제출 #1020820

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1020820		vjudge1	Shortcut (IOI16_shortcut)	C++17	0 / 100	1 ms	348 KiB

shortcut

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3