結果

問題 No.258 回転寿司(2)
ユーザー koyoprokoyopro
提出日時 2015-10-07 19:48:44
言語 C++11
(gcc 13.3.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,026 bytes
コンパイル時間 2,059 ms
コンパイル使用メモリ 164,956 KB
実行使用メモリ 117,632 KB
最終ジャッジ日時 2024-11-24 10:39:44
合計ジャッジ時間 60,841 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 60 TLE * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define REP(i, n) for(int i=0; i<(n); i++)
#define RREP(i, n) for(int i=(n-1); i>=0; i--)
#define MAX 111111
#define ALL(a) (a).begin(),(a).end()
#define CONTAIN(a, b) find(ALL(a), (b)) != (a).end()

int N;
vector< pair<bool, vector<int> > > dp(MAX);
signed main()
{
    cin >> N;
    vector<int> V(N);
    REP(i,N) cin >> V[i];
    int maxv = 0;
    dp[0].first = true;
    REP(i,N) {
        int v = V[i];
        RREP(j,MAX) {
            if (i > 0 && CONTAIN(dp[j].second, i-1)) continue;
            if (!dp[j].first) continue;
            if (dp[j+v].first) {
                vector<int> w = dp[j+v].second;
                if (w[w.size()-1] < i) continue;
            }
            dp[j+v].second = dp[j].second;
            dp[j+v].second.push_back(i);
            dp[j+v].first = true;
            maxv = max(maxv, j+v);
        }
    }
    cout << maxv << endl;
    for (auto&& a : dp[maxv].second) {
        cout << a+1 << " ";
    }
    cout << endl;
    return 0;
}
0