Submission #291614

#	Time	Username	Problem	Language	Result	Execution time	Memory
291614		MoNsTeR_CuBe	Paint By Numbers (IOI16_paint)	C++17	10 / 100	2041 ms	512 KiB

paint

#include <bits/stdc++.h>
    #include "paint.h"
    #include <cstdlib>
    using namespace std;
     vector< int > c;
    #define int long long 
     
    int n, k;
    
     
    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;
    }
    */

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10