#include <bits/stdc++.h>
//#include "closing.h"
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
const int N = 2e5 + 5;
ll p[N], q[N], jog[N];
int n;
int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
n = N;
// for (int i = 0; i < N - 1; ++i) {
// v[U[i]].pb ({V[i], W[i]});
// v[V[i]].pb ({U[i], W[i]});
// }
// return 1;
ll sum = 0;
for (int i = X + 1; i < N; ++i) {
//
sum += W[i - 1];
p[i] = sum + p[i - 1];
}
sum = 0;
for (int i = X - 1; i >= 0; i--) {
sum += W[i];
p[i] = sum + p[i + 1];
}
sum = 0;
for (int i = Y + 1; i < N; ++i) {
//
sum += W[i - 1];
q[i] = sum + q[i - 1];
}
sum = 0;
for (int i = Y - 1; i >= 0; i--) {
sum += W[i];
q[i] = sum + q[i + 1];
}
// exit(0);
for (int i = 0; i < n; ++i) {
jog[i] = max (q[i], p[i]);
}
// for (int i = 0; i < n; ++i) {
// cout << p[i] << " ";
// }
// cout << "\n";
// for (int i = 0; i < n; ++i) {
// cout << q[i] << " ";
// }
// cout << "\n";
// for (int i = 0; i < n; ++i) {
// cout << jog[i] << " ";
// }
// exit(0);
for (int i = 1; i < n; ++i) {
jog[i] += jog[i - 1];
}
int ret = 0;
for (int i = 0; i <= X; ++i) {
for (int j = X; j < n; ++j) {
for (int l = 0; l <= Y; ++l) {
for (int r = Y; r < n; ++r) {
// i-dan j-cenli
// l-dan r-cenli
ll val = 0;
if (j < l) {
val = p[i] + p[j] + q[l] + q[r];
}
else {
int res = max (l, i), res1 = min (r, j);
val = jog[res1];
if (res != 0) val -= jog[res - 1];
val += p[i] + p[j] + q[l] + q[r];
ll ayyr = 0;
if (X <= res) {
ayyr += p[res1];
if (res > X) ayyr -= p[res - 1];
}
else {
ayyr += p[res1];
ayyr += p[res];
}
ll ayyr1 = 0;
if (Y >= res1) {
ayyr1 += q[res];
if (res1 < Y) ayyr1 -= q[res1 + 1];
}
else {
ayyr1 += q[res1];
ayyr1 += q[res];
}
val -= (ayyr + ayyr1);
// if (i == 0 and j == 1 and l == 1 and r == 3) {
//// cout << val << " " << res << " " << res1;
// cout << val << " " << ayyr << " " << ayyr1;
////// cout << p[i] << " " << p[j] << " " << q[l] << " " << q[r];
//// cout << val;
// exit(0);
// }
}
// if (i == 0 and j == 1 and l == 1 and r == 3) {
//// cout << val << " " << res << " " << res1;
//// cout << p[i] << " " << p[j] << " " << q[l] << " " << q[r];
// cout << val;
// exit(0);
// }
if (val <= K) {
ret = max (ret, (X - i + 1) + (j - X) + (Y - l + 1) + (r - Y));
}
// if (ret == 4) {
// cout << i << " " << j << " " << l << " " << r << " " << val << " " << K << "\n";
// exit(0);
// }
}
}
}
}
for (int i = 0; i < n; ++i) {
p[i] = q[i] = jog[i] = 0;
}
return ret;
}
//int main() {
// freopen ("input.txt", "r", stdin);
//
//// cout << max_score(7, 0, 2, 10, [0, 0, 1, 2, 2, 5], [1, 3, 2, 4, 5, 6], [2, 3, 4, 2, 5, 3]);
//
// int Q;
// assert(1 == scanf("%d", &Q));
//
// std::vector<int> N(Q), X(Q), Y(Q);
// std::vector<long long> d, K(Q);
// std::vector<std::vector<int>> U(Q), V(Q), W(Q);
//
// for (int q = 0; q < Q; q++)
// {
// assert(4 == scanf("%d %d %d %lld", &N[q], &X[q], &Y[q], &K[q]));
//
// U[q].resize(N[q] - 1);
// V[q].resize(N[q] - 1);
// W[q].resize(N[q] - 1);
// for (int i = 0; i < N[q] - 1; ++i)
// {
// assert(3 == scanf("%d %d %d", &U[q][i], &V[q][i], &W[q][i]));
// }
// }
// fclose(stdin);
//
// std::vector<int> result(Q);
// for (int q = 0; q < Q; q++)
// {
// result[q] = max_score(N[q], X[q], Y[q], K[q], U[q], V[q], W[q]);
// }
//
// for (int q = 0; q < Q; q++)
// {
// printf("%d\n", result[q]);
// }
// fclose(stdout);
//
// return 0;
//}
/*
2
7 0 2 10
0 1 2
0 3 3
1 2 4
2 4 2
2 5 5
5 6 3
4 0 3 20
0 1 18
1 2 1
2 3 19
answer : 6 3
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 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 |
Execution timed out |
1051 ms |
13136 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
344 KB |
1st lines differ - on the 1st token, expected: '30', found: '22' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
344 KB |
1st lines differ - on the 1st token, expected: '30', found: '22' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
344 KB |
1st lines differ - on the 1st token, expected: '30', found: '22' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 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 |
0 ms |
348 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 |
0 ms |
348 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 |
0 ms |
348 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 |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
