Submission #69137

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
691372018-08-20 06:35:25Sa1378Paint By Numbers (IOI16_paint)C++17
90 / 100
2078 ms37764 KiB
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N ((int)201*1000)
#define K ((int)101)
int n,k;
int lft_[N],rght_[N];
bool dpl[N][K],dpr[N][K];
string solve_puzzle(string s, vector<int> c)
{
n=s.size();k=c.size();
s='.'+s+'.';
lft_[0]=0;
for(int i=1;i<=n;i++)
lft_[i]=max(lft_[i-1],(s[i]=='_'?i:0));
rght_[n+1]=n+1;
for(int i=n;i>=1;i--)
rght_[i]=min(rght_[i+1],(s[i]=='_'?i:n+1));
dpl[0][0]=dpr[n+1][k+1]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=k;j++)
{
if(s[i]!='X' && dpl[i-1][j]){dpl[i][j]=1;continue;}
if(!j || i<c[j-1] || lft_[i]>=i-c[j-1]+1 || s[i-c[j-1]]=='X')continue;
// if(i==6 && j==2)cout<<"hir\n";
dpl[i][j]=((i-c[j-1]-1)>=0)?dpl[i-c[j-1]-1][j-1]:(j==1);
}
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#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...