Submission #1275238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275238		snegle	Knapsack (NOI18_knapsack)	C++20	73 / 100	179 ms	327680 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<vs> vvs;
typedef vector<bool> vb;
typedef vector<vb > vvb;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
const int MOD = 1e9 + 7;
const ll INF = (LLONG_MAX/2)-1;

#define dbg(v) cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;

int main() {
    int n,s;
    cin>>s>>n;
    vector<int> verdi(n+1);
    vector<int> vekt(n+1);
    vector<int> antall(n+1);
    for (int i=1;i<=n;i++){cin>>verdi[i]>>vekt[i]>>antall[i];}
    vector<vector<int>> dp(n+1,vector<int> (s+1));
    for (int i=1;i<=n;i++) {
        for (int j=0;j<=s;j++) {
            dp[i][j] = dp[i-1][j];
            for (int k=1;k<=antall[i];k++) {
                if (j-k*vekt[i] >= 0) {
                    dp[i][j] = max(dp[i][j], dp[i-1][j-k*vekt[i]] + k*verdi[i]);
                } else {
                    break;
                }
            }

        }
    }
    cout<<dp[n][s]<<endl;
    return 0;
}

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