제출 #784915

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

shortcut

#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()
vector<long long> pref(MAXN+1,0);
vector<int> D;
pair<long long,long long> tree[4*MAXN];
void build(int node,int l,int r){
    if(l==r){
        tree[node].F=pref[l]+D[l];
        tree[node].S=l;
        return;
    }
    int mid=(l+r)/2;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    tree[node].F=max(tree[node<<1].F,tree[node<<1|1].F);
    if(tree[node].F==tree[node<<1].F) tree[node].S=tree[node<<1].S;
    else tree[node].S=tree[node<<1|1].S;
}
int query(int node,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
        return tree[node].S;
    }
    int mid=(l+r)/2;
    int ans=0;
    int index=0;
    if(ql<=mid) {
        int x=query(node<<1,l,mid,ql,qr);
        if(pref[x]+D[x]>ans) {
            ans=pref[x]+D[x];
            index=x;
        }
    }
    if(qr>mid){
        int x=query(node<<1|1,mid+1,r,ql,qr);
        if(pref[x]+D[x]>ans) {
            ans=pref[x]+D[x];
            index=x;
        }
    }
    return index;
 
}
long long find_shortcut(int n, vector<int> l, vector<int> d, int c)
{
    D=d;
    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];
    }
    for(long long i=0;i<n-1;i++){
        pref[i+1]=pref[i]+l[i];
    }
    build(1,0,n-1);
    vector<long long> left(MAXN+1,0);
    vector<long long> right(MAXN+1,0);
    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]);
    }
    long long diameter=left[first_node]+right[first_node];
    for(long long i=0;i<=n-1;i++){
        for(long long j=i+1;j<=n-1;j++){
            long long express=left[i]+c+right[j];
            long long newdiameter=0;
            for(long long k=0;k<=n-1;k++){
                
                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])
                    )
                });
 
            }
            for(long long k=n-1;k>=0;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])
                    )
                });
            }
            long long ans=0;
            for(int x=i+1;x<j;x++){
                int y=query(1,0,n-1,x,j-1);
                ans=max(ans,pref[y]-pref[x]+d[y]+d[x]);
            }
 
            diameter=min({max({ans,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;
// }

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

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:71:15: warning: variable 'last_node' set but not used [-Wunused-but-set-variable]
   71 |     long long last_node=n-1;
      |               ^~~~~~~~~

• 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