oj.uz

Submission #601179

# Submission time Handle Problem Language Result Execution time Memory
601179 2022-07-21T12:44:09 Z CSQ31 Uplifting Excursion (BOI22_vault) C++17
5 / 100
 5000 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(a) a.begin(),a.end()
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long int ll;
ll A[5000],B[5000];
unordered_map<ll,ll>val,dp;
int main()
{
	int m;
	ll L;
	cin>>m>>L;
	for(int i=-m;i<=m;i++)cin>>A[i+m];
	ll ans = A[m];
	/*
	//subtask 2 m^4 knapsack??
	//consider left and right side separately
	//let ai be number of art piece i chosen
	//1)atleast one of ai , a_{-i} must be 0
	//2)consider only positive
	//ai aj i<j
	//if aj >= i and ai <= Ai-j
	//do ai+=j aj-=i
	//j > i
	//ai <= Ai-M and aj >= M cant be both true
	//a prefix p has ai>Ai-M then p+1 can be anything
	//ahhhhhhhhh iterate first i such that ai <= M
	for(int i=1;i<=m;i++){
	}
	*/
	dp[0] = 0;
	for(ll i=-m;i<=m;i++){
		if(i==0)continue;
		ll z = 1;
		vector<ll>item;
		while(A[i+m]>=z){
			item.push_back(z);
			A[i+m]-=z;
			z*=2;
		}
		if(A[i+m])item.push_back(A[i+m]);
		for(ll x:item){
			vector<array<ll,2>>upd;
			for(auto y:dp)upd.push_back({x*i+y.first,y.second+x});
			for(auto x:upd)dp[x[0]] = max(dp[x[0]],x[1]);
		}
	}
	if(dp.find(L) == dp.end())cout<<"impossible";
	else cout<<dp[L]+A[m]<<'\n';
	
	
}

Compilation message

vault.cpp: In function 'int main()':
vault.cpp:14:5: warning: unused variable 'ans' [-Wunused-variable]
   14 |  ll ans = A[m];
      |     ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 800 ms 5048 KB Output is correct
6 Correct 846 ms 6152 KB Output is correct
7 Correct 122 ms 2468 KB Output is correct
8 Correct 767 ms 5116 KB Output is correct
9 Correct 1964 ms 9280 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 800 ms 5048 KB Output is correct
6 Correct 846 ms 6152 KB Output is correct
7 Correct 122 ms 2468 KB Output is correct
8 Correct 767 ms 5116 KB Output is correct
9 Correct 1964 ms 9280 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 842 ms 5188 KB Output is correct
17 Correct 843 ms 6256 KB Output is correct
18 Correct 127 ms 2572 KB Output is correct
19 Correct 735 ms 5020 KB Output is correct
20 Correct 1967 ms 9324 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Execution timed out 5046 ms 23708 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 1375 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 1375 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 1375 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 800 ms 5048 KB Output is correct
6 Correct 846 ms 6152 KB Output is correct
7 Correct 122 ms 2468 KB Output is correct
8 Correct 767 ms 5116 KB Output is correct
9 Correct 1964 ms 9280 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Runtime error 1375 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 1375 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 800 ms 5048 KB Output is correct
6 Correct 846 ms 6152 KB Output is correct
7 Correct 122 ms 2468 KB Output is correct
8 Correct 767 ms 5116 KB Output is correct
9 Correct 1964 ms 9280 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 842 ms 5188 KB Output is correct
17 Correct 843 ms 6256 KB Output is correct
18 Correct 127 ms 2572 KB Output is correct
19 Correct 735 ms 5020 KB Output is correct
20 Correct 1967 ms 9324 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Execution timed out 5046 ms 23708 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 1375 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 800 ms 5048 KB Output is correct
6 Correct 846 ms 6152 KB Output is correct
7 Correct 122 ms 2468 KB Output is correct
8 Correct 767 ms 5116 KB Output is correct
9 Correct 1964 ms 9280 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 842 ms 5188 KB Output is correct
17 Correct 843 ms 6256 KB Output is correct
18 Correct 127 ms 2572 KB Output is correct
19 Correct 735 ms 5020 KB Output is correct
20 Correct 1967 ms 9324 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Execution timed out 5046 ms 23708 KB Time limit exceeded
24 Halted 0 ms 0 KB -