akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define INT(a) int((a)+1e-9)
#define INF 1e5


int main(){
	while(true){
		int apl,bpl;
		cin >> apl >> bpl;			if(!apl) return 0;
		int aps[apl]; int bps[bpl];
		REP(api,apl) cin>>aps[api];
		REP(bpi,bpl) cin>>bps[bpi];
		
		int sumap=0,sumbp=0;
		REP(api,apl) sumap+=aps[api];
		REP(bpi,bpl) sumbp+=bps[bpi];
		
		int reap=INF,rebp=INF;
		REP(api,apl){
			int ap=aps[api];
			REP(bpi,bpl){
				int bp=bps[bpi];
				if(sumap-ap+bp==sumbp-bp+ap){
					if(reap+rebp>ap+bp){
						reap=ap;rebp=bp;
					}
				}
			}
		}

		if(reap==INF) cout<<"-1"<<endl;
		else cout<<reap<<" "<<rebp<<endl;
	}
}

Measured memory_bytes: 1160
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String a = scan.next();
		String b = scan.next();
		String c = scan.next();
		if (a.charAt(a.length() - 1) == b.charAt(0) && b.charAt(b.length() - 1) == c.charAt(0)) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
}


Measured memory_bytes: 20948
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>

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

int iin() {
    int i;
    scanf("%d", &i);
    return i;
}

long long llin() {
    long long i;
    scanf("%lld", &i);
    return i;
}

double din() {
    double i;
    scanf("%lf", &i);
    return i;
}

char cin() {
    char c;
    scanf("%c", &c);
    return c;
}

void stin(char *s) {
    scanf("%s", s);
}

void iout(int i) {
    printf("%d\n", i);
}

void llout(long long i) {
    printf("%lld\n", i);
}

void dout(double i) {
    printf("%lf\n", i);
}

void cout(char c) {
    printf("%c\n", c);
}

void stout(char *s) {
    printf("%s\n", s);
}

int main() {
    int a = iin(), b = iin();
    printf("%d %d\n", a * b, 2 * (a + b));
    return 0;
}



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

using namespace std;

int main()
{
	int n,xw;
	cin >> n >> xw;
	vector<int> w(n),v(n);
	for(int i=0;i<n;i++)
		cin >> w[i] >> v[i];
	
	vector<vector<int> > dp(n,vector<int>(100005,1000000009));
	for(int i=0;i<n;i++)
		dp[i][0]=0;
	for(int i=0;i<100005;i++)
		if(i==v[0])
			dp[0][i]=w[0];
	for(int i=1;i<n;i++)
	{
		for(int j=0;j<100005;j++)
		{
			dp[i][j]=dp[i-1][j];
			if(j>=v[i])dp[i][j]=min(dp[i][j],dp[i-1][j-v[i]]+w[i]);
		}
	}

	int ans=0;
	for(int i=100004;i>=0;i--)
	{
		if(dp[n-1][i]<=xw)
		{
			ans=i;
			break;
		}
	}

	cout << ans << endl;
}

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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define ALL(v) (v).begin(), (v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x, n) bitset<n>(x)
#define PI 3.14159265358979323846

typedef long long ll;
typedef pair< int, int > P;
typedef pair< int, P > PP;

int n, m, q;
int len[600][600];

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

    cin >> n >> m >> q;
    REP(i, m) {
        int l, r;
        cin >> l >> r;
        len[r - l][l]++;
    }
    REP(i, n) {
        REP(j, n + 1) {
            len[i][j + 1] += len[i][j];
        }
    }
    REP(i, q) {
        int p, q;
        cin >> p >> q;
        int ans = 0;
        REP(j, q - p + 1) {
            ans += (len[j][q - j] - len[j][p - 1]);
        }
        cout << ans << endl;
    }

    return 0;
}



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

int main()
{
	ios::sync_with_stdio(false);
	
	int n,t,a[100010];
	cin>>n>>t;
	
	for(int i=0;i<n;i++)
		cin>>a[i];
	
	int p[100010]={},mi=1<<30;
	
	for(int i=0;i<n;i++)
	{
		mi=min(mi,a[i]);
		p[i]=a[i]-mi;
	}
	
	sort(p,p+n);
	reverse(p,p+n);
	
	int cnt=0;
	
	for(int i=0;i<n&&p[i]==p[0];i++,cnt++);
		cout<<cnt<<endl;
	
	return 0;
}

Measured memory_bytes: 1024
n,m = map(int,input().split())
lst = [1]*n
red_lst = [False]*n
red_lst[0] = True

xx = []
yy = []
for _ in range(m):
    a,b = map(int,input().split())
    xx.append(a-1)
    yy.append(b-1)

for i in range(m):
    x,y = xx[i], yy[i]
    if red_lst[x]==True and red_lst[y]==False:
        red_lst[y]=True
    if lst[x]==1 and red_lst[x]:
        red_lst[x] = False
    lst[x] -= 1
    lst[y] += 1

print(red_lst.count(True))

Measured memory_bytes: 12540
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	string s;
	cin >> s;
	stack< char > st;
	st.push('M');
	for(int i = 0 ; i < s.size() ; i++){
		if(s[i]=='T' && st.top()=='S')
			st.pop();
		else
			st.push(s[i]);
	}
	int cnt = 0;
	while(!st.empty()){
		cnt++;
		st.pop();
	}
	cout << cnt - 1 << endl;
	return 0;
}

Measured memory_bytes: 644
import java.util.LinkedList;
import java.util.Scanner;

public class Main {

	public static final int MAX_TIME = 12;
	
	public static final double EPS = 1e-10;
	
	public static double dfs(final int K, int day, double r, double l, final double PP, final double P, final double E, final double T){	
		if(T - E > l){
			return 0;
		}
		
		if(T + E < r){
			return 0;
		}
		
		final double H = (r + l) / 2;
		
		//System.out.println(day + " " + r + " " + l + " " + PP + " " + H);
		
		if(day >= K){
			if(Math.abs(T - H) <= E){
				return PP;
			}else{
				return 0;
			}
		}
		
		double ret = 0;
		
		if(H >= T){
			ret += dfs(K, day + 1, r, H, PP * (1.0 - P), P, E, T);
			ret += dfs(K, day + 1, H, l, PP * P, P, E, T);
		}else{
			ret += dfs(K, day + 1, H, l, PP * (1.0 - P), P, E, T);
			ret += dfs(K, day + 1, r, H, PP * P, P, E, T);
		}
		
		return ret;
	}

	public static void main(String[] args) {

		final Scanner sc = new Scanner(System.in);

		final int K = sc.nextInt();
		final int R = sc.nextInt();
		final int L = sc.nextInt();
		
		final double P = sc.nextDouble();
		final double E = sc.nextDouble();
		final double T = sc.nextDouble();
		
		System.out.printf("%.6f\n", dfs(K, 0, R, L, 1, P, E, T));
		
	}

}

Measured memory_bytes: 21700
using System;
using System.Collections.Generic;

namespace AOJ.Volume0
{
    class Program0013
    {
        static void Main(string[] args)
        {
            string line;
            Queue<string> operatingQueue = new Queue<string>();
            Stack<string> trainStack = new Stack<string>();

            while((line = Console.ReadLine()) != null)
            {
                operatingQueue.Enqueue(line);
            }

            foreach (var op in operatingQueue)
            {
                if (op == "0")
                {
                    Console.WriteLine(trainStack.Pop());
                }
                else
                {
                    trainStack.Push(op);
                }
            }
        }
    }
}

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

#define rep(i,N) for(int i=0;i<N;i++)
#define rep2(i,N) for(int i=1;i<=N;i++)
using namespace std;
long long  INF=1e18;
long long mod=1e9+7;

/*基本方針

各桁について(s[i]-'0')*10^iで各桁のmod(P)で累積和をとる。
詳しくは解説とメモ

*/

int main(){

    int n,p;
    cin>>n>>p;
    string s;
    cin>>s;

    int res[n+1];

    for(int i=0;i<n;i++){
        res[i]=int(s[n-1-i]-'0')%p;
        //cout<<res[i];
    }
    //cout<<endl;
    
    int sum[n+1];
    sum[0]=0;
    int ten=1;
    rep2(i,n){
        sum[i]=((res[i-1]*ten)%p+sum[i-1]);
        ten*=10;
        ten%=p;
    }
    rep(i,n+1){
        
        sum[i]%=p;
        //cout<<sum[i]<<" ";
    }
    //cout<<endl;
    map<long long,long long >mp;

    if(p!=2 && p!=5){

    
    rep(i,n+1){
        if(mp.find(sum[i])==mp.end()){
            mp.emplace(make_pair(sum[i],1));
        }
        else{
            mp[sum[i]]++;
        }
    }
    auto iter=mp.begin();
    long long ans=0;
    while(iter!=mp.end()){
        long long tmp=(iter->second*(iter->second-1))/2;
        ans+=(iter->second*(iter->second-1))/2;
        //cout<<iter->first<<" "<<iter->second<<" "<<tmp<<endl;;
        iter++;
    }
    //cout<<endl;
    cout<<ans<<endl;
    }



    else{
        long long ans=0;
        rep(i,n+1){
            if(res[i]==0){
                ans+=n-(i);
            }
        }
        cout<<ans<<endl;
    }
    return 0;

}
/*
20 9997
33883322005544116655

*/


Measured memory_bytes: 2564
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long ul;
// for文短縮類
#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPD(i, n) for (ll i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i <= (ll)(b); i++)
#define FORD(i, a, b) for (ll i = a; i >= (ll)(b); i--)
// iteratorのbeginとendをまとめて渡す
#define ALL(x) (x).begin(), (x).end()
//略
#define PB push_back  // vectorヘの挿入
#define MP make_pair  // pairのコンストラクタ
#define F first       // pairの一つ目の要素
#define S second      // pairの二つ目の要素
//出力
#define COUT(x) cout << (x) << endl
#define SCOUT(x) cout << (x) << " "
#define ENDL cout << endl
/************ Combination wtih MOD ************
const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
// preprocess for some tables
void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++) {
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}
// combination
long long COM(int n, int k) {
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
*******************************************************/
/********** UnionFind ***************
struct UnionFInd {
vector<ll> par;
UnionFInd(ll N) : par(N) {
for (ll i = 0; i < N; i++) {
par[i] = i;
}
}
ll root(ll x) {
if (par[x] == x) return x;
return par[x] = root(par[x]);
}
void unite(ll x, ll y) {
ll rx = root(x);
ll ry = root(y);
if (rx == ry) return;
par[rx] = par[ry];
}
bool same(ll x, ll y) {
ll rx = root(x);
ll ry = root(y);
return rx == ry;
}
};
*************************************/
int main(int argc, char *argv[]) {
  // input高速化。cinとcoutの結合解除。scanfとprintfは使えない。
  cin.tie(0);
  ios_base::sync_with_stdio(0);

  ll n;
  cin >> n;

  map<ll, ll> m;

  for (int x = 1; x < pow(10, 2) + 1; x++) {
    for (int y = 1; y < pow(10, 2) + 1; y++) {
      for (int z = 1; z < pow(10, 2) + 1; z++) {
          ll tmp = pow(x, 2) + pow(y, 2) + pow(z, 2) + x * y + y * z + z * x;
          auto it = m.find(tmp);
          if (it != m.end()){
              it->second +=1;
          }else{
              m.insert(make_pair(tmp, 1));
          }
      }
    }
  }

  for (int i = 1; i < n + 1;i ++){
      auto it = m.find(i);
      if(it == m.end()){
          cout << 0 << endl;
      }else{
          cout << it->second << endl;
      }
  }
}

Measured memory_bytes: 5992
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100 + 10;

int main() {
    char a[maxn], b[maxn], c[maxn];

    scanf("%s%s%s", a, b, c);

    int lena = strlen(a);
    int lenb = strlen(b);

    puts((a[lena-1] == b[0]) && (b[lenb-1] == c[0]) ? "YES" : "NO");
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)

ll mod = 1e9 + 7;



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

  ll n, p;
  cin >> n >> p;

  ll ans = 1, a = 2, rec = 0;

  vector<ll> pn, sn;

  ll tmp = p;

  while(tmp >= a * a){
    if(p % a == 0){
      rec++;
      p /= a;
    }
    else{
      if(rec){
        pn.pb(a);
        sn.pb(rec);
      }
      if(a == 2) a++;
      else a += 2;
      rec = 0;
    }
  }

  pn.pb(p);
  sn.pb(1);

  REP(i, pn.size()){
    ll res = sn[i] / n;
    REP(j, res) ans *= pn[i];
  }

  /*
  cout << pn.size() << endl;

  REP(i, pn.size()){
    cout << pn[i] << " " << sn[i] << endl;
  }
  */

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define x first
#define y second
#define pii pair<int , int>
#define mp make_pair
#define pb push_back
#define sz(a) (int)(a.size())
const int INF = 1000 * 1000 * 1000 + 7;
const ll LINF = INF * (ll)INF;
const int mod = INF;
int mult(int a , int b)
{
	return a * (ll)b % mod;
}
int add(int a , int b)
{
	return a + b >= mod ? a + b - mod : a + b;
}
int sub(int a , int b)
{
	return a - b < 0 ? a - b + mod : a - b;
	
}
int fact[2000005];
int inv[2000005];

int modPow(int a , int step)
{
	int ans = 1;
	while(step)
	{
		if(step & 1)
			ans = mult(ans , a);
		a = mult(a , a);
		step >>= 1;
	}
	return ans;
}
int C(int n , int k)
{
	return mult(fact[n] , mult(inv[k] , inv[n - k]));
}
int f(int r , int c)
{
	int ans = 0;
	for(int i = 0; i <= r; i++)
	{
		ans = add(ans , C(i + 1 + c , c));
	}
	return ans;
}
int main()
{
	fact[0] = inv[0] = 1;
	for(int i = 1; i <= 2000001; i++)
	{
		fact[i] = mult(fact[i - 1] , i);
		inv[i] = modPow(fact[i] , mod - 2);
	}
	int r1 , r2 , c1 , c2;
	cin >> r1 >> c1 >> r2 >> c2;
	int ans = add(f(r2 , c2) , sub(sub(f(r1 - 1, c1 - 1) , f(r2 , c1 - 1)) , f(r1 - 1 , c2)));
	cout << ans << endl;
	
}


Measured memory_bytes: 15872
#define _GLIBCXX_DEBUG
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
using namespace std;
typedef long long ll;
#define ALL(v) (v).begin(), (v).end()

const int mod = 1e9+7;

int main() {
		int N, M;
		cin >> N >> M;
		vector<bool> a(N+1, true);
		for (int i = 0; i < M; i++) {
				int t;
				cin >> t;
				a[t] = false;
		}

		vector<int> dp(N+1, 0);
		dp[0] = 1;
		if (a[1]) dp[1] = 1;

		for (int i = 2; i <= N; i++) {
				if (a[i]) {
						dp[i] = dp[i-1] + dp[i-2];
						dp[i] %= mod;
				}
		}

		cout << dp[N] << endl;
		return 0;
}


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

const int N = 202000;

pair<int, int> max(const pair<int, int> &a, const pair<int, int> &b) {
  return {max(a.first, b.first), max(a.second, b.second)};
}

pair<int, int> T[N << 2];
int n, a[N], f[2], s[N], H[2], C[2];
string ans;

void Modify(int o, int l, int r, int x, pair<int, int> y) {
  if(l == r)
    return (void)(T[o] = y);
  int mid = l + r >> 1;
  if(x <= mid) Modify(o << 1, l, mid, x, y);
  else Modify(o << 1 | 1, mid + 1, r, x, y);
  T[o] = max(T[o << 1], T[o << 1 | 1]);
}

pair<int, int> Query(int o, int l, int r, int x) {
  if(x > n) return {0, 0};
  if(x <= l)
    return T[o];
  int mid = l + r >> 1;
  pair<int, int> Ans = Query(o << 1 | 1, mid + 1, r, x);
  if(x <= mid) Ans = max(Ans, Query(o << 1, l, mid, x));
  return Ans;
}

bool Check(int x, int val) {
  static int tmp[2];
  tie(tmp[0], tmp[1]) = Query(1, 1, n, a[x] + 1);
  return tmp[val & 1] >= val && val >= 0;
}

int main(void) {
  scanf("%d", &n);
  for(int i = 1, x, mx = 0; i <= n; i++) {
    scanf("%d", &x);
    s[i] = (mx = max(mx, a[i] = x)) == x;
  }
  for(int i = n; i; i--) {
    static int f[2];
    int val = s[i] + 1, x, y;
    s[i] += s[i + 1];
    tie(x, y) = Query(1, 1, n, a[i] + 1);
    f[0] = f[1] = 0;
    f[x + val & 1] = max(f[x + val & 1], x + val);
    f[y + val & 1] = max(f[y + val & 1], y + val);
    Modify(1, 1, n, a[i], {f[0], f[1]});
  }
  
  if(!Check(0, s[1]))
    return puts("-1"), 0;
  
  for(int i = 1; i <= n; i++) {
    int x = a[i] > a[H[0]] ? i : H[0];
    int y = C[0] + (i == x);
    Modify(1, 1, n, a[i], {0, 0});
    if(Check(x, C[1] - y + s[i + 1]) || Check(H[1], y - C[1] + s[i + 1]))
      H[0] = x, C[0] = y, ans += '0';
    else
      H[1] = a[i] > a[H[1]] ? i : H[1], C[1] += i == H[1], ans += '1';
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 6916
#include <bits/stdc++.h>
using namespace std;using ll=long long;using uint=unsigned int;using pii=pair<int,int>;using pll=pair<ll,ll>;using ull = unsigned long long;using ld=long double;template<typename T>void _(const char*s,T h){cerr<<s<<" = "<<h<<"\n";}template<typename T,typename...Ts>void _(const char*s,T h,Ts...t){int b=0;while(((b+=*s=='(')-=*s==')')!=0||*s!=',')cerr<<*s++;cerr<<" = "<<h<<",";_(s+1,t...);}// break continue pop_back 998244353
#define int ll
#define pii pll
#define f first
#define s second
#define pb emplace_back
#define forn(i,n) for(int i=0;i<(n);++i)
#define sz(a)((int)(a).size())
#define sqr(x) ((x)*(x))
struct init{init(){cin.tie(0);iostream::sync_with_stdio(0);cout<<fixed<<setprecision(10);cerr<<fixed<<setprecision(5);}~init(){
#ifdef LOCAL
#define dbg(...) _(#__VA_ARGS__,__VA_ARGS__)
cerr<<"Time elapsed: "<<(double)clock()/CLOCKS_PER_SEC<<"s.\n";
#else
#define dbg(...) 
#endif
}}init;template<typename T,typename U>void upx(T&x,U y){if(x<y)x=y;}template<typename T,typename U>void upn(T&x,U y){if(x>y)x=y;}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());const int D=4,dx[]={+1,0,-1,0},dy[]={0,+1,0,-1};

const int N=1<<17;
int x[N];
int y[N];
void f(int n,int b){
    int p=0,q=(1<<n)-1,u=0;
    while(p<q){
        if(x[q]==b){
            while(p<=q)y[u++]=x[p++];
            break;
        }
        y[u++]=x[p++];
        y[u++]=x[q--];
        y[u++]=x[q--];
        y[u++]=x[p++];
    }
    forn(i,1<<n)x[i]=y[i];
}
int32_t main(){
    int n,a,b;
    cin>>n>>a>>b;
    if(__builtin_popcount(a^b)%2==0){
        cout<<"NO\n";
        return 0;
    }
    forn(i,1<<n)x[i]=i^(i>>1);
    b^=a;
    while(x[(1<<n)-1]!=b)f(n,b);
    cout<<"YES\n";
    forn(i,1<<n)cout<<(x[i]^a)<<' ';
    cout<<'\n';
    return 0;
}


Measured memory_bytes: 5616
using System;
using System.Linq;

class Aoj
{
  static void Main()
  {
    for(int i=1;i < 10;i++){
      for(int j=1;j < 10;j++){
        Console.WriteLine("{0}x{1}={2}",i,j,i*j);
      }
    }
  }
}

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

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858    (129)
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize    (130)
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division    (133)
const int mod = 1000000007;

struct mint {
  ll x;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619       (133)
struct combination {//nCkを求めている(二項係数を計算する関数)
  vector<mint> fact, ifact;//階乗と階乗の逆元
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);//これがないと落ちる(式が真であることを表明する)
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();//逆元(nCk=(n+k)!/(n)!(k)!)
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;//これで階乗の逆元が求まっているらしい
  }
  mint operator()(int n, int k) {//nCk=n!/k!(n-K)!のmod版
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

int main() {
  int N,M,K;
  cin >> N >> M >> K;
  combination ans = combination(N*M-2);
  mint co=ans(N*M-2,K-2);
  ll n=(ll)N,m=(ll)M;
  ll ans1=0ll;
  ll MOD = (ll)mod;
  for(ll i=0ll;i<n;i++) {ans1+=((i*(n-i))%MOD * (m*m)%MOD)%MOD;ans1=ans1%MOD;}
  for(ll i=0ll;i<m;i++) {ans1+=((i*(m-i))%MOD * (n*n)%MOD)%MOD;ans1=ans1%MOD;}
  mint ANS(ans1);
  ANS *= co;
  cout << ANS << endl;
  return 0;
}

Measured memory_bytes: 3328
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <string>
#include <numeric>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define rep(i, a, N) for(int i = a; i < N; i++)

int main() {
    int H, W, h, w;
    cin >> H >> W;
    cin >> h >> w;
    cout << H * W - h * W - (H - h) * w << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            int count = map.getOrDefault(a, 0);
            map.put(a, ++count);
        }
        
        int count = 0;
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            if (e.getValue() % 2 !=0) {
                count++;
            }
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 62748
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}

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

  string A, B ; cin >> A >> B ;
  if(A==B) cout << "H"  << endl;
  else cout << "D" << endl;

  //cout << fixed << setprecision(16) << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main() {
	char X,Y;
	cin >> X;
	cin >> Y;
	map<char,int> letr;
	if (X > Y) {
		cout << ">" << endl;
	}
	else if (X < Y) cout << "<" << endl;
	else cout << "=" << endl;

	return 0;
}

Measured memory_bytes: 3560
#include<iostream>
#include <climits>
#include <vector>
using namespace std;

// int Frog2(vector<int> input, int n, int k){
// 	if(n <= 0){
// 		return 0;
// 	}
// 	int ans = INT_MAX;
// 	for(int i = 1; i <= k && n-i >= 0; i++){
// 		int temp = abs(input[n] - input[n-i]) + Frog2(input, n-i, k);
// 		ans = min(ans, temp);
// 	}
// 	return ans;
// }

int Frog2BottomUp(vector<int> input, int n, int k){
	vector<int> dp(n);
	dp[0] = 0;
	for(int i = 1; i < n; i++){
		dp[i] = INT_MAX;
		for(int j = i-1; j >= 0 && (i-j) <= k; j--){
			dp[i] = min(dp[i], abs(input[i] - input[j]) + dp[j]);
		}
	}
	return dp[n-1];
}




int main(){



	int n, k;
	cin>>n>>k;
	vector<int> input(n);
	for(int i = 0; i < n; i++){
		cin>>input[i];
	}
	// cout<<Frog2(input, n-1, k)<<endl;
	cout<<Frog2BottomUp(input, n, k);

	return 0;
}

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

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef long double LD;
typedef pair<LD, LD> PLDLD;

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

const double eps=1e-5;
const int INF=1e9;

int main()
{
	int n;
	cin>>n;
	vector<string> s(n);
	vector<int> cnt(26,INF);
	REP(i,n)
	{
		cin>>s[i];
		vector<int> c(26);
		REP(j,s[i].size())
		{
			c[s[i][j]-'a']++;
		}
		REP(j,26)
			cnt[j]=min(cnt[j], c[j]);
	}
	REP(i,26)
	{
		REP(j,cnt[i])
		{
			cout<<(char)(i+'a');
		}
	}
	cout<<endl;
}



Measured memory_bytes: 256
import java.io.*;
import java.util.*;
public class Main{
	public static void main(String[] args) throws Exception{
		MScanner sc=new MScanner(System.in);
		PrintWriter pw=new PrintWriter(System.out);
		char[]in=sc.nextLine().toCharArray();
		boolean yes=in[2]==in[3] && in[4]==in[5];
		pw.println(yes?"Yes":"No");
		
		pw.flush();
	}
	static class MScanner {
		StringTokenizer st;
		BufferedReader br;
		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}
 
		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int[] intArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public long[] longArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public int[] intSortedArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		public long[] longSortedArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		static void shuffle(int[]in) {
			for(int i=0;i<in.length;i++) {
				int idx=(int)(Math.random()*in.length);
				int tmp=in[i];
				in[i]=in[idx];
				in[idx]=tmp;
			}
		}
		static void shuffle(long[]in) {
			for(int i=0;i<in.length;i++) {
				int idx=(int)(Math.random()*in.length);
				long tmp=in[i];
				in[i]=in[idx];
				in[idx]=tmp;
			}
		}
		public Integer[] IntegerArr(int n) throws IOException {
	        Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public Long[] LongArr(int n) throws IOException {
	        Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public String nextLine() throws IOException {
			return br.readLine();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public char nextChar() throws IOException {
			return next().charAt(0);
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
 
		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
	static void addX(int[]in,int x) {
		for(int i=0;i<in.length;i++)in[i]+=x;
	}
	static void addX(long[]in,int x) {
		for(int i=0;i<in.length;i++)in[i]+=x;
	}
}

Measured memory_bytes: 22996
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

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

const ll mod = 1e9 + 7;
const int INF32 = 1<<30;
const ll INF64 = 1LL<<60;
const ld pi = 3.141592653589793;

void solve(){
     int n;cin >> n;
     vector<ll>a(n);
     ll money = 1000;
     for(int i = 0;i<n;i++) cin >> a[i];
            vector<ll>temp;
            ll now = a[0];
        for(int j = 0;j<n;j++){
            if(a[j]>now){
               temp.push_back(now);
               temp.push_back(a[j]);
               now = a[j];
            }
            else if(a[j]<now){
                now = a[j];
            }
        }
        int t = temp.size();
        //for(int i = 0;i<t;i++) cout << temp[i]<<' ';
        for(int i = 0;i<t-1;i=i+2){
                ll hi = money/temp[i];
            money = hi*temp[i+1]+money%temp[i];
        }
        cout << money;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Measured memory_bytes: 3648
fn get_input() -> String {
    let mut word = String::new();
    std::io::stdin().read_line(&mut word).unwrap();
    word.trim().to_owned()
}

fn main() {
    let line = get_input();
    let mut split = line.split_whitespace();
    let a:i64 = split.next().unwrap().parse().unwrap();
    let p:i64 = split.next().unwrap().parse().unwrap();

    let ans = ((a * 3) + p) / 2;
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <atcoder/all>

// g++-10 f.cpp -std=c++17 -I .

using ll = long long int;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = 998244353ll;

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

ll cnt[100100],fc[100100]={1ll},nv[100100]={1ll},calc[55555]={1ll};
std::vector<ll> u[400400];

ll c(int n, int k){
	ll ret = fc[n];
	mul_mod(ret,nv[k]);
	mul_mod(ret,nv[n-k]);
	return ret;
}

void solve(int i=0, int l=0, int r=100000){
	int j;
	if(r-l>1){
		solve(i*2+1,l,(l+r)/2);
		solve(i*2+2,(l+r)/2,r);
		u[i] = atcoder::convolution<MOD>(u[i*2+1],u[i*2+2]);
	}else{
		for(j=0; j<=cnt[l]; j+=2){
			u[i].push_back(c(cnt[l],j)*calc[(j>>1)]%MOD);
		}
	}
}

int main(void){
	int n,i,m,j,t,h;
	ll ans=0ll;
	scanf("%d",&n);
	m = n*2;
	for(i=1; i<=100000; ++i){
		fc[i] = fc[i-1]*i%MOD;
		nv[i] = atcoder::inv_mod(fc[i],MOD);
	}
	for(i=1; i<=n; ++i){
		calc[i] = calc[i-1]*(i*2-1)%MOD;
	}
	for(i=0; i<m; ++i){
		scanf("%d",&h); --h;
		++cnt[h];
		if(cnt[h]>n){
			std::cout << 0 << std::endl;
			return 0;
		}
	}
	solve();
	std::reverse(calc,calc+n+1);
	for(i=0; i<u[0].l_ength(); ++i){
		// std::cout << calc[i] << " " << v[i] << std::endl;
		if(i&1){
			add_mod(ans,MOD-(calc[i]*u[0][i])%MOD);
		}else{
			add_mod(ans,calc[i]*u[0][i]%MOD);
		}
	}
	printf("%lld\n",ans);
	return 0;
}


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

main() {
    int N; cin >> N; bool can =true;
    string S[N]; map<string,int>m;
    rep(i,N){
        cin >> S[i]; m[S[i]]++;
    }
    rep(i,N-1){
        if(S[i][S[i].size()-1]!=S[i+1][0])
        can = false;
    }
    for(auto p:m){
        if(p.second>1) {can =false; break;}
    }
    if(can) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
void main() {
	auto N = ri;
	auto S = rs.to!(dchar[]);
	const ulong MOD = 1000000007;
	writeln(S.sort().group.map!(i => i[1] + 1).reduce!((i, j) => i * j % MOD) - 1);
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

Measured memory_bytes: 2684
import java.io.BufferedReader;
import java.io.InputStreamReader;

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

	int values[];
	int inputedDominoCount;
	int maxDominoCount;
	int maxValue;
	int minValue;
	boolean isExistDomino[][];
	boolean isConnected[];

	public void dominoesArrangement(){
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = new String();

		try{
			while((str = br.readLine()) != null){
				// 最初はドミノの数が入力される
				maxDominoCount = Integer.parseInt(str);

				// 初期化
				values = new int[7];
				inputedDominoCount = 0;
				isExistDomino = new boolean[7][7];
				isConnected = new boolean[7];

				while(inputedDominoCount < maxDominoCount){
					try{
						str = br.readLine();
					}catch(Exception e){}
					parseDomino(str);
					//System.out.println("inputedDominoCount: " + inputedDominoCount);
				}
				//printArray(values);
				//printArray(isExistDomino);


				// 最小値を求める
				for(minValue = 0; minValue < values.length; minValue++){
					if(values[minValue] != 0) break;
				}
				//System.out.println("最小値:" + minValue);

				// ノードの偶奇チェック
				// ついでに最小値も求める
				int oddCount = 0;
				for(int i = minValue; i < values.length; i++){
					if(values[i] % 2 == 1) oddCount++;
				}
				// 奇数のノードが2より多かったらまず無理
				if(oddCount > 2){
					System.out.println("No");
					continue;
				}

				// 最小値から深さ優先探索
				serch(minValue);
				//printArray(isConnected);

				// 行きたいノードがちゃんと全部接続されているか
				boolean noFlag = false;
				for(int i = minValue; i < values.length; i++){
					if(values[i] != 0){
						//System.out.println(i + ": 値が0でない");
						if(!isConnected[i]){
							noFlag = true;
							break;
						}
					}
				}
				if(noFlag){
					System.out.println("No");
					continue;
				}

				System.out.println("Yes");
			}
		}catch(Exception e){
			//System.err.println(e);
		}
	}

	void parseDomino(String inputStr){
		for(int i = 0; i < inputStr.length(); i++){
			int counter = 0;
			if(inputStr.charAt(i) == ' '){
				// 空白はスルー
			}else{
				int x = Integer.parseInt("" + inputStr.charAt(i));
				int y = Integer.parseInt("" + inputStr.charAt(i+1));
				i++;
				values[x]++;
				values[y]++;
				isExistDomino[x][y] = true;
				isExistDomino[y][x] = true;
				inputedDominoCount++;
			}
		}
	}

	void printArray(int[] array){
		for(int i = 0; i < array.length; i++){
			System.out.println(i + ": " + array[i]);
		}
	}

	void printArray(boolean[] array){
		for(int i = 0; i < array.length; i++){
			System.out.println(i + ": " + array[i]);
		}
	}

	void printArray(boolean[][] array){
		for(int i = 0; i < array.length; i++){
			for(int j = 0; j < array[i].length; j++){
				System.out.print(array[i][j] + "\t");
			}
			System.out.println();
		}
	}

	void serch(int n){
		if(isConnected[n]) return;
		// System.out.println(n + "を探索");
		isConnected[n] = true;
		for(int i = 0; i <= 6; i++){
			if(i == n) continue;
			if(isExistDomino[n][i])
				serch(i);
		}
	}
}

Measured memory_bytes: 16976
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <functional>
#include <ctime>
#include <cmath>
#include <limits>
#include <numeric>
#include <type_traits>
using namespace std;
using ll = long long;

unsigned euclidean_gcd(unsigned a, unsigned b) {
    if (a < b) return euclidean_gcd(b, a);
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

class UnionFind {
public:
    vector <ll> par;
    vector <ll> siz;
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    ll root(ll x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}

int main() {
    int a,b;
    cin >> a >> b;
    if (b > a * (a - 1) / 2 - a + 1) { cout << -1 << endl; }
    else {
        int cn = a * (a - 1)/2 - b;
        cout << cn << endl;
        for (int i = 1; i < a; i++) {
            cout << 1 << " " << i + 1 << endl;
            cn--;
        }
        int v = 0;
        
        for (int i = 2; i < a + 1; i++) {
            if (cn == 0) { break;
            }
            for (int j = i + 1; j < a + 1; j++) {
                cout << i << " " << j << endl;
                cn--;
                if (cn == 0) {
                     v = 1;break;
                }
            }
            if (v == 1)break;
        }
    }
}

Measured memory_bytes: 256
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

n = int(input())
s = input()

c = 0
for i in range(len(s) - 2):
    if s[i] == 'A' and s[i + 1] == 'B' and s[i + 2] == 'C':
        c += 1

print(c)

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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
#define show(a, n) rep(i,n) {cout<<a[i]<<' ';} cout<<endl
#define show2(a, n, m) rep(i, n) { rep(j, m) {cout << a[i][j] << ' ';} cout << endl;} 
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<long long, long long> pll;
typedef long double ld;

const int INF = 1 << 30;
const long long INFL = 1LL << 60;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 100010;

struct UnionFind {
	vector<int> par;

	UnionFind(int N) : par(N) {
		for (int i = 0; i < N; i++) par[i] = i;
	}

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

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

	void merge(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		if (rx == ry) return;
		par[rx] = ry;
	}
};

typedef tuple<ld, int, int> tup;

int main() {
	cout << fixed << setprecision(3);
	vector<ld> ans;
	while(true) {
		int n;
		cin >> n;
		if(n == 0) break;
		vector<ld> x(n), y(n), z(n), r(n);
		rep(i, n) cin >> x[i] >> y[i] >> z[i] >> r[i];
		vector<tup> v;
		rep(i, n - 1) for(int j = i + 1; j < n; j++) {
			ld d = sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) + (z[i]-z[j])*(z[i]-z[j]));
			d = max(d - r[i] - r[j], (ld)0.0);
			v.push_back(tup(d, i, j));
		}
		sort(v.begin(), v.end());
		UnionFind uf(n);
		ld tmp = 0.0;
		rep(i, v.size()) {
			ld d;
			int j, k;
			tie(d, j, k) = v[i];
			if(uf.issame(j, k)) continue;
			tmp += d;
			uf.merge(j, k);
		}
		ans.push_back(tmp);
	}
	for(auto i: ans) cout << i << endl;
}



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

typedef long long int LL;
int main()
{
    int n;
    int cnt = 0;
    cin >> n;
    vector<int> num(n + 1);
    for(int a = 1; a < 105; ++a) {
        for(int b = 1; b < 105; ++b) {
            for(int c = 1; c < 105; ++c) {
                int res = a * a + b * b + c * c + a * b + b * c + c * a;
                if(res > n) continue;
                num[res]++;
            }
        }
    } 
    for(int i = 1; i <=n; ++i) cout << num[i] << "\n";
    return 0;
}


Measured memory_bytes: 3520
n = int(input())
ans = 100000
for i in range(1, n):
    a, b = str(i), str(n-i)
    A, B = 0, 0
    for x in a:
        A += int(x)
    for y in b:
        B += int(y)
    ans = min(ans, A+B)
print(ans)

Measured memory_bytes: 73744
<?php

fscanf(STDIN, "%s", $in_s);
$n = strlen($in_s);
$s1 = substr($in_s , 0, ($n / 2));
$s2 = substr($in_s , -($n / 2), ($n / 2));
//var_dump($in_s);
//var_dump($n);
//var_dump($s1);
//var_dump($s2);

$ans = "Yes";
for ($i = 0; $i < $n / 2; $i++) {
    if($in_s[$i] != $in_s[$n - $i - 1]){
    $ans = "No";
    }
}

$n1 = strlen($s1);
for ($i = 0; $i < $n1 / 2; $i++) {
    if($s1[$i] != $s1[$n1 - $i - 1]){
        $ans = "No";
    }
}

$n2 = strlen($s2);
for ($i = 0; $i < $n2 / 2; $i++) {
    if($s2[$i] != $s2[$n1 - $i - 1]){
        $ans = "No";
    }
}


echo "$ans\n";


Measured memory_bytes: 4728
import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String ST = sc.next();
        StringBuilder S = new StringBuilder(ST);
		
		for(int i=0; i<S.length(); i++){
		    if(S.charAt(i) == '?'){
		            S.setCharAt(i,'D');
		    }
		}
		
		System.out.println(S);
    }
}

Measured memory_bytes: 41216
// SeeAlso: 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define MAX 100000
#define NIL -1

typedef int _loop_int;
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// 最大公約数
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
// 最小公倍数
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
template<class T> void print(const T& x){cout << setprecision(12) << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }

int N;

int main() {
    cin >> N;
    int ans = pow(N, 3);
    print(ans);    
    return 0;
}


Measured memory_bytes: 892
#include<bits/stdc++.h>
using namespace std;
int main(){
    std::ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long int a,b;
    cin>>a>>b;
    cout<<((a<b)?"0":"10")<<endl;
    return 0;
}

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

int main() {
    stack<int> st;
    int n;
    while (cin >> n) {
        if (n == 0) {
            cout << st.top() << endl;
            st.pop();
        } else {
            st.push(n);
        }
    }
    return 0;
}

Measured memory_bytes: 1200
#include <iostream>

using namespace std;

int gcd(int a, int b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    
    return a;
}

int solve(int K) {
    int res = 0;
    for (int i = 1; i <= K; ++i) {
        for (int j = 1; j <= K; ++j) {
            int a = gcd(i, j);
            for (int k = 1; k <= K; ++k) {
                res += gcd(a, k);
            }
        }
    }

    return res;
}

int main() {
    int K; cin >> K;
    cout << solve(K) << endl;
}

Measured memory_bytes: 3188
H, W = map(int, input().split())
sw = [list(str(input())) for i in range(H)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]

for i in range(H):
  for j in range(W):
    if sw[i][j] == "#":
      counter = 0
      for k in range(4):
        if i+dx[k] < 0 or i+dx[k] >= H or j+dy[k] < 0 or j+dy[k] >= W:
          counter += 1
        elif sw[i+dx[k]][j+dy[k]] == ".":
          counter += 1
      if counter == 4:
        print("No")
        exit()
print("Yes")

Measured memory_bytes: 3064
import math
a,b,h,m=map(int,input().split())
alpha=math.pi*m/30
beta=math.pi*(h*60+m)/360

if alpha>beta:
    sita=alpha-beta
else:
    sita=beta-alpha

sita=min(sita,2*math.pi-sita)

c=(a**2+b**2-2*a*b*math.cos(sita))**(1/2)
print(c)

Measured memory_bytes: 9512
#include <bits/stdc++.h>
 
using namespace std;
 
#define repr(i,a,b) for (int i=a; i<b; i++)
#define rep(i,n) for (int i=0; i<  n; i++)
 
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; }
 
const long long INF = 1LL << 60;
#define PI 3.14159265359 
long long MOD = 1000000007;


template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}
 
int gcd(int a, int b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}
 
long long lcm (int a, int b){
    return  (long long) a*b /gcd(a,b);
}

long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }

long long dp[200100];

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

    int ans = max(c*10+a+b,max(a*10+b+c,b*10+c+a));

    cout << ans << endl;
}



Measured memory_bytes: 3600
fun main(args: Array<String>) {
  readLine()
  val array = readLine()
    ?.split("\\s+".toRegex())
    ?.map(String::toInt)
    ?.toIntArray()
    ?: intArrayOf()
  var cnt = 0
  for (i in 0 until array.size - 1) {
    var min = i
    for (j in i + 1 until array.size) {
      if (array[min] > array[j]) {
        min = j
      }
    }
    if (min != i) {
      array.swap(i, min)
      cnt++
    }
  }
  println(array.joinToString(" "))
  println(cnt)
}

fun IntArray.swap(i: Int, j: Int) {
  val tmp = this[i]
  this[i] = this[j]
  this[j] = tmp
}



Measured memory_bytes: 31512
n, k = map(int, input().split())
xs = list(map(int, input().split()))

min_ = None
for i in range(n-k+1):
  res = min(abs(xs[i]) + abs(xs[i+k-1] - xs[i]), abs(xs[i+k-1]) + abs(xs[i] - xs[i+k-1]))
  if min_ is None:
    min_ = res
  else:
    min_ = min(res, min_)
print(min_)

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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 62)

typedef long long i64;
typedef pair<i64,i64> P;

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

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



int n, a[1010], k;
void solve(){
	cin >> n >> k;
	i64 sum = 0;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		sum += a[i];
	}
	vector<int> v;
	for(int i = 1; i*i <= sum; i++){
		if(sum % i == 0){
			v.push_back(i);
			v.push_back(sum/i);
		}
	}
	sort(v.begin(),v.end());
	
	int ans = 1;
	for(int i = 0; i < v.size(); i++){
		i64 cnt = 0;
		priority_queue<int> pq;
		for(int j = 0; j < n; j++){
			cnt += mod(a[j],v[i]);
			pq.push(mod(a[j],v[i]));
		}
		int lp = cnt/v[i];
		for(int j = 0; j < lp; j++){
			cnt -= pq.top();
			pq.pop();
		}
		if(cnt <= k) ans = v[i];
	}
	cout << ans << endl;
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

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

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

	vector<pair<int,int>> pr;

	for(int i = 0;i < n;i++){
		int x,y;
		cin>>x>>y;
		pr.push_back({x,y});
	}

    sort(pr.begin(),pr.end(),greater<pair<int,int>>());

    vector<int> temp;
    for(int i = 0;i < n;i++){ temp.push_back(pr[i].second);}

    sort(temp.begin(),temp.end(),greater<int>()); 
    int res = 0;
    //for(int i = 0;i<n;i++) cout<<temp[i]<<" ";
    for(int i=0;i<(int)temp.size() && h>0;i++){
    	if(temp[i] >= pr[0].first) h-=temp[i];
    	else h-=pr[0].first;
    	res++;
    }
    // if(pr[0].first <= pr[0].second && h>0){
    //  res++;
    //  h-=pr[0].second;
    //  }
     if(h>0 && h%pr[0].first) res+=(h/pr[0].first + 1);
     else if(h>0 && h%pr[0].first == 0) res+=(h/pr[0].first);
  
    cout<<res;
    
}

Measured memory_bytes: 1908