제출 #1102232

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1102232		Richard_Dyinman	Knapsack (NOI18_knapsack)	C++14	0 / 100	34 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;
int dp[2100][100100];
ll dp_ans[2100];
int v[100100], w[100100], k[100100];


void solve(){
    cin>>a>>n;
    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