oj.uz

Submission #225026

# Submission time Handle Problem Language Result Execution time Memory
225026 2020-04-19T08:14:49 Z rama_pang Popeala (CEOI16_popeala) C++14
100 / 100
 1797 ms 17784 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 - 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);
      if (cnt < N) l = min(l, Contestants[r][cnt + 1].first);
      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);
      if (cnt < N) l = min(l, Contestants[r][cnt + 1].first);
      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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 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 52 ms 5376 KB Output is correct
2 Correct 46 ms 5368 KB Output is correct
3 Correct 49 ms 5376 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 6520 KB Output is correct
2 Correct 253 ms 6904 KB Output is correct
3 Correct 315 ms 7544 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4864 KB Output is correct
2 Correct 13 ms 4992 KB Output is correct
3 Correct 52 ms 5376 KB Output is correct
4 Correct 46 ms 5368 KB Output is correct
5 Correct 49 ms 5376 KB Output is correct
6 Correct 184 ms 6520 KB Output is correct
7 Correct 253 ms 6904 KB Output is correct
8 Correct 315 ms 7544 KB Output is correct
9 Correct 437 ms 9304 KB Output is correct
10 Correct 675 ms 10616 KB Output is correct
11 Correct 1544 ms 17528 KB Output is correct
12 Correct 1630 ms 17608 KB Output is correct
13 Correct 1738 ms 17784 KB Output is correct
14 Correct 1797 ms 17656 KB Output is correct
15 Correct 1728 ms 17784 KB Output is correct