Submission #826349

#	Time	Username	Problem	Language	Result	Execution time	Memory
826349		YassineBenYounes	Liteh and Newfiteh (INOI20_litehfiteh)	C++17	30 / 100	2076 ms	9940 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 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 = 1e15;
const int LOG = 20;

int n;
int arr[mx];
ll dp[mx];
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 r, int c){
    ll ans = 0;
    int k = min_query(l, r);
    if((k-c) != 0){
        c++;
        ans++;
    }
    if(l == r){
        if((arr[l]-c) != 0)return inf;
        return ans;
    }
    int md = (l+r)/2;
    ans += f(l, md, c) + f(md+1, r, c);
    return 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];
        if(arr[i] > LOG){
            cout << -1 << endl;
            return 0;
        }
    }
    build();
    for(int i = 0; i <= n;i++){
        dp[i] = inf;
    }
    dp[0] = 0;
    for(int ind = 0; ind < n;ind++){
        for(int i = 1; ind+i-1 < n; i*=2){
            dp[ind+i] = min(dp[ind+i], dp[ind] + f(ind, ind+i-1, 0));
        }
    }
    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: 0 / 70