p01887 Pipe Fitter and the Fierce Dogs_28806
Example

Input

5 5 4
6
3 2
4 2
5 2
1 4
3 4
5 4


Output

6
#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9;

int main() {
    int w, h, k; cin >> w >> h >> k;
    int n; cin >> n;
    vector<vector<int>> cost(w, vector<int>(h / 2, 1));
    for(int i = 0; i < n; ++i) {
        int x, y; cin >> x >> y;
        x--, y--;
        if(y % 2 == 0) continue;
        cost[x][y / 2] = 2;
    }

    k -= (w + 1) / 2;
    if(k < 0) {
        cout << -1 << endl;
        return 0;
    }

    const int hz = (h - 1) / 2, wz = (w + 1) / 2;
    vector<vector<int>> dp(wz + 1, vector<int>(2, inf));
    dp[0][0] = 0;
    for(int y = 0; y < hz; ++y) {
        for(int x = 0; x < wz; ++x) {
            if(dp[x][0] != inf) {
                dp[x + 1][0] = min(dp[x + 1][0], dp[x][0] + cost[x * 2][y]);
                if(x != wz - 1) {
                    dp[x + 1][1] = min(dp[x + 1][1], dp[x][0] + cost[x * 2 + 1][y]);
                }
            }
            if(dp[x][1] != inf) {
                dp[x + 1][0] = min(dp[x + 1][0], dp[x][1] + cost[x * 2 - 1][y]);
            }
        }
        const int ns = dp[wz][0];
        for(int x = 0; x <= wz; ++x) {
            for(int S = 0; S < 2; ++S) {
                dp[x][S] = inf;
            }
        }
        dp[0][0] = ns;
    }

    int ans = dp[0][0];
    const int tcnt = min(k, ans - hz * wz);
    const int ocnt = max(0, k - tcnt);
    ans = max(0, ans - tcnt * 2 - ocnt);
    cout << ans << endl;
}


