oj.uz

Submission #14850

# Submission time Handle Problem Language Result Execution time Memory
14850 2015-07-01T08:12:49 Z Fakeable 막대기 (KOI13_game) C++
13 / 100
 522 ms 9436 KB 
#include<cstdio>
#include<algorithm>
#include<utility>
#include<vector>
#define mp make_pair
using namespace std;

const int max_n = 100100;
typedef pair<int,int> pi;
typedef long long ll;
int n,l;
ll ans,dp1[max_n],dp2[max_n];
pi p[max_n];
vector<int> up[max_n], down[max_n];

void input() {
    scanf("%d%d",&n,&l);
    for(int i=0;i<n;i++) scanf("%d%d",&p[i].first,&p[i].second);
    for(int i=0;i<n;i++) {
        up[p[i].first].push_back(i);
        down[p[i].second].push_back(i);
    }
    return;
}
inline int abs(int x) {return x>0?x:-x;}
ll fill1(int x);
ll fill2(int x);

ll fill1(int x) {
    if(dp1[x]) return dp1[x];
    ll ret = 0;
    for(int i=0; i<(int)down[p[x].second].size(); i++) {
        int nxt = down[p[x].second][i];
        if(p[x].first >= p[nxt].first) continue;
        ret = max(ret, fill2(nxt));
    }
    return dp1[x] = ret + 1LL*abs(p[x].first - p[x].second) + l;
}
ll fill2(int x) {
    if(dp2[x]) return dp2[x];
    ll ret = 0;
    for(int i=0; i<(int)up[p[x].first].size(); i++) {
        int nxt = up[p[x].first][i];
        if(p[x].second >= p[nxt].second) continue;
        ret = max(ret, fill1(nxt));
    }
    return dp2[x] = ret + 1LL*abs(p[x].first - p[x].second) + l;
}
void solve() {
    for(int i=0;i<n;i++) fill1(i);
    for(int i=0;i<n;i++) fill2(i);
    for(int i=0;i<n;i++) {
        ans = max(ans, dp1[i]);
        ans = max(ans, dp2[i]);
    }
    printf("%lld",ans);
    return;
}
int main() {
    input();
    solve();
    return 0;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8248 KB Output is correct
2 Correct 0 ms 8248 KB Output is correct
3 Correct 0 ms 8248 KB Output is correct
4 Correct 0 ms 8248 KB Output is correct
5 Runtime error 0 ms 8244 KB SIGSEGV Segmentation fault

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 8908 KB Output is correct
2 Correct 174 ms 8908 KB Output is correct
3 Correct 241 ms 9436 KB Output is correct
4 Correct 522 ms 9436 KB Output is correct
5 Correct 350 ms 9436 KB Output is correct

Subtask #3
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8248 KB Output is correct
2 Correct 0 ms 8248 KB Output is correct
3 Runtime error 0 ms 8244 KB SIGSEGV Segmentation fault
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8248 KB Output is correct
2 Runtime error 0 ms 8244 KB SIGSEGV Segmentation fault
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 8244 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -