Submission #1050993

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050993		fv3	Paint By Numbers (IOI16_paint)	C++14	0 / 100	0 ms	344 KiB

paint

#include"paint.h"
#include<bits/stdc++.h>
using namespace std;string solve_puzzle(string s, vector<int> c){const int K = c.size();const int N = s.size();s = (char)95 + s + (char)95;vector<int> preSum(N+3);for (int i = 0; i <= N + 2; i++)preSum[i+1] = preSum[i] + (int)(s[i] ==95);vector<vector<int>>DP_r(N+2,vector<int>(K+1));DP_r[0][0] = 1;for (int i = 0; i <= N; i++){if (s[i] == 88) continue;for (int k = 0; k <= K; k++){if (!DP_r[i][k]) continue;if (s[i + 1] != 88)DP_r[i+1][k] = 1;if (k == K || i + c[k] + 1 >= N + 2) continue;if (preSum[i + c[k] + 1] - preSum[i + 1]) continue;if (s[i + c[k] + 1] == 88) continue;DP_r[i + c[k] + 1][k + 1] = 1;}}vector<vector<int>> DP_l(N+2,vector<int>(K+1));DP_l[N+1][K] = 1;for (int i = N+1; i >= 1; i--){if (s[i] == 88)continue;for (int k = 0; k <= K; k++){if (!DP_l[i][k]) continue;if (s[i - 1] != 'X')DP_l[i-1][k] = 1;if (k == 0 || i - c[k-1] - 1 < 0) continue;if (preSum[i] - preSum[i - c[k-1]]) continue;if (s[i - c[k-1] - 1] == 88) continue;DP_l[i - c[k-1] - 1][k - 1] = 1;}}vector<int> ps(N+2);for (int i = 0; i < N + 2; i++){if (s[i] == 88) continue;for (int k = 0; k < K; k++){if (i + c[k] + 1 >= N + 2 || !DP_r[i][k] || !DP_l[i + c[k] + 1][k+1]) continue;if (i + c[k] + 1 >= N + 2) continue;if (preSum[i + c[k] + 1] - preSum[i + 1]) continue;if (s[i + c[k] + 1] == 88) continue;ps[i+1]++;ps[i+c[k]+1]--;}}string res(N, 95);int sum = 0;for (int i = 1; i <= N; i++){sum += ps[i];if (s[i] == 88){res[i-1] = 88;continue;}if (sum){bool ok = true;for (int k = 0; k <= K; k++){if (!DP_r[i][k] || !DP_l[i][k])ok = false;res[i-1] = 63;break;}if (ok) res[i-1] = 88;}}return res;}

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