oj.uz

Submission #1082674

# Submission time Handle Problem Language Result Execution time Memory
1082674 2024-09-01T05:59:11 Z _callmelucian Popeala (CEOI16_popeala) C++14
100 / 100
 540 ms 6996 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 2e4 + 4;
int dp[2][mn], opt[55][mn], pts[mn], pre[mn];
bool solved[55][mn];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, T, S; cin >> n >> T >> S;
    for (int i = 1; i <= T; i++) {
        cin >> pts[i];
        pre[i] = pre[i - 1] + pts[i];
    }
    for (int i = 1; i <= n; i++) {
        string s; cin >> s;
        for (int j = 1; j <= T; j++) solved[i][j] = (s[j - 1] == '1');
    }

    for (int j = 1; j <= T; j++) dp[0][j] = INT_MAX;
    for (int sub = 1; sub <= S; sub++) {
        int t = sub & 1;
        for (int j = 0; j <= T; j++)
            dp[t][j] = INT_MAX;
        for (int score = 0; score <= n; score++)
            opt[score][0] = dp[t ^ 1][0];

        vector<pii> order;
        for (int i = 1; i <= n; i++) order.emplace_back(i, 0);
        for (int j = 1; j <= T; j++) {
            vector<pii> tmp;
            for (pii it : order) {
                int row, col; tie(row, col) = it;
                if (!solved[row][j]) tmp.emplace_back(row, j);
            }
            for (pii it : order) {
                int row, col; tie(row, col) = it;
                if (solved[row][j]) tmp.emplace_back(row, col);
            }
            order = tmp;

            for (int block = 0, low = j; block <= n && low; block++) {
                int score = n - block;
                if (opt[score][low - 1] != INT_MAX)
                    dp[t][j] = min(dp[t][j], opt[score][low - 1] + pre[j] * score);
                if (block < n)
                    low = order[block].second;
            }

            if (dp[t ^ 1][j] == INT_MAX)
                for (int score = 0; score <= n; score++)
                    opt[score][j] = opt[score][j - 1];
            else
                for (int score = 0; score <= n; score++)
                    opt[score][j] = min(opt[score][j - 1], dp[t ^ 1][j] - pre[j] * score);
        }

        cout << dp[t][T] << "\n";
    }

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 860 KB Output is correct
2 Correct 11 ms 1036 KB Output is correct
3 Correct 15 ms 860 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1368 KB Output is correct
2 Correct 75 ms 1828 KB Output is correct
3 Correct 94 ms 2136 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 13 ms 860 KB Output is correct
4 Correct 11 ms 1036 KB Output is correct
5 Correct 15 ms 860 KB Output is correct
6 Correct 52 ms 1368 KB Output is correct
7 Correct 75 ms 1828 KB Output is correct
8 Correct 94 ms 2136 KB Output is correct
9 Correct 152 ms 2952 KB Output is correct
10 Correct 201 ms 3420 KB Output is correct
11 Correct 492 ms 6644 KB Output is correct
12 Correct 476 ms 6996 KB Output is correct
13 Correct 491 ms 6704 KB Output is correct
14 Correct 540 ms 6876 KB Output is correct
15 Correct 476 ms 6748 KB Output is correct