Submission #1286038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286038		mattgryts	Sum Zero (RMI20_sumzero)	C++20	0 / 100	1095 ms	684 KiB

sumzero

//Denysiuk Illia will win EJOI 2026
//Denysiuk Illia will win UJGOI 2026
//Антон Перебейнис ничего не ботал
#include <algorithm>
#include <bits/stdc++.h>
#include <functional>
using namespace std;
const long long INF=1e17;
const long long mod=1e9+7;
const long long maxlog=22;
using victor=vector<int>;
using victorl = vector<long long>;
using pll=pair<int,int>;
const int NIGGA=3*1e5+7;
int n;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int q;
    cin>>n;
    victor a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    victor dp(n+1);
    cin>>q;
    while(q--){
        int li,ri;
        cin>>li>>ri;
        for(int i=0;i<=n;i++)dp[i]=0;
        dp[0]=0;
        map<long long,int>lst;
        lst[0]=0;
        long long pref=0;
        for(int i=li;i<=ri;i++){
            pref+=a[i];
            dp[i]=dp[i-1];
            if(lst.count(pref)!=0)dp[i]=max(dp[i],1+dp[lst[pref]]);
            lst[pref]=i;
        }
        cout<<dp[ri]<<'\n';
    }
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 39
• Subtask 3: 0 / 39