akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#include<bits/stdc++.h>
#define si(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define sd(a) scanf("%lf",&a)
#define ss(a) scanf("%s",a)
#define ms(a) memset(a,0,sizeof(a))
#define repi(i,a,b) for(register int i=a;i<=b;++i)
#define repd(i,a,b) for(register int i=a;i>=b;--i)
#define reps(s) for(int i=head[s],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
#define ce(i,r) i==r?'\n':' '
#define pb push_back 
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define pr(x) cout<<#x<<": "<<x<<endl
using namespace std;
const int MAX_N=1e2+5;
char s[MAX_N];
int main()
{
	ss(s+1);
	int ans=0;
	if(s[1]=='R'||s[2]=='R'||s[3]=='R') ans=1;
	if(s[1]=='R'&&s[2]=='R') ans=2;
	if(s[2]=='R'&&s[3]=='R') ans=2;
	if(s[1]=='R'&&s[2]=='R'&&s[3]=='R') ans=3;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 3756
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main(){
	int n;
  	cin >> n;
  
  	n = (n+1)/2;
  	cout << n << endl;
}

Measured memory_bytes: 3588
import sys
import os
import itertools
import numpy as np
from collections import deque
import copy

def main():
    if os.getenv("ENV")=='LOCAL':
        sys.stdin = open(os.path.dirname(__file__)+'/input.txt', 'r')

    H,W,K=map(int, input().split())
    C=[]
    for i in range(H):
        C.append(input())

    # print(C)
    ans=0
    W_list = []
    for j in range(W+1): #横
        W_list.extend(list(itertools.combinations([i for i in range(W)],j)))

    H_list = []
    for j in range(H+1): #縦
        H_list.extend(list(itertools.combinations([i for i in range(H)],j)))

    for W_set in W_list:
        for H_set in H_list:
            # 消す作業
            tmp=copy.copy(C)
            # print(type(tmp[0][0]))
            # print(W_set)
            # print(tmp)
            for w in W_set:
                # print(w)
                for i in range(H):
                    # if w
                    tmp[i]=tmp[i][:w]+'.'+tmp[i][w+1:]

            for h in H_set:
                for i in range(W):
                    tmp[h]=tmp[h][:i]+'.'+tmp[h][i+1:]

            count = 0
            for w in range(W):
                for h in range(H):
                    if tmp[h][w]=='#':
                        count+=1

            if count == K:
                ans+=1

    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 27120
#include <iostream>
#include <cstring>
#include <map>

using namespace std;

int rootK[200000];
int rootL[200000];

int getRootK(int v){ return rootK[v] == -1 ? v : rootK[v] = getRootK(rootK[v]); }
int getRootL(int v){ return rootL[v] == -1 ? v : rootL[v] = getRootL(rootL[v]); }

int main(){
	int N, K, L;
	while(cin >> N >> K >> L){
		memset(rootK, -1, sizeof(rootK));
		memset(rootL, -1, sizeof(rootL));
		for(int i=0;i<K;i++){
			int p, q; cin >> p >> q;
			p = getRootK(p-1);
			q = getRootK(q-1);
			if(p != q) rootK[q] = p;
		}
		for(int i=0;i<L;i++){
			int p, q; cin >> p >> q;
			p = getRootL(p-1);
			q = getRootL(q-1);
			if(p != q) rootL[q] = p;
		}
		map< pair<int,int>, int > cnt;
		for(int i=0;i<N;i++){
			++cnt[make_pair(getRootK(i), getRootL(i))];
		}
		for(int i=0;i<N;i++){
			cout << cnt[make_pair(getRootK(i), getRootL(i))];
			if(i == N-1) cout << endl;
			else cout << " ";
		}
	}
}


Measured memory_bytes: 13696
# D - AtCoder Express 2
# https://atcoder.jp/contests/abc106/tasks/abc106_d

import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nnn = lambda n: ss2nnn(ii2ss(n))

# N 個の都市
# M 本の列車
# Q 個の興味
def main_lte(N, M, Q, LRm, PQq):
    for p, q in PQq:
        ans = 0
        for l, r in LRm:
            if p <= l and r <= q:
                ans += 1
        print(ans)

def main_lte2(N, M, Q, LRm, PQq):
    table = [[0] * (N+1) for _ in range(N+1)]
    for l, r in LRm:
        table[l][r] += 1
    for p, q in PQq:
        ans = 0
        for i in range(p, q+1):
            for j in range(i, q+1):
                ans += table[i][j]
        print(ans)

def main_lte3(N, M, Q, LRm, PQq):
    table = [[0] * (N+1) for _ in range(N+1)]
    for l, r in LRm:
        table[l][r] += 1
    # 累積輪
    table2 = [[0] * (N+1) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, N+1):
            table2[i][j] = table2[i][j-1] + table[i][j]
    for p, q in PQq:
        ans = 0
        for i in range(p, q+1):
            ans += table2[i][q] - table2[i][p-1]
        print(ans)

def main(N, M, Q, LRm, PQq):
    table = [[0] * (N+1) for _ in range(N+1)]
    for l, r in LRm:
        table[l][r] += 1
    # 二次元累積輪
    for i in range(1, N+1):
        for j in range(1, N+1):
            table[i][j] += table[i][j-1]
    for i in range(1, N+1):
        for j in range(1, N+1):
            table[i][j] += table[i-1][j]
    for p, q in PQq:
        ans = table[q][q] + table[p-1][p-1] - table[p-1][q] - table[q][p-1]
        print(ans)

N, M, Q = i2nn()
LRm = ii2nnn(M)
PQq = ii2nnn(Q)
main(N, M, Q, LRm, PQq)


Measured memory_bytes: 58488
lis = []
while True:
    a = [i for i in input().split()]
    if a[1] == "?":
        break
    else:
        lis.append(a)

for i in lis:
    if i[1] == "+":
        print(int(i[0]) + int(i[2]))
    elif i[1] == "-":
        print(int(i[0]) - int(i[2]))
    elif i[1] == "*":
        print(int(i[0]) * int(i[2]))
    elif i[1] == "/":
        print(int(i[0]) // int(i[2]))



Measured memory_bytes: 5604
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
void yes(){ cout << "Yes" << endl; }
void no(){ cout << "No" << endl; }
int SIZE(string s){ return (int)s.size(); }

int main(){
    int n; cin >> n;
    vector<int> h(n);
    rep(i,n) cin >> h[i];
    rep(i,n-1){
        if(h[i] - h[i+1] > 1){
            no();
            return 0;
        } else if(h[i] - h[i+1] == 1) h[i+1]++;
    }
    yes();
    return 0;
}


Measured memory_bytes: 640
#include<stdio.h>
int main(void)
{
	int S,m,h,A,s;
	scanf("%d",&s);
	h=s/3600;
	A=s%3600;
	m=A/60;
	s=A%60;
	printf("%d:%d:%d\n",h,m,s);
	return 0;
}

Measured memory_bytes: 592
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;
typedef pair<int, int>P;

vector<P>E[100000];
int d[100000];
int main() {
	int v, e, r; scanf("%d%d%d", &v, &e, &r);
	rep(i, e) {
		int s, t, d; scanf("%d%d%d", &s, &t, &d);
		E[s].push_back(P(t, d));
	}
	memset(d, 0x3f, sizeof(d));
	priority_queue<P, vector<P>, greater<P>>que;
	d[r] = 0;
	que.push(P(0, r));
	while (!que.empty()) {
		P p = que.top(); que.pop();
		if (p.first != d[p.second])continue;
		for (P u : E[p.second]) {
			if (d[u.first] > d[p.second] + u.second) {
				d[u.first] = d[p.second] + u.second;
				que.push(P(d[u.first], u.first));
			}
		}
	}
	rep(i, v) {
		if (d[i] == INF)puts("INF");
		else printf("%d\n", d[i]);
	}
}

Measured memory_bytes: 13084
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sc(n) scanf("%d",&n)
#define scl(n) scanf("%lld",&n)
#define pr(n) printf("%d",n)
#define prl(n) printf("%lld",n)
#define nl printf("\n")
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
ll pow1(ll a, ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
		{
			ans=ans*a;
		}
		a=a*a;
		b=b>>1;
	}
	return ans;
}
int main()
{
	int d;
	cin>>d;
	if(d == 24)
	{
		cout<<"Christmas Eve"<<endl;
		return 0;
	}
	if(d == 23)
	{
		cout<<"Christmas Eve Eve"<<endl;
		return 0;
	}
	if(d == 22)
	{
		cout<<"Christmas Eve Eve Eve"<<endl;
		return 0;
	}
	if(d == 25)
	{
		cout<<"Christmas"<<endl;
		return 0;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
int p2(int n)
{
  int ans = 1;
  while(n--) ans = (2 * ans) % MOD;
  return ans;
}
int main(void)
{
  int n; cin >> n;
  std::vector<int> l(n);
  for(int i = 0; i != n; i++) cin >> l[i];
  sort(l.begin(), l.end());
  bool c = true;
  for(int i = 0; i != n; i++){
    if(n % 2){if(l[i] != (i + 1) / 2 * 2) c = false;}
    else if(l[i] != 1 + (i / 2) * 2) c = false;
  }
  cout << (c ? p2(n / 2) : 0) << endl;
  return 0;
}

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

int main() {
  char c;
  cin >> c;

  // ここにプログラムを追記
  if (c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o') {
    cout << "vowel" << endl;
  }
  else {
    cout << "consonant" << endl;
  }
  
}


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

using namespace std;

const int maxn = 110;
const int maxm = 1e5+10;

int w[maxn], v[maxn];

int dp[maxm];

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

	for (int i = 1; i <= n; i++)
		cin >> w[i] >> v[i];

	for (int i = 1; i < maxm; i++)
		dp[i] = m+1;

	for (int i = 1; i <= n; i++)
		for (int j = maxm-1; j >= v[i]; j--)
			dp[j] = min(dp[j], dp[j-v[i]]+w[i]);

	int ans = 0;
	for (int i = 1; i < maxm; i++)
		if (dp[i] <= m) ans = i;

	cout << ans << "\n";
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
    int n;cin>>n;
    int dp[n+1][3];
    dp[0][0] = dp[0][1] = dp[0][2] = 0;
    for(int i = 1; i < n+1; i++) 
    {
        int a,b,c;
        cin >> a >> b >> c;
        dp[i][0] = max(dp[i-1][1],dp[i-1][2]) + a;
        dp[i][1] = max(dp[i-1][0],dp[i-1][2]) + b;
        dp[i][2] = max(dp[i-1][0],dp[i-1][1]) + c;
    }
    cout << max(dp[n][0],max(dp[n][1],dp[n][2])) << endl;
    
    return 0;
}

Measured memory_bytes: 2560
#include <stdio.h>

int main(){
  int i, a, b, c, n = 0;
  scanf("%d %d %d", &a, &b, &c);
  for(i = a;i <= b;i++){
    if(c % i == 0) n += 1;
    }
    printf("%d\n", n);
  return 0;
}



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

const int MOD = 1000000007;
const int INF = 1e9;

//long long
using ll = long long;

//出力系
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
 
// begin() end()
#define all(x) (x).begin(),(x).end()

//for
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n, i##_len=(n); i>=0; i--)
#define FOR(i,a,b) for(int i=(a), i##_len=(b); i<i##_len; ++i)

//最大公約数 
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

int main(){
int N;
cin >> N;
vector<int>A(N);
REP(i, N) cin >> A.at(i);

//左からの累積GCD
vector<int>left(N + 1, 0);
REP(i, N){
  left.at(i + 1) = gcd(left.at(i), A.at(i));
}

//右からの累積GCD
vector<int>right(N + 1, 0);
for (int i = N - 1; i >= 0; --i){
  right.at(i) = gcd(A.at(i), right.at(i + 1));
}

int ans = 0;
REP(i, N){
  int l = left.at(i);
  int r = right.at(i + 1);
  chmax(ans, gcd(l, r));
}
print(ans);
}

Measured memory_bytes: 1408
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
 
int N,K;

int main(void)
{
    cin >> N >>K;
    vector<int> H(N);
    for(int a=0;a<N;a++){
        cin >> H[a];
    }
    sort(H.begin(),H.end(),std::greater<int>());
    ll ans=0;
    for(int a=0;a<N;a++){
        if(a<K){
            //ans++;
        }else{
            ans+=H[a];
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3992
import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int X[] = new int[N];
        
        for(int i = 0; i < N; i++){
        	X[i] = sc.nextInt();
        }
        
        int min = Integer.MAX_VALUE;
        
        for(int i = 0; i <= 100; i++){
        	int sum = 0;
            for(int j = 0; j < N; j++){
            	sum += Math.pow((i - X[j]), 2);
            }
            min = Math.min(min, sum);
        }
        System.out.println(min);
    }
}

Measured memory_bytes: 21716
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pb push_back
 
const int maxn = 1e3 + 20;
const int mod = 1e9 + 7;

int a[maxn] , b[maxn];

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

	int n , m;
	cin >> n >> m;

	for(int i = 0; i < n; i++)
		cin >> a[i];

	for(int i = 0; i < m; i++)
		cin >> b[i];

	sort(a , a + n);
	if(unique(a , a + n) - a != n)
		return cout << 0 << endl , 0;

	sort(b , b + m);
	if(unique(b , b + m) - b != m)
		return cout << 0 << endl , 0;

	int pt1 = n , pt2 = m , res = 1;
	for(int i = n * m; i >= 1; i--)
	{
		while(pt1 >= 0 && a[pt1 - 1] >= i)
			pt1--;
		while(pt2 >= 0 && b[pt2 - 1] >= i)
			pt2--;

		if(a[pt1] == i && b[pt2] == i)
			continue;

		if(a[pt1] == i)
			res = 1LL * res * (m - pt2) % mod;
		else if(b[pt2] == i)
			res = 1LL * res * (n - pt1) % mod;
		else
			res = 1LL * res * ((n - pt1) * (m - pt2) - (n * m - i)) % mod;
	}

	cout << res << endl;
}


















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

typedef long long ll;
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

const int MOD = 1e9 + 7 ;
const double PI = 2 * acos(0.0) ;

int main()
{
    ll num, base ;
    cin >> num >> base ;
    int dig = (int)(floor( log(num) /  log(base)) + 1);
    cout << dig << endl ;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
#else
#define show(x) true
#endif

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);
	
	int N,M;
	cin >> N >> M;
	V<int> a(N+1);
	rep(i,M){
		int l,r;
		cin >> l >> r;
		l--;
		a[l]++,a[r]--;
	}
	rep(i,N) a[i+1] += a[i];
	int ans = 0;
	rep(i,N) if(a[i] == M) ans++;
	cout << ans << endl;
}


Measured memory_bytes: 640
#include <stdio.h>

int main(void)
{
    int q, p, n;
    long long r;
    char c[2];
    scanf("%d", &q);
    r=0;
    while (q--) {
        scanf("%d%s%d", &p, c, &n);
        r+=(*c=='(')?n:-n;
        puts(r?"No":"Yes");
        fflush(stdout);
    }
    return 0;
}

Measured memory_bytes: 592
import sys
input = lambda: sys.stdin.readline().rstrip()

a, b, m = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
xyc = []
for _ in range(m):
    xyc.append([int(x) for x in input().split()])
ans = min(A) + min(B)
for i in range(m):
    x, y, c = xyc[i]
    temp = A[x - 1] + B[y - 1] - c
    ans = min(ans, temp)
print(ans)

Measured memory_bytes: 76396
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,m,n) for(int i=(int)(m);i<(int)(n);++i)
#define rREP(i,m,n) for(int (i)=(n)-1; (i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 1000000001;
constexpr ll mod = 1000000007;
constexpr double PI = 3.1415926535897932;

template<class T>inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T>inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

int main() {
	init();

	vector<int>vec(3);
	rep(i, 0, 3)cin >> vec[i];
	if (vec[0]%2==0&&vec[0] == vec[1] && vec[1] == vec[2]) {
		cout << -1 << "\n";
		return 0;
	}
	int cnt = 0;
	while (1) {
		rep(i, 0, 3) {
			if (vec[i] % 2 == 1) {
				cout << cnt << "\n";
				return 0;
			}
		}
		int x = (vec[1] + vec[2]) / 2, y = (vec[0] + vec[2]) / 2, z = (vec[0] + vec[1]) / 2;
		vec[0] = x;
		vec[1] = y;
		vec[2] = z;
		++cnt;
	}

	return 0;
}

Measured memory_bytes: 256
n=int(input())
a,b=map(int,input().split())
p=list(map(int,input().split()))
x1=[]
x2=[]
x3=[]
for i in range(n):
    if p[i]<=a:
        x1.append(p[i])
    elif a<p[i]<=b:
        x2.append(p[i])
    else:
        x3.append(p[i])
print(min(len(x1),len(x2),len(x3)))


Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;
int Array[200005];

int main(){
    int N , k , i;
    scanf( "%d%d" , &N , &k );

    for( i = 1 ; i <= N ; ++i )
        scanf( "%d" , Array + i );
    
    sort( Array + 1 , Array + N + 1 , greater<int>() );
    long long Ans = 0LL;

    for( i = k + 1 ; i <= N ; ++i )
        Ans = Ans + Array[i];

    printf( "%lld\n" , Ans );
    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a[3];
	int ans=0;
	for(int i=0;i<3;i++)
	{
		cin>>a[i];
	}
	sort(a,a+3);
	for(int i=0;i<3;i++)
	{
		if(i==0)
		{
			continue;
		}
		else
		{
			ans+=abs(a[i]-a[i-1]);
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
ll read(){
	ll a=0,b=getchar(),c=1;
	while(!isdigit(b))c=b=='-'?-1:1,b=getchar();
	while(isdigit(b))a=a*10+b-'0',b=getchar();
	return a*c;
}
int a[200005];
ll n,ans[200005],b[200005],c[200005];
vector<int> g[200005];
ll gg(ll x){
	return x*(x-1)/2+x;
}
void dfs(int x,int y){
	c[x]=1;
	ll d=a[x],s=b[d];
	for(int i=0;i<g[x].size();i++)
		if(g[x][i]!=y){
			int tmp=b[d];
			dfs(g[x][i],x);
			c[x]+=c[g[x][i]];
			ans[d]-=gg(c[g[x][i]]-(b[d]-tmp));
		}
	b[d]=s+c[x];
}
int main(){
	n=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=1;i<n;i++){
		int x=read(),y=read();
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
		ans[i]=gg(n);
	dfs(1,0);
	for(int i=1;i<=n;i++){
		ans[i]-=gg(n-b[i]);
		printf("%lld\n",ans[i]);
	}
	return 0;
}

Measured memory_bytes: 38808
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <cmath>

using namespace std;
using ll = long long int;

template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
  for (auto i = v.begin(); i != v.end(); i++) {
    os << *i << " ";
  }
  return os;
}


void solve(long long N, long long K, string S){
  vector<ll> v;
  char now = '1';
  ll cnt = 0;
  for(ll i=0; i<N; i++) {
    if(S[i]==now) {
      cnt++;
    } else {
      now = S[i];
      v.push_back(cnt);
      cnt = 1;
    }
  }
  v.push_back(cnt);
  if(*(S.end()-1) == '0') v.push_back(0);
  vector<ll> sum(v.size()+1, 0);
  for(ll i=0; i<sum.size(); i++) {
    sum[i+1] = sum[i] + v[i];
  }
  //std::cout << sum << std::endl;
  //std::cout << v << std::endl;
  ll ans = 0;
  for(ll i=0; i<v.size(); i+=2) {
    ll left = i;
    ll right = min((ll)i+K*2+1, (ll)v.size());
    ll now = sum[right]-sum[left];    
    //std::cout << now << std::endl;
    ans = max(ans, now);
  }
  std::cout << ans << std::endl;
}

int main(){
  long long N;
  scanf("%lld",&N);
  long long K;
  scanf("%lld",&K);
  string S;
  cin>>S;
  solve(N, K, S);
  return 0;
}



Measured memory_bytes: 2164
n = int(input())
S = []

for i in range(n):
    s = input()
    S.append(s)

print("AC x " + str(S.count("AC")))
print("WA x " + str(S.count("WA")))
print("TLE x " + str(S.count("TLE")))
print("RE x " + str(S.count("RE")))


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

int main()
{
    int arr[3];
    cin>>arr[0]>>arr[1]>>arr[2];
    sort(arr,arr+3);
    if(arr[2]==arr[1]+arr[0])
    {
        cout<<"Yes"<<endl;
    }
    else cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, a, b) for (int i = a; i >= b; i--)
#define fore(i, a) for (auto &i : a)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

int main() {
  ll a[3], k;
  ll ans = 0;
  cin >> a[2] >> a[1] >> a[0] >> k;
  for (int i = 2; i >= 0; --i) {
    ans += (i - 1) * min(a[i], k);
    k -= min(a[i], k);
  }
  cout << ans;
}


Measured memory_bytes: 3600
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define ff first
#define ss second

const long long MAXN = 2e5 + 21, LG = 20, inf = 0x3f3f3f3f, mod = 998244353;

long long n;
long long cnt[MAXN], v[MAXN];
long long dp[1 << 21];
long long ans, st;

long long dfs(int root) {
	if(root == 0) 
        return 0;
	if(dp[root] ^ -1) 
        return dp[root];

	dp[root] = inf;
	
    for(int i = 0; i < 16; i++)
		if(root>>i&1) {
			for(int j = 0; j < 16; j++)
				if(root>>j&1) {
					int x = j ^ i;
					int nxt = root ^ (1 << j) ^ (1 << i) ^ (1 << x);
					if(__builtin_popcount(nxt) < __builtin_popcount(root))
					    dp[root] = min(dp[root], dfs(nxt) + 1 + ((root & (1 << x)) == (1 << x)));
				}
		}
	return dp[root];
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i < n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
		v[x] ^= z;
		v[y] ^= z; 
	}
	
    memset(dp, -1, sizeof dp);

	for(int i = 0; i < n; i++)
        if(v[i]) 
            cnt[v[i]]++;
	
	for(int i = 1; i < 16; i++) {
		ans += cnt[i] / 2;
		st |= (cnt[i] & 1) << i;
	}
	
    ans += dfs(st);
	cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 18688
def factorial(n):
    ans = 1
    for i in range(2, n + 1):
        ans = ans * i % 1000000007
    return ans
n, m = map(int, input().split())
MOD = 10**9 + 7
if n == m:
    print(2 * factorial(n) ** 2 % MOD)
elif abs(n - m) == 1:
    print(factorial(min(m, n)) ** 2 * max(m, n) % MOD)
else:
    print(0)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define int long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define PI acos(-1)
#define bp __builtin_popcountll
#define all(x) x.begin(),x.end()
#define sp fixed<<setprecision
#define pii pair<long long,long long>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

int MOD = (1e9)+7;
const int N = (1e6)+5;

signed main()
{
    FAST
    int tc=1;
    //cin>>tc;
    for(int ti=1;ti<=tc;ti++)
    {
        string s;
        cin>>s;
        int fl = 0;
        for(int j=0;j<3;j++)if(s[j]=='7')fl=1;
        if(fl)cout<<"Yes";
        else cout<<"No";
    }
    return 0;
}
/*
Test Case
*/


Measured memory_bytes: 3648
#include "bits/stdc++.h"

#define YESNO(x) x ? printf("YES") : printf("NO")
#define YesNo(x) x ? printf("Yes") : printf("No")
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define scani(x) scanf("%d", &x)
#define scanll(x) scanf("%lld", &x)
#define printi(x) printf("%d", x)
#define printll(x) printf("%lld", x)
typedef long long ll;
using namespace std;

long long GCD(long long x, long long y) {
	return y ? GCD(y, x % y) : x;
}

long long LCM(long long x, long long y) {
	return x * y / GCD(x, y);
}

int Main() {
	int s, w;
	scani(s);
	scani(w);

	if (s <= w) {
		printf("unsafe");
	}
	else {
		printf("safe");
	}

	return 0;
}

int main()
{
	Main();
	return 0;
}


Measured memory_bytes: 3780
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
#define Mod 1000000007
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
#define INF 1ll<<59



int main(){
  ll i,j;
  ll n;
  cin>>n;
  ll  a[n],b[n];
  for(i=0;i<n;i++){
    cin>>a[i]>>b[i];
  }
  vector<P> v;
  for(i=0;i<n;i++) v.pb(P(b[i],a[i]));
  sort(v.begin(),v.end());

  ll t=0;
  for(i=0;i<n;i++){
    t+=v[i].se;
    if(t>v[i].fi) {
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;
  return 0;  
}

Measured memory_bytes: 9456
s = "MARCH"
c = Array.new(5, 0)
gets.to_i.times do
  t = gets.chomp
  s.size.times do |i|
    c[i] += 1 if t[0] == s[i]
  end
end
ans = 0
s.size.times do |i|
  (i+1..4).each do |j|
    (j+1..4).each do |k|
      ans += c[i] * c[j] * c[k]
    end
  end
end
puts ans

Measured memory_bytes: 1788
#include<iostream>
#include<stdio.h>
 using namespace std;
int main()
{
    int h, w;
    int i, j;
    cin >> h;
    cin >> w;
    while (h != 0 || w != 0){
        for (i = 0; i < h; i++){
        	if(i+1!=1&&i+1!=h){
            	for (j = 0; j < w; j++){
	                if(j+1==1||j+1==w)cout << "#";
	                else cout << ".";
	            }
        	}
        	if(i+1==1||i+1==h){
        		for (j = 0; j < w; j++)cout << "#";
        	}
            cout << "\n";
        }
        cout << "\n";
        cin >> h;
        cin >> w;
    }
    return 0;
}

Measured memory_bytes: 1120
#include <bits/stdc++.h>
using namespace std;
long long N,K;
long long int_MAX=1000000007;
int main(){
	cin>>N>>K;
	long long total=0;
	for(int i=K; i<=N+1; i++){
		total+=(N-i+1)*i+1%int_MAX;
		total=total%int_MAX;
	}
	cout<<total<<'\n';
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll N;
  ll K;
  cin >> N;
  ll Ans = 0;
  K = N-1;
  for (ll i = 1; ; i++){
    if ((K/i) == 0) break;
    Ans += (K/i);
  }
  cout << Ans << endl;
  return 0;
}

Measured memory_bytes: 3644
(defun carmincost (rest done mincosts)
  "To compute minimum cost to car of rest."
  (let ((dest (car rest)))
    (apply #'min (remove nil (mapcar (lambda (depth)
				       (let ((from (nth depth done))
					     (mincost (nth depth mincosts)))
					 (when from
					   (+ mincost (abs (- dest from))))
					 ))
				     '(0 1))))))
(defun solve (initial-list)
  (labels ((aux (rest done mincosts)
	     (if rest
		 (let ((mincost (carmincost rest done mincosts)))
		   (aux (cdr rest) (cons (car rest) done) (cons mincost mincosts)))
		 (car mincosts))
	     ))
    (aux (cdr initial-list) (list (car initial-list)) '(0))))
(let* ((n (read))
       (initial-list (loop for i from 1 to n
			collect (read))))
  (princ (solve initial-list))
  (princ #\newline))


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

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

    int max = 0, x = 0;

    for(int i = 0; i < N; i++){
        if(s.at(i) == 'I'){
            x++;
            if(max < x){
                max = x;
            }
        }

        if(s.at(i) == 'D'){
            x--;
        }
    }

    cout << max << endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>

using std::cin;
using std::cout;



int main(int argc, char* argv[])
{
  std::ios::sync_with_stdio(false);
  cin.tie(nullptr);

  std::set<std::pair<int,int>> edges;
  for (int i = 0; i < 3; ++i)
  {
    int ai, bi;
    cin >> ai >> bi;
    edges.insert({ai, bi});
    edges.insert({bi, ai});
  }

  bool possible = false;
  std::vector<int> a = {1, 2, 3, 4};
  do
  {
    possible = edges.count({a[0], a[1]}) && edges.count({a[1], a[2]}) && edges.count({a[2], a[3]});
  }
  while (!possible && std::next_permutation(a.begin(), a.end()));

  cout << (possible ? "YES\n" : "NO\n");

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
  {int K, N; cin >> K >> N;
  vector<int> A(N); for (auto &a : A) cin >> a;
  int m = K - A[N - 1] + A[0];
  for (int i = 1; i < N; ++i) m = max(m, A[i] - A[i - 1]);
  cout << K - m << endl;}

Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main(){
    int x;
    cin>>x;
    int a=1;
    int ans=1;
    for(int i=1;i<=31;i++){
        for(int j=2;j<=10;j++){
            a=1;
            for(int k=0;k<j;k++){
                a=a*i;
            }
        if(a>ans&&a<=x) ans=a;
        }
    }
    cout<<ans;
}

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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const ll INF = 1e15;
const int MOD = 1e9+7;
const ll LINF = 1e18;


signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n; cin>>n;
  vll a(n);
  rep(i,n) cin>>a[i];
  a.push_back(a[n-1]);
  ll ans=0;
  ll pos=0;
  while(pos<n){
    ll up;
    for(up=pos; up<n; up++){
      if(a[up]>a[up+1]) break;
    }
    ll dw;
    for(dw=pos; dw<n; dw++){
      if(a[dw]<a[dw+1]) break;
    }
    ans++;
    // cout<<up<<" "<<dw<<" "<<pos<<endl;
    pos=max(up,dw)+1;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 1792
s=int(input())
mod=10**9+7
max=10**4
fac=[0]*max
facinv=[0]*max
inv=[0]*max
fac[0]=fac[1]=1
facinv[0]=facinv[1]=1
inv[1]=1
for i in range(2,max):
    fac[i]=fac[i-1]*i%mod
    inv[i]=mod-inv[mod%i]*(mod//i)%mod
    facinv[i]=facinv[i-1]*inv[i]%mod
def com(n,k):
    if n<k: return 0
    if n<0 or k<0: return 0
    return fac[n]*(facinv[k]*facinv[n-k]%mod)%mod
ans=0
for i in range(1,700):
    if s-3*i<0: break
    temp=s-3*i
    ans+=com(temp+i-1,i-1)
    ans%=mod
print(ans%mod)

Measured memory_bytes: 65048
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;
long long int di[] = {-1, 0, 1, 0, -1, 1, 1, -1};
long long int dj[] = {0, 1, 0, -1, 1, 1, -1, -1};

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */

int main() {
  
  
  lint a, b, k; cin >> a >> b >> k;
  if(a >= 0) {
    lint v = min(k, a);
    k -= v;
    a -= v;
  }

  if(b >= 0) {
    lint v = min(k, b);
    k -= v;
    b -= v;
  }

  cout << a << " " << b << endl;
  return 0;
}


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

using namespace std;

int W, H;
int _x1 = 0, _y1 = 0; // outside
int _x2 = 0, _y2 = 1; // inside
int mode1 = 0, mode2 = 0;

void Move(int& x, int& y, int mode) {
	if (mode == 0) {
		++x;
	}
	else if (mode == 1) {
		++y;
	}
	else if (mode == 2) {
		--x;
	}
	else {
		assert(false);
	}
}
void f(int target) {
	if (target == 0) { // outside
		if (mode1 == 0 && _x1 >= W-1) ++mode1;
		if (mode1 == 1 && _y1 >= H-1) ++mode1;
		Move(_x1, _y1, mode1);
	}
	else { // inside
		if (mode2 == 0 && _x2 >= W-2) ++mode2;
		if (mode2 == 1 && _y2 >= H-2) ++mode2;
		Move(_x2, _y2, mode2);
	}
}
bool check() {
	if ( abs(_x1 - _x2) + abs(_y1 - _y2) == 1 ) {
		return true;
	}
	return false;
}
int main() {
	int N; cin >> W >> H >> N;
	int ans = 0;
	for (int i = 0; i < N; ++i) {
		int p; cin >> p;
		f(p);
		if (check()) ++ans;
	}
	cout << ans << endl;
}

Measured memory_bytes: 3116
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)

int main(){
    int N;
    cin >> N;
    long long  ans=1;
    for(int i = 1; i <= N; i++){
        ans = ans*i%1000000007;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#pragma GCC optimize (3)
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<unordered_map>
/*#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/trie_policy.hpp>
#include<ext/pb_ds/priority_queue.hpp>*/
//#include<ext/rope>
#define ll long long
#define ull unsigned long long
#define INFI 2147483647
#define INFL 9223372036854775807
#define INFU 18446744073709551615
#define maxn 350
using namespace std;
//using namespace __gnu_pbds;
//using namespace __gnu_cxx;
const double PI=acos(-1.0);
const double eps=1e-6;
ll g[maxn][maxn],g2[maxn][maxn];
inline ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
template<typename T> void debug(T x)
{
    cout<<"value="<<x<<endl;
    return;
}
signed main()
{
	//ios_base::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    ll n=read(),m=read(),L=read();
    for(ll i=1;i<=n;i++) for(ll j=1;j<=n;j++) g[i][j]=50000000000000;
    for(ll i=1;i<=n;i++) for(ll j=1;j<=n;j++) g2[i][j]=50000000000000;
    for(int i=1;i<=n;i++) g[i][i]=0;
    for(int i=1;i<=n;i++) g2[i][i]=0;
    for(ll i=1;i<=m;i++){
        ll u=read(),v=read(),w=read();
        if(w>L) continue;
        else{
            g[u][v]=w;
            g[v][u]=w;
        }
    }
    for(ll k=1;k<=n;k++)
        for(ll i=1;i<=n;i++)
            for(ll j=1;j<=n;j++)
                if(g[i][k]+g[k][j]<=g[i][j])
                    g[i][j]=g[i][k]+g[k][j];
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(g[i][j]<=L) g2[i][j]=1LL;
    for(ll k=1;k<=n;k++)
        for(ll i=1;i<=n;i++)
            for(ll j=1;j<=n;j++)
                if(g2[i][k]+g2[k][j]<=g2[i][j])
                    g2[i][j]=g2[i][k]+g2[k][j];
    ll Q=read();
    for(ll i=1;i<=Q;i++){
        ll s=read(),t=read();
        if(g2[s][t]<50000000000000) printf("%lld\n",g2[s][t]-1);
        else cout<<-1<<endl;
    }
	return 0;
}


Measured memory_bytes: 5416
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include <functional>
#include<time.h>
#include <stack>
#include<iomanip>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define ll long long
#define llint long long int
#define sort(s) sort(s.begin(),s.end())
#define reverse(v)  reverse(v.begin(), v.end());
#define Yes(ans) if(ans)cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define hei(a) vector<a>
#define whei(a) vector<vector<a>>
#define UF  UnionFind 
#define Pint pair<int,int>
#define Pll pair<llint,llint>
#define keta(a)  fixed << setprecision(a)
constexpr auto INF = 1000000000000000000;
constexpr auto mod = 1000000007;
//辞書順はnext_permutation( begin( v ), end( v ) );やで！
struct edge { int to, cost; };

ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0)return a;
	return gcd(b, a % b);
}

long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

// mod. m での a の逆元 a^{-1} を計算するよ！
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}


//aCbをmod.mで割った余りを求める
int c(int a, int b, int m) {
	int ans = 1;
	for (int i = 0; i < b; i++) {
		ans *= a - i;
		ans %= m;
	}
	for (int i = 1; i <= b; i++) {
		ans *= modinv(i, m);
		ans %= m;
	}
	return ans;
}
struct UnionFind {
	vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

	UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
		for (int i = 0; i < N; i++) par[i] = i;
	}
	int size(int a) {
		return par[root(a)];
	}

	int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
		if (par[x] == x) return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y) { // xとyの木を併合
		int rx = root(x); //xの根をrx
		int ry = root(y); //yの根をry
		if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
		par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
	}

	bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};

int b_s(vector<int>& a, int key) {
	int left = -1;
	int right = a.size();
	while (right - left > 1) {
		int mid = left + (right - left) / 2;
		if (a[mid] >= key)right = mid;
		else left = mid;
	}
	return left;
}

int main() {
	int a, b,c;
	cin >> a >> b >> c;
	int ans = 0;
	rep(i, a, b + 1)if (i % c == 0)ans++;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;

int main() {
  string s, t;
  cin >> s >> t;
  int n = sz(s), m = sz(t);
  vector<vector<int>> is(26);
  rep(i,n) is[s[i]-'a'].push_back(i);
  rep(i,n) is[s[i]-'a'].push_back(i+n);
  ll ans = 0;
  int p = 0; // after p
  rep(i,m) {
    int c = t[i]-'a';
    if (sz(is[c]) == 0) {
      puts("-1");
      return 0;
    }
    p = *lower_bound(is[c].begin(), is[c].end(), p)+1;
    if (p >= n) {
      p -= n;
      ans += n;
    }
  }
  ans += p;
  cout << ans << endl;
  return 0;
}


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

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str;

        int count = 0;

        str = br.readLine();
        String W = str.toLowerCase();
        while((str = br.readLine()) != null){
           String x = str.toLowerCase();
           String[] temp = x.split("\\s");
           for(int i =0;i<temp.length;i++){
                if(temp[i].equals("END_OF_TEXT")){
                    break;
                }
               if(W.equals(temp[i])){
                   count++;
               }
           }
        } 
        br.close();
        System.out.println(count);
    }
}

Measured memory_bytes: 24388
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> P;
typedef priority_queue<P,vector<P>,greater<P>> P_queue;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n+1)
#define pb push_back
#define mp make_pair
#define ALL(a) a.begin(),a.end()
#define SORT(a) sort(ALL(a))

const ll MOD=998244353;
const ll mod=1000000007;
const ll INF=1e15;
vec dx={1,0,-1,0};
vec dy={0,1,0,-1};

const ll MAXN=200003;

bool used[MAXN];
vec G[MAXN];
ll Par[MAXN][4];

void dfs(ll x){
    used[x]=true;
    rep(i,G[x].size()) {
        ll y=G[x].at(i);
        if(!used[y]) {
            rep(j,3) Par[y][j+1]=Par[x][j];
            dfs(y);
        }
    }
    return;
}


ll par[500001];
ll rnk[500001];
ll Size[500001];

void shoki(){
    for(ll i=0;i<500001;i++) {par[i]=i; rnk[i]=0; Size[i]=1;}
}

ll sch(ll x){
    if(par[x]==x) return x;
    else return par[x]=sch(par[x]);
}

void con(ll A,ll B){
    A=sch(A);
    B=sch(B);
    if(A==B) return;
    if(rnk[A]>rnk[B]) swap(A,B);
    par[A]=B;
    Size[B]+=Size[A];
    Size[A]=Size[B];
    if(rnk[A]==rnk[B]) rnk[B]++;

    return;
}

ll is_size(ll k){
    return Size[sch(k)];
}

bool same(ll A,ll B){
    return sch(A)==sch(B);
}

void CON(ll a, ll b){
    con(a,b+MAXN);
    con(a+MAXN,b);
    return;
}

int main(){
    ll N; cin>>N;
    shoki();
    rep(i,N-1){
        ll x,y; cin>>x>>y;
        x--; y--;
        CON(x,y);
    }

    ll A=sch(0), B=sch(MAXN);
    ll countA=0, countB=0;
    rep(i,N){
        if(sch(i)==A) countA++;
        else countB++;
    }

    vec ans(N,0);
    ll C1=(N+2)/3, C2=(N+1)/3, C3=N/3;
    ll M1=C1, M2=C2, M3=C3;
    if(countA<=N/3){
        rep(i,N){
            if(sch(i)==A) {ans.at(i)=(M3-C3)*3+3; C3--;}
            else {
                if(C1>0) {ans.at(i)=(M1-C1)*3+1; C1--;}
                else if(C2>0) {ans.at(i)=(M2-C2)*3+2; C2--;}
                else {ans.at(i)=(M3-C3)*3+3; C3--;}
            }
        }
    }
    else if(countB<=N/3){
        rep(i,N){
            if(sch(i)==B) {ans.at(i)=(M3-C3)*3+3; C3--;}
            else {
                if(C1>0) {ans.at(i)=(M1-C1)*3+1; C1--;}
                else if(C2>0) {ans.at(i)=(M2-C2)*3+2; C2--;}
                else {ans.at(i)=(M3-C3)*3+3; C3--;}
            }
        }
    }
    else{
        rep(i,N){
            if(sch(i)==A){
                if(C1>0) {ans.at(i)=(M1-C1)*3+1; C1--;}
                else {ans.at(i)=(M3-C3)*3+3; C3--;}
            }
            if(sch(i)==B){
                if(C2>0) {ans.at(i)=(M2-C2)*3+2; C2--;}
                else {ans.at(i)=(M3-C3)*3+3; C3--;}
            }
        }
    }
    rep(i,N) cout<<ans.at(i)<<' ';
    cout<<endl;
    




}

Measured memory_bytes: 21632
H,W = map(int,input().split())
A = []
for i in range(H):
    a = input()
    A.append(a)

ansW,ansH = [],[]
for hi in range(H):
    for wi in range(W):
        if A[hi][wi] == "#":
            break
    else:
        ansH.append(hi)
for wi in range(W):
    for hi in range(H):
        if A[hi][wi] == "#":
            break
    else:
        ansW.append(wi)

Ans = []
for hi in range(H):
    if hi not in ansH:
        ans = ""
        for wi in range(W):
            if wi not in ansW:
                ans += A[hi][wi]
        Ans.append(ans)

for ans in Ans:
    print(ans)



Measured memory_bytes: 3064
#include <stdio.h>

int main(){
  int flag,n,i,j,tmp,cnt=0;
  int A[100];

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  flag = 1;
  while(flag==1){
    flag = 0;
    for(j=n-1;j>0;j--){
      if(A[j]<A[j-1]){
	tmp = A[j];
	A[j] = A[j-1];
	A[j-1] = tmp;
	cnt++;
	flag = 1;
      }
    }
  }
	
  for(i=0;i<n-1;i++){
    printf("%d ",A[i]);
  }
  printf("%d\n%d\n",A[n-1],cnt);

  return 0;
}



Measured memory_bytes: 2044
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
using ll = long long;
using P = pair<int,int>;
int main(void) {
    int a, b, c; cin >> a >> b >> c;
    map<int, int> mp;
    mp[a]++, mp[b]++, mp[c]++;
    cout << mp.size();
}


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

string calcAddition( string a, string b )
{
    int as = a.size(), bs = b.size(), d = as > bs ? as - bs : bs - as;
    string s = "0", t = "0";
    for( int i = 0; i < d; i++ )
        as > bs ? t += "0" : s += "0";
    s += a; t += b;

    for( int i = s.size() - 1; i >= 1; i-- )
    {
        s[i] += t[i] - '0';
        if( s[i] > '9' )
        {
            s[i] -= 10;
            s[i-1]++;
        }
    }

    bool j = true;
    for( int i = 0; i < s.size(); i++ )
        if( s[i] != '0' )
            j = false;
    if( j )
        return "0";
    return s[0] == '0' ? s.substr( 1, s.size() ) : s;
}

string calcSubtraction( string a, string b )
{
    int as = a.size(), bs = b.size(), d = as - bs;
    string s = "", t = "";
    for( int i = 0; i < d; i++ )
        t += "0";

    s += a;
    t += b;

    for( int i = s.size() - 1; i >= 0; i-- )
    {
        if( s[i] < t[i] )
        {
            s[i] += 10;
            if( s[i-1] >= '1' )
                s[i-1]--;
            else
            {
                int j = i - 1;
                while( s[j] == '0' )
                    s[j--] += 9;
                s[j]--;
            }
        }
        s[i] -= ( t[i] - '0' );
    }

    if( s.size() == 1 )
        return s;

    for( int i = 0; i < s.size(); i++ )
    {
        if( '1' <= s[i] && s[i] <= '9' )
            return s.substr( i, s.size() );
    }

    return "0";
}

int main()
{
    string a, b, c;

    cin >> a >> b;

    c = b;
    int as = a.size(), bs = b.size(), cs, d = as - bs;
    for( int i = 0; i < d - 1; i++ )
        c += "0";
    cs = c.size();

    while( c != b )
    {
        while( as > cs || as == cs && a >= c )
        {
            a = calcSubtraction( a, c );
            as = a.size();
        }
        c = c.substr( 0, c.size() - 1 );
        cs = c.size();
    }

    while( as > bs || as == bs && a >= b )
    {
        a = calcSubtraction( a, b );
        as = a.size();
    }

    cout << a << endl;


    return 0;
}




Measured memory_bytes: 3204
# coding: utf-8
import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

A,B,C,D=map(int,input().split())
BA=B-A
CD=lcm(C,D)
AC=A%C
AD=A%D
ACD=A%CD
ans=BA+1

ans-=max((BA-(C-AC)%C)//C,0)
ans-=max((BA-(D-AD)%D)//D,0)
ans+=max((BA-(CD-ACD)%CD)//CD,0)


if (BA-(C-AC)%C)>=0:
    ans-=1

if (BA-(D-AD)%D)>=0:
    ans-=1

if (BA-(CD-ACD)%CD)>=0:
    ans+=1

print(ans)

Measured memory_bytes: 72728
#pragma comment(linker, "/STACK:33554432")
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <unordered_map>
#include <iterator>
#include <stack>
#include <unordered_set>
#include <iomanip>
#include <ctime>
#include <cstring>
#include <bitset>
#include <math.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using ld = long double;
using pll = pair<long long, long long>;

const int MAXH = 2e4 + 20;
const int MAXN = 1e3 + 20;

ll dp[MAXN][MAXH];

void solve() {

    ll h, n;
    cin >> h >> n;

    vector<pair<ll, ll>> scls;
    scls.push_back({-1, 0});

    for (int i = 0; i < n; ++i) {
        ll a, b;
        cin >> a >> b;

        scls.push_back({a, b});
    }


    for (auto &i : dp) {
        for (long long &j : i)
            j = 1e18;
    }

    dp[0][0] = 0;

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < MAXH; ++j) {
            dp[i][j] = dp[i - 1][j];
        }
        for (int j = 0; j + scls[i].first < MAXH; ++j) {
            dp[i][j + scls[i].first] = min(dp[i][j + scls[i].first], dp[i][j] + scls[i].second);
        }
    }


    ll answr = 1e18;

    for (int j = h; j < MAXH; ++j) {
        answr = min(answr, dp[n][j]);
    }

    cout << answr;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cout << fixed << setprecision(20);

    solve();
}

Measured memory_bytes: 159872