oj.uz

Submission #4950

# Submission time Handle Problem Language Result Execution time Memory
4950 2014-01-23T13:19:29 Z hana5505 막대기 (KOI13_game) C++
100 / 100
 92 ms 6248 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6248 KB Output is correct
2 Correct 0 ms 6248 KB Output is correct
3 Correct 0 ms 6248 KB Output is correct
4 Correct 0 ms 6248 KB Output is correct
5 Correct 0 ms 6248 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 6248 KB Output is correct
2 Correct 36 ms 6248 KB Output is correct
3 Correct 84 ms 6248 KB Output is correct
4 Correct 76 ms 6248 KB Output is correct
5 Correct 80 ms 6248 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6248 KB Output is correct
2 Correct 0 ms 6248 KB Output is correct
3 Correct 0 ms 6248 KB Output is correct
4 Correct 0 ms 6248 KB Output is correct
5 Correct 0 ms 6248 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6248 KB Output is correct
2 Correct 0 ms 6248 KB Output is correct
3 Correct 0 ms 6248 KB Output is correct
4 Correct 0 ms 6248 KB Output is correct
5 Correct 0 ms 6248 KB Output is correct
6 Correct 0 ms 6248 KB Output is correct
7 Correct 0 ms 6248 KB Output is correct

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6248 KB Output is correct
2 Correct 8 ms 6248 KB Output is correct
3 Correct 32 ms 6248 KB Output is correct
4 Correct 92 ms 6248 KB Output is correct
5 Correct 88 ms 6248 KB Output is correct
6 Correct 84 ms 6248 KB Output is correct
7 Correct 92 ms 6248 KB Output is correct
8 Correct 80 ms 6248 KB Output is correct
9 Correct 8 ms 6248 KB Output is correct
10 Correct 8 ms 6248 KB Output is correct
11 Correct 88 ms 6248 KB Output is correct
12 Correct 92 ms 6248 KB Output is correct