bovin's blog

By bovin, history, 6 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;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

p is upto $$$10$$$$$$^1$$$$$$^8$$$, and n is only 1000

while(amount < p) {
    amount += a[j % n];
    j++;
    count++;
}

so this loop can run upto $$$10$$$$$$^1$$$$$$^5$$$ times assuming all the values in a are 1