#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;
int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W)
{
vector<ll> lft, rgt;
lft.pb(0), rgt.pb(0);
ll sum = 0;
for (int i = X - 1; i >= 0; i--){
sum += W[i];
lft.pb(lft.back() + sum);
}
sum = 0;
for (int i = Y + 1; i < N; i++){
sum += W[i - 1];
rgt.pb(rgt.back() + sum);
}
ll ans = 0;
//todo : no one can reach the other
{
vector<ll> merge(2 * N + 2, INF);
for (ll i = 0; i < lft.size(); i++){
for (ll j = 0; j < rgt.size(); j++)
merge[i + j] = min(merge[i + j], lft[i] + rgt[j]);
}
vector<ll> cost(N, 0);
ll total = 0;
ll GH = 0;
for (ll i = X; i <= Y; i++){
if (i > X) {
GH += W[i - 1];
cost[i] = GH;
total += cost[i];;
}
ll sum = total;
ll GH2 = 0;
for (ll j = Y; j >= X; j--){
if (j < Y) {
GH2 += W[j];
sum += max((ll)0, GH2 - cost[j]);
}
ll pos = upper_bound(merge.begin(), merge.end(), K - sum) - merge.begin();
if (sum <= K) ans = max(ans, pos + i - X + Y - j + 1);
}
}
}
//todo : X can reach Y
{
vector<ll> merge(2 * N + 2, INF);
for (ll i = 0; i < lft.size(); i++){
for (ll j = 0; j < rgt.size(); j++)
merge[i + j] = min(merge[i + j * 2], lft[i] + rgt[j]);
}
vector<ll> cost(N, 0);
ll total = 0, GH = 0;;
for (ll i = X + 1; i <= Y; i++){
GH += W[i - 1];
cost[i] = GH;
total += cost[i];
}
ll GH2 = 0;
for (ll i = Y; i >= X; i--){
if (i < Y) {
GH2 += W[i];
total += max((ll)0, GH2 - cost[i]);
}
ll pos = upper_bound(merge.begin(), merge.end(), K - total) - merge.begin();
if (total <= K) ans = max(ans, pos + Y - X + Y - i + 1);
}
}
//todo : Y can reach X
{
vector<ll> merge(2 * N + 2, INF);
for (ll i = 0; i < lft.size(); i++){
for (ll j = 0; j < rgt.size(); j++)
merge[i + j] = min(merge[i * 2 + j], lft[i] + rgt[j]);
}
vector<ll> cost(N, 0);
ll total = 0, GH = 0;
for (ll i = Y - 1; i >= X; i--){
GH += W[i];
cost[i] = GH;
total += cost[i];
}
ll GH2 = 0;
for (ll i = X; i <= Y; i++){
if (i > X) {
GH2 += W[i - 1];
total += max((ll)0, GH2 - cost[i - 1]);
}
ll pos = upper_bound(merge.begin(), merge.end(), K - total) - merge.begin();
if (total <= K) ans = max(ans, pos + Y - X + i - X + 1);
}
}
//todo : both can reach each other
{
vector<ll> merge(2 * N + 2, INF);
for (ll i = 0; i < lft.size(); i++){
for (ll j = 0; j < rgt.size(); j++)
merge[i + j] = min(merge[i * 2 + j * 2], lft[i] + rgt[j]);
}
vector<ll> cost(N, 0);
ll total = 0, GH = 0;
for (ll i = Y - 1; i >= X; i--){
GH += W[i];
cost[i] = GH;
total += cost[i];
}
ll GH2 = 0;
for (ll i = X; i <= Y; i++){
if (i > X) {
GH2 += W[i - 1];
total += max((ll)0, GH2 - cost[i - 1]);
}
}
ll pos = upper_bound(merge.begin(), merge.end(), K - total) - merge.begin();
if (total <= K) ans = max(ans, pos + Y - X + Y - X + 1);
}
return ans;
}
/*
int main()
{
fileio();
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:41:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for (ll i = 0; i < lft.size(); i++){
| ~~^~~~~~~~~~~~
closing.cpp:42:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (ll j = 0; j < rgt.size(); j++)
| ~~^~~~~~~~~~~~
closing.cpp:72:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for (ll i = 0; i < lft.size(); i++){
| ~~^~~~~~~~~~~~
closing.cpp:73:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (ll j = 0; j < rgt.size(); j++)
| ~~^~~~~~~~~~~~
closing.cpp:102:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for (ll i = 0; i < lft.size(); i++){
| ~~^~~~~~~~~~~~
closing.cpp:103:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for (ll j = 0; j < rgt.size(); j++)
| ~~^~~~~~~~~~~~
closing.cpp:132:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for (ll i = 0; i < lft.size(); i++){
| ~~^~~~~~~~~~~~
closing.cpp:133:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for (ll j = 0; j < rgt.size(); j++)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1024 ms |
9536 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
