Submission #1070979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070979		AdamGS	Uplifting Excursion (BOI22_vault)	C++17	90 / 100	5036 ms	35776 KiB

vault

    #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 ll LIM=1e6+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;
    	int ile=1;
    	for(ll i=n; i; --i) {
    		if(m>=LIM/2) {
    			ll p=m-LIM/2;
    			p=(p+i-1)/i;
    			p=min(p, max(A[i]-300/ile, 0ll));
    			A[i]-=p;
    			if(A[i]) ++ile;
    			dp[0]+=p;
    			m-=p*i;	
    		}
    	}
    	if(m>=LIM) {
    		cout << "impossible\n";
    		return 0;
    	}
    	rep(xd, 2) {
    		for(ll i=1; i<=n; ++i) if(A[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-1]);
    		rep(i, n+1) 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:50: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]
   50 |         while(l[p]<V[p].size() && (j-V[p][l[p]])/i>A[i]) ++l[p];
vault.cpp:56: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]
   56 |         if(l[p]<V[p].size()) {

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3-1: 10 / 10
• Subtask 3-2: 10 / 10
• Subtask 4-1: 10 / 10
• Subtask 4-2: 10 / 10
• Subtask 5-1: 10 / 10
• Subtask 5-2: 10 / 10
• Subtask 6-1: 10 / 10
• Subtask 6-2: 0 / 10