Cod sursa(job #51002)

Utilizator flo_demonBunau Florin flo_demon Data 9 aprilie 2007 17:27:27
Problema Oite Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>
#include <iostream>
#include <vector>
#include <map>

using namespace std;

int aux, n, sum;
vector<map<int, int> > states;
map<int, int>::reverse_iterator start, end;
vector<int> elem;

int main()
{
    //read
    FILE *fin = fopen("oite.in", "r");
    fscanf(fin, "%d%d", &n, &sum);
    for (int i = 1; i <= n; ++i)
    {
        fscanf(fin, "%d", &aux);
        elem.push_back(aux);
    }
    fclose(fin);
    
    //solve
    sort(elem.begin(), elem.end());
    int K;
    states.resize(6);
    states[0][0] = 1;
    for (int i = 0; i < n; ++i)
        for (int j = 3; j >= 0; --j)
        {
            start = states[j].rbegin();
            end = states[j].rend();
            for (; start != end; ++start)
                if ((*start).first <= sum - elem[i])
                {
                    K = (*start).first+elem[i];
                    states[j+1][K] += states[j][(*start).first] ;
                }
        }   
    
    //write
    aux = states[4][sum];
    FILE *fout = fopen("oite.out", "w");
    fprintf(fout, "%d\n", aux);
    fclose(fout);
    
    return 0;
    
}