Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
t = int(input())
for i in range(t):
l, r = map(int, input().split())
if l * 2 > r:
print(-1, -1)
else:
print(l, l * 2)
Idea: Roms
Tutorial
Tutorial is loading...
Solution 1 (pikmike)
for _ in range(int(input())):
n, k, z = map(int, input().split())
a = [int(x) for x in input().split()]
ans = 0
s = 0
mx = 0
for t in range(z + 1):
pos = k - 2 * t
if pos < 0:
continue
mx = 0
s = 0
for i in range(pos + 1):
if i < n - 1:
mx = max(mx, a[i] + a[i + 1])
s += a[i]
ans = max(ans, s + mx * t)
print(ans)
Solution 2 (pikmike)
for _ in range(int(input())):
n, k, z = map(int, input().split())
a = [int(x) for x in input().split()]
ans = 0
s = 0
mx = 0
for i in range(k + 1):
if i < n - 1:
mx = max(mx, a[i] + a[i + 1])
s += a[i]
if i % 2 == k % 2:
tmp = (k - i) // 2
if tmp <= z:
ans = max(ans, s + mx * tmp)
print(ans)
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)
int solve(const string& s, int x, int y) {
int res = 0;
for (auto c : s) if (c - '0' == x) {
++res;
swap(x, y);
}
if (x != y && res % 2 == 1)
--res;
return res;
}
void solve() {
string s;
cin >> s;
int ans = 0;
forn(x, 10) forn(y, 10)
ans = max(ans, solve(s, x, y));
cout << sz(s) - ans << endl;
}
int main() {
int T;
cin >> T;
while (T--) solve();
}
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
import kotlin.math.*
fun main() {
repeat(readLine()!!.toInt()) {
val (n, k) = readLine()!!.split(' ').map { it.toLong() }
val (l1, r1) = readLine()!!.split(' ').map { it.toLong() }
val (l2, r2) = readLine()!!.split(' ').map { it.toLong() }
var ans = 1e18.toLong()
if (max(l1, l2) <= min(r1, r2)) {
val rem = max(0L, k - n * (min(r1, r2) - max(l1, l2)))
val maxPossible = n * (abs(l1 - l2) + abs(r1 - r2))
ans = min(rem, maxPossible) + max(0L, rem - maxPossible) * 2
} else {
val invest = max(l1, l2) - min(r1, r2)
for (cntInv in 1..n) {
var curAns = invest * cntInv
val maxPossible = (max(r1, r2) - min(l1, l2)) * cntInv
curAns += min(k, maxPossible) + max(0L, k - maxPossible) * 2
ans = min(ans, curAns)
}
}
println(ans)
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (pikmike)
fun gcd(a: Long, b: Long): Long {
if (a == 0L) return b
return gcd(b % a, a)
}
fun main() {
repeat(readLine()!!.toInt()) {
val (m, d, w) = readLine()!!.split(' ').map { it.toLong() }
val w2 = w / gcd(d - 1, w)
val mn = minOf(m, d)
var cnt = mn / w2
println((2 * (mn - w2) - w2 * (cnt - 1)) * cnt / 2)
}
}
Idea: Roms
Tutorial
Tutorial is loading...
Solution 1 (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)
typedef pair<int, int> pt;
const int N = 200 * 1000;
int n;
int l[N], r[N], t[N];
set<pt> st[2];
int main() {
scanf("%d", &n);
forn(i, n) scanf("%d%d%d", &l[i], &r[i], &t[i]), --t[i];
vector<pair<int, pt>> ev;
forn(i, n) {
ev.pb(mp(l[i], mp(0, i)));
ev.pb(mp(r[i], mp(1, i)));
}
sort(all(ev));
int ans = 0;
for (auto it : ev) {
int i = it.y.y;
if (it.y.x) {
int j = t[i];
int k = j ^ 1;
if (st[j].count(mp(r[i], i)) && !st[k].empty()) {
++ans;
st[k].erase(st[k].begin());
}
if (st[j].count(mp(r[i], i))) st[t[i]].erase(mp(r[i], i));
} else {
st[t[i]].insert(mp(r[i], i));
}
}
printf("%d\n", n - ans);
}
Solution 2 (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)
typedef pair<int, int> pt;
const int INF = 1e9;
const int N = 200 * 1000;
int n;
vector<pt> a[2];
struct segtree {
int n;
vector<int> t, ps;
segtree(int n) : n(n) {
t.resize(4 * n, -INF);
ps.resize(4 * n, 0);
}
void push(int v, int l, int r) {
if (l + 1 != r) {
ps[v * 2 + 1] += ps[v];
ps[v * 2 + 2] += ps[v];
}
t[v] += ps[v];
ps[v] = 0;
}
void upd(int v, int l, int r, int pos, int val) {
push(v, l, r);
if (l + 1 == r) {
t[v] = val;
return;
}
int m = (l + r) >> 1;
if (pos < m) upd(v * 2 + 1, l, m, pos, val);
else upd(v * 2 + 2, m, r, pos, val);
t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
}
void add(int v, int l, int r, int L, int R, int val) {
push(v, l, r);
if (L >= R) return;
if (l == L && r == R) {
ps[v] += val;
push(v, l, r);
return;
}
int m = (l + r) >> 1;
add(v * 2 + 1, l, m, L, min(m, R), val);
add(v * 2 + 2, m, r, max(m, L), R, val);
t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
}
int get(int v, int l, int r, int L, int R) {
push(v, l, r);
if (L >= R) return -INF;
if (l == L && r == R)
return t[v];
int m = (l + r) >> 1;
int r1 = get(v * 2 + 1, l, m, L, min(m, R));
int r2 = get(v * 2 + 2, m, r, max(m, L), R);
t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
return max(r1, r2);
}
void upd(int pos, int val) {
return upd(0, 0, n, pos, val);
}
void add(int l, int r, int val) {
return add(0, 0, n, l, r, val);
}
int get(int l, int r) {
return get(0, 0, n, l, r);
}
};
int main() {
scanf("%d", &n);
forn(i, n) {
int l, r, t;
scanf("%d%d%d", &l, &r, &t);
a[t - 1].pb(mp(r, l));
}
forn(i, 2) sort(all(a[i]), [](pt a, pt b) {
if (a.x == b.x) return a.y > b.y;
return a.x < b.x;
});
segtree t1(sz(a[0]) + 1), t2(sz(a[1]) + 1);
t1.upd(0, 0);
t2.upd(0, 0);
int ans = 0;
for (int i = 0, j = 0; i + j < n; ) {
if (i < sz(a[0]) && (j == sz(a[1]) || a[0][i].x <= a[1][j].x)) {
int pos = upper_bound(all(a[1]), mp(a[0][i].y, -INF)) - a[1].begin() + 1;
int cur = t2.get(0, pos) + 1;
ans = max(ans, cur);
t1.upd(i + 1, cur);
t2.add(0, pos, 1);
++i;
} else {
int pos = upper_bound(all(a[0]), mp(a[1][j].y, -INF)) - a[0].begin() + 1;
int cur = t1.get(0, pos) + 1;
ans = max(ans, cur);
t2.upd(j + 1, cur);
t1.add(0, pos, 1);
++j;
}
}
printf("%d\n", ans);
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
typedef long long li;
const int N = 300043;
bool is_bridge[N];
int w[N];
int c[N];
int v[N];
vector<pair<int, int> > g[N];
vector<pair<int, int> > g2[N];
int comp[N];
li sum[N];
li dp[N];
int cnt[N];
int fup[N];
int tin[N];
int T = 0;
li ans[N];
int v1[N], v2[N];
int n, m, k;
int dfs1(int x, int e)
{
tin[x] = T++;
fup[x] = tin[x];
for(auto p : g[x])
{
int y = p.first;
int i = p.second;
if(i == e)
continue;
if(tin[y] != -1)
fup[x] = min(fup[x], tin[y]);
else
{
fup[x] = min(fup[x], dfs1(y, i));
if(fup[y] > tin[x])
is_bridge[i] = true;
}
}
return fup[x];
}
void dfs2(int x, int cc)
{
if(comp[x] != -1)
return;
comp[x] = cc;
cnt[cc] += v[x];
sum[cc] += c[x];
for(auto y : g[x])
if(!is_bridge[y.second])
dfs2(y.first, cc);
}
void process_edge(int x, int y, int m, int weight)
{
li add_dp = dp[y];
if(cnt[y] > 0 && cnt[y] < k)
add_dp = max(0ll, add_dp - weight);
cnt[x] += m * cnt[y];
dp[x] += m * add_dp;
}
void link(int x, int y, int weight)
{
process_edge(x, y, 1, weight);
}
void cut(int x, int y, int weight)
{
process_edge(x, y, -1, weight);
}
void dfs3(int x, int p)
{
dp[x] = sum[x];
for(auto e : g2[x])
{
int i = e.second;
int y = e.first;
if(y == p)
continue;
dfs3(y, x);
link(x, y, w[i]);
}
}
void dfs4(int x, int p)
{
ans[x] = dp[x];
for(auto e : g2[x])
{
int i = e.second;
int y = e.first;
if(y == p)
continue;
cut(x, y, w[i]);
link(y, x, w[i]);
dfs4(y, x);
cut(y, x, w[i]);
link(x, y, w[i]);
}
}
int main()
{
scanf("%d %d %d", &n, &m, &k);
for(int i = 0; i < k; i++)
{
int x;
scanf("%d", &x);
--x;
v[x] = 1;
}
for(int i = 0; i < n; i++)
scanf("%d", &c[i]);
for(int i = 0; i < m; i++)
scanf("%d", &w[i]);
for(int i = 0; i < m; i++)
{
scanf("%d %d", &v1[i], &v2[i]);
--v1[i];
--v2[i];
g[v1[i]].push_back(make_pair(v2[i], i));
g[v2[i]].push_back(make_pair(v1[i], i));
}
for(int i = 0; i < n; i++)
{
tin[i] = -1;
comp[i] = -1;
}
dfs1(0, -1);
int cc = 0;
for(int i = 0; i < n; i++)
if(comp[i] == -1)
dfs2(i, cc++);
for(int i = 0; i < m; i++)
if(is_bridge[i])
{
g2[comp[v1[i]]].push_back(make_pair(comp[v2[i]], i));
g2[comp[v2[i]]].push_back(make_pair(comp[v1[i]], i));
}
dfs3(0, 0);
dfs4(0, 0);
for(int i = 0; i < n; i++)
printf("%lld ", ans[comp[i]]);
puts("");
}