Submission #146784

#	Time	Username	Problem	Language	Result	Execution time	Memory
146784		lyc	Popeala (CEOI16_popeala)	C++14	100 / 100	501 ms	6904 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];

int cost[MAXT];
vector<int> flip[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(j,1,T) {
            if (R[i][j] == '0') flip[i].push_back(j);
        }
        flip[i].push_back(T+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;

    FOR(x,1,S) {
        int nxt[N+1];   FOR(i,1,N) nxt[i] = T+1;
        int state[T+1]; FOR(i,1,T) state[i] = -1;
        int best[N+1];  FOR(i,0,N) best[i] = INF;
        RFOR(i,T,1) {
            state[i] = N;
            if (res[x-1][i+1] != INF) best[N] = min(best[N], P[i]*N + res[x-1][i+1]);
            FOR(m,1,N) if (R[m][i] == '0') {
                //cout << "STATE " << state[nxt[m]-1] << " " << state[i] << endl;
                FOR(s,state[nxt[m]-1],state[i]) best[s] = INF;
                FOR(j,i,nxt[m]-1) {
                    //cout << state[j]-1 << " AAAAA " << P[j]*state[j] + res[x-1][j+1] << endl;
                    --state[j];
                    if (res[x-1][j+1] != INF) best[state[j]] = min(best[state[j]], P[j]*state[j] + res[x-1][j+1]);
                }
                nxt[m] = i;
            }

            res[x][i] = INF;
            FOR(s,0,N) if (best[s] != INF) res[x][i] = min(res[x][i], -P[i-1]*s + best[s]);

            //FOR(j,i,T) {
            //    int nxt = res[x-1][j+1];
            //    if (nxt != INF) res[x][i] = min(res[x][i], nxt + (P[j]-P[i-1])*state[j]);
            //}
            //FOR(j,1,T) { cout << state[j] << ' '; } cout << endl;
            //FOR(s,0,N) { cout << best[s] << ' '; } cout << endl;
            //cout << x << " " << i << " :: " << res[x][i] << endl;
        }
    }

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

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