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
AC × 23
AC × 23
TLE × 21
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