oj.uz

Submission #812249

# Submission time Handle Problem Language Result Execution time Memory
812249 2023-08-07T08:00:34 Z NeroZein Popeala (CEOI16_popeala) C++17
17 / 100
 2000 ms 6828 KB 
#include "bits/stdc++.h"
#define int long long
 
using namespace std;
  
const int INF = 2e9;
const int T = 2e4 + 4;
 
int seg[T * 2]; 
int lazy[T * 2];
 
void build (int nd, int l, int r, vector<int>& v) {
  if (l == r) {
    if (l) {
      seg[nd] = v[l - 1];      
    } else {
      seg[nd] = INF; 
    }
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  build(nd + 1, l, mid, v);
  build(rs, mid + 1, r, v); 
  seg[nd] = min(seg[nd + 1], seg[rs]); 
}
 
void push (int nd, int l, int r) {
  if (!lazy[nd]) {
    return;
  }
  seg[nd] += lazy[nd];
  if (l != r) {
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    lazy[nd + 1] += lazy[nd];
    lazy[rs] += lazy[nd];
  }
  lazy[nd] = 0; 
}
 
void upd (int nd, int l, int r, int s, int e, int v) {
  push(nd, l, r);
  if (l >= s && r <= e) {//problem here
    lazy[nd] = v;
    push(nd, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (mid >= e) {
    upd(nd + 1, l, mid, s, e, v);
    push(rs, mid + 1, r);
  } else {
    if (mid < s) {
      upd(rs, mid + 1, r, s, e, v);
      push(nd + 1, l, mid);
    } else {
      upd(rs, mid + 1, r, s, e, v);
      upd(nd + 1, l, mid, s, e, v);      
    }
  }
  seg[nd] = min(seg[nd + 1], seg[rs]); 
}
 
int qry (int nd, int l, int r, int s, int e) {
  push(nd, l, r);
  if (l >= s && r <= e) {
    return seg[nd];
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (mid >= e) {
    return qry(nd + 1, l, mid, s, e);
  } else {
    if (mid < s) {
      return qry(rs, mid + 1, r, s, e);
    } else {
      return min(qry(nd + 1, l, mid, s, e), qry(rs, mid + 1, r, s, e)); 
    }
  }
}
 
void debug (int nd, int l, int r) {
  push(nd, l, r);
  if (l == r) {
    cout << l << ' ' << r << ' ' << seg[nd] << '\n';
    return;    
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  debug(nd + 1, l, mid);
  debug(rs, mid + 1, r); 
  cout << l << ' ' << r << ' ' << seg[nd] << '\n';
}
 
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, t, s;
  cin >> n >> t >> s;
  vector<int> pts(t + 1);
  for (int i = 1; i <= t; ++i) {
    cin >> pts[i];
  }
  vector<string> b(n);
  for (int i = 0; i < n; ++i) {
    cin >> b[i];
    b[i] = '#' + b[i];
  }
  vector<vector<pair<int, int>>> last_till(t + 1); 
  vector<vector<int>> last(n, vector<int> (t + 1));
  for (int i = 1; i <= t; ++i) {
    vector<int> tmp;
    for (int j = 0; j < n; ++j) {
      if (b[j][i] == '0') {
        last[j][i] = i;
      } else {
        last[j][i] = last[j][i - 1];
      }
      tmp.push_back(last[j][i]);
    }
    sort(tmp.begin(), tmp.end(), greater<int>()); 
    for (int j = 0; j < (int) tmp.size(); ++j) {
      int k = j; 
      while (k + 1 < (int) tmp.size() && tmp[k + 1] == tmp[j]) {
        k++; 
      }
      last_till[i].emplace_back(tmp[j], k - j + 1);
      j = k; 
    }
  }
  vector<int> dp(t + 1, INF); 
  dp[0] = 0; 
  upd(0, 0, t, 0, t, INF);
  upd(0, 0, t, 0, 1, -INF);
  for (int k = 1; k <= s; ++k) {
    vector<int> ndp(t + 1, INF);
    for (int i = k; i <= t; ++i) {
      int r = i;
      int working = n; 
      for (auto [l, f] : last_till[i]) {
        if (l + 1 <= r) {
          upd(0, 0, t, l + 1, r, pts[i] * working);         
        }
        working -= f; 
        r = l; 
      }
      for (int j = 0; j < n; ++j) {
        if (b[j][i] == '0') {
          int sum = 0; 
          for (int l = i - 1; l > last[j][i - 1]; --l) {//this is already fast (t * n * s)
            sum += pts[l]; 
            upd(0, 0, t, l, l, -sum); 
          }
        }
      }
      ndp[i] = qry(0, 0, t, 1, i); 
    }
    swap(dp, ndp); 
    build(0, 0, t, dp); 
    fill(lazy, lazy + T * 2, 0); 
    cout << dp[t] << '\n';
  }
}

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 1264 KB Output is correct
2 Correct 148 ms 1240 KB Output is correct
3 Correct 155 ms 1364 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 857 ms 3772 KB Output is correct
2 Correct 1307 ms 5240 KB Output is correct
3 Execution timed out 2005 ms 6828 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 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 152 ms 1264 KB Output is correct
4 Correct 148 ms 1240 KB Output is correct
5 Correct 155 ms 1364 KB Output is correct
6 Correct 857 ms 3772 KB Output is correct
7 Correct 1307 ms 5240 KB Output is correct
8 Execution timed out 2005 ms 6828 KB Time limit exceeded
9 Halted 0 ms 0 KB -