oj.uz

Submission #1070861

# Submission time Handle Problem Language Result Execution time Memory
1070861 2024-08-22T19:59:01 Z AdamGS Uplifting Excursion (BOI22_vault) C++17
20 / 100
 2068 ms 33808 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=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;
	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-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 38 ms 19036 KB Output is correct
2 Correct 57 ms 19036 KB Output is correct
3 Correct 20 ms 19032 KB Output is correct
4 Correct 188 ms 19036 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 942 ms 19752 KB Output is correct
7 Correct 952 ms 19284 KB Output is correct
8 Correct 949 ms 19500 KB Output is correct
9 Correct 956 ms 19852 KB Output is correct
10 Correct 814 ms 19032 KB Output is correct
11 Correct 819 ms 19252 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 19036 KB Output is correct
2 Correct 57 ms 19036 KB Output is correct
3 Correct 20 ms 19032 KB Output is correct
4 Correct 188 ms 19036 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 942 ms 19752 KB Output is correct
7 Correct 952 ms 19284 KB Output is correct
8 Correct 949 ms 19500 KB Output is correct
9 Correct 956 ms 19852 KB Output is correct
10 Correct 814 ms 19032 KB Output is correct
11 Correct 819 ms 19252 KB Output is correct
12 Correct 42 ms 19036 KB Output is correct
13 Correct 57 ms 19032 KB Output is correct
14 Correct 20 ms 19032 KB Output is correct
15 Correct 189 ms 19036 KB Output is correct
16 Correct 1 ms 10844 KB Output is correct
17 Correct 945 ms 19504 KB Output is correct
18 Correct 934 ms 19288 KB Output is correct
19 Correct 947 ms 19504 KB Output is correct
20 Correct 958 ms 19572 KB Output is correct
21 Correct 825 ms 19252 KB Output is correct
22 Correct 856 ms 19032 KB Output is correct
23 Correct 2 ms 10840 KB Output is correct
24 Correct 1991 ms 20892 KB Output is correct
25 Correct 1960 ms 19888 KB Output is correct
26 Correct 2068 ms 22312 KB Output is correct
27 Correct 2058 ms 22264 KB Output is correct
28 Correct 1665 ms 19256 KB Output is correct
29 Correct 1665 ms 19284 KB Output is correct

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 19036 KB Output is correct
2 Correct 658 ms 23152 KB Output is correct
3 Correct 583 ms 26116 KB Output is correct
4 Correct 634 ms 31624 KB Output is correct
5 Correct 677 ms 31488 KB Output is correct
6 Correct 627 ms 33808 KB Output is correct
7 Incorrect 548 ms 19424 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 200 ms 19036 KB Output is correct
2 Correct 658 ms 23152 KB Output is correct
3 Correct 583 ms 26116 KB Output is correct
4 Correct 634 ms 31624 KB Output is correct
5 Correct 677 ms 31488 KB Output is correct
6 Correct 627 ms 33808 KB Output is correct
7 Incorrect 548 ms 19424 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 200 ms 19036 KB Output is correct
2 Correct 658 ms 23152 KB Output is correct
3 Correct 583 ms 26116 KB Output is correct
4 Correct 634 ms 31624 KB Output is correct
5 Correct 677 ms 31488 KB Output is correct
6 Correct 627 ms 33808 KB Output is correct
7 Incorrect 548 ms 19424 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 38 ms 19036 KB Output is correct
2 Correct 57 ms 19036 KB Output is correct
3 Correct 20 ms 19032 KB Output is correct
4 Correct 188 ms 19036 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 942 ms 19752 KB Output is correct
7 Correct 952 ms 19284 KB Output is correct
8 Correct 949 ms 19500 KB Output is correct
9 Correct 956 ms 19852 KB Output is correct
10 Correct 814 ms 19032 KB Output is correct
11 Correct 819 ms 19252 KB Output is correct
12 Correct 200 ms 19036 KB Output is correct
13 Correct 658 ms 23152 KB Output is correct
14 Correct 583 ms 26116 KB Output is correct
15 Correct 634 ms 31624 KB Output is correct
16 Correct 677 ms 31488 KB Output is correct
17 Correct 627 ms 33808 KB Output is correct
18 Incorrect 548 ms 19424 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 200 ms 19036 KB Output is correct
2 Correct 658 ms 23152 KB Output is correct
3 Correct 583 ms 26116 KB Output is correct
4 Correct 634 ms 31624 KB Output is correct
5 Correct 677 ms 31488 KB Output is correct
6 Correct 627 ms 33808 KB Output is correct
7 Incorrect 548 ms 19424 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 38 ms 19036 KB Output is correct
2 Correct 57 ms 19036 KB Output is correct
3 Correct 20 ms 19032 KB Output is correct
4 Correct 188 ms 19036 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 942 ms 19752 KB Output is correct
7 Correct 952 ms 19284 KB Output is correct
8 Correct 949 ms 19500 KB Output is correct
9 Correct 956 ms 19852 KB Output is correct
10 Correct 814 ms 19032 KB Output is correct
11 Correct 819 ms 19252 KB Output is correct
12 Correct 42 ms 19036 KB Output is correct
13 Correct 57 ms 19032 KB Output is correct
14 Correct 20 ms 19032 KB Output is correct
15 Correct 189 ms 19036 KB Output is correct
16 Correct 1 ms 10844 KB Output is correct
17 Correct 945 ms 19504 KB Output is correct
18 Correct 934 ms 19288 KB Output is correct
19 Correct 947 ms 19504 KB Output is correct
20 Correct 958 ms 19572 KB Output is correct
21 Correct 825 ms 19252 KB Output is correct
22 Correct 856 ms 19032 KB Output is correct
23 Correct 2 ms 10840 KB Output is correct
24 Correct 1991 ms 20892 KB Output is correct
25 Correct 1960 ms 19888 KB Output is correct
26 Correct 2068 ms 22312 KB Output is correct
27 Correct 2058 ms 22264 KB Output is correct
28 Correct 1665 ms 19256 KB Output is correct
29 Correct 1665 ms 19284 KB Output is correct
30 Correct 200 ms 19036 KB Output is correct
31 Correct 658 ms 23152 KB Output is correct
32 Correct 583 ms 26116 KB Output is correct
33 Correct 634 ms 31624 KB Output is correct
34 Correct 677 ms 31488 KB Output is correct
35 Correct 627 ms 33808 KB Output is correct
36 Incorrect 548 ms 19424 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 200 ms 19036 KB Output is correct
2 Correct 658 ms 23152 KB Output is correct
3 Correct 583 ms 26116 KB Output is correct
4 Correct 634 ms 31624 KB Output is correct
5 Correct 677 ms 31488 KB Output is correct
6 Correct 627 ms 33808 KB Output is correct
7 Incorrect 548 ms 19424 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 38 ms 19036 KB Output is correct
2 Correct 57 ms 19036 KB Output is correct
3 Correct 20 ms 19032 KB Output is correct
4 Correct 188 ms 19036 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 942 ms 19752 KB Output is correct
7 Correct 952 ms 19284 KB Output is correct
8 Correct 949 ms 19500 KB Output is correct
9 Correct 956 ms 19852 KB Output is correct
10 Correct 814 ms 19032 KB Output is correct
11 Correct 819 ms 19252 KB Output is correct
12 Correct 42 ms 19036 KB Output is correct
13 Correct 57 ms 19032 KB Output is correct
14 Correct 20 ms 19032 KB Output is correct
15 Correct 189 ms 19036 KB Output is correct
16 Correct 1 ms 10844 KB Output is correct
17 Correct 945 ms 19504 KB Output is correct
18 Correct 934 ms 19288 KB Output is correct
19 Correct 947 ms 19504 KB Output is correct
20 Correct 958 ms 19572 KB Output is correct
21 Correct 825 ms 19252 KB Output is correct
22 Correct 856 ms 19032 KB Output is correct
23 Correct 2 ms 10840 KB Output is correct
24 Correct 1991 ms 20892 KB Output is correct
25 Correct 1960 ms 19888 KB Output is correct
26 Correct 2068 ms 22312 KB Output is correct
27 Correct 2058 ms 22264 KB Output is correct
28 Correct 1665 ms 19256 KB Output is correct
29 Correct 1665 ms 19284 KB Output is correct
30 Correct 200 ms 19036 KB Output is correct
31 Correct 658 ms 23152 KB Output is correct
32 Correct 583 ms 26116 KB Output is correct
33 Correct 634 ms 31624 KB Output is correct
34 Correct 677 ms 31488 KB Output is correct
35 Correct 627 ms 33808 KB Output is correct
36 Incorrect 548 ms 19424 KB Output isn't correct
37 Halted 0 ms 0 KB -