akhauriyash/Code-Regression huggingface dataset:
def insertion_sort(array, element_number):
    for i in range(element_number):
        v = array[i]
        j = i - 1

        while(j>=0 and array[j] > v):
            array[j+1] = array[j]
            j = j - 1

        array[j+1] = v

        for k in range(element_number):
            if k < element_number-1:
                print(str(array[k]) + ' ', end='')
            else:
                print(str(array[k]), end='')

        print('\n', end='')

def test():
    element_number = int(input())
    input_array = list(map(int, input().split()))

    insertion_sort(input_array, element_number)

if __name__ == '__main__':
    test()

Measured memory_bytes: 8032
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n, w;
    cin >> n >> w;
    long long dp[n + 5][w + 5];
    vector<long long>v(n + 5), val(n + 5);
    for(long long i = 1; i <= n; i++){
        cin >> v[i] >> val[i];
    }
    for(long long i = 0; i <= n; i++){
        for(long long j = 0; j <= w; j++){
            dp[i][j] = 0;
        }
    }
    for(long long i = 1; i <= n; i++){
        for(long long j = 1; j <= w; j++){
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
            dp[i][j] = max(dp[i][j], dp[i][j - 1]);
            if(j >= v[i]){
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + val[i]);
            }
        }
    }
    cout << dp[n][w];
    return 0;
}

Measured memory_bytes: 80768
#include<iostream>

using namespace std;

int main(void) {

	int i,n, a,max, min;
	long sum ;

	cin >> n ;

	cin >> a;

	sum = a;
	max = a;
	min = a;

	for (i = 1; i < n; i++)
	{
		cin >> a;
		sum = sum + a;

		if (max < a)
			max = a;
		if (min > a)
			min = a;

	}

	cout << min << " " << max << " " << sum << endl;
	return 0;
}


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

bool isHead[10];
int var[10], coe[10];
vector<char> ch;

typedef pair<int,int> P; // first=sum, second=state
vector<P> va,vb;

void solve( int dep, int st, int en, int sum, int state){
  if( dep>en ){
    if( st==0 ) va.push_back( P(sum,state) );
    else        vb.push_back( P(sum,state) );
  }else{ // coe[dep] の係数をiとする
    for( int i=0;i<10;i++ ){
      if( !i && isHead[dep] ) ++i;

      int nState = state | (1<<i);
      if( nState==state ) continue;
      solve( dep+1, st, en, sum+coe[dep]*i, nState );
    }
  }
}

int main(){
  int n, ans;
  string s;

  while( cin>>n && n ){
    ch.clear();
    for( int j=0;j<10;j++ ){ coe[j]=0; isHead[j]=false; }

    for( int i=1;i<n;i++ ){
      cin >> s;
      for( int j=s.length()-1,k=1,l;j>=0;j--,k*=10 ){
	for( l=0;l<(int)ch.size() && ch[l]!=s[j];l++ );
	if( l==(int)ch.size() ) ch.push_back( s[j] );
	coe[l] += k;
	if( j==0 && s.length()>1 ) isHead[l]=true;
      }
    }
    cin >> s; // 右辺の文字列
    for( int j=s.length()-1,k=1,l;j>=0;j--,k*=10 ){
      for( l=0;l<(int)ch.size() && ch[l]!=s[j];l++ );
      if( l==(int)ch.size() ) ch.push_back( s[j] );
      coe[l] -= k;
      if( j==0 && s.length()>1 ) isHead[l]=true;
    }

    bool f;
    do{
      f=false;
      for( unsigned int i=1;i<ch.size();i++ ){
	if( coe[i-1]<coe[i] ){
	  swap( coe[i-1],coe[i] );
	  swap( isHead[i-1],isHead[i] );
	  f=true;
	}
      }
    }while( f );

    va.clear();
    vb.clear();
    int l=ch.size()/2;
    solve( 0,0,l-1,0,0 );// solve( int dep, int st, int en, int sum, int state)
    solve( l,l,ch.size()-1,0,0 );

    /*    
    cout << "ch.size="<<ch.size() 
	 << " va.size="<<va.size() << " vb.size="<<vb.size() 
	 << " l="<<l<<endl;
    */


    sort( va.begin(),va.end() );
    sort( vb.begin(),vb.end() );
    
    ans=0;
    vector<P>::iterator it;
    for( unsigned int i=0;i<va.size();i++ ){
      // vb を二分探索
      int vai = -va[i].first;
      it=lower_bound( vb.begin(), vb.end(), P(vai,0) );
      
      while( it!=vb.end() ){
	P p = *it;
	if( p.first!=vai )
	  break;
	if( va[i].second & p.second ){
	}else
	  ans++;
	it++;
      }
    }
    cout << ans << endl;
  }

  return 0;
}

Measured memory_bytes: 1540
/*
Roses are red
Memes are neat
All my test cases time out
Lmao yeet
**************************
Time to solve: 
*/
import java.util.*;
import java.io.*;

   public class Main
   {
      public static void main(String args[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         int[][] arr = new int[N][3];
         for(int i=0; i < N; i++)
         {
            st = new StringTokenizer(infile.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
            arr[i][2] = Integer.parseInt(st.nextToken());
         }
         int[][] dp = new int[N][3];
         for(int i=0; i < 3; i++)
            dp[0][i] = arr[0][i];
         for(int i=0; i < N-1; i++)
            for(int par=0; par < 3; par++)
               for(int next=0; next < 3; next++)
               {
                  if(par == next)
                     continue;
                  dp[i+1][next] = Math.max(dp[i+1][next], dp[i][par]+arr[i+1][next]);
               }
         int res = 0;
         for(int a: dp[N-1])
            res = Math.max(res, a);
         System.out.println(res);
      }
   }

Measured memory_bytes: 48284
#include <bits/stdc++.h>
using namespace std;
int main(){
  string abc;
  cin >> abc;
  if(abc[0] != abc[1] && abc[1] != abc[2] && abc[2] != abc[0]){
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


n, m = map(int, readline().split())
h = list(map(int, readline().split()))
ab = [list(map(int, input().split())) for _ in range(m)]
l = [1]*n
for i in range(m):
    if h[ab[i][0] - 1] < h[ab[i][1] - 1]:
        l[ab[i][0] - 1] = 0
    elif h[ab[i][0] - 1] > h[ab[i][1] - 1]:
        l[ab[i][1] - 1] = 0
    else:
        l[ab[i][0] - 1] = 0
        l[ab[i][1] - 1] = 0
print(sum(l))

Measured memory_bytes: 31900
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>
#include<map>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
using P=pair<int,int>;
using lint=long long;
using ll=long long;
const lint inf=1e18+7;
const int MOD=1000000007;
signed main(){
  int a;cin>>a;
  cout<<a+a*a+a*a*a<<"\n";
  return 0;
}


Measured memory_bytes: 3592
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl
#define trace2(x, y) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z) cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define sa(a,n) for(int i =0 ; i<n ; i++) cin>>a[i]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define scan() int n; cin>>n ; int a[n]; for(int i = 0 ; i<n ; i++) cin>>a[i]
#define print(a,n) for(int i = 0 ; i < n ; i++) cout<<a[i]<<' '
using namespace std;
template <typename T, typename U>
T max(T x, U y)
{
    return x>y ? x : y;
}
template <typename T, typename U>
T min(T x, U y)
{
    return x<y ? x : y;
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n;cin >>n;
    double a[n];
    for (int i = 0; i < n; ++i)
    {
    	cin >>a[i];
    }
    double dp[n+1][n+1];
    dp[0][1]=0;
    dp[0][0]=0;double ans=0;
    for (int i = 0; i <= n; ++i)
    {
    	for (int j = 0; j <= i; ++j)
    	{
    		if(i==0 and j==0)dp[i][j]=1;
    		else if(i==0)dp[i][j]=0;
    		else if(j==0)dp[i][j]=dp[i-1][j]*(1-a[i-1]);
    		else
    		dp[i][j]=dp[i-1][j-1]*a[i-1]+dp[i-1][j]*(1-a[i-1]);
    		//if(j>i-1-j)ans+=dp[i][j];
    	}
    }
    for (int i = 0; i <= n; ++i)
    {
    	if(i>n-i)ans+=dp[n][i];
    }
    cout <<setprecision(16) << ans;
    }

Measured memory_bytes: 70400
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(ll i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;

int main() {
  ll n;
  cin >> n;
  ll ans = 0;
  rep(i, n) ans += (i + 1) * (n - i);
  rep(i, n - 1) {
    ll u, v;
    cin >> u >> v;
    if(u > v) swap(u, v);
    ans -= u * (n - v + 1);
  }
  cout << ans << endl;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); i++)
typedef long long ll;
const int mod = 1e9 + 7;

int main(){

    ll n;
    cin >> n;

    if(n % 2 == 1){
        cout << 0 << endl;
        return 0;
    }
    ll d = 10;
    ll ans = n / d;
    while(n / d > 0){
        d *= 5;
        ans += n / d;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std ;
int main(){
    /*int a;
    string s;
    cin>>a>>s;
    if (a<3200) cout<<"red\n";
    else cout<<s<<endl;*/
    int n;
    float sum=0.0;
    cin>>n;
    float a[n];
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++){
        sum += (1/a[i]);
    }
    cout<<1/sum<<endl;

}

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

int main(){
    ll a,b,c;cin>>a>>b>>c;
    
    ll ans = min(c,b+a)+b;
    
    if(c-(b+a)>0)ans++;
    
    cout << ans << endl;
    
    
    return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	int n; scanf("%d", &n);
	std::map<std::string, i64> mp;
	for(int i = 0; i < n; i++) {
		std::string s; cin >> s;
		sort(begin(s), end(s));

		mp[s]++;
	}
	
	i64 ans = 0;
	for(auto v: mp) ans += v.second * (v.second - 1) / 2;
	printf("%lld\n", ans);
	return 0;
}


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

using namespace std;
int ans = 0;

void selectionSort(vector<int>& vec)
{
	for (int i = 0; i < vec.size() - 1; ++i)
	{
		int minj = i;
		bool flag = false;
		for (int j = i; j < vec.size(); ++j)
		{
			if (vec[j] < vec[minj])
			{
				minj = j;
				flag = true;
			}
		}
		if (flag)
		{
			int temp = vec[i];
			vec[i] = vec[minj];
			vec[minj] = temp;
			++ans;
		}
	}
}

void solve()
{
	int n;
	cin >> n;
	vector<int> vec(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> vec[i];
	}
	selectionSort(vec);
	for (int i = 0; i < n - 1; ++i)
	{
		cout << vec[i] << " ";
	}
	cout << vec[vec.size() - 1] << endl;
	cout << ans << endl;
}

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

Measured memory_bytes: 1196
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repf(i, j, n) for (int i = (j); i < (n); i++)
#define repr(i, n) for (int i = (n)-1; i >= 0; i--)

signed main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto&& u : a) cin >> u;
  vector<int> b;
  b.push_back(a[0]);
  for (int i = 1; i < n; i++) {
    int x = lower_bound(begin(b), end(b), a[i]) - begin(b);
    if (x == 0)
      b.insert(b.begin(), a[i]);
    else
      b[x - 1] = a[i];
  }
  cout << b.size() << endl;
}

Measured memory_bytes: 2168
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] head = br.readLine().split(" ");
    int h = Integer.parseInt(head[0]);
    int w = Integer.parseInt(head[1]);
    int m = Integer.parseInt(head[2]);
    int[] cntH = new int[h];
    int[] cntW = new int[w];
    Arrays.fill(cntH, 0);
    Arrays.fill(cntW, 0);
    Target[] targets = new Target[m];
    for (int i = 0; i < m; i++) {
      String[] data = br.readLine().split(" ");
      int posH = Integer.parseInt(data[0]) - 1;
      int posW = Integer.parseInt(data[1]) - 1;
      cntH[posH]++;
      cntW[posW]++;
      targets[i] = new Target(posH, posW);
    }
    br.close();
    int maxCntH = Arrays.stream(cntH).max().getAsInt();
    long maxLinesH = Arrays.stream(cntH).filter(i -> i == maxCntH).count();
    int maxCntW = Arrays.stream(cntW).max().getAsInt();
    long maxLinesW = Arrays.stream(cntW).filter(i -> i == maxCntW).count();

    long intersection = maxLinesH * maxLinesW;
    for (Target target : targets) {
      if (cntH[target.posH] == maxCntH && cntW[target.posW] == maxCntW) {
        intersection--;
      }
    }
    System.out.println(intersection > 0 ? maxCntH + maxCntW : maxCntH + maxCntW - 1);
  }
}

class Target {

  int posH, posW;

  Target(int posH, int posW) {
    this.posH = posH;
    this.posW = posW;
  }
}


Measured memory_bytes: 68548
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         fozubaoyou    pass System Test!
*/
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define int long long
#define pb push_back
using ll = long long;
using namespace std;

signed main(){
//1794 -> 1479
  vector<int> a;
  REP(i,4){
    int t;
    cin >> t;
    a.pb(t);
  }
  sort(all(a));
  if(a[0] == 1 && a[1] == 4 && a[2] == 7 && a[3] == 9){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
  
}


Measured memory_bytes: 764
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <istream>
#include <iterator>
#include <sstream>
#include <list>
#include <map>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>

#define BR "\n"
#define REP(i, n) for(int (i)=0;(i)<(n);++(i))
#define ALL(cont) begin(cont),end(cont)
#define AS_MOD(a, b) ((((a) % (b) ) + (b)) % (b))
#define FEACH(it, cont) for(auto (it) = begin(cont); it!=end(cont);++it)
#define FEACHR(it, cont) for(auto (it) = rbegin(cont); it!=rend(cont);++it)
#define pb push_back
#define pob pop_back
#define is insert
#define fi first
#define se second
#define getll() ([](){ll s;scanf("%lld", &s);return s;})()
#define getld() ([](){ld s;scanf("%Lf", &s);return s;})()
#define prl(P) printf("%lld", P)
#define prd(P) printf("%.10Lf", P)
#define pr(P) printf(P)
#define MAX(V, T) V=max(V,T)

#define DumpArray(cont, from, to) for(int __i=from;__i<to;++__i) {cout<<"(" <<__i<<": " << cont[__i]<<")";} cout<<endl;

/*
 * ***_bound(6)
 * 5 6 6 6 6 6 7 7 7
 *   ^lower    ^upper
 * void reverse(c.begin(), c.end())
 *
 * graph
 * seg tree
 * dp
 * brute force
 */
struct Comparator{
    int operator()(int l, int r) const {
        return r<l;
    }
};
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
//set<int, Comparator> S;
ll N;
vi P,Q;
ll f(ll n){
    return n==1?1:n*f(n-1);
}
ll Rank(vi v) {
    set<int> S;
    ll ret=0;
    for(int i=0;i<N;++i) S.insert(i+1);
    for(int i=0;i<N-1;++i) {
        ll k=distance(S.begin(),S.lower_bound(v[i]));
        ret+=f(N-i-1)*k;
        S.erase(v[i]);
    }
    return ret;
}
int main() {
    cin >> N;
    P.resize(N);Q.resize(N);
    REP(i,N) cin >> P[i];
    REP(i,N) cin >> Q[i];
    cout << abs(Rank(P)-Rank(Q)) << endl;
    return 0;
}


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

const int up = 1;
const int flat = 0;
const int down = -1;

int main() {
    uint N;
    cin >> N;
    vector<int> A(N, 0);
    for (auto &a: A) cin >> a;

    int split = 1;
    int direction = flat;
    for (size_t i=0; i<A.size()-1; ++i) {
        if (A[i] > A[i+1]) {
            if (direction == up) {
                ++split;
                direction = flat; // まだわからない
            }
            else if (direction == flat) {
                direction = down;
            }
        }
        else if (A[i] < A[i+1]) {
            if (direction == down) {
                ++split;
                direction = flat;
            }
            else if (direction == flat) {
                direction = up;
            }
        }
    }
    cout << split << endl;
}

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

using namespace std;

typedef long long ll;

int main(){
    int k;
    string s;
    cin >> k >> s;
    if(s.size() <= k){
        cout << s << '\n';
    }else{
        cout << s.substr(0, k) << "..." << '\n';
    }
}

Measured memory_bytes: 3596
#include<stdio.h>
#define N 100

int bubble(int, int);

int main(){
  
  int array[N], i, j, temp, num, cnt = 0, k;
  
  scanf("%d",&num);

  for(i = 0 ; i < num; i++)scanf("%d",&array[i]);

  for(i = 0; i < num; i++)
    {
      for(j = 0; j < num - i - 1; j++)
	{
	  if(bubble(array[j],array[j + 1]) == 1)
	    {
	      temp = array[j + 1];
	      array[j + 1] = array[j];
	      array[j] = temp;
	      cnt++;
	    }
	  /*for(k = 0; k < num; k++)
	    {
	      printf("%d",array[k]);
	      printf(" ");
	      if(k == num - 1)printf("\n");
	    }
	  */
	}
    }
  
  for(i = 0; i < num; i++)
    {
      printf("%d",array[i]);
      if(i == num - 1){
	printf("\n");
	break;
      }
      printf(" ");
    }

  printf("%d\n",cnt);
  
  return 0;
}

int bubble(int a, int b)
{
  if(a > b)return 1;
  else return 0;
}



Measured memory_bytes: 2048
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
map< pair<string,string> , ll >mp[2];
void solve(string s,ll idx,string r,string b,ll t){
    if(idx==s.size()){
        if(t==0)mp[t][{r,b}]++;
        else mp[t][{b,r}]++;
        return;
    }
    solve(s,idx+1,r+s[idx],b,t);
    solve(s,idx+1,r,b+s[idx],t);
}
int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n;cin>>n;
    string s;cin>>s;
    solve(s.substr(0,n),0,"","",0);

    s = s.substr(n);
    reverse(s.begin(),s.end());
    solve(s,0,"","",1);

    ll ans = 0;
    for(auto &ele:mp[0])ans+=ele.second*mp[1][ele.first];
    cout<<ans;
}




Measured memory_bytes: 104192
#include <cstdio>
#include <cctype>
#include <array>
#include <unordered_set>
#include <queue>
using namespace std;

#define si static inline
#define gcu getchar_unlocked
si int in() {
	int n = 0, c = gcu();
	// bool minus = false; if (c == '-') minus = true, c = gcu();
	do {n = 10 * n + (c - '0'), c = gcu();} while (c >= '0');
	return n; }
	// return minus ? -n : n; }
si void scan(char *s) {while (!isspace(*s++ = gcu()));}
#define pcu putchar_unlocked
#define svo si void out
template <typename T>
svo(T n) {
	static char buf[20];
	char *p = buf;
	//if(n < 0) pcu('-'), n *= -1;
	if (!n) *p++ = '0';
	else while (n) *p++ = n % 10 + '0', n /= 10;
	while (p != buf) pcu(*--p); }
svo(const char *s){while(*s)pcu(*s++);}
svo(char *s){while(*s)pcu(*s++);}
svo(char c){pcu(c);}
//template <typename T>
//svo(vector<T> &v){for(T &x:v)out(' '),out(x);out('\n');}
//svo(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);out('\n');}
template <typename head, typename... tail>
svo(head&& h, tail&&... t){out(h);out(move(t)...);}
#undef svo
#undef si

struct board {
	enum {size = 3};
	struct pos {int r, c;};
	typedef array<array<int, size>, size> arr;

	arr b;
	pos p;
	int f, g, h;

	void read() {
		for (int i = 0; i < size; i++)
			for (int j = 0; j < size; j++) {
				b[i][j] = in();
				if (!b[i][j])
					p.r = i, p.c = j;
			}
		g = 0;
		f = h = hn(b);
	}

	void print() {
		for (auto &r: b) {
			for (int &c: r)
				out(&c == &r[0]?"":" ", c);
			out('\n');
		}
		out('\n');
	}

	static int hn(const arr &a) {
		int l = 0;
		for (int i = 0; i < size; i++)
			for (int j = 0; j < size; j++) {
				int k = a[i][j] ? a[i][j] - 1 : size * size - 1;
				l += abs(i - k / size) + abs(j - k % size);
			}
		return l;
	}

	static int key(const arr &a) {
		int k = 0;
		for (auto &r: a)
			for (int c: r)
				k = (k * 10) + c;
		return k;
	}

	int solver() {
		static const pos to[] = {-1, 0, 0, -1, 1, 0, 0, 1};
		unordered_set<int> m;
		priority_queue<board> q;
		q.push(*this);
		while (!q.empty()) {
			board a = q.top();
			q.pop();
			int k = key(a.b);
			if (m.count(k))
				continue;
			m.insert(k);
			if (!a.h)
				return a.g / 2;
			for (pos o: to) {
				o.r += a.p.r, o.c += a.p.c;
				if (0 <= o.r && o.r < size && 0 <= o.c && o.c < size) {
					board c = a;
					swap(c.b[a.p.r][a.p.c], c.b[o.r][o.c]);
					c.g += 2;
					c.h = hn(c.b);
					c.f = c.g + c.h;
					c.p = o;
					q.push(c);
				}
			}
		}
		return -1;
	}
};

bool operator < (const board &a, const board &b) {
	return a.f > b.f;
}

int main() {
	board b;
	b.read();
	out(b.solver(), '\n');
}



Measured memory_bytes: 13048
//
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define speed ios::sync_with_stdio(false)
using namespace std;

string gs(char x){
    string s(1,x);
    return s;
}

int main()
{
	speed;
	
	ll n,k;
	cin>>n>>k;
	if(n%k){
		cout<<1;

	}
	else
		cout<<0;

	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=(a);i<(b);i++)
typedef long long ll;
using namespace std;
const int INF=1e9, MOD=1e9+7;
const int MAX_N=10000;
int n;
string s;

int main(){
	cin >> n >> s;
	
	bool tmp[n+2], f=false;
	REP(i,0,4){
		tmp[0]=(i&1); tmp[1]=((i>>1)&1);
		REP(j,1,n){
			if(s[j]=='o'){
				tmp[j+1]=tmp[j]^tmp[j-1];
			}else{
				tmp[j+1]=not(tmp[j]^tmp[j-1]);
			}
		}
		if(tmp[n]==tmp[0]){
			if(s[0]=='o') tmp[n+1]=tmp[n]^tmp[n-1];
			else tmp[n+1]=not(tmp[n]^tmp[n-1]);
			if(tmp[n+1]==tmp[1]){
				f=true;
				break;
			}
		}
	}
	
	if(f) REP(i,0,n) cout << (tmp[i]?'W':'S');
	else cout << -1;
	
	cout << endl;
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define COUT(x) cout<<(x)<<endl
#define dump(x)  cout << #x << " = " << (x) << endl;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
using M = map<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int, vector<int>, greater<int>>;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

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

  vector<int> sunuke(n, 0);
  int d;
  REP(i,k) {
    cin >> d;
    int a;
    REP(i,d) {
      cin >> a;
      a--;
      sunuke[a]++;
    }
  }

  int ans = 0;
  REP(i,n) if (sunuke[i] == 0) ans++;
  COUT(ans);

  return 0;
}


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

const int N = 100005;

int q, k;
int n;
vector <pair <int, int> > g[N];
long long dep[N];

void dfs(int u, int p) {
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i].first;
    int w = g[u][i].second;
    if (v == p) continue;
    dep[v] = dep[u] + w;
    dfs(v, u);
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    g[u].push_back(make_pair(v, w));
    g[v].push_back(make_pair(u, w));
  }
  scanf("%d %d", &q, &k);
  dfs(k, 0);
  while (q--) {
    int u, v; scanf("%d %d", &u, &v);
    printf("%lld\n", dep[u] + dep[v]);
  }
  return 0;
}

Measured memory_bytes: 14336
#include<bits/stdc++.h>
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define print(x) cout << (x) << endl;
#define printa(x, n) for(ll i = 0; i < n; i++) {cout << (x[i]) << " ";} cout << endl;
using namespace std;
using ll = long long;

int main(void) {
    int n;
    cin >> n;
    int a[n];
    rep (i, n) {
        cin >> a[i];
        if (a[i] % 2 == 1) {
            cout << "first" << endl;
            return 0;
        } 
    }
    
    cout << "second" << endl;
    return 0;
}

Measured memory_bytes: 640
#include <stdio.h>

int main(void)
{
  int i=0;
  int a,b,c,temp;
  scanf("%d%d%d",&a,&b,&c);
  if(a > b){
    temp = a; a = b; b = temp;
  }
  temp = a;
  while(temp != b+1){
    if(c%temp == 0)i++;
    temp++;
  }
  printf("%d\n",i);
  return 0;
}



Measured memory_bytes: 1812
n = int(input())
s = []
for i in range(n):
      s.append(tuple(map(int,input().split())))
dp = [s[0][0],s[0][0],s[0][1],s[0][1],s[0][2],s[0][2]]
sel = (0,0,1,1,2,2)
pre = ((2,3),(4,5),(0,1),(4,5),(0,1),(2,3))
p = list(dp)
for i in range(1,n):
      for j in range(6):
            dp[j] = max(p[pre[j][0]],p[pre[j][1]]) + s[i][sel[j]]
      p = list(dp)
print(max(dp))

Measured memory_bytes: 63320
#include <bits/stdc++.h>
#define rep(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define repr(i, n, m) for (int i = (int)(n) - 1; i >= (int)(m); i--)
using namespace std;
using ll = int64_t;
const int MOD = 1000000007; // 10^9+7
// https://atcoder.jp/contests/abc168/tasks/abc168_c
int main() {
    double a, b, h, m;
    cin >> a >> b >> h >> m;
    double theta = abs(11 * m - 60 * h) / 2;
    theta = min(theta, 360 - theta);
    double ans = a * a + b * b - 2 * a * b * cos(theta / 180 * M_PI);
    cout << fixed << setprecision(10) << sqrt(ans) << endl;
}


Measured memory_bytes: 4236
// finish date: 2018/10/08

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>>
        vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<double> vd;
typedef vector<vector<double>> vvd;
typedef vector<vector<vector<double>>>
        vvvd;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, pair<int, int>> plii;
const int bigmod = 1000000007;
const int INF = 1050000000;
const long long INFll = 100000000000000000;

//最大公約数
int gcd(int a, int b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    if (a < b) {
        swap(a, b);
    }
    int r = 1; //0以外であれば何でも
    while (r != 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    ll N, M;
    cin >> N >> M;
    string S, T;
    cin >> S >> T;
    ll L = N / gcd((int)N, (int)M) * M;
    map<ll, char> X;
    rep(i, N) {
        X[(ll)i * (L / N)] = S[i];
    }
    rep(i, M) {
        if (X[(ll)i * (L / M)] != T[i] && X[(ll)i * (L / M)]!=X[222222222222222222]) {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << L << endl;

    return 0;
}



Measured memory_bytes: 10880
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <iomanip>
using namespace std;
#define all(x) x.begin(), x.end()
typedef vector <int> vi;
typedef pair<int,int> ii;
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
const ll inf = 3e18 + 5;
int add(int a, int b) { return (a += b) < mod ? a : a - mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }
int sub(int a, int b) { return (a -= b) < 0 ? a + mod : a; }
int ctz(int x) { return __builtin_ctz(x); }
int clz(int x) { return __builtin_clz(x); }

const int maxn = 405;
int a[maxn], n;
ll dp[maxn][maxn];
int cnt = 0;

ll f(int l, int r){
  if(l == r) return 0;
  if(dp[l][r] != -1) return dp[l][r];
  ll ret = inf, s = 0;
  for(int i = l; i <= r; i++){
    s += a[i];
  }
  for(int i = l; i <= r - 1; i++){
    ret = min(ret, s + f(l, i) + f(i + 1, r));
  }
  return dp[l][r] = ret;
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  #ifdef LOCAL
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif

  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }
  memset(dp, -1, sizeof dp);
  cout << f(0, n - 1);
}

Measured memory_bytes: 1536
fun main(args: Array<String>){
        val line: String = readLine() as String
        val a =Array(5, {i -> line[i]-'0'})
        val b =Array(5, {i -> line[i+6]-'0'})
        var min=a[0]*100+a[1]*10+a[2]
        var max=b[0]*100+b[1]*10+b[2]

        if(b[1]>b[3]||(b[1]==b[3]&&b[0]>b[4])){//単に反転したやつがもとのを超える
            max-=1
        }
        if(a[1]<a[3]||(a[1]==a[3]&&a[0]<a[4])){//単に反転したやつがもとのより小さい
            min+=1
        }
        if(max>=min)print(max-min+1)
        else print(0)
}


Measured memory_bytes: 29832
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << '\n';
#define CFYN(n) cout << ( (n) ? "YES":"NO") << '\n';
#define OUT(n) cout << (n) << '\n';
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(void)
{
    IOS
    int n; cin >> n;

    int ans = 0;
    string ns = to_string(n);

    map<pair<char,char>,int> m;
    FOR(i,1,n+1) {
        string si = to_string(i);
        m[{si.front(),si.back()}]++;
    }

    REP(i,10) REP(j,10) {
        ans += m[{i+'0',j+'0'}] * m[{j+'0',i+'0'}];
    }

    cout << ans << '\n';

    return 0;
}

Measured memory_bytes: 256
import bisect,collections,copy,heapq,itertools,math,operator,string
def I(): return int(input())
def S(): return input()
def LI(): return list(map(int,input().split()))
def LS(): return list(input().split())
##################################################
N,M = LI()
A = LI()
for x in A:
    N -= x
print(N if N>=0 else -1)


Measured memory_bytes: 10776
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(int argc, char const *argv[]) {
    int n,k;
    cin >> n >> k;
    int num[n];
    for(int i=0;i<n;i++)cin>>num[i];
    int min = n+1;
    int min_index;
    for(int i=0;i<n;i++){
        if(min > num[i])min = num[i];
        min_index = i;
    }
    int cnt=0;
    if(min_index%(k-1)!=0)
        cnt += min_index/(k-1)+1;
    else
        cnt += min_index/(k-1);

    if((n-(min_index+1))%(k-1)!=0)
        cnt += (n-(min_index+1))/(k-1)+1;
    else
        cnt += (n-(min_index+1))/(k-1);

    cout << cnt << endl;



    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define inf INT_MAX
#define sc(a) scanf("%d",&a)
#define scc(a,b) scanf("%d %d",&a,&b)
#define sccc(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pff(a,b) printf("%d %d",a,b)
#define pfff(a,b,c) printf("%d %d %d",a,b,c)
#define pb(a) push_back(a)
#define em empty()
#define fr front()
#define cl clear()
#define sz size()
#define mp(a,b) make_pair(a,b)
#define fri(b) freopen(b,"r",stdin)
#define fro(b) freopen(b,"w",stdout)
/*
ID: uslusam1
TASK: test
LANG: C++
*/
using namespace std;

int n,k;

int dp[100013];
vector<int> vec;

bool solve(int st,int g){
	if(dp[st]!=-1){
		if(dp[st]==1){
			return g;
		}
		else{
			return !g;
		}
	}
	if(st<=0){
		return !g;
	}
	for(int i=vec.size()-1;i>=0;i--){
		if(vec[i]>st){
			continue;
		}
		int f=solve(st-vec[i],!g);
		if(f==g){
			dp[st]=1;
			return g;
		}
	}
	dp[st]=0;
	return !g;
}

int main(){
	//fri("gir.txt");
	//fro("cik.txt");
	scc(n,k);
	memset(dp,-1,sizeof dp);
	for(int i=1;i<=n;i++){
		int al;
		sc(al);
		vec.pb(al);
	}
	sort(vec.begin(),vec.end());
	int bas=solve(k,1);
	if(bas){
		cout<<"First";
		return 0;
	}
	cout<<"Second";

	
	return 0;
}




Measured memory_bytes: 5376
((N, X), A) = $stdin.read.lines.map(&:chomp).map{|l| l.split(" ").map(&:to_i)}

b = Array.new(N) {Array.new(N)}
class Array
  def sum
    self.inject(:+)
  end
end

N.times do |i|
  s = nil
  N.times do |k|
    s = A[i-k] if s.nil? || s > A[i-k]
    b[k][i] = s
  end
end

a = nil
N.times do |k|
  al = b[k].sum + k * X
  a = al if a.nil? or a > al
end
puts a


Measured memory_bytes: 33276
#include <algorithm>
#include <bitset>
#include <iomanip>
#include <ios>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

using namespace std;

int main()
{
    char a, b;
    cin >> a >> b;
    if (a == 'H') {
        cout << b << "\n";
    } else {
        cout << char(140 - int(b)) << "\n";
    }
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		int count = 0;
		for (int i = 0; i < n; i++) {
			long num = sc.nextLong();
			if(isPrime(num)) count++;
		}

		System.out.println(count);

	}

	private static boolean isPrime(long num) {

		if (num == 2) return true;
		if (num % 2 == 0) return false;

		for (int i = 2; i <= (int)Math.pow(num, 0.5); i++) {
			if(num % i == 0) return false;
		}
		return true;
	}
}

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

const int N = 100000 + 10;

int n, m;
vector<int> g[N];
vector<int> path[2];
bool vis[N];

void dfs( int u, vector<int> &path ) {
	path.push_back(u);
	for( int t = 0; t < (int)g[u].size(); t++ ) {
		int v = g[u][t];
		if( vis[v] ) continue;
		vis[v] = true;
		dfs( v, path );
		return;
	}
}
int main() {
	scanf( "%d%d", &n, &m );
	for( int i = 1; i <= m; i++ ) {
		int u, v;
		scanf( "%d%d", &u, &v );
		g[u].push_back(v);
		g[v].push_back(u);
	}
	vis[1] = true;
	dfs( 1, path[0] );
	dfs( 1, path[1] );
	reverse( path[1].begin(), path[1].end() );
	path[1].pop_back();
	printf( "%d\n", path[0].size() + path[1].size() );
	for( int c = 1; c >= 0; c-- ) {
		for( int t = 0; t < path[c].size(); t++ )
			printf( "%d%s", path[c][t], c == 0 && t + 1== path[c].size() ? "\n" : " " );
	}
}




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

namespace AtCoder_088_B
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int A = 0;
            int B = 0;
            // スペース区切りの整数の入力
            var input = Console.ReadLine().Split(' ');
            int[] cards = new int[N];
            for (int i = 0; i < N; i++)
            {
                cards[i] = int.Parse(input[i]);
            }
            Array.Sort(cards);
            Array.Reverse(cards);
            for (int i = 0; i < N; i++)
            {
                if (i % 2 == 0) A += cards[i];
                else B += cards[i];
            }
            Console.WriteLine(A - B);
        }
    }
}


Measured memory_bytes: 11604
import math
c, f = math.ceil, math.floor

def diff(arr):
    return max(arr) - min(arr)


def solve(h, w):
    if h%3 == 0 or w%3 == 0:
        return 0

    ps = [
        [h*c(w/3), c(h/2)*(w-c(w/3)), (h-c(h/2))*(w-c(w/3))],
        [h*c(w/3), f(h/2)*(w-c(w/3)), (h-f(h/2))*(w-c(w/3))],
        [h*f(w/3), c(h/2)*(w-f(w/3)), (h-c(h/2))*(w-f(w/3))],
        [h*f(w/3), f(h/2)*(w-f(w/3)), (h-f(h/2))*(w-f(w/3))],
        [w*c(h/3), c(w/2)*(h-c(h/3)), (w-c(w/2))*(h-c(h/3))],
        [w*c(h/3), f(w/2)*(h-c(h/3)), (w-f(w/2))*(h-c(h/3))],
        [w*f(h/3), c(w/2)*(h-f(h/3)), (w-c(w/2))*(h-f(h/3))],
        [w*f(h/3), f(w/2)*(h-f(h/3)), (w-f(w/2))*(h-f(h/3))],
        [h*c(w/3), h*c(w/3), h*(w-2*c(w/3))],
        [h*c(w/3), h*f(w/3), h*(w-c(w/3)-f(w/3))],
        [h*f(w/3), h*f(w/3), h*(w-2*f(w/3))],
        [w*c(h/3), w*c(h/3), w*(h-2*c(h/3))],
        [w*c(h/3), w*f(h/3), w*(h-c(h/3)-f(h/3))],
        [w*f(h/3), w*f(h/3), w*(h-2*f(h/3))],
    ]
    values = [diff(p) for p in ps]
    return min(values)

h, w = list(map(int, input().split()))
print(solve(h, w))

"""
"""


Measured memory_bytes: 3192
#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    int n;
    string a;
    cin >> n >> a;
    if (n % 2 == 1)
    {
        cout << "No";
        return 0;
    }
    for (int i = 0, j = n / 2; i < n / 2; ++i, ++j)
    {
        if (a[i] != a[j])
        {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
    return 0;
}


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

using namespace std;

const int md = 1000000007;


int main() {
	int n;
	scanf("%d", &n);
	int res = 1;
	int cont = 1;
	while (cont <= n) {
		res = (long long)(((long long)res % md) * ((long long)cont % md)) % md;
		cont++;
	}
	printf("%d\n", res);
	return 0;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {

    private static FastReader in = new FastReader(System.in);
    private static PrintWriter out = new PrintWriter(System.out);

    private static final long MOD = (long) 1e9 + 7;

    public static void main(String[] args) {
        solve();
        out.flush();
    }

    private static void solve() {
        int n = in.nextInt();
        int m = in.nextInt();
        int[] a = in.nextIntArray(n);
        PriorityQueue<Integer> c = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for (int i : a) {
            c.add(i);
        }

        for (int i=0; i < m; i++) {
            int temp = c.poll();
            temp /= 2;
            c.add(temp);
        }

        long ans = 0;
        for (int i : c)
            ans += i;
        out.println(ans);
    }

    // https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader(InputStream inputStream) {
            br = new BufferedReader(new
                    InputStreamReader(inputStream));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException  e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        // https://qiita.com/masakinpo/items/5f77f2a879578a85a0bb
        public int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }

}


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

using Graph = vector<vector<int> >;

class LCA {
public:
    vector<vector<int> > parent; // parent[d][v] := 2^d-th parent of v
    vector<int> depth;
    
    LCA() { }
    
    LCA(const Graph &G, int r = 0) { init(G, r); }
    
    void init(const Graph &G, int r = 0) {
        
        int V = (int)G.size();
        int h = 1;
        
        while ((1<<h) < V) ++h;
        
        parent.assign(h, vector<int>(V, -1));
        depth.assign(V, -1);
        
        dfs(G, r, -1, 0);
        
        for (int i = 0; i+1 < (int)parent.size(); ++i)
            for (int v = 0; v < V; ++v)
                if (parent[i][v] != -1)
                    parent[i+1][v] = parent[i][parent[i][v]];
    }
    
    
    void dfs(const Graph &G, int v, int p, int d) {
        
        parent[0][v] = p;
        depth[v] = d;
        for (auto e : G[v]) if (e != p) dfs(G, e, v, d+1);
    }
    
    
    int getLCA(int u, int v) {
        
        if (depth[u] > depth[v]) swap(u, v);
        for (int i = 0; i < (int)parent.size(); ++i)
            if ( (depth[v] - depth[u]) & (1<<i) )
                v = parent[i][v];
        if (u == v) return u;
        for (int i = (int)parent.size()-1; i >= 0; --i) {
            if (parent[i][u] != parent[i][v]) {
                u = parent[i][u];
                v = parent[i][v];
            }
        }
        return parent[0][u];
    }
};

int main() {
    int N; cin >> N;
    Graph G(N);
    
    for (int i = 0; i < N; ++i) {
        int num; cin >> num;
        
        for (int j = 0; j < num; ++j) {
            
            int c; cin >> c;
            G[i].push_back(c);
            G[c].push_back(i);
        }
    }
    
    LCA lca(G);
    
    int Q; cin >> Q;
    
    for (int q = 0; q < Q; ++q) {
        int u, v; cin >> u >> v;
        cout << lca.getLCA(u, v) << endl;
    }
}





Measured memory_bytes: 18180
#include <iostream>
#include <numeric>
#include <cmath>
#include <limits>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
ll Max(ll(a), ll(b), ll(c)) {
	return max(max(a, b), c);
}
ll Min(ll(a), ll(b), ll(c)) {
	return min(min(a, b), c);
}
vector<ll> D;
void pre() {
	queue<ll> q;
	q.push(0);
	
	while (q.front() < 3333333334) {
		ll s = q.front();
		D.push_back(s);
		q.pop();
		q.push(s * 10 + 3);
		q.push(s * 10 + 5);
		q.push(s * 10 + 7);
	}
	return;
}




int main() {
	pre();
	ll N;
cin >> N;
	ll i = 0,an=0;

	while (D.at(i) <= N) {
		ll k = D.at(i);
		bool ch[9];
		rep(i, 9) {
			ch[i] = false;
		}
		while (k > 0) {
			ch[k % 10] = true;
			k /= 10;
		}
		if (ch[3] && ch[5] && ch[7])an++;
		i++;
	}
	cout << an << endl;
	

}

Measured memory_bytes: 3876
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        while(true){
        
        int H=sc.nextInt();
        int W=sc.nextInt();
            
            if(W<=0 && H<=0){
            break;
       		 }
        
		for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                System.out.print("#");
            }
            System.out.println("");        
		}
            System.out.println("");
        }
	}
}


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

using namespace std;

int main()
{
    string s;
    cin >>s;
    int aa=0;
    int bb=0;
    if(s[0]=='0'&&s[1]!='0'){
        aa=1;
    }
   else if(s[0]=='0'&&s[1]=='0'){
        aa==0;
    }
   if(s[0]=='1'){
        if(s[1]=='0'||s[1]=='1'||s[1]=='2')
            aa=1;
    }
    if(s[2]=='0'&&s[3]!='0'){
        bb=1;
    }
    if(s[2]=='0'&&s[3]=='0'){
        bb==0;
    }
    if(s[2]=='1'){
        if(s[3]=='0'||s[3]=='1'||s[3]=='2')
            bb=1;
    }
    if(aa==1&&bb==1){
        cout << "AMBIGUOUS"<<endl;
    }
    if(aa==1&&bb==0){
        cout << "MMYY"<<endl;
    }
    if(bb==1&&aa==0){
        cout << "YYMM"<<endl;
    }
    if(aa==0&&bb==0) cout<< "NA"<< endl;
    return 0;
}


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

typedef long long ll;
using namespace std;
static const int MAX = 100001;

int main() {
    ll N, A[MAX], B[MAX];
    cin >> N;
    for (int i = 0; i < N + 1; ++i) cin >> A[i];
    for (int i = 0; i < N; ++i) cin >> B[i];

    ll monster = 0;
    for (int i = 0; i < N; ++i) {
        ll now = min(A[i], B[i]);
        monster += now;
        B[i] -= now;

        ll next = min(A[i + 1], B[i]);
        monster += next;
        A[i + 1] -= next;
    }

    cout << monster;

    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <cstdlib>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <math.h>
#include <random>
#include <time.h>
#include <cassert>
using namespace std;
#define LL long long
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483648
#define INT_MAX 2147483647
#define LL_MIN -9223372036854775808
#define LL_MAX 9223372036854775807

int main(){
    iostream::sync_with_stdio(false);
    
    int N;
    cin >> N;
    int a[100];
    double sum = 0;
    for(int i=0; i<N; i++){
        cin >> a[i];
        sum += a[i];
    }
    sum /= N;
    int ans;
    double now = 99999;
    for(int i=0; i<N; i++){
        if(abs(sum - a[i]) < now){
            now = abs(sum - a[i]);
            ans = i;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
#define REP(i, n) for (Int i = 0, max_i = (n); i < max_i; i++)
#define REPI(i, a, b) for (Int i = (a), max_i = (b); i < max_i; i++)
#define ALL(obj) begin(obj), end(obj)
#define RALL(obj) rbegin(obj), rend(obj)
#define fi first
#define se second
using ii = pair<Int, Int>;
template <class T> inline bool chmax(T& a, const T& b) {
    if (a >= b) return false;
    a = b;
    return true;
}
template <class T> inline bool chmin(T& a, const T& b) {
    if (a <= b) return false;
    a = b;
    return true;
}
struct SetupIO {
    SetupIO() { cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }
} setup_io;

template <class T> std::ostream& print(std::ostream& out, T const& val) { return (out << val << " "); }
template <class T1, class T2> std::ostream& print(std::ostream& out, std::pair<T1, T2> const& val) {
    return (out << "{" << val.first << " " << val.second << "} ");
}
template <template <class, class...> class TT, class... Args>
std::ostream& operator<<(std::ostream& out, TT<Args...> const& cont) {
    for (auto&& elem : cont) print(out, elem);
    return out;
}

void dump_func() { cerr << endl; }
template <class Head, class... Tail> void dump_func(Head&& h, Tail&&... t) {
    cerr << h << (sizeof...(Tail) == 0 ? "" : ", "), dump_func(forward<Tail>(t)...);
}
#ifdef _MY_DEBUG
#define dump(...)                                                                                                    \
    cerr << "/* " << #__VA_ARGS__ << " [" << __LINE__ << ":" << __FUNCTION__ << "]" << endl, dump_func(__VA_ARGS__), \
        cerr << "*/\n\n";
#else
#define dump(...)
#endif

/**
 *    author:  knshnb
 *    created: CREATED_TIMESTAMP
 **/

Int get_sum(Int x) {
    Int ret = 0;
    while (x) {
        ret += x % 10;
        x /= 10;
    }
    return ret;
}
signed main() {
    Int n;
    cin >> n;
    Int ans = -1;
    Int sum = 0;
    REP(i, n) {
        Int d, c;
        cin >> d >> c;
        sum += d * c;
        ans += c;
    }
    ans += (sum - 1) / 9;
    cout << ans << endl;
}


Measured memory_bytes: 256