제출 #1052591

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1052591		fv3	Paint By Numbers (IOI16_paint)	C++14	100 / 100	198 ms	175400 KiB

paint

#include<bits/stdc++.h>
using namespace std;

#include "paint.h"

string solve_puzzle(string s, vector<int> c)
{
    const int K = c.size();
    const int N = s.size();

    s = "_" + s + "_";
    
    // Construct prefix sum
    vector<int> preSum(N+3);
    for (int i = 0; i < N + 2; i++)
        preSum[i+1] = preSum[i] + (int)(s[i] == '_');

    vector<vector<int>> DP_r(N+2, vector<int>(K+1));
    DP_r[0][0] = 1;

    for (int i = 0; i <= N; i++)
    {
        if (s[i] == 'X') continue;
        for (int k = 0; k <= K; k++)
        {
            if (!DP_r[i][k]) continue;
            if (s[i + 1] != 'X')
                DP_r[i+1][k] = 1;

            if (k == K || i + c[k] + 1 >= N + 2) continue;
            if (preSum[i + c[k] + 1] - preSum[i + 1]) continue;
            if (s[i + c[k] + 1] == 'X') continue;
            
            DP_r[i + c[k] + 1][k + 1] = 1;
        }
    }

    
    vector<vector<int>> DP_l(N+2, vector<int>(K+1));
    DP_l[N+1][K] = 1;

    for (int i = N+1; i >= 1; i--)
    {
       if (s[i] == 'X') continue;
       for (int k = 0; k <= K; k++)
       {
           if (!DP_l[i][k]) continue;
           if (s[i - 1] != 'X')
               DP_l[i-1][k] = 1;

           if (k == 0 || i - c[k-1] - 1 < 0) continue;
           
           if (preSum[i] - preSum[i - c[k-1]]) continue;
           
           if (s[i - c[k-1] - 1] == 'X') continue;
           DP_l[i - c[k-1] - 1][k - 1] = 1;
       }
    }

    vector<int> ps(N+2);
    for (int i = 0; i < N + 2; i++)
    {
       if (s[i] == 'X') continue;
       for (int k = 0; k < K; k++)
       {
           if (i + c[k] + 1 >= N + 2 || !DP_r[i][k] || !DP_l[i + c[k] + 1][k+1]) 
               continue;
           
           if (i + c[k] + 1 >= N + 2) continue;
           if (preSum[i + c[k] + 1] - preSum[i + 1]) continue;
           if (s[i + c[k] + 1] == 'X') continue;
           ps[i+1]++;
           ps[i+c[k]+1]--;
       }
    }
   
    string res = "";
    int sum = 0;
    for (int i = 1; i <= N; i++)
    {
       sum += ps[i];
       if (s[i] == 'X')
       {
           res += 'X';
           continue;
       }
       if (sum)
       {
           bool ok = true;
           for (int k = 0; k <= K; k++)
           {
               if (!DP_r[i][k] || !DP_l[i][k]) continue;
               ok = false;
               res += '?';
               break;
           }
           if (ok) res += 'X';
       }
       else
           res += '_';
    }

    return res;
}

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