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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()

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

  vector<int>a(3);
  for(int i=0;i<3;i++)cin>>a[i];
  sort(rng(a));
  cout<<a[0]+a[1]<<endl;
  return 0;
}


Measured memory_bytes: 256
def i():
	return int(input())
def i2():
	return map(int,input().split())
def s():
	return str(input())
def l():
	return list(input())
def intl():
	return list(int(k) for k in input().split())

s = s()
m1 = -1
for i in range(len(s)):
	if s[i] == "A" and m1 == -1:
		m1 = i
	if s[i] == "Z":
		m2 = i
	
print(m2 - m1 + 1)

Measured memory_bytes: 9296
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
m = B[A[0]-1]
for i, j in zip(A, A[1:]):
    m += B[j-1]
    m += C[i-1] if j-i==1 else 0
print(m)

Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdio>

#define MAX_V 210
#define INF (1<<29)

using namespace std;

const double EPS=1e-10;

struct edge{int to,cap,rev;};

vector<edge> G[MAX_V];
bool used[MAX_V];

void add_edge(int from,int to,double cap){
  G[from].push_back((edge){to,cap,G[to].size()});
  G[to].push_back((edge){from,0,G[from].size()-1});
}

int dfs(int v,int t,int f){
  if(v==t)return f;
  used[v]=true;
  for(int i=0;i<G[v].size();i++){
    edge &e=G[v][i];
    if(!used[e.to] && e.cap>0){
      int d=dfs(e.to,t,min(f,e.cap));
      if(d>0){
        e.cap-=d;
        G[e.to][e.rev].cap+=d;
        return d;
      }
    }
  }
  return 0;
}

vector<double>cost[MAX_V];
int n,m;

int max_flow(double lim){

  for(int i=0;i<MAX_V;i++)G[i].clear();

  int s=n+m,t=n+m+1;
  for(int i=0;i<n;i++)add_edge(s,i,1);
  for(int i=0;i<m;i++)add_edge(i+n,t,1);

  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      if(cost[i][j]<lim+EPS){
        add_edge(i,j+n,1);
      }
    }
  }

  int flow=0;
  for(;;){
    fill(used,used+MAX_V,false);
    int f=dfs(s,t,INF);
    if(f==0)return flow;
    flow+=f;
  }
}

double dist(double x1,double y1,double x2,double y2){
  return sqrt(pow(x1-x2,2)+pow(y1-y2,2));
}
int main(void){

  while(cin >> n >> m,n|m){
    vector<double>nx(n),ny(n),nv(n),mx(m),my(m);

    for(int i=0;i<n;i++)
      cin >> nx[i] >> ny[i] >> nv[i];

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

    for(int i=0;i<n;i++){
      cost[i].resize(m);
      for(int j=0;j<m;j++){
        cost[i][j]=dist(nx[i],ny[i],mx[j],my[j])/nv[i];
      }
    }

    double l=0,r=1e8;

    for(int i=0;i<500;i++){
      double mid=(l+r)/2;
      int res=max_flow(mid);
      if(res==m)r=mid;
      else l=mid;
    }

    printf("%.8f\n",r);
  }

  return 0;
}

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

class Program
{
    static void Main()
    {
        var o = Console.ReadLine();
        var e = Console.ReadLine();
        var res = "";
        for (int i = 0; i < o.Length; i++)
        {
            res += o[i];
            if (i > e.Length - 1)
            {
                continue;
            }
            res += e[i];
        }
        Console.WriteLine(res);
    }
}



Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	ios_base::sync_with_stdio(false);
	int a,b, n;
	cin>>n>>a>>b;
	int k;
	if(a>=b)
		k=a-b;
	else
		k=b-a;
	if(k%2==0){
		cout<<"Alice";
	}
	else
		cout<<"Borys";
	return 0;
}

Measured memory_bytes: 256
import math
a,b,h,m = map(int,input().split())

ans = 0
cos = 0
mi = m/60 * 360 #分針の角度
hour = (60*h + m)/720 * 360 #時針の角度

cos = math.cos(math.radians(hour - mi))
ans = a*a + b*b -2*a*b*cos
#余弦定理
ans = ans ** (1/2)
print(ans)


Measured memory_bytes: 9404
#include <iostream>
#include <string>
#include <cmath>
#include <math.h>
#include <limits>

using namespace std;

#define INF 2000000000

int dp[100010] = {0};
int tmp = INF;
int main() {
    int n,k;
    cin >> n >> k;
    int high[n] = {0};
    for (int i=0;i<n;i++){
        cin >> high[i];
    }
    dp[1] = 0;
    dp[2] = abs(high[1] - high[0]);
    for (int i=3;i<=n;i++){
        int j = 1;
        tmp = INF;
        while(j < i && j <= k){
            if(tmp >= dp[i-j] + abs(high[i-1] - high[i-1-j])){
                tmp = dp[i-j] + abs(high[i-1] - high[i-1-j]);
            }
            dp[i] = tmp;
            j++;
        }
    }
    cout << dp[n];
}



Measured memory_bytes: 1024
#include<iostream>
#include<stack>
using namespace std;
static const int N = 100;
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n, M[N][N];
int color[N], d[N], f[N], tt;
int nt[N];

int next(int u){
  for ( int v = nt[u]; v < n; v++ ) {
    nt[u] = v + 1;
    if ( M[u][v] ) return v;
  }
  return -1;
}

void dfs_visit(int r){
  for ( int i = 0; i < n; i++ ) nt[i] = 0;

  stack<int> S;
  S.push(r);
  color[r] = GRAY;
  d[r] = ++tt;

  while ( !S.empty() ) {
    int u = S.top();
    int v = next(u);
    if ( v != -1 ) {
      if ( color[v] == WHITE ) {
        color[v] = GRAY;
        d[v] = ++tt;
        S.push(v);
      }
    } else {
      S.pop();
      color[u] = BLACK;
      f[u] = ++tt;
    }
  }
}

void dfs() {
  for ( int i = 0; i < n; i++ ){
    color[i] = WHITE;
    nt[i] = 0;
  }
  tt = 0;

  for ( int u = 0; u < n; u++ ) {
    if ( color[u] == WHITE ) dfs_visit(u);
  }
  for ( int i = 0; i < n; i++ ) {
    cout << i+1 << " " << d[i] << " " << f[i] << endl;
  }
}

int main() {
  int u, k, v;

  cin >> n;
  for ( int i = 0; i < n; i++ ) {
    for ( int j = 0; j < n; j++ ) M[i][j] = 0;
  }

  for ( int i = 0; i < n; i++ ) {
    cin >> u >> k;
    u--;
    for ( int j = 0; j < k; j++ ) {
      cin >> v;
      v--;
      M[u][v] = 1;
    }
  }

  dfs();

  return 0;
}


Measured memory_bytes: 3140
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <cstdio>
#include <cstdint>
using namespace std;

uint_fast16_t d;
uint_fast32_t M = 0;
uint_fast64_t c, sd = 0, sc = 0;
char ct;

int main() {
    while((ct=getchar_unlocked())>='0') M = M * 10 + ct - '0';
    while(M--) {
        c = 0;
        d = getchar_unlocked() - '0';
        getchar_unlocked();
        while((ct=getchar_unlocked())>='0') c = c * 10 + ct - '0';
        sc += c;
        sd += c * d;
    }
    printf("%lld\n", --sc + --sd / 9);
	return 0;
}


Measured memory_bytes: 128
N = int(input())
W = [int(n) for n in input().split()]
W_ = [W[0]]

for i in range(1, N):
    W_.append(W_[-1] + W[i])
#print(W_)

d_min = 100000
for i in range(N):
    d = abs(2 * W_[i] - W_[-1])
    d_min = min(d_min, d)

print(d_min)


Measured memory_bytes: 9096
n = int(input())
x = list(map(int, input().split()))
x1 = []
for i, xi in enumerate(x):
    x1.append([i, xi])

x_sort = sorted(x1, key=lambda x: x[1])
t = int(n / 2)
lxt = []
for i in range(n):
    if i < t:
        x[x_sort[i][0]] = x_sort[t][1]
    else:
        x[x_sort[i][0]] = x_sort[t - 1][1]

for i in range(n):
    print(x[i])


Measured memory_bytes: 45376
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

			String in = br.readLine();
			String chr[] = in.split(" ");
			int a = Integer.parseInt(chr[0]);
			int b = Integer.parseInt(chr[1]);
			int c = Integer.parseInt(chr[2]);
			System.out.println(a==b?c
							  :a==c?b
							  :a);

		}
	}
}

Measured memory_bytes: 25348
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int k,a,b;
    cin>>k>>a>>b;
    for(int i = a; i<=b;i++)
    {
        if(i%k==0)
        {
            cout<<"OK";
            return 0;
        }
    }
    cout<<"NG";
}


Measured memory_bytes: 3592
#include<stdio.h>
#include<math.h>

int main(){
  int a,b,i;
  char op;

  while(1){
    scanf("%d %c %d",&a,&op,&b);
    if (op=='+'){
      printf("%d\n",a+b);
    }
    else if (op=='-'){
      printf("%d\n",a-b);
    }
    else if (op=='*'){
      printf("%d\n",a*b);
    }
    else if (op=='/'){
      printf("%d\n",a/b);
    }
    else if (op=='?'){
      break;
    }
  }

  return 0;
}
  

Measured memory_bytes: 600
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define M 102
using namespace std;
int read(){
	int nm=0,fh=1; char cw=getchar();
	for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;
	for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
	return nm*fh;
}
int sm[M][M],dp[M][M][M],n,m,X,Y,ans;
char ch[M];
inline int sum(int x,int y,int xx,int yy){return sm[xx][yy]+sm[x-1][y-1]-sm[x-1][yy]-sm[xx][y-1];}
void upd(int &x,int num){x=max(x,num);}
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		scanf("%s",ch+1);
		for(int j=1;j<=m;j++){
			sm[i][j]=ch[j]=='o',sm[i][j]+=sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1];
			if(ch[j]=='E') X=i,Y=j;
		}
	}	
	for(int up=0;up<X;up++){
		for(int i=0;i<=n-X;i++){
			int U=max(i+1,X-up),D=min(n-up,X+i);
			if(U>D) continue;
			for(int j=0;j<Y;j++){
				for(int k=0;k<=m-Y;k++){
					int L=max(k+1,Y-j),R=min(m-j,k+Y);
					if(L>R) continue; else upd(ans,dp[i][j][k]);
					if(Y-j-1>k) upd(dp[i][j+1][k],dp[i][j][k]+sum(U,Y-j-1,D,Y-j-1));
					if(Y+k<m-j) upd(dp[i][j][k+1],dp[i][j][k]+sum(U,Y+k+1,D,Y+k+1));
					if(X+i<n-up) upd(dp[i+1][j][k],dp[i][j][k]+sum(X+i+1,L,X+i+1,R));
					if(X-up-1>i) dp[i][j][k]+=sum(X-up-1,L,X-up-1,R);
				}
			}
		}
	}
	printf("%d\n",ans); return 0;
}

Measured memory_bytes: 4352
#include<cstdio>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>
#include<map>
 
 
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
#define mod 1000000007
//#define mod 998244353

int M,W,H;
vector<int> h_bombs[300005];
vector<int> w_bombs[300005];
set<pair<int,int> > atlas;
signed main(){
    scanf("%lld %lld %lld",&H,&W,&M);
    rep(i,M){
        int h,w;
        scanf("%lld %lld",&h,&w);h--;w--;
        h_bombs[h].pb(w);
        w_bombs[w].pb(h);
        atlas.insert(mp(h,w));
    }
    int h_max=0;
    vector<int> h_max_i;
    int w_max=0;
    vector<int> w_max_i;
    rep(i,H){
        if(h_bombs[i].size()>=h_max){
            if(h_bombs[i].size()>h_max)h_max_i.clear();
            h_max=h_bombs[i].size();
            h_max_i.pb(i);
        }
    }
    rep(i,W){
        if(w_bombs[i].size()>=w_max){
            if(w_bombs[i].size()>w_max)w_max_i.clear();
            w_max=w_bombs[i].size();
            w_max_i.pb(i);
        }
    }
    bool overrap=true;
    rep(i,h_max_i.size()){
        rep(j,w_max_i.size()){
            if(atlas.find(mp(h_max_i[i],w_max_i[j]))==atlas.end()){
                overrap=false;
                break;
            }
        }
    }
    if(overrap){
        int ans=h_max+w_max-1;
        printf("%lld\n",ans);
    }else{
        int ans=h_max+w_max;
        printf("%lld\n",ans);
    }
}

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

int main(){
    int a,b;
    char op;
    
    while(1){
    cin >> a >> op >> b;
    if(op == '?'){
        break;
    }
    
    if(op == '+'){
        cout << a + b << endl;
    }
   else if(op == '-'){
        cout << a - b << endl;
    }
    else if(op == '*'){
        cout << a * b << endl;
    }
    else if(op == '/'){
        cout << a / b << endl;
    }
    
        }
}



Measured memory_bytes: 3088
#include<bits/stdc++.h>
using namespace std;
int a[27];
int b[51];
int c[51];
int main(){
	int n;
	cin >> n;
	for(int i=1;i<=n;i++)
		cin >> a[i];
	for(int i=1;i<=n;i++)
		cin >> b[i];	
	for(int i=1;i<n;i++)
		cin >> c[i]; 
		
	int nz=b[a[1]];	
	for(int i=2;i<=n;i++){
		if(a[i]-1==a[i-1]){
			nz=nz+b[a[i]]+c[a[i-1]];
		//	cout<<nz<<endl;
		}		
		else{
			nz+=b[a[i]];
		//	cout<<nz<<endl;
		}
	}
	cout << nz << endl;
	return 0;
} 


Measured memory_bytes: 256
# 標準入力
N = int(input())
a = input().split()
A = []
for i in a:
  A.append(int(i)-1)
b = input().split()
B = []
for i in b:
  B.append(int(i))
c = input().split()
C = []
for i in c:
  C.append(int(i))
# A[i+1]-A[i]==1なら満足度変数manzokuにC[i]を加える。manzokuの初期値はしぐまB
manzoku = 0
for i in range(N):
  manzoku += B[i]
for i in range(N-1):
  if A[i+1] - A[i] == 1:
    manzoku += C[A[i]]
# 出力じゃ
print(manzoku)

Measured memory_bytes: 3188
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 = sc.nextInt();
		if(N % 500 <= A) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}

	}

}


Measured memory_bytes: 19792
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
using namespace std;

ll n,p[10];
ld sum,fact=1;
pair<ld,ld> a[10];

ld dist( pair<ld,ld> P1 , pair< ld , ld > P2 ){
    return sqrt( (P1.fi-P2.fi)*(P1.fi-P2.fi) + (P1.se-P2.se)*(P1.se-P2.se) );
}

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for(ll i=0; i<n; i++) cin >> a[i].fi >> a[i].se , p[i] = i+1 , fact*=(i+1);

    do{
        for( ll i=1; i<n; i++ ) sum+=dist( a[ p[i]-1 ] , a[ p[i-1]-1 ] );
    }while( next_permutation( p , p+n ) );

    cout << setprecision( 10 ) << (sum/fact);

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
int main(){
    cout << fixed << setprecision(10);
    ll n;
    cin >> n;
    ll ans = 0;
    for(int i=1;i<=n-1;i++){
        ans += i;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
const int INF = 10000;
using namespace std;

int cost[100][100];
int tim[100][100];

void init()
{
	for(int i=0;i<100;i++){
		for(int j=0;j<100;j++){
			if(i == j){
				cost[i][j] = 0;
				tim[i][j] = 0;
			}else{
				cost[i][j] = INF;
				tim[i][j] = INF;
			}
		}
	}
}

int main()
{
	int n,m;
	while(cin >> n >> m){
		if(n == 0 && m == 0)
			break;
		init();
		int a,b,c,t;
		for(int i=0;i<n;i++){
			cin >> a >> b >> c >> t;
			cost[a-1][b-1] = c;
			cost[b-1][a-1] = c;
			tim[a-1][b-1] = t;
			tim[b-1][a-1] = t;
		}
		
		for(int i=0;i<m;i++){
			for(int j=0;j<m;j++){
				for(int k=0;k<m;k++){
					int cdis = cost[j][i] + cost[i][k];
					if(cdis < cost[j][k]){
						cost[j][k] = cdis;
					}
					int tdis = tim[j][i] + tim[i][k];
					if(tdis < tim[j][k]){
						tim[j][k] = tdis;
					}
				}
			}
		}
		
		int n;
		cin >> n;
		int p,q,r;
		for(int i=0;i<n;i++){
			cin >> p >> q >> r;
			if(r == 0){
				cout << cost[p-1][q-1] << endl;
			}else if(r == 1){
				cout << tim[p-1][q-1] << endl;
			}
		}
	}
	return 0;
}

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

int main(){
  int N,M,p,tsum=0,bsum=0,csum=0;
  string s;
  cin >> N >> M;
  vector<bool> ac(N,false);
  vector<int> acn(N,0);
  
  for(int i = 0;i < M;i++){
    s = "",p = -1;
  	cin >> p >> s;
    if(p == -1)
      break;
    if(!(ac.at(p-1))){
    	if(s == "AC"){
        	ac.at(p-1) = true;
          	tsum+=1;
        }else if(s == "WA"){
        	acn.at(p-1) =acn.at(p-1) +1;
        }
    }
  }
  
  for(int i = 0;i < N;i++){
  	if(ac.at(i)){
    	csum += acn.at(i);
    }
  }
  
  cout << tsum << " "<< csum << endl;
}


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

signed main(){
  	int n,k,s;
  	scanf("%d%d%d",&n,&k,&s);
  	if(s==(int)1e9){
        for(int i=1;i<=k;i++){
            printf("%d ",s);
        }
        for(int i=k+1;i<=n;i++){
            printf("1 ");
        }
        puts("");
  	}
  	else{
        for(int i=1;i<=k;i++){
            printf("%d ",s);
        }
        for(int i=k+1;i<=n;i++){
            printf("%d ",s+1);
        }
        puts("");
  	}
  	return 0;

}


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

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

    int a[n];
    float avg = 0.0;

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

    pair<float, int> pa[n];
    for (int i = 0; i < n; i++) {
        pa[i] = make_pair(abs(avg - a[i]), i);
    }

    sort(pa, pa + n);

    cout << pa[0].second << endl;

    return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = 0
for k in range(N):
    if A[k] <= B[k]:
        ans += A[k]
        d = B[k]-A[k]
        if d > A[k+1]:
            ans += A[k+1]
            A[k+1] = 0
        else:
            ans += d
            A[k+1] -= d
    else:
        ans += B[k]
print(ans)


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

import math

def main():
    n,m = map(int, input().strip().split())
    a_li = list(map(int, input().strip().split()))

    if n - sum(a_li) < 0:
        print(-1)
    else:
        print(n - sum(a_li))


if __name__ == '__main__':
    main()


Measured memory_bytes: 9876
# -*- coding: utf-8 -*-
# A
#
# input
a, b = map(int,input().split())
# calc output
if a==b:
  print('Draw')
elif a==1:
  print('Alice')
elif b==1:
  print('Bob')
elif a>b:
  print('Alice')
else:
  print('Bob')

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

int main() {
  int H,W;
  cin >> H>>W;
  vector<char> pic(H*W);
  for(int i=0;i<H*W;i++){
     cin>>pic.at(i);
  }for(int i=0;i<W+2;i++){
      cout<<"#";
  }cout<<endl;
  for(int j=0;j<H;j++){
      cout<<"#";
      for(int k=0;k<W;k++){
          cout<<pic.at(W*j+k);
      }cout<<"#"<<endl;
  }for(int i=0;i<W+2;i++){
      cout<<"#";
  }cout<<endl;
}

Measured memory_bytes: 256
object Main extends App{
    // Your code here!
    def gcd(x:Int, y:Int): Int = {
        @scala.annotation.tailrec
        val t = (x,y)
        t match {
            case (0,_) => return y
            case (_,0) => return x
            case (_,_) => 0
        }
        (x >= y) match {
            case true => gcd(x%y, y)
            case false => gcd(x, y%x)
        }
    }
    val inputArray = io.StdIn.readLine().split(" ").map{_.toInt}
    println(gcd(inputArray(0), inputArray(1)))
}



Measured memory_bytes: 43940
def main():
    N, M, K = map( int, input().split())
    A = list( map( int, input().split()))
    B = list( map( int, input().split()))
    indb = M-1
    now = sum(B)
    count = M
    while now > K:
        now -= B[indb]
        count -= 1
        indb -= 1
 
    ans = count
    for a in A:
        # print(ans, now)
        now += a
        count += 1
        while now > K and indb >= 0:
            now -= B[indb]
            count -= 1
            indb -= 1
        if now <= K:
            if ans < count:
                ans = count
    print(ans)
if __name__ == '__main__':
    main()

Measured memory_bytes: 40684
#include "bits/stdc++.h"
using namespace std;

int main() {
	int N;
	string S;
	int LW = 0;
	int LE = 0;
	int RW = 0;
	int RE = 0;
	cin >> N >> S;
	for (int i = 0; i < N; ++i) {
		if ('E' == S[i]) {
			RE++;
		}
		else {
			RW++;
		}
	}
	int ans = 1e9;
	for (int i = 0; i < N; ++i) {
		if ('E' == S[i]) {
			RE--;
		}
		else {
			RW--;
		}
		ans = min(ans, LW + RE);
		if ('E' == S[i]) {
			LE++;
		}
		else {
			LW++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3856
#include <stdio.h>

static const int n =100;

int ch(int x,int y){
  return x<y ? x : y;
}

int main(){
  int i,j,k,l;
  int num,d[n+1],u[n+1][n+1];
  scanf("%d",&num);

  for(i=1;i<=num;i++){
    scanf("%d %d",&d[i-1],&d[i]);
  }

  for(i=1;i<=num;i++){
    u[i][i] = 0;
  }
  for(l=2;l<=num;l++){
    for(i=0;i<=num-l+1;i++){
      j=l+i-1;
      u[i][j] = (1<<21);
      
      for(k=i;k<=j-1;k++){
	u[i][j] = ch(u[i][j],u[i][k]+u[k+1][j]+d[i-1]*d[k]*d[j]);
      }
    }
  }

printf("%d\n",u[1][num]);

return 0;
}



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

using namespace std;

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  long A, C;
  A = a * b;
  C = c * d;
  if( A >= C )
    cout << A << endl;
  else if( A < C )
    cout << C << endl;
  return 0;
}

Measured memory_bytes: 256
data = input().split()

a = int(data[0])
b = int(data[1])
c = int(data[2])

if a > b:
  temp = a
  a = b
  b = temp

if b > c:
  temp = b
  b = c
  c = temp

if a > b:
  temp = a
  a = b
  b = temp

if b > c:
  temp = b
  b = c
  c = temp

print("{0} {1} {2}".format(a,b,c))


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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define foru(i, a, b) for(int i = a; i <= b; i++)
#define ford(i, a, b) for(int i = a; i >= b; i--)
#define endl "\n"
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
#define com(a, b) a ## b
#define scv(a, b, c) #a#b#c
#define db(x) cerr << "[" << #x << ": " << (x) << "] " << endl;
#define run cerr << 1 << endl; 
template<class T> void printvec(vector<T>& x, int a, int b) {foru (i, a, b) cout << x[i] << " "; cout << endl;}

typedef long long ll;
typedef double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vii;
typedef vector<pll> v2l;
typedef pair<char, int> pci;
typedef vector<pci> vci;

const ld PI = acos((ld) -1);
const ld EPS = 1e-6;
const int N = 1e6 + 1;
const int NN = 1e3 + 1;
const ll MOD = 1e9 + 7;
const ll oo = 1e18 + 7;
const int BASE = 10000;

int GCD(int a, int b) {
    if (!a) {
        return b;
    }
    return GCD(b % a, a);
}

void solve() {
    int n;
    cin >> n;
    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                res += GCD(i, GCD(j, k));
            }
        }
    }
    cout << res;
}

int main() {
    #ifdef DEBUG
        com(fre, open) (scv(solve, ., inp), "r", stdin);
        com(fre, open) (scv(solve, ., out), "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout.precision(10);
    solve();
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    return 0;
} 

Measured memory_bytes: 3776
#include<bits/stdc++.h>
using namespace std;
 
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return
#define lb(v,n) lower_bound(v.begin(),v.end(),n)
#define ub(v,n) upper_bound(v.begin(),v.end(),n)
#define mae(v) max_element(v.begin(),v.end())
#define mie(v) min_element(v.begin(),v.end())
#define INF 0x7FFFFFFF
#define mod 1000000007
#define fir first
#define sec second
typedef long long ll;
////////////////////////////////////////////////////////////
unsigned gcd(unsigned a, unsigned b) {
  while(1) {
    if(a < b) swap(a, b);
    if(!b) break;
    a %= b;
  }
  return a;
}

int main(){
	int n,X;
	cin >> n >> X;

	vector<ll> x(n);
	rep(i,0,n) cin >> x[i];

	if(n == 1 ){
		cout << abs( X - x[0] ) << endl;
		ret 0;
	}

	ll ans = gcd( abs(X-x[0]) ,  abs(X-x[1]) );

	rep(i,0,n){
		ans = gcd( ans , abs(X-x[i]));
	}


	cout << ans << endl;

	ret 0;
}

Measured memory_bytes: 1152
import sys

sys.setrecursionlimit(1000000)

import bisect
import math
import collections
import heapq


def solve(A, B, C, K):
    while K > 0:
        if C > B > A:
            return "Yes"
        else:
            if B <= A:
                B *= 2
            else:
                C *= 2
            K -= 1

    if C > B > A:
        return "Yes"
    return "No"


if __name__ == "__main__":
    A, B, C = tuple(map(int, input().split(" ")))
    K = int(input())
    print(solve(A, B, C, K))


Measured memory_bytes: 9460
#include <stdio.h>
int main(void){
    int n,i,ans = 1,max=0;
    int h[n];
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&h[i]);
    }
    
    max = h[0];
    
    for(i=1;i<n;i++){
        if(h[i-1]<=h[i]&&max<=h[i]){
            max = h[i];
            ans++;
        }
    }
    
    printf("%d\n",ans);
    return 0;
    
}

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

int main()
{
    vector<int> a(3);
    cin >> a[0] >> a[1] >> a[2];
    sort(a.begin(), a.end());
    int substract = 2 * a[2] - a[1] - a[0];
    if (substract % 2 == 0)
    {
        cout << substract / 2 << endl;
    }
    else
    {
        cout << substract / 2 + 2 << endl;
    }
}

Measured memory_bytes: 3620
#
# abc150 c
#

import sys
from io import StringIO
import unittest
import itertools


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
1 3 2
3 1 2"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """8
7 3 5 4 2 1 6 8
3 8 2 5 4 6 7 1"""
        output = """17517"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """3
1 2 3
1 2 3"""
        output = """0"""
        self.assertIO(input, output)


def resolve():
    N = int(input())
    P = list(map(int, input().split()))
    Q = list(map(int, input().split()))

    # NL = [i+1 for i in range(N)]
    # IL = list(itertools.permutations(NL))
    IL = list(itertools.permutations(range(1, N+1)))

    a = b = 0
    for i in range(len(IL)):
        if list(IL[i]) == P:
            a = i
        if list(IL[i]) == Q:
            b = i

    print(abs(a-b))


if __name__ == "__main__":
    # unittest.main()
    resolve()


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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define fst first
#define snd second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define EPS (1e-9)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }

const string YES = "Yes";
const string NO  = "No";

typedef long long ll;

string s;
void solve() {
  string t = string(s.rbegin(),s.rend());
  if( s != t ) {
    puts(NO.c_str());
    return;
  }
  int n = s.size();
  int m = (n-1)/2;
  t = "";
  REP(i,1,m+1) {
    t += s[i-1];
  }
  string u = string(t.rbegin(),t.rend());
  if( t != u ) {
    puts(NO.c_str());
    return;
  }
  t = "";
  m = (n+3)/2;
  REP(i,m,n+1) {
    t += s[i-1];
  }
  u = string(t.rbegin(),t.rend());
  if( t != u ) {
    puts(NO.c_str());
    return;
  }
  puts(YES.c_str());
}

int main() {

  cin >> s;
  solve();
  
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
	int n, k;
  cin>>n>>k;
  string s;
  cin>>s;
  bool a1=0;
  if(s[0]=='A') a1=1;
  if(n==1){
    if(a1){
      if(k%2) cout<<"B"<<endl;
      else cout<<"A"<<endl;
    }else{
      if(k%2) cout<<"A"<<endl;
      else cout<<"B"<<endl;
    }
    return 0;
  }
  int ct=1;
  deque<int> deq;
  for(int i=1; i<n; i++){
    if(s[i]!=s[i-1]){
      deq.push_back(ct);
      ct=1;
    }else{
      ct++;
    }
  }
  deq.push_back(ct);
  int i0=-1;
  for(int i=0; i<k; i++){
    if(a1){
      a1=0;
      int x=deq.front();
      deq.pop_front();
      if(x>1){
        deq.push_front(x-1);
        deq.push_front(1);
      }else{
        int y=deq.front();
        deq.pop_front();
        deq.push_front(y+1);
      }
    }else{
      int x=deq.front();
      deq.pop_front();
      if(x>1){
        a1=1;
        deq.push_front(x-1);
      }
      int y=deq.back();
      if((a1 && deq.size()%2==1) || (!a1 && deq.size()%2==0)){
        deq.pop_back();
        deq.push_back(y+1);
      }else{
        deq.push_back(1);
      }
    }
    if(i>=1 && deq.size()==n){
      i0=i;
      break;
    }
  }
  if(i0==-1){
    for(auto x:deq){
      if(a1){
        for(int i=0; i<x; i++) cout<<"A";
        a1=0;
      }else{
        for(int i=0; i<x; i++) cout<<"B";
        a1=1;
      }
    }
    cout<<endl;
  }else{
    if(n%2==0){
      for(int i=0; i<n; i++){
        if(i%2) cout<<"A";
        else cout<<"B";
      }
      cout<<endl;
    }else{
      if((k-1-i0)%2==0){
        for(int i=0; i<n; i++){
          if(i%2) cout<<"B";
          else cout<<"A";
        }
        cout<<endl;
      }else{
        cout<<"B";
        for(int i=1; i<n; i++){
          if(i%2) cout<<"B";
          else cout<<"A";
        }
        cout<<endl;
      }
    }
  }
	return 0;
}


Measured memory_bytes: 1540
import java.util.Scanner;

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

	private void solveB() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long A = sc.nextLong();
		long B = sc.nextLong();
		long C = sc.nextLong();
		long D = sc.nextLong();

		if (judge(N, A, B, C, D)) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}

	private boolean judge(int N, long A, long B, long C, long D) {
		for (int minus = 0; minus < N; minus++) {
			long min = -D * minus + C * (N - 1 - minus);
			long max = -C * minus + D * (N - 1 - minus);
			if (min <= B - A && B - A <= max) {
				return true;
			}
		}
		return false;
	}
}

Measured memory_bytes: 21844
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# # input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

#####segfunc#####
def segfunc(x, y):
    return max(x,y)
#################

#####ide_ele#####
ide_ele = 0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

n,k = inpm()
A = inplm(n)

seg = SegTree([0]*300001, segfunc, ide_ele)

for a in A:
    seg.update(a,seg.query(max(0,a-k),min(300001,a+k+1)) + 1)

print(seg.query(0,300001))

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

int main(){
    string a, b, c;
    cin >> a >> b >> c;
    if(a[a.size() - 1] == b[0] && b[b.size() - 1] == c[0]) puts("YES");
    else puts("NO");
}

Measured memory_bytes: 3612
from collections import defaultdict
n = int(input())
ls = list(map(int,input().strip().split()))
dic1 = defaultdict(int)
dic2 = defaultdict(int)
for i,val in enumerate(ls,1):
    dic1[val+i] += 1
    dic2[val-i] += 1
ans = 0
for key,val in dic2.items():
    if -key in dic1:
        ans += val*dic1[-key]
print(ans)
    


Measured memory_bytes: 53524
import java.util.*;

// ABC 54-D
// https://beta.atcoder.jp/contests/abc054/tasks/abc054_d

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		int Y = in.nextInt();
		
		int a = -1;
		int b = -1;
		int c = -1;
		int rem = Y;
		boolean shouldContinue = true;
		
		for (int i = Y / 10_000; i >= 0 && shouldContinue; i--) {
			rem = Y - i * 10_000;
			if (i > N) {
				continue;
			}
			for (int j = rem / 5_000; j >= 0 && shouldContinue; j--) {
				if (i + j > N) {
					continue;
				}
				rem = Y - i * 10_000 - j * 5_000;
				int k = rem / 1000;
				rem = Y - i * 10_000 - j * 5_000 - k * 1_000;
				if (rem == 0 && i + j + k == N) {
					shouldContinue = false;
					a = i;
					b = j;
					c = k;
				}
			}
		}
		System.out.printf("%d %d %d\n", a, b, c);
	}
}

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

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

    int p[n];
    int che[n];
    int cou = 0;
    for(int i = 0; i < n; i++){
        cin >> p[i];
        if(p[i] == i + 1){
            che[i] = 0;
        }else{
            che[i] = 1;
            cou++;
        }
    }

    int frag = 0;

    for(int i = 0; i < n; i++){
        if(che[i] == 1){
            if(che[p[i] - 1] == 1){
                che[i] = 0;
                che[p[i] - 1] = 0;
                cou -= 2;
                break;
            }else{
                frag = 1;
                break;
            }
        }
    }

    if(frag == 0 && cou == 0){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin >> s;
    bool is_yes = false;
    for (int i=0; i < s.size()-1;i++){
        for (int t = i + 1; t < s.size();t++){
            if(s.at(i)==s.at(t)){
                is_yes = true;
            }               
        }
    }
    if(is_yes){
        cout << "no" << endl;
    }
    else{
        cout << "yes" << endl;
    }
    return 0;
}


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

// int/long:		-2,147,483,648 - 2,147,483,647 (-2^31 <= int < 2^31)
// long/long long:	-9,223,372,036,854,775,808 - 9,223,372,036,854,775,807 (-2^63 <= long < 2^63)

#define	INF (1<<30)
//1,073,741,824
//= 536,870,912 *2

#define	MOD 1000000007
#define MAX 510000

#define	Rep0(i, n)	for (auto i=0; i<n; i++)
#define	Rep1(i, n)	for (auto i=1; i<=n; i++)
#define Sort(P)	sort(P.begin(), P.end())
#define Rev(P)	reverse(P.begin(), P.end())

ll	myPow(ll x, ll n) {
	ll r=1;
	while(n>0)
		if (0==n%2) {
			x *=x;
			x %=MOD;
			n /=2;
		} else {
			r *=x;
			r %=MOD;
			n--;
		}
	return r;
}

ll	MPl(ll x, ll y) {
	return ((x+y)%MOD+MOD)%MOD;
}

ll	MMi(ll x, ll y) {
	return ((x-y)%MOD+MOD)%MOD;
}

ll	MMul(ll x, ll y) {
	return ((x*y)%MOD+MOD)%MOD;
}

// Array
vector<ll> fac(MAX, 0);
vector<ll> finv(MAX, 0);
vector<ll> inv(MAX, 0);

void	DivInit() { // fac, finv, inv
	fac.at(0) = 1;
	fac.at(1) = 1;
	finv.at(0) = 1;
	finv.at(1) = 1;
	inv.at(1) = 1;
	for (int i=2; i<MAX; i++) {
		fac.at(i) = (fac.at(i-1)*i) %MOD;
		inv.at(i) = MOD - (inv.at(MOD%i)*(MOD/i)) %MOD;
		finv.at(i) = (finv.at(i-1)*inv.at(i)) %MOD; 
	}
}

ll	MDiv(ll x, ll y) {
	if (1!=inv.at(1))
		DivInit();
	if (y<0) {
		x=-x;
		y=-y;
	}
	return ((x*inv.at(y))%MOD+MOD)%MOD;
}

ll	MComb(ll N, ll K) {
	if (1!=inv.at(1))
		DivInit();
	if (N<K)
		return 0;
	if ((N<0)||(K<0))
		return 0;
	return (fac.at(N) * ((finv.at(K)*finv.at(N-K)) %MOD)) %MOD;
}

int	main() {
	ll N;
	cin >>N;
	vector<vector<ll>> DP(1000001, vector<ll> (4, 0));
	DP.at(0).at(0)=1;
	DP.at(1).at(0)=8;
	DP.at(1).at(1)=1;// only 0
	DP.at(1).at(2)=1;// only 9
	DP.at(2).at(0)=8*DP.at(1).at(0);
	DP.at(2).at(1)=8*DP.at(1).at(1)+1*DP.at(1).at(0);
	DP.at(2).at(2)=8*DP.at(1).at(2)+1*DP.at(1).at(0);
	DP.at(2).at(3)=10*DP.at(1).at(3)+1*DP.at(1).at(1)+1*DP.at(1).at(2);
	for (auto i=2; i<=1000000; i++) {
		DP.at(i).at(0)=MMul(8, DP.at(i-1).at(0));
		DP.at(i).at(1)=MPl(MMul(9, DP.at(i-1).at(1)), DP.at(i-1).at(0));
		DP.at(i).at(2)=MPl(MMul(9, DP.at(i-1).at(2)), DP.at(i-1).at(0));
		DP.at(i).at(3)=MPl(DP.at(i-1).at(1), DP.at(i-1).at(2));
		DP.at(i).at(3)=MPl(MMul(10, DP.at(i-1).at(3)), DP.at(i).at(3));
	}
	cout <<DP.at(N).at(3) <<endl;
	return 0;
}



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

int main() {
    int a,b;
    cin>>a>>b;
    int arr[b];
    int sum = 0;
    
    for(int i=0;i<b;i++){
        cin>>arr[i];
    }
    
    for(int i=0;i<b;i++){
        sum = sum + arr[i];
    }
    
    if(sum>=a){
        cout<<"Yes";
    }
    else{
        cout<<"No";
    }
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <cstdint>
#include <string>
#include <algorithm>
#include <set>
#include <map>

using namespace std;

int main() {
	int n;
	cin >> n;
	int sum = ((n + 1) * n) / 2;
	set<pair<int,int>> path;
	if(n % 2 == 0) for(int i = 1;i <= n/2;i++) path.insert(make_pair(i,sum/(n/2)-i));
	else for(int i = 1;i <= n/2;i++) path.insert(make_pair(i,sum/((n/2)+1)-i));
	cout << ((n-1)*n/2)-path.size() << endl;
	for(int i = 1;i <= n;i++) for(int j = 1;j < i;j++) if(path.find(make_pair(j,i)) == path.end()) cout << j << " " << i << endl;
#ifdef _DEBUG
	system("pause");
#endif
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define NMAX 2000000
#define AMAX 10000
int n=AMAX;
void CountingSort(unsigned short *,unsigned short *,int);
int main(){
  int i;
  unsigned short *A;
  unsigned short *B;
  int k;
  

  scanf("%d",&k);

  A=malloc(sizeof(short)*k+1);
  B=malloc(sizeof(short)*k+1);
  
  for(i=0;i<k;i++){
    scanf("%hu",&A[i+1]);
  }
  //  printf("ok1\n");
  CountingSort(A,B,k);
  return 0;
}

void CountingSort(unsigned short *A,unsigned short *B,int k){
  int i,j;
  int C[AMAX+1];
  //printf("ok2\n");
  for(i=0;i<=AMAX;i++){
    C[i]=0;
  }
  //printf("ok3\n");
  for(j=0;j<k;j++){
    C[A[j+1]]++;
  }
  //printf("ok4\n");
  for(i=1;i<=AMAX;i++){
    C[i]=C[i]+C[i-1];
  }
  //printf("ok5\n");
  for(j=1;j<=k;j++){
    B[C[A[j]]]=A[j];
    C[A[j]]--;
  }
  //printf("ok6\n");
  for(i=1;i<=k;i++){
    if(i>1)
      printf(" ");
    printf("%d",B[i]);
  }
  printf("\n");
}




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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

#define lf double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

class UnionFind
{
private:
	vector<int> par;
	vector<int> rank; 
public:
	UnionFind(int n): par(n), rank(n)
	{
		for(int i=0; i<n; i++){
			par[i] = i;
			rank[i] = 0;
		}
	}
	int root(int x)
	{
		if (par[x] == x){
			return x;
		}else{
			return par[x] = root(par[x]);
		}
	}
	void unite(int x, int y)
	{
		int rx = root(x);
		int ry = root(y);
		if (rx == ry) return;
		if (rank[rx] > rank[ry]){
			par[ry] = rx;
		}else{
			par[rx] = ry;
			if (rank[rx] == rank[ry]) rank[ry]++;
		}
	}
	int same(int x, int y)
	{
		return root(x) == root(y);
	}
	int countRoot(void){
		int ret=0;
		for(int i=0; i<par.size(); i++){
			//cout << i << ":" <<  root(i) << endl;
			if (i==root(i)) ret++;
		}
		return ret;
	}
};

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n, k; cin>>n>>k;
	vll p(n);
	rep(i, n) cin>>p[i];
	UnionFind uf(n-k+1);
	set<int> S;
	int cnt=0;
	rep(i, n-1){
		if (p[i+1]>p[i]){
			cnt++;
			if (cnt>=k-1) S.ins(i-k+2);
		}else{
			cnt=0;
		}
	}

	for(auto e:S){
		uf.unite(*(S.begin()), e);
	}

	set<int> sel;
	rep(i, k){
		sel.ins(p[i]);
	}
	for(int i=0; i<=n-k-1; i++){
		sel.ins(p[i+k]);
		int mini = *(sel.begin());
		auto it = sel.end(); it--;
		int maxi = *it;

		if (mini==p[i] && maxi==p[i+k]){
			uf.unite(i, i+1);
			sel.erase(sel.begin());
		}else{
			sel.erase(p[i]);
		}
	}

	cout << uf.countRoot() << "\n";
	return 0;
}

Measured memory_bytes: 12800
// ------------------------------------
// Date:2018/ 2/11
// Problem:0002 : DigitNumber 2.cpp
//
// ------------------------------------

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

#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define REP(i,n) FOR(i,0,n)

int main()
{
  int a,b,cnt;
  while (scanf("%d %d", &a, &b) != EOF) {
    cnt = 0;
    a += b;
    while(a>0) {
      a/=10;
      ++cnt;
    }
    printf("%d\n", cnt);
  }
  return 0;
}


Measured memory_bytes: 3080
MOD = 10 ** 9 + 7
N = gets.to_i
A = gets.split.map(&:to_i)
S = [0,0,0]
ans = A.inject(1) do |s, a|
  i = S.index(a)
  c = S.count(a)
  
  break 0 unless i
  
  S[i] += 1 
  (s * c) % MOD
end
puts ans


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

s = input()
s_list1 = list(s)
s_list2 = list(s)
count1 = 0
#count2 = 0

# 最初塗り替えない
s_len = len(s_list1)
pre = int(s_list1.pop(0))
for i in range(s_len-1):
    if pre == int(s_list1.pop(0)):
        pre = 1 - pre
        count1 += 1
    else:
        pre = 1 - pre
if count1 <= s_len//2:
    print(count1)
else:
    print(s_len-count1)

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

string check(int d, int t, int s)
{
	int d1;
	d1= t*s;
	if(d1>=d) return "Yes";

	return "No";
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
	
	int d,t,s;
	cin>>d>>t>>s;
	cout<<check(d,t,s);
	return 0;
}



Measured memory_bytes: 3576
#include<iostream>
#include<string>
using namespace std;
int main(){
	string a;
	cin>>a;
	int b=0,c=0;
	for(int i=0;i<a.size();i++){
		if(a[i]=='A'||a[i]=='C'||a[i]=='T'||a[i]=='G')
			b++;
		else
			b=0;
		if(b>c)
			c=b;
	}
	cout<<c<<endl;
	return 0;
}

Measured memory_bytes: 256
def main():
    n = int(input())
    ds = sorted(list(map(int, input().split())))

    if n % 2 != 0:
        ans = 0
    else:
        mid = n // 2
        ans = ds[mid] - ds[mid-1]
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 14396
N = $stdin.gets.chomp.to_i
A = $stdin.gets.chomp.split(" ").map{ |a| a.to_i }

Max = A.max
Min = A.min

puts 2*N-1
if Max >= Min.abs
  x = A.index(Max)
  N.times{ |i| puts "#{x+1} #{i+1}" }
  (1...N).each{ |i| puts "#{i} #{i+1}" }
else
  x = A.index(Min)
  N.times{ |i| puts "#{x+1} #{i+1}" }
  (1...N).each{ |i| puts "#{N-i+1} #{N-i}" }  
end

Measured memory_bytes: 1788
#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;


const int MOD = 1e9+7 , maxk = 100005 , maxn = 105;
int dp[maxn][maxk],a[maxn];
int k,n;

/*////////////// O(n*k*k) ///////////////////
int solve( int i ,int k )
{
	if( i==n ) return k==0;
	if( dp[i][k]!=-1 )return dp[i][k];
	dp[i][k]=0;
	for(int j=0;j<=min(k,a[i]);j++)
	{
		dp[i][k]+=solve(i+1,k-j);
		dp[i][k]%=MOD;
	}
	return dp[i][k];
	
}
///////////////////////////////////////////*/
int32_t main()
{
	IOS
	memset(dp,0,sizeof(dp));
	
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	
	for(int j=0;j<=k;j++)
	dp[0][j]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=k;j++)
		{
			dp[i][j] = dp[i-1][j] - ( j-a[i]-1 >=0 ? dp[i-1][j-a[i]-1] : 0LL );
			dp[i][j]+= MOD;
			dp[i][j]%= MOD;
		}
		for(int j=1;j<=k;j++)
		{
			dp[i][j]+=dp[i][j-1];
			dp[i][j]%=MOD;
		}
	}
	cout << (dp[n][k] - (k ? dp[n][k-1]:0 ) + MOD)%MOD << endl;
}


Measured memory_bytes: 82304
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

using adjacent_type = vector<int>;
using value_type = int;
vector<adjacent_type> adjacent;
vector<value_type> value;
vector<int> cnt;

void dfs(int vertex, int prev_cnt, int parent=-1)
{
    cnt[vertex] = value[vertex] + prev_cnt;
    
    for (auto& ad : adjacent[vertex])
    {
        if (ad == parent)continue;
        dfs(ad, cnt[vertex], vertex);
    }
}

int main(int argc, const char * argv[]) {
    
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N, Q;
    cin >> N >> Q;
    
    adjacent.resize(N);
    value.resize(N);
    rep(i, N - 1)
    {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        adjacent[a].push_back(b);
        adjacent[b].push_back(a);
    }
    
    rep(i, Q)
    {
        int p, x;
        cin >> p >> x;
        --p;
        value[p] += x;
    }
    
    cnt.resize(N);
    
    dfs(0, 0);
    
    rep(i, N) printf("%d%c", cnt[i], (i==N-1 ? '\n' : ' '));
    
    
    return 0;
}


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

typedef long lint;
typedef long long llint;
typedef pair<int, int> pint;
typedef pair<long long, long long> pllint;

// static const int MAX = 1e6;
// static const int NIL = -1;
// static const llint INF = 1<<21;
// static const llint MOD = 1e9 + 7;

bool compPair(const pint& arg1, const pint& arg2) { return arg1.first > arg2.first; }
template<class T> void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> void chmin(T& a, T b) { if (a > b) { a = b; } }

bool isPrime(int n) {
    int i;

    if (n<2) return false;
    else if (n==2) return true;
    if (n%2==0) return false;
    for(i=3;i*i<=n;i+=2) {
        if(n%i==0) return false;
    }
    return true;
}

int main(void) {
    int q;
    cin >> q;

    vector<int> l(q);
    vector<int> r(q);

    for(int iq=0;iq<q;iq++) {
        cin >> l.at(iq) >> r.at(iq);
    }

    vector<int> sum(100001, 0);
    vector<bool> yn(100001, false);

    int n=100000;
    for(int in=1;in<=n;in++) {
        sum.at(in) = sum.at(in-1);
        if(in%2==1&&isPrime(in)&&isPrime((in+1)/2))  {
            sum.at(in)++;
            yn.at(in) = true;
        }
    }

    int ans;
    for(int iq=0;iq<q;iq++) {
        ans = sum.at(r.at(iq))-sum.at(l.at(iq)-1);
        // if(yn.at(r.at(iq))) ans++;
        // if(yn.at(l.at(iq))) ans++;
        // if(yn.at(r.at(iq))&&yn.at(l.at(iq))) ans--;
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 1792
import collections
import itertools

N = int(input())
S = [input()[0] for _ in range(N)]
A = []
ans = 0

for i in S:
    if i == 'M' or i == 'A' or i == 'R' or i == 'C' or i == 'H':
        A.append(i)
        
if len(A) != 0:       
    C = collections.Counter(A).most_common()
    v,c = zip(*C)
    #print(C)
    #print(c)

    for a,b,c in itertools.combinations(c,3):
        #print(a,b,c)
        ans += a*b*c

print(ans)





Measured memory_bytes: 10788