| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 291613 | MoNsTeR_CuBe | Paint By Numbers (IOI16_paint) | C++17 | 0 ms | 0 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 <bits/stdc++.h>
#include "paint.h"
#include <cstdlib>
using namespace std;
#define int long long
int n, k;
vector< int > c;
vector< vector< int > > memo;
//ONLY works with empty cells
vector< vector< int > > tot;
vector< vector< int > > timee;
int dp(int posArray, int posC){
///////////////////////////
if(posArray >= n){
if(posC < k) return 0;
else{
return 1;
}
}
if(posC >= k) return 1;
///////////////////////////
if(memo[posArray][posC] != -1){
if(timee[posArray][posC])timee[posArray][posC]++;
return memo[posArray][posC];
}
///////////////////////////
memo[posArray][posC] = 0;
tot[posArray][posC] = 0;
if(posArray + c[posC] - 1 < n){
timee[posArray][posC]++;
memo[posArray][posC] += dp(posArray + c[posC] + 1, posC+1);
tot[posArray][posC] = memo[posArray][posC];
}
memo[posArray][posC] += dp(posArray+1, posC);
return memo[posArray][posC];
///////////////////////////
}
vector< int > ans;
vector< vector< bool > > visited;
void rec(int posArray, int posC){
if(posArray >= n){
return ;
}
if(posC >= k) return;
//if(visited[posArray][posC]) return ;
if(posArray + c[posC]-1 < n ){
//cout << "AT " << posArray << ' ' << posC << ' ' << "Add " << tot[posArray][posC] << ' ' << "From " << posArray << ' ' << "TO " << posArray+c[posC]-1 << ' ' << "TIME " << timee[posArray][posC] << endl;
ans[posArray] += tot[posArray][posC];
ans[posArray+c[posC]]-=tot[posArray][posC];
}
rec(posArray + c[posC] + 1, posC+1);
rec(posArray+1, posC);
visited[posArray][posC] = true;
}
#undef int
string solve_puzzle(string s, vector<int> C){
#define int long long
n = s.size();
k = C.size();
c.resize(k);
memo.assign(n, vector< int> (k,-1));
c = C;
tot.assign(n, vector< int> (k,-1));
timee.assign(n, vector< int> (k,0));
dp(0,0);
ans.assign(n+1,0);
visited.assign(n+1, vector< bool > (k,false));
rec(0,0);
string rep = "";
for(int i = 1; i < n; i++){
ans[i] += ans[i-1];
}
for(int i = 0; i < n; i++){
if(ans[i] == dp(0,0)) rep += 'X';
else if(ans[i]) rep += '?';
else rep += '_';
}
return rep;
}
/*
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
c.resize(k);
memo.assign(n, vector< int> (k,-1));
for(int i = 0; i < k; i++){
cin >> c[i];
}
string s = "";;
for(int i = 0; i < n; i++) s += '.';
cout << solve_puzzle(s,c) << endl;
}
*/