Submission #146778

#	Time	Username	Problem	Language	Result	Execution time	Memory
146778		lyc	Popeala (CEOI16_popeala)	C++14	0 / 100	161 ms	1392 KiB

popeala

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int INF = 2e9+10;

const int MAXT = 20005;
const int MAXN = 55;
const int MAXS = 55;

int N, T, S;
int P[MAXT];
char R[MAXN][MAXT];
int res[MAXS][MAXT];

struct Line { int m, c; };

struct Hull : deque<Line> {
    void add(Line l) {
        //cout << "ADD " << l.m << " " << l.c << endl;
        for (int s; (s = size()) > 1;) {
            if ( (l.c - at(s-1).c) * (at(s-2).m - at(s-1).m) <= (at(s-1).c - at(s-2).c) * (at(s-1).m - l.m) )
                pop_back();
            else break;
        }
        push_back(l);
    }

    int query(int x) {
        for (int s; (s = size()) > 1;) {
            if ( x * (at(s-1).m - at(s-2).m) <= at(s-2).c - at(s-1).c )
                pop_back();
            else break;
        }
        //cout << "LINE " << back().m << " " << back().c << " :: " << x*back().m + back().c << endl;
        return back().m * x + back().c;
    }
} ch[MAXN];

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> T >> S;
    FOR(i,1,T) { cin >> P[i]; P[i] += P[i-1]; }
    FOR(i,1,N) { cin >> (R[i]+1); }
    //FOR(i,1,N) { FOR(j,1,T) { cout << R[i][j] << " "; } cout << endl; }

    res[0][T+1] = 0;
    FOR(x,1,S) res[x][T+1] = INF;
    FOR(i,1,T) res[0][i] = INF;
    int nxt[N+1], state[T+2];

    FOR(x,1,S) {
        fill(nxt+1, nxt+1+N, T+1);
        state[T+1] = 0;
        FOR(m,0,N) ch[m].clear();

        RFOR(i,T,1) {
            state[i] = N;
            if (res[x-1][i+1] != INF) ch[N].add((Line){ P[i], res[x-1][i+1] });
            FOR(m,1,N) if (R[m][i] == '0') {
                //cout << "up" << m << " " << nxt[m] << " " << state[i] << endl;
                if (state[nxt[m]]-1 >= 0) {
                    RFOR(j,SZ(ch[state[nxt[m]]])-1,0) ch[state[nxt[m]]-1].add(ch[state[nxt[m]]][j]);
                }
                ch[state[nxt[m]]].clear();

                FOR(j,state[nxt[m]]+1,state[i]) {
                    swap(ch[j],ch[j-1]);
                }
                nxt[m] = i;
                --state[i];
            }
            res[x][i] = INF;
            //FOR(m,0,N) { cout << ch[m].size() << ' '; } cout << endl;
            FOR(m,0,N) if (!ch[m].empty()) {
                int cur = -P[i-1]*m + ch[m].query(m);
                //cout << "\t\t\t" << cur << " BY " << m << endl;
                res[x][i] = min(res[x][i], cur);
            }
            //FOR(m,0,N) { cerr << SZ(ch[m]) << ':' << (ch[m].empty() ? -1 : ch[m].query()) << ' '; } cerr << endl;
            //cout << "\t" << x << " " << i << " :: " << res[x][i] << endl;
        }
    }

    FOR(i,1,S) cout << res[i][1] << '\n';
}

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