oj.uz

Submission #1070859

# Submission time Handle Problem Language Result Execution time Memory
1070859 2024-08-22T19:57:46 Z AdamGS Uplifting Excursion (BOI22_vault) C++17
20 / 100
 2443 ms 33980 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]);
		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 49 ms 19036 KB Output is correct
2 Correct 63 ms 19036 KB Output is correct
3 Correct 23 ms 19032 KB Output is correct
4 Correct 207 ms 19036 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 1147 ms 19508 KB Output is correct
7 Correct 1104 ms 19280 KB Output is correct
8 Correct 1161 ms 19504 KB Output is correct
9 Correct 1150 ms 19588 KB Output is correct
10 Correct 867 ms 19036 KB Output is correct
11 Correct 878 ms 19032 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 19036 KB Output is correct
2 Correct 63 ms 19036 KB Output is correct
3 Correct 23 ms 19032 KB Output is correct
4 Correct 207 ms 19036 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 1147 ms 19508 KB Output is correct
7 Correct 1104 ms 19280 KB Output is correct
8 Correct 1161 ms 19504 KB Output is correct
9 Correct 1150 ms 19588 KB Output is correct
10 Correct 867 ms 19036 KB Output is correct
11 Correct 878 ms 19032 KB Output is correct
12 Correct 48 ms 19036 KB Output is correct
13 Correct 61 ms 19248 KB Output is correct
14 Correct 25 ms 19032 KB Output is correct
15 Correct 203 ms 19248 KB Output is correct
16 Correct 2 ms 10840 KB Output is correct
17 Correct 1134 ms 19484 KB Output is correct
18 Correct 1103 ms 19404 KB Output is correct
19 Correct 1133 ms 19504 KB Output is correct
20 Correct 1141 ms 19784 KB Output is correct
21 Correct 861 ms 19036 KB Output is correct
22 Correct 861 ms 19032 KB Output is correct
23 Correct 2 ms 10844 KB Output is correct
24 Correct 2359 ms 21004 KB Output is correct
25 Correct 2311 ms 19708 KB Output is correct
26 Correct 2441 ms 22208 KB Output is correct
27 Correct 2443 ms 22320 KB Output is correct
28 Correct 1705 ms 19516 KB Output is correct
29 Correct 1735 ms 19276 KB Output is correct

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 19032 KB Output is correct
2 Correct 683 ms 23132 KB Output is correct
3 Correct 623 ms 26060 KB Output is correct
4 Correct 676 ms 31736 KB Output is correct
5 Correct 702 ms 31460 KB Output is correct
6 Correct 674 ms 33980 KB Output is correct
7 Incorrect 573 ms 19552 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 205 ms 19032 KB Output is correct
2 Correct 683 ms 23132 KB Output is correct
3 Correct 623 ms 26060 KB Output is correct
4 Correct 676 ms 31736 KB Output is correct
5 Correct 702 ms 31460 KB Output is correct
6 Correct 674 ms 33980 KB Output is correct
7 Incorrect 573 ms 19552 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 205 ms 19032 KB Output is correct
2 Correct 683 ms 23132 KB Output is correct
3 Correct 623 ms 26060 KB Output is correct
4 Correct 676 ms 31736 KB Output is correct
5 Correct 702 ms 31460 KB Output is correct
6 Correct 674 ms 33980 KB Output is correct
7 Incorrect 573 ms 19552 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 49 ms 19036 KB Output is correct
2 Correct 63 ms 19036 KB Output is correct
3 Correct 23 ms 19032 KB Output is correct
4 Correct 207 ms 19036 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 1147 ms 19508 KB Output is correct
7 Correct 1104 ms 19280 KB Output is correct
8 Correct 1161 ms 19504 KB Output is correct
9 Correct 1150 ms 19588 KB Output is correct
10 Correct 867 ms 19036 KB Output is correct
11 Correct 878 ms 19032 KB Output is correct
12 Correct 205 ms 19032 KB Output is correct
13 Correct 683 ms 23132 KB Output is correct
14 Correct 623 ms 26060 KB Output is correct
15 Correct 676 ms 31736 KB Output is correct
16 Correct 702 ms 31460 KB Output is correct
17 Correct 674 ms 33980 KB Output is correct
18 Incorrect 573 ms 19552 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 205 ms 19032 KB Output is correct
2 Correct 683 ms 23132 KB Output is correct
3 Correct 623 ms 26060 KB Output is correct
4 Correct 676 ms 31736 KB Output is correct
5 Correct 702 ms 31460 KB Output is correct
6 Correct 674 ms 33980 KB Output is correct
7 Incorrect 573 ms 19552 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 49 ms 19036 KB Output is correct
2 Correct 63 ms 19036 KB Output is correct
3 Correct 23 ms 19032 KB Output is correct
4 Correct 207 ms 19036 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 1147 ms 19508 KB Output is correct
7 Correct 1104 ms 19280 KB Output is correct
8 Correct 1161 ms 19504 KB Output is correct
9 Correct 1150 ms 19588 KB Output is correct
10 Correct 867 ms 19036 KB Output is correct
11 Correct 878 ms 19032 KB Output is correct
12 Correct 48 ms 19036 KB Output is correct
13 Correct 61 ms 19248 KB Output is correct
14 Correct 25 ms 19032 KB Output is correct
15 Correct 203 ms 19248 KB Output is correct
16 Correct 2 ms 10840 KB Output is correct
17 Correct 1134 ms 19484 KB Output is correct
18 Correct 1103 ms 19404 KB Output is correct
19 Correct 1133 ms 19504 KB Output is correct
20 Correct 1141 ms 19784 KB Output is correct
21 Correct 861 ms 19036 KB Output is correct
22 Correct 861 ms 19032 KB Output is correct
23 Correct 2 ms 10844 KB Output is correct
24 Correct 2359 ms 21004 KB Output is correct
25 Correct 2311 ms 19708 KB Output is correct
26 Correct 2441 ms 22208 KB Output is correct
27 Correct 2443 ms 22320 KB Output is correct
28 Correct 1705 ms 19516 KB Output is correct
29 Correct 1735 ms 19276 KB Output is correct
30 Correct 205 ms 19032 KB Output is correct
31 Correct 683 ms 23132 KB Output is correct
32 Correct 623 ms 26060 KB Output is correct
33 Correct 676 ms 31736 KB Output is correct
34 Correct 702 ms 31460 KB Output is correct
35 Correct 674 ms 33980 KB Output is correct
36 Incorrect 573 ms 19552 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 205 ms 19032 KB Output is correct
2 Correct 683 ms 23132 KB Output is correct
3 Correct 623 ms 26060 KB Output is correct
4 Correct 676 ms 31736 KB Output is correct
5 Correct 702 ms 31460 KB Output is correct
6 Correct 674 ms 33980 KB Output is correct
7 Incorrect 573 ms 19552 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 49 ms 19036 KB Output is correct
2 Correct 63 ms 19036 KB Output is correct
3 Correct 23 ms 19032 KB Output is correct
4 Correct 207 ms 19036 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 1147 ms 19508 KB Output is correct
7 Correct 1104 ms 19280 KB Output is correct
8 Correct 1161 ms 19504 KB Output is correct
9 Correct 1150 ms 19588 KB Output is correct
10 Correct 867 ms 19036 KB Output is correct
11 Correct 878 ms 19032 KB Output is correct
12 Correct 48 ms 19036 KB Output is correct
13 Correct 61 ms 19248 KB Output is correct
14 Correct 25 ms 19032 KB Output is correct
15 Correct 203 ms 19248 KB Output is correct
16 Correct 2 ms 10840 KB Output is correct
17 Correct 1134 ms 19484 KB Output is correct
18 Correct 1103 ms 19404 KB Output is correct
19 Correct 1133 ms 19504 KB Output is correct
20 Correct 1141 ms 19784 KB Output is correct
21 Correct 861 ms 19036 KB Output is correct
22 Correct 861 ms 19032 KB Output is correct
23 Correct 2 ms 10844 KB Output is correct
24 Correct 2359 ms 21004 KB Output is correct
25 Correct 2311 ms 19708 KB Output is correct
26 Correct 2441 ms 22208 KB Output is correct
27 Correct 2443 ms 22320 KB Output is correct
28 Correct 1705 ms 19516 KB Output is correct
29 Correct 1735 ms 19276 KB Output is correct
30 Correct 205 ms 19032 KB Output is correct
31 Correct 683 ms 23132 KB Output is correct
32 Correct 623 ms 26060 KB Output is correct
33 Correct 676 ms 31736 KB Output is correct
34 Correct 702 ms 31460 KB Output is correct
35 Correct 674 ms 33980 KB Output is correct
36 Incorrect 573 ms 19552 KB Output isn't correct
37 Halted 0 ms 0 KB -