oj.uz

Submission #588669

# Submission time Handle Problem Language Result Execution time Memory
588669 2022-07-03T19:58:24 Z peuch Uplifting Excursion (BOI22_vault) C++17
5 / 100
 5000 ms 17644 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14292 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 6 ms 14376 KB Output is correct
4 Correct 6 ms 14332 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 456 ms 15172 KB Output is correct
7 Correct 84 ms 14640 KB Output is correct
8 Correct 407 ms 15020 KB Output is correct
9 Correct 1035 ms 15588 KB Output is correct
10 Correct 6 ms 14420 KB Output is correct
11 Correct 6 ms 14420 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14292 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 6 ms 14376 KB Output is correct
4 Correct 6 ms 14332 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 456 ms 15172 KB Output is correct
7 Correct 84 ms 14640 KB Output is correct
8 Correct 407 ms 15020 KB Output is correct
9 Correct 1035 ms 15588 KB Output is correct
10 Correct 6 ms 14420 KB Output is correct
11 Correct 6 ms 14420 KB Output is correct
12 Correct 8 ms 14380 KB Output is correct
13 Correct 6 ms 14292 KB Output is correct
14 Correct 7 ms 14292 KB Output is correct
15 Correct 7 ms 14340 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 468 ms 15184 KB Output is correct
18 Correct 83 ms 14544 KB Output is correct
19 Correct 408 ms 14784 KB Output is correct
20 Correct 1034 ms 15420 KB Output is correct
21 Correct 6 ms 14420 KB Output is correct
22 Correct 6 ms 14420 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Execution timed out 5051 ms 17644 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14292 KB Output is correct
2 Incorrect 0 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 6 ms 14292 KB Output is correct
2 Incorrect 0 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 6 ms 14292 KB Output is correct
2 Incorrect 0 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 Correct 6 ms 14292 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 6 ms 14376 KB Output is correct
4 Correct 6 ms 14332 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 456 ms 15172 KB Output is correct
7 Correct 84 ms 14640 KB Output is correct
8 Correct 407 ms 15020 KB Output is correct
9 Correct 1035 ms 15588 KB Output is correct
10 Correct 6 ms 14420 KB Output is correct
11 Correct 6 ms 14420 KB Output is correct
12 Correct 6 ms 14292 KB Output is correct
13 Incorrect 0 ms 212 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14292 KB Output is correct
2 Incorrect 0 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 Correct 6 ms 14292 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 6 ms 14376 KB Output is correct
4 Correct 6 ms 14332 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 456 ms 15172 KB Output is correct
7 Correct 84 ms 14640 KB Output is correct
8 Correct 407 ms 15020 KB Output is correct
9 Correct 1035 ms 15588 KB Output is correct
10 Correct 6 ms 14420 KB Output is correct
11 Correct 6 ms 14420 KB Output is correct
12 Correct 8 ms 14380 KB Output is correct
13 Correct 6 ms 14292 KB Output is correct
14 Correct 7 ms 14292 KB Output is correct
15 Correct 7 ms 14340 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 468 ms 15184 KB Output is correct
18 Correct 83 ms 14544 KB Output is correct
19 Correct 408 ms 14784 KB Output is correct
20 Correct 1034 ms 15420 KB Output is correct
21 Correct 6 ms 14420 KB Output is correct
22 Correct 6 ms 14420 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Execution timed out 5051 ms 17644 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14292 KB Output is correct
2 Incorrect 0 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 Correct 6 ms 14292 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 6 ms 14376 KB Output is correct
4 Correct 6 ms 14332 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 456 ms 15172 KB Output is correct
7 Correct 84 ms 14640 KB Output is correct
8 Correct 407 ms 15020 KB Output is correct
9 Correct 1035 ms 15588 KB Output is correct
10 Correct 6 ms 14420 KB Output is correct
11 Correct 6 ms 14420 KB Output is correct
12 Correct 8 ms 14380 KB Output is correct
13 Correct 6 ms 14292 KB Output is correct
14 Correct 7 ms 14292 KB Output is correct
15 Correct 7 ms 14340 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 468 ms 15184 KB Output is correct
18 Correct 83 ms 14544 KB Output is correct
19 Correct 408 ms 14784 KB Output is correct
20 Correct 1034 ms 15420 KB Output is correct
21 Correct 6 ms 14420 KB Output is correct
22 Correct 6 ms 14420 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Execution timed out 5051 ms 17644 KB Time limit exceeded
25 Halted 0 ms 0 KB -