Submission #224979

#	Time	Username	Problem	Language	Result	Execution time	Memory
224979		rama_pang	Popeala (CEOI16_popeala)	C++14	0 / 100	292 ms	6648 KiB

popeala

#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 sparse[MAXT][15];
int LOG[MAXT];

void CalcSparse(int s, int cnt) {
  for (int pos = 0; pos <= T; pos++) {
    sparse[pos][0] = dp[s - 1][pos] - Points[pos] * cnt;
  }
  for (int j = 1; j < 15; j++) {
    for (int pos = 0; pos <= T; pos++) {
      sparse[pos][j] = sparse[pos][j - 1];
      if (pos + (1 << (j - 1)) <= T) {
        sparse[pos][j] = min(sparse[pos][j], sparse[pos + (1 << (j - 1))][j - 1]);
      }
    }
  }
}

int SparseQuery(int L, int R) {
  int lg = LOG[R - L + 1];
  return min(sparse[L][lg], sparse[R - (1 << lg) + 1][lg]);
}

void Calc() {
  LOG[1] = 0;
  for (int i = 2; i < MAXT; i++) {
    LOG[i] = LOG[i / 2] + 1;
  }

  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
      CalcSparse(s, cnt);
      for (int pos = 0; pos <= T; pos++) {
        // for (int k = 0; k < pos; k++) {
        //   if (Contestants[pos][cnt].first <= k + 1 && k + 1 <= Contestants[pos][cnt].second) {
        //     int res = (Points[pos] - Points[k]) * cnt + dp[s - 1][k];
        //     dp[s][pos] = min(dp[s][pos], res);
        //   }
        // }
        if (Contestants[pos][cnt].first > Contestants[pos][cnt].second) continue;
        int res = SparseQuery(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();
  // for (int cnt = 0; cnt <= N; cnt++) {
  //   cout << "CNT " << cnt << ":\n";
  //   for (int r = 1; r <= T; r++) {
  //     cout << Contestants[r][cnt].first << " " << Contestants[r][cnt].second << " for " << r << "\n"; 
  //   }
  // }

  return 0;
}

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