Submission #146294

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

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[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[j] = (P[j]-P[i-1]) * (die.end() - upper_bound(ALL(die), j));

        res[i][1] = cost[T];
        FOR(x,2,S) {
            res[i][x] = INF;
            FOR(j,i,T) {
                int nxt = res[j+1][x-1];
                if (nxt != INF) res[i][x] = min(res[i][x], nxt + cost[j]);
            }
            //cout << i << " " << x << " :: " << res[i][x] << endl;
        }
    }

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

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