akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring> //memset(dp,0,sizeof(dp))
#include <functional>
#include <cctype>
#include <locale>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ppb pop_back()
#define ALL(a) (a).begin(),(a).end()
#define int long long
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
//s[i]=tolower(s[i]); islower(s[i]); cout << tolower(s[i])はバグ

int dp[1025][100001];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector<P> v(n+1);
    rep(i,n){
        cin >> v[i+1].fi >> v[i+1].se;
    }
    int x=0;
    if(n!=1) x+=log2(n/2);
    chmin(x,10);
    for(int i=1;i<(1<<x);i++){
        rep(j,100001){
            chmax(dp[i][j],dp[i/2][j]);
            if(j-v[i].se>=0) chmax(dp[i][j],dp[i/2][j-v[i].se]+v[i].fi);
        }
    }
    int q; cin >> q;
    rep(query,q){
        int V,L;
        cin >> V >> L;
        if(V<(1<<x)){
            cout << dp[V][L] << '\n';
        }else{
            vector<P> vec;
            while(V>=(1<<x)){
                vec.emplace_back(v[V]);
                V/=2;
            }
            int ans=0,sz=vec.size();
            rep(i,1<<sz){
                int resW=0,resV=0;
                rep(j,sz){
                    if(i&(1<<j)){
                        resV+=vec[j].fi;
                        resW+=vec[j].se;
                    }
                }
                if(L-resW<0) continue;
                chmax(ans,resV+dp[V][L-resW]);
            }
            cout << ans << '\n';
        }
    }
    return 0;
}


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

using ll = long long;
using ull = unsigned long long;

#define MOD 1000000007

