Submission #632548

#	Time	Username	Problem	Language	Result	Execution time	Memory
632548		MohammadAghil	Liteh and Newfiteh (INOI20_litehfiteh)	C++17	100 / 100	236 ms	135312 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pp;

#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
#define ff
#define ss

void debug(){
    cerr << endl;
}
template<typename Head, typename... Tail>
void debug(Head h, Tail... t){
    cerr << " " << h << ",";
    debug(t...);
}
#define er(...) cerr << __LINE__ << " (" << #__VA_ARGS__ << "):", debug(__VA_ARGS__)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void IOS(){
    cin.tie(0) -> sync_with_stdio(0);
//    #ifndef ONLINE_JUDGE
//        freopen("inp.txt", "r", stdin);
//        freopen("out.txt", "w", stdout);
//    #endif
}

const ll mod = 1e9 + 7, maxn = 1e5 + 5, lg = 18, inf = ll(1e9) + 5;

int a[maxn];
int dp[maxn][lg][lg], rmq[maxn][lg], dp2[maxn];

int main(){ IOS();
    int n; cin >> n;
    rep(i,0,n){
        cin >> a[i];
        rmq[i][0] = a[i];
        rep(j,0,lg) rep(k,0,lg) dp[i][j][k] = inf;
    }


    rep(i,0,n){
        if(a[i] >= lg){
            return cout << -1 << '\n', 0;
        }
        dp[i][0][a[i]] = 0;
        if(a[i]) dp[i][0][a[i]-1] = 1;
    }

    rep(j,1,lg){
        rep(i,0,n-(1<<j)+1){
            rmq[i][j] = min(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
        }
    }

    rep(j,1,lg){
        rep(i,0,n-(1<<j)+1){
            int mn = rmq[i][j];
            rep(k,0,mn+1){
                dp[i][j][k] = min({
                    dp[i][j-1][k] + dp[i+(1<<(j-1))][j-1][k],
                    (k < lg-1? dp[i][j-1][k+1] + dp[i+(1<<(j-1))][j-1][k+1] + 1: (int)inf),
                    (int)inf
                });
            }
//            er(i, j, dp[i][j][0]);
        }
    }


    rep(i,0,n){
        dp2[i] = inf;
        rep(j,0,lg){
            int l = i - (1<<j) + 1;
            if(l < 0) break;
            dp2[i] = min(dp2[i], dp[l][j][0] + (l?dp2[l-1]:0));
        }
    }

    cout << (dp2[n-1] == inf? -1: dp2[n-1]) << '\n';
    return 0;
}

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