Submission #14852

#	Time	Username	Problem	Language	Result	Execution time	Memory
14852		Fakeable	막대기 (KOI13_game)	C++98	100 / 100	111 ms	12924 KiB

game

#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 / 11
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 22 / 22
• Subtask 5: 38 / 38