oj.uz

Submission #18960

# Submission time Handle Problem Language Result Execution time Memory
18960 2016-02-16T18:16:19 Z hjk0553 막대기 (KOI13_game) C++
100 / 100
 76 ms 6064 KB 
#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.0 / 11.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6064 KB Output is correct
2 Correct 29 ms 6064 KB Output is correct
3 Correct 57 ms 6064 KB Output is correct
4 Correct 55 ms 6064 KB Output is correct
5 Correct 58 ms 6064 KB Output is correct

Subtask #3
16.0 / 16.0

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

Subtask #4
22.0 / 22.0

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

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6064 KB Output is correct
2 Correct 8 ms 6064 KB Output is correct
3 Correct 34 ms 6064 KB Output is correct
4 Correct 70 ms 6064 KB Output is correct
5 Correct 76 ms 6064 KB Output is correct
6 Correct 54 ms 6064 KB Output is correct
7 Correct 61 ms 6064 KB Output is correct
8 Correct 54 ms 6064 KB Output is correct
9 Correct 6 ms 6064 KB Output is correct
10 Correct 6 ms 6064 KB Output is correct
11 Correct 61 ms 6064 KB Output is correct
12 Correct 61 ms 6064 KB Output is correct