akhauriyash/Code-Regression huggingface dataset:
def main():
    n = int(input().rstrip("\b"))
    numbers = [int(x) for x in input().rstrip("\b").split(" ")]
    start_number = numbers.pop(0)
    targets = {start_number:1}
    total = 0
    from collections import defaultdict
    for number in numbers:
        next_targets = defaultdict(int)
        for (target, count) in targets.items():
            total += count
            if (number | target) >= (target + number):
                next_targets[target + number] += count
        next_targets[number] += 1
        targets = next_targets
        #print(total)
    for (target, count) in targets.items():
        total += count

    print(total)

if __name__ == '__main__':
    main()

Measured memory_bytes: 24584
#include<stdio.h>

int main(void){

  int n=0;
  int d=0, x=0;
  int sum=0;
  int k=0;
  int i=0;
  int a[100]={0};

  scanf("%d", &n);
  scanf("%d %d", &d, &x);
  for(i=0; i<n; i++){
    scanf("%d", a+i);
  }

  for(i=0; i<n; i++){
    k=0;
    while(k*a[i]+1 <= d){
      sum=sum+1;
      k++;
    }
  }

  printf("%d\n", sum+x);

  return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
#include<string.h>
#include<math.h>
int main(void)
{
	int a,s,d[101],f,g[101],h,i,j,z[101],x[101],c,v,q;
	scanf("%d",&a);
	scanf("%d",&s);
	for(i=0;i<s;i++) scanf("%d",&d[i]);
	scanf("%d",&f);
	for(i=0;i<f;i++) scanf("%d",&g[i]);
	scanf("%d",&h);
	v=0;
	for(i=0;i<h;i++){
		x[i]=1;
		c=0;
		q=0;
		scanf("%d",&z[i]);
		for(j=0;j<s;j++){
			if(d[j]==z[i]){
				x[i]=0;
				q=1;
			}
		}
		for(j=0;j<f;j++){
			if(g[j]==z[i]){
				x[i]=1;
				break;
			}
		}
		if(q==0) x[i]=1;
	if(x[i]==1) v++;
	}
	printf("%d\n",v);
	return 0;
}

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

// traveling.cpp
// author: Seong Yong-ju ( @sei40kr )
// Copyright (c) 2018 Seong Yong-ju

#define DEBUG(x) cout << #x << ": " << x << endl

#define MIN(a, b) (a > b ? b : a)
#define MAX(a, b) (a > b ? a : b)

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); --i)

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n)-1; i >= 0; --i)

#define ALL(a) (a).begin(), (a).end()

using namespace std;

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

    int N;
    cin >> N;

    int t_last = 0, x_last = 0, y_last = 0;
    bool ans = true;

    REP(i, N) {
        int t, x, y;
        cin >> t >> x >> y;

        int cost_diff = (t - t_last) - abs(y - y_last) - abs(x - x_last);

        if (cost_diff < 0 || cost_diff % 2 == 1) {
            ans = false;
            break;
        }
    }

    cout << (ans ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
/*Code is modified from others*/
#include<cstdio>
#include<algorithm>
#include<vector>
#include <iostream>
#define FL(i,j,k) for(int i=j;i<k;++i)
const int MAXN = 2e6;
using namespace std;
typedef long long ll;
ll A[100000];
ll construct[100000]={0};
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    ll n,x;cin>>n>>x;
    FL(i, 0, n)cin>>A[i];
    construct[0]=min(A[0],x);
    FL(i, 1, n){
        if(construct[i]+construct[i-1]<x){
            construct[i]=min(A[i],x-construct[i]-construct[i-1]);
        }
    }
    ll sum=0;
    FL(i, 0, n)sum+=A[i]-construct[i];
    cout<<sum;
}

Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
#define M_PI 3.14159265359
using namespace std;
 
int main() {
    double r;
    cin >> r;

    double area = r * r * M_PI;
    double circum = 2 * r * M_PI;

    printf("%.6f %.6f\n", area, circum);
}

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

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

typedef pair<int,int> PII;
typedef long long ll;

int main(){
	int n,m,c,a[20][20],b[20];
	cin>>n>>m>>c;
	for (int i = 0; i < m; ++i){
			cin>>b[i];
		}	
	for (int i = 0; i < n; ++i){
		for (int j = 0; j < m; ++j){
			cin>>a[i][j];
		}
	}

	int ans=0;
	for (int i = 0; i < n; ++i){
		int total=0;
		for (int j = 0; j < m; ++j){
			total+=a[i][j]*b[j];
		}
		if(total+c>0)ans++;
	}

	cout<<ans<<endl;

}

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

int main(){
	int a[3],b[3],c[3],d[2];
	bool f=false;

	cin>>a[0]>>b[0]>>c[0];
	d[0]=b[0]-a[0]; //a2-a1;
	d[1]=c[0]-b[0];	//a3-a2;
	for(int i=1;i<3;i++){
		cin>>a[i]>>b[i]>>c[i];
		if(d[0]!=b[i]-a[i]||d[1]!=c[i]-b[i])
			f=true;
	}
	if(f)cout<<"No"<<endl;
	else cout<<"Yes"<<endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
ll mod=1000000007;
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	vector<int> a(3*n);
	rep(i,3*n) cin >> a.at(i);
	sort(a.begin(),a.end());
	ll ans=0,cnt=0;
	for(int i=3*n-2;i>=n;i-=2){
		ans+=a[i];
	}
	cout << ans << endl;
}

Measured memory_bytes: 1408
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	
	public static int[][] matrix_mul(final int n, final int mod, int[][] a, int[][] b){
		int[][] ret = new int[n][n];
		
		for(int i = 0; i < n; i++){
			for(int j = 0;j < n; j++){
				int sum = 0;
				
				for(int k = 0; k < n; k++){
					sum += (a[i][k]* b[k][j])  % mod;
					sum %= mod;
				}
				
				ret[i][j] = sum % mod;
			}
		}
		
		return ret;
	}
	
	public static int[][] matrix_pow(final int n, final int mod, final int t, int[][] ret){
		if(t == 1){
			return ret;
		}
		
		int[][] tmp = matrix_pow(n, mod, t / 2, ret);
		int[][] tmp_2 = matrix_mul(n, mod, tmp, tmp);
		
		if(t % 2 == 0){
			return tmp_2;
		}else{
			return matrix_mul(n, mod, tmp_2, ret);
		}
	}
	
	public static int[] vec_max_mul(final int n, final int mod, int[] array, int[][] matrix){
		int[] ret = new int[n];
		
		for(int i = 0; i < n; i++){
			int sum = 0;
			
			for(int j = 0;j < n; j++){
				sum += (array[j] * matrix[j][i]) % mod;
				sum %= mod;
			}
			
			ret[i] = sum;
		}
		
		return ret;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		while(true){
			final int n = sc.nextInt();
			final int m = sc.nextInt();
			final int a = sc.nextInt();
			final int b = sc.nextInt();
			final int c = sc.nextInt();
			final int t = sc.nextInt();
			
			if(n == 0 && m == 0 && a == 0 && b == 0 && c == 0 && t == 0){
				break;
			}
			
			int[] array = new int[n];
			for(int i = 0; i < n; i++){
				array[i] = sc.nextInt();
			}
			
			int[][] matrix = new int[n][n];
			for(int i = 0; i < n; i++){
				if(i != 0){
					matrix[i-1][i] = a;	
				}
				
				matrix[i][i] = b;
				
				if(i != n-1){
					matrix[i+1][i] = c;
				}
			}
			/*
			for(int[] tmp : matrix){
				System.out.println(Arrays.toString(tmp));
			}
			*/
			int[] ret = null;
			if(t == 0){
				ret = array;
			}else{
				ret = vec_max_mul(n, m, array, matrix_pow(n, m, t, matrix));
			}
			
			
			boolean first = true;
			for(int i = 0; i < n; i++){
				if(first){
					System.out.print(ret[i]);
					first = false;
				}else{
					System.out.print(" " + ret[i]);
				}
			}
			
			System.out.println();
		}
		
	}

}

Measured memory_bytes: 42700
//package lab9;

import java.util.Scanner;

public class Main {
	
	
	static /*
	 * 3 (= q sequences)
	 * abcbdab
	 * bdcaba
	 * abc
	 * 
	 * (q*2 subsequences)
	 * abc
	 * abc
	 * bc
	 */
	
	int subsequence(String one, String two) {
		int[][] LCS = new int[one.length()][two.length()];
		
		for(int j = 0; j < two.length()-1; j++) {
			LCS[0][j] = 0;
		}
		for(int i = 0; i < one.length()-1; i++) {
			LCS[i][0] = 0;
		}
		
		for(int i = 1; i <= one.length()-1; i++) {
			for(int j = 1; j <= two.length()-1; j++) {
				
				if(one.charAt(i-1) != two.charAt(j-1)) {
					LCS[i][j] = Math.max(LCS[i-1][j], LCS[i][j-1]);
				} else {
					LCS[i][j] = 1 + LCS[i-1][j-1];
				}
			}
		}
		
		return LCS[one.length()-1][two.length()-1];
	}
	
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		int q = in.nextInt();
		in.nextLine();
		for(int i = 0; i < q; i++) {
			String one = in.nextLine();
			one += " ";
			String two = in.nextLine();
			two += " ";
			//System.out.println(one);
			//System.out.println(two);
			System.out.println(subsequence(one, two));
		}
		
		
	}
}



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

int main()
{
    int a,b; cin >> a >> b;
    double ans = 0;
    for (int i = 1; i < a+1; i++) {
        double tmp = 1.0 / a;
        int x = i;
        while(x < b){
            x *= 2;
            tmp /= 2;
        }
        ans += tmp;
    }

    printf("%.12f\n",ans);

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  if(n<=111){
    cout<<111<<endl;
  }else if(n<=222){
    cout<<222<<endl;
  }else if(n<=333){
    cout<<333<<endl;
  }else if(n<=444){
    cout<<444<<endl;
  }else if(n<=555){
    cout<<555<<endl;
  }else if(n<=666){
    cout<<666<<endl;
  }else if(n<=777){
    cout<<777<<endl;
  }else if(n<=888){
    cout<<888<<endl;
  }else{
    cout<<999<<endl;
  }
  return 0;
}

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

int main(void)
{
	double h, x, area;
	
	while (1){
		scanf("%lf", &x);
		scanf("%lf", &h);
		if (x == 0 && h == 0){
			break;
		}
		
		area = x * x + 2 * x * sqrt(x * x / 4 + h * h);
		
		printf("%f\n", area);
	}
	return (0);
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << endl;
#define CFYN(n) cout << ( (n) ? "YES":"NO") << endl;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;

int main(void)
{
    IOS
    string s; cin >> s;
    set<char> st;
    bool ans = true;
    for(auto c:s) {
        auto ret = st.insert(c);
        if (!ret.second) {
            ans = false;
            break;
        }
    }
    if (ans) cout << "yes" << endl;
    else cout << "no" << endl;

    return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;
import static java.lang.System.out;

public class Main {
    static MyReader in = new MyReader();

    public static void main(String[] args) {
        int N = in.i();
        int C = in.i();
        int[] d = new int[200002];
        int[] dup = new int[d.length];
        for (int i = 0; i < N; i++) {
            int s = in.i();
            int t = in.i();
            int c = in.i() - 1;
            int j = 2 * s - 1;
            if (flag(dup[j], c)) {
                dup[j] = set(dup[j], c);
                d[j]++;
            }
            j++;
            while (j < 2 * t - 1) {
                d[j++]++;
            }
            if (flag(dup[j], c)) {
                dup[j] = set(dup[j], c);
                d[j]++;
            }
        }
        int ans = 0;
        for (int i = 0; i < d.length; i++) {
            ans = Math.max(ans, d[i]);
        }

        out.println(ans);
    }

    static boolean flag(int n, int i) {
        return ((n >> i) & 1) == 0;
    }

    static int set(int n, int i) {
        return n | (1 << i);
    }
}

class MyReader extends BufferedReader {
    char[] cbuf = new char[1024];
    int head = 0;
    int tail = 0;

    MyReader() {
        super(new InputStreamReader(System.in));
    }

    char next() {
        if (head == tail) {
            try {
                tail = super.read(cbuf, 0, cbuf.length);
            } catch (IOException e) {
                e.printStackTrace();
            }
            head = 0;
        }
        return cbuf[head++];
    }

    void back() {
        head--;
    }

    boolean minus() {
        boolean minus;
        while (true) {
            char c = next();
            if (!isDelimiter(c)) {
                if (!(minus = c == '-')) back();
                return minus;
            }
        }
    }

    void skip() {
        while (isDelimiter(next()));
        back();
    }

    char[] s(int N) {
        char[] cbuf = new char[N];
        read(cbuf, 0, N);
        return cbuf;
    }

    public int read(char[] cbuf, int off, int len) {
        skip();
        int i;
        for (i = 0; i < cbuf.length; i++) {
            char c = next();
            if (isDelimiter(c)) {
                break;
            }
            cbuf[i] = c;
        }
        return i;
    }

    boolean isDelimiter(char c) {
        return c == ' ' || c == '\n' || c == '\r';
    }

    int i() {
        boolean minus = minus();
        int n = 0;
        while (true) {
            int k = next() - '0';
            if (k < 0 || 9 < k) break;
            n = 10 * n + k;
        }
        return minus ? -n : n;
    }

    int[] ii(final int N) {
        int[] a = new int[N];
        for (int j = 0; j < a.length; j++) a[j] = i();
        return a;
    }

    long l() {
        boolean minus = minus();
        long n = 0;
        while (true) {
            int k = next() - '0';
            if (k < 0 || 9 < k) break;
            n = 10 * n + k;
        }
        return minus ? -n : n;
    }
}


Measured memory_bytes: 39464
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
#define rep(i,n)	for(int i=0;i<n;i++)
typedef long long ll;
ll mod=1e9+7;
ll dp[114514];//dp[i]:最後にYに入れたのがiの通り数

int main(){
	ll n,a,b;	cin>>n>>a>>b;
	if(a>b)	swap(a,b);
	vector<ll> s(n);
	rep(i,n)	cin>>s[i];
	n;
	s.insert(s.begin(),-1e18);
	for(int i=2;i<=n;i++){
		if(s[i]-s[i-2]<a){
			cout<<0<<endl;
			return 0;
		}
	}

	int t=0,zero=0;
	ll sum=0;
	dp[0]=dp[1]=1;
	for(int i=2;i<=n;i++){
		if(s[i]-s[i-1]>=a){
			while(s[i]-s[t]>=b)	sum=(sum+dp[t++])%mod;
			dp[i]=sum;
		}
		else{
			while(s[i]-s[t]>=b)	sum=(sum+dp[t++])%mod;
			dp[i]=sum;
			while(zero<i-1){
				if(zero<t)	sum=(sum+mod-dp[zero])%mod;
				dp[zero++]=0;
			}
		}
	}
	ll ret=0;
	rep(i,n+1)	ret=(ret+dp[i])%mod;
	cout<<ret<<endl;
	return 0;
}


Measured memory_bytes: 1920
//Program.cpp
//Author : Aaryan Srivastava 
#include <bits/stdc++.h>
#include <random>
#include <chrono>
#define pb push_back
#define popb pop_back
#define ull unsigned long long  
#define beg begin
#define mp make_pair
#define pii pair<int, int>
#define piii pair<pii,int>
#define rep(i,n) for(int (i) = 0 ; i < (n) ; i++)
#define repA(i,x,y) for(int i = (x) ; i <= (y) ; i++)
#define repD(i,x,y) for(int i = (x) ; i >= (y) ; i--)
#define all(c) (c).begin(),(c).end()
#define ff first
#define ss second 
#define fill(a,val) memset(a,val,sizeof(a))
#define Randomize mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
using ll = long long;
#define int ll
const int N = 2*1e5 +5 ;
const int mod = 1e9 + 7 ;
const int inf = 1e18 ;
const int SZ = 101 ;
const double eps = 1e-9 ;
using namespace std;

#ifdef AaryanS
#define mycout cout
#define mycerr cerr 
#endif

#ifndef AaryanS
#define mycout if(false) cout
#define mycerr if(false) cerr
#define AaryanS 0 
#endif

void solve()
{
    string s; 
    cin >> s ;
    int a = (s[0]-'0')*10 + (s[1]-'0');
    int b = (s[2]-'0')*10 + (s[3]-'0');
    if(min(a,b) > 12 || (min(a,b) == 0 && ( max(a,b) > 12|| a==b ) )) {
        cout << "NA\n" ;
    }
    else if(min(a,b) <= 12 && max(a,b) > 12 && min(a,b) >= 1){
        cout << (a > 12 ? "YYMM" : "MMYY" ) ;
    }
    else if(min(a,b) == 0 && max(a,b) >= 1)
        cout << (a == 0 ? "YYMM" : "MMYY" ) ;
    else{
        cout << "AMBIGUOUS\n" ;
    }

}   

     
int32_t main(int32_t argc, char *argv[])
{
    double t1 = clock() ;
    ios::sync_with_stdio(0);    
    cin.tie(0); cout.tie(0);
    int TC = 1, t = 0;
    //cin >> TC ;
    while(t++ < TC)
    {
        //cout << "Case #" << t << ": " ;
        solve();
        //cout << endl ;
    }
    mycerr << "Time : " << 1000 *(clock() - t1)/CLOCKS_PER_SEC << " ms\n" ;
    return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;
 
public class Main {
  private static boolean debug = false;
  private static boolean elapsed = false;
 
  private static PrintWriter _err = new PrintWriter(System.err);
 
  private static long MOD = 1_000_000_007;
 
  private int N;
  private int[] A;
 
  private void solve(Scanner sc, PrintWriter out) {
    N = sc.nextInt();
    A = new int[N];
    for (int i = 0; i < N; ++i) {
      A[i] = sc.nextInt();
    }
 
    boolean[] b = new boolean[N];
    long total = 1;
    for (int i = 0; i < N; ++i) {
      if (!b[(N - A[i]) / 2]) {
        b[(N - A[i]) / 2] = true;
      } else if (!b[N - ((N - A[i]) / 2) - 1]) {
        b[N - ((N - A[i]) / 2) - 1] = true;
        total <<= 1;
        total %= MOD;
      } else {
        out.println(0);
        return;
      }
    }
    out.println(total);
  }
  private long C(long n, long r) {
    long res = 1;
    for (long i = n; i > n - r; --i) {
      res *= i;
    }
    for (long i = r; i > 1; --i) {
      res /= i;
    }
    return res;
  }
  private long P(long n, long r) {
    long res = 1;
    for (long i = n; i > n - r; --i) {
      res *= i;
    }
    return res;
  }
  private long ceil2pow(long n) {
    if (n == 0) {
      return 1;
    }
    n--;
    n |= (n >>> 1);
    n |= (n >>> 2);
    n |= (n >>> 4);
    n |= (n >>> 8);
    n |= (n >>> 16);
    n++;
    return n;
  }
  /*
   * 10^10 > Integer.MAX_VALUE = 2147483647 > 10^9
   * 10^19 > Long.MAX_VALUE = 9223372036854775807L > 10^18
   */
  public static void main(String[] args) {
    long S = System.currentTimeMillis();
 
    Scanner sc = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);
    new Main().solve(sc, out);
    out.flush();
 
    long G = System.currentTimeMillis();
    if (elapsed) {
      _err.println((G - S) + "ms");
    }
    _err.flush();
  }
}

Measured memory_bytes: 50288
#include<bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define SZ(x) ((int)(x).size())
#define debug(x) cerr << #x << ": " << x << '\n'

bool is_palindrome(string s){
    string t(s.rbegin(),s.rend());
    return s==t;
}
int main(){
    string s;cin >> s;
    int n = s.size();
    if(is_palindrome(s)&&is_palindrome(s.substr(0,(n-1)/2))&&is_palindrome(s.substr((n+1)/2))){
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl;

}

Measured memory_bytes: 256
#include<iostream> 
#include<istream>
#include<string>
using namespace std; 
 
int main ()
{
  string a,b,c;
  cin>>a>>b>>c;
  a[0]=a[0]-32;
  b[0]=b[0]-32;
  c[0]=c[0]-32;
  cout<<a[0]<<b[0]<<c[0];
    return 0;
}

Measured memory_bytes: 256
import java.util.*

fun main(args:Array<String>):Unit {
    while(true){
        val n = readLine()!!.trim().toInt()
        if (n == 0) return
        val floor = Floor(Array(n){
            val a = readLine()!!.trim().split(' ').map(String::toInt).toIntArray()
            (0 until n).map{
                Point(a[it * 2], a[it * 2 + 1])
            }.toTypedArray()
        })
        var loopCount = 0
        val isLooped = Array(n){Array(n){false}}
        for (x in 0 until n) for (y in 0 until n){
            if (!isLooped[y][x]){
                var single = Point(x, y)
                var double = floor[Point(x, y)]
                while (single != double){
                    single = floor[single]
                    double = floor[floor[double]]
                }
                if (!isLooped[single.y][single.x]){
                    ++loopCount
                    do{
                        isLooped[single.y][single.x] = true
                        single = floor[single]
                    }while(single != double)
                }
            }
        }
        println(loopCount)
    }
}
data class Point(val x:Int, val y:Int)
class Floor(private val mFloorState:Array<Array<Point>>){
    operator fun get(point:Point):Point = mFloorState[point.y][point.x]
}



Measured memory_bytes: 48408
#include<bits/stdc++.h>
using namespace std;
/*long long fun(long long sum,int i,int n,long long int *arr)
{
    if(i==(n-1))
    return sum;
    long long int ans1,ans2;
    if((i+1)<=n-1)
    ans1=fun(sum+abs(arr[i+1]-arr[i]),i+1,n,arr);
    else
    ans1=-1;
    if((i+2)<=(n-1))
    ans2=fun(sum+abs(arr[i+2]-arr[i]),i+2,n,arr);
    else
    ans2=-1;
    if(ans1!=-1&&ans2!=-1)
    return min(ans1,ans2);
    else if(ans1==-1)
    return ans2;
    else if(ans2==-1)
    return ans1;
    return -1;
}*/
int main(void)
{
    long long int n;
    cin>>n;
    long long int *arr=new long long int[n];
    for(int i=0;i<n;i++)
    cin>>arr[i];
    //long long int ans=fun(0,0,n,arr);
    //cout<<ans<<endl;
    int a[n]={0};
    int b[n]={0};
    for(int i=1;i<n;i++)
    {
        a[i]=abs(arr[i]-arr[i-1])+min(a[i-1],b[i-1]);
        if(i==1)
        b[i]=a[i];
        else
        b[i]=abs(arr[i]-arr[i-2])+min(a[i-2],b[i-2]);
    }
    cout<<min(a[n-1],b[n-1])<<endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <math.h>
#include <ctype.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;

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

	int ans = 0;
	int X = 0;
	
	int sum = 0;
	vector<int>vec(N);
	vector<int>vec1(N);
	for (int i = L; i < N + L; i++) {
		sum = i + sum;
	}

	for (int i = 0; i < N; i++) {
		vec[i] = L + i;
	}

	for (int i = 0; i < N; i++) {
		vec1[i] = abs(vec[i]);
	}

	sort(vec1.begin(), vec1.end());
	X = vec1[0];
	if (sum > 0) {
		ans = sum - X;
	}
	else {
		ans = sum + X;
	}

	//test
	cout << ans << endl;
}

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

namespace AtCoderBS
{
    class Program
    {
        static void Main(string[] args)
        {
            int a = int.Parse(Console.ReadLine());
            int n = int.Parse(Console.ReadLine());

            if ((a % 500) <= n)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}

Measured memory_bytes: 11092
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
//constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;

template<class T> inline T sqr(T x) {return x*x;}

long long power(long long x, long long n, long long mod = 1000000007) {
    if (n == 0) return 1;
    if (n % 2 == 0) return power(x * x % mod, n/2, mod);
    else return x * power(x, n-1, mod) % mod;
}

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    VVI ru(4,VI(n));
    REP(i,0,n) ru[s[i] == '?' ? 3 : s[i] - 'A'][i]++;
    REP(j,0,4) REP(i,1,n) ru[j][i] += ru[j][i-1];
    LL ans = 0;
    REP(i,1,n-1) {
        if (s[i] == 'B' || s[i] == '?') {
            int ac = ru[0][i-1], cc = ru[2][n-1] - ru[2][i];
            int qb = ru[3][i-1], qa = ru[3][n-1] - ru[3][i];
            LL a = (ac * power(3,qb)) % 1000000007;
            if (qb > 0) a = (a + power(3,qb-1) * qb) % 1000000007;
            LL c = (cc * power(3,qa)) % 1000000007;
            if (qa > 0) c = (c + power(3,qa-1) * qa) % 1000000007;
            ans = (ans + a * c) % 1000000007;
        }
    }
    cout << ans << endl;
}

int main() {
    solve();
    
    return 0;
}

Measured memory_bytes: 2432
import collections

K = int(input())
A, B = map(int, input().split())

X = []

for i in range(B - A + 1):
    m = A + i
    n = m % K

    X.append(n)

dict = collections.Counter(X)
l = dict[0]

if l > 0:
    print('OK')
else:
    print('NG')


Measured memory_bytes: 9492
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int main(){
    ll N;
    cin >> N;
    vector<ll> A(N),B(N+1);
    for(int i=0;i<N;i++){
        cin >> A[i];
        B[A[i]]++;
    }
    vector<ll> cnt(N+1,0),D(N+1,0);
    for(int i=1;i<=N;i++) cnt[B[i]]++;
    vector<ll> sum(N+1,0),sum2(N+1,0);
    for(ll i=1;i<=N;i++){
        sum[i] = sum[i-1]+i*cnt[i];
        sum2[i] = sum2[i-1]+cnt[i];
    }
    vector<ll> f(N+1),ans(N+1,0);
    for(ll i=1;i<=N;i++){
        f[i] = (sum[i]+i*(sum2[N]-sum2[i]))/i;
    }
    int now = 1;
    for(int i=N;i>=1;i--){
        while(now<=N && now<=f[i]){
            ans[now] = i;
            now++;
        }
    }
    for(int i=1;i<=N;i++) cout << ans[i] << endl;
}

Measured memory_bytes: 19584
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();

int main() {
    int N, K;
    string S;
    cin >> N >> S >> K;
    char target = S[K-1];
    for(int i = 0; i < N; i++)
        if (S[i] != target)
            S[i] = '*';
    cout << S << endl;
    return 0;
}




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

int main()
{
    string S;
    string T;
    cin >> S;
    cin >> T;
    bool flag = false;
    for(int i = 0; i < S.size(); i++) {
        if(S[i] != T[i]) {
            flag = true;
        }
    }
    if(flag) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }
    return 0;
}

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

using namespace std;


int main() {
	long long int N, M;
	cin >> N >> M;
	vector<long long int> mod( M ), sub( M );
	vector<long long int>data( 100001 );
	for( size_t i = 0; i < N; i++ ) {
		long long int X;
		cin >> X;
		data[X]++;
		mod[X%M]++;
	}
	long long int ans = 0;
	ans += mod[0] / 2;
	if( M % 2 == 0 ) {
		ans += mod[M / 2] / 2;
	}
	//cout << ans << endl;
	for( size_t i = 1; i < (M + 1) / 2; i++ ) {
		//cout << min( mod[i], mod[M - i] ) << endl;
		ans += min( mod[i], mod[M - i] );
		sub[i] = min( mod[i], mod[M - i] );
		sub[M - i] = min( mod[i], mod[M - i] );
	}
	for( size_t i = 0; i < M; i++ ) {
		//cout << sub[i] << " ";
	}
	//	cout << endl;
	for( size_t i = 0; i < 100001; i++ ) {
		if( i%M != 0 && (i%M) * 2 != M ) {
			if( data[i] % 2 == 1 && sub[i%M] > 0 ) {
				sub[i % M]--;
				data[i]--;
			}
		}
	}
	for( size_t i = 0; i < 100001; i++ ) {
		if( i%M && (i%M) * 2 != M ) {
			long long int xx = min( data[i], sub[i%M] );
			data[i] -= xx;
			sub[i%M] -= xx;
			ans += data[i] / 2;
		}
	}
	cout << ans << endl;
}

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

int main(){
  int n;
  cin >> n;
  int p[n];
  rep(i,n) cin >> p[i];
  int num = 0;
  
  for(int i=1;i<n-1;i++){
    if( (p[i]>p[i-1] && p[i]<p[i+1]) || (p[i]<p[i-1] && p[i]>p[i+1]) ) num++;
  }
  
  cout << num << endl;

  return 0;
}

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;
const int inf = 1001001001;

int main(){
  int a,b;
  cin >> a >> b;
  
  if (a == b) cout << "Draw" << endl;
  else if (a == 1) cout << "Alice" << endl;
  else if (b == 1) cout << "Bob" << endl;
  else if (a > b) cout << "Alice" << endl;
  else if (a < b) cout << "Bob" << endl;
  
}

Measured memory_bytes: 256
#include <stdio.h>

int main()	{

	int m, nmin, nmax, curr, next, res, gap, gapmax;

	while (true)	{

		scanf("%d %d %d", &m, &nmin, &nmax);

		if (m == 0)	{ break; }

		gapmax = -1;
		gap = -1;

		// res番目の点数を入力したところで、
		// res-1番目が合格するかどうか明らかになる
		for (int i = 1; i <= m; i++)	{

			if (i == 1)	{
				scanf("%d", &next);
				///
				//printf("1banme\n");
				///
				continue;
			}

			curr = next;
			scanf("%d", &next);

			if (i <= nmin)	{
				///
				//printf("hidarisugi\n");
				///
				continue;
			} else if	(i > nmax + 1)	{
				///
				//printf("migisugi\n");
				///
				continue;
			}

			gap = curr - next;

			if (gap >= gapmax)	{
				///
				//printf("ギャップが大きい\n");
				///
				gapmax = gap;
				res = i - 1;
			}
		}

		printf("%d\n", res);
	}

	return 0;
}


Measured memory_bytes: 2664
#include<iostream>
#include<cmath>

using namespace std;

int main(){
	long long a,b,c,x,y,sum,ans,t,cnt;
	cin>>a>>b>>c>>x>>y;
	if(x<y){
	sum=(y-x)*b+c*x*2;
	ans=y*c*2;
	cnt=a*x+y*b;
}
else {
	cnt=a*x+y*b;
	sum=(x-y)*a+y*c*2;
	ans=x*c*2;
}
t=min(ans,sum);
t=min(t,cnt);
cout<<t<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <math.h>
#include <stdio.h>
int main() {
	int a, v, b, w, t;
	scanf("%d%d%d%d%d", &a, &v, &b, &w, &t);
	if (v <= w) {
		printf("NO\n");
		return 0;
	}
	if (abs(a - b) <= (long long)t * (v - w)) {
		printf("YES\n");
	} else {
		printf("NO\n");
	}
	return 0;
}

Measured memory_bytes: 1660
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		int nn = sc.nextInt();
		int xx = sc.nextInt();
		int[] ll = new int[nn];
		long res = 0;
		int i=0;
		
		for (i=0;i<nn;i++){
			ll[i] = sc.nextInt();
		}
		
		for (i=0;i<nn;i++){
			res += ll[i];
			if(res >xx){
				break;
			}
		}
		
		System.out.print(i+1);
	}
}

Measured memory_bytes: 23892
#include<stdio.h>

int main(void){
    int A,B,N;
    scanf("%d",&N);
    
    if(N == 1){
        printf("Hello World");
    }

    if(N == 2){
        scanf("%d",&A);
        scanf("%d",&B);
        printf("%d",A + B);
        
    }
    return 0;
}

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

int main() {
  int A,B,C,D;
  cin >> A >> B >> C >>D;
  if (A+B > C+D)
    cout << "Left" << endl;
  else if (A+B < C+D)
    cout << "Right" << endl;
  else
    cout << "Balanced" << endl;
  return 0;
}

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

typedef long long ll;

using namespace std;
int main()
{
  ll n, m, h[100010], a, b, mx[100010] = {}, ans = 0;

  cin >> n >> m;
  for (int i = 1; i <= n; i++)
  {
    cin >> h[i];
  }
  for (int i = 0; i < m; i++)
  {
    cin >> a >> b;
    mx[a] = (mx[a] < h[b] ? h[b] : mx[a]);
    mx[b] = (mx[b] < h[a] ? h[a] : mx[b]);
  }

  for (int i = 1; i <= n; i++)
  {
    ans += h[i] > mx[i];
  }

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


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

using namespace std;
typedef long long ll;
typedef long int lt;
typedef vector<ll> vi;
typedef vector<int> vin;
typedef pair<ll,ll> pll;
typedef pair<int,int> pin;
#define all(a) a.begin(),a.end()
#define rep(i,a,b) for(int i=a;i<b;++i)
#define f(i,b) for(int i=0;i<b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define test(t) int t; cin>>t; while(t--) solve()
#define endl "\n"
#define p1 cout<<"YES"<<endl
#define p0 cout<<"NO"<<endl
#define fst ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

int main()
{
    int n,m;
    cin>>n>>m;
    ll sum=0;
    f(i,m){
        ll x;
        cin>>x;
        sum+=x;
    } 

    if(n-sum>=0)
        cout<<n-sum<<endl;
    else
        cout<<-1<<endl;
}

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

#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define repp(i, n, m) for(int (i) = (n); (i) < (m); (i)++)
#define repn(i, n) for(int (i) = 1; (i) <= (n); (i)++)
#define repr(i, n) for(int (i) = (n-1); (i) >= 0; (i)--)
#define all(x) (x).begin(), (x).end()
#define lint long long
#define ulint unsigned long long
#define ldou long double
#define fi first
#define se second
#define setpre(x) std::cout << fixed << setprecision(x)
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define out(x) cout << (x) << endl
#define outs(x) cout << (x) << " "
#define yn(x) cout << ((x)?("Yes"):("No")) << endl
#define YN(x) cout << ((x)?("YES"):("NO")) << endl
#define bit_c(x) __builtin_popcountll(x)

inline void logger(){ std::cout << " [LOGGER] " << endl; }
template<typename A, typename... B>
void logger(const A& a, const B&... b){
    cout << a << " , "; logger(b...);
}

typedef pair<lint, lint> P;
const lint MOD = 1000000007;
const lint MOD9 = 998244353;
const lint INF = MOD * MOD;
const int MAX = 200005;

/* ...o(^-^)o... */

int main(){
    int n; cin>>n;
    int ans = 1;
    while(1){
        if(ans*2 <= n){
            ans *= 2;
        }
        else break;
    }
    out(ans);
}

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

int main() {
  int n;
  cin >> n;
  vi a(n);
  rep(i,n) cin >> a.at(i);
  vi b(n);
  rep(i,n) cin >> b.at(i);
  vi cnta(n);
  rep(i,n) {
    if(i==0) cnta[i] = a[i];
    else cnta[i] = cnta[i-1] + a[i];
  }
  vi cntb(n);
  per(i,n) {
    if(i==n-1) cntb[i] = b[i];
    else cntb[i] = cntb[i+1] + b[i];
  }
  int ans = 0;
  rep(i,n) ans = max(ans,cnta[i]+cntb[i]);
  cout << ans << endl;  
  return 0;
}

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

#define ll long long
#define INF 99999999
#define rep(i,n) for(int i=0,temp=(int)(n);i<temp;++i) //vec.size()がnの時等の高速化
#define loop(i,start,end) for(int i=start,temp=(int)(end);i<end;++i)
#define all(x) (x).begin(),(x).end()
#define SORT(v, n) sort(v, v+n)
#define vsort(v) sort(v.begin(), v.end())
#define vfsort(v,lambda) sort(v.begin(),v.end(),lambda)
#define vint vector<int>
#define vvint vector<vector<int>>
#define vin(v,n) rep(i,n) cin >> v[i]

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int ctoi(char c) {return c-'0';}
//(lambda (x y) (< x y)) => [](int x, int y) -> int { return x<y; }

ll ceil(ll x,ll y){
  if(x%y==0) return x/y;
  return x/y+1;
}

int main(){
  ll n,a,b,c,d,e;
  cin >> n >> a >> b >> c >> d >> e;
  ll m = min(a,min(b,min(c,min(d,e))));
  cout << ceil(n,m)+4 << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define double long double
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mod 1000000007
#define endl "\n"
 
int32_t main()
{
	fast;
	int n;
	cin>>n;
	vector<int> v(n);
	for(int i=0;i<n;i++)
		cin>>v[i];
	int mx=0;
	int x=1;
	for(int i=1;i<n;i++)
	{
		if(v[i]<=v[i-1])
		{
			x++;
		}
		else
		{
			mx=max(x, mx);
			x=1;
		}
	}
	mx=max(x, mx);
	cout<<mx-1<<endl;
	return 0;
}

Measured memory_bytes: 1024
x, y = map(int, input().split())
if y*x < 0:
    ans = abs(x + y) + 1
elif y*x == 0:
    if x < y:
        ans = y - x
    else:
        ans = x - y + 1
else:
    if x < y:
        ans = y - x
    else:
        ans = x - y + 2

print(ans)

Measured memory_bytes: 9100
using System;
using System.Collections.Generic;
using System.Linq;

namespace abc153_c
{
    class Program
    {
        static void Main(string[] args)
        {
            List<decimal> input1 = Console.ReadLine().Split(' ').Select(decimal.Parse).ToList();
            List<decimal> input2 = Console.ReadLine().Split(' ').Select(decimal.Parse).ToList();

            decimal output = 0;

            List<decimal> hList = input2.OrderByDescending(x => x).ToList();

            if (input1[0] > input1[1])
            {
                hList.RemoveRange(0, (int)input1[1]);

                if (hList.Count != 0)
                {
                    output = hList.Sum();
                }
            }


            Console.WriteLine(output);
        }
    }
}


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

int h[200000], a[200000];

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> h[i];
  for (int i = 0; i < n; i++) cin >> a[i];

  map<int,ll> dp;
  dp[0] = 0;
  for (int i = 0; i < n; i++) {
    auto it = dp.upper_bound(h[i]);
    ll v = a[i];
    if (it != dp.begin())
      v += prev(it)->second;
    dp[h[i]] = v;
    it = dp.find(h[i]);
    vector<int> to_remove;
    ++it;
    while (it != dp.end() && it->second <= v) {
      to_remove.push_back(it->first);
      ++it;
    }
    for (int i : to_remove)
      dp.erase(i);
  }
  cout << dp.rbegin()->second << endl;
}


Measured memory_bytes: 14336
#include <bits/stdc++.h> 
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define size_of_array(array) (sizeof(array)/sizeof(array[0]))
#define MAX 100005
#define DEBUG 0 
#define LIMIT (LONG_MAX / 10)
#define POSITIVE_LAST_D (LONG_MAX % 10)
using ll =long long;
using namespace std;
using Graph=vector<vector<int>>;


int main(){
    ll n;
    int k;
    cin>>n>>k;
    int i=0;
    while(1){
        if(n>=pow(k,i)){
            i++;
        }else{
            break;
        }
    }
    cout<<i<<endl;
    return 0;
}


Measured memory_bytes: 256
from collections import defaultdict
N = int(input())
dict1 = defaultdict(list)
for i in range(N):
    S,P = map(str,input().split())
    P = int(P)
    dict1[S].append([P,i+1])

dict2 = sorted(dict1.items())
for i,v in dict2:
    v.sort(reverse = True)
    for j in v:
        print(j[1])
    

Measured memory_bytes: 3444
#include "bits/stdc++.h"
#define int long long
#define endl '\n'
using namespace std;
 
typedef long long ll;
#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) {
	cout << *it << " = " << a << endl;
	err(++it, args...);
}
 
#define read(a) int a; cin >> a;
#define readb(a, b) int a, b; cin >> a >> b;
#define readc(a, b, c) int a, b, c; cin >> a >> b >> c;
#define readarr(a, n) int a[(n) + 1] = {}; FOR(i, 1, (n)) {cin >> a[i];}
#define readmat(a, n, m) int a[n + 1][m + 1] = {}; FOR(i, 1, n) {FOR(j, 1, m) cin >> a[i][j];}
 
#define print(a) cout << a << endl;
#define printarr(a, n) FOR (i, 1, n) cout << a[i] << " "; cout << endl;
#define printv(v) for (int i: v) cout << i << " "; cout << endl;
#define printmat(a, n, m) FOR (i, 1, n) {FOR (j, 1, m) cout << a[i][j] << " "; cout << endl;} cout << endl;
#define all(v) v.begin(), v.end()
#define sz(v) (int)(v.size())
#define pb push_back
#define fi first
#define se second
#define vi vector <int>
#define pi pair <int, int>
#define vpi vector <pi>
#define vvi vector <vi>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll N = 2e5 + 1;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int power (int a, int b = mod - 2)
{
    int res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}


int n;
vi adj[N];
int dp[N], fac[N], facin[N], siz[N], ans[N];

void input()
{
	cin >> n;	
	FOR (i, 1, n - 1)
	{
		int x, y;
		cin >> x >> y;
		adj[x].pb(y);
		adj[y].pb(x);
	}
}

void dfs (int cur = 1, int prev = 0)
{
    dp[cur] = 1;
    
	for (int i: adj[cur])
		if (i != prev)
		{
		    dfs(i, cur);
		    siz[cur] += siz[i];
		    dp[cur] = dp[cur] * dp[i] % mod;
		}
	
	dp[cur] = dp[cur] * fac[siz[cur]] % mod;
	for (int i: adj[cur])
		if (i != prev)
    		dp[cur] = dp[cur] * facin[siz[i]] % mod;
    
    siz[cur]++;
}

inline int ncr (int a, int b)
{
	return fac[a] * facin[b] % mod * facin[a - b] % mod;
}

void dfs2 (int cur = 1, int prev = 0)
{
    ans[cur] = dp[cur];
	for (int i: adj[cur])
		if (i != prev)
		{
		    int x = dp[cur] * power(dp[i] * ncr(n - 1, siz[i]) % mod) % mod;
		    x = x * ncr(n - 1, n - siz[i]) % mod;
		    
		    dp[i] = dp[i] * x % mod;
			dfs2(i, cur);
			dp[i] = dp[i] * power(x) % mod;
		}
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);	
	fac[0] = facin[0] = 1;
	FOR (i, 1, N - 1) 
	{
	    fac[i] = fac[i - 1] * i %mod;
	    facin[i] = power(fac[i]);
	}
	
	input();
	dfs();
	dfs2();
	printarr(ans, n);
}











Measured memory_bytes: 22512
#include <iostream>
#include <string>
using namespace std;
int main() {
	int n, p[20], ans = 0;
	cin >> n;
	for (int a = 0; a < n; a++) {
		cin >> p[a];
	}
	for (int i = 1; i < n - 1; i++) {
		if (p[i - 1] <= p[i] && p[i] <= p[i + 1])ans++;
		else if (p[i + 1] <= p[i] && p[i] <= p[i - 1])ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<stack>
#include<cmath>
#include<iomanip>
#include<cstdlib>
#include<sstream>
#include<climits>
#include<cassert>
#include<time.h>

using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define pb push_back
#define ss second
#define ff first
#define vi vector<int>
#define vl vector<ll>
#define s(n) scanf("%d",&n)
#define ll long long
#define mp make_pair
#define PII pair <int ,int >
#define PLL pair<ll,ll>
#define inf 1000*1000*1000+5
#define v(a,size,value) vi a(size,value)
#define sz(a) a.size()
#define all(a) a.begin(),a.end()
#define tri pair < int , PII >
#define TRI(a,b,c) mp(a,mp(b,c))
#define xx ff
#define yy ss.ff
#define zz ss.ss
#define in(n) n = inp()
#define vii vector < PII >
#define vll vector< PLL >
#define viii vector < tri >
#define vs vector<string>
#define DREP(a) sort(all(a)); a.erase(unique(all(a)),a.end());
#define INDEX(arr,ind) (lower_bound(all(arr),ind)-arr.begin())
#define ok if(debug)
#define trace1(x) ok cerr << #x << ": " << x << endl;
#define trace2(x, y) ok cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)    ok      cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)  ok cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " \
                                << #d << ": " << d << endl;
#define trace5(a, b, c, d, e) ok cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " \
                                     << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) ok cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " \
                                    << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

#define read(a) freopen(a,"r",stdin)
#define write(a) freopen(a,"w",stdout)
ll MOD = int(1e9) + 7;

int debug = 1;
const int N = int(1e6) + 5;
using namespace std;
int dp[N][3];
int main()
{
        int i,j,n,t,m;
        ios::sync_with_stdio(false);
        string s;
        cin>>s;
        n = sz(s);
        int ans = 0;
        if(n == 1)
        {
          cout<<1;
          return 0;
        }
        if(n == 2)
        {
          if(s[0] == s[1])cout<<2;
          else cout << 1;
          return 0;
        }
        rep(i,N)dp[i][1] = dp[i][2] = -1e9;
        dp[1][1] = 1;
        if(s[1] != s[0]) dp[2][1] = 2;
        dp[2][2] = 1;
        for(i = 3; i <= n; i++)
        {
          dp[i][1] = dp[i-1][2] + 1;
          dp[i][2] = dp[i-2][1] + 1;
          if(s[i-1] != s[i-2])dp[i][1] = max(dp[i][1],dp[i-1][1] + 1);
          if(i >=4 && (s[i-1] != s[i-3] || s[i-2] != s[i-4]))dp[i][2] = max(dp[i][2],dp[i-2][2] + 1);
        }
        ans = max(dp[n][1],dp[n][2]);
        cout<<ans;


}


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

int uni[100000];

int oya(int a){
if (uni[a]<0){
	return a;
}
else{
	uni[a]=oya(uni[a]);
	return oya(uni[a]);
}
}

bool ren(int a,int b){
	a=oya(a);
	b=oya(b);
	if(a==b){
	return	false;
	}
	else{
		
	return true;	
	}
}

int main() {

int n,m;
cin>>n>>m;
for(int y=0;y<n;y++){
	uni[y]=-1;
}

for(int r=0;r<m;r++){
int s,g;
cin>>s>>g;
if(ren(s,g)){
	s=oya(s);
	uni[s]=g;
	}
}
int q;
cin>>q;
for(int rr=0;rr<q;rr++){
	int s,g;
	cin>>s>>g;
	if(ren(s,g)==true){
		cout<<"no"<<endl;
	}
	else{
		cout<<"yes"<<endl;
	}
}
	return 0;
}

Measured memory_bytes: 2152
#include <iostream> // cout, endl, cin
#include <cmath>    //sin, cos, tan
#include <vector>   // vector
#include <iomanip>  //setprecsion
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
using namespace std;
const double PI = acos(-1.0);

void four(int W)
{
  for(int i = 0;i < W;i++)
  {
    cout << "#";
  }
  cout << endl;
}

int main(void)
{
  while(1)
  {
    int H, W;
    cin >> H >> W;
    if(H == 0&&W == 0)
    {
      return 0;
    }
    for(int i = 0;i < H;i++)
    {
      four(W);
    }
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 3076
#include<iostream>
#include<stdio.h>
#include<map>
#include<string>
using namespace std;

int main(){
	char s[2];
	map<string, int>m;
	while(scanf("%*d,%s", s) != EOF){
		m[s]++;
	}
	cout << m["A"] << "\n" << m["B"] << "\n" << m["AB"] << "\n" << m["O"] << endl;
}

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

int n;
vector<int> w[100010];
int dp[100010] = {0};

int DP(int x){
    if(w[x].empty()) return 1;
    if(dp[x]) return dp[x];
    multiset<int> st;
    for(int son : w[x]) st.insert(DP(son));
    int j = 1, l = st.size(), ret = 1;
 
    for(int son : st){
        ret = max(ret, son + l - j + 1);
        j++;
    }
    return dp[x] = ret;
}

int main(){
    cin >> n;
    for(int i=2,a; i<=n; i++){
        cin >> a;
        w[a].push_back(i);
    }
    cout << DP(1) - 1 << endl;
    return 0;
}


Measured memory_bytes: 17024
from math import tan,radians
a,b,w=map(int,input().split())
V=a**2*b
def taiseki(x,a,b):
    x=90-x
    if tan(radians(x))>a/b:
        x=90-x
        return V-(a**3*tan(radians(x)))/2
    else:
        return a*b**2*tan(radians(x))/2
if V==w:
    print(0)
    exit()
ok,ng=0,90
while ng-ok>0.00000001:
    mid=(ok+ng)/2
    if taiseki(mid,a,b)>=w:
        ok=mid
    else:
        ng=mid
print(ng)

Measured memory_bytes: 62608
#include <iostream>

using namespace std;

typedef long long ll;

int main() {
    double W, H, x, y;
    cin >> W >> H >> x >> y;
    double ans, ans1, ans2, ansn1=1e10, ansn2=1e10, tmp_ans, tmp_ans1, tmp_ans2, ans3;

//    if (W < H) {
//        swap(W, H);
//        swap(x, y);
//    }

//    if (x > W / 2 && y > H / 2) {
//        x = W - x;
//        y = H - y;
//    } else if (x > W / 2) {
//        x = W - x;
//    } else if (y > H / 2) {
//        y = H - y;
//    } else {
//        ;
//    }

    // 縦に分割した時
    ans1 = min(x*H, (W-x)*H);
    // 横に分割した時
    ans2 = min(W*y, W*(H-y));

    // 斜めに分割した時
//    double Y = (W / 2 * (H / 2 - y)) / (W / 2 - x);
//    double a = H / 2 - Y;
    ans = W * H / 2.0;
    int flag;
//    if (ans1 == ans && ans2 == ans) {
//        flag = 1;
//    }else if (ans1 == ans || ans2 == ans) {
//        flag = 0;
//    } else {
//        flag = 1;
//    }
//    if (x == 0 && y == 0 || x == W && y == 0 || x == 0 && y == H || x == W && y == H) {
//        flag = 0;
//    } else if (x == W / 2 && y == H / 2) {
//        flag = 1;
//    } else if ((x == W / 2 || y == H / 2)) {
//        flag = 0;
//    } else {
//        flag = 1;
//    }
    if (x == W / 2 && y == H / 2) {
        flag = 1;
    } else flag = 0;
//    cout << ans1 << endl;
//    cout << ans2 << endl;
    cout << ans << " " << flag << endl;
    return 0;
}

Measured memory_bytes: 256