oj.uz

답안 #225008

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
225008 2020-04-19T07:57:49 Z rama_pang 조교 (CEOI16_popeala) C++14
26 / 100
 2000 ms 17400 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXT = 20005;
const int MAXN = 55;

const int INF = 2e9 + 1e8;
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 RQ;
deque<pair<int, int>> minQ;

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

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

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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 5496 KB Output is correct
2 Correct 59 ms 5336 KB Output is correct
3 Correct 64 ms 5372 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 242 ms 6520 KB Output is correct
2 Correct 351 ms 7032 KB Output is correct
3 Correct 442 ms 7520 KB Output is correct

Subtask #4
0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 4864 KB Output is correct
2 Correct 13 ms 4992 KB Output is correct
3 Correct 72 ms 5496 KB Output is correct
4 Correct 59 ms 5336 KB Output is correct
5 Correct 64 ms 5372 KB Output is correct
6 Correct 242 ms 6520 KB Output is correct
7 Correct 351 ms 7032 KB Output is correct
8 Correct 442 ms 7520 KB Output is correct
9 Correct 654 ms 9260 KB Output is correct
10 Correct 985 ms 10396 KB Output is correct
11 Execution timed out 2090 ms 17400 KB Time limit exceeded
12 Halted 0 ms 0 KB -