SIGKILL в спой-лкс

При отправке решения отображается ошибка времени выполнения SIGKILL. Я не знаю, почему !!! Пожалуйста помоги...!! Я не собираюсь беспокоиться о TLE, я просто хочу знать, в чем причина SIGKILL. И после этого вы можете предложить мне любую более быструю процедуру для более эффективного решения этой проблемы. Пожалуйста, помогите, я тоже застрял в этой проблеме. долгое время, но я не могу найти, как появляется эта ошибка времени выполнения. Вот мой код::

#include<stdio.h>

//#define max(a,b) a>b?a:b
int max (int a,int  b){
     if (a>b)
        return a;
     else return b;

}
int V[500];
int W[500];
int F[501][1000001];



int knapsack(int n,int cap){
    if (n==0 || cap==0){
        F[n][cap]=0;
        return 0;
    }
    else if (cap<1000001){
        if (F[n][cap]!=0)
            return F[n][cap];
        else {
            if (W[n-1]>cap){
                 F[n][cap]=knapsack(n-1,cap);
             }
             else {
                 F[n][cap]=max(V[n-1]+knapsack(n-1,cap-W[n-1]),knapsack(n-1,cap));
             }

             return F[n][cap];
        }
    }
    else {
        if (W[n-1]>cap){
            return knapsack(n-1,cap);
            }
        else {
            return max(V[n-1]+knapsack(n-1,cap-W[n-1]),knapsack(n-1,cap));
        }

    }

}

main() {
    int k,n,i;
    scanf("%d %d",&k,&n);

    for (i =0 ;i<n ;i++){
        scanf("%d %d",&V[i],&W[i]);

    }

    printf("%d\n",knapsack(n,k));

 } 

person Saikat Dutta    schedule 24.08.2015    source источник


Ответы (1)


Причиной SIGKILL является ваш массив F[501][1000001];

Это связано с тем, что глобальные переменные получают память из кучи. Теперь ограничение памяти LKS на Spoj составляет 1536 МБ, что эквивалентно 1,6E9 байтам. Поскольку int имеет размер 4 байта, максимальный размер массива int может составлять приблизительно 4E8, и вы объявили массив int размером 5E8. Таким образом, уменьшение размера массива может избавить вас от SIGKILL.

Чтобы решить проблему, вам нужно создать массив для dp из 2 строк, а затем вычислить ответ.

int dp[2][2000001];

Надеюсь, это поможет. :)

person dazzieta    schedule 24.08.2015
comment
Спасибо @utkarsh13 за ваш ответ. Я не нашел вашего способа решить проблему, но позвольте мне попробовать это понять. Еще раз спасибо = D - person Saikat Dutta; 26.08.2015
comment
Обратитесь к этой ссылке stackoverflow.com/questions/17246670/ - person dazzieta; 27.08.2015