Submission #132436

#TimeUsernameProblemLanguageResultExecution timeMemory
132436wilwxkPaint By Numbers (IOI16_paint)C++14
80 / 100
94 ms400 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; const int MAXN=105; string v, respf; vector<int> qv; short dp[MAXN][105]; int soma[2][MAXN]; int n, q; int psum(int ini, int fim, int k) { if(fim>=n) return MAXN; return soma[k][fim]- (ini==0 ? 0 : soma[k][ini-1]); } short fazdp(int ind, int k) { if(ind>=n) return k>=q; if(v[ind]=='X'&&k>=q) return 0; if(dp[ind][k]!=-1) return dp[ind][k]; // printf("call %d %d\n",ind, k); dp[ind][k]=0; int fim=ind+qv[k]-1; int val=psum(ind, fim, 0); int val2=psum(ind, fim, 1); if(val==0&&v[fim+1]!='X') dp[ind][k]|=fazdp(fim+2, k+1); if(v[ind]!='X') dp[ind][k]|=fazdp(ind+1, k); // printf("dp %d %d >> %d // %d %d\n", ind, k, dp[ind][k], val, val2); return dp[ind][k]; } void recalc() { soma[0][0]=soma[1][0]=0; for(int i=0; i<n; i++) { if(i!=0) soma[0][i]=soma[0][i-1], soma[1][i]=soma[1][i-1]; soma[0][i]+=(v[i]=='_'); soma[1][i]+=(v[i]=='X'); } memset(dp, -1, sizeof(dp)); fazdp(0, 0); } bool testa(int ind, char tipo) { v[ind]=tipo; recalc(); v[ind]='.'; return dp[0][0]; } string solve_puzzle(string s, vector<int> c) { n=s.size(); v=s; v.push_back('_'); respf=s; qv=c; q=qv.size(); for(int i=0; i<n; i++) { if(s[i]!='.') continue; bool a=testa(i, '_'); bool b=testa(i, 'X'); // printf("%d >> ab %d %d\n\n", i, a, b); if(a&&b) respf[i]='?'; else if(a) respf[i]='_'; else respf[i]='X'; } return respf; }

Compilation message (stderr)

paint.cpp: In function 'short int fazdp(int, int)':
paint.cpp:26:6: warning: unused variable 'val2' [-Wunused-variable]
  int val2=psum(ind, fim, 1);
      ^~~~
#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...