Educational Codeforces Round 39 (Rated for Div. 2) -- D

D.cpp

/* Copyright 2018 Rafael Rendón Pablo <[email protected]> */
// region Template
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <string>
#include <bitset>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <cctype>
#include <cassert>
#include <cstring>
#include <numeric>
#include <iomanip>
#include <algorithm>

using std::string;
using std::vector;
using std::map;
using std::set;
using std::queue;

typedef long long           int64;
typedef unsigned long long  uint64;
const double kEps   = 10e-8;
const int kMax      = 505;
const int kInf      = 1 << 30;
const int kUndef    = -1;
// endregion

int dp[kMax][kMax];
int sum[kMax];
int best[kMax][kMax];

int f(int n, int k, const int m, const vector<vector<int>>& tt) {
    if (n == 0) {
        return 0;
    }
    int& ans = dp[n][k];
    if (ans != kUndef) {
        return ans;
    }

    ans = kInf;
    for (int x = 0; x <= k; x++) {
        if (best[n-1][x] == kInf) {
            continue;
        }
        ans = std::min(ans, best[n-1][x] + f(n - 1, k - x, m, tt));
    }
    return ans;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, m, k;
    std::cin >> n >> m >> k;
    vector<vector<int>> tt(n);
    for (int i = 0; i < n; i++) {
        string day;
        std::cin >> day;
        for (int j = 0; j < m; j++) {
            if (day[j] == '1') {
                tt[i].push_back(j);
            }
        }
    }
    memset(dp, -1, sizeof dp);
    for (int i = 0; i < n; i++) {
        sum[i] = tt[i].size();
    }

    for (int a = 0; a < n; a++) {
        int size = tt[a].size();
        for (int i = 0; i < kMax; i++) {
            best[a][i] = kInf;
        }
        best[a][size] = 0;
        int leftCount = 0;
        for (int i = 0; i < size; i++) {
            leftCount++;
            int rightCount = 0;
            for (int j = size - 1; j >= i; j--) {
                rightCount++;
                int skipped = leftCount - 1 + rightCount - 1;
                int delta = tt[a][j] - tt[a][i] + 1;
                best[a][skipped] = std::min(best[a][skipped], delta);
            }
        }
    }

    std::cout << f(n, k, m, tt) << std::endl;
    return EXIT_SUCCESS;
}