Bronze
B1
import sys
sys.stdin = open('word.in', 'r')
sys.stdout = open('word.out', 'w')
n, m = map(int, input().split())
l = 0
for s in input().split():
# print(l, s, len(s))
if l + len(s) > m:
print()
l = 0
if l > 0:
print(' ', end='')
print(s, end='')
l += len(s)
print()
B2
import sys
sys.stdin = open('photo.in', 'r')
sys.stdout = open('photo.out', 'w')
n = int(input())
a = list(map(int, input().split()))
def F(s):
b = [s]
for i in range(len(a)):
b.append(a[i] - b[i])
if len(set(b)) == n and max(b) == n and min(b) == 1:
return ' '.join(map(str, b))
return None
for i in range(1, n):
if F(i):
print(F(i))
B3
import sys
import math
sys.stdin = open('race.in', 'r')
sys.stdout = open('race.out', 'w')
def F(t, x):
if t <= x:
return t * (t + 1) // 2
t += x - 1
t1 = t // 2
t2 = t - t1
return t1 * (t1 + 1) // 2 + t2 * (t2 + 1) // 2 - x * (x - 1) // 2
k, n = map(int, input().split())
for i in range(n):
x = int(input())
L = 0
R = k
while L < R - 1:
M = (L + R) // 2
if F(M, x) >= k:
R = M
else:
L = M
print(R)
Silver
S1
#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[1020];
int b[1020];
int main()
{
freopen("berries.in", "r", stdin);
freopen("berries.out", "w", stdout);
cin >> n >> k;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
sort(a, a + n);
int ans = 0;
for (int i = 1; i <= a[n - 1]; i++)
{
int cnt = 0;
for (int j = 0; j < n; j++)
{
b[j] = a[j] % i;
cnt += a[j] / i;
}
sort(b, b + n);
int sum = 0;
if (cnt >= k)
{
sum = i * k / 2;
}
else if (cnt >= k / 2)
{
sum = (cnt - k / 2) * i;
if (n - (k - cnt) < 0)
{
continue;
}
for (int j = n - (k - cnt); j < n; j++)
{
sum += b[j];
}
}
else
{
int kk = k / 2 - cnt;
if (n - kk - k / 2 < 0)
{
continue;
}
for (int j = n - kk - k / 2; j < n - kk; j++)
{
sum += b[j];
}
}
ans = max(ans, sum);
}
cout << ans << endl;
return 0;
}
S2
import sys
sys.stdin = open('loan.in', 'r')
sys.stdout = open('loan.out', 'w')
n, k, m = map(int, input().split())
L = 1
R = n + 1
def ok(n, x):
s = 0
kk = 0
while kk < k:
d = (n - s) // x
if d <= m:
return (n - s + m - 1) // m + kk <= k
t = (n - s - d * x) // d + 1
t = min(t, k - kk)
kk += t
s += t * d
return s == n
while L < R - 1:
M = (L + R) // 2
if ok(n, M):
L = M
else:
R = M
print(L)
S3
#include <bits/stdc++.h>
using namespace std;
int n, m;
int p[100020];
int x[100020];
int y[100020];
int z[100020];
int f[100020];
int F(int x)
{
return f[x] != x ? f[x] = F(f[x]) : x;
}
void U(int x, int y)
{
x = F(x);
y = F(y);
f[x] = y;
}
bool ok(int M)
{
for (int i = 1; i <= n; i++)
{
f[i] = i;
}
for (int i = 0; i < m; i++)
{
if (z[i] >= M)
{
U(x[i], y[i]);
}
}
for (int i = 1; i <= n; i++)
{
if (F(i) != F(p[i]))
{
return false;
}
}
return true;
}
int main()
{
freopen("wormsort.in", "r", stdin);
freopen("wormsort.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &p[i]);
}
for (int i = 0; i < m; i++)
{
scanf("%d%d%d", &x[i], &y[i], &z[i]);
}
int L = 0;
int R = 1000000001;
while (L < R - 1)
{
int M = (L + R) / 2;
if (ok(M))
{
L = M;
}
else
{
R = M;
}
}
if (L == 1000000000)
{
L = -1;
}
printf("%d\n", L);
return 0;
}
Gold
G1
#include <bits/stdc++.h>
using namespace std;
int n, m, c;
int w[1020];
int d[1020][1020];
vector<int> a[1020];
priority_queue<pair<int, int> > q[1020];
int main()
{
freopen("time.in", "r", stdin);
freopen("time.out", "w", stdout);
cin >> n >> m >> c;
int l = 0;
for (int i = 1; i <= n; i++)
{
cin >> w[i];
l = max(l, w[i]);
}
for (int i = 0; i < m; i++)
{
int x, y, z;
cin >> x >> y;
a[x].push_back(y);
}
q[0].push(make_pair(0, 1));
for (int x = 0; x < 1000; x++)
{
while (q[x].size() > 0)
{
int z = q[x].top().first;
int y = q[x].top().second;
q[x].pop();
if (z != d[x][y])
{
continue;
}
for (int i : a[y])
{
if (d[x + 1][i] < d[x][y] + w[i])
{
d[x + 1][i] = d[x][y] + w[i];
q[x + 1].push(make_pair(d[x + 1][i], i));
}
}
}
}
int ans = 0;
for (int i = 0; i < 1001; i++)
{
ans = max(ans, d[i][1] - c * i * i);
}
cout << ans << endl;
return 0;
}
G2
#include <bits/stdc++.h>
using namespace std;
int n, q;
int v[3000020];
int a[5020];
long long z[5020][5020];
int main()
{
freopen("threesum.in", "r", stdin);
freopen("threesum.out", "w", stdout);
cin >> n >> q;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
v[a[j] + 1000000] = 0;
}
for (int j = i - 1; j > 0; j--)
{
z[j][i] = z[j + 1][i] + z[j][i - 1] - z[j + 1][i - 1];
if (1000000 - a[i] - a[j] >= 0)
{
z[j][i] += v[1000000 - a[i] - a[j]];
}
v[1000000 + a[j]]++;
}
}
for (int i = 0; i < q; i++)
{
int l, r;
cin >> l >> r;
cout << z[l][r] << endl;
}
return 0;
}
G3
注ζιζ©η2δΈͺη©ε½’δΈθ½ζδ»»δ½ιε ηι¨εγ
θΏζ ·ι’ε€ηεΊζ₯εεε θ‘ηη»ζοΌεεε εηη»ζγζδΈΎεε²ηΊΏε³ε―γ
#include <bits/stdc++.h>
using namespace std;
pair<pair<int, int>, int> a[200020];
int m, n;
int l[200020], lc;
long long f[200020];
long long c[200020];
long long G(int x)
{
long long re = 0;
for (int i = x; i > 0; i -= i & -i)
{
re = min(re, c[i]);
}
return re;
}
void R(int x, long long y)
{
for (int i = x; i <= lc; i += i & -i)
{
c[i] = min(c[i], y);
}
}
int Q(int y)
{
return lower_bound(l, l + lc, y) - l + 1;
}
int main()
{
freopen("boards.in", "r", stdin);
freopen("boards.out", "w", stdout);
scanf("%d%d", &m, &n);
long long ans = 0;
for (int i = 0; i < n; i++)
{
scanf("%d%d", &a[i].first.first, &a[i].first.second);
a[i].second = i + 1;
l[lc++] = a[i].first.second;
scanf("%d%d", &a[i + n].first.first, &a[i + n].first.second);
a[i + n].second = -i - 1;
l[lc++] = a[i + n].first.second;
}
sort(a, a + 2 * n);
sort(l, l + lc);
lc = unique(l, l + lc) - l;
for (int i = 0; i < 2 * n; i++)
{
if (a[i].second > 0)
{
f[a[i].second] = G(Q(a[i].first.second));
f[a[i].second] += a[i].first.first + a[i].first.second;
}
else
{
f[-a[i].second] -= a[i].first.first + a[i].first.second;
R(Q(a[i].first.second), f[-a[i].second]);
ans = min(ans, f[-a[i].second]);
}
}
printf("%lld\n", ans + 2 * m);
return 0;
}
Platinum
P1
#include <bits/stdc++.h>
using namespace std;
int n, m;
char s[1020][1020];
vector<int> a[1000020];
int cnt;
const int mod = 1000000007;
int f[1000020];
int c[1000020];
int v[1000020];
int F(int x)
{
return f[x] != x ? f[x] = F(f[x]) : x;
}
void U(int x, int y)
{
x = F(x);
y = F(y);
if (x > y)
{
f[x] = y;
}
else
{
f[y] = x;
}
}
int G(int x)
{
int re = 1;
for (int i: a[x])
{
re = (long long)re * G(i) % mod;
}
return (re + 1) % mod;
}
int main()
{
freopen("cave.in", "r", stdin);
freopen("cave.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
{
scanf("%s", s[i]);
}
for (int i = 0; i < n * m; i++)
{
f[i] = i;
}
for (int i = n - 1; i >= 0; i--)
{
for (int j = 0; j < m; j++)
{
if (s[i][j] == '.' && s[i + 1][j] == '.')
{
U(i * m + j, (i + 1) * m + j);
}
}
for (int j = 1; j < m; j++)
{
if (s[i][j - 1] == '.' && s[i][j] == '.')
{
U(i * m + j - 1, i * m + j);
}
}
for (int j = 0; j < m; j++)
{
if (s[i][j] == '.')
{
if (F(i * m + j) == i * m + j)
{
c[i * m + j] = ++cnt;
}
else
{
c[i * m + j] = c[F(i * m + j)];
}
}
}
for (int j = 0; j < m; j++)
{
if (s[i][j] == '.' && s[i + 1][j] == '.')
{
a[c[i * m + j]].push_back(c[(i + 1) * m + j]);
v[c[(i + 1) * m + j]] = 1;
}
}
}
for (int i = 1; i <= cnt; i++)
{
sort(a[i].begin(), a[i].end());
a[i].resize(unique(a[i].begin(), a[i].end()) - a[i].begin());
}
int ans = 1;
for (int i = 1; i <= cnt; i++)
{
if (v[i] == 0)
{
ans = (long long)ans * G(i) % mod;
}
}
printf("%d\n", ans);
return 0;
}
P2
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int mod = 1000000007;
int p[50020][20][20], q[50020][20][20];
int f[20][20][20];
int g[20][20][20];
void amul(int a[20][20], int b[20][20], int c[20][20])
{
for (int i = 0; i < m; i++)
{
for (int j = 0; j < m; j++)
{
c[i][j] = 0;
}
}
for (int i = 0; i < m; i++)
{
for (int k = 0; k < m; k++)
{
if (a[i][k] == 0)
{
continue;
}
for (int j = 0; j < m; j++)
{
c[i][j] = (c[i][j] + (long long)a[i][k] * b[k][j]) % mod;
}
}
}
}
void bmul(int a[20][20], int b[20][20], int c[20][20])
{
for (int i = 0; i < m; i++)
{
for (int j = 0; j < m; j++)
{
c[i][j] = 0;
}
}
for (int j = 0; j < m; j++)
{
for (int k = 0; k < m; k++)
{
if (b[k][j] == 0)
{
continue;
}
for (int i = 0; i < m; i++)
{
c[i][j] = (c[i][j] + (long long)a[i][k] * b[k][j]) % mod;
}
}
}
}
int a[200020];
int main()
{
freopen("nondec.in", "r", stdin);
freopen("nondec.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++)
{
for (int j = 0; j < m; j++)
{
f[i][j][j] = 1;
g[i][j][j] = 1;
}
for (int j = 0; j <= i; j++)
{
f[i][j][i] += 1;
g[i][j][i] = (g[i][j][i] + (mod - 1) / 2) % mod;
}
}
for (int i = 0; i < m; i++)
{
p[0][i][i] = 1;
q[0][i][i] = 1;
}
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
a[i]--;
bmul(p[i - 1], f[a[i]] , p[i]);
amul(g[a[i]] , q[i - 1], q[i]);
}
int t, l, r;
scanf("%d", &t);
for (int i = 0; i < t; i++)
{
scanf("%d%d", &l, &r);
l--;
int ans = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < m; j++)
{
ans = (ans + (long long)q[l][0][i] * p[r][i][j]) % mod;
}
}
printf("%d\n", ans);
}
// fprintf(stderr, "cnt=%d\n", cnt);
return 0;
}
P3
#include <bits/stdc++.h>
using namespace std;
int n;
pair<pair<int, int>, pair<int, int> > a[200020];
int z[200020];
int y[200020];
int p[200020];
pair<int, int> s[200020];
int ss;
bool judge(pair<int, int> a, pair<int, int> b, pair<int, int> c)
{
// cout << "judge" << endl;
// cout << a.first << ' ' << a.second << endl;
// cout << b.first << ' ' << b.second << endl;
// cout << c.first << ' ' << c.second << endl;
// cout << "return " << ((long long)(b.first - a.first) * (a.second - c.second) <= (long long)(c.first - a.first) * (a.second - b.second)) << endl;
return (long long)(b.first - a.first) * (a.second - c.second) <= (long long)(c.first - a.first) * (a.second - b.second);
}
int gcd(int x, int y)
{
return y ? gcd(y, x % y) : x;
}
int main()
{
freopen("falling.in", "r", stdin);
freopen("falling.out", "w", stdout);
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i].first.first);
a[i].first.second = -i - 1;
}
for (int i = 0; i < n; i++)
{
a[i].second.first = i;
scanf("%d", &a[i].second.second);
a[i].second.second--;
}
sort(a, a + n);
for (int i = 0; i < n; i++)
{
p[a[i].second.first] = i;
y[a[i].second.first] = 1;
}
ss = 0;
for (int i = 0; i < n; i++)
{
while ((ss >= 1 && s[ss - 1].second < a[i].first.second) || (ss >= 2 && judge(s[ss - 2], s[ss - 1], a[i].first)))
{
ss--;
}
s[ss++] = a[i].first;
if (p[a[i].second.second] > i)
{
int L = 0;
int R = ss;
pair<int, int> u = a[p[a[i].second.second]].first;
while (L < R - 1)
{
int M = (L + R) / 2;
// cout << "binary search before " << L << ' ' << R << endl;
if ((ss >= 1 && s[M].second < u.second) || (M >= 1 && judge(s[M - 1], s[M], u)))
{
R = M;
}
else
{
L = M;
}
// cout << "binary search after " << L << ' ' << R << endl;
}
// cout << "query " << L << endl;
if (s[L].second < u.second)
{
z[a[i].second.first] = -1;
}
else
{
z[a[i].second.first] = (u.first - s[L].first);
y[a[i].second.first] = (s[L].second - u.second);
}
}
// for (int i = 0; i < ss; i++)
// {
// cout << s[i].first << ' ' << s[i].second << endl;
// }
// cout << endl;
}
ss = 0;
for (int i = n - 1; i >= 0; i--)
{
a[i].first.first = -a[i].first.first;
a[i].first.second = -a[i].first.second;
}
for (int i = n - 1; i >= 0; i--)
{
while ((ss >= 1 && s[ss - 1].second < a[i].first.second) || (ss >= 2 && judge(s[ss - 2], s[ss - 1], a[i].first)))
{
ss--;
}
s[ss++] = a[i].first;
if (p[a[i].second.second] < i)
{
int L = 0;
int R = ss;
pair<int, int> u = a[p[a[i].second.second]].first;
while (L < R - 1)
{
int M = (L + R) / 2;
if ((ss >= 1 && s[M].second < u.second) || (M >= 1 && judge(s[M - 1], s[M], u)))
{
R = M;
}
else
{
L = M;
}
}
if (s[L].second < u.second)
{
z[a[i].second.first] = -1;
}
else
{
z[a[i].second.first] = (u.first - s[L].first);
y[a[i].second.first] = (s[L].second - u.second);
}
}
}
for (int i = 0; i < n; i++)
{
if (z[i] == -1)
{
printf("%d\n", z[i]);
}
else
{
int g = gcd(z[i], y[i]);
z[i] /= g;
y[i] /= g;
printf("%d/%d\n", z[i], y[i]);
}
}
return 0;
}