Cod sursa(job #2465411)

Utilizator Bulboaca_EugenBulboaca Alexandru Eugen Bulboaca_Eugen Data 30 septembrie 2019 09:17:06
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 3;
int v[MAXN], cnt;
int ans[MAXN], lungime;
void alg(int first, int last){      ///se aplica pe un interval care incepe cu secv de 1 si se termina cu 0
    int contor = 0;                 ///aflam cati de '1' transformama in '0'
    for(int i = first; i <= last; ++i){
        (v[i]) ? contor++ : contor--;
    }
    if(contor < 0) return;
    cnt -= contor;                  ///scadem din nr total de transformari
    for(int i = first; i < first + contor; ++i) ans[i] = 0;
}
int main(){
    char ch;
    int first = 1;
    while(cin.get(ch) and ch != '\n'){
        int x = ch - '0';
        v[++lungime] = x;
        ans[lungime] = x;
    }
    v[lungime + 1] = 1;
    for(int i = 0; i <= lungime; ++i){
        if(i and v[i] and !v[i - 1] and !v[i + 1]) continue;///sarim peste '1' izolati
        if(i and v[i] and !v[i - 1]) first = i;             ///marcam inceputul de secventa de '1'
        if(!v[i] and v[i + 1] and v[i + 2]) alg(first, i);               ///efectuam alg cand se termina secv de '0'
    }
    alg(first, lungime);
    for(int i = 1; i <= lungime; ++i)
        cout << ans[i];
    return 0;
}