Submission #1109588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109588		soab	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	0 / 100	4 ms	20816 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;
 
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
 
int dp[503][503][503][3], onePos[503];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int n, k; cin >> n >> k;
    string s; cin >> s;
    s = " " + s;
 
    /// pre-calculations
    int zeroCount = 0, oneCount = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '1') onePos[++oneCount] = i;
        else zeroCount++;
    }
 
    /// setup base-cases
    for (int diff = 0; diff <= n; diff++)
        for (int i = 0; i <= zeroCount; i++)
            for (int j = 0; j <= oneCount; j++)
                for (int last = 0; last < 2; last++) dp[diff][i][j][last] = INT_MAX;
    dp[0][0][0][0] = dp[0][0][0][1] = 0;
 
    /// run DP
    for (int diff = 1; diff <= n; diff++) {
        for (int zCur = 0; zCur <= zeroCount; zCur++) {
            for (int oCur = 0; oCur <= oneCount; oCur++) {
                if (!zCur && !oCur) continue;
                // calculate dp[diff][zCur][oCur][1]
                if (oCur) {
                    int oldPos = onePos[oCur], newPos = zCur + oCur, cost = abs(oldPos - newPos);
                    if (diff) { // place a '0' before it
                        int recur = dp[diff - 1][zCur][oCur - 1][0];
                        if (recur != INT_MAX)
                            dp[diff][zCur][oCur][1] = min(dp[diff][zCur][oCur][1], recur + cost);
                    }
                    if (true) { // place a '1' before it
                        int recur = dp[diff][zCur][oCur - 1][1];
                        if (recur != INT_MAX)
                            dp[diff][zCur][oCur][1] = min(dp[diff][zCur][oCur][1], recur + cost);
                    }
                }
 
                // calculate dp[diff][zCur][oCur][0]
                if (zCur) {
                    if (diff) { // place a '1' before it
                        dp[diff][zCur][oCur][0] = min(dp[diff][zCur][oCur][0], dp[diff - 1][zCur - 1][oCur][1]);
                    }
                    if (true) { // place a '0' before it
                        dp[diff][zCur][oCur][0] = min(dp[diff][zCur][oCur][0], dp[diff][zCur - 1][oCur][0]);
                    }
                }
            }
        }
    }
 
    int ans = 0;
    for (int diff = 2; diff <= n; diff++) {
        //cout << diff << " " << dp[diff][zeroCount][oneCount][0] << " " << dp[diff][zeroCount][oneCount][1] << "\n";
        if (min(dp[diff][zeroCount][oneCount][0], dp[diff][zeroCount][oneCount][1]) <= k) ans = diff - 1;
    }
    cout << ans;
 
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 55
• Subtask 3: 0 / 15
• Subtask 4: 0 / 25