結果
| 問題 | No.2696 Sign Creation |
| コンテスト | |
| ユーザー |
 Astral__
|
| 提出日時 | 2024-03-22 23:33:03 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
WA
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 29,907 bytes |
| 記録 | |
| コンパイル時間 | 4,371 ms |
| コンパイル使用メモリ | 274,288 KB |
| 実行使用メモリ | 9,856 KB |
| 最終ジャッジ日時 | 2024-12-20 12:34:09 |
| 合計ジャッジ時間 | 6,380 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 37 WA * 1 |
ソースコード
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
//using uLL = unsigned __int128;
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using pq = priority_queue<T>;
using pll = pair<long long, long long>;
using pii = pair<int, int>;
using vvvvl = vector<vector<vector<vector<ll>>>>;
using vvvi = vector<vector<vector<int>>>;
using vvvl = vector<vector<vector<ll>>>;
using vvvc = vector<vector<vector<char>>>;
using vvvd = vector<vector<vector<double>>>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvc = vector<vector<char>>;
using vvp = vector<vector<pair<ll, ll>>>;
using vvb = vector<vector<bool>>;
using vvd = vector<vector<double>>;
using vp = vector<pair<ll, ll>>;
using vi = vector<int>;
using vl = vector<ll>;
using vu = vector<unsigned long long>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
#define vvvm vector<vector<vector<mint>>>
#define vvm vector<vector<mint>>
#define vm vector<mint>
template <typename T1, typename T2>
using umap = unordered_map<T1, T2>;
template <typename T1>
using uset = unordered_set<T1>;
#define rrr(l, r) mt()%(r-l+1)+l
#define rep(i, s, f) for(long long i = s; i <= f; i++)
#define rep1(i, s, f) for(long long i = s; i <= f; i++)
#define per(i, s, f) for(long long i = s; i >= f; i--)
#define per1(i, s, f) for(long long i = s; i >= f; i--)
#define all0(x) (x).begin() ,(x).end()
#define all(x) (x).begin() + 1, (x).end()
#define ins(l, r, x) (l <= x && x <= r)
#define ENDL '\n'
////////////////////////////////////////////////////////////////////////////////////////////////////////////
//これが本当の組み込み関数ってね（笑）
template <typename T>
int LB(vector<T> &A, T x) {
return lower_bound(A.begin(), A.end(), x) - A.begin();
}
template <typename T>
int UB(vector<T> &A, T x) {
return upper_bound(A.begin(), A.end(), x) - A.begin();
}
template <typename T>
void UNIQUE(vector<T> &A, int indexed) {
sort(A.begin() + indexed, A.end());
A.erase(unique(A.begin() + indexed, A.end()), A.end());
}
int msb(long long a) {
if(a == 0) return -1;
return 64 - int(__builtin_clzll(a));
}
template<typename T = long long>
void chmin(T &a, T b) {
a = min(a, b);
}
template<typename T = long long>
void chmax(T &a, T b) {
a = max(a, b);
}
//////////////////////////////////////////////////////////////////////
//数学系
///////////////////////////////////////////////////////////////////////
ll extgcd (ll a, ll b, ll &x, ll &y) {
if(b == 0) { x = 1;y = 0;return a;}
ll d = extgcd(b, a%b, y, x);
y -= a/b * x;
return d;
}
template <typename T>
T ceil__(T a, T b) {
assert(b != 0);
if(a % b == 0) return a / b;
if((a <= 0 && b < 0) || (a >= 0 && b > 0)) return a/b + 1;
else return a / b;
}
template <typename T>
T floor__(T a, T b) {
assert(b != 0);
if(a % b == 0) return a / b;
if((a <= 0 && b < 0) || (a >= 0 && b > 0)) return a/b;
else return a/b - 1;
}
ll modpow(ll x, ll y, ll mod) {
if(x > mod) x %= mod;
if(y == 0) return 1;
ll res = modpow(x, y >> 1, mod);
res = res * res % mod;
if(y & 1) res *= x, res %= mod;
return res;
}
ll sqrt__(ll a) {
ll l = 0;
ll r = 3037000499LL;
while(l < r) {
ll mid = (l + r + 1) / 2;
if(mid * mid <= a) l = mid;
else r = mid - 1;
}
return l;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//グローバル変数を置くところ
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize "trapv" //お祈り。変数同士の演算でのみ感知。代入や、 a *= 10000 では感知しない。
const ll big = 1001001001;
const ll BIG = 1001001001001001001LL;
const double pi = 3.141592653589793;
//const ll mod = 1000000007;
//const ll mod = 998244353;
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
template<typename X>
struct splay_set {
struct node_t {
X val;
X acc;
int sum = 0;
node_t* lch;
node_t* rch;
node_t(X v): val(v), acc(v) {
sum = 1;
lch = nullptr;
rch = nullptr;
}
};
using NODE = node_t;
NODE* root = nullptr;//Splay木の根を表すノード。
long long size_of_tree = 0;//木に登録されている要素数を返す。
int pre = 0;
splay_set(){}
private:
long long count(NODE* now) {return now == nullptr ? 0 : now -> sum;}
X acc(NODE* now) {return !now ? X() : now -> acc;}
NODE* pushup(NODE* now) {
if(now != nullptr) {
now -> sum = count(now -> lch) + count(now -> rch) + 1;
now -> acc = acc(now -> lch) + now -> val + acc(now -> rch);
}
return now;
}
NODE* rotate(NODE* now, int b) {//ノードnowを回転させる処理。b = 1で右回転、 b = 0で左回転。」
if(b==1) {
NODE* s = now -> lch;
now -> lch = s -> rch;
s -> rch = now;
pushup(now), pushup(s);
return s;//戻り値は、回転した後nowの位置にくるノードのポインタ。
}
else {
NODE* s = now -> rch;
now -> rch = s -> lch;
s -> lch = now;
pushup(now), pushup(s);
return s;
}
}
/*
NODE* splay_sub_pos(NODE* now, int pos, pair<int, NODE*>& history, bool& found) {
if(now == nullptr) {
found = false;
return now;
}
if(count(now -> lch) + 1 == pos) {
return now;
}
int b = 1;
if(count(now -> lch) + 1 < pos) {
pos -= count(now -> lch) + 1;
now -> rch = splay_sub_pos(now -> rch, pos, history, found);
pushup(now);
}
else {
b = 0, now -> lch = splay_sub_pos(now -> lch, pos, history, found);
pushup(now);
}
if(!found) return now;
auto [pb, pn] = history;
if(pn == nullptr) history = make_pair(b, now);
else {
history = make_pair(-1, nullptr);
if(b == pb) {
now = rotate(now, 1 - b);
now = rotate(now, 1 - b);
}
else {
if(b==1) now -> rch = rotate(pn, 1 - pb);
else now -> lch = rotate(pn, 1 - pb);
pushup(now);
now = rotate(now, 1 - b);
}
}
return now;
}*/
NODE* splay_sub(NODE* now, const X& x, pair<int, NODE*>& history, bool& found) {
if(now == nullptr) {
found = false;
return now;
}
if(now -> val == x) {
return now;
}
int b = 1;
if(x > now -> val) {
now -> rch = splay_sub(now -> rch, x, history, found);
pushup(now);
}
else if(x < now -> val) {
b = 0, now -> lch = splay_sub(now -> lch, x, history, found);
pushup(now);
}
if(!found) return now;
auto [pb, pn] = history;
if(pn == nullptr) history = make_pair(b, now);
else {
history = make_pair(-1, nullptr);
if(b == pb) {
now = rotate(now, 1 - b);
now = rotate(now, 1 - b);
}
else {
if(b==1) now -> rch = rotate(pn, 1 - pb);
else now -> lch = rotate(pn, 1 - pb);
pushup(now);
now = rotate(now, 1 - b);
}
}
return now;
}
void splay(NODE* now, const X& x) {
bool found = true;
pair<int, NODE*> h(-1, nullptr);
root = splay_sub(now, x, h, found);
if(found && h.second != nullptr) {
root = rotate(root, 1 - h.first);
}
return ;
}
/*
void splay_pos(NODE* now, int pos) {
bool found = true;
pair<int, NODE*> h(-1, nullptr);
root = splay_sub_pos(now, pos, h, found);
if(found && h.second != nullptr) {
root = rotate(root, 1 - h.first);
}
return ;
}*/
NODE* change__(NODE* now, X& x) {//現在見ているノード | 挿入する値
if(now == nullptr) {
size_of_tree++;
return new NODE(x);
}
if(now -> val == x) return now;
if(x > now -> val) {
now -> rch = change__(now -> rch, x);
pushup(now);
return now;
}
else {
now -> lch = change__(now -> lch, x);
pushup(now);
return now;
}
}
NODE* find_max_only(NODE* now) {//nowを根とする部分木の中で最大の要素を持つノードを返す。この時、splay操作は行わない。
if(now == nullptr) return now;
NODE* res = now;
while(res -> rch != nullptr) res = res -> rch;
return res;
}
NODE* find_min_only(NODE* now) {//nowを根とする部分木の中で最小の要素を持つノードを返す。この時、splay操作は行わない。
if(now == nullptr) return now;
NODE* res = now;
while(res -> lch != nullptr) res = res -> lch;
return res;
}
NODE* erase__(NODE*now, X& x){//削除ノードまで降っていき、削除が完了次第葉の方から再構成する。
if(now == nullptr) return now;
if(x < now -> val) {
now -> lch = erase__(now -> lch, x);
pushup(now);
}
else if(x > now -> val) {
now -> rch = erase__(now -> rch, x);
pushup(now);
}
else {
if(now -> lch == nullptr) {//左に子がない時
NODE* tmp = now -> rch;
delete now;
size_of_tree--;
return tmp;
}
else if(now -> rch == nullptr) {//右に子がない時
NODE* tmp = now -> lch;
delete now;
size_of_tree--;
return tmp;
} else {//右にも左にも子がある時
NODE* tmp = find_max_only(now -> lch);//左子孫の最大値
now -> val = tmp -> val;
now -> lch = erase__(now -> lch, tmp -> val);//移動したノードを削除。(ポインタの操作に注意)
pushup(now);
}
}
return now;//現在のノードまで削除の作業が完了したらば、更新された現在のノードを返して終了。
}
void lower_bound_val__(NODE*now, X& x, X& res) {//x以上で最小val
//前提：その様な値が存在する。
if(now -> val == x) {
res = x;
return;
}
if(x < now -> val) {//答えは、min(now, nowの左子孫の中でx以上の最小の要素)
res = min(res, now -> val);
if(now -> lch != nullptr) lower_bound_val__(now -> lch, x, res);
}
else {//答えは、右子孫の中でx以上の最小の値
if(now -> rch != nullptr) lower_bound_val__(now -> rch, x, res);//右に子が存在しないという事はない。
}
return;
}
void upper_bound_val__(NODE*now, X& x, X& res) {//x超過で最小val
//前提：その様な値が存在する。
if(x < now -> val) {//答えは、min(now, nowの左子孫の中でxより大きい最小の要素)
res = min(res, now -> val);
if(now -> lch != nullptr) upper_bound_val__(now -> lch, x, res);
}
else {//答えは、右子孫の中でxより大きいの最小の値
if(now -> rch != nullptr) upper_bound_val__(now -> rch, x, res);//右に子が存在しないという事はない。
}
return;
}
void lower_left_bound_val__(NODE* now, X& x, X& res) {//x以下で最大val
//前提：その様な値が存在する。
if(now -> val == x) {
res = x;
return;
}
if(x < now -> val) {//左
if(now -> lch != nullptr) lower_left_bound_val__(now -> lch, x, res);
}
else {
res = max(res, now -> val);
if(now -> rch != nullptr) lower_left_bound_val__(now -> rch, x, res);
}
}
void upper_left_bound_val__(NODE* now, X& x, X& res) {//x未満で最大val
//前提：その様な値が存在する。
if(x <= now -> val) {//左
if(now -> lch != nullptr) upper_left_bound_val__(now -> lch, x, res);
}
else {
res = max(res, now -> key);
if(now -> rch != nullptr) upper_left_bound_val__(now -> rch, x, res);
}
}
NODE* lower_bound__(X x) {//x以上で最小、存在しないならnullptr
if(size_of_tree==0) return nullptr;
NODE* M = find_max_only(root);
X t = M -> val;
if(t < x) return nullptr;//x以上の値は存在しない。
lower_bound_val__(root, x, t);
splay(root, t);
return root;
}
NODE* upper_bound__(X x) {//k超過で最小、存在しないならnullptr
if(size_of_tree==0) return nullptr;
NODE* M = find_max_only(root);
X t = M -> val;
if(t <= x) return nullptr;
upper_bound_val__(root, x, t);
splay(root, t);
return root;
}
NODE* lower_left_bound__(X x) {//k以下で最大。
if(size_of_tree==0) return nullptr;
NODE* m = find_min_only(root);
X t = m -> val;
if(t > x) return nullptr;
lower_left_bound_val__(root, x, t);
splay(root,t);
return root;
}
NODE* upper_left_bound__(X x) {//k未満で最大。
if(size_of_tree==0) return nullptr;
NODE* m = find_min_only(root);
X t = m -> val;
if(t >= x) return nullptr;
upper_left_bound_val__(root, x, t);
splay(root, t);
return root;
}
NODE* ith_element__(NODE* now, long long i) {
long long ls = count(now -> lch);
if(ls + 1 <= i && i <= ls + 1) {
return now;
}
else if(ls >= i) return ith_element__(now -> lch, i);
else return ith_element__(now -> rch, i - 1 - ls);
}
NODE* max_element__() {//最大のkey、存在しないならnullptr
NODE* tar = find_max_only(root);
if(tar == nullptr) return tar;
pair<int, NODE*> h (-1, nullptr);
splay(root , tar -> val);
return root;
}
NODE* min_element__() {//最小のkey、存在しないならnullptr
NODE* tar = find_min_only(root);
if(tar == nullptr) return tar;
pair<int, NODE*> h (-1, nullptr);
splay(root , tar -> val);
return root;
}
NODE* lower_sum_left__(NODE* now, X S, int L) {
X now_sum = X();
if(L != 1) {
S = S + accL(L-1);
}
if(S > acc(root)) return nullptr;
while(1) {
X tmp = now_sum + acc(now -> lch);
if(tmp >= S) now = now -> lch;
else {
tmp += now -> val;
if(tmp >= S) {
splay(root, now->val);
return root;
}
else {
now_sum = tmp;
now = now -> rch;
}
}
}
}
NODE* upper_sum_left__(NODE* now, X S, int L) {
X now_sum = X();
if(L != 1) {
S = S + accL(L-1);
}
if(S >= acc(root)) return nullptr;
while(1) {
X tmp = now_sum + acc(now -> lch);
if(tmp > S) now = now -> lch;
else {
tmp += now -> val;
if(tmp > S) {
splay(root, now->val);
return root;
}
else {
now_sum = tmp;
now = now -> rch;
}
}
}
}
NODE* next(NODE*& now) {//次のkey、存在しないならnullptr
if(now == nullptr) return now;
else return upper_bound__(now -> val);
}
NODE* prev(NODE*& now) {//前のkey。存在しなければnullptr
if(now == nullptr) return now;
else return upper_left_bound__(now -> val);
}
void in_order__(NODE* now, vector<X>& res) {
if(now == nullptr) return;
in_order__(now -> lch, res);
res.push_back(now -> val);
in_order__(now -> rch, res);
return;
}
public:
void insert(X x) {
pushup(root);
change(x);
}
void erase(X x) {//存在しなかった場合、何もしない。
pushup(root);
root = erase__(root, x);
}
bool find(X x) {
pushup(root);
splay(root,x);
if(root == nullptr || root -> val != x) return false;
return true;
}
int count(X x) {
pushup(root);
splay(root, x);
if(root == nullptr || root -> val != x) return 0;
return 1;
}
void change(X x) {//xを挿入)
pushup(root);
root = change__(root, x);
splay(root, x);//根を更新。
return;
}
int size() {
return size_of_tree;
}
bool empty() {
return size_of_tree == 0;
}
bool next(X x, X& res) {//次のkey。存在しないならfalse。結果はresに渡される。
pushup(root);
NODE* r = upper_bound__(x);
if(r==nullptr)return false;
else {
res = r -> val;
return true;
}
}
bool prev(X x, X& res) {//前のkey.存在しないならfalse。結果はresに渡される。
pushup(root);
NODE* r = upper_left_bound__(x);
if(r==nullptr)return false;
else {
res = r -> val;
return true;
}
}
bool ith_element(long long i, X& res) {
pushup(root);
if(count(root) < i) return false;
else {
NODE* tar = ith_element__(root, i);
res = tar -> val;
return i;
}
}
long long get_order(X& x) {
pushup(root);
splay(root, x);
if(root == nullptr || root -> val != x) return -1LL;
else return count(root -> lch) + 1;
}
bool max_element(X& res) {//最大のkey
pushup(root);
NODE* tar = max_element__();
if(tar == nullptr) return false;
else {
res = tar -> val;
return true;
}
}
bool min_element(X& res) {//最小のkey
pushup(root);
NODE* tar = min_element__();
if(tar == nullptr) return false;
else {
res = tar -> val;
return true;
}
}
bool lower_bound(X x, X& res) {//x以上で最小key
pushup(root);
NODE* r = lower_bound__(x);
if(r == nullptr) return false;
else {
res = r -> val;
return true;
}
}
bool upper_bound(X x, X& res) {//k超過で最小となる
pushup(root);
NODE* r = upper_bound__(x);
if(r == nullptr) return false;
else {
res = r -> val;
return true;
}
}
bool lower_left_bound(X x, X& res) {//k以下で最大。
pushup(root);
NODE* r = lower_left_bound__(x);
if(r == nullptr) return false;
else {
res = r -> val;
return true;
}
}
bool upper_left_bound(X x, X& res) {//k未満で最大。
pushup(root);
NODE* r = upper_left_bound__(x);
if(r == nullptr) return false;
else {
res = r -> val;
return true;
}
}
X accL(int R) {//[1, R]のvalのモノイド積 Rがkeyの数より多いと単位元
if(R < 1 || size_of_tree < R) return X();
pushup(root);
X tar;
if(!ith_element(R, tar)) return X();
splay(root, tar);
return acc(root -> lch) + root -> val;
}
X accR(int L) {//[L, MAX]のvalのモノイド
if(L < 1 || size_of_tree < L) return X();
pushup(root);
X tar;
if(!ith_element(L, tar)) return X();
splay(root, tar);
return root -> val + acc(root -> rch);
}
bool lower_sum_left(X sum, int L, X& res) {
pushup(root);
NODE* tar = lower_sum_left__(root, sum, L);
if(tar == nullptr) return false;
else {
res = acc(tar -> lch) + tar -> val;
return true;
}
}
bool upper_sum_left(X sum, int L, X& res) {
pushup(root);
NODE* tar = upper_sum_left__(root, sum, L);
if(tar == nullptr) return false;
else {
res = acc(tar -> lch) + tar -> val;
//res = count(tar -> lch) + 1;
return true;
}
}
vector<X> in_order() {//要素を全て入れた配列 要素がないなら空配列
pushup(root);
vector<X> res;
in_order__(root, res);
return res;
}
void dump() {
pushup(root);
auto r = in_order();
for(X& x : r) cout << x << " ";
cout << endl;
}
NODE* end() {
return nullptr;
}
};
struct Union {
vector<int> Par;
vector<int> size;
int S;
Union(int N) {
Par.resize(N+1);
size.resize(N+1, 1);
S = 0;
for (int i = 1; i <= N; i++) {
Par[i] = i;
}
}
int root(int u) {
if (Par[u] != u) {
return Par[u] = root(Par[u]);
}
return u;
}
bool same(int a, int b) {
return root(a) == root(b);
}
void unit(int a, int b) {
a = root(a), b = root(b);
if(size[a] < size[b]) swap(a, b);
if(a == b) return;
else {
if(size[a] == 1 && size[b] == 1) S++;
else if(size[a] > 1 && size[b] > 1) S--;
Par[b] = root(a);
size[a] += size[b];
}
}
int getsize(int u) {//uが含まれる連結成分のサイズを返す
return size[root(u)];
}//O(1)(大体)
int sum() {
return S;
}
};
void solve() {
int H, W, N, D;
cin >> H >> W >> N >> D;
vi X(N+1), Y(N+1);
vvi table(H+1, vi(W+1, 0));
rep(i,1,N) cin >> Y[i] >> X[i];
rep(i,1,N) table[Y[i]][X[i]] = i;
Union uni(N);
rep(i,1,N) {
rep(dx, -D, D) {
rep(dy, -(D - abs(dx)), D - abs(dx)) {
int nx = X[i] + dx;
int ny = Y[i] + dy;
if(ins(1, H, ny) && ins(1, W, nx)) {
if(table[ny][nx]) uni.unit(i, table[ny][nx]);
}
}
}
}
int m = N;
int M = 0;
rep(x,1,W) {
rep(y, 1, H) {
vector<splay_set<int>> cnt(3);
rep(dx, -D, D) {
rep(dy, -(D - abs(dx)), D - abs(dx)) {
int nx = x + dx;
int ny = y + dy;
if(ins(1, H, ny) && ins(1, W, nx)) {
if(table[ny][nx]) {
cnt[min(2,uni.getsize(table[ny][nx]))].insert(uni.root(table[ny][nx]));
}
}
}
}
int res = uni.sum();
if(cnt[1].size() >= 1) res++;
if(cnt[2].size() >= 1) res -= cnt[2].size()-1;
chmax<int>(M, res);
chmin<int>(m, res);
}
}
cout << m << " " << M << endl;
}
/*
-違法な読み替えをしていないか・違法な操作をしていないか
・実装が重そうな時は確認する 一度飛ばしても良い
・waが出た時は嘘を吐いていないかの他に、違法な操作をしていないかもチェックする
特にふわっとした操作は危ない
・区間をちょっと伸ばす←伸ばす余地はあるか
・選択肢のうち、どれでも良いから消す←本当にどれでも良いか 場合分けを挟んでないか
-その情報はdpで纏めて良いものか
・dpで持つ：「この先の探索をするのに必要な情報」 なぜ必要なのか？
・途中までは辻褄が合っても、最後に分岐とかはある
-何もわからないという時
観察が求められるのは主に、[1]より高速な計算が求められる時 [2]最適解が求められる時 である。逆に、これを求められたら観察が必要になる。
・解を列挙した上で特徴づけ
-数え上げる対象・或いは最適化問題の解・クエリ問題で計算する対象」に、制約によって良い性質が与えられている可能性を探る
-機械で列挙し、最適解の構造を得る
-数え上げる対象が少ないと直感できるが、直接計算が難しそうな時
-可能か？を探る際は、最悪ケースで実験する。穴がある解を未然に防ぐ。
・遷移を図で表現し、使いまわしたりできないか見る
・自由度が高い最適化では、上階が達成できがち 必要条件をつみかさねていく ”非自明な最悪ケース（例：点の数が多いのに答え=0)”を作る時、何を意識したか？
・解の形を、必要条件や貪欲から絞る
・無駄な事/非効率な事は禁止して、その上で何ができるか
・差分を計算するなら、最初から差分計算の処理のみで答えを計算した方が良い。最初を愚直でやると情報をロストする可能性があるし、愚直の枠組みに囚われる事もある。
・要素と制約をグラフで表してみる
・強い制約は、数え上げ・最適化・クエリ・ゲーム共に良い性質を生みやすいので注目する
-制約に具体的な数値が登場している←適当に解をいじると何となく性質が見えることが多い
・制約を「全ての要素についてoo ⇔ (1<=i<=N)で、iについてoo」といったように、独立なものに言い換えた方がやりやすいこともある
・よくわからないものを言い換える。
-慣れ親しんだ制約も、問題設定によってより扱いやすい形に言い換えられるかもしれない（例：グラフが連結)
-一つの解法で駄目な時、周辺の解法も試すようにする。周辺で見えないなら全部試す。
・「貪欲で最適解」と「解の形を絞って全探索」
・「dp/最適化」と「解の形を絞って全探索」と 上界を見積もる」
・「dp」と「必要な情報を言い換える・何でのその情報が必要なのか考える事による高速化」
・「dp」と「探索の順番を変更する: でかい方から、深い方から、DAGで先端になっている・或いは葉になっている所から、全てを逆に言い換えて時系列的に後ろから」
・「dp」と「軸にするものを変える: マスを軸にするのではなく、燃料を軸にするなど」
*/
int main() {
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cout << fixed << setprecision(15);
ll T = 1;
//cin >> T;
rep(i, 1, T) {
solve();
}
return 0;
}