oj.uz

Submission #734187

# Submission time Handle Problem Language Result Execution time Memory
734187 2023-05-02T03:51:09 Z minhcool Uplifting Excursion (BOI22_vault) C++17
0 / 100
 21 ms 2648 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 305;

const int oo = 1e18 + 7, mod = 1e9 + 7;

int n, L;

int a[N];

int dp[N][2 * N * N];// maximum in the end of i, (maximum possible +- = j)

void process(){
	cin >> n >> L;
	for(int i = 0; i <= 2 * n; i++) cin >> a[i];
	//cout << "OK\n";
	for(int i = 0; i <= n; i++){
		for(int j = -(n * n); j <= (n * n); j++) dp[i][j + (n * n)] = -oo;
	}
	int answer = -oo;
	dp[0][n * n] = a[n];
	if(L >= 0 && a[n + 1] >= L){
		answer = max(answer, L);
		//return;
	}
	if(L < 0 && a[n - 1] >= -L){
		answer = max(answer, -L);
		//return;
	}
	//int answer = -oo;
	int total = 0;
	for(int i = 1; i <= n; i++){
		total += (a[n + i] - a[n - i]) * i;
		for(int j = -(n * n); j <= (n * n); j++){
			//cout << dp[i][j] << "\n;
			for(int k = 0; k <= min(a[n - i], n * n); k++){// delete the negatives 
				int lst = (j - k * i);
				if(lst < -(n * n)) break;
				dp[i][j + n * n] = max(dp[i][j + n * n], dp[i - 1][lst + n * n] + (a[n - i] + a[n + i] - k));
			}
			for(int k = 0; k <= min(a[n + i], n * n); k++){
				int lst = (j + k * i);
				if(lst > (n * n)) break;
				dp[i][j + n * n] = max(dp[i][j + n * n], dp[i - 1][lst + n * n] + (a[n - i] + a[n + i] - k));
			}
			int diff = (L - total - j);
			//cout << i << " " << j << " " << total << " " << dp[i][j + n * n] << "\n";
			if(!(diff % (i + 1))){
				diff /= (i + 1);
				if(diff >= 0 && diff <= (a[n + i + 1])) answer = max(answer, dp[i][j + n * n] + diff);
				if(i < n && diff < 0 && -diff <= (a[n - i - 1])) answer = max(answer, dp[i][j + n * n] + (-diff));
			}
		}
	}
	if(answer >= 0) cout << answer;
	else cout << "impossible";
	//cout << (answer >= 0 ? answer : "impossible") << "\n";
}

signed main(){
//	ios_base::sync_with_stdio(0);
//	cin.tie(0);
	process();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 21 ms 2624 KB Output is correct
6 Correct 21 ms 2608 KB Output is correct
7 Correct 10 ms 2644 KB Output is correct
8 Incorrect 19 ms 2648 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 21 ms 2624 KB Output is correct
6 Correct 21 ms 2608 KB Output is correct
7 Correct 10 ms 2644 KB Output is correct
8 Incorrect 19 ms 2648 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 1 ms 340 KB Output is correct
2 Correct 5 ms 852 KB Output is correct
3 Correct 11 ms 852 KB Output is correct
4 Correct 6 ms 932 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Incorrect 2 ms 852 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 5 ms 852 KB Output is correct
3 Correct 11 ms 852 KB Output is correct
4 Correct 6 ms 932 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Incorrect 2 ms 852 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 5 ms 852 KB Output is correct
3 Correct 11 ms 852 KB Output is correct
4 Correct 6 ms 932 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Incorrect 2 ms 852 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 21 ms 2624 KB Output is correct
6 Correct 21 ms 2608 KB Output is correct
7 Correct 10 ms 2644 KB Output is correct
8 Incorrect 19 ms 2648 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 1 ms 340 KB Output is correct
2 Correct 5 ms 852 KB Output is correct
3 Correct 11 ms 852 KB Output is correct
4 Correct 6 ms 932 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Incorrect 2 ms 852 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 21 ms 2624 KB Output is correct
6 Correct 21 ms 2608 KB Output is correct
7 Correct 10 ms 2644 KB Output is correct
8 Incorrect 19 ms 2648 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 1 ms 340 KB Output is correct
2 Correct 5 ms 852 KB Output is correct
3 Correct 11 ms 852 KB Output is correct
4 Correct 6 ms 932 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Incorrect 2 ms 852 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 21 ms 2624 KB Output is correct
6 Correct 21 ms 2608 KB Output is correct
7 Correct 10 ms 2644 KB Output is correct
8 Incorrect 19 ms 2648 KB Output isn't correct
9 Halted 0 ms 0 KB -