oj.uz

Submission #52996

# Submission time Handle Problem Language Result Execution time Memory
52996 2018-06-27T13:58:01 Z someone_aa Popeala (CEOI16_popeala) C++17
100 / 100
 1020 ms 22400 KB 
#include <bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int maxt = 21100;
const int maxn = 55;
int dp[maxn][maxt];
int tree[maxn][4*maxt];
int n, t, s;
int pref[maxt], arr[maxt];
int prefans[maxn][maxt];
int maxans[maxt];
int prefmin[maxn][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>>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++) {
        memset(prefmin, -1, sizeof(prefmin));
        for(int j=0;j<=n;j++) {
            int minm = INT_MAX;
            for(int tt=1;tt<=t;tt++) {
                if(dp[i-1][tt-1] == -1) continue;
                minm = min(minm, dp[i-1][tt-1] - j * pref[tt-1]);
                prefmin[j][tt] = minm;
            }
            /*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(prefmin[x][intervals[x][j].second] != -1) {
                    dp[i][j] = min(dp[i][j], prefmin[x][intervals[x][j].second] + 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 9 ms 9464 KB Output is correct
2 Correct 12 ms 9960 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 10292 KB Output is correct
2 Correct 32 ms 10292 KB Output is correct
3 Correct 34 ms 10348 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 11376 KB Output is correct
2 Correct 107 ms 11976 KB Output is correct
3 Correct 144 ms 12692 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9464 KB Output is correct
2 Correct 12 ms 9960 KB Output is correct
3 Correct 33 ms 10292 KB Output is correct
4 Correct 32 ms 10292 KB Output is correct
5 Correct 34 ms 10348 KB Output is correct
6 Correct 80 ms 11376 KB Output is correct
7 Correct 107 ms 11976 KB Output is correct
8 Correct 144 ms 12692 KB Output is correct
9 Correct 283 ms 14156 KB Output is correct
10 Correct 339 ms 15360 KB Output is correct
11 Correct 804 ms 22028 KB Output is correct
12 Correct 1020 ms 22324 KB Output is correct
13 Correct 929 ms 22324 KB Output is correct
14 Correct 882 ms 22400 KB Output is correct
15 Correct 890 ms 22400 KB Output is correct