oj.uz

Submission #627097

# Submission time Handle Problem Language Result Execution time Memory
627097 2022-08-12T07:31:55 Z NothingXD Liteh and Newfiteh (INOI20_litehfiteh) C++14
30 / 100
 148 ms 230704 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

const int MAXN = 1e5 + 10;
const int LOG = 17;
const int INF = 1e9;
int n, a[MAXN], dp[LOG][LOG][MAXN], ans[MAXN];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	memset(dp, 63, sizeof dp);
	memset(ans, 63, sizeof ans);
	debug(2*ans[0]+1);
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		dp[0][a[i]][i] = 0;
		if (a[i]) dp[0][a[i]-1][i] = 1;
	}
	for (int i = 1; i < LOG; i++){
		for (int j = 0; j < LOG; j++){
			for (int k = 1; k + (1 << i) - 1 <= n; k++){
				dp[i][j][k] = min({dp[i][j][k], dp[i-1][j][k] + dp[i-1][j][k + (1 << (i-1))],
						dp[i-1][j+1][k] + dp[i-1][j+1][k + (1 << (i-1))] + 1});
				}
		}
	}
	ans[n+1] = 0;
	for (int i = n; i; i--){
		for (int j = 0; i + (1 << j) - 1 <= n; j++){
			ans[i] = min(ans[i], dp[j][0][i] + ans[i + (1 << j)]);
		}
	}
	cout << (ans[1] >= INF? -1: ans[1]) << '\n';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 113704 KB Output is correct
2 Correct 42 ms 113740 KB Output is correct
3 Correct 41 ms 113776 KB Output is correct
4 Correct 43 ms 113724 KB Output is correct
5 Correct 46 ms 113704 KB Output is correct
6 Correct 44 ms 113740 KB Output is correct
7 Correct 43 ms 113804 KB Output is correct
8 Correct 42 ms 113748 KB Output is correct
9 Correct 43 ms 113824 KB Output is correct
10 Correct 42 ms 113772 KB Output is correct
11 Correct 48 ms 113740 KB Output is correct
12 Correct 47 ms 113828 KB Output is correct
13 Correct 44 ms 113780 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 113704 KB Output is correct
2 Correct 42 ms 113740 KB Output is correct
3 Correct 41 ms 113776 KB Output is correct
4 Correct 43 ms 113724 KB Output is correct
5 Correct 46 ms 113704 KB Output is correct
6 Correct 44 ms 113740 KB Output is correct
7 Correct 43 ms 113804 KB Output is correct
8 Correct 42 ms 113748 KB Output is correct
9 Correct 43 ms 113824 KB Output is correct
10 Correct 42 ms 113772 KB Output is correct
11 Correct 48 ms 113740 KB Output is correct
12 Correct 47 ms 113828 KB Output is correct
13 Correct 44 ms 113780 KB Output is correct
14 Correct 42 ms 113740 KB Output is correct
15 Correct 43 ms 113708 KB Output is correct
16 Correct 45 ms 113708 KB Output is correct
17 Correct 43 ms 113832 KB Output is correct
18 Correct 44 ms 113824 KB Output is correct
19 Correct 43 ms 113716 KB Output is correct
20 Correct 46 ms 113868 KB Output is correct
21 Correct 49 ms 113824 KB Output is correct
22 Correct 91 ms 114388 KB Output is correct
23 Runtime error 148 ms 230704 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -