akhauriyash/Code-Regression huggingface dataset:
// http://algorithms.blog55.fc2.com/blog-entry-66.html

#include <iostream>
using namespace std;
#include <stdio.h>

#define MAX 100
#define INFTY (1 << 21)

int SIZE;
int R[MAX + 2];
int C[MAX+1][MAX+1]; // cost table
int B[MAX+1][MAX+1]; // best table

void compute(){
    for ( int i = 1; i <= SIZE; i++ )
    for ( int j = 1; j <= SIZE; j++ ) C[i][j] = INFTY;
    
    for ( int i = 1; i <= SIZE; i++ ) C[i][i] = 0;
    
    for ( int j = 1; j <= SIZE - 1; j++ ){
        for ( int i = 1; i <= SIZE - j; i++ ){
            for ( int k = i + 1; k <= i + j; k++ ){
                // C[i][i+j] = min( C[i][i+j], 
                //                  C[i][k-1] + C[k][i+j] + R[i]*R[k]*R[i+j+1]);
                int cost = C[i][k-1] + C[k][i+j] + R[i]*R[k]*R[i+j+1];
                if ( cost < C[i][i+j] ){
                    C[i][i+j] =  cost;
                    B[i][i+j] = k;
                }
                
            }
        }
    }
}

void order( int i, int j ){
    if ( i == j ) cout << "M" << i;
    else{
        cout << "(";
        order( i, B[i][j]-1 ); order(B[i][j], j);
        cout << ")";
    }
}

void input(){
    cin >> SIZE;
	int z,i=1;
    for (; i <= SIZE; i++ ) cin >> R[i]>>z;
	R[i]=z;
	//SIZE++;
}

void output(){
    cout <<  C[1][SIZE] << endl;
    //order(1, SIZE);
    //cout << endl;
}

main(){
    input();
    compute();
    output();
}

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

#define FOR(i,a,n) for(int i = (a); i < (n); ++i)
#define REP(i,n) FOR(i,0,n)
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)

#define max 8001

bool dpx[max/2][2*max];
bool dpy[max/2][2*max];

int main() {
  string s; cin >> s;
  int n = s.size();
  vector<int> x, y; x.push_back(0); y.push_back(0);
  int cnt = 0; bool flag = true;
  REP(i, n) {
    if (s[i]=='T') {
      if(flag) x.push_back(cnt);
      else y.push_back(cnt);
      cnt = 0; flag = !flag;
    } else cnt++;
  }
  if(flag) x.push_back(cnt);
  else y.push_back(cnt);

  dpx[0][max] = true;
  dpx[1][max+x[1]] = true;
  n = x.size();
  FOR(i, 2, n) FOR(j, 0, 2*max) dpx[i][j] = dpx[i-1][j-x[i]] || dpx[i-1][j+x[i]];

  dpy[0][max] = true;
  n = y.size();
  FOR(i, 1, n) FOR(j, 0, 2*max) dpy[i][j] = dpy[i-1][j-y[i]] || dpy[i-1][j+y[i]];
  
  int gx, gy;
  cin >> gx >> gy;
  gx+=max; gy+=max;
  if(dpx[x.size()-1][gx] && dpy[y.size()-1][gy]) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

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

long long ggd(long long number1,long long number2){
	long long m = number1;
	long long n = number2;

	if(number2 > number1){
		m = number2;
		n = number1;
	}
    long long r = n % m;
	while(r != 0){
        n = m;
        m = r;
        r = n % m;
	}

	return m;
}

long long lcm(long long number1,long long number2){
	return number1 * number2 / ggd(number1,number2);	
}

int main() {
    int N;
    cin >> N;
    vector <long> A(N);
    long long sum_ggd;
    for(int i = 0; i < N; i++)
        cin >> A[i];
    sort(A.begin(), A.end());
    vector <long> ggd_list(N), ggd_rlist(N);
    ggd_list[0] = A[0];
    ggd_rlist[N - 1] = A[N - 1];
    for(int i = 1; i < N; i++)
        ggd_list[i] = ggd(ggd_list[i - 1], A[i]);

    for(int i = N - 2; i >= 0; i--)
        ggd_rlist[i] = ggd(ggd_rlist[i + 1], A[i]);

    long max_ggd = ggd(A[N - 1], ggd_rlist[1]);
    for(int i = 1; i < N - 1; i++)
    {
        long a = ggd(ggd_list[i - 1], A[N - 1]);
        a = ggd(a, ggd_rlist[i + 1]);
        max_ggd = max(max_ggd, a);
    }

    long a = ggd_list[N - 2];
    max_ggd = max(max_ggd, a);


    cout << max_ggd << endl;
    return 0;  

}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int n,m;
    string s;
    while(cin>>n>>m){
        int arr[30]={0};
        int n2=0,n1=0;
        for(int i=0;i<n;i++){
            cin>>s;
            for(int j=0;j<m;j++){
                arr[s[j]-'a']++;
            }
        }
        for(int i=0;i<26;i++){
            if(arr[i]%4==1){
                n1++;
            }
            else if(arr[i]%4==2){
                n2++;
            }
            else if(arr[i]%4==3){
                n1++;n2++;
            }
        }
        int oc=0,tc=0;
        if((n&1)&&(m&1)){
            oc=1;
            tc=n/2+m/2;
        }
        else if(n&1){
            tc=m/2;
        }
        else if(m&1){
            tc=n/2;
        }
        if(n1<=oc&&n2<=tc){
            cout<<"Yes"<<endl;
        }
        else{
            cout<<"No"<<endl;
        }
    }
}


Measured memory_bytes: 256
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
using namespace std;
#define testcase(t) int t;cin>>t;for(int testcnt=1;testcnt<=t;testcnt++)
#define int long long
#define double long double
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define endl "\n"
#define pb push_back
#define eb emplace_back
bool sortbysec(const pair<int,int> &a,
              const pair<int,int> &b)
{
    return (a.second < b.second);
}
int nod(int n)
{
	string s = to_string(n);
	return (int)s.length();
}
int sod(int n)
{
	int ans = 0;
	while(n)
	ans+=(n%10),n/=10;
	return ans;
}
int modexpo(int x,int y,int p)
{
	int res=1;
	x%=p;
	while(y){
		if(y&1)
		res*=x,res%=p;
		x*=x,x%=p;
		y>>=1;
	}
	return res;
}
int a[100005],b[100005],c[100005];
int dp[100005][3];
int32_t main()
{
	IOS
	int n,k;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i]>>b[i]>>c[i];
	dp[0][0]=a[0],dp[0][1]=b[0],dp[0][2]=c[0];
	for(int i=1;i<n;i++)
	{
		dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i];
		dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i];
		dp[i][2]=max(dp[i-1][1],dp[i-1][0])+c[i];
	}
	cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
}

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

const long long INF = static_cast<long long>(1e18) + 1LL;

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main()
{
    long long N = 0, K = 0;
    cin >> N >> K;

    vector<long long> A(N, 0);
    for (size_t i = 0; i < N; i++)
    {
        cin >> A[i];
    }

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

    long long res = 0;

    long long left = -INF, right = INF;
    while (left + 1 < right)
    {
        long long center = (left + right) / 2, x = 0;
        for (size_t i = 0; i < N; i++)
        {
            if (A[i] < 0)
            {
                long long l = -1, r = N;
                while (l + 1 < r)
                {
                    long long c = (l + r) / 2;
                    if (A[i] * A[c] < center)
                    {
                        r = c;
                    }
                    else
                    {
                        l = c;
                    }
                }
                x += (N - r);
            }
            else
            {
                long long l = -1, r = N;
                while (l + 1 < r)
                {
                    long long c = (l + r) / 2;
                    if (A[i] * A[c] < center)
                    {
                        l = c;
                    }
                    else
                    {
                        r = c;
                    }
                }
                x += r;
            }

            if (A[i] * A[i] < center)
            {
                x--;
            }
        }
        x /= 2;

        if (x < K)
        {
            left = center;
        }
        else
        {
            right = center;
        }
    }

    cout << left << endl;

    return 0;
}


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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int k, n;
	cin >> k >> n;
	vector<int> a(n);
	for(int& x : a) cin >> x;
	int ans = k;
	
	for(int i = 0; i < n; i++) {
		int L = a[(i - 1 + n) % n], R = a[(i+1)%n];
		ans = min({ans, k - (a[i] - L + k) % k, k - (R - a[i] + k) % k});
	}
	
	cout << ans << endl;
}


Measured memory_bytes: 1024
def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]

    max_value = max(A)
    max_index = A.index(max_value)

    for i in range(N):
        if i != max_index:
            print(max_value)
        else:
            if i == 0:
                print(max(A[1:]))
            elif i == N - 1:
                print(max(A[: N - 1]))
            else:
                print(max(max(A[:i]), max(A[i + 1 :])))

    return


if __name__ == "__main__":
    main()


Measured memory_bytes: 14068
package main

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

func main() {
	D, G := ReadInt(), ReadInt()
	p := make([]int, D)
	c := make([]int, D)
	for i := 0; i < D; i++ {
		p[i], c[i] = ReadInt(), ReadInt()
	}
	min := 1 << 62
	for i := 0; i < D; i++ {
		for j := 0; j <= p[i]; j++ {
			for S := 0; S < 1<<D; S++ {
				score := j * (i + 1) * 100
				if j == p[i] {
					score += c[i]
				}
				cnt := j
				for k := 0; k < D; k++ {
					if S>>k&1 == 1 && k != i {
						score += p[k]*(k+1)*100 + c[k]
						cnt += p[k]
					}
				}
				if score >= G {
					if cnt < min {
						min = cnt
					}
				}
			}
		}
	}
	fmt.Println(min)
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


Measured memory_bytes: 1876
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
typedef long long ll;
const int INF = 100000000, mod = 1000000007;
using namespace std;

int main() {
    ll n, m;
    cin >> n >> m;
    ll x[n], y[m], xsum = 0, ysum = 0;
    for (int i = 0; i < n; i++) {
        cin >> x[i];
        xsum += (i*x[i] - (n - 1 - i)*x[i]) % mod;
        xsum %= mod;
    }
    for (int i = 0; i < m; i++) {
        cin >> y[i];
        ysum += (i*y[i] - (m - 1 - i)*y[i]) % mod;
        ysum %= mod;
    }
    cout <<(xsum*ysum) % mod << endl;
    return 0;
}

Measured memory_bytes: 1792
x1,y1,x2,y2 = [int(x) for x in input().split()]

A=x2-x1
B=y2-y1

x3 = x2 - B
y3 = y2 + A

x4 = x1 - B
y4 = y1 + A


print(x3,y3,x4,y4)


Measured memory_bytes: 2940
n = int(input())
s = [0 for i in range(n)]
for i in range(n):
    s[i] = input()
m = int(input())
t = [0 for i in range(m)]
for i in range(m):
    t[i] = input()

sum_max = 0
for i in range(n):
    sum_tmp = 0
    for j in range(n):
        if s[i] == s[j]:
            sum_tmp += 1
    for j in range(m):
        if s[i] == t[j]:
            sum_tmp -= 1
    if sum_tmp > sum_max:
        sum_max = 0
        sum_max += sum_tmp
print(sum_max)


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

int main() {
  int A,B; cin >> A >> B;
  if ( A == 1 && B != 1 ) cout << "Alice" << endl;
  else if (A != 1 && B == 1 ) cout << "Bob" << endl;
  else if ( A > B ) cout << "Alice" << endl;
  else if ( A < B ) cout << "Bob" << endl;
  else cout << "Draw" << endl;
  return 0;
}


Measured memory_bytes: 256
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pii = pair<int,pi>;

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int> vd={-n,+1,+n,-1};
    vector<bool> seki(n*n,true);
    ll ans=0;
    int p;
    vector<int> dp(n*n,n*n);
    for(int i = 0;i < n;++i) {
        for(int j = 0;j < n;++j) {
            dp[i*n+j]=min(i,dp[i*n+j]);
            dp[(n-1-i)*n+j]=min(i,dp[(n-1-i)*n+j]);
        }
    }
    for(int j = 0;j < n;++j) {
        for(int i = 0;i < n;++i) {
            dp[j*n+i]=min(i,dp[j*n+i]);
            dp[j*n+(n-1-i)]=min(i,dp[j*n+(n-1-i)]);
        }
    }
    int pp=-1;
    for(int i = 0;i < n*n;++i) {
        cin>>p;
        --p;
        ans+=dp[p];
        deque<pi> deq;
        --dp[p];
        deq.emplace_front(dp[p],p);
        int tans;
        while(!deq.empty()) {
            auto t=deq.front();
            deq.pop_front();
//cerr<<p<<" "<<t.first<<" "<<t.second<<endl;
            for(int i = 0;i < 4;++i) {
                int np=t.second+vd[i];
                int res=t.second%n;
                int nc=t.first;
                if(np<0||n*n<=np||(res==n-1&&i==1)||(res==0&&i==3)) {
                    continue;
                }
                if(seki[np])++nc;
                if(dp[np]<=nc)continue;
                dp[np]=nc;
                if(seki[np]) {
                    deq.emplace_back(nc,np);
                }
                else deq.emplace_front(nc,np);
            }
        }
        eol:;
        seki[p]=false;
    }
    cout<<ans<<"\n";
    return 0;
}


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

typedef long long int ll;
ll MOD = 1000000007;
ll INFL = 1ll << 60;
ll INF = 1 << 30;

int main() {
  ll n, m;
  cin >> n >> m;
  ll a, b;
  vector<pair<ll, ll> > v(n);
  for (int i = 0; i < n; i++) {
    cin >> a >> b;
    v[i] = make_pair(a, b);
  }
  sort(v.begin(), v.end());
  ll ans = 0;
  int i = 0;
  while (m) {
    if (v[i].second == 0) {
      i++;
    } else {
      ans += v[i].first;
      m--;
      v[i].second--;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 1792
#include <iostream>
#include <map>
#include <algorithm>
using namespace std; typedef long long ll; const int INF=1e9+7;
typedef pair<ll,ll> P;

int main() {
  int n; cin>>n;
  ll a[n],b[n]; for(int i=0;i<n;i++) cin>>a[i]>>b[i];

  ll an=0;
  for(int i=n-1;i>=0;i--) {
    an += ((b[i] - (a[i] + an))%b[i] + b[i]) %b[i];
  }
  cout<<an<<endl;
}

Measured memory_bytes: 1792
using System;

namespace AtCoder
{
    class Program
    {
        static void Main()
        {
            var line = Console.ReadLine();
            var n = int.Parse(line);

            var h = n / 3600;
            var m = (n % 3600) / 60;
            var s = n % 60;
            
            Console.WriteLine("{0}:{1}:{2}", h, m, s);
        }
    }
}



Measured memory_bytes: 17988
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<int, P> E;
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	b += MOD;
	a += b;
	a %= MOD;
}

vector<ll> v;

ll st[100100]={0ll},ss[100100]={0ll};

int main(void){
	int n,q,i,s,t;
	ll a,x,l,r,m,ans;
	bool flag;
	cin >> n >> q;
	for(i=0; i<n; ++i){
		cin >> a;
		st[i+1] = st[i] + a;
		if(i%2){
			ss[i+1] = ss[i] + a;
		}else{
			ss[i+1] = ss[i];
		}
		v.push_back(a);
	}
	for(i=0; i<q; ++i){
		cin >> x;
		l = 0ll; r = INF;
		flag = false;
		while(r-l){
			m = (l+r)/2;
			if(flag){
				m = r;
				l = r;
			}else if(r-l==1ll){
				m = l;
				flag = true;
			}
			s = (int)(lower_bound(v.begin(),v.end(),x-m)-v.begin());
			t = (int)(lower_bound(v.begin(),v.end(),x+m)-v.begin());
			if(t<n && v[t]==x+m){
				++t;
				if(t-s==n-t){
					ans = st[n]-st[t]+max(st[s]-ss[s],ss[s]);
					break;
				}else if(t-s+1==n-t){
					ans = st[n]-st[t]+min(st[s]-ss[s],ss[s]);
					break;
				}
				--t;
			}
			if(t-s==n-t){
				ans = st[n]-st[t]+max(st[s]-ss[s],ss[s]);
				break;
			}else if(t-s+1==n-t){
				ans = st[n]-st[t]+min(st[s]-ss[s],ss[s]);
				break;
			}else if(t-s>n-t){
				r = m;
			}else{
				l = m;
			}
		}
		cout << ans << endl;
	}
	return 0;
}


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

int main() {
  int X, Y, Z;
  cin >> X >> Y >> Z;
  
  int P = X / (Y + Z);
  int R = X % (Y + Z);
  
  cout << (R >= Z ? P : P - 1) << endl;
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll ans;
int a[610001],i,j,k,n,m;
int main(){
	scanf("%d",&n);
	for (i=1;i<=3*n;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+3*n);
	for (ans=0,i=1;i<=n;i++) ans+=a[3*n-2*i+1];
	printf("%lld\n",ans);
	return 0;
}

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

int main()
{
    int N; cin >> N;
    string s;
    map<string, int> mp;

    decltype(mp)::iterator it;
    for (int i = 0; i < N; i++) {
        cin >> s;
        if (mp.count(s) == 0) mp[s] = 1;
    }
    
    cout << mp.size() << endl;
}

Measured memory_bytes: 19236
n = gets.to_i

pre_minnumber = gets.to_i
ans_max = -Float::INFINITY

(n-1).times do
    y = gets.to_i
    if ans_max < (y-pre_minnumber)
        ans_max = y - pre_minnumber
    end
    if pre_minnumber > y
        pre_minnumber = y
    end
end

puts ans_max


Measured memory_bytes: 8904
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
 
int main() {
    int N;
    string S;
    cin >> N >> S;
    string abc = "ABC";

    int cnt = 0;
    rep(i,S.length()-2){
        if(S.at(i) == abc.at(0) && S.at(i+1) == abc.at(1) && S.at(i+2) == abc.at(2)){
            cnt++;
        }
    }

    cout << cnt << endl;
}

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) begin(v),end(v)
using ll = long long;

int main() {
  string s;cin>>s;
  bool ans=true;
  if(s[0]!='A')ans=false;
  int cnt=0;
  for(int i=2;i<s.size()-1;i++){
    if(s[i]=='C')cnt++;
  }
  if(cnt!=1)ans=false;
  int a=0;
  rep(i,s.size()){
    if(s[i]>='a')a++;
  }
  if(s.size()-a!=2)ans=false;
  if(ans)cout<<"AC"<<endl;
  else cout<<"WA"<<endl;
}

Measured memory_bytes: 3628
a = gets.to_i
b = gets.to_i
c = gets.to_i
x = gets.to_i
cnt = 0

x /= 50

for i in 0..a do
  for j in 0..b do
    for k in 0..c do
      if 10*i+2*j+k == x then
        cnt += 1
      end
    end
  end
end

puts cnt


Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i);
int main(){
  int a,c=0,d=INT_MAX,f=INT_MAX;cin>>a;
  vector<int>b(a);
  for(int i=0;i<a;i++){
    cin>>b[i];
    c=max(c,b[i]);
    f=min(f,b[i]);
  }
  for(int i=f;i<=c;i++){
    int e=0;
    for(int o=0;o<a;o++){
      e+=(i-b[o])*(i-b[o]);
    }
    d=min(e,d);
  }
  cout<<d;
}


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

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int n, m, c;
  cin >> n >> m >> c;
  vector<int> b(m);
  for (auto &i : b) cin >> i;
  int ans = 0;
  for (int i = 0; i < n; i++) {
    int sum = c;
    for (int j = 0; j < m; j++) {
      int t; cin >> t;
      sum += t * b[j];
    }
    if (sum > 0) ans++;
  }
  cout << ans << '\n';
  return 0;
}


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

struct UnionFind {
    vector<int> par; 
    UnionFind(int N) : par(N) { 
        for(int i = 0; i < N; i++) par[i] = i;
    }
    int root(int x) { 
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }
    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return; 
        par[rx] = ry; 
    }
    void reset(int n){ 
        for(int i=0;i<n;i++)par[i] = root(par[i]);
    }
    bool con(int x,int y){
        return par[x]==par[y];
    }
};

int main(){
    int n,m;
    cin >> n >> m;
    UnionFind tree(n);
    int p[n];
    for(int i=0;i<n;i++)cin >> p[i];
    int x,y;
    for(int i=0;i<m;i++){
        cin >> x >> y;
        tree.unite(x-1, y-1);
    }
    tree.reset(n);
    int ans=0;
    for(int i=0;i<n;i++)ans += tree.con(i,p[i]-1);
    cout << ans << endl;
}

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 1e6 + 5;



int n,q;
map<int,vector<pair<int,int>>> mp;
int ans[maxn];

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

    cin>>n>>q;
    for (int i=0; i<n; i++) {
	int s,e,x; cin>>s>>e>>x;
	mp[x].emplace_back(s,e);
    }

    for (auto& p: mp) sort(p.second.begin(), p.second.end());

    vector<int> v(q);
    for (auto& x: v) cin>>x;

    set<pair<int,int>> active;
    for (int i=0; i<q; i++) {
	active.insert({v[i],i});
    }

    for (auto p: mp) {
	int x = p.first;
	for (auto cur: p.second) {
	    int s = cur.first; int e = cur.second;
	    for (auto iter = active.lower_bound({s-x,0}); iter != active.end() && iter->first < e-x; ) {
		int id = iter->second;
		ans[id] = x;
		iter = active.erase(iter);
	    }
	}
    }

    for (auto p: active) {
	ans[p.second] = -1;
    }


    for (int i=0; i<q; i++) {
	cout<<ans[i]<<"\n";
    }

    return 0;
}


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

const ll INF = 1LL << 60;

ll N;
vector<ll> a;
int main() {
    cin >> N;
    a.resize(N);
    rep(i, N) cin >> a[i];

    map<P, ll> mp;
    rep(i, N) {
        if (i + 1 > a[i]) {
            mp[P(a[i], i + 1)]++;
        } else {
            mp[P(i + 1, a[i])]++;
        }
    }

    ll ans = 0;
    for (auto v : mp) {
        if (v.second == 2) {
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 7296
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <numeric>
#include <functional>
#include <array>
using namespace std;

using pll = pair<long long, long long>;

int main() {
	int N; cin >> N;
	vector<pll> pos(N);
	int par;
	for (int i = 0; i < N; ++i) {
		cin >> pos[i].first >> pos[i].second;
		if (i == 0)par = (abs(pos[0].first) + abs(pos[0].second)) % 2;
		else if(par != ((abs(pos[i].first) + abs(pos[i].second)) % 2)){
			cout << -1; return 0;
		}
	}
		
	vector<long long>deg;
	for (int i = 30; 0 <= i; --i)deg.push_back(1LL << i);
	if (!par)deg.push_back(1);
	cout << deg.size() << endl;
	for (int i = 0; i < deg.size(); ++i)cout << deg[i] << " ";
	cout << endl;

	constexpr array<long long, 4> dx = { -1, +1, 0, 0 };
	constexpr array<long long, 4> dy = { 0, 0, -1, +1 };

	for (int i = 0; i < N;++i) {
		long currentX = 0;
		long currentY = 0;
		string dirLetter = "LRDU";
		for (auto&& d : deg) {
			int dl = 0;
			long long maxDistance = numeric_limits<long long>::max();
			for (int j = 0; j < 4;++j) {
				long nextX = currentX + d * dx[j];
				long nextY = currentY + d * dy[j];
				long distance = abs(nextX-pos[i].first) + abs(nextY-pos[i].second);
				if (distance < maxDistance) {
					maxDistance = distance;
					dl = j;
				}
			}
			cout << dirLetter[dl];
			currentX += d * dx[dl];
			currentY += d * dy[dl];
		}
		cout << endl;
	}
}


Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var a,b,c,d int
	fmt.Scan(&a,&b,&c,&d)
	fmt.Println(max(0, min(b,d) - max(a,c)))
}

func min(n,m int)int {
	if n <= m {
		return n
	}
	return m
}

func max(n,m int)int {
	if n <= m {
		return m
	}
	return n
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
typedef long long ll; 
 
using namespace std;
 
int main() {
	ll D, G;
	cin >> D >> G;
	vector<int> p(D + 1);
	vector<ll> c(D + 1);
	for (int i = 1; i <= D; ++i) {
		cin >> p[i] >> c[i];
	}

	vector<int> flg(D + 1, 0);
	int res = 1e8;
	for (int i = 0; i < (1<<(D + 1)); ++i) {
		for (int j = 0; j <= D; ++j) {
			flg[j] = ((i>>j) & 1);
		}
		if (flg[0]) { continue; }

		ll sum = 0;
		int tmp = 0;
		for (int j = 1; j <= D; ++j) {
			if (flg[j]) {
				sum += (100*j*p[j] + c[j]);
				tmp += p[j];
			}
		}
		if (sum >= G) {
			res = min(res, tmp);
			continue;
		}

		for (int j = D; j > 0; --j) {
			if (flg[j]) { continue; }
			if (sum >= G) { break; }

			for (int k = 1; k < p[j]; ++k) {
				if (sum >= G) { break; }
				sum += (100 * j);
				++tmp;
			}
		}
		if (sum >= G) { res = min(res, tmp); }
	}

	cout << res << endl;

	return 0;
}


Measured memory_bytes: 256
object Main extends App {

  import scala.io.StdIn._

  val Array(n, weightMax) = readLine.trim.split(' ').map(_.toInt)
  val minWeights = Array.tabulate(n * 1000 + 1){_ ⇒ Long.MaxValue}.also{arr ⇒ arr(0) = 0L}
  for (_ ← 0 until n){
    val Array(w, v) = readLine.trim.split(' ').map(_.toInt)
    for (prev ← (0 until minWeights.length - v).reverse) {
      if (minWeights(prev + v) - w > minWeights(prev) && weightMax - w >= minWeights(prev)) {
        minWeights(prev + v) = minWeights(prev) + w
      }
    }
  }
  println(minWeights.indices.filter(p ⇒ minWeights(p) <= weightMax).max)
  case class Goods(weights: Long, value: Long)
  implicit class Extend[T](value: T){
    def also(func: T ⇒ Unit): T = {func(value); value}
    def let[A](func: T ⇒ A): A = func(value)
  }
}

Measured memory_bytes: 37636
from itertools import permutations

N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))

nums = [i for i in range(1, N+1)]
all_list = list(permutations(nums))
a = all_list.index(P)
b = all_list.index(Q)
print(abs(a-b))


Measured memory_bytes: 8052
import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    int[] a=new int[101];
    for(int i=1;i<=9;i++){
      a[sc.nextInt()]=i;
    }
    boolean[] b=new boolean[10];
    int n=sc.nextInt();
    for(int i=0;i<n;i++){
      b[a[sc.nextInt()]]=true;
    }
    boolean flag;
    for(int i=0;i<3;i++){
      flag=true;
      for(int j=0;j<3;j++){
        flag=flag&&b[i*3+j+1];
      }
      if(flag){
        System.out.println("Yes");
        return;
      }
    }
    for(int i=0;i<3;i++){
      flag=true;
      for(int j=0;j<3;j++){
        flag=flag&&b[j*3+i+1];
      }
      if(flag){
        System.out.println("Yes");
        return;
      }
    }
    flag=true;
    for(int i=0;i<3;i++){
      flag=flag&&b[i*4+1];
    }
    if(flag){
      System.out.println("Yes");
      return;
    }
    flag=true;
    for(int i=0;i<3;i++){
      flag=flag&&b[i*2+3];
    }
    if(flag){
      System.out.println("Yes");
      return;
    }
    System.out.println("No");
  }
}

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

using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//
//using namespace __gnu_pbds;
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//class Timer {
//    clock_t start;
//    string name;
//public:
//    Timer() {name = "";start = clock();}
//    Timer(string s){name = s;start = clock();}
//    ~Timer() {fprintf(stderr, "%s: %.3gs\n", name.c_str(), 1.0*(clock() - start) / CLOCKS_PER_SEC);}
//};

//#define isValid(a, b) ((a) >= 0 && (a) < (b))
//int dr[]  =  {0, -1, -1, -1,  0,  1, 1, 1};
//int dc[]  =  {1,  1,  0, -1, -1, -1, 0, 1};

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define um unordered_map
#define us unordered_set
#define endl '\n'
#define what_is(x) cerr << fixed << setprecision(2) << boolalpha << #x << " = " << x << endl

const double EPS = 1e-9;
const double PI = acos(-1.0);

template<typename T> inline T sq(T a){return a*a;}
template<typename T1, typename T2> inline pair<T1, T2> mp(T1 a, T2 b){return make_pair(a, b);}
template<typename T1, typename T2> inline T1 safeMod(T1 a, T2 m){return (a%m + m)%m;}/*handling negative sign of remainder*/
template<typename T1, typename T2> inline bool isEq(T1 a, T2 b){return abs(a - b) < EPS;}
template<typename T1, typename T2, typename T3> inline bool isEq(T1 a, T2 b, T3 eps){return abs(a - b) < eps;}
template<typename T> inline bool isKthBitOn(T n, int k){assert(n <= numeric_limits<T>::max());assert(k<=numeric_limits<T>::digits);T ONE = 1;return bool((n & (ONE<<k)));}
template<typename T> inline void setKthBit(T& n, int k){assert(n <= numeric_limits<T>::max());assert(k<=numeric_limits<T>::digits);T ONE = 1;n = (n|(ONE<<k));}
//mt19937 rng((int)chrono::steady_clock::now().time_since_epoch().count());
//template<typename T> inline T nextRand(T lo, T hi){return uniform_int_distribution<T>(lo, hi)(rng);}

#define toRad(deg) ((deg)*PI/180.0)
#define toDeg(rad) ((rad)*180.0/PI)

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int oo = 0x3f3f3f3f;
const int MAX = 200010;
const int MOD = 1000000007;
const int precision = 10;

int main()
{
    //assert(freopen("in.txt", "r", stdin));
    //assert(freopen("out.txt", "w", stdout));
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cout << fixed << setprecision(precision);
    int a, b, x;
    cin >> a >> b >> x;
    int vol = a*a*b;
    long double ans;
    //what_is(toDeg(atan(b/a)));
    if(2*x < vol){
        long double halfAng = atan(1.0*b/a);
        long double lo = halfAng, hi = PI/2;
        int cnt = 100;
        while(cnt--){
            long double m = (lo+hi)/2;
            long double th = PI/2 - m;
            long double a2 = b*tan(th);
            if(x < a*b*a2/2)
                lo = m;
            else hi = m;
        }
        ans = toDeg((lo+hi)/2);
    }
    else{
        ans = toDeg(atan(2.0L*(a*a*b - x)/(a*a*a)));
    }
    cout << ans << endl;
    return 0;
}


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

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int []h = new int [n];
		int []t = new int [n];
		
		for(int i = 0; i < n ; i++) {
			h[i] = sc.nextInt();
		}
		for(int i = 0; i < n-1 ; i++) {
			int l = h[i+1] - h[i];
			if(l > 0) {
				t[i] = 0;
				}
			else {
				t[i] = 1;
				}
			}
		t[n-1] = 0;
		
		int ans = 0;
		int sum = 0;
		for(int i = 0; i < n; i++) {
			if(t[i] == 0) {
				ans = Math.max(ans, sum);
				sum = 0;
				
			}
			if(t[i] == 1) {
				sum++;
			}
				
		}
		System.out.println(ans);
		
		}
	}





Measured memory_bytes: 49896
package main
import "fmt"
func main() {
  var n,a,b,x,y int
  var s string
  fmt.Scan(&n,&a,&b,&s)
  for i:=0;i<n;i++ {
    if s[i:i+1] == "a" && x+y < a+b { x++;fmt.Println("Yes");continue }
    if s[i:i+1] == "b" && x+y < a+b && y < b { y++;fmt.Println("Yes");continue }
    fmt.Println("No")
  }
}

Measured memory_bytes: 3200
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
import sys
sys.setrecursionlimit(10000000)
#mod = 10**9 + 7
#mod = 9982443453
mod = 998244353
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
a,b = readInts()
print(a+b if b%a == 0 else b-a)


Measured memory_bytes: 10064
package main
 
import (
	"bufio"
	"fmt"
	"log"
	"os"
	"strconv"
)
 
func run() {

	var N int;
    N = nextInt();
    var S string;
    S = next();
	solve(N, S);

}

func solve(N int, S string){
	count := 1
	for i , r := range S {
		if i !=0 && S[i-1] != byte(r) {
			count++
		}
	}
	Println(count)
}


// --- template ---
// Thanks https://gist.github.com/halllllll/853ab587fd82ee3ffe6f7fb7fb499695
 
var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)
 
// Caution: You will get unexpected result if a single token is larger than this size.
const BufferSize = 64 * 1024 * 1024
 
func Print(a ...interface{}) (n int, err error) {
	return fmt.Fprint(out, a...)
}
 
func Printf(format string, a ...interface{}) (n int, err error) {
	return fmt.Fprintf(out, format, a...)
}
 
func Println(a ...interface{}) (n int, err error) {
	return fmt.Fprintln(out, a...)
}
 
func next() string {
	sc.Scan()
	return sc.Text()
}
 
func nextInt() int {
	a, err := strconv.Atoi(next())
	if err != nil {
		log.Fatal(err)
	}
	return a
}

func nextFloat() float64 {
	a, err := strconv.ParseFloat(next(), 64)
	if err != nil {
		log.Fatal(err)
	}
	return a
}


type IntHeap []int
func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

/////数字と文字
// 基本クラス
type NS struct {
    Num int
    Str string
}

//////　数字と数字
// 基本クラス
type NN struct {
    Num1 int
    Num2 int
}

 
func main() {
	sc.Buffer(make([]byte, 0, BufferSize), BufferSize)
	sc.Split(bufio.ScanWords)
	run()
	out.Flush()
}



Measured memory_bytes: 2944
#include <stdio.h>
int main(){
  int n;
  scanf("%d",&n);
  int a=0;
  if (n<10){a=n;}
  else if (n<100) {a=9;}
  else if (n<1000) {a=n-90;}
  else if (n<10000) {a=909;}
  else if (n<100000) {a=n-9090;}
  else{a=90909;}
  printf("%d",a);
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h> 
#define int long long
#define quickie ios_base::sync_with_stdio(false); cin.tie(NULL);
#define rep(i, a, b) for(int i=a; i<b; i++)
#define rep1(i, a, b) for(int i=a; i<=b; i++)
#define repp(i, a, b) for(int i=b-1; i>=a; i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define db double
#define mi map<int, int>
#define mc map<char, int>
#define ms map<string, int>
#define vi vector<int>
#define qi queue<int>
#define MI(x) power(x, mod-2)
#define test int t; cin >> t;
#define mod 1000000007LL
//#define mod 998244353 
using namespace std;
int power(int x, int y) ;
int gcd(int a, int b) ;

signed main() {
    quickie
    int n ;
    db m ;
    cin >> n >> m ;
    int l = m ;
    m = 1/(4*m) ;
    db s = 0 ;
    int c = 0 ;
    db a[n] ;
    rep(i, 0, n) {
        cin >> a[i] ;
        s += a[i] ;
    }
    rep(i, 0, n) {
        if(a[i]/s >= m ) c++ ;
    }
    if(c >= l) cout << "Yes" << endl ;
    else cout << "No" << endl ;
}
 
int power(int x, int y) {
    int res = 1; x %= mod;
    while (y > 0) {
        if (y & 1)
            res = (res*x) % mod;
        y = y>>1;
        x = (x*x) % mod;
    }
    return res%mod;
}
 
int gcd(int a,int b){
    if(a==0) return b;
    return gcd(b%a,a);
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;


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

	long long n, m, i, j, k, ans, a, b;
	cin >> n >> m;
	if (n < m) swap(n, m);
	if (m == 1) ans = 1;
	else if ((n * m) % 2 == 0) ans = n * m / 2;
	else ans = n * m / 2 + 1;
	cout << ans << "\n";


	return 0;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B,L,R;
string S, T;
const ll MOD = 998244353;
const ll INF = 1LL << 60;
typedef pair<ll,ll> P;

int main() {
    cin>>W>>H;
    vec pq(W + H), ord(W + H);
    ll sum = 0;
    rep(i,W + H) cin>>pq[i], sum += pq[i], ord[i] = i;
    sort(ALL(ord), [&](ll x, ll y){
        return pq[x] < pq[y];
    });
    ll usedp, usedq;
    usedp = usedq = 0;
    rep(i, W + H){
        ll id = ord[i];
        bool p = id < W;
        sum += p ? (H - usedq) * pq[id] : (W - usedp) * pq[id];
        p ? ++usedp : ++usedq;
    }
    cout<<sum<<endl;
}

Measured memory_bytes: 3328
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <utility>
using namespace std;

int main() {
  int N;
  cin>>N;
  
  vector<string> s(N);
  for(int i=0;i<N;++i){
    cin>>s[i];
  }
  
  bool flag=true;
  
  for(int i=0;i<N-1;++i){
    if(s[i][s[i].size()-1]!=s[i+1][0])
      flag=false;
  }
  
  for(int i=0;i<N-1;++i){
    for(int j=i+1;j<N;++j){
      if(s[i]==s[j])
        flag=false;
    }
  }
  
  if(flag)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
  
}

Measured memory_bytes: 256
/*
   Created by Rahul Goel.
*/

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>

using namespace std;
typedef long long ll;
ll mod = 1000000007;
const int INF = 1e9;
const ll LINF = 1e18;

#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(c) (c).begin(), (c).end()
#define pii pair < int, int >
#define vi vector < int >
#define vb vector < bool >
#define vvi vector < vector < int > >
#define vvb vector < vector < bool > >
#define vpii vector < pair < int, int > >
#define vvpii vector < vector < pair < int, int > > >
#define pb push_back
#define f first
#define s second
#define mp make_pair

int main(){
    fastio;

    string str;
    cin >> str;
    if(str[0] == '7' || str[1] == '7' || str[2] == '7')
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}


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

int main(){

  int n;
  int key;
  int a[110];
  cin >> n;
  for(int i = 0;i < n; i++){
    cin >> a[i];
  }
  int j;
  for(int i = 0;i < n; i++){
    key = a[i];
    j = i-1;
    while(j >= 0 && a[j] > key){
      a[j+1] = a[j];
      j--;
    }
    a[j+1] = key;
    for(int i = 0;i < n;i++){
      if(i == n-1) cout << a[i] <<endl;
      else cout << a[i] << " ";
    }
  }
  
  return 0;
}

Measured memory_bytes: 1160
N=int(input())
AB=[]
for _ in range(N):
    a,b=map(int,input().split())
    AB.append([a+b,a,b])
AB.sort(reverse=True)

ans=0
for i in range(N):
    if i%2==0:
        ans+=AB[i][1]
    else:
        ans-=AB[i][2]
print(ans)

Measured memory_bytes: 29184
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <cassert>
using namespace std;
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();}
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i, 0, n)
#define EACH(t,i,c) for(t::iterator i=(c).begin(); i!=(c).end(); ++i)
#define PB push_back
const double EPS = 1e-10;
const double PI = acos(-1.0);

struct country {
	int potential;
	vi missiles;
	country():potential(0),missiles(vi()){
	}
};
vector<country> countries;

int main(){
	int n, d;
	while (cin >> n >> d, n | d) {

		// Input
		countries = vector<country>(n,country());
		REP (i, n) {
			int m; cin >> m;
			REP (j, m) {
				int c; cin >> c;
				countries[i].missiles.PB(c);
				countries[i].potential += c;
			}
		}

		bool yes = false;
		while (true) {
			// Check current max, min pottentials
			int max_p = 0, min_p = 10000 * 1000;
			REP (i, n) {
				max_p = max(max_p, countries[i].potential);
				min_p = min(min_p, countries[i].potential);
			}
			if (max_p - min_p > d) {
				goto FINISH;
			}
			if (max_p == 0) {
				yes = true;
				goto FINISH;
			}

			// Remove greedily
			bool updated = true;
			while (updated) {
				updated = false;
				REP (i, n) {
					while (countries[i].missiles.size() && max_p - (countries[i].potential - countries[i].missiles.back()) <= d) {
						countries[i].potential -= countries[i].missiles.back();
						countries[i].missiles.pop_back();
						updated = true;
					}
				}
				// Check current max
				max_p = 0;
				REP (i, n) {
					max_p = max(max_p, countries[i].potential);
				}
			}

			if (max_p == 0) {
				// Peace!
				yes = true;
				goto FINISH;
			}

			// Find max potential country
			int max_country = -1;
			REP (i, n) {
				if (countries[i].potential == max_p) {
					if (max_country != -1) {
						goto FINISH;
					}
					max_country = i;
				}
			}

			// Try removing max_country's missile (validated in next step)
			if (countries[max_country].missiles.size() ) {
				countries[max_country].potential -= countries[max_country].missiles.back();
				countries[max_country].missiles.pop_back();
			}
		}
		
FINISH:
		if (yes) cout << "Yes" << endl;
		else cout << "No" << endl;
	}

}

Measured memory_bytes: 1320
n, m = map(int, input().split())
if abs(n - m) > 1:
    print(0)
    exit()
ans = 1
for i in range(1, n + 1):
    ans *= i
    ans %= 10**9 + 7
for i in range(1, m + 1):
    ans *= i
    ans %= 10**9 + 7
if abs(n - m) == 0:
    ans *= 2
    ans %= 10**9 + 7
print(ans)


Measured memory_bytes: 9124
import Data.List

solve (n:m:rest) =
    sum $ map toInteger $ merge
    where
        split arr = case arr of 
            [] -> []
            (b:c:rest) -> (c,b) : split rest
        (f,r) = splitAt n rest
        cs = (reverse.sort $ split r) >>= (uncurry $ flip replicate)
        merge = zipWith max (sort f) (cs ++ repeat 0)

main = interact $ show.solve.map read.words

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

#define pout(n)  printf ("%d\n", n)

#define rep(i,a,n) for (int i = a;i < n;i++)
#define per(i,n,a) for (int i = n-1;i >= a;i--)
#define BIT(bit,a,n) for (int bit = a;bit < (1<<n);bit++) // {0, 1, ..., n-1} の部分集合の全探索 // n番目のフラグが立っている状態は (1<<n)

const int d4x[4] = {1, 0, -1, 0};
const int d4y[4] = {0, 1, 0, -1};
const int d8x[8] = { 1,1,0,-1,-1,-1,0,1 };
const int d8y[8] = { 0,1,1,1,0,-1,-1,-1 };

#define MAX_N (int)2e5+20

typedef long long ll;
using namespace std;

ll n;
string s;
ll m=0,a=0,r=0,c=0,h=0;
ll ans = 0;
int main() {
    scanf("%lld",&n);
    rep(i,0,n){
        cin >> s;
        if(s[0] == 'M') m++;
        else if(s[0] == 'A') a++;
        else if(s[0] == 'R') r++;
        else if(s[0] == 'C') c++;
        else if(s[0] == 'H') h++;
    }
    ans = m*a*r+m*a*c+m*a*h+m*r*c+m*r*h+m*c*h+a*r*c+a*r*h+a*c*h+r*c*h;

    printf("%lld\n",ans);
    return 0;    
}


Measured memory_bytes: 256
n, m = map(int, raw_input().split())
A = [None] * n
for i in xrange(n):
    A[i] = map(int, raw_input().split())
b = [None] * m
for j in xrange(m):
    b[j] = input()

for i in xrange(n):
    k = 0
    for j in xrange(m):
        k += A[i][j] * b[j]
    print k

Measured memory_bytes: 6636
#include <iostream>
using namespace std;
struct card{
    int number;
    char type;
    bool status;
};

void print_card(struct card card1)
{
    cout<<card1.type<<" "<<card1.number<<endl;
}

int main(){
    int a;
    cin>>a;
    int numbers[13]={1,2,3,4,5,6,7,8,9,10,11,12,13};
    char types[4]={'S','H','C','D'} ;
    card allcard[52];
    card input_card[a];
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<13;j++)
        {
            allcard[i*13+j].number=numbers[j];
            allcard[i*13+j].type=types[i];
            allcard[i*13+j].status=false;
        }
    }
    for(int i=0;i<a;i++)
    {
        cin>>input_card[i].type>>input_card[i].number;
    }
    for(int i=0;i<52;i++)
    {
        for(int j=0;j<a;j++)
        {
            if(input_card[j].type==allcard[i].type&&input_card[j].number==allcard[i].number)
                allcard[i].status=true;
        }
    }
    for(int i=0;i<52;i++)
    {
        if(!allcard[i].status)
            print_card(allcard[i]);
    }
    return 0;

}


Measured memory_bytes: 3060
var main = function(input) {

var array =input.split(' ').map(x=>parseInt(x));
	array=array.sort();
	array=array.reverse();
var sum=array[0]*10+array[1]+array[2];
  console.log(sum)
    return 0; 
}

main(require("fs").readFileSync("/dev/stdin", "utf8").trim());

Measured memory_bytes: 21064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
int main(){
	int a[3];
	cin>>a[0]>>a[1]>>a[2];
	int cnt1=0,cnt2=0;
	for(int i=0;i<3;i++)
		if(a[i]==5) cnt1++;
		else if(a[i]==7) cnt2++;
	if(cnt1==2&&cnt2==1) puts("YES");
	else puts("NO"); 
	return 0;
}

Measured memory_bytes: 3524
import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.Maybe

readInt = fromIntegral . fst . fromJust . BS.readInteger
readIntList = map readInt . BS.words

getInt = readInt <$> BS.getLine
getIntNList n = map readIntList <$> replicateM (fromIntegral n) BS.getLine

calc :: [Int] -> [[Int]] -> Int -> Int -> Float
calc xy [] i j = 0
calc xy (xy' : xys') i j
  | i == j = 0
  | otherwise = sqrt (fromIntegral((head xy - head xy') ^ 2 + (last xy - last xy') ^ 2)) + (calc xy xys' i (j + 1))

calcAll :: [[Int]] -> [[Int]] -> Int -> Float
calcAll [] xys' i = 0
calcAll (xy : xys) xys' i = calc xy xys' i 0 + calcAll xys xys' (i + 1)

main = do
  n <- getInt
  xys <- getIntNList n
  print $ (calcAll xys xys 0) / (fromIntegral n) * 2.0


Measured memory_bytes: 3840
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#include<math.h>
#include<tuple>
#include<bitset>

#define MOD 1000000007
using namespace std;

int main()
{
	int X,A;	cin >> X>>A;

	if (X < A)	cout << 0;
	if (X >= A)	cout << 10;
	return 0;
}

Measured memory_bytes: 256
/* ex4_1
    sak_Citrus*/

#include <stdio.h>
#include <stdbool.h>

int main(void){
    //標準入力
    int appleNum,d,ans;
    scanf("%d %d",&appleNum,&d);

    //一人2d+1本の木を監視可能
    if(appleNum % (2*d + 1) == 0){
        //全員が最大幅を監視
        ans = appleNum / (2*d+1);
    }else{
        //最後の一人だけ少ない監視範囲
        ans = appleNum / (2*d+1) + 1;
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 128
//全国統一プログラミング王予選
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)

int main()
{
ll n , m ,root;
cin >> n >> m ;
vector<vector<ll>> g(n);
set<ll> s;
vector<ll> f(n);
rep(i,n-1+m)
{
  ll a, b;
  cin >> a >> b;
  s.insert(b-1);
  f[b-1]++;
  g[a - 1].push_back(b - 1);
}
rep(i,n){
  if(s.find(i)==s.end())root=i;
}
vector<ll> par(n);
par[root]=-1;
queue<ll> q;
q.push(root);
while(!q.empty()){
  ll p=q.front();
  q.pop();
  for(auto r:g[p]){
    par[r]=p;
    f[r]--;
    if(f[r]==0)q.push(r);
  }
}
for(auto an:par)cout << an+1 << endl;
return 0;
}

Measured memory_bytes: 12544
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
int a[103][27];
int l[103];
int N;
void highplus(int x,int y,int z){
	l[x]=max(l[y],l[z]);
	int i,j;
	for(i=0;i<l[y];i++){
		a[x][i]+=a[y][i]+a[z][i];
		a[x][i+1]+=a[x][i]/10;
		a[x][i]%=10;
	}
	while(a[x][l[x]])l[x]++;
}
int main(){
	memset(a,sizeof(a),0);
	a[0][0]=2;l[0]=1;
	a[1][0]=1;l[1]=1;
	int i;
	scanf("%d",&N);
	for(i=2;i<=N;i++)highplus(i,i-1,i-2);

		for(i=0;i<l[N];i++)printf("%d",a[N][l[N]-i-1]);
		printf("\n");	
	
	return 0;
}

Measured memory_bytes: 256