akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <string.h>
#include <string>
#include <vector>
#include <array>
#include <algorithm>

int main()
{
    int N, X, Y;

    scanf("%d %d %d", &N, &X, &Y);

    std::vector<int> total(N);

    for (int dist = 1; dist < N; ++dist)
    {
        for (int i = 1; i <= (N - dist); ++i)
        {
            int diff = dist;
            int j = i + dist;

            diff = std::min(diff, std::abs(X - i) + 1 + std::abs(j - Y));
            diff = std::min(diff, std::abs(Y - i) + 1 + std::abs(j - X));

            total[diff]++;
            //printf("%d - %d : %d\n", i, target, diff);
        }
    }

    size_t size = total.size();
    for (size_t i = 1; i < size; ++i)
    {
        printf("%d\n", total[i]);
    }
    return 0;
}


Measured memory_bytes: 256
using System;
class Program{
  static void Main(){
    int N=int.Parse(Console.ReadLine());
    string s=Console.ReadLine();
    char[] C=s.ToCharArray();
    int V=0;
    for(int i=1;i<N;i++){
      if(C[i]!=C[i-1])V++;
    }
    Console.WriteLine(V+1);
  }
}

Measured memory_bytes: 11488
#include<stdio.h>
int main(void){
	double r,A,p;
	scanf("%lf",&r);
	A=3.141592653589793*r*r;
	p=2*3.141592653589793*r;
	printf("%.6lf %.6lf\n",A,p);
	return 0;
	}


Measured memory_bytes: 2048
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<utility>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<queue>
#include<stack>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)

using namespace std;

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

    ll N, D;
    cin >> N >> D;
    cout << (N + 2 * D) / (2 * D + 1) << "\n";
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
 public static void main(String[] args){
   Scanner sc = new Scanner(System.in);
 
   int A = sc.nextInt();
   int B = sc.nextInt();

   int sum =(1+(B-A-1))*(B-A-1)/2;
   
   System.out.println(sum-A);
 }
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define EPS 0.0000000001
#define INF 1000000000
#define MOD 1000000007
typedef long long ll;

int main()
{
    int k,x;
    cin>>k>>x;
    if(x-k+1<-1000000){
        int c=-1000000;
        for(int i=0;i<k*2-1;i++){
            cout<<c<<" ";
            c++;
        }
        cout<<endl;
    }
    else{
        for(int i=0;i<k*2-1;i++){
            cout<<x-k+1<<" ";
            x++;
        }
        cout<<endl;
    }
}


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#define MAX 10000

int main(){
  int num[MAX];
  int i,j,n,d,count = 0;

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

  for(i=0; i<n; i++){
    d = 0;
    if(num[i] == 2) d = 0;
    else if(num[i]%2 == 0) continue;
    else {
      for(j=3; j<=sqrt(num[i]); j+=2){
      if(num[i]%j == 0) {
	d = 1;
	break;
       }
     }
    }
    if(d == 0) count++;
  }

  printf("%d\n",count);
  return 0;
}



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

typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define dump(x)  cout << #x << " = " << (x) << endl;	//debug
#define SZ(x) ((int)(x).size())
#define REP(i, n) for(ll i = 0; i < (n); i++)
#define REPR(i, n) for (ll i = (n); i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define RFOR(i, a, b) for (ll i = (a); i >= (b); i--)
#define ps(s) cout << #s << endl;
#define pv(v) cout << (v) << endl;
#define pvd(v) cout << setprecision(16) << res << endl;
#define ALL(a)  (a).begin(),(a).end()
#define RANGE(a, l, r)  (a).begin()+(l),(a).begin()+(r)

int main() {
	double a, b;
	cin >> a >> b;
	FOR(i, 1, 1000) {
		double x = i*0.08;
		double y = i*0.1;
		x = (int)x;
		y = (int)y;
		if (x == a&&y == b) {
			pv(i);
			return(0);
		}
	}
	ps(-1);
	return(0);
}

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

int main(){
  	int a,b,c;
  	cin >> a >> b >> c;
  
  	for(int i = a; i <= b;i++){
		if((a <= i && i <= a+c-1) || (b-c+1 <= i && i <= b)){
         	cout << i << endl; 
        }
    }
 	return 0; 
}

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

template<class Ty>
using passive_queue = priority_queue<Ty, vector<Ty>, greater<Ty>>;

struct Problem {

	void Solve() {
		UL K; cin >> K;

		if (K < 10) { cout << K << endl; return; }

		queue<UL> Q;
		for (UL i = 1; i < 10; i++) Q.push(i);
		UL i = 9;
		UL ans = 0;
		while (true) {
			UL p = Q.front(); Q.pop();
			UL d = p % 10;
			p *= 10;
			if (d != 0) {
				i++; ans = p + d - 1; if (i == K) break;
				Q.push(ans);
			}
			i++; ans = p + d; if (i == K) break;
			Q.push(ans);
			if (d != 9) {
				i++; ans = p + d + 1; if (i == K) break;
				Q.push(ans);
			}
		}
		cout << ans << endl;
	}

	Problem();
};
int main() {
	unique_ptr<Problem> p(new Problem());
	p->Solve();
	return 0;
}
Problem::Problem() {
	cout << fixed << setprecision(10);
}


Measured memory_bytes: 512
"""
考え方のポイント
・自分以外では割り切れないような数の個数を求める
　→ 数列の各項に対して〇（割り切れない）×がついていって、〇の個数を数える
・[2, 2]みたいな入力は、他の数で割り切れるようになるので、同じ数が入っていると絶対に×になる。

まずは入力が全部異なる前提で進める。
範囲内の整数からなる全て配列dを用意する。
→ 入力の数列を約数としてもつ数にチェックをしていく（Anに2が含まれていれば、2の倍数全てにチェック（+1)する）
→ チェック後にd[i]をみたとき、d[i]の約数がan中に何個存在するかが示されていることになる。（2∈Aiならd[5](=6)の値は必ず1以上になってる)
"""
N = int(input())
An = [int(i) for i in input().split()]
An.sort()
max_val = 10**6+1
d = [0] * max_val


# O(N) = O(2*10^5)
# d[i]のうち、配列の値の位置を+1しとく。
for i in An:
    d[i] += 1
    # O(MlogM) = 6*10^6
    # 始めてその倍数がきたときだけ
    if(d[i] == 1):
        # [2, 2]などの重複がない場合（既にカウントされているものではない場合)
        # 倍数の位置にも2としておいて以降はみないようにする
        for val in range(i*2, max_val, i):
            d[val] = 2

print(d.count(1))

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

#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPL(i,a,n) for(ll i=a;i<n;++i)
#define RUP(a,b) ((a+b-1)/(b))
#define ENT "\n"
#define SORTVG(v) sort(v.begin(),v.end(),greater<>())
#define SORTV(v) sort(v.begin(),v.end())
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define INF LLONG_MAX/2
#define int long long

typedef long long ll;
typedef tuple<int,int,bool> Tb;
typedef pair<int,int> Pii;
typedef vector<int> Vi;

template<class T> void chmax(T& a, T b) {if(a < b){a=b;}}
template<class T> void chmin(T& a, T b) {if(a > b){a=b;}}
template<class T> void YesNo(T& a) {if(a){cout << "Yes" << ENT;}else{cout << "No" << ENT;}}
template<class T> void YESNO(T& a) {if(a){cout << "YES" << ENT;}else{cout << "NO" << ENT;}}
template<class T> void AorB(T& a, string A,string B) {if(a){cout << A << ENT;}else{cout << B << ENT;}}

int gcd(int n, int m) {
    return m ? gcd(m, n % m) : n;
}

int atcoder(){
    int n,m;
    string s,t;
    bool ans=true;
    cin>>n>>m>>s>>t;
    int g=gcd(n,m);
    int checks=n/g,checkt=m/g;
    REP(i,0,g){
        if(s[checks*i]!=t[checkt*i]) ans=false;
    }
    if(ans) cout<<n*m/g<<ENT;
    else cout<<-1<<ENT;
    return 0;
}


signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    atcoder();
    return 0;
}


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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    long double a;
    long double b;

    cin>>a>>b;
    
    long double ans = a*b;

    cout<<(long long int)ans<<"\n";

    return 0;
}

Measured memory_bytes: 3748
N = int(input())

P = [1]

for i in range(1, N):
    if 6**i > N:
        break
    P.append(6**i)

for i in range(1, N):
    if 9**i > N:
        break
    P.append(9**i)

P.sort()

DP = [float('inf')] * (N + 1)
DP[0] = 0
for i in range(N):
    for p in P:
        if i + p > N:
            break
        DP[i+p] = min(DP[i+p], DP[i] + 1)
print(DP[N])


Measured memory_bytes: 46032
#include<bits/stdc++.h>
using namespace std;
int main (){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int h,w,m;
	cin>>h>>w>>m;
	set<pair<int,int>> st;
	vector<int> a(h+1),b(w+1);
	for (int i=0;i<m;i++){
		int u,v;
		cin>>u>>v;
		st.insert(make_pair(u,v));
		a[u]++;
		b[v]++;
	}
	vector<pair<int,int>> a1,b1;
	for (int i=1;i<=h;i++) a1.push_back(make_pair(a[i],i));
	for (int i=1;i<=w;i++) b1.push_back(make_pair(b[i],i));
	sort(a1.begin(),a1.end());
	sort(b1.begin(),b1.end());
	reverse(a1.begin(),a1.end());
	reverse(b1.begin(),b1.end());
	vector<int> hang={a1[0].second},cot={b1[0].second};
	int i=1,bom=a1[0].first+b1[0].first;
	while (i<a1.size()&&a1[i].first==a1[i-1].first) {
		hang.push_back(a1[i].second);
		i++;
	}
	i=1;
	while (i<b1.size()&&b1[i].first==b1[i-1].first){
		cot.push_back(b1[i].second);
		i++;
	}
	for (i=0;i<hang.size();i++){
		for (int j=0;j<cot.size();j++) if (st.find(make_pair(hang[i],cot[j]))==st.end()){
			cout<<bom;
			return 0;
		}
	}
	cout<<bom-1;
	return 0;
}

Measured memory_bytes: 28716
#include <iostream>

