oj.uz

Submission #537027

# Submission time Handle Problem Language Result Execution time Memory
537027 2022-03-14T09:48:16 Z joelau Popeala (CEOI16_popeala) C++14
26 / 100
 2000 ms 161740 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 5460 KB Output is correct
2 Correct 64 ms 5204 KB Output is correct
3 Correct 69 ms 5504 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 18944 KB Output is correct
2 Correct 669 ms 26404 KB Output is correct
3 Correct 866 ms 34784 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 73 ms 5460 KB Output is correct
4 Correct 64 ms 5204 KB Output is correct
5 Correct 69 ms 5504 KB Output is correct
6 Correct 472 ms 18944 KB Output is correct
7 Correct 669 ms 26404 KB Output is correct
8 Correct 866 ms 34784 KB Output is correct
9 Correct 1347 ms 55732 KB Output is correct
10 Correct 1971 ms 72476 KB Output is correct
11 Execution timed out 2081 ms 161740 KB Time limit exceeded
12 Halted 0 ms 0 KB -