結果

問題 No.738 平らな農地
ユーザー bal4ubal4u
提出日時 2019-08-05 07:43:27
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 4,430 bytes
コンパイル時間 851 ms
コンパイル使用メモリ 32,980 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-18 10:35:32
合計ジャッジ時間 3,291 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 1 ms
5,376 KB
testcase_12 AC 1 ms
5,376 KB
testcase_13 AC 1 ms
5,376 KB
testcase_14 AC 1 ms
5,376 KB
testcase_15 AC 12 ms
5,376 KB
testcase_16 AC 12 ms
5,376 KB
testcase_17 AC 11 ms
5,376 KB
testcase_18 AC 12 ms
5,376 KB
testcase_19 AC 13 ms
5,376 KB
testcase_20 AC 13 ms
5,376 KB
testcase_21 AC 13 ms
5,376 KB
testcase_22 AC 12 ms
5,376 KB
testcase_23 AC 12 ms
5,376 KB
testcase_24 AC 11 ms
5,376 KB
testcase_25 AC 1 ms
5,376 KB
testcase_26 AC 1 ms
5,376 KB
testcase_27 AC 1 ms
5,376 KB
testcase_28 AC 1 ms
5,376 KB
testcase_29 AC 1 ms
5,376 KB
testcase_30 AC 1 ms
5,376 KB
testcase_31 AC 0 ms
5,376 KB
testcase_32 AC 1 ms
5,376 KB
testcase_33 AC 1 ms
5,376 KB
testcase_34 AC 1 ms
5,376 KB
testcase_35 AC 1 ms
5,376 KB
testcase_36 AC 1 ms
5,376 KB
testcase_37 AC 1 ms
5,376 KB
testcase_38 AC 1 ms
5,376 KB
testcase_39 AC 1 ms
5,376 KB
testcase_40 AC 0 ms
5,376 KB
testcase_41 AC 1 ms
5,376 KB
testcase_42 AC 1 ms
5,376 KB
testcase_43 AC 1 ms
5,376 KB
testcase_44 AC 1 ms
5,376 KB
testcase_45 AC 14 ms
5,376 KB
testcase_46 AC 13 ms
5,376 KB
testcase_47 AC 13 ms
5,376 KB
testcase_48 AC 14 ms
5,376 KB
testcase_49 AC 13 ms
5,376 KB
testcase_50 AC 14 ms
5,376 KB
testcase_51 AC 14 ms
5,376 KB
testcase_52 AC 13 ms
5,376 KB
testcase_53 AC 13 ms
5,376 KB
testcase_54 AC 13 ms
5,376 KB
testcase_55 AC 13 ms
5,376 KB
testcase_56 AC 13 ms
5,376 KB
testcase_57 AC 13 ms
5,376 KB
testcase_58 AC 14 ms
5,376 KB
testcase_59 AC 14 ms
5,376 KB
testcase_60 AC 15 ms
5,376 KB
testcase_61 AC 15 ms
5,376 KB
testcase_62 AC 13 ms
5,376 KB
testcase_63 AC 14 ms
5,376 KB
testcase_64 AC 13 ms
5,376 KB
testcase_65 AC 1 ms
5,376 KB
testcase_66 AC 1 ms
5,376 KB
testcase_67 AC 11 ms
5,376 KB
testcase_68 AC 11 ms
5,376 KB
testcase_69 AC 12 ms
5,376 KB
testcase_70 AC 12 ms
5,376 KB
testcase_71 AC 2 ms
5,376 KB
testcase_72 AC 5 ms
5,376 KB
testcase_73 AC 5 ms
5,376 KB
testcase_74 AC 4 ms
5,376 KB
testcase_75 AC 15 ms
5,376 KB
testcase_76 AC 12 ms
5,376 KB
testcase_77 AC 16 ms
5,376 KB
testcase_78 AC 18 ms
5,376 KB
testcase_79 WA -
testcase_80 WA -
testcase_81 AC 13 ms
5,376 KB
testcase_82 AC 10 ms
5,376 KB
testcase_83 AC 4 ms
5,376 KB
testcase_84 AC 14 ms
5,376 KB
testcase_85 AC 4 ms
5,376 KB
testcase_86 AC 12 ms
5,376 KB
testcase_87 AC 16 ms
5,376 KB
testcase_88 AC 15 ms
5,376 KB
testcase_89 AC 1 ms
5,376 KB
testcase_90 AC 1 ms
5,376 KB
testcase_91 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'in':
main.c:11:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
   11 | #define gc() getchar_unlocked()
      |              ^~~~~~~~~~~~~~~~
main.c:17:24: note: in expansion of macro 'gc'
   17 |         int n = 0, c = gc();
      |                        ^~

ソースコード

diff #
プレゼンテーションモードにする

