oj.uz

Submission #64972

# Submission time Handle Problem Language Result Execution time Memory
64972 2018-08-06T10:39:20 Z FedericoS Shortcut (IOI16_shortcut) C++14
0 / 100
 2000 ms 248 KB 
#include "shortcut.h"
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long int ll;

int N;
ll C;
ll L[3005];
ll D[3005];
ll ans=1e18,res;
ll i,j;
ll sin[3005],des[3005];

ll F(ll x, ll y){

    if(x>y)
        swap(x,y);

    ll a=L[y]-L[x];
    ll b=abs(L[x]-L[i])+abs(L[y]-L[j])+C;

    return min(a,b);

}

long long find_shortcut(int N, std::vector<int> l, std::vector<int> d, int C)
{
    //cout<<"Ok";
    for(int x=1;x<N;x++)
        L[x]=L[x-1]+l[x-1];
    for(int x=0;x<N;i++)
        D[x]=d[x];
    for(int x=1;x<N;x++)
        sin[x]=max(sin[x-1],D[x-1])+L[x]-L[x-1];
    for(int x=N-2;x>=0;x--)
        des[x]=max(des[x+1],D[x+1])+L[x+1]-L[x];


    for(i=0;i<N;i++)
        for(j=i+1;j<N;j++){
            //cout<<i<<" "<<j<<endl;
            int y=i;
            res=0;
            for(int x=i;x<=j;x++){
                while(F(x,y)<F(x,y+1) and y<j)
                    y++;
                res=max(res,F(x,y)+D[x]+D[y]);
            }
            for(int x=i;x<=j;x++){
                res=max(res,F(x,sin[i])+D[i]);
                res=max(res,F(x,des[j])+D[i]);
            }
            ans=min(ans,res);
        }

    return ans;

}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2078 ms 248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2078 ms 248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2078 ms 248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2078 ms 248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2078 ms 248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2078 ms 248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2078 ms 248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2078 ms 248 KB Time limit exceeded
2 Halted 0 ms 0 KB -