946D - Timetable - CodeForces Solution

#include <bits/stdc++.h>
#include <chrono>
#define ll long long
#define ld long double
#define fe first
#define se second
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int maxn=100000+2;
ll mod=998244353;


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m,l;
    cin>>n>>m>>l;
    string s[n];
    for(int i=0;i<n;i++)cin>>s[i];

    int dp[n][m+1];
    for(int i=0;i<n;i++)for(int j=0;j<=m;j++)dp[i][j]=1e7;

    for(int i=0;i<n;i++){
        int cnt1 = 0;
        for(int j=0;j<m;j++){
            if(s[i][j] == '0')continue;
            int cnt2 = 0;
            for(int k = m-1;k>j;k--){
                if(s[i][k] == '0')continue;
                dp[i][cnt1 + cnt2] = min(dp[i][cnt1+cnt2],(k-j+1));
                cnt2++;
            }
            cnt1++;
        }
        dp[i][cnt1] = 0;
        if(cnt1 > 0)dp[i][cnt1 - 1] = 1;
    }

    vector<int>ve(l+1,-1);
    ve[0] = 0;

    for(int i=0;i<n;i++){
        vector<int>temp(l+1,-1);
        for(int j=l;j>=0;j--){
            for(int k=0;k<=m;k++){
                if(dp[i][k] != 1e7 && j-k >= 0)temp[j] = (temp[j] == -1 ? ve[j-k] + dp[i][k] : min(temp[j],ve[j-k] + dp[i][k]));
            }
        }
        swap(ve,temp);
    }
    
    int ans = 1e7;
    for(int i=0;i<=l;i++)if(ve[i] != -1)ans = min(ans,ve[i]);
    cout<<ans;
}