Submission #137452

# Submission time Handle Problem Language Result Execution time Memory
137452 2019-07-27T18:44:57 Z Runtime_error_ Shortcut (IOI16_shortcut) C++14
Compilation error
0 ms 0 KB
#include "shortcut.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf = 3e3+9 , MX = 1e18+9;
ll c,pre[inf],suf[inf],l[inf],d[inf],sum[inf],premx[inf],sufmx[inf];

ll path(ll x,ll y){
    if(x>y)
        swap(x,y);
    return sum[y-1] - sum[x-1];
}

ll find_shortcut(int n, vector<int> L, vector<int> D, int C){
    c = C;
    ll ret = MX;
    for(ll i=1;i<n;i++)
        l[i] = L[i-1] , d[i] = D[i-1],sum[i] = sum[i-1]+l[i];
    d[n] = D[n-1];

    for(ll i=1;i<=n;i++){
        pre[i] = max(pre[i-1]+l[i-1],d[i]);
        premx[i] = max( premx[i-1] , pre[i-1] +l[i-1] + d[i] );
    }
    for(ll i=n;i>=1;i--){
        suf[i] = max(suf[i+1]+l[i],d[i]);
        sufmx[i] = max( sufmx[i+1] , suf[i+1]+l[i] +d[i] );
    }
    ret = sufmx[1];
    for(ll x=1;x<=n;x++){
        for(ll y=x+1;y<=n;y++){

            ll z = 0,k = 0,diameter = pre[x]+suf[y]+c,mx1 = 0,mx2= 0;
            ll mxsuf[inf]={0},mxpre[inf]={0};

            for( z = x;z<=y && path(z,y)>path(z,x)+c;z++);
            z--;
            for( k = y ; k>=x && path(k,x) > path(k,y)+c;k-- );
            k++;
            for(int )
            for(ll i=x;i<=z;i++)
                diameter = max( diameter , path(i,x)+d[i] +c + suf[y] ),mx1 = max(mx1,path(i,x)+d[i]);

            for(ll i=k ;i<=y;i++)
                diameter = max( diameter , path(i,y)+d[i] +c+pre[x] ),mx2 = max(mx2,path(i,y)+d[i]);
            //diameter = max(diameter,mx1+mx2+c);
            if(z<x)
                z = x;
            if(k>y)
                k = y;
            diameter = max( diameter , premx[k-1] );
            diameter = max( diameter ,sufmx[z+1] );
            /*for(ll i=1;i<k;i++)
                diameter = max(diameter , pre[i]);
             for(ll i=z+1;i<=n;i++)
                diameter = max(diameter , suf[i]);*/

            multiset<int> s;
            int l=x;
            for(int i=x;i<=y;i++){
                while(l<i && path(l,i)>path(i,y)+path(x,l)+c)
                    s.erase(s.find(-pre[l-1]+d[l])),l++;
                if(!s.empty())
                    diameter = max(diameter , *s.rbegin()+sum[i-1]+d[i]);
                s.insert(-pre[i-1]+d[i]);
            }

            //cout<<x<<" "<<y<<" "<<z<<" "<<k<<""<<diameter<<endl;
            ret = min( ret , diameter );
        }
    }
    return ret;
}

Compilation message

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:40:21: error: expected unqualified-id before ')' token
             for(int )
                     ^
shortcut.cpp:40:21: error: expected ';' before ')' token
shortcut.cpp:40:21: error: expected primary-expression before ')' token
shortcut.cpp:40:21: error: expected ';' before ')' token
shortcut.cpp:34:16: warning: unused variable 'mxsuf' [-Wunused-variable]
             ll mxsuf[inf]={0},mxpre[inf]={0};
                ^~~~~
shortcut.cpp:34:31: warning: unused variable 'mxpre' [-Wunused-variable]
             ll mxsuf[inf]={0},mxpre[inf]={0};
                               ^~~~~