oj.uz

답안 #590421

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
590421 2022-07-05T23:05:00 Z farhan132 Sky Walking (IOI19_walk) C++17
0 / 100
 34 ms 13316 KB 
#include "walk.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll , ll> ii;
 
#define ff first
#define ss second
#define pb push_back
#define in insert

const ll N = 2e5 + 5;
vector < ll > L[N], R[N];
ll ans[N]; ll dp[N];

long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int S, int E) {

	ll m = l.size();
	for(ll i = 0; i < m; i++){
		L[l[i]].pb(i);
		R[r[i] + 1].pb(i);
		ans[i] = 1e18;
	}
	set < ii > s;

	for(auto i : L[0]){
		s.in({y[i], i});
		dp[i] = y[i];
	}
	ll n = x.size();
	for(ll j = 1; j < n; j++){
		for(auto i : R[j]){
			s.erase({y[i], i});
		}
		if(s.size() == 0) return -1; 
		for(auto i : L[j]){
			auto itr = s.lower_bound(make_pair(y[i], -1));
			if(itr != s.end()){
				auto [X, Y] = *itr;
				dp[i] = min(dp[i], dp[Y] + abs(X - y[i]));
			}
			if(itr != s.begin()){
				itr--;
				auto [X, Y] = *itr;
				dp[i] = min(dp[i], dp[Y] + abs(X - y[i]));
			}
			s.in({y[i], i});
		}
	}
	ll res = 1e18;
	for(auto [x, y] : s){
		res = min(res, dp[y] + x);
	}
	return res + x[n - 1] - x[0];
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 9692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 13316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 13316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 9692 KB Output isn't correct
2 Halted 0 ms 0 KB -