oj.uz

답안 #779256

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
779256 2023-07-11T09:34:42 Z ashcomp Liteh and Newfiteh (INOI20_litehfiteh) C++14
0 / 100
 3 ms 5504 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5504 KB Output isn't correct
2 Halted 0 ms 0 KB -