How to fix timeout?

#1

my code is timing out :frowning:
it is on this problem

here is my code:

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

int main() {
	int piles, howmanyjuicy, juicy, numinpile, sum, juicypile;
	vector<int> storeAns;
	cin >> piles;
	sum = 0;

	for(int i = 0; i < piles; i++){
		cin >> numinpile;
		sum = sum + numinpile;
		storeAns.push_back(sum);
	}

	cin >> howmanyjuicy;

	for(int i = 0; i < howmanyjuicy; i++){
		cin >> juicy;
		juicypile = 0;
		for(int k = 0; k < piles; k++){
				juicypile++;
				if(storeAns[k] >= juicy){
					cout << juicypile << "\n";
					break;
			}
		}
	}
}

does anyone know how to optimize this

#2

What’s your algorithm?

#3

what do you mean?

#4

What’s your code trying to do to solve the problem?

#5

i just get how many piles there are, store all the sum of the piles into a vector, get how many juicy worms there are, find out where each juicy worm is by looping through to find juicypile and printing out juicypile.

#6

It seems that the complexity of your code is too large. You’re iterating through at most 10^5 piles for every worm, which results in a total of 10^{10} observations.

#7

how do i make it faster?

#8

Binary search & prefix sums.

#9

can you go a little more into detail?

#10

Do you know what those concepts are, first of all?

#11

no

#12

I think it’s best if you read up on those first: