oj.uz

Submission #52321

# Submission time Handle Problem Language Result Execution time Memory
52321 2018-06-25T11:58:01 Z someone_aa Popeala (CEOI16_popeala) C++17
0 / 100
 2000 ms 9652 KB 
#include <bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int maxt = 10100;
const int maxn = 55;
int dp[maxn][maxt];
int tree[maxn][4*maxt], n, t, s;
int pref[maxt], arr[maxt];
int prefans[maxn][maxt];
int maxans[maxt];

void build(int i, int x, int li=0, int ri=maxt, int index=1) {
    if(li==ri) {
        if(dp[i][li-1] == -1 || dp[i][li] == -1) tree[x][index] = INT_MAX;
        else tree[x][index] = dp[i][li-1] - (pref[li-1]*x);
    }
    else {
        int mid = (li+ri)/2;
        build(i, x, li, mid, 2*index);
        build(i, x, mid+1, ri, 2*index+1);
        tree[x][index] = min(tree[x][2*index], tree[x][2*index+1]);
    }
}

int query(int x, int ql, int qr, int li=0, int ri=maxt, int index=1) {
    if(li > qr || ri < ql) return INT_MAX;
    else if(li >= ql && ri <= qr) return tree[x][index];
    else {
        int mid = (li+ri)/2;
        return min(query(x, ql, qr, li, mid, 2*index), query(x, ql, qr, mid+1, ri, 2*index+1));
    }
}

int f(int i, int j) {
    int cnt = 0;
    for(int k=1;k<=n;k++) {
        if(prefans[k][j] - prefans[k][i-1] == (j-i+1)) cnt++;
    }
    return cnt;
}

pii bin(int i, int x) {
    int index = 1;
    for(int cekor=i;cekor>0;cekor/=2) {
        while(index+cekor<=i && f(index+cekor, i) <= x) index+=cekor;
    }
    int index2 = i;
    for(int cekor=i;cekor>0;cekor/=2) {
        while(index2-cekor>=1 && f(index2-cekor, i) >= x) index2-=cekor;
    }
    if(f(index, i) != x) return mp(-1, -1);
    else return mp(index2,index);

}

int main() {
    cin>>n>>t>>s;
    for(int i=1;i<=t;i++) {
        cin>>arr[i];
        pref[i] = pref[i-1] + arr[i];
    }

    char answ;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=t;j++) {
            cin>>answ;
            prefans[i][j] = prefans[i][j-1];
            if(answ == '1') {
                prefans[i][j]++;
                maxans[j]++;
            }
        }
    }

    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;

    for(int i=1;i<=t;i++) {
        dp[1][i] = pref[i] * f(1, i);
    }

    cout<<dp[1][t]<<"\n";
    for(int i=2;i<=s;i++) {
        for(int j=0;j<=n;j++) {
            build(i-1, j);
            /*cout<<j<<":\n";
            for(int k=1;k<=t;k++) {
                cout<<query(j, k,k)<<" ";
            }cout<<"\n";*/
        }
        //cout<<"Subtask: "<<i<<"\n";
        for(int j=1;j<=t;j++) {
            if(i > j) continue;
            //cout<<j<<":\n";

            dp[i][j] = INT_MAX;
            for(int x=0;x<=maxans[j];x++) {
                pii interval = bin(j, x);
                if(interval.second == -1) continue;
                int temp = query(x, interval.first, interval.second);

                if(temp != INT_MAX) {
                    dp[i][j] = min(dp[i][j], temp + pref[j] * x);
                }
            }
            //cout<<dp[i][j]<<"\n";
        } //cout<<"\n";
        cout<<dp[i][t]+1<<"\n";
    }

    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2900 KB Output isn't correct
2 Halted 0 ms 0 KB -