Submission #1102222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102222		Richard_Dyinman	Knapsack (NOI18_knapsack)	C++17	0 / 100	174 ms	262144 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()

#define file \
  freopen("time.in", "r", stdin);\
  freopen("time.out", "w", stdout)

#define OJudge(in,out) \
      freopen(in, "r", stdin);\
      freopen(out, "w", stdout)


#define FIn   \
  cin.tie(0); \
  cout.tie(0); \
  ios_base::sync_with_stdio(false)

const string IN = "input.txt";
const string OUT = "output.txt";

ll n,m,a,b,c;
int  tc;


void solve(){
    cin>>a>>n;
    vector<vector<int>>dp(2010, vector<int>(100010));
    vector<int> v(100100), w(100100), k(100100);
    vector<ll> dp_ans(2010);
    for (int i = 0; i<n; i++){
        cin>>v[i]>>w[i]>>k[i];
    }
    ll rslt = 0;
    for(int i = 1; i<= a; i++){
        ll ans = 0;
        int idx = -1;
        for(int j = 0; j < n; j++){
            if(i - w[j] >= 0 && dp[i - w[j]][j] < k[j] && dp_ans[i - w[j]] + v[j] > ans){
                idx = j;
                ans = dp_ans[i - w[j]] + v[j];
            }
        }
        if (idx != -1) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = dp[i - w[idx]][j];
            }
            dp[i][idx]++;
            dp_ans[i] = ans;
            rslt = max(rslt, ans);
        }
    }
    cout<<rslt;
}


int main() {
    FIn;
    //file;
    bool test = 0;
    if (test)
        cin>>tc;
    else tc = 1;
    for (int i = 1; i<=tc; i++){
        solve();
    }
}

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