Submission #1273726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273726		nguyenbaoanh	Sum Zero (RMI20_sumzero)	C++20	0 / 100	1 ms	568 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector<ll> a(n+1), pre(n+1,0);
    for(int i=1;i<=n;i++){
        cin >> a[i];
        pre[i] = pre[i-1] + a[i];
    }

    int q; cin >> q;
    vector<pair<int,int>> queries(q);
    for(int i=0;i<q;i++){
        int l,r; cin >> l >> r;
        queries[i] = {l,r};
    }

    // DP
    vector<int> dp(n+1,0);
    unordered_map<ll,int> best; 
    best.reserve(n*2);
    best.max_load_factor(0.7);

    best[0] = 0; // prefix sum = 0 tại vị trí 0

    for(int i=1;i<=n;i++){
        dp[i] = dp[i-1];
        if(best.count(pre[i])){
            dp[i] = max(dp[i], best[pre[i]] + 1);
        }
        best[pre[i]] = dp[i];
    }

    // trả lời query
    for(auto [l,r] : queries){
        cout << dp[r] - dp[l-1] << "\n";
    }
}

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