akhauriyash/Code-Regression huggingface dataset:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


class Combination:
    def __init__(self, n, mod):

        g1 = [1, 1]
        g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, n + 1):
            g1.append((g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            g2.append((g2[-1] * inverse[-1]) % mod)
        self.MOD = mod
        self.N = n
        self.g1 = g1
        self.g2 = g2
        self.inverse = inverse

    def __call__(self, n, r):
        if (r < 0 or r > n):
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n - r] % self.MOD


# --------------------------------------------

dp = None


def main():
    S = input()

    np = S.count("p")

    print((len(S) // 2) - np)


main()


Measured memory_bytes: 4932
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define mod 1000000007
typedef long long ll;
using namespace std;

int main(){
  int a, b;
  cin >> a >> b;
  cout << (a+b)%24 << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <cmath>
#include <functional>
using namespace std;
#define MOD 998244353
#define INF 1<<30
#define LINF (ll)1<<62
#define MAX 510000
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
#define uni(q) unique(all(q)),q.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;
const int mod = 1e9 + 7;

int main(){
    ll h,w; cin >> h >> w;
    ll a[h][w];
    rep(i,h) rep(j,w) cin >> a[i][j];
    ll cnt = 0;
    vpl ans;
    rep(i,h){
        rep(j,w){
            ll yoko = i%2 ? w-j-1 : j;
            ll nxt = i%2 ? -1 : 1;
            if((i%2 && yoko==0) || (i%2==0 && yoko==w-1)){
                if(i==h-1) break;
                if(cnt==0){
                    if(a[i][yoko]%2==1){
                        ans.push_back(P(i+1,yoko+1));
                        ans.push_back(P(i+2,yoko+1));
                        cnt++;
                    }
                }else{
                    if(a[i][yoko]%2==0){
                        ans.push_back(P(i+1,yoko+1));
                        ans.push_back(P(i+2,yoko+1));
                    }else{
                        cnt--;
                    }
                }
            }else{
                if(cnt==0){
                    if(a[i][yoko]%2==1){
                        ans.push_back(P(i+1,yoko+1));
                        ans.push_back(P(i+1,yoko+1+nxt));
                        cnt++;
                    }
                }else{
                    if(a[i][yoko]%2==0){
                        ans.push_back(P(i+1,yoko+1));
                        ans.push_back(P(i+1,yoko+1+nxt));
                    }else{
                        cnt--;
                    }
                }
            }
        }
    }
    ll n = ans.size();
    cout << n/2 << endl;
    for(ll i=0; i<n; i+=2){
        printf("%lld %lld %lld %lld\n",ans[i].first,ans[i].second,ans[i+1].first,ans[i+1].second);
    }
}

Measured memory_bytes: 8432
#include<bits/stdc++.h>
#define int long long
#define register rg
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
using namespace std;
typedef long long ll;
main() {
	//file("a");
	int maxx=0,a=0,n,ans=0;
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>a;
		maxx=max(maxx,a);
		if(a==maxx)
		ans++; 
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>){
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map(String::toInt).toIntArray()
    val b = readLine()!!.split(" ").map(String::toInt).toIntArray()

    var ans = 0L
    for(i in 0 until n){
        if(a[i] >= b[i]){
            ans += b[i]
        }else if(a[i] + a[i+1] < b[i]){
            ans += (a[i] + a[i+1])
            a[i+1] = 0
        }else{
            ans += b[i]
            a[i+1] -= (b[i] - a[i])
        }
    }
    println(ans)
}

Measured memory_bytes: 82724
#include<bits/stdc++.h>
using namespace std;
string s;
int main()
{
	ios::sync_with_stdio(false);
	cin>>s;
	int ans=0;
	for(int i=0;i<(int)s.size()/2;i++)
		if(s[i]!=s[s.size()-i-1])
			ans++;
	cout<<ans<<endl;
	return 0;
}

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

int main() {
    int n, m;
    int edge[10][10];
    cin >> n >> m;
    vector<int> v(n - 1);
    for (int i = 0; i < n - 1; ++i)
    {
        v[i] = i + 1;
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            edge[i][j] = 0;
        }
    }
    for (int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b;
        edge[a - 1][b - 1] = edge[b - 1][a - 1] = 1;
    }
    int ans = 0;
    do
    {
        int p = 0, f = 1;
        for (int i : v)
        {
            if (!edge[p][i])
            {
                f = 0;
                break;
            }
            p = i;
        }
        if (f)
        {
            ++ans;
        }
    } while (next_permutation(v.begin(), v.end()));
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 256
/*1000000ÈºÌfÅüÍµ½nÈºÌÅåÌfðoÍ·évO*/
#include <iostream>
const int MAX = 1000001;
const int P_NUM = 78498;
using namespace std;

bool p[MAX];
int a[79000]={};

void f(){
    for(int i=0 ; i<MAX ; i++){
        p[i] = (i<=1)? false : true ;
    }
    for(int i=2 ; i*i<= MAX+1 ; i++){
        if( p[i] ){
            for(int j=i*2 ; j<MAX ; j+=i){
                p[j] = false;
            }
        }
    }
	for(int i=2,j=0; i<MAX ; ++i ){
		if(p[i])
			a[j++] = i;
	}
}

int main(){
    int n;

    f();

    while( cin >> n , n ){
		int ans = 0;
		for(int i=0 ; i<n ; ++i )
			if( p[i] && p[n-i] && (n-i) >= i)
				ans++;
		cout << ans << endl;
    }
}

Measured memory_bytes: 0
#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
	int a,b;
	while(1){
	scanf("%d%d",&a,&b);
	if(a+b==0)return a+b;
	pair<int ,int > place[100];
	for(int i=0;i<b;i++)place[i]=make_pair(0,i+1);
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			int t;
			scanf("%d",&t);
			place[j]=make_pair(place[j].first-t,place[j].second);
		}
	}
	std::sort(place,place+b);
	for(int i=0;i<b-1;i++){
		printf("%d ",place[i].second);
	}
	printf("%d\n",place[b-1].second);
	}
}

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

// @@ !! LIM()

int main(/* int argc, char *argv[] */) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll X; cin >> X;
  ll g = gcd(X, 360);
  cout << 360 / g << endl;

  return 0;
}



Measured memory_bytes: 3672
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;

template<class T> inline T sqr(T x) {return x*x;}

int main() {
    string s;
    cin >> s;
    int pos = 0;
    int cnt = 0;
    REP(i,1,s.size()) {
        if (s[i-1] != s[i]) {
            pos = i;
            ++cnt;
        }
    }
    cout << cnt << endl;
    
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define WHATIS(x) cout << #x << " is " << x << endl;
#define ERROR(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x

using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << *it << " = " << a << endl;
    err(++it, args...);
}

const ll MODBASE = 1000000007LL;
const int MAXN = 100010;
const int MAXM = 35;
const int MAXK = 510;
const int MAXQ = 200010;

// class ReconstructNumber {
// public:
//     string smallest(string);
// };

// string ReconstructNumber::smallest(string s) {
// }

int n, a[MAXN];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n;
    FOR(i,1,n) cin >> a[i];
    sort(a+1, a+n+1);
    cout << a[n / 2 + 1] - a[n / 2];
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
// URDL
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
long long mod = 1e9+7;
//

int main(){
  int h, w; cin >> h >> w;
  vector<string> s(h);
  for(int i=0; i<h; i++) cin >> s[i];

  vector< vector<int> > l(h, vector<int>(w, 0));
  vector< vector<int> > r(h, vector<int>(w, 0));
  vector< vector<int> > u(h, vector<int>(w, 0));
  vector< vector<int> > d(h, vector<int>(w, 0));
  for(int i=0; i<h; i++) {
    int cnt = 0;
    for(int j=0; j<w; j++) {
      if(s[i][j] == '.') cnt++;
      else cnt = 0;
      l[i][j] = cnt;
    }
    cnt = 0;
    for(int j=w-1; j>=0; j--) {
      if(s[i][j] == '.') cnt++;
      else cnt = 0;
      r[i][j] = cnt;
    }
  }
  for(int j=0; j<w; j++) {
    int cnt = 0;
    for(int i=0; i<h; i++) {
      if(s[i][j] == '.') cnt++;
      else cnt = 0;
      u[i][j] = cnt;
    }
    cnt = 0;
    for(int i=h-1; i>=0; i--) {
      if(s[i][j] == '.') cnt++;
      else cnt = 0;
      d[i][j] = cnt;
    }
  }
  int ans = 0;
  for(int i=0; i<h; i++) {
    for(int j=0; j<w; j++) {
      int tmp = l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3;
      ans = max(ans, tmp);
    }
  }
  cout << ans << endl;

  return 0;
}




// EOF


Measured memory_bytes: 67200
import sys

def main():
    line = sys.stdin.readline()
    lst = line.split()
    a = lst[0]
    b = lst[1]
    c = lst[2]

    if a[-1] == b[0] and b[-1] == c[0]:
        print("YES")
    else:
        print("NO")
    return 0

if __name__ == '__main__':
    sys.exit(main())


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

int main(){
    int a,p,d;
    cin>>a>>p;
    a=a*3;
    p=a+p;
    d=0;
    while (p>1){
     p=p-2;
     d=d+1;   
    }
      cout<<d<<endl;
return 0;
}

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

using namespace std;
const int ma=1e9;
int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	int a;
	cin>>a;
	int p[a];
	int q[a];
	for(int i=1;i<=a;i++) cin>>p[i];
	for(int i=1;i<=a;i++){
		q[i]=i;
		
		
	}
	int c=-1;
	for(int i=1;i<=a;i++){
		if(p[i]!=q[i]){
			c++;
		}
	} 
	if(c==1 || c==-1) cout<<"YES";
	else cout<<"NO";
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] w = new int[n];
        int[] e = new int[n];
        int countw = 0;
        int counte = 0;
        char[] s = sc.next().toCharArray();
        for (int i = 0; i < n; i++) {
            if (s[i] == 'W') {
                countw++;
                w[i] += countw;
                e[i] = counte;
            } else if (s[i] == 'E') {
                counte++;
                e[i] += counte;
                w[i] = countw;
            }
        }
        int min = e[n - 1] - e[0];
        for (int i = 1; i < n - 1; i++) {
            int now = (w[i - 1]) + (e[n - 1] - e[i]);
            min = Math.min(now, min);
        }
        min = Math.min(w[n - 2], min);
        System.out.println(min);
    }
}


Measured memory_bytes: 45156
class Main
  str = gets
  str = str.split(" ")
  w = str[0].to_i
  h = str[1].to_i
  x = str[2].to_i
  y = str[3].to_i
  r = str[4].to_i
  if w >= (x + r) && h >= (y + r) && 0 <= (x - r) && 0 <= (y - r)
    puts "Yes"
  else 
    puts "No"
  end
end


Measured memory_bytes: 6876
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x) (x).begin(), (x).end()
#define rep(i, s, n) for (i64 i = (s), i##_limit = (n); i < i##_limit; ++i)
#define repr(i, s, t) for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define var(type, ...) \
    type __VA_ARGS__;  \
    read(__VA_ARGS__);
#ifndef DBG
#define dump(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U>
inline bool chmax(T &a, const U &b) {
    return b > a && (a = b, true);
}
template <class T, class U>
inline bool chmin(T &a, const U &b) {
    return b < a && (a = b, true);
}
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
inline vector<T> makeV(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto makeV(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(makeV<T>(initValue, args...))>(
        sz, makeV<T>(initValue, args...));
}

template <class T>
inline istream &operator>>(istream &is, vector<T> &vec) {
    for (auto &e : vec) is >> e;
    return is;
}

inline void read() {}

template <class Head, class... Tail>
inline void read(Head &head, Tail &... tail) {
    cin >> head;
    read(tail...);
}

inline void print() { cout << "\n"; }

template <class Head, class... Tail>
inline void print(Head &&head, Tail &&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream &operator<<(ostream &os, const vector<T> &vec) {
    static constexpr const char *delim[] = {" ", ""};
    for (const auto &e : vec) os << e << delim[&e == &vec.back()];
    return os;
}

template <class Container>
struct Rev {
    Container &x_;
    inline Rev(Container &x) : x_(x) {}
    inline auto begin() { return rbegin(x_); }
    inline auto end() { return rend(x_); }
};
// }}} End Header

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    var(int, N);
    i64 ans = 1;
    rep(i, 0, N) {
        var(i64, x);
        ans = ans / __gcd(ans, x) * x;
    }
    print(ans);

    return 0;
}


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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) std::cout << x << '\n'
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define sz(x) ((int)(x).size())
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };
const int INF = (int)1e9;
const ll  inf = (ll)1e18;
const int mod = 1000000007;
const int MAX_N = 100010;
const double PI = acos(-1);

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	/*------------------------------*/

	int N, M;
	cin >> N >> M;

	vector<vector<int>> vec(M);

	rep(i, M) {
		int k;
		cin >> k;
		vec[i].resize(k);
		rep(j, k) {
			cin >> vec[i][j];
			vec[i][j]--;
		}
	}

	vector<int> p(M);
	rep(i, M) cin >> p[i];

	ll res = 0;
	for (int bit = 0; bit < (1 << N); bit++) {
		bool ok = true;
		for (int i = 0; i < M; i++) {
			int con = 0;
			for (auto v : vec[i]) {
				if (bit & (1 << v)) con++;
			}
			if (con % 2 != p[i]) ok = false;
		}
		if (ok) res++;
	}

	out(res);

	return 0;
}

Measured memory_bytes: 256
s=list(input())
t=list(input())
s.sort()
t.sort()
if s==t and s.count(s[0])==len(s) and t.count(s[0])==len(t):
    print('No')
elif s.count(s[0])==len(s) and t.count(s[0])==len(t):
    if len(s)<len(t):
      print('Yes')
    else:
      print('No')
else:
    if ord(s[0])==ord(t[-1]):
      print('No')
    elif ord(s[0])<ord(t[-1]):
      print('Yes')
    else:
      print('No')

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

int main(){
    string a,b,ans;
    cin>>a>>b;
    int asize=a.size(),bsize=b.size();
    int num=(asize>bsize)?asize:bsize;
    for(int i = 0; i < num;i++){
        ans += a[i];
        if(b[i]<'a' || b[i]>'z'){
            break;
        }
        ans += b[i];
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <algorithm>
#include <functional>
#include <vector>
#include <typeinfo>
#include <climits>
using namespace std;
#define INIT cin.tie(0); ios::sync_with_stdio(false);
#define FOR(i, a, n) for (int i = a; i < n; i++)
#define REP(i, n) for(int i = 0; i < n; i++)

int main()
{
    INIT;

    int A[3];
    REP(i, 3) cin >> A[i];
    sort(A, A + 3);
    if(A[0] == 5 and A[1] == 5 and A[2] == 7) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>

using namespace std;

int main(){

  int length;
  
  string inputString;
  
  cin >> length >> inputString;
  
  if(inputString.length() <= length){
    cout << inputString << endl;
  }
  else{
    string res = "";
    for(int i = 0; i < length; i++){
      res += inputString[i];
    }
    res += "...";
    cout << res << endl;
  }
  
  return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <sstream>
#include <numeric>
// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>

///////////////////////////////////////////////////////////////
// namespace
///////////////////////////////////////////////////////////////
using namespace std;
// namespace mp = boost::multiprecision;

///////////////////////////////////////////////////////////////
// types
///////////////////////////////////////////////////////////////
using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
// using mpi = mp::cpp_int;
// using mpf = mp::number<mp::cpp_dec_float<1024>>;

///////////////////////////////////////////////////////////////
// mod https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a
///////////////////////////////////////////////////////////////
// ll MOD = 1000000007;
// ll mod(long long val) {
//     long long res = val % MOD;
//     if (res < 0) res += MOD;
//     return res;
// }
// ll modinv(ll a) {
//     ll b = MOD, u = 1, v = 0;
//     while (b) {
//         ll t = a / b;
//         a -= t * b; swap(a, b);
//         u -= t * v; swap(u, v);
//     }
//     u %= MOD;
//     if (u < 0) u += MOD;
//     return u;
// }

int N, Q;

map<int, vector<int>> m;
ll arr[200005];
ll ans[200005];
queue<pii> q;

int main() {
    cin >> N >> Q;
    for (int i = 0; i < N - 1; ++i) {
        int a, b;
        cin >> a >> b; --a; --b;
        m[a].push_back(b);
        m[b].push_back(a);
    }
    memset(arr, 0, sizeof(arr));
    memset(ans, -1, sizeof(ans));
    for (int i = 0; i < Q; ++i) {
        ll p, x;
        cin >> p >> x; --p;
        arr[p] += x;
    }

    q.push(make_pair(0, 0));
    while (!q.empty()) {
        ll node = q.front().first;
        ll s = q.front().second;
        q.pop();
        // cout << "queue: " << node << " " << s << endl;
        s += arr[node];
        ans[node] = s;
        for (auto &next : m[node]) {
            // cout << "  next: " << next << endl;
            if (ans[next] != -1) continue;
            q.push(make_pair(next, s));
        }
    }
    for (int i = 0; i < N; ++i) {
        if (i != 0) cout << " ";
        cout << ans[i];
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 29684
#include<iostream>
#include<string>

using namespace std;

int main() {
	string s;
	cin >> s;
	int n = s.size();
	int c = 0;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'S') {
			if (c <= 0) {
				c = 0;
			}
			c++;
		}
		else {
			c--;
			if (c < 0) {
				ans++;
			}
		}
	}
	cout << ans*2 << endl;
	return 0;
}

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

using namespace std;

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

using ll = long long;

vector<ll> factorial(ll x) {
  vector<ll> res;
  for (ll i = 1L; i * i <= x; i++) {
    if (x % i == 0) {
      res.emplace_back(i);
      res.emplace_back(x/i);
    }
  }
  return res;
}

// 8 / 7 == 8 % 7
// 1     == 1

// 8 / 3 == 8 % 3
// 2     == 2

int main() {
  ll N;
  cin >> N;

  ll res = 0L;
  vector<ll> fs = factorial(N);
  REP(i,fs.size()) {
    ll x = fs[i];
    ll m = (N - x) / x;
    if (m != 0 && N / m == N % m)  {
      res += m;
    }
  }

  cout << res << endl;

  return 0;
}


Measured memory_bytes: 384
#include <stdio.h>
#include <string.h>


int main(void) {
	int a, b, i;
	for (i = 0; i < 3000; i++) {
		scanf("%d %d", &a, &b);
		if (a == 0 && b == 0) break;
		(a > b) ? printf("%d %d\n", b, a) : printf("%d %d\n", a, b);

	}
	

	return 0;
}

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

int main() {
  int N, x, y;
  cin >> N;
  int a0=0,a1=0,a2=0,a3=0,a4=0,a5=0,a6=0,a7=0,a8=0;
  if (N >= 100000000) {
    a0 = N / 100000000;
  }
  if (N >= 10000000) {
    a1 = N / 10000000 - a0 * 10;
  }
  if (N >= 1000000) {
    a2 = N / 1000000 - a0*100 - a1*10;
  }
  if (N >= 100000) {
    a3 = N/100000 - a0*1000 - a1*100 - a2*10;
  }
  if (N >= 10000) {
    a4 = N/10000 - a0*10000 - a1*1000 - a2*100 - a3*10;
  }
  if (N >=1000) {
    a5 = N/1000 - a0*100000 - a1*10000 - a2*1000 - a3*100 - a4*10;
  }
  if (N >= 100) {
    a6 = N/100 - a0*1000000 - a1*100000 - a2*10000 - a3*1000 - a4*100 - a5*10;
  }
  if (N >=10) {
    a7 = N/10 - a0*10000000 - a1*1000000 - a2*100000 - a3*10000 - a4*1000 - a5*100 - a6*10;
  }
  if (N >= 1) {
    a8 = N - a0*100000000 - a1*10000000 - a2*1000000 - a3*100000 - a4*10000 - a5*1000 - a6*100 - a7*10;
  }
  x = a0 + a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8;
  y = N % x;
  if (y == 0) {
    cout << "Yes" << endl;
    //cout << x << endl;
  }
  else {
    cout << "No" << endl;
    //cout << x << endl;
  }
}

Measured memory_bytes: 256
N = int(input())
L = list(map(int,input().split()))
L.sort()
cnt = 0

import bisect
for i in range(N):
  for j in range(i+1,N-1):
    insert = bisect.bisect_left(L,L[i]+L[j]) -j -1
    cnt += insert
        
print(cnt)

Measured memory_bytes: 3188
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vi k(n), l(n), r(n);
        rep(i, n) {
            cin >> k[i] >> l[i] >> r[i];
            k[i]--;
        }

        vector<tuple<int, int, int> > tt;
        rep(i, n) {
            if(l[i] > r[i]) tt.emplace_back(k[i], l[i], r[i]);
        }
        sort(rall(tt));
        ll res = 0;
        PQ<P> q;
        int j = 0;
        for(int i = n-1; i >= 0; i--) {
            while(j != tt.size() and get<0>(tt[j]) == i) {
                int lh, rh;
                tie(ignore, lh, rh) = tt[j];
                q.emplace(lh-rh, j);
                j++;
            }

            if(!q.empty()) {
                res += get<1>(tt[q.top().second]);
                q.pop();
            }
        }
        while(!q.empty()) {
            res += get<2>(tt[q.top().second]);
            q.pop();
        }

        tt.clear();
        rep(i, n) {
            if(l[i] <= r[i]) tt.emplace_back(k[i], l[i], r[i]);
        }
        sort(all(tt));
        j = 0;
        rep(i, n) {
            while(j != tt.size() and get<0>(tt[j]) == i-1) {
                int lh, rh;
                tie(ignore, lh, rh) = tt[j];
                q.emplace(rh-lh, j);
                j++;
            }

            if(!q.empty()) {
                res += get<2>(tt[q.top().second]);
                q.pop();
            }
        }
        while(j != tt.size()) {
            res += get<1>(tt[j]);
            j++;
        }
        while(!q.empty()) {
            res += get<1>(tt[q.top().second]);
            q.pop();
        }

        cout << res << '\n';
    }
}

Measured memory_bytes: 7284
import sys

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

if a[0] == 0:
    print(0)
else:
    ans = 1
    while a:
        ans *= a.pop()
        if ans > 10**18:
            print(-1)
            sys.exit()
    print(ans)

Measured memory_bytes: 21636
#include <cstdio>
#include <vector>
#include <iostream>

const int MAX_SIZE = 1000;
char field[MAX_SIZE + 1][MAX_SIZE + 1];

const int STEP_NUM = 4;
const int STEP[STEP_NUM][STEP_NUM] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

using Position = std::pair<int,int>;

const int MAXN = 10;
Position locations[MAXN];
 
int H, W, N;

int get_shortest_distance(int current_HP)
{
	int sx = locations[current_HP-1].first;
	int sy = locations[current_HP-1].second;
	int ex = locations[current_HP].first;
	int ey = locations[current_HP].second;

	bool is_visit[MAX_SIZE + 1][MAX_SIZE + 1]={};
	is_visit[sx][sy]=true;

	std::vector<Position> frontier;
	frontier.push_back(Position{sx,sy});
	for(int step=0;step<W*H;step++)
	{
		std::vector<Position> next_frontier;
		for(auto p:frontier)
			for(int i=0;i<STEP_NUM;i++)
			{
				int nx = p.first+STEP[i][0];
				int ny = p.second+STEP[i][1];
				if(nx==ex && ny==ey)	return step+1;
				if(nx<0 || H<=nx) 		continue;
				if(ny<0 || W<=ny) 		continue;
				if(field[nx][ny]=='X') 	continue;
				if(is_visit[nx][ny]) 	continue;
				next_frontier.push_back(std::make_pair(nx,ny));
				is_visit[nx][ny] = true;
			}
		frontier = next_frontier;
	}
	return -1;
}

int solve()
{
	int total_step = 0;
	for(int i=1;i<N+1;i++)
		total_step += get_shortest_distance(i);
	return total_step;
}

int main()
{
	scanf("%d %d %d", &H, &W, &N);
	for(int i=0; i<H; i++)
		scanf("%s", field[i]);
	for(int i=0; i<H; i++)
		for(int j=0; j<W; j++)
		{
			if(field[i][j]=='S')
				locations[0] = std::make_pair(i,j);
			if(isdigit(field[i][j]))
				locations[field[i][j]-'0'] = std::make_pair(i,j);
		}
	printf("%d\n", solve());
	return 0;
}

Measured memory_bytes: 5088
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
using namespace std;
//cout <<  << endl;
typedef long long int ll;
typedef long double ld;

using Graph = vector<vector<ll>>;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

#define MAX_N 2010

const long long INF = 1LL << 60;

//境界値に注意！！！

int main() {
    ll a,b,k;
    cin >> a >> b >> k;
    if (a+k-1>=b-k+1){
        for (ll i=a;i<=b;i++){
            cout << i << endl;
        }
        return 0;
    }
    for (ll i=0;i<k;i++)cout << a+i << endl;
    for (ll i=k-1;i>=0;i--)cout << b-i << endl;
    return 0;
}


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

int main(){
    int n;
    cin >> n;
    map<int,int> a;

    for(int i=0,in; i<n; i++){
        cin >> in;
        if(a.count(in) == 0){
            a[in];
        }else{
            a.erase(in);
        }
    }

    cout << a.size() << endl;
}

Measured memory_bytes: 4864
a,b = map(int,input().split())

ab =[]
ba = []

for i in range(b):
  ab.append(str(a))
  
for i in range(a):
  ba.append(str(b))

ab.sort()
ba.sort()

if ab < ba:
  print("".join(ab))
else: 
  print("".join(ba))

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

double solve(vector<double> &p,int n,int x,vector<vector<double> > &dp) {
    if(x==0) {
        return 1;
    }
    if(n==0) {
        return 0;
    }
    if(dp[n][x]>-0.9) {
        return dp[n][x];
    }
    return dp[n][x] = p[n]*solve(p,n-1,x-1,dp) + (1-p[n])*solve(p,n-1,x,dp);
}

int main() {
	int n;
	cin>>n;
	vector<double> p(n+1);
	for(int i=1;i<=n;i++) {
	    cin>>p[i];
	}
	vector<vector<double> > dp(n+1,vector<double>(n+1,-1));
	cout<<fixed<<setprecision(10)<<solve(p,n,(n+1)/2,dp);
	return 0;
}


Measured memory_bytes: 74016
/********   All Required Header Files ********/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

typedef long long ll;

using namespace std;

int main() {
    // your code goes here
    ll n , ans = 0 , k;

    vector<int> a;

    cin>>n>>k;

    while(n--){
        int x ; cin>>x;
        a.push_back(x);
    }

    sort(a.begin(),a.end());

    for(int i = 0 ; i < k ; i++){
        ans+=a[i];
    }


    cout<<ans;

    return 0;
}


Measured memory_bytes: 3648
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4") // wonderful

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

#define forn(i, a, n) for (int i = (a); i < (int)n; i++)
#define trav(x, arr) for (auto &x : arr)
#define sz(x) (int)x.size()
#define Matrix(m, h, w) = std::vector<vector<int>> m(h, vector<int> (w)); 
using ll = long long;

#define vi vector<int>
#define vl vector<long>
#define vll vector<ll>

// benq
const int MOD = 1000000007; // 998244353
const ll INF = 1e18;
const int MX = 100001;


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

    int a; cin >> a;
    cout << (a  + a * a + a * a * a);
    


    return 0;
}

Measured memory_bytes: 3664
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

int main()
{
    int n;
    cin >> n;
    multiset<int> ms;
    for(int i=0; i<n; ++i){
        int d;
        cin >> d;
        ms.insert(d);
    }

    int m;
    cin >> m;
    for(int i=0; i<m; ++i){
        int t;
        cin >> t;
        auto it = ms.find(t);
        if(it == ms.end()){
            cout << "NO" << endl;
            return 0;
        }
        ms.erase(it);
    }

    cout << "YES" << endl;
    return 0;
}


Measured memory_bytes: 9600
#include <stdio.h>
 
int main() {

	int N;
	scanf("%d", &N);
	    if(N <= 999){
		  printf("ABC\n");
	}
	
	    else if(N <=1998 && N >= 1000){
		  printf("ABD\n");
	}

	return 0;
}

Measured memory_bytes: 128
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(S: str):
    dp = [[0 for j in range(4)] for i in range(len(S) + 1)]
    STR = "XABC"
    dp[0][0] = 1
    for i in range(len(S)):
        c = S[i]
        for j in range(4):
            next = dp[i][j]
            if c == "?":
                next *= 3
                if j > 0:
                    next += dp[i][j-1]
            if STR[j] == c:  # 選んだ文字列が次選ぶべき文字列だったら
                next += dp[i][j-1]
            dp[i+1][j] = next % MOD
    #  print(dp)
    print(dp[len(S)][3])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)


if __name__ == '__main__':
    main()


Measured memory_bytes: 27636
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int Inf = 1000000001;
constexpr ll INF= 9 * 1e18;
constexpr ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<ll,ll> P;

int main() {
    ll S;
    cin >> S;
    ll ret1 = (S + 1000000000 - 1) / 1000000000;
    ll ret2 = ret1 * 1000000000 - S;
    cout << 0 << " " << 0 << " " << 1 << " " << 1000000000 << " " << ret1 << " " << ret2 << endl;
}

Measured memory_bytes: 256
N = int(input())
status_lst = [0] * (N-1)
for _ in range(N-1):
    status_lst[_] = list(map(int, input().split()))

# simple solution
# 0: C
# 1: S
# 2: F
# print(status_lst)

rev_res = []
for ix, st_i in enumerate(status_lst):
    elapsed = st_i[1] + st_i[0]
    for next_st in range(ix+1, N-1):
        st_n = status_lst[next_st]
        if elapsed < st_n[1]:
            elapsed = st_n[1] + st_n[0]
        else:
            wait_time = elapsed % st_n[2]
            if wait_time == 0:
                elapsed = elapsed + st_n[0]
            else:
                elapsed = elapsed + st_n[2] - (elapsed % st_n[2]) + st_n[0]
            # elif wait_time == elapsed:
            #     # elaplsed < F
            #     # ?
            #     elapsed = st_n[2] + st_n[0]
            # else:
            #     elapsed = elapsed + wait_time + st_n[0]

    rev_res.append(elapsed)

rev_res.append(0)

for ans in rev_res:
    print(ans)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,Q,K,A,B;
string S;
const ll MOD = 998244353;
//const ll MOD = (1e+9) + 7;
typedef pair<ll, ll> P;
const ll INF = (1LL<<60);

int main() {
    cin>>N>>M>>K;
    vec c(N);
    mat a(N, vec(M));
    rep(i,N){
        cin>>c[i];
        rep(j,M) cin>>a[i][j];
    }
    ll ans = INF;
    rep(s, 1<<N){
        vec sco(M, 0);
        ll temp = 0;
        rep(i,N){
            if((s>>i)&1){
                temp += c[i];
                rep(j,M) sco[j] += a[i][j];
            }
        }
        if(*min_element(ALL(sco)) >= K) ans = min(ans, temp);
    }
    cout<<(ans == INF ? -1 : ans)<<endl;
}

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

#define REPI(i, n) for(int i = 0; i < n; i++)
#define REPJ(j, n) for(int j = 0; j < n; j++)

using ll = long long;
using namespace std;

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

    char c; cin >> c;
    cout << (c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o'
            ? "vowel" : "consonant");
}


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

using namespace std;

int main()
{
    int n,mw,w,v,tv=0;
    long long int dp[100001];
    dp[0]=0;
    for(int i=1;i<100001;i++) dp[i]=1000000001;
    cin>>n>>mw;
    while(n--)
    {
        cin>>w>>v;
        tv+=v;
        for(int j=tv;j>=v;j--)
        {
            dp[j]=min(dp[j],w+dp[j-v]);
        }
    }
    for(int i=tv;i>=0;i--)
    {
        if(dp[i]<=mw)
        {
            cout<<i<<endl;
            return 0;
        }
    }
}


Measured memory_bytes: 1024
import sys
input = sys.stdin.readline

import numpy as np

"""
各数字ごとに左移動・右移動・そのまま使う。全部コスト1ならLIS。
左から見て、「最後にそのまま使った数、そこまでの数を並べるコスト」を持ってdp。
"""

N,A,B = map(int,input().split())
P = [int(x) for x in input().split()]

INF = 10**18
dp = np.full(N+1,INF,dtype=np.int64)
dp[0] = 0
for p in P:
    # pを置く
    dp[p] = dp[:p].min()
    # pを左移動
    dp[p+1:] += B
    # pを右移動
    dp[:p] += A

answer = dp.min()
print(answer)

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

int main(){
	int n, inp;
	map<int, int> m;
	cin >> n;
	for( int i = 0; i < n; ++i ){
		cin >> inp;
		m[inp]++;
	}

	cout << m.size() << endl;
	return 0;
}

Measured memory_bytes: 256
//Author: Fuadul Hasan(fuadul202@gmail.com)
#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int N   = 2e5 + 5;

int main(){
	
	int n,k;
	cin>>n>>k;
	int best = (n-1) * (n-2) / 2;
	if(k > best){
		cout<<-1<<endl;
		return 0;
	}
	//cout<<best<<endl;
	int rem  = best  - k;
	vector<pair<int,int>>ret;
	for(int i = 1;i<n;i++){
		ret.emplace_back(1,i+1);
	}

	for(int i=1;i<n and rem; i++){
		for(int j= i+1;j<n and rem; j++){
			ret.emplace_back(i+1,j+1);
			rem--;
		}
	}
	cout<<ret.size()<<endl;
	for(auto& it: ret){
		cout<<it.first<<" "<<it.second<<endl;
	}

	return 0;
}

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

int main() {
  int cnt = 0;
  int num;
  cin >> num;
  
  vector<long long> vec(num);
  for(int i = 0; i < num; i++){
    cin >> vec.at(i);
    
    // 2で割れるだけ割る
    while(vec.at(i) % 2 == 0){
      vec.at(i) /= 2;
      cnt++;
    }
  } 
  
  cout << cnt;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
const ll INF = 1000000000000000000;//10^18
const ll mod = 1000000007;
//printf("%.10f\n", n);
ll modpow(ll x, ll y, ll m = mod) {
	ll res = 1;
	while (y) {
		if (y % 2) { res *= x; res %= m; }
		x = x * x % mod; y /= 2;
	}
	return res;
}
ll X[123456];
signed main() {
	ll n = 0, k = 0, ma = 0, mi = 0, cnt = 1, sum = 1, ans = 0;
	cin >> n >> k; vector<ll> v(n);
	for (int h = 0; h < n; h++) {
		cin >> v[h];
	}
	sort(v.begin(), v.end());
	for (int h = 1; h < k; h++) { cnt *= h; cnt %= mod; }
	for (int h = 1; h < k; h++) { sum *= h; sum %= mod; }
	for (int h = k - 1; h < n; h++) {
		//h C k - 1
		ma += (sum * modpow(cnt, mod - 2) % mod) * v[h]; ma %= mod;
		sum *= modpow(h - k + 2, mod - 2); sum %= mod; sum *= h + 1; sum %= mod;
	}
	for (int h = 0; h <= n - k; h++) {
		sum *= modpow(n - h, mod - 2); sum %= mod; sum *= n - h - k + 1; sum %= mod;
		mi += (sum * modpow(cnt, mod - 2) % mod) * v[h]; mi %= mod;
	}
	ans = ma - mi;
	while (ans < 0) { ans += mod; }
	cout << ans % mod << endl;
	return 0;
}

Measured memory_bytes: 1024
/******Old_school_@15******/
#include<bits/stdc++.h>
using namespace std;
#define lld               long long int
#define ld                long double
#define pb                push_back
#define ppb               pop_back hellooitsme1
#define mp                make_pair
#define F                 first
#define S                 second
#define nl                '\n'
#define all(c)            (c).begin(),(c).end()
#define rall(c)           (c).rbegin(),(c).rend()
#define sz(c)             (c).size()
#define tr(x,a)           for(auto &a : x)
#define psnt(x,a)         (x).find(a)!=(x).end()
#define vpsnt(x,a)        find(all(x),a)!=(x).end()
#define lexichar(x,y)     lexicographical_compare(x,x+strlen(x),y,y+strlen(y)) //modify the ranges
#define lexistr(x,y)      lexicographical_compare(x.begin(),x.end(),y.begin(),y.end()) 
#define MOD               1000000007
#define pi                3.1415926536
#define tod               1
#define itr(i,a,b)        for(lld i=a;i<=b;i++)
#define itrn(i,a,b)       for(lld i=a;i>=b;i--)
#define iot(n)            for(lld i=0;i<n;i++)
#define pls(n,arr)        lld arr[n]; iot(n)  cin>>arr[i];
#define bye               fflush(stdout)

typedef pair<lld,lld>     pii;
typedef pair<string,lld>  psi;
template <typename T>
bool mycomp(T x,T y){ 
   return (x==y);  //give your condition here
}
bool paircomp(const pair<lld,lld> &x,const pair<lld,lld> &y){ 
return x.second<y.second;
}

int main(){
       ios_base::sync_with_stdio(false);
             cin.tie(0);
            cout.tie(0);
      lld t=1; //cin>>t;  
      while(t--){
          lld n; cin>>n;
          string s; cin>>s;
          lld cnt=0;
          iot(n){
              if(s[i]=='R')  cnt++;
          }
          lld cnt2=0;
          iot(cnt){
              if(s[i]=='R')  cnt2++;  
          }
          
          cout<<cnt-cnt2;
      }
}


Measured memory_bytes: 3756
import sys

n, k = map(int, input().split())
s = [int(s) for s in list(input())]
count = 0
tmp = 1
c = []
ans = 0

for i in s:
    if i == tmp:
        count += 1
    else:
        c.append(count)
        tmp = i
        count = 1

c.append(count)
if s[-1] == 0:
    c.append(0)

# kが十分大きいなら
if len(c) <= 2*k+1:
    print(sum(c))
    sys.exit()
# TLEしたから尺取りにしたい
# for i in range(0, len(c)-2*k, 2):
#     ans = max(ans, sum(c[i:i+2*k+1]))
ans = total = sum(c[:2*k+1])
for i in range(0, len(c)-2*k-2, 2):
    total = total + c[i+2*k+1] + c[i+2*k+2] - c[i] - c[i+1]
    ans = max(ans, total)

print(ans)


Measured memory_bytes: 52600
#include<bits/stdc++.h>
/* #define int long long */
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define repa(i, s, n) for(int i = s; i < (int)n; i++)
using namespace std;
using ll = long long;
typedef vector<int> vi;
typedef pair<int, int> P;
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define MOD 1000000007
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

signed main(){
    int w, h;
    cin >> w >> h;

    int n;
    cin >> n;
    vi x(n), y(n), a(n);
    rep(i, n) cin >> x[i] >> y[i] >> a[i];

    int left = 0, under = 0;
    rep(i, n){
        if(a[i] == 1) chmax(left, x[i]);
        else if(a[i] == 2) chmin(w, x[i]);
        else if(a[i] == 3) chmax(under, y[i]);
        else chmin(h, y[i]);
    }

    if(h - under < 0){
        cout << 0 << endl;
        return 0;
    }else if(w - left < 0){
        cout << 0 << endl;
        return 0;
    }

    int all_after = (h - under) * (w - left);

   /*  printf("w = %d, h = %d, left = %d, under = %d\n", w, h, left, under); */

    if(all_after >= 0) cout << all_after << endl;
    else cout << 0 << endl;
}

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

const int MAX = 100;
int A[MAX];
int N;
int main()
{
	cin >> N;
	for (int i = 0; i < N; ++i) cin >> A[i];
	int minj;
	int cnt = 0;
	for (int i = 0; i < N; ++i)
	{
		minj = i;
		for (int j = i + 1; j < N; ++j)
		{
			if (A[j] < A[minj]) minj = j;
		}
		if (i != minj)
		{
			swap(A[i], A[minj]);
			cnt++;
		}
	}
	for (int i = 0; i < N; ++i)
	{
		if (i) cout << ' ';
		cout << A[i];
	}
	cout << endl;
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 3088
#pragma region template 2.4
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using pq_asc = priority_queue<T, vector<T>, greater<T>>;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP1(i, n) for (ll i = 1; i <= (n); ++i)
#define FOR(i, a) for (auto &i : a)
#define CH(f, x, y) x = f(x, y)
#define IN(T, x) \
    T x;         \
    cin >> x;
#define AIN(T, a, n) \
    vector<T> a(n);  \
    FOR(i, a)        \
    cin >> i;
#define A2IN(T1, a, T2, b, n) \
    vector<T1> a(n);          \
    vector<T2> b(n);          \
    REP(i, n)                 \
    cin >> a[i] >> b[i];
#define OUT(x) cout << (x) << endl;
#define FOUT(x) cout << fixed << setprecision(15) << (x) << endl;
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) \
    SORT(a);     \
    reverse(ALL(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define DUMPA(a)          \
    cout << #a << " = {"; \
    JOUT(ALL(a), ", ", cout) << "}" << endl;

template <typename T>
ostream &JOUT(T s, T e, string sep = " ", ostream &os = cout)
{
    if (s != e)
    {
        os << *s;
        ++s;
    }
    while (s != e)
    {
        os << sep << *s;
        ++s;
    }
    return os;
}

ostream &YES(bool cond, string yes = "Yes", string no = "No", ostream &os = cout)
{
    if (cond)
    {
        os << yes << endl;
    }
    else
    {
        os << no << endl;
    }
    return os;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p)
{
    os << '(' << p.first << ", " << p.second << ')';
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << '[';
    JOUT(ALL(v), ", ", os) << ']';
    return os;
}

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#pragma endregion template

int main()
{
    IN(ll, N);
    A2IN(ll, A, ll, B, N);
    SORT(A);
    SORT(B);
    ll l = A[(N - 1) / 2];
    ll r = B[(N - 1) / 2];
    ll ans;
    if (N % 2 == 0)
    {
        ans = (B[(N - 1) / 2 + 1] + r) - (A[(N - 1) / 2 + 1] + l) + 1;
    }
    else
    {
        ans = r - l + 1;
    }
    OUT(ans);
}

Measured memory_bytes: 6376