이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "paint.h"
#include <cstdlib>
using namespace std;
const int MN = 100;
int N, K;
string S;
vector<int> C;
vector<vector<int>> dp (MN + 10, vector<int> (101, -1));
vector<bool> x (MN), w(MN);
int rec(int i1, int i2){
//if(dp[i1][i2] != -1) return dp[i1][i2];
if(i2 == K){
dp[i1][i2] = 1;
for(int i = i1; i < N; i++){
if(S[i] == 'X'){
dp[i1][i2] = 0;
}
}
if(dp[i1][i2]){
for(int i = i1; i < N; i++){
w[i] = 1;
}
}
return dp[i1][i2];
}
dp[i1][i2] = 0;
for(int i = i1; i + C[i2] - 1 < N; i++){
bool b = 1;
for(int j = i; j < i + C[i2]; j++){
if(S[j] == '_'){
b = 0;
break;
}
}
if(b && rec(i + C[i2] + 1, i2+1)){
int t = i + C[i2];
if(t < N){
if(S[t] == 'X') goto next;
else w[t] = 1;
}
for(int j = i; j < i + C[i2]; j++){
x[j] = 1;
}
for(int j = i1; j < i; j++){
w[j] = 1;
}
dp[i1][i2] = 1;
// optimize this
}
next:
if(S[i] == 'X') break;
}
//cout << i1 << " " << i2 << " " << dp[i1][i2] << endl;
return dp[i1][i2];
}
string solve_puzzle(string _s, vector<int> _c) {
//cout << "input: " << _s << endl;
S = _s;
C = _c;
//for(auto e : C) cout << e << " ";
//cout << endl;
N = S.length();
K = C.size();
rec(0, 0);
string res (N, '?');
for(int i = 0; i < N; i++){
if(x[i] && !w[i]) res[i] = 'X';
else if(!x[i] && w[i]) res[i] = '_';
}
return res;
}
# | 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... |