1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
ll Q, M, N, K, T, ans[10005], A[105], B[105];
ll dp(ll d)
{
    ll b;
    memset(ans, 0xFF, sizeof(ans));
    ans[0] = 0;
    for(int i = 0; i < M; i++)
    {
        b = B[i] / d;
        for(int j = 0; j <= K; j++)
        {
            int idx = min(j + b, K);
            if(ans[j] == -1LL)
            {
                continue;
            }
            if(ans[idx] == -1LL)
            {
                ans[idx] = ans[j] + A[i];
            }
            else
            {
                ans[idx] = min(ans[idx], ans[j] + A[i]);
            }
        }
    }
    return ans[K];
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX