akhauriyash/Code-Regression huggingface dataset:
def main():
    D = int(input())
    C = list(map(int, input().split()))
    S = [list(map(int, input().split()))for _ in range(D)]

    len_C = len(C)
    types = []
    lasts = [0] * 26

    for i in range(D):
        s = max(S[i])

        c = []
        c_sum = 0
        for j in range(len_C):
            c.append((i + 1 - lasts[j]) * C[j])
            c_sum += (i + 1 - lasts[j]) * C[j]  # 満足度低下の合計

        if c_sum >= s:
            t = c.index(max(c)) + 1
            lasts[t - 1] = i + 1
        else:
            t = S[i].index(s) + 1

        types.append(t)

    for type in types:
        print(type)


if __name__ == '__main__':
    main()


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

int main()
{
	int n;
	while (cin >> n)
	{
		int ans = 0;
		for (int a = 0; a < 10; a++){
		for (int b = 0; b < 10; b++){
		for (int c = 0; c < 10; c++){
		for (int d = 0; d < 10; d++){

			if (a + b + c + d == n) ++ans;
		}}}}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
s = input()

front = int(s[0:2])
back = int(s[2:4])


def check_type(val):
    if 1 <= val <= 12:
        return 'm'
    else:
        return 'y'


r_front = check_type(front)
r_back = check_type(back)

if r_front == 'y' and r_back == 'm':
    print('YYMM')
elif r_front == 'm' and r_back == 'y':
    print('MMYY')
elif r_front == 'm' and r_back == 'm':
    print('AMBIGUOUS ')
else:
    print('NA')





Measured memory_bytes: 3060
use std::io::*;
use std::str::FromStr;

fn transfer(a: u8, b: u8, c: u8) -> u8 {
    if b + c < a {
        0
    } else {
        (b + c) - a
    }
}

#[test]
fn test() {
    assert_eq!(transfer(6, 4, 3), 1);
    assert_eq!(transfer(8, 3, 9), 4);
    assert_eq!(transfer(12, 3, 7), 0);
}
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
            .bytes()
            .map(|c| c.expect("failed to read char") as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let a: u8 = read();
    let b: u8 = read();
    let c: u8 = read();

    let ans = transfer(a, b, c);
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <iostream>
#include <cstdio>
using namespace std;
int N=0;
int M, A, B, C, D, x1, x2, y1, y2;
int K[32][32];
const int inf = 1001001001;
int s,g,V,P;
void Floyd_Warshall(){
    for(int k=1;k<=N;k++){
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                if(K[i][j]>K[i][k]+K[k][j]){
                    K[i][j]=K[i][k]+K[k][j];
                }
            }
        }
    }
}
void init_K(){
    for(int i=0;i<=N;i++){
        for(int j=0;j<=N;j++){
            K[i][j]=inf;
        }
    }
}
int main() {
    scanf("%d%d", &N, &M);
    init_K();
    for (int i=0; i<M; ++i) {
        scanf("%d,%d,%d,%d", &A, &B, &C, &D);
        K[A][B]=C;
        K[B][A]=D;
    }
    scanf("%d,%d,%d,%d", &s, &g,&V,&P);
    Floyd_Warshall();
    int sum=V-P-K[s][g]-K[g][s];
    cout<<sum<<endl;
    return 0;
}



Measured memory_bytes: 3140
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define uniq(x) (x).erase(unique(ALL(x)),(x).end())
#define SORT(x) sort(ALL(x))
#define REV(x) reverse(ALL(x))
#define foreach(it,x) for(__typeof((x).begin()) it=(x).begin();it!=(x).end();it++)
#define debug(x) cerr<<#x<<"="<<(x)<<endl
#define gett() cerr<<"Time:"<<clock()<<"ms."<<endl
#define ri(x) scanf("%d",&x)
#define rl(x) scanf("%lld",&x)
#define rlcfpoj(x) scanf("%I64d",&x)
#define pi(x) printf("%d",x)
#define pl(x) printf("%lld",x)
#define plcfpoj(x) printf("%I64d",x)
#define lfd() printf("\n")
#define sp() printf(" ")
#define inrep(x) int x;scanf("%d",&x);while(x--)
#define testbit(mask,i) (((mask)>>(i))&1)
#define setbit(mask,i) ((mask)|(1<<i))
#define delbit(mask,i) ((mask)^(1<<i))
int n;
int l[2010];
long long cnt[2010];
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>l[i];
	}
	long long res=0;
	sort(l+1,l+n+1);
	for(int i=1;i<n;i++){//普通三角形 
		int k=0;
		for(int j=i+1;j<n;j++){
			int a=l[i],b=l[j];
			k=max(k,j+1);
			while(k<=n&&l[k]<=a+b-1){
				k++;
			}
			res+=(long long)(k-j-1);
		}
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

def main():
    n = int(input())
    a, b = [], []
    minb = 10**10
    for _ in range(n):
        _a, _b = map(int, input().split())
        a.append(_a)
        b.append(_b)
        if _a != 0 and _b < _a:
            minb = min(minb, _b)
    if a == b:
        print(0)
    else:
        print(sum(a) - minb)


if __name__ == '__main__':
    main()


Measured memory_bytes: 4840
#include<stdio.h>

#define MAX 10000
#define NIL -1

struct Node{
  int p, l, r;
};

struct Node Tree[MAX];
int Depth[MAX], Height[MAX];

void setDepth(int, int);
int setHeight(int);
int Sibling(int);
void Print(int);

int main(){
  int left,right,num,n,i;
  int root = 0;

  scanf("%d",&n);

  for(i = 0 ; i < n ; i++) Tree[i].p = NIL;

  for(i = 0 ; i < n ; i++){
    scanf("%d%d%d",&num,&left,&right);
    Tree[num].l = left;
    Tree[num].r = right;
    if(left != NIL) Tree[left].p = num;
    if(right != NIL) Tree[right].p = num;
  }
 for(i = 0 ; i < n ; i++) if(Tree[i].p == NIL) root = i;

  setDepth(root,0);
  setHeight(root);

  for(i = 0 ; i < n ; i++) Print(i);

  return 0;
}

void setDepth(int a, int b){
  if(a == NIL) return;
  Depth[a] =b;
  setDepth(Tree[a].l,b+1);
  setDepth(Tree[a].r,b+1);
}

int setHeight(int a){
  int h1 = 0, h2 = 0;
  if(Tree[a].l != NIL) h1 = setHeight(Tree[a].l) + 1;
  if(Tree[a].r!= NIL) h2 = setHeight(Tree[a].r) + 1;

  if(h1 > h2) return Height[a] = h1;
  else return Height[a] = h2;
  
}

int Sibling(int x){
  if(Tree[x].p == NIL) return NIL;
  if(Tree[Tree[x].p].l != x && Tree[Tree[x].p].l != NIL){
    return Tree[Tree[x].p].l;
  }
  if(Tree[Tree[x].p].r != x && Tree[Tree[x].p].r != NIL){
    return Tree[Tree[x].p].r;
  }

  return NIL;
}

void Print(int x){
  int deg = 0;
  printf("node %d: ",x);
  printf("parent = %d, ",Tree[x].p);
  printf("sibling = %d, ",Sibling(x));
  if(Tree[x].l != NIL) deg++;
  if(Tree[x].r != NIL) deg++;
  printf("degree = %d, depth = %d, height = %d, ",deg,Depth[x],Height[x]);
 
  if(Tree[x].p==NIL){
    printf("root\n");
  }
  else if(Tree[x].l == NIL && Tree[x].r == NIL){
    printf("leaf\n");
  }
  else printf("internal node\n");
}






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

def main():
     n = int(input())
     a = list(map(int, input().split()))
     num_a = dict()
     com_a = dict()

     for i in a:
          if not i in num_a.keys():
               num_a[i] = 1
          else:
               num_a[i] += 1

     for i in num_a.keys():
          value = num_a[i]
          com_a[i] = com(value)

     # print(num_a)
     # print(com_a)

     pre_ans = sum(com_a.values())
     # print('pre_ans:{}'.format(pre_ans))

     for i in range(n):
          k = a[i]
          ans = pre_ans - com_a[k] + com(num_a[k] - 1)
          print(ans)

def com(n):
     return (n * (n - 1)) // 2

if __name__ == "__main__":
    main()


Measured memory_bytes: 32800
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
const int maxn = 100005;
long long a[maxn];
int n;
int main(){
#ifdef __APPLE__
	freopen("main.in","r",stdin);
#endif
	ios::sync_with_stdio(false);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	sort(a+1,a+n+1);
	int last = -1;
	int num = 0;
	long long ans = 1;
	int tot = 0;
	for(int i = n; i >= 1; i--){
		if(a[i] != last){
			num = 0;
			last = a[i];
		}
		num++;
		if(num == 2){
			ans *= a[i];
			num = 0;
			tot++;
			if(tot == 2) break;
		}
	}
	if(tot != 2) cout << "0" << endl;
	else cout << ans << endl;
	return 0;
}


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

typedef long long ll;

int main() {
	ll n, s = 0;
	cin >> n;
	vector<ll> A(n);
	for (auto& a: A)
	{
		cin >> a;
		s ^= a;
	}
	
	for (auto a: A)
		cout << (s ^ a) << endl;
	
	return 0;
}

Measured memory_bytes: 4656
"""
author : halo2halo
date : 16, Jan, 2020
"""

import sys
# import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N = int(readline())

print('YES' if N==7 or N==5 or N==3 else 'NO')


Measured memory_bytes: 2940
#include<iostream>
#include<vector>
using namespace std;
#define MAX 20
int main()
{
  int N;

  cin>>N;

  vector<int>n(N);
  vector< vector<long long int> >dp(N,vector<long long int>(MAX+1,0));

  for(int i=0;i<N;i++)cin>>n[i];

  dp[0][n[0]]=1;
  for(int i=1;i<N;i++){
    for(int j=0;j<=MAX;j++){
      if(j+n[i]<=MAX){
	dp[i][j]+=dp[i-1][j+n[i]];
      }
      if(j-n[i]>=0){
	dp[i][j]+=dp[i-1][j-n[i]];
      }
    }
  }

  cout<<dp[N-2][n[N-1]]<<endl;
}

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

using namespace std;

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

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

    vector<vector<int>> dp(2, vector<int>(n, 0));

    dp[0][0] = a[0][0];
    for (int i = 1; i < n; i++) {
        dp[0][i] = dp[0][i - 1] + a[0][i];
    }

    dp[1][0] = dp[0][0] + a[1][0];
    for (int i = 1; i < n; i++) {
        dp[1][i] = max(dp[0][i], dp[1][i - 1]) + a[1][i];
    }

    cout << dp[1][n - 1] << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <cmath>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;

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

	for(int i=1; i<=b; i++){
		if((a*i)%b == c){
			cout << "YES" << endl;
			return 0;
		}
	}
	cout << "NO" << endl;
	return 0;
}

Measured memory_bytes: 256
S=str(input())
import sys
t=0
lista=[]
for i in range(99):
    try:
        lista.append(S[i])
        t=t+1
    except IndexError:
        break
u=t//2
v=u//2+1
p=1
for i in range(v):
    if S[i]==S[u-i-1] and S[u-i-1]==S[u+i+1] and S[u+i+1]==S[t-1-i]:
        p=p*1
    else:
        print ('No')
        sys.exit()
print ('Yes')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define dbg(x) cout<<#x<<"="<<x<<" "
#define nl cout<<"\n"
#define fr(i,n) for(int i=0;i<n;i++)
 

int main(){

		    map<string,int>mp={ {"Sunny",0}, {"Cloudy",1}, {"Rainy",2}};
		    string arr[]={ "Sunny", "Cloudy", "Rainy"};
		    string s;cin>>s;
		    cout<<arr[(mp[s]+1)%3];

}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    string S;
    cin >> S;

    int ans = 0;
    for(char i='0'; i<='9'; i++)
    {
        auto itr_i = S.find(i);
        if(itr_i == string::npos) continue;
        for(char j='0'; j<='9'; j++)
        {
            auto itr_j = S.find(j, itr_i+1);
            if(itr_j == string::npos) continue;
            for(char k='0'; k<='9'; k++)
            {
                if(S.find(k, itr_j+1) != string::npos)
                {
                    ans++;
                }
            }
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3692
#include<algorithm>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<cstdio>
#include<iomanip>
#include<cmath>
using namespace std;

int main(){
//    cout << fixed << setprecision(10);
    int X, Y, Z;
    cin >> X >> Y >> Z;
    cout << Z << " " << X << " " << Y;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

int main(){
  vl leng(3);
  rep(i, 3) cin >> leng[i];

  stable_sort(leng.begin(), leng.end());

  cout << leng[0] * leng[1] / 2 << "\n";
  
  return 0;
}


Measured memory_bytes: 3600
N,M = (int(x) for x in input().split())
S_arr = [int(x) for x in input().split()]
T_arr = [int(x) for x in input().split()]

dp = [[1]*(M+1) for _ in range(N+1)]

mod = 1000000007
for n in range(N):
    for m in range(M):
        if S_arr[n] == T_arr[m]:
            dp[n+1][m+1] = (dp[n+1][m]+dp[n][m+1]) % mod
        else:
            dp[n+1][m+1] = (dp[n+1][m]+dp[n][m+1]-dp[n][m]) % mod
print(dp[N][M])


Measured memory_bytes: 72924
#include <bits/stdc++.h>
#include <stdio.h>
#include <numeric>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define repone(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define Rep(j,n) for(int j=0;j<(int)(n);++j)
#define Repo(j,o,n) for(int j=o;j<(int)(n);++j)
#define Repone(j,n) for(int j=1;j<(int)(n);++j)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define int long long
#define pb(a) push_back(a)
#define eraser(v,i) (v).erase(v.begin()+(i))
#define pbpair(a,b) push_back(make_pair(a,b))
#define MOD 1000000007
#define INF 9223372036854775807
#define pairint pair<int,int>
int num[12] = {31,28,31,30,31,30,31,31,30,31,30,31};
bool uru(int checkyear){if(checkyear%4==0){if(checkyear%100!=0||checkyear%400==0)return true;}return false;}
int gcd( int x, int y ){return y ? gcd(y, x%y) : x;}
signed main() {
    int x=0,y=0,z=0,w=0,n=0,m=0;
    cin >>x>>y;
    if(x%3==0)cout<<"Possible";
    else if(y%3==0)cout <<"Possible";
    else if((x+y)%3==0)cout <<"Possible";
    else cout << "Impossible";
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
//#include <conio.h>
using namespace std;

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

#define rep(i,n)	for(ll i=0;i<(n);i++)
#define SZ(x) ((ll)x.size())
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define F first
#define S second
#define int ll
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const ll MOD = INT_MAX;
const double PI = acos(-1);

void openfile(){
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
}
const int N = 305;
double dp[N][N][N];
int n;

double f(int a,int b,int c){
	if(a == 0 && b == 0 && c == 0)	return 0;
	if(dp[a][b][c])	return dp[a][b][c];
	double ans = 1.0 * n / (a+b+c);
	if(a > 0)	ans += 1.0 * a / (a+b+c) * f(a-1,b,c);
	if(b > 0)	ans += 1.0 * b / (a+b+c) * f(a+1,b-1,c);
	if(c > 0)	ans += 1.0 * c / (a+b+c) * f(a,b+1,c-1);
	return dp[a][b][c] = ans;
}

signed main(){
	IOS
	cin >> n;
	double a[n];	rep(i,n)	cin >> a[i];
	int cnt[3] = {0};
	rep(i,n)	cnt[(int)a[i]-1]++;
	cout << setprecision(15) << f(cnt[0],cnt[1],cnt[2]) << endl;
}


Measured memory_bytes: 219392
#include <iostream>

int main(){
   int S;
   std::cin >> S;

   int a = S/100;
   int b = S%100;
   if(a>12){
      if(b>12 || b==0) std::cout << "NA" << std::endl;
      else std::cout << "YYMM" << std::endl;
   }else{
      if(b>12){
	 if(a>0) std::cout << "MMYY" << std::endl;
	 else std::cout << "NA" << std::endl;
      }else {
	 if(a>0){
	    if(b>0) std::cout << "AMBIGUOUS" << std::endl;
	    else std::cout << "MMYY" << std::endl;
	 }else{
	    if(b>0) std::cout << "YYMM" << std::endl;
	    else std::cout << "NA" << std::endl;
	 }
      }
   }
   return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MXN = 5005;
int ans = 0;
int z[MXN];

void z_value(string s){
    // cout << s << '\n';
	int l = 0, r = 0;
	z[0] = 0;
	for (int i = 1; i < (int)s.size(); i++){
		if (i>r)z[i] = 0;
		else{
			int ip = i - l;
			if (ip + z[ip] < z[l])z[i] = z[ip];
			else z[i] = r - i + 1;
		}
		while (i + z[i] < (int)s.size() && s[i + z[i]] == s[z[i]])
        {
            z[i]++;
        }
		if (i + z[i] - 1 > r){
			l = i;
			r = l + z[i] - 1;
		}
        ans = max(ans, (i > z[i] ? z[i] : i));
	}
}

int main()
{
    int n;
    string s;
    cin >> n >> s;
    ans = -1;
    for(int i = 0; i < n; ++i)
    {
        z_value(s.substr(i));
    }
    cout << ans << '\n';
}

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

int main() {
    ios::sync_with_stdio(0);
    
    int n; cin >> n;
    vector<int> ind(2e5+10, 0);
    for (int i = 1; i < n; i++) {
        int a; cin >> a;
        ind[a]++; 
    }

    for (int i = 1; i <= n; i++) cout << ind[i] << "\n"; 
}

Measured memory_bytes: 4004
#include<iostream>
#include<stdlib.h>
#define D(x) cout<<"D:"<<#x<<'='<<x<<endl;
using namespace std;
typedef long long ll;
inline ll next(void)
{
	ll k;
	cin>>k;
	return k;
}
ll num[5][5];
bool t[5][5];
int main(void)
{
//	freopen("$.in", "r", stdin);
//	freopen("$.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	char *str = (char*)malloc(10*sizeof(char));
	str = "No";
	for(int i = 0; i < 3; i++)
		for(int j = 0; j < 3; j++)
			cin>>num[i][j];
	while(cin>>n)
		for(int i = 0; i < 3; i++)
			for(int j = 0; j < 3; j++)
				if (num[i][j] == n) t[i][j] = 1;
	for(int i = 0; i < 3; i++)
		if ((t[i][0] && t[i][1] && t[i][2]) || (t[0][i] && t[1][i] && t[2][i])) str = "Yes";
	if ((t[0][0] && t[1][1] && t[2][2]) || (t[0][2] && t[1][1] && t[2][0])) str = "Yes"; 
	cout<<str<<endl; 
	return 0;
}

Measured memory_bytes: 256
#include <string>
#include <iostream>
#include <set>       // 要素数は size() で取得
#include <algorithm> // count_ifに必要
#include <array>     // size固定の配列
#include <queue>
#include <vector>
#include <numeric>

using namespace std;
// 問題が起こるまでintは使用禁止2020-04-13
using ll = long long;

ll gcd(ll x, ll y)
{
    if (y == 0)
        return x;
    else
        return gcd(y, x % y);
}

template <class InputIterator, class T>
bool contains(InputIterator iterator, const T &value)
{
    if (find(iterator.begin(), iterator.end(), value) == iterator.end())
        return false;
    else
        return true;
}

// =========ここまでテンプレ============

int main()
{
    int n;
    int m;
    vector<int> a;
    cin >> n;
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        int j;
        cin >> j;
        a.push_back(j);
    }
    int total;
    total = accumulate(a.begin(), a.end(), 0);
    cout << max(-1, n - total);
}

// sumを用意する
// vectorをテンプレに
// numeric

Measured memory_bytes: 3264
a = input()
b = list(map(int,input().split()))
 
listdir = []
for i in b:
  if i % 2 == 0:
    if i % 3 != 0 and i % 5 != 0:
      listdir.append(i)
 
if len(listdir) >= 1:
  print("DENIED")
else:
  print("APPROVED")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
unsigned short F[200000][2019]={}; 
int main(){
  string S; cin >> S;
  int i, r, s, N=S.size(), R[10][2019]={};
  for(r=0; r<2019; r++){ for(i=1; i<10; i++){ 
    for(s=0; s<2019; s++){ if((10*s+i)%2019==r){ R[i][r]=s; break; } }
  } }
  for(i=0; i<N; i++){ F[i][S[i]-'0']=1; }  
  for(i=1; i<N; i++){ for(r=0; r<2019; r++){ F[i][r]+=F[i-1][R[S[i]-'0'][r]]; } }
  long ans=0;
  for(i=0; i<N; i++){ ans+=F[i][0]; }
  cout << ans << "\n";
}

Measured memory_bytes: 792408
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010,mod=1000000007,inv2=500000004;
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
	int x=0,f=0;char ch=getchar();
	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return f?-x:x;
}
int n,a[maxn],deg[maxn],ans=1,stk[maxn],tp,q[maxn],h,r,len[maxn],seq[maxn],tot,cnt[maxn];
int fac[maxn],inv[maxn],invfac[maxn];
bool vis[maxn],ins[maxn],cyc[maxn];
void dfs(int u){
	if(vis[u]){
		if(ins[u]){
			ROF(i,tp,1){
				cyc[stk[i]]=true;
				if(stk[i]==u) break;
			}
		}
		return;
	}
	vis[u]=ins[u]=true;
	stk[++tp]=u;
	dfs(a[u]);
	ins[u]=false;
}
bool dfs2(int u){
	if(vis[u]) return true;
	vis[u]=true;
	seq[++tot]=len[u];
	return dfs2(a[u]) && !len[u];
}
inline int C(int n,int m){
	return 1ll*fac[n]*invfac[m]%mod*invfac[n-m]%mod;
}
inline int qpow(int a,int b){
	int ans=1;
	for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) ans=1ll*ans*a%mod;
	return ans;
}
int main(){
	n=read();
	FOR(i,1,n) a[i]=read(),deg[a[i]]++;
	FOR(i,1,n) dfs(i);
	FOR(i,1,n) if(cyc[i] && deg[i]>=3|| !cyc[i] && deg[i]>=2) return puts("0"),0;
	h=1;r=0;
	FOR(i,1,n) if(!deg[i]) q[++r]=i;
	while(h<=r){
		int u=q[h++];
		len[a[u]]=len[u]+1;
		if(!cyc[a[u]]) q[++r]=a[u];
	}
	MEM(vis,0);
	FOR(i,1,n) if(cyc[i] && !vis[i]){
		tot=0;
		if(dfs2(i)) cnt[tot]++;
		else{
			int pre=0;
			FOR(j,1,tot) if(seq[j]){
				if(pre){
					int at=j-seq[j];
					if(at<pre) return puts("0"),0;
					if(at>pre && tot>=2) ans=2*ans%mod;
				}
				pre=j;
			}
			FOR(j,1,tot) if(seq[j]){
				int at=j-seq[j]+tot;
				if(at<pre) return puts("0"),0;
				if(at>pre && tot>=2) ans=2*ans%mod;
				break;
			}
		}
	}
	fac[0]=fac[1]=inv[1]=invfac[0]=invfac[1]=1;
	FOR(i,2,n){
		fac[i]=1ll*fac[i-1]*i%mod;
		inv[i]=mod-1ll*(mod/i)*inv[mod%i]%mod;
		invfac[i]=1ll*invfac[i-1]*inv[i]%mod;
	}
	FOR(i,1,n) if(cnt[i]){
		int s=0;
		FOR(j,0,cnt[i]/2){
			int x=1ll*C(cnt[i],2*j)*C(2*j,j)%mod*fac[j]%mod;
			if(j) x=1ll*x*qpow(inv2,j)%mod*qpow(i,j)%mod;
			if(i%2==1 && i!=1) x=1ll*x*qpow(2,cnt[i]-2*j)%mod;
			s=(s+x)%mod;
		}
		ans=1ll*ans*s%mod;
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 5632
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
    	try (Scanner in = new Scanner(System.in)) {
    		int N = Integer.parseInt(in.next());
    		char[] s = in.next().toCharArray();
    		int redCounter = 0;
    		int blueCounter = 0;
    		
    		for (int i = 0; i < N; i++) {
    			if (s[i] == 'R') redCounter++;
    				else blueCounter++;
    		}
    		
    		if (blueCounter < redCounter) System.out.println("Yes");
    		else System.out.println("No");
    		
    		
    	} catch (Exception e) {
			// TODO: handle exception
		}
    }
}


Measured memory_bytes: 23124
import numpy as np
h,n=map(int,input().split())
p=[list(map(int,input().split())) for _ in range(n)]
m=10**4
dp=[0]*(h+m+1)
for i in range(m+1,h+m+1):
  dp[i]=min(dp[i-a]+b for a,b in p)
print(dp[h+m])


Measured memory_bytes: 27604
#include<bits/stdc++.h>
using namespace std;
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; }
#define rep(i,n) for(int i=0;i<(int)(n);i++)
const int mod = 1e9+7;
const long long INF = 1LL << 60;
typedef long long ll;
int main(){
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); i++){
        if(i==3)break;
        if(s[i]==s[i+1]){
            cout<<"Bad"<<endl;
            return 0;
        }
    }
    cout << "Good"<<endl;
}

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

int main(){
  int n;
  cin >> n;
  vector<int> p(n), q(n);
  rep(i,n) cin >> p[i];
  rep(i,n) cin >> q[i];

  vector<int> natural(n);
  rep(i,n) natural[i] = i + 1;
  int order = 0;
  int a = 0, b = 0;
  do{
  	++order;
  	if(natural == p) a = order;
  	if(natural == q) b = order;
  } while (next_permutation(natural.begin(), natural.end()));

  cout << abs(a - b) << endl;
  return 0;
}


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

int main(){
  int N;
  string S;
  cin >> N >> S;
  for(int i=0; i<S.length(); i++){
    int s_num = int(S[i]+N);
    if(s_num>90) s_num -= 26;
  	cout << char(s_num);
  }
  return 0;
}

Measured memory_bytes: 256
S = input()
T = input()
st = {}
ts = {}
for s, t in zip(S, T):
    if s in st and st[s] != t:
        print("No")
        exit()
    if t in ts and ts[t] != s:
        print("No")
        exit()
    st[s] = t
    ts[t] = s
print("Yes")


Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <complex>
#include <set>
using namespace std;

typedef complex<double> P;

#define EPS (1e-10)
#define EQ(a,b) ((abs((a)-(b)))<EPS)

int past[1001];
vector<int> G[1001];
P points[1001];
bool loud[2][1001];

/*
Ü¸£50ÈàÌXõ¯mðGbWÅñ¾Otðì¬
 éXõª­ºðI¦Ä©çAybæè¨¨­ÌÔª§ÁÄ¢éêÍA×Ú·ém[hÌXõª­ºÂ\
Ü½AXõÌ­ºÍAxb²ÆÉ¯ÉsíêéB
æÁÄA­ºI¹ãy/x+1ñÌ­º²ÆÉAÌ­ºªÂ\ÆÈéB
Ü½AÇÌæ¤ÈðÌ³Âè~ÜÈ¢©ðl¦éB
Ü¸AOñÜÅÉ¯¶­ºXõÌgÝí¹ÉoïÁ½©Ç¤©ðl¦éBi2^1000Êèà éÌÅA·×ÄÌóÔÍÛÅ«È¢j
*/

int main(){
	int t;
	cin>>t;
	while(t--){
		int n,x,y;
		int nx,ny;
		int a;
		cin>>n>>x>>y;
		cin>>nx>>ny;
		a=y/x+1;
		P np=P(nx,ny);
		for(int i=0;i<n;i++)G[i].clear();
		memset(loud,0,sizeof(loud));
		memset(past,0,sizeof(past));
		for(int i=0;i<n;i++){
			int ex,ey;
			cin>>ex>>ey;
			points[i]=P(ex,ey);
		}
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				double d=abs(points[i]-points[j]);
				if(EQ(d,50)||d<50){
					G[i].push_back(j);
					G[j].push_back(i);
				}
			}
		}
		set<int> st;
		for(int i=0;i<n;i++){
			double d=abs(points[i]-np);
			if(EQ(d,10)||d<10){
				loud[0][i]=true;
				past[i]=a;
				st.insert(i);
			}
		}
		// Åå2000ñV~[V
		int cnt;
		int cur=0;
		int nxt=1;
		set<set<int> > ssi;
		ssi.insert(st);
		for(cnt=0;;cnt++){
			set<int> s;
			memset(loud[nxt],0,sizeof(loud[nxt]));
			// »ÝtrueÈçÎA×Úm[hðtrueÉ·é
			bool fin=true;
			for(int i=0;i<n;i++){
				if(loud[cur][i]){
					fin=false;
					for(int j=0;j<(int)G[i].size();j++){
						int to=G[i][j];
						if(!loud[cur][to]&&past[to]<=0&&!loud[nxt][to]){
							s.insert(to);
							loud[nxt][to]=true;
							past[to]=a+1;
						}
					}
				}
			}
			if(fin){
				cout<<cnt*x<<endl;
				break;
			}
			else if(ssi.find(s)!=ssi.end()){
				cout<<"You're always welcome!"<<endl;
				break;
			}
			ssi.insert(s);
			for(int i=0;i<n;i++)past[i]--;
			swap(nxt,cur);
		}
		// goalsÂ\
//		if(cnt==100000)
//			cout<<"You're always welcome!"<<endl;
	}
	return 0;
}

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

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

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <cstdio>

using namespace std;


int H, W, D, Q;

int main() {

    cin >> H >> W >> D;
    vector<pair<int, int> > nums(90001);
    int A;
    for (int i = 0; i < H; i++) { 
        for (int j = 0; j < W; j++) {
            scanf("%d", &A);
            nums[A] = make_pair(i+1, j+1);
        }
    }
    vector<int> a(H*W+1, 0);
    for (int i = D+1; i <= D+D; i++) {
        for (int j = i; j < H*W+1; j+=D) {
            a[j] = abs(nums[j].first - nums[j-D].first) + abs(nums[j].second - nums[j-D].second);
        }
    }

    vector<int> s( H * W + 1, 0);

    for (int i = D+1; i <= D+D; i++) {
        for (int j = i; j < H*W+1; j+=D) {
            s[j] = a[j] + s[j-D];
        }
    }

    cin >> Q;
    int l, r;
    for (int i = 0; i < Q; i++) {
        scanf("%d %d", &l, &r);
        printf("%d\n", s[r] - s[l]);
    }

}


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

int main(void)
{
    int A,B,C,ans,M,x;
    cin >> A >> B >> C;

    M = max({A,B,C});

    for(int i = M;;i++){
        if((3*i)%2 == (A+B+C)%2){
            x = i;
            break;
        }
    }

    ans = (3*x-A-B-C)/2;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
int main () {
  int N;
  cin >> N;
  vector<int> data(N);
  int sum = 0, a;
  for(int i = 0; i < N; i++){
    cin >> data.at(i);
  }
  for(int i = 0; i < N; i++){
    cin >> a;
    sum += a;
  }
  for(int i = 0; i < N - 1; i++){
    cin >> a;
    for(int j = 0; j < N - 1; j++){
      if(data.at(j) == data.at(j + 1) - 1 && data.at(j) == i + 1)sum += a;
    }
  }
  cout << sum << endl;
  return 0;
}

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

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define DUMP(v) REP(aa, (v).size()) { cout << v[aa]; if (aa != v.size() - 1)cout << " "; else cout << endl; }
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll max(ll a, int b) { return max(a, ll(b)); }
ll max(int a, ll b) { return max(ll(a), b); }
ll min(ll a, int b) { return min(a, ll(b)); }
ll min(int a, ll b) { return min(ll(a), b); }

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	vi v(3);
	REP(i, 3)cin >> v[i];
	int ret = INF;
	do {
		int ans = 0;
		ans += abs(v[2] - v[1]);
		ans += abs(v[1] - v[0]);
		ret = min(ret, ans);
	} while (next_permutation(ALL(v)));
	cout << ret << endl;
}

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


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

    for (ll i = -200; i <=200; i++) {
    for (ll j = -200; j <=200; j++) {
        if ((pow(i, 5) - pow(j, 5)) == x) {
            cout << i << " " << j << endl;
            return 0;
        }
    }
    }
}


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

using namespace std;

int n[3], t;

int main() {
	cin >> n[0] >> n[1] >> n[2];
	t = n[0];
	n[0] = n[1];
	n[1] = t;
	t = n[0];
	n[0] = n[2];
	n[2] = t;
	for (int i = 0; i < 3; ++i)
		printf("%d ", n[i]);
	return 0;
}





Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
    int n,m;
    cin >> n >> m;
    string t = "WBR";
    vector<vector<int> > v(n,vector<int>(3,0));
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        for(int j = 0; j < m; j++){
            for(int k = 0; k < 3; k++)if(s[j] == t[k]){
                v[i][k]++;
            }
        }
    }
    int ans = n*m;
    for(int i = 1; i < n-1; i++)for(int j = i+1; j < n; j++){
        int cnt = 0;
        for(int x = 0; x < i; x++){
            cnt += v[x][1] + v[x][2];
        }
        for(int x = i; x < j; x++){
            cnt += v[x][0] + v[x][2];
        }
        for(int x = j; x < n; x++){
            cnt += v[x][0] + v[x][1];
        }
        ans = min(ans, cnt);
    }
    cout << ans << endl;
}



Measured memory_bytes: 3208
S = list(input())
T = list(input())
if len(S)<len(T):
    print("UNRESTORABLE")
else:
    S = S[::-1]
    T = T[::-1]
    k = 0
    l = 0
    for i in range(len(S)-len(T)+1):
        if S[i]=="?" or S[i]==T[0]:
            k = 0
            for j in range(len(T)):
                if S[i+j]=="?" or S[i+j]==T[j]:
                    k+=1
        if k==len(T):
            l = i
            break
    if k!=len(T):
        print("UNRESTORABLE")
    else:
        ans = []
        for i in range(len(S)):
            if l <= i and i < l+k:
                ans.append(T[i-l])
            elif S[i]=="?":
                ans.append("a")
            else:
                ans.append(S[i])
        print("".join(ans[::-1]))

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

const int INF = 0x3f3f3f3f;

int N, M;
vector<int> A, B;

void solve(){
    int smin = INF;
    int aans = -1, bans = -1;
    
    int os1 = accumulate(A.begin(), A.end(), 0);
    int os2 = accumulate(B.begin(), B.end(), 0);
    
    for(int a=0; a<N; a++){
        for(int b=0; b<M; b++){
            int s1 = os1 + B[b] - A[a];
            int s2 = os2 + A[a] - B[b];
            
            if(s1 == s2 && A[a] + B[b] < smin){
                smin = A[a] + B[b];
                aans = A[a];
                bans = B[b];
            }
        }
    }
    if(smin == INF)
        cout << -1 << endl;
    else
        cout << aans << " " << bans << endl;
}

int main(){
    while(cin >> N >> M, N|M){
        A.resize(N);
        B.resize(M);
        
        for(auto &v: A) cin >> v;
        for(auto &v: B) cin >> v;
        
        solve();
    }
}

Measured memory_bytes: 3144
N, M = map(int, input().split(' '))
H_ls = list(map(int, input().split(' ')))
edge, rst = [ [] for i in range(N) ], 0
for i in range(M):
    a, b = map(int, input().split(' '))
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)
for i in range(N):
    is_peak = True
    for j in edge[i]:
        if H_ls[i] <= H_ls[j]:
            is_peak = False
            break
    if is_peak:
        rst += 1
print(rst)

Measured memory_bytes: 29436
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#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--)
#ifdef LOCAL
#define debug(x) cerr << '[' << #x << " = " << (x) << "]\n"
#else
#define debug(x)
#endif

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<int> v(n), pref(n), suf(n);
	rep(i, 0, n) {
		cin >> v[i];
		pref[i] = v[i];
		suf[i] = v[i];
	}
	rep(i, 1, n) pref[i] = __gcd(pref[i - 1], pref[i]);
	per(i, 0, n - 1) suf[i] = __gcd(suf[i + 1], suf[i]);
	int ans = 1;
	rep(i, 0, n) {
		int p, s;
		if (i - 1 >= 0) p = pref[i - 1]; else p = suf[i + 1];
		if (i + 1 < n) s = suf[i + 1]; else s = pref[i - 1];
		ans = max(ans, __gcd(p, s));
	}
	cout << ans << '\n';
}

Measured memory_bytes: 1408
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String a = sc.next();
    String b = sc.next();
    String c = sc.next();
    int numA = 0;
    int numB = 0;
    int numC = 0;
    char present = 'a';
    String ans = "";
    while((numA <= a.length()) && (numB <= b.length()) && (numC <= c.length())) {
      if(present == 'a') {
        if(numA == a.length()) {
          ans = "A";
          break;
        }
        present = a.charAt(numA);
        numA++;
      } else if(present == 'b') {
          if(numB == b.length()) {
            ans = "B";
            break;
          }
          present = b.charAt(numB);
          numB++;
      } else {
          if(numC == c.length()) {
            ans = "C";
            break;
          }
          present = c.charAt(numC);
          numC++;
      }
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 23892
#include <bits/stdc++.h>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const long double PI  = acos(-1.0L);
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
#define chmax(a,b) a = (((a)<(b))?(b):(a))
#define chmin(a,b) a = (((a)>(b))?(b):(a))

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

signed main(){
	int n; cin>>n;
	vector<double> t(n),v(n); rep(i,n)cin>>t[i]; rep(i,n)cin>>v[i];
	double T=0; rep(i,n) t[i]*=2,T+=t[i];
	int l=0, r=0; vector<double> maxv(T+1,INF);
	maxv[0]=maxv[T]=0.0;
	reps(i,T/2){
		maxv[i]=maxv[i-1]+0.5;
		maxv[T-i]=maxv[T-i+1]+0.5;
	}
	rep(i,n){
		r+=t[i];
		reps(j,T){
			if(j<l) chmin(maxv[j],v[i]+(l-j)/2.0);
			else if(j>r) chmin(maxv[j],v[i]+(j-r)/2.0);
			else chmin(maxv[j],v[i]);
		}
		l+=t[i];
	}
	double ans=0.0;
	rep(i,T){
		// cerr<<maxv[i]<<' ';
		ans+=(maxv[i]+maxv[i+1])/2.0;
	}
	// cerr<<endl;
	ans/=2.0;
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 640
using System;

namespace PrimeNumber
{
    class Program
    {
        private static bool?[] arr = new bool?[1000000];

        private static bool Save(int n, bool b)
        {
            arr[n] = b;
            return b;
        }

        private static bool IsPrime(int n)
        {
            if (arr[n] != null) return (bool)arr[n];
            if (n == 2) return Save(n, true);
            if (n % 2 == 0) return Save(n, false);

            double l = Math.Sqrt(n);

            for (var i = 3; i <= l; i += 2)
                if (n % i == 0) return Save(n, false);
       
            return Save(n, true);
        }

        static void Main(string[] args)
        {
            int num;
            
            while (int.TryParse(Console.ReadLine(), out num))
            {
                var count = num >= 2 ? 1 : 0;
                for (var i = 3; i <= num; i+=2)
                    if (IsPrime(i)) count++;
                Console.WriteLine(count);
            }
        }
    }
}


Measured memory_bytes: 11108
#include <bits/stdc++.h>
#define int long long
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define rep(i,l,r) for(int i=l;i<r;i++)
#define bep(i,l,r) for(int i=l;i>=r;i--)
#define ld long double
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define el '\n'
#define sz(s) s.size()
#define all(v) v.begin(),v.end()
#define mii map<int,int>
#define mr  make_pair
using namespace std;
int MOD = 1e9+7;
int inf = 1e18;
const int N = 5e5+999;
//int powmod(int a,int b) {int res=1;if(a>=mod)a%=mod;for(;b;b>>=1){if(b&1)res=res*a;if(res>=mod)res%=mod;a=a*a;if(a>=mod)a%=mod;}return res;}

signed main()
{
    io
    int tt = 1;
    //cin>>tt;
    while(tt--)
    {
      int n;
      cin>>n;
      map<string,int> mp;
      string s;
      while(n--)
      {
          cin>>s;
          mp[s]++;
      }
      set<string> st;
      int maxx = 0;
      for(auto x:mp)
      {
          maxx = max(maxx,x.ss);
      }
      for(auto x:mp)
      {
          if(x.ss==maxx)
            st.insert(x.ff);
      }
      for(auto x:st)
        cout<<x<<el;
    }
   return 0;
}


Measured memory_bytes: 33280
"""
# 標準入力取得
## 文字列
 = sys.stdin.readline().rstrip()
 = list(sys.stdin.readline().rstrip())

## 数値
 = int(sys.stdin.readline())
 = map(int, sys.stdin.readline().split())
 = list(map(int, sys.stdin.readline().split()))
 = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]
"""

import math
import sys
import itertools
import queue
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

if __name__ == "__main__":
    btc_rate = 380000
    total = 0
    N = int(sys.stdin.readline())
    for _ in range(N):
        x, u = sys.stdin.readline().split()
        if u == 'JPY':
            total += int(x)
        else:
            total += (float(x) * btc_rate)
    print(total)



Measured memory_bytes: 5196
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<sstream>
#include<iostream>
using namespace std;
int main(void){

    int ans = 0,n = 5;
    while(n--){
        int x;
        cin>>x;
        ans += max(x,40)/5;
    }
    cout<<ans<<endl;


    return 0;
}

Measured memory_bytes: 1160
def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    c = 0#最も末尾側までLCPを求めたインデックス
    for i in range(1, n):
        #i番目からのLCPが以前計算したcからのLCPに含まれている場合
        if i+LCP[i-c] < c+LCP[c]:
            LCP[i] = LCP[i-c]
        else:
            j = max(0, c+LCP[c]-i)
            while i+j < n and S[j] == S[i+j]: j+=1
            LCP[i] = j
            c = i
    LCP[0] = n
    return LCP

x=int(input())

s=input()
ans=0

for i in range(x):
    t=s[i:]
    lst=Z_algo(t)
    for i,v in enumerate(lst):
        cnt=min(i,v)
        ans=max(ans,cnt)


print(ans)


Measured memory_bytes: 79504
#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define RREP(i,a,b) for(int i=(a);i>=(b);i--)
#define pq priority_queue
#define P pair<int,int>
#define P2 pair<int,P>
#define P3 pair<int,P2>
typedef long long ll; typedef long double ld;
using namespace std;
const int INF=1e9, MOD=1e9+7, around[]={0,1,1,-1,-1,0,-1,1,0,0};
const ll LINF=1e18;
const ld PI=abs(acos(-1));
int n,a[100010];

int main(){
	cin >> n;
	REP(i,0,n) cin >> a[i];
	sort(a,a+n);
	
	int c=0; vector<P> vec;
	vec.push_back(P(a[0],1));
	REP(i,0,n-1){
		if(a[i]==a[i+1]) vec[c].second++;
		else vec.push_back(P(a[i+1], 1)),c++;
	}
	
	int s=0;
	REP(i,0,vec.size()){
		if(vec[i].second>vec[i].first){s+=vec[i].second-vec[i].first;}
		else if(vec[i].second<vec[i].first){s+=vec[i].second;}
	}
	
	cout << s << endl;
	return 0;
}


Measured memory_bytes: 1784
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong unsigned long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

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

int main(){
  llong L;cin>>L;
  llong R;cin>>R;
  llong m =INF;
  if(R-L >= 2019){
    cout << 0<<endl;
  }else if (L% 2019 > R%2019){
    cout <<0<<endl;
  }else{
    FOR(i,L%2019,R%2019){
      FOR(j,i+1,R%2019+1){
        if(m > (i*j)% 2019)m =(i*j)% 2019;
      }
    }
    cout << m <<endl;
  }
}


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

using namespace std;
inline int read(){int w=1,s=0;char ch=getchar();while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}return w*s;}
int col[100010],n,ans; 
int main()
{
	n=read();
	for(register int i=1;i<=n;++i) col[i]=read();
	int k=0;
	for(register int i=1;i<=n;++i)
	{
		if(col[i]==col[i-1]) ++k;
		else 
		{
			ans+=(k+1)/2;
			k=0;
		}
	}
	cout<<ans+(k+1)/2<<"\n";
	return 0;
}


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

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

int main(void) {
    int h, w;
    string a[100], line = "";

    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> h >> w;
    REP(i, h) {
        cin >> a[i];
    }
    REP(i, w + 2) {
        line += "#";
    }

    cout << line << "\n";
    REP(i, h) {
        cout << "#" << a[i] << "#" << "\n";
    }
    cout << line << "\n";
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
typedef long long ll;
#define pb push_back
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}
const double PI=acos(-1);

void solve(){
    ll n; cin >> n;
    vector<ll> h(n);

    REP(i, n){
        cin >> h[i];
    }
    if(n == 1){
        Yes();
        exit(0);
    }

    bool flag = true;
    h[0]--;
    for(int i=1; i<n; i++){
        if(h[i] < h[i-1]){
            flag = false;
            break;
        }
        if(h[i]-1 >= h[i-1]) h[i]--;
        else continue;

    }
    if(flag) Yes();
    else No();
}

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

Measured memory_bytes: 1024
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;

#define EPS (1e-7)
ll choose2(ll n) {
  assert(n > 1);
  return n * (n - 1) / 2;
}

int main() {
  ll N;
  cin >> N;
  vector<ll> A(N);
  for_each(begin(A), end(A), [](auto& x) { cin >> x; });

  map<ll, ll> balls;
  for (const auto& x : A) {
    balls[x]++;  // 整数をカウントする。
  }

  map<ll, ll> comps;
  ll comp_sum = 0;
  // まずは完璧な場合を計算する
  for (const auto& x : balls) {
    auto num = x.first;
    auto count = x.second;
    if (count > 1) {
      comps[num] = choose2(count);
      comp_sum += comps[num];
    } else {
      comps[num] = 0;  // 存在することだけはメモする。
    }
  }

  // 順番に取り除いた場合を計算する
  for (const auto& x : A) {
    ll sum = 0;
    if (comps[x] == 0) {
      sum = comp_sum;
    } else if (balls[x] > 2) {
      sum = comp_sum - choose2(balls[x]) + choose2(balls[x] - 1);
    } else {
      sum = comp_sum - 1;
    }
    cout << sum << endl;
  }
  return 0;
}


Measured memory_bytes: 18944
# encoding: utf-8
N = int(input())
S = [input() for i in range(N)]

ACHMR = [0] * 5
idx = 0
for i, Si in enumerate(sorted(list(filter(lambda x: x[0] in "MARCH", S)))):
    # skip
    if i == 0:
        ACHMR[0] += 1
        Si_prev = Si
        head_prev = Si[0]
        continue
    elif Si[0] != head_prev: idx += 1
    # increment
    ACHMR[idx] += 1
    head_prev = Si[0]
    Si_prev = Si

# print("", ACHMR)

ans = 0
for code in range(2 ** 5):
    # code -> 0b?????
    code_tmp = code
    code_bin = [0] * 5
    for i in range(5):
        code_bin[i] = code_tmp % 2
        code_tmp = code_tmp >> 1
    # bit count
    if sum(code_bin) != 3: continue
    # add
    ans_tmp = 1
    for cnt, bit in zip(ACHMR, code_bin):
        if bit > 0: ans_tmp = ans_tmp * (cnt * bit)
    # print("#", code_bin, ans_tmp)
    ans += ans_tmp

print(ans)

Measured memory_bytes: 11728
N = int(input())
A = [0]+list(map(int,input().split()))+[0]

maxMoney = sum([abs(A[i+1]-A[i]) for i in range(N+1)])
for i in range(1,N+1):
  print(maxMoney-abs(A[i-1]-A[i])-abs(A[i+1]-A[i])+abs(A[i+1]-A[i-1]))

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

int N;
int d[100];
int main() {  
  cin >> N;
  rep(i,N) cin >> d[i];
  sort(d, d + N);
  int ans = 0, now = 0;
  rep(i,N) {
    if (now < d[i]) {
      now = d[i];
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
n = int(input())
As = input().split()
aa = 0
for i in range(n):
    a = int(As[i])
    As[i] = a
    if i == 0:
        aa += abs(a)
    else:
        aa += abs(a - As[i - 1])
aa += abs(As[n - 1])
for i in range(n):
    ans = aa
    if i == 0:
        ans  = ans - abs(As[0]) - abs(As[1] - As[0]) + abs(As[1])
    elif i == n- 1:
        ans  = ans - abs(As[n - 1]) - abs(As[n - 1] - As[n - 2]) + abs(As[n- 2])
    else:
        ans = ans - abs(As[i + 1] - As[i]) - abs(As[i] - As[i - 1]) + abs(As[i + 1] - As[i - 1])
    print(ans)

Measured memory_bytes: 12380
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;

int main()
{
  int n, t, a;
  cin >> n >> t >> a;

  int itr = 0;
  vector<int> h(n);
  for (auto &e : h)
    cin >> e;

  for (int i = 0; i < n; ++i)
  {
    double tmp = t - h[i] * 0.006;
    double tt = t - h[itr] * 0.006;
    if ((tmp - a) * (tmp - a) < (tt - a) * (tt - a))
    {
      itr = i;
    }
  }
  cout << itr + 1 << endl;

  return 0;
}


Measured memory_bytes: 256