oj.uz

Submission #1032707

# Submission time Handle Problem Language Result Execution time Memory
1032707 2024-07-24T06:34:42 Z 변재우(#10969) Popeala (CEOI16_popeala) C++17
26 / 100
 2000 ms 8792 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int Kmax=55, Nmax=20010, INF=1e18;
int N, T, S, A[Nmax], D[Kmax][Nmax];
int R[Nmax];

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>T>>S;
    for(int i=1; i<=T; i++) cin>>A[i], A[i]+=A[i-1];
    for(int i=1; i<=N; i++) {
        string s; cin>>s;
        for(int j=1; j<=T; j++) if(s[j-1]=='1') R[j]+=(1ll<<(i-1));
    }
    for(int i=0; i<=S; i++) for(int j=0; j<=T; j++) D[i][j]=INF;
    D[0][0]=0;
    for(int i=1; i<=S; i++) {
        for(int j=1; j<=T; j++) {
            int P=(1ll<<N)-1;
            for(int k=j; k>=1; k--) {
                P&=R[k];
                D[i][j]=min(D[i][j], D[i-1][k-1]+(A[j]-A[k-1])*__builtin_popcountll(P));
            }
        }
    }
    for(int i=1; i<=S; i++) cout<<D[i][T]<<"\n";
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8540 KB Output is correct
2 Correct 18 ms 8540 KB Output is correct
3 Correct 18 ms 8692 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 8716 KB Output is correct
2 Correct 604 ms 8736 KB Output is correct
3 Correct 1109 ms 8788 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 18 ms 8540 KB Output is correct
4 Correct 18 ms 8540 KB Output is correct
5 Correct 18 ms 8692 KB Output is correct
6 Correct 345 ms 8716 KB Output is correct
7 Correct 604 ms 8736 KB Output is correct
8 Correct 1109 ms 8788 KB Output is correct
9 Execution timed out 2019 ms 8792 KB Time limit exceeded
10 Halted 0 ms 0 KB -