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 algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---

Reply via email to