Submission #230895

#	Time	Username	Problem	Language	Result	Execution time	Memory
230895		walnutwaldo20	Popeala (CEOI16_popeala)	C++14	100 / 100	520 ms	9976 KiB

popeala

#include <bits/stdc++.h>

#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)

#define PB push_back

using namespace std;

typedef vector<int> vi;
typedef long long ll;

#define MAXN 50
#define MAXT 20000
#define MAXS 50

int n, t, s;
ll pref[MAXT];
int numsolved[MAXT];
ll dp[MAXT + 1][MAXN + 1];
vi bestIdx[MAXS + 1];
bool solved[MAXN][MAXT];

void upd(ll& a, ll b) { a = min(a, b); }

ll cost(int prevcases, int newcases) {
    ll amt = pref[newcases - 1] - (prevcases == 0 ? 0 : pref[prevcases - 1]);
    return amt * numsolved[prevcases];
}

void read() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> t >> s;
    F0R(i, t) cin >> pref[i];
    FOR(i, 1, t) {
        pref[i] += pref[i - 1];
    }
    F0R(i, n) {
        F0R(j, t) {
            char c;
            cin >> c;
            solved[i][j] = (c == '1');
        }
    }
}

int main() {
    read();
    F0R(i, t + 1) F0R(j, s + 1) dp[i][j] = 1e10;
    dp[0][0] = 0;
    
    F0R(i, t) numsolved[i] = n;
    F0R(i, s + 1) {
        bestIdx[i] = vi(n + 1, -1);
        bestIdx[i][n] = 0;
    }
    
    FOR(numtests, 1, t + 1) {
        int i = numtests - 1;
        
        int recalcp = numtests - 1;
        int clearp = n + 1;
        vi toprocess;
        F0R(cont, n) if (!solved[cont][i]) {
            int lastmissed = i - 1;
            while (lastmissed >= 0 && solved[cont][lastmissed]) {
                lastmissed--;
            }
            toprocess.PB(lastmissed + 1);
            recalcp = min(recalcp, lastmissed + 1);
            clearp = min(clearp, numsolved[lastmissed + 1]);
        }
        for (const int k : toprocess) {
            FOR(j, k, numtests) numsolved[j]--;
        }
        
        F0R(numgroups, s + 1) {
            FOR(numsolves, clearp, n + 1) bestIdx[numgroups][numsolves] = -1;
            FOR(numprevtests, recalcp, numtests) {
                int ns = numsolved[numprevtests];
                int bi = bestIdx[numgroups][ns];
                if (bi == -1 ||
                    dp[numprevtests][numgroups] + cost(numprevtests, numtests) <
                    dp[bi][numgroups] + cost(bi, numtests)) {
                    bestIdx[numgroups][ns] = numprevtests;
                }
            }
        }
        
        ROF(numgroups, 1, s + 1) {
            F0R(cnt, n + 1) if (bestIdx[numgroups - 1][cnt] != -1) {
                int previ = bestIdx[numgroups - 1][cnt];
                upd(dp[numtests][numgroups], dp[previ][numgroups - 1] +
                    cost(previ, numtests));
            }
        }
    }
    
    FOR(j, 1, s + 1) {
        cout << dp[t][j] << "\n";
    }
}

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