oj.uz

Submission #588661

# Submission time Handle Problem Language Result Execution time Memory
588661 2022-07-03T19:36:00 Z peuch Uplifting Excursion (BOI22_vault) C++17
0 / 100
 3910 ms 524288 KB 
#include<bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

const long long MAXN = 101;
const long long MAXA = 101 * 100 * 101;
const long long INF = 1e18;
const long long HALF = MAXA / 2;

long long m;
long long l;

long long v[2 * MAXN];
long long dp[2][MAXA];

int main(){
	
	scanf("%lld %lld", &m, &l);
	long long sum = 0;
	long long cnt = 0;
	multiset<pair<long long, long long> > auxMoedas;
	for(long long i = -m; i <= m; i++){
		scanf("%lld", &v[i + m]);
		sum += v[i + m] * i;
		cnt += v[i + m];
		for(int j = 0; j < v[i + m]; j++)
			auxMoedas.insert(make_pair(i, -1));
	}
	
	vector<pair<long long, long long> > moedas;
	while(!auxMoedas.empty()){
		pair<int, int> aux = *auxMoedas.begin();
		auxMoedas.erase(auxMoedas.begin());
		if(!moedas.empty() && moedas.back().first == aux.first){
			if(!auxMoedas.empty() && auxMoedas.begin()->first == aux.first){
				aux.first *= 2;
				aux.second += auxMoedas.begin()->second;
				auxMoedas.erase(auxMoedas.begin());
				auxMoedas.insert(aux);
				continue;
			}
		}
		moedas.push_back(aux);
	}
	
	if(l + HALF >= MAXA || l + HALF < 0){
		printf("impossible\n");
		return 0;
	} 
	
	for(long long j = 0; j < MAXA; j++)
		dp[1][j] = INF;
	
	dp[1][HALF] = 0;
	
	for(auto val : moedas){
//		printf("%lld %lld\n", val.first, val.second);
		swap(dp[0], dp[1]);
		for(long long j = 0; j < MAXA; j++){
			dp[1][j] = dp[0][j];
			if(j - val.first < MAXA && j - val.first >= 0) dp[1][j] = min(dp[1][j], dp[0][j - val.first] - val.second);
		}
	}
	
	if(dp[1][sum - l + HALF] == INF) printf("impossible\n");
	else printf("%lld\n", cnt - dp[1][sum - l + HALF]);
}

Compilation message

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("%lld %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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 16212 KB Output is correct
2 Correct 35 ms 16212 KB Output is correct
3 Correct 28 ms 16260 KB Output is correct
4 Correct 96 ms 16252 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3905 ms 16420 KB Output is correct
7 Correct 1514 ms 16320 KB Output is correct
8 Incorrect 3910 ms 16408 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 16212 KB Output is correct
2 Correct 35 ms 16212 KB Output is correct
3 Correct 28 ms 16260 KB Output is correct
4 Correct 96 ms 16252 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3905 ms 16420 KB Output is correct
7 Correct 1514 ms 16320 KB Output is correct
8 Incorrect 3910 ms 16408 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 16268 KB Output is correct
2 Runtime error 2663 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 100 ms 16268 KB Output is correct
2 Runtime error 2663 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 100 ms 16268 KB Output is correct
2 Runtime error 2663 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 39 ms 16212 KB Output is correct
2 Correct 35 ms 16212 KB Output is correct
3 Correct 28 ms 16260 KB Output is correct
4 Correct 96 ms 16252 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3905 ms 16420 KB Output is correct
7 Correct 1514 ms 16320 KB Output is correct
8 Incorrect 3910 ms 16408 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 16268 KB Output is correct
2 Runtime error 2663 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 39 ms 16212 KB Output is correct
2 Correct 35 ms 16212 KB Output is correct
3 Correct 28 ms 16260 KB Output is correct
4 Correct 96 ms 16252 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3905 ms 16420 KB Output is correct
7 Correct 1514 ms 16320 KB Output is correct
8 Incorrect 3910 ms 16408 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 16268 KB Output is correct
2 Runtime error 2663 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 39 ms 16212 KB Output is correct
2 Correct 35 ms 16212 KB Output is correct
3 Correct 28 ms 16260 KB Output is correct
4 Correct 96 ms 16252 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3905 ms 16420 KB Output is correct
7 Correct 1514 ms 16320 KB Output is correct
8 Incorrect 3910 ms 16408 KB Output isn't correct
9 Halted 0 ms 0 KB -