Submission #1126640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126640		Lilinta	K blocks (IZhO14_blocks)	C++20	100 / 100	122 ms	1984 KiB

blocks

//Problem link: https://oj.uz/problem/view/IZhO14_blocks
// Libraries
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; //find_by_order, order_of_key
#include <ext/rope>
using namespace __gnu_cxx;

// Data types
typedef string str;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef unsigned int ui;
typedef unsigned long long ull;

// Methods
#define MP make_pair
#define F first
#define S second
#define PB push_back
#define sz(a) (int)(a).size()

// Iterator
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

// Variable names
#define y1 y1___

// Loops
#define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
#define RFOR(i,a,b) for (int i = (a); i >= (b); --i)

// Constant variables
const int MOD = 1000000007; // 998244353
const int INF = 1000000005;
const ll LLINF = 1000000000000000005LL;
const ld PI = acos((ld)-1);
const ld EPS = 1e-9;

void setIO(str name="") {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout << setprecision(15) << fixed;
    if (fopen((name + ".INP").c_str(), "r")) {
        freopen((name + ".INP").c_str(), "r", stdin);
        freopen((name + ".OUT").c_str(), "w", stdout);
    }
}
inline ll pw(ll bs, ll p, int mod=MOD) {
    ll res = 1;
    ll tmp = bs;
    while (p) {
        if (p & 1) {
            res = res*tmp%mod;
        }
        tmp = tmp*tmp%mod;
        p >>= 1;
    }
    return res;
}
inline ll inv(ll x, int mod=MOD) {
    return pw(x, mod-2, mod);
}

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l, ll r) {
    return l + (ll)(rd() % (ull)(r-l+1));
}

int test = 1;
const int MAXN = 100005;
const int MAXK = 105;
int n, k;
int a[MAXN];
int dp[2][MAXN];
stack<pii> st;

void solve() {
    cin >> n >> k;
    FOR(i, 1, n) {
        cin >> a[i];
    }
    dp[0][0] = 0;
    FOR(i, 1, n) dp[0][i] = INF;
    FOR(_, 1, k) {
        dp[1][0] = INF;
        FOR(i, 1, n) {
            int minF = dp[0][i-1];
            dp[1][i] = minF + a[i];
            while (!st.empty() && a[st.top().F] < a[i]) {
                minF = min(minF, st.top().S);
                dp[1][i] = minF + a[i];
                st.pop();
            }
            if (!st.empty()) {
                dp[1][i] = min(dp[1][i], dp[1][st.top().F]);
            }
            st.push(MP(i, minF));
        }
        FOR(i, 0, n) {
            dp[0][i] = dp[1][i];
        }
        while (!st.empty()) st.pop();
    }
    cout << dp[0][n] << '\n';
}

int main() {
    setIO();
    //cin >> test;
    FOR(_, 1, test) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

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

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