Submission #1256411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256411		pasta	Liteh and Newfiteh (INOI20_litehfiteh)	C++20	100 / 100	362 ms	158484 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define F 	first
#define S 	second
#define pb	push_back
// #define int long long
const int maxn = 1e6 + 1;
const int LOG = 20;
const int inf = 1e9 + 10;


int n, a[maxn], dp[maxn][LOG][LOG], pd[maxn];

// dp[i][k][x]  baze [i, i + (1 << k)] max = x; va min >= 0
void perp() {
	for (int k = 0; k < LOG; k++) {
		for (int ln = 1; ln <= n; ln++) {
			for (int x = 0; x < LOG; x++) {
				dp[ln][k][x] = inf;
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		if (a[i] >= LOG) {
			cout << -1 << '\n';
			exit(0);
		}
		dp[i][0][a[i]] = 0;
		if (a[i])
			dp[i][0][a[i] - 1] = 1;
	}
}

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];

	perp();

	for (int k = 1; k < LOG; k++) {
		for (int ln = 1; ln <= n; ln++) {
			for (int x = 0; x < LOG; x++) {
				dp[ln][k][x] = dp[ln][k - 1][x] + dp[ln + (1 << (k - 1))][k - 1][x];
				dp[ln][k][x] = min(inf, dp[ln][k][x]);
				
				if (x + 1 <= LOG) {
					dp[ln][k][x] = min(dp[ln][k][x], 1 + dp[ln][k - 1][x + 1] + dp[ln + (1 << (k - 1))][k - 1][x + 1]);
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		pd[i] = inf;
		for (int j = 0; j < LOG; j++) {
			if (i >= (1 << j)) {
				pd[i] = min(pd[i], pd[i - (1 << j)] + dp[i - (1 << j) + 1][j][0]);
			}
		}
	}
	if (pd[n] >= inf)
		pd[n] = -1;
	cout << pd[n] << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:50:97: warning: iteration 19 invokes undefined behavior [-Waggressive-loop-optimizations]
   50 |                                         dp[ln][k][x] = min(dp[ln][k][x], 1 + dp[ln][k - 1][x + 1] + dp[ln + (1 << (k - 1))][k - 1][x + 1]);
      |                                                                              ~~~~~~~~~~~~~~~~~~~^
Main.cpp:45:43: note: within this loop
   45 |                         for (int x = 0; x < LOG; x++) {
      |                                         ~~^~~~~

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70