Submission #321210

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
321210	2020-11-11 14:00:13	quocnguyen1012	Paint By Numbers (IOI16_paint)	C++14	100 / 100	468 ms	44596 KiB

paint

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 maxn = 2e5 + 5;
bool pref[maxn][105], suf[maxn][105];
int N, K, sum[maxn];
int black[maxn];
bool white[maxn];
string res;
string solve_puzzle(string str, vector<int> req) {
  N = str.size();
  K = req.size();
  for (int i = 1; i <= N; ++i) {
    sum[i] = sum[i - 1] + (str[i - 1] == '_');
  }
  pref[0][0] = true;
  suf[N][K] = true;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j <= K; ++j) {
      if (str[i] != 'X') {
        pref[i + 1][j] |= pref[i][j];
      }
      if (j < K) {
        if (i + req[j] < N && str[i + req[j]] != 'X' && sum[i + req[j]] == sum[i]) {
          pref[i + req[j] + 1][j + 1] |= pref[i][j];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10