Submission #1571408
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; i64 get_i64() { int c; i64 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<i64> A(N); rep(i, N) A[i] = get_i64(); printf("%llu\n", optimal_alphabetic_tree<i64>(A)); } } 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 | J - 刺身 |
User | Min_25 |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1974 Byte |
Status | AC |
Exec Time | 10 ms |
Memory | 256 KB |
Judge Result
Set Name | Partial 1 | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 3 / 3 | 97 / 97 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Partial 1 | 00_Teuchi_00, 00_Teuchi_01, 00_alternate_0, 00_alternate_1, 00_alternate_2, 00_alternate_3, 00_alternate_4, 00_alternate_5, 00_random_0, 00_random_1, 00_random_2, 00_random_3, 00_random_4, 00_random_5, 00_random_6, 00_random_7, 00_random_8, 00_sample_00, 00_sample_01, 00_sample_02, 00_sorted_0, 00_sorted_1, 00_sorted_2 |
All | 00_Teuchi_00, 00_Teuchi_01, 00_alternate_0, 00_alternate_1, 00_alternate_2, 00_alternate_3, 00_alternate_4, 00_alternate_5, 00_random_0, 00_random_1, 00_random_2, 00_random_3, 00_random_4, 00_random_5, 00_random_6, 00_random_7, 00_random_8, 00_sample_00, 00_sample_01, 00_sample_02, 00_sorted_0, 00_sorted_1, 00_sorted_2, 20_random_11, 20_random_12, 40_alternate_6, 40_alternate_7, 40_alternate_8, 40_alternate_9, 40_random_10, 40_random_13, 40_random_14, 40_random_15, 40_random_16, 40_random_17, 40_random_18, 40_random_19, 40_random_9, 40_sorted_3, 40_sorted_4, 40_sorted_5, 99_Teuchi_00, 99_Teuchi_01, 99_Teuchi_02 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_Teuchi_00 | AC | 1 ms | 256 KB |
00_Teuchi_01 | AC | 1 ms | 256 KB |
00_alternate_0 | AC | 1 ms | 256 KB |
00_alternate_1 | AC | 1 ms | 256 KB |
00_alternate_2 | AC | 1 ms | 256 KB |
00_alternate_3 | AC | 1 ms | 256 KB |
00_alternate_4 | AC | 1 ms | 256 KB |
00_alternate_5 | AC | 1 ms | 256 KB |
00_random_0 | AC | 1 ms | 256 KB |
00_random_1 | AC | 1 ms | 256 KB |
00_random_2 | AC | 1 ms | 256 KB |
00_random_3 | AC | 1 ms | 256 KB |
00_random_4 | AC | 1 ms | 256 KB |
00_random_5 | AC | 1 ms | 256 KB |
00_random_6 | AC | 1 ms | 256 KB |
00_random_7 | AC | 1 ms | 256 KB |
00_random_8 | AC | 1 ms | 256 KB |
00_sample_00 | AC | 1 ms | 256 KB |
00_sample_01 | AC | 1 ms | 256 KB |
00_sample_02 | AC | 1 ms | 256 KB |
00_sorted_0 | AC | 1 ms | 256 KB |
00_sorted_1 | AC | 1 ms | 256 KB |
00_sorted_2 | AC | 1 ms | 256 KB |
20_random_11 | AC | 2 ms | 256 KB |
20_random_12 | AC | 2 ms | 256 KB |
40_alternate_6 | AC | 5 ms | 256 KB |
40_alternate_7 | AC | 5 ms | 256 KB |
40_alternate_8 | AC | 3 ms | 256 KB |
40_alternate_9 | AC | 3 ms | 256 KB |
40_random_10 | AC | 3 ms | 256 KB |
40_random_13 | AC | 3 ms | 256 KB |
40_random_14 | AC | 3 ms | 256 KB |
40_random_15 | AC | 3 ms | 256 KB |
40_random_16 | AC | 3 ms | 256 KB |
40_random_17 | AC | 5 ms | 256 KB |
40_random_18 | AC | 5 ms | 256 KB |
40_random_19 | AC | 5 ms | 256 KB |
40_random_9 | AC | 3 ms | 256 KB |
40_sorted_3 | AC | 7 ms | 256 KB |
40_sorted_4 | AC | 7 ms | 256 KB |
40_sorted_5 | AC | 10 ms | 256 KB |
99_Teuchi_00 | AC | 4 ms | 256 KB |
99_Teuchi_01 | AC | 3 ms | 256 KB |
99_Teuchi_02 | AC | 3 ms | 256 KB |