Submission #155751

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
155751	2019-09-30 08:59:52	souhhcong	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	97.78 / 100	483 ms	87132 KiB

brunhilda

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
#include <iostream>
#include <string.h>
using namespace std;
const int N = 1e5+5, MAXN = 1e7+1e6, INF = 1e9+9;
int n, q, x, p[N], dp[MAXN], mx[MAXN];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 0; i < n; i++)
    {
        cin >> p[i];
        for (int j = p[i]-1; j < MAXN; j += p[i])
        {
            mx[j] = max(mx[j], p[i]-1);
        }
    }
  for (int i = MAXN - 2; i >= 0; i--)
    mx[i] = max(mx[i], mx[i+1]-1);
    for (int i = 1; i < MAXN; i++)
    {
        if (mx[i] > 0)
            dp[i] = 1 + dp[i-mx[i]];
        else
            dp[i] = INF;
    }
    while(q--)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 17.77777777777778 / 20
• Subtask 2: 20 / 20
• Subtask 3: 60 / 60