Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int t;
cin >> t;
forn(tt, t) {
int a, b, c, x, y;
cin >> a >> b >> c >> x >> y;
int ax = min(a, x);
int by = min(b, y);
a -= ax;
x -= ax;
b -= by;
y -= by;
if (c >= x + y)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin >> n;
vector<int>a(n);
for(auto &i : a) cin >> i;
int ans = 0;
for(int i = n - 2; i >= 0; i--){
while(a[i] >= a[i + 1] && a[i] > 0){
a[i] /= 2;
ans++;
}
if(a[i] == a[i+1]){
cout << -1 << '\n';
return;
}
}
cout << ans << '\n';
}
int main(){
int t;
cin >> t;
while(t--){
solve();
}
}
Idea: Gol_D
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int t;
cin >> t;
forn(tt, t) {
string s;
cin >> s;
int n = s.length();
vector<bool> a(n + 1);
a[0] = true;
forn(i, n)
a[i + 1] = a[i] && (s[i] == '1' || s[i] == '?');
vector<bool> b(n + 1);
b[0] = true;
for (int i = n - 1; i >= 0; i--)
b[n - i] = b[n - i - 1] && (s[i] == '0' || s[i] == '?');
int result = 0;
forn(i, n)
if (a[i] && b[n - i - 1])
result++;
cout << result << endl;
}
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin >> n;
vector<int>b(n + 1);
vector<bool>leaf(n + 1, true);
for(int i = 1; i <= n; i++) {
cin >> b[i];
leaf[b[i]] = false;
}
if(n == 1){
cout << "1\n1\n1\n\n";
return;
}
vector<int>paths[n + 1];
vector<bool>used(n + 1, false);
int color = 0;
for(int i = 1; i <= n; i++){
if(!leaf[i]) continue;
used[i] = true;
paths[color].emplace_back(i);
int v = i;
while (b[v] != v && !used[b[v]]){
v = b[v];
used[v] = true;
paths[color].emplace_back(v);
}
color++;
}
cout << color << '\n';
for(auto &path : paths){
if(path.empty()) continue;
cout << (int)path.size() << '\n';
reverse(path.begin(), path.end());
for(auto &v: path) cout << v << ' ';
cout << '\n';
}
cout << '\n';
}
int main(){
int t;
cin >> t;
while(t--){
solve();
}
}
1675E - Replace With the Previous, Minimize
Idea: myav
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define eb emplace_back
template <class T> bool ckmax(T &a, T b) {return a<b ? a=b, true : false;}
void solve() {
int n,k; cin >> n >> k;
string s; cin >> s;
char mn = 'a';
for (int i = 0; i < n; i++) if(s[i] > mn) {
if (s[i] - 'a' > k) {
k -= mn - 'a';
int to = s[i] - k;
for (char c = s[i]; c > to; c--) {
for (char &e:s) if (e == c) {
e = char(c-1);
}
}
break;
} else ckmax(mn, s[i]);
}
for (char &e:s) if (e <= mn) {
e = 'a';
}
cout << s << endl;
}
int main() {
int t;
cin >> t;
forn(tt, t) {
solve();
}
}
1675F - Vlad and Unfinished Business
Idea: Vladosiya
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
//#define double long double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
const int MOD = 1e9 + 7;
const int maxN = 5e3 + 1;
const int INF = 2e9;
const int MB = 20;
vector<vector<int>> g;
vector<bool> todo, good;
void dfs(int v, int p = -1) {
for (int u : g[v]) {
if (u != p) {
dfs(u, v);
if (todo[u]) {
todo[v] = true;
}
if (good[u]) {
good[v] = true;
}
}
}
}
void solve() {
int n, k;
cin >> n >> k;
g.clear();
g.resize(n);
int x, y;
cin >> x >> y;
--x;
--y;
todo.resize(n);
fill(all(todo), false);
good.resize(n);
fill(all(good), false);
for (int i = 0; i < k; ++i) {
int v;
cin >> v;
--v;
todo[v] = true;
}
good[y] = true;
for (int i = 0; i < n - 1; ++i) {
int v, u;
cin >> v >> u;
--v;
--u;
g[v].push_back(u);
g[u].push_back(v);
}
dfs(x);
int ans = 0;
for (int i = 0; i < n; ++i) {
if (i == x) {
continue;
}
if (good[i]) {
++ans;
} else if (todo[i]) {
ans += 2;
}
}
cout << ans << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// srand(time(0));
int t = 1;
cin >> t;
while (t--) solve();
}
Idea: Vladosiya
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
//#define int long long
#define mp make_pair
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
typedef long double ld;
typedef long long ll;
using namespace std;
mt19937 rnd(143);
const ll inf = 1e9 + 7;
const ll M = 998'244'353;
const ld pi = atan2(0, -1);
const ld eps = 1e-4;
void solve(int test_case) {
int n, m;
cin >> n >> m;
vector<int> a(n), pancakes(1);
for(int &e: a) cin >> e;
for(int i = 0; i < n; ++i){
for(int j = 0; j < a[i]; ++j){
pancakes.emplace_back(i);
int c = pancakes.size();
pancakes[c - 1] += pancakes[c - 2];
}
if(i > 0) a[i] += a[i - 1];
}
vector<vector<vector<int>>> dp(n, vector<vector<int>>(m + 1, vector<int>(m + 1, inf)));
for(int j = 0; j <= m; j++){
if(a[0] >= j) dp[0][j][j] = a[0] - j;//moved right
else dp[0][j][j] = pancakes[j];//moved from right
}
for(int j = m - 1; j >= 0; --j){
for(int k = j; k <= m; ++k){
dp[0][j][k] = min(dp[0][j][k], dp[0][j + 1][k]);
}
}
for(int i = 1; i < n; ++i){
for(int j = 0; j <= m; ++j){
for(int k = j; k <= m; ++k){
int add = 0;
if(a[i] >= k) add = a[i] - k;//moved to i + 1
else {
int lend = min(j, k - a[i]);
add = pancakes[k] - pancakes[k - lend] - i * (lend);//moved from greater i
}
dp[i][j][k] = dp[i - 1][j][k - j] + add;
}
}
for(int j = m - 1; j >= 0; --j){
for(int k = (i + 1) * j; k <= m; ++k){
dp[i][j][k] = min(dp[i][j][k], dp[i][j + 1][k]);
}
}
}
cout << dp[n-1][0][m];
}
bool multi = false;
signed main() {
int t = 1;
if (multi) {
cin >> t;
}
for (int i = 1; i <= t; ++i) {
solve(i);
cout << "\n";
}
return 0;
}