oj.uz

Submission #146784

# Submission time Handle Problem Language Result Execution time Memory
146784 2019-08-26T06:38:18 Z lyc Popeala (CEOI16_popeala) C++14
100 / 100
 501 ms 6904 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[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.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 888 KB Output is correct
2 Correct 13 ms 888 KB Output is correct
3 Correct 14 ms 888 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 1608 KB Output is correct
2 Correct 77 ms 1664 KB Output is correct
3 Correct 89 ms 2040 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 14 ms 888 KB Output is correct
4 Correct 13 ms 888 KB Output is correct
5 Correct 14 ms 888 KB Output is correct
6 Correct 56 ms 1608 KB Output is correct
7 Correct 77 ms 1664 KB Output is correct
8 Correct 89 ms 2040 KB Output is correct
9 Correct 141 ms 2808 KB Output is correct
10 Correct 197 ms 3536 KB Output is correct
11 Correct 431 ms 6560 KB Output is correct
12 Correct 450 ms 6904 KB Output is correct
13 Correct 501 ms 6752 KB Output is correct
14 Correct 497 ms 6852 KB Output is correct
15 Correct 485 ms 6824 KB Output is correct