Submission #301236

#TimeUsernameProblemLanguageResultExecution timeMemory
301236williamMBDKPaint By Numbers (IOI16_paint)C++17
59 / 100
1 ms384 KiB
#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 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...