# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1059411 | ArthuroWich | Paint By Numbers (IOI16_paint) | C++17 | 1 ms | 440 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
string solve_puzzle(string s, vector<int> c) {
int n = s.length(), k = c.size();
s = "@"+s+"@";
vector<int> pref(n+2, 0);
vector<vector<int>> dpl(n+2, vector<int>(k+1, 0)), dpr(n+2, vector<int>(k+1, 0));
for (int i = 1; i <= n+1; i++) {
pref[i] = pref[i-1];
if (s[i] == '_') {
pref[i]++;
}
}
dpl[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
if (s[i] != 'X') {
dpl[i][j] |= dpl[i-1][j];
}
if (j > 0 && i-c[j-1] >= 0 && pref[i]-pref[i-c[j-1]] == 0 && (i-c[j-1] <= 0 || s[i-c[j-1]] != 'X')) {
dpl[i][j] |= dpl[max(0, i-c[j-1]-1)][j-1];
}
}
}
reverse(c.begin(), c.end());
dpr[n+1][0] = 1;
for (int i = n; i >= 1; i--) {
for (int j = 0; j <= k; j++) {
if (s[i] != 'X') {
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |