akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

# 1からnまでの等差数列の和
def get_sum(n): return (1+n)*n//2

N = INT()

print(get_sum(N-1))


Measured memory_bytes: 3064
#include<cstdio>
#include<cmath>
using namespace std;
int main()
{
	int n;
	scanf("%d", &n);
	int t, x, y;
	int flag = 1;
	int map[2] = {0, 0};
	int cur = 0;
	while(n--)
	{
		scanf("%d%d%d", &t, &x, &y);
		int distance = abs(x-map[0]) + abs(y-map[1]);
		int temp = (t-cur) - distance;
		if(temp < 0 || (temp >0 && temp%2))
		{
			flag = 0;
		}
		cur = t;
		map[0] = x;
		map[1] = y;
	}
	if(flag)
		printf("Yes\n");
	else
		printf("No\n");
	
	
	
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
struct union_find
{
    vector<long long> par;  //親の番号　
    vector<long long> rank; //木の深さ(根のランクは0)
    vector<long long> siz;  //要素xが根なら木の頂点数を格納する
    //初期化子リストを用いた初期化
    union_find(long long N) : par(N), rank(N), siz(N)
    {
        for (long long i = 0; i < N; i++)
        {
            par[i] = i;
            rank[i] = 0;
            siz[i] = 1;
        }
    }
    //要素xが所属する木の根を再帰的に発見する
    long long root(long long x)
    {
        if (par[x] == x)
            return x;
        return par[x] = root(par[x]); //経路圧縮
    }
    //要素xが属する木と要素yが属する木の併合
    void unite(long long x, long long y)
    {
        long long rx = root(x);
        long long ry = root(y);
        if (rx == ry)
            return; //同じ木に属してたらそのまま
        if (rank[rx] < rank[ry])
        {
            par[rx] = ry; //根がryの木に併合
            siz[ry] = siz[rx] + siz[ry];
        }
        else
        {
            par[ry] = rx; //根がrxの木に併合
            siz[rx] = siz[rx] + siz[ry];
            if (rank[rx] == rank[ry])
                rank[rx]++;
        }
    }
    //要素xが属する木と要素yが属する木が同じならtrueを返す
    bool same(long long x, long long y)
    {
        return root(x) == root(y);
    }
    //要素xが属する木の頂点数を返す
    long long size(long long x)
    {
        return siz[root(x)];
    }
};
struct kruskal_edge
{
    long long u;
    long long v;
    double cost;
};
//辺のコストの大小を比較
bool kruskal_comp(const kruskal_edge &e1, const kruskal_edge &e2)
{
    return e1.cost < e2.cost;
}
vector<kruskal_edge> kruskal_side;
double kruskal(long long V, long long E) //V:頂点数,E:辺数
{
    sort(kruskal_side.begin(), kruskal_side.end(), kruskal_comp); //辺のコストが小さい順にソート
    union_find kruskal_tree(V);
    double kruskal_res = 0;
    for (long long i = 0; i < E; i++)
    {
        kruskal_edge ks = kruskal_side[i];
        if (!kruskal_tree.same(ks.u, ks.v))
        {
            kruskal_tree.unite(ks.u, ks.v);
            kruskal_res += ks.cost;
        }
    }
    return kruskal_res;
}
int main()
{
    cout << fixed << setprecision(3);
    while (true)
    {
        long long n;
        cin >> n;
        kruskal_side.resize(n * (n - 1) / 2);
        if (n == 0)
            break;
        vector<double> x(n);
        vector<double> y(n);
        vector<double> z(n);
        vector<double> r(n);
        for (long long i = 0; i < n; i++)
            cin >> x[i] >> y[i] >> z[i] >> r[i];
        long long now = 0;
        for (long long i = 0; i < n; i++)
        {
            for (long long j = i + 1; j < n; j++)
            {
                kruskal_side[now].u = i;
                kruskal_side[now].v = j;
                double X = x[i] - x[j], Y = y[i] - y[j], Z = z[i] - z[j], R = r[i] + r[j];
                kruskal_side[now].cost = max(0.0, (sqrt(X * X + Y * Y + Z * Z) - R));
                now++;
            }
        }
        cout << kruskal(n, n * (n - 1) / 2) << endl;
    }
    return 0;
}


Measured memory_bytes: 3352
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
using namespace std;
ll n,m,p[200005],xx,yy,root,raod[200005],fix[200005];
vector<ll>v[200005];

void go(ll x,ll par){
	p[x] = par;
	fix[x] = 1;
	for(int i=0; i<v[x].size(); i++)
		raod[v[x][i]]--;
	
	for(int i=0; i<v[x].size(); i++){
		if(!raod[v[x][i]] && !fix[v[x][i]]){
			go(v[x][i],x);
		}
	}
}
int main(){
	cin >> n >> m;
	
	for(int i=1; i<=n+m-1; i++){
		cin >> xx >> yy;
		raod[yy]++;
		v[xx].pb(yy);
	}
	
	for(int i=1; i<=n; i++){
		if(!raod[i])root = i;
	}
	
	go(root,0);
	
	for(int i=1; i<=n; i++)cout << p[i] << endl;
	
	
	return 0;
}

Measured memory_bytes: 17280
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] node = new int[num];
        int[] dp = new int[num];
        for (int i = 0; i < num; i++){
            node[i] = sc.nextInt();
        }
        //すべて無限大で初期化
        for (int i = 0; i < num; i++){
            dp[i] = 2147483647;
        }
        dp[0] = 0;
        dp[1] = dp[0] + Math.abs(node[0] - node[1]);
        for (int i = 2; i < num; i++)
                dp[i] = chmin(dp[i - 2] + Math.abs(node[i] - node[i - 2]), dp[i - 1] + Math.abs(node[i] - node[i - 1]));
        System.out.println(dp[num - 1]);
    }
    public static int chmin(int a, int b){
        if(a > b){
            return b;
        }else{
            return a;
        }
    }
}


Measured memory_bytes: 50564
#include <algorithm>
#include <cstdio>
#include <vector>
#include <valarray>
#include <queue>
#include <iostream>
#include <numeric>
#include <stdint.h>
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define rFOR(i, a, b) for(int i = (a); i >= (b); --i)
#define rREP(i, n) rFOR(i, n-1, 0)
#define AND &&
#define OR ||
#define IN(x, min, max) (min <= x AND x < max)
#define VEC(type) vector<type>
#define DVEC(type) vector<vector<type>>
#define VAL(type) valarray<type>
#define ARRAY_SIZE(array) (sizeof(array)/sizeof(array[0]))
#define HOGE printf("%s\n", "hoge");
#define DUMP(p) cout << p << endl;
const int INF = 2323232323;
using namespace std;
typedef pair<int, int> P;


int main(){
    int N;
    scanf("%d", &N);
    VEC(int64_t) T(N);
    VEC(int64_t) A(N);
    REP(i, N){
        scanf(" %lld", &T[i]);
    }
    REP(i, N){
        scanf(" %lld", &A[i]);
    }

    VEC(int64_t) flag(N, -1);
    int64_t old = -1;
    REP(i, N){
        if (old < T[i]) {
            flag[i] = 1;
            old = T[i];
        } else if (old == T[i]) {
            flag[i] = T[i];
        } else {
            flag[i] = 0;
        }
    }
    old = -1;
    rREP(i, N){
        if (old < A[i]) {
            if (T[i] < A[i] AND flag[i] != 1) {
                flag[i] = 0;
            } else {
                flag[i] = 1;
                old = A[i];
            }
        } else if (old == A[i]) {
            if (flag[i] == 1 AND A[i] < T[i]) {
                flag[i] = 0;
            } else {
                if (A[i] < flag[i]) {
                    flag[i] = A[i];
                }
            }
        } else {
            flag[i] = 0;
        }
    }
    if (T[N-1] != A[0]) {
        flag[0] = 0;
    }
    uint64_t hoge = 1;
    REP(i, 9){
        hoge *= 10;
    }
    hoge += 7;
    uint64_t ans = 1;
    REP(i, N){
        ans %= hoge;
        ans *= flag[i];
    }
    ans %= hoge;
    printf("%llu\n", ans);
    return 0;
}


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

#define INF (INT64_MAX)
#define MOD (1000000000+7)
#define MAX 100

string S;

int main() {
	cin >> S;

	int sz = S.size();
	int ans = 0;
	char c = S[0];
	for( int i = 0; i < sz; i++ ) {
		if( S[i] != c ) {
			ans++;
			c = S[i];
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <tuple>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
using namespace std;
void init();
#define REP(var, num) for(sll var = 0; var < num; var++)
typedef signed long long sll;
typedef unsigned long long ull;
/*
numeric_limits<sll>::max()
*/

int main() {
    init();
    sll n;
    cin >> n;
    sll longest = 0;
    sll sum = 0;
    REP(i, n) {
        sll l;
        cin >> l;
        longest = max(l, longest);
        sum += l;
    }

    if (longest < sum - longest)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

void init() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}

Measured memory_bytes: 256
using System;

class Program {
    private static int Main() {
        var input = Console.ReadLine();
        var values = input.Split( ' ' );

        int a = int.Parse( values[ 0 ] );
        int b = int.Parse( values[ 1 ] );
        int c = int.Parse( values[ 2 ] );

        bool isYes = ( a < b ) && ( b < c );

        var output = isYes ? "Yes" : "No";
        Console.WriteLine( output );

        return 0;
    }
}

Measured memory_bytes: 5296
#include <iostream>

using namespace std;

int n;
int x,y;

int abs(int n)
{
    return n>0?n:-n;
}

int main()
{
    cin>>n;
    for(int i = 1;i<=n;i++)
    {
        int t,posX,posY;
        cin>>t>>posX>>posY;
        posX=abs(x-posX);
        posY=abs(y-posY);
        if((t-posX-posY)%2==0 && t>=posX+posY)
        {

        }
        else
        {
            cout<<"No";
            return 0;
        }
    }
    cout<<"Yes";
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

int main(int argc, char *argv[]) {
  int n;
  std::cin >> n;

  for (int i = 1; i <= n; ++i) {
    int fx = 0;
    for (int x = 1; x * x <= i; ++x) {
      int xx = x * x;
      for (int y = 1; xx + y * y <= i; ++y) {
        int yy = y * y;
        int xy = x * y;
        for (int z = 1; xx + yy + z * z <= i; ++z) {
          int zz = z * z;
          int zy = z * y, zx = z * x;
          if (xx + yy + zz + xy + zy + zx == i)
            ++fx;
        }
      }
    }
    std::cout << fx << std::endl;
  }
}


Measured memory_bytes: 3140
#include <algorithm>
#include <array>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define REP(X, Y, Z) for (ll(X) = (Y); (X) < (Z); (X)++)

using namespace std;
using ll = long long;
using dll = deque<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using usll = unordered_set<ll>;
using umll = unordered_map<ll, ll>;
using sll = stack<int>;
using vll = vector<ll>;
using vvll = vector<vll>;

constexpr ll kMod = 1e9 + 7;

ll gcd(ll a, ll b) {
  if (a < b) {
    return gcd(b, a);
  }
  ll c = a % b;
  while (c != 0) {
    a = b;
    b = c;
    c = a % b;
  }
  return b;
}

ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

void init() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}

int main() {
  init();

  ll N;
  cin >> N;
  vll A(N);
  vll dp(N);
  ll asum = 0;
  REP(i, 0, N) {
    ll a;
    cin >> a;
    A[i] = a;
    asum += a;
    if (i == 0) {
      dp[i] = a;
    } else {
      dp[i] = dp[i - 1] + a;
    }
  }

  if (N == 2) {
    min(abs(A[0]), A[1]);
    if (A[0] > A[1]) {
      cout << A[0] - A[1] << endl;
    } else {
      cout << A[1] - A[0] << endl;
    }
    return 0;
  }

  ll res = 0;
  if (A[0] > (asum - A[0])) {
    res = A[0] - (asum - A[0]);
  } else {
    res = (asum - A[0]) - A[0];
  }
  REP(i, 1, N) {
    res = min(res, abs(asum - 2 * dp[i-1]));
  }
  cout << res << endl;

  return 0;
}


Measured memory_bytes: 3456
#include <bits/stdc++.h>
using namespace std;
int main(){
  set<int> U;
  int n;
  cin >> n;
  for (int i = 0; i < n; i++){
    int a;
    cin >> a;
    U.insert(a);
  }
  int m;
  cin >> m;
  for (int i = 0; i < m; i++){
    int b;
    cin >> b;
    U.insert(b);
  }
  for (auto itr = U.begin(); itr != U.end(); itr++){
    cout << *itr << endl;
  }
}


Measured memory_bytes: 21840
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define df 0
int dc=100000;
#define MAX 100010
typedef long int li;
int ord(li k){
  int i=0;
  while(k){
    k/=10;
    i++;
  }
  return i;
}

int main(){
  if(df)printf("*** debug mode ***\n");
  li n,i;
  scanf("%ld",&n);
  for(i=sqrt(n)+0.5;i>0;i--){
    if(n%i==0)break;
  }

  printf("%d",ord(n/i));
  return 0;
}


/// confirm df==0 ///


Measured memory_bytes: 128
#include <bits/stdc++.h>
#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 chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int		main(void)
{
	const double pi = 3.14159265358979323846;
	int r;
	cin >> r;
	double area =  pi * r * r;
	double cmp_area =  pi * 1 * 1;
	cout << area / cmp_area;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <string>
#include <set>
using namespace std;
#define maxn 100000+5
typedef long long int ll;
const double INF = 1e20;
const double pi = acos (-1.0);
int vis[5];
int main () {
    ll k,a,b;
    scanf("%lld%lld%lld",&k,&a,&b);
    if(b-a<=1){
        printf("%lld",k+1);
    }else {
        ll ans=1;
        ans+=(a-1);
        k-=(a-1);
        //cout<<k<<endl;
        ans+=(k/2)*(b-a);
        k-=(k/2)*2;
        if(k==1)ans++;
        printf("%lld",ans);
    }
   //while(1)getchar();
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, m, n) for(int (i) = (m); (i) < (n); ++i)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
using namespace std;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;
typedef pair<ll, ll> P;
const int INF = 1e9+7;
const ll LINF = 1LL<<60;

#define MAXN 100005
int d[MAXN];

bool isPrime(int x) {
    if (x == 0 || x == 1) return false;
    if (x == 2) return true;

    for(int i = 2; i * i <= x; i += 1) {
        if (x % i == 0) return false;
    }
    return true;
}

int main()
{
    for (int i = 3; i < MAXN; i += 1) {
        d[i] += d[i-1];
        if (i % 2 != 0 && isPrime(i) && isPrime((i + 1) / 2)) {
            d[i]++;
        }
    }

    int q;
    cin >> q;

    rep(i, q) {
        int l, r;
        cin >> l >> r;
        cout << d[r] - d[l - 1] << endl;
    }


    return 0;
}

Measured memory_bytes: 1024
import java.io.*;
import java.util.*;
import java.util.function.*;

final class Solver {
	void solve(Supplier<String> sc) {
		int N = Integer.parseInt(sc.get());
		int K = Integer.parseInt(sc.get());
		int[] A = new int[N];
		Arrays.setAll(A, $ -> Integer.parseInt(sc.get()));
		Arrays.sort(A);

		long[] paired = new long[N];
		int[] minus = new int[N];
		int[] plus = new int[N];
		{
			int midx = 0, pidx = 0;
			for (int value : A) {
				if (value >= 0) {
					plus[pidx++] = -value;
				} else {
					minus[midx++] = value;
				}
			}
			minus = Arrays.copyOf(minus, midx);
			plus = Arrays.copyOf(plus, pidx);
			Arrays.sort(minus);
			Arrays.sort(plus);
		}

		if ((plus.length == 0 && K % 2 != 0) || (plus.length > 0 && N == K && minus.length % 2 != 0)) {
			Integer[] abs = new Integer[N];
			Arrays.setAll(abs, i -> A[i]);
			Arrays.sort(abs, Comparator.comparingInt(Math::abs));
			int result = 1;
			for (int i = 0; i < K; i++) {
				result = mul(result, mod(abs[i]));
			}
			System.out.println(result);
			return;
		}

		int ridx = 0;
		for (int i = 0; i + 1 < minus.length; i += 2) {
			paired[ridx++] = (long) minus[i] * minus[i + 1];
		}
		int i = 0;
		int k = 0;
		int result = 1;
		if (K % 2 != 0) {
			result = mul(result, mod(-plus[i++]));
			k += 1;
		}
		for (; i + 1 < plus.length; i += 2) {
			paired[ridx++] = (long) plus[i] * plus[i + 1];
		}
		Arrays.sort(paired);

		int idx = 0;
		for (; k < K; k += 2) {
			result = mul(result, mod(paired[paired.length - 1 - idx++]));
		}
		System.out.println(result);

	}

	static final int MOD = 1000000007;

	int mod(long val) {
		return Math.floorMod(val, MOD);
	}

	int add(long a, long b) {
		return mod(a + b);
	}

	int sub(long a, long b) {
		return add(a, -b);
	}

	int mul(long a, long b) {
		return mod(a * b);
	}

	int pow(long a, long n) {
		int res = 1;
		for (; n > 0; n /= 2) {
			if (n % 2 == 1) res = mul(res, a);
			a = mul(a, a);
		}
		return res;
	}
}

class Main {
	public static void main(String... args) {
		System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		var reader = new BufferedReader(new InputStreamReader(System.in));
		new Solver().solve(new Supplier<>() {
			StringTokenizer line;

			public String get() {
				while (line == null || !line.hasMoreTokens()) try {
					line = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
				return line.nextToken();
			}
		});
		System.out.flush();
	}
}

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

int x[52] = {0};
long long int dp[52][52][2502]={0};

int main(){
    int n, a;
    cin >> n >> a;
    for(int i=0;i<n;++i)cin >> x[i+1];
    for(int i=0;i<=n;++i)
        dp[i][0][0] = 1;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=i;++j){
            for(int k=0;k<=2500;++k){
                if(k >= x[i]){
                    dp[i][j][k] += dp[i-1][j-1][k-x[i]];
                }
                dp[i][j][k] += dp[i-1][j][k];
            }
        }
    }
    long long int ans = 0;
    for(int i=1;i<=n;++i){
        ans += dp[n][i][a*i];
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 50048
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int mod=1000000007;
const int INF=1001001001;


int main() {
  int64_t N;
  cin>>N;
  vector<int64_t>a(N);
  map<int64_t,int>k;
  for(int i=0;i<N;i++){
    cin>>a[i];
    k[a[i]]++;
  }
  if(k.size()>3){cout<<"No"<<endl;}
  else if(k.size()==1){
    if(k[0]==N){cout<<"Yes"<<endl;}
    else{cout<<"No"<<endl;}
  }
  else {
    for(auto c:k){
      if(c.second!=N/3&&c.second!=2*N/3){cout<<"No"<<endl;return 0;}
    }
    if(k.size()==2){
      int64_t two=0,one=0;
      for(auto c:k){
        if(c.second==N*2/3){two=c.first;}
        else {one=c.first;}
      }
      if(two^two^one==0){cout<<"Yes"<<endl;}
      else{cout<<"No"<<endl;}
    }
    else{
      int64_t fac=0;
      for(auto c:k){
        fac^=c.first;
      }
      if(fac==0){cout<<"Yes"<<endl;}
      else{cout<<"No"<<endl;}
    }
  }
  return 0;  
}

Measured memory_bytes: 8736
n = list(input())
if n[0] == n[1]:
  if n[0] == n[2]:
    print("Yes")
  else:
    print("No")
elif n[1] == n[2]:
  if n[1] == n[3]:
    print("Yes")
  else:
    print("No")
else:
  print("No")

Measured memory_bytes: 3060
import itertools
n = int(input())
r = [i+1 for i in range(n)]
p = list(map(int,input().split()))
q = list(map(int,input().split()))
f = list(itertools.permutations(r,n))
f = list(map(lambda x:list(x),f))
print(abs(f.index(p) - f.index(q)))

Measured memory_bytes: 15092
using System;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Collections.Generic;
using System.Text;
using System.Text.RegularExpressions;
using static System.Math;
using Debug = System.Diagnostics.Debug;


static class P
{
    static void Main()
    {
        var xab = Console.ReadLine().Split().Select(int.Parse).ToArray();
        Console.WriteLine(Abs(xab[0] - xab[1]) > Abs(xab[0] - xab[2]) ? "B" : "A");
    }
}


Measured memory_bytes: 13396
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<stack>
#include<set>
#include<string>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int main()
{
    int x;
    cin>>x;
    if(x>=30)
        printf("Yes\n");
    else
        printf("No\n");
    return 0;
}


Measured memory_bytes: 3600
#include <iostream>
#define N 1000005
using namespace std;
long long n, ans, M=1e9+7, s[N], fac[N]={1,1}, inv[N]={1,1}, fin[N]={1,1};
int main() {
	int i;
	cin>>n;
	for(i=2; i<=n; i++) {
		fac[i] = fac[i-1] * i % M;
		inv[i] = inv[M%i] * (M-M/i) % M;
		fin[i] = fin[i-1] * inv[i] % M;
	}
	for(i=(n+1)/2; i<n; i++) {
		s[i] = fac[i] * fac[i-1] % M * fin[2*i-n] % M;
		ans += (s[i] - s[i-1] + M) * i % M;
	}
	cout<<ans % M;
	return 0;
}

Measured memory_bytes: 28288
n=int(input())
height=list(map(int,input().split()))
fumidai=[0 for i in range(n)]

for i in range(1,n):
    if height[i]<height[i-1]:
        key=height[i-1]-height[i]
        fumidai[i]=key
        height[i]+=key

print(sum(fumidai))

Measured memory_bytes: 101788
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int a, b, k;
    cin >> a >> b >> k;
    for(int i=0; i<k; ++i){
        if(i%2==0){
            if(a%2==1) --a;
            int t=a/2;
            a-=t;
            b+=t;
        } else{
            if(b%2==1) --b;
            int t=b/2;
            b-=t;
            a+=t;
        }
    }
    cout << a << " " << b << endl;
    return 0;
}


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

using namespace std;

#define debug(x,y) cout<<(#x)<<" " <<(#y)<<" is " << (x) <<" "<< (y) << endl
#define watch(x) cout<<(#x)<<" is " << (x) << endl
#define fast ios_base::sync_with_stdio(false)
#define fie(i,a,b) for(i=a;i<b;i++)
#define MOD 1000000007
#define mod 998244353
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define ll long long
#define lld long long int
#define ALL(x) (x).begin(),(x).end()

typedef vector<lld> vi;
typedef vector<vector<lld>> vii;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<pair<lld, lld>> vpi;
typedef long long LL;


int main() {
    fast;
    cin.tie(0);
/*#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w" , stdout);
#endif*/
    lld i, n;
    cin >> n;
    lld a[n];
    map<lld, lld> f;
    for (i = 1; i < n; i++) {
        cin >> a[i];
        f[a[i]]++;
    }
    for (i = 1; i <= n; i++) {
        cout << f[i] << endl;
    }

}

Measured memory_bytes: 17724
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#define maxn 1005
#define _ 0
using namespace std;
struct nod
{
	int nex,id;
	nod(int a,int b)
	{
		nex=a;
		id=b;
	}
	nod(){}
};
int n,m,tim;
int vis[maxn];
int bel[maxn][maxn][2];
int u[maxn*maxn],v[maxn*maxn];
vector<nod> edge[maxn];
void dfs(int now,int fa,int b,int f)
{
//	cerr<<now<<" "<<fa<<" "<<b<<" "<<f<<endl;
	vis[now]=tim; bel[fa][now][f]=b;
	int len=edge[now].size();
	for(int i=0;i<len;i++)
		if(vis[edge[now][i].nex]!=tim)
			dfs(edge[now][i].nex,fa,b,f);
}
void solve(int now)
{
	tim++; vis[now]=tim;
	int len=edge[now].size();
	for(int i=0;i<len;i++)
		if(vis[edge[now][i].nex]!=tim)
			dfs(edge[now][i].nex,now,edge[now][i].id,0);
 
	reverse(edge[now].begin(),edge[now].end());
 
	tim++; vis[now]=tim;
	for(int i=0;i<len;i++)
		if(vis[edge[now][i].nex]!=tim)
			dfs(edge[now][i].nex,now,edge[now][i].id,1);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u[i],&v[i]);
		edge[u[i]].push_back(nod(v[i],i));
	}
	for(int i=1;i<=n;i++)
		solve(i);
	for(int i=1;i<=m;i++)
	{
		if( (bel[v[i]][u[i]][0]!=0) ^ _ ^ (bel[u[i]][v[i]][0]!=i || bel[u[i]][v[i]][1]!=i) )
			printf("diff\n");
		else
			printf("same\n");
	}
}

Measured memory_bytes: 16004
import java.util.*;

public class Main{
	
  public static void main(String[] args){
  	Scanner sc = new Scanner(System.in);
    int A = sc.nextInt();
    int B = sc.nextInt();
    int C = sc.nextInt();
    if((A==5&&B==7&&C==5)
      ||(A==5&&B==5&&C==7)
      ||(A==7&&B==5&&C==5)){
      System.out.println("YES");
    }else{
      System.out.println("NO");
    }
  }
}

Measured memory_bytes: 23252
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[10**10]*(n+1)
dp[0]=0
for i in range(1,n):
    for j in range(1,k+1):
        if i-j<0:
            break
        dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]))
print(dp[n-1])

Measured memory_bytes: 52448
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define mp make_pair
ll power(ll a,ll b)
{ll result=1;
while(b>0)
{if(b%2==1)
 result*=a;
 a*=a;
 b/=2;
}
return result;
}
int main()
{ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 string s;
 cin>>s;
 int n=3,count=0,count1=0;
 for(int i=0;i<n;i++)
 {if(s[i]=='A')
  count++;
  else
  count1++;
}
if(count==0||count1==0)
cout<<"No";
else
cout<<"Yes";
}


Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cassert>
#define InfL 2000000000
#define InfLL 4000000000000000000LL
#define mod 1000000007
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<db> vd;

int main() {
	int N;
	cin >> N;
	ll ans = 0;
	rep(i, N) {
		ll a;
		cin >> a;
		ans += (int)(a % 2 == 1 && i % 2 == 0);
	}

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

Measured memory_bytes: 3632
#include<stdio.h>
#include<stdlib.h>
int main(void){
    int a,b,c,d;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    if(abs(c-a)<=abs(d)){
        printf("Yes\n");
    }
    else if(abs(b-a)<=abs(d)&&abs(c-b)<=abs(d)){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
    return 0;
}

Measured memory_bytes: 128
import itertools
n = int(input())
F = [list(map(int, input().split())) for i in range(n)]
P = [list(map(int, input().split())) for i in range(n)]
combos = sorted(list(itertools.product([0, 1], repeat=10)))
ans = -float('inf')

for combo in combos[1:]:
  total = 0

  for i in range(len(F)):
    count = 0      
    for a, b in zip(combo, F[i]):
      if a == 1 and b == 1:
        count += 1
    total += P[i][count]
  
  ans = max(ans, total)

print(ans)

Measured memory_bytes: 3188
#include <stdio.h>
#include <string.h>

int main(void)
{
	char c;
	int c2 = 0;
	int sum  = 0;
	
	while (scanf("%c", &c) != EOF){
		if (c <= '9' && c >= '0'){
			c -= '0';
			c2 *= 10;
			c2 += c;
		}
		else {
			sum += c2;
			c2 = 0;
		}
	}
	
	printf("%d\n", sum);
	
	return (0);
}

Measured memory_bytes: 540
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX = 100000;
const int mod = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

void COMinit()
{
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = mod - inv[mod%i] * (mod / i) % mod;
		finv[i] = finv[i - 1] * inv[i] % mod;
	}
}

long long COM(int n, int k)
{
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}

int main()
{
	int n, k;
	cin >> n >> k;

	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		a[i] += mod;
	}
	if (k == 1) {
		cout << 0 << endl;

		return 0;
	}
	sort(a.begin(), a.end());
	COMinit();

	long long mins = 0, maxs = 0;
	
	for (int i = 0; i <= n - k; i++) {
		mins += a[i] * COM(n - i - 1, k - 1);
		mins %= mod;
		maxs += a[k - 1 + i] * COM(k - 1 + i, k - 1);
		maxs %= mod;
	}
	cout << ((maxs + mod - mins) % mod) << endl;

	return 0;
}

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

using namespace std;
typedef long long int ll;

int main()

{
    int d,n;
    cin>>d>>n;
    if(n==100) n=101;
    for(int i=0;i<d;i++)
    {
        n*=100;
    }
    cout<<n;

    return 0;
}


Measured memory_bytes: 256
(defun f(s)
  (if (oddp (length s))
    nil
    (string= (subseq s 0 (/ (length s) 2))
             (subseq s (/ (length s) 2) (length s)))))
(let ( (line0 (read-line nil nil))
      (line (read-line nil nil)))
  (format t "~A~%" (if (f line) "Yes" "No")))


Measured memory_bytes: 11872
N = int(input())
counter = 0
primes = [2, 3]
for n in range(5, 2000 + 1, 2):
    isprime = True
    for i in range(1, len(primes)):
        if primes[i] ** 2 > n:
            break
        if n % primes[i] == 0:
            isprime = False
            break
    if isprime:
        primes.append(n)
ans = [i for i in primes if i % 5 == 1]
print(" ".join(map(str, ans[:N])))

Measured memory_bytes: 3064
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    int N = scanner.nextInt();
    NumPos[] p = new NumPos[N];
    for (int i = 0; i < N; i++) p[i] = new NumPos(scanner.nextInt(), i);
    Arrays.sort(p, (t1, t2) -> t2.num - t1.num);

    List<Integer> pos = new ArrayList<>(Arrays.asList(-1, -1, N, N));
    long res = 0;
    for (int i = 0; i < N; i++) {
      int n = p[i].num;
      int m = p[i].pos;
      int x = -Collections.binarySearch(pos, m) - 1;
      int r1 = pos.get(x);
      int r2 = pos.get(x + 1);
      int l1 = pos.get(x - 1);
      int l2 = pos.get(x - 2);
      res += (long) (r2 - r1) * (m - l1) * n;
      res += (long) (l1 - l2) * (r1 - m) * n;
      pos.add(x, m);
    }
    System.out.println(res);
  }

  private static class NumPos {
    private final int num;
    private final int pos;

    private NumPos(int num, int pos) {
      this.num = num;
      this.pos = pos;
    }
  }
}


Measured memory_bytes: 62812
#include<iostream>
#include<iomanip>
#include<math.h>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<functional>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=2e18;
const ll MOD=1e9+7;

ll N,C;
ll x[100010],v[100010];
ll upSum[100010]={};
ll upBest[100010];
ll downSum[100010]={};
ll downBest[100010];
int main(){
    cin>>N>>C;
    for(ll i=0;i<N;i++){
        cin>>x[i]>>v[i];
    }
    upSum[0]=v[0]-x[0];
    upBest[0]=upSum[0];
    for(ll i=1;i<N;i++){
        upSum[i]=upSum[i-1]+v[i]-(x[i]-x[i-1]);
        upBest[i]=max(upBest[i-1],upSum[i]);
    }
    downSum[N-1]=v[N-1]-(C-x[N-1]);
    downBest[N-1]=downSum[N-1];
    for(ll i=N-2;i>=0;i--){
        downSum[i]=downSum[i+1]+v[i]-(x[i+1]-x[i]);
        downBest[i]=max(downBest[i+1],downSum[i]);
    }
    ll ans=max({0ll,upBest[N-1],downBest[0]});
    for(ll i=0;i<N-1;i++){
        ans=max(ans,upSum[i]+downBest[i+1]-x[i]);
    }
    for(ll i=N-1;i>=1;i--){
        ans=max(ans,downSum[i]+upBest[i-1]-(C-x[i]));
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int main() {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    int x3, y3, x4, y4;
    x3 = x2 - (y2-y1);
    y3 = y2 + (x2-x1);
    x4 = x1 - (y2-y1);
    y4 = y1 + (x2-x1);
    cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;

    return 0;
}


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

using namespace std;
using ll = long long;

int main() {
  ios_base::sync_with_stdio (0);
  cin.tie (0);

  ll n;
  cin >> n;
  vector<ll>a (n);
  for (ll i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort (begin (a), end (a) );
  ll ans = 0;
  for (ll i = n - 1; i >= 0; i--) {
    ll l = 0, r = i - 1;
    while (l < r) {
      if (a[l] + a[r] > a[i]) {
        ans += r - l;
        r--;
      } else {
        l++;
      }
    }
  }
  cout << ans << '\n';
  return 0;
}



Measured memory_bytes: 256
// بِسمِ اللہِ  الرَّحم?نِ  الرَّ حِیم
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define MOD 1000000007
#define ll long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define INF 1e18
#define N 100100
#define PI 3.141592653589793238
typedef pair<ll,ll> pll;
ll power(ll a,ll b)
{
    if(b==1)return a;
    if(b==0)return 1;
    ll temp=power(a,b/2);
    ll ans=temp*temp;
    if(b&1)
        ans*=a;
    return ans;
}
ll power(ll a,ll b,ll p)
{
    a=a%p;
    if(b==1)return a;
    if(b==0)return 1;

    ll temp=power(a,b/2,p);
    ll ans=(temp*temp)%p;
    if(b&1)
        ans=(a*ans)%p;
    return ans%p;
}
ll inv(ll a,ll m)
{
    return power(a,m-2,m);
}
//code begins
void solve(){
    ll a,b;cin>>a>>b;
    cout<<a*b<<endl;
}
signed main()
{
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(false);

//    cin.tie(NULL);cout.tie(NULL);

    solve();
    return 0;
}


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

int main() {
  char s[10];
  cin >> s;

  int ans=0;
  for (int i=0; i < 4; ++i) {
    if (s[i] == '+' ) ++ans;
    else --ans;
  }
  cout << ans << endl;
  return 0;

}
  

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define F first
#define S second
#define pb push_back
#define sd(x) scanf("%d",&x)
#define sd2(x,y) scanf("%d%d",&x,&y);
#define sdl(x) scanf("%lld",&x)
#define sd2l(x,y) scanf("%lld%lld",&x,&y);
#define sz(x) (int)(x.size())
#define nax 201010
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 1000000007
#define mp make_pair
#define pi pair<int ,int>
#define pii pair <int,pi>
using namespace std;
int arr[nax];
ll sum[nax];
int BIT[nax];
map<ll ,int> mapp;
vector< ll > sor;
void update(int idx,int val)
{
    while(idx < nax)
    {
        BIT[idx]+=val;
        idx+=idx & -idx;
    }
}
int query(int idx)
{
    int ret = 0;
    while(idx > 0)
    {
        ret+=BIT[idx];
        idx-=idx & -idx;
    }
    return ret;
}
int main(int argc, char const *argv[])
{
  //freopen("input.txt","r",stdin);
  //freopen("output.txt","w",stdout);
  int n,k;
  sd2(n,k);
  for (int i = 1; i <= n; ++i)
  {
      sd(arr[i]);
      arr[i]-=k;
      sum[i] = sum[i-1]+arr[i];
      sor.pb(sum[i]);
  }
  sor.pb(0);
  sort(sor.begin(), sor.end());
  int ctr = 1;
  for (int i = 0; i < sor.size(); ++i)
  {
    if(mapp[sor[i]] == 0)
    {
        mapp[sor[i]] =  ctr++;
    }
  }
  ll fans = 0;
  update(mapp[0],1);
  for(int i = 1;i<= n;i++)
  {
      ll cur = sum[i];
      int pos = mapp[cur];
      fans+=query(pos);
      update(pos,1);
  }
  printf("%lld\n",fans);
  return 0;
}

Measured memory_bytes: 17520
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define pb push_back
#define sz(x) (int)(x).size()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;


int main() {
  string s;
  cin >> s;
  int n=sz(s);
  int ans=0;
  
  rep(i,n){
    int count=0;
    srep(j,i,n){
      if(s[j]=='A' || s[j]=='C' || s[j]=='T' || s[j]=='G'){
        count ++;
      }
      else break;
    }
    ans = max(ans, count);
  }
  cout << ans << endl;
  return 0;
  
}


Measured memory_bytes: 256
//
//  main.cpp
//  ABC158E
//
#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // reverse
using namespace std;
int main(int argc, const char * argv[]) {
    int N,P;
    cin>>N>>P;
    string S;
    cin>>S;
    unsigned long length=S.length();
    vector<unsigned long>d(length);
    vector<unsigned long>c(length); // 累積値
    long long ans=0;
    long long sub=0;
    if (10%P==0) {
        for (unsigned long i=0; i<length; i++) {
            if((S.at(i)-'0')%P==0){
                ans+=i+1;
            }
        }
        cout<<ans<<endl;
        return 0;
    }
    // Pが2,5以外の時
    reverse(S.begin(), S.end());
    int ten=1;
    for (unsigned long i=0; i<length; i++) {
       d.at(i)=((S.at(i)-'0')*(ten%P))%P;
        if (i==0) {
            c.at(i)=d.at(i); // 0桁目
        } else{
            c.at(i)=(c.at(i-1)+d.at(i))%P; // 累積値を計算して記録する
        }
        ten=ten*10;
        ten=ten%P;
    }
    for (int i=0; i<P; i++) {
        sub=count(c.begin(),c.end(),i);
        if (i==0) sub++; // -1桁目は0と定義する
        if(sub>1) ans+=sub*(sub-1)/2;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3716
import sys
import math
import numpy

n , x , y = map(int,input().split())

k = [0] * (n-1)

for i in range(n):
    for j in range(i+1,n):
        cost = min( j-i , abs( (x-1) - i ) + 1 + abs( j-(y-1) )  )
        k[cost - 1 ] += 1

[print(p) for p in k]


Measured memory_bytes: 14432
N, M = map(int, input().split())
a = set([int(input()) for i in range(M)])
MOD = 10 ** 9 + 7
dp = [1]
if 1 in a:
    dp.append(0)
else:
    dp.append(1)
for ith_stair in range(2, N + 1):
    if ith_stair in a:
        dp.append(0)
    else:
        dp.append((dp[ith_stair - 1] + dp[ith_stair - 2]) % MOD)
print(dp[N] % MOD)


Measured memory_bytes: 59604
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define ALL(x) x.rbegin(), x.rend()

const int MAX = 1e5+10;
int N, K;
vl d[MAX];

int main() {
    cin >> N >> K;
    REP (i, N) {
        int t, dd;
        cin >> t >> dd;
        t--;
        d[t].push_back(dd);
    }

    vl F, S;
    REP (i, N) {
        sort(ALL(d[i]));
        REP (j, d[i].size()) {
            if (j == 0) F.push_back(d[i][0]);
            else S.push_back(d[i][j]);
        }
    }

    sort(ALL(F)); F.insert(F.begin(), 0);
    sort(ALL(S)); S.insert(S.begin(), 0);

    ll ans = 0;
    REP (i, F.size()-1) F[i+1] += F[i];
    REP (i, S.size()-1) S[i+1] += S[i];
    REP (k, K+1) {
        if (k >= F.size() || K-k >= S.size()) continue;
        ans = max(ans, F[k] + S[K-k] + k*k);
    }

    cout << ans << endl;
}

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

int main(){
    int N;
    cin >> N;
    pair<int, int> A[N];
    for(int i=0; i<N; i++){
        int a;
        cin >> a;
        A[i].first = a;
        A[i].second = i;
    }
    sort(A, A+N);
    for(int i =0; i <N; i++){
        cout << A[i].second+1 <<" ";
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 1536
#include<iostream>
#include<cstdio>
using namespace std;const int mod=1000000007;
int pre[605],f[605][605],g[605],a[605];
inline int calc(int l,int r) {return (r-l+1)-(pre[r]-pre[l-1]);}
int main() {int n,kkk,u,v,ans=0;
	scanf("%d%d",&n,&kkk),n<<=1;for (int i=1;i<=kkk;++i) {
		scanf("%d%d",&u,&v),pre[a[u]=v]=pre[a[v]=u]=1;
	}for (int i=1;i<=n;++i) pre[i]+=pre[i-1];
	*g=1;for (int i=2;i<=n;i+=2) g[i]=1LL*g[i-2]*(i-1)%mod;
	for (int i=1,j,mk;i<=n;++i) for (j=i;j<=n;++j) if (i+j&1) {mk=0;
		for (int k=i;k<=j;++k) if (a[k]&&(a[k]<i||a[k]>j)) mk=1;
		if (mk) continue;f[i][j]=g[calc(i,j)];
		for (int k=i+1;k<j;++k) f[i][j]=(f[i][j]-1LL*f[i][k]*g[calc(k+1,j)]%mod+mod)%mod;
	}kkk<<=1;for (int i=1;i<=n;++i) for (int j=i;j<=n;++j) if (f[i][j]) {
		ans=(ans+1LL*f[i][j]*g[n-(j-i+1)-(kkk-(pre[j]-pre[i-1]))])%mod;
	}printf("%d",ans);return 0;
}

Measured memory_bytes: 4648
//
//  main.cpp
//  CppTest
//
//  Created by M_Sugawara on 2019/12/22.
//  Copyright © 2019 Sugawar. All rights reserved.
//

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {

    // cinを高速にするためのおまじない
    cin.tie(0);
    ios::sync_with_stdio(false);

    int count;
    string strS;
    string strT;
    string result = "";

    cin >> count >> strS >> strT;

    for(int i=0;i<count;i++) {
        result += strS[i];
        result += strT[i];
    }

    cout << result;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define ALL(v) (v).begin(),(v).end()
#define Vi vector<int>
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define leng(n) (int)(log10(n)+1)
#define INF 9000000000000000000
#define MOD 1000000007
using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}  //  最大公約数gcd
int lcm(int a,int b){return a/gcd(a,b)*b;}  //  最小公倍数lcm

signed main() {
  int n,x;
  cin >> n >>x;
  Vi a(n);
  int qw;
  rep(i,0,n) {
    cin >> qw;
    a[i] = abs(qw-x);
  }
  int ans = a[0];
  if(n==1) {
    cout << ans << endl;
    return 0;
  }
  else {
    rep(i,0,n-1){
      ans = gcd(ans,a[i+1]);
    }
    cout << ans << endl;
    return 0;
  }
}


Measured memory_bytes: 1024
var
	n,k,a,b:int64;
begin
	read(n,k);
	a:=n div k;
	if k mod 2=0 then 
	begin 
		b:=n div (k div 2)-a;
		writeln(a*a*a+b*b*b);
	end
	else writeln(a*a*a);
end.

Measured memory_bytes: 128
use std::collections::VecDeque;
use std::io::BufRead;

#[derive(Debug, PartialEq, Eq, Clone, Copy)]
struct Pos { y: usize, x: usize }

fn main() {
    let stdin = std::io::stdin();

    let mut buf = String::new();
    stdin.read_line(&mut buf).ok();
    let (h, w) = to_pair(&buf);

    let map: Vec<Vec<char>> = stdin.lock().lines().map(|l| l.unwrap().chars().collect()).collect();
    let mut distmap: Vec<Vec<i16>> = vec![vec![-1; w]; h];
    let mut queue: VecDeque<Pos> = VecDeque::new();

    let start = Pos { y: 0, x: 0 };
    distmap[0][0] = 0;
    queue.push_back(start);

    let goal = Pos { y: h - 1, x: w - 1 };

    'outer: while let Some(pos) = queue.pop_front() {
        for &(dy, dx) in &[(1, 0), (-1, 0), (0, 1), (0, -1)] {
            let next_y = pos.y as i32 + dy;
            let next_x = pos.x as i32 + dx;
            if next_y < h as i32 && next_y >= 0 && next_x < w as i32 && next_x >= 0 {
                let next = Pos { y: next_y as usize, x: next_x as usize };
                if distmap[next.y][next.x] == -1 && map[next.y][next.x] == '.' {
                    distmap[next.y][next.x] = distmap[pos.y][pos.x] + 1;
                    if next == goal {
                        break 'outer;
                    }
                    queue.push_back(next);
                }
            }
        }
    }

    if distmap[h - 1][w - 1] == -1 {
        println!("{}", -1);
    } else {
        println!("{}", count_whites(&map) - distmap[h - 1][w -1] - 1);
    }
}

fn count_whites(map: &Vec<Vec<char>>) -> i16 {
    map.iter().map(|v| v.iter().filter(|&&c| c == '.').count() as i16).sum()
}

fn to_pair(s: &str) -> (usize, usize) {
    let v: Vec<usize> = s.split_whitespace().map(|w| w.parse().unwrap()).collect();
    let (l, r) = (v[0], v[1]);
    (l, r)
}


Measured memory_bytes: 4352
x,y,a,b,c = map(int,input().split())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))
p.sort()
p.reverse()
q.sort()
q.reverse()
r.sort()
ans = 0
ele = []
for i in range(x):
    ele.append(p[i])
for i in range(y):
    ele.append(q[i])
for i in range(c):
    ele.append(r[i])
ele.sort()
ele.reverse()
"""a1 = x-1
b1 = y-1
a2 = True
b2 = True
for i in range(c):
    if r[i] > p[a1] and p[a1] <= q[b1] and a2:
        ans += r[i] - p[a1]
        a1 -= 1
        if a1 < 0:
            a2 = False
    elif r[i] > q[b1] and q[b1] < p[a1] and b2:
        ans += r[i] - q[b1]
        b1 -= 1
        if b1 < 0:
            b2 = False"""
for i in range(x+y):
    ans += ele[i]
print(ans)

Measured memory_bytes: 23328
#include<cstdio>
#include<algorithm>
#include<functional>
#include<cstring>
int main(void)
{
	int n,i,d1,d2,cnt,flg;
	scanf("%d",&n);
	cnt=0;
	flg=0;
	for(i=0;i<n;i++)	{
		scanf("%d %d",&d1,&d2);
		if(d1==d2)	{
			cnt++;
			if(cnt>=3)	flg=1;
		}
		else cnt=0;
	}
	if(flg==1)	printf("Yes\n");
	else printf("No\n");
	return 0;
}

Measured memory_bytes: 1644
#include <iostream>
#include <algorithm>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)

int solve(const int n, const int k)
{
  int ret = 1;
  REP(i, n)
   ret =  min(ret * 2, ret + k);
  return ret;
}

int main()
{
  int n, k;
  cin >> n >> k;
  cout << solve(n, k) << endl;
}

Measured memory_bytes: 256
//JAI SRI KRISHNA.//
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
    ll n,m,k,a,b;
    cin>>n>>m>>k;
    if(n<0)
        n=-n;
    a=n/k;
    b=a+1;
    if(m<=a)
    {
        cout<<n-(m*k)<<endl;
    }
    else
    {
        if(a%2==0&&m%2==0||a%2!=0&&m%2!=0)
        {

           cout<<n-(a*k)<<endl;
        }
        else
        {
           cout<<(b*k)-n<<endl;
        }
    }

}


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


int main(void){
  int n,i;
  string s;
  
  cin >> s;
  n=s.size();
  
  for (i=0;i<n-1;i++){
    if (s[i]=='A' && s[i+1]=='C'){
      cout << "Yes" << endl;
      return 0;
    }
  }
  
  cout << "No" << endl;
  
  return 0;
}

Measured memory_bytes: 256
#[allow(dead_code)]
const MOD: usize = 1_000000000 + 7;

fn main() {
    let mut cin = Scanner::new();
    let n = cin.next_usize();
    let mut t = (0..n).map(|_| cin.next_f64()).collect::<Vec<_>>();
    let mut v = (0..n).map(|_| cin.next_f64()).collect::<Vec<_>>();
    t.push(1.0);
    v.push(0.0);

    let mut ans = 0_f64;
    let mut cur_v = 0_f64;
    for i in 0..n {
        let mut acc_t = v[i] - cur_v;
        let mut dec_t = t[i];
        let mut sum_t = t[i];
        for j in i+1..t.len() {
            if dec_t > sum_t - (v[i] - v[j]) {
                dec_t = sum_t - (v[i] - v[j]);
            }
            sum_t += t[j];
        }
        if acc_t > dec_t {
            acc_t = (acc_t + dec_t) / 2.0;
            dec_t = acc_t;
        }
        if acc_t > t[i] {
            acc_t = t[i];
            dec_t = acc_t;
        }
        ans += cur_v * acc_t + acc_t * acc_t / 2.0;
        // println!("{}", cur_v * acc_t + acc_t * acc_t);
        cur_v += acc_t;
        ans += cur_v * (dec_t - acc_t);
        // println!("{}", cur_v * (dec_t - acc_t));
        let dec_t = t[i] - dec_t;
        ans += cur_v * dec_t - dec_t * dec_t / 2.0;
        // println!("{}", cur_v * dec_t - dec_t * dec_t);
        cur_v -= dec_t;
        // println!("{} {} {} {}", i, cur_v, acc_t, dec_t);
    }

    println!("{:.9}", ans);
}


struct Scanner {
    reader: std::io::Stdin,
    tokens: std::collections::VecDeque<String>,
}

impl Scanner {
    fn new() -> Self {
        Scanner {
            reader: std::io::stdin(),
            tokens: std::collections::VecDeque::new(),
        }
    }

    fn next(&mut self) -> String {
        if self.tokens.is_empty() {
            let mut s = String::new();
            loop {
                self.reader.read_line(&mut s).ok();
                let s = s.trim();
                if s.len() != 0 {
                    for it in s.split_whitespace() {
                        self.tokens.push_back(it.into())
                    }
                    break;
                }
            }
        }
        self.tokens.pop_front().unwrap()
    }

    fn next_generics<T>(&mut self) -> T where
        T: std::str::FromStr + std::marker::Copy,
        <T as std::str::FromStr>::Err: std::fmt::Debug
    {
        self.next().parse().unwrap()
    }
    
    #[allow(dead_code)] fn next_i32(&mut self) -> i32 { self.next_generics::<i32>() }
    #[allow(dead_code)] fn next_i64(&mut self) -> i64 { self.next_generics::<i64>() }
    #[allow(dead_code)] fn next_u64(&mut self) -> u64 { self.next_generics::<u64>() }
    #[allow(dead_code)] fn next_f64(&mut self) -> f64 { self.next_generics::<f64>() }
    #[allow(dead_code)] fn next_usize(&mut self) -> usize { self.next_generics::<usize>() }
    #[allow(dead_code)] fn next_isize(&mut self) -> isize { self.next_generics::<isize>() }
}



Measured memory_bytes: 4352