oj.uz

Submission #784726

# Submission time Handle Problem Language Result Execution time Memory
784726 2023-07-16T12:59:45 Z YassirSalama Shortcut (IOI16_shortcut) C++14
0 / 100
 1 ms 340 KB 
#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=5100;
const ll INF=1e9+10;
#define dbg(x) cout<<" [ "<<#x<<" ] : "<<x<<endl;
#define F first
#define S second
#define all(v) v.begin(),v.end()
long long find_shortcut(int n, vector<int> l, vector<int> d, int c)
{
    vector<int> pref(MAXN+1,0);
    for(int i=0;i<n-1;i++){
        pref[i+1]=pref[i]+l[i];
    }
    vector<int> left(MAXN+1,0);
    vector<int> right(MAXN+1,0);
    //the idea is to use pref[i-1]+l[i] or d[i]
    left[0]=d[0];
    int first_node=0;
    for(int i=1;i<n;i++){
        if(d[i]>left[i-1]+l[i-1]) first_node=i;
        left[i]=max(left[i-1]+l[i-1],d[i]);
    }
    int last_node=n-1;
    right[n-1]=d[n-1];
    for(int i=n-2;i>=0;i--){
        if(d[i]>right[i+1]+l[i]) last_node=i;
        right[i]=max(right[i+1]+l[i],d[i]);
    }
    vector<int> nodes;//nodes in the diameter
    // cout<<first_node<<" "<<last_node<<endl;
    int diameter=left[first_node]+right[first_node];
    // cout<<diameter<<endl;
    for(int i=first_node;i<=last_node;i++){
        for(int j=i+1;j<=last_node;j++){
            int express=left[i]+c+right[j];
            int newdiameter=0;
            for(int k=0;k<=j;k++){
                newdiameter=max(newdiameter,abs(pref[j]-pref[k])+right[j]);
            }
            for(int k=n-1;k>=i;k--){
                newdiameter=max(newdiameter,abs(pref[k]-pref[i])+left[i]);
            }
            // if(i==0&&j==7){
                // cout<<pref[j]-
            // }
            // cout<<newdiameter<<" "<<express<<" "<<i<<" "<<j<<endl;
            if(newdiameter>express) continue;
            diameter=min({express,diameter});
        }
    }
    // cout<<c<<endl;
    return diameter;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 7.0

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

Subtask #5
0 / 33.0

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

Subtask #6
0 / 22.0

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

Subtask #7
0 / 4.0

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

Subtask #8
0 / 3.0

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