Submission #821679

#	Time	Username	Problem	Language	Result	Execution time	Memory
821679		Zobio	Knapsack (NOI18_knapsack)	C++14	0 / 100	83 ms	19788 KiB

knapsack

#include<bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef long double ld;
typedef vector<double> vd;
typedef vector<long long> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
typedef vector<pair<int,int>> vpi;
typedef vector<pair<ll,ll>> vpl;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef set<int> si;
typedef set<ll> sl;
 
#define all(c) (c).begin(),(c).end()
#define srt(c) sort(all(c))
#define srtrev(c) sort(all(c)); reverse(all(c))
#define fr(i,a,n) for( int i=a;i<n;i++)
#define frev(i,a,n) for( int i=a;i>=n;i--)
#define inp(ve) for(int i=0;i<ve.size();i++) cin>>ve[i];
#define PB push_back
#define F first
#define S second
#define cont continue
#define br break
#define MP make_pair
#define nl cout<<"\n"
#define M 1000000007
 
const ll INF = 1e17;
const ll NINF = -1e17;
const int N = 1e6+1;

int lindieq (int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = lindieq(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}
 
ll gcd (ll c, ll d) {
    ll a = max(c,d);
    ll b = min(c,d);
    while (b) {
        a %= b;
        ll temp = a;
        a=b;
        b=temp;
    }
    return a;
}
 
ll bexp(ll a,ll b){
    ll res = 1;
    while(b>0){
        if(b%2) res = res*a;
        a*=a;
        b/=2;
    }
    return res;
}
 
vb isprime(int n){
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }
    return is_prime;
}
 
ll bexpm(ll a,ll b){
    ll res = 1;
    while(b>0){
        if(b%2) res = (res*a)%M;
        a = (a*a)%M;
        b/=2;
    }
    return res;
}

// int par[N];
// int r[N];

// int find(int a){
//     if(par[a]==a) return a;
//     else return par[a] = find(par[a]);
// }

// bool isSame(int a, int b){
//     return find(a)==find(b);
// }
// void unite(int a, int b){
//     a = find(a);
//     b = find(b);
//     if(r[a]>=r[b]){
//         par[b] = a;
//         r[a]+=r[b];
//     }else{
//         par[a] = b;
//         r[b]+=r[a];
//     }
// }
map<int,vpl> mp;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        int s,n;
        cin>>s>>n;
        fr(i,0,n){
            int a,b,c;
            cin>>a>>b>>c;
            mp[b].push_back({a,c});
        }

        vvl we(s+1);

        for(auto it : mp){
            srt(it.second);
            reverse(all(it.second));
        }

        for(auto it : mp){
            int ma = s/it.first;
            for(auto el : it.second){
                while(el.second && ma){
                    we[it.first].push_back(el.first);
                    ma--;
                    el.second--;
                }
                if(ma==0) break;
            }
        }

        vvl dp(s+1,vl(s+1,0));
        // for(int i = 1;i<=s;i++){
        //     for(int j : we[i]) cout<<j<<" ";
        //     nl;
        // }


        for(int i=1;i<=s;i++){
            dp[i] = dp[i-1];
            ll cs=0;
            ll w = 0;
            for(ll j : we[i]){
                cs+=j;
                w+=i;
                for(int k = s;k>0;k--){
                    if(k-w<0) break;
                    dp[i][k] = max(dp[i][k],dp[i-1][k-w] + cs);
                }
            }
        }
        fr(i,1,s+1){
            fr(j,1,s+1) cout<<dp[i][j]<<" ";
            nl;
        }
        ll ans = 0;
        for(int i = 0;i<=s;i++){
            ans = max(ans,dp[s][i]);
        }
        cout<<ans;
    }
    return 0;
}

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