akhauriyash/Code-Regression huggingface dataset:
class SegmentTree():
    def __init__(self, values, merge_func=min, default=float("inf")):
        n = len(values)
        self.size = 1
        self.default = default
        self.merge = merge_func
        while self.size < n:
            self.size *= 2
        # tree[0] = empty
        # child of tree[n] = tree[n*2], tree[n*2+1]
        self.tree = [self.default] * self.size * 2
        for i in range(n):
            self.tree[self.size + i] = values[i]
        for i in range(self.size-1, 0, -1):
            self.tree[i] = self.merge(self.tree[i*2], self.tree[i*2+1])

    def update(self, index, value):
        index += self.size
        self.tree[index] = value
        while index > 1:
            index //= 2
            self.tree[index] = self.merge(
                self.tree[index*2], self.tree[index*2+1])

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.default
        if a <= l and r <= b:
            return self.tree[k]
        left = self.__query(a, b, k*2, l, (l+r)//2)
        right = self.__query(a, b, k*2+1, (l+r)//2, r)
        return self.merge(left, right)

    # query segmentation value of [a, b)
    def query(self, a, b):
        return self.__query(a, b, 1, 0, self.size)


def main():
    N = int(input())
    H = list(map(int, input().split()))
    A = list(map(int, input().split()))
    RMQ = SegmentTree([0] * N, merge_func=max, default=0)
    for i in range(N):
        maximum = RMQ.query(0, H[i]-1)
        RMQ.update(H[i]-1, maximum + A[i])
    print(RMQ.query(0, N))


if __name__ == "__main__":
    main()


Measured memory_bytes: 122108
#include <iostream>
#include <cstdio>
#define N 100005
using namespace std;

typedef long long ll;
ll n, m, mx, a[N], b[N];
bool v[N][35], k[35];
void f(ll p) {
	ll i, j, s = 0;
	for (i =0; i < n; i++) {
		for (j = 0; j < 35; j++) {
			if (j == p && v[i][j]) break;
			if (j < p && k[j] == 0 && v[i][j] == 1) break;
		}
		if (j == 35) s += b[i];
	}
	mx = max(mx, s);
}

int main()
{
	ll i, j, u;
	cin >> n >> m;
	for (i = 34; i >= 0; i--) {
		k[i] = m % 2;
		m /= 2;
	}
	for (i = 0; i < n; i++) {
		scanf ("%lld %lld", &a[i], &b[i]);
		u = a[i];
		for (j = 34; j >= 0; j--) {
			v[i][j] = u % 2;
			u /= 2;
		}
	}
	f(35);
	for (i = 0; i < 35; i++) {
		if (k[i]) f(i);
	}
	cout << mx << endl;
    return 0;
}


Measured memory_bytes: 5248
s=input()
arr=[]
for i in s:
    arr.append(i)
brr=[]
count=0
for i in arr:
    if(i=='S'):
        brr.append(count)
        count=0
    if(i=='R'):
        count=count+1 
brr.append(count)
print(max(brr))

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

int main() {
  int n; cin>>n;
  vector<int> a(n);
  int cnt=0;
  int mini=1e9+1;
  rep(i, n) {
    cin>>a[i];
    if (a[i]<0) cnt++;
    if (abs(a[i])<abs(mini)) mini=a[i];
  }
  ll ans=0;
  rep(i, n) ans+=abs(a[i]);
  if (cnt%2==1) ans-=2*abs(mini);
  cout<<ans<<endl;
}


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

int main() {
  int N;
  cin >> N;
  vector<vector<P>> G(N);
  rep(i,N-1) {
    int a, b; ll c;
    cin >> a >> b >> c;
    --a; --b;  // 0-indexed
    G[a].push_back(P(b,c));
    G[b].push_back(P(a,c));
  }
  
  int Q, K;
  cin >> Q >> K;
  --K;  // 0-indexed
  
  vector<ll> dist(N);  // distance from K
  queue<P> search;
  vector<bool> visited(N, false);
  dist[K] = 0;
  search.push(P(K,0));
  visited[K] = true;

  while(!search.empty()) {
    P v = search.front();
    search.pop();

    for (auto nv : G[v.first]) {
      if (visited[nv.first]) continue;  // obstruct backflow

      dist[nv.first] = dist[v.first] + nv.second;
      search.push(nv);
      visited[nv.first] = true;
    }
  }

  rep(i,Q) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    cout << dist[x] + dist[y] << endl;
  }
  return 0;
}


Measured memory_bytes: 10736
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <stack>
#include <queue>
#include <utility>
#define rep(i,l,n) for(lint i=l;i<n;i++)
#define rer(i,l,n) for(lint i=l;i<=n;i++)
#define rrep(i,n,l) for(int i=n-1;i>=l;i--)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef vector<int> vi;
typedef vector<lint> vli;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

int n;
int t[55];
bool dp[55][900][900];

int main(){
	cin>>n;
	int sum=0;
	rep(i,0,n){
		cin>>t[i];
		sum+=t[i];
	}
	memset(dp,false,sizeof(dp));
	dp[0][0][0]=true;
	rep(i,0,n){
		rep(j,0,900){
			rep(k,0,900){
				if(!dp[i][j][k]) continue;
				if(j+t[i]<900) dp[i+1][j+t[i]][k]=true;//?±±????????????
				if(k+t[i]<900) dp[i+1][j][k+t[i]]=true;//?±±????????????
				dp[i+1][j][k]=true;//?±±????????????
			}
		}
	}
	int MIN=1e8;
	rep(i,0,900){
		rep(j,0,900){
			if(dp[n][i][j]){
				int tmp=max(i,max(j,sum-i-j));
				MIN=min(MIN,tmp);
			}
		}
	}
	o(MIN);
}

Measured memory_bytes: 44676
s = int(input())

def f(n):
  if n%2==0:
    return int(n/2)
  else:
    return n*3 + 1

if s==1 or s==2 or s==4:
  print(4)
  exit()
for i in range(1000000):
  s = f(s)
  if s==4:
    print(i + 5)
    break

Measured memory_bytes: 38256
import java.util.*;
import java.lang.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        StringBuilder t = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (i % 2 == 0) {
                t.append(s.charAt(i));
            }
        }
        System.out.println(t);
    }
}


Measured memory_bytes: 26964
#include <stdio.h>
#include <string.h>

int main()
{
	int N;
	char s[128];
	scanf("%d", &N);
	scanf(" %s", s);
	int len = strlen(s);
	int r = 0, b = 0;
	for (int i = 0; i < len; i++) {
		if (s[i] == 'R') {
			r++;
		} else {
			b++;
		}
	}
	if (r > b) {
		printf("Yes\n");
	} else {
		printf("No\n");
	}
	return 0;
}


Measured memory_bytes: 128
from itertools import product

class BellmanFord:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        self.dist = [INF] * self.N # the distance of each vertex from s
        self.prev = [-1] * self.N # the previous vertex of each vertex on a shortest path from s
        self.dist[s] = 0
        for _ in range(self.N):
            updated = False
            for v in range(self.N):
                d = self.dist[v]
                if d != INF:
                    for u, c in self.E[v]:
                        temp = d + c
                        if self.dist[u] > temp:
                            updated = True
                            self.dist[u] = temp
                            self.prev[u] = v
            if not updated: break # the minimum costs are already stored in dist
        else: return None # the above loop is not broken if and only if there exists a negative cycle
        return self.dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

H, W = map(int, input().split())
bf = BellmanFord(H * W)

def vtx(i, j): return i*W + j
def coord(n): return divmod(n, W)

grid = [input() for _ in range(H)] # |string| = W
E = [[] for _ in range(H * W)]
ans = 0 if grid[0][0] == '.' else 1
for i, j in product(range(H), range(W)):
    v = vtx(i, j)
    check = [vtx(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for u in check:
        x, y = coord(u)
        if grid[i][j] == '.' and grid[x][y] == '#':
            bf.add_edge(v, u, 1)
        else:
            bf.add_edge(v, u, 0)
dist = bf.distance(0)
ans += dist[vtx(H-1, W-1)]
print(ans)

Measured memory_bytes: 7284
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
	int n;
	string s;
	char cs;
	int sum = 0;
	cin >> n >> s;
	cs = s[0];
	for (int i = 1; i < n; i++)
	{
		if (s[i] == cs)
		{

		}
		else
		{
			cs = s[i];
			sum++;
		}
	}
	cout << sum + 1 << endl;
}

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

#define MOD 1000000007

//べき乗を求める関数(繰り返し自乗法) O(logN)
int64_t power(int64_t x, int64_t n, int64_t mod){
    int64_t res = 1;
    if(n > 0){
        res = power(x, n/2, mod);
        if(n%2 == 0) res = (res * res) % mod;
        else res = (((res * res) % mod) * x) % mod;
    }
    return res;
}

int main(){
    int m, n;
    cin >> m >> n;
    cout << power(m, n, MOD) << endl;
    return 0;
}


Measured memory_bytes: 3100
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;

int main(){
  int n; cin >> n;
  vector<int> ar(n), cnt(1e6 + 200);
  for(int i = 0; i < n; i ++)
    cin >> ar[i], cnt[ar[i]] ++;
  sort(ar.begin(), ar.end());
  vector<bool> ban(1e6 + 200);
  int ans = 0;
  for(int i = 0; i < n; i ++){
    if(ban[ar[i]])
      continue;
    if(cnt[ar[i]] == 1)
      ans ++;
    for(int j = ar[i]; j < 1e6 + 200; j += ar[i]){
      ban[j] = 1;
    }
  }
  cout << ans;
}


Measured memory_bytes: 7960
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;

namespace AOJ
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }

        class node
        {
            public node left = null;
            public node right = null;
            public long value = -1;
            public node oya = null;
        }
        static void Main(string[] args)
        {
            var N = Sarray()[0];
            var nodes = new node[N];

            node root = null;
            Action<node> insert = null;
            insert = z =>
                  {
                      node y = null;
                      node x = root;
                      while (x != null)
                      {
                          y = x;
                          if (z.value < x.value)
                              x = x.left;
                          else
                              x = x.right;
                      }
                      if (y == null)
                          root = z;
                      else if (z.value < y.value)
                          y.left = z;
                      else
                          y.right = z;
                  };
            Action<long> find = null;
            find = v =>
              {
                  var x = root;
                  while (x != null)
                  {
                      if (x.value == v)
                      {
                          WriteLine("yes");
                          return;
                      }
                      if (x.value < v)
                          x = x.right;
                      else
                          x = x.left;
                  }
                  WriteLine("no");
              };
            Action<node> order = null;
            var preorder = new List<long>();
            var inorder = new List<long>();
            order = n =>
            {
                if (n == null)
                    return;
                preorder.Add(n.value);
                order(n.left);
                inorder.Add(n.value);
                order(n.right);
            };

            for (var i=0;i<N;++i)
            {
                var tmp = ReadLine().Split();
                if (tmp[0] == "insert")
                { insert(new node() { value = long.Parse(tmp[1]) }); }
                else if(tmp[0]=="find")
                { find(long.Parse(tmp[1])); }
                else
                {
                    preorder = new List<long>();
                    inorder = new List<long>();
                    order(root);
                    WriteLine(" " + string.Join(" ", inorder));
                    WriteLine(" " + string.Join(" ", preorder));
                }
            }
        }
    }
}


Measured memory_bytes: 73140
import java.util.*;

public class Main{
    public static void main(String[] argc){
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int X = sc.nextInt();
        int[] a = new int[N];
        for(int i=0;i<N;i++){
            a[i] = Math.abs(X - sc.nextInt());
        }
        if(N == 1){
            System.out.println(a[0]);
            return;
        }

        int ans = gcd(a[0], a[1]);
        for(int i=2;i<N;i++){
            ans = gcd(ans, a[i]);
        }

        System.out.println(ans);
    }

    public static int gcd(int a, int b){
        if(b == 0){
            return a;
        }
        return gcd(b, a%b);
    }
}

Measured memory_bytes: 49116
#include <stdio.h>
#include <vector>
#include <algorithm>

int main(void) {
  int N;
  double res = 0;
  scanf("%d", &N);
  std::vector<int> v;
  v.reserve(N);
  for (int n = 0; n < N; ++n) {
    int i;
    scanf("%d", &i);
    v.push_back(i);
  }
  std::sort(v.begin(), v.end());
  res = v[0];
  for (int n = 1; n < N; n++) {
    res = (res + v[n]) / 2.0;
  }
  printf("%.10f\n", res);
  return 0;
}


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

#define ll long long int
#define rep(i, a, n) for (ll i = a; i < n; i++)
#define repm(i, a, n) for (ll i = a; i >= n; i--)
#define INF 1e9
#define LINF 1e17
#define MOD (int)(1e9 + 7)
#define mod (int)(1e9 + 7)
#define pi 3.141592653589
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vd vector<double>
#define vb vector<bool>
#define vs vector<string>
#define vii vector<vector<int>>
#define vllll vector<vector<ll>>
#define ALL(a) (a).begin(), (a).end()

int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};

void print(bool f)
{
    cout << (f ? "Yes" : "No") << endl;
}

void Print(bool f)
{
    cout << (f ? "YES" : "NO") << endl;
}

int main(void)
{
    ll h, w;
    cin >> h >> w;
    vs s(h);
    rep(i, 0, h) cin >> s[i];

    vllll dp(h + 1, vll(w + 1, INF));
    dp[0][0] = (s[0][0] == '#');
    rep(i, 0, h)
    {
        rep(j, 0, w)
        {
            if (j != 0)
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + (s[i][j] == '#' && s[i][j - 1] == '.'));
            if (i != 0)
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + (s[i][j] == '#' && s[i - 1][j] == '.'));
        }
    }
    cout << dp[h - 1][w - 1] << endl;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using M = map<string,ll>;

ll gcd(ll a,ll b) {
  while(1) {
    if(a < b) swap(a, b);
    if(!b) break;
    a %= b;
  }
  return a;
}
ll lcm(ll a, ll b){
    return a/gcd(a,b)*b;
}



int main(){
    ll N;
    cin >> N;
    vector<ll> T(N,0);
    for(int i=0;i<N;i++){
        cin>>T[i]
    ;}
    ll ans=1;
    for(int i=0;i<N;i++){
        ans=lcm(ans,T[i])
    ;}
    cout<<ans<<endl;



return 0;


}  



Measured memory_bytes: 256
import java.util.*;
public class Main { 
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long ans = 0;
		long[] a = new long[n];
		for(int i = 0; i < n; i++) {
			long tp = sc.nextLong();
			if(i == 0) {
				a[0] = tp;
				continue;
			}
			a[i] =  a[i-1] + tp;
		}
		for(int p = 0; p < a.length; p++) {
			long tp2 = Math.abs((a[a.length-1] - a[p]) - a[p]);
			if(p == 0 || ans > tp2)
			ans = tp2;
		}
		System.out.println(ans);
     }
}

Measured memory_bytes: 88940
#include <bits/stdc++.h>
using namespace std;
map <string,int> ma;
int main (){
	int n,sum=0;cin>>n;
	for (int i=1;i<=n;i++){
		string s;int t;cin>>s>>t;
		sum+=t;ma[s]=sum;
	}
	string s;cin>>s;
	printf ("%d",sum-ma[s]);
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
using namespace std;
const int offset = 100010;

int N, a[100010], bit[200020];

void add(int i)
{
	for (; i < 200020; i += i&-i)
		bit[i]++;
}

int sum(int i)
{
	int ret = 0;
	for (; i > 0; i -= i&-i)
		ret += bit[i];
	return ret;
}

bool check(int med)
{
	long long total = 0;
	int s = 0, i;
	for (i = 0; i < 200020; i++)
		bit[i] = 0;

	for (i = 1; i <= N; i++)
	{
		add(s + offset);
		s += (a[i] >= med) ? 1 : -1;
		total += sum(s + offset);
	}

	return total*4 >= (long long)N*(N+1);
}

int main()
{
	int max = 0;
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &a[i]);
		if (max < a[i])
			max = a[i];
	}

	int l = 1, r = max+1, med;
	while (r-l > 1)
	{
		med = (l+r)/2;
		if (check(med))
			l = med;
		else
			r = med;
	}

	printf("%d\n", l);
}

Measured memory_bytes: 1280
#include <stdio.h>
#define N 8
#define FREE 0
#define NOT_FREE -1

int x[N][N], row[N], col[N], dpos[2*N-1], dneg[2*N-1];
void putQueen(int);
void printBoard();

int main(){
  int i, j, k, r, c;
  
  for(i = 0; i < N; i++){
    for(j = 0; j < N; j++){
      x[i][j] = FREE;
    }
  }
  scanf("%d",&k);
  for(i = 0; i < k; i++){
    scanf("%d%d",&r,&c);
    x[r][c] = NOT_FREE;
  }

  putQueen(0);

  return 0;
}

void putQueen(int i){
  int j;
  if(i == N){
    printBoard();
    return;
  }
  for(j = 0; j < N; j++){
    if(col[j] == NOT_FREE || dpos[i+j] == NOT_FREE || dneg[i-j+N-1] == NOT_FREE)
      continue;
    row[i] = j;
    col[j] = dpos[i+j] = dneg[i-j+N-1] = NOT_FREE;
    putQueen(i+1);
    row[i] = col[j] = dpos[i+j] = dneg[i-j+N-1] = FREE;
  }
}

void printBoard(){
  int i, j;
  for(i = 0; i < N; i++){
    for(j = 0; j < N; j++){
      if(x[i][j] == NOT_FREE){
	if(row[i] != j) return;
      }
    }
  }
  for(i = 0; i < N; i++){
    for(j = 0; j < N; j++){
      if(row[i] == j) printf("Q");
      else printf(".");
    }
    printf("\n");
  }
}

Measured memory_bytes: 572
#include<stdio.h>
int main(){
  int n,m,s,a=1e9,i;
  scanf("%d %d %d",&n,&m,&s);
  if(s>1e8)a=1;
  for(i=0;i<m;i++)printf("%d ",s);
  for(i=m;i<n;i++)printf("%d ",a);
  printf("\n");
  return 0;
}


Measured memory_bytes: 1280
#include <iostream>

using namespace std;

int main(){
  long long int N, K;
  cin >> N >> K;
  long long int A[N+1], cnt[N+1], back=0, front=0, num, mod, ans, len, next, now;
  for(int i=1; i<=N; i++) cin >> A[i];
  for(int i=1; i<=N; i++) cnt[i] = 0;
  next = 1;

  while(1){
    now = next;
    next = A[now];
    cnt[now]++;
    back++;
    if(cnt[now] == 2){
      num = now;
      break;
    }
  }
  next = 1;
  while(1){
    now = next;
    next = A[now];
    cnt[now]++;
    front++;
    if(now == num){
      break;
    }
  }
  len = back - front;

  if(K < front){
    next = 1;
    for(int i=0; i<K; i++){
      now = next;
      next = A[now];
    }
    ans = next;
  }else{
    K -= (front-1);
    mod = K % len;
    next = num;
    for(int i=0; i<mod; i++){
      now = next;
      next = A[now];
    }
    ans = next;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 6704
#include<stdio.h>
int main(){
    int a,x,y,temp;
    scanf("%d %d",&x,&y);
    if(x<y){
        temp = x;
        x = y;
        y = temp;
    }
    a = x%y;
    while(a!=0){
        x=y;
        y=a;
        a = x%y;
    }
    printf("%d\n",y);
    return 0;
}



Measured memory_bytes: 2140
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	int a,c,b;
	cin>>a>>b>>c;
	if(a+b+c>=22)cout<<"bust"<<endl;
	else cout<<"win"<<endl;
	return 0;
}


Measured memory_bytes: 892
import collections

input = raw_input
range = xrange
M = 998244353

def main():
    N = int(input())
    Ds = list(map(int, input().split(" ")))
    if Ds[0] != 0:
        return 0

    counter = collections.Counter(Ds)
    depths = counter.keys()
    
    min_depth = min(depths)
    max_depth = max(depths)

    if min_depth != 0:
        #print("test1")
        return 0
    elif counter[0] != 1:
        return 0
    
    if len(depths) != max_depth + 1:
        #print("test2")
        return 0

    out = 1
    for depth in range(1, max_depth+1):
        num = counter[depth]
        if depth >= 2:
            for i in range(num):
                out = out * before_num
                out = out % M
        before_num = num

    return out

out = main()
print(out)

Measured memory_bytes: 55116
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    int t = 0;
    for( int i = 1; i <= n; i++)
    {
        int l;
        scanf("%d", &l);
        t += min( l, k - l) * 2;
    }
    printf("%d\n", t);
    return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include <cmath>
#include <iostream>
#include <numeric>
#include <string>
#include <string.h>
#include <vector>
#include <deque>

#define REP(i,x) for(int i{ 0 }; i < (int)(x); i++)
#define REPC(i,x) for(int i{ 0 }; i <= (int)(x); i++)
#define RREP(i,x) for(int i{ (int)(x) - 1 }; i >= 0 ;i--)
#define RREPC(i,x) for(int i{ (int)(x)}; i >= 0; i--)
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

typedef int64_t int64;
typedef int64_t ll;

const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };

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

using namespace std;


class C {
	int n;
	string s;
	vector<int> left_west, right_east;

public:
	C()
	{
		cin >> n >> s;
		left_west.resize(n, 0);
		right_east.resize(n, 0);
	}
	void solve()
	{
		int lw{ 0 }, re{ 0 };

		REP(i, n - 1)
		{
			if (s[i] == 'W')
				left_west[i + 1] = left_west[i] + 1;
			else
				left_west[i + 1] = left_west[i];

			if (s[n - i - 1] == 'E')
				right_east[n - i - 2] = right_east[n - i - 1] + 1;
			else
				right_east[n - i - 2] = right_east[n - i - 1];
		}

		//REP(i, n)
		//	cout << left_west[i] << " ";
		//cout << endl;
		//REP(i, n)
		//	cout << right_east[i] << " ";
		//cout << endl;


		int ans{ 400000 };

		REP(i, n)
			chmin(ans, left_west[i] + right_east[i]);

		cout << ans << endl;

	}
};


int main()
{
	C solution;
	solution.solve();

	return 0;
}

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

void print_comp(char x, char y) {
  if(x > y) {
    std::cout << ">" << std::endl;
  } else if(x < y) {
    std::cout << "<" << std::endl;
  } else {
    std::cout << "=" << std::endl;
  }
}
int main(void) {
  int N, M;
  std::cin >> N >> M;
  int r = 1;
  for(int i = 0; i < M; i++) {
    r *= 2;
  }
  std::cout << (1900 * M + 100 * (N - M)) * r << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")

// Begin {{{
using namespace std;

#ifndef DEBUG
#define dump(...)
#endif

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T>
inline vector<T> make_v(const T &initvalue, size_t sz) {
    return vector<T>(sz, initvalue);
}

template <class T, class... Args>
inline auto make_v(const T &initvalue, size_t sz, Args... args) {
    return vector<decltype(make_v<T>(initvalue, args...))>(sz, make_v<T>(initvalue, args...));
}

constexpr int INF = 0x3f3f3f3f;
constexpr int64_t LINF = 0x3f3f3f3f3f3f3f3fLL;

using pii = pair<int64_t, int64_t>;
template <class T> using MaxHeap = priority_queue<T>;
template <class T> using MinHeap = priority_queue<T, vector<T>, greater<>>;
// }}} End

constexpr int dy[] = {0, 1, 0, -1, -1, 1, 1, -1};
constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};

