Submission #16029

#	Time	Username	Problem	Language	Result	Execution time	Memory
16029		jihoon	막대기 (KOI13_game)	C++98	100 / 100	241 ms	9880 KiB

game

#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 / 11
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 22 / 22
• Subtask 5: 38 / 38