bovin's blog

By bovin, history, 7 weeks ago, In English

Problem

Can someone help me, I don't understand where the error is in the code and reasoning. I'm getting the wrong answer, I'm getting extra segments in the answer

My code:

#include <iostream>
#include <vector>

using namespace std;

int f(int n, long long s, vector<long long>& a) {
    int ans = 0;
    int i = 0;
    long long sum = 0;
    for(int j = 0; j < n; j++) { // move the right pointer here
        sum += a[j]; // update the amount
        while(sum >= s) { // as long as the sum on the segment [i, j]
                         //is greater than or equal to s, move the left pointer        
            sum -= a[i]; // update the amount
            i++;    // move the right pointer
        }
        // since sum < s -> i is not included in the segment => segment length = j &mdash; i
        ans += (j &mdash; i);
    }
    return ans;
}

int main() {
    int n;
    long long s;
    cin >> n >> s;
    vector<long long> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    cout << f(n, s, a);
    return 0;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by bovin (previous revision, new revision, compare).