oj.uz

Submission #52993

# Submission time Handle Problem Language Result Execution time Memory
52993 2018-06-27T13:53:44 Z someone_aa Popeala (CEOI16_popeala) C++17
26 / 100
 265 ms 22636 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];
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 5 ms 4728 KB Output is correct
2 Correct 7 ms 5096 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5548 KB Output is correct
2 Correct 23 ms 5596 KB Output is correct
3 Correct 23 ms 5656 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 6640 KB Output is correct
2 Correct 91 ms 7128 KB Output is correct
3 Correct 124 ms 7856 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4728 KB Output is correct
2 Correct 7 ms 5096 KB Output is correct
3 Correct 24 ms 5548 KB Output is correct
4 Correct 23 ms 5596 KB Output is correct
5 Correct 23 ms 5656 KB Output is correct
6 Correct 68 ms 6640 KB Output is correct
7 Correct 91 ms 7128 KB Output is correct
8 Correct 124 ms 7856 KB Output is correct
9 Correct 197 ms 9320 KB Output is correct
10 Correct 265 ms 10564 KB Output is correct
11 Runtime error 40 ms 22636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -