oj.uz

Submission #14852

# Submission time Handle Problem Language Result Execution time Memory
14852 2015-07-01T08:57:07 Z Fakeable 막대기 (KOI13_game) C++
100 / 100
 111 ms 12924 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], v1, v2;

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++) v1.push_back(p[i].first);
    sort(v1.begin(),v1.end());
    v1.erase(unique(v1.begin(),v1.end()),v1.end());
    for(int i=0;i<n;i++) {
        int lo = 0, hi = (int)v1.size()-1;
        while(lo < hi) {
            int mid = (lo+hi-1)/2;
            if(v1[mid] < p[i].first) lo = mid+1;
            else hi = mid;
        }
        p[i].first = lo;
    }
    
    for(int i=0;i<n;i++) v2.push_back(p[i].second);
    sort(v2.begin(), v2.end());
    v2.erase(unique(v2.begin(), v2.end()), v2.end());
    for(int i=0;i<n;i++) {
        int lo = 0, hi = (int)v2.size()-1;
        while(lo < hi) {
            int mid = (lo+hi-1)/2;
            if(v2[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;}
void solve() {
    sort(p,p+n);
    for(int i=n-1;i>=0;i--) {
        ll dist = 1LL*abs(v1[p[i].first]-v2[p[i].second]) + l;
        ll dp1_ = dp2[p[i].second] + dist;
        ll dp2_ = dp1[p[i].first] + dist;
        dp1[p[i].first] = max(dp1[p[i].first], dp1_);
        dp2[p[i].second] = max(dp2[p[i].second], dp2_);
    }
    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 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 #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 9432 KB Output is correct
2 Correct 32 ms 9432 KB Output is correct
3 Correct 69 ms 10472 KB Output is correct
4 Correct 66 ms 10472 KB Output is correct
5 Correct 68 ms 10472 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 0 ms 8252 KB Output is correct
2 Correct 0 ms 8252 KB Output is correct
3 Correct 2 ms 8252 KB Output is correct
4 Correct 3 ms 8252 KB Output is correct
5 Correct 0 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
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8576 KB Output is correct
2 Correct 12 ms 8576 KB Output is correct
3 Correct 33 ms 9904 KB Output is correct
4 Correct 105 ms 12056 KB Output is correct
5 Correct 100 ms 12188 KB Output is correct
6 Correct 84 ms 12688 KB Output is correct
7 Correct 82 ms 12848 KB Output is correct
8 Correct 82 ms 12924 KB Output is correct
9 Correct 7 ms 8576 KB Output is correct
10 Correct 11 ms 8576 KB Output is correct
11 Correct 106 ms 11528 KB Output is correct
12 Correct 111 ms 11528 KB Output is correct