제출 #1364085

#제출 시각아이디문제언어결과실행 시간메모리
1364085vlomaczkAmbulance (JOI25_ambulance)C++20
100 / 100
613 ms63960 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#pragma GCC optimize("O3,unroll-loops")
#ifdef _WIN32
#define getchar_unlocked getchar
#define putchar_unlocked putchar
#endif

inline ll readint() {
    char c = getchar_unlocked();
    while((c < '0' || c > '9') && c != '-') c = getchar_unlocked();
    bool neg = false;
    if(c == '-') neg = true, c = getchar_unlocked();
    ll res = 0;
    while(c >= '0' && c <= '9') res = res * 10 + c - '0', c = getchar_unlocked();
    return neg? -res : res;
}

char _buf[40];
inline void printint(ll n) {
    if(n == 0) putchar_unlocked('0');
    if(n < 0) putchar_unlocked('-'), n = -n;
    ll i = 0;
    for(; n > 0; n /= 10) _buf[i++] = n % 10 + '0';
    while(i--) putchar_unlocked(_buf[i]);
}

struct Point {
	ll x, y, i;
};

void calc_dp_pref(vector<vector<ll>> &DP, vector<Point> pkt, vector<ll> check, vector<ll> A, vector<ll> B, ll T) {
	ll x1 = A[0]; ll y1 = A[1];
	ll x2 = B[0]; ll y2 = B[1];
	ll n = pkt.size();
	vector<ll> t1(n), t2(n);
	for(ll i=0; i<n; ++i) {
		auto[x,y,idx] = pkt[i];
		t1[i] = abs(x - x1) + abs(y - y1);
		t2[i] = abs(x - x2) + abs(y - y2);
	}
	for(int i=0; i<=T; ++i) DP[0][i] = 0;
	for(ll i=1; i<=n; ++i) {
		if(check[pkt[i-1].i]) {
			for(ll t=0; t<=T; ++t) {
				DP[i][t] = DP[i-1][t] + t2[i-1];
				if(t >= t1[i-1]) DP[i][t] = min(DP[i][t], DP[i-1][t - t1[i-1]]);
			}
		} else for(ll t=0; t<=T; ++t) DP[i][t] = DP[i-1][t];
	}
}

void calc_dp_suf(vector<vector<ll>> &DP, vector<Point> pkt, vector<ll> check, vector<ll> A, vector<ll> B, ll T) {
	ll x1 = A[0]; ll y1 = A[1];
	ll x2 = B[0]; ll y2 = B[1];
	ll n = pkt.size();
	vector<ll> t1(n), t2(n);
	for(ll i=0; i<n; ++i) {
		auto[x,y,idx] = pkt[i];
		t1[i] = abs(x - x1) + abs(y - y1);
		t2[i] = abs(x - x2) + abs(y - y2);
	}
	for(int i=0; i<=T; ++i) DP[n][i] = 0;
	for(ll i=n-1; i>=0; --i) {
		if(check[pkt[i].i]) {
			for(ll t=0; t<=T; ++t) {
				DP[i][t] = DP[i+1][t] + t2[i];
				if(t >= t1[i]) DP[i][t] = min(DP[i][t], DP[i+1][t - t1[i]]);
			}
		} else for(ll t=0; t<=T; ++t) DP[i][t] = DP[i+1][t];
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	ll L = readint();
	ll n = readint();
	ll T = readint();
	T/=2;
	vector<Point> pkt(n);
	for(ll i=0; i<n; ++i) {
		pkt[i].x = readint();
		pkt[i].y = readint();
		pkt[i].i = i;
	}
	vector<Point> plus, minus;
	plus = minus = pkt;
	sort(plus.begin(), plus.end(), [&](Point a, Point b){ return a.x+a.y < b.x+b.y; }); //(1,1) (L,L)
	sort(minus.begin(), minus.end(), [&](Point a, Point b){ return a.x-a.y < b.x-b.y; }); //(1,L) (L,1)
	vector<vector<vector<ll>>> DP(4, vector<vector<ll>>(n+2, vector<ll>(T+1, 0)));
	for(ll b1=0; b1<=n; ++b1) {
		vector<vector<ll>> gr1 = {
			{1,1}, {L,L}	
		};
		vector<vector<ll>> gr2 = {
			{1,L}, {L,1}	
		};
		vector<ll> g1(n, 1);
		for(ll i=0; i<b1; ++i) g1[plus[i].i] = 0;

		vector<ll> g1x = g1;
		for(auto &x : g1x) x^=1;

		calc_dp_pref(DP[0],minus,g1x,gr1[0], gr2[0], T);
		calc_dp_pref(DP[1],minus,g1, gr2[0], gr1[1], T);
		calc_dp_suf(DP[2], minus, g1, gr1[1], gr2[1], T);
		calc_dp_suf(DP[3], minus, g1x,gr2[1], gr1[0], T);

		for(ll b2=0; b2<=n; ++b2) {
			for(ll t=0; t<=T; ++t) {
				ll oL = DP[0][b2][t];
				if(oL > T) continue;
				ll rest_oL = T - oL;

				ll LL = DP[1][b2][rest_oL]; 
				if(LL > T) continue;
				ll rest_LL = T - LL;

				ll Lo = DP[2][b2][rest_LL];
				if(Lo > T) continue;
				ll res_Lo = T - Lo;

				ll oo = DP[3][b2][res_Lo];
				if(t + oo <= T) {
					cout << "Yes\n";
					return 0;
				}
			}
		}
	}
	cout << "No\n";

	return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…