oj.uz

Submission #52958

# Submission time Handle Problem Language Result Execution time Memory
52958 2018-06-27T08:56:38 Z 노영훈(#1382) Popeala (CEOI16_popeala) C++11
26 / 100
 1445 ms 47788 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=4010, inf=2e9+10;

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

inline int _min(int x, int y){
    return x<y ? x : y;
}

void init(){
    for(int i=0; i<=s; i++)
        for(int j=0; j<=t; j++)
            D[i][j]=inf;

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

    int S[MX]={};
    for(int i=1; i<=t; i++) S[i]=S[i-1]+P[i];
    for(int l=1; l<=t; l++){
        bool B[51];
        for(int i=1; i<=n; i++) B[i]=true;
        for(int r=l; r<=t; r++){
            int sum=S[r]-S[l-1];
            for(int i=1; i<=n; i++)
                B[i]&=R[i][r], score[l][r]+=(B[i]?sum:0);
        }
    }
}

ll d(int k, int r){
    ll &res=D[k][r];
    if(res>=0) return res;
    res=inf;
    for(int x=r; x>=1; x--){
        ll now=d(k-1, x-1) + score[x][r];
        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');
        }
    
    init();

    for(int k=0; k<=s; k++){
        for(int r=0; r<=t; r++){
            for(int x=r+1; x<=t; x++)
                D[k+1][x]=_min(D[k+1][x], D[k][r]+score[r+1][x]);
        }
    }

    for(int i=1; i<=s; i++)
        cout<<D[i][t]<<'\n';
/*
    for(int i=0; i<=s; i++, cout<<'\n')
        for(int j=0; j<=t; j++)
            cout<<d(i,j)<<' ';

    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 872 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3516 KB Output is correct
2 Correct 28 ms 3564 KB Output is correct
3 Correct 28 ms 3596 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 20052 KB Output is correct
2 Correct 852 ms 31924 KB Output is correct
3 Correct 1445 ms 47788 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 872 KB Output is correct
3 Correct 28 ms 3516 KB Output is correct
4 Correct 28 ms 3564 KB Output is correct
5 Correct 28 ms 3596 KB Output is correct
6 Correct 414 ms 20052 KB Output is correct
7 Correct 852 ms 31924 KB Output is correct
8 Correct 1445 ms 47788 KB Output is correct
9 Runtime error 10 ms 47788 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -