oj.uz

Submission #588644

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

const int MAXN = 210;
const long long INF = 1e18;
const int HALF = MAXN * MAXN / 2;

int m;
long long l;

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

int main(){
	
	scanf("%d %lld", &m, &l);
	long long sum = 0;
	long long cnt = 0;
	for(int i = -m; i <= m; i++){
		scanf("%lld", &v[i + m]);
		sum += v[i + m] * i;
		cnt += v[i + m];
	}
	
	if(l + HALF >= MAXN * MAXN || l + HALF < 0){
		printf("impossible\n");
		return 0;
	}
	
	for(int j = 0; j < MAXN * MAXN; j++)
		dp[1][j] = INF;
	
	dp[1][HALF] = 0;
	for(int i = 1; i <= 2 * m + 1; i++){
		for(int k = 0; k < v[i - 1]; k++){
			for(int j = 0; j < MAXN * MAXN; j++)
				dp[0][j] = dp[1][j];
			for(int j = 0; j < MAXN * MAXN; j++){
				dp[1][j] = dp[0][j];
				if(j - (i - m - 1) < MAXN * MAXN && j - (i - m - 1) >= 0) dp[1][j] = min(dp[1][j], dp[0][j - (i - m - 1)] + 1);
			}
		}
	}
	
	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:16:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%d %lld", &m, &l);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
vault.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   scanf("%lld", &v[i + m]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 4 ms 980 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 175 ms 980 KB Output is correct
7 Correct 64 ms 988 KB Output is correct
8 Correct 151 ms 980 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 4 ms 980 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 175 ms 980 KB Output is correct
7 Correct 64 ms 988 KB Output is correct
8 Correct 151 ms 980 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 980 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 5 ms 980 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 5 ms 980 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 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 4 ms 980 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 175 ms 980 KB Output is correct
7 Correct 64 ms 988 KB Output is correct
8 Correct 151 ms 980 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 980 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 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 4 ms 980 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 175 ms 980 KB Output is correct
7 Correct 64 ms 988 KB Output is correct
8 Correct 151 ms 980 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 980 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 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 4 ms 980 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 175 ms 980 KB Output is correct
7 Correct 64 ms 988 KB Output is correct
8 Correct 151 ms 980 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -