Submission #493261

#	Time	Username	Problem	Language	Result	Execution time	Memory
493261		AkiYuu	Knapsack (NOI18_knapsack)	C++17	100 / 100	93 ms	32308 KiB

knapsack

/*

Problems:
Author: AkiYuu

*/

#include <bits/stdc++.h>
#define task "GROUP"
#define ll long long
#define ld long double
#define pb(u) emplace_back(u)
#define ffw(i,a,b) for (ll i = a; i <= b; i++)
#define fbw(i,b,a) for (ll i = b; i >= a; i--)
#define adj(v,adj,u) for (auto v : adj[u])
#define rep(i,a) for (auto i : a)
#define reset(a) memset(a, 0, sizeof(a))
#define sz(a) a.size()
#define all(a) a.begin(),a.end()

using namespace std;

inline namespace FastIO {
	const int BSZ = 1<<15;
	char ibuf[BSZ]; int ipos, ilen;
	char nc() { //
		if (ipos == ilen) {
			ipos = 0; ilen = fread(ibuf,1,BSZ,stdin);
			if (!ilen) return EOF;
		}
		return ibuf[ipos++];
	}
	void readstr(string& x) {
		char ch; while (isspace(ch = nc()));
		do { x += ch; } while (!isspace(ch = nc()) && ch != EOF);
	}

	template<class T> void readnum(T& x){
		char ch; int sgn = 1;
		while (!isdigit(ch = nc())) if (ch == '-') sgn *= -1;
		x = ch-'0'; while (isdigit(ch = nc())) x = x*10+(ch-'0');
		x *= sgn;
	}
}

void fastio(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
//	freopen(task".inp", "r", stdin);
//	freopen(task".out", "w", stdout);
}

const int mxn = 1e6 + 5;
const ll inf = 1e18 + 7;
typedef pair<ll, ll> ii;

int S , n;
vector < ii >  a[mxn];
int dp[mxn];

void solve(){
    cin >> S >> n;
    ffw(i,1,n){
        int v, k, w;
        cin >> v >> w >> k;
        a[w].pb(ii(v,k));;
    }
    reset(dp);
    ffw(w,1,S){
        if (a[w].size() == 0 ) continue;
        sort(all(a[w]), greater<ii>() );
        int id = 0;
        for (int i = w; i <= S && id < sz(a[w]) ; i+=w){
            int val = a[w][id].first;
//            cout << val << " ";
            if ( --a[w][id].second == 0 ) id++;
            fbw(j,S,w) dp[j] = max(dp[j], dp[j - w] + val);
        }
//        cout << '\n';
    }
    cout << *max_element(dp+1,dp+1+S);
}

int main(){
	fastio();
	solve();
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:73:38: 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]
   73 |         for (int i = w; i <= S && id < sz(a[w]) ; i+=w){
      |                                      ^

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