oj.uz

Submission #64978

# Submission time Handle Problem Language Result Execution time Memory
64978 2018-08-06T10:53:54 Z FedericoS Shortcut (IOI16_shortcut) C++14
0 / 100
 3 ms 376 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)
{

    C=c;

    for(int x=1;x<N;x++)
        L[x]=L[x-1]+l[x-1];
    for(int x=0;x<N;x++)
        D[x]=d[x];

    for(int x=1;x<N;x++)
        if(F(x-1,sin[x-1])+D[sin[x-1]]<D[x])
            sin[x]=x;
        else
            sin[x]=sin[x-1];

    des[N-1]=N-1;
    for(int x=N-2;x>=0;x--)
        if(F(x+1,des[x+1])+D[des[x+1]]<D[x])
            des[x]=x;
        else
            des[x]=des[x+1];

    /*for(int i=0;i<N;i++)
        cout<<sin[i]<<" ";
    cout<<endl;
    for(int i=0;i<N;i++)
        cout<<des[i]<<" ";
    cout<<endl;*/

    for(i=0;i<N;i++)
        for(j=i+1;j<N;j++){
            //cout<<i<<" "<<j<<" ";
            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]);
            }
            //cout<<res<<" ";
            for(int x=i;x<=j;x++){
                res=max(res,F(x,sin[i])+D[x]+D[sin[i]]);
                res=max(res,F(x,des[j])+D[x]+D[des[i]]);
            }
            //cout<<res<<endl;
            ans=min(ans,res);
        }

    return ans;

}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Incorrect 3 ms 376 KB n = 9, incorrect answer: jury 110 vs contestant 80
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Incorrect 3 ms 376 KB n = 9, incorrect answer: jury 110 vs contestant 80
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Incorrect 3 ms 376 KB n = 9, incorrect answer: jury 110 vs contestant 80
3 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Incorrect 3 ms 376 KB n = 9, incorrect answer: jury 110 vs contestant 80
3 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Incorrect 3 ms 376 KB n = 9, incorrect answer: jury 110 vs contestant 80
3 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Incorrect 3 ms 376 KB n = 9, incorrect answer: jury 110 vs contestant 80
3 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Incorrect 3 ms 376 KB n = 9, incorrect answer: jury 110 vs contestant 80
3 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Incorrect 3 ms 376 KB n = 9, incorrect answer: jury 110 vs contestant 80
3 Halted 0 ms 0 KB -