oj.uz

Submission #1070845

# Submission time Handle Problem Language Result Execution time Memory
1070845 2024-08-22T19:33:43 Z AdamGS Uplifting Excursion (BOI22_vault) C++17
0 / 100
 102 ms 6812 KB 
#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=1e5+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;	
		}
	}
	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

vault.cpp: In function 'int main()':
vault.cpp:44:15: 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]
   44 |     while(l[p]<V[p].size() && (j-V[p][l[p]])/i>A[i]) ++l[p];
vault.cpp:50:12: 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 |     if(l[p]<V[p].size()) {

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3164 KB Output is correct
2 Correct 6 ms 3164 KB Output is correct
3 Correct 3 ms 3164 KB Output is correct
4 Correct 22 ms 3420 KB Output is correct
5 Runtime error 102 ms 6812 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3164 KB Output is correct
2 Correct 6 ms 3164 KB Output is correct
3 Correct 3 ms 3164 KB Output is correct
4 Correct 22 ms 3420 KB Output is correct
5 Runtime error 102 ms 6812 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3392 KB Output is correct
2 Correct 64 ms 3932 KB Output is correct
3 Incorrect 62 ms 3920 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3392 KB Output is correct
2 Correct 64 ms 3932 KB Output is correct
3 Incorrect 62 ms 3920 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3392 KB Output is correct
2 Correct 64 ms 3932 KB Output is correct
3 Incorrect 62 ms 3920 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3164 KB Output is correct
2 Correct 6 ms 3164 KB Output is correct
3 Correct 3 ms 3164 KB Output is correct
4 Correct 22 ms 3420 KB Output is correct
5 Runtime error 102 ms 6812 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3392 KB Output is correct
2 Correct 64 ms 3932 KB Output is correct
3 Incorrect 62 ms 3920 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3164 KB Output is correct
2 Correct 6 ms 3164 KB Output is correct
3 Correct 3 ms 3164 KB Output is correct
4 Correct 22 ms 3420 KB Output is correct
5 Runtime error 102 ms 6812 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3392 KB Output is correct
2 Correct 64 ms 3932 KB Output is correct
3 Incorrect 62 ms 3920 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3164 KB Output is correct
2 Correct 6 ms 3164 KB Output is correct
3 Correct 3 ms 3164 KB Output is correct
4 Correct 22 ms 3420 KB Output is correct
5 Runtime error 102 ms 6812 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -