Submission #1261622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261622		Hamed_Ghaffari	Liteh and Newfiteh (INOI20_litehfiteh)	C++20	0 / 100	96 ms	113472 KiB

Main

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

const int MXN = 1e5, LOG = 17, inf = 1e7;

int n, a[MXN], dp[MXN][LOG][LOG], ans[MXN+1];

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i=0; i<n; i++) cin >> a[i];
    for(int i=n-1; i>=0; i--) {
        for(int k=0; k<LOG; k++)
            dp[i][0][k] = (k==a[i] ? 0 : inf);
        for(int j=1; i+(1<<j)<=n; j++)
            for(int k=0; j+k<=LOG; k++)
                dp[i][j][k] = min(inf,
                min(dp[i][j-1][k], dp[i][j-1][k+1]+1) +
                min(dp[i+(1<<(j-1))][j-1][k], dp[i+(1<<(j-1))][j-1][k+1]+1));
        if(a[i]==0) {
            ans[i] = ans[i+1];
            continue;
        }
        ans[i] = inf;
        for(int j=0; i+(1<<j)<=n; j++)
            ans[i] = min(ans[i], dp[i][j][1]+1 + ans[i+(1<<j)]);
    }
    cout << (ans[0]==inf ? -1 : ans[0]) << '\n';
    return 0;
}

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