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

const int N = 100010;

typedef std::pair <int, bool> pib;
std::vector <pib> e[N];

int col[N], fa[N], cnt[10][N];

void dfs(int u){
	for (auto v : e[u]){
		int pre = col[v.first];
		if (col[u] == 4){
			col[v.first] = 4;
		}
		else{
			int x = v.second ? col[u] - 1 : (col[u] + 1) % 3;
			x += !x ? 3 : 0;
			if (col[v.first]){
				col[v.first] = col[v.first] == x ? x : 4;
			}
			else{
				col[v.first] = x;
			}
		}
		if (!pre) dfs(v.first);
	}
}

int find(int u){
	if (fa[u] == u) return u;
	fa[u] = find(fa[u]);
	for (int i = 0; i <= 4; ++ i){
		cnt[i][u] = cnt[i][fa[u]];
	}
	return fa[u];
}

void unite(int u, int v){
	int _u = find(u), _v = find(v);
	if (_u == _v) return;
	for (int i = 0; i <= 4; ++ i){
		cnt[i][_v] += cnt[i][_u];
	}
	fa[_u] = _v;
}

int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 0, u, v; i < m; ++ i){
		scanf("%d%d", &u, &v);
		e[u].push_back({v, false});
		e[v].push_back({u, true});
	}
	for (int i = 1; i <= n; ++ i){
		if (!col[i]){
			col[i] = 1;
			dfs(i);
		}
	}
	for (int i = 1; i <= n; ++ i){
		fa[i] = i;
		cnt[col[i]][i] = 1;
		cnt[0][i] = e[i].size();
	}
	for (int i = 1; i <= n; ++ i){
		for (auto v : e[i]){
			unite(i, v.first);
		}
	}
	long long ans = 0;
	for (int i = 1; i <= n; ++ i){
		if (find(i) != i) continue;
		if (cnt[4][i]){
			int x = cnt[1][i] + cnt[2][i] + cnt[3][i] + cnt[4][i];
			ans += 1ll * x * x;
		}
		else{
			if (!cnt[1][i] || !cnt[2][i] || !cnt[3][i]){
				ans += cnt[0][i] >> 1;
			}
			else{
				for (int j = 1; j <= 3; ++ j){
					ans += 1ll * cnt[j][i] * cnt[j % 3 + 1][i];
				}
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 14976
import java.util.Scanner;
 
class Main {
    Scanner sc = new Scanner(System.in);
 
    public void run() {
        while(true){
 
            String s=sc.nextLine();
            if("-".equals(s))break;
            int count=sc.nextInt();
            for(int i=0;i<count;i++){
                int index=sc.nextInt();
                s=s.substring(index)+s.substring(0,index);
            }sc.nextLine();
            ln(s);
        }
    }
 
    public static void main(String[] args) {
        new Main().run();
    }
 
    public static void pr(Object o) {
        System.out.print(o);
    }
 
    public static void ln(Object o) {
        System.out.println(o);
    }
 
    public static void ln() {
        System.out.println();
    }
}


Measured memory_bytes: 26448
# 25:27
import numpy as np
from numba import njit


@njit("i8(i8[:],i8)")
def solve(K, D):
    N = len(K)
    MOD = 1_000_000_007
    dp = np.zeros((N + 1, 2, D), dtype=np.int64)
    dp[0][0][0] = 1
    for i in range(N):
        for is_less in range(2):
            for k in range(D):
                for l in range(10 if is_less else K[i] + 1):
                    is_less_ = is_less or l < K[i]
                    k_ = (k + l) % D
                    dp[i + 1][is_less_][k_] += dp[i][is_less][k]
                    dp[i + 1][is_less_][k_] %= MOD
    return (dp[N][0][0] + dp[N][1][0] - 1) % MOD


print(solve(np.array(list(map(int, input()))), int(input())))


Measured memory_bytes: 129008
#include<bits/stdc++.h>
using namespace std;
int main()
{
	  long long h;
	  long long attacks = 0;
	  long long curr=1;
	  
	  cin >> h;
	  
	  //cout <<"h :  " << h << endl;
	  
	  while(h)
	  {
	  	h/=2;
	  	attacks += curr;
	  	curr*=2;
	  }
	  
	  cout << attacks;
	  return 0;
}

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

int main() {
  vector<int> cities;
  int n, m, a, b;
  cin >> n >> m;
  for (int i=0; i<n; i++) {
    cities.push_back(0);
  }
  for (int i=0; i<m; i++) {
    cin >> a >> b;
    cities[a-1]++;
    cities[b-1]++;
  }
  for (auto i : cities) cout << i << endl;
  return 0;
}

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

class Program
{
  static void Main()
  {
    var nums = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
    var n5 = 0;
    var n7 = 0;
    foreach (var i in nums)
    {
      if (i == 5) n5++;
      if (i == 7) n7++;
    }
    if (n5 == 2 && n7 == 1) Console.WriteLine("YES");
    else Console.WriteLine("NO");
  }
}

Measured memory_bytes: 11220
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <iterator>
#include <algorithm>
#include <map>
#include <string.h>
#include <vector>
#include <cmath>
#include <deque>
#include <iomanip>
#include <regex>

using namespace std;
#define range(a) a.begin(), a.end()
#define rep(i, c) for(int i = 0; i < (int)c; i++)
typedef long long ll;

template <typename T> ostream& operator<<(ostream& out, vector<T> &v){
  for (int i = 0; i < (int)v.size(); i++) {
    out<<v[i]<<' ';
  }
  return out;
}

const long long INF = 1e18;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);


  // string s("hello william and me");
  // s.replace(s.find("william"), sizeof("william") - 1, "Somename");
  // cout << s << endl;

  ll N;
      cin >> N;
      bool a = false;
      ll ans = 1;
      while(N--) {
          ll b;
          cin >> b;
          if(b == 0) {
              cout << 0 << endl;
              return 0;
          }
          if(INF / b < ans) a = true;
          ans *= b;
      }
      if(a) ans = -1;
      if(ans > INF) ans = -1;
      cout << ans << endl;
      return 0;






  return 0;
}


Measured memory_bytes: 3672
package main

import (
	"fmt"
)

func main() {
	var r int
	fmt.Scan(&r)
	switch {
	case r < 1200:
		fmt.Println("ABC")
	case r < 2800:
		fmt.Println("ARC")
	default:
		fmt.Println("AGC")
	}

}


Measured memory_bytes: 1772
#include <stdio.h>
int main ()
{
  int a,n,i,MAX=-2147483648,min=2147483647;
  long long t=0;
  scanf("%d",&n);
 
  for(i=1;i<=n;i++){
    scanf("%d",&a);
 
    t+=a; 
 
    if( MAX<a)
      MAX=a;
    if( min>a)
      min=a;
  }
  printf("%d ",min);
  printf("%d ",MAX);
  printf("%lld\n",t);
  return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (long long i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PL = pair<long long, long long>;
using Pxy = pair<double, double>;
using T = tuple<int, int, bool>;
const int INF = 1001001007;
const int mod = 1000000007;
const int MOD = 998244353;
const ll inf = 1e18;
template <typename AT>
void printvec(vector<AT> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

void yes(){
    cout << "Yes" << endl;
}

void no (){
    cout << "No" << endl;
}

ll cel (ll a, ll b){
    if (a % b == 0) return a / b;
    else return a / b + 1;
}

ll gcds(ll a, ll b){
    ll c = a % b;
    while (c != 0){
        a = b;
        b = c;
        c = a % b;
    }
    return b;
}

int main() {
    int a, b, c; cin >> a >> b >> c;
    if (c > 0) cout << a * b / 2 << endl;
}

Measured memory_bytes: 3612
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
using namespace std;

int main(){

    int n;
    cin >> n;

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

    int ans = 0;
    int same = 1;

    for(int i = 0; i < n; i++){
        //cout << "i:" << i << endl;
        for(int j = i + 1; j < n; j++){
            if(v[i] != v[j]){
                //cout << i << j << same << endl;
                i = j - 1;
                ans += same / 2;
                same = 1;
                break;
            }
            else same ++;

            if(j == n - 1){
                ans += same / 2;
                i = j;
            }
        }
    }

    cout << ans << endl;

}

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args ) throws Exception {
    Scanner sc = new Scanner(System.in);
    int X = sc.nextInt();
    int upThousand = X / 500;
    int upFive = (X -= 500 * (upThousand)) / 5;
    System.out.println((upThousand * 1000 ) + (upFive * 5));
  }
 }

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

int main(){
    int n,min,max;
    long long sum;
    int x[10000];
    cin>>n;
    cin>>x[0];
    min=x[0];
    max=x[0];
    sum=x[0];
    for(int i=1;i<n;i++){
        cin>>x[i];
        sum+=x[i];
        if(min>x[i]){
            min=x[i];
        }
        if(max<x[i]){
            max=x[i];
        }
    }
    cout<<min<<" "<<max<<" "<<sum<<endl;
    return 0;
}


Measured memory_bytes: 3116
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m,x = li()
a = list(li())
small = 0
large = 0
for ai in a:
    if ai < x:
        small += 1
    else:
        large += 1

print(min(small, large))

Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include <math.h>
#include <iomanip>

using namespace std;
int main(){
    const double pi = acos(-1.0);
    double a, b, c, sinc, s, l, h, ll;
    cin >> a >> b >> c;
    cout<<fixed<<setprecision(12);
    c *= pi/180;
    s = 0.5*a*b*sin(c);
    ll = a*a + b*b - 2*a*b*cos(c);
    l = sqrt(ll);
    h = b*sin(c);
    cout << s << "\n" << a + b +l << "\n" << h <<"\n";
   
	return 0;
}




Measured memory_bytes: 3532
#include <cstdio>
#include <algorithm>
typedef long long int64;
static const int MAXN = 1e5 + 4;

int n, x, a[MAXN];
int64 ans = 0;

int main()
{
    scanf("%d%d", &n, &x);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);

    for (int i = 1; i < n; ++i) {
        int rm = std::max(0, std::min(a[i], a[i] + a[i - 1] - x));
        ans += rm; a[i] -= rm;
        if (a[i - 1] > x) ans += (a[i - 1] - x), a[i - 1] = x;
    }

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


Measured memory_bytes: 512
#include <iostream>
#include <vector>
using namespace std;
#define ll long long
int main () {
    vector<ll> x, y;
    ll N, A=0, B=0;
    cin >> N;
    for (ll i=0;i<N;i++){
        ll a;
        cin >> a;
        x.push_back(a);
    }
    for (ll i=0;i<N;i++){
        ll a;
        cin >> a;
        y.push_back(a);
    }
    for (ll i=0;i<N;i++){
        ll a=x[i], b=y[i];
        if (a>b)
            B+=a-b;
        else if (b>a){
            if ((b-a)%2==1){
                A+=(b-a+1)/2;
                B++;
            }
            else
                A+=(b-a)/2;
        }
    }
    A>=B ? cout << "Yes" : cout << "No";
    return 0;
}

Measured memory_bytes: 512
#include<stdio.h>
#include<string.h>
int main(void)
{
	int i,n,cnt,runner,tokuten;
	char str[10];
	scanf("%d",&n);
	for(i=1;i<=n;i++) {
		cnt=0;
		tokuten=0;
		runner=0;
		while(cnt != 3) {
			scanf("%s",str);
			if(strcmp(str, "OUT" )==0) {
				cnt++;
			}
			else if(strcmp(str, "HIT" )==0) {
				runner++;
			}
			else if(strcmp(str, "HOMERUN" )==0) {
				tokuten=tokuten+(runner+1);
				runner=0;
			}
			if(runner>3) {
				runner--;
				tokuten++;
			}
		}
		printf("%d\n",tokuten);
	}
	return 0;
}

Measured memory_bytes: 596
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
signed main()
{
	int A, B;
	cin >> A >> B;
	if (B % A == 0)cout << A + B;
	else cout << B - A;
}

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

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

    int ans = 0;
    for (int i = 0; i < N; i++)
    {
        while(i + 1 < N && A[i] == A[i+1])
        {
            i++;
        }
        if (i + 1 < N && A[i] < A[i+1])
        {
            while(i + 1 < N && A[i] <= A[i+1])
            {
                i++;
            }
        }

        else if (i + 1 < N && A[i] > A[i+1])
        {
            while(i + 1 < N && A[i] >= A[i+1])
            {
                i++;
            }
        }
        ans++;

    }

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

Measured memory_bytes: 764
#include<cstdio>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#define ll long long
using namespace std;
int sum=0;
map<int,int> mp;
int main()
{
   //freopen("data.in","r",stdin);
   //freopen("data.out,"w",stdout);
   int num;
   cin>>num;
   for(int i=1;i<=num;i++)
   {
   	   int t;cin>>t;
   	   if(mp[t])
   	   {
   	   	  mp[t]=0;
   	   	  sum--;
	   }
	   else
	   {
	   	  mp[t]=1;
	   	  sum++;
	   }
	   
   }
   cout<<sum<<endl;
   return 0;
}


Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
int main () {
    int a,b;
    cin>>a>>b;
    if(a%3==0 || b%3==0 ||(a+b)%3==0)
    cout<<"Possible"<<endl;
    else
     cout<<"Impossible"<<endl;
	return 0;
}

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

int main(){
    int n;

    while(scanf("%d",&n)==1){
        map<int, bool>mp;

        while(n--){
            int v;
            scanf("%d",&v);
            mp[v] = true;
        }

        printf("%d\n",mp.size());
    }

    return 0;
}



Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Program
{
    const int MOD = 1000000007;
    int height;
    int width;
    static void Main(string[] args)
    {
        new Program().Solve();
    }

    void Solve()
    {
        Scanner cin = new Scanner();
        string s = cin.Next();
        Dictionary<char, int> count = new Dictionary<char, int>();
        foreach (var item in s)
        {
            if (count.Select(e => e.Key).Contains(item))
            {
                count[item]++;
            }
            else
            {
                count.Add(item, 1);
            }
        }
        if (count.Count() == 2 && count.Select(e => e.Value).Any(e => e == 2))
        {
            Console.WriteLine("Yes");
        }
        else
        {
            Console.WriteLine("No");
        }
    }
    bool IsInside(int row, int column)
    {
        if (0 <= row && row < height && 0 <= column && column < width)
        {
            return true;
        }
        return false;
    }

}


class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string Next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return Next();
        i = 0;
        return s[i++];
    }

    public int NextInt()
    {
        return int.Parse(Next());
    }

    public char[] ArrayChar()
    {
        return Next().ToCharArray();
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = NextInt() + add;
        }
        return Array;
    }

    public long NextLong()
    {
        return long.Parse(Next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = NextLong() + add;
        }
        return Array;
    }

    public double NextDouble()
    {
        return double.Parse(Next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = NextDouble() + add;
        }
        return Array;
    }
}


