結果

問題 No.783 門松計画
ユーザー maimai
提出日時 2017-07-18 18:16:51
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 25 ms / 2,000 ms
コード長 1,669 bytes
コンパイル時間 2,976 ms
コンパイル使用メモリ 211,356 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-30 18:38:04
合計ジャッジ時間 4,077 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 12 ms
4,380 KB
testcase_11 AC 25 ms
4,380 KB
testcase_12 AC 15 ms
4,376 KB
testcase_13 AC 5 ms
4,376 KB
testcase_14 AC 8 ms
4,376 KB
testcase_15 AC 5 ms
4,380 KB
testcase_16 AC 2 ms
4,380 KB
testcase_17 AC 5 ms
4,376 KB
testcase_18 AC 1 ms
4,376 KB
testcase_19 AC 7 ms
4,376 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 AC 3 ms
4,376 KB
testcase_23 AC 2 ms
4,380 KB
testcase_24 AC 5 ms
4,384 KB
testcase_25 AC 4 ms
4,380 KB
testcase_26 AC 6 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include "bits/stdc++.h"

using namespace std;
typedef long long int ll;

// -----------------------------------------------------------------------
// 余分なコードを削除
// 自作scannerを使わない以外は同じです
// -----------------------------------------------------------------------


inline bool kadomatu(int a, int b, int c) {
    return (a != c) && ((a<b&&b>c) || (a>b&&b<c));
}


int n, cap;
int price[111], len[111];

int dp[51][51][51];


int main() {

    cin >> n >> cap;

    for (int i=0;i<n;++i) {
        cin >> len[i];
    }

    for (int i=0;i<n;++i) {
        cin >> price[i];
    }

    int result = 0;

    for (int i = 0; i < n; ++i) {
        if (price[i] <= cap)
            dp[price[i]][len[i]][0] = len[i];
    }

    for (int cost = 0; cost < cap; ++cost) {
        for (int pre = 0; pre <= 50; ++pre) {
            for (int prepre = 0; prepre <= 50; ++prepre) {
                for (int i = 0; i < n; ++i) {
                    if (cost + price[i] > cap) continue;
                    if (dp[cost][pre][prepre] == 0) continue;

                    if (prepre == 0 || kadomatu(len[i], pre, prepre)) {
                        dp[cost + price[i]][len[i]][pre]
                            = max(
                                dp[cost + price[i]][len[i]][pre],
                                dp[cost][pre][prepre] + len[i]);

                        if (prepre != 0)
                            result = max(result, dp[cost + price[i]][len[i]][pre]);
                    }
                }
            }
        }
    }

    cout << result << endl;


    return 0;
}
0