akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
using namespace std;
using ll = long long;
 
int main()
{
  int N; cin >> N;
  vector<ll> A(N); REP(i, N) cin >> A[i];
 
  int flag = 0, ans = 1;
  for (int i = 1; i < N; ++i) {
    if (flag == 0) {
      if (A[i-1] < A[i]) flag = 1;
      else if (A[i-1] > A[i]) flag = 2;
    } else if (flag == 1) {
      if (A[i-1] > A[i]) {
        flag = 0;
        ans++;
      }
    } else if (flag == 2) {
      if (A[i-1] < A[i]) {
        flag = 0;
        ans++;
      }
    }
  }
 
  cout << ans << endl;
}


Measured memory_bytes: 1024
#!/usr/bin/env ruby

map = {}
n, m = gets.split(' ').map &:to_i
cards = gets.split(' ').map &:to_i
cards.each do |num|
  map[num] ||= 0
  map[num] += 1
end

m.times do
  b, c = gets.split(' ').map &:to_i
  map[c] ||= 0
  map[c] += b
end


sum = 0
card_num = 0
map.keys.sort.reverse.each do |key|
  sum += key * map[key]
  card_num += map[key]
  if card_num >= n
    sum -= key * (card_num - n)
    break
  end
end

puts sum


Measured memory_bytes: 28772
#include <bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#define Y "Yes"
using namespace std;
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m, a, b;

	cin >> n >> m;
	vi ans(n + 1, 0);
	vector<vi> v(n + 1, vi());
	
	while (m--) {
		cin >> a >> b;
		v[a].pb(b);
		v[b].pb(a);
	}
	
	queue<int> q; 
  
    q.push(1);
  
    while (!q.empty()) { 
        int f = q.front(); 
        q.pop(); 
        
        while (!v[f].empty()) { 
        	int e = v[f].back();
        	v[f].pop_back();
            if (ans[e] == 0) { 
                q.push(e);
                ans[e] = f;
            } 
        } 
    } 

	cout << Y << '\n';
	
	for (int i = 2; i <= n; i++)
		cout << ans[i] << '\n';
}

Measured memory_bytes: 10308
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<stdlib.h>
#include<algorithm>
#include<queue>
#define rep(i,s,t) for (i=s;i<=t;i++)
using namespace std;
typedef pair<int,int> PII;
queue <PII> q;
const int maxn = 1000001;
long long depth[maxn];
int l[maxn],r[maxn];
long long dp[maxn];
int qqq[maxn];
long long ans;
long long cnt[maxn];
int i,j,m,n,k,o,p;
int depp;
int tail;
void dfs(int k,int depp)
{

}
int main()
{
//	freopen("1.in","r",stdin);
	while (scanf("%d",&n)!=EOF)
	{
		memset(depth,0,sizeof(depth));
		memset(dp,0,sizeof(dp));
		memset(cnt,0,sizeof(cnt));	
		ans = 0;
		tail = 0;
		queue <PII> q;
		rep(i,1,n-1) scanf("%d%d",&l[i],&r[i]);
		cnt[n] = 1;
		tail = 0;
		q.push(PII(1,0));
		while (!q.empty())
		{
			k = q.front().first;			
			depp = q.front().second;
			q.pop();
			if (k == n)
			{
				ans += depp;
				continue;
			}
			qqq[++tail] = k;
			depth[k] = depp;
			q.push(PII(l[k],depp+1));
			q.push(PII(r[k],depp+1));
		}
		for (i = tail;i>=1;i--)
		{
			k = qqq[i];			
			cnt[k] = cnt[l[k]] + cnt[r[k]];
			dp[k] = max(dp[l[k]] + dp[r[k]],max(dp[l[k]]+depth[k] * cnt[r[k]],dp[r[k]]+depth[k] * cnt[l[k]]));
		}		
		cout << ans - dp[1] << endl;
	}
	fclose(stdin);
	return 0;
}

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

#define fraction() cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define faster() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const long long int infLL = 9000000000000000000;

#define mem(a,b) memset(a, b, sizeof(a) )
#define all(a) (a).begin(),(a).end()
#define mx_int_prime 999999937

const int inf = 2000000000;
const double PI = acos(-1);
const double eps = 1e-9;
typedef long double ld;

#define MOD 1000000007

typedef long long ll;
const int mx=2e5+125;

ll pr[mx],ar[mx],br[mx];

#define PB push_back
#define endl '\n'
#define S second
#define F first

void solve()
{
    string s;
    cin>>s;
    if(s[s.size()-1]=='s')
        cout<<s<<"es"<<endl;
    else
        cout<<s<<"s"<<endl;
}
int main()
{
    faster();
    int tc;
    tc=1;
    while(tc--)
        solve();
    return 0;
}


Measured memory_bytes: 3632
#include<stdio.h>
#include<math.h>
   
typedef struct{
  double x;
  double y;
}koch;
 
void fractal(int,koch,koch);
  
int main(){
   
  koch p1,p2;
  int n;
   
  p1.x = 0;
  p2.x = 100;
  p1.y = 0;
  p2.y = 0;
   
  scanf("%d",&n);
   
  printf("%f %f\n",p1.x,p1.y);
  fractal(n,p1,p2);
  printf("%f %f\n",p2.x,p2.y);
   
  return 0;
}
 
void fractal(int n, koch p1, koch p2){
  
  if(n==0) return;
  koch s,t,u;
   
  s.x = (p2.x-p1.x)/3+p1.x;
  s.y = (p2.y-p1.y)/3+p1.y;
  t.x = 2*(p2.x-p1.x)/3+p1.x;
  t.y = 2*(p2.y-p1.y)/3+p1.y;
  u.x = (t.x-s.x)/2-sqrt(3)/2*(t.y-s.y)+s.x;
  u.y = (t.y-s.y)/2+sqrt(3)/2*(t.x-s.x)+s.y;
   
  fractal(n-1,p1,s);
  printf("%f %f\n",s.x,s.y);
     
  fractal(n-1,s,u);
  printf("%f %f\n",u.x,u.y);
     
  fractal(n-1,u,t);
  printf("%f %f\n",t.x,t.y);
   
  fractal(n-1,t,p2);
}

Measured memory_bytes: 636
;;(declaim (optimize (speed 0) (safety 3) (debug 3)))
#+sbcl (declaim (sb-ext:unmuffle-conditions sb-ext:compiler-note))
(declaim (optimize (speed 3) (safety 0) (debug 0)))

(declaim (type fixnum *len* *max-i* *tuple-n*))
(defvar *len* (read))
(defvar *max-i* (read))
(defvar *tuple-n* (read))

;; a1  a2  a3 ...  an
;;   x1  x2     x(n-1)

(defstruct tuple
  (a -1 :type fixnum)
  (b -1 :type fixnum)
  (c -1 :type fixnum)
  (d -1 :type fixnum))

(declaim (type (simple-array tuple (*)) *tuples*))
(defvar *tuples* (make-array *tuple-n* :element-type 'tuple))

(dotimes (i *tuple-n*)
  (let* ((a (read)) (b (read)) (c (read)) (d (read)))
    (declare (type fixnum a b c d))
    (setf (aref *tuples* i) (make-tuple :a a :b b :c c :d d))))

(defun next-seq (arr)
  (declare (type (simple-array fixnum (*)) arr))
  (loop for i from (1- *len*) downto 0 do
	(cond ((/= (aref arr i) *max-i*)
	       (incf (aref arr i))
	       (loop for j from (1+ i) to (1- *len*) do
		     (setf (aref arr j) (aref arr i)))
	       (return-from next-seq t))
	      ((= i 0)
	       (return-from next-seq nil)))))

(defun calculate-point (arr)
  (declare (type (simple-array fixnum (*)) arr))
  (loop for tu across *tuples* sum
	(if (= (tuple-c tu) (- (aref arr (1- (tuple-b tu)))
			      (aref arr (1- (tuple-a tu)))))
	    (tuple-d tu)
	  0) fixnum))

(declaim (type (simple-array fixnum (*)) *a*))
(defvar *a* (make-array *len*
			:initial-element 1
			:element-type 'fixnum))
(let ((m -1))
  (declare (type fixnum m)) ;; m <= sum[d_i] <= 50*10^5
  (loop
   (let ((p (calculate-point *a*)))
     (declare (type fixnum p))
     (if (> p m)
	 (setf m p)))
   (unless (next-seq *a*)
     (return)))
  (princ m))


Measured memory_bytes: 25256
/* AOJ 0080
 *
 * http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0080
 *
 */

#include <stdio.h>
#include <math.h>


#define DEBUG 0


double f(double x, double q){
    return x - ((x*x*x - q)/(3*x*x));
}

double solve(double q){
    double x;
    x = q/2.0;

    if(DEBUG){
        printf("--x=%f, q=%f\n",x,q);
    }

    while(!(fabsl(x*x*x - q) < (0.00001*q))){
        x = f(x, q);
        if(DEBUG){
            printf("--x=%f, q=%f\n",x,q);
        }
    }
    return x;
}

int main(){
    int q;
    while(scanf("%d", &q)==1 && q!= -1){
        printf("%f\n", solve(q));
    }

    return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int k,x;
    cin >> k >> x;
    
    for(int i=x-k+1;i<=x+k-1;i++){
        cout << i << " ";
        if(i==x+k-1) cout << endl;
    }
    
}


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

int main() {
  int n = 0;
  cin >> n;
  if(n < 10){
    cout << n << endl;
  }else if(n < 100){
    cout << 9 << endl;
  }else if(n < 1000){
    cout << 9 + n - 99 << endl;
  }else if(n < 10000){
    cout << 909 << endl;
  }else if(n < 100000){
    cout << 909 + n - 9999 << endl;
  }else{
    cout << 90909 << endl;
  }
}


Measured memory_bytes: 256
import scala.io.StdIn.{readLine,readInt}

object Main {
  def main(args:Array[String]) = {
    var s = ""
    while({ s = readLine; s.trim } != "0 0 0 0") {
      val n = s.split(" ").map(_.toInt)
      val m = n(0);val t = n(1);val p = n(2); val r = n(3)
      val team = new Array[(Int,Int)](t)
      val tdata = (for(i<-0 until t) yield {
        (for(j<-0 until p) yield {
          (0,0,0) // (??????,??£?§£?????????,?????£?§£??°)
        }).toArray
      }).toArray

      for(i<-0 until r) {
        val s = readLine.split(" ").map(_.toInt)
        val data = tdata(s(1)-1)(s(2)-1)
        tdata(s(1)-1)(s(2)-1) = (if(s(3)==0) s(0) else 0,if(s(3)==0) 1 else 0,if(s(3)!=0) data._3+1 else data._3)
      }
      for(i<-0 until t) {
        val data = tdata(i)
        var success = 0
        var time = 0
        for(j<-0 until data.length) {
          if(data(j)._2 == 1) {
            success += 1
            time += data(j)._1 + data(j)._3*20
          }
        }
        team(i) = (success, time)
      }

      val sorted = team.zipWithIndex.sortWith{(x,y) =>
        if(x._1._1>y._1._1) true
        else if(x._1._1==y._1._1 && x._1._2<y._1._2) true
        else if(x._1._1 == y._1._1 && x._1._2 == y._1._2 && x._2 > y._2) true
        else false
      }
      var prevCnt = sorted(0)._1._1
      var prevTime = sorted(0)._1._2
      print(sorted(0)._2+1)
      for(i<-1 until sorted.length) {
        if(prevCnt == sorted(i)._1._1 && prevTime == sorted(i)._1._2) print("=")
        else print(",")
        print(sorted(i)._2+1)
        prevCnt = sorted(i)._1._1
        prevTime = sorted(i)._1._2
      }
      println
    }
  }
}

Measured memory_bytes: 59568
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    vector<long long> march(5,0);
    cin>>n;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        if(s[0]=='M')march[0]++;
        if(s[0]=='A')march[1]++;
        if(s[0]=='R')march[2]++;
        if(s[0]=='C')march[3]++;
        if(s[0]=='H')march[4]++;
    }
    long long ans=0;
    for(int i=0;i<5;i++){
        for(int j=i+1;j<5;j++){
            for(int k=j+1;k<5;k++){
                ans+=march[i]*march[j]*march[k];
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=2e5+100;
int main(){
	ios;
	string s;
	cin>>s;
	int len=s.size();
	if(s[len-1]=='s') s+="es";
	else s+="s";
	cout<<s<<'\n';
	return 0;
}

Measured memory_bytes: 3688
A,B,H,M = list(map(int,input().split()))
import math
x = abs((30*H + 30*M/60) -6*M)
if x >= 180:
  x = 360-x
c = A*A + B*B - (2*A*B*(math.cos(math.radians(x))))
print(c**0.5)

Measured memory_bytes: 62588
from sys import exit
import math
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

s=input()
t=input()
ans=0
for i in range(len(s)):
    if s[i] != t[i]:
        ans += 1
print(ans)


Measured memory_bytes: 9540
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cmath>

using namespace std;
#define PI 3.1415926535897932384626433832795
#define MOD (1000000007)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
typedef long long ll;
typedef unsigned long long ull;

int main()
{
	ll N, ans = 0;
	int DN;
	bool dec = false;

	cin >> N;
	DN = log10(N) + 1;

	rep(i, DN) {
		if (i == DN - 1) {
			if (dec) ans += N % 10 - 1;
			else ans += N % 10;
		}
		else {
			if (N % 10 != 9) dec = true;
			ans += 9;
		}
		N /= 10;
	}

	cout << ans << endl;

	return 0;
}


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

vector<long long int>D;

int main() {
	long long int N;
	D.push_back( 1 );
	D.push_back( 1 );
	D.push_back( 2 );
	D.push_back( 4 );
	while( cin >> N, N ) {
		while( D.size() <= N ) {
			D.push_back( D[D.size() - 1] + D[D.size() - 2] + D[D.size() - 3] );
		}
		cout << D[N] / 3650 + 1 << endl;
	}
}

Measured memory_bytes: 3036
#include<iostream>
#include<string.h>
using namespace std;
int main(){
 
    string a,b;
    cin>>a>>b;
    for(int i=0;i<a.size();i++){
           rotate(a.begin(), a.begin()+1, a.end());
           if(a==b){
                cout<<"Yes";
                return 0;
           }
    }
     cout<<"No";
}


Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
b=[]
c=[]
for i in range(n):
  b.append(a[i]-(i+1))
  c.append(-(a[i]+i+1))
from collections import defaultdict
#cnt_b=Counter(b)
cnt_c=defaultdict(int)
ans=0
for i in range(n):
  v=cnt_c[b[i]]
  ans+=v
  cnt_c[c[i]]+=1
print(ans)

Measured memory_bytes: 66308
//https://atcoder.jp/contests/dp/tasks/dp_i
#include<bits/stdc++.h>
using namespace std;

int main(int argc, char* argv[]) {
	int n;
	cin >> n;
	vector<double> p (n);
	vector<double> dp (n+1);
	for (int i = 0; i < n; i++) {
		cin >> p[i];
	}
	dp[0]=1;
	for (int i = 0; i < n; i++) {
		for (int j = i+1; j >= 0; j--) {
			dp[j] = ((j==0) ? 0 : dp[j-1]*p[i]) + dp[j]*(1-p[i]);
		}
	}
	double ans = 0;
	for (int i = 0; i <= n; i++) {
		int j = n - i;
		if (i > j) {
			ans += dp[i];
		}
	}
	printf("%.10lf\n", ans);
	return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main()
{
  string s,t;

  cin >> s >> t;
  
  if(s[0] == t[2] && s[2] == t[0] && s[1] == t[1]) cout << "YES" << endl;
  else cout << "NO" << endl;

  return 0;
}

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

const int mod = 1000000007;

struct mint {
    ll x; // typedef long long ll;
    mint(ll x = 0) : x(x % mod) {}

    mint &operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }

    mint &operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }

    mint &operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }

    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }

    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }

    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }

    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(mod - 2);
    }

    mint &operator/=(const mint a) {
        return (*this) *= a.inv();
    }

    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }
};

struct combination {
    vector<mint> fact, ifact;

    combination(int n) : fact(n + 1), ifact(n + 1) {
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
    }

    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * ifact[k] * ifact[n - k];
    }
} comb(100005);

mint f(int n, int k) {
    if (n < 0) return 0;
    // nPk = nCk * k!
    mint res = comb(n, k);
    res *= comb.fact[k];
    return res;
}

mint dp[110][10];

int main() {
    int H, W, K;
    cin >> H >> W >> K;

    dp[0][0] = 1;
    rep(i, H) {
        rep(j, W) {
            rep(bit, 1 << (W - 1)) { // 横線のつながりを全探索する
                // 横線が連続してつながっているパターンは除外する
                bool ok = true;
                rep(l, W - 2) if (((bit >> l) & 1) && ((bit >> (l + 1)) & 1)) ok = false;
                if (!ok) continue;

                if (j >= 1 && ((bit >> (j - 1)) & 1)) { // 左線をたどるパターン
                    dp[i + 1][j - 1] += dp[i][j];
                } else if (j < W - 1 && ((bit >> j) & 1)) { // 右戦をたどるパターン
                    dp[i + 1][j + 1] += dp[i][j];
                } else { // 横線が無いパターン
                    dp[i + 1][j] += dp[i][j];
                }
            }
        }
    }

    cout << dp[H][K - 1].x << endl;
}


Measured memory_bytes: 1792
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <tuple>
#include <cassert>

using namespace std;

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define mp(a,b) make_pair((a), (b))
#define mt(a,b,c) make_tuple((a),(b),(c))

typedef long long ll;

int main(){
    int n,k; cin >> n >> k;
    string s; cin >> s;
    if(s[k-1]=='A') s[k-1] = 'a';
    else if(s[k-1]=='B') s[k-1] = 'b';
    else if(s[k-1]=='C') s[k-1] = 'c';
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
#include <assert.h>
#include <ctype.h>
#include <errno.h>
#include <float.h>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <set>
#include <queue>
#include <limits>
#include <deque>
#include <locale>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <wchar.h>
#include <wctype.h>
#include <algorithm>
#include <bitset>
#include <map>
#include <iomanip>
#include <ios>
#include <iostream>
#include <vector>
#include <cwchar>
#include <cwctype>
#define mp make_pair
#define fs first
#define se second
#define memset(a,t) memset(a,t,sizeof(a))
#define all(v) v.begin(),v.end()
#define eprintf(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define MN 0LL
#define Mx 2000000005
#define Mn -Mx
#define MX 20000000000000005
using namespace std;
int readint(){
	char c;
	while(c=getchar(),(c<'0'||c>'9')&&c!='-');
	bool flag=(c=='-');
	if(flag)c=getchar();
	int x=0;
	while(c>='0'&&c<='9'){
		x=x*10+c-48;
		c=getchar();
	}
	return flag?-x:x;
}
inline string tos(int x){
	string s;
	while(x) s=(char)(x%10+'0')+s,x/=10;
	return s;
}
inline int pt(int a[],int l,int r){
	int p,i,j;
	p=a[l];
	i=l;
	j=r+1;
	for(;;){
		while(a[++i]<p) if(i>=r) break;
		while(a[--j]>p) if(j<=l) break;
		if(i>=j) break;
		else swap(a[i],a[j]);
	}
	if(j==l) return j;
	swap(a[l],a[j]);
	return j;
}
inline void q_sort(int a[],int l,int r){
	int q;
	if(r>l){
		q=pt(a,l,r);
		q_sort(a,l,q-1);
		q_sort(a,q+1,r);
	}
}
int a[111111];
int main(){
	ios_base::sync_with_stdio(false);
	long long lst,i,j,n,ans=0;
	cin>>n;
	for(i=1;i<=n;i++) cin>>a[i];
	lst=1;
	for(;;){
		bool ok=1;
		for(i=lst;i<=n;i++) if(a[i]==i){
			ok=0;
			break;
		}
		if(ok==1) break;
		ans++;
		swap(a[i],a[i+1]);
		lst=i;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 640
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
uf = UnionFind(n)
s = n*(n-1)//2
ans = [0]*m
for i in range(m-1,-1,-1):
  if uf.find(ab[i][0]-1) != uf.find(ab[i][1]-1):
    s -= uf.size(ab[i][0]-1)*uf.size(ab[i][1]-1)
  uf.union(ab[i][0]-1,ab[i][1]-1)
  ans[i-1] = s
ans[m-1] = n*(n-1)//2
for i in ans:
  print(i)

Measured memory_bytes: 34652
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>

#define F first
#define S second
#define vsort(v) sort((v).begin(), (v).end())
#define vrev(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;

int main(int argc, const char * argv[]) {
    int r, g;
    cin >> r >> g;
    cout << 2.0 * g - r  << endl;
    return 0;
}


Measured memory_bytes: 256
N,C,K = map(int,input().split())
T = [int(input()) for i in range(N)]

T.sort()

ans = 0
bus = [T[0]]
for i in range(1,N):
    if T[i]-bus[0] <= K and len(bus) <= C-1:
        bus.append(T[i])
    else:
        bus = [T[i]]
        ans += 1
if bus != []:
    ans += 1
print(ans)



Measured memory_bytes: 7384
<?php

class In {

	private $buf = [];
	private $count = 0;
	private $pointer = 0;

	public function nextLine() {
		$ret = '';
		if($this->hasNext()){
			while($this->hasNext()){
				$ret .= $this->next();
			}
		}else{
			$ret = trim(fgets(STDIN));
		}

		return $ret;
	}

	public function next() {
		if(!$this->hasNext()) {
			$str = trim(fgets(STDIN));
			$this->buf = explode(' ',$str);
			$this->count = count($this->buf);
			$this->pointer = 0;
		}

		return $this->buf[$this->pointer++];
	}

	public function hasNext() {
		return $this->pointer < $this->count;
	}

	public function nextInt() {
		return (int)$this->next();
	}

	public function nextDouble() {
		return (double)$this->next();
	}
}

class Out {
	public function println($str = '') {
		echo $str . PHP_EOL;
	}
}

$in = new In();
$out = new Out();

$S = $in->next();
$L = strlen($S);
for ($i = floor($L/2)-1;$i >= 1;$i--) {
	$a = substr($S,0,$i);
	$b = substr($S,$i,$i);

	if (strcmp($a,$b) === 0) {
		$out->println($i*2);
		break;
	}
}

?>


Measured memory_bytes: 4728
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <functional>
#include <climits>
#include <cstring>
#include <cmath>
#include <numeric>
#include <iomanip>

using namespace std;

#define int long long

#define rep(i, n) for (int i=0;i<(int)n;++i)
#define rep1(i, n) for (int i=1;i<=(int)n;++i)
#define rrep(i, n) for (int i=(int)n-1;i>=0;--i)
#define rrep1(i, n) for (int i=n;i>=1;--i)
#define range(i, l, r) for (int i=l;i<(int)r;++i)
#define rrange(i, l, r) for (int i=(int)r-1;i>=(int)l;--i)
#define unless(a) if(!(a))
#define all(a) begin(a),end(a)
#define fst first
#define scd second
#define PB emplace_back
#define PPB pop_back

using vi=vector<int>;
using pii=pair<int, int>;

bool chmin(int&a,int b){return a>b?(a=b,true):false;}
bool chmax(int&a,int b){return a<b?(a=b,true):false;}
int read(){int a;scanf("%lld",&a);return a;}
constexpr int TEN(int n){return n==0?1:10*TEN(n-1);}

signed main()
{
	string s[2] = {"ABC","ARC"};
	string t;cin>>t;
	if (t==s[0])cout<<s[1]<<endl;
	else cout<<s[0]<<endl;
}



Measured memory_bytes: 3628
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

/*BigInteger
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/rational.hpp>
namespace xxx = boost::multiprecision;
using Bint = xxx::cpp_int;
using Real = xxx::number<xxx::cpp_dec_float<1024>>;
*/

#define int long long
#define pb(x) push_back(x)
#define m0(x) memset((x), 0LL, sizeof(x))
#define mm(x) memset((x), -1LL, sizeof(x))

//container
#define ALL(x) (x).begin(), (x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
#define PERM(c) \
  sort(ALL(c)); \
  for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))

// debug
#define GET_VAR_NAME(variable) #variable
#define test(x) cout << GET_VAR_NAME(x) << " = " << x << endl;

// bit_macro
#define Bit(n) (1LL << (n))
#define Bitset(a, b) (a) |= (1LL << (b))
#define Bitunset(a, b) (a) &= ~(1LL << (b))
#define Bitcheck(a, b) ((((a) >> (b)) & 1LL) == 1LL)
#define Bitcount(a) __builtin_popcountll((a))

//typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

//constant
constexpr int INF = (int)1e18;
constexpr int MOD = (int)1e9 + 7;
constexpr double PI = (double)acos(-1);
constexpr double EPS = (double)1e-10;
constexpr int dx[] = {-1, 0, 0, 1, 0, -1, -1, 1, 1};
constexpr int dy[] = {0, -1, 1, 0, 0, 1, -1, 1, -1};

//
template <typename T>
void chmax(T &a, T b) { a = max(a, b); }
template <typename T>
void chmin(T &a, T b) { a = min(a, b); }
//
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

//
struct Accelerate_Cin {
  Accelerate_Cin() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
  };
};

int H, W;
char a[1010][1010];
int dist[1010][1010];
int ans = 0;
queue<P> q;

void bfs() {
  while (!q.empty()) {
    P p = q.front();
    q.pop();
    int x = p.second, y = p.first;
    for (int i = 0; i < 4; i++) {
      int nx = x + dx[i], ny = y + dy[i];
      if (dist[ny][nx] || a[ny][nx] == '#') continue;
      dist[ny][nx] = dist[y][x] + 1;
      chmax(ans, dist[ny][nx]);
      q.push(P(ny, nx));
    }
  }
}

signed main() {
  cin >> H >> W;
  for (int i = 0; i <= H + 1; i++) {
    for (int j = 0; j <= W + 1; j++) {
      a[i][j] = '#';
    }
  }
  for (int i = 1; i <= H; i++) {
    for (int j = 1; j <= W; j++) {
      cin >> a[i][j];
    }
  }

  for (int i = 1; i <= H; i++) {
    for (int j = 1; j <= W; j++) {
      if (a[i][j] == '#') {
        q.push(P(i, j));
        dist[i][j] = 0;
      }
    }
  }
  bfs();
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 25524
#modN等差数列が必要...根本的に違う
n=int(input())
a=list(map(int, input().split()))
sa= sum(a)
if sa%(n*(n+1)//2):
    print("NO")
    exit()
k=sa//(n*(n+1)//2)###+
b=[a[i]-a[i-1] -k for i in range(n)]

for i in range(n):
    if b[i]%n or b[i]>0:
        print("NO")
        exit()
print("YES")

Measured memory_bytes: 14492
n, m = (int(xi) for xi in input().split())

a = []
diff = []
a0 = 0
if m>0:
    a1 = int(input())
    a.append(a1)
    diff.append(a1+1)

    if m>1:
        for xi in range(m-1):
            a0 = a1
            a1 = int(input())
            a.append(a1)
            diff.append(a1-a0)

    if a1==n-1:
        diff.append(n-a1+1)
    else:
        diff.append(n-a1+1)


else:
    if n==1: diff.append(n+1)
    diff.append(n+2)

# print(diff)
# print(a)

p = [0]
p.append(1)
p.append(1)
for xi in range(3,max(diff)+2):
    add = (p[xi-1]+p[xi-2])%1_000_000_007
    p.append(add)

# print(p)

# print(len(diff))
out = 1
for xi in range(len(diff)):
    out *= p[diff[xi]-1]

print(out% 1_000_000_007 )


Measured memory_bytes: 13508
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define PF push_front
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double
#define pii pair<int,int>
#define pll pair<LL,LL>
#define vi vector<int>
#define vl vector<LL>
#define vii vector<vi>
#define vll vector<vl>

const double pi = 3.14159265358979323846264;
const int mod=1000000007;

int main(){
	int n,m;
    cin>>n>>m;
    vi a(n);
    int sm=0;
    FOR(i,0,n){
        cin>>a[i];
        sm+=a[i];
    }
    int c=0;
    FOR(i,0,n){
        if(a[i]*4*m>=sm){
            c++;
        }
    }
    if(c>=m){
        cout<<"Yes";
    }else{
        cout<<"No";
    }


}


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

int main() {
	// your code goes here
	int n,k;
	cin>>n>>k;
	int dp[n];
	int h[n]; for(int i=0;i<n;i++){cin>>h[i]; dp[i]=INT_MAX;}
	
	dp[0]=0;
	dp[1]=abs(h[1]-h[0]);
	

	for(int i=2;i<n;i++)
	for(int j=i-1;j>=0&&j>=i-k;j--)
	{
	 dp[i]=min(dp[i],dp[j]+abs(h[j]-h[i]));
	 
	}
	cout<<dp[n-1];
	
	
	return 0;
}

Measured memory_bytes: 4372
from collections import Counter
from functools import reduce
# import statistics
import bisect
import copy
import fractions
import math
import pprint
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))
def unite(x, y):
    # それぞれのノードの根を求める
    x = root(x)
    y = root(y)
    if x == y:
        return
    # node[x]の根をyに変更する
    node[x] = y
def same(x,y): return bool(root(x) == root(y))
def root(x):
    if node[x] == x:  # xが根の場合
        return x
    else:
        node[x] = root(node[x])  # 経路圧縮
        return node[x]
def dfs(v):
    # ノードに訪れた
    visited[v] = True
    for v2 in range(n):
        if graph[v][v2] == False:  # そもそもvとv2が辺でつながっていない
            continue
        if visited[v2] == True:  # もう見た
            continue
        dfs(v2)


n, a = II(), LI()
ruiseki = [0] * n
ruiseki[0] = a[0]
allsum = sum(a)
if n == 2:
    print(abs(a[0] - a[1]))
    exit()

for i in range(1, n):
    ruiseki[i] = ruiseki[i-1] + a[i]

mini = INF
for i in range(0, n-1):
    # abs(ruiseki[i] - (allsum - ruiseki[i])
    mini = min(mini, abs(2 * ruiseki[i] - allsum))

print(mini)



Measured memory_bytes: 27084
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for(int i = (a); i < (int)(b); i++)
#define ln(a) cout << (a) << endl
#define debug(a, n) rep(hoge, n) printf("%lld%c", a[hoge], hoge == (n) - 1? '\n' : ' ');
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define INF 1e9
#define LINF 1e18
#define MOD 1000000007
#define EPS 0.00000001

using namespace std;
using ll = long long;
using P = pair<int, int>;
using LP = pair<ll, ll>;

signed main() {
    int h, n;
    cin >> h >> n;
    rep(i, n) {
        int x;
        cin >> x;
        h -= x;
    }
    if(h <= 0) ln("Yes");
    else ln("No");
}



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

const int MAXN = 2000;

int N, K;
vector<int> G[MAXN + 10];
int cc[MAXN + 10];
int level[MAXN + 10];
int L[MAXN + 10], R[MAXN + 10];
int ii = 0;

void dfs(int u, int p = -1) {
   cc[u] = 1;
   L[u] = ++ii;
   level[u] = p == -1 ? 0 : level[p] + 1;

   for(int v : G[u]) {
      if(v == p) continue;
      dfs(v, u);
      cc[u] += cc[v];
   }

   R[u] = ii;
}

int diam() {
   dfs(1);
   int u = max_element(level + 1, level + N + 1) - level;
   dfs(u);
   return *max_element(level + 1, level + N + 1);
}

int calc2(int u, int kk, int p) {
   if(kk == 0) return cc[u];
   int res = 0;
   for(int w : G[u]) {
      if(w == p) continue;
      res += calc2(w, min(K / 2, kk - 1), u);
   }
   return res;
}

int calc(int u, int v) {
   int res = 0, kk = 0, p = -1;
   while(u != v) {
      for(int w : G[u]) {
         if(w == p || (L[w] <= L[v] && L[v] <= R[w])) {
            continue;
         }
         res += calc2(w, min(kk, K - kk), u);
      }
      int w = *find_if(G[u].begin(), G[u].end(), [&](int w) { return w != p && L[w] <= L[v] && L[v] <= R[w]; });
      p = u;
      u = w;
      kk++;
   }
   res += cc[v] - 1;
   return res;
}

int solve() {
   if(diam() <= K) {
      //cerr << "diam <= K\n";
      return 0;
   }
   //cerr << "diam > K\n";
   int mn = N;
   for(int u = 1; u <= N; u++) {
      dfs(u);
      vector<int> diam_v;
      for(int v = 1; v <= N; v++) {
         if(level[v] == K) diam_v.push_back(v);
      }
      //cerr << "u = " << u << "\n";
      for(int v : diam_v) {
         //cerr << "v = " << v << "\n";
         int c = calc(u, v);
         if(c == 0) {
            //cerr << "calc(" << u << ", " << v << ") = " << c << "\n";
         }
         mn = min(mn, c);
      }
   }
   return mn;
}

int main() {
   scanf("%d%d", &N, &K);
   for(int i = 0; i < N-1; i++) {
      int u, v; scanf("%d%d", &u, &v);
      G[u].push_back(v);
      G[v].push_back(u);
   }
   printf("%d\n", solve());
}


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

int main() {
    int n_a = 0, n_b = 0;
    for(int i = 0; i < 3; i++) {
        char c;
        cin >> c;
        if(c == 'A') {
            n_a++;
        }
        else {
            n_b++;
        }
    }    
    if(n_a == 0 || n_b == 0) {
        cout << "No\n";
    }
    else {
        cout << "Yes\n";
    }
    return 0;
}

Measured memory_bytes: 3600
import java.util.Scanner;
public class Main
{
    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    int n =s.length();
    char s1 =s.charAt(2);
    char s2 =s.charAt(3);
    char s3 =s.charAt(4);
    char s4 =s.charAt(5);
    if(n==6&&s1==s2&&s3==s4){
        System.out.println("Yes");
    }else{
        System.out.println("No");
    }
}
}

Measured memory_bytes: 22740
#include <iostream>      // cout, endl, cin
#include <string>        // string, to_string, stoi
#include <vector>        // vector
#include <algorithm>     // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility>       // pair, make_pair
#include <tuple>         // tuple, make_tuple
#include <cstdint>       // int64_t, int*_t
#include <cstdio>        // printf
#include <map>           // map
#include <queue>         // queue, priority_queue
#include <set>           // set
#include <stack>         // stack
#include <deque>         // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset>        // bitset
#include <bits/stdc++.h> // isupper, islower, isdigit, toupper, tolower
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> Pl;
typedef pair<int, int> P;

int main()
{
  ll N , ans;
  ll INF = 200001;
  // INF = 5;
  cin >> N;
  vector<ll> A(N);
  vector<ll> B(INF);
  //ボールを覗いていない計算
  vector<ll> Before(INF);
  //ボールを一つ覗いた計算
  vector<ll> After(INF);
  vector<ll> ANS(N);
  rep(i, N)
  {
    cin >> A.at(i);
    B.at(A.at(i))++;
  }
  // rep(i, N)
  // {
  //   cout << i << "Number of " << B.at(i) << endl;
  // }
  // 7 * 6 /2 = 21
  // 6 * 5 /2 = 15
  //K番目を抜く
  rep(i, INF)
  {
    Before.at(i) = (B.at(i) * (B.at(i) - 1)) / 2;
    if (B.at(i) - 1 > 0 && B.at(i) - 2 > 0)
    {
      After.at(i) = (((B.at(i) - 1) * (B.at(i) - 2)) / 2);
      // cout << (((B.at(i) - 1) * (B.at(i) - 2)) / 2) << endl;
    }
    else
    {
      After.at(i) = 0;
    }
  }
  //K番目を抜く
  rep(i, INF)
  {
    ans += Before.at(i);
  }

  rep(i, N)
  {

    cout << ans - Before.at(A.at(i)) + After.at(A.at(i)) << endl;
  }



  return 0;
}


Measured memory_bytes: 10368
N = int(input())
Sum = 0
Min = 119
for i in range(N):
    s = int(input())
    if s%10 != 0:
        Min = min(Min,s)
    Sum += s
if Sum%10 == 0:
    if Min == 119:
        print(0)
    else:
        print(Sum-Min)
else:
    print(Sum)

Measured memory_bytes: 3060
#include<string>
#include<cctype>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn = 100 + 8;

int n;
int bubbleSort(int a[])
{
    int num = 0;
    bool flag = 1;
    for(int i = 0; flag; ++i){
        flag = 0;
        for(int j = n-1; j >= i+1; j--){
            if(a[j] < a[j-1]){
                swap(a[j],a[j-1]);
                flag = 1;
                num++;
            }
        }
    }

    return num;
}
int a[maxn];
int main()
{
    fill(a,a+n,0);
    scanf("%d",&n);
    for(int i = 0; i < n; ++i){
        scanf("%d",&a[i]);
    }
    int ans = bubbleSort(a);

    for(int i = 0; i < n; ++i){
        printf("%s%d",i == 0 ? "":" ",a[i]);
    }
    printf("\n%d\n",ans);
}

Measured memory_bytes: 3196
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
#include<limits.h>
#include<unordered_map>
#include<unordered_set>
#include<deque>
#include<cstdio>
typedef long long int ll;
#define rep(i,n) for(int i=0;i<n;++i)
#define ALL(x) x.begin(),x.end();
const int INF = 1LL << 30;
const ll LLINF = 1LL << 60;
using namespace std;
int v[2][200],n;
int main() {
	cin >> n;
	rep(i, 2)rep(j, n) {
		cin >> v[i][j];
		if (j != 0)v[i][j] += v[i][j - 1];
	}
	int ans = 0;
	rep(i, n) {
		ans = max(ans, v[0][i] + v[1][n - 1] - v[1][i-1]);
	}
	cout << ans << endl;
	return 0;
}

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

int main(){
//終了時間が最も早いものを選ぶ
  int n;
  cin >> n;
  pair<int ,int> itv[n];
  for(int i=0;i<n;i++){
  int d,e;
    cin >> d >> e;
    itv[i].first = d+e;
    itv[i].second = d-e;
  }
  
  sort(itv, itv+n);
  
  int ans=0;
  int t=-2000000001;
  for(int i=0;i<n;i++){
   if(t<=itv[i].second){
     ans++;
     t=itv[i].first;
   }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1024
path_list = 3.times.map { gets.split(' ').map(&:to_i) }
edge_to_count = Hash.new(0)
path_list.each do |(a, b)|
  edge_to_count[a] += 1
  edge_to_count[b] += 1
end

ans = edge_to_count.keys.size == 4 && edge_to_count.values.max < 3
puts(ans ? 'YES': 'NO')


Measured memory_bytes: 3836
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cmath>

using namespace std;
using ll = long long;
using ull = unsigned long long;

constexpr ll LLINF {1001002003004005006};//ll = 9*LLINF
constexpr int INTINF {1000000000};//int = 2*INTINF

#define  rep(i,n)   for(int i = 0; i < (n); ++i)
#define rrep(i,n)   for(int i = 1; i <= (n); ++i)
#define drep(i,n)   for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for(int i = s; i < t;  ++i)

template<typename T>
void maxs(T& x, T&& y) {
  x=std::max(x,y);
}
template<typename T>
void maxs(T& x, T& y) {
  x=std::max(x,y);
}

template<typename T>
void mins(T& x, T&& y) {
  x=std::min(x,y);
}
template<typename T>
void mins(T& x, T& y) {
  x=std::min(x,y);
}

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

  int N;
  cin >> N;
  vector<char> S(N);
  rep(i, N) cin >> S[i];

  vector<int> X(N+1, 0);
  rep(i, N) {
    X[i+1] = X[i] + ((S[i]=='E')?0:1);
  }
  vector<int> Y(N+1, 0);
  drep(i, N) {
    Y[i] = Y[i+1] + ((S[i]=='W')?0:1);
  }
  int answer {X[N]+Y[N]};
  rep(i, N) {
    mins(answer, X[i]+Y[i]);
  }
  cout << answer << '\n';
}


Measured memory_bytes: 2944
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
typedef long long int ll;
#define forn for(int i=0;i<n;i++) 
#define kek cout<<"\n"
#define press_F_to_pay_respect ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define forn for(int i=0;i<n;i++) 
#define form for(int j=0;j<n;j++) 
#define fora(i,a,b) for(int i = a; i < (b); i++)
#define pb push_back 
#define pob pop_back()
#define mp make_pair 
#define sc second 
#define f first 
#define all(v) ((v).begin()), ((v).end()) 
#define pob pop_back() 
#define halt {cout<<-1; return 0;}
const ll MOD = 1e9 + 7;
const int N = 200005;
const ll INF = 1e8;
const ll MOD1=998244353;
using namespace std;
bool comp(string a, string b)
{
          return a.size()<b.size();
}
int main()
{
#if defined(_DEBUG)
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
  press_F_to_pay_respect;
 // string al="abcdefghijklmnopqrstuvwxyz";
int r;
cin>>r;
 cout << fixed << setprecision(12) <<  (double) 2*M_PI*r;

 
 
 return 0;
 
 
 
  

}

Measured memory_bytes: 3808
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <iomanip>
#include <queue>
#include <numeric>
#define repl(i, l, r) for (ll i = l; i < r; i++)
#define rep(i, n) repl(i, 0, n)

using namespace std;
using ll = long long;


int main() {

    ll N, M;

    cin >> N >> M;

    vector<bool> L(N + 1);
    vector<bool> R(N + 1);
    ll a, b;

    rep(i, M){
        cin >> a >> b;
        if (a == 1 || b == 1) {
            L[max(a, b)] = true;
        }
        if (a == N || b == N) {
            R[min(a, b)] = true;
        }
    }

    bool ans = false;

    rep(i, N + 1) {
        if (L[i] && R[i]) {
            ans = true;
        }
    }

    if (ans) {
        cout << "POSSIBLE";
    }
    else {
        cout << "IMPOSSIBLE";
    }

	return 0;
}


Measured memory_bytes: 3064
n, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort(key = lambda x:x[0])
sum = 0
for i in range(n):
	sum += ab[i][1]
	if k<=sum:
		print(ab[i][0])
		break

Measured memory_bytes: 29144
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <array>
#include <list>
#include <set>
#include <map>
#include <cmath>
using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); i++);

typedef long long ll;

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;}

int main() {
    int s;
    cin >> s;
    set<int> st;

    st.insert(s);
    for (int i = 0; i < 1e9; i++) {
        if (s % 2 == 0) {
            s = s / 2;
        } else {
            s = 3 * s + 1;
        }
        if (st.count(s)) {
            cout << i+2 << endl;
            return 0;
        }
        st.insert(s);
    }
    return 0;
}


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

#define INF 1 << 29
#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)

using namespace std;

typedef pair<int,int> pii;
typedef long long int ll;

void gen_sosuu(int sosuu[]){
  REP(i,100010){
    sosuu[i] = true;
  }
  sosuu[0] = false;
  sosuu[1] = false;
  sosuu[2] = true;
  FOR(i,2,sqrt(100000)+1){
    if(sosuu[i] == false) continue;
    for(int j = 2; i*j<=100000;j++){
      //printf("%d %d %d\n",i*j,i,j);
      sosuu[i*j] =false;
    }
  }
}

int n;
vector<ll> a,b;
vector<int> ans;
int main(){
  cin >> n;
  REP(i,n){
    int x;
    cin >> x;
    a.push_back(x);
  }
  REP(i,n){
    int x;
    cin >> x;
    b.push_back(x);
  }
  sort(b.begin(),b.end());
  ll mod = 1ll;
  REP(i,30){
    ll cnt = 0;
    mod*=2;
    vector<ll> c = b;
    REP(i,n) c[i] %= mod;
    sort(c.begin(),c.end());
    REP(j,n){
      ll T = mod/2;
      ll tmp = a[j] % mod;
      cnt += (lower_bound(c.begin(),c.end(),2*T-tmp)- lower_bound(c.begin(),c.end(),T-tmp));
      cnt += (lower_bound(c.begin(),c.end(),4*T-tmp)- lower_bound(c.begin(),c.end(),3*T-tmp));
    }
    if(cnt%2==1) ans.push_back(1);
    else ans.push_back(0);
  }
  //reverse(ans.begin(),ans.end());
  ll sum = 0;
  ll k = 1;
  REP(i,ans.size()){
    //printf("%d\n",ans[i]);
    sum += ans[i]*k;
    k*=2;
  }
  cout << sum <<endl;

}


Measured memory_bytes: 5104
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 1e6+10;
char s[SIZE];
int main(){
    RS(s);
    int n=LEN(s);
    int cnt[26]={};
    REP(i,n)cnt[s[i]-'a']++;
    bool suc=0;
    REPP(i,1,n-1){
        if(s[i-1]!=s[i+1])suc=1;
    }
    if(!suc)return 0*puts("Second");
    int ma=0;
    REP(i,26)ma=max(ma,cnt[i]);
    if(s[0]==s[n-1]){
        if(n%2==1)puts("Second");
        else puts("First");
    }
    else{
        if(n%2==1)puts("First");
        else puts("Second");
    }
    return 0;
}


Measured memory_bytes: 384
#include <stdio.h>
int main(void)


{
	int S, h, m, s, amari;
	scanf("%d", &S);
	h = S / 3600;
	amari = S % 3600;
	m = amari / 60;
	s = amari % 60;
	printf("%d:%d:%d\n", h,m,s);
	return 0;
}

Measured memory_bytes: 592
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
#include<bits/stdc++.h>

#define sync ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi 3.1415926535897932
#define eps 0.000001

//#define int ll

using namespace std;

int t[400005];

void update(int v, int vl, int vr, int pos, int el)
{
    if (vl == vr)
    {
        t[v] = el;
        return ;
    }
    int mid = (vl + vr) >> 1;
    if (pos <= mid)
    {
        update(v + v, vl, mid, pos, el);
    }
    else
    {
        update(v + v + 1, mid + 1, vr, pos, el);
    }
    t[v] = max(t[v + v], t[v + v + 1]);
}

int Max(int v, int vl, int vr, int  l, int r)
{
    if (l > vr || vl > r)
    {
        return 0;
    }
    if (vl >= l && vr <= r)
    {
        return t[v];
    }
    int mid = (vl + vr) >> 1;
    return max(Max(v + v, vl, mid, l, r), Max(v + v + 1, mid + 1, vr, l, r));
}

int main()
{
    int n;
    cin >> n;
    vector<int> x(n);
    for(int i = 0;i < n;++i)
    {
        cin >> x[i];
    }

    vector<int> cnt(100005);
    vector<int> a(100005), b(100005);
    int cur = 0, num = 1;
    for(int i = 0;i < n;i += 2)
    {
        cnt[x[i]]++;
        a[x[i]] = cnt[x[i]];
    }

    for(int i = 0;i < 100005;i++)
        cnt[i] = 0;

    cur = 0;
    for(int i = 1;i < n;i += 2)
    {
        cnt[x[i]]++;
        b[x[i]] = cnt[x[i]];
    }

    for(int i = 1;i <= 100000;++i)
    {
        update(1, 0, 99999, i - 1, b[i]);
    }
    int ans = 1e9;
    for(int i = 1;i <= 100000;++i)
    {
        update(1, 0, 99999, i - 1, 0);
        ans = min(ans, n - a[i] - Max(1, 0, 99999, 0, 99999));
        update(1, 0, 99999, i - 1, b[i]);
    }
    for(int i = 1;i <= 100000;++i)
    {
        update(1, 0, 99999, i - 1, a[i]);
    }
    for(int i = 1;i <= 100000;++i)
    {
        update(1, 0, 99999, i - 1, 0);
        ans = min(ans, n - b[i] - Max(1, 0, 99999, 0, 99999));
        update(1, 0, 99999, i - 1, a[i]);
    }

    cout << ans;

    return 0;
}






Measured memory_bytes: 2816