bovin's blog

By bovin, history, 4 weeks ago, In English

Problem

I get the error "Time limit exceeded on test 25". I can't understand why

#include <iostream>
#include <climits>

using namespace std;

int main()
{
    int a[1000];
    int n;
    long long p;
    cin >> n >> p;
    for(int i = 0; i < n; i++) cin >> a[i];
    long long amount = 0;
    int count = 0, ans_count = INT_MAX, num_track;
    int j = 0;
    for(int i = 0;  i < n; i++) {
        while(amount < p) {
            amount += a[j % n];
            j++;
            count++;
        }
        if(ans_count > count) {
            ans_count = count;
            num_track = i + 1;
        }
        amount -= a[i];
        count--;
    }
    cout << num_track << " " << ans_count;
    return 0;
}

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By bovin, history, 6 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;
}

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By bovin, history, 6 weeks ago, translation, In English

Problem My code crashes on one of the tests. I assumed it was an overflow problem and tried to fix it, but it didn't work. Now i don't understand what could be the error.

Code:

#include <iostream>
#include <vector>
 
using namespace std;
 
int f(int n, int m, vector<long long int>& nums1, vector<long long int>&nums2) {
    int i = 0, j = 0;
    long long int count = 0, cnt1, cnt2;
    while(i < n && j < m) {
        if(nums1[i] < nums2[j]) i++;
        else if(nums1[i] > nums2[j]) j++;
        else { // nums1[i] == nums2[j]
            cnt1 = 0, cnt2 = 0;
            int val = nums1[i];
            while(i < n && nums1[i] == val) {
                cnt1++;
                i++;
            }
            while(j < m && nums2[j] == val) {
                cnt2++;
                j++;
            }
            count += cnt1 * cnt2;
        }
    }
    return count;
}
 
int main()
{
    int n, m;
    cin >> n >> m;
    vector<long long int> nums1(n);
    vector<long long int> nums2(m);
    for(int i = 0; i < n; i++) cin >> nums1[i];
    for(int i = 0; i < m; i++) cin >> nums2[i];
    int ans = f(n, m, nums1, nums2);
    cout << ans;
    return 0;
}

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it