Submission #98733

#	Time	Username	Problem	Language	Result	Execution time	Memory
98733		SpeedOfMagic	Popeala (CEOI16_popeala)	C++17	0 / 100	1229 ms	2688 KiB

popeala

/** MIT License Copyright (c) 2018-2019 Vasilev Daniil **/
#include <bits/stdc++.h>
using namespace std;
template<typename T> using v = vector<T>;
//#define int long long
typedef long double ld;
typedef string str;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define fs first
#define sc second
#define sz(a) ((int) a.size())
const long long inf = 4611686018427387903; //2^62 - 1
const long double EPS = 1e-10;
#if 0  //FileIO
const string fileName = "";
ifstream fin ((fileName == "" ? "input.txt"  : fileName + ".in" ));
ofstream fout((fileName == "" ? "output.txt" : fileName + ".out"));
#define get fin >>
#define put fout <<
#else
#define get cin >>
#define put cout <<
#endif
#define eol put endl
void read() {} template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get (arg)     ;read(args...) ;}
void print(){} template<typename Arg,typename... Args> void print(Arg  arg,Args...  args){put (arg)<<" ";print(args...);}
int getInt(){int a; get a; return a;}
//code starts here
const int N = 32768;
const int oo = 2000000001;
int val[N * 2], lazy[N * 2];

inline void pushdown(int cur) {
    if (cur < N) {
        lazy[cur << 1] += lazy[cur];
        lazy[cur << 1 | 1] += lazy[cur];
    }

    val[cur] += lazy[cur];
    lazy[cur] = 0;
}

inline void upd(int l, int r, int w, int cur = 1, int ll = 1, int rr = N) {
    if (l > r)
        return;
    pushdown(cur);
    if (l == ll && r == rr) {
        lazy[cur] += w;
        pushdown(cur);
        return;
    }

    int mid = (ll + rr) >> 1;
    upd(l, min(r, mid), w, cur << 1, ll, mid);
    upd(max(l, mid + 1), r, w, cur << 1 | 1, mid + 1, rr);
    val[cur] = min(val[cur << 1], val[cur << 1 | 1]);
}

inline int query(int l, int r, int cur = 1, int ll = 1, int rr = N) {
    if (l > r)
        return oo;
    pushdown(cur);
    if (l == ll && r == rr)
        return val[cur];
    int mid = (ll + rr) >> 1;
    return min(query(l, min(r, mid), cur << 1, ll, mid),
               query(max(l, mid + 1), r, cur << 1 | 1, mid + 1, rr));
}

struct quer {
    int l, r, w;
    quer() {}
    quer(int ll, int rr, int ww) : l(ll), r(rr), w(ww) {}
};

void run() {
    int n, t, s;
    read(n, t, s);
    int pts[t];
    rep(i, 0, t)
        get pts[i];

    char res[n][t];
    rep(i, 0, n) {
        str st;
        get st;
        rep(j, 0, t)
            res[i][j] = st[j] - '0';
    }

    quer queries[n][t];
    rep(i, 0, n) {
        int pr = 0, sum = 0;
        rep(j, 0, t) {
            if (res[i][j]) {
                queries[i][j] = quer(pr + 1, j, pts[j]);
                if (j != pr)
                    sum += pts[j];
            } else {
                queries[i][j] = quer(pr + 1, j - 1, -sum);
                sum = 0;
                pr = j;
            }
        }
    }

    int dp[t][s];
    rep(i, 0, t)
        rep(j, 0, s)
            dp[i][j] = oo;

    int cur[n];
    memset(cur, 0, sizeof cur);
    rep(i, 0, t) {
        rep(j, 0, n)
            if (res[j][i] && cur[j] != -1)
                cur[j] += pts[i];
            else
                cur[j] = -1;

        dp[i][0] = 0;
        rep(j, 0, n)
            if (cur[j] != -1)
                dp[i][0] += cur[j];
    }

    rep(j, 1, s) {
        memset(lazy, 0, sizeof lazy);
        for (int i = N; i < N + t; i++)
            val[i] = dp[i - N][j - 1];
        for (int i = N + t; i < N * 2; i++)
            val[i] = oo;
        for (int i = N - 1; i; i--)
            val[i] = min(val[i << 1], val[i << 1 | 1]);

        rep(i, 0, t) {
            memset(cur, 0, sizeof cur);
            rep(l, 0, n)
                upd(queries[l][i].l, queries[l][i].r, queries[l][i].w);
            dp[i][j] = min(dp[i][j], query(1, i));
        }
    }

    rep(j, 0, s)
        put dp[t - 1][j], eol;

    /*
    rep(i, 0, n)
        rep(j, 0, t)
            print(j, queries[i][j].l, queries[i][j].r, queries[i][j].w), eol;
    rep(i, 0, s) {
        rep(j, 0, t)
            print(dp[j][i]);
        eol;
    }
    */
}
/* 0 8 16
2 3 3
4 3 5
101
110
*//* 7 7
1 2 2
4 3
11
*//* 0 1
1 3 2
2 4 1
011
*/
signed main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); put fixed << setprecision(12); run(); return 0;}

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