oj.uz

Submission #1020820

# Submission time Handle Problem Language Result Execution time Memory
1020820 2024-07-12T10:14:30 Z vjudge1 Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 348 KB 
#include "shortcut.h"
#include <bits/stdc++.h>

#define ll long long
// #define int ll
#define pii pair<int,int>
#define F first
#define S second
#define sz(s) (int)s.size()
#define in insert
#define pb push_back
#define all(v) v.begin(),v.end()
#define mem(a,i) memset(a,i,sizeof(a))

using namespace std;

const int MAX=2e5+10;
const ll inf=1e18;

int n;
ll c;
ll d[MAX];
ll pin[MAX];
ll pin1[MAX];

ll get(int l,int r,vector<int> &d){
    // cout<<l<<" "<<r<<"\n";
    ll ans=0;
    {
        ll mx1=-inf;
        for(int i=0;i<=l;i++){
            ans=max(ans,pin[i]+d[i]+mx1);
            mx1=max(mx1,d[i]-pin[i]);
        }
    }
    {
        ll mx1=-inf;
        for(int i=0;i<=l;i++)mx1=max(mx1,pin[l]-pin[i]+d[i]);
        // cout<<mx1<<'\n';
        for(int i=l;i<=r;i++){
            // cout<<i<<" "<<pin[i]-pin[l]<<" "<<pin[r]-pin[i]+c<<" "<<d[i]<<"\n";
            ans=max(ans,mx1+min(pin[i]-pin[l],pin[r]-pin[i]+c)+d[i]);
        }
    }
    {
        ll mx1=-inf;
        for(int i=0;i<=l;i++){
            mx1=max(mx1,pin[l]-pin[i]+d[i]);
        }
        for(int i=r;i<n;i++){
            // cout<<i<<" "<<pin[i]-pin[r]<<" "<<min(c,pin[r]-pin[l])<<" "<<mx1+d[i]<<"\n";
            ans=max(ans,pin[i]-pin[r]+min(c,pin[r]-pin[l])+mx1+d[i]);
        }
    }
    return ans;
}

ll calc(int l,int r,vector<int> &d){
    ll ans=get(l,r,d);
    // cout<<get(l,r,d)<<"\n";
    reverse(all(d));
    for(int i=0;i<n;i++)swap(pin[i],pin1[i]);
    // reverse(pin,pin+n);
    ans=max(ans,get(n-r-1,n-l-1,d));
    // cout<<get(n-r-1,n-l-1,d)<<"\n";
    reverse(all(d));
    for(int i=0;i<n;i++)swap(pin[i],pin1[i]);
    return ans;
}

ll calcmid(int l,int r,vector<int> &d){

    ll ans=0;
    for(int i=l;i<=r;i++){
        for(int j=i+1;j<=r;j++){
            ans=max(ans,min(pin[j]-pin[i],pin[r]-pin[l]+c+pin[i]-pin[j])+d[i]+d[j]);
        }
    }
    return ans;
}

long long find_shortcut(int N, vector<int> l, vector<int> d, int C){
    n=N;
    c=C;
    ll ans=inf;
    for(int i=1;i<n;i++){
        pin[i]=pin[i-1]+l[i-1];
    }

    for(int i=1;i<n;i++){
        pin1[i]=pin1[i-1]+l[n-1-i];
    }
    // return calc(0,3,d);
    for(int i=0;i<n;i++){
        ll mid=-inf,mid1=-inf;
        for(int j=i+1;j<n;j++){
            ll x=calc(i,j,d);
            ans=min(ans,max(x,calcmid(i,j,d)));
        }
    }
    return ans;
}

Compilation message

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:95:12: warning: unused variable 'mid' [-Wunused-variable]
   95 |         ll mid=-inf,mid1=-inf;
      |            ^~~
shortcut.cpp:95:21: warning: unused variable 'mid1' [-Wunused-variable]
   95 |         ll mid=-inf,mid1=-inf;
      |                     ^~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 344 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 348 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 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 344 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 348 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 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 344 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 348 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 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 344 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 348 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 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 344 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 348 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 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 344 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 348 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 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 344 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 348 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 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 1 ms 344 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 348 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -