akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
int n;
int a[200005],l,r,tail;
struct que
{
	int x,v;
}sta[200005];
void insert(int x,int v)
{
	while(sta[tail].x>x) tail--;
	if(sta[tail].x==x) sta[tail].v++;
	else sta[++tail]=(que){x,1};
	if(tail>1&&sta[tail].v==v) tail--,insert(x-1,v);
}
bool check(int v)
{
	tail=0;
	sta[++tail]=(que){0,0};
	for(int i=2;i<=n;i++) if(a[i]<=a[i-1]) insert(a[i],v);
	return !sta[1].v;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	bool flag=1;
	for(int i=2;i<=n;i++) if(a[i]<=a[i-1]) flag=0;
	if(flag)
	{
		puts("1");
		return 0;
	}
	l=2,r=n;
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	printf("%d",l);
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define endl '\n'
#define debug(X) cout << #X << " = " << X << endl

using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	#ifdef UTP
	freopen("input.txt", "r", stdin);
	#endif
	int n, x; cin >> n >> x;
	vector<int> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	sort(a.begin(), a.end());
	int ans = 0;
	for (int i = 0; i < n - 1; i++)
		if (x >= a[i]) x -= a[i], ans++;
	ans += (x == a[n - 1]);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
import collections

N,M = map(int, input().split())
G = [[] for i in range(3*N+1)]

for i in range(M):
  u,v = map(int, input().split())
  G[u].append(v+N)
  G[u+N].append(v+2*N)
  G[u+2*N].append(v)
S,T = map(int, input().split())

def bfs(s):
  que = collections.deque()
  que.append(s)
  d = [-1 for _ in range(3*N+1)]
  d[s] = 0

  while (0 < len(que)):

    p = que.popleft()
    if (T == p):
      return d[p]

    for pp in G[p]:
      if d[pp] == -1:
        que.append(pp)
        d[pp] = d[p]+1

  return -1

ans = bfs(S)
if (-1 == ans):
  print(-1)
else:
  print(ans//3)

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

int main()
{
    string s;
    cin >> s;
    int cnt[26] = {},flag = 0;
    for(int i = 0; i < s.length(); i++){
        if(cnt[s[i]-'a'] == 0) cnt[s[i]-'a']++;
        else flag = 1;  
    }

    cout << (flag == 0 ? "yes" : "no") << endl;
    return 0;
}

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

using namespace std;

int main()
{int N;cin >> N;
 vector<long long> A(N);
 for(int i = 0; i < N; i++)
 {cin >> A[i];}
 long long sum = 0;
 for(int i = 0; i < N; i++)
 {while(A[i]%2 == 0)
 {A[i] = A[i]/2;
  sum++;}}
 
 cout << sum << endl;
 return 0;
}

Measured memory_bytes: 384
n,m,c = map(int,input().split())
listb = list(map(int,input().split()))
lista = [list(map(int,input().split())) for i in range(n)]

ans = 0
count = 0
for i in range(n):
    for j in range(m):
        ans += listb[j]*lista[i][j]
    ans += c
    if ans > 0:
        count += 1
    ans = 0

print(count)

Measured memory_bytes: 38256
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef long long ll;
const ll maxn = 1e6+100;
const ll mod = 1e9+7;
char s[maxn];
ll f[3][3];
ll san[maxn];
int main(){
    scanf("%s",s);
    san[0]=1;
    for(int i=1;i<=100000;i++)
        san[i] = san[i-1]*3%mod;
    memset(f,0,sizeof(f));
    ll ans = 0;
    int n = (int)strlen(s);
    int cnt = 0;
    for(int i=0;i<n;i++)
        if(s[i]=='?') cnt++;
    for(int i=0;i<n;i++){
        if(s[i] == 'A'){
            f[1][0]++;
        }
        else if(s[i]=='B'){
            f[2][0] += f[1][0]; f[2][0]%=mod;
            f[2][1] += f[1][1]; f[2][1]%=mod;
        }
        else if(s[i]=='C'){
            if(cnt>=2)
                ans += f[2][0]*san[cnt]%mod+f[2][1]*san[cnt-1]%mod+f[2][2]*san[cnt-2]%mod,ans%=mod;
            else if(cnt==1)
                ans += f[2][0]+f[2][1]*san[cnt-1]%mod,ans%=mod;
            else ans  += f[2][0],ans%=mod;
        }
        else{
            if(cnt>=3)
                ans += f[2][0]*san[cnt-1]+f[2][1]*san[cnt-2]%mod+f[2][2]*san[cnt-3]%mod,ans%=mod;
            else if(cnt==2)
                ans += f[2][0]*san[cnt-1]+f[2][1]*san[cnt-2]%mod,ans%=mod;
            else if(cnt==1)
                ans += f[2][0]+f[2][1]*san[cnt-1]%mod,ans%=mod;
            f[2][1]+=f[1][0];f[2][1]%=mod;
            f[2][2]+=f[1][1];f[2][2]%=mod;
            f[1][1]++;f[1][1]%=mod;
        }
      //  printf("%lld %lld %lld %lld %lld %lld\n",f[1][0],f[1][1],f[2][0],f[2][1],f[2][2],ans);
    }
    printf("%lld",ans);
}

Measured memory_bytes: 3072
//
//  header_useful.h
//  c++_acm
//
//  Created by 李弘辰 on 2019/7/23.
//  Copyright © 2019 李弘辰. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <vector>
#include <list>
#include <set>
#include <utility> // pair
#include <map>
#include <iostream>
#include <sstream>
#include <algorithm> // sort
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <bitset>

using namespace std;

#define ll long long
#define uchar unsigned char
#define ushort unsigned short
#define uint unsigned int
#define ulong unsigned long
#define ull unsigned long long

#define INT_INF 0x7fffffff

#define pi acos(-1)

#define mx(a,b) (a) > (b) ? (a) : (b)
#define mn(a,b) (a) < (b) ? (a) : (b)
#define mem(a,b) memset(a,b,sizeof(a))
#define fre(a) freopen(a,"r",stdin)

#define cio ios::sync_with_stdio(false); // Do not use it with "scanf" and other c input!

#define itn int
#define nit int
#define inr int
#define mian main
#define ednl endl
#define fro for
#define fir for
#define reutrn return
#define retunr return
#define reutnr return


/* header_useful_h */


int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    int s[110] = {0};
    int d;
    int in;
    for (int i = 0;i < k;i ++) {
        scanf("%d",&d);
        for (int j = 0;j < d;j ++) {
            scanf("%d",&in);
            s[in] ++;
        }
    }
    int c = 0;
    for (int i = 1;i <= n;i ++) if (s[i] == 0) c ++;
    printf("%d\n",c);
    return 0;
}


Measured memory_bytes: 3224
#pragma GCC optimze("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define pp pair<ll,ll>
#define ppp pair<ll,pp >
#define trace(...) cout<<"Line:"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cout<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma=strchr(names+1,',');
	cout.write(names,comma-names)<<" : "<<arg1<<" | ";
	__f(comma+1,args...);
}
typedef tree<pp,null_type,less<pp>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define ld long double
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rep(i,a,b) for(ll i=a;i<b;i+=1)
#define sz(v) (ll)(v.size())
#define hell (ll)1000000007
#define slld(x) scanf("%lld",&x)
ll t=1, tt;
const ll inf=1e18, N=100005;
vector<ll> adj[N];
inline ll mult(ll x,ll y){x%=hell;y%=hell;return (1LL*x*y)%hell;}
inline ll add(ll x,ll y){x+=y;return x%hell;}
inline ll powMod(ll base,ll expo){
	if(base==0)return 0;
	ll ans=1;
	while(expo){
		if(expo&1)ans=mult(ans,base);
		base=mult(base,base); 
		expo>>=1;
	}
	return ans;
}
ll n,d,dp[2][105][10005];
string s;
ll go(ll f,ll cur,ll pos){
	if(pos>=n)return cur%d==0;
	if(dp[f][cur][pos]!=-1)return dp[f][cur][pos];
	dp[f][cur][pos]=0;
	ll newf,maxi,curD;
	if(f)maxi=9;
	else
		maxi=s[pos]-'0';
	//st=0;
	//if(pos==n-1 and f==0)st=1;
	for(curD=0;curD<=maxi;curD++){
		if(f)newf=1;
		else
			newf=(curD<maxi);
		dp[f][cur][pos]=add(dp[f][cur][pos],go(newf,(cur+curD)%d,pos+1));
	}
	return dp[f][cur][pos];
}
void solve(){
	cin>>s>>d;
	n=sz(s);
	memset(dp,-1,sizeof dp);
	ll ans=go(0,0,0);
	ans=add(ans,hell-1);
	cout<<ans;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   	//cin>>t;
   	tt=t;
    while(t--){
        solve();
        if(t)cout<<"\n";
    }
    return 0 ;
}


Measured memory_bytes: 19712
#include<iostream>
#include<vector>
#include<algorithm>
#include<iterator>
#include<string>
#include<queue>
#include<set>
#include<stack>
#include<map>

using namespace std;

int solve(int n){
    int ret=0;
    while(n>=1){
        ret+=(n%10);
        n/=10;
    }
    return ret;
}

int main(){
    int N;
    cin>>N;
    int ans=1e5;
    for(int i=1;i<N;i++){
        int tmp=solve(i)+solve(N-i);
        ans=min(ans,tmp);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);

        long m = sc.nextLong();
        long n = sc.nextLong();

        long ans = 1;

        while (n > 0) {
            if ((n & 1) != 0) {
                ans *= m;
                ans %= 1000000007;
            }
            m *= m;
            m %= 1000000007;
            n >>= 1;
        }

        System.out.println(ans);
    }
}



Measured memory_bytes: 26400
#include<stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 1000

int top;
int S[MAX];

int initialize(){
       return top=0;
       }

int isempty(){
       return top==0;
       }

int isfull(){
       return top>=MAX-1;
       }

void push(int n){
       if (isfull()){printf("overflow");}

       top++;
       S[top]=n;
       }

int pop(){
       if (isempty()){printf("unerflow\n");}

       top--;
       return S[top+1];
       }

int main(){
       int i,j,x,y;
       char op[MAX];
       top=0;
       while(scanf("%s",&op) != EOF){
                   if(op[0]=='+'){
                               x=pop();
                               y=pop();
                               push(y+x);
                               }
                   else if(op[0]=='-'){
                               x=pop();
                               y=pop();
                               push(y-x);
                               }
                   else if(op[0]=='*'){
                               x=pop();
                               y=pop();
                               push(y*x);
                               }
                   else {push(atoi(op));}
                   }
          printf("%d\n",pop());
          return 0;
          }




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



void print(vector<int> v){
	
	for(int i=0;i<v.size();i++){
		cout<<v[i];
	}
	//cout<<endl;
}
int jud(int x){
	
	if(x%2==0)return x/2;
	else return (3*x)+1;
}
int X;
int m[10000001]={0};
string S;
long long minS=100000000000;
void solve(){
	cin>>S;
	for(int i=0;i<(S.size()-2);i++){
		//cout<<i<<endl;
		string S3=S.substr(i,3);
		//cout<<S3<<endl;
		long long iS=atoi(S3.c_str());
		long long diffS=abs(753-iS);
		minS=min(minS,diffS);
	}
	cout<<minS<<endl;


}


int main(){

    solve();
    return 0;
}




Measured memory_bytes: 256
n, m, q = 0, 0, 0
Q = []

def main():
    global n, m, q
    n, m, q = map(int, input().split())
    for _ in range(q):
        a, b, c, d = map(int, input().split())
        a, b = a - 1, b - 1
        Q.append([a, b, c, d])
    ans = solve()
    print(ans)

def solve():
    ans = 0
    for i in range(1, m + 1):
        ans = max(ans, dfs([i], 0))
    return ans

def dfs(A, ans):
    #print('dfs({}, {}, {})'.format(A, n, m))
    if len(A) == n:
        tmp = sum([Q[i][3] for i in range(q) if A[Q[i][1]] - A[Q[i][0]] == Q[i][2]])
        #print('A:{} score:{}'.format(A, tmp))

        return max(ans, tmp)

    A.append(A[-1])
    while A[-1] <= m:
        ans = max(ans, dfs(A, ans))
        A[-1] += 1
    A.pop()
    
    return ans

if __name__ == '__main__':
    main()

Measured memory_bytes: 9248
N,M=map(int,input().split())

div=10**9+7
n=1
m=1
diff=abs(N-M)
for i in range(1,N+1):
    n*=i
    n%=div
for i in range(1,M+1):
    m*=i
    m%=div

if diff>1:
    ans=0
elif diff==0:
    ans=(2*n*m)%div
elif diff==1:
    ans=(n*m)%div
print(ans)

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

#define REP(i, a, b) for(int i = (a); i <= (b); i++)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define debug(x) cerr << #x << " = " << x << endl;
#define SET(c, v) memset(c, v, sizeof c)
#define pi 3.14159265358979323846264338
#define all(S) (S).begin(), (S).end()
#define INF 0x3f3f3f3f
#define mod 1000000007
#define pf push_front
#define pb push_back
#define mk make_pair
#define S second
#define F first
#define MAX 100005

typedef long long ll;
typedef pair<int, int> ii;
typedef unsigned long long int ull;
vector<int> adj[MAX];
int pd[MAX];

int solve1(int u) {
	if(pd[u] != -1) return pd[u];
	if(adj[u].size() == 0) pd[u] = 0;

	
	int tam = adj[u].size();
	for(int i = 0; i < tam; i++) {
		int v = adj[u][i];
		pd[u] = max(pd[u], solve1(v) + 1);
	}
	
	return pd[u];
}


int main() {
	int n, m;
	
	scanf("%i %i", &n, &m);
	rep(i, 0, m) {
		int a, b;
		scanf("%i %i", &a, &b);
		adj[a].pb(b);
	}	
	
	int ans = -INF;
	memset(pd, -1, sizeof(pd));
	for(int i = 1; i <= n; i++) {
		ans = max(ans, solve1(i));
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 8192
#include <bits/stdc++.h>
using namespace std;
int main() 
{  
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(false); 
        cin.tie(NULL);
    int N,A,B;
    cin>>N>>A>>B;
    cout<<min(N*A,B);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N;
    cin>>N;
    map<int,int> m;
    for(int i=0;i<N;i++) {
        int a;
        cin >> a;
        m[a]++;
    }
    int ans=0;
    for(int i=0;i<100000;i++) {
        ans=max(ans,m[i]+m[i-1]+m[i+1]);
    }
    cout<<ans<<endl;
}

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

using lint = long long;

constexpr long double eps = 1e-4;

template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
	typedef Point P;
	T x, y;
	explicit Point(T x=0, T y=0) : x(x), y(y) {}
	bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
	bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
	P operator+(P p) const { return P(x+p.x, y+p.y); }
	P operator-(P p) const { return P(x-p.x, y-p.y); }
	P operator*(T d) const { return P(x*d, y*d); }
	P operator/(T d) const { return P(x/d, y/d); }
	T dot(P p) const { return x*p.x + y*p.y; }
	T cross(P p) const { return x*p.y - y*p.x; }
	T cross(P a, P b) const { return (a-*this).cross(b-*this); }
	T dist2() const { return x*x + y*y; }
	double dist() const { return sqrt((double)dist2()); }
	// angle to x-axis in interval [-pi, pi]
	double angle() const { return atan2(y, x); }
	P unit() const { return *this/dist(); } // makes dist()=1
	P perp() const { return P(-y, x); } // rotates +90 degrees
	P normal() const { return perp().unit(); }
	// returns point rotated 'a' radians ccw around the origin
	P rotate(double a) const {
		return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
};

using P = Point<double>;
vector<P> points;

double dist(double x, double y) {
	double furthest = 0.0;
	for (int i = 0; i < points.size(); ++i) {
		double d = (x - points[i].x) * (x - points[i].x) 
		+ (y - points[i].y) * (y - points[i].y);
		furthest = max(furthest, sqrt(d));
	}
	return furthest;
}

double ts(double x) {
	double left = -1010, right = 1010;
	for (int i = 0; i <= 100; ++i) {
		double lmid = (2 * left + right)/3.0;
		double rmid = (left + 2 * right)/3.0;
		if (dist(x, lmid) > dist(x, rmid)) left = lmid;
		else right = rmid;
	}
	return dist(x, left);
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    points.resize(n);
    for (int i = 0; i < n; ++i) cin >> points[i].x >> points[i].y;
    double left = -1010, right = 1010;
	for (int i = 0; i <= 100; ++i) {
		double lmid = (2 * left + right)/3.0;
		double rmid = (left + 2 * right)/3.0;
		if (ts(lmid) > ts(rmid)) left = lmid;
		else right = rmid;
	}
	cout << setprecision(10) << fixed << ts(left) << '\n';
}

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

#define INF (INT64_MAX)
#define MOD (1000000000+7)
#define MAX 10

int main() {
	long long K, A, B;

	cin >> K >> A >> B;

	long long ans = K + 1;
	K -= A - 1;
	if( K > 0 ) {
		long long ans1 = A;
		ans1 += K / 2 * ( B - A );
		if( K % 2 ) {
			ans1++;
		}
		ans = max( ans, ans1 );
	}

	cout << ans << endl;

	return 0;
}


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

int data[10000];
int init(void){ memset(data, -1, sizeof(data)); }
int root(int x){ return data[x] < 0 ? x : (data[x] = root(data[x])); }
int size(int x){ return -data[root(x)]; }
int find(int x, int y){ return root(x) == root(y); }
int merge(int x, int y){
	x = root(x);
	y = root(y);
	if (x != y){
		if (data[y] < data[x]) x ^= y ^= x ^= y;
		data[x] += data[y];
		data[y] = x;
	}
	return x != y;
}

typedef struct { int from, to; int v; } Edge;
int cmp_edge(Edge *a, Edge *b){ return a->v - b->v; }
Edge V[10000];

int main(void)
{
	int n;

	while (scanf("%d", &n), n){
		int m, i;
		int minv;
		int count;

		init();

		scanf("%d", &m);
		for (i = 0; i < m; i++){
			int from, to, v;
			scanf("%d,%d,%d", &from, &to, &v);
			V[i] = (Edge){from, to, v / 100 - 1};
		}
		
		qsort(V, m, sizeof(Edge), cmp_edge);

		minv = count = 0;
		for (i = 0; i < m; i++){
			if (count >= n) break;
			if (!find(V[i].from, V[i].to)){
				if (merge(V[i].from, V[i].to)) minv += V[i].v, count++;
			}
		}
		printf("%d\n", minv);
	}
	return (0);
}

Measured memory_bytes: 808
/*pata hai na?*/

//CF,CC,AtC,SPOJ: hp1999
//HE: hemant269
//HR: hemant2132

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

#define     int          long long int
#define     ld           long double
#define     fast()       ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     all(x)       x.begin(),x.end()
#define     mem(a,b)     memset(a,b,sizeof(a))
#define     gcd(a,b)     (__gcd((a),(b)))
#define     lcm(a,b)     (((a)*(b))/gcd((a),(b)))
#define     pb           push_back
#define     ins          insert
#define     pii          pair<int,int>
#define     F            first
#define     S            second
#define     makep        make_pair
#define     maket        make_tuple
#define     show(x)      for(auto c:x)cout<<c<<" ";cout<<"\n";
#define     show2(x)     for(auto c:x)cout<<c.F<<" "<<c.S<<"\n";

const ld pi=acos(-1);
const int inf=1e18,M=1e9+7;
const int N=1e5+10;

vector<int> v[N],vis(N,0),cmp(N,0),sz(N,0),ans(N,0);

int comp=0,cur;

void dfs(int x)
{
    vis[x]=1;
    cmp[x]=comp;
    ++cur;
    for(auto c:v[x])
    {
        if(!vis[c])
            dfs(c);
    }
}

void solve()
{
    int n,m,k;
    cin>>n>>m>>k;

    int a,b;
    for(int i=0;i<m;++i)
    {
        cin>>a>>b;
        v[a].pb(b);
        v[b].pb(a);
    }

    for(int i=1;i<=n;++i)
    {
        if(!vis[i])
        {
            cur=0;
            ++comp;
            dfs(i);
            sz[comp]=cur;
        }
    }

    for(int i=0;i<k;++i)
    {
        cin>>a>>b;

        if(cmp[a]==cmp[b])
        {
            --ans[a];
            --ans[b];
        }
    }

    for(int i=1;i<=n;++i)
    {
        ans[i]+=sz[cmp[i]]-1ll-v[i].size();
        cout<<ans[i]<<" ";
    }
}

int32_t main()
{
    fast();

    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
        //cout<<"\n";
    }

    return 0;
}



Measured memory_bytes: 10624
import math
N, D = map(int, input().split())
xd = [list(map(int, input().split())) for _ in range(N)]
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        t = 0
        for k in range(D):
            t += pow(xd[i][k]-xd[j][k], 2)
        t = math.sqrt(t)
        if t == float(int(t)):
            ans += 1
print(ans)


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

#define FAST_INP  ios_base::sync_with_stdio(false);cin.tie(NULL)
int main()  
{ 
    FAST_INP;
    int n;
    long long a,ans=1,m=(long long)1e18; 
    cin >> n;
    bool f=false;
    for(int i=0;i<n;i++){
    	cin >> a;
    	if(a==0){
    		ans=0;
    		f=false;
			break;
		}	
    	if(!f){
    		if(m/ans<a) {
	    		f=true;
			}
	    	ans*=a;
		}
	}
	if(f) ans=-1;
	
	cout << ans << endl;
    return 0;
} 

Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define repr(i, n) for(int i = n;i >= 0;i--)
#define for1(i, m, n) for(int i = m;i < n;i++)
#define ll long long
#define endl '\n'
using namespace std;


int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
    int n, a[100000];
    cin >> n;
    rep(i, n) {
        cin >> a[i];
    }

    int cnt = 0;
    rep(i, n) {
        if (i == a[a[i] - 1] - 1) cnt++;
    }
    cout << cnt / 2 << endl;
	return 0;
}

Measured memory_bytes: 640
#include<iostream>
using namespace std;
int matrix[4][105],maxx;
int main() {
	int n;
	cin>>n;
	for (int i=0;i<2;++i) 
		for (int j=1;j<=n;++j) {
			cin>>matrix[i][j];
			if (!i) matrix[3][j]=matrix[0][j]+matrix[3][j-1];
		}
	for (int j=n;j>=1;--j) matrix[2][j]=matrix[1][j]+matrix[2][j+1];
	for (int j=1;j<=n;++j) maxx=max(maxx,matrix[2][j]+matrix[3][j]);
	cout<<maxx<<endl;
	return 0;
}

Measured memory_bytes: 256
//by Himanshu Shukla
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll long long
#define v32 vector<int>
#define v64 vector<ll>
#define s32 set<int>
#define s64 set<ll>
#define graph vector<s32>
#define p32 pair<int, int>
#define p64 pair<ll, ll>
#define fi first
#define se second
#define ln '\n'
#define debug(x) cout << (#x) << ": " << (x) << ln
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline ll add(ll a, ll b, ll m) { return (((a % m + b % m) % m + m) % m); }
inline ll mul(ll a, ll b, ll m) { return (((a % m * b % m) % m + m) % m); }
const double EPS = 1e-6;
const ll MOD = 1e9 + 7;
template <typename T, typename U>
ostream &operator<<(ostream &out, const pair<T, U> &p)
{
	out << '[' << p.fi << ", " << p.se << ']';
	return out;
}
template <template <typename, typename...> class ContainerType, typename ValueType, typename... Args>
void print_container(const ContainerType<ValueType, Args...> &c)
{
	cout << "{ ";
	for (const auto &v : c)
		cout << v << ' ';
	cout << '}' << ln;
}

int main()
{
	FASTIO;
	string s, t;
	cin >> s;
	cin >> t;
	int ans = 0;
	for (int i = 0; i < 3; i++)
		if (s[i] == t[i])
			ans++;
	cout << ans << ln;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef int in;
#define int long long
using namespace std;

int solve(vector<int>arr){
	vector<int>dp;
	int n = arr.size();
	dp.resize(n);
	dp[0] = 0;
	if (n >= 2) {
		dp[1] = abs(arr[1] - arr[0]);
	}
	

	for (int i = 2; i < n; i++) {
		dp[i] = min(dp[i - 2] + abs(arr[i] - arr[i - 2]), dp[i - 1] + abs(arr[i] - arr[i - 1]));
	}

	return dp[n - 1];

}

in main() {

	// cout << "hoho";
	int n;
	cin >> n;
	vector<int>arr;
	arr.resize(n);
	vector<int>dp;
	dp.resize(n);
	for (int i = 0; i < n; i++)
		dp[i] = -1;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	cout << solve(arr);

}



Measured memory_bytes: 6380
#include <bits/stdc++.h>
#define rep(i, l, r) for(register int i = l; i < r; i++)
#define hrp(i, l, r) for(register int i = l; i <= r; i++)
#define rev(i, r, l) for(register int i = r; i >= l; i--)
#define ms(n, t) memset(n, t, sizeof(n))
#define U 10050
#define pb push_back
#define int ll
#ifndef JOEON
#define D(...)
#define R(x, l)
#define sp
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
template<typename tn> inline tn next(void);
template<typename tn> inline ostream& operator << (ostream& os, const vector<tn>& v);
int w[U];
signed main(void)
{
	#ifdef JOEON
//		freopen("C:\\Users\\Joeon\\Desktop\\IN.txt", "r", stdin);
//		freopen("C:\\Users\\Joeon\\Desktop\\OUT.txt", "w", stdout);
	#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k, sum = 0;
	cin>>n>>k;
	rep(i, 0, n) cin>>w[i];
	sort(w, w+n);
	rep(i, 0, k) sum += w[i];
	cout<<sum<<endl;
	return 0;
}
template<typename tn> inline tn next(void)
{
	tn k;
	cin>>k;
	return k;
}
template<typename tn> inline ostream& operator << (ostream& os, const vector<tn>& v)
{
	rep(i, 0, v.size()) os<<v[i]<<' ';
	return os;
}


Measured memory_bytes: 3596
#pragma comment (linker, "/STACK:256000000")
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define BUGAVOID(x) x
#define rep(...) BUGAVOID(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define sz(c) (int)(c.size())
#define all(c) c.begin(),c.end()
#define mp make_pair
#define write(x) cout<<(x)<<"\n"
using namespace std; typedef long long ll;
typedef vector<int> vi; typedef vector<ll> vll; template<class T, class U>using vp = vector<pair<T, U>>;
template<class T>using vv = vector<vector<T>>; template<class T, class U>using vvp = vv<pair<T, U>>;
template<class T>vv<T> vvec(const size_t n, const size_t m, const T v) { return vv<T>(n, vector<T>(m, v)); }
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; }
constexpr ll pow2(const int n) { return 1ll << n; }
constexpr int INF = 1 << 28; constexpr ll LINF = 1ll << 60;
constexpr int MAX = 1e5 + 5; constexpr int MOD = 1e9 + 7; constexpr double EPS = 1e-6;
constexpr int dy[4] = { 0,1,0,-1 }; constexpr int dx[4] = { 1,0,-1,0 };
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); }; }aaaa;

struct UnionFindSize {
    vector<int> parent;

    UnionFindSize() {}
    UnionFindSize(const int size) { init(size); }
    void init(const int size) {
        parent.resize(size, -1);
    }
    int operator[](const int x) {
        return parent[x];
    }
    int find(const int x) {
        return parent[x] < 0 ? x : (parent[x] = find(parent[x]));
    }
    int size(const int x) {
        return -parent[find(x)];
    }
    bool same(const int x, const int y) {
        return find(x) == find(y);
    }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        else if (size(x) > size(y)) swap(x, y);
        parent[y] += parent[x];
        parent[x] = y;
        return true;
    }
};

int N, K, L;
UnionFindSize road, line;
vp<int, int> counter;

int main() {
    cin >> N >> K >> L;
    road = UnionFindSize(N);
    line = UnionFindSize(N);
    counter.resize(N);

    rep(i, K) {
        int p, q;
        cin >> p >> q;
        p--; q--;
        road.unite(p, q);
    }
    rep(i, L) {
        int r, s;
        cin >> r >> s;
        r--; s--;
        line.unite(r, s);
    }    

    rep(i, N) {
        counter[i] = mp(road.find(i), line.find(i));
    }
    sort(all(counter));

    rep(i, N) {
        int cnt = upper_bound(all(counter), mp(road.find(i), line.find(i))) - lower_bound(all(counter), mp(road.find(i), line.find(i)));
        write(cnt);
    }
}

Measured memory_bytes: 3840
import std;

void main() {
    int n, m; scan(n, m);
    auto hs = readints;

    auto s = new bool[n];
    foreach (_; 0..m) {
        int a, b; scan(a, b);
        a--; b--;
        if (hs[a] <= hs[b]) s[a] = true;
        if (hs[a] >= hs[b]) s[b] = true;
    }
    auto ans = s.count!"!a";
    writeln(ans);
}

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;


Measured memory_bytes: 7728
import math

n=int(input())
e = [[int(i) for i in input().split()] for i in range(n)] 
c=0

for i in range(n):
    for j in range(n):
        if i!=j:
            c+=math.sqrt((e[i][0]-e[j][0])**2+(e[i][1]-e[j][1])**2)
print(c/n)



Measured memory_bytes: 3060
def cal(formula: str) -> int:
    nums = formula.split("+")
    ans = 0
    for n in nums:
        ans += int(n)
    return ans


def dfs(i: int, s: str, formula: str) -> int:
    if (i == len(s) - 1):
        return cal(formula)
    return dfs(i + 1, s, formula + s[i + 1]) + dfs(i + 1, s, formula + "+" + s[i + 1])


S = input()
print(dfs(0, S, S[0]))


Measured memory_bytes: 38640
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
n=int(input())
a_list=list(map(int,input().split()))
ans=[[0]*w for i in range(h)]
count=0
for i in range(n):
    a=a_list[i]
    p_q=count//w
    p_r=count%w
    count=a+count
    n_q=count//w
    n_r=count%w
    if p_q==n_q:
        for j in range(p_r,n_r):
            ans[p_q][j]=i+1
    else:
        for j in range(p_r,w):
            ans[p_q][j]=i+1
        for k in range(p_q+1,n_q):
            for j in range(w):
                ans[k][j]=i+1
        for j in range(n_r):
            ans[n_q][j]=i+1
for i in range(h):
    if i%2==0:
        for j in range(w):
            print(ans[i][j],end='')
            print(' ',end='')
        print('')
    else:
        for j in range(w-1,-1,-1):
            print(ans[i][j],end='')
            print(' ',end='')
        print('')
        
            


Measured memory_bytes: 51176
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <math.h>
#include <numeric>
#include <queue>
#define rep(i,s,n) for (int i=s;i<n;++i)
#define drep(i,s,n) for (int i=n;i>=s;--i)
#define all(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define print(x) cout<<(x)<<endl
using namespace std;
typedef long long ll;

int gcd(int a,int b)
{if (a%b == 0) return(b);
 else          return(gcd(b,a%b));}
int lcm(int a,int b)
{return a*b/gcd(a,b);}
void printv(vector<auto> v) {cout<<'[';rep(i,0,v.size()){cout<<v[i]<<',';}cout<<']'<<endl;}
void printvv(vector<vector<auto>> vv)
{
  cout<<'['<<endl;
  rep(q,0,vv.size()){cout<<'[';rep(p,0,vv.at(q).size())cout<<vv.at(q).at(p)<<',';cout <<']'<<endl;}
  cout<<']'<<endl;
}
void solve(); int main(){cin.tie(0);ios::sync_with_stdio(0);solve();}
int step_x[] = {-1,0,0,1};
int step_y[] = {0,-1,1,0};
//------------------------------------------------------------
int n,m,ans=0;

void solve() {
  cin>>n>>m;

  vector<vector<int>> v(m, vector<int>(2));

  rep(i,0,m) cin >> v[i][0] >> v[i][1];

  sort(all(v), [](const vector<int> &a, const vector<int> &b){return a[0]<b[0];});

  int r=0;
  rep(i,0,m)
  {
    // 橋をポトス必要がある
    if(r<=v[i][0])
    {
      ans++;
      r=v[i][1];
    }
    // 最短の変更
    else if(r>v[i][1])
    {
      r=v[i][1];
    }

  }

  print(ans);

  return;
}


Measured memory_bytes: 5888
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T
import Data.List (sort, group)

main :: IO ()
main = do
  n <- unsafeTextToInt <$> T.getLine :: IO Int
  ss <- sequence . replicate n $ T.getLine :: IO [T.Text]
  print . length . group . sort $ ss

unsafeTextToInt :: T.Text -> Int
unsafeTextToInt s = case T.signed T.decimal s of
  Right (n, _) -> n


Measured memory_bytes: 68080
//#include "pch.h"
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <utility>
#include <queue>
#include <algorithm>
#include <functional>
#include <string>
#include <bitset>

#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 INF 1000000000000000000//10^18
#define INFINT 2000000001//2*10^9+1
#define MOD 1000000007
#define MODANOTHER 998244353
#define PI acos(-1)

using namespace std;

int main(void)
{
	//変数の宣言
	int n;
	static int b[110];
	static int a[110];

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



	//データの読み込み


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

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

	//	printf("nは%dです\n", n);
	//	printf("データの読み込み終了\n");
	//実際の処理

	for(i=0;i<n;i++){
		a[i]=0;
		for(j=0;j<n-i;j++){
			if(b[j]==j+1) a[i]=b[j];
		}
		if(a[i]==0){
			printf("-1");
			return 0;
		}
		for(j=a[i]-1;j<n-i-1;j++){
			b[j]=b[j+1];
		}
	}

	for(i=n-1;i>=0;i--){
		printf("%d\n",a[i]);
	}


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

	//出力

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

	return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
#define inf 1145141919

int max(int a,int b){if(a>b){return a;}return b;}
int min(int a,int b){if(a<b){return a;}return b;}

int main(void){
    int i,op=0,cl=0,n;
    char s[128];
    scanf("%d%s",&n,s);
    for(i = 0;i < n;i++){
        if(s[i] == '('){op++;}
        else{if(op != 0){op--;}else{cl++;}}
    }
    for(i = 1;i <= cl;i++){printf("(");}
    printf("%s",s);
    for(i = 1;i <= op;i++){printf(")");}
    return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
int main(void)
{
  int m;
  int k;
  int i;
  while(1){
    scanf("%d",&m);
    if(m){
      int n[7]={0};
      for(i=0;i<m;i++){
	scanf("%d",&k);
	if(k<10)
	  n[0]++;
	if(10<=k && k<20)
	  n[1]++;
	if(20<=k && k<30)
	  n[2]++;
	if(30<=k && k<40)
	  n[3]++;
	if(40<=k && k<50)
	  n[4]++;
	if(50<=k && k<60)
	  n[5]++;
	if(60<=k)
	  n[6]++;
      }
      for(i=0;i<7;i++)
	printf("%d\n",n[i]);
    }
    else
      break;
  }

  return 0;
}

Measured memory_bytes: 600
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define bit(n,m)(((n)>>(m))&1)
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p)pom(a,p-2,p)

char s[1010][1010];
ll dp[1010][1010];
int main(){
	ll h,w;
	scanf("%lld%lld",&h,&w);
	rep(i,0,h)scanf(" %s",s[i]);
	dp[0][0]=1;
	rep(i,0,h)rep(j,0,w)if(s[i][j]=='.'){
		//右
		if(s[i][j+1]=='.')dp[i][j+1]=(dp[i][j+1]+dp[i][j])%MOD;
		//下
		if(s[i+1][j]=='.')dp[i+1][j]=(dp[i+1][j]+dp[i][j])%MOD;
	}
	printf("%lld\n",dp[h-1][w-1]);
}


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

using namespace std;
using ll = long long;

int main() {
	int n, m;
	cin >> n >> m;
	vector<ll> a(n+1), b(n+1);
	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i];
	}
	vector<ll> c(m+1), d(m+1);
	for (int i = 1; i <= m; i++) {
		cin >> c[i] >> d[i];
	}

	for (int i = 1; i <= n; i++) {
		ll ans = 1;
		ll sum = abs(a[i] - c[1]) + abs(b[i] - d[1]);
		for (int j = 1; j <= m; j++) {
			ll temp = abs(a[i] - c[j]) + abs(b[i] - d[j]);
			if (sum > temp) {
				sum = temp;
				ans = j;
			}
		}
		cout << ans << endl;
	}
	return 0;
}

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

using namespace std;
typedef long long ll;
typedef string str;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;
typedef map <str,int> mapsi;
typedef map <str,int> :: iterator mapsitr;
typedef map <int , int> mint;
typedef map <ll , ll> mll;
typedef set <int> si;
typedef set <ll> sll;
typedef si :: iterator sitr;
typedef si :: reverse_iterator rsitr;
typedef sll :: iterator sltr;
typedef sll :: reverse_iterator rsltr;
#define mset multiset

typedef mset <int> msi;
typedef mset <ll> msll;
typedef msi :: iterator msitr;
typedef msi :: reverse_iterator msritr;
typedef msll :: iterator msltr;
typedef msll :: reverse_iterator mslritr;

#define mp make_pair
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define fi first
#define se second
#define fs first.second
#define ss second.second
#define ff first.first
#define sf second.first
#define newl '\n'

char to_upper (char x){
    if( 97 <= int(x) && int(x) <= 126)return char(x-32);
    else if( 65 <= int(x) && int(x) <= 90)return x;
}
char to_lower (char x){
    if( 97 <= int(x) && int(x) <= 126)return x;
    else if( 65 <= int(x) && int(x) <= 90)return char(x+32);
}
int numerize (char x){
    if(48 <= int(x) && int(x) <= 57)return int(x-'0');
    else if( 97 <= int(x) && int(x) <= 126)return int(x-96);
    else if( 65 <= int(x) && int(x) <= 90)return int(x-64);
}
// end of Template

ll a[200000],sum,n;
vll ans;
int main(){

//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(i%2==1){sum+=a[i];}
        else{sum-=a[i];}
    }
    ans.pb(sum);

    for(int i=1;i<n;i++){
        ll temp = 2*a[i] - ans.back();
        ans.pb(temp);
    }

    for(int i=0;i<ans.size();i++){
        cout<<ans[i];
        if(i<ans.size()-1)cout<<" ";
    }

}


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <stdint.h>
#include <algorithm>
#include <vector>


using namespace std;

int main() {
	int k,x;
	cin >> k >> x;
	
	int mini = max(x - k + 1, -1000000);
	int maxi = min(x + k - 1, 1000000);
	
	for (int i = mini; i <= maxi; i++) {
		if(i != maxi) {
			cout << i << " ";
		} else cout << i << endl;
	}
	
	
	
	return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**7)

v, e = list(map(int, input().split()))

G = [[] for _ in range(v)]
for _ in range(e):
    s, t = map(int, input().split())
    G[s].append(t)
    G[t].append(s)


def solve():
    
    used = [False for _ in range(v)]
    ord = [0 for _ in range(v)]
    low = [float("inf") for _ in range(v)]
    is_articulation = [False for _ in range(v)]
    
    def dfs(v, prev, k):
        if used[v]:
            return
        used[v] = True
        k = k+1
        ord[v] = k
        low[v] = ord[v]
        cnt = 0
        for u in G[v]:
            if not used[u]:
                cnt += 1
                dfs(u, v, k)
                low[v] = min(low[v], low[u])
                if prev >= 0 and ord[v] <= low[u]:
                    is_articulation[v] = True
            elif u != prev:
                low[v] = min(low[v], ord[u])
        if prev == -1 and cnt >= 2:
            is_articulation[v] = True
        
        return k
    
    dfs(0, -1, 0)
    
    for i in range(v):
        if is_articulation[i]:
            print(i)

solve()

        
    
    







        
    
    








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

typedef long double ld;

int main(){
  int n;
  cin >> n;
  int a[n];
  rep(i,n) cin >> a[i];
  
  ld ans = 0;
  rep(i,n) ans += 1/(ld)a[i];
  ans = 1/ans;
  
  cout << setprecision(12) << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#define _USE_MATH_DEFINES
#include<math.h>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<list>
#include<map>
#include<unordered_map>
#include<set>
#include <algorithm>
#include <utility>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::set;
using std::vector;
using std::pair;
using std::make_pair;
using std::priority_queue;

typedef unsigned long long ull;
typedef long long ll;

#define Prime1 1000000007
#define Prime2 9999973

#define INF 0x7fffffffffffffff

ull i, j, k, l, m, n;
ull H, W, Q;
ull a, b, c, x, y;
ull K, L, N, M;
string str;


int main()
{
	vector<int> d;
	cin >> N;
	d.resize(N);

	for (i = 0; i < N; ++i)
	{
		cin >> d[i];
	}
	std::sort(d.begin(), d.end());

	cout << d[N / 2] - d[N / 2 - 1];

	return 0;
}


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

int N, deg[100000], cnt[100000], used[100000];
vector<int> G[100000];

int main(){
	cin >> N;
	rep(i, N-1){
		int a, b; cin >> a >> b;
		a--; b--;
		G[a].push_back(b);
		G[b].push_back(a);
		deg[a]++; deg[b]++;
	}
	rep(i, N)rep(j, G[i].size()){
		if(deg[G[i][j]] == 1) cnt[i]++;
	}
	queue<int> que;
	rep(i, N){
		if(cnt[i] > 1){ cout << "First" << endl; return 0; }
		if(deg[i] == 1) que.push(i);
	}
	int size = N;
	while(size > 2){
		int a = que.front(); que.pop();
		if(used[a] == 1) continue;
		size -= 2;
		used[a] = 1;
		int to;
		rep(i, G[a].size()){
			if(used[G[a][i]] == 0) to = G[a][i];
		}
		used[to] = 1;
		rep(i, G[to].size()){
			if(used[G[to][i]] == 0){
				deg[G[to][i]]--;
				if(deg[G[to][i]] == 1){
					rep(j, G[G[to][i]].size()){
						if(used[G[G[to][i]][j]] == 0){
							cnt[G[G[to][i]][j]]++;
							if(cnt[G[G[to][i]][j]] > 1){ cout << "First" << endl; return 0; }
						}
					}
					que.push(G[to][i]);
				}
			}
		}
	}
	if(size == 2) cout << "Second" << endl;
	else cout << "First" << endl;
	return 0;
}


Measured memory_bytes: 9088
n = gets.to_i
ss = n.times.map { gets.chomp }.sort
count = {}
ss.each do |s|
  count[s] ||= 0
  count[s] += 1
end
m = count.values.max
ss.each do |s|
  if count[s] == m
    puts s
    count[s] = 0
  end
end

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

int main() {
    int n;
    cin >> n;
    vector<int> h(n);
    rep(i, n) cin >> h[i];

    int dp[100010];
    dp[0] = 0;
    dp[1] = abs(h[1] - h[0]);

    rep(i, n - 2) {
        dp[i + 2] = min(dp[i] + abs(h[i + 2] - h[i]), dp[i + 1] + abs(h[i + 2] - h[i + 1]));
    }

    cout << dp[n - 1] << endl;
}

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

const ll mod = 1e9+7;

ll solve(ll a,ll b){
    ll ans = 1;
    rep(i,a){
        ans = ans*b%mod;
    }
    return ans;
}

int main(void){
    int n;
    cin >> n;
    
    ll ans = 0;
    if(n == 1)cout << 0 << endl;
    else {
        ans = solve(n,10)-solve(n,9)-solve(n,9)+solve(n,8);
        ans %= mod;
        cout << (ans + mod) % mod << endl;
    }
}

Measured memory_bytes: 3608
n=int(input())
l=list(map(int,input().split()))
l=[format(i,"b").zfill(61) for i in l]
ans=0
MOD=10**9+7
la=[0 for i in range(61)]
for i in l:
    for num,j in enumerate(str(i)):
        if j=="1":
            la[60-num]+=1
for num,i in enumerate(la):
    ans+=2**num*i*(n-i)
    ans%=MOD
print(ans)

Measured memory_bytes: 128144
import java.util.Scanner;

public class Main
{

    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        int W = scan.nextInt();
        int H = scan.nextInt();
        int C = scan.nextInt();
        int a = W;
        int b = H;
        int c;

        while (a % b != 0) {
            c = a;
            a = b;
            b = c % a;

        }
        System.out.println((W / b) * (H / b) * C);

    }

}



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

namespace C {
    class questionC {
        static void Main(string[] args) {
            int N = int.Parse(Console.ReadLine()); //標準入力
            string[] inputAstr = Console.ReadLine().Split(' ');//2つ以上のスペース区切り入力の取得
            int[] inputA = inputAstr.Select(s => int.Parse(s)).ToArray();
            string[] inputBstr = Console.ReadLine().Split(' ');//2つ以上のスペース区切り入力の取得
            int[] inputB = inputBstr.Select(s => int.Parse(s)).ToArray();
            int max = 0;
            max += inputA[0];
            for (int i = 0; i < N; i++) {
                max += inputB[i];
            }
            int nowCandies = max;
            for (int i = 0; i < (N - 1); i++) {
                nowCandies -= inputB[i];
                nowCandies += inputA[i + 1];
                if(nowCandies > max) {
                    max = nowCandies;
                }
            }
            // Console.Write("改行なし a = {0} b = {1} c = {2}", a, b, c)//改行なし出力
            // Console.WriteLine("改行あり a = {0} b = {1} c = {2}", a, b, c);//改行付き出力
            Console.WriteLine(max.ToString());
        }
    }
}

Measured memory_bytes: 13396
MOD = 998244353

N = int(input())
A = [int(input()) for _ in range(N)]
SUM = sum(A)

dp = [ [0] * (SUM + 1) for _ in range(N+1) ]
dp2 = [ [0] * (SUM + 1) for _ in range(N+1) ]
# red [i][r] : rまで塗った
dp[0][0] = 1
dp2[0][0] = 1
for i in range(N):
    a = A[i]
    for r in range(0, SUM-a +1):
        #pick
        dp[i+1][r+a] = ( dp[i+1][r+a] + dp[i][r] ) % MOD
        dp2[i+1][r+a] = ( dp2[i+1][r+a] + dp2[i][r] ) % MOD


    for r in range(0, SUM + 1):
        # nopick    
        # B,G に入れる 2通り考える
        dp[i+1][r] = (dp[i+1][r] +  dp[i][r] * 2 ) % MOD
        dp2[i+1][r] = (dp2[i+1][r] +  dp2[i][r]  ) % MOD

if SUM % 2 ==0:
    notans = sum(dp[N][ SUM//2 : ]) * 3 % MOD

    notans = ( notans - 3 * dp2[N][SUM//2] ) %MOD
    cand = pow(3, N, MOD)

    print(  (cand - notans + MOD) % MOD  )
else:
    notans = sum(dp[N][ SUM//2 + 1: ]) * 3 % MOD
    cand = pow(3, N, MOD)
    print(  (cand - notans + MOD) % MOD  )



Measured memory_bytes: 458520
#include <stdio.h>
#define MAX 100
#define WHITE 0
#define GRAY 1
#define BLACK 2
static const int INFTY = (1<<21);
 
int A[MAX][MAX],n,v,i;
 
int prim(){
  int u,m,sum=0;
  int d[MAX],p[MAX],color[MAX];
  
  for(i=0; i<n; i++){
    d[i]=INFTY;
    p[i]=-1;
    color[i]=WHITE;
  }
  
  d[0]=0;
    
  while(1){
    m=INFTY;
    u=-1;
    for(i=0; i<n; i++){
      if(m>d[i]&&color[i]!=BLACK){
        u=i;
        m=d[i];
      }
    }
    if(u==-1)  break;
    color[u]=BLACK;
    for(v=0; v<n; v++){
      if(color[v]!=BLACK&&A[u][v]!=INFTY){
        if(d[v]>A[u][v]){
          d[v]=A[u][v];
          p[v]=u;
          color[v]=GRAY;
        }
      }
    }
  }
  for(i=0; i<n; i++){
    if(p[i]!=-1) sum+=A[i][p[i]];
  }
  return sum;
}
 
int main(){
  int e,j;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      scanf("%d",&e);
      A[i][j]=(e==-1)?INFTY:e;
    }
  }
  printf("%d\n",prim());
  return 0;
}

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

int main(){
  int n,m,mas[1201];
  while(cin >> n >> m,n||m){
    queue <int> que;
    for(int i=0;i<n;i++) cin >> mas[i];
    for(int i=0;i<m;i++){
      int t; cin >> t; que.push(t);
    }
    int now = 0,a = 0;
    while(true){
      if(now >= n - 1) break;
      int p = que.front(); now += p; que.pop(); a++;
      now += mas[now];
    }
    cout << a << endl;
  }
}

Measured memory_bytes: 1224
#include<bits/stdc++.h>
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ms memset
#define MOD 1000000007
#define sp fixed<<setprecision
#define sz sizeof
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
bool pr[1000007];
ll fpow(ll x,ll y){x=x%MOD;ll res=1;while(y){if(y&1)res=res*x;res%=MOD;y=y>>1;x=x*x;x%=MOD;}return res;}
ll inv(ll a,ll m=MOD){ll c=m;ll y=0,x=1;if(m==1)return 0;while(a>1){ll q=a/m;ll t=m;m=a%m,a=t;t=y;y=x-q*y;x=t;}if(x<0)x+=c;return x;}
ll dp[100][100001];
ll suff[100][100001];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll n,k;
    cin>>n>>k;
    ll a[n];
    for(int i=0;i<n;i++)
    cin>>a[i];
    memset(dp,0,sizeof(dp));
    memset(suff,0,sizeof(suff));
    for(int i=0;i<=a[0];i++)
    dp[0][i]=1;
	suff[0][a[0]]=1;
    for(int i=a[0]-1;i>=0;i--)
    suff[0][i]=suff[0][i+1]+dp[0][i];
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<=k;j++)
        {
            ll x=max((ll)(0),j-a[i]);
            ll y,z;
            if(j==k)
            {
                y=0;
                z=suff[i-1][x];
            }
            else
            {
                y=suff[i-1][j+1];
                z=suff[i-1][x];
            }
            dp[i][j]=z-y;
            if(dp[i][j]<0)
            dp[i][j]+=MOD;
        }
        suff[i][k]=dp[i][k];
        for(int j=k-1;j>=0;j--)
        {
            suff[i][j]=(suff[i][j+1]%MOD+dp[i][j]%MOD)%MOD;
        }
    }
    cout<<dp[n-1][k];
}

Measured memory_bytes: 156544
while True:
    a, op, b = input().split()
    a = int(a)
    b = int(b)
    if op == '?':
        break

    if op == '+':
       print(a+b)
    elif op == '-':
       print(a-b)
    elif op == '*':
       print(a*b)
    elif op == '/':
       print(a//b)


Measured memory_bytes: 5592