Submission #827333

#	Time	Username	Problem	Language	Result	Execution time	Memory
827333		YassineBenYounes	Liteh and Newfiteh (INOI20_litehfiteh)	C++17	100 / 100	762 ms	399136 KiB

Main

#include<bits/stdc++.h>
using namespace std;
void init(){
    #ifndef ONLINE_JUDGE
 
freopen("input.txt", "r", stdin);
 
freopen("output.txt", "w", stdout);
 
#endif // ONLINE_JUDGE
}
typedef long long ll;
#define int ll
#define pii pair<int, int>
#define ff first
#define ss second
#define vii vector<pii>
#define pb push_back
#define vi vector<int>
const int mx = 1e5+5;
const ll inf = 1e11;
const int LOG = 22;
 
int n;
int arr[mx];
ll dp[mx];
ll dp2[mx][LOG][LOG];
int st[mx][LOG];
int lg[mx];
 
void pre_log(int n){
    lg[1] = 0;
    for(int i = 2; i <= n;i++){
        lg[i] = lg[i/2]+1;
    }
}
 
void build(){
    for(int i = 0; i < n;i++){
        st[i][0] = arr[i];
    }
    for(int j = 1;j < LOG;j++){
        for(int i = 0; i < n;i++){
            int pos = i + (1 << (j-1));
            if(pos >= n)continue;
            st[i][j] = min(st[i][j-1], st[pos][j-1]);
        }
    }
}
 
int min_query(int a, int b){
    int sz = b-a+1;
    int k = lg[sz];
    return min(st[a][k], st[b-(1<<k)+1][k]);
}
 
ll f(int l, int j, int c){
    if(dp2[l][j][c] != -1)return dp2[l][j][c];
    int r = l + (1 << j)-1;
    ll ans = 0;
    int k = min_query(l, r);
    int add = 0;
    if((k-c) != 0){
        add++;
        ans++;
    }
    if(l == r){
        if((arr[l]-c-add) != 0)return dp2[l][j][c] = inf;
        return dp2[l][j][c] = ans;
    }
    int md = (l+r)/2;
    ans += f(l, j-1, c+add) + f(md+1, j-1, c+add);
    return dp2[l][j][c] = ans;
}
 
int32_t main(){
    //init();
    cin.tie();cout.tie();ios::sync_with_stdio(false);
    cin >> n;
    pre_log(n+1);
    for(int i = 0; i < n;i++){
        cin >> arr[i];
    }
    build();
    for(int i = 0; i <= n;i++){
        dp[i] = inf;
    }
    memset(dp2, -1, sizeof dp2);
    dp[0] = 0;
    for(int ind = 0; ind < n;ind++){
        int k = 0;
        for(int i = 1; ind+i-1 < n; i*=2){
            dp[ind+i] = min(dp[ind+i], dp[ind] + f(ind, k, 0));
            k++;
        }
    }
    cout << (dp[n] >= inf ? -1 : dp[n]) << endl;
}

Compilation message (stderr)

Main.cpp: In function 'void init()':
Main.cpp:6:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | freopen("input.txt", "r", stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:8:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | freopen("output.txt", "w", stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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