oj.uz

Submission #1109588

# Submission time Handle Problem Language Result Execution time Memory
1109588 2024-11-07T06:31:30 Z soab Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 4 ms 20816 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 6480 KB Output is correct
4 Incorrect 4 ms 20816 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 6480 KB Output is correct
4 Incorrect 4 ms 20816 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 6480 KB Output is correct
4 Incorrect 4 ms 20816 KB Output isn't correct
5 Halted 0 ms 0 KB -