Submission #1293417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293417		hiepsimauhong	K개의 묶음 (IZhO14_blocks)	C++20	53 / 100	1097 ms	5352 KiB

blocks

#include <bits/stdc++.h>

using namespace std;

//#define int long long

#define FOR(I, L, R) for(int I(L); I <= (int)R ; ++I)
#define FOD(I, R, L) for(int I(R); I >= (int)L ; --I)
#define FOA(I, A) for(auto &I : A)

#define print(A, L, R) FOR(I, L, R){cout << A[I] <<' ';} cout << '\n';
#define printz(A, L, R) FOR(I, 0, L){FOR(J, 0, R){cout << A[I][J] << ' ';} cout << '\n';} cout << '\n';
#define prints(A) FOA(I, A) cout << I <<' '; cout << '\n';

#define fs first
#define sd second
#define ii pair<int, int>
#define iii pair<int, ii>
#define all(A) A.begin(), A.end()
#define quickly cin.tie(0) -> ios_base::sync_with_stdio(0);
#define FILE "dincpath"

const int N = 1e5 + 5;
const int K = 101;

const int mod = 1e9 + 7;
const int oo = 1e9;

struct Modint{
        int x;

        Modint(){x = 0;}
        Modint(int _x){x = (_x + mod) % mod;}

        Modint operator + (const Modint &other) const{ return Modint((x + other.x) % mod); }
        Modint operator - (const Modint &other) const{ return Modint((x - other.x + mod) % mod); }
        Modint operator * (const Modint &other) const{ return Modint((1LL * x * other.x) % mod); }

        void operator += (const Modint &other) { *this = *this + other; }
        void operator -= (const Modint &other) { *this = *this - other; }
        void operator *= (const Modint &other) { *this = *this * other; }

        friend ostream& operator << (ostream& os, const Modint &other){
                return os << other.x;
        }
};

int n, k;
int a[N], in[N], dp[N];
stack<int> st;

struct node{
        int cost, res, mx;

        node(){cost = res = oo; mx = 0;}

        node operator + (const node &other) const {
                node _new;

                _new.res = min(res, other.res);
                _new.cost = min(cost, other.cost);
                _new.mx = max(mx, other.mx);

                return _new;
        }

        void change(int x){
                mx = x;
                res = cost + x;
        }
};

struct SegmentTree{
        node sg[N << 2];
        int lazy[N << 2];

        void build(int id, int l, int r){
                lazy[id] = 0;
                if(l == r){
                        sg[id] = node();
                        return;
                }

                int mid = (l + r) >> 1;

                build(id << 1, l, mid);
                build(id << 1 | 1, mid + 1, r);

                sg[id] = sg[id << 1] + sg[id << 1 | 1];
        }

        void push_down(int id, int l, int r){
                if(lazy[id]){
                        int &x = lazy[id];

                        lazy[id << 1] = x;
                        lazy[id << 1 | 1] = x;

                        sg[id << 1].change(x);
                        sg[id << 1 | 1].change(x);

                        x = 0;
                }
        }

        void updateCost(int id, int l, int r, int pos, int val){
                if(l > pos || r < pos){
                        return;
                }
                if(l == r){
                        sg[id].cost = val;
                        sg[id].res = sg[id].mx + val;
                        return;
                }
                push_down(id, l, r);

                int mid = (l + r) >> 1;

                updateCost(id << 1, l, mid, pos, val);
                updateCost(id << 1 | 1, mid + 1, r, pos, val);

                sg[id] = sg[id << 1] + sg[id << 1 | 1];
        }

        void update(int id, int l, int r, int u, int v, int val){
                if(l > v || r < u){
                        return;
                }
                if(u <= l && r <= v){
                        lazy[id] = val;
                        sg[id].change(val);
                        return;
                }
                push_down(id, l, r);

                int mid = (l + r) >> 1;

                update(id << 1, l, mid, u, v, val);
                update(id << 1 | 1, mid + 1, r, u, v, val);

                sg[id] = sg[id << 1] + sg[id << 1 | 1];
        }

        int get(int id, int l, int r, int u, int v){
                if(l > v || r < u){
                        return oo;
                }
                if(l == r){
                        return sg[id].res;
                }
                push_down(id, l, r);

                int mid = (l + r) >> 1;

                return min(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
        }
} sg;

signed main(){ quickly
        if(fopen(FILE".inp", "r")){
                freopen(FILE".inp", "r", stdin);
                freopen(FILE".out", "w", stdout);
        }

        cin >> n >> k;

        FOR(i, 1, n){
                cin >> a[i];
        }

        a[0] = oo;
        st.push(0);

        FOR(i, 1, n){
                while(a[st.top()] < a[i]){
                        st.pop();
                }
                in[i] = st.top();
                st.push(i);
        }

        sg.updateCost(1, 0, n, 0, 0);
        sg.update(1, 0, n, 0, 0, 0);

        FOR(j, 1, k){
                FOR(i, 1, n){
                        sg.update(1, 0, n, in[i], i - 1, a[i]);
                        dp[i] = sg.get(1, 0, n, 0, i - 1);
                }

                sg.build(1, 0, n);
                FOR(i, 1, n){
                        sg.updateCost(1, 0, n, i, dp[i]);
                }
        }

        cout << dp[n];
}

Compilation message (stderr)

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

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