Submission #576219

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
576219	2022-06-12T14:16:49 Z	cheissmart	Uplifting Excursion (BOI22_vault)	C++14	5 / 100	109 ms	4032 KB

vault

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
	cerr << to_string(h);
	if(sizeof ...(t)) cerr << ", ";
	DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif

const int INF = 1e9 + 7, mxM = 52, mxC = mxM * mxM * mxM / 2;

void cmax(ll& a, ll b) {
	a = max(a, b);
}

int m;
ll l, zero;

V<ll> go(ll* a) {
	V<ll> dp(mxC, -1);
	dp[0] = 0;
	for(int i = 1; i <= m; i++) {
		V<ll> ndp(mxC, -1);
		for(int j = 0; j < mxC; j++) if(dp[j] != -1) {
			for(int take = 0; take <= a[i]; take++)
				cmax(ndp[j + take * i], dp[j] + take);
		}
		swap(dp, ndp);
	}
	return dp;
}

ll a[mxM], b[mxM];

signed main()
{
	IO_OP;

	cin >> m >> l;
	for(int i = m; i >= 1; i--)
		cin >> a[i];
	cin >> zero;
	for(int i = 1; i <= m; i++)
		cin >> b[i];

	V<ll> dpa = go(a), dpb = go(b);

	ll mx = -1;
	for(int i = 0; i < mxC; i++) {
		if(i + l < 0 || i + l >= mxC) continue;
		int j = i + l;
		if(dpa[i] != -1 && dpb[j] != -1)
			mx = max(mx, dpa[i] + dpb[j]);
	}
	if(mx == -1) {
		cout << "impossible\n";
		return 0;
	}
	cout << mx + zero << '\n';

}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1924 KB	Output is correct
2	Correct	2 ms	1924 KB	Output is correct
3	Correct	1 ms	1964 KB	Output is correct
4	Correct	3 ms	1924 KB	Output is correct
5	Correct	33 ms	1948 KB	Output is correct
6	Correct	35 ms	1944 KB	Output is correct
7	Correct	12 ms	1924 KB	Output is correct
8	Correct	32 ms	1940 KB	Output is correct
9	Correct	109 ms	1944 KB	Output is correct
10	Correct	6 ms	1980 KB	Output is correct
11	Correct	6 ms	1924 KB	Output is correct

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1924 KB	Output is correct
2	Correct	2 ms	1924 KB	Output is correct
3	Correct	1 ms	1964 KB	Output is correct
4	Correct	3 ms	1924 KB	Output is correct
5	Correct	33 ms	1948 KB	Output is correct
6	Correct	35 ms	1944 KB	Output is correct
7	Correct	12 ms	1924 KB	Output is correct
8	Correct	32 ms	1940 KB	Output is correct
9	Correct	109 ms	1944 KB	Output is correct
10	Correct	6 ms	1980 KB	Output is correct
11	Correct	6 ms	1924 KB	Output is correct
12	Correct	2 ms	1924 KB	Output is correct
13	Correct	2 ms	1924 KB	Output is correct
14	Correct	1 ms	1964 KB	Output is correct
15	Correct	3 ms	1924 KB	Output is correct
16	Correct	36 ms	1924 KB	Output is correct
17	Correct	37 ms	1944 KB	Output is correct
18	Correct	12 ms	1924 KB	Output is correct
19	Correct	37 ms	1956 KB	Output is correct
20	Correct	106 ms	2036 KB	Output is correct
21	Correct	8 ms	1924 KB	Output is correct
22	Correct	5 ms	1940 KB	Output is correct
23	Runtime error	66 ms	1920 KB	Execution killed with signal 11
24	Halted	0 ms	0 KB	-

Subtask #3-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	1924 KB	Output is correct
2	Runtime error	5 ms	4032 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #3-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	1924 KB	Output is correct
2	Runtime error	5 ms	4032 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #4-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	1924 KB	Output is correct
2	Runtime error	5 ms	4032 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #4-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1924 KB	Output is correct
2	Correct	2 ms	1924 KB	Output is correct
3	Correct	1 ms	1964 KB	Output is correct
4	Correct	3 ms	1924 KB	Output is correct
5	Correct	33 ms	1948 KB	Output is correct
6	Correct	35 ms	1944 KB	Output is correct
7	Correct	12 ms	1924 KB	Output is correct
8	Correct	32 ms	1940 KB	Output is correct
9	Correct	109 ms	1944 KB	Output is correct
10	Correct	6 ms	1980 KB	Output is correct
11	Correct	6 ms	1924 KB	Output is correct
12	Correct	2 ms	1924 KB	Output is correct
13	Runtime error	5 ms	4032 KB	Execution killed with signal 11
14	Halted	0 ms	0 KB	-

Subtask #5-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	1924 KB	Output is correct
2	Runtime error	5 ms	4032 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #5-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1924 KB	Output is correct
2	Correct	2 ms	1924 KB	Output is correct
3	Correct	1 ms	1964 KB	Output is correct
4	Correct	3 ms	1924 KB	Output is correct
5	Correct	33 ms	1948 KB	Output is correct
6	Correct	35 ms	1944 KB	Output is correct
7	Correct	12 ms	1924 KB	Output is correct
8	Correct	32 ms	1940 KB	Output is correct
9	Correct	109 ms	1944 KB	Output is correct
10	Correct	6 ms	1980 KB	Output is correct
11	Correct	6 ms	1924 KB	Output is correct
12	Correct	2 ms	1924 KB	Output is correct
13	Correct	2 ms	1924 KB	Output is correct
14	Correct	1 ms	1964 KB	Output is correct
15	Correct	3 ms	1924 KB	Output is correct
16	Correct	36 ms	1924 KB	Output is correct
17	Correct	37 ms	1944 KB	Output is correct
18	Correct	12 ms	1924 KB	Output is correct
19	Correct	37 ms	1956 KB	Output is correct
20	Correct	106 ms	2036 KB	Output is correct
21	Correct	8 ms	1924 KB	Output is correct
22	Correct	5 ms	1940 KB	Output is correct
23	Runtime error	66 ms	1920 KB	Execution killed with signal 11
24	Halted	0 ms	0 KB	-

Subtask #6-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	1924 KB	Output is correct
2	Runtime error	5 ms	4032 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #6-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1924 KB	Output is correct
2	Correct	2 ms	1924 KB	Output is correct
3	Correct	1 ms	1964 KB	Output is correct
4	Correct	3 ms	1924 KB	Output is correct
5	Correct	33 ms	1948 KB	Output is correct
6	Correct	35 ms	1944 KB	Output is correct
7	Correct	12 ms	1924 KB	Output is correct
8	Correct	32 ms	1940 KB	Output is correct
9	Correct	109 ms	1944 KB	Output is correct
10	Correct	6 ms	1980 KB	Output is correct
11	Correct	6 ms	1924 KB	Output is correct
12	Correct	2 ms	1924 KB	Output is correct
13	Correct	2 ms	1924 KB	Output is correct
14	Correct	1 ms	1964 KB	Output is correct
15	Correct	3 ms	1924 KB	Output is correct
16	Correct	36 ms	1924 KB	Output is correct
17	Correct	37 ms	1944 KB	Output is correct
18	Correct	12 ms	1924 KB	Output is correct
19	Correct	37 ms	1956 KB	Output is correct
20	Correct	106 ms	2036 KB	Output is correct
21	Correct	8 ms	1924 KB	Output is correct
22	Correct	5 ms	1940 KB	Output is correct
23	Runtime error	66 ms	1920 KB	Execution killed with signal 11
24	Halted	0 ms	0 KB	-

Submission #576219

Compilation message