Submission #1070853

#TimeUsernameProblemLanguageResultExecution timeMemory
1070853AdamGSUplifting Excursion (BOI22_vault)C++17
5 / 100
722 ms9500 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const ll INF=1e18+7; const int LIM=3e5+7; ll dp[LIM], dp2[LIM], A[LIM], B[LIM]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); ll n, m; cin >> n >> m; rep(i, n) cin >> A[n-i]; rep(i, n+1) cin >> B[i]; ll ans=0; rep(i, n+1) ans+=B[i]; rep(i, n+1) ans+=A[i]; rep(i, n+1) m+=A[i]*(ll)i; rep(i, n+1) m-=B[i]*(ll)i; if(m<0) { m*=-1; rep(i, n+1) swap(A[i], B[i]); } rep(i, LIM) dp[i]=INF; dp[0]=0; for(ll i=n; i; --i) { if(m>=LIM/2) { ll p=m-LIM/2; p=(p+i-1)/i; p=min(p, A[i]); A[i]-=p; dp[0]+=p; m-=p*i; } } if(m>=LIM) { cout << "impossible\n"; return 0; } rep(xd, 2) { for(ll i=1; i<=n; ++i) { vector<ll>V[i], l(i); rep(j, LIM) { ll p=j%i; while(l[p]<V[p].size() && (j-V[p][l[p]])/i>A[i]) ++l[p]; while(V[p].size()>0 && dp[j]<=dp[V[p].back()]+(j-V[p].back())/i) { V[p].pop_back(); l[p]=min(l[p], (ll)V[p].size()); } dp2[j]=dp[j]; if(l[p]<V[p].size()) { dp2[j]=min(dp2[j], dp[V[p][l[p]]]+(j-V[p][l[p]])/i); } V[p].pb(j); } rep(j, LIM) dp[j]=dp2[j]; } rep(i, LIM/2) swap(dp[i], dp[LIM-i]); rep(i, n) swap(A[i], B[i]); } if(dp[m]==INF) { cout << "impossible\n"; return 0; } cout << ans-dp[m] << '\n'; }

Compilation message (stderr)

vault.cpp: In function 'int main()':
vault.cpp:48:19: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         while(l[p]<V[p].size() && (j-V[p][l[p]])/i>A[i]) ++l[p];
vault.cpp:54:16: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         if(l[p]<V[p].size()) {
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...