oj.uz

Submission #52997

# Submission time Handle Problem Language Result Execution time Memory
52997 2018-06-27T13:59:28 Z someone_aa Popeala (CEOI16_popeala) C++17
100 / 100
 1124 ms 22364 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 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];


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;
            }
        }
        for(int j=1;j<=t;j++) {
            if(i > j) continue;
            dp[i][j] = INT_MAX;
            for(int x=0;x<=maxans[j];x++) {
                if(prefmin[x][intervals[x][j].second] != -1) {
                    dp[i][j] = min(dp[i][j], prefmin[x][intervals[x][j].second] + pref[j] * x);
                }
            }
        }
    }

    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 9468 KB Output is correct
2 Correct 12 ms 9700 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 10376 KB Output is correct
2 Correct 38 ms 10376 KB Output is correct
3 Correct 36 ms 10376 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 11228 KB Output is correct
2 Correct 113 ms 11796 KB Output is correct
3 Correct 145 ms 12384 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9468 KB Output is correct
2 Correct 12 ms 9700 KB Output is correct
3 Correct 35 ms 10376 KB Output is correct
4 Correct 38 ms 10376 KB Output is correct
5 Correct 36 ms 10376 KB Output is correct
6 Correct 114 ms 11228 KB Output is correct
7 Correct 113 ms 11796 KB Output is correct
8 Correct 145 ms 12384 KB Output is correct
9 Correct 437 ms 14152 KB Output is correct
10 Correct 353 ms 15112 KB Output is correct
11 Correct 1062 ms 21724 KB Output is correct
12 Correct 1063 ms 22316 KB Output is correct
13 Correct 1016 ms 22316 KB Output is correct
14 Correct 1124 ms 22364 KB Output is correct
15 Correct 1006 ms 22364 KB Output is correct