Cod sursa(job #2162813)

Utilizator cella.florescuCella Florescu cella.florescu Data 12 martie 2018 14:27:32
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 500;

char les[MAXN + 1][MAXN + 4];

int dp[MAXN + 2][MAXN + 2], aux[MAXN + 2][MAXN + 2], nb[MAXN + 2];
vector <int> v[MAXN + 2];

int main() {
//    ifstream cin(".in");
//    ofstream cout(".out");
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i) {
      cin >> (les[i] + 1);
      for (int j = 1; j <= m; ++j) {
        nb[i] += les[i][j] - '0';
        if (les[i][j] == '1')
          v[i].push_back(j);
      }
    }
    memset(aux, 0x3f, sizeof aux);
    for (int i = 1; i <= n; ++i) {
      aux[i][nb[i]] = 0;
      for (int j = nb[i] - 1; j >= 0; --j) {
        int num = nb[i] - j;
        int loc = INT_MAX;
        for (int p = num - 1; p < (int) v[i].size(); ++p)
          loc = min(loc, v[i][p] - v[i][p - num + 1] + 1);
        aux[i][j] = loc;
      }
      for (int j = nb[i] + 1; j <= k; ++j)
        aux[i][j] = 0;
    }
    memset(dp, 0x3f, sizeof dp);
    for (int i = 0; i <= k; ++i)
      dp[1][i] = aux[1][i];
    for (int i = 2; i <= n; ++i)
      for (int j = 0; j <= k; ++j) {
        for (int num = 0; num <= k && num <= nb[i]; ++num)
          dp[i][j] = min(dp[i][j], dp[i - 1][k - num] + aux[i][num]);
      }
    for (int i = 0; i < k; ++i)
      dp[n][k] = min(dp[n][k], dp[n][i]);
    cout << dp[n][k];
    return 0;
}