Submission #1163361

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1163361	2025-03-08 03:09:29	boclobanchat	Knapsack (NOI18_knapsack)	C++20	100 / 100	39 ms	1740 KiB

knapsack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
struct item { int v,w,k; };
bool sortt(item a,item b) { if(a.w==b.w) return a.v>b.v;return a.w<b.w; }
const int MAXN=2024;
const long long INF=1e18;
vector<int> vi[MAXN];
long long dp[MAXN];
item A[MAXN*50];
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int s,n;
  cin>>s>>n;
  for(int i=1;i<=n;i++) cin>>A[i].v>>A[i].w>>A[i].k;
  sort(A+1,A+n+1,sortt);
  for(int i=1;i<=n;i++)
  {
    if(A[i].w>s) break;
    while(A[i].k--&&(int)vi[A[i].w].size()*A[i].w<=s) vi[A[i].w].push_back(A[i].v);
  }
  for(int i=1;i<=s;i++) dp[i]=-INF;
  for(int i=1;i<=s;i++)
  {
    for(int j=s;j>=0;j--)
    {
      int p=j;
      long long w=0;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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