Submission #37322

#	Time	Username	Problem	Language	Result	Execution time	Memory
37322		cheater2k	Popeala (CEOI16_popeala)	C++14	100 / 100	1896 ms	16224 KiB

popeala

#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 (stderr)

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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74