제출 #388855

#제출 시각아이디문제언어결과실행 시간메모리
388855ParsaAlizadehPaint By Numbers (IOI16_paint)C++17
59 / 100
1 ms208 KiB
#include <bits/stdc++.h> #include "paint.h" using namespace std; string solve_puzzle(string s, vector<int> c) { s = "_" + s; int const N = s.size(); int const K = c.size(); vector<int> ps(N + 1, 0); for (int i = 0; i < N; i++) ps[i + 1] = s[i] == '_'; partial_sum(begin(ps), end(ps), begin(ps)); vector<vector<bool>> dp(N + 1, vector<bool>(K + 1, false)); dp[0][0] = true; for (int i = 1; i <= N; i++) { for (int j = 0; j <= K; j++) { dp[i][j] = dp[i][j] || (s[i - 1] != 'X' && dp[i - 1][j]); if (j && i > c[j - 1] && s[i - c[j - 1] - 1] != 'X' && ps[i] - ps[i - c[j - 1]] == 0) { dp[i][j] = dp[i][j] || dp[i - c[j - 1] - 1][j - 1]; } } } vector<int> cX(N + 1, 0), c_(N, 0); vector<vector<bool>> mark(N + 1, vector<bool>(K + 1, false)); mark[N][K] = true; for (int i = N; i >= 1; i--) { for (int j = K; j >= 0; j--) { if (!mark[i][j]) continue; if (s[i - 1] != 'X' && dp[i - 1][j]) { mark[i - 1][j] = true; c_[i - 1]++; } if ( j && i > c[j - 1] && s[i - c[j - 1] - 1] != 'X' && ps[i] - ps[i - c[j - 1]] == 0 && dp[i - c[j - 1]][j - 1] ) { mark[i - c[j - 1] - 1][j - 1] = true; cX[i - c[j - 1]]++; cX[i]--; c_[i - c[j - 1] - 1]++; } } } partial_sum(begin(cX), end(cX), begin(cX)); string ans; for (int i = 1; i < N; i++) { if (c_[i] && cX[i]) ans.push_back('?'); else if (c_[i]) ans.push_back('_'); else ans.push_back('X'); } return ans; }
#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...