oj.uz

Submission #230889

# Submission time Handle Problem Language Result Execution time Memory
230889 2020-05-11T23:14:23 Z walnutwaldo20 Popeala (CEOI16_popeala) C++14
17 / 100
 2000 ms 2432 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;
        
        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, numtests) 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, 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 44 ms 888 KB Output is correct
2 Correct 44 ms 768 KB Output is correct
3 Correct 51 ms 976 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 1616 KB Output is correct
2 Correct 1166 ms 2016 KB Output is correct
3 Execution timed out 2082 ms 2432 KB Time limit exceeded

Subtask #4
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 44 ms 888 KB Output is correct
4 Correct 44 ms 768 KB Output is correct
5 Correct 51 ms 976 KB Output is correct
6 Correct 543 ms 1616 KB Output is correct
7 Correct 1166 ms 2016 KB Output is correct
8 Execution timed out 2082 ms 2432 KB Time limit exceeded