akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = 0;
//---------------------------------//

int N, M, L;
int A[112345], B[112345], C[112345];
ll dist[300][300], dp[300][300], ans[300][300];

int main() {
	cin >> N >> M >> L;
	fill(dist[0], dist[N], longINF);
	REP(i, M) {
		scanf("%d %d %d", A + i, B + i, C + i);
		A[i]--; B[i]--;
		chmin(dist[A[i]][B[i]], C[i]);
		chmin(dist[B[i]][A[i]], C[i]);
	}
	
	REP(k, N) REP(i, N) REP(j, N) chmin(dist[i][j], dist[i][k] + dist[k][j]);
	
	fill(dp[0], dp[N], longINF);
	fill(ans[0], ans[N], longINF);
	REP(i, N) {
		queue<int> que;
		que.push(i);
		dp[i][i] = 0;
		
		while (!que.empty()) {
			int u = que.front(); que.pop();
			chmin(ans[i][u], dp[i][u]);
			
			REP(j, N) if (dist[u][j] != longINF) {
				if (dist[u][j] <= L && chmin(dp[i][j], dp[i][u] + 1)) {
					chmin(ans[i][j], dp[i][u]);
					que.push(j);
				}
			}
		}
	}
	
	int Q;
	cin >> Q;
	while (Q--) {
		int s, t;
		scanf("%d %d", &s, &t);
		s--; t--;
		if (ans[s][t] == longINF) puts("-1");
		else printf("%lld\n", ans[s][t]);
	}
	
	return 0;
}


Measured memory_bytes: 3072
def main():
    N, M = (int(i) for i in input().split())
    S = input()
    T = input()

    def gcd(x, y):
        if y == 0:
            return x
        while y != 0:
            x, y = y, x % y
        return x

    def lcm(x, y):
        return x*y//gcd(x, y)
    L = lcm(N, M)

    match = lcm(L//N, L//M)
    for a in range(0, L, match):
        if S[a * N//L] != T[a * M//L]:
            return print(-1)
    else:
        print(L)


if __name__ == '__main__':
    main()


Measured memory_bytes: 40048
while True:
    N = int(input())
    if N == 0:
        break

    # ??????????????????????¨???????????????°?????????
    (a, b) = (0, 0)
    
    inputs = []

    # ???????????°???????????????
    for x in range(N):
        # ??????????????????????????????
        inputs.append(list(map(int, input().split())))

    for points in inputs:
        # ?????°?????????????????????????????°???????¨?????????????
        if points[0] == points[1]:
            a = a + points[0]
            b = b + points[1]
        elif points[0] > points[1]:
            a = a + points[0] + points[1]
        else:
            b = b + points[0] + points[1]

    # ????????????????????¨???
    print(a,b)

Measured memory_bytes: 9268
using System;
using static System.Console;
using static System.Math;
using System.Collections.Generic;
using System.Linq;

class Program
{
    public static void Main()
    {
        int N = int.Parse(ReadLine());
        int res = N;
        for(int i = 0; i <= N; i++)
        {
            int cc = 0;
            int t = i;
            while (t > 0)
            {
                cc += t % 6;
                t /= 6;
            }
            t = N - i;
            while (t > 0)
            {
                cc += t % 9;
                t /= 9;
            }
            if (res > cc) res = cc;
        }
        WriteLine(res);
    }
}

Measured memory_bytes: 11092
<?php
$str = trim(fgets(STDIN));
$array = str_split($str);
$result = 0;
for ($i = 0; $i < 3; $i++) {
	if ($array[$i] == "R") {
    	$result += 1;
    } else if ($array[$i] == "S" && $array[$i - 1] == "R") {
    	break;
    }
}

echo $result;
?>

Measured memory_bytes: 16112
// AOJ 0604: Take the 'IOI' train
// 2017.12.5 bal4u@uu

#include <stdio.h>
#include <string.h>

char s[2002], t[2002];
int dp[2][2002][2002];

int main()
{
	int n, m, i, j, ans;
	char *p;

	fgets(s, 20, stdin);
	sscanf(s, "%d%d", &m, &n);
	fgets(s, 2002, stdin);
	fgets(t, 2002, stdin);

	for (p = s; *p > ' '; p++) *p = (*p == 'O');
	for (p = t; *p > ' '; p++) *p = (*p == 'O');

	ans = 0;
	memset(dp[0], -1, sizeof(dp[0]));

	for (i = 0; i < m; i++) {
		for (j = 0; j < n; j++) {
			if (dp[s[i]][i+1][j] < dp[1-s[i]][i][j] + 1)
				dp[s[i]][i+1][j] = dp[1-s[i]][i][j] + 1;

			if (dp[t[j]][i][j+1] < dp[1-t[j]][i][j] + 1)
				dp[t[j]][i][j+1] = dp[1-t[j]][i][j] + 1;

			if (ans < dp[0][i][j]) ans = dp[0][i][j];
		}
		if (dp[s[i]][i+1][n] < dp[1-s[i]][i][n] + 1)
			dp[s[i]][i+1][n] = dp[1-s[i]][i][n] + 1;
		if (ans < dp[0][i][n]) ans = dp[0][i][n];
	}
	for (j = 0; j < n; j++) {
		if (dp[t[j]][m][j+1] < dp[1-t[j]][m][j] + 1)
			dp[t[j]][m][j+1] = dp[1-t[j]][m][j] + 1;
		if (ans < dp[0][m][j]) ans = dp[0][m][j];
	}
	if (ans < dp[0][m][n]) ans = dp[0][m][n];

	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 33168
#include <iostream>
using namespace std;
int main(){
    long long int N,K;
    cin >> N >> K;
    long long int y=N;
    y=y%K;
    long long int x=-y+K;
    if(x<y){
        cout << x;
    }else{
        cout << y;
    }
    return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        //System.setIn(Main.class.getClassLoader().getResourceAsStream("input"));
        Scanner sc = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        String day = sc.next();
        int t = 0;
        switch (day) {
            case "SUN": t = 7; break;
            case "MON": t = 6; break;
            case "TUE": t = 5; break;
            case "WED": t = 4; break;
            case "THU": t = 3; break;
            case "FRI": t = 2; break;
            case "SAT": t = 1; break;
        }
        System.out.println(t);
    }
}


Measured memory_bytes: 21076
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
    int A,B;
    cin>>A>>B;
    if(A>=13)cout<<B<<endl;
    if(A>=6&&A<=12)cout<<B/2<<endl;
    if(A<6)cout<<0<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int x, y, a, b, c;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> x >> y >> a >> b >> c;
    int p[a], q[b], r[c];

    ll sum = 0;
    for (int i = 0; i < a; ++i) {
        cin >> p[i];
    }
    for (int i = 0; i < b; ++i) {
        cin >> q[i];
    }
    for (int i = 0; i < c; ++i) {
        cin >> r[i];
    }
    sort(p, p + a, greater<int>());
    sort(q, q + b, greater<int>());
    sort(r, r + c, greater<int>());
    int pi = x - 1;
    int qi = y - 1;
    int ri = 0;
    for (int i = 0; i < x; ++i) {
        sum += p[i];
    }
    for (int i = 0; i < y; ++i) {
        sum += q[i];
    }
    while (ri < c && (pi >= 0 || qi >= 0)) {
        if (pi < 0) {
            if (r[ri] <= q[qi]) break;
            else sum += (r[ri++] - q[qi--]);
            continue;
        }
        if (qi < 0) {
            if (r[ri] <= p[pi]) break;
            else sum += (r[ri++] - p[pi--]);
            continue;
        }
        if (r[ri] <= p[pi] && r[ri] <= q[qi]) break;
        if (p[pi] < q[qi]) {
            sum += (r[ri++] - p[pi--]);
        } else {
            sum += (r[ri++] - q[qi--]);
        }
    }

    cout << sum << endl;

    return 0;
}



Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define all(x) (x).begin(), (x).end()
ll inf = LLONG_MAX;
long double pi = M_PI;
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

//UnionFind
//全て添字で扱うこと
struct union_find {
  vll parent;
  vll sizes;

  void init(ll n) {
    for (ll i = 0; i < n; i++) parent.push_back(i);
    for (ll i = 0; i < n; i++) sizes.push_back(1);
    return;
  }

  ll root(ll n) {
    if (parent[n] == n) return n;
    return parent[n] = root(parent[n]);
  }

  ll size(ll n) {
    return sizes[root(n)];
  }

  bool is_united(ll a, ll b) {
    return (root(a) == root(b));
  }

  void unite(ll a, ll b) {
    if (is_united(a, b)) return;
    sizes[root(a)] += size(b);
    parent[root(b)] = root(a);
    return;
  }
};

int main() {
  ll n, m;
  cin >> n >> m;

  vll a(m), b(m);
  for (ll i = 0; i < m; i++) cin >> a[i] >> b[i];

  struct union_find uf;
  uf.init(n);

  ll unconv = n * (n - 1) / 2;
  vll ans(1, unconv);

  for (ll i = m - 1; i > 0; i--) {
    if (!uf.is_united(a[i] - 1, b[i] - 1)) {
      unconv -= uf.size(a[i] - 1) * uf.size(b[i] - 1);
    }
    uf.unite(a[i] - 1, b[i] - 1);
    ans.push_back(unconv);
  }

  for (ll i = 0; i < m; i++) cout << ans[m - 1 - i] << endl;
}

Measured memory_bytes: 5364
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
ans=1
upper_limit = int(1e18)
if A[-1]==0:
  print(0)
  exit()
else:
  for i in range(N):
    ans*=A[i]
    if ans > upper_limit:
      print(-1)
      exit()
print(ans)

Measured memory_bytes: 84216
<?php
fscanf(STDIN, "%d %d", $a, $b);

$i = $a + $b;
$j = $a - $b;
$k = $a * $b;

$tmp = $i;
if($i < $j){
  if($j < $k){
	$tmp = $k;
  }else{
	$tmp = $j;  
  }
}elseif($i < $k){
  $tmp = $k;
}

echo $tmp;

?>

Measured memory_bytes: 3700
fun main(args :Array<String>) {
    val sum = readIntegerList().sum()
    val ans = if (sum >= 22) "bust" else "win"
    println(ans)
}

fun readInteger() = readLine()!!.toInt()
fun readStringList() = readLine()!!.split(" ")
fun readIntegerList() = readStringList().map(String::toInt)
fun readLongList() = readStringList().map(String::toLong)


Measured memory_bytes: 36004
#include <bits/stdc++.h>
using namespace std;

int main()
{
  int N;
  cin >> N;

  vector<int> ans(10000, 0);

  for (int x = 1; x <= 100; x++)
  {
    for (int y = 1; y <= 100; y++)
    {
      for (int z = 1; z <= 100; z++)
      {
        int tmp = x * x + y * y + z * z + x * y + y * z + z * x;
        if (tmp <= 10000)
        {
          ans[tmp]++;
        }
      }
    }
  }
  for (int i = 0; i < N; i++)
  {
    cout << ans[i + 1] << endl;
  }
}

Measured memory_bytes: 3612
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

int N;
VI B;

void MAIN() {
    scanf("%d", &N);
    B.resize(N);
    REP (i, N) scanf("%d", &B[i]);
    VI ans;

    REP (t, N) {
	bool ok = false;
	for (int i=B.size(); i--;) {
	    if (i+1 == B[i]) {
		ans.push_back(i+1);
		B.erase(B.begin()+i);
		ok = true;
		break;
	    }
	}
	if (!ok) {
	    puts("-1");
	    return;
	}
    }
    reverse(ans.begin(), ans.end());
    REP (i, N) printf("%d\n", ans[i]);

}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 768
#include <bits/stdc++.h>

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<ll,ll> pii;
const int MD = (int)1e9 + 7;
void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }



int main(){
	//cin.tie(0); ios_base::sync_with_stdio(false);
	int n; ll p;
	cin >>n >>p;
	vector<ll> t(n);
	for(auto& it: t) cin >>it;

	ll ans =0, st = t[0], et = t[0] + p;
	rep2(i, 1, n){
		if(t[i] - t[i-1] > p){
			ans += et - st;
			st = t[i]; et = t[i]+p;
		}else{
			et = t[i]+p;
		}
	}
	ans += et - st;
	cout << ans <<endl;
	return 0;
}

Measured memory_bytes: 1792
"""
dp[i] i番目に到達するときの最小値
遷移
送るDP
i-1段目まで下記を実施
dp[i+1] = min(dp[i+1], dp[i]+コスト)
if (一段飛ばしできる余地があれば): 
    dp[i+2] = min(dp[i+2],dp[i]+コスト)

"""
N, K = map(int, input().split())
hs = list(map(int, input().split()))

INF = 10**12
dp = [INF]*101000
dp[0] = 0

for i in range(1,N):
    for j in range(1,K+1):
        if i-j >= 0:
            cost = abs(hs[i]-hs[i-j])
            dp[i] = min(dp[i],dp[i-j]+cost)

print(dp[N-1])

Measured memory_bytes: 52448
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (a); i < static_cast<int>(b); i++)
#define FORR(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) FOR (i, 0, n)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'
template <typename T>
void print(const vector<vector<T>> matrix);
template <typename T>
void print(const vector<T> vec);
template <typename Arg>
void print(const Arg arg);
template <typename Head, typename... Args>
void print(const Head head, const Args... args);
template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = INT_MAX / 2;
using ll = long long;

int main() {
    int n, m;
    cin >> n >> m;
    int max = m / n;

    for (int i = max; i >= 1; i--) {
        if (m % i == 0) {
            print(i);
            break;
        }
    }

    return 0;
}

//---------------------------------------------
template <typename T>
void print(const vector<vector<T>> matrix) {
    repall (vec, matrix)
        print(vec);
}
template <typename T>
void print(const vector<T> vec) {
    unsigned int len = vec.size();
    rep (i, len - 1)
        cout << vec[i] << ' ';
    cout << vec[len - 1] << '\n';
}
template <typename Arg>
void print(const Arg arg) {
    cout << arg << '\n';
}
template <typename Head, typename... Args>
void print(const Head head, const Args... args) {
    cout << head << " ";
    print(args...);
}


Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <stdint.h>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
  int N;
  cin >> N;

  vector<int> P, Q;

  for (int n=0; n<N; ++n) {
    int ii;
    cin >> ii;
    P.push_back(ii);
  }

  for (int n=0; n<N; ++n) {
    int ii;
    cin >> ii;
    Q.push_back(ii);
  }
  
  vector<int> X;
  for (int n=0; n<N; ++n)
    X.push_back(n+1);

  int i=0, p, q;
  
  do {
    ++i;
    if (X==P)
      p = i;
    if (X==Q)
      q = i;
  } while (std::next_permutation(X.begin(), X.end()));

  cout << abs(p-q) << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;

int main(){
    int n;
    cin>>n;
    int c=0;
    for(int i = 0; i < n; i++) {
        int a;
        cin>>a;
        if(a%2==1) c++;
    }
    if(c%2==0) {
        cout<<"YES"<<endl;
    }
    else {
        cout<<"NO"<<endl;
    }        
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int n, a, b;
	long long int ans;

	char buf[128];

	fgets(buf, sizeof(buf), stdin);
	sscanf(buf, "%d %d %d", &n, &a, &b);

	if (a == b) {
		ans = 1;
	} else if (n == 1 || a > b){
		ans = 0;
	} else {
		ans = (b - a);
		ans = ans * (n - 2) + 1;
	}

	printf("%lld\n", ans);

	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define endl '\n'
int32_t main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n;
  cin >> n;
  string s;
  cin >> s;
  int r = 0;
  int w = 0;
  for (int i = 0; i < n; i++)
  {
    if (s[i] == 'R')
      r++;
    else
      w++;
  }
  int ans = min(r, w);
  int cnt = 0;
  for (int i = 0; i < r; ++i)
  {
    if (s[i] != 'R')
    {
      cnt++;
    }
  }
  ans = min(ans, cnt);
  cout << ans << endl;
}


Measured memory_bytes: 3756
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repp(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define repm(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define INF (1ll<<60)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
const lint MOD =1000000007;
const lint MAX = 10000000;
using Graph =vector<vector<lint>>;

 
lint fac[MAX], finv[MAX], inv[MAX];

void COMinit() // 二項係数を求める時は前処理としてCOMinit()をする
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (lint i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
// 二項係数計算
long long COM(lint n, lint k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

lint primary(lint num)
{
    if (num < 2) return 0;
    else if (num == 2) return 1;
    else if (num % 2 == 0) return 0; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return 0;
        }
    }

    // 素数である
    return 1;
}
lint lcm(lint a,lint b){
      return a/__gcd(a,b)*b;
  }
  int main(){
     lint N;
     lint ans=0;
     cin>>N;
     pair<lint,lint> v[N];
     rep(i,N){
         lint x,l;
         cin>>x>>l;
         lint g=x+l;
         lint a=x-l;
        v[i]=make_pair(g,a);
     }
     sort(v,v+N);
    lint t=-INF;
     rep(i,N){
         lint x,l;
         tie(x,l)=v[i];
         if(t<=l){
             ans++;
             t=x;
         }
     }
     cout<<ans;
  }
  

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define XX first
#define YY second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define REP rep
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define all(X) (X).begin(),(X).end()
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
const ll MOD=1e9+7;

#define rall(X) (X).rbegin(),(X).rend()
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}

string S;
LL L, R;
using V = array<LL, 26>;

// re[i] := S[0..i-1]の接頭辞・接尾辞が最大何文字一致しているか
void mp(const string &S, vector<int> &re){
  re.resize(S.size()+1); re[0]=-1;
  int j=-1;
  rep(i, S.size()){
    while(j>=0 && S[i]!=S[j]) j=re[j];
    re[i+1]=++j;
  }
}

V Count(string &s) {
  V ret = {};
  for (char c : s) {
    ret[c-'a']++;
  }
  return ret;
}

LL Sum(V &a) {
  LL ret = 0;
  rep(i, 26) {
    ret += a[i];
  }
  return ret;
}

V Solve(LL r) {
  V ret = {};
  if (!r) return ret;

  if (S.size()*2 >= r) {
    string SS = S+S;
    rep(i, r) {
      ret[SS[i]-'a']++;
    }
    return ret;
  }

  vector<int> re;
  mp(S, re);
  int n = S.size();
  int w = n - re[n];
  string P = S.substr(0, w);
  auto a = Count(P);
  if (n%w == 0) {
    rep(i, 26) {
      ret[i] += a[i] * (r/w);
    }
    rep(i, r%w) {
      ret[P[i]-'a']++;
    }
    return ret;
  }
  
  vector<V> series;
  series.eb(a);
  series.eb(Count(S));
  int idx = 1;
  while (1) {
    if (Sum(series[idx])*2 >= r) {
      assert (Sum(series[idx]) < r);
      {
        ret = series[idx];
        r -= Sum(series[idx]);
      }
      break;
    }

    series.eb();
    rep(i, 26) {
      series.back()[i] = series[idx-1][i] + series[idx][i];
    }
    ++idx;
  }

  while (idx > 1) {
    //cout << "r: " << r << endl;
    //cout << idx << ": ";
    //rep(i, 26) {
    //  if (i) cout << " ";
    //  cout << ret[i];
    //}cout << endl;
    assert(Sum(series[idx]) >= r);
    --idx;
    if (Sum(series[idx]) <= r) {
      rep(i, 26) ret[i] += series[idx][i];
      r -= Sum(series[idx]);
      --idx;
    }
  }
  if (idx == 1) {
    assert(r <= S.size());
    rep(i, r) {
      ret[S[i]-'a']++;
    }
  } else {
    assert(idx == 0 && Sum(series[idx]) >= r);
    assert(r <= w);
    rep(i, r) {
      ret[P[i]-'a']++;
    }
  }
  return ret;
}

signed main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);

  cin >> S;
  assert(S.size()%2 == 0);
  S = S.substr(S.size()/2);
  cin >> L >> R;
  auto ans = Solve(R);
  auto sub = Solve(L-1);
  rep(i, 26) {
    if (i) cout << " ";
    assert(ans[i] >= sub[i]);
    cout << ans[i] - sub[i];
  }
  cout << endl;
}


Measured memory_bytes: 848
s=str(input())
t=str(input())

sl=[]
tl=[]

for i in range(len(s)):
  sl.append(s[i])
for i in range(len(t)):
  tl.append(t[i])
  
m=100000
for i in range(len(s)-len(t)+1):
  cnt=0
  for j in range(len(t)):
    if t[j]!=s[i+j]:
      cnt+=1
  m=min(m,cnt)
print(m)

Measured memory_bytes: 8988
package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)
	for i := 1; i < len(s); i++ {
		t := s[:len(s)-i]
		if len(t)%2 == 0 && t[0:len(t)/2] == t[len(t)/2:] {
			fmt.Println(len(t))
			break
		}
	}
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;

string winner(vector<int>& v,int n,int k){
    bool dp[k+1];
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=k;i++){
        for(int cut: v){
            if(cut>i){
                continue;
            }
            if(dp[i-cut]==0){
                dp[i] = 1;
            }
        }
    }
    return dp[k] ? "First" : "Second";
}

int main(){
    int n,k;
    cin>>n>>k;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    cout<<winner(v,n,k);
    return 0;
}

Measured memory_bytes: 384
import sys
input=sys.stdin.readline

def main():
    N,M=map(int, input().split())

    K=[]
    for i in range(M):
        sw = list(map(int, input().split()))
        x = 0
        for j in sw[1:]:
            x += 2**(j-1)
        K.append(x)

    P = list(map(int, input().split()))

    ans = 0
    for i in range(2**N):
        b = True
        for j in range(M):
            if "{:b}".format(i&K[j]).count("1") %2 != P[j]:
                b = False
                break
        if b:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e17)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
//#define i_7 998'244'353
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;

bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

long long gcd_(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}


int main(){
  
  bool dp[100010] = {};
  int x;
  cin>>x;
  REP(i,6){
    dp[100+i] = true;
  }
  for(int i = 106; i<=100000; i++){
    bool temp = false;
    REP(j,6){
      temp = temp || dp[i-(100+j)];
    }
    dp[i] = temp;
  }
  if(dp[x]){
    cout<<1<<endl;
  }else{
    cout<<0<<endl;
  }
    
  return 0; 
}


Measured memory_bytes: 384
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<sstream> 
#include<unordered_map>      

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;

const int inf = numeric_limits<int>::max() >> 2;
const ll linf = numeric_limits<ll>::max() >> 2;
const ull ulinf = numeric_limits<ull>::max() >> 2;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define umap(i,j) unordered_map<i,j>
#define P(p) cout<<(p)<<endl
#define PS(p) cout<<(p)<< " "
#define PN cout << endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i = (n-1); i >= (int)(m); i--)
#define inrep(n,a) for(int i = 0; i < (int)(n); i++)cin >> a[i];
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end())
#define rvsort(v,c) sort(v.begin(), v.end(), greater<c>()) 
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - (a)) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define ub(a,n,k) (upper_bound(a,a+n,k) - (a)) 
#define vub(a,k)  (upper_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

/*
ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
*/

/*
vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}
*/

/*
ll ncr[100][100];
ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

ll npr[100][100]={};
ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

ll nHr(int n,int r){ret nCr(n+r-1,r);}
*/

///////////////////////////////////////////////////////////////////////////



int main(){
    
    string s;
    cin >> s;
    rep(i,0,sz(s))cout << 'x';
    PN;
    return  0;
}


Measured memory_bytes: 256
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) x.size()
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N=4e3+10;

struct node {
	int to,val,next;
} e[N];

int n,x,y;
int head[N],dis[N],vis[N],cnt,ans[N];

void add(int u,int v,int w) {
	e[++cnt].to=v;
	e[cnt].val=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}


