oj.uz

Submission #8253

# Submission time Handle Problem Language Result Execution time Memory
8253 2014-09-08T13:27:50 Z gs14004 막대기 (KOI13_game) C++
0 / 100
 1000 ms 2648 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2648 KB Output is correct
2 Incorrect 0 ms 2648 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 2644 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2648 KB Output is correct
2 Incorrect 0 ms 2648 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 176 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -