제출 #1273820

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273820		dung3683833	K개의 묶음 (IZhO14_blocks)	C++20	100 / 100	220 ms	93144 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
int a[N];
ll st[25][N];
int L[N];
int n, k;
ll dp[105][N];
int lg[N];
inline void build(int r) {
    for (int i = 1; i <= n; i++) {
        st[0][i] = dp[r][i];
    }
    for (int i = 1; i <= lg[n]; i++) {
        for (int j = 1; j + (1 << i) - 1 <= n; j++) {
            st[i][j] = min(st[i-1][j], st[i-1][j + (1 << (i-1))]);
        }
    }
}
inline ll get(int l, int r) {
    int i = lg[r - l + 1];
    return min(st[i][l], st[i][r - (1 << i) + 1]);
}
void prep() {
    stack<int> st;
    for (int i = 1; i <= n; i++) {
        while (st.size() && a[st.top()] <= a[i]) st.pop();
        if (st.size()) L[i] = st.top();
        st.push(i);
    }
}
signed main() {
    if (fopen("I.inp", "r")) {
        freopen("I.inp", "r", stdin);
        freopen("I.out", "w", stdout);
    }
    for (int i = 2; i < N; i++) lg[i] = lg[i/2] + 1;
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    prep();
    for (int i = 0; i <= k; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = 1e18;
        }
    }
    dp[0][0] = 0;
    for (int i = 1; i <= k; i++) {
        build(i-1);
        for (int j = 1; j <= n; j++) {
            if (j < i) continue;
            if (L[j] >= i) dp[i][j] = dp[i][L[j]];
            dp[i][j] = min(dp[i][j], get(max(i-1, L[j]), j-1) + a[j]);
            // cerr << i-1 << ' ' << L[j] << ' ' << get(max(i-1, L[j]), j-1) << endl;
        }
    }
    cout << dp[k][n];
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

blocks.cpp: In function 'int main()':
blocks.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         freopen("I.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
blocks.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen("I.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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