#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=5100;
const ll INF=1e9+10;
#define dbg(x) cout<<"[ "<<#x<<" ] : "<<x<<endl;
#define F first
#define S second
#define all(v) v.begin(),v.end()
long long find_shortcut(int n, vector<int> l, vector<int> d, int c)
{
if(n==2){
if(c<l[0])
return (long long)d[0]+c+(long long)d[1];
return (ll)d[0]+(ll)l[0]+(ll)d[1];
}
vector<long long> pref(MAXN+1,0);
for(long long i=0;i<n-1;i++){
pref[i+1]=pref[i]+l[i];
}
vector<long long> left(MAXN+1,0);
vector<long long> right(MAXN+1,0);
// vector<bool> used_left(MAXN+1,false);
// vector<bool> used_right(MAXN+1,false);
//the idea is to use pref[i-1]+l[i] or d[i]
left[0]=(ll)d[0];
long long first_node=0;
for(long long i=1;i<n;i++){
if(d[i]>left[i-1]+l[i-1]) first_node=i;
left[i]=max(left[i-1]+l[i-1],(ll)d[i]);
}
long long last_node=n-1;
right[n-1]=d[n-1];
for(long long i=n-2;i>=0;i--){
if(d[i]>right[i+1]+l[i]&&i!=first_node) last_node=i;
right[i]=max(right[i+1]+l[i],(ll)d[i]);
}
// used_left[first_node]=true;
vector<long long> nodes;//nodes in the diameter
// cout<<first_node<<" "<<last_node<<endl;
for(int i=0;i<n;i++){
// cout<<i<<" -->> "<<" "<<pref[i]<<endl;
}
long long diameter=left[first_node]+right[first_node];
for(long long i=0;i<=n-1;i++){
for(long long j=i+1;j<=n-1;j++){
long long express=left[i]+c+right[j];
long long newdiameter=0;
for(long long k=0;k<=n-1;k++){
//last diameter or the sum of values mabin j nd k+ max in right of the j.
// Hna we add a new case that is using teleporter o passing mn left dial k
// So here it's like right[j]+c... Hna wsslna l i
//then we add depth mabin i and j
newdiameter=max({newdiameter,
min(
(ll)abs(pref[j]-pref[k])+right[j]+(d[k]==right[j]&&k==j?0LL:d[k]) ,
(ll)right[j]+(ll)c+(ll)abs(pref[i]-pref[k])+(d[k]==right[j]&&k==j?0LL:d[k])
)
});
}
// dbg(newdiameter);
for(long long k=n-1;k>=0;k--){
//hna we check like wach kayn wa7d diameter starting mn dak left[i] tal k
newdiameter=max({newdiameter,
min(
(ll)abs(pref[k]-pref[i])+left[i]+(d[k]==left[i]&&k==i?0:d[k]),
(ll)left[i]+c+abs(pref[j]-pref[k])+(d[k]==left[i]&&k==i?0:d[k])
)
});
// if(newdiameter==38) {
// dbg(i);
// dbg(j);
// dbg((ll)abs(pref[k]-pref[i])+left[i]+d[k]);
// dbg((ll)left[i]+c+abs(pref[j]-pref[k])+d[k]);
// }
}
// dbg(left[1]);
// dbg(pref[1]);
// if(i==0&&j==7){
// cout<<pref[j]-
// }
// cout<<first_node<<" "<<last_node<<endl;
// cout<<newdiameter<<" "<<express<<" "<<i<<" "<<j<<endl;
// if(newdiameter>express) continue;
// if(last_node-first_node==1||j-i==1) continue;
diameter=min({max(newdiameter,(ll)express),(ll)diameter});
}
}
// cout<<c<<endl;
return diameter;
}
// int main()
// {
// int n, c;
// assert(2 == scanf("%d%d", &n, &c));
// std::vector<int> l(n - 1);
// std::vector<int> d(n);
// for (int i = 0; i < n - 1; i++)
// assert(1 == scanf("%d", &l[i]));
// for (int i = 0; i < n; i++)
// assert(1 == scanf("%d", &d[i]));
// long long t = find_shortcut(n, l, d, c);
// printf("%lld\n", t);
// return 0;
// }
Compilation message
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:34:15: warning: variable 'last_node' set but not used [-Wunused-but-set-variable]
34 | long long last_node=n-1;
| ^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
0 ms |
340 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
1 ms |
340 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
0 ms |
340 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
1 ms |
340 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
0 ms |
340 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
1 ms |
340 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
0 ms |
340 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
1 ms |
340 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
0 ms |
340 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
1 ms |
340 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
0 ms |
340 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
1 ms |
340 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
0 ms |
340 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
1 ms |
340 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
0 ms |
340 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
1 ms |
340 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
| 4 |
Halted |
0 ms |
0 KB |
- |
