#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
int N, T, S, P[20005], lim[55], dp[20005], ndp[20005];
bool R[55][20005];
char C;
vector<ii> vec;
vector<iiii> qq;
map<int, int> mpp;
void qry(int l, int r, int x, int idx) {
qq.eb(x, l, r, idx);
}
struct MonotonicLineContainer { // increasing inserts and queries only
vector<ii> D; // use an array as a last resort
int sf = 0;
long double is(int a, int b, int c, int d) { // replace with cross-multiplication if no overflow
return (long double)(d - b) / (a - c);
}
void add(int m, int c) { // insert y = mx + c
if (!D.empty() && D.back().first == m && D.back().second > c) return;
while (D.size() - sf > 1) {
int s = D.size();
if (
(D[s - 1].first == m && c > D[s - 1].second) ||
(is(D[s - 1].first, D[s - 1].second, m, c) <= is(D[s - 2].first, D[s - 2].second, m, c))
)
D.pop_back();
else break;
}
D.emplace_back(m, c);
}
int query(int x) { // max query
while (D.size() - sf > 1) {
if (D[sf].first * x + D[sf].second < D[sf + 1].first * x + D[sf + 1].second) sf++;
else break;
}
return D[sf].first * x + D[sf].second;
}
};
MonotonicLineContainer hull;
void dnc(int l, int r, vector<iiii> &q) {
if (l > r || q.empty()) return;
vector<iiii> lq, rq, to_ans;
int m = (l + r) >> 1;
for (auto [x, l1, r1, idx] : q) {
if (l1 <= m && m < r1) lq.eb(x, l1, m, idx), rq.eb(x, m + 1, r1, idx);
else if (l1 == l && r1 == r) to_ans.eb(x, l1, m, idx);
else if (r1 <= m) lq.eb(x, l1, r1, idx);
else rq.eb(x, l1, r1, idx);
}
hull.D.clear();
hull.sf = 0;
for (int i = l; i <= r; i++)
hull.add(P[i - 1], -dp[i - 1]);
for (auto [x, l1, r1, idx] : to_ans)
ndp[idx] = min(ndp[idx], -hull.query(x) + x * P[idx]);
dnc(l, m, lq);
dnc(m + 1, r, rq);
}
void go() {
for (int i = 1; i <= T; i++) {
mpp.clear();
vec.clear();
for (int k = 1; k <= N; k++) {
if (R[k][i]) lim[k] = (lim[k] ? lim[k] : i);
else lim[k] = 0;
if (lim[k]) mpp[lim[k]]++;
}
for (auto k : mpp) vec.eb(k.first, k.second);
ndp[i] = LLONG_MAX;
if (vec.empty()) {
qry(1, i, 0, i);
continue;
}
for (int k = 0, cum = 0; k < vec.size(); k++) {
cum += vec[k].second;
//cout << "! " << vec[k].first << ' ' << (k + 1 < vec.size() ? vec[k + 1].first - 1 : i) << ' ' << cum << '\n';
qry(vec[k].first, (k + 1 < vec.size() ? vec[k + 1].first - 1 : i), cum, i);
}
if (vec[0].first != 1) {
//cout << 1 << ' ' << vec[0].first - 1 << " 0\n";
qry(1, vec[0].first - 1, 0, i);
}
}
sort(qq.begin(), qq.end());
dnc(1, T, qq);
}
main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> T >> S;
for (int i = 1; i <= T; i++) cin >> P[i], P[i] += P[i - 1];
for (int i = 1; i <= N; i++)
for (int j = 1; j <= T; j++) {
cin >> C;
R[i][j] = (C == '1');
}
dp[0] = 0;
for (int i = 1; i <= T; i++) dp[i] = 1e16;
for (int i = 1; i <= S; i++) {
for (int j = 1; j <= N; j++) lim[j] = 0;
qq.clear();
go();
swap(dp, ndp);
cout << dp[T] << '\n';
dp[0] = 1e16;
}
}
Compilation message
popeala.cpp: In function 'void go()':
popeala.cpp:105:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for (int k = 0, cum = 0; k < vec.size(); k++) {
| ~~^~~~~~~~~~~~
popeala.cpp:108:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | qry(vec[k].first, (k + 1 < vec.size() ? vec[k + 1].first - 1 : i), cum, i);
| ~~~~~~^~~~~~~~~~~~
popeala.cpp: At global scope:
popeala.cpp:119:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
119 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
3 ms |
852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
454 ms |
3216 KB |
Output is correct |
| 2 |
Correct |
397 ms |
3320 KB |
Output is correct |
| 3 |
Correct |
435 ms |
3216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2082 ms |
11684 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
3 ms |
852 KB |
Output is correct |
| 3 |
Correct |
454 ms |
3216 KB |
Output is correct |
| 4 |
Correct |
397 ms |
3320 KB |
Output is correct |
| 5 |
Correct |
435 ms |
3216 KB |
Output is correct |
| 6 |
Execution timed out |
2082 ms |
11684 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
