Submission #71354817

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>
#include <inttypes.h>
#define INF INT64_C(5050505050505050505)
int N, K;
int X[16], Y[16];
int64_t score_memo[1 << 16];
int64_t get_score(int points) {
  if (score_memo[points]) {
    return ~score_memo[points];
  } else {
    int64_t ans = 0;
    int i, j;
    for (i = 0; i < N; i++) {
      if ((points >> i) & 1) {
        for (j = i + 1; j < N; j++) {
          if ((points >> j) & 1) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

#define INF INT64_C(5050505050505050505)

int N, K;
int X[16], Y[16];

int64_t score_memo[1 << 16];

int64_t get_score(int points) {
	if (score_memo[points]) {
		return ~score_memo[points];
	} else {
		int64_t ans = 0;
		int i, j;
		for (i = 0; i < N; i++) {
			if ((points >> i) & 1) {
				for (j = i + 1; j < N; j++) {
					if ((points >> j) & 1) {
						int64_t candidate = (int64_t)(X[i] - X[j]) * (X[i] - X[j]) + (int64_t)(Y[i] - Y[j]) * (Y[i] - Y[j]);
						if (candidate > ans) ans = candidate;
					}
				}
			}
		}
		return ~(score_memo[points] = ~ans);
	}
}

#define MOD_BY 8475787
#define MULT 5644889
#define MULT2 4207433

struct memo_s {
	int cur, left;
	int64_t ans;
	struct memo_s* next;
};

struct memo_s* memos[MOD_BY];

int64_t* get_memo(int group_left, int cur, int left) {
	int hash = (int)(((long long) group_left * MULT + (long long)cur * MULT2 + left) % MOD_BY);
	struct memo_s** pmemo = &memos[hash];
	while (*pmemo != NULL) {
		if ((*pmemo)->cur == cur && (*pmemo)->left == left) {
			return &(*pmemo)->ans;
		}
		pmemo = &(*pmemo)->next;
	}
	*pmemo = malloc(sizeof(**pmemo));
	if (*pmemo == NULL) exit(2);
	**pmemo = (struct memo_s){ cur, left, -1, NULL };
	return &(*pmemo)->ans;
}

int64_t tiisakunaihou(int64_t a, int64_t b) {
	return a >= b ? a : b;
}

int64_t calc(int group_left, int cur, int left) {
	int64_t *pmemo = get_memo(group_left, cur, left);
	if (*pmemo >= 0) return *pmemo;
	if (cur == 0) {
		if (left == 0) {
			/* 全部グループに分け終わった or グループ枠が余った */
			return *pmemo = group_left == 0 ? 0 : INF;
		} else {
			if (group_left <= 0) {
				/* グループ枠が足りない */
				return *pmemo = INF;
			} else {
				/* 新規グループの作成開始 */
				int i;
				for (i = 0; ((left >> i) & 1) == 0; i++);
				return *pmemo = calc(group_left - 1, 1 << i, left & ~(1 << i));
			}
		}
	} else {
		/* 現在のグループの内容で精算する */
		int64_t ans = tiisakunaihou(calc(group_left, 0, left), get_score(cur));
		/* 現在のグループに点を追加する */
		int i;
		for (i = 0; i < N; i++) {
			if ((left >> i) & 1) {
				int64_t candidate = calc(group_left, cur | (1 << i), left & ~(1 << i));
				if (candidate < ans) ans = candidate;
			}
		}
		return *pmemo = ans;
	}
}

int main(void) {
	int i;
	if (scanf("%d%d", &N, &K) != 2) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d%d", &X[i], &Y[i]) != 2) return 1;
	}
	printf("%" PRId64 "\n", calc(K, 0, (1 << N) - 1));
	return 0;
}

Submission Info

Judge Result