#include "shortcut.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define all( x ) x.begin(), x.end()
#define umin( x, y ) x = min( x, (y) )
#define umax( x, y ) x = max( x, (y) )
#define pb push_back
using namespace std;
typedef long long Lint;
typedef pair<int,Lint> ii;
const int inf = 1e9 + 137;
const int maxn = 200020;
Lint pre[maxn], suf[maxn], x[maxn];
ii st1[maxn];
int at1, al1;
ii st2[maxn];
int at2, al2;
int c;
Lint calc( vector<ii> &v ) {
if( v.size() == 3 ) {
for(int i=0;i<v.size();i++)
printf("-- %d %d\n",v[i].fi,v[i].se);
}
Lint tot = v[v.size()-1].fi-v[0].fi+c;
Lint ret = 0;
at1 = 0, al1 = 1;
at2 = 0, al2 = 1;
for(int i=0,j=0;i<v.size()*2;i++) {
ii t = v[i%v.size()];
if( i >= v.size() ) t.fi += tot;
while( j < i && j < v.size() && t.fi-v[j].fi > tot/2 ) {
if( st1[al1].fi == j ) al1++;
if( st2[al2].fi == j ) al2++;
j++;
}
if( j >= v.size() ) break;
if( al1 <= at1 ) {
//printf("asd %d %d --> %d\n",j,i,st1[al1].se + t.se+t.fi);
umax( ret, st1[al1].se + t.se+t.fi );
}
while( at1>=al1 && st1[at1].se <= t.se-t.fi ) at1--; st1[++at1] = ii( i, t.se-t.fi );
while( at2>=al2 && st2[at2].se <= t.se+t.fi ) at2--; st2[++at2] = ii( i, t.se+t.fi );
}
return ret;
}
long long find_shortcut(int n, vector<int> l, vector<int> d, int C)
{
c = C;
x[0] = 0;
for(int i=1;i<n;i++)
x[i] = x[i-1]+l[i-1];
for(int i=0;i<n;i++) {
if( i == 0 ) pre[i] = d[i];
else pre[i] = max( pre[i-1]+l[i-1], (Lint)d[i] );
}
for(int i=n-1;i>=0;i--) {
if( i == n-1 ) suf[i] = d[i];
else suf[i] = max( suf[i+1]+l[i], (Lint)d[i] );
}
Lint ans = 1e18 + 5;
for(int i=0;i<n;i++) {
vector<ii> v;
v.pb( ii( x[i], pre[i] ) );
for(int j=i+1;j<n;j++) {
v.pb( ii( x[j], suf[j] ) );
umin( ans, calc( v ) );
//printf("Asd %d %d --> %lld\n",i,j,ans);
if( i == 0 && j == 2 ) return ans;
v[v.size()-1].se = d[j];
}
}
return ans;
}
Compilation message
shortcut.cpp: In function 'Lint calc(std::vector<std::pair<int, long long int> >&)':
shortcut.cpp:27:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v.size();i++)
^
shortcut.cpp:28:44: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
printf("-- %d %d\n",v[i].fi,v[i].se);
^
shortcut.cpp:34:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0,j=0;i<v.size()*2;i++) {
^
shortcut.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if( i >= v.size() ) t.fi += tot;
^
shortcut.cpp:38:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while( j < i && j < v.size() && t.fi-v[j].fi > tot/2 ) {
^
shortcut.cpp:43:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if( j >= v.size() ) break;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
12956 KB |
Secret is incorrect! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
12956 KB |
Secret is incorrect! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
12956 KB |
Secret is incorrect! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
12956 KB |
Secret is incorrect! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
12956 KB |
Secret is incorrect! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
12956 KB |
Secret is incorrect! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
12956 KB |
Secret is incorrect! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
12956 KB |
Secret is incorrect! |
| 2 |
Halted |
0 ms |
0 KB |
- |