int main(void) {
    ll N, X;
    ll count = 1;
    ll sum = 0;
    vector<ll> L;
    cin >> N >> X;
    L.resize(N);
    for(ll i = 0;i < N;i++) cin >> L[i];
    for(ll i = 0;i < N;i++) {
        sum += L[i];
        count++;
        if(sum > X) {
            count--;
            break;
        }
        if(sum == X) break;
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var x, a, b int
	fmt.Scan(&x,&a,&b)
	
	if a >= b {
		fmt.Println("delicious")
	} else if a + x >= b {
		fmt.Println("safe")
	} else {
		fmt.Println("dangerous")
	}
}

Measured memory_bytes: 512
#include <iostream>
using namespace std;
int main(){
    int n,a;
    cin>>n;
    int p[n+1];
    for(int i=0;i<=n;i++){
        cin>>p[i]>>p[i+1];
    }
    int m[n+1][n+1];
    for(int i=1;i<=n;i++){
        m[i][i]=0;
    }
    for(int l=2;l<=n;l++){
        for(int i=1;i<=n-l+1;i++){
            int j=i+l-1;
            m[i][j]=100000000;
            for(int k=i;k<=j-1;k++){
                int q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                if(q<m[i][j]){
                    m[i][j]=q;
                }
            }
        }
    }
    cout<<m[1][n]<<endl;
    return 0;
}


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


//c++ templte for help............................................................................................................................................
typedef long long ll;

//template<typename... T>
//void print1(T... t){
	//((cout<<t<<" "),...);
//}

//template<typename... T>
//void print2(T... t){
		//vector<vector<ll>> ans={t...};
		//for(ll i=0;i<(ll)ans.size();i++){
			//if(i!=0) cout<<"\t\t";
			//else cout<<"\t";
			//for(ll j=0;j<(ll)ans[i].size();j++){
				//cout<<ans[i][j]<<" ";
			//}
			//if(i!=(ll)ans.size()-1)
			//cout<<endl;
		//}
//}	
//#define deb(...) cout<<" [ "#__VA_ARGS__<<" : "; print1(__VA_ARGS__); cout<<"]"<<endl; 
//#define vdeb(...) cout<<" [ "#__VA_ARGS__<<" : "; print2(__VA_ARGS__); cout<<"]"<<endl;





	
 
//for loop
//#define fo(i,n) for(int i=0;i<(ll)n;i++)
//#define Fo(i,k,n) for(int i=k;i<n;i++)
 
 
//to print vector element 
//template<typename T>
//void printV(T vec){
	//fo(i,vec.size()) cout<<vec[i]<<" "<<flush;
	//cout<<endl;
	//}
	
 
//#define modulo 1000000007
//const int INF=1e9+5;
 
//iterate map
//template<typename T>
//void itR(T map){
	 //for(auto itr=map.begin();itr!=map.end();itr++){
				//deb(itr->first,itr->second);
			//}
	//cout<<endl;
//}
 
 
 
//c++ template for help...........................................................................................................................................


ll solve(){
	vector<int> vec(5);
	for(int i=0;i<5;i++){
		cin>>vec[i];
		if(vec[i]==0) return i+1;
	}
	return 0;
}

int main() {
	//stringstream ss;
	//ss<<"akhil";
	//cout<<ss.str()<<endl;
	cout<<setprecision(50);
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	
	 // TESTCASE KO DEKH KA BHAUT SARA CONDITION GENERATE MAT KRO 
	 // PAPER PD CONFIRM HO JAO THORA JADA TIME HI KYU NA LGA
	 // greedy ma jadatr exceptional case check kr ke dekh lo
	 
	 // WHILE DOING THE QUESTION OF DYNAMIC PROGRAMMING GREEDY KA TRAH SOCHNA BAND KRO
	 // DP M DATA KA BHI USE KRNA PDTA HA BE BHULO MT 
	 // DP BHI WO LEETCODE WALE MATRIX KA QUESTION KI TARAH HA
	 // CONSTRAIN WILL BE THE DIMENSION OF DP
	 // DP MA STATE PTA KRO AUR PHIR FUNCTION GENERATE KRO
	 // OBJECT KO CHOOSE KIA YA NAE KIA AGAR KIA TO KYA HOGA AUR NAE KIA TO KYA HOGA
	 // KYA KYA CHEJ IMPORTANT HA WO STATE BN JAGA AUR HUM LOG STATE KO CHANGE KR SKTA HA JYSA KNPSACK 2 WALE PROBLEM MA KIA THA
	 

	 
	//ll testCase;
	//cin>>testCase;
	//for(ll tt=0;tt<testCase;tt++){
		//solve();
		ll ans=solve();
		cout<<ans<<endl;
	//}
	return 0;
}


Measured memory_bytes: 3636
using System;

namespace B
{
    class B
    {
        static void Main(string[] args)
        {
            int n, q, i, count = 0;
            string a;
            string[] b = new string[30000];
            int[] S = new int[100000];
            BinarySearch search = new BinarySearch();
            a = Console.ReadLine();
            n = int.Parse(a);
            b = Console.ReadLine().Split(' ');
            for (i=0; i<n; i++)
            {
                S[i] = int.Parse(b[i]);
            }
            a = Console.ReadLine();
            q = int.Parse(a);
            b = Console.ReadLine().Split(' ');
            for (i=0; i<q; i++)
            {
                count = count + search.count(S, int.Parse(b[i]), n);
            }

            Console.WriteLine(count);
            
        }
    }
    
    class BinarySearch
    {
        
        public int count(int[] A, int key, int n)
        {
            int left = 0;
            int right = n;
            while (left < right)
            {
                int mid = (left + right) / 2;
                if (key == A[mid])
                {
                    return 1;
                }
                else if(key>A[mid]){
                    left = mid + 1;
                }
                else
                {
                    right = mid;
                }
            }
            return 0;
        }
    }
}



Measured memory_bytes: 20208
import std.stdio, std.conv, std.array, std.string;
import std.algorithm;
import std.container;
import std.range;
import core.stdc.stdlib;
import std.math;
import std.typecons;

void main() {
  auto N = readln.chomp.to!int;
  int[] prices;
  foreach(i; 0..50000) {
    auto price = cast(int)(1.08f * cast(real)i);
    if (price == N) {
      prices ~= i;
    } 
  }

  if (prices.length == 0) {
    writeln(":(");
  } else {
    writeln(prices[0]);
  }
}


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

using namespace std;

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

	int n, k;
	string s;
	cin >> n >> k >> s;
	int ans = 0;
	int l = 0, cur_k = 0;
	for (int r = 0; r < n; r++) {
		if (s[r] == '0' && ((r == 0) || (s[r - 1] == '1')))
			cur_k++;
		while(cur_k > k && l < r) {
			l++;
			if (s[l] == '1' && s[l - 1] == '0')
				cur_k--;
		}
		ans = max(ans, r - l + 1);
	}
	cout << ans << endl;
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define int long long
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

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

int n, m;
string s, t;
map<int, char> dict;

signed main() {
	int i;
	
	cin >> n >> m >> s >> t;
	int l = lcm(n, m);
	
	rep(i, n) {
		int id = i * l / n;
		dict[id] = s[i];
	}
	
	rep(i, m) {
		int id = i * l / m;
		if (dict.find(id) == dict.end()) continue;
		if (dict[id] != t[i]) {
			cout << "-1" << endl;
			return 0;
		}
	}
	cout << l << endl;
	return 0;
}

Measured memory_bytes: 6144
temp=input().split(' ')
N=int(temp[0])
K=int(temp[1])

flag=[1 for n in range(N)]

for k in range(K):
  d=int(input())
  A=input().split(' ')
  for a in A:
    flag[int(a)-1]=0

ans=sum(flag)
print(ans)

Measured memory_bytes: 67592
s=int(input())
p=10**9+7
if s<=2:
    print(0)
    exit()
n=s//3
ans=0
x=[0]*(s+1)
x[0]=1
x[1]=1
y=[0]*(s+1)

for i in range(2,s+1):
    x[i]=x[i-1]*i%p

y[s]=pow(x[s],p-2,p)
for i in range(s):
    y[s-1-i]=y[s-i]*(s-i)%p

for k in range(1,n+1):
    ans+=x[s-2*k-1]*y[k-1]*y[s-3*k]%p

print(ans%p)



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

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

const int maxn = 1e5 + 10;
vector<int> adj[maxn]; 
int p[maxn], n, k;

int main(int argc, char const *argv[]) {
#ifdef LOCAL_TESTING
	freopen("in", "r", stdin);
#endif
	scanf("%d", &n); p[n] = -1;
	for(int i = 1; i < n; ++i) {
		int u, v; p[i] = -1;
		scanf("%d %d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	} scanf("%d", &k);	
	priority_queue<ii, vector<ii>, greater<ii> > q;
	for(int i = 0; i < k; ++i) {
		int u; scanf("%d", &u);
		scanf("%d", &p[u]);
		q.push({p[u], u});
	} 
	while(!q.empty()) {
		ii x = q.top(); q.pop(); 
		int val = x.first, u = x.second; 
		for(int v : adj[u]) {
			if(p[v] == -1) {
				p[v] = val + 1;
				q.push({p[v], v});
			}
			else if(abs(p[v] - p[u]) != 1) {
				puts("No"); return 0;
			}
		}
	}
	puts("Yes");
	for(int i = 1; i <= n; ++i) {
		printf("%d\n", p[i]);
	}
}

Measured memory_bytes: 7924
import sys

input = sys.stdin.readline

# input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    b = list(map(int, input().split()))
    ans = []

    for i in range(N):
        for j in range(len(b))[::-1]:
            if j+1 == b[j]:
                ans.append(b[j])
                b.remove(b[j])
                break
        else:
            print(-1)
            return

    ans = ans[::-1]
    for i in range(N):
        print(ans[i])


if __name__ == '__main__':
    main()


Measured memory_bytes: 38652
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <algorithm>
#include <array>
#include <complex>
#include <string>
#include <utility>
#include <map>
#include <queue>
#include <list>
#include <functional>
#include <numeric>
#include <stack>
#include <tuple>

using namespace std;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
const int INF = 100000000;
const long long LINF = 1000000000000000000;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-6;
using pii = std::pair<int, int>;
using ll=long long;  
using pLL = std::pair<ll, ll>;

#define SORT(v) std::sort(v.begin(), v.end())
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M,count=0;
    cin >> N;
    if(N==25) cout << "Christmas" <<endl;
    if(N==24) cout << "Christmas Eve" <<endl;
    if(N==23) cout << "Christmas Eve Eve" <<endl;
    if(N==22) cout << "Christmas Eve Eve Eve" <<endl;
    return 0;
}

Measured memory_bytes: 256
整数 = int
入力 = input
各々 = map
文字列 = str
分割 = 文字列.split
配列 = list
総和 = sum
絶対値 = abs
出現回数 = 配列.count
出力 = print
零 = 0
真偽 = bool
又 = 真偽.__or__
且 = 真偽.__and__
余 = 整数.__mod__
和 = 整数.__add__
積 = 整数.__mul__
弐 = 2
壱 = 1
最小値 = min
差 = 整数.__sub__
負 = lambda 整数: 整数 < 零


長さ = 整数(入力())
整数列 = 配列(各々(整数, 分割(入力())))
絶対値列 = 配列(各々(絶対値, 整数列))


絶対値の和 = 総和(絶対値列)
零の数 = 出現回数(整数列, 零)
負の数の数 = 総和(各々(負, 整数列))


出力(差(絶対値の和,
      積(最小値(絶対値列),
          積(弐,
              差(壱,
                 整数(又(真偽(零の数),
                         真偽(余(和(負の数の数, 壱), 弐)))))))))


Measured memory_bytes: 14500
using System;
using System.IO;

class Solve{
    static void Main(string[] args){
        var arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        var a = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        var N = arr[0];
        var x = arr[1];
        Array.Sort(a);
        var answer = 0;
        int i = 0;
        for (; i < N; i++){
            if (a[i] > x){
                x = 0;
                break;}
            answer++;
            x -= a[i];}
        if (x > 0 && answer > 0) answer--;
        var writer = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(writer);
        Console.WriteLine(answer);
        Console.Out.Flush();}}

Measured memory_bytes: 27288
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef complex <double> cp;
#define debug(a) cout<<#a<<":"<<a<<endl;
#define fr freopen("in.txt","r",stdin);
#define Fill(x,a) memset(x,a,sizeof(x))
#define cpy(a,b) memcpy(a,b,sizeof(a))
const double PI = acos(-1);
const ll INF=0x3f3f3f3f;
const ll N=1e6+7;
const ll mod=1e9+7;
ll maxn,minn;
ll T,n,m,q;
ll flag = 0;
ll g[N];
map<ll,ll>mp;
ll arr[N];

bool isprime[N];
ll prime[N/10];
void primes(){
    memset(isprime,false,sizeof(isprime));
    isprime[1]=true,m=1;
    for(ll i=2;i<N;i++){
        if(!isprime[i]){
            prime[m++] = i;
            for(ll j=i*i;j<N;j+=i)	isprime[j] = true;
        }
    }
}

void solve(ll n){ //n的因子个数
	for(ll i=1;i<=m&&prime[i]*prime[i]<=n;i++){
		if(n%prime[i]==0){
			if(mp[prime[i]]){
				flag = 1;
			}
			mp[prime[i]] = 1;
			while(n%prime[i] == 0){
				n /= prime[i];
			}
		}
	}
	if(n != 1){
		if(mp[n]){
			flag = 1;
		}
		else{
			mp[n] = 1;
		}
	} 
	return ;
}


int main(){
	primes();
	cin >> n;
	for(ll i = 1; i <= n; i ++ ){
		scanf("%lld", arr + i);
	}
	for(ll i = 1;i <= n; i++ ){
		solve(arr[i]);
		if(flag == 1){
			break;
		}
	}
	if(flag == 0){
		puts("pairwise coprime");
	}
	else{
		g[n] = arr[n];
		for(ll i = n - 1; i >= 1; i -- ){
			g[i] = __gcd(g[i + 1], arr[i]);
		}
		if(g[1] == 1){
			puts("setwise coprime");
		}
		else{
			puts("not coprime");
		}
	}
	
	
	
	
	
	
	
	
	


	return 0;
}



Measured memory_bytes: 20868
#include <bits/stdc++.h>
#include <iomanip>
#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() {
  double r;
  cin >> r;
  cout << 2*r*3.1415 << endl;
  return 0;
}


Measured memory_bytes: 3788
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define reps(i,a,b) for(int i= a; i < b; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main()
{
  ll w, h, x, y;
  cin >> w >> h >> x >> y;
  printf("%.9f", w*h/2.0);
  cout << " ";
  if (w/2.0 == x && h/2.0 == y) {
    cout << 1 << endl;
  } else {
    cout << 0 << endl;
  }
  return 0;
}

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

#define int long long int 
#define pi pair<int,int>
#define pb push_back
#define fi first
#define se second
#define inf 1e18
#define endl '\n'
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FILEIO(name) \
    freopen(name".in","r",stdin); \
    freopen(name".out","w",stdout);

const int N=100005;
int l[N];
int dp[N]={0};

signed main()
{
    IOS;
    int n,k;
    cin>>n>>k;
    for (int i=0;i<n;i++) cin>>l[i];
    for (int i=1;i<n;i++)
    {
      int temp=inf;
      for (int j=1;j<=min(k,i);j++)
      {
        temp=min(temp,dp[i-j]+abs(l[i]-l[i-j]));
      }
      dp[i]=temp;
    }
    cout<<dp[n-1]<<endl;
    return 0;
}

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

using namespace std;

int main()
{
	int n; 
	cin >> n;
	vector <int> v(n);
	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}
	int a = 0;
	while (true)
	{
		for (int i = 0; i < n; i++)
		{
			if (v[i] % 2 == 0)
			{
				v[i] /= 2;
			}
			else
			{
				cout << a << endl;
				return 0;
			}
		}
		a++;
	}
	return 0;
}

Measured memory_bytes: 256
using static System.Math;
using static System.Console;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System;

namespace AtCoder
{
    class Program
    {
        private static long mod = 1000000007;
        static void Main(string[] args)
        {
            //var n = int.Parse(ReadLine());
            //var line = ReadLine().Split(' ').Select(value => long.Parse(value)).ToArray();

            var s = ReadLine();

            if(s.Last() == 's')
            {
                WriteLine(s + "es");
            }
            else
            {
                WriteLine(s + "s");
            }
        }
    }
}


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

#define int long long
//#define uint __int128_t

#define pb push_back
#define fi first
#define se second
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define low(a,b) lower_bound(all(a),(b))-(a).begin()
#define upp(a,b) upper_bound(all(a),(b))-(a).begin()
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<vint> vvint;
typedef vector<pint>vpint;
typedef pair<pint,int> P1;
typedef pair<int,pint> P2;
typedef pair<pint,pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD=1000000007;
const ll INF=1e18;

int N;
int p[202];
int A,B;
int cnt[3];

signed main() {
    IOS();
    //(1ll<<N)シフト演算のオーバーフローに気をつける
    //MOD同士の引き算に注意
    cin>>N>>A>>B;
    rep(i,0,N){
        cin>>p[i];
        if(p[i]<=A)cnt[0]++;
        else if(p[i]<=B)cnt[1]++;
        else cnt[2]++;
    }
    cout<<min({cnt[0],cnt[1],cnt[2]})<<endl;
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

def main():
    h, n = rli()
    la = rli()
    if (sum(la) >= h):
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()


Measured memory_bytes: 13964
import math


def solve(N, D):
    return math.ceil(N / (2 * D + 1))


if __name__ == "__main__":
    # N = int(input())
    # Vs = list(map(int, input().split(" ")))
    N, D = tuple(map(int, input().split()))
    print(solve(N, D))


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

int main() {
    int A,B,C,D,E,F,G,H,I;
    int result=0;
    vector<int> lacked;

    cin >> A >> B >> C >> D >> E >> F >> G >> H >> I;

    for (int i=1; i<=9 ;i++) {
        if (
            A != i &&
            B != i &&
            C != i &&
            D != i &&
            E != i &&
            F != i &&
            G != i &&
            H != i &&
            I != i
        ) {
            lacked.push_back(i);
        }
    }

    do {
        int cnt=0;
        int num1=0,num2=0,num3=0,num4=0;

        if (A != -1) num1 += A;
        else {
            num1 += lacked[cnt];
            cnt++;
        }

        if (B != -1) num2 += B*10;
        else {
            num2 += lacked[cnt] * 10;
            cnt++;
        }

        if (C != -1) num2 += C*1;
        else {
            num2 += lacked[cnt] * 1;
            cnt++;
        }


        if (D != -1) num3 += D*100;
        else {
            num3 += lacked[cnt] * 100;
            cnt++;
        }

        if (E != -1) num3 += E*10;
        else {
            num3 += lacked[cnt] * 10;
            cnt++;
        }

        if (F != -1) num3 += F*1;
        else {
            num3 += lacked[cnt] * 1;
            cnt++;
        }

        if (G != -1) num4 += G*100;
        else {
            num4 += lacked[cnt] * 100;
            cnt++;
        }

        if (H != -1) num4 += H*10;
        else {
            num4 += lacked[cnt] * 10;
            cnt++;
        }

        if (I != -1) num4 += I*1;
        else {
            num4 += lacked[cnt] * 1;
            cnt++;
        }


        if (num1 + num2 + num3 == num4) {
            result++;
        }

    } while (next_permutation(lacked.begin(), lacked.end()));


    cout << result << endl;
    

    return 0;
}



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

#define mod 1000000007
#define pb push_back
#define ff first
#define ss second
#define ll unsigned long long 
 
using namespace std;

 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	int p[n];
	int maxi=INT_MIN;
	ll sum=0;
	for(int i=0;i<n;i++)
	{
	     cin>>p[i];
	     if(p[i]>maxi)
	     maxi=p[i];
	     sum+=p[i];
	}
	cout<<sum-maxi/2;
	
	return 0;
}


Measured memory_bytes: 3624
#include <cstdio>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <ctime>
#include <cstring>
#include <cassert>
#include <bitset>
#include <sstream>
#include <queue>

#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define sz(a) ((int) (a).size())
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

typedef long long int64;
typedef long double ldb;

const long double eps = 1e-9;
const int inf = (1 << 30) - 1;
const long long inf64 = ((long long)1 << 62) - 1;
const long double pi = acos(-1);

template <class T> T sqr (T x) {return x * x;}
template <class T> T abs (T x) {return x < 0 ? -x : x;}

const int MAXN = 120 * 1000;

int a[MAXN], ind[MAXN];

bool comp(int ind1, int ind2) {
	return (a[ind1] < a[ind2]);
}

int main () {
//  ios_base::sync_with_stdio(0);
//	freopen("input.txt", "rt", stdin);
//	freopen("output.txt", "wt", stdout);

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

	sort(ind, ind + n, comp);

	int res = 0;
	for (int i = 0; i < n; ++i) {
		if (ind[i] % 2 != i % 2) {
			res++;
		}
	}
	res /= 2;

	cout << res << endl;

	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define MAX 300005
int main() {
    LL n, d;
    cin>>n>>d;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        LL x, y;
        scanf("%lld%lld", &x,&y);
        if(x * x + y * y <= d * d)ans++;
    }
    cout<<ans;
}

Measured memory_bytes: 3752
#define N 100001 
long p[N],r[N],n,m,i,b[N],a[N][2],c,d;int f(int x){if(p[x]==x)return x;return p[x]=f(p[x]);}int u(int x,int y){x=f(x);y=f(y);p[x]=y;r[y]+=r[x];r[x]=r[y];}int main(){scanf("%ld%ld",&n,&m);for(i=0;i<m;i++)scanf("%d%d",a[i],&a[i][1]);b[m]=n*(n-1)/2;for(i=0;i++<N;){p[i]=i;r[i]=1;};for(i=m;i-->0;){c=a[i][0],d=a[i][1];b[i]=b[i+1];if(f(c)!=f(d)){b[i]-=r[f(c)]*r[f(d)];u(c,d);}}for(i=0;i++<m;)printf("%ld\n",b[i]);}

Measured memory_bytes: 5120
import sys
import math
def I():return int(sys.stdin.readline().replace("\n",""))
def I2():return map(int,sys.stdin.readline().replace("\n","").split())
def S():return str(sys.stdin.readline().replace("\n",""))
def L():return list(sys.stdin.readline().replace("\n",""))
def Intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def Lx(k):return list(map(lambda x:int(x)*-k,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":
    n ,k = I2()
    a = Intl()
    #minは1なのである要素から1までの距離を考えて、それをk-1で割った商が置き換え回数
    print(math.ceil((n - 1)/(k - 1)))

Measured memory_bytes: 20512
<?php
fscanf(STDIN, '%d %d', $n, $k);
fscanf(STDIN, '%s', $s);
$i = $top = $cnt = $ans = 0;
$top_s = $s[$top];
while($top < $n) {
    $next_s = ($top_s === 'L') ? 'R' : 'L';
    $next_top = strpos($s, $next_s, $top);
    if ($next_top === false) $next_top = $n;
    $cnt_s = $next_top - $top;
    if ($i % 2 === 1) $cnt++;
    if ($cnt <= $k && $i !== 0) $ans += $cnt_s;
    else $ans += $cnt_s - 1;
    $i++;
    $top_s = $next_s;
    $top = $next_top;
}
echo $ans . PHP_EOL;

Measured memory_bytes: 4728
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define rep2(i,n) for(int i=1; i<=(n); ++i)
#define Sort(x) sort((x).begin(),(x).end())
#define Sort2(x) sort((x).begin(),(x).end(), greater<int>())
#define pb push_back
using namespace std;
using ll = long long;
using P = pair<int,int>;


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

    return b;
}

int main()
{    
    int k; cin >> k; ll sum = 0;
    rep2(a,k){
        rep2(b,k){
            rep2(c,k){
                sum += gcd(gcd(a,b),c);
            }
        }
    }
    cout << sum << endl;
}

/*
Ctrl+@ でコンソールを開け、以下で実行。
g++ code3.cpp
./a.out
*/

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

using namespace std;
typedef pair<int,int> PII;
#define MP make_pair;

int hp, hp_max;
int R, C;
char maze[101][101];
int T;
int dat[101][101];
int S;
PII path[1001];
int P;
int portion[16];
int dp[1<<12][1010];

int main(){
  while(cin>>hp>>hp_max, hp){
	cin >> R >> C;
	for(int y=0;y<R;++y)
	  for(int x=0;x<C;++x)
		cin >> maze[y][x];
	cin >> T;
	for(int t=0;t<T;++t){
	  char c; int d; cin >> c >> d;
	  for(int y=0;y<R;++y)
		for(int x=0;x<C;++x)
		  if(maze[y][x] == c)
			dat[y][x] = d;
	}
	cin >> S;
	int N = 1;
	path[0].first = 0;
	path[0].second = 0;
	for(int i=0;i<S;++i){
	  char c; int x;
	  cin >> c >> x;
	  switch(c){
	  case 'U':
		for(int j=0;j<x;++j){
		  path[N] = path[N-1];
		  path[N++].first--;
		}
		break;
	  case 'D':
		for(int j=0;j<x;++j){
		  path[N] = path[N-1];
		  path[N++].first++;
		}
		break;
	  case 'L':
		for(int j=0;j<x;++j){
		  path[N] = path[N-1];
		  path[N++].second--;
		}
		break;
	  case 'R':
		for(int j=0;j<x;++j){
		  path[N] = path[N-1];
		  path[N++].second++;
		}
		break;
	  }
	}
	cin >> P;
	for(int i=0;i<P;++i) cin >> portion[i];

	fill((int*)dp, (int*)dp+(1<<12)*1010, 0);
	dp[0][0] = hp;
	for(int i=0;i<N;++i){
	  int y = path[i].first, x = path[i].second;
	  for(int b=0;b<1<<P;++b){
		if(!dp[b][i]) continue;
		if(dp[b][i] > dat[y][x])
		  dp[b][i+1] = max(dp[b][i+1], dp[b][i] - dat[y][x]);
		else
		  for(int j=0;j<P;++j)
			if((b>>j&1) == 0)
			  dp[b|(1<<j)][i] = max(dp[b|(1<<j)][i], min(hp_max, dp[b][i] + portion[j]));
	  }
	}

	bool ans = false;
	for(int b=0;b<1<<P;++b)
	  if(dp[b][N]) ans = true;
	cout << (ans? "YES": "NO") << endl;
  }
  
  return 0;
}

Measured memory_bytes: 19320
#include<bits/stdc++.h>
#define tmp(x) std::cout<<"& "<<(x)<<" &\n"
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;

using namespace std;
const int maxn=2e5+100;
int n,t;

int main(){
//	freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int x;
 	cin>>x;
 	if(x>=30)cout<<"Yes";
 	else cout<<"No";
 	
 
 
 
    return 0;
}

Measured memory_bytes: 3632
N,A,B,C,D=map(int,input().split())
mod=10**9+7

factorial=[1]
for i in range(1,1001):
    factorial.append((factorial[-1]*i)%mod)

inverse=[pow(factorial[i],mod-2,mod) for i in range(1001)]

Inverse=[[1] for i in range(1001)]
for i in range(1001):
    for j in range(1,1001):
        Inverse[i].append((Inverse[i][-1]*inverse[i])%mod)

dp=[{i:0 for i in range(A-1,B+1)} for j in range(N+1)]

for i in range(A-1,B+1):
    dp[0][i]=1


for i in range(1,N+1):
    for j in range(A,B+1):
        dp[i][j]=dp[i][j-1]+factorial[i]*sum(dp[i-k*j][j-1]*Inverse[j][k]*inverse[k]*inverse[i-j*k] for k in range(C,min(D,i//j)+1))
        dp[i][j]%=mod

print(dp[N][B])

Measured memory_bytes: 155144
#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 ff                  first
#define ss                  second
#define endl                "\n"
#define loop(i,s,e)         for(int i=s;i<e;i++)
#define int                 long long
#define vi                  vector<int> 
#define S(v)                sort(v.begin(),v.end())
#define RS(v)               sort(v.rbegin(),v.rend())
#define R(v)                reverse(v.begin(),v.end())
#define mxpq(T)             priority_queue <T>
#define mnpq(T)             priority_queue<T,vector<T>,greater<T>>
#define prv(v)              for(auto &x : v)cout << x << " ";
#define piirv(v)            for(auto &x : v)cout << x.ff << " " << x.ss << endl;
#define prvv(v)             for(auto &x : v)for(auto &y : x.ss)cout << y << " ";
#define mp                  make_pair
#define pii                 pair<int,int>
#define mset(a,f)           memset(a , f , sizeof(a))
#define pb                  push_back
#define inf                 INT_MAX
#define INF                 LLONG_MAX
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
 
const int N = 2e6 + 6;
const int M = 1e9+7;
int A[N];
int n , m;

void solve()
{
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	cout << max({a*c , a*d , b*c , b*d});
}			
 
int32_t main()
{
 
cout<<fixed<<setprecision(16);
 
ios_base:: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
 	
 
 	int t = 1;
 	// cin >> t;
 	while(t--)solve();
  
}

Measured memory_bytes: 3648
(defun l-to-s (l)
  (format nil "~{~A~}" l))

(defun solve (str)
  (labels
    ((check (s)
       (let ((s0 (aref s 0)))
         (loop for i across s unless (eq s0 i) do (return-from check nil))
         t)) 
     (f (s c n)
       (when (check s) (return-from f n))
       (let ((ns (l-to-s (loop for i below (1- (length s))
                           collect (if (or (eq c (char s i)) (eq c (char s (1+ i))))
                                     c
                                     (char s i))))))
         (f ns c (1+ n)))))
    (loop for i below 26
        minimize (f str (code-char (+ i 97)) 0))))

(princ (solve (read-line)))

Measured memory_bytes: 15720
#include <bits/stdc++.h>
using namespace std;
using vec = vector<int>;
using intk = int64_t;

int main() {
int N;
  string S;
  cin >> N >>S;
  int ans =0;
  int kai =0;
  for(int i=0;i<N;i++){
   if(S[i] == 'I') ans++;
     else ans--;
    kai = max(ans,kai);
  }
  cout <<kai <<endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int rooms[4][3][10]={0}, sect, t1, t2, t3, t4;
  scanf("%d", &sect);
  for(int i=0;i<sect;i++){
    scanf("%d %d %d %d", &t1, &t2, &t3, &t4);
    rooms[t1-1][t2-1][t3-1]+=t4;
  }
  for(int i=0;i<4;i++){
    for(int j=0;j<3;j++){
      for(int k=0;k<10;k++){
        printf(" %d", rooms[i][j][k]);
      }
      printf("\n");
    }
    if(i!=3){for(int s=0;s<20;s++){printf("#");}printf("\n");}
  }
  return 0;
}

Measured memory_bytes: 2692
import math

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

# c = 0
# taps = 1
# while(True) :
#     # 1犠牲にしてAを得る
#     # jack = A * (taps-1) + A
#     jack = (A-1) * (taps-1) + A
#     if (jack >= B) :
#         break
    
#     taps += 1


# print(taps)

print(math.ceil((B-A) / (A-1)) + 1)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,number = 0,count = -1;
  cin >> N;
  for (int i = 0; i< N;i++){
    int l = 1,m = 2;
    for(;;){
      if ((i + 1)% m != 0 || i + 1 < m) break;
      l++;
      m *= 2;
    }
    count = max(l - 1,count);
    if (count == l - 1) number = i+1;
  }
  cout << number << endl;
}

Measured memory_bytes: 256
//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
#define bged(v) (v).begin(),(v).end()
#define foreach(it,s) for(__typeof((s).begin()) it=(s).begin();it!=(s).end();it++)
typedef long long ll;
const int Imx=2147483647;
const ll Lbig=2e18;
const int mod=1e9+7;
//My i/o stream
struct fastio
{
	char s[100000];
	int it,len;
	fastio(){it=len=0;}
	inline char get()
	{
		if(it<len)return s[it++];it=0;
		len=fread(s,1,100000,stdin);
		if(len==0)return EOF;else return s[it++];
	}
	bool notend()
	{
		char c=get();
		while(c==' '||c=='\n')c=get();
		if(it>0)it--;
		return c!=EOF;
	}
}_buff;
#define geti(x) x=getnum()
#define getii(x,y) geti(x),geti(y)
#define getiii(x,y,z) getii(x,y),geti(z)
#define puti(x) putnum(x),putchar(' ')
#define putii(x,y) puti(x),puti(y)
#define putiii(x,y,z) putii(x,y),puti(z)
#define putsi(x) putnum(x),putchar('\n')
#define putsii(x,y) puti(x),putsi(y)
#define putsiii(x,y,z) putii(x,y),putsi(z)
inline ll getnum()
{
	ll r=0;bool ng=0;char c;c=_buff.get();
	while(c!='-'&&(c<'0'||c>'9'))c=_buff.get();
	if(c=='-')ng=1,c=_buff.get();
	while(c>='0'&&c<='9')r=r*10+c-'0',c=_buff.get();
	return ng?-r:r;
}
template<class T> inline void putnum(T x)
{
	if(x<0)putchar('-'),x=-x;
	register short a[20]={},sz=0;
	while(x)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1;i>=0;i--)putchar('0'+a[i]);
}
inline char getreal(){char c=_buff.get();while(c==' '||c=='\n')c=_buff.get();return c;}
int n,m;
int a[311][311];
int it[311],cnt[311];
pair<int,int> getmx()
{
	int mx=0,mxid=0;
	for(int i=1;i<=m;i++)
	{
		if(cnt[i]>mx)mx=cnt[i],mxid=i;
	}
	return MP(mx,mxid);
}
bool del[311];
int main()
{
	getii(n,m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			geti(a[i][j]);
		}
		it[i]=1;
		cnt[a[i][1]]++;
	}
	int ans=getmx().FF;
	while(true)
	{
		int x=getmx().SS;
		del[x]=1;
		for(int j=1;j<=n;j++)
		{
			while(it[j]<=m&&del[a[j][it[j]]])
			{
				cnt[a[j][it[j]]]--;
				it[j]++;
				cnt[a[j][it[j]]]++;
			}
			if(it[j]>m)
			{
				cout<<ans<<endl;
				return 0;
			}
		}
		ans=min(ans,getmx().FF);
	}
	return 0;
}


Measured memory_bytes: 768
A = []
for _ in range(3):
    A.append([int(i) for i in input().split(' ')])
N = int(input())
a = []
for _ in range(N):
    a.append(int(input()))

for num in a:
    for i in range(3):
        for j in range(3):
            if num == A[i][j]:
                A[i][j] = '*'

ans = 'No'
for i in range(3):
    flg = 0 
    b1 = all(A[i][j] == '*' for j in range(3))
    b2 = all(A[j][i] == '*' for j in range(3))
    b3 = all(A[j][j] == '*' for j in range(3))
    b4 = all(A[2-j][j] == '*' for j in range(3))
    if b1 or b2 or b3 or b4:
        ans = 'Yes'

print(ans)
        

Measured memory_bytes: 3064
#  --*-coding:utf-8-*--

import bisect

def f(n, aVals, bVals, cVals):
    #     return len(ys)*len(xs) - sum(bisect.bisect_left(ys, x) for x in xs

    bVals = sorted(bVals)
    cVals = sorted(cVals)

    xs = [0]*(n+1)
    x = 0
    for i in range(n-1, -1, -1):
        x += n - bisect.bisect_right(cVals, bVals[i])
        xs[i] = x

    return sum(xs[bisect.bisect_right(bVals, a)]
               for a in aVals)


def test():
    assert f(2, [1, 5], [2, 4], [3, 6]) == 3
    assert f(3, [1, 1, 1], [2, 2, 2], [3, 3, 3]) == 27
    assert f(6, [3, 14, 159, 2, 6, 53],
             [58, 9, 79, 323, 84, 6],
             [2643, 383, 2, 79, 50, 288]) == 87


def main():
    n = int(input())
    aVals = list(map(int, input().split()))
    bVals = list(map(int, input().split()))
    cVals = list(map(int, input().split()))

    print(f(n, aVals, bVals, cVals))


if __name__ == '__main__':
    main()


Measured memory_bytes: 24180
// 解き直し.
// https://img.atcoder.jp/data/arc/058/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL MOD = 1e9 + 7;
LL dp[41][1 << 16];
LL mPow10[41];

int main(){
    
    // 1. 入力情報.
    int N, X, Y, Z;
    scanf("%d %d %d %d", &N, &X, &Y, &Z);
    
    // 2. 10 の 冪乗 を 保存.
    mPow10[0] = 1;
    rep(i, 40) mPow10[i + 1] = mPow10[i] * 10, mPow10[i + 1] %= MOD;
    
    // 3. XYZ を 含まない文字列の数をカウント(解説通り).
    int mask  = (1 << (X + Y + Z - 1)) - 1;
    int xMask = 1 << (X + Y + Z - 1);
    int yMask = 1 << (Y + Z - 1);
    int zMask = 1 << (Z - 1);
    dp[0][0] = 1;
    repx(i, 1, N + 1){
        // 前回以前の情報に, 今回出現情報(1 ～ 10) を 結合.
        rep(n, 10){
            int cur = 1 << n; // 現在見ている数列の値.
            rep(bef, 1 << 16){
                // 3-1. 評価対象.
                int eva = (bef << (n + 1)) + cur;
                
                // 3-2. 今回以前が, XYZ と 等しい場合は, Skip.
                if((eva & xMask) && (eva & yMask) && (eva & zMask)) continue;
                
                // 3-3. 今回以前が, XYZ と 等しくない場合は, 更新.
                int j = mask & eva;
                dp[i][j] += dp[i - 1][bef];
                dp[i][j] %= MOD;
            }
        }
    }
    
    // 4. 出力.
    LL ans = 0;
    rep(j, 1 << 16) ans += dp[N][j], ans %= MOD; 
    ans = (MOD + mPow10[N] - ans) % MOD;
    printf("%lld\n", ans);
    return 0;
    
}

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

int solve(string s){
    int res=0;
    for(int i = 0;i < s.size();i ++){
        if(i%2){
            if(s[i]=='g') res ++;
        }else{
            if(s[i]=='p') res --;
        }
    }
    return res;
}

int main(){
    string s;
    cin >> s;
    cout << solve(s) << endl;    
    return 0;
}

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

signed main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  int ans = max({a*c,a*d, b*c, b*d});
  cout << ans << '\n';
}

Measured memory_bytes: 3632
/*
    ||S|A|M|R|A|T||
    Author:codingsamrat
*/
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define int long long 
#define ld long double
#define INF LONG_MAX
#define pb push_back
#define gcd __gcd
#define f(i,a,b) for(int i=a;i<b;i++)
#define fe(i,a,b) for(int i=a;i<=b;i++)
#define vii vector<int>
#define vll vector<long long>
typedef long long  ll;

ll modl= 998244353;

ll bpow(ll a, ll b) {
	a=a%modl;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a%modl;
        a = a * a%modl;
        b >>= 1;
    }
    return res;
}

int32_t main()
{	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
//	#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    #endif
	ll fact[200005];
	fact[0]=1;
	fact[1]=1;
	for(ll i=2;i<200005;i++)
	{
		fact[i]=(fact[i-1]%modl*i%modl)%modl;
	}

	ll test;
	test=1;
	while(test--)
	{
	ll n,m,k;
	cin>>n>>m>>k;
	ll ans=1;
	ll sum=0;
	fe(i,0,k)
	{
	ans=1;
	ans*=(m%modl)%modl;	
	ans=(ans%modl * bpow(m-1,n-1-i)%modl)%modl;
	ans=(ans%modl * fact[n-1]%modl)%modl;
	ll z=bpow(((fact[i]%modl * fact[n-1-i]%modl)%modl),modl-2);
	ans=(ans%modl * z%modl)%modl;
	sum+=ans;
	sum=sum%modl;
	}
	
	cout<<sum%modl;
	}
     
return 0;

}


Measured memory_bytes: 5136
package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)

	n := len(s)
	for i := 0; i < n/2; i++ {
		if s[i] != s[n-i-1] ||
			s[i] != s[(n-1)/2-1-i] ||
			s[n-i-1] != s[(n+3)/2-1+i] {
			fmt.Println("No")
			return
		}
	}

	fmt.Println("Yes")
}


