Submission #230874

#	Time	Username	Problem	Language	Result	Execution time	Memory
230874		walnutwaldo20	Popeala (CEOI16_popeala)	C++14	8 / 100	460 ms	1608 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[MAXN];
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 i, int j) {
    ll amt = pref[j] - (i == -1 ? 0 : pref[i]);
    return amt * numsolved[i + 1];
}

void read() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> t >> s;
    F0R(i, t) cin >> pref[i];
    F0R(i, t) if (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;
        
        vi toprocess;
        F0R(cont, n) if (!solved[cont][i]) {
            int lastmissed = i - 1;
            while (lastmissed >= 0 && solved[cont][lastmissed]) {
                lastmissed--;
            }
            toprocess.PB(lastmissed + 1);
        }
        sort(toprocess.begin(), toprocess.end());
        for (const int startp : toprocess) {
            FOR(j, startp, i + 1) numsolved[j]--;
        }
        
        F0R(numgroups, s + 1) {
            F0R(numsolves, n + 1) bestIdx[numgroups][numsolves] = -1;
            F0R(numprevtests, numtests) {
                int ns = numsolved[numprevtests];
                int bi = bestIdx[numgroups][ns];
                if (bi == -1 ||
                    dp[numprevtests][numgroups] + cost(numprevtests - 1, i) <
                    dp[bi][numgroups] + cost(bi - 1, i)) {
                    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 - 1, i));
            }
        }
    }
    
    F0R(j, s + 1) if (j) {
        cout << dp[t][j] << "\n";
    }
}

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