Pagini recente » Cod sursa (job #2320879) | Cod sursa (job #3287866) | Cod sursa (job #175876) | Cod sursa (job #1659568) | Cod sursa (job #1900769)
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
FILE *f1 = fopen("tribut.in", "r");
FILE *f2 = fopen("tribut.out", "w");
struct uniune
{
int sum, nr;
int system[101];
}v[101];
int tribut[101], i, j, t, n, m, sum ,nr, k, f[101], total = 0;
int comp(uniune a, uniune b)
{
if (a.sum > b.sum) return 1;
return 0;
}
int comp2(int a, int b)
{
if (f[a] < f[b]) return 1;
if (f[a] == f[b] && tribut[a] > tribut[b]) return 1;
return 0;
}
int main()
{
fscanf(f1, "%d", &t);
for (i = 1; i <= t; i++)
{
fscanf(f1, "%d%d", &n, &m);
memset(f, 0, sizeof(f));
total = 0;
for (j = 1; j <= n; j++)
fscanf(f1, "%d", &tribut[j]);
for (j = 1; j <= m; j++)
{
fscanf(f1, "%d%d", &nr, &sum);
v[j].sum = sum; v[j].nr = nr;
for (k = 1; k <= nr; k++)
{
fscanf(f1, "%d", &v[j].system[k]);
if (v[j].sum != 0)
f[v[j].system[k]]++;
}
}
sort(v + 1, v + m + 1, comp);
j = 1;
while(j <= m && v[j].sum > 0)
{
sort(v[j].system + 1, v[j].system + v[j].nr + 1, comp2);
k = 1;
while (k <= v[j].nr && v[j].sum > 0)
{
if (v[j].sum >= tribut[v[j].system[k]])
{
total += tribut[v[j].system[k]];
v[j].sum -= tribut[v[j].system[k]];
tribut[v[j].system[k]] = 0;
} else
{
total += v[j].sum;
tribut[v[j].system[k]] -= v[j].sum;
v[j].sum = 0;
}
k++;
}
j++;
}
fprintf(f2, "%d\n", total);
}
fclose(f1);
fclose(f2);
return 0;
}