Submission #1570452
Source Code Expand
#include <cstdio> #include <cassert> #include <cmath> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <map> #include <set> #include <functional> #include <stack> #include <queue> #include <tuple> #define getchar getchar_unlocked #define putchar putchar_unlocked #define _rep(_1, _2, _3, _4, name, ...) name #define rep2(i, n) rep3(i, 0, n) #define rep3(i, a, b) rep4(i, a, b, 1) #define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c)) #define rep(...) _rep(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__) using namespace std; using i64 = long long; using u8 = unsigned char; using u32 = unsigned; using u64 = unsigned long long; using f80 = long double; int get_int() { int c, n; while ((c = getchar()) < '0'); n = c - '0'; while ((c = getchar()) >= '0') n = n * 10 + (c - '0'); return n; } template <typename T> __attribute__((target("avx"), optimize("-O3"))) i64 optimal_alphabetic_tree(const vector<T>& A) { constexpr T Inf = T(1) << (sizeof(T) * 8 - 2); int N = A.size(); vector<T> S(N + 2); S[0] = S[N + 1] = Inf; for (int i = 1; i <= N; ++i) S[i] = A[i - 1]; i64 ret = 0; int first = 1; while (N > 1) { for (int i = first; i < N; ++i) if (S[i - 1] > S[i + 1] && S[i] <= S[i + 2]) { T w = S[i] + S[i + 1]; ret += w; for (int j = i + 1; j <= N; ++j) S[j] = S[j + 1]; for (int j = i - 1; j >= 0; --j) { if (S[j] < w) S[j + 1] = S[j]; else { S[j + 1] = w; first = max(1, j - 1); break; } } --N; break; } } return ret; } void solve() { int N; while (~scanf("%d", &N)) { vector<int> A(N); rep(i, N) A[i] = get_int(); auto ans = optimal_alphabetic_tree<int>(A); printf("%llu\n", ans); } } int main() { clock_t beg = clock(); solve(); clock_t end = clock(); fprintf(stderr, "%.3f sec\n", double(end - beg) / CLOCKS_PER_SEC); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 最適二分探索木 |
User | Min_25 |
Language | C++14 (GCC 5.4.1) |
Score | 101 |
Code Size | 1996 Byte |
Status | AC |
Exec Time | 774 ms |
Memory | 1024 KB |
Judge Result
Set Name | Sample | Dataset1 | Dataset2 | Dataset3 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 50 / 50 | 50 / 50 | 1 / 1 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_01.txt |
Dataset1 | 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt |
Dataset2 | 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt, 02_00.txt, 02_01.txt, 02_02.txt, 02_03.txt, 02_04.txt, 02_05.txt, 02_06.txt, 02_07.txt, 02_08.txt, 02_09.txt, 02_10.txt, 02_11.txt, 02_12.txt, 02_13.txt, 02_14.txt, 02_15.txt, 02_16.txt, 02_17.txt, 02_18.txt, 02_19.txt, 02_20.txt, 02_21.txt, 02_22.txt, 02_23.txt, 02_24.txt, 02_25.txt, 02_26.txt, 02_27.txt, 02_28.txt, 02_29.txt |
Dataset3 | 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt, 02_00.txt, 02_01.txt, 02_02.txt, 02_03.txt, 02_04.txt, 02_05.txt, 02_06.txt, 02_07.txt, 02_08.txt, 02_09.txt, 02_10.txt, 02_11.txt, 02_12.txt, 02_13.txt, 02_14.txt, 02_15.txt, 02_16.txt, 02_17.txt, 02_18.txt, 02_19.txt, 02_20.txt, 02_21.txt, 02_22.txt, 02_23.txt, 02_24.txt, 02_25.txt, 02_26.txt, 02_27.txt, 02_28.txt, 02_29.txt, 03_00.txt, 03_01.txt, 03_02.txt, 03_03.txt, 03_04.txt, 03_05.txt, 03_06.txt, 03_07.txt, 03_08.txt, 03_09.txt, 03_10.txt, 03_11.txt, 03_12.txt, 03_13.txt, 03_14.txt, 03_15.txt, 03_16.txt, 03_17.txt, 03_18.txt, 03_19.txt, 03_20.txt, 03_21.txt, 03_22.txt, 03_23.txt, 03_24.txt, 03_25.txt, 03_26.txt, 03_27.txt, 03_28.txt, 03_29.txt, 03_30.txt, 03_31.txt, 03_32.txt, 03_33.txt, 03_34.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_01.txt | AC | 1 ms | 256 KB |
01_00.txt | AC | 1 ms | 256 KB |
01_01.txt | AC | 1 ms | 256 KB |
01_02.txt | AC | 1 ms | 256 KB |
01_03.txt | AC | 1 ms | 256 KB |
01_04.txt | AC | 1 ms | 256 KB |
01_05.txt | AC | 1 ms | 256 KB |
01_06.txt | AC | 1 ms | 256 KB |
01_07.txt | AC | 1 ms | 256 KB |
01_08.txt | AC | 1 ms | 256 KB |
01_09.txt | AC | 1 ms | 256 KB |
01_10.txt | AC | 1 ms | 256 KB |
01_11.txt | AC | 1 ms | 256 KB |
01_12.txt | AC | 1 ms | 256 KB |
01_13.txt | AC | 1 ms | 256 KB |
01_14.txt | AC | 1 ms | 256 KB |
01_15.txt | AC | 1 ms | 256 KB |
01_16.txt | AC | 1 ms | 256 KB |
01_17.txt | AC | 1 ms | 256 KB |
01_18.txt | AC | 1 ms | 256 KB |
01_19.txt | AC | 1 ms | 256 KB |
01_20.txt | AC | 1 ms | 256 KB |
01_21.txt | AC | 1 ms | 256 KB |
01_22.txt | AC | 1 ms | 256 KB |
01_23.txt | AC | 1 ms | 256 KB |
01_24.txt | AC | 1 ms | 256 KB |
01_25.txt | AC | 1 ms | 256 KB |
01_26.txt | AC | 1 ms | 256 KB |
01_27.txt | AC | 1 ms | 256 KB |
01_28.txt | AC | 1 ms | 256 KB |
01_29.txt | AC | 1 ms | 256 KB |
02_00.txt | AC | 2 ms | 256 KB |
02_01.txt | AC | 2 ms | 256 KB |
02_02.txt | AC | 2 ms | 256 KB |
02_03.txt | AC | 2 ms | 256 KB |
02_04.txt | AC | 2 ms | 256 KB |
02_05.txt | AC | 2 ms | 256 KB |
02_06.txt | AC | 2 ms | 256 KB |
02_07.txt | AC | 2 ms | 256 KB |
02_08.txt | AC | 2 ms | 256 KB |
02_09.txt | AC | 2 ms | 256 KB |
02_10.txt | AC | 2 ms | 256 KB |
02_11.txt | AC | 2 ms | 256 KB |
02_12.txt | AC | 2 ms | 256 KB |
02_13.txt | AC | 2 ms | 256 KB |
02_14.txt | AC | 2 ms | 256 KB |
02_15.txt | AC | 2 ms | 256 KB |
02_16.txt | AC | 2 ms | 256 KB |
02_17.txt | AC | 2 ms | 256 KB |
02_18.txt | AC | 2 ms | 256 KB |
02_19.txt | AC | 2 ms | 256 KB |
02_20.txt | AC | 2 ms | 256 KB |
02_21.txt | AC | 2 ms | 256 KB |
02_22.txt | AC | 2 ms | 256 KB |
02_23.txt | AC | 2 ms | 256 KB |
02_24.txt | AC | 2 ms | 256 KB |
02_25.txt | AC | 2 ms | 256 KB |
02_26.txt | AC | 2 ms | 256 KB |
02_27.txt | AC | 2 ms | 256 KB |
02_28.txt | AC | 2 ms | 256 KB |
02_29.txt | AC | 2 ms | 256 KB |
03_00.txt | AC | 739 ms | 1024 KB |
03_01.txt | AC | 734 ms | 1024 KB |
03_02.txt | AC | 734 ms | 1024 KB |
03_03.txt | AC | 735 ms | 1024 KB |
03_04.txt | AC | 734 ms | 1024 KB |
03_05.txt | AC | 707 ms | 1024 KB |
03_06.txt | AC | 697 ms | 1024 KB |
03_07.txt | AC | 705 ms | 1024 KB |
03_08.txt | AC | 705 ms | 1024 KB |
03_09.txt | AC | 705 ms | 1024 KB |
03_10.txt | AC | 708 ms | 1024 KB |
03_11.txt | AC | 716 ms | 1024 KB |
03_12.txt | AC | 705 ms | 1024 KB |
03_13.txt | AC | 709 ms | 1024 KB |
03_14.txt | AC | 708 ms | 1024 KB |
03_15.txt | AC | 706 ms | 1024 KB |
03_16.txt | AC | 708 ms | 1024 KB |
03_17.txt | AC | 745 ms | 1024 KB |
03_18.txt | AC | 698 ms | 1024 KB |
03_19.txt | AC | 711 ms | 1024 KB |
03_20.txt | AC | 708 ms | 1024 KB |
03_21.txt | AC | 705 ms | 1024 KB |
03_22.txt | AC | 707 ms | 1024 KB |
03_23.txt | AC | 758 ms | 1024 KB |
03_24.txt | AC | 703 ms | 1024 KB |
03_25.txt | AC | 710 ms | 1024 KB |
03_26.txt | AC | 707 ms | 1024 KB |
03_27.txt | AC | 705 ms | 1024 KB |
03_28.txt | AC | 710 ms | 1024 KB |
03_29.txt | AC | 774 ms | 1024 KB |
03_30.txt | AC | 716 ms | 1024 KB |
03_31.txt | AC | 707 ms | 1024 KB |
03_32.txt | AC | 709 ms | 1024 KB |
03_33.txt | AC | 706 ms | 1024 KB |
03_34.txt | AC | 709 ms | 1024 KB |