akhauriyash/Code-Regression huggingface dataset:
N,K=map(int,input().split())
S=input()
initial=S[0]
S01=[]
if initial=='L':
    for s in S:
        if s=='L':
            S01.append(0)
        else:
            S01.append(1)
else:
    for s in S:
        if s=='R':
            S01.append(0)
        else:
            S01.append(1)
            
count=0
T01=[0]
flag=0
for n in range(N-1):
    left=S01[n]
    right=S01[n+1]
    if left==0 and right==1:
        flag=1
    if left==1 and right==0:
        flag=0
        count+=1
    
    if flag==0:
        T01.append(0)
    elif count<K:
        T01.append(0)
    else:
        T01.append(1)
    
            
point=0
for n in range(N-1):
    left=T01[n]
    right=T01[n+1]
    if left==right:
        point+=1

print(point)

Measured memory_bytes: 4980
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n; cin >> n;
  vector<int> x(n), so(n);
  REP(i, n) {
    cin >> x[i];
    so[i] = x[i];
  }
  sort(ALL(so));
  map<int, int> mp;
  REP(i, n/2) mp[so[i]] = so[n/2];
  FOR(i, n/2, n) mp[so[i]] = so[n/2-1];
  REP(i, n) cout << mp[x[i]] << '\n';
  return 0;
}


Measured memory_bytes: 12928
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

a, b, c = MAP()

if b-a == c-b:
	print("YES")
else:
	print("NO")


Measured memory_bytes: 5148
#include <stdio.h>
 
int n;
int ni[200],di[200];
int x[200]={0},y[200]={0};
int mx[4]={-1,0,1,0};
int my[4]={0,-1,0,1};
int max,mix,may,miy;
 
int main(void){
  int i,j;
  while(1){
    scanf("%d",&n);
    if(n==0)break;
    for(i=1;i<n;i++)scanf("%d%d",&ni[i],&di[i]);
    max=0;
    mix=0;
    may=0;
    miy=0;
    for(i=1;i<n;i++){
      x[i]=x[ni[i]]+mx[di[i]];
      y[i]=y[ni[i]]+my[di[i]];
      if(x[i]>max)max=x[i];
      if(x[i]<mix)mix=x[i];
      if(y[i]>may)may=y[i];
      if(y[i]<miy)miy=y[i];
    }
    printf("%d %d\n",max-mix+1,may-miy+1);
  }
  return 0;
}



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

int main(){
  int N,W;
  cin>>N>>W;

  int v[1000],w[1000];
  for(int i=0;i<N;i++)
  cin>>v[i]>>w[i];

  int DP[N+1][W+1];
  for(int j=0;j<=W;j++)
  DP[0][j]=0;

  for(int i=1;i<=N;i++)
    for(int j=0;j<=W;j++)
      if(j<w[i-1])
        DP[i][j]=DP[i-1][j];
      else{
        if(DP[i-1][j]>DP[i-1][j-w[i-1]]+v[i-1])
          DP[i][j]=DP[i-1][j];
        else
          DP[i][j]=DP[i-1][j-w[i-1]]+v[i-1];
      }

      cout<<DP[N][W]<<endl;

      return 0;

}



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

int main () {
  
  int N;
  cin >> N;
  
  vector<long long> a(N);
  for (int i = 0; i < N; i++) cin >> a[i];
  
  set<int> S;
  map<int, int> MAP;
  
  for (int i = 0; i < N; i++) {
    if (!S.count(a[i])) S.insert(a[i]);
    MAP[a[i]]++;
  }
  
  if (S.size() == 3) {
  
    vector<int> num(3);
  
    for (int i = 0; i < 3; i++) {
      num[i] = *rbegin(S);
      S.erase(num[i]);
    }
  
    int b = num[0] ^ num[1];
  
    if (MAP[num[0]] != MAP[num[1]] || MAP[num[1]] != MAP[num[2]] || b != num[2]) {
      cout << "No" << endl;
      return 0;
    }
  
    cout << "Yes" << endl;
    return 0;
  }
  
  if (S.size() == 2) {
    
    vector<int> num(2);
  
    for (int i = 0; i < 2; i++) {
      num[i] = *rbegin(S);
      S.erase(num[i]);
    }
    
    if (num[1] == 0 && MAP[num[0]] == 2 * MAP[num[1]]) {
      cout << "Yes" << endl;
      return 0;
    }
    
    if (num[0] == 0 && MAP[num[1]] == 2 * MAP[num[0]]) {
      cout << "Yes" << endl;
      return 0;
    }
    
    else {
      cout << "No" << endl;
      return 0;
    }
  }
  
  if (S.size() == 1) {
    
    if (*rbegin(S) == 0) {
      cout << "Yes" << endl;
      return 0;
    }
    
    else {
      cout << "No" << endl;
      return 0;
    }
  }
  
  cout << "No" << endl;
  
  return 0;
  
}

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

int main() {
  string S;
  cin >> S;

  for(int i = 0; i < S.size(); i++){
    if(i % 2 == 0 && S.at(i) == 'L'){
      cout << "No" << endl;
      break;
    }
    if(i % 2 == 1 && S.at(i) == 'R'){
      cout << "No" << endl;
      break;
    }
    if(i == S.size() - 1)
      cout << "Yes" << endl;
  }
}


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

int main() {
	int N, A[100] = {};
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}
	sort(A, A + N);
	cout << A[N - 1] - A[0];
}


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

int main() {
  string S;
  cin >> S;
  int count=0;
  for (int i=0; i<S.size()-1; i++) {
    if (S[i] != S[i+1]) {
      count++;
    }
  }
  cout << count << endl;
}

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

int main(){
    int A,B,C,D; cin>>A>>B>>C>>D;
   if((A+B)>(C+D)){
     cout << "Left"<<endl;
   }else if((A+B)==(C+D)){
     cout << "Balanced"<<endl;;
   }else {
     cout <<"Right"<<endl;
   }
   return 0;
}


Measured memory_bytes: 256
macro_rules !input {(source =$s :expr ,$($r :tt ) *) =>{let mut iter =$s .split_whitespace () ;let mut next =||{iter .next () .unwrap () } ;input_inner !{next ,$($r ) *} } ;($($r :tt ) *) =>{let stdin =std ::io ::stdin () ;let mut bytes =std ::io ::Read ::bytes (std ::io ::BufReader ::new (stdin .lock () ) ) ;let mut next =move ||->String {bytes .by_ref () .map (|r |r .unwrap () as char ) .skip_while (|c |c .is_whitespace () ) .take_while (|c |!c .is_whitespace () ) .collect () } ;input_inner !{next ,$($r ) *} } ;}
macro_rules !input_inner {($next :expr ) =>{} ;($next :expr ,) =>{} ;($next :expr ,$var :ident :$t :tt $($r :tt ) *) =>{let $var =read_value !($next ,$t ) ;input_inner !{$next $($r ) *} } ;}
macro_rules !read_value {($next :expr ,($($t :tt ) ,*) ) =>{($(read_value !($next ,$t ) ) ,*) } ;($next :expr ,[$t :tt ;$len :expr ] ) =>{(0 ..$len ) .map (|_ |read_value !($next ,$t ) ) .collect ::<Vec <_ >>() } ;($next :expr ,chars ) =>{read_value !($next ,String ) .chars () .collect ::<Vec <char >>() } ;($next :expr ,usize1 ) =>{read_value !($next ,usize ) -1 } ;($next :expr ,$t :ty ) =>{$next () .parse ::<$t >() .expect ("Parse error" ) } ;}

fn main() {
   input! {
      n: usize,
      a: [usize; n]
   }
   let mut x = vec![0; 1e5 as usize +2];
   for a in a {
      if a!=0 {
         x[a-1] += 1;
      }
      x[a] += 1;
      x[a+1] += 1;
   }
   let mut ans = 0;
   for x in x {
      ans = std::cmp::max(ans, x);
   }
   println!("{}", ans);
}


Measured memory_bytes: 4352
n, x = map(int, input().split())

p = [0] * -~n
l = [0] * -~n

p[0] = 1
l[0] = 1
for i in range(1, n + 1):
    p[i] = p[i - 1] * 2 + 1
    l[i] = l[i - 1] * 2 + 3

# バーガーの長さは奇数


def rec(m, y):
    if y <= 0:
        return 0
    if m == 0:
        return 1 if y > 0 else 0
    h = l[m] // 2  # レベルmの半分より左側の長さ
    if h < y:  # 真ん中含む
        return 1 + p[m - 1] + rec(m - 1, y - h - 1)
    else:
        return rec(m - 1, y - 1)


print(rec(n, x))


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



int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    	int h, w, k;
	scanf("%d%d%d", &h, &w, &k);
	int x1, y1, x2, y2;
	scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
	char maze[h][w];
	int dis[h][w];
	for (int i=0; i<h; i++) {
		for (int j=0; j<w; j++) {
			scanf(" %c", &maze[i][j]);
			dis[i][j] = INT_MAX;
		}
	}
 
	x1--;
	y1--;
	x2--;
	y2--;
 
	const int dir[4][2] = {{-1,0}, {0,-1}, {1,0}, {0,1}};
	queue<pair<int, int> > q;
	dis[x1][y1] = 0;
	q.push({x1, y1});
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
 
		for (int i=0; i<4; i++) {
			int nx = x;
			int ny = y;
			int nd = dis[x][y]+1;
			for (int j=1; j<=k; j++) {
				nx += dir[i][0];
				ny += dir[i][1];
 
				if (nx<0 || nx>=h || ny<0 || ny>=w || '@'==maze[nx][ny] || dis[nx][ny]<nd) {
					break;
				}
				if (dis[nx][ny]>nd) {
					dis[nx][ny] = nd;
					q.push({nx, ny});
				}
			}
		}
	}
 
	int ans = dis[x2][y2];
	printf("%d\n", (INT_MAX==ans ? -1 : ans));
 
	return 0;
}


Measured memory_bytes: 9208
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int MOD = 1e9+7, MAX = 1e9, larg = 1e5, INF = -1e9;
long long A,B,C,D,E,F,G,H,I,J,K,L,N,M,O,P,Q,R,S,T,U,V,W,X,Y,Z;
long long max_value = 0, max_index = 0;
long long min_value = MAX, min_index = 0;
long long sum = 0;

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

int main() {
    cin >> D >> N;
    int num = 1;
    rep(i, D) num *= 100;
    if(N != 100) cout << num * N;
    else cout << num * (N+1);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char a[1009],b[1009],c[1009];
int main(){
    char x;
    int x1=-1,x2=-1,x3=-1;
    cin>>a>>b>>c;
    int al=strlen(a);
    int bl=strlen(b);
    int cl=strlen(c);
    x='a';
    while(1)
    switch(x){
        case 'a':{
            x1++;
            x=a[x1];
            if(x1==al) x=1;
            break;
        }
        case 'b':{
            x2++;
            x=b[x2];
            if(x2==bl) x=2;
            break;
        }
        case 'c':{
            x3++;
            x=c[x3];
            if(x3==cl) x=3;
            break;
        }
        default:{
            //cout<<x<<endl;
            if(x==1) cout<<'A';
            else if(x==2) cout<<'B';
            else if(x==3) cout<<'C';
            goto l;
        }
    }
    l:;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n; cin >> n;
    string s, t; cin >> s >> t;
    vector<ll> dp(30, 0);
    dp[s[0] - 'a'] = 1;
    for(int i = 1; i < n - 1; i++)
    {
        dp[s[i] - 'a'] += dp[t[i] - 'a'];
        dp[s[i] - 'a'] %= MOD;
    }
    cout << dp[t[n - 1] - 'a'] << endl;
    return 0;
}


Measured memory_bytes: 3320
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int N;
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        int[] A = new int[N+1];
        for(int i = 1 ; i < N ; i++)
        {
            A[sc.nextInt()]++;
        }
        for(int i = 1 ; i <= N ; i++)
        {
            System.out.println(A[i]);
        }


    }
}


Measured memory_bytes: 60488
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}


const int INF = 1001001001;

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

int n;
cin >> n;
vector<int> a(n);
rep(i,n) cin >> a[i];
int pre = -999;
rep(i,n) {
    if (pre <= a[i]-1) {
        pre = a[i]-1;
    } else if (pre == a[i]) {
        pre = a[i];
    } else {
        puts("No");
        return 0;
    }
}
puts("Yes");

return 0;
}

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

int main()
{
    int A, B, C;
    cin >> A >> B >> C;
    vector<int> ans = {0, 0, 0};
    ans[0] = A;
    ans[1] = B;
    ans[2] = C;
    sort(ans.begin(), ans.end());
    if (ans[0] == 5 && ans[1] == 5 && ans[2] == 7)
    {
        cout << "YES";
        return 0;
    }
    cout << "NO";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/trie_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
using ll = long long;
const int mxn=405;
const ll INF=2e18+2;
int n;
int a[mxn];
ll dp[mxn][mxn];
ll sum[mxn];
ll getsum(int l,int r)
{
    return(sum[r]-sum[l-1]);
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    for (int l=n;l>=1;l--)
    for (int r=l;r<=n;r++)
    {
        dp[l][r]=INF;
        if (l==r) dp[l][r]=0;
        else
        for (int i=l;i<=r;i++)
        {
            dp[l][r]=min(dp[l][r],dp[l][i]+dp[i+1][r]+getsum(l,r));
        }
    }
    cout<<dp[1][n];
}


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

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
#define dline    cerr << __LINE__ << endl;

using ll = long long;
template<class T, class U> using P = pair<T,U>;
template<class T> using Heap = priority_queue<T>;
template<class T> using heaP = priority_queue<T,vector<T>,greater<T>>;
template<class T,class U> using umap = unordered_map<T,U>;
template<class T> using uset = unordered_set<T>;

template<class T>
bool ChangeMax(T&a,const T&b){
  if(a >= b) return false;
  a = b;    return true;
}

template<class T>
bool ChangeMin(T&a,const T&b){
  if(a <= b) return false;
  a = b;    return true;  
}

template<class T, size_t N, class U>
void Fill(T (&a)[N], const U&v){
    fill((U*)a,(U*)(a+N),v);
}

template<class T>
istream& operator >> (istream&is, vector<T>&v){
  for(auto&e:v)is >> e;
  return is;
}

int main(){
  int k; cin >> k;
  string s; cin >> s;
  if((int)s.size() <= k)cout << s << endl;
  else cout << s.substr(0,k) + "..." << endl;
  return 0;
}


Measured memory_bytes: 3636
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

'''
1,2,3,4,5,6,7,8,9,10,11,12,21,22,23,32,33,34,43,44,45,54,55,56,65,66,67,76,77,78,87,88,89,98,99,100 (36)
101,110,111,112,121,122,123,210,211,212,221,222,223,232,233,234,

1
10
11
12
100
101
110
111
112
121
122
123
1000
1001
1002


'''
#precomp:
nums = []
def precomp(i):
    temp = str(i)
    x=[-1,0,1]
    for j in range(3):
        foo = int(temp[-1])+x[j]
        if(foo>=0 and foo<=9):
            toadd = int(temp+str(foo))

            if (i > 3234566667):
                return
            nums.append(toadd)
            precomp(toadd)

for i in range(1, 10):
    nums.append(i)
    precomp(i)

nums.sort()

k = INT()

print(nums[k-1])

# k = INT()


Measured memory_bytes: 96080
#include<stdio.h>

int main(void){
    
    int i, temp;
    int x,y;
    
    for(i=1; ;i++){
        scanf("%d", &x);
        scanf("%d", &y);
        if((x == 0) && (y == 0)) break;
        if(x > y){
            temp = x;
            x = y;
            y = temp;
        } 
        printf("%d %d\n", x, y);
    }
    
    return 0;
}


Measured memory_bytes: 2040
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;

int main() {
    int A,B;
    cin>>A>>B;
    if((A+B)>=10) cout<<"error"<<endl;
    else cout<<A+B<<endl;
}

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

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

  sort(a.begin(), a.end());
  a.push_back(0);

  int ret = 0;
  vector<bool> p(a[n-1], true);
  for (int i = 0; i < n; i++) {
    if (!p[a[i]]) continue;
    if (a[i]==a[i+1]) p[a[i]] = false;
    int t = 2;
    while (a[i]*t<=a[n-1]) {p[a[i]*t] = false; t++;}
  }

  for (int i = 0; i < n; i++) {
    if (p[a[i]]) ret++;
  }

  cout << ret << endl;
  return 0;
}


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

int main(){
  int N,Q,count = 0;
  cin >> N >> Q;
  string str;
  cin >> str;

  vector<int> vec(N+1);
  for(int i = 1; i < N; i++){
    if(str.at(i-1) == 'A'){
      if(str.at(i) == 'C'){
        count ++;
      }
    }
    vec.at(i) = count;
  }
  vec.at(N) = vec.at(N-1);

  for(int i = 0; i < Q; i ++){
    int l,r;
    cin >> l >> r;
    cout << vec.at(r-1) - vec.at(l-1) <<endl;
   }

}


Measured memory_bytes: 1408
N = int(input())
array = []
for i in range(10**9):
    res = ''
    digit = 0
    while i:
        res = '0357'[i % 4] + res
        i //= 4
    if '3' in res and '5' in res and '7' in res and '0' not in res:
        res = int(res)
        if res > 10 ** 9:
            break
        array += [res]
array += [10**9]
for i in range(len(array)):
    if array[i] > N:
        print(i)
        exit()


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

#define ll long long

const ll MOD = 1000000007;

ll factorial(ll a) {
  if (a == 1) return 1;
  
  return (a * factorial(a-1)) % MOD;
}

int main() {
  ll N, M;
  cin >> N >> M;
  
  if (abs(N-M) > 1) {
    cout << 0 << endl;
  } else if (abs(N - M) == 1) {
    cout << (factorial(max(M, N)) * factorial(min(M,N))) % MOD << endl;
  } else {
    cout << (2 * factorial(N) * factorial(M)) % MOD << endl; 
  }
  
  
  
}

Measured memory_bytes: 5040
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        int d = x / y;
        int r = x % y;
        double f = (double)x / y;
        System.out.println(d+" "+r+" "+String.format("%.5f", f));
    }
}


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

// 総数を1000000007（素数）で割った余り
const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

int main(){
    int n;
    cin >> n;
    map<string, int> sm;
    rep(i, n) {
        string s;
        cin >> s;
        sort(all(s));
        sm[s]++;
    }
    ll ans = 0;
    for (auto p : sm) {
        int i = p.second;
        ans += ll(i) * (i-1) / 2;
    }
    cout << ans << endl;
    return 0;
}


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

int main() {
  long q, h, s, d, n;
  long ans = 0;

  cin >> q >> h >> s >> d >> n;

  if (q * 8 > d && h * 4 > d && s * 2 > d) {
    ans += n / 2 * d;
    n %= 2;
  }
  if (q * 4 > s && h * 2 > s) {
    ans += n / 1 * s;
    n = 0;
  }
  if (q * 2 > h) {
    ans += n * 2 * h;
    n = 0;
  }
  cout << ans + n * 4 * q;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e9+7;
int mod = 1e9+7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int A,B,C,D,E,F;
int ans1 = 0;
int ans2 = 1;
signed main() {
    cin >> A >> B >> C >> D >> E >> F;
    A*=100;B*=100;
    for(int i = 0; i <= F; i+=A) {
        for(int j = 0; i+j <= F; j+=B) {
            int X = min(F-i-j,(i+j)/100*E);
            for(int k = 0; k <= X; k+=C) {
                for(int l = 0; k+l <= X; l+=D) {
                    if(ans1*(i+j+k+l) <= (k+l)*(ans1+ans2)) {
                        ans1 = k+l;
                        ans2 = i+j;
                    }
                }
            }
        }
    }
    if(ans1 == 0 && ans2 == 1) {
        cout << 0 << " " << 0 << endl;
        return 0;
    }
    cout << ans1+ans2 << " " << ans1 << endl;
}


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


const int maxn=1e6+5;
int isprime[maxn];

void rest()
{
  int arr[2]={3,5};
  for(int i=0;i<2;i++)
  {
    if(!isprime[arr[i]])
    {
      for(int j=arr[i];j<=maxn;j+=arr[i])
      {
        if(!isprime[j])
            isprime[j]=1;
      }
    }
  }
}

int main()
{


     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
    rest();
    int t=1;
    while(t--)
    {
      
      int count;
      cin>>count;
      long long int ans=0;
      for(int i=1;i<=count;i++)
      {
        ans+=isprime[i]==1?0:i;
      }
      cout<<ans<<endl;

    }

return 0;

}

Measured memory_bytes: 7560
#include <stdio.h>

int main(void)
{
	int i, j, H, W;
	
	while(1) {
	
	scanf("%d %d", &H, &W);
	if (H ==0 && W == 0) break;
	
	for (i = 1; i <= H; i++) {
		for (j = 1; j <= W; j++) {
			if ((i + j) % 2 == 0) printf("#");
			else
			printf(".");
		}
		printf("\n");
	}
	printf("\n");
	
	}
						
	return 0;
}

Measured memory_bytes: 572
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<deque>
#include<math.h>
#include<functional>
#include<cassert>
using namespace std;
#define ll long long
int main(){
    ll a,b,c,d,e;
    cin >> a >> b >> c >> d >> e;
    ll f=min({(a+9)%10,(b+9)%10,(c+9)%10,(d+9)%10,(e+9)%10})+1;
    cout << (a-1)/10*10+(b-1)/10*10+(c-1)/10*10+(d-1)/10*10+(e-1)/10*10+40+f <<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
#include<string>
using namespace std;
int main() {
	int N, A, B;	cin >> N >> A >> B;
	int num;
	int sum;
	int ans = 0;
	for (int i = 1; i <= N; ++i) {
		num = i;
		sum = 0;
		while (num) {
			sum += num % 10;
			num /= 10;
		}
		if (sum >= A && sum <= B) {
			ans += i;
		}
	}
	cout << ans;
	cin >> A;
}

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

int main(){
  int N, M; cin >> N >> M;
  vector<int> H(M);
  for(int i=0; i<M; i++){
    cin >> H[i];
  }
  int ans=0;
  vector<int> I(M-1);
  sort(H.begin(), H.end());
  if(N>=M){
    cout << ans << endl;
  }else{
    for(int i=0; i<M-1; i++){
      I[i] = H[i+1]-H[i];
    }
    sort(I.begin(), I.end());
    for(int i=0; i<M-N; i++){
      ans+=I[i];
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 1024
import string

N = int(input())
S = string.ascii_letters[:N] 
S_idx = {s:i for i, s in enumerate(S)}

def main(s, n):
    if n >= N:
        return print(s)
    idx =  S_idx[max(s)]
    for i in S[:idx+2]:
        main(s+i, n+1)
        
main('a', 1)

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

using namespace std;

typedef long long ll;

const int N = 1e8;
const int INF = 1e9;
const int MOD = 998244353;



int main() {
    int a, b, h;
    cin >> a >> b >> h;
    cout << h / 2 * (a + b);
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstdlib>
#include <string>
#include <iostream>
#include <queue>

using namespace std;

const char *X, *Y;
int X_length, Y_length;
bool alreadySeenTable[256];
int table_lcs[1001][1001];

int lcs(int x_begin, int y_begin) {
	int i, j, to;
	int max = 0;
	int v_lcs;
	
	if (table_lcs[x_begin][y_begin] != -1) {
		return table_lcs[x_begin][y_begin];
	}
	
	for (i = 0; i < 256; i++) {
		alreadySeenTable[i] = false;
	}
	i = x_begin;
	j = y_begin;
	to = Y_length-1;
	while(i <= X_length-1) {
		bool found = false;
		while (j <= to) {
			if (X[i] == Y[j]) {
				v_lcs = lcs(i + 1, j + 1) + 1;
				if (v_lcs > max) {
					max = v_lcs;
				}
				found = true;
				break;
			}
			else {
				j++;
			}
		}
		if (found == false) {
			i++;
			j = y_begin;
		}
		else {
			i++;
			to = j - 1;
			j = y_begin;
		}
	}
	return table_lcs[x_begin][y_begin] = max;
}

int main() {

	int N;
	cin >> N;
	string stringX, stringY;

	for (int i = 1; i <= N; i++) {
		for (int i = 0; i < 1001; i++) {
			for (int j = 0; j < 1001; j++) {
				table_lcs[i][j] = -1;
			}
		}
		cin >> stringX >> stringY;
		X = stringX.c_str();
		X_length = stringX.size();
		Y = stringY.c_str();
		Y_length = stringY.size();
		printf("%d\n", lcs(0, 0));
	}
	return 0;
}

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

const int MAXN = 100100;

int n;
int a[MAXN], p[MAXN], csum[2*MAXN];

bool good(int c){
  for(int i=0;i<n;i++){
    if (a[i] >= c) p[i] = 1;
    else p[i] = -1;
  }
  for(int i=0;i<2*MAXN;i++) csum[i] = 0;

  int cs = MAXN;
  csum[cs] = 1;
  int ctot = 1;
  long long res = 0;
  for(int i=0;i<n;i++){
    if(p[i] == -1){
      ctot -= csum[cs];
      cs--;
    }else{
      ctot += csum[cs+1];
      cs++;
    }
    res += ctot;
    csum[cs]++;
    ctot++;
  }
  return res * 2 >= (n*((long long)n+1))/2;
}

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

  int l=0, r=1e9;
  while(l<r){
    int mid = (l+r+1)/2;
    if(good(mid)) l = mid;
    else r = mid - 1;
  }
  cout << l << endl;
}


Measured memory_bytes: 1792
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353
a, b, _ = list(map(int, sys.stdin.buffer.readline().split()))
print(int(a * b // 2))


Measured memory_bytes: 13676
//
// Created by kuribohkute on 01/12/2018.
// https://dwacon5th-prelims.contest.atcoder.jp/tasks/dwacon5th_prelims_b

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long cc;

cc solve(const vector<cc> &a, const int &k) {

    cc ans = 0;

    auto temp = a;
    for (int i = 41; i >= 0; i--) {
        int cnt = 0;
        for (auto x: temp) {
            if ((x >> i) & 1) {
                ++cnt;
            }
        }
        
        if (cnt >= k) {
            int sz = (int)temp.size();
            for (int j = sz - 1; j >= 0; j--) {
                if (!((temp[j] >> i) & 1)) {
                    swap(temp[j], temp.back());
                    temp.pop_back();
                }
            }
        }
    }

    if ((int)temp.size() >= k) {
        ans = temp[0];
        for (auto x: temp) {
            ans &= x;
        }
    }

    return ans;
}

void read_inp() {
    int n, k;
    vector<int> a;

    cin >> n >> k;
    a.resize((unsigned  long)n);

    vector<cc> sub;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) {
        cc sum = 0;
        for (int j = i; j < n; j++) {
            sum += a[j];
            sub.push_back(sum);
        }
    }

    cout << solve(sub, k);
}

int main () {
//    freopen("input.in", "r", stdin);
//    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int test = 1;
    while (test--) {
        read_inp();
    }
    return 0;
}



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

int main() {
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int taka;
    if(c%b==0){
        taka=c/b;
    }else{
        taka=c/b+1;
    }
    int aoki;
    if(a%d==0){
        aoki=a/d;
    }else{
        aoki=a/d+1;
    }
    if(taka<=aoki){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
const int MX = 200005;

    // 整数スキャン（複数）
    /*
    int x;
    scanf("%d",&x);
    int y;
    scanf("%d",&y);
    int z;
    scanf("%d",&z);

    // n個の整数のスキャン
    /*
    ll a[n] = {};
    rep(i,n){
        scanf("%lld",&a[i]);
    }
    */

    // 文字列スキャン
    /*
    string s;
    cin >> s;
    */

    // n個の文字列スキャン
    /*
    vector<string> slist;
    rep(i,n){
        string s;
        cin >> s;
        slist.push_back(s);
    }
    */

int main() {
    int n;
    scanf("%d",&n);
    int t[n+1]={};
    int x[n+1]={};
    int y[n+1]={};
    srep(i,1,n+1){
        scanf("%d%d%d",&t[i],&x[i],&y[i]);
    }
    srep(i,1,n+1){
        if(abs(x[i]-x[i-1])+abs(y[i]-y[i-1])>t[i]-t[i-1]){
            puts("No");
            return 0;
        }else{
            if((abs(x[i]-x[i-1])+abs(y[i]-y[i-1]))%2 != (t[i]-t[i-1])%2){
                puts("No");
                return 0;
            }
        }
    }

    puts("Yes");
    return 0;
}
 
 


Measured memory_bytes: 1408
import itertools
import math
import fractions
import functools
import copy

n, l = map(int, input().split())
aji = []
for i in range(1,n+1):
    aji.append(l+i-1)

minimum = min(aji)
maximum = max(aji)

if minimum <= 0 and maximum >= 0:
    print(sum(aji))
    quit()
if minimum <= 0 and maximum <= 0:
    print(sum(aji)-maximum)
    quit()
if minimum >= 0 and maximum >= 0:
    print(sum(aji)-minimum)

Measured memory_bytes: 63980
#include <iostream>
#include <math.h>
#include <string>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int ctoi(const char c){
  switch(c){
    case '0': return 0;
    case '1': return 1;
    case '2': return 2;
    case '3': return 3;
    case '4': return 4;
    case '5': return 5;
    case '6': return 6;
    case '7': return 7;
    case '8': return 8;
    case '9': return 9;
    default : return -1;
  }
}

int main(){
  string a;
  int sum=0;
  int flag=0;
  vector<int> v;
  cin >>a;
  for(int i=0; i<a.size(); i++){
  	v.push_back(ctoi(a[i]));
  }
  int length;
  length=v.size();
  while(1){
  	int tmp;
  	tmp=v.at(0);
  	for(int i=0; i<v.size();i++){
  	  if(tmp!=v.at(i)){
  	  	if(v.size()!=2){
  	  	  v.erase(v.begin()+i-1);
  	  	  v.erase(v.begin()+i-1);
  	  	  sum+=2;
  	  	  flag=1;
  	  	  break;
  	    }else{
  	      sum+=2;
  	      flag=0;
  	      break;
  	    }
  	  }else{
  	  	flag=0;
  	  	tmp=v.at(i);
  	  }
  	}
  	if(flag==0){
  		break;
  	}
  }
  cout <<sum<<endl;
  return 0;
}

Measured memory_bytes: 1020
import sys

input=sys.stdin.readline

N,M=map(int,input().split())
hen=[]
for i in range(0,M):
    a,b,length=map(int,input().split())
    hen.append((a-1,b-1,length))

shortest=[[10**20 for i in range(0,N)] for j in range(0,N)]

for i in range(0,M):
    a,b,length=hen[i]
    shortest[a][b]=length
    shortest[b][a]=length

for k in range(0,N):
    for i in range(0,N):
        for j in range(0,N):
            shortest[i][j]=min(shortest[i][j],shortest[i][k]+shortest[k][j])

count=0
for i in range(0,M):
    a,b,length=hen[i]
    if length!=shortest[a][b]:
        count+=1

print(count)

Measured memory_bytes: 45676
code = r"""
# distutils: language=c++
# distutils: include_dirs = [/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
from libcpp cimport *

cdef extern from "/opt/atcoder-stl/atcoder/fenwicktree.hpp" namespace "atcoder":
    cdef cppclass fenwick_tree[T]:
        fenwick_tree()
        fenwick_tree(int n)
        void add(int a, T x)
        T sum(int l, int r)

import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())
cdef fenwick_tree[long] bit 
bit = fenwick_tree[long](N)

A = list(map(int, input().split()))
for i, a in enumerate(A):
    bit.add(i, a)

for _ in range(Q):
    t, u, v = map(int, input().split())
    if t == 0:
        bit.add(u, v)
    else:
        print(bit.sum(u, v))

"""
import os
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

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

#define MOD 1000000007
#define si(x) scanf("%d",&x);
#define sii(x,y) scanf("%d%d",&x,&y);
#define siii(x,y,z) scanf("%d%d%d",&x,&y,&z);
#define pi(x) printf("%d",x);
#define pii(x,y) printf("%d%d",x,y);
#define piii(x,y,z) printf("%d%d%d",x,y,z); 
#define sl(x) scanf("%lld",&x);
#define sll(x,y) scanf("%lld%lld",&x,&y);
#define slll(x,y,z) scanf("%lld%lld%lld",&x,&y,&z);
#define pl(x) printf("%lld",x);
#define pll(x,y) printf("%lld%lld",x,y);
#define plll(x,y,z) printf("%lld%lld%lld",x,y,z);  

#define ll long long
#define mp make_pair
#define pb push_back
#define pp pop_back
#define nl printf("\n");
#define sf scanf
#define pf printf
#define rep(i,n) for(int i=0;i<n;i++)
#define repi(i,a,b) for(int i=a;i<b;i++)
#define vint vector<int> 
#define tci int t;scanf("%d",&t);while(t--)
int main()
{
    int n,a;
    sii(n,a)
    printf("%d",(n*n)-a);
  return 0;
}   

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main
{
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
    public static void main(String args[])
    {
        FastReader obj = new FastReader();
        String s = obj.next(),t = obj.next();
        int count = 0;
        for(int i=0;i<s.length();i++)
        {
            if(s.charAt(i)!=t.charAt(i))count++;
        }
        System.out.println(count);
    }
}


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

int main() {
	int H, W, c[10][10], A, count = 0;
	cin >> H >> W;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> c[i][j];
		}
	}
	for (int k = 0; k < 10; k++) {
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
			}
		}
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> A;
			if (A != -1) count += c[A][1];
		}
	}
	cout << count;
}

Measured memory_bytes: 256
#ifdef _WIN32
#include "stdc++.h"
#else
#include <bits/stdc++.h>
#endif

// 継承可能な型
template <class Type>
struct IN : Type
{
	IN()
	{
		std::cin >> *this;
	}
};

// 継承不可能な型
template <class Type>
struct IN_
{
	Type val;

	IN_()
	{
		std::cin >> val;
	}

	operator Type&()
	{
		return val;
	}

	IN_<Type>& operator=(const Type& _value)
	{
		val = _value;
		return *this;
	}
};

template <class Char, class Type>
std::basic_ostream<Char>& operator <<(std::basic_ostream<Char>& os, const IN_<Type>& value)
{
	return os << value.val;
}

template <class Char, class Type>
std::basic_istream<Char>& operator >>(std::basic_istream<Char>& is, IN_<Type>& value)
{
	return is >> value.val;
}

template <class Type>
void OUT(const Type& value)
{
	std::cout << value << std::endl;
}

template <class Type, class ... Args>
void OUT(const Type& value, const Args& ... args)
{
	std::cout << value << ' ';
	OUT(args...);
}

void Yes()
{
	OUT("Yes");
}
void No()
{
	OUT("No");
}

using ll = long long;
using inll = IN_<ll>;
using vll = std::vector<ll>;
using setll = std::set<ll>;
using msetll = std::multiset<ll>;
using instr = IN<std::string>;

#define FOR(i, m, n) for (ll (i) = (m); (i) < (n); ++(i))
#define REP(i, n) for (ll (i) = 0; (i) < (n); ++(i))
#define REPR(i, n) for (ll (i) = (n); (i) >= 0; --(i))
#define ITRREP(it, v) for (auto (it) = (v).begin(); (it) != (v).end(); ++(it))
#define ITRREPR(it, v) for (auto (it) = (v).rbegin(); (it) != (v).rend(); ++(it))
#define DIVUP(a, b) (((a) + (b) - 1) / (b))

void Main();

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

	Main();

#ifdef _DEBUG
	system("pause");
#endif

	return 0;
}

using namespace std;

//////////////////////////////

void Main()
{
	inll n;
	setll a;
	REP(i, n)
	{
		inll a_;
		a.insert(a_);
	}

	ll res1 = *(--a.end());

	ll old = -1;

	ITRREP(it, a)
	{
		if (min(old, res1 - old) >= min(*it, res1 - *it))
			return OUT(res1, old);
		old = *it;
	}

	auto tm = a.end();
	tm--;
	tm--;

	return OUT(res1, *tm);
}


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

using namespace std;

int N;
map<long long,int> id;
long long seq[100050];
int sz[100050];
vector<int> v[100050];
long long ans = 0;

void Serval(int pos,int dep,int lst)
{
	ans += dep;
	for(int i = 0;i < v[pos].size(); ++ i)
	{
		int nxt = v[pos][i];
		if(nxt != lst)
			Serval(nxt,dep + 1,pos);
	}
}

int main()
{
	scanf("%d",&N);
	for(int i = 1;i <= N; ++ i)
		scanf("%lld",&seq[i]),id[seq[i]] = i,sz[i] = 1;
	sort(seq + 1,seq + 1 + N);
	for(int i = N;i >= 2; -- i)
	{
		int delta = N - 2 * sz[id[seq[i]]];
		if(delta < 0)
		{
			printf("-1\n");
			return 0;
		}
		long long to_find = seq[i] - delta;
		if(!id.count(to_find))
		{
			printf("-1\n");
			return 0;
		}
		sz[id[to_find]] += sz[id[seq[i]]];
		v[id[seq[i]]].push_back(id[to_find]);
		v[id[to_find]].push_back(id[seq[i]]);
	}
	Serval(id[seq[1]],0,0);
	if(ans != seq[1])
	{
		printf("-1\n");
		return 0;
	}
	for(int i = 1;i <= N; ++ i)
	{
		for(int j = 0;j < v[i].size(); ++ j)
		{
			int nxt = v[i][j];
			if(nxt > i) printf("%d %d\n",i,nxt);
		}
	}
}

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

int main() {
  int n;
  cin >> n;
  vector <int> a(n);
  
  for (int i =0; i<n; i++){
    cin >> a[i];
  }
  
  int min=1000000000;
  int count=0;
  
  for (int i = 0; i<n; i++){
  while (a[i]%2 == 0){
    a[i] = a[i]/2;
      count ++;
  }
    if (count < min) {
      min = count;
    }
    count =0;
  }
  cout << min << endl;
   
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	float sum=0;
	 int a[n];
	 for(int i=0;i<n;i++)
	  {
	  	cin>>a[i];
	  	float k=a[i];
	  	sum=sum+1/k;
	  }
	 sum=1/sum;
	 cout<<sum;
 return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define PI 3.141592653589793238462643383279502884L
#define lli long long int
#define d double
#define mod 1000000007
#define mx 100001
using namespace std;
int main() {
	FIO;
	int n;
	cin>>n;
	vector<d> dp(n+1);//dp[i]->prob of getting exatly i heads.....
	d x;
	cin>>x;
	dp[0]=1-x;
	dp[1]=x;
	for(int i=2;i<=n;i++){
		cin>>x;
		vector<d> temp_dp=dp;
		dp[0]=temp_dp[0]*(1-x);
		for(int j=1;j<=i;j++){
			dp[j]=temp_dp[j]*(1-x)+temp_dp[j-1]*x;
		}
	}
	d ans=0;
	for(int i=(n+1)/2;i<=n;i++) ans+= dp[i];
	cout<<fixed<<setprecision(10)<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(),v.end()

int main() {
  string a;
  int b=0;
  cin >> a;
  if(a=="RRR"){b=3;}
  else if(a=="RRS"){b=2;}
  else if(a=="RSR"){b=1;}
  else if(a=="SRR"){b=2;}
  else if(a=="SSS"){b=0;}
  else{b=1;}
  
  cout << b << endl;
}



Measured memory_bytes: 3592
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Main {

	public static void main(String args[]) {
		Main col = new Main();
		Scanner sc = new Scanner(System.in);
		int input = sc.nextInt();
		List<Integer> number = new ArrayList<Integer>();
		number.add(input);
		int minimum = 1000000;
		for (int i = 1; i <= 1000000; i++) {
			int result = col.returnNumbers(number.get(i - 1));
//			System.out.println("i = "+i +" " +result);
			if (number.contains(result)) {
				minimum = i + 1;
				break;
			}
			number.add(result);
		}
		System.out.print(minimum);

	}

	public int returnNumbers(int x) {
		if (x % 2 == 0)
			return x / 2;
		else
			return 3 * x + 1;
	}
}


Measured memory_bytes: 23124
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cassert>
#define InfL 1000000000
#define InfLL 1000000000000000000LL
#define nmax_def 220000
#define mod 1000000007
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rrep(i,n) for(int (i)=(n-1);(i)>=(0);(i)--)
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<db> vd;

// ----- UnionFind -----

class UnionFind {
public:
	vi par;
	vi adjnum;
	int N;

	void UnionFind_ini(int Narg);
	int root(int x);
	void unite(int x, int y);
	bool same(int x, int y);
	int adjnum_func(int x);
	void solve();
};

void UnionFind::UnionFind_ini(int Narg) {
	N = Narg;
	adjnum.resize(N);
	par.resize(N);
	rep(i, N) {
		adjnum[i] = 1;
		par[i] = i;
	}
}

int UnionFind::root(int x) {
	if (par[x] == x)
		return x;
	par[x] = root(par[x]);
	return par[x];
}

void UnionFind::unite(int x, int y) {
	int rx = root(x);
	int ry = root(y);
	if (rx == ry)
		return;
	par[rx] = ry;
	adjnum[ry] += adjnum[rx];
	return;
}

bool UnionFind::same(int x, int y) {
	int rx = root(x);
	int ry = root(y);
	return rx == ry;
}

int UnionFind::adjnum_func(int x) {
	int rx = root(x);
	return adjnum[rx];
}

void UnionFind::solve() {
	int Narg, M, K;
	cin >> Narg >> M >> K;
	UnionFind_ini(Narg);
	vi ans(N, 0);
	rep(i, M) {
		int A, B;
		cin >> A >> B;
		A--;
		B--;
		unite(A, B);
		ans[A]--;
		ans[B]--;
	}
	rep(i, N) {
		ans[i] += adjnum[root(i)];
	}
	rep(i, K) {
		int A, B;
		cin >> A >> B;
		A--;
		B--;
		if (same(A, B)) {
			ans[A]--;
			ans[B]--;
		}
	}
	rep(i, N) {
		cout << ans[i] - 1 << " ";
	}
	cout << endl;
	return;
}

int main(void) {
	UnionFind graph;
	graph.solve();
	return 0;
}

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

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

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

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

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

using namespace std;

/* Some Libraries */

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin>>n;
    vll a(n);
    ll ans=0;
    rep(i,n) cin>>a[i];
    rep(i,n) ans^=a[i];
    rep(i,60){
        int cnt=0;
        rep(j,n)if(a[j]>>i&1) cnt++;
        if(cnt&1)rep(j,n) a[j]-=a[j]&(1LL<<i);
    }
    int k=0;
    RFOR(i,59,0){
        bool find=false;
        FOR(j,k,n-1)if(a[j]>>i&1){
            swap(a[k],a[j]);
            find=true;
            break;
        }
        if (!find) continue;
        rep(j,n)if(j!=k && a[j]>>i&1){
            a[j]^=a[k];
        }
        k++;
    }
    ll sum=0;
    rep(i,n) sum^=a[i];
    ans+=sum*2;
    cout<<ans<<"\n";
    return 0;
}


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


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

    int n;
    cin>>n;
    vector<int> a(n,0);
    for(int i=0; i<n; i++) {
        cin>>a[i];
    }
    if(n==2) {
        cout<<max(a[0],a[1]);
        return 0;
    }
    vector<int> g(3,0);
    g[0] = __gcd(a[0],a[1]);
    g[1] = __gcd(a[0],a[2]);
    g[2] = __gcd(a[1],a[2]);
   set<int> d;
    for(int i=0;i<3;i++){
        for(int j=1;j*j<=g[i];j++){
            if(g[i] % j == 0){
                d.insert(j);
                d.insert(g[i]/j);
            }
        }
    }

    int answer = 1;

    for(int val : d){
        int bad = 0;
        for(int i=0;i<n;i++){
            bad += a[i] % val > 0;
        }
        if(bad <= 1){
            answer = max(answer, val);
        }
    }
    cout<<answer;

    return 0;
}


Measured memory_bytes: 640