Pagini recente » Monitorul de evaluare | Istoria paginii utilizator/mario2005 | Cod sursa (job #108538) | Cod sursa (job #289311) | Cod sursa (job #20090)
Cod sursa(job #20090)
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX(a, b) ( (a) < (b) ? (b) : (a) )
#define MMAX 300001
#define NMAX 21
#define PMAX 20
#define KMAX 5
using namespace std;
int A[NMAX][NMAX][KMAX + 1];
int S[NMAX][NMAX][KMAX + 1];
int V[MMAX], St[NMAX], U[NMAX];
int i, j, k, N, M;
int K, P, maxs, suma, val, rest;
/*void back(int i)
{
int k, j;
if (i > K - 1)
{
int sm = 0, suma = 0;
memset(U, 0, sizeof(U));
for (j = 1; j <= K - 1; j++) sm += St[j], U[St[j]]++;
for (j = 0; j < P; j++) if ((sm + j) % P == 0) break;
St[K] = j, U[St[K]]++;
for (j = 0; j < P; j++)
if (U[j] > A[P][j][0]) { suma = -1; break; }
else suma += S[P][j][U[j]];
maxs = MAX(maxs, suma);
}
else
{
for (k = 0; k < P; k++)
{
St[i] = k;
back(i + 1);
St[i] = -1;
}
}
}*/
void back(int i, int last)
{
int k;
if (i == K)
{
k = (4*P - rest) % P;
val = suma + A[P][k][A[P][k][0]];
maxs = MAX(maxs, val);
}
else
for (k = last; k < P; k++)
if (A[P][k][A[P][k][0]] > 0)
{
suma += A[P][k][A[P][k][0]];
A[P][k][0]++;
rest += k;
back(i+1, k);
A[P][k][0]--;
suma -= A[P][k][A[P][k][0]];
rest -= k;
}
}
int main()
{
freopen("tricouri.in", "r", stdin);
freopen("tricouri.out", "w", stdout);
scanf("%d %d", &N, &M);
for (i = 1; i <= N; i++) scanf("%d", &V[i]);
sort(V + 1, V + N + 1);
for (i = N; i >= 1; i--)
{
for (j = 2; j <= PMAX; j++)
if (A[j][V[i] % j][0] < KMAX)
{
k = V[i] % j;
int nr = ++A[j][k][0];
A[j][k][nr] = V[i], S[j][k][nr] = S[j][k][nr - 1] + A[j][k][nr];
}
}
for (i = 1; i <= M; i++)
{
maxs = -1, suma = 0, rest = 0, val = -1;
scanf("%d %d", &K, &P);
for (j = 0; j < P; j++) A[P][j][0] = 1;
back(1, 0);
if (maxs == 0 && val == 0) { printf("-1\n"); continue; }
printf("%d\n", maxs);
}
return 0;
}