akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

const int p=998244353,maxN=1<<15,g=3,ig=332748118;
int W[maxN],iW[maxN];
int fac[maxN],ifac[maxN],inv[maxN];
int qpow(int a,int k){
    int ans=1;
    while(k){
        if(k&1) ans=1LL*ans*a%p;
        a=1LL*a*a%p;
        k>>=1;
    }
    return ans;
}
 
int R[maxN];
void NTT(int d[],int n0,bool flg){
    int x=1,len=0;while(x<n0) x<<=1,len++;
    for(int i=0;i<x;i++){
        R[i]=(R[i>>1]>>1)|((i&1)<<(len-1));
        if(i<R[i]) swap(d[i],d[R[i]]);
    }
    for(int i=1,l=maxN/(i<<1);i<x;i<<=1,l>>=1)
    for(int j=0;j<x;j+=(i<<1))
    for(int k=0,u=0;k<i;k++,u+=l){
        int a0=d[j|k],a1=1LL*(flg?iW[u]:W[u])*d[j|i|k]%p;
        d[j|k]=(a0+a1)%p;d[j|i|k]=a0-a1+p;
    	if(d[j|i|k]>=p)d[j|i|k]-=p;
	}
    if(flg){
        int invx=qpow(x,p-2);
        for(int i=0;i<x;i++) d[i]=1LL*d[i]*invx%p;
    }
}

int N,M;

int F[205][maxN];
int G[maxN],H[maxN];

int C(int n,int m){
	if(n<m) return 0;
	return 1LL*fac[n]*ifac[m]%p*ifac[n-m]%p;
}

int main(){
	int w=qpow(g,(p-1)/maxN),iw=qpow(ig,(p-1)/maxN);
    W[0]=iW[0]=1;
    for(int i=1;i<maxN;i++)
        W[i]=1LL*W[i-1]*w%p,
        iW[i]=1LL*iW[i-1]*iw%p;
    inv[1]=ifac[0]=ifac[1]=fac[0]=fac[1]=1;
    for(int i=2;i<maxN;i++)
    	inv[i]=1LL*(p-p/i)*inv[p%i]%p,
    	fac[i]=1LL*fac[i-1]*i%p,
    	ifac[i]=1LL*ifac[i-1]*inv[i]%p;
    
    scanf("%d%d",&N,&M);
    F[0][0]=1;
    int n0=1;while(n0<((N+3)<<1)) n0<<=1;
    for(int j=1;j<=M;j++){
    	for(int i=0;i<n0;i++) G[i]=0;
    	for(int i=0;i<=N;i++) G[i]=1LL*F[j-1][i]*ifac[i]%p;
    	for(int i=0;i<n0;i++) H[i]=0;
    	for(int i=1;i<=N;i++) H[i]=ifac[i+2];
    	NTT(G,n0,0);NTT(H,n0,0);
    	for(int i=0;i<n0;i++) G[i]=1LL*G[i]*H[i]%p;
    	NTT(G,n0,1);
    	for(int i=0;i<=N;i++) F[j][i]=(1LL*fac[i+2]*G[i]%p+1LL*(1+i+C(i,2))%p*F[j-1][i]%p)%p;
	}
	
	int ans=0;
	for(int i=0;i<=N;i++) ans=(ans+1LL*C(N,i)*F[M][i]%p)%p;
	printf("%d\n",ans);
}

Measured memory_bytes: 10964
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	k := 1
	ok := false
	for ; k*(k-1)/2 <= n; k++ {
		if k*(k-1)/2 == n {
			ok = true
			break
		}
	}
	if !ok {
		fmt.Println("No")
		return
	}

	fmt.Println("Yes")
	fmt.Println(k)
	sets := [][]int{{1}, {1}}
	for q := 3; q <= k; q++ {
		a := (q-1)*(q-2)/2 + 1
		for i := 0; i < len(sets); i++ {
			sets[i] = append(sets[i], i+a)
		}
		ns := []int{}
		for v := a; v <= q*(q-1)/2; v++ {
			ns = append(ns, v)
		}
		sets = append(sets, ns)
	}
	for _, s := range sets {
		fmt.Print(len(s))
		for _, v := range s {
			fmt.Printf(" %d", v)
		}
		fmt.Println("")
	}
}


Measured memory_bytes: 5888
import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args)throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int a[] = new int[n + 1];
        int b[] = new int[n + 1];
        for(int i = 1;i <= n;i++){
            st = new StringTokenizer(br.readLine());
            int a1 = Integer.parseInt(st.nextToken());
            int b1 = Integer.parseInt(st.nextToken());
            a[i] = a1;
            b[i] = b1;
        }
        long add = 0;
        for(int i = n;i >= 1;i--){
            if((a[i] + add) % b[i] == 0)continue;
            long to_add = b[i] - ((a[i] + add) % b[i]);
            add += to_add;
        }
        System.out.println(add);
    }
}

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

int main(){
    long long n, m;
    cin >> n >> m;
    long long ans = (n - 2) * (m - 2);
    if(n == 1 and m == 1) ans = 1;
    else if(n == 1 or m == 1) ans = max(m-2, n-2);

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;
import java.lang.Math;
import java.util.Arrays;

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

        Scanner sc = new Scanner(System.in);

        int a[] = new int[3];
        a[0] = sc.nextInt();
        a[1] = sc.nextInt();
        a[2] = sc.nextInt();

        Arrays.sort(a);

        for(int i = 0; i < 3; i++){
            System.out.print(a[i]);
            if(i != 2)System.out.print(" ");
        }
        System.out.print("\n");
    }
  
}


Measured memory_bytes: 26216
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            if (x % 2 == 0 && x % 3 != 0 && x % 5 != 0) {
                System.out.println("DENIED");
                return;
            }
        }
        System.out.println("APPROVED");
    }
}

Measured memory_bytes: 21844
import java.util.*;
public class Main
{
  public static Scanner sc = new Scanner(System.in);
  public static void main(String[]args)
  {
    int n = sc.nextInt();
    int x = sc.nextInt();
    int t = sc.nextInt();
    
    int ans =0;
    while(n>0)
    {
      ans+=t;
      n=n-x;
    } 
    System.out.println(ans);
  }
}


Measured memory_bytes: 35620
#include<stdio.h>

int main() {
  int n, S[10000], q, t, sum = 0;

  scanf("%d", &n);
  for ( int i = 0; i < n; i++ ) scanf("%d", &S[i]);
  scanf("%d", &q);
  for ( int i = 0; i < q; i++ ) {
    scanf("%d", &t);
    for ( int j = 0; j < n; j++ ) {
      if (S[j] == t) {
        sum++;
        break;
      }
    }
  }

  printf("%d\n", sum);
  return 0;
}



Measured memory_bytes: 2732
#include <stdio.h>
int main(){
  int N,A,B,result;
  scanf("%d %d %d",&N,&A,&B);
  
  result = N*A;
  //printf("%d,%d\n",result,B);
  
  if(result < B) printf("%d\n",result);
  else printf("%d\n",B);
  
  return 0;
}

Measured memory_bytes: 128
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>
#include <memory.h>
#include <map>

using namespace std;

typedef long long ll;

const int MAXN = 2e5+1;

class UnionFindTree{
  ll par[MAXN];
  ll rank[MAXN];

public:
  void init(int n){
    for(ll i=0;i<n;i++){
      par[i] = i;
      rank[i] = 0;
    }
  }

  ll find(ll x){
    if(par[x] == x){
      return x;
    }else{
      return par[x] = find(par[x]);
    }
  }

  void unite(ll x, ll y){
    x = find(x);
    y = find(y);
    if(x == y) return;

    if(rank[x] < rank[y]){
      par[x] = y;
    }else{
      par[y] = x;
      if(rank[x] == rank[y]) rank[x]++;
    }
  }

  bool same(ll x, ll y){
    return find(x) == find(y);
  }

};

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int N, K, L; cin >> N >> K >> L;
  UnionFindTree a, b;
  // 0-indexed
  a.init(N);
  b.init(N);
  for(int i=0;i<K;i++){
    int p, q; cin >> p >> q;
    a.unite(p-1, q-1);
  }
  for(int i=0;i<L;i++){
    int r, s; cin >> r >> s;
    b.unite(r-1, s-1);
  }
  map<pair<int, int>, int> mp;
  for(int i=0;i<N;i++){
    mp[make_pair(a.find(i), b.find(i))]++;
  }
  for(int i=0;i<N-1;i++){
    cout << mp[make_pair(a.find(i), b.find(i))] << " ";
  }
  cout << mp[make_pair(a.find(N-1), b.find(N-1))] << endl;
}

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

#define MOD(N) ((N) % 1000000007)

typedef long long ll;

ll fact[100001];

int N,M;


int main()
{
	fact[0] = 1;

	for(ll i = 1;i <= 100000;i++)
	{
		fact[i] = MOD(fact[i - 1] * i);

	}
	ll result = 0;
	cin >> N >> M;
	if(max(N - M,M - N) <= 1)
	{
		result = MOD(fact[N]);
		result = MOD(fact[M] * result);
		if(N == M)
		{
			result = MOD(result * 2);
		}
	}
	cout << result << endl;
	return 0;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
using namespace std;
constexpr int kMod = 1000000007;
typedef long long LL;

template<typename T>
istream& operator >> (istream& is, vector<T>& vs){
  for(T& v: vs) is >> v;
  return is;
}
template<typename T>
ostream& operator << (ostream& os, vector<T>& vs){
  for (const T& v : vs) os << v << " ";
  return os;
}

int main() {
  int N; cin >> N;
  vector<pair<int, int>> ps(N);
  for (int i = 0; i < N; ++i) cin >> ps[i].first >> ps[i].second;

  double total = 0;
  int count = 0;
  std::vector<int> ids(N);
  for (int i = 0; i < N; ++i) ids[i] = i;
  do {
    auto p1 = ps[ids[0]];
    for (int id : ids) {
      auto p2 = ps[id];
      double dx = p1.first - p2.first;
      double dy = p1.second - p2.second;
      total += hypot(dx, dy);
      p1 = p2;
    }
    ++count;
  } while(next_permutation(ids.begin(), ids.end()));
  printf("%.9f\n", total/count);
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline

class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.rank_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.rank_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)


if __name__ == "__main__":
    N,M = map(int,input().split())
    ans = N
    node_list = [UnionFindNode(i) for i in range(N)]
    for i in range(M):
        X,Y,Z = map(int,input().split())
        X -= 1
        Y -= 1
        if node_list[X].root() != node_list[Y].root():
            ans -= 1
        node_list[X].unite(node_list[Y])
    print(ans)

Measured memory_bytes: 32884
c = int(input())  # 1
b = int(input())  # 2
a = int(input())  # 10
x = int(input()) // 50
ans = 0
for i in range(a + 1):
    for j in range(b + 1):
        for k in range(c + 1):
            if x == i + 2 * j + 10 * k:
                ans += 1
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001001001001
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(v) v.begin(),v.end()
int main(){
    vector<int>a(3);
    rep(i,3){
        cin>>a.at(i);
    }
    sort(a.begin(),a.end());
    int A=a.at(0)+a.at(1);
    int B=a.at(2);
    if(A==B){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}


Measured memory_bytes: 3596
#include <iostream>
#define ll long long
using namespace std;
const int N = 5009;
int n,k;
int p[N],c[N],sp[N],avail[N];
long long f[N][N];
int main(){
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> p[i];
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1; i <= n; i++){
        memset(avail,0,sizeof(avail));
        int j = i , cnt = 0;
        while (avail[p[j]] == 0){
            cnt++;
            f[i][cnt] = f[i][cnt - 1] + c[p[j]];
            avail[p[j]] = 1;
            j = p[j];
        }
        sp[i] = cnt;
    }
    ll ans = -1e18;
    for (int i = 1; i <= n; i++){
        ll pos_max = 0 , val = -1e18;
         for (int j = 1; j <= min(sp[i],k); j++)
            if (f[i][j] > val){
                val = f[i][j];
                pos_max = j;
            }
        ans = max(ans,f[i][pos_max] + 1LL * ((k - pos_max)/sp[i]) * f[i][sp[i]]);
        ans = max(ans , 1LL * (k/sp[i]) * f[i][sp[i]] + f[i][k % sp[i]]);
        ans = max(ans,f[i][pos_max]);
    }
    cout << ans;
}

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

#define MAX 3

int main() {
	int c[MAX][MAX], a[MAX], b[MAX];
	a[0] = 0;
	for (int i = 0; i < MAX; i++)
		for (int j = 0; j < MAX; j++)
			cin >> c[i][j];
	for (int i = 0; i < MAX; i++)
		b[i] = c[0][i] - a[0];
	for (int i = 1; i < MAX; i++)
		a[i] = c[i][0] - b[0];
	for (int i = 1; i < MAX; i++) {
		for (int j = 1; j < MAX; j++) {
			if (a[i] + b[j] != c[i][j]) {
				cout << "No" << endl;
				return 0;
			}
		}
	}
	cout << "Yes" << endl;
	return 0;
}


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

#define                           int                         long long
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<int,int>
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define                           double                      long double



using namespace std;

const int inf=1e18;
const int mod=1e9+7;
const int M=100009;
inline int bigmod(int B,int P){int R=1;while(P>0){if(P&1){R=(R*B)%mod;}P>>=1;B=(B*B)%mod;}return R;}


 main()

{
    fast
    double yo;
    cin>>yo;
    double x=yo/3.000;
    double ses=x*x*x;
    cout<<fixed<<setprecision(15)<<ses<<endl;
    return 0;

}













Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD = 1e9 + 7;
vector<long long> fact_inv, inv;
void init_nCk(int SIZE) {
  fact_inv.resize(SIZE + 5);
  inv.resize(SIZE + 5);
  fact_inv[0] = fact_inv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < SIZE + 5; i++) {
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD;
  }
}
long long nCk(int n, int k) {
    assert(!(n < k));
    assert(!(n < 0 || k < 0));
    long long ans = 1;
    for (int i = n; i >= n - k + 1; i--) {
        ans*=i;
        ans%=MOD;
    }
    return ans * fact_inv[k] % MOD;
}
int main() {
  ll N,a,b,x=1,d,e;
  cin>>N>>a>>b;
  for(ll i=0;i<N/10;i++){
    x*=1024;
    x%=MOD;
  }
  for(ll i=0;i<N%10;i++){
    x*=2;
    x%=MOD;
  }
  x--;
  if(a<=N){init_nCk(a);d=nCk(N,a);x-=d;}
  if(b<=N){init_nCk(b);e=nCk(N,b);x-=e;}
  cout<<(x+2*MOD)%MOD<<endl;
}

Measured memory_bytes: 5988
/*
      author : nishi5451
      created: 11.08.2020 00:26:41
*/

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


int main(){
    int a,b;
    cin >> a >> b;
    cout << (a+b)%24 << endl;
    return 0;
}

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

using namespace std;

#define forn(i, n) for (ll i = 0; i < (ll) (n); ++i)
#define sz(a) static_cast<int>((a).size())
#define pb emplace_back
#define mp make_pair
#define endl '\n'
#define f first
#define s second

#ifdef SEREZHKA
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...)
#endif

template<typename T>
void _dbg(const char* _s, T _h) { cerr << _s << " = " << _h << "\n"; }

template<typename T, typename... Ts>
void _dbg(const char*_s, T _h, Ts... _t) {
    int _b = 0;
    
    while (((_b += *_s == '(') -= *_s == ')') != 0 || *_s != ',')
        cerr << *_s++;
    
    cerr << " = " << _h << ",";
    _dbg(_s + 1, _t...);
}

using ll = long long;

const ll INF = static_cast<ll>(1e9) + 7ll;
const ll LINF = INF * INF;
const int MAXN = static_cast<int>(2e5) + 17;

int n, m;
string s[MAXN];

bool read() {
    if (!(cin >> n >> m))
        return false;

    forn (i, n)
        cin >> s[i];

    return true;
}

void solve() {
    int i = 0, j = 0;

    while (i < n || j < m) {
        if (s[i][j] != '#') {
            cout << "Impossible\n";
            return ;
        }

        s[i][j] = '.';

        if (i == n - 1 && j == m - 1)
            break;

        if (i < n && s[i + 1][j] == '#')
            ++i;
        else if (j < m && s[i][j + 1] == '#')
            ++j;
        else {
            cout << "Impossible\n";
            return ;
        }
    }

    int cnt = 0;

    forn (i, n)
        cnt += count(s[i].begin(), s[i].end(), '#');

    cout << (cnt ? "Impossible" : "Possible") << endl;
}

int main() {
    cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    
#ifdef SEREZHKA
    freopen("file.in", "r", stdin);
#endif
    
    while (read())
        solve();
    
    return 0;
}



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

#define f(i,a,b) for (int i = a; i < b; i++)

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	clock_t start = clock();
#endif

	int n,m,a,b;
	cin>>n>>m>>a>>b;
	char board[n][m];
	f(i,0,n) f(j,0,m) board[i][j] = '.';
	if (((n*(m/2)&1)^(a&1))&&(n*m&1)&&n>=3&&m>=3&&a>=2&&b>=2) {
		a-=2;
		b-=2;
		board[n-1][m-1] = '>';
		board[n-1][m-2] = '<';
		board[n-3][m-1] = '^';
		board[n-2][m-1] = 'v';
		board[n-3][m-3] = '<';
		board[n-3][m-2] = '>';
		board[n-2][m-3] = '^';
		board[n-1][m-3] = 'v';
	}
	for (int j = 0; n&1 && a && j < m-(m&1); j+=2)
		if (board[n-1][j] == '.' && board[n-1][j+1] == '.')
			board[n-1][j] = '<', board[n-1][j+1] = '>', a--;
	for (int i = 0; m&1 && b && i < n-(n&1); i+=2)
		if (board[i][m-1] == '.' &&  board[i+1][m-1] == '.')
			board[i][m-1] = '^', board[i+1][m-1] = 'v', b--;
	for (int i = 0; i < n-(n&1); i += 2) for (int j = 0; j < m-(m&1); j += 2) {
		if (a) {
			int x = min(2,a);
			f(d,0,x) {
				if (board[i+d][j] == '.' && board[i+d][j+1] == '.') {
					board[i+d][j] = '<', board[i+d][j+1] = '>',a--;
				}
			}
		} else if (b) {
			int x = min(2,b);
			f(d,0,x) 
			if (board[i][j+d] == '.' && board[i+1][j+d] == '.') {
				board[i][j+d] = '^', board[i+1][j+d] = 'v', b--;
			}
		}		
	}
	if (a || b) cout << "NO" << endl;
	else {
		cout << "YES" << endl;
		f(i,0,n) {
			string s;
			f(j,0,m) s += board[i][j];
			cout << s << endl;
		}
	}

#ifdef LOCAL
	cout << setprecision(12) << (long double)(clock()-start) / CLOCKS_PER_SEC << endl;
#endif
	
	return 0;
}



Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl '\n';

int main(){
    ios_base::sync_with_stdio(0); cin.tie(nullptr);
    ll n; cin>>n;
    ll q, k=0, mx=0;
    for(ll i=1; i<=n; i++){
    	cin>>q;
    	mx = max(mx,q);
    	if(q<mx) k+=mx-q;
    }
    cout<<k<<endl;
    return 0;
}

Measured memory_bytes: 3644
from collections import Counter
import sys
sys.setrecursionlimit(10 ** 6)


# パート2 の解法
def dfs(n):
    if memo[n] >= 0:
        rst = memo[n]
    else:
        tmp = n
        one = 0
        while tmp > 0:
            one += tmp & 1
            tmp >>= 1
        m = n % one
        rst = 1 if m == 0 else 1 + dfs(m)
        memo[n] = rst
    return rst


N = int(input())
X = list(map(int, list(input())))
one = Counter(X)[1]

# パート1の解法.
# Xがオール0のとき, 1が一つしか含まれないとき、を場合分けする
if one > 1:
    Sm = 0
    mm = one - 1
    tm = 1
    for i in range(N - 1, -1, -1):
        tm %= mm
        if X[i] == 1:
            Sm += tm
            Sm %= mm
        tm *= 2

Sp = 0
mp = one + 1
tp = 1
for i in range(N - 1, -1, -1):
    tp %= mp
    if X[i] == 1:
        Sp += tp
        Sp %= mp
    tp *= 2


memo = [-1] * (2 * (10 ** 5) + 10)
memo[0] = 0

for i in range(N):
    # 解法パート1
    if X[i] == 0:
        m = (Sp + pow(2, N - 1 - i, mp)) % mp
    elif one > 1:
        m = (Sm - pow(2, N - 1 - i, mm)) % mm
    else:  # X[i] == 1 かつ 全体で1が一つしかない 場合 は必ず0になる
        print(0)
        continue
    cnt = 1

    # 解法パート2
    cnt += dfs(m)
    print(cnt)

Measured memory_bytes: 96900
import numpy as np
n = input()
num_list = list(map(int,input().split()))
num_list = np.sort(num_list)

flag = False
for i in range(len(num_list)):
    if i == len(num_list)-1:
        break
    
    if num_list[i] == num_list[i+1]:
        flag = True
        break
        
if flag:
    print('NO')

else:
    print('YES')

Measured memory_bytes: 34172
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
using ll = long long;
int main(){
  ll n,a,b;
  cin>>n>>a>>b;
  if((b-a)%2==0){
    cout<<(b-a)/2<<endl;
  }else if(a-1<n-b){
    cout<<a+(b-a-1)/2<<endl;
  }else{
    cout<<(n-b+1)+(b-a-1)/2<<endl;
  }
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char x = sc.next().charAt(0);
        char y = sc.next().charAt(0);
        if(x > y) System.out.println(">");
        else if(x < y) System.out.println("<");
        else System.out.println("=");
    }
}

Measured memory_bytes: 35540
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int mp[5][105];
int p[5][105];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&mp[1][i]);
	for(int i=1;i<=n;++i)
		scanf("%d",&mp[2][i]);
	p[1][1]=mp[1][1];p[2][1]=mp[2][1]+mp[1][1];
	for(int i=2;i<=n;++i){
		p[1][i]=p[1][i-1]+mp[1][i];
		p[2][i]=max(p[1][i],p[2][i-1])+mp[2][i];
	}
	printf("%d\n",p[2][n]);
	return 0;
}

Measured memory_bytes: 128
long lcm(long a, long b){
	  return a*b / gcd(a, b);
}
void main(){
	long a, b;
	readf("%d %d", &a, &b);
	writeln(lcm(a, b));
}

import std.stdio, std.conv, std.algorithm, std.numeric, std.string, std.math;

// 1要素のみの入力
T _scan(T= int)(){
	return to!(T)( readln().chomp() );
}

// 1行に同一型の複数入力
T[] _scanln(T = int)(){
	T[] ln;
	foreach(string elm; readln().chomp().split()){
		ln ~= elm.to!T();
	}
	return ln;
}


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

int main() {
  int H,W;
  cin >> H >> W;
  vector<vector<bool>> mp(H+2,vector<bool> (W+2,false));
  vector<vector<int>> scorey(H+2,vector<int> (W+2,0));
  vector<vector<int>> scoret(H+2,vector<int> (W+2,0));
  string s;
  for (int i=0; i<H; i++) {
    cin >> s;
    for (int j=0; j<W; j++) {
      if (s[j] == '.') {
        mp[i+1][j+1] = true;
      }
    }
  }
  
  for (int i=1; i<H+1; i++) {
    for (int j=1; j<W+1; j++) {
      if (mp[i][j]) {
        scorey[i][j] = scorey[i][j-1]+1;
      }
    }
  }
  for (int i=H; i>0; i--) {
    for (int j=W; j>0; j--) {
      if (mp[i][j]) {
        scorey[i][j] = max(scorey[i][j],scorey[i][j+1]);
      }
    }
  }
  
  for (int i=1; i<H+1; i++) {
    for (int j=1; j<W+1; j++) {
      if (mp[i][j]) {
        scoret[i][j] = scoret[i-1][j]+1;
      }
    }
  }
  for (int i=H; i>0; i--) {
    for (int j=W; j>0; j--) {
      if (mp[i][j]) {
        scoret[i][j] = max(scoret[i+1][j],scoret[i][j]);
      }
    }
  }
  
  int ans = 0;
  int term = 0;
  
  for (int i=1; i<H+1; i++) {
    for (int j=1; j<W+1; j++) {
      if (mp[i][j]) {
        term = scoret[i][j] + scorey[i][j];
        ans = max(ans,term);
      }
    }
  }
  
  cout << ans-1 << endl;
  return 0;
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int Q; cin >> Q;
  vector<bool> isP(101010,true);
  isP[0] = isP[1] = false;
  for(int i = 2; i < 101010; i++) {
    if (isP[i])
        for (int j = i * 2; j < 101010; j += i)
          isP[j] = false;
  }
  vector<int> is2017(101010, false);
  rep(i, 1, 101010) {
    if(i&1 && isP[i] && isP[(i + 1) / 2]) is2017[i] = true;
  }
  vector<int> sum(101011);
  rep(i, 0, 101010)  sum[i+1] = sum[i] + is2017[i];
  int ans = 0;
  rep(i, 0, Q) {
    int l, r;
    cin >> l >> r;
    cout << sum[r + 1] - sum[l] << "\n";
  }
  return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
//#include <boost/array.hpp>
//#include <boost/range/numeric.hpp>
//#include <boost/range/algorithm.hpp>
//#include <boost/multiprecision/cpp_int.hpp>

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
//using namespace boost::multiprecision;

constexpr long long INF = LLONG_MAX;
constexpr long long MOD = 1000000007;
constexpr long double PI = M_PI;

#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); ++i)
#define RFOR(i,n,r) for(ll i = (ll)(n-1); i >= r; --i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,n,0)
#define ALL(x) x.begin(),x.end()
#define CALL(x) x.cbegin(),x.cend()
#define RALL(x) x.rbegin(),x.rend()
#define CRALL(x) x.crbegin(),x.crend()

#define cout cout << fixed << setprecision(12)
#define dbglf cerr << '\n'

#define ACCM(arr) accumulate(ALL(arr),0LL)
#define Yes(ex) cout << ((ex) ? "Yes" : "No") << endl
#define YES(ex) cout << ((ex) ? "YES" : "NO") << endl

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using vi = vector<ll>;
using vvi = vector<vi>;
using vp = vector<pair<ll, ll>>;
using vs = vector<string>;
using vc = vector<char>;
using lst = list<ll>;
using pq = priority_queue<ll>;

template < typename T >
inline void veccin(vector<T>& v) {
    for (auto && e : v) { cin >> e; }
}

template < typename T >
inline void dbg(T a) { cerr << a << ' '; }

ll n, m, k;
ll ans = 0, sum = 0, cnt = 0;
//ld d;
string s/*1, s2, s3*/;
char c/*1, c2, c3*/;
bool flag = false;

/*--------------------template--------------------*/

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

    cin >> n>>m;
	vi h(n);veccin(h);
	vi a(m),b(m);
	vi dai(n,0);
	REP(i,m){
    	cin >>a[i]>>b[i];
   		if(h[a[i]-1]==h[b[i]-1]){
    	dai[a[i]-1] = 1;
    	dai[b[i]-1] = 1;
    }else if (h[a[i]-1]<h[b[i]-1])
    	dai[a[i]-1] = 1;
    	else
        dai[b[i]-1] = 1;
    }
    cout << count(ALL(dai),0) << endl;
}


Measured memory_bytes: 6368
def resolve():
    N, K = map(int, input().split())
    n= 300010
    #####segfunc######
    def segfunc(x, y):
        return max(x, y)

    def init(init_val):
        # set_val
        for i in range(n):
            seg[i + num - 1] = init_val[i]
            # built
        for i in range(num - 2, -1, -1):
            seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k - 1) // 2
            seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = segfunc(res, seg[p])
            if q & 1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    #####単位元######
    ide_ele = 0

    # num:n以上の最小の2のべき乗
    num = 2 ** (n - 1).bit_length()
    seg = [ide_ele] * 2 * num

    #init([0]*300005)

    for i in range(N):
        a = int(input())
        b = query(max(0, a-K), min(a+K+1, 300001))
        update(a, b+1)
    print(query(0, 300000))
resolve()

Measured memory_bytes: 83116
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <cstdio>
#include <set>

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

using namespace std;

int uf[1001];
void inituf() {
  for (int i = 0; i < 1001; ++i) {
    uf[i] = -1;
  }
}

int root(int i) {
  if(uf[i] < 0) {
    return i;
  } else {
    return uf[i] = root(uf[i]);
  }
}

void join(int i, int j) {
  int ri = root(i);
  int rj = root(j);
  if (uf[ri] > uf[rj]) {
    uf[ri] = rj;
  } else {
    if (uf[ri] == uf[rj])
      --uf[ri];
    uf[rj] = ri;
  }
}

int main() {
  int v,d;
  while(scanf("%d%d",&v,&d) != EOF) {
    vector<int> a;
    int fibo[v+3];
    fibo[0] = 1;
    fibo[1] = 2;
    a.push_back(2);
    for (int i = 2;i <= v; ++i) {
      fibo[i] = fibo[i-1] + fibo[i-2];
      fibo[i] %= 1001;
      a.push_back(fibo[i]);
    }
    sort(begin(a),end(a));
    auto itr = unique(begin(a),end(a));
    a.resize(itr - begin(a));
    inituf();
    for (int i = 1; i < a.size(); ++i) {
      if (a[i] - a[i-1] < d) {
        join(i,i-1);
      }
    }
    set<int> rts;
    for (int i = 0; i < a.size(); ++i) {
      rts.insert(root(i));
    }
    cout << rts.size() << endl;
  }
  return 0;
}

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

int main(){
  string S;
  cin >> S;
  if(S=="abc" || S=="acb" || S=="bac" || S=="bca" || S=="cab" || S=="cba"){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
use std::collections::HashMap;

fn main() {
    let n = read::<usize>();
    let mut map: HashMap<Vec<char>, usize> = HashMap::new();
    let mut ans = 0usize;

    for _ in 0..n {
        let mut s: Vec<char> = read::<String>().chars().collect();
        s.sort();

        let insert_value = if let Some(value) = map.get(&s) {
            ans += *value;
            value + 1
        }
        else {
            1
        };

        map.insert(s, insert_value);

    }

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

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

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

Measured memory_bytes: 16636
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cerr << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cerr<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 500010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
mt19937 rng; //use it by rng() % mod, shuffle(all(vec), rng)
///////////////////////////////////////////////////////////////////////////////////////////////////

int N;
int A[MAX_N];
int ans[MAX_N];

void solve() {
	cin >> N;
	rep(i, 1, N + 1) cin >> A[i];
	vector<int> vec;
	for(int i = N; i >= 1; i--) {
		int tmp = A[i];
		for(int j = i * 2; j <= N; j += i) {
			tmp ^= ans[j];
		}
		ans[i] = tmp;
		if(ans[i]) vec.pb(i);
	}
	cout << sz(vec) << "\n";
	rep(i, 0, sz(vec)) {
		cout << vec[i] << "\n";
	}
}

uint32_t rd() {
	uint32_t res;
#ifdef __MINGW32__
	asm volatile("rdrand %0" :"=a"(res) ::"cc");
#else
	res = std::random_device()();
#endif
	return res;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
    cerr << fixed;
	cerr.precision(6);
	rng.seed(rd());
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
	if(!freopen("in.txt", "rt", stdin)) return 1;
#endif	
	solve();
    cerr << "Time: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}



Measured memory_bytes: 3192
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define sz(v) v.size()
#define INF 1000000009
// aよりもbが大きいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}

int main(){
  string S;
  cin >> S;
  ll ans = 0;
  rep(i, sz(S)){
    ll c = 0;
    rep2(j, i, sz(S)){
      if(S.at(j) == 'A' || S.at(j) == 'C' || S.at(j) == 'G' || S.at(j) == 'T'){
        c++;
      }
      else{
        break;
      }
    }
    chmax(ans, c);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
#print(s)
for i in range(h):
    for j in range(w):
        #print(i,j)
        if s[i][j]=="#":
            if i!=0:
                if s[i-1][j]=="#":
                    continue
            if i!=h-1:
                if s[i+1][j]=="#":
                    continue
            if j!=0:
                if s[i][j-1]=="#":
                    continue
            if j!=w-1:
                if s[i][j+1]=="#":
                    continue
            print("No")
            exit()
print("Yes")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(begin, i, end) for (int i = begin; i < (int)(end); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1000000007;

int main()
{
    int N;
    string S;
    cin >> N >> S;
    vector<int> num1(N + 1, 0), num2(N + 1, 0);
    rep(1, i, N + 1)
    {
        if (S.at(i - 1) == 'W')
        {
            num1.at(i) = num1.at(i - 1) + 1;
        }
        else
        {
            num1.at(i) = num1.at(i - 1);
        }
    }

    reverse(all(S));
    rep(1, i, N + 1)
    {
        if (S.at(i - 1) == 'E')
        {
            num2.at(i) = num2.at(i - 1) + 1;
        }
        else
        {
            num2.at(i) = num2.at(i - 1);
        }
    }
    reverse(all(num2));

    int num, ans = N;
    rep(0, i, N + 1)
    {
        if (i != N)
        {
            num = num1.at(i) + num2.at(i + 1);
            ans = min(ans, num);
        }
        else
        {
            ans = min(ans, num1.at(N));
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;
ll MOD = 1e9 + 7;

int main() {
    ll n;
    cin >> n;
    vector<ll> p;
    for (ll a = 2; a * a <= n; a++) {
        if (n % a == 0) {
            p.push_back(0);
            while (n % a == 0) {
                p.back()++;
                n /= a;
            }
        }
    }
    if (n != 1) p.push_back(1);
    int cnt = 0;
    for (int i = 0; i < (int)p.size(); i++) {
        int num = 1;
        while (p[i] - num >= 0) {
            cnt++;
            p[i] -= num;
            num++;
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
const int MAXN=110;
int n,m,a[MAXN],sum;
int main () {
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) {scanf("%d",&a[i]);sum+=a[i];}
	int tmp=((sum%(4*m))?sum/(4*m)+1:sum/(4*m)),res=0;
	for (int i=1;i<=n;i++) {if (a[i]>=tmp) {res++;}}
	if (res>=m) {printf("Yes\n");}
	else {printf("No\n");}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl "\n"
#define sz(x) ((ll)(x).size())
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define prt(x) cout << (x)
#define prtl(x) cout << (x) << endl
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define rrep(i,a,b) for(ll i=a; i>b; i--)
#define mp(a, b) make_pair(a, b)
using namespace std;
using vi = vector<int>;
using vll = vector<long long int>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vc = vector<char>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<long long int>>;
using vvc = vector<vector<char>>;
using ll = long long;
using P = pair<long long int, long long int>;
using Map = map<long long int, long long int>;

int main(){
    ll A; string B;
    cin >> A >> B;
    string m = "...";
    m[0] = B[0];
    m[1] = B[2];
    m[2] = B[3];
    ll v = stoi(m);
    ll C = A*v;
    C -= C%100;
    C /= 100;
    prt(C);
}


Measured memory_bytes: 3532
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
  
using namespace std;
  
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P> PP;
  
static const double EPS = 1e-8;
  
int tx[] = {0,1,0,-1};
int ty[] = {-1,0,1,0};

int main(){
  int a,b;
  while(~scanf("%d %d",&a,&b)){
    printf("%lf\n",(double)(a*b) / 3.305785);
  }
}

Measured memory_bytes: 1216
from collections import Counter
def main():
    n=int(input())
    S=tuple(input() for _ in range(n))
    D=Counter(S)
    m=max(D.values())
    L = [d[0] for d in D.items() if d[1]==m]
    L=sorted(L)
    for l in L:
        print(l)
main()

Measured memory_bytes: 35468
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<functional>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cassert>
#include<ctime>
using namespace std;

#define mind(a,b) (a>b?b:a)
#define maxd(a,b) (a>b?a:b)
#define absd(x) (x<0?-(x):x)
#define pow2(x) ((x)*(x))
#define rep(i,n) for(int i=0; i<n; ++i)
#define repr(i,n) for(int i=n-1; i>=0; --i)
#define repl(i,s,n) for(int i=s; i<=n; ++i)
#define replr(i,s,n) for(int i=n; i>=s; --i)
#define repf(i,s,n,j) for(int i=s; i<=n; i+=j)
#define repe(e,obj) for(auto e : obj)

#define SP << " " <<
#define COL << " : " <<
#define COM << ", " <<
#define ARR << " -> " <<
#define PNT(STR) cout << STR << endl
#define POS(X,Y) "(" << X << ", " << Y << ")"
#define DEB(A) " (" << #A << ") " << A
#define DEBREP(i,n,val) for(int i=0; i<n; ++i) cout << val << " "; cout << endl
#define ALL(V) (V).begin(), (V).end()
#define INF 1000000007
#define INFLL 1000000000000000007LL
#define EPS 1e-9

typedef unsigned int uint;
typedef unsigned long ulong;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define P_TYPE int
typedef pair<P_TYPE, P_TYPE> P;
typedef pair<P, P_TYPE> PI;
typedef pair<P_TYPE, P> IP;
typedef pair<P, P> PP;
typedef priority_queue<P, vector<P>, greater<P> > pvqueue;

#define N 100007
#define MOD 1000000007

int n;
vector<int> g[N];

ll memo[N][2];
ll dfs(int v, int s, int p = -1) {
  if(memo[v][s] != -1) {
    return memo[v][s];
  }
  if((p != -1 && g[v].size() == 1) || (p == -1 && g[v].size() == 0)) {
    return s == 0 ? 2 : 1;
  }
  ll r0 = 1, r1 = 1;
  repe(w, g[v]) {
    if(w == p) continue;
    if(s == 0) r0 = (r0 * dfs(w, 1, v)) % MOD;
    r1 = (r1 * dfs(w, 0, v)) % MOD;
  }
  return memo[v][s] = (s == 0 ? r0 + r1 : r1) % MOD;
}

int main() {
  cin >> n;
  rep(i, n-1) {
    int x, y; cin >> x >> y; --x; --y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  rep(i, n) rep(j, 2) memo[i][j] = -1;
  cout << dfs(0, 0) << endl;
  return 0;
}

Measured memory_bytes: 15616
n = int(input())
order = list(map(int,input().split()))
satisfaction = list(map(int,input().split()))
add_satisfaction = list(map(int,input().split()))

total_satisfaction = 0
pre_num = -10

for i in order:
    total_satisfaction += satisfaction[i-1]
    if pre_num + 1 == i:
        total_satisfaction += add_satisfaction[pre_num-1]
    pre_num = i

print(total_satisfaction)

Measured memory_bytes: 3064
#include<iostream>
#include<vector>
using namespace std;
int main() {
  int N;
  int A[3][3];
  int i,j;
  for(i=0;i<3;i++)for(j=0;j<3;j++)cin >> A[i][j];
  cin >> N;
  vector<bool> f(110,false);
  for(i=0;i<N;i++) {
    cin >> j;
    f[j] = true;
  }
  bool F = false,v,h;
  for(i=0;i<3;i++) {
    h = v = true;
    for(j=0;j<3;j++) {
      if(!f[A[i][j]])h = false;
      if(!f[A[j][i]])v = false;
    }
    if(h || v)F = true;
  }
  h = v = true;
  for(i=0;i<3;i++) {
    if(!f[A[i][i]])h = false;
    if(!f[A[i][2-i]])v = false;
  }
  if(h || v)F = true;
  if(F)cout << "Yes" << endl;
  else cout << "No" << endl;
}

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

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

    int mi = 1001;

    int cnt = 0;

    rep(i, N) {
        int m;
        cin >> m;
        X -= m;
        mi = min(mi, m);
        cnt++;
    }

    cout << cnt + X / mi << endl;


    return 0;
}

Measured memory_bytes: 3624
from itertools import accumulate
from math import gcd

N = int(input())
A = list(map(int, input().split()))

l = list(accumulate(A[:-1], gcd, initial=0))
r = list(accumulate(A[::-1], gcd, initial=0))
print(max(gcd(l[i], r[N-i-1]) for i in range(N)))

Measured memory_bytes: 21940
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
#include<time.h>
#include<cassert>

using namespace std;
#define ll long long
#define ld long double
#define int long long
#define all(a) (a).begin(),(a).end()
#define EPS (1e-13)
#define fs first
#define sc second
#define xx first
#define yy second.first
#define zz second.second
#define H pair<int, int>
#define P pair<int, pair<int, int>>
#define Q(i,j,k) mkp(i,mkp(j,k))
#define rep(i,n) for(int (i) = 0 ; (i) < (n) ; (i)++)
#define mkp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define crdcomp(b) sort(all((b)));(b).erase(unique(all((b))),(b).end())
#define ssp(i,n) (i==n-1?"\n":" ")
const int mod = 1e9 + 7;
const int Mod = 998244353;
const ll Inf = 3 * 1e18;
const int inf = 15 * 1e8;
ll read() {
	ll u, k = scanf("%lld", &u);
	return u;
}
ll gcd(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcd(j % i, i);
}
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}
ll bcount(ll x) {
	int sum = 0;
	for (int i = 0; i < 20; i++)
		if ((1ll << i) & x) sum++;
	return sum;
}
/*const int fn_ = 2000000;
ll fact_[fn_], comp_[fn_];
ll comb(ll x, ll y, ll Mod = mod) {
	if (!fact_[0]) {
		fact_[0] = 1; comp_[0] = 1;
		for (int i = 1; i < fn_; i++) {
			fact_[i] = fact_[i - 1] * i % Mod;
			comp_[i] = mod_pow(fact_[i], Mod - 2, Mod);
		}
	}
	if (x < y) return 0;
	return fact_[x] * comp_[x - y] % Mod * comp_[y] % Mod;
}*/
//---------------------------------------------------
int n, m;
int a[200000];
int dp[200000][3];
signed main() {
	cin >> m >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int ans = 0;
	if (m == 2) {
		dp[0][3 - a[0]] = 1;
		for (int i = 1; i < n; i++) {
			dp[i][a[i]] = dp[i - 1][3 - a[i]];
			dp[i][3 - a[i]] = dp[i - 1][a[i]] + 1;
		}
		cout << min(dp[n - 1][1], dp[n - 1][2]) << endl;
		return 0;
	}
	for (int i = 0; i < n;) {
		int j = i;
		while (j < n && a[i] == a[j]) {
			j++;
		}
		ans += (j - i) / 2;
		i = j;
	}
	cout << ans << endl;
}


Measured memory_bytes: 6232
N = int(input())
S = input()
H = list(S)
P = len(H)
oo = []
ll = []
if P%2 == 0:
  for a in range (0,int(N/2)):
    oo.append(H[int(a)])
    ll.append(H[int(a+N/2)])
  if oo == ll :
    print("Yes")
  else :
    print("No")
else :
  print("No")
    
 
    

  


Measured memory_bytes: 3060
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <set>
#include <list>
#include <map>
#include <queue>
#include <iterator>
#include <iomanip>
#include <stdio.h>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <utility>
#include <functional>
#include <stack>
#include <deque>
#include <sstream>
using namespace std;

#define ll long long
#define mod 1000000007
#define ld long double
#define infinity (ll)1e18+1
#define PI 3.14159265358979

#define pdd pair<double,double>
#define pll pair<ll, ll>
#define pii pair<int,int>

#define MP make_pair
#define SZ size()
#define PB push_back

#define vi vector<int>//ll
#define vll vector<ll>
#define vpll vector<pll>
#define vpii vector<pii>
#define vch vector<char>
#define vb vector<bool>
#define vld vector<ld>
#define vs vector<string>

#define FOR(i,a,b) for(ll i = (a); i < (b); ++i)
#define RFOR(i,b,a) for(ll i = (b) - 1; i >= (a); --i)
#define REPEAT(i) FOR(counter1234,0,i)
#define ALL(a) a.begin(), a.end()
#define X first
#define Y second
#define MAXN 10001
/*
ll power(ll n, ll to)
{
	if (to == 0) return 1;
	if (to == 1) return n;
	int exp = 1;
	ll ans = n;
	while (2 * exp <= to)
	{
		ans *= ans;
		ans %= mod;
		exp *= 2;
	}
	return ((ans*power(n, to - exp)) % mod);
}

ll gcd(ll a, ll b)
{
	if (a < b)
		swap(a, b);

	if (b == 0)
		return a;

	if (a < b)
		swap(a, b);

	return gcd(b, a%b);
}

pll add(int a, int b)
{
	if (a > b)
		swap(a, b);

	ll mult = 1;
	FOR(i, a, b + 1)
	{
		mult *= i;
		mult %= mod;
	}

	ll num = 0;
	FOR(i, a, b + 1)
	{
		num += (mult * power(i, mod - 2));
		num %= mod;
	}

	return MP(num, mult);
}

ll n;
vll a, b;

int main()
{
	srand(time(NULL));
	clock_t startTime = clock();
	ios_base::sync_with_stdio(false), cin.tie(0);
	//ifstream in("In.txt");

	cin >> n;
	a.assign(n, 0);
	b.assign(n - 1, 0);
	FOR(i, 0, n)
		cin >> a[i];

	FOR(i, 0, n - 1)
		cin >> b[i];

	sort(ALL(a));

	if (n == 2)
	{
		ll p, q;

		p = b[0];
		q = a[1] - a[0];

		auto sum = add(a[0] + 1, a[1]);
		
		p *= sum.first;
		q *= sum.second;
		p %= mod;
		q %= mod;

		ll res = p % mod;
		res *= power(q, mod - 2);
		cout << res%mod;
	}
	else
	{
		if (n == 3)
		{
			pll c1, c2, c3;
			c2.X = a[1] * b[1] - b[0];
			c2.Y = (a[2] - a[1])*(a[1] - a[0]);

			c1.X = a[0] * b[1] - b[0];
			c1.Y = (a[2] - a[0])*(a[0] - a[1]);

			c1.X %= mod;
			c1.Y %= mod;
			c2.Y %= mod;
			c2.X %= mod;

			c3.Y = c1.Y * c2.Y;
			c3.X = mod * mod - (c1.Y * c2.X + c1.X * c2.Y);

			c3.X %= mod;
			c3.Y %= mod;




		}
	}
	

	
	return 0;
}*/

int main()
{
	srand(time(NULL));
	clock_t startTime = clock();
	ios_base::sync_with_stdio(false), cin.tie(0);
	//ifstream in("In.txt");

	int n; cin >> n;
	vll a(n);
	FOR(i, 0, n)
		cin >> a[i];

	sort(ALL(a));
	cout << a[n - 1] - a[0];

	return 0;
}

Measured memory_bytes: 384
n, a, b = map(int,input().split())
X = list(map(int,input().split()))

dist = []
for i in range(n-1):
    dist.append(X[i+1]-X[i])
    
ans = 0
for d in dist:
    if d*a > b:
        ans += b
    else:
        ans += d*a

print(ans)

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

int main() {
    int a, b, ans=0, one, two, three, four, five;
    cin >> a >> b;
    for (int i = a; i <= b; i++) {
        one = i % 10;
        two = (i % 100 - one) / 10;
        three = (i % 1000 - two) / 100;
        four = (i % 10000 - three) / 1000; 
        five = (i % 100000 - four) / 10000; 
        if (one == five && two == four) ans += 1;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>

typedef long long int64;

int64 gcd(const int64 x, const int64 y) { return y ? gcd(y, x % y) : x; }

int main() {
	int T;
	int64 A, B, C, D, g;
	
	scanf("%d", &T);
	while(T) {
		T--;
		scanf("%lld %lld %lld %lld", &A, &B, &C, &D);
		if(B > A or B > D)
			printf("No\n");
		else if(C >= B)
			printf("Yes\n");
		else {
			g = gcd(B, D);
			if(B - g + A % B % g > C)
				printf("No\n");
			else
				printf("Yes\n");
		}
	}
	return 0;
}

Measured memory_bytes: 128