akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>
#include <bitset>
#include <time.h>

using namespace std;

typedef long long ll;
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 = (1LL << 31) - 1;
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

struct Segtree {
	ll a[N_SIZE];
	ll seg[N_SIZE * 2];
	ll lazy[N_SIZE * 2];
	ll gt;
	void init(int n) {
		gt = 1;
		while (n > gt)gt *= 2;
		REP(i, n)a[i] = 0;
		REP(i, N_SIZE) {
			seg[i] = 0;
			lazy[i] = 0;
		}
		REP(i, n)seg[i + gt - 1] = a[i];
	}

	void lazy_evaluate(int k, int l, int r) {
		seg[k] += lazy[k] * (r - l);
		if (gt > k) {
			lazy[2 * k + 1] += lazy[k];
			lazy[2 * k + 2] += lazy[k];
		}
		lazy[k] = 0;
	}

	//[a,b)
	void update(int a, int b, int x) { update(a, b, 0, 0, gt, x); }
	void update(int a, int b, int k, int l, int r, int x) {
		if (r <= a || b <= l)return;
		if (a <= l&&r <= b)lazy[k] += x;
		else {
			update(a, b, 2 * k + 1, l, (l + r) / 2, x);
			update(a, b, 2 * k + 2, (l + r) / 2, r, x);
			if (gt > k) {
				seg[k] = seg[2 * k + 1] + lazy[2 * k + 1] * (r - l) / 2
					+ seg[2 * k + 2] + lazy[2 * k + 2] * (r - l) / 2;
			}
		}
	}

	//[a,b???min
	ll query(int a, int b) { return query(a, b, 0, 0, gt); }
	ll query(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l)return 0;
		if (a <= l&&r <= b) {
			return seg[k] + (r - l)*lazy[k];
		}
		else {
			lazy_evaluate(k, l, r);
			return query(a, b, 2 * k + 1, l, (l + r) / 2)
				+ query(a, b, 2 * k + 2, (l + r) / 2, r);
		}
	}

	void print() {
		REP(i, gt * 2)cout << "!" << i << " " << seg[i] << " " << lazy[i] << endl;
	}
};

int n, q;
Segtree tr;

int main() {
	cin >> n >> q;
	tr.init(n);
	REP(i, q) {
		bool f;
		int a, b, c;
		cin >> f;
		if (!f) {
			cin >> a >> b >> c;
			a--; b--;
			tr.update(a, b + 1, c);
		}
		else {
			cin >> a >> b;
			a--; b--;
			cout << tr.query(a, b + 1) << endl;
		}
	}
}

Measured memory_bytes: 20312
#include <iostream>
using namespace std;
int main(void){
    int a;
    int b;
    cin>>a;
    cin>>b;
    if(a<b){
        cout<<"a"<<" < "<<"b"<<endl;
    }else{
        if(a>b){
            cout<<"a"<<" > "<<"b"<<endl;
        }else{
            cout<<"a"<<" == "<<"b"<<endl;
        }
    }
}


Measured memory_bytes: 3112
#include <iostream>

int main() {
  int n;
  std::cin >> n;
  int max = 0;
  int value;
  int sum = 0;

  for (auto i = 0u; i < n; ++i) {
    std::cin >> value;
    if (max < value) {
      max = value;
    }
    sum += value;
  }
  sum -= (max / 2);
  std::cout << sum << std::endl;
}

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

int main()
{
	ios::sync_with_stdio(false),cin.tie(0);
	int n,m;
	bool vis[10];//记录那些位置需要被修改 
	int a[10];
	cin>>n>>m;
	int ans,beta;
	bool flag=0;//判断是否冲突 
	while(m--){
		cin>>ans>>beta;
		if(vis[ans]==0){
			vis[ans]=1;
			a[ans]=beta;
		}
		else{
			if(a[ans]!=beta)flag=1;
		}
	}
	if(flag)cout<<-1<<endl;
	else{
		if(n==1){//特判 
			if(vis[1])cout<<a[ans]<<endl;
			else cout<<0<<endl;
		}
		else if(a[1]==0&&vis[1])cout<<-1<<endl;//第一个为0直接前导冲突 
		else{
			if(vis[1]&&a[1]){//没有前导0问题 
				for(int i=1;i<=n;i++){
					if(vis[i])cout<<a[i];
					else cout<<0;
				}
			}
			else{
				a[1]=1,vis[1]=1;
				for(int i=1;i<=n;i++){
					if(vis[i])cout<<a[i];
					else cout<<0;
				}
			}
		}
	}
	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++)
using ll = long long;
using vi = vector<int>;
using Graph = vector<vector<ll>>;
using P = pair<int, int>;
const int INFTY = 1e9+7;

int main() {
  int N, M;
  cin >> N >> M;
  vi S(N), T(M);
  rep(i,N) cin >> S[i];
  rep(j,M) cin >> T[j];

  map<int, vi> pos_S, pos_T;  // 1-indexed
  // rep(i,N) pos_S[S[i]].push_back(i+1);
  rep(j,M) pos_T[T[j]].push_back(j+1);

  Graph dp(N+1, vector<ll>(M+1));  // 1-indexed
  rep(i,N+1) dp[i][0] = 1;
  rep(j,M+1) dp[0][j] = 1;
  
  for (int i=1; i<=N; i++) {
    ll sum = 0;
    for (int j=1; j<=M; j++) {
      if (S[i-1] == T[j-1]) {
        sum += dp[i-1][j-1];
        sum %= INFTY;
      }
      dp[i][j] = (dp[i-1][j] + sum) % INFTY;
    }
  }

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


Measured memory_bytes: 31744
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var str = Console.ReadLine();
            if (n % 2 == 1) { Console.WriteLine("No"); return; }

            var head = new string(str.Take(n / 2).ToArray());
            Console.WriteLine(head + head == str ? "Yes" : "No");

        }
    }
}

Measured memory_bytes: 28256
#include<bits/stdc++.h>
#define Fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

int main()
{
    //Fast;
    long long n,m,i,j,k,x=0,y=0,z,t;
    double nn,mm,kk;
    cin>>n;
    nn=(n*1.0)/3.0;
    mm=(nn*nn*nn);
    printf("%.8lf\n",mm);
}



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

int main()
{
int N,C,sum;
cin>>N>>C;
sum=0;
for(int i=0;i<C;i++){
int p;
cin>>p;
sum=sum+p;
}
cout<<(sum+N)/(N+1)<<endl;
return 0;
}




Measured memory_bytes: 3100
# -*- coding: utf-8 -*-
def main():
    answer = ''
    N,K = map(int,input().split())
    S = list(input())
    if S[K-1] == 'A':
        S[K-1] = 'a'
    elif S[K-1] == 'B':
        S[K-1] = 'b'
    elif S[K-1] == 'C':
        S[K-1] = 'c'
    for s in S:
        answer += s
    print(answer)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
#include "bits/stdc++.h"
#include <sys/timeb.h>
#include <fstream>

using namespace std;

#define repr(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define repi(itr,ds) for(auto itr=ds.begin();itr!=ds.end();itr++)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define INF 1050000000
#define INFL 9e18
#define EPS (1e-10)
#define MOD 1000000007
#define PI 3.1415926536
#define RMAX 4294967295

typedef long long ll;
typedef pair<int, int> Pi;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<vector<int> > vvi;
typedef vector<vector<bool> > vvb;
typedef vector<vector<ll> > vvll;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<double> > vvd;
typedef vector<vector<Pi> > vvPi;
typedef priority_queue<int, vector<int>, greater<int> > pqli;
typedef priority_queue<ll, vector<ll>, greater<ll> > pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi> > pqlP;
struct Edge {
	int from, to, cost;
	bool operator<(Edge e) {
		return cost < e.cost;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
template <class T>
using vec = vector<T>;
template<class T>
using pql = priority_queue<T, vector<T>, greater<T>>;
string debug_show(Pi a) {
	return "(" + to_string(a.first) + "," + to_string(a.second) + ")";
}

template<class T>
struct augEdge {
	T from, to;
	int cost;
	bool operator<(augEdge e) { return cost < e.cost; }
	bool operator>(augEdge e) { return cost > e.cost; }
};
template<class T>
using augGraph = vector<augEdge<T>>;


int main(void) {
	int N;
	cin >> N;
	vi a(N);
	ll num = 1;
	ll ans = 1;
	rep(i, N) {
		cin >> a[i];
		if (a[i] % 2 == 0)ans *= 2;
		num *= 3;
	}

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

Measured memory_bytes: 256
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 main(){
    let n = read::<i64>();
    let a = n / 2;
    let b = n - a;
    println!("{}",a *b );
}

Measured memory_bytes: 4352
/*  ex3_3
    potter0723sw  */

//方針：NをKで何回も割って商が0になるまでの割る回数をカウントする

#include <stdio.h>

int main(void) {
	int number,ary,answer;
	scanf("%d %d", &number, &ary);
	answer = 1;//最後に2桁増えることを考慮して1からスタート
	while(number >= ary){//numberがaryより小さくなったら割るのを終わる
		number = number / ary;
		answer += 1;
	}
	printf("%d\n",answer);
	return 0;
}


Measured memory_bytes: 128
import sys
input = sys.stdin.readline
def inputs():return [int(x) for x in input().split()]
N,K = inputs()
xy = [inputs() for _ in range(N)]
#xy = sorted(xy,key=lambda x: x[1])
xy = sorted(xy,key=lambda x: x[0])
#print(xy)
ans = 10**20
for i in range(N-K+1):
  for j in range(i+K-1,N):
    #print(i,j)
    xy1 = xy[i:j+1]
    #print(xy1)
    xy1 = sorted(xy1,key=lambda x: x[1])
    mi = min(xy1[i+K-1][1]-xy1[i][1] for i in range(len(xy1)-K+1))
    ans = min(ans,(xy[j][0]-xy[i][0])*mi)
print(ans)
    
    

Measured memory_bytes: 39920
#include <stdio.h> 
#include <string.h>
int main(void) 
{ 
    char s[1000][1000], t[1000][1000];
    int n, m, i, j, a, b=0;
    
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%s",s[i]);
    scanf("%d",&m);
    for(i=0;i<m;i++) scanf("%s",t[i]);
    
    for(i=0;i<n;i++){
        a=0;
        for(j=i;j<n;j++){
            if(strcmp(s[i],s[j])==0) a++;
        }
        for(j=0;j<m;j++){
            if(strcmp(s[i],t[j])==0) a--;
        }
        if(a>b) b=a;
    }
    printf("%d\n",b);
    return 0;
}

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

int main()
{
    int n;
    cin >> n;
    vector<string> s(n);
    rep(i,n){
        cin >> s[i];
    }
    vector<int> c(4);
    rep(i,4) c[i] = 0;
    rep(i,n){
        if (s[i] == "AC") c[0]++;
        else if (s[i] == "WA") c[1]++;
        else if (s[i] == "TLE") c[2]++;
        else if (s[i] == "RE") c[3]++;
    }
    cout << "AC x " << c[0] << endl;
    cout << "WA x " << c[1] << endl;
    cout << "TLE x " << c[2] << endl;
    cout << "RE x " << c[3] << endl;
    return 0;
}

Measured memory_bytes: 6428
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <cmath>
#include <iterator>
#include <numeric>
#include <iomanip>
#define FI first
#define SE second
#define EB emplace_back
#define REP(i, n) for (ll i = 0; i < n; i++)
#define INF 1100000000
#define LLINF 1100000000000000000LL
#define Decimal fixed << setprecision(20)
#define ALL(c) c.begin(),c.end()
#define SHOWVEC(v, sz) for(int i = 0; i < sz; i++) cerr << v[i] << ' '; cerr << endl;
#define SHOWX(x) cerr << #x << ": " << x << endl;
#define SHOWP(p) cerr << "[" << p.first << ',' << p.second << "]";

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

int main()
{
  string s;
  cin >> s;
  if (s == "Sunny") cout << "Cloudy" << endl;
  else if (s == "Cloudy") cout << "Rainy" << endl;
  else cout << "Sunny" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
#include <cassert>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	string s, t;
	cin >> s >> t;
	s += s;
	for (int i = 0; i < t.length(); i++)
	{
		if (s.substr(i, t.length()) == t) puts("Yes"), exit(0);
	}
	puts("No");
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){

    int n,a,b;
    scanf("%d %d %d",&n,&a,&b);

    int bus = a*n;
    int taxy = b;

    if(bus>taxy){
        printf("%d\n",taxy);
    }else{
        printf("%d\n",bus);
    }


    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
 
typedef long long ll;
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define forr(i, a, b) for(int i = (a); i < (int) (b); i++)
#define forn(i, n) forr(i, 0, n)
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define DBG(x) cerr << #x << " = " << (x) << endl
#define DBGV(v,n) forn(i,n) cout << v[i] << " "; cout << endl
#define esta(x,c) ((c).find(x) != (c).end())
#define RAYA cerr << "===============================" << endl
#define MAXN 2005

string funcion(ll n)
{
	string ans;
	ll m = 26;
	while(n)
	{
		n--;
		ll aux = (n)%m;
		ans.pb('a'+aux);
		n/=26;
		//DBG(n);
	}
	reverse(all(ans));
	return ans;
}

int main()
{ 
	FIN;
	
	#ifdef input
		//freopen("test1.txt", "r", stdin);
	#endif
	
	ll n;
	cin >> n;
	string ans = funcion(n);
	cout << ans << endl;
		
		
	
	return 0;
}


Measured memory_bytes: 3668
#include<bits/stdc++.h>
using namespace std ;
#define ll long long int 
#define pb push_back 
#define mp make_pair 
#define pii pair <int , int > 
#define pll pair < ll , ll >
int main(){
	ios_base::sync_with_stdio(false) ;
	cin.tie(NULL) ;
	int n ;
	ll ans = 0 ;
	cin >> n ;
	map < string , ll > m ;
	for(int i = 0 ; i < n ; i++){
		string s ;
		cin >> s ;
		sort(s.begin() , s.end() ) ;
		m[s]++ ;
	}	
	for(auto it : m){
		ll a = it.second ;
		ans += (a*(a-1))/2 ;
	}
	cout << ans ;
}

Measured memory_bytes: 11264
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll gcd (ll a, ll b) {
    return b ? gcd (b, a % b) : a;
}
int main()
{
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll k=c*d/gcd(c,d);
    ll nc=(b/c)-max(((a-1)/c),(ll)0);
    ll nd=(b/d)-max(((a-1)/d),(ll)0);
    ll ncd=(b/(k))-max(((a-1)/(k)),(ll)0);
    cout<<(b-a+1)-(nc+nd-ncd);
}


Measured memory_bytes: 256
def main(v1, v2, t1, t2):
    if v1 * v2 >= 0:  # どんどん離れる
        return 0
    # v1>0, v2<0とする
    d1 = abs(v1) * t1
    d2 = abs(v2) * t2

    if d1 > d2:  # 追いつけない
        return 0
    if d1 == d2:  # 毎回ちょうど追いつく
        return "infinity"

    dL = d2 - d1
    peak = (d1 + dL - 1) // dL
    if d1 % dL == 0:
        return peak * 2
    else:
        return peak * 2 - 1


t1, t2 = map(int, input().split())
a1, a2 = map(int, input().split())
b1, b2 = map(int, input().split())
print(main(a1-b1, a2-b2, t1, t2))

Measured memory_bytes: 9208
//過去問演習はここ
//問題名：Remainder Reminder
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long GCD(long long A, long long B) {
    if (B == 0) return A;
    else return GCD(B, A % B);
}
int main() {
    long long N; cin >> N;
    long long gcd = GCD(N, 360);
    long long LCM = N * 360 / gcd;
    cout << LCM / N << endl;
}

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

int main(){
  int n;
  while(cin>>n,n){
    int s[100][100];
    for(int i=0;i<n;++i){
      for(int j=0;j<n;++j){
        cin>>s[i][j];
      }
    }
    int max[100],min[100];
    for(int i=0;i<n;++i){
    	max[i]=0;
    	min[i]=1000000;
    }
    for(int i=0;i<n;++i){
      for(int j=0;j<n;++j){
        if(max[j]<s[i][j]) max[j]=s[i][j];
        if(min[i]>s[i][j]) min[i]=s[i][j];
      }
    }
    int ans=0;
    for(int i=0;i<n;++i){
      for(int j=0;j<n;++j){
        if(min[i] == max[j]){
          ans=max[j];
        }
      }
    }
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 1164
#include<iostream>
using namespace std;
#define ll long long
int main(){
	ll n;
	cin>>n;
	ll a[100001]={0};
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	int f=1;
	for(int i=n-1;i>0;i--)
	{
		if(a[i]<a[i-1])
		{
			a[i-1]--;
			if(a[i]<a[i-1])
			{
				f=0;
				break;
			}
		}
	}
	if(f==1){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>

int main(){
    long N, Q;
    std::string S;

    std::cin >> N >> Q;
    std::cin >> S;

    std::vector<long> ind;
    for(int i = 0; i < S.size() - 1; i++){
        if(S.substr(i, 2) == "AC"){
            ind.push_back(i);
        }
    }

    std::vector<long> ans;
    for(int i = 0; i < Q; i++){
        long x, y;
        std::cin >> x >> y;

        auto ind1 = std::distance(ind.begin(),std::lower_bound(ind.begin(), ind.end(), x - 1));
        auto ind2 = std::distance(ind.begin(),std::lower_bound(ind.begin(), ind.end(), y - 1));

        ans.push_back(ind2 - ind1);

    }

    for(auto x : ans){
        std::cout << x << std::endl;
    }

    return 0;
}


Measured memory_bytes: 2356
#include<stdio.h>
#include<stdlib.h>

#define INFTY 1000000001

void merge(int*,int,int,int);
void mergeSort(int*,int,int);
int cnt=0;
int main(){
  int A[10000000],i,j,n;
  scanf("%d",&n);
  for(i=0;i<n;i++)scanf("%d",&A[i]);
  mergeSort(A,0,n);
  for(i=0;i<n-1;i++)printf("%d ",A[i]);
  printf("%d\n",A[i]);
  printf("%d\n",cnt);
}

void merge(int *A,int left,int mid,int right){
  int n1,n2,i,j,k;
  n1=mid-left;
  n2=right-mid;
  int L[n1],R[n2];
  for(i=0;i<n1;i++)L[i]=A[left+i];
  for(j=0;j<n2;j++)R[j]=A[mid+j];
  L[n1]=INFTY;
  R[n2]=INFTY;
  i=0;j=0;

  for(k=left;k<right;k++){
    cnt++;
    if(L[i]<=R[j]){
      A[k]=L[i];
      i++;
    }else{
      A[k]=R[j];
      j++;
    }
  }
}
void mergeSort(int *A,int left,int right){
  int mid;
  if(left+1<right){
    mid=(left+right)/2;
    mergeSort(A,left,mid);
    mergeSort(A,mid,right);
    merge(A,left,mid,right);
  }
}



Measured memory_bytes: 5604
import numpy as np
n = int(input())
a =  [int(input()) for i in range(n)]
max_a_num = a.count(max(a))
b = sorted(a, reverse=True)
m1, m2 = b[0], b[1]
for i in range(n):
  if max_a_num == 1:
    if a[i] == m1:
      print(m2)
    else:
      print(m1)
  else:
    print(m2)


Measured memory_bytes: 24184
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define int long long
#define pb push_back
#define mod 1000000007
#define setbits(x) __builtin_popcountll(x)
#define zerobits(x) __builtin_ctzll(x)
#define inf 1e18
#define pre(x,y) fixed<<setprecision(y)<<x
#define pq priority_queue<int>
#define mpq priority_queue<int,vector<int>,greater<int>>
#define gcd(x,y) __gcd(x,y)
#define mp make_pair



int32_t main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,i,j,k;
    cin>>n>>k;
    int a[n];
    for(i=0;i<n;i++) cin>>a[i];
    vector<int> dp(k+1,0);
    dp[0]=0;
    for(i=1;i<=k;i++)
    {
    	for(j=0;j<n;j++)
    	{
    		if(i-a[j]>=0)
    		{
    			if(dp[i-a[j]]==0) {dp[i]=1;break;}
    		}
    	}
    }
    if(dp[k]) cout<<"First"<<endl;
    else cout<<"Second"<<endl;
	return 0;
}


Measured memory_bytes: 3972
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <functional>
#include <set>
#define DB cerr<<"D"<<endl
#define pb push_back
using namespace std; using ll=long long; using ld=long double; const int INF=1e9; const ll LINF=1e18; const double dINF = 1e18; const ld ldINF = 1e18; const double EPS = 1e-6;
template<typename T, typename U, typename O> void caut(T a, U b, O c){cout<<"("<<a<<","<<b<<","<<c<<") ";} template<typename T, typename U> void caut(T a, U b){cout<<"("<<a<<","<<b<<") ";} template<typename T> void caut(T a){cout<<"("<<a<<") ";}
using P=pair<int,int>;
const ll M = 1e9+7, mx = 200000;
void add(ll& x, ll y) {x+=y; x%=M;}
void chmax(ll& x, ll y) {if (x<y) x=y;}

const int up[]={1,-1,0,0}, lf[]={0,0,1,-1};
bool vaild(int x, int y, int hh, int ww){return 0<=x&&x<hh&&0<=y&&y<ww;}

template <typename T>
struct seg_Lp {
  // 区間更新、一点取得
  using F = function<T(T,T)>;
  const F f,g; const T ft; vector<T> lazy; int m, n, n2;
  seg_Lp(int _m, F _f, T _ft) : m(_m), f(_f), ft(_ft) {
    n=1; while(m>n) n<<=1;
    n2=2*n; lazy.resize(n2);
    for(int i=1;i<n2;i++) lazy[i]=ft;
  }

  // 増加
  void update(int k, int a, int b, int v, int l, int r) {
    if (a <= l && r <= b) {lazy[k] = f(lazy[k],v); return;}
    else if (a >= r || b <= l) return;
    else {
      update(2*k, a, b, v, l, (l+r)/2);
      update(2*k+1, a, b, v, (l+r)/2, r);
    }
  }

  // 増加（使用用）
  void update(int a, int b, int v) {
    update(1, a, b, v, 0, n);
  }

  // 合計
  T sum(int k) {
    //int fir = sum[k];
    k+=n;
    int ins = lazy[k];
    while(k>0) {
      k = k / 2;
      ins = f(ins,lazy[k]);
    }
    return ins; 
  }
  void print() {
    for(int i=1,j=0;i<n2;i++) {
      if (i+1 > (1<<j)) {cout<<endl; j++;}
      cout<<lazy[i]<<" ";
    } cout<<endl;
  }
};

struct tup {
  int x,y,c;
  bool operator<(const tup tt) const {
    if (c != tt.c) return c < tt.c;
    else if (x != tt.x) return x < tt.x;
    else return y < tt.y;
  }
  bool operator>(const tup tt) const {
    if (c != tt.c) return c > tt.c;
    else if (x != tt.x) return x > tt.x;
    else return y > tt.y;
  }
};

int main() {
  int n,m; cin>>n>>m;
  tup tp[n];
  for(int i=0;i<n;i++) cin>>tp[i].x>>tp[i].y;
  for(int i=0;i<n;i++) {
    tp[i].c=tp[i].y-tp[i].x+1;
  }
  sort(tp,tp+n);
  seg_Lp<int> sg(m+1,[](ll a,ll b){return a+b;},0);
  for(int i=1,j=0;i<=m;i++) {
    int an = n-j;
    for(int k=i;k<=m;k+=i) {
      an+=sg.sum(k);
    }
    cout<<an<<endl;
    while(j<n && tp[j].c <= i) {
      sg.update(tp[j].x,tp[j].y+1,1); j++;
    }
    //sg.print();
  }
}

Measured memory_bytes: 5504
#include <stdio.h>
#include <algorithm>
using namespace std;
int main(){
int a[1000000],n,mid;
long long int ans=0;
scanf("%d",&n);
mid=n/2;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
a[i]-=i;
}
sort(a,a+n);
for(int i=0;i<mid;i++)ans+=a[mid]-a[i];
for(int i=mid+1;i<n;i++)ans+=a[i]-a[mid];
printf("%lld\n",ans);
}


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

#define llint long long int

using namespace std;

int main(){
    int N, M;

    cin >> N >> M;

    vector<int> A(N);

    int sum = 0;

    for(int i = 0; i < N; i ++){
        cin >> A[i];

        sum += A[i];
    }
    sort(A.begin(), A.end());

    auto it = lower_bound(A.begin(), A.end(), sum / (4.0 * M));

    if(A.end() - it >= M){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repe(i, n) for (int i = 0; i <= (int)(n); i++)
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define ANS cout << ans << endl
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define REVERSE(a) reverse(all(a))
#define int ll
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORe(i, m, n) for(int i = m;i <= n;i++)
#define VIin(a) for(int i=0; i<a.size(); i++) cin >> a[i]
#define OUT(a) cout << a << endl
#define IN(a) cin >> a
#define INT(a) int a; cin >> a
typedef vector<int> VI;
typedef vector<VI> VVI;
const int MOD=1e9+7;
const long long INF = 1LL << 60;
/*最大公約数*/int gcd(int x, int y) { return y ? gcd(y,x%y) : x;}
/*最小公倍数*/int lcm(int a, int b) { int g = gcd(a, b); return a / g * b; }
/*素数判定*/int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*約数列挙*/vector<int> getDivisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------------------------------------
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n,a,b; IN(n >> a >> b);
    int ans = 0;
    FOR(i,1,n+1){
        string s = to_string(i);
        int sum = 0;
        rep(j,s.size()) sum += s[j] - '0';
        if(sum >= a && sum <= b) ans += i;
    }
    ANS;

    return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var r, D, x2000 int

	list := make([]int, 11)

	fmt.Scanf("%d %d %d", &r, &D, &x2000)

	list[0] = x2000

	for i := 1; i <= 10; i++ {
		list[i] = r*list[i-1] - D
		fmt.Println(list[i])
	}
}


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

typedef pair<int,int> P;
#define ll long long
#define ld long double
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define sz(x) ((int)(x).size())
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(x) (x).begin(),(x).end()

const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;
int main()
{
    int n;cin >> n;
    int sum = 0;
    int k = 0;
    for (int i = 1; i < 1000; i++)
    {
        sum += i;
        if(sum!=n)
        {
            continue;
        }
        k = i;
        cout << "Yes" << endl;
        int size = n*2/k;
        vector<int> vc[size];
        int num = 1;
        for (int i = 0; i < size; i++)
        {
            for (int j = i+1; j < size; j++)
            {
                vc[i].push_back(num);
                vc[j].push_back(num);
                num++;
            }
        }
        cout << size << endl;
        rep(i,size)
        {
            cout << sz(vc[i]) << " ";
            for (auto &&j : vc[i])
            {
                cout << j << " ";
            }
            cout  << endl;
        }
        return 0;
    }
    cout << "No" << endl;
    

}

Measured memory_bytes: 4364
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <cstdlib>
#include <memory.h>
#include <ctime>
#include <bitset>

using namespace std;

#define ABS(a) ((a>0)?a:-(a))
#define MIN(a,b) ((a<b)?(a):(b))
#define MAX(a,b) ((a<b)?(b):(a))
#define FOR(i,a,n) for (int i=(a);i<(n);++i)
#define FI(i,n) for (int i=0; i<(n); ++i)
#define pnt pair <int, int>
#define mp make_pair
#define PI 3.1415926535897
#define MEMS(a,b) memset(a,b,sizeof(a))
#define LL long long
#define U unsigned

vector<int> ans;

void addToPos(int p, int v) {
	vector<int> oAns = ans;
	ans.clear();
	ans.resize(oAns.size() + 1);
	ans[p] = v;
	FOR(i, 0, p) {
		ans[i] = oAns[i];
	}
	FOR(i, p + 1, ans.size()) {
		ans[i] = oAns[i - 1];
	}
}

void fillEmpty(int v) {
	FOR(i, 0, v) {
		ans.push_back(i);
	}
	FOR(i, 0, v) {
		ans.push_back(i);
	}
}

int main()
{
#ifdef Fcdkbear
	freopen("in.txt", "r", stdin);
	double beg = clock();
	//freopen("out.txt", "w", stdout);
#endif

	LL n;
	cin >> n;
	if (n == 1) {
		cout << 2 << endl;
		cout << 1 << " " << 1 << endl;
		return 0;
	}
	int fb = -1;
	int cnt = 0;
	int v = 0;
	for (int i = 40; i >= 0; --i) {
		if ((n >> i) & 1) {
			if (ans.size() == 0) {
				fb = i;
				fillEmpty(i);
				v = i - 1;
			}
			else {
				v++;
				addToPos(0, v);
				int need = i;
				int idx = ans.size() - 1;
				while (need > 0) {
					if (ans[idx] < fb) {
						need--;
					}
					idx--;
				}
				addToPos(idx + 1, v);
			}
			cnt++;
		}
	}
	addToPos(0, v + 1);
	addToPos(ans.size(), v + 1);
	printf("%d\n", ans.size());
	FOR(i, 0, ans.size()) {
		if (i) {
			printf(" ");
		}
		printf("%d", ans[i] + 1);
	}
	printf("\n");

#ifdef Fcdkbear
	double end = clock();
	fprintf(stderr, "*** Total time = %.3lf ***\n", (end - beg) / CLOCKS_PER_SEC);
#endif
	return 0;
}

Measured memory_bytes: 256
/*
    Reference :-
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define forn1(i, n) for (int i = 1; i < int(n); i++)
#define PI pair<int,int>
#define all(vec) vec.begin(),vec.end()
ll mod=1000000007;
ll power(ll n,ll k){
    ll ans=1;
    while(k){
        if(k&1)ans=(ans*n)%mod;
        k/=2;
        n=(n*n)%mod;
    }
    //ans=(ans-1+mod)%mod;
    return ans;
}

int main(){
    //std::ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string s;
    cin>>s;
    int fl=0;
    if(s.size()%2==1){
        cout<<"No";return 0;
    }
    for(int i=0;i<s.size();i+=2){
        if(!(s[i]=='h'&&s[i+1]=='i'))fl=1;
    }
    if(fl==0)cout<<"Yes";
    else cout<<"No";
	return 0;
}


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

signed main(){
  int N;cin>>N;
  double ans=0;
  for(int i=0;i<N;i++){
    double x;string u;cin>>x>>u;
    if(u=="JPY")ans+=x;
    else ans+=x*380000;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std; typedef long double ld; typedef long long ll;
typedef unsigned long long ull;
#define endl "\n"
#define MP make_pair
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORR(x,arr) for(auto& x:arr)
#define PII pair<int, int>
#define FI first 
#define SE second
#define ALL(x) (x).begin(), (x).end()
constexpr int INF=1<<30; constexpr ll LINF=1LL<<60;
template<class T>inline bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>inline bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//-------------------
int n;
ll k;
ll a[2000+5];
//unordered_map<int, int> mp;
int one[2000+5];

const int mod = 1000000007;
struct mint {
	ll x;
	mint(ll x=0):x(x%mod){}

	bool operator==(const mint a)const{return x==a.x;}
	bool operator!=(const mint a)const{return x!=a.x;}
	bool operator>=(const mint a){return (x >= a.x)? 1: 0;}
	bool operator<(const mint a){return !(*this>=a);}
	bool operator>(const mint a){return (x > a.x)? 1:0;}
	bool operator<=(const mint a){return !(*this>a);}
	mint& operator+=(const mint a) {
		if ((x += a.x) >= mod) x -= mod;
			return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += mod-a.x) >= mod) x -= mod;
			return *this;
	}
	mint& operator*=(const mint a) {
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint a) const {
		mint res(*this);
		return res+=a;
	}
	mint operator-(const mint a) const {
		mint res(*this);
		return res-=a;
	}
	mint operator*(const mint a) const {
		mint res(*this);
		return res*=a;
	}
	mint pow(ll t) const {
		if (!t) return 1;
			mint a = pow(t>>1);
			a *= a;  //2 square
		if (t&1) a *= *this; 
		return a;
	}
	// for prime mod
	mint inv() const {
		return pow(mod-2);
	}
	mint& operator/=(const mint a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint a) const {
		mint res(*this);
		return res/=a;
	}
};

int main(){
	cin >> n >> k;
	map<ll, int> cnt;
	map<ll, int> cntless;
	FOR(i,1,n) {cin >> a[i]; cnt[a[i]]++;}
	
	for(auto it = cnt.begin(); it!=cnt.end(); it++){
		if(it==cnt.begin()){
			cntless[it->first] = 0;
			continue;
		}
		auto prev_it = it;
		prev_it--;
		cntless[it->first] = cntless[prev_it->first] + cnt[prev_it->first];
		//cout << it->first << ' ' << cntless[it->first] << endl;
 		//cout << cntless[i] << ' ';
	}
	FOR(i,1,n-1){
		FOR(j,i+1,n){
			if(a[i] > a[j]) one[i]++;
		}
	}
	mint ans(0);
	FOR(i,1,n) ans += mint(k)*one[i];
	//cout << ans.x << endl;

	FOR(i,1,n){
		//cout << cntless[a[i]];
		ans += mint((k-1)*(k))*cntless[a[i]]/2;
	}
	cout << ans.x << endl; 
    return 0;
}


Measured memory_bytes: 384
#include <string>
#include <iostream>
#include <vector>
#include <stack>
#include <stdio.h>
#include <math.h>
#include <utility>
#include <algorithm>

int main()
{
	int H,W,h,w;
	std::cin >> H >> W >> h >> w;
	std::cout << (H - h)*(W - w);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef pair<int,int> pl;
ll a=1000000000+7;
map<int,ll> m;

void pf(int n){
  for(int i=2;i*i<=n;i++){
    if(n%i) continue;
    while(n%i==0){
      m[i]++;
      n/=i;
    }
  }
  if(n!=1) m[n]++;
}
int main(){
  int n; cin>>n;

  ll ans=1;
  for(int i=1;i<=n;i++){
    pf(i);
  }

  for(auto iter=m.begin();iter!=m.end();iter++){
    ans*=((iter->second)+1);
    ans%=a;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
    int h, w;
    while (1)
    {
        cin >> h >> w;
        if (h == 0 && w == 0) break;
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                if (i == 0 || i == h - 1){
                    cout << "#";
                }
                else if (j == 0 || j == w - 1){
                    cout << "#";
                }
                else {
                    cout << ".";
                }
            }
            cout << endl;
        }
        cout << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3072
#include<bits/stdc++.h>
using namespace std;
int main(){
	long long n;
	cin>>n;
	long long ans=0;
	long long count=0;
	if(n>=500){
		long long rem=n%500;
			ans=ans+(n/500);
			n=rem;
			count=ans*1000;
	}
	ans=(n/5)*5;
	count+=ans;
	cout<<count;
	
	
	
	return 0;
}

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

using namespace std;
typedef long long ll;

int N;
pair <pair <string, int>, int> p[110];

int main()
{
    ios_base::sync_with_stdio(0);
    
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> p[i].first.first >> p[i].first.second;
        p[i].first.second = -p[i].first.second;
        p[i].second = i + 1;
    }
    sort (p, p + N);
    for (int i = 0; i < N; i++)
        cout << p[i].second << "\n";
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
        long long n, c, x,xn,v;
       scanf("%lld",&n);
       scanf("%lld",&c);
       long long p =0;
       long long q = 0;
       long long pans1 = 0;
       long long qans1 = 0;
       long long pans2 =0;
       long long qans2 = 0;
       long long qzn = 0;
       long long pzn = 0;
       x = 0;
       for(int i =0;i<n;i++){
           scanf("%lld",&xn);
           scanf("%lld",&v);
           if(pans1 > (p-(xn-x))){
               pans1 = (p-(xn-x));
           }
           if(qans2 > (q-2*(xn-x))){
               qans2 = (q-2*(xn-x));
           }
           if(qzn-(p-(xn-x))>qans1 - pans1){
               qans1 =qzn ;
               pans1 = p-(xn-x);
           }
            if(pzn-(q-2*(xn-x))>pans2 - qans2){
            pans2 = pzn;
            qans2 = q-2*(xn-x);
        }
            p = p-(xn-x);
           q = q-2*(xn-x);
           
           
           q = q +v;
       
           p = p+v;
           if(qzn<q){
               qzn = q;
           }
           if(pzn<p){
               pzn = p;
           }
           x = xn;
          // printf("%lld %lld %lld %lld\n",pans1,qans1,pans2,qans2);
       }
        if(pans1 > (p-(c-x))){
               pans1 = (p-(c-x));
           }
           if(qans2 > (q-2*(c-x))){
               qans2 = (q-2*(c-x));
           }
       if(q-(p-(c-x))>qans1 - pans1){
               qans1 =q ;
               pans1 = p-(c-x);
           }
            if(p-(q-2*(c-x))>pans2 - qans2){
            pans2 = p;
            qans2 = q-2*(c-x);
        }
        //printf("%lld %lld %lld %lld\n",pans1,qans1,pans2,qans2);
p = p-(c-x);
           q = q-2*(c-x);
       // printf("%lld",p+qans1-pans1);
      // printf("%lld",p-c+pans2-qans2);
     if(p+qans1-pans1>p-c+pans2-qans2){
         printf("%lld",p+qans1-pans1);
     }
     else{
        // printf("%lld\n",p);
         printf("%lld",p-c+pans2-qans2);
     }

        return 0;
}

Measured memory_bytes: 128
import math
n, h = map(int,input().split())
thr = []
att = []
ans = 0
for i in range(n):
 a, b = map(int,input().split())
 att.append(a)
 thr.append(b)
thr.sort(reverse = True)
att.sort(reverse = True)


for m in range(n):
 if h > 0:
  if thr[m] > att[0]:
   h = h -thr[m]
   ans = ans+1
  else:
   h = h-att[0]
   ans = ans+1
if h > 0:
 turn = h/att[0]
 turn = math.ceil(turn)
 ans = ans+ turn

print(ans)

Measured memory_bytes: 11392
// clang-format off
#include <bits/stdc++.h>

#define mp make_pair
#define fst first
#define snd second
#define forn(i,n) for (int i = 0; i < int(n); i++)
#define forn1(i,n) for (int i = 1; i <= int(n); i++)
#define popcnt __builtin_popcount
#define ffs __builtin_ffs
#define ctz __builtin_ctz
#define clz __builtin_clz
#define all(a) (a).begin(), (a).end()
 
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
using pil = pair<int,ll>;
using pll = pair<ll,ll>;
template <typename T> using vec = vector<T>;
using vi = vec<int>;
using vl = vec<ll>;
template <typename T> using que = queue<T>;
template <typename T> using deq = deque<T>;

template <typename T> T id(T b) {return b;};
template <typename T> void chmax(T &x, T y) {if (x < y) x = y;}
template <typename T> void chmin(T &x, T y) {if (x > y) x = y;}
template <typename S, typename K> bool contains(S &s, K k) { return s.find(k) != s.end(); }
void fastio() { ios_base::sync_with_stdio(false); cin.tie(nullptr); }
constexpr ll TEN(int n) { if (n == 0) return 1LL; else return 10LL*TEN(n-1); }
// clang-format on

const ll MOD = TEN(9) + 7;
const int MAX_N = 200000;
int n;
vi g[MAX_N];
ll cnt[MAX_N];
ll dp[MAX_N];
ll fact[MAX_N + 1];
ll fact_inv[MAX_N + 1];
vl ans;

template <long long mod>
long long mod_pow(long long a, long long b) {
    if (b == 0) return 1;
    long long ret = mod_pow<mod>(a, b / 2);
    ret = ret * ret % mod;
    if (b % 2 == 1) ret = a * ret % mod;
    return ret;
}

void dfs(int i, int p) {
    ll ans = 1;
    ll c = 0;
    for (int j : g[i]) {
        if (j == p) continue;
        dfs(j, i);
        ans = ans * dp[j] % MOD * fact_inv[cnt[j]] % MOD;
        c = (c + cnt[j]) % MOD;
    }

    ans = ans * fact[c] % MOD;
    cnt[i] = c + 1;
    dp[i] = ans;
}

void pre_calc() {
    fact[0] = 1;
    for (ll i = 1; i <= MAX_N; i++) {
        fact[i] = i * fact[i - 1] % MOD;
    }

    for (ll i = 0; i <= MAX_N; i++) {
        fact_inv[i] = mod_pow<MOD>(fact[i], MOD - 2) % MOD;
    }
}

ll inv(ll x) {
    return mod_pow<MOD>(x, MOD - 2);
}

void go(int i, int p) {
    ans[i] = dp[i];

    for (int j : g[i]) {
        if (j == p) continue;
        ll dpi = dp[i];
        ll ci = cnt[i];
        ll dpj = dp[j];
        ll cj = cnt[j];

        dp[i] = dp[i] * fact_inv[n - 1] % MOD * inv(dp[j]) % MOD * fact[cj] % MOD * fact[n - 1 - cj] % MOD;
        cnt[i] = n - cj;
        //printf("dp[%d]=%lld cnt[%d]=%lld\n", i, dp[i], i, cnt[i]);
        dp[j] = dp[j] * fact_inv[cj - 1] % MOD * dp[i] % MOD * fact_inv[cnt[i]] % MOD * fact[n - 1] % MOD;
        cnt[j] = n;

        go(j, i);
        dp[i] = dpi;
        dp[j] = dpj;
        cnt[i] = ci;
        cnt[j] = cj;
    }
}

int main() {
    fastio();

    pre_calc();

    cin >> n;
    forn(i, n - 1) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    ans = vl(n);
    dfs(0, -1);
    go(0, -1);

    for (ll x : ans) {
        cout << x << "\n";
    }

    return 0;
}

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

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

#define all(x) (x).begin(),(x).end()

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  // freopen("out", "w", stdout);
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int h, w;
  cin >> h >> w;
  for (int i = 0; i < h; i++) {
    string s;
    cin >> s;
    cout << s << '\n' << s << '\n';
  }
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define repi(i, a, b) for (int i = (int)(a) ; i < (int)(b) ; i++)
#define rep(i, n) repi(i, 0, n)
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
struct Vec{
    double x, y;
};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
     return false;
}
template<class T>
T min(T a, T b)
{
    if (a < b) return a;
    return b;
}
template<class T>
T max(T a, T b)
{
    if (a > b) return a;
    return b;
}
using namespace std;
int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    // cout << fixed << setprecision(15);
    int h, w, k, cnt, ans=0;
    cin >> h >> w >> k;
    vector<string> c(h);
    rep(i, h) cin >> c[i];
  
    rep(ih, 1<<h) rep(iw, 1<<w){
        cnt = 0;
        rep(i, h) rep(l, w){
            if (ih & 1 << i) continue;
            if (iw & 1 << l) continue;
            if (c[i][l] == '#') cnt++;
        }
        if (cnt == k) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3632
from sys import setrecursionlimit
setrecursionlimit(10**6)

MOD = 10**9 + 7

N = int(input())
G = [[] for _ in range(N)]

for _ in range(N-1):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    G[x].append(y)
    G[y].append(x)

def dfs(pos: int, par: int):
    # posが白の時 -> 子はなんでも良い
    # posが黒の時 -> 子は全て白
    white = 1
    black = 1
    for v in G[pos]:
        if v != par:
            tmp = dfs(v, pos)
            white *= sum(tmp)
            black *= tmp[0]
            white %= MOD
            black %= MOD
    return [white, black]  # [白, 黒]

print(sum(dfs(0, 0))%MOD)

Measured memory_bytes: 99788
#include <bits/stdc++.h>
#define S second
#define F first
#define ll long long
#define ld long double

using namespace std;

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

map<pair<int, pair<int, int> >, int> mop;

char s[N];
int sum[3];

int main()
{
    scanf("%s", s);
    string a = string(s);
    scanf("%s", s);
    string b = string(s);
    reverse(a.begin(), a.end());
    puts(a == b ? "YES" : "NO");
    return 0;
}


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

int main(void)
{
    int N;
    multiset<int> A;
    cin >> N;
  	long long sum = 0;
    for (int i=0; i<N; ++i){
        int a;
        cin >> a;
        A.insert(a);
      	sum += a;
    }

  	vector<int> L(100000, -1);
  
    int Q;
    cin >> Q;
    for (int i=0; i<Q; ++i){
        int B, C;
        cin >> B >> C;

      	if(L[B-1] == -1){
          L[B-1] = A.erase(B);
        }
      	int tmp = L[B-1];
      	if(L[C-1] == -1){
          L[C-1] = A.count(C);
        }
        L[C-1] += L[B-1];
        L[B-1] = 0;
        
        sum = sum + tmp * (C - B);
        cout << sum << endl;
    }
    return 0;
}

Measured memory_bytes: 7852
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll int
#define N 100005
#define mod 1000000007
#define rep(i,j,k) for (ll i=j;i<=k;++i)
#define per(i,j,k) for (ll i=j;i>=k;--i)
using namespace std;
inline ll read(){
	char ch=getchar(); ll x=0,f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	while (ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	return x*f;
}
ll n,tot,ans,a[N<<2];
int main(){
	n=read();
	rep(i,1,n){
		ll x=read();
		a[++tot]=x-1;
		a[++tot]=x;
		a[++tot]=x+1;
	}
	sort(a+1,a+1+tot);
	for (ll l=1,r=1;l<=tot;l=++r){
		while (a[r+1]==a[l]) ++r;
		ans=max(ans,r-l+1);
	}
	printf("%d",ans);
}

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

using namespace std;

int main() {
	int a, b;
	while (cin >> a >> b) {
		int kou[110] = {0};
		kou[a]++;
		kou[b]++;
		while (1) {
			cin >> a >> b;
			if (a == 0 && b == 0) {
				break;
			}
			kou[a]++;
			kou[b]++;
		}
		int k = 0;
		for (int i = 0; i < 110; i++) {
			if (kou[i] % 2 == 1) {
				k++;
			}
		}
		//cout << k << endl;
		if (k == 2 && (kou[1] % 2 == 1) && (kou[2] % 2 == 1)) {
			cout << "OK" << endl;
		} else {
			cout << "NG" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1156
def count(s1, s2):
    c = 0
    for i in range(len(s1)):
        if not s1[i] == s2[i]:
            c += 1
    return c


s = input()

mid = len(s) // 2
if len(s) % 2 == 0:
    print(count(s[:mid], s[mid:][::-1]))
else:
    print(count(s[:mid], s[mid+1:][::-1]))



Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define endl "\n"

using namespace std;

int main()
{

    ll n, k;
    cin >> n >> k;

    vector<int> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    vector<int> dp(n);

    dp[0] = 0;

    for (int i = 1; i < n; i++)
    {
        dp[i] = INT_MAX;
        for (int j = 1; j <= k && i - j >= 0; j++)
        {
            int p = abs(arr[i] - arr[i - j]);
            dp[i] = min(dp[i - j] + p, dp[i]);
        }
    }

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


Measured memory_bytes: 1024
import sys
readline = sys.stdin.readline
H,W,D = map(int,input().split())
A = [list(map(int,readline().split())) for i in range(H)]
Q=int(input())
Qls = [list(map(int,readline().split())) for i in range(Q)]
X = []
for i in range(H):
    for j in range(W):
        X.append([A[i][j],i,j])
X.sort()
wa = [[0 for i in range(H*W//D+1)] for j in range(D+1)]
for i in range(1,H*W+1):
    qt = i//D
    mod = i%D
    if qt >= 1:
        wa[mod][qt]=wa[mod][qt-1]+abs(X[i-1][1]-X[i-1-D][1])+abs(X[i-1][2]-X[i-1-D][2])
for i in range(Q):
    qti = Qls[i][0]//D
    mod = Qls[i][0]%D
    qtf = Qls[i][1]//D
    print(wa[mod][qtf]-wa[mod][qti])

Measured memory_bytes: 46756
/** Author : Izanagi **/

#pragma warning(disable:4996)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("-ffloat-store")

#include <bits/stdc++.h>

using namespace std;

const long long Mod = 1e9 + 7;
const long long inf = 1e18;
const long long INF = 1e9 + 7;
const long long Lim = 1e5 + 1e3;
const double eps = 1e-10;

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

#define x first
#define y second
#define mp make_pair
#define pb push_back
#define mem(a,val) memset(a,val,sizeof(a))
#define all(v) v.begin(), v.end()
#define faster ios_base:: sync_with_stdio(false),cin.tie(0),cout.tie(0)

// Debugging Function

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
    cerr << *it << " = " << a << endl;
    err(++it, args...);
}

//------------------------X-----------------------------------//

int main()
{
    int n, k;

    cin >> n >> k;

    vector <int> h(n);

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

    vector <int> dp(n,INF);

    dp[0] = 0;

    for(int i=0; i<n; i++)
    {
        for(int j = i+1; j<= i+k; j++)
        {
           if(j < n)
           {
               dp[j] = min(dp[j],dp[i] + abs(h[i] - h[j]));
           }
        }
    }

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

    return 0;
}


Measured memory_bytes: 1024