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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int Q;
int N;
string S;
int R[1010];
int C[2][1010];
int mi[1010],ma[1010],v[1010];
int ptr,L;

void parse() {
	int x=ptr;
	if(S[ptr]=='0') {
		R[x]=x+1;
		v[x]=mi[x]=ma[x]=0;
		ptr++;
	}
	else if(S[ptr]>='1' && S[ptr]<='9') {
		v[x]=mi[x]=S[ptr]-'0';
		ma[x]=mi[x]*10+9;
		ptr++;
		if(S[ptr]>='0' && S[ptr]<='9') {
			v[x]=v[x]*10+S[ptr]-'0';
			ptr++;
		}
	}
	else if(S[x]=='^' || S[x]=='_') {
		ptr++;
		ptr++;
		C[0][x]=ptr;
		parse();
		ptr++;
		C[1][x]=ptr;
		parse();
		ptr++;
		if(S[x]=='^') v[x]=max(v[C[0][x]],v[C[1][x]]);
		else v[x]=min(v[C[0][x]],v[C[1][x]]);
	}
}

pair<int,int> hoge() {
	if(ptr>=L) return {0,99};
	int x=ptr;
	if(S[x]=='0') {
		ptr++;
		return {0,0};
	}
	else if(S[x]>='1' && S[x]<='9') {
		ptr++;
		if(x==L-1) {
			return {S[x]-'0',(S[x]-'0')*10+9};
		}
		
		if(S[ptr]>='0' && S[ptr]<='9') {
			ptr++;
			return {(S[x]-'0')*10+(S[x+1]-'0'),(S[x]-'0')*10+(S[x+1]-'0')};
		}
		else {
			return {S[x]-'0',S[x]-'0'};
		}
	}
	else if(S[x]=='^' || S[x]=='_') {
		ptr++;
		ptr++;
		if(ptr>=L) return {0,99};
		auto lh=hoge(),rh=lh;
		ptr++;
		if(ptr>=L) {
			rh={0,99};
		}
		else {
			rh=hoge();
		}
		
		
		ptr++;
		if(S[x]=='^') return {max(lh.first,rh.first),max(lh.second,rh.second)};
		else return {min(lh.first,rh.first),min(lh.second,rh.second)};
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>Q;
	while(Q--) {
		ZERO(R);
		cin>>S;
		N=S.size();
		ptr=0;
		parse();
		for(i=1;i<=N;i++) {
			ptr=0;
			L=i;
			auto ret=hoge();
			if(ret.first==ret.second) {
				cout<<ret.first<<" "<<i<<endl;
				break;
			}
		}
	}
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


Measured memory_bytes: 256
mod=10**9+7
n=int(input())
arr=list(map(int,input().split()))
blist=[0]*61
plist=[2**i for i in range(61)]
for i in range(n):
  tmp=arr[i]
  pos=0
  while tmp!=0:
    if tmp%2==1:
      blist[pos]+=1
      tmp-=1
    tmp=tmp//2
    pos+=1
ans=0
for i in range(61):
  ans+=(plist[i]*blist[i])*(n-blist[i])+(plist[i]*(n-blist[i]))*blist[i]
  ans%=mod
ans*=pow(2,mod-2,mod)
ans%=mod
print(ans)

Measured memory_bytes: 125624
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Linq.Enumerable;
using static System.Math;

class Program
{
    static void Main()
    {
        var N = int.Parse(ReadLine());
        var A = ReadLine().Split(' ').Select(int.Parse).ToArray();

        var P = new[] { 0 }.Concat(A).Concat(new[] { 0 }).ToArray();
        var sum = P.Zip(P.Skip(1), (a, b) => Abs(a - b)).Sum();

        for (int i = 1; i < N + 1; i++)
        {
            var ans = sum;

            ans -= Abs(P[i] - P[i - 1]) + Abs(P[i] - P[i + 1]);
            ans += Abs(P[i - 1] - P[i + 1]);

            WriteLine(ans);
        }
    }
}

static class ArrayDeconstructExtensions
{
    public static void Deconstruct<T>(this T[] a, out T i1, out T i2) => (i1, i2) = (a[0], a[1]);
    public static void Deconstruct<T>(this T[] a, out T i1, out T i2, out T i3) => (i1, i2, i3) = (a[0], a[1], a[2]);
    public static void Deconstruct<T>(this T[] a, out T i1, out T i2, out T i3, out T i4) => (i1, i2, i3, i4) = (a[0], a[1], a[2], a[3]);
    public static void Deconstruct<T>(this T[] a, out T i1, out T i2, out T i3, out T i4, out T i5) => (i1, i2, i3, i4, i5) = (a[0], a[1], a[2], a[3], a[4]);
}


Measured memory_bytes: 36344
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define all(x) x.begin(), x.end()

int main() {
  ll n, k, sum = 0;
  cin >> n >> k;
  vector<ll> h(n);
  for (ll i = 0; i < n; i++) {
    cin >> h.at(i);
  }
  sort(all(h), greater<ll>());
  for (ll i = k; i < n; i++) {
    sum += h.at(i);
  }
  cout << sum << endl;
}

Measured memory_bytes: 1792
import scala.io.Source.stdin

object Main extends App{
  stdin.getLines.foreach { s=>
    var d = s.toDouble
    println {
      d + (for(i<-2 to 10) yield {
        if(i%2==0) d=d*2
        else d=d/3
        d
      }).sum
    }
  }
}

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

int main() {
	string s;
	cin >> s;
	int a = 0,b=0;//a...同じか b...1なら奇数
	if (s[0] == s[s.size() - 1])a++;
	if (s.size() & 1)b++;
	if (a) {
		if (b)puts("Second");
		else puts("First");
	}
	else {
		if (b)puts("First");
		else puts("Second");
	}
}

Measured memory_bytes: 512
answermap=[0]*51
answermap[0] = 1
answermap[1] = 4
answermap[2] = 10
answermap[3] = 20
answermap[4] = 35
answermap[5] = 56
answermap[6] = 84
answermap[7] = 120
answermap[8] = 165
answermap[9] = 220
answermap[10] = 282
answermap[11] = 348
answermap[12] = 415
answermap[13] = 480
answermap[14] = 540
answermap[15] = 592
answermap[16] = 633
answermap[17] = 660
answermap[18] = 670
answermap[19] = 660
answermap[20] = 633
answermap[21] = 592
answermap[22] = 540
answermap[23] = 480
answermap[24] = 415
answermap[25] = 348
answermap[26] = 282
answermap[27] = 220
answermap[28] = 165
answermap[29] = 120
answermap[30] = 84
answermap[31] = 56
answermap[32] = 35
answermap[33] = 20
answermap[34] = 10
answermap[35] = 4
answermap[36] = 1
answermap[37] = 0
answermap[38] = 0
answermap[39] = 0
answermap[40] = 0
answermap[41] = 0
answermap[42] = 0
answermap[43] = 0
answermap[44] = 0
answermap[45] = 0
answermap[46] = 0
answermap[47] = 0
answermap[48] = 0
answermap[49] = 0
answermap[50] = 0

inputs = []

while True:
  try:
    inputs.append(int(input()))
  except EOFError:
    break

for i in inputs:
  print(answermap[i])

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

int main()
{
	string S;
	ll K;
	cin >> S >> K;
	int idx = 1000;
	rep(i,S.size())
	{
		if (S[i] != '1')
		{
			idx = i;
			break;
		}
	}

	//cout << "idx:" << idx << endl;

	if (K < idx+1)
	{
		cout << S[K-1] << endl;
	}
	else
	{
		cout << S[idx] << endl;
	}
	return 0;
}

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

int main (){
    int a,b,c;
    cin >> a >> b >> c;
    if ((a==5&&b==5&&c==7) ||(a==5&&b==7&&c==5) || (a==7&&b==5&&c==5)){
        cout <<"YES" <<endl;

    }else{
        cout << "NO" << endl;
    }

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
using ll=long long;
constexpr ll mod=1000000007;
constexpr int inf=1000000000;
constexpr ll linf=1000000000000000000;

int main(){
    int h,w,k;
    cin>>h>>w>>k;
    string c[h];
    rep(i,h)cin>>c[i];
    int ans=0;
    rep(i,1<<h){
        rep(j,1<<w){
            int cnt=0;
            rep(a,h){
                rep(b,w){
                    if(((i>>a)&1)&&((j>>b)&1)&&(c[a][b]=='#')){
                        ++cnt;
                    }
                }
            }
            if(cnt==k)++ans;
        }
    }
    cout<<ans<<endl;
}


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

int main(){
  long long a,b,c,k,am=1;
  cin>>a>>b>>c>>k;
  for(int j=1;j<=k;j++){
    am*=2;
  }
  if(max(max(a,b),c)==a){
    
    cout<<a*am+b+c<<endl;
  }
  else if(max(max(a,b),c)==b){
    cout<<b*am+a+c<<endl;
  }
  else if(max(max(a,b),c)==c){
    cout<<c*am+a+b<<endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  vector<int> h(n);
  for(int i = 0; i < n; i++){
    cin >> h[i];
  }
  vector<int> dp(n);
  dp[1] = abs(h[1]-h[0]);
  for(int i = 0; i < n-2; i++){
    dp[i+2] = min(dp[i]+abs(h[i+2]-h[i]), dp[i+1]+abs(h[i+2]-h[i+1]));
  }
  cout << dp[n-1] << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c;

  cin >> a >> b >> c;

  if(a != b && a != c && b != c){
    cout << "3";
  }else if(a == b && a != c){
    cout << "2";
  }else if(a == c && a != b){
    cout << "2";
  }else if(b == c && b != a){
    cout << "2";
  }else if(a == b && a == c && b == c){
    cout << "1";
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	vector<int> p(n), c(n);
	for (int i = 0; i < n; i++) {
		cin >> p[i];
		p[i]--;
	}
	for (int i = 0; i < n; i++) {
		cin >> c[i];
	}
	long long ans = LLONG_MIN;
	for (int i = 0; i < n; i++) {
		vector<int> cyc(n, -1);
		long long sum = 0;
		int cur = i;
		for (int i = 0; i < k; i++) {
			if (cyc[cur] >= 0 && 2 * n <= k) {
				long long prefix = 0, start = cur;
				do {
					prefix += c[cur];
					ans = max(sum + prefix, ans);
					cur = p[cur];
				} while (cur != start);
				int cycle_size = i - cyc[cur], moves_left = k - i;
				long long take = 1LL * (moves_left/cycle_size - 1) * prefix;
				prefix = 0;
				for (int i = 0; i < moves_left % cycle_size + cycle_size; i++) {
					prefix += c[cur];
					ans = max(sum + take + prefix, ans);
					cur = p[cur];
				}
				break;
			}
			sum += c[cur];
			ans = max(ans, sum);
			cyc[cur] = i;
			cur = p[cur];
		}
	}
	cout << ans << '\n';
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i,l,r) for(int (i)=(l);(i)<(r);(i)++)
#define ll long long
using namespace std;
int main(){
    int a;
    cin>>a;
    int han=a/100,sum=a%100;
    if(han*5<sum) cout<<"0"<<endl;
    else cout<<"1"<<endl;
}

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

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

int main() {
    string S;
    cin >> S; 
    for(int i = S.size() - 1; i > 0; --i) {
        if (i % 2 != 0) {
            // 奇数
            continue;
        } else {
            // 偶数
            string s_l, s_r;
            s_l = S.substr(0, i / 2);
            s_r = S.substr(i / 2, (i - i / 2));
            // cout << s_l << ":" << s_r << endl;
            if (s_l == s_r) {
                cout << i << endl;
                return 0;
            }
        }
    }
    cout << 0 << endl;


    return 0;
}


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

string fixedNum( string a )
{
    if( a.size() == 1 )
        return a;
    for( int i = 0; i < a.size(); i++ )
        if( '1'<= a[i] && a[i] <= '9' )
            return a.substr( i, a.size() );
    return "0";
}

string calcAddition( string a, string b )
{
    a = fixedNum(a); b = fixedNum(b);
    int as = a.size(), bs = b.size(), d = as > bs ? as - bs : bs - as;
    string s = "0", t = "0";
    for( int i = 0; i < d; i++ )
        as > bs ? t += "0" : s += "0";
    s += a; t += b;

    for( int i = s.size() - 1; i >= 1; i-- )
    {
        s[i] += t[i] - '0';
        if( s[i] > '9' )
        {
            s[i] -= 10;
            s[i-1]++;
        }
    }
    return s[0] == '0' ? s.substr( 1, s.size() ) : s;
}

string calcSubtraction( string a, string b )
{
    int as = a.size(), bs = b.size(), d = as - bs;
    string s = "", t = "";
    for( int i = 0; i < d; i++ )
        t += "0";

    s += a;
    t += b;

    for( int i = s.size() - 1; i >= 0; i-- )
    {
        if( s[i] < t[i] )
        {
            s[i] += 10;
            if( s[i-1] >= '1' )
                s[i-1]--;
            else
            {
                int j = i - 1;
                while( s[j] == '0' )
                    s[j--] += 9;
                s[j]--;
            }
        }
        s[i] -= ( t[i] - '0' );
    }

    if( s.size() == 1 )
        return s;

    for( int i = 0; i < s.size(); i++ )
    {
        if( '1' <= s[i] && s[i] <= '9' )
            return s.substr( i, s.size() );
    }
    return "0";
}

int main()
{
    string a, b, c, sum = "0", cnt = "1";
    bool j1 = false;
    cin >> a >> b;

    if( a == "0" )
    {
        cout << 0 << endl;
        return 0;
    }
    else if( a[0] == '-' && b[0] == '-' )
    {
        a = a.substr( 1, a.size() );
        b = b.substr( 1, b.size() );
    }
    else if( a[0] == '-' )
    {
        j1 = true;
        a = a.substr( 1, a.size() );
    }
    else if( b[0] == '-' )
    {
        j1 = true;
        b = b.substr( 1, b.size() );
    }
    else;

    c = b;
    int as = a.size(), bs = b.size(), cs, d = as - bs;
    for( int i = 0; i < d - 1; i++ )
    {
        c += "0";
        cnt += "0";
    }
    cs = c.size();

    bool j2 = false;
    while( c != b )
    {
        while( as > cs || as == cs && a >= c )
        {
            j2 = true;
            a = calcSubtraction( a, c );
            as = a.size();
            sum = calcAddition( sum, cnt );
        }
        c = c.substr( 0, c.size() - 1 );
        cnt = cnt.substr( 0, cnt.size() - 1 );
        cs = c.size();
    }

    while( as > bs || as == bs && a >= b )
    {
        j2 = true;
        a = calcSubtraction( a, b );
        sum = calcAddition( sum, cnt );
        as = a.size();
    }

    if( j1 && j2 )
        cout << '-';
    cout << sum << endl;

    return 0;
}




Measured memory_bytes: 3204
#include <iostream>
using namespace std;
int main(){
    while(1){
        int n,x;
        cin >> n >> x;
        if(n==0 and x==0) return 0;
        int c = 0;
        for(int i=1;i<x/3;i++){
            for(int j=i+1;j<x/2;j++){
                for(int k=j+1;k<=n;k++){
                    if(i+j+k==x){ c++; break; }
                }
            }
        }
        cout << c << endl;
    }
}

Measured memory_bytes: 1160
import sys
input = lambda : sys.stdin.readline().rstrip()

n = int(input())
a = list(map(int, input().split()))
a_ = []
for i in a:
    if not a_:
        a_.append(i)
    elif i != a_[-1]:
        a_.append(i)
cnt = 0
flag = 0
for i in range(len(a_) - 1):
    if flag == 0:
        if a_[i + 1] - a_[i] > 0:
            flag = 1
        else:
            flag = -1
        continue
    if flag == 1 and a_[i + 1] - a_[i] < 0:
        cnt += 1
        flag = 0
    elif flag == -1 and a_[i + 1] - a_[i] > 0:
        cnt += 1
        flag = 0
print(cnt + 1)


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

int main() {
  string a;
  cin >> a ;
  
  if(a[0]=='A') cout << "T" << endl;
  if(a[0]=='T') cout << "A" << endl;
  if(a[0]=='C') cout << "G" << endl;
  if(a[0]=='G') cout << "C" << endl;
  return 0;
}

Measured memory_bytes: 256
use proconio::{fastout, input};
// use proconio::marker::*;

#[fastout]
fn main() {
   input! {
      n: usize,
      m: usize
   }

   let mut ans = Vec::new();
   let mut l = 1;
   let mut r = n / 2;
   while l < r {
      ans.push((l, r));
      l += 1;
      r -= 1;
   }
   let mut l = if n % 2 == 0 { n / 2 + 2 } else { n / 2 + 1 };
   let mut r = n;
   while l < r {
      ans.push((l, r));
      l += 1;
      r -= 1;
   }
   for i in 0..m {
      println!("{} {}", ans[i].0, ans[i].1);
   }
}


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

int main(){
  int A, B, C, X;
  cin >> A >> B >> C >> X;
  int ans = 0;
  for(int i=0; i<=A; i++){
    for(int j=0; j<=B; j++){
      int res = X-500*i-100*j;
      if(0<=res && res<=50*C){
        ans++;
      }
    }
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define pb push_back
#define inf 1e9
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que; get min
const double eps = 1.0e-10;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
//const int maxn = 3e5 + 10;
const int  maxn = 100005;
const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
int zimu[30];
int sum = 0;
map<char, int> mp;
int main()
{
        string now;
        cin >> now;
        string ans = "";
        for (int i = 0; i < now.size(); i++)
        {
                zimu[now[i] - 'a']++;
        }
        if (now.size() < 26)
        {
                cout << now;
                for (int i = 0; i <= 25; i++)
                {
                        if (!zimu[i])
                        {
                                cout << (char)('a' + i);
                                return 0;
                        }
                }
        }
        for (int i = now.size() - 1; i >= 0; i--)
        {
                int cnt = now[i] - 'a';
                for (int j = cnt + 1; j <= 25; j++)
                {
                        if (!zimu[j])
                        {
                                for (int k = 0; k < i; k++)
                                {
                                        cout << now[k];
                                }
                                cout << (char)('a' + j);
                                return 0;
                        }
                }
                zimu[now[i] - 'a']--;
        }
        cout << -1 << endl;
}


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

int main() {
  int N,D;
  cin >> N >>D;
  if(!(N%(2*D+1)==0)){
    cout << (N-N%(2*D+1))/(2*D+1)+1 <<endl;
  }
  else{
    cout << (N-N%(2*D+1))/(2*D+1) <<endl;
  }
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#define SENTINEL 10000000000
void merge(int*, int, int, int);
void mergeSort(int*, int, int);

int count = 0;

int main() {
  int *A;
  int n,i,j;
  scanf("%d",&n);
  A = (int*)malloc(sizeof(int) * (n+1));

  for(i = 0; i < n; i++) {
    scanf("%d",&A[i]);
  }

  mergeSort(A,0,n);

  for(i = 0; i < n-1; i++) {
    printf("%d ",A[i]);
  }
  printf("%d\n",A[n-1]);
  printf("%d\n",count);
  free(A);
  return 0;
}

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

    count++;

    if(L[i] <= R[j]) {
      A[k] = L[i];
      i = i + 1;
    } else {
      A[k] = R[j];
      j = j + 1;
    }
  }
  free(R);
  free(L);
}

void mergeSort(int *A, int left, int right) {
  int mid;
  if(left+1 < right){
    mid = (left + right)/2;
    mergeSort(A, left, mid);
    mergeSort(A, mid, right);
    merge(A, left, mid, right);
  }
}

Measured memory_bytes: 4480
use std::io::*;

fn main() {
  let stdin = stdin();
  let line = stdin.lock().lines().next().unwrap().unwrap();
  let mut iter = line.split_whitespace().map(|s| s.parse::<u32>().unwrap());

  let (a, b, x) = (iter.next().unwrap(), iter.next().unwrap(), iter.next().unwrap() as f64);

  let amount = if a <= b {
    a * ((x / 1000.0).ceil() as u32)
  }
  else if a < b * 2 {
    let u = (x / 500.0).ceil() as u32;
    a * (u / 2) + b * (u % 2)
  }
  else {
    b * ((x / 500.0).ceil() as u32)
  };

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



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

int main() {
  int N, C, K; cin >> N >> C >> K;
  int T[N]; for (int i = 0; i < N; ++i) cin >> T[i];
  sort(T, T + N);
  int busFirst = T[0], peopleNum = 1, busNum = 1;
  for (int i = 1; i < N; ++i) {
    if (peopleNum >= C) {
      peopleNum = 0;
      ++busNum;
      busFirst = T[i];
    }
    if (T[i] - busFirst > K) {
      peopleNum = 0;
      ++busNum;
      busFirst = T[i];
    }
    ++peopleNum;
  }
  cout << busNum << endl;
}

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

using namespace std;

#define MOD 1000000007

long long powMOD(long long base, long long pow) {
  long long result = 1;
  
  while (pow > 0) {
    if (pow % 2 == 1) {
      result = (result * base) % MOD;
    }
    
    base = (base * base) % MOD;
    
    pow >>= 1;
  }
  
  return result;
}

long long combinationMOD(long long a, long long b){
  long long c = 1, d = 1;
  
  for (int i = 0; i < b; i++) {
    c *= a - i;
    c %= MOD;
    d *= powMOD(i + 1, MOD - 2);
    d %= MOD;
  }
  
  return (c * d) % MOD;
}

int main() {
  int S, seq = 1;
  long long ans = 0;
  
  cin >> S;
  
  if (S < 3) {
    cout << ans << endl;
    
    return 0;
  }
  
  ans++;
  S -= 6;
  
  while (S >= 0) {
    ans += combinationMOD(S + seq, seq);
    ans %= MOD;
    
    S -= 3;
    seq++;
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 3552
# ABC115C - Christmas Eve
n, k = list(map(int, input().rstrip().split()))
lst = sorted(list(map(int, [input().rstrip() for _ in range(n)])))
ans = lst[k - 1] - lst[0]
for i, j in zip(lst, lst[k - 1 :]):
    ans = min(ans, j - i)
print(ans)

Measured memory_bytes: 14236
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb emplace_back
#define mp make_pair
#define f(i,a,n) for(int i=a ; i<n ; i++)
#define F first
#define E endl
#define S second
#define fast ios:: sync_with_stdio(false),cin.tie(0);
        
int main()
{
	string a,b;
	cin>>a>>b;
	cout<<b<<a;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  int m, f, r;
  vector<string> s;
  while (1) {
    cin >> m >> f >> r;
    if (m == -1 && f == -1)
      break;
    if (m == -1 || f == -1)
      s.push_back("F");
    else if (m + f >= 80)
      s.push_back("A");
    else if (m + f >= 65)
      s.push_back("B");
    else if (m + f >= 50)
      s.push_back("C");
    else if (m + f >= 30) {
      if (r >= 50)
        s.push_back("C");
      else
        s.push_back("D");
    } else
      s.push_back("F");
  }

  rep(i, s.size()) cout << s[i] << endl;

  return 0;
}


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

using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;
    s.push_back('#');
    int ans = 0;
    for(int i = 0; i + 1 < s.size(); i++) {
        if(s[i] != s[i+1]) ans++;
    }
    cout << ans << endl;    
}

Measured memory_bytes: 3696
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define vi vector<int>
#define ff first
#define ss second
#define file_se_input  freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define pp long long int
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define pb push_back
#define mp make_pair
#define pi 3.141592653589793238
#define eb emplace_back
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define zip(i,a,b) for(int i=a;i<b;i++)
#define rzip(i,a,b) for(int i=a;i>=b;i--)
#define ll unsigned long long int
#define test int t;cin>>t; while(t--)
#define um unordered_map
#define en '\n'
#define us unordered_set
typedef pair<int, int>     pii;
typedef pair<char, int>    pci;
typedef pair<char, char>   pcc;
typedef vector<pii>       vii;
typedef long double ld;
#define all(v) v.begin(), v.end()
#define INF (1e18+5)
#define inf (1e9+5)
#define mod 1000000007


bool check_prime(long long n)
{
	int flag = 0;
	for (long long i = 2; i * i <= n; i++)
	{
		if (n % i == 0)
		{
			flag = 1;
			break;
		}
	}
	if (n == 1)
		return false;
	else if (flag == 0 || n == 2 || n == 3)
	{
		return true;
	}
	else
	{
		return false;
	}

}

int BE(int x, int n, int m) //function to calculate x raise to power n modulo m
{
	int result = 1;
	while (n > 0)
	{
		if (n % 2 == 1)
			result = result * x % m;
		x = x * x % m;
		n = n / 2;
	}
	return result;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(0);
#ifndef ONLINE_JUDGE
	if (fopen("input.txt", "r"))
	{
		freopen ("input.txt" , "r" , stdin);
		freopen ("output.txt" , "w" , stdout);
	}
#endif
	//_______________________________-code starts-_______________________________________________
	ll n;
	cin >> n;
	ll a[n];
	zip(i, 0, n)
	{
		cin >> a[i];
	}
	sort(a, a + n);
	if (a[0] == 0)
	{
		cout << 0 << en;
		return 0;
	}
	ll ans = 1;
	ll x = 1e18 ;
	ll flag = 0;
	ll ans1 = 1;
	ll y;
	zip(i, 0, n)
	{
		ans *= a[i];

		y = x / ans;
		//cout << ans << en << y << en;
		if (y < a[i + 1] && i < n - 1)
		{
			flag = 1;
			break;
		}
	}
	//cout << ans1 << " " << ans << en;
	if (flag == 1)
	{
		cout << -1 << en;
	}
	else
	{
		cout << ans << en;
	}





	return 0;
}



Measured memory_bytes: 4432
# 通ってるコードをコピペ、ほぼ同じはずなんだけどこれは通る？
x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])


Measured memory_bytes: 160516
#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define fr(i, n) for (int i = 0; i < n; i++)
#define frf(i, j, n) for (int i = j; i <= n; i++)
#define frd(i, n) for (int i = n; i >= 0; i--)
#define mp(i, j) make_pair(i, j)
#define pb(x) push_back(x)
using namespace std;
// typedef vector<vector<ll> > matrix;
// const ll S = 3e5 + 20;
// const ll N = 1e6 + 1;
// const ll PRIME = 1e9 + 7;
const ll MAX = 1e6;

void solve()
{
    int n;
    cin >> n;
    int a[n];
    int m = 0;

    fr(i, n)
    {
        cin >> a[i];
        if (a[i] > m)
            m = a[i];
    }
    vector<int> freq(m + 1, 0);
    fr(i, n)
    {
        freq[a[i]]++;
    }
    sort(a, a + n);
    vector<int> b(m + 1, 1);
    fr(i, n)
    {
        for (int j = a[i]; j <= m; j += a[i])
        {

            if (j % a[i] == 0)
            {
                if (freq[a[i]] > 1 || j != a[i])
                    b[j] = 0;
            }
        }
    }
    // cout << b[3];
    ll ans = 0;
    fr(i, n)
    {
        // cout<<b[a[i]]<<" ";
        if (b[a[i]] == 1)
            ans++;
    }
    cout << ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int t;
    // cin >> t;
    t = 1;
    while (t--)
    {
        solve();
    }
}


Measured memory_bytes: 11912
use proconio::input;
use proconio::marker::Chars;

fn main() {
    input! {
        n: usize,
        x_s: Chars,
    }

    let pop: i64 = pop_count(&x_s);
    let x0: i64 = rem(&x_s, pop + 1);
    // popが1だったら？
    if pop == 1 {
        for (i, c) in x_s.iter().copied().enumerate() {
            if c == '1' {
                println!("{}", 0);
            } else {
                let modulo = 2;
                let d = pow_mod(2, (n - i - 1) as i64, modulo);
                let x3 = (x0 + d) % modulo;
                println!("{}", f(x3) + 1);
            }
        }
        return
    }

    let x1: i64 = rem(&x_s, pop - 1);
    for i in 0..n {
        let modulo =  if x_s[i] == '0' { pop + 1 } else { pop - 1 };
        let x3 = if x_s[i] == '0' {
            let d = pow_mod(2, (n - i - 1) as i64, modulo);
            (x0 + d) % modulo
        } else {
            let d = pow_mod(2, (n - i - 1) as i64, modulo);
            ((x1 - d) % modulo + modulo) % modulo
        };
        // dbg!(x3);
        println!("{}", f(x3) + 1);
    }
}

fn f(n: i64) -> i64 {
    let mut n = n;
    let mut count = 0i64;
    while n > 0 {
        let pop = n.count_ones() as i64;
        n = n % pop;
        count += 1;
    }
    count
}

fn pow_mod(n: i64, p: i64, modulo: i64) -> i64 {
    if p == 0 {
        return 1;
    }

    if p % 2 == 0 {
        let x = pow_mod(n, p / 2, modulo);
        (x * x) % modulo
    } else {
        n * pow_mod(n, p - 1, modulo)
    }
}

fn pop_count(x_s: &Vec<char>) -> i64 {
    x_s.iter().filter(|c| **c == '1').count() as i64
}

fn rem(x_s: &Vec<char>, modulo: i64) -> i64 {
    let mut x_r = x_s.clone();
    x_r.reverse();
    let mut ret = 0i64;
    for (i, c) in x_r.iter().copied().enumerate() {
        if c == '1' {
            ret += pow_mod(2, i as i64, modulo);
            ret = ret % modulo;
        }
    }

    ret % modulo
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn pow_mod_test() {
        assert_eq!(pow_mod(2, 3, 3), 2);
        assert_eq!(pow_mod(2, 0, 3), 1);
        assert_eq!(pow_mod(3, 2, 5), 4);
    }

    #[test]
    fn pop_count_test() {
        assert_eq!(pop_count(&"111".chars().collect()), 3);
        assert_eq!(pop_count(&"101".chars().collect()), 2);
    }

    #[test]
    fn rem_test() {
        assert_eq!(rem(&"111".chars().collect(), 3), 1);
    }

    #[test]
    fn f_test() {
        assert_eq!(f(1), 1);
        assert_eq!(f(0), 0);
    }
}


Measured memory_bytes: 3836
count_p=0
count_w=0
count_g=0
count_y=0


N=input()
N=int(N)
S=input()

for i in range(N*2):
    #奇数の場合のみ抽出
    if i%2==0:
        #色分け
        if S[i]=='P' and count_p==0:
            count_p+=1
        if S[i]=='W' and count_w==0:
            count_w+=1
        if S[i]=='G' and count_g==0:
            count_g+=1
        if S[i]=='Y' and count_y==0:
            count_y+=1

if count_p+count_w+count_g+count_y==3:
    print('Three')
else:
    print('Four')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ff first               // For pairs
#define ss second              // For pairs
#define sz(a) int((a).size())  // Function to determine size of any container
#define pb push_back           // Pushback to vector
#define mp make_pair           // Makes pairs to be stored as pair
#define all(c) (c).begin(), (c).end()
#define tr(container, it) for (auto it = container.begin(); it != container.end(); it++)  //traversing macro
#define present(c, x) (c.find(x) != c.end())

using namespace std;
typedef vector<ll> vi;            // Vector of long long
typedef vector<vi> vvi;           // Vector of vi
typedef vector<pair<ll, ll>> ii;  // Vector of pairs
typedef vector<ii> vii;           // Vector of ii
int main() {
    // ll t;
    // cin >> t;
    // for (int T = 1; T <= t; T++) {
    // ll n, k;
    // cin >> n >> k;
    // vi a;
    // for (int i = 0; i < n; i++) {
    //     cin >> a[i];
    // }
    string s;
    cin >> s;
    if (s.length() < 6)
        cout << "No\n";
    else if (s[2] == s[3] && s[4] == s[5])
        cout << "Yes\n";
    else
        cout << "No\n";

    // printf("Case #%d: %lld\n", T, dp[n - 1][p]);
    // }
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <map>
#include <set>
static const int MAXN = 1e5 + 4;

int n;
int a[MAXN], b[MAXN];

namespace dsu {
    int p[MAXN];
    inline void init(int n) { for (int i = 0; i < n; ++i) p[i] = i; }
    inline int root(int u) { return (p[u] == u) ? u : (p[u] = root(p[u])); }
    inline void merge(int u, int v) { u = root(u), v = root(v); if (u != v) p[u] = v; }
}

inline int min_rots(int n, int *a, int *b)
{
    int id_tot = 0;
    std::map<int, int> id;
    dsu::init(n);
    for (int i = 0; i < n; ++i) if (b[i] != a[i]) {
        if (id.find(a[i]) == id.end()) id[a[i]] = id_tot++;
        if (id.find(b[i]) == id.end()) id[b[i]] = id_tot++;
        dsu::merge(id[a[i]], id[b[i]]);
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) if (b[i] != a[i]) ++ans;
    for (int i = 0; i < id_tot; ++i) if (dsu::root(i) == i) ++ans;
    return ans;
}

int main()
{
    scanf("%d", &n);
    int xor_sum = 0;
    for (int i = 0; i < n; ++i) { scanf("%d", &a[i]); xor_sum ^= a[i]; }
    for (int i = 0; i < n; ++i) scanf("%d", &b[i]);

    std::multiset<int> as;
    for (int i = 0; i < n; ++i) as.insert(a[i]);
    bool has_sum = false;
    for (int i = 0; i < n; ++i) {
        auto p = as.find(b[i]);
        if (p == as.end()) {
            if (b[i] == xor_sum && !has_sum) {
                has_sum = true;
            } else {
                puts("-1"); return 0;
            }
        } else {
            as.erase(p);
        }
    }

    if (has_sum) {
        int idx = -1;
        for (int i = 0; i < n; ++i)
            if (b[i] == xor_sum && a[i] != b[i]) { idx = i; break; }
        if (idx == -1)
            for (int i = 0; i < n; ++i) if (b[i] == xor_sum) { idx = i; break; }
        b[idx] = *as.begin();
        int ans = min_rots(n, a, b);
        printf("%d\n", ans == 0 ? 1 : ans - 1);
    } else {
        bool save = false;
        for (int i = 0; i < n; ++i)
            if (b[i] == xor_sum && b[i] != a[i]) save = true;
        printf("%d\n", min_rots(n, a, b) - save);
    }

    return 0;
}


Measured memory_bytes: 7040
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rep1(i,n) for(int i = 1; i < (n); i++)

double ky(int i, int j, vector<int> x, vector<int> y){
    double ans;
    ans = sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]));
    return ans;
}

int main(){
    int n;
    cin >> n;
    vector<int> x(n), y(n);
    rep(i,n){
        cin >> x[i] >> y[i];
    }
    double ans = 0;
    double c = 0;
    vector<int> p(n);
    rep(i,n)p[i] = i;
    do{
        rep(i,n-1){
            ans += ky(p[i], p[i+1], x, y);
        }
        c++;
    } while (next_permutation(p.begin(), p.end()));
    ans /= c;
    printf("%.10f\n", ans);
}

Measured memory_bytes: 256
import math
import fractions

def main(a,b,c,d):
    count = 0
    for i in range(a, b+1):
        if i%c != 0:
            if i%d != 0:
                count += 1

    return count

def main2(a,b,c,d):
    g = (c * d) // fractions.gcd(c,d)
    tempC = (b // c) - ((a-1) // c)
    tempD = (b // d) - ((a-1) // d)
    tempCD = (b // g) - ((a-1) // g)
    return (b - (a-1)) - (tempC + tempD - tempCD)

A,B,C,D = map(int, input().split())
print(main2(A,B,C,D))

Measured memory_bytes: 5076
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;

// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>

vector <ll> v;

ll fep(ll x, ll y, ll mod)
{ll res=1;while(y>0){if(y&1)res=(res*x)%mod;
    y=y>>1;x=(x*x)%mod;}return res%mod;}

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

	ll n,i,m,j,k,x,y,a,b,c,d,t,r;
	string s;
	
	cin >> r;
	cout << 2*3.1415*r;

	return 0;
}


Measured memory_bytes: 3752
import java.util.*;
 
public class Main{
	public static void main(String[] args){
	    Scanner sc = new Scanner(System.in);
    	int num = sc.nextInt();
        int number[] =new int[num];
		for(int i = 0; i < num; i++){
			number[i] = sc.nextInt();
        }
        int count = 0;
        for(int i = 0; i < num - 2; i++){
        	if(number[i + 1] < number[i] && number[i + 1] > number[i + 2]){
            	count++;
            }else if(number[i + 1] < number[i + 2] && number[i + 1] > number[i]){
            	count++;
            }
        }
        System.out.println(count);
	}
}

Measured memory_bytes: 35612
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
pair<int,int> a[300*300+5];
long long sum[300*300+5];
int n,m,d;
int cal(pair<int,int> a,pair<int,int> b)
{
    return abs(a.first-b.first)+abs(a.second-b.second);
}
int main()
{
    scanf("%d%d%d",&n,&m,&d);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            int x;
            scanf("%d",&x);
            a[x]=make_pair(i,j);
        }
    for(int i=1;i<=d;++i) sum[i]=0;
    for(int i=d+1;i<=n*m;++i) sum[i]=sum[i-d]+cal(a[i],a[i-d]);
    int q;
    scanf("%d",&q);
    while(q--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%lld\n",sum[r]-sum[l]);
    }
    return 0;
}


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

int main(){
    int n;
    cin>>n;
    vector<int> ans(101);
    for(int i=0;i<n;i++){
        ans[i]=0;
    }
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        int y;
        cin>>y;
        int z;
        for(int j=0;j<y;j++){
            cin>>z;
            ans[z-1]=1;
        }
        for(int k=0;k<n;k++){
            cout<<ans[k]<<flush;
            if(k<n-1){
            	cout<<' '<<flush;
            }
        }
        for(int j=0;j<n;j++){
        ans[j]=0;
    }
    if(i<n){
    cout<<endl;
    }
    }
    return 0;
}






Measured memory_bytes: 3108
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

int main()
{
    vector<int> a(3);
    for(int i=0; i<3; ++i)
        cin >> a[i];

    sort(a.begin(), a.end());
    if(a[0] + a[1] == a[2])
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

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

namespace ABC170D
{
    class Class1
    {
        static void Main(string[] args)
        {
            long N = long.Parse(Console.ReadLine());
            string[] Ainput = Console.ReadLine().Split(' ');
            long[] A = new long[N+1];
            for(int i = 0; i < N; i++)
            {
                A[i] = long.Parse(Ainput[i]);
            }
            A[N] = 1000001;
            Array.Sort(A);
            bool[] hantei = new bool[1000001];
            int ans = 0;
            for(int i = 0; i < N; i++)
            {
                if (hantei[A[i]] == false)
                {
                    int j = 1;
                    while (j * A[i] <= 1000000)
                    {
                        hantei[j * A[i]] = true;
                        j += 1;
                    }
                    if (A[i] != A[i + 1])
                    {
                        ans += 1;
                    }
                }
            }
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 44612
#include<iostream>
#include<algorithm>
using namespace std;
long long p[100000], q[100000], h, w, sum;
pair<long long, int>x[200000]; long long XX, YY;
int main() {
	cin >> h >> w; XX = h + 1, YY = w + 1;
	for (int i = 0; i < h; i++) { cin >> p[i]; x[i] = make_pair(p[i], 0); }
	for (int i = 0; i < w; i++) { cin >> q[i]; x[i + h] = make_pair(q[i], 1); }
	sort(x, x + h + w);
	for (int i = 0; i < h + w; i++) {
		if (x[i].second == 0) { sum += YY*x[i].first; XX--; }
		if (x[i].second == 1) { sum += XX*x[i].first; YY--; }
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 4992
import math
import collections

N, M = map(int, input().split())
MOD = 10 ** 9 + 7


def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors


def comb(n,k,p):
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = factorial(n) % p
    b = factorial(k) % p
    c = factorial(n - k) % p
    return (a * power_func(b, p - 2, p) * power_func(c, p - 2, p)) % p


def power_func(a,b,p):
    if b == 0: return 1
    if b % 2 == 0:
        d = power_func(a, b // 2, p)
        return d * d % p
    if b % 2 == 1:
        return (a * power_func(a, b - 1, p)) % p

def m():
    ans = 1
    f = prime_factors(M)
    counts = collections.Counter(f)
    for k,v in counts.items():
        ans *= comb(v + N-1, N-1, MOD)
    return ans % MOD

print(m())

Measured memory_bytes: 112220
#include<stdio.h>
int c[64][64];
int dp[64][64];
int main()
{
	for(int i=0;i<=50;i++)
	{
		c[i][0]=1;
		for(int j=1;j<=i;j++)
		{
			c[i][j]=c[i-1][j-1]+c[i-1][j];
			if(c[i][j]>=1000000007)
			{
				c[i][j]-=1000000007;
			}
		}
	}
	dp[1][49]=1;
	dp[1][50]=1;
	for(int i=1;i<=50;i++)
	{
		for(int j=-i;j<=i;j++)
		{
			for(int k=0;k<=50-i;k++)
			{
				for(int l=0;l<=50-i-k;l++)
				{
					if(k==0&&l==0)
					{
						continue;
					}
					if((j+k-l)&1)
					{
						continue;
					}
					if(j+k+l<0||j-k-l>0)
					{
						continue;
					}
					int inc=(long long)c[i+k][k]*c[i+k+l][l]%1000000007;
					dp[i+k+l][((j+k-l)>>1)+50]+=(long long)dp[i][j+50]*inc%1000000007;
					if(dp[i+k+l][((j+k-l)>>1)+50]>=1000000007)
					{
						dp[i+k+l][((j+k-l)>>1)+50]-=1000000007;
					}
				}
			}
		}
	}
	int n;
	scanf("%d",&n);
	printf("%d\n",dp[n][50]);
	return 0;
}

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

int gcd(int a, int b)
{
  if(a < b)swap(a, b);
  int r = a%b;
  while(r != 0)
  {
    a = b;
    b = r;
    r = a%b;
  }
  return b;
}

int main()
{
  long long a, b;
  long long c, d;
  cin >> a >> b >> c >> d;
  long long u = b-a+1;
  long long cc = b/c - (a-1)/c;
  long long dd = b/d - (a-1)/d;
  long long lcm = c * d / gcd(c, d);
  long long cd = b/lcm - (a-1)/lcm;
  cout << u - (cc + dd - cd) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define FOR(i,a,n) for(register int i=a; i<=n; ++i)
#define FDR(i,a,n) for(register int i=a; i>=n; --i)
#define mem(a) memset(a, 0, sizeof(a))
#define pb push_back()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int maxn = 100005;
const int MOD = 1000000009;
int a[maxn];
string str;
int main()
{
    cin >> str;
    bool flag = true;
    int sum = 0;
    for(int i = 0; i < str.size(); i++)
    {
        if(i == 0 && str[i] != 'A')flag = false;
        if(str[i] >= 'A' && str[i] <= 'Z')sum++;
        if((i < 2 || i == str.size()-1) && str[i] == 'C')flag = false;

    }
    if(sum > 2|| sum == 1)flag = false;
    if(flag)puts("AC");
    else puts("WA");
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define foreach(i,n) for(auto &&i:n)
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort(all(x))
#define REV(x) reverse(all(x))
#define MAX(x) *max_element(all(x))
#define MIN(x) *min_element(all(x))
#define LOWitr(x, n) lower_bound(all(x), n)
#define UPRitr(x, n) upper_bound(all(x), n)
#define cii(x) int x;cin >> x
#define cill(x) LL x;cin >> x
#define cis(x) string x;cin >> x
#define co(x) cout << x << endl
#define dump(x)  cout << #x << " = " << (x) << endl
#define truecheck assert
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef long long int64;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
template<class T,class U>bool chmax(T &a, const U &b){if (a<b){a=b;return true;}return false;}
template<class T,class U>bool chmin(T &a, const U &b){if (b<a){a=b;return true;}return false;}
template<class T,class U>void vcin(T &v, U n){rep(i, n){typename T::value_type a;cin >> a;v.pb(a);}}
const int INF = 1e9, MOD = 1e9 + 7;
const LL LLINF = 1e16;

int main() {
    fastcin();
    cout << fixed << setprecision(10);
    cii(n);
    cii(x);
    cii(y);
    VI vi(n+10);
    rep1(j, n-1){
        for (int k = j + 1; k <= n; ++k){
            vi[min(k - j, abs(x - j) + 1 + abs(y - k))]++;
        }
    }
    rep1(i, n-1){
        co(vi[i]);
    }
    return 0;
}

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

signed main(){
    string S;
    int Q;
    cin >> S >> Q;
    
    int Query,F,Q_cnt=0;
    char C;
    for(int i=0;i<Q;i++){
        cin >> Query;
        
        if(Query == 1){
            Q_cnt++;
        }else{
            cin >> F >> C;
            if(F-1==Q_cnt%2) S.insert(S.begin(),C);
            else S.push_back(C);
        }
    }
    
    if(Q_cnt%2 == 0) cout << S << endl;
    else{
        reverse(S.begin(),S.end());
        cout << S << endl;
    }
    return 0;
}



Measured memory_bytes: 900
#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#include <numeric>
#include <queue>
#include <sstream>
#include <string>
#include <string.h>
#include <tuple>
#include <vector>

#define REP(i,x) for(int i{ 0 }; i < (int)(x); i++)
#define REPC(i,x) for(int i{ 0 }; i <= (int)(x); i++)
#define RREP(i,x) for(int i{ (int)(x) - 1 }; i >= 0 ;i--)
#define RREPC(i,x) for(int i{ (int)(x)}; i >= 0; i--)
#define REP1O(i,x) for(int i{ 1 }; i < (int)(x); i++)
#define REP1C(i,x) for(int i{ 1 }; i <= (int)(x); i++)

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef int64_t ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tupiii;
typedef tuple<ll, ll, ll> tuplll;

const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;
const int MOD = 1000000007;

template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
inline void swap(ll& a, ll& b) { a ^= b; b ^= a; a ^= b; }
inline void swap(int& a, int& b) { a ^= b; b ^= a; a ^= b; }



int main()
{
	char a, b;
	cin >> a >> b;

	if (a == 'H')
		cout << b << endl;
	else
	{
		if (b == 'H')
			cout << 'D' << endl;
		else
			cout << 'H' << endl;
	}

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long dp[3005][3005][3];
vector<long long> V;
long long f(int lo, int hi, int e){
	if(lo>hi) return 0;
	if(dp[lo][hi][e] != -1) return dp[lo][hi][e];
	int s = 0;
	if(!e) s = 1;
	return dp[lo][hi][e] = max(V[lo] - f(lo + 1, hi, s) , V[hi] - f(lo, hi - 1, s));
}
int main() {
	int n;
	long long a, s = 0;
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> a;
		V.push_back(a);
		s+=a;
	}
	memset(dp, -1, sizeof(dp));
	cout << f(0, n-1, 1);
	return 0;
}

Measured memory_bytes: 212224
N, M = gets.split.map(&:to_i)
MAX = 1 << 30
dist = Array.new(N) { Array.new(N, MAX) }
graph = []
M.times do
  a, b, c = gets.split.map(&:to_i)
  graph << [a-1, b-1, c]
  dist[a - 1][b - 1] = dist[b - 1][a - 1] = c
end

N.times do |k|
  N.times do |i|
    N.times do |j|
      dist[i][j] = dist[i][k] + dist[k][j] if dist[i][j] > dist[i][k] + dist[k][j]
    end
  end
end
ans = 0
graph.each do |(a,b,c)|
  ans += 1 if dist[a][b] < c
end
p ans

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

const int maxn=1e6+5;

inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}

bool vis[maxn];
int a[maxn];

bool deal(int n)
{
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            if(vis[i]) return false;
            vis[i]=true;
            while(n%i==0) n/=i;
        }
    }
    if(n>1)
    {
        if(vis[n]) return false;
        vis[n]=true;
    }
    return true;
}

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

    int n,res=0;cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        res=gcd(a[i],res);
    }
    bool ans=true;
    for(int i=n;i>=1;i--)
    {
        ans=deal(a[i]);
        if(!ans) break;
    }
    if(ans) cout<<"pairwise coprime";
    else if(res==1) cout<<"setwise coprime";
    else cout<<"not coprime";
    return 0;
}

Measured memory_bytes: 7532
#include <iostream>
#include <cmath>
#include <queue>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <functional>
using namespace std;

long long N, A[200009], L;

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i]; A[i] -= i;
	}
	sort(A, A + N);
	for (int i = 0; i < N; i++) {
		L += abs(A[i] - A[N / 2]);
	}
	cout << L << endl;
	return 0;
}

Measured memory_bytes: 1792