akhauriyash/Code-Regression huggingface dataset:
/*#pragma GCC optimize("O3")*/
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp> 
//#define ordered_set tree<int, null_type,less<int >, rb_tree_tag,tree_order_statistics_node_update> 
#define eps 1e-9
#define MOD1 998244353
#define MOD2 1000000007
#define INV_10 299473306
#define INF 1000000001
#define PI 3.14159265358979323846
using namespace std;
double dp[3005][3005];
double a[3005];
int n;
double solve(int idx, int rem)
{
	//cout << idx << ' ' << rem << '\n';
	if(idx==n)
	{
		if(rem==0)
			return 1.0000;
		else
			return 0.0;
	}
	if(n-idx < rem)
		return 0.0;
	if((dp[idx][rem]) > -0.0000000001)
		return dp[idx][rem];
	dp[idx][rem]=0.0;
	dp[idx][rem]+=(solve(idx+1, rem)*(1.0-a[idx]));
	if(rem)
		dp[idx][rem]+=(solve(idx+1, rem-1)*a[idx]);
	//cout << idx << ' ' << rem << ' ' << dp[idx][rem] << '\n';
	return dp[idx][rem];
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	for(int i = 0; i < 3005; i++)
		for(int j = 0; j < 3005; j++)
			dp[i][j]=-1.0;
	double ans=0.0;
	for(int i = n/2+1; i <= n; i++)
		ans+=solve(0, i);
	cout << fixed << setprecision(10) <<  ans << '\n';
}
//size

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

int main()
{
  int w,n,k,sum=0;
  vector<int> a;
  cin >> n >> k;
  for(int i=0;i<n;i++)
  {  cin >> w;
     a.push_back(w);
      
  }
  sort(a.begin(),a.end());
  
  for(int j=0;j<k;j++)
  {
      sum=sum+a[j];
  }
 
 cout << sum;
 return 0;
}


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


Measured memory_bytes: 3084
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
#include <sstream>

using namespace std;

int main()
{
  int N;
  cin >> N;
  vector<long long> v(N);
  for (int i = 0; i < N; ++i) {
    cin >> v[i];
    v[i] -= i + 1;
  }
  sort(v.begin(), v.end());
  long long sum = 0;
  for (int i = 0; i < N; ++i) {
    sum += abs(v[i] - v[N / 2]);
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 1792
<?php

$words = explode(' ',trim(fgets(STDIN)));

for ($i=0; $i<3; $i++){
  $first[$i] = substr($words[$i],0,1);  
  $last[$i] = substr($words[$i],-1,1);
}

echo $last[0] == $first[1] && $last[1] == $first[2] ? 'YES': 'NO';
?>

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

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

    string s;
    cin >> s;

    int ptr = 0;
    string prev = s.substr(ptr, 1);
    int prelen = 1;
    ++ptr;
    int res = 1;
    while(ptr < s.size()-1){
        if(prev == s.substr(ptr, 1)){
            ++res;
            prev = s.substr(ptr, 2);
            ptr += 2;
            prelen = 2;
        }
        else{
            ++res;
            prev = s.substr(ptr, 1);
            ++ptr;
            prelen = 1;
        }
    }

    if(prelen == 1){
        if(s.substr(ptr, 1) != "" && prev != s.substr(ptr, 1)) ++res;
    }

    if(prelen == 2){
        if(s.substr(ptr, 2) != "" && prev != s.substr(ptr, 2)) ++res;
    }
  	

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 720
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define ff first
#define ar array
#define ss second
#define ll long long int
#define mem(x) memset(x,0,sizeof(x))
#define setbits(x)  __builtin_popcount(x)
#define ull unsigned long long int
#define all(c) (c).begin(),(c).end()
#define debug(x) cout<<#x<<" :: "<<x<<endl;
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define db double
#define endl "\n"
#define  fbo(x) find_by_order(x)
#define  ook(x) order_of_key(x)
 
using namespace __gnu_pbds;
using namespace std;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair<ll,ll > iil;
typedef pair<ll,int> li;
typedef pair<int,int> ii;
typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update>
    os1;
typedef tree<int, null_type, greater<int>, rb_tree_tag,
            tree_order_statistics_node_update>
    os2;

inline void fast()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}
const ll pi=31;
const ll MOD[2] = {1187278649, 1149736019};//for double hashing
const ll mod=(ll)(1e9)+7;
ll pmod(ll x,ll n){
  ll r=1;
  while(n>0)
  {
    if(n&1LL)
      r=(r*x)%mod;
    x=(x*x)%mod;
    n=n/2;
    n%=mod;
  }
  return r;
}
ll pMod(ll x,ll n,ll mod)
{ ll r=1;
  while(n>0)
  {
    if(n&1LL)
      r=(r*x)%mod;
    x=(x*x)%mod;
    n=n/2;
    n%=mod;
  }
  return r;
 
}
 
//think recursively also;
string s,t;
int LCS[3005][3005];
int n,m;
int sol(int i,int j)
{  
   if(i==n && j==m)
    return 0;
  if(i>n)
    return -3005;
  if(j>m)
    return -3005;
  if(LCS[i][j]!=-1)
    return LCS[i][j];
   int ans=0;
   if(i<n && j<m && s[i]==t[j])
    ans=sol(i+1,j+1)+1;
   if(i<n)
    ans=max(ans,sol(i+1,j));
   if(j<m)
    ans=max(ans,sol(i,j+1));
  LCS[i][j]=ans;
  return ans;
}
void solve()
{ 
  cin>>s>>t;
  n=s.size();
  m=t.size();
  memset(LCS,-1,sizeof(LCS));
  int mx=sol(0,0);
  int i=0,j=0;
  string ans="";
  while(i<n && j<m)
  {  
     if(s[i]==t[j])
     {
      ans+=s[i];
      i++;
      j++;
      continue;
     }
     if(LCS[i][j+1]>=LCS[i+1][j])
     {
      j++;
     }
     else if((LCS[i][j+1]<=LCS[i+1][j]))
     {
       i++;
     }
  }
  //if(ans.size())
 // reverse(all(ans));
  cout<<ans<<endl;
}
int main()
{
  fast();
   // int t;
   // cin>>t;
   // for(int casee=1;casee<=t;casee++)
  {//cout<<"Case #"<<casee<<": ";
    solve();
  }
 
 
 
}

Measured memory_bytes: 39240
input_tuple = tuple(map(int,list(input())))

n = 3
c_list = [list(map(int,format(i,"b").zfill(n))) for i in range(2**n)]

for i in c_list:
    input_list = list(input_tuple)
    for j, v in enumerate(i):
        if v == 1:
            input_list[j+1] = input_list[j+1] * -1
    if sum(input_list) == 7:
        break
ans = [str(input_list[0])]
for j in range(3):
    if i[j] == 0:
        ans.append("+")
    ans.append(str(input_list[j+1]))
else:
    ans.append("=7")

print("".join(ans))

Measured memory_bytes: 3316
import itertools
import numpy as np
import copy

N,W,K = map(int,input().split())
g_all = np.array([list(input()) for i in range(N)])

K_all = np.count_nonzero(g_all == '#')
count = 0

def dfs(i,g):
  if (i<N):
    g[i,:] = ['r']*W
  else:
    g[:,i-N] = ['r']*N
  return g

g = g_all

for l in range(N+W+1):
  combi = itertools.combinations([i for i in range(N+W)],l)
  for com in combi:
    g = g_all.copy()
    for i in com:
      if (i<N):
        g[i,:] = ['r']*W
      else:
        g[:,i-N] = ['r']*N
    if np.count_nonzero(g == '#') ==K:
      count+=1
print(count)


Measured memory_bytes: 27048
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using static System.Console;
using static System.Math;
class Z { static void Main() => new K(); }
class K
{
	int F => int.Parse(Str);
	long FL => long.Parse(Str);
	int[] G => Strs.Select(int.Parse).ToArray();
	long[] GL => Strs.Select(long.Parse).ToArray();
	string Str => ReadLine();
	string[] Strs => Str.Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
	const int MOD = 1000000007;
	public K()
	{
		SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		Solve();
		Out.Flush();
	}
	void Solve()
	{
		var N = F;
		for (var i = 0; 4 * i <= N; i++) if ((N - 4 * i) % 7 == 0) { WriteLine("Yes"); return; }
		WriteLine("No");
	}
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()

template< int mod >
struct ModInt {
  int x;

  ModInt() : x(0) {}

  ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

  ModInt &operator+=(const ModInt &p) {
    if((x += p.x) >= mod) x -= mod;
    return *this;
  }

  ModInt &operator-=(const ModInt &p) {
    if((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }

  ModInt &operator*=(const ModInt &p) {
    x = (int) (1LL * x * p.x % mod);
    return *this;
  }

  ModInt &operator/=(const ModInt &p) {
    *this *= p.inverse();
    return *this;
  }

  ModInt operator-() const { return ModInt(-x); }

  ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }

  ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }

  ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }

  ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }

  bool operator==(const ModInt &p) const { return x == p.x; }

  bool operator!=(const ModInt &p) const { return x != p.x; }

  ModInt inverse() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while(b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }

  ModInt pow(int64_t n) const {
    ModInt ret(1), mul(x);
    while(n > 0) {
      if(n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }

  friend ostream &operator<<(ostream &os, const ModInt &p) {
    return os << p.x;
  }

  friend istream &operator>>(istream &is, ModInt &a) {
    int64_t t;
    is >> t;
    a = ModInt< mod >(t);
    return (is);
  }

  static int get_mod() { return mod; }
};

const int mod = 1e9 + 7;

using modint = ModInt< mod >;



int main() {
    int a, b, c, d, k;
    cin >> a >> b >> c >> d >> k;
    int x = 60 * a + b;
    int y = 60 * c + d;
    cout << y - x - k << endl;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define PI 3.14159265359
#define INF 1000100100//000000000
#define MOD 1000000007
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define P pair<int, int>
#define PP pair<P,P>
#define T tuple<int,int,int> 
using namespace std;

int main(){
    int n,m; cin >> n >> m;
    vector<vector<int> > lag(m);
    vector<vector<int> > abts(n);
    rep(i,n){
        int k; cin >> k;
        rep(j,k){
            int l; cin>> l;
            l--;
            lag[l].push_back(i);
            abts[i].push_back(l);
        }
    }

    vector<int> check(n,0);
    vector<int> lcheck(m,0);
    queue<int> q;
    q.push(0);
    check[0]++;

    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int x : abts[now]){
            if(lcheck[x]) continue;
            lcheck[x]++;
            for(int y : lag[x]){
                if(!check[y]){
                    q.push(y);
                    check[y]++;
                }
            }
        }
    }

    rep(i,n){
        if(!check[i]){
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

Measured memory_bytes: 12508
#include <iostream>
#include <cstdio>
#define N 1005
#define M 2005
using namespace std;

typedef long long ll;
ll n, m, a[M], b[M], c[M], d[N];
bool v = 1;
int main()
{
	ll i, j, t;
	cin >> n >> m;
	for (i = 0; i < m; i++) scanf("%lld %lld %lld", &a[i], &b[i], &c[i]);
	for (i = 2; i <= n; i++) d[i] = -1e18;
	for (i = 0; i < n - 1 && v; i++) {
		v = 0;
		for (j = 0; j < m; j++) {
			if (d[b[j]] < d[a[j]] + c[j]) v = 1, d[b[j]] = d[a[j]] + c[j];
		}
	}
	if (v) {
		t = d[n];
		for (i = 0; i < m; i++) {
			if (d[b[i]] < d[a[i]] + c[i]) d[b[i]] = d[a[i]] + c[i];
		}
		if (t != d[n]) {cout << "inf"; return 0;}
	}
    cout << d[n];
    return 0;
}

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(){

  int n,k,t,u,v,l;
  cin >> n >> k >> t >> u >> v >> l;
  vector<int> d(n+1);
  rep(i,n)cin>>d[i];
  d[n] = l;

  int h = 0;
  double time = 0.0;
  int pos = 0;
  int dind = -1;
  while (pos<l){
    if (h==0){
      dind++;
      time += (double)(d[dind]-pos)/u;
      pos = d[dind];
      // cout << dind << " " << pos << " " << time << endl;
      h = 1;
    } else {
      h--;
      auto itr=upper_bound(d.begin(),d.end(),pos+v*t)-1;
      int c = distance(d.begin(),itr)-dind;
      // cout << c << endl;
      if(h+c<=k){
        if (pos+v*t<l){
          pos += v*t;
          time += t;
          dind += c;
          h += c;
          // cout << dind << " " << pos << " " << time << " " << h << endl;
        } else {
          time += (double)(l-pos)/v;
          pos = l;
        }
      } else {
        h = k;
        dind += c;
        int pos_d = d[dind]+v*t;
        if(pos_d>l){
          time += (double)(l-pos)/v;
          pos = l;
        } else {
          time += (double)(pos_d-pos)/v;
          // cout << dind << " " << pos << " " << time << " " << h << endl;
          pos = pos_d;
        }
      }
    }
  }
  cout << setprecision(10) << time << endl;

  return 0;
}



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

using ll = long long;

int main() {
    int N;
    string S;
    cin >> N >> S;
    if (N % 2 == 1) {
        cout << "No" << endl;
        return 0;
    }
    rep(i, N / 2) {
        if (S[i] != S[i + N / 2]) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 256
from itertools import permutations
n = int(input())
p = list(map(int,input().split()))
q = list(map(int,input().split()))

a,b = -1,-1
for i,x in enumerate(permutations([i+1 for i in range(n)])):
    c,d = True,True
    for j in range(n):
        if x[j] != p[j]:
            c = False
        if x[j] != q[j]:
            d = False
    if c:a = i+1
    if d:b = i+1
print(abs(a-b))

Measured memory_bytes: 3064
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N,M=mis()
    W = [None] + [set() for _ in range(N)]
    for _ in range(M):
        a, b = mis()
        W[a].add(b)
        W[b].add(a)
    ans = [None]*(N+1)
    ans[1] = True
    q = deque()
    q.append(1)
    while q:
        p = q.popleft()
        for np in W[p]:
            if ans[np] is None:
                ans[np] = p
                q.append(np)
    print('Yes')
    print(*ans[2:], sep='\n')


main()



Measured memory_bytes: 65692
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

const int MaxN = 3e5;
struct SEG {
	int l, r, len;
}a[MaxN + 5];
int n, m, c[MaxN + 5];

bool cmp(SEG A, SEG B) {return A.len < B.len;}

void Init()
{
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &a[i].l, &a[i].r);
		a[i].len = a[i].r - a[i].l + 1;
	}
	sort(a + 1, a + n + 1, cmp);
	memset(c, 0, sizeof(c));
}

int Lowbit(int x) {return (x & (-x)); }
void Add(int x, int t)
{
	int p = x;
	while (p <= m) {
		c[p] += t;
		p += Lowbit(p);
	}
}

int Sigma(int x)
{
	int p = x, ans = 0;
	while (p > 0) {
		ans += c[p];
		p -= Lowbit(p);
	}
	return ans;
}

void Solve()
{
	int p = 0;
	for (int i = 1; i <= m; i++) {
		int cnt = n - p;
		for (int j = 0; i * j <= m; j++)
			cnt += Sigma(i * j);		
		while (p < n && a[p + 1].len <= i) {
			p++; Add(a[p].l, 1); Add(a[p].r + 1, -1);
		}
		printf("%d\n", cnt);
	}
}


int main()
{
	while (~scanf("%d%d", &n, &m)) {
		Init();
		Solve();
	}
	return 0;
}

Measured memory_bytes: 5632
#include "iostream"
#include "algorithm"
#include "string"
using namespace std;

int main() {
	int n, f[50];
	cin >> n;
	for (int i = 0; i <= n; i++) {
		if (i == 0 || i == 1) {
			f[i] = 1;
		}
		else {
			f[i] = f[i - 1] + f[i - 2];
		}
	}
	cout << f[n] << endl;
}


Measured memory_bytes: 3112
#define _USE_MATH_DEFINES
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <clocale>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i, s, n) for(int i = (s), i##_len=(n); i < i##_len; ++i)
#define FORS(i, s, n) for(int i = (s), i##_len=(n); i <= i##_len; ++i)
#define VFOR(i, s, n) for(int i = (s); i < (n); ++i)
#define VFORS(i, s, n) for(int i = (s); i <= (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) FORS(i, 0, n)
#define VREP(i, n) VFOR(i, 0, n)
#define VREPS(i, n) VFORS(i, 0, n)
#define RFOR(i, s, n) for(int i = (s), i##_len=(n); i >= i##_len; --i)
#define RFORS(i, s, n) for(int i = (s), i##_len=(n); i > i##_len; --i)
#define RREP(i, n) RFOR(i, n, 0)
#define RREPS(i, n) RFORS(i, n, 0)
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v), greater<decltype(v[0])>())
#define SZ(x) ((int)(x).size())
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())

using ld = long double;
using ll = long long;
using ui = unsigned int;
using ull = unsigned long long;
using Pi_i = pair<int, int>;
using Pll_ll = pair<ll, ll>;
using VB = vector<bool>;
using VC = vector<char>;
using VD = vector<double>;
using VI = vector<int>;
using VLL = vector<ll>;
using VS = vector<string>;
using VSH = vector<short>;
using VULL = vector<ull>;

const int MOD = 1000000007;
const int INF = 1000000000;
const int NIL = -1;
const double EPS = 1E-10;

template<class T, class S>
bool chmax(T &a, const S &b){
    if(a < b){
        a = b; return true;
    }
    return false;
}
template<class T, class S>
bool chmin(T &a, const S &b){
    if(b < a){
        a = b; return true;
    }
    return false;
}


int main(){
    unordered_set<int> uset;
    int N; cin >> N;
    bool match = false;
    REP(i, N){
        int A; cin >> A;
        if(uset.find(A) != uset.end()) match = true;
        uset.emplace(A);
    }
    cout << (match ? "NO" : "YES") << endl;
    return 0;
}


Measured memory_bytes: 8520
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>

#define N 1000000

using namespace std;

int main(int argc, const char * argv[]) {
    // insert code here...
    
    
    /////////
    //write//
    /////////
    
    while(1){
        int a, d, n; cin >> a >> d >> n;
        if(a==0 && d== 0 && n==0)break;
        int arr[N];
        for(int i=0; i<N; i++){
            arr[i] = i;
        }
        for(int i=2; i<sqrt(N); i++){
            if(arr[i]){
                for(int j=0; i*(j+2)<N; j++){
                    arr[i*(j+2)]=0;
                }
            }
        }
        int cnt = 1;
        for(int i=2; i<N; i++){
            if(arr[i]){
                if((arr[i]-a)%d==0 && (arr[i]-a)/d>=0){
                    if(cnt == n)cout << arr[i] << endl;
                    cnt++;
                }
            }
        }
    }
    
    return 0;
}




Measured memory_bytes: 7004
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
int main(void){
	int n,m,c,i,j;
	cin>>n>>m>>c;
	int b[m],a[n][m];
	for(i=0;i<m;i++)cin>>b[i];
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			cin>>a[i][j];
		}
	}
	int sum,ans=0;
	for(i=0;i<n;i++){
		sum=0;
		for(j=0;j<m;j++){
			sum+=a[i][j]*b[j];
		}
		if(sum+c>0)ans++;
	}
	cout<<ans<<endl;
}


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