Measured memory_bytes: 512
A, B = map(int, input().split())
k = 1

while True:
    if B == 0:
        break
    if 2**(k-1) <= B < 2**k:
        break
    k += 1


def sum_xor(n):
    res = []
    for i in range(k):
        if i == 0:
            res.append(1) if n % 4 == 1 or n % 4 == 2 else res.append(0)
        else:
            nmod = n % (2 ** (i + 1))
            if (2**(i+1))/2 <= nmod < 2**(i+1) and nmod % 2 == 0:
                res.append(1)
            else:
                res.append(0)
            # odd = [2**i+2*j for j in range(2**(i-1))]
            # tmp = n % 2**(i+1)
            # res.append(1) if tmp in odd else res.append(0)
    res.reverse()
    return res


ax = sum_xor(A-1)
bx = sum_xor(B)

ans = []
for j in range(k):
    ans.append(1) if (ax[j] + bx[j]) % 2 == 1 else ans.append(0)

ans = "".join(map(str, ans))
print(int(ans, 2))


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <iostream>
#include <functional>
#include <vector>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <math.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define rep1(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define per1(i,a,n) for (int i=a;i>n;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define endl "\n"
#define pi 3.14159265358979323846264338327950288419716939937510
#define IOS cin.sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll mod=1000000007;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
ll qpow(ll a,ll b){ll s=1;while(b>0){if(b%2==1){s=s*a;}a=a*a;b=b>>1;}return s;}
ll qpowmod(ll a, ll b, ll c){ll res, t;res=1;t=a%c;while(b){if(b & 1){res=res*t%c;}t=t*t%c;b>>=1;}return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline long long read(){long long k=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}return k*f;}
inline void write(long long x){if(x<0)x=-x,putchar('-');if(x>9)write(x/10);putchar(x%10+'0');}
// head
const int maxn=2e5+5;
ll n,m,a,b,p[maxn],v[maxn],ans,vis[maxn];
int fd(int x)
{
    if(p[x]!=x)
    {
        int y=p[x];
        p[x]=fd(p[x]);
        v[x]=v[x]+v[y];
    }
    return p[x];
}
signed main()
{
    //IOS;
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        p[i]=i;
        v[i]=1;
    }
    for(int i=1; i<=m; i++)
    {
        cin>>a>>b;
        int x=fd(a);
        int y=fd(b);
        //cout<<x<<' '<<y<<endl;
        if(x!=y)
        {
            p[x]=y;
            v[y]+=v[x];
            //cout<<v[y]<<endl;
        }
    }
    for(int i=1; i<=n; i++)
    {
        int x=fd(i);
        if(vis[x]==0)
        {
            vis[x]=1;
            ans=max(ans,v[x]);
            //cout<<v[x]<<endl;
        }
    }
    cout<<ans<<endl;
    return 0;
}
/*

*/


