oj.uz

Submission #853465

# Submission time Handle Problem Language Result Execution time Memory
853465 2023-09-24T11:54:42 Z vjudge1 Uplifting Excursion (BOI22_vault) C++17
0 / 100
 2 ms 600 KB 
#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

void solve(){
	long long M, L; cin >> M >> L;
	vector<int> val(2 * M + 1);
	for(int i = -M; i <= M; i++){
		val[i + M] = i;
	}
	vector<long long> A(2 * M + 1);
	for(auto &i : A) cin >> i;
	if(L < 0){
		L *= -1;
		for(int i = 0; i < M; i++){
			swap(A[i], A[2 * M - i]);
		}
	}
	long long max_sum = 0;
	for(int i = M; i <= 2 * M; i++){
		max_sum += val[i] * A[i];
	}
	if(max_sum < L){
		cout << "impossible" << endl;
		return;
	}
	vector<int> ans(max_sum + 1, -1);
	ans[0] = 0;
	for(int i = M + 1; i <= 2 * M; i++){
		for(int _ = 0; _ < A[i]; _++){
			for(int w = max_sum; w >= 0; w--){
				if(ans[w] != -1) ans[w + val[i]] = max(ans[w + val[i]], ans[w] + 1);
			}
		}
	}
	for(int i = 0; i < M; i++){
		for(int _ = 0; _ < A[i]; _++){
			for(int w = val[i]; w <= max_sum; w++){
				if(ans[w] != -1) ans[w + val[i]] = max(ans[w + val[i]], ans[w] + 1);
			}
		}
	}
	if(ans[L] == -1) cout << "impossible" << endl;
	else cout << ans[L] + A[M] << endl;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	solve();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 2 ms 600 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 2 ms 600 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 2 ms 600 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 2 ms 600 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 2 ms 600 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -