Submission #988435

#TimeUsernameProblemLanguageResultExecution timeMemory
988435LOLOLOPopeala (CEOI16_popeala)C++17
0 / 100
2041 ms10884 KiB
#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; 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 = 0; 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 == val) break; 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 (cur.f != val) { nxt.pb(cur); } for (auto x : best) { nxt.pb({x.f & mask[i], 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...