秋祭 | 静岡高校工学部



卬高杯


提出詳細

提出id提出時刻ユーザー名問題言語判定状況判定実行時間
1150322023-10-26 06:20:08momoyuuGcpp16/16AC58

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){ 
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int n,m;
    cin>>n>>m;
    vector<ll> dp(m+1,0);
    vector<ll> x(n),y(n);
    for(int i = 0;i<n;i++) cin>>x[i];
    for(int i = 0;i<n;i++) cin>>y[i];
    for(int i = 0;i<n;i++){
        vector<ll> ndp(m+1,0);
        for(int j = 0;j<=m;j++){
            ndp[j] = max(ndp[j],dp[j]);
            if(j+y[i]<m) ndp[j+y[i]] = max(ndp[j+y[i]],dp[j]+x[i]);
        }
        swap(ndp,dp);
    }
    ll ans = 0;
    for(int i = 0;i<m;i++) ans = max(ans,dp[i]);
    cout<<ans<<endl;
}

sample1.txt AC 2
case1.txt AC 2
case2.txt AC 58
case3.txt AC 2
case4.txt AC 12
case5.txt AC 34
case6.txt AC 17
case7.txt AC 29
case8.txt AC 22
case9.txt AC 14
case10.txt AC 49
case11.txt AC 9
case12.txt AC 10
case13.txt AC 31
case14.txt AC 39
case15.txt AC 4
58 AC58 AC