oj.uz

Submission #602551

# Submission time Handle Problem Language Result Execution time Memory
602551 2022-07-23T08:04:58 Z CSQ31 Uplifting Excursion (BOI22_vault) C++17
0 / 100
 1 ms 212 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];
vector<ll>knapsack(int n,vector<int>item){
	vector<ll>dp(n+1,-1e18);
	dp[0] = 0;
	int m = item.size()-1;
	for(int i=1;i<=m;i++){
		int x = item[i];
		int z = 1;
		while(x>=z){
			x-=z;
			for(int j=n;j>=i*z;j--)dp[j] = max(dp[j],dp[j-i*z] + z);
			z*=2;
		}
		if(x)for(int j=n;j>=i*x;j--)dp[j] = max(dp[j],dp[j-i*x] + x);
	}
	return dp;
	
}
int main()
{
	ll m,L;
	cin>>m>>L;
	for(int i=-m;i<=m;i++)cin>>A[i+m];
	//greedy sol and optimal sol distance small
	ll neg = 0,pos = 0;
	for(ll i=-m;i<=0;i++)neg+=i*A[i+m];
	for(ll i=0 ;i<=m;i++)pos+=i*A[i+m];
	if(!(neg<=L && L<=pos)){
		cout<<"impossible";
		return 0;
	}
	if(neg+pos<L){
		cout<<"impossible"<<'\n';
		return 0;
	}//cout<<neg<<" "<<pos<<" "<<L<<'\n';
	ll cur = 0;
	ll mx = 2*m*m;
	vector<int>item(m+1);
	for(int i=-m;i<0;i++)item[-i] = min(2*m,A[i+m]);
	for(ll i=1;i<=m;i++){
		if(neg+i > L)break;
		ll take = min((L-neg)/i ,A[i+m]);
		A[i+m]-=take;
		neg+=take*i;
		cur+=take;
	}
    vector<ll>dp1 = knapsack(mx,item);
    for(int i=1;i<=m;i++)item[i] = min(2*m,A[i+m]);
	vector<ll>dp2 = knapsack(mx,item);
	int need = L-neg;
	ll ans = -1e18;
	for(int i=need;i<=mx;i++){
		if(dp2[i] >=0 && dp1[i-need]>=0)ans = max(ans,dp2[i] + dp1[i-need]);
	}
	if(ans==-1e18)cout<<"impossible"<<'\n';
	else cout<<ans + A[m] + cur<<'\n';
		
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 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 212 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 Incorrect 1 ms 212 KB Output isn't correct
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 Incorrect 1 ms 212 KB Output isn't correct
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 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 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 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 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 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

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