Submission #1004743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004743		vjudge1	Knapsack (NOI18_knapsack)	C++17	100 / 100	49 ms	5212 KiB

knapsack

#include<bits/stdc++.h>

typedef long long ll;
typedef std::pair<int, int> pii;

#define fi first
#define se second
#define pb push_back
#define inarr(n, arr) for(int ax = 0; ax<(n); ax++)cin>>(arr)[ax];
#define all(x) (x).begin(), (x).end()
#define allr(x) x.rbegin(),(x).rend()
#define Ones(n) __builtin_popcount(n)
#define el '\n'
#define PI acos(-1)
#define sin(a) sin((a)*PI/180)
#define cos(a) cos((a)*PI/180)
#define tan(a) tan((a)*PI/180)
#define yes cout<<"YES\n";
#define no cout<<"NO\n";
#define int long long
using namespace std;

void Sparnke() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
//#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
//#endif
}


int dx[] = {+0, +0, -1, +1, +1, +1, -1, -1};
int dy[] = {-1, +1, +0, +0, +1, -1, +1, -1};

const double EPS = 1e-9;
const ll N = 500 + 5, INF = INT_MAX, MOD = 1e9 + 7;

ll gcd(ll x, ll y) {
    return y ? gcd(y, x % y) : x;
}

ll lcm(ll a, ll b) {
    return (a * b) / __gcd(a, b);
}

ll mul(const ll &a, const ll &b) {
    return (a % MOD + MOD) * (b % MOD + MOD) % MOD;
}

ll add(const ll &a, const ll &b) {
    return (a + b + 2 * MOD) % MOD;
}


void solve() {
    int n, s;
    cin >> s >> n;
    vector<pair<int, int>> weights[s + 5];
    for (int i = 0; i < n; ++i) {
        int v, w, k;
        cin >> v >> w >> k;
        weights[w].emplace_back(v, k);
    }
    vector<pair<int, int>> v;
    for(int i = 1; i <= s; i++){
        sort(allr(weights[i]));
        int take = s / i;
        for(auto &p : weights[i]){
            while (p.second > 0 && take > 0){
                v.push_back({i, p.first});
                p.second--, take--;
            }
        }
    }
    vector<int> dp(s + 5, 0);
    for (int i = 0; i < v.size(); ++i) {
        for (int w = s; w >= 0; w--) {
            if(w - v[i].first >= 0)
                dp[w] = max(dp[w], dp[w - v[i].first] + v[i].second);
        }
    }
    cout << *max_element(all(dp));
}


signed main() {
    Sparnke();
    int t = 1, cnt = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:77:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i = 0; i < v.size(); ++i) {
      |                     ~~^~~~~~~~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:89:16: warning: unused variable 'cnt' [-Wunused-variable]
   89 |     int t = 1, cnt = 1;
      |                ^~~

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