oj.uz

Submission #1070891

# Submission time Handle Problem Language Result Execution time Memory
1070891 2024-08-22T20:29:08 Z AdamGS Uplifting Excursion (BOI22_vault) C++17
20 / 100
 1419 ms 23080 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 ll LIM=7e5+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, max(A[i]-20, 0ll));
			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-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

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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 13916 KB Output is correct
2 Correct 41 ms 13916 KB Output is correct
3 Correct 15 ms 13912 KB Output is correct
4 Correct 135 ms 13964 KB Output is correct
5 Correct 2 ms 9816 KB Output is correct
6 Correct 650 ms 14212 KB Output is correct
7 Correct 649 ms 13960 KB Output is correct
8 Correct 649 ms 14196 KB Output is correct
9 Correct 660 ms 14432 KB Output is correct
10 Correct 561 ms 13916 KB Output is correct
11 Correct 562 ms 13916 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 13916 KB Output is correct
2 Correct 41 ms 13916 KB Output is correct
3 Correct 15 ms 13912 KB Output is correct
4 Correct 135 ms 13964 KB Output is correct
5 Correct 2 ms 9816 KB Output is correct
6 Correct 650 ms 14212 KB Output is correct
7 Correct 649 ms 13960 KB Output is correct
8 Correct 649 ms 14196 KB Output is correct
9 Correct 660 ms 14432 KB Output is correct
10 Correct 561 ms 13916 KB Output is correct
11 Correct 562 ms 13916 KB Output is correct
12 Correct 27 ms 13916 KB Output is correct
13 Correct 38 ms 13916 KB Output is correct
14 Correct 15 ms 13916 KB Output is correct
15 Correct 134 ms 13916 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 646 ms 14216 KB Output is correct
18 Correct 643 ms 13960 KB Output is correct
19 Correct 672 ms 14200 KB Output is correct
20 Correct 658 ms 14288 KB Output is correct
21 Correct 563 ms 13972 KB Output is correct
22 Correct 567 ms 13916 KB Output is correct
23 Correct 2 ms 9820 KB Output is correct
24 Correct 1378 ms 15692 KB Output is correct
25 Correct 1337 ms 14420 KB Output is correct
26 Correct 1414 ms 16912 KB Output is correct
27 Correct 1419 ms 16884 KB Output is correct
28 Correct 1129 ms 13964 KB Output is correct
29 Correct 1122 ms 13912 KB Output is correct

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 13916 KB Output is correct
2 Correct 455 ms 17264 KB Output is correct
3 Correct 387 ms 17724 KB Output is correct
4 Correct 480 ms 23052 KB Output is correct
5 Correct 466 ms 20812 KB Output is correct
6 Correct 506 ms 23080 KB Output is correct
7 Incorrect 364 ms 14164 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 13916 KB Output is correct
2 Correct 455 ms 17264 KB Output is correct
3 Correct 387 ms 17724 KB Output is correct
4 Correct 480 ms 23052 KB Output is correct
5 Correct 466 ms 20812 KB Output is correct
6 Correct 506 ms 23080 KB Output is correct
7 Incorrect 364 ms 14164 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 13916 KB Output is correct
2 Correct 455 ms 17264 KB Output is correct
3 Correct 387 ms 17724 KB Output is correct
4 Correct 480 ms 23052 KB Output is correct
5 Correct 466 ms 20812 KB Output is correct
6 Correct 506 ms 23080 KB Output is correct
7 Incorrect 364 ms 14164 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 13916 KB Output is correct
2 Correct 41 ms 13916 KB Output is correct
3 Correct 15 ms 13912 KB Output is correct
4 Correct 135 ms 13964 KB Output is correct
5 Correct 2 ms 9816 KB Output is correct
6 Correct 650 ms 14212 KB Output is correct
7 Correct 649 ms 13960 KB Output is correct
8 Correct 649 ms 14196 KB Output is correct
9 Correct 660 ms 14432 KB Output is correct
10 Correct 561 ms 13916 KB Output is correct
11 Correct 562 ms 13916 KB Output is correct
12 Correct 136 ms 13916 KB Output is correct
13 Correct 455 ms 17264 KB Output is correct
14 Correct 387 ms 17724 KB Output is correct
15 Correct 480 ms 23052 KB Output is correct
16 Correct 466 ms 20812 KB Output is correct
17 Correct 506 ms 23080 KB Output is correct
18 Incorrect 364 ms 14164 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 13916 KB Output is correct
2 Correct 455 ms 17264 KB Output is correct
3 Correct 387 ms 17724 KB Output is correct
4 Correct 480 ms 23052 KB Output is correct
5 Correct 466 ms 20812 KB Output is correct
6 Correct 506 ms 23080 KB Output is correct
7 Incorrect 364 ms 14164 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 13916 KB Output is correct
2 Correct 41 ms 13916 KB Output is correct
3 Correct 15 ms 13912 KB Output is correct
4 Correct 135 ms 13964 KB Output is correct
5 Correct 2 ms 9816 KB Output is correct
6 Correct 650 ms 14212 KB Output is correct
7 Correct 649 ms 13960 KB Output is correct
8 Correct 649 ms 14196 KB Output is correct
9 Correct 660 ms 14432 KB Output is correct
10 Correct 561 ms 13916 KB Output is correct
11 Correct 562 ms 13916 KB Output is correct
12 Correct 27 ms 13916 KB Output is correct
13 Correct 38 ms 13916 KB Output is correct
14 Correct 15 ms 13916 KB Output is correct
15 Correct 134 ms 13916 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 646 ms 14216 KB Output is correct
18 Correct 643 ms 13960 KB Output is correct
19 Correct 672 ms 14200 KB Output is correct
20 Correct 658 ms 14288 KB Output is correct
21 Correct 563 ms 13972 KB Output is correct
22 Correct 567 ms 13916 KB Output is correct
23 Correct 2 ms 9820 KB Output is correct
24 Correct 1378 ms 15692 KB Output is correct
25 Correct 1337 ms 14420 KB Output is correct
26 Correct 1414 ms 16912 KB Output is correct
27 Correct 1419 ms 16884 KB Output is correct
28 Correct 1129 ms 13964 KB Output is correct
29 Correct 1122 ms 13912 KB Output is correct
30 Correct 136 ms 13916 KB Output is correct
31 Correct 455 ms 17264 KB Output is correct
32 Correct 387 ms 17724 KB Output is correct
33 Correct 480 ms 23052 KB Output is correct
34 Correct 466 ms 20812 KB Output is correct
35 Correct 506 ms 23080 KB Output is correct
36 Incorrect 364 ms 14164 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 13916 KB Output is correct
2 Correct 455 ms 17264 KB Output is correct
3 Correct 387 ms 17724 KB Output is correct
4 Correct 480 ms 23052 KB Output is correct
5 Correct 466 ms 20812 KB Output is correct
6 Correct 506 ms 23080 KB Output is correct
7 Incorrect 364 ms 14164 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 13916 KB Output is correct
2 Correct 41 ms 13916 KB Output is correct
3 Correct 15 ms 13912 KB Output is correct
4 Correct 135 ms 13964 KB Output is correct
5 Correct 2 ms 9816 KB Output is correct
6 Correct 650 ms 14212 KB Output is correct
7 Correct 649 ms 13960 KB Output is correct
8 Correct 649 ms 14196 KB Output is correct
9 Correct 660 ms 14432 KB Output is correct
10 Correct 561 ms 13916 KB Output is correct
11 Correct 562 ms 13916 KB Output is correct
12 Correct 27 ms 13916 KB Output is correct
13 Correct 38 ms 13916 KB Output is correct
14 Correct 15 ms 13916 KB Output is correct
15 Correct 134 ms 13916 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 646 ms 14216 KB Output is correct
18 Correct 643 ms 13960 KB Output is correct
19 Correct 672 ms 14200 KB Output is correct
20 Correct 658 ms 14288 KB Output is correct
21 Correct 563 ms 13972 KB Output is correct
22 Correct 567 ms 13916 KB Output is correct
23 Correct 2 ms 9820 KB Output is correct
24 Correct 1378 ms 15692 KB Output is correct
25 Correct 1337 ms 14420 KB Output is correct
26 Correct 1414 ms 16912 KB Output is correct
27 Correct 1419 ms 16884 KB Output is correct
28 Correct 1129 ms 13964 KB Output is correct
29 Correct 1122 ms 13912 KB Output is correct
30 Correct 136 ms 13916 KB Output is correct
31 Correct 455 ms 17264 KB Output is correct
32 Correct 387 ms 17724 KB Output is correct
33 Correct 480 ms 23052 KB Output is correct
34 Correct 466 ms 20812 KB Output is correct
35 Correct 506 ms 23080 KB Output is correct
36 Incorrect 364 ms 14164 KB Output isn't correct
37 Halted 0 ms 0 KB -