akhauriyash/Code-Regression huggingface dataset:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int v = Integer.parseInt(scan.next());
        int e = Integer.parseInt(scan.next());
        List<Edge> edgeList = new ArrayList<Edge>(e);
        for (int i = 0; i < e; i++) {
            int s = Integer.parseInt(scan.next());
            int t = Integer.parseInt(scan.next());
            int w = Integer.parseInt(scan.next());
            edgeList.add(new Edge(s, t, w));
        }
        scan.close();

        Collections.sort(edgeList, new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                if (o1.w != o2.w) {
                    return o1.w - o2.w;
                }
                if (o1.s != o2.s) {
                    return o1.s - o2.s;
                }
                return o1.t - o2.t;
            }
        });

        UnionFind uf = new UnionFind(v);
        long ans = 0;
        for (Edge edge : edgeList) {
            if (!uf.isSameParent(edge.s, edge.t)) {
                uf.union(edge.s, edge.t);
                ans += edge.w;
            }
        }

        System.out.println(ans);
    }

    static class Edge {
        int s;
        int t;
        int w;

        public Edge(int s, int t, int w) {
            this.s = s;
            this.t = t;
            this.w = w;
        }

    }

    static class UnionFind {
        int[] elements;

        public UnionFind(int elementsCount) {
            elements = new int[elementsCount];
            for (int i = 0; i < elementsCount; i++) {
                elements[i] = i;
            }
        }

        public void union(int x, int y) {
            elements[getParent(y)] = getParent(x);
        }

        public boolean isSameParent(int x, int y) {
            return getParent(x) == getParent(y);
        }

        public int getParent(int x) {
            int parent = elements[x];
            if (x != parent) {
                elements[x] = getParent(parent);
            }
            return elements[x];
        }
    }

}



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

using namespace std;

int main() {
  int m, k;
  scanf("%d %d", &m, &k);
  if (k == 0) {
    for (int i = 0; i < (1 << m); ++i)
      printf("%d %d ", i, i);
    return 0;
  }
  if (k >= (1 << m) || (m == 1 && k == 1)) {
    puts("-1");
    return 0;
  }
  printf("0 %d 0 ", k);
  for (int i = 1; i < (1 << m); ++i) {
    if (i != k)
      printf("%d ", i);
  }
  printf("%d ", k);
  for (int i = (1 << m) - 1; i >= 1; i--) {
    if (i != k)
      printf("%d ", i);
  }
  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>

using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>


ll n, ans = 0;
int main() {
	cin >> n;

	ll a[110], b[110];
	REP(i, n) {
		cin >> a[i];
		
	}
	REP(i, n) {
		cin >> b[i];
	}
	REP(i, n) {
		if (a[i] - b[i] > 0)ans += a[i] - b[i];
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> i_i;
typedef pair<ll, ll> l_l;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define int ll
//const ll mod = 1000000007;

int n, t;
vector<int> a;
int p, ng;
int sum;
int ans;

signed main() {
    cin >> n;
    for (int i=0;i<n;i++) {
        cin >> t; a.push_back(t);
        if (t > 0) p += t;
        else ng += t;
    }

    if (p == 0) {
        sort(a.begin(), a.end(), greater<int>());
        cout << -ng + 2*a.front() << endl;

        sum = a.front();
        for (int i=1;i<n;i++) {
            cout << sum << " " << a[i] << endl;
            sum -= a[i];
        }
    }
    else if (ng == 0) {
        sort(a.begin(), a.end());
        cout << p - 2*a.front() << endl;

        sum = a.front();
        for (int i=1;i<n-1;i++) {
            cout << sum << " " << a[i] << endl;
            sum -= a[i];
        }
        cout << a[n-1] << " " << sum << endl;
    }

    else {
        cout << p - ng << endl;

        sort(a.begin(), a.end());
        sum = a.back(); a.pop_back();
        while(a.back()>0) {
            cout << a.front() << " " << a.back() << endl;
            a.front() -= a.back();
            a.pop_back();
        }
        
        for (auto& it: a) {
            cout << sum << " " << it << endl;
            sum -= it;
        }
    }
}

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

using namespace std;

const int maxn=1e5+5;

char s[maxn];

int main(){
	scanf("%s",s);
	int k;
	scanf("%d",&k);
	int n=strlen(s);
	int flg=0;
	for(int i=1;i<n;i++){
		if(s[i-1]!=s[i]) flg=1;
	}
	if(!flg){
		printf("%lld",1ll*n*k/2);
	}
	else{
		if(s[0]==s[n-1]){
			int a=1,b=1;
			for(int i=1;i<n;i++){
				if(s[i]==s[i-1]){
					a++;
				}
				else break;
			}
			for(int i=n-2;i>=0;i--){
				if(s[i]==s[i+1]) b++;
				else break;
			}
			int tmp=0;
			for(int i=1;i<n;i++){
				if(s[i]==s[i-1]){
					s[i]='.';
					tmp++;
				} 
			}
			printf("%lld",1ll*tmp*k-1ll*(a/2+b/2-(a+b)/2)*(k-1));
		}
		else{
			int tmp=0;
			for(int i=1;i<n;i++){
				if(s[i]==s[i-1]){
					s[i]='.';
					tmp++;
				} 
			}
			printf("%lld",1ll*tmp*k);
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
#include <atcoder/all>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define ALL(v) v.begin(),v.end()
template < class T > inline bool chmax(T& a, T b) {if (a < b) { a=b; return true; } return false; }
template < class T > inline bool chmin(T& a, T b) {if (a > b) { a=b; return true; } return false; }
#define DEBUG_VLL(vec) for(int sz=0;sz<int(vec.size());sz++) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, d; cin >> n >> d;
    vll x(n), y(n);
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];

    atcoder::two_sat ts(2 * n);
    for (int i = 0; i < n; i++) {
        ts.add_clause(i, true, i + n, true);
        ts.add_clause(i, false, i + n, false);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            if (abs(x[i] - x[j]) < d) ts.add_clause(i, false, j, false);
            if (abs(x[i] - y[j]) < d) ts.add_clause(i, false, j + n, false);
            if (abs(y[i] - y[j]) < d) ts.add_clause(i + n, false, j + n, false);
        }
    }

    if (ts.satisfiable()) {
        cout << "Yes\n";
        V<bool> ans = ts.answer();
        for (int i = 0; i < n; i++) {
            if (ans[i]) cout << x[i] << '\n';
            if (ans[i + n]) cout << y[i] << '\n';
        }
    } else {
        cout << "No\n";
    }
    return 0;
}


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

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

typedef long long ll;
using namespace std;
int mod = 1000000007;

int main(void){
    int N;
    vector<int> ans;
    while(true){
        cin >> N;
        if(N == 0) break;
        int res = 0;
        int acc;
        for(int i = 1; i < N; i++){
            acc = 0;
            for(int j = i; acc < N; j++){
                acc += j;
            }
            if(acc == N) res++;
        }
        ans.push_back(res);
    }
    rep(i, ans.size()) cout << ans[i] << endl;
    return 0;
}


Measured memory_bytes: 3060
n, k = map(int, input().split())
A = list(map(int, input().split()))

b = [0 for _ in range(2001)]
in_range = 0

# 与えられたA内の転倒数 in_range
for i in A:
    in_range += sum(b[i+1:])
    b[i] += 1
    
# Aを二つつなげた時、それらの間
compare_to_another = 0
for i in A:
    compare_to_another += sum(b[i+1:])

# もとめるもの
answer = ( (in_range * k) + (compare_to_another * (k*(k-1))//2) ) % (10**9 + 7)
print(answer)

Measured memory_bytes: 41436
#include <stdio.h>

int main(void){
  int row, col, srow, scol;

  scanf("%d %d", &row, &col);
  scanf("%d %d", &srow, &scol);
  printf("%d\n", row*col-(srow*col+scol*row)+srow*scol);
  return 0;
}


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

using namespace std;

int main()
{
    int A, B, K, C;
    cin >> A >> B >> K;
    vector<int> v;

    C = max(A, B);

    for (int i = 1; i <= C; i++)
    {
        if (A % i == 0 && B % i == 0)
        {
            v.push_back(i);
        }
    }

    sort(v.begin(), v.end(), greater<>());

    cout << v[K - 1];
}

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

int main()
{
  int i,k,a,b,c;
  char number[3][100];

  i = 0;
  k = 0;
  while((c = getchar()) != EOF) {
    if(c == ' ') {
      k++;
      i = 0;
    }else{
      number[k][i] = c;
      i++;
    }
  }
  a = atoi(number[0]);
  b = atoi(number[1]);
  c = atoi(number[2]);

  if(a <= b) {
    if(b > c) {
      k = b;
      b = c;
      c = k;
    }
  }else{
    if(b >= c) {
      k = a;
      a = c;
      c = k;
    }else{
      if(a <= c) {
	k = a;
	a = b;
	b = k;
      }else{
	k = a;
	a = b;
	b = k;
	k = b;
	b = c;
	c = k;
      }
    }
  }
  printf("%d %d %d\n", a, b, c);
  
  return 0;
}

Measured memory_bytes: 524
#include <iostream>
    using namespace std;
    int main()
    {
        long a, b, c, x, y;
        long ans = 0;
        cin >> a >> b >> c >> x >> y;
        if(x <= y){
		    if(a+b>=2*c)
		        ans=2*c*x+min(b,2*c)*(y-x);
		    else
		        ans=a*x+b*y;
	    }else{
    		if(a+b>=2*c)
    		    ans=2*c*y+min(a,2*c)*(x-y);
		    else
		        ans=a*x+b*y;
	    }
        cout << ans << endl;
        return 0;
    }

Measured memory_bytes: 256
#include<iostream>

std::string judgeMagnitude(int a, int b);

int main()
{
	int a, b;
	std::string ans;

	std::cin >> a >> b;

	ans=judgeMagnitude(a, b);

	std::cout << ans << std::endl;

	return 0;
}

std::string judgeMagnitude(int a, int b)
{
	if (a < b)
	{
		return "a < b";
	}
	else if (a > b)
	{
		return "a > b";
	}
	else if (a == b)
	{
		return "a == b";
	}
}


Measured memory_bytes: 3148
import java.util.Scanner;
public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		long a = sc.nextLong();
		long b = sc.nextLong();
		
		long gcd = gcd(a,b);
		
		System.out.println(prime(gcd));

	}
	
	static long gcd(long a ,long b) {
		if(b > a)
			return gcd(b,a);
		if(a % b == 0)
			return b;
		
		return gcd(b ,a%b);
	}

	static long prime(long n) {
		
		long d = n;
		long count = 1;
		
		for(long i = 2 ; i* i <= d ; i++) {
			if(n % i == 0) {
				count++;
				while(n % i == 0) {
					n = n/i;
				}
			}
		}
		if(n != 1)
			count++;
		
		return count;
		}
}


Measured memory_bytes: 23508
#include <stdio.h>

int n ;
int p ;
int stack[15] ;

int main ( )
{
	p = 0 ;
	while ( scanf ( "%d" , &n ) == 1 ) {
		if ( n == 0 ) {
			printf ( "%d\n" , stack[p-1] ) ;
			p-- ;
		}
		else {
			stack[p++] = n ;
		}
	}
	return 0 ;
}

Measured memory_bytes: 1028
package main
import . "fmt"
func main() {
  var a,b,c,k,m,s int
  Scan(&a,&b,&c)
  Scan(&k)
  m = max(a,b,c)
  s = a+b+c
  for i:=0;i<k;i++ {
    s += m
    m *= 2
  }
  Println(s)
}
func max(n ...int) int {
  var m int = n[0]
  for _,i := range n {
    if m < i { m = i }
  }
  return m
}

Measured memory_bytes: 512
using System;

class Program
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        int a = int.Parse(input[0]);
        int b = int.Parse(input[1]);

        int k1, k2, k3, k4;
        k1 = (a + b) / 2;
        k2 = (a - b) / 2;
        k3 = -(a + b) / 2;
        k4 = -(a - b) / 2;

        int ans1 = Math.Abs(a - k1) - Math.Abs(b - k1);
        int ans2 = Math.Abs(a - k2) - Math.Abs(b - k2);
        int ans3 = Math.Abs(a - k3) - Math.Abs(b - k3);
        int ans4 = Math.Abs(a - k4) - Math.Abs(b - k4);
        if (ans1 == 0)
        {
            Console.WriteLine(k1.ToString());
        }
        else if (ans2 == 0)
        {
            Console.WriteLine(k2.ToString());
        }
        else if (ans3 == 0)
        {
            Console.WriteLine(k3.ToString());
        }
        else if (ans4 == 0)
        {
            Console.WriteLine(k3.ToString());
        }
        else
        {
            Console.WriteLine("IMPOSSIBLE");
        }

    }
}



Measured memory_bytes: 11220
#!/usr/bin/perl
<>=~/ (.+) /;
for($i=1;$i<=$`;$i++){
	$s=0;
	$j=$i;
	for(;$j;$j=int($j/10)){$s+=$j%10}
	if($1<=$s&&$s<=$'){$r+=$i}
}
print$r

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

using namespace std;

template<typename T>
class LazySegTree {
public:
    explicit LazySegTree(int n, T init, T def) : N(calcN_(n)), def(def) {
        mVal.assign(2*N+1, init);
        mLazy.assign(2*N+1, 0);
        mDirty.assign(2*N+1, 0);
    }
    void update(int l, int r, T value){
        updateImpl_(l, r, value, 0, 0, N);
    }
    T get(int l, int r){
        return getImpl_(l, r, 0, 0, N);
    }
private:
    int calcN_(int n){
        int res = 1;
        while(res < n) res *= 2;
        return res;
    }
    void updateImpl_(int l, int r, T value, int idx, int rangeL, int rangeR){
        eval_(idx, rangeL, rangeR);
        if(r <= rangeL || rangeR <= l) return;
        if(l <= rangeL && rangeR <= r){
            setLazy_(idx, value);
            eval_(idx, rangeL, rangeR);
        } else {
            int rangeM = (rangeL+rangeR)/2;
            updateImpl_(l, r, value, 2*idx+1, rangeL, rangeM);
            updateImpl_(l, r, value, 2*idx+2, rangeM, rangeR);
            mVal[idx] = operate_(mVal[2*idx+1], mVal[2*idx+2]);
        }
    }
    void setLazy_(int idx, T value){
        mLazy[idx] = value;
        mDirty[idx] = 1;
    }
    T getImpl_(int l, int r, int idx, int rangeL, int rangeR){
        if(r <= rangeL || rangeR <= l) return def;
        eval_(idx, rangeL, rangeR);
        if(l <= rangeL && rangeR <= r) return mVal[idx];
        int rangeM = (rangeL+rangeR)/2;
        T a = getImpl_(l, r, 2*idx+1, rangeL, rangeM);
        T b = getImpl_(l, r, 2*idx+2, rangeM, rangeR);
        return operate_(a, b);
    }
    void eval_(int idx, int rangeL, int rangeR){
        if(!mDirty[idx]) return;
        mVal[idx] = mLazy[idx];
        if(idx < N-1){
            setLazy_(2*idx+1, mLazy[idx]);
            setLazy_(2*idx+2, mLazy[idx]);
        }
        mLazy[idx] = 0;
        mDirty[idx] = 0;
    }
    T operate_(T a, T b) const { return min(a, b); }
    const int N;
    const T def;
    vector<T> mVal; 
    vector<T> mLazy;
    vector<int> mDirty;
};

int main(){
    int n, q;
    while(cin >> n >> q){
        LazySegTree<int> seg(n, 0x7FFFFFFF, 0x7FFFFFFF);
        for(int i=0;i<q;i++){
            int c; cin >> c;
            if(c == 0){
                int s, t, x; cin >> s >> t >> x;
                seg.update(s, t+1, x);
            } else {
                int s, t; cin >> s >> t;
                cout << seg.get(s, t+1) << endl;
            }
        }
    }
}



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

#define ll long long

using namespace std;
void sum(string &s, int pos, ll add, ll &ans){
	if(pos == s.size()){
		ans += add;
	}
	ll num = s[pos] - '0';
	ll ret = 0;
	for(int i = pos; i < s.size(); i++){
		sum(s, i + 1, add + num, ans);
		if(i + 1 < s.size()){
			num *= 10;
			num += (s[i + 1] - '0');
		}
	}
}


int
main(void){
	string s; cin >> s;
	ll ans = 0;
	sum(s, 0, 0, ans);
	cout << ans;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int Q,c,a,n,cnt,i;
	scanf("%d",&Q);
	for(i=0;i<Q;i++){
		cnt=0;
		scanf("%d %d %d",&c,&a,&n);
		while(1){
			if(c>0&&a>0&&n>0){
				cnt++;
				c--;
				a--;
				n--;
			}
			else{
				break;
			}
		}
		while(1){
			if(c>1&&a>0){
				cnt++;
				c-=2;
				a--;
			}
			else{
				break;
			}
		}
		while(1){
			if(c<3){
				break;
			}
			else{
				cnt++;
				c-=3;
			}
		}
		printf("%d\n",cnt);
	}
	return 0;
}

Measured memory_bytes: 1028
#include <bits/stdc++.h>
#include <vector>
#include <iostream>

using namespace std;

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

    vector<string> grid(h);

    for (int i = 0; i < h; i++)
        cin >> grid[i];

    vector<int> tate(h), yoko(w);
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (grid[i][j] == '#') {
                tate[i] = 1;
                break;
            }
            
        }
    }
    for (int i = 0; i < w; i++) {
        for (int j = 0; j < h; j++) {
            if (grid[j][i] == '#') {
                yoko[i] = 1;
                break;
            }
        }
    }

    for (int i = 0; i < h; i++) {
        if (tate[i]) {
            for (int j = 0; j < w; j++) {
                if (yoko[j])
                    cout << grid[i][j];
            }
            cout << endl;
        }
    }
}

Measured memory_bytes: 256
#include<algorithm>
#include <iostream>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<string>
using namespace std;
int main(){
    
    int h,w;
    cin>>h>>w;
    string s[50];
    for(int i=0;i<h;i++){
        cin>>s[i];
    }
    
    const int dx[8]={1,0,-1,0,1,-1,-1,1};
    const int dy[8]={0,1,0,-1,1,1,-1,-1};
    
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(s[i][j]=='#')continue;
            
            int num=0;
            for(int d=0;d<8;d++){
                const int ni=i+dx[d];
                const int nj=j+dy[d];
                
                if(ni<0 || h<=ni)continue;
                if(nj<0 || w<=nj)continue;
                if(s[ni][nj]=='#')num++;
                
            }
            s[i][j]=char(num+'0');
            
        }
    }
    
    for(int i=0;i<h;i++)cout<<s[i]<<endl;
        
    return 0;
}








Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 998244353;
ll mul(ll a, ll b){
    return ((a%mod) * (b%mod))%mod;
}
ll power(ll a, ll b){
    ll z = 1; ll x = a;
    while(b>0){
        if (b&1)z = mul(z, x);
        x = mul(x, x);
        b >>= 1;
    }
    return z;
}
int main()
{
    //dsgsd
    int n;
    cin>>n;
    map<string, int> m;
    m["AC"] = 0, m["WA"] = 0, m["TLE"] = 0, m["RE"] = 0;
    while(n--){
        string s;
        cin>>s;
        m[s]++;
    }
    cout<<"AC "<<"x "<<m["AC"]<<endl;
    cout<<"WA "<<"x "<<m["WA"]<<endl;
    cout<<"TLE "<<"x "<<m["TLE"]<<endl;
    cout<<"RE "<<"x "<<m["RE"]<<endl;
}


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

int main() {
  int H, W, D;
  cin >> H >> W >> D;
  vector<int> X(H * W + 1), Y(H * W + 1);
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      int A;
      cin >> A;
      X.at(A) = i;
      Y.at(A) = j;
    }
  }
  vector<int> d(H * W + 1);
  for (int i = 1; i <= H * W; i++) {
    if (i <= D) d.at(i) = 0;
    else d.at(i) = d.at(i - D) + abs(X.at(i) - X.at(i - D)) + abs(Y.at(i) - Y.at(i - D));
  }
  int Q;
  cin >> Q;
  for (int i = 0; i < Q; i++) {
    int L, R;
    cin >> L >> R;
    cout << d.at(R) - d.at(L) << endl;
  }
}

Measured memory_bytes: 4296
#include <iostream>
#include <vector>
#include <string.h>

#define N_MAX 9

#define B 100
#define W 200

using namespace std;

int f[N_MAX][N_MAX][N_MAX];
int dx[13]={1,0,0,1,1,0,-1,-1, 0,1,-1, 1, 1};
int dy[13]={0,1,0,1,0,1, 1, 0,-1,1, 1,-1, 1};
int dz[13]={0,0,1,0,1,1, 0, 1, 1,1, 1, 1,-1};

int main(void)
{
	int n,m,p;
	int i1,i2;
	int x,y,z;
	int xx,yy,zz;
	int color;
	int count;

	while(1){
		memset(f,0,sizeof(f));
		cin>>n>>m>>p;
		if(n+m+p==0) break;

		count=0;

		for(i1=0;i1<p;i1++){
			cin>>x>>y;

			if(count>=m) continue;
			else{

				for(z=1;z<=n;z++){
					if(f[y][x][z]==0) break; 
				}
				color=100*(i1%2+1);
				f[y][x][z]=color;
				
				for(i2=0;i2<13;i2++){
					count=1;
					xx=x+dx[i2];
					yy=y+dy[i2];
					zz=z+dz[i2];
					while(f[yy][xx][zz]==color) {
						xx+=dx[i2];
						yy+=dy[i2];
						zz+=dz[i2];
						count++;
					}
					xx=x-dx[i2];
					yy=y-dy[i2];
					zz=z-dz[i2];
					while(f[yy][xx][zz]==color) {
						xx-=dx[i2];
						yy-=dy[i2];
						zz-=dz[i2];
						count++;
					}
					if(count>=m) break;
				}

				if(count>=m) {
					if(color==B) cout<<"Black "<<i1+1<<endl;
					else cout<<"White "<<i1+1<<endl;
				}
			}	
		}
		if(count<m) cout<<"Draw"<<endl;
	}

		return 0;
}

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

int main(){
    int N, M;  cin >> N >> M;
    vector<tup> cities(M);
    for(int i=0; i<M; i++){
        int P, Y;  cin >> P >> Y;
        cities[i] = tup(Y, P, i);
    }
    sort(cities.begin(), cities.end());

    vector<int> nCity(N+1);
    vector<string> cityID(M);
    for(int i=0; i<M; i++){
        int p, num;
        p = get<1>(cities[i]);
        num = get<2>(cities[i]);

        nCity[p]++;
        string prefID = to_string(p);
        while(prefID.length() < 6) prefID = "0" + prefID;
        string numID = to_string(nCity[p]);
        while(numID.length() < 6) numID = "0" + numID;

        cityID[num] = prefID + numID;
    }

    for(int i=0; i<M; i++) cout << cityID[i] << endl;
}


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

using ll = long long;
const int N = 1e5+10;
const int oo = 2e9;
int n, a[N], dp[N];

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		a[i] = -a[i];
	}
	vector<int> dp;
	for(int i = 1; i <= n; i++) {
		auto it = upper_bound(dp.begin(), dp.end(), a[i]);
		if(it == dp.end()) dp.push_back(a[i]);
		else dp[it - dp.begin()] = a[i];
	}
	printf("%d\n", (int)dp.size());
	return 0;
}

Measured memory_bytes: 1276
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,len[N],a[N],pos[N];
int main(){
	scanf("%d",&n);
	for(int i=1; i<=n; ++i)scanf("%d",&a[i]),pos[a[i]]=i;
	len[1]=1;
	for(int i=2; i<=n; ++i)
		if(pos[i-1]<pos[i])
			len[i]=len[i-1]+1;
		else len[i]=1;
	int maxlen=0;
	for(int i=1; i<=n; ++i)maxlen=max(maxlen,len[i]);
	printf("%d",n-maxlen);
	return 0;
}

Measured memory_bytes: 2560
//#include "pch.h"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <limits.h>
#include <string>
#include <deque>
#include <cmath>

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

#define rip(i, n, s) for (int i = (s);i < (int)( n ); i++)
#define mpa make_pair
#define all(a) (a).begin(), (a).end()

int main(){
    int n;
    string s;
    cin >> n >> s;
    vector<int> da(n);
    rip(i,n,0){
        da[i] = s[i] - '0';
    }
    vector<int> li(1000);
    vector<int> ju(1000,3);
    rip(i,1000,0) li[i] = i;
    rip(i,n,0){
        rip(j,1000,0){
            if(da[i] == li[j] % 10){
                li[j] /= 10;
                ju[j] --;
            }
        }
    }
    int ans = 0;
    rip(i,1000,0){
        if(ju[i] < 1){
            ans ++;
        }
    }
    cout << ans << endl;
}

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

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

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
using namespace std;


int main(void){
    int n, l ;
    cin >> n >> l;
    VI vec(n);
    REP(i, n){
        vec.at(i) = l + i ;
    }
    REP(i, n){
        dump (vec.at(i));
    }
    
    int ta = 0;
    REP(i , n){
        ta += vec.at(i);
    }
    dump(ta);
    
    VI vec2(n);
    REP(i, n){
        int tb = 0;
        REP(j, n){
            if(j != i) tb +=vec.at(j); 
        }
        vec2.at(i) = tb;
    }
    REP(i, n){
        dump(vec2.at(i));
    }
    
    VI vec3(n);
    REP(i, n){
        vec3.at(i) = abs(ta - vec2.at(i));
    }
     REP(i, n){
        dump(vec3.at(i));
    }
    int k = distance(vec3.begin(), min_element(ALL(vec3)));
    dump(k);
    cout << vec2.at(k);

        return 0;
}

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

int main() {
  const int mod=1000000007;
  long alpha[26]={};
  int N;
  cin >> N;
  for(int i=0;i<N;i++){
    char c;
    cin >> c;
    alpha[c-'a']++;
  }
  long ans=1;
  for(int i=0;i<26;i++){
    ans=ans*(alpha[i]+1)%mod;
  }
  ans=(ans-1)%mod;
  cout << ans;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T, class T2> void smin(T& a, T2 val) {if (a > val) a = val;}template<class T, class T2> void smax(T& a, T2 val) {if (a < val) a = val;}
const int N = 5*(int)1e5 + 10;

int n, a;
long double b;

int32_t main(){_
   
   cin >> a >> b;

   long double x = a * b;
   
   cout<<(int)x;

   return 0;
}

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

using namespace std;

typedef long long llong;
typedef unsigned long long ullong;
#define inf 1ll<<60
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define fn fill_n
#define int llong
#define be(x) x.begin(), x.end()
typedef pair<int, int> P;


signed main(){
	int K, A, B;
	cin >> K >> A >> B;
	int a = 1+K;
	int b = 0;
	if(K >= A+1){
		b = B + (B-A)*((K-A-1)/2) + (K-A-1)%2;
	}

	cout << max(a,b) << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <string.h>
using namespace std;
typedef long long ll;

int main() {
    string s, t; cin >> s >> t;
    int a, b; cin >> a >> b;
    string u; cin >> u;
    if (s == u) a--;
    if (t == u) b--;
    cout << a << " " << b << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int) x.size()
#define cat(x) cerr << #x << " = " << x << endl
#define all(x) x.begin(), x.end()
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
 
using ll = long long;
using ld = long double;
using namespace std;

int n, a, x, cnt[30];

int main() {
	scanf ("%d", &n);
	rep(i, 1, n) {
		scanf ("%d", &a);
		x ^= a;
		cnt[__builtin_ctz(a)]++;
	}
	int ans = 0;
	per(i, 0, 29) {
		if (!((x >> i) & 1)) continue;
		if (!cnt[i]) return !printf ("-1\n");
		x ^= (1 << (i + 1)) - 1;
		ans++;
	}
	printf ("%d\n", ans); 
		
	return 0;
}


Measured memory_bytes: 3824
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

typedef long long llt;

const int MaxN = 10000 + 5, MaxD = 100 + 5;
const llt Mod = 1e9 + 7;

string K;
int N, D;
int A[MaxN];
llt dp[MaxN][MaxD][2];
bool vis[MaxN][MaxD][2];

void init() {
  cin >> K >> D;
  N = K.length();
  for (int i = 1; i <= N; ++i) A[i] = K[i - 1] - '0';
}

// 到了第 x 高位，数字和在模 D 意义下和为 d，是否有上限
llt dfs(int x, int d, int lim) {
  if (x > N) {
    if (d == 0) return 1;
    else return 0;
  }
  if (vis[x][d][lim] == true) return dp[x][d][lim];
  vis[x][d][lim] = true;

  if (lim == 0) {
    for (int i = 0; i <= 9; ++i) {
      int s = (d + i) % D;
      dp[x][d][lim] = (dp[x][d][lim] + dfs(x + 1, s, 0)) % Mod;
    }
  } else {
    for (int i = 0; i < A[x]; ++i) {
      int s = (d + i) % D;
      dp[x][d][lim] = (dp[x][d][lim] + dfs(x + 1, s, 0)) % Mod;
    }
    int s = (d + A[x]) % D;
    dp[x][d][lim] = (dp[x][d][lim] + dfs(x + 1, s, 1)) % Mod;
  }
  return dp[x][d][lim];
}

void solve() {
  llt ans = dfs(1, 0, 1);

  ans = ((ans - 1) % Mod + Mod) % Mod;
  cout << ans << endl;
}

int main() {
  init();
  solve();
  return 0;
}

Measured memory_bytes: 19584
n = int(input())
a = list(map(int,input().split()))

alice = 0
bob = 0
count = 1
while(count <= n):
    alice += max(a)
    index = a.index(max(a))
    del a[index]
    count += 1
    if(len(a) > 0):
        bob += max(a)
        index = a.index(max(a))
        del a[index]
        count += 1
    
print(alice - bob)


Measured memory_bytes: 3060
S = input()
threeS=""
flag=0
count=0
for s in S:
    if flag == 1:
        threeS = threeS + "3"
    elif s > "7":
        threeS = threeS + "3"
        flag=1
    elif s == "7":
        threeS = threeS + "3"
    elif s > "5":
        threeS = threeS + "2"
        flag=1
    elif s == "5":
        threeS = threeS + "2"
    elif s > "3":
        threeS = threeS + "1"
        flag=1
    elif s =="3":
        threeS = threeS + "1"
    else:
        if threeS == "":
            threeS = threeS + "0"
        else:
            threeS = threeS[0:-1] + str(max(0,int(threeS[-1:])-1))
            threeS = threeS + "3"
        flag=1

x=str(111)
count = 0

def add(s):
    if s == "":
        return "1"
    s = str( int(s)+1 )
    if s[-1:] == "4":
        s = add(s[:-1]) + "1"
    return s

while int(x) <= int(threeS):
    if "1" in x:
        if "2" in x:
            if "3" in x:
                count += 1
    x = add(x)

print(count)

Measured memory_bytes: 3064
#include "bits/stdc++.h"

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define ALL(v) v.begin(),v.end()
#define FOR(i, j, k) for(ll i=j;i<k;i++)
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cout<<v[i]<<" "

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<ll, ll> P;
typedef long double ld;
struct Edge{ll from, to, cost;};
struct node{ll cost, to;
  bool friend operator>(node a, node b){
    return a.cost>b.cost;
  }
};

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

ll modpow(ll a, ll n, ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

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

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}

ll N;
vector<P> A;
ll dp[3000][3000];

ll dpf(ll l, ll r){
  if(dp[l][r]>=0){
    return dp[l][r];
  }else{
    dp[l][r]=0;
    if(l == 0 and r == 0){
      return dp[l][r];
      /*}else if(r+l==N){
      if(l-1>=0)dp[l][r]=max(dp[l][r], dpf(l-1, r));
      if(r-1>=0)dp[l][r]=max(dp[l][r], dpf(l, r-1));
      */
    }else{
      P c = A[l+r-1];
      if(l-1>=0)dp[l][r]=max(dp[l][r], dpf(l-1, r)+abs(c.second-(l-1)) * c.first);
      if(r-1>=0)dp[l][r]=max(dp[l][r], dpf(l, r-1)+abs((N-1-(r-1))-c.second) * c.first);
    }
    return dp[l][r];
  }
}

/**************************************
** A main function starts from here  **
***************************************/
int main(){
  cin >> N;
  A = vector<P>(N);
  rep(i, N){
    ll a;
    cin >> a;
    A[i] = make_pair(a, i);
  }
  sort(ALL(A));
  reverse(ALL(A));
  fill(dp[0], dp[3000], -10);
  ll ans = 0;
  rep(i, N+1){
    ans = max(ans, dpf(i, N-i));
  }
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 74056
import sys,math,collections,itertools,copy
input = sys.stdin.readline

D,G=list(map(int,input().split()))
score = []
maxScore = []
maxS = []
for d in range(D):
    p,c=map(int,input().split())
    tmp = [(d+1)*100]*p
    tmp[-1]+=c
    score.append(tmp)
    maxScore.append(sum(tmp))
    maxS.append([p,sum(tmp)])

#-最大いくつの問題セットを必要とするか-#
maxScore.sort()
tmp = 0
for idx,mS in enumerate(maxScore):
    tmp += mS
    if tmp >= G:
        max_num = idx+1
        break
#-足し上げる-#
choice = set(range(1,D+1))
ans = float('inf')
for ch in itertools.permutations(choice,max_num):
    times = 0
    total = 0
    flag = 0
    for ci in ch:
        if total + maxS[ci-1][1] <G:
            total += maxS[ci-1][1]
            times += maxS[ci-1][0]
        else:
            for sc in score[ci-1]:
                total += sc
                times += 1
                if total >= G:
                    ans = min(ans,times)
                    falg = 1
                    break
    if flag ==1:
        break
print(ans)     


Measured memory_bytes: 74856
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m, x, y, k;
signed main() {
    scanf ("%d %d", &n, &m);
    x = 1, y = 1 + m;
    if (m & 1) {
        for (int i = 1; i <= m / 2 + 1; ++i)
            printf ("%d %d\n", x, y), ++x, --y;
        x = 2 + m, y = x + m - 1;
        for (int i = 1; i <= m / 2; ++i)
            printf ("%d %d\n", x, y), ++x, --y;
    }
    else {
        for (int i = 1; i <= m / 2; ++i)
            printf ("%d %d\n", x, y), ++x, --y;
        x = 2 + m, y = x + m - 1;
        for (int i = 1; i <= m / 2; ++i)
            printf ("%d %d\n", x, y), ++x, --y;
    }
    return 0;
}


Measured memory_bytes: 3688
m,d = map(int,input().split())
ans = 0

for i in range(m+1):
    for j in range(d+1):
        d1 = j % 10
        d10 = (j - d1) // 10
        if d1 >= 2 and d10 >= 2 and d1 * d10 == i:
            ans += 1

print(ans)


Measured memory_bytes: 2940
function Main(input) {
    var N = parseInt(input, 10);
    function hoge(hoge) {
        var hogehoge = hoge.toString().split('').map(n => parseInt(n, 10))
        return hogehoge.reduce((a, b) => a + b);
    }
    if(N % hoge(N) === 0) {
        console.log('Yes');
    } else{
        console.log('No');
    }
    }
Main(require('fs').readFileSync('/dev/stdin', 'utf8'));

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

int main(){
  int n,k,sum=0;
  cin>>n>>k;
  int a[n];
  rep(i,n){
    cin>>a[i];
    if(a[i]>=k)sum++;
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 640
import java.io.*;

class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        int A,B;
        String[] sb = str.split(" ");
        A = Integer.parseInt(sb[0]);
        B = Integer.parseInt(sb[1]);
        int ans;
        if (A > B){
            ans = 2 * A - 1;
        } else if (A < B) {
            ans = 2 * B - 1;
        } else {
            ans = 2 * A;
        }
        System.out.println(ans);
    }
}

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

#define ll long long

using namespace std;

int n, a[200000 + 2], b[200000 + 2];
int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b, b+n);
    for (int i = 0; i < n; ++i) {
        if (a[i] == b[n - 1])
            cout << b[n - 2];
        else
            cout << b[n - 1];
        cout << "\n";
    }

    return 0;
}


Measured memory_bytes: 3200
#include <stdio.h>
#include <string.h>
#include <math.h>

int bunkai(int);
int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};
int count[168]={};


int main(){
	int N;
	int k;
	long long ans=1;
	
	
	scanf("%d",&N);
	for(k=1;k<=N;k++){
		bunkai(k);
	}
	
	for(k=0;k<168;k++){
		if(count[k]!=0){
			ans=((ans*(count[k]+1))%1000000007);
		}
	}
	//ans=ans%1000000007;
	
	printf("%lld\n",ans);
	return 0;
}

int bunkai(int a){
	int i,j,n=0,power;
	for(i=0;i<168;i++){
		if(a%prime[i]==0){
			for(j=1;pow(prime[i],j)<=1000;j++){
				power=pow(prime[i],j);
				if((a%power)==0){
				count[i]++;
				}
			}
		}
	}
}



Measured memory_bytes: 256
n, x=gets.split.map(&:to_i)

if x==1 or x==n*2-1
  puts 'No'
  exit 0
else 
  puts 'Yes'
end

arr=(0..(n*2-1)).to_a
(-1..1).each do |j|
  i=arr.index(x+j)
  arr[n+j], arr[i]=arr[i], arr[n+j]
end

(1..(n*2-1)).each{|i| puts arr[i]}

=begin

def func(arr)
  if arr.size==1
    arr[0]
  else
    m, nex=arr.size, []
    (1...(m-1)).each do |i|
      med=[arr[i-1], arr[i], arr[i+1]].sort[1]
      nex.push(med)
    end
    func(nex)
  end
end

n=5
freq=Array.new(n*2, 0)
(1..(n*2-1)).to_a.permutation do |arr|
  # puts func(arr)
  freq[func(arr)]+=1
end

(1..(n*2-1)).each do |i|
  if freq[i]>0
    puts "#{i} : ok"
  else
    puts "#{i} : ng"
  end
end

=end

Measured memory_bytes: 4732
#include <iostream>

int main(void){
  int n;
  std::string s,t;
  std::cin >> n >> s >> t;

  int max_i = 0;
  for(int i=1; i<=n; i++){
    if(s.substr(n-i, i) == t.substr(0, i)){
      max_i = i;
    }
  }

  std::cout << n*2-max_i << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <limits>
#include <memory>
#include <queue>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

#define all(a) (a).begin(), (a).end()
#define sz(a) static_cast<int>((a).size())
#define fillchar(a, x) memset(a, x, sizeof(a))
#define rep(i, a, b) for(int i=int(a); i<=int(b); ++i)
#define irep(i, a, b) for(int i=int(a); i>=int(b); --i)
#define replr(i, a, b) rep(i, a, (b)-1)
#define reprl(i, a, b) irep(i, (b)-1, a)
#define repn(i, n) rep(i, 0, (n)-1)
#define irepn(i, n) irep(i, (n)-1, 0)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef vector<LL> VL;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<string> VS;
template<class T, class S> ostream& operator<<(ostream& os, const pair<T, S>& v) { return os<<"("<<v.first<<", "<<v.second<<")"; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& v) { os<<"["; repn(i, sz(v)) { if(i) os<<", "; os<<v[i]; } return os<<"]"; }
template<class T> bool setmax(T &_a, T _b) { if(_b>_a) { _a=_b; return true; } return false; }
template<class T> bool setmin(T &_a, T _b) { if(_b<_a) { _a=_b; return true; } return false; }
template<class T> T gcd(T _a, T _b) { return _b==0?_a:gcd(_b,_a%_b); }

const LL MOD=LL(1e9)+7;
const int N=900010;

LL m2[N], m3[N], inv[N], fac[N], inv_fac[N];

void pre() {
    m2[0]=m3[0]=1;
    rep(i, 1, N-1) {
        m2[i]=m2[i-1]*2%MOD;
        m3[i]=m3[i-1]*3%MOD;
    }
    inv[1]=1;
    rep(i, 2, N-1) inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
    fac[0]=inv_fac[0]=1;
    rep(i, 1, N-1) {
        fac[i]=fac[i-1]*i%MOD;
        inv_fac[i]=inv_fac[i-1]*inv[i]%MOD;
    }
}

LL binom(int n, int r) {
    if(r<0 || r>n) return 0;
    LL ans=fac[n]*inv_fac[r]%MOD*inv_fac[n-r]%MOD;
    return ans;
}

int cn, cs, ct;
LL cans;

LL query(int n, int s, int t) {
    while(cn<n) {
        cans=(cans*2+binom(cn, cs-1)-binom(cn, ct))%MOD;
        ++cn;
    }
    while(cs<s) cans=(cans-binom(cn, cs++))%MOD;
    while(cs>s) cans=(cans+binom(cn, --cs))%MOD;
    while(ct<t) cans=(cans+binom(cn, ++ct))%MOD;
    while(ct>t) cans=(cans-binom(cn, ct--))%MOD;
    cans=(cans+MOD)%MOD;
    return cans;
}

int main() {
    ios_base::sync_with_stdio(false);

    pre();
    int n, m, k; cin>>n>>m>>k; --n;

    cn=cs=ct=0, cans=1;
    LL ans=0;
    rep(p, 0, m+k) {
        LL cur=m3[m+k-p];
        (cur*=binom(n+p, n))%=MOD;
        (cur*=query(p, max(0,p-k), min(p,m)))%=MOD;
        (ans+=cur)%=MOD;
    }
    cout<<ans<<endl;

    return 0;
}


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

using i64 = int64_t;

int main(){
    int k, q;
    cin >> k >> q;
    vector<i64> d;
    for(int i=0;i<k;++i){
        i64 tmp;
        cin >> tmp;
        d.push_back(tmp);
    }
    for(int t=0;t<q;++t){
        i64 n, x, m;
        cin >> n >> x >> m;
        auto v = d;
        for(auto &e: v)e %= m;
        x %= m;
        i64 sum = x, equal = 0;
        for(i64 i=0;i<k;++i){
            if(v[i] == 0){
                equal += (n-1) / k;
                if(i < (n-1)%k)equal++;
            }
            sum += (n-1) / k * v[i];
            if(i < (n-1)%k)sum += v[i];
        }
        i64 large = sum / m - x / m;
        //cerr << sum << " " << large << " " << equal << endl;
        cout << (n-1) - large - equal << endl;
    }

    return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<utility>
#include<set>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<bitset>
#include<sstream>
#include<list>
#include<climits>

using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define nrep(i,i0,n) for(int i=(i0);i<(int)(n);++i)
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vii;
typedef long long ll;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;cin>>n;
	int minj=11;
	nrep(i,1,(int)sqrt(n)+10){
		if(n%i==0){
			ll t=n/i;
			int tmp=(int)log10(1.0*t)+1;
			minj=min(minj,tmp);
		}
	}
	cout<<minj<<endl;
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define double long double
#define int long long
#define mii map<int,int>
#define low lower_bound
#define upp upper_bound
#define inf 1000000007 //10^9+7
#define rep(i,n) for(int i=0;i<n;i++)
#define all(vec) vec.begin(),vec.end()
#define vsort(vec) sort(all(vec))
#define vrever(vec) reverse(all(vec));
#define vunsort(vec) vsort(vec); vrever(vec);
#define bisea binary_search
#define cend cout<<endl;
#define F first
#define S second
using namespace std;
signed main() {
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  cout<<b+c-d<<" "<<c+d-a<<" ";
  cout<<a+b-d<<" "<<b+c-a<<endl;
}

Measured memory_bytes: 256
/**
  * http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_2_C
  * 3 ????????°?????´???
  * ???????????´??°?????????????????????????????????????°??????????????????????????????????????????°?????????????????????????????????
  */
object Main {
  def main(args: Array[String]): Unit = {
    val seq = io.StdIn.readLine().split(" +").map(_.toInt).toSeq
    val answer = seq.sorted.mkString(" ")
    println(answer)
  }
}

Measured memory_bytes: 43752
using System;
using System.Linq;

namespace arc075_b
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] s = new int[n];
            for (int i = 0; i < n; i++)
            {
                s[i] = int.Parse(Console.ReadLine());
            }
            Array.Sort(s);
            if (s.Sum() % 10 != 0)
            {
                Console.WriteLine(s.Sum());
            }
            else
            {
                bool find = false;
                int i;
                for (i = 0; i < n && !find; i++)
                {
                    if (s[i] % 10 != 0) find = true;
                }
                Console.WriteLine(find ? s.Sum() - s[i - 1] : 0);
            }
        }
    }
}

Measured memory_bytes: 13268
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;


public class Main {
    static Scanner s = new Scanner(System.in);

    static class square {
        int width;
        int height;
        
        square(int width, int height) {
            this.width = width;
            this.height = height;
        }
    }

    public static void main(String[] args) {
        while (true) {
            int N = s.nextInt();
            if (N == 0) break;

            square[] data = new square[N];
            data[0] = new square(0, 0);
            int maxWidth=0;
            int minWidth=0;
            int maxHeight=0;
            int minHeight=0;

            for (int i = 1; i < N; i++) {
                int num = s.nextInt();
                int direction = s.nextInt();
                int width;
                int height;

                if (direction == 0) {
                    width = data[num].width - 1;
                    height = data[num].height;
                    data[i] = new square(width, height);
                    if(minWidth>width) minWidth=width;
                } else if (direction == 1) {
                    width = data[num].width;
                    height = data[num].height - 1;
                    data[i] = new square(width, height);
                    if(minHeight>height) minHeight=height;
                } else if (direction == 2) {
                    width = data[num].width + 1;
                    height = data[num].height;
                    data[i] = new square(width, height);
                    if(maxWidth<width) maxWidth=width;
                } else if (direction == 3) {
                    width = data[num].width;
                    height = data[num].height + 1;
                    data[i] = new square(width, height);
                    if(maxHeight<height) maxHeight=height;
                }
            }


            int ansWidth = maxWidth - minWidth + 1;
            int ansHeight = maxHeight - minHeight + 1;

            System.out.println(ansWidth + " " + ansHeight);
        }
    }


}

Measured memory_bytes: 34224