oj.uz

Submission #1070911

# Submission time Handle Problem Language Result Execution time Memory
1070911 2024-08-22T20:42:12 Z AdamGS Uplifting Excursion (BOI22_vault) C++17
20 / 100
 2035 ms 31328 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;
  int ile=0;
	for(ll i=n; i; --i) {
		if(m>=LIM/2) {
			ll p=m-LIM/2;
			p=(p+i-1)/i;
		if(ile<5)	p=min(p, max(A[i]-50, 0ll));
			A[i]-=p;
		if(A[i]) ++ile;
          
          dp[0]+=p;
			m-=p*i;	
		}
	}
	if(m>=LIM) {
		cout << "impossible\n";
		return 0;
	}
	rep(xd, 2) {
		for(ll i=1; i<=n; ++i) if(A[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:51: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]
   51 |     while(l[p]<V[p].size() && (j-V[p][l[p]])/i>A[i]) ++l[p];
vault.cpp:57: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]
   57 |     if(l[p]<V[p].size()) {

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 19036 KB Output is correct
2 Correct 32 ms 19036 KB Output is correct
3 Correct 14 ms 19036 KB Output is correct
4 Correct 100 ms 19032 KB Output is correct
5 Correct 938 ms 19464 KB Output is correct
6 Correct 964 ms 19716 KB Output is correct
7 Correct 429 ms 19400 KB Output is correct
8 Correct 942 ms 19504 KB Output is correct
9 Correct 978 ms 19588 KB Output is correct
10 Correct 23 ms 19036 KB Output is correct
11 Correct 49 ms 19256 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 19036 KB Output is correct
2 Correct 32 ms 19036 KB Output is correct
3 Correct 14 ms 19036 KB Output is correct
4 Correct 100 ms 19032 KB Output is correct
5 Correct 938 ms 19464 KB Output is correct
6 Correct 964 ms 19716 KB Output is correct
7 Correct 429 ms 19400 KB Output is correct
8 Correct 942 ms 19504 KB Output is correct
9 Correct 978 ms 19588 KB Output is correct
10 Correct 23 ms 19036 KB Output is correct
11 Correct 49 ms 19256 KB Output is correct
12 Correct 41 ms 19036 KB Output is correct
13 Correct 30 ms 19036 KB Output is correct
14 Correct 13 ms 19036 KB Output is correct
15 Correct 93 ms 19036 KB Output is correct
16 Correct 932 ms 19456 KB Output is correct
17 Correct 948 ms 19768 KB Output is correct
18 Correct 425 ms 19272 KB Output is correct
19 Correct 938 ms 19508 KB Output is correct
20 Correct 976 ms 19592 KB Output is correct
21 Correct 23 ms 19036 KB Output is correct
22 Correct 47 ms 19264 KB Output is correct
23 Correct 1981 ms 20900 KB Output is correct
24 Correct 2008 ms 20968 KB Output is correct
25 Correct 794 ms 19676 KB Output is correct
26 Correct 2027 ms 22256 KB Output is correct
27 Correct 2035 ms 22280 KB Output is correct
28 Correct 22 ms 19032 KB Output is correct
29 Correct 47 ms 19036 KB Output is correct

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 19252 KB Output is correct
2 Correct 402 ms 23124 KB Output is correct
3 Correct 119 ms 26248 KB Output is correct
4 Incorrect 409 ms 31328 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 19252 KB Output is correct
2 Correct 402 ms 23124 KB Output is correct
3 Correct 119 ms 26248 KB Output is correct
4 Incorrect 409 ms 31328 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 19252 KB Output is correct
2 Correct 402 ms 23124 KB Output is correct
3 Correct 119 ms 26248 KB Output is correct
4 Incorrect 409 ms 31328 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 19036 KB Output is correct
2 Correct 32 ms 19036 KB Output is correct
3 Correct 14 ms 19036 KB Output is correct
4 Correct 100 ms 19032 KB Output is correct
5 Correct 938 ms 19464 KB Output is correct
6 Correct 964 ms 19716 KB Output is correct
7 Correct 429 ms 19400 KB Output is correct
8 Correct 942 ms 19504 KB Output is correct
9 Correct 978 ms 19588 KB Output is correct
10 Correct 23 ms 19036 KB Output is correct
11 Correct 49 ms 19256 KB Output is correct
12 Correct 94 ms 19252 KB Output is correct
13 Correct 402 ms 23124 KB Output is correct
14 Correct 119 ms 26248 KB Output is correct
15 Incorrect 409 ms 31328 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 19252 KB Output is correct
2 Correct 402 ms 23124 KB Output is correct
3 Correct 119 ms 26248 KB Output is correct
4 Incorrect 409 ms 31328 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 19036 KB Output is correct
2 Correct 32 ms 19036 KB Output is correct
3 Correct 14 ms 19036 KB Output is correct
4 Correct 100 ms 19032 KB Output is correct
5 Correct 938 ms 19464 KB Output is correct
6 Correct 964 ms 19716 KB Output is correct
7 Correct 429 ms 19400 KB Output is correct
8 Correct 942 ms 19504 KB Output is correct
9 Correct 978 ms 19588 KB Output is correct
10 Correct 23 ms 19036 KB Output is correct
11 Correct 49 ms 19256 KB Output is correct
12 Correct 41 ms 19036 KB Output is correct
13 Correct 30 ms 19036 KB Output is correct
14 Correct 13 ms 19036 KB Output is correct
15 Correct 93 ms 19036 KB Output is correct
16 Correct 932 ms 19456 KB Output is correct
17 Correct 948 ms 19768 KB Output is correct
18 Correct 425 ms 19272 KB Output is correct
19 Correct 938 ms 19508 KB Output is correct
20 Correct 976 ms 19592 KB Output is correct
21 Correct 23 ms 19036 KB Output is correct
22 Correct 47 ms 19264 KB Output is correct
23 Correct 1981 ms 20900 KB Output is correct
24 Correct 2008 ms 20968 KB Output is correct
25 Correct 794 ms 19676 KB Output is correct
26 Correct 2027 ms 22256 KB Output is correct
27 Correct 2035 ms 22280 KB Output is correct
28 Correct 22 ms 19032 KB Output is correct
29 Correct 47 ms 19036 KB Output is correct
30 Correct 94 ms 19252 KB Output is correct
31 Correct 402 ms 23124 KB Output is correct
32 Correct 119 ms 26248 KB Output is correct
33 Incorrect 409 ms 31328 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 19252 KB Output is correct
2 Correct 402 ms 23124 KB Output is correct
3 Correct 119 ms 26248 KB Output is correct
4 Incorrect 409 ms 31328 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 19036 KB Output is correct
2 Correct 32 ms 19036 KB Output is correct
3 Correct 14 ms 19036 KB Output is correct
4 Correct 100 ms 19032 KB Output is correct
5 Correct 938 ms 19464 KB Output is correct
6 Correct 964 ms 19716 KB Output is correct
7 Correct 429 ms 19400 KB Output is correct
8 Correct 942 ms 19504 KB Output is correct
9 Correct 978 ms 19588 KB Output is correct
10 Correct 23 ms 19036 KB Output is correct
11 Correct 49 ms 19256 KB Output is correct
12 Correct 41 ms 19036 KB Output is correct
13 Correct 30 ms 19036 KB Output is correct
14 Correct 13 ms 19036 KB Output is correct
15 Correct 93 ms 19036 KB Output is correct
16 Correct 932 ms 19456 KB Output is correct
17 Correct 948 ms 19768 KB Output is correct
18 Correct 425 ms 19272 KB Output is correct
19 Correct 938 ms 19508 KB Output is correct
20 Correct 976 ms 19592 KB Output is correct
21 Correct 23 ms 19036 KB Output is correct
22 Correct 47 ms 19264 KB Output is correct
23 Correct 1981 ms 20900 KB Output is correct
24 Correct 2008 ms 20968 KB Output is correct
25 Correct 794 ms 19676 KB Output is correct
26 Correct 2027 ms 22256 KB Output is correct
27 Correct 2035 ms 22280 KB Output is correct
28 Correct 22 ms 19032 KB Output is correct
29 Correct 47 ms 19036 KB Output is correct
30 Correct 94 ms 19252 KB Output is correct
31 Correct 402 ms 23124 KB Output is correct
32 Correct 119 ms 26248 KB Output is correct
33 Incorrect 409 ms 31328 KB Output isn't correct
34 Halted 0 ms 0 KB -