oj.uz

Submission #784853

# Submission time Handle Problem Language Result Execution time Memory
784853 2023-07-16T15:32:02 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)
{
    if(n==2){
        if(c<l[0])
            return (long long)d[0]+c+(long long)d[1];
        return (ll)d[0]+(ll)l[0]+(ll)d[1];
    }
    vector<long long> pref(MAXN+1,0);
    for(long long i=0;i<n-1;i++){
        pref[i+1]=pref[i]+l[i];
    }
    vector<long long> left(MAXN+1,0);
    vector<long long> right(MAXN+1,0);
    //the idea is to use pref[i-1]+l[i] or d[i]
    left[0]=(ll)d[0];
    long long first_node=0;
    for(long long 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],(ll)d[i]);
    }
    long long last_node=n-1;
    right[n-1]=d[n-1];
    for(long long i=n-2;i>=0;i--){
        if(d[i]>right[i+1]+l[i]&&i!=first_node) last_node=i;
        right[i]=max(right[i+1]+l[i],(ll)d[i]);
    }
    vector<long long> nodes;//nodes in the diameter
    // cout<<first_node<<" "<<last_node<<endl;
    for(int i=0;i<n;i++){
        // cout<<i<<"  -->> "<<" "<<pref[i]<<endl;
    }
    long long diameter=left[first_node]+right[first_node];
    for(long long i=first_node;i<=last_node;i++){
        for(long long j=i+1;j<=last_node;j++){
            long long express=left[i]+c+right[j];
            long long newdiameter=0;
            for(long long k=0;k<=n-1;k++){
                //last diameter or the sum of values mabin j nd k+ max in right of the j.
                // Hna we add a new case that is using teleporter o passing mn left dial k
                // So here it's like right[j]+c... Hna wsslna l i
                //then we add depth mabin i and j
                
                newdiameter=max({newdiameter,
                    min(
                        (ll)abs(pref[j]-pref[k])+right[j]+(d[k]==right[j]&&k==j?0LL:d[k]) ,
                        (ll)right[j]+(ll)c+(ll)abs(pref[i]-pref[k])+(d[k]==right[j]&&k==j?0LL:d[k])
                    )
                });

            }
            // dbg(newdiameter);
            for(long long k=n-1;k>=0;k--){
                //hna we check like wach kayn wa7d diameter starting mn dak left[i] tal k
                newdiameter=max({newdiameter,
                    min(
                        (ll)abs(pref[k]-pref[i])+left[i]+(d[k]==left[i]&&k==i?0:d[k]),
                        (ll)left[i]+c+abs(pref[j]-pref[k])+(d[k]==left[i]&&k==i?0:d[k])
                    )
                });
                // if(newdiameter==38) {
                //     dbg(i);
                //     dbg(j);
                //     dbg((ll)abs(pref[k]-pref[i])+left[i]+d[k]);
                //     dbg((ll)left[i]+c+abs(pref[j]-pref[k])+d[k]);
                // }
            }
            // dbg(left[1]);
            // dbg(pref[1]);
            // if(i==0&&j==7){
                // cout<<pref[j]-
            // }
            // cout<<first_node<<" "<<last_node<<endl;
            // cout<<newdiameter<<" "<<express<<" "<<i<<" "<<j<<endl;
            // if(newdiameter>express) continue;
            // if(last_node-first_node==1||j-i==1) continue;
            diameter=min({max(newdiameter,(ll)express),(ll)diameter}); 
        }
    }
    // cout<<c<<endl;
    return diameter;
}

// int main()
// {
//     int n, c;
//     assert(2 == scanf("%d%d", &n, &c));
    
//     std::vector<int> l(n - 1);
//     std::vector<int> d(n);
//     for (int i = 0; i < n - 1; i++)
//         assert(1 == scanf("%d", &l[i]));
//     for (int i = 0; i < n; i++)
//         assert(1 == scanf("%d", &d[i]));
        
