Submission #4950

#	Time	Username	Problem	Language	Result	Execution time	Memory
4950		hana5505	막대기 (KOI13_game)	C++98	100 / 100	92 ms	6248 KiB

game

#include<stdio.h>
#include<algorithm>
using namespace std;
struct pp{
    int x,y;
}ar[110001];
int xy[220001];
long long ans1[220001]={0,},an;//위
long long ans2[220001]={0,};//아래
bool cmp(struct pp a,struct pp b){
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}
long long mx(long long a,long long b){
    if(a<b) return b;
    return a;
}
long long ab(long long k){
    if(k<0) return -k;
    return k;
}
int main()
{
    int n,l,i,j;
    long long kx,ky;
 
    scanf("%d %d",&n,&l);
    for(i=1;i<=n;i++){
        scanf("%d %d",&ar[i].x,&ar[i].y);
        xy[i*2-1]=ar[i].x;
        xy[i*2]=ar[i].y;
    }
    sort(xy+1,xy+2*n+1);
 
    for(i=1;i<=n;i++){
        j=lower_bound(xy+1,xy+2*n+1,ar[i].x)-xy;
        ar[i].x=j;
        j=lower_bound(xy+1,xy+2*n+1,ar[i].y)-xy;
        ar[i].y=j;
    }
 
    sort(ar+1,ar+n+1,cmp);
 
    for(i=1;i<=n;i++){
        kx=ans1[ar[i].x];
        ky=ans2[ar[i].y];
        ans1[ar[i].x]=mx(ky+ab(xy[ar[i].x]-xy[ar[i].y])+l,ans1[ar[i].x]);
        ans2[ar[i].y]=mx(kx+ab(xy[ar[i].x]-xy[ar[i].y])+l,ans2[ar[i].y]);
    }
 
    for(i=1;i<=2*n;i++){
        an=mx(an,mx(ans1[i],ans2[i]));
    }
 
    printf("%lld",an);
}

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