akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,ini,n) for(int i=ini;i<n;i++)
#define _rep(i,ini,n) for(int i=ini;i>=n;i--)
#define ToEnd(a) a.begin(),a.end()
uint64_t MOD=1000000007;

int main(){
    int H,W; cin>>H>>W;
    vector<vector<char>> V(H,vector<char>(W));
    int num=0;
    rep(h,0,H)rep(w,0,W) {cin>>V.at(h).at(w); if(V.at(h).at(w)=='#')num++;}

    pair<int,int> pos={0,0};
    string ans="Possible";
    while(pos!=make_pair(H-1,W-1)){
        num--;
        if(pos.first+1<H && V.at(pos.first+1).at(pos.second)=='#') pos.first++;
        else if(pos.second+1<W && V.at(pos.first).at(pos.second+1)=='#') pos.second++;
        else{ans="Impossible"; break;}
    }
    
    if(pos==make_pair(H-1,W-1)) num--;
    if(num>0) ans="Impossible";
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
ll fact[200001];
ll inv_fact[200001];
ll mod_pow(ll a, ll b) {
	if (b == 0) return 1;
	if (b % 2 == 0) {
		ll x = mod_pow(a, b / 2);
		return (x*x) % MOD;
	}
	return (a*mod_pow(a, b - 1)) % MOD;
}
ll comb(ll n, ll k) {
	if (n < k) return 0;
	ll ret = fact[n];
	(ret *= inv_fact[k]) %= MOD;
	(ret *= inv_fact[n - k]) %= MOD;
	return ret;
}
int main() {
	fact[0] = inv_fact[0] = 1;
	for (int i = 1; i <= 200000; i++) {
		fact[i] = (fact[i - 1] * i) % MOD;
		inv_fact[i] = (inv_fact[i - 1] * mod_pow(i, MOD - 2)) % MOD;
	}
	int H, W, A, B;
	cin >> H >> W >> A >> B;
	ll ans = 0;
	for (int i = 0; i < H - A; i++) {
		ll t = comb(i + B - 1, i);
		(t *= comb(H - i - 1 + W - B - 1, H - i - 1)) %= MOD;
		(ans += t) %= MOD;
	}
	cout << ans << endl;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define range(i,a,n) for(int i=(a);i<(n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}
void OUT(bool b){cout<<(b?"YES":"NO")<<endl;}
void Out(bool b){cout<<(b?"Yes":"No")<<endl;}
void out(bool b){cout<<(b?"yes":"no")<<endl;}
int popcnt(int x){return __builtin_popcount(x);}
int popcnt(ll x){return __builtin_popcountll(x);}
int bsr(int x){return 31 - __builtin_clz(x);}
int bsr(ll x){return 63 - __builtin_clzll(x);}
int bsf(int x){return __builtin_ctz(x);}
int bsf(ll x){return __builtin_ctzll(x);}

/*他のライブラリを入れる場所*/

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,a,b;
	cin>>n>>a>>b;
	//戻る必要ない気がする？
	vl x(n);
	rep(i,n)cin>>x[i];
	ll ans=0;
	rep(i,n-1){
		ans+=min((x[i+1]-x[i])*a,b);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
int main(){
	int n,m;//n:個数、m:ナップサックの上限重量
	scanf("%d %d",&n,&m);
	int dp[n][m+1];
	int v[n],w[n];//v:価値,w:重量
	int i,j;
	for(i=0;i<n;i++){
		scanf("%d %d",&v[i],&w[i]);
	}
	for(i=0;i<n;i++){
		for(j=0;j<=m;j++){
			dp[i][j]=0;
		}
	}
	for(i=w[0];i<=m;i++){
		dp[0][i]=v[0];
	}
	int a;//比較用
	for(i=1;i<n;i++){
		for(j=0;j<=m;j++){
			a=0;
			if(j>=w[i]){
				a=dp[i-1][j-w[i]]+v[i];
			}
			dp[i][j]=dp[i-1][j]>a?dp[i-1][j]:a;
		}
	}
	printf("%d\n",dp[n-1][m]);
	return 0;
}

Measured memory_bytes: 4504
#include <bits/stdc++.h>
 
#define ALL(l)  (l).begin(),(l).end()
#define rep(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using namespace std;
typedef long long ll;
//const ll mod =  1000000007;
//const ll maxn = 1000000000;

//---------------------------------------------------------------------------------------------------
using vi = vector<int>; // intの1次元の型に vi という別名をつける
using vll = vector<ll>; // intの1次元の型に vi という別名をつける
using vvll = vector<vll>; // intの2次元の型に vvi という別名をつける
using vs = vector<string>; // stringの1次元の型に vs という別名をつける
using pll = pair<ll, ll>; // これ以降 pii という型名はpair<ll, ll> と同じ意味で使える
//---------------------------------------------------------------------------------------------------

int main(){
  int n,bob=0,alice=0;
  cin>>n;
  vi a(n);
  rep(i,n)cin>>a.at(i);
  sort(ALL(a));
  if(n%2==0){
      for(int i=n-1;i>=0;i--){
          if(i%2==0)bob+=a.at(i);
          else alice+=a.at(i);
      }
  }else{
      for(int i=n-1;i>=0;i--){
          if(i%2!=0)bob+=a.at(i);
          else alice+=a.at(i);
      }
  }
  cout<<alice-bob<<endl;
  
}

   
    

   


    

   



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
const int INFTY =2147483647;
int main(){
    int n,m,s,c,A[3],ans=0;
    int x=true;
    cin>>n>>m;
    REP(i,3) A[i]=-1;
    REP(i,m){
        cin>>s>>c;
        if(A[(3-n)+s-1]==-1) A[(3-n)+s-1]=c;
        else if(A[(3-n)+s-1]!=c) x=false;
    }

    if(n>=2&&A[3-n]==0) x=false;
    else REP(i,3){
        if(A[i]==-1){
            if(i==3-n&&n>1)A[i]=1;
            else A[i]=0;
        }
    }
    if(x){
        REP(i,n) ans+=A[2-i]*pow(10,i);
        cout<<ans<<endl;
    }
    else cout<<-1<<endl;
}

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

int main()
{
    char s[4],t[4];

    scanf("%s",&s);
    scanf("%s",&t);

    int r = 0;

    for(int i = 0; i<=2; i++){
        if(s[i] == t[i]){
            r++;
        }
    }
    printf("%d",r);

    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define pb push_back
#define N 200001
#define ll long long
#define int ll 
#define pi pair<int , int>
#define pip pair<pair ,int>
#define mp make_pair 
#define f first
#define s second
#define mod 998244353
ll Mod(ll x, ll y, int p) 
{ll res = 1; x = x % p;
while (y > 0) 
{if(y & 1) res = (res*x) % p; 
y = y>>1;x = (x*x) % p; 
}return res; 
}
int* getlps(string pattern){
 int len = pattern.length();
 int * lps = new int[len];
 lps[0] = 0;
 int i = 1 , j = 0;
 while(i < len){
  if(pattern[i] == pattern[j]){
	  lps[i] = j+1;
   i++;
   j++;
  }
  else{
		if(j != 0){
		 j = lps[j-1];
		}
		else{
		 lps[i] = 0;
		 i++;
		}
  }
 }
 return lps;
}
class Triplet{
 public:
 int x ;
 int y ;
 int gcd;
};
Triplet extendedEuclid(int a , int b){
 if(b == 0){Triplet ans; ans.gcd = a;ans.x = 1;ans.y = 0;return ans;}
 Triplet smallAns = extendedEuclid(b , a%b);
 Triplet ans;
 ans.gcd = smallAns.gcd;
 ans.x = smallAns.y;
 ans.y = smallAns.x - (a/b)*smallAns.y;
 return ans;
}
int mmInverse(int a , int m){
 Triplet ans = extendedEuclid(a , m);
 return ans.x;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n  , su;
cin>>n>>su;
vector<pair<int , string>> v(su);
for(int i = 0 ; i < su ;i++){
 cin>>v[i].f;
 string str;
 cin>>str;
 v[i].s = str;
}
//sort(v.begin() , v.end());
int pen = 0;
int tell = 0;
int ac = 0;
map<int , int> m;
map<int , int> chut;
for(int i = 0 ; i < su ;i++){
  if(v[i].s[0] == 'W' && m.find(v[i].f) == m.end()){
       chut[v[i].f]++;
  }
  else if(v[i].s[0] == 'A' && m.find(v[i].f) == m.end()){
       ac++;
       pen += chut[v[i].f];
       m[v[i].f] = i;
  }
}
//pen += tell;
cout<<min(ac , n)<<" "<<pen<<endl;
}


Measured memory_bytes: 19072
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define PF push_front
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double
#define pii pair<int,int>
#define pll pair<LL,LL>
#define vi vector<int>
#define vii vector<vi>

const double pi = 3.14159265358979323846264;
const int mod=1000000007;

vector< int64_t > divisor(int64_t n) {
  vector< int64_t > ret;
  for(int64_t i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

int main(){
	 //cin.tie(0);
	//ios::sync_with_stdio(false);
	//std::cout << std::fixed;
	//std::cout << std::setprecision(12);
	//std::cout << std::defaultfloat;
	int n;
	cin>>n;
	vector<int> a(n+1,0);
	vector<int> ans;
	FOR(i,0,n){
		cin>>a[i+1];
	}
	FORD(i,n+1,1){
		if(a[i]!=0){
			ans.PB(i);
			a[i]=0;
			auto v=divisor(i);
			for(const auto& x:v){
				//cerr<<x<<" ";
				if(x==a[i])continue;
				a[x]^=1;
			}
			//cerr<<endl;
		}
	}

	cout<<ans.size()<<endl;
	for(const auto& x:ans){
		cout<<x<<endl;
	}


	return 0;
}


Measured memory_bytes: 2424
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define piii pair<pii,int>
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef long double ld;



int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	ll n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	int mi = 1000000000+5,ma = -1;
	for(int i=0;i<n;i++){
		if(a[i]>ma)ma = a[i];
		if(a[i]<mi) mi = a[i];
	}
	cout<<ma-mi<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define REP(i, d, n) for(int i=(d); i<(n); ++i)
typedef long long ll;
const int mod = 1e9 + 7;
int main() {

    int n;
    string s;
    cin >> n >> s;

    vector<int> v(n, 0);
    if(s[0] == 'W'){
        v[0] = 1;
    }
    REP(i, 1, n){
        v[i] = v[i-1];
        if(s[i] == 'W'){
            v[i]++;
        }
    }

    int ans = v[n-1];
    REP(i, 1, n){
        int tmp = v[i-1] + (n-(i+1) - (v[n-1]-v[i]));
        ans = min(ans, tmp);
    }
    ans = min(ans, n-v[n-1]);

    cout << ans << endl; 

    return 0;
}

Measured memory_bytes: 1796
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric>
#include <set>
#include <cstdlib>
#include <queue>
#include <map>

using namespace std;

typedef long long llint;
typedef long double ld;
#define inf 1e18
#define mod 1000000007
priority_queue<llint,vector<llint>,greater<llint>> que;
//priority_queue<llint> q;

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

llint n,a,b;

void solve(){
  cin >> n;
  int a[n];
  for(int i=0;i<n;i++)cin >> a[i];
  int ans=0;
  int m=n+1;
  for(int i=1;i<n;i++){
    if(a[i]==a[i-1]){
      a[i]=m;
      m++;
      ans++;
    }
  }
  cout << ans << endl;
}

int main(int argc, char *argv[]) {
  solve();
  return 0;
}


Measured memory_bytes: 256
package main
import (
  "bufio"
  "os"
  "strconv"
  "strings"
  "fmt"
)

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  buffer := make([]byte, 0)
  for true {
    line, isPrefix, err := reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func NextInt() int {
  n, _ := strconv.Atoi(NextLine())
  return n
}
func NextIntVec() []int {
  L := strings.Split(NextLine(), " ")
  N := make([]int, len(L))
  for i := range N {
    N[i], _ = strconv.Atoi(L[i])
  }
  return N
}
func Write(s interface{}) {
  fmt.Fprintln(writer, s)
}
func WriteIntVec(A []int) {
  S := make([]string, len(A))
  for i, a := range A {
    S[i] = strconv.Itoa(a)
  }
  Write(strings.Join(S, " "))
}
func Output() {
  _ = writer.Flush()
}

func Max(x, y int) int {
  if x < y { return y }
  return x
}

func main() {
  N := NextInt()
  A := NextIntVec()
  B := make([][][]int, len(A))
  for i, a := range A {
    B[i] = make([][]int, 2)
    B[i][0] = []int{a, i}
    B[i][1] = []int{0, -1}
  }
  for i, b := range B {
    for j := 0; j < N; j++ {
      k := i | (1 << uint(j))
      if B[k][0][0] < b[0][0] {
        B[k][1] = B[k][0]
        B[k][0] = b[0]
      } else if B[k][1][0] < b[0][0] && B[k][0][1] != b[0][1] {
        B[k][1] = b[0]
      }
      if B[k][1][0] < b[1][0] {
        B[k][1] = b[1]
      }
    }
  }
  ans := 0
  for _, b := range B[1:] {
    ans = Max(b[0][0] + b[1][0], ans)
    Write(ans)
  }
  Output()
}

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

int main(){
    int h,w,cnt[59][59];
    cin >> h >>w;
    char c[59][59];
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin >> c[i][j];
            cnt[i][j]=0;
        }
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(c[i][j]=='#'){
                for(int k=-1;k<=1;k++){
                    for(int l=-1;l<=1;l++){
                        if(0<=i+k && i+k<=h-1 && 0<=j+l && j+l<=w-1){
                            cnt[i+k][j+l]++;
                        }
                    }
                }
            }
        }
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(c[i][j]=='#'){
                cout << '#';
            }
            else{
                cout << cnt[i][j];
            }
        }
        cout << endl;
    }
}

Measured memory_bytes: 256
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n,k = LI()
    h = IR(n)
    h.sort()
    ans = float("inf")
    for i in range(n-k+1):
        ans = min(ans,h[i+k-1]-h[i])
    print(ans)

#D
def D():
    n,x = LI()
    l = [1 for i in range(n+1)]
    for i in range(n):
        l[i+1] = 2*l[i]+3
    p = [1 for i in range(n+1)]
    for i in range(n):
        p[i+1] = 2*p[i]+1
    ans = 0
    for i in range(1,n+1)[::-1]:
        if i == 1:
            if x == 5:ans += 3
            else:ans += max(0,x-1)
        else:
            if x == 0:continue
            if x == l[i]:
                ans += p[i]
                x = 0
            if x > l[i-1]+1:
                ans += p[i-1]+1
                x -= l[i-1]+2
            else:
                x -= 1
    print(ans)
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()


Measured memory_bytes: 38640
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//INSERT ABOVE HERE
template<typename T> signed size(const T &x){return x.size();}
signed main(){
  Int k,n;
  cin>>k>>n;
  if(k%2==0){
    cout<<k/2;
    for(Int i=1;i<n;i++) cout<<" "<<k;
    cout<<endl;
    return 0;
  }
  vector<Int> ans(n,(k+1)/2);
  for(Int i=0;i<n/2;i++){
    if(ans.back()==1) ans.pop_back();
    else{
      ans.back()--;
      while(size(ans)<n) ans.emplace_back(k);
    }
  }
  for(Int i=0;i<size(ans);i++){
    if(i) cout<<" ";
    cout<<ans[i];
  }
  cout<<endl;
  return 0;
}


Measured memory_bytes: 4608
import java.util.Scanner;
public class Main{
    public static void main (String [] args){
        Scanner sc =new Scanner(System.in);
        int a =sc.nextInt();
        int b =sc.nextInt();
        if((a-b)>0)System.out.println("a > b");
        else if((a-b)==0)System.out.println("a == b");
        else System.out.println("a < b");
        
        sc.close();
   }
 
}


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

#define ll long long
#define pb push_back

vector<int>g[100003];
vector<int>v(100003);
queue<int>q;

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

    ll in[n];
    pair<int,int>pr;
    vector<pair<int,int> >vec;
    for(int i=0;i<n;i++)
    {
        cin>>in[i];

        vec.pb({in[i],i+1});
    }
    sort(vec.begin(),vec.end());

    for(int i=0;i<n;i++)
    {
        cout<<vec[i].second<<" ";
    }
    cout<<endl;



}











Measured memory_bytes: 5236
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
typedef long long ll;
using namespace std;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
#define repi(i, n, init) for (ll i = init; i < (n); i++)

int main()
{
    int n, a = 0, b = 0, ab = 0, ans = 0;
    cin >> n;
    repi(i, n, 0)
    {
        string s;
        cin >> s;
        repi(j, s.size(), 1)
        {
            if (s.at(j) == 'B' && s.at(j - 1) == 'A')
                ans++;
        }
        if (s.at(0) == 'B' && s.at(s.size() - 1) == 'A')
            ab++;
        else if (s.at(0) == 'B')
            b++;
        else if (s.at(s.size() - 1) == 'A')
            a++;
    }
    if (ab == 0)
    {
        cout << ans + min(a, b) << endl;
    }
    else if (a + b == 0)
    {
        cout << ans + ab - 1 << endl;
    }
    else
    {
        cout << ans + ab + min(a,b) << endl;
    }
    return 0;
}

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

int main() {

  /* input data */
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i=0;i<N;i++){
    cin >> A.at(i);
  }
  
  /* Play card game */
  sort(A.begin(), A.end(), greater<int>() );
  
  int Alice=0;
  int Bob=0;
  for(int i=0;i<N;i++){
    if(i%2==0)
      Alice+=A.at(i);
    else
      Bob+=A.at(i);
  }
  
  /* output data */
    cout << Alice-Bob << endl;
}


Measured memory_bytes: 256
// template {{{

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

#define loop(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) loop(i, 0, n)
#define rloop(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); i--)
#define rrep(i, n) rloop(i, 0, n)
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define pf pop_front
#define all(c) std::begin(c), std::end(c)
#define mp std::make_pair
#define mt std::make_tuple
#define fi first
#define se second
#define popcnt __builtin_popcountll

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

template<typename T>
using max_pq = priority_queue<T, vector<T>, less<T>>;

template<typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

const int MOD = 1e9 + 7;
const int INF = 1e9 + 10;
const ll LLINF = 1e18 + 10;

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

template<typename T>
inline T sq(T x){ return x * x; }

template<typename T, typename U>
inline bool chmax(T &x, U y){ if (x >= y) return false; x = y; return true; }

template<typename T, typename U>
inline bool chmin(T &x, U y){ if (x <= y) return false; x = y; return true; }

template<typename T>
inline void sort(T &c){ std::sort(std::begin(c), std::end(c)); }

template<typename T>
inline void reverse(T &c){ std::reverse(std::begin(c), std::end(c)); }

template<typename T>
inline void unique(T &c){ std::sort(std::begin(c), std::end(c)); c.erase(std::unique(all(c)), std::end(c)); }

// }}}

using iter = string::const_iterator;

int pri[256];
function<ll(ll, ll)> op[256];

ll expr(iter &it, int p)
{
	ll res = 0;
	if (p == 3){
		if (*it == '('){
			++it;
			res = expr(it, 0);
			++it;
			return res;
		}
		while (isdigit(*it)){
			res = res * 10 + (*it - '0');
			++it;
		}
		return res;
	}

	res = expr(it, p + 1);
	while (true){
		if (pri[*it] == p){
			char c = *it;
			++it;
			res = (op[c])(res, expr(it, p + 1));
		}
		else break;
	}

	return res;
}

ll eval(const string &s)
{
	iter it = begin(s);
	return expr(it, 0);
}

int main()
{
	op['+'] = [](ll x, ll y){ return x + y; };
	op['-'] = [](ll x, ll y){ return x - y; };
	op['*'] = [](ll x, ll y){ return x * y; };
	memset(pri, -1, sizeof(pri));

	string s;
	cin >> s;

	ll res = LLONG_MIN;
	rep(i, 3) rep(j, 3) rep(k, 3){
		pri['+'] = i;
		pri['-'] = j;
		pri['*'] = k;
		chmax(res, eval(s));
	}

	cout << res << endl;
}

Measured memory_bytes: 3228
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<bitset>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(10);
}
const ll MAX_N = 20;
const ll MAX_V = 55;
const ll INF = 1e10;
vector<vector<ll>> dp(1ll << MAX_N,vector<ll>(MAX_V,INF));
signed main(){
  init_io();
  ll n;
  cin >> n;
  vector<ll> a(n),b(n);
  vector<P> bitlist;
  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  for(int i=0;i<n;i++){
    cin >> b[i];
  }
  for(ll s=0;s<(1ll<<n);s++){
    ll btc = 0;
    for(int j=0;j<n;j++){
      if(s&(1ll<<j)) btc++;
    }
    bitlist.push_back(P(btc,s));
  }
  dp[0][0] = 0;
  sort(bitlist.begin(),bitlist.end());
  for(auto [btc,s]:bitlist){
    for(ll i=0;i<n;i++){
      ll ns = s | (1ll << i);
      ll dist,l_val,now=i;
      if(s == ns) continue;
      for(ll j=i+1;j<n;j++){
        if(s&(1ll<<j)) now++;
      }
      dist = abs(btc-now);
      if(abs(btc-i)%2==0) l_val = a[i];
      else l_val = b[i];
      for(ll last=0;last<=l_val;last++){
        dp[ns][l_val] = min(dp[ns][l_val],dp[s][last]+dist);
      }
    }
  }
  ll ans = INF;
  for(int i=0;i<MAX_V;i++){
    ans = min(dp[(1ll<<n)-1][i],ans);
  }
  if(ans==INF) cout <<-1<<endl;
  else cout << ans << endl;
}


Measured memory_bytes: 490748
from scipy.misc import comb
N=int(input())
A=list(map(int,input().split()))
nset=set([])
ndict={}
for a in A:
  if a in nset:
    ndict[a]+=1
  else:
    nset.add(a)
    ndict[a]=1
#print(nset,ndict)
all=0
for n in nset:
  tmp=ndict[n]
  if tmp>=2:
    all+=comb(tmp,2,exact=True)
all=int(all)
for a in A:
  tmp=ndict[a]
  if tmp==1:
    print(all)
  elif tmp==2:
    print(all-1)
  else:
    print( all-comb(tmp,2,exact=True)+comb(tmp-1,2,exact=True) )

Measured memory_bytes: 36568
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define inf 1000000007
#define Endl endl
#define LINF 100000000000000007LL
#define ll long long
using namespace std;
signed main(){
	int t1,t2,a1,a2,b1,b2;
	cin>>t1>>t2>>a1>>a2>>b1>>b2;
	int s1 = t1 * ( a1 - b1 );
	int s2 = t2 * ( a2 - b2 );
	if( ( s1 > 0 && s2 > 0 ) || (s1 < 0 && s2 <0) || ( abs(s1) > abs(s2) ) ){
		cout<<0<<endl;
		return 0;
	}
	else{
		if( s1 + s2 == 0 ){
			cout<<"infinity"<<endl;
			return 0;
		}
		else{
			int sa = abs( abs(s1) - abs(s2) );
			int mi = min( abs(s1), abs(s2) );
			int sp = mi/sa + 1;
			if( mi % sa == 0 ) sp--;
			int ans = sp*2-1;
			if( mi % sa == 0 ) ans++;
			cout<<ans<<endl;
			return 0;
		}
	}
	return 0;
}

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

A = sorted(A,reverse=True)

ans=0

ans+=A[0]
N-=2
ptr=1

while N>0:
    if N>=2:
        ans+=A[ptr]*2
        N-=2
    else:
        ans+=A[ptr]
        N-=1
    ptr+=1
print(ans)


Measured memory_bytes: 94248
// ABC170-A
#include <bits/stdc++.h>
#define endl "\n"
#define rep(i,n) for(int i=0;i<int(n);i++)
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ipair;
typedef pair<ll,ll> lpair;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v) //vectorの中身を見る
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);

    vector<int> a(6);
    rep(i,5) cin>>a[i+1];
    for(int i=1;i<=5;i++){
        if(a[i]==0) cout<<i<<endl;
    }
    return 0;
}

Measured memory_bytes: 3664
using System.Linq;
using static System.Console;

public static class Program
{
    public static void Main()
    {
        var n = int.Parse(ReadLine());
        var aArray = ReadLine().Split(' ').Select(int.Parse).ToArray();
        int count = 0;
        for(int i = 0; i < n; ++i)
        {
            if ((i + 1) % 2 != 0 && aArray[i] % 2 != 0) ++count;
        }
        WriteLine(count);
    }
}

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

int main(){
  int N,key,j=0;
  int a[100];
  cin >> N;
  for (int i=0;i<N;i++)
    cin >> a[i];

  for(int i=0;i<N;i++){
    key = a[i];
    j = i - 1;
    while(j>=0 && a[j] > key){
      a[j+1] = a[j];
      j--;
    }
    a[j+1] = key;
    for(int k=0;k<N;k++){
      cout << a[k];
      if(k != N-1)cout << " ";
    }
    cout << endl;
  }
    return 0;
}
		

Measured memory_bytes: 1160
#include<bits/stdc++.h>
#define endl enjoy_codeforces
int main(){
    std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);
    int n;std::cin>>n;
    std::vector<int>a(n);
    for(int&x:a)std::cin>>x;
    std::sort(a.begin(),a.end());
    std::cout<<a.at(n/2)-a.at(n/2-1)<<'\n';
}


Measured memory_bytes: 640
#include <stdio.h>
int main(void){
    int i,n,b,r,f,v,j,k;
    int tower[100][100][100];
     
    scanf("%d",&n);
     
    for(i=1;i<=n;i++){
        scanf("%d %d %d %d ",&b,&r,&f,&v);
            
                    tower[b][r][f]+=v;
            
         
    }
     
     
 
 
    for(i=1;i<=4;i++){
        for(j=1;j<=3;j++){
            for(k=1;k<=10;k++){
                if(tower[i][j][k]>=1){
                     
                        printf(" %d",tower[i][j][k]);
                     
                }
                else if(i==4||j==3||k==10){
                    if(tower[i][j][k]>=1){
                        printf(" %d",tower[i][j][k]);
                    }
                    else{
                        printf(" 0");
                    }
                }
                 
                 
                else{
                    printf(" 0");
                }
                 
                 
                 
            }
            printf("\n");
        }
        if(i!=4){
            printf("####################\n");    
        }
    }
     
 
 
}


Measured memory_bytes: 2076
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		int h1 = 0;
		int h2 = 0;
		int h3 = 0;
		Scanner sc = new Scanner(System.in);
		h1 = sc.nextInt();
		h2 = sc.nextInt();
		h3 = sc.nextInt();
		sc.close();
		String strValue = "";
		if (h3 >= h1 && h3 <= h2) {
			strValue = "Yes";
		} else {
			strValue = "No";
		}

		System.out.println(strValue);
	}
}

Measured memory_bytes: 23764
n = int(input())
s = input()

count = 0
for i in range(10):
    p1 = s.find(str(i))
    if p1 == -1:
        continue
    for j in range(10):
        p2 = s.find(str(j), p1 + 1)
        if p2 == -1:
            continue
        for k in range(10):
            p3 = s.find(str(k), p2+1)
            if p3 != -1:
                count += 1

print(count)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b; }
template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b; }
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cout << H << " "; debug_out(T...); }
#ifdef _DEBUG
  #define debug(...) debug_out(__VA_ARGS__)
#else
  #define debug(...) 
#endif

ll gcd (ll x, ll y) { return y ? gcd(y,x%y) : x; }

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  ll s;
  cin >> s;
  ll y = s / 1000000000;
  ll x = s % 1000000000;
  debug(y, x);
  if (y == 1000000000) {
    x = 0;
  }
  else {
    y++;
    x = 1000000000 - x;
  }
  cout << "0 0 1000000000 1 " << x << " " << y << endl;;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	char s[110]="";
	scanf("%s",s+1);
	int n=strlen(s+1),ans=1e9;
	for (char ch='a';ch<='z';ch++){
		int val=0;
		int last=1;
		for (int i=1;i<=n;i++)
		if (s[i]==ch){
			val=max(val,i-last);
			last=i+1;
		}
		if (last<=n) val=max(val,n+1-last);
		ans=min(ans,val);
	}
	printf("%d\n",ans);
	return 0;
}

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

int main(){
    int N, m;
    cin >> N;
    m = 0;
    vector<int> b(N);
    cin >> b[0];
    m += b[0];
    for (int i = 1; i < N - 1; i++){
        cin >> b[i];
        m += min(b[i], b[i-1]);
    }
    cout << m + b[N-2] << endl;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
#define vec(s) vector
;
#define vvec(s) vector<vector
> ;
typedef vector<lli> vi;
typedef vector<vi> vvi;
typedef pair<lli,lli> pii;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define YN(x) cout<<(bool x?"Yes":"No")<<endl;
#define out(s) cout<<s<<endl;
#define pb(s) push_back(s);
#define sp " ";
#define INF 10000000000
#define all(s) s.begin(),s.end()
void vout(vi v){
    for(int i=0;i<v.size();i++)
    cout<<v.at(i)<<endl;
}
int main(){
    lli n,k;
    cin>>n>>k;
    vi ans(n+2,0),cnt(n+2,0),meme(n+2,0);
    rep(i,n) cin>>ans[i+1];
  
    rep(i,min(k,(lli) 41)){  
        swap(ans,cnt);
        ans=meme;
        for(int j=1;j<=n;j++){
            (j-cnt[j]>0?ans[j-cnt[j]]+=1:ans[0]+=1);
            (j+cnt[j]+1<n+1?ans[j+cnt[j]+1]-=1:ans[n+1]-=1);
        }
        for(int j=1;j<=n;j++){
            ans[j]=ans[j]+ans[j-1];
        }

    }
    for(int i=1;i<=n;i++){
        cout<<ans[i];
        if(i!=n) cout<<" ";
        else cout<<endl;
    }
}

Measured memory_bytes: 7968
N = int(input())
W = [int(i) for i in input().split()]
left = [0]
right = [0]
j = 0
 
for i in range(N):
    if j-1 == N-1-i:
        break
    right.append(W[N-1-i])
    while (sum(left) < sum(right)) and (j < N-1-i):
        left.append(W[j])
        j += 1
 
print(abs(sum(left)-sum(right)))

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

signed main() {
  int x; cin >> x;

  // b^p
  int ans = 1;
  // 2^2, 2^3, ... , 3^2, 3^3, ...
  for(int b = 2; b <= x; b++) {
    int powered = b*b;
    while(true) {
      if(powered > x) break;
      ans = max(ans, powered);
      powered *= b;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...)name
#define _rep(i,n)repi(i,0,n)
#define repi(i,a,b)for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T, class U>bool chmax(T& a, U&& b) { return a < b ? a = b, 1 : 0; }
template<class T, class U>bool chmin(T& a, U&& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

int main() {
    ll I, O, T, J, L, S, Z;
    cin >> I >> O >> T >> J >> L >> S >> Z;

    if (!I) {
        write(J / 2 * 2 + L / 2 * 2 + O);
    }
    else if (I && J && L && I % 2 + J % 2 + L % 2 > 1) {
        write(~- I / 2 * 2 + ~- J / 2 * 2 + ~- L / 2 * 2 + O + 3);
    }
    else {
        write(I / 2 * 2 + J / 2 * 2 + L / 2 * 2 + O);
    }
}

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

int main() {
  ll K, A, B;
  cin >> K >> A >> B;
  ll result = 0;
  for (ll i = A; i < B + 1; ++i) {
    if (i % K == 0) {
      result = i;
      break;
    }
  }
  
  if (result == 0) {
    cout << "NG" << endl;
  } else {
    cout << "OK" << endl;
  }
  return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
int main() {
    ll n;
    cin >> n;
    vector<ll>l(n);
    for(ll i=0;i<n;i++){
        cin >> l[i];
    }
    ll ans=0;
    for(ll i=0;i<n;i++){
        for(ll j=i+1;j<n;j++){
            for(ll k=j+1;k<n;k++){
                if(l[i]==l[j]||l[j]==l[k]||l[k]==l[i]) continue;
                if(abs(l[i]-l[j])<l[k]&&l[k]<l[i]+l[j]){
                    ans++;
                }
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3632
n, k = map(int, input().split())
s, p, r = map(int, input().split())
t = input()
pre = "0"
ans = 0

for i in range(k):
    for j in t[i::k]:
        if j != pre:
            pre = j
            if j == "s":
                ans += s
            elif j == "p":
                ans += p
            else:
                ans += r
        else:
            pre = "0"
    pre = "0"
print(ans)

Measured memory_bytes: 3316
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <cstdio>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main() {
  int K, X;
  cin >> K >> X;
  bool flag = false;
  for(int i=X-K+1; i<X+K; i++) {
    if(i >= -1000000 && i<= 1000000) {
      if(flag)
        cout << ' ';
      cout << i;
      flag = true;
    }
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>

#include <algorithm>

using namespace std; 
int gcd(int a,int b){
    if (a%b==0){
        return b;
    }else{
        while(a>0){
            a /=b;
        }
        return gcd(b,a);
    }
}
int main(){
int N;
int M;
cin>>N>>M;
cout<<max(max(N+M,N*M),N-M);
return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int kMaxn = 5e3 + 5;
int N, K;

int main() {
  //
  cin >> K;
  if (K % 7 == 0) K /= 7;
  K *= 9;
  int ans;
  ans = -1;
  for (int i = 1, tmp = 10; i < K; i++, tmp = 10LL * tmp % K)
    if ((tmp - 1) % K == 0) {
      ans = i;
      break;
    }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3192
a, b, c, k = map(int, input().split())
box = []
result = 0

if k <= a:
    print(k)
    quit()
else:
    k = k - a
    result = a
    if k <= b:
        print(result)
        quit()
    else:
        k = k - b
        if k <= c:
            result = result - k
            print(result)
            quit()
        else:
            result = result -c
            print(result)
            quit()

Measured memory_bytes: 9144
def main():
    c = int(input()) // 2
    elem = list(map(int, input().split()))
    right, left = sorted(elem)[c - 1:c + 1]
    for val in elem:
        print(median(val, right, left))


def median(val, right, left):
    if val <= right:
        return left
    else:
        return right


if __name__ == '__main__':
    main()


Measured memory_bytes: 25228
#include <stdio.h>

int main(void) {
	int i,j,x,y,size,field[10][10],siro = 0,Max = 0;
    for(i = 0;i < 10;i++){
        for(j = 0;j < 10;j++) field[i][j] = 0;
    }
    while(scanf("%d,%d,%d",&x,&y,&size) != EOF){
        for(i = -2;i <= 2;i++){
            for(j = -2;j <= 2;j++){
                if(x + i >= 0 && x + i < 10 && y + j >= 0 && y + j < 10){
    if(size == 1){
        if(abs(i) + abs(j) <= 1) field[y + j][x + i]++;
    }
    else if(size == 2){
        if(i > -2 && i < 2 && j > -2 && j < 2) field[y + j][x + i]++; 
    }
    else if(size == 3){
        if(abs(i) + abs(j) <= 2) field[y + j][x + i]++;
    }
}
            }
        }
    }
    for(i = 0;i < 10;i++){
        for(j = 0;j < 10;j++){
           if(!field[i][j]) siro++;
           if(Max < field[i][j]) Max = field[i][j];
        }
    }
    printf("%d\n%d\n",siro,Max);
	return 0;
}

Measured memory_bytes: 600
#include <stdio.h>
using namespace std;
typedef long long ll;

int main(void) {
  ll i, j, n = 2019, now[n], tmp[n], ans = 0;
  char s[200010];
  scanf("%s", s);
  for(i = 0; i < n; ++i) now[i] = 0;
  now[0] = 1;
  for(i = 0; s[i]; ++i) {
    for(j = 0; j < n; ++j) tmp[j] = 0;
    for(j = 0; j < n; ++j) if(now[j]) tmp[(10 * j + s[i] - '0') % n] += now[j];
    ans += tmp[0];
    for(j = 0; j < n; ++j) now[j] = tmp[j];
    now[0]++;
  }
  printf("%lld", ans);
  return 0;
}

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

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
const int mod = 1000000007;

struct mint {
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint &operator-=(const mint a) {
    if ((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint &operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res -= a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1) a *= *this;
    return a;
  }
  mint inv() const { return pow(mod - 2); }
  mint &operator/=(const mint a) { return (*this) *= a.inv(); }
  mint operator/(const mint a) const {
    mint res(*this);
    return res /= a;
  }
  friend ostream &operator<<(ostream &os, const mint &a) {
    os << a.x;
    return os;
  }
  friend istream &operator>>(istream &is, mint &a) {
    is >> a.x;
    return is;
  }
};
struct combination {
  vector<mint> fact, ifact;
  combination(int n) : fact(n + 1), ifact(n + 1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * ifact[k] * ifact[n - k];
  }
};

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];
  sort(a.begin(), a.end());

  mint num = 0;
  combination combi(n);

  for (int i = n - 1; i >= 0; --i) {
    // cout << "max: " << a[i] << " " << combi(i, k - 1) << endl;
    num += combi(i, k - 1) * a[i];
  }
  for (int i = 0; i < n; ++i) {
    // cout << "min: " << a[i] << " " << combi(n - (i + 1), k - 1) << endl;
    num -= combi(n - (i + 1), k - 1) * a[i];
  }

  cout << num << endl;
}


Measured memory_bytes: 2176
n, m = gets.split.map(&:to_i)
abs = []
m.times do
  abs.push gets.split.map(&:to_i)
end
road = Array.new(n, 0)
abs.each do |ab|
  road[ab.first - 1] += 1
  road[ab.last - 1] += 1
end
road.each do |r|
  puts r
end


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

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

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

  int x, a, b;
  cin >> x >> a >> b;

  if (b <= a) {
    cout << "delicious" << endl;
  } else if (b <= a + x) {
    cout << "safe" << endl;
  } else {
    cout << "dangerous" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
n=int(input())
a=[[[0 for _ in range(10)] for _ in range(3)] for _ in range(4)]

for _ in range(n):
    b,f,r,v=map(int,input().split())
    a[b-1][f-1][r-1]+=v

for c in range(4):
    for d in range(3):print('',*a[c][d])
    if c != 3:print('#' *20)

Measured memory_bytes: 7704
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string input, output;
	cin>>input;
	int n=input.length();
	if(input[n-1]=='s') output=input+"es";
	else if(input[n-1]!='s') output=input+"s";
	cout<<output<<endl;
	return 0;
}

Measured memory_bytes: 3628
import java.util.*;
import java.math.*;

class Main{
	public static void main(String[] args){
		Solve s = new Solve();
		s.solve();
	}	
}

class Solve{
	Solve(){}
	
	Scanner in = new Scanner(System.in);

	void solve(){
		int w = in.nextInt(), h = in.nextInt(), n = in.nextInt();
		int ans = 0;
		int x = in.nextInt(), y = in.nextInt();

		for(int i = 0; i < n -1; i++){
			int nx = in.nextInt(), ny = in.nextInt();

			if(x > nx && y > ny){
				int d = Math.min(x - nx, y - ny);
				ans += d;
				x -= d;
				y -= d;
			}
			else if(x < nx && y < ny){
				int d = Math.min(nx - x, ny - y);
				ans += d;
				x += d;
				y += d;
			}

			ans += Math.abs(x - nx) + Math.abs(y - ny);

			x = nx; y = ny;
		}

		System.out.println(ans);
	}
	
}

// while(in.hasNext()){
		// 	int n = in.nextInt();
		// 	if(n == 0) return;
			
		// }

Measured memory_bytes: 32212
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll n,a,b,k,s=0;
    map<ll,ll>mp;
    map<ll,ll>::iterator it;
    vector<ll>v;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b;
        mp[a]+=b;
    }
    for(it=mp.begin();it!=mp.end();it++)
    {
        s+=it->second;
        if(s>=k)
        {
            a=it->first;
            break;
        }
    }
    cout<<a<<endl;

    return 0;
}




Measured memory_bytes: 4224
N, X = map(int, input().split())

size, p_num = [1], [1]
for i in range(1, N + 1):
    size.append(size[i - 1] * 2 + 3)
    p_num.append(p_num[i - 1] * 2 + 1)


def f(n, x):
    if n == 0:
        return 0 if x <= 0 else 1
    elif x <= 1 + size[n - 1]:
        return f(n - 1, x - 1)
    else:
        return p_num[n - 1] + 1 + f(n - 1, x - 2 - size[n - 1])  # x - 1 - size[n - 1] - 1


print(f(N, X))


Measured memory_bytes: 3064
#!python3

import bisect

LI = lambda: list(map(int, input().split()))

# input
N, M, K = LI()
A = LI()
B = LI()


def main():
    sa = [0] * (N + 1)
    for i in range(N):
        sa[i + 1] = sa[i] + A[i]
    sb = [0] * (M + 1)
    for i in range(M):
        sb[i + 1] = sb[i] + B[i]
    ans = 0
    for i in range(N + 1):
        a = sa[i]
        if a > K:
            break
        j = bisect.bisect_right(sb, K - a)
        ans = max(ans, i + j - 1)
    print(ans)


if __name__ == "__main__":
    main()


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

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

using namespace std;
typedef long long ll;
const int MAXN = 200000;

int R[MAXN];

int main() {
	int n;

	cin >> n;
	rep(i, n)cin >> R[i];

	int maxv = -1e9;
	int minv = R[0];
	
	for (int i = 1; i < n; i++) {
		maxv = max(maxv, R[i] - minv);
		minv = min(minv, R[i]);
	}
	cout << maxv << endl;
	return 0;
}


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

using namespace std;

bool three(int a) {

        stringstream ss;
        int i = 0;
        ss << a;
        string str = ss.str(); // "a"

        while(str[i] != '\0') {
                if(str[i] == '3') return true;
                i++;
        }
        return false;

}

int main(int argc, char const *argv[]) {
        int upper;
        cin >> upper;

        for(int i = 1; i <= upper; i++) {
                if(i%3 == 0 || three(i)) cout << ' ' << i;
        }
        cout << '\n';
        return 0;
}



Measured memory_bytes: 3196
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <tuple>
#include <queue>
#include <bitset>
#include <unordered_map>
#include <tuple>
#include <utility>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <sys/time.h>

using namespace std;

void solve(string s){
  long long ans = 0;
  long long a = 0;
  for (int i = 0; i < s.size()-1; i++) {
    if (s[i] == 'A') {
      a++;
    } else if (s[i] == 'B' && s[i+1] == 'C') {
      ans += a;
      i++;
    } else {
      a = 0;
    }
  }
  std::cout << ans << std::endl;
}

int main(){
  string s;
  cin >> s;
  solve(s);
  return 0;
}


Measured memory_bytes: 888
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main(){
	int h,m;
	int n;
	double l,s;
	double mi = 0;
	cin >> n;
	while(n--){
		mi = (1<<21);
		scanf("%d:%d",&h,&m);
		l = m * 0.5 + h * 30.0;
		s = m * 6 ;
		mi = min(mi,fabs(l-s));
		if(l>s)s+=360.0;
		else   l+=360.0;
		mi = min(mi,fabs(l-s));
		
		if(mi<30.0){
			cout << "alert" << endl;
		}else if(mi<90.0){
			cout << "warning" << endl;
		}else{
			cout << "safe" << endl;
		}
	}
}
		

Measured memory_bytes: 0
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Integer n = scanner.nextInt();
        List<Integer> list = new ArrayList<Integer>();
        for(int index = 0; index < n; index++) {
          list.add(scanner.nextInt());
        }
        
        Integer candidate = Collections.max(list);
        int indexOfCandidate = list.indexOf(candidate);
        list.remove(indexOfCandidate);
        
        Integer secondCandidate = Collections.max(list);
        
        for(int index = 0;index < n; index++) {
          if(index == indexOfCandidate) {
            System.out.println(secondCandidate);
          } else {
            System.out.println(candidate);
          }
        }
}
}

Measured memory_bytes: 91572
#include <bits/stdc++.h>
#define rep(i, n) for (int i = (int)(0); i < (int)(n); i++)
#define repp(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using lint     = long long;
const lint MOD = 1e9 + 7;
const lint INF = 1e18;

int main() {
  int n;
  cin >> n;
  if (n == 0) {
    cout << "0" << endl;
    return 0;
  }
  string ret = "";
  while (0 != n) {
    if (n % 2 != 0) {
      n = (n - 1) / (-2);
      ret += "1";
    } else {
      n = n / (-2);
      ret += "0";
    }
  }
  reverse(all(ret));
  cout << ret << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

void _main() {
  int N;
  string A, B, C;
  cin >> N >> A >> B >> C;

  int ans = 0;
  rep(i, 0, N) {
    if (A[i] == B[i] && A[i] == C[i]) {
      continue;
    }
    if (A[i] == B[i] || A[i] == C[i] || B[i] == C[i]) {
      ans++;
      continue;
    }
    ans += 2;
  }

  cout << ans << "\n";
}

Measured memory_bytes: 256