oj.uz

Submission #198953

# Submission time Handle Problem Language Result Execution time Memory
198953 2020-01-28T11:20:01 Z lobo_prix 막대기 (KOI13_game) C++17
62 / 100
 1000 ms 6392 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]]
	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);
	}
	for(auto& i:b)
		for(auto& j:i)
			sort(all(j.se));

	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 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 6 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 #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 3448 KB Output is correct
2 Correct 247 ms 3676 KB Output is correct
3 Correct 311 ms 6264 KB Output is correct
4 Correct 629 ms 6136 KB Output is correct
5 Correct 442 ms 6392 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 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 7 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 14 ms 504 KB Output is correct
4 Correct 6 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
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1400 KB Output is correct
2 Correct 19 ms 1528 KB Output is correct
3 Execution timed out 1093 ms 5488 KB Time limit exceeded
4 Halted 0 ms 0 KB -