akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <complex>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B,C,L,R;
string S,T;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL << 60;
const long double EPS = 1e-9;
typedef pair<ll,ll> P;

typedef vector<P> vp;
typedef vector<vp> matP;


int main() {
    cin>>N;
    ll num = (1LL << N);
    vec a(num);
    rep(i,num) cin>>a[i];
    a.push_back(-1); //a[num]で最小値に飛ぶ
    mat dp(num,vec(2,num));
    rep(i,num){
        if(i == 0){
            dp[0][0] = 0;
        }else{
            dp[i][0] = i;
            ll &n1 = dp[i][0], &n2 = dp[i][1];
            //for(int j = ((i - 1) & i); ; j = ((j - 1) & i)){
            rep(bit,18){
                if(((i>>bit)&1) == 0) continue;
                int j = i - (1LL<<bit);
                rep(k,2){
                    ll tp = dp[j][k];
                    if((tp == n1) || (tp == n2)) continue;
                    if(a[n1] <= a[tp]){
                        n2 = n1;
                        n1 = tp;
                    }else if(a[n2] < a[tp]){
                        n2 = tp;
                    }
                }
                if(j == 0) break;
            }
        }
    }
    ll ans = -1;
    reps(i,1,num){
        ans = max(ans, a[dp[i][0]] + a[dp[i][1]]);
        cout<<ans<<endl;
    }
}

Measured memory_bytes: 21372
#include <stdio.h>


typedef struct{
  char mj;
  int  num;
}trump;

void show(trump A[],int N){
  for (int  i = 0; i < N; i++) {
    printf("%c%d",A[i].mj,A[i].num );
    if(i!=N-1)printf(" ");
  }
  printf("\n");
}

void bubble(trump A[],int N){
  int sw;
  char swc;
  for (int i = 0; i < N-1; i++) {
    for (int j = N-1; i < j; j--) {
      if(A[j].num < A[j-1].num){
        sw = A[j].num;
        A[j].num=A[j-1].num;
        A[j-1].num=sw;
        swc = A[j].mj;
        A[j].mj=A[j-1].mj;
        A[j-1].mj=swc;
      }
    }
  }
}

int comp(trump A[],trump B[],int N){
    for (int i = 0; i < N; i++) {
      if(A[i].mj!=B[i].mj) return 0;
    }
    return 1;
}

void selection(trump A[],int N)
{
  int minj;
  trump sw;
  for (int i = 0; i < N-1; i++) {
    minj=i;
    for (int j = i; j < N; j++) {
      if(A[minj].num>A[j].num) minj=j;
    }
    sw=A[i];A[i]=A[minj];A[minj]=sw;
  }

}

int main()
{
 trump I[100];
 trump B[100];
 int N;
 scanf("%d\n",&N);
 /*for (int i = 0; i < N; i++) {
   scanf("%c%d",&I[i].mj,&I[i].num);
   B[i].num = I[i].num;
   B[i].mj = I[i].mj;
 }*/
 int i;
 for(i=0;i<N;i++){
scanf(" %c%d",&I[i].mj,&I[i].num);
B[i]=I[i];
}
 bubble(B,N);
 show(B,N);
 if(comp(B,B,N)) printf("Stable\n"); else printf("Not stable\n" );
 selection(I,N);
 show(I,N);
  if(comp(B,I,N)) printf("Stable\n"); else printf("Not stable\n" );
 return 0;
}



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

int main() {
    ll N, M, K; cin >> N >> M >> K;
    vector<ll> A(N), B(M), S(M+1, 0);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 0; i < M; ++i) cin >> B[i];
    for (int i = 0; i < M; ++i) S[i+1] = S[i] + B[i];
    ll sum = 0;
    ll ans = 0;
    for (int i = 0; i <= N; ++i) {
        if (sum > K) break;
        ll j = upper_bound(S.begin(), S.end(), K - sum) - S.begin() - 1;
        ans = max(ans, i + j);
        if (i < N) sum += A[i];
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 7980
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P>IP;
typedef vector<ll> V;
typedef vector<V> V2;
typedef vector<vector<P> > G;
void g_dir(G &graph, ll a, ll b, ll w = 1){graph[a].push_back(P(b, w));}
void g_undir(G &graph, ll a, ll b, ll w = 1){g_dir(graph, a, b, w);g_dir(graph, b, a, w);}
#define rep(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define rep1(i, n) for(ll (i) = 1; (i) <= (n); (i)++)
#define rrep(i, n) for(ll (i) = (n) - 1; (i) >= 0; (i)--)
#define rrep1(i, n) for(ll (i) = (n); (i) >= 1; (i)--)
template<class T> void chmax(T &a, const T &b){if(a < b){a = b;}}
template<class T> void chmin(T &a, const T &b){if(a > b){a = b;}}
const ll INF = 1145141919;
const ll MOD = 1000000007;
const ll NUM = 101010;

int main(){
    
    ll N, a, b;
    cin >> N >> a >> b;
    rep(i, N - 1){
        ll x, y;
        cin >> x >> y;
        ll c = a / x;
        if(a % x)c++;
        ll d = b / y;
        if(b % y)d++;
        a = max(c, d) * x;
        b = max(c, d) * y;
    }
    cout << a + b << endl;
    
    return 0;
}

Measured memory_bytes: 256
import itertools

N=int(input())
X=tuple(map(int,input().split()))
Y=tuple(map(int,input().split()))
#print(X)

L=[i for i in range(1,N+1)]
A=list(itertools.permutations(L,N))
A.sort()
x=0
y=0
for i in range(len(A)):
    if A[i]==X:
        x=i
    if A[i]==Y:
        y=i
#print(A)
#print(x,y)
print(abs(x-y))


Measured memory_bytes: 8052
#include<bits/stdc++.h>
#define maxn 50000

using namespace std;
int ans,n,k,query,j,m;
int f[maxn],g[maxn];

int solve(int x,int y)
{
    if (y==1) return x;
    if (x%y==0) return x/y;
    int d=x/y+1,r=((x-y*(x/y))-1)/d+1;
    return solve(x-r*d,y);
}

int main()
{
    scanf("%d",&query);
    while (query--)
    {
        scanf("%d%d",&n,&k);
        ans^=solve(n,k);
        //cout << solve(n,k) << endl;
    }
    if (ans) cout << "Takahashi" << endl; else cout << "Aoki" << endl;
    return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
ans = B[A[0]-1]
for i in range(1,N):
    ans += B[A[i]-1]
    if A[i]-A[i-1] ==1:
        ans += C[A[i-1]-1]
print(ans)

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

typedef long long int ll;
typedef pair<ll, ll> p_ll;
typedef vector<pair<ll, ll>> vec_p; //vector<pair<ll, ll>> pairs(n) ,pairs.at(i) = make_pair(i*i, i)

const ll MOD = pow(10, 9) + 7;
const ll LLINF = pow(2, 61) - 1;
const int INF = pow(2, 30) - 1;

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

    ll N;
    cin >> N;

    vector<ll> vec(N+1);
    for (ll i = 1; i <= N; i++) {
        cin>>vec.at(i);
    }

    ll tmp = 1;
    ll count = -1;
    vector<ll> flag(N + 1);
    for (ll i = 1; i <= N; i++) {
        flag.at(i)=0;
    }
    while(true){
        flag.at(tmp) = 1;
        tmp = vec.at(tmp);
        count++;
        if (flag.at(2) == 1)
        {
            cout << count << endl;
            break;
        }
        else if(flag.at(tmp)==1){
            cout << -1 << endl;
            break;
        }
        
    }
}


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

namespace ABC153C
{
    public class EmptyClass
    {
        public static void Main(string[] args)
        {
            long[] n = Array.ConvertAll(Console.ReadLine().Split(' '), long.Parse);
            long[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), long.Parse);
            Console.WriteLine(arr.OrderByDescending(e => e).Skip((int)n[1]).Sum());

        }
    }
}


Measured memory_bytes: 39680
#include <stdio.h>

int main (void)
{
    int a,b,c,d;

    scanf("%d",&a);
    scanf("%d",&b);
    scanf("%d",&c);
    scanf("%d",&d);

    if(a*b == c*d)
        printf("%d\n",a*b);
    else if(a*b > c*d)
        printf("%d\n",a*b);
    else
        printf("%d\n",c*d);


    return 0;
}

Measured memory_bytes: 128
from collections import deque
import sys
import heapq
n = int(input())
V = [[int(i) for i in input().split()] for _ in range(n)]
dis = [sys.maxsize for _ in range(n)]
dis[0] = 0
h = []
for i in range(n):
    heapq.heappush(h,(dis[i],i))
while(len(h)>0):
    node = heapq.heappop(h)
    tmp = node[1]
    for i in range(V[tmp][1]):
        ind = V[tmp][2*i+2]
        cos = V[tmp][2*i+3]
        if cos + dis[tmp] < dis[ind]:
            dis[ind] = cos + dis[tmp]
            heapq.heappush(h,(dis[ind],ind))
for i,j in enumerate(dis):
    print(i,j)


Measured memory_bytes: 6228
class UFTree
  def initialize(n)
    @p = Array.new(n + 1, -1)
  end
  def find(x)
    @p[x] < 0 ? x : @p[x] = find(@p[x])
  end
  def unite(a, b)
    x = find(a)
    y = find(b)
    if x != y
      x, y = y, x if @p[y] < @p[x]
      @p[y] = x
    end
  end
  def parents
    @p
  end
end

N, M = gets.split.map(&:to_i)

tree = UFTree.new(N)
M.times do
  a, b = gets.split.map(&:to_i)
  tree.unite(a, b)
end
puts tree.parents.count{|x| x < 0} - 2


Measured memory_bytes: 15148
N = int(input())
H = list(map(int, input().split()))

best = []
a = 0
for i in range(N-1):
  if H[i] >= H[i+1]:
    a += 1
  else : 
    best.append(a)
    a = 0
best.append(a)
print(max(best))

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

using namespace std;

int main()
{
  int N;
  cin >> N;
  vector<vector<int>> shortest(N, vector<int>(N, 0));
  for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) cin >> shortest[i][j];
  bool possible = true;
  long sum = 0;
  for (int i = 0; i < N; ++i) {
    for (int j = i + 1; j < N; ++j) {
      bool use = true;
      int d0 = shortest[i][j];
      for (int k = 0; k < N; ++k) {
        if (k == i or k == j) continue;
        long d = shortest[i][k] + shortest[k][j];
        if (d < d0) {
          possible = false;
          goto exit;
        }
        if (d == d0) use = false;
      }
      if (use) sum += d0;
    }
  }
exit: 
  cout << (possible ? sum : -1) << endl;
  return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <string>
#include  <queue>
#include <vector>
#include  <cstdio>
#include <cstring>
#include<map>
#include<set>
#include <cmath>
#include<unordered_map>
//#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define I(a) scanf("%d",&a)
#define I2(a,b) scanf("%d%d",&a,&b)
#define I3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define L(a) scanf("%lld",&a)
#define L2(a,b) scanf("%lld%lld",&a,&b)
#define L3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define PI(a) printf("%d",a)
#define PL(a) printf("%lld",a)
#define PT(t) printf("Case %d: ",t)
#define PB push_back
#define x first
#define y second
#define xx first.first
#define xy first.second
#define yx second.first
#define yy second.second
#define SC scanf
#define PC printf
#define NL printf("\n")
#define SET(a) memset(a,0,sizeof a)
#define SETR(a) memset(a,-1,sizeof a)
#define SZ(a) ((int)a.size())-1
#define f(i,a,b) for(int i=a;i<=b; i++)
#define fr(i,a,b) for(int i=a;i<=b; i++)
#define frr(i,a,b) for(int i=a;i>=b; i--)
#define frv(i,a)  for(int i=0;i<a.size();i++)
#define pi 2.0*acos(0.0)
#define R(a) freopen(a, "r", stdin);
#define W(a) freopen(a, "w", stdout);
#define CB(x) __builtin_popcount(x)
#define STN(a) stringtonumber<ll>(a)
#define lol printf("BUG\n")
#define Endl "\n"
#define mk make_pair
using namespace std;
template <class T> inline T BM(T p, T e, T M)
{
    ll ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    }
    return (T)ret;
}
template <class T> inline T mul(T p, T e, T M)
{
    ll ret = 0;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret + p) ;
        p = (p + p) ;
        if(ret>=M)ret-=M;
        if(p>=M)p-=M;
    }
    return (T)ret;
}
template <class T> inline T gcd(T a, T b)
{
    if(b == 0)return a;
    return gcd(b, a % b);
}
template <class T> inline T mdINV(T a, T M)
{
    return BM(a, M - 2, M);
}
template <class T> inline T PW(T p, T e)
{
    ll ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p);
        p = (p * p);
    }
    return (T)ret;
}
 
 
template <class T>bool ISLEFT(T a, T b, T c)
{
    if(((a.xx - b.xx) * (b.yy - c.yy) - (b.xx - c.xx) * (a.yy - b.yy)) < 0.0)return 1;  //Uporer dike //A,b,c, x okkher ordera sorted
    else return 0;
}
 

#define  mx 2000000000000000ll
#define base 193ll
 
typedef pair<int,int >P;
//////////////////////////
////////////////////////
#define F(i,a,b) for(int i=a;i<b; i++)
#define LL long long
#define MX  10000000
#define md 998244353ll
///////////////////////////
///////////////////////////
///

int main(){
    char ar[100];
    SC("%s", ar+1);
    int l = strlen(ar+1);
    int res = 753;
    for(int i = 1;i<=l-3+1;i++){
        int val =( (ar[i] - '0')*10 + ar[i+1] - '0')*10 + ar[i+2] - '0';
        res = min(res, abs(753-val));
    }
    cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,j,s=0,k,f,m;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            for(k=1;k<=n;k++)
            {
                if(i==j&&j==k)
                    s+=k;
                else
                {
                    m=min(i,min(j,k));
                    for(f=m;f>=1;f--)
                    {
                        if(i%f==0&&j%f==0&&k%f==0)
                        {
                            s+=f;
                            break;
                        }
                    }
                }
            }
        }
    }
    cout<<s<<endl;
    return 0;
}


Measured memory_bytes: 3636
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        (a,b,c,k): (i64, i64,i64,i64)
    };

    if k <= a {
        println!("{}", k);
        return;
    } else if k <= a + b {
        println!("{}", a);
    } else {
        println!("{}", a - (k - (a + b)));
    }
}


Measured memory_bytes: 2128
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin >> s;
    for(int i = 0;i < 26;i++)
    {
        char c = 'a' + i;
        if(s.find(c) == -1)
        {
            cout << c;
            return 0;
        }
    }
    cout << "None";
    
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <vector>
#include <string.h>
using namespace std;

int main() {
	int N,k=0,A[200000]={},ans=0,K,a;
	cin>>N>>K;
	for(int i=0;i<N;i++)
	{
		cin>>a;
		A[a]++;
	}
	sort(A,A+200000);
	for(int i=200000-1;i>=0;i--)
	{
		if(k>=K)ans+=A[i];
		if(A[i]==0)break;
		k++;
	}
	cout<<ans;
	}

Measured memory_bytes: 1024
fun main(args: Array<String>) {
    val (x, y) = readLine()!!.split(" ").map { it.toInt() }
    val l = readLine()!!.split(" ").map { Math.abs(it.toInt() - y) }
    var a = l.first()
    for (i in 0 until l.size) {
        a = gcd(a,l[i])
    }
    println(a)
}

fun gcd(a: Int, b: Int): Int {
    if (b == 0) return a
    return if (a < b)gcd(b, a) else gcd(b, a % b)
}


Measured memory_bytes: 49664
#include <iostream>
#include<algorithm>
#include<string>
#include <cmath>
#include <vector>
#include <map>
#include <cstdio>
#pragma region Macros
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define int long long
#define all(x) (x).begin(),(x).end()
#define swap(a,b) (a += b,b = a - b,a -= b)
#define CEIL(a,b) ((a+b-1)/b)
#define MOD 1000000007
int GCD(int a, int b) // assuming a,b >= 1
{
	if (a < b)
		swap(a, b);
	if (b == 0)
		return a;
	if (a % b == 0)
		return b;
	return GCD(b, a % b);
}
int LCM(int a, int b) // assuming a,b >= 1
{
	return  a * b / GCD(a, b);
}
inline bool BETWEEN(int x, int min,int max) {
	if (min <= x && x <= max)
		return true;
	else
		return false;
}
int cnt;
int combination(int n, int m) {
	cnt++;
	if (m > n - m)
		m = n - m;
	if (m == 0 || n == m)
		return 1;
	return combination(n - 1, m) + combination(n - 1, m - 1);
}



using namespace std;
#pragma endregion
signed main() {
		int n,k;
		cin >> n >> k;
		cout << n*n-k;
}

Measured memory_bytes: 256
<?php
define("MOD", 100);
$n = intval(trim(fgets(STDIN)));
$s = trim(fgets(STDIN));
$n = strlen($s);
$kigu = 0;
for($i = 0; $i < $n; ++$i){
    $dp[$i] = ((int)$s[$i])-1;
    $kigu ^= ($dp[$i]%2) * ((($n-1) & $i) == $i);
}
if($kigu){
    echo 1;
}else{
    if(array_search(1, $dp)!==false){
        echo 0;
    }else{
        $kigu = 0;
        for($i = 0; $i < $n; ++$i){
            $kigu ^= (($dp[$i]/2)%2) * ((($n-1) & $i) == $i);
        }
        if($kigu){
            echo 2;
        }else{
            echo 0;
        }
    }
}


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

int main()
{
    vector<int> a(32);
   a = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

    int k;
    cin >> k;
    cout << a.at(k-1) << "\n";
    return 0;
}


Measured memory_bytes: 384
#pragma warning( disable : 4996 )
/*
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
*/
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cstdint>
#include <cmath>
#include <algorithm>
#include <tuple>
#define ios_jazz ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define FOR(i, l, r) for (int i = (l); i < (r); ++i)
#define FORR(i, r, l) for (int i =(r); i >= (l); --i)
#define P(STR) puts(#STR)

using namespace std;

constexpr int Dir4[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
constexpr int Dir8[8][2] = { {-1, -1}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 1} };
constexpr double EPS = 1e-8;
const double PI = acos(-1);

using int16 = short;
using uint16 = unsigned short;
using uint = unsigned int;
using int64 = long long;
using uint64 = unsigned long long;
using pii = pair<int, int>;

auto Equal = [](double a, double b) { return fabs(a - b) < EPS; };

/* mods */

/* main code */
#include <set>
#include <map>

int n, x;
map<int, int> cnt;
multiset<int> Set;

int main()
{
	scanf("%d", &n);

	while (n--)
	{
		scanf("%d", &x);

		++cnt[x];
		if (cnt[x] == 2)
		{
			cnt[x] = 0;
			Set.insert(x);
		}
	}

	if (Set.size() < 2)
	{
		P(0);
		return 0;
	}

	auto a = Set.rbegin(), b = Set.rbegin();
	++b;

	printf("%lld", (int64)(*a) * (*b));

	return 0;
}


Measured memory_bytes: 4864
# coding: utf-8
if __name__ == '__main__':
    dic = dict()
    n = int(input())
    for i in range(n):
        val = input()
        if val in dic.keys():
            dic[val]+=1
        else:
            dic[val]=1
    max_keys = max(dic.values())
    values_of_max_key = [val for val in dic if dic[val] == max_keys]
    sorted_values_of_max_key = sorted(values_of_max_key)
    for s in sorted_values_of_max_key:
        print(s)

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

int main(){
	string X;
	char ch[2000000];
	
	stack <char> first;
	stack <char> second;

	cin >> ch;
	X = ch;

	for(int i=0; i<X.size(); i++){
		if(first.size() == 0){
			first.push(X[i]);
		}
		else{
			if(first.top() == 'S' && X[i] == 'T'){
				first.pop();
				second.push(X[i]);
			}
			else{
				first.push(X[i]);
			}
		}
	}
	
	cout << first.size();

	return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const ll mo = 1000000007;
const ll INF = 1LL << 60; //MAX 9223372036854775807
ll ans = 0;
struct UnionFind {
  vector<ll> data;
  UnionFind(ll size) : data(size, -1) { }
  bool unionSet(ll x, ll y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(ll x, ll y) {
    return root(x) == root(y);
  }
  ll root(ll x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  ll size(ll x) {
    return -data[root(x)];
  }
};

//UnionFind arr(n);で０～n-1バラバラが生成
//arr.findSet(x,y)同じ集合か
//arr.size(x)xが属す要素の個数
//arr.unionSet(x,y)xが属す集合とyが属す集合をマージ
int main()
{
ll n;
cin >> n;
UnionFind arr(200000);
set<ll> xx,yy;
rep(i, n){
    ll x,y;
    cin >> x>>y;
    x--;y--;
    arr.unionSet(x,y+100000);
    xx.insert(x);
    yy.insert(y);
}
map<ll,pair<ll,ll>> m{};
auto itr=xx.begin();
rep(i,xx.size()){
    m[arr.root(*itr)].first+=1;
    itr++;
}
itr=yy.begin();
rep(i,yy.size()){
    m[arr.root(*itr+100000)].second+=1;
    itr++;
}

for (auto i = m.begin(); i != m.end(); ++i) {
    pair<ll,ll> pp;
    pp=i->second;
    ans+=pp.first*pp.second;
}

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


Measured memory_bytes: 6528
function read()
    return io.read("*num")
end
n = read()
T = read()
A = read()
Max = math.maxinteger;
for i = 1, n do
    x = read()
    now = math.abs(T - x * 0.006 - A)
    if now < Max then
        Max = now
        ans = i
    end
end
print(ans)



Measured memory_bytes: 760
N = gets.to_i
values = gets.split.take(N).map(&:to_i)
ns, ms = values.partition.with_index { |_, i| i.odd? }
ns_table = Hash.new { 0 }
ns.each do |n|
  ns_table[n] += 1
end
ms_table = Hash.new { 0 }
ms.each do |n|
  ms_table[n] += 1
end
sorted_ns = ns_table.sort_by { |k, v| -v }
sorted_ms = ms_table.sort_by { |k, v| -v }
ns_max1 = sorted_ns[0]
ns_max2 = sorted_ns[1]
ms_max1 = sorted_ms[0]
ms_max2 = sorted_ms[1]
combinations = [
  [ns_max1, ms_max1],
  ms_max2 ? [ns_max1, ms_max2] : nil,
  ns_max2 ? [ns_max2, ms_max1] : nil,
  (ns_max2 && ms_max2) ? [ns_max2, ms_max2] : nil
].compact
combinations = combinations.select { |ns, ms| ns[0] != ms[0] }
if combinations.empty?
  puts N / 2
else
  ans = combinations.map { |ns, ms| (N / 2 - ns[1]) + (N / 2 - ms[1]) }
                    .min
  puts ans
end


Measured memory_bytes: 21468
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#define int long long
using namespace std;
const int maxn = 2e6+10;
const int mod = 1e9+7;

int read(){
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+c-48;c=getchar();}
	return x*f;
}

int k,m,n;
int x,y,xx,yy;
int fac[maxn],inv[maxn],num=2e6+5;
int fpm(int x,int y){
	int sum=1;
	while(y){
		if(y&1)sum=1ll*sum*x%mod;
		x=1ll*x*x%mod;
		y>>=1;
	}
	return sum;
}
inline void init(){
	fac[0]=inv[0]=1;
	for(register int i=1;i<=num;i++)fac[i]=fac[i-1]*i%mod;
	inv[num]=fpm(fac[num],mod-2);
	for(register int i=num-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%mod;
	return;
}

int C(int x,int y){
	return fac[y]*inv[x]%mod*inv[y-x]%mod;
}

int A(int x,int y){
	return fac[y]*inv[x]%mod;
}

int solve(int n,int m){
	int sum=0;
	for(register int i=1;i<=n;i++){
		(sum+=C(i+1,i+m+1))%=mod;
	}
	return sum;
}

signed main(){
	init();
	x=read();y=read();
	xx=read();yy=read();
	int ans=0;
	//for(register int i=x;i<=xx;i++){
	//	for(register int j=y;j<=yy;j++){
	//		(ans+=C(i,i+j))%=mod;
	//	}
	//}
	ans=solve(xx,yy)-solve(x-1,yy)-solve(xx,y-1)+solve(x-1,y-1);
	while(ans<0)ans+=mod;
	ans%=mod;
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 31488
#include <bits/stdc++.h>
using namespace std;
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout << fixed << setprecision(20);
#define int long long
#define double long double
const int INF = 1e18, MOD = 1e9 + 7;

signed main() {
    int n, m;
    cin>>n>>m;
    int s[10], c[10];
    for (int i = 0; i < m; i++) {
        cin>>s[i]>>c[i];
    }
    switch (n) {
        case 1:
            for (int i = 0; i < 10; i++) {
                bool flag = true;
                for (int j = 0; j < m; j++) {
                    int tmp = i;
                    for (int k = 0; k < n - s[j]; k++) tmp /= 10;
                    if (tmp % 10 != c[j]) flag = false;
                }
                if (flag) {
                    cout<<i<<endl;
                    return 0;
                }
            }
            break;
        case 2:
            for (int i = 10; i < 100; i++) {
                bool flag = true;
                for (int j = 0; j < m; j++) {
                    int tmp = i;
                    for (int k = 0; k < n - s[j]; k++) tmp /= 10;
                    if (tmp % 10 != c[j]) flag = false;
                }
                if (flag) {
                    cout<<i<<endl;
                    return 0;
                }
            }
            break;
        case 3:
            for (int i = 100; i < 1000; i++) {
                bool flag = true;
                for (int j = 0; j < m; j++) {
                    int tmp = i;
                    for (int k = 0; k < n - s[j]; k++) tmp /= 10;
                    if (tmp % 10 != c[j]) flag = false;
                }
                if (flag) {
                    cout<<i<<endl;
                    return 0;
                }
            }
            break;
    }
    cout<<-1<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
const double PI = acos(-1);
#define rep(i, n) for (int i = 0; i < (int)(n); i++ )
using namespace std;
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}
int main(){
    long long n;
    cin >> n;
    int ans = 0;
    bool f = false;
    int m = 0;
    vector<char> c(n);
    rep(i,n) cin >> c.at(i);
    for(int i = n-1; i >= 0; i--){
        if(c.at(i) == 'R'){
            for(int j = m; j < n; j++){
                if(c.at(j) == 'W'){
                    swap(c.at(j),c.at(i));
                    ans++;
                    m = j;
                    break;
                }
                if(j == i){
                    f = true;
                    break;
                }
            }
        }
        if(f) break;
    }
    cout << ans << endl;
}

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

const int MOD = 1000000007;

int main() {
    int N, M;
    std::cin >> N >> M;

    std::vector<int> S(N), T(M);
    for (int i = 0; i < N; i++)
        std::cin >> S[i];
    for (int i = 0; i < M; i++)
        std::cin >> T[i];

    std::vector<std::vector<int>> cs(N + 1, std::vector<int>(M + 1));
    cs[0][0] = 1;
    for (int i = 0; i <= N; i++)
        for (int j = 0; j <= M; j++) {
            if (i > 0)
                cs[i][j] = (cs[i][j] + cs[i - 1][j]) % MOD;
            if (j > 0)
                cs[i][j] = (cs[i][j] + cs[i][j - 1]) % MOD;
            if (i > 0 && j > 0) {
                cs[i][j] -= cs[i - 1][j - 1];
                cs[i][j] += cs[i][j] < 0 ? MOD : 0;
                if (S[i - 1] == T[j - 1])
                    cs[i][j] = (cs[i][j] + cs[i - 1][j - 1]) % MOD;
            }
        }

    std::cout << cs[N][M] << "\n";
}

Measured memory_bytes: 16000
module String = struct
  include String

  let to_list str =
    let rec doit i acc =
      if i < 0 then acc
      else doit (i - 1) (String.get str i :: acc) in
    doit (String.length str - 1) []

end

let (height, width) = (8, 8)

let read_ns () = read_line () |> String.to_list |> List.map (fun e -> Char.code e - Char.code '0')

(* check index *)

let check t i j =
  let a i j = i+1 < height && j+1 < width && List.for_all ((=) 1) [t.(i).(j); t.(i).(j+1); t.(i+1).(j); t.(i+1).(j+1)] in
  let b i j = i+3 < height && List.for_all ((=) 1) [t.(i).(j); t.(i+1).(j); t.(i+2).(j); t.(i+3).(j)] in
  let c i j = j+3 < width && List.for_all ((=) 1) [t.(i).(j); t.(i).(j+1); t.(i).(j+2); t.(i).(j+3)] in
  let d i j = i+2 < height && j-1 >= 0 && List.for_all ((=) 1) [t.(i).(j); t.(i+1).(j-1); t.(i+1).(j); t.(i+2).(j-1)] in
  let e i j = i+1 < height && j+2 < width && List.for_all ((=) 1) [t.(i).(j); t.(i).(j+1); t.(i+1).(j+1); t.(i+1).(j+2)] in
  let f i j = i+2 < height && j+1 < width && List.for_all ((=) 1) [t.(i).(j); t.(i+1).(j); t.(i+1).(j+1); t.(i+2).(j+1)] in
  let g i j = i+1 < height && j-1 >= 0 && j+1 < width && List.for_all ((=) 1) [t.(i).(j); t.(i).(j+1); t.(i+1).(j-1); t.(i+1).(j)] in
  let rec doit = function
    | [] -> assert false
    | (f, s) :: tl ->
      if f i j then s
      else doit tl in
  doit [(a, "A"); (b, "B"); (c, "C"); (d, "D"); (e, "E"); (f, "F"); (g, "G")]

let () =
  try
    while true do
      let t = Array.make_matrix height width 0 in
      for i = 0 to height - 1 do
        let rec doit j = function
          | [] -> ()
          | hd :: tl ->
            t.(i).(j) <- hd;
            doit (j + 1) tl in
        read_ns () |> doit 0;
      done;
      let rec doit = function
        | (i, _) when i = height -> assert false
        | (i, j) when j = width -> doit (i + 1, 0)
        | (i, j) ->
          if t.(i).(j) = 1 then (check t i j |> print_endline)
          else doit (i, j + 1) in
      doit (0, 0);
      read_line () |> ignore;
    done
  with _ -> ()

Measured memory_bytes: 2180
def main():
  s = str(input())
  keyence = 'keyence'
  for i in range(len(keyence)+1):
    prefix = keyence[:i]
    postfix = keyence[i:]
    if s.startswith(prefix) and s.endswith(postfix):
      print('YES')
      return
  print('NO')


if __name__ == '__main__':
  main()


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

int main(){

    int n;
    cin>>n;
    set<int> check;
    bool ans=true;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        if(!check.count(a)) check.insert(a);
        else ans=false;
    }
    cout<<(ans?"YES":"NO")<<endl;

    return 0;
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i< (n); i++)
using ll = long long;
using P = pair<int, int>;
int main()
{   
    int n;
    cin >> n;
    string m = to_string(n);
    int cnt = 0;
    rep(i,m.size()){
        cnt += m.at(i) - '0';
    }
    if(n % cnt == 0)cout << "Yes" << endl;
    else cout << "No" << endl;
return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main(){
	int n;
	cin>>n;
	long long h[n];
	for(int i=0;i<n;i++){
		cin>>h[i];
	}
	const long long INF = 1LL << 60;
    long long dp[100100];
    for (int i = 0; i < 100100; ++i) dp[i] = INF;
	dp[0] = 0;
    for (int i=1;i<n;i++) {
        chmin(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]));
        if(i>1)chmin(dp[i],dp[i - 2]+abs(h[i]-h[i - 2]));
    }
    cout<<dp[n-1]<<endl;
	return 0;
}

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

#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x
#define dump_1(x1) cerr << #x1 << ": " << x1 << endl
#define dump_2(x1, x2) \
  cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl
#define dump_3(x1, x2, x3)                                                \
  cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
       << x3 << endl
#define dump_4(x1, x2, x3, x4)                                            \
  cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
       << x3 << ", " #x4 << ": " << x4 << endl
#define dump_5(x1, x2, x3, x4, x5)                                        \
  cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
       << x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl
#define dump(...) \
  CHOOSE((__VA_ARGS__, dump_5, dump_4, dump_3, dump_2, dump_1, ~))(__VA_ARGS__)
#define check(s) cerr << s << endl

#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define unique(v) v.erase(unique(v.begin(), v.end()), v.end());
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

using namespace std;

using ll = long long;

vector<int> dx = {0, 1, 0, -1};
vector<int> dy = {1, 0, -1, 0};

const ll LINF = 2e18;
const int INF = 1e9;

ll N;
std::vector<ll> a;

vector<vector<ll>> dp;

ll f(int l, int r) {
  if (dp.at(l).at(r) != -1) return dp.at(l).at(r);
  if (l == r) return a.at(l);

  ll ret = max(a.at(l) - f(l + 1, r), a.at(r) - f(l, r - 1));
  return dp.at(l).at(r) = ret;
}

void solve() {
  dp.resize(N + 1, vector<ll>(N + 1, -1));

  cout << f(0, N - 1) << endl;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  scanf("%lld", &N);
  a.resize(N);
  for (int i = 0; i < N; i++) {
    scanf("%lld", &a[i]);
  }
  solve();
  return 0;
}


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

using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;
#define DEBUG freopen("in.txt", "r", stdin);

struct fastio {
    fastio() {
        ios::sync_with_stdio(false);
        cout << setprecision(10) << fixed;
        cin.tie(0);
    }
};

fastio _fast_io;

int k;
string s;
int main() {
    cin >> s >> k;
    int n = s.length();
    char t = 'a';
    while (k) {
        set<string> st;
        for (int i = 0; i < n; ++i) {
            if (s[i] == t) {
                string ss;
                for (int j = 0; j < k && i + j < n; ++j) {
                    ss += s[i + j];
                    st.insert(ss);
                }
            }
        }
        if (st.size() >= k) {
            auto it = st.begin();
            while (k != 1) {
                --k;
                ++it;
            }
            cout << *it << endl;
            exit(0);
        }
        k -= st.size();
        ++t;
    }
    return 0;
}


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

using namespace std;

int main()
{
    int N;
    long long res  = 0;

    cin >> N;

    for(int i = 1; i <= N; ++i)
    {
        if(i % 3 != 0 && i % 5 != 0)
        {
            res += i;
        }
    }

    cout << res << endl;
	return 0;
}

Measured memory_bytes: 3576
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
/*
//#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
*/

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#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 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<<"{";
  for(const T& v:vc) o<<v<<",";
  o<<"}";
  return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
#else
#define show(x) true
#endif

VV<int> G;
int I;
V<ll> a,ans;
void dfs(int v,int p){
  ans[v] = a[I++];
  for(int u:G[v]) if(u!=p){
    dfs(u,v);
  }
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);    //DON'T USE scanf/printf/puts !!
  cout << fixed << setprecision(20);

  int N;
  cin >> N;
  G.resize(N);
  rep(i,N-1){
    int x,y;
    cin>>x>>y;
    x--,y--;
    G[x].pb(y);
    G[y].pb(x);
  }
  a.resize(N);
  rep(i,N) cin >> a[i];
  sort(all(a),greater<ll>());
  ans.resize(N);
  dfs(0,-1);
  ll S = 0;
  rep(i,N) if(i) S+=a[i];
  cout<<S<<endl;
  rep(i,N) cout << ans[i] << " ";
  cout<<endl;
}


Measured memory_bytes: 1536
#include <iostream>
#include <cmath>
#include <string>
#include <vector>

using namespace std;

string S, WORD = "keyence";

bool can(){
  int cnt;
  int diff = S.size() - WORD.size();
  if(diff < 0) return false;

  for(cnt = 0; cnt < 7; cnt++)
    if(S[cnt]!=WORD[cnt]) break;

  for(int back_cnt = 6; back_cnt >= cnt; back_cnt--)
    if(S[back_cnt + diff] != WORD[back_cnt]) return false;

  return true;
}

int main(){
  cin >> S;

  if (can()) cout << "YES" << endl;
  else cout << "NO" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;



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

	int a, b, c;
	cin >> a >> b;
	c = (a + b) % 24;
	cout << c;

	return 0;
}


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

using namespace std;

#define pb push_back
#define mp make_pair
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;

int n, k;
int a[200000];

int main() {
    scanf("%d%d", &n, &k);
    forn(i, n) {
        int x;
        scanf("%d", &x), --x;
        ++a[x];
    }
    sort(a, a + n, greater<int>());
    int ans = 0;
    for (int i = k; i < n; ++i) {
        ans += a[i];
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
	Scanner s = new Scanner(System.in);
	int a = s.nextInt();
	int b = s.nextInt();
	int c = s.nextInt();

	if(a < b && a < c){
	    if(b < c) System.out.println(a+" "+b+" "+c);
	    else System.out.println(a+" "+c+" "+b);
	}
	else if(b < a && b < c){
	    if(a < c) System.out.println(b+" "+a+" "+c);
	    else System.out.println(b+" "+c+" "+a);
	}
	else{
	    if(a < b) System.out.println(c+" "+a+" "+b);
	    else System.out.println(c+" "+b+" "+a);
	}
    }
}



Measured memory_bytes: 26156
#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) (((x) < 0)?-(x):(x))
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

using cat = long long;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int N, M;
	cin >> N >> M;
	bool sw = false;
	if(N < M) swap(N, M), sw = true;
	vector< vector<char> > V(1<<N, vector<char>(1<<M, 0));
	for(int i = 0; i < (1<<M); i++)
		for(int j = 0; j < (1<<M); j++)
			V[i][j] = __builtin_popcount(i&j) & 1;
	for(int i = (1<<M); i < (1<<N); i++)
		for(int j = 0; j < (1<<M); j++)
			V[i][j] = V[i-(1<<M)][j];
	if(sw) {
		vector< vector<char> > VT(1<<M, vector<char>(1<<N, 0));
		for(int i = 0; i < (1<<N); i++)
			for(int j = 0; j < (1<<M); j++)
				VT[j][i] = V[i][j];
		V = VT;
		swap(N, M);
	}
	for(int i = (1<<N)-1; i > 0; i--)
		for(int j = (1<<M)-1; j > 0; j--)
			V[i][j] ^= V[i-1][j] ^ V[i-1][j-1] ^ V[i][j-1];
	for(int i = 1; i < (1<<N); i++) {
		for(int j = 1; j < (1<<M); j++) cout << (int)V[i][j];
		cout << "\n";
	}
	return 0;
}

// look at my code
// my code is amazing


Measured memory_bytes: 2304
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
//#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define MOD 1000000
#define SIZE 1005

int N;
ll num_lose[SIZE];
ll nCm[SIZE][SIZE],dp[SIZE],num_children[SIZE];
vector<int> G[SIZE];

void dfs(int node_id){

	dp[node_id] = 1;

	if(G[node_id].size() == 0){

		return;
	}

	for(int i = 0; i < G[node_id].size(); i++){

		int child = G[node_id][i];
		dfs(child);

		dp[node_id] *= nCm[num_children[node_id]+num_children[child]+1][num_children[child]+1];
		dp[node_id] %= MOD;
		dp[node_id] *= dp[child];
		dp[node_id] %= MOD;

		num_children[node_id] += num_children[child]+1;
	}
}


int main(){

	//コンビネーションを求める
	nCm[0][0] = 1;
	for(ll n = 1; n < SIZE; n++) {
		for (int m = 0; m < SIZE; m++) {
			if(m > 0){
				nCm[n][m] = nCm[n-1][m]+nCm[n-1][m-1];
			}else{ //m == 0
				nCm[n][m] = 1;
			}
			nCm[n][m] %= MOD;
		}
	}

	scanf("%d",&N);

	for(int i = 0; i < N; i++){

		num_lose[i] = 0;
		num_children[i] = 0;
	}

	int from,to;

	for(int i = 0; i < N-1; i++){

		scanf("%d %d",&from,&to);
		from--;
		to--;

		G[from].push_back(to);

		num_lose[to]++;
	}

	int root;

	for(int i = 0; i < N; i++){

		if(num_lose[i] == 0){

			root = i;
			break;
		}
	}

	dfs(root);

	printf("%lld\n",dp[root]);

	return 0;
}



Measured memory_bytes: 11208
#include <iostream>
using namespace std;
int main() {
	int n;
	scanf("%d", &n);
	int sum = 0, m = 1e9;
	for (int i = 0; i < n; i++) {
		int a;
		scanf("%d", &a);
		sum += a;
		if (a % 10) m = min(m, a);
	}
	if (sum % 10)
		printf("%d\n", sum);
	else
		printf("%d\n", max(0, sum - m));
	return 0;
}

Measured memory_bytes: 256
def sum_digit(num):
    sums = 0
    while num != 0:
        sums += num % 10
        num //= 10
    return sums

n, a, b = map(int, input().split())
sums = 0
for i in range(1, n+1):
    if a <= sum_digit(i) <= b:
        sums += i
print(sums)

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

using namespace std;


void solve() {
    int n,k;
    cin >> n >> k;
    vector<int> sum(n+1);
    for (int i = 1; i <= n; i++) {
        int x; cin >> x; x++;
        sum[i] = sum[i-1] + x;
    }
    double mx = 0;
    for (int i = 0; i+k <= n; i++) {
        mx = max(mx, double(sum[i+k]-sum[i]) / 2);
    }
    cout << fixed << setprecision(10) << mx;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n, k;
int a[200000];
int dp[200000];
int main(){
	int i, j;
	scanf("%d %d", &n, &k);
	for(i = 1; i <= n; i++){
		scanf("%d", &a[i]);
	}
	dp[1] = 0;
	for(i = 2; i <= n; i++){
		dp[i] = 0x7fffffff;
		for(j = max(1, i-k); j < i; j++){
			dp[i] = min(dp[i], abs(a[i]-a[j])+dp[j]);
		}
	}
	printf("%d", dp[n]);
	return 0;
}

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

int main() {
  int n;
  	cin>>n;
  vector<string>vec(n);
  vector<char>first(n);
  vector<char>last(n);
  
  for(int i=0;i<n;i++){
    string s;
    	cin>>s;
    int sige=s.size();
    vec[i]=s;
    first[i]=s.at(0);
    last[i]=s.at(sige-1);
  }
  
  int sum=0;
  for(int i=1;i<n;i++){
    if(first[i]!=last[i-1]){
      sum=i;
      cout<<"No"<<endl;
      	break;
    }
    else{
    for(int j=0;j<i;j++){
      if(vec[i]==vec[j]){
        cout<<"No"<<endl;
        sum=i;
        break;
      }
    }
    } 
    }
  if(sum==0) cout<<"Yes"<<endl;
}

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

enum state { YES, MAYBE, NO };

struct box {
    int cont;
    state red;
};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n,m;
    while(cin >> n >> m) {
        vector<box> v(n, {1, NO});
        v[0].red = YES;
        // process queries
        while(m--) {
            int x,y; cin >> x >> y; x--; y--;
            v[x].cont--;
            v[y].cont++;
            
            if(v[x].red == YES) {
                if(v[x].cont == 0) {
                    v[x].red = NO;
                    v[y].red = YES;
                } else {
                    v[x].red = MAYBE;
                    v[y].red = MAYBE;
                }
            } else if(v[x].red == MAYBE) {
                if(v[x].cont == 0) {
                    v[x].red = NO;
                } 
                v[y].red = MAYBE;
            }

        }
        // check if any box contains the red marble for sure
        int cont = 0, sure = 0;
        for(int i = 0; i < n; i++)
            if(v[i].red == YES) {
                sure = 1;
            } else if(v[i].red == MAYBE) {
                cont++;
            }
        cout << (sure? 1 : cont) << '\n';
    }
    return 0;
}

Measured memory_bytes: 1024
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    let n: usize = iter.next().unwrap().parse().unwrap();
    let a: Vec<usize> = (0..n)
        .map(|_| iter.next().unwrap().parse().unwrap())
        .collect();
    let mut l = a.clone();
    let mut r = a.clone();
    for i in 1..n {
        l[i] = std::cmp::max(l[i], l[i - 1]);
    }
    for i in (0..n-1).rev() {
        r[i] = std::cmp::max(r[i], r[i + 1]);
    }
    for i in 0..n {
        let mut ans = 0;
        if i >= 1 {
            ans = std::cmp::max(ans, l[i - 1]);
        }
        if i + 1 < n {
            ans = std::cmp::max(ans, r[i + 1]);
        }
        println!("{}", ans);
    }
}


Measured memory_bytes: 13820
#include <bits/stdc++.h> //AtCoder
//#include <iostream> //Codeforces
//#include <vector> //Codeforces

#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repeq(i,a,b) for(int i=a;i<=b;i++)
#define Vi vector<int>
#define VVi vector<Vi>
#define Vs vector<string>
#define Vc vector<char>
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define cyes cout<<"yes"<<endl
#define cno cout<<"no"<<endl

using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}//最大公約数
int lcm(int a,int b){return a/gcd(a,b)*b;}//最小公倍数

/****************************** START ******************************/

signed main(){
  string S;
  cin >> S;
  int ans = 0;
  if (S == "RRR"){ans = 3;}
  else if (S == "RRS" || S == "SRR"){ans = 2;}
  else if (S == "SSS"){ans = 0;}
  else {ans = 1;}
  
  cout << ans;
}

Measured memory_bytes: 3620
#include <stdio.h>
typedef long long ll;
#define MOD 1000000007
ll modpow(ll a, ll n) {
	if (n == 0)
		return 1;
	if (n % 2 == 1)
		return (a * modpow(a, n - 1) % MOD);
	ll t = modpow(a, n / 2);
	return (t * t % MOD);
}
ll comb(ll n, ll r) {
	if (n < r || n < 0 || r < 0)
		return 0;
	ll x = 1, y = 1;
	for (ll i = n; i > n - r; i--)
		x = x * i % MOD;
	for (ll i = 2; i <= r; i++)
		y = y * i % MOD;
	return (x * modpow(y, MOD - 2) % MOD);
}
int main() {
	int x, y;
	scanf("%d%d", &x, &y);
	if ((x + y) % 3 != 0) {
		printf("0\n");
		return 0;
	}
	int n = (x + y) / 3;
	int r = n * 2 - x;
	// printf("%d %d\n", n, r);
	printf("%lld\n", comb(n, r));
	return 0;
}

Measured memory_bytes: 1732
#include <stdio.h>
#define N 36

typedef struct
{
  char mark;
  char num;
} CARD;

int main()
{
  int n,i,j,minj;
  CARD C1[N],C2[N],a;
  CARD Select[N];
  char ch;

  scanf("%d%c",&n,&ch);

  for(i=0 ; i<n ;i++)
  {
    scanf("%c%c%c",&C1[i].mark,&C1[i].num,&ch);

    C2[i]=C1[i];
  }


/*BubbleSort*/
for(i=0 ; i<n ; i++)
{
  for(j=n-1 ; j>i ; j--)
  {
    if(C1[j].num < C1[j-1].num)
    {
      a=C1[j];
      C1[j]=C1[j-1];
      C1[j-1]=a;
    }
  }
}

/*SelectionSort*/
for(i=0 ; i<n ; i++)
{
  minj = i;
  for(j=i ; j<n ; j++)
  {
    if(C2[j].num < C2[minj].num) minj = j;
  }
    a=C2[i];
    C2[i] =  C2[minj];
    C2[minj] = a;
}


/*print*/
for(i=0 ; i<n-1 ; i++)
{
  printf("%c%c ",C1[i].mark,C1[i].num);
}
printf("%c%c\nStable\n",C1[n-1].mark,C1[n-1].num);

for(i=0 ; i<n-1 ; i++)
{
  printf("%c%c ",C2[i].mark,C2[i].num);
}
printf("%c%c\n",C2[n-1].mark,C2[n-1].num);

for(i=0 ; i<n ; i++)
{
  if(C1[i].mark != C2[i].mark)
  {
    printf("Not stable\n");
    break;
  }
}
if(i==n) printf("Stable\n");

  return 0;
}



Measured memory_bytes: 2108