Идея: mainyutin, разработка: mainyutin
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using ll = signed long long int;
using namespace std;
void solve() {
ll n, a, b;
cin >> n >> a >> b;
ll ans = n * a;
if (b < 2 * a) {
ans = (n / 2) * b + (n % 2) * a;
}
cout << ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
Идея: ssor96, mainyutin, разработка: Vladosiya
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
using ll = signed long long int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
void solve() {
int n;
ll c, d;
cin >> n >> c >> d;
vl a(n * n);
for (int i = 0; i < n * n; ++i) {
cin >> a[i];
}
sort(all(a));
vl b(n * n);
b[0] = a[0];
for (int i = 1; i < n; ++i) {
b[i] = b[i - 1] + c;
}
for (int i = 1; i < n; ++i) {
for (int j = 0; j < n; ++j) {
b[i * n + j] = b[(i - 1) * n + j] + d;
}
}
sort(all(b));
cout << (a == b ? "YEs" : "nO") << '\n';
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
1955C - Обитатель морских глубин
Идея: ssor96, Vladosiya, разработка: mainyutin
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
using ll = signed long long int;
void solve() {
int n;
ll k;
cin >> n >> k;
deque<ll> dq(n);
for (int i = 0; i < n; ++i) {
cin >> dq[i];
}
while (dq.size() > 1 && k) {
ll mn = min(dq.front(), dq.back());
if (k < 2 * mn) {
dq.front() -= k / 2 + k % 2;
dq.back() -= k / 2;
k = 0;
} else {
dq.front() -= mn;
dq.back() -= mn;
k -= 2 * mn;
}
if (dq.front() == 0) {
dq.pop_front();
}
if (dq.back() == 0) {
dq.pop_back();
}
}
int ans = n - dq.size();
cout << ans + (dq.size() && dq.front() <= k) << '\n';
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
1955D - Неточный поиск подперестановки
Идея: mainyutin, Vladosiya, разработка: mainyutin
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using ll = signed long long int;
#define all(x) (x).begin(), (x).end()
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using namespace std;
void solve() {
int n, m;
size_t k;
cin >> n >> m >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
multiset<int> todo, done, extra;
for (int j = 0; j < m; ++j) {
int b;
cin >> b;
todo.insert(b);
}
for (int j = 0; j < m; ++j) {
if (todo.find(a[j]) != todo.end()) {
todo.erase(todo.find(a[j]));
done.insert(a[j]);
} else {
extra.insert(a[j]);
}
}
int ans = (done.size() >= k);
for (int r = m; r < n; ++r) {
int old = a[r - m];
if (extra.find(old) != extra.end()) {
extra.erase(extra.find(old));
} else if (done.find(old) != done.end()) {
done.erase(done.find(old));
todo.insert(old);
}
if (todo.find(a[r]) != todo.end()) {
todo.erase(todo.find(a[r]));
done.insert(a[r]);
} else {
extra.insert(a[r]);
}
ans += (done.size() >= k);
}
cout << ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
1955E - Длинное инвертирование
Идея: ssor96, разработка: Vladosiya
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using ll = signed long long int;
#define all(x) (x).begin(), (x).end()
using pii = std::array<int, 2>;
using pll = std::array<ll, 2>;
using vi = std::vector<int>;
using vl = std::vector<ll>;
using namespace std;
void solve() {
int n;
string s;
cin >> n >> s;
for (int k = n; k > 0; --k) {
vector<char> t(n), end(n + 1);
for (int i = 0; i < n; ++i) {
t[i] = s[i] - '0';
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
cnt -= end[i];
t[i] ^= (cnt & 1);
if (t[i] == 0) {
if (i + k <= n) {
++end[i + k];
++cnt;
t[i] = 1;
} else {
break;
}
}
}
if (*min_element(all(t)) == 1) {
cout << k << '\n';
return;
}
}
assert(false);
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
Идея: mainyutin, разработка: mainyutin
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
const int N = 201;
int dp[N][N][N];
void precalc() {
dp[0][0][0] = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
for (int k = 0; k < N; ++k) {
int prev = 0;
if (i) prev = max(prev, dp[i - 1][j][k]);
if (j) prev = max(prev, dp[i][j - 1][k]);
if (k) prev = max(prev, dp[i][j][k - 1]);
dp[i][j][k] = prev;
int xr = ((i & 1) * 1) ^ ((j & 1) * 2) ^ ((k & 1) * 3);
if (xr == 0 && (i || j || k)) {
++dp[i][j][k];
}
}
}
}
}
void solve() {
vector<int> cnt(4);
for (int i = 0; i < 4; ++i) {
cin >> cnt[i];
}
cout << dp[cnt[0]][cnt[1]][cnt[2]] + cnt[3] / 2 << '\n';
}
int main() {
precalc();
int t;
cin >> t;
while (t--) {
solve();
}
}
Идея: ZergTricky, разработка: mainyutin
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using ll = signed long long int;
#define all(x) (x).begin(), (x).end()
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<vector<int> > a(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
int ans = 1, g = gcd(a[0][0], a[n - 1][m - 1]);
vector<vector<char> > dp(n, vector<char>(m));
for (int x = 1; x * x <= g; ++x) {
if (g % x > 0) {
continue;
}
vector<int> cand = {x, g / x};
for (int el : cand) {
for (int i = 0; i < n; ++i) {
dp[i].assign(m, 0);
}
dp[0][0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (a[i][j] % el > 0) {
continue;
}
if (!dp[i][j] && i) {
dp[i][j] = (dp[i - 1][j] == 1 ? 1 : 0);
}
if (!dp[i][j] && j) {
dp[i][j] = (dp[i][j - 1] == 1 ? 1 : 0);
}
}
}
if (dp[n - 1][m - 1]) {
ans = max(ans, el);
}
}
}
cout << ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
1955H - Самая безбашенная оборона
Идея: vmanosin7, разработка: mainyutin
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using ll = signed long long int;
#define all(x) (x).begin(), (x).end()
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using namespace std;
const int R = 12, INF = 2e9;
bool check(int x, int n) { return (0 <= x && x < n); }
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<string> gr(n);
for (int i = 0; i < n; ++i) {
cin >> gr[i];
}
vector<pii> cord(k);
vector<int> p(k);
for (int i = 0; i < k; ++i) {
cin >> cord[i].first >> cord[i].second >> p[i];
--cord[i].first;
--cord[i].second;
}
vector<vector<int> > cover(k, vector<int>(R + 1));
for (int i = 0; i < k; ++i) {
int x = cord[i].first;
int y = cord[i].second;
for (int r = 1; r <= R; ++r) {
for (int dx = -r; dx <= r; ++dx) {
for (int dy = -r; dy <= r; ++dy) {
int nx = x + dx;
int ny = y + dy;
if (!check(nx, n) || !check(ny, m)) {
continue;
}
if ((x - nx) * (x - nx) + (y - ny) * (y - ny) <= r * r) {
cover[i][r] += (gr[nx][ny] == '#');
}
}
}
}
}
vector<vector<int> > dp(k + 1, vector<int>(1 << R, -INF));
dp[0][0] = 0;
for (int i = 1; i <= k; ++i) {
for (int mask = 0; mask < (1 << R); ++mask) {
dp[i][mask] = dp[i - 1][mask];
for (int r = 1; r <= R; ++r) {
int j = r - 1;
if (!(mask & (1 << j))) {
continue;
}
dp[i][mask] = max(dp[i][mask], dp[i - 1][mask ^ (1 << j)] +
p[i - 1] * cover[i - 1][r]);
}
}
}
int ans = 0;
for (int mask = 0; mask < (1 << R); ++mask) {
int hp = 0, mlt = 3;
for (int j = 0; j < R; ++j) {
if (mask & (1 << j)) {
hp += mlt;
}
mlt *= 3;
}
for (int i = 0; i <= k; ++i) {
ans = max(ans, dp[i][mask] - hp);
}
}
cout << ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}