oj.uz

Submission #538321

# Submission time Handle Problem Language Result Execution time Memory
538321 2022-03-16T15:24:16 Z siewjh Popeala (CEOI16_popeala) C++17
26 / 100
 598 ms 5504 KB 
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
int pref[20'005];
bool ac[55][20'005];
int dp[55][20'005];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int ppl, cases, grp; cin >> ppl >> cases >> grp;
    pref[0] = 0;
    for (int i = 1; i <= cases; i++) {
        cin >> pref[i];
        pref[i] += pref[i - 1];
    }
    for (int i = 1; i <= ppl; i++){
        string str; cin >> str;
        for (int j = 1; j <= cases; j++) ac[i][j] = (str[j - 1] == '1');
    }
    for (int i = 0; i <= grp; i++)
        for (int j = 0; j <= cases; j++)
            dp[i][j] = inf;
    dp[0][0] = 0;
    for (int i = 1; i <= grp; i++){
        int best[55], last[55], fc[20'005];
        memset(best, 0, sizeof(best));
        memset(last, 0, sizeof(last));
        for (int j = 0; j <= cases; j++) fc[j] = ppl;
        for (int j = 1; j <= cases; j++){
            if (dp[i - 1][best[ppl]] + (pref[j] - pref[best[ppl]]) * fc[best[ppl] + 1] > dp[i - 1][j - 1] + (pref[j] - pref[j - 1]) * ppl) best[ppl] = j - 1;
            for (int p = 1; p <= ppl; p++){
                if (ac[p][j]) continue;
                for (int k = last[p] + 1; k <= j; k++) best[fc[k]] = 0;
                for (int k = last[p] + 1; k <= j; k++){
                    fc[k]--;
                    if (dp[i - 1][best[fc[k]]] + (pref[j] - pref[best[fc[k]]]) * fc[k] > dp[i - 1][k - 1] + (pref[j] - pref[k - 1]) * fc[k]) best[fc[k]] = k - 1;
                }
                last[p] = j;
            }
            if (j < i) continue;
            for (int p = 0; p <= ppl; p++) dp[i][j] = min(dp[i][j], dp[i - 1][best[p]] + (pref[j] - pref[best[p]]) * fc[best[p] + 1]);
        }
        cout << dp[i][cases] << '\n';
    }
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 964 KB Output is correct
2 Correct 17 ms 852 KB Output is correct
3 Correct 16 ms 852 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 1436 KB Output is correct
2 Correct 90 ms 1492 KB Output is correct
3 Correct 119 ms 1816 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 16 ms 964 KB Output is correct
4 Correct 17 ms 852 KB Output is correct
5 Correct 16 ms 852 KB Output is correct
6 Correct 63 ms 1436 KB Output is correct
7 Correct 90 ms 1492 KB Output is correct
8 Correct 119 ms 1816 KB Output is correct
9 Correct 209 ms 2444 KB Output is correct
10 Correct 257 ms 2956 KB Output is correct
11 Correct 598 ms 5472 KB Output is correct
12 Incorrect 582 ms 5504 KB Output isn't correct
13 Halted 0 ms 0 KB -