oj.uz

Submission #800576

# Submission time Handle Problem Language Result Execution time Memory
800576 2023-08-01T16:18:00 Z Theo830 Liteh and Newfiteh (INOI20_litehfiteh) C++17
100 / 100
 383 ms 262136 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define ii pair<ll,ll>
#define iii pair<ll,ii>
#define F first
#define S second
ll exo[100005][18][18];
const ll INF = 1e9;
ll dp[100005];
ll n;
ll solve(ll idx){
    if(idx == n){
        return 0;
    }
    if(dp[idx] != -1){
        return dp[idx];
    }
    ll ans = INF;
    f(j,0,18){
        if(idx + (1<<j) > n){
            break;
        }
        ans = min(ans,solve(idx + (1<<j)) + exo[idx][0][j]);
    }
    return dp[idx] = ans;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    ll arr[n];
    f(i,0,n){
        cin>>arr[i];
    }
    for(ll i = n-1;i >= 0;i--){
        for(ll k = 17;k >= 0;k--){
            exo[i][k][0] = INF;
            if(arr[i] == k){
                exo[i][k][0] = 0;
            }
            if(arr[i] == k+1){
                exo[i][k][0] = 1;
            }
            f(j,1,18){
                exo[i][k][j] = INF;
                if(i + (1<<(j-1)) < n){
                    exo[i][k][j] = min(exo[i][k][j],exo[i][k][j-1] + exo[i + (1<<(j-1))][k][j - 1]);
                    if(k+1 < 18){
                        exo[i][k][j] = min(exo[i][k][j],1 + exo[i][k+1][j-1] + exo[i + (1<<(j-1))][k+1][j - 1]);
                    }
                }
            }
        }
    }
    memset(dp,-1,sizeof dp);
    ll ans = solve(0);
    if(ans == INF){
        ans = -1;
    }
    cout<<ans<<"\n";
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2584 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2632 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2632 KB Output is correct
7 Correct 6 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2628 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2584 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2632 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2632 KB Output is correct
7 Correct 6 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2628 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 1 ms 1108 KB Output is correct
15 Correct 1 ms 1108 KB Output is correct
16 Correct 1 ms 1364 KB Output is correct
17 Correct 1 ms 1364 KB Output is correct
18 Correct 2 ms 3668 KB Output is correct
19 Correct 3 ms 3652 KB Output is correct
20 Correct 26 ms 27092 KB Output is correct
21 Correct 27 ms 27176 KB Output is correct
22 Correct 371 ms 261916 KB Output is correct
23 Correct 372 ms 262136 KB Output is correct
24 Correct 363 ms 261936 KB Output is correct
25 Correct 1 ms 1108 KB Output is correct
26 Correct 1 ms 1364 KB Output is correct
27 Correct 1 ms 1364 KB Output is correct
28 Correct 2 ms 3660 KB Output is correct
29 Correct 27 ms 27080 KB Output is correct
30 Correct 26 ms 27108 KB Output is correct
31 Correct 26 ms 27104 KB Output is correct
32 Correct 34 ms 27212 KB Output is correct
33 Correct 370 ms 261912 KB Output is correct
34 Correct 370 ms 262056 KB Output is correct
35 Correct 366 ms 261960 KB Output is correct
36 Correct 383 ms 261988 KB Output is correct
37 Correct 364 ms 261964 KB Output is correct
38 Correct 366 ms 261924 KB Output is correct
39 Correct 364 ms 261840 KB Output is correct
40 Correct 369 ms 261912 KB Output is correct
41 Correct 372 ms 261836 KB Output is correct
42 Correct 371 ms 261940 KB Output is correct
43 Correct 376 ms 261964 KB Output is correct
44 Correct 367 ms 261816 KB Output is correct
45 Correct 380 ms 261904 KB Output is correct
46 Correct 367 ms 261916 KB Output is correct
47 Correct 243 ms 174976 KB Output is correct
48 Correct 277 ms 203852 KB Output is correct
49 Correct 333 ms 232976 KB Output is correct
50 Correct 366 ms 261916 KB Output is correct
51 Correct 26 ms 27064 KB Output is correct
52 Correct 371 ms 261924 KB Output is correct