Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
t = int(input())
for i in range(t):
x, y = map(int, input().split())
if(x - y > 1):
print('YES')
else:
print('NO')
Идея: Neon
Разбор
Tutorial is loading...
Решение (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
const int N = 100 * 1000 + 13;
int n, r;
int a[N];
void solve() {
scanf("%d%d", &n, &r);
forn(i, n) scanf("%d", &a[i]);
sort(a, a + n);
n = unique(a, a + n) - a;
int ans = 0;
for (int i = n - 1; i >= 0; i--)
ans += (a[i] - ans * r > 0);
printf("%d\n", ans);
}
int main() {
int q;
scanf("%d", &q);
forn(i, q) solve();
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
const int INF = int(1e9);
int h, n;
vector<int> p;
inline bool read() {
if(!(cin >> h >> n))
return false;
p.resize(n);
fore(i, 0, n)
cin >> p[i];
return true;
}
inline void solve() {
int ans = 0;
int lf = 0;
fore(i, 0, n) {
if (i > 0 && p[i - 1] > p[i] + 1) {
if (lf > 0)
ans += (i - lf) & 1;
else
ans += 1 - ((i - lf) & 1);
lf = i;
}
}
if (p[n - 1] > 1) {
if (lf != 0)
ans += (n - lf) & 1;
else
ans += 1 - ((n - lf) & 1);
}
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
int tc; cin >> tc;
while(tc--) {
read();
solve();
}
return 0;
}
Идея: Roms
Разбор
Tutorial is loading...
Решение (Roms)
n = int(input())
s = input()
res = n * (n - 1) // 2
for x in range(2):
cur = 1
for i in range(1, n):
if s[i] == s[i - 1]:
cur += 1
else:
res -= cur - x
cur = 1
s = s[::-1]
print(res)
Идея: Roms
Разбор
Tutorial is loading...
Решение (Roms)
#include <bits/stdc++.h>
using namespace std;
void upd(int &a, int b){
a = min(a, b);
}
const int N = 20;
const int M = (1 << N) + 55;
const int INF = int(1e9) + 100;
int a, n;
string s;
int cnt[N][N];
int d[M][N];
int dp[M];
int cntBit[M];
int minBit[M];
int main() {
cin >> n >> a >> s;
int B = (1 << a) - 1;
for(int i = 1; i < s.size(); ++i){
++cnt[s[i] - 'a'][s[i - 1] - 'a'];
++cnt[s[i - 1] - 'a'][s[i] - 'a'];
}
for(int i = 0; i < M; ++i)
dp[i] = INF;
dp[0] = 0;
for(int msk = 1; msk < M; ++msk){
cntBit[msk] = 1 + cntBit[msk & (msk - 1)];
for(int i = 0; i < N; ++i) if((msk >> i) & 1){
minBit[msk] = i;
break;
}
}
for(int msk = 1; msk < M; ++msk)
for(int i = 0; i < a; ++i){
int b = minBit[msk];
d[msk][i] = d[msk ^ (1 << b)][i] + cnt[i][b];
}
for(int msk = 0; msk < (1 << a); ++msk){
for(int i = 0; i < a; ++i){
if((msk >> i) & 1) continue;
//i -> x
int pos = cntBit[msk];
int nmsk = msk | (1 << i);
upd(dp[nmsk], dp[msk] + pos * (d[msk][i] - d[B ^ nmsk][i]));
}
}
cout << dp[B] << endl;
return 0;
}
Идея: Roms
Разбор
Tutorial is loading...
Решение (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = int(3e5) + 99;
int n;
vector <int> g[N];
int d[N];
int dp[N][2];
void dfs(int v, int p){
vector <int> d1;
dp[v][1] = d[v] - 1;
for(auto to : g[v]){
if(to == p) continue;
dfs(to, v);
dp[v][0] = max(dp[v][0], dp[to][0]);
if(g[to].size() > 1){
d1.push_back(dp[to][1]);
dp[v][1] = max(dp[v][1], d[v] + dp[to][1] - 1);
}
}
sort(d1.rbegin(), d1.rend());
int x = d[v] + 1;
for(int i = 0; i < 2; ++i)
if(i < d1.size())
x += d1[i];
dp[v][0] = max(dp[v][0], x);
}
int main() {
int q;
scanf("%d", &q);
for(int qc = 0; qc < q; ++qc){
scanf("%d", &n);
for(int i = 0; i < n; ++i){
g[i].clear();
d[i] = 0;
dp[i][0] = dp[i][1] = 0;
}
for(int i = 0; i < n - 1; ++i){
int u, v;
scanf("%d %d", &u, &v);
--u, --v;
g[u].push_back(v), g[v].push_back(u);
}
if(n <= 2){
printf("%d\n", n);
continue;
}
for(int v = 0; v < n; ++v){
//d[v] = 1;
//for(auto to : g[v])
// d[v] += g[to].size() == 1;
d[v] = g[v].size();
}
int r = -1;
for(int v = 0; v < n; ++v)
if(g[v].size() != 1)
r = v;
dfs(r, r);
printf("%d\n", dp[r][0]);
}
return 0;
}
1238G - Adilbek and the Watering System
Идея: Neon
Разбор
Tutorial is loading...
Решение (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp make_pair
#define forn(i, n) for (int i = 0; i < int(n); ++i)
typedef long long li;
typedef pair<int, int> pt;
const int N = 500 * 1000 + 13;
int n, m, c, c0;
pair<int, pt> a[N];
li solve() {
scanf("%d%d%d%d", &n, &m, &c, &c0);
forn(i, n) scanf("%d%d%d", &a[i].x, &a[i].y.x, &a[i].y.y);
a[n++] = mp(m, mp(0, 0));
sort(a, a + n);
int sum = c0;
map<int, int> q;
q[0] = c0;
li ans = 0;
forn(i, n) {
int x = a[i].x;
int cnt = a[i].y.x;
int cost = a[i].y.y;
int dist = x - (i ? a[i - 1].x : 0);
while (!q.empty() && dist > 0) {
int can = min(q.begin()->y, dist);
ans += q.begin()->x * 1ll * can;
sum -= can;
dist -= can;
q.begin()->y -= can;
if (q.begin()->y == 0) q.erase(q.begin());
}
if (dist > 0)
return -1;
int add = min(c - sum, cnt);
sum += add;
while (add < cnt && !q.empty() && q.rbegin()->x > cost) {
if (cnt - add >= q.rbegin()->y) {
add += q.rbegin()->y;
q.erase(--q.end());
} else {
q.rbegin()->y -= cnt - add;
add = cnt;
}
}
q[cost] += add;
}
return ans;
}
int main() {
int q;
scanf("%d", &q);
forn(i, q) printf("%lld\n", solve());
}