Submission #516841

#	Time	Username	Problem	Language	Result	Execution time	Memory
516841		Be_dos	K blocks (IZhO14_blocks)	C++17	53 / 100	1086 ms	452 KiB

blocks

#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
#include <cassert>

#define INF 1'000'000'000

int32_t* arr;
void advance(int32_t n, int32_t* dp, int32_t* dp2) {
    dp2[0] = INF;
    for(int32_t i = 1; i <= n; i++) {
        dp2[i] = INF;
        int32_t max_ = 0;
        for(int32_t j = i - 1; j >= 0; j--) {
            max_ = std::max(max_, arr[j]);
            dp2[i] = std::min(dp2[i], dp[j] + max_);
        }
    }
}

int main() {
    int32_t n, k;
    std::cin >> n >> k;

    arr = new int32_t[n];
    for(int32_t i = 0; i < n; i++)
        std::cin >> arr[i];

    int32_t* dp = new int32_t[n + 1];
    dp[0] = 0;
    for(int32_t i = 1; i <= n; i++)
        dp[i] = std::max(dp[i - 1], arr[i - 1]);
    dp[0] = INF;

    int32_t* dp2 = new int32_t[n + 1];
    for(int32_t i = 1; i < k; i++) {
        advance(n, dp, dp2);

        int32_t* tmp = dp;
        dp = dp2;
        dp2 = tmp;
    }

    std::cout << dp[n];
    return 0;
}
         

• Subtask 1: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 0 / 47