CSES - Aalto Competitive Programming 2024 - wk3 - Mon - Results
Submission details
Task:Particle accelerator
Sender:louaha1
Submission time:2024-09-16 17:47:06 +0300
Language:C++ (C++11)
Status:COMPILE ERROR

Compiler report

input/code.cpp: In function 'long long int calculate_min_cost(int, const std::vector<long long int>&)':
input/code.cpp:16:73: error: 'LLONG_MAX' was not declared in this scope
   16 |     vector<vector<long long>> cost_matrix(size, vector<long long>(size, LLONG_MAX));
      |                                                                         ^~~~~~~~~
input/code.cpp:4:1: note: 'LLONG_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
    3 | #include <limits>
  +++ |+#include <climits>
    4 | using namespace std;

Code

#include <iostream>
#include <vector>
#include <limits>
using namespace std;

long long compute_mass(const vector<long long>& prefix_sum, int start, int end) {
    return prefix_sum[end + 1] - prefix_sum[start];
}

long long calculate_min_cost(int size, const vector<long long>& values) {
    vector<long long> prefix_sum(size + 1, 0);
    for (int index = 0; index < size; ++index) {
        prefix_sum[index + 1] = prefix_sum[index] + values[index];
    }

    vector<vector<long long>> cost_matrix(size, vector<long long>(size, LLONG_MAX));

    for (int index = 0; index < size; ++index) {
        cost_matrix[index][index] = 0;
    }

    for (int len = 2; len <= size; ++len) {
        for (int start = 0; start <= size - len; ++start) {
            int end = start + len - 1;

            for (int split = start; split < end; ++split) {
                long long left_mass = compute_mass(prefix_sum, start, split);
                long long right_mass = compute_mass(prefix_sum, split + 1, end);
                long long segment_mass = left_mass * right_mass;
                long long min_mass = min(left_mass, right_mass);
                long long current_cost = cost_matrix[start][split] + cost_matrix[split + 1][end] + segment_mass - min_mass * min_mass;
                cost_matrix[start][end] = min(cost_matrix[start][end], current_cost);
            }
        }
    }

    return cost_matrix[0][size - 1];
}

int main() {
    int size;
    cin >> size;
    vector<long long> values(size);
    for (int index = 0; index < size; ++index) {
        cin >> values[index];
    }
    cout << calculate_min_cost(size, values) << endl;
    return 0;
}