abc 062 3N numbers priority_queue

縦 H ピクセル、横 W ピクセルの画像があります。 各ピクセルは英小文字で表されます。 上から i 番目、左から j 番目のピクセルは aij です。
この画像の周囲 1 ピクセルを # で囲んだものを出力してください。

```
#include<iostream>
using namespace std;
int main() {
	int H, W;
	cin >> H >> W;
	char a[110][110];
	for (int i = 1; i <= H; ++i) {
		for (int j = 1; j <= W; ++j) {
			cin >> a[i][j];
		}
	}

	for (int i = 0; i <= W + 1; ++i) {
		cout << '#';
	}
	cout << endl;
	for (int j = 1; j <= H; ++j) {
		cout << '#';
		for (int i = 1; i <= W; ++i) {
			cout << a[j][i];
		}
		cout << '#' << endl;
	}
	for (int i = 0; i <= W+1; ++i) {
		cout << '#';
	}
	return 0;
}
```
筋トレ的な、

C
縦 H ブロック、横 W ブロックの板チョコがあります。 すぬけ君は、この板チョコをちょうど 3 つのピースに分割しようとしています。 ただし、各ピースはブロックの境目に沿った長方形でなければなりません。
すぬけ君は、3 つのピースの面積 (ブロック数) をできるだけ均等にしようとしています。 具体的には、3 つのピースの面積の最大値を Smax、最小値を Smin としたとき、Smax−Smin を最小化しようとしています。 Smax−Smin の最小値を求めてください
HとWどちらかが３の倍数の時は考える必要もなく０．よってどちらも３の倍数じゃない時を考える。
同じ方向に二回切るのと違う方向に一回ずつ切るので計算方法が異なりそうなので分けて考える。
同じ方向の時は、min(H,W)である。
違う方向は？
それぞれをできるだけH*W/3に近づけたい。一般化すると、
a=W/3,W/3+1,b=H/2,H/2+1
X=aH,Y=b(W-a),Z=(W-a)(H-b)となる。

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9;
int main() {
	ll h, w, a, b;
	ll ans, M, m, X, Y, Z;
	cin >> h >> w;
	if (h*w % 3 == 0) {
		cout << 0 << endl;
		return 0;
	}
	ans = min(h, w);
	for (int k = 0; k < 2; ++k) {
		for (int i = 0; i <= 1; ++i) {
			for (int j = 0; j <= 1; ++j) {
				a = w / 3 + i; b = h / 2 + j;
				X = a * h;
				Y = b * (w - a);
				Z = (w - a)*(h - b);
				M = max(X, Y);
				M = max(M, Z);
				m = min(X, Y);
				m = min(m, Z);
				ans = min(ans, M - m);
			}
		}
		swap(h, w);
	}
	cout << ans << endl;
	return 0;
}
```

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////

int main() {
	ll N;
	cin >> N;
	ll a[N * 3 + 1];
	for (int i = 1; i <= N*3; ++i)cin >> a[i];
	ll red[2*N+1];
	red[0] = 0;
	//red[i]=前半i個からN個選んだ総和の最大値
	priority_queue<ll,vector<ll>,greater<ll>>rque;
	//大きいほうからN個を保持
	for (int i = 1; i <= N; ++i) {
		red[i] = red[i - 1] + a[i];
		rque.push(a[i]);
	}
	//ここから小さいのが切り捨てられる
	for (int i = N + 1; i <= N * 2; ++i) {
		red[i] = red[i - 1] + a[i];
		rque.push(a[i]);
		red[i] -= rque.top();
		rque.pop();
	}
	reverse(a+1,a+N*3+1);
	ll blue[N * 2 + 1];
	blue[0] = 0;
	//blue[i]=後半i個からN個選んだ総和の最小値
	priority_queue<ll>bque;
	for (int i = 1; i <= N; ++i) {
		blue[i] = blue[i - 1] + a[i];
		bque.push(a[i]);
	}
	for (int i = N+1; i <= N * 2; ++i) {
		blue[i] = blue[i - 1] + a[i];
		bque.push(a[i]);
		blue[i] -= bque.top();
		bque.pop();
	}
	ll ans = -1e20;
	for (int i = N; i <= N * 2; ++i) {
		ans = max(ans, red[i] - blue[N * 3 - i]);
	}
	cout << ans << endl;
	return 0;
}
```