oj.uz

Submission #53015

# Submission time Handle Problem Language Result Execution time Memory
53015 2018-06-27T17:31:09 Z someone_aa Popeala (CEOI16_popeala) C++17
100 / 100
 838 ms 22476 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;
}

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++;
            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 9464 KB Output is correct
2 Correct 12 ms 9892 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 10276 KB Output is correct
2 Correct 33 ms 10276 KB Output is correct
3 Correct 31 ms 10320 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 11396 KB Output is correct
2 Correct 88 ms 11824 KB Output is correct
3 Correct 113 ms 12536 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 9892 KB Output is correct
3 Correct 45 ms 10276 KB Output is correct
4 Correct 33 ms 10276 KB Output is correct
5 Correct 31 ms 10320 KB Output is correct
6 Correct 95 ms 11396 KB Output is correct
7 Correct 88 ms 11824 KB Output is correct
8 Correct 113 ms 12536 KB Output is correct
9 Correct 220 ms 14012 KB Output is correct
10 Correct 309 ms 15292 KB Output is correct
11 Correct 746 ms 21820 KB Output is correct
12 Correct 803 ms 22460 KB Output is correct
13 Correct 838 ms 22460 KB Output is correct
14 Correct 726 ms 22476 KB Output is correct
15 Correct 770 ms 22476 KB Output is correct