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 = 2e4 + 10;
int mod = 1e9 + 7;
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, int>> best;
for (int i = 1; i <= t; i++) {
vector <pair <ll, int>> nxt;
ll all = mask[i];
pair <ll, ll> cur;
cur = {all, i};
for (auto x : best) {
pair <ll, ll> temp = x;
temp.f &= all;
if (temp.f != cur.f) {
nxt.pb(cur);
cur = temp;
} else {
if (dp[k - 1][cur.s - 1] + (p[i] - p[cur.s - 1]) * cntbit(cur.f) > dp[k - 1][temp.s - 1] + (p[i] - p[temp.s - 1]) * cntbit(temp.f)) {
cur = temp;
}
}
minimize(dp[k][i], dp[k - 1][cur.s - 1] + (p[i] - p[cur.s - 1]) * cntbit(cur.f));
}
nxt.pb(cur);
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... |