Submission #1265850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265850		asemoonabi	Liteh and Newfiteh (INOI20_litehfiteh)	C++20	100 / 100	418 ms	284560 KiB

Main

#include<bits/stdc++.h>
using namespace std ; 
typedef long long ll ;
#define el '\n'
const ll maxn = 1e5 + 100 ;
const ll maxk = 19 ;
const ll mod = 1e9 + 7 ;
const ll oo = 1e15 + 7 ;
ll n , a[maxn] , dp[maxn][maxk][maxk] , dp2[maxn] ;
void solve(){
    ll mx = 0 ;
    cin>>n ; for(ll i = 0 ; i < n ; i++){cin>>a[i];a[i] = max(mx,a[i]);}
    if(maxk <= mx){cout<<-1<<el;return;}
    for(ll i = 0 ; i < n ; i++){
        for(ll k = 0 ; k < maxk ; k++){
            dp[i][0][k] = oo ;
        }
    }
    for(ll i = 0 ; i < n ; i++){
        dp[i][0][a[i]] = 0 ;
        if(0 < a[i]){dp[i][0][a[i]-1] = 1;}
    }
    for(ll x = 1 ; x < maxk-1 ; x++){
        for(ll i = 0 ; i < n ; i++){
            if(n < i+(1<<x)){break;}
            for(ll k = 0 ; k < maxk-1 ; k++){
                ll A1 = dp[i][x-1][k+1] + dp[i+(1<<(x-1))][x-1][k+1] + 1 ;
                ll A2 = dp[i][x-1][k] + dp[i+(1<<(x-1))][x-1][k] ;
                ll A = min(A1,A2) ; A = min(A,oo) ;
                dp[i][x][k] = A ;
            }
        }
    }
    for(ll i = 0 ; i < n; i++){
        dp2[i] = oo ;
        for(ll x = 0 ; x < maxk-1 ; x++){
            ll ind = i-(1<<x) ;
            if(i-(1<<x) == -1){dp2[i] = min(dp2[i],dp[0][x][0]);}
            if(ind < 0){continue;}
            dp2[i] = min(dp2[i],dp2[ind]+dp[ind+1][x][0]) ;
        }
    }
    cout<<((dp2[n-1] < oo) ? dp2[n-1] : -1)<<el ;
    return ;
}
int main(){
    solve() ;
}

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