#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define el '\n'
#define ff first
#define ss second
#define pii pair <ll, ll>
#define pb push_back
#define mkp make_pair
#define fr(i, l, r) for(ll i = l; i <= r; i++)
#define debug(x) \
{ cout << #x << " = " << x << el; }
template<class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template<class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
const ll N = 2e5 + 10;
const ll M = 1e5 + 10;
const ll K = 400;
const ll INF = 1e18 + 10;
const ll inf = 1e9 + 10;
const ll LOG = 20;
const ll mod = 1000002022;
mt19937 rnd(time(0));
/*
1
7 1 4 2000
0 1 1
1 2 4
2 3 2
3 4 1
4 5 3
5 6 2
*/
ll x[N], y[N], pref[N], pref2[N], mnv[N];
int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
if(X > Y) swap(X, Y);
for(int i = X - 1; i >= 0; i--)
x[i] = x[i + 1] + W[i];
for(int i = Y - 1; i >= 0; i--)
y[i] = y[i + 1] + W[i];
for(int i = X + 1; i < N; i++)
x[i] = x[i - 1] + W[i - 1];
for(int i = Y + 1; i < N; i++)
y[i] = y[i - 1] + W[i - 1];
vector <ll> s;
for(int i = 0; i < N; i++) {
ll mn = min(x[i], y[i]);
s.pb(mn);
pref[i] = mn;
pref2[i] = x[i] + y[i] - 2 * mn;
if(i) pref[i] += pref[i - 1];
if(i) pref2[i] += pref2[i - 1];
//cout << i << " " << x[i] << " " << y[i] << el;
}
for(int i = 0; i <= N; i++)
mnv[i] = INF;
for(int L = X + 1; L < Y; L++) {
for(int R = L; R < Y; R++) {
if(x[L - 1] > y[L - 1]) continue;
if(y[R + 1] > x[R + 1]) continue;
ll val = pref2[R] - pref2[L - 1];
ll d = R - L + 1;
chmin(mnv[d], val);
}
}
for(int i = N - 1; i >= 0; i--)
chmin(mnv[i], mnv[i + 1]);
sort(s.begin(), s.end());
ll ans = 0;
ll k2 = K;
for(int i = 0; i < s.size(); i++) {
if(k2 >= s[i]) {
k2 -= s[i];
ans++;
}
}
for(int L = 0; L <= X; L++) {
for(int R = Y; R < N; R++) {
ll k2 = K - pref[R];
if(L) k2 += pref[L - 1];
if(k2 < 0) {
R = N;
continue;
}
ll res = R - L + 1;
ll l = 0, r = N;
while(l < r) {
ll mid = (l + r + 1) / 2;
if(mnv[mid] <= k2) l = mid;
else r = mid - 1;
}
if(l) {
k2 -= mnv[l];
res += l;
}
res += k2 / x[Y];
//cout << L << " " << R << " " << res << el;
chmax(ans, res);
}
}
chmin(ans, 2 * N);
return ans;
}
/*
int main() {
int Q;
assert(1 == scanf("%d", &Q));
std::vector<int> N(Q), X(Q), Y(Q);
std::vector<long long> 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;
}
*/
Compilation message
closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(int i = 0; i < s.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 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 |
365 ms |
14964 KB |
1st lines differ - on the 1st token, expected: '451', found: '371' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
4444 KB |
1st lines differ - on the 1st token, expected: '30', found: '40' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
4444 KB |
1st lines differ - on the 1st token, expected: '30', found: '40' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
4444 KB |
1st lines differ - on the 1st token, expected: '30', found: '40' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 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 |
4444 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 |
4444 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 |
4444 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 |
4444 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
