oj.uz

Submission #601177

# Submission time Handle Problem Language Result Execution time Memory
601177 2022-07-21T12:43:07 Z CSQ31 Uplifting Excursion (BOI22_vault) C++17
0 / 100
 1319 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=1;i<=m;i++){
		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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1319 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 0 ms 212 KB Output is correct
2 Runtime error 1319 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 0 ms 212 KB Output is correct
2 Runtime error 1319 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 Incorrect 0 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1319 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 Incorrect 0 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1319 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 Incorrect 0 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -