제출 #646550

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
646550		Ronin13	Paint By Numbers (IOI16_paint)	C++14	0 / 100	1 ms	340 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
#include <cstdlib>
using namespace std;

ll dp[200005][105];
ll DP[200005][105];

std::string solve_puzzle(std::string s, std::vector<int> c) {
    int n = s.size(), k = c.size();
    char ch[n + 2], a[k + 1], pref[n + 1];
    ch[0] = ch[n + 1] = '.';
    for(int i = 1; i<= n; i++){
        ch[i] = s[i - 1];
    }
    for(int i = 1; i <= k; i++) a[i] = c[i - 1];
    pref[0] = 0;
    for(int i = 1; i <= n; i++){
        pref[i] = pref[i - 1];
        if(ch[i] == '_') pref[i]++;
    }
    dp[0][0] = 1;
    DP[n + 1][k + 1] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= k; j++){
            if(ch[i] != 'X') dp[i][j] += dp[i - 1][j];
            if(j == 0) continue;
            if(i < a[j]) continue;
            int v = pref[i] - pref[i - a[j]];
            if(v == 0 && ch[i - a[j]] != 'X'){
                dp[i][j] += dp[max(0, i - a[j] - 1)][j - 1];
            }

        }
    }
    for(int i = n; i >= 1; i--){
        for(int j = 1; j <= k + 1; j++){
            if(ch[i] != 'X') DP[i][j] += DP[i + 1][j];
            if(j == k + 1) continue;
            if(i + a[j] - 1 > n) continue;
            int v = pref[i + a[j] - 1] - pref[i - 1];
            if(v == 0 && ch[i + a[j]] != 'X'){
                DP[i][j] += DP[min(n + 1, i + a[j] + 1)][j + 1];
            }
        }
    }
    ll sum[n + 2];
    fill(sum, sum + n + 2, 0);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= k; j++){
            if(i < a[j]) continue;
            if(ch[i - a[j]] != 'X' && ch[i + 1] != 'X'){
                if(pref[i] - pref[i - a[j]]) continue;
                ll val = dp[max(i - a[j] - 1, 0)][j - 1] * DP[min(i + 2, n + 1)][j + 1];
                int l = i - a[j] + 1, r = i + 1;
                sum[l] += val;
                sum[r] -= val;
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= k; j++){
            cout << dp[i][j] << ' ';
        }
        cout << "\n";
    }
    string ans = "";
    ll cursum = sum[0];
    for(int i = 1; i <= n; i++){
        cursum += sum[i];
        if(cursum == dp[n][k]) ans += 'X';
        if(cursum == 0) ans += '_';
        if(cursum  && cursum != dp[n][k]) ans += '?';
    }
    return ans;
}

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