oj.uz

Submission #608867

# Submission time Handle Problem Language Result Execution time Memory
608867 2022-07-27T10:57:50 Z BERNARB01 Popeala (CEOI16_popeala) C++17
17 / 100
 2000 ms 1620 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef B01
#include "../debb.h"
#else
#define deb(...)
#endif

class segtree {
  public:
  struct node {
    long long mn = 0;
    long long add = 0;

    void apply(int l, int r, long long v) {
      add += v;
      mn += v;
    }
  };

  node unite(const node& a, const node& b) const {
    node res;
    res.mn = min(a.mn, b.mn);
    return res;
  }

  inline void push(int x, int l, int r) {
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    if (tr[x].add != 0) {
      tr[x + 1].apply(l, y, tr[x].add);
      tr[z].apply(y + 1, r, tr[x].add);
      tr[x].add = 0;
    }
  }

  inline void pull(int x, int z) {
    tr[x] = unite(tr[x + 1], tr[z]);
  }

  int n;
  vector<node> tr;

  void build(int x, int l, int r) {
    if (l == r) {
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }

  template <typename M>
  void build(int x, int l, int r, const vector<M> &v) {
    if (l == r) {
      tr[x].apply(l, r, v[l]);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y, v);
    build(z, y + 1, r, v);
    pull(x, z);
  }

  node get(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return tr[x];
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    node res{};
    if (rr <= y) {
      res = get(x + 1, l, y, ll, rr);
    } else {
      if (ll > y) {
        res = get(z, y + 1, r, ll, rr);
      } else {
        res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
      }
    }
    pull(x, z);
    return res;
  }

  template <typename... M>
  void imodify(int x, int l, int r, int ll, int rr, const M&... v) {
    if (ll <= l && r <= rr) {
      tr[x].apply(l, r, v...);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    if (ll <= y) {
      imodify(x + 1, l, y, ll, rr, v...);
    }
    if (rr > y) {
      imodify(z, y + 1, r, ll, rr, v...);
    }
    pull(x, z);
  }

  template <typename M>
  segtree(const vector<M> &v) {
    n = v.size();
    assert(n > 0);
    tr.resize(2 * n - 1);
    build(0, 0, n - 1, v);
  }

  node get(int ll, int rr) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return get(0, 0, n - 1, ll, rr);
  }

  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(0, 0, n - 1, p, p);
  }

  template <typename... M>
  void modify(int ll, int rr, const M&... v) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    imodify(0, 0, n - 1, ll, rr, v...);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, tt, s;
  cin >> n >> tt >> s;
  vector<int> rsc(tt);
  for (int i = 0; i < tt; i++) {
    cin >> rsc[i];
  }
  vector<vector<int>> pts(tt, vector<int>(n));
  for (int i = 0; i < n; i++) {
    string t;
    cin >> t;
    for (int j = 0; j < tt; j++) {
      pts[j][i] = (t[j] - '0') * rsc[j];
    }
  }
  vector<long long> dp(tt);
  vector<int> ss(n);
  int zz = 0;
  for (int i = 0; i < tt; i++) {
    for (int j = 0; j < n; j++) {
      if (pts[i][j] == 0) {
        if (ss[j] != -1) {
          zz -= ss[j];
          ss[j] = -1;
        }
      } else {
        if (ss[j] != -1) {
          ss[j] += pts[i][j];
          zz += pts[i][j];
        }
      }
    }
    dp[i] = zz;
  }
  cout << dp.back() << '\n';
  for (int k = 1; k < s; k++) {
    for (int i = tt - 2; i >= 0; i--) {
      dp[i + 1] = dp[i];
    }
    dp[0] = 0;
    const long long inf = (long long) 4e9L;
    for (int i = 0; i < k; i++) {
      dp[i] = inf;
    }
    segtree st(dp);
    vector<int> last0(n, -1);
    vector<long long> pd(tt, inf);
    for (int i = k; i < tt; i++) {
      for (int j = 0; j < n; j++) {
        if (pts[i][j]) {
          st.modify(last0[j] + 1, i, pts[i][j]);
        } else {
          int beg = last0[j], end = i - 1;
          last0[j] = i;
          int z = 0;
          while (end > beg) {
            z += pts[end][j];
            st.modify(end, end, -z);
            --end;
          }
        }
      }
      pd[i] = st.get(0, i).mn;
    }
    swap(dp, pd);
    cout << dp.back() << '\n';
  }
  return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 320 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 472 KB Output is correct
2 Correct 223 ms 468 KB Output is correct
3 Correct 237 ms 468 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1241 ms 1028 KB Output is correct
2 Correct 1917 ms 1300 KB Output is correct
3 Execution timed out 2063 ms 1620 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 320 KB Output is correct
3 Correct 227 ms 472 KB Output is correct
4 Correct 223 ms 468 KB Output is correct
5 Correct 237 ms 468 KB Output is correct
6 Correct 1241 ms 1028 KB Output is correct
7 Correct 1917 ms 1300 KB Output is correct
8 Execution timed out 2063 ms 1620 KB Time limit exceeded
9 Halted 0 ms 0 KB -