const int maxn=1e6+7;
int a[maxn],x,y,z;

int main (){
    int n;cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1;i<=1000000;i++){
        int x=upper_bound(a+1,a+1+n,i)-a;
        int y=upper_bound(a+1,a+1+n,i)-a;
        x=(y-(y-x)-1);
        //f(i==5) cout<<x<<endl;
        if(2*x==n) ans++;
    }
    cout<<ans<<endl;
    return 0;
}



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

int main(){
    int n,a,b;
    scanf("%d %d %d",&n,&a,&b);
    int i,x,ans=0;
    for(i=0;i<n;i++){
        scanf("%d",&x);
        if(x<a || x>=b) ans ++;
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 256
def c_digit(n)
  return n.to_s.size
end

def main
  n = gets.to_i
  ret = 2**64-1
  i = 1
  while i * i <= n
    ret = [ret, [c_digit(i), c_digit(n/i)].max].min if n%i == 0
    i += 1
  end
  puts ret
end

main


Measured memory_bytes: 1788
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_A main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LLONG_MAX/2)
const int MGN = 10;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using psi = pair<string, int>;
// functions

#endif


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

    int M, D; cin >> M >> D;

    int ans = 0;
    FOR(m,1,M+1) {
        FOR(d,1,D+1) {
            if (d < 10) continue;

            int d10 = d / 10;
            int d1 = d % 10;
            
            if (d10 == 1 || d1 == 1) continue;

            if (d10*d1 == m) ans++;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
  int a,b,c;
  cin >> a >> b >> c;
  vector<int> vec;
  vec.push_back(a);
  vec.push_back(b);
  vec.push_back(c);
  sort(vec.begin(),vec.end());
  if(vec[2] == vec[1] + vec[0]){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
int n;

struct Point{
	double x;
	double y;
};

void calc(int m,Point p1,Point p2){
	if(m>=n){
		return;
	}
	Point s,t,u;
	s.x=(2.0*p1.x+p2.x)/3.0;
	s.y=(2.0*p1.y+p2.y)/3.0;
	t.x=(p1.x+2.0*p2.x)/3.0;
	t.y=(p1.y+2.0*p2.y)/3.0;
	u.x=(t.x-s.x)*(1.0/2.0)-(t.y-s.y)*(sqrt(3.0)/2.0)+s.x;
	u.y=(t.x-s.x)*(sqrt(3.0)/2.0)+(t.y-s.y)*(1.0/2.0)+s.y;
	calc(m+1,p1,s);
	printf("%.8f %.8f\n",s.x,s.y);
	calc(m+1,s,u);
	printf("%.8f %.8f\n",u.x,u.y);
	calc(m+1,u,t);
	printf("%.8f %.8f\n",t.x,t.y);
	calc(m+1,t,p2);
}

int main(){
	std::cin>>n;
	Point p1,p2;
	p1.x=0; p1.y=0; p2.x=100; p2.y=0;
	printf("%.8f %.8f\n",p1.x,p1.y);
	calc(0,p1,p2);
	printf("%.8f %.8f\n",p2.x,p2.y);
	
	return 0;
}
	



Measured memory_bytes: 3224
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define P pair<ll, ll>
#define Graph vector<vector<ll>>
#define fi first
#define se second
constexpr ll mod = 1000000007;
constexpr ll INF = (1ll << 60);
constexpr double pi = 3.14159265358979323846;
template <typename T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}

int main() {
    ll a, b, k;
    cin >> a >> b >> k;
    while (k) {
        if (a % 2 == 1) {
            a--;
        }
        b += (a / 2);
        a /= 2;

        k--;
        if (k == 0) break;

        if (b % 2 == 1) {
            b--;
        }
        a += (b / 2);
        b /= 2;

        k--;
    }

    cout << a << " " << b << "\n";
    return 0;
}

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

class Solution
{
    static int n;
    static int z;
    static int w;
    static int[] a;

    static int[][] cache = new int[2][];
    static int GetBest(int index, int player)
    {
        var key = Tuple.Create(index, player);
        if (cache[player][index + 1] >= 0)
        {
            return cache[player][index + 1];
        }

        var best = 0;
        if (player == 1)
        {
            best = int.MaxValue;
        }
        for (int i = index + 1; i < n; i++)
        {
            int diff;
            if (i != n - 1)
            {
                diff = GetBest(i, player ^ 1);
            }
            else
            {
                int enemyNum;
                if (index >= 0)
                {
                    enemyNum = a[index];
                }
                else
                {
                    enemyNum = (player == 1) ? z : w;
                }

                diff = Math.Abs(enemyNum - a.Last());
            }

            if (player == 0)
            {
                best = Math.Max(best, diff);
            }
            else
            {
                best = Math.Min(best, diff);
            }
        }

        cache[player][index + 1] = best;
        return best;
    }

    static void Main()
    {
        var vals = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        n = vals[0];
        z = vals[1];
        w = vals[2];
        a = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

        for (int i = 0; i < 2; i++)
        {
            cache[i] = Enumerable.Repeat(-1, n + 1).ToArray();
        }
        var result = GetBest(-1, 0);

        Console.WriteLine(result);
    }
}

Measured memory_bytes: 20160
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int K = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		
		int[] A = new int[N];
		int ans = K;
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++)
			A[i] = Integer.parseInt(st.nextToken());
		
		ans = A[N-1] - A[0];
		
		for(int i=1; i<N; i++)
			ans = Math.min(ans, K - (A[i] - A[i-1]));
		
		System.out.println(ans);
	}

}

Measured memory_bytes: 55308
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define max(a, b)	(((a) > (b)) ? (a) : (b))		/* ２個の値の最大値 */
#define min(a, b)	(((a) < (b)) ? (a) : (b))		/* ２個の値の最小値 */
#define ENTER		printf("\n")					/* 改行プリント */
int DBG = 1;										/* デバッグプリント 提出時は0 */
/* main *************************************************************/
int main()
{
	int		a,b,c,i,j,k,n,m,x,y;
	char	str[256];
	double  ans;
	
	scanf("%d", &n);

	a = n / 2;
	b = n - a;
	
	ans = (double)b / n;
	
	printf("%f\n",ans);

	return 0;
}


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

int main()
{
int N = 0;
cin >> N;
int A[N];
bool result = false;
for (int i = 0; i < N; i++)
{
    cin >> A[i];
}
for (int i = 0; i < N;i++)
{
    if(A[i] % 2 == 0){
        if(A[i] % 3 != 0){
            if(A[i] % 5 != 0)
            {result = true;
            }
        }
    }
}
    if(result == false){
        cout << "APPROVED" << endl;
    }
    else{
        cout << "DENIED" << endl;
    }
}

Measured memory_bytes: 256
using System;

public class hello
{
    public static void Main()
    {
        var c = 0; var e = 0; var d = 0;
        while (true)
        {
            string[] s = Console.ReadLine().Trim().Split(' ');
            var tri = Array.ConvertAll(s, int.Parse);
            Array.Sort(tri);
            if (tri[2] - tri[0] - tri[1] >= 0) break;
            if (tri[2] * tri[2] > tri[0] * tri[0] + tri[1] * tri[1]) d++;
            else if (tri[2] * tri[2] == tri[0] * tri[0] + tri[1] * tri[1]) c++;
            else e++;
        }
        Console.WriteLine("{0} {1} {2} {3}", c + e + d, c, e, d);
    }
}

