# 某岛

… : "…アッカリ～ン . .. . " .. .
February 15, 2023

# The 1st Universal Cup, Stage 3, Poland

## Problem B. Bars

n 个人排成一排开酒吧，每个人可以选择开或不开，且每个人会去自己以外的左右最近 2 个开业酒吧各 1 次（没有则不去），第 i 个人的酒吧每招待一个顾客得 p_i 元，最大化总利润。

```#include <lastweapon/io>
using namespace lastweapon;

const int N = int(1e6) + 9;

LL f[N]; int p[N];
int n;

int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif

Rush {
RD(n); REP(i, n) RD(p[i]);
fill(f, f+n, 0);
FOR(i, 1, n) {
REP(j, i) checkMax(f[i], f[j] + (LL)(p[i]+p[j]) * (i-j));
}
cout << f[n-1] << endl;
}
}
```

```#include <lastweapon/io>
using namespace lastweapon;

const int N = int(1e6) + 9;

int p[N], s[N], sn;
int n;

LL w(int j, int i) {
return (LL)(p[i]+p[j])*(i-j);
}

bool bad(int a, int b, int c) {
return w(a, b) + w(b, c) <= w(a, c);
}

int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif

Rush {
RD(n); REP(i, n) RD(p[i]);

sn = 0; REP(i, n) {
while (sn > 1 && bad(s[sn-1], s[sn], i)) --sn;;
s[++sn] = i;
}

LL z = 0; REP_1(i, sn) z += w(s[i-1], s[i]);
cout << z << endl;
}
}

```

## Problem C. Ctrl+C Ctrl+V

```#include <lastweapon/io>
using namespace lastweapon;

const int N = int(1e6) + 9;

char p[5] = "ania";
char s[N];
int n, z, c;

int main() {
#ifndef ONLINE_JUDGE
// freopen("in.txt", "r", stdin);
#endif

Rush {
n = strlen(RS(s));
z = 0; c = 0;

int j = 0;
for (int i=0;i<n;++i) {
if (s[i] == p[j]) {
++j; if (j == 4) {
++c;
j = 1;
}
}
else {
z += (c+1)/2; c = 0;
if (s[i] == 'a') j = 1;
else j = 0;
}
}
z += (c+1)/2;
cout << z << endl;
}
}

```

## Problem D. Dazzling Mountain

```#include <lastweapon/io>
using namespace lastweapon;

const int N = int(1e6) + 9;

int n;

void dfs(int u = 1, int p = 0) {
sz[u] = 1;
for (auto v: adj[u]) if (v != p) {
fa[v] = u; dfs(v, u);
sz[u] += sz[v];
}
}

int main() {
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
#endif

Rush {

DO(n-1) {
int a, b; RD(a, b);
}

dfs(); VI z; z.clear();
map<int, VI> H; H[sz[1]].PB(1);

while (true) {
int s = H.begin()->fi; z.PB(s); if (s == 1) break;

do {
auto it = H.end(); --it;
VI U = it->se; H.erase(it);
for (auto u: U) {
for (auto v: adj[u]) if (v != fa[u]) {
H[sz[v]].PB(v);
}
}
} while (SZ(H) != 1);
}

SRT(z); cout << SZ(z) << endl;
for (auto zi : z) printf("%d ", zi);
puts("");
}
}
```

## Problem I. Investors

（参考诗人小 G）

```#include <lastweapon/io>
#include <lastweapon/fenwicktree>
using namespace lastweapon;

const int N = int(6e3) + 9;

int a[N], f[2][N], w[N][N]; VI A; int p = 0, q = 1;
int Q[N], P[N]; int cz, op;
int n, m;

int calc(int l, int r) {
return f[q][l] + w[l+1][r];
}

int left(int a, int b) {
int l = a, r = n;
while (l < r) {
int m = (l + r) / 2;
if (calc(b, m) <= calc(a, m)) {
r = m;
} else {
l = m + 1;
}
}
return l;
}

int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif

Rush {

RD(n, m); A.clear(); REP(i, n) A.PB(RD(a[i]));

if (m >= n-1) {
puts("0");
continue;
}

UNQ(A); REP(i, n) a[i] = LBD(A, a[i]);

REP(i, n) {
fenwick_tree<int> T(SZ(A));
FOR(j, i+1, n) {
w[i][j] = w[i][j-1] + (j-i) - T.sum(a[j]+1);
}
}

FOR(i, 1, n) f[p][i] = w[0][i];

REP_1(s, m) {
swap(p, q); cz = 0, op = 0; Q[0] = s-1;

FOR(i, s, n) {
//f[p][i] = INF; FOR(j, s-1, i) checkMin(f[p][i], calc(j, i))；
while (cz < op && P[cz] <= i) ++cz;
f[p][i] = calc(Q[cz], i);
int j = left(Q[op], i);
while (cz < op && j <= P[op-1]) j = left(Q[--op], i);
P[op] = j; Q[++op] = i;
}
}

cout << f[p][n-1] << endl;
}
}

```

## Problem M. Minor Evil

(上次遇到类似的套路应该是在 Codeforces Round #800 (Div. 1+2) 的 C 题。)

d[i] 现在定义为：i 位置可被删除的最晚时刻。

```#include <lastweapon/io>
using namespace lastweapon;

const int N = int(1e6) + 9;
set<int> Q[N]; VII adj[N]; char s[N]; int d[N];
int n, k;

bool dijkstra() {
REP_1(i, k+1) Q[i].clear();
REP_1(i, n) if (d[i] == k+1) Q[k+1].insert(i);

DWN_1(i, k+1, 2) {
for (auto u: Q[i]) {
int v = e.fi, w = e.se;
if (d[v] < w && w < i) {
if (d[v]) Q[d[v]].erase(Q[d[v]] .find(v));
Q[d[v] = w].insert(v);
}
}
}
}

REP_1(i, n) if (!d[i]) return 0;
return 1;
}

int main() {

#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
#endif

Rush {

REP_1(i, k) {
int a, b; RD(a, b);
}

REP_1(i, n) d[i] = k+1;
Rush d[RD()] = 0;

if (!dijkstra()) {
puts("NIE");
} else {
puts("TAK");
REP(i, k) s[i] = 'N';
REP_1(i, n) s[d[i]-1] = 'T'; s[k] = 0;
puts(s);
}
}
}

```