akhauriyash/Code-Regression huggingface dataset:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
# 約数列挙
def find_divisor(n):
    divisors=[]
    for i in range(1, int(sqrt(n)) + 1):
        if n % i == 0:
            divisors.append(i)
            if i*i!=n:
                divisors.append(n // i)
    return divisors


# 素因数分解
def prime_factorization(n):
    fact=[]
    for i in range(2, int(sqrt(n)) + 1):
        while n % i == 0:
            n //= i
            fact.append(i)
    if n!=1:
        fact.append(n)
    return fact
def main():
    N,M=MI()
    D=find_divisor(M)
    ans = 1
    for d in D:
        if M//d >= N:
            ans = max(ans,d)
    print(ans)
if __name__ == '__main__':
    main()

Measured memory_bytes: 69740
import math
a,b=map(int,input().split(" "))
c=input()
if c=="":
    print(a)
else:
    c = list(map(int,c.split(" ")))
    c.sort()
    #print(c)
    inaria=list(range(min(c)-1,max(c)+2))
    add1=c+inaria
    add1=sorted(add1)
    l_all_only = [x for x in add1 if add1.count(x) == 1]
    #print(l_all_only)
    min=4000000
    min_data=0
    for n in l_all_only:
        abn=abs(a-n)
        #print(n,abn)
        if abn<min:
            min=abn
            min_data=n
    print(min_data)


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

int n, m, idx, d;
bool amd[30][9];

bool solve(int now = m - 1,int y = 0){
  if(y == d) return now + 1 == idx;
  if(now && amd[y][now - 1]) return solve(now - 1, y + 1);
  if(now != n - 1 && amd[y][now]) return solve(now + 1, y + 1);
  return solve(now, y + 1);
}
int main(){
  while(cin >> n , n){
    cin >> m >> idx >> d;
    char c;
    for(int i = 0; i < d ; i++ ){
      for(int j = 0 ; j < n - 1 ; amd[i][j++] = c - '0' ){
        cin >> c;
      }
    }
    if(solve()){
      cout << 0 << endl;
      continue;
    }
    bool ok = false;
    for(int i = 0 ; i < d && !ok; i++ ){
      for(int j = 0 ; j < n - 1 && !ok ; j++ ){
        if(amd[i][j] || (j & amd[i][j-1]) || (j != n - 2 & amd[i][j+1])) continue;
        amd[i][j] = true;
        if(solve()) cout << i+1 << " " << j+1 << endl, ok++; // break
        else amd[i][j] = false;
      }
    }
    if(!ok) cout << 1 << endl;
  }
}

Measured memory_bytes: 1160
#include<iostream>

using namespace std;

int main(){
	
	double v;
	while(cin>>v){
		double t=v/9.8;
		double y=4.9*t*t;
		y/=5.0;
		int ans=(y-(int)y==0.0)?y:(int)y+1;
		cout<<ans+1<<endl;
	}
}

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

using namespace std;

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

const int maxn = 131072 + 10;

ll cur;
int n, v[maxn], ls[maxn], rs[maxn], sz[maxn], fa[maxn];
ll dis[maxn];

void dfs1(int u) {
	sz[u] = 1;
	if (!ls[u]) return;
	dis[ls[u]] = dis[u] + v[ls[u]];
	dfs1(ls[u]);
	dis[rs[u]] = dis[u] + v[rs[u]];
	dfs1(rs[u]);
	sz[u] += sz[ls[u]];
	sz[u] += sz[rs[u]];
	if (sz[ls[u]] > sz[rs[u]]) swap(ls[u], rs[u]);
}

vector<pi> tr(const vector<pi> &vec) {
	vector<pi> r;
	for (int i = 0; i < vec.size(); i++) {
		int u = vec[i].first, v = vec[i].second;
		if (!r.empty() && dis[r[r.size() - 1].second] <= dis[v]) continue;
		r.push_back(pi(u, v));
	}
	return r;
}

vector<pi> Merge(const vector<pi> &v1, const vector<pi> &v2) {
	int s1 = 0, s2 = 0;
	vector<pi> ret;
	while (s1 < v1.size() && s2 < v2.size()) {
		if (dis[v1[s1].first] < dis[v2[s2].first]) {
			ret.push_back(v1[s1++]);
		} else {
			ret.push_back(v2[s2++]);
		}
	}
	for (int i = s1; i < v1.size(); i++) ret.push_back(v1[i]);
	for (int i = s2; i < v2.size(); i++) ret.push_back(v2[i]);
	return tr(ret);
}

vector<pi> dfs2(int u) {
	vector<pi> ret;
	if (!ls[u]) {
		ret.push_back(pi(u, u));
		return ret;
	}
	vector<pi> vl, vr;
	vl = dfs2(ls[u]);
	vr = dfs2(rs[u]);
	vector<pi> v1, v2;
	int p = int (vr.size() - 1);
	for (int i = int (vl.size() - 1); i >= 0; i--) {
		int x = vl[i].first, y = vl[i].second;
		while (p >= 0 && dis[y] + dis[vr[p].first] - 2 * dis[u] > cur) -- p;
		if (p >= 0) {
			v1.push_back(pi(x, vr[p].second));
			v2.push_back(pi(vr[p].second, x));
		}
	}
	reverse(v1.begin(), v1.end());
	return Merge(tr(v1), tr(v2));
}

int main() {
	scanf("%d", &n);
	for (int i = 2; i <= n; i++) {
		scanf("%d%d", &fa[i], &v[i]);
		if (!ls[fa[i]]) ls[fa[i]] = i;
		else rs[fa[i]] = i;
	}
	dfs1(1);
	ll L = 0, R = (1ll << 34), ans = -1;
	while (L <= R) {
		cur = (L + R) >> 1;
		vector<pi> res = dfs2(1);
		if (res.empty()) {
			L = cur + 1;
		} else {
			ans = cur;
			R = cur - 1;
		}
	}
	printf("%lld\n", ans); 
	return 0;
}

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

int main(){
  int d;
  ll g;
  cin >> d >> g;
  vector<P> p(d);
  int ans = 0;
  rep(i,d){
    cin >> p[i].first;
    cin >> p[i].second;
    ans += p[i].first;
  }

  rep(i,1<<(d+1)){
    ll score = 0;
    int cnt = 0;
    rep(j,d){
      if((i & 1<<j) == (1<<j)){
        score += (j+1)*100 * p[j].first + p[j].second;
        cnt += p[j].first;
      }
    }
    if(score < g){
      int j = d-1;
      while(score < g && j >= 0){
        if((i & 1<<j) != (1<<j)){
          int k=1;
          while(score < g && k<p[j].first){
            score += (j+1)*100;
            cnt++;
            k++;
          }
        }
        j--;
      }
    }
    if(cnt < ans && score >= g) ans = cnt;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3596
// When you are hungry for something and you're determined and you're focused 
// and you're committed to something it's hard to surrender, isn't it?

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ll long long 
#define int ll
#define mod 1000000007
#define mod1 1000000006
#define modi 998244353
#define setbit(x) __builtin_popcount(x)
#define ff first
#define ss second
#define pb push_back
vector<ll> vi[300005];
int color[100005];
ll pa[500005];
ll si[500005];
#define pb push_back
bool visi[1000005]={false};
bool is[100005];
ll fac[10000001];
ll prime[400005];
ll bit[100005];
const long double eps = 1.0e-14;      // allowable error
#define fio ios_base::sync_with_stdio(false); cin.tie(NULL);
 
 
void fact(){
    fac[0]=1;
    for(int i=1;i<=10000000;i++){
        fac[i]=(fac[i-1]*i)%mod;
    }
    return ;
}
void sieve(){
    prime[0]=0;
    prime[1]=0;
    for(int i=2;i<400005;i++){
        prime[i]=1;
    }
    for(int i=2;i*i<400005;i++){
        if(prime[i]==1){
            for(int j=i*i;j<400005;j+=i){
                prime[j]=0;
            }
        }
    }
    
}
 
ll power(ll n , ll p ){
    if(p==0)
        return 1;
    
    ll res = power((n*n)%mod,p/2);
    if(p%2==1)
        res = (n*res)%mod;
    
    return res;
}
 
 
void upd(ll i,ll val,ll n) {
    for(;i<=n;i+=i&(-i))
        bit[i]+=val;
}
 
ll qry(ll i) {
    ll sum=0;
    for(;i>0;i-=i&(-i))
        sum+=bit[i];
    return sum;
}
 
 
ll fin(ll u) {
    if(pa[u]==u)
        return u;
    return fin(pa[u]);
}
 
void uni(ll u,ll v) {
    ll p1=fin(u);
    ll p2=fin(v);
    if(p1==p2)
        return;
    if(si[p1]<si[p2])
        swap(p1,p2);
    si[p1]+=si[p2];
    pa[p2]=p1;
    return;
}
 
int32_t main() {
    fio

    int n;
    cin >> n;
    
    int arr[n];
    for(int i=0;i<n;i++)
    cin >> arr[i];
    
    sort(arr,arr+n);
    
    int st=1,ed=arr[n-1];
    int ans=INT_MAX,loc=-1;
    for(int i=st;i<=ed;i++) {
        int c=0;
        for(int j=0;j<n;j++) {
            c+=(int)pow((abs(i-arr[j])),2);
        }
        if(c<ans){
        ans = c;
        //loc=i;
        }
        }
        
        cout << ans ;
    
    
    return 0;
    
}

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

int main() {

  char c;
  cin >> c;

  if(c == 'a'){
    cout << "vowel" << endl;
  }else if (c == 'e'){
    cout << "vowel" << endl;
  }else if (c == 'i'){
    cout << "vowel" << endl;
  }else if (c == 'o'){
    cout << "vowel" << endl;
  }else if (c == 'u'){
    cout << "vowel" << endl;
  }else{
    cout << "consonant" << endl;
  }
  
  /*string S;
  cin >> S;

  //文字列の長さを取得する
  S.size();
  //計算結果を代入する
  int T = 1;

  for (int i=0; i < S.size(); i++){
    if(S.at(i)=='+'){
      T += 1;
    }else if(S.at(i)=='-'){
      T -= 1;
    }
    }
  cout << T << endl;*/
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define endl "\n"
const int MOD=1e9+7;
#ifndef HOME
#define cerr if(0)cerr
#endif

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin>>n>>m;
    int a[n][m];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            char c;
            cin>>c;
            if(c=='.'){
                a[i][j]=0;
            }else{
                a[i][j]=1;
            }
        }
    }
    int dp[n][m] = {0};
    bool vis = false;
    for(int i=0;i<n;i++){
        if(a[i][0]){
            vis = true;
        }
        if(!vis){
            dp[i][0]=1;
        }else{
            dp[i][0]=0;
        }
        
        
    }
    vis = false;
    for(int j=0;j<m;j++){

        if(a[0][j]){
            vis = true;
        }
        if(!vis){
            dp[0][j]=1;
        }else{
            dp[0][j]=0;
        }
         
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<m;j++){
            if(a[i][j]){
                continue;
            }
            dp[i][j] = 0;
            if(!a[i-1][j]){
                dp[i][j] += dp[i-1][j];
                dp[i][j] %= MOD;
            }
            if(!a[i][j-1]){
                dp[i][j] += dp[i][j-1];
                dp[i][j] %= MOD;
            }
        }
    }
    dp[2][0];
    cout<<dp[n-1][m-1] % MOD;
    
    return 0;
    
}



Measured memory_bytes: 15872
#include<iostream>

using namespace std;

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

int main(){
    int a, b;
    cin >> a >> b;
    if(a%3==0 || b%3==0 || (a+b)%3==0){
        cout << "Possible" << endl;
    } else {
        cout << "Impossible" << endl;
    }
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
using namespace std;
typedef long long LL;
int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}
int main()
{
	deque<int>q;
	LL n;cin>>n;n++;int tot=0,i;
	for (i=40;!(n>>i&1);i--);
	while (i--) {
		q.push_back(++tot);
		if (n>>i&1)
			q.push_front(++tot);
	}
	printf("%d\n",tot<<1);
	for (auto k:q) printf("%d ",k);
	for (int i=1;i<=tot;i++) printf("%d ",i);
	return 0;
}


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

int main()
{
  int64_t n; cin >> n;
  
  int64_t ans=0;
  for (int i=1; i<=n; i++) {
    if (i %3 == 0 || i%5 == 0)
      continue;
    ans += i;
  }
   cout << ans<< endl;
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

const ll mod = 1e9+7;
struct mint {
    ll x;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res/=a;
    }
};

int main(){
    int N,K;
    cin >> N >> K;
    vector<int> A(N);
    for(int i=0;i<N;i++){
        cin >> A[i];
    }
    mint ans = 0,k = K;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(A[j]>A[i]){
                if(j<i) ans += k*(k+1)/2;
                else ans += k*(k-1)/2;
            }
        }
    }
    cout << ans.x << endl;
}

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

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

#define loop(i, n) for(int i = 0;i < n;i++)
#define IINF 2e9
#define MOD 1e9+7

int main(void){

    int n;
    cin >> n;

    vector<int> d(n*2);

    int count = 0;
    for(int i = 0;i < n;i++){
        int a, b;
        cin >> a >> b;
        if(a == b) count++;
        else count = 0;

        if(count >= 3){
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 3628
/* Author : Pranav Deshmukh
            PICT,Pune
   Purpose: Practice B Codeforces Round #653 (Div. 3)
*/

#include<bits/stdc++.h>
using namespace std;

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#define int             long long
#define dip(type,var)   type var; cin>>var;
#define dipi(x)			int x; cin>>x;
#define w(x)            int x; cin>>x; while(x--)
#define mka(arr,n,type) type *arr=new type[n];
#define foi(i,n)		for(int i=0;i<n;i++)
#define mod             pow(10,9)+7
#define inf             1e18
#define endl			"\n"
#define ff              first
#define ss              second
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >

void c_p_c()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin.tie(0);
#ifndef ONLINE_JUDGE

	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

int32_t main() {
	c_p_c();
	dipi(a);
	dipi(b);
	dipi(c);
	dipi(k);
	int count = 0, sum = 0;
	while (count < k) {
		if (count < a) {
			sum += 1;
		}
		else if (count < a + b) {

		}
		else
			sum -= 1;
		count++;
	}
	cout << sum << endl;
	return 0;
}

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

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

   if ((b != 1 && a > b) || (a == 1 && b != a)) {
       cout << "Alice" << endl;
   } else if (a == b) {
       cout << "Draw" << endl;
   } else if ((a != 1 && a < b) || (b == 1 && a != b)){
       cout << "Bob" << endl;
   }
}

Measured memory_bytes: 256
import math
def mchoose(n, k):
    return (math.factorial(n+k-1) // (math.factorial(k) * math.factorial(n-1)))%(10**9+7)

N, K = map(int, input().split())

for i in range(1,K+1):
    if N-K<i-1:
        print(0)
    else:
        print((mchoose(i,K-i)*mchoose(i+1,N-K-i+1))%(10**9+7))

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

long long gcd(long long a, long long b) {
  long long t;    // 補助変数
  while ( b != 0 ) {
    t = a%b; a = b; b = t;
  }
  return a;
}
int main() {
	long long n,m,ans;
	cin>>n>>m;
	string s,t;
	cin>>s>>t;
	int x=gcd(n,m);
	ans=(n*m)/x;
	for(int i=0;i<x;i++){
	    if(s[(i*n)/x]!=t[(i*m)/x])ans=-1;
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 512
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

//Building a Space Station
public class Main{

	class E implements Comparable<E>{
		int s, t;
		double d;
		public E(int s, int t, double d) {
			this.s = s;
			this.t = t;
			this.d = d;
		}
		public int compareTo(E o) {
			return d-o.d<0?-1:o.d-d<0?1:0;
		}
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt();
			if(n==0)break;
			UnionFind u = new UnionFind(n);
			double[][] p = new double[n][3];
			double[] r = new double[n];
			for(int i=0;i<n;i++){
				for(int j=0;j<3;j++)p[i][j]=sc.nextDouble();
				r[i] = sc.nextDouble();
			}
			PriorityQueue<E> q = new PriorityQueue<E>();
			for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){
				if(u.find(i, j))continue;
				double d = Math.sqrt(Math.pow(p[i][0]-p[j][0], 2)+Math.pow(p[i][1]-p[j][1], 2)+Math.pow(p[i][2]-p[j][2], 2))-r[i]-r[j];
				if(d<1e-6)u.union(i, j);
				else q.add(new E(i, j, d));
			}
			double res = 0;
			while(u.num>1){
				E e = q.poll();
				if(!u.find(e.s, e.t)){
					u.union(e.s, e.t);
					res+=e.d;
				}
			}
			System.out.printf("%.3f\n", res);
		}
	}
	
	class UnionFind {
		final int[] tree;
		int num;
		public UnionFind(int n) {
			this.tree = new int[n];
			Arrays.fill(tree, -1);
			num=n;
		}

		// merge the set contains x and the set contains y
		void union(int x, int y) {
			x = root(x);
			y = root(y);
			if(x != y) {
				if(tree[x] < tree[y]) {
					x ^= y; y ^= x; x^= y;
				}
				tree[x] += tree[y];
				tree[y] = x;
				num--;
			}
		}
		// decide if x and y belong to the same set
		boolean find(int x, int y) {
			return root(x) == root(y);
		}
		int root(int x) {
			return tree[x] < 0 ? x : (tree[x] = root(tree[x]));
		}
		// return size of the set contains x
		int size(int x) {
			return -tree[root(x)];
		}
		// return the number of sets
		int getNum() {
			return num;
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

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

/**
 * vector<int>ar(3);
 * for(auto&e:ar){
 *     scanf("%d",&e);
 * }
 * sort(ar.begin(),ar.end())
 * int sum=accumulate(ar.begin(),ar.end(),0);
 ***/

int main(){
    double pai=3.141592653589;
    int n,a,b;
    char c[1000],rc[1000],s[10];
    scanf("%s",&c);
    scanf("%d",&n);
    string w;
    for(int i=0;i<n;i++){
        scanf("%s",&s);
        w=s;
        if(w=="print"){
            scanf("%d %d",&a,&b);
            for(int i=a;i<=b;i++){
                printf("%c",c[i]);
            }
            printf("\n");
        }else if(w=="replace"){
            scanf("%d %d %s",&a,&b,&rc);
            int j=0;
            for(int i=a;i<=b;i++){
                c[i]=rc[j];
                j++;
            }
        }else{
            scanf("%d %d",&a,&b);
            int j=b;
            strcpy(rc,c);
            for(int i=a;i<=b;i++){
                c[i]=rc[j];
                j--;
            }
        }
    }
    return 0;
}

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

int main() {
    int n; cin >> n;
    int abc[n][3];
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> abc[i][j];
        }
    }
    
    // print the input
    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < 3; j++) {
    //         cout << abc[i][j] << " ";
    //     } cout << endl;
    // } cout << endl;
    
    int H[n][3];
    H[0][0] = abc[0][0];
    H[0][1] = abc[0][1];
    H[0][2] = abc[0][2];
    
    for (int row = 1; row < n; row++) {
        for (int col = 0; col < 3; col++) {
            int m_happ = INT_MIN;
            for (int prev_day = 0; prev_day < 3; prev_day++) {
                if (col == prev_day) {
                    continue;
                } else {
                    int hap = abc[row][col] + H[row - 1][prev_day];
                    if (hap > m_happ) {
                        m_happ = hap;
                    }
                }
            }
            H[row][col] = m_happ;
            // cout << m_happ << " ";
        } // cout << endl;
    } // cout << endl;
    
    int ans = INT_MIN;
    
    for (int i = 0; i < 3; i++) {
        if (H[n - 1][i] > ans) {
            ans = H[n - 1][i];
        }
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 2560
use std::io::*;

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let a: i64 = itr.next().unwrap().parse().unwrap();
    let b: i64 = itr.next().unwrap().parse().unwrap();
    let c: i64 = itr.next().unwrap().parse().unwrap();
    let x = 4 * a * b;
    let y = (c - a - b);
    if y > 0 && x < y*y {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 4352
n = int(input())
a = input()
b = input()
c = input()

ans = 0
for i in range(n):
    s = len(set((a[i], b[i], c[i])))
    if s == 1:
        pass
    if s == 2:
        ans += 1
    if s == 3:
        ans += 2

print(ans)

Measured memory_bytes: 3064
import sys
from collections import Counter, defaultdict
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return list(map(int, input().split()))

ans = []
while 1:
	n = INT()
	if n == 0:
		break
	c = input().split()

	cnt = Counter(c)
	tmp = cnt.most_common()
	if len(tmp) == 1:
		ans.append("{} {}".format(tmp[0][0], n//2+1))
	elif tmp[0][1] == tmp[1][1]:  # 引き分け
		ans.append("TIE")
	else:  # 決着がつく
		count = defaultdict(int)
		count["hoge"] += 1
		for i in range(n):
			count[c[i]] += 1
			max_ = max(count.values())
			if max_ > n//2:  # 決定
				ans.append("{} {}".format(tmp[0][0], i+1))
				break
			for j in count:  # すべてのキーのとりうる最大得点を求める．
				# print(j, count[j] + (n-i-1))
				if j != tmp[0][0] and count[j] + (n-i-1) >= max_:
					break
			else:  # もうこえない
				ans.append("{} {}".format(tmp[0][0], i+1))
				break
			
for x in ans:
	print(x)



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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(in.readLine());
    int[] a = new int[n-1];
    String[] str = in.readLine().split(" ");
    int[] boss = new int[n];
    for(int i=0; i<n-1; i++) {
      a[i] = Integer.parseInt(str[i]); 
      boss[a[i]-1]++;
    }
    for(int i=0; i<n; i++) {
      System.out.println(boss[i]);
    }
  }
}

Measured memory_bytes: 66404
H, W = gets.split.map(&:to_i)
S = readlines.map(&:strip)

@g = []; @g[0] = @g[H + 1] = ['#'] * (W + 2)
(1 .. H).each{|h| @g[h] = ['#'] + S[h - 1].split('') + ['#']}

def bfs(v)
  q = [v]
  d = {}; d[v] = 0
  while !q.empty?
    x, y = q.shift
    [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]].each do |a, b|
      next if @g[a][b] == '#' || !d[[a, b]].nil?
      q << [a, b]
      d[[a, b]] = d[[x, y]] + 1
    end
  end
  d.values.max
end

puts [*1 .. H].product([*1 .. W]).map{|x, y| bfs([x, y]) if @g[x][y] == '.'}.compact.max

Measured memory_bytes: 2172
#include <bits/stdc++.h>
using namespace std;
const int MAX_N=500005;
char str[MAX_N];
int dp[MAX_N],L[MAX_N];
int main()
{
	int n;
	scanf("%d",&n);
	scanf("%s",str+1); 
    for(int i=1;i<=n;i++)
    {
        if(str[i]=='1')L[i]=L[i-1];
        else L[i]=i;
    }
    for(int i=1;i<=n;i++)
    {
        dp[i]=dp[i-1];
        if(str[i]=='1')
        {
            if(str[i-1]=='0' && str[i-2]=='1')
            {
                dp[i]=max(dp[i],dp[L[i-2]]+(i-2)-L[i-2]);
                dp[i]=max(dp[i],dp[L[i-2]+1]+(i-2)-L[i-2]-1);
            }
            else if(L[i]>1 && str[L[i]-1]=='1')
            {
                dp[i]=max(dp[i],dp[L[i]-2]+i-L[i]);
            }
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}

Measured memory_bytes: 4608
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <iomanip>
using namespace std;
#define int long long

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

    int n,p; cin >> n >> p;

    vector<int> a(100000001);

    if(p == 1){
        cout << 1 << endl;
        return 0;
    }
    if(n == 1){
        cout << p << endl;
        return 0;
    }

    int i = 2;

    while(p > 1 && i < 10000000){
        if(p % i == 0){
            a.at(i) ++;
            p /= i;
        }else{
            i ++;
        }
    }

    int ans = 1;
    for(int i = 2;i < 100000001;i ++){
        if(a.at(i) >= n){
            int j = a.at(i) / n;
            ans *= pow(i,j);
        }
    }

    cout << ans << endl;

}

Measured memory_bytes: 784304
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,x,d,gcd,ans;
template<typename T>
void fin(T a){
  cout<<a<<endl;
  exit(0);
}

signed main(){
  cin>>n>>x>>d;
  if(!d&&!x)fin(1);
  if(!d)fin(n+1);
  if(!x)fin(n*(n-1)/2+1);
  if(x<0)x*=-1,d*=-1;
  gcd=__gcd(x,abs(d));x/=gcd;d/=gcd;
  ans=n*n*(n+1)/2-n*(n+1)*(2*n+1)/6+n+1;
  for(int i=0;i<=n;i++)ans-=max(0LL,min((n*2-i-1)*i/2,(n*2-i-d-1)*(i+d)/2+x)-max(i*(i-1)/2,(i+d)*(i+d-1)/2+x)+1);
  fin(ans);
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <iterator>
#include <math.h>
#include <cmath>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <regex>
#include <stdexcept>
#include <unordered_set>
#include <string>
#include <map>
#include <iomanip>
#include <sstream>
#include <cassert>
#include <time.h>
#include <numeric>
#include <complex>

using namespace std;
using ull = unsigned long long;
using ll = long long;
using ld = long double;
using D = double;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;

#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()
#define fill(x, y) memset(x, y, sizeof(x))
#define makeunique(x) sort(all(x)), (x).resize(unique(all(x)) - (x).begin())
#define rep(i, x)  for(int i = 0; i < (x); i++)
#define rrep(i, x) for(int i = (x - 1); i >= 0; i--)
#define y1 y1_1234413
#define j1 j1_235
#define y0 y0_235
#define j0 j0_256
#define fi first
#define se second
#define itn int
#define re return
#define prev PREV
#define next NEXT

#define sz(x) ((int)x.size())

const int inf = 2e9;
const ld st = 0.000001;
const ld pi = acos((ld)-1);
const int maxn = 2*1000005;

#define FILENAME ""

ll a[100000 + 100][3];
ll dp[100000 + 100][3];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            ll x;
            cin >> x;
            a[i][j] = x;
        }
    }
    for (int i = 0; i < 3; i++) {
        dp[0][i] = a[0][i];
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                if (j != k) {
                    dp[i][j] = max(dp[i - 1][k] + a[i][j], dp[i][j]);
                }
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < 3; i++) {
        ans = max(ans, dp[n - 1][i]);
    }
    cout << ans;
    return 0;
}



Measured memory_bytes: 4992
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	num, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return num
}

func main() {
	sc.Split(bufio.ScanWords)

	N := nextInt()

	count := 1
	crash := 0

	ans := func() int {
		for i := 0; i < N; i++ {
			a := nextInt()
			if a == count {
				count++
			} else {
				crash++
			}
		}
		if count == 1 {
			return -1
		}
		return crash
	}()

	fmt.Println(ans)
}


Measured memory_bytes: 2304
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll N;
char S[305][305];
int main(){
  cin>>N;
  for(ll i=0;i<N;i++){
    string s;cin>>s;
    for(ll j=0;j<N;j++)
      S[i][j]=s[j];
  }
  ll ans=0;
  for(ll i=-(N-1);i<N;i++){
    bool judge=true;
    for(ll A=0;A<N;A++)
      for(ll B=0;B<N;B++)
        if(S[A][(B+i+N)%N]!=S[B][(A+i+N)%N]){judge=false;break;}
  if(judge)
    ans+=(N-abs(i));
      }cout<<ans<<endl;
   return 0;
}

Measured memory_bytes: 3696
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
//ll mod = 998244353;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s += "0";
    int ans = 0;
    rep(i, n) {
        if (s[i] != s[i+1]) ++ans;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3728
#include <stdio.h>

int main(void)
{
	int l[1000], neko_stack[100];
	int i, j, k, n, err;
	
	scanf( "%d", &n );
	for( i = 0; i < n; i++ )
	{
		scanf( "%d", &l[i] );
	}

	i = 0;
	j = 0;
	err = 0;
	do
	{
		//printf( "l[%d]=%d,", i, l[i] );
		if( l[i] > 0 )
		{
			if( j > 0 )
			{
				for( k = j - 1; k >= 0; k-- )
				{
					if( l[i] == neko_stack[k] )
					{
						err = i+1;
					}
					else if( l[i] + neko_stack[k] == 0 )
					{
						k = 0;
					}
				}
			}
			if( err == 0 )
			{
				neko_stack[j] = l[i];
				//printf( "neko_stack[%d]=%d\n", j, neko_stack[j] );
				j++;
			}
			else
			{
				//printf( "error_p=%d\n", err );
			}
		}
		else if( l[i] < 0 )
		{
			if( j > 0 )
			{
				if( l[i] + neko_stack[j-1] != 0 )
				{
					err = i+1;
				}
			}
			else if( j == 0 )
			{
				err = i+1;
			}
			if( err == 0 )
			{
				j--;
				//printf( "neko_stack[%d]=%d\n", j-1, neko_stack[j-1] );
			}
			else
			{
				//printf( "error_n=%d\n", err );
			}
		}
		i++;
		if( err == 0 && n == i )
		{
			err = 9999;
		}
	}
	while( err == 0 );

	if( err == 9999 )
	{
		printf( "OK\n" );
	}
	else
	{
		printf( "%d\n", err );
	}

	return 0;
}


Measured memory_bytes: 2104
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
n,q=map(int,input().split())
a=UnionFind(n)
for i in range(q):
    t,u,v=input().split()
    u,v=int(u),int(v)
    if t=='0':
        a.union(u,v)
    else:
        print(int(a.same(u,v)))

Measured memory_bytes: 11484
import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] Az = new int[N];
        for (int i = 0; i < N; i++) {
            Az[i] = sc.nextInt();
        }
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < N; i++) {
            set.add(Az[i]);
        }
        if (set.size() == N){
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}


Measured memory_bytes: 69392
import sys
input = sys.stdin.readline

#input
N = int(input())
D = list(map(int, input().split()))

#output
from collections import Counter
l = Counter(D).most_common()
l = sorted(l, key = lambda x:x[0])
M = len(l)

answer = 1

if D[0] != 0:
    answer = 0
elif l[0][1] != 1:
    answer = 0
else:
    for i in range(M-1):
        if l[i][0] + 1 != l[i+1][0]:
            answer = 0
for i in range(M-1):
    answer *= pow(l[i][1],l[i+1][1])
print(answer % 998244353)

Measured memory_bytes: 72220
#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <functional>
#include <iomanip>
#include <bitset>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
const long long mod = 1000000007;
typedef long long ll;

int main() {

	int n;
	cin >> n;
	vector<double> a(n);
	rep(i, n) cin >> a.at(i);
	double ans = 0.0;
	rep(i, n) {
		ans += 1 / a.at(i);
	}
	cout << double(1 / ans) << endl;

	return 0;
}

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

int main() {
	string S;
	bool check = true;
	cin >> S;
	for (int i = 0; i < 3; i++) {
		if (S[i] == S[i + 1]) check = false;
	}
	if (check) cout << "Good" << endl;
	else cout << "Bad" << endl;
}

Measured memory_bytes: 256
# include <bits/stdc++.h>  
using namespace std;  
  
typedef long long LL;  
const int maxn = 1e5;  
int n, a, b, m[maxn+3];  
  
bool judge(LL x)  
{  
    LL sum = 0;  
    for(int i=0; i<n; ++i)  
    {  
        LL t = (LL)m[i]-x*b;  
        if(t>0)  
        {  
            sum += (int)ceil(t*1.0/(a-b));  
            if(sum > x)  
                return false;  
        }  
    }  
    return true;  
}  
int main()  
{  
    while(~scanf("%d%d%d",&n,&a,&b))  
    {  
        int imax = 0;  
        for(int i=0; i<n; ++i) scanf("%d",&m[i]), imax = max(imax, m[i]);  
        LL l=0, r=imax;  
        while(l<r)  
        {  
            LL mid = l+r>>1;  
            if(judge(mid)) r=mid;  
            else l=mid+1;  
        }  
        printf("%lld\n",r);  
    }  
    return 0;  
}  

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long int n,k,sum=0,che,sums=0;cin>>n>>k;
  long long int a[n],b[n];
  vector<long long int> v(n),w={};
  for(long long int i=0;i<n;i++) cin>>a[i]>>b[i];
  for(long long int i=0;i<n;i++) v.at(i)=a[i];
  sort(v.begin(),v.end());
  w.push_back(v.at(0));
  che=v.at(0);
  for(long long int i=1;i<n;i++){
    if(che!=v.at(i)){
      w.push_back(v.at(i));
      che=v.at(i);
    }
  }
  for(int i=0;i<n;i++) sums+=b[i];
  if(k<sums/2){ 
  for(long long int i=0;i<w.size();i++){
    for(long long int j=0;j<n;j++){
      if(a[j]==w.at(i)){
        sum+=b[j];
      }
    }
    if(sum>=k){
      cout<<w.at(i)<<endl;
      break;
    }
  }
  }
  else{
    for(long long int i=w.size()-1;i>=0;i--){
    for(long long int j=0;j<n;j++){
      if(a[j]==w.at(i)){
        sum+=b[j];
      }
    }
    if(sum>=sums+1-k){
      cout<<w.at(i)<<endl;
      break;
    }
  }
  }
}


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


#define ll long long
#define ull unsigned ll
#define vi vector <int>
#define ii pair <int, int>
#define vii vector <ii>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define INF (int)1e9
#define EPS 1e-9
#define forall(i, a, b) for(int i=a; i < b; i++)
#define all(a) a.begin(), a.end()
#define in(a,b) ( (b).find(a) != (b).end())
#define pb push_back
#define fill(a,constant) memset(a, constant, sizeof(a))
#define mp make_pair
#define checkbit(n,b) ( (n >> b) & 1)
#define sort(a) sort(all(a))
#define PI acos(-1.0)
#define DEBUG 0

int main ()

{
    fast;
    
    int n;
    cin >> n;
    
    int answer = (n/500)*500*2 + ((n-(n/500)*500)/5)*5;
    
    if (answer < 0) cout << 0 << endl;
    else cout << answer << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(), (c).end());
const long long MOD = 10e9 + 7;
typedef long long ll;

int main(){
	int S;
	cin >> S;
	int A = S % 100;//下二桁
	int B = (S - A) / 100;//上二桁
	string ans;
	if(A > 12 || A == 0){
		if(B > 12 || B == 0){
			ans = "NA";
		} else {
			ans = "MMYY";
		}
	} else {
		if(B > 12 || B == 0){
			ans = "YYMM";
		} else {
			ans = "AMBIGUOUS";
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <limits>
#include <algorithm>
#include <utility>
#include <sstream>
#include <numeric>
#include <iterator>

using namespace std;

#define repd(i,a,b) for (int i=(a);i<(b);++i)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
typedef pair<int, int> P;

int main(int argc, const char * argv[]) {
  // vector<vector<bool>> bingo(3, vector<bool>(3,false));
  vector<int> bingo(101, -1);
  rep(i, 3){
    rep(j, 3){
      int a;
      cin >> a;
      bingo[a] = (i*3)+j;
    }
  }
  int n;
  cin >> n;
  vector<bool> vec(9, false);
  rep(i, n){
    int b;
    cin >> b;
    if(bingo[b] >= 0){
      vec[bingo[b]] = true;
    }
  }
  rep(i, 3){
    int count = 0;
    int count2 = 0;
    rep(j, 3){
      // cout << vec[(i*3)+j] << endl;
      if(vec[(i*3)+j]) count++;
      if(vec[(j*3)+i]) count2++;
    }
    if(count == 3 || count2 == 3){
      cout << "Yes" << endl;
      return 0;
    }
  }
  if(vec[0] && vec[4] && vec[8]){
    cout << "Yes" << endl;
    return 0;
  }
  if(vec[2] && vec[4] && vec[6]){
    cout << "Yes" << endl;
    return 0;
  }  
  cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 888
#include<algorithm>
#include<cmath>
#include<complex>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<deque>
#include<functional>
#include<iostream>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<sstream>
#include<string>
#include<vector>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
typedef long long ll;

using namespace std;

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

	string a, b;
	cin >> a >> b;
	if (a[0] == b[2] && a[1] == b[1] && a[2] == b[0])cout << "YES" << endl;
	else cout << "NO" << endl;
}

Measured memory_bytes: 3584
#include <iostream>
using namespace std;
int main()
{
    int i,p[100005],N,K,Q,A;
    cin>>N>>K>>Q;
    for(i=1;i<=N;i++)
        p[i]=K;
    for(i=1;i<=Q;i++)
    {
        scanf("%d",&A);
        p[A]++;
    }
    for(i=1;i<=N;i++)
    {
        if(p[i]-Q>0)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
typedef pair<int, vector<P>> S;
void output(int time, S s){
    printf("time %d, inv %d\n", time, s.first);
    for(auto vi : s.second) printf("(%d, %d) ", vi.first, vi.second);
    cout << endl;
}
int main(){
    int n;
    while(cin >> n && n){
        vector<P> v(n);
        for(auto& vi : v) cin >> vi.first >> vi.second;
        for(auto& vi : v) if(vi.first < vi.second) swap(vi.first, vi.second);
        int inv = 0;
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if(v[i].first > v[j].first) inv++;
                if(v[i].first > v[j].second) inv++;
                if(v[i].second > v[j].first) inv++;
                if(v[i].second > v[j].second) inv++;
            }
        }
        priority_queue<S, vector<S>, greater<S>> que;
        set<vector<P>> used;
        que.push(S(inv, v));
        used.insert(v);
        const int BEAM = 1 << 8;
        for(int iter = 0; ; iter++){
            priority_queue<S, vector<S>, greater<S>> nque;
            if(que.top().first == 0){
                cout << iter << endl;
                break;
            }
            for(int i = 0; i < BEAM && !que.empty(); i++){
                S s = que.top(); que.pop();
                int inv = s.first;
                vector<P>& v = s.second;
                for(int i = 0; i < n - 1; i++){
                    if(v[i].first > v[i + 1].second){
                        int ninv = inv - 1;
                        swap(v[i].first, v[i + 1].second);
                        bool b1 = false, b2 = false;
                        if(v[i].first < v[i].second){
                            swap(v[i].first, v[i].second);
                            ninv--;
                            b1 = true;
                        }
                        if(v[i + 1].first < v[i + 1].second){
                            swap(v[i + 1].first, v[i + 1].second);
                            ninv--;
                            b2 = true;
                        }
                        if(!used.count(v)){
                            used.insert(v);
                            nque.push(S(ninv, v));
                        }
                        if(b1) swap(v[i].first, v[i].second);
                        if(b2) swap(v[i + 1].first, v[i + 1].second);
                        swap(v[i].first, v[i + 1].second);
                    }
                }
            }
            que.swap(nque);
        }
    }
    return 0;
}

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

int main(){
  int N; cin>>N;
  vector<int> vec(N);
  for(int i=0;i<N;i++){
    cin>>vec[i];
  }
  bool zero;
  int zcnt,ans=0;
  for(int i=0;/*o*/;i++){
    zero=true; zcnt=0;
    for(int j=0;j<N;j++){
      if(vec[j]>0){
        if(zero){
          zcnt++; zero=false;
        }
      }else{
        zero=true;
      }
      vec[j]--;
    }
    ans+=zcnt;
    if(zcnt)
      zcnt=0;
    else
      break;
  }
  cout<<ans<<endl;
}

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

public class Main {

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);
		Long inputNum = scanner.nextLong();
		inputNum++;
		String[] digitStr = String.valueOf(inputNum).split("");

		List<Integer> numArray = new ArrayList<>();

		for (String str : digitStr) {
			numArray.add(Integer.parseInt(str));
		}
      
		int firstNum = numArray.get(0);
		int maxSum = 0;

		for (int i = 1; i < numArray.size(); i++) {
			maxSum += 9;
		}
		maxSum += firstNum - 1;
		System.out.println(maxSum);
	}
}

Measured memory_bytes: 23764
// Template from https://techracho.bpsinc.jp/jhonda/2019_08_05/78537

// input macro for competive-programming from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };

    ($iter:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, bytes) => {
        read_value!($iter, String).into_bytes()
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    use std::io::Read;
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();

    println!("{}", solve(&s));
}

macro_rules! test {
    ($($input:expr => $output:expr),* $(,)*) => {
        #[test]
        fn solve_test() {
            $(
                assert_eq!(solve($input), $output);
            )*
        }
    };
}

test! {
r#"5 2"# => "4",
r#"6 4"# => "3",
r#"7 7"# => "1",
r#"15 11"# => "5",

}

fn solve(src: &str) -> String {
    input! {
        source = src,
        n: usize,
        i: usize,
    }
    (n - i + 1).to_string()
}

Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int maxn = 2e5 + 5 ;
int n , k ;
int a[maxn] ;
int main()
{
	ll ans = 0 ;
	scanf("%d%d" , &n , &k) ;
	for(int i = 1 ; i <= n ; i ++)  scanf("%d" , &a[i]) ;
	sort(a + 1 , a + n + 1) ;
	for(int i = 1 ; i <= n - k ; i ++)  ans += a[i] ;
	printf("%lld\n" , ans) ;
	return 0 ;
}


Measured memory_bytes: 1024
=begin
－－－－－－－－－－－－－－
  N = 入力値
  cnt = 桁数
  ans = 答え
－－－－－－－－－－－－－－
  digitsメソッドを作成(num)
    1: cnt += 1
    2: num /10
    3. num < 0 になったら cnt を返す
  メソッド－－－－－－－－－－

  1: 1 ~ N まで繰り返す(i)
  2: digits(i) % 2 が 0 以外なら ans += 1
  3: ans を出力
=end

def digits(num)
  cnt = 0;
  while num > 0
    cnt += 1;
    num /= 10;
  end
  return cnt;
end

n = gets.to_i;
ans = 0;
(n+1).times do |i|
  ans += 1 unless digits(i) % 2 == 0
end

puts ans

Measured memory_bytes: 1788
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <queue>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
template <class T> void setmin(T & a, T const & b) { if (b < a) a = b; }
void bfs(vector<int> xs, map<vector<int>,int> & memo) {
    int n = xs.size();
    queue<vector<int> > que;
    que.emplace(xs);
    while (not que.empty()) {
        vector<int> xs = que.front(); que.pop();
        int depth = memo[xs];
        repeat (r,n+1) repeat (l,r-1) {
            reverse(xs.begin() + l, xs.begin() + r);
            if (not memo.count(xs)) {
                memo[xs] = depth + 1;
                if (depth+1 < (n-1)/2) {
                    que.emplace(xs);
                }
            }
            reverse(xs.begin() + l, xs.begin() + r);
        }
    }
};
int main() {
    // input
    int n; scanf("%d", &n);
    vector<int> a(n);
    repeat (i,n) {
        scanf("%d", &a[i]);
        -- a[i];
    }
    // compute
    map<vector<int>,int> memo_l, memo_r;
    vector<int> b(n); iota(b.begin(), b.end(), 0);
    bfs(b, memo_l);
    bfs(a, memo_r);
    int ans = n-1;
    do {
        if (memo_l.count(b) and memo_r.count(b)) {
            setmin(ans, memo_l[b] + memo_r[b]);
        }
    } while (next_permutation(b.begin(), b.end()));
    // output
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 66476
#include<bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int N, M;
    int A[1000];

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

    int res = 0;
    double limit = (double)all / (4.0 * (double)M);
    for (int i = 0; i < N ; i++) {
        if(!(A[i] < limit)){
            res += 1;
        }
    }

    cout << (res >= M ? "Yes" : "No") << endl;

}


Measured memory_bytes: 256