oj.uz

Submission #908782

# Submission time Handle Problem Language Result Execution time Memory
908782 2024-01-16T20:43:08 Z tvladm2009 Popeala (CEOI16_popeala) C++17
100 / 100
 217 ms 11860 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int T = 2e4 + 7;
const int N = 50 + 7;
const int INF = 2e9;
int n, t, S;
int points[T], pref[T];
int dp[N][T], best[T], last[T][N];
string s[N];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> t >> S;
    for (int i = 1; i <= t; ++i) cin >> points[i];
    for (int i = 1; i <= t; ++i) pref[i] = pref[i - 1] + points[i];
    for (int i = 1; i <= n; ++i) cin >> s[i];
    for (int i = 1; i <= n; ++i) s[i] = "#" + s[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= t; ++j) {
            if (s[i][j] == '0') {
                last[j][i] = j; 
            } else {
                last[j][i] = last[j - 1][i];
            }
        }
    }
    for (int i = 1; i <= t; ++i) {
        last[i][0] = i;
        sort(last[i], last[i] + n + 1);
    }
    for (int g = 0; g <= S; ++g) for (int i = 0; i <= t; ++i) dp[g][i] = INF;
    dp[0][0] = 0;
    for (int i = 1; i <= S; ++i) {
        for (int j = 0; j <= n; ++j) best[j] = INF;
        for (int j = 1; j <= t; ++j) {
            for (int cnt = 0; cnt <= n; ++cnt) {
                for (int it = last[j - 1][cnt]; it < last[j][cnt]; ++it) 
                    best[cnt] = min(best[cnt], dp[i - 1][it] - cnt * pref[it]);
                dp[i][j] = min(dp[i][j], best[cnt] + cnt * pref[j]);
            }
        }
    }
    for (int i = 1; i <= S; ++i) cout << dp[i][t] << "\n";
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4700 KB Output is correct
2 Correct 6 ms 4700 KB Output is correct
3 Correct 7 ms 4700 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 7000 KB Output is correct
2 Correct 42 ms 7000 KB Output is correct
3 Correct 46 ms 7320 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 7 ms 4700 KB Output is correct
4 Correct 6 ms 4700 KB Output is correct
5 Correct 7 ms 4700 KB Output is correct
6 Correct 32 ms 7000 KB Output is correct
7 Correct 42 ms 7000 KB Output is correct
8 Correct 46 ms 7320 KB Output is correct
9 Correct 56 ms 7656 KB Output is correct
10 Correct 98 ms 7924 KB Output is correct
11 Correct 150 ms 11512 KB Output is correct
12 Correct 168 ms 11604 KB Output is correct
13 Correct 213 ms 11600 KB Output is correct
14 Correct 217 ms 11860 KB Output is correct
15 Correct 216 ms 11612 KB Output is correct