this time I am getting a prenstation error...
Code: Select all
deleted
Moderator: Board moderators
Code: Select all
#include<stdio.h>
#include<math.h>
#include<string.h>
#define MAXCOINS 102
#define MAXCENTS 455
#define MAXSUM MAXCOINS * MAXCENTS
int nway[MAXSUM + 1];
int ncoins, value, sum;
void main()
{
int test, i, j, min,m,first,flag=1;
scanf("%d", &test);
while (test--)
{
memset(nway, 0, sizeof(nway));
nway[0] = 1;
sum = 0;
m = -1;
scanf("\n%d", &ncoins);
for (i = 0; i < ncoins; i++)
{
scanf("%d", &value);
sum += value;
for (j = MAXSUM - value; j >= 0; j--)
if (nway[j])
nway[j + value] = 1;
}
m = min = 3000;
first = 0;
for (i = 0; i <= sum; i++)
if (nway[i] && abs(2 * i - sum) < min)
{
min = abs(2 * i - sum);
if(min<m)
{
if(i>sum/2)
{
first = i - min;
}
else
first = i;
m = min;
}
}
if(!flag)
printf("\n");
flag = 0;
printf("%d %d\n", first,first+m);
}
}
For the following input:the number of people on the two teams must not differ by more than 1
Your code gives "400 500" where my AC program gives "300 600"1
5
500
100
100
100
100
Consider using stl's hash_map, or making your own hash tables to store the values.Charles Miller wrote:well, tried a different algorithm, but now I keep on getting MLE, so does anyone possibly have any type of ideas they can give to possibly save me some memory here and there. Any help is appreciated.
Well, I thought the same, but I tried this problem last night:Anyway, as I've said, input for this problem is 30Kb long, so I don't understand why Java programmers had to optimize their codes to compensate the time expense. I think it's only a coincidence that they got AC.
Code: Select all
ACed