Measured memory_bytes: 9224
import math
K = int(input())
ans = 0

for a in range(1, K+1):
    for b in range(a, K+1):
        for c in range(b, K+1):
            s = math.gcd(a, b)
            t = math.gcd(s, c)
            if a == c:
                ans += t
            elif (a == b or b == c) and a != c:
                ans += 3*t
            else:
                ans += 6*t
print(ans)

Measured memory_bytes: 9192
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

/*BigInteger
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/rational.hpp>
namespace xxx = boost::multiprecision;
using Bint = xxx::cpp_int;
using Real = xxx::number<xxx::cpp_dec_float<1024>>;
*/

#define int long long
#define pb(x) push_back(x)
#define m0(x) memset((x), 0LL, sizeof(x))
#define mm(x) memset((x), -1LL, sizeof(x))

//container
#define ALL(x) (x).begin(), (x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
#define PERM(c) \
  sort(ALL(c)); \
  for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))

// debug
#define GET_VAR_NAME(variable) #variable
#define test(x) cout << GET_VAR_NAME(x) << " = " << x << endl;

// bit_macro
#define Bit(n) (1LL << (n))
#define Bitset(a, b) (a) |= (1LL << (b))
#define Bitunset(a, b) (a) &= ~(1LL << (b))
#define Bitcheck(a, b) ((((a) >> (b)) & 1LL) == 1LL)
#define Bitcount(a) __builtin_popcountll((a))

//typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

//constant
constexpr int INF = (int)1e18;
constexpr int MOD = (int)1e9 + 7;
constexpr double PI = (double)acos(-1);
constexpr double EPS = (double)1e-10;
constexpr int dx[] = {-1, 0, 0, 1, 0, -1, -1, 1, 1};
constexpr int dy[] = {0, -1, 1, 0, 0, 1, -1, 1, -1};

//
template <typename T>
void chmax(T &a, T b) { a = max(a, b); }
template <typename T>
void chmin(T &a, T b) { a = min(a, b); }
//
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

//
struct Accelerate_Cin {
  Accelerate_Cin() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
  };
} Accelerate_Cin;

vector<int> diviser(int n) {
  vector<int> res;
  for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      res.push_back(i);
      if (i != n / i)
        res.push_back(n / i);
    }
  }
  return res;
}

signed main() {
  int N;
  cin >> N;

  vector<int> v = diviser(N);

  int ans = 0;
  for (auto x : v) {
    if (x == 1) continue;

    int m = x - 1;
    if (N / m == N % m) {
      ans += m;
    }
  }

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


Measured memory_bytes: 384
#include <iostream>
#include <cstring>
using namespace std;
#define INF (1<<25)
int dp[60][50][50][2] = {};
int g[50][50] = {};
int n,m;

int dfs(int mid,int a,int b,int t){
	if(t == 0 && a == b) return -INF;
	if(dp[mid][a][b][t] != -1) return dp[mid][a][b][t];
	if(mid == 0){
		//cout << a << " " << b << " " << t << endl;
		return 0;
	}
	if(t==0){
		int ans = -INF;
		for(int i = 0 ; i < n ; i++)
			if(g[a][i]) ans = max(ans,dfs(mid,i,b,t^1));
		return dp[mid][a][b][t] = ans;
	}else{
		int ans = INF;
		for(int i = 0 ; i < n ; i++)
			if(g[b][i]) ans = min(ans,dfs(mid-1,a,i,t^1)+1);
		return dp[mid][a][b][t] = ans;
	}
}
int main(){
	int T; cin >> T;
	while(T--){
		cin >> n;
		int a,b;
		for(int i = 0 ; i < n ; i++)
			for(int j = 0 ; j < n ; j++)
				cin >> g[i][j];
		for(int i = 0 ; i < n ; i++)
			g[i][i] = 1;
		cin >> a >> b;
		
		memset(dp,-1,sizeof(dp));
		int l = 0 , r = 52;
		while(l!=r){
			int mid = (l+r+1) / 2;
			if( dfs(mid,a,b,0) >= 0 ) l = mid;
			else r = mid-1;
		}
		if(l==52) cout << "infinity" << endl;
		else cout << l+1 << endl;
	}
}

Measured memory_bytes: 2048
#include<iostream>
using namespace std;
int main() {
	int A, B, ans = 0;
	cin >> A >> B;
	for (int i = A;i <= B;i++) {
		if (i / 10000 == i % 10) {
			if (i % 10000/1000 == i % 100/10) {
				ans++;
			}
		}
	}
	cout << ans << endl;
}

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

using static Input;
using static Util;
class Program
{
    static long N;
    static void INPUT()
    {
        N = NextLong();
    }

    static void OUT()
    {
        var a = long.MaxValue;
        for (var n = 1L; n <= Math.Pow(N, 0.5); n++)
            if (N % n == 0)
            {
                a = Math.Min(n + N / n - 2, a);
            }

        Console.WriteLine(a);
    }
    static void Main(string[] args)
    {
#if DEBUG  
        //TESTINPUT();
        INPUT();

#else
        INPUT();
#endif
        OUT();
    }

    static void TESTINPUT()
    {
    }

}

public class Input
{
    public const long MOD = 1000000007;
    public const int INF = 1000000007;
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}

class Util
{

}




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

bool used[100];
int main() {
	int a, b, c; cin >> a >> b >> c;
	for (int i = 1;; i++) {
		if (used[(a*i) % b])break;
		used[(a*i) % b] = 1;
	}
	puts(used[c] ? "YES" : "NO");
}

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

using namespace std;
typedef pair<int, int> P;

int n, k;
vector<int> G[2005];
int depth[2005];

void dfs(int v, int prev, int dep)
{
	depth[v] = dep;
	for(int i = 0; i < G[v].size(); i++){
		if(G[v][i] == prev) continue;
		dfs(G[v][i], v, dep+1);
	}
}

P cntdfs(int v, int prev, int dep)
{
	P ret = make_pair(0, 0);
	if(depth[v] <= dep) ret.first++;
	if(depth[v] == dep+1) ret.second++;
	for(int i = 0; i < G[v].size(); i++){
		if(G[v][i] == prev) continue;
		P res = cntdfs(G[v][i], v, dep);
		ret.first += res.first;
		ret.second += res.second;
	}
	return ret;
}

int main(void)
{
	cin >> n >> k;
	int a, b;
	for(int i = 0; i < n-1; i++){
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	
	int ans = 0;
	for(int i = 1; i <= n; i++){
		dfs(i, -1, 0);
		int cnt = 1, mx = 0;
		for(int j = 0; j < G[i].size(); j++){
			P res = cntdfs(G[i][j], i, k/2);
			cnt += res.first;
			mx = max(mx, res.second);
		}
		if(k % 2) cnt += mx;
		ans = max(ans, cnt);
	}
	
	cout << n - ans << endl;
	return 0;
}

Measured memory_bytes: 512
#include <stdio.h>
static int min(int a, int b)
{
	return a<b?a:b;
}
static int max(int a, int b)
{
	return a>b?a:b;
}
struct {
	int e;
	int (*f)(int,int);
	int xy;
} table[] = {
	{0, max, 0},
	{0, max, 0},
	{0, min, 0},
	{0, max, 0},
	{0, min, 0},
};
void solve(void)
{
	int w, h, n;
	scanf("%d %d %d", &w, &h, &n);
	table[1].e=0; table[2].e=w; table[3].e=0; table[4].e=h;
	while(n-->0){
		int xy[2],a;
		scanf("%d %d %d", xy, xy+1, &a);
		table[a].e = table[a].f(table[a].e, xy[a<3?0:1]);
	}
	if(table[2].e<table[1].e)
		table[2].e=table[1].e;
	if(table[4].e<table[3].e)
		table[4].e=table[3].e;
	printf("%d\n", (table[2].e-table[1].e)*(table[4].e-table[3].e));
}
int main(int argc, char **argv)
{
	solve();
	return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<cstdio>
using namespace std;
const int N=600005;
const int MOD=1000000007;
int n,m,L,R;
long long fac[N],inv[N];
long long ksm(long long a,long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1) res=res*a%MOD;
		a=a*a%MOD,b>>=1;
	}
	return res;
}
void init(int n=600000)
{
	fac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%MOD;
	inv[n]=ksm(fac[n],MOD-2);
	for(int i=n;i>=1;i--)
		inv[i-1]=inv[i]*i%MOD;
	return;
}
long long C(int n,int m)
{
	if(m>n) return 0;
	else return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
long long calc(long long x,int p,int q)
{
	x-=1LL*m*p;
	if(x<0) return 0;
	long long res=0;
	for(int i=0;i<=n-m&&x-1LL*i*q>=0;i++)
		if(i&1) res=(res-C(n-m,i)*C(x-1LL*i*q+n,n)%MOD+MOD)%MOD;
		else res=(res+C(n-m,i)*C(x-1LL*i*q+n,n)%MOD)%MOD;
	res*=C(n,m);
	return res;
}
long long solve(int x)
{
	long long res=0;
	for(int p=0;p<=x;p++)
		res=(res+(calc(x,p,p)-calc(x,p+1,p)+MOD)%MOD)%MOD;
	res=(C(x+n,n)-res+MOD)%MOD;
	return res;
}
int main()
{
	init();
	scanf("%d%d%d%d",&n,&m,&L,&R);
	printf("%lld",(solve(R)-solve(L-1)+MOD)%MOD);
	return 0;
}


Measured memory_bytes: 13196
#include <map>
#include <algorithm>
#include <cassert>
#include <climits>
#include <complex>
#include <cstdio>
#include <string>
#include <iostream>
#include <queue>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
using ll = long long;
using ld = long double;
template<class T> bool chmin(T &a, T b) { return a>b?(a=b,true):false; }
template<class T> bool chmax(T &a, T b) { return a<b?(a=b,true):false; }
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
#define bs2int(bs) (int)((bs).to_ulong())
#define FOR(i,x,y) for(int i=(x);i<(int)(y);i++)
#define FORP(i,x,y) for(int i=(x);i<=(int)(y);i++)
#define REP(i,y) for(int i=0;i<(int)(y);i++)
#define REPP(i,y) for(int i=1;i<=(int)(y);i++)
#define REPB(i,n) for(int i=(int)(n)-1;i>=0;i--)

string s,t;

int main() {
  cin>>s;
  int n=s.length();
  int cur=0;
  for (char c : s)
    if (c!='x') t+=c;

  string p(t);
  reverse(all(p));
  if (t!=p) return 0*puts("-1");

  int l=0,r=n-1;
  int cnt=0;
  while(l<r)
  {
    if (s[l]=='x'&&s[r]!='x')
    {
      cnt++;
      l++;
      continue;
    }
    if (s[l]!='x'&&s[r]=='x')
    {
      cnt++;
      r--;
      continue;
    }
    l++,r--;
  }
  cout << cnt << endl;
}


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

using ll = long long;
#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)

#define INF 1e9

int main(){
  int H, N;
  cin >> H >> N;
  vector<int> A(N);
  ll sum = 0;
  REP(i, N){
    cin >> A[i];
    sum += A[i];
  }
  if(sum >= H){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 int main() {
   int64_t a,b,c;
   cin>>a>>b>>c;
   if(c-a-b>0&&4LL*a*b<(c-a-b)*(c-a-b)){cout<<"Yes"<<endl;}
   else{cout<<"No"<<endl;}
              
 }

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

#ifdef LOCAL
#include "debug.h"
#else
#define DEBUG(...)
#endif

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  string s;
  cin >> s;
  int ta = 0, tb = 0;
  vector<int> id(2 * n);
  vector<int> posa(n), posb(n);
  for (int i = 0; i < 2 * n; ++i) {
    if (s[i] == 'a') {
      id[i] = ta++;
      posa[id[i]] = i;
    } else {
      id[i] = tb++;
      posb[id[i]] = i;
    }
  }
  vector<string> dp(2 * n + 1);
  for (int i = 2 * n; i--; ) {
    if (s[i] == 'a' and posb[id[i]] > i) {
      dp[i] = "ab" + dp[posb[id[i]] + 1];
    } else if (s[i] == 'b' and posa[id[i]] > i) {
      vector<int> v;
      int p = i;
      while (true) {
        int q = posa[id[p]];
        v.push_back(p);
        v.push_back(q);
        ++p;
        while (p < q and s[p] != 'b') {
          p++;
        }
        if (s[p] != 'b') break;
      }
      sort(begin(v), end(v));
      for (int e : v) {
        dp[i] += s[e];
      }
      dp[i] += dp[v.back() + 1];
    }
    dp[i] = max(dp[i], dp[i + 1]);
  }
  cout << dp[0] << '\n';
}


Measured memory_bytes: 15616
$cnt = 0

def selection_sort(arr, n)
  (0...n).each {|i|
    minj = i
    (i...n).each{|j|
      minj = j if arr[j] < arr[minj]
    }
    arr[i], arr[minj] = arr[minj], arr[i]
    $cnt += 1 if i != minj
  }
  arr
end

n = gets.to_i
arr = gets.split.map(&:to_i)
ans = selection_sort(arr, n)
puts ans.join(" ")
puts $cnt


Measured memory_bytes: 6872
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <iterator>
#include <stack>
#include <string.h>
#include <cstdlib>
#include <queue>
#include <list>

using namespace std;

int main()
{
    int n,x,y;
    long long dist;
    
    cin >> n >> x >> y;
    
    long long a[2000] = {0};
    
    for (int i = 1;i <= n-1;i++){
        for (int j = i+1;j <= n;j++){
            if (i <= x && j >= y){
                dist = x-i+j-y+1;
            }
            else if (i > x && j >= y){
                dist = min(j-i,i-x+1+j-y);
            }
            else if (i <= x && j < y){
                dist = min(j-i,y-j+x-i+1);
            }
            else {
                dist = min(j-i,i-x+y-j+1);
            }
            a[dist]++;
        }
    }
    for (int i = 1;i <= n-1;i++){
        cout << a[i] << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = a; i < n; i++)
#define Repr(i, n, a) for (int i = n; i >= a; i--)
#define rep(i, n) Rep(i, 0, n)
#define repr(i, n) Repr(i, n, 0)
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

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

    int n, m;
    cin >> n >> m;
    vector<int> x(m);
    rep(i, m) cin >> x[i];
    sort(all(x));
    vector<int> d(m - 1);
    rep(i, m - 1) d[i] = x[i + 1] - x[i];
    sort(all(d));
    int ans = 0;
    rep(i, m - n) ans += d[i];
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include<iostream>
#include<cstdio>
using namespace std;
int ans;
int main()
{
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    int n[10001];
    for(int i=1;i<=a;++i)
    {
        scanf("%d",&n[i]);
        if(n[i]<b || n[i]>=c)
        {
            ans++;
        }
    }
    cout<<ans;
    cout<<endl;
    return 0;
}

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

const int INF = 1 << 30;

int N;
int h[100010];

int dp[100010];

int solve(int i) {
    if(i == 0) return 0;
    if(dp[i] != INF) return dp[i];

    int res = INF;
    res = min(res, solve(i - 1) + abs(h[i] - h[i - 1]));
    if(i >= 2) res = min(res, solve(i - 2) + abs(h[i] - h[i - 2]));
    return dp[i] = res;
}

int main() {
    cin >> N;
    for(int i = 0; i < N; i++)
        cin >> h[i];

    for(int i = 0; i < 100010; i++)
        dp[i] = INF;

    cout << solve(N - 1) << endl;

    return 0;
}

Measured memory_bytes: 4096
#include<stdio.h>
int main(void)
{
	int n,p,d1,d2,max,s,i;
	while(1){
		scanf("%d",&n);
		if(n==0) break;
		max=0;
		for(i=0;i<n;i++){
			scanf("%d%d%d",&p,&d1,&d2);
			if(max<d1+d2){
				max=d1+d2;
				s=p;
			}
		}
		printf("%d %d\n",s,max);
	}
	return 0;
}

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

using namespace std;

int main() {
  int n; cin >> n;
  vector<int> x(n);
  int sum = 0;
  for (int i = 0; i < n; i++) {
    cin >> x[i];
    sum += x[i];
  }

  int ave1 = sum/n, ave2 = (sum+n-1)/n;
  int ans1 = 0, ans2 = 0;
  for (int i = 0; i < n; i++) {
    ans1 += (x[i]-ave1) * (x[i]-ave1);
    ans2 += (x[i]-ave2) * (x[i]-ave2);
  }
  cout << min(ans1, ans2) << endl;
  return 0;
}

Measured memory_bytes: 384
A, B, C = map(int, input().split())
mods = set()
i = 1
while True:
    mod = (A*i)%B
    if mod in mods:
        break
    mods.add(mod)
    i += 1
# 結局, 総和は A の倍数になる
print("YES" if C in mods else "NO")


Measured memory_bytes: 2940
N = int(input())
A = list(map(int,input().split()))
s = 1
for i in A:
  if i < 0:
    s *= -1
Aabs = list(map(abs,A))

if s == 1:
  print(sum(Aabs))
else:
  print(sum(Aabs)-2*min(Aabs))

Measured memory_bytes: 14480
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
 
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

int main(){
    int a,b;
    cin >> a >> b;
    cout << a + b/2 << endl;
}   


Measured memory_bytes: 256