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

using ll=long long;
const int SIZE=62;
const ll MOD=1e9+7;
int main(){
    ll n; cin>>n;
    n++;
    vector<vector<ll>> dpl(SIZE,vector<ll>(2,0));
    vector<vector<ll>> dpg(SIZE,vector<ll>(2,0));
    dpg[0][0]=1;
    for(int i=0;i+1<SIZE;i++){
        int x=(n>>i)&1;
        if(x==1){
            dpl[i+1][0]+=dpl[i][0]*2+dpl[i][1]+dpg[i][0];
            dpl[i+1][1]+=dpl[i][0]+dpl[i][1]*2+dpg[i][0]+dpg[i][1];
            dpg[i+1][0]+=dpg[i][0]+dpg[i][1];
            dpg[i+1][1]+=dpg[i][1];
        }
        else{
            dpl[i+1][0]+=dpl[i][0];
            dpl[i+1][1]+=dpl[i][0]+dpl[i][1];
            dpg[i+1][0]+=dpl[i][0]+dpl[i][1]+dpg[i][0]*2+dpg[i][1];
            dpg[i+1][1]+=dpl[i][1]+dpg[i][0]+dpg[i][1]*2;
        }
        dpl[i+1][0]%=MOD;
        dpl[i+1][1]%=MOD;
        dpg[i+1][0]%=MOD;
        dpg[i+1][1]%=MOD;
    }
    cout<<dpl[SIZE-1][0]<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define test int t; cin>>t; while(t--)
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef long long ll;
using namespace std;
int main()
{
   int a,b,c,cnt=0;
   cin>>a>>b>>c;
   for(int i=a;i<=b;i++)
   {
       if(i%c==0)
        cnt++;
   }
   cout<<cnt<<endl;
   
    return 0;
}


Measured memory_bytes: 3620
import java.util.*;
import java.io.*;
public class Main {
    static int[][] A;
    public static void main(String[] args) throws Exception {
        InputStreamReader r = new InputStreamReader(System.in);
        int N = nextInt(r);
        A = new int[N][N];
        for (int i = 0; i < N; i++) {
            int Ai = nextInt(r);
            for (int j = 0; j < Ai; j++) {
                int x = nextInt(r);
                int y = nextInt(r);
                A[i][x-1] = y == 1 ? 1 : -1;
            }
        }

        int ans = 0;
        int pow = pow(N);
        for (int i = 0; i < pow; i++) {
            int[] d = set(N, i);
            boolean ok = true;
            ok = check(N, d);
            ok = check(N, d);
            ok = check(N, d);
            if (ok) {
                int c = 0;
                for (int j = 0; j < N; j++) {
                    if (d[j] == 1) {
                        c++;
                    }
                }
                ans = Math.max(ans, c);
            }
        }
        System.out.println(ans);
    }

    public static int nextInt(InputStreamReader r) throws Exception {
        String str = "";
        while (true) {
            int c = r.read();
            if (c == 32 || c == 10 || c == -1) {
                break;
            }
            str += (char)c;
        }
        return Integer.parseInt(str);
    }

    public static int pow(int N) {
        return N == 0 ? 1 : 2 * pow(N-1);
    }

    public static int[] set(int N, int i) {
        int[] res = new int[N];
        for (int j = 0; j < N; j++) {
            res[j] = i % 2 == 1 ? 1 : 0;
            i = i / 2;
        }
        return res;
    }

    public static boolean check(int N, int[] d) {
        for (int j = 0; j < N; j++) {
            if (d[j] == 1) {
                for (int k = 0; k < N; k++) {
                    if (A[j][k] == 1) {
                        if (d[k] == -1) {
                            return false;
                        } else {
                            d[k] = A[j][k];
                        }
                    }
                    if (A[j][k] == -1) {
                        if (d[k] == 1) {
                            return false;
                        } else {
                            d[k] = A[j][k];
                        }
                    }
                }
            }
        }
        return true;
    }
}


Measured memory_bytes: 25812
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define ALL(n) begin(n),end(n)
#define VMAX 50
#define EMAX 500
#define DMAX 20
#define TRUE 1
#define FALSE 0
#define NOTUSED 0
#define END -1
#define ROOT -1
using Graph = vector<vector<int>>;

int main(){
    // 隣接頂点リストの受け取り
    int n;
    cin>>n;

    Graph G(n+1);
    G[0]={NOTUSED};
    REP(i,n){
        int u,k;
        cin>>u>>k;
        G[u].resize(k);
        REP(j,k){
            cin>>G[u][j];
        }
    }

    // BFS のためのデータ構造
    vector<int> d(n+1,-1);
    d[0]=NOTUSED;
    queue<int> que;

    // 初期条件(頂点 1 を初期ノードとする)
    d[1]=0;
    que.push(1);

    // BFS 開始(キューが空になるまで探索を行う)
    while(!que.empty()){
        int v=que.front();
        que.pop();

        // v から辿れる頂点をすべて調べる
        for(int adj_v:G[v]){
            // すでに発見済みの頂点は探索しない
            if(d[adj_v]!=-1) continue;

            // 新たな白色頂点 nv について距離情報を更新してキューに追加する
            d[adj_v]=d[v]+1;
            que.push(adj_v);
        }
    }

    for(int i=1; i<=n; i++){
        cout<<i<<" "<<d[i]<<endl;
    }
}


Measured memory_bytes: 3112
import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())))
mod = 10**9+7

ans = 0
max_digit = 0
for i in range(n):
    max_digit = max(max_digit, len(bin(a[i])))
for i in range(max_digit):
    num1 = np.count_nonzero((a >> i) & 1)  # 1の数
    num2 = n - num1  # 0の数
    ans += pow(2, i, mod) * (num1 * num2) % mod
print(ans % mod)

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

int main(){
	string A, B, S;
	int nA, nB, cnt=0;
	cin >> A >> B;

	nA = stoi(A);
	nB = stoi(B);

	for(int i=nA; i<nB+1; i++){
		S = to_string(i);
		int k = 0;
		for (int j=0; j<S.length()/2;j++){
			if ( S[j]==S[S.length()-1-j] ) {
				k++;
			}
			else{
				break;
			}
		}
		if ( k==S.length()/2 ) cnt++;
	}
	cout << cnt << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define f first
#define s second

typedef pair<int, int> P;
typedef pair<P, string> P2;

int main(){
  int n, m;
  
  while(cin >> n >> m){
    if(n == 0 && m == 0) break;
    P2 era[1010];
    int tmp;
    for(int i = 0 ; i < n ; i++){
      cin >> era[i].s >> tmp >> era[i].f.s;
      era[i].f.f = era[i].f.s - tmp;
    }
    
    sort(era, era+n);
     
    while(m--){
      bool flag = false;
      cin >> tmp;
      for(int i = 0 ; i < n ; i++){
	if(era[i].f.f < tmp && tmp <= era[i].f.s){
	  cout << era[i].s << ' ' << tmp-era[i].f.f << endl;
	  flag = true;
	  break;
	}
      }
      if(!flag) cout << "Unknown" << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1288
#![allow(unused_imports)]
#![allow(unused_variables)]
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(deprecated)]

use std::cell::{Cell, Ref, RefCell, RefMut};
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;
use std::usize;

const MOD_10_9_7: u64 = 1_000_000_007;
const INF: i64 = 1_000_000_000_000;
const MIN_INF: i64 = -1_000_000_000_000;

/// FYI: https://github.com/vain0x/scan-bench
#[allow(unused_macros)]
macro_rules! read {
    ([$t:ty] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ($($t:ty),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ([$t:ty]) =>
        (rl().split_whitespace().map(|w| w.parse().unwrap()).collect::<Vec<$t>>());
    ($t:ty) =>
        (rl().parse::<$t>().unwrap());
    ($($t:ty),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(w.next().unwrap().parse::<$t>().unwrap()),*)
    }};
}

fn rl() -> String {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    buf.trim_right().to_owned()
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn main() {
    let (n, x): (usize, usize) = read!(usize, usize);

    let mut l = Vec::with_capacity(n + 1); // レベルiバーガーの層の数
    let mut p = Vec::with_capacity(n + 1); // レベルiバーガーのパティの数
    l.push(1usize);
    p.push(1usize);
    for i in 1..(n + 1) {
        let l_prev = l[i - 1];
        let p_prev = p[i - 1];
        l.push(l_prev * 2 + 3);
        p.push(p_prev * 2 + 1);
    }

    let mut ans = 0usize;
    let mut i = 0usize;
    let mut i_in_d = 0usize;
    let mut cur_level = n;
    while i < x {
        if i_in_d == 0 {
            // レベルcur_levelバーガーの一番下を見ているとき
            if cur_level == 0 {
                i_in_d = 0;
                i += 1;
                ans += 1;
                continue;
            } else {
                i_in_d += 1;
                i += 1;
                continue;
            }
        }
        if i_in_d == l[cur_level - 1] + 1 {
            // レベルcur_levelバーガーの中央にあるパティを見ているとき
            i_in_d += 1;
            i += 1;
            ans += 1;
            continue;
        }
        if i_in_d == l[cur_level - 1] * 2 + 2 {
            // レベルcur_levelバーガーの一番上を見ているとき
            i_in_d += 1;
            i += 1;
            continue;
        }
        if i + l[cur_level - 1] < x {
            // レベルcur_level - 1バーガーを全部食べても大丈夫なとき
            i_in_d += l[cur_level - 1];
            i += l[cur_level - 1];
            ans += p[cur_level - 1];
            continue;
        }

        // レベルcur_level - 1バーガーを全部食べることができない場合
        i_in_d = 0;
        cur_level -= 1;
    }
    println!("{}", ans);
}


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

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
#define ordered_set tree<long long int, null_type,less<long long int>, rb_tree_tag,tree_order_statistics_node_update> 

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    long long int a[n];
    long long int temp=0;
    for (int i=0;i<n;i++){
        cin>>a[i];
        temp^=a[i];
    }    
    for (int i=0;i<n;i++)
        cout<<(a[i]^temp)<<" ";
        cout<<"\n";
}

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

using namespace std;
int main(){
    int A=0,B=0;
    std::vector<int> result(3);
    cin >> A >> B;

    result[1] = A*B;
    result[0] = A+B;
    result[2] = A-B;



    cout << *std::max_element(result.begin(), result.end());;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() 
{
    int a, b; cin >> a >> b;
    if (a == b) cout << "Draw" << endl;
    else if (a == 1)      cout << "Alice" << endl;
    else if (b == 1)      cout << "Bob" << endl;
    else                  cout << (a > b ? "Alice" : "Bob") << endl;
    return 0;
}

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

int gcd(int a, int b) {
    if (!b) return a;
    return gcd(b, a % b);
}

int l[100001], r[100001], a[100001];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    FOR(i, 1, n + 1) cin >> a[i];
    FOR(i, 1, n + 1) l[i] = gcd(l[i - 1], a[i]), r[n - i] = gcd(r[n - i + 1], a[n - i + 1]);
    int ans = 0;
    FOR(i, 0, n + 1) ans = max(ans, gcd(l[i], r[i + 1]));
    cout << ans;
    return 0;
}

Measured memory_bytes: 1536
#include "bits/stdc++.h"
using namespace std;typedef long long lint;typedef vector<lint> liv;
//#define rep(i,n) for(int i=0;i<n;++i)
#define all(v) v.begin(),v.end()
#define linf 1152921504606846976
#define MAXN 100010
#define md 1000000007//998244353

#define pb push_back
#define _vcppunko4(tuple) _getname4 tuple
#define _getname4(_1,_2,_3,_4,name,...) name
#define _getname3(_1,_2,_3,name,...) name
#define _trep2(tuple) _rep2 tuple
#define _trep3(tuple) _rep3 tuple
#define _trep4(tuple) _rep4 tuple
#define _rep1(n) for(lint i=0;i<n;++i)
#define _rep2(i,n) for(lint i=0;i<n;++i)
#define _rep3(i,a,b) for(lint i=a;i<b;++i)
#define _rep4(i,a,b,c) for(lint i=a;i<b;i+=c)
#define _trrep2(tuple) _rrep2 tuple
#define _trrep3(tuple) _rrep3 tuple
#define _trrep4(tuple) _rrep4 tuple
#define _rrep1(n) for(lint i=n-1;i>=0;--i)
#define _rrep2(i,n) for(lint i=n-1;i>=0;--i)
#define _rrep3(i,a,b) for(lint i=b-1;i>=a;--i)
#define _rrep4(i,a,b,c) for(lint i=a+(b-a-1)/c*c;i>=a;i-=c)
template<class T>
istream& operator>>(istream& is,vector<T>& vec);
template<class T,size_t size>
istream& operator>>(istream& is,array<T,size>& vec);
template<class T,class L>
istream& operator>>(istream& is,pair<T,L>& p);
template<class T>
ostream& operator<<(ostream& os,vector<T>& vec);
template<class T,class L>
ostream& operator<<(ostream& os,pair<T,L>& p);
template<class T>
istream& operator>>(istream& is,vector<T>& vec){ for(T& x: vec) is>>x;return is; }
template<class T,class L>
istream& operator>>(istream& is,pair<T,L>& p){ is>>p.first;is>>p.second;return is; }
//template<class T>
//ostream& operator<<(ostream& os,vector<T>& vec){ os<<vec[0];rep(i,1,vec.size())os<<' '<<vec[i];return os; }
//template<class T>
//ostream& operator<<(ostream& os,deque<T>& deq){ os<<deq[0];rep(i,1,deq.size())os<<' '<<deq[i];return os; }
template<class T,class L>
ostream& operator<<(ostream& os,pair<T,L>& p){ os<<p.first<<" "<<p.second;return os; }

inline void in(){}
template <class Head,class... Tail>
inline void in(Head&& head,Tail&&... tail){ cin>>head;in(move(tail)...); }
template <class T>
inline bool out(T t){ cout<<t<<'\n';return 0; }
inline bool out(){ cout<<'\n';return 0; }
template <class Head,class... Tail>
inline bool out(Head head,Tail... tail){ cout<<head<<' ';out(move(tail)...);return 0; }

#define rep(...) _vcppunko4((__VA_ARGS__,_trep4,_trep3,_trep2,_rep1))((__VA_ARGS__))
#define rrep(...) _vcppunko4((__VA_ARGS__,_trrep4,_trrep3,_trrep2,_trrep1))((__VA_ARGS__))
#define lin(...) lint __VA_ARGS__;in(__VA_ARGS__)
#define stin(...) string __VA_ARGS__;in(__VA_ARGS__)
#define vin(type,name,size) vector<type> name(size);in(name)
#define fi i.first
#define se i.second
#define YES(c) cout<<((c)?"YES\n":"NO\n")
#define Yes(c) cout<<((c)?"Yes\n":"No\n")

int main(){
	stin(s);lint n=s.size();
	lin(k);
	vector<string> kouho;
	char least='z';
	rep(n-5)least=min(least,s[i]);
	rep(n-5)if(s[i]==least){
		rep(j,5)kouho.pb(s.substr(i,j+1));
	}
	rep(i,max(0ll,n-5),n){
		rep(j,0,n-i){
			kouho.pb(s.substr(i,j+1));
		}
	}
	sort(all(kouho));
	kouho.erase(unique(all(kouho)),kouho.end());
	cout<<kouho[--k]<<endl;
}

Measured memory_bytes: 1660
#include <bits/stdc++.h>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const long double PI  = acos(-1.0L);
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
#define chmax(a,b) a = (((a)<(b))?(b):(a))
#define chmin(a,b) a = (((a)>(b))?(b):(a))

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

signed main(){
	int n; cin>>n;
	ll idx[n];
	for(ll i=1;i<=n;i++){
		ll a; cin>>a; a--; idx[a]=i;
	}
	set<ll> s{0LL,n+1};
	ll ans=0LL;
	for(ll i=0;i<n;i++){
		ll next=idx[i];
		s.insert(next);
		auto itr_next=s.lower_bound(next);
		// int idx_next=distance(s.begin(),itr_next);
		itr_next--;
		ll a=*itr_next; itr_next++;
		ll b=*itr_next; itr_next++;
		ll c=*itr_next;
		// cerr<<a SP b SP c<<endl;
		ans+=(i+1)*(c-b)*(b-a);
		// cerr<<i SP ans<<endl;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 11264
/*
  AOJ 1072
  Title:
  @kankichi573
*/
#include <stdio.h>
int r,c;
main()
{
  while(scanf("%d %d",&r,&c) && (r||c))
    {
      if((r & 1) && (c & 1))
	printf("no\n");
      else
	printf("yes\n");
    }
  return(0);
}

Measured memory_bytes: 584
#include <iostream>
#include <cmath>

// math.h をインクルードする！
using namespace std;
typedef long long ll;


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

    //cout << "直角を挟む２辺の長さを入力して下さい > ";
    cin >> a >> b>>c;
  
  long double eps = 1.0E-14;

    
    //cout << "斜辺の長さは "
      //   << sqrt(a * a + b * b) << " です。" << endl;
  if(sqrt(a)+sqrt(b)+eps<sqrt(c)){cout << "Yes" << endl;}else{cout << "No" << endl;}

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
int isPrime(int);
int main(){
  int n,i,j,count=0;

  scanf("%d",&n);
  int A[n];
  for(i=0;i<n;++i){
    scanf("%d",&A[i]);
    count += isPrime(A[i]);
  }
  printf("%d\n",count);
  return 0;
}

int isPrime(int a){
  int i;
  if(a==2) return 1;
  
  if(a<2 || a%2==0) return 0;
  
  i=3;
  while(i<=sqrt(a)){
    if(a%i==0)return 0;
    i+=2;
  }
  return 1;
}



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

#define ull unsigned long long
#define ll long long

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

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

    int m1 = n/2-1;
    int m2 = n/2;

    cout << a[m2]-a[m1];
    return 0;
}

Measured memory_bytes: 3728
#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits>
#include <numeric>
#include <string>
#include <vector>

using namespace std;
int main() {
    string s;
    int a, b, c;
    cin >> a >> b >> c;
    cout << c << " " << a << " " << b << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String s = sc.next();
		String t = sc.next();
		sc.close();

		for (int i = 0; i < n; i++) {
			System.out.print(s.charAt(i));
			System.out.print(t.charAt(i));
		}
		System.out.println();
	}
}


Measured memory_bytes: 21844
// ABC148D2.cpp
//#include "pch.h"
#include <iostream>
#include<vector>
using namespace std;
int main()
{
	bool one = false;
	int N;
	cin >> N;
	vector<long long>a(N + 1);
	for (int i = 1; i <= N; i++)
	{
		cin >> a.at(i);
		if (a.at(i)==1)
		{
			one = true;
		}
	}
	if (one==false)	// 1が含まれないなら、不可能。
	{
		cout << "-1" << endl;
		return 0;
	}
	int size = a.size();
	int j = 1;
	int ai = 1;
	int count = 0;
	while (j<size)
	{
		if (a.at(j)!=ai)	// a.at(j)とaiが異なるなら、砕く
		{
			j++;
			count++;		// 砕くレンガの個数
		}else{				// a.at(j)とaiが同じなら、次をチェック
			j++;
			ai++;
		}
	}
	cout << count << endl;
}


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

int main(){
  int N;
  cin >> N;
  vector<int> s(N);
  for(int i=0; i<N; i++) cin >> s.at(i);
  sort(s.begin(),s.end());
  int ans=0;
  for(int i=0; i<N; i++) ans+=s.at(i);
  if(ans%10==0){
    for(int i=0; i<N; i++){
      if(s.at(i)%10!=0){
        ans-=s.at(i);
        break;
      }
    }
  }
  if(ans%10==0) ans=0;
  cout << ans << endl;
  
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main
{
  static class FastScanner
  {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer("");
    
    String next() {
      while(!st.hasMoreTokens()) {
        try {
          st = new StringTokenizer(br.readLine());
        } catch (IOException e) {}
      }
      return st.nextToken();
    }
    
    int nextInt() {
      return Integer.parseInt(next());
    }
    
    long nextLong() {
      return Long.parseLong(next());
    }
    
  }
  
  public static void main(String[] args) {
    FastScanner fs = new FastScanner();
    int n = fs.nextInt();
    int[] arr = new int[n];
    for(int i = 0; i < n; ++i) {
      arr[i] = fs.nextInt();
    }
    int[] dp = new int[n];
    dp[1] = (int)Math.abs(arr[1]-arr[0]);
    for(int i = 2; i < n; ++i) {
      dp[i] = Math.min(dp[i-1] + (int)Math.abs(arr[i-1]-arr[i]), 
          dp[i-2] + (int)Math.abs(arr[i-2]-arr[i]));
    }
    PrintWriter out = new PrintWriter(System.out);
    out.println(dp[n-1]);
    out.close();
  }

}


Measured memory_bytes: 43244
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <cmath>
#include <map>
#include <limits.h>
#include <map>

using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int> da(n);
  for(int i=0;i<n;i++){
    cin >> da[i];
  }
  int ma=0;
  for(int i=0;i<n;i++){
    ma=max(ma,da[i]);
  }
  int gg=ma/2+ma%2;
  int ab=ma,mi=0;
  for(int i=0;i<n;i++){
    if((abs(da[i]-gg)<ab)&da[i]!=ma){
        ab=abs(da[i]-gg);
        mi=da[i];
    }
  }
  cout << ma << ' ' << mi << endl;
}

Measured memory_bytes: 640
# ALDS1_8_A: Binary Search Tree 1: Insert

class BinaryTree
  class Node
    attr_reader :key
    attr_accessor :left, :right

    def initialize(key)
      @key = key
      @left = @right = NIL
    end
  end

  NIL = Node.new(-1)

  def initialize
    @root = NIL
  end

  def insert(key)
    parent = NIL
    node   = @root
    while node != NIL
      parent = node 
      if key < node.key
        node = node.left
      else
        node = node.right
      end
    end

    new_node = Node.new key
    if parent == NIL
      @root = new_node
    elsif key < parent.key
      parent.left = new_node
    else
      parent.right = new_node
    end
  end

  def keys_by_preorder(node = @root)
    return [] if node == NIL
    left_keys  = keys_by_preorder(node.left)
    right_keys = keys_by_preorder(node.right)
    [node.key] + left_keys + right_keys
  end

  def keys_by_inorder(node = @root)
    return [] if node == NIL
    left_keys  = keys_by_inorder(node.left)
    right_keys = keys_by_inorder(node.right)
    left_keys + [node.key] + right_keys
  end
end

tree = BinaryTree.new

n_commands = gets.to_i
n_commands.times do
  command = gets.chomp
  case command
  when /insert (-?\d+)/
    key = $1.to_i
    tree.insert key
  when /print/
    puts ' ' << tree.keys_by_inorder.join(' ')
    puts ' ' << tree.keys_by_preorder.join(' ')
  end
end

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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define pb push_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j
#define lbidx(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
#define ubidx(x, y) upper_bound(x.begin(), x.end(), y) - x.begin()
#define BiSearchRangeNum(x, y, z) lower_bound(x.begin(), x.end(), z) - lower_bound(x.begin(), x.end(), y)turn idx;
#define deg_to_rad(deg) ((((double)deg)/((double)360)*2*M_PI))
#define rad_to_deg(rad) ((((double)rad)/(double)2/M_PI)*(double)360)

template<class T>
inline bool chmax(T &a, T b) {
  if(a < b) {
    a = b;
    return true;
  }
  return false;
};

template<class T>
inline bool chmin(T &a, T b) {
  if(a > b) {
    a = b;
    return true;
  }
  return false;
};

int main() {
  char c;
  cin >> c;
  cout << (char) (c + 1) << endl;
};


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








bool test=0;
void solve()
{
 
    int n,m;
    cin>>n>>m;
    cout<<n*(n-1)/2+m*(m-1)/2;
    
}



















int main() {
    int t=1;
	if(test)
	cin>>t;
	while(t--)
	{
	    solve();
	}
	return 0;
}

Measured memory_bytes: 256
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

x = ni()
if x in [3,5,7]:
    print('YES')
else:
    print('NO')

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {


	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
	    int[] input = new int [5];
	    for(int i = 0; i < input.length; i++) {
	    	input[i] = sc.nextInt();
	    }
	    
	    int lastOrderIndex = input.length-1;
	    int min1digit = Integer.MAX_VALUE;
	    for( int i = 0; i < input.length; i++) {
	    	if( input[i]%10 == 0 ) {
	    		continue;
	    	}
	    	
	    	if( input[i]%10 < min1digit ) {
	    		min1digit = input[i]%10;
	    		lastOrderIndex = i;
	    	}
	    }
	    
	    int sum = 0;
	    for( int i = 0; i < input.length; i++) {
	    	if( i == lastOrderIndex ) {
	    		sum += input[i];
	    	} else if( input[i]%10 == 0 ) {
	    		sum += input[i];
	    	} else {
	    		sum += input[i] + (10 - input[i]%10);
	    	}
	    }
    	System.out.println(sum);

		sc.close();
	}
}

Measured memory_bytes: 22612
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep0(a,b) for(int a=0;a<b;a++)
#define rep1(a,b) for(int a=1;a<=b;a++)
#define repp(a,b,c) for(int a=b;a<c;a++)
#define rev(a,b,c) for(int a=b;a>=c;a--)
#define in insert
#define len length()
#define si size()
#define lb lower_bound
#define ub upper_bound
#define beg begin()
#define end end()
#define vec vector<ll>
#define se set<ll>
#define mults multiset<ll>
#define F first
#define S second
#define pr(a) cout<<a
#define pr2(a,b) cout<<a<<" "<<b
#define get(a) cin>>a
#define nextl cout<<endl
const ll mod = 1000000007;
const ll maxn = 500005;
const ll mm = 1e+18;
ll power(ll x, ll y)
{
    ll res = 1;
    x = x % mod;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % mod;
        y = y>>1;
        x = (x*x) % mod;
    }
    return res;
}
ll ncr(ll n, ll k)
{
    ll C[k+1];
    memset(C, 0, sizeof(C));

    C[0] = 1;

    for (ll i = 1; i <= n; i++)
    {
        for (ll j = min(i, k); j > 0; j--)
            C[j] = (C[j] + C[j-1])%mod;
    }
    return C[k];
}
void solve()
{
     set<int>s;
     rep1(i,9)rep1(j,9) s.in(i*j);
     int n;
     cin>>n;
     auto it=s.find(n);
     if(it==s.end) cout<<"No";
     else cout<<"Yes";
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
   // cin>>t;
    while(t--){
        solve();
      //  nextl;
    }
    return 0;
}


Measured memory_bytes: 256
def main():
    s = input()
    s_list = list(s)
    t = input()
    for i in range(len(s) - len(t), -1, -1):
        sub_str = s[i:i+len(t)]
        for j in range(len(t) + 1):
            if j == len(t):
                print((s[:i] + t + s[i+len(t):]).replace("?", "a"))
                exit()
            if sub_str[j] == "?":
                continue
            elif sub_str[j] != t[j]:
                break
    print("UNRESTORABLE")


if __name__ == '__main__':
    main()


Measured memory_bytes: 38256
import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
		int a=scan.nextInt();
		int b=scan.nextInt();
		if((a+b)%2==1) {
			System.out.println((a+b)/2+1);
		}
		else {
		System.out.println((a+b)/2);
	}
		}
}

Measured memory_bytes: 21844
#include <assert.h>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using ll = long long;
using P = std::pair<ll, ll>;

template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << "[" << pa.first << ", " << pa.second << "]";
}

template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  os << "{";
  for (int i = 0; i < vec.size(); i++)
    os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
  os << "}";
  return os;
}

#define rep(i, a, b) for (ll(i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cerr << "debug " << i << std::endl

// const ll MOD = 998244353;
const ll MOD = 1e9 + 7;

//非再帰累乗(mod付き)
ll pow_mod(ll a, ll b, ll mod=-1) {
  if ((a == 0)||(mod!=-1&&a%mod==0)) {
    return 0;
  }

  ll x = 1;

  while (b > 0) {
    if (b & 1) {
      x = (mod!=-1)?(x * a) % mod:x*a;
    }
    a = (mod!=-1)?(a * a) % mod:a*a;
    b >>= 1;
  }
  return x;
}

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

  ll n;
  std::string s;
  std::cin>>n>>s;
  ll m=s.size();

  std::vector<std::vector<ll>> dp(n+1,std::vector<ll>(n+1,0));

  dp[0][0]=1;

  rep(i,1,n+1){
    dp[i][0]=(dp[i-1][1]+dp[i-1][0])%MOD;
    dp[i][n]=(2*dp[i-1][n-1])%MOD;
    rep(j,1,n){
      dp[i][j]=(dp[i-1][j-1]*2+dp[i-1][j+1])%MOD;
    }
  }

  std::cout<<(dp[n][m]*pow_mod(5*1e8+4,m,MOD))%MOD;

  return 0;
}

Measured memory_bytes: 195840
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

std::string solve(const std::string& s)
{
  long sum = 0;
  for (auto c : s) {
    sum += c - '0';
  }
  return sum % 9 ? "No" : "Yes";
}

int main()
{
  std::string s;
  std::cin >> s;

  std::cout << std::setprecision(20);
  std::cout << solve(s) << std::endl;
}


Measured memory_bytes: 3752
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,K;
  cin>>N>>K;
  int d=0;
  int A[N]={0};
  int B,answer;
  answer=0;
  B=0;
  for(int i=0;i<K;i++){
    cin>>d;
    for(int j=0;j<d;j++){
    cin>>B;
      A[B-1]=1;
    }
  }
  for(int i=0;i<N;i++){
      answer+=A[i];
  }
  cout<<N-answer<<endl;
 return 0; 
}

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

/*
int main(void)
{
  int n,s,com,i,j,sum;
  while(scanf("%d %d",&n,&s)!=EOF){  
    if(n==0&&s==0)
      break;
    com=0;
    

    printf("%d\n",com);
  }
  return 0;
}
*/

int main(void)
{
  int w,s,i,j,a[10],b[10],queue;
  s=1;
  for(i=0;i<10;i++){
    a[i]=s;
    s*=2;
  }
  
  while(scanf("%d",&w)!=EOF){
    i=9;
    queue=0;
    while(1){
      while(a[i]>w){
	i--;
      }
      w-=a[i];
      b[queue++]=a[i];
      if(w==0)break;
    }
    for(j=queue-1;j>=0;j--){
      printf("%d",b[j]);
      if(j!=0) printf(" ");
    }
    printf("\n"); 
  }
  
  return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <algorithm>
#include <fstream>
#include <utility>
#include <iomanip>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define IO ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
typedef long long ll;
typedef long double ld;

using namespace std;
const ll INF = 1e18;
const int mod = 1e4, N = 1e5 + 5, inf = 1e9;

int main()
{
    IO
    int n, arr[N], brr[N];
    ll ans = 0;
    cin >> n;
    for(int i = 0; i <= n; i++)
        cin >> arr[i];
    for(int i = 0; i < n; i++)
        cin >> brr[i];
    for(int i = 0; i < n; i++)
    {
        int tmp = 0;
        tmp = min(brr[i], arr[i]);
        brr[i] -= tmp;
        arr[i] -= tmp;
        ans += tmp;
        tmp = min(brr[i], arr[i + 1]);
        brr[i] -= tmp;
        arr[i + 1] -= tmp;
        ans += tmp;
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 4332
#include <bits/stdc++.h>
#define dum(x) cout<<#x<<'='<<x<<endl
#define ll long long
using namespace std;

int main() {
  string s;
  ll k;
  cin >> s >> k;

  for (int i = 0; i < k; ++i) {
    if (s.at(i) != '1') {
      cout << s.at(i) << endl;
      return 0;
    }
  }

  cout << 1 << endl;
  return 0;
}


Measured memory_bytes: 256
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	public static void main(String[]args) {
		try(Scanner scan = new Scanner(System.in)){
			
			
			int N = scan.nextInt();
			int[]x  = new int[N];
			int[]y  = new int[N];
			
			for(int i = 0;i<N;i++) {
				x[i] = scan.nextInt();
				y[i] = scan.nextInt();
			}
			
			StringBuffer A = new StringBuffer();
			for(int i = 1;i<=N;i++) {
				A.append(i);
			}
			
			String s = A.toString();
		double goukei = 0;
			BigDecimal big = new BigDecimal(0.0);
			
			  while (true) {
			  //System.out.println(s);
				double kyori = 0;  
				for(int i = 0;i<s.length()-1;i++) {  
					int a = Integer.valueOf(s.substring(i, i+1));//現在地
					int b = Integer.valueOf(s.substring(i+1, i+2));//行先
					
					kyori+=Math.sqrt(Math.pow(x[a-1]-x[b-1], 2)+Math.pow(y[a-1]-y[b-1], 2));
					
					
				}
				
				//System.out.println(kyori);
				goukei+=kyori;
				  
				  
				  
			  s = nextPermutation(s);
			  if (s.equals("Final")) break;
			  }
			  
			  BigDecimal kai = BigDecimal.valueOf(kaijyou(N));
			big.divide(kai,7,RoundingMode.HALF_UP);
			String str = big.toPlainString();
			
			System.out.println(goukei/(double)kaijyou(N));
			
			
			
			
			
			
		}
	}
		
		
		
		
		private static int kaijyou(int n) {
			if(n==1)return 1;
			else return n*kaijyou(n-1);
		}
		
		
		
		private static String nextPermutation (String s) {
		/*入力した文字列(数列、英語小文字、英語大文字)の次の順番を返すメソッド
		 * String s = "ABC";
		 * while (true) {
		 * System.out.println(s);
		 * s = nextPermutation(s);
		 * if (s.equals("Final")) break;
		 * }
		 * とmainメソッド に書けばN文字の文字列をN!文小さい物から順に列挙することができる*/

		ArrayList<Character> list = new ArrayList<>();
		for (int i=0; i<s.length(); i++) list.add(s.charAt(i));

		int pivotPos = -1;
		char pivot = 0;
		for (int i=list.size()-2; i>=0; i--) {
			if (list.get(i) < list.get(i+1)) {
				pivotPos = i;
				pivot = list.get(i);
				break;
			}
		}

		if (pivotPos==-1 && pivot==0) return "Final";

		int L = pivotPos+1, R = list.size()-1;
		int minPos = -1;
		char min = Character.MAX_VALUE;
		for (int i=R; i>=L; i--) {
			if (pivot < list.get(i)) {
				if (list.get(i) < min) {
					min = list.get(i);
					minPos = i;
				}
			}
		}

		Collections.swap(list, pivotPos, minPos);
		Collections.sort(list.subList(L, R+1));

		StringBuilder sb = new StringBuilder();
		for (int i=0; i<list.size(); i++) sb.append(list.get(i));

		return sb.toString();

	
		
		
	}
		

}


Measured memory_bytes: 61316
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define INF INT_MAX;
typedef long long ll;
using namespace std;

int main(){
  int money;
  cin >> money;
  int ans=0;
  ans+=money/500*1000;
  money = money%500;
  ans+=money/5*5;
  cout << ans ;
}


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

using namespace std;

int main() {
	size_t n;
	int *ptr, *a, i;
	cin >> n;
	ptr = (int *)calloc(n, sizeof(int));
	if (ptr == NULL)
		exit(EXIT_FAILURE);
	a = ptr;
	for (i = 0; i < (int)n; i++) {
		cin >> *(a + i);
	}
	for (i = (int)n - 1; i >= 0; i--) {
		cout << *(a + i);
		if (i > 0)
			cout << " ";
	}
	cout << endl;
}

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


int main(){
  int n,i;
  cin >> n;
  vector<pair<int,int>> a(n);
  for(i=0;i<n;++i){
    int x;
    cin >> x;
    a[i]=make_pair(x,i+1);
  }
  sort(a.begin(),a.end());
  for(i=0;i<n;++i){
    cout << a[i].second << " " ;
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 1536
X, Y, A, B, C = map(int, input().split())
p = sorted(list(map(int, input().split())))
q = sorted(list(map(int, input().split())))
r = sorted(list(map(int, input().split())))[::-1]

ans = sorted(p[A-X:] + q[B-Y:])
ans_sum = [ans[0]]
for i in range(1, X+Y):
    ans_sum.append(ans_sum[i-1] + ans[i])

r_sum = [r[0]]
for i in range(1, C):
    r_sum.append(r_sum[i-1] + r[i])

index, temp = -1, ans_sum[-1]
for i in range(min(C, X+Y)):
    if temp < ans_sum[-1] + r_sum[i] - ans_sum[i]:
        temp = ans_sum[-1] + r_sum[i] - ans_sum[i]
print(temp)

Measured memory_bytes: 29908
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
using Edge = pair<int, ll>;
using Graph = vector<vector<int>>;
using WeightedGraph = vector<vector<Edge>>;
const ll INF64 = 1LL << 60;
const int INF32 = 1 << 29;
const ll MOD = 1000000007;

const int CASES = 3;

void solve() {
    ll n, k, s; cin >> n >> k >> s;
    vector<ll> a(n);
    ll M = pow(10, 9);
    for (int i = 0; i < k; ++i) {
        a[i] = s;
    }
    for (int i = k; i < n; ++i) {
        if(s != M) a[i] = s+1;
        else a[i] = 1;
    }
    for (int i = 0; i < n; ++i) {
        cout << a[i];
        if(i == n-1) cout << endl;
        else cout << ' ';
    }
}

int main() {
#ifdef MYLOCAL
    vector<string> filenames {"input1.txt", "input2.txt", "input3.txt", "input4.txt"};
    cout << "------------\n";
    for(int i = 0; i < CASES; ++i){
        ifstream in(filenames[i]);
        cin.rdbuf(in.rdbuf());
        solve();
        cout << "------------\n";
    }
#else

    solve();

#endif
    return 0;
}


Measured memory_bytes: 2048
import itertools
N,M,X = map(int,input().split())
A = [list(map(int,input().split())) for i in range(N)]

z = [i for i in range(1, N+1)]
m = [1000000000000000000]

for i in range(N):
    x = list(itertools.combinations(z,i+1))

    for s in x:

        for k in range(1,M+1):
            C = sum(A[j-1][k] for j in s)
            if C < X:
                break
        else:
            m.append(sum(A[o-1][0] for o in s))

print(min(m) if min(m)!=1000000000000000000 else -1)


Measured memory_bytes: 9500
import math
a, b, h, m = map(int, input().split())

big = max(30*h + (m*0.5), 6*m)
small = min(30*h + (m*0.5), 6*m)
gap = min(big - small, 360 - (big - small))

print(format(math.sqrt(a**2 + b**2 - 2*a*b*math.cos(math.radians(gap))), ".20f"))

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

int main() {
    string S;
    cin >> S;
    int ans = 0;
    for (int i = 0; i < S.size() - 1; i++) {
        if (S[i] != S[i + 1])
            ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 512
#include<stdio.h>

int main(){
  int r;
  scanf("%d", &r);

  if(r<1200){
    printf("ABC\n");
  }
  else if(r<2800){
    printf("ARC\n");
  }
  else{
    printf("AGC\n");
  }

  return 0;
} 


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
#define ll long long
#define rep(i,n) for (ll i = 0; i < (n); i++)
const ll mod=1e9+7;

/*ll powmod(ll x,ll y){     //指数乗の計算　MODありver
  ll ans=1;
  rep(i,y){
    ans=ans*x%mod;
  }
  return ans;
}*/

int main()
{
  string s;
  cin>>s;
  if(s[s.size()-1]!='s') cout <<s+"s" <<endl;
  else cout <<s+"es" <<endl;
}


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

int main(){

    double n; cin >> n;
    vector<double> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    double sum = 0.0;
    for(int i = 0; i < n; i++) sum += a[i];
    double av = sum / n;
    int id = 0;
    double ans = 100100100.0;
    for(int i = 0; i < n; i++){
        if(ans > abs(av - a[i])){
            ans = abs(av - a[i]);
            id = i;
        }
    }

    cout << id << endl;
    return 0;
}

Measured memory_bytes: 764
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <cstring>
#include <cmath>
using namespace std;
#define MAXH 1000000001
#define MAXW 1000000007
#define INF 1000000007
#define MAXN 200001
#define MOD 1000000007
typedef long long ll;
typedef pair<int, int> P;

static ll ran1[MAXN], ran2[MAXN];
static ll parent1[MAXN], parent2[MAXN];

void init_union_find(ll n, ll ran[], ll parent[]){
    for(ll i = 0;i < n;i++){
        ran[i] = 0;
        parent[i] = i;
    }
    return;
}

int find(ll c, ll parent[]){
    if(parent[c] == c) return c;
    return parent[c] = find(parent[c], parent);
}

bool same(ll l, ll r, ll parent[]){
    return find(l, parent) == find(r, parent);
}

void link(ll l, ll r, ll ran[], ll parent[]){
    l = find(l, parent);
    r = find(r, parent);
    if(l == r) return;

    if(ran[l] < ran[r]){
        parent[l] = r; 
    }else {
        parent[r] = l;
        if(ran[l] == ran[r]){
            ran[l]++;
        }
    }

    return;
}

ll N, K, L;
ll p[MAXN], q[MAXN], r[MAXN], s[MAXN];

int main(){
    cin >> N >> K >> L;
    for(int i = 0;i < K;i++){
        cin >> p[i] >> q[i];
        p[i]--;q[i]--;
    }
    for(int i = 0;i < L;i++){
        cin >> r[i] >> s[i];
        r[i]--;s[i]--;
    }
    init_union_find(N, ran1, parent1);
    init_union_find(N, ran2, parent2);

    for(int i = 0;i < K;i++){
        link(p[i], q[i], ran1, parent1);
    }
    for(int i = 0;i < L;i++){
        link(r[i], s[i], ran2, parent2);
    }

    vector<P> vec;
    for(int i = 0;i < N;i++){
        vec.push_back({find(i, parent1), find(i, parent2)});
    }

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

    for(int i = 0;i < N;i++){
        printf("%d\n", (int)(upper_bound(vec.begin(), vec.end(), make_pair(find(i, parent1), find(i, parent2)) ) - lower_bound(vec.begin(), vec.end(), make_pair(find(i, parent1), find(i, parent2)) ) ) );
    }

    return 0;
}

Measured memory_bytes: 14196
def gcd3(x,y):
    if x>=y:
        if x%y==0:
            return y
        else:
            return gcd3(y,x%y)
    else:
        if y%x==0:
            return x
        else:
            return gcd3(x,y%x)
def gcd2(x4):
    if len(x4)>2:
        return gcd3(gcd2(x4[:len(x4)//2]),gcd2(x4[len(x4)//2:]))
    elif len(x4) ==2:
        return gcd3(x4[0],x4[1])
    else:
        return x4[0]
N, X = map(int,input().split())
x=[int(i) for i in input().split()]
x.append(X)
x3=[]
for i in range(len(x)-1):
    x3.append(abs(x[i+1]-x[i]))
print(gcd2(x3))


Measured memory_bytes: 14480
H, W = gets.split.map(&:to_i)
MAP = Array.new(H) do
  gets.split.map(&:to_i)
end

H.times do |i|
  gets.split.map(&:to_i).each_with_index do |b, j|
    MAP[i][j] = (MAP[i][j] - b).abs
  end
end

DP = Array.new(H) do
  Array.new(W) do
    0
  end
end

BASE = 1300

diff = MAP[0][0]
DP[0][0] |= 1 << (BASE + diff)
DP[0][0] |= 1 << (BASE - diff)
# DP
H.times do |i|
  W.times do |j|
    diff = MAP[i][j]
    if (i > 0)
      tmp = DP[i-1][j]
      DP[i][j] |= tmp << diff
      DP[i][j] |= tmp >> diff
    end
    if (j > 0)
      tmp = DP[i][j-1]
      DP[i][j] |= tmp << diff
      DP[i][j] |= tmp >> diff
    end
  end
end

BASE.times do |i|
  if DP[H-1][W-1][BASE + i] == 1 || DP[H-1][W-1][BASE - i] == 1
    puts i.abs
    break
  end
end


Measured memory_bytes: 20732
n = input()
op_cnt = len(n) - 1  # すき間の個数
for i in range(2**op_cnt):
  op = ['-'] * op_cnt
  for j in range(op_cnt):
    if (i >> j) & 1:
      op[op_cnt-1-j] = '+'
  formula = ''
  for p_n, p_o in zip(n, op + ['']):
    formula += (p_n + p_o)
  if eval(formula) == 7:
    print(formula + '=7')
    break

Measured memory_bytes: 9084
package main
 
import (
    "fmt"
)
 
type dice struct {
    t, s, e, w, n, b int
}
 
func main() {
    var t, s, e, w, n, b int
    fmt.Scan(&t, &s, &e, &w, &n, &b)
    d := dice{t: t, s: s, e: e, w: w, n: n, b: b}
 
    var cmds string
    fmt.Scan(&cmds)
    for _, v := range cmds {
        switch v {
        case 'E':
            d.t, d.e, d.w, d.b = d.w, d.t, d.b, d.e
        case 'W':
            d.t, d.e, d.w, d.b = d.e, d.b, d.t, d.w
        case 'S':
            d.t, d.s, d.b, d.n = d.n, d.t, d.s, d.b
        case 'N':
            d.t, d.s, d.b, d.n = d.s, d.b, d.n, d.t
        }
    }
    fmt.Println(d.t)
}


Measured memory_bytes: 1128
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <limits>
#include <cassert>
#include <random>
#include <stack>
#include <ctime>
#define REP(i,n) for(long (i)=0;(i)<(n);(i)++)
#define REPI(i,a,b) for(long (i)=(a);(i)<(b);(i)++)
#define INF numeric_limits<double>::infinity()
constexpr long MOD = 1e9 + 7;
using namespace std;
using P = pair<long, long>;
using VI = vector<long>;

int d[1000][1000];
int b[500][500];

using VP = vector<P>;
int main() {
    long n, c;
    cin >> n >> c;
    REP(i,c) {
        REP(j,c) {
            cin >> d[i][j];
        }
    }
    REP(i,500) {
        REP(j,500) {
            b[i][j] = -1;
        }
    }
    REP(i,n) {
        REP(j,n) {
            cin >> b[i][j];
            b[i][j]--;
        }
    }
    
    VI mod3[3];
    REP(i,3) {
        REP(j,n) {
            REP(k,n) {
                if ((j + k) % 3 == i) {
                    mod3[i].push_back(b[j][k]);
                }
            }
        }
    }
    VP mod3cost[3];
    // mod3cost[i][j]: the sum of cost when the color becomes j
    REP(i,3) {
        REP(j,c) {
            long cost = 0;
            for (auto k: mod3[i]) {
                cost += d[k][j];
            }
            mod3cost[i].push_back(P(cost,j));
        }
        sort(mod3cost[i].begin(), mod3cost[i].end());
    }
    
    long ans = 1e18;
    
    REP(i,3) {
        REP(j,3) {
            REP(k,3) {
                if (mod3cost[0][i].second
                    != mod3cost[1][j].second && mod3cost[1][j].second != mod3cost[2][k].second && mod3cost[0][i].second != mod3cost[2][k].second) {
                    ans = min(ans, mod3cost[0][i].first + mod3cost[1][j].first + mod3cost[2][k].first);
                }
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 4212
#define  _CRT_SECURE_NO_WARNINGS
#pragma comment (linker, "/STACK:526000000")

#include "bits/stdc++.h"

using namespace std;
typedef string::const_iterator State;
#define eps 1e-11L
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL

#define MOD 998244353LL
#define seg_size 262144*2LL
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))
#define ALL(x) (x).begin(),(x).end()

unsigned long xor128() {
	static unsigned long x = 123456789, y = 362436069, z = 521288629, w = time(NULL);
	unsigned long t = (x ^ (x << 11));
	x = y; y = z; z = w;
	return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

void init() {
	iostream::sync_with_stdio(false);
	cout << fixed << setprecision(20);
}

#define int ll

void solve(){
	while (true) {
		int n;
		cin >> n;
		if (n == 0) return;
		int dp[(1 << 18)] = {};
		REP(i, n) {
			int m, l;
			cin >> m >> l;
			int neko = 0;
			REP(i, m) {
				int a, b;
				cin >> a >> b;
				a -= 6;
				b -= 6;
				for (int i = a; i < b; ++i) {
					neko += (1 << i);
				}
			}
			REP(q, (1 << 18)) {
				if (q & neko) continue;
				dp[q + neko] = max(dp[q + neko], dp[q] + l);
			}
		}
		int ans = 0;
		REP(i, (1 << 18)) {
			ans = max(ans, dp[i]);
		}
		cout << ans << endl;
	}
}

#undef int
int main() {
	init();
	solve();
}


Measured memory_bytes: 5268
#include <iostream>
#include <vector>
#include <algorithm>

int main(void)
{
    std::string in, out;
    std::vector<std::string> ilog(50);
    const char tail = 'a';

    in = "aaaa";

    while(std::find( ilog.begin(), ilog.end(), in) == ilog.end() && in[0]==tail) {
        ilog.push_back(in);
        std::cout << "?" << in[in.size()-1] << in << tail << std::endl;
        std::cin >> in;
    }

    std::cout << "!OUT" << std::endl;

    return 0;
}

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

static const int INF=1e9;
static const int MOD=1000000007;
typedef long long ll;
typedef pair<int,int> P;

int main(){
    int N; cin >> N;
    int a[N];
    for(int i=0;i<N;i++) cin >> a[i];
    int tmp=1;
    int ans=0;
    for(int i=0;i<N;i++){
        if(a[i]==tmp){
            tmp++;
        }else{
            ans++;
        }
    }
    if(ans>N-1){
        cout << -1 << endl;
    }else{
        cout << ans << endl;
    }
    
}


Measured memory_bytes: 1024
n,k = map(int,input().split())
p = list(map(int,input().split()))
l = [0]

for i in range(1,1001):
    t = 0
    for j in range(i+1):
        t+=j
    l.append(t/i)

ans = 0

for e,i in enumerate(p):
    p[e] = l[i]
P = [0]*(n+1)
P[0] = 0
for e,i in enumerate(p):
    P[e+1] +=P[e]+i
M = 0  
for i , j in zip(P,P[k:]):
    M = max(M,j-i)
print(M)

Measured memory_bytes: 24804