Submission #860167

#	Time	Username	Problem	Language	Result	Execution time	Memory
860167		Nhoksocqt1	Popeala (CEOI16_popeala)	C++17	100 / 100	253 ms	24860 KiB

popeala

#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 20004;
const int MAXGROUP = 52;

vector<int> B[MAXN];
int sumP[MAXN], g[MAXGROUP][MAXN], dp[MAXGROUP][MAXN], maxL[MAXGROUP][MAXN];
int point[MAXN], sum[MAXGROUP][MAXN], numTest, numPerson, maxGroup;
bool result[MAXGROUP][MAXN];

void brute(void) {
    for (int j = 0; j <= maxGroup; ++j) {
        for (int i = 0; i <= numTest; ++i)
            dp[j][i] = 2e9+7;
    }

    dp[0][0] = 0;
    for (int j = 1; j <= maxGroup; ++j) {
        for (int i = 0; i < numTest; ++i) {
            if(dp[j - 1][i] > 2e9)
                continue;

            for (int k = i + 1; k <= numTest; ++k) {
                int cnt(0);
                for (int l = 1; l <= numPerson; ++l)
                    cnt += (sum[l][k] - sum[l][i] == k - i);

                dp[j][k] = min(dp[j][k], dp[j - 1][i] + cnt * (sumP[k] - sumP[i]));
                //cout << cnt << ' ' << i + 1 << ' ' << k << ' ' << dp[j][k] << ' ' << (sumP[k] - sumP[i]) * cnt << '\n';
            }
        }
    }

    for (int j = 1; j <= maxGroup; ++j)
        cout << dp[j][numTest] << '\n';
}

void process(void) {
    cin >> numPerson >> numTest >> maxGroup;
    for (int i = 1; i <= numTest; ++i) {
        cin >> point[i];
        //point[i] = Random(1, 100); cout << point[i] << " \n"[i == numTest];
        sumP[i] = sumP[i - 1] + point[i];
    }

    for (int j = 1; j <= numPerson; ++j) {
        for (int i = 1; i <= numTest; ++i) {
            char c;
            cin >> c;
            //c = Random('0', '1'); cout << c; if(i == numTest) cout << '\n';
            result[j][i] = (c == '1');
            sum[j][i] = sum[j][i - 1] + result[j][i];
        }
    }

    //brute();
    for (int j = 1; j <= maxGroup; ++j) {
        for (int i = 1; i <= numTest; ++i)
            dp[j][i] = 2e9+7;
    }

    for (int i = 1; i <= numTest; ++i) {
        int cnt(0);
        for (int j = 1; j <= numPerson; ++j)
            cnt += (sum[j][i] == i);

        dp[1][i] = cnt * sumP[i];
    }

    for (int i = 1; i <= numTest; ++i) {
        for (int j = 1; j <= numPerson; ++j)
            maxL[j][i] = (result[j][i] & result[j][i - 1]) ? maxL[j][i - 1] : i + (!result[j][i]);

        for (int j = 1; j <= numPerson; ++j)
            B[i].push_back(maxL[j][i]);

        sort(B[i].begin(), B[i].end(), greater<int>());
    }

    for (int j = 2; j <= maxGroup; ++j) {
        for (int k = 0; k <= numPerson; ++k)
            g[k][j - 2] = 2e9+7;

        for (int i = j - 1; i <= numTest; ++i) {
            for (int k = 0; k <= numPerson; ++k)
                g[k][i] = min(g[k][i - 1], dp[j - 1][i] - k * sumP[i]);
        }

        for (int i = j; i <= numTest; ++i) {
            int cnt(0);
            for (int k = 1; k <= numPerson; ++k)
                cnt += (result[k][i]);

            dp[j][i] = sumP[i] * cnt + g[cnt][i - 1];

            vector<int> p(B[i]);
            for (int it = 0; it < sz(p); ++it) {
                if(it + 1 < sz(p) && p[it] == p[it + 1])
                    continue;

                int x(p[it]); --x;
                if(x >= j) {
                    dp[j][i] = min(dp[j][i], sumP[i] * (sz(p) - it - 1) + g[sz(p) - it - 1][x - 1]);
                    //if(j == 2) cout << j << ' ' << i << ' ' << x << ' ' << sz(p) - it - 1 << ' ' << g[sz(p) - it - 1][x - 1] << '\n';
                }
            }
        }
    }

    for (int i = 1; i <= maxGroup; ++i)
        cout << dp[i][numTest] << '\n';
}

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    process();
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74