| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 71788 |
2018-08-25T15:56:38 Z |
KLPP |
Shortcut (IOI16_shortcut) |
C++14 |
|
0 ms |
0 KB |
#include "shortcut.h"
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef long long int lld;
typedef pair<int,long long int> pii;
vector<pii>nei[1000000];
lld max(lld x, lld y){
if(x<y)return y;
return x;
}
lld min(lld x, lld y){
if(x>y)return y;
return x;
}
class ST{
lld maximo[100000];
int n;
public:
void build(int a, int b, int node){
maximo[node]=0;
if(a==b)return;
int mid=(a+b)/2;
build(a,mid,2*node);
build(mid+1,b,2*node+1);
}
void init(int N){
n=N;
build(0,n-1,1);
}
void update(int pos, lld val,int a, int b, int node){
if(pos<a || pos>b)return;
if(a==b){
maximo[node]=val;
return;
}
int mid=(a+b)/2;
update(pos,val,a,mid,2*node);
update(pos,val,mid+1,b,2*node+1);
maximo[node]=max(maximo[2*node],maximo[2*node+1]);
}
void set(int pos,lld val){
update(pos,val,0,n-1,1);
}
lld query(){
return maximo[1];
}
};
lld positive(lld values[],lld distances[],int n){
int pnt=0;
lld dist=0;
lld sum=0;
lld DP[n];
DP[0]=0;
for(int i=0;i<n-1;i++)DP[i+1]=DP[i]+distances[i];
for(int i=0;i<n;i++)sum+=distances[i];
//cout<<sum<<endl;
ST *s=new ST();
s->init(n);
lld ans=0;
for(int i=0;i<n;i++){
while(pnt<n && 2*(dist+distances[pnt])<=sum){
dist+=distances[pnt];
pnt++;
if(pnt<n)s->set(pnt,DP[pnt]+values[pnt]);
}//cout<<i<<" "<<pnt<<" "<<dist<<endl;
s->set(i,0);
ans=max(ans,s->query()-DP[i]+values[i]);
ans=max(ans,values[i]);
dist-=distances[i];
}
return ans;
}
lld negative(lld values[],lld distances[],int n){
int pnt=0;
lld dist=0;
lld sum=0;
lld DP[n];
DP[0]=0;
for(int i=0;i<n-1;i++)DP[i+1]=DP[i]+distances[i];
for(int i=0;i<n;i++)sum+=distances[i];
//cout<<sum<<endl;
//for(int i=0;i<n;i++)cout<<distances[i]<<" "<<values[i]<<endl;
ST *s=new ST();
s->init(n);
for(int i=0;i<n;i++)s->set(i,sum-DP[i]+values[i]);
lld ans=0;//cout<<endl;
for(int i=0;i<n;i++){
while(pnt<n && 2*dist<=sum){s->set(pnt,0);
dist+=distances[pnt];
pnt++;
}//cout<<i<<" "<<pnt<<" "<<dist<<endl;
//s->set(i,0);
if(pnt<n)ans=max(ans,s->query()+DP[i]+values[i]);
ans=max(ans,values[i]);
dist-=distances[i];
//cout<<values[i]<<" ";
}//cout<<endl<<endl;
return ans;
}
long long find_shortcut(int n, int l[], int d[], int c)
{
lld ans=1000000000000000;
lld left[n];
left[0]=d[0];
for(int i=1;i<n;i++){
left[i]=left[i-1];
lld dist=0;
for(int j=i-1;j>-1;j--){
dist+=l[j];
left[i]=max(left[i],dist+d[j]+d[i]);
}
//cout<<left[i]<<" ";
}//cout<<endl;
lld right[n];
right[n-1]=d[n-1];
for(int i=n-2;i>-1;i--){
right[i]=right[i+1];
lld dist=0;
for(int j=i;j<n-1;j++){
dist+=l[j];
right[i]=max(right[i],dist+d[j+1]+d[i]);
}
//cout<<right[i]<<" ";
}//cout<<endl;
/*
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
lld values[j-i+1];
lld distances[j-i+1];
int size=j-i+1;
for(int h=0;h<j-i;h++){
distances[h]=l[i+h];
}
distances[j-i]=c;
for(int h=i+1;h<j;h++){
values[h-i]=d[h];
}
lld dist=0;
values[0]=d[i];
for(int h=i-1;h>-1;h--){
dist+=l[h];
values[0]=max(values[0],dist+d[h]);
}
values[j-i]=d[j];
dist=0;
for(int h=j;h<n-1;h++){
dist+=l[h];
values[j-i]=max(values[j-i],dist+d[h+1]);
}
lld r=positive(values,distances,size);
//cout<<i<<" A "<<j<<" "<<r<<endl;
r=max(r,negative(values,distances,size));
//cout<<i<<" B "<<j<<" "<<r<<endl;
//cout<<values[0]<<" "<<values[j-i]<<endl;
r=max(r,left[i]);
r=max(r,right[j]);
//cout<<max(left[i],right[j])<<endl;
ans=min(ans,r);
}
}*/
return ans;
}
Compilation message
/tmp/ccZRQ6RN.o: In function `main':
grader.cpp:(.text.startup+0x10d): 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
