Submission #539034

#	Time	Username	Problem	Language	Result	Execution time	Memory
539034		man_in_danger	Knapsack (NOI18_knapsack)	C++14	100 / 100	238 ms	39712 KiB

knapsack

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define mk make_tuple
#define f first
#define s second

#define turbo(){	\
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL); \
}

#define FIO(){	\
    freopen("feast.in", "r", stdin); \
    freopen("feast.out", "w", stdout);\
}

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<PII, null_type,less<PII>, rb_tree_tag,tree_order_statistics_node_update>

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> PII;

const ll mod = 1e9+7;
const ll inf = 1e18;
const ll inf2 = 1e9;

vector<int> v[2005], num[2005];
map<int, map<int, int>> mp;
int tra[2005][2005];
ll dp[2005];
int main()
{
    turbo();
    //FIO()
    int t = 1;
    //cin >> t;
    while(t--){
        int s, n, i, j, w, va, k;
        ll ans = 0;
        v[2].pb(1);
        cin >> s >> n;
        for(i = 0; i < n; i++){
            cin >> va >> w >> k;
            v[w].pb(va);
            mp[w][va] = k;
        }
        for(i = 1; i <= s; i++){
            sort(v[i].rbegin(), v[i].rend());
            for(j = 0; j < v[i].size(); j++){
                int l = 0;
                while(l < mp[i][v[i][j]] && num[i].size() <= 2000){
                    num[i].pb(v[i][j]);
                    l++;
                }
            }
        }
        for(i = 1; i <= s; i++){
            ll mx = 0, up1 = -1, up2 = -1;
            for(j = 1; j <= s; j++){
                if(i - j >= 0  && tra[i - j][j] < num[j].size()){
                    if(dp[i - j] + num[j][tra[i - j][j]] > mx){
                        mx = dp[i - j] + num[j][tra[i - j][j]];
                        up1 = i - j;
                        up2 = j;
                    }
                }
            }
            if(mx){
                for(j = 1; j <= s; j++){
                    tra[i][j] += tra[up1][j];
                }
                tra[i][up2]++;
                dp[i] = mx;
            }
            ans = max(dp[i], ans);
        }
        cout << ans << '\n';
    }
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:59:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             for(j = 0; j < v[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~
knapsack.cpp:70:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |                 if(i - j >= 0  && tra[i - j][j] < num[j].size()){
      |                                   ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

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