Cod sursa(job #2882456)
Utilizator | Bratu Mihai-Alexandru Mihai7218 | Data | 31 martie 2022 14:24:28 |
---|---|---|---|
Problema | Sate2 | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva ICPC | Marime | 2.21 kb |
#include <fstream>
#include <vector>
#include <map>
using namespace std;
int main()
{
ifstream fin("sate2.in");
ofstream fout("sate2.out");
int t;
fin >> t;
for (int tc = 0; tc < t; ++tc)
{
int n, m, k, x, mx = 0;
fin >> n >> m >> k;
vector <int> d(m/k+1, 0), v;
vector <vector <vector <int> > > ds(m/k+1);
for (int i = 0; i < n; ++i)
fin >> x, v.push_back(x), mx = max(mx, x);
if ((m/k)*k != m || mx > m/k)
{
fout << "NU\n";
continue;
}
d[0] = 1;
for (int i = 0; i < n; ++i)
{
for (int j = m/k; j >= v[i]; --j)
{
if (d[j-v[i]] == 1)
{
d[j] = 1;
for (int it = 0; it < ds[j-v[i]].size(); ++it)
{
ds[j].push_back(ds[j-v[i]][it]);
(*ds[j].rbegin()).push_back(i);
}
if (j == v[i])
{
vector <int> t;
t.push_back(i);
ds[j].push_back(t);
}
}
}
}
int possible;
for (int i = 0; i < ds[m/k].size(); i++)
{
map <int, int> fr; possible = 0;
for (int l = i; l < ds[m/k].size(); l++)
{
bool check = 1;
for (int j = 0; j < ds[m/k][l].size(); j++)
{
if (fr[ds[m/k][l][j]] > 0)
{
check = 0;
break;
}
}
if (check)
{
for (int j = 0; j < ds[m/k][l].size(); j++)
fr[ds[m/k][l][j]]++;
possible++;
}
if (possible == k)
break;
}
if (possible == k)
break;
}
if (possible == k)
fout << "DA\n";
else fout << "NU\n";
}
fout.close();
return 0;
}