結果

問題 No.572 妖精の演奏
ユーザー horiesiniti
提出日時 2016-07-08 09:51:58
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 37 ms / 2,000 ms
コード長 1,585 bytes
コンパイル時間 531 ms
コンパイル使用メモリ 59,484 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-12 23:25:27
合計ジャッジ時間 1,699 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:12:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   12 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
main.cpp:13:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   13 |         scanf("%d",&m);
      |         ~~~~~^~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
const int LIMIT=100;
int main(){
    long long int as[LIMIT][LIMIT],dp[LIMIT][LIMIT],nextdp[LIMIT][LIMIT],ansdp[LIMIT][LIMIT];
    int n,m;
    scanf("%d",&n);
    scanf("%d",&m);
    bool last1=(n%2==1);
    n/=2;
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
            std::cin>>as[i][j];
            dp[i][j]=as[i][j];
        }
    }
    memset(ansdp,0,sizeof(ansdp));
    bool first=true;
    while(n>0){
        memset(nextdp,0,sizeof(nextdp));
        if(n%2==1){
            for(int i=0;i<m;i++){
                for(int j=0;j<m;j++){
                    for(int k=0;k<m;k++){
                        for(int l=0;l<m;l++){
                            
                            long long int t;    
                            if(first==true){
                                t=dp[i][l];
                                
                            }else{
                                t=dp[i][j]+as[j][k]+ansdp[k][l];
                            }
                            nextdp[i][l]=std::max(nextdp[i][l],t);
                        }
                    }
                }
            }
            first=false;
            memcpy(ansdp,nextdp,sizeof(nextdp));
        }
        
        memset(nextdp,0,sizeof(nextdp));
        for(int i=0;i<m;i++){
            for(int j=0;j<m;j++){
                for(int k=0;k<m;k++){
                    for(int l=0;l<m;l++){
                        long long int t=dp[i][j]+as[j][k]+dp[k][l];
                        nextdp[i][l]=std::max(t,nextdp[i][l]);
                    }
                }
            }
        }
        memcpy(dp,nextdp,sizeof(nextdp));
        n/=2;
    }
    if(last1==true){
        memset(nextdp,0,sizeof(nextdp));
        for(int i=0;i<m;i++){
            for(int j=0;j<m;j++){
                for(int k=0;k<m;k++){
                    long long int t=as[i][j]+ansdp[j][k];
                    nextdp[i][k]=std::max(t,nextdp[i][k]);
                }
            }
        }
        memcpy(ansdp,nextdp,sizeof(nextdp));
    }
    long long int ans=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
            ans=std::max(ans,ansdp[i][j]);
        }
    }
    std::cout<<ans<<"\n";
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0