oj.uz

Submission #710727

# Submission time Handle Problem Language Result Execution time Memory
710727 2023-03-15T17:14:55 Z Huseyn123 Knapsack (NOI18_knapsack) C++17
100 / 100
 70 ms 11120 KB 
#include <bits/stdc++.h>
#define MAX 200001
#define INF LLONG_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define gett(x,m) get<m>(x)
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define sorta(a,sz) sort(a,a+sz)
#define inputar(a,b){\
    for(int i=0;i<b;i++){\
        cin >> a[i];\
    }\
}
#define inputvec(a,b){\
    for(int i=0;i<b;i++){\
        ll num;\
        cin >> num;\
        a.pb(num);\
    }\
}
#define outputar(a,b){\
    for(int i=0;i<b;i++){\
        cout << a[i] << " ";\
    }\
    cout << "\n";\
}
#define outputvec(a){\
    for(auto x:a){\
        cout << x << " ";\
    }\
    cout << "\n";\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef double db;
typedef long double ldb;
inline void USACO(string filename){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}
ll n,q,t=1,m,n2,m2,k,cnt=0,a[MAX],b[MAX],d[MAX],cnte[MAX],x,y,z,x2,y2,z2,res1=0,cnt1,cnt2,cnt3;
ll c[501][501];
ll fact[MAX];
ll inv_fact[MAX];
//char c;
string str[MAX];
string s1,s2;
vector<tuple<ll,ll,ll>> v;
vector<pll> v1,v2,v3,v4;
const int mod = 998244353;
ll modmul(ll x,ll y,ll md){
    if(y==1){
        return x;
    }
    if(y%2){
        return (x+modmul(x,y-1,md))%md;
    }
    else{
        return (modmul((x+x)%md,y/2,md))%md;
    }
}
ll powmod(ll x,ll y,ll md){
    x%=md;
    if(x==0){
        return 0;
    }
    ll res=1;
    while(y){
        if(y%2==1){
            res*=x;
            res%=md;
        }
        x*=x;
        x%=md;
        y/=2;
    }
    return res;
}
ll pow2(ll x,ll y){
    if(x==0){
        return 0;
    }
    ll res=1;
    while(y>0){
        if(y%2==1){
            res*=x;
        }
        x*=x;
        y/=2;
    }
    return res;
}
ll inv(ll n,ll md){
    return powmod(n,md-2,md);
}
ll nCkm(ll n,ll k,ll md){
    if(n-k<0){
        return 0;
    }
    return fact[n]*inv_fact[k]%md*inv_fact[n-k]%md;
}
ll nCk(ll x,ll y){
    if(x<y){
        return 0;
    }
    ll res=1;
    if(y>x-y){
        for(int i=y+1;i<=x;i++){
            res*=i;
        }
        for(int i=2;i<=x-y;i++){
            res/=i;
        }
    }
    else{
        for(int i=x-y+1;i<=x;i++){
            res*=i;
        }
        for(int i=2;i<=y;i++){
            res/=i;
        }
    }
    return res;
}
ll countbits(ll x){
    ll cnt=0;
    while(x){
        cnt+=x&1;
        x>>=1;
    }
    return cnt;
}
ll gcd(ll x,ll y){
    if(y==0){
        return x;
    }
    return gcd(y,x%y);
}
ll lcm(ll x,ll y){
    return x*y/gcd(x,y);
}
bool alpha(char c1,char c2){
    ll h1,h2;
    if(c1>='a'){
        h1=c1-'a';
    }
    else{
        h1=c1-'A';
    }
    if(c2>='a'){
        h2=c2-'a';
    }
    else{
        h2=c2-'A';
    }
    if(h1==h2){
        return c1<c2;
    }
    else{
        return h1<h2;
    }
}
ll dx[4]={1,0,0,-1};
ll dy[4]={0,1,-1,0};
struct custom_hash {
   static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
struct segtree{
    int size;
    vector<ll> minimum;
    void build(vector<int> &a,int x,int lx,int rx){
        if(rx-lx==1){
            if(lx<(int)a.size()){
                minimum[x]=a[lx];
            }
            return;
        }
        int m=(lx+rx)/2;
        build(a,2*x+1,lx,m);
        build(a,2*x+2,m,rx);
        minimum[x]=min(minimum[2*x+1],minimum[2*x+2]);
    }
    void build(vector<int> &a){
        build(a,0,0,size);
    }
    void init(int n){
        size=1;
        while(size<n){
            size*=2;
        }
        minimum.assign(2*size,INF);
    }
    ll get_min(int l,int r,int x,int lx,int rx){
        if(lx>=r || rx<=l){
            return INF;
        }
        if(lx>=l && rx<=r){
            return minimum[x];
        }
        ll s1,s2;
        int m=(lx+rx)/2;
        s1=get_min(l,r,2*x+1,lx,m);
        s2=get_min(l,r,2*x+2,m,rx);
        return min(s1,s2);
    }
    ll get_min(int l,int r){
        return get_min(l,r,0,0,size);
    }
    void set(int i,int v,int x,int lx,int rx){
        if(rx-lx==1){
            minimum[x]=v;
            return;
        }
        int m=(lx+rx)/2;
        if(i<m){
            set(i,v,2*x+1,lx,m);
        }
        else{
            set(i,v,2*x+2,m,rx);
        }
        minimum[x]=min(minimum[2*x+1],minimum[2*x+2]);
    }
    void set(int i,int v){
        set(i,v,0,0,size);
    }
};
void solve(){
    cin >> m >> n;
    vector<vector<pll>> c(m+1);
    for(int i=0;i<n;i++){
        cin >> x >> y >> z;
        c[y].pb(mp(x,z));
    }
    ll dp[2][m+1];
    for(int i=0;i<=m;i++){
        dp[0][i]=-INF;
    }
    dp[0][0]=0;
    ll res=0;
    for(int i=1;i<=m;i++){
        int cur,prev;
        cur=i&1;
        prev=cur^1;
        for(int i=0;i<=m;i++){
            dp[cur][i]=dp[prev][i];
        }
        sortv(c[i]);
        reverse(all(c[i]));
        ll j=0;
        ll cnt=1;
        ll cnt2=1;
        ll sum=0;
        while(j<c[i].size() && cnt2*i<=m){
            sum+=c[i][j].ff;
            //cout << cnt2*i << " " << sum << "\n";
            for(int z=m;z>=0;z--){
                if(z>=cnt2*i && dp[prev][z-cnt2*i]!=-INF){
                    dp[cur][z]=max(dp[cur][z],dp[prev][z-cnt2*i]+sum);
                    res=max(res,dp[cur][z]);
                }
            }
            cnt2++;
            cnt++;
            if(cnt>c[i][j].ss){
                cnt-=c[i][j].ss;
                j++;
            }
        }
    }
    cout << res << "\n";
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //USACO("feast");
    //freopen("input.txt","r",stdin);
    //cin >> t;
    ll cnt1=1;
    while(t--){
        solve();
        cnt1++;
    }
}
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ifstream fin("template.in");
ofstream fout("template.out");
*/
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ifstream fin("template.in");
ofstream fout("template.out");
*/
/*
ll b[51][51];
b[0][0] = 1;
    for (int n = 1; n <= 50; ++n){
        b[n][0] = b[n][n] = 1;
        for (int k = 1; k < n; ++k)
            b[n][k] = b[n - 1][k - 1] + b[n - 1][k];
    }
*/

Compilation message

knapsack.cpp: In function 'void solve()':
knapsack.cpp:274:16: 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]
  274 |         while(j<c[i].size() && cnt2*i<=m){
      |               ~^~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6612 KB Output is correct
2 Correct 5 ms 6584 KB Output is correct
3 Correct 5 ms 6588 KB Output is correct
4 Correct 4 ms 6592 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6588 KB Output is correct
2 Correct 6 ms 6612 KB Output is correct
3 Correct 6 ms 6612 KB Output is correct
4 Correct 6 ms 6612 KB Output is correct
5 Correct 6 ms 6616 KB Output is correct
6 Correct 6 ms 6612 KB Output is correct
7 Correct 6 ms 6612 KB Output is correct
8 Correct 6 ms 6588 KB Output is correct
9 Correct 6 ms 6588 KB Output is correct
10 Correct 6 ms 6588 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6588 KB Output is correct
2 Correct 6 ms 6612 KB Output is correct
3 Correct 6 ms 6612 KB Output is correct
4 Correct 6 ms 6612 KB Output is correct
5 Correct 6 ms 6616 KB Output is correct
6 Correct 6 ms 6612 KB Output is correct
7 Correct 6 ms 6612 KB Output is correct
8 Correct 6 ms 6588 KB Output is correct
9 Correct 6 ms 6588 KB Output is correct
10 Correct 6 ms 6588 KB Output is correct
11 Correct 4 ms 6592 KB Output is correct
12 Correct 7 ms 6588 KB Output is correct
13 Correct 6 ms 6612 KB Output is correct
14 Correct 6 ms 6588 KB Output is correct
15 Correct 6 ms 6740 KB Output is correct
16 Correct 7 ms 6612 KB Output is correct
17 Correct 5 ms 6612 KB Output is correct
18 Correct 6 ms 6612 KB Output is correct
19 Correct 6 ms 6612 KB Output is correct
20 Correct 6 ms 6612 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6612 KB Output is correct
2 Correct 5 ms 6584 KB Output is correct
3 Correct 5 ms 6588 KB Output is correct
4 Correct 4 ms 6592 KB Output is correct
5 Correct 3 ms 6588 KB Output is correct
6 Correct 6 ms 6612 KB Output is correct
7 Correct 6 ms 6612 KB Output is correct
8 Correct 6 ms 6612 KB Output is correct
9 Correct 6 ms 6616 KB Output is correct
10 Correct 6 ms 6612 KB Output is correct
11 Correct 6 ms 6612 KB Output is correct
12 Correct 6 ms 6588 KB Output is correct
13 Correct 6 ms 6588 KB Output is correct
14 Correct 6 ms 6588 KB Output is correct
15 Correct 4 ms 6592 KB Output is correct
16 Correct 7 ms 6588 KB Output is correct
17 Correct 6 ms 6612 KB Output is correct
18 Correct 6 ms 6588 KB Output is correct
19 Correct 6 ms 6740 KB Output is correct
20 Correct 7 ms 6612 KB Output is correct
21 Correct 5 ms 6612 KB Output is correct
22 Correct 6 ms 6612 KB Output is correct
23 Correct 6 ms 6612 KB Output is correct
24 Correct 6 ms 6612 KB Output is correct
25 Correct 3 ms 6484 KB Output is correct
26 Correct 9 ms 6612 KB Output is correct
27 Correct 6 ms 6612 KB Output is correct
28 Correct 6 ms 6612 KB Output is correct
29 Correct 6 ms 6588 KB Output is correct
30 Correct 7 ms 6612 KB Output is correct
31 Correct 6 ms 6592 KB Output is correct
32 Correct 8 ms 6652 KB Output is correct
33 Correct 6 ms 6612 KB Output is correct
34 Correct 6 ms 6612 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6612 KB Output is correct
2 Correct 5 ms 6584 KB Output is correct
3 Correct 5 ms 6588 KB Output is correct
4 Correct 4 ms 6592 KB Output is correct
5 Correct 3 ms 6588 KB Output is correct
6 Correct 6 ms 6612 KB Output is correct
7 Correct 6 ms 6612 KB Output is correct
8 Correct 6 ms 6612 KB Output is correct
9 Correct 6 ms 6616 KB Output is correct
10 Correct 6 ms 6612 KB Output is correct
11 Correct 6 ms 6612 KB Output is correct
12 Correct 6 ms 6588 KB Output is correct
13 Correct 6 ms 6588 KB Output is correct
14 Correct 6 ms 6588 KB Output is correct
15 Correct 4 ms 6592 KB Output is correct
16 Correct 7 ms 6588 KB Output is correct
17 Correct 6 ms 6612 KB Output is correct
18 Correct 6 ms 6588 KB Output is correct
19 Correct 6 ms 6740 KB Output is correct
20 Correct 7 ms 6612 KB Output is correct
21 Correct 5 ms 6612 KB Output is correct
22 Correct 6 ms 6612 KB Output is correct
23 Correct 6 ms 6612 KB Output is correct
24 Correct 6 ms 6612 KB Output is correct
25 Correct 3 ms 6484 KB Output is correct
26 Correct 9 ms 6612 KB Output is correct
27 Correct 6 ms 6612 KB Output is correct
28 Correct 6 ms 6612 KB Output is correct
29 Correct 6 ms 6588 KB Output is correct
30 Correct 7 ms 6612 KB Output is correct
31 Correct 6 ms 6592 KB Output is correct
32 Correct 8 ms 6652 KB Output is correct
33 Correct 6 ms 6612 KB Output is correct
34 Correct 6 ms 6612 KB Output is correct
35 Correct 33 ms 9556 KB Output is correct
36 Correct 39 ms 9804 KB Output is correct
37 Correct 35 ms 9584 KB Output is correct
38 Correct 34 ms 10028 KB Output is correct
39 Correct 43 ms 10520 KB Output is correct
40 Correct 70 ms 11084 KB Output is correct
41 Correct 51 ms 10264 KB Output is correct
42 Correct 49 ms 10188 KB Output is correct
43 Correct 59 ms 10288 KB Output is correct
44 Correct 58 ms 10192 KB Output is correct
45 Correct 39 ms 11084 KB Output is correct
46 Correct 38 ms 10364 KB Output is correct
47 Correct 45 ms 11120 KB Output is correct
48 Correct 52 ms 10968 KB Output is correct
49 Correct 36 ms 10820 KB Output is correct
50 Correct 55 ms 10476 KB Output is correct