#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
const int INF=0x3f3f3f3f;
const int N=3e5+5;
ll sum[N];
ll pref[N], suff[N];
ll until[N], later[N];
#define DEBUG 0
long long find_shortcut(int n, vector<ll> l, vector<ll> d, ll c) {
l.insert(l.begin(), 0);
sum[0]=0;
for (int i=1; i<n; ++i) sum[i]=sum[i-1]+l[i];
pref[0]=d[0];
until[0]=d[0];
for (int i=1; i<n; ++i) {
until[i]=max(until[i-1]+l[i], (ll)d[i]);
pref[i]=max(pref[i-1], until[i-1]+d[i]+l[i]);
}
suff[n-1]=d[n-1];
later[n-1]=d[n-1];
for (int i=n-2; i>=0; --i) {
later[i]=max(later[i+1]+l[i+1], (ll)d[i]);
suff[i]=max(suff[i+1], later[i+1]+d[i]+l[i+1]);
}
ll najv=-1;
int lef=-1, rig=-1;
for (int i=0; i<n; ++i) {
for (int j=i+1; j<n; ++j) {
ll curr=sum[j]-sum[i]+d[i]+d[j];
if (curr>najv || (curr==najv && j-i<rig-lef)) najv=curr, lef=i, rig=j;
}
}
#if DEBUG
printf("until: ");
for (int i=0; i<n; ++i) printf("%lld ", until[i]);
printf("\npref: ");
for (int i=0; i<n; ++i) printf("%lld ", pref[i]);
printf("\nlater: ");
for (int i=0; i<n; ++i) printf("%lld ", later[i]);
printf("\nsuff: ");
for (int i=0; i<n; ++i) printf("%lld ", suff[i]);
printf("\n\n");
#endif // DEBUG
ll sol=pref[n-1];
for (int i=lef; i<rig; ++i) {
for (int j=i+1; j<=rig; ++j) {
if (sum[j]-sum[i]<=c) continue;
ll maxi=max(pref[i], suff[j]);
maxi=max(maxi, until[i]+later[j]+c);
#if DEBUG
printf("i: %d, j: %d, maxi: %lld\n", i, j, maxi);
#endif
for (int k=i+1; k<j; ++k) {
ll curr1=min(sum[j]-sum[k]+d[k]+c+until[i], d[k]+sum[k]-sum[i]+until[i]);
maxi=max(maxi, curr1);
ll curr2=min(sum[k]-sum[i]+d[k]+c+later[j], d[k]+sum[j]-sum[k]+later[j]);
maxi=max(maxi, curr2);
#if DEBUG
printf("k: %d, prvo: %lld, drugo: %lld\n", k, curr1, curr2);
#endif // DEBUG
}
#if DEBUG
printf("ukupno ==================== %lld\n\n", maxi);
#endif
sol=min(sol, maxi);
}
}
return sol;
}
Compilation message
/tmp/ccAmC8DC.o: In function `main':
grader.cpp:(.text.startup+0x124): undefined reference to `find_shortcut(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int)'
collect2: error: ld returned 1 exit status