// yukicoder: No.738
// 2019.8.4 bal4u
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef long long ll;
#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif
int in() { //
int n = 0, c = gc();
do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
return n;
}
#define MAX 100005
typedef struct { int v, id; } QUE;
QUE qmin[MAX]; int szqmin;
QUE qmax[MAX]; int szqmax;
#define PARENT(i) ((i)>>1)
#define LEFT(i) ((i)<<1)
#define RIGHT(i) (((i)<<1)+1)
void min_heapify(int i) {
int l, r, min;
l = LEFT(i), r = RIGHT(i);
if (l < szqmin && (qmin[l].v < qmin[i].v ||
(qmin[l].v == qmin[i].v && qmin[l].id < qmin[i].id))) min = l; else min = i;
if (r < szqmin && (qmin[r].v < qmin[min].v ||
(qmin[r].v == qmin[min].v && qmin[r].id < qmin[min].id))) min = r;
if (min != i) {
QUE qt = qmin[i]; qmin[i] = qmin[min]; qmin[min] = qt;
min_heapify(min);
}
}
int deqmin() {
qmin[0] = qmin[--szqmin];
min_heapify(0);
return 1;
}
void enqmin(int id, int v) {
int i, min;
i = szqmin++;
qmin[i].id = id, qmin[i].v = v;
while (i > 0 && (qmin[min = PARENT(i)].v > qmin[i].v ||
(qmin[min].v == qmin[i].v && qmin[min].id > qmin[i].id))) {
QUE qt = qmin[i]; qmin[i] = qmin[min]; qmin[min] = qt;
i = min;
}
}
void max_heapify(int i) {
int l, r, max;
l = LEFT(i), r = RIGHT(i);
if (l < szqmax && (qmax[l].v > qmax[i].v ||
(qmax[l].v == qmax[i].v && qmax[l].id < qmax[i].id))) max = l; else max = i;
if (r < szqmax && (qmax[r].v > qmax[max].v ||
(qmax[r].v == qmax[max].v && qmax[r].id < qmax[max].id))) max = r;
if (max != i) {
QUE qt = qmax[i]; qmax[i] = qmax[max], qmax[max] = qt;
max_heapify(max);
}
}
void deqmax() {
qmax[0] = qmax[--szqmax];
max_heapify(0);
}
void enqmax(int id, int v) {
int i, max;
i = szqmax++;
qmax[i].id = id, qmax[i].v = v;
while (i > 0 && (qmax[max = PARENT(i)].v < qmax[i].v ||
(qmax[max].v == qmax[i].v && qmax[max].id > qmax[i].id))) {
QUE qt = qmax[i]; qmax[i] = qmax[max], qmax[max] = qt;
i = max;
}
}
#define ABS(x) ((x)>=0?(x):-(x))
int N;
int a[MAX]; QUE b[MAX];
int cmp(const void *a, const void *b) {
int t = ((QUE *)a)->v - ((QUE *)b)->v;
if (t) return t;
return ((QUE *)a)->id - ((QUE *)b)->id;
}
int main()
{
int i, K, k, m, pm, ngmin, ngmax, diff;
ll smin, smax, ans, t;
N = in(), K = in(), k = K >> 1;
if (K == 1) { puts("0"); return 0; }
#if 1
if (K == 2) {
m = in(), ans = 0x7fffffff;
while (--N) {
pm = m, m = in();
if ((t = ABS(pm-m)) < ans) ans = t;
}
goto done;
}
#endif
for (i = 0; i < N; i++) a[i] = in();
for (i = 0; i < K; i++) b[i].v = a[i], b[i].id = i;
qsort(b, K, sizeof(QUE), cmp);
m = b[k].v, smin = smax = 0, ngmin = ngmax = 0;
for (i = 0; i < k; i++) enqmax(b[i].id, b[i].v), smax += m-b[i].v;
for ( ; i < K; i++) enqmin(b[i].id, b[i].v), smin += b[i].v-m;
ans = smin + smax; if (ans == 0) goto done;
// printf("K=%d, k=%d, m=%d, szqmin=%d, szqmax=%d, smin=%lld, smax=%lld, ans=%lld\n",
// K, k, m, szqmin, szqmax, smin, smax, ans);
for (i = K; i < N; i++) {
int x = a[i-K];
if (x > qmin[0].v) ngmin++, smin -= x-m;
else if (x < qmax[0].v) ngmax++, smax -= m-x;
else if (i-K == qmin[0].id) deqmin(), smin -= x-m;
else if (i-K == qmax[0].id) deqmax(), smax -= m-x;
else { printf("Panic median=%d, a[%]=%d\n", m, i-K, a[i-K]); return 0; }
//printf("szqmin=%d, ngmin=%d, smin=%lld, sqzmax=%d, ngmax=%d, smax=%lld\n",
// szqmin, ngmin, smin, szqmax, ngmax, smax);
if (a[i] >= m) enqmin(i, a[i]), smin += a[i]-m;
else enqmax(i, a[i]), smax += m-a[i];
while (1) {
QUE qt;
diff = (szqmin-ngmin) - (szqmax-ngmax);
//printf("a[%d]=%d, diff=%d\n", i, a[i], diff);
if (K & 1) {
if (diff == 1) break;
} else if (diff == 0) break;
if (diff > 0) {
qt = qmin[0], deqmin();
if (qt.id <= i-K) ngmin--;
else enqmax(qt.id, qt.v), smin -= qt.v-m, smax += m-qt.v;
} else {
qt = qmax[0], deqmax();
if (qt.id <= i-K) ngmax--;
else enqmin(qt.id, qt.v), smin += qt.v-m, smax -= m-qt.v;
}
}
pm = m;
if (diff >= 0) m = qmin[0].v; else m = qmax[0].v;
if (m != pm) smin += (pm-m) * (szqmin-ngmin), smax += (m-pm)*(szqmax-ngmax);
t = smin + smax; if (t < ans) { ans = t; if (ans == 0) goto done; }
//printf("pm=%d, m=%d, smin=%lld, smax=%lld, t=%lld, ans=%lld\n\n", pm,m,smin,smax,t,ans);
}
done:
printf("%lld\n", ans);
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0