This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (int)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) (ll)__builtin_popcountll(x)
#define len(x) (int)(x.length())
const int N = 20000 + 10;
ll mask[N], p[N];
ll dp[51][N];
bool minimize(ll &a, ll b) {
if (a > b) {
a = b;
return 1;
}
return 0;
}
void solve() {
mem(dp, 0x3f);
int n, t, s;
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++) {
char c;
cin >> c;
if (c == '1') {
mask[j] |= ((ll)1 << (i - 1));
}
}
}
dp[0][0] = 0;
for (int k = 1; k <= s; k++) {
vector <pair <ll, ll>> best;
for (int i = 1; i <= t; i++) {
vector <pair <ll, ll>> nxt;
ll val = -1;
for (auto x : best) {
if ((mask[i] & x.f) == x.f) {
val = x.f;
break;
}
}
pair <ll, ll> cur = {mask[i], i};
ll all = mask[i];
for (int j = i; j >= 1; j--) {
all &= mask[j];
if (all != cur.f) {
nxt.pb(cur);
cur = {all, j};
} else {
if (dp[k - 1][cur.s - 1] + (p[i] - p[cur.s - 1]) * cntbit(cur.f) > dp[k - 1][j - 1] + (p[i] - p[j - 1]) * cntbit(all)) {
cur = {all, j};
}
}
if (all == val)
break;
}
if (cur.f != val) {
nxt.pb(cur);
} else {
if (mask[i] == val) {
auto cur = best[0];
if (dp[k - 1][i - 1] + (p[i] - p[i - 1]) * cntbit(val) < dp[k - 1][cur.s - 1] + (p[i] - p[cur.s - 1]) * cntbit(cur.f)) {
best[0] = {mask[i], i};
}
}
}
for (auto x : best) {
if (x.f <= val)
nxt.pb({x.f, x.s});
}
best = nxt;
for (auto cur : best)
minimize(dp[k][i], dp[k - 1][cur.s - 1] + (p[i] - p[cur.s - 1]) * cntbit(cur.f));
}
}
for (int i = 1; i <= s; i++) {
cout << dp[i][t] << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
//cin >> t;
while (t--) {
solve();
//cout << solve() << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |