akhauriyash/Code-Regression huggingface dataset:
N = int(input())
cards = list(map(int,input().split(' ')))

cards.sort(reverse=True)
cards
Alice,Bob = 0,0
flg = 0

while len(cards) != 0:
    if flg == 0: 
        Alice += cards.pop(0)
        flg = 1
    else:
        Bob += cards.pop(0)
        flg = 0
print(Alice-Bob)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define int long long
#define for1(i, n) for(int i = 1; i <= (n);i++)
#define puts(x) cout << x << "\n"
constexpr int mod = 1000000007;
using namespace std;
int d, c[30], l[30], s[400][30];
signed main() {
	cin >> d;
	for1(i, 26)cin >> c[i];
	for1(i, d)for1(j, 26)cin >> s[i][j];
	for1(i, d) {
		int p = 0, k = -mod;
		for1(j, 26) {
			int kj = s[i][j] + c[j] * (i - l[j]) * 3.2 + c[j] * 11.5;
			if (kj > k) { p = j; k = kj; }
			else if (kj == k && c[j] > c[p])p = j;
		}
		puts(p); l[p] = i;
	}
}

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

int main()
{
    int X;
    cin >> X;

    if(X < 100){
        cout << "0" << endl;
        return 0;
    }

    int y = (X / 100)*5;
    int a = (X/100)*100;
    // int z = X;
    // int a = 1;
    // while(z > 0){
    //     z /= 10;
    //     a *= 10;
    // }å
    // a /= 10;
    // a *= X/a;
    //cout << X << " " << a+y << endl;
    if(X <= a+y){
        cout << "1" << endl;
    }else{
        cout << "0" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = int(A); I < int(B); ++I)
#define FORR(I,A,B) for(ll I = int((B)-1); I >= int(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;


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

	ll N,k,ans=0;
	cin >> N;
	map<ll,ll> D;
	D[0]++;
	vector<ll> time;
	bool zero = false;
	FOR(i,0,N){
		cin >> k;
		D[k]++;
		if(D[k]==2){
			time.push_back(k);
			time.push_back((24-k)%24);
		}else if(D[k]>2){
			zero = true;
		}
	}
	if(zero){
		cout << 0 << endl;
		return 0;
	}

	vector<ll> kouho;
	FOR(i,0,13){
		if(D[i]==1)kouho.push_back(i);
	}
	ll si = kouho.size();
	FOR(i,0,(1LL<<si)){
		ll ansp = 10000;
		vector<ll> timep=time;
		FOR(j,0,si){
			if(i&(1LL<<j))timep.push_back(kouho[j]);
			else timep.push_back((24-kouho[j])%24);
		}
		timep.push_back(24);
		FOR(j,0,timep.size()){
			FOR(l,0,timep.size()){
				if(j==l)continue;
				ansp = min(ansp,abs(timep[j]-timep[l]));
			}
		}
		ans = max(ans,ansp);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

var sc = bufio.NewScanner(os.Stdin)

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

func main() {
	sc.Split(bufio.ScanWords)
	s := stringLineScan()
	t := stringLineScan()
	ls := len(s)
	lt := len(t)
	a := make([]string, 0)
	for i := 0; i < ls-lt+1; i++ {
		f := true
		for j := 0; j < lt; j++ {
			if t[j] != s[i+j] && s[i+j] != '?' {
				f = false
				break
			}
		}
		if f {
			x := ""
			for j := 0; j < ls; j++ {
				if j >= i && j < i+lt {
					x = x + string(t[j-i])
				} else if s[j] == '?' {
					x = x + "a"
				} else {
					x = x + string(s[j])
				}
			}
			a = append(a, x)
		}
	}
	sort.Strings(a)
	if len(a) > 0 {
		fmt.Println(a[0])
	} else {
		fmt.Println("UNRESTORABLE")
	}
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    int n, a, b, c, d;
    cin >> n >> a >> b >> c >> d;
    a--;
    b--;
    c--;
    d--;
    string s;
    cin >> s;
    if(c < d)
    {
        int pos = a;
        while(pos < d)
        {
            int count = 0;
            while(pos < d && s[pos] == '.')
            {
                pos++;
            }
            if(pos >= d-1) break;
            if(s[pos+1] == '#')
            {
                cout << "No" << endl;
                return 0;
            }
            pos++;
        }
        cout << "Yes" << endl;
    }
    else
    {
        int pos = a;
        while(pos < c)
        {
            int count = 0;
            while(pos < c && s[pos] == '.')
            {
                pos++;
            }
            if(pos >= c-1) break;
            if(s[pos+1] == '#')
            {
                cout << "No" << endl;
                return 0;
            }
            pos++;
        }
        pos = b-1;
        bool ok = false;
        while(pos <= d+1)
        {
            int count = 0;
            while(pos <= d+1 && s[pos] == '.')
            {
                pos++;
                count++;
            }
            if(count >= 3)
            {
                ok = true;
                break;
            }
            pos++;
        }
        if(!ok)
        {
            cout << "No" << endl;
            return 0;
        }
        cout << "Yes" << endl;
    }
}


Measured memory_bytes: 640
#include <math.h>
#include <time.h>
#include <ctype.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include<iomanip>

#define mod 1000000007
#define ll long long int
#define pb(x) push_back(x)
#define MP(x,y) make_pair(x,y)

using namespace std;

ll power(ll a, ll b, ll m)
{
	if (b == 0)
		return(1);
	ll sol = power(a, b / 2, m);
	sol = (sol * sol) % m;
	if (b % 2 == 1)
		sol = (sol * a) % m;
	return(sol);
}

ll gcd(ll a, ll b)
{
	if (b == 0)
		return a;
	else
	{
		return gcd(b, a % b);
	}
}
void solve()
{
	int n, d;
	cin >> n >> d;
	int sol = (n + (2*d+1) - 1) / (2*d+1);
	cout << sol;
}
int main()
{
	int t = 1;
	//cin >> t;
	while (t--)
		solve();
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <valarray>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <iomanip>
#include <map>
#include <set>
#include <list>
#include <limits>
#include <numeric>
#include <utility>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#include <array>
#include <bitset>
#include <complex>
#include <tuple>
#include <random>

using namespace std;
using ll = long long;
using ld = long double;
const int INF = 1e9;
const ld EPS = 1e-9;
const ll MOD = 1e9 + 7;

int main()
{
  int n;
  cin >> n;
  vector<int> x(n);
  for (auto &e : x)
    cin >> e;
  int ans = INF;
  for (int j = 0; j <= 100; ++j)
  {
    int sum = 0;
    for (int i = 0; i < n; ++i)
    {
      sum += pow(x[i] - j, 2);
    }
    ans = min(ans, sum);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
vector<ll> V;
int pre[maxn];
int ans[maxn];
int main() {
    int n,x,y;cin>>n>>x>>y;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            ans[min(j-i,abs(j-y)+abs(i-x)+1)]++;
        }
    }
    for(int i=1;i<n;i++)
        cout<<ans[i]<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ldb = long double;
using pa = pair < ll, ll >;
using vec = vector < ll >;
#define pb push_back
#define F  first
#define S  second
#define f(i,x,n) for(ll i=x;i<n;i++) 
#define all(c) c.begin(),c.end()
#define edl "\n"
#define str string
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
const int MOD = 1e9 + 7, N = 1e5 + 10;
const ll LINF = LLONG_MAX;
int main() {
    fast();

    ll n;
    cin >> n;
    cout<<"ABC"<<n;  

    cerr << "Time taken: " << int((clock() * 1000.) / CLOCKS_PER_SEC) << "ms\n";
    return 0;
}
 

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int main(){

  
  int N ,K;
  cin>>N>>K;
  double ans=0;
  for (int i=1;i<=N;i++){
      double tmp=1;
      int now=i;
      while(now<K){
          now*=2;
          tmp/=2;
      }
      ans+=tmp;

  }
  ans/=N;
  cout <<fixed<<setprecision(10)<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
import Data.List
import qualified Data.ByteString.Char8 as B
import Data.Char

main :: IO ()
main = breads >>= main'
    where
        main' [a, b] = getLine >>= putStrLn . solve a b 

solve :: Int -> Int -> String -> String
solve a b s
    | y == '-' && all isDigit xs && all isDigit ys = "Yes"
    | otherwise = "No"
    where
        (xs, y : ys) = splitAt a s

breads :: IO [Int]
breads = unfoldr uff <$> B.getLine
    where
        uff b = check <$> B.readInt b
        check (a, b)
            | B.null b = (a, b)
            | otherwise = (a, B.tail b)

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

int N, Z, W;
vector<int> a;

int memo[2][2001][2001];
int dfs(int t, int n, int prev_n) {
  if (memo[t % 2][n][prev_n] != -1) return memo[t % 2][n][prev_n];
  int ret;
  if (t % 2 == 0) {
    ret = -1;
    for (int i = n; i < N; i++) {
      if (i + 1 != N) ret = max(dfs(t + 1, i + 1, i), ret);
      else ret = max(ret, abs(a[i] - a[prev_n]));
    }
  } else {
    ret = 1e9 + 1;
    for (int i = n; i < N; i++) {
      if (i + 1 != N) ret = min(dfs(t + 1, i + 1, i), ret);
      else ret = min(ret, abs(a[i] - a[prev_n]));
    }
  }
  return memo[t % 2][n][prev_n] = ret;
}

int main(void) {
  cin >> N >> Z >> W;
  memset(memo, -1, sizeof(memo));
  a = vector<int>(N + 1);
  for (int i = 0; i < N; i++) {
    cin >> a[i];
  }
  a[N] = W;
  cout << dfs(0, 0, N) << endl;
  return 0;
}


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

using namespace std;
using vi = vector<int>;

// int const            INF = 1e9;
int const            M  = 3;
map<char, int> const id = {{'r', 0}, {'s', 1}, {'p', 2}};

int arg_max(vector<int> v)
{
    return distance(v.begin(), max_element(v.begin(), v.end()));
}

vector<vi> transpose(const vector<vi> &mat)
{
    int        n = mat.size(), m = mat[0].size();
    vector<vi> ans(m, vi(n, 0));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            ans[j][i] = mat[i][j];
    return ans;
}

int solve(int n, int k, vector<vi> reward, vi t)
{
    int        ans      = 0, last;
    vector<vi> reward_T = transpose(reward);

    for (int res = 0; res < k; ++res)
    {
        last = -1;
        for (int i = res; i < n; i += k)
        {
            if (t[i] == last)
            {
                if (i + k < n)
                {
                    for (int j = 0; j < M; ++j)
                        if (j != t[i] and j != t[i + k])
                            last = j;
                }
            }
            else
            {
                last = t[i];
                ans += reward[arg_max(reward_T[t[i]])][t[i]];
            }
        }
    }
    return ans;
}

int main(void)
{
    int        n, k;
    string     t;
    vi         tp;
    vector<vi> reward(M, vi(M, 0));

    cin >> n >> k;
    cin >> reward[0][1] >> reward[1][2] >> reward[2][0];
    cin >> t;

    tp.resize(n);
    for (int i = 0; i < n; ++i)
        tp[i] = id.at(t[i]);

    cout << solve(n, k, reward, tp) << endl;

    return 0;
}


Measured memory_bytes: 4316
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <iomanip>
using namespace std;
  
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define RREP(i,n) for(int (i)=(int)(n)-1;i>=0;i--)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
typedef long long ll;

long long FibonacciNumber(long long n, long long mod) {
    long long A[2][2] = {{1, 1}, {1, 0}};
    long long M[2][2] = {{1, 0}, {0, 1}};
    while (n > 0) {
        if (n & 1) {
            long long M_00 = M[0][0] * A[0][0] + M[0][1] * A[1][0];
            long long M_01 = M[0][0] * A[0][1] + M[0][1] * A[1][1];
            long long M_10 = M[1][0] * A[0][0] + M[1][1] * A[1][0];
            long long M_11 = M[1][0] * A[0][1] + M[1][1] * A[1][1];
            M[0][0] = M_00 % mod;
            M[0][1] = M_01 % mod;
            M[1][0] = M_10 % mod;
            M[1][1] = M_11 % mod;
        }
        long long A_00 = A[0][0] * A[0][0] + A[0][1] * A[1][0];
        long long A_01 = A[0][0] * A[0][1] + A[0][1] * A[1][1];
        long long A_10 = A[1][0] * A[0][0] + A[1][1] * A[1][0];
        long long A_11 = A[1][0] * A[0][1] + A[1][1] * A[1][1];
        A[0][0] = A_00 % mod;
        A[0][1] = A_01 % mod;
        A[1][0] = A_10 % mod;
        A[1][1] = A_11 % mod;
        n >>= 1;
    }
    return M[1][0];
}

int main() {

    ll n; cin >> n;
    cout << FibonacciNumber(n + 1, 1e18) << endl;
   
    return 0;
}

Measured memory_bytes: 3092
import Foundation

let array = readLine()!.componentsSeparatedByString(" ")
let numOfPeople = Int(array[0])!
let trainFee = Int(array[1])!
let taxiFee = Int(array[2])!

if trainFee * numOfPeople < taxiFee {
  print(trainFee * numOfPeople)
} else {
  print(taxiFee)
}

Measured memory_bytes: 7908
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll Mod = 1000000007;
int main() {
  ll N,X;
  cin >> N >> X;
  ll a = min(X,N-X);
  ll b = max(X,N-X);
  ll ans = N;
  ans += (b/a) * 2 * a;
  while (b % a != 0) {
    ll c = b % a;
    b = a;
    a = c;
    ans += ((b/a) * 2 * a);
    if (b % a == 0) {
      break;
    }
  }
  ans -= a;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
seito_tensu = []
tensu = []
seito = 0
while seito < 50:
    m, f, r = [int(e) for e in input().split()]
    seito += 1
    if m==-1and f==-1 and r==-1:
        break
    else:
        seito_tensu = [m, f, r]
        tensu.append(seito_tensu)
        
for x in range(len(tensu)):
    if tensu[x][0]==-1 or tensu[x][1]==-1:
        print("F")
    elif tensu[x][0]+tensu[x][1]>=80:
        print("A")
    elif tensu[x][0]+tensu[x][1]>=65 and tensu[x][0]+tensu[x][1]<80:
        print("B")
    elif tensu[x][0]+tensu[x][1]>=50 and tensu[x][0]+tensu[x][1]<65:
        print("C")
    elif tensu[x][0]+tensu[x][1]>=30 and tensu[x][0]+tensu[x][1]<50:
        if tensu[x][2]>=50:
            print("C")
        else:
            print("D")
    else:
        print("F")



Measured memory_bytes: 5612
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int INF=INT_MAX;
const ld PI=3.1415926535838797323;
const ld E=2.71828183;
const int MOD=1e9+7;
vi bfs(vector<vi>adj,int src){
    //adjacency list, not-weighted, possibly directed ,src is 1-indexed, adj[0].size()=0!!!
    //for n vertices, adj.size()=n+1. (constructed via push_back() ).

    queue<int>q;
    q.push(src);
    vi dst(adj.size(),INF);
    dst[src]=0;
    while(!q.empty()){
        int c=q.front();
        q.pop();
        for(int nbr:adj[c]){
            if(dst[nbr]==INF){
                dst[nbr]=dst[c]+1;
                q.push(nbr);
            }
        }
    }
    return dst;
}
vi bfsParents(vector<vi>adj,int src){
    vi parents=vi(adj.size(),INF);
    parents[src]=-1;
    queue<int>q;
    q.push(src);
    vi dst(adj.size(),INF);
    dst[src]=0;
    while(!q.empty()){
        int c=q.front();
        q.pop();
        for(int nbr:adj[c]){
            if(dst[nbr]==INF){
                parents[nbr]=c;
                dst[nbr]=dst[c]+1;
                q.push(nbr);
            }
        }
    }
    return parents;
}
int powMod(int base,int exp,int mod){
    //base^exp %mod
    int ans=1;
    for(int i=0; i<exp; i++)
        ans=((ans%mod)*(base%mod))%mod;
    return ans;
}
vi divisorsOf(int n){
    //vector of divisors of n (inc. 1 , excl.n)
    vi ans;
    for(int i=1; i*i<=n; i++){
        if(n%i==0)
            ans.push_back(i);
        if(i*i!=n && i!=1)
            ans.push_back(n/i);
    }
    return ans;
}

void solve();

int main() {
    //  int t;
    //cin >> t;
    //while(t--)
    solve();
}
void solve(){
    int n,m;
    cin >> n >> m;
    vector<vi>adj(n+1);
    for(int i=0; i<m; i++){
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vi dst=bfs(adj,1);
    vi parents=bfsParents(adj,1);
    for(int i=1; i<=n; i++)
        if(dst[i]==INF){
            cout << "No\n";
            return;
        }
    cout << "Yes\n";
    for(int i=2; i<=n ; i++)
        cout << parents[i] << "\n";

}

Measured memory_bytes: 16624
import java.util.*;
import java.lang.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] a = new int[M];
		int[] b = new int[M];
		int count = 1;
		int[] land = new int[N+1];     
		for( int i=0; i<M; i++ ){
			a[i] = sc.nextInt();
			b[i] = sc.nextInt();
			if( a[i]==1 ){
				land[count] = b[i];
				count++;
			}
			if( b[i]==N ){
				land[count] = a[i];
				count++;
			}           
		}       
		Arrays.sort(land);  
		for( int i=N-count+1; i<=N-1; i++ ){
			if( land[i]==land[i+1] ){
				System.out.println("POSSIBLE");
				break;
			}
			if( i==N-1 ){
				System.out.println("IMPOSSIBLE");
			}
		}
	}
}


Measured memory_bytes: 100460
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const ll inf = (1 << 30) - 1;
const ll infll = (1LL << 61) - 1;

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    cout << ((b * 10 + c) % 4 == 0 ? "YES" : "NO") << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Scanner;

class Main{

	static int N;
	static int M;
	static 		ArrayList<ArrayList<Integer>> map;
	static boolean[] used;
	static int f = 0;
	static int s = 0;

	static int mindis = 1000000000;
	static ArrayList<Integer> saitan;




	public static void main(String[] args) {


		Scanner sc = new Scanner(System.in);			//文字の入力
		String x = sc.next();
		
		if(x.length() == 2){
			System.out.println(0);
			return;
		}
		
		
		x = x.substring(0,x.length()-1);

int l = x.length();
		for(int i = 0;i < l;i++){

			if(x.length()%2 == 0){
				String f = x.substring(0, x.length()/2);		
				String b = x.substring(x.length()/2);



				for(int j = 0;j < f.length();j++){

					if(f.charAt(j) != b.charAt(j)){
						break;
					}else if(j == f.length()-1){
						System.out.println(x.length());
						return;
					}
				}

				

			}
			x = x.substring(0,x.length()-1);


		}
	}

}




Measured memory_bytes: 23764
#include <iostream>
#include <vector>
#include <algorithm>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

int main(){
  int a[3];
  cin >> a[0];
  cin >> a[1];
  cin >> a[2];

  int diff[3];

  diff[0] = abs(a[0] - a[1]);
  diff[1] = abs(a[1] - a[2]);
  diff[2] = abs(a[2] - a[0]);


  SORT(diff, 3);

  cout << diff[0]+diff[1] << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <tuple>

using namespace std;
using ll = long long;
using ull = unsigned long long;
#define out(S) cout<<(S)<<endl;
#define REP(i,b) for(size_t i=0;i<(b);i++)
#define rREP(i,b) for(int i=(b)-1;i>=0;i--)
#define FOR(i,a,b) for(size_t i=(a);i<(b);i++)
#define rFOR(i,a,b) for(int i=(b)-1;i>=0;i--)
#define Foreach(item,collection) for(auto item:collection)
#define mod(i) ((i) % (ll)(1e9 + 7))
ll modpow(ll i, ll j) { ll tmp = 1; while (j) { if (j % 2)tmp = mod(tmp*i); i = mod(i*i); j /= 2; }return tmp; }
#define divmod(a,b) (mod(a * modpow((ll)b,(ll)(1e9 + 5))))
#define Yes out("Yes")
#define No out("No")
#define NO out("NO")
#define YES out("YES")
#define INF 1e10;
#define ShowAll(collection) for(auto i:collection){out(i);}
#define IfOut(condition,text) if((condition)){out(text);return 0;}
#define IfeOut(condition,itext,etext) if(condition){out(itext);return 0;}else{out(etext);return 0;}
#define Select(collection,condition,result) Foreach(i,collection){result+=condition;}
#define GetAuto(_N,vect) {cin>>N;vect.resize(N);REP(i,_N){cin>>vect[i];}}
void removeAt(string& s, int index) { s.erase(index, 1); }
template<typename T> void removeAt(vector<T>& v, int index) { v.erase(v.begin() + index); }
ll manhattanDistance(ll x1, ll y1, ll x2, ll y2) { return (abs(x2 - x1) + abs(y2 - y1)); }

bool check(string t) {
	char c = t[0];
	Foreach(item, t) if (c != item) return false;
	return true;
}

int main() {
	string s;
	cin >> s;
	map<char, int> m;
	int ans = INF;
	Foreach(item, s) {
		string t = s;
		int cnt = 0;
		while (!check(t))
		{
			cnt++;
			string tmp = "";
			FOR(i, 0, t.size()-1) {
				tmp += t[i + 1] == item ? item : t[i];
			}
			t = tmp;
		}
		ans = min(ans, cnt);
	}
	out(ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ff first
#define ss second
#define sf scanf
#define pf printf
#define MAX 200002
#define INF 100000000000000
#define EXP 1e-6
#define endl '\n'
#define all(v) v.begin(), v.end()
#define FOR(i, a, b, c) for( int i = a; i < b; i+=c )
#define rep(i, a) for( int i = 0; i < a; i++ )
#define fastio ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);

typedef long long ll;
const int maxn = 2e5 + 10;
const ll MOD = 1e9 + 7;

using namespace std;

typedef pair <int, int> ii;
typedef pair <int, ii> trie;
typedef vector <int> vi;
typedef vector <ii> vii;
typedef vector <vii> vvii;
typedef vector <vi> vvi;
typedef vector <bool> vb;
typedef vector <trie> vtrie;
typedef bitset <maxn> bs;

int n;
int points[maxn][4];
ll dp[maxn][4];

ll knapsack( int pos, int pre_pos ) {

	ll &ret = dp[pos][pre_pos];
	if( pos >= n ) return 0LL;
	if( ret != -1 ) return ret;

	ll max_hapiness = 0LL;
	for( int i = 1; i < 4; i++ )
		if( i != pre_pos )
			max_hapiness = max( max_hapiness, knapsack(pos + 1, i) + points[pos][i] );
	return ret = max_hapiness;
}

int main()
{
	fastio

    cin >> n;
    for( int i = 0; i < n; i++ )
    	cin >> points[i][1] >> points[i][2] >> points[i][3];

    memset( dp, -1, sizeof(dp) );
    cout << knapsack( 0, 0 ) << endl;

	return 0;

}

Measured memory_bytes: 14720
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

int main() {

	int d[100000];
	
	int dd[10][10];
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> dd[i][j];
		}
		d[i] = dd[0][i];
	}

	for (int i = 10; i < 100000; i++) {
		int a = i / 10;
		int b = i % 10;
		d[i] = dd[d[a]][b];
	}
	/*
	for (int i = 0; i < 100000; i++) {
		if (d[i] < 0 || 9 < d[i]) {
			cout << i << ' ' << d[i] << endl;
		}
	}
	*/
	int ans = 0;
	//cout << 'a' << endl;
	for (int i = 0; i < 10000; i++) {
		//cout << i << endl;
		int cos = 0;
		int kari = i*10+d[i];
		vector<int> p(5);
		p[0] = kari / 10000;
		kari %= 10000;
		p[1] = kari / 1000;
		kari %= 1000;
		p[2] = kari / 100;
		kari %= 100;
		p[3] = kari / 10;
		kari %= 10;
		p[4] = kari;
		
		kari = i * 10 + d[i];

		for (int j = 0; j < 5; j++) {
			vector<int> q(5);
			q = p;
			for (int k = 0; k < 10; k++) {
				q[j] = k;
				int n = 0;
				for (int l = 0; l < 5; l++) {
					n *= 10;
					n += q[l];
				}
				if (d[n] == 0 && n != kari) {
					cos++;
				}
			}
		}
		
		for (int j = 0; j < 4; j++) {
			vector<int> q(5);
			q = p;
			swap(q[j], q[j + 1]);
			int n = 0;
			for (int k = 0; k < 5; k++) {
				n *= 10;
				n += q[k];
			}
			if (d[n] == 0 && n != kari) {
				cos++;
			}
		}
		if (cos > 0) {
			ans++;
			//cout << i << endl;
		}
	}

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

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

#define vi vector<int>

const int N = 2e5 + 10 ;
vi g[N] ;

int main () {
	int n ,  m ;
	cin >> n >> m ;
	for (int i = 0 ; i < m ; ++i) {
		int u , v ;
		cin >> u >> v ;
		g[u].push_back(v) ;
		g[v].push_back(u) ;
	}
	vi ans (n+1 , -1) ;
	queue <int> q ;
	q.push(1) ;
	while (q.size()) {
		int node = q.front() ;
		q.pop() ;
		for (int &i : g[node]) {
			if (ans[i] != -1) {
				continue ;
			}
			ans[i] = node ;
			q.push(i) ;
		}
	}
	for (int i = 2 ; i <= n ; ++i) {
		if (ans[i] == -1) {
			cout << "No" ;
			return 0 ;
		}
	}
	cout << "Yes\n" ;
	for (int i = 2 ; i <= n ; ++i) {
		cout << ans[i] << '\n' ;
	}
}

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

int main() {
  int n;
  ll k;
  cin >> n >> k;
  vector<int> a(n);
  vector<int> f(n);
  rep(i, n) cin >> a[i];
  rep(i, n) cin >> f[i];
  sort(a.begin(), a.end());
  sort(f.rbegin(), f.rend());
  ll l = -1, r = 1e12;
  while (l+1 < r){
    ll c = (l+r) / 2;
    bool ok = [&]{
      ll s = 0;
      rep(i, n){
        s += max(0ll, a[i]-c/f[i]);
      }
      return s <= k;
    }();
    if(ok) r = c;
    else l = c;
  }
  cout << r << endl;
  return 0;
}


Measured memory_bytes: 4844
using Microsoft.VisualBasic;
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace AtCoder
{
	public class ABC
	{
		static public void Main(string[] args)
		{
			Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
			Solve(args);
			Console.Out.Flush();
		}

		const int mod = 1000000007;  // 10^9+7
		static int Mod(long x, int m) { return (int)((x % m + m) % m); }
		static long Mod(long x, long m) { return (x % m + m) % m; }

		static public void Solve(string[] args)
		{
			//string s = Console.ReadLine();
			//int n = int.Parse(Console.ReadLine());
			//long x = long.Parse(Console.ReadLine());
			//int[] vs = Console.ReadLine().Split().Select(int.Parse).ToArray();
			//long[] vs = Console.ReadLine().Split().Select(long.Parse).ToArray();

			int[] vs = Console.ReadLine().Split().Select(int.Parse).ToArray();
			int h = vs[0];
			int w = vs[1];
			int k = vs[2];

			string[] s = new string[h];
			for (int i = 0; i < h; i++) {
				s[i] = Console.ReadLine();
			}

			int ans = 0;
			int x = 1 << w;
			int y = 1 << h;
			for (int i = 0; i < x; i++) {
				for (int j = 0; j < y; j++) {
					int c = Count(s, i, j);
					if (c == k) {
						//System.Diagnostics.Debug.WriteLine($"{Convert.ToString(i, 2),3} {Convert.ToString(j, 2),3} {c}");
						ans++;
					}
				}
			}
			Console.WriteLine(ans);

		}

		static int Count(string[] s, int x, int y)
		{
			int result = 0;
			for (int i = 0; i < s[0].Length; i++) {
				for (int j = 0; j < s.Length; j++) {
					if ((x & (1 << i)) == 0 && (y & (1 << j)) == 0 && s[j][i] == '#') {
						result++;
					}

				}
			}
			return result;
		}

	}
}


Measured memory_bytes: 28288
n = input()

if n[-1] == '2' or n[-1] == '4' or n[-1] == '5' or n[-1] == '7' or n[-1] == '9':
  print('hon')
elif n[-1] == '0' or n[-1] == '1' or n[-1] == '6' or n[-1] == '8':
  print('pon')
elif n[-1] == '3':
  print('bon')

  

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

int main(){
    int n;
    cin >> n;
    int t,x,y;
    int rt = 0;
    int rx = 0;
    int ry = 0;
    int p;
    for(int i=0; i!=n; i++){
        cin >> t >> x >> y;
        if(x - rx < 0){
            p = (x - rx) * -1;
        }else{
            p = x - rx;
        }
        rx = x;
        if(y - ry < 0){
            p = (y - ry) * -1 + p;
        }else{
            p = y - ry + p;
        }
        ry = y;
        t = t - rt;
        if(t < p || (t - p) % 2 != 0){
            cout << "No\n";
            return 0;
        }
        rt = rt + t;
    }
    cout << "Yes\n";
    return 0;
}

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

int main(){
	ll a,v;	cin>>a>>v;
 	ll b,w;	cin>>b>>w;
  	ll t;	cin>>t;
  if(v>w){
  	double temp=abs(b-a)*(1.0);
    double tm=v-w;
   	double p=(temp/tm);
    if(p<=t){
    	cout<<"YES"<<endl;
    }
    else{
    	cout<<"NO"<<endl;
    }
  }
  else{
  	cout<<"NO"<<endl;
  }
  return 0;
}


Measured memory_bytes: 3592
n, k = gets.chomp.split(' ').map(&:to_i)

ar = []
n.times do |n|
  ar << gets.chomp.to_i
end

ar = ar.sort.reverse

min = ar.first * k

(0..n-k).each do |i|
  n = ar[i] - ar[i+k-1]
  if n < min
    min = n
  end
end

puts min


Measured memory_bytes: 4216
import itertools

while 1:
    n = int(input())
    k = int(input())
    if n == 0:
        break

    card = []
    for _ in range(n):
        num = int(input())
        card.append(num)

    ans = []
    for permu in itertools.permutations(card, k):
        num = ''.join(str(p) for p in permu)
        ans.append(num)

    ans = list(set(ans))
    print(len(ans))



Measured memory_bytes: 6100
#define _USE_MATH_DEFINES

#include <iostream>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <set>
#include <utility>
#include <vector>
#include <list>
#include <algorithm>
#include <regex>
#include <cmath>
#include <map>
#include <iterator>
#include <climits>
#include <numeric>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <array>
#include <valarray>
#include <complex>
#include <random>
#include <functional>
#include <cassert>
#include <chrono>
#include <memory>

using namespace std;

#define int long long
//region TEMPLATE
////@formatter:off
//#define double long double
typedef long long ll;
typedef unsigned long long ull;
template<typename T>
void __read(T &a) { cin >> a; }
template<typename T, typename ... Args>
void __read(T &a, Args &... args) {cin >> a;__read(args...);}
#define make(t, ...) t __VA_ARGS__; __read(__VA_ARGS__)
#define makev(a, n) VI a(n); FOR(n) cin >> a[i]
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define FORIT(p) for(auto it = p.begin(); it != p.end(); it++)
#define FOR(b) for(signed i = 0; i <(b); i++)
#define FORE(i, l, r) for(int i = (l); i < (r); i++)
#define NFOR(i, n) for(int i = (((int) n)-1); i >= 0; i--)
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef pair<pair<int, int>, int> PPII;
constexpr ll M7 = 1000000007ll;
constexpr ll M9 = 1000000009ll;
constexpr ll MFFT = 998244353ll;
template<class T>
void outv(const T &a) { for (auto &x : a) cout << x << ' '; }
static mt19937 rnd(static_cast<unsigned>(chrono::steady_clock::now().time_since_epoch().count())); // NOLINT(cert-err58-cpp)
auto __fast_io__ = (ios_base::sync_with_stdio(false), cin.tie(nullptr)); // NOLINT(cert-err58-cpp,cppcoreguidelines-interfaces-global-init)
////@formatter:on
//endregion



int32_t main() {
    make(int, n);
    VVI cnt(50, VI(30));
    int ans = 0;
    for(int i = 0; i < n; ++i){
        make(double, q);
        int num = q * 1'000'000'000 + 0.5;
        int cnt2 = 0;
        while(num % 2 == 0){
            num /= 2;
            cnt2++;
        }
        int cnt5 = 0;
        while(num % 5 == 0){
            num /= 5;
            cnt5++;
        }
        for(int j = 0; j < 50; ++j){
            for(int k = 0; k < 30; ++k){
                if (cnt2 + j >= 18 && cnt5 + k >= 18){
                    ans += cnt[j][k];
                }
            }
        }
        cnt[cnt2][cnt5]++;
    }
    cout << ans;

    return 0;
}

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

using namespace std;

char m[][6] = {
  {},
  {5, '.', ',', '!', '?', ' '}, // 1
  {3, 'a', 'b', 'c'}, // 2
  {3, 'd', 'e', 'f'}, // 3
  {3, 'g', 'h', 'i'}, // 4
  {3, 'j', 'k', 'l'}, // 5
  {3, 'm', 'n', 'o'}, // 6
  {4, 'p', 'q', 'r', 's'}, // 7
  {3, 't', 'u', 'v'}, // 8
  {4, 'w', 'x', 'y', 'z'}, // 9
};

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

  while (N--) {
    string str;
    cin >> str;

    int s = 0, cnt = -1;
    for (int i=0; i<str.size(); i++) {
      int d = str[i] - '0';
      if (d == 0) {
        if (s != 0) { cout << m[s][ (cnt % m[s][0]) + 1 ]; }
        s = 0; cnt = -1;
      } else {
        s = d;
        cnt++;
      }
    }

    cout << endl;
  }

  return 0;
}

Measured memory_bytes: 3184
#include<stdio.h>

int N[6]={1,5,2,3,0,4};
int S[6]={4,0,2,3,5,1};
int E[6]={3,1,0,5,4,2};
int W[6]={2,1,5,0,4,3};
int O[6]={0,1,2,3,4,5};
int PT[8]={3,1,2,4,3,1,2,4};

void cpy(int *a,int *b,char dir){
    int i,*d;
    if(dir=='N'){
        d=N;   
    }
    else if(dir=='S'){
        d=S;
    }
    else if(dir=='E'){
        d=E;
    }
    else if (dir=='W'){
        d=W;
    }
    else {
        d=O;
    }
    for(i=0;i<6;i++){
        b[i]=a[d[i]];
    }
}
int chk(int *a,int *b){
    int i;
    for(i=0;i<6;i++){
        if (a[i]!=b[i]){
            break;
        }
    }
    return (i==6)? 1:0;
}
int main(void){
    int i,j,q,buf,d[6],c[6],e[6],ca[8],cb[4],fl=0;
    for(i=0;i<6;i++){
        scanf("%d",&e[i]);
    }
    for(i=0;i<6;i++){
        scanf("%d",&d[i]);
    }
    while(1){
        if(chk(d,e)) break;
        if(d[1]==e[0] || d[4]==e[0] || d[5]==e[0]){
            cpy(d,c,'O');cpy(c,d,'N');
        }
        else if(d[3]==e[0] || d[2]==e[0]){
            cpy(d,c,'O');cpy(c,d,'E');
        }
        else{
            break;
        }
    }
    for(i=0;i<8;i++){
        ca[i]=e[PT[i]];
        if(i<4){
            cb[i]=d[PT[i]];
        }
    }
    for(i=0;i<5;i++){
        if (ca[i]==cb[0] && ca[i+1]==cb[1] && ca[i+2]==cb[2] && ca[i+3]==cb[3]){fl=1;break;}
    }
    printf("%s\n",(fl)? "Yes":"No");
    return 0;
}


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

using namespace std;

typedef long long ll;
typedef vector <int> vi;
typedef vector <ll> vl;
typedef pair <ll, ll> dl;
typedef pair <int, int> ii;
typedef vector <ii> vii;
typedef vector <vi> graph;

int n, k;
ll arr[100010];
ll dp[100010];

ll piedra(int id) {
	if (id == n - 1) return 0;
	if (dp[id] != -1) return dp[id];
	ll temp, menor = 1000000000;
	for (int i = 1; i <= k && id + i < n; ++i)
	{
		temp = abs(arr[id] - arr[id + i]) + piedra(id + i);
		menor = min(temp, menor);
	}
	return dp[id] = menor;
}

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

	cin >> n >> k;
	for (int i = 0; i < n; ++i)
	{
		cin >> arr[i];
	}
	for (int i = 0; i < 100010; ++i)
	{
		dp[i] = -1;
	}
	cout << piedra(0) << "\n";
    return 0;
}


Measured memory_bytes: 6528
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
ll INFL = 1000000000000000010;//10^18 = 2^60
int INF = 2147483600;//10^9
ll MOD  = 1000000007;
int main(void){
    // Your code here!
    
    int a,b;
    cin >> a >> b;
    
    int ans = 0;
    ans += (a-1);
    if(a <= b) ans++;
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
const LL N=1e6;
LL n,v[50];
struct data {
    LL x,y;
}a[N+10];
LL Abs(LL x) {
    return (x<0)?(-x):x;
}
int main() {
    scanf("%lld",&n);
    for (int i=1;i<=n;i++) {        
        scanf("%lld%lld",&a[i].x,&a[i].y);
        if (((a[i].x+a[i].y)%2+2)%2!=(((a[1].x+a[1].y)%2)+2)%2) {
            printf("-1\n");
            return 0;
        }
    }
    LL m;
    if ((a[1].x+a[1].y)%2==0) {
        m=32;
        v[1]=1;
        for (int i=2;i<=32;i++) v[i]=(1<<(i-2));
    }
    else {
        m=31;
        for (int i=1;i<=31;i++) v[i]=(1<<(i-1));
    }
    printf("%lld\n",m);
    for (int i=m;i>=1;i--) printf("%lld ",v[i]);
    printf("\n");
    for (int i=1;i<=n;i++) {
        LL nowx=0,nowy=0;
        for (int j=m;j>=1;j--) {
            char ch=' ';
            LL now=2e12;
            if (Abs(nowx+v[j]-a[i].x)+Abs(nowy-a[i].y)<now) {
                ch='R';
                now=Abs(nowx+v[j]-a[i].x)+Abs(nowy-a[i].y);
            }
            if (Abs(nowx-v[j]-a[i].x)+Abs(nowy-a[i].y)<now) {
                ch='L';
                now=Abs(nowx-v[j]-a[i].x)+Abs(nowy-a[i].y);
            }
            if (Abs(nowx-a[i].x)+Abs(nowy+v[j]-a[i].y)<now) {
                ch='U';
                now=Abs(nowx-a[i].x)+Abs(nowy+v[j]-a[i].y);
            }
            if (Abs(nowx-a[i].x)+Abs(nowy-v[j]-a[i].y)<now) {
                ch='D';
                now=Abs(nowx-a[i].x)+Abs(nowy-v[j]-a[i].y);
            }
            putchar(ch);
            if (ch=='R') nowx+=v[j];
            else if (ch=='L') nowx-=v[j];
            else if (ch=='U') nowy+=v[j];
            else nowy-=v[j];
        }
        putchar('\n');
    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
    int a,b;
    int i=0,sum=0;

    while(scanf("%d %d", &a,&b) != EOF){
        sum = a + b;
        while(sum){
            sum /= 10;
            i++;
            }
            printf("%d\n",i);
            i=0;
    }
    return(0);
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int n;
int t[125252];
int a[125252];
int mx[125252],mn[125252];

int main(){
  scanf("%d",&n);
  REP(i,n)scanf("%d",t+i);
  REP(i,n)scanf("%d",a+i);
  REP(i,n)mx[i]=MOD, mn[i]=1;
  REP(i,n){
    CHMIN(mx[i],t[i]);
    if(i==0 || t[i-1]<t[i]){
      CHMAX(mn[i],t[i]);
    }
  }
  FORR(i,0,n){
    CHMIN(mx[i],a[i]);
    if(i==n-1 || a[i+1]<a[i]){
      CHMAX(mn[i],a[i]);
    }
  }
  ll ans = 1;
  REP(i,n){
    int haba = mx[i] - mn[i] + 1;
    if(haba<=0){
      ans = 0;
    }else{
      ans = (ans * haba) % MOD;
    }
  }
  printf("%lld\n",ans);
  return 0;
}


Measured memory_bytes: 1920
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>

using namespace std;

int main() {
	vector<int>a;
	int n, t, i, j;
	int time;

	cin >> n >> t;

	for (i = 0; i < n; i++) {
		cin >> j;
		a.push_back(j);
	}

	time = 0;
	for (i = 0; i < n - 1; i++) {
		if ((a[i + 1] - a[i]) <= t) {
			time += a[i + 1] - a[i];
		}
		else {
			time += t;
		}
	}
	time += t;

	cout << time;

	return 0;
}

Measured memory_bytes: 1400
def nCr_mod_p(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 5  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


n, k = map(int, input().split())
a = list( map(int, input().split()))
MOD = 10**9 + 7
ans = 0

a.sort()

for j in range(n):
    i = j +1
    if j <= n-k:
        minX = a[i-1]
        ans -= a[i-1]*nCr_mod_p(n-i,k-1,MOD)%MOD
    if k -1 <= i:
        maxX = a[i-1]
        ans += a[i-1]*nCr_mod_p(i-1,k-1,MOD)%MOD

print(ans%MOD)




Measured memory_bytes: 26752
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S, W;
  string DE[4] = {"maerd","esare","resare","remaerd"};
  int L, N, K;
  cin >> S;
  L = S.size();
  N = L;
  bool H = true;
  reverse(S.begin(), S.end());
  
  
  while(H){
     W = "";
     bool H2 = true;
     if(N == 0){
     break;
     }
     if(N < 5){
     H = false;
     break;
     }
    
     if(S.at(L - N) == 'm' || S.at(L - N) == 'e'){
     K = 0;
     }
     else if(S.at(L - N) == 'r'){
        if(S.at(L - N + 2) == 's'){
        K = 1;
        }
        else if(S.at(L - N + 2) == 'm'){
        K = 2;
        }
     }
        
     for(int i = 0;i < 5 + K;i++){
     W = W + S.at(L - N + i);
     }

     if(W == DE[0] || W == DE[1] || W == DE[2] || W == DE[3]){
     N = N - 5 - K;
     }
     else if(H2){
     H = false;
     }
  }
 
  if(H){
  cout << "YES" << endl;
  }
  else{
  cout << "NO" << endl;
  }
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
#define all(q) (q).begin(),(q).end()
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define MODADD(ADD_X,ADD_Y)  (ADD_X+ADD_Y)%MOD;
#define MODSUB(SUB_X,SUB_Y)  (SUB_X-SUB_Y)+MOD)%MOD;
#define MODMUL(MUL_X,MUL_Y)  (MUL_X*MUL_Y)%MOD;
#define LCM(LCM_X,LCM_Y) (LCM_X*LCM_Y)/__gcd(LCM_X,LCM_Y);
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
int dx[]= {1,0,-1,0,1,-1,1,-1};
int dy[]= {0,1,0,-1,1,-1,-1,1};
int arr[MAX];
int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
    string s;
    cin>>s;
    int n=s.length(),cnt=1;
    for(int i=1; i<n; i++)
    {
        if(s[i]=='R')
        {
            cnt++;
        }
        else
        {
           // cout<<i<<" "<<cnt<<endl;
            arr[i]+=cnt/2;
            arr[i-1]+=(cnt+1)/2;
            cnt=0;
        }
    }

    cnt=1;
    for(int i=n-2; i>=0; i--)
    {
        if(s[i]=='L')
        {
            cnt++;
        }
        else
        {
            arr[i]+=cnt/2;
            arr[i+1]+=(cnt+1)/2;
            cnt=0;
        }
    }
    for(int i=0;i<n;i++)
        cout<<arr[i]<<" ";


    return 0;
}


Measured memory_bytes: 4100
#include <iostream>
#include <string>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)

typedef long long ll;


string ss[] = {"SUN", "MON", "TUE", "WED", "THU", "FRI" , "SAT"};

int main(void) {
  string s;
  cin >> s;
  REP(i, 7) {
    if(ss[i] == s) {
      cout << (7 - i) << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
 
int p[300000][26];
int dp[300000];
 
int main(){
	string s;cin>>s;
	rep(i,26)p[s.size()][i]=s.size()+1;
	memset(dp,0x3f,sizeof(dp));
	dp[s.size()+1]=0;
	dp[s.size()]=1;
	for(int i=s.size()-1;i>=0;i--){
		rep(j,26){
			if(s[i]-'a'==j)p[i][j]=i+1;
			else p[i][j]=p[i+1][j];
			dp[i]=min(dp[i],dp[p[i][j]]+1);
		}
	}
	int pos=0;
	string ans;
	while(pos!=s.size()+1){
		rep(i,26){
			if(dp[p[pos][i]]==dp[pos]-1){
				ans+='a'+i;
				pos=p[pos][i];
				break;
			}
		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 23044
/* Author : Aaryan Srivastava ^__^ */ 
#include <bits/stdc++.h>
#include <random>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#define pb push_back
#define mp make_pair
#define ff first
#define ss second   
#define rep(i,n) for(int (i) = 0 ; i < (n) ; i++)
#define repA(i,x,y) for(int i = (x) ; i <= (y) ; i++)
#define repD(i,x,y) for(int i = (x) ; i >= (y) ; i--)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).end()
#define setval(a,val) memset(a,val,sizeof(a))
#define Randomize mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define trav(x , a) for(auto &x : a)
#define sz(a) ((int)a.size())
typedef long long ll ; 

#define int ll

using namespace std;

const int N = 3e5 +5 ;
const int mod = 1e9 + 7 ;
const ll inf = 1e18 ;
const int SZ = 101 ;
const double eps = 1e-9 ;
using namespace __gnu_pbds;
using ordered_set =  tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ;

typedef pair<int, int> pii; 
typedef pair<int , pii> ipii ;
typedef pair<pii , int> piii ; 
typedef unsigned long long ull ;
typedef long double ld;

ll po(ll x,ll y,ll p = mod) {ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}

void solve()
{
    int n; cin >> n ;
    int a[n];
    rep(i , n) cin >> a[i], a[i]--; 
    queue<pii> q;
    q.push({0 , 0});
    int vis[n] = {} ;
    while(!q.empty()){
        pii u = q.front();
        q.pop();
        if(vis[u.ff]) continue ;
        if(u.ff == 1){
            cout << u.ss ;
            return ;
        }
        vis[u.ff]=true;
        q.push({a[u.ff] , u.ss + 1});
    }
    cout << -1;

}   

     
int32_t main(int32_t argc, char *argv[])
{
    ios::sync_with_stdio(0);    
    cin.tie(0); cout.tie(0);
    int TC = 1, t = 0;
    //cin >> TC ;
    while(t++ < TC)
    {
        //cout << "Case #" << t << ": " ;
        solve();
        cout << "\n" ;
    }
    return 0;
}

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

signed main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);  
  cout.tie(0);   
#ifndef ONLINE_JUDGE
    if(fopen("INPUT.txt","r"))
    {
    freopen ("INPUT.txt" , "r" , stdin);
    freopen ("OUTPUT.txt" , "w" , stdout);
    }
#endif

  int k;
  int a,b;
  cin>>k>>a>>b;
  int z=(b/k)-(a-1)/k;
  if(z>0)
     cout<<"OK";
  else
    cout<<"NG";
  
}

Measured memory_bytes: 3656
#include<iostream>
#include <sstream>

using namespace std;

int par[100000];
int weight_diff[100000];

void init(int n){
  for(int i=0; i<n; i++) par[i] = i;
}
 
int root(int x){
  if(par[x] == x){
    return x;
  }else{
    int n = root(par[x]);
    weight_diff[x] += weight_diff[par[x]];
    return par[x] = n;
  }
}

int weight(int x) {
  root(x);
  return weight_diff[x];
}

int diff(int x, int y) {
  return weight(y) - weight(x);
}

bool same(int x, int y){
  return root(x) == root(y);
}
	
void unite(int x, int y, int w){
  w += weight(x); w -= weight(y);
  x = root(x);
  y = root(y);
  if(x == y) return;
  weight_diff[y] = w;
  par[y] = x;
}

int main()
{
  int n,q;
  cin >> n >> q;
  int p, a, b, w;
  init(n);
  for(int i=0; i<q; i++){
    cin >> p;
    if(p == 0){
      cin >> a >> b >> w;
      unite(a, b, w);
    }
    else{
      cin >> a >> b;
      cout << (same(a, b) ? to_string(diff(a,b)) : "?") << endl;
    }
  }
  
  return 0;
}



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

namespace _1_3_A {
    class Program {
        static void Main(string[] args) {
            var list = new List<KeyValuePair<int, int>>();
            var pair = new KeyValuePair<int, int>();
            while (true) {
                var input = Console.ReadLine();
                var array = input.Split(' ').Select(x => int.Parse(x)).ToArray();

                if (array[0] == 0 && array[1] == 0)
                    break;

                if (array[0] > array[1]) {
                    var temp = array[0];
                    array[0] = array[1];
                    array[1] = temp;
                }

                list.Add(new KeyValuePair<int, int>(array[0], array[1]));
            }
            list.ForEach(x => Console.WriteLine($"{x.Key} {x.Value}"));
        }
    }
}



Measured memory_bytes: 14308
N, M = gets.split.map(&:to_i)
ab = []
M.times {
  ab << gets.split.map(&:to_i)
}

a_b = []

ab.each do |abab|
  a_b << abab[0]
  a_b << abab[1]
end

N.times do |i|
count = a_b.count(i + 1)
p count
end

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

int main(){
  int N;
  cin >> N;
  bool ans = false;
  for(; N >= 4; N -= 4){
    if((N % 4)*(N % 7) == 0){
      ans = true;
    }
  }
  if(ans){
    cout << "Yes";
  }else{
    cout << "No";
  }
  return 0;
}


Measured memory_bytes: 3620