akhauriyash/Code-Regression huggingface dataset:
n = int(input())
v = list(map(int, input().split()))
d1 = {}
d2 = {}

for i in range(0, n, 2):
    if v[i] in d1.keys():
        d1[v[i]] += 1
    else:
        d1[v[i]] = 1
for i in range(1, n, 2):
    if v[i] in d2.keys():
        d2[v[i]] += 1
    else:
        d2[v[i]] = 1


def keys_values(d):
    fk, fv, sk, sv = 0, 0, 0, 0
    for k in d:
        if d[k] > fv:
            sk, sv = fk, fv
            fk, fv = k, d[k]
        elif d[k] > sv:
            sk, sv = k, d[k]
    return fk, fv, sk, sv


ak, av, bk, bv = keys_values(d1)
ck, cv, dk, dv = keys_values(d2)
if ak != ck:
    print(n-av-cv)
else:
    print(min((n-av-dv), n-bv-cv))


Measured memory_bytes: 18016
N = int(input())
A = [i for i in map(int,input().split())]
B = [i for i in map(int,input().split())]
ans = 0
for i in range(N):
    if A[i] > B[i]:
        ans += B[i]
    if B[i] >= A[i]:
        if A[i+1] > (B[i] - A[i]):
            ans += B[i]
            A[i+1] -= (B[i] - A[i])
        else: 
            ans += (A[i] + A[i+1])
            A[i+1] = 0
print(ans)




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

int count(int n, int x){
	int sum = 0;
	for(int i = 1; i <=  n-2; i++){
		for(int j = i+1; j <= n-1; j++){
			for(int k =j+1; k <= n; k++){
				if(i + j + k == x) sum++;
			}
		}
	}
	
	return sum;
}

int main(){
	int n, x;
	while(1){
		cin >> n >> x;
		if(n == 0 && x == 0) break;
		cout << count(n, x) << endl;
	}

	return 0;
}

Measured memory_bytes: 1160
#include <stdio.h>

int main(){
    int h,w;
    int i,j;
    while(1){
        scanf("%d %d", &h,&w);
        
        if (h == 0 && w == 0){
            break;
        }
        
        
        for (i=0;i<h;i++){
            for (j=0;j<w;j++){
                if(i==0 || i==h-1 || j==0 || j==w-1){
                    printf("#");
                }else{
                    printf(".");
                }
            }
            printf("\n");
        }
        printf("\n");
    }
    
    return 0;
}
        
    
    

Measured memory_bytes: 572
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
typedef long long ll;

int main(){
    int n; string s ;cin>>n>>s;
    rep(i,s.size())s[i] = (char)((s[i]-'A'+n)%26+'A');
    cout<<s<<endl;return 0;
}


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

using namespace std;

const int N_CONTEST = 26;

struct Contest {
    int day;
    vector<int> complain;
    vector<vector<int>> satisfy;

    Contest() {
        cin >> day;

        complain.resize(N_CONTEST+1);
        for ( int c = 1; c <= N_CONTEST; c++ )
            cin >> complain.at(c);

        satisfy.resize(day+1);
        for ( int d = 1; d <= day; d++ ) {
            satisfy.at(d).resize(N_CONTEST+1);
            for ( int c = 1; c <= N_CONTEST; c++ )
                cin >> satisfy.at(d).at(c);
        }
    }

    void dump() {
        printf("----- Dump contents of struct Contest -----\n"
               "%d\n", day);
        for ( int c = 1; c <= N_CONTEST; c++ )
            printf("%d ", complain.at(c));
        printf("\n");
        for ( int d = 1; d <= day; d++ ) {
            for ( int c = 1; c <= N_CONTEST; c++ )
                printf("%d ", satisfy.at(d).at(c));
            printf("\n");
        }
        printf("----- Dump done -----\n");
    }
};

static int calc_greedy_ans (Contest contests, int day, vector<int> last) {
    int max_score = INT_MIN;
    int ans_c = 1;

    for ( int con = 1; con <= N_CONTEST; con++ ) {
        int score = contests.satisfy.at(day).at(con);
        for ( int con_ = 1; con_ <= N_CONTEST; con_++ ) {
            if ( con_ == con ) {
                continue;
            }
            score -= contests.complain.at(con_) * (day - last.at(con_));
        }
        if ( score > max_score ) {
            max_score = score;
            ans_c = con;
        }
    }

    last.at(ans_c) = day;

    return ans_c;
}

static void dump_ans (Contest contests) {
    vector<int> last(N_CONTEST+1, 0);

    for ( int d = 1; d <= contests.day; d++ ) {
        int c = calc_greedy_ans(contests, d, last);
        cout << c << endl;
    }
}

int main (void) {
    Contest contests;

    dump_ans(contests);

    return 0;
}



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

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

#define rep(i,cc,n) for(int i=cc;i<n;++i)
#define lrep(i,cc,n) for(long long i=cc;i<n;++i)
#define sqrep(i,cc,n) for(long long i=cc;i*i<=n;++i)
#define rrep(i,cc,n) for(long i=cc;i>n;--i)
#define pii pair<int, int>
#define pll pair<long long, long long>
 
using ll = long long;

const vector<int> dx = {1, 0, -1, 0};
const vector<int> dy = {0, 1, 0, -1};
const double PI = 3.1415926535;
const ll inf = 1001001001;
const ll e9  = 1000000000;
const ll mod = 1000000007;

int main(){
    int n;
    cin >> n;
    vector<ll>a(n),t(n);
    rep(i, 0, n)cin >> a[i] >> t[i];
    ll left=a[0], right=t[0];
    rep(i, 1, n){
        if(a[i]>=left && t[i]>=right){
            left = a[i];
            right = t[i];
        }else if(a[i]<left && t[i]>=right){
            ll temp = (left+a[i]-1)/a[i];
            left = a[i]*temp;
            right = t[i]*temp;
        }else if(a[i]>=left && t[i]<right){
            ll temp = (right+t[i]-1)/t[i];
            left = a[i]*temp;
            right = t[i]*temp;
        }else{
            ll tempa = (left+a[i]-1)/a[i];
            ll tempt = (right+t[i]-1)/t[i];
            left = a[i]*max(tempa,tempt);
            right = t[i]*max(tempa,tempt);
        }
        //cout << left << " " << right << endl;
    }
    cout << left+right << endl;
}

Measured memory_bytes: 3644
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

const i64 mod = 1e9 + 7;
int n;
string s;
int main() {
  cin >> n >> s;

  i64 ans = 1, h = 0;
  for (char c : s) {
    if ((c == 'B' && h % 2 == 0) || (c == 'W' && h % 2 == 1)) {
      ++h;
    } else {
      (ans *= h) %= mod;
      --h;
    }
    if (h < 0) {
      cout << 0 << endl;
      return 0;
    }
  }
  if (h != 0) ans = 0;

  for (i64 i = 1; i <= n; ++i) {
    (ans *= i) %= mod;
  }
  cout << ans << endl;
  return 0;
}

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

using namespace std;

int main(){
  int n,t,j;
  int c = 1001;
  cin >> n >> t;
  int cs[100],ts[100];
  for(int i=0;i<n;i++){
    cin >> cs[i] >> ts[i];
    if(ts[i]<t+1){
      j = cs[i];
      c = min(j,c);
    }
  }

if(c==1001){
  cout << "TLE" << endl;
}else{
  cout << c << endl;
}

}


Measured memory_bytes: 256
import math
int_n = int(input())
i = (math.sqrt(int_n))
i = math.floor(i)
while i >= 1:
    if int_n % i == 0:
        j = int_n/i
        print(math.floor((i - 1) + (j - 1)))
        break
    i = i - 1

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

int main() {
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  if (A+B > C+D) {
    cout << "Left" << endl;
  }
  else if (A+B == C+D){
    cout << "Balanced" << endl;
  }
  else if (A+B < C+D){
    cout << "Right" << endl;
  }
  
}

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

int main(){
    int a, b; scanf("%d%d", &a, &b);
    if(a<b){
        for(int i=0; i<b; i++) {
            printf("%d", a);
        }
    }else{
        for(int i=0; i<a; i++){
            printf("%d", b);
        }
    }
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
    
    Scanner sc = new Scanner(System.in);
      
      int A = sc.nextInt();//高HP
      int B = sc.nextInt();//高攻撃力
      int C = sc.nextInt();//青HP
      int D = sc.nextInt();//青攻撃力
      
      //どちらかが先にHP０になるまで
      while(true){
       C = C-B;
       A = A-D;
      
      if(C<=0){
          System.out.print("Yes"); 
        break;
      }
        else if(A<=0){
          System.out.print("No");
         break;
        }
      }
    }
}

Measured memory_bytes: 35616
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lb long double
#define pb push_back
#define l first
#define r second
#define qwerty3 -> first
#define qwerty4 -> second
#define umap unordered_map
#define uset unordered_set
#define pii pair < int , int >

using namespace std;

const int N = 100005;
const int M = 1000000007;
const lb PI = acos(-1);

int n , k;
char x , y;
pair < int , int > a[N];

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

    int i , cnt = 0 , lg = 1;

    cin >> n >> k;
    cin >> x;

    for(i = 2 ; i <= n ; i++)
    {
        cin >> y;

        if(x == y)
            ++lg;
        else
        {
            if(x == '0')
                a[++cnt] = {i - lg , i - 1};

            lg = 1;
        }

        x = y;
    }

    if(y == '0')
        a[++cnt] = {n - lg + 1 , n};

    if(cnt <= k)
    {
        cout << n;
        return 0;
    }

    int ans = 0;

    for(i = 2 ; i < cnt - k + 1 ; i++)
        ans = max(ans , a[i + k].l - 1 - (a[i - 1].r + 1) + 1);

    ans = max(ans , a[1 + k].l - 1);
    ans = max(ans , n - a[cnt - k].r);

    cout << ans;

    return 0;
}


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

int main() {
  string sa,sb,sc;
  cin >> sa >> sb >> sc;
  char turn='a';
  while(true) {
    if (turn=='a') {
      if (sa.size()==0) break;
      turn=sa.at(0);
      sa.erase(sa.begin());
    }else if (turn =='b') {
      if (sb.size()==0) break;
      turn=sb.at(0);
      sb.erase(sb.begin());
    }else if (turn=='c') {
      if (sc.size()==0) break;
      turn=sc.at(0);
      sc.erase(sc.begin());
    }
  }
  if (turn=='a') turn='A';
  if (turn=='b') turn='B';
  if (turn=='c') turn='C';
  cout << turn << endl;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"bufio"
	"os"
	"strconv"
)

//=====I/O=====

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func scanInt() int {
	sc.Scan()
	a,_ := strconv.Atoi(sc.Text())
	return a
}

func scanInt64() int64 {
	sc.Scan()
	a,_ := strconv.ParseInt(sc.Text(),10,64)
	return a
}

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ { res[i] = scanInt() }
	return res
}

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

func printInts(a ...int) {
	for i, e := range a {
		fmt.Fprint(wr, e)
		if i != len(a)-1 { fmt.Fprint(wr, " ") }
	}
	fmt.Fprintln(wr)
	wr.Flush()
}

//=====main=====

func main() {
	sc.Split(bufio.ScanWords)

	n := scanInt()
	ss := make([]string, n)
	ts := make([]int, n)
	
	for i := 0; i < n; i++ {
		ss[i] = scanText()
		ts[i] = scanInt()
	}

	f := false

	x := scanText()

	ans := 0
	for i := 0; i < n; i++ {
		if f {
			ans+=ts[i]
		}

		if ss[i]==x {
			f = true
		}
	}

	fmt.Println(ans)
}


Measured memory_bytes: 640
from scipy.sparse import*;f=lambda*z:map(int,input().split());n,=f();c=[1]*~-n;g,h=csgraph.dijkstra(csr_matrix((c,list(zip(*map(f,c)))),[n+1]*2),0,[1,n]);print('FSennunkeec'[sum(g[i]>h[i]for i in range(n+1))*2>=n::2])

Measured memory_bytes: 68956
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>

using namespace std;

int main()
{
   long long N,ans = 0;
   cin>>N;
   vector<vector<char>> s(N,vector<char>(10));
   map<vector<char>,long long> M;
   for(int i = 0;i<N;i++)
   {
      for(int j = 0;j<10;j++)
      {
          cin>>s[i][j];
      }
     
   }
   for(int i = 0;i<N;i++)
   {
      sort(s[i].begin(),s[i].end());
      auto itr = M.find(s[i]);
      if(itr == M.end()) //キーとしてs[i]が存在しないなら
      {
      M[s[i]] = 1;
 //     ans++;
      }
      else 
      {
         M[s[i]]++;
      }
   }
 //  int max = (*max_element(M.begin(),M.end())).second;
   for(auto i = M.begin();i!=M.end();i++)
   {
      long long a = i->second;
      ans += (a*(a-1))/2;
   }
   cout<<ans;
}

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

using namespace std;

typedef long long ll;

int n;
int dp[201][201];

int gcd(int a, int b) {
  if(dp[a][b] > 0) return dp[a][b];
  if(a == 0) return b;
  dp[a][b] = gcd(b % a, a);
  return dp[a][b];
}

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

  memset(dp, 0, sizeof(dp));
  
  cin >> n;
  int ans = 0;
  for(int i = 1; i <= n; ++i) {
    for(int j = 1; j <= n; ++j) {
      for(int k = 1; k <= n; ++k) {
        ans += gcd(i, gcd(j, k));
      }
    }
  }
  cout << ans << '\n';
  
  return 0;
}


Measured memory_bytes: 3764
import itertools
combi = itertools.combinations([0,1,2,3,4], 3)
n = int(input())
num = [0,0,0,0,0]
count = 0

for _ in range(n):
    tmp = input()
    if tmp[0] =="M":
        num[0] +=1
    elif tmp[0] == "A":
        num[1] += 1
    elif tmp[0] == "R":
        num[2] += 1
    elif tmp[0] == "C":
        num[3] += 1
    elif tmp[0] == "H":
        num[4] += 1
    else:
        continue

for i in combi:
    count += num[list(i)[0]] * num[list(i)[1]] * num[list(i)[2]]
print(count)

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

int main()
{
    //ios::sync_with_stdio(0); cin.tie(0); //C++关同步
    int n;
    cin >> n;
    ll ans = 1, res = 360;
    while(n != 0){
        ans *= res / n;
        n = res % n;
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 3532
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int,int>;
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; }
ll gcd(ll a, ll b) { return b?gcd(b, a%b):a;}
ll lcm(ll a, ll b) { return a*b/gcd(a,b);}
ll MOD=1000000007;



int main(){
  int n,q;cin>>n>>q;
  string s;cin>>s;
  vi kaisu(n);
  int k=0;
  for(int i=1;i<n;i++){
    if(s.at(i-1)=='A' and s.at(i)=='C'){
      k++;
    }
    kaisu.at(i)=k;
  }

  rep(i,q){
    int l,r;
    cin>>l>>r;
    cout<<kaisu.at(r-1)-kaisu.at(l-1)<<endl;
  }
}

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

using ll = long long;

int main(){
  int N,K;
  cin >> N >> K;
  vector<int> A(N);
  int d,num;
  rep(i,K){
    cin >> d;
    rep(j,d){
      cin >> num;
      A[num-1]++;
    }

  }

  int ans = 0;
  rep(i,N){if(A[i]==0)ans++;}

  cout << ans << endl;
}


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

int a[2010][2010];
int sum1[2010][2010], sum2[2010][2010];
int n, d, now;

int chmax(int &x, int y){
	x = x > y ? x : y;
}

int count1(int a, int b, int c, int d){
	if (a > c || b > d) return 0;
	return sum1[c][d] - sum1[a - 1][d] - sum1[c][b - 1] + sum1[a - 1][b - 1];
}

int count2(int a, int b, int c, int d){
	if (a > c || b > d) return 0;
	return sum2[c][d] - sum2[a - 1][d] - sum2[c][b - 1] + sum2[a - 1][b - 1];
}

int check(int k){
	for (int i = 1; i <= d; i++){
		for (int j = 1; j <= d; j++){
			int flag = 1;
			if (count1(i + k, j + k, d + i - 1, d + j - 1) != (d - k) * (d - k)) flag = 0;
			if (count2(1, 1, d, d) - count2(i, j, i + k - 1, j + k - 1) != d * d - k * k) flag = 0;
			if (flag) return 1;
		}
	}
	return 0;
}

int main(){
	scanf("%d%d", &n, &d);
	for (int i = 0; i < n; i++){
		int x, y; scanf("%d%d", &x, &y);
		a[x % d + 1][y % d + 1]++;
	}
	int maxj = 0;
	for (int i = 1; i <= d; i++){
		for (int j = 1; j <= d; j++){
			maxj = max(maxj, a[i][j]);
		}
	}
	now = 1;
	while (now * now < maxj) now++;
	now--;
	for (int i = 1; i <= 2 * d; i++){
		for (int j = 1; j <= 2 * d; j++){
			a[i][j] = a[(i - 1) % d + 1][(j - 1) % d + 1];
			sum1[i][j] = sum1[i - 1][j] + sum1[i][j - 1] - sum1[i - 1][j - 1] + (a[i][j] <= now * now);
			sum2[i][j] = sum2[i - 1][j] + sum2[i][j - 1] - sum2[i - 1][j - 1] + (a[i][j] <= now * (now + 1));
		}
	}
	int l = 0, r = d;
	while (l < r){
		int mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%d\n", now * d - 1 + l);
	return 0;
}


Measured memory_bytes: 47488
class UnionFind():
    # コンストラクタ
    def __init__(self, n):
        # 要素数
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n

    # 要素xが属するグループの根を返す
    # 経路圧縮
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 要素xが属するグループと要素yが属するグループとを併合する
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]

    # 要素x,yが同じグループに属するかどうかを返す
    def same(self, x, y):
        return self.find(x) == self.find(y)

N,M = map(int,input().split())
AB = [[int(i)-1 for i in input().split()] for _ in range(M)]

UF = UnionFind(N)

from collections import deque

ans = deque([N*(N-1)//2])
for A,B in AB[::-1]:
    if UF.same(A,B):
        ans.appendleft(ans[0])
    else:
        ans.appendleft(ans[0] - UF.size(A) * UF.size(B))
        UF.union(A,B)

# 崩壊する前の情報はいらない
ans.popleft()

print(*ans, sep="\n")

Measured memory_bytes: 30728
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  int a, b ,c;
  cin >> a >> b >> c;
  int gusu = 0;
  if( a % 2 == 0){
    gusu += 1;
  }
  if( b%2 == 0){
    gusu += 1;
  }
  if( c%2 == 0){
    gusu += 1;
  }
  int maxn = 0;
  int ans = 0; 
  if(gusu == 1){
    if( a % 2 != 0){
      a += 1;
      }
    if( b%2 != 0){
      b += 1;
    }
    if( c%2 != 0){
      c += 1;
    }
    ans +=1;
  }
  else if(gusu == 2){
    if( a % 2 == 0){
      a += 1;
      }
    if( b%2 == 0){
      b += 1;
    }
    if( c%2 == 0){
      c += 1;
    }
    ans +=1;
  } 
  maxn = max(max(b,c),max(a,b));
  ans += (3*maxn - a - b -c)/2;
  cout << ans << endl;  
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
 
using namespace std;
typedef long long ll;
 
// int naive(int N, int K) {
//   int cnt = 0;
//   for (int a = 1; a <= N; a++) {
//     for (int b = 1; b <= N; b++) {
//       for (int c = 1; c <= N; c++) {
//         if ((a + b) % K == 0 && (b + c) % K == 0 && (a + c) % K == 0) {
//           cnt++;
//         }
//       }
//     }
//   }
//   return cnt;
// }

ll solve(ll N, ll K) {
  ll ans = 0;
  vector<ll> cnt(200001);
  for(ll i = 1; i <= N; i++) {
    cnt[i % K]++;
  }
  for(ll b = 0; b < K; b++) {
    ll m = (K - b) % K;
    if ((2 * m) % K == 0) {
      ans += cnt[m] * cnt[m] * cnt[b];
    }
  }
  return ans;
}

int main() {
  ll N, K;
  cin >> N >> K;
  cout << solve(N, K) << endl;
  return 0;
}

Measured memory_bytes: 1792
//------------------------------>> tsukasa_diary's template <<------------------------------//
#include <bits/stdc++.h>
using namespace std;

#define for_(i,a,b) for(int i=(a);i<(b);++i)
#define for_rev(i,a,b) for(int i=(a);i>=(b);--i)
#define allof(a) (a).begin(),(a).end()
#define minit(a,b) memset(a,b,sizeof(a))

using lint = long long;
using pii = pair< int, int >;

template< typename T > using Vec = vector< T >;

template< typename T > bool in_range(T x, T lb, T ub) { return lb <= x && x < ub; }
template< typename T > bool in_range(T x, T y, T lb, T ub) { return in_range(x, lb, ub) && in_range(y, lb, ub); }

template< typename T > void modAdd(T& a, T b, T mod) { a = (a + b + mod) % mod; }
template< typename T > void modMul(T& a, T b, T mod) { a = (a * b) % mod; }
template< typename T > void minUpdate(T& a, T b) { a = min(a, b); }
template< typename T > void maxUpdate(T& a, T b) { a = max(a, b); }

int bitCount(int x) { return __builtin_popcount(x); }
int bitCount(lint x) { return __builtin_popcountll(x); }

const int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};
const int Dx[8] = {0,1,1,1,0,-1,-1,-1}, Dy[8] = {-1,-1,0,1,1,1,0,-1};
const double EPS = 1e-9;
const double PI = acos(-1);

//--------------8---------------->> coding space <<-----------------8-------------//

struct Point {
	/*** Point on the 2D-plane ***/
	double x, y;
	Point operator + (const Point& p) const { return Point{x + p.x, y + p.y}; }
	Point operator - (const Point& p) const { return Point{x - p.x, y - p.y}; }
	Point operator * (double d) const { return Point{x * d, y * d}; }
	Point operator / (double d) const { return Point{x / d, y / d}; }
	bool operator < (const Point& p) const { return x == p.x ? y < p.y : x < p.x; }
	Point normal() const { return Point{y, -x}; }
	double norm() const { return x * x + y * y; }
};

double cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }

struct Circle {
	Point c;
	double r;
};

Circle make_circle(Point a, Point b, Point c) {
	Point s1 = (a + b) / 2.;
	Point s2 = (b + c) / 2.;
	Point t1 = s1 + (b - a).normal();
	Point t2 = s2 + (c - b).normal();
	
	double d1 = cross(t2 - s2, s2 - s1);
	double d2 = cross(t2 - s2, t1 - s1);
	Point ct = s1 + (t1 - s1) * d1 / d2;
	double r = (ct - a).norm();
	
	return Circle{ct, r};
}

int main() {
	int N;
	cin >> N;
	
	Vec<Point> p(N);
	for (int i=0; i<N; ++i) cin >> p[i].x >> p[i].y;
	
	double ans = 1e9;
	
	for (int i=0; i<N; ++i) for (int j=i+1; j<N; ++j) {
		Point c = p[i] + ((p[j] - p[i]) / 2);
		Circle circ{c, (p[i] - c).norm()};
		bool isok = true;
		for (int tar=0; tar<N; ++tar) {
			double dst = (circ.c - p[tar]).norm();
			isok &= (dst - circ.r < EPS);
		}
		if (isok) ans = min(ans, sqrt(circ.r));
	}
	
	for (int i=0; i<N; ++i) for (int j=i+1; j<N; ++j) for (int k=j+1; k<N; ++k) {
		Circle circ = make_circle(p[i], p[j], p[k]);
		bool isok = true;
		for (int tar=0; tar<N; ++tar) {
			double dst = (circ.c - p[tar]).norm();
			isok &= (dst - circ.r< EPS);
		}
		if (isok) ans = min(ans, sqrt(circ.r));
	}
	
	printf("%.9f\n", ans);
}
//--------------8---------------->> coding space <<-----------------8-------------//

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define mm 1000000007
int n,m,x,y,z,a,b,c,cc[300000],dd[300000],ff[300000];
char s[500000],ss[500000],g;
int main(){
	for (int i=1;i<=3;i++){
		scanf("%c",&g);
		if (g=='1') printf("9");
		else printf("1");
	}
	printf("\n");
	return 0;
}

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

int main()
{
  ll a, b, n;
  cin >> a >> b >> n;

  ll s = min(b - 1, n);
  ll ans = floor(a * s / b) - a * floor(s / b);
  cout << ans << endl;
}


Measured memory_bytes: 3564
#include"bits/stdc++.h"
using namespace std;
int main()
{
  int n;
  cin>>n;
  if(n<82) {
    if(n%10==0) {
      if(n/5 < 10) cout<<"Yes\n";
      else cout<<"No\n";
    }
    else {
        bool flag=0;
      for(int i=1;i<10;i++) {
          if(n%i==0 && ((n/i)<10) && n%(n/i)==0) {flag=1;break;}
      }
      if(flag) cout<<"Yes\n";
      else cout<<"No\n";
    }
  }
    else {
      cout<<"No\n";
    }
}


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

using namespace std;

int main(){
	string s[8];
	while(true){
		bool end = false;
		for(int i=0;i<8;i++){
			if(!(cin >> s[i])) end = true;
		}
		if(end) break;
		for(int i=0;i<8&&!end;i++){
			for(int j=0;j<8&&!end;j++){
				if(s[i][j]=='1'){
					if(i+3<8&&s[i+3][j]=='1') cout << "B" << endl;
					else if(j+3<8&&s[i][j+3]=='1') cout << "C" << endl;
					else if(i+2<8&&0<=j-1&&s[i+2][j-1]=='1') cout << "D" << endl;
					else if(i+1<8&&j+2<8&&s[i+1][j+2]=='1') cout << "E" << endl;
					else if(i+2<8&&j+1<8&&s[i+2][j+1]=='1') cout << "F" << endl;
					else if(i+1<8&&0<=j-1&&s[i+1][j-1]=='1') cout << "G" << endl;
					else cout << "A" << endl;
					end = true;
				}
			}
		}
	}
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include<vector>
#include<algorithm>
#include<math.h>
#include<limits.h>
#include<string>
#include<iomanip>
#include<numeric>
#include<queue>
using namespace std;

long long  mod = 1000000007;

long max(long x, long y) {
	return x > y ? x : y;
}

long min(long x, long y) {
	return x < y ? x : y;
}

long factorial(long n) {
	if (n == 1) {
		return 1;
	}
	else {
		return n * factorial(n - 1);
	}
}

long long  fel(long long  n,long long  f) {

		if (f == 1) {
			return n % mod;
		}
		else if (f % 2 == 0) {
			return (fel(n,f / 2) * fel(n,f / 2)) % mod;
		}
		else {
			return ((n  * fel(n,f / 2) %mod) * fel(n,f / 2))% mod;
		}
	

}


int main()
{

	int n;
	string s;

	cin >> n;
	cin >> s;

	if (n < 3200) {
		cout << "red";
	}
	else {
		cout << s;
	}
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
// statics
using namespace std;
using int64 = long long;
using PAIR = pair<int64, int64>;
constexpr int INF = 1 << 30;
constexpr int64 LINF = 1LL << 60;
constexpr int MOD = 1e9 + 7;
constexpr int MAX_N = 3e5 + 1;

// init/input
#define int int64
#define INIT ios::sync_with_stdio(false);cin.tie(0);
#define VAR(type, ...) type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T &t) {cin>>t;}
template<typename First, typename...Rest> void MACRO_VAR_Scan(First &first, Rest&...rest) {cin>>first;MACRO_VAR_Scan(rest...);}
#define VEC(type, c, n) vector<type> c(n);for(auto &&i:c)cin>>i;

// out
#define OUT(dist) cout<<(dist);
#define FOUT(n, dist) cout<<fixed<<setprecision(n)<<(dist);
#define SP cout<<" ";
#define BR cout<<endl;
#define zero(n) cout<<setfill('0')<<right<<setw(n)
#define debug(x) cerr<<#x<<":"<< (x);BR;

// utility
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(i, a) for(auto &&i:(a))
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RFOR(i, a, b) for(int i=(b)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<(n);++i)
#define RREP(i, n) for(int i=(n)-1;i>=0;--i)
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; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}

signed main() {
  INIT;
  VAR(int,a,b,c,d);

  int la = (a-1)/c;
  int lb = (a-1)/d;
  int ua = b/c;
  int ub = b/d;
  int lab = (a-1)/(c*d/gcd(c,d));
  int uab = b/(c*d/gcd(c,d));
  debug(ua-la);
  debug(ub-lb);
  debug(uab-lab);
  OUT(b-a+1-(ua+ub-la-lb-(uab-lab)))BR;
  
  return 0;
}


Measured memory_bytes: 764
#include <stdio.h>

int main(void){

  int a,b;
  scanf("%d", &a);
  scanf("%d", &b);
  int check[3];
  for (int i = 0; i < 3; i++) {
    check[i] = 0;
  }
  check[a-1] = 1;
  check[b-1] = 1;
  for (int i = 0; i < 3; i++) {
    if (check[i] == 0) {
      printf("%d\n", i+1);
      break;
    }
  }

  return 0;
}

Measured memory_bytes: 128
def max(a,b); a > b ? a : b; end

N = gets.to_i
C = Array.new(10 ** 5, 0)

gets.split.map(&:to_i).each do |v|
  C[v] += 1
end
ans = (1 .. C.size - 2).inject(0) do |m,i|
  max(m, C[i-1] + C[i] + C[i + 1])
end
puts ans


Measured memory_bytes: 8836
import collections

s = input()
k = int(input())
b = collections.Counter(s)
c = sorted(b.items())
con = []
n = 0
while True:
    con.append(c[n][0])
    if len(con) == k:
        break
    for i in range(len(c)):
        check = c[n][0] + c[i][0]
        if check in s:
            con.append(check)
            if len(con) >= k:
                break
            for i_2 in range(len(c)):
                check_2 = check + c[i_2][0]
                if check_2 in s:
                    con.append(check_2)
                    if len(con) >= k:
                        break
                    for i_3 in range(len(c)):
                        check_3 = check_2 + c[i_3][0]
                        if check_3 in s:
                            con.append(check_3)
                            if len(con) >= k:
                                break
                            for i_4 in range(len(c)):
                                check_4 = check_3 + c[i_4][0]
                                if check_4 in s:
                                    con.append(check_4)
                                    if len(con) >= k:
                                        break
    if len(con) >= k:
        break                              
    n +=1
print(con[k-1])

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

int a[maxn], b[maxn];
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);

    int n;
    cin >> n;
    for (int i = 1; i <= n + 1; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];
    ll ans = 0;
    for (int i = 1; i <= n; ++i){
        if (a[i] + a[i + 1] >= b[i]){
            ans += b[i];
            b[i] -= a[i];
            if (b[i] < 0) b[i] = 0;
            a[i + 1] -= b[i];
        }else{
            ans += a[i] + a[i + 1];
            a[i] = a[i + 1] = 0;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
import scala.io.StdIn._

object Main extends App {

  val Array(n,k,s) = readLine().split(" ").map(_.toInt)
  def solve() = {
    val str = if(s == 1e9) {
      ((1e9.toInt).toString + ",") * k + "1," * (n-k)
    } else {
      (s.toString + ",") * k + ((s+1).toString + ",") * (n-k)
    }
    str.split(",").mkString(" ")
  }

  println(solve())

}



Measured memory_bytes: 70280
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <cmath>
#include <numeric>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <complex>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <list>
#include <unordered_map>

using namespace std;
typedef long long ll;
#define inf 1e4+1

int main()
{
	int n;
	const int k = 3;
	std::cin >> n;

	vector< vector<int> > a(n, vector<int>(k));
	vector< vector<int> > dp(n, vector<int>(k));

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < k; ++j)
		{
			cin >> a[i][j];
		}
	}

	dp[0] = a[0];
	for (int i = 1; i < n; ++i)
	{
		int preID = i - 1;
		dp[i][0] = a[i][0] + max(dp[preID][1], dp[preID][2]);
		dp[i][1] = a[i][1] + max(dp[preID][0], dp[preID][2]);
		dp[i][2] = a[i][2] + max(dp[preID][1], dp[preID][0]);
	}

	int ans = 0;
	int s = n - 1;
	ans = max(dp[s][0], dp[s][1]);
	ans = max(ans, dp[s][2]);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 11136
import collections
n = int(input())
blue = [input() for i in range(n)]
blue_count = collections.Counter(blue)
m = int(input())
red = [input() for i in range(m)]
red_count = collections.Counter(red)
yen = []
for k, v in blue_count.items():
    if k in red_count:
        x = red_count[k]
        count = v - x
        yen.append(count)
    else:
        yen.append(v)
y = max(yen)
print(max(0, y))

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

typedef long long ll;
typedef pair<int,int> ii;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	string s; cin>>s;
	int ret=0;
	for (const char &ch: s)
		if(ch=='x')
			ret++;
	cout<<(ret>=8?"NO":"YES")<<"\n";
	return 0;
}

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

int main(){
  int n, ret=0;
  cin >> n;
  vector<string>s(n);
  for(int i=0; i<n; i++)cin >> s[i];
  int la=0, fb=0, lafb=0;
  for(int i=0; i<n; i++){
    for(int j=0; j<s[i].length()-1; j++){
      if(s[i][j]=='A' && s[i][j+1]=='B')ret++;
    }
    if(s[i][0]=='B')fb++;
    if(s[i][s[i].length()-1]=='A')la++;
    if(s[i][0]=='B' && s[i][s[i].length()-1]=='A')lafb++;
  }
  ret+=min(la, fb);
  if(lafb>0 && la+fb-2*lafb==0)ret--;
  cout << ret;
  return 0;
}

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

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

    int cost;
    int min_cost = 2 * 100000 * 5000;
    for (int i = max(x, y)*2; i >= 0; i--) {
        if (i % 2 != 0) continue;

        cost = c * i + max(0, x - i/2) * a + max(0, y - i/2) * b;
        min_cost = min(min_cost, cost);
    }

    cout << min_cost << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define all(vec) vec.begin(),vec.end()
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
#define pb push_back
#define fi first
#define se second
const int MOD=1e9+7;
const int INF=1e9;
const ll LINF=1LL<<60;
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
int main(){
    int n;
    cin>>n;
    cout<<"Christmas";
    REP(i,25-n){
        cout<<" Eve";
    }cout<<endl;
    return 0;
}

Measured memory_bytes: 768
MAX = 1000


def getAgenerator():
    for i in range(MAX):
        yield i


def getBgenerator():
    for j in range(MAX):
        yield j
        yield j * -1


X = int(input())

for a in getAgenerator():
    for b in getBgenerator():
        if a ** 5 - b ** 5 == X:
            print("{} {}".format(a, b))
            exit()


Measured memory_bytes: 68064
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> T gcd(T a, T b){return !b?a:gcd(b,a%b);}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
mt19937 R(chrono::system_clock().now().time_since_epoch().count());
const int N = 1066666;
int n,m,q,a[N],b[N],res;
int main() {
	read(n);read(m);read(q);int x=1e9,y=1e9;
	rep(i,1,n)read(a[i]),umin(x,a[i]);
	rep(i,1,m)read(b[i]),umin(y,b[i]);
	res=x+y;
	while(q--){
		int x,y,z;read(x);read(y);read(z);umin(res,a[x]+b[y]-z);
	}
	cout<<res;
	return 0;
}


Measured memory_bytes: 2688
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c;
    while(cin>>a>>b>>c)
    {
        if(a==b&&b==c)
        {
            cout<<"1"<<endl;
        }
        else if(a==b&&a!=c)
        {
            cout<<"2"<<endl;
        }
        else if(a==c&&a!=b)
        {
            cout<<"2"<<endl;
        }
         else if(b==c&&a!=b)
        {
            cout<<"2"<<endl;
        }
        else
        {
           cout<<"3"<<endl;
        }
    }

    return 0;
}



Measured memory_bytes: 256
use std::collections::VecDeque;
use std::io;

fn is_lunlun_num(target_num: i64) -> bool {
    let mut is_lunlun_num: bool = true;
    let str_num: String = target_num.to_string();
    let str_num_vec: Vec<char> = str_num.chars().collect();
    let digit_num = str_num_vec.len();
    for i in 0..(digit_num - 1) {
        let now_num = str_num_vec[i] as i64;
        let next_num = str_num_vec[i + 1] as i64;
        if (now_num - next_num).abs() > 1 {
            is_lunlun_num = false;
            break;
        }
    }
    is_lunlun_num
}

fn main() {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    let k: i64 = buf.trim().parse().unwrap();
    let mut queue: VecDeque<i64> = VecDeque::new();

    for i in 1..10 {
        queue.push_back(i);
    }

    let mut count: i64 = 0;

    loop {
        // k番目のlunlunNumberかの判定処理
        let previous_digit_num: i64 = queue.pop_front().unwrap();
        count += 1;
        if count == k {
            println!("{}", previous_digit_num);
            break;
        }
        // lunlunNumberの追加処理
        let basic_digit: i64 = previous_digit_num * 10;
        for i in 0..10 {
            let now_num: i64 = basic_digit + i;
            if is_lunlun_num(now_num) {
                queue.push_back(now_num);
            }
        }
    }
}


Measured memory_bytes: 6396
#include<bits/stdc++.h>
using  namespace std;
#define ll long long
int main()
{
    ll n,k;
    cin>>n>>k;
    ll a[k],i;
    for(i=0;i<k;i++)
        cin>>a[i];
    ll max1=n-a[k-1]+a[0];
    for(i=0;i<k-1;i++)
    {
        max1=max(max1,abs(a[i]-a[i+1]));
    }
    cout<<n-max1<<endl;


}


Measured memory_bytes: 1792
#include <iostream>
using namespace std;
int main(){
	 int n;
	 cin >> n;
	 long long sum=0;
	 for(int i = 1; i <= n; i++){
		if(i%3==0||i%5==0)continue;
		sum+=i;
	 }
	 cout << sum << endl;
	return 0;
}


Measured memory_bytes: 3536
use proconio::input;
use proconio::marker::{Chars, Usize1};
use std::iter::Iterator;
use std::collections::*;
use std::cmp::*;
use itertools::Itertools;

#[allow(unused_macros)]
macro_rules! max {
    ($x:expr) => {
      $x
    };
    ($x:expr, $($xs:tt)+) => {
      max($x,max!($($xs)+))
    };
  }
  
  #[allow(unused_macros)]
  macro_rules! min {
    ($x:expr) => {
      $x
    };
    ($x:expr, $($xs:tt)+) => {
      min($x,min!($($xs)+))
    };
  }

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn main() {
    input! {
    n: usize,
    }

let mut vec = vec![0; n + 1];

    for x in 1..100 {
      for y in 1..100 {
        for z in 1..100 {
           let res = x * x + y * y + z * z + x*y + y*z + z*x;
          if res <= n {
            vec[res] += 1;
          }
        }
      }
    }  

    for i in 1..=n {
      println!("{}" , vec[i]);
    }

}


Measured memory_bytes: 2128
n = gets.to_i
min = last = gets.to_i
max = 0
profits = []
(n-1).times{
  current = gets.to_i
  if (current <= last)
    profits<<(current-last)
    min = current if (current < min)
    max = 0
  end
  max = current if (current > last)
  profits<<(max-min) if (max != 0)
  last = current
}
puts profits.max

Measured memory_bytes: 10460
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;


// modint: mod 計算を int を扱うように扱える構造体
template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) v += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr istream& operator >> (istream &is, Fp<MOD>& x) noexcept {
        return is >> x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

const int MOD = 1000000007;
using mint = Fp<MOD>;


int N, M;
vector<int> S, T;
mint dp[2100][2100];

int main() {
    cin >> N >> M;
    S.resize(N), T.resize(M);
    for (int i = 0; i < N; ++i) cin >> S[i];
    for (int i = 0; i < M; ++i) cin >> T[i];

    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= M; ++j) {
            if (i-1 >= 0 && j-1 >= 0 && S[i-1] == T[j-1]) dp[i][j] += dp[i-1][j-1];
            if (i-1 >= 0) dp[i][j] += dp[i-1][j];
            if (j-1 >= 0) dp[i][j] += dp[i][j-1];
            if (i-1 >= 0 && j-1 >= 0) dp[i][j] -= dp[i-1][j-1]; // ダブルカウントを除く
        }
    }
    cout << dp[N][M] << endl;
}

Measured memory_bytes: 34688
MOD = 10**9 + 7

class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % MOD
            self.inv[i] = -self.inv[MOD % i] * (MOD // i) % MOD
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % MOD

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % MOD

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % MOD) % MOD

    def nhr(self, n, r):  # 重複組合せ: x_1 + ... + x_n = r
        return self.ncr(n + r - 1, n - 1)

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9 + 7
comb = Combination(N + 10)

A.sort()
ans = 0
for i, a in enumerate(A):
    mi = comb.ncr(N - i - 1, K - 1)
    mx = comb.ncr(i, K - 1)
    ans += (mx - mi) * a
    ans %= MOD
print(ans)


Measured memory_bytes: 19796
a = int(input())
b = int(input())
c = int(input())
x = int(input())
answer = 0

for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):
      if i*500 + j*100 + k*50 == x:
        answer += 1
        
print(answer)

Measured memory_bytes: 3060
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author champon
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 9e18
#define ceill(a, b) (a+b-1)/b
#define ok cout << "ok" << endl;
#define sp << " " <<
ll mod = 1e9+7;
void ans(bool b, ostream& out=cout){ out << (b ? "Yes" : "No") << endl; }
void ans2(bool b, ostream& out=cout){ out << (b ? "YES" : "NO") << endl; }
template<typename T> inline bool chmax(T &a, T b){ if(a<b){a=b; return true;} return false; }
template<typename T> inline bool chmin(T &a, T b){ if(b<a){a=b; return true;} return false; }
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val){fill((T*)array, (T*)(array+N), val);}
int dx[] = {1, 0, -1, 0, 1, -1, 1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, -1, 1};

#ifndef INCLUDE_DEBUG_HPP
#define INCLUDE_DEBUG_HPP

class debug
{
public:
    template<typename T> void vdeb(T vec);
    template<typename T1, typename T2> void adeb(T1 *arr, T2 n);
    template<typename T> void mdeb(T mp);
};

#endif //INCLUDE_DEBUG_HPP

template<typename T> void debug::vdeb(T vec)
{
    cout << "#vector set debug" << endl;
    for(auto vv : vec) cout << vv << " ";
    cout << endl;
}

template<typename T1, typename T2> void debug::adeb(T1 *arr, T2 n)
{
    cout << "#adebug" << endl;
    for(int i=0; i<=n; i++) cout << arr[i] << " ";
    cout << endl;
}

template<typename T> void debug::mdeb(T mp)
{
    cout << "#map pair debug" << endl;
    for(auto const& m : mp) cout << m.first sp m.second << endl;
}
debug dbg;

class BStoneMonument {
public:
	void solve(std::istream& in, std::ostream& out)
	{
	    int a, b;
	    in >> a >> b;
	    vector<int> h(999);
	    h[0] = 1;
	    for(int i=1; i<999; i++){
	        h[i] = h[i-1] + (i+1);
	    }

	    int hdiff = b-a;
	    out << h[hdiff-2] - a << endl;
	}
};


int main() {
	BStoneMonument solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL
    freopen("input.txt", "rt", stdin);
#endif

    const int MAX = 5;
    const int inf = 1e9;
    vector<int> vec(MAX);
    for (int i = 0; i < MAX; i++) {
        cin >> vec[i];
    }
    sort(vec.begin(), vec.end());
    int ans = inf;
    do {
        int time = 0;
        for (int i = 0; i < MAX; i++) {
            time += vec[i];
            if (i < MAX - 1) for (int j = 0; ; j += 10) {
                if (j >= time) {
                    time += j - time;
                    break;
                }
            }
        }
        ans = min(ans, time);
    } while (next_permutation(vec.begin(), vec.end()));
    
    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

using namespace std;
LL p = 1000000007ll;

int main(void)
{
  LL n,m;
  cin >> n >> m;
  vector<set<LL>> nei(n+1);
  REP(i,n-1) {
    LL a,b;
    cin >> a >> b;
    nei[a].insert(b);
    nei[b].insert(a);
  }
  queue<LL> q;
  q.push(1);
  while(!q.empty()) {
    LL pos = q.front();
    q.pop();
    for(auto x:nei[pos]) {
      q.push(x);
      nei[x].erase(pos);
    }
  }

  vector<LL> score(n+1);

  REP(i,m) {
    LL p, x;
    cin >> p >> x;
    score[p]+=x;
  }

  q.push(1);
  while(!q.empty()) {
    LL pos = q.front();
    q.pop();
    for(auto x:nei[pos]) {
      q.push(x);
      score[x]+=score[pos];
    }
  }

  REP(i,n) {
    if(i) cout << " ";
    cout << score[i+1];
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 33536