oj.uz

Submission #905433

# Submission time Handle Problem Language Result Execution time Memory
905433 2024-01-13T02:42:32 Z Shifted777 Knapsack (NOI18_knapsack) C++17
73 / 100
 1000 ms 600 KB 
#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using ind_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T> using ind_ms=tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define sz(x) (int)(x).size()
#define sq(x) (x)*(x)
#define sqmod(x) (x)*(x)%MOD
#define all(x) x.begin(),x.end()
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
#define addmod(x,y) x=(x+y)%MOD
#define submod(x,y) x=((x-y)%MOD+MOD)%MOD
 
#define ll long long
#define ld long double
#define pii pair<int,int>
#define vpii vector<pii>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define vi vector<int>
#define vll vector<ll>
#define pld pair<ld,ld>
#define vld vector<ld>
#define vchr vector<char>
 
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define pcnt __builtin_popcount
#define clz __builtin_clz
 
mt19937_64 rv(chrono::steady_clock::now().time_since_epoch().count());
ll rng(ll l,ll r){ return (ll)uniform_int_distribution<ll>(l,r)(rv); }
 
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 r=chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x+r);
    }
};

int MOD=1e9+7;
int MOD2=998244353;

const ll INF=1e18;
const double PI=4*atan(1); 
ld degRad(ld a){ return PI/180*a; }
ld radDeg(ld a){ return 180/PI*a; }
 
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const char dc[4]={'R','D','L','U'};

const ld ERR=1e-12;
bool isEqual(ld a,ld b){ return abs(a-b)<=ERR; }
 
ll p2(int b){ return (1ll<<b); }
int l2(int x){ return 31-clz(x); }
int l2(ll x){ return 63-clz(x); }

ll mul(ll a,ll b){ return (__int128)a*b%MOD; } 
ll exp(ll b,ll e){ return (e==0)?(1ll):(exp(b*b,e/2)*((e%2)?(b):(1ll))); }
ll mexp(ll b,ll e){ return (e==0)?(1ll):(mexp(b*b%MOD,e/2)*((e%2)?(b):(1ll))%MOD)%MOD; }
ll inv(ll b) { return mexp(b,MOD-2); }
 
const int maxnck=5005;
ll fac[maxnck+1],ifac[maxnck+1];
//ll nck(ll a,ll b){ return fac[a]*ifac[b]%MOD*ifac[a-b]%MOD; }
ll nck(ll a,ll b){ return fac[a]*inv(fac[b])%MOD*inv(fac[a-b])%MOD; }

void factorial(bool inverse=false){
    fac[0]=1;ifac[0]=1;
    for(int i=1;i<=maxnck;++i){
        fac[i]=fac[i-1]*i%MOD;
        if(inverse)ifac[i]=inv(fac[i]);
    }
}

const int maxspf=1e6;
int spf[maxspf+1];
void sieve(){
    fill(spf,spf+maxspf+1,0);
    for(int i=2;i<=maxspf;++i){
        if(!spf[i])for(int j=i*2;j<=maxspf;j+=i)spf[j]=i;
    }
}

vll divisors(ll n){
    vll v;
    for(ll d=1;d*d<=n;++d){
        if(n%d==0){
            v.pb(d);
            if(d*d!=n)v.pb(n/d);
        }
    }
    return v;
}

template<typename T> struct SegTree{
    T DEF;
    vector<T> v;int len;
    SegTree(int n,T def=0) : len(n),v(n*2,def),DEF(def) {}
    T oper(T a,T b){
        return a+b;
    }
    void edit(int ind,T val){
        ind+=len;v[ind]=val;
        while(ind>1){
            v[ind/2]=oper(v[ind],v[ind^1]);
            ind/=2;
        }
    }
    T query(int l,int r){ // [l,r)
        T ans=DEF;l+=len;r+=len;
        while(l<r){
            if(l%2)ans=oper(ans,v[l++]);
            if(r%2)ans=oper(ans,v[--r]);
            l/=2;r/=2;
        }
        return ans;
    }
};

struct DSU{
    vector<int> p,c;
    DSU(int n) : c(n,1),p(n){ for(int i=0;i<n;++i)p[i]=i; }
    int get(int v){ return v==p[v] ? v : p[v]=get(p[v]); }
    int size(int v){ return c[get(v)]; }
    bool same(int x,int y){ return get(x)==get(y); }
    bool unite(int x,int y){
        x=get(x);y=get(y);if(x==y)return 0;
        if(c[x]<c[y])swap(x,y);
        p[y]=x;c[x]+=c[y];return 1;
    }
};

const int N=2e5+5;

void solve(int tc){
    ll s,n;cin>>s>>n;
    vll dp(s+1,0);
    for(int i=0;i<n;++i){
        ll v,w,k;cin>>v>>w>>k;
        chmin(k,s);
        ll f=1;
        while(1){
            for(int j=s-f*w;j>=0;--j){
                chmax(dp[j+f*w],dp[j]+f*v);
            }
            k-=f;
            f*=2;
            if(k-f<=0){
                f=k;
                for(int j=s-f*w;j>=0;--j){
                    chmax(dp[j+f*w],dp[j]+f*v);
                }
                break;
            }
            if(w*f>s)break;
        }
    }
    ll mx=0;
    for(auto x:dp)chmax(mx,x);
    //for(auto x:dp)cout<<x<<' ';cout<<'\n';
    cout<<mx<<'\n';
}

void setio(string s=""){
    #ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if(sz(s)){
        freopen((s+".in").c_str(),"r",stdin);
        freopen((s+".out").c_str(),"w",stdout);
    }
    #endif
    // return;
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("err.txt","w",stderr);
    freopen("out.txt","w",stdout);
    #endif
}
 
int32_t main(){
    setio();
    // factorial();
    // sieve();
 
    int t=1;
    // cin>>t;
    for(int i=0;i<t;++i)solve(i);
 
    cerr<<"Time : "<<(double)clock()/CLOCKS_PER_SEC<<"s"<<endl;
    return 0;
}

Compilation message

knapsack.cpp: In constructor 'DSU::DSU(int)':
knapsack.cpp:140:19: warning: 'DSU::c' will be initialized after [-Wreorder]
  140 |     vector<int> p,c;
      |                   ^
knapsack.cpp:140:17: warning:   'std::vector<int> DSU::p' [-Wreorder]
  140 |     vector<int> p,c;
      |                 ^
knapsack.cpp:141:5: warning:   when initialized here [-Wreorder]
  141 |     DSU(int n) : c(n,1),p(n){ for(int i=0;i<n;++i)p[i]=i; }
      |     ^~~
knapsack.cpp: In function 'void setio(std::string)':
knapsack.cpp:188:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |         freopen((s+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:189:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  189 |         freopen((s+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 3 ms 348 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 2 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 2 ms 344 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 3 ms 348 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 2 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 2 ms 344 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 4 ms 348 KB Output is correct
27 Correct 2 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 2 ms 344 KB Output is correct
34 Correct 1 ms 348 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 2 ms 344 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 3 ms 348 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 2 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 2 ms 344 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 4 ms 348 KB Output is correct
27 Correct 2 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 2 ms 344 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 17 ms 460 KB Output is correct
36 Execution timed out 1062 ms 348 KB Time limit exceeded
37 Halted 0 ms 0 KB -