結果
| 問題 | No.3334 I hate Image Convolution |
| コンテスト | |
| ユーザー |
 tau0529
|
| 提出日時 | 2026-05-27 18:47:46 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 89 ms / 3,000 ms |
| コード長 | 14,628 bytes |
| 記録 | |
| コンパイル時間 | 4,687 ms |
| コンパイル使用メモリ | 388,656 KB |
| 実行使用メモリ | 11,164 KB |
| 最終ジャッジ日時 | 2026-05-27 18:48:05 |
| 合計ジャッジ時間 | 15,321 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_1 |
| 純コード判定待ち |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 56 |
ソースコード
//.at(i)を[i]と書いても警告が出るように
#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
struct RedCerr : public streambuf {
streambuf* orig;
bool line_start = true;
RedCerr() : orig(cerr.rdbuf()) { cerr.rdbuf(this); }
~RedCerr() { cerr.rdbuf(orig); }
int overflow(int c) override {
if (c == EOF) return c;
if (line_start) {
string red = "\033[31m";
orig->sputn(red.c_str(), red.size());
line_start = false;
}
orig->sputc(c);
if (c == '\n') {
string reset = "\033[0m";
orig->sputn(reset.c_str(), reset.size());
line_start = true;
}
return c;
}
} red_cerr;
//int64_t
using lint = int64_t;
//long double
using ld = long double;
//ベクター
template<typename T> using vc = vector<T>; //1次元リスト
template<typename T> using vv = vector<vector<T>>; //2次元リスト
template<typename T> using vvv = vector<vector<vector<T>>>; //3次元リスト
template<typename T> using vvvv = vector<vector<vector<vector<T>>>>; //4次元リスト
//ペア
using pll = pair<int64_t, int64_t>;
//プライオリティーキュー
template<typename T> using pq = priority_queue<T, vector<T>>; // 大きい順
template<typename T> using pqg = priority_queue<T, vector<T>, greater<T>>; // 小さい順
#define pb push_back
#define mp make_pair
#define fi first
#define se second
//all マクロ
#define all(v) (v).begin(), (v).end()
//ループマクロ
#define re(n) for (int64_t r_= 0; r_< int64_t(n);r_++)
#define rep(i, n) for (int64_t i = 0; i < int64_t(n); i++)
#define repp(i, n) for (int64_t i = 0; i <= int64_t(n); i++)
#define rrep(i, a, b) for (int64_t i = int64_t(a); i < int64_t(b); i++)
#define rrepp(i, a, b) for (int64_t i = int64_t(a); i <= int64_t(b); i++)
#define reep(i, n) for (int64_t i = int64_t(n)-1; i >= 0; i--)
#define reepp(i, n) for (int64_t i = int64_t(n); i >= 0; i--)
#define rreep(i, a, b) for (int64_t i = int64_t(b)-1; i >= int64_t(a); i--)
#define rreepp(i, a, b) for (int64_t i = int64_t(b); i >= int64_t(a); i--)
//sizeをint64_t型に
#define sz(x) ((int64_t)x.size())
//next_permutation
#define next_p(v) next_permutation((v).begin(), (v).end())
//無限
const int64_t inf = 1001001001;
const int64_t INF = 4004004004004004004LL;
//モッド
const int64_t MOD = 998244353;
//const int64_t MOD = 1000000007;
//パイ
const long double pi = 3.141592653589793238L;
//ネイピア数
const long double napier = 2.7182818284590452353L;
//移動
static constexpr int64_t dh[] = {0, -1, 0, 1, -1, -1, 1, 1};
static constexpr int64_t dw[] = {1, 0, -1, 0, 1, -1, -1, 1};
//cin cout オーバーロード
//vector
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
for (T & in : v) is >> in;
return is;
}
template <typename T>
ostream &operator<<(ostream & os, const vector<T> &v) {
for (int64_t i = 0; i < (int64_t)v.size(); i++) {
os << v[i] << (i + 1 != (int64_t)v.size() ? " " : "");
}
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v) {
for (int64_t i = 0; i < (int64_t)v.size(); i++) {
os << v[i] << endl;
}
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v) {
for (int64_t i = 0; i < (int64_t)v.size(); i++) {
os << "i = " << i << endl;
os << v[i];
}
return os;
}
//pair
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
is >> p.first >> p.second;
return is;
}
template <typename T1, typename T2>
ostream &operator<<(ostream & os, const pair<T1, T2> & p) {
os << "(" << p.first << "," << p.second << ")";
return os;
}
//vector複数行受け取り
template <typename T1, typename T2>
void vcin(vector<T1> &u, vector<T2> &v) {
if (u.size() != v.size()) {
cerr << "vcinエラー サイズが異なります" << endl;
assert(false);
return;
}
for (int64_t i = 0; i < (int64_t)u.size(); i++) {
cin >> u[i] >> v[i];
}
return;
}
template <typename T1, typename T2, typename T3>
void vcin(vector<T1> &u, vector<T2> &v, vector<T3> &w) {
if (u.size() != v.size() || v.size() != w.size()) {
cerr << "vcinエラー サイズが異なります" << endl;
assert(false);
return;
}
for (int64_t i = 0; i < (int64_t)u.size(); i++) {
cin >> u[i] >> v[i] >> w[i];
}
return;
}
//Yes No出力
#define YES cout << "YES" << endl;
#define Yes cout << "Yes" << endl;
#define NO cout << "NO" << endl;
#define No cout << "No" << endl;
void YN (bool b) {
if (b) cout << "YES" << endl;
else cout << "NO" << endl;
return;
}
void yn (bool b) {
if (b) cout << "Yes" << endl;
else cout << "No" << endl;
return;
}
// 値の更新
template<typename T1, typename T2>
bool chmax(T1 &x, const T2 &y) {
bool compare = x < y;
if (compare) x = y;
return compare;
}
template<typename T1, typename T2>
bool chmin(T1 &x, const T2 &y) {
bool compare = x > y;
if (compare) x = y;
return compare;
}
//経過時間
long double Time () {
return 1.0 * (clock()) / CLOCKS_PER_SEC;
}
//小さい順
template<typename T>
void Vsort (vector<T> &v) {
sort(v.begin(), v.end());
return;
}
//大きい順
template<typename T>
void Vsortg (vector<T> &v) {
sort(v.rbegin(), v.rend());
return;
}
//リバース
template<typename T>
void Vreverse (vector<T> &v) {
reverse(v.begin(), v.end());
return;
}
//重複の削除
template<typename T>
void Vunique (vector<T> &v) {
#ifndef ONLINE_JUDGE
static bool w = false;
if (!w) { cerr << "Vuniqueでは必ずソートされてますか？" << endl; w = true; }
#endif
v.erase(unique(v.begin(), v.end()), v.end());
return;
}
//上下反転
template<typename T>
void UDflip (vector<vector<T>> &v) {
reverse(v.begin(), v.end());
return;
}
//左右反転
template<typename T>
void LRflip (vector<vector<T>> &v) {
for (auto &x : v) {
reverse(x.begin(), x.end());
}
return;
}
//リストの移動
template<typename T>
void Vrotate (vector<T> &v, int64_t n) {
if (v.empty()) return;
n %= (int64_t)v.size();
rotate(v.begin(), v.begin() + n, v.end());
return;
}
//右回転
template<typename T>
void VVrotate (vector<vector<T>> &v) {
int64_t H = v[0].size();
int64_t W = v.size();
vector<vector<T>> L(H, vector<T>(W));
for (int64_t i = 0; i < H; i++) {
for (int64_t j = 0; j < W; j++) {
L[j][W - i - 1] = v[i][j];
}
}
v = L;
return;
}
//左回転
template<typename T>
void VVrotateg (vector<vector<T>> &v) {
int64_t H = v[0].size();
int64_t W = v.size();
vector<vector<T>> L(H, vector<T>(W));
for (int64_t i = 0; i < H; i++) {
for (int64_t j = 0; j < W; j++) {
L[H - j - 1][i] = v[i][j];
}
}
v = L;
return;
}
//2次元距離
template<typename T>
long double distan (T x1, T y1, T x2, T y2) {
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
//2次元距離の2乗
template<typename T>
T distan2 (T x1, T y1, T x2, T y2) {
return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}
//範囲内チェック
#define in_grid(h, w, H, W) if (!(0 <= h && 0 <= w && h < H && w < W)) continue;
//nPr
int64_t nPr (int64_t n, int64_t r) {
int64_t Ans = 1;
for (int64_t i = 0; i < r; i++) {
Ans *= n - i;
}
return Ans;
}
//nCr
vector<vector<int64_t>> nCr_memo;
int64_t nCr (int64_t n, int64_t r) {
if (n < r) {
cerr << "Error nCrのrがnより大きいです" << endl;
assert(false);
return 0;
}
for (int64_t i = (int64_t)nCr_memo.size(); i <= n; i++) {
nCr_memo.push_back(vector<int64_t>(i + 1, 1));
for (int64_t j = 1; j < i; j++) {
nCr_memo[i][j] = nCr_memo[i - 1][j - 1] + nCr_memo[i - 1][j];
}
}
return nCr_memo[n][r];
}
//累乗
int64_t power (int64_t a, int64_t b) {
int64_t Ans = 1;
while (b > 0) {
if (b & 1) Ans *= a;
a *= a;
b >>= 1;
}
return Ans;
}
//階乗
int64_t factorial(int64_t n) {
int64_t Ans = 1;
for (int64_t i = 1; i <= n; i++) Ans *= i;
return Ans;
}
//数値のN桁目
int64_t digit(int64_t x, int64_t k) {
while (k--) x /= 10;
return x % 10;
}
static constexpr int64_t ID = -8e18;
constexpr int64_t sum_op (int64_t a, int64_t b) { return (a + b); }
constexpr int64_t mul_op (int64_t a, int64_t b) { return (a * b); }
string txt_op (string a, string b) { return (a + b); }
constexpr int64_t min_op (int64_t a, int64_t b) { return min(a , b); }
constexpr int64_t max_op (int64_t a, int64_t b) { return max(a , b); }
constexpr int64_t lcm_op (int64_t a, int64_t b) { return lcm(a , b); }
constexpr int64_t gcd_op (int64_t a, int64_t b) { return gcd(a , b); }
constexpr int64_t xor_op (int64_t a, int64_t b) { return (a ^ b); }
constexpr pair<int64_t, int64_t> sum_OP (pair<int64_t, int64_t> a, pair<int64_t, int64_t> b) { return make_pair(sum_op(a.first, b.first), a.second + b.second); }
constexpr int64_t no0_e () { return 0; }
constexpr int64_t no1_e () { return 1; }
string emp_e () { return ""; }
constexpr int64_t max_e () { return 4e18; }
constexpr int64_t min_e () { return -4e18; }
constexpr pair<int64_t, int64_t> no0_E () { return {0, 0}; }
constexpr int64_t add_map (int64_t f, int64_t x) { return x + f; }
constexpr int64_t upd_map (int64_t f, int64_t x) { return f == ID ? x : f; }
constexpr pair<int64_t, int64_t> add_MAP (int64_t f, pair<int64_t, int64_t> x) { x.first += f * x.second; return x; }
constexpr pair<int64_t, int64_t> upd_MAP (int64_t f, pair<int64_t, int64_t> x) { if (f != ID) x.first = f * x.second; return x; }
constexpr int64_t add_com (int64_t f, int64_t g) { return g + f; }
constexpr int64_t upd_com (int64_t f, int64_t g) { return f == ID ? g : f; }
constexpr int64_t no0_id () { return 0; }
constexpr int64_t upd_id () { return ID; }
//セグ木
using sumtree = segtree<int64_t, sum_op, no0_e>;
using multree = segtree<int64_t, mul_op, no1_e>;
using txttree = segtree<string , txt_op, emp_e>;
using mintree = segtree<int64_t, min_op, max_e>;
using maxtree = segtree<int64_t, max_op, min_e>;
using lcmtree = segtree<int64_t, lcm_op, no1_e>;
using gcdtree = segtree<int64_t, gcd_op, no0_e>;
using xortree = segtree<int64_t, xor_op, no0_e>;
//遅延セグ木
using lazyaddsum = lazy_segtree<pair<int64_t, int64_t>, sum_OP, no0_E, int64_t, add_MAP, add_com, no0_id>;
using lazyupdsum = lazy_segtree<pair<int64_t, int64_t>, sum_OP, no0_E, int64_t, upd_MAP, upd_com, upd_id>;
using addmintree = lazy_segtree<int64_t, min_op, max_e, int64_t, add_map, add_com, no0_id>;
using updmintree = lazy_segtree<int64_t, min_op, max_e, int64_t, upd_map, upd_com, upd_id>;
using addmaxtree = lazy_segtree<int64_t, max_op, min_e, int64_t, add_map, add_com, no0_id>;
using updmaxtree = lazy_segtree<int64_t, max_op, min_e, int64_t, upd_map, upd_com, upd_id>;
struct addsumtree : lazyaddsum {
addsumtree (int64_t n) : lazyaddsum(vector<pair<int64_t, int64_t>>(n, {0, 1})) {}
addsumtree (vector<int64_t> v) : lazyaddsum([&]{
vector<pair<int64_t, int64_t>> p(v.size());
for (int64_t i = 0; i < (int64_t)v.size(); i++) p[i] = {v[i], 1};
return p;
}()) {}
};
struct updsumtree : lazyupdsum {
updsumtree (int64_t n) : lazyupdsum(vector<pair<int64_t, int64_t>>(n, {0, 1})) {}
updsumtree (vector<int64_t> v) : lazyupdsum([&]{
vector<pair<int64_t, int64_t>> p(v.size());
for (int64_t i = 0; i < (int64_t)v.size(); i++) p[i] = {v[i], 1};
return p;
}()) {}
};
//!####################################################################################################
//フリーセグ木
//区間和の例
using seg_s = int64_t;
constexpr seg_s seg_op (seg_s a, seg_s b) {
return a + b;
}
constexpr seg_s seg_e () {
return 0;
}
using segtre = segtree<seg_s, seg_op, seg_e>;
//フリー遅延セグ木（サイズ持ち
//区間加算操作・区間和取得の例
using leg_s = pair<int64_t, int64_t>;
constexpr leg_s leg_op (leg_s a, leg_s b) { //演算
auto x = a.first, y = b.first;//
auto z = x + y;
return {z, a.second + b.second};//
}
constexpr leg_s leg_e () { //初期値（単位元
return {0, 0};
}
#define leg_f int64_t
constexpr leg_s leg_map (leg_f f, leg_s x) { //遅延後の操作
auto a = x.first, size = x.second;//
return {a + size * f, size};
}
constexpr leg_f leg_com (leg_f f, leg_f g) { //遅延の重ね方
return g + f;
}
constexpr leg_f leg_id () { //遅延の単位元
return 0;
}
using lazyleg = lazy_segtree<leg_s, leg_op, leg_e, leg_f, leg_map, leg_com, leg_id>;
struct legtre : lazyleg {
legtre (int64_t n) : lazyleg(vector<leg_s>(n, {0, 1})) {}
legtre (vector<int64_t> v) : lazyleg([&]{
vector<leg_s> p(v.size());
for (int64_t i = 0; i < (int64_t)v.size(); i++) p[i] = {v[i], 1};
return p;
}()) {}
};
//!####################################################################################################
void solve () {
lint N; cin >> N;
vc<lint> C((N-1) * (N-1)); cin >> C;
Vsort(C);
vv<lint> L(N, vc<lint>(N, 0));
rep (h, N-1) {
rep (w, N-1) {
lint c = 0;
c += L[h][w];
c += L[h][w+1];
c += L[h+1][w];
L[h+1][w+1] = C[h*(N-1)+w] - c;
}
lint Min = inf;
rep (w, N-1) {
chmin(Min, L[h+1][w+1]);
}
if (Min >= 0) continue;
rep (w, N) {
if (w % 2 == 0) L[h+1][w] -= Min;
else L[h+1][w] += Min;
}
}
lint Min = inf;
for (auto x : L) {
for (auto y : x) {
chmin(Min, y);
}
}
if (Min < 0) {
cout << -1 << endl;
return;
}
cout << L;
return;
}
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
RedCerr red_cerr; //VSCodeで色つけるやつ
cout << fixed << setprecision(15);
cerr << fixed << setprecision(15);
lint T = 1;
cin >> T;
re (T) solve();
cerr << endl << Time() << endl;
}