Submission #574563

#	Time	Username	Problem	Language	Result	Execution time	Memory
574563		jackkkk	Knapsack (NOI18_knapsack)	C++11	100 / 100	61 ms	4932 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);
  long long s,n; cin >> s >> n;
  vector<vector<pair<long long, long long>>> tmp(2001);
  for(long long i = 0; i < n; i++){
    long long v,w,k; cin >> v >> w >> k;
    tmp[w].emplace_back(v,k);
  }
  for(long long i = 0; i <= 2000; i++){
    sort(tmp[i].begin(), tmp[i].end(), [](pair<int,int> a, pair<int, int> b){
      return a.first > b.first;
    });
  }
  vector<long long> dp(2001, -1);
  dp[0]=0;
  for(long long w = 1; w < 2000; w++){
    long long cnt = 0;
    long long mx = 2000/w;
    for(const auto &item : tmp[w]){
      long long upto = min(item.second, mx-cnt);
      for(long long i = 0; i < upto; i++){
        for(long long 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;
      }
    }
  }
  long long ans = 0;
  for(long long i = 0; i <= s; i++){
    ans = max(ans, dp[i]);
  }
  cout << ans << "\n";
  quit();
}

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