# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1082634 | Halym2007 | Closing Time (IOI23_closing) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "closing.h"
#include "grader.cpp"
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;
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];
}
for (int i = 0; i < n; ++i) {
jog[i] = max (q[i], p[i]);
}
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;
}