akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<string.h>
int main(){
	int i,c=0;
	char w[11],t[1001];
	scanf("%s",&w);
	while(1){
		scanf("%s",t);
		if(!strcmp(t,"END_OF_TEXT"))break;
		for(i=0;t[i]!='\0';i++)if(t[i]<91)t[i]+=32;
		if(!strcmp(w,t))c++;
	}
	printf("%d\n",c);
	return 0;
}


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

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int MOD = 1e9+7;
const int N = 2005;

int fastpow(int n, int p){
	int res = 1;
	while(p){
		if(p&1) res = (res * n) % MOD;
		n = (n * n) % MOD;
		p>>=1;
	}
	return res;
}

int fact[N];

void init(){
	fact[0] = 1;
	for(int i = 1;i < N;i++){
		fact[i] = fact[i-1] * i % MOD;
	}
}

void solve(){
	init();
	int n;
	cin >> n;
	int ans = 0, i = 1;
	while(n-3*i >= 0){
		//cout << n-3*i << " " << i-1 << "\n";
		//cout << fact[n-3*i+i-1]*fastpow(fact[n-3*i],MOD-2)%MOD*fastpow(fact[i-1],MOD-2)%MOD << "\n";
		ans = (ans + fact[n-3*i+i-1]*fastpow(fact[n-3*i],MOD-2)%MOD*fastpow(fact[i-1],MOD-2)%MOD)%MOD;
		i++;
	}
	cout << ans << "\n";
}

signed main(){
	fastio
	int t = 1;
	//cin >> t;
	while(t--) solve();
}

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

int main(void){
	int a, b;

	cin >> a >> b;

	if (a == b) cout << "Draw" << endl;
	else if (a != 1 && (b == 1 || a < b)) cout << "Bob" << endl;
	else cout << "Alice" << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <functional>
#include <string>
#include <stack>
#include <set>
#include <sstream>
#include <iomanip>
#include <limits>
#include <cstring>

using namespace std;
using ll = long long;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<double, double >pd;
typedef pair<string, string> sP;
typedef pair<ll, P> PP;
typedef pair<P, P> PPP;

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll INF = 1 << 30;
const ll INF2 = 9e18;
const double INF3 = 9e14;
const double eps = 1e-10;
const double PI = 3.14159265358979323846;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };

#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
#define fr first
#define sc second

vector<ll>x, y;
ll n, h, w, hmax[100010], ans = INF;
P a[100010];

int main() {
	cin >> w >> h >> n;
	for (int i = 0;i < n;i++) {
		cin >> a[i].fr >> a[i].sc;
	}
	sort(a, a + n);
	for (int i = n - 1;i >= 0;i--) {
		hmax[a[i].fr - 1] = max(hmax[a[i].fr - 1], a[i].sc);
	}
	for (int i = w - 1;i > 0;i--) {
		hmax[i - 1] = max(hmax[i], hmax[i - 1]);
	}
	for (ll i = 0;i < w;i++) {
		ll l = -1, r = h, mid;
		while (r - l > 1) {
			mid = (r + l) / 2;
			if (mid >= hmax[i])r = mid;
			else l = mid;
		}
		ans = min(ans, i + r);
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 5440
#include <bits/stdc++.h>
using namespace std;
#define fore(i, init, n) for(long long i = init; i < n; i++)
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;

const int MAXN = 1e4+5;
int sn, tn, dp[MAXN][MAXN];
string s, t;

int solve(int i, int j) {
    int aux; 
    if (i==sn || j==tn) return 0;
    if (dp[i][j] != -1) return dp[i][j];
    
    if (s[i] == t[j]) aux = 1 +   solve(i+1, j+1);
    else aux = max(solve(i+1, j), solve(i, j+1));
    
    dp[i][j] = aux;
    return aux;
}

int main() {
    FIN;
    cin >> s >> t;
    
    sn = s.size(); 
    tn = t.size();
   
    memset(dp, -1, sizeof dp);
   
    solve(0,0);
    
    int i = 0, j = 0;
    string res;
    while(i < sn && j < tn) {
        if (s[i] == t[j]) {
            res += s[i];
            i++;j++;
        } else { 
            if (dp[i+1][j] > dp[i][j+1]) i++;
            else j++;
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 391552
#include<bits/stdc++.h>
#define EM 100000000
using namespace std;
using LL = long long;
using P = pair<LL, LL>;
LL LINF = 1e18;
int INF = 1e9;
using vint = vector<int>;
using vLL = vector<LL>;
using vvint = vector<vector<int>>;
using vvLL = vector<vector<LL>>;

int main(){
	int N; 
	cin >> N;
	vLL x(N), y(N);
	map<P, int>	mp;
	for(int i = 0;i < N;i++)	cin >> x[i] >> y[i];
	for(int i = 0;i < N;i++){
		for(int j = 0;j < N;j++){
			if(i != j){
				LL xi = x[i]-x[j];
				LL yi = y[i]-y[j];
				mp[P(xi, yi)]++;
			}
		}
	}
	int num = 0;
	for(auto &v : mp)	num = max(num, v.second);
	cout << (N-num) << endl; 
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define maxn 100010
#define ll long long
ll s1[maxn],s2[maxn],ans;
int a[maxn],n,q,i,j,x,l,r,mid,t;
int getnum()
{
	int s=0;
	char c=getchar();
	for (;!isdigit(c);c=getchar());
	for (;isdigit(c);c=getchar())
		s=s*10+c-'0';
	return s;
}
int get(int x)
{
	int l=1,r=n,mid=(l+r)>>1,ans=n;
	for (;l<=r;mid=(l+r)>>1)
		if (a[mid]>=x)
		{
			ans=mid;
			r=mid-1;
		}
		else l=mid+1;
	return ans;
}
int main()
{
	n=getnum();
	q=getnum();
	for (i=1;i<=n;i++)
		a[i]=getnum();
	s1[1]=s2[1]=a[1];
	for (i=2;i<=n;i++)
	{
		s1[i]=s1[i-1]+(ll)a[i];
		s2[i]=s2[i-2]+(ll)a[i];
	}
	for (i=1;i<=q;i++)
	{
		x=getnum();
		l=1;
		r=n;
		ans=s2[n];
		for (mid=(l+r)>>1;l<=r;mid=(l+r)>>1)
			if (a[mid]<=x) l=mid+1;
				else
				{
					t=get(x*2-a[mid]);
					if (mid-t<n-mid) l=mid+1;
					else
					{
						ans=s1[n]-s1[mid-1]+(n>=(n-mid+1)*2 ? s2[n-(n-mid+1)*2] : 0);
						r=mid-1;
					}
				}
		printf("%lld\n",ans);
	}
	return 0;
}

Measured memory_bytes: 3712
#include<cstdio>
#include<algorithm>
using namespace std;
int n,s[100];

int main()
{
        scanf("%d",&n);
        if (n==0) return 0;
        for (int i=0;i<n;i++){
                scanf("%d",s+i);
        }
        sort(s, s+n);
        int k=0;
        for (int i=1;i<n-1;i++){
                k+=s[i];
        }
        k/=n-2;
        printf("%d\n",k);
        main();
}
  

Measured memory_bytes: 0
#include <iostream>
using namespace std;
char Str[7];
bool Read()
{
    cin.getline(Str + 1, 7);
    for(int i = 1; Str[i] != 0; i++)
    {
        if(Str[i + 1] == 0)
            return 0;
        if(Str[i] == 'A' && Str[i + 1] == 'C')
            return 1;
    }
    return 0;
}

int main()
{
    if(Read())
        cout << "Yes\n";
    else
        cout << "No\n";
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

int main(void){
	while(true){
		string number;
		cin >> number;
		if(number == "0"){
			break;
		}
		int tmp = 0;
		for(int i = 0;i < number.length(); ++i){
			tmp += (number.at(i) - '0');
		}
		cout << tmp << endl;
	}

	return 0;
}

Measured memory_bytes: 1192
#include <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

int main(){
  int n;
  while(cin >> n, n){
    stack<string> st;
    string e;
    int d = 0;
    for(int i = 0; i < n; ++i){
      cin >> e;
      int l = e.length();
      e = e[l-1];
      while(l < d){
	vector<int> t;
	string s = st.top();
	while(s.length() > 1 || (s >= "0" && s <= "9")){
	  t.push_back(stoi(s));
	  st.pop();
	  s = st.top();
	}
	string o = "";
	if(!st.empty()){
	  o = st.top();
	  st.pop();
	}
	if(o == ""){
	  if(t.size() > 1){
	    cout << "Error" << endl;
	  }else{
	    cout << t[0] << endl;
	  }
	}else{
	  if(o == "+"){
	    int ret = 0;
	    for(int i = 0; i < t.size(); ++i){
	      ret += t[i];
	    }
	    st.push(to_string(ret));
	    --d;
	  }else if(o == "*"){
	    int ret = 1;
	    for(int i = 0; i < t.size(); ++i){
	      ret *= t[i];
	    }
	    st.push(to_string(ret));
	    --d;
	  }
	}
      }
      st.push(e);
      d = l;
    }

    stack<int> st2;
    while(!st.empty()){
      string e = st.top();
      st.pop();
      if(e == "+"){
	int k = 0;
	while(!st2.empty()){
	  int l = st2.top();
	  k += l;
	  st2.pop();
	}
	st.push(to_string(k));
      }else if(e == "*"){
	int k = 1;
	while(!st2.empty()){
	  int l = st2.top();
	  k *= l;
	  st2.pop();
	}
	st.push(to_string(k));
      }else{
	st2.push(stoi(e));
      }
      if(st.empty()){
	cout << st2.top() << endl;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 3296
//In the name of God

#include <bits/stdc++.h>
using namespace std;

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

const int N = 1e5+10 , mod = 1e9+7;

int dp[N] , a[N];

int32_t main(){
   ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
   cout << fixed << setprecision(9);
   int n , k;
   cin >> n >> k;
   for(int i = 0 ; i < n ; i++)
      cin >> a[i];
   dp[0] = 0;
   for(int i = 1 ; i <= k ; i++)
      for(int j = 0 ; j < n ; j++)
         if(i >= a[j] && !dp[i - a[j]])
            dp[i] = 1;
   cout << ((dp[k] == 1) ? "First" : "Second");
   return 0;
}


Measured memory_bytes: 640
#include <iostream>
#define MAX 600000
using namespace std;

int is_prime[MAX];

void tenesu(void){

  for( int i = 0 ; i < MAX ; i++ ) is_prime[i] = 1;
  is_prime[0] = is_prime[1] = 0;

  for( int i = 0 ; i*i < MAX ; i++ ){
    if( is_prime[i] ){
      for( int j = 2*i ; j < MAX ; j += i ){
	is_prime[j] = 0;
      }
    }
  }
}


int main(void){

  tenesu();

  int n; 
  while( cin >> n ){

    for( int i = n - 1; i > 0 ; i-- ){
      if( is_prime[i] ){
	cout << i << " ";
	break;
      }
    }

    for( int i = n + 1; i < MAX ; i++ ){
      if( is_prime[i] ){
	cout << i << endl;;
	break;
      }
    }

  }
  return 0;
}

Measured memory_bytes: 3504
N = int(input())
word = input()
W = [input() for i in range(N-1)]
used = set()
used.add(word)

for w in W:
    if w[0] == word[-1] and w not in used:
        used.add(w)
        word = w
    else:
        print("No")
        break
else:
    print("Yes")


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

int n,a;

int main(){
	cin>>n;
	if(n % 10 == 9){
		cout<<"Yes"<<endl;
	}else if(n / 10 == 9){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

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

		int N = sc.nextInt();
		int[] A = new int[N];
		for (int i=0; i<A.length; i++) {
			A[i] = sc.nextInt();
		}

		
		for (int i=0; i<N-1; i++) {
			while (true) {
				if (A[i] < A[i+1]) {
					if (A[i+1] % A[i] == 0) {
						A[i+1] = A[i];
						break;
					}
					
					A[i+1] = A[i+1] % A[i];
				}
				else if (A[i] > A[i+1]) {
					if (A[i] % A[i+1] == 0) {
						A[i] = A[i+1];
						break;
					}
					
					A[i] = A[i] % A[i+1];
				}
				else {
					break;
				}
			}
			
		}
		
		System.out.println(A[N-1]);
	}

}


Measured memory_bytes: 49828
#include<cstdio>
#include<bitset>
#include<vector>
#include<iostream>
using namespace std;

typedef long long ll;
bitset<1000001> pt;
vector<int> pa;

void MakeTable(int n){
  pt.reset();
  pt.set(2);

  int i = 2;
  while(++i<=n)if(i&1)pt.set(i);

  i = 3;
  while(i*i<=n){
    for(int j=3*i;j<n;j+=2*i)pt.reset(j);
    while(!pt[++i]);
  }
}

void MakeArray(int n){
  MakeTable(n);
  for(int i=0;i<=n;i++)
    if(pt[i])pa.push_back(i);
}

vector<int> e,te;

int rec(int x){
  if(x==(int)e.size()){
    int res = 1;
    for(int i=0;i<(int)e.size();i++)
      if(e[i]==te[i])res *= (e[i]+1);
    return res;
  }else{
    int res = 0;
    for(int i=0;i<=e[x];i++){
      te.push_back(i);
      res += rec(x+1);
      te.pop_back();
    }
    return res;
  }
}

int main(){
  ll l;
  MakeArray(1000000);
  while(scanf("%lld",&l) && l){
    int j = 0;
    e.clear();
    while(j<(int)pa.size() && pa[j]<=l){
      int cnt = 0;
      while(!(l%pa[j])){
	l/=pa[j];
	cnt++;
      }
      if(cnt)e.push_back(cnt);
      j++;
    }
    if(l>1)e.push_back(1);
    te.clear();
    int ans = rec(0);
    printf("%d\n",(ans+1)/2);
  }
}

Measured memory_bytes: 0
#include <iostream>
#include <map>
#define int long long
using namespace std;

signed main(){
	int n,m;
	while(cin >> n >> m,n){
		int a[30010] = {},ma = 0;
		map<int,bool> mp;
		for(int i = 1;i <= n;i++){
			cin >> a[i];
			a[i] = (a[i - 1] + a[i]) % m;
			auto it = mp.upper_bound(a[i]);
			if(it == mp.end()) ma = max(ma,a[i]);
			else ma = max(ma,a[i] + m - it->first);
			mp[a[i]] = true;
		}
		cout << ma << endl;
	}
}

Measured memory_bytes: 4876
#include <bits/stdc++.h>
using namespace std;
#define iof freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define BiEdge(v,a,b) (v)[(a)].pb((b)),(v)[(b)].pb((a))
#define ll long long
#define ld long double
#define pb push_back
#define Pb pop_back
#define F first
#define S second
#define X real()
#define Y imag()
#define pi acos(-1)
#define eps 1e-7
#define bpc __builtin_popcount
#define all(f) (f).begin(),(f).end()
#define allr(f) (f).rbegin(),(f).rend()
#define cross(a,b) (conj(a)*(b)).real()
#define dot(a,b) (conj(a)*(b)).imag()
typedef complex <ld> point ;
typedef vector <point> polygon ;
typedef tuple <ll,ll,ll> line ;
const int mod = 1e9+7 , A = 1e4+1 ;

int main()
{
	ios
	ll n ;
	cin >> n ;
	ll a , b , c ;
	for (int i = 0 ; i < n ; i++)
	{
		ll x , y , z , tmpa = a , tmpb = b , tmpc = c ;
		cin >> x >> y >> z ;
		if (!i)
			a = x , b = y , c = z ;
		else
			a = x + max(tmpb , tmpc) , b = y + max(tmpa , tmpc) , c = z + max(tmpa , tmpb) ;
	}
	ll ans = max(a , max(b , c)) ;
	cout << ans ;
	return 0 ;
}

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

using namespace std;

int N, K, A[5000];
bool dp1[5002][5001];
int dp2[5002][5001];


int main()
{
  cin >> N >> K;
  for(int i = 0; i < N; i++) {
    cin >> A[i];
    A[i] = min(A[i], K);
  }

  dp1[0][0] = true;
  for(int i = 0; i < N; i++) {
    for(int j = K; j >= A[i]; j--) {
      dp1[i + 1][j] |= dp1[i][j - A[i]];
    }
    for(int j = K; j >= 0; j--) {
      dp1[i + 1][j] |= dp1[i][j];
    }
  }

  dp2[N][0] = true;
  for(int i = N - 1; i >= 0; i--) {
    for(int j = K; j >= A[i]; j--) {
      dp2[i][j] |= dp2[i + 1][j - A[i]] > 0;
    }
    for(int j = K; j >= 0; j--) {
      dp2[i][j] |= dp2[i + 1][j] > 0;
    }
  }
  for(int i = 0; i <= N; i++) {
    for(int j = 1; j <= K; j++) {
      dp2[i][j] += dp2[i][j - 1];
    }
  }

  int ret = N;
  for(int i = 1; i <= N; i++) {
    bool flag = false;
    for(int j = 0; j < K; j++) {
      if(dp1[i - 1][j]) {
        int x = K - A[i - 1] - j; // 以上
        int y = K - j; // 未満
        if(dp2[i][y - 1] - (x <= 0 ? 0 : dp2[i][x - 1]) > 0) {
          flag = true;
        }
      }
    }

    ret -= flag;
  }

  cout << ret << endl;
}

Measured memory_bytes: 122368
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define min_3(a,b,c) min(a,min(b,c))
#define max_3(a,b,c) max(a,max(b,c))
#define nout(ans) cout << (ans) << "\n"
#define sout(ans) cout << (ans) << " "
using namespace std;

const double pi = 3.14159265359;
const ll INF = 1e12;
const ll MOD = 1e9 + 7;
const ll N = 1e5 + 5; 
/*
Decimal Places: cout << fixed << setprecision(n) << ans << endl
*/

bool compare(const pair<int, int>&i, const pair<int, int>&j)
{
    return i.second < j.second;
}

ll raise(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}


ll n, a; vector <ll> v; set<ll>s; ll ans=0;
map <ll,ll> m;

void solve()
{
    cin >> n;
    for (int i=0; i<n; ++i) {
        cin >> a;
        m[a]++;
        if (!s.count(a)) {
            v.pb(a); s.insert(a);
        }
    }
    sort(v.begin(),v.end());
    n=v.size();
    for (int i=0; i<n; ++i) {
        for (int j=i+1; j<n; ++j) {
            for (int k=j+1; k<n; ++k) {
                if (v[i]+v[j]>v[k]) {
                    ans += m[v[i]]*m[v[j]]*m[v[k]];
                    //sout(v[i]); sout(v[j]); nout(v[k]);
                }
            }
        }
    }nout(ans); 
    
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    //cin >> t;
    for (int i=1; i<=t; i++)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++) cin>>a[i];
  int ans=1e9;
  for(int i=1;i<=100;i++)
  {
      int temp=0;
      for(int j=0;j<n;j++)
          temp+=(a[j]-i)*(a[j]-i);
      ans=min(ans,temp);
  }
  cout<<ans;
  return 0;
}

Measured memory_bytes: 3652
/* -*- coding:utf-8 -*- */

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cmath>

using namespace std;

int main(void)
{
  double a,b,c,d,e,f;


  while(cin >> a >> b >> c >> d >> e >> f, !cin.eof()) {
    double x,y;
    x = (e*c-b*f)/(a*e-b*d);
    y = (-c*d+a*f)/(a*e-b*d);
    cout << fixed << setprecision(3) << showpoint << ((fabs(x) < 1e-4) ? 0 : x) << ' ' << ((fabs(y) < 1e-4) ? 0 : y) << endl;
  }
  return 0;
}

Measured memory_bytes: 1280
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder_solve
{
    class Program
    {
        public const ulong mod = 1000000007;

        static void Main(string[] args)
        {
            var abcxy = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var a = abcxy[0];
            var b = abcxy[1];
            var c = abcxy[2];
            var x = abcxy[3];
            var y = abcxy[4];
            long ans = 0;

            if (a + b < 2 * c)
            {
                ans += a * x + b * y
;
            }
            else
            {
                ans += 2 * c * Math.Min(x, y);
                if (x - y >= 0 && a <= 2 * c) ans += a * (x - y);
                if (x - y >= 0 && a > 2 * c) ans += 2 * c * (x - y);
                if (x - y < 0 && b <= 2 * c) ans += b * (y - x);
                if (x - y < 0 && b > 2 * c) ans += 2 * c * (y - x);
            }

            Console.WriteLine(ans);

        }

        static public long Input()
        {
            return long.Parse(Console.ReadLine());
        }

        static public string[] Input2()
        {
            return Console.ReadLine().Split();
        }
        
        static public long[] Input3()
        {
            string[] data = Console.ReadLine().Split();
            long[] res = new long[data.LongLength];
            for(long i = 0; i < data.LongLength; i++)
            {
                res[i] = long.Parse(data[i]);
            }
            return res;
        }
        public static long Choose(long n, long a)
        {
            long x = 1;
            long y = 1;
            for (long i = 0; i < a; i++)
            {
                x *= n - i;
                y *= i + 1;
            }
            return x / y;
        }

        public static long Gcd(long a, long b)
        {
            long x = Math.Max(a, b);
            long y = Math.Min(a, b);
            if (x % y == 0) return y;
            else return Gcd(y, x % y);
        }
    }
}


Measured memory_bytes: 13396
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long int> v1, v2;
    for (int i = 0; i < n; i++) {
        long long int x, y;
        cin >> x >> y;
        v1.push_back(x + y);
        v2.push_back(x - y);
    }
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    cout << max(v2.back() - v2[0], v1.back() - v1[0]) << endl;
}




Measured memory_bytes: 6640
#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

struct Tag {
    int r, c, dir;
    int cost;

    Tag() {}
    Tag(int r, int c, int dir, int cost) : r(r), c(c), dir(dir), cost(cost) {}

    bool operator <(const Tag &other) const {
        return cost > other.cost;
    }
};

// dir = EAST, NORTH, WEST, SOUTH
int DR[4] = {0, -1, 0, 1};
int DC[4] = {1, 0, -1, 0};
// {STRAIGHT, RIGHT, BACK, LEFT}
int DD[4] = {0, 3, 2, 1};

inline bool in_range(int a, int x, int b) {
    return a <= x && x < b;
}

bool update(int &a, int v) {
    if(v < a) {
        a = v;
        return true;
    }
    return false;
}

// memo[dir][r][c]
int memo[4][30][30];
int main() {
    while(true) {
        int W, H;
        cin >> W >> H;
        if(!W && !H) break;

        vector<vector<int> > field(H);
        for(int i = 0; i < H; ++i) {
            field[i].resize(W);
            for(int j = 0; j < W; ++j) {
                cin >> field[i][j];
            }
        }
        vector<int> cost(4);
        for(int i = 0; i < 4; ++i) {
            cin >> cost[i];
        }

        for(int dir = 0; dir < 4; ++dir) {
            for(int r = 0; r < H; ++r) {
                for(int c = 0; c < W; ++c) {
                    memo[dir][r][c] = INT_MAX;
                }
            }
        }
        int ans = -1;
        priority_queue<Tag> q;
        q.push(Tag(0, 0, 0, 0));
        memo[0][0][0] = 0;
        while(!q.empty()) {
            Tag cur = q.top();
            q.pop();
            if(cur.r == H-1 && cur.c == W-1) {
                ans = cur.cost;
                break;
            }
            if(memo[cur.dir][cur.r][cur.c] < cur.cost) continue;

            for(int act = 0; act < 4; ++act) {
                const int ncost = (field[cur.r][cur.c] == act) ? cur.cost : (cur.cost+cost[act]);
                const int nd = (cur.dir + DD[act]) % 4;
                const int nr = cur.r + DR[nd];
                const int nc = cur.c + DC[nd];
                if(in_range(0, nr, H) && in_range(0, nc, W)) {
                    if(update(memo[nd][nr][nc], ncost)) {
                        q.push(Tag(nr, nc, nd, ncost));
                    }
                }
            }
        }

        cout << ans << endl;
    }

    return 0;
}

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

using namespace std;

using int64 = long long;

struct Edge {
  int from, to;
};

vector<vector<Edge>> ReadUndirectedGraph(
    int n, int m, bool is_one_indexed=false) {
  vector<vector<Edge>> graph(n);
  for (int i = 0; i < m; i++) {
    int v1, v2;
    cin >> v1 >> v2;
    if (is_one_indexed) {
      v1--;
      v2--;
    }
    graph[v1].push_back(Edge({v1, v2}));
    graph[v2].push_back(Edge({v2, v1}));
  }
  return graph;
}

// For modular arithmetic when a modular is specified per input case.
// Verified: ABC129F
struct ModInt {
 private:
  static int64 M;
  int64 x;
 public:
  static void SetMod(int64 mod) {
    M = mod;
  }
  ModInt(int64 input_x) : x(input_x % M) {}
  ModInt() : x(0) {}
  int64 Value() { return x; }
  inline ModInt operator+(ModInt o) {
    ModInt r(*this); r += o; return r;
  }
  inline ModInt operator-(ModInt o) {
    ModInt r(*this); r -= o; return r;
  }
  inline ModInt operator* (ModInt o) {
    ModInt r(*this); r *= o; return r;
  }
  inline void operator+= (ModInt o) { x = (x + o.x) % M; }
  inline void operator-= (ModInt o) { x = (x + M - o.x) % M; }
  inline void operator*= (ModInt o) { x = (x * o.x) % M; }
};
int64 ModInt::M = 1;  // Do not forget to add this line.

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

  int n;
  int64 mod;
  cin >> n >> mod;
  ModInt::SetMod(mod);

  vector<vector<Edge>> graph = ReadUndirectedGraph(n, n - 1, true);

  vector<ModInt> dp1(n);
  vector<vector<ModInt>> v_to_cpl(n);  // Cumulative product left
  vector<vector<ModInt>> v_to_cpr(n);  // Cumulative product right

  function<void(int, int)> dfs1 = [&](int v, int parent) {
    vector<ModInt> ps;
    for (auto e : graph[v]) {
      if (e.to == parent) continue;
      dfs1(e.to, v);
      ps.push_back(dp1[e.to] + 1);
    }

    if (ps.size() == 0) {
      dp1[v] = 1;
      return;
    }

    int d = ps.size();
    auto& cpl = v_to_cpl[v];
    auto& cpr = v_to_cpr[v];
    cpl.resize(d);
    cpr.resize(d);
    cpl[0] = ps[0];
    for (int i = 1; i < d; i++) {
      cpl[i] = cpl[i - 1] * ps[i];
    }
    cpr[d - 1] = ps[d - 1];
    for (int i = d - 2; i >= 0; i--) {
      cpr[i] = cpr[i + 1] * ps[i];
    }
    dp1[v] = cpl[d - 1];
  };
  dfs1(0, -1);

  vector<ModInt> dp2(n);
  function<void(int, int, ModInt)> dfs2 =
      [&](int v, int parent, ModInt factor) {
    // cout << "v: " << v << " factor: " << factor.Value() << endl;
    
    dp2[v] = dp1[v] * factor;

    auto& cpl = v_to_cpl[v];
    auto& cpr = v_to_cpr[v];
    
    int edge_id = 0;
    for (auto e : graph[v]) {
      if (e.to == parent) continue;
      ModInt new_factor = factor;
      if (edge_id - 1 >= 0) new_factor *= cpl[edge_id - 1];
      if (edge_id + 1 < cpr.size()) new_factor *= cpr[edge_id + 1];
      new_factor += 1;
      dfs2(e.to, v, new_factor);
      edge_id++;
    }
  };
  dfs2(0, -1, 1);

  for (int i = 0; i < n; i++) {
    cout << dp2[i].Value() << endl;
  }
}


Measured memory_bytes: 27520
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main() {
    int N;
    int a[110];
    cin >> N;
    int A = 0, B = 0;
    for(int i = 0; i < N; i++)
        cin >> a[i];
    //ソート(降順)
    sort(a, a + N, greater<int>());

    for(int i = 0; i < N; i++){
        if(i%2==0) A += a[i];
        else B += a[i];
    }

    cout << A - B << endl;
    return 0;
}

Measured memory_bytes: 3564
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
int main()
{
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        a[i]--;
    }
    vector<vector<int>> nx(61, vector<int>(n, 0));
    for(int i = 0; i < n; i++)
    {
        nx[0][i] = a[i];
    }
    for(int i = 0; i < 60; i++)
    {
        for(int j = 0; j < n; j++)
        {
            nx[i+1][j] = nx[i][nx[i][j]];
        }
    }
    int pos = 0;
    for(int i = 0; i < 60; i++)
    {
        if(k >> i & 1)
        {
            pos = nx[i][pos];
        }
    }
    cout << pos+1 << endl;
}






Measured memory_bytes: 53412
while True:
    n=input()
    if n==0:break
    for i in range(n):
        x1,y1,z1,w1,x2,y2,z2,w2=map(int,raw_input().split())
        x3=x1*x2-y1*y2-z1*z2-w1*w2
        y3=x1*y2+x2*y1+z1*w2-w1*z2
        z3=x1*z2-y1*w2+x2*z1+y2*w1
        w3=x1*w2+y1*z2-y2*z1+x2*w1
        print x3,y3,z3,w3

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

int toInt(list<int> c){
	int result=0,base=1;
	for(auto it=c.begin(); it!=c.end(); it++){
		result += base * (*it);
		base*=10;
	}
	return result;
}
list<int> calc(list<int> a, list<int> b, list<int> c, int borrow, int k){
	if(!a.size()) return c;
	if(k<0) return list<int>();
	int ce=a.front()-b.front()-borrow;
	a.pop_front();
	b.pop_front();
	if(ce>=0){
		c.push_back(ce);
		return calc(a, b, c, 0, k);
	}else{
		c.push_back(10+ce);
		list<int> succ = calc(a, b, c, 1, k);
		list<int> fail = calc(a, b, c, 0, k-1);
		return toInt(succ)<toInt(fail)?fail:succ;
	}
}

int main(){
	int a,b,k;
	cin>>a>>b>>k;
	list<int> as,bs;
	for(;;){
		as.push_back(a%10);
		bs.push_back(b%10);
		a /= 10;
		b /= 10;
		if(!a) break;
	}
	cout<<toInt(calc(as,bs,list<int>(),0,k))<<endl;
}

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

int main() {
    int n; cin >> n;
    vector<Int> l(n);
    rep(i, n) {
        cin >> l[i];
    }
    int ans = 0;
    sort(l.begin(), l.end());
    for (int i = 0; i < n-2;i++) {
        for (int j = i+1; j < n-1; j++) {
            if (l[i] == l[j])
                continue;
            for (int k = j+1; k < n; k++) {
                if (l[i] == l[k] || l[j] == l[k])
                    continue;
                //printf("i=%ld, j=%ld, k=%ld\n", i, j, k);
                if ((Int)((Int)l[i]+(Int)l[j]) > (Int)l[k]) {
                    ans++;
                }
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3628
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n)         for(int i=0; i<(n); i++)
#define P pair<int, int>
#define prtd(n, var)     cout << fixed << setprecision(n) << var << "\n"

//----------------------------------------------------

int main(){
    int x, y; cin >> x >> y;
    cout << x + y/2 << endl;
}

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

template<typename T>
T Pow(T a,T b) {
    T ret = 1;
    for(int i = 0;i < b;i++) {
        ret *= a;
    }
    return ret;
}

ll mod(ll val) {
    ll res = val % MOD;
    if(res < 0) {
        res += MOD;
    }
    return res;
}

struct edge{
    int a;
    int b;
    int c;
    int d;
};

int N,M,Q;
vector<edge> vec(100);
int ret = 0;

void dfs(vector<int> cnt) {
    if(cnt.size() == N) {
        int cnt2 = 0;
        for(int i = 0;i < Q;i++) {
            if(cnt.at(vec.at(i).b) - cnt.at(vec.at(i).a) == vec.at(i).c) {
                cnt2 += vec.at(i).d;
            }
        }
        ret = max(ret,cnt2);
        return;
    }
    if(cnt.empty()) {
        for(int i = 1;i <= M;i++) {
            cnt.push_back(i);
            dfs(cnt);
            cnt.pop_back();
        }
        return;
    }
    for(int i = cnt.at(cnt.size() - 1);i <= M;i++) {
        cnt.push_back(i);
        dfs(cnt);
        cnt.pop_back();
    }
}

int main() {
    cin >> N >> M >> Q;
    vec.resize(Q);
    for(int i = 0;i < Q;i++) {
        int A,B,C,D;
        cin >> A >> B >> C >> D;
        A--;
        B--;
        vec.at(i) = edge{A,B,C,D};
    }
    vector<int> E = {};
    dfs(E);
    cout << ret << endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define inf 1000000000
#define mod 1000000007
int par[111111],ran[111111],diff_weight[111111];
void init(int n){
	rep(i,n){
		par[i]=i;
		ran[i]=0;
		diff_weight[i]=0;
	}
}
int find(int x){
	if(par[x]==x)return x;
	int r=find(par[x]);
	diff_weight[x]+=diff_weight[par[x]];
	return par[x]=r;
}
int weight(int x){
	find(x);
	return diff_weight[x];
}
bool same(int x,int y){
	return find(x)==find(y);
}
void unite(int x,int y,int w){
	w+=weight(x);
	w-=weight(y);
	x=find(x);
	y=find(y);
	if(x==y)return;
	if(ran[x]<ran[y]){
		swap(x,y);
		w*=-1;
	}
	if(ran[x]==ran[y])ran[x]++;
	par[y]=x;
	diff_weight[y]=w;
}
int diff(int x,int y){
	if(same(x,y))return weight(y)-weight(x);
	return inf;
}
int n,q;
int x,a,b,c;
signed main(){
	cin>>n>>q;
	init(n);
	while(q--){
		cin>>x;
		if(x==0){
			cin>>a>>b>>c;
			unite(a,b,c);
		}
		else{
			cin>>a>>b;
			if(diff(a,b)==inf)puts("?");
			else cout<<diff(a,b)<<endl;
		}
	}
	return 0;
}



Measured memory_bytes: 5436
#include "bits/stdc++.h"
#define ll long long
#define rep2(i,a,b) for(int i=(a);i<=(b);++i)
#define rep(i,n) rep2(i,0,n-1)
int MOD=1000000000+7;
int INF=1e6;
 
using namespace std;
string alphabet("abcdefghijklmnopqrstuvwxyz");
 
int a[270000],n,sup;
 
struct sect{
    int first;
    int last;
    int min;
  	
};
bool operator> (const sect &s1,const sect &s2){
    return s1.min>s2.min;
};
 
 
int d1[270000],d2[270000];
priority_queue<sect,vector<sect>,greater<sect>> p;
 
int search1(int (first),int (last),int k,int l,int r){
    if(r<first||l>last) return INF;
    if(first<=l&&last>=r) return d1[k];
    int leftmin=search1(first,last,k*2+1,l,(l+r)/2);
    int rightmin=search1(first,last,k*2+2,(l+r+1)/2,r);
    return min(leftmin,rightmin);
}
int search2(int (first),int (last),int k,int l,int r){
    if(r<first||l>last) return INF;
    if(first<=l&&last>=r) return d2[k];
    int leftmin=search2(first,last,k*2+1,l,(l+r)/2);
    int rightmin=search2(first,last,k*2+2,(l+r+1)/2,r);
    return min(leftmin,rightmin);
}
int search(int (a),int (b)){
    if(a%2){
        return search1(a/2,(b-1)/2,0,0,sup/2-1);
    }
    else return search2(a/2,b/2,0,0,sup/2-1);
}

int pos[210000];
void GO(){
    while(!p.empty()){
        sect s=p.top();
        p.pop();
        int min2;
        min2=search(pos[s.min]+1,s.last);
      	sect t;
        if(s.first!=pos[s.min]){
            t={s.first,pos[s.min]-1,search(s.first,pos[s.min]-1)};
            p.push(t);
          	
        }
        if(pos[s.min]+1!=pos[min2]){
            t={pos[s.min]+1,pos[min2]-1,search(pos[s.min]+1,pos[min2]-1)};
            p.push(t);
          
        }
        if(pos[min2]!=s.last){
            t={pos[min2]+1,s.last,search(pos[min2]+1,s.last)};
            p.push(t);
          
          
        }
        printf("%d %d ",s.min,min2);
    }
}
main(){
    cin>>n;
    sup=1;
    while(sup<n)
    sup*=2;
    rep(i,n){
        scanf("%d",&a[i]);
        pos[a[i]]=i;
        if(i%2){
            d1[sup/2-1+i/2]=a[i];
        }
        else{
            d2[sup/2-1+i/2]=a[i];
        }
    }
    rep2(i,n,sup-1){
        if(i%2){
            d1[sup/2-1+i/2]=INF;
        }
        else{
            d2[sup/2-1+i/2]=INF;
        }
    }
    for(int i=sup/2-2;i>=0;i--){
        d1[i]=min(d1[i*2+1],d1[i*2+2]);
        d2[i]=min(d2[i*2+1],d2[i*2+2]);
    }
    sect temp{0,n-1,d2[0]};
  	p.push(temp);
    GO();
  return 0;
}

Measured memory_bytes: 5752
{-# LANGUAGE FlexibleContexts #-}

module Main where

import Debug.Trace
import Data.List
import qualified Data.Set as Set
import qualified Data.Sequence as Seq
import qualified Data.ByteString.Char8 as B
import Data.Int
import Data.Word
import Data.Char
import Data.Bits
-- import Data.Array
import Data.Array.Unboxed
-- import Data.Array.IO
import Data.Maybe
-- import qualified Data.Map as M
import qualified Data.IntMap as M
-- import Control.Monad.ST
-- import Data.STRef
import Data.Ord
import Data.Functor
import Control.Applicative
import Control.Monad
import Text.Printf

solver :: B.ByteString -> B.ByteString -> [Int]
solver w s = iter 0 0 [] where
    iter j k ac
        | j >= ls = reverse ac
        | B.index s j == B.index w k = if k + 1 >= lw
                                            then iter (j+1) (tbl!(k+1)) ((j-k):ac)
                                            else iter (j+1) (k+1) ac
        | tbl!k < 0 = iter (j+1) (tbl!k +1) ac
        | otherwise = iter j (tbl!k) ac
    ls = B.length s
    lw = B.length w
    tbl :: UArray Int Int
    tbl = iter 1 0 $ array (0, lw) [(0,-1)] where
        iter p c t 
            | p >= lw = t // [(p, c)]
            | B.index w p == B.index w c = iter (p+1) (c+1) (t // [(p, t!c)])
            | otherwise = iter (p+1) (c'+1) t' where
                c' = iter c where
                    iter c
                        | c < 0 || B.index w p == B.index w c = c 
                        | otherwise = iter (t'!c)
                t' = t // [(p, c)]

main :: IO() 
main = do
    s <- B.getLine
    w <- B.getLine
    mapM_ print $ solver w s



Measured memory_bytes: 152304
#include<stdio.h>
int main()
{
	int A,B,C,D,m,n;
	scanf("%d",&A);
	scanf("%d",&B);
	scanf("%d",&C);
	scanf("%d",&D);
	if(A<B)m=A;else m=B;
	if(C<D)n=C;else n=D;
	printf("%d",m+n);
 } 

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

int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	int d[1000];
	for(int i=0;i<n;i++) scanf("%d",&d[i]);
	int c[1000];
	for(int j=0;j<m;j++) scanf("%d",&c[j]);
	ll dp[1001][1001];//i??\??§j?????§??????????°?
	for(int i=0;i<=1000;i++) for(int j=0;j<=1000;j++) dp[i][j]=100000000000;
	for(int i=0;i<m;i++) dp[i][0]=0;
	for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) dp[i][j]=min(dp[i-1][j],dp[i-1][j-1]+d[j-1]*c[i-1]);
	printf("%lld\n",dp[m][n]);
}

Measured memory_bytes: 9024
#include <bits/stdc++.h>
using namespace std;
int cnt[10][10];
int sx[]={-1,0,0,0,1},mx[]={-1,-1,-1,0,0,0,1,1,1},lx[]={-2,-1,-1,-1,0,0,0,0,0,1,1,1,2};
int sy[]={0,1,0,-1,0},my[]={1,0,-1,1,0,-1,1,0,-1},ly[]={0,1,0,-1,2,1,0,-1,-2,1,0,-1,0};
bool isInside(int y,int x){
	if(y<0||10<=y)	return false;
	if(x<0||10<=x)	return false;
	return true;
}
int main(){
	memset(cnt,0,sizeof(cnt));
	int x,y,s;
	while(scanf("%d,%d,%d",&x,&y,&s)!=EOF){
		switch(s){
			case 1:
				for(int i=0;i<5;i++){
					if(isInside(y+sy[i],x+sx[i]))	cnt[y+sy[i]][x+sx[i]]++;
				}
				break;
			case 2:
				for(int i=0;i<9;i++){
					if(isInside(y+my[i],x+mx[i]))	cnt[y+my[i]][x+mx[i]]++;
				}
				break;
			case 3:
				for(int i=0;i<13;i++){
					if(isInside(y+ly[i],x+lx[i]))	cnt[y+ly[i]][x+lx[i]]++;
				}
				break;
			case -1:
				goto end;
		}
	}
	end:;
	int big=0,blank=0;
	for(int i=0;i<10;i++){
		for(int j=0;j<10;j++){
			if(cnt[i][j]==0)	blank++;
			big=max(big,cnt[i][j]);
		}
	}
	cout<<blank<<endl;
	cout<<big<<endl;
	return 0;
}

Measured memory_bytes: 3044
#include <bits/stdc++.h>
using namespace std;
const int M = 998244353,N = 5000;
int n,k,fact[N],inv[N],p[N];
int power(int base,int to){
    int ret = 1;
    while(to){
        if(to&1)ret = ret*1LL*base%M;
        to>>=1;
        base = base*1LL*base%M;
    }
    return ret;
}
void add(int &a,int b){
    a+=b;
    if(a >= M)a-=M;
}
int find(int n,int a,int b){
    int ret = 0;
    ret = fact[n + a + b - 1]*1LL*inv[a + b - 1]%M;
    ret = ret*1LL*inv[n]%M;
    ret = ret*1LL*p[b]%M;
    return ret;
}
int main(){
    //freopen("readin.txt","r",stdin);
    scanf("%d%d",&k,&n);
    fact[0] = inv[0] = p[0] = 1;
    for(int i = 1;i < N;i++)fact[i] = fact[i - 1]*1LL*i%M,inv[i] = inv[i - 1]*1LL*power(i,M - 2)%M,add(p[i],p[i - 1] + p[i - 1]);
    for(int at = 2;at <= 2*k;at++){
        int two = 0,one = 0,ans = 0;
        for(int i = 1;i <= k;i++){
            if(at - i == i)continue;
            if(at - i < 1 || at - i > k)one++;
            else two++;
        }
        two>>=1;
        for(int i = 0;i <= two;i++){
            if(i > n)break;
            int x = (fact[two]*1LL*inv[i]%M)*inv[two - i]%M;
            if(one + i)add(ans,x*1LL*find(n - i,one,i)%M);
            if(!(at&1) && n - i > 0 && one + i)add(ans,x*1LL*find(n - 1 - i,one,i)%M);
        }
        printf("%d\n",ans);
    }
}

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

#define each(i, c) for (auto& i : c)
#define mkp(a, b) make_pair(a, b)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> Pll;
const ll MOD = 1e9+7;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << ": " << p.second << ")"; return os; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ", "; os << ")"; return os; }
template<typename K, typename V> ostream& operator << (ostream& os, map<K, V> m) { os << "{"; each (i, m) os << i << ", "; os << "}"; return os; }

int main() {
  ll n;
  cin >> n;

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

  ll q, k;
  cin >> q >> k;
  k--;
  vector<ll> x(q);
  vector<ll> y(q);
  for (ll i = 0; i < q; ++i) {
    cin >> x[i] >> y[i];
    x[i]--;
    y[i]--;
  }

  vector<ll> ds(n, -1);
  queue<ll> que;
  que.push(k);
  ds[k] = 0;
  while (!que.empty()) {
    auto v = que.front();
    que.pop();

    each (i, g[v]) {
      ll next = i.first;
      ll cost = i.second + ds[v];
      if (ds[next] >= 0) continue;
      ds[next] = cost;
      que.push(next);
    }
  }

  for (ll i = 0; i < q; ++i) {
    cout << ds[x[i]] + ds[y[i]] << endl;
  }

  return 0;
}


Measured memory_bytes: 13452
int main(void)
{
  int A,B;
  scanf("%d %d",&A,&B);
  if(A <= 5) printf("0\n");
  else if(A >= 6 && A <= 12) printf("%d\n",B / 2);
  else if(A >= 13) printf("%d\n",B);
  return 0;
}

Measured memory_bytes: 128
W, H, N = map(int, input().split())
points = [list(map(int, input().split())) for i in range(N)]
width = [0, W]
hight = [0, H]

for i in range(N):
    if points[i][2] == 1 and points[i][0] > width[0]:
        width[0] = points[i][0]
    elif points[i][2] == 2 and points[i][0] < width[1]:
        width[1] = points[i][0]
    elif points[i][2] == 3 and points[i][1] > hight[0]:
        hight[0] = points[i][1]
    elif points[i][2] == 4 and points[i][1] < hight[1]:
        hight[1] = points[i][1]
    if width[0] >= width[1] or hight[0] >= hight[1]:
        print(0)
        exit()

area = (width[1] - width[0]) * (hight[1] - hight[0])
print(area)


Measured memory_bytes: 3064
N, K = map(int, input().split())

M = N*(N-1)//2-K


if M < N-1:
    print(-1)
    exit()

print(M)
for i in range(1, N):
    for j in range(i+1, N+1):
        print(i, j)
        M -= 1
        if M == 0:
            exit()


Measured memory_bytes: 42736
#include <cstdio>

template<class T>void fr(T &a) {
    T w=0,s=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-')s=-1;c=getchar();}
    while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();
    a=w*s;
}
template<class T>T fr() {T a;fr(a);return a;}
#define R() fr<int>()

char str[110],s1[110],s2[110];

int main() {
    int n=R();
    if(n%2)return !printf("No\n");
    scanf("%s",str+1);
    for(int i=1;i<=n/2;i++) s1[i]=str[i];
    for(int i=n/2+1;i<=n;i++) s2[i-n/2]=str[i];
    for(int i=1;i<=n/2;i++) 
        if(s1[i]!=s2[i])return !printf("No\n");
    return !printf("Yes\n");
}

Measured memory_bytes: 888
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
const long long mod = 1e9+7;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};
const int ddx[4] = {1,1,-1, -1};
const int ddy[4] = {1,-1,-1,1};
//////////////////////////////////

int main(){
  int n; cin >> n;
  cout << (n+1)/2 << endl;

  return 0;
}

// EOF



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

int main()
{
	long double a, b, c;
	cin >> a >> b >> c;

	if (c - (a + b + 2 * sqrt(a) * sqrt(b)) > 0) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}
}


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

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

    int n, K;
    cin >> n >> K;
    int ok = 1e18, ng = 0;
    auto check = [&](int m) {
        int cur = m;
        REP(i, n) {
            if (cur == 0) return false;
            cur -= (cur + K - 1) / K;
        }
        return true;
    };
    while (abs(ok - ng) > 1) {
        int m = (ok + ng) / 2;
        (check(m) ? ok : ng) = m;
    }

    cout << ok - 1 << endl;
}



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

using namespace std;

int main() {
  int a[3][3];
  string ans = "No";
  
  for(int i = 0; i < 3; i++) {
    for(int j = 0; j < 3; j++) {
      cin >> a[i][j];
    }
  }
  int n;
  cin >> n;
  int b[n-1];
  for(int k = 0; k < n; ++k) {
    cin >> b[k];
  }
  
  for(int l = 0; l < 3; l++) {
    for(int o = 0; o < 3; o++) {
      for(int p = 0; p < n; p++) {
        if ( a[l][o] == b[p]) {
          a[l][o] = 0;
        }
      }
    }
  }

  if (a[0][0] == 0 && a[1][0] == 0 && a[2][0] == 0) {
    ans = "Yes";
  } else if (a[0][1] == 0 && a[1][1] == 0 && a[2][1] == 0) {
    ans = "Yes";
  } else if (a[0][2] == 0 && a[1][2] == 0 && a[2][2] == 0) {
    ans = "Yes";
  } else if (a[0][0] == 0 && a[0][1] == 0 && a[0][2] == 0) {
    ans = "Yes";
  } else if (a[1][0] == 0 && a[1][1] == 0 && a[1][2] == 0) {
    ans = "Yes";
  } else if (a[2][0] == 0 && a[2][1] == 0 && a[2][2] == 0) {
    ans = "Yes";
  }

  if (a[0][0] == 0 and a[1][1] == 0 and a[2][2]== 0 ) ans = "Yes";
  if (a[0][2] == 0 and a[1][1] == 0 and a[2][0]== 0 ) ans = "Yes";

  cout << ans << endl;
}

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

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

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

    sort(h, h + n, greater<int>());

    ll ans = 0;
    if (k >= n) {
        ans = 0;
    } else {
        for (int i = k; i < n; ++i) {
            ans += h[i];
        }
    }

    cout << ans << endl;
    return 0;
}

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

//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)
//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();}

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

typedef long long LL;
const LL mod=1000000007;
#define MAX 10000
#define NIL -1
const double PI  = acos(-1.0);
const int INF = 1e9 + 7;
//-------------------------------------------


int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    LL x, y;
    cin >> x >> y;

    //int a[MAX] = {};
    int ans = 0;

    for( LL i = x; i <= y; ){
        ans++;
        i *= 2;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cmath>
using namespace std;

int main()
{
	int n;
	int p[20];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> p[i];
	}

	int count = 0;
	for (int i = 0; i < n - 2; i++) {
		if (p[i] < p[i + 1] && p[i + 1] < p[i + 2]) {
			count++;
		}
		else if (p[i] > p[i + 1] && p[i + 1] > p[i + 2]) {
			count++;
		}
	}

	cout << count << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <bitset>
#include <iomanip>
#include <deque>
#include <tuple>
#include <algorithm>

using namespace std;

int main()
{
    int a, b, c, d;

    cin >> a >> b >> c >> d;

    if (abs(a-c) <= d) {
        cout << "Yes" << endl;
        return (0);
    }

    if (abs(a-b) <= d && abs(b-c) <= d) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
/*#ifndef LOCAL_RUN
    #pragma GCC optimize("Ofast")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC optimize("fast-math")
    #pragma GCC target("avx2,tune=native")
#endif*/
#define X first
#define Y second
using namespace std;

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

const int N = 2e5+228;

vector<int> graph[N];
bool used[N];
int sz;

void dfs(int v)
{
    ++sz;
    used[v] = true;
    for (int u: graph[v]) {
        if (used[u]) continue;
        dfs(u);
    }
}

int main()
{
    #ifdef LOCAL_RUN
        freopen("input.txt", "r", stdin);
    //#else
        //freopen("cowcode.in", "r", stdin);
        //freopen("cowcode.out", "w", stdout);
    #endif
	ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            sz = 0;
            dfs(i);
            ans = max(ans, sz);
        }
    }
    cout << ans;

    return 0;
}

// 272472LF


Measured memory_bytes: 20984