Submission #866203

#	Time	Username	Problem	Language	Result	Execution time	Memory
866203		Srivardhan_M	Knapsack (NOI18_knapsack)	C++14	100 / 100	88 ms	36692 KiB

knapsack

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #include <sys/resource.h>
using namespace std;
using namespace __gnu_pbds;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


const long long infty = 1e18;
#define num1 1000000007
#define num2 998244353
#define rep(i,a,n) for(ll i=a;i<n;i++)
#define repd(i,a,n) for(ll i=a; i>=n; i--)
#define pb push_back
#define pob pop_back
#define f first
#define s second
#define fix(f,n) std::fixed<<std::setprecision(n)<<f
#define all(x) x.begin(), x.end()
#define M_PI 3.14159265358979323846
#define epsilon (double)(0.000000001)
#define popcount __builtin_popcountll
#define fileio(x) freopen("input.txt", "r", stdin); freopen(x, "w", stdout);
#define out(x) cout << ((x) ? "Yes" : "No")<<endl;
#define len(x) x.size()
#define vvll(vec,n,m) vector<vector<long long>> vec(n, vector<long long> (m))
#define start_clock() auto start_time = std::chrono::high_resolution_clock::now();
#define measure() auto end_time = std::chrono::high_resolution_clock::now(); cerr << (end_time - start_time)/std::chrono::milliseconds(1) << "ms" << endl;
#define println(x) cout<<x<<"\n";
 
 
typedef long long ll;
typedef long double ld;
typedef vector<long long> vll;
typedef pair<long long, long long> pll;
typedef vector<pair<long long, long long>> vpll;
typedef vector<int> vii;

ll sqr(ll x){
    return x*x;
}

void print(vector<vll> &v){
    cout<<"=========================="<<endl;
    rep(i, 0, v.size()) {
        rep(j, 0, v[i].size()) cout<<v[i][j]<<" ";
        cout<<endl;
    }
    cout<<"=========================="<<endl;
}
void print(vll &v){
    cout<<"=========================="<<endl;
    rep(i, 0, v.size()) cout<<v[i]<<" ";
    cout<<endl;
    cout<<"=========================="<<endl;
}

const ll maxn = 2e3+5;
vector<pll> ed[maxn];
ll dp[maxn][maxn];

ll func(ll ind, ll tar){
    if(ind <  0) return 0;
    if(dp[ind][tar] != -1) return dp[ind][tar];
    ll res = func(ind-1, tar);
    ll tmp = tar;
    ll sum = 0;
    for(auto &pr: ed[ind]){
        if(tmp < ind) break;
        ll num = pr.second;
        ll val =  pr.f;
        while(num--){
            if(tmp<ind) break;
            tmp -= ind;
            sum += val;
            res = max(res, func(ind-1,tmp)+sum);
        }
    }
    return dp[ind][tar] = res;
}

void solve(){
    memset(dp, -1, sizeof(dp));
    ll tar, n; cin>>tar>>n;
    rep(i, 0, n){
        ll v, w, k; cin>>v>>w>>k;
        ed[w].pb({v, k});
    }
    rep(i, 0, maxn){
        sort(all(ed[i]));
        reverse(all(ed[i]));
    }
    cout<<func(maxn-1, tar)<<endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t = 1;
    // cin>>t;
    while(t--){
        solve();
    }
}

Compilation message (stderr)

knapsack.cpp: In function 'void print(std::vector<std::vector<long long int> >&)':
knapsack.cpp:15:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define rep(i,a,n) for(ll i=a;i<n;i++)
......
   48 |     rep(i, 0, v.size()) {
      |         ~~~~~~~~~~~~~~          
knapsack.cpp:48:5: note: in expansion of macro 'rep'
   48 |     rep(i, 0, v.size()) {
      |     ^~~
knapsack.cpp:15:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define rep(i,a,n) for(ll i=a;i<n;i++)
......
   49 |         rep(j, 0, v[i].size()) cout<<v[i][j]<<" ";
      |             ~~~~~~~~~~~~~~~~~   
knapsack.cpp:49:9: note: in expansion of macro 'rep'
   49 |         rep(j, 0, v[i].size()) cout<<v[i][j]<<" ";
      |         ^~~
knapsack.cpp: In function 'void print(vll&)':
knapsack.cpp:15:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define rep(i,a,n) for(ll i=a;i<n;i++)
......
   56 |     rep(i, 0, v.size()) cout<<v[i]<<" ";
      |         ~~~~~~~~~~~~~~          
knapsack.cpp:56:5: note: in expansion of macro 'rep'
   56 |     rep(i, 0, v.size()) cout<<v[i]<<" ";
      |     ^~~

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