이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <iostream>
#include<queue>
#include<vector>
#include<utility>
using namespace std;
typedef long long ll;
const int sz=2001;
const int sz1=1e6+1;
ll n,x,k,i,j,w,m,high,track;
vector<pair<ll,ll>>a;
ll dp[sz][sz];
int main(){
cin>>w>>n;
map<ll,vector<array<ll,2>>>wei;
for(int i=0;i<n;i++){
ll t,u,v;cin>>t>>u>>v;
high=max(high,u);
if(u<=2000 and v>0) wei[u].push_back({t,v});
} for(int i=1;i<=w;i++){
for(int j=0;j<=w;j++){
dp[i][j]=INT_MIN;
}
}
for(int poi=0;poi<=w;poi++){
for(auto [we,at]:wei){
sort(at.rbegin(),at.rend());
for(int i=0;i<=w;i++){
if (poi>0) dp[poi][i]=dp[poi-1][i];
ll profit,used,cops;
profit=used=x=0; cops=1;
while(x<at.size() and cops*we<=i){
ll y=i-cops*we;
profit+=at[x][0];
if (dp[we-1][y]!=INT_MIN){
dp[we][i]=max(dp[we][i],dp[we-1][y]+profit);
}
used++;cops++;
if (used==at[x][1]){x++; used=0;}
}
}
}
} cout<<dp[w][w]<<endl;
}
컴파일 시 표준 에러 (stderr) 메시지
knapsack.cpp: In function 'int main()':
knapsack.cpp:32:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | while(x<at.size() and cops*we<=i){
| ~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |