**Editorial**

Tutorial is loading...

**Solution (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, m;
cin >> n >> m;
vector<int> cnt(n);
for (int i = 0; i < m; ++i) {
int col;
cin >> col;
++cnt[col - 1];
}
cout << *min_element(cnt.begin(), cnt.end()) << endl;
return 0;
}
```

**Editorial**

Tutorial is loading...

**Solution (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;
scanf("%d %d", &n, &k);
vector<int> a(n);
vector<int> t(n);
int overall = 0;
for (int i = 0; i < n; ++i)
scanf("%d", &a[i]);
for (int i = 0; i < n; ++i)
scanf("%d", &t[i]);
vector<int> pr(n);
for (int i = 0; i < n; ++i) {
if (i) pr[i] += pr[i - 1];
if (t[i] == 0) pr[i] += a[i];
else overall += a[i];
}
int add = 0;
for (int i = k - 1; i < n; ++i)
add = max(add, pr[i] - (i >= k ? pr[i - k] : 0));
printf("%d\n", overall + add);
return 0;
}
```

**Editorial**

Tutorial is loading...

**Solution (Ajosteen)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = 109;
int n;
string a[4][N];
int main() {
cin >> n;
for(int k = 0; k < 4; ++k)
for(int i = 0; i < n; ++i){
cin >> a[k][i];
for(int j = 0; j < n; ++j)
a[k][i][j] -= '0';
}
vector <int> v;
for(int k = 0; k < 4; ++k){
int sum = 0;
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
if((i + j) % 2 != a[k][i][j])
++sum;
v.push_back(sum);
}
int res = int(1e9);
vector <int> perm;
for(int k = 0; k < 4; ++k) perm.push_back(k);
do{
int sum = 0;
for(int k = 0; k < 4; ++k){
int id = perm[k];
if(k & 1)
sum += v[id];
else
sum += n * n - v[id];
}
res = min(res, sum);
}while(next_permutation(perm.begin(), perm.end()));
cout << res << endl;
}
```

**Editorial**

Tutorial is loading...

**Solution (adedalic)**

```
#include <bits/stdc++.h>
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define all(a) (a).begin(), (a).end()
#define sz(a) int(a.size())
#define mp make_pair
#define x first
#define y second
using namespace std;
typedef long long li;
typedef pair<int, int> pt;
inline pt operator -(const pt &a, const pt &b) {
return {a.x - b.x, a.y - b.y};
}
inline li cross(const pt &a, const pt &b) {
return a.x * 1ll * b.y - a.y * 1ll * b.x;
}
const int N = 200 * 1000 + 555;
int n;
pt p[N];
inline bool read() {
if(!(cin >> n))
return false;
fore(i, 0, n)
scanf("%d%d", &p[i].x, &p[i].y);
return true;
}
bool used[N];
bool check() {
int i1 = -1, i2 = -1;
fore(i, 0, n) {
if(used[i])
continue;
if(i1 == -1)
i1 = i;
else if(i2 == -1)
i2 = i;
}
if(i2 == -1)
return true;
fore(i, 0, n) {
if(used[i])
continue;
if(cross(p[i2] - p[i1], p[i] - p[i1]) != 0)
return false;
}
return true;
}
bool check2(pt a, pt b) {
memset(used, 0, sizeof used);
fore(i, 0, n)
if(cross(b - a, p[i] - a) == 0)
used[i] = 1;
return check();
}
inline void solve() {
if(n <= 2) {
puts("YES");
return;
}
if(check2(p[0], p[1]) || check2(p[0], p[2]) || check2(p[1], p[2]))
puts("YES");
else
puts("NO");
}
int main(){
if(read()) {
solve();
}
return 0;
}
```

**Editorial**

Tutorial is loading...

**Solution (Ajosteen)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = 200 * 1000 + 9;
int n;
int a[N];
int f[N];
vector <int> v[N];
void upd(int pos, int d){
for(; pos < N; pos |= pos + 1)
f[pos] += d;
}
int get(int pos){
int res = 0;
for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
res += f[pos];
return res;
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n; ++i){
scanf("%d", a + i);
--a[i];
}
for(int i = 0; i < n; ++i){
if(a[i] < N)
v[a[i]].push_back(i);
upd(i, 1);
}
long long res = 0;
for(int i = 0; i < n; ++i){
int to = min(N - 1, a[i]);
res += get(to);
for(auto x : v[i])
upd(x, -1);
}
for(int i = 0; i < n; ++i)
if(i <= a[i])
--res;
assert(res % 2 == 0);
cout << res / 2 << endl;
}
```

**Editorial**

Tutorial is loading...

**Alternative solution (jtnydv25)**

**Solution (adedalic, suffix array)**

```
#include <bits/stdc++.h>
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define all(a) (a).begin(), (a).end()
#define sz(a) int(a.size())
#define mp make_pair
#define x first
#define y second
using namespace std;
typedef pair<int, int> pt;
const int LOGN = 21;
const int N = 1000 * 1000 + 555;
int n;
string s;
inline bool read() {
if(!(cin >> n))
return false;
char buf[N];
assert(scanf("%s", buf) == 1);
s = buf;
return true;
}
pair<pt, int> d[N], curP[N];
int szd = 0;
int cnt[N], szcnt;
int rdp[N];
inline void radix_sort() {
fore(k, 0, 2) {
szcnt = 0;
fore(i, 0, szd) {
int val = k == 0 ? d[i].x.y : d[i].x.x;
while(szcnt <= val)
cnt[szcnt++] = 0;
cnt[val]++;
}
int sum = 0;
fore(i, 0, szcnt) {
rdp[i] = sum;
sum += cnt[i];
}
fore(i, 0, szd) {
int val = k == 0 ? d[i].x.y : d[i].x.x;
curP[rdp[val]++] = d[i];
}
fore(i, 0, szd)
d[i] = curP[i];
}
}
int c[N], id[N];
int lcp[N];
int lg[N];
int st[LOGN][N];
void precalc() {
s += '$';
for(int len = 1; len < 2 * sz(s); len <<= 1) {
szd = 0;
fore(i, 0, sz(s)) {
int sh = len >> 1;
d[szd++] = {len == 1 ? mp((int)s[i], 0) : mp(c[i], c[(i + sh) % sz(s)]), i};
}
radix_sort();
c[d[0].y] = 0;
fore(i, 1, szd)
c[d[i].y] = c[d[i - 1].y] + (d[i - 1].x != d[i].x);
if(c[d[szd - 1].y] == sz(s) - 1)
break;
}
fore(i, 0, sz(s)) {
c[i]--;
if(c[i] >= 0) id[c[i]] = i;
}
s.pop_back();
int l = 0;
fore(i1, 0, n) {
l = max(l - 1, 0);
if(c[i1] == n - 1)
continue;
int i2 = id[c[i1] + 1];
while(i1 + l < n && i2 + l < n && s[i1 + l] == s[i2 + l])
l++;
lcp[c[i1]] = l;
}
lg[0] = 0;
fore(i, 1, N) {
lg[i] = lg[i - 1];
if((1 << (lg[i] + 1)) <= i)
lg[i]++;
}
fore(pw, 0, LOGN) {
if(pw == 0) {
fore(i, 0, n)
st[pw][i] = lcp[i];
continue;
}
fore(i, 0, n) {
st[pw][i] = st[pw - 1][i];
if(i + (1 << (pw - 1)) < n)
st[pw][i] = min(st[pw][i], st[pw - 1][i + (1 << (pw - 1))]);
}
}
}
inline int getMin(int l, int r) {
if(l >= r) swap(l, r);
int len = lg[r - l];
return min(st[len][l], st[len][r - (1 << len)]);
}
inline bool eq(int i1, int i2, int l) {
if(i1 == i2) return true;
return getMin(c[i1], c[i2]) >= l;
}
int l[N], mx[N];
inline void solve() {
precalc();
fore(i, 0, n / 2) {
int c1 = i, c2 = n - 1 - i;
if(s[c1] != s[c2]) {
l[i] = -1;
continue;
}
int lf = 0, rg = min(c1, n - 1 - c2) + 1;
while(rg - lf > 1) {
int mid = (lf + rg) >> 1;
if(eq(c1 - mid, c2 - mid, 2 * mid + 1))
lf = mid;
else
rg = mid;
}
l[i] = lf;
}
fore(i, 0, n / 2) {
if(l[i] < 0)
continue;
mx[i - l[i]] = max(mx[i - l[i]], 2 * l[i] + 1);
}
fore(i, 1, n / 2)
mx[i] = max(mx[i], mx[i - 1] - 2);
fore(i, 0, (n + 1) / 2) {
if(i) printf(" ");
printf("%d", mx[i] == 0 ? -1 : mx[i]);
}
puts("");
}
int main(){
if(read()) {
solve();
}
return 0;
}
```

