oj.uz

Submission #224896

# Submission time Handle Problem Language Result Execution time Memory
224896 2020-04-19T04:43:25 Z rama_pang Popeala (CEOI16_popeala) C++14
0 / 100
 1784 ms 5504 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXT = 20005;
const int MAXN = 55;

const int INF = 2e9 + 100;
const int MOD = 1e9 + 9;
const int KEY = 63;

int N, T, S;
int Points[MAXT];

int POWKEY[MAXT];
int INVKEY[MAXT];

int ResultsHash[MAXN][MAXT]; // Res[N] = 111...111

int Power(int n, int x) {
  if (x == 0) return 1;
  int res = Power(n, x / 2);
  res = 1ll * res * res % MOD;
  if (x & 1) res = 1ll * res * n % MOD;
  return res;
}

void Precompute() {
  POWKEY[0] = INVKEY[0] = 1;
  for (int i = 1; i < MAXT; i++) {
    POWKEY[i] = 1ll * POWKEY[i - 1] * KEY % MOD;
    INVKEY[i] = Power(POWKEY[i], MOD - 2);
  }
}

int GetHash(int id, int L, int R) {
  int res = (ResultsHash[id][R] - ResultsHash[id][L - 1]) % MOD;
  res = 1ll * res * INVKEY[L] % MOD;
  if (res < 0) res += MOD;
  return res;
}

int GetCost(int L, int R) {
  int cnt = 0;
  for (int i = 0; i < N; i++) {
    if (GetHash(i, L, R) == GetHash(N, L, R)) {
      cnt++;
    }
  }
  return cnt * (Points[R] - Points[L - 1]);
}

int dp[MAXN][MAXT];

void BaseCase() {
  for (int i = 0; i < MAXN; i++) {
    for (int j = 0; j < MAXT; j++) {
      dp[i][j] = INF;
    }
  }
  dp[0][0] = 0;
}

void Calc() {
  for (int i = 1; i <= T; i++) {
    for (int j = 1; j <= S; j++) {
      int &res = dp[j][i] = INF;
      for (int k = 0; k < i; k++) {
        res = min(res, dp[j - 1][k] + GetCost(k + 1, i));
      }
    }
  }
}

void DP_DnC(int s, int lo, int hi, int l, int r) {
  if (lo > hi) return;
  int mid = (lo + hi) / 2;
  int &res = dp[s][mid] = INF;
  int opt = -1;
  for (int k = l; k <= min(r, mid - 1); k++) {
    int cost = dp[s - 1][k] + GetCost(k + 1, mid);
    if (res > cost) {
      res = cost;
      opt = k;
    } 
  }
  DP_DnC(s, lo, mid - 1, l, min(opt + 30, T));
  DP_DnC(s, mid + 1, hi, max(opt - 30, 0), r);
}

int main() {
  Precompute();

  cin >> N >> T >> S;
  for (int i = 1; i <= T; i++) {
    cin >> Points[i];
    Points[i] += Points[i - 1];
  }

  for (int i = 0; i <= N; i++) {
    string Result(T, '1');
    if (i < N) cin >> Result;
    auto Hash = ResultsHash[i];
    for (int j = 1; j <= T; j++) {
      Hash[j] = (1ll * Hash[j - 1] + 1ll * POWKEY[j] * (Result[j - 1] - '0' + 1)) % MOD;
    }
  }

  BaseCase();
  for (int i = 1; i <= S; i++) {
    DP_DnC(i, 0, T, 0, T);
    cout << dp[i][T] << "\n";
  }

  return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4736 KB Output is correct
2 Incorrect 15 ms 4992 KB Output isn't correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 320 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1784 ms 5504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4736 KB Output is correct
2 Incorrect 15 ms 4992 KB Output isn't correct