## 代码

/*
* Computer programmers do it byte by byte.
*/

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

template <typename T> void read(T &n) {
char c;
for (; (c = getchar()) < '0' || c > '9';)
;
for (n = c - '0'; (c = getchar()) >= '0' && c <= '9'; (n *= 10) += c - '0')
;
}

typedef int const ic;

static ic N = 100005;

class heap {
private:
std::priority_queue<int> que, buf;

void clear() {
for (; !que.empty() && !buf.empty() && que.top() == buf.top();
que.pop(), buf.pop())
;
}

public:
void push(ic &n) {
if (n)
que.push(n);
}

void erase(ic &n) {
if (n)
buf.push(n);
}

void pop() {
clear();
if (!que.empty())
que.pop();
}

int top() {
clear();
return que.empty() ? 0 : que.top();
}

int top2() {
clear();
if (que.empty())
return 0;
int tmp = que.top(), ret = tmp;
que.pop(), clear();
if (que.empty()) {
que.push(tmp);
return 0;
}
ret += que.top(), que.push(tmp);
return ret;
}
} global;

namespace tree {
int n, nume, h[N], col[N];
int tim, fi[N], dep[N], lca[N << 1][20];
int power[N << 1];
int root, up[N], size[N], mx[N], vis[N];
heap toup[N], me[N];
struct Edge {
int v, nxt;
} e[N << 1];

void add_edge(ic &u, ic &v) {
e[++nume] = (Edge){v, h[u]}, h[u] = nume;
e[++nume] = (Edge){u, h[v]}, h[v] = nume;
}

void dfs(ic &t, ic &fa) {
lca[++tim][0] = t, fi[t] = tim, dep[t] = dep[fa] + 1;
for (int i = h[t]; i; i = e[i].nxt)
if (e[i].v != fa)
dfs(e[i].v, t), lca[++tim][0] = t;
}

void init() {
for (int i = 2; i <= tim; i <<= 1)
++power[i];
for (int i = 1; i <= tim; ++i)
power[i] += power[i - 1];
for (int i = 1; i < 20; ++i)
for (int j = 1; j <= tim; ++j) {
ic k = std::min(tim, j + (1 << i - 1));
lca[j][i] = dep[lca[j][i - 1]] < dep[lca[k][i - 1]] ? lca[j][i - 1]
: lca[k][i - 1];
}
}

int get_lca(ic &u, ic &v) {
ic l = std::min(fi[u], fi[v]), r = std::max(fi[u], fi[v]);
ic len = power[r - l + 1], k = r - (1 << len) + 1;
return dep[lca[l][len]] < dep[lca[k][len]] ? lca[l][len] : lca[k][len];
}

int get_dist(ic &u, ic &v) {
ic lca = get_lca(u, v);
return dep[u] + dep[v] - 2 * dep[lca];
}

int get_size(ic &t, ic &fa) {
int ret = 1;
for (int i = h[t]; i; i = e[i].nxt)
if (!vis[e[i].v] && e[i].v != fa)
ret += get_size(e[i].v, t);
return ret;
}

void get_root(ic &t, ic &fa, ic &tot) {
size[t] = 1, mx[t] = 0;
for (int i = h[t]; i; i = e[i].nxt)
if (!vis[e[i].v] && e[i].v != fa)
get_root(e[i].v, t, tot), size[t] += size[e[i].v],
mx[t] = std::max(mx[t], size[e[i].v]);
(mx[t] = std::max(mx[t], tot - size[t])) < mx[root] && (root = t);
}

void init_heap(ic &t, ic &fa, ic &dep, heap &hp) {
hp.push(dep);
for (int i = h[t]; i; i = e[i].nxt)
if (!vis[e[i].v] && e[i].v != fa)
init_heap(e[i].v, t, dep + 1, hp);
}

void build(int t) {
vis[t] = true;
for (int i = h[t]; i; i = e[i].nxt)
if (!vis[e[i].v])
root = 0,
get_root(e[i].v, 0,
size[e[i].v] < size[t] ? size[e[i].v] : get_size(e[i].v, t)),
up[root] = t, init_heap(e[i].v, t, 1, toup[root]),
me[t].push(toup[root].top()), build(root);
global.push(me[t].top()), global.push(me[t].top2());
}

void modify(int t) {
ic p = t;
if (col[t])
global.erase(me[t].top());
else
global.push(me[t].top());
for (; up[t]; t = up[t]) {
if (col[up[t]])
global.erase(me[up[t]].top());
global.erase(me[up[t]].top2());
me[up[t]].erase(toup[t].top());
if (col[p])
toup[t].erase(get_dist(p, up[t]));
else
toup[t].push(get_dist(p, up[t]));
me[up[t]].push(toup[t].top());
if (col[up[t]])
global.push(me[up[t]].top());
global.push(me[up[t]].top2());
}
col[p] = !col[p];
}
} // namespace tree

int main() {
for (int i = 1, u, v; i < tree::n; ++i)
tree::dfs(1, 0), tree::init(), tree::get_root(1, 0, tree::n),
tree::build(tree::root);
for (int i = 1; i <= tree::n; ++i)
tree::col[i] = 1;
int q;
char c;
scanf(" %c", &c);
if (c == 'G')
printf("%d\n", global.top());
else {
int p;
}
}
return 0;
}


## 题目描述

As we know, DZY loves playing games. One day DZY decided to play with a $n \times m$ matrix. To be more precise, he decided to modify the matrix with exactly $k$ operations.
Each modification is one of the following:

• Pick some row of the matrix and decrease each element of the row by $p$. This operation brings to DZY the value of pleasure equal to the sum of elements of the row before the decreasing.
• Pick some column of the matrix and decrease each element of the column by $p$. This operation brings to DZY the value of pleasure equal to the sum of elements of the column before the decreasing.

DZY wants to know: what is the largest total value of pleasure he could get after performing exactly $k$ modifications? Please, help him to calculate this value.

## 代码

#include <iostream>
#include <queue>
using namespace std;
priority_queue<long long> r, c;
long long n, m, k, p, s, t, ans = -1e18, a[1001][1001], rr[1000001], cc[1000001];
int main()
{
cin >> n >> m >> k >> p;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) cin >> a[i][j];
for (int i = 1; i <= n; ++i) {
long long s = 0;
for (int j = 1; j <= m; ++j) s += a[i][j];
r.push(s);
}
for (int j = 1; j <= m; ++j) {
long long s = 0;
for (int i = 1; i <= n; ++i) s += a[i][j];
c.push(s);
}
for (int i = 1; i <= k; ++i) {
long long u = r.top(); r.pop();
rr[i] = rr[i - 1] + u;
r.push(u - p * m);
u = c.top(); c.pop();
cc[i] = cc[i - 1] + u;
c.push(u - p * n);
}
for (int i = 0; i <= k; ++i) ans = max(ans, rr[i] + cc[k - i] - p * i * (k - i));
cout << ans << endl;
return 0;
}


## 题目描述

You are given a directed acyclic graph with $n$ vertices and $m$ edges. There are no self-loops or multiple edges between any pair of vertices. Graph can be disconnected.
You should assign labels to all vertices in such a way that:

• Labels form a valid permutation of length $n$ – an integer sequence such that each integer from $1$ to $n$ appears exactly once in it.
• If there exists an edge from vertex $v$ to vertex $u$ then $label_v$ should be smaller than $label_u$.
• Permutation should be lexicographically smallest among all suitable.

Find such sequence of labels to satisfy all the conditions.

## 代码

#include <iostream>
#include <queue>
using namespace std;
struct edge { int v, nxt; } e[100001];
int n, m, nume, cnt, h[200001], in[200001], id[200001];
priority_queue<int> que;
void add_edge(int u, int v) {
e[++nume].v = v, e[nume].nxt = h[u], h[u] = nume;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v; cin >> u >> v;
}
for (int i = 1; i <= n; ++i) if (!in[i]) que.push(i);
while (!que.empty()) {
int u = que.top(); que.pop(), id[u] = cnt++;
for (int i = h[u]; i; i = e[i].nxt) {
--in[e[i].v]; if (!in[e[i].v]) que.push(e[i].v);
}
}
for (int i = 1; i <= n; ++i) cout << n - id[i] << ' ';
cout << endl;
return 0;
}


## 题目描述

A new web-design studio, called SMART (Simply Masters of ART), employs two people. The first one is a web-designer and an executive director at the same time. The second one is a programmer. The director is so a nimble guy that the studio has already got $N$ contracts for web site development. Each contract has a deadline $d_i$.
It is known that the programmer is lazy. Usually he does not work as fast as he could. Therefore, under normal conditions the programmer needs $b_i$ of time to perform the contract number $i$. Fortunately, the guy is very greedy for money. If the director pays him $x_i$ dollars extra, he needs only $(b_i-a_ix_i)$ of time to do his job. But this extra payment does not influent other contract. It means that each contract should be paid separately to be done faster. The programmer is so greedy that he can do his job almost instantly if the extra payment is $(b_i/a_i)$ dollars for the contract number $i$.
The director has a difficult problem to solve. He needs to organize programmer’s job and, may be, assign extra payments for some of the contracts so that all contracts are performed in time. Obviously he wishes to minimize the sum of extra payments. Help the director!

## 代码

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
int n, t;
double ans;
struct contract {
int a, b, d;
bool operator < (const contract &t) const {
return a < t.a;
}
} c[100001];
bool cmp(contract a, contract b) {
return a.d < b.d;
}
priority_queue<contract> q;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d%d%d", &c[i].a, &c[i].b, &c[i].d);
}
sort(c + 1, c + n + 1, cmp);
for (int i = 1; i <= n; i++) {
q.push(c[i]);
t += c[i].b;
if (t > c[i].d) {
int delta = t - c[i].d;
while (delta) {
contract tmp = q.top();
q.pop();
if (tmp.b < delta) {
delta -= tmp.b;
ans += tmp.b * 1.0 / tmp.a;
} else {
tmp.b -= delta;
ans += delta * 1.0 / tmp.a;
delta = 0;
q.push(tmp);
}
}
t = c[i].d;
}
}
printf("%.2lf\n", ans);
return 0;
}