akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int read()
{
    char s;
    int k=0,base=1;
    while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
    if(s==EOF)exit(0);
    if(s=='-')base=-1,s=getchar();
    while(s>='0'&&s<='9')
    {
        k=k*10+(s-'0');
        s=getchar();
    }
    return k*base;
}
void write(int x)
{
    if(x<0)
    {
        putchar('-');
        write(-x);
    }
    else
    {
        if(x/10)write(x/10);
        putchar(x%10+'0');
    }
}
char ch[100];
char c[5]={'K','I','H','B','R'};
int n,p,s;
int main()
{
	scanf("%s",ch+1);
	n=strlen(ch+1);
	if (n>9)
	{
		printf("NO");
		return 0;
	}
	p=0;
	for (int i=1;i<=n;i++)
	{
		if (ch[i]=='A') {s++;continue;}
		if (ch[i]!=c[p])
		{
			printf("NO");
			return 0;
		}
		if ((p==1||p==2)&&s!=0)
		{
			printf("NO");
			return 0;
		}
		if (s>1)
		{
			printf("NO");
			return 0;
		}
		s=0;p++;
	}
	if (p==5) printf("YES"); else printf("NO"); 
	return 0;
}

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

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

using namespace std;

const int vy[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int vx[] = {-1, 0, 1, 1, 1, 0, -1, -1};

string S[19];
int sx, sy;

bool isgoal(int y, int x)
{
  return ((y == 18 && 0 <= x && x <= 14) || y == 19);
}

int bfs()
{
  unordered_map< int, int > v[19][15];
  queue< tuple< int, int, int > > que;
  que.emplace(0, sy, sx);
  v[sy][sx][0] = 0;
  while(!que.empty()) {
    int bit, y, x;
    tie(bit, y, x) = que.front();
    que.pop();
    for(int i = 0; i < 8; i++) {
      int ny = vy[i] + y, nx = vx[i] + x, bb = bit;
      while(nx >= 0 && nx < 15 && ny >= 0 && ny < 19 && S[ny][nx] < 20) {
        if((bit >> S[ny][nx]) & 1) break;
        bb |= 1 << S[ny][nx];
        ny += vy[i], nx += vx[i];
      }
      if(ny == vy[i] + y && nx == vx[i] + x) continue;
      if(isgoal(ny, nx)) return (v[y][x][bit] + 1);
      if(ny >= 0 && nx < 15 && ny >= 0 && ny < 19) {
        auto nxt = make_tuple(bb, ny, nx);
        if(v[ny][nx].count(bb) && v[ny][nx][bb] <= v[y][x][bit] + 1)continue;
        v[ny][nx][bb] = v[y][x][bit] + 1;
        que.emplace(nxt);
      }
    }
  }
  return (-1);
}

int main()
{
  int pad = 0;
  for(int i = 0; i < 19; i++) {
    cin >> S[i];
    for(int j = 0; j < 15; j++) {
      if(S[i][j] == 'X') S[i][j] = pad++;
      else if(S[i][j] == 'O') sy = i, sx = j;
    }
  }
  cout << bfs() << endl;
}

Measured memory_bytes: 5988
# abc168 C
a, b, h, m = gets.split.map(&:to_i)
h = h + (m / 60.0)

ac = h * (Math::PI / 6)
ax = a * Math.sin(ac)
ay = a * Math.cos(ac)

bc = m * 6  * (Math::PI / 180)
bx = b * Math.sin(bc)
by = b * Math.cos(bc)

p ( (ax - bx) ** 2 + (ay - by) ** 2 ) ** (1.0/2)


Measured memory_bytes: 14844
N = int(input())
gA, sA, bA = map(int, input().split())
gB, sB, bB = map(int, input().split())

#[重さ,価値]を要素とする配列
lstAB_2 = [[gA, gB-gA], [sA, sB-sA], [bA, bB-bA]]
lstBA_2 = [[gB, gA-gB], [sB, sA-sB], [bB, bA-bB]]
lstAB = []
for i in range(3):
    if lstAB_2[i][1] > 0:
        lstAB += [lstAB_2[i]]  

lstBA = []
for i in range(3):
    if lstBA_2[i][1] > 0:
        lstBA += [lstBA_2[i]]

dp = [[0] * (N+1) for _ in range(len(lstAB)+1)]
for i in range(len(lstAB)):
    for j in range(N+1):
        if j < lstAB[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j-lstAB[i][0]]+lstAB[i][1])

N += dp[len(lstAB)][N]
# print (N)

dp2 = [[0] * (N+1) for _ in range(len(lstBA)+1)]
for i in range(len(lstBA)):
    for j in range(N+1):
        if j < lstBA[i][0]:
            dp2[i+1][j] = dp2[i][j]
        else:
            dp2[i+1][j] = max(dp2[i][j], dp2[i+1][j-lstBA[i][0]]+lstBA[i][1])
print (N + dp2[len(lstBA)][N])

Measured memory_bytes: 614936
#include<stdio.h>

int main()
{
    int a1,a2,a3,sum;

    scanf("%d%d%d",&a1,&a2,&a3);

    sum=a1+a2+a3;

    if(sum>=22)

    printf("bust\n");
    else
        printf("win\n");

    return 0;

}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int freq[10];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	string s;
	
	while (t--) {
		cin >> s;
		if (s == "AC") freq[0]++;
		else if (s == "WA") freq[1]++;
		else if (s == "TLE") freq[2]++;
		else freq[3]++;
	}
	cout << "AC x " << freq[0] << '\n';
	cout << "WA x " << freq[1] << '\n';
	cout << "TLE x " << freq[2] << '\n';
	cout << "RE x " << freq[3];
	return 0;
}

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

const long long inf = 1e18;

struct edge {
	int from, to;
	long long cost;
};

int main() {
	long long N, M, P; cin >> N >> M >> P;
	vector<edge> edges(M);
    for (int i = 0; i < M; i++) {
        long long A, B, C; cin >> A >> B >> C;
        edges[i].from = A - 1;
        edges[i].to = B - 1;
        edges[i].cost = - C + P;
    }

    vector<long long> d(N, inf);
    d[0] = 0;
    for (int i = 0; i < 2 * N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (d[edges[j].from] < inf) {
                if (d[edges[j].to] > d[edges[j].from] + edges[j].cost) {
                    if (i < N)
                        d[edges[j].to] = max(-inf, min(inf, d[edges[j].from] + edges[j].cost));
                    else
                        d[edges[j].to] = -inf;
                }
            }
        }
    }
    if (d[N - 1] == -inf) {
        cout << -1 << endl;
    } else {
        cout << max(0LL, -d[N - 1]);
    }

    return 0;
}


Measured memory_bytes: 512
n = int(input())
m = 0
a = 0
r = 0
c = 0
h = 0
cnt = 0
for i in range(n):
  p = input()
  if p[0] == "M":
    m += 1
  if p[0] == "A":
    a += 1
  if p[0] == "R":
    r += 1
  if p[0] == "C":
    c += 1
  if p[0] == "H":
    h += 1
if m > 0:
  cnt += 1
if a > 0:
  cnt += 1
if r > 0:
  cnt += 1
if c > 0:
  cnt += 1
if h > 0:
  cnt += 1
  
if cnt < 3:
  print(0)
else:
  print(m*a*r + m*a*c + m*a*h + m*r*c + m*r*h + m*c*h + a*r*c + a*r*h + a*c*h + r*c*h)


Measured memory_bytes: 49768
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using ii=pair<ll,ll>;
using vi=vector<ll>;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (ll)1e18
#define all(x) (x).begin(),(x).end()
#define print(a); for(auto x:a)cout<<x<<" "; cout<<"\n";
#define mset(a); memset(a,0,sizeof(a));

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
    ll n;cin>>n;
    ll sum=0;
    for(int i=1;i<=n;i++){
        sum+=i*(n/i)*(n/i+1)/2;
    }
    cout<<sum<<"\n";
}


Measured memory_bytes: 3604
import java.io.IOException;
import java.math.BigDecimal;
import java.util.Scanner;

/**
 * メインクラス
 *
 */
public class Main {

	/**
	 * メインメソッド
	 * @param args
	 * @throws IOException
	 */
	public static void main(String[] args) throws IOException {

		// 標準入力を取得
		Scanner sc = new Scanner(System.in);
		BigDecimal T = new BigDecimal(sc.next());
		BigDecimal X = new BigDecimal(sc.next());

		System.out.println(T.divide(X, 10, BigDecimal.ROUND_HALF_UP).toPlainString());
	}
}

Measured memory_bytes: 23764
#include <sstream>
#include <fstream>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <map>
#include <unordered_map>
#include <functional>
#include <utility>
#include <bitset>
#include <cstdlib>
#include <ctime>
#include <cstdio>


#include <stdlib.h>
#include <iostream>
#include <chrono> //clock
#include <vector>
#include <string>
#include <iomanip>  //setprecision function
#include <cmath>	//math
#include <cstdio>
#include <vector>	//vector array
#include <algorithm>	//STL algorithm
#include <set> //STL library set
#include <sstream> // for stringstream


using namespace std;
using namespace std::chrono; 


int main() {
	stringstream ss;
	//ss<<"akhil";
	//cout<<ss.str()<<endl;
	cout<<setprecision(16);
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	
	 // TESTCASE KO DEKH KA BHAUT SARA CONDITION GENERATE MAT KRO 
	 // PAPER PD CONFIRM HO JAO THORA JADA TIME HI KYU NA LGA

	int N;
	cin>>N;
	vector<int> vec;
	for(int i=0;i<=N;i++){
		int a;cin>>a;
		vec.push_back(a);
	}
	
	vector<int> dp(N+1,1e9+5);
	dp[0]=0;
	dp[1]=0;
	for(int i=2;i<=N;i++){
		for(int j : {i-1,i-2}){
			if(i-1>=0 and j-1>=0)
			dp[i]=min(dp[i],dp[j]+abs(vec[i-1]-vec[j-1]));
		}
	}

	
	cout<<dp[N]<<endl;
	
	return 0;
}





























Measured memory_bytes: 1144
def main():
    s = input()
    diff1 = 0
    diff2 = 0
    for i, c in enumerate(s):
        if i % 2 == 0:
            if c == "0":
                diff1 += 1
            else:
                diff2 += 1
        else:
            if c == "1":
                diff1 += 1
            else:
                diff2 += 1
    print(min(diff1, diff2))


if __name__ == "__main__":
    main()


Measured memory_bytes: 3188
def f2(k):
    r = k % 4
    if r == 0:
        return k
    elif r == 1:
        return 1
    elif r == 2:
        return k ^ 1
    else:
        # r == 3
        return 0


def f(m, n):
    return f2(m - 1) ^ f2(n)


a, b = map(int, input().split())
print(f(a, b))

"""
f(a,b) = f(0,a-1) ^ f(0,b)
重なった範囲がキャンセルされるため
"""


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

using namespace std;

#define ll long long
#define uint unsigned int

ll num[100];

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

    num[0] = 2;
    num[1] = 1;
    for (int i = 2; i <= n; ++i) {
        num[i] = num[i - 1] + num[i - 2];
    }

    cout << num[n] << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <math.h>
#include <utility>
#include <set>
#include <map>
#define INF 1000000000
#define rep(i,n) for(int i =0;i<n;i++)
using namespace std;
typedef long long int ll;

int main(){
    for(;;){
        int n,p;
        cin >> n >> p;
        if(n==0) break;
        int ch = 0;
        int i = p,j=0;
        vector<int> g(n,0);
        int ans;
        while (true) {
            if(i>0){
                i--;
                if(g[j]==0)ch++;
                g[j]++;
            }else{
                i+=g[j];
                if(g[j]!=0)ch--;
                g[j]=0;
            }
            if(ch == 1 and i == 0){
                ans = j;
                break;
            }
            j++;
            if(j>=n) j-=n;
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 1196
/**
*    created: 12.05.2020 09:07:32
**/

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
const int inf =1000000000;

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    //aの中に奇数の要素が奇数個あるとダメ
    //偶数個あればよい
    int k = 0;
    rep(i,n){
        if(a[i]%2)
            k++;
    }
    if(k%2) cout << "NO" << endl;
    else cout << "YES" << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define REP(i,n) for(int i=0;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<29
#define LINF LLONG_MAX/3
#define DINF DBL_MAX/3
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(v) (v).begin(),(v).end()
#define all(v) ALL(v)
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
#define CININIT cin.tie(0),ios::sync_with_stdio(false)
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }

constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

void solve(int n,int m,int p,int a,int b){
    vi t(n);
    rep(i,n) cin>>t[i];
    vector<vector<int>> g(m,vi(m,INF));
    rep(i,p){
        int x,y,z;cin>>x>>y>>z;
        x--;
        y--;
        g[x][y]=z;
        g[y][x]=z;
    }
    sort(all(t));
    vector<vector<double>> d(m,vector<double>(1<<n,DINF));
    using P = pair<double,pair<int,int>>;                    // <distance , <node,used>>
    priority_queue<P,vector<P>,greater<P>> que;
    que.push(P(0,pii(a,0)));
    d[a][0] = 0;
    while(!que.empty()){
        auto p = que.top();que.pop();
        double dist = p.first;
        int v=p.second.first;
        int kip=p.second.second;

        //cerr << "POP : " << v << " " << static_cast<bitset<9>>(kip) << " " << dist << endl;
        if(dist>d[v][kip]) continue;

        for(int i=0;i<n;i++){       //i?????????????¬?????????¨
            if((kip>>i)&1) continue;
            int nkip = (kip | (1<<i));
            for(int j=0;j<m;j++){
                if(g[v][j]==INF) continue;
                double cost=dist+(g[v][j]/(double)t[i]);
                if(cost<d[j][nkip]){
                    //cerr << "\tPUSH: (" << j << "," << static_cast<bitset<9>>(nkip) << "," << cost << ")" << endl;
                    d[j][nkip] = cost;
                    que.push(P(cost,pii(j,nkip)));
                }
            }
        }
    }

    double ans = DINF;
//    for(int i=0;i<m;i++){
//        cout << d[i] << endl;
//    }
    rep(i,(1<<n)){
        ans = min(ans,d[b][i]);
    }
    if(abs(DINF-ans)<0.00001) cout << "Impossible" << endl;
    else printf("%.20lf\n",ans);
}

int main(){/*{{{*/
    int n,m,p,a,b;
    while(cin>>n>>m>>p>>a>>b){
        if(n==0 and m==0 and p==0 and a==0 and b==0) break;
        a--;
        b--;
        solve(n,m,p,a,b);
    }
}/*}}}*/

Measured memory_bytes: 4528
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<(int)(n);i++)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

int main(){
    ll n,m;
    cin >> n >> m;
    vi a(n);
    rep(i,n) cin >> a[i];

    int lcm = n * m / gcd(n,m);

    vector<int> b(lcm);
    for(int i=0;i<lcm;i++) b[i] = a[i%n];

    int index = 0;
    ll ans = 0;
    while(index < lcm){
        ll max = numeric_limits<ll>::min();
        ll min = numeric_limits<ll>::max();
        for(int i=0;i<m;i++){
            chmax(max,b[index + i]);
            chmin(min,b[index + i]);
        }
        ans += max - min;
        index += m;
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 6520
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan0
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/














int K, X;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> K >> X;
	if (X <= K * 500) cout << "Yes" << endl;
	else cout << "No" << endl;
}







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

int main() {
  string S;
  long long sum = 0;
  long long res = 0;

  cin >> S;
  
  rep(tmp,1 << S.size()-1){
    bitset<N> index(tmp);

    long long sum = 0;
    rep(i,S.size()){
      sum = 10*sum + (S.at(i)-'0');

      if(S.size()-2-i >= 0){
        if(index.test(i)){
          res += sum;
          sum = 0;
        }
      }
    }
    res += sum;
  }

  cout << res << endl;
  
  return 0;
}

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

using namespace std;
using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll A, B, C, K;
  cin >> A >> B >> C >> K;
  if (K % 2 == 0)
    cout << A - B << '\n';
  else
    cout << B - A << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int p = 0, q[2000000];

int max_num(int x, int y){
    if(q[x]>q[y])   return x;
    else    return y;
}

insert(int k){
    int i, j, temp;
    p++;
    q[p] = k;
    i = p;
    while(q[i]>q[i/2] && i>1){
        temp = q[i];
        q[i] = q[i/2];
        q[i/2] = temp;
        i = i/2;
    }
}

int extract(){
    int i, temp, max, a;
    a = q[1];
    q[1] = q[p];
    p--;
    i = 1;
    while(i*2<=p){
        if(i*2+1<=p)    max = max_num(i*2, i*2+1);
        else    max =i*2;
        if(max_num(max, i)==max){
            temp = q[max];
            q[max] = q[i];
            q[i] = temp;
            i = max;
        }
        else break;
    }
    return a;
}

int main(){
    int i, j, k;
    char cmd[10];
    while(1){
        scanf("%s",cmd);
        if(cmd[0]=='i'){
            scanf("%d",&k);
            insert(k);
        }
        if(cmd[0]=='e' && cmd[1]=='x')  printf("%d\n",extract());
        if(cmd[0]=='e' && cmd[1]=='n')  break;
    }
    return 0;
}


Measured memory_bytes: 5664
"""
author : halo2halo
date : 25,Oct,2019
"""

import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(readline().rstrip())
lis = list(map(int, readline().rstrip().split()))


def divide2cnt(N):
    lis = []
    for i in N:
        cnt = 0
        while i % 2 == 0:
            i /= 2
            cnt += 1
        lis.append(cnt)

    return sorted(lis)[0]


print(divide2cnt(lis))


Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <list>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>
#include <bitset>
#include <cassert>

using namespace std;

/* typedef */
typedef long long ll;

/* constant */
const int INF = 1 << 30;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;

/* struct for mod Calculation*/
struct mint {
    ll x;
    mint(ll x = 0):x((x % mod + mod) % mod) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(mod - 2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }
};

/* global variables */

/* function */
struct combination {
    vector<mint> fact, ifact;
    combination(int n):fact(n+1), ifact(n+1) {
        assert(n < mod);
        fact[0] = 1;
        for (int i = 1; i <= n; i++) fact[i] = fact[i-1] * i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i] * i;
    }
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * ifact[k] * ifact[n-k];
    }
};

/* main */
int main(){
        int n, k;
    cin >> n >> k;
    k = min(k, n-1);
    combination c(n);
    mint ans;
    for (int z = 0; z <= k; z++) {
        int r = n - z;
        ans += c(n, z) * c((n - z - 1) + z, z);
    }
    cout << ans.x << '\n';
}


Measured memory_bytes: 3328
from sys import stdin
import sys
##  input functions for me
def ria(sep = ''):
    if sep == '' :
        return list(map(int, input().split())) 
    else: return list(map(int, input().split(sep)))
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##
def main():
    A, B, C = map(int, input().split())
    print("No" if (C < A and C < B) or (C > A and C > B) else "Yes")
    


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include <stdio.h>
#include <algorithm>

const int N=1e5+5;

int n,ans;

struct Node {
	int val,pos;
} a[N];

bool cmp(Node a,Node b) {
	return a.val<b.val;
}

int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
		scanf("%d",&a[i].val),a[i].pos=i;
	std::sort(a+1,a+1+n,cmp);
	for(int i=1; i<=n; i++)
		if((a[i].pos-i)%2)
			ans++;
	printf("%d",ans/2);
	return 0;
}

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

using namespace std;

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

  int f = false;

  for (int i = 0; i < n+1; i++) {
    for (int j = 0; j < n+1; j++) {
      if(i+j > n) break;
      int k = n - i - j;
      if(y == i*10000 + j*5000 + k*1000) {
        f = true;
        cout << i << " " << j << " " << k << endl;
        break;
      }
    }
    if(f) break;
  }

  if(!f) cout << "-1 -1 -1" << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
using ui = unsigned int;



template<class T,std::size_t N>
constexpr auto size(const T(&arr)[N]) {
	return N;
}

ui x[]{ 5,3,7,4,6,8,0,2,9,1};




template<class Container , class F>
auto merge(Container& arr, ui first, ui mid, ui last,F f) {
//	std::cout << first << " " << last << "\n";
	auto a = mid - first;
	auto b = last - mid;

	std::vector<ui> larr, rarr;
	larr.resize(a+1);
	rarr.resize(b+1);

	for (ui i{}; i < a; ++i) {
		larr[i] = arr[first + i];
//		std::cout << ">> L:" << larr[i]<<"\n";
	}
	for (ui i{}; i < b; ++i) {
		rarr[i] = arr[mid + i];
//		std::cout << ">> R:" << rarr[i] << "\n";
	}

	larr[a] = -1 ;//非負整数の最大値
	rarr[b] = -1 ;//同上

//	for (const auto&e : larr)
//		std::cout << e << " ";
//	std::cout << "\n";

	ui i{}, j{};
	for (ui k{ first }; k < last; ++k) {
		if ( f(larr[i] , rarr[j] ) ){
			arr[k] = larr[i];
			++i;
		}
		else {
			arr[k] = rarr[j];
			++j;
		}
	}
}

template<class Container,class F>
void merge_sort(Container &tab, ui first, ui last, F f) {

	if(first +1 <last ){

		auto mid = (first + last) / 2;
		merge_sort(tab, first, mid , f);
		merge_sort(tab, mid, last, f);
		merge(tab, first, mid, last ,f);

	}
}

template<class Container>
void merge_sort(Container &tab, ui first, ui last) {
	merge_sort(tab, first, last, [](auto x, auto y) {return x <= y; });
}


void indexer(ui left, ui right) {

	std::cout << left << " " << right << "\n";
	if (right <= left + 1)return;

	ui mid = (left + right) / 2;
	indexer(left, mid);		
	indexer(mid, right);
}

int main() {
	
/*
	for (const auto&e : x)
		std::cout << e << " ";
	std::cout << "\n";
*/

//	indexer(0, 15);

	ui n; std::cin >> n;

	std::vector<ui>v; v.resize(n);
	for (auto&e:v) {
		std::cin >> e;
	}
	//ui A[500000];

	ui count{};

	merge_sort(v, 0, n
		, [&](auto x,auto y) {
		++count;
		return x <= y;
	});

	std::cout << v.front();
	for (ui i{ 1 }; i < n; i++) 
		std::cout << " " << v[i];
	std::cout << "\n";

	std::cout << count << "\n";
/*	for (const auto&e : x)
		std::cout << e << " ";
	std::cout << "\n";
	*/

	return 0;
}


Measured memory_bytes: 6780
#include <bits/stdc++.h>
using namespace std;
long long A[51];
long long P[51];

void init() {
    A[0] = 1; P[0] = 1;
    for(int i=0; i<50; ++i) {
        A[i+1] = 2 * A[i] + 3;
        P[i+1] = 2 * P[i] + 1;
    }
}

long long solve(int N, long long X) {
    if(N == 0) {
        if(X) return 1;
        else return 0;
    }
    if(X == 1) return 0;
    else if(X <= A[N-1] + 1) return solve(N - 1, X - 1);
    else if(X == A[N-1] + 2) return P[N-1] + 1;
    else if(X <= 2 * A[N-1] + 2) return P[N-1] + 1 + solve(N-1, X - A[N-1] - 2);
    else return 2 * P[N-1] + 1;
}

int main() {
    int N;
    long long X;
    cin >> N >> X;
    init();
    cout << solve(N,X) << endl;
}

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

int main(){
    int n;
    int m;
    int a[n];
    int b[n];
    int c[n];
    cin >> n;
    cin >> m;
    int sum = 0;
    int count = 0;
    int j = 0;
    int k = 0;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      sum += a[i]; //総投票数
    }
    while (j < n){
        b[j] = a[j] * 4 * m; //得票数に4Mをかける
        c[j] = b[j] - sum; //0以上なら人気、未満なら不人気
        j++;
    }
    for (int k = 0; k < n; k++) {
        if (c[k] >= 0) {
            count += 1; //人気商品の個数
        }
        else {
        }
    }
    if (count >= m){ //人気商品の個数がm以上
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    return 0;
}

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}

const int MAX_N = 112345;
int a[MAX_N];

int main2() {
  CLR(a, 0);
  int N = nextInt();
  int M = nextInt();
  REP(i, M) {
    int L = nextInt();
    int R = nextInt();
    a[L]++;
    a[R+1]--;
  }
  for (int i = 1; i <= MAX_N; i++) {
    a[i] += a[i-1];
  }
  int ans = 0;
  for (int i = 1; i <= MAX_N; i++)
    if (a[i] == M)
      ans++;

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

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}


Measured memory_bytes: 640
def main():
    N, Q = map( int, input().split())
    A = list( map( int, input().split()))
    bit = [0]*N
    def add(bit,a,w):#リストに値を追加する関数
        x = a
        while x <= N:
            bit[x-1] += w
            x += x&(-x)

    def sums(bit,a):#k番目までの和
        x = a
        S = 0
        while x > 0:
            S += bit[x-1]
            x -= x&(-x)
        return S

    for i, a in enumerate(A):
        add(bit,i+1,a)
    Q = [ tuple( map( int, input().split())) for _ in range(Q)]
    ANS = []
    for q,p,x in Q:
        if q == 0:
            add(bit,p+1,x)
        else:
            ANS.append( sums(bit,x)-sums(bit,p))
    print( "\n".join( map( str, ANS)))
if __name__ == '__main__':
    main()


Measured memory_bytes: 151228
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string o,s;
  cin>>o>>s;
  string x;
  x="";
  int N=o.size();
  for(int i=0;i<N;i++){
   char a=o.at(i);
    x+=a;
    if(s.size()>i){
   char b=s.at(i);
    x+=b;
    }
  }
  cout<<x<<endl;
}
    

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <unordered_map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e15;
const ll MOD = 1000000007;
const ll MOD2 = 998244353;
typedef pair<ll,ll> P;
typedef pair<double,double> point;
const ll MAX = 200005;
constexpr ll nx[8] = {1,0,-1,0,1,-1,1,-1};
constexpr ll ny[8] = {0,1,0,-1,1,1,-1,-1};
vector<ll> pop(MAX,0);
void init(){
    rep(i,1,MAX){
        ll s = 0,a = i;
        while(a > 0){
            s += a%2;
            a /= 2;
        }
        pop[i] = pop[i%s]+1;
    }
}
ll mod_pow(ll n, ll p, ll m){
    ll ret = 1;
    ll mul = n%m;
    while(p){
        if (p&1) ret = ret*mul%m;
        p >>= 1;
        mul = mul*mul%m;
    }
    return ret;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    string x;
    cin >> n >> x;
    ll a = 2;
    init();
    ll p = 0;
    rep(i,x.length()){
        if (x[i] == '1') p++;
    }
    ll m = x.length(),bitp = 1,bitm = 1,cntp = 0,cntm = 0;
    rep(i,m){
        (cntp += bitp*(x[m-i-1]-'0'))%=p+1;
        if (p > 1) (cntm += bitm*(x[m-i-1]-'0'))%= p-1;
        (bitp *= 2)%=p+1;
        if (p > 1) (bitm *= 2)%=p-1;
    }
    //PRINT(cntp << " " << cntm);
    rep(i,n){
        ll s = n-i-1;
        if (x[i] == '0'){
            ll cnt = (cntp+mod_pow(2,s,p+1))%(p+1);
            PRINT(pop[cnt]+1);
        }
        else{
            if (p == 1){
                PRINT(0);
            }
            else{
                ll cnt = (cntm+p-1-mod_pow(2,s,p-1))%(p-1);
                PRINT(pop[cnt]+1);
            }
        }
    }
}


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

#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ii pair<int,int>
#define vi vector<int>
#define vll vector<ll>
#define vii vector<ii>

using namespace std;

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//#ifndef ONLINE_JUDGE
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	//#endif
	int n;
	cin>>n;
	vi a(n),b(n),c(n);iota(all(c),1);
	for(int i=0;i<n;++i){
		cin>>a[i];
	}
	for(int i=0;i<n;++i){
		cin>>b[i];
	}
	int l,r,x=0;
	do{
		if(c==a) l = x;
		if(c==b) r = x;
		++x;
	}while(next_permutation(all(c)));
	cout<<abs(r-l)<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
using namespace std;
int main(void){
    int a,b ;
    cin >> a;
    cin >> b;
    int d=a/b;
    int r=a%b;
    double f=double(a)/double(b) ;
    cout << d;
    cout <<" ";
    cout << r;
    cout <<" ";
    cout << fixed << setprecision(5)<<f;
    cout <<endl;
    
}


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

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

using ll = long long;
using lb = long double;
using P = pair<ll,ll>;
using graph = vector<vector<ll>>;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const ll INF = 1LL<<60;
const ll mod = 1000000007LL;

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

int main() {
  int N;
  cin>>N;
  vector<int> v(N);
  rep(i,N) cin>>v[i];
  vector<int> ans(N);
  rep(i,N){
    ans[v[i]-1] = i+1;
  }
  rep(i,N) cout<<ans[i]<<" ";
  cout<<endl;
}

Measured memory_bytes: 3956
using System;
using System.Linq;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        var AB = ReadLine().Split(' ').Select(s => double.Parse(s)).ToArray();
        var (A, B) = (AB[0], AB[1]);

        var ans = 0;
        var possible = false;
        var yen = 0;

        while(true)
        {
            var aTax = Math.Floor(yen * 0.08);
            var bTax = Math.Floor(yen * 0.10);

            if (aTax > 100 || bTax > 100)
                break;

            if (aTax == A && bTax == B)
            {
                ans = yen;
                possible = true;
                break;
            }

            yen++;
        }

        if (!possible)
            ans = -1;

        WriteLine(ans);
    }
}


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

using namespace std;

int Atoi(const char);

int main(){
  int i, j, n, x, y;
  char c; 
  string str, _str, data[9];

  data[0] = ".,!? ";
  data[1] = "abc";
  data[2] = "def";
  data[3] = "ghi";
  data[4] = "jkl";
  data[5] = "mno";
  data[6] = "pqrs";
  data[7] = "tuv";
  data[8] = "wxyz";

  cin >> n;

  for(i=0; i<n; ++i){
    cin >> str;

    for(j=0, c='0'; j<str.size(); ++j){
      if(c != str[j]){
	if(c == '0'){
	  y = 0;
	  c = str[j];
	}else{
	  x = Atoi(c)-1;
	  y %= data[x].size();
	  _str.push_back(data[x][y]);
	  c = '0';
	}
      }else if(c != '0'){
	++y;
      }
    }

    cout << _str << endl;
    _str.clear();
  }
  return 0;
}

int Atoi(const char c){
  int x;
  x = c - 48;
  return x;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

int gcd(int x,int y) {
  if (y == 0) return x;
  return gcd(y, x%y); 
}
int main() {
  int n; cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  vector<int> l(n), r(n);
  rep(i, n-1) l[i+1] = gcd(l[i], a[i]);
  for (int i = n-1;  i >= 1; i--) r[i-1] = gcd(r[i], a[i]);
  int ans = 1;
  rep(i, n) ans = max(ans, gcd(l[i], r[i]));
  cout << ans << endl;
}

Measured memory_bytes: 1408
N = int(input())
A = list(map(int, input().split()))
sA = [A[0]]
d = []
for i in range(1, N):
    sA.append(sA[-1] + A[i])

for i in range(N):
    d.append(abs(sA[i] - (sA[-1] - sA[i])))
print(min(d))


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


using namespace std;

const int MAX = 100000 + 10;
bool prime[MAX];

int a[MAX];
void primer(){
    int i, j;
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1] = false; prime[2] = true;
     for(i = 2; i * i <= MAX; i ++)
     {
         if(prime[i])
            {
             for(j = i + i; j <= MAX; j += i)
                 prime[j] = false;
         }
    }
}

int main(){
    primer();
    int n,cnt = 0;

    for(int i = 1; i <= 100000; i += 2)
        if((i&1)&&prime[(i + 1)/2] &&prime[i]) a[cnt++] = i;

    scanf("%d", &n);
    while(n--){
    int l = 1, r = 1, c = 0;
    scanf("%d%d",&l, &r);
    for(int i = 0; i < cnt; i++) if(a[i] >= l && a[i] <= r) c++;

    printf("%d\n", c);
    }

}


Measured memory_bytes: 768
n,k=map(int,input().split())
a=list(map(int,input().split()))
# dp[i]=石の個数が残り i 個の局面が勝ちか負けかを bool 値で表したもの
dp=[False]*(10**5+1)
dp[0]=False
for aa in a:
  dp[aa]=True

for i in range(1,k+1):
  ok=False
  for j in range(n):
    if i-a[j]>=0:
      if dp[i-a[j]]==0:
        ok=True
  if ok: 
    dp[i]=True
# print(dp[k])
print("First") if dp[k] else print("Second")


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

using namespace std;

int main(){
    long long int N,ans=1,div=1000000000000000000;
    cin >> N;
    vector<long long int> A(N);

    for(int i=0;i<N;i++){
        cin >> A[i];
        if(A[i]==0){
            cout << 0 << endl;
            return 0;
        }
    }

    for(int i=0;i<N;i++){
        div /= A[i];
        if(div==0){
            cout << -1 << endl;
            return 0;
        }
    }


    for(int i=0;i<N;i++){
        ans *= A[i];
    }

    cout << ans << endl;
}

Measured memory_bytes: 4052
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a[100000],b[100000],cnt=1,ans;
map<ll,ll> mp;
int main(void){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b,b+n);
    for(int i=0;i<n;i++){
        mp[b[i]]=cnt++;
    }
    for(int i=0;i<n;i++){
        a[i]=mp[a[i]];
    }
    for(int i=0;i<n;i+=2){
        if(a[i]%2==0)ans++;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 8064
#include<iostream>
using namespace std;
int main()
{
  int N;
cin >> N;
  string s,t;
  cin >> s >> t;
  for(int i=0;i<N;i++){
  char s_i =s.at(i);
  char t_i = t.at(i);
  cout << s_i << t_i;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <cstring>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
static const int INF = 1000010000;
static const int MOD = 100000;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define SORT(v) sort(v.begin(), v.end());
#define pb push_back
#define mp make_pair
#define np next_permutation
#define pq priority_queue

//int dx4[4] = {0,1,0,-1}, dy4[4] = {-1,0,1,0};
//int dx5[5] = {-1,0,0,0,1}, dy5[5] = {0,-1,0,1,0};
//int dx8[8] = {-1,0,1,1,1,0,-1,-1}, dy8[8] = {1,1,1,0,-1,-1,-1,0};
//int dx9[9] = {-1,0,1,1,1,0,-1,-1,0}, dy9[9] = {1,1,1,0,-1,-1,-1,0,0};

struct edge {
	int u, v;
	ll cost;
};

const int mn = 100010;
vector<P> x, y;

#define N 100010

bool comp(const edge& e1, const edge& e2) {
	return e1.cost < e2.cost;
}

int par[N];
int urank[N];

void init(int n) {
	REP(i, n) {
		par[i] = i;
		urank[i] = 0;
	}
}

int find(int x) {
	if (par[x] == x) {
		return x;
	}
	else {
		return par[x] = find(par[x]);
	}
}

void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return;

	if (urank[x] < urank[y]) {
		par[x] = y;
	}
	else {
		par[y] = x;
		if (urank[x] == urank[y]) urank[x]++;
	}
}

bool same(int x, int y) {
	return find(x) == find(y);
}

edge es[N * 2];

ll kruskal(int E) {
	sort(es, es + E, comp);
	ll res = 0;
	REP(i, E) {
		edge e = es[i];
		if (!same(e.u, e.v)) {
			unite(e.u, e.v);
			res += e.cost;
		}
	}
	return res;
}


int main() {
	int n;
	cin >> n;
	int E = 0;
	REP(i, n) {
      	P a, b;
		cin >> a.first >> b.first;
		a.second = b.second = i;
      	x.pb(a); y.pb(b);
	}

	init(n);
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
	REP(i, n - 1) {
		edge e;
		e.u = x[i].second; e.v = x[i + 1].second; e.cost = x[i + 1].first - x[i].first; es[i] = e; E++;
		e.u = y[i].second; e.v = y[i + 1].second; e.cost = y[i + 1].first - y[i].first; es[i + n - 1] = e; E++;
	}
	cout << kruskal(E) << endl;
}

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

#define FAST_IO                       \
	ios_base::sync_with_stdio(false); \
	cin.tie(0);                       \
	cout.tie(0);

#define debug(a) cout << #a << " " << a << endl;
#define _debug(a, i) cout << #a << "[" << i << "]" << " = " << a[i] << endl;

using namespace std;

using ll = long long;

const int MOD = 998244353;
const ll INF_LLONG = 1e18 + 9;
const int INF_INT = 1e9 + 9;

template<typename T>
unsigned int index_of_max(vector<T>& arr) {
	unsigned int idx = 0;
	for (int i = 0; i < arr.size(); ++i) {
		if (arr[i] > arr[idx])
			idx = i;
	}
	return idx;
}

template<typename T>
unsigned int index_of_min(vector<T>& arr) {
	unsigned int idx = 0;
	for (int i = 0; i < arr.size(); ++i) {
		if (arr[i] < arr[idx])
			idx = i;
	}
	return idx;
}

bool isPalindrome(string s, int l, int r) {
	for (; l <= r; ++l, --r) {
		if (s[l] != s[r])
			return false;
	}
	return true;
}

const int MAXN = 3005;
ll dp[MAXN][MAXN];

int main()
{
	//	#ifndef ONLINE_JUDGE
	//		(void)freopen("input.txt", "r", stdin);
	//		(void)freopen("output.txt", "w", stdout);
	//	#endif	
	FAST_IO;
	int n;
	cin >> n;
	vector<ll> a(n);
	for (auto& x : a)
		cin >> x;
	// dp[0][n-1]
	for (int L = n-1; L >= 0; --L) {
		for (int R = L; R < n; ++R) {
			if (L == R)
				dp[L][R] = a[L];
			else
				dp[L][R] = max(a[L] - dp[L + 1][R], a[R] - dp[L][R - 1]);
		}
	}
	cout << dp[0][n - 1];
	return 0;
}




Measured memory_bytes: 70016
#include <iostream>
using namespace std;
int main(void){
    int s1[5], s2[5]; //午前と午後の販売個数
    
    while(true){
        for(int i = 0; i < 5; i++){
            cin >> s1[i] >> s2[i];
            if(s1[0] == 0 && s2[0] == 0) return 0;
        }

        int sum[5]; //１日の販売個数
        int max = 0; //１日の販売個数の最大値
        char n[5] = {'A', 'B', 'C', 'D', 'E'}; //店名
        int p; //１日の販売個数が最大のお店

        for(int i = 0; i < 5; i++){
            sum[i] = s1[i] + s2[i];
            if(sum[i] > max){
                max = sum[i];
                p = i;
            }
        }
        cout << n[p] << " " << max << endl;
    }
        /*if(max_name == 1) cout << "A" << " " << max << endl;
        if(max_name == 2) cout << "B" << " " << max << endl;
        if(max_name == 3) cout << "C" << " " << max << endl;
        if(max_name == 4) cout << "D" << " " << max << endl;
        if(max_name == 5) cout << "E" << " " << max << endl;*/
}  



Measured memory_bytes: 3068
#include<stdio.h>
#include<string.h>

int main(){
	int n,m;
	scanf("%d%d", &n, &m);
	int suki[n+1], A[n+1][m+1];
	int sukicount[m+1];
	for(int i=0; i<m+1; i++){
		sukicount[i]=0;
	}
	for(int i=1; i<=n; i++){
		scanf("%d", &suki[i]);
		for(int j=1; j<=suki[i]; j++){
			scanf("%d", &A[i][j]);
			sukicount[A[i][j]]++;
		}
	}
	
	int food_count=0;
	for(int i=1; i<=m; i++){
		if(sukicount[i] == n) food_count++;
	}
	
	printf("%d", food_count);
	
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<string>
using namespace std;
int main() {
	int a, b, c, d; cin >> a >> b >> c >> d;
	if ((c - 1) / b <= (a - 1) / d) {
		cout << "Yes" << endl;
		return 0;
	}
	cout << "No" << endl;
}

Measured memory_bytes: 3620
l, r = map(int, input().split())

list_ = []
c = 0

while c < 2019:
    if c > r - l:
        break
    list_.append((l+c) % 2019)
    c += 1

list_.sort()
ans = 1000000
for i in range(len(list_)):
    for j in range(len(list_)):
        if i != j:
            ans = min(ans, (list_[i] * list_[j]) % 2019)
print(ans)


Measured memory_bytes: 41436
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

bool ans=true;
vector<pair<ll,ll>>a[100010];
ll co[100010];
void dep(ll now,ll cos){
	for(ll i=0;i<a[now].size();i++){
		ll next=a[now][i].first;
		ll val=a[now][i].second;
		if(co[next]!=INF){
			ll ch=co[now]+val;
			if(ch!=co[next]){
				ans=false;
			}
			continue;
		}
		co[next]=co[now]+val;
		dep(next,co[next]);
	}
}
int main() {
	ll n,m;
	cin>>n>>m;
	for(ll i=0;i<m;i++){
		ll x,y,z;
		cin>>x>>y>>z;
		x--;y--;
		a[x].push_back(make_pair(y,z));
		a[y].push_back(make_pair(x,-1*z));
	}
	for(ll i=0;i<n;i++){
		co[i]=INF;
	}
	for(ll i=0;i<n;i++){
		if(co[i]!=INF){
			continue;
		}
		co[i]=0;
		dep(i,co[i]);
	}
	cout << (ans?"Yes":"No");
	// your code goes here
	return 0;
}

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

int64_t cubic(const int64_t x) {
	return x*x*x;
}

void print(const int64_t x) {
	cout << x << endl;
}

int main() {
	int64_t x;
	cin >> x;
	
	//print x^3
	print(cubic(x));
	
	return 0;
}

Measured memory_bytes: 3100
import copy
s = list(str(input()))
t = list(str(input()))
#print(s)

bool =True
cnt =0
while bool:
    S =s.copy()
    for i in range(len(s)):
        if i == 0:
            s[0]=S[-1]
        else:
            s[i]=S[i-1]
    #print(s)
    if s==t:
        print('Yes')
        exit()
    cnt +=1
    if cnt == len(s):
        bool =False
print('No')

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
    int n;
    cin >> n;
    vector<int> data(n);
    for (int i = 0; i < n; i++)
    {
        cin >> data[i];
    }
    int ans = 0;
    int i, j;
    for (i = 0; i < n; i++)
    {
        for (j = i + 1; j < n; j++)
        {
            ans += data[i] * data[j];
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <map>
#include <algorithm>
#include <cassert>
#include <climits>
#include <complex>
#include <cstdio>
#include <string>
#include <iostream>
#include <queue>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
using ll = long long;
using ld = long double;
template<class T> bool chmin(T &a, T b) { return a>b?(a=b,true):false; }
template<class T> bool chmax(T &a, T b) { return a<b?(a=b,true):false; }
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
#define FOR(i,x,y) for(int i=(x);i<(int)(y);i++)
#define FORP(i,x,y) for(int i=(x);i<=(int)(y);i++)
#define REP(i,y) for(int i=0;i<(int)(y);i++)
#define REPP(i,y) for(int i=1;i<=(int)(y);i++)
#define REPB(i,n) for(int i=(int)(n)-1;i>=0;i--)

string s;
map<int,int> mp;

int main() {
  cin>>s;
  ll n=s.length();
  for (char c : s) mp[c-'a']++;
  ll res = 0;
  REP(i,26)
  {
    if (mp[i]>1) res += (mp[i] * 1LL * (mp[i]-1)) / 2;
  }
  cout << (n*(n-1))/2 + 1LL - res << endl;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repe(i, n) for (int i = 0; i <= (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define reps(i, s, n) for (int i = (s); i < (n); ++i)
#define repse(i, s, n) for (int i = (s); i <= (n); ++i)
#define repsr(i, n, s) for (int i = (n); i >= (s); --i)
const int64_t inf = (int64_t)1e18;
const int64_t mod = (int64_t)1e9 + 7;

int main() {
  int N, M; cin >> N >> M;
  vector<int> foods(M + 1, 0);
  rep(i, N) {
    int K; cin >> K;
    rep(j, K) {
      int A; cin >> A;
      foods[A]++;
    }
  }
  int ans = 0;
  repse(i, 1, M) {
    if (foods[i] == N) ans++;
  }
  cout << ans << endl;
  return 0;
}

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

int main(){
	int a, b, c, x=0, y=0;
	while( scanf(" %d,%d,%d", &a, &b, &c) != EOF ){
		
		if(c*c == a*a+b*b) ++x;
		else if(a==b) ++y;
	
	}
	
	printf("%d\n%d\n", x, y);

	return 0;
}

Measured memory_bytes: 1188