#include "closing.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define NN (2 << 12)
int n, x, y;
ll k;
pair<ll, int> tree[2 * NN];
ll pt[3][NN];
void st(int k, pair<ll, int> x) {
k += NN;
tree[k] = x;
for (k /= 2; k >= 1; k /= 2) {
tree[k] = {tree[2 * k].first + tree[2 * k + 1].first, tree[2 * k].second + tree[2 * k + 1].second};
}
}
pair<ll, int> sum(int a, int b) {
a += NN;
b += NN;
pair<ll, int> ans = {0, 0};
while (a <= b) {
if (a % 2 == 1) {
ans.first += tree[a].first;
ans.second += tree[a].second;
a++;
}
if (b % 2 == 0) {
ans.first += tree[b].first;
ans.second += tree[b].second;
b--;
}
a /= 2; b /= 2;
}
return ans;
}
ll gt(int i, int a, int b) {
ll ans = pt[i][b];
if (a != 0) ans -= pt[i][a - 1];
return ans;
}
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
n = N;
x = X;
y = Y;
k = K;
pt[0][x] = 0;
for (int i = x - 1; i >= 0; --i) {
pt[0][i] = W[i] + pt[0][i + 1];
}
for (int i = x + 1; i < n; ++i) {
pt[0][i] = W[i - 1] + pt[0][i - 1];
}
pt[1][y] = 0;
for (int i = y - 1; i >= 0; --i) {
pt[1][i] = W[i] + pt[1][i + 1];
}
for (int i = y + 1; i < n; ++i) {
pt[1][i] = W[i - 1] + pt[1][i - 1];
}
pt[2][0] = pt[1][0];
for (int i = 1; i < n; ++i) {
pt[2][i] = pt[2][i - 1] + max(pt[0][i], pt[1][i]);
pt[1][i] += pt[1][i - 1];
pt[0][i] += pt[0][i - 1];
}
/*for (int i = 0; i < 3; ++i) {
for (int j = 0; j < n; ++j) {
cout << pt[i][j] << " ";
}
cout << endl;
}*/
vector<pair<ll, int>> comb;
for (int i = 0; i < x; ++i) {
comb.push_back({gt(0, i, i), i});
}
for (int i = y + 1; i < n; ++i) {
comb.push_back({gt(1, i, i), i});
}
sort(comb.begin(), comb.end());
map<int, int> pos_to_idx;
int idx = 0;
for (auto [val, x] : comb) {
pos_to_idx[x] = idx;
// cout << "idx: " << idx << " id: " << x << " = " << val << endl;
st(idx++, {val, 1});
}
int idx_tot = idx;
int best = 0;
for (int ar = x; ar < n; ++ar) {
if (ar > y) {
st(pos_to_idx[ar], {0, 0});
}
vector<pair<int, ll>> rst;
for (int bl = y; bl >= 0; --bl) {
ll cur = 0;
int ans = 0;
if (bl <= ar) {
cur += gt(2, bl, ar);
ans += 2 * (ar - bl + 1);
}
// [a, bl-1]
int tmp = min(bl - 1, ar);
if (x <= tmp) {
cur += gt(0, x, tmp);
ans += (tmp) - x + 1;
}
// [ar + 1, b]
tmp = max(ar + 1, bl);
if (tmp <= y) {
cur += gt(1, tmp, y);
ans += y - tmp + 1;
}
// too large
if (cur > k) break;
ll left = k - cur;
if (bl < x) {
int tr_i = pos_to_idx[bl];
rst.push_back({tr_i, sum(tr_i, tr_i).first});
st(tr_i, {0, 0});
}
// cout << "ar: " << ar << " bl: " << bl << " cur: " << cur << " k: " << k << " ans: " << ans << endl;
int tk = 0;
while (tk < idx_tot && left >= sum(tk, tk).first) {
left -= sum(tk, tk).first;
ans += sum(tk, tk).second;
// cout << left << ", " << tk << " " << sum(tk, tk).first << " " << sum(tk, tk).second << endl;
tk++;
}
/*int li = min(bl - 1, x - 1);
int ri = max(ar + 1, y + 1);
while (true) {
ll small = k;
int use = 0;
if (li >= 0) {
small = gt(0, li, li);
use = 1;
}
if (ri < n && gt(1, ri, ri) < small) {
small = gt(1, ri, ri);
use = 2;
}
if (use == 0 || left < small) break;
if (use == 1) li--;
if (use == 2) ri++;
left -= small;
ans++;
}*/
best = max(best, ans);
}
for (auto [idx, val] : rst) {
st(idx, {val, 1});
}
}
return best;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
46 ms |
10828 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
256 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
256 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
3 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
104 ms |
396 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
194 ms |
356 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
212 KB |
Output is correct |
| 24 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
256 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
3 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
104 ms |
396 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
194 ms |
356 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
212 KB |
Output is correct |
| 24 |
Correct |
1 ms |
212 KB |
Output is correct |
| 25 |
Correct |
16 ms |
340 KB |
Output is correct |
| 26 |
Execution timed out |
1048 ms |
724 KB |
Time limit exceeded |
| 27 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
