akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

int n;
int v[101];

int main()
{
    int cnt = 0;
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> v[i];

    for(int i = 2; i <= n; i ++)
    {
        if(v[i] == v[i - 1])
        {
            cnt ++;
            if(i == n)
                v[i] += (v[i] == n ? -1 : 1);

            else
            {
                int a = min(v[i - 1], v[i + 1]);
                int b = max(v[i - 1], v[i + 1]);

                if(a == b)
                    v[i] += (v[i] == n ? -1 : 1);

                else
                    if(a < b - 1)
                        v[i] = a + 1;

                else
                    v[i] = (a == 1 ? 3 : 1);
            }
        }
    }

    cout << cnt << "\n";

    return 0;
}


Measured memory_bytes: 256
def getsub(arr):
    minv = arr[0]
    maxdist = arr[1] - minv

    for v in arr[1:]:
        # update maxdist
        maxdist = max(maxdist, v- minv)

        # update minv
        minv = min(minv, v)

    return maxdist

def main():
    # get input
    N = int(input())
    arr = [int(input()) for i in range(N)]

    # get sub
    print(getsub(arr))

if __name__ == '__main__':
    main()

Measured memory_bytes: 17180
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int n,q;

int main(){
//	freopen("a.txt","r",stdin);
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
//	sort(a,a+n);
	cin>>q;
	int res=0,number;
	for(int i=0;i<q;i++){
		cin>>number;
		int jb=lower_bound(a,a+n,number)-a;
		if(jb<n&&a[jb]==number)res++;
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 3380
#include<cstdio>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>
 
 
using namespace std;
#define int long long int
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back


struct Napsack_multiok{
    int C;
    int N;
    pair<int,int> *prods;
    int *dp;
    int prod_count; 
    Napsack_multiok(int c,int n){
      	C=c;N=n;
        prods = new pair<int,int>[N];
        prod_count=0;
        dp = new int[(C+2)*(N+2)];
      	initdp();
    }
    int mkitr(int x,int y){
        return x*(C+1)+y;
    }
    void initdp(){
        rep(i,N+1){
            rep(j,C+1){
                dp[mkitr(i,j)]=0;
            }
        }
    }
    void push_prods(int c,int p){
        prods[prod_count++]=mp(c,p);
    }
    int solve(){
        initdp();
        rep(i,N+1){
            if(i>0)rep(j,C+1){
                dp[mkitr(i,j)]=dp[mkitr(i-1,j)];
                if(j>0)dp[mkitr(i,j)]=max(dp[mkitr(i,j)],dp[mkitr(i,j-1)]);
                int p=prods[i-1].second;int c=prods[i-1].first;
                if(j-c>=0)dp[mkitr(i,j)]=max(dp[mkitr(i,j)],dp[mkitr(i,j-c)]+p);
            }
        }
        return dp[mkitr(N,C)];
    }
    void debug_printdp(){
        rep(i,N+1){
            rep(j,C+1){printf("%lld ",dp[mkitr(i,j)]);}
            printf("\n");
        }
    }
    void free_(){
        delete[] prods;
        delete[] dp;
    }
    
};

int N_input;
int ga,sa,ba,gb,sb,bb;
int ans=0;
signed main(){
    scanf("%lld",&N_input);
    scanf("%lld %lld %lld",&ga,&sa,&ba);
    scanf("%lld %lld %lld",&gb,&sb,&bb);
    Napsack_multiok AC(N_input,3);
    AC.push_prods(ga,gb-ga);AC.push_prods(sa,sb-sa);AC.push_prods(ba,bb-ba);
    int M=AC.solve()+N_input;
    AC.free_();
    Napsack_multiok BD(M,3);
    BD.push_prods(gb,ga-gb);BD.push_prods(sb,sa-sb);BD.push_prods(bb,ba-bb);
  	ans=BD.solve()+M;
    printf("%lld\n",ans);
    BD.free_();
}


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

#define ll long long
#define f(i, a, b) for(ll i=a;i<b;i++)
#define fi(i, a, b) for(ll i=b-1;i>=a;i--)
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define ml map<ll,ll>
#define pll pair<ll,ll>
map<ll,ll>mp;
void primeFactors(ll n){
    while (n % 2 == 0)
    {
      mp[2]++;
        n = n/2;
    }
    for (int i = 3; i <= sqrt(n); i = i + 2)
    {
        while (n % i == 0)
        {
            mp[i]++;
            n = n/i;
        }
    }
    if (n > 2)
        mp[n]++;
}

int main(){

  ll res=0;
  ll n;
   cin>>n;
    primeFactors(n);
    for(auto k : mp){
           int curr=0;
      // cout<<k.first<<" "<<k.second<<"\n";
         for(int i=1;i<=k.second;i++){

           if( ((i)*(i+1))/2<=k.second){
           curr=i;
           //cout<<i<<" ";
         }
           else
           break;
         }
         res+=curr;
      }
    cout<<res;
   }


Measured memory_bytes: 3704
from collections import deque

def T2F1(org_S,rev_S, C, jdg):
    if jdg%2 == 0:
        org_S.appendleft(C)
        rev_S.append(C)
        return org_S, rev_S
    else:
        org_S.append(C)
        rev_S.appendleft(C)
        return org_S, rev_S
def T2F2(org_S, rev_S, C,jdg):
    if jdg%2 == 0:
        org_S.append(C)
        rev_S.appendleft(C)
        return org_S, rev_S
    else:
        org_S.appendleft(C)
        rev_S.append(C)
        return org_S, rev_S
    
org_S = deque(list(input()))
rev_S = deque(list(reversed(org_S)))
Q = int(input())
jdg = 0

for i in range(Q):
    A = list(input().split())
    if A[0] == "1":
        jdg += 1
    elif A[1] == "1":
        T2F1(org_S, rev_S, A[2],jdg)
    else:
        T2F2(org_S, rev_S, A[2],jdg)
        
if jdg%2 ==0:
    org_S = "".join(org_S)
    print(org_S)
    
else:
    rev_S = "".join(rev_S)
    print(rev_S)

Measured memory_bytes: 82664
import java.util.Scanner;

public class Main {
	void run() {
		Scanner sc = new Scanner(System.in);

		String tab = "";

		while (true) {
			int o = sc.nextInt();
			if (o == 0)
				break;
			int k10  = sc.nextInt();
			int k50  = sc.nextInt();
			int k100 = sc.nextInt();
			int k500 = sc.nextInt();

			int o10, o50, o100, o500;
			o10 = o50 = o100 = o500 = 1 << 20;
			for (int p10 = 0; p10 <= k10; p10++) {
				for (int p50 = 0; p50 <= k50; p50++) {
					for (int p100 = 0; p100 <= k100; p100++) {
						for (int p500 = 0; p500 <= k500; p500++) {
							int pay = 10*p10 + 50*p50 + 100*p100 + 500*p500;
							if (pay < o) continue;

							int change = pay - o;
							int c500 = change / 500;
							change %= 500;
							int c100 = change / 100;
							change %= 100;
							int c50 = change / 50;
							change %= 50;
							int c10 = change / 10;

							int r10 = k10 - p10 + c10;
							int r50 = k50 - p50 + c50;
							int r100 = k100 - p100 + c100;
							int r500 = k500 - p500 + c500;
							if (r10+r50+r100+r500 < o10+o50+o100+o500) {
								o10 = r10;
								o50 = r50;
								o100 = r100;
								o500 = r500;
							}
						}
					}
				}
			}

			System.out.print(tab);
			tab = "" + '\n';
			if (o10 < k10)
				System.out.println(10 + " " + (k10 - o10));
			if (o50 < k50)
				System.out.println(50 + " " + (k50 - o50));
			if (o100 < k100)
				System.out.println(100 + " " + (k100 - o100));
			if (o500 < k500)
				System.out.println(500 + " " + (k500 - o500));
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

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

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	string ans;
	if (c <= a + b) {
		ans = "Yes";
	} else {
		ans = "No";
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  int sum = 0;
  REP(i,n){
    int l,r;
    cin >> l >> r;
    sum += r-l+1;
  }
  cout << sum << endl;
  return 0;
}


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

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> arr(N);
    for(int i = 0; i < N; i++)
        cin >> arr[i];

    int sum0 = 0;
    int sum1 = 0;
    for(int i = 0; i < N; i++)
        sum1 += arr[i];

    int mini = sum1;
    for(int i = 0; i < N; i++) {
        sum0 += arr[i];
        sum1 -= arr[i];
        mini = min(abs(sum1-sum0), mini);
    }

    cout << mini << endl;
    return 0;
}


Measured memory_bytes: 256
<?php
// Your code here!
$a = fgets(STDIN);
$b = fgets(STDIN);
$c = fgets(STDIN);
$t = fgets(STDIN);

$ans = 0;
for($i=0; $i<=$a; ++$i){
    for($j=0; $j<=$b; ++$j){
        for($k=0; $k<=$c; ++$k){
            if( (500*$i) + (100*$j) + (50*$k) == $t){
                $ans++;
            }       
        }
    }
}
echo $ans;
?>

Measured memory_bytes: 3700
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		new Main().run();
	}

	private void run() throws IOException {
		Scanner scanner = new Scanner(System.in);
		while (true) {
			n = scanner.nextInt();
			u = scanner.nextInt();
			if ((n | u) == 0)
				break;
			need = new int[n];
			int all = 0;
			unit = new int[n];
			for (int i = 0; i < n; i++) {
				unit[i] = scanner.nextInt();
				all += unit[i];
				int k = scanner.nextInt();
				for (int j = 0; j < k; j++) {
					int x = scanner.nextInt();
					need[i] |= (1 << x);
				}
			}
			if (all == u) {
				System.out.println(n);
				continue;
			}
			ans = n;
			v = new boolean[1 << n];
			slove(0, 0, 0);
			System.out.println(ans);
		}
	}

	private void slove(int bit, int one, int have) {
		if (ans == one)
			return;
		if (have >= u) {
			ans = one;
			return;
		}

		for (int i = 0; i < n; i++) {
			int a = bit | (1 << i);
			if (v[a] || (bit | need[i]) != bit)
				continue;
			v[a] = true;
			slove(a, one + 1, have + unit[i]);
		}
	}

	int n, u;
	int[] need, unit;
	int ans;
	boolean[] v;
}

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

int main(){
    int N;
    cin >> N;
    int W[N];
    rep(i, N){
        cin >> W[i];
    }
    int s[N+1] = {};
    for(int i=1;i<N+1;i++){
        s[i] = s[i-1]+W[i-1]; 
    }
    int a = 0, b = 0;
    int MIN = 10000000;
    rep(t, N){
        a = s[t+1];
        b = s[N] - a;
        int dif = abs(a-b);
        MIN = min(MIN, dif);
    }
    printf("%d\n", MIN);
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N=1000010,Mo=1000000007;
int fac[N],rev[N],d[N];
inline int Pow(int x,int y) {
    int ret=1;
    while(y) {
	if(y&1) ret=1LL*ret*x%Mo;
	x=1LL*x*x%Mo,y>>=1;
    }
    return ret;
}
inline int C(int n,int m) {
    if(n<m) return 0;
    return 1LL*fac[n]*rev[m]%Mo*rev[n-m]%Mo;
}
int main() {
    int n,m,k,s,L=0,R=0,t=1,ans=0;
    cin>>n>>m>>k,s=n+m+k;
    for(int i=fac[0]=1;i<=s;i++) fac[i]=1LL*fac[i-1]*i%Mo;
    rev[s]=Pow(fac[s],Mo-2);
    for(int i=s;i;i--) rev[i-1]=1LL*rev[i]*i%Mo;
    for(int i=d[0]=1;i<=s;i++) d[i]=3LL*d[i-1]%Mo;
    ans=d[m+k];
    for(int i=1;i<=m+k;i++) {
	t=(2LL*t+C(i-1,++R)+C(i-1,L-1))%Mo;
	int l=max(0,i-k),r=min(i,m);
	if(L<l) t=(t-C(i,L++))%Mo;
	if(r<R) t=(t-C(i,R--))%Mo;
	ans=(ans+1LL*C(n+i-1,n-1)*t%Mo*d[m+k-i])%Mo;
    }
    cout<<(ans+Mo)%Mo;
    return 0;
}

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

#define pb push_back
#define pf push_front
#define pp pop_back
#define sz(a) (int)(a.size())
#define mp make_pair
#define F first
#define S second
#define next _next
#define prev _prev
#define left _left
#define right _right
#define y1 _y1
#define all(x) x.begin(), x.end()
#define what_is(x) #x << " is " << (x)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = (int)1e6 + 123;
const ll INF = (ll)1e18 + 123;
const int inf = (int)1e9 + 123;
const int MOD = (int)1e9 + 7;

void megaRandom() {
	unsigned int FOR;
 	asm("rdtsc" : "=A"(FOR));
  srand(FOR);
}

int n, m;
char ch[10][10];

void no() {
	cout << "Impossible";
	exit(0);
}

bool u[10][10];

int main() {
	megaRandom();
	cin >> n >> m;
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++)
			cin >> ch[i][j];
	int x = 1, y = 1;
	while(x != n || y != m) {
		u[x][y] = 1;
		bool ok1 = 0, ok2 = 0;
		if(x + 1 <= n && ch[x + 1][y] == '#')
			ok1 = 1;
		if(y + 1 <= m && ch[x][y + 1] == '#')
			ok2 = 1;
		if(ok1 + ok2 != 1)	
			no();
		if(ok1) x++;
		else    y ++;
	}
	u[x][y] = 1;
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++)
			if(!u[i][j] && ch[i][j] == '#')
				no();
	cout << "Possible";
	return 0;  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;;
#define ll long long
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define INF 1<<30
#define LINF 1LL<<62
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
const int MOD = 1000000007;
 
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;


ll d[105];
ll dp[105][100];
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n; cin >> n;
  FOR(i,1,n+1){
          ll tmp = i;
      FOR(j,2,i+1){
          while(tmp%j==0){
              d[j]++;
              tmp/=j;
              if(tmp==1)break;
          }
      }
  }
  dp[0][1] = 1;
  FOR(i,1,n+1){
      FOR(j,1,76){
          REP(k,d[i]+1){
              if(j*(k+1)<76){
                  dp[i][j*(k+1)] += dp[i-1][j];
              }
          }
      }
  }
  ll ans = dp[n][75];
  
  cout << ans << endl;
  
}

Measured memory_bytes: 384
//08
#include<iostream>

using namespace std;

int main(){
  static long long e[1000001]={0,2};
  for(int i=2;i<=1000000;i++){
    e[i]=i;
  }
  for(int i=2;i<=1000000;i++){
    if(e[i]==i){
      for(int j=i;j<=1000000;j+=i){
	e[j]=e[j]/i*(i-1);
      }
    }
  }
  static long long a[1000001];
  for(int i=1;i<=1000000;i++){
    a[i]=a[i-1]+e[i];
  }
  int t;
  cin>>t;
  while(t--){
    int n;
    cin>>n;
    cout<<a[n]<<endl;
  }
  return 0;
}

Measured memory_bytes: 16780
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

using namespace std;

typedef pair<long long int, long long int> P;
long long int INF = 1e18;
long long int MOD = 1000000007;

int const TREE_SIZE = 1 << 20;
long long int seg_tree[TREE_SIZE] = {};

void change(int a, long long int w){
	
	a += TREE_SIZE / 2;
	
	seg_tree[a] += w;
	
	for(int x = a / 2; x > 0; x /= 2){
		seg_tree[x] = seg_tree[2 * x] + seg_tree[2 * x + 1];
	}
}

long long int query(int a, int b, int index, int l, int r){
	
	// 外からは query(a, b, 1, 0, TREE_SIZE / 2) のように呼ぶ
	
	if(r <= a || b <= l){
		return 0;
	}
	if(a <= l && r <= b){
		return seg_tree[index];
	}
	
	return query(a, b, index * 2, l, (l + r) / 2) + query(a, b, index * 2 + 1, (l + r) / 2, r);
}

#define MAX_V 110000

vector<int> E[MAX_V];
int child_num[MAX_V];
int p_num[MAX_V];

int func(int p, int id){
	p_num[p] = id;
	int S = 1;
	for(int i = 0; i < E[p].size(); i++){
		S += func(E[p][i], id + S);
	}
	return child_num[p] = S;
}

int main(){
	
	int V, Q;
	cin >> V;
	
	for(int i = 0; i < V; i++){
		int num;
		cin >> num;
		for(int j = 0; j < num; j++){
			int v;
			cin >> v;
			E[i].push_back(v);
		}
	}
	
	func(0, 0);
	
	cin >> Q;
	
	for(int i = 0; i < Q; i++){
		long long int num, v, w;
		cin >> num;
		if(num == 0){
			cin >> v >> w;
			change(p_num[v], w);
			change(p_num[v] + child_num[v], -w);
		}else{
			cin >> v;
			cout << query(0, p_num[v] + 1, 1, 0, TREE_SIZE / 2) << endl;
		}
	}
	
	return 0;
}



Measured memory_bytes: 15860
from collections import defaultdict


def is_prime(n: int)-> bool:
    if n == 2:
        return True
    if n < 2 or n % 2 == 0:
        return False
    # when n is a prime number
    # x^(n-1) ≡ 1 (mod n)
    return pow(2, (n-1), n) == 1


def prime_factorize(n: int):
    prime_factors = []
    range_max = int(n //2) + 1

    for i in range(2, range_max):
        if not is_prime(i):
            continue
        while True:
            div, mod = divmod(n, i)
            if mod == 0:
                prime_factors.append(i)
                n = div
            else:
                break
        if n == 1:
            break
    prime_factors.append(n)
    return prime_factors


prime_factors_dict = {0: {}}

def main():
    n = int(input())

    for i in range(1,n+1):
        prime_factors = prime_factorize(i)
        this_prime_factors = defaultdict(int)
        for pm in prime_factors:
            this_prime_factors[pm] += 1

        for k, v in prime_factors_dict[i-1].items():
            this_prime_factors[k] += v
        prime_factors_dict[i] = this_prime_factors

    this_prime_factors = prime_factors_dict[n]

    prime_factors_list = sorted(list(filter(lambda x:x[0] != 1, this_prime_factors.items())))

    cnt_mt_74times = len(list(filter(lambda x: x[1] >= 74, prime_factors_list)))
    cnt_mt_24times = len(list(filter(lambda x: x[1] >= 24, prime_factors_list)))
    cnt_mt_14times = len(list(filter(lambda x: x[1] >= 14, prime_factors_list)))
    cnt_mt_4times  = len(list(filter(lambda x: x[1] >= 4, prime_factors_list)))
    cnt_mt_2times  = len(list(filter(lambda x: x[1] >= 2, prime_factors_list)))

    ans_cnt = 0

    # q^74
    ans_cnt += cnt_mt_74times

    # q^24 * p^2
    ans_cnt += cnt_mt_24times * (cnt_mt_2times - 1)

    # q^14 * p^4
    ans_cnt += cnt_mt_14times * (cnt_mt_4times - 1)

    # q^4 * p^4 * r^2
    ans_cnt += cnt_mt_4times * (cnt_mt_4times - 1) // 2 * (cnt_mt_2times - 2)

    print(ans_cnt)

    return



main()

Measured memory_bytes: 3444
#include <iostream>
//#include <iomanip>
#include <string>
//#include <vector>
//#include <algorithm>
//#include <utility>
//#include <set>
//#include <map>
//#include <queue>
//#include <deque>
//#include <bitset>
//#include <math.h>
using namespace std ;
using ll = long long ;
//using ld = long double ;
//using vll = vector<ll> ;
//using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
//using pll = pair<ll,ll> ;
//#define all(v) v.begin(),v.end()
//ll mod = 1000000007 ;
//long double pie = acos(-1) ;
//ll INF = 1000000000000 ;

//void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
//ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
//ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void fix_cout(){cout << fixed << setprecision(20) ;}

int main(){
	ll k ; cin >> k ;
	string s ; cin >> s ;
	if(s.size()<=k) cout << s << endl ;
	else{
		for(int i=0;i<k;i++) cout << s.at(i) ;
		cout << "...\n" ;
	}
}


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

#define en "\n"
#define INF (int) 9e18
#define HELL (int) (1e9 + 7)
#define int long long
#define double long double
#define uint unsigned long long
#define pii pair<int, int>
#define pb push_back
#define fs first
#define sc second
#define size(a) (int) a.size()
#define deb(x) cerr << #x << " => " << x << en
#define deba(x) cerr << #x << en; for (auto a : x) cerr << a << " "; cerr << en;
#define debp(x) cerr << #x << en; for (auto a : x)cerr<<"("<<a.fs<<", "<<a.sc<<") "; cerr << en;
#define debm(x) cerr << #x << en; for (auto a : x){for(auto b : a) cerr << b << " "; cerr << en;}
#define getMat(x, n, m, val) vector<vector<int>> x(n, vector<int> (m, val))
#define fastio ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define pout cout << fixed << setprecision(10)
int fastpow(int a, int b, int m = HELL) { int res = 1; a %= m;
while (b > 0) { if (b & 1) res = (res * a) % m; a = (a * a) % m; b >>= 1; } return res;}
#define inv(a) fastpow(a, HELL - 2)

int32_t main() { fastio;
	int n; cin >> n;
	set<string> S;
	for (int i = 0; i < n; i++) {
		string x; cin >> x;
		S.insert(x);
	}
	cout << size(S) << endl;
	return 0;
}


Measured memory_bytes: 19284
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 200005
int N,M;
int A[NUM],B[NUM];

int main(){

	scanf("%d %d",&N,&M);

	for(int i = 0; i < N; i++){

		scanf("%d",&A[i]);
	}

	for(int i = 0; i < M; i++){

		scanf("%d",&B[i]);
	}

	int index = 0;

	//and検索
	queue<int> AND;

	for(int i = 0; i < N; i++){
		while(index < M && B[index] < A[i])index++;
		if(index == M)break;
		if(B[index] == A[i]){
			AND.push(A[i]);
			index++;
		}
	}

	//or検索
	vector<int> OR;

	for(int i = 0; i < N; i++){
		OR.push_back(A[i]);
	}

	index = 0;
	for(int i = 0; i < M; i++){
		while(index < N && A[index] < B[i])index++;
		if(index == N){
			for(int k = i; k < M; k++){
				OR.push_back(B[k]);
			}
			break;
		}
		if(A[index] == B[i])continue;
		else{
			OR.push_back(B[i]);
		}
	}

	sort(OR.begin(),OR.end());

	printf("%lld %lld\n",AND.size(),OR.size());

	while(!AND.empty()){

		printf("%d\n",AND.front());
		AND.pop();
	}

	for(int i = 0; i < OR.size(); i++){

		printf("%d\n",OR[i]);
	}

	return 0;
}



Measured memory_bytes: 4968
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder {
    class MainClass {
        public static void Main(string[] args) {

            int NUM = 500;

            var input = Console.ReadLine().Split(' ');

            var k = int.Parse(input[0]);
            var x = int.Parse(input[1]);

            if(NUM * k >= x) {

                Console.WriteLine("Yes");

            } else {

                Console.WriteLine("No");

            }

        }

        
    }
}

Measured memory_bytes: 27468
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
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 int INF=1001001001;
vector<pair<int64_t,int64_t>>prime_factorize(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p; 
}

int main() {
  int sx,sy,tx,ty;
  cin>>sx>>sy>>tx>>ty;
  int dx=abs(sx-tx);
  int dy=abs(sy-ty);
  cout<<string(dx,'R')<<string(dy,'U');
  cout<<string(dx,'L')<<string(dy,'D');
  cout<<'L'<<string(dy+1,'U')<<string(dx+1,'R')<<'D';
  cout<<'R'<<string(dy+1,'D')<<string(dx+1,'L')<<'U';
  cout<<endl;
  return 0;
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
#define int long long
#define double long double
#define INF 1e18
#define MOD 1000000007
using namespace std;
signed main() {
  int N;
  while(cin>>N,N){
  vector<int> a(N);
  int avg = 0;
  for (int i=0;i<N;i++) {
    cin>>a[i];
    avg+=a[i];
  }
  avg/=N;
  int ans=0;
  for (int i=0;i<N;i++) {
    if(a[i]<=avg)ans++;
  }
  cout<<ans<<endl;
  }
}



Measured memory_bytes: 3160
#include<stdio.h>
#include<iostream>
#include<string>
using namespace std;

int main() {
	/*
	int a = 0;//整数変数aを作る
	int b = 0;//整数変数bを作る

	cin >> a >> b;//2つの数字を受け取り、a,bに代入

	cout << a * b << endl;//a*bを出力
	*/

	string S;
	cin >> S;
	if (S[0]=='7'||S[1]=='7'||S[2]=='7') {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}





	return 0;


}

Measured memory_bytes: 3608
def c_christmas_eve(N, K, H):
    H.sort()
    ans = float('inf')
    for j in range(N - K + 1):
        h_max = H[j + K - 1]
        h_min = H[j]
        ans = min(ans, h_max - h_min)
    return ans

N, K = [int(i) for i in input().split()]
H = [int(input()) for _ in range(N)]
print(c_christmas_eve(N, K, H))

Measured memory_bytes: 7488
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"
#include "chrono"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-12;

//int N, M, K, T, H, W, L, R;
long long int N, M, K, T, H, W, L, R;

class Add_Segment_Tree {
	vector<long long int>v;
	long long int ret;
	int num;
	long long int Update(int place) {
		if (place >= v.size() / 2) {
			return v[place];
		}
		v[place] = Update(place * 2) + Update(place * 2 + 1);
		return v[place];
	}
public:
	Add_Segment_Tree(int n) {
		n++;
		num = 1;
		while (num < n * 2)num *= 2;
		v.resize(num, 0);
	}
	void Add(int place, long long int num, bool update) {
		place += v.size() / 2;
		v[place] += num;
		if (!update)return;
		place /= 2;
		while (place) {
			v[place] = v[place * 2] + v[place * 2 + 1];
			place /= 2;
		}
	}
	void TopDown() {
		Update(1);
	}
	long long int Sum(int a, int b) {
		ret = 0;
		b++;
		for (a += num / 2, b += num / 2; a < b; a >>= 1, b >>= 1) {
			if (a & 1)ret += v[a++];
			if (b & 1)ret += v[--b];
		}
		return ret;
	}
};

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

	cin >> N >> K;
	Add_Segment_Tree asg(N);
	for (int i = 0; i < N; i++) {
		cin >> M;
		asg.Add(i, M, false);
	}
	asg.TopDown();
	while (K--) {
		cin >> M >> L >> R;
		if (M == 0) {
			asg.Add(L, R, true);
		}
		else {
			cout << asg.Sum(L, R - 1) << endl;
		}
	}
}

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

using namespace std;

#define ll long long

#define DEBUG (0)

int main()
{
  ll H = 0;
  cin >> H;

  ll num = 1;
  ll sum = 0;

  while(1){
    if(H == 1){
      sum += num;
      break;
    }else{
      H = H/2;
      sum += num;
      num = num*2;
    }
  }

  cout << sum << "\n";

}

Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <vector>
#include <cstring>
#include <cassert>
using namespace std;

int dp[111111];

int C[] = {2, 5, 5, 4, 5, 6, 3, 7, 6};
int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};

set<int> S;

int dfs(int r){
    if( r == 0 ) return 0;
    if( r < 0 ) return -1e9;
    if( dp[r] != -1 ) return dp[r];
    int ans = -1e9;
    for(int i = 0 ; i < 9 ; i++){
        if( S.count(A[i]) == 0 ) continue;
        int t = dfs(r - C[i]) + 1;
        if( t > ans ){
            ans = t;
        }
    }
    return dp[r] = ans;
}

int rec(int r){
    assert(r>=0);
    if(r == 0 ) return 0;
    int ans = dfs(r);
    for(int i = 8 ; i >= 0 ; i--){
        if( S.count(A[i])  == 0 ) continue;
        int t = dfs(r - C[i]) + 1;
        if( t == ans ){		
            cout << A[i];
            rec(r-C[i]);
            return 0;   
        }
    }
}

int main(){
    memset(dp, -1, sizeof(dp));
    int N;
    int K;
    cin >> N >> K;
    for(int i = 0 ; i < K ; i++){
        int x;
        cin >> x;
        S.insert(x);
    }
    rec(N);
    cout << endl;
   
}

Measured memory_bytes: 896
process.stdin.resume();
process.stdin.setEncoding('utf8');

var lines = [];
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
reader.on('line', (line) => {
  lines.push(line);
});
reader.on('close', () => {
  const ans = exec(lines);
  console.log(ans);
});

function exec(lines)
{
  const x = parseInt(lines[0]);
  return (x*x*x);
}


Measured memory_bytes: 16496
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,k;
	cin>>n>>k;
	vector<int>v(n);
	for(int i=0;i<n;i++){
		cin>>v[i];
	}	
	sort(v.begin(),v.end(),greater<int>());
	for(int i=0;i<min(n,k);i++){
		v[i]=0;
	}
	long long int ans=0;
	for(int i=0;i<n;i++){
		ans+=v[i];
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3988
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#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 <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;

string rev(string s) {
    cerr << s << endl;
    reverse(s.begin(), s.end());
    return s;
}

int main() {
    string s; cin >> s;
    int N = s.size();
    
    bool ok = true;
    ok &= (s == rev(s));
    ok &= (s.substr(0, N/2) == rev(s.substr(0, N/2)));
    ok &= (s.substr((N+1)/2, N/2) == rev(s.substr((N+1)/2, N/2)));
    cout << (ok ? "Yes" : "No") << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct MX{
	int r,c;
} mx[105];
long long dp[105][105];
int main()
{
	int n; cin>>n;
	for(int i=1;i<=n;i++){
		cin>>mx[i].r>>mx[i].c;
	}
	for(int i=i;i<=n;i++) dp[i][i] = 0;
	for(int k=1;k<n;k++){
		for(int i=1;i<=n-k;i++){
			int j = i+k;
			long long mini=1e19,t;
			for(int a=i;a<j;a++){
				t = dp[i][a]+dp[a+1][j]+mx[i].r*mx[a].c*mx[j].c;
				mini = min(mini,t);
			}
			dp[i][j] = mini;
		}
	}
	cout<<dp[1][n]<<endl;
	return 0;
}



Measured memory_bytes: 3160
#include<stdio.h>
//#include<stdlib.h>
//#include<string.h>
 
int main()
{
  int i=0;
  int stack[100];
  char s[100];
  
  while(scanf("%s", s) != EOF){
    if(s[0] == '+'){
      stack[i-2] += stack[i-1];
      i--;
    }
	else if(s[0] == '-'){
      stack[i-2] -= stack[i-1];
      i--;
    }
	else if(s[0] == '*'){
      stack[i-2] *= stack[i-1];
      i--;
    }
	else{
      stack[i++] = atoi(s);
    }
  }

  printf("%d\n", stack[0]);
  return 0;
}

Measured memory_bytes: 548
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
#include <stdio.h>
#include <stack>
#include <queue>
#include <cstdio>
#include <cmath>

using namespace std;

#define Int int64_t

void printVec(std::vector<int>& vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
	vector.erase(vector.begin() + index);
}




int main() {
	int a, b, c,d;
	cin >> a >> b >> c;

	d = b / a;
	if (d >= c) cout << c << endl;
	else cout << d << endl;
	

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
int main() {
  int x,y,s,i,j,sum;
  while(1){
    int max=0;
    cin>>x;
    cin>>y;
    cin>>s;
    if (x==0) break;
    for (i=1;i<s;i++){
      for (j=1;j<=s-i;j++){
    if (i*(100+x)/100+j*(100+x)/100==s){
      sum=i*(100+y)/100+j*(100+y)/100;
      if (max<sum) max=sum;
    }
      }
    }
    cout<<max<<endl;
  }
}

Measured memory_bytes: 1160
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P>IP;
typedef vector<ll> V;
typedef vector<V> V2;
typedef vector<vector<P> > G;
void g_dir(G &graph, ll a, ll b, ll w = 1){graph[a].push_back(P(b, w));}
void g_undir(G &graph, ll a, ll b, ll w = 1){g_dir(graph, a, b, w);g_dir(graph, b, a, w);}
#define rep(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define rep1(i, n) for(ll (i) = 1; (i) <= (n); (i)++)
#define rrep(i, n) for(ll (i) = (n) - 1; (i) >= 0; (i)--)
#define rrep1(i, n) for(ll (i) = (n); (i) >= 1; (i)--)
template<class T> void chmax(T &a, const T &b){if(a < b){a = b;}}
template<class T> void chmin(T &a, const T &b){if(a > b){a = b;}}
const ll INF = 1145141919;
const ll MOD = 1000000007;
const ll NUM = 101010;

ll N, M;
V v;

ll check(ll x){
    ll sum = 0;
    rep(i, N){
        if(v[i] + v[0] < x)continue;
        ll ok = 0, ng = N;
        while(ok + 1 < ng){
            ll mid = (ok + ng) / 2;
            if(v[i] + v[mid] >= x)ok = mid;
            else ng = mid;
        }
        sum += ng;
    }
    return sum;
}

ll solve(ll x){
    V t(N);
    rep(i, N){
        if(i == 0)t[i] = v[i];
        else t[i] = t[i - 1] + v[i];
    }
    ll sum = 0;
    rep(i, N){
        if(v[i] + v[0] < x)continue;
        ll ok = 0, ng = N;
        while(ok + 1 < ng){
            ll mid = (ok + ng) / 2;
            if(v[i] + v[mid] >= x)ok = mid;
            else ng = mid;
        }
        sum += v[i] * ng + t[ok];
    }
    return sum;
}

int main(){

    cin >> N >> M;
    v = V(N);
    rep(i, N)cin >> v[i];
    sort(v.begin(), v.end(), greater<ll>());
    ll ng = 0, ok = INF;
    while(ng + 1 < ok){
        ll mid = (ng + ok) / 2;
        if(check(mid) <= M)ok = mid;
        else ng = mid;
    }
    // cout << ok << ", " << check(ok)<< endl;

    cout << solve(ok) + (M - check(ok)) * (ok - 1)<< endl;
    return 0;
}

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

int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  vector<int> s(n + 1);
  int mx = 0;
  for (int i = 1; i <= n; i++) {
    int a;
    scanf("%d", &a);
    s[i] = s[i - 1] + a;
    
    if (i >= k && s[i] - s[i - k] > mx)
      mx = s[i] - s[i - k];
  }

  printf("%lf\n", 1.0 * (mx + k) / 2);

  return 0;
}

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

int main() {
  char c;
  cin >> c;
  if (c=='A') {
    cout << 'T';
  } else if (c=='T') {
    cout << 'A';
  } else if (c=='G') {
    cout << 'C';
  } else if (c=='C') {
    cout << 'G';
  }
  return 0;
}

Measured memory_bytes: 256
from collections import defaultdict
N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

hold = defaultdict(list)
like = [0] * N
sport = 0
NG = [False] * (M + 1)
ans = []

while all(like[i] < M for i in range(N)):
    hold = defaultdict(list)
    for i in range(N):
        hold[A[i][like[i]]].append(i)

    res = -1
    for k, v in hold.items():
        if len(v) > res:
            res = len(v)
            sport = k
    NG[sport] = True
    ans.append(res)

    for i in range(N):
        while like[i] < M:
            if NG[A[i][like[i]]]:
                like[i] += 1
            else:
                break

print(min(ans))

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

int main() {
    int a, b;
    cin >> a >> b;

    int ans = 0;
    for (int i = a; i <= b; i++) {
        string s = to_string(i);
        if (s[0] == s[4] && s[1] == s[3]) ans++;
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
from collections import Counter

s = input()
t = input()

dict_st = {}
dict_ts = {}

for x, y in zip(s, t):
    if x not in dict_st:
        dict_st[x] = y
    else:
        if dict_st[x] != y:
            print("No")
            break
    
    if y not in dict_ts:
        dict_ts[y] = x
    else:
        if dict_ts[y] != x:
            print("No")
            break
else:
    print("Yes")


Measured memory_bytes: 4136
#include <bits/stdc++.h>
using intl = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for(intl i = 0; i < (intl)(n); i++)
#define repd(i, n) for(intl i = (intl)(n); i >= 0; i--)
#define repi(i, a, b) for(intl i = (intl)(a); i < (intl)(b); i++)
#define repid(i, a, b) for(intl i = (intl)(a); i >= (intl)(b); i--)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define all(x) (x).begin,(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,1,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define alength(a) (sizeof(a) / sizeof(a[0]))
#define cin(i, a) rep(i, alength(a))cin >> a[i]
#define ccin(i, j, a) rep(i, alength(a))rep(j, alength(a[i]))cin >> a[i][j]
#define debug(x) cout << #x << ":" << x << endl
#define rdebug(i,x) rep(i, alength(x))cout << #x << "[" << i << "]:" << x[i] << endl
#define sqrt sqrtl
#define int intl
#define itn intl
#define double ld
#define pb push_back
#define mp make_pair
const intl INF = 1e9;
const intl MOD = 1e9+7;
const ld eps = 1.0e-14;//-9
void fp(bool flag){
    if(flag)cout << "Yes" << endl;
    else cout << "No" << endl;
}
void fp(bool flag, string s, string t){
    if(flag)cout << s << endl;
    else cout << t << endl;
}
intl kai(intl k){
    intl a = 1;
    for(int i = 2; i <= k; i++){
        a *= i;
    }
    return a;
}
intl gcd(intl a, intl b){
    if(!b)return a;
    return gcd(b, a % b);
}
intl digit10(intl a){
    if(!a)return 1;
    intl b = 0;
    while(a){
        a /= 10;
        b++;
    }
    return b;
}
signed main(){
    cout << fixed << setprecision(10);
    intl n;
    cin >> n;
    string s[n];
    rep(i,n){
        string t = "";
        char c[10];
        rep(i,10){
            char a;
            cin >> a;
            c[i] = a;
        }
        sort(c, c + 10);
        rep(i, 10){
            t += c[i];
        }
        s[i] = t;
    }
    sort(s,s + n);
    intl cnt = 0;
    intl a = 1;
    rep(i,n - 1){
        if(s[i] == s[i + 1])a++;
        else {
            cnt += (a * (a - 1) / 2);
            a = 1;
        }
    }
    cnt += a * (a - 1) / 2;
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 7296
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
#define rep(i,m,n) for(int i=m;i<n;i++)
#define co(n) cout<<n<<endl
#define all(n) (n).begin(),(n).end()
#define pb(n,m) n.push_back(m)
#define pi(n,m) n.insert(n.begin(),m);
#define ee(n) n.erase(n.end()-1)
#define eb(n) n.erase(n.begin())
using namespace std;
//using bint=boost::multiprecision::cpp_int;
typedef long long ll;
typedef unsigned long long ull;

int main(){
  int a,b; cin>>a>>b;
  if(b==0){co(a); return 0;}
  vector<int> n(b);
  rep(i,0,b) cin>>n[i];
  sort(all(n));
  int ans=10000,c=0,d=0;
  while(1){
    if(binary_search(all(n),a+c)==false) break;
    else c++;
  }
  while(1){
    if(binary_search(all(n),a-d)==false) break;
    else d++;
  }
  if(c==d) co(a-d);
  else if(c>d) co(a-d);
  else co(a+c);
  
  return 0;
}

Measured memory_bytes: 3628
#include<iostream>
#include<stdio.h>
#include<string.h>
#define P 1000000007
using namespace std;
int n;
long long f[1200000],ans,sum;
long long power(long long x,int k){
	long long ans=1;
	while(k){
		if(k&1)(ans*=x)%=P;
		(x*=x)%=P;
		k>>=1;
	}
	return ans;
}
long long get(long long x){
	if(x>=3)return n-x+2;
	return n-x+1;
}
long long cal(long long x){
	if(x>=2)return (1LL*(n-1)*(n-1)%P+get(x))%P;
	return n;
}
int main(){
	scanf("%d",&n);
	f[0]=1;
	f[1]=1;
	if(n==1){
		printf("1\n");
		return 0;
	}
	ans+=cal(n)*f[0]+cal(n-1)*f[1];
	sum=2;
	ans%=P; 
	for(int i=2;i<n;i++){
		f[i]=(sum-f[i-2]+P)%P;
		ans+=f[i]*cal(n-i)%P;
		ans%=P;
		(sum+=f[i])%=P;
	}
	printf("%lld",ans);
}

Measured memory_bytes: 8448
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;

const int N=1000;
const int wal[][2]={{1,0},{-1,0},{0,1},{0,-1}};

int n,m,k,ans;
char ma[N+5][N+5];
bool vis[N+5][N+5];
struct node
{
	int x,y,p;
}t;

inline bool Pan(int x,int y)
{
	return (x>=1 && x<=n) && (y>=1 && y<=m);
}

queue<node> Q;
void Bfs(int bx,int by,int p)
{
	while(!Q.empty()) Q.pop();
	
	vis[bx][by] = 1;
	t.x=bx,t.y=by,t.p=ans;
	Q.push(t);
	
	while(!Q.empty())
	{
		node q=Q.front(); Q.pop();
		if(ma[q.x][q.y] - '0' == p+1)
		{
			ans = q.p;
			return ;
		}
		for(int i=0;i<4;i++)
		{
			int fx=q.x+wal[i][0],fy=q.y+wal[i][1];
			if(Pan(fx,fy) && !vis[fx][fy] && ma[fx][fy] != 'X')
			{
				vis[fx][fy] = 1;
				t.x=fx;t.y=fy;t.p=q.p+1;
				Q.push(t);
			}
		}
	}
}

int main()
{
	scanf("%d %d %d",&n,&m,&k);
	for(int i=1;i<=n;i++)
		scanf("%s",ma[i]+1);
	for(int p=0;p<k;p++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(ma[i][j] == ( !p ? 'S' : p+'0'))
				{
					memset(vis,0,sizeof(vis));
					Bfs(i,j,p);
					break;
				}
	printf("%d\n",ans);
	return 0;
}


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

int main() {
  string str;

  getline(cin, str);

  for(int i = 0; i < str.size(); i++) {
    if(str[i] == 'p' && str[i+1] == 'e' && str[i+2] == 'a' && str[i+3] == 'c' && str[i\
+4] == 'h') {
      cout << "apple";
      i+=4;
    }
    else if(str[i] == 'a' && str[i+1] == 'p' && str[i+2] == 'p' && str[i+3] == 'l' && \
str[i+4] == 'e') {
      cout << "peach";
      i+=4;
    }
    else cout << str[i];
  }
  cout << endl;

  return 0;
}



Measured memory_bytes: 3116
N = int( input() )
takoyaki_list = list( map( int, input().split() ) )
answer = 0
for i in takoyaki_list:
  for j in takoyaki_list:
    answer += int(i*j)
for k in range (len ( takoyaki_list ) ):
  answer -= takoyaki_list[k]**2
print( int( answer/2) )


Measured memory_bytes: 2940
dorm = [[[0 for i in range(10)] for j in range(3)] for k in range(4)]

inp_num = int(input())
for i in range(inp_num):
    building,floor,room,v = list(map(int, input().split()))
    dorm[building - 1][floor - 1][room - 1] += v

for i in range(4):
    for j in range(3):
        for k in range(10):
            print(f' {dorm[i][j][k]}', end='')
        print('')
    if i != 3:
        print('####################')


Measured memory_bytes: 5640
N, M = [int(x) for x in input().split()]
bridge = [[int(x) for x in input().split()] for x in range(M)]

par = [int(x) for x in range(N+1)]  # 所属グループ
gn = [1 for _ in range(N+1)]


def group(i):
    if par[i] == i:
        return i
    else:
        return group(par[i])


def group_num(i):               # order(NlogN)?
    counter = 0
    for j in range(N+1):
        if group(j) == i:
            counter += 1
    return counter


ans = [int(N*(N-1)/2)]

for i, b in enumerate(bridge[::-1]):  # O(M)
    g0 = group(b[0])
    g1 = group(b[1])
    # print(i)
    if g0 > g1:
        ans.append(int(ans[-1] - gn[g0]*gn[g1]))
        par[g0] = g1
        gn[g1] += gn[g0]
        gn[g0] = 0
        par[g0] = g1
    elif g0 < g1:
        ans.append(int(ans[-1] - gn[g0]*gn[g1]))
        par[g1] = g0
        gn[g0] += gn[g1]
        gn[g1] = 0
    else:
        ans.append(ans[-1])

# print(par)
# print([group(x) for x in par])
for x in ans[::-1][1:]:
    print(x)


Measured memory_bytes: 29364
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	int n, k; scanf("%d%d", &n, &k); std::vector<int> a(n);
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);	

	// pre
	std::vector<i64> b(n + 1, 0);
	for(auto & v: a) v = v % k + (k - 1);
	for(int i = 0; i < n; i++) b[i + 1] = (b[i] + a[i]) % k;

//	for(auto v: b) cout << v << " "; cout << endl;
	
	// solve
	i64 ans = 0;
	std::map<i64, i64> mp;
	for(int i = 0; i < n + 1; i++) {
		ans += mp[b[i]]++;
		
		if(i - k + 1 >= 0) mp[b[i - k + 1]]--;
	}

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


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

int main() {
    int r;
    cin >> r;
    if(r < 1200)cout << "ABC" << endl;
    else if(r < 2800)cout << "ARC" << endl;
    else cout << "AGC" << endl;
}


Measured memory_bytes: 256
A = int(input())
B = int(input())
C = int(input())
X = int(input())

answer = 0
for a in range(A+1):
    for b in range(B+1):
        for c in range(C+1):
            total = 500*a + 100*b + 50*c
            if total == X:
                answer += 1

print(answer)


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

typedef long long ll;
const ll N = 1e5;

int main()
{
    int n,t,a,b;

    cin>>n>>t;
    int m=N;
    for(int i=0; i<n; i++)
    {
        cin>>a>>b;
        if(b<=t) m= min(m,a);
    }

    if(m==N) cout<<"TLE"<<endl;
    else cout<<m<<endl;

    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MN 100005
using namespace std;
inline int in(){
    int x=0;bool f=0; char c;
    for (;(c=getchar())<'0'||c>'9';f=c=='-');
    for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');
    return f?-x:x;
}
struct edge{
	int to,nxt;
}e[MN<<1];
int h[MN],fa[MN],n,x,y,cnt;
bool col[MN];
inline void ins(int x,int y){
	e[++cnt].to=y;e[cnt].nxt=h[x];h[x]=cnt;
}
inline bool dfs(int u){
	for (int i=h[u];i;i=e[i].nxt){
		int v=e[i].to;
		if (fa[u]!=v) {fa[v]=u;if (!dfs(v)) return 0;}
	}if (!col[u])
	if (!fa[u]||col[fa[u]]) return 0;
	else col[fa[u]]=col[u]=1;return 1;
} 
int main()
{
	n=in();
	for (int i=1;i<n;++i){
		x=in();y=in();
		ins(x,y);ins(y,x);
	}fa[1]=0;printf(dfs(1)?"Second":"First");return 0;
}

Measured memory_bytes: 2560
import java.io.*;

public class Main {
	public static void main(String[] argv) throws NumberFormatException,
			IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		String[] lineArray;
		while ((line = br.readLine()) != null) {
			lineArray = line.split(" ");
			double[] f = new double[lineArray.length];
			for (int i = 0; i < lineArray.length; i++) {
				f[i] = (double) Integer.parseInt(lineArray[i]);
			}
			double x = (f[4] * f[2] - f[1] * f[5]) / (f[0] * f[4] - f[1] * f[3]);
			double y = (-f[2] * f[3] + f[0] * f[5]) / (f[0] * f[4] - f[1] * f[3]);
			if (x == -0.0) {
				x = 0.0;
			}
			if (y == -0.0) {
				y = 0.0;
			}
			System.out.print(String.format("%.3f %.3f\n", x, y));
		}
	}
}

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

int main(){
  int N, K;
  cin >> N >> K;
  vector<int> V(N);
  for(int i=0; i<N; i++){
    cin >> V[i];
  }
  int R= min(N, K);
  int ans =0;
  for(int i=0; i<=R; i++){
    for(int j=0; j<=R-i; j++){
      vector<int> C;
      for(int k=1; k<=i; k++){
        C.push_back(V[k-1]);
      }
      for(int k=1; k<=j; k++){
        C.push_back(V[N-k]);
      }
      sort(C.begin(),C.end());
      long tmp=0;
      int itr = min(i+j, K-i-j);
      for(int k=1; k<=itr; k++){
        if(C[k-1]<0) C[k-1]=0;
        else break;
      }
      for(int k=0; k<C.size(); k++){
        tmp+=C[k];
      }
      if(ans<tmp) ans=tmp;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
from collections import Counter
N=int(input())
A=list(map(int,input().split()))

cnt=Counter(A)
sum=0
for k,v in cnt.items():
    sum+=v*(v-1)//2

for i in range(N):
    num=cnt.get(A[i])
    if num==1:
        ans=sum
    elif num==2:
        ans=sum-1
    else:
        ans=sum-num*(num-1)//2+(num-1)*(num-2)//2

    print(ans)
    

Measured memory_bytes: 33948
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
int main(){
	int a,b,c;
	while(scanf("%d %d %d",&a,&b,&c)!=EOF){
		int ryu=a*365+(b-1)*31+c;
		if(ryu>=725993){
			printf("heisei %d %d %d",a-1988,b,c);
		}else if(ryu>=703356){
			printf("showa %d %d %d",a-1925,b,c);
		}else if(ryu>=698096){
			printf("taisho %d %d %d",a-1911,b,c);
		}else if(ryu>=682076){
			printf("meiji %d %d %d",a-1867,b,c);
		}else{
			printf("pre-meiji");
		}
		puts("");
	}
}

Measured memory_bytes: 1196
function parseInt(x) parse(Int, x) end

function main()
	n = parseInt(readline())
	a = parseInt.(split(readline()))
	b = [0 for i in 1:n]
	for i in 1:n
		b[i] = a[i] -i
	end
	m = median(b)
	sum = 0
	for i in 1:n
		sum += abs(b[i]-m)
	end
	println(convert(Int, sum))
end

main()

Measured memory_bytes: 153652