Submission #1228883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228883		antromancap	여별 열쇠 (JOI15_keys)	C++17	100 / 100	16 ms	32584 KiB

keys

#include <bits/stdc++.h>

using namespace std;

template <class T> bool mini(T &x, const T &y) { return y < x ? x = y, 1 : 0; }
template <class T> bool maxi(T &x, const T &y) { return y > x ? x = y, 1 : 0; }

const int N = 2002;
int n, m, k, c[N][N], dp[N][N][2];
int nxt[N], prv[N];

void add(int u, int v, int x) { c[u][v] = (c[v][u] += x); }
struct lab {
	int a, b, c;
} E[2 * N];

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

	cin >> n >> m >> k;
	for (int i = 0, s, t; i < n; i++) {
		cin >> s >> t;
		E[i << 1] = { s, i, 0 };
		E[i << 1 | 1] = { t, i, 1 };
	}
	memset(prv, -1, 4 * N);
	memset(nxt, -1, 4 * N);
	memset(dp, -1, sizeof dp);
	sort(E, E + 2 * n, [&](lab x, lab y) { return x.a < y.a; });
	int res = E[0].a + m - E[2 * n - 1].a;
	for (int i = 0; i < 2 * n - 1; i++) {
		if (E[i].c) {
			if (E[i + 1].c) {
				add(E[i + 1].b, E[i + 1].b, E[i + 1].a - E[i].a);
			} else {
				res += E[i + 1].a - E[i].a;
			}
		} else {
			if (E[i + 1].c) {
				add(E[i + 1].b, E[i].b, E[i + 1].a - E[i].a);
				if (E[i + 1].b != E[i].b) prv[nxt[E[i + 1].b] = E[i].b] = E[i + 1].b;

			} else add(E[i].b, E[i].b, E[i + 1].a - E[i].a);
		}
	}
	vector<int> v;
	for (int i = 0; i < n; i++) {
		if (~prv[i]) continue;
		for (int u = i; ~u; u = nxt[u]) v.push_back(u);
	}
	dp[1][1][1] = c[v[0]][v[0]];
	dp[1][0][0] = 0;
	for (int i = 1; i < n; i++)
		for (int j = 0; j <= i; j++)
			for (int k = 0; k < 2; k++)
				if (dp[i][j][k] >= 0) {
					maxi(dp[i + 1][j + 1][1], dp[i][j][k] + c[v[i]][v[i]] + k * c[v[i - 1]][v[i]]);
					maxi(dp[i + 1][j][0], dp[i][j][k]);
				}

	cout << max(dp[n][k][0], dp[n][k][1]) + res;
}

• Subtask 1: 10 / 10
• Subtask 2: 90 / 90