結果

問題 No.783 門松計画
ユーザー treeone
提出日時 2019-01-12 00:43:35
言語 C++17(1z)
(gcc 8.2.0)
結果
AC  
実行時間 120 ms
コード長 1,690 Byte
コンパイル時間 2,315 ms
使用メモリ 3,720 KB
最終ジャッジ日時 2019-02-23 19:35:55

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0test01.txt AC 11 ms
3,716 KB
0test02.txt AC 21 ms
3,704 KB
0test03.txt AC 9 ms
3,720 KB
1simple00.txt AC 7 ms
3,704 KB
1simple01.txt AC 8 ms
3,704 KB
1simple02.txt AC 9 ms
3,704 KB
1simple03.txt AC 8 ms
3,704 KB
1simple04.txt AC 8 ms
3,700 KB
1simple05.txt AC 7 ms
3,700 KB
1simple06.txt AC 10 ms
3,716 KB
5extreme00.txt AC 49 ms
3,720 KB
5extreme01.txt AC 55 ms
3,716 KB
5extreme02.txt AC 120 ms
3,716 KB
5extreme03.txt AC 36 ms
3,720 KB
7gen_case1.txt AC 36 ms
3,716 KB
7gen_case2.txt AC 11 ms
3,720 KB
7gen_case3.txt AC 10 ms
3,716 KB
7gen_case4.txt AC 27 ms
3,716 KB
7gen_case5.txt AC 9 ms
3,700 KB
7gen_case6.txt AC 23 ms
3,716 KB
7gen_case7.txt AC 15 ms
3,700 KB
7gen_case8.txt AC 13 ms
3,704 KB
7gen_case9.txt AC 9 ms
3,704 KB
7gen_case10.txt AC 10 ms
3,700 KB
7gen_case11.txt AC 15 ms
3,720 KB
7gen_case12.txt AC 14 ms
3,720 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define int long long
#define all(a) a.begin(), a.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

int dp[52][52][52], nxt[52][52][52];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, c;
    cin >> n >> c;
    vector<int> l(n), w(n);
    rep(i, 0, n) cin >> l[i];
    rep(i, 0, n) cin >> w[i];
    rep(i, 0, 52) rep(j, 0, 52) rep(k, 0, 52) dp[i][j][k] = -1;
    dp[0][0][0] = 0;
    int ans = 0;
    rep(i, 0, c){
        rep(j, 0, 52) rep(k, 0, 52) rep(m, 0, 52) nxt[j][k][m] = -1;
        rep(j, 0, c){
            rep(k, 0, 52){
                rep(m, 0, 52){
                    if(dp[j][k][m] == -1) continue;
                    rep(p, 0, n){
                        if(max({k, m, l[p]}) == m || min({k, m, l[p]}) == m || i < 2){
                            if((k != m && m != l[p] && k != l[p]) || i < 2){
                                if(j + w[p] <= c){
                                    nxt[j + w[p]][m][l[p]] = max(nxt[j + w[p]][m][l[p]], dp[j][k][m] + l[p]);
                                }
                            }
                        }
                    }
                }
            }
        }
        swap(dp, nxt);
        if(i >= 2){
            rep(j, 0, c + 1){
                rep(k, 1, 52){
                    rep(m, 1, 52){
                        ans = max(ans, dp[j][k][m]);
                    }
                }
            }
        }
    }
    cout << ans << endl;
}
0