Submission #588669

#	Time	Username	Problem	Language	Result	Execution time	Memory
588669		peuch	Uplifting Excursion (BOI22_vault)	C++17	5 / 100	5051 ms	17644 KiB

vault

#include<bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
 
const int MAXN = 101;
const int MAXA = 101 * 100 * 101 - 3e5;
const long long INF = 1e18;
const int HALF = MAXA / 2;
 
int m;
long long l;
 
long long v[2 * MAXN];
long long dp[2][MAXA];
 
int main(){
	
	scanf("%d %lld", &m, &l);
	long long sum = 0;
	long long cnt = 0;
	vector<pair<long long, long long> > moedas;
	for(long long i = -m; i <= m; i++){
		scanf("%lld", &v[i + m]);
		sum += v[i + m] * i;
		cnt += v[i + m];
		long long aux = v[i + m];
		long long tam = 1;
		while(aux > 0){
			moedas.push_back(make_pair(i * tam, tam));
			aux--;
			if(aux % 2 == 1){
				moedas.push_back(make_pair(i * tam, tam));
				aux--;
			}
			aux /= 2;
			tam *= 2;
		}
	}
	
	if(l + HALF >= MAXA || l + HALF < 0){
		printf("impossible\n");
		return 0;
	} 
	
	for(long long j = 0; j < MAXA; j++)
		dp[1][j] = dp[0][j] = INF;
	
	dp[0][HALF] = 0;
	
	vector<int> founds(1, HALF);
	vector<int> marc(MAXA);
	marc[HALF] = 1;
	
	for(auto val : moedas){
		queue<int> auxFound;
		for(int j : founds){
			if(j + val.first >= MAXA && j + val.first < 0) continue;
			dp[1][j + val.first] = min(dp[1][j + val.first], dp[0][j] + val.second);
			auxFound.push(j + val.first);
		}
		while(!auxFound.empty()){
			int j = auxFound.front();
			auxFound.pop();
			dp[0][j] = min(dp[0][j], dp[1][j]);
			if(!marc[j]) marc[j] = 1, founds.push_back(j);
		}
	}
	
	if(dp[0][sum - l + HALF] == INF) printf("impossible\n");
	else printf("%lld\n", cnt - dp[0][sum - l + HALF]);
}

Compilation message (stderr)

vault.cpp: In function 'int main()':
vault.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |  scanf("%d %lld", &m, &l);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
vault.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   scanf("%lld", &v[i + m]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 15
• Subtask 3-1: 0 / 10
• Subtask 3-2: 0 / 10
• Subtask 4-1: 0 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 0 / 10
• Subtask 5-2: 0 / 10
• Subtask 6-1: 0 / 10
• Subtask 6-2: 0 / 10