Submission #734183

#	Time	Username	Problem	Language	Result	Execution time	Memory
734183		minhcool	Uplifting Excursion (BOI22_vault)	C++17	0 / 100	1 ms	340 KiB

vault

#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];
	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){
		cout << L;
		return;
	}
	if(L < 0 && a[n - 1] >= -L){
		cout << -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
• 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