Submission #590479

#	Time	Username	Problem	Language	Result	Execution time	Memory
590479		Tam_theguide	K blocks (IZhO14_blocks)	C++14	100 / 100	272 ms	42772 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define FORC(i, a, b, c) for (int i = (a), _b = (b); i <= _b; i+=(c))
#define FORM(i, a, b, c) for (int i = (a), _b = (b); i <= _b; i*=(c))
#define FORS(i, a, b) for (int i = (a), _b = (b); i < _b; i++)
#define ll long long
#define fi first
#define se second
#define pb push_back
#define MASK(i) (1 << (i))
#define MASKLL(i) (1LL << (i))
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) (x).begin(), (x).end()
#define revall(x) (x).rbegin(), (x).rend()
#define print(x) cout<<"["<<(x)<<"] "
#define gc(x) ((x) - 'a')
#define popcountll(x) __builtin_popcountll((x))
#define popcount(x) __builtin_popcount((x))
#define mkp(a, b) make_pair((a), (b))
void minimize(int& a, int b){ a = min(a, b); }
void maximize(int& a, int b){ a = max(a, b); }
void setIO(string name = ""){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if ((int)(name.size())){
        freopen((name + ".inp").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}
/// ---- Const / Mod / Limit ---- ///

const int N = 1e5 + 5;
const int K = 105;
const int Lim = 1e6 + 5;
/// ---- Struct ---- ///


/// ---- Basic inp ---- ///
int n, k, a[N];

/// ---- Prequesite ---- ///
int dp[N][K];


int main(){
    setIO();
    cin >> n >> k;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 0, n) FOR(j, 0, k) dp[i][j] = 1e9;
    dp[0][0] = 0; a[0] = 1e9;
    FOR(j, 1, k){
        stack<pii> st; st.push({0, 0});
        FOR(i, j, n){
            int v = dp[i - 1][j - 1];
            while (!st.empty() && a[st.top().se] <= a[i]){
                minimize(v, st.top().fi);
                st.pop();
            }
            dp[i][j] = min(v + a[i], dp[st.top().se][j]);
            st.push({v, i});
            //cout << "dp"; print(i); print(j) << " : " << dp[i][j] << '\n';
        }
    }

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

Compilation message (stderr)

blocks.cpp: In function 'void setIO(std::string)':
blocks.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen((name + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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