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

#define REP(i, n) for (ll (i) = 0 ; (i) < (ll)(n) ; ++(i))
#define REPN(i, m, n) for (ll (i) = m ; (i) < (ll)(n) ; ++(i))
#define REP_REV(i, n) for (ll (i) = (ll)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (ll (i) = (ll)(n) - 1 ; (i) >= m ; --(i))

#define INF             2e9
#define INF_LL          1LL<<60
#define ll              long long
#define Ceil(x, n)      (((((x))+((n)-1))/n))
#define CeilN(x, n)     (((((x))+((n)-1))/n)*n)
#define FloorN(x, n)    ((x)-(x)%(n))
#define ALL(x)          (x).begin(),(x).end()

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    vector<int> rank;
    vector<int> size; // size[i]: iが親なら連結成分の数
 
    UnionFind(int N) : par(N), rank(N), size(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) {par[i] = i; rank[i] = 0; size[i] = 1;}
    }
 
    int find(int x) { // データxが属する木の根を再帰で得る：find(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = find(par[x]);
    }
 
    void unite(int x, int y) { // xとyの木を併合
        int rx = find(x); //xの根をrx
        int ry = find(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
 
        // rank[rx] >= rank[ry] となるように rx と ry を swap
        if(rank[rx] < rank[ry]) swap(rx, ry);
 
        // 同じ高さだったならばまとめたことによって高さ +1
        if(rank[rx] == rank[ry]) ++rank[rx];
 
        par[ry] = rx; // root rx に ry の木をつなぐ
        size[rx] += size[ry];
        size[ry] = 0;
 
    }
 
    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = find(x);
        int ry = find(y);
        return rx == ry;
    }
 
    int get_size(int x){
        int rx = find(x);
        return size[rx];
    }
};

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> conv[m];

    UnionFind uf(n);

    REP(i, n) {
        int k;
        cin >> k;
        REP(j, k) {
            int gengo;
            cin >> gengo;
            gengo--;
            conv[gengo].push_back(i);
        }
    }

    REP(i, m) {
        //cout << conv[i].size() << endl;
    }

    REP(i, m) {
        if(conv[i].size() == 0) continue;
        REP(j, conv[i].size()-1) {
            if(!uf.same(conv[i][j], conv[i][j+1])) {
                uf.unite(conv[i][j], conv[i][j+1]);
            }
        }
    }

    if(uf.get_size(0) == n) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}

Measured memory_bytes: 4608
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	int k;
	cin>>k>>s;
	if(s.size()<=k){
		cout<<s;
		return 0;
	}else{
		for(int i=0;i<k;i++){
			cout<<s[i];
		}
	}cout<<"...";
	return 0;
} 

Measured memory_bytes: 3628
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);

		String s = sc.nextLine();

		int ans = Math.abs(Integer.parseInt(s.substring(0, 3))-753);
		for (int i=0; i<s.length()-2; i++) {
			ans = Math.min(ans, Math.abs(Integer.parseInt(s.substring(i,i+3))-753));
		}

		System.out.println(ans);
	}

}


Measured memory_bytes: 22736
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
struct node
{
	int x,y;
}a[100010];
int n,m;
int f[200010][2];
bool cmp(node x,node y)
{
	return x.x<y.x;
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d",&a[i].x,&a[i].y);
	}
	sort(a+1,a+m+1,cmp);
	for (int i=1;i<=m;i++)
	{
		int t=a[i].y;
		f[t][1]=max(f[t+1][1]+1,f[t][1]);
		f[t+1][0]=max(f[t][0]+1,f[t+1][0]);
	}
	printf("%d",f[1][0]+f[1][1]+1);
	for (int i=2;i<=n;i++)
	{
		printf(" %d",f[i][0]+f[i][1]+1);
	}
	printf("\n");
    return 0;
}


Measured memory_bytes: 5596
#include <iostream>

using namespace std;

#define int long long

const int N = 1e6 + 10, K = 1e2 + 10;

int dp[N], w[K], v[K];

int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);    
  int n, W; 
  cin >> n >> W;
  for (int i = 0; i < n; ++i) {
    cin >> w[i] >> v[i];
  }  
  for (int i = 1; i < N; ++i) {
    dp[i] = 1e15;
  }
  for (int i = 0; i < n; ++i) {
    for (int j = N - 1; j >= v[i]; --j) {
      dp[j] = min(dp[j], dp[j - v[i]] + w[i]);
    }
  }
  for (int i = N - 1; i >= 0; --i) {
    if (dp[i] <= W) {
      cout << i;
      break;
    }
  }
  return 0;
}


Measured memory_bytes: 11472
fun main(args: Array<String>) {
    val A = readInputLine().toInt()
    val B = readInputLine().toInt()

    if (A != 1 && B != 1) {
        println(1)
    } else if (A != 2 && B != 2) {
        println(2)
    } else {
        println(3)
    }
}

fun readInputLine(): String {
    return readLine()!!
}


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

int main(){
    char s[15];
    for(int i=0;i<4;i++) cin>>s[i];
    s[4]=' ';
    for(int i=5;i<13;i++) cin>>s[i];
    for(int i=0;i<13;i++) cout<<s[i];
    cout<<endl;
    return 0;
}


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

int main() {
  int i, h, w;
  cin >> h >> w;

  string s[101];
  for (i = 0; i < h; i++) {
    cin >> s[i];
  }
  for (i = 0; i <= w + 1; i++) {
    cout << '#';
  }
  cout << "\n";
  for (i = 0; i < h; i++) {
    cout << '#' << s[i] << '#' << "\n";
  }
  for (i = 0; i <= w + 1; i++) {
    cout << '#';
  }
  cout << "\n";
  return 0;
}

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

#define MAX


struct node{
  int key;
  struct node *right;
  struct node *left;
  struct node *parent;
};
  typedef struct node Node;
Node *root,*NIL;

