oj.uz

Submission #827330

# Submission time Handle Problem Language Result Execution time Memory
827330 2023-08-16T11:13:35 Z YassineBenYounes Liteh and Newfiteh (INOI20_litehfiteh) C++17
30 / 100
 336 ms 323072 KB 
#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];
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(){
    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;
    }
    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

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

# Verdict Execution time Memory Grader output
1 Correct 101 ms 313416 KB Output is correct
2 Correct 95 ms 313424 KB Output is correct
3 Correct 95 ms 313476 KB Output is correct
4 Correct 96 ms 313412 KB Output is correct
5 Correct 95 ms 313444 KB Output is correct
6 Correct 94 ms 313472 KB Output is correct
7 Correct 96 ms 313468 KB Output is correct
8 Correct 96 ms 313480 KB Output is correct
9 Correct 95 ms 313500 KB Output is correct
10 Correct 103 ms 313404 KB Output is correct
11 Correct 95 ms 313468 KB Output is correct
12 Correct 104 ms 313396 KB Output is correct
13 Correct 95 ms 313420 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 313416 KB Output is correct
2 Correct 95 ms 313424 KB Output is correct
3 Correct 95 ms 313476 KB Output is correct
4 Correct 96 ms 313412 KB Output is correct
5 Correct 95 ms 313444 KB Output is correct
6 Correct 94 ms 313472 KB Output is correct
7 Correct 96 ms 313468 KB Output is correct
8 Correct 96 ms 313480 KB Output is correct
9 Correct 95 ms 313500 KB Output is correct
10 Correct 103 ms 313404 KB Output is correct
11 Correct 95 ms 313468 KB Output is correct
12 Correct 104 ms 313396 KB Output is correct
13 Correct 95 ms 313420 KB Output is correct
14 Correct 94 ms 313412 KB Output is correct
15 Correct 97 ms 313460 KB Output is correct
16 Correct 103 ms 313456 KB Output is correct
17 Correct 96 ms 313432 KB Output is correct
18 Correct 96 ms 313436 KB Output is correct
19 Correct 95 ms 313524 KB Output is correct
20 Correct 112 ms 314460 KB Output is correct
21 Correct 110 ms 314304 KB Output is correct
22 Incorrect 336 ms 323072 KB Output isn't correct
23 Halted 0 ms 0 KB -