All ideas belong to MikeMirzayanov.
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto &it : a) cin >> it;
sort(a.begin(), a.end());
bool ok = true;
for (int i = 1; i < n; ++i) {
ok &= (a[i] - a[i - 1] <= 1);
}
if (ok) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n), b(n);
for (auto &it : a) cin >> it;
for (auto &it : b) cin >> it;
int mna = *min_element(a.begin(), a.end());
int mnb = *min_element(b.begin(), b.end());
long long ans = 0;
for (int i = 0; i < n; ++i) {
ans += max(a[i] - mna, b[i] - mnb);
}
cout << ans << endl;
}
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> cnt(n + 1);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
++cnt[x];
}
int ans = 0;
for (int s = 2; s <= 2 * n; ++s) {
int cur = 0;
for (int i = 1; i < (s + 1) / 2; ++i) {
if (s - i > n) continue;
cur += min(cnt[i], cnt[s - i]);
}
if (s % 2 == 0) cur += cnt[s / 2] / 2;
ans = max(ans, cur);
}
cout << ans << endl;
}
return 0;
}
1399D - Binary String To Subsequences
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n;
string s;
cin >> n >> s;
vector<int> ans(n);
vector<int> pos0, pos1;
for (int i = 0; i < n; ++i) {
int newpos = pos0.size() + pos1.size();
if (s[i] == '0') {
if (pos1.empty()) {
pos0.push_back(newpos);
} else {
newpos = pos1.back();
pos1.pop_back();
pos0.push_back(newpos);
}
} else {
if (pos0.empty()) {
pos1.push_back(newpos);
} else {
newpos = pos0.back();
pos0.pop_back();
pos1.push_back(newpos);
}
}
ans[i] = newpos;
}
cout << pos0.size() + pos1.size() << endl;
for (auto it : ans) cout << it + 1 << " ";
cout << endl;
}
return 0;
}
1399E1 - Weights Division (easy version)
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
vector<int> w, cnt;
vector<vector<pair<int, int>>> g;
long long getdiff(int i) {
return w[i] * 1ll * cnt[i] - (w[i] / 2) * 1ll * cnt[i];
}
void dfs(int v, int p = -1) {
if (g[v].size() == 1) cnt[p] = 1;
for (auto [to, id] : g[v]) {
if (id == p) continue;
dfs(to, id);
if (p != -1) cnt[p] += cnt[id];
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n;
long long s;
cin >> n >> s;
w = cnt = vector<int>(n - 1);
g = vector<vector<pair<int, int>>>(n);
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y >> w[i];
--x, --y;
g[x].push_back({y, i});
g[y].push_back({x, i});
}
dfs(0);
set<pair<long long, int>> st;
long long cur = 0;
for (int i = 0; i < n - 1; ++i) {
st.insert({getdiff(i), i});
cur += w[i] * 1ll * cnt[i];
}
cerr << cur << endl;
int ans = 0;
while (cur > s) {
int id = st.rbegin()->second;
st.erase(prev(st.end()));
cur -= getdiff(id);
w[id] /= 2;
st.insert({getdiff(id), id});
++ans;
}
cout << ans << endl;
}
return 0;
}
1399E2 - Weights Division (hard version)
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n;
vector<int> w, c, cnt;
vector<vector<pair<int, int>>> g;
long long getdiff(int i) {
return w[i] * 1ll * cnt[i] - (w[i] / 2) * 1ll * cnt[i];
}
void dfs(int v, int p = -1) {
if (g[v].size() == 1) cnt[p] = 1;
for (auto [to, id] : g[v]) {
if (id == p) continue;
dfs(to, id);
if (p != -1) cnt[p] += cnt[id];
}
}
vector<long long> get(int clr) {
set<pair<long long, int>> st;
long long cur = 0;
for (int i = 0; i < n - 1; ++i) {
if (c[i] == clr) {
st.insert({getdiff(i), i});
cur += w[i] * 1ll * cnt[i];
}
}
vector<long long> res;
res.push_back(cur);
while (cur > 0 && !st.empty()) {
int id = st.rbegin()->second;
st.erase(prev(st.end()));
cur -= getdiff(id);
res.push_back(cur);
w[id] /= 2;
st.insert({getdiff(id), id});
}
return res;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
long long s;
cin >> n >> s;
w = c = cnt = vector<int>(n - 1);
g = vector<vector<pair<int, int>>>(n);
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y >> w[i] >> c[i];
--x, --y;
g[x].push_back({y, i});
g[y].push_back({x, i});
}
dfs(0);
vector<long long> v1 = get(1), v2 = get(2);
int pos = int(v2.size()) - 1;
int ans = INF;
for (int i = 0; i < int(v1.size()); ++i) {
while (pos > 0 && v1[i] + v2[pos - 1] <= s) --pos;
if (v1[i] + v2[pos] <= s) {
ans = min(ans, i + pos * 2);
}
}
cout << ans << endl;
}
return 0;
}
1399F - Yet Another Segments Subset
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> rg;
vector<vector<int>> dp;
int calc(int l, int r) {
if (dp[l][r] != -1) return dp[l][r];
dp[l][r] = 0;
if (l > r) return dp[l][r];
bool add = count(rg[l].begin(), rg[l].end(), r); // can't be greater than 1
dp[l][r] = max(dp[l][r], add + (l + 1 > r ? 0 : calc(l + 1, r)));
for (auto nr : rg[l]) {
if (nr >= r) continue;
dp[l][r] = max(dp[l][r], add + calc(l, nr) + (nr + 1 > r ? 0 : calc(nr + 1, r)));
}
return dp[l][r];
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> l(n), r(n);
vector<int> val;
for (int i = 0; i < n; ++i) {
cin >> l[i] >> r[i];
val.push_back(l[i]);
val.push_back(r[i]);
}
sort(val.begin(), val.end());
val.resize(unique(val.begin(), val.end()) - val.begin());
for (int i = 0; i < n; ++i) {
l[i] = lower_bound(val.begin(), val.end(), l[i]) - val.begin();
r[i] = lower_bound(val.begin(), val.end(), r[i]) - val.begin();
}
int siz = val.size();
dp = vector<vector<int>>(siz, vector<int>(siz, -1));
rg = vector<vector<int>>(siz);
for (int i = 0; i < n; ++i) {
rg[l[i]].push_back(r[i]);
}
cout << calc(0, siz - 1) << endl;
}
return 0;
}