Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
for _ in range(int(input())):
n, k, x = map(int, input().split())
if x != 1:
print("YES")
print(n)
print(*([1] * n))
elif k == 1 or (k == 2 and n % 2 == 1):
print("NO")
else:
print("YES")
print(n // 2)
print(*([3 if n % 2 == 1 else 2] + [2] * (n // 2 - 1)))
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
pt A, B, C;
inline bool read() {
if(!(cin >> A.x >> A.y))
return false;
cin >> B.x >> B.y;
cin >> C.x >> C.y;
return true;
}
int dist(const pt &A, const pt &B) {
return abs(A.x - B.x) + abs(A.y - B.y);
}
inline void solve() {
cout << (dist(A, B) + dist(A, C) - dist(B, C)) / 2 + 1 << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
int t; cin >> t;
while (t--) {
read();
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
import sys
for _ in range(int(sys.stdin.readline())):
s = [int(c) for c in sys.stdin.readline().strip()]
n = len(s)
m = int(sys.stdin.readline())
l = sys.stdin.readline()
r = sys.stdin.readline()
mx = 0
for i in range(m):
li = int(l[i])
ri = int(r[i])
nmx = mx
for c in range(li, ri + 1):
cur = mx
while cur < n and s[cur] != c:
cur += 1
nmx = max(nmx, cur)
mx = nmx + 1
print("YES" if mx > n else "NO")
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
using li = long long;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
li delta = 0, ans = 0;
li sum = 0, mx = 0;
for (int i = 0; i < n; ++i) {
li x; cin >> x;
sum += x;
mx = max(mx, sum);
if (sum - mx < delta) {
delta = sum - mx;
ans = mx;
}
}
cout << ans << '\n';
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int MOD = int(1e9) + 7;
int add(int a, int b){
a += b;
if (a >= MOD)
a -= MOD;
return a;
}
int main() {
int n, k;
scanf("%d%d", &n, &k);
vector<int> a(n);
forn(i, n) scanf("%d", &a[i]);
int lim = 1;
while (lim * (lim + 1) < k * 2) ++lim;
vector<vector<vector<int>>> dp(2, vector<vector<int>>(2 * lim + 1, vector<int>(k + 1)));
dp[0][lim][0] = 1;
forn(ii, n){
int i = ii & 1;
int ni = i ^ 1;
dp[ni] = vector<vector<int>>(2 * lim + 1, vector<int>(k + 1));
forn(j, 2 * lim + 1) forn(t, k + 1) if (dp[i][j][t]){
forn(z, 2){
int nj = j + z - a[ii];
int nt = t + abs(nj - lim);
if (nt <= k) dp[ni][nj][nt] = add(dp[ni][nj][nt], dp[i][j][t]);
}
}
}
int ans = 0;
for (int t = k & 1; t <= k; t += 2)
ans = add(ans, dp[n & 1][lim][t]);
printf("%d\n", ans);
return 0;
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
fore(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
const int INF = int(1e9);
const li INF64 = li(1e18);
const int LOGN = 19;
const int N = (1 << LOGN) + 555;
struct comp {
double x, y;
comp(double x = .0, double y = .0) : x(x), y(y) {}
inline comp conj() { return comp(x, -y); }
};
inline comp operator +(const comp &a, const comp &b) {
return comp(a.x + b.x, a.y + b.y);
}
inline comp operator -(const comp &a, const comp &b) {
return comp(a.x - b.x, a.y - b.y);
}
inline comp operator *(const comp &a, const comp &b) {
return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
inline comp operator /(const comp &a, const double &b) {
return comp(a.x / b, a.y / b);
}
namespace FFT {
const double PI = acosl(-1.0);
vector<comp> w[LOGN];
vector<int> rv;
void precalc() {
forn(st, LOGN) {
w[st].resize(1 << st);
forn(i, 1 << st) {
double ang = PI / (1 << st) * i;
w[st][i] = comp(cos(ang), sin(ang));
}
}
rv.assign(1 << LOGN, 0);
fore(i, 1, sz(rv))
rv[i] = (rv[i >> 1] >> 1) | ((i & 1) << (LOGN - 1));
}
inline void fft(comp a[N], int n, bool inv) {
int ln = __builtin_ctz(n);
forn(i, n) {
int ni = rv[i] >> (LOGN - ln);
if(i < ni) swap(a[i], a[ni]);
}
for(int st = 0; st < ln; st++) {
int len = 1 << st;
for(int k = 0; k < n; k += (len << 1))
fore(pos, k, k + len) {
comp l = a[pos];
comp r = a[pos + len] * w[st][pos - k];
a[pos] = l + r;
a[pos + len] = l - r;
}
}
if(inv) {
forn(i, n)
a[i] = a[i] / n;
reverse(a + 1, a + n);
}
}
comp aa[N], bb[N], cc[N];
inline void multiply(int a[N], int sza, int b[N], int szb, int c[N], int &szc) {
int ln = 1;
while(ln < (sza + szb)) // sometimes works max(sza, szb)
ln <<= 1;
forn(i, ln)
aa[i] = (i < sza ? a[i] : comp());
forn(i, ln)
bb[i] = (i < szb ? b[i] : comp());
fft(aa, ln, false);
fft(bb, ln, false);
forn(i, ln)
cc[i] = aa[i] * bb[i];
fft(cc, ln, true);
szc = ln;
forn(i, szc)
c[i] = int(cc[i].x + 0.5);
}
}
const int MOD = int(1e9) + 7;
int norm(int a) {
while (a >= MOD)
a -= MOD;
while (a < 0)
a += MOD;
return a;
}
int mul(int a, int b) {
return int(a * 1ll * b % MOD);
}
li l, t;
int n;
vector<int> v;
inline bool read() {
if(!(cin >> l >> t >> n))
return false;
v.resize(n);
fore (i, 0, n)
cin >> v[i];
return true;
}
int mu[N], minD[N];
vector<int> divs[N];
void precalcDivs(int N) {
fore (d, 1, N) {
for (int v = d; v < N; v += d)
divs[v].push_back(d);
}
mu[1] = 1;
fore (d, 2, N) {
if (minD[d] == 0)
minD[d] = d;
if (minD[d] != minD[d / minD[d]])
mu[d] = -mu[d / minD[d]];
for (int v = 2 * d; v < N; v += d) {
if (minD[v] == 0)
minD[v] = d;
}
}
}
int vs[2][N], res[N], ps[N];
li mxk[N];
inline void solve() {
FFT::precalc();
fore (i, 0, n) {
vs[0][v[i]] = 1;
vs[1][v[i]] = 1;
}
int sz = 1 + *max_element(v.begin(), v.end());
int szRes = 0;
FFT::multiply(vs[0], sz, vs[1], sz, res, szRes);
fore (i, 0, szRes) {
if (!(i & 1) && vs[0][i >> 1] > 0)
res[i]--;
if (res[i] > 0) {
ps[i] = 1;
}
}
memset(vs[1], 0, sizeof vs[1]);
fore (i, 0, n)
vs[1][sz - 1 - v[i]] = 1;
FFT::multiply(vs[0], sz, vs[1], sz, res, szRes);
fore (i, sz, szRes) {
if (res[i] > 0) {
ps[i - sz + 1] = 1;
}
}
precalcDivs(2 * sz);
int ans = 0;
for (int i = N - 1; i > 0; i--) {
if (ps[i] > 0)
mxk[i] = max(mxk[i], t * 1ll * i / (2ll * l));
for (int d : divs[i]) {
// ans += mu[d] * (mxk[i] / d);
ans = norm(ans + mu[d] * int((mxk[i] / d) % MOD));
mxk[i / d] = max(mxk[i / d], mxk[i] / d);
}
}
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}