結果

問題 No.9 モンスターのレベル上げ
ユーザー FF256grhyFF256grhy
提出日時 2015-05-12 07:15:50
言語 C++11
(gcc 8.5.0)
結果
AC  
実行時間 4,474 ms / 5,000 ms
コード長 1,605 bytes
コンパイル時間 300 ms
使用メモリ 5,160 KB
最終ジャッジ日時 2023-01-21 14:31:16
合計ジャッジ時間 22,864 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
testcase_00 AC 1 ms
5,160 KB
testcase_01 AC 2 ms
5,156 KB
testcase_02 AC 2,361 ms
4,904 KB
testcase_03 AC 1,625 ms
4,900 KB
testcase_04 AC 671 ms
5,160 KB
testcase_05 AC 367 ms
4,900 KB
testcase_06 AC 80 ms
5,156 KB
testcase_07 AC 2 ms
4,904 KB
testcase_08 AC 130 ms
4,904 KB
testcase_09 AC 2,186 ms
4,904 KB
testcase_10 AC 1 ms
4,900 KB
testcase_11 AC 4,474 ms
5,156 KB
testcase_12 AC 15 ms
4,904 KB
testcase_13 AC 3,527 ms
5,156 KB
testcase_14 AC 2,193 ms
4,904 KB
testcase_15 AC 1,976 ms
4,900 KB
testcase_16 AC 7 ms
4,900 KB
testcase_17 AC 1,028 ms
5,152 KB
testcase_18 AC 808 ms
4,904 KB
testcase_19 AC 5 ms
4,900 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

void marge_sort(int[], int, int);
int win(int, int);

int n, a[1500], b[1500], level[1500], buttle[1500];

int main(void) {
	scanf("%d", &n);
	int i, j;
 	for(i = 0; i < n; i++) { scanf("%d", &a[i]); }
	for(i = 0; i < n; i++) { scanf("%d", &b[i]); b[i] /= 2; }
	
	marge_sort(a, 0, n - 1);
	
	int min = 1501;
	for(i = 0; i < n; i++) { // i: 開始位置
		for(j = 0; j < n; j++) {
			level [j] = a[j];
			buttle[j] = 0;
		}
		for(j = 0; j < n; j++) {
			level [0] += b[(i + j) % n];
			buttle[0]++;
			int p = 0;
			while(p + 1 < n && win(p, p + 1)) {
				int temp_l = level [p];
				int temp_b = buttle[p];
				level [p] =  level[p + 1];
				buttle[p] = buttle[p + 1];
				level [p + 1] = temp_l;
				buttle[p + 1] = temp_b;
				p++;
			}
		}
		int max = 0;
		for(j = 0; j < n; j++) {
			max = max < buttle[j] ? buttle[j] : max;
		}
		min = max < min ? max : min;
	}
	printf("%d\n", min);
	return 0;
}

void marge_sort(int x[], int l, int r) {
	if(l == r) { return; }
	int m = (l + r) / 2;
	marge_sort(x, l, m);
	marge_sort(x, m + 1, r);
	int p = l, q = m + 1, cnt = 0, copy[r - l + 1];
	while(1) {
		int flag;
		if(m < p && r < q) { break; }
		else if(r < q) { flag = 1; }
		else if(m < p) { flag = 0; }
		else { flag = ( x[p] <= x[q] ); }
		if(flag) {
			copy[cnt] = x[p];
			p++;
		} else {
			copy[cnt] = x[q];
			q++;
		}
		cnt++;
	}
	int i;
	for(i = 0; i < r - l + 1; i++) {
		x[l + i] = copy[i];
	}
	return;
}

int win(int p, int q) { // pの方が大きければ1
	if(level[q]  < level[p]) { return 1; }
	if(level[q] == level[p]) { return buttle[q] < buttle[p]; }
	return 0;
}
0