int main() {
  int A, B, C;
  std::cin >> A >> B >> C;

  if ( A == B ) {
    std::cout << C << std::endl;
  } else if ( A == C ) {
    std::cout << B << std::endl;
  } else if ( B == C ) {
    std::cout << A << std::endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i=a; i<n; i++)
#define RREP(i, a, n) for(ll i=n-1; i>=a; i--)
#define SIZE_N (2<<15)
typedef long long ll;
const ll mod =1e9+7;
const ll inf =1e18;
using namespace std;

ll n;
int main() {
    while(cin>>n, n){
        ll cnt=0;

        for(int i=1 ; i*i <= n ; i++){
            if(i*i == n) cnt++;
            for(int j=i ; i*i + j*j <= n ; j++){
                if(i*i + j*j == n) cnt++;
                for(int k=j ; i*i + j*j + k*k <= n ; k++){
                    if(i*i + j*j + k*k == n) cnt++;
                    for(int l=k ; i*i + j*j + k*k + l*l <= n ; l++){
                        if(i*i + j*j + k*k + l*l == n) cnt++;
                    }
                }
            }
        }

        cout<<cnt<<endl;
    }
    return 0;
}


Measured memory_bytes: 3012
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define lli  long long int   //used int to avoid mle
#define ulli unsigned long long int 
#define ld long double
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define loop(i,a,b) for(lli i=a;i<b;i++)
#define initialize(array,size,value) for(lli i=0;i<size;i++) array[i]=value
#define couta(array,size) for(lli i=0;i<size;i++) cout<<array[i]<<" "
#define vl vector<lli>
#define vp vector< pair <lli,lli> >
#define sl set<lli>
#define spl set<pll>
#define msl multiset <lli>
#define msp multiset <pll>
#define pll pair<lli, lli>
#define mll map<lli, lli>              //for( map<lli, lli>::iterator i=temp.begin();i!=temp.end();i++)cout<<i->fi<<" "<<i->se<<endl;
#define mvl map<lli, vl>
#define umll unordered_map<lli, lli>
#define vt vector<pair<lli, pll >  >
#define vf vector<pair<pll,pll > >
#define qu queue<lli>
#define pq priority_queue<lli>
#define dq deque <lli>
#define ptr vector<lli>::iterator
#define bs(array,x) binary_search(array.begin(),array.end(),x)
#define lb(array,x) lower_bound(array.begin(),array.end(),x)
#define ub(array,x) upper_bound(array.begin(),array.end(),x)
#define nobw(array,i,j) upper_bound(array.begin(), array.end(), j)-lower_bound(array.begin(), array.end(), i) //number of numbers between i & j
#define vc clear()
#define fbo find_by_order //returns iterator
#define fok order_of_key //return index
#define endl '\n'
#define sp system("pause");
#define INF 9223372036854775807
#define MINF -9223372036854775808
#define start_routine() int begtime = clock();
#define end_routine() int endtime = clock(); cerr << endl << "Time elapsed: " << (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms"; return 0
lli mod=998244353;
lli inf=9223372036854775807;
//string s=bitset<32>(n).to_string();
typedef tree<lli,null_type,less<lli>,rb_tree_tag, // change both to lli if set is req insted of multiset
tree_order_statistics_node_update> indexed_set;
int main()
{
	lli t;
	t=1;//cin>>t;
	while(t--){
		lli n;
		cin>>n;
		lli s[n];
		lli an=0;
		loop(i,0,n)cin>>s[i];
		for(lli i=0;i<n;i++)if(i%2==0 && s[i]%2==1)an++;
		cout<<an;
		
		
		
	}
 
    return 0;
}

Measured memory_bytes: 3596
package main

import "fmt"
import "strings"

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	A := make([][]string, 0, 0)
	B := make([][]string, 0, 0)
	for i := 0; i < n; i++ {
		var tmp string
		fmt.Scan(&tmp)
		tmpString := strings.Split(tmp, "")
		A = append(A, tmpString)
	}
	for i := 0; i < m; i++ {
		var tmp string
		fmt.Scan(&tmp)
		tmpString := strings.Split(tmp, "")
		B = append(B, tmpString)
	}

	result := true

	for i := 0; i <= n-m; i++ {
		for j := 0; j <= n-m; j++ {
			result = true
			for k := 0; k < m; k++ {
				for l := 0; l < m; l++ {
					if B[k][l] != A[i+k][j+l] {
						result = false
					}
				}
			}
			if result {
				fmt.Println("Yes")
				return
			}

		}
	}

	fmt.Println("No")

}

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

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

  for (int i = 40000; ; i--) {
    if (i * i <= n) {
      cout << i * i << endl;
      break;
    }
  }
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int a = scanner.nextInt()
				, b = scanner.nextInt()
				, c = scanner.nextInt();
		
		String ans = "NO";
		for (int i = 0;; i++) {
			if (i*a%b==c) {
				ans = "YES";
				break;
			}
			if (i*a>a*b) {
				break;
			}
		}
		System.out.println(ans);
		
		
		scanner.close();
	}
}


Measured memory_bytes: 23764
def main():
    n,a,b = map(int,input().split())
    MOD = 10**9 +7
    s = pow(2,n,MOD)-1
    
    print(comb_mod(n,MOD,a,b,s))

def comb_mod(n, mod,a,b,s):
    numerator = 1
    denominator = 1
    for i in range(b):
        numerator = (numerator * (n - i)) % mod
        denominator = (denominator * (i + 1)) % mod
        if i == a-1 or i == b-1:
            s = s - (numerator * pow(denominator, mod - 2, mod)) % mod
    return s%mod


if __name__=='__main__':
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define endl "\n"
#define ii pair<int, int>
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define make_pair mp
#define MAX (int)1e5+5
#define INF (int)1e9
#define K 26






int32_t main (){
		string s;
		int t1,t2;
		cin >> s;
		int t = s.size();
		t1 = (t-1)/2;
		t1-=1;
		t2 = (t+3)/2;
		t2-=1;
		string a,b;
		for(int i = 0; i<=t1; i++){
			a.pb(s[i]);
		}
		for(int i = t2; i<s.size(); i++){
			b.pb(s[i]);
		}
		
		if(a == b){
			cout << "Yes\n";
		}else{
			cout << "No\n";
		}
	
	
	
	return 0;
}

Measured memory_bytes: 256
import collections

h, w = map(int, input().split())
s = [[""]*(w+2)]
for _ in range(h):
    _s = list(input())
    _s.insert(0, "")
    _s.append("")
    s.append(_s)
s.append([""]*(w+2))

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if s[i][j] == "#":
            continue

        q = collections.deque([[i, j]])

        f = [[-1]*(w+2) for _ in range(h+2)]
        f[i][j] += 1

        while 0 < len(q):
            _x, _y = q.pop()
            for _dx, _dy in zip(dx, dy):
                x = _x + _dx
                y = _y + _dy
                if s[x][y] == "." and f[x][y] == -1:
                    f[x][y] = f[_x][_y] + 1
                    q.appendleft([x, y])

        for _f in f:
            ans = max(ans, max(_f))

print(ans)


Measured memory_bytes: 3316
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
#include <string>
#include <set>
#include <map>
using namespace std;

int main()
{
	int32_t N, Q;
	cin >> N >> Q;

	string S;
	cin >> S;

	//vector<int32_t> cnts(N);
	int32_t cnts[100000];
	cnts[0] = 0;
	for (int32_t i = 0; i < N - 1; i++) {
		cnts[i + 1] = cnts[i];
		if (S[i] == 'A' && S[i + 1] == 'C')
			cnts[i + 1]++;
	}

	for (int32_t i = 0; i < Q; i++) {
		int32_t l, r;
		cin >> l >> r;
		l--;
		r--;
		cout << (cnts[r] - cnts[l]) << endl;
	}

	return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(),(a).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
double EPS=1e-8;
int INF = 2e9;
char fld[1050][1050];
int cnt[1050][1050];
bool used[1050][1050];
int main(){
	int h,w,turn=0;
	cin>>h>>w;
	REP(i,h)REP(j,w)cin>>fld[j][i];
	memset(used,false,sizeof(used));
	queue<P> Q;
	REP(i,h)REP(j,w){
		if(fld[j][i]=='.')continue;
		for(int x=-1;x<=1;x++)for(int y=-1;y<=1;y++)if(fld[j+x][i+y]=='.')cnt[j][i]++;
		if(cnt[j][i]>=(fld[j][i]-'0')){
			Q.push(P(j,i));
			used[j][i]=true;
		}
	}
	if(Q.size())turn++;
	else{
		cout<<0<<endl;
		return 0;
	}
	bool update=true;
	while(update){
		int ql=Q.size();
		REP(i,ql){
			P p=Q.front();Q.pop();
			for(int x=-1;x<=1;x++){
				for(int y=-1;y<=1;y++){
					if(fld[p.first+x][p.second+y]!='.'){
						cnt[p.first+x][p.second+y]++;
						if(cnt[p.first+x][p.second+y]>=(fld[p.first+x][p.second+y]-'0')&&!used[p.first+x][p.second+y]){
							Q.push(P(p.first+x,p.second+y));
							used[p.first+x][p.second+y]=true;
						}
					}
				}
			}
		}
		if(!Q.size()){
			cout<<turn<<endl;
			return 0;
		}
		turn++;
	}
}

Measured memory_bytes: 7640
N,Q = map(int, input().split())
S = input()
L = []
for i in range(Q):
    L.append([int(x) for x in input().split()])
    
ac_list = [0 for i in range(N)]
ac_num = 0
for i in range(1, N):
    pre = S[i-1]
    ac_list[i] = ac_list[i-1]
    if pre == "A" and S[i] == "C":
        ac_num += 1
        ac_list[i] = ac_num

for i in range(Q):
    ans = ac_list[L[i][1]-1] - ac_list[L[i][0]-1]
    print(ans)

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

int main(void){
    int a,f=0;
    cin>>a;
    for(int i=1;i<=9;i++){
        if(a%i==0){
            if(a/i<=9){
                cout<<"Yes"<<endl;
                return 0;
            }
        }
    }
    cout<<"No"<<endl;
    
}

Measured memory_bytes: 256
#include <stdio.h>
  int main() {
      int A, B, i; 
      scanf("%d %d" ,&A ,&B);
      i = A+B;
      if(i < 10){
      printf("%d\n" , i);
      }
      else{
      printf("error\n");
      }
      return 0;
      }

Measured memory_bytes: 128
def main():
    n, k = map(int, input().split())
    xs = list(map(int, input().split()))
    res = 1 << 30
    for i in range(k - 1, n):
        d = xs[i] - xs[i - k + 1] + min(abs(xs[i]), abs(xs[i - k + 1]))
        res = min(res, d)
    print(res)


if __name__ == '__main__':
    main()


Measured memory_bytes: 14224
N = int(input())
L = list(map(int, input().split()))
ans = 0

for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            a, b, c = L[i], L[j], L[k]
            if a == b or b == c or c == a:
                continue
            if a + b > c and b + c > a and c + a > b:
                ans += 1

print(ans)

Measured memory_bytes: 73744
#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)
using namespace std;
using ll = long long;

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

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

/**
 * @brief 多次元 vector の作成
 * @author えびちゃん
 */
namespace detail {
    template<typename T, int N>
    auto make_vec(vector<int>& sizes, T const& x) {
        if constexpr (N == 1) {
            return vector(sizes[0], x);
        } else {
            int size = sizes[N-1];
            sizes.pop_back();
            return vector(size, make_vec<T, N-1>(sizes, x));
        }
    }
}
template<typename T, int N>
auto make_vec(int const(&sizes)[N], T const& x = T()) {
    vector<int> s(N);
    for (int i = 0; i < N; ++i) s[i] = sizes[N-i-1];
    return detail::make_vec<T, N>(s, x);
}

__attribute__((constructor))
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    ll k, a, b;
    cin >> k >> a >> b;
    if (a + 2 >= b || 1 + k <= a) {
        cout << k + 1 << '\n';
        return 0;
    }

    ll rest = k - (a - 1);
    ll ans = a;
    if (rest & 1) ans++, rest--;
    ans += rest / 2 * (b - a);
    cout << ans << '\n';
}


Measured memory_bytes: 3660
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

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

typedef long long lint;

using namespace std;

int main(){
  lint T1,T2,A1,A2,B1,B2;
  cin>>T1>>T2>>A1>>A2>>B1>>B2;
  A1-=B1;
  A2-=B2;
  if(A1<0){
    A1*=-1;
    A2*=-1;
  }
  lint diff=-(T1*A1+T2*A2);
  if(diff<0){
    cout<<0<<endl;
    return 0;    
  }
  if(diff==0){
    cout<<"infinity"<<endl;
    return 0;
  }
  cout<<((T1*A1)/diff)*2+1-((T1*A1)%diff==0?1:0)<<endl;
  return 0;
}


Measured memory_bytes: 256
// D - joisino's travel
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define rp(i,s,e) for(int i=(s);i<(e);++i)

void warshall_floyd(vvi &D){//1_origin
	rp(relay,1,D.size()) rp(from,1,D.size()) rp(to,1,D.size())
		D[from][to] = min(D[from][to], D[from][relay] + D[relay][to]);
}

#define DIST_MAX 1000000000
#define N_MAX 200
#define R_MAX 8
int N,M,R;
vi RR(R_MAX+1);
vvi D(N_MAX+1, vi(N_MAX+1, DIST_MAX));
int ans_dist = DIST_MAX;

vi visited(R_MAX+1, false);

void dfs(int p, int depth, int dist){
	if(depth+1 >= R+1) ans_dist = min(ans_dist, dist);
	else
		rp(r, 1, R+1){
			if(visited[r]) continue;
			visited[r] = true;
			dfs(RR[r], depth+1, dist+D[p][RR[r]]);
			visited[r] = false;
		}
}

int main(){
	cin>>N>>M>>R;
	rp(i, 1, R+1) cin>>RR[i];
	rp(i, 0, N+1) D[i][i] = 0;
	rp(i, 1, N+1) D[0][i] = D[i][0] = 0;
	rp(i, 0, M) rp(j, 0, 3){ int a,b,c; cin>>a>>b>>c; D[a][b] = D[b][a] = c; }
	warshall_floyd(D);
	dfs(0, 0, 0);
	cout<< ans_dist <<endl;
}

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

void swap(int A[], int i, int j) {
    int tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;
}

int partition(int A[], int p, int r) {
    int pivot = A[r];
    int i, j;

    i = p - 1;
    for(j = 0; j < r; j++) {
        if(A[j] <= pivot) {
            i++;
            swap(A, i, j);
        }
    }
    swap(A, i + 1, r);
    return i + 1;
}

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

    int q = partition(A, 0, n - 1);
    for(int i = 0; i < n; i++) {
        if(i > 0) printf(" ");
        if(i == q)
            printf("[%d]", A[i]);
        else
            printf("%d", A[i]);
    }
    printf("\n");
}

Measured memory_bytes: 3464
#include <iostream>
using namespace std;
int main(){
    int a, moneyF, yearL, vary, i1, i2, i3, s, moneyB1, moneyB2, risi1, risi2, moneyto, max;
    double per;
    i1 = 0;
    cin >> a;
    while(1){
        i1++;
        if(i1>a){break;}
        cin >> moneyF >> yearL >> vary;
        i2 = 0;
        max = 0;
        while(1){
            i2++;
            if(i2>vary){break;}
            cin >> s >> per >> moneyB1;
            i3 = 0;
            moneyB2 = moneyF;
            risi2 = 0;
            if(s==0){
                while(1){
                    i3++;
                    if(i3>yearL){break;}
                    risi1 = moneyB2 * per;
                    moneyB2 = moneyB2 - moneyB1;
                    risi2 = risi2 + risi1;
                }
            }
            else{
                while(1){
                    i3++;
                    if(i3>yearL){break;}
                    risi1 = moneyB2 * per;
                    moneyB2 = moneyB2 + risi1 - moneyB1;
                }
            }
            moneyto = moneyB2 + risi2;
            if(max<moneyto){max = moneyto;}
        }
        cout << max << endl;
        
        
    }
    return 0;

}

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

int main() {
  string x;
  cin >> x;
  
  int count = 0;
  
  if (x[0] == '1') {
    count++;
  }
  if (x[1] == '1') {
    count++;
  }
  if (x[2] == '1') {
    count++;
  }
  cout << count << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(n); i++)
int main() {
  int a, b, c;
  cin >> a >> b >> c;
  int maxx = max({a,b,c});
  while((maxx*3)%2 != (a+b+c)%2){
    maxx++;
  }
  cout << (maxx * 3 - (a + b + c)) / 2 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define ld long double
#define f(a, b) for (ll i = a; i <= b; i++)
#define pb push_back
#define pf push_front
#define mp make_pair
using namespace std;
#define N 200005
const int INF = 1000000001;
const int MOD = 1000000007;
void c_p_c()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

int dp[1001][1001] = {0};
int ways(int h, int w) {
    //int dp[1001][1001]={0};
    if (dp[0][0] == -1) {
        return 0;
    }
    for (int j = 0; j < w; j++) {
        if (dp[0][j] == -1) {
            break;
        }
        dp[0][j] = 1;
    }
    for (int i = 0; i < h; i++) {
        if (dp[i][0] == -1) {
            break;
        }
        dp[i][0] = 1;
    }
    for (int i = 1; i < h; i++) {
        for (int j = 1; j < w; j++) {
            if (dp[i][j] == -1)
                continue;
            dp[i][j] = 0;
            if (dp[i][j - 1] != -1)
                dp[i][j] = dp[i][j - 1] % MOD;;
            if (dp[i - 1][j] != -1) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;;
            }
        }
    }
    if (dp[h - 1][w - 1] == -1)
        return 0;

    return dp[h - 1][w - 1];


}
int32_t main() {
    c_p_c();
    memset(dp, 0, sizeof dp);

    int h, w;
    cin >> h >> w;

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            char no;
            cin >> no;
            if (no == '#') {
                dp[i][j] = -1;
            }
        }

    }
    cout << ways(h, w);
}


Measured memory_bytes: 11492
package main

import (
	"fmt"
	"strconv"
)

func main() {
	var n string
	fmt.Scan(&n)
	var sum int
	sum = 0
	for _, c := range n {
		a, _ := strconv.Atoi(string([]rune{c}))
		sum = sum + int(a)
	}
	if sum%9 == 0 {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 4064
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException{
    BufferedReader x=new BufferedReader(new InputStreamReader(System.in));
    String f=x.readLine();
    String[] s=f.split(" ");
    int a,b;
    a=Integer.parseInt(s[0]);
    b=Integer.parseInt(s[1]);
    
    if(a == b)
        System.out.println("a == b");
    else if(a<b)
        System.out.println("a < b");
    else
        System.out.println("a > b");
    }
}

Measured memory_bytes: 24148
import std.stdio, std.conv, std.string, std.bigint;
import std.math, std.random, std.datetime;
import std.array, std.range, std.algorithm, std.container;
string read(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }

class Node{
	int id;
	int groupId;
	Node[] adjs;
	bool isVisited = 0;
	this(int id){
		this.id = id;
		}
	void setGroupId(int gid){
		this.groupId = gid;
		this.isVisited = true;
		foreach(adj; adjs) if(! adj.isVisited) adj.setGroupId(gid);
		}
	}


void main(){
	auto n = read.to!int;
	auto m = read.to!int;
	
	auto ps = readln.chomp.split.to!(int[]).map!(i => i - 1)().array;
	
	Node[] nodes;
	foreach(i; 0 .. n) nodes ~= new Node(i);
	
	foreach(j; 0 .. m){
		auto x = read.to!int - 1;
		auto y = read.to!int - 1;
		nodes[x].adjs ~= nodes[y];
		nodes[y].adjs ~= nodes[x];
		}
	
	foreach(nd; nodes){
		if(nd.isVisited) continue;
		nd.setGroupId(nd.id);
		}
	
	int count = 0;
	foreach(i; 0 .. n){
		if(nodes[i].groupId == nodes[ps[i]].groupId){
			count += 1;
			}
		}
	
	count.writeln;
	}

Measured memory_bytes: 27068
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>

using namespace std;
using ll = long long;

int res = 0;
vector<int> colors;
vector<vector<pair<int, int>>> g;

void dfs(int v, int p, int pc) {
	int c = 0;
	for (auto& e : g[v]) {
		if (e.first == p) {
			continue;
		}
		++c;
		if (pc == c) {
			++c;
		}
		colors[e.second] = c;
		dfs(e.first, v, c);
	}
	res = max(res, c);
}

int main() {
	int n;
	cin >> n;
	colors.resize(n - 1);
	g.resize(n + 1);
	for (int i = 0; i < n - 1; ++i) {
		int a, b;
		cin >> a >> b;
		g[a].push_back({b, i});
		g[b].push_back({a, i});
	}
	dfs(1, -1, -1);
	cout << res << "\n";
	for (int i = 0; i < n - 1; ++i) {
		cout << colors[i] << "\n";
	}
	return 0;
}


Measured memory_bytes: 7424
#include <bits/stdc++.h>
//#pragma GCC diagnostic error "-Wconversion"
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(vec) vec.begin(), vec.end()
#define mp(a, b) make_pair(a, b)
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = (1e9 + 7);
using namespace std;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
ll dp[100010];
ll gcd(ll x, ll y){
  return y == 0 ? x : gcd(y, x % y);
}
ll lcg(ll x, ll y){
  return x * y / gcd(x, y);
}
ll digits(ll x){
  ll length = 0;
  while (x > 0){
    x /= 10;
    length++;
  }
  return length;
  if (x == 0) return 0;
}
map<ll, ll> factor(ll n){
  map<ll, ll> ans;
  ll a = 2;
  while (n >= a * a){
    if (n % a == 0){
      ans[a]++;
      n /= a;
    }
    else a++;
  }
  ans[n]++;
  return ans;
}
template<class T> inline bool chmin(T& a, T b){
  if (a > b){
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b){
  if (a < b){
    a = b;
    return true;
  }
  return false;
}

int main(){
  cout << fixed << setprecision(15);
  //int ans = 0;
  string ans = "";

  string keys; cin >> keys;
  rep(i, keys.size()){
    if (keys[i] == '0') ans.push_back('0');
    if (keys[i] == '1') ans.push_back('1');
    if (keys[i] == 'B' && ans.size() != 0) ans.pop_back();
  }

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

Measured memory_bytes: 3592
#include <bits/stdc++.h>
// #include <atcoder/all>
#define ll long long int
#define ld long double
#define yorn(f) std::cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) std::cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i, n) for (ll i = 1; i < (ll)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) std::cout << x << endl;
#define println(x) std::cout << x << endl;
template<typename T>bool mins(T& x,const T&y){if(x>y){x=y;return true;}else return false;}
template<typename T>bool maxs(T& x,const T&y){if(x<y){x=y;return true;}else return false;}
const ll INF = 1e18;
using namespace std;
// using namespace atcoder;
void Main()
{
    ll n;
    cin >> n;
    vector<string> S(n);
    rep(i, n) cin >> S[i];

    vector<ll> A(n);
    vector<ll> B(n);
    rep(i, n) {
        ll l = 0, r = 0;
        rep(j, S[i].size()) {
            if ('(' == S[i][j]) {
                l++;
            }
            if (')' == S[i][j]) {
                if (l >= 1) l--;
                else r++;
            }
            A[i] = r;
            B[i] = l;
        }
    }

    // A[i]: )))の数
    // B[i]: (((の数

    
    vector<pair<ll, ll> > p1, p2;
    rep(i, n) {
        if (A[i] <= B[i]) {
            p1.push_back({A[i], B[i]});
        }
        else {
            p2.push_back({B[i], A[i]});
        };
    }

    sort(all(p1));
    sort(all(p2));
    reverse(all(p2));

    ll cnt = 0;
    for (auto& p: p1) {
        ll a = p.first;
        ll b = p.second;
        cnt -= a;
        if (cnt < 0) {
            put("No");
            return;
        }
        cnt += b;
    }
    for (auto& p: p2) {
        ll a = p.second;
        ll b = p.first;
        cnt -= a;
        if (cnt < 0) {
            put("No");
            return;
        }
        cnt += b;
    }

    yorn(cnt == 0);
}
signed main(){ Main();return 0;}

Measured memory_bytes: 65828
#include <stdio.h>

int main(void)
{
int i, j,H,W;

   while(1){
    scanf("%d %d",&H,&W);

    if(H==0&&W==0)
    break;
    for ( i = 0; i < H; i++ ){
        for ( j = 0; j < W; j++ ){
        if((i+j)%2==0)
            printf("#");
         else 
            printf(".");
    }
    printf("\n");
    }
    printf("\n");
   }
  return 0;
}

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

int main(){
	int W,H;
	cin >> W >> H;
	vector<pair<long long,int>> pq;
	for(int i=0;i<W;i++){
		pair<long long,int> p;
		cin >> p.first;
		p.second=1;
		pq.push_back(p);
	}
	for(int i=0;i<H;i++){
		pair<long long,int> q;
		cin >> q.first;
		q.second=2;
		pq.push_back(q);
	}
	
	sort(pq.begin(),pq.end());
	
	long long ans=0;
	int x=0,y=0;
	
	for(int i=0;i<H+W;i++){
		if(pq[i].second==1){
			x++;
			ans+=pq[i].first*(long long)(H-y+1);
		}
		else{
			y++;
			ans+=pq[i].first*(long long)(W-x+1);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 6512
#include<iostream>

using namespace std;

long long int cclt(long long int n);
long long int c(long long int n);

int main()
{
    long long int n;
    cin>>n;
    long long int rst=0;
    rst=cclt(n);
    cout<<rst<<endl;
    return 0;
}

long long int cclt(long long int n)
{
    if(n==0)
    {
        return 0;
    }
    long long int rst=0,f=1;
    while(n/f>0)
    {
        rst+=cclt(n%f)+(n/f)*c(n%f);
        f*=10;
    }
    return rst;
}

long long int c(long long int n)
{
    int t=1;
    while(n/10>0)
    {
        t*=2;
        n/=10;
    }
    return t;
}

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

#define ARG4(_1, _2, _3, _4, ...) _4
#define rep(...) ARG4(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define REP(i, a) FOR(i, 0, a)
#define FOR(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define rrep(...) ARG4(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define RREP(i, a) RFOR(i, 0, a)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (int)(a); --i)
#define ALL(c) (c).begin(), (c).end()
#define TEN(n) ((ll)(1e##n))
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define let const auto
#define USE_T template <typename T>
#define USE_Ti template <typename T = int>
#define USE_TU template <typename T, typename U>

USE_Ti using duo = std::pair<T, T>;
USE_Ti using vec = std::vector<T>;
using ll = long long;
// clang-format off
USE_TU inline bool chmax(T&x,U a){return x<a&&(x=a,1);}
USE_TU inline bool chmin(T&x,U a){return a<x&&(x=a,1);}
USE_Ti inline T in(){T x;std::cin>>x;return x;}
USE_Ti inline vec<T> in(int n){vec<T> v;v.reserve(n);rep(i,n)v.pb(in<T>());return v;}
USE_T inline void in(T*x,int n){rep(i,n)x[i]=in<T>();}
struct IoSetup {
  IoSetup(){
    using namespace std;
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<setprecision(10);
    cerr<<setprecision(10);
  }
} iosetup;
// clang-format on
// }}}
using namespace std;
const int inf = 1001001001;
const ll infll = 1001001001001001001ll;
const int dd[] = {0, 1, 0, -1, 0};

signed main() {
  auto S = in(6);
  int tot = std::accumulate(ALL(S), 0);
  tot -= *min_element(ALL(S) - 2);
  tot -= *min_element(4 + ALL(S));
  cout << tot << endl;
  return 0;
}

Measured memory_bytes: 3136
N=int(input())
S=input()
list=list(S)
x=0
for j in range(N+1):
    a=0
    for i in range(97,123):

        if (chr(i) in list[0:j]) and (chr(i) in list[j:N]):
            a+=1
    if a>x:
        x=a
print(x)

Measured memory_bytes: 40176
import java.io.*;
import java.util.regex.Pattern;
import java.util.regex.Matcher;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String key = br.readLine();
		int count=0;
		//Pattern p = Pattern.compile(key, Pattern.CASE_INSENSITIVE);
		String line=br.readLine();
		String[] words = line.split(" ",0);
		while(!line.equals("END_OF_TEXT")){
			for(int i=0;i<words.length;i++){
				if(key.equalsIgnoreCase(words[i])){
					count++;
				}
			}
			line=br.readLine();
			words = line.split(" ");
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 16912
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX_N = 100;
const int MAX_M = 50;
long long int comb[MAX_M+5][MAX_M+5];
int P[MAX_N+5], T[MAX_N+5], V[MAX_N+5];
double prob[MAX_N+5][MAX_M+5];
double goal_t[MAX_N+5][MAX_M+5];

void init_comb() {
    comb[0][0] = 1;
    for(int i=1; i<=MAX_M; i++) {
        comb[i][0] = 1;
        for(int j=1; j<=MAX_M; j++) {
            comb[i][j] = comb[i-1][j-1] + comb[i-1][j];
        }
    }
}

int main() {
    init_comb();
    int N, M, L; scanf("%d%d%d", &N, &M, &L);
    for(int i=0; i<N; i++) {
        scanf("%d%d%d", &P[i], &T[i], &V[i]);
        for(int k=0; k<=M; k++) {
            goal_t[i][k] = 1.0 * L / V[i] + k * T[i];
            prob[i][k] = comb[M][k] * pow(P[i] / 100.0, k) * pow((100-P[i]) / 100.0, M-k);
            if(k != 0) prob[i][k] += prob[i][k-1];
        }
    }

    for(int i=0; i<N; i++) {
        double ans = 0.0;
        for(int k=0; k<=M; k++) {
            double player_t = goal_t[i][k], tmp = prob[i][k] - (k != 0 ? prob[i][k-1] : 0);
            for(int j=0; j<N; j++) {
                if(i == j) continue;
                // かてない
                if(player_t > goal_t[j][M]) tmp = 0;
                // よゆう
                else if(player_t < goal_t[j][0]) continue;
                else {
                    int idx = upper_bound(goal_t[j], goal_t[j]+M+1, player_t) - goal_t[j] - 1;
                    tmp *= (1.0 - prob[j][idx]);
                }
            }
            // printf("initial tmp = %.12f, current = %.12f\n", prob[i][k], tmp);
            ans += tmp;
        }
        printf("%.12f\n", ans);
    }
    return 0;
}


Measured memory_bytes: 3080
#include <bits/stdc++.h>
using namespace std;
int n, m, x, y;
int a[107], b[107];

int main() {
	cin >> n >> m >> x >> y;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= m; i++) cin >> b[i];
	sort(a + 1, a + n + 1);
	sort(b + 1, b + m + 1);
	bool flg = 0;
	for(int i = x + 1; i <= y; i++) {
		if(i > a[n] && i <= b[1]) {
			flg = 1; break;
		}
	}
	if(!flg) puts("War");
	else puts("No War");
}

Measured memory_bytes: 256
(let* ((si (loop repeat (read)
                 collect (coerce (read-line) 'list)))
       (a (make-array 26 :initial-element 50)))
 (mapc (lambda (s)
         (let ((b (make-array 26 :initial-element 0))) 
           (mapc (lambda (c)
                   (incf (aref b (- (char-code c) 97))))
               s)
           (loop for y across b
                 for i from 0
                 when (> (aref a i) y)
                 do (setf (aref a i) y))))
       si)
 (loop for x across a
       for i from 97
       do (loop repeat x
                do (princ (code-char i))))
 (fresh-line))

Measured memory_bytes: 19680
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x) x
#define rep(...) MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c) c.begin(),c.end()
#define mp make_pair
#define write(x) cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T, class U>bool chmax(T& a, U&& b) { return a < b ? a = b, 1 : 0; }
template<class T, class U>bool chmin(T& a, U&& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

const double PI = 3.14159265359;

int N;
vector<int> Y, X;

double sumDeg(const vector<int>& order) {
    int y = 0, x = 0;
    double deg = 0.0, sum = 0.0;

    for (int o : order) {
        double nextDeg = 0.0;

        if (x == X[o]) {
            if (y < Y[o]) {
                nextDeg = PI / 2;
            }
            else {
                nextDeg = 3 * PI / 2;
            }
        }
        else {
            nextDeg = X[o] > x ? atan((double)(Y[o] - y) / (X[o] - x)) : PI + atan((double)(Y[o] - y) / (X[o] - x));
            if (nextDeg > 2 * PI) nextDeg - 2 * PI;
        }

        sum += nextDeg > deg ?
            min(nextDeg - deg, 2 * PI - (nextDeg - deg)) :
            min(deg - nextDeg, 2 * PI - (deg - nextDeg));

        deg = nextDeg;
        y = Y[o];
        x = X[o];
    }

    return 180 * sum / PI;
}

int main() {
    cin >> N;
    Y.resize(N);
    X.resize(N);
    rep(i, N) cin >> X[i] >> Y[i];
    Y.push_back(0);
    X.push_back(0);

    vector<int> order(N + 1);
    iota(all(order), 0);

    double ans = 1e9;
    do {
        ans = min(ans, sumDeg(order));
    } while (next_permutation(order.begin(), order.end() - 1));

    write(ans);
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define rep(i, a, n) for (ll i = (a); i < (n); i++)
#define debug(x) cerr << #x << ": " << x << endl;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

int main() {
    ll n;
    string s;
    cin >> n >> s;
    ll cr = 0, cb = 0;
    for(auto c : s) {
        if (c == 'R') cr++;
        else cb++;
    }
    if(cr > cb) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (n); ++i)
#define FOR(i, m, n) for(ll i = m; i < (n); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vii = vector<vi>;
using pii = pair<int, int>; 
using vl = vector<ll>;
using vll = vector<vl>;
using pll = pair<ll, ll>;

int main() {
    string S;
    cin >> S;
    if(S == "ABC"){
        cout << "ARC";
    }else{
        cout << "ABC";
    }
}

Measured memory_bytes: 3596
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <deque>
#define INF_INT (INT_MAX / 2)
#define INF_LONG (LONG_MAX / 2)
//#define DEBUG true
#define DEBUG false
using namespace std;

const int MAX = 100001;
const int MOD = 1000000007;

typedef long long ll;
typedef pair< int, int > pii;
typedef pair< ll, ll > pll;
typedef pair< ll, int > pli;
typedef pair< int, ll > pil;

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

  int h, w, k;
  cin >> h >> w >> k;

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

  ll fib[w];
  fib[0] = 1;
  fib[1] = 2;
  for(int i = 2; i < w; i++){
    fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
  }

  ll dp[h + 1][w];
  fill(dp[0], dp[0] + w, 0);
  dp[0][0] = 1;
  for(int i = 1; i <= h; i++){
    for(int j = 0; j < w; j++){
      ll tmp = (dp[i - 1][j]);
      if(j - 1 >= 0) tmp = (tmp * fib[j - 1]) % MOD;
      if(w - j - 2 >= 0) tmp = (tmp * fib[w - j - 2]) % MOD;
      dp[i][j] = tmp;
      if(j > 0){
        tmp = (dp[i - 1][j - 1]);
        if(j - 2 >= 0) tmp = (tmp * fib[j - 2]) % MOD;
        if(w - j - 2 >= 0) tmp = (tmp * fib[w - j - 2]) % MOD;
        dp[i][j] = (dp[i][j] + tmp) % MOD;
      }
      if(j + 1 < w){
        tmp = (dp[i - 1][j + 1]);
        if(w - j - 3 >= 0) tmp = (tmp * (fib[w - j - 3])) % MOD;
        if(j - 1 >= 0) tmp = (tmp * fib[j - 1]) % MOD;
        dp[i][j] = (dp[i][j] + tmp) % MOD;
      }
    }
  }

  cout << dp[h][k - 1] << endl;

  return 0;
}


Measured memory_bytes: 256
// Problem : G - Longest Path
// Contest : AtCoder - Educational DP Contest
// URL : https://atcoder.jp/contests/dp/tasks/dp_g
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

//Macros

#define ll long long
#define db long double
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define mi map<int,int>
#define mii map<pii,int>
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define sz(x) (int)x.size()
#define mod 1000000007
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define inf 1e10
#define PI acos(-1.0)
#define int long long
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define N 100005

//Solution

vi top;
int dp[N],vis[N];
vi g[N];
int n,m;

void dfs(int u){
    vis[u] = 1;
    for(int i : g[u]){
        if(!vis[i]) dfs(i);
    }
    top.pb(u);
}

void solve(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v; cin>>u>>v;
        g[u].pb(v);
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]) dfs(i);
    }
    reverse(all(top));
    for(int i : top){
        for(int j : g[i]) dp[j] = max(dp[j],dp[i]+1);
    }
    int ans = 0;
    for(int i=1;i<=n;i++) ans = max(ans,dp[i]);
    cout<<ans;
}

signed main(){
    io;
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    int tests;
    //cin>>tests;
    tests = 1;
    while(tests--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 13128
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define ii pair<int,int>
#define F first
#define S second
#define pb push_back
#define pf push_front
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fore(i,a,b) for(int i = a;i < b; i+= 1)
#define forr(i,a) for(int i = a; i >= 0; i--)
#define fori(i,m) for(auto i = m.begin(); i != m.end(); i++) 
#define sz(s) int(s.size())
#define cls(a,car) memset(a,car,sizeof (a))
using namespace std;
typedef long long ll;
const int N = 1 * 1e5 + 5;
const ll mod = 1e9 + 7;
const int INF = INT_MAX;
const ll INFCAD  = ll(INT_MAX) * 2 + 1;
set<ll> s;
void build(){
    queue<ll> q;
    q.push(1LL);
    q.push(2LL);
    q.push(3LL);
    q.push(4LL);
    q.push(5LL);
    q.push(6LL);
    q.push(7LL);
    q.push(8LL);
    q.push(9LL);

    while(sz(q)){
        //cout << q.front() << " coleli\n";
        ll a = q.front();
        s.insert(a);
        q.pop();
        if(sz(s) <= 100000)
        for(int i = 0; i <= 9; i++){
            if(abs(a % 10 - i) <= 1 && a * 10 + i <= 3234566667){
                ll nw = a * 10 + i;
                s.insert(nw);
                q.push(nw);
            }
        }
    }
}
int main(){/*
    freopen("in","r",stdin);
    freopen("out","w",stdout);*/
    fast;
    int k;
    cin >> k;
    build();
    int cnt = 1;
    fori(i,s){
        if(cnt == k){
            cout << *i << '\n';
            break;
        }
        cnt++;
    }
    return 0;   
}

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

a = list(map(int, input().split()))
a = sorted(a)

ans = n
size = a[0]
count = 1
for i in range(1, n):
    if a[i] > size * 2:
        count = 1
    else:
        count += 1
    size += a[i]

print(count)



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

int main() {
	int N;
	cin >>N;
	vector<int> v(N);
	double a;
	for(int i=0;i<N;i++){
		cin >> v.at(i);
	}
	sort(v.begin(),v.end());
	a=v.at(0);
	for(int i=0;i<N-1;i++){
		a=(a+v.at(i+1))/2.0;
	}
	cout << a<<endl;

}

Measured memory_bytes: 384