Submission #1074772

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1074772	2024-08-25T13:53:10 Z	socpite	Uplifting Excursion (BOI22_vault)	C++17	0 / 100	279 ms	3932 KB

vault

#include<bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
const int maxn = 305;

long long A[2*maxn], inp[2*maxn];

int bs_A[2*maxn][65];

vector<pair<int, long long>> g[65][maxn];

long long dp[2*maxn*maxn];
long long tmp[2*maxn*maxn];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int m;
	long long L;
	cin >> m >> L;
	for(int i = 0; i <= 2*m; i++)cin >> A[i];
	if(L < 0){
		L*=-1;
		for(int i = 1; i <= m; i++)swap(A[m-i], A[m+i]);
	}
	for(int i = 0; i <= 2*m; i++){
		if(i == m)continue;
		for(int j = 0; j <= 60; j++){
			if(A[i] == 0)break;
			bs_A[i][j] = A[i]&1 ? 1 : 2;
			A[i] = (A[i]-1)/2;
		}
	}
	for(int b = 0; b <= 60; b++){
		for(int i = 1; i <= m; i++){
			map<int, long long> mp;
			for(int p_val = 0; p_val <= bs_A[m+i][b]; p_val++){
				for(int n_val = 0; n_val <= bs_A[m-i][b]; n_val++){
					mp[(p_val - n_val)*i] = max<long long>(mp[(p_val - n_val)*i], p_val + n_val);
				}
			}	
			for(auto v: mp)g[b][i].push_back({v.first, v.second<<b});
		}
	}
	int sum = m*(m+1);
	memset(dp, -1, sizeof(dp));
	dp[sum] = 0;
	for(int b = 0; b <= 60; b++){
		for(int i = 1; i <= m; i++){
			memset(tmp, -1, sizeof(tmp));
			for(int j = 0; j <= 2*sum; j++){
				if(dp[j] == -1)continue;
				for(auto v: g[b][i])tmp[j + v.first] = max(tmp[j + v.first], dp[j] + v.second);
			}
			memcpy(dp, tmp, sizeof(dp));
		}
		for(int j = 0; j <= 2*sum; j++)tmp[j] = -1; 
		for(int i = 0; i <= 2*sum; i++){
			if(((i&1)^(sum&1)) != ((L>>b)&1))continue;
			int ri = i - sum, pos;
			if(ri < 0)pos = (ri-1)/2 + sum;
			else pos = ri/2 + sum;
			assert(pos >= 0 && pos <= 2*sum);
			tmp[pos] = max(tmp[pos], dp[i]);
		}
		for(int i = 0; i <= 2*sum; i++)dp[i] = tmp[i];
	}
	if(dp[sum] == -1)cout << "impossible";
	else cout << dp[sum] + A[m];
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	3840 KB	Output is correct
2	Correct	17 ms	3852 KB	Output is correct
3	Correct	7 ms	3676 KB	Output is correct
4	Correct	51 ms	3844 KB	Output is correct
5	Correct	270 ms	3928 KB	Output is correct
6	Correct	267 ms	3932 KB	Output is correct
7	Correct	262 ms	3928 KB	Output is correct
8	Correct	279 ms	3932 KB	Output is correct
9	Incorrect	267 ms	3932 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	3840 KB	Output is correct
2	Correct	17 ms	3852 KB	Output is correct
3	Correct	7 ms	3676 KB	Output is correct
4	Correct	51 ms	3844 KB	Output is correct
5	Correct	270 ms	3928 KB	Output is correct
6	Correct	267 ms	3932 KB	Output is correct
7	Correct	262 ms	3928 KB	Output is correct
8	Correct	279 ms	3932 KB	Output is correct
9	Incorrect	267 ms	3932 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	55 ms	3672 KB	Output is correct
2	Correct	158 ms	3932 KB	Output is correct
3	Correct	158 ms	3672 KB	Output is correct
4	Correct	160 ms	3672 KB	Output is correct
5	Incorrect	160 ms	3928 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #3-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	3672 KB	Output is correct
2	Correct	158 ms	3932 KB	Output is correct
3	Correct	158 ms	3672 KB	Output is correct
4	Correct	160 ms	3672 KB	Output is correct
5	Incorrect	160 ms	3928 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #4-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	3672 KB	Output is correct
2	Correct	158 ms	3932 KB	Output is correct
3	Correct	158 ms	3672 KB	Output is correct
4	Correct	160 ms	3672 KB	Output is correct
5	Incorrect	160 ms	3928 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #4-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	3840 KB	Output is correct
2	Correct	17 ms	3852 KB	Output is correct
3	Correct	7 ms	3676 KB	Output is correct
4	Correct	51 ms	3844 KB	Output is correct
5	Correct	270 ms	3928 KB	Output is correct
6	Correct	267 ms	3932 KB	Output is correct
7	Correct	262 ms	3928 KB	Output is correct
8	Correct	279 ms	3932 KB	Output is correct
9	Incorrect	267 ms	3932 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	55 ms	3672 KB	Output is correct
2	Correct	158 ms	3932 KB	Output is correct
3	Correct	158 ms	3672 KB	Output is correct
4	Correct	160 ms	3672 KB	Output is correct
5	Incorrect	160 ms	3928 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #5-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	3840 KB	Output is correct
2	Correct	17 ms	3852 KB	Output is correct
3	Correct	7 ms	3676 KB	Output is correct
4	Correct	51 ms	3844 KB	Output is correct
5	Correct	270 ms	3928 KB	Output is correct
6	Correct	267 ms	3932 KB	Output is correct
7	Correct	262 ms	3928 KB	Output is correct
8	Correct	279 ms	3932 KB	Output is correct
9	Incorrect	267 ms	3932 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	55 ms	3672 KB	Output is correct
2	Correct	158 ms	3932 KB	Output is correct
3	Correct	158 ms	3672 KB	Output is correct
4	Correct	160 ms	3672 KB	Output is correct
5	Incorrect	160 ms	3928 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #6-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	3840 KB	Output is correct
2	Correct	17 ms	3852 KB	Output is correct
3	Correct	7 ms	3676 KB	Output is correct
4	Correct	51 ms	3844 KB	Output is correct
5	Correct	270 ms	3928 KB	Output is correct
6	Correct	267 ms	3932 KB	Output is correct
7	Correct	262 ms	3928 KB	Output is correct
8	Correct	279 ms	3932 KB	Output is correct
9	Incorrect	267 ms	3932 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Submission #1074772

Compilation message