#include "shortcut.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
using vi = vector<int>;
using ll = long long;
using ii = pair<int, int>;
ll find_shortcut(int n, vi l, vi d, int c) {
vector<ll> sl;
for(int i = 0; i < n - 1; ++i) {
sl.push_back(l[i]);
if(i) sl[i] += sl[i - 1];
}
auto dist_direct = [&](int u, int v) {
if(u == v) return 0ll;
if(u > v) swap(u, v);
if(!v) return 0ll;
if(u) return sl[v - 1] - sl[ u - 1 ];
else return sl[v - 1];
};
vector<vector<ll> > DD(n, vector(n, 0ll));
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j) DD[i][j] = dist_direct(i, j);
auto dist = [&](int u, int v, int st, int dr) { /// (st, dr) express line
ll re = DD[u][v];
re = min(re, DD[u][st] + DD[dr][v] + c);
re = min(re, DD[u][dr] + DD[st][v] + c);
return re + d[u] + d[v];
};
ll reg = 1e18;
map<ii, ll> M;
vector<ll> DPST(n, 0), DPDR(n, 0);
for(int i = 1; i < n; ++i) {
DPST[i] = DPST[i - 1];
for(int j = 0; j < i; ++j)
DPST[i] = max(DPST[i], DD[i][j] + d[i] + d[j]);
}
for(int i = n - 1; i >= 0; --i) {
if(i + 1 < n)
DPDR[i] = DPDR[i + 1];
for(int j = i + 1; j < n; ++j)
DPDR[i] = max(DPDR[i], DD[i][j] + d[i] + d[j]);
}
int nrap = 0;
auto simu = [&](int st, int dr) {
++nrap;
ll cre = dist(st, dr, st, dr);
///pt st
ll ma1 = -1e9, ma2 = -1e9;
for(int i = 0; i < st; ++i) ma1 = max(ma1, dist(i, st, st, dr));
for(int i = st + 1; i < n; ++i) ma2 = max(ma2, dist(i, st, st, dr));
cre = max(cre, ma1 + ma2 - 2 * d[st]);
cre = max(cre, max(ma1, ma2));
///pt dr
ma1 = -1e9, ma2 = -1e9;
for(int i = 0; i < dr; ++i) ma1 = max(ma1, dist(i, dr, st, dr));
for(int i = dr + 1; i < n; ++i) ma2 = max(ma2, dist(i, dr, st, dr));
cre = max(cre, ma1 + ma2 - 2 * d[dr]);
cre = max(cre, max(ma1, ma2));
cre = max(cre, DPST[st]);
cre = max(cre, DPDR[dr]);
for(int i = st; i <= dr; ++i)
for(int j = i + 1; j <= dr; ++j)
cre = max(dist(i, j, st, dr), cre);
return cre;
};
const int CBULAN = 50;
map<int, ll> CST;
auto cost_st = [&](int st) {
if(CST.count(st)) return CST[st];
ll re = 1e18;
int l = st + 1, r = n - 1;
while(l + CBULAN < r) {
int m1 = (2 * l + r) / 3, m2 = (2 * r + l) / 3;
auto c1 = simu(st, m1);
auto c2 = simu(st, m2);
re = min(re, c1);
re = min(re, c2);
if(c1 == c2) {
auto r1 = simu(st, r);
re = min(r1, re);
--r;
continue;
}
if(c1 > c2) {
l = m1;
} else r = m2;
}
for(int dr = l; dr <= r; ++dr) {
auto cre = simu(st, dr);
re = min(re, cre);
}
CST[st] = re;
return re;
};
int st = 0, dr = n - 1;
while(st + CBULAN < dr) {
int m1 = (2 * st + dr) / 3, m2 = (st + 2 * dr) / 3;
auto c1 = cost_st(m1);
auto c2 = cost_st(m2);
reg = min(reg, c1);
reg = min(reg, c2);
if(c1 == c2) {
auto c3 = cost_st(dr);
reg = min(reg, c3);
--dr;
continue;
} else {
if(c1 > c2) {
st = m1;
} else
dr = m2;
}
if(nrap > 1e6) break
}
for(int i = st; i <= dr; ++i)
reg = min(reg, cost_st(i));
return reg;
}
Compilation message
shortcut.cpp: In function 'll find_shortcut(int, vi, vi, int)':
shortcut.cpp:127:29: error: expected ';' before '}' token
127 | if(nrap > 1e6) break
| ^
| ;
128 | }
| ~
