Submission #779433

#	Time	Username	Problem	Language	Result	Execution time	Memory
779433		ashcomp	Liteh and Newfiteh (INOI20_litehfiteh)	C++17	100 / 100	245 ms	366272 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define wall cerr<<"-------------------------------------"<<endl
typedef long long ll;

const ll INF = 1e17;
const ll maxn = 1e5 + 10;

ll n , a[maxn] , mn[maxn] , res[maxn][22];
vector<pll> seg[maxn];
ll dp[22][maxn][22];


int main()
{
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>a[i];
    }
    for(int i=0; i<20; i++){
        for(int l=1; l<=n; l++){
            for(int k=0; k<20; k++){
                dp[i][l][k] = INF;
                dp[i][l][k] = INF;
            }
        }
    }
    for(int pos=1; pos<=n; pos++){
        dp[0][pos][a[pos]] = 0;
        if(a[pos]<1)continue;
        dp[0][pos][a[pos]-1] = 1;
    }
    for(int i=1; i<20; i++){
        for(int l=1; l+(1<<i)-1<=n; l++){
            int mid=l+(1<<(i-1));
            for(int k=0; k<20; k++){
                    dp[i][l][k] = min(dp[i][l][k] , dp[i-1][l][k]+dp[i-1][mid][k]);
                    dp[i][l][k] = min(dp[i][l][k] , dp[i-1][l][k+1]+dp[i-1][mid][k+1]+1);
            }
        }
    }
    /**
    for(int i=0; i<4; i++){
        for(int l=1; l+(1<<i)-1<=n; l++){
            for(int k=0; k<4; k++){
                    cout<<l<<'-'<<l+(1<<i)-1<<" , +"<<k<<" : "<<dp[i][l][k]<<endl;
            }
            wall;
        }
        wall;
        wall;
    }
    **/
    for(int i=1; i<=n; i++){
        for(int j=0; j<20; j++){
            res[i][j] = INF;
        }
    }
    for(int i=0; i<20; i++){
        for(int l=1; l+(1<<i)-1<=n; l++){
            int r=l+(1<<i)-1;
            res[r][i] = dp[i][l][0];
        }
    }
    mn[0] = 0;
    for(int i=1; i<=n; i++)mn[i] = INF;
    for(int i=1; i<=n; i++){
        for(int j=0; j<20; j++){
            int l = i-(1<<j) , w = res[i][j];
            if(l<0)continue;
            mn[i] = min(mn[i] , mn[l]+w);
        }
    }
    if(mn[n]>=(20*n)){
        cout<<-1;
        return 0;
    }else cout<<mn[n];

    return 0;
}
/**
10
0 0 0 0 0 0 0 0 0 0
*/
// ans = 5;

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