Помогите решить задачку, мой код не проходит тесты из-за времени работы. Дан массив неотрицательных чисел, необходимой найти максимальный отрезок массива, с суммой меньше заданной. Я ищу эту суммы обычным while, но решение получается слишком медленное, не знаю, как его ускорить.
Вот мой код
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
uint32_t Query (uint32_t l, uint64_t sum,const uint32_t *arr,uint32_t n);
int main() {;
FILE *f = fopen("input.txt","r");
FILE *s = fopen("output.txt","w");
uint32_t n,t,l;
uint64_t sum;
fscanf(f,"%d",&n);
fscanf(f,"%d",&t);
uint32_t *arr = malloc(sizeof (uint32_t) * n);
for( int i = 0; i < n; i++){
fscanf(f,"%d",&arr[i]);
}
for( int i = 0; i < t; i++){
fscanf(f,"%d %lld",&l,&sum);
Query(l,sum,arr,n);
}
return 0;
}
uint32_t Query (uint32_t l, uint64_t sum,const uint32_t *arr,uint32_t n){
uint64_t summy = 0;
uint32_t i;
for( i = l ; i < n; i++){
summy+= arr[i];
if (summy > sum){
return i;
}
}
return i;
}
Пример теста Входные данные
10 7
1
4
0
5
6
0
0
1
5
3
0 100
0 5
4 11
4 12
4 13
10 100
Выходные данные
10
3
8
9
9
10
8
Первые 2 цифры - это кол-во элементов массива и кол-во вопросов к нему.
Дальше идут n элементов массива.
Потом идут пары цифр l и sum - необходимо найти максимальный отрезок массива с началом в l и суммой меньше, чем sum.
Индексация идёт, как в обычном C. Начинается массив с 0 и идёт до n.
Друзья советуют искать сумму от 0 до i, а потом как-то бинарным поиском находить нужный отрезок, но я совсем не понимаю как такое реализовать(