inline bool inside(int y, int x, int H, int W) {
    return (y >= 0 && x >= 0 && y < H && x < W);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M; cin >> N >> M;

    vector<string> a(N), b(M);
    for (auto &ai: a) cin >> ai;
    for (auto &bi: b) cin >> bi;

    const auto match = [&](size_t y, size_t x) -> bool {
        for (size_t i = 0; i < M; ++i) {
            for (size_t j = 0; j < M; ++j) {
                if (y + i < N && x + j < N) {
                    if (a[y + i][x + j] != b[i][j]) {
                        return false;
                    }
                } else {
                    return false;
                }
            }
        }
        return true;
    };

    for (size_t y = 0; y < N; ++y) {
        for (size_t x = 0; x < N; ++x) {
            if (match(y, x)) {
                return cout << "Yes" << "\n", 0;
            }
        }
    }

    cout << "No" << "\n";

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<math.h>
#include<string>
#include<vector>
using namespace std;
int main(){
  int a,b,c, d;
  cin >> a >> b >> c >> d;

  int bus=c, train=a;
  if( a > b ) train = b;
  if( c > d ) bus = d;
  printf("%d\n", train+bus);

  return 0;
  
}


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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define ASC(x) sort(ALL((x)))
#define DESC(x) sort(ALL((x)),greater<ll>())
#define REV(x) reverse(ALL((x)))
#define pb push_back

int main()
{
    ll X, N;
    cin >> X >> N;
    vec p(N);
    REP(i,0,N) {
        cin >> p[i];
    }
    if(SZ(p) > 0) ASC(p);

    queue<ll> _D;
    vec D;
    ll k = 0;
    REP(i,-100,200) _D.push(i+1);
    if(SZ(p) > 0) {
    while(!_D.empty()) {
        ll d = _D.front(); _D.pop();
        if(d != p[k]) {
            D.pb(d);
        }
        else ++k;
    }}

    ll d = INF, P = X;
    FORR(v,D) {
        if(d > abs(v-X)) {
            d = abs(v-X);
            P = v;
        }
    }
    PR(P);

    return 0;
}

/*



*/

Measured memory_bytes: 3612
#include<iostream>
#include <algorithm>
#include <string>
#include<math.h>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;
int main() {
    int a, b;
    cin >> a >> b;

    cout << (a>b?a-1:a) << endl;
    return 0;
}


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

int main(void){

    int n;
    double sum = 0;
    vector<int> list;
    cin >> n;

    for(int i = 0;i < n;i++){
        int a;
        cin >> a;
        list.push_back(a);
    }

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

    for(int i = 0;i < n;i++){
        if(i == 0) sum += (list[i] + list[i+1]) / 2.0;
        else if(i >= 2) sum = (sum + list[i]) / 2.0;
    }

    cout << sum << endl;


    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include <fstream>
#include <time.h>
#include <iterator>


#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 SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
#define print(x) cout<<x<<endl;
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
#define int long long
#define all(x) (x).begin(), (x).end()

using namespace std;

int MOD = (ll)1000000000 + 7;
const ll INF = 1e17;
const double pi = acos(-1);
const long double EPS = 1e-14;
typedef pair<int, int>P;
const int MAX = 200020;

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };




signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int c[10];
	REP(i, 5) {
		cin >> c[i];
	}
	int perm[5];
	REP(i, 5)perm[i] = i;
	int ans = INF;
	do{
		int t = 0;
		REP(i, 5) {
			int idx = perm[i];
			t += (10 - t % 10) % 10;
			t += c[idx];
		}
		ans = min(ans, t);
	} while (next_permutation(perm, perm + 5));
	print(ans);
}


Measured memory_bytes: 384
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
        int A = 0;
		Integer maxA = Integer.MIN_VALUE;//MIN_VALUEで最小値を代入
		Integer minA = Integer.MAX_VALUE;//MAX_VALUEで最大値を代入
		for(int i=0; i<N; i++) {
			A = sc.nextInt();
          	
            minA = Math.min(minA,A);//Aの最小値を求める
			maxA = Math.max(maxA,A);//Aの最大値を求める
			
		}
		//最大値から最小値を引いた数を表示する
		System.out.println(maxA-minA);
	}
}

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

int main(){
 int N,g=0,t=0;
  
  cin>>N;

rep(i,N){
  rep(j,N){
    rep(k,N){
    g=gcd(i+1,j+1); 
      g=gcd(g,k+1);
    t+=g;
}
}
}
  cout << t <<endl;
}
int gcd(int a,int b){
  int tmp;
   if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }
 
  /* ユークリッドの互除法 */
  int r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }

  
return b;
}





Measured memory_bytes: 3564
#include <stdio.h>
#include <string.h>

int main(){
	int k,i;
	scanf("%d", &k);
	getchar();
	
	char s[100];
	scanf("%[^\n]", s);
	
	int len = strlen(s);
	
	if(len == k || len < k){
		printf("%s", s);
	} else if(len > k){
		for(i=0; i<k; i++){
			printf("%c", s[i]);
		}
		printf("...");
	}
	
	return 0;
}

Measured memory_bytes: 1728
#include <bits/stdc++.h>
#define ll long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
#define M 1000000007

using namespace std;

int main() 
{
	IOS	
	ll n;
	cin>>n;
	ll a[n],b[n],c[n];
	for(ll i=0;i<n;++i)
	{
	    cin>>a[i]>>b[i]>>c[i];
	}
	ll dp1[n],dp2[n],dp3[n];
	for(ll i=0;i<n;++i)
	{
	    if(i==0){dp1[i]=a[i];dp2[i]=b[i];dp3[i]=c[i];}
	    else
	    {
	        dp1[i]=max(dp2[i-1],dp3[i-1])+a[i];
	        dp2[i]=max(dp1[i-1],dp3[i-1])+b[i];
	        dp3[i]=max(dp1[i-1],dp2[i-1])+c[i];
	    }
	}
	cout<<max(max(dp1[n-1],dp2[n-1]),dp3[n-1]);
}

Measured memory_bytes: 4992
s1,s2=input().split(" ")
s1=s1.lower()
s2=s2.lower()
flag=0
if(len(s1)>len(s2)):
   a=len(s2)
else:
    a=len(s1)

for i in range(0,a):
    if(s1[i]==s2[i]):
        flag=flag+1
    elif(s1[i]>s2[i]):
            print('>')
            break;
    elif(s1[i]<s2[i]):
            print('<')
            break;
if(flag==a):
    if(len(s1)>len(s2)):
        print(">")

    elif(len(s1)<len(s2)):
        print("<")
    else:
            print("=")
        

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

using Graph=vector<vector<int>>;
class LCA{
    int n;
    vector<int> dep;
    vector<vector<int>> par;
    Graph g;
    const int LOGN_MAX=100;
    void setDep(int v,int d,Graph& tree){
        dep[v]=d;
        for(int i=0;i<tree[v].size();i++) setDep(tree[v][i],d+1,tree);
    }
    public:
    LCA(Graph &tree):n(tree.size()){
        dep=vector<int>(n);
        par=vector<vector<int>>(min(LOGN_MAX,int(log2(n))+1),vector<int>(n));
        g=Graph(n);
        for(int i=0;i<tree.size();i++){
            for(int j=0;j<tree[i].size();j++){
                g[tree[i][j]].push_back(i);
            }
        }

        bool isTree=true;
        int root=-1;
        for(int i=0;i<g.size();i++){
            if(g[i].size()){
                isTree&=(g[i].size()==1);
            }
            else if(root==-1){
                root=i;
                if(g[i].size()==0){
                setDep(i,0,tree);
               }
            }
            else{
                isTree=false;
            }
        }
        assert(isTree);

        for(int i=0;i<n;i++){
            par[0][i]=(g[i].size() ? g[i][0] : i);
        }
        for(int i=0;i+1<par.size();i++){
            for(int j=0;j<par[i].size();j++){
                par[i+1][j]=par[i][par[i][j]];
            }
        }
    }

    int lca(int a,int b){
        if(dep[a]>dep[b]) swap(a,b);
        int dist=dep[b]-dep[a];
        for(int i=0;dist;i++,dist/=2){
            if(dist%2) b=par[i][b];
        }
        assert(dep[a]==dep[b]);
        while(true){
            if(a==b) return a;
            if(par[0][a]==par[0][b]) return par[0][a];
            int lb=0;
            int ub=par.size();
            //[ub,LOGN_MAX)->same anc
            while(ub-lb>1){
                int mid=(lb+ub)/2;
                if(par[mid][a]==par[mid][b]) ub=mid;
                else lb=mid;
            }
            a=par[lb][a];
            b=par[lb][b];
        }
    }
};

int main(){
    int n;
    cin>>n;
    Graph g(n);
    for(int i=0;i<n;i++){
        int k;
        cin>>k;
        for(int j=0;j<k;j++){
            int c;
            cin>>c;
            g[i].push_back(c);
        }
    }
    LCA lg(g);
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        int u,v;
        cin>>u>>v;
        cout<<lg.lca(u,v)<<endl;
    }
}

Measured memory_bytes: 23340
#line 1 "/mnt/c/Users/leafc/dev/compro/lib/template.hpp"


#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
#define MM << " " <<

using namespace std;

template <class T> void say(bool val, T yes = "Yes", T no = "No") { cout << (val ? yes : no) << "\n"; }

template <class T> void chmin(T &a, T b) {
  if (a > b)
    a = b;
}

template <class T> void chmax(T &a, T b) {
  if (a < b)
    a = b;
}


#line 2 "tmp.cpp"

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

  int n;
  cin >> n;
  vi p(n);
  REP(i, n) {
    cin >> p[i];
    p[i]--;
  }

  vi a(n), b(n);
  REP(i, n) {
    a[i] = (i + 1) * n;
    b[i] = (n - i) * n;
  }

  REP(i, n) { a[p[i]] += i; }

  REP(i, n) { cout << a[i] << (i == n - 1 ? "\n" : " "); }
  REP(i, n) { cout << b[i] << (i == n - 1 ? "\n" : " "); }
  return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, m;

