#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll find_shortcut(int n, vector<int> l, vector<int> d, int c){
ll pathlength[1000000]={0};
pathlength[0]=0;
for (ll i = 1; i<n; i++){
pathlength[i]=pathlength[i-1]+l[i-1];
}
ll prefixmax[1000000]={0};
ll suffixmax[1000000]={0};
prefixmax[0]=pathlength[n-1]-pathlength[0]+d[0];
for (ll i = 1; i<n; i++){
prefixmax[i]=max(prefixmax[i-1],d[i]+pathlength[n-1]-pathlength[i]);
}
for (ll i = 0; i<n; i++){
prefixmax[i]-=pathlength[n-1]-pathlength[i];
}
suffixmax[n-1]=pathlength[n-1]-pathlength[0]+d[n-1];
for (ll i = n-2; i>=0; i--){
suffixmax[i]=max(suffixmax[i+1],d[i]+pathlength[i]-pathlength[0]);
}
for (ll i = 0; i<n; i++){
suffixmax[i]-=pathlength[i]-pathlength[0];
}
ll prefixrangemax[1000000]={0};
ll suffixrangemax[1000000]={0};
for (int i = 1; i<n; i++){
prefixrangemax[i]=prefixrangemax[i-1];
for (int j = 0; j<i; j++){
//from j to i
prefixrangemax[i]=max(prefixrangemax[i],d[i]+d[j]+pathlength[i]-pathlength[j]);
}
}
for (int i = n-2; i>=0; i--){
suffixrangemax[i]=suffixrangemax[i+1];
for (int j = i+1; j<n; j++){
//from j to i
suffixrangemax[i]=max(suffixrangemax[i],d[i]+d[j]+pathlength[j]-pathlength[i]);
}
}
ll endspluspath[1000000]={0};
ll endsminuspath[1000000]={0};
for (ll i = 0; i<n; i++){
endspluspath[i]=d[i]+pathlength[i];
endsminuspath[i]=d[i]-pathlength[i];
}
ll mindist = 1e18;
/*for (int i : prefixmax){
cout<<i<<' ';
}cout<<'\n';
for (int i : suffixmax){
cout<<i<<' ';
}cout<<'\n';*/
for (ll a = 0; a<n-1; a++){
for (ll b = a+1; b<n; b++){
//try express road linking a and b
ll mxdist = max(prefixrangemax[a],suffixrangemax[b]);
//try thing-on-left to thing-on-right
mxdist = max(mxdist,min(ll(c),pathlength[b]-pathlength[a])+suffixmax[b]+prefixmax[a]);
//try thing-on-left to middle, thing-on-right to middle
//segmenttree-ify
for (ll x = a; x<=b; x++){
if (x!=a){
mxdist = max(mxdist,
min(
pathlength[b]-pathlength[x]+c,
pathlength[x]-pathlength[a]
) + prefixmax[a] + d[x]);
}
if (x!=b){
mxdist = max(mxdist,
min(
pathlength[b]-pathlength[x],
pathlength[x]-pathlength[a]+c
) + suffixmax[b] + d[x]);
}
if (mxdist>mindist){break;}
}
if (mxdist>mindist){break;}
//try thing-on-middle to thing-on-middle
for (ll m = a; m<b; m++){
for (ll n = a+1; n<=b; n++){
//from m to n
mxdist = max(mxdist,
min(
c+pathlength[b]-pathlength[n]+pathlength[m]-pathlength[a],
pathlength[n]-pathlength[m]
)+d[n]+d[m]);
if (mxdist>mindist){break;}
}
if (mxdist>mindist){break;}
}
//cout<<a<<' '<<b<<": "<<mxdist<<'\n';
mindist = min(mindist, mxdist);
}
}
return mindist;
}
Compilation message
shortcut.cpp: In function 'll find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:48:5: warning: variable 'endspluspath' set but not used [-Wunused-but-set-variable]
48 | ll endspluspath[1000000]={0};
| ^~~~~~~~~~~~
shortcut.cpp:49:5: warning: variable 'endsminuspath' set but not used [-Wunused-but-set-variable]
49 | ll endsminuspath[1000000]={0};
| ^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
39424 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
39424 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
39424 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
39424 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
39424 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
39424 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
39424 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
39424 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
