oj.uz

Submission #52830

# Submission time Handle Problem Language Result Execution time Memory
52830 2018-06-27T04:32:58 Z 노영훈(#1382) Popeala (CEOI16_popeala) C++11
17 / 100
 2000 ms 1884 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=20010, inf=2e9+10;

int n, t, s;
int P[MX];
bool R[51][MX];
ll D[51][MX];

/*
void solve(int idx, int s, int e, int l, int r){
    if(s>e) return;
    int m=(s+e)/2, pos=l;
    ll &d=D[idx][m]; d=inf;

    int sum=0; bool B[51];
    for(int i=1; i<=n; i++) B[i]=true;

    for(int x=m; x>r; x--){
        sum+=P[x];
        for(int i=1; i<=n; i++) B[i]&=R[i][x];
    }

    for(int x=min(r,m-1); x>=l; x--){
        sum+=P[x];
        int cnt=0;
        for(int i=1; i<=n; i++) B[i]&=R[i][x], cnt+=B[i];
        ll now=D[idx-1][x-1] + cnt * sum;
        if(now<d) now=d, pos=x;
    }

    solve(idx, s, m-1, l, pos);
    solve(idx, m+1, e, pos, r);
}
*/

ll d(int k, int r){
    ll &res=D[k][r];
    if(res>=0) return res;
    res=inf;
    bool B[51]; int sum=0;
    fill(B, B+n+1, true);
    for(int x=r; x>=1; x--){
        sum+=P[x];
        int cnt=0;
        for(int i=1; i<=n; i++) B[i]&=R[i][x], cnt+=B[i];
        ll now=d(k-1, x-1) + cnt * sum;
        if(now<res) res=now;
    }
    return res;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>t>>s;
    for(int i=1; i<=t; i++)
        cin>>P[i];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=t; j++){
            char c; cin>>c;
            R[i][j]=(c=='1');
        }

    for(int i=0; i<=s; i++)
        for(int j=0; j<=t; j++)
            D[i][j]=-1;

    for(int i=1; i<=t; i++)
        D[0][i]=inf;
    D[0][0]=0;
    /*
    for(int i=1; i<=s; i++){
        solve(i,1,t,1,t);
    }
    
    for(int i=1; i<=s; i++)
        cout<<D[i][t]<<'\n';
    */
    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 3 ms 376 KB Output is correct
2 Correct 3 ms 616 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 1068 KB Output is correct
2 Correct 512 ms 1116 KB Output is correct
3 Correct 484 ms 1244 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2064 ms 1884 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 616 KB Output is correct
3 Correct 452 ms 1068 KB Output is correct
4 Correct 512 ms 1116 KB Output is correct
5 Correct 484 ms 1244 KB Output is correct
6 Execution timed out 2064 ms 1884 KB Time limit exceeded
7 Halted 0 ms 0 KB -