oj.uz

Submission #827332

# Submission time Handle Problem Language Result Execution time Memory
827332 2023-08-16T11:16:07 Z YassineBenYounes Liteh and Newfiteh (INOI20_litehfiteh) C++17
30 / 100
 388 ms 398828 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 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 = 1e15;
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

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 121 ms 379356 KB Output is correct
2 Correct 118 ms 379316 KB Output is correct
3 Correct 115 ms 379316 KB Output is correct
4 Correct 113 ms 379300 KB Output is correct
5 Correct 117 ms 379240 KB Output is correct
6 Correct 113 ms 379288 KB Output is correct
7 Correct 114 ms 379236 KB Output is correct
8 Correct 128 ms 379288 KB Output is correct
9 Correct 114 ms 379268 KB Output is correct
10 Correct 114 ms 379212 KB Output is correct
11 Correct 121 ms 379324 KB Output is correct
12 Correct 114 ms 379268 KB Output is correct
13 Correct 116 ms 379264 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 379356 KB Output is correct
2 Correct 118 ms 379316 KB Output is correct
3 Correct 115 ms 379316 KB Output is correct
4 Correct 113 ms 379300 KB Output is correct
5 Correct 117 ms 379240 KB Output is correct
6 Correct 113 ms 379288 KB Output is correct
7 Correct 114 ms 379236 KB Output is correct
8 Correct 128 ms 379288 KB Output is correct
9 Correct 114 ms 379268 KB Output is correct
10 Correct 114 ms 379212 KB Output is correct
11 Correct 121 ms 379324 KB Output is correct
12 Correct 114 ms 379268 KB Output is correct
13 Correct 116 ms 379264 KB Output is correct
14 Correct 117 ms 379096 KB Output is correct
15 Correct 114 ms 379160 KB Output is correct
16 Correct 117 ms 379176 KB Output is correct
17 Correct 114 ms 379212 KB Output is correct
18 Correct 126 ms 379316 KB Output is correct
19 Correct 118 ms 379340 KB Output is correct
20 Correct 129 ms 381104 KB Output is correct
21 Correct 129 ms 381060 KB Output is correct
22 Incorrect 388 ms 398828 KB Output isn't correct
23 Halted 0 ms 0 KB -