akhauriyash/Code-Regression huggingface dataset:
//#include "pch.h"
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

//#include <vector>
//#include <set>
//#include <map>
//#include <iostream>

#define ll long long
#define fri(n) for(i=0;i<(n);i++)
#define frj(n) for(j=0;j<(n);i++)
#define min(p,q) ((p)<(q)?(p):(q))
#define max(p,q) ((p)>(q)?(p):(q))
#define swap(p,q) r=(p);(p)=(q);(q)=r
#define INF 1000000000000//10^12



int main(void)
{
	//変数の宣言
	int q;
	static char s[100010];
	static char t[100010];
	static int a[100010];
	static int b[100010];
	static int c[100010];
	static int d[100010];
	static int ruiseki_s[100010];
	static int ruiseki_t[100010];

	//よく使う変数
	int i,j,k,l;
	int flag=0;
	int ans=0;
	int count=0;
	int temp,temp1,temp2;
	int max,min;
	int len;
	int sum=0;



	//データの読み込み

	scanf("%s",&s);
	scanf("%s",&t);
//	scanf_s("%s",&s,100010);
//	scanf_s("%s",&t,100010);

	scanf("%d",&q);
//	scanf_s("%d",&q);

	for(i=0;i<q;i++){
		scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
//		scanf_s("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
	}

	//	printf("nは%dです\n", n);
	//	printf("データの読み込み終了\n");
	//実際の処理
	
	ruiseki_s[0]=0;
	len=strlen(s);
	for(i=0;i<len;i++){
		if(s[i]=='A'){
			ruiseki_s[i+1]=(ruiseki_s[i]+1)%3;
		}else{
			ruiseki_s[i+1]=(ruiseki_s[i]+2)%3;
		}
	}

	ruiseki_t[0]=0;
	len=strlen(t);
	for(i=0;i<len;i++){
		if(t[i]=='A'){
			ruiseki_t[i+1]=(ruiseki_t[i]+1)%3;
		}else{
			ruiseki_t[i+1]=(ruiseki_t[i]+2)%3;
		}
	}
	
	for(i=0;i<q;i++){
		temp1=ruiseki_s[b[i]]-ruiseki_s[a[i]-1];
		temp2=ruiseki_t[d[i]]-ruiseki_t[c[i]-1];
		if((temp1-temp2)%3==0){
			printf("YES\n");
		}else{
			printf("NO\n");
		}
	}

	//	printf("計算部分終了\n");

	//出力

	//printf("%d",ans);

	//	printf("結果の出力終了\n");


	return 0;
}



Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = (1 << 30) - 1;

int H, W, ans, dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
char grid[1111][1111];
queue<pair<int, pair<int, int>>> que;

int main()
{
    cin >> H >> W;
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            cin >> grid[i][j];
            if (grid[i][j] == '#')
                que.emplace(0, make_pair(i, j));
        }
    }

    while (!que.empty())
    {
        auto p = que.front();
        que.pop();
        int y = p.second.first, x = p.second.second, cnt = p.first;
        if (cnt != 0 && grid[y][x] == '#')
            continue;
        ans = max(cnt, ans), grid[y][x] = '#', cnt++;
        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i], nx = x + dx[i];
            if ((ny < 0 || ny >= H) || (nx < 0 || nx >= W) || (grid[ny][nx] == '#'))
                continue;
            que.emplace(cnt, make_pair(ny, nx));
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 13456
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;
ll MOD = 1e9 + 7;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> x(m);
    for (int i = 0; i < m; i++) {
        cin >> x[i];
    }
    int ans = 0;
    if (n < m) {
        vector<int> dif(m - 1);
        sort(x.begin(), x.end());
        for (int i = 0; i < m - 1; i++) {
            dif[i] = abs(x[i + 1] - x[i]);
        }
        sort(dif.begin(), dif.end());
        for (int i = 0; i < m - n; i++) {
            ans += dif[i];
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4032
#include <stdio.h>
#include <stdlib.h>
 
int main(void) {
  int N;
  scanf("%d", &N);
 
  int X[100];
  int Y[100];
  int H[100];
  for(int i = 0; i < N; i++) {
    scanf("%d %d %d", &X[i], &Y[i], &H[i]);
  }
 
  int init;
  for(init = 0; init < N; init++) {
    if(H[init] != 0) break;
  }
 
  for(int x = 0; x <= 100; x++) {
    for(int y = 0; y <= 100; y++) {
      int height = H[init] + abs(X[init] - x) + abs(Y[init] - y);
 
      int flag = 0;
      for(int i = 0; i < N; i++) {
	int tmpH = height - abs(x - X[i]) - abs(y - Y[i]);
	if(tmpH < 0) tmpH = 0;
	if(tmpH != H[i]) {
	  flag = 1;
	  break;
	}
      }
	
      if(flag == 0) {
	printf("%d %d %d\n", x, y, height);
	return 0;
      }
    }
  }
  
  return 0;
}

Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;

// GNU C Compiler
//template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

// type
using ll = int_fast64_t;
using ull = uint_fast64_t;
using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
//using pair<T1, T2> = p12;

//container
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
#define ALL(v) v.begin(),v.end()

//repetition
#define REP(n) for(ll i=0; i<(n); i++)
#define REPj(n) for(ll j=0; j<(n); j++)
#define REPinit(i,a,n) for(ll i=(a); i<(n); i++)
#define REPinitj(j,a,n) for(ll j=(a); j<(n); j++)

//algorithm
#define SORT(c) sort((c).begin(),(c).end())
#define CONTAINER_ALL(a) a.begin(),a.end()

//constant

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//Optimizer
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")


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

    int T, X;
    cin >> T >> X;
    printf("%.10lf\n", (static_cast<double>(T) / static_cast<double>(X)));

    return 0;
}


Measured memory_bytes: 3748
#include <stdio.h>
#include <math.h>

int main(){
  double a, b, c, s, l, h;
  scanf("%lf%lf%lf", &a, &b, &c);
  h = b * sin(c * M_PI / 180);
  s = a * h / 2;
  l = a + b + (pow((a - b * cos(c * M_PI / 180)) * (a - b * cos(c * M_PI /180)) + h * h, 0.5));
  printf("%lf\n%lf\n%lf\n", s, l, h);
}



Measured memory_bytes: 2968
#include<stdio.h>

int main(void){
  int n;
  int m;
  int i=0;
  int l=0;
  int r = 0;
  int min = n;
  int max = 0;
  scanf("%d", &n);
  scanf("%d", &m);
  for(i=0;i<m;i++){
    scanf("%d", &l);
    if(max<l){
      max = l;
    }
    scanf("%d", &r);
    if(r<min){
      min = r;
    }
  }
  if(min-max<0){
    printf("0");
  }else{
    printf("%d", min-max+1);
  }
  return 0;
}

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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define mp(a,b) make_pair((a),(b))
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define dump(x)
#endif

typedef long long int ll;
typedef pair<int,int> pii;
//template<typename T> using vec=std::vector<T>;

const int INF=1<<30;
const long long int INF_=1LL<<58;
const double EPS=1e-9;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
	os << "[";
	for (const auto &v : vec) {
		os << v << ",";
	}
	os << "]";
	return os;
}

void Solve(){
	int n,K;
	scanf("%d%d",&n,&K);

	vector<pair<double,double>> ps;
	const double PI=3.14159265359;
	rep(i,0,n){
		double x,y,r;
		scanf("%lf%lf%lf",&x,&y,&r);
		if(y+r<=0) continue;
		if(y-r<=0){
			double f,s;
			if(x<0){
				f=atan2(y,x)-asin(r/sqrt(x*x+y*y));
				s=PI;
			}else{
				f=0;
				s=atan2(y,x)+asin(r/sqrt(x*x+y*y));
			}
			while(f<0) f+=PI;
			while(s<0) s+=PI;
			ps.push_back(mp(f,s));
		}else ps.push_back(mp(atan2(y,x)-asin(r/sqrt(x*x+y*y)),atan2(y,x)+asin(r/sqrt(x*x+y*y))));
	}
	
	sort(ps.begin(),ps.end());
	ps.erase(unique(ps.begin(),ps.end()),ps.end()); //同じ区間があると次の処理で面倒なので消しておく

	//他の区間に完全に包含されているものを取り除く
	vector<pair<double,double>> tmp;
	rep(i,0,ps.size()){
		bool ok=true;
		rep(j,0,ps.size()){
			if(i==j) continue;
			if(ps[j].first<=ps[i].first&&ps[i].second<=ps[j].second){
				ok=false;
				break;
			}
		}
		if(ok) tmp.push_back(ps[i]);
	}
	ps=tmp;

	if(ps.size()==0){
		cout << 0 << endl;
		return;
	}

	vector<int> a(ps.size()); //a[i]=i番目の区間とギリギリ重なってる区間。存在しない場合はもっとも近いやつ
	rep(i,1,ps.size()){
		rep(j,0,i+1){
			if(ps[j].second>=ps[i].first){
				a[i]=j;
				break;
			}
		}
		if(a[i]==i) a[i]=i-1;
	}

	static double dp[1500][1501][2]; //dp[i][j][k]=i番目の区間まででj個取って、i番目の区間を使った(k==1)or使わなかった(k==0)ときの最大
	dp[0][0][0]=0;
	dp[0][1][1]=ps[0].second-ps[0].first;
	double ans=dp[0][1][1];
	rep(i,1,ps.size()){
		rep(j,0,K+1){
			dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);
			if(j==0) continue;
			//a[i]番目の区間を使った場合は重複している部分を取り除く、使わなかった場合は重なっていないのでそのまま足す。
			dp[i][j][1]=max(dp[a[i]][j-1][1]+ps[i].second-max(ps[i].first,ps[a[i]].second),dp[a[i]][j-1][0]+ps[i].second-ps[i].first);
			ans=max({ans,dp[i][j][1],dp[i][j][0]});
		}
	}

	printf("%.10lf\n",ans/PI);
}

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

Measured memory_bytes: 36584
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdio>
#include<cmath>
#define pb(in,tmp) in.push_back(tmp)
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,b) loop(i,0,b)
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
using namespace std;
int main(){
  int n;
  while(cin>>n,n){
    char in[100]={'\0'};
	cin>>in;
	vector< vector<int> >a(21);
    rep(i,strlen(in))a[0].push_back(in[i]-'0');
	a[0].push_back(-1);
	rep(i,n){
	  //rep(j,a[i].size()-1)cout<<a[i][j];
	  //cout<<endl;
	  int co=0;
	  int h=a[i][0];
	  rep(j,a[i].size()){
	    if(a[i][j]==h)co++;
		else{
		  if(co==100){a[i+1].push_back(1);a[i+1].push_back(0);}
		  else if(co>=10)a[i+1].push_back(co/10);
		  a[i+1].push_back(co%10);
		  a[i+1].push_back(h);
		  co=1;
		  h=a[i][j];
		}
	  }
	  a[i+1].push_back(-1);
	}
	rep(i,a[n].size()-1)cout<<a[n][i];
	cout<<endl;
  }
}

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

int main() {
  int a,b,c,d; cin >> a >> b >> c >> d;
  int left = a + b, right = c + d;
  if(right - left > 0) cout << "Right";
  else if (right - left < 0) cout << "Left";
  else cout << "Balanced";
  
  cout << endl;
  
  return 0;
}

Measured memory_bytes: 256
#prag\
ma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	int n,y;
	cin>>n>>y;
	int x=y/1000;
	if(n>x){cout<<"-1 -1 -1";return 0;}
	if(n==x){cout<<"0 0 "<<x;return 0;}
	x-=n;
	if(x<4){cout<<"-1 -1 -1";return 0;}
	for(int i=0;i<=x/9;i++)
		for(int j=0;j<=x/4;j++)
			if(9*i+4*j==x&&n-i-j>=0){
				cout<<i<<' '<<j<<' '<<n-i-j;
				return 0;
			}
	cout<<"-1 -1 -1";return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main() {
    unsigned long long a, b, n;
    cin >> n >> a >> b;
    unsigned long long x = (n / (a + b)) * a;
    unsigned long long mod = n % (a + b);
    cout << x + min(mod, a) << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int n;
  cin >>n;
  while(n--){
    int edge[3];
    for(int i=0; i<3; i++){cin >>edge[i];edge[i] = edge[i]*edge[i];}
    if(edge[0] == edge[1]+edge[2] || edge[1] == edge[2]+edge[0] || edge[2] == edge[0]+edge[1]) cout <<"YES"<<endl;
    else cout <<"NO"<<endl;
  }
  return 0;
}

Measured memory_bytes: 1152
#Back and Forth
#四角形を描くようにして移動する
#次に，四角形より最初と最後1つずらした形を構成する．

def sign(x):
    if x > 0:
        return 1
    if x == 0:
        return 0
    
    return -1

def solve():
    move_x = ["", "R", "L"]
    move_y = ["", "U", "D"]
    
    sx, sy, tx, ty = list(map(int, input().split()))
    
    dx = tx - sx
    dy = ty - sy

    outward = ""
    homeward = ""


    if dx == 0 and dy == 0:
        print()
        return
    
    if dx == 0:
        outward = move_y[sign(dy)] * abs(dy)
        homeward = move_y[-sign(dy)] * abs(dy)

        fir_route = outward + "R" + homeward + "L"
        sec_route = "L" + outward + "R" + move_y[sign(dy)] + "RR" + move_y[-sign(dy)] + homeward + move_y[-sign(dy)] + "LL" + move_y[sign(dy)]

        print(fir_route, end="")
        print(sec_route)

        return

    if dy == 0:
        outward = move_x[sign(dx)] * abs(dx)
        homeward = move_x[-sign(dx)] * abs(dx)

        fir_route = outward + "U" + homeward + "D"
        sec_route = "D" + outward + "U" + move_x[sign(dx)] + "UU" + move_x[-sign(dx)] + homeward + move_x[-sign(dx)] + "DD" + move_x[sign(dx)]

        print(fir_route, end="")
        print(sec_route)

        return
    
    outward = move_x[sign(dx)] * abs(dx) + move_y[sign(dy)] * abs(dy)
    homeward = move_x[-sign(dx)] * abs(dx) + move_y[-sign(dy)] * abs(dy)
    
    fir_route = outward + homeward
    sec_route = move_y[-sign(dy)] + move_x[sign(dx)] + outward + move_y[sign(dy)] + move_x[-sign(dx)] + move_y[sign(dy)] + move_x[-sign(dx)] + homeward + move_y[-sign(dy)] + move_x[sign(dx)]

    print(fir_route, end="")
    print(sec_route)

if __name__ == "__main__":
    solve()

Measured memory_bytes: 3192
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a),i##_end=(b);i<=i##_end;i++)
#define per(i,b,a) for(int i=(b),i##_st=(a);i>=i##_st;i--)
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define debug(x) cerr<<#x" = "<<x<<endl
#define Debug(...) fprintf(stderr, __VA_ARGS__)
#define Es(x,i) for(Edge *i=G[x];i;i=i->nex)
typedef pair<int,int> pii;
typedef long long ll;
const int inf=~0u>>1,MOD=1e9+7;/*
char *TT,*mo,but[(1<<15)+2];
#define getchar() ((TT==mo&&(mo=((TT=but)+fread(but,1,1<<15,stdin)),TT==mo))?-1:*TT++)//*/
inline int rd() {
	int x=0,c=0,f=1;
	for(; c<'0'||c>'9'; c=getchar())f=c!='-';
	for(; c>='0'&&c<='9'; c=getchar())x=x*10+c-'0';
	return f?x:-x;
}
const int N=1e5+5;
struct Node{
	int l,r;
	bool operator<(const Node&t)const{
		return r-l<t.r-t.l;
	}
} p[N*3];
int c[N],n,m;
void updata(int x,int v){
	while(x<=m){
		c[x]+=v;
		x+=(x&-x);
	}
}
int query(int x){
	int ret=0;
	while(x){
		ret+=c[x];
		x^=(x&-x);
	}
	return ret;
}
int main(){
	n=rd(),m=rd();
	rep(i,1,n){
		p[i].l=rd(),p[i].r=rd();
		//p[i].len=p[i].r-p[i].l+1;
	}
	sort(p+1,p+n+1);
	int now=1;
	rep(i,1,m){
		while(now<=n&&p[now].r-p[now].l+1<i){
			updata(p[now].l,1);
			updata(p[now].r+1,-1);
			now++;
		}
		/*debug(now);
		debug(p[now].l);
		debug(p[now].r);*/
		int tmp=0;
		for(int j=i;j<=m;j+=i)tmp+=query(j);
		printf("%d\n",n-now+1+tmp);
	}
}

Measured memory_bytes: 3712
#include<iostream>

int main() {
  int N;
  std::cin >> N;
  int temp_N = N;
  int sum = 0;
  while (temp_N!=0) {
    sum += temp_N%10;
    temp_N /= 10;
  }
  if (N % sum == 0) {
    std::cout << "Yes" << std::endl;
  }
  else {
    std::cout << "No" << std::endl;
  }
}


Measured memory_bytes: 256
from collections import defaultdict
import sys
sys.setrecursionlimit(100*sys.getrecursionlimit())
V, E = map(int, input().split())
G = defaultdict(list)
T = defaultdict(list)
for i in range(E):
    s,t = map(int, input().split())
    G[s].append(t)
    G[t].append(s)

prenum = [float('inf')] * V
lowest = [float('inf')] * V
parent = [None] * V
visited = [False] * V

def dfs(g,s,c=0,p=None):    
    visited[s] = True
    prenum[s] = c
    lowest[s] = c
    c+=1    
    for v in g[s]:
        if not visited[v]:
            parent[v] = s
            T[v].append(s)
            T[s].append(v)
            dfs(g,v,c,s)
            lowest[s] = min( lowest[s], lowest[v] )
        elif v != p:
            lowest[s] = min( lowest[s], prenum[v] )

dfs(G,0)
k = []
if len(T[0]) > 1: k.append(0)
for u in range(V):
    p = parent[u]
    if p is None or p == 0: continue
    if prenum[p] <= lowest[u]: k.append(p)
for i in sorted(set(k)):
    print(i)

Measured memory_bytes: 24088
A,B,C,X,Y = map(int,input().split())
ans1 = 0
ans2 = 0
ans1 = X*A+B*Y
ans2 = min(X,Y)*C*2
ans3 = max(X,Y)*C*2
if X>Y:
    ans2+=(X-Y)*A
elif Y>X:
    ans2+=(Y-X)*B
print(min(ans1,ans2,ans3))

Measured memory_bytes: 3064
c = [list(map(int,input().split())) for _ in range(3)]
if (c[2][0]-c[1][0])==(c[2][1]-c[1][1])==(c[2][2]-c[1][2]) and (c[1][0]-c[0][0])==(c[1][1]-c[0][1])==(c[1][2]-c[0][2]) and (c[2][2]-c[2][1])==(c[1][2]-c[1][1])==(c[0][2]-c[0][1]) and (c[2][1]-c[2][0])==(c[1][1]-c[1][0])==(c[0][1]-c[0][0]):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9212
character(10**5) S
integer,allocatable,dimension(:,:)::DP
integer keta(6)
integer SL
read*,S
SL=len_trim(S)
allocate(DP(0:12,SL))
DP=0
keta=[1,10,9,12,3,4]

if(S(SL:SL)=="?")then
  do i=0,9
    DP(i,1)=1
  end do
else 
  DP(ichar(S(SL:SL))-48,1)=1
end if

do i=2,SL
  if(S(SL-i+1:SL-i+1)=="?")then
  do j=0,9
    do k=0,12
      jj=mod(j*Keta( mod(i-1,6) +1 )+k,13)
      DP(jj,i)=mod(DP(jj,i)+DP(k,i-1),10**9+7)
    end do
  end do
  else
    jj=(ichar(S(SL-i+1:SL-i+1))-48)*Keta( mod(i-1,6) +1 )
    do j=0,12
      DP(mod(jj+j,13),i)=DP(j,i-1)
    end do
  endif
end do

print"(i0)",DP(5,SL)
end

Measured memory_bytes: 5668
#!/usr/bin/env python3
import sys
import math
INF = float("inf")


def solve(A: int, B: int):
    h = 100
    w = 99
    print(h, w)

    grid = [["."]*w for row in range(h)]

    for i in range(h//2, h):
        grid[i] = ["#"]*w

    def ij_k(k):
        row = (w-1)//2
        i = (k//row)*2+1
        j = (k % row)*2+1
        return i, j

    for k in range(B-1):
        i, j = ij_k(k)
        grid[i][j] = "#"

    for k in range(A-1):
        i, j = ij_k(k)
        grid[i+h//2][j] = "."

    for i in range(h):
        r = "".join(grid[i])
        print(r)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3188
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<tuple>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;

int m;ll n,s;

void solve(){
    cin >> m;
    rep(i,m){
        ll c,d;
        cin >> d >> c;
        n+=c;
        s+=d*c;
    }
    cout << n-1+(s-1)/9 << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(50);
    solve();
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for(int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

const ll MOD = 1000000007;

int main() {
    int n;
    cin >> n;
    ll A, B;
    cin >> A >> B;
    if(A > B)swap(A, B);
    ll s[n];
    rep(i,n)cin >> s[i];
    srep(i,2,n){
        if(s[i] < s[i-2] + A){
            cout << 0 << endl;
            return 0;
        }
    }
    vector<vector<ll>> v;
    vector<ll> vv;
    rep(i,n){
        if(vv.size() == 0){
            vv.push_back(s[i]);
        }else{
            if(s[i-1] + B <= s[i]){
                v.push_back(vv);
                vv.clear();
                vv.push_back(s[i]);
            }else{
                vv.push_back(s[i]);
            }
        }
    }
    v.push_back(vv);

    ll ans = 1;

    rep(_,v.size()){
        vv = v[_];
        int m = vv.size();
        ll dp[m][2];
        ll sum = 0;
        int now = 0;
        int flag = 1;
        int del = 0;
        rep(i,m){
            dp[i][0] = 0;
            dp[i][1] = flag;
            if(i >= 1 && vv[i-1] + A > vv[i])flag = 0;
            if(i == 0){
                dp[i][0] = 1;
                dp[i][1] = 1;
            }else{
                dp[i][0] = dp[i-1][1];
                if(vv[i-1] + A <= vv[i]) dp[i][0] += dp[i-1][0];
                dp[i][0] %= MOD;
                while(vv[now] + B <= vv[i]){
                    sum = (sum + dp[now][1]) % MOD;
                    now++;
                }
                if(del <= now)dp[i][1] += sum;
                dp[i][1] %= MOD;
                if(vv[i-1] + A > vv[i]){
                    while(del < i-1){
                        sum += MOD * 100 - dp[del][1];
                        sum %= MOD;
                        del++;
                    } 
                }
            }
        }
        ans *= (dp[m-1][0] + dp[m-1][1]) % MOD;
        ans %= MOD;

        // rep(i,m)cout << i << ' ' << dp[i][0] << ' ' << dp[i][1] << endl;
    }

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




Measured memory_bytes: 9524
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
N = int(input())
C = list(map(int,input().split()))
AB = [tuple(map(int,input().split())) for i in range(N-1)]

es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
cs = [[] for _ in range(N)]
for i,c in enumerate(C):
    cs[c-1].append(i)

tin = [-1]*N
tout = [-1]*N
k = 0
def dfs(v,p=-1):
    global k
    tin[v] = k
    k += 1
    for to in es[v]:
        if to==p: continue
        dfs(to,v)
    tout[v] = k
dfs(0)

class BinaryIndexedTree:
    def __init__(self,size):
        self.N = size
        self.bit = [0]*(size+1)
    def add(self,x,w): # 0-indexed
        x += 1
        while x <= self.N:
            self.bit[x] += w
            x += (x & -x)
    def _sum(self,x): # 1-indexed
        ret = 0
        while x > 0:
            ret += self.bit[x]
            x -= (x & -x)
        return ret
    def sum(self,l,r): # [l,r)
        return self._sum(r) - self._sum(l)
    def __str__(self): # for debug
        arr = [self.sum(i,i+1) for i in range(self.N)]
        return str(arr)
bit = BinaryIndexedTree(N)
for i in range(N):
    bit.add(i,1)

whole = N*(N+1)//2
anss = []
for i in range(N):
    ans = whole
    cs[i].sort(key=lambda x: -tin[x])
    history = []
    for v in cs[i]:
        cnt = 1
        for to in es[v]:
            if tin[to] < tin[v]: continue
            num = bit.sum(tin[to], tout[to])
            ans -= num*(num+1)//2
            cnt += num
        bit.add(tin[v], -cnt)
        history.append((tin[v], cnt))
    pn = bit.sum(0,N)
    ans -= pn*(pn+1)//2
    for a,b in history:
        bit.add(a,b)
    anss.append(ans)
print(*anss, sep='\n')

Measured memory_bytes: 358660
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
typedef vector<ll> vel;
typedef vector<str> ves;
#define REP(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
#define rep(i, b) REP(i, 0, b)
const ll mod = 1000000007;
const double pi = 3.14159265358979;

ll expo(ll a, ll b){
    ll ex = 1;
    rep(i, b){
        ex *= a;
    }
    return ex;
}

ll fact(ll a){
    ll fc = 1;
    REP(i, 1, a+1){
        fc *= i;
    }
    return fc;
}

int main() {
    ll r;
    cin >> r;
    if(r<1200) {
        cout << "ABC" << endl;
    }
    else if(r<2800) {
        cout << "ARC" << endl;
    }
    else {
        cout << "AGC" << endl;
    }
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <bitset>

#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define debug(x) cerr << #x << ": " << x << endl

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;

const ll MOD = 1000000007;
const long double EPS = 1e-10;
const int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    cout << min(b/a, c) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define M 1000000007
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n;
    cin>>n;
    cout<<(n-1)/2;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int main() {
  int N; cin>>N;
  vector<int> a(N);
  int ans = 0;
  for(int i = 0; i < N; i++) {
    cin>>a[i];
  }
  sort(a.begin(), a.end());
  reverse(a.begin(), a.end());
  for(int i = 0; i < N; i++) {
    if(i % 2 == 0) ans += a[i];
    else ans -= a[i];
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())
answer = 0
cooking_time_order = sorted([A, B, C, D, E], key=lambda x: 10 - (x % 10))
for _ in range(5):
    if cooking_time_order[-1] % 10 == 0:
        answer += cooking_time_order[-1]
        cooking_time_order.pop()
    else:
        break
if len(cooking_time_order) == 0:
    pass
else:
    for cooking_time in cooking_time_order[:-1]:
        answer += (cooking_time + (10 - (cooking_time % 10)))
    answer += (cooking_time_order[-1])
print(answer)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())

template <class T>
void cout_vec(const vector<T> &vec1){
  rep(i,len(vec1)){
    cout<<vec1[i]<<' ';
  }
  cout<<'\n';
}

typedef pair<ll,ll> P;

const ll mod=1e9+7;

ll gcd(ll a, ll b){
    ll r;
    while((r =a%b)){
        a = b;
        b = r;
    }
    return b;
}

bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}


//単純な素数か素数じゃないかの問題ではない。
int main(){

  int A;
  cin >> A;

  bool flag = false;

  for(int i = 9; i > 0; i--){
    if(A % i == 0){
      for (int j = i; j > 0; j--) {
        if(A == i * j){
          flag = true;
        }
      }
    }
  }

  if( flag ){
    cout << "Yes" << endl;
  }else {
    cout << "No" << endl;
  }


  return 0;

}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstdlib>
#define LL long long
#define LD long double
using namespace std;
const int NN=500000 +117;
const int MM=100000 +117;
int read(){
	int fl=1,x;char c;
	for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
	if(c=='-'){fl=-1;c=getchar();}
	for(x=0;c>='0'&&c<='9';c=getchar())
		x=(x<<3)+(x<<1)+c-'0';
	return x*fl;
}
void open(){
	freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
}
void close(){
	fclose(stdin);
	fclose(stdout);
}


int m,n;
LL fact[NN]={};
LL rev[NN]={};
const int mod=998244353;
LL ksm(LL a,LL b){
	LL ret=1;
	for(;b;b>>=1,a=a*a%mod){
		if(b&1)ret=ret*a%mod;
	}
	return ret;
}
void prefact(int n){
	fact[0]=1;
	for(int i=1;i<=n;++i)fact[i]=fact[i-1]*i%mod;
	rev[n]=ksm(fact[n],mod-2);
	for(int i=n;i>=1;--i)rev[i-1]=rev[i]*i%mod;
}
LL comp(int n,int m){
	return fact[n]*rev[m]%mod*rev[n-m]%mod;
}
LL nocross(int a,int b,int s){
	if(s>b)return comp(a+b,b);
	else return (comp(a+b,b)-comp(a+b,b-s)+mod)%mod;
}
int main(){
	//open();
	n=read();
	int k=read();
	prefact(k+10);
	LL ans=0;
	for(int i=max((k+1)/2,n);i<=k;++i){
		int s=i-n+1;
		if(i==k-i){
			ans+=nocross(i,k-i-1,s);
		}
		else ans+=nocross(i,k-i,s);
	}
	ans%=mod;
	printf("%lld\n",ans);
	close();
	return 0;
}

Measured memory_bytes: 8064
s = input()
ans = 0

a_stack = 0
i = 0
while i < len(s):
    v = s[i]
    if v == 'A':
        a_stack += 1
        pass
    elif v == 'B' and i < len(s)-1 and s[i+1] == 'C':
        ans += a_stack
        i += 1
    else:
        a_stack = 0
    i+=1
print(ans)


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

int main(){
  string S;
  cin >> S;
  
  int ans;
  int N = S.length();
  int count = 0;
  
  repeat(i,N-1){
    if(S[i]==S[i+1]){
      count++; 
      i+=2;
    }
  }
 
  ans = N - count;
    
  cout << ans << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main(){
    int su[52], n, a = 0, x = 1, i = 0, kazu;
    char e[52],moyo;
    char  gara[5] = "SHCD"; 
    
    while(i<52){
        for(int j=0;j<13;j++){
            e[i] = gara[a];
            su[i] = j+1;
            i++;
        }
        a++;
    }
    cin >> n;
    for(int j=0;j<n;j++){
        cin >> moyo >> kazu;
        for(int k=0;k<52;k++){
            if(e[k] == moyo&&su[k] == kazu){
                su[k] = 0;
            }
        }
    }
    for(int j=0;j<52;j++){
        if(su[j] != 0){
            cout << e[j] << " " << su[j] << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3108
#include<iostream>
#include<vector>
#include<string>
#include<array>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<numeric>
#include<iomanip>
#include<utility>
#include<cstdlib>
#include<typeinfo>


using namespace std;
#define INF 1000000005
int main()
{
int n,m;
std::cin >> n >> m;
std::vector<pair<int,int>> q;
for(int i = 0; i < m; i++){
    int a,b;
    std::cin >> a >> b;
    pair<int,int> temp = make_pair(a,b);
    q.push_back(temp);
}
std::sort(q.begin(),q.end());
std::vector<std::vector<int>> out;
int sum = 1;
std::vector<int> first = {q[0].first,q[0].second};
out.push_back(first);
for(int i = 1; i < m; i++){
    int tempa = q[i].first;
    int tempb = q[i].second;
    int flag = 0;
    for(int j = 0; j < sum; j++){
        if(out[j][0] < tempb && out[j][1] > tempa){
            flag = 1;
            if(out[j][0] < tempa){
                out[j][0] = tempa;
            }
            if(out[j][1] > tempb){
                out[j][1] = tempb;
            }
        }
        if(flag == 1){
            break;
        } 
    }
    if(flag == 0){
        sum++;
        std::vector<int> temp = {tempa,tempb};
        out.push_back(temp);
    }
}
std::cout << sum << std::endl;
return 0;
}

Measured memory_bytes: 1400
fun main(args: Array<String>) {

    val (N, W) = readLine()!!.split(" ").map(String::toInt)
    val WV = Array(N) { readLine()!!.split(" ").map(String::toLong) }
    val w = WV.map { it[0].toInt() }
    val v = WV.map { it[1] }

    val dp = Array(N) { LongArray(W + 1) }


    for (j in w[0].toInt()..W) {
        dp[0][j] = v[0]
    }
    for (i in 1 until N) {
        for (j in 0..W) {
            dp[i][j] = when {
                w[i] > j -> {
                    dp[i - 1][j]
                }
                w[i] > W -> {
                    dp[i - 1][j]
                }
                else -> {
                    Math.max(
                        // 現状維持
                        dp[i - 1][j],
                        // 入れる
                        dp[i - 1][j - w[i]] + v[i]
                    )
                }
            }
        }
    }

    println(dp.last().last())
}


Measured memory_bytes: 123180
K, N = map(int, input().split(' '))
A = tuple(map(int, input().split(' ')))

d_max = A[0] + K - A[-1]
for a1, a2 in zip(A, A[1:]):
    d_max = max(d_max, a2 - a1)

print(K - d_max)


Measured memory_bytes: 26676
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Set;
import java.util.TreeMap;

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO 自動生成されたメソッド・スタブ
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String W = in.readLine();
		int N = Integer.parseInt(W);


		TreeMap<Long ,ArrayList<Long>> map = new TreeMap<Long ,ArrayList<Long>>();
		ArrayList<Long> list ;
		//データを締め切り毎にリスト化
		for(int i=0;i<N;i++){
			W = in.readLine();
			long A =  Long.parseLong(W.split(" ")[0]);
			long B =  Long.parseLong(W.split(" ")[1]);

			if(map.containsKey(B)){
				list = map.get(B);
				boolean flg = true;
				for(int x=0;x<list.size();x++){
					if(A < list.get(x)){
						list.add(A);
						flg = false;;
						break;
					}
				}
				if(flg){
					list.add(A);
				}
			}else{
				list = new ArrayList<Long>();
				list.add(A);
				map.put(B, list);
			}
		}

		long time =0;
		String ans = "Yes";
		Set<Long> st = map.keySet();
		for(long key : st){
			list = map.get(key);
			for(long val:list){
				time += val;
				if(time <= key){
					continue;
				}else{
					ans = "No";
					break;
				}
			}
		}


		System.out.println(ans);
	}


}


Measured memory_bytes: 130524
import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, M = map(int, readline().split())
A = list(map(int, readline().split()))
sum_A = sum(A)

if sum_A > N:
    print(-1)
else:
    print(N - sum_A)


Measured memory_bytes: 9912
#include <stdio.h>

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

    if (a > b){
    	printf("a > b\n");
    }else if(a < b){
    	printf("a < b\n");
    }else{
    	printf("a == b\n");
    }

	return 0;
}

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

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

    int* city = new int [n+1]();
    for(int i=0;i<m;i++)
    {
        int a ,b;
        cin>>a>>b;
        city[a]++;
        city[b]++;
    }
    for(int i=1;i<=n;i++)
    {
        cout<<city[i]<<"\n";
    }
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
typedef long long ll;
const int INF = 1<<30;

int main(){
  int n, d, x;cin>>n>>d>>x;
  for(int i=0;i<n;i++){
    int a;cin>>a;
    x+=(d-1)/a+1;
  }
  cout << x << endl;
}


Measured memory_bytes: 256
from collections import Counter
n = int(input())
x = list(map(int, input().split()))
a = []
b = []
for i in range(n):
    a.append(i+1+x[i])
    b.append(i+1-x[i])
ans = 0
a, b = Counter(a), Counter(b)
for i in range(min(a), max(b)+1):
    ans += a[i]*b[i]
print(ans)

Measured memory_bytes: 63232
n = int(input())
Tall_list = [0] * 6
for i in range(n) :
    tall = float(input())
    if tall < 165 :
        Tall_list[0] += 1
    elif tall < 170 :
        Tall_list[1] += 1
    elif tall < 175 :
        Tall_list[2] += 1
    elif tall < 180 :
        Tall_list[3] += 1
    elif tall < 185 :
        Tall_list[4] += 1
    else :
        Tall_list[5] += 1

for i in range(6) :
    print(i+1, ":", sep = "", end = "")
    for j in range(Tall_list[i]) :
        print("*", end = "")
    print()


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

struct Point {double x, y;};

void koch(int n, Point a, Point b) {
    if (n == 0) return;
    Point s, t, u;
    double th = M_PI * 60.0 / 180.0;
    s.x = (2.0 * a.x + 1.0 * b.x) / 3.0;
    s.y = (2.0 * a.y + 1.0 * b.y) / 3.0;
    t.x = (1.0 * a.x + 2.0 * b.x) / 3.0;
    t.y = (1.0 * a.y + 2.0 * b.y) / 3.0;
    u.x = (t.x - s.x) * cos(th) - (t.y - s.y) * sin(th) + s.x;
    u.y = (t.x - s.x) * sin(th) + (t.y - s.y) * cos(th) + s.y;

    koch(n-1, a, s);
    printf("%.8f %.8f\n", s.x, s.y);
    koch(n-1, s, u);
    printf("%.8f %.8f\n", u.x, u.y);
    koch(n-1, u, t);
    printf("%.8f %.8f\n", t.x, t.y);
    koch(n-1, t, b);
}

int main() {
    Point a, b;
    int n;
    cin >> n;

    a.x = 0;
    a.y = 0;
    b.x = 100;
    b.y = 0;

    printf("%.8f %.8f\n", a.x, a.y);
    koch(n, a, b);
    printf("%.8f %.8f\n", b.x, b.y);

    return 0;
}


Measured memory_bytes: 3144
import re
while 1:
    s=input()
    if s==".":break
    while "+-" in s or "-+" in s:
        s=s.replace("+-","").replace("-+","")
    while "+" in s:
        pos=s.rfind("+")
        cha=s[pos]+s[pos+1]
        if ord(s[pos+1])==90:cha_r="A"
        elif ord(s[pos+1])==63:cha_r="?"
        else:cha_r=chr(ord(s[pos+1])+1)
        s=s.replace(cha,cha_r)
    while "-" in s:
        pos=s.rfind("-")
        cha=s[pos]+s[pos+1]
        if ord(s[pos+1])==65:cha_r="Z"
        elif ord(s[pos+1])==63:cha_r="?"
        else:cha_r=chr(ord(s[pos+1])-1)
        s=s.replace(cha,cha_r)
    while "[" in s:
        match = re.search(r'\[[A-Z\?]+\]',s)
        cha=match.group(0)
        cha_r=cha[::-1][1:-1]
        s=s.replace(cha,cha_r)
    while "?" in s:
        s=s.replace("?","A")
    print(s)


Measured memory_bytes: 6508
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
priority_queue<int> q;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1,x;i<=n;i++){
        cin>>x;
        q.push(x);
    }
    while (m--){
        int x = q.top();
        q.pop();
        q.push(x/2);
    }
    ll ans=0;
    while (q.size())ans+=q.top(),q.pop();
    cout<<ans<<endl;
}

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

typedef long long ll;
typedef pair<int,int> P;
int dx[] = {-1, 1, 0,  0};
int dy[] = { 0, 0, 1, -1};
 
int main(){
  int n, c;
  cin >> n >> c;
  vector<vector<int>> d(c, vector<int>(c));
  for(int i=0; i<c; i++){
    for(int j=0; j<c; j++){
      cin >> d[i][j];
    }
  }
  vector<vector<int>> color(3, vector<int>(c, 0));
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      int a;
      cin >> a;
      a--;
      color[(i+j)%3][a]++;
    }
  }
  int ans = 1000000009;
  for(int i=0; i<c; i++){
    for(int j=0; j<c; j++){
      if(i==j) continue;
      for(int k=0; k<c; k++){
        if(i==k || j==k) continue;
        int tmp = 0;
        for(int m=0; m<c; m++){
          tmp += color[0][m]*d[m][i];
          tmp += color[1][m]*d[m][j];
          tmp += color[2][m]*d[m][k];
        }
        ans = min(tmp, ans);
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define vll vector<ll>
#define vi vector<int>
#define vpll vector<pair<ll,ll>>
#define pii pair<int,int>
#define REP(i,a) for(int (i)=0; (i)<(a); (i)++)
#define REP2(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
#define m0(x) memset(x,0,sizeof(x))
typedef long long ll;

using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

ll modpow(ll a,ll n){
  ll ans=1;
  if(n==0)return 1;
  if(n%2==0) ans=modpow(a,n/2)*modpow(a,n/2)%MOD;
  else ans = a * modpow(a, n-1) % MOD;
  return ans;
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll N;
  cin>>N;
  vll d(N);
  REP(i,N)cin>>d[i];
  sort(ALL(d));
  ll mark = d[N/2-1]; //0,1,...,(N/2)-1,
  if(d[N/2]==mark)cout<<"0";
  else{
    ll mark2 = d[N/2];
    cout<<mark2-mark;
  }
  
  return 0;
}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define MAXN 1000010
#define rep(i,n) for (int i = 0; i < (n); ++i)
const ll mod = 1e9+7;

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; }

int main() {
    ll n;
    cin >> n;
    ll a;
    for(ll i= sqrt(n); i>0; --i) {
        if (n%i==0) {
            a = i;
            break;
        }
    }

    ll b = n/a;
    ll ans = 0;
    while (b>0) {
        b /= 10;
        ++ans;
    }

    cout << ans << endl;

}



Measured memory_bytes: 256
import java.util.*;

public class Main {
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		long count = 0;
		if (k % 2 == 0) {
			long x = n / k;
			count += (x * x * x);
			long y = (n + k / 2) / k;
			count += (y * y * y);
		} else {
			long x = n / k;
			count += (x * x * x);
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 23124
N, A, B = (int(i) for i in input().split())  

diff = abs(A-B)
if diff == 0:
  print(0)
elif diff % 2 == 0:
  print(diff//2)
else:
  print(min(B-A+(A-1)*2+1, B-A+(N-B)*2+1)//2)
    

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

typedef unsigned long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;

#define INF (int)(1e9)

#define rep(i,n) for(auto i=0; i<(n); ++i)
#define REP(i,start,end) for(auto i=(start);i<=(end);++i)
#define all(n) begin(n),end(n)

#define DEBUG

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	int n,r;
	cin >> n >> r;
	int ans;
	if(n < 10)
	{
		ans = (100 * (10 - n)) + r;
	}
	else ans = r;

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
vector<long int> fas(100001,-1);
vector<long int> fbs(100001,-1);
vector<long int> fcs(100001,-1);
vector<int>a(100001);
vector<int>b(100001);
vector<int>c(100001);
long int fa(int);
long int fb(int);
long int fc(int);
long int fa(int n)
{
	if(fas[n]!=-1)
		return fas[n];
	if(n==1)
	{
		fas[1]=a[1];
		return fas[1];
	}
	fas[n]=max(fb(n-1),fc(n-1))+a[n];
	return fas[n];
}
long int fb(int n)
{
	if(fbs[n]!=-1)
		return fbs[n];
	if(n==1)
	{
		fbs[1]=b[1];
		return fbs[1];
	}
	fbs[n]=max(fc(n-1),fa(n-1))+b[n];
	return fbs[n];
}
long int fc(int n)
{
	if(fcs[n]!=-1)
		return fcs[n];
	if(n==1)
	{
		fcs[1]=c[1];
		return fcs[1];
	}
	fcs[n]=max(fa(n-1),fb(n-1))+c[n];
	return fcs[n];
}
int main()
{
	int n,i;
	cin>>n;
	long int ans;
	for(i=1;i<=n;i++)
		cin>>a[i]>>b[i]>>c[i];
	ans=max(fa(n),fb(n));//,fc(n));
	ans=max(ans,fc(n));
	cout<<ans;
}


Measured memory_bytes: 8448
#include<stdio.h>
int main(void)
{ 
    char S[5];
  
    scanf("%s",S);
   
    if(S[0]==S[1]) printf("Bad\n");
    else if(S[1]==S[2]) printf("Bad\n");
    else if(S[2]==S[3]) printf("Bad\n");
    else printf("Good\n");
  
    return 0;
}

Measured memory_bytes: 1604
N,M = map(int,input().split())
*A, = map(int,input().split())

A.sort(reverse=True)

def count(i,B):
    B = B - A[i]
    l = -1
    r = N
    while l+1<r:
        j = (l+r)//2
        if A[j] >= B:
            l = j
        else:
            r = j
    return r

l = 0
r = 10**5*3
while l+1<r:
    i = (l+r)//2
    S = 0
    for j in range(N):
        S += count(j,i)
    if S==M:
        r = i
        break
    elif S>M:
        l = i
    else:
        r = i

ans = 0
tmp = 0
SA = [0]*(N+1)
for j in range(N):
    SA[j+1] = SA[j] + A[j]
for j in range(N):
    c = count(j,r)
    ans += A[j]*c + SA[c]
    tmp += c
if M>tmp:
    n = 0
    for j in range(N):
        c = count(j,r)
        if c==N: continue
        n = max(n,A[j] + A[c])
    ans += n*(M-tmp)
print(ans)

Measured memory_bytes: 62616
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <climits>
#include <numeric>
#include <cmath>
#include <queue>
#include <sstream>
#include <string.h>
#include <bitset>

using namespace std;
typedef long long ll;

template<class Monoid> struct SegTree {
  using Func = function<Monoid(Monoid, Monoid)>;
  const Func F;
  const Monoid UNITY;
  int SIZE_R;
  vector<Monoid> dat;
  
  SegTree(int n, const Func f, const Monoid &unity): F(f), UNITY(unity) { init(n); }
  void init(int n) {
    SIZE_R = 1;
    while (SIZE_R < n) SIZE_R *= 2;
    dat.assign(SIZE_R * 2, UNITY);
  }
  
  /* set, a is 0-indexed */
  void set(int a, const Monoid &v) { dat[a + SIZE_R] = v; }
  void build() {
    for (int k = SIZE_R - 1; k > 0; --k)
      dat[k] = F(dat[k*2], dat[k*2+1]);
  }
  
  /* update a, a is 0-indexed */
  void update(int a, const Monoid &v) {
    int k = a + SIZE_R;
    dat[k] = v;
    while (k >>= 1) dat[k] = F(dat[k*2], dat[k*2+1]);
  }
  
  /* get [a, b), a and b are 0-indexed */
  Monoid get(int a, int b) {
    Monoid vleft = UNITY, vright = UNITY;
    for (int left = a + SIZE_R, right = b + SIZE_R; left < right; left >>= 1, right >>= 1) {
      if (left & 1) vleft = F(vleft, dat[left++]);
      if (right & 1) vright = F(dat[--right], vright);
    }
    return F(vleft, vright);
  }
  inline Monoid operator [] (int a) { return dat[a + SIZE_R]; }
  
  /* debug */
  void print() {
    for (int i = 0; i < SIZE_R; ++i) {
      cout << (*this)[i];
      if (i != SIZE_R-1) cout << ",";
    }
    cout << endl;
  }
};

long long GCD(long long a, long long b) {
  return b ? GCD(b, a%b) : a;
}

int main(int argc, const char * argv[]) {
  int n;
  cin >> n;

  SegTree<ll> seg(n, [](ll a, ll b) {
    return GCD(a, b);
  }, 0);
  
  vector<ll> vec(n);
  for (int i = 0; i < n; i++) {
    cin >> vec[i];
    seg.set(i, vec[i]);
  }
  seg.build();
  
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    ll left = seg.get(0, i);
    ll right = seg.get(i + 1, n);
    ans = max(ans, GCD(left, right));
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3072
n = int(input())

x = [0] * n

x = list(map(int, input().split()))

x.sort()
sum = 0
min_sum = 100 * 10000
for i in list(range(x[0], x[-1] + 1)):
    sum = 0
    for j in x:
        sum += (j - i) * (j - i)
    if sum < min_sum:
        min_sum = sum
print(min_sum)


Measured memory_bytes: 38512
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<cstdio>
#include<cstring>
#include<queue>
#include<deque>
#include<stack>
using namespace std;

const int INF=100005;

int n,mn=INF,mx=-1,ans;
int a[INF];

int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		a[x]++;
		mx=max(mx,x);
		mn=min(mn,x);
	}
	for(int i=mn;i<=mx;i++){
		if(i==mn) ans=max(ans,a[i]+a[i+1]);
		else if(i==mx) ans=max(ans,a[i]+a[i-1]);
		else ans=max(ans,a[i]+a[i+1]+a[i-1]);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define fin(ans) cout<<(ans)<<endl
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p,q)
#define pb(n) push_back(n)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define Sort(a) sort(a.begin(),a.end())
#define Rort(a) sort(a.rbegin(),a.rend())
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;}
const int P = 1000000007;
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;

bool isPrime(int x){
    int i;
    if(x < 2)return 0;
    else if(x == 2) return 1;
    if(x%2 == 0) return 0;
    for(i = 3; i*i <= x; i += 2) if(x%i == 0) return 0;
    return 1;
}

bool judge(int n){
    if(n==0||n==1||n%2==0)return false;
    bool ue=false,sita=false;
    ue=isPrime(n);
    sita=isPrime((n+1)/2);
    if(ue&&sita)return true;
    else return false;
}

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

    bool is2017[100050];
    rep(i,100050){
        is2017[i]=judge(i);
    }
    vi csum(100050,0);
    for(int i=1;i<csum.size();i++){
        csum[i]=csum[i-1]+int(is2017[i]);
    }
    int q;
    cin>>q;
    int l,r;
    rep(i,q){
        cin>>l>>r;
        cout<<csum[r]-csum[l-1]<<endl;
    }


//////////////////////////////////////////////////////
return 0;}

Measured memory_bytes: 1152