Submission #1215465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215465		trimkus	Marathon Race 2 (JOI24_ho_t3)	C++20	100 / 100	181 ms	27600 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> a, cnt;
int n;

ll dp[5002][5002][2];

void chmin(ll& x, ll y) {
	x = min(x, y);
}

void solve() {
	vector<int> ps(n + 5);
	for (int i = 0; i < n; ++i) {
		ps[i + 1] = ps[i] + cnt[i];
	}
	for (int l = 0; l <= n; ++l) {
		for (int r = n; r >= l + 2; --r) {
			assert(l < n);
			//~ cerr << l << " " << r << endl;
			int w = ps[l + 1] + ps[n] - ps[r] + 1;
			chmin(dp[l + 1][r][0], dp[l][r][0] + 1LL * abs(a[l + 1] - a[l]) * w + cnt[l + 1]);
			chmin(dp[l][r - 1][1], dp[l][r][0] + 1LL * abs(a[r - 1] - a[l]) * w + cnt[r - 1]);
			if (r < n) {
				chmin(dp[l + 1][r][0], dp[l][r][1] + 1LL * abs(a[l + 1] - a[r]) * w + cnt[l + 1]);
				chmin(dp[l][r - 1][1], dp[l][r][1] + 1LL * abs(a[r - 1] - a[r]) * w + cnt[r - 1]);
			}
		}
	}
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int l;
	cin >> n >> l;
	a = vector<int>(n);
	int mx = 0;
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		a[i] = x;
	}
	//~ cerr << "A\n";
	sort(begin(a), end(a));
	vector<int> pool = a;
	pool.erase(unique(begin(pool), end(pool)), end(pool));
	//~ cerr << "size = " << cnt.size() << endl;
	//~ cerr << "A\n";
	cnt = vector<int>((int)pool.size());
	for (int i = 0; i < n; ++i) {
		int id = lower_bound(begin(pool), end(pool), a[i]) - begin(pool);
		assert(pool[id] == a[i]);
		cnt[id] += 1;
	}
	a = pool;
	n = (int)a.size();
	int total = 0;
	for (int i = 0; i < n; ++i) total += cnt[i];
	
	
	int m;
	cin >> m;
	vector<array<int, 3>> Q(m);
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < 3; ++j) {
			cin >> Q[i][j];
		}
		mx = max(mx, Q[i][2]);
	}
	//~ cerr << "Done reading...\n";
	if (1LL * n * (n + 1) / 2 > (int)1e6) {
		for (int i = 0; i < m; ++i) {
			cout << "No\n";
		}
		return 0;
	}
	vector<bool> res(m, false);
	auto update = [&]() -> void {
		for (int i = 0; i < m; ++i) {
			ll add = abs(a[0] - Q[i][0]);
			int pos = lower_bound(begin(a), end(a), Q[i][1] + 1) - begin(a);
			ll now = Q[i][2] + 1;
			if (pos > 0) {
				chmin(now, dp[pos - 1][pos][0] + 1LL * (total + 1) * abs(a[pos - 1] - Q[i][1]));
				if (pos < n) {
					chmin(now, dp[pos - 1][pos][1] + 1LL * (total + 1) * abs(a[pos] - Q[i][1]));
				}
			}
			//~ cerr << Q[i][0] << " " << Q[i][1] << " = " << now << " + " << add << " <=? " << Q[i][2] << endl;
			if (now + add <= Q[i][2]) res[i] = true;
		}
		for (int i = 0; i <= n; ++i) for (int j = 0; j <= n; ++j) for (int k = 0; k < 2; ++k) dp[i][j][k] = 1e18;
	};
	//~ cerr << "Here!\n";
	
	for (int i = 0; i <= n; ++i) for (int j = 0; j <= n; ++j) for (int k = 0; k < 2; ++k) dp[i][j][k] = 1e18;
	update(); dp[0][n][0] = cnt[0]; 
	//~ cerr << "Here!\n";
	//~ cerr << "ASAUGBF(ISFI\n";
	//~ cerr << "asassize before = " << cnt.size() << endl;
	solve(); 
	//~ cerr << "Here!\n";
	//~ cerr << "size after = " << cnt.size() << endl;
	update(); 
	//~ cerr << "Here!\n";
	//~ cerr << "Starting...\n";
	for (int i = 0; i < n; ++i) {
		a[i] = l - a[i];
	}
	//~ cerr << "a\n";
	reverse(begin(a), end(a));
	//~ cerr << "a\n";
	//~ cerr << "size = " << cnt.size() << endl;
	//~ for (auto& u : cnt) cerr << u << " ";
	//~ cerr << "\n";
	reverse(begin(cnt), end(cnt));
	//~ cerr << "a\n";
	for (int i = 0; i < m; ++i) {
		Q[i][0] = l - Q[i][0];
		Q[i][1] = l - Q[i][1];
	}
	dp[0][n][0] = cnt[0]; 
	//~ cerr << "Starting again...\n";
	solve(); update();
	for (int i = 0; i < m; ++i) {
		cout << (res[i] ? "Yes\n" : "No\n");
	}
}

• 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