//     long long t = find_shortcut(n, l, d, c);
    
    
//     printf("%lld\n", t);
    
//     return 0;
// }

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 0 ms 340 KB n = 9, 110 is a correct answer
3 Correct 0 ms 340 KB n = 4, 21 is a correct answer
4 Correct 0 ms 340 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 340 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 340 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 340 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 340 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 340 KB n = 5, 4000000000 is a correct answer
17 Incorrect 0 ms 340 KB n = 10, incorrect answer: jury 1000000343 vs contestant 2000000000
18 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 0 ms 340 KB n = 9, 110 is a correct answer
3 Correct 0 ms 340 KB n = 4, 21 is a correct answer
4 Correct 0 ms 340 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 340 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 340 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 340 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 340 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 340 KB n = 5, 4000000000 is a correct answer
17 Incorrect 0 ms 340 KB n = 10, incorrect answer: jury 1000000343 vs contestant 2000000000
18 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 0 ms 340 KB n = 9, 110 is a correct answer
3 Correct 0 ms 340 KB n = 4, 21 is a correct answer
4 Correct 0 ms 340 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 340 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 340 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 340 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 340 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 340 KB n = 5, 4000000000 is a correct answer
17 Incorrect 0 ms 340 KB n = 10, incorrect answer: jury 1000000343 vs contestant 2000000000
18 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 0 ms 340 KB n = 9, 110 is a correct answer
3 Correct 0 ms 340 KB n = 4, 21 is a correct answer
4 Correct 0 ms 340 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 340 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 340 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 340 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 340 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 340 KB n = 5, 4000000000 is a correct answer
17 Incorrect 0 ms 340 KB n = 10, incorrect answer: jury 1000000343 vs contestant 2000000000
18 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 0 ms 340 KB n = 9, 110 is a correct answer
3 Correct 0 ms 340 KB n = 4, 21 is a correct answer
4 Correct 0 ms 340 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 340 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 340 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 340 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 340 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 340 KB n = 5, 4000000000 is a correct answer
17 Incorrect 0 ms 340 KB n = 10, incorrect answer: jury 1000000343 vs contestant 2000000000
18 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 0 ms 340 KB n = 9, 110 is a correct answer
3 Correct 0 ms 340 KB n = 4, 21 is a correct answer
4 Correct 0 ms 340 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 340 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 340 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 340 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 340 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 340 KB n = 5, 4000000000 is a correct answer
17 Incorrect 0 ms 340 KB n = 10, incorrect answer: jury 1000000343 vs contestant 2000000000
18 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 0 ms 340 KB n = 9, 110 is a correct answer
3 Correct 0 ms 340 KB n = 4, 21 is a correct answer
4 Correct 0 ms 340 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 340 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 340 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 340 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 340 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 340 KB n = 5, 4000000000 is a correct answer
17 Incorrect 0 ms 340 KB n = 10, incorrect answer: jury 1000000343 vs contestant 2000000000
18 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 0 ms 340 KB n = 9, 110 is a correct answer
3 Correct 0 ms 340 KB n = 4, 21 is a correct answer
4 Correct 0 ms 340 KB n = 3, 4 is a correct answer
5 Correct 0 ms 212 KB n = 2, 62 is a correct answer
6 Correct 1 ms 212 KB n = 2, 3 is a correct answer
7 Correct 0 ms 340 KB n = 3, 29 is a correct answer
8 Correct 0 ms 212 KB n = 2, 3 is a correct answer
9 Correct 0 ms 212 KB n = 2, 3 is a correct answer
10 Correct 0 ms 212 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 212 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 340 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 340 KB n = 3, 3000000000 is a correct answer
14 Correct 1 ms 340 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 340 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 340 KB n = 5, 4000000000 is a correct answer
17 Incorrect 0 ms 340 KB n = 10, incorrect answer: jury 1000000343 vs contestant 2000000000
18 Halted 0 ms 0 KB -