Submission #1059411

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
10594112024-08-14 23:28:40ArthuroWichPaint By Numbers (IOI16_paint)C++17
59 / 100
1 ms440 KiB
#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') {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...