Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
for _ in range(int(input())):
x, y = map(int, input().split())
print("YES" if y >= -1 else "NO")
1989B - Подстрока и подпоследовательность
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string a, b;
cin >> a >> b;
int n = a.size(), m = b.size();
int ans = n + m;
for (int i = 0; i < m; ++i) {
int j = i;
for (auto c : a) {
if (j < m && c == b[j]) ++j;
}
ans = min(ans, n + m - (j - i));
}
cout << ans << '\n';
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n), b(n);
for (auto& x : a) cin >> x;
for (auto& x : b) cin >> x;
int x = 0, y = 0, neg = 0, pos = 0;
for (int i = 0; i < n; ++i) {
if (a[i] > b[i]) {
x += a[i];
} else if (a[i] < b[i]) {
y += b[i];
} else {
neg += (a[i] < 0);
pos += (a[i] > 0);
}
}
int ans = -1e9;
for (int i = -neg; i <= pos; ++i)
ans = max(ans, min(x + i, y + (pos - neg - i)));
cout << ans << '\n';
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (adedalic)
fun main() {
val (n, m) = readln().split(" ").map { it.toInt() }
val a = readln().split(" ").map { it.toInt() }
val b = readln().split(" ").map { it.toInt() }
val c = readln().split(" ").map { it.toInt() }
val mx = a.maxOrNull()!! + 1
val best = IntArray(mx) { 1e9.toInt() }
val calc = IntArray(mx) { 0 }
for (i in a.indices)
best[a[i]] = minOf(best[a[i]], a[i] - b[i])
for (v in 1 until mx)
best[v] = minOf(best[v], best[v - 1])
for (v in 1 until mx)
if (v >= best[v])
calc[v] = 2 + calc[v - best[v]]
var ans = 0L
for (v in c) {
var cur = v
if (cur >= mx) {
val k = (cur - mx + 1 + best[mx - 1]) / best[mx - 1]
ans += 2L * k
cur -= k * best[mx - 1]
}
ans += calc[cur]
}
println(ans)
}
1989E - Расстояние до различных
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int add(int x, int y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
return x;
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
int main()
{
int n;
cin >> n;
int k;
cin >> k;
vector<vector<int>> dp(n + 1, vector<int>(k + 1));
dp[0][0] = 1;
vector<int> sum(k + 1);
sum[0] = 1;
for(int i = 0; i < n; i++)
{
for(int j = 0; j <= k; j++)
{
int& d = dp[i + 1][min(j + 1, k)];
d = add(d, sum[j]);
if(i >= 2 && i != n - 1)
d = add(d, -dp[i - 1][j]);
}
for(int j = 0; j <= k; j++)
sum[j] = add(sum[j], dp[i + 1][j]);
}
cout << dp[n][k] << endl;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
struct edge{
int v, u;
};
vector<vector<int>> g, tg;
vector<int> ord;
vector<char> used;
vector<int> clr;
void ts(int v){
used[v] = true;
for (int u : g[v]) if (!used[u])
ts(u);
ord.push_back(v);
}
void dfs(int v, int k){
clr[v] = k;
for (int u : tg[v]) if (clr[u] == -1)
dfs(u, k);
}
vector<long long> rk, p;
long long sum;
vector<long long*> where;
vector<long long> val;
long long cost(int x){
return x == 1 ? 0ll : x * 1ll * x;
}
int getp(int a){
return a == p[a] ? a : getp(p[a]);
}
void unite(int a, int b){
a = getp(a), b = getp(b);
if (a == b) return;
if (clr[a] != clr[b]) return;
if (rk[a] < rk[b]) swap(a, b);
where.push_back(&sum);
val.push_back(sum);
sum -= cost(rk[a]);
sum -= cost(rk[b]);
sum += cost(rk[a] + rk[b]);
where.push_back(&rk[a]);
val.push_back(rk[a]);
rk[a] += rk[b];
where.push_back(&p[b]);
val.push_back(p[b]);
p[b] = a;
}
vector<edge> e;
vector<long long> ans;
void calc(int l, int r, const vector<int> &cur){
if (l == r - 1){
ans.push_back(sum);
return;
}
int m = (l + r) / 2;
for (int i : cur) if (i < m){
int v = getp(e[i].v), u = getp(e[i].u);
for (int w : {v, u}) if (used[w]){
g[w].clear();
tg[w].clear();
clr[w] = -1;
used[w] = false;
}
g[v].push_back(u);
tg[u].push_back(v);
}
ord.clear();
for (int i : cur) if (i < m){
for (int v : {getp(e[i].v), getp(e[i].u)}) if (!used[v]){
ts(v);
}
}
reverse(ord.begin(), ord.end());
int k = 0;
for (int v : ord) if (clr[v] == -1){
dfs(v, k);
++k;
}
int tim = val.size();
for (int i : cur) if (i < m) unite(e[i].v, e[i].u);
vector<int> tol, tor;
for (int i : cur){
if (i >= m)
tor.push_back(i);
else if (getp(e[i].v) == getp(e[i].u))
tol.push_back(i);
else
tor.push_back(i);
}
calc(m, r, tor);
while (int(val.size()) > tim){
*where.back() = val.back();
where.pop_back();
val.pop_back();
}
calc(l, m, tol);
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int n, m, q;
cin >> n >> m >> q;
e.resize(q);
forn(i, q){
int x, y;
char c;
cin >> x >> y >> c;
--x, --y;
if (c == 'R')
e[i] = {y + n, x};
else
e[i] = {x, y + n};
}
rk.resize(n + m, 1);
p.resize(n + m);
iota(p.begin(), p.end(), 0);
used.resize(n + m, 0);
clr.resize(n + m, -1);
g.resize(n + m);
tg.resize(n + m);
vector<int> cur(q);
iota(cur.begin(), cur.end(), 0);
calc(0, q + 1, cur);
ans.pop_back();
reverse(ans.begin(), ans.end());
for (long long x : ans) cout << x << '\n';
return 0;
}