Cod sursa(job #18385)

Utilizator StTwisterKerekes Felix StTwister Data 18 februarie 2007 11:53:13
Problema Ghiozdan Scor 20
Compilator cpp Status done
Runda preONI 2007, Runda 2, Clasele 11-12 Marime 1.75 kb
#include <stdio.h>
#include <string>
#include <map>

#define NMAX 20001
#define LMAX 201
#define GMAX 75001
#define INF 0x3f3f3f3f

using namespace std;

typedef map<int,int> mii;

int A[LMAX];
int minN[GMAX];
map<int, int> used[GMAX];
int N, G;
int best;

int main()
{
    freopen("ghiozdan.in", "r", stdin);
    freopen("ghiozdan.out", "w", stdout);

    memset(minN, 0x3f, sizeof(minN));
    memset(A, 0, sizeof(A));

    scanf("%d %d", &N, &G);
    for (int i = 1; i<=N; ++i)
    {
        int x;
        scanf("%d", &x);
        ++A[x];
    }

    minN[0] = 0;
    for (int i = 1; i<=G; ++i)
    {
        minN[i] = INF;
        for (int j = 1; j<=200; ++j)
        {
            if (i-j >= 0)
            {
                if (minN[i-j]+1<minN[i] && used[i-j][j] < A[j])
                {
                    minN[i] = minN[i-j] + 1;
                    // TODO: improve copy procedure
                    for (int k = 1; k<=200; ++k)
                    {
                        used[i][k] = used[i-j][k];
                    }
                    //used[i].clear();
                    //for (mii::iterator k = used[i-j].begin(); k != used[i-j].end(); ++k)
                    //{
                    //    used[i].insert(*k);
                    //}
                    ++used[i][j];
                }
            }
            else
                break;
        }
        if (minN[i] != INF)
            best = i;
    }

    printf("%d %d\n", best, minN[best]);
    for (mii::iterator i = used[best].begin(); i != used[best].end(); ++i)
    {
        int nr = (*i).first;
        int cnt = (*i).second;
        for (int j = 1; j<=cnt; ++j)
        {
            printf("%d\n", nr);
        }
    }

}