akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=1LL<<61;

int main() {
  ll n,c,k;
  cin >> n >> c >> k;
  ll ans=0;
  ll cnt=0;
  ll ti=-inf;
  vec t(n);
  for(ll i=0;i<n;i++) cin >> t[i];
  sort(t.begin(),t.end());
  for(ll i=0;i<n;i++) {
    if(ti+k<t[i]||c<=cnt) {
      cnt=1;
      ti=t[i];
      ans++;
    }
    else {
      cnt++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1024
#include <cstdio>

using namespace std;

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    double ans = 0;
    for (int i = 1; i <= n; ++i) {
        double cnt = 1.0 / n;
        int p = i;
        while (p < k) p <<= 1, cnt /= 2;
        ans += cnt;
    }
    printf("%.15lf\n", ans);
    return 0;
}


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

using namespace std;

#define MP make_pair
#define FF first
#define SS second

using LL = long long;
using PII = pair<int,int>;
using PLL = pair<LL,LL>;
using PILL = pair<LL,PII>;

const LL INF = 1e15;
const int UB = 400010;

int N, M, S, Gl;
map<PLL,int> ids;
LL dist[UB];
void dijk(vector<vector<PLL>>& G){
  priority_queue<PLL, vector<PLL>, greater<PLL>> pq;
  fill(dist, dist+UB, INF);
  pq.push(PLL(0,ids[MP(S,0)]));
  dist[ids[MP(S,0)]] = 0;

  while(!pq.empty()){
	PLL p = pq.top();
	pq.pop();
	if(p.FF > dist[p.SS])
	  continue;
	  
	for(auto&& e: G[p.SS]){
	  if(p.FF + e.SS < dist[e.FF]){
		dist[e.FF] = p.FF + e.SS;
		pq.push(MP(dist[e.FF], e.FF));
	  }
	}
  }
}

int main(){
  cin >> N >> M >> S >> Gl;
  --S;
  --Gl;
  int id = 0;
  
  vector<vector<int>> tms(N);
  ids[MP(0,S)] = id++;
  tms[S].push_back(0);
  vector<vector<PLL>> G(UB);
  for(int i=0;i<M;++i){
	int u, v, t, c;
	cin >> u >> v >> t >> c;
	--u;
	--v;
	if(!ids.count(MP(u,t)))
	  ids[MP(u,t)] = id++;
	if(!ids.count(MP(v,t+c)))
	  ids[MP(v,t+c)] = id++;
	tms[u].push_back(t);
	tms[v].push_back(t+c);
	G[ids[MP(u,t)]].emplace_back(ids[MP(v,t+c)], 0);
  }

  for(int i=0;i<N;++i){
	sort(begin(tms[i]), end(tms[i]));
	tms[i].erase(unique(begin(tms[i]), end(tms[i])), end(tms[i]));
	for(int j=0;j+1<tms[i].size();++j){
	  G[ids[MP(i,tms[i][j])]].emplace_back(ids[MP(i,tms[i][j+1])], tms[i][j+1] - tms[i][j]);
	}
  }

  dijk(G);
  LL ans = INF;
  for(auto&& t: tms[Gl])
	ans = min(ans, dist[ids[MP(Gl,t)]]);
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 61068
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  int n, t, a, ans, min=1000000000;
  cin >> n;
  cin >> t >> a;
  for(int i=0; i<n; i++){
    int h, temp;
    cin >> h;
    temp = t*1000 - h * 6;
    if(min > abs(temp - a*1000)){
      ans = i;
      min = abs(temp - a*1000);
    }
  }
  cout << ans + 1 << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<ctime>

using namespace std;
using ll = long long;

int f_dir[2][4] = {{-1, 0, 0, 1}, {0, -1, 1, 0}};
int e_dir[2][8] = {{-1, -1, -1, 0, 0, 1, 1, 1}, {-1, 0, 1, -1, 1, -1, 0, 1}};
bool is_in_field(int y, int x, int h, int w){
  return (y >= 0 && y < h && x >= 0 && x < w);
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int ti = clock();
  // start-----------------------------------------------
  string s; cin >> s;
  int q; cin >> q;
  int rev = 0;
  string a, b;
  for(int i = 0; i < q; i++){
    int t; cin >> t;
    if(t == 1){
      rev = (rev + 1)%2;
    }
    else{
      int f; char c; cin >> f >> c;
      if(rev){
        if(f == 1){
          b += c;
        }
        else{
          a = c + a;
        }
      }
      else{
        if(f == 1){
          a = c + a;
        }
        else{
          b += c;
        }
      }
    }
  }
  if(rev){
    reverse(s.begin(), s.end());
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    cout << b + s + a << endl;
  }
  else{
    cout << a + s + b << endl;
  }

  // end-----------------------------------------------
  // cerr << 1.0 * (clock() - ti) / CLOCKS_PER_SEC << endl;
}


Measured memory_bytes: 1416
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;

main() {
    int64_t n;
    cin >> n;

    unordered_map<string, int64_t> c;
    for (auto i : irange(0L, n)) {
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        ++c[s];
    }

    int64_t ans = 0;
    for (const auto& kv : c) {
        ans += kv.second * (kv.second - 1) / 2;
    }

    cout << ans << endl;
}

Measured memory_bytes: 10660
#include <iostream>
#include <math.h>
#define PI 3.141592653589793

using namespace std;

double transToRadian( double degree ){
	double radian = degree * PI / 180.0;

	return radian;
}

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

	 double sinC = sin( transToRadian(c) );
	 double cosC = cos( transToRadian(c) );

	 double S = a * b * sinC / 2;

	 double L = a + b+ sqrt( a * a + b * b - 2 * a * b * cosC );

	 double h = b * sinC;

	 cout << fixed << S << endl;
	 cout << fixed << L << endl;
	 cout << fixed << h << endl;
}

Measured memory_bytes: 1284
N=int(input())
lsA=[int(s) for s in input().split()]
lsB=[int(s) for s in input().split()]
lsC=[int(s) for s in input().split()]
sum=lsB[lsA[0]-1]
for i in range(1,N):
  a=lsA[i]
  if lsA[i-1]+1==a:
    sum+=lsB[a-1]+lsC[a-2]
  else:
    sum+=lsB[a-1]
print(sum)
  

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <iomanip>
#include <cassert>
#include <random>
#include <tuple>
#include <cstdint>

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

using namespace std;
typedef long long ll;

const int INF = 1 << 30;
const int MOD = 1e9 + 7;


int main() {
    int n; cin >> n;
    vector<double> p(n); rep(i, n) cin >> p[i];
    vector<vector<double>> dp(n+1, vector<double>(n+1, 0));
    dp[0][0] = 1;
    rep(i, n) rep(j, n+1) {
        if (j+1 <= n) dp[i+1][j+1] += dp[i][j] * p[i];
        dp[i+1][j] += dp[i][j] * (1-p[i]);
    }

    double ans = 0;
    for (int i = n/2 + 1; i <= n; i++) {
        ans += dp[n][i];
    }
    cout << setprecision(10) << ans << endl;

    return 0;
}

Measured memory_bytes: 70784
/*

                   بِسْمِ ٱللَّٰهِ ٱلرَّحْمَٰنِ ٱلرَّحِيمِ
                  لآ اِلَهَ اِلّا اللّهُ مُحَمَّدٌ رَسُوُل اللّهِ
*/

/*
    Auther:   n0oO0o0Ob(None of them)
    from  :   https://n0oo0o0ob.sleek.page/

*/




#include <bits/stdc++.h>

using namespace std;
#define endl "\n"
#define pb push_back

                                        #define noob n0oO0o0Ob
// ---------------------------------
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
//----------------------------------
const ld PI = acos((ld)-1);
const int MOD = 1000000007;
//----------------------------------


int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    int a;
    string x;
    cin >> a >> x;
    int v=0;
    for(int i=0; i<a-2; i++){
        if(x[i] == 'A' && x[i+1] == 'B' && x[i+2] == 'C') v++;
    }
    cout << v << endl;



	return 0;
}



Measured memory_bytes: 3620
using System;
using System.Linq;
using System.Collections;

namespace Bcs
{
    class Program
    {
        static void Main(string[] args)
        {
            var ar = Console.ReadLine().Split(' ').Select(x=>int.Parse(x)).ToArray();
            var k = int.Parse(Console.ReadLine().Trim());

            var max = ar.Max();
            var sum = ar.Sum() - max;
            sum += (int)(Math.Pow(2, k))* max;

            Console.WriteLine(sum);
        }
    }
}


Measured memory_bytes: 13396
a=input()
b = input()


list = [1,2,3]
c = int(a)-1
d = int(b)-1

list[c]= 4
list[d]= 4


if 1 in list:
    print(1)
elif 2 in list:
    print(2)
elif 3 in list:
    print(3)


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
struct pp
{
    int x,y,flag;
};
bool cmp(const pp&a,const pp&b)
{
    if(a.x!=b.x)
        return a.x<b.x;
    return a.y<b.y;
}
pp a[110],b[110];
int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=0;i<n;i++)
        {
            cin>>a[i].x>>a[i].y;
            a[i].flag=0;
        }
        for(int i=0;i<n;i++)
            cin>>b[i].x>>b[i].y;
        sort(a,a+n,cmp);
        sort(b,b+n,cmp);
        int s=0;
        for(int i=0;i<n;i++)
        {
            int flag=0,p=-1;;
            for(int j=0;a[j].x<=b[i].x&&j<n;j++)
              if(a[j].x<b[i].x&&a[j].y<b[i].y&&!a[j].flag)
              {
                 if(!flag)
                    p=j;
                 else if(a[j].y>a[p].y)
                    p=j;
                 flag=1;
              }
            if(flag)
            {
                s++;
                a[p].flag=1;
            }
        }
        cout<<s<<endl;
    }
    return 0;
}

Measured memory_bytes: 3596
#include <iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
#define INF 1e8
using namespace std;
int main(void){
int  n,m;
cin>>n>>m;

if(n*500>=m)
    cout<<"Yes";
else
    cout<<"No";



}



Measured memory_bytes: 3056
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func Scanner() string {
	sc.Scan()
	return sc.Text()
}

func intScanner() int {
	n, _ := strconv.Atoi(Scanner())
	return n
}

func main() {
	mod := 1000000007
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	n := intScanner()
	k := intScanner()
	as := make([]int, n)
	for i := 0; i < n; i++ {
		as[i] = intScanner()
	}
	dp := make([][]int, n+1)
	for i := 0; i < n+1; i++ {
		dp[i] = make([]int, k+1)
	}
	dp[0][0] = 1
	for i := 1; i < n+1; i++ {
		s := make([]int, k+1)
		s[0] = dp[i-1][0]
		for j := 1; j < k+1; j++ {
			s[j] = (s[j-1] + dp[i-1][j]) % mod
		}
		for j := 0; j < k+1; j++ {
			if j-as[i-1] <= 0 {
				dp[i][j] = s[j]
			} else {
				dp[i][j] = (s[j] - s[j-as[i-1]-1] + mod) % mod
			}
		}
	}
	fmt.Println(dp[n][k])
}


Measured memory_bytes: 144768
#include<iostream>
#include<iomanip>
using namespace std;
int main(){
    int mlc[11][11],n;
    while(cin>>n,n){
        //restart
        for(int i=0;i<11;i++)for(int j=0;j<11;j++)mlc[i][j]=0;
        //input
        for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>mlc[i][j];
        //sum
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                mlc[i][n]+=mlc[i][j];
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                mlc[n][i]+=mlc[j][i];

        for(int i=0;i<n;i++)mlc[n][n]+=mlc[i][n];

        for(int i=0;i<=n;i++){
            for(int j=0;j<=n;j++)cout<<setw(5)<<mlc[i][j];
            cout<<endl;


        }

    }
    return 0;
}

Measured memory_bytes: 1172
//include
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath> 
#include <iomanip>
#include <math.h>
#include <utility>
#include <functional>
#include <cstdlib>
//using
using namespace std;
using vl = vector <long long>;
using vs = vector <string>;
using vc = vector <char>;
using ll= long long;
using vvl = vector<vector<ll> >;
//vector<vector<char> > hyou(N, vector<char>(N));
using vd = vector <double>;
//define
//#define int long long
#define rep(i,n) for(int i=0; i<n; i++)
#define print(n) cout<<n<<endl;
#define sortp(d) sort(d.begin(),d.end()) //1234
#define sortm(d) sort(d.rbegin(),d.rend()) //4321
//素数判定　O(√A) 
bool is_prime(int x){
 if(x<=1) return false;
 for(int i=2;i*i<=x;i++)
 if(x%i==0) return false;
 return true;
 }
/*順列生成
do {
  // 順列に対する処理
} while (next_permutation(配列変数.begin(), 配列変数.end()));*/

//絶対値　abs()

//グローバル変数宣言
 ll p=0,q=0,r=0;

int main(){
   ll n,a,b;
   cin>>n>>a>>b;
   p=n/(a+b);
   q=n%(a+b);
   if (q>a)
   {
     q=a;
   }
   print(a*p+q)
   
   
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
struct S{
    mint sum;
    mint size;
};
struct F{
    mint a, b;
};
S op(S a, S b){
    return S{a.sum + b.sum, a.size + b.size};
}
S e(){
    return S{0, 0};
}
S mapping(F f, S x){
    return S{x.sum * f.a + x.size * f.b, x.size};
}
F composition(F f, F g){
    return F{f.a * g.a, f.a * g.b + f.b};
}
F id(){
    return F{1, 0};
}
int main(){
    int N, Q;
    cin >> N >> Q;
    vector<S> a(N);
    for(int i = 0; i < N; i++){
        long long b;
        cin >> b;
        a[i] = S{b, 1};
    }
    lazy_segtree<S, op, e, F, mapping, composition, id> segK(a);
    for(int i = 0; i < Q; i++){
        int f;
        cin >> f;
        if(f == 0){
            long long l, r, b, c;
            cin >> l >> r >> b >> c;
            segK.apply(l, r, F{b, c});
        }
        else{
            int l, r;
            cin >> l >> r;
            S ans = segK.prod(l, r);
            cout << ans.sum.val() << endl;
        }
    }
}

Measured memory_bytes: 19276
n = int(input())
h = [int(i) for i in input().split()]
# dpの最小値を変更する関数
def chmin(a, b):
    if a > b:
        return b
    else:
        return a
    
# 無限大の値
f_inf = float('inf')
# DP テーブルを初期化　(最小化問題なので INF に初期化)
dp = [f_inf] * (10**5+10)
# 初期条件
dp[0] = 0
# 足場 i から足場 i+1 へ移動する。コストは|h[i]−h[i+1]|
# 足場 i から足場 i+2 へと移動する コストは |h[i]−h[i+2]|
for i in range(n-1):
    dp[i + 1] = chmin(dp[i + 1], dp[i] + abs(h[i] - h[i + 1]))
    # n-2の時は2つ先はない
    if i < n-2:
        dp[i + 2] = chmin(dp[i + 2], dp[i] + abs(h[i] - h[i + 2]))
print(dp[n-1])

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

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<pi> vpi;
typedef vector<bool> vbool;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define forall(it,s) for(auto it = s.begin(); it != s.end(); ++it)
#define F0(i,n) for(ll i = 0; i < n; i++)
#define F1(i,n) for(ll i = 1; i <= n; i++)
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define per(i,a,b) for(int i = b-1; i >= a; i--)
#define FIN ios::sync_with_stdio(false);cin.tie(0);
#define db(x) cout<<#x<<" = "<<x<<"\n"
#define all(v) v.begin(),v.end()
#define modulo(a,b) ((a%b)+b)%b
#define F first
#define S second
#define INF 1000000010
#define INFLL 1000000000000000000
#define eps 0.000000000001
#define mod 1000000007
template<class C> void mini(C&a, C b){ a=min(a, b);}
template<class C> void maxi(C&a, C b){a=max(a,b);}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

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


int main () {
	//FIN

  int k; cin >> k;
  for (int i = 0; i < k; i++)
    cout << "ACL";
  cout << "\n";

	return 0;
}










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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << setprecision(20) << fixed;
  int N; cin >> N;
  if(N == 1){
    cout << "Hello World" <<endl;
  } else{
    int A, B;
    cin >> A >> B;
    cout << A + B <<endl;
  }
}


Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int n;
  cin >> n;
  vector<vector<ll>> s(n,vector<ll>(n));
  for(int i=0;i<n;i++){
    string u;cin >> u;
    for(int j=0;j<n;j++){
      if(u[j]=='1'){
        s[i][j]=1;
      }
      else{
        s[i][j]=1e9;
      }
    }
    s[i][i]=0;
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      for(int k=0;k<n;k++){
        s[j][k]=min(s[j][k],s[j][i]+s[i][k]);
      }
    }
  }
  ll ans=0;
  int q;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(ans<s[i][j]){
        q=i;
        ans=max(ans,s[i][j]);
      }
    }
  }
  map<ll,ll> mp;
  for(int i=0;i<n;i++){
    mp[i]=s[q][i];
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(mp[i]==mp[j]){
        if(s[i][j]==1){
          cout << -1 << endl;
          return 0;
        }
      }
    }
  }
  cout << ans+1 << endl;
}

Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<algorithm>
#include<functional>
#include<bitset>
#include<iomanip>
#include<vector>
#include<set>
#include<map>
#include<list>
#include<stack>
#include<queue>
#include<deque>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;

void insertionsort(int a[], int n){
  for(int i=0; i < n; i++){
    int v = a[i];
    int j = i-1;
    while(0 <= j && a[j] > v){
      a[j+1] = a[j];
      j--;
    }
    a[j+1] = v;
    for(int i=0; i < n; i++){
      if(i)cout << ' ';
      cout << a[i];
    }
    cout << endl;
  }
}



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


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

int main(){
int N,L;
  cin >> N >> L;
  int R=L+N-1;
  int eat;
  if(R<=0)eat=R;
  else if(L>=0)eat = L;
  else eat = 0;
  int ans = (R+L)*N/2-eat;
  cout << ans << endl;
}

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

using namespace std;

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

    vector<pair<long long, long long>> vt(n);
    for (int i = 0; i < n; ++i) {
        cin >> vt[i].first >> vt[i].second;
    }
    sort(vt.begin(), vt.end());

    auto ans = 0L;
    auto curr = 0L;
    for (int i = 0; i < n; ++i) {
        if (curr + vt[i].second <= m) {
            ans += vt[i].first * vt[i].second;
            curr += vt[i].second;
        } else {
            ans += vt[i].first * (m - curr);
            curr = m;
        }

        if (curr == m) {
            cout << ans << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 1792
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
from functools import reduce

n,k = list(map(int, input().split()))

a = n*(n+k+1)*(n-k+2)//2
b = n-k+2
c = -((n+2)*(n+1)*n - k*(k-1)*(k-2))//3

print((a+b+c) % (10**9+7))

Measured memory_bytes: 9424
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <cmath>
#include <iomanip>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int mod=1e9+7;

int main() {
  double a,b,x;
  cin>>a>>b>>x;
  double S=x/a;
  double deg=0;
  if(S>=a*b/2){
    double t=2*(a*b-S)/a;
    deg=atan2(t,a);
  }
  else{
    double t=2*S/b;
    deg=atan2(b,t);
  }
  double PI=acos(-1);
  double ans=deg/PI*180;
  cout<<fixed<<setprecision(10)<<ans<<endl;
  return 0;  
}

Measured memory_bytes: 4164
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

_ = ri()
a = sorted(rl())
if sum(a[:-1]) > a[-1]:
  print('Yes')
else:
  print('No')

    










Measured memory_bytes: 27152
#include <stdio.h>

#define MAX 500000
#define SENTINEL 2000000000

int L[MAX/2+2], R[MAX/2+2];
int cnt;

void merge(int A[],int n,int left, int mid, int right) {
  int i, j, k;
  int n1 = mid -left;
  int n2 = right - mid;
  for(i=0;i<n1;i++) L[i] = A[left + i];
  for(i=0;i<n2;i++) R[i] = A[mid + i];
  L[n1] = R[n2] = SENTINEL;
  i=0, j=0;
  for(k=left; k<right; k++) {
    cnt++;
    if(L[i]<=R[j]) {
      A[k] = L[i++];
    } else {
      A[k] = R[j++];
    }
  }
}

void mergeSort(int A[],int n,int left,int right) {
  int mid;
  if(left+1 < right) {
    mid = (left+right) / 2;
    mergeSort(A,n,left,mid);
    mergeSort(A,n,mid, right);
    merge(A,n,left,mid,right);
  }
}

int main(void) {
  int A[MAX], n, i;
  cnt = 0;

  scanf("%d",&n);
  for(i=0;i<n;i++) scanf("%d",&A[i]);

  mergeSort(A, n, 0, n);
  for(i=0;i<n;i++) {
    if(i) printf(" ");
    printf("%d",A[i]);
  }
  printf("\n%d\n",cnt);

  return 0;
}


Measured memory_bytes: 6492
#include <stdio.h>

int main(void)
{
	int h,w;
	int i,j,k;
	
	while(1){
		scanf("%d %d",&h,&w);
		if(h==0||w==0) break;
		for(i=0;i<h;i++){
			for(j=0;j<w;j++){
				if((i-j)%2==0)printf("#");
				else{printf(".");}
			}
		printf("\n");
		}
	printf("\n");
	}
	
	return 0;
}

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

int main()
{
  int n, a, min = 1000001, max = -1000001;
  long long sum = 0;
  cin >> n;
  for (int i=0; i<n; i++) {
    cin >> a;
    if (a < min) min = a;
    if (a > max) max = a;
    sum += a;
  }
  cout << min << ' ' << max << ' ' << sum << endl;
  return 0;
}



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

int main() {
	int n;
	cin >> n;
	int out = 0;
	for (int i = 0; i < (n + 1)/2; ++i) {
		int l = 1 + 2 * i;
		int tmp = 0;
		for (int j = 0; j < (l + 1) /2; ++j) {
			int k = 1 + 2 * j;
			if (l % k == 0) tmp += 1;
		}
		if(tmp == 8) out += 1;
	}
	cout << out << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
const ll INF = 1e+15;

template<class T>
class segTree{
    vector<T> tree;             // 木を示す配列
    int N;                      // 木で保持しているノード数
    T def_val;                  // 範囲外などの時に返却する値
    function<T(T,T)> selector;  // 選択関数(max, min, sum etc...)

    public: 
        // 初期化
        segTree(vector<T> &v, function<T(T,T)> f, T default_val){
            int n = v.size();
            N = pow(2, ceil(log2(n))); 
            tree.resize(2*N-1);
            selector = f;
            def_val = default_val;

            for(int i=0;i<N;i++) tree[N-1+i] = (i>=n?def_val:v[i]);
            for(int i=N-2;i>=0;i--) tree[i] = selector(tree[2*i+1], tree[2*i+2]);
        };

        // 値の更新
        void update(int ind, T val){
            ind += N - 1;
            tree[ind] = val;
            while(ind > 0){
                ind = (ind - 1) / 2;
                tree[ind] = selector(tree[2*ind+1], tree[2*ind+2]);
            }
        };

        // 値の取得(半閉区間[a,b)の範囲)
        T query(int a, int b, int ind = 0, int l = 0, int r = -1){
            if(r < 0) r = N;
            if(r <= a || b <= l) return def_val;
            if(a <= l && r <= b) return tree[ind];
            else return selector(query(a, b, 2*ind+1, l, (l+r)/2), 
                                 query(a, b, 2*ind+2, (l+r)/2, r));
        };
};


int main(){
    int n, m;
    cin >> n >> m;
    int l, r, c;
    vector<ll> dp(n, INF);

    vector<vector<P>> edge(n, vector<P>()); 
    for(int i=0;i<m;i++){
        cin >> l >> r >> c;
        --l;--r;
        edge[r].push_back({c, l});
    }
    dp[0] = 0;
    segTree<ll> st(dp, [](ll x, ll y){return min(x,y);}, INF);
    for(int i=1;i<n;i++){
        for(auto e: edge[i]){
            ll cost = st.query(e.second, i);
            dp[i] = min(cost + e.first, dp[i]);
            st.update(i, dp[i]);
        }
    }
    if ( dp[n-1] == INF) cout << -1 << endl;
    else cout << dp[n-1] << endl;
}

Measured memory_bytes: 8448
import java.util.Scanner;

public class Main {

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

	public static void main(String[] args) {
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] A = new int[N];
		int[] B = new int[M];
		for (int i = 0; i < N; ++i) {
			A[i] = sc.nextInt();
		}
		for (int i = 0; i < M; ++i) {
			B[i] = sc.nextInt();
		}
		int[] dp = new int[M + 1];
		for (int i = 0; i < N; ++i) {
			for (int j = M - 1; j >= 0; --j) {
				if (A[i] == B[j]) {
					dp[j + 1] = Math.max(dp[j + 1], dp[j] + 1);
				}
			}
		}
		int ans = 0;
		for (int i = 1; i <= M; ++i) {
			ans = Math.max(ans, dp[i]);
		}
		System.out.println(ans);
	}
}

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

#[fastout]
fn main() {
    input!{
        n:i32,
        s:[String;n]
    };


    let st = vec!["AC", "WA", "TLE", "RE"];

    let mut cnt = vec![];
    for i in &st {
        let cn = s.iter().filter(|n| *n == i).count();
        cnt.push(cn);
    
    }

    for i in 0..4 {
        println!("{} x {}", st[i], cnt[i]);

    }
}


Measured memory_bytes: 7940
<?php
//error_reporting(0);
$N = trim(fgets(STDIN));
//list($A,$B,$C) = explode(" ",trim(fgets(STDIN)));
$h = explode(" ",trim(fgets(STDIN)));

$mx = max($h);
$mn = min($h);

$total = 0;
for($i=$mx;$i>0;$i--) {
  $total += cnt($i);
}
printf("%d\n",$total);


function cnt($n) {
  global $h,$N;
  $last = -9;
  $mizuyari = 0;
  for($i=0;$i<$N;$i++) {
    if ($n == $h[$i]) {
      if ($last != $i - 1) {
        $mizuyari++;
      }
      $last=$i;
      $h[$i]-=1;
    }
  }
  return $mizuyari;
}


Measured memory_bytes: 4856
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

using namespace std;
typedef long long int64;

int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

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

  vector<int> rev_res;
  int pos=n;
  while(pos>0){
    bool can_step=false;
    for(int step=k;step>=1;step--){
      int next_pos=pos-step;
      if(next_pos<0) continue;
      if(s[next_pos]=='0'){
        can_step=true;
        rev_res.push_back(step);
        pos=next_pos;
        break;
      }
    }
    if(!can_step){
      cout<<-1<<endl;
      return 0;
    }
  }


  for(int i=rev_res.size()-1;i>=1;i--){
    cout<<rev_res[i]<<" ";
  }
  cout<<rev_res[0]<<endl;






  return 0;
}

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

using namespace std;

int main()
{
    int N, Q;
    string S;
    cin >> N >> Q >> S;
    vector<int> AClist(N + 1);
    for (int i = 0; i < N; i++)
    {
        if (S[i] == 'A' && S[i + 1] == 'C')
            AClist[i + 1] = AClist[i] + 1;
        else
        {
            AClist[i + 1] = AClist[i];
        }
    }

    int l[Q], r[Q];
    for (int i = 0; i < Q; i++)
    {
        cin >> l[i] >> r[i];
    }
    for (int i = 0; i < Q; i++)
    {
        cout << AClist[r[i] - 1] - AClist[l[i] - 1] << endl;
    }

    return 0;
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
int N, M;
struct dataset {
    long long P;
    long long Y;
    int num;
    int count;
};

vector<int> counter(100010, 1);

bool cmp(const dataset &l, const dataset &r) {
    return l.num < r.num;
}

bool cmp2(const dataset &l, const dataset &r) {
    return l.Y < r.Y;
}

int main() {
    cin >> N >> M;
    vector<dataset> D(M);
    int plus = 0;
    for(int i = 0; i < M; ++i) {
        cin >> D.at(i).P >> D.at(i).Y;
        D.at(i).num = plus;
        D.at(i).count = 0;
        plus++;
    }

    sort(D.begin(), D.end(), cmp2);

    for(int i = 0; i < M; ++i) {
        D.at(i).count = counter.at(D.at(i).P);
        counter.at(D.at(i).P)++;
    }

    sort(D.begin(), D.end(), cmp);

    for(int i = 0; i < M; ++i) {
        printf("%012lld\n", D.at(i).P * 1000000 + D.at(i).count);
    }

}

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

int main(){
  ll x;
  cin >>x;
  int ans = 1;
  ll cur = 100;
  for(int i = 1;;i++){
    cur = cur*1.01;
    if(cur>=x) {
      ans = i;
      break;
    }
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 3580
//#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"

#define rep(i,n) for(ll (i)=0;(i)<(ll)(n);(i)++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007LL
#define INF (1LL<<60LL)
#define int long long
#define MAX_N (100001)
typedef long long ll;

using namespace std;


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	double l; cin >> l;
	double ans = (l / 3.0) * (l / 3.0) * (l / 3.0);
	cout << fixed << setprecision(8) << ans << endl;
}

Measured memory_bytes: 256
#pragma region
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <iomanip>
#include <cstdint>
#include <bitset>
#include <fstream>

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))
#define all(x) x.begin(),x.end()

#pragma region UnionFind
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;
		else return par[x] = root(par[x]);
	}

	bool 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;
		if (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x)
	{
		return -par[root(x)];
	}
};
#pragma endregion
#pragma region GCD
int gcd(int a, int b)
{
	if (a%b == 0)return b;
	return gcd(b, a%b);
}
#pragma endregion
#pragma region chmin
template<class T> inline bool chmin(T& a, T b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma region chmax
template<class T> inline bool chmax(T& a, T b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma endregion


int main()
{
	string s; cin >> s;
	vector<int> v(3);
	for (char c : s)v[c - 'a']++;
	sort(all(v), greater<int>());
	if (v[0] - v[2] <= 1)cout << "YES" << endl;
	else cout << "NO" << endl;
}

Measured memory_bytes: 3748
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    int n, m;
    cin >> n >> m;
    if(n == m){
        cout << "Yes" << endl; 
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
x = [int(input()) for i in range(6)]
i = 0
j = 0
flag = 0
while i <= 5 and flag == 0:
    while j <= 5:
        if x[i]-x[j] > x[5]:
            print(":(")
            flag = 1
            break
        j += 1
    i += 1
    j = 0

if flag == 0:
    print("Yay!")


Measured memory_bytes: 2940
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
using namespace std;

int main(){
  long long N = 0;
  cin >> N;
  vector<long long> high(N);
  vector<int> rank(N);
  for(int i = 0;i < N;i++){
    cin >> high.at(i);
    rank.at(i) = 0;
  }
  long long now = 0;
  now = high.at(0);
  int count = 0;
  for(int i = 1;i < N;i++){
    if(now >= high.at(i)){
      count++;
    }else{
      count = 0;
    }
    now = high.at(i);
    rank.at(i) = count;
  }
  int ans = 0;
  for(int i = 0;i < N;i++){
    ans = max(ans,rank.at(i));
  }
  cout << ans << endl;
}


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

int main() {
  int n;
  cin >> n;
  set<string>s;
  for(int i = 0; i < n; i++) {
    string khin;
    cin >> khin;
    s.insert(khin);
  }
  cout << s.size();
}

Measured memory_bytes: 19224
#include <bits/stdc++.h>
using namespace std;
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(false), cout << fixed << setprecision(20);
#define int long long
#define gcd __gcd
#define all(x) (x).begin(), (x).end()
template<class T>
bool chmax(T& a, T b){return (a = max(a, b)) == b;}
template<class T>
bool chmin(T& a, T b){return (a = min(a, b)) == b;}
#define _overload(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(...) _overload(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
#define _rev(i, n) revi(i, n, 0)
#define revi(i, a, b) for(int i = (int)(a - 1); i >= (int)(b); i--)
#define rev(...) _overload(__VA_ARGS__, revi, _rev)(__VA_ARGS__)
#define each(i, n) for(auto&& i: n)
const int INF = 1e18, MOD = 1e9 + 7;
signed main() {
    INCANT;
    int n, res = 0;
    cin>>n;
    int a[111111];
    rep(i, n) {
        cin>>a[i];
    }
    sort(a, a + n);
    int sum[111111] = {a[0]};
    rep(i, 1, n) {
        sum[i] = sum[i - 1] + a[i];
    }
    rev(i, n, 1) {
        if(a[i] > sum[i - 1] * 2) {
            cout<<n - i<<endl;
            return 0;
        }
    }
    cout<<n<<endl;
}


Measured memory_bytes: 1920
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fs first
#define fst first
#define sc second
#define snd second
#define sz(X) (int)(X).size()
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define fornr(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define forab(i, a, b) for(int i = int(a); i < int(b); i++)
#define all(X) X.begin(), X.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef double dbl;
typedef long double ld;
typedef vector<int> vi;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin >> n;
    if (n % 2) cout << "0\n";
    else {
        ll x = 5, y = 2;
        ll cnt5 = 0, cnt2 = 0;
        while (n / x) cnt5 += (n / x) / 2, x *= 5;
        while (n / y) cnt2 += n / y, y *= 2;
        cout << min(cnt2, cnt5) << "\n";
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define rev1(i,n) for(int i=n;i>0;i--)
#define pb push_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vpii vector<pair<int,int> >
#define vb vector<bool>
#define pii pair<int,int>
#define F first
#define S second
#define INF 1e9+7
typedef long long int ll;
const int N=2e5+7;
vi G[N];
int parent[N];
int cnt[N];
int tmp;

void dfs1(int v){
  for(auto x:G[v]){
    if(parent[x]==0) {parent[x]=v;dfs1(x);}
  }
}
void dfs(int v){
  for(auto x:G[v]){
    if(x!=parent[v]) {cnt[x]+=cnt[v];dfs(x);}
  }
}
void solve(){
  int n,q;cin>>n>>q;
  rep(i,n-1){
    int a,b;cin>>a>>b;
    G[a].pb(b);
    G[b].pb(a);
  }
  parent[1]=-1;
  dfs1(1);
  rep(i,q){
    int p;cin>>p>>tmp;
    cnt[p]+=tmp;
  }
  dfs(1);
  rep1(i,n) cout<<cnt[i]<<" ";
}
signed main() {
    // your code goes here
    IOS
    ll t=1;
    //cin>>t;
    rep1(i,t){
        solve(); 
    }
}

Measured memory_bytes: 21120
#include<cstdio>

using namespace std;

typedef long long ll;

int main(){
	ll a, b, x; scanf("%lld %lld %lld", &a, &b, &x);
	ll res = b / x;
	if(a == 0) res++;
	else res -= (a - 1) / x;
	printf("%lld\n", res);
	return 0;
}

Measured memory_bytes: 128
//raja1999

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string> 
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

//std::ios::sync_with_stdio(false);

main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t,t1;
	//cin>>t;
	t=1;
	t1=t;
	while(t--){
		int n;
		cin>>n;
		string s;
		cin>>s;
		int i;
		rep(i,s.length()){
			cout<<char((s[i]-'A'+n)%26+'A');
		}
		cout<<endl;
	}
	return 0;
} 
	

Measured memory_bytes: 256
#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; cin >> n;
    vint a(n); vin(a);
    int min = *min_element(all(a));
    int max = *max_element(all(a));

    int ans = INT_MAX;

    for(int x = min; x <= max; ++x) {
        int cost = 0;
        rfor(c, a) {
            int d = abs(c - x);
            cost += d * d;
        }
        chmin(ans, cost);
    }
    print(ans);

    return 0;
}


Measured memory_bytes: 256
import fileinput

n = int(input())

a = list(map(int, input().split()))

b = True

for i in range(n):
    aa = a[i]
    if aa % 2 != 0:
        continue
    if aa % 3 != 0 and aa % 5 != 0:
        b = False
        break

if b:
    print("APPROVED")
else:
    print("DENIED")



Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define MOD7 1000000007
#define MOD9 1e9 + 9
#define SCD(t) scanf("%d",&t)
#define SCLD(t) scanf("%ld",&t)
#define SCLLD(t) scanf("%lld",&t)
#define SCC(t) scanf("%c",&t)
#define SCS(t) scanf("%s",t)
#define SCF(t) scanf("%f",&t)
#define SCLF(t) scanf("%lf",&t)
#define MEM(a, b) memset(a, (b), sizeof(a))
typedef long long ll;
typedef long double ld;
typedef string str;
typedef double d;
typedef unsigned u;
typedef unsigned long long ull;

const long long BIGINF = 2e18 + 7;
const int INF = 2e9 + 7;


const int N = 2e5 + 5;
int factorial[N];

int mul(int x, int y) {
	return 1LL * x * y % MOD7;
}

int power(int x, int exp) {
	int res = 1;
	while (exp) {
		if (exp & 1) {
			res = mul(res, x);
		}
		x = mul(x, x);
		exp >>= 1;
	}
	return res;
}


int inv(int x) {
	return power(x, MOD7 - 2);	
}

int binomial(int x, int y){
	if (x < y) return 0;
	return mul(factorial[x], inv(mul(factorial[y], factorial[x - y])));
}

int sub(int x, int y) {
	int k = x - y;
	if (k < 0) k += MOD7;
	return k;
}


int main () {
	/*#ifndef ONLINE_JUDGE
		freopen("inputf.txt", "r", stdin);
		freopen("outputf.txt", "w", stdout);
	#endif*/
	int n, k;
	SCD(n);
	SCD(k);
	int x;
	factorial[0] = 1;
	for (int i = 1; i <= N; i++) {
		factorial[i] = mul(factorial[i - 1], i);
	}
	vector<int> v;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		SCD(x);
		v.push_back(x);
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < n - 1; i++) {
		int diff = sub(v[i + 1], v[i]);
		int num_ways = binomial(n, k);
		num_ways = sub(num_ways, binomial(i + 1, k));
		num_ways = sub(num_ways, binomial(n - i - 1, k));
		ans = (ans + mul(diff, num_ways)) % MOD7;
	}
	printf("%d", ans);
    return 0;
}



Measured memory_bytes: 1660
from collections import deque

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

l, que = 0, deque([])
for i in s:
    que.append(i)
    if i == '(':
        l += 1
    if i == ')':
        if l == 0:
            que.appendleft('(')
        else:
            l -= 1
print(*que, ')' * l, sep='')


Measured memory_bytes: 65168
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let n: i64 = read();

    let mut e = vec![0; n as usize + 1];

    for i in 2..n + 1 {
        let mut cur = i;
        for j in 2..i + 1 {
            while cur % j == 0 {
                e[j as usize] += 1;
                cur /= j;
            }
        }
    }
    let num = |m| e.iter().filter(|&&x| x >= m - 1).count() as i64;

    println!(
        "{}",
        num(75)
            + num(25) * (num(3) - 1)
            + num(15) * (num(5) - 1)
            + num(5) * (num(5) - 1) * (num(3) - 2) / 2
    );
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


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

int main(){
  int N,a;
  cin >> N >> a;
  vector<string>str(N);
  for(int i=0;i<N;i++){
    cin >> str.at(i);
  }
  sort(str.begin(),str.end());
  string s;
  for(int i=0;i<N;i++){
    s+=str.at(i);
  }
  cout << s << endl;
}
  

Measured memory_bytes: 256
D = [int(_) for _ in input().split()]

def solve(D):
    N = D[0]
    M = D[1]
    K = D[2]
    
    for i in range(N+1):
        for j in range(M+1):
            if (i*(M-j) + (N-i)*j) == K:
                return "Yes"

    return "No"

print(solve(D))

Measured memory_bytes: 3060
N = input()
a = [ int(n) for n in input().split()]
a.sort(reverse=True)
A = B = 0
while len(a) > 0:
	A += a.pop(0)
	if len(a) < 1:
		break
	else:
		B += a.pop(0)
print(str(A-B))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const ll mod = 1e9 + 7;
const int maxn = 3e5 + 10;
ll ans = 1, num[maxn];
int n, k, vis[maxn];
vector <int> g[maxn];

void dfs(int t){
	vis[t] = 1;
	int x = k-2;
	if(t==1) x++;
	if(x<0) x = 0;
	for(auto i : g[t]){
		if(vis[i]) continue;
		num[i] = x--;
		dfs(i);
	}
}

int main() {
	scanf("%d %d", &n, &k);
	for(int i=0, u, v; i<n-1; i++){
		scanf("%d %d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	num[1] = k;
	dfs(1);
	for(int i=1; i<=n; i++){
		(ans *= num[i]) %= mod;
	}
	
	printf("%lld\n", ans);
}

Measured memory_bytes: 16000
#include<bits/stdc++.h>
#define ll long long
#define uint unsigned
#define ull unsigned ll
#define db double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define vi vector<int>
#define vpi vector<pii >
#define IT iterator
 
#define PB push_back
#define MK make_pair
#define LB lower_bound
#define UB upper_bound
#define y1 wzpakking
#define fi first
#define se second
#define BG begin
#define ED end
 
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(a))
#define sqr(x) (1ll*x*x)
 
#define LS3 k*2,l,mid
#define RS3 k*2+1,mid+1,r
#define LS5 k*2,l,mid,x,y
#define RS5 k*2+1,mid+1,r,x,y
#define GET pushdown(k);int mid=(l+r)/2
#define inf (1<<30)
using namespace std;
const int N=200005;
int n,mo,res,a[N];
bool check(int d){
	for (int l=2*n-d+1,r=2*n;l<=r;l++,r--)
		if (a[l]+a[r]<mo) return 0;
	return 1;
}
int main(){
	scanf("%d%d",&n,&mo);
	For(i,1,2*n) scanf("%d",&a[i]);
	sort(a+1,a+2*n+1);
	int l=1,r=n,ans=0;
	while (l<=r){
		int mid=(l+r)/2;
		if (check(mid*2)) ans=mid,l=mid+1;
		else r=mid-1;
	}
	ans*=2;
	for (int l=1,r=2*n-ans;l<=r;++l,--r)
		res=max(res,a[l]+a[r]);
	for (int l=2*n-ans+1,r=2*n;l<=r;++l,--r)
		res=max(res,a[l]+a[r]-mo);
	printf("%d\n",res);
}

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

#define N_MAX 10002
#define D_MAX 102
#define ll long long

using namespace std;

const ll MOD = 1e9+7;

int n;

int k[N_MAX];

int d;

ll dp[N_MAX][D_MAX][2];

int modd (int a, int b)
{
    return (a % d - b % d + d) % d;
}

int main()
{
    string s;
    cin >> s;
    n = s.size();
    for(int i = 1; i <= n; i++)
        k[i] = s[n - i] - '0';
    cin >> d;
    dp[0][0][true] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j < d; j++)
        {
            for(int c = 0; c <= 9; c++)
            {
                if(c > k[i])
                    dp[i][j][false] += dp[i - 1][modd(j, c)][false] + dp[i - 1][modd(j, c)][true];
                if(c < k[i])
                    dp[i][j][true] += dp[i - 1][modd(j, c)][false] + dp[i - 1][modd(j, c)][true];
                if(c == k[i])
                {
                    dp[i][j][false] += dp[i - 1][modd(j, c)][false];
                    dp[i][j][true] += dp[i - 1][modd(j, c)][true];
                }
            }
            dp[i][j][false] %= MOD;
            dp[i][j][true] %= MOD;
        }
    cout << (dp[n][0][true] - 1 + MOD) % MOD << "\n";
    return 0;
}


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

#define MAX_M 1000000

int memo[MAX_M + 1];

int f(int n) {
  if(n % 2 == 0) return n / 2;
  return 3 * n + 1;
}

int main() {
  int s, a;

  std::cin >> s;

  a = s;
  memo[a]++;
  int ans = 1;
  while(memo[a] < 2) {
    a = f(a);
    memo[a]++;
    ans++;
  }

  std::cout << ans << std::endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << endl
#define debugArray(x, n)                           \
  for (long long hoge = 0; (hoge) < (n); ++(hoge)) \
  cerr << #x << "[" << hoge << "]: " << x[hoge] << endl
using namespace std;

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long A, V, B, W, T;
  cin >> A >> V >> B >> W >> T;
  if (B < A) swap(A, B);
  long long tmp = B + W * T - (A + V * T);
  cout << (tmp > 0 ? "NO" : "YES") << endl;
  return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define LLINF 9223372036854775807
#define MOD ll(1e9+7)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr<<#x<<": "<<x<<endl


int main(){
    ll k, x;
    cin >> k >> x;

    int s = x-k+1;
    for(int i = 0; i < 2*k-1; i++){
        cout << s + i << " ";
    }
    cout << endl;
    return 0;

}


Measured memory_bytes: 256
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]



H, W = LI()

ans = H*W

if H == 1 or W == 1:
    print(1)
elif ans%2 == 0:
    print(int(ans/2))
else:
    print(int(ans//2 + 1))

Measured memory_bytes: 38384