oj.uz

Submission #739473

# Submission time Handle Problem Language Result Execution time Memory
739473 2023-05-10T13:45:48 Z GrindMachine Popeala (CEOI16_popeala) C++17
100 / 100
 344 ms 37520 KB 
// Om Namah Shivaya

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

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

void solve(int test_case)
{
    ll n, t, s; cin >> n >> t >> s;
    vector<ll> a(t + 5);
    rep1(i, t) cin >> a[i];

    vector<ll> p(t + 5);
    rep1(i, t) p[i] = p[i - 1] + a[i];

    ll b[n + 5][t + 5];

    rep1(i, n) {
        rep1(j, t) {
            char ch; cin >> ch;
            b[i][j] = ch - '0';
        }
    }

    ll prev_bad[n + 5][t + 5];
    memset(prev_bad, -1, sizeof prev_bad);

    rep1(i, n) {
        rep1(j, t) {
            if (!b[i][j]) {
                prev_bad[i][j] = j;
            }
            else {
                prev_bad[i][j] = prev_bad[i][j - 1];
            }
        }
    }

    vector<ll> changes[t + 5];
    rep1(i, t) {
        rep1(j, n) {
            ll pos = prev_bad[j][i];
            if (pos != -1) {
                changes[i].pb(pos - 1);
            }
        }

        sort(rall(changes[i]));
    }

    vector<ll> dp1(t + 5, inf2), dp2(t + 5, inf2);
    dp1[0] = 0;

    ll prefmn[t + 5][n + 5];

    rep1(iter, s) {
        memset(prefmn, 0x10, sizeof prefmn);
        rep(i, t + 1) {
            rep(g, n + 1) {
                ll val = dp1[i] - g * p[i];
                if (i) prefmn[i][g] = min(prefmn[i - 1][g], val);
                else prefmn[i][g] = val;
            }
        }

        rep1(i, t) {
            auto change = changes[i];
            ll g = n;

            amin(dp2[i], g * p[i] + prefmn[i - 1][g]);

            trav(pos, change) {
                g--;
                ll val = g * p[i] + prefmn[pos][g];
                amin(dp2[i], val);
            }
        }

        ll ans = dp2[t];
        cout << ans << endl;

        dp1 = dp2;
        fill(all(dp2), inf2);
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1248 KB Output is correct
2 Correct 6 ms 1108 KB Output is correct
3 Correct 7 ms 1236 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4436 KB Output is correct
2 Correct 39 ms 5904 KB Output is correct
3 Correct 53 ms 7756 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 9 ms 1248 KB Output is correct
4 Correct 6 ms 1108 KB Output is correct
5 Correct 7 ms 1236 KB Output is correct
6 Correct 30 ms 4436 KB Output is correct
7 Correct 39 ms 5904 KB Output is correct
8 Correct 53 ms 7756 KB Output is correct
9 Correct 77 ms 12200 KB Output is correct
10 Correct 145 ms 16120 KB Output is correct
11 Correct 300 ms 36472 KB Output is correct
12 Correct 315 ms 37252 KB Output is correct
13 Correct 344 ms 37420 KB Output is correct
14 Correct 317 ms 37516 KB Output is correct
15 Correct 334 ms 37520 KB Output is correct