KickStart 退役选手 ：）

#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

#define w first
#define s second
typedef pair<int, int> PII;
const int N = 1e5 + 10;

PII cows[N];

int main()
{
int n;
cin >> n;

for (int i = 0; i < n; ++i)
{
cin >> cows[i].w >> cows[i].s;
}

sort(cows, cows + n, [](PII &a, PII &b) {
return a.w + a.s < b.w + b.s;
});

int sum = 0, res = INT_MIN;
for (int i = 0; i < n; ++i)
{
res = max(res, sum - cows[i].s);
sum += cows[i].w;
}

cout << res << endl;
return 0;
}



#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
int dst[2 * N], n, k;
int q[2 * N];

int bfs()
{
memset(dst, -1, sizeof dst);
int hh = 0, tt = 0;
q[0] = n;
dst[n] = 0;

while (hh <= tt)
{
int t = q[ hh ++ ];

if (t == k) return dst[t];

if (t + 1 < N && dst[t + 1] == -1)
{
q[ ++ tt] = t + 1;
dst[t + 1] = dst[t] + 1;
}

if (t - 1 >= 0 && dst[t - 1] == -1)
{
q[ ++ tt] = t - 1;
dst[t - 1] = dst[t] + 1;
}

if (2 * t < N && dst[2 * t] == -1)
{
q[ ++ tt] = 2 * t;
dst[2 * t] = dst[t] + 1;
}
}
return -1;
}

int main()
{
cin >> n >> k;
cout << bfs() << endl;
return 0;
}



#include <iostream>
#include <cstring>
using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second

const int N = 155;
char g[N][N];
int n, m;
PII q[N * N];
int dst[N][N];

int bfs()
{
int sx, sy;
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (g[i][j] == 'K')
sx = i, sy = j;

memset(dst, -1, sizeof dst);
int hh = 0, tt = 0;
q[0] = {sx, sy};
dst[sx][sy] = 0;

while (hh <= tt)
{
PII t = q[ hh ++ ];
for (int i = 0; i < 8; ++i)
{
int x = t.x + dx[i], y = t.y + dy[i];
if (x < 0 || x >= n || y < 0 || y >= m) continue;
if (g[x][y] == '*') continue;
if (dst[x][y] != -1) continue;
if (g[x][y] == 'H') return dst[t.x][t.y] + 1;
q[ ++ tt] = {x, y};
dst[x][y] = dst[t.x][t.y] + 1;
}
}
return -1;
}

int main()
{
cin >> m >> n;
for (int i = 0; i < n; ++i)
cin >> g[i];

cout << bfs() << endl;
return 0;
}


#include <iostream>
using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second
const int N = 1010;
int g[N][N], n;
PII q[N * N];
bool st[N][N];
PII pre[N][N];

void bfs()
{
st[n - 1][n - 1] = true;
q[0] = {n - 1, n - 1};
int hh = 0, tt = 0;
int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

while (hh <= tt)
{
PII t = q[hh ++ ];
for (int i = 0; i < 4; ++i)
{
int x = t.x + dirs[i][0], y = t.y + dirs[i][1];
if (x < 0 || x >= n || y < 0 || y >= n || st[x][y]) continue;
if (g[x][y] == 1) continue;
pre[x][y] = t;
st[x][y] = true;
q[ ++ tt] = {x, y};
}
}

}

int main()
{
cin >> n;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
cin >> g[i][j];

bfs();

PII start(0, 0);
while (true)
{
cout << start.x << " " << start.y << endl;
if (start.x == n - 1 && start.y == n - 1) break;
start = pre[start.x][start.y];
}
return 0;
}



#include <iostream>
using namespace std;

#define x first
#define y second
typedef pair<int, int> PII;
const int N = 1010;

int g[N][N], n;
bool st[N][N];
PII q[N * N];

void bfs(int sx, int sy, bool& has_higher, bool& has_lower)
{
q[0] = {sx, sy};
st[sx][sy] = true;
int hh = 0, tt = 0;

while (hh <= tt)
{
auto t = q[hh ++ ];
for (int i = -1; i <= 1; ++i)
for (int j = -1; j <= 1; ++j)
{
int x = t.x + i, y = t.y + j;
if (x < 0 || x >= n || y < 0 || y >= n) continue;

if (g[x][y] == g[sx][sy])
{
if (!st[x][y])
q[ ++ tt] = {x, y};
st[x][y] = true;
}
else if (g[x][y] > g[sx][sy]) has_higher = true;
else has_lower = true;
}
}
}

int main()
{
cin >> n;

for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
cin >> g[i][j];

int peak = 0, valley = 0;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (!st[i][j])
{
bool has_higher = false, has_lower = false;
bfs(i, j, has_higher, has_lower);
if (!has_higher) ++ peak ;
if (!has_lower) ++ valley ;
}
}
}
cout << peak << " " << valley << endl;
return 0;
}



#### C++ 代码

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

#define x first
#define y second

const int N = 5e3 + 10;
pair<int, int> arr[N];
int f[N];
int n;

int main()
{
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> arr[i].x >> arr[i].y;
}

sort(arr, arr + n);

int len = 0;
f[0] = INT_MIN;
for (int i = 0; i < n; ++i)
{
if (arr[i].y >= f[len]) f[++len] = arr[i].y;
else
{
int l = 1, r = len;
while (l < r)
{
int mid = l + r >> 1;
if (f[mid] >= arr[i].y) r = mid;
else l = mid + 1;
}
f[l] = arr[i].y;
}
}
cout << len << endl;
return 0;
}


#include <iostream>
using namespace std;

#define x first
#define y second
typedef pair<int, int> PII;

const int N = 55;
int g[N][N];
bool st[N][N];
int n, m;
int dirs[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};

int bfs(int sx, int sy)
{
PII q[N * N];
int hh = 0, tt = 0, area = 0;
q[0] = {sx, sy};
st[sx][sy] = true;

while (hh <= tt)
{
PII p = q[hh ++ ];
++area;
for (int i = 0; i < 4; ++i)
{
int x = p.x + dirs[i][0], y = p.y + dirs[i][1];
if (x < 0 || x >= n || y < 0 || y >= m) continue;
if (st[x][y]) continue;
if (g[p.x][p.y] >> i & 1) continue;
q[ ++ tt] = {x, y};
st[x][y] = true;
}
}
return area;
}

int main()
{

cin >> n >> m;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
cin >> g[i][j];

int cnt = 0, area = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (!st[i][j])
{
++cnt;
area = max(area, bfs(i, j));
}

cout << cnt << endl;
cout << area << endl;
return 0;
}


#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long LL;

// pos, digit, flag, zero
LL cnt[15][15][2][2];

LL dp(vector<int>& nums, int sum, int pos, int digit, bool issmall, bool zero)
{
if (pos == nums.size()) return sum;
if (cnt[pos][sum][issmall][zero] != -1) return cnt[pos][sum][issmall][zero];

int upper = issmall ? 9 : nums[pos];

LL res = 0;
for (int i = 0; i <= upper; ++i)
{
res += dp(nums, sum + (digit == i && (!zero || i)), pos + 1,
digit, issmall || (i < upper), zero && (i == 0));
}

return cnt[pos][sum][issmall][zero] = res;
}

vector<LL> solve(int n)
{
vector<int> nums;

if (n == 0) nums.push_back(0);

int t = n;
while (t)
{
nums.push_back(t % 10);
t /= 10;
}

reverse(nums.begin(), nums.end());

vector<LL> ans(10, 0);

for (int i = 0; i < 10; ++i)
{
memset(cnt, -1, sizeof cnt);
ans[i] = dp(nums, 0, 0, i, false, true);
}
return ans;
}

int main()
{
int a, b;
while (scanf("%d%d", &a, &b) != EOF && a != 0 && b != 0)
{
if (a < b) swap(a, b);
auto cnt1 = solve(a), cnt2 = solve(b - 1);
for (int i = 0; i <= 9; ++i)
{
cout << cnt1[i] - cnt2[i] << " ";
}
cout << endl;
}
return 0;
}


#include <iostream>
#include <string>
#include <cstring>
using namespace std;

const int N = 1e5 + 3;
int h[N], e[N], ne[N], idx;

bool find(int x)
{
int k = (x % N + N) % N;
for (int i = h[k]; ~i; i = ne[i])
{
int j = e[i];
if (j == x)
return true;
}
return false;
}

void insert(int x)
{
int k = (x % N + N) % N;
e[idx] = x, ne[idx] = h[k], h[k] = idx ++;
}

int main()
{
int n;
cin >> n;
memset(h, -1, sizeof h);
while (n -- )
{
string op;
int x;
cin >> op >> x;
if (op == "I")
{
insert(x);
}
else
{
if (find(x))
{
cout << "Yes" << endl;
}
else cout << "No" << endl;
}
}
return 0;
}



#include <iostream>
#include <string>
using namespace std;

const int N = 1e5 + 10;
int h[N], ph[N], hp[N], Size;

void heap_swap(int a, int b)
{
swap(ph[hp[a]], ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}

void up(int u)
{
while (u / 2 && h[u / 2] > h[u])
{
heap_swap(u, u / 2);
u /= 2;
}
}

void down(int u)
{
int t = u;
if (u * 2 <= Size && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= Size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
heap_swap(u, t);
down(t);
}
}

int main()
{
int n, m = 0;
cin >> n;
while (n -- )
{
string op;
int k, x;
cin >> op;
if (op == "I")
{
cin >> x;
++m, ++Size;
h[Size] = x;
ph[m] = Size;
hp[Size] = m;
up(Size);
}
else if (op == "PM")
{
cout << h[1] << endl;
}
else if (op == "DM")
{
heap_swap(1, Size--);
down(1);
}
else if (op == "D")
{
cin >> k;
k = ph[k];
heap_swap(k, Size--);
down(k), up(k);
}
else
{
cin >> k >> x;
k = ph[k];
h[k] = x;
down(k), up(k);
}
}
return 0;
}