oj.uz

Submission #230895

# Submission time Handle Problem Language Result Execution time Memory
230895 2020-05-11T23:24:22 Z walnutwaldo20 Popeala (CEOI16_popeala) C++14
100 / 100
 520 ms 9976 KB 
#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.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 896 KB Output is correct
2 Correct 14 ms 768 KB Output is correct
3 Correct 15 ms 768 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1760 KB Output is correct
2 Correct 65 ms 2048 KB Output is correct
3 Correct 99 ms 2560 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 15 ms 896 KB Output is correct
4 Correct 14 ms 768 KB Output is correct
5 Correct 15 ms 768 KB Output is correct
6 Correct 49 ms 1760 KB Output is correct
7 Correct 65 ms 2048 KB Output is correct
8 Correct 99 ms 2560 KB Output is correct
9 Correct 158 ms 3840 KB Output is correct
10 Correct 207 ms 4856 KB Output is correct
11 Correct 516 ms 9792 KB Output is correct
12 Correct 520 ms 9848 KB Output is correct
13 Correct 476 ms 9728 KB Output is correct
14 Correct 491 ms 9976 KB Output is correct
15 Correct 490 ms 9848 KB Output is correct