Measured memory_bytes: 12820
#define max(a,b) ((a)>(b)?(a):(b))
short lcs[4002][4002];

int main(){
  char a[4002],b[4002];
  int i,j,_a,_b,m;
  while(~scanf("%s%s",a+1,b+1)){
    memset(lcs,0,sizeof(lcs));
    _a=strlen(a+1);_b=strlen(b+1);
    for(m=0,i=1;i<=_a;i++)
      for(j=1;j<=_b;j++){
        lcs[i][j]=a[i]==b[j]?lcs[i-1][j-1]+1:0;
        if(m<lcs[i][j])m=lcs[i][j];
      }
    printf("%d\n",m);
  }
  return 0;
}

Measured memory_bytes: 31844
a,b=gets.chomp.split(" ").map(&:to_i)

c = 0

(a..b).each do |i|
  if (i / 10000 == i % 10) && ((i % 10000) / 1000 == (i % 100) / 10)
    c += 1
  end
end

print(c)


Measured memory_bytes: 14148
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
long long  n,w;
pair<long long ,long long > a[100001];
long long  dp[101][100001];

long long  recur(long long  i, long long  rest){
    if(i == n) return 0;
    if(dp[i][rest] != -1) return dp[i][rest];
    else {
        if(rest - a[i].ff < 0) return dp[i][rest] = max(dp[i][rest],recur(i+1,rest));
        else{
            return dp[i][rest] = max(recur(i+1,rest - a[i].ff) + a[i].ss,recur(i+1,rest));
        }
    }
}


