Submission #1089723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089723		TooruLuoiDiHoc	K blocks (IZhO14_blocks)	C++14	100 / 100	146 ms	42904 KiB

blocks

/*
Link: https://oj.uz/problem/submit/IZhO14_blocks
*/
#include <bits/stdc++.h>
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define __builtin_popcount __builtin_popcountll
#define __builtin_ctz __builtin_ctzll
#define For(i, a, b) for(int i = (int)(a); i <= (int)(b); ++i)
#define Fod(i, a, b) for(int i = (int)(a); i >= (int)(b); --i)
//#define int long long
#define ll long long
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define whole(a) a.begin(), a.end()
#define vi vector<int>
#define ii pair<int, int>
#define pb push_back
#define fi first
#define se second
#define gqt ""

template<class X, class Y>
bool minimize(X& x, const Y& y) {
    X eps = 1e-9;
    if (x > y + eps) {
        x = y;
        return true;
    }
    else return false;
}

template<class X, class Y>
bool maximize(X& x, const Y& y) {
    X eps = 1e-9;
    if (x + eps < y) {
        x = y;
        return true;
    }
    else return false;
}

template<class T>
T Abs(const T& x) {
    return (x < 0 ? -x : x);
}

const int INF = 1e9 + 7;
const ll oo = 1e18 + 7;
const int MAX = 1000005;
const int MOD = 1e9 + 7;

using namespace std;
int n, k, a[MAX], dp[105][100005];
void process(){
    cin >> n >> k;
    For(i, 1, n) cin >> a[i];
    memset(dp, 0x3f, sizeof(dp));
    dp[1][0] = 0;
    For(i, 1, n) dp[1][i] = max(dp[1][i - 1], a[i]);
    For(i, 2, k){
        stack<ii> st;
        For(j, i, n){
            int minF = dp[i - 1][j - 1];
            while(!st.empty() && a[st.top().se] <= a[j]){
                minimize(minF, st.top().fi);
                st.pop();
            }
            dp[i][j] = min(dp[i][st.empty() ? 0 : st.top().se], minF + a[j]);
            st.push(ii(minF, j));
        }
    }
    cout << dp[k][n];
}

signed main()
{
    fastio
    if (fopen(gqt".inp", "r")) {
        freopen(gqt".inp", "r", stdin);
        freopen(gqt".out", "w", stdout);
    }
    int Test = 1;
    while (Test--) {
        process();
    }
    return 0;
}

Compilation message (stderr)

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

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