oj.uz

답안 #734183

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
734183 2023-05-02T03:37:59 Z minhcool Uplifting Excursion (BOI22_vault) C++17
0 / 100
 1 ms 340 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];
	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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -