제출 #673758

#제출 시각아이디문제언어결과실행 시간메모리
673758tbzardPaint By Numbers (IOI16_paint)C++14
59 / 100
1 ms340 KiB
#include <bits/stdc++.h> using namespace std; bool space[200001]; int add[200002]; bool dp[200001][101], dp2[200001][101]; int sum[200001]; string solve_puzzle(string s, vector<int> c){ int n = s.length(), k = c.size(); for(int i=1;i<=n;i++){ if(s[i-1] == '.' || s[i-1] == 'X') sum[i]++; sum[i] += sum[i-1]; } dp[0][0] = 1; for(int i=1;i<=n;i++){ for(int j=0;j<=k;j++){ if(dp[i-1][j] && (s[i-1] == '_' || s[i-1] == '.')) dp[i][j] = 1; if(j == 0){ if(j < k && i >= c[j] && sum[i]-sum[i-c[j]] == c[j] && dp[i-c[j]][j]){ dp[i][j+1] = 1; } } else{ if(j < k && i >= c[j]+1 && sum[i]-sum[i-c[j]] == c[j] && (s[i-c[j]-1] == '_' || s[i-c[j]-1] == '.')){ dp[i][j+1] |= dp[i-c[j]-1][j]; } } } } dp2[n][k] = 1; for(int i=n;i>=1;i--){ for(int j=k;j>=0;j--){ if(dp2[i][j]){ if(dp[i-1][j] && (s[i-1] == '_' || s[i-1] == '.')){ dp2[i-1][j] = 1; space[i] = 1; } if(j == 1){ if(j > 0 && i >= c[j-1] && sum[i]-sum[i-c[j-1]] == c[j-1] && dp[i-c[j-1]][j-1]){ add[i]++; add[i-c[j-1]]--; dp2[i-c[j-1]][j-1] = 1; } } else{ if(j > 0 && i >= c[j-1]+1 && sum[i]-sum[i-c[j-1]] == c[j-1] && (s[i-c[j-1]-1] == '_' || s[i-c[j-1]-1] == '.')){ add[i]++; add[i-c[j-1]]--; space[i-c[j-1]] = 1; dp2[i-c[j-1]-1][j-1] = 1; } } } } } string ans = ""; for(int i=0;i<n;i++) ans += '?'; for(int i=n;i>=1;i--){ add[i] += add[i+1]; if(add[i] && !space[i]) ans[i-1] = 'X'; else if(!add[i] && space[i]) ans[i-1] = '_'; } 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...