oj.uz

Submission #860340

# Submission time Handle Problem Language Result Execution time Memory
860340 2023-10-12T15:56:39 Z wii Popeala (CEOI16_popeala) C++17
100 / 100
 1664 ms 44352 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

typedef double db;
typedef long long ll;
typedef long double ld;

#define int ll
typedef pair<int, int> pii;

#define X first
#define Y second
#define gcd __gcd
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define bit(i, mask) ((mask) >> (i) & 1)
#define reset(x, val) memset(x, val, sizeof(x))
#define foru(i,a,b) for(int i = (a); i <= (b); ++i)
#define ford(i,a,b) for(int i = (a); i >= (b); --i)
#define FastIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

template<typename T> bool maximize(T &res, const T &val) { if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) { if (val < res) { res = val; return true; } return false; }

const ll Linf = 0x3f3f3f3f3f3f3f3f;
const int Inf = 0x3f3f3f3f;
const ll Mod = 1e9 + 7;
const ll Mod2 = ll(1e9) + 9;
const int Lim = 1e6 + 5;
const int inv6 = 166666668;

// #define Sieve
#ifdef Sieve
    vector<int> pr;
    vector<int> lpf;
    void Linear_sieve(int n = Lim) {
        pr.assign(1, 2);
        lpf.assign(n + 1, 2);

        for (int x = 3; x <= n; x += 2) {
            if (lpf[x] == 2) pr.push_back(lpf[x] = x);
            for (int i = 1; i < pr.size() && pr[i] <= lpf[x] && pr[i] * x <= n; ++i)
                lpf[pr[i] * x] = pr[i];
        }
    }
#endif

// #define Ckn_calc
#ifdef Ckn_calc
    const int LIM = 1e6 + 16;

    int fact[LIM + 10]; /// factorial:         fact[n] = n!
    int invs[LIM + 10]; /// inverse modular:   invs[n] = n^(-1)
    int tcaf[LIM + 10]; /// inverse factorial: tcaf[n] = (n!)^(-1)
    void precal_nck(int n = LIM)
    {
        fact[0] = fact[1] = 1;
        invs[0] = invs[1] = 1;
        tcaf[0] = tcaf[1] = 1;
        for (int i = 2; i <= n; ++i)
        {
            fact[i] = (1LL * fact[i - 1] * i) % Mod;
            invs[i] = Mod - 1LL * (Mod / i) * invs[Mod % i] % Mod;
            tcaf[i] = (1LL * tcaf[i - 1] * invs[i]) % Mod;
        }
    }

    ll C(int n, int k) {
        if (n < k || k < 0) return 0;

        ll res = fact[n];
        res *= tcaf[k], res %= Mod;
        res *= tcaf[n - k], res %= Mod;
        return res;
    }

    ll P(int n, int k) {
        ll res = fact[n];
        res *= tcaf[n - k], res %= Mod;
        return res;
    }
#endif

/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

const int base = 3;
const int N = 2e4 + 5;
const int K = 50 + 5;
const int dx[] = {+1, -1, 0, 0};
const int dy[] = {0, 0, +1, -1};
const int block_size = sqrt(2e9) + 2;

int n, t, k;
int a[N], last[N][K], dp[N][K], f[N][K];
int opt[N], cnt[N];

int full_row(int l, int r) {
    int ans = 0;
    foru(i, 1, n)
        ans += (f[r][i] - f[l - 1][i] == r - l + 1);
    return ans;
}

int seg[K][N * 2];
void update(int mul, int u, int x) {
    for (seg[mul][u += t] = x; u > 1; u >>= 1)
        seg[mul][u >> 1] = min(seg[mul][u], seg[mul][u ^ 1]);
}

int get(int mul, int l, int r) {
    int ans = Linf;
    for (l += t, r += t + 1; l < r; l >>= 1, r >>= 1) {
        if (l & 1) minimize(ans, seg[mul][l++]);
        if (r & 1) minimize(ans, seg[mul][--r]);
    }
    return ans;
}

void solve() {
    cin >> n >> t >> k;
    foru(i, 1, t) cin >> a[i], a[i] += a[i - 1];

    foru(i, 1, n) {
        char x;
        foru(j, 1, t) {
            cin >> x;
            last[j][i] = (x == '0' ? j : last[j - 1][i]);
            f[j][i] = f[j - 1][i] + (x == '1');
        }
    }

    foru(j, 1, t) sort(last[j] + 1, last[j] + n + 1);

    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = 0;

    foru(z, 1, k) {
        foru(x, 0, n) {
            foru(i, 1, t) {
                opt[i] = dp[i - 1][z - 1] - x * a[i - 1];
                update(x, i, opt[i]);
            }
        }
        
        foru(i, 1, t) {
            foru(p, 1, n)
                cnt[last[i][p]] += 1;
            last[i][n + 1] = i;

            foru(p, 1, n + 1) if (last[i][p] != last[i][p - 1])
                cnt[last[i][p]] += cnt[last[i][p - 1]];

            foru(p, 1, n + 1) {
                int l = last[i][p - 1] + 1, r = last[i][p];
                int x = cnt[l - 1];

                int ans = get(x, l, r);
                minimize(dp[i][z], ans + a[i] * x);
            }

            foru(p, 0, n + 1) cnt[last[i][p]] = 0;
        }

        cout << dp[t][z] << "\n";
    }
}

signed main() {
    FastIO;

    #define task "test"
    if (fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}

    #ifdef Sieve
        Linear_sieve();
    #endif

    #ifdef Ckn_calc
        precal_nck();
    #endif

    int ntest = 1;
    // cin >> ntest;
    while (ntest--) {
        //cout << "Case " << q << ": " << "\n"; 
        solve();
        cout << "\n";
    }

    return 0;
}

/**  /\_/\
 *  (= ._.)
 *  / >TL \>AC
**/

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:176:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:177:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12380 KB Output is correct
2 Correct 5 ms 22620 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 27228 KB Output is correct
2 Correct 30 ms 27228 KB Output is correct
3 Correct 32 ms 27228 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 30212 KB Output is correct
2 Correct 200 ms 32344 KB Output is correct
3 Correct 273 ms 32344 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12380 KB Output is correct
2 Correct 5 ms 22620 KB Output is correct
3 Correct 31 ms 27228 KB Output is correct
4 Correct 30 ms 27228 KB Output is correct
5 Correct 32 ms 27228 KB Output is correct
6 Correct 143 ms 30212 KB Output is correct
7 Correct 200 ms 32344 KB Output is correct
8 Correct 273 ms 32344 KB Output is correct
9 Correct 458 ms 34648 KB Output is correct
10 Correct 625 ms 36688 KB Output is correct
11 Correct 1582 ms 43336 KB Output is correct
12 Correct 1664 ms 44116 KB Output is correct
13 Correct 1650 ms 44352 KB Output is correct
14 Correct 1645 ms 44204 KB Output is correct
15 Correct 1641 ms 44240 KB Output is correct