Submission #1259105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259105		mohammadsam	Liteh and Newfiteh (INOI20_litehfiteh)	C++20	100 / 100	150 ms	134980 KiB

Main

/*
    in the name of god
*/
//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll ;

#define File          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define all(V)        V.begin(),V.end()
#define setprec(x)    fixed << setprecision(x)
#define Mp(a,b)       make_pair(a,b)
#define len(V)        (int)(V.size())
#define sep           ' '
#define endl          '\n'
#define pb(x)         push_back(x)
#define fi            first
#define sec           second
#define popcount(x)   __builtin_popcount(x)
#define lid           u<<1
#define rid           (lid)|1
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 1e5 + 10,SQ=320,LOG=18;
const ll inf = 1e9 , MD = 1e9 + 7;

inline ll md(ll x){ x %= MD; return (x < 0 ? x + MD : x);}
int n,dp[N][LOG][LOG];
int f[N];
int arr[N];
int mn[N][LOG];
void Build_sparse(){
    for(int i = n;i>=1;i--){
        mn[i][0] = arr[i];
        for(int j = 1;j < LOG and i + (1<<j) - 1 <= n;j++){
            mn[i][j] = min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
        }
    }
}
int32_t main() {
    ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);
    cin >> n;
    for(int i =1 ;i<=n;i++) cin >> arr[i];
    Build_sparse();
    for(int i = 0 ;i <=n+1;i++){
        for(int j = 0;j < LOG;j++){
            for(int k = 0 ; k < LOG;k++) dp[i][j][k] = inf;
        }
    }
    for(int i = n;i >= 1;i--){
        for(int k = 0;k<LOG;k++){
            if(arr[i] - k == 0) dp[i][0][k] = 0;
            else if(arr[i] - k == 1) dp[i][0][k] = 1;
            else dp[i][0][k] = inf;
        }
        for(int j = 1;j<LOG and i + (1<<j) - 1 <= n;j++){
            for(int k = 0 ;k < LOG;k++){
                if(mn[i][j] - k < 0){
                    continue;
                }
                if(mn[i][j] - k > 0){
                    dp[i][j][k] = min(dp[i][j][k],1+dp[i][j-1][k+1]+dp[i+(1<<(j-1))][j-1][k+1]);
                }
                if(mn[i][j] - k == 0){
                    dp[i][j][k] = min(dp[i][j][k],dp[i][j-1][k]+dp[i+(1<<(j-1))][j-1][k]);
                }
            }
        }
        if(arr[i] == 0) f[i] = f[i+1];
        else
        {
            f[i] = inf;
            for(int j = 0;j < LOG and i + (1<<j) - 1 <= n;j++) f[i] = min(f[i],f[i+(1<<j)] + dp[i][j][0]);
        }
    }
    if(f[1] >= inf) f[1] = -1;
    cout << f[1] << endl;
    return 0;
}

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