Submission #779256

#	Time	Username	Problem	Language	Result	Execution time	Memory
779256		ashcomp	Liteh and Newfiteh (INOI20_litehfiteh)	C++14	0 / 100	3 ms	5504 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 = 1e18;
const ll maxn = 1e5 + 10;

ll n , a[maxn] , mn[maxn];
vector<pll> ve[32];
vector<pll> seg[maxn];
ll dp[32][maxn][32][2];


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 l=1; l<=n; l++){
        for(int j=0; j<30; j++){
            int len = 1ll<<j , r=l+len-1;
            if(r>n)break;
            ve[j].push_back({l,r});
        }
    }
    for(int i=0; i<30; i++){
        for(auto e : ve[i]){
            int l=e.F , r=e.S , mid=l+(1ll<<(i-1));
            for(int k=0; k<30; k++){
                dp[i][l][k][0] = INF;
                dp[i][l][k][1] = INF;
            }
        }
    }
    for(auto e : ve[0]){
        int pos = e.F;
        dp[0][pos][a[pos]][0] = 0;
        if(a[pos]<1)continue;
        dp[0][pos][a[pos]-1][1] = 1;
    }
    /****/
    for(int i=1; i<30; i++){
        for(auto e : ve[i]){
            int l=e.F , mid=l+(1<<(i-1));
            for(int k=0; k<30; k++){
                dp[i][l][k][0] = min(dp[i][l][k][0] , dp[i-1][l][k][1]+dp[i-1][mid][k][0]);
                dp[i][l][k][0] = min(dp[i][l][k][0] , dp[i-1][l][k][1]+dp[i-1][mid][k][1]);
                dp[i][l][k][0] = min(dp[i][l][k][0] , dp[i-1][l][k][0]+dp[i-1][mid][k][0]);
                dp[i][l][k][0] = min(dp[i][l][k][0] , dp[i-1][l][k][0]+dp[i-1][mid][k][1]);

                dp[i][l][k][1] = min(dp[i][l][k][1] , dp[i-1][l][k+1][1]+dp[i-1][mid][k+1][0]+1);
                dp[i][l][k][1] = min(dp[i][l][k][1] , dp[i-1][l][k+1][1]+dp[i-1][mid][k+1][1]+1);
                dp[i][l][k][1] = min(dp[i][l][k][1] , dp[i-1][l][k+1][0]+dp[i-1][mid][k+1][0]+1);
                dp[i][l][k][1] = min(dp[i][l][k][1] , dp[i-1][l][k+1][0]+dp[i-1][mid][k+1][1]+1);
            }
        }
    }
    /***/
    /*for(int i=0; i<3; i++){
        for(auto e : ve[i]){
            int l=e.F , mid=l+(1<<(i-1));
            for(int k=0; k<4; k++){
                    cout<<e.F<<"-"<<e.S<<", +"<<k<<" , not : "<<dp[i][l][k][0]<<endl;
                    cout<<e.F<<"-"<<e.S<<", +"<<k<<" , yes : "<<dp[i][l][k][1]<<endl;
            }
            wall;
        }
        wall;wall;
    }*/
    /****/
    for(int i=1; i<30; i++){
        for(auto e : ve[i]){
            int l=e.F , r=e.S;
            if(dp[i][l][0][0]<INF){
                seg[r].push_back({l,dp[i][l][0][0]});
            }
            if(dp[i][l][0][1]<INF){
                seg[r].push_back({l,dp[i][l][0][1]});
            }
        }
    }
    mn[0] = 0;
    for(int i=1; i<=n; i++)mn[i] = INF;
    for(int i=1; i<=n; i++){
        for(auto e : seg[i]){
            int l = e.F , w = e.S;
            mn[i] = min(mn[i] , mn[l-1]+w);
        }
    }
    if(mn[n]==INF){
        cout<<-1;
        return 0;
    }else cout<<mn[n];

    return 0;
}
/**
10
1 1 1 1 2 2 2 3 2 1
*/
// ans = 5;

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:37:25: warning: unused variable 'r' [-Wunused-variable]
   37 |             int l=e.F , r=e.S , mid=l+(1ll<<(i-1));
      |                         ^
Main.cpp:37:33: warning: unused variable 'mid' [-Wunused-variable]
   37 |             int l=e.F , r=e.S , mid=l+(1ll<<(i-1));
      |                                 ^~~

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