Submission #18960

#	Time	Username	Problem	Language	Result	Execution time	Memory
18960		hjk0553	막대기 (KOI13_game)	C++98	100 / 100	76 ms	6064 KiB

game

#include<bits/stdc++.h>
#define N 111111
struct d{
    int t,d;
} data[N];
bool compare(const d &a,const d &b){
    if(a.t==b.t) return a.d<b.d;
    return a.t<b.t;
}
long long dt1[N],dt2[N],a1[N],a2[N];
int main(){
    int n,l,i;
    long long ans=0;
    scanf("%d %d",&n,&l);
    for(i=1;i<=n;i++) scanf("%d %d",&data[i].t,&data[i].d);
    std::sort(data+1,data+1+n,compare);
    for(i=1;i<=n;i++) a1[i]=data[i].t,a2[i]=data[i].d;
    std::sort(a2+1,a2+1+n);
    int cnt1=std::unique(a1+1,a1+1+n)-a1,cnt2=std::unique(a2+1,a2+1+n)-a2;
    for(i=1;i<=n;i++){
        int idx1=std::lower_bound(a1+1,a1+cnt1+1,data[i].t)-a1;
        long long t=dt1[idx1];
        int idx2=std::lower_bound(a2+1,a2+cnt2+1,data[i].d)-a2;
        dt1[idx1]=std::max(dt1[idx1],l+std::abs(data[i].t-data[i].d)+dt2[idx2]);
        dt2[idx2]=std::max(dt2[idx2],l+std::abs(data[i].t-data[i].d)+t);
    }
    for(i=1;i<=n;i++) ans=std::max(ans,std::max(dt1[i],dt2[i]));
    printf("%lld",ans);
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 22 / 22
• Subtask 5: 38 / 38