oj.uz

Submission #225021

# Submission time Handle Problem Language Result Execution time Memory
225021 2020-04-19T08:11:23 Z rama_pang Popeala (CEOI16_popeala) C++14
26 / 100
 2000 ms 17652 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);
      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.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 5376 KB Output is correct
2 Correct 51 ms 5300 KB Output is correct
3 Correct 57 ms 5368 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 6384 KB Output is correct
2 Correct 286 ms 7032 KB Output is correct
3 Correct 362 ms 7544 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4864 KB Output is correct
2 Correct 15 ms 4992 KB Output is correct
3 Correct 56 ms 5376 KB Output is correct
4 Correct 51 ms 5300 KB Output is correct
5 Correct 57 ms 5368 KB Output is correct
6 Correct 196 ms 6384 KB Output is correct
7 Correct 286 ms 7032 KB Output is correct
8 Correct 362 ms 7544 KB Output is correct
9 Correct 592 ms 9216 KB Output is correct
10 Correct 803 ms 10488 KB Output is correct
11 Correct 1850 ms 17404 KB Output is correct
12 Correct 1923 ms 17580 KB Output is correct
13 Execution timed out 2044 ms 17652 KB Time limit exceeded
14 Halted 0 ms 0 KB -