akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) x
#define WATCH(x) TRACE(cout << #x" = " << x << endl)
#define WATCHR(a, b) TRACE(for (auto it=a; it!=b;) cout << *(it++) << " "; cout << endl)
#define WATCHC(V) TRACE({cout << #V" = "; WATCHR(V.begin(), V.end());})

#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

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

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

    cout << (1 << M) * (100 * (N - M) + 1900 * M) << endl;

    return 0;
}



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

#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(x) x.begin(), x.end()

using namespace std;

int main(){
  int N; cin >> N;
  cout << (N*800)-(N/15*200) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

double power( double a, int n )
{
  double r;
  int abs_n;

  r = 1; abs_n = n < 0 ? -n : n;
  while ( abs_n > 0 ) {
    if ( abs_n % 2 == 1 ) { r *= a; }
    a *= a;
    abs_n /= 2;
  }

  return n >= 0 ? r : 1/r;
}

double nthroot( double a, int n )
{
  double x, y;

  if ( a <= 0 || n < 0 ) { return 0; }
  if ( n == 0 ) { return 1; }

  /* a > 0 かつ n > 0 の場合 */
  y = (a > 1) ? a : 1;
  do {
    x = y;
    y = ((n-1)*x + a/power(x, n-1)) / n;
  } while ( y < x );

  return y;
}

int is_power( int a )
{
  int i; 

  if ( a == 1 ) { return 1; }

  for ( i = 2; i <= floor(log2(a)); i++ ) {
    if ( power(floor(nthroot(a, i)), i) == a ) { 
      return 1;
    }
  }

  return 0;
}
int main()
{
  int x;
  cin >> x;
  while(!is_power(x)){	
	x--;
  }
  cout << x << endl;

  return 0;
}

Measured memory_bytes: 256
N,M = map(int,input().split())
A = [0]*N
B = [0]*N
C = [0]*M
D = [0]*M
result = [0]*N
for i in range(N):
	A[i],B[i] = map(int,input().split())
for i in range(M):
	C[i],D[i] = map(int,input().split())
for i in range(N):
	Cnt = 0
	Dist = float('inf')
	x = A[i]
	y = B[i]
	for j in range(M):
		if abs(x-C[j])+abs(y-D[j]) < Dist:
			#print(i,j,Dist)
			Dist = abs(x-C[j])+abs(y-D[j])
			Cnt = j+1
	result[i]=Cnt

for i in range(N):
	print(result[i])

Measured memory_bytes: 3064
#include <bits/stdc++.h>
    #define gcd __gcd
    using namespace std;
    typedef long long ll;
     
    int prime(ll x) {
      for (ll i = 2; i * i <= x; i++) if (x % i == 0) return false;
      return true;
    }
     
    int main() {
      ll a, b;
      cin >> a >> b;
      a = gcd(a, b);
      set<ll> s;
      for (ll i = 1; i * i <= a; i++)
        if (a % i == 0)
          s.insert(i), s.insert(a / i);
      ll ans = 0;
      for (ll c : s) if (c == 1 || prime(c)) ans++;
      cout << ans << endl;
    }

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define lint long long
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define MP make_pair
#define to_stirng to_string
using namespace std;

// cout << fixed << setprecision(12)

int main(){
  lint X,Y;
  cin >> X >> Y;
  
  bool OK = true;
  
  if(Y%2==1) OK = false;
  if(Y < 2*X) OK = false;
  if(Y > 4*X) OK = false;
  
  if(OK) cout << "Yes" << endl;
  else cout << "No" << endl;
}
  
  


Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
int n,i,maxx,minn=1111111111;
int main()
{
    cin>>n;
    while(n--)
    {
        cin>>i;
        if(minn>i)
            minn=i;
        if(maxx<i)
            maxx=i;
    }
    cout<<maxx-minn;
}


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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

const int MAX = 1510000;
long long fac[MAX], finv[MAX], inv[MAX];
bool initialized = false;

/**
 * @fn
 * This function must be called at first.
 */
void combination_init() {
    initialized = true;
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

/**
 * @fn
 * Calculates the combination  ( nCK % p: N choose K mod p).
 *
 * @brief constraint: 1 ≤ k ≤ n ≤ 10^7
 * @return nCK % MOD
 */
long long combination(int n, int k) {
    assert(initialized);
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

/**
 * @fn
 * Calculates the factorial of the number.
 *
 * @return N! % MOD
 */
long long factorial(int n) {
    assert(initialized);
    if (n < 0) return 0;
    return fac[n] % MOD;
}

/**
 * @fn
 * Calculates the combination ( nCK % p: N choose K mod p).
 *
 * @brief constraint: 1 ≤ k ≤ 10^7 and 1 ≤ n ≤ 10^9
 * @return nCK % MOD
 */
long long combination2(int n, int k) {
    assert(initialized);
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    ll res = 1;
    k = min(k, n - k);
    for (long long x = 1; x <= k; x++) {
        res *= (n - x + 1);
        res %= MOD;
        res *= inv[x];
        res %= MOD;
    }
    return res;
}


void solve() {
    ll X, Y;
    cin >> X >> Y;
    combination_init();
    if (2 * X - Y >= 0 && 2 * Y - X >= 0 && (2 * X - Y) % 3 == 0 && (2 * Y - X) % 3 == 0) {
        cout << combination((X + Y) / 3, (X * 2 - Y) / 3) << '\n';
    } else {
        cout << 0 << '\n';
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}


Measured memory_bytes: 35712
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
#define NIL -2000000001
#define MAX 2000000

int abs (int a) {
  if (a>0) {
    return a;
  } else {
    return -a;
  }
}

int main() {
  int a,b,c;
  scanf("%d %d %d", &a, &b, &c);

  int min=MAX;
  if (abs(a-b)+abs(b-c)<min) min = abs(a-b)+abs(b-c);
  if (abs(a-c)+abs(c-b)<min) min = abs(a-c)+abs(c-b);
  if (abs(b-a)+abs(a-c)<min) min = abs(b-a)+abs(a-c);
  if (abs(b-c)+abs(c-a)<min) min = abs(b-c)+abs(c-a);
  if (abs(c-a)+abs(a-b)<min) min = abs(c-a)+abs(a-b);
  if (abs(c-b)+abs(b-a)<min) min = abs(c-b)+abs(b-a);

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

  return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"io"
	"math/big"
	"strconv"
)

func main() {
	//sc := NewBufScanner(os.Stdin)
	//n := int(sc.Int())
	var n int
	fmt.Scan(&n)
	sum := big.NewInt(1)

	upper := big.NewInt(1e18)
	as := make([]int64, n)
	for i := 0; i < n; i++ {
		// as[i] = sc.Int()
		fmt.Scan(&as[i])
		if as[i]== 0 {
			fmt.Println(0)
			return
		}
	}
	for i, v := range  as {
		if i == 0 {
			sum = big.NewInt(v)
			continue
		}
		sum.Mul(sum, big.NewInt(v))
		if sum.Cmp(upper) >0 {
			fmt.Println("-1")
			return
		}
	}
	fmt.Println(sum.Int64())
}

type BufScanner struct {
	*bufio.Scanner
}

func NewBufScanner(r io.Reader) *BufScanner {
	s := bufio.NewScanner(r)
	s.Split(bufio.ScanWords)
	// s.Split(scanWords)
	return &BufScanner{s}
}

func scanWords(data []byte, atEOF bool) (advance int, token []byte, err error) {
	start := 0
	for isSpace(data[start]) {
		start++
	}
	for i := start; i < len(data); i++ {
		if isSpace(data[i]) {
			return i+1, data[start:i], nil
		}
	}
	if atEOF && len(data) > start {
		return len(data), data[start:], nil
	}
	return start, nil, nil
}
func isSpace(b byte) bool {
	return b == ' ' || b == '\n' || b == '\r' || b == '\t'
}

func (s *BufScanner) String() string {
	s.Scan()
	return s.Text()
}

func (s *BufScanner) Int() int64 {
	return int64(s.UInt())
}


func (s *BufScanner) UInt() uint64 {
	s.Scan()
	i, e := strconv.ParseUint(s.Text(), 10, 64)
	if e != nil {
		panic(e)
	}
	return i
}


Measured memory_bytes: 6452
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <random>
using namespace std;

#define endl '\n'
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef complex<double> comp;
typedef vector< vector<ld> > matrix;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const int inf = 1e9 + 9;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);

int n, k, l;
int p[100010], q[100010];
int r[100010], s[100010];

class UnionFind {
private:
    static const int MAX = 200010;
    int par[MAX];
    int r[MAX];
public:
    UnionFind(int n = MAX) {
	for (int i = 0; i < n; i++) {
	    par[i] = i;
	    r[i] = 0;
	}
    }

    int find(int x) {
	if (par[x] == x) {
	    return x;
	} else {
	    return par[x] = find(par[x]);
	}
    }

    void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return;
	if (r[x] < r[y]) {
	    par[x] = y;
	} else {
	    par[y] = x;
	    if (r[x] == r[y]) r[x]++;
	}
    }

    bool same(int x, int y) {
	return find(x) == find(y);
    }
};

void solve() {
    UnionFind uf[2];
    for (int i = 0; i < k; i++) {
        uf[0].unite(p[i], q[i]);
    }
    for (int i = 0; i < l; i++) {
        uf[1].unite(r[i], s[i]);
    }

    P label[200010];
    unordered_map<P, int, pairhash> mp;
    for (int i = 0; i < n; i++) {
        P v = P(uf[0].find(i), uf[1].find(i));
        label[i] = v;
        mp[v]++;
    }
    for (int i = 0; i < n; i++) {
        cout << mp[label[i]] << (i==n-1?endl:' ');
    }
}

void input() {
    cin >> n >> k >> l;
    for (int i = 0; i < k; i++) {
        cin >> p[i] >> q[i];
        p[i]--; q[i]--;
    }
    for (int i = 0; i < l; i++) {
        cin >> r[i] >> s[i];
        r[i]--; s[i]--;
    }
}

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

    input();
    solve();
}

Measured memory_bytes: 17480
#include <stdio.h>

int main(void)
{
	int a, b, c;
	int keta;
	while (scanf("%d %d", &a, &b) != EOF){
		c = a + b;
		keta = 0;
		while (c != 0){
			c /= 10;
			keta++;
		}
		printf("%d\n", keta);
	}
	return (0);
}

Measured memory_bytes: 1784
import std.stdio, std.algorithm, std.string, std.conv, std.array;

void main()
{
    auto input = stdin.byLine().map!(line => line.split(",").map!(to!int).array).array;
    input.count!q{ a[0] ^^ 2 + a[1] ^^ 2 == a[2] ^^ 2}.writeln;
    input.count!q{ a[0] ==  a[1]}.writeln;
}

Measured memory_bytes: 1072
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mod = 1e9+7;

//ユークリッドの互除法
ll gcd(ll x,ll y){
    if(x > y) swap(x,y);
    if(x == 0) return y;
    return gcd(x,y%x);
};

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i= 0; i < n; i++){
        cin >> a[i];
    }
    int ans;
    ans = gcd(a[0],a[1]);
    for(int i = 2; i < n; i++){
        ans = gcd(ans,a[i]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
int main(void)
{
	int H=1,W=1,i,j,n;

	while(H!=0&&W!=0)
	{
	 
		scanf("%d %d",&H,&W);
		
		if(H!=0&&W!=0)
	    {
		
		   
	
			for(n=0;W>n;n++)
			{
				printf("#");
			}

			printf("\n");
		
			for(i=0;i<H-2;i++)
			{
				printf("#");
			
				for(j=0;j<n-2;j++)
				{
					printf(".");
				}
			
				printf("#");
			printf("\n");
			}


			for(n=0;W>n;n++)
			{
				printf("#");
			}
			printf("\n");
		printf("\n");
	  
	  }
	
			
		else
		{
		}
	}



	return 0;
}

Measured memory_bytes: 572
#include<iostream>

#define MAX(a,b) (a>b? a:b)
#define MIN(a,b) (a>b? b:a)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define lint long int

using namespace std;

lint GCD(lint a, lint b, lint &x, lint &y){
	if(b==0) {
		x=1;
		y=0;
		return a;
	}
	lint q=a/b;
	lint g=GCD(b,a-q*b,x,y);
	lint z=x-q*y;
	x=y;
	y=z;
	return g;
}

int main(){
	lint N;
    cin >> N;
    lint *A = new lint[N];
    rep(i,N) cin >> A[i];
    lint g = A[0], x, y;
    rep(i,N-1) g = GCD(g,A[i+1],x,y);
    cout << g << endl;
	return 0;
}


Measured memory_bytes: 1024
import sys

def comb(n, k):
    if k == 0:
        return 0
    if n < k:
        return 0
    res=1
    for i in range(n - k + 1, n + 1):
        res *= i
    for i in range(1,k + 1):
        res //= i
    return res

n=input()
k = int(input())
l = len(n)

top = int(n[0])

if l == 1:
    if k >= 2:
        print(0)
        sys.exit()
    print(top)
    sys.exit()

if k == 1:
    z = 9
elif k == 2:
    z = 81
else:
    z = 729

ans = comb(l - 1, k) * z
ans += comb(l - 1, k - 1) * (top - 1) * (z // 9)

if k == 1:
    ans+=top
elif k == 2:
    for i in range(1, l):
        if i==1 or int(n[1:i]) == 0:
            ans += int(n[i])
        else:
            ans += 9
elif k == 3:
    for i in range(1, l):
        for j in range(i + 1, l):
            flag1 = i == 1 or int(n[1:i]) == 0
            flag2 = j == i + 1 or int(n[i + 1 :j]) == 0
            if not(flag1) and not(flag2):
                ans += 81
            elif flag1 and not (flag2):
                ans += 9 * int(n[i])
            elif not (flag1) and flag2:
                ans += 81
            else:
                if int(n[i]) == 0:
                    continue
                ans += 9 * (int(n[i]) - 1) + int(n[j])

print(ans)


Measured memory_bytes: 3064
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include<math.h>
using namespace std;
#define INF 110000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,int> P;

int D,G,p[11],c[11];

int main(){
  cin>>D>>G;

  for(int i=0;i<D;i++){
    cin>>p[i]>>c[i];
  }

  int ans=1e9;

  for(int bit=0;bit< (1<<D); bit++){
    int s=0,num=0,rest_max=-1;
    for(int i=0;i<D;i++){
      if(bit>>i & 1){
        s+=100*(i+1)*p[i]+c[i];
        num+=p[i];
      }else{
        rest_max=i;
      }
    }
    if(s<G){
      int s1=100*(rest_max+1);
      int need=(G-s+s1-1)/s1;
      if(need>=p[rest_max]) continue;
      else{
        num+=need;
        
      }
    }
    ans=min(ans,num);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(100000000)
A,B,C,D,E,F = [int(x) for x in input().split()]

x = []
y = []
ans_max = 0
ans = [0,0]

for i in range(F//(100*A)+1):
    for j in range((F-100*A*i)//(100*B)+1):
        water = 100*(A*i+B*j)
        if(water<=F and not water in x and water!=0):
            x.append(water)

ans[0]=x[0]

for i in range(F):
    for j in range(F):
        salt = C*i+D*j
        if(salt<=F and not salt in y):
            y.append(salt)

for i in x:
    for j in y:
        if(i==0):
            continue
        elif(100*j <= i*E and i+j <= F):
            percent = 100*j/(i+j)
            if(ans_max < percent):
                ans_max = percent
                ans = [i,j]

print(sum(ans),ans[1])


Measured memory_bytes: 3064
n = int(input())
a = sorted([list(map(int, input().split())) for _ in range(n)])
d = {}
ret = float('inf')
for i in range(n - 1):
    for j in range(i + 1, n):
        p, q = a[j][0] - a[i][0], a[j][1] - a[i][1]
        if p == 0 and q == 0:
            continue
        key = (p, q)
        d.setdefault(key, 0)
        d[key] += 1
print(n - (max(d.values()) if d  else 0))


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

using namespace std;

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

#define REP(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

ll a, b, c;
ll N, M;

void solve() {
    cin >> N >> M;
    ll A[N];
    rep(i, N) cin >> A[i];
    ll sum[N+1] = {};
    rep(i, N) {
        sum[i+1] = sum[i] + A[i];
        sum[i+1] %= M;
    }
    map<ll, ll> mp;
    rep(i, N+1) {
        mp[sum[i]]++;
    }
    ll ans = 0;
    for (auto v : mp) {
        ans += v.second * (v.second-1) / 2;
    }
    cout << ans << endl;
}

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


Measured memory_bytes: 5760
#include <iostream>
#include <vector>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<deque>
#include<map>
#include<bitset>
#include<math.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
typedef long long ll;
typedef pair<int,int> pint;
const ll mod= 1e9+7;
const int inf=1e9+7;
const ll  longinf = 1LL<<60;
int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};


int main(){
  int a,b;
  cin>>a;
  if(a>=1000)cout<<"ABD"<<endl;
  else cout<<"ABC"<<endl;
  return 0;
  }


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define mrep(i,j,n) for(int i = j; i < n; i++)
#define reps(i,n) for(int i = 1; i <= n; i++)
#define rrep(i,n) for(int i = n-1; i >= 0; i--)
#define rreps(i,n) for(int i = n; i >= 1; i--)
#define co(x) cout << x <<endl
#define cs(x) cout << x <<" "
#define el cout<<endl
#define cer(x) cerr << x <<endl
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ERASE(x,val) x.erase(remove(ALL(x), val), x.end())
#define vi vector<int> 
#define vvi vector<vector<int>> 
#define vpii vector<pair<int,int>> 
#define vl vector<ll> 
#define vvl vector<vector<ll>> 
#define vb vector<bool> 
#define vvb vector<vector<bool>>
#define vs vector<string> 
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll mod = 1e9 + 7;
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; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a * b / g; }
bool is_prime(ll x) { for (ll i = 2; i * i <= x; i++) { if (x % i == 0)return false; } return true; }

ll mod_pow(ll a, ll p)
{
	if (p == 0)return 1;
	else if (p == 1)return a;
	else if (p % 2 == 0)
	{
		ll h = mod_pow(a, p / 2);
		return h * h % mod;
	}
	else return (mod_pow(a, p - 1) * a) % mod;
}

vl fact;
vl fact_inv;

int main()
{
	int n, k; cin >> n >> k;
	vl a(n);
	fact.resize(n + 1);
	fact_inv.resize(n + 1);
	rep(i, n+1)
	{
		fact[i] = i <= 1 ? 1 : (fact[i - 1] * i) % mod;
		//fact_inv[i] = mod_pow(fact[i], mod - 2) % mod;
		fact_inv[i] = i<=1 ? 1 : fact_inv[i-1] * mod_pow(i, mod - 2) % mod;
	}
	//reps(i, n)cs(fact[i]); el;
	//reps(i, n)cs(fact_inv[i]); return 0;
	rep(i, n)cin >> a[i];
	sort(all(a));
	
	ll ans = 0;
	for (int i = k - 1; i < n; i++)
	{
		ll comb = ((fact[i] * fact_inv[i - k + 1] % mod) * fact_inv[k - 1]) % mod;
		ll tmp = a[i] * comb % mod;
		ans += tmp;
      	cer(a[i] << " "<<tmp<<" "<<fact[i]<<" "<<fact_inv[i-k+1]<<" "<<fact_inv[k-1]);
		ans %= mod;
	}
	cer("");
	for (int i = 0; i+k-1 < n; i++)
	{
		ll comb = ((fact[n-i-1] * fact_inv[n-i-k] % mod) * fact_inv[k - 1]) % mod;
		ll tmp = a[i] * comb % mod;
		ans -= tmp;
      	cer(tmp);
		ans = (ans + mod) % mod;
	}
	co(ans);
	return 0;
}


Measured memory_bytes: 2560
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

int main(){
  int N,M;
  cin >> N >> M;
  vector<int> s; //1とNからいける島
  for(int i=0;i<M;i++){
    int a,b;
    cin >> a >> b;
    if(a == 1) s.push_back(b);
    if(b == N) s.push_back(a);
  }

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

  for(int i=1;i<s.size();i++){
    if(s[i] == s[i-1]){
      cout << "POSSIBLE" << endl;
      return 0;
    }
  }

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


Measured memory_bytes: 1400
fun main(){
    val n = readLine()!!.split(" ")[0].toInt()
    val count = MutableList(n + 1){ 0 }
    for (x in 1 until 100){
        for (y in 1 until 100){
            for (z in 1 until 100){
                val ans = x * x + y * y + z * z + x * y + y * z + z * x
                if (ans <= n){
                    count[ans]++
                }
            }
        }
    }
    for (i in 0 until n){
        println(count[i + 1])
    }
}

Measured memory_bytes: 39704
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>
#include <set>
#include <ctime>
#include <tuple>
#include <bitset>
#include <assert.h>
#include <deque>
#include <functional>
using namespace std;
typedef long long ll;

#define fi first
#define se second
#define rep(i, n) for (ll i = 0; i < n; i++)
#define debugA cerr << "AAAAA" << endl
#define debug_ cerr << "-------------" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define debug_vec(v)                   \
    cout << #v << endl;                \
    for (int i = 0; i < v.size(); i++) \
    {                                  \
        cout << v[i] << " ";           \
    }                                  \
    cout << endl;
#define debug_vec2(v)                         \
    cout << #v << endl;                       \
    for (int i = 0; i < v.size(); i++)        \
    {                                         \
        for (int j = 0; j < v[i].size(); j++) \
        {                                     \
            cout << v[i][j] << " ";           \
        }                                     \
        cout << endl;                         \
    }

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

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

template <typename T>
void quit(T a)
{
    cout << a << endl;
    exit(0);
}

using Graph = vector<vector<int>>;
using P = pair<int, int>;
using P1 = pair<int, pair<int, int>>; // クラスカル法とかで、{cost, {from, to}}的に使う。
const ll LINF = 10010020030040056ll;
const int INF = 1001001001;
const double pi = acos(-1);

int main()
{
    ll n;
    cin >> n;
    // debugA;
    ll ans = LINF;
    for (ll i = 1; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            ans = min(ans, i + n / i - 2);
        }
    }
    // debugA;
    if (ans == LINF)
    {
        cout << n - 1 << endl;
    }
    else
    {
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 3564
let read_lines () =
  let rec iter xs =
    try read_line() :: xs |> iter
    with End_of_file -> xs
  in iter [] |> List.rev

let split_ints str =
  Str.split (Str.regexp " ") str
  |> List.map int_of_string

let println_int i =
  print_int i;
  print_newline ()

let rec digit_length n =
  if n >= 10 then
    1 + digit_length (n / 10)
  else 1
                
let () = read_lines()
         |> List.map split_ints
         |> List.map (List.fold_left (+) 0)
         |> List.map digit_length
         |> List.iter println_int

Measured memory_bytes: 2388
/*
	queue?????¨MLE???
 */

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <queue>
#include <set>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <bitset>
#include <climits>
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define RFOR(i,a,b) for (int i=(a)-1;i>=(b);i--)
#define ll long long
#define ull unsigned long long
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int INF = 1e9;
const int MOD = 1e9 + 7;
 
using namespace std;
int k;
double r,l,t,e,p;
double solve(int tk,double tr,double tl){
	double h = (tr+tl)/2;
	tk--;
	if(tk==-1)
		if(h >= t-e && h <= t+e)return 1;
		else return 0;
	if(tr<=t-e&&tl <=t-e||tr>=t+e&&tl>=t+e)return 0;
	if(t-e<=tr&&tl<=t+e)return 1;
	double tmp_p = t <= h ? p : 1-p;
	double res = tmp_p*solve(tk,h,tl);
	res+=(1-tmp_p)*solve(tk,tr,h);
	return res;
} 
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
	cin>>k>>r>>l>>p>>e>>t;
	cout.precision(10);
	cout << fixed << 	solve(k,r,l) << endl;
  return 0;
}

Measured memory_bytes: 3280
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint,time,random
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def cal(T):
    res = 0
    last = [0] * 26
    for day in range(D):
        t = T[day]; t -= 1
        last[t] = 0
        res += s[day][t]
        for i in range(26):
            if i == t: continue
            last[i] += 1
            res -= c[i] * last[i]
    return res
def check_change(td,tq):
    global score,res
    old_q = res[td]
    res[td] = tq
    now = cal(res)
    if now > score:
        score = now
    else:
        res[td] = old_q
def out():
    global res
    for x in res:
        print(x)
    quit()

start_time = time.time()
n = 26
D = inp()
c = inpl()
s = []
max_s = []
for i in range(D):
    tmp = inpl()
    mx = 0; ind = -1
    for j in range(n):
        if tmp[j] > mx:
            mx = tmp[j]
            ind = j
    max_s.append(ind+1)
    s.append(tmp)

last = [0] * n
res = [-1] * D
for d in range(D):
    ans = -1
    mx = -INF
    for i in range(n):
        now = s[d][i]
        for j in range(n):
            if i == j: continue
            now -= s[d][j] * (last[j]+1)
        if now > mx:
            mx = now
            ans = i
    res[d] = ans+1
    for j in range(n):
        last[j] += 1
        if j == ans: last[j] = 0
score = cal(res)
# print(now_score)

while True:
    if time.time() - start_time > 1.3: break
    td,tq = random.randrange(0,D), random.randrange(1,n+1)
    check_change(td,tq)

for x in itertools.combinations(range(D), 2):
    if time.time() - start_time > 1.83: out()
    old = []
    if sum(x^y for x,y in zip(res,max_s)) == 0: continue
    for i in range(2):
        old.append(res[x[i]])
        res[x[i]] = max_s[x[i]]
    now = cal(res)
    if now > score:
        score = now
    else:
        for i in range(2):
            res[x[i]] = old[i]


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

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ii=pair<int,int>;

const int mxN = 505;
int N, g[mxN][mxN], e[mxN][mxN];
int dy[] = {-1,0,1,0};
int dx[] = {0,1,0,-1};

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

    cin >> N;
    FOR(i,1,N){
        FOR(j,1,N){
            g[i][j] = min(min(i,N-i+1), min(j,N-j+1));
            e[i][j] = 1;
        }
    }
    int ans = 0;
    FOR(i,1,N*N){
        int P; cin >> P;
        int x = (P-1)/N + 1, y = P - (x-1)*N;
        //TRACE(P _ x _ y _ g[x][y]-1);
        ans += g[x][y]-1;

        queue<ii> qu;
        g[x][y] -= 1;
        e[x][y] = 0;
        qu.emplace(x,y);
        while (!qu.empty()) {
            ii xy = qu.front(); qu.pop();
            int x = xy.first, y = xy.second;
            FOR(k,0,3){
                int p = x+dx[k], q = y+dy[k];
                if (p >= 1 && p <= N && q >= 1 && q <= N && g[x][y]+e[p][q] < g[p][q]) {
                    g[p][q] = g[x][y]+e[p][q];
                    qu.emplace(p,q);
                }
            }
        }
    }
    cout << ans;
}



Measured memory_bytes: 5592
n = int(input())
a = list(map(int, input().split()))
b = [0] * n

for i in reversed(range(1, n+1)):
    count = 0
    for j in range(2, n+1):
        if i * j > n:
            break
        count += b[i*j-1]
    if count % 2 == a[i-1]:
        b[i-1] = 0
    else:
        b[i-1] = 1

ans = 0
box = []
for i in range(n):
    if b[i]:
        ans += 1
        box.append(i+1)

print(ans)
print(*box)

Measured memory_bytes: 70364
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,n,s) for(int i = s; i < (n); ++i)
#define rsrep(i,n,s) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<x<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define out_ary(...) { for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef vector<int> vint;
typedef vector<float> vfloat;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vstr> vvstr;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;

double mx_con;

double calc(int A, int B) {
    if (B == 0) return 0.0;
    double con = 1.0 * B / A;
    if (con <= mx_con) return con;
    else return -1.0;
}

int main() {
    int a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;
    double mx = -1;
    a *= 100;
    b *= 100;
    mx_con = e / (e + 100.0);
    set<int> w, s;
    int sum;
    rep(i, f+1) {
        rep(j, f+1) {
            sum = a * i + b * j;
            if (sum <= f) w.insert(sum);
            sum = c * i + d * j;
            if (sum <= f) s.insert(sum);
        }
    }
    w.erase(0);
    int WS = *w.begin(), S = 0;

    for (auto wi : w) {
        for (auto si : s) {
            int ws = wi + si;
            if (ws > f) continue;
            double con = calc(ws, si);
            if (con > mx) {
                mx = con;
                WS = ws;
                S = si;
            }
        }
    }
    cout << WS << " " << S << endl;
    return 0;
}

Measured memory_bytes: 384
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#define REP(i, n) for (int i = 0; i < (n); i++)

using namespace std;
typedef pair<long long, long> P;

long N, M;

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

  vector<P> AB(N);

  REP(i, N) {
    int a, b;
    cin >> a >> b;
    AB[i] = make_pair(a, b);
  }

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

  long long ans = 0;
  long collected = 0;
  REP(i, N) {
    if (collected == M) break;
    ans += min(AB[i].second, M - collected) * AB[i].first;
    collected += min(AB[i].second, M - collected);
  }

  cout << ans << '\n';
}

Measured memory_bytes: 1792
def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    ans = 0
    for i in range(n):
        if a[i] == 0:
            continue
        ans += a[i]//2
        if i != n-1 and a[i]&1 and a[i+1] != 0:
            ans += 1
            a[i+1] -= 1
    print(ans)
if __name__ == "__main__":
    main()

Measured memory_bytes: 50264
#include <algorithm>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 1> { using type = vector<T>; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
/* clang-format on */

int main() {
  int R;
  while (cin >> R) {
    if (R < 1200) {
      cout << "ABC" << endl;
    } else if (R < 2800) {
      cout << "ARC" << endl;
    } else {
      cout << "AGC" << endl;
    }
  }
  return 0;
}


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

const ll mod = 1e9 + 7;
const int MAX_NODE = 1e5 + 5;

vector<int> g[MAX_NODE];

ll dfs(int cur, int par, int k) {
  ll ret = 1;
  ll can_k = ( par != 0 ) ? k-2 : k-1;

  for ( int i = 0; i < g[cur].size(); i++ ) {
    if ( g[cur][i] == par ) { continue; }
    ret = ret * can_k-- % mod;
  }
  for ( int i = 0; i < g[cur].size(); i++ ) {
    if ( g[cur][i] == par ) { continue; }
    ret = ret * dfs(g[cur][i], cur, k) % mod;
  }

  return ret;
}

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

  for ( int i = 0; i < n-1; i++ ) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  ll ans = k * dfs(1, 0, k) % mod;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 13580
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>

using namespace std;

int main() {
	string s;

	cin >> s;

	bool hasN = s.find('N') != string::npos;
	bool hasE = s.find('E') != string::npos;
	bool hasW = s.find('W') != string::npos;
	bool hasS = s.find('S') != string::npos;

	bool ans = (hasN == hasS) && (hasE == hasW);
	cout << (ans ? "Yes" : "No") << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<long long,long long>
#define mod 1000000007
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);

ll power(ll a,ll b){
	ll ans=1;
	while(b>0){
		if(b%2!=0){
			ans=(ans*a)%mod;
		}
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}

int main() {
	IOS;
	int t=1;
	//cin>>t;
	while(t--){
		int a,b;
		cin>>a>>b;
		if(b==1){
			cout<<0;
			return 0;
		}
		for(int i=1;i<100;i++){
			if((a-1)*(i-1)+a>=b){
				cout<<i;
				return 0;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
//freopen("input.txt","r",stdin);
int a,b,c,d,e;
cin>>a>>b>>c>>d>>e;
a=a*60+b;
c=c*60+d;
cout<<c-a-e<<endl;



}


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

#define NEW(p,n){p=malloc((n)*sizeof(p[0]));if(p==NULL){printf("not enough memory\n");exit(1);};}
//pの型の変数n個の要素分のメモリを確保し、そのアドレスをpに代入するマクロ

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

int comp(const void* a, const void* b){
    if (*(long*)a > *(long*)b) return -1;
	if (*(long*)a < *(long*)b) return 1;
	return 0;
}

int main(void){
    int X,Y,Z,K;
    scanf("%d%d%d%d",&X,&Y,&Z,&K);

    //A[0]~A[X-1]に格納する→降順ソート
    long A[1000];
    for(int i=0;i<X;i++){
        scanf("%ld",&A[i]);
    }
    qsort(A,X,sizeof(long),comp);
    //B[0]~B[Y-1]に格納する→降順ソート
    long B[1000];
    for(int i=0;i<Y;i++){
        scanf("%ld",&B[i]);
    }
    qsort(B,Y,sizeof(long),comp);
    //C[0]~C[Z-1]に格納する→降順ソート
    long C[1000];
    for(int i=0;i<Z;i++){
        scanf("%ld",&C[i]);
    }
    qsort(C,Z,sizeof(long),comp);

    long AB[1000000];
    int ab=0;
    for(int i=0;i<X;i++){
        for(int j=0;j<Y;j++){
            AB[ab]=A[i]+B[j];
            ab++;
        }
    }
    qsort(AB,ab,sizeof(long),comp);

    long ans[3000000];
    int count=0;
    for(int i=0;i<Z;i++){
        for(int j=0;j<K && j<ab;j++){
            ans[count]=C[i]+AB[j];
            count++;
        }
    }
    qsort(ans,count,sizeof(long),comp);

    for(int i=0;i<K;i++){
        printf("%ld\n",ans[i]);
    }

    return 0;
}

//確実に上位K位に入らないものを取り除くという考え方
//なぜかWAしかでない

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

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//const value
//const ll MOD = 1e9 + 7;
//const int dx[] = {0,1,0,-1};//{0,0,1,1,1,-1,-1,-1};
//const int dy[] = {1,0,-1,0};//{1,-1,0,1,-1,0,1,-1};

//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

int n, m, s, g[2];
ll dist[100][100];
const ll INF = 1e15;
void solve(){
  rep(k,n){
    rep(i,n){
      rep(j,n){
        dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j]);
      }
    }
  }
  ll ans = INF;
  rep(mid,n){
    ans = min(dist[s][mid] + dist[mid][g[0]] + dist[mid][g[1]], ans);
  }
  cout << ans << endl;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  while(true){
    cin >> n >> m >> s >> g[0] >> g[1];
    if(n == 0 && m == 0 && s == 0 && g[0] == 0 && g[1] == 0) break;
    s--, g[0]--, g[1]--;
    rep(i,100)rep(j,100) dist[i][j] = INF;
    rep(i,n) dist[i][i] = 0;
    rep(i,m){
      int a,b,c;
      cin >> a >> b >> c;
      a--, b--;
      dist[a][b] = c;
    }
    solve();
  }
  return 0;
}



Measured memory_bytes: 3116
use std::io::*;
use std::cmp;

fn read<T: std::str::FromStr>() -> T {
    let stdin = stdin();
    let mut buf = String::new();
	stdin.lock().read_line(&mut buf);
	buf.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
	read::<String>().trim().split_whitespace()
        .map(|w| w.parse().ok().unwrap()).collect()
}

fn read_mat<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn main() {
    let v = read_vec::<usize>();
    let (n,k) = (v[0],v[1]);
    let mut map: Vec<Vec<i64>> = vec![vec![0;2*k];k];
    for i in 0..n {
        let s = read::<String>();
        let w: Vec<&str> = s.trim().split_whitespace().collect();
        let x: usize = w[0].parse().ok().unwrap();
        let y: usize = w[1].parse().ok().unwrap();
        let xi = x % (2*k);
        let mut yi = y % (2*k);
        if w[2] == "W" {
            yi = (yi + k) % (2 * k);
        }
        if xi >= k {
            map[xi-k][(yi+k)%(2*k)] += 1;
        } else {
            map[xi][yi] += 1;
        }
    }

    for i in 1..k {
        map[i][0] += map[i-1][0];
    }
    for i in 1..2*k {
        map[0][i] += map[0][i-1];
    }
    for i in 1..k {
        for j in 1..2*k {
            map[i][j] += map[i-1][j] + map[i][j-1] - map[i-1][j-1];
        }
    }

    let mut max = map[k-1][k-1];
    for i in 1..k {
        let sum = map[k-1][k-1] + map[i-1][2*k-1] - 2*map[i-1][k-1];
        max = cmp::max(max,cmp::max(sum,n as i64 - sum));
    }
    for i in 0..k {
        let sum = map[k-1][i+k] - map[k-1][i];
        max = cmp::max(max,cmp::max(sum,n as i64 - sum));
        for j in 1..k {
            let sum = map[k-1][i+k] - map[k-1][i] + map[j-1][2*k-1] + 2*map[j-1][i] - 2*map[j-1][i+k];
            max = cmp::max(max,cmp::max(sum,n as i64 - sum));
        }
    }
    println!("{}",max);
}


Measured memory_bytes: 24828
#include <bits/stdc++.h>
#define int long long 
#define re register int 
#define il inline
#define ll long long
using namespace std;
const int inf=1e9;
il int read(){
	char c=getchar();int z=0,f=1;
	while(c!='-'&&(c>'9'||c<'0')) c=getchar();
	if(c=='-') f=-1,c=getchar();
	while(c>='0'&&c<='9') z=(z<<1)+(z<<3)+c-'0',c=getchar();
	return z*f;
}
const int N=1e5+10;
const int mod=1e9+7;
int n,A,B;
int f[N],sum[N],a[N];
signed main (){
	n=read();A=read();B=read();
	if(A<B) swap(A,B);
	for(re i=1;i<=n;i++) a[i]=read();
	for(re i=1;i+2<=n;i++) 
		if(a[i+2]-a[i]<B){cout<<0;return 0;}
	f[0]=sum[0]=1;
	for(re i=1,p=0,q=0;i<=n;i++){
		while(q<i&&a[i]-a[q+1]>=A) ++q;
		if(p<=q)f[i]=(f[i]+sum[q]-(p?sum[p-1]:0)+mod)%mod;
		sum[i]=(sum[i-1]+f[i])%mod;
		if(i>1&&a[i]-a[i-1]<B) p=i-1;
	}
	int ans=0;
	for(re i=n;i>=0;i--){
		ans=(ans+f[i])%mod;
		if(i<n&&a[i+1]-a[i]<B) break;
	}
	cout<<ans;
	return 0;
} 

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

#define INF 100000000

typedef struct state{
  int pos,cost;
} state;

state A[2000001];
int N=0;

int parent(int i){return i/2;}
int left(int i){return i*2;}
int right(int i){return i*2+1;}

void exchange(state* a, state* b){
  state tmp=*a;
  *a=*b;
  *b=tmp;
}

void minHeapify(int i){
  int l=left(i);
  int r=right(i);
  int small;

  if( l<=N && A[l].cost<A[i].cost )small=l;
  else small=i;

  if( r<=N && A[r].cost<A[small].cost)small=r;

  if(small!=i){
    exchange(&A[i],&A[small]);
    minHeapify(small);
  }

}

state heapExtractMin(){
  if(N<1)return (state){0,0};
  state min=A[1];
  A[1]=A[N];
  N--;
  minHeapify(1);
  return min;
}


void heapIncreaseKey(int i, state key){
  if(key.cost>A[i].cost)return;

  A[i]=key;
  while(i>1&&A[parent(i)].cost>A[i].cost){
    exchange(&A[i],&A[parent(i)]);
    i=parent(i);
  }
}

void minHeapInsert(state key){
  N++;
  A[N]=(state){INF, INF};
  heapIncreaseKey(N, key);
}


typedef struct edge{
  int to,cost;
} edge;

edge* G[10000];
int size[10000];
int n;
int d[10000];
edge e;
state s;

int main(){

  int i, j, a, b;

  scanf("%d", &n);

  for(i=0; i<n; i++){
    scanf("%d %d", &a, &b);
    G[a] = malloc( sizeof( edge ) *b );
    size[a]=b;
    for(j=0; j<b; j++){
      scanf("%d %d",&G[a][j].to, &G[a][j].cost);
    }
    d[i]=INF;
  }

  d[0]=0;
  minHeapInsert( (state){0, 0} );

  while(N!=0){
    s = heapExtractMin();
    if(s.cost>d[s.pos])continue;
    for(i=0;i<size[s.pos];i++){
      e=G[s.pos][i];
      if(d[e.to]<=d[s.pos]+e.cost)continue;
      d[e.to]=d[s.pos]+e.cost;
      minHeapInsert((state){e.to, d[e.to]});
    }
  }

  for(i=0; i<n; i++)
    printf("%d %d\n", i, d[i]);

  return 0;
}

Measured memory_bytes: 4580
import std.algorithm, std.conv, std.range, std.stdio, std.string;

void main()
{
  auto n = readln.chomp.to!size_t;
  auto ai = readln.split.to!(int[]);

  auto c = 0;
  mergeSort(ai, 0, n, c);

  writeln(ai.to!(string[]).join(" "));
  writeln(c);
}

void merge(ref int[] ai, size_t l, size_t m, size_t r, ref int c)
{
  auto li = ai[l..m].dup;
  auto ri = ai[m..r].dup;

  li ~= int.max;
  ri ~= int.max;

  auto i = 0, j = 0;
  foreach (k; l..r) {
    ++c;
    if (li[i] <= ri[j]) {
      ai[k] = li[i];
      ++i;
    } else {
      ai[k] = ri[j];
      ++j;
    }
  }
}

void mergeSort(ref int[] ai, size_t l, size_t r, ref int c)
{
  if (l + 1 < r) {
    auto m = (l + r) / 2;
    mergeSort(ai, l, m, c);
    mergeSort(ai, m, r, c);
    merge(ai, l, m, r, c);
  }
}

Measured memory_bytes: 28032
def f(a):
	res = 1
	for i in range(n):
		res *= int(a[i])
		if res > 10 ** 18:
			if zer(i):
				return 0
			else:
				return -1
	return res

def zer(i):
	for j in range(i, n):
		if a[j] == "0":
			return True
	return False
n = int(input())
a = input().split()

print(f(a))


Measured memory_bytes: 19352
#include <iostream>

using namespace std;

int main()
{
    int N;
    cin>>N;
    int flag=0;
    while(N!=0){
        int x=N%10;
        if(x==7){
            flag=1;
            break;
        }
        N=N/10;
    }
    if(flag==1){
        cout<<"Yes\n";
    }
if (flag==0){
    cout<<"No"<<endl;
}
    return 0;
}


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

const int MAXN = 4000;

int dp[MAXN][MAXN];

char s[MAXN], t[MAXN];
stack<char> ans;

int main(){
	scanf(" %s", s);
	scanf(" %s", t);
	int stam = strlen(s);
	int ttam = strlen(t);
	for(int i = 1; i <= stam; i++){
		for(int j = 1; j <= ttam; j++){
			if (i == 1 && j == 1){
				if(s[i - 1] == t[j - 1]) dp[i][j] = 1;
				else dp[i][j] = 0;
			}
			else{
				if(s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
				else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
			}
		}
	}
	// printf("%d\n", dp[stam][ttam]);
	int i = stam, j = ttam;
	while(i > 0 || j > 0){
		// printf("%d %d\n", i, j);
		if(i > 0 && j > 0 && dp[i][j] == dp[i - 1][j - 1] + 1 && s[i - 1] == t[j - 1]){
			ans.push(s[i - 1]);
			i--;
			j--;
		}
		else if(i > 0 && dp[i - 1][j] == dp[i][j]) i--;
		else j--; 
	}
	while(!ans.empty()){
		printf("%c", ans.top());
		ans.pop();
	}
	printf("\n");
}


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

#define rep(i,n) for(int i=0; i<n; i++)
#define all(x) (x).begin(),(x).end()
#define INF (1e9)

class UnionFind{
  public:
  //親の番号を格納する 親だった場合-1*集合のサイズ
  vector<int> Parent;

  //コンストラクタ 初めはバラバラの状態
  UnionFind(int N){
    Parent = vector<int>(N,-1);//要素数N,要素の値-1で初期化
  }

  //Ａがどのグループに属しているか調べる
  int root(int A){
    if(Parent[A] < 0)return A;//Aが親だったらA自身を返す
    return Parent[A] = root(Parent[A]);//親に繋ぎなおす
  }

  //頂点数を調べる
  int size(int A){
    return -Parent[root(A)];//Aの根×-1=集合のサイズ
  }

  //AとBをくっつける
  bool connect(int A, int B){
    //Aの根とBの根をくっつける
    A = root(A);
    B = root(B);
    if(A==B)return false;//既に同じグループならそのままでfalseを返す

    //Aのサイズ>=Bのサイズとする  
    if(size(A)<size(B))swap(A,B);

    Parent[A] += Parent[B];//AのサイズにBのサイズを足す
    Parent[B] = A;//Bの親をAに変更する
    return true;
  }

  //AとBが同じグループかどうか調べる
  bool same(int A,int B){
    if(root(A)==root(B))return true;
    else return false;
  }

};

int main(){
  int n,k,l,p[100010],q[100010],r[100010],s[100010];
  cin >> n >> k >> l;
  UnionFind UniT(n);
  UnionFind UniD(n);
  rep(i,k){
    cin >> p[i] >> q[i];
    UniD.connect(p[i]-1,q[i]-1);
  }
  rep(i,l){
    cin >> r[i] >> s[i];
    UniT.connect(r[i]-1,s[i]-1);
  }
  vector<pair<int,int> > P(n);
  map<pair<int,int>,int> mp;//あるペアがいくつあるか
  rep(i,n){
    P[i] = make_pair(UniD.root(i),UniT.root(i));
    mp[P[i]]++;
  }

  rep(i,n){
    cout << mp[P[i]];
    if(i!=n-1)cout << " ";
  }
  cout << endl;
}

Measured memory_bytes: 16640
#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <numeric>
#include <queue>
#include <numeric>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <map>
#include <functional>
#include <limits>
#include <set>
#include <stack>
#include <cctype>
#define rep(i,a,b) for((i)=a;i<(int)(b);i++)

#define AAA (1000000007) 


using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pairII;


ll gcd(ll a, ll b) {
	if (b == 0)return a;
	return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}
ll powD(ll a, ll b) {
	ll ans = 1;
	a %= AAA;
	for (int i = 0; i < b; i++)
	{
		ans *= a;
		ans %= AAA;
	}
	return ans;
}

int primeNumber(const int n) {
	//上から確認する
	for (int N = n; N >= 1; N--) {

		bool isPrime = true;
		//素数判定 i < sqrt(N)+1
		for (int i = 2; i * i <= N; i++) {
			if (N % i == 0) {
				isPrime = false;
				break;
			}
		}
		//もし素数なら
		if (isPrime) {
			return N;
		}
	}
}

int main() {
	int i, j, k;

	int A, B, C;
	cin >> A >> B >> C;
	C -= A - B;
	C = max(C, 0);
	cout << C << endl;

	return 0;
}

Measured memory_bytes: 3632
#include<stdio.h>
int n,m;
int num[100005];
bool ans[100005];
main()
{
    int i,x,y;
    int cnt;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        num[i] = 1;
        ans[i] = false;
    }
    ans[1] = true;
    for(i=0;i<m;i++)
    {
        scanf("%d%d",&x,&y);
        num[x]--; num[y]++;
        if(ans[x]) ans[y] = true;
        if(num[x]==0) ans[x] = false;
    }
    cnt = 0;
    for(i=1;i<=n;i++) if(ans[i] && num[i]) cnt++;
    printf("%d",cnt);
}


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

int main() {
    int sx, sy, tx, ty; cin >> sx >> sy >> tx >> ty;
    int dx = tx - sx, dy = ty - sy;
    cout << string(dx, 'R') << string(dy, 'U');
    cout << string(dx, 'L') << string(dy, 'D');
    cout << 'D' << string(dx + 1, 'R') << string(dy + 1, 'U') << 'L';
    cout << 'U' << string(dx + 1, 'L') << string(dy + 1, 'D') << 'R';
    cout << endl;
    return 0;
}


Measured memory_bytes: 256