Submission #574558

#	Time	Username	Problem	Language	Result	Execution time	Memory
574558		jackkkk	Knapsack (NOI18_knapsack)	C++11	12 / 100	1 ms	396 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>
using namespace std;


void quit() {
  cout.flush();
  exit(0);
}




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<vector<pair<int, int>>> tmp(2001);
  for(int i = 0; i < n; i++){
    int v,w,k; cin >> v >> w >> k;
    tmp[w].emplace_back(v,k);
  }
  for(int i = 0; i <= 2000; i++){
    sort(tmp[i].begin(), tmp[i].end());
  }
  vector<int> dp(2001, -1);
  dp[0]=0;
  for(int w = 1; w < 2000; w++){
    int cnt = 0;
    int mx = 2000/w;
    for(const auto &item : tmp[w]){
      int upto = min(item.second, mx-cnt);
      for(int i = 0; i < upto; i++){
        for(int j = 2000-w; j >= 0; j--){
          if(dp[j] >= 0){
            dp[j+w]=max(dp[j+w],dp[j]+item.first);
          }
        }
      }
      cnt += item.second;
      if(cnt > mx){
        break;
      }
    }
  }
  int ans = 0;
  for(int i = 0; i <= s; i++){
    ans = max(ans, dp[i]);
  }
  cout << ans << "\n";
  quit();
}

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