oj.uz

Submission #52991

# Submission time Handle Problem Language Result Execution time Memory
52991 2018-06-27T13:44:20 Z someone_aa Popeala (CEOI16_popeala) C++17
17 / 100
 2000 ms 12384 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];

pair<int, int> intervals[55][maxt];

void build(int i, int x, int li=1, int ri=maxt+1, 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=1, int ri=maxt+1, 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() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    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]++;
            }
        }
    }

    for(int i=0;i<=n;i++) {
        int li=1, ri=1;

        for(int j=1;j<=t;j++) {
            while(ri < j && f(ri+1, j) <= i) ri++;
            while(li < ri && f(li+1, j) < i) li++;

            if(i == 0) intervals[i][j] = make_pair(1, ri);
            else intervals[i][j] = make_pair(li+1, ri);

        }
    }

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

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

    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++) {
                int temp = query(x, intervals[x][j].first, intervals[x][j].second);

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

    for(int i=1;i<=s;i++) {
        cout<<dp[i][t]<<"\n";
    }

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2936 KB Output is correct
2 Correct 57 ms 7780 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 10136 KB Output is correct
2 Correct 425 ms 10136 KB Output is correct
3 Correct 498 ms 10212 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 962 ms 10948 KB Output is correct
2 Correct 1284 ms 11772 KB Output is correct
3 Execution timed out 2020 ms 12384 KB Time limit exceeded

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2936 KB Output is correct
2 Correct 57 ms 7780 KB Output is correct
3 Correct 430 ms 10136 KB Output is correct
4 Correct 425 ms 10136 KB Output is correct
5 Correct 498 ms 10212 KB Output is correct
6 Correct 962 ms 10948 KB Output is correct
7 Correct 1284 ms 11772 KB Output is correct
8 Execution timed out 2020 ms 12384 KB Time limit exceeded