int main(){
    cin>>n>>w;
    for(long long  i = 0;  i < n; i++) cin>>a[i].ff>>a[i].ss;
    memset(dp,-1,sizeof dp);
    cout<<recur(0,w);
}


Measured memory_bytes: 80128
#include <iostream>
using namespace std;
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, ans = 0; cin>>n;
	for(int i=1;i<=n;i++){
		int c; cin>>c;
		if((i & 1) && (c & 1)) ans++;
	}
	cout<<ans;
}

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

bool kaibun(string s) {
  string r(s.rbegin(), s.rend());
  return s == r;
}

signed main() {
  string S;
  cin >> S;
  int N = S.size();

  if(!kaibun(S)) {
    puts("No");
    return 0;
  }

  if(!kaibun(S.substr(0, (N-1)/2))) {
    puts("No");
    return 0;
  }

  if(!kaibun(S.substr((N+3)/2-1))) {
    puts("No");
    return 0;
  }
  puts("Yes");
}


Measured memory_bytes: 256
#include<iostream>


using namespace std;

int main()

{

    string s;

    cin>>s;

    if(s=="++++")

    {

        cout<<4;

    }
    else if(s=="----")

    {

        cout<<-4;

    }


    else if(s=="+-++" || s=="++-+" || s=="+++-" || s=="-+++")

    {

        cout<<2;

    }

    else if(s=="++--" || s=="+-+-" || s=="-+-+" || s=="--++" || s=="+--+" || s=="-++-")

    {

        cout<<0;

    }

    else if(s=="+---" || s=="-+--" || s=="--+-" || s=="---+")

    {

        cout<<-2;

    }


    return 0;

}






Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h> // int64_t
#include <math.h>

#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) > (b) ? (b) : (a))

int get_int(void) {
  int num;
  scanf("%d", &num);
  return num;
}

int get_int2(int *a1, int *a2) {
  scanf("%d %d", a1, a2);
  return 0;
}

int get_int3(int *a1, int *a2, int *a3) {
  scanf("%d %d %d", a1, a2, a3);
  return 0;
}

int get_int4(int *a1, int *a2, int *a3, int *a4) {
  scanf("%d %d %d %d", a1, a2, a3, a4);
  return 0;
}

int get_int5(int *a1, int *a2, int *a3, int *a4, int *a5) {
  scanf("%d %d %d %d %d", a1, a2, a3, a4, a5);
  return 0;
}

// <arr[0]> <arr[1]> .. <arr[size-1]>
int fget_array(int *arr, int size) {
    int i;
    for(i = 0; i < size; i++) {
        scanf("%d", &arr[i]);
    }
    return 0;
}
#define NUM_MAX 2000

int main() {
    int num, Z, W;
    scanf("%d %d %d", &num, &Z, &W);
    int arr[NUM_MAX];
    fget_array(arr, num);

    static int dp[NUM_MAX][2];
    int last = arr[num-1];
    for (int i = num-1; i >= 0; i--) {
        int Y = (i ? arr[i-1] : W);
        dp[i][0] = abs(Y - last);
        for (int j = i+1; j < num; ++j) {
            dp[i][0] = max(dp[i][0], dp[j][1]);
        }

        int X = (i ? arr[i-1] : Z);
        dp[i][1] = abs(X - last);
        for (int j = i+1; j < num; ++j) {
            dp[i][1] = min(dp[i][1], dp[j][0]);
        }
    }
    printf("%d\n", dp[0][0]);
}

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

using namespace std;

typedef long long ll;

int n, k;
int a[1111];
vector<ll> v;

int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) {
		ll s = 0;
		for (int j = i; j < n; j++) {
			s += a[j];
			v.push_back(s);
		}
	}
	for (int b = 40; b >= 0; b--) {
		vector<ll> u;
		int c = 0;
		for (auto x : v) {
			if (x&(1LL<<b)) {
				c++;
				u.push_back(x);
			}
		}
		if (c >= k) v = u;
	}
	ll r = v[0];
	for (auto x : v) r &= x;
	cout << r << "\n";
}

Measured memory_bytes: 6256