結果

問題 No.258 回転寿司(2)
ユーザー maimai
提出日時 2016-05-29 11:14:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 1,127 bytes
コンパイル時間 1,645 ms
コンパイル使用メモリ 170,324 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-11-06 19:03:07
合計ジャッジ時間 5,002 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 67
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;

int val[1001];
int dp[1001];
vector<int> history[1001];

int calc(int n){
    switch(n){
        case 0:
            return val[0];
        case 1:
            return max(val[0],val[1]);
        default:
            if (!dp[n]){
                int a=calc(n-1),b=val[n]+calc(n-2);
                if (a>=b){
                    history[n]=history[n-1];
                    dp[n]=a;
                }else{
                    history[n]=history[n-2];
                    history[n].push_back(n);
                    dp[n]=b;
                }
            }
            return dp[n];
    }
}

int main(){
    int i,j,k,l,m,n,h,x,y,w;
    // int i,j,k;
    
    cin >> n;
    
    if (n==1){
        cin>>i;
        cout<<i<<endl;
        cout<<1<<endl;
        return 0;
    }
    
    for (i=0;i<n;i++){
        scanf("%d",val+i);
    }
    
    history[0].push_back(0);
    history[1].push_back(val[0]>=val[1] ? 0 : 1);
    
    cout << calc(n-1) <<endl;
    for (int e:history[n-1]){
        printf("%d ",e+1);
    }
    cout<<endl;
    
    return 0;
}
0