Submission #2412768

---

Source Code Expand

#include <bits/stdc++.h>

// #define DEBUG
#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define debug(x) cerr << #x << ": " << x << endl

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;
struct edge{int from, to; ll cost;};

int H, W, h, w;

int count_use(int i, int j){
    return min(i+1, H-i) * min(j+1, W-j);
}

int main() {
    std::ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> H >> W >> h >> w;

    ll ans[H][W];
    fill(ans[0], ans[H], LLONG_MAX);

    int use_cnt[H][W], max_cnt = 0;
    repp(i, H) repp(j, W){
        use_cnt[i][j] = count_use(i, j);
        max_cnt = max(max_cnt, use_cnt[i][j]);
    }

    ll total_part = 0LL;
    repp(i, H-h+1){
        repp(j, W-w+1){
            int most_used_cnt = -1;
            Pii most_used;
            vector<int> vdi, vdj;
            if(i == 0){
                vdi.resize(h);
                repp(ii, h) vdi[ii] = ii;
            }else{
                vdi.push_back(h-1);
            }
            if(j == 0){
                vdj.resize(w);
                repp(jj, w) vdj[jj] = jj;
            }else{
                vdj.push_back(w-1);
            }
            if(j) repp(di, h) total_part -= ans[i+di][j-1];
            if(i) repp(dj, w) total_part -= ans[i-1][j+dj];
            for(int di: vdi){
                for(int dj: vdj){
                    int cnt = use_cnt[i+di][j+dj];
                    if(cnt >= most_used_cnt){
                        most_used_cnt = cnt;
                        most_used = make_pair(i+di, j+dj);
                    }
                    ans[i+di][j+dj] = max_cnt - use_cnt[i+di][j+dj];
                    total_part += ans[i+di][j+dj];
                }
            }
            if(total_part >= 0){
                ll tmp = total_part+1;
                total_part -= ans[most_used.first][most_used.second];
                ans[most_used.first][most_used.second] = -tmp;
                total_part += ans[most_used.first][most_used.second];
                
            }
        }
    }

    ll total_all = 0LL;
    rep(H)repp(j, W) total_all += ans[i][j];

    if(total_all > 0LL){
        cout << "Yes" << endl;
        rep(H){
            repp(j, W) cout << ans[i][j] << " ";
            cout << endl;
        }
    }else{
        cout << "No" << endl;
        #ifdef DEBUG
        rep(H){
            repp(j, W) cout << ans[i][j] << " ";
            cout << endl;
        }
        #endif
    }
}

Submission Info

Judge Result