oj.uz

Submission #1070850

# Submission time Handle Problem Language Result Execution time Memory
1070850 2024-08-22T19:41:46 Z AdamGS Uplifting Excursion (BOI22_vault) C++17
0 / 100
 116 ms 3928 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;	
		}
	}
	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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3164 KB Output is correct
2 Correct 7 ms 3408 KB Output is correct
3 Correct 3 ms 3160 KB Output is correct
4 Correct 22 ms 3160 KB Output is correct
5 Correct 1 ms 3164 KB Output is correct
6 Correct 113 ms 3632 KB Output is correct
7 Correct 109 ms 3512 KB Output is correct
8 Correct 111 ms 3616 KB Output is correct
9 Incorrect 116 ms 3816 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3164 KB Output is correct
2 Correct 7 ms 3408 KB Output is correct
3 Correct 3 ms 3160 KB Output is correct
4 Correct 22 ms 3160 KB Output is correct
5 Correct 1 ms 3164 KB Output is correct
6 Correct 113 ms 3632 KB Output is correct
7 Correct 109 ms 3512 KB Output is correct
8 Correct 111 ms 3616 KB Output is correct
9 Incorrect 116 ms 3816 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3412 KB Output is correct
2 Correct 63 ms 3928 KB Output is correct
3 Incorrect 58 ms 3916 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 22 ms 3412 KB Output is correct
2 Correct 63 ms 3928 KB Output is correct
3 Incorrect 58 ms 3916 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 22 ms 3412 KB Output is correct
2 Correct 63 ms 3928 KB Output is correct
3 Incorrect 58 ms 3916 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 6 ms 3164 KB Output is correct
2 Correct 7 ms 3408 KB Output is correct
3 Correct 3 ms 3160 KB Output is correct
4 Correct 22 ms 3160 KB Output is correct
5 Correct 1 ms 3164 KB Output is correct
6 Correct 113 ms 3632 KB Output is correct
7 Correct 109 ms 3512 KB Output is correct
8 Correct 111 ms 3616 KB Output is correct
9 Incorrect 116 ms 3816 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3412 KB Output is correct
2 Correct 63 ms 3928 KB Output is correct
3 Incorrect 58 ms 3916 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 6 ms 3164 KB Output is correct
2 Correct 7 ms 3408 KB Output is correct
3 Correct 3 ms 3160 KB Output is correct
4 Correct 22 ms 3160 KB Output is correct
5 Correct 1 ms 3164 KB Output is correct
6 Correct 113 ms 3632 KB Output is correct
7 Correct 109 ms 3512 KB Output is correct
8 Correct 111 ms 3616 KB Output is correct
9 Incorrect 116 ms 3816 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3412 KB Output is correct
2 Correct 63 ms 3928 KB Output is correct
3 Incorrect 58 ms 3916 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 6 ms 3164 KB Output is correct
2 Correct 7 ms 3408 KB Output is correct
3 Correct 3 ms 3160 KB Output is correct
4 Correct 22 ms 3160 KB Output is correct
5 Correct 1 ms 3164 KB Output is correct
6 Correct 113 ms 3632 KB Output is correct
7 Correct 109 ms 3512 KB Output is correct
8 Correct 111 ms 3616 KB Output is correct
9 Incorrect 116 ms 3816 KB Output isn't correct
10 Halted 0 ms 0 KB -