akhauriyash/Code-Regression huggingface dataset:
#include<algorithm>
#include<cmath>
#include<climits>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()

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

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

	string S;
	cin >> S;

	int wcnt = 0;
	int bcnt = 0;

	rep(i, N)
	{
		if (S[i] == '.') wcnt++;
	}

	int cost = wcnt;
	char prev = '.';
	
	rep(i, S.size())
	{
		if (prev != S[i])
		{
			//左側・・・黒を白くする
			//右側・・・白を黒くする
			chmin(cost, bcnt + wcnt);
		}

		if (S[i] == '#')
			bcnt++;
		else
			wcnt--;

		prev = S[i];
	}

	chmin(cost, bcnt);

	cout << cost << endl;

	return 0;
}

Measured memory_bytes: 640
//
/*==========================================================*/
/*    Template ver 2017-0720    |    Created by JollyBee    */
/* DOMINUS pascit me, et nihil mihi deerit (Psalmorum 23:1) */
/*==========================================================*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vii;
const double EPS=(double)1e-9;
const double PI=(double)acos(-1.0);
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define FOR(i,n) for(int i=0;i<n;i++)
#define REPP(i,l,r,c) for(int i=l;i<=r;i+=c)
#define REP(i,l,r) REPP(i,l,r,1)
#define FORD(i,n) for(int i=n-1;i>=0;i--)
#define REVV(i,l,r,c) for(int i=l;i>=r;i-=c)
#define REV(i,l,r) REVV(i,l,r,1)
//random
int irand(int lo, int hi){
    return (((double)rand())/(RAND_MAX+1.0)) * (hi-lo+1) + lo;
}
//ll to string
string toString(ll x) {
    stringstream ss;
    ss << x;
    return ss.str();
}
//string to ll
ll toNumber(string S) {
    ll ret;
    sscanf(S.c_str(),"%lld",&ret);
    return ret;
}
// std::fill(start, end, value);
// for(auto it: DS){}

const int INF=(int)2e9;
const ll MOD=(ll)1e9+7;
/*==========================================================*/
/*                     END OF TEMPLATE                      */
/* DOMINUS pascit me, et nihil mihi deerit (Psalmorum 23:1) */
/*==========================================================*/

char s[100005];

int main(){
    int n,k; scanf("%d %d", &n, &k);
    scanf("%s", s);
    //
    int res = 0;
    FOR(i,n-1) res += (s[i] == 'L' && s[i+1] == 'L');
    FORD(i,n-1) res += (s[i] == 'R' && s[i+1] == 'R');
    //
    printf("%d\n", min(n-1, res + 2*k));
    return 0;
}


Measured memory_bytes: 384
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef long long ll;
using namespace std;

const int N=410;
const int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
ll ans;
char mp[N][N];
int n,m,co,bel[N][N],s1[N*N],s2[N*N];
struct P{ int x,y; }q[N*N];

void bfs(int sx,int sy){
	int st=0,ed=1; q[1]=(P){sx,sy}; co++; bel[sx][sy]=co;
	if (mp[sx][sy]=='#') s1[co]++; else s2[co]++;
	while (st<ed){
		st++; int x=q[st].x,y=q[st].y;
		rep(i,0,3){
			int x1=x+dx[i],y1=y+dy[i];
			if (x1<1 || x1>n || y1<1 || y1>m || mp[x1][y1]==mp[x][y]) continue;
			if (!bel[x1][y1]){
				bel[x1][y1]=co; q[++ed]=(P){x1,y1};
				if (mp[x1][y1]=='#') s1[co]++; else s2[co]++;
			}
		}
	}
}

int main(){
	scanf("%d%d",&n,&m);
	rep(i,1,n) scanf("%s",mp[i]+1);
	rep(i,1,n) rep(j,1,m) if (!bel[i][j]) bfs(i,j);
	rep(i,1,co) ans+=1ll*s1[i]*s2[i];
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 2304
def main():
    N = int(input())
    X = [(int(i),idx) for idx,i in enumerate(input().split())]
    Y = [(i,idx) for idx,i in enumerate(sorted(X))]
    ans1 = Y[(N//2)][0][0]
    ans2 = Y[N//2-1][0][0]
    Y.sort(key=lambda p: p[0][1])
    for y in Y:
        if y[1] <= N//2 - 1:
            print(ans1)
        else:
            print(ans2)

if __name__ == '__main__':
    main()

Measured memory_bytes: 121560
#include<iostream>
#include<algorithm>
using namespace std;
static const int MAX = 200000;

int main(void){
	int num,rating[MAX];
	
	cin >> num;

	for(int i = 0; i < num; i ++) cin >> rating[i];
	
	int maxv = -2000000000;
	int minv = rating[0];
	for(int i = 1; i < num; i ++){
		maxv = max(maxv, rating[i] - minv);
		minv = min(minv, rating[i]);
	}
	
	cout << maxv << endl;
	
	return 0;
}

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

const int MAX = 2100;

int main() {
  long long res = 0;
  int N;
  cin >> N;

  vector<long long> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);
  sort(A.begin(), A.end());

  vector<long long> C(MAX, 0), S(MAX + 1, 0);
  for (int i = 0; i < N; i++) C.at(A.at(i))++;
  for (int x = 0; x < MAX; ++x) S.at(x + 1) = S.at(x) + C.at(x);

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (i == j) continue;

      int left = abs(A.at(i) - A.at(j)) + 1;
      int right = A.at(i) + A.at(j);

      int count = S.at(right) - S.at(left);
      if (left <= A.at(i) && A.at(i) < right) --count;
      if (left <= A.at(j) && A.at(j) < right) --count;

      res += max(count, 0);
    }
  }

  cout << res / 6 << endl;
}

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

// clang-format off
#define fs first
#define sc second
#define pb emplace_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define debug(x) cerr << "(" << __LINE__ << ")" << #x << ": " << (x) << endl

#define rep(i, n) for (int i = 0; i < (int)(n); ++(i))
#define reps(i, n) for (int i = 1; i <= (int)(n); ++(i))
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --(i))
#define rreps(i, n) for (int i = (int)(n); i > 0; --(i))

#define range(i, l, r) for (int i = (int)l; i < (int)(r); ++(i))
#define rrange(i, l, r) for (int i = ((int)(r) - 1); i >= (int)l; --(i))

#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
#define rwhole(f,x,...) ([&](decltype((x)) whole) { return (f)(rbegin(whole), rend(whole), ## __VA_ARGS__); })(x)

using int32 = int;
using int64 = long long;

constexpr int mod     = 1e9 + 7;
constexpr int32 inf   = 1001001001;
constexpr int64 infll = 1001001001001001001ll;
constexpr int dx[]    = {0, -1, 1, 0, -1, 1, -1, 1},
              dy[]    = {-1, 0, 0, 1, -1, -1, 1, 1};
const string YES = "YES", NO = "NO", Yes = "Yes", No = "No", yes = "yes", no = "no";

template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { os << v[0]; for (int i = 1; i < v.size(); ++i) os << " " << v[i]; return os; }
template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p) { os << p.fs << " " << p.sc; return os; }
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.fs >> p.sc; return is; }

struct IoSetup { IoSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup;

template<typename T = int64> T input() { T x; cin >> x; return x; }

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

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
// clang-format on

void solver() {
  int N = input(), T = input();
  vector<int> A(N);
  cin >> A;
  
  int diff = -inf;
  int min_A = A[0];
  int ans = 0;

  range(i, 1, N) {
    if (chmax(diff, (A[i] - min_A))) {
      ans = 1;
    } else if (diff == (A[i] - min_A)) {
      ans++;
    }

    chmin(min_A, A[i]);
  }

  cout << ans << endl;
}

signed main(int argc, char *argv[]) {
    solver();
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, x, N) for (long long i = x; i < (N); i++)
using namespace std;
int main()
{
	int H, A;
	cin >> H >> A;
	if (H % A == 0)
	{
		cout << H / A << endl;
	}
	else
	{
		cout << H / A + 1 << endl;
	}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define all(v) ((v).begin()),((v).end())
#define ll long long
#define fastIO cout << fixed << setprecision(12), ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
double const EPS = 1e-12, PI = acos(-1);
const int N = 1e6 + 9, M = 5e3 + 9, OO = 1e9 + 7, MOD = 1e9 + 7;
const ll inf = 1e18;

bool prime[N];
vector<int> p;

void sieve() {
  ll mx = 1e6;
  prime[0] = prime[1] = 1;
  for(int i = 2; i * i <= mx; ++i) {
    if(prime[i]) continue;
    for(int j = i * i; j <= mx; j += i) {
      prime[j] = 1;
    }
  }
  for(int i = 2; i < mx; ++i) {
    if(!prime[i])
      p.push_back(i);
  }
}

int main() {
  fastIO;
#ifdef LOCAL
  freopen("input.in", "rt", stdin);
#endif
  int x;
  sieve();
  cin >> x;
 int it = lower_bound(p.begin(), p.end(), x) - p.begin();
 cout << p[it];
  return 0;
}


Measured memory_bytes: 1916
import java.util.*;

class Main
{
    public static void main (String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++){
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);
        int count = 0;
        int i = 0;
        while(x >= a[i]){
            x -= a[i];
            if(i < n-1 || ( i == n-1 && x == 0)){
                count++;
            }
            i++;
            if(i == n) break;
        }
        System.out.println(count);
    }
}

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

int main(){
  char s[100000];
  char a[100000];
  int top = 0;
  int read = 0;
  cin >> a;
  while(a[read]){
    if(a[read] == 'B'){
      if(top != 0) top--;
    }else{
      s[top] = a[read];
      top++;
    }
    read++;
  }
  rep(i,top){
    cout << s[i];
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cctype>
#include <functional>
using namespace std;
using ll = long long;

#define reps(i,s,n) for(int (i) = (s); (i) < (n); (i)++)
#define rep(i,n) reps(i,0,n)


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

    sort(v.begin(),v.end());
    int tmp = v[0];
    int cnt = 1;
    reps(i,1,n){
        if(tmp != v[i]) {
            tmp = v[i];
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 3572
/**
 *  author: mahfuzz
 *  created: 12.01.2020
**/
 
#include <iostream>
using namespace std;
typedef long long ll;

int main(int argc, char* argv[]){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    int k, x; cin >> k >> x;
    
    if(k*500 >= x)
        cout << "Yes\n";
    else
        cout << "No\n";
    
    
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static double sum(int p) {
		long ans = 0;
		ans = (long) p * (long) (p + 1);
		ans >>= 1;
		return (double) ans;
	}

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), k = sc.nextInt();
		int p[] = new int[n];
		for (int i = 0; i < n; ++i)
			p[i] = sc.nextInt();
		sc.close();
		double e[] = new double[n + 1];
		for (int i = 1; i <= n; ++i) {
			int tmpp = p[i - 1];
			double tmp = sum(tmpp) / (double) tmpp;
			e[i] = e[i - 1] + tmp;
		}
		double ans = 0;
		for (int i = 0; i <= n - k; ++i) {
			double tmp = e[i + k] - e[i];
			ans = Math.max(ans, tmp);
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 74636
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef  unsigned long long int ull;
typedef pair<ll,ll> P;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int main(){
  int n;
  while(1){
  cin>>n;
  if(n==0)return 0;
  int ans=0;
   V<int> a(n);
   for(int i=0;i<n;i++)a[i]=i+1;
   int r=0,sum=0;
   for(int l=0;l<n;l++){
       while(r<n&&sum+a[r]<=n){
           sum+=a[r];
           r++;
       }
       if(sum==n&&r-l>=2)ans++;
       if(l==r)r++;
       else sum-=a[l];
   }
   cout<<ans<<endl;
  }
 
}


Measured memory_bytes: 3168
N=int(input())
X=input()

def popcount(x):
    return str(bin(x)).count("1")

cnt=[0]*N
for i in range(1,N):
    p = popcount(i)
    cnt[i]=cnt[i%p]+1


P=X.count("1")

#MODSPP[i]=2**i%(P+1)
MODSPP=[0]*N
MODSPM=[0]*N

PP=P+1
if P-1<=0:
    PM=1
else:
    PM=P-1

MODSPP[0]=1%PP
MODSPM[0]=1%PM

for i in range(1,N):
    MODSPP[i]=(MODSPP[i-1]*2)%PP
    MODSPM[i]=(MODSPM[i-1]*2)%PM



MODSX_PP=0
MODSX_PM=0
for i in range(N):
    if X[i]=="1":
        MODSX_PP+=MODSPP[N-i-1]
        MODSX_PM+=MODSPM[N-i-1]
    MODSX_PP%=PP
    MODSX_PM%=PM


for i in range(N):
    if X[i]=="0":
        ret=MODSX_PP+MODSPP[N-i-1]
        ret%=PP
        print(cnt[ret]+1)
    else:
        if P-1<=0:
            print(0)
        else:
            ret=(MODSX_PM-MODSPM[N-i-1]+PM)%PM
            print(cnt[ret]+1)


Measured memory_bytes: 26600
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
using namespace std;

int main(void){
	int c[100000];
	int r[100000];
	int n;
	int m;
	int x;
	int y;
	int s;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++){
		r[i] = 0;
		c[i] = 1;
	}
	r[0] = 1;
	for (int i = 0; i < m; i++){
		scanf("%d %d", &x, &y);
		x--;
		y--;
		if (r[x] == 1){
			r[y] = 1;
			c[x]--;
			c[y]++;
			if (c[x] == 0)r[x] = 0;
		}
		else{
			c[x]--;
			c[y]++;
		}
	}
	s = 0;
	for (int i = 0; i < n; i++){
		s = s + r[i];
	}
	printf("%d\n", s);
	return 0;
}


Measured memory_bytes: 896
import java.util.Scanner;

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 = b-a;
		int sum = (1+c)*c/2;
		System.out.println(sum -b);
	}
}

Measured memory_bytes: 35568
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>
#include <set>
#include <ctime>
#include <tuple>
#include <bitset>
#include <assert.h>
#include <deque>
using namespace std;

/*
using PAIR = pair<string, int>;
sort(sp.begin(), sp.end(), [](PAIR l, PAIR r){
        return l.first<r.first || (l.first==r.first && l.second > r.second);
        });
*/

typedef long long ll;

#define fi first
#define se second
#define rep(i, n) for (ll i = 0; i < n; i++)
#define debugA() cerr << "AAAAA" << endl
#define debug_() cerr << "-------------" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define debug_vec(v)                   \
    for (int i = 0; i < v.size(); i++) \
    {                                  \
        cout << v[i] << " ";           \
    }                                  \
    cout << endl;

using Graph = vector<vector<int>>;

int main()
{
    int a, b, c, x, y;
    cin >> a >> b >> c >> x >> y;
    int ans = a * x + b * y;
    while (true)
    {
        if (ans - a - b + 2 * c < ans && x - 1 >= 0 && y - 1 >= 0)
        {
            x--;
            y--;
            ans = ans - a - b + 2 * c;
        }
        else if (ans - b + 2 * c < ans && x == 0 && y - 1 >= 0)
        {
            y--;
            ans = ans - b + 2 * c;
        }
        else if (ans - a + 2 * c < ans && x - 1 >= 0 && y == 0)
        {
            x--;
            ans = ans - a + 2 * c;
        }
        else
        {
            break;
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<cstdlib>
#define pb push_back
#define mk make_pair
#define ll long long
#define lson ch[x][0]
#define rson ch[x][1]
#define int long long

using namespace std;

inline int read()
{
   int x=0,f=1;char ch=getchar();
   while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
   while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
   return x*f;
}

int a,b,k;

signed main()
{
   k=read(),a=read(),b=read();
   if (a+2>b)
   {
     cout<<k+1;
     return 0;
   }
   if (k<a+1)
   {
     cout<<k+1;
     return 0;
   }
   else
   {
     int ans=0;
     ans+=b;
     k-=a+1;
     cout<<ans+k/2*(b-a)+k-k/2*2;
   }
   return 0;
}



Measured memory_bytes: 256
#![allow(dead_code)]

fn main() {
    let num:Vec<u32>= read_vec();
    
    
    println!("{}", num[0] * num[1]);

}


fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}

fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}


fn read_n<T: std::str::FromStr>(n: u32) -> Vec<T> {
    (0..n).map(|_| read()).collect()
}


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

long int modpow(long int a,long int n,long int mod){
  long int ans=1;
  while(n>0){
    if(n & 1){
      ans=ans*a%mod;
    }
    a=a*a%mod;
    n/=2;
  }

  return ans;
}

/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/

int main(void){
  long int n;
  scanf("%ld",&n);
  char s[n+10];
  scanf("%s",s);

  long int count=0;
  for(int i=n-1;i>=0;i--){
    if(s[i]=='1'){
      count++;
    }
  }

  int prep=0;
  int prem=0;

  int now=1;
  for(int i=n-1;i>=0;i--){
    int a=s[i]-'0';
    prep+=now*a;
    prep%=(count+1);
    now*=2;
    now%=(count+1);
  }
  now=1;

  if(count>1){
    for(int i=n-1;i>=0;i--){
      int a=s[i]-'0';
      prem+=now*a;
      prem%=(count-1);
      now*=2;
      now%=(count-1);
    }
  }

  for(long int i=0;i<n;i++){
    int x=0;
    int ans=1;
    if(s[i]=='0'){
      x=prep;
      x+=modpow(2,n-1-i,count+1);
      x%=(count+1);
    }
    else if(count==1 && s[i]=='1'){
      printf("0\n");
      continue;
    }
    else{
      x=prem;
      x-=modpow(2,n-1-i,count-1);
      x+=2*(count-1);
      x%=(count-1);
    }

    int past=x;
    int cnt=0;
    while(past!=0){
      cnt=0;
      x=past;
      while(x!=0){
        if(x%2==1){
          cnt++;
        }
        x/=2;
      }

      if(cnt==0){
        ans++;
        break;
      }
      past=past%cnt;
      ans++;
    }

    printf("%ld\n",ans);
  }
}

Measured memory_bytes: 1884
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    t1, t2 = LI()
    a1, a2 = LI()
    b1, b2 = LI()
    if t1 * a1 + t2 * a2 == t1 * b1 + t2 * b2:
        print("infinity")
        return
    if t1 * a1 > t1 * b1:
        if t1 * a1 + t2 * a2 > t1 * b1 + t2 * b2:
            print(0)
            return
        else:
            x = t1 * (a1 - b1) / (-t1 * (a1 - b1) + t2 * (b2 - a2))
            if x.is_integer():
                print(2 * (t1 * (a1 - b1) // (-t1 * (a1 - b1) + t2 * (b2 - a2))))
            else:
                print(2 * (t1 * (a1 - b1) // (-t1 * (a1 - b1) + t2 * (b2 - a2))) + 1)
            return
    elif t1 * a1 < t1 * b1:
        if t1 * a1 + t2 * a2 < t1 * b1 + t2 * b2:
            print(0)
            return
        else:
            x = t1 * (b1 - a1) / (-t1 * (b1 - a1) + t2 * (a2 - b2))
            if x.is_integer():
                print(2 * (t1 * (b1 - a1) // (-t1 * (b1 - a1) + t2 * (a2 - b2))))
            else:
                print(2 * (t1 * (b1 - a1) // (-t1 * (b1 - a1) + t2 * (a2 - b2))) + 1)
            return
    return


#main
if __name__ == '__main__':
    solve()


Measured memory_bytes: 39280
#include<bits/stdc++.h>
using namespace std;
#define fastIO ios::sync_with_stdio(0), cin.tie(0)
#define all(x) (x).begin() (x).end()
#define rall(x) (x).rbegin() (x).rend()
typedef pair<int,int> pii;
typedef long long ll;

int main(){
	int m,p; cin>>m>>p;
	cout<<((m*3)+p)/2<<endl;
}


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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repp(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perr(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)

typedef long long LL;
typedef long double LD;

int main(){
  string s;
  cin >> s;
  int n = s.length();
  queue<int> q;
  rep(i,n-1){
    if(s[i]=='A'){
      q.push(1);
    }else if(s[i]=='B'){
      if(s[i+1]=='C') q.push(0),i++;
      else q.push(-1);
    }else{
      q.push(-1);
    }
  }
  LL ans=0;
  LL count=0;
  while(!q.empty()){
    int x = q.front();
    q.pop();
    if(x==0){
      ans+=count;
    }else if(x==1){
      count++;
    }else{
      count=0;
    }
  }
  cout << ans << endl;
  return 0;
}


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

namespace AtCorder
{
	public class Program
	{
		const long MOD = 1000000007;
		static void Main(string[] args)
		{
			Scanner cin = new Scanner();
			int q = cin.Int();

			bool[] p = new bool[100001];
			for (int i = 2; i <= 100000; i++) {
				if (IsPrime(i)) {
					p[i] = true;
				}
			}

			int[] num = new int[100001];
			int count = 0;
			for (int i = 3; i <= 100000; i++) {
				if (i % 2 == 1 && p[i] && p[(i + 1) / 2]) {
					++count;
				}

				num[i] = count;
			}

			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < q; i++) {
				int l = cin.Int();
				int r = cin.Int();
				sb.AppendLine((num[r] - num[l - 1]).ToString());
			}

			Console.WriteLine(sb.ToString());
		}

		public static bool IsPrime(long value)
		{
			for (int i = 2; i * i <= value; i++) {
				if (value % i == 0) {
					return false;
				}
			}

			return true;
		}
	}

	public class Scanner
	{
		private readonly char[] delimiter_ = new char[] { ' ' };
		private string[] buf_;
		private int index_;
		
		public Scanner()
		{
			buf_ = new string[0];
			index_ = 0;
		}

		public string Next()
		{
			if (index_ < buf_.Length) {
				return buf_[index_++];
			}

			string st = Console.ReadLine();
			while (st == "") {
				st = Console.ReadLine();
			}

			buf_ = st.Split(delimiter_, StringSplitOptions.RemoveEmptyEntries);
			if (buf_.Length == 0) {
				return Next();
			}

			index_ = 0;
			return buf_[index_++];
		}

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

		public long Long()
		{
			return long.Parse(Next());
		}

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

		public double Double()
		{
			return double.Parse(Next());
		}

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


Measured memory_bytes: 18120
#include <cstdio>
#include <algorithm>
#define maxn 233
using namespace std;
int cnt,n,i,a[maxn*maxn],col[maxn][maxn],m,N;

void dfs(int x,int y,int c,int fx)
{
	if (cnt>=n*m) return ;
	for (i=y;i<=m&&i>=1&&a[c];i+=fx) col[x][i]=c,--a[c],++cnt;
	i-=fx;
	if (!a[c]) ++c;
	if (i==m&&fx==1) dfs(x+1,m,c,-fx);
	else if (i==1&&fx==-1) dfs(x+1,1,c,-fx);
	else dfs(x,i+fx,c,fx);
}

int main()
{
	scanf("%d%d%d",&n,&m,&N);
	for (int i=1;i<=N;++i) scanf("%d",&a[i]);
	dfs(1,1,1,1);
	for (int i=1;i<=n;++i) 
	{
		for (int j=1;j<=m;++j) printf("%d ",col[i][j]);
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 384
import java.io.*;

class Main
{
       public static void main (String[] args) throws IOException
       {

       BufferedReader br =
        new BufferedReader(new InputStreamReader(System.in));

       String str1 =br.readLine();
       String str2[] =str1.split(" ");
       int a =Integer.parseInt(str2[0]);
       int b =Integer.parseInt(str2[1]);
       int c =a*b;       
       int d =2*(a+b);

       System.out.println(c + " " + d);

    }
}

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

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    int n;
    long d;

    cin >> n >> d;

    int t = 0;
    for (int i = 0; i < n; ++i) {
        long x, y;
        cin >> x >> y;

        if (sqrt(x*x+y*y) <= d) {
            t++;
        }

    }

    cout << t;
    return 0;
}


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

int main(){

string S,T;
int A,B;
string U;

cin >> S >> T >> A >> B >> U;

if(S == U){
  cout << A-1 << " " << B << endl;
} else{
  cout << A << " " << B-1 << endl;
}
  return 0;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
B = [set() for x in range(N)]

ans = 0
for i in range(N):
    j = A[i] - 1
    if j in B[i] or i in B[j]:
        ans += 1
    else:
        B[i].add(j)
        B[j].add(i)

print(ans)


Measured memory_bytes: 105088
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <cmath>   
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
#define all(x) (x).begin(),(x).end()
#define rep(i,m,n) for(int i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(int i = m;i >= n;--i)
#define INF INT_MAX/2
using namespace std;
using ll = long long;
using R = double;
using Data = pair<ll, vector<int>>;
const ll MOD = 1e9 + 7;
const ll inf = 1LL << 50;
struct edge { ll from; ll to; ll cost; };

ll N[3], K;
ll A[3][1010];
vector<ll>B;
ll BN;


int check(ll x) {
	ll cnt = 0;
	rep(i, 0, N[0]) {
		ll ind = lower_bound(all(B),x-A[0][i]) - B.begin();
		cnt += BN - ind;
	}
	return K <= cnt;
}



int main() {
	rep(i, 0, 3)cin >> N[i];
	cin >> K;
	rep(i, 0, 3)rep(j, 0, N[i])cin >> A[i][j];
	rep(a, 0, N[1])rep(b, 0, N[2])B.pb(A[1][a]+A[2][b]);
	sort(all(B));
	BN = B.size();

	ll ok = 0; ll ng = inf;
	while (ng - ok > 1) {
		ll mid = (ok + ng) / 2;
		if (check(mid))ok = mid;
		else ng = mid;
	}

	reverse(all(B));
	vector<ll>ans;
	rep(i, 0, N[0]){
		fore(b,B){
			if (A[0][i] + b > ok)ans.pb(A[0][i] + b);
			else break;
		}
	}

	while (ans.size() < K)ans.pb(ok);

	sort(all(ans));
	reverse(all(ans));
	rep(i, 0, K) {
		cout << ans[i] << endl;
	}


	return 0;
}

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

const int M=105;
int cnt[M];

int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	int d,a;
	for(int i=0;i<k;i++)
	{
		scanf("%d",&d);
		while(d--)
		{
			scanf("%d",&a);
			cnt[a]++;
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		if(!cnt[i]) ans++;
	printf("%d\n",ans);
	return 0;
}

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

int N;

bool check_mark(int k, string s) {
	string mark = string(k, 'x');
	for (int i = 0; i < k; ++i) {
		int idx = (int)(s[i] - '0');
		mark[idx] = 'o';
	}
	bool ret = true;
	for (int i = 0; i < k - 1; ++i) {
		if (mark[i] == 'x' && mark[i + 1] == 'o') {
			ret = false;
			break;
		}
	}
	return ret;
}

void rec(int k, string s) {
	bool flag = check_mark(k, s);
	if (!flag)
		return;
	if (k == N) {
		if (flag) {
			for (int i = 0; i < N; ++i)
				s[i] += 'a' - '0';
			cout << s << '\n';
			return;
		}
	}
	for (int i = 0; i <= k; ++i) {
		char c = (char)i + '0';
		string ns = s + c;
		rec(k + 1, ns);
	}
}

int main(void) {
	cin >> N;
	rec(1, "0");
	return 0;
}


Measured memory_bytes: 1536
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AtCoder
{
  class Program
  {
    static void Main(string[] args)
    {
      int input = int.Parse(Console.ReadLine());
      double PI = 3.1415926535897931;
      
      double result = (input * 2 * PI);
      
      Console.WriteLine(result);
    }
  }
}

Measured memory_bytes: 27580
R = 2**15+1
r = 182
s = [i*i for i in range(r)]
L = [0]*R
for i in range(r):
	for j in range(i,r):
		for k in range(j,r):
			for l in range(k,r):
				if s[i]+s[j]+s[k]+s[l] < R:
					L[s[i]+s[j]+s[k]+s[l]] += 1

while 1:
	n = input()
	if n == 0: break
	print L[n]

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

using namespace std;

#define pb push_back
#define mp make_pair
#define sz(x) (int)x.size()
#define mem(a) memset(a,0,sizeof(a))
#define sqr(x) ((x)*(x))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const int mn=2e5+5;

int n;

int sum(int a){
    int s=0;
    while(a){
        s+=a%10;
        a/=10;
    }
    return s;
}

int main() {
#ifdef trote
    freopen("../1.txt", "r", stdin);
#endif

    scanf("%d",&n);

    int maxi=1e9;
    for(int i=1;i<n;i++){
        int b=n-i;
        //printf("%d %d\n",i,sum(i)+sum(b));
        maxi=min(sum(i)+sum(b),maxi);
    }
    printf("%d\n",maxi);

    return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
int main(void){
    char s[200001];
    int start=0, stop=0;
    scanf("%s", s);
    for(int i=0; s[i]!='A'; i++) start = i+1;
    for(int i=strlen(s); s[i]!='Z'; i--) stop = i-1;
    printf("%d", stop-start+1);
    return 0;
}

Measured memory_bytes: 1928
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define lld long int
int main()
{
    ll n;
    cin>>n;
    ll arr[n];
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    ll ans=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            ans+=arr[i]*arr[j];
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
t = int(input())
for _ in range(t):
  gx, gy = map(int, input().split())
  p = int(input())
  right_stop = set()
  down_stop = set()
  
  for _ in range(p):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == x2:
      down_stop.add((x1 + 1, min(y1, y2) + 1))
    if y1 == y2:
      right_stop.add((min(x1, x2) + 1, y1 + 1))
  
  dp = [[0] * (gx + 2) for _ in range(gy + 2)]
  dp[1][1] = 1
  for y in range(1, gy + 2):
    for x in range(1, gx + 2):
      if (x - 1, y) not in right_stop:
        dp[y][x] += dp[y][x - 1]
      if (x, y - 1) not in down_stop:
        dp[y][x] += dp[y - 1][x]
  if dp[gy + 1][gx + 1] > 0:
    print(dp[gy + 1][gx + 1])
  else:
    print("Miserable Hokusai!")
  


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



int main() {
    //input
    long long h,w;
    cin >> h >> w;

    for(int i=0;i<h;i++){
        string str;
        cin >> str;
        cout << str << endl;
        cout << str << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int maximam(n,m){
    if(n>m) return n;
    return m;
}
int main(void){
    int n,m;
    int i;
    int l,r;
    int min=10000000,max=-1;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++){
        scanf("%d%d",&l,&r);
        if(l>max) max=l;
        if(r<min) min=r;
    }
    printf("%d",maximam(min-max+1,0));
    return 0;
}


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

int main() {
	int n,m;
	cin>>n>>m;
	int arr[m+1];
	memset(arr,0,sizeof(arr));
	int maxi=-1;
	for(int i=0;i<n;i++)
	{
		int k;
		cin>>k;
		while(k--)
		{
			int a;
			cin>>a;
			arr[a]++;
			//maxi=max(maxi,arr[i]);
		}
	}
	sort(arr,arr+m+1);
	int cnt=0;
	for(int i=m;i>=0;i--)
	{
		//cout<<arr[i]<<endl;
		if(arr[i]==n)cnt++;
	}
	cout<<cnt;
	
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
 
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define pvec(v) rep(i,v.size()){cout << v[i] << " ";};cout<<endl;
#define pb push_back
#define pf push_front
#define mod 1e9+7
#define m_p make_pair
 
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef vector<vector<int>> vvi;
const double pi = acos(-1.0);
 
ll gcd(ll x, ll y) { return (y == 0) ? x : gcd(y, x % y); }
ll lcm(ll x, ll y) { return x * y / gcd(x, y); }

bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    ll a,b;
    cin >> a >> b;
    if(a < b) cout << 0 << endl;
    else cout << 10 << endl;
    return 0;
}


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

int main(void){
	int flag , i;
	char t[90] = {0};
	char str1[] = "the";
	char str2[] = "that";
	char str3[] = "this";
	i = 0;
	while(scanf("%[^\n]" , t)!=EOF){
		while(1){
				i = 0;
			while(t[i] != '\0'){
				if(isalpha((int)t[i])){
					t[i] = (t[i] - 'a' + 1) % 26 + 'a';
				}
				i++;
			}
			if((strstr(t , str1) != NULL)||(strstr(t , str2) != NULL)||(strstr(t , str3) != NULL)){
				printf("%s\n" , t);
				break;
			}
		}
		scanf("%*c");
	}
return 0;
}

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


void solve(long long a, long long b, long long c, long long d){
    long long max = -1000000000000000000;



    // for(long long i = a; i <= b; i++) {
    //     for(long long j = c; j <= d; j++) {
    //         long long buf = i * j;
    //         if(buf > max) {
    //             max = buf;
    //         }
    //     }
    // }
    if(a * d > max) {
        max = a * d;
    }
    if(a * c > max) {
        max = a * c;
    }
    if(b * c > max) {
        max = b * c;
    }
    if(b * d > max) {
        max = b * d;
    }



    cout << max << endl;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long a;
    scanf("%lld",&a);
    long long b;
    scanf("%lld",&b);
    long long c;
    scanf("%lld",&c);
    long long d;
    scanf("%lld",&d);
    solve(a, b, c, d);
    return 0;
}


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

using namespace std;
#define SORT(a) sort((a).begin(), (a).end())
#define RSORT(a) reverse((a).begin(), (a).end())
#define rep(i, a, b) for (int64_t i = (a); i < (b); ++i)
const int MOD = 1e9 + 7;
typedef long long ll;
const long long INF = 1LL << 60;
using Graph = vector<vector<int>>;

long long saiki(ll h) {
  if (h == 1) return 1;
  return 2 * saiki(h / 2) + 1;
}

int main() {
  ll h;
  cin >> h;
  cout << saiki(h) << endl;
}


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

#define i_cin(X) scanf("%d", &X)
#define i_cin2(X,Y) scanf("%d %d",&X,&Y)
#define i_cin3(X,Y,Z) scanf("%d %d %d",&X,&Y,&Z)
#define l_cin(X) scanf("%ld",&X)
#define l_cin2(X,Y) scanf("%ld %ld",&X,&Y)
#define s_cin(X) scanf("%s",&X)

#define  i_cout(X) printf("%d\n",X)
#define  f_cout(X) printf("%g\n",X)
#define  i_cout2(X,Y) printf("%d %d\n",X,Y)
#define  l_cout(X) printf("%ld\n",X)
#define  s_cout(X) printf("%s\n",X)
#define  ll_cout(X) printf("%lld\n",X)

typedef long long int lli;
#define rept(x, s, n) for (int x = s; x < n; x++)

#define YES_RTN s_cout("Yes");return 0
#define NO_RTN  s_cout("No");return 0


int i_cins(int n, int* A);
int l_cins2(int n, long* A,long* B);
int s_dsort(const void* a, const void* b);
int s_asort(const void* a, const void* b);


int main(void) {

	int   N, A[101], i,cnt = 0;

	i_cin(N);
	i_cins(N,A);

	rept(i, 0, (N - 2)) {
		if ((A[i] < A[i + 1]) && (A[i + 1] < A[i + 2]))
		{
			cnt++; continue;
		}
		if ((A[i] > A[i + 1]) && (A[i + 1] > A[i + 2])) cnt++; 
	}
	
 	i_cout(cnt);
	return 0;
	}
	
//降順
int s_dsort(const void* a, const void* b) {
	return(*(int*)b - *(int*)a);
}
int s_asort(const void* a, const void* b) {
	return(*(int*)a -*(int*)b);
}
//
int l_cins2(int n, long* a, long* b) {
	int i;
	rept(i, 0, n) {
		l_cin2(*(a + i), *(b + i));
	}
	return 0;
}
int i_cins(int n, int* a) {
	int i;
	rept(i, 0, n) {
		i_cin(*(a + i));
	}
	return 0;
}

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

typedef long long ll;
const ll mod = 1e9+7;

ll mod_pow(ll x,ll n){
  static unordered_map<int,int> memo;
  if( memo.count(x) ) return memo[x];
  ll res=1;
  while(n){
    if(n%2) res=res*x%mod;
    x=x*x%mod;
    n = n>>1;
  }
  return memo[x] = res;
}

ll factorial(int i){
  static vector<ll> k(1e6);
  if(!k[0]){k[0]=1;for(int i=1;i<(int)k.size();++i)k[i]=i*k[i-1]%mod;}
  return k[i];
}

ll nPr(ll &n,ll &r){
  return factorial(n) * mod_pow( factorial(n-r), mod - 2 ) % mod;
}

ll nCr(ll &n,ll &r){
  ll a = mod_pow( factorial(r) * factorial(n-r) % mod, mod-2 );
  return factorial(n) * a % mod;
}

int n;
vector<int> G[5005];

int cent = 0;
vector<int> SZ;

int dfs(int x, int px){
  
  int res = 1;
  
  int flag = 1;
  
  vector<int> pepi;
  
  for(int nx : G[x] ){
    
    if( nx == px ) continue;
    
    int r = dfs( nx, x );
    
    if( r > n / 2 ) flag = 0;
    
    pepi.push_back(r);
    
    res += r;
    
  }
  
  pepi.push_back(n-res);
  
  if( n - res > n / 2 ) flag = 0;
  
  if( flag ){
    cent++;
    SZ = pepi;
  }
  
  return res;
}

int dp[5005][5005];

signed main(){
  
  cin>>n;
  
  for(int i=0;i<n-1;i++){
    int x, y;
    cin>>x>>y;
    G[x-1].push_back(y-1);
    G[y-1].push_back(x-1);
  }
  
  dfs(0,-1);
  
  if( cent == 2 ){
    cout<<(int)mod_pow(factorial(n/2),2)%mod<<endl;
    return 0;
  }
  
  dp[0][0] = 1;
  
  sort(SZ.begin(),SZ.end());

  int len = SZ.size();
  
  for(int i=0;i<len;++i){
    
    for(int k=0;k<=SZ[i];++k){
      
      int me = nCr(SZ[i],k) * nPr(SZ[i],k) % mod;
	
      for(int j=0;j<=n;++j){
      
	if( dp[i][j] == 0 ) break;
	
	dp[i+1][j+k] += dp[i][j] * me;
	
	dp[i+1][j+k] %= mod;
	
      }
      
    }
    
  }
  
  int ans = 0;
  
  for(int i=0;i<=n;i++){
    
    if( i % 2 == 0 ) ans += dp[(int)SZ.size()][i] * factorial( n - i ) % mod;
    else ans -= dp[(int)SZ.size()][i] * factorial( n - i ) % mod;
    
    ans += mod;

    ans %= mod;
  }
  
  cout<<(ans+mod)%mod<<endl;
  
  return 0;
}


Measured memory_bytes: 202240
import math
a,b=list(map(int,input().split(" ")))

def solve(a,b,fc):

    S=a*b

    if fc=="ceil":
        x=math.ceil((S/3)/a)
    else:
        x=math.floor((S/3)/a)
    l=math.floor(a/2)
    S_l=(b-x)*l
    S_U=a*x
    S_r=(b-x)*(a-l)

    SMax=max(S_l,S_U,S_r)
    SMin=min(S_l,S_U,S_r)
    return abs(SMax-SMin)

def solve3(a,b,dupplicate=True):
    la=math.ceil(a/3)
    lc=math.floor(a/3)
    if dupplicate:
        lb=la
    else:
        lb=lc

    Sa=la*b
    Sb=lc*b
    return abs(Sa-Sb)




s1=solve(a,b,"floor")
s2=solve(a,b,"ceil")
s3=solve(b,a,"floor")
s4=solve(b,a,"ceil")
s5=solve3(a,b)
s6=solve3(a,b,False)
s7=solve3(b,a)
s8=solve3(b,a,False)

print(min(s1,s2,s3,s4,s5,s6,s7,s8))

Measured memory_bytes: 3064
#include<stdio.h>
int main(void){
	int N,i,j,v;
	int A[100];
	scanf("%d",&N);
	for(i=0;i<N;i++){
		scanf("%d",&A[i]);
	}
	for(j=0;j<N-1;j++){
			printf("%d ",A[j]);
	}
	printf("%d\n",A[N-1]);
	for(i=1;i<N;i++){
		v=A[i];
		j=i-1;
		while(0<=j && A[j]>v){
			A[j+1]=A[j];
			j--;
		}
		A[j+1]=v;
		for(j=0;j<N-1;j++){
			printf("%d ",A[j]);
		}
		printf("%d\n",A[N-1]);
	}
	return 0;
}

Measured memory_bytes: 600
#include<iostream>
#include<string>
#include<map>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define cout(x) cout << x << endl;
typedef vector<int> vint;
typedef vector<long> vl;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef map<string, int> mapstri;
typedef map<string, int> mapii;

int main () {
    int N, R;
    cin >> N >> R;
    if (N < 10) cout(R + (100*(10-N)))
    else cout(R)
    return 0;
}

Measured memory_bytes: 888
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,i,e,f,g,n,m,k,l,A[200005],x;
vector <long long> v[200005];
string s;
int main() {
	cin>>x;
	for(long long i=0;i<=10000;i++) {
		for(long long j=0;j<=10000;j++) {
			a=i*i*i*i*i;
			b=j*j*j*j*j;
			if(a+b==x) { cout<<i<<" "<<-j; return 0; }
			if(a-b==x) { cout<<i<<" "<<j; return 0; }
		}
	}
}

Measured memory_bytes: 8320
#include<iostream>
#include<stdio.h>
#include<string>
#include<cmath>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<unordered_map>
#define rep(i,n) for(int i = 0; i < (n); i++)
#define PI 3.141592653589793

using namespace std;
using ll = unsigned long long;

int main() {

	ll n;
	
	cin >> n;

	vector<int> c(n);
	vector<int> v(n);
	vector<int> r(n);

	rep(i, n) {
		cin >> v[i];
	}
	rep(i, n) {
		cin >> c[i];
	}
	rep(i, n) {
		r[i] = v[i] - c[i];
	}
	int ans = 0;

	rep(i, n) {

		if (r[i] > 0)ans += r[i];

	}

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

Measured memory_bytes: 256
import numpy as np
from collections import deque

N,K = (int(i) for i in input().split())  
AB = [[int(i) for i in input().split()] for i in range(N-1)] 

Tree = [[] for _ in range(N+1)]
d = deque()

for i in range(N-1):
    a, b = AB[i]
    Tree[a].append(b)
    Tree[b].append(a)

answer = K

for i in range(len(Tree[1])):
    answer = (answer * (K - 1 - i))%(int(10**9)+7)
    d.append([1, Tree[1][i]])

Tree[1] = []

while d != deque():
    for i in range(len(d)):
        parent, child = d[0]
        Tree[child].pop(Tree[child].index(parent))
        for j in range(len(Tree[child])):
            d.append([child, Tree[child][j]])
            answer = (answer * (K - 2 - j))%(int(10**9)+7)
        d.popleft()
print(answer)


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

int main()
{
    iostream::sync_with_stdio(0);
    multiset<int>s;
    int T,num=0;
    cin>>T;
    while(T--)
    {
        int flag,x;
        cin>>flag>>x;
        if(flag==0)
        {
            auto it=s.insert(x);
           // if(it.second==1)
                num++;
            cout<<num<<endl;
        }
        else if(flag==1)
        {
            auto m=s.count(x);

             cout<<m<<endl;
        }
        else if(flag==2)
        {
            int n=s.erase(x);
            num-=n;
        }
        else
        {
            int R;
            cin>>R;
            for(auto it=s.lower_bound(x);it!=s.end()&&*it<=R;it++)
            {

                    cout<<*it<<endl;

            }
        }
    }
  //  cout << "Hello world!" << endl;
    return 0;
}



Measured memory_bytes: 12444
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n,k,x,y; cin >> n >> k >> x >> y;
    ll ans = 0;
    rep(i,n)
    {
        if (i+1<=k)
        {
            ans += x;
        }
        else
        {
            ans += y;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
  ll A,B,M,maximum=200000,min1=100000,min2=100000;
  cin>>A>>B>>M;
  vector<ll> a(A);
  vector<ll> b(B);
  for(ll i=0;i<A;i++){
    cin>>a.at(i);
    min1=min(min1,a.at(i));
  }
  for(ll i=0;i<B;i++){
    cin>>b.at(i);
    min2=min(min2,b.at(i));
  }
  for(ll i=0;i<M;i++){
    ll x,y,c;
    cin>>x>>y>>c;
    maximum=min(maximum,(a.at(x-1)+b.at(y-1)-c));
  }
  cout<<min(min1+min2,maximum)<<endl;
  return 0;
}

Measured memory_bytes: 1792
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
inc = []
dec = []
for _ in range(n):
    s = readline().rstrip().decode()
    d, r = 0, 0
    for m in s:
        d += (1 if m == '(' else -1)
        r = max(r, -d)
    (dec if d < 0 else inc).append((d, r))
inc.sort(key=lambda x: x[1])
dec.sort(key=lambda x: x[0] + x[1])
p1 = 0
p2 = 0
flag = True
for i in inc:
    flag &= i[1] <= p1
    p1 += i[0]
for d in dec:
    flag &= p2 >= d[0] + d[1]
    p2 -= d[0]
flag &= p1 == p2
print('Yes' if flag else 'No')


Measured memory_bytes: 84072