Submission #584310

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
584310	2022-06-27T07:49:30 Z	alirezasamimi100	Uplifting Excursion (BOI22_vault)	C++17	20 / 100	1357 ms	8056 KB

vault

/*#pragma GCC optimize("Ofast,unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")*/
/*#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")*/
#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
using ld=long double;
using pll=pair<ll,ll>;
using pii=pair<int,int>;
using point=complex<double>;
#define F first
#define S second
//#define X real()
//#define Y imag()
#define pb push_back
#define mp make_pair
#define lc v<<1
#define rc v<<1|1
#define fast_io ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#define kill(x) cout << x << '\n';exit(0)
#define killshayan kill("done!")
#define killmashtali kill("Hello, World!")
const int N=2e5+10,LN=20,M=1e6+10,SQ=700,BS=737,inf=1.05e9,NSQ=N/SQ+3;
const ll INF=1e18;
const double pi=acos(-1);
const ld ep=1e-7;
const int MH=1000696969,MD=998244353,MOD=1000000007;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#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,greater<pii>, rb_tree_tag,tree_order_statistics_node_update>
ll pow(ll x, ll y, ll mod){
    ll ans=1;
    while (y != 0) {
        if (y & 1) ans = ans * x % mod;
        y >>= 1;
        x = x * x % mod;
    }
    return ans;
}
ll n,l,*dp,ns,ps;
vector<pll> neg,pos;
int main(){
    fast_io;
    cin >> n >> l;
    for(ll i=-n; i<0; i++){
        ll x,t=1;
        cin >> x;
        ns+=x*i;
        while(t<x){
            neg.pb({i*t,t});
            x-=t;
            t*=2;
        }
        if(x) neg.pb({i*x,x});
    }
    for(ll i=0; i<=n; i++){
        ll x,t=1;
        cin >> x;
        ps+=x*i;
        while(t<x){
            pos.pb({i*t,t});
            x-=t;
            t*=2;
        }
        if(x) pos.pb({i*x,x});
    }
    if(l<ns || l>ps){
        cout << "impossible\n";
        return 0;
    }
    dp=new ll[abs(ns)+ps+1]+abs(ns);
    for(ll i=ns; i<=ps; i++) dp[i]=-INF;
    dp[0]=0;
    for(auto [x,y] : neg){
        for(ll i=ns; i<=ps; i++){
            if(i-x<=ps) dp[i]=max(dp[i],dp[i-x]+y);
        }
    }
    for(auto [x,y] : pos){
        for(ll i=ps; i>=ns; i--){
            if(i-x>=ns) dp[i]=max(dp[i],dp[i-x]+y);
        }
    }
    if(dp[l]<0) cout << "impossible\n";
    else cout << dp[l] << '\n';
    return 0;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	228 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	40 ms	852 KB	Output is correct
7	Correct	6 ms	468 KB	Output is correct
8	Correct	31 ms	724 KB	Output is correct
9	Correct	65 ms	1284 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct

Subtask #2
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	228 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	40 ms	852 KB	Output is correct
7	Correct	6 ms	468 KB	Output is correct
8	Correct	31 ms	724 KB	Output is correct
9	Correct	65 ms	1284 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	35 ms	972 KB	Output is correct
18	Correct	7 ms	468 KB	Output is correct
19	Correct	36 ms	724 KB	Output is correct
20	Correct	83 ms	1288 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	553 ms	4328 KB	Output is correct
25	Correct	103 ms	1948 KB	Output is correct
26	Correct	1357 ms	8056 KB	Output is correct
27	Correct	1356 ms	8036 KB	Output is correct
28	Correct	1 ms	468 KB	Output is correct
29	Correct	1 ms	468 KB	Output is correct

Subtask #3-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Runtime error	3 ms	596 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #3-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Runtime error	3 ms	596 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #4-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Runtime error	3 ms	596 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #4-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	228 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	40 ms	852 KB	Output is correct
7	Correct	6 ms	468 KB	Output is correct
8	Correct	31 ms	724 KB	Output is correct
9	Correct	65 ms	1284 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Runtime error	3 ms	596 KB	Execution killed with signal 6
14	Halted	0 ms	0 KB	-

Subtask #5-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Runtime error	3 ms	596 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #5-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	228 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	40 ms	852 KB	Output is correct
7	Correct	6 ms	468 KB	Output is correct
8	Correct	31 ms	724 KB	Output is correct
9	Correct	65 ms	1284 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	35 ms	972 KB	Output is correct
18	Correct	7 ms	468 KB	Output is correct
19	Correct	36 ms	724 KB	Output is correct
20	Correct	83 ms	1288 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	553 ms	4328 KB	Output is correct
25	Correct	103 ms	1948 KB	Output is correct
26	Correct	1357 ms	8056 KB	Output is correct
27	Correct	1356 ms	8036 KB	Output is correct
28	Correct	1 ms	468 KB	Output is correct
29	Correct	1 ms	468 KB	Output is correct
30	Correct	1 ms	212 KB	Output is correct
31	Runtime error	3 ms	596 KB	Execution killed with signal 6
32	Halted	0 ms	0 KB	-

Subtask #6-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Runtime error	3 ms	596 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #6-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	228 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	40 ms	852 KB	Output is correct
7	Correct	6 ms	468 KB	Output is correct
8	Correct	31 ms	724 KB	Output is correct
9	Correct	65 ms	1284 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	35 ms	972 KB	Output is correct
18	Correct	7 ms	468 KB	Output is correct
19	Correct	36 ms	724 KB	Output is correct
20	Correct	83 ms	1288 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	553 ms	4328 KB	Output is correct
25	Correct	103 ms	1948 KB	Output is correct
26	Correct	1357 ms	8056 KB	Output is correct
27	Correct	1356 ms	8036 KB	Output is correct
28	Correct	1 ms	468 KB	Output is correct
29	Correct	1 ms	468 KB	Output is correct
30	Correct	1 ms	212 KB	Output is correct
31	Runtime error	3 ms	596 KB	Execution killed with signal 6
32	Halted	0 ms	0 KB	-

Submission #584310

Compilation message