Submission #1174412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174412		Tsagana	Marathon Race 2 (JOI24_ho_t3)	C++20	100 / 100	448 ms	21612 KiB

Main

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(a) a.begin(), a.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

const int Inf = 2e18;
int n, L, joi;
int a[500010];
int p[500010];
int dp[2][1010][1010];
int f[2][1010];
vector<pair<int,int>> v;

void prep() {
	sort(a + 1, a + n + 1);
	v.pb({a[1] , 0});
	for (int i = 1; i <= n; i++) {
		if (v.back().F == a[i]) v.back().S++;
		else v.pb({a[i], 1});
		p[a[i]]++;
	}
	n = v.size();
	for (int i = 1; i < 500000; i++) p[i] += p[i-1];
}

void build() {
	if (n >= 1010) return;
	for (int T = 0; T < 2; T++) {
		for (int l = 0; l < n; l++)
			for (int r = 0; r < n; r++)
				dp[0][l][r] = dp[1][l][r] = Inf;

		dp[T][0][n-1] = 0;
		for (int len = n; len > 1; len--)
			for (int l = 0 , r = len-1; r < n; l++, r++) {
				int cnt = joi + p[v[l].F-1 ] - p[v[r].F] + 1;

				dp[0][l+1][r] = min(dp[0][l+1][r] , dp[0][l][r] + (cnt + v[l].S)*(v[l+1].F-v[l].F));
				dp[0][l+1][r] = min(dp[0][l+1][r] , dp[1][l][r] + cnt*(v[r].F+v[l+1].F-2*v[l].F)+v[l].S*(v[l+1].F-v[l].F));

				dp[1][l][r-1] = min(dp[1][l][r-1] , dp[1][l][r] + (cnt + v[r].S)*(v[r].F-v[r-1].F));
				dp[1][l][r-1] = min(dp[1][l][r-1] , dp[0][l][r] + cnt*(2*v[r].F-v[l].F-v[r-1].F) + v[r].S*(v[r].F-v[r-1].F));
			}

		for (int i = 0; i < n; i++) f[T][i] = min(dp[0][i][i] , dp[1][i][i]);
	}
}

void solve () {
	cin >> n >> L; joi = n;
	for (int i = 1; i <= n; i++) cin >> a[i];

	prep();
	build();

	int q; cin >> q;
	while (q--) {
		int st , en , T;
		cin >> st >> en >> T;
		T -= joi;
		if (n >= 1010)  {cout << "No\n"; continue ;}
		int k = lb(all(v), make_pair(en, 0ll)) - v.begin();
		int ans = Inf;
		for (int i = max(0ll, k-2); i <= min(n-1, k+2); i++) {
			ans = min(ans, f[0][i] + abs(st-v[0].F) + (joi+1)*abs(en-v[i].F));
			ans = min(ans, f[1][i] + abs(st-v[n-1].F) + (joi+1)*abs(en-v[i].F));
		}
		if (ans <= T) cout << "Yes\n";
		else cout << "No\n";
	}
}
signed main() {IOS solve(); return 0;}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 28 / 28
• Subtask 5: 10 / 10
• Subtask 6: 19 / 19
• Subtask 7: 19 / 19