Submission #134109

#	Time	Username	Problem	Language	Result	Execution time	Memory
134109		imeimi2000	Popeala (CEOI16_popeala)	C++17	100 / 100	1044 ms	16632 KiB

popeala

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long llong;

const llong inf = 1e18;
int n, t, s;
int P[20001];
llong dp[51][20001];

struct dq {
    int bt, tp;
    llong val[20001];
    int idx[20001];
    void init() {
        bt = tp = 0;
    }
    void push(int i, llong v) {
        while (bt < tp && val[tp - 1] > v) --tp;
        val[tp] = v;
        idx[tp] = i;
        ++tp;
    }
    void pop(int i) {
        if (bt < tp && idx[bt] == i) ++bt;
    }
    llong get() const {
        if (bt < tp) return val[bt];
        return inf;
    }
} D[51];
int bt[51], tp[51];

char R[51][20002];
int last[20001][51];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> t >> s;
    for (int i = 1; i <= t; ++i) {
        cin >> P[i];
        P[i] += P[i - 1];
        dp[0][i] = inf;
    }
    for (int i = 1; i <= n; ++i) cin >> R[i] + 1;
    for (int i = 1; i <= t; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (R[j][i] == '0') last[i][j] = i;
            else last[i][j] = last[i - 1][j];
        }
        last[i][0] = i;
    }
    for (int i = 1; i <= t; ++i)
        sort(last[i], last[i] + (n + 1));
    for (int g = 1; g <= s; ++g) {
        for (int i = 0; i <= n; ++i) {
            bt[i] = tp[i] = 0;
            D[i].init();
        }
        dp[g][0] = inf;
        for (int i = 1; i <= t; ++i) {
            int p = 0;
            llong v = inf;
            for (int j = 0; j <= n; ++j) {
                int x = last[i][j];
                while (tp[j] < x) {
                    D[j].push(tp[j], dp[g - 1][tp[j]] - (llong)P[tp[j]] * j);
                    ++tp[j];
                }
                while (bt[j] < p) {
                    D[j].pop(bt[j]);
                    ++bt[j];
                }
                v = min(v, D[j].get() + (llong)P[i] * j);
                p = x;
            }
            dp[g][i] = v;
        }
    }
    for (int i = 1; i <= s; ++i) printf("%lld\n", dp[i][t]);
    return 0;
}

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:46:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     for (int i = 1; i <= n; ++i) cin >> R[i] + 1;
                                         ~~~~~^~~

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74