akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cmath>
using namespace std;
int main(void)
{
	int N, A, bestI;
	double T, H, bestAbs = -1, tempAbs, tempC;
	cin >> N >> T >> A;
	for (int i = 0; i < N; i++)
	{
		cin >> H;
		tempC = T - H * 0.006;
		tempAbs = abs(tempC - A);
		if ((bestAbs == -1)
          ||(bestAbs > tempAbs))
		{
			bestAbs = tempAbs;
			bestI = i + 1;
		}
		else;
	}
	cout << bestI << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(n);++i)
const int INF =1001001001;
using ll=long long;
using P = pair<int,int>;
using Graph =vector<string>;
Graph field;
queue<P> q;

int main() {
  ll a;
  cin>>a;
  if(a<30){
    cout<<"No"<<endl;
  }else{
    cout<<"Yes"<<endl;
  }

}


Measured memory_bytes: 3596
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto abck = readln.split.to!(long[]);
    auto A = abck[0];
    auto B = abck[1];
    auto C = abck[2];
    auto K = abck[3];

    long r;
    if (K > 0) {
        r += min(K, A);
        K -= min(K, A);
    }
    if (K > 0) {
        K -= min(K, B);
    }
    if (K > 0) {
        r -= min(K, C);
    }
    writeln(r);
}

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

public final class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] stone = new int[n];
        int diff2 = Integer.MAX_VALUE;
        for(int i=0; i<n; i++){
          	stone[i] = sc.nextInt();
        }
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i=1; i<n; i++){
            for(int j=1; j<=k; j++){
                if(i-j>=0)
                    diff2  = dp[i-j] + Math.abs(stone[i]-stone[i-j]);
                else
                    diff2 = Integer.MAX_VALUE;
                // System.out.println(dp[j]+" "+diff2);        
                dp[i] = Math.min(dp[i],diff2);
            }
        }
        // for(int i=0; i<n; i++){
        //     System.out.print(dp[i]+" ");
        // }
        System.out.println(dp[n-1]);
        sc.close(); 
    }
}

Measured memory_bytes: 50668
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m,x,a;cin>>n>>m>>x;
	int cntl=0,cntr=0;
	for(int i=0;i<m;i++){
		cin>>a;
		if(a>x)cntr++;
		else cntl++;
	}
	cout<<(min(cntr,cntl))<<endl;
}


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

int main() {
    string s;
    cin >> s;
    cout << ((s[0] == s[1] || s[1] == s[2] || s[2] == s[3]) ? "Bad\n" : "Good\n");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,n,s) for(int i = s; i < (n); ++i)
#define rsrep(i,n,s) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<x<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;

int main() {
    int n, k;
    cin >> n >> k;
    vll m(k, 0);
    rep(i, n) m[(i+1)%k]++;
    ll ans = 0;
    rep(a, k) {
        int tmp = (k-a) % k;
        int b = tmp, c = tmp;
        if ((b+c) % k == 0) ans += m[a]*m[b]*m[c];
    }

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

Measured memory_bytes: 1792
#include <stdio.h>
#define INIT_DEBT 100000

int main() {
    int n_weeks;
    int debt = INIT_DEBT;
    scanf("%d", &n_weeks);
    while (n_weeks-- > 0) {
        debt = debt * 1.05;
        if (debt % 1000 != 0) {
            debt = debt / 1000 * 1000 + 1000;
        }
    }
    printf("%d\n", debt);
    return 0;
}



Measured memory_bytes: 2040
//Author: AnandRaj uux
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll; 

#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define test() int t;cin>>t;while(t--)
#define forn(i,f,n) for(int i=f;i<f+n;i++)
#define rforn(i,l,n) for(int i=l;i>l-n;i--)
#define all(v) v.begin(),v.end()
#define prin(V) for(auto v:V) cout<<v<<" ";cout<<endl
#define take(V,f,n) for(int i=f;i<f+n;i++) cin>>V[i]
#define what(x) cerr<<#x<<" = "<<x<<endl
#define KStest() int t,t1;cin>>t;t1=t;while(t--)
#define KScout cout<<"Case #"<<t1-t<<": "

const int MOD = 1e9+7,MAX = 1e5+5;
/////////////////FastExp///////////////////
ll powN(ll a,ll p)
{
	if(p==0) return 1;
	ll z=powN(a,p/2);
	z=(z*z)%MOD;
	if(p%2) z=(z*a)%MOD;
	return z;
}
/////////////////FastExp///////////////////
//////////////////Sieve////////////////////
vector<bool> is_prime(MAX+1, true);
void Sieve()
{
	is_prime[0] = is_prime[1] = false;
	int i,j;
	for (i = 2; i*i <= MAX; i++) 
	{
    	if (is_prime[i]) 
    	{
        	for (j = i * i; j <= MAX; j += i)
            	is_prime[j] = false;
    	}
	}
}
//////////////////Sieve////////////////////

int main()
{
	int n,m;
	cin>>n>>m;
	vi A(n);
	int tot=0;
	take(A,0,n);
	sort(all(A));
	reverse(all(A));
	for(auto x:A) tot+=x;
	int how=0;
	for(int i=0;i<n;i++)
	{
		if(A[i]*4*m>=tot) how++;
		else break;
	}
	if(how>=m) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;

}		

Measured memory_bytes: 256
from itertools import chain

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

IMP = 100

dp = [[IMP for _ in range(51)] for _ in range(51)]

for i in range(51):
  dp[i][i] = 0
  for j in range(i):
    for m in range(1,51):
      if dp[i%m][j] != IMP:
        dp[i][j] = m
        break


if max(dp[x][y] for x,y in zip(A,B)) == IMP:
  print(-1)
else:
  cost = 0
  m = max(dp[x][y] for x,y in zip(A,B))
  AL = [{a} for a in A]

  def candmin(al,b):
    m = min(dp[a][b] for a in al)
    al.discard(a for a in al if dp[a][b] > m)
    return m

  while m != 0:
    for i,(al,b) in enumerate(zip(AL,B)):
      AL[i] |= set(a%m for a in al)
    cost += 2**m

    m = max(candmin(al,b) for al,b in zip(AL,B))

  print(cost)

Measured memory_bytes: 3188
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val s = readLine()!!
    var count = 0
    var last = ' '
    for (i in 0 until n) {
        if (s[i] != last) {
            last = s[i]
            count += 1
        }
    }
    println(count)
}

Measured memory_bytes: 34404
import java.util.Arrays;
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner stdIn=new Scanner(System.in);
		int N=stdIn.nextInt();
		int A[]=new int[N+1];
		int B[]=new int[N];
		int ans[]=new int[N];
		int C[]=new int[N];
		int z=0;
		long key=0,cout=0;
		for(int i=0;i<3;i++){
			for(int j=0;j<N;j++){
				if(i==0)
					A[j]=stdIn.nextInt();
				if(i==1)
					B[j]=stdIn.nextInt();
				if(i==2)
					C[j]=stdIn.nextInt();
			}
		}
		A[N]=1000000005;
		Arrays.sort(A);
		Arrays.sort(B);
		Arrays.sort(C);
		for(int i=0;i<N;i++){
			while(z<N+1){
				if(A[z]>=B[i]){
					ans[i]=z;
					break;
				}
				z++;
			}
		}z=0;
		for(int i=0;i<N;i++){
			while(z<N+1){
				if(z==N&&B[z-1]<C[i]){
					key+=cout;
					break;
				}
				else
					if(z==N)
						break;
				if(B[z]>=C[i]){
					key+=cout;
					break;
				}
				cout+=ans[z];
				z++;
			}
		}
		System.out.println(key);
	}
}


Measured memory_bytes: 94908
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>

using namespace std;

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

	long long ans=0;
	for(auto it=count.begin();it!=count.end();it++)
	{
//		cout << it->first << " : " << it->second << endl;
		int x=it->first;
		int c=it->second;
		ans+=(x>c ? c : c-x);
	}
	cout << ans << endl;


	
}


Measured memory_bytes: 5120
#include "bits/stdc++.h"
using namespace std;
#define repr(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define MOD 998244353
#define PI 3.1415926535
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<Pll> vPll;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
typedef vector<vector<double>> vvd;
typedef vector<vector<Pi>> vvPi;
typedef priority_queue<int, vector<int>, greater<int>> pqli;
typedef priority_queue<ll, vector<ll>, greater<ll>> pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi>> pqlP;
string YN(bool y) { return (y?"YES":"NO"); }
string yn(bool y) { return (y?"Yes":"No"); }
string ON(bool y) { return (y?"OK":"NG"); }
int main(void)
{
	ll d, n, ans;

	cin>>d>>n;

	ans=(int)pow(100.0, (double)d)*n;

	if(n!=100){
		cout<<ans<<endl;
	}else{
		cout<<ans+(int)pow(100.0, (double)d)<<endl;
	}
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
using namespace std;
constexpr int kMod = 1000000007;
typedef long long LL;

struct Edge {
  int to, dist;
  Edge (int a, int b) : to(a), dist(b) {}
};

vector<vector<Edge>> G;
vector<int> colors;

void dfs(int v, int c) {
  for (const auto& e : G[v]) {
    int u = e.to;
    int w = e.dist;
    int nc = (w % 2 == 0) ? c : -c;
    if (colors[u] == 0) {
      colors[u] = nc;
      dfs(u, nc);
    }
  }
}

int main() {
  int N; cin >> N;
  G.resize(N);
  colors.resize(N, 0);

  for (int i = 0; i < N-1; ++i) {
    int u, v, w; cin >> u >> v >> w; --u, --v;
    G[u].push_back(Edge(v, w));
    G[v].push_back(Edge(u, w));
  }

  colors[0] = 1;
  dfs(0, 1);
  for (int c : colors) {
    cout << max(c, 0) << endl;
  }
}


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

int main() {
    int a, b;
    cin >> a >> b;
    if (a < b){
        cout << "a < b" << endl;
    }
    if (a > b) {
        cout << "a > b" << endl;
    }
    if (a == b) {
        cout << "a == b" << endl;
    }
    return 0;
}


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

int main(){
  int n, k, q;
  cin >> n >> k >> q;
  vector<int> a(q);
  for(int k = 0; k < q; k++){
    cin >> a.at(k);
  }	//input
  
  for(int j = 0; j < q; j++){
    a.at(j)--;
  }
  
  vector<int> point(n, -q);
  for(int i = 0; i < q; i++){
    point.at(a.at(i))++;
  }
  
  for(int i = 0; i < n; i++){
    if(point.at(i) > -k) cout << "Yes" << endl;
    else cout <<"No" << endl;
  }
}

Measured memory_bytes: 4028
#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<functional>
#include<numeric>
#include<random>
 
using namespace std;

// 蟻本pp.43f 区間スケジューリング問題

int main() { 
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	pair<int, int> ab[100000];
	for (int i = 0; i < m; i++) {
		cin >> ab[i].second >> ab[i].first;
	}
	sort(ab, ab + m);
	int ans = 0, x = 0;
	for (int i = 0; i < m; i++) {
		if (x <= ab[i].second) {
			ans++;
			x = ab[i].first;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
int N;
double a[200000];
int main(){
	cin>>N;
	N*=2;
	rep(i,N) cin>>a[i];
	sort(a,a+N);
	double ans = 0;
	rep(i,N) ans += a[i]*i/(N-1);
	printf("%.12f\n",ans);
}


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

int main() {
	int a, b;
	cin >> a >> b;
	int n[3];
	n[0] = a + b;
	n[1] = a - b;
	n[2] = a * b;
	sort(n, n+3);
	int ans = n[2];
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
n,a,b = map(int,input().split())
count = 0
aaa = [str(i) for i in range(1,n+1)]
for j in aaa:
    m = 0
    for k in j:
        m += int(k)
    if a <= m <= b:
        count += int(j)
        
print(count)

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

#define ed cout << "\n";
#define speed                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define ll long long
#define ffor(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(i, n) ffor(i, 0, n)
#define All(obj) (obj).begin(), (obj).end()
#define INF ((ll)1e9 + 7)
#define c(a) cout << a << "\n";
using namespace std;
const int N = 100005;

int main()
{
    speed;
    cout << fixed << setprecision(10);
    /*start*/
    int a, b, c;
    cin >> a >> b >> c;
    set<int> f;
    f.insert(a);
    f.insert(b);
    f.insert(c);
    if (f.size() == 2)
    {
        c("Yes");
    }
    else
        c("No");
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			int r = sc.nextInt();
			if (r == 0) {
				sc.close();
				break;
			}

			int n = sc.nextInt();

			int[] xl = new int[n];
			int[] xr = new int[n];
			int[] h = new int[n];
			for (int i = 0; i < n; i++) {
				xl[i] = sc.nextInt();
				xr[i] = sc.nextInt();
				h[i] = sc.nextInt();
			}

			int[] cover = new int[2 * r];
			for (int i = 0; i < n; i++) {
				int ll = Math.max(0, xl[i] + r);
				int rr = Math.min(r * 2, Math.max(0, xr[i] + r));

				for (int j = ll; j < rr; j++) {
					cover[j] = Math.max(cover[j], h[i]);
				}
			}

			double ans = 100000.0;
			for (int i = 0; i < cover.length; i++) {
				int xx = i - r > 0 ? i - r + 1 : r - i - 1;
				double t1 = cover[i] - r
						* Math.sin(Math.acos((double) Math.abs(r - i) / r));
				double t2 = cover[i] - r * Math.sin(Math.acos((double) xx / r));
				ans = Math.min(ans, Math.min(t1 + r, t2 + r));
			}

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

Measured memory_bytes: 26256
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = str(input())

#r<p,s<r,p<s
flag = []
alls = 0
for i in range(N) :
    if i < K :
       flag.append(0)
       if T[i]=="r" : 
          alls += P
       elif T[i]=="s" :  
          alls += R
       else :  
          alls += S
    elif T[i]!=T[i-K] or ( T[i]==T[i-K] and flag[i%K] == 1 ):
       flag[i%K] = 0
       if T[i]=="r" : 
          alls += P
       elif T[i]=="s" :  
          alls += R
       else :  
          alls += S
    elif T[i]==T[i-K]:
       flag[i%K] = 1

print( alls )

Measured memory_bytes: 3964
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll a,b,c;
    cin>>a>>b>>c;
    if((a+b+c)>=22)
        cout<<"bust"<<endl;
    else
        cout<<"win"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char s[6];
int main(){
scanf("%s",s);
 bool flag = true;
 for(int i =1 ; i < 4; i++){
 	if(s[i]==s[i-1]){
      flag = false;
      break ;
    }
 }
 cout << (flag?"Good":"Bad") << endl;
  
  return 0;
}


Measured memory_bytes: 256
S=list(input())
s=0
op_count=len(S)-1
for i in range(2**op_count) :
    op=[""]*op_count
    for j in range(op_count) :
        if (i>>j) & 1 :
            op[j]="+"
    
    formula=""
    for p,q in zip(S,op+["+"]) :
        formula+=(p+q)
    formula+="0"
    s+=eval(formula)
print(s)


Measured memory_bytes: 9016
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

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

	int sum = 0;
	for (int i = 0; i < n; i++) {
		int m;
		cin >> m;
		if (m>=k) {
			sum++;
		}
	}
	cout << sum << endl;
	return 0;
}


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

typedef long long ll;

typedef pair<int, int> p;

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

    int N;
    cin >> N;

    vector<int> f(N);
    vector<int> b(N);

    vector<vector<int> > x(N);

    for(int i = 0; i < N - 1; i++) {
        int a, c;
        cin >> a >> c;
        a--;
        c--;
        x[a].push_back(c);
        x[c].push_back(a);
    }

    vector<bool> fb(N, false);
    vector<bool> bb(N, false);

    stack<p> s;

    s.push(make_pair(0, 0));

    while(!s.empty()) {
        p q = s.top();
        s.pop();
        int pos = q.first;
        int l = q.second;
        if(fb[pos]) continue;
        fb[pos] = true;
        f[pos] = l;
        for(int i = 0; i < x[pos].size(); i++) {
            s.push(make_pair(x[pos][i], l + 1));
        }
    }

    s.push(make_pair(N - 1, 0));

    while(!s.empty()) {
        p q = s.top();
        s.pop();
        int pos = q.first;
        int l = q.second;
        if(bb[pos]) continue;
        bb[pos] = true;
        b[pos] = l;
        for(int i = 0; i < x[pos].size(); i++) {
            s.push(make_pair(x[pos][i], l + 1));
        }
    }

    int fc = 0;
    int bc = 0;

    for(int i = 0; i < N; i++) {
        if(f[i] > b[i]) bc++;
        else fc++;
    }

    cerr << fc << endl << bc << endl;

    if(fc > bc) {
        cout << "Fennec" << endl;
    } else {
        cout << "Snuke" << endl;
    }
}

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

// def
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
#define repeat(i, a, b) for (int i = (a); i < (b); i++)
#define revrepeat(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define revrep(i, n) for (int i = (n)-1; i >= 0; i--)
typedef long long ll;
typedef pair<ll, ll> P;
const int M = 1e9 + 7;
const int INF = 1e9;
const int MAX_V = 100 + 5;
const int MAX_N = 1e5 + 5;

// save memory
int MOD = 1e9 + 7;
long modpow(long m, long p) {
    if (p == 0) return 1;
    if (p % 2)
        return m * modpow(m, p - 1) % MOD;
    else {
        long res = modpow(m, p / 2);
        return res * res % MOD;
    }
}

int main() {
    int n, m;
    ll ans = 0;
    cin >> n >> m;
    priority_queue<int> que;
    rep(i, n) {
        ll temp;
        cin >> temp;
        que.push(temp);
    }
    rep(i, m) {
        ll t = que.top();
        que.pop();
        t /= 2;
        que.push(t);
    }
    while (!que.empty()) {
        ans += que.top();
        que.pop();
    }
    cout << ans << endl;
}


Measured memory_bytes: 892
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<time.h>
#include<tuple>
#include<set>
#include<map>
#include<cctype>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define vint vector<int> 
#define vvint vector<vint>
#define ct(a) cout<<a<<endl
#define tget(a,b) get<a>(b)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;
string a;

int main(void) {
	cin >> a;
	int n = a.length();
	int ans1 = -1, ans2 = -1;
	char mae = 'A';
	FOR(i, 0, n) {
		if (mae != a[i]) {
			ans1++;
			mae = a[i];
			}
	}
	mae = 'A';
	FOR(i, 0, n) {
		if (mae != a[n - i - 1]) {
			ans2++;
			mae = a[n - i - 1];
		}
	}
	ct(min(ans1, ans2));
	
	return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define RFOR(i,a,b) for(int i=(b-1); i>=(a); i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define pb push_back
using ll = long long;
using D = double;
using LD = long double;
using P = pair<ll, ll>;
const int mod = 1e9+7;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

struct UnionFind {
    vector<int> par;

    UnionFind(int sz) {
        par.assign(sz, -1);
    }

    bool merge(int x, int y) {
        x = root(x), y = root(y);
        if(x == y) return (false);
        if(par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return (true);
    }

    int root(int k) {
        if(par[k] < 0) return (k);
        return (par[k] = root(par[k]));
    }

    int size(int k) {
        return (-par[root(k)]);
    }

    bool same(int x, int y) {
        return root(x) == root(y);
    }
};

int main(){
    int n; cin >> n;
    UnionFind uf(200005);
    rep(i,n){
        int X, Y; cin >> X >> Y; X--; Y--;
        uf.merge(X, Y + 100000);
    }
    map<int, P> mp;
    rep(i,100000){
        mp[uf.root(i)].first++;
        mp[uf.root(i+100000)].second++;
    }
    ll ans = 0;
    for(auto val : mp){
        ans += val.second.first * val.second.second;
    }
    ans -= n;
    cout << ans << endl;
}


Measured memory_bytes: 13568
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>
using ll = long long;
using itn = int;
using namespace std;
int main(){
    int n,x;
    cin >> n >> x;
    int m[n];
    int l=1e9,sum=0,cnt=0;
    for(int i=0; i<n; i++){
        cin >> m[i];
        sum+=m[i];
        cnt++;
        if(m[i]<l) l=m[i];
    }
    cnt += (x-sum)/l;
    cout << cnt << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
#ifdef __LOCAL
#define debug(x) cerr << __LINE__ << ": " << #x << " = " << x << endl
#define debugArray(x, n)                           \
  cerr << __LINE__ << ": " << #x << " = {";        \
  for (long long hoge = 0; (hoge) < (n); ++(hoge)) \
    cerr << ((hoge) ? "," : "") << x[hoge];        \
  cerr << "}" << endl
#else
#define debug(x) (void(0))
#define debugArray(x, n) (void(0))
#endif

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  const long long INF = LLONG_MAX / 10;
  string s, t;
  cin >> s >> t;
  int N = s.length();
  long long to[N][26];
  fill(to[N - 1], to[N - 1] + 26, INF);
  for (int i = N - 2; i >= 0; i--) {
    for (int j = 0; j < 26; j++) to[i][j] = to[i + 1][j] + 1;
    to[i][s[i + 1] - 'a'] = 1;
  }
  for (int i = N - 1; i >= 0; i--) {
    for (int j = 0; j < 26; j++) to[i][j] = to[(i + 1) % N][j] + 1;
    to[i][s[(i + 1) % N] - 'a'] = 1;
  }
  long long ans = 0;
  long long cur = N - 1;
  for (int i = 0; i < (int)t.length(); i++) {
    debug(i);
    long long tmp = to[cur][t[i] - 'a'];
    if (tmp >= INF) {
      ans = -1;
      break;
    }
    ans += tmp;
    (cur += tmp) %= N;
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 24068
#include <bits/stdc++.h>
using namespace std;
struct iofix
{
   ios_base::Init i;
   iofix() {
      cin.sync_with_stdio(0);
      cin.tie(0);
      cout.sync_with_stdio(0);
      cout.tie(0);
      cout.precision(10);
      cout << fixed;
   }
} iofix;

void solve(){
   int64_t l ,r ,d; cin >> l >> r >> d;
   int c = 0 ;
   for (int i = l; i <=r;i++)
       if (i%d==0)
          c++;
   cout << c;
}

int main(){

   	solve();

   return 0;
}

Measured memory_bytes: 3608
s = input()
n = s[1::2]
o = s[::2]
cnt = 0
r = set(list("DRU"))
l = set(list("DLU"))
if set(o) | r == r: cnt+=1
if set(n) | l == l: cnt+=1
if cnt==2: print("Yes")
else: print("No")

Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#include<iomanip>
#include<cassert>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 50;
 
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;
}
using namespace std;

int k;
vector<ll>a;

bool C(ll mid){
    rep(i,k){
        mid-=(mid)%a[i];
    }
    if(mid<=2)return true;
    else return false;
}

bool C2(ll mid){
    rep(i,k){
        mid-=(mid)%a[i];
    }
    if(mid>=2)return true;
    else return false;
}

void solve(){
    cin>>k;
    a.resize(k);
    ll maxV=0;
    rep(i,k){
        cin>>a[i];
        chmax(maxV,a[i]);
    }
    ll l=2,r=INF;
    while(r-l>1){
        ll mid=(l+r)/2;
        if(C(mid))l=mid;
        else r=mid;
    }
    ll maxv=l;
    l=1,r=2+k*maxV;
    while(r-l>1){
        ll mid=(l+r)/2;
        if(C2(mid))r=mid;
        else l=mid;
    }
    if(maxv>=r)cout<<r<<" "<<maxv<<"\n";
    else cout<<-1<<"\n";
}
 
signed main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
	cout<<fixed<<setprecision(15);
	solve();
	return 0;
}


Measured memory_bytes: 1024
// clang-format

#include <bits/stdc++.h>
#define rep(i, n) for (lli i = 0; i < (n); i++)
#define rrep(i, n) for (lli i = (n)-1; i >= 0; i--)
using namespace std;

using lli = long long int;



void solve(long long n, long long m, long long P, std::vector<long long> A,
           std::vector<long long> B, std::vector<long long> C) {

  rep(i, m) B[i]--,A[i]--;
  rep(i, m)C[i] = P - C[i];
  vector<bool> visited(n);
  queue<int> que;
  que.push(n-1);
  while(!que.empty()){
    int cur = que.front();
    que.pop();
    if(visited[cur])continue;
    visited[cur] = true;
    //cout << cur << endl;
    rep(j, m) {
      if(B[j] == cur)
      que.push(A[j]);
    }
  }
  vector<lli> dist(n, 1e18);
  dist[0] = 0;
  rep(i, n){
    bool updated = false;
    rep(j, m) {
      if(dist[B[j]]>dist[A[j]] + C[j] && dist[A[j]] != 1e18){
        updated |= visited[B[j]];
        dist[B[j]] = min(dist[B[j]], dist[A[j]] + C[j]);
      }
    }
    if(!updated)break;
    if(i==n-1){
      cout << -1 << endl;
      return;
    }
  }
  cout << max(-dist[n-1], 0ll) <<endl;
}

int main() {
  int a;
  long long N;
  scanf("%lld", &N);
  long long M;
  scanf("%lld", &M);
  long long P;
  scanf("%lld", &P);
  std::vector<long long> A(M);
  std::vector<long long> B(M);
  std::vector<long long> C(M);
  for (int i = 0; i < M; i++) {
    scanf("%lld", &A[i]);
    scanf("%lld", &B[i]);
    scanf("%lld", &C[i]);
  }
  solve(N, M, P, std::move(A), std::move(B), std::move(C));
  return 0;
}


Measured memory_bytes: 384
def resolve():
    def dic_factorization(n):
        dic = {}  # 素数:指数
        i = 2
        while i * i <= n:
            while n % i == 0:
                n //= i
                if i in dic:
                    dic[i] += 1
                else:
                    dic[i] = 1
            i += 1
        if n > 1:
            dic[n] = 1
        return dic

    MOD = 10 ** 9 + 7
    N = int(input())
    exp = [0] * (N + 1)
    for i in range(2, N + 1):
        dic_prime = dic_factorization(i)
        for k, v in dic_prime.items():
            exp[k] += v

    ans = 1
    for i in range(2, N + 1):
        ans *= exp[i] + 1
        ans %= MOD

    print(ans)

if __name__ == "__main__":
    resolve()

Measured memory_bytes: 3064
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 C = sc.nextInt();
   int X = sc.nextInt();
   
   int ans =0;
   for(int i=0;i<=A;i++)
   {
     for(int k=0;k<=B;k++)
     {
       for(int j=0;j<=C;j++)
       {
         if(500*i+100*k+50*j==X) ans++;
       }
     }
   }
   
   System.out.println(ans);
 }
}

Measured memory_bytes: 21844
import java.util.*;
import java.util.Vector;
import java.math.*; 
public class Main {
     Scanner sc = new Scanner(System.in);
	
	
	void run(){ // kokonikaku
	 int  x=sc.nextInt();
	 int  y=sc.nextInt();
	 int  z=sc.nextInt();
	 int  k=sc.nextInt();
	 
	long[] a =new long[1010];
	long[] b =new long[1010];
	long[] c =new long[1010];
		
		for(int i=0;i<x;i++){
			a[i]=sc.nextLong();
			a[i]*=-1;
		}
		Arrays.sort(a,0,x);
		for(int i=0;i<x;i++){
			a[i]*=-1;
			
		//	System.out.println(a[i]);
		}
		
		for(int i=0;i<y;i++){
			b[i]=sc.nextLong();
			b[i]*=-1;
		}
		Arrays.sort(b,0,y);
		for(int i=0;i<y;i++){
			b[i]*=-1;
			
		//	System.out.println(a[i]);
		}
		
		for(int i=0;i<z;i++){
			c[i]=sc.nextLong();
			c[i]*=-1;
		}
		Arrays.sort(c,0,z);
		for(int i=0;i<z;i++){
			c[i]*=-1;
			
			//System.out.println(a[i]);
		}
		
		ArrayList<Long> ve=new ArrayList<Long>();
		for(int i=0;i<x;i++)for(int j=0;j<y;j++){
			ve.add(a[i]+b[j]);
		}
		Collections.sort(ve, Comparator.reverseOrder());
    //	System.out.println(ve.toString());
		
		//ArrayList<Long> ve2=new ArrayList<Long>();
		
		int siz=Math.min(k,x*y);
		
		ArrayList<Long> ve3=new ArrayList<Long>();
		
		for(int i=0;i<siz;i++)for(int j=0;j<z;j++){
			ve3.add(ve.get(i)+c[j]);
		}
		
		Collections.sort(ve3, Comparator.reverseOrder());
		
		for(int i=0;i<k;i++){
			System.out.println(ve3.get(i));
		}
		
		/*
		for(int i=0;i<x*y;i++){
			System.out.println(ve[i]);
		}
		*/
	}

	
	public static void main(String[] args) {
		new Main().run();
        
    }
}

Measured memory_bytes: 191604
# coding: utf-8
N, M = map(int, input().split())
A = list(map(int, input().split()))
total = sum(A)
cnt = 0
for i in range(N):
    if A[i] / total >= 1 / (4 * M):
        cnt += 1
print("Yes" if cnt >= M else "No")

Measured memory_bytes: 38384
from itertools import product

N, M = [int(x) for x in input().split()]

Ss = []
for i in range(M):
    Ss.append([int(x) for x in input().split()][1:])

Ps = [int(x) for x in input().split()]

c = 0
for onoff in product([0,1], repeat=N):
    d = 0
    for i, S in enumerate(Ss):
        t = sum(onoff[s-1] for s in S)
        if t % 2 == Ps[i]:
            d += 1
    if d == M:
        #print("*", onoff)
        c+=1
print(c)


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

int main() {
    ll  N;
    cin >> N;
    vector<pair<ll, ll>> m;
    for (ll i = 1; i * i <= N; i++) {
        if (N % i == 0) {
            ll aux = N / i;
            m.push_back(make_pair(i, aux));
        }
    }
    pair<ll, ll> ans;
    ll dif = 1000000000000000000000000;
    for (pair<ll, ll> p : m) {
        ll aux = abs(1 - p.first) + abs(1 - p.second);
        if (aux < dif) {
            ans = p;
            dif = aux;
        }
    }

    ll result = abs(1 - ans.first) + abs(1 - ans.second);
    cout << result << endl;

    return 0;
}



Measured memory_bytes: 384
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cmp(const void* x, const void* y) {
	return strcmp(x, y);
}

int N;
char S[271828][12];

int nyanCount;
int nyan[271828][2];

int max;
int maxCount;
int maxIndex[271828];

int mofu(const void* x, const void* y) {
	return strcmp(S[*(const int*)x], S[*(const int*)y]);
}

int main(void) {
	int i;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%11s", S[i]) != 1) return 1;
	}
	qsort(S, N, sizeof(*S), cmp);
	nyanCount = 1;
	nyan[0][0] = 0;
	nyan[0][1] = 1;
	for (i = 1; i < N; i++) {
		if (strcmp(S[i], S[nyan[nyanCount - 1][0]]) == 0) {
			nyan[nyanCount - 1][1]++;
		} else {
			nyan[nyanCount][0] = i;
			nyan[nyanCount][1] = 1;
			nyanCount++;
		}
	}
	max = 0;
	maxCount = 0;
	for (i = 0; i < nyanCount; i++) {
		if (nyan[i][1] > max) {
			max = nyan[i][1];
			maxIndex[0] = nyan[i][0];
			maxCount = 1;
		} else if (nyan[i][1] == max) {
			maxIndex[maxCount++] = nyan[i][0];
		}
	}
	qsort(maxIndex, maxCount, sizeof(*maxIndex), mofu);
	for (i = 0; i < maxCount; i++) {
		puts(S[maxIndex[i]]);
	}
	return 0;
}


Measured memory_bytes: 7912
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T> ostream& operator<<(ostream& s,const multiset<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double EPS=1e-10;
const double PI=acos(-1);

/*
1-indexed
verified by
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4490492#1
https://atcoder.jp/contests/arc033/submissions/11204957
*/
template<typename T>
struct BIT{
    vector<T> node;
    int n;
    BIT(int n) :n(n) { 
        node.resize(n + 1LL, 0);
    }
    T sum(int k) {
        T ret=0;
        for (;k>0;k-=(k & -k)) ret+=node[k];
        return ret;
    }	
    T sum(int a, int b){//[a,b)
        return sum(b)-sum(a);
    } 
    void add(int k, T x) {
        for(;k<=n;k+=(k & -k)) node[k]+=x;
    }
};

//Compress<ll> comp(a);みたいな感じで
template <class T>
struct Compress{
    int N;
    map<T,int> idx;
    vector<T> cmp;
    Compress(vector<T> v){
        for(auto& x:v) cmp.push_back(x);
        sort(cmp.begin(),cmp.end());
        cmp.erase(unique(cmp.begin(),cmp.end()),cmp.end());
        N=cmp.size();
        for(int i=0;i<N;i++) idx[cmp[i]]=i;
    }
    int id(T val){return idx[val];}//前→後
    T val(int id){return cmp[id];}//後→前
};

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    ll n,k;
    cin>>n>>k;
    vector<ll> a(n),sum(n+1,0);
    rep(i,n){
        cin>>a[i];
        sum[i+1]=sum[i]+a[i];
    }
    rep(i,n+1){
        sum[i]-=k*i;
    }
    Compress<ll> comp(sum);
    rep(i,n+1){
        sum[i]=comp.id(sum[i])+1;
    }
    BIT<ll> seg(n+1);
    ll ans=0;
    seg.add(sum[0],1);
    FOR(r,1,n+1){
        ans+=seg.sum(sum[r]);
        seg.add(sum[r],1);
    }
    cout<<ans<<endl;
}

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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << endl; exit(0); }
inline void no() { cout << "No" << endl; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); return a / gcd(a, b) * b; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { x = max(x, y); }
template <typename T> inline void amin(T &x, T y) { x = min(x, y); }
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

template <int mod>
struct ModInt {
  int x;
  ModInt(): x(0) {}
  ModInt(long long a) { x = a % mod; if (x < 0) x += mod; }
  ModInt &operator+=(ModInt that) { x = (x + that.x) % mod; return *this; }
  ModInt &operator-=(ModInt that) { x = (x + mod - that.x) % mod; return *this; }
  ModInt &operator*=(ModInt that) { x = (long long) x * that.x % mod; return *this; }
  ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
  ModInt inverse() {
    int a = x, b = mod, u = 1, v = 0;
    while (b) { int t = a / b; a -= t * b; u -= t * v; swap(a, b); swap(u, v); }
    return ModInt(u);
  }
  #define op(o, p) ModInt operator o(ModInt that) { return ModInt(*this) p that; }
    op(+, +=) op(-, -=) op(*, *=) op(/, /=)
  #undef op
  friend ostream& operator<<(ostream &os, ModInt m) { return os << m.x; }
};

using mint = ModInt<1000000007>;

void solve() {
  int n, k;
  cin >> n >> k;
  vi32 a(n);
  cin >> a;
  vi32 c(n), d(n);
  rep(i, n) rep(j, n) {
    if (i == j) continue;
    if (i < j && a[i] > a[j]) c[i]++;
    if (i > j && a[i] > a[j]) d[i]++;
  }
  mint ans = 0;
  rep(i, n) {
    ans += (mint) k * (k + 1) * c[i];
    ans += (mint) k * (k - 1) * d[i];
  }
  cout << ans / 2 << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
long long int A,B;
long long int C,D;
int gcd(int a,int b) {
	if(b==0)return a;
	return gcd(b,a%b);
}

int main() {
	//容斥模板 
	cin >> A >> B >> C >> D;
	long long int a1=B/C-(A-1)/C;//能被C整除的数 
	long long int a2=B/D-(A-1)/D;//能被D整除的数 
	long long int g=C*D/gcd(C,D);//求C,D的最大公约数以找出能被C和D整除的数 
	long long int a3=B/g-(A-1)/g;//能被C和D整除的数 
	cout << (B-A+1)-a1-a2+a3 << endl;//(B-A+1)是区间(A,B)的元素个数
									//+a3是加上 （减去的重复计算的数）
									//比如说6被减了两次,第一次是在a1,第二次是在a2 
//	cout << a1 << " " << a2 <<" " << a3;
	
	return 0;
}

Measured memory_bytes: 256
/*
  A - ABC/ARC
  Contest 054
  Rakesh Kumar --> 04/08/2020
 */

#include <bits/stdc++.h>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);

    int r = 0;
    std::cin >> r;
    std::cout << (r < 1200 ? "ABC" : "ARC") << std::endl;

    return 0;
}


Measured memory_bytes: 3612
## ABC 045 b
import sys

sa = list(input())
sb = list(input())
sc = list(input())

sa = sa[::-1]
sb = sb[::-1]
sc = sc[::-1]

f = sa.pop()
while(len(sa) != 0 or len(sb) != 0 or len(sc) != 0 ):
    if(f == 'a'):
        if (len(sa) == 0):
            print('A')
            sys.exit(0)
        else:
            f = sa.pop()

    elif(f == 'b'):
        if (len(sb) == 0):
            print('B')
            sys.exit(0)
        else:
            f = sb.pop()
    else:
        if (len(sc) == 0):
            print('C')
            sys.exit(0)
        else:
            f = sc.pop()


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

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

	for (int i = 1; i <= 50000;i++) {
		if ((int)((float)i*1.08) == n) { 
			cout << i;
			return 0;
		}
	}

	cout << ":(";


	return 0;
}

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

	int n;
	cin >> n;
	vector<int> V,C;

	rep(i,n) {
		int a;
		cin >> a;
		V.push_back(a);
	}
	rep(i,n) {
		int b;
		cin >> b;
		C.push_back(b);
	}

	int ans = 0;
	rep(i,n) {
		if (V[i]>C[i]) {
			ans += V[i] - C[i];
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#!/usr/bin/env ruby

require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.chomp.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

A, B = get_ints

if B % A == 0
  puts A + B
else
  puts B - A
end


Measured memory_bytes: 14308
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

#define int long long
#define endl "\n"

const long long INF = (long long)1e18;
const long long MOD = (long long)1e9 + 7; 

string yn(bool f){return f?"Yes":"No";}
string YN(bool f){return f?"YES":"NO";}



signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int n, A = 0, B = 1;
	int query, num;
	
	cin>>n;
	
	for(int i = 0; i < n; i++){
		cin>>query>>num;
		
		if(query == 2){
			A -= num;
		} else if(query == 1){
			A *= num;
			B *= num;
		} else if(query == 3){
			A += num;
		}
	}
	
	cout<<A<<" "<<B<<endl;
	return 0;
}


Measured memory_bytes: 3216
import sys
ans = [0]*26
str = sys.stdin.read()

for i in range(len(str)):
    code = ord(str[i])-ord("a")
    if 0 <= code <= 25:
        ans[code]+=1
    else:
        code = ord(str[i])-ord("A")
        if 0 <= code <= 25:
            ans[code]+=1

for i in range(26):
    print(chr(ord('a')+i), ":", ans[i])


Measured memory_bytes: 5568
#include <chrono>

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <time.h>
#include <random>
#include <string>
#include <cassert>
#include <vector>
#include <ostream>
#include <istream>
#include <stack>
#include <deque>
#include <queue>
#include <functional>

using namespace std;

#define int long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define pii pair<int, int>
#define ld long double

ostream& operator << (ostream &a, const vector<int> &b) {
    for (auto k : b) cout << k << " ";
    return a;
}

#ifdef LOCAL
    #define dbg(x) cout << #x << " : " << (x) << "\n";
    const int INF = 1e18;
//    const int mod = 2600000069;
//    const int p = 10;
//    const ld PI = 3.1415926535;
#else
    #define dbg(x)
    const int INF = 1e18;
//    const int mod = 2600000069;
//    const int p = 179;
//    const ld PI = 3.1415926535;
#endif

//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,sse3,sse4")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("fast-math")
//#pragma GCC target("avx2")
//#pragma GCC optimize("section-anchors")
//#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
//#pragma GCC optimize("vpt")
//#pragma GCC optimize("rename-registers")
//#pragma GCC optimize("move-loop-invariants")
//#pragma GCC optimize("unswitch-loops")
//#pragma GCC optimize("function-sections")
//#pragma GCC optimize("data-sections")

const int mod = 1e9 + 7;

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifdef LOCAL
    #else
//        freopen("capitals.in", "r", stdin);
//        freopen("capitals.out", "w", stdout);
    #endif
    string s;
    cin >> s;
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(2, 0));
    dp[0][0] = 1;
    dp[0][1] = 2;
    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] * 3;
        dp[i][1] = dp[i - 1][1];
        if (s[i] == '1') {
            dp[i][0] += dp[i - 1][1];
            dp[i][1] *= 2;
        }
        dp[i][0] %= mod;
        dp[i][1] %= mod;
    }
    cout << (dp[n - 1][0] + dp[n - 1][1]) % mod;
}
/*

*/


Measured memory_bytes: 5840
#include <bits/stdc++.h>
using namespace std;
#define int long long
const double eps = 1e-9;

int n,a;
vector<int>v;

int solve(int x)
{
	int r = 0;
	for(int a : v)
		r += (a - x)*(a - x);
		
	return r;
}

int32_t main()
{
	cin >> n;
	for(int i=0; i<n; i++)
	{
		cin >> a;
		v.push_back(a);
	}
	
	int mn = 1000000;
	for(int i=-500; i<=500; i++)
		if(solve(i) < mn)
			mn = solve(i);
			
	cout << mn << '\n';
}

Measured memory_bytes: 256
S = input()
LS = len(S)

ans = [-1, -1]
flg = False
if LS < 2:
    flg = False
elif LS == 2:
    flg = S[0] == S[1]
    if flg: ans = [1, 2]
else:  # LS > 2
    for i in range(len(S) - 2):
        p1 = S[i] == S[i + 1]
        p2 = S[i] == S[i + 2]
        p3 = S[i + 1] == S[i + 2]
        flg = p1 or p2 or p3
        if flg:
            ans = [i + 1, i + 1 + 2]
            break
print(*ans)


Measured memory_bytes: 3188
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
bi=[0]* N
children = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    bi[i]=b-1
    children[a-1].append(b-1)

queue = deque([0])
colors = [0] * N
maxColor = 0
while queue:
    node = queue.popleft()
    nodeColor = colors[node]
    color = 1
    for child in children[node]:
        if color == nodeColor: color += 1
        colors[child] = color
        queue.append(child)
        color += 1
    maxColor = max(maxColor, color-1)

print(maxColor)
for i in range(N-1):
    print(colors[bi[i]])

Measured memory_bytes: 21784