7613 | 2024. 01. 10 09:07:04 | Ablablabla | Takaros Sorozat (80 pont) | cpp17 | Hibás válasz 46/80 | 9ms | 8216 KiB |
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
string s;
cin >> s;
vector<int> szamok(n + 1, 0);
for(int i = 1; i <= n; i++){
szamok[i] = s[i - 1] - '0';
}
vector<int> pref1(n + 1, 0);
vector<int> suf1(n + 1, 0);
for(int i = 1; i <= n; i++){
pref1[i] = pref1[i - 1] + szamok[i];
}
for(int i = n - 1; i >= 0; i--){
suf1[i] = suf1[i + 1] + (szamok[i + 1] == 0);
}
vector<int> pref2(n + 1, 0);
vector<int> suf2(n + 1, 0);
int nullas = 0;
int egyes = 0;
for(int i = 1; i <= n; i++){
if(szamok[i]){
egyes++;
} else{
nullas++;
}
if(i - 4 >= 1){
if(szamok[i - 4]){
egyes--;
} else{
nullas--;
}
}
pref2[i] = pref2[i - 1] + (szamok[i]);
if(nullas == 2 && egyes == 2){
pref2[i] = min(pref2[i], pref2[i - 4] + 1);
}
}
nullas = 0;
egyes = 0;
for(int i = n - 1; i >= 0; i--){
if(szamok[i + 1]){
egyes++;
} else{
nullas++;
}
if(i + 5 <= n){
if(szamok[i + 5]){
egyes--;
} else{
nullas--;
}
}
suf2[i] = suf2[i + 1] + (szamok[i + 1] == 0);
//cout << i << " : " << suf2[i] << " ";
if(nullas == 2 && egyes == 2){
suf2[i] = min(suf2[i], suf2[i + 4] + 1);
//cout << suf2[i + 4] + 1;
}
//cout << "\n";
}
int mini = 2e9 + 7;
for(int i = 0; i < n; i++){
mini = min(mini, pref1[i] + suf1[i]);
}
cout << mini << "\n";
for(int i = 0; i < n; i++){
mini = min(mini, pref2[i] + suf2[i]);
}
cout << mini << "\n";
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 46/80 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1816 KiB | |||
2 | Hibás válasz | 0/0 | 9ms | 6136 KiB | |||
3 | Hibás válasz | 0/4 | 3ms | 2288 KiB | |||
4 | Elfogadva | 4/4 | 3ms | 2492 KiB | |||
5 | Részben helyes | 2/4 | 3ms | 2700 KiB | |||
6 | Részben helyes | 2/4 | 3ms | 2904 KiB | |||
7 | Részben helyes | 2/4 | 3ms | 2896 KiB | |||
8 | Elfogadva | 4/4 | 3ms | 3024 KiB | |||
9 | Elfogadva | 4/4 | 3ms | 3108 KiB | |||
10 | Hibás válasz | 0/4 | 3ms | 3104 KiB | |||
11 | Elfogadva | 4/4 | 3ms | 3388 KiB | |||
12 | Hibás válasz | 0/4 | 3ms | 3256 KiB | |||
13 | Elfogadva | 4/4 | 8ms | 7080 KiB | |||
14 | Részben helyes | 2/4 | 8ms | 7336 KiB | |||
15 | Elfogadva | 4/4 | 8ms | 7584 KiB | |||
16 | Elfogadva | 4/4 | 8ms | 7644 KiB | |||
17 | Részben helyes | 2/4 | 8ms | 7624 KiB | |||
18 | Hibás válasz | 0/4 | 8ms | 7776 KiB | |||
19 | Részben helyes | 2/4 | 8ms | 8012 KiB | |||
20 | Részben helyes | 2/4 | 8ms | 8112 KiB | |||
21 | Részben helyes | 2/4 | 8ms | 8216 KiB | |||
22 | Részben helyes | 2/4 | 9ms | 8080 KiB |