#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
vector<long long> val;
vector<long long> maxL, maxR;
vector<long long> dist;
vector<long long> D;
int N;
long long cost;
struct maxQueue{
deque<pair<long long, int> > d;
long long soma;
int ini, fim;
maxQueue(){
soma = 0;
ini = 0, fim = -1;
}
void push(long long val){
while(!d.empty() && d.back().first <= val - soma) d.pop_back();
d.push_back(make_pair(val - soma, ++fim));
}
void pop(){
if(!d.empty() && ini == d.front().second) d.pop_front();
ini++;
}
long long getMax(){
if(d.empty()) return 0;
return d.front().first + soma;
}
void add(long long val){
soma += val;
}
};
long long getLen(int id, int ini, int fim){
if(id > fim) id = ini;
if(id == ini) return cost;
return dist[id] - dist[id - 1];
}
long long test(int ini, int fim){
val[ini] = maxL[ini];
val[fim] = maxR[fim];
long long diam = 0;
if(ini != 0) diam = max(diam, maxL[ini - 1] + dist[ini] - dist[ini - 1] + D[ini]);
if(fim != N - 1) diam = max(diam, maxR[fim + 1] + dist[fim + 1] - dist[fim] + D[fim]);
long long sum = 0;
long long tam = dist[fim] - dist[ini] + cost;
int it = ini;
maxQueue fila;
fila.push(val[ini]);
for(int i = ini + 1; i < fim; i++){
fila.add(getLen(i, ini, fim));
sum += getLen(i, ini, fim);
val[i] = D[i];
fila.push(val[i]);
}
fila.add(getLen(fim, ini, fim));
sum += getLen(fim, ini, fim);
while(2 * sum > tam){
fila.pop();
it++;
if(it > fim) it = ini;
sum -= getLen(it, ini, fim);
}
diam = max(diam, val[fim] + fila.getMax());
fila.push(val[fim]);
for(int i = ini; i < fim; i++){
fila.add(getLen(i, ini, fim));
sum += getLen(i, ini, fim);
while(2 * sum > tam){
fila.pop();
it++;
if(it > fim) it = ini;
sum -= getLen(it, ini, fim);
}
diam = max(diam, val[i] + fila.getMax());
fila.push(val[i]);
}
maxQueue fila2;
it = fim;
sum = 0;
fila2.push(val[fim]);
for(int i = fim - 1; i > ini; i--){
fila2.add(getLen(i + 1, ini, fim));
sum += getLen(i + 1, ini, fim);
fila2.push(val[i]);
}
fila2.add(getLen(ini + 1, ini, fim));
sum += getLen(ini + 1, ini, fim);
while(2 * sum > tam){
fila2.pop();
sum -= getLen(it, ini, fim);
it--;
if(it < ini) it = fim;
}
diam = max(diam, val[ini] + fila2.getMax());
fila2.push(val[ini]);
for(int i = fim; i > ini; i--){
fila2.add(getLen(i + 1, ini, fim));
sum += getLen(i + 1, ini, fim);
while(2 * sum > tam){
fila2.pop();
sum -= getLen(it, ini, fim);
it--;
if(it < ini) it = fim;
}
diam = max(diam, val[i] + fila2.getMax());
fila2.push(val[i]);
}
return diam;
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
cost = c;
N = n;
dist = vector<long long> (n);
val = vector<long long> (n);
maxL = vector<long long> (n);
maxR = vector<long long> (n);
D = vector<long long> (n);
dist[0] = 0;
long long len = 0;
maxL[0] = d[0];
D[0] = d[0];
for(int i = 1; i < n; i++){
dist[i] = dist[i - 1] + l[i - 1];
maxL[i] = max((long long)d[i], maxL[i - 1] + l[i - 1]);
D[i] = d[i];
}
maxR[n - 1] = d[n - 1];
for(int i = n - 2; i >= 0; i--){
maxR[i] = max((long long)d[i], maxR[i + 1] + l[i]);
}
len = dist[n - 1];
long long maxi = 0;
int ini = 0;
for(int i = 0; i < n; i++)
if(d[i] + dist[i] > maxi) maxi = d[i] + dist[i], ini = i;
maxi = 0;
int fim = 0;
for(int i = 0; i < ini; i++)
if(dist[ini] - dist[i] + d[ini] + d[i] > maxi) maxi = dist[ini] - dist[i] + d[ini] + d[i], fim = i;
for(int i = ini + 1; i < n; i++)
if(dist[i] - dist[ini] + d[ini] + d[i] > maxi) maxi = dist[i] - dist[ini] + d[ini] + d[i], fim = i;
if(ini > fim) swap(ini, fim);
long long ans = maxi;
// int j = ini + 1;
// for(int i = ini; i < fim; i++){
// j = max(j, i + 1);
// while(1){
// long long aux = test(i, j);
// ans = min(ans, aux);
// if(j == fim || aux > maxL[i] + maxR[j] + cost) break;
// j++;
// }
// }
for(int i = 0; i <= fim; i++)
for(int j = min(ini, i + 1); j < n; j++)
ans = min(ans, test(i, j));
return ans;
}
Compilation message
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:137:12: warning: variable 'len' set but not used [-Wunused-but-set-variable]
137 | long long len = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
n = 4, incorrect answer: jury 80 vs contestant 60 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
n = 4, incorrect answer: jury 80 vs contestant 60 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
n = 4, incorrect answer: jury 80 vs contestant 60 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
n = 4, incorrect answer: jury 80 vs contestant 60 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
n = 4, incorrect answer: jury 80 vs contestant 60 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
n = 4, incorrect answer: jury 80 vs contestant 60 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
n = 4, incorrect answer: jury 80 vs contestant 60 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
n = 4, incorrect answer: jury 80 vs contestant 60 |
| 2 |
Halted |
0 ms |
0 KB |
- |
