Submission #375162

#	Time	Username	Problem	Language	Result	Execution time	Memory
375162		SeDunion	Po (COCI21_po)	C++17	10 / 70	1089 ms	1972 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 66;

int a[N];

int solve(int l, int r) {
	if (l >= r) return 0;
	int mn = int(1e9);
	for (int i = l ; i < r ; ++ i) {
		mn = min(mn, a[i]);
	}
	int res = 1;
	int last = l;
	for (int i = l ; i < r ; ++ i) {
		if (a[i] == mn) {
			res += solve(last, i);
			last = i + 1;
		}
	}
	res += solve(last, r);
	return res;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for (int i = 0 ; i < n ; ++ i) {
		cin >> a[i];
	}
	cout << solve(0, n);
}

• Subtask 1: 10 / 70