Submission #88266

#	Time	Username	Problem	Language	Result	Execution time	Memory
88266		xiaowuc1	Popeala (CEOI16_popeala)	C++14	9 / 100	836 ms	33284 KiB

popeala

#include <bits/stdc++.h>

using namespace std;

const int INF = 2.1e9;

int testsums[20001];
int people;
int numTests;
int numTasks;

struct ragetree {
  int ragetreemax[4*20001];
  int ragetreelazy[4*20001];
  void pushdown(int idx) {
    if(ragetreelazy[idx] != INF) {
      ragetreelazy[2*idx] = min(ragetreelazy[2*idx], ragetreelazy[idx]);
      ragetreelazy[2*idx+1] = min(ragetreelazy[2*idx+1], ragetreelazy[idx]);
      ragetreelazy[idx] = INF;
    }
  }
  void pullup(int idx) {
    assert(ragetreelazy[idx] == INF);
    ragetreemax[idx] = max(ragetreemax[2*idx], ragetreemax[2*idx+1]);
    if(ragetreelazy[2*idx] != INF) ragetreemax[idx] = max(ragetreemax[idx], ragetreelazy[2*idx]);
    if(ragetreelazy[2*idx+1] != INF) ragetreemax[idx] = max(ragetreemax[idx], ragetreelazy[2*idx+1]);
  }
  ragetree() {
    for(int i = 0; i < 4*20001; i++) {
      ragetreemax[i] = INF;
    }
    for(int i = 0; i < 4*20001; i++) {
      ragetreelazy[i] = INF;
    }
  }
  void update(int idx, int l, int r, int lhs, int rhs, int v) {
    if(v >= ragetreelazy[idx]) return;
    if(v >= ragetreemax[idx]) return;
    if(l >= lhs && r <= rhs) {
      ragetreelazy[idx] = v;
      return;
    }
    pushdown(idx);
    int m = (l+r)/2;
    if(m >= lhs) update(2*idx, l, m, lhs, rhs, v);
    if(m+1 <= rhs) update(2*idx+1, m+1, r, lhs, rhs, v);
    pullup(idx);
  }
  void update(int l, int r, int v) {
    assert(v <= 2000000000);
    update(1, 0, 20000, l, r, v);
  }
  int query(int idx, int l, int r, int i) {
    if(l==r) return min(ragetreemax[idx], ragetreelazy[idx]);
    pushdown(idx);
    int ret;
    int m = (l+r)/2;
    if(i <= m) ret = query(2*idx, l, m, i);
    else ret = query(2*idx+1, m+1, r, i);
    pullup(idx);
    return ret;
  }
  int query(int i) {
    return query(1, 0, 20000, i);
  }
};

string l[50];
int firstWrong[50][20001];
ragetree dp[51];

int bad[50];
void compute() {
  for(int i = 0; i < numTests; i++) {
    for(int j = 0; j < people; j++) {
      bad[j] = firstWrong[j][i];
    }
    sort(bad, bad+people);
    {
      int good = people;
      for(int a = 0; a < people; a++) {
        if(bad[a] == i) {
          good--;
        }
        else break;
      }
      for(int a = 0; a < numTasks; a++) {
        int curr = dp[a].query(i);
        if(curr == INF) continue;
        dp[a+1].update(i+1, i+1, curr + good * (testsums[i+1] - testsums[i]));
      }
    }
    int numGood = people;
    int lhs = i+1;
    for(int j = 0; j < people;) {
      int k = j+1;
      while(k < people && bad[j] == bad[k]) {
        k++;
      }
      if(numGood < people) {
        for(int a = 0; a < numTasks; a++) {
          int curr = dp[a].query(i);
          if(curr == INF) continue;
          dp[a+1].update(lhs, bad[j], curr + numGood * (testsums[bad[j]] - testsums[i]));
        }
      }
      lhs = bad[j]+1;
      numGood -= k-j;
      j = k;
    }
    if(lhs <= numTests) {
      for(int a = 0; a < numTasks; a++) {
        int curr = dp[a].query(i);
        if(curr == INF) continue;
        dp[a+1].update(lhs, numTests, curr);
      }
    }
  }
}

void solve() {
  cin >> people >> numTests >> numTasks;
  for(int i = 1; i <= numTests; i++) {
    cin >> testsums[i];
    testsums[i] += testsums[i-1];
  }
  dp[0].update(0, 0, 0);
  for(int i = 0; i < people; i++) {
    cin >> l[i];
    firstWrong[i][numTests] = numTests;
    for(int j = numTests-1; j >= 0; j--) {
      if(l[i][j] == '0') {
        firstWrong[i][j] = j;
      }
      else {
        firstWrong[i][j] = firstWrong[i][j+1];
      }
    }
  }
  compute();
  for(int i = 1; i <= numTasks; i++) {
    cout << dp[i].query(numTests);
    cout << "\n";
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  solve();
}

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