Submission #14850

#	Time	Username	Problem	Language	Result	Execution time	Memory
14850		Fakeable	막대기 (KOI13_game)	C++98	13 / 100	522 ms	9436 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];

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