oj.uz

Submission #728510

# Submission time Handle Problem Language Result Execution time Memory
728510 2023-04-22T14:39:39 Z Dead_Inside7 Knapsack (NOI18_knapsack) C++17
12 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int cap,n;cin>>cap>>n;
    vector<vector<pair<long long,long long>>> arr(cap+1);
    for(int j=0;j<n;j++){
        int value,weight,amt;
        cin>>value>>weight>>amt;
        arr[weight].push_back({value,amt});
    }
    vector<pair<long long,long long>> knapsack;
    for(int j=1;j<=cap;j++){
        sort(arr[cap].begin(),arr[cap].end());
        reverse(arr[cap].begin(),arr[cap].end());
        vector<long long> subs;
        int i=0;
        while(subs.size()<cap/j&&i<arr[j].size()){
        	while(subs.size()<(cap/j)&&arr[j][i].second>0){
        		subs.push_back(arr[j][i].first);
        		arr[j][i].second--;
        	}
        	i++;
        }
        for(auto it:subs) knapsack.push_back({it,j});
    }
    vector<long long> dp(cap+1);
    dp[0]=0;
    for(int j=0;j<knapsack.size();j++){
    	for(int i=cap;i>=0;i--){
    	if((i-knapsack[j].second)>=0) dp[i]=max(dp[i],dp[i-knapsack[j].second] + knapsack[j].first);
    }
    }
    cout<<dp[cap]<<endl;
    return 0;
}

Compilation message

knapsack.cpp: In function 'int main()':
knapsack.cpp:17:26: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   17 |         while(subs.size()<cap/j&&i<arr[j].size()){
      |               ~~~~~~~~~~~^~~~~~
knapsack.cpp:17:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         while(subs.size()<cap/j&&i<arr[j].size()){
      |                                  ~^~~~~~~~~~~~~~
knapsack.cpp:18:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |          while(subs.size()<(cap/j)&&arr[j][i].second>0){
      |                ~~~~~~~~~~~^~~~~~~~
knapsack.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int j=0;j<knapsack.size();j++){
      |                 ~^~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -