oj.uz

Submission #680700

# Submission time Handle Problem Language Result Execution time Memory
680700 2023-01-11T14:28:37 Z peijar Popeala (CEOI16_popeala) C++17
100 / 100
 981 ms 47144 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
  out << "[";
  for (int i = 0; i < (int)vec.size(); ++i) {
    out << vec[i];
    if (i + 1 < (int)vec.size())
      out << ", ";
  }
  return out << "]";
}
} // namespace std

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << H;
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int INF = 1e18;
struct SegTree {
  vector<int> seg;
  int from;

  SegTree(int sz) {
    from = 1;
    while (from < sz)
      from *= 2;
    seg.assign(2 * from, INF);
  }

  void upd(int i, int x) {
    i += from;
    seg[i] = x;
    while (i > 1) {
      i /= 2;
      seg[i] = min(seg[2 * i], seg[2 * i + 1]);
    }
  }

  int query(int deb, int fin) {
    deb += from, fin += from;

    int ret = INF;
    while (deb < fin) {
      if (deb % 2)
        ret = min(ret, seg[deb++]);
      if (fin % 2)
        ret = min(ret, seg[--fin]);
      deb /= 2;
      fin /= 2;
    }
    return ret;
  }
};

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbEleves, nbTests, maxSubtasks;
  cin >> nbEleves >> nbTests >> maxSubtasks;
  vector<int> points(nbTests), prefSum(nbTests + 1);

  for (int i = 0; i < nbTests; ++i) {
    cin >> points[i];
    prefSum[i + 1] = prefSum[i] + points[i];
  }

  vector<vector<int>> prvWA(nbEleves, vector<int>(nbTests + 1, -1));
  for (int i = 0; i < nbEleves; ++i)
    for (int j = 0; j < nbTests; ++j) {
      char c;
      cin >> c;
      prvWA[i][j + 1] = prvWA[i][j];
      if (c == '0')
        prvWA[i][j + 1] = j;
    }

  vector<SegTree> segtrees(nbEleves + 1, nbTests + 1);
  for (int i = 0; i <= nbEleves; ++i)
    segtrees[i].upd(0, 0);
  vector<vector<int>> posChange(nbTests + 1);
  for (int testRestant = 1; testRestant <= nbTests; ++testRestant) {
    for (int iEleve = 0; iEleve < nbEleves; ++iEleve)
      if (prvWA[iEleve][testRestant] != -1)
        posChange[testRestant].push_back(prvWA[iEleve][testRestant]);
    sort(posChange[testRestant].rbegin(), posChange[testRestant].rend());
  }

  for (int nbTaches = 1; nbTaches <= maxSubtasks; ++nbTaches) {
    vector<int> dp(nbTests + 1, INF);

    for (int testRestant = 1; testRestant <= nbTests; ++testRestant) {
      int prv = testRestant - 1;
      for (int nbMauvais = 0; nbMauvais <= (int)posChange[testRestant].size();
           ++nbMauvais) {
        int nxt = nbMauvais == (int)posChange[testRestant].size()
                      ? -1
                      : posChange[testRestant][nbMauvais]; // can't take nxt
        int nbBons = nbEleves - nbMauvais;
        dp[testRestant] =
            min(dp[testRestant], nbBons * prefSum[testRestant] +
                                     segtrees[nbBons].query(nxt + 1, prv + 1));
        prv = nxt;
      }
    }
    for (int nbBons = 0; nbBons <= nbEleves; ++nbBons) {
      int from = segtrees[nbBons].from;
      for (int i = 0; i <= nbTests; ++i) {
        segtrees[nbBons].seg[from + i] = dp[i] - nbBons * prefSum[i];
      }
      for (int i = from - 1; i >= 1; --i)
        segtrees[nbBons].seg[i] =
            min(segtrees[nbBons].seg[2 * i], segtrees[nbBons].seg[2 * i + 1]);
    }
    dbg(dp);
    cout << dp.back() << '\n';
  }
}

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1108 KB Output is correct
2 Correct 19 ms 1164 KB Output is correct
3 Correct 15 ms 1108 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 5504 KB Output is correct
2 Correct 140 ms 6440 KB Output is correct
3 Correct 190 ms 7368 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 15 ms 1108 KB Output is correct
4 Correct 19 ms 1164 KB Output is correct
5 Correct 15 ms 1108 KB Output is correct
6 Correct 73 ms 5504 KB Output is correct
7 Correct 140 ms 6440 KB Output is correct
8 Correct 190 ms 7368 KB Output is correct
9 Correct 258 ms 13160 KB Output is correct
10 Correct 394 ms 21700 KB Output is correct
11 Correct 907 ms 44296 KB Output is correct
12 Correct 957 ms 46796 KB Output is correct
13 Correct 981 ms 46876 KB Output is correct
14 Correct 978 ms 47144 KB Output is correct
15 Correct 933 ms 47044 KB Output is correct