oj.uz

Submission #537045

# Submission time Handle Problem Language Result Execution time Memory
537045 2022-03-14T10:07:33 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;

inline long long rd() {
    long long x = 0;
    char ch = getchar_unlocked();
    while (ch < '0' || ch > '9') ch = getchar_unlocked();
    while (ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar_unlocked();
	}
    return x;
}

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() {
    N = rd(), T = rd(), S = rd();
    A[0] = 0;
    for (long long i = 1; i <= T; ++i) {
        A[i] = rd();
        A[i] += A[i-1];
    }
    for (long long i = 1; i <= N; ++i) for (long long j = 1; j <= T; ++j) {
        char ch = getchar_unlocked();
        while (ch != '0' && ch != '1') ch = getchar_unlocked();
        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]);
        }
        printf("%lld\n", dp[0][T]);
        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 3 ms 1236 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 5432 KB Output is correct
2 Correct 67 ms 5240 KB Output is correct
3 Correct 108 ms 5332 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 18920 KB Output is correct
2 Correct 717 ms 26460 KB Output is correct
3 Correct 917 ms 34772 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 3 ms 1236 KB Output is correct
3 Correct 72 ms 5432 KB Output is correct
4 Correct 67 ms 5240 KB Output is correct
5 Correct 108 ms 5332 KB Output is correct
6 Correct 463 ms 18920 KB Output is correct
7 Correct 717 ms 26460 KB Output is correct
8 Correct 917 ms 34772 KB Output is correct
9 Correct 1408 ms 55708 KB Output is correct
10 Correct 1983 ms 72528 KB Output is correct
11 Execution timed out 2095 ms 161740 KB Time limit exceeded
12 Halted 0 ms 0 KB -