int main() {
	cin>>n>>m;
	int a, b, p[n+1];
	memset(p, -1, sizeof(p));
	vector <int> adjlist[n+1];
	for (int i=0; i<m; i++) {
		cin>>a>>b;
		adjlist[a].push_back(b);
		adjlist[b].push_back(a);
	}
	/*for (int i=1; i<=n; i++) {
		cout<<i<<": ";
		for (auto j: adjlist[i]) cout<<j<<" ";
		cout<<endl;
	}*/
	bool vis[n+1];
	memset(vis, 0, sizeof(vis));
	queue <int> q;
	q.push(1);
	vis[1]=1;
	while (!q.empty()) {
		int x=q.front();
		//cout<<x<<endl;
		for (auto i:adjlist[x]) {
			if (!vis[i]) {
				vis[i]=1;
				q.push(i);
				p[i]=x;
			}
		}
		q.pop();
	}
	bool bisa=1;
	for (int i=2; i<=n; i++) {
		if (p[i]==-1) {
			bisa=0;
			break;
		}
	}
	if (bisa) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	for (int i=2; i<=n; i++) {
		cout<<p[i]<<endl;
	}
}



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


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;cin >> n;
	int ans=100,cnt1,cnt2;
	ll x,y;
	for(ll i=1;i*i<=n;++i){
		if(n%i==0){
			x=i;
			y=n/i;
			cnt1=0;
			cnt2=0;
			while(x>0){
				cnt1++;
				x/=10;
			}
			while(y>0){
				cnt2++;
				y/=10;
			}
			ans=min(ans,max(cnt1,cnt2));
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
/*
#defin AB (N/A+( N%A != 0 ))*B
#defin CD (N/C+( N%C != 0 ))*D
*/
int main(void) {
   int  N,A,B,C,D;
   scanf( "%d %d %d %d %d" , &N,&A,&B,&C,&D );
   printf("%d\n" , ((N/A+( N%A != 0 ))*B<(N/C+( N%C != 0 ))*D)*(N/A+( N%A != 0 ))*B+((N/A+( N%A != 0 ))*B>=(N/C+( N%C != 0 ))*D)*(N/C+( N%C != 0 ))*D);
   return 0;
}



Measured memory_bytes: 2136
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;


// maxn = no of digits in [ number s ] 
// maxk = max modulo asked
//    k = modulo
const int maxn = 10000,maxk = 1000 , MOD = 1e9 + 7;
int dp[maxn][2][maxk];
string s;
int K,n;

int solve(int i,int f,int k)
{
	if( i==n )return k == 0;
	if( dp[i][f][k]!=-1 )return dp[i][f][k];
	dp[i][f][k]=0;
	if( f )
	{
		for(int j=0;j<s[i]-'0';j++)
		{
			dp[i][f][k]+=solve(i+1,0,(k+j)%K);
			dp[i][f][k]%=MOD;
		}
		dp[i][f][k]+=solve(i+1,1,(k+s[i]-'0')%K);
	}
	else
	{
		for(int j=0;j<10;j++)
		{
			dp[i][f][k]+=solve(i+1,0,(k+j)%K);
			dp[i][f][k]%=MOD;
		}
	}
	return dp[i][f][k];
		
}

int32_t main()
{
	IOS
	memset(dp,-1,sizeof(dp));
	cin >> s >> K;
	n = s.length();
	
	cout << ( solve( 0 , 1 , 0 ) -1 + MOD )%MOD << endl;
	
	
	
}


Measured memory_bytes: 157184
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 10001; //check the limits, dummy

ll* facs = new ll[MX];

ll modExp(ll base, ll power) {
    if (power == 0) {
        return 1;
    } else {
        ll cur = modExp(base, power / 2); cur = cur * cur; cur = cur % MOD;
        if (power % 2 == 1) cur = cur * base;
        cur = cur % MOD;
        return cur;
    }
}

ll modInv(ll base) {
    return modExp(base, MOD-2);
}

ll mul(ll A, ll B) {
    return (A*B)%MOD;
}

ll add(ll A, ll B) {
    return (A+B)%MOD;
}

ll sub(ll A, ll B) {
    return (A-B+MOD)%MOD;
}

ll choose(ll a, ll b) {
    ll cur = facs[a];
    cur = mul(cur, modInv(facs[b]));
    cur = mul(cur, modInv(facs[a-b]));
    return cur;
}

void initFacs() {
    facs[0] = 1;
    FOR(i, 1, MX) {
        facs[i] = (facs[i-1] * i) % MOD;
    }
}

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

    int N, K; cin >> N >> K;
    initFacs();
    ll ans = 0;


    FOR(i, 1, K+1) {
        int newB = K - i;
        int newR = N - K - i + 1;
        if (newR < 0) {
            cout << 0 << endl; continue;
        }
        ll curAns = choose(newB+i-1, i-1) * choose(newR+i, i);
        curAns = curAns % MOD;
        cout << curAns << endl;
    }


    return 0;
}

// read the question correctly (ll vs int)
// template by bqi343

Measured memory_bytes: 384
N, M = map(int, input().split())

#UnionFind木を使う

p = [-1] * N

def find(x):
    #print(x)
    if p[x] < 0:
        return x
    else:
        p[x] = find(p[x])
        return p[x]

def union(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return
    p[y] += p[x] #木のサイズをマイナスの方向に増やして記録していく
    p[x] = y
    return

def size(x):
    return -p[p[x]]

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1

    union(a, b)

#print(p)
# xが子の場合，p[x] = 親（根，root）
# xが親の場合，p[x] = -1 * 木のサイズ

ans = max(map(size, range(N)))

print(ans)

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

using namespace std;

typedef long long Long;

const int N = 1e5 + 5;

pair<int, int> points_x[N], points_y[N];

struct Point {
  int x, y, ind;
} points[N];

vector<int> adj[N];
int n;

bool vis[N];

int getDist(int i, int j) {
  int dx = points[i].x - points[j].x;
  int dy = points[i].y - points[j].y;
  return min(abs(dx), abs(dy));
}

Long Prim() {
  sort(points, points + n, [](const Point& i , const Point& j) {
    return i.ind < j.ind;
  });

  Long res = 0;

  priority_queue<pair<int, int>> q;
  q.emplace(0, 0);

  while (!q.empty()) {
    auto curr = q.top();
    q.pop();
    if (vis[curr.second]) continue;
    vis[curr.second] = true;
    res -= curr.first;

    for (int v : adj[curr.second]) {
      if (vis[v]) continue;
      q.emplace(-getDist(curr.second, v), v);
    }
  }

  return res;
}

void Build() {
  for (int k = 0; k < 2; ++k) {
    sort(points, points + n, [](const Point& i , const Point& j) {
      return make_pair(i.x,i.y) < make_pair(j.x,j.y);
    });

    for (int i = 0; i < n; ++i) {
      if (i + 1 < n) {
        adj[points[i].ind].push_back(points[i + 1].ind);
      }
      if (i > 0) {
        adj[points[i].ind].push_back(points[i - 1].ind);
      }
    }

    for (int i = 0; i < n; ++i) {
      swap(points[i].x, points[i].y);
    }
  }
}

int main() {
  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);

#ifdef Local
  freopen("test.in", "r", stdin);
#endif

  cin >> n;

  for (int i = 0; i < n; ++i) {
    cin >> points[i].x >> points[i].y;
    points[i].ind = i;
  }

  Build();
  cout << Prim();

}


Measured memory_bytes: 8568
#include <iostream>
#include <iomanip>
#include <math.h>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <bitset>
using namespace std;

#define ll long long int
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repm(i, a, n) for (int i = a; i >= n; i--)
#define INF 1e9
#define LINF 1e17
#define MOD (int)(1e9 + 7)
#define pi 3.141592653589
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vs vector<string>
#define vii vector<vector<int>>
#define vll vector<ll>
#define vllll vector<vector<ll>>
#define vd vector<double>
#define ALL(a) (a).begin(), (a).end()
#define sort_v(a) sort(a.begin(), a.end())
#define reverse_v(a) reverse(a.begin(), a.end())
#define fi first
#define se second

void print(bool c)
{
    (c) ? (cout << "Yes" << endl) : (cout << "No" << endl);
}

void Print(bool c)
{
    (c) ? (cout << "YES" << endl) : (cout << "NO" << endl);
}

//最小公倍数
template <typename T>
T gcd(T a, T b)
{
    while (1)
    {
        if (a < b)
            swap(a, b);
        if (b == 0)
            break;
        a %= b;
    }
    return a;
}

//最大公約数
template <typename T>
T lcm(T a, T b)
{
    return a * b / gcd(a, b);
}
//セカンドキー->ファーストキーの順ソート
bool cmp(const pii &a, const pii &b)
{
    if (a.second != b.second)
        return a.second < b.second;
    return a.first < b.first;
}

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int eve(int x)
{
    if (x % 400 == 0)
        return 1;
    if (x % 100 == 0)
        return 0;
    if (x % 4 == 0)
        return 1;
    return 0;
}

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

    ll ans = 1;
    for (ll i = sqrt(m); i >= 1; i--)
    {
        if (m % i == 0)
        {
            if (m / i <= m / n)
                ans = max(ans, m / i);
            if (i <= m / n)
                ans = max(ans, i);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long, long long> P;
#define int long long
#define override_rep(i, l, r, mes, ...) mes
#define rep1(i, n) for (int i = 0; i < n; i++)
#define rep2(i, l, r) for (int i = l; i < r; i++)
#define rep(...) override_rep(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
template<typename T, typename U>
istream& operator>>(istream& in, pair<T, U>& p) {
    in >> p.first >> p.second;
    return in;
}
int dp[100001][13];
signed main(signed argc, char* argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    const int MOD = 1000000007;
	string s;
	cin>>s;
	dp[0][0]=1;
	rep(i,s.size()){
		rep(it,10) {
			if(s[i]!='?'&&it!=s[i]-'0')continue;
			rep(j, 13) {
				dp[i + 1][(j*10 + it) % 13] = (dp[i + 1][(j*10 + it) % 13]+dp[i][j])%MOD;
			}
		}
	}
	cout<<dp[s.size()][5]<<endl;
}


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

int main() {
	ios_base::sync_with_stdio( false );

	int64_t N, A, B;
	cin >> N >> A >> B;

	if( A > B ) {
		cout << 0 << endl;
	}
	else if( N == 1 ) {
		cout << (A == B ? 1 : 0) << endl;
	}
	else {
		cout << (N-2) * (B-A) + 1 << endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define ll long long
using ull = unsigned long long;
using namespace std;
const int INF = 1e10;
const int MOD = 1e9 + 7;
#define dump(x)                             \
    if (dbg) {                              \
        cerr << #x << " = " << (x) << endl; \
    }
#define overload4(_1, _2, _3, _4, name, ...) name
#define FOR1(n) for (ll i = 0; i < (n); ++i)
#define FOR2(i, n) for (ll i = 0; i < (n); ++i)
#define FOR3(i, a, b) for (ll i = (a); i < (b); ++i)
#define FOR4(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FORR(i, a, b) for (int i = (a); i <= (b); ++i)
template <class T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return 1;
    } else
        return 0;
}
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    } else
        return 0;
}
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(), (v).end()
#define SZ(x) ((int)(x).size())
#define P pair<int, int>
#define V vector<int>
//#define S set<int>
#define itn int
bool dbg = false;

int N, A[202020];

void solve() {
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> N;
    FOR(N)
    cin >> A[i];
    sort(A, A + N);
    bool flag = true;
    FOR(N - 1) {
        if (A[i] == A[i + 1])
            flag = false;
    }
    cout << (flag ? "YES" : "NO") << endl;
    solve();
    return 0;
}


Measured memory_bytes: 1792
#include <stdio.h>
#include <vector>
#include <set>
#include <utility>
using namespace std;
typedef long long ll;

int main(void) {
  ll i, j, k, n, m, a, b, now, t;
  scanf("%lld%lld", &n, &m);
  vector<ll> vec[n];
  ll dis[n], dir[n];
  set< pair<ll, ll> > s;
  pair<ll, ll> p;
  for(i = 0; i < m; ++i) {
    scanf("%lld%lld", &a, &b);
    vec[--a].push_back(--b);
    vec[b].push_back(a);
  }
  for(i = 0; i < n; ++i) {
    dis[i] = 1e9;
    dis[0] = 0;
    s.insert(make_pair(dis[i], i));
  }
  while(s.size()) {
    now = (*s.begin()).second, s.erase(s.begin());
    for(i = 0; i < vec[now].size(); ++i) {
      t = vec[now][i];
      if(dis[t] > dis[now] + 1) {
        p = make_pair(dis[t], t);
        s.erase(p);
        dir[t] = now;
        dis[t] = p.first = dis[now] + 1;
        s.insert(p);
      }
    }
  }
  printf("Yes\n");
  for(i = 1; i < n; ++i) printf("%lld\n", dir[i] + 1);
  return 0;
}

Measured memory_bytes: 19372
S, T = readlines.map(&:chomp)

rep = ->(s, n){s.codepoints * ((s.size + n - 1) / s.size)}
ptn = rep[T, S.size + T.size]
mp = [-1]
j = -1
ptn.size.times do |i|
  j = mp[j] while j >= 0 && ptn[i] != ptn[j]
  j += 1
  mp << j
end
j = 0
mx = 0
rep[S, S.size * 2 + T.size].each do |x|
  j = mp[j] while j == ptn.size || (j >= 0 && ptn[j] != x)
  j += 1
  mx = j if mx < j
end
puts mx >= S.size + T.size ? -1 : mx / T.size

Measured memory_bytes: 48160