Submission #592105

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
592105	2022-07-08T13:49:32 Z	tutis	Uplifting Excursion (BOI22_vault)	C++17	5 / 100	5000 ms	524288 KB

vault

/*input
2 5
2 3 1 1 4

*/

#pragma GCC optimize ("O3")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T,  null_type,  less<T>,  rb_tree_tag,  tree_order_statistics_node_update>;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
mt19937_64 rng(0);
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int M;
	ll L;
	cin >> M >> L;
	ll A_[2 * M + 1];
	ll* A = A_ + M;
	for (int i = -M; i <= M; i++)
		cin >> A[i];
	ll pl = 0;
	pl += A[0];
	A[0] = 0;
	L = -L;
	ll cnt = 0;
	for (int l = -M; l <= M; l++)
	{
		L += l * A[l];
		cnt += A[l];
	}
	cc_hash_table<ll, ll>D;
	D[0] = 0;
	ll del = M;
	A[0] = 1;
	for (int v = M; v >= 1; v--)
	{
		cc_hash_table<ll, ll>D_;
		for (int l : {v, -v})
		{
			for (pair<ll, ll>v : D)
			{
				ll k = (L - v.first) / l;
				k = max(k, 0ll);
				k = min(k, A[l]);
				ll lo = max(0ll, k - del);
				ll hi = min(k + del, A[l]);
				if (abs(L - (v.first + k * l)) < abs(l) && A[L - (v.first + k * l)] > 0)
				{
					ll v_ = v.first + l * k;
					ll c_ = v.second + k;
					auto it = D_.find(v_);
					if (it == D_.end())
						D_[v_] = c_;
					else
						it->second = min(it->second, c_);
				}
				else
					for (ll c = lo; c <= hi; c++)
					{
						ll v_ = v.first + l * c;
						ll c_ = v.second + c;
						auto it = D_.find(v_);
						if (it == D_.end())
							D_[v_] = c_;
						else
							it->second = min(it->second, c_);
					}
			}
		}
		D = D_;
	}
	if (D.find(L) != D.end())
		cout << pl + cnt - D[L] << "\n";
	else
		cout << "impossible\n";
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	968 ms	9412 KB	Output is correct
6	Correct	988 ms	14824 KB	Output is correct
7	Correct	256 ms	4540 KB	Output is correct
8	Correct	809 ms	8896 KB	Output is correct
9	Correct	2750 ms	17444 KB	Output is correct
10	Correct	20 ms	772 KB	Output is correct
11	Correct	23 ms	852 KB	Output is correct

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	968 ms	9412 KB	Output is correct
6	Correct	988 ms	14824 KB	Output is correct
7	Correct	256 ms	4540 KB	Output is correct
8	Correct	809 ms	8896 KB	Output is correct
9	Correct	2750 ms	17444 KB	Output is correct
10	Correct	20 ms	772 KB	Output is correct
11	Correct	23 ms	852 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1018 ms	9548 KB	Output is correct
17	Correct	978 ms	14724 KB	Output is correct
18	Correct	245 ms	4520 KB	Output is correct
19	Correct	793 ms	8892 KB	Output is correct
20	Correct	2665 ms	17472 KB	Output is correct
21	Correct	19 ms	772 KB	Output is correct
22	Correct	24 ms	852 KB	Output is correct
23	Execution timed out	5063 ms	63740 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-

Subtask #3-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	6 ms	468 KB	Output is correct
3	Correct	11 ms	780 KB	Output is correct
4	Runtime error	2859 ms	524288 KB	Execution killed with signal 9
5	Halted	0 ms	0 KB	-

Subtask #3-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	6 ms	468 KB	Output is correct
3	Correct	11 ms	780 KB	Output is correct
4	Runtime error	2859 ms	524288 KB	Execution killed with signal 9
5	Halted	0 ms	0 KB	-

Subtask #4-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	6 ms	468 KB	Output is correct
3	Correct	11 ms	780 KB	Output is correct
4	Runtime error	2859 ms	524288 KB	Execution killed with signal 9
5	Halted	0 ms	0 KB	-

Subtask #4-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	968 ms	9412 KB	Output is correct
6	Correct	988 ms	14824 KB	Output is correct
7	Correct	256 ms	4540 KB	Output is correct
8	Correct	809 ms	8896 KB	Output is correct
9	Correct	2750 ms	17444 KB	Output is correct
10	Correct	20 ms	772 KB	Output is correct
11	Correct	23 ms	852 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	6 ms	468 KB	Output is correct
14	Correct	11 ms	780 KB	Output is correct
15	Runtime error	2859 ms	524288 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-

Subtask #5-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	6 ms	468 KB	Output is correct
3	Correct	11 ms	780 KB	Output is correct
4	Runtime error	2859 ms	524288 KB	Execution killed with signal 9
5	Halted	0 ms	0 KB	-

Subtask #5-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	968 ms	9412 KB	Output is correct
6	Correct	988 ms	14824 KB	Output is correct
7	Correct	256 ms	4540 KB	Output is correct
8	Correct	809 ms	8896 KB	Output is correct
9	Correct	2750 ms	17444 KB	Output is correct
10	Correct	20 ms	772 KB	Output is correct
11	Correct	23 ms	852 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1018 ms	9548 KB	Output is correct
17	Correct	978 ms	14724 KB	Output is correct
18	Correct	245 ms	4520 KB	Output is correct
19	Correct	793 ms	8892 KB	Output is correct
20	Correct	2665 ms	17472 KB	Output is correct
21	Correct	19 ms	772 KB	Output is correct
22	Correct	24 ms	852 KB	Output is correct
23	Execution timed out	5063 ms	63740 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-

Subtask #6-1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	6 ms	468 KB	Output is correct
3	Correct	11 ms	780 KB	Output is correct
4	Runtime error	2859 ms	524288 KB	Execution killed with signal 9
5	Halted	0 ms	0 KB	-

Subtask #6-2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	968 ms	9412 KB	Output is correct
6	Correct	988 ms	14824 KB	Output is correct
7	Correct	256 ms	4540 KB	Output is correct
8	Correct	809 ms	8896 KB	Output is correct
9	Correct	2750 ms	17444 KB	Output is correct
10	Correct	20 ms	772 KB	Output is correct
11	Correct	23 ms	852 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1018 ms	9548 KB	Output is correct
17	Correct	978 ms	14724 KB	Output is correct
18	Correct	245 ms	4520 KB	Output is correct
19	Correct	793 ms	8892 KB	Output is correct
20	Correct	2665 ms	17472 KB	Output is correct
21	Correct	19 ms	772 KB	Output is correct
22	Correct	24 ms	852 KB	Output is correct
23	Execution timed out	5063 ms	63740 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-

Submission #592105

Compilation message