akhauriyash/Code-Regression huggingface dataset:
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000000000000
#define MOD 1000000007
typedef pair<int, int> P;

bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int mod_pow(int n, int p, int m) {
	if (p == 0) return 1;
	if (p % 2 == 0) {
		int t = mod_pow(n, p / 2, m);
		return (t * t) % m;
	}
	return n * mod_pow(n, p - 1, m) % m;
}
int extGCD(int a, int b, int& x, int& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
int digit(int x) {
	int cnt = 0;
	while (x > 0) {
		cnt += x % 10;
		x /= 10;
	}
	return cnt;
}
int read() {
	int tmp;
	cin >> tmp;
	return tmp;
}
int xor128() {
	static int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
	int t = (x xor (x << 11));
	x = y; y = z; z = w;
	return (w = (w xor (w >> 19)) xor (t xor (t >> 8)));
}

signed main() {
	int n;
	cin >> n;
	cout << (n - 1) * n / 2 << endl;
		
	return 0;
}


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

#define ll long long
#define mod 1000000007

using namespace std;



int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios_base::sync_with_stdio(false);
//    cin.tie(NULL);
    ll t,c=0;
    cin>>t;
    if(t>=400&&t<=599)cout<<8<<endl;
    if(t>=600&&t<=799)cout<<7<<endl;
    if(t>=800&&t<=999)cout<<6<<endl;
    if(t>=1000&&t<=1199)cout<<5<<endl;
    if(t>=1200&&t<=1399)cout<<4<<endl;
    if(t>=1400&&t<=1599)cout<<3<<endl;
    if(t>=1600&&t<=1799)cout<<2<<endl;
    if(t>=1800&&t<=1999)cout<<1<<endl;
}


Measured memory_bytes: 3620
#include <stdio.h>

int main(){

  int x, y;
  while(1){
        scanf("%d %d", &x, &y);
        if(x == 0 && y == 0){break;}

        if(x > y){
          printf("%d %d\n", y, x);
        }else{
          printf("%d %d\n", x, y);
        }
  }

  return 0;
}


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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string a;
    cin >>a;
    int nie=0;
    if (a[0] == a[1] && a[1] == a[2]){
            cout << "Yes";
    return 0;}
    if (a[1] == a[2] && a[2] == a[3]){
            cout << "Yes";
    return 0;}
    cout <<"No";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
struct Edge {
  ll to;
  ll cost;
};
int main() {
  ll N, K;
  cin >> N >> K;
  vector<int> a(N + 1);
  vector<int> ov(2010);
  REP(i, N) {
    cin >> a[i + 1];
    ov[a[i + 1]]++;
  }
  REP(i, 2005) { ov[i + 1] += ov[i]; }
  ll tenti = 0;
  for (int i = 1; i <= N; i++) {
    ll tmp = 0;
    tmp = (K * (K - 1)) / 2 % MOD;
    tmp *= ov[a[i] - 1];
    tmp %= MOD;
    tenti += tmp;
    tenti %= MOD;
    ll k = 0;
    for (int j = i + 1; j <= N; j++) {
      if (a[i] > a[j]) k++;
    }
    tenti += (k * K) % MOD;
    tenti %= MOD;
  }
  cout << tenti << endl;
}

Measured memory_bytes: 3636
#include<stdio.h>
int main(){
    char s[4];
    int ans;
    scanf("%s",s);
    if(s[0]=='S'&&s[1]=='U') printf("7");
    if(s[0]=='M'&&s[1]=='O') printf("6");
    if(s[0]=='T'&&s[1]=='U') printf("5");
    if(s[0]=='W'&&s[1]=='E') printf("4");
    if(s[0]=='T'&&s[1]=='H') printf("3");
    if(s[0]=='F'&&s[1]=='R') printf("2");
    if(s[0]=='S'&&s[1]=='A') printf("1");
    return 0;
}

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

int main(){
  int w,h,x,y,r;
  cin>>w>>h>>x>>y>>r;
  if(0 <= x-r && x+r <= w && 0 <= y-r && y+r <=h)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
  return 0;
}


Measured memory_bytes: 3116
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
const int mod=998244353;
const int N=2008;
char s[N];
int n; 
int nr[N*2],nb[N*2];
int f[N*2][N*2],ans;
IL void upd(int &x,int y)
{
	x+=y;
	if(x>=mod)	x-=mod;	
}
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;++i){
		int t=0,p=0;
		if(s[i]=='0')	t=2,p=0;
		else if(s[i]=='1')	t=1,p=1;
		else	t=0,p=2;
		nr[i]=nr[i-1]+t;	
		nb[i]=nb[i-1]+p;
	}
	for(int i=n+1;i<=n+n;++i){
		nr[i]=nr[n];
		nb[i]=nb[n];	
	}
	for(int i=1;i<=n+n;++i){
	//	cout<<"!!"<<i<<' '<<nr[i]<<' '<<nb[i]<<'\n';	
	}
	f[0][0]=1;
	for(int i=0;i<n+n;++i){
		for(int j=0;j<=i;++j){
			//cout<<i<<' '<<j<<' '<<f[i][j]<<'\n';
			if(nr[i+1]>j){
				upd(f[i+1][j+1],f[i][j]);
			}	
			if(nb[i+1]>i-j){
				upd(f[i+1][j],f[i][j]);	
			}
		}
	}
	for(int j=0;j<=n+n;++j){
		upd(ans,f[n+n][j]);	
	}
	printf("%d",ans);
	return 0;
}


Measured memory_bytes: 61568
n, k = map(int, input().split())
d = [0] * (10 ** 5 + 10)
for _ in range(n):
    a, b = map(int, input().split())

    d[a] += b
for i in range(len(d)):
    k -= d[i]
    if k <= 0:
        print(i)
        break

Measured memory_bytes: 45912
#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>;


int N;

void calc_sum(int n, ll sum, vector<vector<int>> &tree, vector<ll> &cnt, vector<ll> &ans, vector<bool> &seen) {
    seen.at(n) = true;
    ans.at(n) = sum + cnt.at(n);
    for (auto x : tree.at(n)) {
        if (!seen.at(x)) calc_sum(x, ans.at(n), tree, cnt, ans, seen);
    }
}

int main() {
    int Q, a, b, p, x;
    cin >> N >> Q;
    vector<vector<int>> tree(N);
    vector<bool> seen(N);
    vector<ll> cnt(N), ans(N);
    rep(i,N-1) {
        cin >> a >> b;
        --a;
        --b;
        tree.at(a).push_back(b);
        tree.at(b).push_back(a);
    }
    rep(i,Q) {
        cin >> p >> x;
        --p;
        cnt.at(p) += x;
    }
    calc_sum(0, 0, tree, cnt, ans, seen);
    rep(i,N) cout << ans.at(i) << " ";
}


Measured memory_bytes: 35948
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define DEBUG true
#ifdef ONLINE_JUDGE
#undef DEBUG
#define DEBUG false
#endif 

using namespace std;

#define MAXN ((int)4e5+5)
#define MOD ((int)1e9 + 7)
#define INF ((int)1e9 + 9)
#define ll long long
#define _ << " " <<
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define TRACE(x) if(DEBUG) cerr << #x << " = " << x << endl;
#define TRACE2(x,y) if(DEBUG) cerr << #x << " = " << x << " | " << #y << " = " << y << endl;
#define LOG(x) if(DEBUG) cerr << x << endl;
#define pb push_back
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pii pair<int,int>
#define mid ((l+r)/2)

ll fac[MAXN];
ll inv[MAXN];
ll ans;
ll n,k;

ll modInverse(ll a)
{
	ll m = MOD;
	ll y = 0, x = 1;
	if (m == 1)
		return 0;
	while (a > 1)
	{
		ll q = a / m;
		ll t = m;
		m = a % m, a = t;
		t = y;
		y = x - q * y;
		x = t;
	}
	if (x < 0)
		x += MOD;
	return x;
}

void precalc()
{
	fac[0] = 1;
	for (int i = 1; i < MAXN; ++i)
	{
		fac[i] = (fac[i-1] * i) % MOD;
		// TRACE(fac[i]);
	}

	inv[0] = 1;
	for (int i = 1; i < MAXN; ++i)
	{
		inv[i] = modInverse(fac[i]);
		// TRACE(inv[i]);
	}
}

ll C(ll a, ll b)
{
	ll res = 1;

	res = (res * fac[a]) % MOD;
	res = (res * inv[b]) % MOD;
	res = (res * inv[a-b]) % MOD;

	return res;
}

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);
	
	cin >> n >> k;
	k = min(k,n-1);
	precalc();

	for (int i = k; i >= 0; i--)
	{
		// TRACE(C(n,i));
		// TRACE(C(n-1, n-1-i));
		ans += (C(n,i) * C(n-1, n-1-i));
		ans %= MOD;
	}

	cout << ans << endl;

}

Measured memory_bytes: 6528
object Main extends App {
  import scala.io.StdIn._
  println(
    (0 until readLine.trim.toInt).map(_ ⇒ readLine.trim.split(' ').map(_.toInt)).let{a ⇒ a.indices.map(i ⇒ (0 until 3).filter(j ⇒ a.map(_(j)).count(_ == a(i)(j)) == 1).map(j ⇒ a(i)(j)).sum).mkString("\n")}
  )
  implicit class ScopeFunc[T](val value: T){
    def let[A](func: T ⇒ A): A = func(value)
    def also(func: T ⇒ Unit): T = {
      func(value)
      value
    }
  }
}


Measured memory_bytes: 46372
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int main() {
	char map[1002][1002];
	int H, W;
	cin >> H >> W;
	for (int i = 0; i <= W + 1; ++i) {
		map[i][0] = '.';
		map[i][H + 1] = '.';
	}
	for (int i = 0; i <= H + 1; ++i) {
		map[0][i] = '.';
		map[W + 1][i] = '.';
	}
	for (int y = 1; y <= H; ++y) {
		for (int x = 1; x <= W; ++x) {
			cin >> map[x][y];
		}
	}
	queue<pair<short,short> > stock;
	short movex[]{ 0,1,1,1,0,-1,-1,-1 }, movey[]{ 1,1,0,-1,-1,-1,0,1 };
	for (int y = 1; y <= H; ++y) {
		for (int x = 1; x <= W; ++x) {
			int count=0;
			if (map[x][y] != '.'&&map[x][y] != '?') {
				for (int i = 0; i < 8; ++i) {
					if (map[x + movex[i]][y + movey[i]] == '.') {
						++count;
					}
				}
				if ('0' >= (map[x][y] = map[x][y] - count)) {
					stock.push(pair<short, short>(x, y));
					map[x][y] = '?';
				}
			}
		}
	}
	int answer = 0;
	pair<short, short> dummy;
	queue<pair<short,short> > date;
	while (!stock.empty()) {
		++answer;
		while (!stock.empty()) {
			dummy = stock.front();
			stock.pop();
			for (int i = 0; i < 8; ++i) {
				if (map[dummy.first + movex[i]][dummy.second + movey[i]] != '.'&&map[dummy.first+movex[i]][dummy.second+movey[i]]!='?') {
					if (--map[dummy.first + movex[i]][dummy.second + movey[i]] == '0') {
						date.push(pair<short, short>(dummy.first + movex[i], dummy.second + movey[i]));
						map[dummy.first + movex[i]][dummy.second + movey[i]] = '.';
					}
				}
			}
		}
		swap(date, stock);
	}
	cout << answer << endl;
	return 0;
}

Measured memory_bytes: 4124
#define DEBUG 1
#include <bits/stdc++.h>
#define loop(n) for (lint ngtkana_is_a_genius = 0; ngtkana_is_a_genius < lint(n); ngtkana_is_a_genius++)
#define rep(i, begin, end) for (lint i = lint(begin); (i) < lint(end); i++)
#define all(v) v.begin(), v.end()
#define rand(l, r) std::uniform_int_distribution<>(l, r)(mt)
using lint = long long;
auto mt = std::mt19937_64(std::random_device{}());
auto cmn = [](auto&& a, auto b){ if (a > b) {a = b; return true;} return false; };
auto cmx = [](auto&& a, auto b){ if (a < b) {a = b; return true;} return false; };
void debug_impl() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_impl(Head head, Tail... tail) { std::cerr << " " << head; debug_impl(tail...); }
#if DEBUG
#define debug(...)\
  do {\
    std::cerr << std::boolalpha << "[" << #__VA_ARGS__ << "]:";\
    debug_impl(__VA_ARGS__);\
    std::cerr << std::noboolalpha;\
  } while (false)
#else
#define debug(...) {}
#endif

int main() {
  std::cin.tie(0); std::cin.sync_with_stdio(false);
  int k, x; std::cin >> k >> x;
  bool ans = k * 500 >= x;
  std::cout << (ans ? "Yes" : "No") << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,a,b,p[5050],dy[5050];
long long dp[5050][5050],ans=0x3f3f3f3f3f3f3f3f;
int main()
{
	scanf("%d %d %d",&n,&a,&b);
	for(int i=1;i<=n;++i)scanf("%d",&p[i]),dy[p[i]]=i;
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	for(int i=1;i<=n;++i)
	{
		long long mi=0x3f3f3f3f3f3f3f3f;
		for(int j=0;j<=n;++j)
		{
			mi=min(mi,dp[i-1][j]);
			dp[i][j]=min(dp[i][j],mi+(j>=dy[i]?a:b));
			if(j+1==dy[i])dp[i][j+1]=min(dp[i][j+1],mi);
		}
	}
	for(int i=0;i<=n;++i)ans=min(ans,dp[n][i]);
	printf("%lld",ans);
	return 0;
}


Measured memory_bytes: 199424
_a = input()
_b = input()
_c = input()
a = [_a[i] for i in range(len(_a))]
b = [_b[i] for i in range(len(_b))]
c = [_c[i] for i in range(len(_c))]

turn = "a"
while True:
    if turn == "a":
        if len(a) == 0:
            print("A")
            exit()
        else:
            turn = a[0]
            del a[0]
    elif turn == "b":
        if len(b) == 0:
            print("B")
            exit()
        else:
            turn = b[0]
            del b[0]
    elif turn == "c":
        if len(c) == 0:
            print("C")
            exit()
        else:
            turn = c[0]
            del c[0]

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i < (ll)(n); i++)
const ll mo = 1000000007;
const ll INF = 1LL << 60; //MAX 9223372036854775807
ll ans = 0;

int main()
{
ll n;
cin >> n;
ll t[n] = {};
ll a=-10;
rep(i, n)
{
    cin >> t[i];
    t[i]--;
    if(i==t[i]&&a!=i-1)a=i;
    else if(i==t[i]&&a==i-1){ans++;a=-10;}
    else if(a==i-1){ans++;a=-10;}
}
if(a!=-10)ans++;
cout << ans << endl;
return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
 
 
int main()
{
  char s[1000000],t[1000000];
  scanf("%s%s",s,t);
  
  char *ptrs,*ptrt;
  ptrs = s;
  ptrt = t;
  
  int cnt = 0;
  while(*ptrs != '\0')
  {
    if(*ptrs!=*ptrt)
    {
      cnt++;
    }
    ptrs++;
    ptrt++;
  }
  printf("%d\n",cnt);
  return 0;
}

Measured memory_bytes: 2132
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstdint>
using namespace std;

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

int main () {

    int N;
    cin >> N;
    set < string > used;

    char c = '?';
    REP(i,N) {
        string s;
        cin >> s;

        if (used.find(s) != used.end()) {
            cout << "No" << endl;
            return 0;
        }

        used.insert(s);
        if (c == '?') {
            c = s.back();
        } else {
            if (s.front() != c) {
                cout << "No" << endl;
                return 0;
            } else {
                c = s.back();
            }
        }
    }

    cout << "Yes" << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define mod 998244353

using namespace std;
typedef pair<llint, llint> P;

llint n, m, k;

const int FACT_MAX = 600005;
llint fact[FACT_MAX], fact_inv[FACT_MAX];

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

void make_fact()
{
	llint val = 1;
	fact[0] = 1;
	for(int i = 1; i < FACT_MAX; i++){
		val *= i;
		val %= mod;
		fact[i] = val;
	}
	fact_inv[FACT_MAX-1] = modpow(fact[FACT_MAX-1], mod-2);
	for(int i = FACT_MAX-2; i >= 0; i--){
		fact_inv[i] = fact_inv[i+1] * (i+1) % mod;
	}
}

llint comb(llint n, llint k)
{
	llint ret = 1;
	ret *= fact[n];
	ret *= fact_inv[k], ret %= mod;
	ret *= fact_inv[n-k], ret %= mod;
	return ret;
}

llint divide(llint n, llint k)
{
	
	n -= k;
	return comb(n+k-1, n);
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	make_fact();
	
	cin >> n >> m >> k;
	
	llint ans = 0;
	for(int i = 0; i <= k; i++){
		llint tmp = divide(n, n-i);
		tmp *= m * modpow(m-1, n-i-1) % mod;
		tmp %= mod;
		ans += tmp, ans %= mod;
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 13012
#include <iostream>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define lli long long int
using namespace std;
#define S second
#define F first
#define pb push_back 
#define M1 1000000007
#define M2 998244353
#define plli pair<lli,lli>
#define setit set<lli>::iterator seti
#define mapit map<lli,lli> ::iterator mapi
#define MP make_pair
#define MT make_tuple
// map      iterator->first  iterator.first
// map      mp[key]=value
// set      *s.begin()
// vector   v[j]=value
// pair     p.first p.second
// vector of pairs v[j].first v[j].second
// tuple    get<index>(tuple_name)
// vector of tuples get<index>(v[j])  sort(v.begin(),v.end())
//priority queue .top() .pop() .push()
// __gcd(x,y)
#define mini(x,y) (y + ((x - y) & ((x - y) >>(sizeof(int) * CHAR_BIT - 1))))
#define maxi(x,y) (x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))))
#define fr(j,a,b) for(j=a;j<b;j++)

int power(int x, unsigned int y, int p)  
{    int res = 1;    
     x = x % p;
     if (x == 0) return 0;
     while (y > 0)  
     {  if (y & 1)  
        res = (res*x) % p;  
        y = y>>1;
        x = (x*x) % p;  
     }  
    return res;  
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    lli t,i,j,n,x,k;string s;
    cin>>k>>s;
    n=s.length();
    if(k>=n){
        cout<<s;
    }
    else{
        for(i=0;i<k;i++){cout<<s[i];}
        cout<<"...";
    }
}


Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
typedef long double lld;
#define mod 1000000007
#define mod2 998244353
#define fori(n) for (int i = 0; i < n; i++)
#define forj(n) for (int j = 0; j < n; j++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl "\n"
#define sortvec(a) sort(a.begin(), a.end())
#define watch(x) cerr << "\n" << (#x) << " is " << (x) << endl
#define cerr if(true)cerr
void print(){cout<<endl;}
template<typename T,typename... Args>
void print(T a, Args... args) {cout<<a<<" ";print(args...);}
lli llipowerp(lli x, lli y, lli p=LLONG_MAX)
{
    lli res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1) res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
lli binarySearch(vector<int> arr, int l, int r, int x)
{
    if (r >= l)
    {
        lli mid = l + (r - l) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}
template <typename T>
inline void printvec(vector<T> inp){
    for(auto it:inp) cout<<it<<" ";
    cout << endl;
}
//---------------------------------------------------------------------------------
int dp[(int)1e5+10];
int n,m;
vector<vector<int>> adj;
int fill(int nr){
    
    if(dp[nr]!=-1) return dp[nr];
    
    if(adj[nr].size()==0){
        dp[nr]=0;
        return 0;
    }
    int maxlen=0;
    for(auto i:adj[nr]){
        maxlen=max(maxlen,fill(i));
    }
    dp[nr]=1+maxlen;
    return dp[nr];
}

int main()
{   
    cin>>n>>m;
    adj.resize(n+1);
    int u,v;
    memset(dp,-1,sizeof(dp));

    fori(m){
        cin>>u>>v;
        adj[u].pb(v);
                
    }
    int ans=0;
    fori(n+1) {
        ans=max(ans,fill(i));
        //cout<<fill(i)<<endl;
    }
    cout<<ans<<endl;

    
}

Measured memory_bytes: 8192
#include<iostream>
#include<algorithm>
#include<set>
using lint=int64_t;
using namespace std;

int main()
{
	int N;
	int index[200010]={};
	set<int> s;

	cin >> N;
	for(int i=1;i<=N;i++)
	{
		int a;
		cin >> a;
		index[a]=i;
	}

	s.insert(0);
	s.insert(N+1);
	lint ans=0;
	for(int i=1;i<=N;i++)
	{
		int mid=index[i];
		auto itr=s.lower_bound(mid);
		lint l,r;
		r=*itr;
		--itr;
		l=*itr;

		ans+=i*((mid-l)*(r-mid));
		s.insert(index[i]);
	}

	cout << ans << endl;

	

	return 0;
}


Measured memory_bytes: 10496
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); i++)
#define all(x) (x).begin(), (x).end()
#define bit(x) (1L << (x))
using ll = long long;
using namespace std;

template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
 
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
        return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}

int main() {
        int n;
        string s;
        cin >> n >> s;

        vector<int> a(n);
        auto d = make_v(3, n + 1, 0);
        for (int i = 0; i < n; i++) {
                if (s[i] == 'R') a[i] = 0;
                else if (s[i] == 'G') a[i] = 1;
                else a[i] = 2;

                rep (j, 3) {
                        if (j == a[i]) {
                                d[j][i + 1] = d[j][i] + 1;
                        } else {
                                d[j][i + 1] = d[j][i];
                        }
                }
        }

        ll ans = 0;
        rep(i, n) for (int j = i + 1; j < n; j++) {
                if (a[i] == a[j]) continue;
                int x = 3 - (a[i] + a[j]); 

                int t = d[x][n] - d[x][j + 1];
                if (2 * j - i < n && a[2 * j - i] == x) {
                        t--;
                }

                ans += t;
        }

        cout << ans << endl;

        return 0;
}


Measured memory_bytes: 3652
#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>;
ll mod = 1000000007;
const int inf = 2147483647;
const ll MAX_N = 201000;
const ll MAX_W = 200100;

/*************ここから**********************/
class union_find{
public: 
    ll N;
    ll par[MAX_N];
    ll rank[MAX_N];
 
 
    union_find(void){init();};
    union_find(ll n):N(n){init();}
    void init(){
        for(int i=0;i<N;i++){
            par[i] = i;
            rank[i] = 0;
        }
    }
    //xの始点を探す
    ll find(ll x){
        if(par[x] == x){
            return x;
        }else{
            return par[x] = find(par[x]);
        }
    }
    //グループを結合
    void unite(ll x,ll y){
        x = find(x);
        y = find(y);
        if(x == y) return;
        if(rank[x]>rank[y]){
            par[y] = x;
        }
        else if(rank[x]<rank[y]){
            par[x] = y;
        }else{
            par[x] = y;
            rank[x]++;
        }
    }
    //始点の親が同じか
    bool same(int x,int y){
        return find(x) == find(y);
    }
    //引数xの含まれるグループを表示
    void print_tree(int x){
        string str;
        str = "{";
        for(int i=0;i<N;i++){
            if(same(x,i)){
              str = str + to_string(i) + ",";
            }
        }
        str[str.size()-1] = '}';
        cout << str << endl;
    }
    //すべてのグループを表示
    void print_all(void){
        vector<bool> is_printed(N,false);
        for(int i=0;i<N;i++){
            if(!is_printed[i]){
                print_tree(i);
                for(int j=0;j<N;j++){
                    if(same(i,j)) is_printed[j] = true;
                }
            }
        }
        return;
    }
};

/**************ここまで*************************/
int main(void){
    ll n,m; cin >> n >> m;
    union_find uf(n);
    rep(i,m) {
        ll a,b;cin >> a >> b;
        a--;b--;
        uf.unite(a,b);
    }
    ll group[200010];
    for(int i=0;i<n;i++){
        group[uf.find(i)]++;
    }
    ll ans = 0;
    for(int i=0;i<n;i++){
        ans = max(ans,group[i]);
    }
    cout << ans << endl;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1

ll mod_add(ll a, ll b) { return (a + b) % MOD; }
ll mod_sub(ll a, ll b) { return (a - b + MOD) % MOD; }
ll mod_mul(ll a, ll b) { return a*b % MOD; }

ll n;

ll calc(string s){
    ll res = 0;
    ll num = (s[0] - '0')*10+(s[1] - '0');
    res += num *3600;
    num = (s[3] - '0')*10+(s[4] - '0');
    res += num *60;
    num = (s[6] - '0')*10+(s[7] - '0');
    res += num;
    return res;
}

int main(){
    while(cin >> n && n){
        vector<ll> sum(24*3600+1,0);
        rep(i,n){
            string s,t;
            cin >> s >> t;
            sum[calc(s)]++;
            sum[calc(t)]--;
        }
        rep(i,sum.size()-1)sum[i+1] += sum[i];
        ll ans = 0;
        rep(i,sum.size())ans = max(ans,sum[i]);
        cout << ans << endl;
    }
}


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

using namespace std;
typedef uint64_t u64;
typedef int64_t i64;
typedef double db;

int main() {
  i64 N, M;
  cin >> N >> M;
  vector<i64> successed(N), failed(N);
  for (int i = 0; i < M; i++) {
    int p;
    string s;
    cin >> p >> s;
    if (s[0] == 'A') {
      successed[p-1] = 1;
    } else {
      failed[p-1] += (1 - successed[p-1]);
    }
  }
  for (int i = 0; i < N; i++) {
    failed[i] *= successed[i];
  }
  cout << accumulate(successed.begin(), successed.end(), 0) << ' '
       << accumulate(failed.begin(), failed.end(), 0)
       << endl;
}


Measured memory_bytes: 4808
#include<iostream>
#include<algorithm>
using lint=int64_t;
using namespace std;

int main()
{
	int N,A,B;
	
	cin >> N >> A >> B;
	
	if((B-A)%2==0)
		cout << "Alice";
	else 
		cout << "Borys";
	cout << endl;	
	return 0;
}



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

int x[3000];
int y[3000];
int main(){

	
	for (int n = 0; n <= 2999; n++){
	cin >> x[n] >> y[n];
		if (x[n] == 0 && y[n] == 0) break;

		
		if (x[n] <= y[n]) cout << x[n]<<" "<< y[n]<<endl;
		else if (y[n] <= x[n]) cout << y[n]<<" " << x[n] << endl;
	
	
	
	
	
	}
	


	return 0;
}



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

int main() {
  int a; cin >> a;
  cout << a + a*a + a*a*a << endl;
  return 0;
}

Measured memory_bytes: 3632
#include <stdio.h>

int main(int argc, const char * argv[]) {
    int n, m;
    int A[100][100];
    int B[100];
    int h, w, C[100] = { 0 };
    scanf("%d %d", &n, &m);
    for (h = 0; h<n; h++)
    {
        for (w = 0; w<m; w++)
        {
            scanf("%d", &A[h][w]);
        }
    }
    for (w = 0; w<m; w++)
    {
        scanf("%d", &B[w]);
    }
    for (h = 0; h < n; h++)
    {
        for (w = 0; w < m; w++)
        {
            C[h] += A[h][w] * B[w];
        }
    }
    for (h = 0; h<n; h++)
    {
        printf("%d\n", C[h]);
    }
    
    return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int max(int i, int j){
        if (i > j){
                return i;
        }else{
                return j;
        }
}
int main(void){
        int N;
        scanf("%d", &N);
        int H;
        int x[N];
        int y[N];
        int h[N];
        int tmp;
        for (int i = 0; i < N; i++) {
                scanf("%d %d %d", &x[i], &y[i], &h[i]);
        }
        for (int i = 0; i < N; i++) {
                if (h[i] != 0) tmp = i;
        }

        for (int i = 0; i < 101; i++) {
                for (int j = 0; j < 101; j++) {
                                H = abs(i - x[tmp]) + abs(j - y[tmp]) + h[tmp];
                        for (int k = 0; k < N; k++) {
                                if (h[k] != max(0,H-abs(i-x[k])-abs(j-y[k]))) break;
                                if (k == N - 1){
                                        printf("%d %d %d\n",i,j,H);
                                }

                        }
                }
        }


}

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


int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  int N;
  cin>>N;
  int A[N],dp[N];
  for(int i = 0;i<N;i++) cin>>A[i];
  dp[0] = 0; dp[1] = abs(A[1] - A[0]);
  for(int i = 2;i<N ; i++){
  	dp[i] = min(dp[i-1] + abs(A[i] - A[i-1]),dp[i-2] + abs(A[i] - A[i-2]));
  }
  cout<<dp[N-1];
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define REP(i, n) FOR(i, 0, n)
#define INF 999999999
typedef long long ll;
using namespace std;
int main() {
    int N, A;
    cin >> N >> A;
    if(A >= (N %= 500)) puts("Yes");
    else puts("No");
}

Measured memory_bytes: 256
from functools import reduce

N = int(input())
T = [int(input()) for i in range(N)]


def gcd_base(a, b):
    while b:
        a, b = b, a % b
    return a


def gcd(numbers):  # "numbers" is list
    return reduce(gcd_base, numbers)


def lcm_base(a, b):
    return (a * b) // gcd_base(a, b)


def lcm(numbers):  # "numbers" is list
    return reduce(lcm_base, numbers,
                  1)  # [third argument] return 1 if "numbers" is empty


print(lcm(T))

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double pi =acos(-1.0);
const int maxn=2e5+5;
int mysqrt(ll x){
	ll l=1,r=1e10;
	while(l<r){
		ll mid=(l+r)>>1;
		if(mid*mid<x)l=mid+1;
		else r=mid;
	}
	return l;
}

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

    int x1,x2,y1,y2;
    x1=y2=mysqrt(s);

    x2=1;
    y1=1ll*x1*y2-s;

    cout<<0<<' '<<0<<' '<<x1<<' '<<y1<<' '<<x2<<' '<<y2<<endl;



	return 0;
}



Measured memory_bytes: 3604
#include <bits/stdc++.h>
#define rep(i, N) for(int (i) = 0; (i) < (N); (i)++)


int main(){

    int X, Y, Z; std::cin >> X >> Y >> Z; X -= 2 * Z;

    int ans = (X - Y) / (Y + Z) + 1;

    std::cout << ans;

    system("pause");

    return 0;
}

Measured memory_bytes: 504
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pcc pair<char,char>
#define vi vector <int>
#define vl vector <ll>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d",x)
#define plld(x) printf("%lld",x)
#define pds(x) printf("%d ",x)
#define pllds(x) printf("%lld ",x)
#define pdn(x) printf("%d\n",x)
#define plldn(x) printf("%lld\n",x)
using namespace std;
ll multiply(ll num1, ll num2, ll mod) { // with mod > 1e9
	ll ans = 0;
	num1 %= mod;
	num2 %= mod;
	while (num2) {
		if (num2&1) {
			ans += num1;
			ans %= mod;
		}
		num1 *= 2;
		num1 %= mod;
		num2 /= 2;
	}
	return ans;
}
ll powmod2(ll base,ll exponent,ll mod){ // with mod > 1e9
	ll ans = 1;
	while (exponent) {
		if (exponent&1) {
			ans = multiply(ans, base, mod);
		}
		base = multiply(base, base, mod);
		exponent /= 2;
	}
	return ans;
}
ll powmod(ll base,ll exponent,ll mod){ // with mod < 1e9
	ll ans=1;
	while(exponent){
		if(exponent&1)ans=(ans*base)%mod;
		base=(base*base)%mod;
		exponent/=2;
	}
	return ans;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b,a%b);
}
const int upperlimit = 1e6+100;
const int mod = 1e9+7;
int main() {
	int k;
	sd(k);
	ll ans=k;
	ans++;
	ans/=2;
	ans*=k/2;
	plld(ans);
	return 0;
}

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

int top, cpp[1000];
void push(int s)
{
	cpp[++top] = s;
}
int pop()
{
	
	return cpp[top--];
}

int main()
{
	int n, i;
	char c[3];
	top = 0;
	while (cin >> c)
	{
		if (c[0] == '+')
		{
			n = pop();
			i = pop();
			push(n + i);
		}
		else if (c[0] == '-')
		{
			n = pop();
			i = pop();
			push(i - n);
		}
		else if (c[0] == '*')
		{
			n = pop();
			i = pop();
			push(n * i);
		}
		else push(atoi(c));
	}
	cout << pop() << endl;
	return 0;
}


Measured memory_bytes: 3092
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>

#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
using namespace std;

int main() {
  int n,temp;
  cin >> n;
  std::vector<int> v;
  std::vector<int> w;

  int count = n;
  for (size_t i = 0; i < count; i++) {
    cin >> temp;
    v.push_back(temp);
  }
  copy(v.begin(), v.end(), back_inserter(w) );
  VSORT(v);
  int mid_max = v[(count+1)/2];
  int mid_min = v[(count-1)/2];
  for (size_t i = 0; i < count; i++) {
    if (mid_max == mid_min) cout << mid_max << endl;
    else if (mid_max <= w[i]) cout << mid_min << endl;
    else cout << mid_max << endl;
  }
}


Measured memory_bytes: 3828
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int,int > ii;
typedef pair< long long int ,long long int > iil;
typedef long long ll;
typedef vector< ll > vl;
const ll MOD = 1e9+7,MAX = 1e5;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for( auto i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define EE '\n'
#define ll long long int
#define forn(i,n) for ( int i=0 ; i<n ; i++ )
#define fornl(i,n) for(ll i=0;i<n;i++)
#define forni(i,j,n) for ( int i=j ; i<n ; i++ )
#define PI 3.14159265
#define g(a,b) a>b?a:b
#define l(a,b) a<b?a:b
#define SOT(A) sort(A.begin(),A.end())
#define SOTR(A) sort(A.rbegin(),A.rend())

//////////////////Sieve////////////////////
vector<bool> is_prime(MAX+1, true);
void Sieve()
{
	is_prime[0] = is_prime[1] = false;
	int i,j;
	for (i = 2; i*i <= MAX; i++) 
	{
    	if (is_prime[i]) 
    	{
        	for (j = i * i; j <= MAX; j += i)
            	is_prime[j] = false;
    	}
	}
}
//////////////////Sieve////////////////////



int main(){
    int t=1;
    //cin>>t;
    forn(term,t){
        ll x,y,z;
        cin>>x>>y>>z;
        cout<<z<<" "<<x<<" "<<y<<endl;
    }
}






Measured memory_bytes: 256
#include <iostream>
#include <math.h>

using namespace std;

typedef long long ll;

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

const int MOD = 1e9+7;
const int MAX = 1e5+10;

ll fac[MAX];  /// fac[n] = n!
ll finv[MAX]; /// (fac[n] * finv[n]) % MOD = 1
ll inv[MAX];  /// (n * inv[n]) % MOD = 1

void init() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  FOR (i, 2, MAX) {
    fac[i] = fac[i-1]*i % MOD;
    inv[i] = MOD - inv[MOD%i]*(MOD/i) % MOD;
    finv[i] = finv[i-1]*inv[i] % MOD;
  }
}

ll nCk (int n, int k) {
  if (n < k || k < 0 || n < 0) return 0;
  return fac[n]*finv[k]%MOD*finv[n-k]%MOD;
}

ll nHk (int n, int k) {
  return nCk(n-1+k, n-1);
}

ll factorial(ll n) {
  if (n < 0) return 1;
  return fac[n];
}

ll N;

ll value(ll n) {
  ll res = factorial(n);
  (res *= factorial(N-n-1)) %= MOD;
  (res *= nHk(N-n, n+1)) %= MOD;
  return res;
}

int main() {
  init();

  cin >> N;
  ll r = 0, ans = 0;
  REP (i, N) (r += value(i)) %= MOD;

  REP (i, N) {
    ll a;
    cin >> a;
    (ans += a*r)%=MOD;
    if ((i+1) *2 == N) {} // 偶数の中央
    else if ((i+1)*2 < N) // 左半分
      (r += MOD + value(i+1) - value(N-i-1)) %= MOD;
    else                  // 右半分
      (r += MOD - value(N-i-1) + value(i+1)) %= MOD;
  }

  cout << ans << endl;
}

Measured memory_bytes: 2560
n = int(input())
x = input()
num = 0
count = 0
for i in range(n):
    if x[-(i+1)] == "1":
        num += 2**i
        count += 1

mod = [[0, 0] for _ in range(n)]
mod[0][0] = 1%(count-1) if count!=1 else 0
mod[0][1] = 1%(count+1)
for i in range(1, n):
    if mod[i-1][0] != 0:
        mod[i][0] = (mod[i-1][0]*2)%(count-1)
    if mod[i-1][1] != 0:
        mod[i][1] = (mod[i-1][1]*2)%(count+1)
mod1 = num%(count-1) if count!=1 else 0
mod2 = num%(count+1)

table = [0]*(2*10**5+10)
for i in range(2*10**5+10):
    _num = i
    while True:
        _count = 0
        for c in bin(_num):
            if c == "1":
                _count += 1
        if _num == 0:
            break
        _num %= _count
        table[i] += 1

ans = [0]*n
for i in range(n):
    if x[-(i+1)] == "1":
        _num = num-2**i
        if _num == 0:
            continue
        _num = (mod1-mod[i][0])%(count-1)
    else:
        _num = num+2**i
        _num = (mod2+mod[i][1])%(count+1)
    ans[i] = 1+table[_num]
for i in range(n):
    print(ans[-(i+1)])

Measured memory_bytes: 107168
A=int(input())
B=int(input())
C=int(input())
X=int(input())
count=0
for i in range(0,A+1):
    for j in range(0,B+1):
      for k in range(0,C+1):
        value=i*500+j*100+k*50
        if value==X: count+=1
print(count)

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

int main(){
  long N, D;
  cin >> N >> D;

  int num = 0;
  long p, q;
  for(int i = 0; i < N; i++)
  {
    cin >> p >> q;
    if(p*p+q*q <= D*D)
    {
      num++;
    }
  }
  
  cout << num << endl;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
/// TONI BO$$ was here
/// #MLC

using namespace std;

char v[101];

int main()
{
    int i,n,k;
    scanf("%d%d\n%s",&n,&k,v+1);
    v[k]=v[k]-'A'+'a';
    for(i=1; i<=n; i++)
        putchar(v[i]);

    return 0;
}


Measured memory_bytes: 256
#define rep(i, m, n) for(int i = m; i < n; i++)
#define repM(i, m, n) for(int i = n-1; i>=m; i--)
#define all(x) (x).begin(),(x).end()
typedef long long ll; using namespace std;
//typedef pair<int,int> pii;
// d = distance(lower_bound(all(x)), upper_bound(all(x)));
int INF = 1e9;
int M = 1e9+7;
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

int main(){
  int N, K; cin >> N >> K; if (N==1) {cout << 0 << endl; return 0;}
  string s; cin >> s;
  int c=0;
  for(int i=0; i<N-1; i++) {
    if (s[i] != s[i+1]) c++;
  }
  cout << min(N-1, N-1-c+2*K) << endl;
}

Measured memory_bytes: 512
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <stdio.h>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#define rep(i,a,n) for(ll i =(a);i<(n);++i)
#define urep(i,a,n) for(ll i = (a);i>=(n);--i)
#define all(x) (x).begin(),(x).end()
#define INF 1e18
const int mod = 1e9 + 7;
typedef long long ll;
using namespace std;
ll dx[4] = { 1,-1,0,0 };
ll dy[4] = { 0,0,1,-1 };
ll N,M,X,Y,A,B,C,Q,K,R,W,H,P,L;
string S,T;
ll y[101010];
ll a[101010];
ll b[101010];
ll t[101010];
ll p[101010];
ll n[101010];
ll l[101010];
ll gcd(ll a, ll b) {
	if (b == 0)return a;
	else return gcd(b, a%b);
}
struct Edge{
	ll to,cost;
	 Edge(ll to, ll cost) : to(to), cost(cost) {}
};
typedef vector<vector<Edge> > AdjList;
AdjList graph;
vector<ll> dist;

struct UnionFind {
    vector<ll> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
	vector<ll> size;
    UnionFind(ll N) : par(N),size(N) { //最初は全てが根であるとして初期化
        for(ll i = 0; i < N; i++) par[i] = i;
		for(ll i = 0; i < N; i++) size[i] = 1;
    }

    ll root(ll x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }
	ll GetSize(ll x){
		return size[root(x)];
	}

    void unite(ll x, ll y) { // xとyの木を併合
        ll rx = root(x); //xの根をrx
        ll ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
		size[ry]+=size[rx];

    }

    bool same(ll x, ll y) { // 2つのデータx, yが属する木が同じならtrueを返す
        ll rx = root(x);
        ll ry = root(y);
        return rx == ry;
    }
};

int main() {
    cin>>N;
    vector<ll> c(N);
    vector<ll> x(202020);
    vector<ll> v;
    v.resize(202020);
    vector<ll> ans(N);
    ans[0]=0;
    rep(i,0,N){
        cin>>c[i];
        if(i!=0){
            if(c[i]!=c[i-1]){
                ans[i]=ans[i-1]+v[c[i]];
                v[c[i]]+=1+ans[i-1];
                ans[i]%=mod;
            }else{
                ans[i]=ans[i-1];
            }
        }else{
            v[c[i]]++;
        }
    }
    cout<<(ans[N-1]+1)%mod<<endl;
	return 0;
}


Measured memory_bytes: 6528
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,s;
int main(){
	cin>>a>>b>>c;
	if(b<a&&b<=c)
		cout<<-1<<endl;
	else if(a<=b)
		cout<<1<<endl;
	else{
		if((a-b)%(b-c)>=1)
			s=1;
		cout<<((a-b)/(b-c)+s)*2+1<<endl; 
	}
	return 0; 
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

long int  ksdp(long int  cap, long int* val, long int* wt, long int  n){
	long int  dp[n+1][cap+1];
	//start from 0,0
	for(long int  i=0;i<n+1;i++){
		for(long int  j=0; j<cap+1;j++){
			if(j==0||i==0)
				dp[i][j]=0;
			
			else if(j-wt[i-1]<0)
				dp[i][j] = dp[i-1][j];
				
			else
				dp[i][j] = max(dp[i-1][j], val[i-1] + dp[i-1][j-wt[i-1]]);
		}
	}
	return dp[n][cap];
}




int main(){

	long int n, cap, tempval, tempw;
	
	cin>>n;
	cin>>cap;
	
	
	long int  val[n];
	long int  wt[n];
	
	
	for (long int  i=0;i<n;i++){
	
	
		cin>>tempw;
		cin>>tempval;
		
		wt[i] = tempw;
		val[i] = tempval;
		
	} 
	
	cout<<ksdp(cap, val, wt, n)<<endl;
	
	return 0; 
	
}

Measured memory_bytes: 79104
/* ???????????? */

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

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

  int64 sq = 1;
  while(sq < N) sq *= 2;

  int64 ret = N;
  for(int64 i = sq; i > 0; i >>= 1) {
    const int64 head = (N + i - 1) / i * i;
    const int64 rev_width = i / 2;
    if(head - N <= 0) continue;
    ret = min(ret, head - N);

  }
  cout << ret << endl;


}

Measured memory_bytes: 3080
#include <iostream>

using namespace std;

int n,u,k,v;
int a[101][101]={};

int main()
{
    cin >> n;
    for(int i=0;i<n;i++)
    {
        cin >> u >> k;
        u-=1;
        for(int j=0;j<k;j++)
        {
            cin >> v;
            v-=1;
            a[u][v]=1;
        }
    }
    for(int i=0;i<n;i++)
    {
        cout << a[i][0];
        for(int j=1;j<n;j++)
        {
            cout << " " << a[i][j];
        }
        cout << endl;
    }
    return 0;
}


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

int main(){
    int N;  cin >> N;
    int S = 0;
    int mod = 998244353;
    vector<int> a(N+1,0);
    for(int i=1; i<=N; i++){
        cin >> a[i];
        S += a[i];
    }
    vector<vector<ll>> dp1(N+1, vector<ll>(S+1,0));
    dp1[0][0] = 1;
    for(int i=1; i<=N; i++){
        for(int r=0; r<=S; r++){
            dp1[i][r] = 2*dp1[i-1][r]%mod;
            if(r>=a[i]) dp1[i][r] = (dp1[i][r] + dp1[i-1][r-a[i]]) % mod;
        }
    }
    
	vector<vector<ll>> dp2(N+1, vector<ll>(S+1,0));
	dp2[0][0] = 1;
	for(int i=1; i<=N; i++){
		for(int r=0; r<=S; r++){
			dp2[i][r] = dp2[i-1][r]%mod;
			if(r>=a[i]) dp2[i][r] = (dp2[i][r] + dp2[i-1][r-a[i]]) % mod;
		}
	}

    ll ans = 1;
    for(int i=0; i<N; i++){
        ans = (ans*3)%mod;
    }
    for(int r=S/2+1; r<=S; r++){
        ans = ans - 3*dp1[N][r];
        while(ans<0) ans += mod;
        ans%=mod;
    }
    if(S%2==0){
        ans = ans - 3*dp1[N][S/2];
    	while(ans<0) ans += mod;
    	ans = (ans + 3*dp2[N][S/2]) % mod;
    }
    cout << ans << endl;
}


Measured memory_bytes: 423744
#include <iostream>


using namespace std;


int  T1, T2;
long long  A1, A2, B1, B2;



int main()
{

	cin >> T1;
	cin >> T2;
	cin >> A1;
	cin >> A2;
	cin >> B1;
	cin >> B2;


	long long C1 = A1 - B1;
	long long C2 = A2 - B2;

	long long tx = C1 * T1;
	long long bx = tx + C2 * T2;

	if (bx == 0) {
		cout << "infinity" << endl;
		return 0;
	}

	if ( !((tx > 0) ^ (bx > 0))) {
		cout << 0 << endl;
		return 0;
	}

	long long int ans = ((-tx) / bx) * 2 + 1;
  
	if ((-tx) % bx == 0) { ans--; }

	cout << ans << endl;

	return 0;


}

Measured memory_bytes: 256
import math
A, B, H, M = [float(s) for s in input().split(" ")]

def deg2rad(deg):
  return deg * math.pi / 180.0

th1 = deg2rad(M * 360.0 / 60)
th2 = deg2rad(((H % 12) + M / 60.0) * 360.0 / 12)

c2 = A**2 + B**2 - 2.0 * A * B * math.cos(th1 - th2)

print(math.sqrt(c2))

Measured memory_bytes: 9244
#include <stdio.h>

int main(void)
{
	int n;
	int pm, pe, pj;
	int i;
	
	while (scanf("%d", &n) != EOF){
		if (n == 0){
			break;
		}
		for (i = 1; i <= n; i++){
			scanf("%d %d %d", &pm, &pe, &pj);
			if (pm == 100 || pe == 100 || pj == 100){
				printf("A\n");
			}
			else if ((pm + pe) / 2 >= 90){
				printf("A\n");
			}
			else if ((pm + pe + pj) / 3 >= 80){
				printf("A\n");
			}
			else if ((pm + pe + pj) / 3 >= 70){
				printf("B\n");
			}
			else if ((pm + pe + pj) / 3 >= 50 && pm >= 80 || pe >= 80){
				printf("B\n");
			}
			else {
				printf("C\n");
			}
		}
	}
	
	return (0);
}

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

typedef long long int ll;
typedef pair<int, int> pii;
bool R(){return true;}
template<typename T, typename ... Args>
bool R(T & x, Args & ... args){return cin >> x && R(args...);}
void init_io(){ios::sync_with_stdio(false);cin.tie(0);}

#define PB push_back
#define FOR(prom, a, b) for(int prom = (a); prom < (b); prom++)
#define FORDE(prom, a, b) for(int prom = (a); prom >= (b); prom--)
#define ALL(vec) (vec).begin(), (vec).end()
#define MM(co, cim) memset((co), (cim), sizeof((co)))
#define DEB(x) cerr << ">>> " << #x << " : " << x << endl;
#define INF   1000000007
#define INFLL 4000000000000000007LL

int n, numd[10000014];

void init_divc ()
{
  MM(numd, 0);
  FOR(i, 1, 10000001) for (int j = i; j <= 10000000; j += i) ++numd[j];
}

void solve ()
{
  init_divc();
  R(n);
  ll res = 0;
  FOR(k, 1, n + 1) res += 1LL * k * numd[k];
  printf("%lld\n", res);
}

int main ()
{
  init_io();
  int T = 1;
  //R(T);
  while (T--) solve();
  return 0;
}


Measured memory_bytes: 42824
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return(a)

N,X=map(int,input().split())
x_list=list(map(int,input().split()))

#x_list.append(X)
x_list_new=sorted(x_list)
x_list_new_dif=[abs(x_list_new[i]-X) for i in range(len(x_list_new))]

for i in range(len(x_list_new_dif)):
    if i==0:
        skip=x_list_new_dif[0]
    else:
        skip=gcd(skip,x_list_new_dif[i])
print(skip)

Measured memory_bytes: 14224