Measured memory_bytes: 13408
def examA():
    N = I()
    A = LI()
    ans = "YES"
    cur = 0
    for a in A:
        if a%2==1:
            cur +=1
    if cur%2==1:
        ans = "NO"
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    ans = "YES"
    sumA = sum(A)
    oneA = (1+N)*N//2
    if sumA%oneA!=0:
        ans = "NO"
    ope = sumA//oneA
    #各Aについて何回始点としたか二分探索
    cur = 0
    for i in range(N):
        now = ope - (A[i]-A[i-1])
        if now%N!=0 or now<0:
#            print(now,i)
            ans = "NO"
            break
        cur += now//N
    if cur!=ope:
        ans = "NO"
    print(ans)
    return

def examC():
    N = I()
    A = LI()
    V = [[]for _ in range(N)]
    for i in range(N-1):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
    s = -1
    for i,v in enumerate(V):
        if len(v)>1:
            s = i
            break
    if s==-1:
        if A[0]==A[1]:
            print("YES")
        else:
            print("NO")
        return
    def dfs(s,p):
        flag = 1
        rep = 0
        maxA = 0
        for v in V[s]:
            if v==p:
                continue
            cur,next = dfs(v,s)
            if maxA<cur:
                maxA = cur
            rep += cur
            flag *= next
        if len(V[s])==1:
            return A[s],flag
        if (rep+1)//2>A[s] or rep<A[s] or maxA>A[s]:
            flag = 0
        #print(s,rep)
        rep -= (rep-A[s])*2
        return rep,flag
    rep,flag = dfs(s,-1)
    if rep!=0:
        flag = 0
    if flag:
        print("YES")
    else:
        print("NO")
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<60
_ep = 10**(-16)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()


Measured memory_bytes: 124592
#include<iostream>
#include<fstream>
#include<string>
using namespace std;
int main()
{
    long long a, b, c;
    cin >> a;
    cin >> b;
    cin >> c;
    if(a%2 == 0 || b%2 == 0 || c%2 == 0)
        cout << 0 << endl;
    else
        cout << min(min(a*b, b*c), a*c) << endl;
    return 0;
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
const int N = 19;
int n;
long long a[N];
unordered_map<int, unordered_map<int, long long>> mem[N][N];
unordered_map<int, unordered_map<int, bool>> vis[N][N];

long long dp(int i, long long xi, int j, long long xj) {
	if (j - i + 1 <= 2) {
		return 0;
	}
	if (vis[i][j][xi][xj]) {
		return mem[i][j][xi][xj];
	}
	vis[i][j][xi][xj] = true;

	long long ans = LLONG_MAX;
	for (int m = i + 1; m < j; m++) {
		ans = min(ans, dp(i, xi, m, xi + xj) + dp(m, xi + xj, j, xj) + a[m] * (xi + xj));
	}

	return mem[i][j][xi][xj] = ans;
}

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

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

	cout << dp(0, 1, n - 1, 1) + a[0] + a[n - 1] << '\n';

	return 0;
}


Measured memory_bytes: 26368
import math
x=int(input())
if x==1 or x==2 or x==3:
  print(1)
  exit()
a=int(math.sqrt(x))
m=0
b=0
for i in range(2,a+1):
  b=1
  while True:
    b*=i
    if b>x:
      break
    if b>m:
      m=b
print(m)

Measured memory_bytes: 3060
n = int(input())
h = {}

for i in range(n):
  verdict = input()
  if verdict == 'AC' or verdict == 'TLE' or verdict == 'RE' or verdict == 'WA':
    if verdict in h:
      h[verdict] += 1
    else:
      h[verdict] = 1

for k in ('AC', 'WA', 'TLE', 'RE'):
  if k in h:
    print("%s x %d" % (k, h[k]))
  else:
    print("%s x 0" % k)

Measured memory_bytes: 9180
N, T = [int(i) for i in input().split()]
C = []

for i in range(N):
    C.append([int(i) for i in input().split()])

x = T
res = []

for c in C:
    cost = c[0]
    time = c[1]
    if time <= x:
        res.append(cost)
    

if len(res) == 0:
    print("TLE")
else:
    p = min(res)
    print(p)

Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<deque>
#include<bitset>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
typedef pair<int,int> P;
template<class T> inline bool chmax(T&a , T b){ if(a<b){ a=b; return true; } else{ return false; } }
template<class T> inline bool chmin(T&a , T b){ if(a>b){ a=b; return true; } else{ return false; } } 

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

const int MAX_N = 2000005;

vector<int> a,ans;
vector<int> to[2000005];
int dp[MAX_N];

void dfs(int v, int pre=-1){
    int i = lower_bound(dp, dp+MAX_N, a[v]) - dp;
    int old = dp[i];
    dp[i] = a[v];
    ans[v] = lower_bound(dp, dp+MAX_N, INF) - dp - 1;
    for(int u : to[v]){
        if(u==pre) continue;
        dfs(u,v);
    }
    dp[i] = old;
}

int main(){
    int n;
    cin >> n;
    a = ans = vector<int>(n);
    rep(i,n) cin >> a[i];
    rep(i,n-1){
        int u,v;
        cin >> u >> v;
        --u; --v;
        to[u].push_back(v);
        to[v].push_back(u);
    }
    rep(i,MAX_N) dp[i] = INF;
    dp[0] = -INF;
    dfs(0);
    rep(i,n) cout << ans[i] << endl;
    return 0;
}

Measured memory_bytes: 79916
#include <cstdio>
#include <functional>
#include <algorithm>
#include <vector>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>

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

ll calcNumOfCombination(ll n, ll r) {
    ll num = 1;
    for (ll i = 1; i <= r; i++) {
        num = num * (n - i + 1) / i;
    }
    return num;
}

int gcd(int x, int y) { return (x % y) ? gcd(y, x % y) : y; }

int findSumDigits(int s) {
    int num = 0;
    int temp = 0;
    while (s) {
        temp = s % 10;
        num += temp;
        s = s / 10;
    }
    return num;
}

int countDivisorNum(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {
            count++;
        }
    }
    return count;
}

int main() {
    ll x;
    cin >> x;
    long long int money = 100;
    ll count = 0;
 
    while (1) {
        count++;
        money = money * 1.01;
        if (money >= x) {
            cout << count << endl;
            return 0;
        }
    }

    return 0;
}

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

double s[1000];
int main() {
	int n; 
	while (cin >> n, n) {
		double sum = 0;
		rep(i, n) {
			cin >> s[i];
			sum += s[i];
		}
		sum /= n;
		double d = 0;
		rep(i, n) {
			d += (s[i] - sum)*(s[i] - sum);
		}
		printf("%.7lf\n", sqrt(d / n));
	}
}

Measured memory_bytes: 3268
DX = [ 0, 1, 0,-1, 1,-1, 1,-1]
DY = [ 1, 0,-1, 0, 1,-1,-1, 1]

while line = gets
  w,h = line.split.map(&:to_i)
  break if w.zero? && h.zero?

  c = Array.new(h){ gets.split.map(&:to_i) }
  seen = Array.new(h){ Array.new(w,false) }

  inside = -> y, x { 0 <= y && y < h && 0 <= x && x < w }

  dfs = -> x,y do
    return if seen[y][x]
    seen[y][x] = true
    8.times do |i|
      nx = DX[i] + x
      ny = DY[i] + y
      next unless inside[ny, nx]
      next if seen[ny][nx]
      next if c[ny][nx].zero?
      dfs[nx,ny]
    end
  end
  
  ans = 0
  h.times do |y|
    w.times do |x|
      next if seen[y][x]
      next if c[y][x].zero?
      ans += 1
      dfs[x,y]
    end
  end
  p ans
end




Measured memory_bytes: 16828
#include <bits/stdc++.h> 
using namespace std; 
typedef long long int ll;
typedef unsigned long long int ull;
const long long int m=1e9+7;

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin>>s;
    ll ans=s.length();
    for(int i=0;i<s.length()-1;i++)
    {
        if(s[i]==s[i+1])
        {ans--;
        i+=2;}
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3764
n = int(input())
p = list(map(int, input().split()))
m =[0] * n
m[0] = p[0]
mi = m[0]
for i in range(1, n):
    mi = min(mi, p[i])
    m[i] = mi
ans = 0
for i in range(n):
  if p[i] == m[i]:
    ans += 1
print(ans)

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

int main(){
  int a,b,x1,x2,y1,y2,x3,x4,y3,y4;cin >> x1 >> y1 >> x2 >> y2;
  a = x2 - x1;
  b = y2 - y1;
  x3 = x2 - b;
  y3 = y2 + a;
  x4 = x3 - a;
  y4 = y3 - b;
     cout << x3 <<" "<< y3 <<" "<< x4 <<" "<< y4  << endl;
}

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

using namespace std;

int isM(int k)
{
    if(k > 0 && k < 13)
        return 1;
    else 
        return 0;
}

int main()
{
    int k, pre, pos;
    cin >> k;
    pre = k/100;
    pos = k%100;
    if(isM(pre) && isM(pos))
    {
        cout << "AMBIGUOUS";
        return 0;
    }
    else if(!isM(pre) && !isM(pos))
    {
        cout << "NA";
        return 0;
    }
    else
    {
        if(isM(pre))
        {
            cout << "MMYY";
            return 0;
        }
        else
        {
            cout << "YYMM";
            return 0;
        }
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = 0; i <= (n); i++)
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const ll INF = 1LL<<60;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using Graph = vector<vector<int>>;

typedef pair<int, int> P;
typedef priority_queue<int, vector<int>, greater<int>> PQ;


int main(){
    int X, N; cin >> X >> N;
    set<int> p;
    rep(i,N){
        int P; cin >> P;
        p.insert(P);
    }

    int ans = 1000000;
    int diff = 1000000;
    
    for (int i = -1000; i <=1000; i++){

        set<int>::iterator it = p.find(i);
        if (it==p.end()){
            if (diff > abs(i-X)){
                ans = i;
                diff = abs(i-X);
            }
            else if( diff == abs(i-X)){
                ans = min(ans, i);
            }
        }
        
    }

    cout << ans << endl;
}

Measured memory_bytes: 3604
K , A,B=  list(map(int,input().split(" ")))
num = 1
if A>=B - 1 or A - 1 >  K:
    num += K

else:
    #1回目
    a = A -1
    num += a

    b = (K - a)//2
    nokori = (K - a)%2
    num += b* (B-A)

    num += nokori
print(num)


Measured memory_bytes: 3060
#include<iostream>
#include<vector>

using namespace std;

int main(void) {

	/*
	double x[3] = { 0,0,0 };
	double y[3] = { 0,0,0 };
	double xp = 0, yp = 0;
	int flag[3] = { 0,0,0 };

	while (cin >> x[0]>> y[0]>> x[1]>> y[1]>> x[2]>> y[2]>> xp>> yp) {
		for (int i = 0; i < 3; i++) {
			int temp1 = (i + 1) % 3;
			int temp2 = (i + 2) % 3;
			double checkI = (y[temp1] - y[i]) * (x[temp2] - x[i]) - (x[temp1] - x[i]) * (y[temp2] - y[i]);
			double checkP = (y[temp1] - y[i]) * (xp - x[i]) - (x[temp1] - x[i]) * (yp - y[i]);

			if (checkI * checkP > 0) {
				flag[i] = 1;
			}
		}
		if (flag[0] == 1 && flag[1] == 1 && flag[2] == 1) {
			cout << "YES" << endl;
		}
		else {
			cout << "NO" << endl;
		}
		flag[0] = 0;
		flag[1] = 0;
		flag[2] = 0;
	}
	*/
	/*
	int input_num;
	vector<int> train_num;
	while (cin >> input_num) {
		if (input_num == 0) {
			cout << train_num.back() << endl;
			train_num.pop_back();
		}
		else if (input_num >= 1 && input_num <= 10) {
			train_num.push_back(input_num);
		}
	}
	*/
	/*
	int d;
	int sum = 0;
	while (cin >> d) {
		for (int i = 0; i < 600 / d; i++) {
			sum += d*i*d*i*d;
		}
		cout << sum << endl;
		sum = 0;
	}
	*/
	/*
	int a[4], b[4];

	while (cin >> a[0] >> a[1] >> a[2] >> a[3] >> b[0] >> b[1] >> b[2] >> b[3]) {
		int hit = 0;
		int blow = 0;
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if (a[i] == b[j]) {
					if (i == j) {
						hit++;
					}
					else {
						blow++;
					}
				}
			}
		}
		cout << hit << " " << blow << endl;
	}
	*/

	int Month[13]{
		0,
		31,29,31,30,
		31,30,31,31,
		30,31,30,31
	};
	//??????0?????\???6
	int dow = 2;
	int in_day, in_month;
	while (cin >> in_month >> in_day) {

		if (in_month == 0)break;

		dow = 2;
		for (int i = 0; i < in_month; i++) {
			dow += Month[i];
		}
		dow += in_day;
		if (dow % 7 == 0) {
			cout << "Monday" << endl;
		}
		else if (dow % 7 == 1) {
			cout << "Tuesday" << endl;
		}
		else if (dow % 7 == 2) {
			cout << "Wednesday" << endl;
		}
		else if (dow % 7 == 3) {
			cout << "Thursday" << endl;
		}
		else if (dow % 7 == 4) {
			cout << "Friday" << endl;
		}
		else if (dow % 7 == 5) {
			cout << "Saturday" << endl;
		}
		else if (dow % 7 == 6) {
			cout << "Sunday" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1156
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
    
		// 整数の入力
		int n = sc.nextInt();
        int[] list = new int[n];
        for(int i = 0; i < n; i++) {
          list[i] = sc.nextInt();
        }
        int i = 0;
        int count = 0;
        boolean[] passed = new boolean[n];
        while(true) {
          if (i == 1) {
            break;
          }
          if (!passed[i]) {
             passed[i] = true;
             i = list[i] - 1;
             count++;
          } else {
            count = -1;
            break;
          }
        }
    
		// 出力
		System.out.println(count);
	}
}

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

#define endl '\n'
#define ff first
#define ss second
#define mp make_pair

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

void solve(){

	int n;
	cin >> n;

	vector<int> arr(2 * n);

	for(int i = 0; i < 2 * n; i++){
		cin >> arr[i];
	}

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

	int ans = 0;

	for(int i = 1; i < (int)arr.size(); i += 2){
		ans += min(arr[i], arr[i - 1]);
	}

	cout << ans << endl;

}


int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef LOCAL
		ifstream in("in");
		cin.rdbuf(in.rdbuf());
	#endif

	solve();

	return 0;
}

Measured memory_bytes: 256
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 510
#define ll long long
int n;
int a[N][N];
ll p[N][N],q[N][N];
ll f[2][N][N];
void upd(ll &a,ll b){a=max(a,b);}
int main(){
	scanf("%d",&n);
	ll sum=0;
	for (int i=1;i<=n;++i){
		for (int j=1;j<i;++j)
			scanf("%d",&a[i][j]),sum+=a[i][j];
		for (int j=i+1;j<=n;++j)
			scanf("%d",&a[i][j]),sum+=a[i][j];
	}
	for (int i=1;i<=n;++i){
		for (int j=i-1;j>=1;--j)
			p[i][j]=p[i][j+1]+a[i][j];
		for (int j=1;j<i;++j)
			q[i][j]=q[i][j-1]+a[j][i];
	}
	int now=1,las=0;
	memset(f[now],128,sizeof f[now]);
	f[now][1][0]=0;
	for (int i=1;i<n;++i){
		swap(now,las);
		memset(f[now],128,sizeof f[now]);
		for (int j=1;j<=i;++j)
			for (int k=j-1;k<i;++k)
				if (f[las][j][k]>=0){
					upd(f[now][j][k],f[las][j][k]+p[i+1][j]+q[i+1][k]);
					upd(f[now][k+1][i],f[las][j][k]+p[i+1][k+1]+q[i+1][i]);
				}
	}
	ll ans=0;
	for (int j=1;j<=n;++j)
		for (int k=j-1;k<n;++k)
			upd(ans,f[now][j][k]);
	printf("%lld\n",sum-ans);
	return 0;
}













Measured memory_bytes: 10760
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/pb_ds/assoc_container.hpp> 
using namespace std; 
using namespace __gnu_pbds;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
 
template <class T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_mset;
 
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define F0R(i,a) for(int i = 0; i < a; i++)
#define F0Rd(i,a) for (int i = a - 1; i >=0 ; i--)
#define FORd(i,a,b) for (int i = b - 1; i >= a; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) int((x).size())
#define newl '\n'
 
#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define print(x) cout << x << newl;
#define finish(x) return cout << x << "\n", 0;
#define bug(x) cerr << ">>> " << #x << " = " << x << "\n";
#define _ << " " << 
 
const int MXN = 2e5 + 5;
//const int MXN = 1e6 + 5;
const ll MOD = 998244353;
const ll INF = 1e9 + 7;
 

int N;
ll a[402], DP[402][402], pref[402];

ll dp(int i, int j){
    if (DP[i][j] != 1e18) return DP[i][j];
    if (j == i) return DP[i][j] = 0;
    if (j - i == 1) return DP[i][j]=a[i+1]+a[j+1];
    FOR(x,i+1,j+1){
        DP[i][j] = min(DP[i][j],dp(i,x-1)+dp(x,j)+pref[j+1]-pref[i]);
    }
    return DP[i][j];
}

 
int main(){ FAST
    //ifstream cin("/Users/konwoo/input.txt");
    //ofstream cout("/Users/konwoo/output.txt");

    cin >> N;
    F0R(i,N){
        cin >> a[i+1];
        pref[i+1] = pref[i] + a[i+1];
    }
    F0R(i,N){
        F0R(j,N){
            DP[i][j] = 1e18;
        }
    }
    finish(dp(0,N-1));
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
    return 0;
}


Measured memory_bytes: 1664
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

int main()
{
	int n;
	long long k;
	cin >> n >> k;
	vector<int> a(n);
	for(int i=0;i<n;i++)
	{
		cin >> a[i];
		a[i]--;
	}

	vector<long long> x(n,-1);

	int now=0;
	x[now]=0;
	long long cnt=0;
	int loop=-1;
	while(true)
	{
		cnt++;
		int nx=a[now];
		if(x[nx]==-1)
		{
			x[nx]=x[now]+1;
		}
		else
		{
			loop=x[now]-x[nx]+1;
			break;
		}
		now=nx;
	}

	for(int i=0;i<n;i++)
	{
		if(x[i]==k)
		{
			cout << i+1 << endl;
			return 0;
		}
	}

	int base=cnt-loop;
	k-=cnt;
//	k+=1;
	k%=loop;
	k+=base;

	for(int i=0;i<n;i++)
	{
		//cerr << i << " " << x[i] << endl;
		if(x[i]==k)
		{
			cout << i+1 << endl;
		}
	}
	




}

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

using namespace std;
using ll = long long;

void init();
void solve();

#define rep(i, a) for (int i = 0; i < (int) (a); i++)
#define reps(i, a, b) for (int i = (int) (a); i < (int) (b); i++)
#define rrep(i, a) for (int i = (int) a-1; i >= 0; i--)
#define rreps(i, a, b) for (int i = (int) (a)-1; i >= (int) (b); i--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}
#define TRUE__  "Yes"
#define FALSE__ "No"
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x

#ifdef LOCAL
#define lcout(a) cout << a
#define lcoutln(a) cout << a << endl
#define lcerr(a) cerr << a
#define lcerrln(a) cerr << a << endl
#else
#define lcout(a) 
#define lcoutln(a) 
#define lcerr(a) 
#define lcerrln(a) 
#endif
#define MOD 1000000007

signed main()
{
	init();
	solve();
}

string s;

void init()
{
	cin >> s;
}

void solve()
{
	s.erase(unique(all(s)), s.end());
	cout << s.length() - 1 << endl;
}



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

int main(void) {
    int a[5];
    int t1,t2,ans;
    for(int i=0; i<5; i++)
        cin>>a[i];

    t1 = a[1]%a[3]; t2=a[2]%a[4];
    int p1 = a[1]/a[3], p2 = a[2]/a[4];
    if(t1 == 0 && t2 == 0)
        ans = a[0] - max(p1, p2);
    else if(t1 == 0)
        ans = a[0] - max(p1, p2+1);
    else if(t2 == 0)
        ans = a[0] - max(p1+1, p2);
    else
        ans = a[0] - max(p1+1, p2+1);

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<stdio.h>
using namespace std;
int main(){
	int tall[10],i,j,box;
	for(i=0;i<10;i++){
		scanf("%d",&tall[i]);
	}
	for(i=0;i<9;i++){
		for(j=i+1;j<10;j++){
			if(tall[i]<tall[j]){
				box=tall[j];
				tall[j]=tall[i];
				tall[i]=box;
			}
		}
	}for(i=0;i<3;i++){
		printf("%d\n",tall[i]);
	}
	return 0;
}

Measured memory_bytes: 3204
#include<iostream>
     
    using namespace std;
     
    int main()
    {
    	int A,B,C,D,E,F;
    	cin>> A>> B>> C>> D>> E>> F;
     
    	
    	int sugar,water;
    	float par=0;
    	for(int a=0;a<=F;a+=100*A)
    	for(int b=0;a+b<=F;b+=100*B)
    	for(int c=0;a+b+c<=F;c+=C)
    	for(int d=0;a+b+c+d<=F;d+=D)
    	{
    		float x=a+b,y=c+d;
    		if(x+y!=0&&(float)E/100>=y/x&&par<=(y)/(x+y))
    		{
    			par=y/(x+y);
    			water=x+y;
    			sugar=y;
    		}
    	}
    	cout<< water<< " "<< sugar<< endl;
    	
    	return 0;
    }

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

using namespace std;


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

    auto a = vector<int>(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    
    for (int loop_cnt = 0; loop_cnt < k; loop_cnt++)
    {
        if (*min_element(a.begin(), a.end()) >= n)
        {
            break;
        }
        
        auto imos = vector<int>(n + 1);
        for (int i = 0; i < n; i++)
        {
            imos[max(0, i - a[i])] += 1;
            imos[min(n, i + a[i] + 1)] -= 1;
        }
        
        a[0] = imos[0];
        for (int i = 1; i < n; i++)
        {
            a[i] = a[i - 1] + imos[i];
        }
    }
    
    for (int i = 0; i < n - 1; i++)
    {
        cout << a[i] << " ";
    }
    cout << a[n - 1] << endl;

    return 0;
}


Measured memory_bytes: 4840
#include "bits/stdc++.h"
	using namespace std;
	static const int MAX=10000;
	static const int INFTY=(1<<21);
	static const int WHITE=0;
	static const int GRAY=1;
	static const int BLACK=2;
	
	int n;
	//????????????????????°???????????£??\???????????¨???
	vector<pair<int,int> >adj[MAX];
	
	void dijkstra(){
		priority_queue<pair<int,int> > PQ;
		int color[MAX];
		int d[MAX];
		for (int i = 0; i < n; ++i) {
			d[i]=INFTY;
			color[i]=WHITE;
		}
		d[0]=0;
		PQ.push(make_pair(0,0));
		color[0]=GRAY;
		while(!PQ.empty()){
			pair<int,int> f=PQ.top();PQ.pop();
			int u=f.second;
			color[u]=BLACK;
			//????°???????????????????????????????????????§???????????°??????
			if(d[u]<f.first *(-1))continue;
	
			for (int j = 0; j < adj[u].size(); ++j) {
				int v=adj[u][j].first;
				if(color[v]==BLACK)continue;
				if(d[v]>d[u]+adj[u][j].second){
					d[v]=d[u]+adj[u][j].second;
					//priority_queue????????????????????§??§??????????????????????????????-1????????????
					PQ.push(make_pair(d[v]*(-1),v));
					color[v]=GRAY;
				}
			}
		}
		for (int i = 0; i < n; ++i) {
			cout<<i<< " "<<(d[i]==INFTY?-1:d[i])<<endl;
	   }
	}
	
	
	int main(){
		cin>>n;
		int k,c,u,v;
		for (int i = 0; i < n; ++i) {
			cin>>u>>k;
			for (int j = 0; j < k; ++j) {
				cin>>v>>c;
				adj[u].push_back(make_pair(v,c));
			}
		}
		dijkstra();
		return 0;
	}

Measured memory_bytes: 7948
import fractions

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

def multiple(A, B, C): #number of multiples of C between A and B
    return B//C - (A-1)//C

A, B, C, D = map(int, input().split())

allnumbers = B-A+1

ans = allnumbers - (multiple(A,B,C) + multiple(A,B,D) - multiple(A,B,lcm(C,D)))

print(ans)


Measured memory_bytes: 5048
// #include {{{
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
// }}}
// #define {{{
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
// }}}

const int N = 1e5 + 10;
int n , a[N];

int main(){
  cin >> n;
  rep(i,1,n+1) cin >> a[i];
  sort(a + 1 , a + n + 1);
  reverse(a + 1 , a + n + 1);
  int i = 1;
  while(i + 1 <= n && i + 1 <= a[i + 1])
    ++i;
  int hori = a[i] - i + 1;
  int vert = 0;
  for(int j=i;j<=n;++j) {
    if(a[j]<i) break;
    vert++;
  }
  puts(hori % 2 == 1 && vert % 2 == 1 ?
      "Second" : "First");
  return 0;
}


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

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

const int INF=INT_MAX-1;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    set<string>s;
    for(int i=0; i<n; i++){
        string t;
        cin >> t;
        s.insert(t);
    }
    cout << s.size() << "\n";
    return 0;
}

Measured memory_bytes: 19276
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>

using namespace std;

const int inf = 1e9;

int main() {
	int h, w;
	cin >> h >> w;

	vector<vector<int>> c(10, vector<int>(10, 0));
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> c[i][j];
		}
	}

	map<int, int> wall;
	int x;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> x;
			wall[x]++;
		}
	}
	auto needs = c;

	bool update;
	do {
		update = false;
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				for (int k = 0; k < 10; k++) {
					int tmp = needs[i][k] + needs[k][j];
					if (tmp < needs[i][j]) {
						needs[i][j] = tmp;
						// printf("%d -> %d: %d\n", i, j, tmp);
						update = true;
					}
				}
			}
		}
	} while (update);

	long long ans = 0;
	for (auto p: wall) {
		switch(p.first) {
			case -1: case 1:
				break;
			default:
				ans += p.second * needs[p.first][1];
		}
	}
	cout << ans << endl;

	return 0;
}


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

int main() {
  int h, n, ai;
  cin >> h >> n;
  int sum = 0;
  rep(i,n) {
    cin >> ai;
    sum += ai;
  }
  if (h > sum) {
    cout << "No";
  } else {
    cout << "Yes";
  }
}


Measured memory_bytes: 256
#pragma warning(disable: 4996)
#define _USE_MATH_DEFINES
#include <iostream>
#include <unordered_map>
#include <functional>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
using namespace std;

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

	int r;
	cin >> r;
	cout << r * r << endl;
	return 0;
}


Measured memory_bytes: 888
#include<iostream>
#include<array>

int main(){
    std::array<int, 4> a;
    std::array<int, 4> b;
    while(std::cin >> a[0] >> a[1] >> a[2] >> a[3]){
        std::cin >> b[0] >> b[1] >> b[2] >> b[3];
        int hit = 0, blow = 0;
        for(int i = 0; i < a.size(); ++i){
            for(int j = 0; j < b.size(); ++j){
                if(a[i] == b[j] && i == j)
                    ++hit;
                else if (a[i] == b[j])
                    blow ++;
            }
        }
          std::cout << hit << " " << blow << std::endl;
    }
      return 0;
}

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

using namespace std;

#define fore(i, s, e) for(int i = s; i < e; i++)

const int N = 2e6;
int aux[N];
int n;
int a[N];

long long solve(int i){
    if(i == n - 1) return 0;
    if(i == n - 2) return abs(a[i] - a[i+1]);
    
    if(aux[i] != -1) return aux[i]; 
    
    long long res = 1e15;
    res = min(res, abs(a[i] - a[i+1]) + solve(i+1));
    res = min(res, abs(a[i] - a[i+2]) + solve(i+2));
    
    aux[i] = res;
    return res;
}

int main(){
    cin >> n;
    fore(i, 0, n){
        aux[i] = -1;
        cin >> a[i];
    }
        
    cout << solve(0) << endl;
}


Measured memory_bytes: 9472
def main():
    X = input()
    cnt_s = 0
    cnt_removal = 0
    for x in X:
        if x == 'T':
            if cnt_s > 0:
                cnt_s -= 1
                cnt_removal += 1
        else:
            cnt_s += 1
    print(len(X) - 2 * cnt_removal)


if __name__ == '__main__':
    main()

Measured memory_bytes: 9028
#include <algorithm>
#include <iostream>

auto main() -> int {
    int heights[10];
    for (int i = 0; i < 10; i++) {
        std::cin >> heights[i];
    }

    std::sort(std::begin(heights), std::end(heights), std::greater<int>());

    for (int i = 0; i < 3; i++) {
        std::cout << heights[i] << std::endl;
    }
}

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

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

			//文字を読み取る。
			String strLineS = insBR.readLine();
			String strLineP =insBR.readLine();
			String strLineSS = strLineS + strLineS;

			//作れるか判定する。
			int intIndex = strLineSS.indexOf(strLineP);
			String strMessage = "";
			if(intIndex != -1){
				strMessage = "Yes";
			}else{
				strMessage = "No";
			}

			//出力。
			System.out.println(strMessage);

		}catch(IOException e){
			e.printStackTrace();
		}catch(NumberFormatException e){
			e.printStackTrace();
		}
	}

}



Measured memory_bytes: 24440
#include<bits/stdc++.h>
using namespace std;
#define lop(i,n) for(ll i=0;i<n;i++)
#define lop1(i,n) for(ll i=1;i<=n;i++)
#define lopr(i,n) for(ll i=n-1;i>=0;i--)
#define ll long long int
#define pb push_back
#define all(v) v.begin(),v.end()
#define IOS  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endl "\n"
#define F first
#define S second	
#define mem(arr,val) memset(arr,val,sizeof(arr))
#define pii pair<int,int>
#define pll pair<ll,ll>
#define LCM(a,b) (a*b)/__gcd(a,b)
#define mii map<int,int>
#define mll map<ll,ll>
#define ub upper_bound
#define lb lower_bound
#define sz(x) (ll)x.size()
#define ld long double
#define pcnt(x) __builtin_popcountll(x)
const long long I1=1e9;
const long long I2=1e18;
const int32_t M1=1e9+7;
const int32_t M2=998244353;
template<typename T,typename T1>T maxn(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T minn(T &a,T1 b){if(b<a)a=b;return a;}

void solve()
{
  //code begins from here//
  ll n;
  cin>>n;
  string s;
  cin>>s;
  ll pre[n+1],suf[n+1];
  pre[0]=0,suf[n]=0;
  lop1(i,n) 
  {
    pre[i]=pre[i-1]+(s[i-1]=='W');
  }
  lopr(i,n)
  {
    suf[i]=suf[i+1]+(s[i]=='R');
  }
  ll ans=I1;
  lop(i,n+1)
  {
    minn(ans,max(pre[i],suf[i]));
  }
  cout<<ans<<endl;
}

signed main()
{
    IOS;
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #ifdef MODULO
        initialize();
    #endif
    #ifdef SIEVE
        sieve();
    #endif
    int testcase=1;
    //cin>>testcase;
    while(testcase--) solve();
    return 0;
}


Measured memory_bytes: 6808
if __name__ == '__main__':
    N, K = map(int, input().split())
    h_list = list(map(int, input().split()))
 
    dp_list = [0]
    for n in range(1, N):
        tmp_h = h_list[n]
        if n < K:
            lst = [abs(tmp_h - h_list[i]) + dp_list[i] for i in range(n)]
        else:
            lst = [abs(tmp_h - h_list[n-k]) + dp_list[n-k] for k in range(1, K + 1)]
        dp_list.append(min(lst))
    print(dp_list[-1])

Measured memory_bytes: 20508