Submission #146308

#	Time	Username	Problem	Language	Result	Execution time	Memory
146308		lyc	Popeala (CEOI16_popeala)	C++14	0 / 100	5 ms	1164 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[MAXT][MAXS], opt[MAXT][MAXS];

int cost[MAXN][MAXT];
vector<int> flip[MAXN];

void dnc(int s, int e, int x, int y, int k) {
    int m = (s + e)/2;
    res[m][k] = INF, opt[m][k] = y;
    FOR(j,max(m,x),y) {
        int nxt = res[j+1][k-1];
        if (nxt != INF) { if (nxt + cost[m][j] < res[m][k]) res[m][k] = nxt + cost[m][j], opt[m][k] = j; }
    }
    //cout << "DNC " << s << " " << e << " " << x << " " << y << " :: " << m << " " << k << " :: " << res[m][k] << endl;
    
    if (s < m) dnc(s,m-1,x,opt[m][k],k);
    if (m < e) dnc(m+1,e,opt[m][k],y,k);
}

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[T+1][0] = 0; FOR(x,1,S) res[T+1][x] = INF;
    RFOR(i,T,1) {
        vector<int> die;
        die.push_back(i);
        FOR(j,1,N) die.push_back(*lower_bound(ALL(flip[j]), i));
        sort(ALL(die));
        FOR(j,i,T) cost[i][j] = (P[j]-P[i-1]) * (die.end() - upper_bound(ALL(die), j));

        res[i][1] = cost[i][T];
    }

    FOR(x,2,S) dnc(1,T,1,T,x);

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

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