#include <iostream>
#include <vector>
using namespace std;
vector <long long> dist[2], maxd[2]; //1 asking from the right, i.e. int the left direction, 0 asking from the left
int N;
vector<int> l, d;
int c;
int dst(int a, int b){
return dist[1][b]-dist[1][a];
}
long long find_shortcut(int n, vector<int> l_c, vector<int> d_c, int c_c){
N = n;
l = l_c;
d = d_c;
c = c_c;
dist[0].assign(N+1, 0);
maxd[0] = maxd[1] = dist[0];
dist[1] = dist[0];
dist[0][0] = dist[1][N-1] = 0;
maxd[0][0] = d[0];
maxd[1][N-1] = d[N-1];
for(int x=1; x<N; x++){
dist[0][x] = dist[0][x-1]+l[x-1];
maxd[0][x] = max(maxd[0][x-1]+l[x-1], (long long)d[x]);
}
for(int x = N-2; x>=0; x--){
dist[1][x] = dist[1][x+1]+l[x];
maxd[1][x] = max(maxd[1][x+1]+l[x], (long long)d[x]);
}
long long a = 0;
for(int x=0; x<N; x++){
a = max(a, maxd[0][x]+maxd[1][x]);
cout << dist[0][x] << " " << dist[1][x] << endl;
cout << maxd[0][x] << " " << maxd[1][x] << endl;
}
for(int x=0; x<N-1; x++){
for(int y=x+1; y<N; y++){
//count the maxdist if we put a node between x and y
long long nmxd = c+maxd[1][y]+maxd[0][x];
if(nmxd<a)
cout << x << " " << y << endl;
for(int z=x+1; z<y; z++){
nmxd = max(nmxd, (long long)min(dst(z, y), dst(x, z)+c));
nmxd = max(nmxd, (long long)min(dst(z, y)+c, dst(x, z)));
for(int z1 = z+1; z1<y; z1++){
nmxd = max(nmxd, (long long)d[z]+d[z1]+min(dst(z, z1), dst(x, z)+c+dst(z1, y)));
}
}
if(nmxd<a)
cout << x << " " << y << " " << nmxd << endl;
a = min(a, nmxd);
}
}
return a;
}
int main(){
vector<int> l = {10, 20, 20}, d = {0, 40, 0, 30};
cout << find_shortcut(4, l, d, 10) << endl;
}
Compilation message
/tmp/ccmja9uq.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccvu0urw.o:shortcut.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
