oj.uz

Submission #988464

# Submission time Handle Problem Language Result Execution time Memory
988464 2024-05-24T18:10:59 Z LOLOLO Popeala (CEOI16_popeala) C++17
100 / 100
 874 ms 10068 KB 
#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, id = 0;
            for (auto x : best) {
                if ((mask[i] & x.f) == x.f) {
                    val = x.f;
                    break;
                } 
                id++;
            }

            pair <ll, ll> cur = {mask[i], i};
            ll all = mask[i], all2 = mask[i - 1];
            for (int j = i; j >= 1; j--) {
                all &= mask[j];

                if (j < i)
                    all2 &= 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 (all2 == val)
                    break;
            }

            if (cur.f != val) {
                nxt.pb(cur);
            } else if (val != -1) {
                auto temp = best[id];
                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)) {
                    best[id] = cur;
                } 
            }

            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;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8484 KB Output is correct
2 Correct 19 ms 8284 KB Output is correct
3 Correct 19 ms 8284 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 8280 KB Output is correct
2 Correct 109 ms 8536 KB Output is correct
3 Correct 175 ms 8752 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 19 ms 8484 KB Output is correct
4 Correct 19 ms 8284 KB Output is correct
5 Correct 19 ms 8284 KB Output is correct
6 Correct 76 ms 8280 KB Output is correct
7 Correct 109 ms 8536 KB Output is correct
8 Correct 175 ms 8752 KB Output is correct
9 Correct 262 ms 8916 KB Output is correct
10 Correct 338 ms 9048 KB Output is correct
11 Correct 841 ms 9800 KB Output is correct
12 Correct 874 ms 9832 KB Output is correct
13 Correct 808 ms 9840 KB Output is correct
14 Correct 804 ms 10068 KB Output is correct
15 Correct 822 ms 10064 KB Output is correct