제출 #483300

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
483300	2021-10-28 14:47:09	ntabc05101	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	230 ms	79224 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<bits/stdc++.h>
using namespace std;
const int mxN = 10000000;
int dp[mxN + 1], b[mxN + 1];
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int m, Q; cin >> m >> Q;
  int prs[m];
  for (int i = 0; i < m; i++) {
    cin >> prs[i];
  }
  iota(b + 1, b + mxN + 1, 1);
  sort(prs, prs + m);
  int mn = mxN + 1;
  for (int i = 0; i < m; i++) {
    int j;
    for (j = prs[i]; j <= mxN; j += prs[i]) {
      b[j - 1] = j - prs[i];
    }
    mn = min(mn, j - prs[i]);
  }
  for (int i = mxN; i; i--) {
    dp[i] = mxN + 1;
    mn = min(mn, b[i]);
    b[i] = mn;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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