제출 #620088

#제출 시각아이디문제언어결과실행 시간메모리
620088sofapudenPaint By Numbers (IOI16_paint)C++14
0 / 100
94 ms167176 KiB
#include "paint.h" #include<bits/stdc++.h> using namespace std; const int mxN = 2e5+5; const int mxK = 1e2+5; int dp[mxN][mxK]; int N, K; vector<int> C; string S; vector<int> W, B; vector<int> pW; int f(int n, int k){ if(n > N)return 0; if(n == N)return k == K; if(dp[n][k] != -1)return dp[n][k]; if(S[n] == 'X'){ if(k == K)return dp[n][k] = 0; if(n+C[k] > N)return dp[n][k] = 0; if(pW[n+C[k]-1] != (n ? pW[n-1] : 0))return dp[n][k] = 0; int se; if(n+C[k] == N)se = (k+1 == K); else if(S[n+C[k]] == 'X')return dp[n][k] = 0; else se = f(n+C[k]+1,k+1); if(se){B[n] = max(B[n],C[k]);W[n+C[k]]=1;} return dp[n][k] = se; } else if(S[n] == '_'){ W[n] = 1; return dp[n][k] = f(n+1,k); } else{ int fi; if(k == K)fi = 0; else if(n+C[k] > N)fi = 0; else if(pW[n+C[k]-1] != (n ? pW[n-1] : 0))fi = 0; else if(n+C[k] == N)fi = (k+1 == K); else if(S[n+C[k]] == 'X')fi = 0; else fi = f(n+C[k]+1,k+1); if(fi){B[n] = max(B[n],C[k]);W[n+C[k]]=1;} int se = f(n+1,k); W[n] |= se; return dp[n][k] = fi|se; } } string solve_puzzle(string s, vector<int> c) { S = s; C = c; N = s.size(); K = c.size(); W.resize(N,0); B.resize(N,0); pW.resize(N,0); for(int i = 0; i < N; ++i)pW[i] = (S[i] == '_') + (i ? pW[i-1] : 0); for(int i = 0; i < mxN; ++i)for(int j = 0; j < mxK; ++j)dp[i][j] = -1; f(0,0); int cn = 0; for(int i = 0; i < N; ++i){ cn = max(cn-1,B[i]); if(W[i] && cn > 0)S[i] = '?'; else if(W[i])S[i] = '_'; else if(cn > 0)S[i] = 'X'; } return S; }
#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...