oj.uz

Submission #622325

# Submission time Handle Problem Language Result Execution time Memory
622325 2022-08-04T07:17:18 Z rrrr10000 Uplifting Excursion (BOI22_vault) C++14
5 / 100
 5000 ms 76940 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pb emplace_back
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
const ll inf=1001001001001001001;

int main(){
    ll n,K;cin>>n>>K;
    ll tot=0,sum=0;
    vi a(n),b(n);
    rep(i,n)cin>>a[i];
    cin>>tot;
    rep(i,n)cin>>b[i];
    reverse(all(a));
    rep(i,n)sum-=a[i]*(i+1);
    rep(i,n)sum+=b[i]*(i+1);
    rep(i,n)tot+=a[i];
    rep(i,n)tot+=b[i];
    sum-=K;
    if(sum<0){
        sum*=-1;swap(a,b);
    }
    ll mx=3000000;
    auto sol=[&](vi v){
        vi dp(mx+1,inf);dp[0]=0;
        REP(i,1,v.size()+1){
            vi ndp=dp;
            rep(j,i){
                deque<ll> deq;
                for(ll k=j;k<=mx;k+=i){
                    if(dp[k]!=inf){
                        while(deq.size()&&dp[deq.back()]-deq.back()/i>=dp[k]-k/i)deq.pop_back();
                        deq.pb(k);
                    }
                    while(deq.size()&&deq.front()<k-i*v[i-1])deq.pop_front();
                    if(deq.size())chmin(ndp[k],dp[deq.front()]+(k-deq.front())/i);
                }
            }
            dp=ndp;
        }
        return dp;
    };
    for(int i=n;i>0;i--)if(sum>=mx/10){
        ll mi=min(b[i-1]-i*3,(sum-mx/10)/i+1);
        chmax(mi,0ll);
        sum-=mi*i;
        b[i-1]-=mi;
    }
    if(sum>mx){
        out("impossible");
        return 0;
    }
    vi dpa=sol(a);
    vi dpb=sol(b);
    ll ans=inf;
    rep(i,dpa.size())if(i+sum<dpb.size())chmin(ans,dpa[i]+dpb[i+sum]);
    if(ans==inf)out("impossible");
    else out(tot-ans);
}

Compilation message

vault.cpp: In function 'int main()':
vault.cpp:73:30: 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]
   73 |     rep(i,dpa.size())if(i+sum<dpb.size())chmin(ans,dpa[i]+dpb[i+sum]);
      |                         ~~~~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 70736 KB Output is correct
