akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long  

int32_t main(){

        IOS;
        string s,t;
        cin >> s >> t;
        int c=0;
        for(int i=0;i<s.length();i++){
            if(s[i] != t[i])
                c++;
        }
        cout << c << endl;
    
    return 0;
}



Measured memory_bytes: 3888
#include <bits/stdc++.h>
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Weverything"
//#include <boost/multi_array.hpp>
//#include <boost/optional.hpp>
//#include <boost/range/adaptors.hpp>
//#include <boost/range/algorithm.hpp>
//#include <boost/range/irange.hpp>
#pragma clang diagnostic pop

using namespace std;

std::vector<int64_t> solve(int64_t n, std::vector<int64_t> as) {
  std::vector<int64_t> ret;
  ret.reserve(n);
  std::vector<int64_t> bs(as);
  std::sort(bs.rbegin(), bs.rend());
  for (auto&& a : as) {
    if (a == bs.front()) {
      ret.push_back(bs[1]);
    } else {
      ret.push_back(bs[0]);
    }
  }
  return ret;
}

int main() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  int64_t n;
  std::cin >> n;
  std::vector<int64_t> as(n);
  for (int i = 0; i < n; i++) {
    std::cin >> as[i];
  }
  auto const res = solve(n, std::move(as));
  for (int i = 0; i < n; i++) {
    std::cout << res[i] << std::endl;
  }
  return 0;
}


Measured memory_bytes: 4992
// warm heart, wagging tail,and a smile just for you!
//                                                                     ███████████
//                                                                   ███╬╬╬╬╬╬╬╬╬╬███
//                                                                ███╬╬╬╬╬████╬╬╬╬╬╬███
//                                            ███████████       ██╬╬╬╬╬████╬╬████╬╬╬╬╬██
//                                      █████████╬╬╬╬╬████████████╬╬╬╬╬██╬╬╬╬╬╬███╬╬╬╬╬██
//                               ████████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████████╬╬╬╬╬╬██╬╬╬╬╬╬╬██
//                             ████╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████████╬╬╬╬╬╬╬╬╬╬╬██
//                           ███╬╬╬█╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬███╬╬╬╬╬╬╬█████
//                         ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬████████╬╬╬╬╬██
//                       ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬╬╬╬╬╬███
//                     ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬██
//                 ████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████╬╬╬╬╬████
//     █████████████╬╬╬╬╬╬╬╬██╬╬╬╬╬████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬██████
//   ████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬██████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██████╬╬╬╬╬╬╬███████████╬╬╬╬╬╬╬╬██╬╬╬██╬╬╬██
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████╬╬╬╬╬╬╬╬╬╬╬█╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬██
// ██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬▓▓▓▓▓▓╬╬╬████╬╬████╬╬╬╬╬╬╬▓▓▓▓▓▓▓▓██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬███
// ██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██████▓▓▓▓▓▓▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓▓▓▓▓▓▓██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬█████
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████████
//   ███╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██
//       ██████████████  ████╬╬╬╬╬╬███████████████████████████╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████
//                         ███████                           █████  ███████████████████  
//
#include "bits/stdc++.h"
using namespace std;
#define INF (1<<30)
#define LINF (1LL<<60)
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for(int i = (b-1);i>=(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl
#define SP << " " << 
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
#define MSB(x) (63-__builtin_clzll(x))
#define pcnt(x) (__builtin_popcountll(x))
#define parity(i,j) (i&(1LL<<j))
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

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

  double r;
  cin >> r;

  cout << fixed << setprecision(12) << r*2*3.141592 << endl;

  return 0;
}

Measured memory_bytes: 3804
#include<bits/stdc++.h>
#define MOD 1000000007
#define MOD2 1000000006
#define TEMPMOD1 998244353
#define TEMPMOD2 998244352
#define INF 1000000000000000007
#define NEGINF -1000000000000000007
#define vll vector<ll> 
#define vvll vector<vector<ll>>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define plll pair<ll,pll>
#define vpll vector<pll>
using namespace std;
typedef long long int ll;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    ll n;
    cin>>n;
    ll arr1[n+1];
    ll prefix[n+1];
    prefix[0]=0;
    for(ll i=1;i<=n;i++)
    {
        cin>>arr1[i];
        prefix[i]=prefix[i-1]+arr1[i];
    }
    ll dp[n+1][n+1];
    for(ll i=0;i<=n;i++)
    {
        for(ll j=0;j<=n;j++)
        {
            dp[i][j]=0;
        }
    }
    ll pos;
    for(ll len=2;len<=n;len++)
    {
        for(ll j=1;j<=(n+1-len);j++)
        {
            pos=j+len-1;
            dp[j][pos]=INF;
            for(ll k=j;k<=pos;k++)
            {
                dp[j][pos]=min(dp[j][pos],dp[j][k]+dp[k+1][pos]+prefix[pos]-prefix[j-1]);
            }
        }
    }
    cout<<dp[1][n];
    return 0;
}

Measured memory_bytes: 1536
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
using namespace std;
int n,m;
struct f{
	int l,r;
}a[15];
int cmp(f x,f y)
{
	return x.l<y.l;
}
int p()
{
	for(int i=1;i<m;i++)
	if(a[i].l==a[i-1].l&&a[i].r!=a[i-1].r) return 0;
	return 1;
}
int main ()
{
	cin>>n>>m;
	for(int i=0;i<m;i++)
	scanf("%d%d",&a[i].l,&a[i].r);
	sort(a,a+m,cmp);
	int ans[5],sum=0;
	memset(ans,0,sizeof(ans));
	if(p()==0) 
	cout<<"-1"<<endl;
	else if(m==0)
	{
		if(n==1) cout<<"0"<<endl;
		else if(n==2) cout<<"10"<<endl;
		else if(n==3) cout<<"100"<<endl;
	}
	else
	{
		if(a[0].l==2&&n>1) ans[1]=1;
		if(a[0].l==3) ans[1]=1;
		for(int i=0;i<m;i++)
		{
			ans[a[i].l]=a[i].r;
		}
		if(n>1&&ans[1]==0) cout<<"-1"<<endl;
		else
		{
			for(int i=1;i<=n;i++)
				sum=sum*10+ans[i];
				cout<<sum<<endl;
		}
		
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,k,h[100009],dp[100009];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	for(int i=0;i<n;i++) cin>>h[i];
	memset(dp,0x3f,sizeof(dp));
	dp[0]=0;
	for(int i=0;i<n-1;i++)
		for(int j=i+1;j<=min(n-1,i+k);j++)
			dp[j]=min(dp[j],dp[i]+abs(h[i]-h[j]));
	cout<<dp[n-1]<<endl;
	return 0;
}

Measured memory_bytes: 1024
#define _CRT_SECURE_NO_WARNINGS
#pragma target("avx")
#pragma optimize("O3")
#pragma optimize("unroll-loops")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define rep(i,n) for(int i=0;i<(lint)(n);i++)
#define REP(i,n) for(int i=1;i<=(lint)(n);i++)
#define all(V) V.begin(),V.end()
typedef long long lint;
typedef std::pair<lint, lint> P;
constexpr int INF = INT_MAX/2;
constexpr lint LINF = LLONG_MAX/2;
constexpr double eps = 1e-9;
template<class T>
class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};
template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
	if (lhs < rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
	if (lhs > rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
inline lint gcd(lint a, lint b) {
	while (b) {
		lint c = a;
		a = b; b = c % b;
	}
	return a;
}
inline lint lcm(lint a, lint b) {
	return a / gcd(a, b) * b;
}
bool isprime(lint n) {
	if (n == 1)return false;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0)return false;
	}
	return true;
}
lint mypow(lint a, lint b) {
	if (!b)return 1;
	if (b & 1)return mypow(a, b - 1) * a;
	lint memo = mypow(a, b >> 1);
	return memo * memo;
}
lint modpow(lint a, lint b, lint m) {
	if (!b)return 1;
	if (b & 1)return modpow(a, b - 1, m) * a % m;
	lint memo = modpow(a, b >> 1, m);
	return memo * memo % m;
}
template<typename T>
void printArray(std::vector<T>& vec) {
	rep(i, vec.size() - 1)std::cout << vec[i] << " ";
	std::cout << vec.back() << std::endl;
}
template<typename T>
void printArray(T l, T r) {
	T rprev = r;
	rprev--;
	for (T i = l; i != rprev; i++) {
		std::cout << *i << " ";
	}
	std::cout << *rprev << std::endl;
}
std::string to_string(std::vector<int>& vec) {
	std::string res = "[";
	rep(i, vec.size() - 1)res += std::to_string(vec[i]) + ", ";
	res += std::to_string(vec.back()) + "]";
	return res;
}
int a,b,h,m;
int main(){
	std::cin>>a>>b>>h>>m;
	double l=h*30.0+m*0.5,r=m*6;
	double lx=a*cos((l-90)*acos(-1)/180.0),ly=a*sin((l-90)*acos(-1)/180.0);
	double rx=b*cos((r-90)*acos(-1)/180.0),ry=b*sin((r-90)*acos(-1)/180.0);
	printf("%.12lf\n",hypot(lx-rx,ly-ry));
	return 0;
}


Measured memory_bytes: 4056
#include<iostream>
//#include<bits/stdc++.h>
#include<cstdio>
#define ll long long
#define ull unsigned long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#include<cstring>
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
int a[maxn],b[maxn];
int main()
{
    int n ,x;
      ll sum=0,e=0;
     cin>>n;
      rep(i,0,n)
      {
          scanf("%d",&x);
          sum+=x;
          e+=x*x;
      }

       ll ans;
     if(sum%n==0)
       ans=e-sum*sum/n;
     else
     {
         //x=ceil((double)sum/n);
          int bei=sum/n;
         if(sum>=0)
         x=n*(bei+1)-sum>sum-n*bei?floor((double)sum/n):ceil((double)sum/n);
         /*else
            x=n*(bei+1)-sum>sum-n*bei?ceil((double)sum/n):floor((double)sum/n);*/


         ans=n*x*x-2*x*sum+e;
     }
        cout<<ans<<endl;
}


Measured memory_bytes: 3748
#include <iostream>
using namespace std;
int main() {
    int a;
    char op[4];
    a = 0;
    cin >> op;
    for (int i = 0; i < 4; ++i) {
        if (op[i] == '+'){
            a = a + 1;
        } else if (op[i] == '-'){
            a = a - 1;
        }
    }
    cout << a << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int i, n;
		double s, sum, sum2;
		while(true){
			n = sc.nextInt();
			if(n==0) break;
			for(i=0, sum=0, sum2=0; i<n; i++){
				s = sc.nextDouble();
				sum += s;
				sum2 += s*s;
			}
			System.out.println(Math.sqrt(sum2/n-(sum/n)*(sum/n)));
		}
	}
}

Measured memory_bytes: 28640
import sys
sys.setrecursionlimit(10**9)


N, M = map(int, input().split())
to = [[] for _ in range(N)]
count = 0

for _ in range(M):
    A, B = map(lambda x:int(x) - 1, input().split())
    to[A].append(B)
    to[B].append(A)


def dfs(v, to, seen):
    global count
    seen[v] = True
    count += 1
    for nv in to[v]:
        if seen[nv]:
            continue
        dfs(nv, to, seen)


def main():
    global count
    seen = [False] * N
    cnts = []
    for i in range(N):
        if not seen[i]:
            dfs(i, to, seen)
            cnts.append(count)
            count = 0
    
    print(max(cnts))


if __name__ == "__main__":
    main()



Measured memory_bytes: 222040
let rec calc (r,i,n,k) =
	if i==n then r else calc((r+k) mod i,i+1,n,k);;

while true do
	Scanf.sscanf (read_line ()) "%d %d %d" (fun n k m ->
		if n==0 then exit(0) else (print_int((calc(0,1,n,k)+m) mod n+1); print_string "\n")
	) done;;

Measured memory_bytes: 2324
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define x0 gtmshb
#define y0 gtmsub
#define x1 gtmjtjl
#define y1 gtmsf
vector<int> g[100010];
int ans,n,du[100010],pos;
bool on[100010];
void dfs(int p,int fa)
{
	on[p]=0;
	if(g[p].size()>2)on[p]=1;
	for(auto i:g[p])
	if(i!=fa)
	{
		dfs(i,p);
		on[p]|=on[i];
	}
}
int main()
{
	scanf("%d",&n);
	pos=-1;
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);x++;y++;
		g[x].pb(y);
		g[y].pb(x);
		du[x]++;du[y]++;
		if(du[x]>2)pos=x;
		if(du[y]>2)pos=y;
	}
	if(pos==-1)
	{
		puts("1");
		return 0;
	}
	dfs(pos,0);
	//for(int i=1;i<=n;i++)printf("%d\n",on[i]);
	for(int i=1;i<=n;i++)
	if(on[i])
	{
		int num=0;
		for(auto j:g[i])if(!on[j])num++;
		if(num)ans+=num-1;
	}
	printf("%d\n",max(1,ans));
	return 0;
}

Measured memory_bytes: 8960
sa = input()
sb = input()
sc = input()
a,b,c = 0,0,0
turn = "a"
while True:
    if turn == "a":
        if a == len(sa):
            print("A")
            exit()  
        else:
            turn = sa[a] 
            a += 1
    elif turn == "b":
        if b == len(sb):
            print("B")
            exit()
        else:
            turn = sb[b] 
            b += 1
    elif turn == "c":
        if c == len(sc):
            print("C")
            exit()
        else:
            turn = sc[c] 
            c += 1


Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
/* int floorSearch(int arr[], int low,
                int high, int x)
{
    // If low and high cross each other
    if (low > high)
        return -1;

    // If last element is smaller than x
    if (x >= arr[high])
        return high;

    // Find the middle point
    int mid = (low + high) / 2;

    // If middle point is floor.
    if (arr[mid] == x)
        return mid;

    // If x lies between mid-1 and mid
    if (mid > 0 && arr[mid - 1] <= x
        && x < arr[mid])
        return mid - 1;

    // If x is smaller than mid, floor
    // must be in left half.
    if (x < arr[mid])
        return floorSearch(
            arr, low, mid - 1, x);

    // If mid-1 is not floor and x is
    // greater than arr[mid],
    return floorSearch(arr, mid + 1, high, x);
} */
int main()
{
    int n, m, k, csum, temp, cntr, maxc, temp2, index;
    cin >> n;
    cin >> m;
    cin >> k;
    csum = 0;
    vector<int> a;
    vector<int> b;
    for ( int i = 0; i < n; i ++) {
        cin >> temp2;
        temp = csum + temp2;
        if ( temp <= k && temp > 0){
            a.push_back(temp);
            csum = temp;
        }
        else break;
    }
    if ( ! (n == a.size()) ){
        for ( int i = 0; i < n - a.size() - 1; i++) cin >> temp2;
    }
    csum = 0;
    for ( int i = 0; i < m; i++) {
        cin >> temp2;
        temp = csum + temp2;
        if ( temp <= k && temp > 0){
            b.push_back(temp);
            csum = temp;
        }
        else break;
    }
    if ( ! (m == b.size()) ) {
        for ( int i = 0; i < m - b.size() - 1; i++) cin >> temp2;
    }
    maxc = b.size();
    for ( int i = 0; i < a.size(); i++) {
        auto it = lower_bound(b.begin(), b.end(), k - a[i]);
        index = it - b.begin();
        if ( it != b.end() && (*it > k - a[i])) index--;
        if ( it == b.end() ) cntr = b.size() + i + 1;
        else cntr = index + 1 + i + 1;
        if ( cntr > maxc ) maxc = cntr;
    }
    cout << maxc;
    return 0;
}

Measured memory_bytes: 5148
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <functional>
using namespace std;

const int MAX_N = 200005, MOD = 1000000007;
typedef long long i64;

int N, X, Y, fa[MAX_N];
i64 fac[MAX_N], ifac[MAX_N], inv[MAX_N];

vector<int> vec[MAX_N], sz[MAX_N];

void work() {
  for (int i = 1; i <= N; ++i) {
    sort(vec[i].begin(), vec[i].end(), greater<int>());
    if (vec[i].size() <= 1) {
      sz[i] = vector<int>(vec[i].size(), 1);
      continue;
    }
    
    int mn = vec[i].back(), size = 1;
    vec[i].pop_back();

    while (vec[i].size() > 0 && vec[i].back() + mn <= X) {
      size++, vec[i].pop_back();
    }
    
    sz[i] = vector<int>(vec[i].size(), 1);
    sz[i].push_back(size), vec[i].push_back(mn);
  }

  int mn = 1000000001, id = 0, smn = 1000000001, sid = 0;
    
  for (int i = 1; i <= N; ++i) 
    if (vec[i].size() > 0 && vec[i].back() < mn) {
      smn = mn, sid = id;
      mn = vec[i].back(), id = i;
    } else if (vec[i].size() > 0 && vec[i].back() < smn) {
      smn = vec[i].back(), sid = i;
    }

  i64 res = 1;
  int tot = 0;
  
  for (int i = 1; i <= N; ++i)
    if (i != id) {
      int num = 0;
      for (int j = 0; j < vec[i].size(); ++j)
	if (vec[i][j] + mn <= Y) num += sz[i][j];
      res = res * ifac[num] % MOD;
      tot += num;
    } else {
      int num = 0;
      for (int j = 0; j < vec[i].size() - 1; ++j)
	if (vec[i][j] + smn <= Y) num += sz[i][j];
      num += sz[i].back();
      res = res * ifac[num] % MOD;
      tot += num;
    }
  res = res * fac[tot] % MOD;
  printf("%lld\n", (res + MOD) % MOD);
}

int main() {
  scanf("%d%d%d", &N, &X, &Y);
  
  fac[0] = ifac[0] = 1, inv[1] = 1;
  for (int i = 1; i <= N; ++i) fac[i] = fac[i - 1] * i % MOD;
  for (int i = 2; i <= N; ++i) inv[i] = -(MOD / i) * inv[MOD % i] % MOD;
  for (int i = 1; i <= N; ++i) ifac[i] = ifac[i - 1] * inv[i] % MOD;

  for (int i = 1; i <= N; ++i) fa[i] = i;
  
  for (int i = 1, C, W; i <= N; ++i) {
    scanf("%d%d", &C, &W);
    vec[C].push_back(W);
  }

  work();
  
  return 0;
}


Measured memory_bytes: 23808
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <limits>
using namespace std;

struct state {
  int sum_danger;
  int danger;
  int row, col;
  int jump;
  state(int s, int d, int r, int c, int j) : sum_danger(s), danger(d), row(r), col(c), jump(j) {}
  bool operator<(const state& rhs) const
  {
    return sum_danger > rhs.sum_danger;
  }
};

int main()
{
  int N, M;
  while (cin >> N >> M && N != 0) {
    vector<vector<pair<int,int> > > g(N);
    for (int i = 0; i < N; i++) {
      int k;
      cin >> k;
      for (int j = 0; j < k; j++) {
        int c, d;
        cin >> c >> d;
        g[i].push_back(make_pair(c, d));
      }
    }

    vector<vector<vector<int> > > tbl(N);
    for (int i = 0; i < N; i++) {
      tbl[i] = vector<vector<int> >(g[i].size(), vector<int>(M+1, numeric_limits<int>::max()));
    }
    priority_queue<state> q;
    for (int i = 0; i < g[0].size(); i++) {
      q.push(state(0, g[0][i].second, 0, g[0][i].first, 0));
      tbl[0][i][0] = 0;
    }
    for (int i = 0; i < g[1].size(); i++) {
      q.push(state(0, g[1][i].second, 1, g[1][i].first, 1));
      tbl[1][i][1] = 0;
    }

    int ans = numeric_limits<int>::max();
    while (!q.empty()) {
      const state s = q.top();
      q.pop();

      if (s.row+1 == N) {
        ans = min(ans, s.sum_danger);
        continue;
      }
      // normal jump
      for (int i = 0; i < g[s.row+1].size(); i++) {
        const int next_col = g[s.row+1][i].first;
        const int next_danger = g[s.row+1][i].second;
        const int d = s.sum_danger + (s.danger + next_danger) * abs(next_col - s.col);
        if (d < tbl[s.row+1][i][s.jump]) {
          tbl[s.row+1][i][s.jump] = d;
          q.push(state(d, next_danger, s.row+1, next_col, s.jump));
        }
      }
      if (s.jump < M && s.row+2 <= N) {
        if (s.row+2 == N) {
          ans = min(ans, s.sum_danger);
        } else {
          // super jump
          for (int i = 0; i < g[s.row+2].size(); i++) {
            const int next_col = g[s.row+2][i].first;
            const int next_danger = g[s.row+2][i].second;
            const int d = s.sum_danger + (s.danger + next_danger) * abs(next_col - s.col);
            if (d < tbl[s.row+2][i][s.jump+1]) {
              tbl[s.row+2][i][s.jump+1] = d;
              q.push(state(d, next_danger, s.row+2, next_col, s.jump+1));
            }
          }
        }
      }
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 2988
/*input
123456789
*/

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

int main() {
    string s;
    cin >> s;

    int t = 0;
    rep(i, s.size()) t += s[i]-'0';
    if (t%9 == 0) puts("Yes");
    else puts("No"); 
}

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

long long N;
long long A[200005];
int main(){
	cin >> N;
	for(long long i = 0; i < N; i++) {
		cin >> A[i];
	}
	set<long long> aset;
	for(long long i = 0; i < N; i++) {
		if(aset.count(A[i]) != 0) {
			cout << "NO" << endl;
			return 0;
		}
		aset.insert(A[i]);
	}
	cout << "YES" << endl;
}

Measured memory_bytes: 14412
MOD = 10**9+7
MAXN = 5*(10**5)+5
f = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % MOD)
def nCr(n, r, mod=MOD):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

def nPr(n, r, mod=MOD):
    return f[n] * pow(f[n-r], mod-2, mod) % mod

n, m = map(int, input().split())
ans = 0
for k in range(n+1):
    tmp = pow(nPr(m-k, n-k), 2, MOD) * nPr(m, k) * nCr(n,k) % MOD
    if k%2:
        ans -= tmp
    else:
        ans += tmp
ans = (ans + MOD) % MOD
print(ans)

Measured memory_bytes: 122576
#include<stdio.h>
#include<string>
#include<iostream>
#include<math.h>
#include<vector>
#include<set>
#include<algorithm>
#include<list>
using namespace std;

int main() {
	    int x;
	    cin >> x;
		if (x < 1200)  cout << "ABC" << endl;
		else    cout << "ARC" << endl;
	
}


Measured memory_bytes: 256
#include<stdio.h>

int H[500001],n;

void MaxHeapify(int pos){
	int L=pos*2, R=pos*2+1,largest,tmp;

	if(L<=n && H[L]>H[pos])largest=L;
	else largest=pos;

	if(R<=n && H[R]>H[largest])largest=R;

	if(largest!=pos){
		//swap
		tmp=H[pos];
		H[pos]=H[largest];
		H[largest]=tmp;

		MaxHeapify(largest);
	}

	return;
}

int main(){
	int i;	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&H[i]);

	for(i=n/2;i>0;i--)MaxHeapify(i);
	for(i=1;i<=n;i++){
		printf(" %d",H[i]);
	}printf("\n");


	return 0;
}


Measured memory_bytes: 3644
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log,gcd
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')

#Pythonを用いる場合
#numpy 1.18.0, scipy 1.4.1, scikit-learn 0.22, numba 0.47.0, networkx 2.4
 
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

s=list(ss())
k=ii()
ans=""
for i in range(len(s)):
    p=ord(s[i])
    
    if i==len(s)-1:
        k%=122-97+1
        #print(k)
        p+=k
        if p>=123:
            p-=122-97+1
        ans=ans+chr(p)
        #print(p)
    elif s[i]=="a":
        ans=ans+"a"
    elif k>=123-p:
        k-=123-p
        ans=ans+"a"
    else:
        ans=ans+s[i]

print(ans)

Measured memory_bytes: 38328
if __name__ == "__main__":
    N, A, B, C, D = map(int, input().split())
    # if A > B:
    #     A, B = B, A
    rest = N - 2

    for k in range(rest + 1):
        #minus
        l = rest + 1 - k
        left = A + C * k - l * D
        right = A + D * k - l * C
        # print(k, left, right)
        if left <= B and B <= right:
            print("YES")
            exit(0)
    print("NO")


Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define ll long long 
#define ld long double
#define vl vector
#define pb push_back
#define ff first
#define ss second
using namespace std;

int main()
{
    ll n,m,i,a=0,b=0,k,t,j;
    cin>>n;
    if(n%2) cout<<"0";
    else
    {
        a=5*2;
        ll ans=0;
        while(a<=n)
        {
            ans+=n/a;
            a*=5;
        }
        cout<<ans;
    }
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
#define Int int64_t

using namespace std;

int main() {
	Int N;
	cin >> N;
	vector<Int> a(N);
	for (int i = 0; i < N; ++i) { cin >> a[i]; }

	Int ans = 0;
	while (true) {
		Int sum = 0;
		for (int i = 0; i < N; ++i) {
			sum += a[i] / N;
		}
		if (sum == 0) { break; }

		for (int i = 0; i < N; ++i) {
			a[i] += (sum - a[i] / N) - (a[i] / N * N);
		}
		ans += sum;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, start, n) for (ll i = (ll)(start); i < (ll)(n); ++i)
static const ll INFTY = 1L << 62L;
void solver(ll *a, ll n)
{
    ll ans = a[0];
    rep(i, 1, n) ans = gcd(ans, a[i]);
    if (ans != 1)
    {
        cout << "not coprime\n";
        return;
    }
    ll m = 0;
    rep(i, 0, n) m = max(m, a[i]);
    ll d[m + 1];
    bool v[m + 1] = {};
    rep(i, 0, m + 1)
    {
        d[i] = i;
    }
    rep(i, 2, sqrt(m) + 1)
    {
        for (ll j = i * 2; j <= m; j += i)
        {
            if (d[j] == j)
                d[j] = i;
        }
    }
    rep(i, 0, n)
    {
        vector<ll> tmp;
        while (a[i] != 1)
        {
            ll r = d[a[i]];
            if (v[r])
            {
                cout << "setwise coprime\n";
                return;
            }
            tmp.push_back(r);
            a[i] /= r;
        }
        rep(j, 0, tmp.size())
        {
            v[tmp[j]] = true;
        }
    }
    cout << "pairwise coprime\n";
    return;
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    ll a[n];
    rep(i, 0, n) cin >> a[i];
    solver(a, n);
}

Measured memory_bytes: 20212
import * as fs from 'fs'

const input = fs.readFileSync('/dev/stdin', 'utf8');
const args: string[][] = input.split('\n').map(l => l.split(' '));

const [n, k] = args[0].map(x => parseInt(x));

const P = 1000000007;

let tmp = 0;
for (let i = k; i <= n + 1; i++) {
  let max = Math.floor(((n - i + 1) + n) * i / 2);
  let min = Math.floor((0 + (i - 1)) * i / 2);
  tmp = (tmp + (max - min + 1) % P) % P;
}

console.log(tmp);

Measured memory_bytes: 33876
#include <iostream>

using namespace std;

typedef enum enum_WL {win, lose, draw} WL;

bool isWin(char board[][3], char ox)
{
	for (int i=0; i<3; i++) {
		if (board[i][0] == ox && board[i][1] == ox && board[i][2] == ox) return true;
	}
	for (int i=0; i<3; i++) {
		if (board[0][i] == ox && board[1][i] == ox && board[2][i] == ox) return true;
	}
	if (board[0][0] == ox && board[1][1] == ox && board[2][2] == ox) return true;
	if (board[0][2] == ox && board[1][1] == ox && board[2][0] == ox) return true;
	return false;
}

WL win_or_lose(char board[][3], bool turn)
{
	if ( isWin(board, 'o') ) return win;
	else if ( isWin(board, 'x') ) return lose;
	
	for (int i=0; i<3; i++) {
		for (int j=0; j<3; j++) {
			if (board[i][j] != 's') continue;
			board[i][j] = turn ? 'o' : 'x';
			WL wl = win_or_lose(board, !turn);
			if (wl != draw) return wl;
			board[i][j] = 's';
		}
	}
	return draw;
}

int main()
{
	char board[3][3];
	char buf[10];
	
	while ( cin >> buf ) {
		bool turn = true; // true : o's turn
		for (int i=0; i<3; i++) {
			for (int j=0; j<3; j++) {
				board[i][j] = buf[3*i+j];
				if (board[i][j] != 's') turn = !turn;
			}
		}
		switch ( win_or_lose(board, turn) ) {
		case win :  cout << "o"; break;
		case lose : cout << "x"; break;
		case draw : cout << "d"; break;
		}
		cout << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3108
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>
#include <functional>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define EB emplace_back
#define GREATER(T) T, VT<T> greater<T>
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

int main(void) {
    int N, K;
    cin >> N >> K;
    VI h(N);
    REP(i, N) cin >> h[i];

    int ans = 0;
    REP(i, N) ans += h[i] >= K;
    cout << ans << endl;
}


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

constexpr int INF = INT_MAX;

void chmin(int &a, int b){
    a = min(a, b);
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int> > cnt(n+1, vector<int>(m));
    for(int i=0;i<n;i++){
        int a;
        cin >> a;
        a--;
        cnt[i+1][a]++;
        for(int j=0;j<m;j++){
            cnt[i+1][j] += cnt[i][j];
        }
    }
    vector<int> sum(1<<m), dp(1<<m, INF);
    for(int S=1;S<1<<m;S++){
        for(int i=0;i<m;i++){
            if((S>>i)&1) sum[S] += cnt[n][i];
        }
    }
    dp[0] = 0;
    for(int S=1;S<1<<m;S++){
        for(int i=0;i<m;i++){
            if((S>>i)&1){
                int T = S^(1<<i);
                chmin(dp[S], dp[T] + cnt[n][i] - (cnt[sum[S]][i]-cnt[sum[T]][i]));
            }
        }
    }
    cout << dp[(1<<m)-1] << endl;
    return 0;
}



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

int main(){
  int i,j,e,x,y,z,m,min;
  while(1){
    min=1000000;
    cin >> e;
    if(e==0)break;
    for(y = 0; y <=1000; y++){
      for(z = 0; z<=100; z++){
	x=e-y*y-z*z*z;
	m=x+y+z;
	if(min>m && x>=0 && y>=0 && z>=0){
	  //cout << "x" << x << " " << "y" << y << " " << "z" << z << endl;
	  min=m;
	  // cout << "min" << min << endl;
	}
      }
    }
    cout << min << endl;
  }
  return 0;
}

Measured memory_bytes: 1156
#include <stdio.h>

int main(void)
{
	int student[501][501];
	int list[501];
	int n, m;
	int i, j;
	int p1, p2;
	int loop;
	int count;
	
    
    while (1){
    	scanf("%d", &n);
    	scanf("%d", &m);
    	
        if ((n | m) == 0){
            break;
        }
        
        
    	for (i = 0; i <= 500; i++){
    		list[i] = 0;
    		for (j = 0; j <= 500; j++){
    			student[i][j] = 0;
    		}
    	}
    	
    	for (i = 0; i < m; i++){
    		scanf("%d%d", &p1, &p2);
    		student[p1][p2] = 1;
    		student[p2][p1] = 1;
    	}
    	

    	for (i = 2; i <= n; i++){
    		if (student[1][i] == 1){
    			list[i] = 1;
    		}
    	}
    	
    	for (i = 2; i <= n; i++){
    		if (student[1][i] == 1){
    			for (j = 2; j <= n; j++){
    				if (student[i][j] == 1){
  						list[j] = 1;
    				}
    			}
    		}
    	}
    	
    	count = 0;
    	for (i = 2; i <= n; i++){
    		count += list[i];
    	}
    	printf("%d\n", count);
    }
    
	return (0);
}

Measured memory_bytes: 1580
n = int(input())
A = list(map(int, input().split()))

maxim = max(A)
mini = min(A)

if maxim == mini:
    print(0)
    exit()

if abs(maxim) >= abs(mini):
    max_idx = A.index(maxim) + 1
    print(2*n)
    print(max_idx, 1)
    print(max_idx, 1)
    for i in range(1, n):
        print(i, i+1)
        print(i, i+1)

else:
    min_idx = A.index(mini) + 1
    print(2*n)
    print(min_idx, n)
    print(min_idx, n)
    for i in range(n, 1, -1):
        print(i, i-1)
        print(i, i-1)

Measured memory_bytes: 3064
n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
for p in range(3):
    print(sum(abs(x[i] - y[i]) ** (p+1) for i in range(n)) ** (1/(p+1)))
print(max(abs(x[i] - y[i]) for i in range(n)))


Measured memory_bytes: 5648
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int MAXN = 200005;
const int mod = 1e9 + 7;
#define sz(v) ((int)v.size())

struct bit{
	lint tree[MAXN];
	void add(int x, int v){
		while(x < MAXN){
			tree[x] += v;
			x += x & -x;
		}
	}
	int query(int x){
		lint ret = 0;
		while(x){
			ret += tree[x];
			x -= x & -x;
		}
		return ret % mod;
	}
}bit;

int n, m;
pi a[MAXN];
vector<pi> pnt;
lint dp[MAXN];

int main(){
	scanf("%d %d",&n,&m);
	for(int i=0; i<n+m; i++){
		scanf("%d",&a[i].first);
		if(i >= n) a[i].second = 1;
	}
	sort(a, a+n+m);
	int lst = -1;
	for(int i=0; i<n+m; i++){
		if(a[i].second == 1){
			if(~lst){
				for(int j=lst+1; j<i; j++){
					pnt.emplace_back(a[j].first - a[lst].first, a[i].first - a[j].first);
				}
			}
			lst = i;
		}
	}
	sort(pnt.begin(), pnt.end(), [&](const pi &a, const pi &b){
		return pi(a.first, -a.second) < pi(b.first, -b.second);
	});
	pnt.resize(unique(pnt.begin(), pnt.end()) - pnt.begin());
	vector<int> v;
	for(auto &i : pnt) v.push_back(i.second);
	sort(v.begin(), v.end());
	for(auto &i : pnt){
		i.second = lower_bound(v.begin(), v.end(), i.second) - v.begin() + 1;
	}
	lint ret = 1;
	for(int i=0; i<sz(pnt); i++){
		dp[i] = 1 + bit.query(pnt[i].second - 1);
		bit.add(pnt[i].second, dp[i]);
		ret += dp[i];
	}
	cout <<ret % mod << endl;
}


Measured memory_bytes: 5236
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
b.append(0)
ans = 0
for i in range(n):
    beat = min(a[i], b[i])
    a[i] -= beat
    b[i] -= beat
    if i != n:
        beat2 = min(a[i + 1], b[i])
        a[i + 1] -= beat2
    ans += beat + beat2
print(ans)


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

using namespace std;

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

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    each(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    rep(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
    rep(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s; cin >> s;
    const ll n = s.size();
    vector<ll> v(n+1, 0);
    vector<ll> cnt(26, 0);
    rep(i, n) {
        cnt[s[i]-'a']++;
        rep(j, 26) {
            if (cnt[j] % 2 == 1) {
                v[i+1] |= 1LL<<j;
            }
        }
    }
    ll ans = linf;
    map<ll, ll> dp;
    dp[0] = 0;
    rep(i, n) {
        ll x = v[i+1];
        ll a = linf;
        if (dp.count(x) > 0) chmin(a, dp[x]+1);
        rep(j, 26) {
            ll nx = x^(1LL<<j);
            if (dp.count(nx) > 0) {
                chmin(a, dp[nx]+1);
            }
        }
        // cout << i << " " << a << endl;
        if (dp.count(v[i+1]) > 0) {
            chmin(dp[v[i+1]], a);
        }
        else {
            dp[v[i+1]] = a;
        }
        assert(a < linf);
        if (i == n-1) ans = a;
    }
    cout << ans << endl;
}


Measured memory_bytes: 14484
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  int d[N];
  FOR(i,0,N) {
    cin >> d[i];
  }
  sort(d, d+N);
  cout << d[N/2] - d[N/2 - 1] << endl;
}



Measured memory_bytes: 640
#include<iostream>
using namespace std;
int main()
{
  int k;
  cin>>k;
  int a[32]={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};
  cout<<a[k-1];
}

Measured memory_bytes: 256
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, Counter
from sys import exit
import math
# def seni(dp, a)


def main():
    n, a, b, c = getList()
    a = min(a,2)
    b = min(b, 2)
    c = min(c, 2)
    dp = [[0 for i in range(28)] for j in range(n+1)]
    dp[0][a*9 + b * 3 + c] = 1
    for i in range(n):
        q = input().strip()
        if q == "AB":
            # A->B
            for na in range(1, 3):
                for nb in range(3):
                    for nc in range(3):
                        if dp[i][na * 9 + nb * 3 + nc] != 0:
                            dp[i+1][(na-1) * 9 + min(nb+1, 2) * 3 + nc] = ["AB", na * 9 + nb * 3 + nc]

            for nb in range(1, 3):
                for na in range(3):
                    for nc in range(3):
                        if dp[i][na * 9 + nb * 3 + nc] != 0:
                            dp[i+1][min(na+1, 2) * 9 + (nb-1) * 3 + nc] = ["BA", na * 9 + nb * 3 + nc]

        if q == "BC":
            # B C
            for nb in range(1, 3):
                for na in range(3):
                    for nc in range(3):
                        if dp[i][na * 9 + nb * 3 + nc] != 0:
                            dp[i+1][na * 9 + (nb-1) * 3 + min(nc+1, 2)] = ["BC", na * 9 + nb * 3 + nc]

            for nc in range(1, 3):
                for na in range(3):
                    for nb in range(3):
                        if dp[i][na * 9 + nb * 3 + nc] != 0:
                            dp[i+1][na * 9 + min(nb+1, 2) * 3 + nc-1] = ["CB", na * 9 + nb * 3 + nc]

        if q == "AC":
            # A C
            for na in range(1, 3):
                for nb in range(3):
                    for nc in range(3):
                        if dp[i][na * 9 + nb * 3 + nc] != 0:
                            dp[i+1][(na-1) * 9 + nb * 3 + min(nc + 1, 2)] = ["AC", na * 9 + nb * 3 + nc]

            for nc in range(1, 3):
                for na in range(3):
                    for nb in range(3):
                        if dp[i][na * 9 + nb * 3 + nc] != 0:
                            dp[i+1][min(na+1, 2) * 9 + nb * 3 + nc - 1] = ["CA", na * 9 + nb * 3 + nc]


    # for d in dp:
    #     print(d)

    for i, tgt in enumerate(dp[-1]):
        if tgt != 0:
            ans = hukugen(dp, i, n)
            print("Yes")
            for an in ans:
                print(an)

            return


    print("No")

def hukugen(dp, cur, n):
    ans = []
    taiou = {"A": 9, "B": 3, "C":1}
    for i in range(n):
        moji = dp[n-i][cur][0]
        # print(moji, dp[n-i], cur)
        ans.append(moji[1])
        cur =dp[n-i][cur][1]
        # cur -= taiou[moji[1]]

    return (list(reversed(ans)))


if __name__ == "__main__":
    main()

Measured memory_bytes: 312008
//#pragma GCC target("avx2")
#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

template <typename T>
void print(T x) {
    cout << x << "\n";
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REVFOR(i, m, n) for (int i = (n - 1); i >= (m); --i)
#define REP(i, n) FOR(i, 0, n)
#define REVREP(i, n) REVFOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

struct UnionFind {
    vector<int> par;

    UnionFind(int n): par(n, -1) {}
    void init(int n) { par.assign(n, -1); }

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

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

    bool merge(int x, int y) {
        x = root(x); y = root(y);

        if (x == y) return false;

        // merge by size
        // force size of x to be bigger than that of y
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;

        return true;
    }

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

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int n, m;
    cin >> n >> m;

    UnionFind uf(n);

    REP(i, m) {
        int a, b; cin >> a >> b;
        a--; b--;
        uf.merge(a, b);
    }

    ll ans = 0;
    REP(i, n) {
        ans = max(ans, uf.size(i));
    }

    print(ans);


    
}


Measured memory_bytes: 3972
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        for (; ; ) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            if (n == 0 && m == 0) break;

            int[] d = new int[n];
            int[] v = new int[n];

            for (int i = 0; i < n; ++i) {
                d[i] = sc.nextInt() - 1;
                v[i] = sc.nextInt();
            }

            int[] maxRecommendation = new int[m];
            for (int i = 0; i < n; ++i) {
                maxRecommendation[d[i]] = Math.max(maxRecommendation[d[i]], v[i]);
            }

            int result = 0;
            for (int i = 0; i < m; ++i) {
                result += maxRecommendation[i];
            }

            out.println(result);
        }

        sc.close();
        out.close();
    }
}

Measured memory_bytes: 35056
N ,K = map(int, input().split()) 

lst = [i for i in range(N+1)]
rlst = [i for i in range(N,-1,-1)]

P = 10**9 + 7
rlt = 0

mini = sum(lst[:K-1])
maxi = sum(rlst[:K-1])

for i in range(N -K + 2):
  mini += lst[K+i-1]
  maxi += rlst[K+i-1]
  rlt += maxi -mini + 1
  rlt %= P
  
print(rlt)

Measured memory_bytes: 96176
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1000000000
#define LINF 1000000000000000000
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

typedef pair<int, int> P;
typedef pair<long long, long long> LLP;

long long powMod(long long x, long long n, long long m) {
    long long res = 1;
    while (n > 0) {
        if ((n & 1) == 1) res = res * x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return res;
}

int main() {

    int N, K;
    cin >> N >> K;

    long long ans = 0;
    vector<long long> res(K + 1, 0);
    for (int i = K; i >= 1; i--) {
        int count = K / i;
        res[i] = powMod(count, N, MOD) % MOD;
        int j = i + i;
        while (j <= K) {
            res[i] = (res[i] + MOD - res[j]) % MOD;
            j += i;
        }
        ans = (ans + (i * res[i]) % MOD) % MOD;
    }

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

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

typedef long long ll;

int n,ans;
int d[55];

int main(){

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

    cin>>n;
    for(int i=0;i<n;i++){
        cin>>d[i];
        for(int j=0;j<i;j++){
            ans+=d[i]*d[j];
        }
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>
#include<functional>
#include<set>


#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
#define LOWER(a,x) lower_bound(ALL(a), x) - a.begin() - 1;
#define COUNT(a,x)  upper_bound(ALL(a), x) - lower_bound(ALL(a), x);
#define MCOUNT(a,x,y) upper_bound(ALL(a), y) - lower_bound(ALL(a), x);
#define scan(x) scanf("%lld",&x);
#define inf 5555555555555555555
#define mod 1000000007
#define pi 3.14159265358979323846
#define pb push_back
#define F first
#define S second
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef map<ll, ll> MAP;
typedef set<ll> SET;
ll n = 0, m = 0, ans = 0, sum = 0, cnt = 0, tmp = 0, ma = 0, mi = 0;
string s;
bool flag, ok;
ll dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
ll ddx[9] = { 1,-1,0,0,1,1,-1,-1,0 }, ddy[9] = { 0,0,1,-1,1,-1,1,-1,0 };
#pragma endregion
#define MAX 111111


int main(void) {
  string s1, s2, s3, s4, ss;
  ll le;
  cin >> s;
  le = s.length();
  s1 = "dream";
  s2 = "dreamer";
  s3 = "erase";
  s4 = "eraser";
  while (1) {
	if (le < 4) break;
	if (le >= 7) {
	  ss = s.substr(le - 7, 7);
	  if (ss == s2 ) {
		le -= 7;
		continue;
	  }
	}

	if (le >= 6) {
	  ss = s.substr(le - 6, 6);
	  if (ss == s4) {
		le -= 6;
		continue;
	  }
	}

	if (le >= 5) {
	  ss = s.substr(le - 5, 5);
	  if (ss == s1 || ss == s3) {
		le -= 5;
		continue;
	  }
	}

	break;
  }

  if (le == 0) {
	cout << "YES" << endl;
  }
  else {
	cout << "NO" << endl;
  }

  return 0;
}

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


int main(){
    //input
    string s;
  	cin >> s;
    vector<int> v(s.size(),0);

    //convert
    for (int i = 0; i < s.size(); i++){
        if (s[i] == 'A' || s[i] == 'T' || s[i] == 'C' || s[i] == 'G'){
            v[i] = 1;
        }
        else{
            v[i] = 0;
        }
    }

    // check v
    int temp = 0;
    int ans = 0;
    for (int i =0; i < v.size(); i++){
        temp = 0;
        for (int j = i; j < v.size(); j++){
            if (v[j] == 1){
                temp++;
            }
            else{
                break;
            }
        }
        ans = max(ans,temp);
    }
    cout << ans << endl;
}



Measured memory_bytes: 256