oj.uz

Submission #660245

# Submission time Handle Problem Language Result Execution time Memory
660245 2022-11-21T10:03:17 Z prarie Bali Sculptures (APIO15_sculpture) C++17
0 / 100
 186 ms 31820 KB 
#include <bits/stdc++.h>
 
#define fastio ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define fi first
#define se second
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define compress(v) sort(all(v)), (v).erase(unique(all((v))), v.end())
#define pb push_back
#define eb emplace_back
 
using namespace std;
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ld = long double;
 
template <typename T>
inline void Mx(T &x, T y) { x < y && (x = y); }
template <typename T>
inline void Mn(T &x, T y) { x > y && (x = y); }

int x[2005], y[2005];
int dp[2005][2005];
int pref[2005][2005];

int main() {
	fastio;
	int N, A, B;
	cin >> N >> A >> B;
	vector<int> Y(N);
	for (auto &y : Y) {
		cin >> y;
	}

	auto check = [&](ll p, ll q) -> bool {
		memset(x, -1, sizeof x);
		memset(y, -1, sizeof y);
		ll s1 = 0, s2 = 0;
		for (int i = 0, u = 0, v = 0; i < N; i++) {
			s1 += Y[i];
			s2 += Y[i];
			while (u < i && s1 > q) {
				s1 -= Y[u++];
			}
			while (v < i && s2 - Y[v] >= p) {
				s2 -= Y[v++];
			}

			if (p <= s1 && s1 <= q) {
				x[i] = u;
			}
			if (p <= s2 && s2 <= q) {
				y[i] = v;
			}
		}

		memset(dp, 0, sizeof dp);
		memset(pref, 0, sizeof pref);
		pref[0][0] = 1;
		for (int i = 0; i < N; i++) {
			for (int j = 1; j <= B; j++) {
				if (x[i] == -1 || y[i] == -1) {
					assert(x[i] == -1 && y[i] == -1);
					break;
				}

				if (pref[y[i]][j - 1] - (x[i] == 0 ? 0 : pref[x[i] - 1][j - 1])) {
					dp[i][j] = 1;
				}
			}
			for (int j = 0; j <= B; j++) {
				pref[i + 1][j] = pref[i][j] + dp[i][j];
			}
		}

		for (int i = A; i <= B; i++) {
			if (dp[N - 1][i]) {
				return true;
			}
		}
		return false;
	};


	ll ans = 0;
	for (int b = 50; b >= 0; b--) {
		ll p = ans, q = ans | ((1LL << b) - 1);
		if (!check(p, q)) {
			ans |= (1LL << b);
		}
		
	}

	cout << ans << endl;
	return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 31792 KB Output is correct
2 Incorrect 174 ms 31784 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 31820 KB Output is correct
2 Incorrect 172 ms 31784 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 31792 KB Output is correct
2 Incorrect 173 ms 31700 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 31756 KB Output is correct
2 Incorrect 184 ms 31700 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 31800 KB Output is correct
2 Incorrect 174 ms 31784 KB Output isn't correct
3 Halted 0 ms 0 KB -