# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
83090 | chunghan | 막대기 (KOI13_game) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
int N, L, A[100000], B[100000];
vector<int> X[100000], Y[100000];
lld D[100000], dist[100000];
lld solve(int i) {
if(D[i] != -1) return D[i];
int x = A[i], y = B[i];
lld ret = 0;
for(auto p : X[x])
if(&& B[p] < B[i] && p != i)
ret = max(ret, solve(p));
for(auto p : Y[y])
if(A[p] < A[i] && p != i)
ret = max(ret, solve(p));
//cout << i << ' ' << ret+dist[i] << endl;
return D[i] = ret + dist[i];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
memset(D, -1, sizeof(D));
cin >> N >> L;
for(int i = 0; i < N; i++) {
int x, y;
cin >> x >> y;
A[i] = x; B[i] = y;
X[x].push_back(i); Y[y].push_back(i);
dist[i] = abs(y-x) + L;
//cout << i << ' ' << dist[i] << endl;
}
lld rst = 0;
for(int i = 0; i < N; i++) rst = max(rst, solve(i));
cout << rst;
return 0;
}