Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <cassert>
- #include <cstdio>
- #include <iostream>
- #include <set>
- #include <vector>
- using namespace std;
- const int N = 1000000;
- const int oo = N + 1;
- int n;
- int a[N];
- int d[N][3];
- int main() {
- cin >> n;
- assert(1 <= n && n <= N);
- for (int i = 0; i < n; i++) {
- cin >> a[i];
- assert(a[i] == -1 || a[i] == 0 || a[i] == 1);
- a[i] += 1;
- }
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < 3; j++) {
- d[i][j] = oo;
- }
- }
- d[0][a[0]] = 0;
- for (int i = 1; i < n; i++) {
- for (int j = 0; j < 3; j++) if (j <= a[i]) {
- d[i][a[i]] = min(d[i][a[i]], d[i-1][j]);
- }
- for (int j = 0; j < 3; j++) {
- for (int c = 1; c <= 2; c++) {
- int k = c * (j - 1) + a[i];
- if (k >= 0 && k < 3 && j <= k) {
- d[i][k] = min(d[i][k], d[i-1][j] + c);
- }
- }
- }
- }
- int r = oo;
- for (int j = 0; j < 3; j++) {
- r = min(r, d[n - 1][j]);
- }
- if (r == oo) {
- cout << "Mumkun emes" << endl;
- } else {
- cout << r << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement