akhauriyash/Code-Regression huggingface dataset:
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <iterator>
#include <cmath>
#include <deque>
using namespace std;

vector<vector<pair<int, int>>> g;
vector<int> color;
vector<bool> used;
int k = 0, kmax = 0;

void dfs(int v, int p, int colFrom)
{
    
    int k = 1;
    for (auto to : g[v]) 
        if (to.first != p) {
            while (k == colFrom)
                ++k;
            kmax = max(kmax, k);
            color[to.second] = k;
            dfs(to.first, v, k);
            ++k;
        }
}

int main()
{
    {
        if (fopen("input.txt", "r")) {
            freopen("input.txt", "r", stdin);
            freopen("output.txt", "w", stdout);
        }
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    }

    int n;
    cin >> n;
    g.resize(n + 1);
    for (int i = 0; i != n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back({ v, i });
        g[v].push_back({ u, i });
    }
    color.resize(n);
    used.resize(n + 1);
    dfs(1, 1, 0);
    cout << kmax << '\n';
    for (int i = 0; i != n - 1; ++i)
        cout << color[i] << '\n';
    return 0;
}

Measured memory_bytes: 8320
#include <iostream>                                                                                 
using namespace std;                                                                                
int main(){                                                                                         
  int n;                                                                                            
  cin >> n;                                                                                         
  int* a = new int[n];                                                                              
  for (int i=0; i<n; i++){                                                                          
    cin >> a[i];                                                                                    
  }                                                                                                 
  for (int i=0;i<n;i++){                                                                            
    cout << a[n-i-1];                                                                               
    if (i != n-1)                                                                                   
      cout << " ";                                                                                  
  }                                                                                                 
  cout << endl;                                                                                     
}                                                                                                   
                                                                                                    
                                                                                                    
                                                                                                    
                                                                                                    
                                                                                                    
                                                                                                    
                                                                                                    
                                                                                                    
                                                              


Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define ALL(c) (c).begin(), (c).end()
using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e6+6;


int main(){
//	freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);//cout.precision(12);cout<<fixed;
	
	int n, m;
	
	set<int> s;
	cin>>n;
	while(n--){
		int x;
		cin>>x;
		if(s.count(x)) s.erase(x); else s.insert(x);
	}
	cout<<s.size()<<endl;
	
	return 0;
}


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

int main() {
 int n,k,cnt=0;
  cin >> n >> k;
  int m=1;
  while(cnt!=n){
    if(m*2<=m+k){
    m*=2;
    }
    else{
    m+=k;
    }
    cnt++;
  }

  cout << m << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll M = 1e9+7;


int main() {
  int h,w;
  cin>>h>>w;
  ll dp[h+1][w+1];
  for(int i=0;i<h+1;i++) dp[i][0]=0;
  for(int i=0;i<w+1;i++) dp[0][i]=0;
  char ch;
  for(int i=1;i<h+1;i++) {
  	for(int j=1;j<w+1;j++) {
      cin>>ch;
      if(ch=='.') {
      	dp[i][j]=(dp[i-1][j]+dp[i][j-1])%M;
      }
      else dp[i][j]=0;
     if(i==1&&j==1) dp[i][j]=1;
    }
  }
  ll res = dp[h][w]%M ;
  cout<<res<<endl;
}

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

priority_queue<pair<int, bool> > q;

int main(){
    int n,h,i,a,b;
    scanf("%d%d",&n,&h);
    for(i=1;i<=n;i++){
        scanf("%d%d",&a,&b);
        q.push(make_pair(a,1));
        q.push(make_pair(b,0));
    }
    int ans=0;
    while(h>0){
        int attack=q.top().first;
        bool multi_attack=q.top().second;
        q.pop();
        if(multi_attack){
            int cnt=h/attack;
            if(h%attack)cnt++;
            h-=attack*cnt;
            ans+=cnt;
        }
        else{
            h-=attack;
            ans++;
        }
    }
    printf("%d\n", ans);
    return 0;
}

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

int main(){
    ll n;
    cin>>n;
    int k;
    k = 1;
    rep(i,n){
        if (n>pow(26,i+1)){
            n -= pow(26,i+1);
            k++;
        }
        else break;
    }
    string ans;
    n--;
    rep(i,k){
        if(n==0) ans += 'a';
        else{
        ans += 'a'+n%26;
        n /= 26;
        }
    }
    reverse(ans.begin(),ans.end());
    cout<<ans<<endl;
}

Measured memory_bytes: 4108
#include <stdio.h>

int main(int argc, char **argv){
	int w,h,x,y,r;
	
	scanf("%d %d %d %d %d",&w, &h, &x, &y, &r);
	
	if( x - r >= 0 && y - r >= 0 && x + r <= w && y + r <= h ){
		printf("Yes\n");
	} else {
		printf("No\n");
	}
	
	return 0;
}

Measured memory_bytes: 584
#include<bits/stdc++.h>
using namespace std;
typedef long long unsigned int ll;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i, start, end) for(int i = start; i < (int)(end); ++i)

int main(){
    int x, y, z;
    cin >> x >> y >> z;
    cout << z << " "  << x  << " " << y << endl;
    return 0;
}

Measured memory_bytes: 256
// Think twice, Code once
// 1SAC
#include<bits/stdc++.h>
using namespace std;
 
/*============================ DEBUGGING =============================*/
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define deb(x...)
#endif
/*============================= DEFINES ==============================*/
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define FIO {ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);}
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
/*============================== TYPEDEFS ============================*/
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef long double ld;
/*============================ START FROM HERE =======================*/
 
int main(){
	FIO
	
	int n;cin >> n;
	string s;cin >> s;
	int ans = 0; 
	forn(i, s.size() - 2){
		if(s[i]=='A' && s[i+1]=='B' && s[i+2]=='C')ans++;
	}
	cout << ans;
	return 0;
}


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

int main() {
  int L, R;
  cin >> L >> R;
  if (R - L >= 2018) cout << 0 << endl;
  else {
    int l = L % 2019, r = R % 2019;
    if (l > r) cout << 0 << endl;
    else {
      int ans = 1000000000;
      for (int i = l; i < r; i++) {
        for (int j = i + 1; j <= r; j++) {
          ans = min(ans, (i * j) % 2019);
        }
      }
      cout << ans << endl;
    }
  }
}

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

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int MOD = 1000000007;
const int INF = 2147483647;

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//myfuncs
//素数判定
template<class T> inline T isPrime(T x) {
	bool ret = true;
	if (x < 2) {
		ret = false;
	}
	for (LL i = 2; i <= sqrt(x); i++) {
		if (x%i == 0) {
			ret = false;
		}
	}
	return ret;
}

//Union FInd
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

//main code

bool comp(const PII &l, const PII &r) {
    return l.second < r.second;
}

int main(int argc, char const* argv[])
{
    int n,m;
    cin >> n >> m;
    vector<PII> v;
    LL ans = 0;
    for (int i = 0; i < m; i++) {
        int a,b;
        cin >> a >> b;
        v.push_back(make_pair(a,b));
    }
    sort(v.begin(),v.end(),comp);
    int br = 0;
    for (auto&& var : v) {
        if (br < var.first) {
            ans++;
            br = var.second - 1;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
int dep[55],par[55],f[55],s[55],l[55],p[55],cnt;
long long pw[55];
vector<int> v[55],d[2];
void pre(int node,int p)
{
	par[node]=p;
	dep[node]=dep[p]+1;
	for (int u:v[node])
	{
		if (u!=p)
		pre(u,node);
	}
}
int lca(int u,int v)
{
	while (u!=v)
	{
		if (dep[u]>dep[v])
		u=par[u];
		else
		v=par[v];
	}
	return u;
}
int find(int x)
{
	if (p[x]!=x)
	p[x]=find(p[x]);
	return p[x];
}
void Union(int x,int y)
{
	x=find(x);
	y=find(y);
	if (x!=y)
	p[x]=y;
}
void update(int u,int v)
{
	u=find(u);
	while (dep[u]>dep[v])
	{
		cnt--;
		Union(u,par[u]);
		u=find(u);
	}
}
int main()
{
	int n,m;
	scanf("%d",&n);
	pw[0]=1;
	for (int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		v[a].push_back(b);
		v[b].push_back(a);
		pw[i]=2*pw[i-1];
	}
	pre(1,0);
	scanf("%d",&m);
	for (int i=0;i<m;i++)
	{
		scanf("%d%d",&f[i],&s[i]);
		l[i]=lca(f[i],s[i]);
	}
	long long ans=0;
	for (int mask=0;mask<(1<<m);mask++)
	{
		cnt=n-1;
		for (int i=1;i<=n;i++)
		p[i]=i;
		for (int i=0;i<m;i++)
		{
			if (mask&(1<<i))
			{
				update(f[i],l[i]);
				update(s[i],l[i]);
			}
		}
		d[__builtin_popcount(mask)%2].push_back(cnt);
	}
	while (!d[0].empty() || !d[1].empty())
	{
		if (ans<0 || d[1].empty())
		{
			ans+=pw[d[0].back()];
			d[0].pop_back();
		}
		else
		{
			ans-=pw[d[1].back()];
			d[1].pop_back();
		}
	}
	printf("%lld",ans);
}

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

#define ll long long
#define mod 1000000007
#define MAXN 100010

using namespace std;

int h, w, n;

int a[MAXN];

int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	scanf("%d%d%d", &h, &w, &n);
	
	int ans = 0;
	int m = max(h, w);
	if (n % m == 0) cout << n / m << endl;
	else cout << n / m + 1 << endl;
	return 0;
}

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

int main() {
    string s; int w, h, x, y, r; cin >> w >> h >> x >> y >> r;
    if (r<=x && x<=w-r && r<=y && y<=h-r) s = "Yes";
    else s = "No";
    cout << s << endl;
}

Measured memory_bytes: 3204
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define rep(i,n) for(int i=0;(i)<(n);(i)++)
typedef struct{
    int len;
    int dir;
}Line;
Line line[10];
int cal(int d,int m,Line x[10]){
    int j,flag=1;
    for(j=0;j<m-1;j++){
        if(x[j].len!=line[j].len||(x[j].dir+d)%4!=line[j].dir){
            flag=0; break;}
    }if(flag) return 1;
    for(j=0;j<m-1;j++){
        if(x[m-2-j].len!=line[j].len||(x[m-2-j].dir+2+d)%4!=line[j].dir)
            return 0;
    }
    return 2;
}
int main(void){
    while(1){
        int n,m1,cnt=0;
        scanf("%d",&n);
        if(n==0) break;
        int y,x;
        scanf("%d",&m1);
        scanf("%d%d",&x,&y);
        for(int i=0;i<m1-1;i++){
            int z,w;
            scanf("%d%d",&z,&w);
            if(x==z){
                line[i].len=abs(y-w);
                line[i].dir=(y<w?2:0);
            }
            else{
                line[i].len=abs(x-z);
                line[i].dir=(x<z?1:3);
            }
            x=z,y=w;
        }
        //rep(i,m-1) printf("len:%d dir:%d\n",line[i].len,line[i].dir); puts("");
        //printf("-------------------\n");
        int flag=1;
        for(int i=0;i<n;i++){
            int x,y,m2; Line tmp[10];
            scanf("%d",&m2);
            scanf("%d%d",&x,&y);
            for(int j=0;j<m2-1;j++){
                int z,w;
                scanf("%d%d",&z,&w);
                if(x==z){
                    tmp[j].len=abs(y-w);
                    tmp[j].dir=(y<w?2:0);
                }
                else{
                    tmp[j].len=abs(x-z);
                    tmp[j].dir=(x<z?1:3);
                }
                x=z,y=w;
            }
            if(m1!=m2) continue;
            //rep(k,m-1) printf("len:%d dir:%d\n",tmp[k].len,tmp[k].dir); puts("");
            for(int d=0;d<4;d++){
                if(cal(d,m2,tmp)){
                    printf("%d\n",i+1);
                    break;}
            }
        }
        if(flag) printf("+++++\n");
    }
}



Measured memory_bytes: 2100
#include <iostream>

void selectoinSort(int* a, int n) {
    int swap_count{};
    for(auto i=0; i<n; i++) {
        int minj{i};
        for(auto j=i; j<n; j++) {
            minj = (a[j]<a[minj]) ? j : minj;
        }
        std::swap(a[i], a[minj]);
        swap_count += (i!=minj) ? 1 : 0;
    }
    for(auto i=0; i<n; i++) {
        std::cout << a[i] << ((i<n-1) ? " " : "\n");
    }
    std::cout << swap_count << std::endl;
}

int main() {
    int n{}; std::cin >> n;
    int a[n]; for(auto i=0; i<n; i++) std::cin >> a[i];
    selectoinSort(a, n);
}



Measured memory_bytes: 3108
from itertools import permutations

N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))
a, b = 0, 0

for i, l in enumerate(permutations(range(1, N+1))):
    if l==P: 
        a = i
    if l==Q:
        b = i

print(abs(a-b))

Measured memory_bytes: 3064
open System

// prelude
let readStr () = stdin.ReadLine()

let read f () = readStr() |> f
let reads f () = readStr().Split() |> Array.map f

let pair = function
| [|a; b|] -> (a, b)
| _ -> failwith "owatta"

let triple = function
| [|a; b; c|] -> (a, b, c)
| _ -> failwith "owatta"

let readPair f g () =
  let (a,b) = readStr().Split() |> pair
  (f a, g b)

let readTriple f g h () =
  let (a,b,c) = readStr().Split() |> triple
  (f a, g b, h c)

let inc n = n + 1
let dec n = n - 1

let inline flip f a b = f b a
let rec fix f = fun x -> (f (fix f)) x

module Option =
  let getOr defaultValue = function
  | Some x -> x
  | None -> defaultValue

module Array =
  let modify (arr: _ []) i f =
    arr.[i] <- f arr.[i]

module Array2D =
  let modify (arr: _ [,]) i j f =
    arr.[i, j] <- f arr.[i, j]

// start
let (N,K) = readPair int int ()
let snk = Array.create N false

for i in 0..(K-1) do
  let d = read int ()
  reads int () |> Array.iter (fun x -> snk.[x-1] <- true)

snk
|> Array.fold (fun sum x -> sum + if x then 0 else 1) 0
|> printfn "%d"

Measured memory_bytes: 30284
#include <iostream>

using namespace std;

int main() {
    for (int i = 1; i < 10; ++i) {
        for (int j = 1; j < 10 ; ++j) {
            cout << i;
            cout << 'x';
            cout << j;
            cout << '=';
            cout << i * j;
            cout << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1116
def main():
    from collections import Counter
    N, P = (int(i) for i in input().split())
    S = [int(s) for s in input()]

    ans = 0
    if P == 5 or P == 2:
        for i, s in enumerate(S, start=1):
            # j文字取る
            if s % P == 0:
                ans += i
    else:
        acc = [0]*(N+1)
        d = 1
        for i, s in enumerate(S[::-1], start=1):
            # print(i, s)
            acc[i] = (s * d + acc[i-1]) % P
            d *= 10
            d %= P
        c = Counter(acc)
        # print(acc, c)
        ans = sum(v*(v-1)//2 for v in c.values())
    print(ans)


if __name__ == '__main__':
    main()


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

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void cmpmax(T& reference, T value) {
	reference = max(reference, value);
}

template<typename T>
void cmpmin(T& reference, T value) {
	reference = min(reference, value);
}

const ll mod = 1000000007;

static const ll INF = 1e15;

int n;
vector<vector<int>> graph;
vector<vector<ll>> dp;
const int white = 0;
const int black = 1;

void dfs(int c, int from) {
	ll w = 1;
	ll b = 1;
	for (auto p : graph[c]) {
		if (p == from) continue;
		dfs(p, c);
		w *= (dp[p][white] + dp[p][black]);
		b *= dp[p][white];
		w %= mod;
		b %= mod;
	}
	dp[c][white] = w;
	dp[c][black] = b;
}

int main() {
	cin >> n;
	graph.resize(n);
	rep(i, n-1) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	int leaf = 0;
	rep(i, n) {
		if (graph[i].size() == 1) {
			leaf = i;
			break;
		}
	}
	dp.resize(n, vector<ll>(2, 0));
	dfs(leaf, -1);	
	auto sum = dp[leaf][white] + dp[leaf][black];
	sum %= mod;
	cout << sum << endl;
	return 0;
}
	


Measured memory_bytes: 18944
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cctype>
#include<climits>
#include<string>
#include<bitset>
#include<cfloat>
#include<iomanip>
#include<numeric>

//#define int long long
#define repi(i,start,end) for(int (i)=(start),TemPNuM=(int)(end);(i)<TemPNuM;++(i))
#define rep(i,end) repi((i),0,(end))
#define rfor(x,v) for(auto& (x) : (v))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fsort(v,lambda) sort(all((v)),(lambda))
#define vin(v) rep(i,(v).size())cin >> (v)[i];
#define vpin(v) rep(i,(v).size())cin>>v[i].first>>v[i].second

using namespace std;
using ll =  long long;
using pint =  pair<int,int>;
using vint = vector<int>;
using vvint = vector<vint>;
using vpint = vector<pint>;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class T>void put_double(T a){if(cout.precision()!=12)cout<<setprecision(12);cout<<a<<endl;}
template<class T>void print(T a){cout << a << endl;}
//lambda: [](int x, int y){return x<y;}

signed main(void) {
    int n, m; cin >> n >> m;
    int once = 100 * (n - m) + 1900 * m;
    int ans = once * (int)pow(2, m);
    print(ans);

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define lli long long int
#define rep(i,a,b)	for(i=a;i<b;i++)
#define M 1000000007
#define vll vector<long long int>
#define mll map<long long int,long long int>
#define pi 3.1415926535897932384626433832795028841971
using namespace std;

lli mpower(lli a,lli b,lli m)
{
	if(b==0)	return 1;
	if(b==1)	return a%m;
	lli res=1;
	a=a%m;
	while(b){
		if(b&1){
			res=(res*a)%m;
		}
		a=((a%m)*(a%m))%m;
		b>>=1;
	}
	return res;
}

long long int spf[1000005];
void SPF()
{
	long long int i,j;
	spf[0]=1;
	for(i=1;i<=1000004;i++)	spf[i]=i;
	for(i=2;i<=1000004;i++){
		if(spf[i]==i){
			for(j=i*i;j<=1000004;j+=i){
				spf[j]=min(i,spf[j]);
			}
		}
	}
}

mll ma;
mll::iterator et;
lli mlcm(vll v,lli n)
{
	lli i,num,factor,ans=1;
	for(i=0;i<n;i++){
		num=v[i];
		mll temp;
		mll::iterator it;
		while(num>1){
			temp[spf[num]]++;
			num/=spf[num];
		}
		for(it=temp.begin();it!=temp.end();++it){
			ma[it->first]=max(ma[it->first],it->second);
		}
	}
	for(et=ma.begin();et!=ma.end();++et){
		ans=(ans*mpower(et->first,et->second,M))%M;
	}
	return ans;
}

lli imod(lli a,lli m)
{
    lli g;
    return mpower(a,m-2,m);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	char ch,ch1,ch2;
	string s1,s2,s3;
    lli i,j,k,s,a,b,t,c,n,m,sum=0,ans=0,temp;
    cin >> n;
    vll v(n);
    rep(i,0,n)	cin >> v[i];
    SPF();
    a=mlcm(v,n);
    for(i=0;i<n;i++){
    	temp=a*imod(v[i],M);
    	ans+=(temp);
    	ans%=M;
	}
	cout << ans << endl;
    
	
	
    
    
    return 0;
}


Measured memory_bytes: 8832
#include<bits/stdc++.h>
using namespace std;
long long int N,M,K,T,H,W,L,R;
int main()
{
	cin>>N>>M>>K;
	N=abs(N);
	long long int num=N/K;
	if(num>=M)
	{
		cout<<N-M*K;
		return 0;
	}
	H=N%K;
	if((M-num)&1)
	{
		cout<<K-H;
	}
	else
	{
		cout<<H;
		
	}
}

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

int main() {

    int n,p;

    long long int ans = 0;

    cin >> n >> p;

    int a[n+1];

    for(int i=0;i<n;i++){
        cin >> a[i];
    }

    long long int dp[51][2];

    dp[0][0] = 1;
    dp[0][1] = 0;
    for(int i=0;i<n;i++){

        if(a[i]%2 == 0){
            dp[i+1][0] = 2 * dp[i][0];
            dp[i+1][1] = 2 * dp[i][1];
        }
        else{
            dp[i+1][0] = dp[i][0] + dp[i][1];
            dp[i+1][1] = dp[i][0] + dp[i][1];
        }

    }

    cout << dp[n][p] << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, M;
	cin >> N >> M;
	vector<int> C(M, 0);
	int res = 0;
	int K;
	int A;
	for (int i = 0; i < N; i++) {
		cin >> K;
		for (int j = 0; j < K; j++) {
			cin >> A;
			C[A - 1]++;
		}
	}
	for (int i = 0; i < M; i++) {
		if (C[i] == N)res++;
	}
	cout << res << endl;
}

Measured memory_bytes: 256
n = gets.to_i
ss = gets.chomp.chars
ans = ss.count("R") * ss.count("G") * ss.count("B")

0.upto(n) do |i|
  j = 1

  (1..).each do |j|
    k = i + 2 * j
    break unless k < n

    a = ss[i]
    b = ss[i + j]
    c = ss[k]
    ans -= 1 if a != b && b != c && c != a
  end
end

puts ans


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


int main(){
  ll n,k;
  cin>>n>>k;
  if(n==k){
    cout<<0<<endl;
  }else if(n<k){
    cout<<min(n,k-n)<<endl;
  }else{
    cout<<min(n%k,k-n%k)<<endl;
    
     }
}

Measured memory_bytes: 256
N, M = map(int, input().split())
# 全通り
ary = []
for i in range(2 ** N):
    ary.append((bin(i)[2:].zfill(N)))
# 残り入力
ary2 = []
for i in range(M):
    kS = list(map(int, input().split()))
    ary2.append(kS)
P = list(map(int, input().split()))
# 解く
cnt = 0
for i in range(2 ** N):
    flg = 0
    for j in range(M):
        tot = 0
        for k in range(len(ary2[j])-1):
            tot += int(ary[i][ary2[j][k+1]-1])
        if tot % 2 != P[j]:
            flg = 1
            break
    if flg == 0:
        cnt += 1
print(cnt)

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

int main() {

  int n , c ,p , w , g , y ;
    cin >> n;
    string s ;
    c = 0;
    p = 0;
    w = 0;
    g = 0;
    y = 0;
    
    for (int j = 0; j < n; j++) {
       
      cin  >> s ;
      
      if (s == "P" && p == 0){
         c ++;
         p = 1 ;
      }
   
      if (s == "W" && w ==0){
         c  ++ ;
         w = 1 ;
      }
      
      if (s == "G" && g == 0){
         c ++;
         g = 1 ;
     } 
      if (s == "Y" && y == 0){
         c ++;
         y = 1 ;
     }
     
    }
  
    if(c==3){
        cout << "Three"<< endl;
    }
    else if(c==4){
        cout << "Four" << endl;
   
  }
  }

Measured memory_bytes: 3616
from math import sqrt
N, D = map(int, input().split())
xs = [list(map(int, input().split())) for i in range(N)]

ans = 0
for i in range(N):
    for j in range(i+1, N):
        dist_sum = sum([ (xs[i][k] - xs[j][k])**2 for k in range(D)])
        dist = sqrt(dist_sum)
        if dist % 1 == 0:
            ans += 1
print(ans)

Measured memory_bytes: 3188
#include<bits/stdc++.h>
typedef long long     ll;
#define fast          ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define last          freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define fr            first
#define sc            second
#define lcm(a,b)      (a*b)/__gcd(a,b)
#define com(i,n)      for(int i=0;i<n;i++)
#define dom(i,n)      for(int i=1;i<=n;i++)
#define mom(i,n)      for(int i=n;i>=0;i--)
#define sortI(a,n)    sort(a,a+n)
#define sortD(a,n)    sort(a,a+n,greater<int>())
#define sortvi(a)     sort(a.begin(),a.end())
#define sortvd(a)     sort(a.begin(),a.end(),greater<int>())
#define sumall(a,x)   accumulate(a.begin(),a.end(),x)
#define pi            3.14159265358979323846264338327950
#define endl          '\n'
using namespace std;
int main()
{
     double x,y,n,d;
     cin>>n>>d;
     int cnt=0;
     com(i,n)
     {
          cin>>x>>y;
          if(x*x+y*y<=d*d)
               cnt++;
     }
     cout << cnt << endl;
}



Measured memory_bytes: 3692
#include<bits/stdc++.h>
using namespace std;
int prime[303]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,
149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,
317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,
509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,
719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,
937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,
1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,
1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,
1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,
1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,
1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,1993,1997,1999},n,k,cnt[303],xx[10003];
long long C(long long x,long long y){
	y=min(y,x-y);
	long long ans=1;
	for(int i=0;i<y;i++)xx[i]=x-i;
	for(int i=1;i<=y;i++){
		long long tmp=i;
		for(long long xxx=0;xxx<303;xxx++)
			while(tmp%prime[xxx]==0)
				tmp/=prime[xxx],
				cnt[xxx]++;
	}
	for(long long i=0;i<y;i++)
		for(long long xxx=0;xxx<303;xxx++)
			while(cnt[xxx]&&xx[i]%prime[xxx]==0)
				cnt[xxx]--,
				xx[i]/=prime[xxx];
	for(long long i=0;i<y;i++)ans=(ans*xx[i])%1000000007;
	return ans;
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=k;i++)
		if(i+1<=n-k+2)
			printf("%lld\n",(C(k-1,i-1)*C(n-k+1,i))%1000000007);
		else
			printf("0\n");
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define  IOS ios_base::sync_with_stdio(false),cin.tie(NULL)

bool isvalid(int a , int b, int c)
{
	set<int>s;
	s.insert(a);
	s.insert(b);
	s.insert(c);
	if (s.size() == 3)return true;

	return false;
}


int main()
{
	IOS;
	int n;
	int c = 0;
	cin >> n;
	vector<int>a(n);
	for (int i = 0; i < n; i++)cin >> a[i];

	sort(a.rbegin(), a.rend());

	for (int i = 0; i <= n - 3; i++)
		for (int j = i + 1; j <= n - 2; j++)
			for (int k = j + 1; k <= n - 1; k++) {
				if (isvalid(a[i], a[j], a[k])) {
					if (a[j] + a[k] > a[i])c++;

				}
			}

	cout << c << "\n";
}

Measured memory_bytes: 3644
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100;
const int MAX_NN = MAX_N * MAX_N;

/* typedef */

typedef vector<int> vi;

/* global variables */

int n, nn;
int flds[MAX_NN], ids[MAX_NN];

/* subroutines */

/* main */

int main() {
  for (;;) {
    cin >> n;
    if (n == 0) break;
    nn = n * n;

    for (int pos = 0; pos < nn; pos++) {
      int x, y;
      cin >> x >> y;
      flds[pos] = y * n + x;
    }

    memset(ids, 0, sizeof(ids));

    int id = 0;
    vi fs;

    for (int pos0 = 0; pos0 < nn; pos0++) {
      if (ids[pos0] > 0) continue;

      ids[pos0] = ++id;
      fs.clear();
      fs.push_back(pos0);
      
      int pos = flds[pos0];
      while (! ids[pos]) {
	ids[pos] = id;
	fs.push_back(pos);
	pos = flds[pos];
      }

      int id0 = ids[pos];
      if (id0 != id) {
	for (vi::iterator vit = fs.begin(); vit != fs.end(); vit++)
	  ids[*vit] = id0;
	--id;
      }
    }

    cout << id << endl;
  }

  return 0;
}

Measured memory_bytes: 1300
import sys

def encode(n:int) -> str:
  if n == 0:
      return '0'

  if n == 1:
      return '1'

  if n % 2 == 1:
      ans = '{}1'.format(encode((n-1) // (-2)))
      sys.stderr.write('{} for {}'.format(ans, n))
      sys.stderr.write('\n')
      return ans

  if n % 2 == 0:
      ans = '{}0'.format(encode(n // (-2)))
      sys.stderr.write('{} for {}'.format(ans, n))
      sys.stderr.write('\n')

      return ans

n = int(input())
ans = encode(n)
print(ans)

  


Measured memory_bytes: 3064
#include<iostream>

using namespace std;
int depth[10];
const int inf = 999999999;
int c[10][10];

void f(int position, int distance)
{
    if(depth[position] <= distance){
        return;
    }
    depth[position] = distance;
    for(int i = 0; i < 10; i++){
        f(i, distance + c[i][position]);
    }
}


int main()
{
    int h, w;
    cin >> h >> w;
    for(int i = 0; i < 10; i++){
        for(int j = 0; j < 10; j++){
            cin >> c[i][j];
        }
    }
    int a[210][210];
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            cin >> a[i][j];
        }
    }
    for(int i = 0; i < 10; i++){
        depth[i] = inf;
    }
    for(int i = 0; i < 10; i++){
        f(i, c[i][1]);
    }
    int answer = 0;
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            if(a[i][j] == -1){
                continue;
            }
            answer += depth[a[i][j]];
        }
    }
    cout << answer << endl;
    return 0;
}

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

int main() {
  char c;
  if(c == 'z'){
    printf("z\n");
    return 0;
  }
  cin >> c;
  printf("%c\n", c+1);
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	int h,m,s,a,b,c,x,y;
	for(int i=0;i<3;i++){
		cin>>h>>m>>s;
		x=h*3600+m*60+s;
		cin>>a>>b>>c;
		y=a*3600+b*60+c;
		y-=x;
		cout<<y/3600<<" ";
		y%=3600;
		cout<<y/60<<" ";
		y%=60;
		cout<<y<<endl;
	}
}

Measured memory_bytes: 3092
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<bitset>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<queue>
#include<vector>
using namespace std;

#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL

int main() {
	string T, P; cin >> T >> P;
	for (size_t s = T.find(P); s != string::npos; s = T.find(P, s)) {
		printf("%d\n", s++);
	}
	return 0;
}

Measured memory_bytes: 1200
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using P	  = pair<ll, ll>;
using mat = vector<vector<ll>>;
typedef string::const_iterator State;
class ParseError {};

void IOS() { ios::sync_with_stdio(false), cin.tie(0); }

constexpr ll INF = 1e16;
constexpr ll INM = 114514;
constexpr ll MOD = 1e9 + 7;
constexpr ld EPS = 1e-12;

template <typename T>
void dump(T x) { cout << x << endl; }
void dumpf(ld x, ll t) { cout << setprecision(t) << fixed << x << endl; }
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
	fill((T *)array, (T *)(array + N), val);
}
inline ll mod(ll a, ll b) {
	if (a > 0) return a % b;
	if (a % b == 0) return 0;
	ll x = -a / b + 1;
	a += x * b;
	return a % b;
}
ll powm(ll a, ll b, ll c) {
	if (b == 0)
		return 1;
	else if (b % 2 == 0) {
		ll d = powm(a, b / 2, c);
		return (d * d) % c;
	} else
		return (a * powm(a, b - 1, c)) % c;
}
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll dx[4] = {1, 0, -1, 0};
ll dy[4] = {0, 1, 0, -1};

vector<ll> divis(ll n) {
	vector<ll> ret;
	for (int i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			ret.push_back(i);
			if (i != n / i) ret.push_back(n / i);
		}
	}
	return ret;
}

int main() {
	IOS();
	ll x;
	cin >> x;
	for (int i = x; i < 4 * x;i++) {
		if(divis(i).size() == 2){
			dump(i);
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define inf 1000000000
#define INF 100000000000000
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265
#define F first
#define S second
#define PB push_back
#define EB emplace_back

int n,m;
ll ans=-INF;
vector<ll> x,y,z;

void f(int i,int j,int k){
  vector<ll> v;
  rep(s,n){
    v.PB(x[s]*i+y[s]*j+z[s]*k);
  }
  sort(all(v));
  reverse(all(v));
  ll res=0;
  rep(s,m){
    res+=v[s];
  }
  ans = max(ans,res);
}

int main(){
  cin>>n>>m;
  x.resize(n);
  y.resize(n);
  z.resize(n);
  rep(i,n){
    cin>>x[i]>>y[i]>>z[i];
  }

  FOR(i,-1,2){
    FOR(j,-1,2){
      FOR(k,-1,2){
        if(i&&j&&k)
          f(i,j,k);
      }
    }
  }

  cout<<ans<<endl;
}


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

int main(){
  string w;
  cin >>w;
  int N[26];
  for (int i=0;i<26;i++){
    N[i]=0;
  }
  
  for (int i=0;i<w.length();i++){
    N[w.at(i)-'a']++;
  }
  
  for (int j=0;j<26;j++){
    if(! (N[j]%2==0)){
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout <<"Yes"<<endl;
  return 0;
}

  

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n, m;
	cin>>n>>m;
	vector<string> vec(n);
	for(int i = 0; i < n; ++i){
		cin>>vec[i];
	}
	for(int i = 0; i < n; ++i){
		if(vec[i][0] == '.'){
			bool ok = true;
			for(int j = 0; j < m; ++j){
				if(vec[i][j] == '#')ok = false;
			}
			if(ok){
				for(int j = 0; j < m; ++j){
					vec[i][j] = 'x';
				}
			}
		}
	}
	for(int j = 0; j < m; ++j){
		if(vec[0][j] == '.' || vec[0][j] == 'x'){
			bool ok = true;
			for(int i = 0; i < n; ++i){
				if(vec[i][j] == '#'){
					ok = false;
				}
			}
			if(ok){
				for(int i = 0; i < n; ++i){
					vec[i][j] = 'x';
				}
			}
		}
	}
	for(int i = 0; i < n; ++i){
		bool ok = false;
		for(int j = 0; j < m; ++j){
			if(vec[i][j] == '.' || vec[i][j] == '#')ok=true;
		}
		if(ok){
			for(int j = 0; j < m; ++j){
				if(vec[i][j] != 'x'){
					cout<<vec[i][j];
				}
			}
			cout<<endl;
		}
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define ort ((bas+son+1ll)/2ll)
#define coc g[node][i]
#define mod 1000000007
#define inf 1000000009
#define N 1000005
using namespace std;
 
typedef long long ll;
typedef pair < int , int > ii;

string s;

int main() {
	
	cin >> s;
	
	for(int i = 0; i < s.length() - 1; i++)
	{
		if(s[i] == s[i+1])
		{
			cout << "Bad";
			return 0;
		}
	}
	
	cout << "Good";
	
	return 0;
}


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

#define rep(i, a) for (int i = 0; i < (a); i++ )
#define FOR(i, m, n) for(int i = m; i < n; i++)

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

const int INF = 1001001001;
const int MOD = 1000000007;
const double PI=acos(-1);

int main(){
    int N;
    cin >> N;
    int c2,c4,co;
    c2 = c4 = co = 0;

    rep(i,N) {
        int tmp;
        cin >> tmp;
        if (tmp%4==0) {
            c4++;
        }
        else if (tmp%2==0) {
            c2++;
        }
        else {
            co++;
        }
    }
    if ((co+c2%2)>c4+1) {
        cout << "No" << endl;
    }
    else {
        cout << "Yes" << endl;
    }
}


Measured memory_bytes: 256
n = int(input())
sn = str(n)
n3 = 0
minx = 0
temp = 754
for i in range(len(str(n // 100))):
    n3 = int(sn[i : i + 3])
    minx = abs(753 - n3)
    if temp > minx:
        temp = minx

print(temp)


Measured memory_bytes: 3060
#include <iostream>

int main() {
	int n, m;
	std::cin >> n >> m;
	int num = n / (m * 2 + 1);
	if (n % (m * 2 + 1))
		num++;
	/*if (!num)
		num = 1;*/
	std::cout << num << std::endl;
}


Measured memory_bytes: 3608
S = input()

def check(S):
    size = len(S)
    if S[0]=="0" or S[-1]=="1":
        return False
    else:
        for i in range(size-1):
            a, b = i, size-i-2
            if (S[a]=="1" and S[b]=="0") or (S[a]=="0" and S[b]=="1"):
                return False
        return True

if check(S):
    N = len(S)
    l = [1]
    p = False
    for i in range(2, N+1):
        if p:
            l.append(i)
            if S[i-1]=="1":
                p = True
            else:
                p = False
        else:
            print(l[-1], i)
            if S[i-1]=="1":
                p = True
    sl = len(l)
    for i in range(sl-1):
        print(l[i], l[i+1])
else:
    print(-1)

Measured memory_bytes: 8576
N, M = map(int, input().split())
X = list(map(int, input().split()))
X.sort()

difX = []
for i in range(len(X)-1):
    difX.append(X[i+1]-X[i])
difX.sort(reverse=True)

if M > N:

    difX = difX[N-1:]

    total = 0
    for x in difX:
        total+= x

    print(total)
else:
    print(0)

Measured memory_bytes: 13968
# 桁DP

n = gets.chomp.split("").map(&:to_i)
k = gets.to_i
length = n.length
# dp[上から i 桁まで][smaller][0 でない数字を使った回数]の出現回数
dp = (length + 1).times.map { 2.times.map { Array.new([length + 1, k + 1].max, 0) } }
# 初期化
# dp[0 桁目まで][桁は不自由][0 でない数字 を 0 回使った]の出現回数は 1
dp[0][0][0] = 1

# 桁数分ループする（i は遷移元の桁）
length.times do |i|
  # smaller == 1 の場合、以下の桁は自由
  2.times do |smaller|
    # 1 を使った回数ごとに確認する
    length.times do |count|
      # smaller が既に 1 の場合は 10 回ループ、0 の場合は(その桁の数字 + 1）回ループ
      limit = smaller == 1 ? 9 : n[i]
      dp_current = dp[i][smaller]
      # 最適化のため、事前に 1 行分だけ浅いコピーをする
      # dp_next と dp[i + 1] の object_id は同じ
      dp_next = dp[i + 1]
      (limit + 1).times do |d|
        # smaller == 0 且つ d == limit（上限）の時のみ、0 のまま遷移する
        next_smaller = smaller == 0 && d == limit ? 0 : 1
        # d == 0 でない場合は回数を足す
        addition = d == 0 ? 0 : 1
        # 次の桁に遷移する
        dp_next[next_smaller][count + addition] += dp_current[count]
      end
    end
  end
end

ans = 0
# 桁が自由、不自由ともに、(0 以外を k 回使った出現回数)を ans に足す
2.times do |i|
  ans += dp[length][i][k]
end
puts ans


Measured memory_bytes: 2684
# Aizu Problem 0226: Hit and Blow

import sys, math, os, bisect

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def hit_and_blow(seq, guess):
    hit, blow = 0, 0
    nums = list(range(10))
    for k in range(4):
        s = seq
        if seq[k] == guess[k]:
            hit += 1
            nums.remove(int(seq[k]))
    blow = sum([str(n) in guess and str(n) in seq for n in nums])
    return hit, blow
            

while True:
    seq, guess = [_ for _ in input().split()]
    if seq == guess == "0":
        break
    hit, blow = hit_and_blow(seq, guess)
    print(hit, blow)

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

int main() {
  long int N,K,temp=0,p;
  cin >> N >> K;
  
  if(N%K){
    N%=K;
  }else{
    cout << 0 << endl;
    return 0;
  }
  while(1){
    temp=N;
    if(N>=K) N-=K;
    else N=K-N;
    if(temp>=N){
      continue;
    }else{
      break;
    }
  }
  
  cout << temp << endl;
  
  return 0;
}


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

int main(){
   int year;
   int month, day;
   char c1,c2;
   cin >> year >> c1 >> month >> c2>> day;
   cout<<(month <= 4 ? "Heisei" : "TBD") <<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll Inf = 1e15;

ll n,k;
ll h[100100];
ll Dp[100100];

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

    for(ll i=0;i<n;i++) scanf("%I64d",h+i);

    Dp[n-1] = 0;

    for(ll i=n-2;i>=0;i--)  Dp[i] = Inf;

    for(ll i=n-2;i>=0;i--)
        for(ll j=1;i+j<n&&j<=k;j++)
            Dp[i] = min( Dp[i] , abs(h[i]-h[i+j]) + Dp[i+j] );

    cout<<Dp[0];
}



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

bool kaibun(string S) {
  if (S[0] == S[4] && S[1] == S[3])
    return true;
  return false;
}

int main() {
  int A, B;
  cin >> A >> B;
  int ans = 0;
  for (int i = A; i <= B; i++) {
    if (kaibun(to_string(i)))
      ans++;
  }
  cout << ans << endl;
}

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

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;
 
int main(){
  //input
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  
  int a , b ;
  cin  >> a >> b ;
  int ans=0;
  int sum=1;
  while(sum<b){
    sum+=a-1;
    ans++;
  }
  cout<<ans<<endl;
}
  



Measured memory_bytes: 256
# aising2019C - Alternating Path
def dfs(sx: int, sy: int) -> None:
    color, stack = [0] * 2, [(sx, sy, S[sx][sy])]
    S[sx][sy] = 2  # make the grid visited
    while stack:
        x, y, col = stack.pop()
        color[col] += 1
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == col ^ 1:
                stack.append((nx, ny, S[nx][ny]))
                S[nx][ny] = 2  # make the grid visited
    return color[0] * color[1]


def main():
    # separate S to connected components
    global H, W, S, dxy
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    S = [[1 if i == "#" else 0 for i in s] for s in S]
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] != 2:
                ans += dfs(i, j)
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 12556
import numpy as np

N,A,B,C,D = map(str,input().split())
S = input()
S = str(S)
N = int(N)
A = int(A)
B = int(B)
C = int(C)
D = int(D)

flag = 'No'
if(C<D):
    if("##" in S[A-1:D]):
        flag = "No"
    else:
        flag = "Yes"
elif(C>D):
    if("##" in S[A-1:C]):
        flag = "No"
    else:
        if("..." in S[B-2:D+1]):
            flag = "Yes"
        else:
            flag = "No"
print(flag)

Measured memory_bytes: 20644
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<int>; using VVI = vector<VI>; using VVVI = vector<VVI>;
const int inf=1e9+7;
const ll INF=1LL<<61;
const ll mod=1e9+7;

ll gcd(ll a,ll b){
  if(a<b) swap(a,b);
  if(b==0) return a;
  if(a%b==0) return b;
  return gcd(a%b,b);
}

int main(){
  int i,j;
  int n,m;
  cin>>n>>m;
  ll a[n];
  ll aa[n];
  VI v(n,0);
  bool ng=0;
  for(i=0;i<n;i++){
    cin>>a[i];
    aa[i]=a[i]/2;
    while(a[i]%2==0) {
      a[i]/=2;
      v[i]++;
    }
  }
  for(i=0;i<n;i++){
    if(v[0]!=v[i]){
      cout<<0<<endl;
      return 0;
    }
  }
  if(v[0]==0){
    cout<<0<<endl;
    return 0;
  }

  ll l=aa[0];
  for(i=1;i<n;i++){
    l=(l/gcd(l,aa[i]))*aa[i];
    if(l>m){
      cout<<0<<endl;
      return 0;
    }
  }
  
  cout<<m/l-m/(l*2)<<endl;

  
  return 0;
}


Measured memory_bytes: 2176
N = int(input())
S_dict = {}
for i in range(0, N):
  char = input()

  if char in S_dict:
    S_dict[char] += 1
  else:
    S_dict[char] = 1

S_dict_sorted = sorted(S_dict.items(), key=lambda x: -x[1])
_, value = S_dict_sorted[0]
ans_list = []
for k, v in S_dict_sorted:
  if value == v:
    ans_list.append(k)

ans_list.sort()
for item in ans_list:
  print(item)


Measured memory_bytes: 45788
n, m = map(int, input().split())
A = [ int(input()) for _ in range(m) ]
dp = [0]*(n+1)
broken = [False]*(n+1)
for i in A:
  broken[i] = True
dp[0] = 1
if not broken[1]:
  dp[1] = 1
for i in range(2, n+1):
  if broken[i]:
    continue
  else:
    dp[i] = dp[i-2] + dp[i-1]

print(dp[n]%(10**9+7))   

Measured memory_bytes: 460788
# -*-coding: utf-8 -*-
N, T = map(int, input().split())
ct = []
for i in range(N):
    ct.append(list(map(int, input().split())))
ans_list = []
for i in range(N):
    if ct[i][1] <= T:
        ans_list.append(ct[i][0])

if len(ans_list) == 0:
    print("TLE")
else:
    print(min(ans_list))

Measured memory_bytes: 3060