Submission #568464

#	Time	Username	Problem	Language	Result	Execution time	Memory
568464		jackkkk	Knapsack (NOI18_knapsack)	C++11	37 / 100	1052 ms	340 KiB

knapsack

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <array>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <list>
#include <float.h>
#include <climits>
#include <iomanip>
#include <chrono>

using namespace std;
using namespace std::chrono;


void quit() {
  cout.flush();
  exit(0);
}
const long long md = 1e9+7;

const int mx = 2000;
int main(void){
  //freopen("qwer.in", "r", stdin);
  //freopen("qwer.out", "w", stdout);
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int s, n; cin >> s >> n;
  vector<long long> dp(mx+1, -1e15);
  dp[0]=0;
  for(int i = 0; i < n; i++){
    long long v,w,k; cin >> v >> w >> k;
    for(int curr = 2000; curr >= 0; curr--){
      for(int j = 1; j <= k; j++){
        int x = curr-j*w;
        if(x >= 0){
          dp[curr]=max(dp[curr], dp[x]+v*j);
        }
      }
    }
  }
  long long ans = 0;
  for(int i = s; i >= 0; i--){
    ans = max(ans, dp[i]);
  }
  cout << ans << "\n";
  quit();
}

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