oj.uz

Submission #860167

# Submission time Handle Problem Language Result Execution time Memory
860167 2023-10-12T00:41:31 Z Nhoksocqt1 Popeala (CEOI16_popeala) C++17
100 / 100
 253 ms 24860 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9052 KB Output is correct
2 Correct 2 ms 13224 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15708 KB Output is correct
2 Correct 8 ms 15704 KB Output is correct
3 Correct 8 ms 15968 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16312 KB Output is correct
2 Correct 41 ms 16732 KB Output is correct
3 Correct 53 ms 17232 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9052 KB Output is correct
2 Correct 2 ms 13224 KB Output is correct
3 Correct 8 ms 15708 KB Output is correct
4 Correct 8 ms 15704 KB Output is correct
5 Correct 8 ms 15968 KB Output is correct
6 Correct 31 ms 16312 KB Output is correct
7 Correct 41 ms 16732 KB Output is correct
8 Correct 53 ms 17232 KB Output is correct
9 Correct 74 ms 18504 KB Output is correct
10 Correct 102 ms 19436 KB Output is correct
11 Correct 199 ms 24408 KB Output is correct
12 Correct 215 ms 24672 KB Output is correct
13 Correct 246 ms 24616 KB Output is correct
14 Correct 247 ms 24668 KB Output is correct
15 Correct 253 ms 24860 KB Output is correct