제출 #1282284

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

blocks

/*
 * @Author: RMQuan
 * @Date: 2025-10-23 03:40:00
 * @Last Modified by: RMQuan
 * @Last Modified time: 2025-10-23 03:40:00
 */
/*idea :
   dp[j][i] = min_{t<i}(dp[j-1][t] + max_{t+1..i} a)
   => dùng L[i] = chỉ số gần nhất bên trái có a[L[i]] > a[i]
   thì a[i] là max cho vùng (L[i], i]
   => dp[j][i] = min( dp[j][L[i]], min_{t∈[max(L[i], j-1)..i-1]} dp[j-1][t] + a[i] )
   => min vùng dùng Sparse Table.
*/

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define endl '\n'
#define TASK "TEST"
#define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
bool M1;

const int maxn = 1e5 + 7;
const int LOG = 17;
const int INF = 1e18;

int n, k, a[maxn];
int L[maxn];
int lg2[maxn];
long long dp[105][maxn];
long long st[LOG][maxn];

void build(int r) {
    for (int i = 1; i <= n; i++) st[0][i] = dp[r][i];
    for (int j = 1; j <= lg2[n]; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            st[j][i] = min(st[j-1][i], st[j-1][i + (1 << (j-1))]);
}
long long getmin(int l, int r) {
    if (l > r) return INF;
    int j = lg2[r - l + 1];
    return min(st[j][l], st[j][r - (1 << j) + 1]);
}

void prep() {
    stack<int> st;
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && a[st.top()] <= a[i]) st.pop();
        if (!st.empty()) L[i] = st.top();
        else L[i] = 0;
        st.push(i);
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    file();

    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 2; i <= n; i++) lg2[i] = lg2[i/2] + 1;

    prep();

    for (int i = 0; i <= k; i++)
        for (int j = 0; j <= n; j++)
            dp[i][j] = INF;
    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], getmin(max(i-1, L[j]), j-1) + a[j]);
        }
    }

    cout << dp[k][n] << endl;

    bool M2;
    cerr << "------------------------------------------" << endl;
    cerr << "Time : " << clock() << " ms" << endl;
    cerr << "Memory : " << abs(&M2 - &M1) / 1024.0 / 1024.0 << " MB" << endl;
    cerr << "------------------------------------------" << endl;
    return 0;
}

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

blocks.cpp: In function 'int32_t main()':
blocks.cpp:22:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | #define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
      |                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:61:5: note: in expansion of macro 'file'
   61 |     file();
      |     ^~~~
blocks.cpp:22:81: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | #define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
      |                                                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:61:5: note: in expansion of macro 'file'
   61 |     file();
      |     ^~~~

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