結果

問題 No.783 門松計画
ユーザー mai
提出日時 2017-07-18 18:16:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 27 ms / 2,000 ms
コード長 1,669 bytes
コンパイル時間 3,034 ms
コンパイル使用メモリ 213,800 KB
最終ジャッジ日時 2025-01-05 01:42:12
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

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