Submission #198954

#	Time	Username	Problem	Language	Result	Execution time	Memory
198954		lobo_prix	막대기 (KOI13_game)	C++17	100 / 100	351 ms	21240 KiB

game

#include <bits/stdc++.h>

using namespace std;using f64 = double;using i64=long long;using u64=unsigned long long;
template<typename T> using Arr=vector<T>;
#define hfor(v, s, e) for(int v=(s);(s)<=v&&v<(e);++v)//half-opened range
#define hfori(v, s, e) for(int v=(e)-1;(s)<=v&&v<(e);--v)//inversion
#define hforo(v, s, e) int v=(s);for(;(s)<=v&&v<(e);++v)//out declaration
#define hforoi(v, s, e) int v=(e)-1; for(;(s)<=v&&v<(e);--v)
#define cfor(v, s, e) hfor(v,(s),(e)+1)//closed range
#define cfori(v, s, e) hfori(v,(s),(e)+1)
#define cforo(v, s, e) hforo(v,(s),(e)+1)
#define cforoi(v, s, e) hforoi(v,(s),(e)+1)
#define rep(v,x) hfor(v,0,(x))
#define repi(v,x) hfori(v,0,(x))
#define repo(v,x) hforo(v,0,(x))
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define pushb push_back
#define pushf push_front
#define popb pop_back
#define popf pop_front
#define empl emplace
#define emplb emplace_back
#define emplf emplace_front
#define fi first
#define se second
#define cxp constexpr
#define PQ std::priority_queue

#ifndef DEBUG
	#pragma GCC optimize ("Ofast")
	auto __PRE_RUN__=(ios::sync_with_stdio(0), cin.tie(0), cout.tie(0),(cout<<fixed<<setprecision(11)), 0);
#endif

template<typename T> cxp T inf() { return numeric_limits<T>::max() / 2; }
auto mapf(auto a, auto f){for(auto& x:a)x=f(x); return a;}
int rd(int lb, int ub){static mt19937 rng(time(0)^i64(new int)); return uniform_int_distribution<int>(lb, ub-1)(rng);}
int rd(int ub=inf<int>()){return rd(0,ub);}
const f64 pi=acosl(-1);
#define endl '\n'//not interactive?
#define int i64//MLE?
using pint = pair<int,int>;
using tint = tuple<int,int,int>;

const int N=100000;
int n,l;
int a[N][2];
map<int,Arr<int>> b[2];
int dp[N][2];

int f(int idx, bool td){
	int& ret=dp[idx][td];
	if(ret)
		return ret;
	//b[!td][a[idx][!td]]
	auto it=lower_bound(all(b[td][a[idx][td]]), idx, [&](auto z1, auto z2){return a[z1][!td]<a[z2][!td];});
	if(it==b[td][a[idx][td]].begin())
		ret=0;
	else{
		auto pit=prev(it);
		ret = max( f(*pit,td)-abs(a[*pit][0]-a[*pit][1])-l, f(*pit,!td) );
	}
	//for(auto i:b[td][a[idx][td]])
	//	if(a[idx][!td] > a[i][!td])
	//		ret=max(ret, f(i,!td));
	return ret+=abs(a[idx][0]-a[idx][1])+l;
}

signed main(){
	cin>>n>>l;
	rep(i,n){
		cin>>a[i][0]>>a[i][1];
		b[0][a[i][0]].pushb(i);
		b[1][a[i][1]].pushb(i);
	}
	rep(td,2)
		for(auto& j:b[td])
			sort(all(j.se), [&](auto z1, auto z2){return a[z1][!td]<a[z2][!td];});

	int ans=0;
	rep(i,n)
		rep(j,2)
			ans=max(ans, f(i,j));
	cout<<ans<<endl;

	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 22 / 22
• Subtask 5: 38 / 38