akhauriyash/Code-Regression huggingface dataset:
#![allow(unused)]

//input
//use std::io::Read;

//collections
//use std::collections::BTreeMap;
//use std::collections::BTreeSet;
use std::collections::HashMap;
//use std::collections::HashSet;


//入力マクロここから
//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
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,
        s: [String;n],
    }
    
    let mut dic:HashMap<String,u64> = HashMap::new();
    
    for e in s {
        if dic.contains_key(&e) {
            *dic.get_mut(&e).unwrap() += 1;
        } else {
            dic.insert(e, 1);
        }
    }
    
    let mut max_value:u64 = 0;

    for (key, value) in dic.iter() {
        if *value > max_value {
            max_value = *value;
        }
    }

    let mut ans:Vec<String> = Vec::new();

    for e in dic {
        if e.1 == max_value {
            ans.push(e.0);
        }
    }

    ans.sort();

    for e in ans {
        println!("{}", e);
    }
}

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

int main(){
    string s;
    cin>>s;
    for(int i=0;i<s.length();++i){
        if(s[i]=='?')cout<<'D';
        else cout<<s[i];
    }
    return 0;
}

Measured memory_bytes: 3708
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

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

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------
int N, K;
int x[100], y[100];

bool check(int top, int bottom, int right, int left) {
  int cnt = 0;
  rep(k, 0, N) {
    int cx = x[k];
    int cy = y[k];
    if (left <= cx && cx <= right && bottom <= cy && cy <= top) {
      ++cnt;
    }
  }

  return cnt >= K;
}

int main() {
  cin >> N >> K;
  rep(i, 0, N) { cin >> x[i] >> y[i]; }

  ll ans = numeric_limits<ll>::max();
  rep(i, 0, N) {
    rep(j, i, N) {
      rep(k, j, N) {
        rep(l, k, N) {
          ll top = max(y[i], max(y[j], max(y[k], y[l])));
          ll bottom = min(y[i], min(y[j], min(y[k], y[l])));
          ll left = min(x[i], min(x[j], min(x[k], x[l])));
          ll right = max(x[i], max(x[j], max(x[k], x[l])));

          if (check(top, bottom, right, left)) {
            chmin(ans, (top - bottom) * (right - left));
          }
        }
      }
    }
  }

  cout << ans << endl;
}


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

int calc(vector<vector<int>> &a){
	int i1, i2, j1, j2, k, l, ans = 0;
	for(i1 = 0; i1 < a.size(); i1++){
		for(i2 = i1; i2 < a.size(); i2++){
			for(j1 = 0; j1 < a[0].size(); j1++){
				for(j2 = j1; j2 < a[0].size(); j2++){
					int now = 0;
					for(k = i1; k <= i2; k++){
						for(l = j1; l <= j2; l++){
							now += a[k][l];
						}
					}
					ans += now % 2;
				}
			}
		}
	}
	return ans;
}

vector<vector<int>> make(int A, int B){
	int i, j;
	vector<vector<int>> ans(A, vector<int>(B, -1));
/*	if(A == 1){
		for(j = 0; j < B; j++){
			ans[0][j] = 1 - j % 2;
		}
		return ans;
	}
	if(B == 1){
		for(i = 0; i < A; i++){
			ans[i][0] = 1 - i % 2;
		}
		return ans;
	}
*/	if(A * B == 0){
		return ans;
	}
	vector<vector<int>> res = make(A / 2, B / 2);
/*	for(i = 0; i < A / 2; i++){
		for(j = 0; j < B / 2; j++){
			printf("%d", res[i][j]);
		}
		printf("\n");
	}
	printf("\n");
*/	for(i = 0; i < A; i++){
		ans[i][B / 2] = 0;
	}
	for(j = 0; j < B; j++){
		ans[A / 2][j] = 0;
	}
	ans[A / 2][B / 2] = 1;
/*	for(i = 0; i < A; i++){
		for(j = 0; j < B; j++){
			printf("%d", ans[i][j]);
		}
		printf("\n");
	}
	printf("\n");
*/	for(i = 0; i < A / 2; i++){
		for(j = 0; j < B / 2; j++){
			ans[i][j] = res[i][j];
			ans[A / 2 + 1 + i][j] = res[i][j];
			ans[i][B / 2 + 1 + j] = res[i][j];
			ans[A / 2 + 1 + i][B / 2 + 1 + j] = res[i][j];
		}
	}
/*	for(i = 0; i < A; i++){
		for(j = 0; j < B; j++){
			printf("%d", ans[i][j]);
		}
		printf("\n");
	}
	printf("\n");
*/	return ans;
}

int main(){
	int N, M, i, j;
	scanf("%d%d", &N, &M);
	vector<vector<int>> a((1 << N) - 1, vector<int>((1 << M) - 1, -1));
/*	for(i = 0; i < (1 << N) - 1; i++){
		for(j = 0; j < (1 << M) - 1; j++){
			a[i][j] = 1 - (i + j) % 2;
			scanf("%1d", &a[i][j]);
		}
	}
*/	a = make((1 << N) - 1, (1 << M) - 1);
//	printf("score = %d\n", calc(a));
//	return 0;
	for(i = 0; i < (1 << N) - 1; i++){
		for(j = 0; j < (1 << M) - 1; j++){
			printf("%d", a[i][j]);
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 9856
import scala.collection.mutable.ListBuffer
import scala.io.StdIn

object Main extends App {

  var target = "-1"
  val buff = ListBuffer.empty[String]
  while(target != "0"){
    target = StdIn.readLine()
    buff += target.foldLeft(0){ (acc, f) =>
      acc + f.toString.toInt
    }.toString
  }
  
  println(buff.dropRight(1).mkString(f"%n"))
}


Measured memory_bytes: 44316
N,K,Q = map(int, input().split())
A = []
for i in range(Q):
    A.append(int(input()))
    
List = [0 for i in range(N)]
for i in range(Q):
    List[A[i]-1] += 1
    
for i in range(N):
    if List[i] > Q-K:
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 8636
package main

import(
  "fmt"
)

func max( array []int , limit int  )int {
  max := 0
  for i := 0 ; i < len( array ) ; i++ {
    if max < array[i] && array[i] < limit {
      max = array[i]
    }
  }

  return max
}

func main(){
  var n int
  fmt.Scan( &n )
  array := make( []int , 0 , n )

  for i := 0 ; i < n ; i++ {
    var temp int
    fmt.Scan( &temp )
    array = append( array , temp )
  }

  limit := 1000
  dan := 0
  for i := 0 ; i < n ; i++ {
    max := max( array , limit )
    if 0 < max {
      dan++
      limit = max
    }
  }

  fmt.Print( dan )

}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl "\n"

int main()
{
  i64 N;
  cin >> N;
  vector<i64> A(N);
  for (i64 i = 0; i < N; i++)
    cin >> A[i];
  i64 ans = 1000, ka = 0;
  for (i64 i = 0; i < N; i++)
    if (i + 1 == N || A[i + 1] < A[i])
    {
      ans += ka * A[i];
      ka = 0;
    }
    else if (A[i] < A[i + 1])
    {
      ka += ans / A[i];
      ans -= ans / A[i] * A[i];
    }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3588
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int H = 210;

int n,h;
int deg[H*2];
int cnt[H*2];
int fa[H*2],siz[H*2];
bool bz[H*2],sef[H*2];

int getfather(int x){
	if (fa[x]==x)return fa[x];
	return fa[x]=getfather(fa[x]);
}

int main(){
	n=get();h=get();
	fo(i,0,h*2)fa[i]=i,siz[i]=1;
	fo(i,1,n){
		int a=get(),b=get(),c=get(),d=get();
		if (c)a=-c;
		if (d)b=d;else b=-b;
		a+=h;b+=h;
		int ta=getfather(a),tb=getfather(b);
		deg[a]++;deg[b]--;
		if (ta!=tb){
			fa[ta]=tb;
			siz[tb]+=siz[ta];
		}
		else sef[ta]=1;
	}
	bool ans=1;
	fo(i,0,h)if (deg[i]>0)ans=0;
	fo(i,h,2*h)if (deg[i]<0)ans=0;
	fo(i,0,h*2)bz[getfather(i)]|=(deg[i]!=0);
	fo(i,0,h*2)
	if (siz[i]>1&&getfather(i)==i&&!bz[i])ans=0;
	fo(i,0,h*2)
	if (siz[i]==1&&sef[i]&&getfather(i)==i)ans=0;
	if (ans)printf("YES\n");
	else printf("NO\n");
	return 0;
}

Measured memory_bytes: 384
#include <stdio.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef vector<vector<int>> v2int;
typedef vector<ll> vll;
typedef vector<vector<ll>> v2ll;
typedef list<int> liint;
typedef pair<int, int> pint;
const int INF = int(2e9);
const ll LINF = ll(2e9) * ll(2e9);
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b) { a > b ? : a = b; }
template<class T, class C> void chmin(T& a, C b) { a < b ? : a = b; }


ll func(ll N, ll L) {
    ll X = N - L;
    ll ret = (X / L) * 2 * L;
    ll L2 = X % L;
    if (L2 == 0) {
        return ret;
    }
    return ret + L + L2 + func(L, L2);
}

//bool is_first = true;
//ll func(ll X, ll Z) {
//    ll a;
//    if (is_first == true)
//        a = X / Z;
//    else
//        a = (X - Z) / Z;
//    is_first = false;
//    ll X2 = X % Z;
//    
//    ll ret = X + Z + 2 * a * Z + X2;
//    if (X2 == 0) {
//        return ret ;
//    }
//    ll Z2 = Z - X2;
//    return ret + func(X2, Z2);
//}

int main() {
    ll X, N;
    cin >> N >> X;
    cout << X + func(N, N - X) << endl;
    return 0;
}

Measured memory_bytes: 256
n=int(input())

jun=list(map(int,input().split()))
sat=list(map(int,input().split()))
add=list(map(int,input().split()))

ans=sum(sat)
for i in range(n-1):
    if jun[i+1]==jun[i]+1:
        ans+=add[jun[i]-1]


print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

long long n;
long long memo[305][305] = {0};
bool ch[305][305] = {0};
vector<pair<long long, pair<int, int>>> v;

long long solve();

int main() {
  cin >> n;
  for(int i = 0; i < n; ++i)
    for(int j = 0; j < n; ++j) cin >> memo[i][j];
  for(int i = 0; i < n; ++i)
    for(int j = i + 1; j < n; ++j)
      v.push_back(make_pair(memo[i][j], make_pair(i, j)));
  sort(v.begin(), v.end());
  cout << solve() << endl;
  return 0;
}

long long solve() {
  long long ans = 0;
  for(int k = 0; k < n; ++k)
    for(int i = 0; i < n; ++i)
      for(int j = 0; j < n; ++j)
        if(memo[i][j] > memo[i][k] + memo[k][j]) return -1;
  for(int i = 0; i < v.size(); ++i)
    if(!ch[v[i].se.fi][v[i].se.se]) {
      ch[v[i].se.fi][v[i].se.se] = 1;
      pair<long long, pair<int, int>> now = v[i];
      ans += now.fi;
      for(int j = 0; j < n; ++j)
        if(now.se.fi != j && now.se.se != j) {
          long long dis = now.fi;
          if(dis + memo[j][now.se.fi] == memo[now.se.se][j])
            ch[min(j, now.se.se)][max(j, now.se.se)] = 1;
          if(dis + memo[j][now.se.se] == memo[now.se.fi][j])
            ch[min(j, now.se.fi)][max(j, now.se.fi)] = 1;
        }
    }
  return ans;
}

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

using namespace std;

long long int GCD(long long int a, long long int b) {
    if(a<b) {
        long long int tmp=a;
        a = b;
        b = tmp;
    }
    
    if(b==0) {
        return a;
    }
    
    return GCD(b, a%b);
}

int main() {
    int N;
    long long int M;
    cin >> N >> M;
    vector<long long int> A(N);
    cin >> A[0];
    long long int lcm=A[0]/2;
    long long int po=0, tmpA=A[0]/2;
    while(tmpA%2==0) {
        tmpA /= 2;
        po++;
    }
    bool flag=true;
    for(int n=1; n<N; n++) {
        cin >> A[n];
        if(!flag) continue;
        if(lcm<M) {
            lcm *= (A[n]/2)/GCD(lcm, A[n]/2);
        } else {
            flag=false;
        }
        
        tmpA = A[n]/2;
        long long int tmpo=0;
        while(tmpA%2==0) {
            tmpA /= 2;
            tmpo++;
        }
        if(po!=tmpo) {
            flag=false;
        }
    }

    long long int ans=M/lcm;
    if(flag) {
        cout << (ans+1)/2 << endl;
    } else {
        cout << 0 << endl;
    }


    return 0;
    
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define endl "\n"
#define pb push_back
#define SZ(x) ((int)(x.size()))
#define FOR(i,s,n) for (ll i = (s); (i) < (n); ++i)
#define FORD(i,s,l) for (ll i = (s); (i) >= l; --i)
#define F first
#define S second
#define TC int __tc; cin >> __tc; FOR(case_num,1,__tc+1)
#define TEST(x,i) ((x)&(1ll<<(i)))
#define SET(x,i) ((x)|(1ll<<(i)))
#define FLIP(x,i) ((x)^(1ll<<(i)))
#define CLEAR(x,i) ((x)&~(1ll<<(i)))

const double pi = 4 * atan(1);
using namespace std;
typedef long long ll;

const ll MOD = 1000000007;
const int MAXN = 200005;

ll num[MAXN];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	
	for (int i = 0; i < n; i++){
		cin >> num[i];
	}
	
	sort(num,num+n,greater<ll>());
	
	ll ans = 0;
	ans+=num[0];	
	
	int j = 1;
	int c = 0;
	for (int i = 2; i < n; i++){
		ans+=num[j];
		c++;
		if (c == 2) {
			c = 0;
			j++;
		}
	}
	
	cout << ans << "\n";
	
}


Measured memory_bytes: 5200
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<ctime>
using namespace std;
#define int long long
struct RBST{
    struct node{
        node *lch,*rch;
        int val,sum,lazy,cnt;
        node(int val):val(val),sum(val),lazy(0),cnt(1){
            lch=rch=NULL;
        }
    };

    RBST():root(NULL){srand((unsigned)time(NULL));}
    node *root;

    int count(node *t){return !t?0:t->cnt;}
    int sum(node *t){return !t?0:t->sum;}

    node *update(node *t){
        if(!t)return t;
        if(t->lazy){
            t->val+=t->lazy;
            if(t->lch){
                t->lch->lazy+=t->lazy;
                t->sum+=count(t->lch)*t->lazy;
            }
            if(t->rch){
                t->rch->lazy+=t->lazy;
                t->sum+=count(t->rch)*t->lazy;
            }
            t->lazy=0;
        }
        t->cnt=count(t->lch)+count(t->rch)+1;
        t->sum=sum(t->lch)+sum(t->rch)+t->val;
        return t;
    }

    node *merge(node *a,node *b){
        if(!a)return b;
        if(!b)return a;

        if(rand()%(count(a)+count(b))<count(a)){
            a=update(a);
            a->rch=merge(a->rch,b);
            return update(a);
        }
        else{
            b=update(b);
            b->lch=merge(a,b->lch);
            return update(b);
        }
    }

    pair<node *,node *>split(node *t,int k){
        if(!t)return make_pair(t,t);
        t=update(t);
        if(k<=count(t->lch)){
            pair<node *,node *>s=split(t->lch,k);
            t->lch=s.second;
            return make_pair(s.first,update(t));
        }
        else{
            pair<node *,node *>s=split(t->rch,k-count(t->lch)-1);
            t->rch=s.first;
            return make_pair(update(t),s.second);
        }
    }

    void insert(int k,int val){
        pair<node *,node *>s=split(root,k);
        node *a=new node(val);
        root=merge(s.first,a);
        root=merge(root,s.second);
    }

    void erase(int k){
        pair<node *,node *>s1,s2;
        s1=split(root,k);
        s2=split(s1.second,1);
        root=merge(s1.first,s2.second);
    }

    int getSum(int l,int r){
        pair<node *,node *>s1,s2;
        int ret;

        s1=split(root,l);
        s2=split(s1.second,r-l);
        ret=s2.first->sum;
        root=merge(s1.first,s2.first);
        root=merge(root,s2.second);
        return ret;
    }

    void add(int l,int r,int x){
        pair<node *,node *>s1,s2;
        s1=split(root,l);
        s2=split(s1.second,r-l);
        s2.first->lazy+=x;update(s2.first);
        root=merge(s1.first,s2.first);
        root=merge(root,s2.second);
    }



};

int N,Q;
RBST T;
signed main(){
    scanf("%lld%lld",&N,&Q);
    for(int i=0;i<N;i++){
        T.insert(i,0);
    }
    while(Q--){
        int type;
        scanf("%lld",&type);
        if(type==0){
            int k,x;
            scanf("%lld%lld",&k,&x);
            k--;
            T.add(k,k+1,x);
        }
        else{
            int l,r;
            scanf("%lld%lld",&l,&r);
            l--;
            printf("%lld\n",T.getSum(l,r));
        }
    }
    return 0;
}

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

using namespace std;

using ll = long long;
using ld = long double;

const double PI = 3.1415926535897932384626433832795;

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

int gcd(int x, int y) { return y ? gcd(y, x % y) : abs(x); }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : abs(x); }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

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

	int n;
	cin >> n;

	vector<int> items(n);
	for (auto &v : items) {
		cin >> v;
	}

	sort(begin(items), end(items));
	int ans = 0;
	for (int i = 0; i < n; i++) {
		ans += i != n - 1 ? items[i] : items[i] / 2;
	}

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


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int n;
int seq[35];

bool sorted(){
  for(int i=0; i<n-1; i++){
    for(int j=i+1; j<n; j++){
      if(seq[i] > seq[j])
        return false;
    }
  }

  return true;
}

int main(){
  ios::sync_with_stdio(false);
  cin >> n;

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

  if(sorted()){
      cout << "YES" << endl;
      return 0;
    }
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(i == j)
        continue;
      swap(seq[i], seq[j]);
      if(sorted()){
        cout << "YES" << endl;
        return 0;
      }else
        swap(seq[i], seq[j]);
    }
  }

  cout << "NO" << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define f first
#define s second
#define fore(i,a,b) for(int i = (a), ThxMK = (b); i < ThxMK; ++i)
#define pb push_back
#define all(s) begin(s), end(s)
#define _ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define sz(s) int(s.size())
#define ENDL '\n'
using namespace std;
typedef long double ld;
typedef long long lli;
typedef pair<lli,lli> ii;
typedef vector<int> vi;
typedef vector<lli> vl;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
#define deb(x) cout << #x": " << (x) << endl;

const int N = 3e3+5;
const lli INF = 1e18;
const lli MOD = 1e9+7;

vi m;
vi primes(1,2);
vector<vector<ld>>nk;
void sieve(){
	m = vi(N+1,0);
	for(int i = 4; i<N; i+=2)m[i]=1;
	for(int i = 3; i*i<=N; i+=2)if(!m[i])for(int j = i*i; j<N; j+=i)m[j]=1;
	for(int i = 3; i<N; i+=2)if(!m[i])primes.pb(i);
}

void pascal(){
	nk =vector<vector<ld>>(N,vector<ld>(N,0.0));
	fore(i,0,N)nk[i][0]=nk[i][i]=1.0;
	fore(i,1,N)fore(j,1,i)nk[i][j]=nk[i-1][j-1]+nk[i-1][j];
}

lli gcd(lli a, lli b){return (b?gcd(b,a%b):a);}

lli lcm(lli a, lli b){
	if(a<b)swap(a,b);
	lli c = gcd(a,b);
	a/=c;
	return a*b;
}

int popcount(lli x) { return __builtin_popcountll(x); }

lli poww(lli a, lli b){
	lli res =1;
	while(b){
		if(b&1) res = res * a;
		a = a*a;
		b/=2;
	}
	return res;
}

lli powm(lli a, lli b){
	lli res =1;
	while(b){
		if(b&1) res = (res * a)%MOD;
		a = (a*a)%MOD;
		b/=2;
	}
	return res;
}

bool isPrime(lli x){
	if(x==1)return 0;
	for(auto i:primes){
		if(i*i>x)return 1;
		if(x%i==0)return 0;
	}
	return 1;
}

lli SUM(lli a, lli b, lli mod=MOD){
	return (a+b+mod)%mod;
}

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

// ---- コーディングはここから！ ('-')7

void solve(){
	int n; cin>>n; vl v(n); fore(i,0,n)cin>>v[i];
	vl dp(n+1,-1);
	auto f=[&](auto f, int a)->lli{
		if(a==n-1)return 0;
		if(dp[a]!=-1)return dp[a];
		dp[a]=INF;
		fore(i,1,3)if(i+a>n)break; else dp[a]=min(f(f,i+a)+abs(v[a]-v[a+i]),dp[a]);
		return dp[a];
	};
	cout<<f(f,0)<<ENDL;
}

int main(){_
	//int t; cin>>t; while(t--)
	solve();
}


Measured memory_bytes: 14252
#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
int main(){

    map<string,vector<int> > M;
    string str;
    while(cin>>str){
        int p;
        cin>>p;
        M[str].push_back(p);
    }
    map<string,vector<int> >::iterator it = M.begin();
    for(;it != M.end();it++){
        sort((*it).second.begin(),(*it).second.end());
        cout<<(*it).first<<endl;
        cout<<(*it).second[0];
        for(int i = 1;i < (*it).second.size();i++){
            cout<<" "<<(*it).second[i];
        }
        cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 1244
#include <iostream>
using namespace std;
typedef unsigned long long ullong;

#define M 1000000007

ullong pow(ullong m, ullong n){
  if(n == 0)
    return 1;
  if(n%2 == 0)
    return (pow((m*m)%M, n/2))%M;
  else
    return (pow((m*m)%M, n/2)*m)%M;
}

int main(void){
  ullong m, n;
  cin >> m >> n;

  cout << pow(m, n) << endl;

  return 0;
}

Measured memory_bytes: 3088
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long int ll;

ll x[1010];
ll y[1010];
ll dx[4] = {1, 0, -1, 0};
ll dy[4] = {0, 1, 0, -1};
char dir[4] = {'R', 'U', 'L', 'D'};

int main() {
    ll N;
    cin >> N;
    ll par = 0;
    for (ll i = 0; i < N; i++) {
        cin >> x[i] >> y[i];
        if (i == 0) par = x[i] + y[i];
        if ((par - (x[i] + y[i])) % 2 == 0) continue;
        cout << -1 << endl;
        return 0; 
    }
    if (par % 2 == 0) {
        cout << 32 << endl;
        cout << 1 << " ";
    } else {
        cout << 31 << endl;
    }
    for (ll i = 30; i >= 0; i--) {
        cout << ((ll)1 << i) << " ";
    }
    cout << endl;
    for (ll i = 0; i < N; i++) {
        if (par % 2 == 0) {
            x[i]--;
            cout << 'R';
        }
        for (ll stick = ((ll)1 << 30); stick >= 1; stick >>= 1) {
            for (ll j = 0; j < 4; j++) {
                ll tx = x[i] - stick * dx[j];
                ll ty = y[i] - stick * dy[j];
                if (abs(tx) + abs(ty) < stick) {
                    cout << dir[j];
                    x[i] = tx;
                    y[i] = ty;
                    break;
                }
            }
        }
        cout << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int,int> pii;
typedef vector< pii > vii;

#define ll          long long
#define ff          first
#define ss          second
#define pb          push_back
#define mkp         make_pair
#define sz          size()

#define forf(a,b,c)    for(int i=a;i<=b;i+=c)
#define forr(a,b,c)    for(int i=a;i>=b;i-=c)
#define all(a)      a.begin(),a.end()
#define mem(a,b)    memset(a,b,sizeof(a))
#define pi          2*acos(0.0)
#define End         return 0;
#define nl endl

#define scan1(a)    scanf("%d",&a)
#define scan2(a,b)  scanf("%d %d",&a,&b)
#define scan3(a,b,c)  scanf("%d %d %d",&a,&b,&c)
#define scanl(a)    scanf("%lld",&a)
#define scanll(a,b) scanf("%lld %lld",&a,&b)
#define scanlll(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)

#define print1(a)    printf("%d",a)
#define print2(a,b)  printf("%d %d",a,b)
#define print3(a,b,c)  printf("%d %d %d",a,b,c)
#define printl(a)    printf("%lld",a)
#define printll(a,b) printf("%lld %lld",a,b)
#define printlll(a,b,c) printf("%lld %lld %lld",a,b,c)

#define MAXN        100000007
#define INF 0x3f3f3f3f
bool mark[100005];vi prime;
void seive(ll N){for(int i=2;i<=N;i++){if(mark[i]==false){prime.pb(i);for(int j=i+i;j<N;j+=i)mark[j]=true;}}}
//freopen("input.txt", "r", stdin);

bool sorts(const pair<string,pair<int,int>>&a,
           const pair<string,pair<int,int>>&b){
           return a.ss.ff>b.ss.ff;
           }
int main()
{
   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    ll n;
    cin>>n;
    vector<pair<string, pair<int,int>>>v;
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        int c;
        cin>>c;
        v.pb(mkp(s,mkp(c,i)));
    }

    sort(all(v));


       // cout<<endl;
   // for(int i=0;i<n;i++)
        //cout<<v[i].ff<<" "<<v[i].ss.ff<<endl;

    int init=0,en=1;
    while(en<n){
        if(v[en].ff!=v[en-1].ff){
            sort(v.begin()+init,v.begin()+en,sorts);
            //cout<<"en "<<en<<endl;
            init=en;
        }
        if(en==n-1)
        {
            sort(v.begin()+init,v.begin()+(en+1),sorts);
            break;
        }
        en++;
    }

   // sort(v.begin(),v.begin()+2,sorts);
    cout<<endl;
    //for(int i=0;i<n;i++)
        //cout<<v[i].ff<<" "<<v[i].ss.ff<<endl;

    for(int i=0;i<n;i++){
        cout<<v[i].ss.ss<<endl;
    }
    End;
}


Measured memory_bytes: 256
/***********************
*  Author: xuziyuan    * 
***********************/

#include <bits/stdc++.h>

#define rt0 return 0
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define replet(c) for(char c='a';c<='z';c++) 
#define LL long long
#define pii pair <int,int>
#define pb push_back
#define fi first
#define se second
#define mpr make_pair
#define sqr(a) ((a)*(a))

using namespace std;

const LL MOD=1e9+7;

LL n,m,x,y,num[100010],par[100010];
vector <pii> v;
vector <LL> ans;

LL FIND(LL pos)
{
	if(par[pos]!=pos) par[pos]=FIND(par[pos]);
	return par[pos];
}

void UNION(LL pos1,LL pos2)
{
	num[FIND(pos2)]+=num[FIND(pos1)];
	par[FIND(pos1)]=FIND(pos2);
}

int main()
{
	cin>>n>>m;
	rep(i,m)
	{
		cin>>x>>y;
		v.pb({x,y});
	}
	reverse(v.begin(),v.end());
	rep(i,100005) par[i]=i,num[i]=1;
	ans.pb(n*(n-1)/2);
	LL cnt=ans[0];
	rep(i,m-1)
	{
		if(FIND(v[i].fi)!=FIND(v[i].se))
		{
			//cout<<i<<endl;
			//cout<<v[i].fi<<' '<<FIND(v[i].fi)<<endl<<v[i].se<<' '<<FIND(v[i].se)<<endl;
			//cout<<num[FIND(v[i].fi)]<<' '<<num[FIND(v[i].se)]<<'p'<<endl;
			cnt-=num[FIND(v[i].fi)]*num[FIND(v[i].se)];
			UNION(v[i].fi,v[i].se);
			//cout<<v[i].fi<<' '<<FIND(v[i].fi)<<endl<<v[i].se<<' '<<FIND(v[i].se)<<endl;
		}
		ans.pb(cnt);
	}
	reverse(ans.begin(),ans.end());
	rep(i,m) cout<<ans[i]<<endl;
	rt0;
}

Measured memory_bytes: 4596
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

#define INF (1 << 30)
#define INFL (1LL << 62)
#define MOD7 1000000007
#define MOD9 1000000009
#define EPS 1e-10

using ll = long long;
using ull = unsigned long long;

int main() {
    int n, h[100000], cnt = 0, ans = 0;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
        if (i > 0 && h[i - 1] >= h[i]) {
            cnt++;
            ans = max(ans, cnt);
        }
        else {
            cnt = 0;
        }
    }
    cout << ans << endl;

    return 0;
}

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

int main(void){
    int n, m;
    cin >> n >> m;
    vector<int> h(n);
    rep(i,n) cin >> h[i];
    vector<vector<int>> g(n);
    rep(i,m){
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int cnt = 0;
    rep(i,n){
        bool is_good = true;
        for (int nxt : g[i]) {
            if (h[i] <= h[nxt]) {
                is_good = false;
            }
        }
        if (is_good) cnt++;
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 8804
_ = gets.to_i
a = gets.split.map(&:to_i)

b = []
b[0] = a[0]
(1..a.length-1).each do |i|
  b[i] = b[i-1].gcd(a[i])
end
c = []
c[a.length-1] = a[-1]
(2..a.length).each do |i|
  c[a.length-i] = c[a.length-i+1].gcd(a[a.length-i])
end

result = (0..a.length-1).map do |i|
  if i == 0
    c[i+1]
  elsif i == a.length-1
    b[i-1]
  else
    b[i-1].gcd(c[i+1])
  end
end.max

puts result


Measured memory_bytes: 11092
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
int n;
vector<int> pre;
vector<int> in;
vector<int> post;
void postorder(int i, vector<int> child[]){
	if(i==-1) return;
	vector<int> temp = child[i];
	postorder(temp.at(0),child);
	postorder(temp.at(1),child);
	post.push_back(i);
}
void inorder(int i, vector<int> child[]){
	if(i==-1) return;
	vector<int> temp = child[i];
	inorder(temp.at(0),child);
	in.push_back(i);
	inorder(temp.at(1),child);
}
void preorder(int i, vector<int> child[]){
	if(i==-1) return;
	pre.push_back(i);
	vector<int> temp = child[i];
	preorder(temp.at(0),child);
	preorder(temp.at(1),child);
}
int main(){
	scanf("%d",&n);
	int tree[n]; //store parent
	for(int i = 0; i<n; i++){
		tree[i] = -1;
	}
	vector<int> child[n];
	for(int i = 0; i<n; i++){
		int p;
		int l,r;
		int count = 0; // count the degree
		scanf("%d %d %d",&p,&l,&r);
		vector<int> temp;
		{
			tree[l] = p;temp.push_back(l);
		}
		{
			tree[r] = p;temp.push_back(r);
		}
		child[p] = temp;
	}
	int root;
	for(int i = 0; i<n; i++){
		if(tree[i] == -1){
			root = i;break;
		}
	}
	printf("Preorder\n");
	preorder(root,child);
	for(int i = 0; i<pre.size(); i++){
		if(i==pre.size()-1)
		printf(" %d\n",pre.at(i));
		else printf(" %d",pre.at(i));
	}
	printf("Inorder\n");
	inorder(root,child);
	for(int i = 0; i<in.size(); i++){
		if(i==in.size()-1)
		printf(" %d\n",in.at(i));
		else printf(" %d",in.at(i));
	}
	printf("Postorder\n");
	postorder(root,child);
	for(int i = 0; i<post.size(); i++){
		if(i==pre.size()-1)
		printf(" %d\n",post.at(i));
		else printf(" %d",post.at(i));
	}
	
	return 0;
}


Measured memory_bytes: 3272
#include <stdio.h>
#include <stdlib.h>

char buf[16];

void bubblesort(int *a, int n)
{
  int i, j, nswap = 0;
  int flag = 1;
  do {
    flag = 0;
    for (j=n-1; j>=1; j--) {
      if (a[j] < a[j-1]) {
	int t = a[j];
	a[j] = a[j-1];
	a[j-1] = t;
	nswap ++;
	flag = 1;
      }
    }
  } while (flag);

  buf[15]=0;
  buf[14] = ' ';
  for (i=0; i<n-1; i++) {
    if (a[i]==0)  putc_unlocked('0', stdout);
    for (j=13; a[i]>0; j--, a[i]/=10) buf[j]='0' + (a[i]%10);
    fputs(buf+j+1, stdout);
  }
  buf[14] = '\n';
  for (j=13; a[i]>0; j--, a[i]/=10) buf[j]='0' + (a[i]%10);
  fputs(buf+j+1, stdout);

  if (nswap==0)  putc_unlocked('0', stdout);
  for (j=13; nswap>0; j--, nswap/=10) buf[j]='0' + (nswap%10);
  fputs(buf+j+1, stdout);
}

int main()
{
  char *p = NULL;
  size_t linecap = 0;
  fgets(buf, 12, stdin);
  int n = atoi(buf);
  int *a = (int*)malloc(sizeof(int)*n);
  getline(&p, &linecap, stdin);
  a[0] = 0;
  int i=0;
  for (; *p!='\n'; p++) {
    if (*p == ' ') {
      a[++i] = *(++p)-'0';
    } else {
      a[i] = a[i] * 10 + *p - '0';
    }
  }
  bubblesort(a, n);

  return 0;
}



Measured memory_bytes: 2044
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-12;

//int N, M, K, T, H, W, L, R;
long long int N, M, K, T, H, W, L, R;

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

	while (cin >> N >> M, N) {
		vector<string>s(N);
		vector<string>t(M);
		vector<int>num(N);
		vector<int>anum(N);
		vector<int>bnum(N);
		vector<int>cnum(N);
		for (auto &i : s)cin >> i;
		for (auto &i : t)cin >> i;
		for (int i = 0; i < N; i++) {
			for (auto j : s[i]) {
				if (j == '.')num[i]++;
				else break;
			}
			for (auto j : s[i]) {
				if (j == '(')anum[i]++;
				if (j == ')')anum[i]--;
				if (j == '{')bnum[i]++;
				if (j == '}')bnum[i]--;
				if (j == '[')cnum[i]++;
				if (j == ']')cnum[i]--;
			}
		}
		set<pair<int, pair<int,int>>>st;
		vector<int>ans(M,MOD);
		for (int i = 1; i <= 20; i++) {
			for (int j = 1; j <= 20; j++) {
				for (int k = 1; k <= 20; k++) {
					int a, b, c;
					a = b = c = 0;
					bool flag = true;
					for (int l = 0; l < N; l++) {
						if (a*i + b * j + c * k != num[l])flag = false;
						a += anum[l];
						b += bnum[l];
						c += cnum[l];
					}
					if (flag) {
						st.insert({ i,{j,k} });
					}
				}
			}
		}
		vector<int>aanum(M);
		vector<int>bbnum(M);
		vector<int>ccnum(M);
		for (int i = 0; i < M; i++) {
			for (auto j : t[i]) {
				if (j == '(')aanum[i]++;
				if (j == ')')aanum[i]--;
				if (j == '{')bbnum[i]++;
				if (j == '}')bbnum[i]--;
				if (j == '[')ccnum[i]++;
				if (j == ']')ccnum[i]--;
			}
		}
		for (auto i : st) {
			int aa = i.first, bb = i.second.first, cc = i.second.second;
			int a, b, c ;
			a = b = c = 0;
			for (int j = 0; j < M; j++) {
				if (ans[j] == MOD) {
					ans[j] = a * aa + b * bb + c * cc;
				}
				else if (ans[j] != a * aa + b * bb + c * cc) {
					ans[j] = -1;
				}
				a += aanum[j];
				b += bbnum[j];
				c += ccnum[j];
			}
		}
		for (int i = 0; i < M; i++) {
			if (i)cout << " ";
			cout << ans[i];
		}
		cout << endl;
	}
}


Measured memory_bytes: 3688
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <cmath>
#include <numeric>
#include <iomanip>

using namespace std;
long long A[100000];
long long cumsum_A[100000];
int main(void){
  int N;
  long long M;
  cin >> N >> M;
  for(int i = 0; i < N; i++){
    cin >> A[i];
  }
  sort(A, A + N);
  reverse(A, A + N);
  cumsum_A[0] = A[0];
  for(int i = 0; i < N; i++){
    cumsum_A[i] = A[i] + cumsum_A[i - 1];
  }

  long long left = A[0] + A[0] + 1;
  long long right = 0;

  while(left > 1 + right){
    long long mid = (left + right) / 2;
    long long tmp_count = 0;
    for(int i = 0; i < N; i++){
      long long target = mid - A[i];
      auto it = upper_bound(A, A + N, target, greater<long long>());
      tmp_count += (it - A);
    }
    if(tmp_count >= M){
      right = mid;
    } else {
      left = mid;
    }
  }
  long long ans = 0;
  long long count = 0;
  for(int i = 0; i < N; i++){
    long long target = right - A[i];
    auto it = upper_bound(A, A + N, target, greater<long long>());
    count += (it - A);
    if(it - A > 0){
      ans += (cumsum_A[(it - A) - 1] + A[i] * (it - A));
    }
  }
  ans -=  (right * (count - M));
  cout << ans << endl;
  return 0;
}

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

int main(){
	int h,w;
	cin >> h >> w;
	vector<string> s(h);
	for(int i=0;i<h;++i) cin >> s[i];
	string l;
	for(int i=0;i<w;++i) l.push_back('#');
	s.insert(s.begin(),l);
	s.push_back(l);
	for(int i=0;i<h+2;++i){
		s[i].insert(0,"#");
		s[i].push_back('#');
	}
	for(auto a:s)cout << a << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
enum { MAXN = 8 };
int n, m;
vector<int> adj[MAXN+5];
vector<bool> vis(MAXN+5, false);

int dfs(int u) {
	bool av = true;
	for (int i = 1; i <= n; i++) {
		av &= vis[i];
	}
	if (av) {
		return 1;
	}
	int ret = 0;
	for (auto ui : adj[u]) {
		if (!vis[ui]) {
			vis[ui] = true;
			ret += dfs(ui);
			vis[ui] = false;
		}
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	vis[1] = true;
	cout << dfs(1) << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int solve(int,int);

int n,A[2000];

int main(){
  int q,B[2000];
  int i,j;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }

  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&B[i]);
  }

  for(i=0;i<q;i++){
      
    if(solve(0,B[i])==1)
      printf("yes\n");
    else
      printf("no\n");
  }

  return 0;
}

int solve(int i, int m){
  
  int res;
  
  if(m==0) return 1;

  if(i>=n) return 0;

  if( solve(i+1,m) || solve(i+1,m-A[i]) ) return 1;

}

Measured memory_bytes: 588
N = int(input())
S = [input() for _ in range(N)]

head = {'M':0, 'A':0, 'R':0, 'C':0, 'H':0}
march = "MARCH"
for s in S:
  if(s[0] in head):
    head[s[0]] += 1
ans = 0
for i in range(3):
  for j in range(i+1,4):
    for k in range(j+1,5):
      ans += head[march[i]] * head[march[j]] * head[march[k]]
print(ans)

Measured memory_bytes: 9752
import math
from bisect import bisect_left
N=int(input())
P=[int(i) for i in input().split()]
Q=[int(i) for i in input().split()]
a=1
b=1
for i,n in enumerate([m for m in range(1,N+1)]):
    if min(P[i:])<P[i]:
        a+=bisect_left(sorted(P[i:]),P[i])*math.factorial(N-i-1)
    if min(Q[i:])<Q[i]:
        b+=bisect_left(sorted(Q[i:]),Q[i])*math.factorial(N-i-1)
print(abs(a-b))

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

using namespace std;

int main()
{
    int N;
    cin>>N;
    vector<int> a(N);
    for (int &t: a)
        cin>>t;

    vector<vector<long long>> T(N, vector<long long>(N));
    for (int i=2; i<=N; i++)
        for (int j=0; j+i<=N; j++)
        {
            T[j][j+i-1] = 0x3fffffffffffffffLL;
            long long s = 0;
            for (int k=j; k<=j+i-1; k++)
                s += a[k];
            for (int k=j; k+1<=j+i-1; k++)
                T[j][j+i-1] = min(T[j][j+i-1], T[j][k]+T[k+1][j+i-1]+s);
        }
    cout<<T[0][N-1]<<endl;
}


Measured memory_bytes: 1536
n = $stdin.gets.to_i
count = 0
a = 0
b = 0

found_header = false
n.times do
  str = $stdin.gets.strip
  if str[-1]=="A"
    a+=1
    if str[0] !="B"
      found_header = true
    end
  end

  if str[0]=="B"
    b+=1
  end

  count += str.scan("AB").size
end
add =[a, b, n].min
if !found_header && a >= b
  add -= 1
end
count+= [0, add].max
puts count

Measured memory_bytes: 3836
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    if(a>0)
    	cout<<"Positive"<<endl;
    else
    	if(a==0||a<0&&b>0)
            cout<<"Zero"<<endl;
        else
        {
        	int c=abs(a),d=abs(b);
            if((d-c)%2!=0)
                cout<<"Positive"<<endl;
            else
                cout<<"Negative"<<endl;
        }
}

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

using namespace std;

int main() {
	long long d, n;
	cin >> d >> n;
	if (n == 100) {
		n += 1;
	}
	for (int i = 0; i < d; i++) {
		n *= 100;
	}
	cout << n;
	return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args){

		Scanner sc = new Scanner(System.in);
		String a1 = sc.next();
		String b1 = sc.next();

		int a = Integer.parseInt(a1);
		int b = Integer.parseInt(b1);

		int d = a/b;
		int r = a%b;
		double f = a/(double)b;

		System.out.println(d);
		System.out.println(r);

		System.out.println(String.format("%f", f));
	}
}

Measured memory_bytes: 26424
#include <bits/stdc++.h>
#include <numeric>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rep1(i,n) for (int i = 1; i <= n; ++i)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;

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

  ld l; cin >> l;
  ld edge = l / (ld)3;
  ld ans = edge * edge * edge;

  cout << std::fixed << std::setprecision(12) << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define irep(i,n,m) for(int i=(int)(n);i<(int)(m);i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    rep(i,n) cin>>a.at(i);
    sort(all(a));
    
    string x;
    if(n%2==0){
        for(int i=1;i<n;i+=2){
            x+='0'+i;
            x+='0'+i;
        }
    }
    else{
        x+='0';
        for(int i=2;i<n;i+=2){
            x+='0'+i;
            x+='0'+i;
        }
    }
    
    string y;
    rep(i,n) y+='0'+a.at(i);
    
    if(x!=y) cout<<0<<endl;
    else{
        ll ans=1;
        rep(i,n/2) {
            ans*=2;
            ans%=1000000007;
        }
        cout<<ans<<endl;
    }
}



Measured memory_bytes: 1024
#include<stdio.h>

int sentaku(int*,int);

int main()
{
  int A[100],N,a,sum;

  scanf("%d",&N);
  for(a=0;a<N;a++)
    {
      scanf("%d",&A[a]);
    }
  sum=sentaku(A,N);

  for(a=0;a<N;a++)
    {
      if(a>0)
	{
	  printf(" ");
	}
      printf("%d",A[a]);
    }
  printf("\n");
  printf("%d\n",sum);

  return 0;
}

int sentaku(int A[],int N)
{
  int a,b,c,sum=0,num;

  for(a=0;a<N-1;a++)
    {
      num=a;
      for(b=a;b<N;b++)
	{
	  if(A[b]<A[num])
	    {
	      num=b;
	    }
	}
      c=A[a];
      A[a]=A[num];
      A[num]=c;
      if(a!=num)
	{
	  sum++;
	  }
    }
  return sum;
}



Measured memory_bytes: 2108
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <limits>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <map>
#include <tuple>

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

 

 
int main(){
    int n; cin >> n;
    vector<pair<int, int>> p(n);
    rep(i,n) {
        int a; cin >> a;
        p[i].first = a;
        p[i].second = i+1;
        

    }
    sort(p.begin(), p.end());
    
    rep(i,n){
        cout << p[i].second << endl;
    }
    
}


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

using namespace std;

typedef long long ll;
#define fi first
#define se second
#define pb push_back

const int N = 200005;

int main() {
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    scanf("%d", &n);
    multiset <pair <int, int> > st;
    bool no = false;
    for (int i = 0; i < n; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		if (y - x < 0) {
			no = true;
		}
		st.insert({y, y - x});
	}
	if (no) {
		printf("No");
	} else {
		int lst = 0;
		auto it = st.begin();
		while (it != st.end()) {
			int l = it->se, r = it->fi;
			if (l >= lst) {
				lst += r - l;
			} else {
				return printf("No"), 0;
			}
			it++;
		}
		printf("Yes");
	}
    return 0;
}


Measured memory_bytes: 13168
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S; cin >> S;
    rep(i, 3) {
        if(S[i] == '1') cout << '9';
        else cout << '1';
    }
    cout << endl;

    return 0;
}


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

const int maxn = 1100, maxw = 1e4+500;
int N;

struct Block
{
    int val, weight, solid;
} b[maxn];

ll dp[maxn][maxw];

ll f(int i, int ms) {
    if (i == N) return 0LL;
    assert(ms >= 0);
    if (dp[i][ms] >= 0) return dp[i][ms];
    if (b[i].weight > ms) return dp[i][ms] = f(i+1,ms);
    return dp[i][ms] = max(f(i+1,ms),b[i].val+f(i+1,min(ms-b[i].weight,b[i].solid)));    
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; i++) { cin >> b[i].weight >> b[i].solid >> b[i].val; }
    sort(b,b+N,[](auto aa, auto bb) { return aa.weight + aa.solid > bb.weight + bb.solid; });
    memset(dp,-1,sizeof dp);
    ll ans = 0;
    for (int t = 0; t < N; t++) {
        ans = max(ans,b[t].val + f(t+1,b[t].solid));
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 90496
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n= scan.nextInt();
		int d[]=new int[n];
		for(int i=0;i<n;i++) {
			d[i]=scan.nextInt();
		}
		scan.close();

		Arrays.sort(d);
		int cnt=1;
		for(int i=1;i<n;i++) {
			if(d[i-1]!=d[i]) {
				cnt++;
			}
		}
		System.out.println(cnt);
	}

}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    cin >> N >> M;
    vector<int> H(N);
    for (int i = 0; i < N; ++i) {
        cin >> H[i];
    }
    vector<bool> good(N, true);
    for (int i = 0; i < M; ++i) {
        int A, B;
        cin >> A >> B;
        --A;
        --B;
        if (H[A] <= H[B]) {
            good[A] = false;
        }
        if (H[B] <= H[A]) {
            good[B] = false;
        }
    }
    int ans = 0;
    for (int i = 0; i < N; ++i) {
        if (good[i]) {
            ++ans;
        }
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 3728
N, K = map(int, input().split())
# クリークから1つ減らすごとに、距離2が1個ずつ増える
# クリークの辺の本数はN(N-1)/2
# 連結グラフ成立に必要な辺の本数はN-1

M = N * (N-1) // 2 - K
if M < N-1:
  print(-1)
  exit()

edges = []
for i in range(1, N+1):
  for j in range(i+1, N+1):
    edges.append((i, j))
edges.sort(key=lambda x: x[0])
print(M)
for f, t in edges[:M]:
  print(f, t)

Measured memory_bytes: 3992
//To debug :  g++ -g file.cpp -o code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,n) for(i=a;i<n;++i)
#define irep(i,n,a) for(i=n;i>a;--i)
#define mod 1000000007
#define pb push_back
#define big 9223372036854775807
#define big1 LONG_MAX
#define big2 INT_MAX
#define big3 1000000000
#define sma -(big+1)
#define sma1 LONG_MIN
#define sma2 INT_MIN
#define sma3 -1000000000
#define mp make_pair
#define mt make_tuple
#define dub double
#define ivec vector<int>
#define lvec vector<long long>
#define cvec vector<char>
#define svec vector<string>
#define inv2 500000004
#define MOD 998244353 
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);

int main()
{

	ll x,y,a,b,c,i,l,r,m,j,k,ans=0;
	cin>>x>>y>>a>>b>>c;


	ll xx[a];
	ll yy[b];
	ll cc[c];

	rep(i,0,a)
		cin>>xx[i];

	rep(i,0,b)
		cin>>yy[i];

	rep(i,0,c)
		cin>>cc[i];


	sort(xx,xx+a,greater<int>());
	sort(yy,yy+b,greater<int>());
	sort(cc,cc+c);

	j = x-1;
	k = y-1;


	for(i=c-1;i>=0;)
	{
		if(j==-1 || k==-1)
			break;

		if(xx[j]<yy[k])
		{
			if(cc[i]>xx[j])
			{
				xx[j] = cc[i];
				--j;
				--i;
			}
			else
				break;
				
		}
		else
		{
			if(cc[i]>yy[k])
			{
				yy[k] = cc[i];
				--k;
				--i;
			}
			else
				break;
		}

	}

	for(;i>=0;)
	{
		if(j==-1)
			break;

		if(cc[i]>xx[j])
		{
			xx[j] = cc[i];
			--j;
			--i;
		}
		else
			break;
	}

	for(;i>=0;)
	{
		if(cc[i]>yy[k])
		{
			yy[k] = cc[i];
			--k;
			--i;
		}
		else
			break;
	}

	for(i=0;i<x;++i)
		ans += xx[i];

	for(i=0;i<y;++i)
		ans += yy[i];


	cout<<ans<<"\n";



	return 0;
}

Measured memory_bytes: 2560