Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; //Os valores das somas podem passar de 2*10^9,
//então usaremos essa abreviação pra long long
const int MAXN = 2e5 + 10;
set<ll> s;
ll t[MAXN];
int main(){
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%lld", &t[i]);
//lemos os valores das transições
}
s.insert(0);
//iniciaremos o set com valor 0
//para não testarmos se o prefixo é igual a 0
//podendo então usar o algoritmo descrito normalmente
int ans = 0;
ll pref = 0;
for(int i = 1; i <= n; i++){
pref += t[i];
if(s.find(pref) != s.end()){
//se existe algum valor no set igual a soma atual,
//sabemos que existe um intervalo de soma 0
//portanto, inserimos uma nova transação e reiniciamos o set
ans++;
s.clear();
s.insert(0);
pref = t[i];
}
//adicionamos o prefixo atual
s.insert(pref);
}
printf("%d\n",ans );
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment