oj.uz

Submission #16029

# Submission time Handle Problem Language Result Execution time Memory
16029 2015-08-08T09:18:01 Z jihoon 막대기 (KOI13_game) C++
100 / 100
 241 ms 9880 KB 
#include<cstdio>
#include<map>
#include<vector>
#include<math.h>
#include<cstdlib>
#include<algorithm>
using namespace std;

int n,l;
long long int dp[100001][2];
long long int cal1,cal2;
int upper[100001],ucnt;
int lower[100001],lcnt;
map<int,int> upmap;
map<int,int> downmap;

class link{
public:
    int up,down,dist;
    bool operator < (const link &l) const{
        if(up==l.up) return down < l.down;
        else return up < l.up;
    }
}line[100002];

int main(){
    int i;
    long long int cal1,cal2,mx=0;
    scanf("%d %d",&n,&l);
    for(i=0;i<n;i++){
        scanf("%d %d",&(line[i].up),&(line[i].down));
        line[i].dist=l+abs(line[i].up-line[i].down);
        if(upmap[line[i].up]==0){
            upmap[line[i].up]=-1;
            upper[ucnt++]=line[i].up;
        }
        if(downmap[line[i].down]==0){
            downmap[line[i].down]=-1;
            lower[lcnt++]=line[i].down;
        }
    }
    sort(upper,upper+ucnt);
    sort(lower,lower+lcnt);
    for(i=0;i<ucnt;i++){
        upmap[upper[i]]=i;
    }
    for(i=0;i<lcnt;i++){
        downmap[lower[i]]=i;
    }
    for(i=0;i<n;i++){
        line[i].up=upmap[line[i].up];
        line[i].down=downmap[line[i].down];
    }
    sort(line,line+n);
    for(i=0;i<n;i++){
        cal1=line[i].dist+dp[line[i].up][0];
        cal2=line[i].dist+dp[line[i].down][1];
        dp[line[i].up][0]=max(dp[line[i].up][0],cal2);
        dp[line[i].down][1]=max(dp[line[i].down][1],cal1);
    }
    for(i=0;i<n;i++){
        mx=max(mx,dp[i][0]);
        mx=max(mx,dp[i][1]);
    }
    printf("%lld",mx);
}

Subtask #1
11.0 / 11.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 4732 KB Output is correct
2 Correct 23 ms 4732 KB Output is correct
3 Correct 82 ms 4732 KB Output is correct
4 Correct 73 ms 4732 KB Output is correct
5 Correct 55 ms 4732 KB Output is correct

Subtask #3
16.0 / 16.0

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

Subtask #4
22.0 / 22.0

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

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4996 KB Output is correct
2 Correct 13 ms 4996 KB Output is correct
3 Correct 63 ms 6052 KB Output is correct
4 Correct 200 ms 8560 KB Output is correct
5 Correct 241 ms 9088 KB Output is correct
6 Correct 176 ms 8824 KB Output is correct
7 Correct 227 ms 9880 KB Output is correct
8 Correct 153 ms 9352 KB Output is correct
9 Correct 15 ms 5128 KB Output is correct
10 Correct 11 ms 4864 KB Output is correct
11 Correct 185 ms 7768 KB Output is correct
12 Correct 196 ms 7768 KB Output is correct