7628 | 2024. 01. 10 09:34:20 | Ablablabla | Takaros Sorozat (80 pont) | cpp17 | Elfogadva 80/80 | 12ms | 9820 KiB |
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
string s;
cin >> s;
vector<int> a(n + 5);
for(int i = 1; i <= n; i++) {
a[i] = s[i - 1] - '0';
}
vector<int> pref(n + 1), suf(n + 2), elotte(n + 5), utana(n + 5);
for(int i = 1; i <= n; i++) {
pref[i] = pref[i-1] + a[i];
if (a[i]) elotte[i] = i;
else elotte[i] = elotte[i-1];
}
for(int i = n; i > 0; i--) {
suf[i] = suf[i+1] + !a[i];
if (!a[i]) utana[i] = i;
else utana[i] = utana[i+1];
}
int mini = INT_MAX;
for(int i = 0; i <= n; i++) {
mini = min(mini, pref[i] + suf[i+1]);
}
cout << mini << "\n";
vector<int> dpe(n+2), dpu(n+2);
// if (a[1]) dpe[1] = 1;
for(int i = 1; i <= n; i++) {
dpe[i] = dpe[i - 1];
if (a[i] && elotte[i - 1]) {
if (abs(elotte[i - 1] - i) <= 3) {
dpe[i] = dpe[elotte[i - 1] - 1] + 1;
} else {
dpe[i] = dpe[elotte[i - 1]] + 1;
}
} else if (a[i]) {
dpe[i] = 1;
}
}
for(int i = n; i > 0; i--) {
dpu[i] = dpu[i + 1];
if(!a[i] && utana[i + 1]) {
if(abs(utana[i + 1] - i) <= 3) {
dpu[i] = dpu[utana[i + 1] + 1] + 1;
} else {
dpu[i] = dpu[utana[i + 1]] + 1;
}
} else if (!a[i]) {
dpu[i] = 1;
}
}
int mini2 = INT_MAX;
for(int i = 0; i <= n; i++) {
mini2 = min(mini2, dpe[i] + dpu[i+1]);
}
cout << mini2 << "\n";
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 80/80 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1808 KiB | |||
2 | Elfogadva | 0/0 | 12ms | 7700 KiB | |||
3 | Elfogadva | 4/4 | 3ms | 2196 KiB | |||
4 | Elfogadva | 4/4 | 2ms | 2272 KiB | |||
5 | Elfogadva | 4/4 | 3ms | 2396 KiB | |||
6 | Elfogadva | 4/4 | 3ms | 2604 KiB | |||
7 | Elfogadva | 4/4 | 3ms | 2852 KiB | |||
8 | Elfogadva | 4/4 | 3ms | 2972 KiB | |||
9 | Elfogadva | 4/4 | 3ms | 3172 KiB | |||
10 | Elfogadva | 4/4 | 3ms | 3244 KiB | |||
11 | Elfogadva | 4/4 | 3ms | 3344 KiB | |||
12 | Elfogadva | 4/4 | 3ms | 3436 KiB | |||
13 | Elfogadva | 4/4 | 8ms | 9036 KiB | |||
14 | Elfogadva | 4/4 | 8ms | 8992 KiB | |||
15 | Elfogadva | 4/4 | 8ms | 9276 KiB | |||
16 | Elfogadva | 4/4 | 8ms | 9340 KiB | |||
17 | Elfogadva | 4/4 | 8ms | 9332 KiB | |||
18 | Elfogadva | 4/4 | 8ms | 9392 KiB | |||
19 | Elfogadva | 4/4 | 8ms | 9528 KiB | |||
20 | Elfogadva | 4/4 | 10ms | 9612 KiB | |||
21 | Elfogadva | 4/4 | 9ms | 9740 KiB | |||
22 | Elfogadva | 4/4 | 12ms | 9820 KiB |