Submission #1188443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188443		JelalTkm	Paint By Numbers (IOI16_paint)	C++17	7 / 100	0 ms	328 KiB

paint

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

// #define int long long int

// const int N = 2e5 + 10;
// const int md = 1e9 + 7;
// const int INF = 1e18;

string solve_puzzle(string s, vector<int> c){
  int n = (int) s.size();
  s = "#" + s;
  vector<int> pref(n + 1);
  for (int i = 1; i <= n; i++)
    pref[i] = pref[i - 1] + (s[i] == '_');
  int k = (int) c.size();
  c.insert(c.begin(), 0);

  vector<vector<int>> cn(k + 1, vector<int> (n + 1)), cn1(k + 1, vector<int> (n + 2));
  vector<vector<int>> cnt(k + 1, vector<int> (n + 1)), cnt1(k + 1, vector<int> (n + 1));

  int ans = 0;
  for (int i = 1; i <= n; i++)
    cn[0][i] = 1, cn1[0][i] = 1;
  for (int j = 1; j <= k; j++) {
    for (int i = 1; i <= n; i++) {
      if ((i - c[j]) - 1 < 0 && (i - c[j] != 0)) continue;
      if (pref[i] - pref[i - c[j]] != 0) continue;
      if (j == 1) {
        if (i - c[j] >= 0) cn[j][i] = 1;
        cnt[j][i] = max(cnt[j][i], cn[j][i]);
      } else {
        for (int nw = (i - c[j] - 1); nw >= 1; nw--) {
          cn[j][i] += cn[j - 1][nw];
        }
        cnt[j][i] = max(cnt[j][i], cn[j][i]);
      }

      if (j == k) {
        ans += cn[j][i];
      }
    }
  }

  // cout << ans << '\n';
  for (int j = k; j >= 1; j--) {
    for (int i = n; i >= 1; i--) {
      if ((i - c[j]) - 1 < 0 && (i - c[j] != 0)) continue;
      if (pref[i] - pref[i - c[j]] != 0) continue;
      if (j == k) {
        if (i - c[j] >= 0) cn1[j][i] = 1;
        cnt1[j][i] = max(cnt1[j][i], cn1[j][i]);
      } else {
        for (int nw = (i + c[j + 1] + 1); nw <= n; nw++) {
          cn1[j][i] += cn1[j + 1][nw];
        }
        cnt1[j][i] = max(cnt1[j][i], cn1[j][i]);
      }
    }
  }

  for (int j = 1; j <= k; j++)
    for (int i = 1; i <= n; i++)
      if (cnt[j][i] != 0 && cnt1[j][i] != 0) {
        cnt[j][i] = max(cnt[j][i], cnt1[j][i]);
      } else cnt[j][i] = 0;

  vector<int> o(n + 2);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= k; j++)
      if (cnt[j][i] != 0) {
        o[i - c[j] + 1] += cnt[j][i];
        o[i + 1] -= cnt[j][i];
      }

  string ans1 = "";
  for (int i = 1; i <= n; i++) {
    o[i] += o[i - 1];
    if (o[i] > 0) ans1 += (o[i] == ans ? "X" : "?");
    else ans1 += "_";
  }

  return ans1;
}

// int32_t main(int32_t argc, char *argv[]) {
//   ios::sync_with_stdio(false);
//   cin.tie(nullptr);

//   int T = 1;
//   // cin >> T;
//   while (T--) {
//     string s;
//     cin >> s;
//     int k;
//     cin >> k;
//     vector<int> c(k);
//     for (int i = 0; i < k; i++)
//       cin >> c[i];

//     cout << solve_puzzle(s, c) << '\n';
//   }

//   return 0;
// }

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 7 / 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