**Solution (adedalic, hashes)**

```
#include <bits/stdc++.h>
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define all(a) (a).begin(), (a).end()
#define sz(a) int(a.size())
#define mp make_pair
#define x first
#define y second
using namespace std;
typedef long long li;
const li MOD = li(1e18) + 3;
const li BASE = 1009;
inline li norm(li a) {
while(a >= MOD)
a -= MOD;
while(a < 0)
a += MOD;
return a;
}
inline li mul(li a, li b) {
li m = ((long double)(a) * b) / MOD;
return norm(a * b - m * MOD);
}
const int N = 1000 * 1000 + 555;
int n;
string s;
inline bool read() {
if(!(cin >> n))
return false;
char buf[N];
assert(scanf("%s", buf) == 1);
s = buf;
return true;
}
li h[N], pw[N];
inline void precalc() {
h[0] = 0;
fore(i, 0, n)
h[i + 1] = norm(mul(h[i], BASE) + s[i] - 'a' + 1);
pw[0] = 1;
fore(i, 1, N)
pw[i] = mul(pw[i - 1], BASE);
}
inline li getHash(int l, int r) {
return norm(h[r] - mul(h[l], pw[r - l]));
}
inline bool eq(int i1, int i2, int l) {
if(i1 == i2) return true;
return getHash(i1, i1 + l) == getHash(i2, i2 + l);
}
int l[N], mx[N];
inline void solve() {
precalc();
fore(i, 0, n / 2) {
int c1 = i, c2 = n - 1 - i;
if(s[c1] != s[c2]) {
l[i] = -1;
continue;
}
int lf = 0, rg = min(c1, n - 1 - c2) + 1;
while(rg - lf > 1) {
int mid = (lf + rg) >> 1;
if(eq(c1 - mid, c2 - mid, 2 * mid + 1))
lf = mid;
else
rg = mid;
}
l[i] = lf;
}
fore(i, 0, n / 2) {
if(l[i] < 0)
continue;
mx[i - l[i]] = max(mx[i - l[i]], 2 * l[i] + 1);
}
fore(i, 1, n / 2)
mx[i] = max(mx[i], mx[i - 1] - 2);
fore(i, 0, (n + 1) / 2) {
if(i) printf(" ");
if(mx[i] == 0) mx[i] = -1;
printf("%d", mx[i]);
}
puts("");
}
int main(){
if(read()) {
solve();
}
return 0;
}
```

**Editorial**

Tutorial is loading...

**Solution (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) fore(i, 0, n)
const int MOD = int(1e9) + 7;
inline int norm(int a) {
while(a >= MOD)
a -= MOD;
while(a < 0)
a += MOD;
return a;
}
inline int mul(int a, int b) {
return int((a * 1ll * b) % MOD);
}
inline int binPow(int a, int k) {
int ans = 1;
while(k > 0) {
if(k & 1) ans = mul(ans, a);
a = mul(a, a);
k >>= 1;
}
return ans;
}
const int N = 200 * 1000 + 555;
int f[N], inf[N];
void precalc() {
f[0] = inf[0] = 1;
fore(i, 1, N) {
f[i] = mul(f[i - 1], i);
inf[i] = mul(inf[i - 1], binPow(i, MOD - 2));
}
}
int n, k, w[N];
inline bool read() {
if(!(cin >> n >> k))
return false;
forn(i, n)
cin >> w[i];
return true;
}
inline int c(int n, int k) {
if(k > n || n < 0) return 0;
if(k == 0 || n == k) return 1;
return mul(f[n], mul(inf[n - k], inf[k]));
}
inline int s(int n, int k) {
if(n == 0) return k == 0;
if(k == 0) return n == 0;
int ans = 0, sg[2] = {1, MOD - 1};
forn(cnt, k)
ans = norm(ans + mul(sg[cnt & 1], mul(c(k, cnt), binPow(k - cnt, n))));
return mul(ans, inf[k]);
}
inline void solve() {
int sum = 0;
forn(i, n)
sum = norm(sum + w[i]);
int s0 = s(n, k);
int s1 = mul(n - 1, s(n - 1, k));
cout << mul(sum, norm(s0 + s1)) << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif
precalc();
assert(read());
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() << endl;
#endif
return 0;
}
```