void insert(int k){
  Node *y = NIL;
  Node *x = root;
  Node *z;

  z=(Node *)malloc(sizeof(Node));
  z->key =k;
  z->left = NIL;
  z->right = NIL;

  while(x != NIL){
    //leafのところまで探索
    y = x;
    if(z->key < x->key){
      x = x->left;
    }
    else{
      x = x->right;
    }
  }
  z->parent = y;
  //右に入るか左に入るかを考える
  if( y == NIL)root = z;
  else{
    if(z->key < y->key ){
      y->left=z;
    }
    else{
      y->right = z;
    }
  }       
}
void inorder(Node *u){ 
  if(u == NIL)return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}
void print(Node *u){
  if(u == NIL)return;
  printf(" %d",u->key);
  print(u->left);
  print(u->right);
}

Node *find(Node *x,int k){
  while(x != NIL && k != x->key){
    if(k < x->key)x = x->left;
    else x = x->right;
  }
  return x;
}


int main(){
  int i,j,n,k;
  char s[10];
  Node *t;
  
  scanf("%d",&n);
  for(i=0; i<n; i++){
    scanf("%s",s);
    if(s[0]=='i'){
      scanf("%d",&k);
      insert(k);
    }
    else if(s[0]=='p'){
      //print
      inorder(root);
      printf("\n");
      print(root);
      printf("\n");
    }
    else if(s[0]=='f'){
      //find
      scanf("%d",&k);
      t = find(root,k);
      if(t != NIL)printf("yes\n");
      else printf("no\n");
    }
  }
  return 0;
}




Measured memory_bytes: 20496
X, Y, A, B, C = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)

p = p[:X]
q = q[:Y]

all = p + q + r
all.sort(reverse=True)
ans = sum(all[:X + Y])
print(ans)


Measured memory_bytes: 103892
S = input()
N = len(S)
tmp = ['']
x = {'A', 'C', 'G', 'T'}
for i in range(N):
    for j in range(i, N):
        if set(S[i:j+1]) <= x:
            tmp.append(S[i:j+1])
print(max(map(len, tmp)))


Measured memory_bytes: 3060
import math


def main():
    A, B = list(map(int, input().split(' ')))
    price = 1
    answer = -1
    while True:
        tax_008 = math.floor(0.08 * price)
        tax_010 = math.floor(0.1 * price)
        if tax_008 > A or tax_010 > B:
            break
        if tax_008 == A and tax_010 == B:
            answer = price
            break
        price += 1
    print(answer)


if __name__ == '__main__':
    main()

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 10000000
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll> P;


int main(){
    int count=0;
    string s,t[200000];
    cin>>s;
    s.push_back('?');
    for(int i=0;i<(int)s.size();i++){
        if(s[i]=='A') t[count].push_back('A');
        else if(s[i]=='B' && s[i+1]=='C'){
            t[count].push_back('D');
            i++;
        }else count++;
    }
    int temp=0;
    ll ans=0;
    for(int i=0;i<count;i++){
        for(int j=0;j<(int)t[i].size();j++){
            if(t[i][j]=='A') temp++;
            else ans+=temp;
        }
        temp=0;
    }
    cout<<ans<<endl;

}


Measured memory_bytes: 5756
#include <bits/stdc++.h>
using namespace std;
string b[1000000];
bool cmp(string a, string b)
{
    return a < b;
}
int main()
{

    int n,l;
    cin >> n >> l;
    for(int i = 1;i <= n;++i)
        cin >> b[i];
    sort(b + 1,b + 1 + n,cmp);
    for(int i = 1;i <= n;++i)
        cout << b[i];
    return 0;
}

Measured memory_bytes: 8064
#include <iostream>
using namespace std;
typedef long long ll;

int main()
{
    ll x, k, d;
    cin >> x >> k >> d;
    x = abs(x);
    if(x / d >= k){
        cout << x - d * k << endl;
    }
    else{
        ll t = x / d;
        x -= d * t;
        k -= t;
        if(k % 2) cout << d - x << endl;
        else cout << x << endl;
    }
}


Measured memory_bytes: 3632
from collections import defaultdict
def main(n):
    S = list(input().split())
    d = defaultdict(int)
    d[0] = 0
    for num,s in enumerate(S):
        d[s] += 1
        di = sorted(d.items(), key=lambda x: x[1], reverse = True)
        if di[0][1] > di[1][1] + n - num - 1:
            print(di[0][0], num + 1)
            return
    print("TIE")
    return

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


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

#define range 524289
#define mod 1000000007
#define eps 1e-9
#define PI 3.14159265358979323846
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define ALL(V) V.begin(), V.end()
#define _ <<" "<<

using namespace std;

typedef  long long int ll;
typedef vector <ll> vi;
typedef vector<vi> vvi;
typedef pair <ll, ll> ii;
typedef pair<int, pair<int,int> > iii;
typedef vector<ii> vii;
typedef vector<iii> viii;


vi a;
vvi dp;
vi pre;

ll res;

ll cal(int i, int j){

    if(i==j){
        return 0;
    }
    if(dp[i][j]!=-1) return dp[i][j];
    ll minm = LONG_MAX;

    for(int k=i;k<j;k++){
        ll yoo = cal(i, k)+cal(k+1, j)+ pre[j]-pre[i-1];
        minm = min(yoo, minm);

    }

    return dp[i][j] = minm;
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	int t = 1;
	// cin>>t;
	while(t--){

        int n, k;
        cin>>n;
        a = vi(n+1);
        dp = vvi(n+1, vi(n+1, -1));
        res = 0;
        pre = vi(n+1);
        for (int i = 1; i <= n; ++i)
        {
            /* code */
            cin>>a[i];
            pre[i] = pre[i-1]+a[i];
        }

        cout<<cal(1, n)<<endl;





	}

    return 0;
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;

int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	
	int n; string s; cin >> n >> s;
	
	vector<int> v;
	for(int i = 1;i < n;i++){
		v.push_back(abs((int)(s[i] - s[i-1])));
	}
	
	reverse(v.begin(),v.end());
	bool hasOne = false;
	for(int x : v){
		if(x == 1) hasOne = true;
	}
	
	
	int dom = 1;
	if(hasOne) dom = 1;
	else dom = 2;
	
	for(int i = 0;i < (int) v.size();i++){
		if(hasOne){
			if(v[i] == 2) v[i] = 0;
		}
	}
	
	
	int ans = 0;
	for(int i = 0;i < (int) v.size();i++){
		if(v[i] != 0){
			if(((n-2) & i) == i){
				ans = 1 - ans;
			}
		}
	}
	
	cout << dom * ans;
	
	
}


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

int N;
int coin[12] = {59049, 46656, 7776, 6561, 1296, 729, 216, 81, 36, 9, 6, 1};
int dp[100000] = {0};
int result = INT_MAX;

void rec(int count = 0, int sum = 0){
    
    if(sum > N) return;
    if(count > result) return;
    if(sum == N){
        result = min(result, count);
        return;
    }
    
    if(dp[sum] != 0 && dp[sum] <= count) return;
    dp[sum] = count;
    
    for(int i = 0; i < 12; ++i){
        rec(count + 1, sum + coin[i]);
    }
    
    return;
}

int main(void){
    
    cin >> N;
    
    rec();
    
    cout << result << endl;
    
    return 0;
    
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
//using P = pair<int,int>;
//pow(x,n)
//cout << fixed << setprecision(桁数);
//string = to_string(数値)
//int = stoi(文字列)
//(int)(char-'0')
//string = itoa(int)
//円周率: M_PI

int main() {
    string s; cin>>s;
    if(s=="ABC") cout << "ARC" << endl;
    else cout << "ABC" << endl;
}





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

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

  int side = 1;

  for (int i = 2; i <= sqrt(N); i++) {
    if (N % i == 0) side = max(side, i);
  }

  cout << side - 1 + N / side - 1 << "\n";
}

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

long gcd(long x, long y);
long lcm(long x, long y);

int main() {
    long n, t, ans = 1;
    cin >> n;
    rep(i, n) {
        cin >> t;
        ans = lcm(ans, t);
    }
    cout << ans << endl;
}

long gcd(long x, long y) {
    if(x % y == 0) return y;
    else return gcd(y, x % y);
}

long lcm(long x, long y) {
    return x / gcd(max(x, y), min(x, y)) * y;
}

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

using namespace std;
using ll = long long;
 
#define rep(i, n)      for (int i = 0; i < (n); i++)
#define repr(i, n)     for (int i = (n) - 1; i >= 0; i--)
#define repe(i, l, r)  for (int i = (l); i < (r); i++)
#define reper(i, l, r) for (int i = (r) - 1; i >= (l); i--)
#define repi(i, l, r)  for (int i = (l); i <= (r); i++)
#define repir(i, l, r) for (int i = (r); i >= (l); i--)
#define range(a) a.begin(), a.end()
void initio() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }

int main() { initio();
  int M; cin >> M;
  vector<ll> D(M), C(M); rep(i, M) cin >> D[i] >> C[i];
  ll ans = 0;
  ll cur = 0;
  rep(i, M) {
    map<int, int> mp;
    vector<ll> val = {0};
    vector<ll> now;
    ll diff = 0;
    rep(j, C[i]) {
      now.push_back(cur);
      if (mp.count(cur)) {
        ll k = mp[cur];
        ll len = j - k;
        ans += (C[i] - j) / len * (val[j] - val[k]);
        ans += val[k + (C[i] - j) % len] - val[k];
        cur = now[k + (C[i] - j) % len];
        break;
      }
      mp[cur] = j;
      cur = cur * 10 + D[i];
      while (cur >= 10) {
        cur = cur / 10 + cur % 10;
        diff++;
      }
      val.push_back(diff);
    }
    ans += diff;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3456
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
#define maxn 5010
#define llg long long 
#define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
llg n,m;
bool f[maxn][maxn],bj[maxn][maxn];

inline int getint()
{
       int w=0,q=0; char c=getchar();
       while((c<'0' || c>'9') && c!='-') c=getchar(); if(c=='-') q=1,c=getchar(); 
       while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w;
}

bool dp(llg a,llg b)
{
	if (bj[a][b]) return f[a][b];
	bj[a][b]=1;
	for (llg i=1;i*2<=a;i++) 
		if (dp(a-i*2,b+i)==0)
		{
			f[a][b]=1;
			return 1;
		}

	for (llg i=1;i*2<=b;i++)
		if (dp(a+i,b-i*2)==0)
		{
			f[a][b]=1;
			return 1;
		}
	return 0;
}

int main()
{
//	yyj("B");
	bj[0][0]=1;
	llg a,b;
	cin>>a>>b;
	a%=1024,b%=1024;
	if (dp(a,b)) cout<<"Alice";else cout<<"Brown";
	return 0;
}


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

using namespace std;
using ll = long long;
using ld = long double;

//#define int long long
//signed main(){
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int r,g,b;
    cin >> r >> g >> b;
    if((g*10+b)%4) cout << "NO" << "\n";
    else cout << "YES" << "\n";

    return 0;
}

Measured memory_bytes: 3608
import std.algorithm;
import std.array;
import std.container;
import std.conv;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void calc(long[] a) {
    long[long] freq;
    foreach (x; a) freq[x]++;

    long sum = 0;
    foreach (v; freq.values) {
        sum += v * (v - 1) / 2;
    }

    foreach (x; a) {
        long v = freq[x];
        long prev = v * (v - 1) / 2;
        long curr = (v - 1) * (v - 2) / 2;
        writeln(sum - prev + curr);
    }
}

void main() {
    readint;
    auto a = reads!long;
    calc(a);
}

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;


Measured memory_bytes: 26512
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;

int binpow(int a, int b) {
    if (b == 0)
    {
        return 1;
    }
    ll res = binpow(a, b / 2);
    res*=res;
    if (b % 2)
    {
        return res * a;
    }
    return res;
}

ll gcd(ll a,ll b)
{
    if (b==0) return a;
    return gcd(b,a%b);
}
string to_upper(string a)
{
    for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
    return a;
}
 
string to_lower(string a)
{
    for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
    return a;
}

int firstDigit(int n)
{
    while (n>9)
    {
        n/=10;
    }
    return n;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    map<pair<int,int>,int> m;
    ll ans=0;
    int n,f;
    cin>>n;
    for (int i=1;i<=n;++i)
    {
        f=firstDigit(i);
        if (f==i%10)
        {
            ++ans;
        }
        ans+=(m[{i%10,f}])*2;
        //cout<<i<<" "<<m[{i%10,f}]<<"\n";
        ++m[{f,i%10}];
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using ll = long long;

int main() {
    ll n;
    std::string s;
    std::cin >> s;
    std::cin >> n;
    for (ll i = 0; i < n; i++) {
        if (s[i] != '1') {
            std::cout << s[i] << std::endl;
            return 0;
        }
    }
    std::cout << '1' << std::endl;
}


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

const int mod = 1000000007;

class mint {
    long long x;
public:
    mint(long long x=0) : x((x%mod+mod)%mod) {}
    mint operator-() const { 
      return mint(-x);
    }
    mint& operator+=(const mint& a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const  mint& a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint& a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res/=a;
    }

    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
};

// ll mod = 1e9+7;

ll solve1(vector<ll> A, ll N){
	ll sum=0;
	for(int i=0; i<N-1; i++){
		for(int j=i+1; j<N; j++){
			sum += (A[i]*A[j])%mod;
			sum %= mod;
		}
	}
	return sum;
}



int main(){
	ios::sync_with_stdio(false);
	
	ll N; cin>>N;
	vector<ll> A(N);
	rep(i,N) cin>>A[i];

	mint zyowa=0,  sum=0;
	for(int i=0; i<N; i++){
		zyowa += (A[i]*A[i])%mod;
		sum += A[i];
		//zyowa %= mod;
		//sum %= mod;
		// cerr << "zyowa: " << zyowa << endl;
		// cerr << "sum: " << sum << endl;
	}

	mint ans = (sum*sum);
	ans = (ans - zyowa);
	ans /= 2;
	cout << ans << endl;

	// cout << solve1(A,N) << endl;
}


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

void main()
{
    immutable nm = readln.chomp.split(" ").map!(to!int).array;
    immutable n = nm[0];
    immutable m = nm[1];

    auto nodes = new int[][n];

    foreach(_i; 0..m) {
        auto ab = readln.chomp.split(" ").map!(to!int).array;
        nodes[ab[0]-1] ~= ab[1]-1;
        nodes[ab[1]-1] ~= ab[0]-1;
    }

    int search(int pos, int[] hist)
    {
        auto nexts = nodes[pos].filter!(n => hist.find(n).empty);

        if (nexts.empty) {
            if (hist.length == n)
                return 1;
            else
                return 0;
        }

        return reduce!"a + b"(0, nexts.map!(node => search(node, hist ~ node)));
    }

    writeln(search(0, [0]));
}

Measured memory_bytes: 1276
#include <iostream>

using namespace std;

int N;

int main(){

    cin >> N;

    int A[N+1];
    for(int i=1; i<=N; i++){
        cin >> A[i];
    }

    int ans = true;
    int B[N+1];
    for(int i=1; i<=N; i++){
        B[i] = 0;
    }

    for(int i=N; i>0; i--){
        int j=2;
        int sum = 0;
        while(i*j <= N){
            sum += B[i*j];
            j++;
        }

        if((sum+1) % 2 == A[i]) B[i] = 1;
        if(sum % 2 == A[i]) B[i] = 0;

    }

    int M=0;
    for(int i=1; i<=N; i++){
        M += B[i];
    }

    cout << M << endl;
    for(int i=1; i<=N; i++){
        if(B[i] == 1) cout << i << " ";
    }

    return 0;
}

Measured memory_bytes: 2432
-- https://github.com/minoki/my-atcoder-solutions
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE BangPatterns #-}
import Control.Monad
import Data.Bits
import Data.Monoid
import qualified Data.ByteString.Builder as BSB
import System.IO

printEdge :: Int -> Int -> IO ()
printEdge !i !j = BSB.hPutBuilder stdout $ BSB.intDec i <> BSB.char7 ' ' <> BSB.intDec j <> BSB.char7 '\n'

main = do
  n :: Int <- readLn
  if n .&. (n-1) == 0 -- n = 2^k for some k
    then putStrLn "No"
    else do putStrLn "Yes"
            let m = bit (floor (logBase 2 (fromIntegral (n+1))))
            forM_ [1..m-2] $ \i -> do
              printEdge i (i+1)
            printEdge (m-1) (n+1)
            forM_ [1..m-2] $ \i -> do
              printEdge (n+i) (n+i+1)
            when (n >= m + 1) $ do
              printEdge 1 m
              printEdge m (m+1)
              printEdge 1 (n+m+1)
              printEdge (n+m+1) (n+m)
              when (n >= m + 2) $ do
                printEdge 2 (m+2)
                printEdge (n+m+1) (n+m+2)
                when (n >= m + 3) $ do
                  printEdge m (m+3)
                  printEdge 2 (n+m+3)
                  when (n >= m + 4) $ do
                    printEdge m (n+m+4)
                    printEdge 4 (m+4)
                    forM_ [m+5..n] $ \i -> do
                      printEdge (i-1) (n+i)
                      printEdge (i-m) i


Measured memory_bytes: 3452
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

vector<int> adj[51];
int p[51][2], vis[51], d[51], c;

#define ll long long

void dfs(int v) {
    vis[v] = 1;
    for (int u:adj[v]) {
        if (vis[u]) continue;
        d[u] = d[v] + 1, p[u][0] = v, p[u][1] = c++;
        dfs(u);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, u, v;
    cin >> n;
    for (int i = 1; i < n; i++) {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) vis[i] = 0;
    p[1][0] = 0, c = 1, d[1] = 0;
    dfs(1);

    cin >> m;
    int pp[m][2];
    for (int i = 0; i < m; i++) cin >> pp[i][0] >> pp[i][1];
    ll res = (1ll << (n - 1));
    int s[n], cnt;
    for (int i = 1; i < (1 << m); i++) {
        memset(s,0, sizeof(s));
        cnt = n - 1;
        for (int j = 0; j < m; j++) {
            if (i & (1 << j)) {
                u = pp[j][0], v = pp[j][1];
                while (d[u] > d[v]) {
                    if (s[p[u][1]] == 0) s[p[u][1]] = 1, cnt--;
                    u = p[u][0];
                }
                while (d[v] > d[u]) {
                    if (s[p[v][1]] == 0) s[p[v][1]] = 1, cnt--;
                    v = p[v][0];
                }
                while (u != v) {
                    if (s[p[u][1]] == 0) s[p[u][1]] = 1, cnt--;
                    u = p[u][0];
                    if (s[p[v][1]] == 0) s[p[v][1]] = 1, cnt--;
                    v = p[v][0];
                }
            }
        }
        if (__builtin_popcount(i) & 1) res -= (1ll << cnt);
        else res += (1ll << cnt);
    }
    cout << res << "\n";
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mem(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define lp(k,a) for(int k=1;k<=a;k++)
#define lp0(k,a) for(int k=0;k<a;k++)
#define lpn(k,n,a) for(int k=n;k<=a;k++)
#define lpd(k,n,a) for(int k=n;k>=a;k--)
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d %d",&a,&b)
#define ll unsigned long long
#define MAX 100000
#define maxn 100100

using namespace std;

int n,m,top,pre[maxn];
ll dis[maxn];
bool vis[maxn];
queue<int>q;

int Q,K;

struct Side
{
    int to,next;
    ll w;
}side[200100];

void add(int u,int v,ll w)
{
    side[top]=(Side){v,pre[u],w};
    pre[u]=top++;
}

void spfa(int S)
{
    mem(vis);
    mem1(dis);
    q.push(S);
    dis[S]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=false;
        for(int i=pre[u];~i;i=side[i].next)
        {
            int v=side[i].to;
            if(dis[u]+side[i].w<dis[v] || dis[v]==-1)
            {
                dis[v]=dis[u]+side[i].w;
                if(!vis[v])
                {
                    vis[v]=true;
                    q.push(v);
                }
            }
        }
    }
}

int main()
{
   // freopen("in.txt","r",stdin);
    cin>>n;
    n--;
    int u,v; ll w;
    top=0;
    mem1(pre);
    while(n--)
    {
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    cin>>Q>>K;
     spfa(K);
     int x,y;
     while(Q--)
     {
         cin>>x>>y;
         cout<<dis[x]+dis[y]<<endl;
     }

    return 0;
}


Measured memory_bytes: 6144
input = require("fs").readFileSync("/dev/stdin", "utf8").trim();
input = input.split('\n');
function abs(x){
  if (x > 0){
    return x;
  }
  else{
    return -x;
  }
}
let n = parseInt(input[0]);
input[1] = input[1].split(' ');
a = new Int32Array(n);
for (i=0;i<n;i++){
  a[i] = input[1][i];
}
if (n < 3){
  console.log(0);
}
else{
  cnt = 0;
  for (i=0;i<n-2;i++){
    for (j=i+1;j<n-1;j++){
      for (k=j+1;k<n;k++){
        if (a[k] < a[i] + a[j] && a[k] > abs(a[i] - a[j])){
          if (a[i] != a[j] && a[j] != a[k] && a[k] != a[i]){
            cnt += 1;
          }
        }
      }
    }
  }
  console.log(cnt);
}

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

using namespace std;

int main(void)
{
	int n;
	cin >> n;
	vector<int> cities;
	long long ans = 0;
	for (int i = 0; i < n + 1; ++i)
	{
		int a;
		cin >> a;
		cities.push_back(a);
	}
	for (int i = 0; i < n; ++i)
	{
		int a;
		cin >> a;
		if (cities[i] >= a)
		{
			ans += a;
			cities[i] -= a;
		}
		else
		{
			ans += cities[i];
			a -= cities[i];
			if (cities[i + 1] >= a)
			{
				ans += a;
				cities[i + 1] -= a;
			}
			else
			{
				ans += cities[i + 1];
				cities[i + 1] = 0;
				//a -= cities[i + 1];
			}
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 892
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

int n,m,a[105],Odd;

void work()
{
	scanf("%d %d",&n,&m);
	for (int i=1; i<=m; i++)  scanf("%d",&a[i]);
	if (m==1)
		{
			printf("%d\n",a[1]);
			if (a[1]==1)  printf("1\n1");
			else  printf("2\n%d 1",a[1]-1);
			return;
		}
	if (m==2)
		{
			printf("%d %d\n",a[1],a[2]);
			if (a[1]==1)  printf("1\n%d",n);
			else  printf("2\n%d %d",a[1]-1,a[2]+1);
			return;
		}
	for (int i=1; i<=m; i++)  Odd+=(a[i]&1);
	if (Odd>2)  {puts("Impossible");  return;}
	for (int i=1; i<=m; i++)
		if (a[i]&1)
			swap(a[i],(a[1]&1)?a[m]:a[1]);
	for (int i=1; i<=m; i++)  printf("%d ",a[i]);  puts("");
	a[1]++,a[m]--;
	if (a[m]==0)  m--;
	printf("%d\n",m);
	for (int i=1; i<=m; i++)  printf("%d ",a[i]);
}

int main()
{
	work();
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner $ = new Scanner(System.in);
		int N = $.nextInt(), K = 0;
		String S = $.next(), s = "";
		K = $.nextInt();
		s = S.substring(K - 1, K);
		for (int i = 0; i < N; i++){
			String Judge = S.substring(i, i + 1);
			if (Judge.equals(s))  System.out.print(Judge);
			else System.out.print("*");
		}
		System.out.println();
		/*
		5 error 2 -> *rr*r
		6 eleven 5 -> e*e*e*
		9 education 7 -> ******i**
		*/
	}
}


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

using namespace std;
#define ll long long
#define cinf(n,x) for(int i=0;i<(n);i++) cin >> x[i];
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
const ll mod = 1e9 + 7;

int main (){
    
    int n;
  	cin >> n;
    int count = 0;
    REP(i,n){
      	ll a;
		cin >> a;
        if(a % 2 == 1) count++;
        
        
    }

    if(count % 2 == 0){
        cout << "YES" << endl;
    }else cout << "NO" <<endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define repr(i, n) for (int i = (int)n - 1; i >= 0; --i)
#define ALL(a) (a).begin(), (a).end()
using ll = long long;
using Graph = vector<vector<int>>;
const ll mod = 1e9 + 7;
const ll INF = 1e9;

int main() {
  int n;
  cin >> n;
  vector<int> x(n);
  rep(i, n) cin >> x[i];
  sort(ALL(x));
  int ans = 100000000;
  rep(i, x[n - 1] + 1) {
    int tmp = 0;
    rep(j, n) { tmp += abs(i - x[j]) * abs(i - x[j]); }
    ans = min(ans, tmp);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#pragma region template
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long MOD = 1e9 + 7, MAX = LLONG_MAX, larg = 1e5, INF = -1e9;
long long A, B, C, D, E, F, G, H, I, J, K, L, N, M, O, P, Q, R, S, T, U, V, W;
typedef long long ll;
typedef pair<ll, ll> Pa;
typedef pair<Pa, ll> info;

int main() {
    cin >> N;
    string s;
    cin >> s;
    ll cnt = 0;
    rep(i, N-1){
        if(s[i+1] == 'E') cnt++;
    }
    ll ans = cnt;
    rep(i, N-1){
        if(s[i] == 'W') cnt++;
        if(s[i+1] == 'E') cnt--;
        ans = min(ans, cnt);
    }
    cout << ans;
}


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

using namespace std;

int main(){
	int n;
	cin>>n;
	vector<int> stick(n);
	priority_queue<int> hoge;

	for(int i=0;i<n;i++) cin>>stick.at(i);

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

	int cnt=1;
	int now=stick.at(0);

	for(int i=1;i<n;i++){
		if(stick.at(i)==now) cnt++;
		else cnt=1;
		now=stick.at(i);

		if(cnt==2){
			hoge.push(now);
			cnt=0;
		}
	}

	if(hoge.size()<2){
		cout<<0<<endl;
		return 0;
	}

	long long one=hoge.top();
	hoge.pop();
	long long two=hoge.top();

	cout<<one*two<<endl;

	return 0;
}


Measured memory_bytes: 1024
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<ll>>;
ll t = 0;
Graph g;
vector<pair<ll, ll>> seen(110);
bool dfs(const Graph G, ll v){
    t++;
    if(!seen[v].first) seen[v].first = t;

    for(auto next_v : G[v]){
        if(seen[next_v].first) continue;
        dfs(G,next_v);
        t++;
    }
    seen[v].second = t + 1;
}

int main(){
    ll n; cin >> n;
    Graph g(n);
    for (ll i = 0; i < n; i++){
        ll k; cin >> k;
        ll v; cin >> v;
        for (ll j = 0; j < v; j++){
            ll u; cin >> u;
            g[k-1].push_back(u-1);
        }
    }
    for (ll i = 0; i < n; i++){
        for (ll j = 0; j < g[i].size(); j++){
        }
    }
    

    for (ll i = 0; i < n; i++){
        seen[i].first = 0;
        seen[i].second = 0;
    }

    for (ll i = 0; i < n; i++) {
        if(!seen[i].first) {
            dfs(g, i);
            t++;
        }
    }

    for (ll i = 0; i < n; i++){
        printf("%lld %lld %lld\n", i+1, seen[i].first, seen[i].second);
    }

    return 0;
}


Measured memory_bytes: 4260
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <map>
#include <set>
#include <math.h>
#include <ctype.h>
#include <string.h>
#include <string>
#include <stdlib.h>
#include <queue>
#include <limits.h>
using namespace std;

typedef long long ll;

const int N = 1e5;
int n, dp[N][3], a[N][3];

int main(int argc, char **argv) {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < 3; ++j)
			scanf("%d", &a[i][j]);
	for (int j = 0; j < 3; ++j)
		dp[0][j] = a[0][j];
	for (int i = 1; i < n; ++i)
		for (int j = 0; j < 3; ++j)
			for (int k = 0; k < 3; ++k)
				if (j != k)
					dp[i][j] = max(dp[i][j], dp[i - 1][k] + a[i][j]);
	int res = 0;
	for (int j = 0; j < 3; ++j)
		res = max(res, dp[n - 1][j]);
	printf("%d\n", res);
	return 0;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long  int a,b,c,d,e,f,g,h,j,i;
    cin>>a;
    cin>>b>>c;
    if(a>=c)
    {
        a-=c;
     
   cout<<a<<" "<<b<<endl;
   return 0;
    }
    else
    {
        c-=a;
        a-=a;


        if(b>=c)
        {
            b-=c;
            cout<<a<<" "<<b<<endl;
            return 0;
        }
        else
        {
            cout<<"0"<<" "<<"0"<<endl;
            return 0;
        }
    }


}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define LiangJiaJun main
using namespace std;
int x,a,b;
int LiangJiaJun(){
	cin>>x>>a>>b;
	if(a>=b) return puts("delicious"),0;
	if(b>a&&b<=x+a) return puts("safe"),0;
	puts("dangerous");
	return 0;
}

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

using namespace std;

int N, A, B, C;
vector < int >l;

int ans = INT_MAX;

int calc(vector < int >v)
{
	int mp = 0;
	pair < int, int >p[4];
	for (int i = 0; i < 4; i++) {
		// count and length
		p[i] = make_pair(0, 0);
	}

	for (int i = 0; i < N; i++) {
		p[v[i]] = make_pair(p[v[i]].first + 1, p[v[i]].second + l[i]);
	}

	// only A, B, C
	for (int i = 0; i < 3; i++) {
		if (p[i].first == 0) {
			// cannot make from nothing
			return INT_MAX;
		} else {
			mp += (p[i].first - 1) * 10;
		}
	}
	mp += abs(p[0].second - A);
	mp += abs(p[1].second - B);
	mp += abs(p[2].second - C);

	return mp;
}

void dfs(vector < int >v)
{
	if (v.size() == (size_t) N) {
		int mp = calc(v);
		if (mp < ans) {
			ans = mp;
		}
	} else {
		for (int i = 0; i < 4; i++) {
			vector < int >vv = v;
			vv.push_back(i);
			dfs(vv);
		}
	}
}

int main()
{
	cin >> N >> A >> B >> C;

	for (int i = 0; i < N; i++) {
		int size;
		cin >> size;
		l.push_back(size);
	}

	dfs(vector < int >());

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int Inf = 1000000000;
constexpr ll INF= 1000000000000000000;
constexpr ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<int,int> P;

template<typename T>
T Pow(T a,T b) {
    T ret = 1;
    for(int i = 0;i < b;i++) {
        ret *= a;
    }
    return ret;
}
 
ll mod(ll val) {
    ll res = val % MOD;
    if(res < 0) {
        res += MOD;
    }
    return res;
}
 
ll RS(ll N, ll P, ll M){
    if(P==0) return 1;
    if(P < 0) {
        return 0;
    }
    if(P%2==0){
        ll t = RS(N, P/2, M);
        return t*t % M;
    }
    return N * RS(N, P-1, M) % M;
}

int main() {
    int X,N;
    cin >> X >> N;
    map<int,int> ma;
    for(int i = 0;i < N;i++) {
        int A;
        cin >> A;
        ma[A]++;
    }
    int ret = -100;
    int ret2 = Inf;
    for(int i = -1000;i <= 1000;i++) {
        if(!ma.count(i) && abs(i - X) < ret2) {
            ret = i;
            ret2 = abs(X - i);
        }
    }
    cout << ret << endl;
}

Measured memory_bytes: 3636
package main

import "fmt"
//import "sort"
func main() {
    

    a := make([]float64, 3)
    for i := 0; i < 3; i++ {
      fmt.Scan(&a[i])
    }
    // sort.Ints(a)
    
    fmt.Println( (a[0] + a[1]) * a[2] / float64(2) )
    
}

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

#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999

using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

int iy[]={0, 0, 1, -1};
int ix[]={1, -1, 0, 0};

int n;
unsigned long long int ans, x[100010], a, b;

int main(){
	cin >> n >> a >> b;
	for(int i=0;i<n;i++){
		cin >> x[i];
	}
	for(int i=0;i<n-1;i++){
		ans += min((x[i+1]-x[i])*a, b);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int INT_INF = 1 << 30;
#define MOD 1000000007LL
#define endl "\n"

ll modbeki(ll x, ll n){
  ll res = 1LL;
  while(n > 0){
    if(n & 1){
      res *= x % MOD;
      res %= MOD;
    }
    x = x * x % MOD;
    n >>= 1;
  }
  return res % MOD;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n, k;
  cin >> n >> k;

  vll fact(2*n+1), ifact(2*n+1);
  fact.at(0) = 1LL;
  for(int i = 1; i <= 2*n; i++){
    fact.at(i) = fact.at(i-1) * i % MOD;
  }
  for(int i = 1; i <= 2*n; i++){
    ifact.at(i) = modbeki(fact.at(i), MOD-2);
  }
  auto ncr = [&](ll a, ll b){
    if(b == a || b == 0) return 1LL;
    return fact.at(a) * ifact.at(a-b) % MOD * ifact.at(b) % MOD;
  };
  auto nhr = [&](ll a, ll b){
    return ncr(a+b-1, b);
  };

  if(k >= n-1){
    cout << nhr(n+1, n-1) << endl;
    return 0;
  }
  if(k == 1){
    cout << ncr(n, 1LL) * ncr(n-1LL, 1LL) << endl;
    return 0;
  }
  ll ans = 0LL;
  for(int i = 0; i <= k; i++){
    ans += ncr(n, i) * nhr(n-i, i) % MOD;
    ans %= MOD;
  }
  cout << ans << endl;
}

Measured memory_bytes: 6528
//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
using ll=long long;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=1e9;
const ll INF=1e18;
using P=pair<int,int>;
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  ll n,m,ans=0,cnt,x[1005]={},y[1005]={},z[1005]={},a[1005]={};
  cin >> n >> m;
  for(int i=0; i<n; i++) {
    cin >> x[i] >> y[i] >> z[i];
  }
  for(int i=0; i<(1<<3); i++) {
    cnt=0;
    for(int j=0; j<n; j++) {
      a[j]=x[j]*(i&1?1:-1)+y[j]*(i&2?1:-1)+z[j]*(i&4?1:-1);
    }
    sort(a,a+n,greater<ll>());
    for(int j=0; j<m; j++) {
      cnt+=a[j];
    }
    ans=max(ans,cnt);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define INF 1<<28
#define MAX 100005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

typedef long long ll;

int main()
{
    FASTIO
   /* 
   double start_time = clock();
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
  #endif
    */
    int n,a,b,c,d;
    cin >> n;
    a = b = 0;
    cin >> c;
    d = c;

    for(int i = 1; i < n; i++)
        {
          int x;
          cin >> x;
          a = min(a+abs(x-c), b + abs(x - d));
          swap(a,b);
          c = d;
          d = x;
        }
        cout << b << "\n";

    // double end_time = clock();
  //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
   
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
using P = pair<int, int>;
const int INF = 1e9;
const long long LINF = 1e18;
const long long MOD = 1e9 + 7;

signed main(){
    int h,n;
    cin >> h >> n;
    int a[n],b[n];
    rep(i,n){
        cin >> a[i] >> b[i];
    }
    vector<vector<ll>> dp(n + 1, vector<ll>(h + 1, LINF));
    rep(i,n){
        dp[i][0] = 0;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= h; j++){
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j]);
            int k = min(h, j + a[i]);
            dp[i + 1][k] = min(dp[i + 1][k], dp[i + 1][j] + b[i]);
        }
    }
    cout << dp[n][h] << endl;
    return 0;
}

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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define UB upper_bound
#define LB lower_bound
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

int n, k, d[10];

bool f(int v) {
	while(v) {
		inc(i, k) {
			if(v % 10 == d[i]) { return false; }
		}
		v /= 10;
	}
	return true;
}

int main() {
	cin >> n >> k;
	inc(i, k) { cin >> d[i]; }
	
	int ans = -1;
	incII(i, n, 99999) {
		if(f(i)) { ans = i; break; }
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 256
S = str(input())

if S == "SUN":
    print(7)
elif S == "MON":
    print(6)
elif S == "TUE":
    print(5)
elif S == "WED":
    print(4)
elif S == "THU":
    print(3)
elif S == "FRI":
    print(2)
else:
    print(1)


Measured memory_bytes: 2940
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		
		char[][] s = new char[N][];
		for(int i=0; i<N; i++)
			s[i] = sc.next().toCharArray();
		
		int ab = 0;
		int headB = 0;
		int tailA = 0;
		int headBtailA = 0;
		
		for(int i=0; i<N; i++) {
			if(s[i][0]=='B') {
				if(s[i][s[i].length-1]=='A')
					headBtailA++;
				else
					headB++;
			} else if(s[i][s[i].length-1]=='A') {
				tailA++;
			}
			
			for(int j=0; j<s[i].length-1; j++) {
				if(s[i][j]=='A' && s[i][j+1]=='B') {
					ab++;
					j++;
				}
			}
		}
		
		if(headBtailA>=1) {
			ab += headBtailA-1;
			if(tailA>=1) {
				tailA--;
				ab++;
			}
			if(headB>=1) {
				headB--;
				ab++;
			}
		}
		ab += Math.min(headB, tailA);
		System.out.println(ab);
		
		sc.close();
	}
}


Measured memory_bytes: 30032
s = gets.chomp.to_i
a = [s]
1000.times do |i|
  if s % 2 == 0
    s /= 2
    a.each do |j|
      if j == s
        puts i + 2
        exit
      end
    end
  else
    s = 3 * s + 1
    a.each do |j|
      if j == s
        puts i + 2
        exit
      end
    end
  end
  a << s
end


Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;
//const int mod = 998244353;

struct UnionFind
{
    int num;
    vector<int> r, p;
    UnionFind() {}
    UnionFind(int n) : num(n), r(n, 1), p(n, 0) { iota(p.begin(), p.end(), 0); }
    int find(int x)
    {
        return (x == p[x] ? x : p[x] = find(p[x]));
    }
    bool same(int x, int y)
    {
        return find(x) == find(y);
    }
    void unite(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
            return;
        if (r[x] < r[y])
            swap(x, y);
        r[x] += r[y];
        p[y] = x;
        num--;
    }
    int size(int x)
    {
        return r[find(x)];
    }
    int count() const
    {
        return num;
    }
};

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

    int n, k, l;
    cin >> n >> k >> l;
    UnionFind uf1(n);
    rep(i, k)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        uf1.unite(a, b);
    }
    UnionFind uf2(n);
    rep(i, l)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        uf2.unite(a, b);
    }
    vector<P> v(n);
    rep(i, n) v[i].first = uf1.find(i);
    rep(i, n) v[i].second = uf2.find(i);
    sort(all(v));
    map<P, int> mp;
    rep(i, n) mp[v[i]]++;
    rep(i, n)
    {
        P p = {uf1.find(i), uf2.find(i)};
        cout << mp[p] << " ";
    }
    cout << endl;
}

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


int main() {
  int n,m,A,B,num;
  cin>>n>>m;
  vector<int> H(n);
  vector<int> ans(n,1);
  
  rep(i,n){
    cin>>H[i];
  }
  
  rep(i,m){
    cin>>A>>B;
    if(H[A-1]>H[B-1])
      ans[B-1]=0;
    if(H[A-1]<H[B-1])
      ans[A-1]=0;
    if(H[A-1]==H[B-1]){
      ans[B-1]=0;
      ans[A-1]=0;
    }
  }
  
  int cnt=0;
  rep(i,n){
    if(ans[i]==1)
      cnt++;
      
  }
 
  cout<<cnt<<endl;
    
  
 
    
  
  
}

Measured memory_bytes: 4052
n=int(input())
l=[]
for i in range(1,n+1):
    s,p=input().split()
    p=int(p)
    l.append((s,p,i))
l.sort(key=lambda x:x[1], reverse=True)
l.sort(key=lambda x:x[0])

for i in range(n):
    print(l[i][2])



Measured memory_bytes: 3060