# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
69137 | Sa1378 | Paint By Numbers (IOI16_paint) | C++17 | 2078 ms | 37764 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |