제출 #8253

#제출 시각아이디문제언어결과실행 시간메모리
8253gs14004막대기 (KOI13_game)C++98
0 / 100
1000 ms2648 KiB
#include <cstdio>
#include <utility>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef pair<int,int> pi;
typedef long long lint;

int n,l;
pi a[100005];
lint dp[100005];

lint len(int p){return l + abs(a[p].second - a[p].first);}

lint yourOrdinaryDP(int pos){
    if(dp[pos]) return dp[pos];
    lint res = 0;
    for (int i=0; i<n; i++) {
        if(a[pos].first == a[i].first && a[pos].second < a[i].second){
            res = max(res,yourOrdinaryDP(i));
        }
        if(a[pos].second == a[i].second && a[pos].first < a[i].first){
            res = max(res,yourOrdinaryDP(i));
        }
    }
    return dp[pos] = res + len(pos);
}

int main(){
    scanf("%d %d",&n,&l);
    for (int i=0; i<n; i++) {
        scanf("%d %d",&a[i].first,&a[i].second);
    }
    lint res = 0;
    for (int i=0; i<n; i++) {
        res = max(res,yourOrdinaryDP(i));
    }
    printf("%lld",res);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...