oj.uz

답안 #486904

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
486904 2021-11-13T09:06:12 Z YHC2538 Knapsack (NOI18_knapsack) C++14
12 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>
using namespace std;
void _debug(){cerr<<'\n';}
template<typename A,typename...B>
void _debug(A a,B...b){cerr<<a<<' ',_debug(b...);}
#define debug(args...) cerr<<"("<<(#args)<<"): ", _debug(args);
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int N=2005;
ll dp[N];
int main(){
    int s,n; cin>>s>>n;
    vector<vector<pii>> weight(s+1);
    for(int i=1;i<=n;i++){
        int v,w,k; cin>>v>>w>>k;
        weight[w].push_back({v,k});
    }
    for(int i=1;i<=s;i++){
        sort(all(weight[i]));
        if(weight[i].size()==0) continue;
        int id=0; //next item with weight i
        for(int j=1;j*i<=s;j++){
            if(id>=weight[i].size()) break;
            for(int k=s;k>=i;k--){
                dp[k]=max(dp[k],dp[k-i]+weight[i][id].first);
            }
            if(--weight[i][id].second==0) id++;
        }
    }
    cout<<dp[s]<<'\n';
}

Compilation message

knapsack.cpp: In function 'int main()':
knapsack.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |             if(id>=weight[i].size()) break;
      |                ~~^~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Incorrect 1 ms 204 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Incorrect 1 ms 204 KB Output isn't correct
6 Halted 0 ms 0 KB -