oj.uz

답안 #1032698

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1032698 2024-07-24T06:30:29 Z 변재우(#10969) 조교 (CEOI16_popeala) C++17
26 / 100
 2000 ms 9064 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];
bitset<Kmax> 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][i]=true;
    }
    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++) {
            bitset<Kmax> P;
            for(int j=1; j<=N; j++) P[j]=true;
            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])*(int)P.count());
            }
        }
    }
    for(int i=1; i<=S; i++) cout<<D[i][T]<<"\n";
    return 0;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 8700 KB Output is correct
2 Correct 19 ms 8536 KB Output is correct
3 Correct 19 ms 8536 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 358 ms 8540 KB Output is correct
2 Correct 549 ms 8796 KB Output is correct
3 Correct 1076 ms 8968 KB Output is correct

Subtask #4
0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 19 ms 8700 KB Output is correct
4 Correct 19 ms 8536 KB Output is correct
5 Correct 19 ms 8536 KB Output is correct
6 Correct 358 ms 8540 KB Output is correct
7 Correct 549 ms 8796 KB Output is correct
8 Correct 1076 ms 8968 KB Output is correct
9 Execution timed out 2070 ms 9064 KB Time limit exceeded
10 Halted 0 ms 0 KB -