akhauriyash/Code-Regression huggingface dataset:
# include <cstdio>
# include <iostream>
# include <algorithm>
using namespace std;
int n,ans,sum=-1e9;
string s;

int main () {
//	freopen (".in", "r", stdin);
//	freopen (".out", "w", stdout);
	scanf ("%d",&n);
	cin>>s;
	for (int i=0;i<n;i++){
		if (s[i]=='I') ans++;
		else ans--;
		sum=max(sum,ans);
	}
	sum=max(sum,0);
	printf ("%d\n",sum);
	return 0;
}
//By苍空的蓝耀


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
// #include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
// #include <random>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

/*
unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 g1.seed(seed1);
*/
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<pii, pii> ppiipii;
typedef pair<int, ppiipii> pippiipii;
typedef pair<int, pii> pipii;
typedef pair<pii, int> ppiii;
typedef pair<int, ppiii> pippiii;
typedef pair<int, ll> pill;
typedef pair<int, double> pid;
typedef pair<string, string> pss;
// note to self, the below two triggers someone
typedef pair<ll, ll> pll;
typedef pair<ll, int> plli;
typedef long double ld;

int l[100005];

int main() {
  int n;
  scanf("%d", &n);
  for(int i = 0; i < n; i++) {
    scanf("%d", &l[i]);
  }
  sort(l, l+n);
  int best = 0;
  for(int i = 1; i < n-1; i++) {
    if(abs(l[n-1] - 2 * l[i]) < abs(l[n-1] - 2 * l[best])) {
      best = i;
    }
  }
  printf("%d %d\n", l[n-1], l[best]);
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define X first
#define Y second
#define sz(v) (int)v.size()
using ord = tree<int, null_type, greater<int>, rb_tree_tag, tree_order_statistics_node_update>;
 
void solve();
 
main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
#ifdef ONPC
	freopen("in.txt", "r", stdin);
#endif
	int t = 1;
	//cin >> t;
	while (t--) solve();
	return 0;
}

const int N = 2e5 + 5;
int n, a[N], cur;

void solve() {
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i <= n; ++i) {
		if (a[i] == cur + 1) {
			++cur;
		}
	}
	if (cur == 0) cout << -1;
	else cout << n - cur;
}


Measured memory_bytes: 1024
#include <string>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <utility>
#include <algorithm>
#include <numeric>
#include <iostream>

using namespace std;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

int main()
{
	char c = 'A',f[10];
	while(~scanf("%s",&f)){
		if(f[0] == c) c = f[2];
		else if(f[2] == c) c = f[0];
	}
	printf("%c\n",c);
}

Measured memory_bytes: 0
#define _CRT_SECURE_NO_WARNINGS
#define _SCL_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <utility>
#include <algorithm>
#include <functional>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <limits>
#include <numeric>
#include <valarray>
#include <fstream>

using namespace std;
typedef unsigned int uint;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL, LL> PP;
#define REP(i,a,n) for(LL i = (a); i < (LL)(n); ++i)
#define REM(i,a,n) for(LL i = ((n) - 1); i >= (a); --i)
#define FLOAT fixed << setprecision(16)
#define SPEEDUP {cin.tie(0); ios::sync_with_stdio(false);}
const int INF = 0x3FFFFFFF;
const LL INFLL = 0x3FFFFFFF3FFFFFFF;
const double INFD = 1.0e+308;
const string INFSTR = "\x7f";
const double EPS = 1.0e-9;

void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
template <class T, class U>
istream& operator>>(istream& ist, pair<T, U>& right) { return ist >> right.first >> right.second; }
template <class T, class U>
ostream& operator<<(ostream& ost, const pair<T, U>& right) { return ost << right.first << ' ' << right.second; }
template <class T, class TCompatible, size_t N>
void Fill(T(&dest)[N], const TCompatible& val) { fill(dest, dest + N, val); }
template <class T, class TCompatible, size_t M, size_t N>
void Fill(T(&dest)[M][N], const TCompatible& val) { for (int i = 0; i < M; ++i) Fill(dest[i], val); }
template<class T>
T Compare(T left, T right) { return left > right ? 1 : (left < right ? -1 : 0); }
istream& Ignore(istream& ist) { string s; ist >> s; return ist; }
bool Inside(int i, int j, int h, int w) { return i >= 0 && i < h && j >= 0 && j < w; }
// all_of
// partial_sum, adjacent_difference

#ifdef ONLY_MY_ENVIR
#include "IntMod.h"
#include "Union_Find.h"
#include "Graph.h"
#include "Range.h"
#include "Global.h"
#include "Flow_Solver.h"
#include "Tree.h"
#include "Suffix_Array.h"
#include "Geometry.h"
#include "Matrix.h"
#endif

#ifdef __GNUC__
typedef __int128 LLL;
istream& operator>> (istream& ist, __int128& val) { LL tmp;  ist >> tmp; val = tmp; return ist; }
ostream& operator<< (ostream& ost, __int128 val) { LL tmp = val; ost << tmp; return ost; }
#endif

#if 1234567891
#include <array>
#include <random>
#include <unordered_set>
#include <unordered_map>
template<typename T>
using PriorityQ = priority_queue<T, vector<T>, greater<T> >;	// コスト小を優先
#endif

int N;
vector<bool> v;
vector<bool> ans;

int main() {
	cin >> N;
	int prev;
	cin >> prev;
	int cnt = 0;
	int sgn = 0;
	
	REP(i, 1, N) {
		int a;
		cin >> a;
		int diff = a - prev;

		if (sgn == 0) {
			sgn = diff;
		} else if (LL(sgn) * diff < 0) {
			++cnt;
			sgn = 0;
		}
		prev = a;
	}
	cout << cnt + 1 << endl;
	return 0;
}

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

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

    if(b==1)
    {
        printf("0");
        return 0;
    }
    else if(a>=b)
    {
        printf("1");
        return 0;
    }
    else
    {
        ans = 1;
        b = b - a;
        ans += (b+a-2)/(a-1);
        printf("%d", ans);
        return 0;
    }
    
}

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

int main(){
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;
    
    std::string p,q;
    int ans=n;
    
    for(int i=0;i<s.size()-1;++i){
        p=s[i];
        for(int j=i+1;j<s.size();++j){
            q=s[j];
            if(p==q){
                ans--;
                i++;
            } else {
                
                break;
            }
        }
    }
    std::cout << ans << std::endl;
    return 0;
}

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

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

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

  vector<pair<int, int>> item(n);
  rep(i, n) cin >> item.at(i).first >> item.at(i).second;

  vector<vector<int64_t>> dp(n + 1, vector<int64_t>(w + 1));

  for (int i = 0; i < n; i++) {
    int value = item.at(i).second;
    int weight = item.at(i).first;
    for (int sum_w = 0; sum_w <= w; sum_w++) {
      if (sum_w - weight >= 0) {
        chmax(dp.at(i + 1).at(sum_w), dp.at(i).at(sum_w - weight) + value);
      }
      chmax(dp.at(i + 1).at(sum_w), dp.at(i).at(sum_w));
    }
  }

  cout << dp.at(n).at(w) << endl;
  return 0;
}

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

#define inf  1e18
#define int  long long
#define float double
#define endl  "\n"
#define w(t)  int t;cin>>t;while(t--)
#define str  to_string
#define vci  vector<int>
#define vcs  vector<string> 
#define mp   make_pair
#define pb   push_back
#define pii   pair<int,int>
#define pis   pair<int,string>
#define fastio() ios::sync_with_stdio(0);cin.tie(0)
#define mod   1000000007
random_device rd;
mt19937 rand_gen(rd());
#define setbits(x)     __builtin_popcountll(x)
#define trailzero(x)   __builtin_ctzll(x)
#define shuffle(vc) shuffle(vc.begin(), vc.end(), rand_gen);
#define decimal(x,value)  cout<<fixed<<setprecision(x)<<value
void io()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	#ifndef ONLINE_JUDGE
		freopen("/home/kashif/cp/input.txt","r",stdin);
		
		freopen("/home/kashif/cp/output.txt","w",stdout);
	#endif

}
int n;
vector<int*> v;
int a[100001]={0};
int b[100001]={0};
int c[100001]={0};
int dp[3][100001];

int solve(int curr,int day)
{
	int &ans=dp[curr][day];
	if(ans!=-1)
		return ans;
	ans=0;
	if(day==n)
	{
		
		for(int i=0;i<3;i++)
		{
			if(i!=curr)
				ans=max(ans,v[curr][day]);
		}
		
	}
	else
	{
		
		for(int i=0;i<3;i++)
		{
			if(i!=curr)
				ans=max(ans,v[curr][day]+solve(i,day+1));
		}
			
	}
	return ans;



}



int32_t main()
{
	
	fastio();
	//io();
	memset(dp,-1,sizeof(dp));
	v.pb(a);
	v.pb(b);
	v.pb(c);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>v[0][i]>>v[1][i]>>v[2][i];
	}
	int t=solve(0,1);
	int g=solve(1,1);
	int k=solve(2,1);
	cout<<max(max(t,g),k)<<endl;
}


Measured memory_bytes: 16108
#define MOD 1000000007
#include <bits/stdc++.h>
#include <numeric>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

class SegmentTree{
	vector<int> tree;
	int _build(vector<int> &arr,int l,int r,int ind){
		if(l==r){
			return tree[ind]=arr[l];
		}
		else{
			return tree[ind]=max(_build(arr,l,(l+r)/2,2*ind+1),_build(arr,(l+r)/2+1,r,2*ind+2));
		}
	}
	int _update(int loc,int val,int l,int r,int ind){
		if(l==r){
			return tree[ind]=val;
		}
		else if(loc>(l+r)/2){
			return tree[ind]=max(tree[2*ind+1],_update(loc,val,(l+r)/2+1,r,2*ind+2));
		}
		else{
			return tree[ind]=max(_update(loc,val,l,(l+r)/2,2*ind+1),tree[2*ind+2]);
		}
	}
	int _query(int l,int r,int bl,int br,int ind){
		if(r<bl||br<l){
			return -1;
		}
		else if(bl>=l&&br<=r){
			return tree[ind];
		}
		else{
			return max(_query(l,r,bl,(bl+br)/2,2*ind+1),_query(l,r,(bl+br)/2+1,br,2*ind+2));
		}
	}
	public:
	SegmentTree(vector<int> arr){
		tree.resize(4*arr.size());
		_build(arr,0,arr.size()-1,0);
	}
	void Update(int loc,int val){
		_update(loc,val,0,tree.size()/4-1,0);
	}
	int Query(int l,int r){
		return _query(l,r,0,tree.size()/4-1,0);
	}
};
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n,k,maxi=0;
	cin>>n>>k;
	vector<int> a(300001,0);
	SegmentTree t(a);
	a.resize(n);
	for(int i=0; i<a.size(); ++i){
		cin>>a[i];
		int val=t.Query(max(0,a[i]-k),min(300000,a[i]+k));
		maxi=max(maxi,val+1);
		t.Update(a[i],val+1);
	}
	cout<<maxi<<endl;
}


Measured memory_bytes: 10348
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#define debug(x) cerr << #x << ':' << x << endl
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
using namespace std;
typedef long long ll;


bool mach(string s1, string s2){
    // cout << s1 << "|" << s2 << endl;
    if(s1.size()!=s2.size()) return false;
    bool is_ok = true;
    REP(i,s1.size())
        if(!(s1[i]==s2[i]||s2[i]=='?')){
            is_ok=false;
            break;
        }
    return is_ok;
}
int main(){
    string s,t;
    cin >> s >> t;
    int n1 = s.size();
    int n2 = t.size();
    
    string tmp="";
    for(int i=n1-1; 0<=i; i--){
        if(mach(t,s.substr(i,n2))){
            tmp = s.substr(0,i) + t + s.substr(i+n2, n1-i-n2);
            // cout << tmp << endl;
            break;
        }
    }
    if(tmp==""){
        cout << "UNRESTORABLE" << endl;
        return 0;
    }
    else{
        REP(i,n1){
            if(tmp[i]=='?')cout << 'a';
            else cout << tmp[i];
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
#define rep(i,strt,end) for(long long i = strt;i < end;i++)


int main(){
    long long a,b,c,k;
    cin >> a >> b >> c >> k;
    if(k <= a){
        cout << k << endl;
    }else if(k <= (a + b)){
        cout << a << endl;
    }else{
        cout << 2*a+b-k << endl;
    }
    //--------------
    return 0;
}

Measured memory_bytes: 3624
"""
17D8101031C 杉山　祥吾 ID:keisei334 python
"""

def gcd(a,b):
    if a%b==0:
        return b
    else:
        return gcd(b,a%b)

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

print(gcd(x[0],x[1]))

"""実行結果
147 105
21
"""



Measured memory_bytes: 5612
N = int(input())
S = input()

tmp = 0
left = []
for c in S:
    if c == 'W':
        tmp += 1
    left.append(tmp)

tmp = 0
right = []
for c in reversed(S):
    if c == 'E':
        tmp += 1
    right.append(tmp)

right = list(reversed(right))

ans = min(right[0], left[N - 1])

for i in range(1, N - 1):
    ans = min(ans, left[i - 1] + right[i + 1])
print(ans)

Measured memory_bytes: 20384
#include <bits/stdc++.h>
#define FOR(v, a, b) for(int v = (a); v < (b); ++v)
#define FORE(v, a, b) for(int v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(int v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define LLI long long int
#define fst first
#define snd second
#define popcount __builtin_popcount

#ifdef DEBUG
#include <misc/C++/Debug.cpp>
#else
#define dump(x) ((void)0)
#endif

#define gcd __gcd

using namespace std;
template <class T> constexpr T lcm(T m, T n){return m/gcd(m,n)*n;}

template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}
template <typename T, typename U> istream& operator>>(istream &is, pair<T,U> &p){is >> p.first >> p.second; return is;}

template <typename T, typename U> bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);}
template <typename T, typename U> bool chmax(T &a, const U &b){return (a<b ? a=b, true : false);}
template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}

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

  int N,K;
  string S;
  while(cin >> N >> K >> S){
    S[K-1] -= 'A'-'a';
    cout << S << endl;
  }
  
  return 0;
}


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

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

Measured memory_bytes: 256
//**************************
//*** author  :  Alex Hu **
//************************

#include<bits/stdc++.h>

using namespace std;

#define CLEAN(a,b) memset(a,b,sizeof(a))
#define mkp make_pair
#define pb push_back
#define rept(i,a,b) for(int i=(int)(a);i<(int)(b);i++)

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

const int MAX=1e5+5;

int dis[MAX],n,m,ans;
vi v[MAX];

int dfs(int x)
{
	if (dis[x]!=-1) return dis[x];
	int ret=0;
	rept(i,0,v[x].size()) ret=max(ret,dfs(v[x][i])+1);
	return dis[x]=ret;
}

int main()
{
	cin>>n>>m;
	CLEAN(dis,-1);
	rept(i,0,m)
	{
		int x,y;
		cin>>x>>y;
		v[x].pb(y);
	}
	rept(i,1,n+1) ans=max(ans,dfs(i));
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 8832
// by : 信冯哥
#include<bits/stdc++.h>
using namespace std;
const int maxn = (int)1e5+5;
const int mod = (int)1e9+7;
 
typedef long long ll;
#define int ll
 
#define orz cout<<endl
#define debug cout<<"-------------------"<<endl
#define input freopen("in.txt","r",stdin)
#define output freopen("out.txt","w",stdout)
#define sync ios::sync_with_stdio(false)
 
struct st
{
	int ans;
	int id,year;
};
vector<st>opt;
vector<st>p[maxn];
int n,m,k,l,s,t,r;
 
int cmp1(st x,st y)
{
	return x.year<y.year;
}
 
int cmp2(st x,st y)
{
	return x.id<y.id;
}
 
main()
{
 
	scanf("%lld %lld",&l,&n);
	for(int i=1;i<=n;i++)
	{
		st e;
		scanf("%lld %lld",&l,&r);
		e.id=i;
		e.year=r;
		p[l].push_back(e);
		k=max(k,l);
	}
	for(int i=1;i<=k;i++)
		sort(p[i].begin(),p[i].end(),cmp1);
	for(int i=1;i<=k;i++)
		{
			int l=p[i].size();
			for(int j=0;j<l;j++)
				p[i][j].ans=i*(ll)1e6+j+1,opt.push_back(p[i][j]);
		}
	
	sort(opt.begin(),opt.end(),cmp2);
	int l=opt.size();
	for(int i=0;i<l;i++)
		printf("%012lld\n",opt[i].ans);
	return 0;
}

Measured memory_bytes: 10608
n, k = input().split()
ds = input().split()
ns = {_n for _n in n} 
ds = { d for d in ds}

result = 1
while(True):
    rs = {r for r in str(result)}
    if result >= int(n) and len(rs&ds) == 0 :
        print(result)
        break
    else:
        result += 1


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

using namespace std;

#define loop(i,a,b) for(int i=(a); i<(int)(b); i++)
#define rep(i,b) loop(i,0,b)

int main(){
    string s; cin>>s;
    cout<<(s[0]=='x'&&s.back()=='x' ? 'x' : 'o')<< endl;
}

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

int main()
{
	ios_base::sync_with_stdio(false);   
	cin.tie(NULL);
	cout.tie(NULL);
	
	string s;
	cin>>s;
	deque<char> dq;
	for(ll i=0;i<s.length();i++)
	{
		dq.push_back(s[i]);
	}
	ll q;
	cin>>q;
	ll yo=0;
	while(q--)
	{
		ll n;
		cin>>n;
		if(n==1)
		{
			yo++;
		}
		else if(n==2)
		{
			ll m;
			char c;
			cin>>m>>c;
			if(m==1)
			{
				if(yo%2==0)
				{
					dq.push_front(c);
				}
				else
				dq.push_back(c);
				
			}
			else
			{
				if(yo%2!=0)
				{
					dq.push_front(c);
				}
				else
				dq.push_back(c);
			}
			
		}
	}
	if(yo%2==0)
	{
		for(ll i=0;i<dq.size();i++)
		{
			cout<<dq[i];
		}
	}
	else
	{
		for(ll i=dq.size()-1;i>=0;i--)
		{
			cout<<dq[i];
		}
		
	}
	
}

Measured memory_bytes: 976
#include <iostream>
#include <vector>
#define REP(i, n) for(int i = 0; i < (n); i++)

using namespace std;
typedef long long ll;

int main()
{
  int N; cin >> N;
  ll ans = 0;
  REP(i, N) {
    int A; cin >> A;
    while (A % 2 == 0) ans++, A /= 2;
  }
  cout << ans << endl;

  return 0;
}

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

using namespace std;

const int MAXN = 1E5;
int a[MAXN];

long long solve(bool pos, int n)
{
    long long ans = 0;
    long long sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum += a[i];
        if (pos && sum <= 0)
        {
            ans += -sum + 1;
            sum = 1;
        }
        else if (!pos && sum >= 0)
        {
            ans += sum + 1;
            sum = -1;
        }
        pos = !pos;
    }
    return ans;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    cout << min(solve(false, n), solve(true, n)) << endl;

    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int n,m;

int a[1000],b[1000];




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



 

    
 

Measured memory_bytes: 3636
from collections import Counter
N, K, L = [int(i) for i in input().split()]
par = [i for i in range(N)]
rank = [1 for i in range(N)]

def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        pass
    else:
        if rank[x] > rank[y]:
            par[y] = x
            rank[x] += rank[y]
        else:
            par[x] = par[y]
            rank[y] += rank[x]


def find_2(x):
    if par_2[x] == x:
        return x
    else:
        return find_2(par_2[x])

def unite_2(x, y, is_incre=True):
    x = find_2(x)
    y = find_2(y)
    if x == y:
        pass
    else:
        if rank_2[x] > rank_2[y]:
            par_2[y] = x
            if is_incre:
                rank_2[x] += rank_2[y]
        else:
            par_2[x] = par_2[y]
            if is_incre:
                rank_2[y] += rank_2[x]

def is_same(x, y):
    if find(x) == find(y):
        return True
    else:
        return False

def is_same_2(x, y):
    if find_2(x) == find_2(y):
        return True
    else:
        return False

for i in range(K):
    p, q = [int(i)-1 for i in input().split()]
    if is_same(p, q):
        continue
    else:
        unite(p, q)

rank_2 = [1 for i in range(N)]
par_2 = [i for i in range(N)]
for l in range(L):
    r, s = [int(i)-1 for i in input().split()]
    if is_same_2(r, s):
        pass
    else:
        unite_2(r, s)

par_ls = list()
for i in range(N):
    ar = find(i)
    br = find_2(i)
    par_ls.append((ar, br))
ct = Counter(par_ls)

for i in range(N):
    print(ct[par_ls[i]])

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

int abs(int x) {
  return (x < 0 ? -x : x);
}

int main() {
  long long int n;
  cin >> n;
  vector<long long int> aa;

  for (int k = 1; k <= n; k++) {
    long long int t;
    cin >> t;
    aa.push_back(t - k);
  }

  sort(aa.begin(), aa.end());
  long long int median = aa[n / 2];
  //int median = (n % 2 == 0 ? (aa[(n - 1) / 2] + aa[n / 2]) / 2 : aa[(n - 1) / 2]);

  long long int res = 0;
  for (long long int k = 0; k < n; k++) {
    res += abs(aa[k] - median);
  }
  cout << res << endl;
}

Measured memory_bytes: 2420
#include <cstdio>

using namespace std;

int main() {
  int i;
  int N;
  int A[100010];
  int num_odd = 0;
  scanf("%d", &N);
  for (i = 0; i < N; i++) {
    scanf("%d", &A[i]);
    if (A[i] % 2 == 1) {
      num_odd += 1;
    }
  }
  if (num_odd % 2 == 1) {
    printf("NO");
  } else {
    printf("YES");
  }
  return 0;
}


Measured memory_bytes: 512
n=int(input(''))
A=10**9+7
if n==1:
    print(0)
elif n==2:
    print(2)
elif n>=3:
    e=1
    f=1
    g=1
    for i in range(n):
        e=e*10
        f=f*9
        g=g*8
        if e>=A:
           e=e%A
        if f>=A:
            f=f%A
        if g>=A:
            g=g%A

    print((e-f*2+g)%A)

Measured memory_bytes: 9208
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
namespace mp = boost::multiprecision;

int main(){
	int n=1;
	cin >> n;
	double a[n][2];

	for(int i = 0; i<n; i++) {
		for(int j = 0; j<2; j++) {
			cin >> a[i][j];
		}
	}

	double sum = 0;

	for(int i = 0; i<n; i++) {
		for(int j = i+1; j<n; j++) {
			sum += sqrt(pow(a[i][0] - a[j][0], 2) + pow(a[i][1] - a[j][1], 2));
		}
	}

	cout << std::setprecision(10) << sum * 2 / n;

	return 0;
}

int kaijou(int x) {
	int n = 1;
	for(int i = 1; i<x+1; i++) {
		n = n * i;
	}
	return n;
}

Measured memory_bytes: 888
# -*- coding: utf-8 -*-

N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(N)]

def dfs(n, a):
    if n==0:
        if ("A" not in a) | ("B" not in a) | ("C" not in a):
            return 999999999999
        mp=-30
        At=Bt=Ct=0
        for i, ai in enumerate(a):
            if ai=="A":
                At+=l[i]
                mp+=10
            elif ai=="B":
                Bt+=l[i]
                mp+=10
            elif ai=="C":
                Ct+=l[i]
                mp+=10
        mp+=abs(At-A)
        mp+=abs(Bt-B)
        mp+=abs(Ct-C)
        return mp
    
    return min(dfs(n-1, a+"A"), dfs(n-1, a+"B"), dfs(n-1, a+"C"), dfs(n-1, a+"N"))

print(dfs(N, ""))


Measured memory_bytes: 3188
n,a = map(int,input().split())
c = 0
d = 1000
for i in range(1,n+1):
    c+=a+i-1
    d = min(abs(a+i-1),d)
if a<0 and a-n <= 0:
    print(c+d)
else:
    print(c-d)

Measured memory_bytes: 9104
#include <iostream>
#include <vector>
#include <string>

using std::vector;
using std::string;

char flip(char lr) {
  return (lr == 'R') ? 'L' : 'R';
}

int happiness(const string& s) {
  int result = 0;

  for (int i = 0; i < s.length(); ++i) {
    if (s[i] == 'L') {
      if (i > 0 && s[i - 1] == 'L') {
        result++;
      }
    }
    if (s[i] == 'R') {
      if (i < s.length() - 1 && s[i + 1] == 'R') {
        result++;
      }
    }
  }

  return result;
}

int main(int argc, char* argv[]) {
  using std::cin;
  using std::cout;

  int n, k;
  cin >> n >> k;
  std::string s;
  cin >> s;

  // ...RL... source of unhappiness
  // ...RLR... => ...RRR... +2 happiness
  // ...RLLR... => ...RRRR... +2 happiness
  //
  // More than +2 happiness is not possible
  // ...RL...RL... => ...RL...RL... +0
  // ...RL...LL... => ...RR...RL... +0
  // ...RL...RR... => ...RL...RR... +0

  int i = 1;
  char lr = s[0];
  int c = 0;
  while (i < n) {
    if (s[i] == lr) {
      ++i;
      continue;
    }
    int j = i;
    while (j < n - 1 && s[j + 1] == flip(lr)) {
      ++j;
    }

    for (int k = i; k <= j; ++k) {
      s[k] = lr;
    }

    ++c;
    if (c == k) {
      break;
    }

    i = j + 1;
  }

  cout << happiness(s);

  return 0;
}


Measured memory_bytes: 512
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		Dice d = new Dice();
		for(int i = 0; i < 6; i++) {
			d.side[i] = sc.nextInt();
		}
		int q = sc.nextInt();
		for(int i = 0; i < q; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			d.getRightSide(a, b);
		}
		
		sc.close();
	}
}

class Dice {
	int[] side = new int[6];

	public void getUpperSide() {
		System.out.println(this.side[0]);
	}
	public void getRightSide(int a, int b) {
		int[][] mtx = {{0, 3, 5, 2, 4, 0}, {4, 0, 1, 6, 0, 3}, 
{2, 6, 0, 0, 1, 5}, {5, 1, 0, 0, 6, 2}, {3, 0, 6, 1, 0, 4}, {0, 4, 2, 5, 3, 2, 0}};
		int aI = -1;
		int bI = -1;
		for(int i = 0; i < 6; i++) {
			if(a==this.side[i]) {
				aI = i;
			}
			if(b==this.side[i]) {
				bI = i;
			}
			if(aI>=0&&bI>=0) break;
		}
		System.out.println(this.side[mtx[aI][bI] - 1]);
	}

	public void rollE() {
		int w = this.side[5];
		this.side[5] = this.side[2];
		this.side[2] = this.side[0];
		this.side[0] = this.side[3];
		this.side[3] = w;
	}
	public void rollW() {
		int w = this.side[5];
		this.side[5] = this.side[3];
		this.side[3] = this.side[0];
		this.side[0] = this.side[2];
		this.side[2] = w;
	}
	public void rollN() {
		int w = this.side[5];
		this.side[5] = this.side[4];
		this.side[4] = this.side[0];
		this.side[0] = this.side[1];
		this.side[1] = w;
	}
	public void rollS() {
		int w = this.side[5];
		this.side[5] = this.side[1];
		this.side[1] = this.side[0];
		this.side[0] = this.side[4];
		this.side[4] = w;
	}
}


Measured memory_bytes: 26184
tem1=input().split()
N = int(tem1[0])
K = int(tem1[1])
tem2 = input().split()
jud = [0 for i in range(len(tem2))]
now =1
circle=0
for i in range(0,K):
    if jud[now-1]==0:
        jud[now-1]=i
        now = int(tem2[now - 1])
    else:
        circle=i-jud[now-1]
        fact=(K-i-1)%circle
        for j in range(0,fact+1):
            now = int(tem2[now - 1])
        break

print(now)

Measured memory_bytes: 30804
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Integer> list = new ArrayList<Integer>();
        int limit = Integer.parseInt(scanner.next());
        for (int i = 0; i < limit; i++) {
            for (int j = 0; j < 3; j++) {
                list.add(Integer.parseInt(scanner.next()));
            }
            Collections.sort(list);
            Collections.reverse(list);
            int a = list.get(0);
            int b = list.get(1);
            int c = list.get(2);
            double cosA = getCosA(a, b, c);
            if (cosA == 0.0) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
            list.clear();
        }
    }

    private static double getCosA(int a, int b, int c) {
        return (Math.pow(b, 2) + Math.pow(c, 2) - Math.pow(a, 2)) / (2 * b * c);
    }
}

Measured memory_bytes: 22088
a = int(input())
b = int(input())
c = int(input())
x = int(input())

# 全部最大値からスタートしたほうがシンプルな気がする

coins_number_list = [a,b,c]
buf_coins_number_list = [a,b,c]
all_patterns_list =[]


# コインの合計値を求める関数
def sum_coins(coins_list):
  return coins_list[0] * 500 + coins_list[1] * 100 + coins_list[2] * 50


while(True):
  while(True):
    while(True):
      all_patterns_list.append(list(buf_coins_number_list))
      buf_coins_number_list[2] = buf_coins_number_list[2] - 1
      if buf_coins_number_list[2] < 0:
        break

    buf_coins_number_list[2] = c
    buf_coins_number_list[1] = buf_coins_number_list[1] - 1
    if buf_coins_number_list[1] < 0:
      break
  buf_coins_number_list[1] = b
  buf_coins_number_list[0] = buf_coins_number_list[0] - 1
  if buf_coins_number_list[0] < 0:
    break



all_patterns_sum_list = list(map(sum_coins, all_patterns_list))


print(all_patterns_sum_list.count(x))

Measured memory_bytes: 26080
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define repeat(i, k, j) for(int i=(k); i < (int)(j); i++)
template<class T> bool set_min(T &a, const T &b) { return a > b  ? a = b, true : false; }
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
const int INF = 1 << 30;

class Solver {
  public:
    bool solve() {
        int N, K; cin >> N >> K;
        vector<int> H(N); cin >> H;

        vector<int> dp(N, INF);
        dp[0] = 0;
        rep(i, N) {
            repeat(k, 1, K + 1) {
                if(i + k < N) set_min(dp[i + k], dp[i] + abs(H[i + k] - H[i]));
            }
        }
        cout << dp[N - 1] << endl;
        return 0;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    Solver s;
    s.solve();
    return 0;
}


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

void strss(char *p,int psize){
    for(int i=0;i<psize;i++){
        if(p[i]>='A'&&p[i]<='Z'){
            int u=p[i]-'A';
            p[i]='a'+u;
        }
    }
    
}


int main(){
    string t;
    cin>>t;
    strss(&t[0],t.size());
    //cout<<t;
   string com;
    int ans=0;
    //com[0]=' ';
    while(true){
        string tcom;
        cin>>tcom;
        if(tcom=="END_OF_TEXT")break;
        strss(&tcom[0],tcom.size());
        if(tcom==t)ans++;
        com+=tcom;
    }
    cout<<ans<<endl;;
    
    return 0;
    
}


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

int main(){
	int n;
	cin>>n;
	int b[n];
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		b[x]=i;	
	}
	for(int i=1;i<=n;i++){
		cout<<b[i]<<' ';
	}
}

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

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

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

int main() {
  int n, d;
  cin >> n >> d;
  int ans = (n + 2*d + 1 - 1)/(2*d + 1);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b;
  cin >> a >> b;
  int x;
  x = a * b % 2;
   if(x == 1){
    cout << "Odd" << endl;
  }
  else{
    cout << "Even" << endl;
  }
}

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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)-form-)

#ifdef YANG33
#include "mydebug.hpp"
#else
#define DD(x) 
#endif

const int INF = 1e9;
int N;
VI A;

int f(int pre, bool p) {
	int res;
	if (!p) {
		res = -INF;
		FOR(i, pre + 1, N + 1) {
			if (i == N) {
				res = max(res, abs(A[N] - A[pre]));
			}
			else {
				res = max(res, f(i, !p));
			}
		}
	}
	else {
		res = INF;
		FOR(i, pre + 1, N + 1) {
			if (i == N) {
				res = min(res, abs(A[N] - A[pre]));
			}
			else {
				res = min(res, f(i, !p));
			}
		}
	}
	return res;
}
const LL LINF = 1e18;

int main() {

	int N, Z, W; cin >> N >> Z >> W;
	VL A(N + 1);
	A.front() = W;
	for (int i = 0; i < N; ++i) {
		cin >> A[i + 1];
	}
	VVL memo(N, VL(2, LINF));
	function<LL(int, bool)> f = [&](int pre, bool p) {
		if (memo[pre][p] != LINF)return memo[pre][p];
		LL res;
		if (!p) {
			res = -LINF;
			FOR(i, pre + 1, N + 1) {
				if (i == N) {
					DD(de(A[N], A[pre], N, pre));
					res = max(res, abs(A[N] - A[pre]));
				}
				else {
					res = max(res, f(i, !p));
				}
			}
		}
		else {
			res = LINF;
			FOR(i, pre + 1, N + 1) {
				if (i == N) {
					DD(de(A[N], A[pre], N, pre));
					res = min(res, abs(A[N] - A[pre]));
				}
				else {
					res = min(res, f(i, !p));
				}
			}
		}
		return memo[pre][p] = res;

	};
	LL res = f(0, 0);
	cout << res << endl;
}

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

using namespace std;

#define N 500

struct Event{
	int xi, yi, xf, yf;

	Event(){}

	Event(int xi, int yi, int xf, int yf){
		this->xi = xi;
		this->yi = yi;
		this->xf = xf;
		this->yf = yf;
	}
};

int a[N + 1][N + 1];
vector<Event> ans;

int main(){
	int n, m, i, j;

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

	for (i = 1; i <= n; i++){
		for (j = 1; j <= m; j++){
			scanf("%d", a[i] + j);
		}
	}

	for (i = 1; i <= n;){
		for (j = 1; j < m; j++){
			if (a[i][j] % 2){
				a[i][j]--;
				a[i][j + 1]++;
				ans.push_back(Event(i, j, i, j + 1));
			}
		}

		i++;

		if (i > n){
			break;
		}

		if (a[i - 1][m] % 2){
			a[i - 1][m]--;
			a[i][m]++;
			ans.push_back(Event(i - 1, m, i, m));
		}

		for (j = m; j > 1; j--){
			if (a[i][j] % 2){
				a[i][j]--;
				a[i][j - 1]++;
				ans.push_back(Event(i, j, i, j - 1));
			}
		}

		i++;

		if (i > n){
			break;
		}

		if (a[i - 1][1] % 2){
			a[i - 1][1]--;
			a[i][1]++;
			ans.push_back(Event(i - 1, 1, i, 1));
		}
	}

	printf("%d\n", (int)ans.size());

	for (i = 0; i < (int)ans.size(); i++){
		printf("%d %d %d %d\n", ans[i].xi, ans[i].yi, ans[i].xf, ans[i].yf);
	}

	return 0;
}

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

int X;

int main()
{
    cin >> X;
    int sum = 0;
    for (int i = 1;; i++)
    {
        sum += i;
        if (sum >= X)
        {
            cout << i << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())


int n, m;
vector<int> edge[100000];

int memo[100000];

int dfs(int u) {
	if (memo[u] != -1)return memo[u];
	int ret = 0;
	for(int v: edge[u]) {
		ret = max(ret, 1 + dfs(v));
	}
	return memo[u] = ret;
}


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

	cin >> n >> m;
	rep(i,m) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		edge[x].push_back(y);
	}
	memset(memo, -1, sizeof(memo));

	int ans = 0;
	rep(i,n) {
		ans = max(ans, dfs(i));
	}
	cout << ans << endl;


	
	return 0;
}


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

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

  for (int i = 0; i < N; i++) {
    string S;
    cin >> S;
    
    if(S == "Y"){
      cout << "Four" << endl;
      break;
    }
    else if(i == N - 1){
      cout << "Three" << endl;
    }
  }
  
}


Measured memory_bytes: 256
/*给一棵树，x和y博弈，首先x在u点，y在v点，游戏结束条件是x和y重合，
x先动，x希望游戏更晚结束dist(p,u)要大，y希望游戏更早结束，
求y在游戏结束前走的步数 设游戏在p点结束，那么dist(p,u)≤dist(p,v)显然成立，
dist(p,u)<dist(p,v)等同于x掉头等待y  大于就不会在p点相遇 
或者可以讲Y会继续前行等待x 
所以要取满足条件的max(dist(p,v))即可。
*/
#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
vector<int>g[100000];
int n, u, v, a, b, ans;
int du[100000], dv[100000];

//Graph ? std::vector<int> v[100]; 100 verices
void dfs(int x, int y, int z) {
	dv[x] = z;
	for (int i = 0; i < g[x].size(); i++) {
		if (g[x][i] != y)dfs(g[x][i], x, z + 1);
	}
}

int main() {
  scanf("%d%d%d", &n, &u, &v);
	u--; v--;
	for (int i = 0; i < n - 1; i++) {
		scanf("%d%d", &a, &b);
		a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}

dfs(u, -1, 0);
for (int i = 0; i < n; i++)du[i] = dv[i];
dfs(v, -1, 0);
for (int i = 0; i < n; i++) {
  if (dv[i] >du[i]) {//早走1步 
    if (dv[i] > ans)ans = dv[i];
  }
}
printf("%d\n", ans - 1);

  return 0;
}


Measured memory_bytes: 11648
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
ll x[100000];
int nxt[31][100001];
int main() {
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) cin >> x[i];
	ll L;
	cin >> L;
	for (int i = 0; i <= 30; i++) nxt[i][N] = N;
	nxt[0][N - 1] = N;
	for (int i = 0; i + 1 < N; i++) {
		nxt[0][i] = upper_bound(x, x + N, x[i] + L) - x - 1;
	}
	for (int i = 0; i < 30; i++) {
		for (int j = 0; j < N; j++) {
			nxt[i + 1][j] = nxt[i][nxt[i][j]];
		}
	}
	int Q;
	cin >> Q;
	for (int i = 0; i < Q; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		if (a > b) swap(a, b);
		int now = a;
		ll ans = 0;
		for (int j = 30; j >= 0; j--) {
			if (nxt[j][now] <= b) {
				now = nxt[j][now];
				ans += (1LL << j);
			}
		}
		if (now < b) ans++;
		cout << ans << endl;
	}
}


Measured memory_bytes: 13696
import java.util.*;
import java.util.HashSet;
import java.util.Set;
public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        int A=sc.nextInt();
        int B=sc.nextInt();
        int C=sc.nextInt();
        int D=sc.nextInt();
        int E=A*B;
        int F=C*D;
        if(E>=F){
            System.out.println(E);
        }else{
            System.out.println(F);
        }

        

        }
       
        
    }

Measured memory_bytes: 25556
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 5001;
int dp[N][N];
vector<vector<int>> adj;
int n;
int G[N];
int sz[N];

int solve(int u, int p = -1){
  sz[u] = 1;
  dp[u][1] = 1;
  for(auto el : adj[u]){
    if(el != p){
      solve(el, u);
      ll tmp[sz[u] + sz[el] + 1];
      memset(tmp, 0, sizeof(tmp));
      for(int i = 1;i <= sz[u];i++){
        for(int j = 1;j <= sz[el];j++){
          tmp[i + j] = (tmp[i + j] + 1ll * dp[el][j] * dp[u][i] % MOD) % MOD;
          if(j % 2 == 0)
            tmp[i] = ((tmp[i] - 1ll * dp[el][j] * dp[u][i] % MOD * G[j] % MOD) % MOD + MOD) % MOD;
        }
      }
      sz[u] += sz[el];
      for(int i = 0;i <= sz[u];i++)
        dp[u][i] = tmp[i];
    }
  }
}
int main()
{
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
  cin >> n;
  adj.resize(n);
  for(int i = 0;i < n - 1;i++){
    int u, v;
    scanf("%d %d", &u, &v);
    u--, v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
//  solve(0);
//  return 0;
  G[0] = 1;
  for(int i = 2;i < N;i += 2)
    G[i] = 1ll * (i - 1) * G[i - 2] % MOD;
//  for(int i =1 ;i < 10;i++){
//    cout << G[i] << endl;
//  }
  solve(0);
//cout << sz[0]<< endl;
  ll res = 0;
  for(int i = 1;i <= n;i++){
//    cout << dp[0][i] << endl;
    res += 1ll * dp[0][i] * G[i] % MOD;
    res %= MOD;
  }
  cout << res;
  return 0;
}


Measured memory_bytes: 97536
#include<bits/stdc++.h>
// #include <atcoder/all>
#define ll long long int
#define rep(i,n) for(ll i=0;i<n;i++)
#define vec vector<ll>
#define mat vector<vector<ll>>

using namespace std;
// using namespace atcoder;

const ll mod=1000000007;//998244353;
const ll inf=LONG_LONG_MAX;
ll dx4[4]={1,0,-1,0};
ll dy4[4]={0,-1,0,1};
ll dx8[8]={1,0,-1,1,-1,1,0,-1};
ll dy8[8]={1,1,1,0,0,-1,-1,-1};

int main(){

  ll n,m;
  cin >> n >> m;
  vec a(n);
  for(ll i=0;i<n;i++)cin >> a[i];

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

  ll l=1,r=2*100000;
  ll h;
  while(abs(r-l)>1){
    h=(r+l)/2;
    ll s=0;
    for(ll i=0;i<n;i++){
      ll p=upper_bound(a.begin(),a.end(),h-a[i])-a.begin();
      // if(i<=p)p=2*(n-p)-1;
      // else p=2*(n-p);
      p=n-p;
      s+=p;
      //cout << p << endl;
    }
    if(s>=m)l=h;
    else r=h;
  }
  h=r;//これをこえる握手がm個未満なhで最小のもの

  vec b(n);//各a[i]を何回足すか
  ll s=0;
  for(ll i=0;i<n;i++){
    ll p=upper_bound(a.begin(),a.end(),h-a[i])-a.begin();
    p=2*(n-p);
    //if(a[i]*2>h)p--;
    b[i]=p;
    s+=p;
    //cout << p << endl;
  }

  ll ans=0;
  for(ll i=0;i<n;i++)ans+=a[i]*b[i];
  //cout << s << endl;
  ans+=(m-s/2)*h;

  cout << ans << endl;

  //cout << h << endl;
  

  return 0;
}

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

int main()
{
    int n, m, x;
    cin >> n >> m >> x;
    vector<int> a(m);
    rep(i, m) cin >> a.at(i);

    int to_zero_cost = 0, to_n_cost = 0;
    rep(i, m)
    {
        if (a.at(i) < x)
        {
            to_zero_cost++;
        }
        else
        {
            to_n_cost++;
        }
    }

    cout << min(to_zero_cost, to_n_cost) << endl;
}

Measured memory_bytes: 256
N=int(input())
A=list(map(int,input().split()))
from functools import reduce
from math import gcd
g=reduce(lambda x,y:gcd(x,y),A,0)
if g>1:
    print('not coprime')
    exit()
def prime(N):
    p=set(range(2,N+1))
    for i in range(int(N**.5)+1):
        if i in p:
            p-=set(range(i*2,N+1,i))
    return p
p=prime(1000)
r=1
s=set()
for a in A:
    f=0
    for x in p:
        if a%x==0:
            if f==0:
                p2=p.copy()
                f=1
            p2.remove(x)
        while a%x==0:
            a//=x
        if a==1:
            break
    if a>1:
        if 1000<a and a not in s:
            s.add(a)
        else:
            r=0
            break
    if f:
        p=p2
print(['setwise coprime','pairwise coprime'][r])

Measured memory_bytes: 197484
from collections import deque


def submit():
    h, w = map(int, input().split())
    board = [input() for _ in range(h)]

    white = 0
    for i in range(h):
        for j in range(w):
            if board[i][j] == ".":
                white += 1
    
    q = deque()
    q.appendleft((0, 0))
    dist = {(i, j): -1 for i in range(h) for j in range(w)}
    dist[(0, 0)] = 1
    while len(q):
        x, y = q.pop()
        d = dist[(x, y)]
        if (x, y) == (h - 1, w - 1):
            break

        if 0 <= x - 1 and dist[(x - 1, y)] < 0 and board[x - 1][y] == '.':
            dist[(x - 1, y)] = d + 1
            q.appendleft((x - 1, y))
        if x + 1 < h and dist[(x + 1, y)] < 0 and board[x + 1][y] == '.':
            dist[(x + 1, y)] = d + 1
            q.appendleft((x + 1, y))
        if 0 <= y - 1 and dist[(x, y - 1)] < 0 and board[x][y - 1] == '.':
            dist[(x, y - 1)] = d + 1
            q.appendleft((x, y - 1))
        if y + 1 < w and dist[(x, y + 1)] < 0 and board[x][y + 1] == '.':
            dist[(x, y + 1)] = d + 1
            q.appendleft((x, y + 1))

    if dist[(h - 1, w - 1)] < 0:
        print(-1)
    else:
        print(white - dist[(h - 1, w - 1)])

    
submit()

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

#define _GLIBCXX_DEBUG
#define all(v) (v).begin(),(v).end()

using namespace std;

using ll=long long;
using pii=pair<int, int>;
using vi=vector<int>;
using vii=vector<vector<int>>;

const ll LINF=1LL<<60;
const int INF=1<<29;
const int MOD=1e9+7;

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

int main(){
    int R, C, K; cin >> R >> C >> K;
    map<pii, int> mp;
    for(int i=0; i<K; i++){
        int r, c, v;
        cin >> r >> c >> v;
        r--, c--;
        mp[{r, c}]=v;
    }

    vector<vector<vector<ll>>> dp(R, vector<vector<ll>>(C, vector<ll>(4, 0)));
    if(mp.count({0, 0})) dp[0][0][1]=mp[{0, 0}];
    for(int x=0; x<R; x++){
        for(int y=0; y<C; y++){
            int px, py;
            for(int i=0; i<=3; i++){
                px=x, py=y-1;
                if(py < 0) continue;
                if(mp.count({x, y}) && i > 0){
                    chmax(dp[x][y][i], dp[px][py][i-1]+mp[{x, y}]);
                }
                chmax(dp[x][y][i], dp[px][py][i]);
            }
            px=x-1, py=y;
            if(px < 0) continue;
            if(mp.count({x, y})){
                for(int i=0; i<=3; i++){
                    chmax(dp[x][y][1], dp[px][py][i]+mp[{x, y}]);
                }
            }
            else{
                for(int i=0; i<=3; i++){
                    chmax(dp[x][y][0], dp[px][py][i]);
                }
            }
        }
    }
    ll ans=0;
    for(int i=0; i<=3; i++) ans=max(ans, dp[R-1][C-1][i]);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 648936
#include <iostream>
#include <set>
#include <cctype>
#include <vector>

using namespace std;

string S;

bool is_op(char c)
{
    return (c == '+' || c == '-' || c == '*' || c == '/');
}

bool is_num(int L, int R)
{
    for (int i = L; i <= R; i++) {
        if (!isdigit(S[i])) return 0;
    }
    return 1;
}

int num(int L, int R)
{
    int res = 0;
    for (int i = L; i <= R; i++) {
        res *= 10;
        res += (S[i] - '0');
    }
    return res;
}

int near(int L, int R)
{
    int p = 0;
    for (int i = L; i <= R; i++) {
        if (S[i] == '(') p++;
        if (S[i] == ')') p--;
        if (p == 0) return i;
    }
    return -1;
}

set<int> expr(int L, int R)
{
    set<int> res;
    
    if (is_num(L, R)) return {num(L, R)};
    
    int nR = near(L, R);
    if (nR == R && S[L] == '(' && S[R] == ')') {
        return expr(L + 1, R - 1);
    }
    
    for (int i = L; i <= R - 1; i++) {
        char c = S[i];
        
        if (!is_op(c)) continue;        
        
        auto l = expr(L, i - 1);
        auto r = expr(i + 1, R);
        
        for (int lv : l) {
            for (int rv : r) {
                switch (c) {
                    case '+':
                        res.insert(lv + rv);
                        break;
                    case '-':
                        res.insert(lv - rv);
                        break;
                    case '*':
                        res.insert(lv * rv);
                        break;
                    case '/':
                        if (rv != 0) {
                            res.insert(lv / rv);                            
                        }                            
                        break;
                }
            }
        }
    } 
    return res;
}

void solve()
{
    int N = S.size();
    cout << expr(0, N - 1).size() << endl;
}

int main()
{
    while (cin >> S, S != "#") {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3180