oj.uz

Submission #622335

# Submission time Handle Problem Language Result Execution time Memory
622335 2022-08-04T07:30:59 Z rrrr10000 Uplifting Excursion (BOI22_vault) C++14
5 / 100
 2094 ms 25880 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=1000000,mx2=125000;
    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>mx2){
        ll mi=min(b[i-1]-i*3,(sum-mx2)/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 34 ms 23808 KB Output is correct
2 Correct 50 ms 23792 KB Output is correct
3 Correct 25 ms 23772 KB Output is correct
4 Correct 127 ms 23772 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 777 ms 23752 KB Output is correct
7 Correct 794 ms 23880 KB Output is correct
8 Correct 805 ms 23884 KB Output is correct
9 Correct 799 ms 23776 KB Output is correct
10 Correct 811 ms 23884 KB Output is correct
11 Correct 729 ms 23776 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 23808 KB Output is correct
2 Correct 50 ms 23792 KB Output is correct
3 Correct 25 ms 23772 KB Output is correct
4 Correct 127 ms 23772 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 777 ms 23752 KB Output is correct
7 Correct 794 ms 23880 KB Output is correct
8 Correct 805 ms 23884 KB Output is correct
9 Correct 799 ms 23776 KB Output is correct
10 Correct 811 ms 23884 KB Output is correct
11 Correct 729 ms 23776 KB Output is correct
12 Correct 32 ms 23756 KB Output is correct
13 Correct 46 ms 23772 KB Output is correct
14 Correct 21 ms 23756 KB Output is correct
15 Correct 115 ms 23780 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 862 ms 23780 KB Output is correct
18 Correct 892 ms 23864 KB Output is correct
19 Correct 760 ms 23880 KB Output is correct
20 Correct 754 ms 23756 KB Output is correct
21 Correct 816 ms 23776 KB Output is correct
22 Correct 760 ms 23776 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 1912 ms 23788 KB Output is correct
25 Correct 1652 ms 23764 KB Output is correct
26 Incorrect 2094 ms 23776 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 23736 KB Output is correct
2 Correct 1010 ms 24492 KB Output is correct
3 Correct 697 ms 23860 KB Output is correct
4 Incorrect 1000 ms 25880 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 113 ms 23736 KB Output is correct
2 Correct 1010 ms 24492 KB Output is correct
3 Correct 697 ms 23860 KB Output is correct
4 Incorrect 1000 ms 25880 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 113 ms 23736 KB Output is correct
2 Correct 1010 ms 24492 KB Output is correct
3 Correct 697 ms 23860 KB Output is correct
4 Incorrect 1000 ms 25880 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 34 ms 23808 KB Output is correct
2 Correct 50 ms 23792 KB Output is correct
3 Correct 25 ms 23772 KB Output is correct
4 Correct 127 ms 23772 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 777 ms 23752 KB Output is correct
7 Correct 794 ms 23880 KB Output is correct
8 Correct 805 ms 23884 KB Output is correct
9 Correct 799 ms 23776 KB Output is correct
10 Correct 811 ms 23884 KB Output is correct
11 Correct 729 ms 23776 KB Output is correct
12 Correct 113 ms 23736 KB Output is correct
13 Correct 1010 ms 24492 KB Output is correct
14 Correct 697 ms 23860 KB Output is correct
15 Incorrect 1000 ms 25880 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 113 ms 23736 KB Output is correct
2 Correct 1010 ms 24492 KB Output is correct
3 Correct 697 ms 23860 KB Output is correct
4 Incorrect 1000 ms 25880 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 34 ms 23808 KB Output is correct
2 Correct 50 ms 23792 KB Output is correct
3 Correct 25 ms 23772 KB Output is correct
4 Correct 127 ms 23772 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 777 ms 23752 KB Output is correct
7 Correct 794 ms 23880 KB Output is correct
8 Correct 805 ms 23884 KB Output is correct
9 Correct 799 ms 23776 KB Output is correct
10 Correct 811 ms 23884 KB Output is correct
11 Correct 729 ms 23776 KB Output is correct
12 Correct 32 ms 23756 KB Output is correct
13 Correct 46 ms 23772 KB Output is correct
14 Correct 21 ms 23756 KB Output is correct
15 Correct 115 ms 23780 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 862 ms 23780 KB Output is correct
18 Correct 892 ms 23864 KB Output is correct
19 Correct 760 ms 23880 KB Output is correct
20 Correct 754 ms 23756 KB Output is correct
21 Correct 816 ms 23776 KB Output is correct
22 Correct 760 ms 23776 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 1912 ms 23788 KB Output is correct
25 Correct 1652 ms 23764 KB Output is correct
26 Incorrect 2094 ms 23776 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 23736 KB Output is correct
2 Correct 1010 ms 24492 KB Output is correct
3 Correct 697 ms 23860 KB Output is correct
4 Incorrect 1000 ms 25880 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 34 ms 23808 KB Output is correct
2 Correct 50 ms 23792 KB Output is correct
3 Correct 25 ms 23772 KB Output is correct
4 Correct 127 ms 23772 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 777 ms 23752 KB Output is correct
7 Correct 794 ms 23880 KB Output is correct
8 Correct 805 ms 23884 KB Output is correct
9 Correct 799 ms 23776 KB Output is correct
10 Correct 811 ms 23884 KB Output is correct
11 Correct 729 ms 23776 KB Output is correct
12 Correct 32 ms 23756 KB Output is correct
13 Correct 46 ms 23772 KB Output is correct
14 Correct 21 ms 23756 KB Output is correct
15 Correct 115 ms 23780 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 862 ms 23780 KB Output is correct
18 Correct 892 ms 23864 KB Output is correct
19 Correct 760 ms 23880 KB Output is correct
20 Correct 754 ms 23756 KB Output is correct
21 Correct 816 ms 23776 KB Output is correct
22 Correct 760 ms 23776 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 1912 ms 23788 KB Output is correct
25 Correct 1652 ms 23764 KB Output is correct
26 Incorrect 2094 ms 23776 KB Output isn't correct
27 Halted 0 ms 0 KB -