Submission #850279

#	Time	Username	Problem	Language	Result	Execution time	Memory
850279		now_or_never	Knapsack (NOI18_knapsack)	C++14	100 / 100	58 ms	4948 KiB

knapsack

//Name: Nguyen Quang Huy
//Time: 2023-2024
#include <bits/stdc++.h>
#define Foru(i,a,b) for(int i=(a);i<=(b);++i)
#define Ford(i,a,b) for(int i=(a);i>=(b);--i)
#define se second
#define fi first
#define nl cout << "\n";
#define pi pair<int,int>
#define bit(x, k) (1ll&((x)>>(k)))
#define sz size
#define io() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ms(a,i) memset(a,i,sizeof(a))
#define pb(x) push_back(x)
#define epb(x,y) emplace_back({x,y})
#define all(x) (x).begin(), (x).end()
#define hr cout << "-----------------------------------------------\n";

typedef long long ll;

using namespace std;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const int maxn=1e5+7;

template<class T> T mi(T a, T b){return (a<=b)?a:b;}
template<class T> T ma(T a, T b){return (a>=b)?a:b;}
template<class T> void Unique(vector<T> &v){sort(all(v));v.erase(unique(all(v)), v.end());}

struct Item{
    int w,v,k;
} items[maxn];

int n,s;
ll dp[maxn];

void ioFile(string str){
    freopen((str+".in").c_str(),"r",stdin);
    freopen((str+".out").c_str(),"w",stdout);
}

void inp(){
    cin >> s >> n;
    Foru(i,1,n){
        cin >> items[i].v >> items[i].w >> items[i].k;
    }
}

void solve(){
    vector<pi> tmp[2001];
    Foru(i,1,n){
        tmp[items[i].w].push_back({items[i].v,items[i].k});
    }
    Foru(i,1,s){
        if(tmp[i].empty())continue;
        sort(all(tmp[i]),[&](pi a, pi b){
            return a.fi>b.fi;
        });
        int id=0;
        Foru(j,1,s/i){
            if(id>=tmp[i].sz())break;
            Ford(k,s,1)if(k>=i){
                dp[k]=max(dp[k],dp[k-i]+tmp[i][id].fi);
            }
            tmp[i][id].se--;
            if(tmp[i][id].se==0)++id;
        }
    }
    cout << dp[s];
}

int main(){
	io();
    inp();
    solve();

	return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:61: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]
   61 |             if(id>=tmp[i].sz())break;
      |                ~~^~~~~~~~~~~~~
knapsack.cpp: In function 'void ioFile(std::string)':
knapsack.cpp:38:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     freopen((str+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:39:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     freopen((str+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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