# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
652742 | alvinpiter | Paint By Numbers (IOI16_paint) | C++14 | 228 ms | 85188 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.
/*
color -> 0 means white, 1 means black
dpPrefix[j][k][color] -> Can the first j character obey the first k rules such that the j-th character is painted "color"
dpSuffix[j][k][color] -> Can the suffix starting from j-th character obey the rules starting from the k-th such that s[j] is painted "color"
For each index j, define:
canBlack[j] -> > 0 if there is a solution such that s[j] is painted black, 0 otherwise.
canWhite[j] -> > 0 if there is a solution such that s[j] is painted white, 0 otherwise.
canBlack[j] = dpPrefix[j][k][1] && dpSuffix[j + 1][k + 1][0]
canWhite[j] = dpPrefix[j][k][0] && (dpSuffix[j + 1][k + 1][0] || dpSuffix[j + 1][k + 1][1])
Try every possible k.
Complexity: O(NK)
*/
#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200000
#define MAXK 100
bool dpPrefix[MAXN + 3][MAXK + 3][2], dpSuffix[MAXN + 3][MAXK + 3][2];
int canBlack[MAXN + 3], canWhite[MAXN + 3];
int cntBlack[MAXN + 3], cntWhite[MAXN + 3];
std::string solve_puzzle(std::string s, std::vector<int> c) {
int N = s.length();
int K = c.size();
Compilation message (stderr)
# | 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... |