2 Correct 112 ms 70740 KB Output is correct
3 Correct 69 ms 70704 KB Output is correct
4 Correct 346 ms 70748 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2995 ms 70816 KB Output is correct
7 Correct 2760 ms 70684 KB Output is correct
8 Correct 2853 ms 70688 KB Output is correct
9 Correct 2783 ms 70684 KB Output is correct
10 Correct 2862 ms 70740 KB Output is correct
11 Correct 2891 ms 70860 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 70736 KB Output is correct
2 Correct 112 ms 70740 KB Output is correct
3 Correct 69 ms 70704 KB Output is correct
4 Correct 346 ms 70748 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2995 ms 70816 KB Output is correct
7 Correct 2760 ms 70684 KB Output is correct
8 Correct 2853 ms 70688 KB Output is correct
9 Correct 2783 ms 70684 KB Output is correct
10 Correct 2862 ms 70740 KB Output is correct
11 Correct 2891 ms 70860 KB Output is correct
12 Correct 91 ms 70632 KB Output is correct
13 Correct 123 ms 70740 KB Output is correct
14 Correct 75 ms 70740 KB Output is correct
15 Correct 357 ms 70740 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 2805 ms 70744 KB Output is correct
18 Correct 2968 ms 70736 KB Output is correct
19 Correct 3001 ms 70812 KB Output is correct
20 Correct 2955 ms 70744 KB Output is correct
21 Correct 2927 ms 70680 KB Output is correct
22 Correct 2921 ms 70744 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Execution timed out 5089 ms 70680 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 70744 KB Output is correct
2 Correct 3499 ms 72728 KB Output is correct
3 Correct 2362 ms 71192 KB Output is correct
4 Incorrect 3285 ms 76940 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 70744 KB Output is correct
2 Correct 3499 ms 72728 KB Output is correct
3 Correct 2362 ms 71192 KB Output is correct
4 Incorrect 3285 ms 76940 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 70744 KB Output is correct
2 Correct 3499 ms 72728 KB Output is correct
3 Correct 2362 ms 71192 KB Output is correct
4 Incorrect 3285 ms 76940 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 70736 KB Output is correct
2 Correct 112 ms 70740 KB Output is correct
3 Correct 69 ms 70704 KB Output is correct
4 Correct 346 ms 70748 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2995 ms 70816 KB Output is correct
7 Correct 2760 ms 70684 KB Output is correct
8 Correct 2853 ms 70688 KB Output is correct
9 Correct 2783 ms 70684 KB Output is correct
10 Correct 2862 ms 70740 KB Output is correct
11 Correct 2891 ms 70860 KB Output is correct
12 Correct 353 ms 70744 KB Output is correct
13 Correct 3499 ms 72728 KB Output is correct
14 Correct 2362 ms 71192 KB Output is correct
15 Incorrect 3285 ms 76940 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 70744 KB Output is correct
2 Correct 3499 ms 72728 KB Output is correct
3 Correct 2362 ms 71192 KB Output is correct
4 Incorrect 3285 ms 76940 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 70736 KB Output is correct
2 Correct 112 ms 70740 KB Output is correct
3 Correct 69 ms 70704 KB Output is correct
4 Correct 346 ms 70748 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2995 ms 70816 KB Output is correct
7 Correct 2760 ms 70684 KB Output is correct
8 Correct 2853 ms 70688 KB Output is correct
9 Correct 2783 ms 70684 KB Output is correct
10 Correct 2862 ms 70740 KB Output is correct
11 Correct 2891 ms 70860 KB Output is correct
12 Correct 91 ms 70632 KB Output is correct
13 Correct 123 ms 70740 KB Output is correct
14 Correct 75 ms 70740 KB Output is correct
15 Correct 357 ms 70740 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 2805 ms 70744 KB Output is correct
18 Correct 2968 ms 70736 KB Output is correct
19 Correct 3001 ms 70812 KB Output is correct
20 Correct 2955 ms 70744 KB Output is correct
21 Correct 2927 ms 70680 KB Output is correct
22 Correct 2921 ms 70744 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Execution timed out 5089 ms 70680 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 70744 KB Output is correct
2 Correct 3499 ms 72728 KB Output is correct
3 Correct 2362 ms 71192 KB Output is correct
4 Incorrect 3285 ms 76940 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 70736 KB Output is correct
2 Correct 112 ms 70740 KB Output is correct
3 Correct 69 ms 70704 KB Output is correct
4 Correct 346 ms 70748 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2995 ms 70816 KB Output is correct
7 Correct 2760 ms 70684 KB Output is correct
8 Correct 2853 ms 70688 KB Output is correct
9 Correct 2783 ms 70684 KB Output is correct
10 Correct 2862 ms 70740 KB Output is correct
11 Correct 2891 ms 70860 KB Output is correct
12 Correct 91 ms 70632 KB Output is correct
13 Correct 123 ms 70740 KB Output is correct
14 Correct 75 ms 70740 KB Output is correct
15 Correct 357 ms 70740 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 2805 ms 70744 KB Output is correct
18 Correct 2968 ms 70736 KB Output is correct
19 Correct 3001 ms 70812 KB Output is correct
20 Correct 2955 ms 70744 KB Output is correct
21 Correct 2927 ms 70680 KB Output is correct
22 Correct 2921 ms 70744 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Execution timed out 5089 ms 70680 KB Time limit exceeded
25 Halted 0 ms 0 KB -