Разбор
Tutorial is loading...
Решение (Vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, k;
cin >> n >> k;
set<int> el;
vector<int> ans;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
if (!el.count(x)) {
ans.push_back(i);
el.insert(x);
}
}
if (int(ans.size()) < k) {
cout << "NO\n";
} else {
cout << "YES\n";
for (int i = 0; i < k; ++i)
cout << ans[i] + 1 << " ";
cout << endl;
}
return 0;
}
Разбор
Tutorial is loading...
Решение (Vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
vector<string> s(n);
for (int i = 0; i < n; ++i)
cin >> s[i];
sort(s.begin(), s.end(), [&] (const string &s, const string &t) {
return s.size() < t.size();
});
for (int i = 0; i < n - 1; ++i) {
if (s[i + 1].find(s[i]) == string::npos) {
cout << "NO\n";
return 0;
}
}
cout << "YES\n";
for (auto it : s)
cout << it << endl;
return 0;
}
Разбор
Tutorial is loading...
Решение (Vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int k;
cin >> k;
vector<pair<int, pair<int, int>>> a;
for (int i = 0; i < k; ++i) {
int n;
cin >> n;
vector<int> x(n);
for (int j = 0; j < n; ++j)
cin >> x[j];
int sum = accumulate(x.begin(), x.end(), 0);
for (int j = 0; j < n; ++j)
a.push_back(make_pair(sum - x[j], make_pair(i, j)));
}
stable_sort(a.begin(), a.end());
for (int i = 0; i < int(a.size()) - 1; ++i) {
if (a[i].first == a[i + 1].first && (a[i].second.first != a[i + 1].second.first)) {
cout << "YES" << endl;
cout << a[i + 1].second.first + 1 << " " << a[i + 1].second.second + 1 << endl;
cout << a[i].second.first + 1 << " " << a[i].second.second + 1 << endl;
return 0;
}
}
cout << "NO\n";
return 0;
}
988D - Points and Powers of Two
Разбор
Tutorial is loading...
Решение (Vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
vector<int> x(n);
for (int i = 0; i < n; ++i) {
cin >> x[i];
}
sort(x.begin(), x.end());
vector<int> res = { x[0] };
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 31; ++j) {
int lx = x[i] - (1 << j);
int rx = x[i] + (1 << j);
bool isl = binary_search(x.begin(), x.end(), lx);
bool isr = binary_search(x.begin(), x.end(), rx);
if (isl && isr && int(res.size()) < 3) {
res = { lx, x[i], rx };
}
if (isl && int(res.size()) < 2) {
res = { lx, x[i] };
}
if (isl && int(res.size()) < 2) {
res = { x[i], rx };
}
}
}
cout << int(res.size()) << endl;
for (auto it : res)
cout << it << " ";
cout << endl;
return 0;
}
Разбор
Tutorial is loading...
Решение (Vovuh)
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000 * 1000 * 1000;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
long long n;
cin >> n;
string s = to_string(n);
int ans = INF;
int len = s.size();
for (int i = 0; i < len; ++i) {
for (int j = 0; j < len; ++j) {
if (i == j) continue;
string t = s;
int cur = 0;
for (int k = i; k < len - 1; ++k) {
swap(t[k], t[k + 1]);
++cur;
}
for (int k = j - (j > i); k < len - 2; ++k) {
swap(t[k], t[k + 1]);
++cur;
}
int pos = -1;
for (int k = 0; k < len; ++k) {
if (t[k] != '0') {
pos = k;
break;
}
}
for (int k = pos; k > 0; --k) {
swap(t[k], t[k - 1]);
++cur;
}
long long nn = atoll(t.c_str());
if (nn % 25 == 0)
ans = min(ans, cur);
}
}
if (ans == INF)
ans = -1;
cout << ans << endl;
return 0;
}
Разбор
Tutorial is loading...
Решение (Vovuh)
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000 * 1000 * 1000;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int a, n, m;
cin >> a >> n >> m;
vector<int> rain(a + 1);
vector<pair<int, int>> umb(a + 1, make_pair(INF, -1));
vector<int> costs(m);
for (int i = 0; i < n; ++i) {
int l, r;
cin >> l >> r;
for (int j = l; j < r; ++j)
rain[j] = 1;
}
for (int i = 0; i < m; ++i) {
int x, p;
cin >> x >> p;
costs[i] = p;
umb[x] = min(umb[x], make_pair(p, i));
}
vector<vector<int>> dp(a + 1, vector<int>(m + 1, INF));
dp[0][m] = 0;
for (int i = 0; i < a; ++i) {
for (int j = 0; j <= m; ++j) {
if (dp[i][j] == INF)
continue;
if (rain[i] == 0)
dp[i + 1][m] = min(dp[i + 1][m], dp[i][j]);
if (j < m)
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + costs[j]);
if (umb[i].first != INF)
dp[i + 1][umb[i].second] = min(dp[i + 1][umb[i].second], dp[i][j] + umb[i].first);
}
}
int ans = INF;
for (int i = 0; i <= m; ++i)
ans = min(ans, dp[a][i]);
if (ans == INF)
ans = -1;
cout << ans << endl;
return 0;
}
Решение (step_by_step)
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include <stdio.h>
#include <bits/stdc++.h>
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = l; i < r; i++)
#define repb(i, r, l) for (int i = r; i > l; i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
using namespace std;
inline void setmin(int &x, int y) { if (y < x) x = y; }
inline void setmax(int &x, int y) { if (y > x) x = y; }
inline void setmin(ll &x, ll y) { if (y < x) x = y; }
inline void setmax(ll &x, ll y) { if (y > x) x = y; }
const int N = 2001;
const int inf = (int)1e9 + 1;
const ll big = (ll)1e18 + 1;
const int P = 239;
const int MOD = (int)1e9 + 7;
const int MOD1 = (int)1e9 + 9;
const double eps = 1e-9;
const double pi = atan2(0, -1);
const int ABC = 26;
struct Line
{
ll k, b;
Line() {}
Line(ll k, ll b) : k(k), b(b) {}
ll val(ll x) { return k * x + b; }
};
int cnt_v;
Line tree[N * 4];
void build(int n)
{
cnt_v = 1;
while (cnt_v < n)
cnt_v <<= 1;
rep(i, 0, cnt_v * 2 - 1)
tree[i] = Line(0, inf);
}
void upd(int x, int lx, int rx, int l, int r, Line line)
{
if (lx >= r || l >= rx)
return;
else if (lx >= l && rx <= r)
{
int m = (lx + rx) / 2;
if (line.val(m) < tree[x].val(m))
swap(tree[x], line);
if (rx - lx == 1)
return;
if (line.val(lx) < tree[x].val(lx))
upd(x * 2 + 1, lx, (lx + rx) / 2, l, r, line);
else
upd(x * 2 + 2, (lx + rx) / 2, rx, l, r, line);
}
else
{
upd(x * 2 + 1, lx, (lx + rx) / 2, l, r, line);
upd(x * 2 + 2, (lx + rx) / 2, rx, l, r, line);
}
}
ll get(ll p)
{
int x = p + cnt_v - 1;
ll res = tree[x].val(p);
while (x > 0)
{
x = (x - 1) / 2;
setmin(res, tree[x].val(p));
}
return res;
}
int add[N];
int best[N];
ll dp[N];
int main()
{
//freopen("a.in", "r", stdin);
//freopen("a.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.precision(20);
cout << fixed;
//ll TL = 0.95 * CLOCKS_PER_SEC;
//clock_t time = clock();
int L, n, m;
cin >> L >> n >> m;
rep(i, 0, n)
{
int l, r;
cin >> l >> r;
add[l]++;
add[r]--;
}
rep(i, 1, L + 1)
add[i] += add[i - 1];
fill(best, best + L + 1, inf);
rep(i, 0, m)
{
int x, p;
cin >> x >> p;
setmin(best[x], p);
}
// dp[i] + best[i] * (j - i) = best[i] * j + (dp[i] - best[i] * i)
build(L + 1);
fill(dp, dp + L + 1, inf);
dp[0] = 0;
upd(0, 0, cnt_v, 0 + 1, cnt_v, Line(best[0], dp[0] - best[0] * 0));
rep(i, 1, L + 1)
{
dp[i] = get(i);
if (add[i - 1] == 0)
setmin(dp[i], dp[i - 1]);
upd(0, 0, cnt_v, i + 1, cnt_v, Line(best[i], dp[i] - best[i] * i));
}
cout << (dp[L] != inf ? dp[L] : -1) << "\n";
return 0;
}