結果
| 問題 |
No.3306 Life is Easy?
|
| ユーザー |
 hirayuu_yc
|
| 提出日時 | 2025-10-05 15:28:41 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 21,814 bytes |
| コンパイル時間 | 3,516 ms |
| コンパイル使用メモリ | 319,884 KB |
| 実行使用メモリ | 137,832 KB |
| 最終ジャッジ日時 | 2025-10-05 15:29:00 |
| 合計ジャッジ時間 | 12,931 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 2 TLE * 2 -- * 31 |
ソースコード
// Problem: No.3306 Life is Easy?
// Contest: yukicoder
// URL: https://yukicoder.me/problems/no/3306
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#line 2 "/root/AtCoder/Halc-Library/Template/Template.hpp"
#include <bits/stdc++.h>
using namespace std;
#line 8 "/root/AtCoder/Halc-Library/Template/InOut.hpp"
inline void scan() {}
inline void scan(int32_t &a) { std::cin >> a; }
inline void scan(uint32_t &a) { std::cin >> a; }
inline void scan(int64_t &a) { std::cin >> a; }
inline void scan(uint64_t &a) { std::cin >> a; }
inline void scan(char &a) { std::cin >> a; }
inline void scan(float &a) { std::cin >> a; }
inline void scan(double &a) { std::cin >> a; }
inline void scan(long double &a) { std::cin >> a; }
inline void scan(std::vector<bool> &vec) {
for (int32_t i = 0; i < vec.size(); i++) {
int a;
scan(a);
vec[i] = a;
}
}
inline void scan(std::string &a) { std::cin >> a; }
template <class T>
inline void scan(std::vector<T> &vec);
template <class T, size_t size>
inline void scan(std::array<T, size> &vec);
template <class T, class L>
inline void scan(std::pair<T, L> &p);
template <class T, size_t size>
inline void scan(T (&vec)[size]);
template <class T>
inline void scan(std::vector<T> &vec) {
for (auto &i : vec) scan(i);
}
template <class T>
inline void scan(std::deque<T> &vec) {
for (auto &i : vec) scan(i);
}
template <class T, size_t size>
inline void scan(std::array<T, size> &vec) {
for (auto &i : vec) scan(i);
}
template <class T, class L>
inline void scan(std::pair<T, L> &p) {
scan(p.first);
scan(p.second);
}
template <class T, size_t size>
inline void scan(T (&vec)[size]) {
for (auto &i : vec) scan(i);
}
template <class T>
inline void scan(T &a) {
std::cin >> a;
}
inline void in() {}
template <class Head, class... Tail>
inline void in(Head &head, Tail &...tail) {
scan(head);
in(tail...);
}
inline void print() { std::cout << ' '; }
inline void print(const bool &a) { std::cout << a; }
inline void print(const int32_t &a) { std::cout << a; }
inline void print(const uint32_t &a) { std::cout << a; }
inline void print(const int64_t &a) { std::cout << a; }
inline void print(const uint64_t &a) { std::cout << a; }
inline void print(const char &a) { std::cout << a; }
inline void print(const char a[]) { std::cout << a; }
inline void print(const float &a) { std::cout << a; }
inline void print(const double &a) { std::cout << a; }
inline void print(const long double &a) { std::cout << a; }
inline void print(const std::string &a) {
for (auto &&i : a) print(i);
}
template <class T>
inline void print(const std::vector<T> &vec);
template <class T, size_t size>
inline void print(const std::array<T, size> &vec);
template <class T, class L>
inline void print(const std::pair<T, L> &p);
template <class T, size_t size>
inline void print(const T (&vec)[size]);
template <class T>
inline void print(const std::vector<T> &vec) {
if (vec.empty()) return;
print(vec[0]);
for (auto i = vec.begin(); ++i != vec.end();) {
std::cout << ' ';
print(*i);
}
}
template <class T>
inline void print(const std::deque<T> &vec) {
if (vec.empty()) return;
print(vec[0]);
for (auto i = vec.begin(); ++i != vec.end();) {
std::cout << ' ';
print(*i);
}
}
template <class T, size_t size>
inline void print(const std::array<T, size> &vec) {
print(vec[0]);
for (auto i = vec.begin(); ++i != vec.end();) {
std::cout << ' ';
print(*i);
}
}
template <class T, class L>
inline void print(const std::pair<T, L> &p) {
print(p.first);
std::cout << ' ';
print(p.second);
}
template <class T, size_t size>
inline void print(const T (&vec)[size]) {
print(vec[0]);
for (auto i = vec; ++i != end(vec);) {
std::cout << ' ';
print(*i);
}
}
template <class T>
inline void print(const T &a) {
std::cout << a;
}
inline void out() { std::cout << '\n'; }
template <class T>
inline void out(const T &t) {
print(t);
std::cout << '\n';
}
template <class Head, class... Tail>
inline void out(const Head &head, const Tail &...tail) {
print(head);
std::cout << ' ';
out(tail...);
}
inline void Yes(bool i = true) { out(i ? "Yes" : "No"); }
inline void No(bool i = true) { out(i ? "No" : "Yes"); }
inline void Takahashi(bool i = true) { out(i ? "Takahashi" : "Aoki"); }
inline void Aoki(bool i = true) { out(i ? "Aoki" : "Takahashi"); }
inline void Alice(bool i = true) { out(i ? "Alice" : "Bob"); }
inline void Bob(bool i = true) { out(i ? "Bob" : "Alice"); }
inline void First(bool i = true) { out(i ? "First" : "Second"); }
inline void Second(bool i = true) { out(i ? "Second" : "First"); }
inline void Possible(bool i = true) { out(i ? "Possible" : "Impossible"); }
inline void Impossible(bool i = true) { out(i ? "Impossible" : "Possible"); }
inline void fls() { std::flush(std::cout); }
struct IOsetup {
IOsetup() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << std::fixed << std::setprecision(16);
}
} iosetup;
#line 9 "/root/AtCoder/Halc-Library/Template/Util.hpp"
using ll = int64_t;
using ld = long double;
using ull = uint64_t;
using uint = uint32_t;
using pll = std::pair<ll, ll>;
using pii = std::pair<int32_t, int32_t>;
using vl = std::vector<ll>;
using vvl = std::vector<std::vector<ll>>;
using pdd = std::pair<ld, ld>;
using tuplis = std::array<ll, 3>;
template <class T>
using pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
constexpr ll LINF = (1LL << 62) - (1LL << 31);
constexpr int32_t INF = INT_MAX >> 1;
constexpr ll MINF = 1LL << 40;
constexpr ld DINF = std::numeric_limits<ld>::infinity();
constexpr int32_t MODD = 1000000007;
constexpr int32_t MOD = 998244353;
constexpr ld EPS = 1e-9;
constexpr ld PI = 3.1415926535897932;
const ll four[] = {0, 1, 0, -1, 0};
const ll eight[] = {0, 1, 1, 0, -1, -1, 1, -1, 0};
template <class T>
bool chmin(T &a, const T &b) {
if (a > b) {
a = b;
return true;
} else
return false;
}
template <class T>
bool chmax(T &a, const T &b) {
if (a < b) {
a = b;
return true;
} else
return false;
}
template <class T>
ll sum(const T &a) {
return accumulate(std::begin(a), std::end(a), 0LL);
}
template <class T>
ld dsum(const T &a) {
return accumulate(std::begin(a), std::end(a), 0.0L);
}
template <class T>
auto min(const T &a) {
return *min_element(std::begin(a), std::end(a));
}
template <class T>
auto max(const T &a) {
return *max_element(std::begin(a), std::end(a));
}
#line 1 "/root/AtCoder/Halc-Library/Template/Macro.hpp"
#define _overload3(_1, _2, _3, name, ...) name
#define _overload4(_1, _2, _3, _4, name, ...) name
#define _rep1(i, n) for (int64_t i = 0; i < (n); i++)
#define _rep2(i, a, b) for (int64_t i = (a); i < (b); i++)
#define _rep3(i, a, b, c) for (int64_t i = (a); i < (b); i += (c))
#define rep(...) _overload4(__VA_ARGS__, _rep3, _rep2, _rep1)(__VA_ARGS__)
#define _rrep1(i, n) for (int64_t i = (n) - 1; i >= 0; i--)
#define _rrep2(i, a, b) for (int64_t i = (b) - 1; i >= (a); i--)
#define rrep(...) _overload3(__VA_ARGS__, _rrep2, _rrep1)(__VA_ARGS__)
#define each(i, ...) for (auto&& i : __VA_ARGS__)
#define all(i) std::begin(i), std::end(i)
#define rall(i) std::rbegin(i), std::rend(i)
#define len(x) ((int64_t)(x).size())
#define fi first
#define se second
#define uniq(x) x.erase(unique(all(x)), std::end(x))
#define vec(type, name, ...) vector<type> name(__VA_ARGS__);
#define vv(type, name, h, ...) std::vector<std::vector<type>> name(h, std::vector<type>(__VA_ARGS__));
#define INT(...) int32_t __VA_ARGS__; in(__VA_ARGS__)
#define LL(...) int64_t __VA_ARGS__; in(__VA_ARGS__)
#define ULL(...) uint64_t __VA_ARGS__; in(__VA_ARGS__)
#define STR(...) std::string __VA_ARGS__; in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__; in(__VA_ARGS__)
#define LD(...) long double __VA_ARGS__; in(__VA_ARGS__)
#define VEC(type, name, size) std::vector<type> name(size); in(name)
#define VV(type, name, h, w) std::vector<std::vector<type>> name(h, std::vector<type>(w)); in(name)
#line 2 "main.cpp"
template <class Cap, class Cost, class TotalCost>
struct NetworkSimplex {
private:
struct Edge {
int to;
Cap cap;
Cost cost;
int idx;
};
template <class E>
struct CSR {
struct Range {
std::vector<E>::iterator bg, ed;
std::vector<E>::iterator begin() const { return bg; }
std::vector<E>::iterator end() const { return ed; }
int size() const { return ed - bg; }
E &operator[](int i) const { return bg[i]; }
};
vector<pair<int, E>> given_e;
vector<E> e_elem;
vector<int> pos;
int sz;
CSR(int n) : sz(n), pos(n + 1, 0) {}
void add(int p, E e) {
given_e.emplace_back(p, e);
pos[p + 1]++;
}
void build() {
for (int i = 0; i < sz; i++) pos[i + 1] += pos[i];
e_elem.resize(pos.back());
for (int i = 0; i < pos.back(); i++) {
e_elem[pos[given_e[i].first]] = given_e[i].second;
pos[given_e[i].first]++;
}
for (int i = sz - 1; i >= 0; i--) {
pos[i + 1] = pos[i];
}
pos[0] = 0;
}
Range operator[](int u) {
return Range{e_elem.begin() + pos[u], e_elem.begin() + pos[u + 1]};
}
};
void add_linked(CSR<pair<int, int>> &list, int idx, int pos) {
int last = list[idx][list[idx].size() - 1].first;
list[idx][last].second = pos + 1;
list[idx][list[idx].size() - 1].first = pos + 1;
list[idx][pos + 1].first = last;
list[idx][pos + 1].second = list[idx].size() - 1;
}
void erase_linked(CSR<pair<int, int>> &list, int idx, int pos) {
int left = list[idx][pos + 1].first, right = list[idx][pos + 1].second;
list[idx][left].second = right;
list[idx][right].first = left;
list[idx][pos + 1] = {-1, -1};
}
public:
int n;
TotalCost total_cost = 0;
vector<Cap> lowers;
vector<Cap> b;
CSR<Edge> g;
// vector<vector<Edge>> g;
vector<pair<int, int>> edges;
// b:supply-demand
NetworkSimplex(int sz) : n(sz), g(sz), b(sz) {}
// add supply/demand
void add_excess(int v, Cap c) { b[v] += c; }
// s->t l<=f<=u cost=c
void add_edge(int s, int t, Cap l, Cap u, Cost c) {
lowers.push_back(l);
edges.emplace_back(-1, -1);
total_cost += TotalCost(c) * TotalCost(l);
b[s] -= l;
b[t] += l;
if (s != t) {
edges.back() = {s, g.pos[s + 1]};
g.add(s, {t, u - l, c, g.pos[t + 1]});
g.add(t, {s, 0, -c, g.pos[s + 1] - 1});
} else if (c < 0) {
total_cost += TotalCost(c) * TotalCost(u - l);
lowers.back() += u - l;
}
}
struct FlowResult {
bool feasible;
TotalCost cost;
vector<Cap> flow;
vector<Cost> potential;
};
FlowResult solve() {
int zs = g.pos[1];
for (int i = 1; i < n; i++) {
g.add(0, {i, 0, 0, g.pos[i + 1]});
g.add(i, {0, 0, 0, g.pos[1] - 1});
}
g.build();
vector<int> level(n);
vector<int> iter(n);
int mn;
auto dfs = [&](auto self, int v, Cap f) -> Cap {
if (b[v] < 0) {
b[v] += f;
return f;
}
if (level[v] >= mn) return 0;
for (int &i = iter[v]; i < g[v].size(); i++) {
Edge &e = g[v][i];
if (e.cap == 0 || level[v] >= level[e.to]) continue;
Cap d = self(self, e.to, min(f, e.cap));
if (d > 0) {
e.cap -= d;
g[e.to][e.idx].cap += d;
if (b[v] > 0) {
b[v] -= d;
if (b[v] == 0) return d;
f = min(f, b[v]);
} else {
return d;
}
}
}
return 0;
};
while (true) {
fill(level.begin(), level.end(), -1);
fill(iter.begin(), iter.end(), 0);
queue<int> q;
for (int i = 0; i < n; i++) {
if (b[i] > 0) {
q.push(i);
level[i] = 0;
}
}
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto &e : g[v]) {
if (e.cap > 0 && level[e.to] == -1) {
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
mn = n;
for (int i = 0; i < n; i++) {
if (b[i] < 0 && level[i] != -1) mn = min(mn, level[i]);
}
if (mn == n) break;
stack<pair<int, Cap>> pos;
for (int i = 0; i < n; i++) {
int cnt = 0;
if (b[i] > 0) {
dfs(dfs, i, b[i]);
}
}
}
for (int i = 0; i < n; i++) {
if (b[i] != 0) return {false, 0, {}, {}};
}
fill(level.begin(), level.end(), -1);
for (int i = 0; i < n; i++) {
if (level[i] != -1) continue;
while (true) {
fill(iter.begin(), iter.end(), -1);
stack<int> pos;
iter[i] = 0;
pos.push(i);
vector<pair<int, int>> cycle;
while (!pos.empty()) {
int v = pos.top();
level[v] = 0;
int used = -1;
if (pos.size() > 1) {
pos.pop();
used = g[pos.top()][iter[pos.top()]].idx;
pos.push(v);
}
bool flg = false;
for (int &j = iter[v]; j < g[v].size(); j++) {
Edge &e = g[v][j];
if (e.cap == 0 || g[e.to][e.idx].cap == 0 || j == used)
continue;
if (iter[e.to] == -1) {
iter[e.to] = 0;
pos.push(e.to);
flg = true;
break;
}
if (iter[e.to] < g[e.to].size()) {
while (true) {
int nv = pos.top();
cycle.emplace_back(nv, iter[nv]);
pos.pop();
if (nv == e.to) break;
}
break;
}
}
if (!cycle.empty()) break;
if (flg) continue;
pos.pop();
if (pos.empty()) break;
iter[pos.top()]++;
}
if (cycle.empty()) break;
Cost sm = 0;
Cap mn = numeric_limits<Cap>::max();
for (auto &p : cycle) {
Edge &e = g[p.first][p.second];
sm += e.cost;
mn = min(mn, e.cap);
}
if (sm <= 0) {
for (auto &p : cycle) {
Edge &e = g[p.first][p.second];
e.cap -= mn;
g[e.to][e.idx].cap += mn;
}
} else {
mn = numeric_limits<Cap>::max();
for (auto &p : cycle) {
Edge &e = g[p.first][p.second];
mn = min(mn, g[e.to][e.idx].cap);
}
for (auto &p : cycle) {
Edge &e = g[p.first][p.second];
e.cap += mn;
g[e.to][e.idx].cap -= mn;
}
}
}
}
CSR<pair<int, int>> tree(n);
for (int i = 0; i < n; i++) {
tree.add(i, {-1, g[i].size() + 1});
rep(_, g[i].size()) { tree.add(i, {-1, -1}); }
tree.add(i, {0, -1});
}
tree.build();
fill(level.begin(), level.end(), -1);
vector<Cost> p(n, 0);
vector<int> parent(n, -1);
vector<pair<int, int>> can;
for (int i = 0; i < n; i++) {
if (level[i] != -1) continue;
stack<int> q;
q.push(i);
if (i == 0)
level[i] = 0;
else
level[i] = 1;
p[i] = 0;
if (i != 0) {
parent[i] = g[0][zs + i - 1].idx;
add_linked(tree, 0, zs + i - 1);
add_linked(tree, g[0][zs + i - 1].to, g[0][zs + i - 1].idx);
}
while (!q.empty()) {
int v = q.top();
q.pop();
for (int i = 0; i < g[v].size(); i++) {
Edge &e = g[v][i];
if (e.cap == 0 || g[e.to][e.idx].cap == 0 ||
level[e.to] != -1) {
if (e.cap != 0) {
if (g[e.to][e.idx].cap == 0)
can.emplace_back(v, i);
else
parent[v] = i;
}
continue;
}
level[e.to] = level[v] + 1;
p[e.to] = p[v] + e.cost;
q.push(e.to);
add_linked(tree, v, i);
add_linked(tree, e.to, e.idx);
}
}
}
while (true) {
pair<Cost, int> mn = {numeric_limits<Cost>::max(), -1};
for (int i = 0; i < can.size(); i++) {
Edge &e = g[can[i].first][can[i].second];
if (e.cap == 0) continue;
mn = min(mn, {e.cost + p[can[i].first] - p[e.to], i});
}
if (mn.first >= 0) break;
vector<int> gl = {can[mn.second].first};
int st = g[can[mn.second].first][can[mn.second].second].to;
vector<pair<int, int>> ncyc = {can[mn.second]};
while (st != gl.back()) {
if (level[st] < level[gl.back()]) {
gl.emplace_back(g[gl.back()][parent[gl.back()]].to);
} else {
ncyc.emplace_back(st, parent[st]);
st = g[st][parent[st]].to;
}
}
for (int i = gl.size() - 2; i >= 0; i--) {
ncyc.emplace_back(gl[i + 1], g[gl[i]][parent[gl[i]]].idx);
}
Cap mc = numeric_limits<Cap>::max();
for (auto &i : ncyc) mc = min(mc, g[i.first][i.second].cap);
int del = -1;
for (int i = 0; i < ncyc.size(); i++) {
Edge &e = g[ncyc[i].first][ncyc[i].second];
e.cap -= mc;
if (e.cap == 0) del = i;
g[e.to][e.idx].cap += mc;
}
if (del == 0) {
can[mn.second] = {
g[can[mn.second].first][can[mn.second].second].to,
g[can[mn.second].first][can[mn.second].second].idx};
continue;
}
erase_linked(tree, ncyc[del].first, ncyc[del].second);
erase_linked(tree, g[ncyc[del].first][ncyc[del].second].to,
g[ncyc[del].first][ncyc[del].second].idx);
add_linked(tree, can[mn.second].first, can[mn.second].second);
add_linked(tree, g[can[mn.second].first][can[mn.second].second].to,
g[can[mn.second].first][can[mn.second].second].idx);
can[mn.second] = {g[ncyc[del].first][ncyc[del].second].to,
g[ncyc[del].first][ncyc[del].second].idx};
fill(level.begin(), level.end(), -1);
level[0] = 0;
stack<int> q;
q.push(0);
while (!q.empty()) {
int v = q.top();
q.pop();
int pos = 0;
while (true) {
int np = tree[v][pos].second;
pos = np;
np--;
if (np >= g[v].size()) break;
Edge &e = g[v][np];
if (level[e.to] != -1) {
parent[v] = np;
continue;
}
p[e.to] = p[v] + e.cost;
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
for (int i = 0; i < edges.size(); i++) {
int s = edges[i].first, t = edges[i].second;
if (s == -1) continue;
Edge &e = g[s][t];
lowers[i] += g[e.to][e.idx].cap;
total_cost += TotalCost(e.cost) * TotalCost(g[e.to][e.idx].cap);
}
return {true, total_cost, lowers, p};
}
};
void solve() {
LL(N,M);
VV(ll,A,N,M);
ll day=N/2;
NetworkSimplex<ll,ll,ll> gr(day*2);
rep(i,day){
rep(j,day){
ll mx=0;
rep(k,M){
chmax(mx,A[N-j-1][k]-A[i][k]);
}
gr.add_edge(i,j+day,0,1,-mx);
}
gr.add_excess(i,1);
gr.add_excess(i+day,-1);
}
out(-gr.solve().cost);
}
int main() { solve(); }