Submission #537027

#	Time	Username	Problem	Language	Result	Execution time	Memory
537027		joelau	Popeala (CEOI16_popeala)	C++14	26 / 100	2081 ms	161740 KiB

popeala

#include <bits/stdc++.h>
using namespace std;

long long N,T,S, A[20005], B[55][20005], dp[2][20005], spt[55][20005][20], pos[55], inf = 2100000000;
vector<long long> v;

long long query (long long n, long long i, long long j) {
    long long k = (long long) floor(log((double)j-i+1) / log(2.0));
    return min(spt[n][i][k],spt[n][j-(1<<k)+1][k]);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> T >> S;
    A[0] = 0;
    for (long long i = 1; i <= T; ++i) {
        cin >> A[i];
        A[i] += A[i-1];
    }
    for (long long i = 1; i <= N; ++i) for (long long j = 1; j <= T; ++j) {
        char ch; cin >> ch;
        B[i][j] = ch - '0';
    }
    for (long long i = 0; i <= T; ++i) dp[0][i] = dp[1][i] = inf;
    dp[1][0] = 0;
    for (long long a = 1; a <= S; ++a) {
        for (long long n = 0; n <= N; ++n) {
            for (long long i = 0; i <= T; ++i) spt[n][i][0] = dp[1][i] == inf ? inf : dp[1][i] - n * A[i];
            for (long long j = 1; (1<<j) <= T+1; ++j)
                for (long long i = 0; i + (1<<j) - 1 <= T; ++i)
                    spt[n][i][j] = min(spt[n][i][j-1],spt[n][i+(1<<(j-1))][j-1]);
        }
        dp[0][0] = inf;
        memset(pos,0,sizeof(pos));
        for (long long i = 1; i <= T; ++i) {
            v.clear();
            for (long long j = 1; j <= N; ++j) {
                if (B[j][i] == 0) pos[j] = i;
                v.push_back(pos[j]);
            }
            sort(v.begin(),v.end());
            dp[0][i] = inf;
            if (v[0] != 0) dp[0][i] = query(0,0,v[0]-1);
            for (long long j = 1; j < N; ++j) if (v[j] != v[j-1] && query(j,v[j-1],v[j]-1) != inf) dp[0][i] = min(dp[0][i], query(j,v[j-1],v[j]-1) + j * A[i]);
            if (v[N-1] <= i-1 && query(N,v[N-1],i-1) != inf) dp[0][i] = min(dp[0][i],query(N,v[N-1],i-1) + N * A[i]);
        }
        cout << dp[0][T] << '\n';
        swap(dp[0],dp[1]);
    }

    return 0;
}

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