Hi there,
This problem is from: http://acm.pku.edu.cn/JudgeOnline/problem?id=1742
I got TLE and don't know how to optimize it. Can anybody help me out?
The following is my code:
#include <stdio.h>
#include <algorithm>
#include <memory.h>
#include <string.h>
#include <vector>
using namespace std;
const int MAX_N = 101;
const int MAX_M = 100001;
int f[MAX_M];
int main()
{
//freopen ("D:/VC Project/Test/Test/Data.txt", "r", stdin);
//Solve ();
int n = 0;
int m = 0;
int a[MAX_N] = {0};
int c[MAX_N] = {0};
while (true)
{
scanf ("%d%d", &n, &m);
if (n == 0 && m == 0)
{
break;
}
int i = 0;
for (i = 0; i < n; ++i)
{
scanf ("%d", a+i);
}
for (i = 0; i < n; ++i)
{
scanf ("%d", c+i);
}
int k = 0;
int v[MAX_M] = {0};
memset(f, 0, sizeof(f));
f[0] = 1;
int count = 0;
for (i = 0; i < n; ++i)
{
memset(v, 0, sizeof(v));
for (k = 0; k <= m - a[i]; ++k)
{
if (f[k] != 0 && f[k+a[i]] == 0 && v[k] < c[i])
{
f[k+a[i]] = 1;
v[k+a[i]] = v[k] + 1;
++count;
}
}
}
printf ("%d\n", count);
}
return 0;
}
Thanks in advance!
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
