Submission #73225976

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
struct yokobou_s {
  int a, b;
};
/* bの降順 → aの昇順 */
int cmp(const void* x, const void* y) {
  struct yokobou_s a = *(const struct yokobou_s*)x, b = *(const struct yokobou_s*)y;
  return
    ((a.b < b.b) - (a.b > b.b)) * 2 +
    ((a.a > b.a) - (a.a < b.a));
}
int n, m, h, k;
int s[1024];
struct yokobou_s ab[114514];
int pos[1024];
int dore[114514][2];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>

struct yokobou_s {
	int a, b;
};

/* bの降順 → aの昇順 */
int cmp(const void* x, const void* y) {
	struct yokobou_s a = *(const struct yokobou_s*)x, b = *(const struct yokobou_s*)y;
	return
		((a.b < b.b) - (a.b > b.b)) * 2 +
		((a.a > b.a) - (a.a < b.a));
}

int n, m, h, k;
int s[1024];
struct yokobou_s ab[114514];

int pos[1024];
int dore[114514][2];
char used[1024];

int main(void) {
	int i;
	int cur = 0, ans;
	if (scanf("%d%d%d%d", &n, &m, &h, &k) != 4) return 1;
	for (i = 1; i <= n; i++) {
		if (scanf("%d", &s[i]) != 1) return 1;
	}
	for (i = 0; i < m; i++) {
		if (scanf("%d%d", &ab[i].a, &ab[i].b) != 2) return 1;
	}
	qsort(ab, m, sizeof(*ab), cmp);
	for (i = 1; i <= n; i++) {
		pos[i] = i;
	}
	for (i = 0; i < m; i++) {
		int t;
		dore[i][0] = pos[ab[i].a];
		dore[i][1] = pos[ab[i].a + 1];
		t = pos[ab[i].a];
		pos[ab[i].a] = pos[ab[i].a + 1];
		pos[ab[i].a + 1] = t;
	}
	for (i = 1; i <= k; i++) {
		cur += s[pos[i]];
		used[pos[i]] = 1;
	}
	ans = cur;
	for (i = 0; i < m; i++) {
		int candidate = cur;
		if (used[dore[i][0]] && !used[dore[i][1]]) {
			candidate -= s[dore[i][0]];
			candidate += s[dore[i][1]];
		} else if (!used[dore[i][0]] && used[dore[i][1]]) {
			candidate -= s[dore[i][1]];
			candidate += s[dore[i][0]];
		}
		if (candidate < ans) ans = candidate;
	}
	printf("%d\n", ans);
	return 0;
}

/*

横棒の削除 → その横棒の真下に横棒を追加して入れ替えるのと同じ
その横棒を通る2本のみに影響する

下から上にどこに行くかを調べ、各横棒について差分

*/

Submission Info

Judge Result