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

typedef long long  ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;

#define INPUT(arr,n) for(ll i = 0;i<n;i++) cin>>arr[i];
#define PRINT(arr,n) for(ll i = 0;i<=n;i++) printf("%lld ",arr[i]);printf("\n");
#define MEM(var,val) memset(var,(val),sizeof(var))
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define mp make_pair
#define pb push_back

const ll NMAX = 100000+7;
const ll MOD = 1000*1000*1000+7;
const ll INT_BITS = 32 ;
ll arr[NMAX][3];
ll dp[NMAX][3];

inline ll add(ll a, ll b) {
  ll r = a + b;
  return (r >= MOD ? r - MOD : r);
}

inline ll sub(ll a, ll b) {
  ll r = a - b;
  return (r < 0 ? r + MOD : r);
}

inline ll mul(ll a, ll b) {
  ll r = a * b;
  return (r >= MOD ? r % MOD : r);
}


ll N;

ll func(ll i, ll s){
  if(s>=0 and dp[i][s] != -1) return dp[i][s];
  if(i >= N) return 0;

  ll res = 0;
  for(ll k = 0;k<3;k++){
      if(k==s)continue;
    // cout<<res<<endl;
    res = max(res, func(i+1,k)+arr[i][k]);
  }
  return dp[i][s] = res;
}

int main(int argc, char const *argv[])
{
	cin>>N;
  MEM(dp,-1);
  for(ll i = 0;i<N;i++)
    for(ll k = 0;k<3;k++)
      cin>>arr[i][k];
  cout<<func(0,-1)<<endl;;
	return 0;
}

Measured memory_bytes: 11136
#include<iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <cmath>
using namespace std;

int main()
{
    // 整数の入力
    long long n,m,d;
    double base;
    cin >> n >> m >> d;
    if (d == 0){
        base = 1.0/n;
    }else if (2 * d < n){
        base =(2.0 * d/n) * 1.0/n + ((n - 2.0* d)/n) * 2.0/n;
    }else{
        base = (2.0* n - 2.0 * d)/n * 1.0/n;
    }
    cout << fixed << setprecision(10) << base * (m-1) << endl;
    return 0;
}

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

int main() {
  int x;
  cin >> x;
  int big = x / 500;
  int small = x % 500 / 5;
  
  cout << big * 1000 + small * 5;

}

Measured memory_bytes: 256
N=int(input())
M=10**9+7
#A=[int(x) for x in input().split()]
A=list(map(int,input().split()))

ans=0
for i in range(60):
  one=sum([a>>i&1 for a in A])
  zero=N-one
  ans+=(one*zero)*2**i
  ans%=M
  #print(one,zero)
print(ans)

Measured memory_bytes: 51136
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	int n, ans = 0; cin >> n;
	vi to(n); rep(i, n) cin >> to[i], to[i]--;
	rep(i, n) if(to[to[i]] == i) ans++;
	cout << ans / 2 << endl;
	return 0;
}

Measured memory_bytes: 640
parseInt(x)=parse(Int, x)
parseMap(x::Array{SubString{String},1})=map(parseInt, x)

function npow(x,n,p)
	ans = 1
	for i in 1:n
		ans = ans*x%p
	end
	ans
end

function main()
	p = 1000000007
	n,k = readline() |> split |> parseMap
	dp = zeros(Int,k)
	for i in k>>1+1:k
		dp[i] = 1
	end
	pow = -ones(Int,k)
	for i in k>>1:-1:1
		mp = 2
		mk = 0
		while i*mp<=k
			dp[i] = mod(dp[i]-dp[i*mp],p)
			mp += 1
			mk += 1
		end
		if pow[mk+1]==-1
			pow[mk+1] = npow(mk+1,n,p)
		end
		dp[i]=(dp[i]+pow[mk+1])%p
	end
	s = 0
	for i in 1:k
		s = (s+dp[i]*i%p)%p
	end
	println(s)
end

main()

Measured memory_bytes: 182448
#include<iostream>
#include<cmath>
#include<string.h>

using namespace std;

int main(){
	char a[100],b[100],c[100];
	int n,m;
	cin >> a >> b;
	cin >> n >> m;
	cin >> c;
	if(strcmp(a,c)==0) n--;
	if(strcmp(b,c)==0) m--;
	cout << n << " " <<m <<endl;
	return 0;
}

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

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  string s;
  cin >> s;

  int l = 0, r = s.size()-1, prevl = 0, prevr = s.size()-1;
  ll ret = 0;
  while(l < r) {
    while(l < r && s[l] == 'x') l++;
    while(l < r && s[r] == 'x') r--;
    // cout << l << " " << r << " ";
    if(l == r && s[l] == 'x' && s[r] == 'x') break;
    if(s[l] != s[r]) {
      cout << "-1" << endl;
      return 0;
    }
    ret += abs((l-prevl-1) - (prevr-r-1));
    // cout << ret << endl;
    prevl = l, prevr = r;
    l++, r--;
  }
  cout << ret << endl;

  return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
const int N = 2e5+5;
const int mod = 1e9+7;
typedef long long ll ;
ll s[N],arr[N];


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int num;
    cin>>num;
    for(int i = 1;i<=num;i++)
    {
        ll temp;
        cin>>temp;
        arr[i]=temp;
        if(i==1)
            s[i]=temp;
        else
            s[i]=(s[i-1]+temp);
    }
    ll he = 0;
    for(int i =1;i<=num;i++)
    {
        he+=((s[num]-s[i])%mod)*arr[i];
        he=he%mod;
    }
    cout<<he<<endl;


}


Measured memory_bytes: 6728
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <stdio.h>
#include <complex>

using namespace std;

//conversion
//------------------------------------------
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();}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef vector<LL> VLL;

//container util

//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#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 SORT(c) sort((c).begin(),(c).end())
#define MT(a,b,c) MP(a, MP(b, c))

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

int main(){
	while(1){
		int w,h;
		int xd[11], yd[11];
		int dc=1;
		cin>>w>>h;
		if(w == 0)break;
		VS board(h+2);
		REP(i, h){
			cin>>board[i+1];
			board[i+1] = "x" + board[i+1]+"x";
		}
		board[0] = board[1];
		board[h+1] = board[1];
		REP(i,w+2){
			board[0][i] = 'x';
			board[h+1][i] = 'x';
		}
		
		REP(i, h+2){
			REP(j, w+2){
				if(board[i][j] == 'o'){
					xd[0] = j;
					yd[0] = i;
					board[i][j] = 'a';
				}
				if(board[i][j] == '*'){
					board[i][j] = 'a'+dc;
					xd[dc] = j;
					yd[dc++] = i;
				}
			}
		}
		VVI dist(dc, VI(dc, -1));
		REP(i,dc)dist[i][i]=0;
		for(int d = 0; d<dc; d++){
			VVI visit(h+2, VI(w+2, 0));
			priority_queue<TIII, vector<TIII>, greater<TIII> > q;
			q.push(MT(0, xd[d], yd[d]));
			while(!q.empty()){
				TIII tmp = q.top();
				q.pop();
				int tx = tmp.second.first;
				int ty = tmp.second.second;
				int td = tmp.first;
				if(visit[ty][tx]==1)continue;
				if(board[ty][tx]!='.')dist[d][board[ty][tx]-'a']=td;
				visit[ty][tx] = 1;
				REP(i, 4){
					switch(board[ty+dy[i]][tx+dx[i]]){
					case 'x':
						break;
					default:
						q.push(MT(td+1, tx+dx[i], ty+dy[i]));
						break;
					}
				}
			}
		}
		VI v(dc-1);
		int flag = 0;
		REP(i,dc)REP(j,dc)if(dist[i][j]<0)flag = 1;
		if(flag){
			cout << "-1" <<endl;
			continue;
		}
		REP(i, dc-1)v[i] = i+1;
		int ret = 1000000000;
		do{
			int s = 0;
			int tret = dist[0][v[0]];
			REP(i, dc-2)tret += dist[v[i]][v[i+1]];
			if(tret < ret)ret = tret;
		}while(next_permutation(ALL(v)));
		cout << ret << endl;
	}
	return 0;
}

Measured memory_bytes: 1252
class FutureMath:
    def gcd(self, a, b):
        if a < b:
            return self.gcd(b, a)
        if b == 0:
            return a
        while b:
            a, b = b, a % b
        return a

    def gcd_(self, list):
        result = list[0]
        for el in list[1:]:
            result = self.gcd(result, el)
        return result

    def lcm(self, a, b):
        return a * b // self.gcd(a, b)

    def lcm_(self, list):
        result = list[0]
        for el in list[1:]:
            result = self.lcm(result, el)
        return result

    def divisors(self, n):
        result = list()
        for i in range(1, n+1):
            if n % i == 0:
                result.append(i)
        return result


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

fm = FutureMath()


a, b, c, d = LI()
B = b - (b//c + b//d - b//fm.lcm(c, d))
A = a - (a//c + a//d - a//fm.lcm(c, d))
border = 1 - int((a % c == 0) or (a % d == 0))
print(B - A + border)


Measured memory_bytes: 3064
#include <stdio.h>
#include <cmath>
using namespace std;

// 二分探索
int binarySearch(int *A, int n, int key) {
    int compare=int(n/2);
    float tmp=compare;
    while(tmp > 0) {
        if(key < A[compare]) {
            tmp = tmp/2;
            compare = compare - tmp;
        } else if(key > A[compare]) {
            tmp = tmp/2;
            compare = compare + tmp +0.5;
        } else {
            return 1;
        }
    }
    return 0;
}

int main() {
    int n, q;
    scanf("%d", &n);
    int S[n];
    for(int i=0; i<n; i++) scanf("%d", &S[i]);
    scanf("%d", &q);
    
    int tmp, sum=0;
    for(int i=0; i<q; i++) {
        scanf("%d", &tmp);
        sum += binarySearch(S, n, tmp);
    }
    
    printf("%d\n", sum);
    return 0;
}


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

#define REP(type, i, a, b) for( type i = a; i < b; i++ )
typedef long long ll;

using namespace std;

int main (void) {
    ll N, ans;
    scanf("%lld", &N);
    ans = N*N*N;
    printf("%lld\n", ans);
    return 0;
}


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

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)

using ll = long long;
using ld = long double;
ll INF = LLONG_MAX;

using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int, int>;

namespace output {
	void pr(int x) { cout << x; }
	void pr(long x) { cout << x; }
	void pr(ll x) { cout << x; }
	void pr(unsigned x) { cout << x; }
	void pr(unsigned long x) { cout << x; }
	void pr(unsigned long long x) { cout << x; }
	void pr(float x) { cout << x; }
	void pr(double x) { cout << x; }
	void pr(ld x) { cout << x; }
	void pr(char x) { cout << x; }
	void pr(const char* x) { cout << x; }
	void pr(const string& x) { cout << x; }
	void pr(bool x) { pr(x ? "true" : "false"); }
	template<class T> void pr(const complex<T>& x) { cout << x; }
	
	template<class T1, class T2> void pr(const pair<T1,T2>& x);
	template<class T> void pr(const T& x);
	
	template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { 
		pr(t); pr(ts...); 
	}
	template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
		pr("{",x.f,", ",x.s,"}"); 
	}
	template<class T> void pr(const T& x) { 
		pr("{"); // const iterator needed for vector<bool>
		bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; 
		pr("}");
	}
	
	void print() { pr("\n"); } // print w/ spaces
	template<class T, class... Ts> void print(const T& t, const Ts&... ts) { 
		pr(t); if (sizeof...(ts)) pr(" "); print(ts...); 
	}
}

using namespace output;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int N, M; cin >> N >> M;
	
	vi AS (N);
	F0R(i, N) {
		cin >> AS[i];
		AS[i] /= 2;
	}

	ll lcm = 1; 
	for (int i = 0; i < N; ++i) {
		lcm = lcm * AS[i] / __gcd((int) lcm, AS[i]);
		if (lcm > M) {
			cout << 0 << endl;
			return 0;
		}
	}

	bool be = false;
	bool bo = false;
	for (int i = 0; i < N; ++i) {
		if (lcm / AS[i] % 2 == 0) {
			// doesnt alternate
			if (lcm % (2 * AS[i]) == 0) {
				cout << 0 << endl;
				return 0;
			}
		} else {
			// alternates
			if (lcm % (2 * AS[i]) == 0) {
				be = true;
			} else {
				bo = true;
			}
		}
	}

	if (be && bo) {
		print(0);
	} else if (bo) {
		print((M-lcm) / (2 * lcm) + 1);
	} else if (be) {
		print(M / (2 * lcm));
	} else {
		print(M / lcm);
	}
}

Measured memory_bytes: 640
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#include <unordered_map>

using namespace std;

#define int long long
#define ll long long
//#define double long double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

const int INF = 2e9;
const int MB = 20;
const int MOD = 1e9 + 7;

void solve() {
    int n, d;
    cin >> n >> d;
    vector<vector<int>> a(n, vector<int>(d));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < d; j++) {
            cin >> a[i][j];
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int res = 0;
            for (int c = 0; c < d; c++) {
                res += (a[i][c] - a[j][c]) * (a[i][c] - a[j][c]);
            }
            double one = (int)sqrt(res);
            if (one == sqrt(res)) ans++;
        }
    }
    cout << ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    //int t;
    //cin >> t;
    int t = 1;
    while (t--) solve();
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ctime>
#include <cstdlib>
#define rep(i, N) for (long i = 0; i < (N); i++)
#define swap(a, b) (a += b, b = a - b, a -= b)
using namespace std;
int main()
{
    int N;
    cin >> N;
    vector<long > A(N + 1), B(N);
    rep(i, N + 1)
    {
        cin >> A[i];
    }
    rep(i, N)
    {
        cin >> B[i];
    }
    long  S, count = 0;
    rep(i, N)
    {
        S = B[i] - A[i];
        if (S >= 0)
        {
            count += A[i];
            A[i] = 0;
            if (S >= A[i + 1])
            {
                count += A[i + 1];
                A[i + 1] = 0;
            }
            else
            {
                A[i + 1] -= S;
                count += S;
            }
        }
        else
        {
            count += B[i];
            A[i] -= B[i];
        }
    }
    cout << count << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string s;
  cin >> s;
  
  int cnt = 0;
  if(s.at(0)=='1') cnt++;
  if(s.at(1)=='1') cnt++;
  if(s.at(2)=='1') cnt++;
  
  cout << cnt << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <math.h>

using namespace std;

typedef long long int ll;
typedef long double ld;

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define vsort(a) sort(a.begin(), a.end())
#define rev(a) reverse(a.begin(), a.end())


// a,bの最小公倍数
ll LCM(ll a, ll b){ll lcm = a * b; ll r = a % b;while(r != 0){a = b; b = r; r = a % b;}return lcm /= b;}
// a,bの最大公約数
ll GCD(ll a, ll b){ll r = a % b;while(r != 0){a = b; b = r; r = a % b;}return b;}


const int MOD = 1000000007;
const int INF = INT_MAX;



int main(){



    string s;
    cin >> s;

    ll cnt = 0;
    ll w = 0;
    rep(i,s.size()) {
        if (s[i] == 'W') {
            cnt += i - w;
            w++;
        }
    }

    cout << cnt << endl;



}





//              g++ -std=c++1z


Measured memory_bytes: 832
#include <iostream>
using namespace std;
int t[11] = {0, 1, 2, 3, 4, 5, 5, 4, 3, 2, 1};
int main() {
    string x;
    while (cin >> x) {
        int ans = 0;
        for (int i = x.size() - 1; i > 0; i--) {
            int p = x[i] - '0';
            if (p == 5 && x[i - 1] >= '5') {
                ans += 10 - p;
                x[i - 1]++;
            } else if (p > 5) {
                ans += 10 - p;
                x[i - 1]++;
            } else {
                ans += p;
            }
        }
        ans += t[x[0] - '0'];
        cout << ans << endl;
    }
}

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

using namespace std;

int main(){
	string s;
	string al = "abcdefghijklmnopqrstuvwxyz";

	cin >> s;

	for(int i=0; i<s.length(); i++){
		for(int j=0; j<al.length(); j++){
			if(s[i] == al[j]) al[j] = '0';
		}
	}
	for(int i=0; i<al.length(); i++){
		if(al[i] != '0'){
			cout << al[i] << endl;
			break;
		}
		if(i == 25) cout << "None" << endl;
	}
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ll a,b,k;
	cin >> a >> b >> k;
	ll i;
	for(i=1;i<=k;i++)
	{
		if(i%2!=0)
		{
			if(a%2==1)
			{
				a--;
			}
			ll x= a/2;
			a= a- x;
			b= b+x;
		}
		else
		{
			if(b%2==1)
			{
				b--;
			}
			ll x= b/2;
			b= b-x;
			a = a+ x;
		}
	}
	cout << a << " "  << b;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <sstream>
#include <algorithm>

using namespace std;

#define	numberof(a)	(sizeof(a) / sizeof(a[0]))
#define	INF		(1000000)
#define Rep(i,n) for(int i = 0; i < (n); i++ )

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define	show(x)	 copy( (x).begin(), (x).end(), ostream_iterator<int>(cout, ",") );	// container<int>を全て表示

using namespace std;

typedef long long ll;

//constant
//--------------------------------------------
const double EPS = 1e-10;
//const double PI  = acos(-1.0);

ll kaijo( ll N )
{
	// 階乗
	if( N == 0 ) return 1;
	return N * kaijo(N - 1);
}

map<ll, ll> prime_factor(ll N)
{
	// 素因数分解
	map<ll, ll> ret;
	for( ll i = 2; i * i <= N; i++ ){
		while( N % i == 0 ){
			ret[i]++;
			N /= i;
		}
	}
	if(N != 1) ret[N] = 1;
	return ret;
}

ll gcd( ll a, ll b )
{
	// a >= b
	if( b > a ) swap(a, b);
	if( b == 0 ) return a;
	return gcd( a % b, b );
}

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

ll max( ll a, ll b )
{
	if( a > b ) return a;
	return b;
}
ll min( ll a, ll b )
{
	if( a > b ) return b;
	return a;
}

class UnionFind
{
public:
	vector<int> parent;
	vector<int> rank;

	UnionFind(int n)
	{
		Rep(i, n){
			parent.push_back(i);
			rank.push_back(1);
		}
	}
	int root(int x)
	{
		if( parent[x] != x ) parent[x] = root(parent[x]);
		return parent[x];
	}
	void unite(int x, int y)
	{
		int rx = root(x);
		int ry = root(y);
		if( rx == ry ) return;
		if( rank[rx] > rank[ry] ){
			parent[ry] = rx;
			rank[rx] += rank[ry];
		}
		if( rank[rx] <= rank[ry] ){
			parent[rx] = ry;
			rank[ry] += rank[rx];
		}
	}
};

int main()
{
	ll N = 0;
	ll ans = 0;

	cin >> N;

	for(int i = 1; i <= N; ++i){
		map<ll, ll> factors = prime_factor(i);

		ll tmp = 1;
		for(int j = 2; j * j <= N; ++j){
			tmp *= (factors[j] + 1);
		}

		if(tmp == 8 && i % 2 == 1){
			ans++;
		}
	}

	cout << ans << endl;
	cin >> N;

	return 0;
}


Measured memory_bytes: 384
M, K = map(int, input().split())
A = list(map(int, input().split()))
cnt = 0
for i, Ai in enumerate(A):
  for Aj in A[i+1:]:
    if Ai > Aj:
      cnt += 1
cnt_sorted = 0
A_sorted = sorted(A, reverse=True)
for i, Ai in enumerate(A_sorted):
  for Aj in A_sorted[i+1:]:
    if Ai > Aj:
      cnt_sorted += 1
ans = cnt * K + cnt_sorted * K * (K-1) // 2
print(ans % (10 ** 9 + 7))

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

int main() {
  int n,m;
  cin>>n>>m;
  int A[100001];
  for(int i=0;i<m;i++){
    cin>>A[i];
  }  
  bool broken[100001];
  for(int i=0;i<m;i++){
    broken[A[i]]=true;
  }
  int dp[100001]={1};
  if(broken[1]==true){
    dp[1]=0;
  }
  else{
    dp[1]=1;
  }
  for(int i=2;i<=n;i++){
    if(broken[i]==true) continue;
    else{
      dp[i]=dp[i-1]+dp[i-2];
      dp[i] %= 1000000007;
    }
  }
  cout<<dp[n]<<endl;
  return 0;
}
    

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

using namespace std;

typedef long long L;
const int maxn = 233 , mod = 1e9 + 7 , inv2 = 500000004;
int n;
int h[maxn];
int fpw(int x , int t){
	if(!t) return 1;
	int c = fpw(x , t >> 1);
	c = (L)c * c % mod;
	if(t & 1) c = (L)c * x % mod;
	return c;
}

int ans[maxn][maxn][3];
bool vis[maxn][maxn];
int c[2];

void solve(int l , int r , int d){
	if(vis[l][r])
		return ;
	vis[l][r] = 1;
	if(l == r){
		ans[l][r][1] = fpw(2 , h[l] - d + 1);
//		cerr << l << " " << r << " " << d << " " << ans[l][r][0] << " " << ans[l][r][1] << endl;
		return ;
	}
	int minn = (int)1e9 + 10;
	for(int k = l ; k <= r ; ++ k)
		minn = min(minn , h[k]);
	int ll = l , rr = -1;
	for(int k = l ; k <= r ; ++ k)
		if(h[k] == minn){
			rr = k - 1;
			if(ll <= rr)
				solve(ll , rr , minn + 1);
			ll = k + 1;
		}
	rr = r;
	if(ll <= rr)
		solve(ll , rr , minn + 1);
	memset(c , 0 , sizeof c);
	ll = l , rr = r;
	bool first = 1;
	for(int k = l ; k <= r ; ++ k)
		if(h[k] == minn){
			rr = k - 1;
			if(ll <= rr){
				if(first){
					c[0] = ans[ll][rr][0];
					c[1] = (ans[ll][rr][1] << 1) % mod;
					first = 0;
				}
				else{
					c[0] = ((L)c[0] * ((L)2 * ans[ll][rr][1] + ans[ll][rr][0]) + (L)c[1] * (ans[ll][rr][0] + ans[ll][rr][1])) % mod;
					c[1] = (L)c[1] * ans[ll][rr][1] % mod;
				}
			}
//			cerr << k << " " << c[0] << " " << c[1] << endl;
			if(first){
				c[0] = 0;
				c[1] = 2;
				first = 0;
			}
			else
				c[0] = ((L)c[0] * 2 + c[1]) % mod;
			ll = k + 1;
//			cerr << k << " " << c[0] << " " << c[1] << endl;
		}
	rr = r;
	if(ll <= rr){
		if(first){
			c[0] = ans[ll][rr][0];
			c[1] = (ans[ll][rr][1] << 1) % mod;
			first = 0;
		}
		else{
			c[0] = ((L)c[0] * ((L)2 * ans[ll][rr][1] + ans[ll][rr][0]) + (L)c[1] * (ans[ll][rr][0] + ans[ll][rr][1])) % mod;
			c[1] = (L)c[1] * ans[ll][rr][1] % mod;
		}
	}
	ans[l][r][0] = c[0];
	ans[l][r][1] = (L)c[1] * fpw(2 , minn - d) % mod;
//	cerr << l << " " << r << " " << d << " " << ans[l][r][0] << " " << ans[l][r][1] << endl;
}
int main(){
	cin >> n;
	for(int i = 1 ; i <= n ; ++ i)
		cin >> h[i];
	solve(1 , n , 1);
	cout << (ans[1][n][0] + ans[1][n][1]) % mod << endl;
	return 0;
}

Measured memory_bytes: 512
#include<stdio.h>

int main(){
  int i;
  int a,b;
  if(scanf("%d%d",&a,&b)!=2) return 1;
  if(a<b) for(i=0;i<b;i++) printf("%d",a);
  else for(i=0;i<a;i++) printf("%d",b);
  printf("\n");
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <queue>
#include <deque>
#include <cstdio>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORE(i,a,b) for(int i=(a);i<=(b);i++)
#define REP(i,b) FOR(i,0,b)
int dx[5]={0,1,0,-1,0}, dy[5]={1,0,-1,0,0};
using namespace std;
typedef long long ll;
const ll INF=(ll)1<<60;
typedef pair<int,int> pr;
typedef pair<int,pr> ppr;
typedef vector<int> vi;
typedef vector<pr> vpr;
const int size=100001;
const int segSize=1+(1<<18);
ll N,M,C,a[size]={};
ll segmentL[segSize]={},segmentR[segSize]={};
ll getMax(ll segment[segSize],int now,int tall,int s,int e){
		int nS=now*(1<<(18-(tall+1)))-(1<<17),nE=(now+1)*(1<<(18-(tall+1)))-1-(1<<17);
		if(s<=nS&&nE<=e)
		return segment[now];
		if(s>nE||e<nS)
		return -INF;
		return max(getMax(segment,now*2+1,tall+1,s,e),getMax(segment,now*2,tall+1,s,e));
}
void check(ll segment[segSize],int R){
	if(R==0)
	return;
	else
	segment[R]=max(segment[R*2],segment[R*2+1]);
	check(segment,R/2);
	return;
}
void put(ll segment[segSize],int num,ll value){
	segment[(1<<17)+num]=value;
	check(segment,((1<<17)+num)/2);
}
bool able(int R){
	ll sum=0;
	REP(i,N){
	 	sum+=max(getMax(segmentL,1,0,max(0,i-R),i)+(ll)(N-i-1)*C,getMax(segmentR,1,0,i,min(N-1,(ll)i+R))+(ll)(i*C));

	}
	return sum>=M;
}
int main() {
	cin >> N >> M >> C;
	REP(i,segSize){
		segmentL[i]=-INF;
		segmentR[i]=-INF;
	}
	REP(i,N){
	cin >>a[i];
	put(segmentL,i,a[i]-(N-i-1)*C);
	put(segmentR,i,a[i]-(i*C));
	}
	int s=0,e=N-1;
	while(s<=e){
		int next=(s+e)/2;
		if(able(next))
		e=next-1;
		else
		s=next+1;
	}
	if(s==N)
	cout <<-1<<endl;
	else
	cout << s << endl;
	// your code goes here
	return 0;
}


Measured memory_bytes: 6040
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int INF=998244353;
char a[202020];
int f[202020][3][3][2];
int main()
{
	int n,sum,pp,i,j,k,l,ans=0,lt;
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%s",a+1);
	n=strlen(a+1);
	if(n<4)
	{
		if(n==1)
		{
			printf("1");
			return 0;
		}
		if(n==2)
		{
			if(a[1]==a[2])
				printf("1");
			else
				printf("2");
			return 0;
		}
		if(a[1]==a[2]||a[2]==a[3])
		{
			if(a[1]==a[2]&&a[2]==a[3])
				ans=1;
			else
				ans=6;
		}
		else
		{
			if(a[1]==a[3])
				ans=7;
			else
				ans=3;
		}
		printf("%d\n",ans);
		return 0;
	}
	sum=0,pp=0;
	for(i=2;i<=n;i++)
	{
		if(a[i]==a[i-1])
			sum++;
		pp+=a[i]-'a';
	}
	pp+=a[1]-'a';
	pp%=3;
	if(sum==n-1)
	{
		printf("1");
		return 0;
	}
	if(sum==0)
		ans++;
	//f[0][0][0][0]=1;
	for(i=0;i<=2;i++)
		f[1][i][i][0]=1;
	for(i=2;i<=n;i++)
	{
		for(j=0;j<=2;j++)
		{
			for(k=0;k<=2;k++)
			{
				for(l=0;l<=2;l++)
				{
					lt=j-k;
					if(lt<0)
						lt+=3;
					if(k==l)
					{
						f[i][j][k][1]=(f[i][j][k][1]+f[i-1][lt][l][0])%INF;
						f[i][j][k][1]=(f[i][j][k][1]+f[i-1][lt][l][1])%INF;
					}
					else
					{
						f[i][j][k][0]=(f[i][j][k][0]+f[i-1][lt][l][0])%INF;
						f[i][j][k][1]=(f[i][j][k][1]+f[i-1][lt][l][1])%INF;
					}
				}
			//	printf("%d %d %d %d %d %d\n",i,j,k,l,f[i][j][k][0],f[i][j][k][1]);
			}
		}
	}
	for(i=0;i<=2;i++)
	{
		ans=(ans+f[n][pp][i][1])%INF;
	}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 14592
using System;
class Program
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        var a = Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
        long ans = 0;
        for (int i = 0; i < n; i++)
        {
            while (a[i] % 2 == 0)
            {
                a[i] /= 2;
                ans++;
            }
        }
        Console.WriteLine(ans);
    }
}

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

#define fi first
#define se second
#define pb push_back
#define rep(i,n) for(int i=0; i<(int)(n); i++)

double dp[301][301][301];
int n;

double rec(int i, int j, int k) {
	//cout << "i:" << i << "j:" << j << "k:" << k << endl;
	if(dp[i][j][k] >= 0) {
		//cout << "already memoed" << endl;
		return dp[i][j][k];
	}
	if(i==0 && j==0 && k==0) return 0.0;
	else {
		double ans=0;
		if(i != 0) ans += i*rec(i-1,j,k);
		if(j != 0) ans += j*rec(i+1,j-1,k);
		if(k != 0) ans += k*rec(i, j+1,k-1);
		ans += n;
		ans *= 1.0 / (i+j+k);

		return dp[i][j][k] = ans;
		
	}
}

int main() {
	cin >> n;
	int a,a1=0,a2=0,a3=0;
	rep(i,n) {
		cin >> a;
		if(a == 1) a1++;
		else if(a == 2) a2++;
		else a3++;
	}
	memset(dp, -1, sizeof(dp));
	cout << setprecision(15) << rec(a1,a2,a3) << endl;
  return 0;
}


Measured memory_bytes: 213376
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define in(x) cin >> x
#define out(str) cout << str << endl

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

int A,B,C;

int main(){
    cin>>A>>B>>C;
    if(C>=A&&C<=B){
        out("Yes");
    }else{
        out("No");
    }
}

Measured memory_bytes: 256
N, Q = map(int, input().split())
S = str(input())
L = [0]  # ruisekiwa
for i in range(1, len(S)):
    if S[i-1:i+1] == 'AC':
        L.append(L[i-1]+1)
    else:
        L.append(L[i-1])

for i in range(Q):
    l, r = map(int, input().split())
    print(L[r-1]-L[l-1])


Measured memory_bytes: 6156
#include<iostream>
#include<string>
#include<vector>
#include<numeric>
#include<math.h>
#include<algorithm>
#include<iomanip>
#include<bitset>
using namespace std;

int main() {

	string S, T;
	cin >> S >> T;

	if (S == T.substr(0, S.size())) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}


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

int main() {
  int A,B,C,D;
  cin>>A>>B>>C>>D;
  int X=A/D;
  if(A>X*D){
    X++;
  }
  int Y=C/B;
  if(C>B*Y){
    Y++;
  }
  if(Y<=X){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
}

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

int main() {
  char a[3];
  int count = 0;
  int i;
  cin >> a[0];
  cin >> a[1];
  cin >> a[2];
  for(i = 0;i < 3;i++){
  	if(a[i] == '1'){
    	count++;
    }
  }
  cout <<  count << endl;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    int t = 0;
    if (a < k) {
        t += a;
        k -= a;
        if (b < k) {
            k -= b;
            t -= min(c, k);
        }
    } else {
        t = min(a, k);
    }
    cout << t << endl;
}

Measured memory_bytes: 3620
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		sc.close();
		String a = "CODEFESTIVAL2016";
		int len = s.length();
		int ans = 0;
		for(int i=0; i<len; i++){
			if(s.charAt(i) == a.charAt(i)){
				ans++;
			}
		}
		System.out.println(len-ans);
	}

}

Measured memory_bytes: 10064
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int (i)=0;(i)<(n);(i)++)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
bool custom1 (pair<int, int> a, pair<int, int> b) {
  return (a.first < b.first);
}
bool custom2(pair<int, int> a, pair<int, int> b) {
  return (a.second < b.second);
}

const int MAX = 200005;
const long long MOD = 1000000007;
const long long MODMOD = 998244353;
const double PI = acos(-1);

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

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

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

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
struct UnionFind {
  vector<int> p;
  vector<int> s;
  void init(int n) {
    p.resize(n, -1);
    s.resize(n, 1);
  }
  int find(int n) {
    if(p[n] == -1) return n;
    else return find(p[n]);
  }
  int size(int n) {
    return s[find(n)];
  }
  void unite(int n, int m) {
    int pn = find(n);
    int pm = find(m);
    if(pn == pm) return;
    if(s[pn] > s[pm]) {
      s[pn] = s[pn] + s[pm];
      p[pm]= pn;
    } else {
      s[pm] = s[pm] + s[pn];
      p[pn] = pm;
    }
  }
};

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

int main() {
  int n;
  cin >> n;
  vector<string> prev;
  vector<char> largest;
  rep(i, n) {
    if(i == 0) {
      prev.emplace_back("a");
      largest.emplace_back('a');
    }
    else {
      vector<string> now;
      vector<char> now_largest;
      rep(j, prev.size()) {
        char c = largest[j];
        char add = 'a';
        while(add != c + 2) {
          now.emplace_back(prev[j]+add);
          now_largest.emplace_back(max(c, add));
          add++;
        }
      }
      prev.resize(now.size());
      largest.resize(now_largest.size());
      largest = now_largest;
      prev = now;
    }
  }
  sort(prev.begin(), prev.end());
  rep(i, prev.size()) cout << prev[i] << endl;
}


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

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

int main() {

    ll d; cin >> d;

    vector<ll> c(26);
    for (ll i = 0; i < 26; ++i) {
        cin >> c[i];
    }

    vector<vector<ll>> s(d, vector<ll>(26));
    for (ll i = 0; i < d; ++i) {
        for (ll j = 0; j < 26; ++j) {
            cin >> s[i][j];
        }
    }

    vector<ll> t(d);
    for (ll i = 0; i < d; ++i) {
        ll idx = 0;
        ll mx = 0;
        for (ll j = 0; j < 26; ++j) {
            if (mx < s[i][j]) {
                mx = s[i][j];
                idx = j;
            }
        }
        t[i] = idx;
    }

    vector<ll> score(d, 0);
    vector<vector<ll>> last(d, vector<ll>(26, 0));

    auto re_score = [&](ll start) {
        for (ll i = start; i < d; ++i) {
            score[i] = (i - 1 >= 0 ? score[i - 1] : 0) + s[i][t[i]];

            if (i - 1 >= 0) {
                last[i] = last[i - 1];
            } else {
                for (ll j = 0; j < 26; ++j) {
                    last[0][j] = 0;
                }
            }

            last[i][t[i]] = i + 1;

            ll j = i + 1;

            for (ll k = 0; k < 26; ++k) {
                score[i] -= c[k] * (j - last[i][k]);
            }
        }
    };

    re_score(0);

    vector<vector<pair<ll, ll>>> kouho(d);

    ll mx_score = score[d - 1];
//    for (int r = 0; r < 10; ++r) {
        for (ll i = 0; i < d; ++i) {
            for (ll j = 0; j < 26; ++j) {
                ll tmp = t[i];

                t[i] = j;
                re_score(i);

                kouho[i].push_back(make_pair(score[d - 1], j));

                if (mx_score >= score[d - 1]) {
                    t[i] = tmp;
                    re_score(i);
                } else {
                    mx_score = score[d - 1];
                }
            }
        }
//    }

    for (int i = 0; i < d; ++i) {
        sort(kouho[i].rbegin(), kouho[i].rend());
    }

    for (int r = 0; r < 10; ++r) {
        for (ll i = 0; i < d; ++i) {
            for (ll j = 0; j < 10; ++j) {
                ll tmp = t[i];

                t[i] = kouho[i][j].second;
                re_score(i);

                if (mx_score >= score[d - 1]) {
                    t[i] = tmp;
                    re_score(i);
                } else {
                    mx_score = score[d - 1];
                }
            }
        }
    }

    for (ll i = 0; i < d; ++i) {
        cout << t[i] + 1 << endl;
    }
}

Measured memory_bytes: 3996
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(ll i=0;i<(n);i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORC(i,a,b,c) for(ll i=(a);i<(b);i+=(c))
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define ff first
#define ss second
#define dd long double
#define mod 1000000007

ll getMid(ll s, ll e) { return s + (e -s)/2; }

ll getSumUtil(ll *st, ll ss, ll se, ll qs, ll qe, ll si)
{
    if (qs <= ss && qe >= se)
        return st[si];
    if (se < qs || ss > qe)
        return 0;
    ll mid = getMid(ss, se);
    return max(getSumUtil(st, ss, mid, qs, qe, 2*si+1),
        getSumUtil(st, mid+1, se, qs, qe, 2*si+2));
}

void updateValueUtil(ll *st, ll ss, ll se, ll i, ll diff, ll si)
{
    if (i < ss || i > se)
        return;
    if(ss==se){
        st[si]+=diff;
    }
    else{
        ll mid = getMid(ss, se);
        updateValueUtil(st, ss, mid, i, diff, 2*si + 1);
        updateValueUtil(st, mid+1, se, i, diff, 2*si + 2);
        st[si]=max(st[2*si+1],st[2*si+2]);
    }
}
void updateValue(ll arr[], ll *st, ll n, ll i, ll new_val)
{
    if (i < 0 || i > n-1)
    {
        cout<<"Invalid Input";
        return;
    }
    ll diff = new_val - arr[i];
    arr[i] = new_val;
    updateValueUtil(st, 0, n-1, i, diff, 0);
}
ll getSum(ll *st, ll n, ll qs, ll qe)
{
    if (qs < 0 || qe > n-1 || qs > qe)
    {
        cout<<"Invalid Input";
        return -1;
    }
    return getSumUtil(st, 0, n-1, qs, qe, 0);
}
ll constructSTUtil(ll arr[], ll ss, ll se, ll *st, ll si)
{
    if (ss == se)
    {
        st[si] = arr[ss];
        return arr[ss];
    }
    ll mid = getMid(ss, se);
    st[si] = max(constructSTUtil(arr, ss, mid, st, si*2+1),
            constructSTUtil(arr, mid+1, se, st, si*2+2));
    return st[si];
}

ll *constructST(ll arr[], ll n)
{
    ll x = (ll)(ceil(log2(n)));
    ll max_size = 2*(ll)pow(2, x) - 1;
    ll *st = new ll[max_size];
    constructSTUtil(arr, 0, n-1, st, 0);
    return st;
}
const ll N=8e5;
ll arr[N];
ll * st=constructST(arr,N);
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,k;
    cin>>n>>k;
    REP(i,n){
        ll t;
        cin>>t;
        ll lower=max(0ll,t-k);
        ll higher=t+k;
        ll val=getSum(st,N,lower,higher);
        updateValue(arr,st,N,t,val+1);
    }
    cout<<getSum(st,N,0,N-1);
}


Measured memory_bytes: 22780
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<b;++i) 
#define ROF(i,a,b) for(int i=a;i>=b;--i)
#define vi vector<int>
#define vlli vector<long long int>
#define pb push_back
#define mp make_pair
#define all(c)  ((c).begin()), ((c).end())
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	string s;
	cin>>s;
	int c=0;
	FOR(i,0,s.size()){
		if(s[i]=='2')
			c++;
	}
	cout<<c<<"\n";
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
    int a, b, c, x;
    cin >> a;
    cin >> b;
    cin >> c;
    cin >> x;

    int amount = 0;
    for (int i = 0; i <= a; i++) {
        for (int j = 0; j <= b; j++) {
            for (int k = 0; k <= c; k++) {
                if (500 * i + 100 * j + 50 * k == x) {
                    amount++;
                }
            }
        }
    }
    cout << amount << endl;
    return 0;
}


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

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

    vector<int> v(n), c(n);
    for(int i=0; i < n; i++) cin >> v[i];
    for(int i=0; i < n; i++) cin >> c[i];

    int z = 0;
    for(int i=0; i < n; i++) {
        if(v[i] > c[i]) z += v[i] - c[i];
    }
    cout << z << endl;
}



Measured memory_bytes: 256
S = input()
X = [1] * len(S)

for i in range(len(S)):
    if S[i] == 'R' and S[i+1] == 'R':
        X[i+2] += X[i]
        X[i] = 0

for i in reversed(range(len(S))):
    if S[i] == 'L' and S[i-1] == 'L':
        X[i-2] += X[i]
        X[i] = 0

print(' '.join([str(_) for _ in X]))


Measured memory_bytes: 10484
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N =2e5+10 , M = 5e5+10, OO = 0x3f3f3f3f ,  MOD = 1e9+7;
const double EPS = 1e-3;
#define M_PI 3.14159265358979323846
#define clr(arr,val) memset(arr , val , sizeof (arr))
#define loop(i,n) for(int i = 0;i < int(n);i++)
#define rloop(i,n) for(int i = int(n)-1;i >= 0;i--)
#define range(i,a,b) for(int i = int(a);i <= int(b);i++)
#define pb push_back
#define F first
#define S second
#define all(v) ((v).begin()) , ((v).end())
#define sz(v)  ((int)((v).size()))
typedef pair <int,int> pii ;
typedef vector < pii > vii ;
int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
//int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
//int dx[6]={2,1,-1,-2,-1,1};int dy[6]={0,1,1,0,-1,-1}; //Hexagonal Direction
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
 
 

 
 
int main(){
 
 
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);cout.tie(0);
 
    string s , t, ans;


    cin >> s >> t;
    ans = t+s;
    cout << ans << "\n";




 
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define MOD 998244353
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
	int x = 0, p = 1; 
	char c = getchar();	
	while (c <= 32) c = getchar();
	if (c == 45) p = -p, c = getchar();
	while (c > 32) x = x * 10 + c - 48, c = getchar();
	return x * p;
}
using namespace std;
//ruogu_alter
const int N = 1e5 + 5;
int n, d[N], mx, c[N];
//
int main() {
	n = getint();
	rep(i, n) d[i] = getint();
	if (d[0]) return !printf("%d\n", 0);
	rep(i, n) {
		mx = max(mx, d[i]);
		if(i && !d[i]) return !printf("%d\n", 0);
		c[d[i]]++;
	}
	ll res = 1;
	for(int i = 1; i <= mx; i++) rep(j, c[i]) {
		(res *= c[i - 1]) %= MOD;
	}
	cout << res;
	return 0;
}


Measured memory_bytes: 1024
from sys import stdin
from collections import defaultdict
import itertools
 
d = defaultdict(list)
N = int(stdin.readline().rstrip())
p = [[0,1] for i in range(N)]
 
for i in range(N):
    A = int(stdin.readline().rstrip())
    for j in range(A):
        x,y = [int(x) for x in stdin.readline().rstrip().split()]
        d[i].append((x,y))
ans = 0
 
for ind,i in enumerate(itertools.product(*p)):
    cnt = 0
    flag = True
    for m in range(N):
        if i[m] == 1:
            for j,k in d[m]:
                if i[j-1] != k:
                    flag = False
            if flag:
               cnt += 1
        else:
            continue
    if flag:
       ans = max(ans,cnt)
    cnt = 0
print(ans)

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

using namespace std;
using ll = long long;

int main() {
    ll S;
    ll N = 1;
    string Ss;
    cin >> Ss;
    S = stoll(Ss);
    while (S/(ll)pow(10,N)) {
        //cout << pow(10,N) << endl;
        //cout << S/pow(10,N) << endl;
        //cout << N << endl;
        N++;
    }
    //cout << N << endl;
    ll ans = 1000;

    for(int i = 0; i < N-2; i++) {
        ans = min(ans,abs(753 - (S/(int)pow(10,i))%1000));
    }
    cout << ans << endl;




    return 0;
}

Measured memory_bytes: 3964
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(ll i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
#define pb push_back
using namespace std;
using ll=long long;
using ld=long double;
using ch=char;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<ch> vc;
typedef vector<vc> vvc;
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
struct edge{ll to,cost;};
struct edge2{ll from,to,cost;};

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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    string t="CODEFESTIVAL2016";
    ll ans=0;
    rep(i,16){
        if(s[i]!=t[i]){
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3616
#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>

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

using namespace std;
typedef long long ll;

int main() {

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


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

bool isprime(int n){
	if(n==1)return false;
	if(n==2)return true;
	for(int i=2;i<=sqrt(n)+1;i++){
		if(n%i==0)return false;
	}
	return true;
}

int main(void){
	int h;
	cin>>h;
	// int n=h;
	cout<<h<<":";
	int n=h;
	for(int i=2;i<=sqrt(h)+1;i++){
		if(isprime(i)){
			while(n%i==0){
				n/=i;
				cout<<" "<<i;
			}
			if(isprime(n))break;
		}
	}
	if(n!=1)cout<<" "<<n;
	cout<<endl;
	return 0;
}

Measured memory_bytes: 3096
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	ll n; cin >> n;
	cout << (ll)1000 * (n / (ll)500) + (ll)5 * ((n % (ll)500) / (ll)5) << '\n';



}

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

using namespace std;

int main(){
  int n;
  cin >> n;
  
  vector<int64_t> a(n);
  
  int64_t mul = 1;
  for(int i = 0; i < n; i++){
    cin >> a.at(i);
    if(a.at(i) == 0){
      mul = 0;
      cout << mul << endl;
      return 0;
    }
  }
  for(int i = 0; i < n; i++){
    if(a.at(i) <= (1000000000000000000 / mul)){
      mul *= a.at(i);
    }
    else{
      mul = -1;
      break;
    }
  }

  cout << mul << endl;
  
  return 0;
}


Measured memory_bytes: 4052
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long

using namespace std;

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

	if (N >= 1000){
	cout << "ABD" << "\n";

	} else {
	cout << "ABC" << "\n";

	}




	return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;
typedef long long ll;
using namespace std;
const ll mod=1000000007,mod9=1000000009;
template <class T>inline T lcm(T a,T b){return (a*b/__gcd(a,b));}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin>>s; 
    vector<int> v;
    int n=s.length();
    ll ans=0;
    for(int i=0;i<n;i++){
        if(s[i]=='A'){
            v.pb(0);
        }
        else if(s[i]=='B'&& i<n-1&&s[i+1]=='C'){
            v.pb(1);
            i++;
        }
        else{
            v.pb(-1);
        }
    }
    int m=v.size();
    int x=0;
    for(int i=m-1;i>=0;i--){
        if(v[i]==1)x++;
        else if(v[i]==0)ans+=x;
        else x=0;
    }
    cout << ans<<endl;
    return 0;
}



Measured memory_bytes: 1680