#306241 (C++14) No.777 再帰的ケーキ

• 問題: No.777 再帰的ケーキ
• ユーザー: kriii
• 提出日時: 2018-12-24 00:04:20
• 言語: C++14 (gcc 13.2.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 117 ms / 2,000 ms
• コード長: 833 bytes
• コンパイル時間: 1,007 ms
• コンパイル使用メモリ: 48,032 KB
• 実行使用メモリ: 7,088 KB
• 最終ジャッジ日時: 2023-10-26 02:46:46
• 合計ジャッジ時間: 5,661 ms
• ジャッジサーバーID （参考情報）: judge15 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,232 KB
testcase_01	AC	2 ms; 5,232 KB
testcase_02	AC	2 ms; 5,232 KB
testcase_03	AC	2 ms; 5,232 KB
testcase_04	AC	2 ms; 5,232 KB
testcase_05	AC	2 ms; 5,232 KB
testcase_06	AC	2 ms; 5,232 KB
testcase_07	AC	2 ms; 5,232 KB
testcase_08	AC	2 ms; 5,232 KB
testcase_09	AC	2 ms; 5,232 KB
testcase_10	AC	2 ms; 5,232 KB
testcase_11	AC	2 ms; 5,232 KB
testcase_12	AC	2 ms; 5,232 KB
testcase_13	AC	2 ms; 5,232 KB
testcase_14	AC	2 ms; 5,232 KB
testcase_15	AC	2 ms; 5,232 KB
testcase_16	AC	2 ms; 5,232 KB
testcase_17	AC	2 ms; 5,232 KB
testcase_18	AC	2 ms; 5,232 KB
testcase_19	AC	2 ms; 5,232 KB
testcase_20	AC	3 ms; 5,232 KB
testcase_21	AC	3 ms; 5,244 KB
testcase_22	AC	3 ms; 5,244 KB
testcase_23	AC	3 ms; 5,232 KB
testcase_24	AC	3 ms; 5,232 KB
testcase_25	AC	3 ms; 5,244 KB
testcase_26	AC	3 ms; 5,244 KB
testcase_27	AC	3 ms; 5,232 KB
testcase_28	AC	107 ms; 7,088 KB
testcase_29	AC	106 ms; 7,088 KB
testcase_30	AC	116 ms; 7,088 KB
testcase_31	AC	117 ms; 7,088 KB
testcase_32	AC	74 ms; 7,088 KB
testcase_33	AC	42 ms; 5,640 KB
testcase_34	AC	63 ms; 6,420 KB
testcase_35	AC	108 ms; 7,088 KB
testcase_36	AC	73 ms; 7,088 KB

ソースコード

#include <stdio.h>
#include <algorithm>
using namespace std;

struct Cake{
	int a,b,c;
	bool operator <(const Cake &t)const{
		if (a != t.a) return a < t.a;
		return b > t.b;
	}
}C[200200];

int N,V;
long long B[200200];

void push(int x, long long u)
{
	while (x <= V){
		B[x] = max(B[x],u);
		x += x & (-x);
	}
}

long long pop(int x)
{
	long long r = 0;
	while (x){
		r = max(r,B[x]);
		x -= x & (-x);
	}
	return r;
}

int main()
{
	scanf ("%d",&N);
	for (int i=0;i<N;i++) scanf ("%d %d %d",&C[i].a,&C[i].b,&C[i].c);
	sort(C,C+N,[](const Cake& a, const Cake& b){
		return a.b < b.b;
	});

	int l = -1;
	for (int i=0;i<N;i++){
		if (C[i].b != l){
			l = C[i].b;
			V++;
		}
		C[i].b = V;
	}

	sort(C,C+N);
	for (int i=0;i<N;i++){
		long long u = pop(C[i].b-1) + C[i].c;
		push(C[i].b,u);
	}

	printf("%lld\n",pop(V));

	return 0;
}