結果
問題 | No.777 再帰的ケーキ |
ユーザー | bal4u |
提出日時 | 2019-08-25 11:38:28 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 126 ms / 2,000 ms |
コード長 | 1,852 bytes |
コンパイル時間 | 577 ms |
コンパイル使用メモリ | 31,616 KB |
実行使用メモリ | 7,956 KB |
最終ジャッジ日時 | 2024-04-24 00:39:03 |
合計ジャッジ時間 | 3,531 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 2 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 | 1 ms
5,376 KB |
testcase_16 | AC | 1 ms
5,376 KB |
testcase_17 | AC | 1 ms
5,376 KB |
testcase_18 | AC | 1 ms
5,376 KB |
testcase_19 | AC | 1 ms
5,376 KB |
testcase_20 | AC | 1 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 1 ms
5,376 KB |
testcase_24 | AC | 1 ms
5,376 KB |
testcase_25 | AC | 2 ms
5,376 KB |
testcase_26 | AC | 2 ms
5,376 KB |
testcase_27 | AC | 2 ms
5,376 KB |
testcase_28 | AC | 122 ms
7,952 KB |
testcase_29 | AC | 121 ms
7,948 KB |
testcase_30 | AC | 126 ms
7,952 KB |
testcase_31 | AC | 126 ms
7,956 KB |
testcase_32 | AC | 56 ms
6,800 KB |
testcase_33 | AC | 48 ms
5,376 KB |
testcase_34 | AC | 75 ms
6,144 KB |
testcase_35 | AC | 104 ms
7,180 KB |
testcase_36 | AC | 58 ms
6,800 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(); | ^~
ソースコード
// yukicoder: No.777 再帰的ケーキ // bal4u 2019.8.25 #include <stdio.h> #include <stdlib.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; } inline static void chmax(ll *a, ll b) { if (*a < b) *a = b; } //// bit木 1-indexedに注意 #define MAX 200005 ll bit[MAX]; int bitn; //void add(int i) { while (i <= bitn) bit[i]++, i += i & -i; } //int sum(int i) { int s = 0; while (i > 0) s += bit[i], i -= i & -i; return s; } void update(int i, ll v) { while (i <= bitn && bit[i] < v) bit[i] = v, i += i & -i; } ll maxv(int i) { ll ma = 0; while (i > 0) chmax(&ma, bit[i]), i -= i & -i; return ma; } //// 本問題関連 typedef struct { int a, b, c; } T; T t[MAX];int N; int cmpb(const void *u, const void *v) { // b昇順, a昇順, c降順 int t; if (t = ((T *)u)->b - ((T *)v)->b) return t; if (t = ((T *)u)->a - ((T *)v)->a) return t; return ((T *)v)->c - ((T *)u)->c; } void compact() { int i, v, b; qsort(t, N, sizeof(T), cmpb); b = t[0].b, v = 1, t[0].b = v; for (i = 1; i < N; i++) { if (t[i].b == b) t[i].b = (t[i].a == t[i-1].a)? 0: v; else b = t[i].b, t[i].b = ++v; } } int cmp(const void *u, const void *v) { // a昇順, b降順 int t; if (t = ((T *)u)->a - ((T *)v)->a) return t; return ((T *)v)->b - ((T *)u)->b; } int main() { int i; N = in(); for (i = 0; i < N; i++) { t[i].a = in(), t[i].b = in(), t[i].c = in(); } compact(); // データ圧縮 qsort(t, N, sizeof(T), cmp); //for (i = 0; i < N; i++) printf("[%d] (%d,%d,%d)\n", i, t[i].a, t[i].b, t[i].c); bitn = N+1; for (i = 0; i < N; i++) if (t[i].b) update(t[i].b+1, maxv(t[i].b) + t[i].c); printf("%lld\n", maxv(N+1)); return 0; }