Submission #225021

#	Time	Username	Problem	Language	Result	Execution time	Memory
225021		rama_pang	Popeala (CEOI16_popeala)	C++14	26 / 100	2044 ms	17652 KiB

popeala

#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]);
  if (res < 0) res += MOD;
  res = 1ll * res * INVKEY[L - 1] % MOD;
  return res;
}

int CountContestant(int L, int R) {
  int res = 0;
  int ones = ResultsHash[N][R - L + 1];
  for (int i = 0; i < N; i++) {
    if (GetHash(i, L, R) == ones) {
      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 - 1] * (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 RQ;
deque<pair<int, int>> minQ;

void Clear() {
  RQ = 0;
  minQ.clear();
}

void Insert(int s, int cnt, int pos) {
  int val = dp[s - 1][pos] - Points[pos] * cnt;
  while (!minQ.empty() && minQ.back().second > val) {
    minQ.pop_back();
  }
  minQ.emplace_back(pos, val);
}

int Query(int s, int cnt, int l, int r) {
  while (RQ <= r) Insert(s, cnt, RQ++);
  while (minQ.front().first < l) minQ.pop_front();
  return minQ.front().second;
}

void Calc() {
  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
      Clear();
      for (int pos = 1; pos <= T; pos++) {
        if (Contestants[pos][cnt].first > Contestants[pos][cnt].second) continue;
        int res = Query(s, cnt, Contestants[pos][cnt].first - 1, Contestants[pos][cnt].second - 1);
        dp[s][pos] = min(dp[s][pos], res + Points[pos] * cnt);
      }
    }
  }
}

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();
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 0 / 74