Submission #635834

#	Time	Username	Problem	Language	Result	Execution time	Memory
635834		K4YAN	Liteh and Newfiteh (INOI20_litehfiteh)	C++17	100 / 100	506 ms	270400 KiB

Main

//Be Name Khoda

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define pll pair<ll, ll>
#define all(x) x.begin(), x.end()

const ll mxn = 1e5 + 16, lg = 18, INF = 1e16 + 16;
ll n, q, w, e;
ll dp[mxn], mn[mxn][lg], pd[mxn][lg][lg];
vector<ll> g;
bool bomb;

inline void input() {

    for(int i = 0; i < mxn; i++) {
        dp[i] = INF;
        for(int j = 0; j < lg; j++) {
            mn[i][j] = INF;
            fill(pd[i][j], pd[i][j] + lg, INF);
        }
    }

    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> q;
        g.push_back(q);
        if(q >= lg) bomb = 1;
        mn[i][0] = q;
    }

}

inline void solve() {

    if(bomb) {
        cout << "-1\n";
        return;
    }

    for(int j = 1; j < lg; j++) {
        for(int i = 0; i < n; i++) {
            if(i + (1 << (j - 1)) >= n) break;
            mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
        }
    }
    for(int i = 0; i < n; i++) {
        for(int k = 0; k < lg; k++) {
            if(k == g[i] - 1) {
                pd[i][0][k] = 1;
            } if(k == g[i]) {
                pd[i][0][k] = 0;
            }
        }
    }
    for(int j = 1; j < lg; j++) {
        for(int i = 0; i < n; i++) {
            if(i + (1 << j) > n) break;
            for(int k = 0; k < lg; k++) {
                if(mn[i][j] < k) break;
                pd[i][j][k] = min(INF, pd[i][j - 1][k] + pd[i + (1 << (j - 1))][j - 1][k]);
                if(k + 1 < lg && mn[i][j] >= k + 1) {
                    pd[i][j][k] = min(pd[i][j][k], pd[i][j - 1][k + 1] + pd[i + (1 << (j - 1))][j - 1][k + 1] + 1);
                } 
            }
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; (1 << j) <= i + 1; j++) {
            if((1 << j) == i + 1) {
                dp[i] = min(dp[i], pd[0][j][0]);
                continue;
            }
            dp[i] = min(dp[i], pd[i - (1 << j) + 1][j][0] + dp[i - (1 << j)]);
        }
    }
    if(dp[n - 1] >= INF) {
        cout << "-1\n";
        return;
    } cout << dp[n - 1] << endl;
    return;

}

int main() {

    ios::sync_with_stdio(false); cin.tie(NULL);

    input(), solve();

    return 0;
    
}
/*
8
2 2 2 0 1 1 2 2
*/

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70