# WA - KSUM (LunchTime)

I have followed the editorial and I have done the problem in C,But I am getting wrong answer.
Here is the snippet of the code:

``````#include <stdio.h>
typedef struct node {
long long  sum;
int l_index;
int r_index;
}node_t;

long long  A[100005];
node_t Q[100005];

/*The number of elements in Q-array*/
int N = 0;

void swap(node_t* Q ,int index,int  index2){

node_t temp;
#if 0
temp.sum = Q[index].sum;
temp.l_index = Q[index].l_index;
temp.r_index = Q[index].r_index;

Q[index].sum = Q[index2].sum;
Q[index].l_index = Q[index2].l_index;
Q[index].r_index = Q[index2].r_index;

Q[index2].sum = temp.sum;
Q[index2].l_index = temp.l_index;
Q[index2].r_index = temp.r_index;

#endif
temp = Q[index];
Q[index] = Q[index2];
Q[index2] = temp;
}

void insert(node_t * Q,long long sum, int l_index, int r_index){

int index;

N=N+1;

index = N;

Q[N].sum = sum;
Q[N].l_index = l_index;
Q[N].r_index = r_index;

/*This is the concept of heapify up*/
while(index > 1 && Q[index/2].sum < Q[index].sum) {
swap(Q,index/2,index);
index/=2;
}

}

/*This uses the concept of heapify down*/
void  max_heapify(node_t* Q, int index){

int largest,left,right;

left=2*index;
right=2*index+1;

if(right<=N && Q[index].sum < Q[right].sum)
largest=right;
else
largest=index;

if(left<=N && Q[largest].sum < Q.sum)
largest=left;

if(largest != index){
swap(Q,index,largest);
max_heapify(Q,largest);
}
}

int main() {

int  n, k, i, left, right;
long long sum = 0;
node_t temp;

scanf("%d%d", &n, &k);

for(i = 1; i <= n; i++) {
scanf("%lld", A + i);
sum += A[i];
}

/*We will insert the sum*/
insert(Q, sum, 1, n);

/*We will loop only through the min((n*(n+1)/2, 10^5)*/
for(i = 0; i < k; i++) {

temp = Q[1];
left =  temp.l_index;
right = temp.r_index;
Q[1].sum = -1;

max_heapify(Q, 1);

N--;
printf("%lld ", temp.sum);

if(left != right) {

insert(Q, temp.sum - A, left + 1, right);
insert(Q, temp.sum - A[right], left, right - 1);
}

}

printf("\n");

return 0;
}``````

My guess: Youâ€™re counting intervals multiple times. For example [2.n-1] might get inserted twice, smaller intervals even more often. In the tutorial a set is used instead if a priority queue, thereby eliminating duplicates.

1 Like