oj.uz

Submission #252187

# Submission time Handle Problem Language Result Execution time Memory
252187 2020-07-24T15:33:03 Z Haunted_Cpp Palindromic Partitions (CEOI17_palindromic) C++17
60 / 100
 10000 ms 98948 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 = 1e6 + 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 1 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 1 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 0 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 1 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 0 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 789 ms 98948 KB Output is correct
11 Correct 90 ms 696 KB Output is correct
12 Correct 15 ms 640 KB Output is correct
13 Correct 444 ms 784 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 789 ms 98948 KB Output is correct
11 Correct 90 ms 696 KB Output is correct
12 Correct 15 ms 640 KB Output is correct
13 Correct 444 ms 784 KB Output is correct
14 Execution timed out 10053 ms 10268 KB Time limit exceeded
15 Halted 0 ms 0 KB -