Submission #896697

#	Time	Username	Problem	Language	Result	Execution time	Memory
896697		guechotjrhh	Treatment Project (JOI20_treatment)	C++14	35 / 100	701 ms	524288 KiB

treatment

#include <iostream>
#include<vector>
#include<set>
#include<map>
#include<fstream>
#include<algorithm>
using namespace std;
#define ll long long
#define pi pair<ll,ll>
#define x first
#define y second
#define vi vector<int>
#define all(v) v.begin(),v.end()
#define l x.x
#define r x.y
#define t y.x
#define p y.y

ll min(ll a, ll b) { return a < b ? a : b; }
ll ab(ll n) { return n > 0 ? n : -n; }
int s, n;
long long func(int S, int N, vector<int> T, vector<int> L, vector<int> R, vector<int> P) {
	s = S; n = N;
	//N <= 5000
	vector<pair<pi, pi>> vec(n);
	for (int i = 0; i < n; i++)	vec[i] = { {L[i],R[i]}, {T[i],P[i]} };
	vector<pi> so(n);
	for (int i = 0; i < n; i++) {
		so[i] = {L[i] - T[i], i};
		if (L[i] == 1) so[i].x = -1e18;
	}
	sort(all(so));
	vector<ll> dp(n, 1e18);
	ll mn = 1e18;
	vector<vector<pi>> g(n + 2);
	for (int q = n - 1; q >= 0; q--) {
		int i = so[q].y;
		for (int z = 0; z < n; z++) {
			int j = so[z].y;
			if (R[i] - ab(T[j] - T[i]) >= L[j] - 1) {
				//dp[i] = min(dp[i], P[i] + dp[j]);
				//cout << q << ' ' << z << endl;
				g[i].push_back({ j, P[j] });
			}
		}
	}
	for (int i = 0; i < n; i++) if (L[i] == 1) g[n].push_back({ i,P[i] });
	for (int i = 0; i < n; i++) if (R[i] == s) g[i].push_back({ n+1,0 });

	vector<ll> dist(n + 2, 1e18);
	dist[n] = 0;
	set<pair<ll, int>> st;
	for (int i = 0; i < n+2; i++) st.insert({ dist[i],i });
	while (st.size()) {
		auto it = st.begin();
		int i = it->y;
		ll dst = it->x;
		st.erase(it);
		for (pi& pr : g[i]) {
			if (dist[pr.x] > pr.y + dst) {
				st.erase(st.find({ dist[pr.x],pr.x }));
				dist[pr.x] = pr.y + dst;
				st.insert({ dist[pr.x],pr.x });
			}
		}
	}
	return dist[n + 1] == 1e18 ? -1 : dist[n + 1];

	/*for (int q = n - 1; q >= 0; q--) {
		int i = so[q].y;
		if (R[i] == s) { dp[i] = P[i]; }
		else {
			for (int z = q + 1; z < n; z++) {
				int j = so[z].y;
				if (R[i]-ab(T[j]-T[i]) >= L[j]-1) {
					dp[i] = min(dp[i], P[i] + dp[j]);
				}
			}
		}
		cout << i << endl;
		cout << T[i] << ' ' << P[i] << endl;
		cout << L[i] << ' ' << R[i] << endl;
		cout << dp[i] << endl;
		if (L[i] == 1) mn = min(mn, dp[i]);
	}
	return mn == 1e18 ? -1 : mn;
	/*map<int, ll> mp;
	vector<pair<pi, pi>> vec(n);
	for (int i = 0; i < n; i++)	vec[i] = { {L[i],R[i]}, {T[i],P[i]} };
	sort(all(vec));
	mp[s + 1] = 0;
	for (int i = n - 1; i >= 0; i--) {
		auto it = mp.upper_bound(vec[i].r + 1);
		if (it != mp.begin()) {
			it--;
			if (mp.find(vec[i].l) == mp.end()) mp[vec[i].l] = vec[i].p + it->y;
			else mp[vec[i].l] = min(mp[vec[i].l], vec[i].p + it->y);

			auto it = mp.find(vec[i].l);
			while (next(it) != mp.end() && it->y < next(it)->y) mp.erase(next(it));
		}
	}
	if (mp.find(1) != mp.end()) return mp[1];
	return -1;*/
}

void run_tests() {
	string name = "03-00.txt";
	for (int i = 1; i <= 18; i++) {
		name[3] = '0' + i / 10;
		name[4] = '0' + i % 10;
		ifstream fin("in/" + name);
		ifstream fout("out/" + name);

		int S, N;
		fin >> S >> N;

		vector<int> T(N), L(N), R(N), P(N);
		for (int i = 0; i < N; i++) fin >> T[i] >> L[i] >> R[i] >> P[i];

		ll u = func(S, N, T, L, R, P),u1;
		fout >> u1;
		if (u != u1) {
			cout << i << endl;
			cout << S << ' ' << N << endl;
			cout << u << ' ' << u1 << endl;
			//for (int i = 0; i < N; i++) cout << T[i] << ' ' << L[i] << ' ' << R[i] << ' ' << P[i] << endl;
			return;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	//run_tests();
	//return 0;

	int S, N;
	cin >> S >> N;
	
	vector<int> T(N), L(N), R(N), P(N);
	for (int i = 0; i < N; i++) cin >> T[i] >> L[i] >> R[i] >> P[i];

	cout << func(S, N, move(T), move(L), move(R), move(P)) << endl;

	return 0;
}
/*
10 5
2 5 10 3
1 1 6 5
5 2 8 3
7 6 10 4
4 1 3 1

7
*/

Compilation message (stderr)

treatment.cpp:87:2: warning: "/*" within comment [-Wcomment]
   87 |  /*map<int, ll> mp;
      |   
treatment.cpp: In function 'long long int func(int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
treatment.cpp:34:5: warning: unused variable 'mn' [-Wunused-variable]
   34 |  ll mn = 1e18;
      |     ^~

• Subtask 1: 0 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 0 / 61