oj.uz

Submission #198954

# Submission time Handle Problem Language Result Execution time Memory
198954 2020-01-28T11:26:54 Z lobo_prix 막대기 (KOI13_game) C++17
100 / 100
 351 ms 21240 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 3448 KB Output is correct
2 Correct 58 ms 3576 KB Output is correct
3 Correct 122 ms 6112 KB Output is correct
4 Correct 106 ms 6072 KB Output is correct
5 Correct 123 ms 6264 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 760 KB Output is correct
4 Correct 7 ms 504 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 6 ms 504 KB Output is correct

Subtask #5
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1400 KB Output is correct
2 Correct 20 ms 1528 KB Output is correct
3 Correct 90 ms 7548 KB Output is correct
4 Correct 324 ms 14712 KB Output is correct
5 Correct 313 ms 15864 KB Output is correct
6 Correct 294 ms 16224 KB Output is correct
7 Correct 351 ms 17696 KB Output is correct
8 Correct 207 ms 20844 KB Output is correct
9 Correct 20 ms 1912 KB Output is correct
10 Correct 18 ms 1528 KB Output is correct
11 Correct 269 ms 18784 KB Output is correct
12 Correct 253 ms 21240 KB Output is correct