제출 #516919

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
516919		Be_dos	K개의 묶음 (IZhO14_blocks)	C++17	100 / 100	212 ms	2572 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

struct Segment {
    int32_t val;
    int32_t dp_min;

    int32_t stack_min;

    Segment(int32_t val_, int32_t dp_min_, int32_t stack_min_) {
        val = val_;
        dp_min = dp_min_;
        stack_min = stack_min_;
    }
};

int32_t* arr;
void advance(int32_t n, int32_t* dp, int32_t* dp2) {
    dp2[0] = INF;
    std::stack<Segment> segments;
    for(int32_t i = 1; i <= n; i++) {
        int32_t min_new = dp[i - 1];
        while(segments.size() > 0 && segments.top().val <= arr[i - 1]) {
            min_new = std::min(min_new, segments.top().dp_min);
            segments.pop();
        }
        segments.emplace(arr[i - 1], min_new, std::min(min_new + arr[i - 1], segments.empty() ? INF : segments.top().stack_min));

        dp2[i] = segments.top().stack_min;
    }
}

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

    arr = new int32_t[n];
    std::mt19937 rng;
    for(int32_t i = 0; i < n; i++)
        std::cin >> arr[i];
        //arr[i] = rng() % 100;

    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: 47 / 47