Submission #30233
Source Code Expand
#include <iostream> #include <stdint.h> #include <vector> using namespace std; int main() { int n; cin >> n; vector< uint64_t > xs(n); for(int i = 0; i < n; ++i) cin >> xs[i]; vector< vector< uint64_t > > table(n, vector< uint64_t >(n, 1e16)); for(int i = 0; i < n; ++i) table[i][i] = 0; for(int len = 1; len < n; ++len) { for (int i = 0; i < n; ++i) { if (n <= i+len) break; uint64_t total = 0; uint64_t v = table[i][i+len]; for (int j = i; j <= i+len; ++j) total += xs[j]; for (int j = i; j < i+len; ++j) v = min(v, table[i][j]+table[j+1][i+len]+total); table[i][i+len] = v; } } cout << table[0][n-1] << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | J - 刺身 |
User | notogawa |
Language | C++ (G++ 4.6.4) |
Score | 3 |
Code Size | 810 Byte |
Status | TLE |
Exec Time | 3051 ms |
Memory | 126164 KB |
Judge Result
Set Name | Partial 1 | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 3 / 3 | 0 / 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 | 21 ms | 788 KB |
00_Teuchi_01 | AC | 22 ms | 784 KB |
00_alternate_0 | AC | 21 ms | 788 KB |
00_alternate_1 | AC | 21 ms | 788 KB |
00_alternate_2 | AC | 21 ms | 788 KB |
00_alternate_3 | AC | 22 ms | 888 KB |
00_alternate_4 | AC | 21 ms | 756 KB |
00_alternate_5 | AC | 23 ms | 780 KB |
00_random_0 | AC | 23 ms | 780 KB |
00_random_1 | AC | 21 ms | 788 KB |
00_random_2 | AC | 21 ms | 780 KB |
00_random_3 | AC | 22 ms | 788 KB |
00_random_4 | AC | 20 ms | 764 KB |
00_random_5 | AC | 22 ms | 772 KB |
00_random_6 | AC | 22 ms | 768 KB |
00_random_7 | AC | 21 ms | 784 KB |
00_random_8 | AC | 20 ms | 788 KB |
00_sample_00 | AC | 22 ms | 744 KB |
00_sample_01 | AC | 22 ms | 792 KB |
00_sample_02 | AC | 23 ms | 776 KB |
00_sorted_0 | AC | 21 ms | 788 KB |
00_sorted_1 | AC | 22 ms | 788 KB |
00_sorted_2 | AC | 20 ms | 812 KB |
20_random_11 | TLE | 3035 ms | 33652 KB |
20_random_12 | TLE | 3035 ms | 33784 KB |
40_alternate_6 | TLE | 3047 ms | 126076 KB |
40_alternate_7 | TLE | 3048 ms | 126064 KB |
40_alternate_8 | TLE | 3045 ms | 126072 KB |
40_alternate_9 | TLE | 3050 ms | 126072 KB |
40_random_10 | TLE | 3049 ms | 126072 KB |
40_random_13 | TLE | 3051 ms | 126084 KB |
40_random_14 | TLE | 3049 ms | 126072 KB |
40_random_15 | TLE | 3050 ms | 126132 KB |
40_random_16 | TLE | 3047 ms | 126064 KB |
40_random_17 | TLE | 3051 ms | 126164 KB |
40_random_18 | TLE | 3049 ms | 126068 KB |
40_random_19 | TLE | 3047 ms | 126072 KB |
40_random_9 | TLE | 3043 ms | 126084 KB |
40_sorted_3 | TLE | 3046 ms | 126076 KB |
40_sorted_4 | TLE | 3049 ms | 126064 KB |
40_sorted_5 | TLE | 3050 ms | 126072 KB |
99_Teuchi_00 | TLE | 3050 ms | 126068 KB |
99_Teuchi_01 | TLE | 3051 ms | 126068 KB |
99_Teuchi_02 | TLE | 3047 ms | 126080 KB |