oj.uz

Submission #134109

# Submission time Handle Problem Language Result Execution time Memory
134109 2019-07-22T05:38:38 Z imeimi2000 Popeala (CEOI16_popeala) C++17
100 / 100
 1044 ms 16632 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 888 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1656 KB Output is correct
2 Correct 28 ms 1532 KB Output is correct
3 Correct 30 ms 1656 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 3160 KB Output is correct
2 Correct 179 ms 3752 KB Output is correct
3 Correct 207 ms 4452 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 888 KB Output is correct
3 Correct 32 ms 1656 KB Output is correct
4 Correct 28 ms 1532 KB Output is correct
5 Correct 30 ms 1656 KB Output is correct
6 Correct 126 ms 3160 KB Output is correct
7 Correct 179 ms 3752 KB Output is correct
8 Correct 207 ms 4452 KB Output is correct
9 Correct 281 ms 6188 KB Output is correct
10 Correct 475 ms 7948 KB Output is correct
11 Correct 814 ms 15300 KB Output is correct
12 Correct 855 ms 15648 KB Output is correct
13 Correct 1012 ms 16608 KB Output is correct
14 Correct 1044 ms 16632 KB Output is correct
15 Correct 1022 ms 16468 KB Output is correct