oj.uz

Submission #224974

# Submission time Handle Problem Language Result Execution time Memory
224974 2020-04-19T07:31:24 Z rama_pang Popeala (CEOI16_popeala) C++14
17 / 100
 2000 ms 6660 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]; // Prefix sum of original Points[] array
pair<int, int> Contestants[MAXT][MAXN]; // Contestant[r][cnt] = the segment i...j where contestants = cnt

namespace String { // Convert Results[] to Contestants[][]

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 CountContestant(int L, int R) {
  int res = 0;
  for (int i = 0; i < N; i++) {
    if (GetHash(i, L, R) == GetHash(N, L, R)) {
      res++;
    }
  }
  return res;
}

void Solve() {
  Precompute();
  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;
    }
  }

  for (int cnt = N; cnt >= 0; cnt--) {
    for (int r = T, l = T; r >= 1; r--) {
      l = min(l, r);
      while (l > 0 && CountContestant(l, r) > cnt) l--;
      Contestants[r][cnt].second = l;
    }
    for (int r = T, l = T; r >= 1; r--) {
      l = min(l, r);
      while (l > 0 && CountContestant(l, r) >= cnt) l--;
      Contestants[r][cnt].first = l + 1;
    }   
  }
}

}

namespace DP {

int dp[MAXN][MAXT];
int sparse[MAXT][15];
int LOG[MAXT];

void CalcSparse(int s, int cnt) {
  for (int pos = 0; pos <= T; pos++) {
    sparse[pos][0] = dp[s - 1][pos] - Points[pos] * cnt;
  }
  for (int j = 1; j < 15; j++) {
    for (int pos = 0; pos <= T; pos++) {
      sparse[pos][j] = sparse[pos][j - 1];
      if (pos + (1 << (j - 1)) <= T) {
        sparse[pos][j] = min(sparse[pos][j], sparse[pos + (1 << (j - 1))][j - 1]);
      }
    }
  }
}

int SparseQuery(int L, int R) {
  int lg = LOG[R - L + 1];
  return min(sparse[L][lg], sparse[R - (1 << lg) + 1][lg]);
}

void Calc() {
  LOG[1] = 0;
  for (int i = 2; i < MAXT; i++) {
    LOG[i] = LOG[i / 2] + 1;
  }

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

  dp[0][0] = 0;
  for (int s = 1; s <= S; s++) { // subtasks
    for (int cnt = 0; cnt <= N; cnt++) { // contestants
      CalcSparse(s, cnt);
      for (int pos = 0; pos <= T; pos++) {
        for (int k = 0; k < pos; k++) {
          if (Contestants[pos][cnt].first <= k + 1 && k + 1 <= Contestants[pos][cnt].second) {
            int res = (Points[pos] - Points[k]) * cnt + dp[s - 1][k];
            dp[s][pos] = min(dp[s][pos], res);
          }
        }
        // if (Contestants[pos][cnt].first > Contestants[pos][cnt].second) continue;
        // int res = SparseQuery(Contestants[pos][cnt].first - 1, Contestants[pos][cnt].second - 1) + Points[pos] * cnt;
        // dp[s][pos] = min(dp[s][pos], res);
      }
    }
  }
}

void Solve() {
  Calc();
  for (int s = 1; s <= S; s++) {
    cout << dp[s][T] << "\n";
  }
}

}

void Read() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

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

int main() {
  Read();
  String::Solve();
  DP::Solve();
  // for (int cnt = 0; cnt <= N; cnt++) {
  //   cout << "CNT " << cnt << ":\n";
  //   for (int r = 1; r <= T; r++) {
  //     cout << Contestants[r][cnt].first << " " << Contestants[r][cnt].second << " for " << r << "\n"; 
  //   }
  // }

  return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4864 KB Output is correct
2 Correct 17 ms 5120 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 5496 KB Output is correct
2 Correct 386 ms 5496 KB Output is correct
3 Correct 378 ms 5496 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2090 ms 6660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4864 KB Output is correct
2 Correct 17 ms 5120 KB Output is correct
3 Correct 370 ms 5496 KB Output is correct
4 Correct 386 ms 5496 KB Output is correct
5 Correct 378 ms 5496 KB Output is correct
6 Execution timed out 2090 ms 6660 KB Time limit exceeded
7 Halted 0 ms 0 KB -