void spfa(int s) {
	for(int i=1; i<=n; i++) {
		dis[i]=INF;
		vis[i]=0;
	}
	dis[s]=0;
	vis[s]=1;
	queue<int> q;
	q.push(s);
	while(!q.empty()) {
		int u=q.front();
		vis[u]=0;
		q.pop();
		for(int i=head[u]; i; i=e[i].next) {
			int v=e[i].to;
			if(dis[v]>(dis[u]+e[i].val)) {
				dis[v]=dis[u]+e[i].val;
				if(!vis[v]) {
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	for(int i=1;i<=n;i++) ans[dis[i]]++;

}

int main() {
	IOS;
#ifdef xiaofan
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
#endif

	
	cin>>n>>x>>y;
	for(int i=1;i<n;i++){
		add(i,i+1,1);
		add(i+1,i,1);
	}
	add(x,y,1);
	add(y,x,1);
	for(int i=1;i<=n;i++) spfa(i);
	for(int i=1;i<=n-1;i++) cout<<ans[i]/2<<endl;




	return 0;
}



Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;

int main(){
  
  while(true){
    string s,t1,t2;
    int m, h,count=0;
    cin>>s;
    
    count = (int)s.length();
     if(s == "-") break;
     
     cin>>m;
    for(int i=0; i<m; i++){
      cin>>h;
      t1 = s.substr(0,h);
      t2 = s.substr(h,count-1);
      s = t2 + t1;
      //cout<<t2<<t1<<endl;
    }
    cout<<t2<<t1<<endl;
  }
 
}



Measured memory_bytes: 3176
#include <iostream>
#include <string>
using namespace std;

int main()
{
    long long n;
    while(1){
        cin >> n;
        if(n==0) break;
        long long ans = 0;  
        long long a = 5;
        while(a <= n){
            ans += n / a;
            a *= 5;
        }
        cout << ans << endl;
    }
	return 0;
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(), (x).end())
#define ALL(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define reps(i, m, n) for (ll i = m; i < n; i++)
#define repr(i, m, n) for (ll i = m; i >= n; i--)
#define de(x) cout << #x << "=" << x << endl;
template <class T>
bool maxi(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool mini(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
#define INF2 1000000000000000037
#define INF 1000000007
#define MOD 1000000007
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
//--GLOBAL---------------------------------



//--MAIN-----------------------------------
void Main() {
    ll N; cin>>N;
    vector<ll> X(N);
    vector<ll> Y(N);
    vector<ll> U(N);
    vector<ll> V(N);
    rep(i,N){ cin>>X[i]; cin>>Y[i]; U[i]=X[i]+Y[i]; V[i]=X[i]-Y[i];}

    bool kisu;

    rep(i,N){
        if(i==0){
            kisu = (abs(U[i]%2)==1);
        }

        else{
            if( kisu!= (abs(U[i]%2)==1) ){
                cout<<  -1 <<"\n"; return;
            }
        }
        if(!kisu){
            X[i]+=1;
            U[i]+=1;
            V[i]+=1;
        }
    }

    ll m=38;
    //ll m=7;
    ll d[m+1];
    string ans[N]={};

    rep(i,m){
        d[i]=pow(2,(m-1-i));
    }

    ll nowU[N]={};
    ll nowV[N]={};

    rep(j,m){
        rep(i,N){
            bool Uplus,Vplus;
            if(abs(U[i]-(nowU[i]+d[j]))<=abs(U[i]-(nowU[i]-d[j]))){
                Uplus=true; nowU[i]+=d[j];
            }
            else{
                Uplus=false; nowU[i]-=d[j];
            }
            if(abs(V[i]-(nowV[i]+d[j]))<=abs(V[i]-(nowV[i]-d[j]))){
                Vplus=true; nowV[i]+=d[j];
            }
            else{
                Vplus=false; nowV[i]-=d[j];
            }
            if(Uplus and Vplus) ans[i]+="R";
            if(Uplus and !Vplus) ans[i]+="U";
            if(!Uplus and Vplus) ans[i]+="D";
            if(!Uplus and !Vplus) ans[i]+="L";
            /*
            de(i);
            de(j);
            de(nowU[i]);
            de(nowV[i]);
            */
        }
    }

    if(!kisu){
        ++m;
        d[m-1]=1;
        rep(i,N){
            ans[i]+="L";
        }
    }

    cout<< m<<"\n";
    rep(i,m){
        cout<< d[i] <<" ";
    }
    cout<<"\n";
    rep(i,N){
        cout<< ans[i]<<"\n";
    }

}   
//--START----------------------------------
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
}
//-----------------------------------------


Measured memory_bytes: 512
def main():
  N = int(input())
  A = list(map(int, input().split()))
  A = sorted(A, reverse = True)
  flag = True
  num = 0
  ans = 1
  for i in range(N-1):
    if A[i] == A[i+1] and flag:
      ans *= A[i]
      num += 1
      if num == 2:
        break
      flag = False
    elif not flag:
      flag = True
  if num < 2:
    ans = 0
  print(ans)
main()

Measured memory_bytes: 14252
#include <bits/stdc++.h>
#include <complex>
#include <queue>
#include <set>
#include <list>
#include <chrono>
#include <random>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <stack>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<vector<ll> > vv64;
typedef vector<vector<p64> > vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
ll MOD = 1e9+7;
#define forn(i,e) for(ll i = 0; i < e; i++)
#define forsn(i,s,e) for(ll i = s; i < e; i++)
#define rforn(i,s) for(ll i = s; i >= 0; i--)
#define rforsn(i,s,e) for(ll i = s; i >= e; i--)
#define ln "\n"
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define INF LLONG_MAX/2e5

ll mpow(ll a, ll b){
	if(b==0) return 1;
	ll t1 = mpow(a,b/2);
	t1 *= t1;
	t1 %= MOD;
	if(b%2) t1 *= a;
	t1 %= MOD;
	return t1;
}

void solve(ll in){
	ll n;
	cin >> n;
	p64 a[n];
	forn(i,n){
		cin >> a[i].fi >> a[i].se;
	}
	map<p64,ll> m;
	forn(i,n){
		forn(j,n){
			if(i!=j){
				m[mp(a[i].fi-a[j].fi,a[i].se-a[j].se)]++;
			}
		}
	}
	ll ans = 0;
	for(auto i : m){
		ans = max(ans,i.se);
	}
	cout << n-ans << ln;
}


int main()
{
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
    // cin >> t;
    forn(i,t) {
    	solve(i+1);
    }
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>

#define mp make_pair
#define fst first
#define snd second
#define forn(i,n) for (int i = 0; i < int(n); i++)
#define forn1(i,n) for (int i = 1; i <= int(n); i++)
#define popcnt __builtin_popcount

using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

template <typename T> T id(T b) {return b;};
template <class It> bool all(It f,It l){return std::all_of(f,l,id<bool>);}
template <class It> bool any(It f,It l){return std::any_of(f,l,id<bool>);}
template <typename T> void chmax(T &x, T y) {if (x < y) x = y;}
template <typename T> void chmin(T &x, T y) {if (x > y) x = y;}

int n,m;

int main()
{
#ifdef FASTIO
  ios_base::sync_with_stdio(false); cin.tie(nullptr);
#endif

  cin >> n >> m;
  int a = 1, b = n;

  forn(i,n) {
    int l,r;
    cin >> l >> r;
    chmax(a,l);
    chmin(b,r);
  }

  cout << max(0,b - a + 1) << endl;

  return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main()
{
    const int Max = 100010;
    long long int fib[Max] = {};
    fib[0] = 0,fib[1] = 1;
    for(int i = 2;i < Max;i++)
    {
        fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
    }
    int n,m;
    cin >> n >> m;
    if(m == 0)
    {
        cout << fib[n + 1] << "\n";
        return 0;
    }
    int a[m];
    for(int i = 0;i < m;i++)
    {
        cin >> a[i];
    }
    vector<long long int> v;
    int temp = 0;
    v.push_back(fib[a[0]]);
    for(int i = 1;i < m;i++)
    {
        v.push_back(fib[a[i] - a[i - 1] - 1]);
    }
    v.push_back(fib[n - a[m - 1]]);
    long long int ans = 1;
    for(int i = 0;i < v.size();i++)
    {
        ans *= v[i];
        ans = ans % MOD;
    }
    cout << ans % MOD << "\n";

    return 0;
}

Measured memory_bytes: 2552
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>
#include <cmath>
#include <cassert>
#include <bitset>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define EL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
/* libraries */

struct UnionFind
{
  int n;
  std::vector<int> par,size;
  UnionFind(int sz) : n(sz), par(sz,0), size(sz,1) {
    std::iota(par.begin(),par.end(),0);
  }
  int find(int x) {
    if(par[x]==x) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x=find(x);y=find(y);
    if(x==y) return;
    if(size[x]<size[y]) std::swap(x,y);
    size[x]+=size[y];
    par[y]=x;
  }
};


struct E
{
	int a,b;
	E(int x, int y) : a(x),b(y) {
		if(a>b) std::swap(a,b);
	}
	bool operator<(const E e) const {
		if(a!=e.a) return a<e.a;
		return b<e.b;
	}
};

signed main() {
	int n,m;
	std::cin >> n >> m;
	std::set<E> edgesI;
	rep(i,m) {
		int a,b;
		std::cin >> a >> b;
		a--;b--;
		edgesI.emplace(a,b);
	}
	// get complement
	std::set<E> edges;
	for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) edges.emplace(i,j);
	for(auto x:edgesI) edges.erase(x);
	std::vector<std::vector<int> > g(n);
	UnionFind uf(n);
	for(auto e:edges) {
		uf.unite(e.a,e.b);
		g[e.a].emplace_back(e.b);
		g[e.b].emplace_back(e.a);
	}

	std::vector<int> col(n,-1);
	auto dfs = [&] (auto f, int i, int c) -> int {
		col[i]=c;
		for(auto to:g[i]) {
			if(col[to]==c) return 1;
			if(col[to]!=-1) continue;
			if(f(f,to,c^1)) return 1;
		}
		return 0;
	};

	for(int i=0;i<n;i++) {
		if(col[i]==-1) if(dfs(dfs,i,0)) {
			print(-1);
			return 0;
		}
	}
	std::map<int,int> map;
	rep(i,n) {
		if(col[i]) map[uf.find(i)]++;
		else map[uf.find(i)]--;
	}
	std::vector<int> v;
	for(auto x:map) {
		v.emplace_back(std::abs(x.second));
	}
	std::vector<std::vector<int> > dp(v.size()+1,std::vector<int>(2*n+1,0));
	int z=n;
	dp[0][z]=1;
	rep(i,v.size()) {
		for(int j=0;j<2*n+1;j++) {
			if(dp[i][j]) {
				dp[i+1][j+v[i]]=1;
				dp[i+1][j-v[i]]=1;
			}
		}
	}
	int min=1e9;
	rep(i,2*n+1) {
		if(dp[v.size()][i]) min=std::min(min,std::abs(i-z));
	}
	assert((n-min)%2==0);
	int a=(n-min)>>1;
	int b=n-a;
	print(a*(a-1)/2+b*(b-1)/2);
	return 0;
}


Measured memory_bytes: 30848
N, K = list(map(int, input().split()))
S = input()

def gen_0_idx(S):
  N = len(S)
  idx_list = []
  start_0 = False
  for i in range(N):
    if S[i] == "0" and not start_0:
      start_idx = i
      start_0 = True
    elif S[i] == "1" and start_0:
      end_idx = i - 1
      idx_list.append((start_idx, end_idx))
      start_0 = False
    if i == N - 1 and start_0:
      end_idx = i
      idx_list.append((start_idx, end_idx))
  return idx_list

idx_list = gen_0_idx(S)
if len(idx_list) <= K:
  print(N)
else:
  N_I = len(idx_list)
  one_len_list = []
  for i in range(N_I - K + 1):
    if i == 0:
      length = idx_list[K][0]
    elif i == N_I - K:
      length = N - idx_list[N_I - K - 1][1] - 1
    else:
      length = idx_list[i + K][0] - idx_list[i - 1][1] - 1
    one_len_list.append(length)
  print(max(one_len_list))

Measured memory_bytes: 11516
#include <iostream>
#include <algorithm>
#include <functional>
#include <cmath>
#include <string>
#include <vector>
#include <queue>

using namespace std;

const int SIZE = 3;

int main() {
  int a[SIZE][SIZE];
  for (int i = 0; i < SIZE; ++i) {
    for (int j = 0; j < SIZE; ++j) {
      cin >> a[i][j];
    }
  }

  int n;
  cin >> n;
  int c[SIZE][SIZE] = {0};
  for (int i = 0; i < n; ++i) {
    int b;
    cin >> b;
    for (int i = 0; i < SIZE; ++i) {
      for (int j = 0; j < SIZE; ++j) {
        if (a[i][j] == b) {
          c[i][j] = 1;
        }
      }
    }
  }

  for (int i = 0; i < SIZE; ++i) {
    for (int j = 0; j < SIZE; ++j) {
      if (!c[i][j]) break;
      else if (j != SIZE-1) continue;

      cout << "Yes" << endl;
      return 0;
    }
  }

  for (int i = 0; i < SIZE; ++i) {
    for (int j = 0; j < SIZE; ++j) {
      if (!c[j][i]) break;
      else if (j != SIZE-1) continue;

      cout << "Yes" << endl;
      return 0;
    }
  }

  for (int i = 0; i < SIZE; ++i) {
    if (!c[i][i]) break;
    else if (i != SIZE-1) continue;

    cout << "Yes" << endl;
    return 0;
  }

  for (int i = SIZE - 1; i >= 0; --i) {
    if (!c[SIZE-1-i][i]) break;
    else if (i != 0) continue;

    cout << "Yes" << endl;
    return 0;
  }


  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()

ans = 0
A = [0] * (K+1)
for x in range(K, 1, -1):
    a = K // x
    A[x] = pow(a, N, MOD)
    i = x
    while i + x <= K:
        i += x
        A[x] -= A[i]
    A[x] %= MOD
    ans += A[x] * x
    ans %= MOD
ans += pow(K, N, MOD) - sum(A)
ans %= MOD
print(ans)


Measured memory_bytes: 68996
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional> // for less 
#include <iostream> 
using namespace __gnu_pbds; 
using namespace std; 
#include<bits/stdc++.h>
#define int long long
#define pb push_back 
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define repa(i,a,b) for (int i=a; i<=b; i++)
#define repd(i,b,a) for (int i=b; i>=a; i--)
#define endl "\n"
typedef tree<int, null_type, less<int>, 
rb_tree_tag, tree_order_statistics_node_update> pbset; 
//debugging
#define debug1(a) cout<<#a<<" = "<<(a)<<endl;
#define debug2(a,b) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<endl;
#define debug3(a,b,c) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<endl;
#define debug4(a,b,c,d) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<", "<<#d<<" = "<<(d)<<endl;

const int N = 1e+6+5;
int big = 1e+18+3;
int mod = 1e+9+7;

signed main()
{
    IOS;
    
    int n,d;
    cin>>n>>d;

    int cnt = 0;

    repa(i,1,n)
    {
        int x,y;
        cin>>x>>y;
        x*=x;
        y*=y;
        x+=y;
        if (x<=d*d)
            cnt++;
    }

    cout<<cnt<<endl;
                 
}

Measured memory_bytes: 3652
NK = input().split()
N,K = int(NK[0]), int(NK[1])
A = list(map(int, input().split()))
#コストの配列 全部無限にしておく
cost = [float("inf") for _ in range(N)]
cost[0] = 0

for i in range(N-1):
    if(i + K >= N):
        K = N-1-i
    for j in range(1, K+1):
        cost[i + j] = min(cost[i + j], cost[i] + abs(A[i+j] - A[i]))
print(cost[N-1])

Measured memory_bytes: 57056
#include<bits/stdc++.h>
using namespace std;

/***typededfs***/
typedef long long ll;
typedef long double ldb;

/***defines***/
#define M1 1000000007
#define M2 998244353
#define F first
#define S second
#define pb push_back
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define forz(i,n) for(int i=0;i<(n);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define rforz(i,n) for(int i=(n-1);i>=0;i--)
#define rfore(i,a,b) for(int i=(a);i>=(b);i--)
#define test int T; cin>>T; while(T--)


int main(){ 
      FASTIO;
      int n,k;
      cin>>n>>k;
      int h[n];
      forz(i,n)cin>>h[i];
      int dp[n]{};
      dp[0] =0;
      //cout<<"dp[1]="<<dp[1]<<' ';
      fore(i,1,n-1){
            dp[i] = INT_MAX;
            fore(j,1,k){
                  if(i-j<0){break;}
                  dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]));
                  //cout<<"dp["<<i<<"] = "<<dp[i]<<", j = "<<j<<'\n';
            }
            //cout<<"dp["<<i<<"]="<<dp[i]<<' ';
      }
      cout<<dp[n-1];


}

Measured memory_bytes: 4436
/*
  GOOD is not Enough
  You've got to be GREAT.
*/ 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
// #include<boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define mod 1000000007
#define FAST ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define f(i,n) for(int i=0;i<n;i++)
#define fp(i,k,n) for(int i=k;i<=n;i++)
#define fr(i,k,n) for(int i=k;i>=n;i--)
#define pb push_back
#define pii pair<int,int>
#define dbg(x) cout << (#x) << " is " << (x) << '\n' 
#define F first
#define S second
#define sz(x) (int)(x).size()
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(),a.end()
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;

void solve()
{
  int a,b;
  cin >> a >> b;
  cout << a*b << '\n'; 
  return;
} 

signed main()
{
  FAST
  int T=1;
  // cin >> T;
  while(T--)
  {
    solve();
  }
  return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef int Int;
typedef pair<Int, Int> pii;
typedef pair<Int, double> pid;
typedef pair<double, double> pdd;
typedef pair<Int, pii> pip;
typedef pair<pii, Int> ppi;
typedef pair<double, Int> pdp;
typedef vector<Int> veci;
typedef vector<double> vecd;
typedef vector<int> veci;
typedef vector<ll> vecll;
typedef vector<double> vecd;
typedef vector<pii> vecpii;
typedef vector<ppi> vecppi;
typedef vector<veci> mati;
typedef vector<vecll> matll;
typedef vector<vecd> matd;
#define PB(x) push_back(x)
#define EB(x) emplace_back(x)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (x).size()
#define CLR(x) memset(x,0,sizeof x)
#define pdebug() printf("%d\n",__LINE__)
#define REP(i, a, b) for(int i = (a);i <= (b);i++)
#define FORO(i, n) REP(i,0,(int)n-1)
#define FORI(i, n) REP(i,1,(int)n)
#define FORIT(i, t) for(auto i = t.begin();i != t.end();i++)
#define eps 1e-6
#define sqr(x) ((x)*(x))
#define dist(_a, _b) sqrt(sqr(_a.A-_b.A)+sqr(_a.B-_b.B))
#define norm(_a) sqrt(sqr(_a.A)+sqr(_a.B))
#define DEBUG 1
#if DEBUG
#define DUMP(a) do { std::cout << #a " = " << (a) << ", "; } while(false)
#define DUMPLN(a) do { std::cout << #a " = " << (a) << std::endl; } while(false)
#else
#define DUMP(a)
#define DUMPLN(a)
#endif
template<typename T, typename U>
inline void getMin(T &a, U b) { if (a > b) a = b; }
template<typename T, typename U>
inline void getMax(T &a, U b) { if (a < b) a = b; }
template<typename T>
vector<T> getVector(const int n) { return vector<T>(n); }
template<typename T>
vector<T> getVector(const int n, const T a) { return vector<T>(n, a); }
template<typename T>
vector<T> getEmptyVector() { return vector<T>(); }
template<typename T>
void appendAll(vector<T> &a, vector<T> b) { a.insert(a.end(), b.begin(), b.end()); }
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
// #define X first
// #define Y second
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
const ll MOD = 1000000007;
const int MAXN = 1 << 17;
const int inf = 1 << 27;
const ll llinf = 1LL << 50;
const int NIL = -inf;
int popcount(int x) { return __builtin_popcount(x); }



void solve() {
    ll N, X, M;
    cin >> N >> X >> M;
    vecll visited(M + 1);
    vecll tot(M + 1);
    ll ans = 0;
    for(int i = 1;i <= N;i++) {
        ans += X;
        tot[i] = X + tot[i - 1];
        if(visited[X]) {
            ll cycles = visited[X];
            ll diff = tot[i - 1] - tot[cycles - 1];
            ans -= X;
            ll ncycle = (i - visited[X]);
            ans += diff * ((N - i + 1) / ncycle);
            ans += tot[cycles + ((N - i + 1) % ncycle) - 1] - tot[cycles - 1];
            break;
        }
        visited[X] = i;
        X = (X * X) % M;
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int tc = 1;
    // cin >> tc;
    while(tc--) {
        solve();
    }

    return 0;
}


Measured memory_bytes: 4776