oj.uz

Submission #349972

# Submission time Handle Problem Language Result Execution time Memory
349972 2021-01-18T19:07:22 Z doowey Popeala (CEOI16_popeala) C++14
0 / 100
 880 ms 2136 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 20010;
const int M = 55;
const ll inf = (ll)1e18;

ll dp[M][N];
ll sum[N];
int cnt[M][N];

int n, t;

ll cost(int li, int ri){
    ll f1 = sum[ri]-sum[li-1];
    ll f2 = 0;
    for(int i = 1; i <= n; i ++ ){
        f2 += (cnt[i][ri]-cnt[i][li-1]==(ri-li+1));
    }
    return f1 * 1ll * f2;
}

void solve(int id, int li, int ri, int optl, int optr){
    if(li>ri)return;
    int mid = (li+ri)/2;
    int opt = optl;
    ll low = inf;
    ll cur;
    for(int j = optl; j < mid ; j ++ ){
        cur = cost(j + 1, mid) + dp[id-1][j];
        if(cur < low){
            low = cur;
            opt = j;
        }
    }
    dp[id][mid]=low;
    solve(id,li,mid-1,optl,opt);
    solve(id,mid+1,ri,opt,optr);
}

int main(){
    fastIO;
    //freopen("in.txt","r",stdin);
    int s;
    cin >> n >> t >> s;
    for(int i = 0 ; i <= s; i ++ ){
        for(int j =0; j <= t; j ++ ){
            dp[i][j]=inf;
        }
    }
    dp[0][0]=0;
    for(int i = 1; i <= t; i ++ ){
        cin >> sum[i];
        sum[i] += sum[i - 1];
    }
    char q;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= t; j ++ ){
            cin >> q;
            cnt[i][j]=q-'0';
            cnt[i][j]+=cnt[i][j-1];
        }
    }
    for(int i = 1; i <= s; i ++ ){
        solve(i,i,t,i-1,t);
        cout << dp[i][t] << "\n";
    }
    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 620 KB Output isn't correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 1144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 880 ms 2136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 620 KB Output isn't correct