Submission #744974

#	Time	Username	Problem	Language	Result	Execution time	Memory
744974		glupan	Knapsack (NOI18_knapsack)	C++14	0 / 100	123 ms	262144 KiB

knapsack

#include <bits/stdc++.h>
#define div /
#define ll long long
#define fore(i, l, r) for(int i=int(l); i<int(r); i++)
#define sz(a) int((a).size())

using namespace std;

const int INF = 1e9;
const int MX = 5e5 + 23;
const int MOD = 1000000007;
const int MAX_N = 5e5+23;
const int N = 1e6;

void solve() {
    int s,n;
    cin >> s >> n;
    vector<int>p;
    vector<int>we;
    fore(i,0,n) {
        int v,w,k;
        cin >> v >> w >> k;
        fore(j,0,k) {
            p.push_back(v);
            we.push_back(w);
        }
    }
    int dp[p.size()+5][s+5];
    fore(i,0,p.size()) {
        fore(j,0,s) {
            dp[i][j]=0;
            if(i) {
                dp[i][j]+=dp[i-1][j];
                if(j >= we[i] && dp[i-1][j-we[i]] + p[i] > dp[i][j])
                    dp[i][j] = dp[i-1][j-we[i]] + p[i];
            }
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    cout << dp[p.size()-1][s-1] << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("feast.in","r",stdin);
    //freopen("feast.out","w",stdout);

    int t=1;
    while(t--)
        solve();
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27