Submission #1176343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176343		sean503	Knapsack (NOI18_knapsack)	C++20	100 / 100	66 ms	34376 KiB

knapsack

#include<iostream>
#include<vector>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<set>
#include<math.h>
#include<map>
#include<deque>
#include<unordered_map>
#include<iomanip>
#include<queue>
#include<array>
#include<climits>
#include<cstring>
#include<unordered_set>
#include<cstdint>
#include<typeinfo>
using namespace std;
#define int long long
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    int s,n;
    cin>>s>>n;
    map<int, vector<pair<int, int>>> m;
    for(int i = 0; i<n; i++){
        int x,y,z;
        cin>>x>>y>>z;
        if(y <= s && z>0){
            m[y].push_back({x,z});
        }
    }
    vector<vector<long long>> v(m.size() + 1,vector<long long>(s + 1, INT32_MIN));
    v[0][0] = 0;
    int ind = 1;
    for(auto &[x,z] : m){
        sort(z.begin(), z.end(), greater<pair<int, int>>());
        for (int i = 0; i <= s; i++) {
			v[ind][i] = v[ind - 1][i];
			int a = 0;
			int b = 0;
			int c = 0;
			int d = 0;
			while ((a + 1) * x <= i && b < z.size()) {
				a++;
				d += z[b].first;
				if (v[ind - 1][i - a * x] != INT32_MIN) {
					v[ind][i] = max(v[ind][i], v[ind - 1][i - a * x] + d);
				}
				c++;
				if (c == z[b].second) {
					c = 0;
					b++;
				}
			}
		}
        ind ++;
    }
    cout<<*max_element(v.back().begin(), v.back().end());
}

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