oj.uz

Submission #37322

# Submission time Handle Problem Language Result Execution time Memory
37322 2017-12-24T04:30:22 Z cheater2k Popeala (CEOI16_popeala) C++14
100 / 100
 1896 ms 16224 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXT = 20010, MAXN = 55;
const int INF = 2e9 + 10023;

int N, S, T;
char a[MAXN][MAXT];
int score[MAXT];
int sum[MAXN][MAXT];
int f[MAXT][MAXN];
int cur[MAXN], mn[MAXN][MAXT];

int get(int l, int r) {
    if (l > r) return 0;
    int res = 0;
    for (int i = 1; i <= N; ++i) res += (sum[i][r] - sum[i][l-1] == r - l + 1);
    return res;
}

void reset(int k) {
    for (int i = 0; i <= N; ++i) {
        mn[i][0] = f[0][k];
        for (int j = 1; j <= T; ++j) mn[i][j] = min(mn[i][j-1], f[j][k] - i * score[j]);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N >> T >> S;

    for (int i = 1; i <= T; ++i) cin >> score[i], score[i] += score[i-1];
    for (int i = 1; i <= N; ++i) for (int j = 1; j <= T; ++j) cin >> a[i][j], sum[i][j] = sum[i][j-1] + (a[i][j] - '0');
    for (int i = 1; i <= T; ++i) f[i][0] = INF; reset(0);
    for (int k = 1; k <= S; ++k) {
        vector <int> v;
        for (int i = 1; i <= N; ++i) cur[i] = 1, v.push_back(i);
        f[0][k] = INF;
        for (int i = 1; i <= T; ++i) {
            for (int j = 1; j <= N; ++j) cur[j] = (a[j][i] == '1') ? cur[j] : i + 1;
            vector <int> newV; for (int j = 1; j <= N; ++j) if (cur[j] == i + 1) newV.push_back(j);
            for (int j = 0; j < v.size(); ++j) if (cur[v[j]] != i + 1) newV.push_back(v[j]);

            v = newV;
            f[i][k] = INF; if (i < k) continue;
            for (int j = 0; j <= v.size(); ++j) {
                int l = (j == v.size()) ? 1 : cur[v[j]];
                int r = (j == 0) ? i : cur[v[j-1]] - 1;
                if (l <= r) f[i][k] = min(f[i][k], mn[N-j][r-1] + (N-j) * score[i]);
            }
        }
        reset(k);
    }

    for (int k = 1; k <= S; ++k) cout << f[T][k] << endl;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:42:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < v.size(); ++j) if (cur[v[j]] != i + 1) newV.push_back(v[j]);
                               ^
popeala.cpp:46:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j <= v.size(); ++j) {
                               ^
popeala.cpp:47:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 int l = (j == v.size()) ? 1 : cur[v[j]];
                            ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 16224 KB Output is correct
2 Correct 0 ms 16224 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 16224 KB Output is correct
2 Correct 36 ms 16224 KB Output is correct
3 Correct 36 ms 16224 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 16224 KB Output is correct
2 Correct 266 ms 16224 KB Output is correct
3 Correct 329 ms 16224 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 16224 KB Output is correct
2 Correct 0 ms 16224 KB Output is correct
3 Correct 39 ms 16224 KB Output is correct
4 Correct 36 ms 16224 KB Output is correct
5 Correct 36 ms 16224 KB Output is correct
6 Correct 186 ms 16224 KB Output is correct
7 Correct 266 ms 16224 KB Output is correct
8 Correct 329 ms 16224 KB Output is correct
9 Correct 579 ms 16224 KB Output is correct
10 Correct 763 ms 16224 KB Output is correct
11 Correct 1623 ms 16224 KB Output is correct
12 Correct 1643 ms 16224 KB Output is correct
13 Correct 1866 ms 16224 KB Output is correct
14 Correct 1896 ms 16224 KB Output is correct
15 Correct 1823 ms 16224 KB Output is correct