oj.uz

Submission #14851

# Submission time Handle Problem Language Result Execution time Memory
14851 2015-07-01T08:20:07 Z Fakeable 막대기 (KOI13_game) C++
62 / 100
 1000 ms 10468 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], v;

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++) {
        v.push_back(p[i].first);
        v.push_back(p[i].second);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=0;i<n;i++) {
        int lo = 0, hi = (int)v.size()-1;
        while(lo < hi) {
            int mid = (lo+hi-1)/2;
            if(v[mid] < p[i].first) lo = mid+1;
            else hi = mid;
        }
        p[i].first = lo;
        lo = 0, hi = (int)v.size()-1;
        while(lo < hi) {
            int mid = (lo+hi-1)/2;
            if(v[mid] < p[i].second) lo = mid+1;
            else hi = mid;
        }
        p[i].second = lo;
    }
    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(v[p[x].first] - v[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(v[p[x].first] - v[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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8252 KB Output is correct
2 Correct 0 ms 8252 KB Output is correct
3 Correct 3 ms 8252 KB Output is correct
4 Correct 0 ms 8252 KB Output is correct
5 Correct 0 ms 8252 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 9428 KB Output is correct
2 Correct 219 ms 9428 KB Output is correct
3 Correct 262 ms 10468 KB Output is correct
4 Correct 555 ms 10468 KB Output is correct
5 Correct 378 ms 10468 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8252 KB Output is correct
2 Correct 0 ms 8252 KB Output is correct
3 Correct 0 ms 8252 KB Output is correct
4 Correct 0 ms 8252 KB Output is correct
5 Correct 0 ms 8252 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8252 KB Output is correct
2 Correct 3 ms 8252 KB Output is correct
3 Correct 10 ms 8252 KB Output is correct
4 Correct 0 ms 8252 KB Output is correct
5 Correct 3 ms 8252 KB Output is correct
6 Correct 0 ms 8252 KB Output is correct
7 Correct 0 ms 8252 KB Output is correct

Subtask #5
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8516 KB Output is correct
2 Correct 10 ms 8648 KB Output is correct
3 Execution timed out 1000 ms 9896 KB Program timed out
4 Halted 0 ms 0 KB -