Submission #782228

#	Time	Username	Problem	Language	Result	Execution time	Memory
782228		devariaota	Knapsack (NOI18_knapsack)	C++17	100 / 100	154 ms	248352 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
typedef long long ll;
const ll INF = 1e9; //4e18;
const ll MOD = 1e9 + 7;
const ll MAXN = 1e5 + 5;
const ll LOG = 30; //20;
const double EPS = 1e-9;
#define vi vector <int>
#define vll vector <ll>
#define pii pair <int, int>
#define pll pair <ll, ll>
#define ipi pair <int, pii>
#define lpl pair <ll, pll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define apaaja                          ios_base::sync_with_stdio(0);       cin.tie(0);                         cout.tie(0);                    
ll t, n;
vector < vector <pll> > v;
vector <pll> item;

bool mrg (pll a, pll b){
    return a.fi > b.fi;
}

int main(){
    apaaja
    cin >> t >> n;
    v.resize(t+1);
    for(ll i = 1; i <= n; i++){
        ll l, e, k;
        cin >> l >> e >> k;
        v[e].pb(mp(l, k));
    }

    item.push_back({0, 0});
    for(ll i = 1; i <= t; i++){
        sort(v[i].begin(), v[i].end(), mrg);
        ll cnt = 0, j = 0;
        while(cnt < (t/i) and j < v[i].size()){
            item.push_back({v[i][j].first, i});
            v[i][j].second--;
            cnt++;
            if(v[i][j].second == 0) j++;
        }
    }

    // for(auto i : item){
    //     cout << i.first << ' ' << i.second << '\n';
    // }

    ll dp [item.size()+1][2005];
    memset(dp, 0, sizeof(dp));
    for(ll i = 1; i < item.size(); i++){
        for(ll j = 1; j <= t; j++){
            dp[i][j] = dp[i-1][j];
            if(j >= item[i].se){
                dp[i][j] = max(dp[i][j], dp[i-1][j-item[i].second] + item[i].fi);
            }
            // cout << i << " << " << j << " << " << dp[i][j] << endl;
        }
    }
    cout << dp[item.size() - 1][t] << endl;

    // vector<ll> dp(t + 1, 0);
    // for(ll i = 1; i <= item.size(); i++){
    //     vector<ll> tmp = dp;
    //     for(ll j = 1; j <= t; j++){
    //         if(j >= item[i].se){
    //             tmp[j] = max(tmp[j], dp[j-item[i].second] + item[i].fi);
    //         }
    //         // cout << i << " << " << j << " << " << dp[i][j] << endl;
    //         dp = tmp;
    //         for(auto i : dp) cout << i << ' ';
    //         cout << '\n';
    //     }
    // }

    // cout << dp[t] << endl;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:44:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         while(cnt < (t/i) and j < v[i].size()){
      |                               ~~^~~~~~~~~~~~~
knapsack.cpp:58:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(ll i = 1; i < item.size(); i++){
      |                   ~~^~~~~~~~~~~~~

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