Pagini recente » Cod sursa (job #39011) | Cod sursa (job #3187303) | Cod sursa (job #2905781) | Cod sursa (job #34407) | Cod sursa (job #51002)
Cod sursa(job #51002)
#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;
}