akhauriyash/Code-Regression huggingface dataset:
N, M = map(int, input().split())
H = list(map(int, input().split()))
A = list()
B = list()
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a-1)
    B.append(b-1)

kyuryo = [set() for _ in range(N)]
for michi in range(M):
    kyuryo[A[michi]].add(B[michi])
    kyuryo[B[michi]].add(A[michi])

nice_count = 0
for tenbodai in range(N):
    for neighbor in kyuryo[tenbodai]:
        if H[neighbor] >= H[tenbodai]:
            break
    else:
        nice_count += 1

print(nice_count)


Measured memory_bytes: 47212
using System;
using System.Linq;
using System.Collections.Generic;

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            var l = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int x = l[0], y = l[1];
            var count = 0;
            if (x < y) {
               if (x >= 0) 
                   count = y - x;
               else
                   count = Math.Min(y - x, Math.Abs(y + x) + 1);
            }
            else {
               if (x >= 0) {
                  count = Math.Min(x - y + 2, Math.Abs(x + y) + 1); 
               } else {
                  count = x - y + 2;
               }
            }
            
            Console.WriteLine(count);
        }
    }
}


Measured memory_bytes: 13396
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n,m,p,q,r;
    for(;;){
        scanf("%d%d%d%d%d",&n,&m,&p,&q,&r);
        if(n==0) break;
        pair<int,int> *cards=new pair<int,int>[1];
        cards[0]=make_pair(1,n);
        int csize=1;
        for(int ix=0;ix<m;ix++){
            int x,y;
            scanf("%d%d",&x,&y);
            int *maif=new int[csize],*mais=new int[csize];
            maif[0]=1;
            mais[0]=cards[0].second-cards[0].first+1;
            for(int i=1;i<csize;i++){
                mais[i]=mais[i-1]+(cards[i].second-cards[i].first+1);
                maif[i]=mais[i-1]+1;
            }
            vector<pair<int,int> > a,b,c;
            for(int i=0;i<csize;i++){
                if(mais[i]<=x) a.push_back(cards[i]);
                else if(y<maif[i]) c.push_back(cards[i]);
                else if(x<maif[i]&&mais[i]<=y) b.push_back(cards[i]);
                else if(x<maif[i]&&y<mais[i]){
                    b.push_back(make_pair(cards[i].first,y+(cards[i].first-maif[i])));
                    c.push_back(make_pair(y+(cards[i].first-maif[i])+1,cards[i].second));
                }
                else if(maif[i]<=x&&mais[i]<=y){
                    a.push_back(make_pair(cards[i].first,x+(cards[i].first-maif[i])));
                    b.push_back(make_pair(x+(cards[i].first-maif[i])+1,cards[i].second));
                }
                else if(maif[i]<=x&&y<mais[i]){
                    a.push_back(make_pair(cards[i].first,x+(cards[i].first-maif[i])));
                    b.push_back(make_pair(x+(cards[i].first-maif[i])+1,y+(cards[i].first-maif[i])));
                    c.push_back(make_pair(y+(cards[i].first-maif[i])+1,cards[i].second));
                }
            }
            delete[] cards;
            delete[] maif;
            delete[] mais;
            csize=c.size()+b.size()+a.size();
            cards=new pair<int,int>[csize];
            for(int ii=0;ii<c.size();ii++)cards[ii]=c[ii];
            for(int ii=0;ii<b.size();ii++)cards[ii+c.size()]=b[ii];
            for(int ii=0;ii<a.size();ii++)cards[ii+c.size()+b.size()]=a[ii];
        }
        int *maif=new int[csize],*mais=new int[csize];
        maif[0]=1;
        mais[0]=cards[0].second-cards[0].first+1;
        for(int i=1;i<csize;i++){
            mais[i]=mais[i-1]+(cards[i].second-cards[i].first+1);
            maif[i]=mais[i-1]+1;
        }
        int ans=0;
        for(int i=0;i<csize;i++){
            if(p<=maif[i]&&mais[i]<=q) ans+=max(0,min(r,cards[i].second)-cards[i].first+1);
            else if(maif[i]<p) ans+=max(0,min(r,cards[i].second)-(cards[i].first+(p-maif[i]))+1);
            else if(q<mais[i]) ans+=max(0,min(r,cards[i].second-(mais[i]-q))-cards[i].first+1);
            else ans+=max(0,min(r,cards[i].second-(mais[i]-q))-(cards[i].first+(p-maif[i]))+1);
        }
        printf("%d\n",ans);
        delete[] cards;
        delete[] maif;
        delete[] mais;
    }
}

Measured memory_bytes: 1028
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N-1)]

adja_dict={}

for a,b in AB:
  adja_dict.setdefault(a, set()).add(b)
  adja_dict.setdefault(b, set()).add(a)

nodes = [None] * (N+2) #N[0]:b N[N+1]:w
nodes[0] = nodes[1] = 1
nodes[N] = nodes[N+1] = -1

from collections import deque
dq = deque([1, N])
while dq:
  x = dq.popleft()
  for y in adja_dict[x]:
    if nodes[y] is None:
      nodes[y] = nodes[x]
      dq.append(y)
#print(nodes)
if sum(nodes)>0:
  print('Fennec')
else:
  print('Snuke')

Measured memory_bytes: 58048
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=500010, inf=1e9;
int n, K;
int a[maxn];

template<typename T>
inline void read(T &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}

int main()
{
	read(n); read(K);
	for(int i=1;i<=n;i++) read(a[i]);
	int l=1, r=n;
	while(l<r)
	{
		int mid=(l+r)>>1;
//		printf("%d %d %d\n", a[mid], l, r);
		if(a[mid]>=0) r=mid;
		else l=mid+1;
	}
	if(a[l]<0) l++;
//	printf("l:%d\n", l);
	int ans=inf;
	for(int i=1;i<=n-K+1;i++)
	{
//		printf("i:%d ans:%d\n", i, ans);
		if(i+K-1<l) ans=min(ans, -a[i]);//, printf("a[i]:%d\n", a[i]);
		else if(l<=i) ans=min(ans, a[i+K-1]);//, printf("a:%d\n", a[i+K]);
		else ans=min(ans, min(2*(-a[i])+a[i+K-1], 2*a[i+K-1]-a[i]));// printf("%d %d\n", 2*(-a[i])+a[i+K], 2*a[i+K]-a[i]);
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 640
n = int(input())
nums = list(map(int, input().split()))

nums1 = nums[0::2]
nums2 = nums[1::2]

bug1 = [0] * 100001
bug2 = [0] * 100001

for num in nums1:
    bug1[num] += 1

for num in nums2:
    bug2[num] += 1

max_v_1 = max(bug1)
max_i_1 = bug1.index(max_v_1)
max_v_2 = max(bug2)
max_i_2 = bug2.index(max_v_2)

if max_i_1 == max_i_2:
    bug1[max_i_1] = 0
    bug2[max_i_2] = 0
    sec_max_v_1 = max(bug1)
    sec_max_v_2 = max(bug2)
    print(n - min(max_v_1, max_v_2) - max(sec_max_v_1, sec_max_v_2))
else:
    print(n - max_v_1 - max_v_2)


Measured memory_bytes: 14396
#include <cstdio>

int main(){
	int n;
	int card[52]={0};
	
	scanf(" %d", &n);
	for(int i=0; i<n; ++i){
		char c;
		int a;
		scanf(" %c %d", &c, &a);
	
		if(c=='S') card[a-1]=1;
		else if(c=='H') card[a-1+13]=1;
		else if(c=='C') card[a-1+26]=1;
		else if(c=='D') card[a-1+39]=1;
	}
	
	for(int i=0; i<52; ++i){
		if(card[i]==0){
			if(i<13) printf("S ");
			else if(i<26) printf("H ");
			else if(i<39) printf("C ");
			else if(i<52) printf("D ");
			
			printf("%d\n", i%13+1);
		}
	}

	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, n;
  cin >> N;
  n = N;
  int sum = 0;
  while(n != 0){
  	sum += n % 10;
    n /= 10;
  }
  if(N % sum == 0){
  	cout << "Yes" << endl;
  }else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
N = int(input())
s = [input() for i in range(N)]
ans = 0
start = 0
end = 0
onaji = 0
hiku = 0
for i in s:
    if i[0]=="B":
        start += 1
    if i[-1]=="A":
        end += 1
    if i[0]=="B" and i[-1]=="A":
        onaji += 1
    if i[0]=="B" and i[-1]!="A":
        hiku += 1
    if i[0]!="B" and i[-1]=="A":
        hiku += 1
    for j in range(len(i)-1):
        if i[j]=="A":
            if i[j+1]=="B":
                ans += 1

if onaji>0 and hiku==0:
    print(ans+min(start, end)-1)
else:
    print(ans+min(start, end))

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

using namespace std;
using Int = long long int;
using UInt = unsigned long long int;


namespace IO {
    template <typename TYPE>
        class TableIO {
            public:
                // 標準入力から二次元配列を作成
                static vector<vector<TYPE> > MakeTable(); // 標準
                static vector<vector<TYPE> > MakeTableWithWall(const TYPE& init); // 壁付き
                // 二次元配列を出力
                static void PrintTable(const vector<vector<TYPE> >& table); 
        };

    // 標準入力から二次元配列を作成
    template <typename TYPE>
        vector<vector<TYPE> > TableIO<TYPE>::MakeTable() {
            Int h, w;
            cin >> h >> w;
            vector<vector<TYPE> > input(h, vector<TYPE>(w));
            for (Int i = 0; i < h; ++i) {
                for (Int j = 0; j < w; ++j) {
                    cin >> input[i][j];
                }
            }
            return input;
        }
    // 標準入力から二次元配列を作成
    template <typename TYPE>
        vector<vector<TYPE> > TableIO<TYPE>::MakeTableWithWall(const TYPE& init) {
            Int h, w;
            cin >> h >> w;
            vector<vector<TYPE> > input(h + 2, vector<TYPE>(w + 2, init));
            for (Int i = 1; i <= h; ++i) {
                for (Int j = 1; j <= w; ++j) {
                    cin >> input[i][j];
                }
            }
            return input;
        }

    // 二次元配列を出力
    template <typename TYPE>
        void TableIO<TYPE>::PrintTable(const vector<vector<TYPE> >& table) {
            for (Int i = 0; i < table.size(); ++i) {
                for (Int j = 0; j < table[0].size(); ++j) {
                    cout << table[i][j] << " ";
                }
                cout << endl;
            }
            return;
        }
}
using namespace IO;

bool tonari(vector<vector<char> >& v, Int i, Int j) {
    if (v[i - 1][j] == '#') {
    } else if (v[i + 1][j] == '#') {
    } else if (v[i][j - 1] == '#') {
    } else if (v[i][j + 1] == '#') {
    } else {
        return false;
    }
    return true;
}

int main(void) {
    vector<vector<char> > v = TableIO<char>::MakeTableWithWall('.');
    //TableIO<char>::PrintTable(v);
    bool result = true;
    for (Int i = 1; i < v.size(); ++i) {
        for (Int j = 1; j < v[0].size(); ++j) {
            if (v[i][j] == '.') {
            } else if (v[i][j] == '#' && tonari(v, i, j)) {
            } else {
                result = false;
            }
        }
    }
    if (result == true) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}



Measured memory_bytes: 3616
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define repi(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define repdi(i,a,b) for(ll i=(a)-1;i>=(b);--i)
#define repd(i,a) repdi(i,a,0)
#define itr(it,a) for( auto it = (a).begin(); it != (a).end(); ++it )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

using ll = long long;
using P = std::pair<ll, ll>;

constexpr ll INF = 1ll<<60;

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; }

template<class S, class T>
std::ostream& operator<< ( std::ostream& out, const std::pair<S,T>& a )
{ std::cout << '(' << a.first << ", " << a.second << ')'; return out; }

template<class T>
std::ostream &operator<< ( std::ostream& out, const std::vector<T>& a )
{ std::cout << '['; rep( i, a.size() ){ std::cout << a[i]; if( i != a.size()-1 ) std::cout << ", "; } std::cout << ']'; return out; }

ll N, K;
std::vector<ll> A(2000000);

int main()
{
  std::cin >> N >> K;

  rep( i, N )
    std::cin >> A[i];

  ll prod = 1;
  ll prv = -1;

  rep( i, N ) {
    if( i < K )
      continue;
    
    std::cout << (A[i-K] < A[i] ? "Yes" : "No") << std::endl;
  }

  return 0;
}

Measured memory_bytes: 18724
N = int(input())
A = list(map(int, input().split()))

from fractions import gcd
left = [A[0]]
right = [A[-1]]

for i in range(1, N-1):
    left.append(gcd(left[-1], A[i]))
    right.append(gcd(right[-1], A[-1-i]))

ans = 1
for i in range(N):
    if i == 0:
        tmp = right[-1]
    elif i == N-1:
        tmp = left[-1]
    else:
        tmp = gcd(left[i-1], right[N-2-i])
    ans = max(ans, tmp)

print(ans)


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

int main() {
	int n; scanf("%d%*c", &n);
	rep(i, n) {
		string s; getline(cin, s);
		regex re("Hoshino");
		cout << regex_replace(s, re, "Hoshina") << endl;
	}
}

Measured memory_bytes: 3320
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
What do you think? What do you think?
1st on Billboard, what do you think of it
Next is a Grammy, what do you think of it
However you think, I’m sorry, but shit, I have no fcking interest
*******************************
I'm standing on top of my Monopoly board
That means I'm on top of my game and it don't stop
til my hip don't hop anymore
https://www.a2oj.com/Ladder16.html
*******************************
Shining through the city with a little funk and soul
*******************************
300iq as writer = Sad!
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class Main
   {
      static final long MOD = 998244353L;
      public static void main(String hi[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         int K = Integer.parseInt(st.nextToken());
         int[][] arr = new int[K][2];
         for(int i=0; i < K; i++)
         {
            st = new StringTokenizer(infile.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
         }
         long[] dp = new long[N+1];
         long[] pref = new long[N+1];
         dp[1] = pref[1] = 1L;
         for(int i=2; i <= N; i++)
         {
            for(int k=0; k < K; k++)
            {
               if(i-arr[k][0] <= 0)
                  continue;
               int right = i-arr[k][0];
               int left = Math.max(1, i-arr[k][1]);
               dp[i] += pref[right]-pref[left-1]+MOD;
               while(dp[i] >= MOD)
                  dp[i] -= MOD;
            }
            pref[i] = pref[i-1]+dp[i];
            if(pref[i] >= MOD)
               pref[i] -= MOD;
         }
         System.out.println(dp[N]);
      }
   }

Measured memory_bytes: 36904
#include <iostream>

using namespace std;

int main(){
        int i,j,N;
        unsigned long long ans=1;
        j=1;
        for(i=1; i<10; i++) {
                j *= 10;
        }
        j += 7;
        cin >> N;

        for(i=1; i<=N; i++) {
                ans = i * ans;
                ans = ans % j;
        }
        cout << ans << endl;
        return 0;
}


Measured memory_bytes: 256
/**
 *    author:  tourist
 *    created: 11.11.2017 15:18:19       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  int a, b;
  scanf("%d %d", &a, &b);
  long long x = 1900 * b + 100 * (a - b);
  x *= (1 << b);
  cout << x << endl;
  return 0;
}


Measured memory_bytes: 256
if __FILE__ == $0
  price_acc = 0
  variation = 0
  count_sum = 0
  while line = gets
    price, count = line.split(',').map{|i| i.to_i}
    price_acc += price * count
    variation += 1
    count_sum += count
  end
  puts price_acc
  puts (count_sum.to_f / variation.to_f).round
end

Measured memory_bytes: 6112
#include <iostream>
#include <vector>
#include <set>
#include <array>
#include <algorithm>

using namespace std;

struct Point {
	int x;
	int y;

};

int main() {

	int a, b, c;
	cin >> a >> b >> c;
	array<int ,3> vec;
	vec[0] = a + b;
	vec[1] = a + c;
	vec[2] = b + c;

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

	cout << vec[0] << endl;

	return 0;
}

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

typedef long long int ll;

using namespace std;

ll pow_mod(ll n, ll k, ll mod) {

    if(k == 0) {

        return 1;

    } else if(k % 2 == 1) {

        return pow_mod(n, k - 1, mod) * n % mod;

    } else {

        ll t = pow_mod(n, k / 2, mod);

        return t * t % mod;

    }

}

int main() {

	// your code goes here

 cin.tie(0);

    ios::sync_with_stdio(false);

    ll n;

    ll p=2019;

    

    string s;

    cin >> s;

    n=s.length();

    vector<ll> a(n);

    for(ll i = 0; i < n; i++) {

        a[i] = (ll)(s[i] - '0');

    }

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

    vector<int> sum(n + 1, 0);

    for(ll i = 0; i < n; i++) {

        sum[i + 1] = sum[i] + a[i] * pow_mod(10, i, p) % p;

        sum[i + 1] %= p;

    }

    map<ll, ll> mp;

    for(ll i = 0; i < n + 1; i++) {

        // cout << sum[i] << " ";

        mp[sum[i]]++;

    }

    // cout << endl;

    ll ans = 0;

    

    for(const auto &p : mp) {

        ans += (p.second - 1) * p.second / 2;

    }

    cout << ans << endl;

     

     

	return 0;

}

Measured memory_bytes: 5944
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>

using namespace std;

struct Edge{int to, cost;};
const int NODE = 101;
const int MAX = 1e4+1;

vector<Edge> E[NODE];

int N,M;

void input(){
  for(int i = 0; i < NODE; i++) E[i].clear();

  for(int i = 0; i < M; i++){
    int a,b,c;
    cin >> a >> b >> c;
    a--; b--;
    E[a].push_back((Edge){b,c});
    E[b].push_back((Edge){a,c});
  }
}

bool prim(int low, int high){

  bool used[N];
  for(int i = 0; i < N; i++) used[i] = false;

  used[0] = true;
  queue<int> Q;
  Q.push(0);

  int connect = 1;
  while(!Q.empty()){
    const int now = Q.front();
    Q.pop();
    
    for(int i = 0; i < E[now].size(); i++){
      Edge& e = E[now][i];
      if(!used[e.to] && low <= e.cost && e.cost <= high){
	used[e.to] = true;
	connect++;
	Q.push(e.to);
      }
    }
  }
  for(int i = 0; i < N; i++) if(!used[i])return false;
  return true;
}

void solve(){
  
  int ans = -1;

  for(int i = 0; i < MAX; i++){
    int L = i,R = MAX;
    while(L < R){
      int C = (L+R)/2;
      if(prim(i,C)) R = C;
      else L = C+1;
    }

    if(ans == -1 || ans > (R-i) && R < MAX) ans = (R-i);
  }
  if(ans >= MAX) cout << -1 << endl;
  else cout << ans << endl;
}

int main(){
  while(cin >> N >> M && N+M){
    input();
    solve();
  }
  return 0;
}

Measured memory_bytes: 1328
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int A[200010];
int main()
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = N - 1; i >= 0; i -= 2) cout << A[i] << " ";
	if (N % 2 == 0) {
		for (int i = 0; i < N; i += 2) cout << A[i] << " ";
	}
	else {
		for (int i = 1; i < N; i += 2) cout << A[i] << " ";
	}
	cout << endl;
}


Measured memory_bytes: 2944
#include <iostream>
using namespace std;
int main(){
    int N;
    cin >> N;
    int H[N];
    for(int i=0;i<N;i++){
        cin >> H[i];
    }
    
    int now=0,total=0;
    
    for(int j=N-1;0<j;j--){
        if(H[j]<=H[j-1]){
            now++;
            if(total<now) total=now;
        }else{
            now = 0;
        }
    }
    cout << total << endl;
    return 0;
}

Measured memory_bytes: 640
def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x

def lcm(x, y):
    return x//gcd(x, y)*y

def f(x, c, d):
    return x - x//c - x//d + x//(lcm(c, d))

a, b, c, d = map(int, input().split())
print(f(b, c, d) - f(a-1, c, d))


Measured memory_bytes: 3060
#include <iostream>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<map>
#include<cstdio>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define mp make_pair
#define pb push_back
#define P pair<int,int>
#define ll __int64
int n,a,b;
int main(){
cin>>n>>a>>b;

for(int i=0;i<100000;i++){
if((i+1)%2){//Alice
	if(a+1!=b)a++;
	else a--;
}
else{//Borys
	if(b-1!=a)b--;
	else b++;
}

if(b==n+1){cout<<"Alice"<<endl;break;}
 if(a==0){cout<<"Borys"<<endl;break;}

}
	return 0;
}

Measured memory_bytes: 764
class BIT():
    def __init__(self,size):
        self.size=size
        self.node=[0]*(size+1)

    def sum(self,idx):
        ret=0
        while idx>0:
            ret+=self.node[idx]
            idx-=idx&(-idx)
        return ret

    def add(self,idx,x):
        while idx<=self.size:
            self.node[idx]+=x
            idx+=idx&(-idx)

n,k=map(int,raw_input().split())
a=[int(raw_input()) for _ in xrange(n)]
diff=[]
for i in xrange(n):
    diff.append(a[i]-k)
for i in xrange(n-1):
    diff[i+1]+=diff[i]
bit=BIT(n)
s=set([])
for i in xrange(n):
    s.add(diff[i])
li=list(s)
li.sort()
d={}
for i in xrange(len(li)):
    d[li[i]]=i+1
ans=0
for i in xrange(n):
    pos=d[diff[i]]
    ans+=bit.sum(pos)
    if diff[i]>=0:
        ans+=1
    bit.add(pos,1)
print ans


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

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

    ll N, W;
    cin >> N >> W;
    vector<ll> v(N), w(N);
    for (int i = 0; i < N; ++i) {
        cin >> v.at(i) >> w.at(i);
    }

    vector<vector<ll> > dp(N + 1, vector<ll>(10001, INT_MAX));
    dp.at(0).at(0) = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= 10000; ++j) {
            if (j >= v.at(i)) {
                dp.at(i + 1).at(j) = min(dp.at(i).at(j), dp.at(i).at(j - v.at(i)) + w.at(i));
            } else {
                dp.at(i + 1).at(j) = dp.at(i).at(j);
            }
        }
    }

    ll ans = 0;
    for (int j = 0; j <= 10000; ++j) {
        if (dp.at(N).at(j) <= W) ans = j;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 10800
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, p;
  cin >> n >> p;
  string s;
  cin >> s;
  long long ans = 0;
  if (p == 5 || p == 2) {
    for (int i = 0; i < n; i++) {
      int x = s[i] - '0';
      if (x % p == 0) ans += (i + 1);
    }
  } else {
    vector<int> a(n + 1);
    int c = 1;
    for (int i = n - 1; i >= 0; i--) {
      int x = s[i] - '0';
      a[i] = (x * c) % p;
      c *= 10;
      c %= p;
    }
    reverse(a.begin(), a.end());
    // for (int i = 0; i <= n; i++) cerr << a[i] << " ";
    // cerr << endl;
    for (int i = 1; i <= n; i++) {
      a[i] += a[i - 1];
      a[i] %= p;
    }
    // for (int i = 0; i <= n; i++) cerr << a[i] << " ";
    // cerr << endl;
    vector<int> cnt(p);
    for (int i = 0; i <= n; i++) {
      ans += cnt[a[i]];
      cnt[a[i]]++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1428
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <time.h>
#include <queue>
#include <string.h>
#define sf scanf
#define pf printf
#define lf double
#define ll long long
#define p123 printf("123\n");
#define pn printf("\n");
#define pk printf(" ");
#define p(n) printf("%d",n);
#define pln(n) printf("%d\n",n);
#define s(n) scanf("%d",&n);
#define ss(n) scanf("%s",n);
#define ps(n) printf("%s",n);
#define sld(n) scanf("%lld",&n);
#define pld(n) printf("%lld",n);
#define slf(n) scanf("%lf",&n);
#define plf(n) printf("%lf",n);
#define sc(n) scanf("%c",&n);
#define pc(n) printf("%c",n);
#define gc getchar();
#define re(n,a) memset(n,a,sizeof(n));
#define len(a) strlen(a)
#define LL long long
#define eps 1e-6
using namespace std;



int main() {
    ll n,k,x,y;
    sld(n) sld(k) sld(x) sld(y);
    if(n >k){
       pld(x*k+(n-k)*y) pn
    }else{
        pld(n*x) pn
    }


    return 0;
}


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

int main () {
  
  int ans = 0;
  
  int N;
  cin >> N;
  vector<int> d(N);
  
  for (int i = 0; i < N; i++) {
    cin >> d[i];
  }
  
  for (int i = 0; i < N - 1; i++) {
    for (int j = i + 1; j < N; j++) {
      ans += (d[i]*d[j]);
    }
  }
  
  cout << ans << endl;
  
  
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int n;
	int i, j;
	float high;
	int fl[6] = {0};
	
	scanf("%d", &n);
	
	for (i = 0; i < n; i++){
		scanf("%f", &high);
		
		if (high < 165.0){
			fl[0]++;
		}
		else if (high < 170.0){
			fl[1]++;
		}
		else if (high < 175.0){
			fl[2]++;
		}
		else if (high < 180.0){
			fl[3]++;
		}
		else if (high < 185.0){
			fl[4]++;
		}
		else {
			fl[5]++;
		}
	}
	
	for (i = 0; i < 6; i++){
		printf("%d:", i + 1);
		
		for (j = 0; j < fl[i]; j++){
			printf("*");
		}
		printf("\n");
	}
	
	return (0);
}

Measured memory_bytes: 636
#include <bits/stdc++.h>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i,a,b) for (ll i=(a);i<(ll)b; i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll,ll> p;
const int MOD = 1000000007;

int main(){
    int K,S;cin>>K>>S;
    int cnt = 0;
    REP(x,K+1){
        REP(y,K+1){
            if(0<=S-x-y and S-x-y<=K) cnt++;

            
        }
    }
    cout<<cnt<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)(b); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    int D; //365
    cin >> D;

    int c[26];
    rep(i, 0, 26) {
        cin >> c[i];
    }

    int s[D][26];
    int t[D] = {};
    //各日について、s[i][j]が最大になるコンテストタイプで初期化
    rep(i, 0, D) {
        int mx = -1;
        rep(j, 0, 26) {
            cin >> s[i][j];
            if (mx < s[i][j]) {
                mx = s[i][j];
                t[i] = j;
            }
        }
    }

    //日程を乱数で初期化
    srand(time(NULL));
    /*rep(i, 0, D) {
        t[i] = rand() % 26;
    }*/

    ll mx_score = -1e18;
    int cnt = 200000;
    while (cnt--) {
        //d日目のコンテストをqに置き換えてスコアを計算し、改善しなければ元に戻す
        int d = rand() % 365;
        int q = rand() % 26;
        int old = t[d];
        t[d] = q;

        //スコアを計算する
        ll score[D] = {};
        vector<int> last_day(26, -1);
        rep(i, 0, D) {
            if (i != 0) score[i] = score[i - 1];
            //増加分
            score[i] += s[i][t[i]];

            last_day[t[i]] = i;

            //減少分
            ll decrease = 0;
            rep(j, 0, 26) {
                decrease += c[j] * (i - last_day[j]);
            }
            score[i] -= decrease;
        }
        //cout << "score[D - 1]: " << score[D - 1] << endl;
        if (mx_score > score[D - 1]) {
            t[d] = old;
        } else {
            mx_score = score[D - 1];
        }
    }

    rep(i, 0, D) cout << t[i] + 1 << endl;
    return 0;
}


Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll>PLL;
#define rep(i,n) for (int i = 0; i < (n); ++i)
ll MOD = 1e4+7;
int main() {
    int n;
    cin >> n;
    vector<int> t(n);
    int ans = 0;
    rep(i, n) {
        cin >> t[i];
        ans += t[i];
    }
    int m;
    cin >> m;
    rep(i, m) {
        int p, x;
        cin >> p >> x;
        --p;
        cout << ans - ( t[p] - x ) << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
using llong = long long;

llong x, y;
llong cnt;

int main() {
    cin >> x >> y;
    for (int i = 0; i <= x; i++) {
        llong j = x - i;

        if (i * 4 + 2 * j == y) cnt++;
    }
    if (cnt) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

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

#define INF 1001001001
#define LINF 1001001001001001001
#define MOD 1000000007
#define MOD2 998244353

#define all(a)  (a).begin(),(a).end()
#define dig(n)  to_string(n).length()

#define pb push_back
#define eb emplace_back
#define mkp make_pair

#define se second
#define fi first

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,pii> ppii;

int main(){

    bool flag=false;
    ll ans=0,sum=0;

    int n,k,r,s,p;
    cin >>n>>k>>r>>s>>p;
    vector<int> loss(n,-1);

    string t;
    cin >> t;

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

        if(i >= k && t[i-k] == t[i] && loss[i-k] == -1){
            loss[i]=1;
        }else{
            if(t[i]=='r'){
                ans += p;
            }else if(t[i]=='s'){
                ans += r;
            }else{
                ans += s;
            }
        }
    }

    //cout <<fixed<<setprecision(16)<< << endl;
    cout << ans << endl;

    //if(flag)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


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

void PrintArray(int A[], int N) {
  for (int i = 0; i < N-1; i++) {
    cout << A[i] << " ";
  }
  cout << A[N-1] << endl;
}

int main() {
  int N; 
  int A[1010];
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  for (int i = 0; i < N; i++) {
    int j = i-1;
    int temp = A[i];
    while (j >= 0 && A[j] > temp) {
      A[j+1] = A[j];
      j--;
    }
    A[j+1] = temp;
    PrintArray(A, N);
  }
}




Measured memory_bytes: 3104
S = input()
K = int(input())
if S[0] == '1':
    if K == 1:
        print('1')
    else:
        for i in range(1, len(S)):
            if S[i] != '1':
                break
        if i <= K - 1:
            print(S[i])
        else:
            print('1')
else:
    print(S[0])


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

using namespace std;

using ll = long long;
using ld = long double;

const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

ld distance(ld x1, ld y1, ld x2, ld y2) {
  return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

int main () {
  cin.tie(0);
  cout << fixed << setprecision(10);
  ld x1, y1, x2, y2, x3, y3; cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
  ld a = distance(x1, y1, x2, y2);
  ld b = distance(x2, y2, x3, y3);
  ld c = distance(x3, y3, x1, y1);
  ld s = (a + b + c) / 2;
  ld S = sqrt(s * (s - a) * (s - b) * (s - c));
  ld x = 2 * S / (a + b + c);
  ld ma = max(a, max(b, c));
  ld r = x * ma / (2 * x + ma);
  cout << r << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define BUF_SIZE 52

struct point {
  int x;
  int y;
};
struct point dir[8] = {
  {-1, -1}, {-1, 0}, {-1, 1},
  {0, -1}          , {0, 1},
  {1, -1}, {1, 0}, {1, 1}
};

int main(void) {
  char line[BUF_SIZE];
  FILE *fp = stdin;
  if(!fgets(line, BUF_SIZE, fp)) return 0;
  int row, col;
  sscanf(line, "%d %d", &row, &col);
  int mat[BUF_SIZE][BUF_SIZE] = {0};

  int i, j;
  for(i = 1; i <= row; i++) {
    if(!fgets(line, BUF_SIZE, fp)) return 0;
    char* tmp;
    int s;
    for(tmp = line, s = 1; *tmp != '\n'; tmp++, s++) {
      if(*tmp == '#') {
        mat[i][s] = -51;
        for(j = 0; j < 8; j++) {
          mat[i+dir[j].x][s+dir[j].y]++;
        }
      }
    }
  }
  for(i = 1; i <= row; i++) {
    for(j = 1; j <= col; j++) {
      char ch = mat[i][j] < 0 ? '#' : '0'+mat[i][j];
      putchar(ch);
    }
    putchar('\n');
  }

  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T = int> void print(vector<T> v){for(auto a:v)cout<<a<<" ";cout<<endl;}

/*
素因数の個数さえ分かればいい
エラトステネスをする
O(nloglogn)
*/

ll n,er[10000010],ans=0;

int main(void){
	cin>>n;
	ans+=1;
	reg(i,1,n)er[i]=1;
	reg(i,2,n){
		if(er[i]==1){
			for(ll j=1;j*i<=n;++j){
				ll m=i*j,a=1;
				while(m%i==0){
					m/=i;
					a++;
				}
				er[i*j]*=a;
			}
		}
		ans += er[i]*i;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 81716
#include <iostream>
#include <vector>
#include <algorithm>
#include<string>

using namespace std;

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

    int h = 0, w = 0;
    if(a > b){
        h = b;
        if(a > c){
            w = c;
        }else{
            w = a;
        }
    }else{
        h = a;
        if(b > c){
            w = c;
        }else{
            w = b;
        }
    }

    cout << (h * w)/2 << endl;
}

Measured memory_bytes: 256
/***************************************************************
	File name: A.cpp
	Author: huhao
	Create time: Sun 04 Aug 2019 08:00:11 PM CST
***************************************************************/
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define fr(i,a,b) for(int i=(a),end_##i=(b);i<=end_##i;i++)
#define fd(i,a,b) for(int i=(a),end_##i=(b);i>=end_##i;i--)
int read()
{
	int r=0,t=1,c=getchar();
	while(c<'0'||c>'9')
	{
		t=c=='-'?-1:1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		r=r*10+c-48;
		c=getchar();
	}
	return r*t;
}
int main()
{
	int a=read(),b=read(),c=read();
	printf("%d\n",max(0,b+c-a));
	return 0;
}

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

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

using namespace std;
using ll = long long;

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

    const int INF = INT_MAX;

    string s, t;
    cin >> s >> t;

    int ans = INF, diff;

    rep(i, s.size() - t.size() + 1) {
        diff = 0;
        rep(j, t.size()) {
            if(s.at(i + j) != t.at(j)) diff++;
        }
        ans = min(ans, diff);
    }

    printf("%d\n", ans);

    return 0;
}

Measured memory_bytes: 3724
from math import ceil

v = [int(input()) for _ in range(5)]

ans = float('inf')
for i in range(5):
    # 最後の注文i
    t = 0
    for j in range(5):
        # 加算対象の注文j
        if i == j:
            t += v[j]
        else:
            t += ceil(v[j] / 10) * 10
    ans = min(ans, t)
print(ans)


Measured memory_bytes: 3060
import java.util.*;
 
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        
        String[] linesp = line.split(" ");
        
        int[] nums = new int[5];
        for(int i = 0; i < 5; i++) {
            nums[i] = Integer.parseInt(linesp[i]);
        }
        Arrays.sort(nums);
        for(int i = 4; i >= 0; i--) {
            System.out.print(nums[i]);
            if(i > 0) {
                System.out.print(" ");
            }else {
                System.out.println("");
            }
            
        }
    }
}


Measured memory_bytes: 26068
#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
	int x;
	int n;
	int t;
	int total = 0;

	cin >> n >> x >> t ;

	total = (n + (x - 1)) / x * t;

	cout << total << endl;

	return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define int long long
int inf = 10e17;
#define mod 1000000007
int findLowerBound(
    vector<pair<int, int>> &arr,
    pair<int, int> &p)
{

    auto low = lower_bound(arr.begin(),
                           arr.end(), p);

    return low - arr.begin();
}
int findUpperBound(
    vector<pair<int, int>> &arr,
    pair<int, int> &p)
{
    auto up = upper_bound(arr.begin(),
                          arr.end(), p);

    return up - arr.begin();
}
bool vis[200005];
vector<int> vec[100005];
int child[100005];
int div1[100005];
void dfs(int node)
{
    vis[node] = 1;
    for (int i = 0; i < vec[node].size(); i++)
    {
        if (!vis[vec[node][i]])
        {
            dfs(vec[node][i]);
            child[node] += child[vec[node][i]];
        }
    }
}
void belman(int n, int m, vector<pair<int, pair<int, int>>> vec, int dis[])
{
    for (int i = 0; i <= n + m - 1; i++)
    {
        for (int j = 0; j < vec.size(); j++)
        {
            int u = vec[j].second.first;
            int v = vec[j].second.second;
            int w = vec[j].first;

            if (dis[u] + w < dis[v])
            {
                dis[v] = dis[u] + w;
            }
        }
    }
}
int fun(int a, int b)
{
    if (a > b)
        return 0;
    if (a == b)
        return 1;
    else
    {
        return fun(a + 1, b) + fun(a, b - a);
    }
}
int32_t main()
{
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    // cout.tie(NULL);
    int a[3] = {0};
    cin >> a[0] >> a[1] >> a[2];
    int count[11];
    for (int i = 0; i < 3; i++)
        count[a[i]]++;
    if (a[0] + a[1] + a[2] == 17)
        cout << "YES"
             << "\n";
    else
    {
        cout << "NO"
             << "\n";
    }

    return 0;
}


Measured memory_bytes: 5912
N,K=map(int,input().split())
R,S,P=map(int,input().split())
T=input()

ans=0
for k in range(K):
    dp=[0,0,0]
    for i in range(k,N,K):
        #print(i)
        x=T[i]
        if x=='r':
            r,s,p=max(dp[1],dp[2]),max(dp[0],dp[2]),max(dp[0],dp[1])+P
        elif x=='s':
            r,s,p=max(dp[1],dp[2])+R,max(dp[0],dp[2]),max(dp[0],dp[1])
        else:
            r,s,p=max(dp[1],dp[2]),max(dp[0],dp[2])+S,max(dp[0],dp[1])
        dp=[r,s,p]
    ans+=max(dp)
print(ans)

Measured memory_bytes: 9308
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); i++)
#define RREP(i, s, n) for (int i = s; i < (n); i++)
#define ALL(a) a.begin(), a.end()
#define RALL(a) a.rbegin(), a.rend()
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; }
using namespace std;
using ll = long long;
typedef pair<int, int> pint;
typedef pair<ll, ll> pll;
const ll MOD = 1000000007;
const ll INF = MOD * MOD;
const int inf = (1<<29);

int main() {

    ll x;
    cin >> x;

    ll a = 100;

    ll i = 0;
    while (a < x) {
        i++;
        a += a / 100;
    }

    cout << i << endl;
    
    return 0;
}

Measured memory_bytes: 3564
import std.stdio, std.conv, std.functional, std.string;
import std.algorithm, std.array, std.container, std.range, std.typecons;
import std.bigint, std.numeric, std.math, std.random;
import core.bitop;

string FMT_F = "%.10f";

static File _f;
void file_io(string fn) { _f = File(fn, "r"); }
static string[] s_rd;
T _RD(T = long)() { while(!s_rd.length) s_rd = readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
T _RD(T = long)(File f) { while(!s_rd.length) s_rd = f.readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
T[] _RDA(T = long)(T fix = 0) { auto r = readln.chomp.split.to!(T[]); r[] += fix; return r; }
T[] _RDA(T = long)(File f, T fix = 0) { auto r = f.readln.chomp.split.to!(T[]); r[] += fix; return r; }
T RD(T = long)() { if (_f.isOpen) return _RD!T(_f); else return _RD!T; }
T[] RDA(T = long)(T fix = 0) { if (_f.isOpen)  return _RDA!T(_f, fix); else return _RDA!T(fix); }

size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

void chmin(T)(ref T x, T y) { x = min(x, y); } void chmax(T)(ref T x, T y) { x = max(x, y); }
bool inside(T)(T x, T b, T e) { return x >= b && x < e; }
T lcm(T)(T x, T y) { return x * (y / gcd(x, y)); }

//long mod = 10^^9 + 7;
long mod = 998_244_353;
//long mod = 1_000_003;
void moda(T)(ref T x, T y) { x = (x + y) % mod; }
void mods(T)(ref T x, T y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(T)(ref T x, T y) { x = (x * y) % mod; }
void modpow(T)(ref T x, T y) { if (!y) { x = 1; return; } auto t = x; x.modpow(y>>1); x.modm(x); if (y&1) x.modm(t); }
void modd(T)(ref T x, T y) { y.modpow(mod - 2); x.modm(y); }

void main()
{
	auto T = RD!(char[]);

	foreach (i; 0..T.length)
	{
		if (T[i] == '?')
			T[i] = 'D';
	}

	writeln(T);
	stdout.flush;
	debug readln;
}

Measured memory_bytes: 3192
// Package main provides
//
// File:  main.go
// Author: ymiyamoto
//
// Created on Sat Jan 18 17:39:17 2020
//
package main

import (
	"fmt"
	"sort"
)

const MOD = 1e9 + 7

var memo []int

func newComb(n int) {
	memo = make([]int, n+1)
	memo[0] = 1
}

func comb(n, k int) int {
	var fact func(n int) int
	fact = func(n int) int {
		if memo[n] > 0 {
			return memo[n]
		}
		memo[n] = n * fact(n-1) % MOD
		return memo[n]
	}

	var pow func(n, k int) int
	pow = func(n, k int) int {
		if k == 0 {
			return 1
		}
		if k%2 == 1 {
			return n * pow(n*n%MOD, k/2) % MOD
		}
		return pow(n*n%MOD, k/2)
	}

	if n == 0 || k == 0 || n-k < 0 {
		return 0
	}
	return fact(n) * pow(fact(k), MOD-2) % MOD * pow(fact(n-k), MOD-2) % MOD
}

var N, K int
var A []int

func main() {
	fmt.Scan(&N, &K)
	A = make([]int, N)
	for i := range A {
		fmt.Scan(&A[i])
	}
	sort.Ints(A)

	newComb(N)
	ans := 0
	for i := 0; i < N; i++ {
		ans += comb(N-1-i, K-1) * A[N-1-i] % MOD
		ans -= comb(N-1-i, K-1) * A[i] % MOD
		if ans < 0 {
			ans += MOD
		}
		ans %= MOD
	}
	fmt.Println(ans)
}


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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};

int main()
{
    int n,ans=0;
    cin>>n;
    vector<tuple<int,int,int>> red(n),blue(n);
    
    for(int i = 0; i < n; i++)
    {
        int x,y;
        cin>>x>>y;
        red[i]=make_tuple(x,y,-1);
    }
    for(int i = 0; i < n; i++)
    {
        int x,y;
        cin>>x>>y;
        blue[i]=make_tuple(x,y,-1);
    }
    sort(all(red));
    sort(all(blue));
    
    for(int bcnt = 0; bcnt < n; bcnt++)
    {
        int p =-1;
        for(int rcnt = 0; rcnt < n; rcnt++)
        {
            if(get<2>(red[rcnt])!=-1) continue;
            if(get<0>(red[rcnt]) < get<0>(blue[bcnt]))
            {
                if(get<1>(red[rcnt]) < get<1>(blue[bcnt]))
                {
                    if(p==-1)
                    {
                        p=rcnt;
                    }
                    else if(get<1>(red[p]) < get<1>(red[rcnt]))
                    {
                        p=rcnt;
                    }
                }    
            }
            else break;
        }
        if(p!=-1)
        {
            ans++;
            get<2>(red[p])=p;
        }
    }
    
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using int64 = int64_t;

constexpr int INF = 1 << 28;

int N, M, S, G1, G2;
int B1[1000], B2[1000], C[1000];

int graph[100][100];

int solve() {
    assert(N <= 100);
    int min_dist[100][100];
    for (int j = 0; j < N; ++j) { fill(min_dist[j], min_dist[j]+N, INF); min_dist[j][j] = 0; }
    for (int j = 0; j < M; ++j) min_dist[B1[j]][B2[j]] = C[j];
    
    for (int l = 0; l < N; ++l) {
        for (int j = 0; j < N; ++j) {
            for (int k = 0; k < N; ++k) {
                int cand = min_dist[j][l] + min_dist[l][k];
                if (cand < min_dist[j][k]) min_dist[j][k] = cand;
            }
        }
    }

    int ans = INF;
    for (int j = 0; j < N; ++j) {
        int cand = min_dist[S][j] + min_dist[j][G1] + min_dist[j][G2];
        if (cand < ans) {
            ans = cand;
        }
    }
    return ans;
}

int main() {
    while (true) {
        cin >> N >> M >> S >> G1 >> G2;
        if (N == 0 && M == 0 && S == 0 && G1 == 0 && G2 == 0) break;
        --S; --G1; --G2;
        for (int j = 0; j < M; ++j) {
            cin >> B1[j] >> B2[j] >> C[j];
            --B1[j]; --B2[j];
        }
        cout << solve() << endl;
    }
    return 0;
}

Measured memory_bytes: 3156
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>

#define CH(N,A,B) (A<=N&&N<B)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define RREP(i,a,b) for(int i=(b-1);a<=i;i--)
#define F first
#define S second

using namespace std;

long long d[100010];

int main() {
  long long N,K;
  cin>>N>>K;
  REP(i,0,N){
    int a;
    long long b;
    cin>>a>>b;
    d[a] += b;
  }
  REP(i,1,100010) d[i] += d[i-1];
  REP(i,1,100010){
    //cout<<"d["<<i<<"] : "<<d[i]<<endl;
    if(d[i] >= K){
      cout<<i<<endl;
      return 0;
    }
  }

  return 0;
}


Measured memory_bytes: 1024
A, B, C, D = gets.chomp.split(" ").map(&:to_i)

t1, m1 = A.divmod(D)
t2, m2 = C.divmod(B)
t1 += 1 if m1 > 0
t2 += 1 if m2 > 0

if t1 < t2
  puts "No"
else
  puts "Yes"
end


Measured memory_bytes: 14300
#include <algorithm>
#include <set>
#include <iostream>
using namespace std;

typedef long long ll;

// sortして挿入をO(logN), 中央値を求めるのをO(1)でできるデータ構造
// set (multiset) を二本もって左半分と右半分に分ける
struct MedianList {
  const ll INF = 10e15;
  multiset<ll> left, right;

  double median() { 
    ll l = *(--left.end());
    ll r = *right.begin();
    if (left.size() > right.size()) return l;
    else if (left.size() < right.size()) return r;
    // left.size() == right.size()
    return (l+r)/2;
  }

  ll getLeft() { 
    if (left.size() == 0) return -INF;
    auto it = left.end();
    --it;
    return *it;
  }
  ll getRight() { 
    if (right.size() == 0) return INF;
    auto it = right.begin();
    return *it;
  }

  void insert(ll x) { 
    ll r = getRight();
    if (x < r) left.insert(x);
    else right.insert(x);
    int nl = left.size();
    int nr = right.size();
    while (nl-nr > 1) {
      auto it = left.end();
      --it;
      right.insert(*it);
      left.erase(it);
      nl = left.size();
      nr = right.size();
    }
    while (nr-nl > 1) {
      auto it = right.begin();
      left.insert(*it);
      right.erase(it);
      nl = left.size();
      nr = right.size();
    }
  }
};

int main() {
  int q;
  cin >> q;
  MedianList ml;
  int n = 0;
  ll suma = 0;
  ll sumb = 0;
  for (int i = 0; i < q; ++i) {
    int type;
    cin >> type;
    if (type == 1) {
      ll a, b;
      cin >> a >> b;
      sumb += b;

      ll l = ml.getLeft();
      ll r = ml.getRight();
      if (a < l) { suma += l-a; }
      if (a > r) { suma += a-r; }

      ml.insert(a);
      ml.insert(a);
      // cerr << a << " " << b << " " << suma << endl;
    }
    else {
      cout << ml.getLeft() << " " << suma+sumb << endl;
    }
  }
}



Measured memory_bytes: 18944
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<queue>
#define mem(a,b) memset(a,b,sizeof(a))
#define mod 20123
#define inf 123456789
#define LL long long
using  namespace std;
int max(int a,int b){ return a>b?a:b;}
int maxn (int a,int b,int c){return max(max(a,b),max(b,c));}
int min(int a,int b){return a<b?a:b;}
LL num[100005],vis[100005],pre[100005],x;
int main()
{
    LL i,j,n,k,ans=0;
    mem(num,0);
    mem(vis,0);
    mem(pre,0);
    scanf("%lld%lld",&n,&k);
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&x);
        if(i==1&&x!=1)
        {
            ans++;
        }
        else {
            pre[i]=x;
            num[x]++;
        }
    }
    int m,t;
    queue<int>q;
    for(i=2;i<=n;i++)
        if(num[i]==0) q.push(i);
    while(!q.empty())
    {
        m=q.front();
        q.pop();
        if(m==1) break;
        if(pre[m]!=1&&vis[m]==(k-1))
            ans++;
        else vis[pre[m]]=max(vis[pre[m]],vis[m]+1);
        num[pre[m]]--;
        if(num[pre[m]]==0) q.push(pre[m]);
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 2944