oj.uz

Submission #635833

# Submission time Handle Problem Language Result Execution time Memory
635833 2022-08-27T07:06:41 Z K4YAN Liteh and Newfiteh (INOI20_litehfiteh) C++17
30 / 100
 418 ms 536928 KB 
//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++) {
            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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 268744 KB Output is correct
2 Correct 128 ms 268960 KB Output is correct
3 Correct 115 ms 268732 KB Output is correct
4 Correct 111 ms 268768 KB Output is correct
5 Correct 122 ms 268776 KB Output is correct
6 Correct 118 ms 268840 KB Output is correct
7 Correct 124 ms 268876 KB Output is correct
8 Correct 133 ms 268748 KB Output is correct
9 Correct 126 ms 268900 KB Output is correct
10 Correct 115 ms 268804 KB Output is correct
11 Correct 115 ms 268876 KB Output is correct
12 Correct 116 ms 268796 KB Output is correct
13 Correct 113 ms 268812 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 268744 KB Output is correct
2 Correct 128 ms 268960 KB Output is correct
3 Correct 115 ms 268732 KB Output is correct
4 Correct 111 ms 268768 KB Output is correct
5 Correct 122 ms 268776 KB Output is correct
6 Correct 118 ms 268840 KB Output is correct
7 Correct 124 ms 268876 KB Output is correct
8 Correct 133 ms 268748 KB Output is correct
9 Correct 126 ms 268900 KB Output is correct
10 Correct 115 ms 268804 KB Output is correct
11 Correct 115 ms 268876 KB Output is correct
12 Correct 116 ms 268796 KB Output is correct
13 Correct 113 ms 268812 KB Output is correct
14 Correct 120 ms 268800 KB Output is correct
15 Correct 117 ms 268736 KB Output is correct
16 Correct 114 ms 268720 KB Output is correct
17 Correct 112 ms 268736 KB Output is correct
18 Correct 123 ms 268748 KB Output is correct
19 Correct 123 ms 268804 KB Output is correct
20 Correct 124 ms 268972 KB Output is correct
21 Correct 119 ms 268944 KB Output is correct
22 Runtime error 418 ms 536928 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -