提出 #75560174

---

ソースコード 拡げる

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

const int M = 200005;

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,q;
    cin >> n >> q;
    vector<int>a(n+1);
    vector<int>dp(M+5);
    for(int i = 1; i<=n; i++){
        cin >> a[i];
    }
    for(int i = 1; i<=M; i++){
        for(int j = 1; j<=min(n,i); j++){
            dp[i] = max(dp[i],dp[i-j] + a[j]);
        }
    }
    while(q--){
        int w;
        cin >> w;
        if(w <= M){
            cout << dp[w] << '\n';
        }
        else{
            int ans = 0;
            for(int i = 1; i<=n; i++){
                int amt = (w - M + i-1)/i + 5;
                ans = max(ans,dp[w - amt * i] + amt * a[i]);
            }
            cout << ans << '\n';
        }
    }
    return 0;
}

提出情報

ジャッジ結果