oj.uz

Submission #146294

# Submission time Handle Problem Language Result Execution time Memory
146294 2019-08-23T10:21:46 Z lyc Popeala (CEOI16_popeala) C++14
26 / 100
 2000 ms 2632 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 632 KB Output is correct
2 Correct 25 ms 692 KB Output is correct
3 Correct 23 ms 764 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 1388 KB Output is correct
2 Correct 760 ms 1784 KB Output is correct
3 Correct 1389 ms 2084 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 23 ms 632 KB Output is correct
4 Correct 25 ms 692 KB Output is correct
5 Correct 23 ms 764 KB Output is correct
6 Correct 411 ms 1388 KB Output is correct
7 Correct 760 ms 1784 KB Output is correct
8 Correct 1389 ms 2084 KB Output is correct
9 Execution timed out 2051 ms 2632 KB Time limit exceeded
10 Halted 0 ms 0 KB -