akhauriyash/Code-Regression huggingface dataset:
// Created by ...Lusifer
#include<bits/stdc++.h>
using namespace std;
 
#define pb 		push_back
#define mp 		make_pair
#define prior   priority_queue
#define MOD 	1000000007
#define INF64 	(long long)1e18
#define INF 	(int)1e9
#define PI 		3.1415926535897932384626433832795 
#define ll      long long
#define ld		long double
#define ret     return
#define NUM 	1000001
const int SIZE = 2e5+4;
void fastio(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

void solveTest(){
	int n;
	cin>>n;
	int b[n],a[n];
	for(int i=0;i<n-1;i++){
		cin>>b[i];
	}
	a[0] = b[0];
	a[n-1] = b[n-2];
	for(int i=1;i<n-1;i++){
		a[i] = min(b[i],b[i-1]);
	}
	ll sum=0;
	for(int i=0;i<n;i++){
		sum+=a[i];
	}
	cout<<sum<<endl;
	return ;
}
 
int main(){
	fastio();

	int t=1;
	//cin>>t;
	while(t--){
		solveTest();
 
	}
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main(){
  char s[4];
  int i,cnt=0;
  scanf("%s",s);
  for(i=0; i<3; i++){
    if(s[i]==s[i+1]){
      cnt++;
    }
  }
  if(cnt==0){
    printf("Good\n");
  }
  else{
    printf("Bad\n");
  }
  return 0;
}


Measured memory_bytes: 128
n, l = gets().chomp.split("\s").map{|x| x.to_i}

list = []
(1..n).each do |i|
  list.push(l + i - 1)
end

min = nil
list.each do |l|
  min = l if min.nil? || l.abs < min.abs
end

puts list.sum() - min

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

int dp[100005][3];

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

    dp[0][0] = a[0];
    dp[0][1] = b[0];
    dp[0][2] = c[0];
    for(int i = 1; i < n; i++) {
        dp[i][0] = a[i] + max(dp[i-1][1], dp[i-1][2]);
        dp[i][1] = b[i] + max(dp[i-1][0], dp[i-1][2]);
        dp[i][2] = c[i] + max(dp[i-1][0], dp[i-1][1]);
    }
    cout << max(max(dp[n-1][0], dp[n-1][1]), dp[n-1][2]) <<endl;

	return 0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <bitset>
#include <sstream>
#include <cstdlib>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <climits>
using namespace std;

#define eps 1e-8
#define mod 1000000007
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fi first
#define se second

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> vvi;

#define MAXN 100010

ll foo[MAXN];

void init() {
    foo[0] = 1;
    for (int i = 1; i < MAXN; ++i) {
        foo[i] = i * foo[i - 1] % mod;
    }
}

ll myPow(ll base, int exp) {
    ll res = 1;
    while (exp) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

ll inv(ll a) {
    return myPow(a, mod - 2);
}

ll C(ll a, ll b) {
    return (foo[a] * inv(foo[b]) % mod) * inv(foo[a - b]) % mod;
}

int main() {
    init();
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    ll cand = 0;
    for (int i = 0; i <= n; ++i) {
        cin >> a[i];
        cand = cand ^ i ^ a[i];
    }

    bool between = false;
    int cnt = 0;
    for (int i = 0; i <= n; ++i) {
        if (a[i] == cand) {
            if (between) {
                between = false;
            } else {
                between = true;
            }
        } else {
            if (!between) ++cnt;
        }
    }

    for (int i = 1; i <= n + 1; ++i) {
        if (i > 1) cout << endl;
        if (i - 1 <= cnt) {
            cout << (C(n + 1, i) - C(cnt, i - 1) + mod) % mod;
        } else {
            cout << C(n + 1, i);
        }
    }

    return 0;
}

Measured memory_bytes: 2816
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;

int main(){
  int n,m,q;
  while(cin >> n >> m >> q){
    if(n==0 && m==0 && q==0)return 0;

    vector<ll> cor(m, (1LL<<n) - 1);

    ll bit = 0;
    for(int x=0;x<q;x++){
      string b,s;
      cin >> b >> s;

      ll change = 0;
      for(int i=0;i<n;i++){
	if(b[i] == '1')change |= 1LL<<i;
      }

      bit ^= change;

      for(int i=0;i<m;i++){
	if(s[i] == '1')cor[i] &= bit;
      }

      ll revbit = (1LL<<n)-1 - bit; 
      for(int i=0;i<m;i++){
	if(s[i] == '0')cor[i] &= revbit;
      }
    }

    map<ll,int> log2;
    for(int i=0;i<n;i++)log2[1LL<<i] = i;

    vector<int> det, use(n,0);
    unsigned int p = 0;
    while(true){
      for(int i=0;i<m;i++){
	if(log2.find(cor[i]) != log2.end()){
	  int id = log2[cor[i]];
	  if(!use[id]){
	    det.push_back(id); use[id]=true;
	  }
	}
      }

      if(p==det.size())break;

      while(p<det.size()){
	ll exp2 = 1LL<<det[p];
	for(int i=0;i<m;i++){
	  if( cor[i]!=exp2 && cor[i]&exp2 )cor[i] -= exp2;
	}
	p++;
      }
      //for(int i=0;i<m;i++)cout << cor[i] << " "; cout << endl;
    }

    for(int i=0;i<m;i++){
      if(log2.find(cor[i]) != log2.end()){
	int id = log2[cor[i]];
	if(id<10)cout << id;
	else cout << (char)('A'+id-10);
      }else{
	cout << "?";
      }
    }
    cout << endl;
  }
}

Measured memory_bytes: 1240
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define SORT(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
int main()
{
	double x1,y1,x2,y2,xq,yq,nx,ny;
	while(scanf("%lf,%lf,%lf,%lf,%lf,%lf",&x1,&y1,&x2,&y2,&xq,&yq)!=EOF)
	{
		if(x1==x2)
		{
			printf("%.6f %.6f\n",x1*2-xq,yq);
			continue;
		}
		if(y1==y2)
		{
			printf("%.6f %.6f\n",xq,y1*2-yq);
			continue;
		}
		nx=((x2-x1)*(x2-x1)*xq+(y2-y1)*(y2-y1)*x1+yq*(y2-y1)*(x2-x1)-y1*(x2-x1)*(y2-y1))/((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
		ny=(y2-y1)*(nx-x1)/(x2-x1)+y1;
		printf("%.6f %.6f\n",nx*2-xq,ny*2-yq);
	}
	return 0;
}

Measured memory_bytes: 1240
#include <bits/stdc++.h>
#define pb push_back
#define cmin(a,b) (a>b?a=b:a)
#define cmax(a,b) (a<b?a=b:a)
#define mem(a,k) memset(a,k,sizeof(a))
#define lop(i,s,t) for(int i=s;i<(t);++i)
#define rep(i,s,t) for(int i=s;i<=(t);++i)
#define dec(i,s,t) for(int i=s;i>=(t);--i)
#define fore(i,v) for(int i=g[v],d=es[i].d;i;i=es[i].nxt,d=es[i].d)
using namespace std;

#define Pr(f,...) fprintf(stdout,f,##__VA_ARGS__),fflush(stdout)

typedef long long ll;

template<typename T>
void read(T &x){
	x=0; 
	char c;
	for(c=getchar();!isdigit(c);c=getchar()); 
	for(;isdigit(c);c=getchar())x=x*10+c-'0'; 
}

const int N=2e5+50,oo=N;

char col[N]; 
int siz[N],n,mx[N],sc[N],R[N],L[N]; 
ll ans;
vector<int> g[N]; 

void chkMx(int v,int w){
	if(w>mx[v]){
		sc[v]=mx[v];
		mx[v]=w;
	}else if(w>sc[v]){
		sc[v]=w;
	}
}

void dp(int v,int p){
	mx[v]=0;
	sc[v]=-oo;
	L[v]=oo;
	siz[v]=col[v]-'0';
	for(int d:g[v])if(d!=p){
		dp(d,v);
		chkMx(v,mx[d]+1); 
		siz[v]+=siz[d];
		if(siz[d])cmin(L[v],mx[d]+1); 
	}
}

void calc(int v,int p,int uMx){
	chkMx(v,uMx); 
	R[v]=min(mx[v],sc[v]+2)-1;
	if(col[v]=='1')L[v]=0;
	for(int d:g[v])if(d!=p){
		int u=mx[v]==mx[d]+1?sc[v]+1:mx[v]+1;
		if(siz[1]-siz[d]>0)cmin(L[d],u); 
		calc(d,v,u); 
	}
}	

int main(int argc,char *argv[]){
#ifdef CURIOUSCAT
	//freopen("dat.in","r",stdin);
	//freopen("my.out","w",stdout);
#endif
	read(n); 
	rep(i,1,n-1){
		int u,v; 
		read(u),read(v); 
		g[u].pb(v); 
		g[v].pb(u); 
	}	
	scanf("%s",col+1); 
	dp(1,0); 
	calc(1,0,0); 
	rep(i,1,n){
		ans+=max(0,R[i]-L[i]+1);
		//Pr("v=%d,L[v]=%d,R[v]=%d\n",i,L[i],R[i]); 
	}
	printf("%lld\n", ans+1);
	return 0;
}



Measured memory_bytes: 24832
#import <Foundation/Foundation.h>
typedef long long Int;
int main() {
	char prev = '\0';
	Int current = 0;
	NSMutableArray *list = [NSMutableArray array];
	char c;
	while((c=getchar())!='\n'){
		if(c=='<'){
			if(prev==c){
				current++;
			}else{
				if(prev!='\0') [list addObject:@(current)];
				current = 1;
			}
		}else{
			if(prev==c){
				current--;
			}else{
				if(prev!='\0') [list addObject:@(current)];
				current = -1;
			}
		}
		prev = c;
	}
	[list addObject:@(current)];
	Int ans = 0;
	current = 0;
	for(NSNumber *value in list){
		Int val = [value longLongValue];
		if(val > 0){
			ans += val*(val+1)/2;
			current = val;
		}else{
			val = ABS(val);
			if(val>current) {
				ans -= current;
				ans += val;
			}
			ans += val*(val-1)/2;
			current = 0;
		}
	}
	printf("%lld\n", ans);
}


Measured memory_bytes: 6692
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    long long s = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            for(int k = 1; k <= n; k++) s += __gcd(__gcd(i, j), k);
        }
    }
    cout << s;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define testcase() int t; cin>>t; while(t--)
#define fo(n) for (int i = 0; i < n; i++)
#define deb(x) cout << #x << " = " << x << endl;
#define ll long long

using namespace std;

void solve()
{
    int n;
    cin >> n;
    ll arr[n];
    ll x = 0;
    fo (n)
    {    
        cin >> arr[i];
        x ^= arr[i];
    }
    ll temp = x;
    for (int i = 0; i < n; i++)
    {
        temp = x;
        cout << (temp ^ arr[i]) << " ";
    }
    cout << endl;
}

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

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

A = [input() for _ in range(N)]
B = [input() for _ in range(M)]

c = []

d = 0

for i in range(N-M+1):
    if d==1:break
    for j in range(N-M+1):
        c = [A[i+k][j:j+M] for k in range(M)]
        if B==c:
            d = 1
            break
if d==1:print('Yes')
else:print('No')



Measured memory_bytes: 3060
#pragma GCC optimize("Ofast,inline,unroll-loops,fast-math")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <sstream>
#include <bitset>
#include <memory>
#include <string>
#include <vector>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <deque>
#include <algorithm>
#include <random>
#include <iomanip>
using namespace std;

int main(int argc, char *argv[]) {

	string s, t;
	cin >> s >> t;
	string u;
	int a, b;
	cin >> a >> b;
	cin >> u;
	if (u == s)
		a--;
	else
		b--;
	cout << a << " " << b << endl;
}









Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "iomanip"
#include "random"

using namespace std;

const long long int MOD = 1000000007;
const long double EPS = 0.00000001;
const long double PI = 3.1415926535897932384626433;

long long int N, M, K, H, W;
long double L, R;



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

	string s;
	getline(cin, s);
	while (s != ".") {
		stack <char>st;
		bool flag = true;
		for (auto i : s) {
			if (i == '(' || i == '[') {
				st.push(i);
			}
			if (i == ')') {
				if (st.empty()) {
					flag = false;
					break;
				}
				if (st.top() == '[') {
					flag = false;
					break;
				}
				st.pop();
			}
			if (i == ']') {
				if (st.empty()) {
					flag = false;
					break;
				}
				if (st.top() == '(') {
					flag = false;
					break;
				}
				st.pop();
			}
		}
		if (flag&&st.empty()) {
			cout << "yes\n";
		}
		else {
			cout << "no\n";
		}
		getline(cin, s);
	}
	return 0;
}

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

const int INF = 1001001001;

int a[12][12];

int main(void)
{
  int N, M, X;
  cin >> N >> M >> X;
  vector<int> C(N);
  rep(i, N)
  {
    cin >> C[i];
    rep(j, M)
    {
      cin >> a[i][j];
    }
  }

  int ans = INF;
  rep(s, 1 << N)
  {
    int cost = 0;
    vector<int> d(M);
    rep(i, N)
    {
      if (s >> i & 1)
      {
        cost += C[i];
        rep(j, M) d[j] += a[i][j];
      }
      bool ok = true;
      rep(j, M) if (d[j] < X) ok = false;
      if (ok)
        ans = min(ans, cost);
    }
  }

  if (ans == INF)
    cout << -1 << endl;
  else
    cout << ans << endl;

  return 0;
}

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

using namespace std;

#define pb push_back
#define ll long long
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define bug cout << "ok" << endl

const ll INF = 1e9 + 5, N = 1e5 + 5, mod = 1e9 + 7;

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

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

int main(){
  int n;
  long long d;
  cin >> n >> d;
  
  int ans=0;
  for(int i=0; i<n; i++){
    long long x,y;
    
    cin >> x >> y;
    if(x*x+y*y<=d*d){
      ans++;
    }
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 3640
double x[100],y[100],t,u,s;n,i,j,k,c;main(m){for(;m=scanf("%d",&n),i=n;printf("%d\n",m)){for(;i--;scanf("%lf,%lf",x+i,y+i));for(i=n;j=--i;)for(;j--;)if(s=(u=acos(hypot(x[j]-x[i],y[j]-y[i])/2))<9)for(t=atan2(y[j]-y[i],x[j]-x[i]);c=0,s+3;s-=2)for(k=n;k--;)hypot(x[i]+cos(t+s*u)-x[k],y[i]+sin(t+s*u)-y[k])<1.1&&++c>m?m=c:0;}}

Measured memory_bytes: 0
# 整数の入力
N = gets.to_i
# スペース区切りの整数の入力
d = gets.chop.split.map(&:to_i)
l = d.length

point = 0

for i in 0..l-1 do
  for j in i+1..l-1 do
    point += d[i]*d[j]
  end
end

puts point


Measured memory_bytes: 1788
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <random>



using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)













int main(){
    ll n;
    cin >> n;
    vector<double> v(n);
    REP(i, n){
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    double ans = v[0];
    for(ll i = 1; i < n; i++){
        ans = (ans + v[i]) / 2.0;
    }
    printf("%.8lf\n", ans);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
#define _start  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb 		push_back
#define ss 		second
#define ff 		first
#define ll		long long
#define int     long long
#define mk      make_pair
#define ld 		long double
#define vi 		vector<int>
#define pi		pair<int,int>
#define mod 	1000000007
#define pqg     priority_queue<int>
#define pqs     priority_queue<int,vi,greater<int> >
#define forn(n) for(int i=0;i<n;i++)
#define w(t) 	int t; cin>>t; while(t--)
#define kick(t) int t; cin>>t; for(int p=0;p<t;p++)
// typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> oset;
ll powmod(ll base,ll exp,ll MOD=mod){ll res=1;while(exp>0){if(exp%2==1) res=(res*base)%MOD;base=(base*base)%MOD;exp/=2;}return (res%MOD);}
ll mul_inv(ll a,ll b = mod) {ll t1=a,t2=b,t3,v1=1,v2=0,v3;while(t2!=1){ll x=t1/t2;t3=t1-x*t2;v3=v1-x*v2;t1=t2,t2=t3;v1=v2,v2=v3;}return(v2+b)%b;}

int32_t main(){
    _start
    int n;
    cin>>n;
    vector<int> arr(n);
    forn(n)cin>>arr[i];
    int count=0;
    sort(arr.begin(),arr.end());
    for(int k=n-1;k>=2;k--){
        for(int i=0;i<k-1;i++){
            for(int j=i+1;j<k;j++){
                if(arr[i]==arr[j]||arr[i]==arr[k]||arr[j]==arr[k])
                    continue;
                if(i<j&&j<k&&arr[i]+arr[j]>arr[k]){
                    count++;
//                    cout<<i<<" "<<j<<" "<<k<<"-";
//                    cout<<arr[i]<<" "<<arr[j]<<" "<<arr[k]<<endl;
                }
            }
        }
    }
    cout<<count<<endl;
}


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

const int maxn=4e5+7,p=1e9+7;
long long fac[maxn],inv[maxn],ans;
int n,k;

long long poww(long long a,long long b)
{
	long long ans=1,tmp=a;
	while(b) {
		if(b&1) ans=(ans*tmp)%p;
		tmp=(tmp*tmp)%p;
		b>>=1;
	}
	return ans;
}

long long c(int n,int m)
{
	long long ans=fac[n];
	ans=(((ans*inv[m])%p)*inv[n-m])%p;
	return ans;
}

int main()
{
	scanf("%d %d",&n,&k);
	fac[0]=inv[0]=1;
	for(int i=1;i<maxn;++i) fac[i]=(fac[i-1]*i)%p;
	inv[maxn-1]=poww(fac[maxn-1],p-2);
	for(int i=maxn-2;i;--i) inv[i]=(inv[i+1]*(i+1))%p;
	k=min(k,n-1);
	for(int i=0;i<=k;++i) {
		ans+=(c(n,i)*c(n-1,i))%p;
		ans%=p;
	}
	printf("%lld",ans);
}

Measured memory_bytes: 6528
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <iomanip>

#define PI 3.14159265358979323846

int main(){
    int a,b,h,m;
    std::cin >> a >> b >> h >> m;
    double x=30*h; //長身
    x=x+0.5*m-90;
    
    double y=6*m-90; //短針
    
    double p=a*std::sin(y*PI/180);
    double q=a*std::cos(y*PI/180);
    double s=b*std::sin(x*PI/180);
    double t=b*std::cos(x*PI/180);
    
    double ans=std::sqrt((s-p)*(s-p)+(t-q)*(t-q));
    std::cout << std::fixed << std::setprecision(20) << ans << std::endl;
    return 0;
}



Measured memory_bytes: 4124
#include <stdio.h>

int A[50];

int fib(int);

int main(){
  int i,n;

  scanf("%d",&n);
  for(i=0;i<50;i++) A[i]=-1;

  printf("%d\n",fib(n));

  return 0;
}

int fib(int n){
  if(n==0 || n==1)return A[n]=1;
  if(A[n]!=-1) return A[n];
  return A[n]=fib(n-1)+fib(n-2);
}



Measured memory_bytes: 2056
n,m,x = gets.split(" ").map { |e| e.to_i }
a = gets.split(" ").map { |e| e.to_i }

big = a.select{ |n| n >= x }
small = a.select{ |n| n <= x }

n_big = big.length
n_sma = small.length

puts [n_big, n_sma].min

Measured memory_bytes: 1788
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import bisect


def main():
    N, M, X = map(int, input().split())
    A = list(map(int, input().split()))
    index = bisect.bisect_left(A, X)
    print(min(index, M - index))


if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,v,p;
int a[100005],b[100005],sum[100005];
map<int,int> tr[100005];
void upt(int x,int v,int c){
	while(x<=n) tr[x][v]+=c,x+=(x&-x);
}
int query(int x,int v){
	int res=0;
	while(x) res+=tr[x][v],x-=(x&-x);
	return res;
}
//m judges
//v problems
//first p problems
signed main(){
	int n,a,b;
	cin>>n>>a>>b;
	if(a>b) swap(a,b);
	if((b-a)%2==0) cout<<(b-a)/2;
	else cout<<min(a,n-b+1)+(b-a-1)/2;
	return 0;
} 


Measured memory_bytes: 8336
using System;
using System.Linq;
using System.Collections.Generic;
using System.Numerics;
using static System.Console;

class Solver {
    Scanner sc = new Scanner();

    public void Solve() {
        var N = sc.nextInt();
        var a = sc.ArrayInt(N);

        var n = a.Max();
        var half = n / 2;
        var r = 0;
        var tmp = int.MaxValue;
        for (int i = 0; i < N; i++) {
            if (a[i] == n) { continue; }
            var abs = Math.Abs(half - a[i]);
            if (tmp > abs) {
                tmp = abs;
                r = a[i];
            }
        }

        WriteLine(n + " " + r);
    }
}



class Scanner {
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner() {
        s = new string[0];
        i = 0;
    }

    public string next() {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt() {


        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0) {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong() {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0) {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble() {
        return double.Parse(next());
    }

    public double[] ArrayDouble(int N, double add = 0) {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

class Program {
    static void Main(string[] args) {
        Solver s = new Solver();
        s.Solve();
    }
}

Measured memory_bytes: 19808
#include<iostream>
#include<string>
using namespace std;
int main()
{
	int n, a;
	string shuffle;
	cin >> shuffle;
	while(shuffle[0] != '-')
	{
		cin >> n;
		while (n--)
		{
			cin >> a;
			shuffle = shuffle.substr(a, shuffle.size() - a) + shuffle.substr(0, a);
		}
		cout << shuffle;
		cout << endl;
		cin >> shuffle;
	}
	return 0;
}


Measured memory_bytes: 3204
import sys

# import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
import itertools
# from operator import attrgetter, itemgetter
# import math

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, a, b, c = list(map(int, readline().split()))
    l = [int(input()) for _ in range(n)]

    ans = INF

    selects = list(itertools.product(range(4), repeat=n))

    for select in selects:
        mp = -30
        bamboo_length = [0] * 3
        for i, num in enumerate(select):
            if num != 3:
                bamboo_length[num] += l[i]
                mp += 10

        for length in bamboo_length:
            if length == 0:
                break
        else:
            mp += abs(a - bamboo_length[0])
            mp += abs(b - bamboo_length[1])
            mp += abs(c - bamboo_length[2])
            ans = min(mp, ans)

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 10996
use std::cmp::min;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let n: usize = sc.read();
    let l: Vec<u64> = sc.vec(n + 1);
    if l[0] != 0 {
        if n == 0 && l[0] == 1 {
            println!("1");
            return;
        } else {
            println!("-1");
            return;
        }
    }

    let mut max_p = vec![0; n + 1];
    let mut min_p = vec![0; n + 1];
    for i in (0..n).rev() {
        let max_next_node = max_p[i + 1] + l[i + 1];
        let min_next_node = min_p[i + 1] + l[i + 1];
        min_p[i] = (min_next_node + 1) / 2;
        max_p[i] = max_next_node;
    }

    let mut p = vec![0; n + 1];
    p[0] = 1;
    for i in 1..n {
        let prev_p = p[i - 1];
        if l[i] > prev_p * 2 {
            println!("-1");
            return;
        }
        p[i] = min(prev_p * 2 - l[i], max_p[i]);
        if p[i] < min_p[i] {
            println!("-1");
            return;
        }
    }

    let mut ans = 0;
    for i in 0..=n {
        ans += p[i] + l[i];
    }

    println!("{}", ans);
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        Self(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 5232
g = [[-1 for i in range(15)] for j in range(15)]
# 15×15の行列gを-1で埋めておく

n=int(input()) #参加人数
for i in range(n):
  m = int(input())
  for j in range(m):
    x, y= map(int, input().split())
    g[i][x-1] = y
#人の番号Aは1から始まるのでxの番号も1つ前倒し
# y==1なら正直, Y==0なら不親切
ans=0

for i in range (1<<n): #range(2**n)でも同じはず
  honests = [0 for _ in range(n)] #正直者の番号格納用、0の列
  for j in range(n):
    if (i >> j) & 1:
      honests[j] = 1 
#正直ものが1,3,5,6ならhonests = [1,0,1,0,1,1,・・・]となる
#これを全bitで作成したものがhonests[施行番号][スイッチ行列]
  hantei = True
  for j in range(n):
    if honests[j]==1: 
      #j番目の人の証言が正しいとしたときの分岐
      for k in range(n):
        if g[j][k] == -1: 
          continue #証言なし
        if g[j][k] != honests[k]:
          #g[j][k]はj番目の人が話したk番目の人に対する証言
          #これが異なっていると矛盾が生じている
          hantei = False
  if hantei == True:
    ans = max(ans, honests.count(1))
                     
print(ans)

Measured memory_bytes: 9108
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue> 
#include <stack>
#include <set>

using namespace std;
typedef long long ll;
#define rep(i, s, e) for (int(i) = (s); (i) <= (e); ++(i))
#define all(x) x.begin(),x.end()


int main()
{
	int N, W; cin >> N >> W;
	vector<int> w(N + 1);
	vector<ll> v(N + 1);
	rep(i, 1, N)cin >> w[i] >> v[i];

	vector<vector<ll>> dp(N + 1, vector<ll>(500000, 0));
	rep(i, 1, N)rep(j, 0, W)
	{
		if (j < w[i])dp[i][j] = dp[i - 1][j];
		else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
	}
	cout << dp[N][W] << endl;
}

Measured memory_bytes: 398848
package main

import (
	"fmt"
	"strings"
)

func main() {
	var N, K int
	fmt.Scanf("%d %d", &N, &K)

	var S string
	fmt.Scanf("%s", &S)

	var res string
	for i := range S {
		if i == K-1 {
			res += strings.ToLower(string(S[i]))
		} else {
			res += string(S[i])
		}
	}
	fmt.Println(res)
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int mod=1000000007;
const int maxn=55;
int n,m,k,dfn[maxn],low[maxn],tot,cnt,c1[maxn],c2[maxn],vis[maxn],C[205][205],pk[55];
vector<int> G[maxn];
stack<pii> stk;
void tarjan(int u,int fa) {
    dfn[u]=low[u]=++tot;
    for (int i=0;i<(int)G[u].size();++i) {
        int v=G[u][i];
        if (v==fa) continue;
        if (!dfn[v]) {
            stk.push(pii(u,v));
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if (low[v]>=dfn[u]) {
                ++cnt;
                while (!stk.empty()) {
                    int x=stk.top().first;
                    int y=stk.top().second;
                    stk.pop();
                    if (vis[x]!=cnt) {
                        vis[x]=cnt;
                        ++c1[cnt];
                    }
                    if (vis[y]!=cnt) {
                        vis[y]=cnt;
                        ++c1[cnt];
                    }
                    ++c2[cnt];
                    if (x==u&&y==v) break;
                }
            }
        } else if (dfn[v]<dfn[u]) {
            low[u]=min(low[u],dfn[v]);
            stk.push(pii(u,v));
        }
    }
}
inline int ksm(int x,int n) {
    int ret=1;
    while (n) {
        if (n&1) ret=1ll*ret*x%mod;
        n>>=1;
        x=1ll*x*x%mod;
    }
    return ret;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    C[0][0]=pk[0]=1;
    for (int i=1;i<=m+k;++i) {
        C[i][0]=1;
        for (int j=1;j<=i;++j)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
    for (int i=1;i<=n;++i) pk[i]=1ll*pk[i-1]*k%mod;
    for (int i=0;i<m;++i) {
        int u,v;scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i=1;i<=n;++i) if (!dfn[i])
        tarjan(i,0);
    int res=1;
    for (int i=1;i<=cnt;++i)
        if (c1[i]>c2[i]) res=1ll*res*k%mod;
        else if (c2[i]==c1[i]) {
            int tmp=0;
            for (int j=1;j<=c1[i];++j)
                tmp=(tmp+pk[__gcd(j,c1[i])])%mod;
            res=1ll*res*tmp%mod*ksm(c1[i],mod-2)%mod;
        } else res=1ll*res*C[c2[i]+k-1][k-1]%mod;
    printf("%d\n",res);
    return 0;
}


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

#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); i--)
#define ITER(it, a) for(typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a, value, sizeof(a))

#define SZ(a) (int) a.size()
#define ALL(a) a.begin(),a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const LL INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;

const int MOD = 998244353;

const int MAX = 300300;

LL bpow(LL a, LL b)
{
	LL res = 1;
	while(b)
	{
		if (b & 1) res = (res * a) % MOD;
		a = (a * a) % MOD;
		b /= 2;
	}
	return res;
}

LL inv(LL a)
{
	return bpow(a, MOD - 2);
}

LL F[MAX];
LL IF[MAX];

LL C(int n, int k)
{
	LL res = F[n];
	res *= IF[k];
	res %= MOD;
	res *= IF[n-k];
	res %= MOD;
	return res;
}

char A[4][MAX];
int n, m;

LL V[2][MAX];

void calcVals(int x, char* u, char* d, int m, LL* V)
{
	int y = 0;
	int z = 0;
	FOR (i, 0, m)
	{
		y += u[i];
		z += d[i];

		if (x == 0)
		{
			if (y == 0 && z == 0) V[i] = 1;
			else V[i] = 0;
		}
		else
		{
			V[i] = C(x + y + z - 1, x - 1);
		}
	}
}

LL solve(char* u, char* d, char* l, char* r)
{
	int x = 0;
	FOR (i, 0, n)
	{
		x += l[i];
	}

	calcVals(x, u, d, m, V[0]);

	x = 0;
	FOR (i, 0, n)
	{
		x += r[i];
	}

	reverse(d, d+m);
	reverse(u, u+m);

	calcVals(x, u, d, m, V[1]);

	reverse(d, d+m);
	reverse(u, u+m);
	reverse(V[1], V[1] + m);

	LL res = 0;
	LL sum = 0;

	FOR (i, 0, m)
	{

		if (i) sum += V[0][i-1];
		else
		{
			sum++;
		}
		sum = (sum * (u[i] + d[i])) % MOD;
		LL cur = 0;
		if (i < m - 1) cur = V[1][i+1];
		else cur = 1;

	//	cout<<i<<": "<<sum<<' '<<cur<<endl;

		cur *= sum;

		res = (res + cur) % MOD;
	}

	return res;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//ios::sync_with_stdio(false); cin.tie(0);

	F[0] = 1;
	IF[0] = 1;
	FOR (i, 1, MAX)
	{
		F[i] = (F[i-1] * i) % MOD;
		IF[i] = inv(F[i]);
	}

	scanf("%d%d", &n, &m);

	FOR (it, 0, 4)
	{
		scanf("%s", A[it]);
		int len = strlen(A[it]);
		FOR (j, 0, len)
		{
			A[it][j] -= '0';
		}
	}

	char* l = A[0];
	char* r = A[1];
	char* u = A[2];
	char* d = A[3];

	int ind = 0;
	FOR (i, 0, m)
	{
		if (u[i] == 0 && d[i] == 0) continue;
		u[ind] = u[i];
		d[ind] = d[i];
		ind++;
	}

	m = ind;

	ind = 0;
	FOR (i, 0, n)
	{
		if (l[i] == 0 && r[i] == 0) continue;
		l[ind] = l[i];
		r[ind] = r[i];
		ind++;
	}

	n = ind;

	//cout<<"!! "<<n<<' '<<m<<endl;

	if (n == 0 || m == 0)
	{
		LL res = 1;
		FOR (i, 0, m)
		{
			res = (res * (d[i] + u[i])) % MOD;
		}
		FOR (i, 0, n)
		{
			res = (res * (l[i] + r[i])) % MOD;
		}

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

	LL res = solve(u, d, l, r);
	swap(n, m);
	res += solve(l, r, u, d);

	res %= MOD;
	cout<<res<<endl;



}


Measured memory_bytes: 9728
#include "bits/stdc++.h"
typedef long long ll;
using namespace std;

int main() {
    int m1, m2, d1, d2;
    cin >> m1 >> d1;
    cin >> m2 >> d2;
    if (m1 != m2) {
        cout << 1 << endl;
        return 0;
    }
    if (m2 < m1) {
        cout << 1 << endl;
        return 0;
    }
    cout << 0 << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main()
{
  int a,b; cin>>a>>b;
  int x,y; cin>>x>>y;
  cout<<fixed;
  cout<<setprecision(12);
  double p = a;
  double q = b;
  cout<<(p*q)/2.0<<" ";
  cout<<setprecision(0);
  if(a  % 2 == 0 and b % 2 ==0)
  {
    if( x == a/2 and y == b/2)
    	cout<<1;
    else cout<<0;
  }
  else
  {
    cout<<0;
  }
  return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	A = inputList()

	A.sort()
	zyuufuku = {}
	for i,val in enumerate(A):
		if i == 0:
			continue
		if val == A[i-1]:
			if val in zyuufuku:
				pass
			else:
				zyuufuku[val] = 1

	refd = [0 for i in range(1000000 + 1)]
	for i,val in enumerate(A):
		if val in zyuufuku:
			if zyuufuku[val] > 2:
				continue
			else:
				zyuufuku[val] += 1
		for j in range(val,1000000 + 1,val):
			refd[j] += 1

	ans = 0
	for i,val in enumerate(A):
		if val in zyuufuku:
			continue
		if refd[val] < 2:
			ans += 1

	print(ans)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()


Measured memory_bytes: 169892
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9 + 7);

int main(void) {
	int n;
	cin >> n;
	
	vector<string> s(n);
	map<string, int> mp; 
	for(int i = 0; i < n; ++i) {
		cin >> s[i];
		mp[s[i]]++;
	}
	
	for(auto& x : mp) {
		if( x.second > 1 ) {
			cout << "No" << endl;
			return 0;
		}
	}
	
	for(int i = 0; i < n - 1; ++i) {
		if( s[i].back() != s[i + 1].front() ) {
			cout << "No" << endl;
			return 0;
		}
	}
	
	cout << "Yes" << endl;
	
	return 0;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define INF 1e9
#define MOD 1000000007
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int main(void) {
    ll N;
    cin >> N;

    if(N%2 == 1){
        cout << 0 << endl;
        return 0;
    } else {
        ll ans = 0;
        ll div = 10;

        while (N >= div)
        {
            ans += N / div;            
            div *= 5;
        }
        cout << ans << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3556
n, m = map(int, input().split())
passed = 0
failed = 0
dicto = {}

for i in range(1, n+1):
    dicto[i] = [False, 0]

for i in range(m):
    key, status = input().split()
    key = int(key)
    if status == 'WA' and not dicto[key][0]:
        dicto[key][1] += 1
    else:
        dicto[key][0] = True

for i in dicto:
    if dicto[i][0]:
        failed += dicto[i][1]
        passed += 1

print(passed, failed)


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

namespace AtCoder
{
    class Program
    {
        public static void Main()
        {
            new Program().Solve();
        }

        void Solve()
        {
            int n = int.Parse(Console.ReadLine());
            var x = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            var tmpX = x.OrderBy(_ => _).ToArray();
            var b = new int[n];

            var lMedian = tmpX[n / 2 - 1];
            var rMedian = tmpX[n / 2];
            for (int i = 0; i < n; i++)
            {
                int value = x[i];
                if (value <= lMedian)
                {
                    b[i] = rMedian;
                }
                else if (value >= rMedian)
                {
                    b[i] = lMedian;
                }
            }

            for (int i = 0; i < b.Length; i++)
            {
                Console.WriteLine(b[i]);
            }
        }
    }
}


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

using namespace std;
using ll = long long;
using ull = unsigned long long;

#ifndef __MACRO_H__
#define __MACRO_H__

#define all(collection) (collection).begin(), (collection).end()  // begin to end
#define each(e, collection) for(auto& e: collection)              // for each
#define rep(i, begin, end) for (ll i = begin; i < end; i++)       // repeat
#define repr(i, begin, end) for (ll i = begin; end < i; i--)      // repeat reverse
#define size(collection) ((ll) (collection).size())               // collection size

#endif

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

	ll max = (n - 1) * (n - 2) / 2;

	if (max < k)
	{
		cout << -1;
		return 0;
	}

	vector<pair<ll, ll>> ans;
	ans.push_back({ 0, 1 });
	rep(i, 2, n)
		ans.push_back({ 1, i });
	if (max == k)
	{
		cout << size(ans) << endl;
		each(e, ans)
			cout << e.first + 1 << " " << e.second + 1 << endl;
		return 0;
	}

	rep(e, 2, n)
	{
		ans.push_back({ 0, e });
		max--;
		if (max == k)
		{
			cout << size(ans) << endl;
			each(e, ans)
				cout << e.first + 1 << " " << e.second + 1 << endl;
			return 0;
		}
	}

	rep(s, 2, n-1)
	{
		rep(e, s + 1, n)
		{
			ans.push_back({ s, e });
			max--;
			if (max == k)
			{
				cout << size(ans) << endl;
				each(e, ans)
					cout << e.first + 1 << " " << e.second + 1 << endl;
				return 0;
			}
		}
	}

	return 0;
}



Measured memory_bytes: 512
#include <stdio.h>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <cmath>
//#include <unordered_map>
//#include <unordered_set>
//#include <boost/container/static_vector.hpp>
//#include <boost/unordered_set.hpp>
//#include <boost/unordered_map.hpp>
//#include <unistd.h>

//#include <cv.h>
//#include <highgui.h>
#include <stdlib.h>
#include <string>

const int MAX_M = 100050;
int N, M;
int L[MAX_M], R[MAX_M];

int main(int argc, char **argv) {
    std::cin >> N >> M;

    for (int i = 1; i <= M; i++) {
        std::cin >> L[i] >> R[i];
    }

    L[0] = L[1];
    R[0] = R[1];

    for (int i = 1; i <= M; i++) {
        L[0] = std::max(L[0], L[i]);
        R[0] = std::min(R[0], R[i]);
    }

    std::cout << std::max(0, R[0] - L[0] + 1);

    return 0;
}

Measured memory_bytes: 1024
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

type Stack [200]int

func (S *Stack) pop(top int) (int, int) {
	top--
	return S[top+1], top
}

func (S *Stack) push(top int, x int) (Stack, int) {
	top++
	S[top] = x
	return *S, top
}

func atoi(s string) int {
	v, _ := strconv.Atoi(s)
	return v
}

func readLine(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func main() {
	var S Stack
	var a, b int
	var top int
	var ans int

	sc := bufio.NewScanner(os.Stdin)
	A := strings.Split(readLine(sc), " ")

	for _, x := range A {
		if x == "+" {
			a, top = S.pop(top)
			b, top = S.pop(top)
			S, top = S.push(top, a+b)
		} else if x == "*" {
			a, top = S.pop(top)
			b, top = S.pop(top)
			S, top = S.push(top, a*b)
		} else if x == "-" {
			b, top = S.pop(top)
			a, top = S.pop(top)
			S, top = S.push(top, a-b)
		} else {
			S, top = S.push(top, atoi(x))
		}
	}
	// fmt.Println(top)
	// fmt.Println(S)
	ans, top = S.pop(top)
	fmt.Println(ans)
}



Measured memory_bytes: 1204
using System.Collections.Generic;
using System;

public class hello
{
    public static void Main()
    {
        var triangle = new List<int>();
        var n = int.Parse(Console.ReadLine().Trim());
        for (int i = 0; i < n; i++)
        {
            string[] line = Console.ReadLine().Trim().Split(' ');
            for (int j = 0; j < 3; j++)
                triangle.Add(int.Parse(line[j]));
            triangle.Sort();
            if (triangle[2] * triangle[2] == triangle[0] * triangle[0] + triangle[1] * triangle[1]) Console.WriteLine("YES");
            else Console.WriteLine("NO");
            triangle.RemoveAll(x => x >= 0);
        }
    }
}

Measured memory_bytes: 9076
N = gets.to_i
as = gets.split.map(&:to_i)

max = 0
dp = Array.new(1<<N)
dp[0] = [[0, as[0]], [-1, 0]]
(1...(2**N)).each do |bits|
    first = [bits, as[bits]]
    second = [-1, 0]
    N.times do |i|
        if bits[i] == 1
            dp[bits - (1<<i)].each do |i, v|
                next if first[0] == i || second[0] == i
                if first[1] < v
                    second = first
                    first = [i, v]
                elsif second[1] < v
                    second = [i, v]
                end
            end
        end
    end
    dp[bits] = [first, second]
    sum = first[1] + second[1]
    max = sum if max < sum
    puts max
end

Measured memory_bytes: 59528
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

#include <limits.h>

using namespace std;

typedef long long ll;

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

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

int main(void) {
    string S;
    cin >> S;
    for (int i = 0; i < 3; i++) {
        cout << S[i];
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 3544
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007

int dpl[5010][5010], dpr[5010][5010];
int main() {
    int n, k, a[5010];
    cin >> n >> k;
    for (int i = 0; i < n; ++i)
        cin >> a[i];

    dpl[0][0] = 1;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < k; ++j)
            dpl[i + 1][j] = dpl[i][j] || j >= a[i] && dpl[i][j - a[i]];

    dpr[n][0] = 1;
    for (int i = n - 1; i >= 0; --i)
        for (int j = 0; j < k; ++j)
            dpr[i][j] = dpr[i + 1][j] || j >= a[i] && dpr[i + 1][j - a[i]];

    for (int i = 0; i <= n; ++i)
    {
        int imos[5010];
        imos[0] = 0;
        for (int j = 0; j < k; ++j)
            imos[j + 1] = imos[j] + dpr[i][j];
        for (int j = 0; j <= k; ++j)
            dpr[i][j] = imos[j];
    }
    int ans = n;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < k; ++j)
        {
            if (dpl[i][j] && dpr[i + 1][k - j] - dpr[i + 1][max(k - j - a[i], 0)])
            {
                --ans;
                break;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}


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

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

    string s;
    cin >> s;

    int n = (int)s.size();
    vector<int> t(n);
    if(s[n-1] == 'T') t[n-1] = 1;
    for(int i = n - 2; i >= 0; i--){
        t[i] = t[i+1] + (s[i] == 'T' ? 1 : 0);
    }

    int cnt = 0;
    for(int i = 0; i < n - 1; i++){
        if(s[i] == 'S' && t[i] > 0){
            cnt += 2;
            t[i+1] = t[i] - 1;
        }
        t[i+1] = min(t[i+1],t[i]);
    }
    cout << n - cnt << endl;
}

Measured memory_bytes: 1428
import math
import string


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

n = int(input())
a = readints()
sum = 1
for i in range(len(a)):
    if a[i] % 2 == 0:
        sum *= 2
    else:
        sum *= 1
print(3**len(a)-sum)


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

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<int, int> P;

const int MOD = 1000000007;
const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

const ll mod = 13;

int main()
{
    string S;
    cin >> S;
    int N = S.size();
    vector<vector<ll>> dp(N + 5, vector<ll>(mod, 0));

    if (S[0] == '?') {
        for (int j = 0; j < 10; j++)
            dp[1][j] = 1;
    } else {
        int j = (int)(S[0] - '0');
        dp[1][j] = 1;
    }

    for (int i = 1; i < N; i++) {
        for (int j = 0; j < mod; j++) {
            if (S[i] == '?') {
                for (int k = 0; k < 10; k++) {
                    int nj = (j * 10 + k) % mod;
                    dp[i + 1][nj] += dp[i][j];
                    dp[i + 1][nj] %= MOD;
                }
            } else {
                int k = (int)(S[i] - '0');
                int nj = (j * 10 + k) % mod;
                dp[i + 1][nj] += dp[i][j];
                dp[i + 1][nj] %= MOD;
            }
        }
    }

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


Measured memory_bytes: 16684
from collections import deque

n,m = map(int,input().split())


grafo = [[] for i in range(n+1)]

num_adj = [0] * (n+1)

for i in range(m):
    u, v = map(int,input().split())
    grafo[u].append(v)
    num_adj[v] += 1

q = deque()

for i in range(1, n+1):
    if num_adj[i] == 0:
        q.append(i)

dp = [0] * (n + 1)

while q:
    n = q.popleft()
    for s in grafo[n]:
        num_adj[s] -= 1

        if num_adj[s] == 0:
            q.append(s)
            dp[s] = dp[n] + 1

print(max(dp))


Measured memory_bytes: 87732