結果
問題 | No.777 再帰的ケーキ |
ユーザー |
![]() |
提出日時 | 2019-08-25 10:55:35 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 110 ms / 2,000 ms |
コード長 | 1,887 bytes |
コンパイル時間 | 1,316 ms |
コンパイル使用メモリ | 30,464 KB |
実行使用メモリ | 12,668 KB |
最終ジャッジ日時 | 2024-11-06 04:41:58 |
合計ジャッジ時間 | 3,843 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 33 |
コンパイルメッセージ
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()#endifint 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 200005ll 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, id; } T;T t[MAX];int N;T s[MAX];int cmpb(const void *u, const void *v) { return ((T *)u)->b - ((T *)v)->b; } // b昇順void compact() {int i, v;s[0] = t[0];for (i = 1; i < N; i++) {if (t[i].a == t[i-1].a && t[i].b == t[i-1].b) t[i].b = 0;else s[i] = t[i], s[i].id = i;}qsort(s, N, sizeof(T), cmpb);v = 1; t[s[0].id].b = v;for (i = 1; i < N; i++) {if (s[i].b != s[i-1].b) v++;t[s[i].id].b = v;}}int cmp(const void *u, const void *v) { // a昇順, b降順, c降順int t;if (t = ((T *)u)->a - ((T *)v)->a) return t;if (t = ((T *)v)->b - ((T *)u)->b) return t;return ((T *)v)->c - ((T *)u)->c;}int main(){int i;N = in(); for (i = 0; i < N; i++) {t[i].a = in(), t[i].b = in(), t[i].c = in();}qsort(t, N, sizeof(T), cmp);compact(); // データ圧縮//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;}