oj.uz

Submission #622311

# Submission time Handle Problem Language Result Execution time Memory
622311 2022-08-04T07:05:19 Z rrrr10000 Uplifting Excursion (BOI22_vault) C++14
5 / 100
 380 ms 235308 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);
    }
    auto sol=[&](vi v){
        ll mx=10000000/n;
        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;
    };
    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:63: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]
   63 |     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 211 ms 117776 KB Output is correct
2 Correct 120 ms 78592 KB Output is correct
3 Correct 211 ms 235308 KB Output is correct
4 Correct 143 ms 23684 KB Output is correct
5 Correct 93 ms 4996 KB Output is correct
6 Correct 96 ms 4996 KB Output is correct
7 Correct 81 ms 4976 KB Output is correct
8 Correct 93 ms 4992 KB Output is correct
9 Correct 113 ms 4976 KB Output is correct
10 Correct 69 ms 4988 KB Output is correct
11 Correct 74 ms 4996 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 117776 KB Output is correct
2 Correct 120 ms 78592 KB Output is correct
3 Correct 211 ms 235308 KB Output is correct
4 Correct 143 ms 23684 KB Output is correct
5 Correct 93 ms 4996 KB Output is correct
6 Correct 96 ms 4996 KB Output is correct
7 Correct 81 ms 4976 KB Output is correct
8 Correct 93 ms 4992 KB Output is correct
9 Correct 113 ms 4976 KB Output is correct
10 Correct 69 ms 4988 KB Output is correct
11 Correct 74 ms 4996 KB Output is correct
12 Correct 178 ms 117696 KB Output is correct
13 Correct 124 ms 78556 KB Output is correct
14 Correct 206 ms 235180 KB Output is correct
15 Correct 145 ms 23780 KB Output is correct
16 Correct 92 ms 4908 KB Output is correct
17 Correct 96 ms 4972 KB Output is correct
18 Correct 84 ms 4980 KB Output is correct
19 Correct 110 ms 4988 KB Output is correct
20 Correct 123 ms 4972 KB Output is correct
21 Correct 72 ms 5036 KB Output is correct
22 Correct 68 ms 4964 KB Output is correct
23 Correct 291 ms 2656 KB Output is correct
24 Correct 306 ms 2748 KB Output is correct
25 Correct 175 ms 2648 KB Output is correct
26 Incorrect 380 ms 2748 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 141 ms 23764 KB Output is correct
2 Correct 315 ms 8456 KB Output is correct
3 Correct 186 ms 8156 KB Output is correct
4 Incorrect 331 ms 8820 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 141 ms 23764 KB Output is correct
2 Correct 315 ms 8456 KB Output is correct
3 Correct 186 ms 8156 KB Output is correct
4 Incorrect 331 ms 8820 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 141 ms 23764 KB Output is correct
2 Correct 315 ms 8456 KB Output is correct
3 Correct 186 ms 8156 KB Output is correct
4 Incorrect 331 ms 8820 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 211 ms 117776 KB Output is correct
2 Correct 120 ms 78592 KB Output is correct
3 Correct 211 ms 235308 KB Output is correct
4 Correct 143 ms 23684 KB Output is correct
5 Correct 93 ms 4996 KB Output is correct
6 Correct 96 ms 4996 KB Output is correct
7 Correct 81 ms 4976 KB Output is correct
8 Correct 93 ms 4992 KB Output is correct
9 Correct 113 ms 4976 KB Output is correct
10 Correct 69 ms 4988 KB Output is correct
11 Correct 74 ms 4996 KB Output is correct
12 Correct 141 ms 23764 KB Output is correct
13 Correct 315 ms 8456 KB Output is correct
14 Correct 186 ms 8156 KB Output is correct
15 Incorrect 331 ms 8820 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 141 ms 23764 KB Output is correct
2 Correct 315 ms 8456 KB Output is correct
3 Correct 186 ms 8156 KB Output is correct
4 Incorrect 331 ms 8820 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 211 ms 117776 KB Output is correct
2 Correct 120 ms 78592 KB Output is correct
3 Correct 211 ms 235308 KB Output is correct
4 Correct 143 ms 23684 KB Output is correct
5 Correct 93 ms 4996 KB Output is correct
6 Correct 96 ms 4996 KB Output is correct
7 Correct 81 ms 4976 KB Output is correct
8 Correct 93 ms 4992 KB Output is correct
9 Correct 113 ms 4976 KB Output is correct
10 Correct 69 ms 4988 KB Output is correct
11 Correct 74 ms 4996 KB Output is correct
12 Correct 178 ms 117696 KB Output is correct
13 Correct 124 ms 78556 KB Output is correct
14 Correct 206 ms 235180 KB Output is correct
15 Correct 145 ms 23780 KB Output is correct
16 Correct 92 ms 4908 KB Output is correct
17 Correct 96 ms 4972 KB Output is correct
18 Correct 84 ms 4980 KB Output is correct
19 Correct 110 ms 4988 KB Output is correct
20 Correct 123 ms 4972 KB Output is correct
21 Correct 72 ms 5036 KB Output is correct
22 Correct 68 ms 4964 KB Output is correct
23 Correct 291 ms 2656 KB Output is correct
24 Correct 306 ms 2748 KB Output is correct
25 Correct 175 ms 2648 KB Output is correct
26 Incorrect 380 ms 2748 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 141 ms 23764 KB Output is correct
2 Correct 315 ms 8456 KB Output is correct
3 Correct 186 ms 8156 KB Output is correct
4 Incorrect 331 ms 8820 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 211 ms 117776 KB Output is correct
2 Correct 120 ms 78592 KB Output is correct
3 Correct 211 ms 235308 KB Output is correct
4 Correct 143 ms 23684 KB Output is correct
5 Correct 93 ms 4996 KB Output is correct
6 Correct 96 ms 4996 KB Output is correct
7 Correct 81 ms 4976 KB Output is correct
8 Correct 93 ms 4992 KB Output is correct
9 Correct 113 ms 4976 KB Output is correct
10 Correct 69 ms 4988 KB Output is correct
11 Correct 74 ms 4996 KB Output is correct
12 Correct 178 ms 117696 KB Output is correct
13 Correct 124 ms 78556 KB Output is correct
14 Correct 206 ms 235180 KB Output is correct
15 Correct 145 ms 23780 KB Output is correct
16 Correct 92 ms 4908 KB Output is correct
17 Correct 96 ms 4972 KB Output is correct
18 Correct 84 ms 4980 KB Output is correct
19 Correct 110 ms 4988 KB Output is correct
20 Correct 123 ms 4972 KB Output is correct
21 Correct 72 ms 5036 KB Output is correct
22 Correct 68 ms 4964 KB Output is correct
23 Correct 291 ms 2656 KB Output is correct
24 Correct 306 ms 2748 KB Output is correct
25 Correct 175 ms 2648 KB Output is correct
26 Incorrect 380 ms 2748 KB Output isn't correct
27 Halted 0 ms 0 KB -