oj.uz

Submission #592205

# Submission time Handle Problem Language Result Execution time Memory
592205 2022-07-08T18:31:34 Z tutis Uplifting Excursion (BOI22_vault) C++17
0 / 100
 74 ms 1584 KB 
/*input
1 5
0 0 6

*/

#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);
const int mxdel = 40000;
ll A_[2 * 300 + 1];
ll ej[2][2 * mxdel + 1];
ll sum[300 + 2];
ld C_[2 * 300 + 1];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int M;
	ll L;
	cin >> M >> L;
	ll* A = A_ + M;
	for (ll i = -M; i <= M; i++)
		cin >> A[i];
	L = -L;
	ll cnt = 0;
	for (ll l = -M; l <= M; l++)
	{
		L += l * A[l];
		cnt += A[l];
	}
	A[0] = 0;
	ld L_ = L;
	ld* C = C_ + M;
	C[0] = 0;
	for (ll x = M; x >= 1; x--)
	{
		for (ll v : {x, -x})
		{
			C[v] = L_ / v;
			C[v] = max(ld(0), C[v]);
			C[v] = min(ld(A[v]), C[v]);
			L_ -= C[v] * v;
		}
		sum[x] = (ll)roundl(L_);
	}
	sum[0] = 0;
	sum[M + 1] = L;
	ll infi = 2e18;
	for (ll b = 0; b <= 2 * mxdel; b++)
		ej[(M + 1) % 2][b] = infi;
	ej[(M + 1) % 2][0 + mxdel] = 0;
	int mxdelt = 5;
	for (int x = M; x >= 0; x--)
	{
		int x1 = (x + 1) % 2;
		int x0 = x % 2;
		for (int b = 0; b <= 2 * mxdel; b++)
			ej[x0][b] = infi;
		for (int a = -mxdel; a <= mxdel; a++)
		{
			ll val = sum[x + 1] + a - sum[x];
			ll e = ej[x1][a + mxdel];
			if (e != infi)
				for (ll v : {x, -x})
				{
					ll opt = 0;
					if (x != 0)
						opt = val / v;
					opt = max(opt, 0ll);
					opt = min(opt, A[v]);
					for (ll k = max(0ll, opt - mxdelt); k <= min(A[v], opt + mxdelt); k++)
					{
						ll val_ = val - k * v;
						ll e_ = e + k;
						if (abs(val_) <= mxdel)
						{
							if (e_ < ej[x0][val_ + mxdel])
							{
								ej[x0][val_ + mxdel] = e_;
							}
						}
					}
				}
		}
	}
	ll best = ej[0][mxdel];
	if (best != infi)
		cout << cnt - best << "\n";
	else
		cout << "impossible\n";
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 2 ms 1492 KB Output is correct
5 Correct 52 ms 1560 KB Output is correct
6 Correct 19 ms 1492 KB Output is correct
7 Correct 22 ms 1584 KB Output is correct
8 Correct 43 ms 1568 KB Output is correct
9 Correct 74 ms 1572 KB Output is correct
10 Incorrect 5 ms 1492 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 2 ms 1492 KB Output is correct
5 Correct 52 ms 1560 KB Output is correct
6 Correct 19 ms 1492 KB Output is correct
7 Correct 22 ms 1584 KB Output is correct
8 Correct 43 ms 1568 KB Output is correct
9 Correct 74 ms 1572 KB Output is correct
10 Incorrect 5 ms 1492 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 5 ms 1492 KB Output is correct
3 Correct 3 ms 1492 KB Output is correct
4 Correct 6 ms 1580 KB Output is correct
5 Correct 5 ms 1492 KB Output is correct
6 Correct 7 ms 1492 KB Output is correct
7 Incorrect 3 ms 1492 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 5 ms 1492 KB Output is correct
3 Correct 3 ms 1492 KB Output is correct
4 Correct 6 ms 1580 KB Output is correct
5 Correct 5 ms 1492 KB Output is correct
6 Correct 7 ms 1492 KB Output is correct
7 Incorrect 3 ms 1492 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 5 ms 1492 KB Output is correct
3 Correct 3 ms 1492 KB Output is correct
4 Correct 6 ms 1580 KB Output is correct
5 Correct 5 ms 1492 KB Output is correct
6 Correct 7 ms 1492 KB Output is correct
7 Incorrect 3 ms 1492 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 2 ms 1492 KB Output is correct
5 Correct 52 ms 1560 KB Output is correct
6 Correct 19 ms 1492 KB Output is correct
7 Correct 22 ms 1584 KB Output is correct
8 Correct 43 ms 1568 KB Output is correct
9 Correct 74 ms 1572 KB Output is correct
10 Incorrect 5 ms 1492 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 5 ms 1492 KB Output is correct
3 Correct 3 ms 1492 KB Output is correct
4 Correct 6 ms 1580 KB Output is correct
5 Correct 5 ms 1492 KB Output is correct
6 Correct 7 ms 1492 KB Output is correct
7 Incorrect 3 ms 1492 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 2 ms 1492 KB Output is correct
5 Correct 52 ms 1560 KB Output is correct
6 Correct 19 ms 1492 KB Output is correct
7 Correct 22 ms 1584 KB Output is correct
8 Correct 43 ms 1568 KB Output is correct
9 Correct 74 ms 1572 KB Output is correct
10 Incorrect 5 ms 1492 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 5 ms 1492 KB Output is correct
3 Correct 3 ms 1492 KB Output is correct
4 Correct 6 ms 1580 KB Output is correct
5 Correct 5 ms 1492 KB Output is correct
6 Correct 7 ms 1492 KB Output is correct
7 Incorrect 3 ms 1492 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 2 ms 1492 KB Output is correct
5 Correct 52 ms 1560 KB Output is correct
6 Correct 19 ms 1492 KB Output is correct
7 Correct 22 ms 1584 KB Output is correct
8 Correct 43 ms 1568 KB Output is correct
9 Correct 74 ms 1572 KB Output is correct
10 Incorrect 5 ms 1492 KB Output isn't correct
11 Halted 0 ms 0 KB -