oj.uz

Submission #252186

# Submission time Handle Problem Language Result Execution time Memory
252186 2020-07-24T15:32:40 Z Haunted_Cpp Palindromic Partitions (CEOI17_palindromic) C++17
60 / 100
 793 ms 99136 KB 
/**
 * author: Haunted_Cpp
**/

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

template<typename T> ostream &operator << (ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream &operator << (ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream &operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
 
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
 
#ifdef LOCAL
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
#define debug(...) 47
#endif

const int N = 1e4 + 50;

int dp[N], n;
string w;

vector<int> calc_z(string cur) {
  const int T = (int) cur.size();
  vector<int> z(T);
  z[0] = 0;
  int L = 0, R = 0;
  for (int i = 1; i < T; i++) {
    z[i] = (i <= R ? min(z[i - L], R - i + 1) : 0);
    while(i + z[i] < T && cur[i + z[i]] == cur[z[i]]) ++z[i]; 
    if (i + z[i] > R) {
      L = i;
      R = i + z[i] - 1;
    } 
  }
  return z;
}

int solve(int l) {
  int r = n - l - 1;
  if (l > r) return 0;
  int &res = dp[l];
  if (~res) return res;
  res = 1;
  int size = r - l + 1;
  vector<int> z = calc_z(w.substr(l, size));
  for (int i = 0; i < (int) z.size(); i++) {
    if (i + z[i] >= size) {
      res = max(res, 2 + solve(l + z[i]));
    }
  }
  return res;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while(t--) {
    cin >> w;
    n = (int) w.size();
    for (int i = 0; i < n; i++) dp[i] = -1;
    cout << solve(0) << '\n';
  }
  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 793 ms 99136 KB Output is correct
11 Correct 96 ms 776 KB Output is correct
12 Correct 18 ms 512 KB Output is correct
13 Correct 445 ms 800 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 793 ms 99136 KB Output is correct
11 Correct 96 ms 776 KB Output is correct
12 Correct 18 ms 512 KB Output is correct
13 Correct 445 ms 800 KB Output is correct
14 Runtime error 5 ms 3868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -