akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class AAddtion
    {
        public static void Main(string[] args)
        {
            new AAddtion().Solve(new ConsoleInput(Console.In, ' '));
        }

        public void Solve(ConsoleInput cin)
        {
            // 解答はココに書く
            var n = cin.ReadInt;
            var aList = cin.ReadIntArray(n);
            

            var ans = (aList.Count(x => x%2 !=0))%2 == 0 ? "YES" : "NO";

            WriteLine(ans);

        }
    }
}
public class ConsoleInput
{
    private readonly System.IO.TextReader _stream;
    private char _separator = ' ';
    private Queue<string> inputStream;
    public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
    {
        this._separator = separator;
        this._stream = stream;
        inputStream = new Queue<string>();
    }
    public string Read
    {
        get
        {
            if (inputStream.Count != 0) return inputStream.Dequeue();
            string[] tmp = _stream.ReadLine().Split(_separator);
            for (int i = 0; i < tmp.Length; ++i)
                inputStream.Enqueue(tmp[i]);
            return inputStream.Dequeue();
        }
    }
    public string ReadLine { get { return _stream.ReadLine(); } }
    public int ReadInt { get { return int.Parse(Read); } }
    public long ReadLong { get { return long.Parse(Read); } }
    public double ReadDouble { get { return double.Parse(Read); } }
    public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
    public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
    public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
}

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

using namespace std;

int solve(const int n, const int m, const vector<vector<int>>& a) {
    vector<vector<int>> dp(n, vector<int>(m, 0));
    vector<int> dpc(m, 0);
    int best = 0;
    for (int i = 0; i < n; i++) {
        int dpr = 0;
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 1) {
                dp[i][j] = 0;
                dpc[j] = 0;
                dpr = 0;
            }
            else {
                dpr++;
                dpc[j]++;
                dp[i][j] = 1;
                if (i > 0 && j > 0) {
                    dp[i][j] = max(dp[i][j], min(dp[i - 1][j - 1] + 1, min(dpr, dpc[j])));
                }
                best = max(best, dp[i][j]);
            }
        }  
    }
    return best;   
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> matrix(n, vector<int>(m));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> matrix[i][j];
        }
    }
    
    int ans = solve(n, m, matrix);
    
    cout << ans * ans << endl;
    
    return 0;
}

Measured memory_bytes: 18092
#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int main(void)
{
    int n;
    char w[150][15];

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> w[i];
    }

    for (int i = 0; i < n; i++) {
        if (i != 0 && w[i-1][strlen(w[i-1])-1] != w[i][0]) {
            cout << "No" << endl;
            return 0;
        }
        for (int j = 0; j < i; j++) {
            if (!strcmp(w[i], w[j])) {
                cout << "No" << endl;
                return 0;
            }
        }
    }

    cout << "Yes" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
static const int N=100;

int main(){
    //0 0 ??????????????\??????
    int M[N][N];
    int n,u,k,v;

    cin>>n;

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            M[i][j]=0;

    for(int i=0;i<n;i++){
        cin>>u>>k;
        //??¬??¢???0??????
        u--;
        for(int j=0;j<k;j++){
            cin>>v;
            //??¬??¢???0??????
            v--;
            //??¨u???v?????´????????????
            M[u][v]=1;
        }
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(j)
                cout<<" ";
            cout<<M[i][j];
        }
        cout<<endl;
    }
}

Measured memory_bytes: 3108
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#define llint long long
#define inf 1e18

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

llint n, Q;
llint a[100005], b[100005];
llint a2[100005], b2[100005], dif[100005];
llint Amin[100005], Bmin[100005];
llint add[100005];
const int B = 300;

void calc(llint l, llint r, llint x)
{
	llint bid = l/B, L = bid*B, R = min(n, (bid+1)*B);
	for(int i = l; i <= r; i++) a[i] += x;
	for(int i = L; i < R; i++) a[i] += add[bid];
	add[bid] = 0;
	
	vector<P> vec;
	for(int i = L; i < R; i++){
		vec.push_back(P(a[i]-b[i], i));
	}
	sort(vec.begin(), vec.end());
	
	for(int i = 0; i < vec.size(); i++){
		llint p = L + i;
		dif[p] = vec[i].first;
		a2[p] = a[vec[i].second], b2[p] = b[vec[i].second];
	}
	llint mn = inf;
	for(int i = L; i < R; i++){
		mn = min(mn, b2[i]);
		Bmin[i] = mn;
	}
	mn = inf;
	for(int i = R-1; i >= L; i--){
		mn = min(mn, a2[i]);
		Amin[i] = mn;
	}
}

llint get(llint l, llint r)
{
	llint ret = inf, bid = l/B;
	for(int i = l; i <= r; i++){
		ret = min(ret, max(a[i]+add[bid], b[i]));
	}
	return ret;
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> Q;
	for(int i = 0; i < n; i++) cin >> a[i] >> b[i];
	for(int i = 0; i < n/B; i++) calc(i*B, (i+1)*B-1, 0);
	calc(n/B*B, n-1, 0);
	
	/*for(int i = 0; i < n; i++) cout << a[i] << " "; cout << endl;
	for(int i = 0; i < n; i++) cout << b[i] << " "; cout << endl;
	for(int i = 0; i < n; i++) cout << a2[i] << " "; cout << endl;
	for(int i = 0; i < n; i++) cout << b2[i] << " "; cout << endl;
	for(int i = 0; i < n; i++) cout << dif[i] << " "; cout << endl;
	for(int i = 0; i < n/B; i++) cout << add[i] << " "; cout << endl;*/
	
	llint t, l, r, x;
	for(int q = 1; q <= Q; q++){
		//cout << "Q " << q << endl;
		cin >> t >> l >> r;
		l--, r--;
		llint L = (l+B-1)/B*B, R = r/B*B;
		if(t == 1){
			cin >> x;
			if(l/B == r/B){
				calc(l, r, x);
				continue;
			}
			calc(l, L-1, x);
			calc(R, r, x);
			for(int i = L/B; i < R/B; i++) add[i] += x;
		}
		else{
			llint ans = inf;
			if(l/B == r/B){
				cout << get(l, r) << endl;
				continue;
			}
			ans = min(ans, get(l, L-1));
			ans = min(ans, get(R, r));
			for(int i = L/B; i < R/B; i++){
				llint pos = lower_bound(dif+i*B, dif+(i+1)*B, -add[i]) - dif;
				if(pos < n && pos/B == i) ans = min(ans, Amin[pos]+add[i]);
				if(pos > 0 && (pos-1)/B == i) ans = min(ans, Bmin[pos-1]);
			}
			cout << ans << endl;
		}
	}
	
	return 0;
}


Measured memory_bytes: 8664
N, M = list(map(int, input().split()))

S = []
for i in range(M):
    hoge = list(map(int, input().split()))
    S.append(hoge)

P = list(map(int, input().split()))



foo = [0] * N
hoge = []
def rec(n):
    if (n < 0):
        hoge.append(foo.copy())
        return
    foo[n] = 1
    rec(n-1)
    foo[n] = 0
    rec(n-1)

rec(N-1)

res = 0
for i in hoge:
    flag = True
    for j in range(M):
        tmp = 0
        for k in range(S[j][0]):
            if (i[S[j][k+1]-1]):
                tmp += 1

        if tmp % 2 != P[j]:
            flag = False
            break
    if flag:
        res += 1
    

print(res)

            
            


Measured memory_bytes: 3188
#include <cassert>// c
#include <ctime>
#include <iostream>// io
#include <iomanip>
#include <fstream>
#include <sstream>
#include <vector>// container
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <algorithm>// other
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <random>
#include <regex>

using namespace std;
typedef long long ll;

#define ALL(c) (c).begin(),(c).end()
#define FOR(i,l,r) for(int i=(int)l;i<(int)r;++i)
#define REP(i,n) FOR(i,0,n)
#define FORr(i,l,r) for(int i=(int)r-1;i>=(int)l;--i)
#define REPr(i,n) FORr(i,0,n)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define IN(l,v,r) ((l)<=(v) && (v)<(r))
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end())
//debug
#define DUMP(x)  cerr << #x << " = " << (x)
#define LINE()    cerr<< " (L" << __LINE__ << ")"

int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cout <<fixed <<setprecision(20);

	int N;double W;cin >> N >> W;
	vector<double> ws(N),vs(N);REP(i,N)cin >> ws[i] >> vs[i];


	double res=0;
	vector<pair<double,int> > val;
	REP(i,N){
		if(vs[i]>=0 && ws[i]<=0){
			res+=vs[i];W-=ws[i];
		}
		if(vs[i]<0 && ws[i]<0){
			val.push_back(make_pair(vs[i]/ws[i],i));
			res-=abs(vs[i]);W+=abs(ws[i]);
		}
		if(vs[i]>0 && ws[i]>0){
			val.push_back(make_pair(vs[i]/ws[i],i));
		}
	}

	sort(ALL(val),greater<pair<double,int> >());
	REP(i,val.size()){
		int ind=val[i].second;
		double use=min(1.0,W/abs(ws[ind]));
		res+=use*abs(vs[ind]);
		W-=use*abs(ws[ind]);
	}
	cout << res << endl;
 	return 0;
 }

Measured memory_bytes: 1584
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) > (b) ? (b) : (a))
#define REP(i, n) for(int i = 0; i < n; i++)
typedef long long ll;

int dsc(const void *a, const void *b){
  return *(int *)b - *(int *)a;
}

int
main(int argc, char *argv[])
{
  int n, h, a, amax = -1, b[100001];
  scanf("%d %d", &n, &h);
  REP(i, n){
    scanf("%d %d", &a, &b[i]);
    amax = Max(amax, a);
  }

  qsort(b, n, sizeof(int), dsc);

  int k = 0, ans = 0;
  while(h > 0){
    if(b[k] > amax){
      h -= b[k++];
      ans++;
    }else{
      ans += (h - 1) / amax + 1;
      break;
    }
  }

  printf("%d\n", ans);

  return 0;
}


Measured memory_bytes: 892
def ihf(x):
    lookup = {}
    def printAns(k, s, x):
        lk, ls = lookup[k], lookup[s] 
        if k - s == x:
            print(lk, ls)
        elif k + s == x:
            print(lk, -ls)
        elif -k - s == x:
            print(-lk, ls)
        elif -k + s == x:
            print(-lk, -ls)

    for i in range(5000):
        lookup[i ** 5] = i
    for k in lookup.keys():
        search = (x + k, x - k)
        f2 = 1
        for i, s in enumerate(search):
            if s < 0:
                s = -s
                f2 = -1
            if lookup.get(s, None):
                printAns(k, s, x)
                return

if __name__ == "__main__":
    import sys
    x = int(input())
    ihf(x)


Measured memory_bytes: 9496
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int x;
  int num,count=0;

  cin>>x;
  num=x;

  while(1){
    for(int i=1;i<=num;i++){
      if(num%i==0) count++;
      if(count==3) break;
    }
    if(count==2) break;
    count=0;
    num++;
  }

  cout<<num<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
using namespace std;

bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}

int main(){
  int x;
  cin >> x;
  for(int i=0; i<100000000; i++){
    if(IsPrime(x)==true){
      cout << x;
      return 0;
    }
    x++;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>

using namespace std;

bool sortBySec(const pair<string, int> &a, const pair<string, int> &b) {
    return a.second < b.second;
}

int main() {

    int N;
    cin >> N;

    map<string, int> m;
    for (int i = 0; i < N; ++i) {
        string S;
        cin >> S;
        m[S] += 1;
    }

    vector<pair<string, int>> vs;

    for (pair<string, int> kv:m) {
        vs.emplace_back(kv.first, kv.second);
    }

    sort(vs.begin(), vs.end(), sortBySec);
    reverse(vs.begin(), vs.end());

    long l = vs[0].second;
    vector<string> ss;
    ss.push_back(vs[0].first);
    for (int i = 1; i < vs.size(); ++i) {
        if (vs[i].second == l) {
            ss.push_back(vs[i].first);
        } else {
            break;
        }
    }

    sort(ss.begin(), ss.end());

    for (int i = 0; i < ss.size(); ++i) {
        cout << ss[i] << endl;
    }

    return 0;
}

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

int a[100001];
int dp[100001];
int go(int dp[] , int n)
{
  if(dp[n]!=-1)
    	return dp[n];
  dp[n] = min(go(dp,n-1) + abs(a[n] - a[n-1]),go(dp,n-2) + abs(a[n] - a[n-2]) );
  return dp[n];
}

int main()
{
  int n;
  cin >> n;
  
  for(int i = 0 ;  i < n ; i ++)
    	cin >> a[i];
  memset(dp,-1,sizeof(dp));
  dp[0] = 0;
  dp[1] = abs(a[1] - a[0]);
  if(n>=3)
   	dp[2] = min(abs(a[2] - a[0]),dp[1] + abs(a[2] - a[1]));
  
  cout << go(dp,n-1);
  return  0 ; 
}


Measured memory_bytes: 4096
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>

#include <sstream>
#include <iomanip>

using namespace std;

struct city
{
	int id, p, y;
};

bool comp(city l, city r)
{
	return l.y < r.y;
}

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

	map<int, vector<city>> pref;

	for (int i = 0; i < M; i++)
	{
		int p, y;
		cin >> p >> y;

		pref[p].push_back({ i, p, y });
	}

	vector<string> ans(M);
	for (auto itr = pref.begin(); itr != pref.end(); itr++)
	{
		auto vec = (*itr).second;

		sort(vec.begin(), vec.end(), comp);

		for (int i = 0; i < vec.size(); i++)
		{
			ostringstream ss;
			ss << setw(6) << setfill('0') << vec[i].p;

			ss << setw(6) << setfill('0') << (i + 1);
			
			ans[vec[i].id] = ss.str();
		}
	}

	for (int i = 0; i < M; i++)
	{
		cout << ans[i] << endl;
	}

	return 0;
}

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

int main() {
  int N, A;
  cin >> N >> A;
  
  if (N < 500) {
    if (N <= A) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  } else {
    if (N % 500 <= A) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  }
}

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

const int mod = 998244353;
long long power(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;
}

int main(){

    
    long long n;
    long long ans = 1;
    std::map<long long,long long> um;
    std::cin>>n;
    for(long long i=0;i<n;i++){
        long long tmp;
        std::cin>>tmp;
        um[tmp]++;
        if(i && !tmp)ans = 0;//頂点2~で1との距離が0の場合
        if(!i && tmp)ans = 0;//頂点1が0で無い場合
    }

    for(long long i=1;i<n;i++){
        ans *= power(um[i-1],um[i],998244353);
        ans %= 998244353;
    }

    std::cout<<ans<<std::endl;
}

Measured memory_bytes: 6528
def lscan;gets.split.map(&:to_i);end

n, m = lscan

trig = m.times.map{lscan[1..-1].map{|e| e-1}}
pp = lscan

ans = 0
[0,1].repeated_permutation(n) do |sw|
  
  flg = true
  m.times do |i|
    flg &&= trig[i].map{|t| sw[t]}.reduce(:+)%2 == pp[i]
  end
  ans += 1 if flg
end

p ans

Measured memory_bytes: 1916
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<iostream>
#include <bitset>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x.begin(), _x.end(), std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
#define vec_unique(_a) _a.erase(std::unique(all(_a)), _a.end());
#define vvec vector<vector<ll>>
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
#define INF 1 << 30
const int mod = 1000000007;
ll power(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x *= x; p /= 2; } else { a *= x; p--; } }return a; }
ll mpower(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x = x * x % mod; p /= 2; } else { a = a * x % mod; p--; } }return a; }
ll c(ll n, ll k) { ll a = 1; rep(i, 1, k) { a *= n - i + 1; a /= i; }return a; }
ll mc(ll n, ll m) { ll k = 1, l = 1; rep(i, n - m + 1, n + 1) k = k * i % mod; rep(i, 1, m + 1) l = l * i % mod; l = mpower(l, mod - 2); return k * l % mod; }
vector<vector<int>> G;
vector<int> f;
int ans, n, m;
void dfs(int v) {
	bool check = true;
	rep(i, 0, n) {
		if (!f[i]) {
			check = false;
			break;
		}
	}
	if (check) {
		ans++; return;
	}
	for (auto next : G[v]) {
		if (f[next])continue;
		f[next] = 1;
		dfs(next);
		f[next] = 0;
	}
}
int main()
{
	int a, b;
	cin >> n >> m;
	G.resize(n);
	f.resize(n, 0);
	rep(i, 0, m) {
		cin >> a >> b;
		a--, b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	f[0] = 1;
	dfs(0);
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 3752
#include <bits/stdc++.h>
#define rep(i, start, end) for (long long i = start; i < end; ++i)
#define repreverse(i, start, end) for (long long i = start; i >= end; --i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define len(x) ((long long)(x).size())
#define lcm(a, b) ((a) / __gcd((a), (b)) * (b))
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vllvll = vector<vll>;
using vc = vector<char>;
using pll = pair<ll, ll>;
template<class T>void print1d(T x,ll n=-1){if(n==-1)n=x.size();rep(i,0,n){cout<<x[i]<<' ';}cout<<'\n';}
template<class T>void print2d(T x,ll r=-1,ll c=-1){if(r==-1)r=x.size();if(c==-1)c=x[0].size();rep(i,0,r)print1d(x[i],c);}
template<class T, class U>bool haskey(T mp, U key) { return mp.find(key) != mp.end(); }
template<class T, class U>bool isin(T el, U container) { return find(all(container), el) != container.end(); }
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; }
template<class T>bool even(T n) { return ! (n & 1); }
template<class T>bool odd(T n) { return n & 1; }
template<class T>ld deg2rad(T deg) { return M_PI * deg / 180.0; }
template<class T>ld rad2deg(T rad) { return 180.0 * rad / M_PI; }
ll intpow(ll a,ll n){ll p=1;while(n){if(n&1)p*=a;a*=a;n>>=1;}return p;} 
const long double pi = M_PI;
const long long big = 1LL << 50;
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;



int main()
{
        ll N;
        cin >> N;
        vll L(N);
        rep(i, 0, N) {
                ll x;
                cin >> x;
                L[i] = x;
        }
        ll ans = 0;
        sort(all(L));
        rep(i, 0, N) {
                rep(j, i+1, N) {
                        rep(k, j+1, N) {
                                ll a = L[i];
                                ll b = L[j];
                                ll c = L[k];
                                if (a == b or b == c or c == a) continue;
                                if (a + b > c and b + c > a and c + a > b) {
                                        ++ans;
                                        //cout << i << j << k << endl;
                                }
                        }
                }
        }
        cout << ans << endl;
}


Measured memory_bytes: 3628
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>

using std::cout;
using std::cin;
using std::endl;
using std::pow;
using std::vector;
using std::string;

int fun(int x,int y,int z){
    return x*x+y*y+z*z+x*y+y*z+z*x;
}

int main(){
    int L,R,d,count=0;
    cin >> L >> R >> d;
    for(int i=L;i<=R;i++){
        if(i % d == 0) count++;
    }
    cout << count;
}

Measured memory_bytes: 3584
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>
#include <chrono>
#include <ctime>
#include <bitset>
#include <iterator>
#include <cmath>
#include <stack>
#include <random>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define debug(x) cerr << #x << ": " << x << ", "
#define debugln(x) cerr << #x << ": " << x << '\n'

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

using namespace std;
using ll = long long;
using P = pair<ll, ll>;

constexpr ll mod = 1e9+7;
const double PI = acos(-1.0);
mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count());

int extgcd(int a, int b, int &x, int &y) {
  int d = a;
  if (b != 0) {
    d = extgcd(b, a%b, y, x);
    y -= (a/b)*x;
  } else {
    x = 1;
    y = 0;
  }
  return d;
}

// m is a large prime integer. Usually 1000000007 is used.
int mod_inverse(int a, int m) {
  int x, y;
  extgcd(a, m, x, y);
  return (m + x%m)%m;
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, x; cin >> n >> x;
  vector<int> s(n);
  rep(i, n) cin >> s[i];
  sort(s.begin(), s.end());

  ll fact = 1;
  for(int i=2; i<n; i++) {
    fact *= i;
    fact %= mod;
  }
  vector<ll> modinv(n);
  for(int i=1; i<n; i++) {
    modinv[i] = mod_inverse(i, mod);
  }

  unordered_map<int, ll> mp;
  unordered_map<int, ll> mp2;

  rep(i, n) {
    auto r = x%s[i];
    mp[r] += fact;
    mp[r] %= mod;
  }

  bool flag = true;
  while(flag) {
    flag = false;
    for(auto e: mp) {
      auto r = e.first;
      auto it = upper_bound(s.begin(), s.end(), r);
      auto k = distance(s.begin(), it);
      if (k==0) {
        mp2[e.first] += mp[e.first];
        mp2[e.first] %= mod;
      }
      for(int i=0; i<k; i++) {
        flag = true;
        auto pos = r%s[i];
        mp2[pos] += e.second * modinv[k];
        mp2[pos] %= mod;
      }
    }
    mp = mp2;
    mp2.clear();
  }

  ll ans = 0;
  for(auto e: mp) {
    ans += e.second*e.first;
    ans %= mod;
  }
  cout << ans << endl;
}


Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
int n, a[500010], b[500010], cnt = 0;
void merge(int l, int mid, int r){
	int n1 = mid - l, n2 = r - mid;
	int T = r - l, i = 0, j = 0, now = 0;
	while(T--){
		cnt++;
		if(i == n1){
			b[now++] = a[mid + j];
			j++;
		}
		else if(j == n2){
			b[now++] = a[l + i];
			i++;
		}
		else if(a[l + i] < a[mid + j]){
			b[now++] = a[l + i];
			i++;
		}
		else{
			b[now++] = a[mid + j];
			j++;
		}
		
	}
	for(int i = 0; i < now; i++) a[l + i] = b[i];
	//for(int i = 0; i < now; i++) printf("%d ", b[i]);
	//printf("\n");
}
void MergeSort(int l, int r){
	if(l + 1 >= r) return;
	int mid = (l + r) / 2;
	MergeSort(l, mid);
	MergeSort(mid, r);
	merge(l, mid, r);
}
int main()
{
	scanf("%d", &n);
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
	MergeSort(0, n);
	for(int i = 0; i < n - 1; i++) printf("%d ", a[i]);
	
	printf("%d\n%d\n", a[n-1], cnt);
	return 0; 
}


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



int main(){
  ll n,x;
  cin >> n >> x;
  vector<ll> a(n);
  ll cal=0;
  for(ll i=0;i<n;++i){
    cin >> a[i];
    cal+=a[i];
  }
  ll ans=0;
  if(a[0]>x){
    a[0]=x;
  }
  ans=a[0];
  for(ll i=1;i<n;++i){
    if(a[i-1]+a[i]>x){
      a[i]=x-a[i-1];
    }
    ans+=a[i];
  }
  ans=cal-ans;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define pb push_back
#define Int long long
using namespace std;

const int MAXN=500005;
const long MOD=(long)(1e9+7);
vector<int> adj[MAXN];
vector<pair<int,int>> G[MAXN];

Int N,M,K;
Int B,C,H,W;
Int X,Y,Z;
vector<Int> A;

Int ceilS(Int x,Int y){
    return (x+y-1)/y;
}
using D=long double;

Int perform(Int x){
    return (x*(x+1))/2LL;
}



int main()
{
   string S,T;
   cin>>S>>T;
   cin>>N>>M;
   string x;cin>>x;
   if(x==S){
       cout<<N-1<<" "<<M<<"\n";
   }
   else{
       cout<<N<<" "<<M-1<<"\n";
   }
   
    
}

Measured memory_bytes: 26984
#include <bits/stdc++.h>
#define ss second
#define ff first
#define all(x) x.begin(), x.end()

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

const int oo = 1e9 + 7;
const ll mod = 1e9 + 7, maxn = 1000001;
const double PI = acos(-1);
bitset<1000010> isprime;
vector<int> primos;
int v[maxn];

void sieve(){
    isprime.set();
    isprime[0] = isprime[1] = 0;
    primos.push_back(2);

    for (int i=3; i*i<maxn; i+=2){
        if (isprime[i]){
            for (int j=i*i; j<maxn; j+=(2*i)){
                isprime[j] = 0;
            }
        }
    }

    for (int i=3; i<maxn; i+=2){
        if (isprime[i]) primos.push_back(i);
    }
}

ll fexp(ll base, ll p){
    ll ans = 1;
    while (p){
        if (p&1){
            ans = (ans*base)%mod;
        }
        p = p >> 1;
        base = (base*base)%mod;
    }
    return ans;
}

int main (){
    ios_base::sync_with_stdio(false);
    ll n, ans = 0, lcm = 1;
    sieve();
    cin >> n;

    int pn = primos.size();
    vector<ll> pot(pn, 0);

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

    for (auto x: v){
        for (int i=0; i<pn; i++){
            if (isprime[x] and x&1) {
                int pos = lower_bound(all(primos), x) - primos.begin();
                pot[pos] = max(1LL, pot[pos]);
                break;
            }
            ll val = primos[i], power = 0;
            if (val > x) break;
            while (x%val == 0) x/=val, power++;
            pot[i] = max(pot[i], power);
        }
    }

    for (int i=0; i<pn; i++){
        lcm = (lcm * fexp(primos[i], pot[i]))%mod;
    }

    for (int i=0; i<n; i++){
        ans = (ans + lcm*fexp(v[i], mod-2))%mod;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1528
n = gets.chomp.to_i
d_list = gets.chomp.split.map(&:to_i)

res = 0
(0..(n-2)).each do |i|
  (1..(n-i-1)).each do |j|
    res += d_list[i] * d_list[i+j]
  end
end

puts res


Measured memory_bytes: 1788
#include <algorithm>
#include <functional>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <climits>

#define all(c) (c).begin(), (c).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)
#define fr first
#define sc second

const int INF=100000000;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
using namespace std;
typedef pair<int ,int > P;
typedef long long ll;

bool binary_search(int *a,int n,int x) {
    int l=0,r=n;
    while(r-l>0) {
        int mid = (l+r)/2;
        if(a[mid] < x) l=mid+1;
        else if(a[mid] == x) return true;
        else r=mid;
    }
    // cout<<l<<","<<r<<endl;
    return false;
}

int n;
int S[100005];
int q;
int main() {
    int ans=0;
    cin>>n;
    rep(i,n) cin>>S[i];
    cin>>q;
    rep(i,q) {
        int t;
        cin>>t;
        if(binary_search(S,n,t)) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1548
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin.bytes().map(|c| c.expect("faild") as char).skip_while(|c| c.is_whitespace()).take_while(|c| !c.is_whitespace()).collect();
    token.parse().ok().expect("faild parse")
}
fn main(){
    let w: i32 = read();
    let h: i32 = read();
    let x: i32 = read();
    let y: i32 = read();
    let r: i32 = read();
    if x - r >= 0 && x + r <= w && y - r >=0 && y + r <= h{
        println!("Yes");
    }else{
        println!("No");
    }
}


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

long long a[200000];
long long b[200000];

int main(void) {
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        scanf("%lld %lld",&a[i],&b[i]);
    }
    sort(a,a+n);
    sort(b,b+n);
    if (n%2==1) {
        printf("%lld",b[n/2]-a[n/2]+1);
    }
    else {
        printf("%lld",b[n/2]+b[n/2-1]-a[n/2]-a[n/2-1]+1);
    }
}

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

int main(){

    int n, m;
    cin >> n >> m;

    vector<vector<int>> road(n);

    for (int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        road.at(a).push_back(b);
        road.at(b).push_back(a);
    }

    for (int i=0; i<n; i++){
        cout << road.at(i).size() << endl;
    } 
    return 0;
}

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

int A[128], N;
int main(){
  A[0] = 1;
  while(cin >> N && N > 0){
    for(int i=1; i<=32; i++){
      A[i] = A[i-1];
      if(i>=2) A[i] += A[i-2];
      if(i>=3) A[i] += A[i-3];
    }
    ll days = (A[N]+9) / 10;
    ll ans = (days+364) / 365;
    cout << ans << endl;
  }
  return 0;
}



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

const int MAX = 105;
const int WHITE = 0;
const int GRAY = 1;
const int BLACK = 2;
const int INFTY = 1 << 21;
int n;
int m[MAX][MAX];
int color[MAX];
int d[MAX];
int p[MAX];

int prim() {
  for (int i = 0; i < n; i++) {
    d[i] = INFTY;
    p[i] = -1;
  }
  d[0] = 0;
  p[0] = -1;

  while (true) {
    int u {-1};
    int min_cost = INFTY;
    for (int i = 0; i < n; i++) {
      if (color[i] != BLACK && d[i] < min_cost) {
        min_cost = d[i];
        u = i;
      }
    }
    if (u == -1) break;
    color[u] = BLACK;
    for (int v = 0; v < n; v++) {
      if (color[v] != BLACK && m[u][v] < d[v]) {
        d[v] = m[u][v];
        p[v] = u;
        color[v] = GRAY;
      }
    }
  }

  int sum {0};
  for (int i = 0; i < n; i++) {
    if (p[i] != -1) sum += m[i][p[i]];
  }
  return sum;
}

int main() {
  cin >> n;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      int e; cin >> e;
      m[i][j] = (e == -1) ? INFTY : e;
    }
  }
  cout << prim() << endl;
}



Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false) ; cin.tie(NULL) ; cout.tie(NULL);
#define int long long
#define pi pair<int,int>
#define ff first
#define ss second
#define pb push_back
#define mod 1000000007
#define vi vector<int >

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

cout<<ceil(n/1000.0) * 1000 - n<<endl;

}

Measured memory_bytes: 3812
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<map>
#include<queue>


using namespace std;
#define mod 1000000007
#define ll long long 

ll n, k;

ll arr[29][29];
ll dp[22][(1<<22)];



ll solve(ll idx, ll mask) {

	if(idx == n)
		return mask == (1 << n) - 1;

	if(dp[idx][mask] != -1)
		return dp[idx][mask];

	ll ans = 0;
	ll new_mask;

	for(int i = 0; i < n; i++) {
		if(!(mask&(1<<i)) && arr[idx][i]) {
			
			new_mask = mask | ( 1 << i);
			ans += solve(idx + 1, new_mask);
			ans %= mod;
		}
	}

	return dp[idx][mask] = ans;
}


int main() {
	memset(dp, -1, sizeof(dp));
	cin>>n;
    for(int i = 0; i < n; i++) {
    	for(int j = 0; j < n; j++) {
 			scanf("%lld", &arr[i][j]);   		
    	}
    }
    cout<<solve(0, 0)<<endl;
}

Measured memory_bytes: 721152
class NormalInput {
  input: string[];
  pointer: number;
  constructor(raw: string) {
    this.input = raw.split(/ |\n/);
    this.pointer = 0;
  }
  int = (): number => {
    const ret = parseInt(this.input[this.pointer], 10);
    this.pointer++;
    return ret;
  };
  str = (): string => {
    const ret = this.input[this.pointer];
    this.pointer++;
    return ret;
  };
  strs = (length: number): string[] => {
    let ret: string[] = [];
    for (let i = 0; i < length; i++) {
      ret.push(this.str());
    }
    return ret;
  };
  ints = (length: number): number[] => {
    let ret: number[] = [];
    for (let i = 0; i < length; i++) {
      ret.push(this.int());
    }
    return ret;
  };
}
function rep(n: number) {
  let a = [];
  for (let i = 0; i < n; i++) a.push(i);
  return a;
}
function naive(A: number[]) {
  while (A.length > 1) {
    console.log(A.join(""));
    A = scan(A, 1);
  }
  console.log(A[0]);
}
function scan(A: number[], step: number) {
  let ret = [];
  for (let i = 0; i < A.length - step; i++) {
    ret.push(Math.abs(A[i] - A[i + step]));
  }
  return ret;
}
function maxPowerOf2Div(n: number): number {
  if (n == 0) throw "aaaaaaaaaaaa";
  if (n % 2 == 0) return maxPowerOf2Div(n / 2) * 2;
  else return 1;
}
function solve(A: number[]): number {
  const size = A.length - 1;
  if (size == 0) return A[0];
  const step = maxPowerOf2Div(size);
  return solve(scan(A, step));
}
function Main({ int, str, strs, ints }: NormalInput) {
  const N = int();
  const _A = str();
  let A = [];
  for (let i = 0; i < N; i++) A.push(_A[i] == "1" ? 0 : _A[i] == "2" ? 1 : 2);
  // naive(A);
  if (A.some(a => a == 1)) {
    // 0(2), 1
    console.log(solve(A) % 2);
  } else {
    // 0, 2
    A = A.map(a => a / 2);
    // 0, 1
    console.log(solve(A) * 2);
  }
}

//DO NOT EDIT
Main(new NormalInput(require("fs").readFileSync("/dev/stdin", "utf8")));


Measured memory_bytes: 255884
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include <cmath>
#include <limits>
#include <iostream>
using namespace std;
#define INF 100000
#define MAX 100000
#define MOD 1000000007
typedef long long ll;
typedef pair<int,int> P;
typedef pair< pair<int,int>, int> p; 
#define bit(n,k) ((n>>k)&1) /*nのk bit目*/

int main(){
    int N;
    cin>>N;
    bool flag=false;
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
            if(i*j==N) flag=true;
        }
    }
    if(flag) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}



Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<string>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
#define PI acos(-1)
#define pb push_back
#define all(x) x.begin(),x.end()
#define INF 0x3f3f3f3f
#define dd(x) cout<<#x<<" = "<<x<<","
#define de(x) cout<<#x<<" = "<<x<<"\n"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int main()
{
	int h1,m1,h2,m2,k;
	scanf("%d%d%d%d%d",&h1,&m1,&h2,&m2,&k);
	if(m1>m2){
		h1++;
		m2+=60;
	}
	int tot=(h2-h1)*60+m2-m1;
	printf("%d",tot-k);
}


Measured memory_bytes: 3792
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF 0x3f3f3f3f
#define NIL (-1)
//#define M 1000003
#define M 1046527
using namespace std;
int T[M+1];
void trans(char *s){
    for(int i = 0; i < strlen(s); i++){
        if(s[i] == 'A') s[i] = '4';
        else if(s[i] == 'C') s[i] = '1';
        else if(s[i] == 'G') s[i] = '2';
        else if(s[i] == 'T') s[i] = '3';
    }
}
int stringToInt(char s[]){
    int t = 0;
    int p = 1;
    for(int i = strlen(s)-1; i >= 0; i--){
        t += (s[i]-'0')*p;
        p *= 5;
    }
    return t;
}
int h1(int a){
    return (int)(a % M);
}
int h2(int a){
    return 1+(int)(a % (M-1));
}
int h(int a, int i){
    return (h1(a) + i * h2(a))%M;
}
 
void insert(int c){
    int i = 0;
    while(true){
        int temp = h(c, i);
        if(T[temp] == NIL){
            T[temp] = c;
            return ;
        }
        else{
            i++;
        }
    }
}
int find(int d){
    int i = 0;
    while(true){
        int temp = h(d, i);
        if(T[temp] == NIL){
            return -1;
        }
        else if(T[temp] == d){
            return 1;
        }
        else{
            i++;
            if(i >= M) return -1;
        }
    }
}
int main(){
    for(int i = 0; i < M; i++) T[i] = NIL;
 
    int n;
    scanf("%d", &n);
    while(n--){
        char a[10], b[14];
        scanf("%s %s", a, b);
        if(a[0] == 'i'){
            trans(b);
            int c = stringToInt(b);
            insert(c);
        }
        else{
            trans(b);
            int d = stringToInt(b);
            if(find(d) != -1){
                printf("yes\n");
            }
            else{
                printf("no\n");
            }
        }
    }
 
    return 0;
}


Measured memory_bytes: 6752
MOD = int(1e9+7)

def fast_power(b, e):
    res = 1
    while e > 0:
        if e % 2 == 1:
            res = res * b % MOD
        b = b * b % MOD
        e >>= 1
    return res

def mod_inverse(n):
    return fast_power(n, MOD-2)
def mul(x, y):
    return ((x % MOD) * (y % MOD) % MOD + MOD) % MOD
def multiply(x, y, z):
    return mul(mul(x, y), z)

def nCr(n, r):
    if r == 0:
        return 1
    fac = [1] * (n+1)
    for i in range(1, n+1):
        fac[i] = fac[i-1] * i % MOD
    # n! / (r! * (n-r)!)
    return multiply(fac[n], mod_inverse(fac[r]), mod_inverse(fac[n-r]))

x, y = map(int, input().split())
n = (2*x-y) // 3
m = (2*y-x) // 3
if min(n, m) < 0 or (x+y)%3 != 0:
    print(0)
    exit()
print(nCr(m+n, n))


Measured memory_bytes: 43760
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
const int INF = 2147483647;//int max
const int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;


int main() {
    int n,k;
    cin >> n >> k;
    int res = 1;
    rep(i,n){
        if(res + k < res*2)res += k;
        else res *= 2;
    }
    cout << res << endl;
    return 0;
}
/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

import static java.lang.System.out;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] one = br.readLine().split(" ");
        int n = Integer.parseInt(one[0]);
        int k = Integer.parseInt(one[1]);
        String[] two = br.readLine().split(" ");
        int[] heights = new int[n];
        for (int i = 0; i < n; i++) {
            heights[i] = Integer.parseInt(two[i]);
        }

        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 1; i < n; i++) {
            for (int j = Math.max(i - k, 0); j < i; j++) {
                dp[i] = Math.min(dp[i], dp[j] + Math.abs(heights[i] - heights[j]));
            }
        }
        out.println(dp[n - 1]);
    }
}

Measured memory_bytes: 34656
#include<iostream>
#include<algorithm>
#include<utility>

using namespace std;

int main(){

	int a, b, c;
	cin >> a >> b >> c;

	int cnt = 0;
	for (int i = a; i <= b; i++){
		if (c % i == 0) cnt++;
	}

	cout << cnt << "\n";
}

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

typedef long long ll;
const int mod = 1e9 + 7;

ll A(ll x, ll y) {
	if (x < 0 || y < 0 || x < y) return 0;
	ll res = 1;
	for (ll i = x - y + 1; i <= x; i++) {
		res = res * i % mod;
	}
	return res % mod;
}

ll C(ll x, ll y) {
	if (x < 0 || y < 0 || x < y) return 0;
	ll res = 1;
	for (ll i = x - y + 1; i <= x; i++) {
		res = res * i;
	}
	for (ll i = 1; i <= y; i++) {
		res /= i;
	}
	return res % mod;
}

int main() {
	ll n, m;
	cin >> n >> m;
	if (n < m) swap(n, m);
	cout << A(m, m) * A(n, n) * C(n + 2 - m, m + 1 - n) % mod << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, begin, end) for(ll i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(ll i=(begin)-1;i>=(end);i--)
#define IREP(i, n) IFOR(i,n,0)
#define SORT(a) sort(a.begin(), a.end())
#define ISORT(a) sort(a.begin(), a.end(),greater<ll>())
#define REVERSE(a) reverse(a.begin(), a.end())
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) cout << #v << "=("; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << ")" << endl;
#define mdebug(m) cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;}
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)

#define ll long long
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define INF 1000000000000000000

using vec = vector<ll>;
using mat = vector<vec>;
using Pii = pair<ll, ll>;
using PiP = pair<ll, Pii>;
using PPi = pair<Pii, ll>;
using bvec = vector<bool>;
using Pvec = vector<Pii>;


template<typename T> void readv(vector<T> &a) { REP(i, a.size()) cin >> a[i]; }
void readv_m1(vector<int> &a) { REP(i, a.size()) {cin >> a[i]; a[i]--;} }

ll mod = 1000000007;

int main()
{

	ll s;
	cin >> s;

	ll maxm = 1000001;
	vec count(maxm, 0);
	ll counttot = 0;
	while (true) {
		count[s]++;
		counttot++;
		if (count[s] == 2) break;
		if (s % 2 == 0) s /= 2;
		else s = 3 * s + 1;

	}
	cout << counttot << endl;
	return 0;
}

Measured memory_bytes: 8064
#include <string>
#include <sstream>
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <functional>
#include <map>
#include <climits>
#include <queue>

using namespace std;

#define ull unsigned long long

class Main {
public:
	ull minNum(vector<ull> as, vector<ull> bs) {
		ull minA = 1;
		ull minB = 1;
		for (ull i = 0;i < as.size();i++) {
			ull ratio = (ull)max(minA/as[i] + (minA%as[i]!=0), minB / bs[i] + (minB%bs[i]!=0));
			minA = as[i] * ratio;
			minB = bs[i] * ratio;
		}

		return minA + minB;
	}
};


int main()
{
	Main m;
	ull n;
	vector<ull> as;
	vector<ull> bs;

	cin >> n;
	for (ull i = 0;i < n;i++) {
		ull inpA, inpB;
		cin >> inpA >> inpB;
		as.push_back(inpA);
		bs.push_back(inpB);
	}

	cout << m.minNum(as,bs) << endl;

    return 0;
}



Measured memory_bytes: 256
a,b,c = map(int,input().split())

if a%2==b%2==c%2:
	x = max(a,b,c)
	print((3*x-a-b-c)//2)
elif a%2==b%2!=c%2:
	x = max(a+1,b+1,c)
	print((3*x-a-b-c-2)//2+1)
elif a%2!=b%2==c%2:
	x = max(a,b+1,c+1)
	print((3*x-a-b-c-2)//2+1)
elif a%2==c%2!=b%2:
	x = max(a+1,b,c+1)
	print((3*x-a-b-c-2)//2+1)




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

using namespace std;

#define int long long
#define endl '\n'
#define MOD 1000000007
#define maxn 100010

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

    string s;
    cin >> s;

    int k;
    cin >> k;

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '1' and k != i + 1)
            continue;
        return cout << s[i] << endl , 0;
    }
}

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

using namespace std;
int L[205];
int main()
{
	int N;
	int sum=0;
	int min;
	while(~scanf("%d",&N))
	{
		for(int i=0;i<2*N;i++)
		{
			cin>>L[i];
		}
		sort(L,L+2*N);
		
		for(int j=0;j<2*N;j=j+2)
		{
			min=L[j]<L[j+1] ? L[j] : L[j+1];
			sum=sum+min;
		}
		cout<<sum<<endl;
	}
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;
int main(){
	int n,m,i;
	cin>>n>>m;
	pair<int,string> a[100005];
	for(i=0;i<m;i++)
		cin>>a[i].first>>a[i].second;
	//sort(a,a+n);
	int p=0,acc=0;
	int ac[100005]={0},pt[100005]={0};
	for(i=0;i<m;i++)
	{
		int pb=a[i].first;
		//cout<<pb<<a[i].second<<endl;
		
		if(ac[pb]==0)
		{
			//cout<<"in if \n";
			//cout<<pb<<a[i].second<<endl;
			if(a[i].second=="AC")
				ac[pb]=1;
			else pt[pb]++;
		}
	}	
	/*for(i=1;i<=n;i++)
		cout<<"pb "<<i<<" ac "<<ac[i]<<" pt "<<pt[i]<<endl;*/
	for(i=1;i<=n;i++)
	{
		if(ac[i])
		{	acc++;
			p+=pt[i];
		}
	}
	cout<<acc<<" "<<p<<endl;
}

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

using namespace std;

int main() {
 int n, ctr = 0;
  cin>>n;
  string str, sam = "ABC";
  cin>>str;
  for(int i = 0;  i <= str.length() - 3; i++) {
  	if(sam == str.substr(i, 3))
      ctr++;
  }
  cout<<ctr;
  return 0;
}

Measured memory_bytes: 256
n, m, c = map(int, input().split())
b_lst = list(map(int, input().split()))
ans = 0
for _ in range(n):
    a_lst = list(map(int, input().split()))
    tmp = c
    for a, b in zip(a_lst, b_lst):
        tmp += a * b
    if tmp > 0:
        ans += 1
print(ans)

Measured memory_bytes: 3064
#include<stdio.h>

int main(void)
{
	int s,m=1;
	int a[1000001];
	scanf("%d",&s);
	a[s]=1;
	while(s!=0){
		if(s%2==0)
			s=s/2;
		else
			s=s*3+1;
		m++;
		if(a[s]==0)
			a[s]=1;
		else{
			printf("%d",m);
			return 0;
		}
	}
	return 0;
}
		

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
using namespace std;
#define ll signed long long

int main() {
  ll K, N;
  cin >> K >> N;
  ll A[N];
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
  }

  ll m = A[0] + K - A[N-1];
  for (int i = 1; i < N; ++i) {
    m = max(m, A[i] - A[i - 1]);
  }

  cout << K - m << endl;

  return 0;
}


Measured memory_bytes: 1792
from random import randint
import sys
input = sys.stdin.readline
INF = 9223372036854775808


def calc_score(D, C, S, T):
    """
    開催日程Tを受け取ってそこまでのスコアを返す
    コンテストi 0-indexed
    d 0-indexed
    """
    score = 0
    last = [0]*26  # コンテストiを前回開催した日
    for d, t in enumerate(T):
        last[t] = d + 1
        for i in range(26):
            score -= (d + 1 - last[i]) * C[i]
        score += S[d][t]
    return score


def update_score(D, C, S, T, score, ct, ci):
    """
    ct日目のコンテストをコンテストciに変更する
    スコアを差分更新する

    ct: change t 変更日 0-indexed
    ci: change i 変更コンテスト 0-indexed
    """
    last = [0]*26  # コンテストiを前回開催した日
    for d in range(ct):
        last[T[d]] = d + 1
    prei = T[ct]  # 変更前に開催する予定だったコンテストi
    score -= S[ct][prei]
    score += S[ct][ci]
    for d in range(ct, D):
        if d != ct and T[d] == prei:
            break
        score += C[prei]*(d + 1 - ct - 1)
        score -= C[prei]*(d + 1 - last[prei])
    for d in range(ct, D):
        if d != ct and T[d] == ci:
            break
        score += C[ci]*(d + 1 - last[ci])
        score -= C[ci]*(d + 1 - ct - 1)
    T[ct] = ci
    return score, T


def evaluate(D, C, S, T, k):
    """
    d日目終了時点での満足度を計算し，
    d + k日目終了時点での満足度の減少も考慮する
    """
    score = 0
    last = [0]*26
    for d, t in enumerate(T):
        last[t] = d + 1
        for i in range(26):
            score -= (d + 1 - last[i]) * C[i]
        score += S[d][t]

    for d in range(len(T), min(len(T) + k, D)):
        for i in range(26):
            score -= (d + 1 - last[i]) * C[i]
    return score


def greedy(D, C, S):
    Ts = []
    for k in range(5, 13):
        T = []  # 0-indexed
        max_score = -INF
        for d in range(D):
            # d+k日目終了時点で満足度が一番高くなるようなコンテストiを開催する
            max_score = -INF
            best_i = 0
            for i in range(26):
                T.append(i)
                score = evaluate(D, C, S, T, k)
                if max_score < score:
                    max_score = score
                    best_i = i
                T.pop()
            T.append(best_i)
        Ts.append((max_score, T))
    return max(Ts, key=lambda pair: pair[0])


def local_search(D, C, S, score, T):
    for _ in range(800):
        ct = randint(0, D-1)
        ci = randint(0, 25)
        ori = T[ct]
        T[ct] = ci
        new_score = calc_score(D, C, S, T)
        # 差分更新がバグってそう
        if score < new_score:
            score = new_score
        else:
            T[ct] = ori

    return T


if __name__ == '__main__':
    D = int(input())
    C = [int(i) for i in input().split()]
    S = [[int(i) for i in input().split()] for j in range(D)]
    init_score, T = greedy(D, C, S)
    T = local_search(D, C, S, init_score, T)
    for t in T:
        print(t+1)


Measured memory_bytes: 84196