oj.uz

Submission #1082668

# Submission time Handle Problem Language Result Execution time Memory
1082668 2024-09-01T05:20:45 Z _callmelucian Popeala (CEOI16_popeala) C++14
0 / 100
 44 ms 856 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], pts[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];
    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 sub = 1; sub <= S; sub++) {
        int t = sub & 1;
        for (int j = 0; j <= T; j++) dp[t][j] = INT_MAX;

        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;

            if (j < sub) continue;
            int sumPt = pts[j] * n, low = j;
            for (int block = 0; block <= n && low; block++, sumPt -= pts[j]) {
                if (dp[t ^ 1][low - 1] != INT_MAX)
                    dp[t][j] = min(dp[t][j], dp[t ^ 1][low - 1] + sumPt);
                if (block < n)
                    low = min(low, order[block].second);
            }
        }

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

    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -