The problem can be found here

My Thought Process

The first thing we should do is probably to find the maximum number of squares we can take with the path. Starting at the top left corner and moving down seems to be the most optimal way. If starting at another cell in the top leads to the optimal results, we can just create a path from the top left to that cell. None of the cells in this path should be a fountain since if that cell is optimal, it wouldn’t contain a fountain in the region.

Now, how do we move to the general bottom right area and obtain the maximum number of cells. Well, in the first column, if there are no fountains, we can take all of the cells. If there is a fountain though at a cell with row $x$, we need to start at $n - x - 1$ so we don’t take the fountain. What about the next column? We can go to the rows from $n-x-1$ to $n$ but we get more cells if we go to a row closer to $n-x-1$. That means that everytime we go to a new column, we want to go directly right or go to the fountain furthest down (as shown in the image in the problem) and down one more so we don;t touch it.

Implementation

#include <bits/stdc++.h>

using ll = long long;
#define pb push_back

using namespace std;

const int MOD = 1e9+7;
const int MAXN = 2e6+1;

#define int long long

void solve() { 
    int n, m, k; cin >> n >> m >> k;
    vector<pair<int, int>> v;
    vector<pair<int, int>> a;
    for(int i = 0; i < k; ++i){
        int x, y; cin >> x >> y;
        a.pb({x, y});
        v.pb({y, x});
    }

    sort(v.begin(), v.end());

    int maxn = 0;
    int ans = 0;
    int minn = n;

    for(int i = 0; i < k; ++i){
        int y = v[i].first;
        int x = v[i].second;
        if(i == 0){
            maxn = x; 
            ans += (y - 1) * n;
            continue;
        }   

        if(y != v[i-1].first){
            minn = min(minn, (n - maxn));
            ans += minn * (v[i].first - v[i-1].first);
            maxn = 0;
        }

        maxn = max(maxn, x);
    }

    minn = min(minn, (n - maxn));
    ans += min(minn, (n - maxn));
    ans += (m - v[k-1].first) * minn;

    map<pair<int, int>, int> res;

    v.pb({2e9, -1});
    maxn = 0;
    for(int i = 0; i < k; ++i){
        if(v[i].first != v[i+1].first && v[i].second > maxn){
            res[{v[i].second, v[i].first}] = 1;
        }
        else{
            res[{v[i].second, v[i].first}] = 0;
        }
        maxn = max(maxn, v[i].second);
    }

    cout << ans << endl;

    for(auto i : a){
        cout << res[i] << ' ';
    }

    cout << endl;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    int t;
    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

Final Thoughts

See here for the solution and another implementation.