5 5 4
6
3 2
4 2
5 2
1 4
3 4
5 4 9 5 4
6
3 2
4 2
5 2
1 4
3 4
5 4 9 5 5
6
3 2
4 2
5 2
1 4
3 4
5 4 9 5 10
6
3 1
4 2
5 2
1 4
3 4
7 4 9 5 6
6
3 2
4 4
6 1
2 5
3 4
5 4 9 7 5
6
3 2
7 4
6 1
2 7
3 4
5 4 9 5 9
6
3 2
4 2
5 2
1 4
3 4
5 5 11 5 6
0
10 1
3 0
10 4
0 0
5 4
0 5 9 5 12
2
3 2
4 4
6 1
2 1
3 4
4 4 9 5 7
5
3 2
4 4
5 2
2 5
3 4
5 4 5 9 4
6
3 2
4 4
10 1
2 5
3 6
5 7 6 5 12
2
3 2
4 4
6 1
2 1
3 2
4 4 9 5 5
6
3 2
4 2
5 2
1 4
3 4
7 4 9 5 5
6
3 1
4 2
5 2
1 4
3 4
7 4 9 5 4
6
3 2
4 4
5 2
1 4
3 4
5 4 9 5 5
6
3 2
4 2
5 2
1 4
3 4
5 5 9 5 5
6
3 2
4 2
9 2
1 4
3 4
7 4 9 5 4
6
3 2
4 4
5 2
1 5
3 4
5 4 9 5 4
6
3 2
4 4
5 2
2 5
3 4
5 4 9 5 4
6
3 2
4 4
5 1
2 5
3 4
5 4 9 5 4
6
3 2
4 4
6 1
2 5
3 4
5 4 9 5 4
6
3 2
4 4
6 1
2 7
3 4
5 4 9 7 4
6
3 2
4 4
6 1
2 7
3 4
5 4 9 7 4
6
3 2
7 4
6 1
2 7
3 4
5 4 9 7 4
6
3 2
7 4
6 1
2 7
6 4
5 4 9 7 4
6
3 1
7 4
6 1
2 7
6 4
5 4 9 7 4
6
3 1
7 4
6 1
2 7
6 2
5 4 9 7 4
6
3 1
7 4
6 1
0 7
6 2
5 4 9 7 4
6
2 1
7 4
6 1
0 7
6 2
5 4 9 6 4
6
2 1
7 4
6 1
0 7
6 2
5 4 9 6 4
6
4 1
7 4
6 1
0 7
6 2
5 4 9 5 4
6
3 2
6 2
5 2
1 4
3 4
5 4 9 5 4
6
3 2
4 4
5 2
1 4
3 4
5 1 9 5 5
6
3 2
4 2
5 2
1 4
3 4
5 1 9 10 4
6
3 2
4 4
5 2
1 5
3 4
5 4 9 5 4
6
3 2
4 4
5 1
2 5
3 6
5 4 16 7 4
6
3 2
7 4
6 1
2 7
6 4
5 4 9 7 4
6
3 1
3 4
6 1
2 7
6 2
5 4 9 7 4
6
2 1
7 4
6 1
0 7
6 2
2 4 9 6 4
6
2 1
7 4
6 1
0 7
6 2
4 4 9 6 4
6
4 1
7 4
6 1
0 7
6 2
5 7 9 5 4
6
3 2
6 2
5 2
1 4
3 4
9 4 9 5 4
6
3 2
4 4
2 2
1 4
3 4
5 1 9 5 4
6
3 2
4 4
5 1
2 5
5 6
5 4 9 5 6
2
3 2
4 4
6 1
2 5
3 4
5 4 9 7 5
6
6 2
7 4
6 1
2 7
3 4
5 4 16 7 4
6
3 2
7 4
1 1
2 7
6 4
5 4 12 7 4
6
3 1
3 4
6 1
2 7
6 2
5 4 9 7 4
6
2 1
7 2
6 1
0 7
6 2
2 4 9 6 4
6
2 1
7 4
12 1
0 7
6 2
4 4 9 6 4
6
4 1
7 4
6 1
0 7
6 2
8 7 9 7 4
6
3 2
6 2
5 2
1 4
3 4
9 4 9 10 4
6
3 2
4 4
2 2
1 4
3 4
5 1 9 5 4
6
3 2
4 4
2 1
2 5
5 6
5 4 9 5 6
2
3 2
4 4
6 1
2 1
3 4
5 4 16 7 4
6
3 2
7 4
0 1
2 7
6 4
5 4 12 7 4
6
3 1
3 4
9 1
2 7
6 2
5 4 9 6 4
6
4 1
7 7
6 1
0 7
6 2
8 7 9 7 4
6
3 2
6 2
5 2
1 4
1 4
9 4 9 10 4
6
3 2
4 4
2 3
1 4
3 4
5 1 9 5 4
6
3 2
4 4
1 1
2 5
5 6
5 4 9 5 6
2
3 2
4 4
9 1
2 1
3 4
5 4 16 7 4
6
3 2
7 4
0 1
2 5
6 4
5 4 12 3 4
6
3 1
3 4
9 1
2 7
6 2
5 4 9 4 4
6
4 1
7 7
6 1
0 7
6 2
8 7 9 10 4
6
3 2
4 5
2 3
1 4
3 4
5 1 9 5 4
2
3 2
4 4
9 1
2 1
3 4
5 4 12 3 4
6
3 1
3 4
9 1
2 7
6 2
5 2 9 4 4
6
4 1
5 7
6 1
0 7
6 2
8 7 9 10 4
6
3 2
4 5
0 3
1 4
3 4
5 1 9 5 4
2
3 2
4 4
9 1
0 1
3 4
5 4 12 3 0
6
3 1
3 4
9 1
2 7
6 2
5 2 9 4 4
6
4 1
5 7
9 1
0 7
6 2
8 7 9 10 4
6
3 2
4 5
0 3
1 4
3 6
5 1 9 5 4
2
3 2
3 4
9 1
0 1
3 4
5 4 12 3 0
6
3 1
3 4
9 1
2 7
6 2
5 3 9 6 4
6
4 1
5 7
9 1
0 7
6 2
8 7 9 5 4
2
3 2
3 2
9 1
0 1
3 4
5 4 12 3 0
6
3 1
3 4
9 1
2 7
6 2
10 3 9 5 4
2
3 3
3 2
9 1
0 1
3 4
5 4 12 3 0
6
3 1
2 4
9 1
2 7
6 2
10 3 9 5 4
2
3 3
3 2
9 1
0 1
3 4
9 4 9 5 4
2
3 3
3 2
9 1
0 1
3 4
10 4 9 5 4
2
3 3
3 2
9 1
0 1
3 4
0 4 9 5 4
2
3 3
3 2
10 1
0 1
3 4
0 4 9 5 4
2
3 3
3 2
10 1
0 1
5 4
0 4 11 5 4
2
3 3
3 2
10 1
0 1
5 4
0 4 11 5 4
2
3 3
3 2
10 2
0 1
5 4
0 4 11 5 4
2
5 3
3 2
10 2
0 1
5 4
0 4 11 5 4
2
5 1
3 2
10 2
0 1
5 4
0 4 11 5 4
0
5 1
3 2
10 2
0 1
5 4
0 4 11 5 4
0
10 1
3 2
10 2
0 1
5 4
0 4 11 5 4
0
10 1
3 2
10 2
0 0
5 4
0 4 11 5 4
0
10 1
3 2
10 2
0 0
5 4
0 5 11 5 4
0
10 1
3 0
10 2
0 0
5 4
0 5 11 5 4
0
10 1
3 0
10 4
0 0
5 4
0 5 11 5 4
0
10 1
3 0
10 4
0 0
5 4
0 8 11 5 4
0
10 0
3 0
10 4
0 0
5 4
0 8 11 5 4
0
10 0
3 0
10 4
0 0
5 4
0 7 11 8 4
0
10 0
3 0
10 4
0 0
5 4
0 7 11 8 1
0
10 0
3 0
10 4
0 0
5 4
0 7
6 -1
 10
 5
 9
 15
 6
 12
 3
 8
 11
 0
 10
 10
 -1
 10
 10
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 10
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 9
 15
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 9
 -1
 -1
 -1
 -1
 -1
 -1
 9
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
