Submission #8253

#	Time	Username	Problem	Language	Result	Execution time	Memory
8253		gs14004	막대기 (KOI13_game)	C++98	0 / 100	1000 ms	2648 KiB

game

#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);
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 16
• Subtask 4: 0 / 22
• Subtask 5: 0 / 38