oj.uz

Submission #225016

# Submission time Handle Problem Language Result Execution time Memory
225016 2020-04-19T08:06:09 Z rama_pang Popeala (CEOI16_popeala) C++14
100 / 100
 1933 ms 18856 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]);
  if (res < 0) res += MOD;
  res = 1ll * res * INVKEY[L] % MOD;
  return res;
}

int CountContestant(int L, int R) {
  int res = 0;
  int ones = GetHash(N, L, R);
  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] * (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], (int) min(1ll * INF, res + 1ll * 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.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 5368 KB Output is correct
2 Correct 50 ms 5364 KB Output is correct
3 Correct 61 ms 5368 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 6392 KB Output is correct
2 Correct 272 ms 6904 KB Output is correct
3 Correct 349 ms 7544 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4864 KB Output is correct
2 Correct 13 ms 4992 KB Output is correct
3 Correct 54 ms 5368 KB Output is correct
4 Correct 50 ms 5364 KB Output is correct
5 Correct 61 ms 5368 KB Output is correct
6 Correct 191 ms 6392 KB Output is correct
7 Correct 272 ms 6904 KB Output is correct
8 Correct 349 ms 7544 KB Output is correct
9 Correct 506 ms 9208 KB Output is correct
10 Correct 750 ms 10488 KB Output is correct
11 Correct 1726 ms 17376 KB Output is correct
12 Correct 1813 ms 18808 KB Output is correct
13 Correct 1899 ms 18856 KB Output is correct
14 Correct 1933 ms 18820 KB Output is correct
15 Correct 1896 ms 18820 KB Output is correct