akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
using namespace std;

int main(){

  string S, Y;
  getline(cin, S);
  Y = "2019/04/30";

  for(int i=0; i<S.size()-1; i++){
    if(S[i] > Y[i]){
      cout << "TBD" << endl;
      return 0;
    }
  }

  cout << "Heisei" << endl;

  return 0;
}


Measured memory_bytes: 256
from collections import deque

N, K = map(int, input().split())
A = list(map(int, input().split()))
AS = sum(A)


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 7, 61] if n < 1 << 32 else [2, 3, 5, 7, 11, 13, 17] if n < 1 << 48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
                                                                                     31, 37]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = y * y % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1


def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g):
                return g
            elif isPrimeMR(n // g):
                return n // g
            return findFactorRho(g)


def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += i % 2 + (3 if i % 3 == 1 else 1)
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret


def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p] + 1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret, reverse=True)


def is_ok(n):
    B_ = []
    for a in A:
        b = a % n
        B_.append(b)
    B_.sort()
    B = deque(B_)
    start = 0
    end = 0
    cnt = 0
    while B:
        start += B.popleft()
        while start > end:
            end += n - B.pop()
        end -= start
        cnt += start
        start = 0
        if cnt > K:
            return False
    return True






Can = divisors(AS)

for c in Can:
    if is_ok(c):
        print(c)
        exit()


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

using namespace std;

const int SIZE = 1000005;
const int MOD  = 998244353;

struct Node {
  int x, y;
} a[SIZE];

int n, x[SIZE], y[SIZE], p2[SIZE];

struct Cmpx {
  inline bool operator () (const Node n1, const Node n2) const {
    return n1.x < n2.x;
  }
};

struct Cmpy {
  inline bool operator () (const Node n1, const Node n2) const {
    return n1.y < n2.y;
  }
};

struct BIT {
  int arr[SIZE];

  inline void clear(void) {
    memset(arr, 0, sizeof arr);
    return;
  }

  inline void add(int x) {
    while (x <= n) {
      ++arr[x];
      x += (x & (-x));
    }
    return;
  }

  inline int sum(int x) {
    int ans = 0;
    while (x > 0) {
      ans += arr[x];
      x   -= (x & (-x));
    }
    return ans;
  }
} bit;

int main(void) {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &x[i], &y[i]);
    a[i] = (Node){x[i], y[i]};
  }
  p2[0] = 1;
  for (int i = 1; i <= n; ++i)
    p2[i] = p2[i - 1] * 2 % MOD;
  sort(x, x + n);
  sort(y, y + n);
  for (int i = 0; i < n; ++i) {
    a[i].x = lower_bound(x, x + n, a[i].x) - x + 1;
    a[i].y = lower_bound(y, y + n, a[i].y) - y + 1;
  }
  long long ans = (long long)n * (p2[n] - 1) % MOD;
  bit.clear();
  for (int i = 0; i < n; ++i)
    ans = (ans - 2 * p2[i] - 2 * p2[n - i - 1] + 4 + MOD) % MOD;
  sort(a, a + n, Cmpy());
  for (int i = 0; i < n; ++i) {
    ans = (ans + p2[bit.sum(a[i].x)] - 1 + MOD) % MOD;
    ans = (ans + p2[i - bit.sum(a[i].x)] - 1 + MOD) % MOD;
    bit.add(a[i].x);
  }
  bit.clear();
  for (int i = n - 1; i >= 0; --i) {
    ans = (ans + p2[bit.sum(a[i].x)] - 1 + MOD) % MOD;
    ans = (ans + p2[n - 1 - i - bit.sum(a[i].x)] - 1 + MOD) % MOD;
    bit.add(a[i].x);
  }
  printf("%lld\n", ans);
  return 0;
}


Measured memory_bytes: 18688
sx, sy, tx, ty = gets.strip.split.map(&:to_i)

y_diff = ty-sy
x_diff = tx-sx

upper = 'U'*y_diff + 'R'*x_diff
downer = 'D'*y_diff + 'L'*x_diff

first = upper
second = downer
third = 'LU' + upper + 'RD'
forth = 'RD' + downer + 'LU'

result = first + second + third + forth

puts result


Measured memory_bytes: 1788
module Main
  extend self

  @@memo = {}
  def can_assemble?(elements, index, sum, raw_elements_length)
    unless @@memo[index].nil?
      return @@memo[index][sum] unless @@memo[index][sum].nil?
    else
      @@memo[index] = {}
    end

    if sum == 0
      true
    elsif index >= raw_elements_length
      false
    else
      @@memo[index][sum] = can_assemble?(elements, index + 1, sum, raw_elements_length) || can_assemble?(elements, index + 1, sum - elements[index], raw_elements_length)
      @@memo[index][sum]
    end
  end

  def main
    lines = STDIN.read.split(/\n/)
    lines.shift

    elements = lines.shift.split(' ').map{|s|s.to_i}
    lines.shift

    sums = lines.shift.split(' ').map{|s|s.to_i}
    sums.each{ |sum|
      puts can_assemble?(elements, 0, sum, elements.size) ? 'yes' : 'no'
    }

  end
end

Main::main

Measured memory_bytes: 10600
#include <stdio.h>
#include <stdlib.h>
void print_road1(int a,int b)
{
    int i;
    for(i=1;i<=b;i++)
    {
        printf("U");
    }
    for(i=1;i<=a;i++)
    {
        printf("R");
    }
}

void print_road2(int a,int b)
{
    int i;
    for(i=b;i>=1;i--)
    {
        printf("D");
    }
    for(i=a;i>=1;i--)
    {
        printf("L");
    }
}

int main()
{
    int sx,sy,tx,ty,x,y;
    scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
    x=tx-sx;
    y=ty-sy;
    print_road1(x,y);
    print_road2(x,y);
    printf("L");
    x=x+1;
    y=y+1;
    print_road1(x,y);
    printf("D");
    printf("R");
    print_road2(x,y);
    printf("U");


    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(false), cout << fixed << setprecision(20);
#define int long long
#define gcd __gcd
#define all(x) (x).begin(), (x).end()
template<class T>
bool chmax(T& a, T b){return (a = max(a, b)) == b;}
template<class T>
bool chmin(T& a, T b){return (a = min(a, b)) == b;}
#define _overload(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(...) _overload(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
#define _rev(i, n) revi(i, n, 0)
#define revi(i, a, b) for(int i = (int)(a - 1); i >= (int)(b); i--)
#define rev(...) _overload(__VA_ARGS__, revi, _rev)(__VA_ARGS__)
#define each(i, n) for(auto&& i: n)
const int INF = 1e18, MOD = 1e9 + 7;
signed main() {
    INCANT;
    int y, m, d, Y, M, D, res = 0;
    cin>>y>>m>>d>>Y>>M>>D;
    if(y == Y){
        if(m == M && d == D){
            cout<<0<<endl;
        }else{
            cout<<1<<endl;
        }
    }else if(y > Y){
        if(m == M){
            if(d == D){
                cout<<y - Y<<endl;
            }else if(d > D){
                cout<<y - Y + 1<<endl;
            }else{
                cout<<y - Y<<endl;
            }
        }else if(m > M){
            cout<<y - Y + 1<<endl;
        }else{
            cout<<y - Y<<endl;
        }
    }else{
        if(m == M){
            if(d == D){
                cout<<Y - y<<endl;
            }else if(d > D){
                cout<<Y - y<<endl;
            }else{
                cout<<Y - y<<endl;
            }
        }else if(m > M){
            cout<<Y - y<<endl;
        }else{
            cout<<Y - y + 1<<endl;
        }
    }
}



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

const int MaxFact = pow(10, 9);
int cnt = 0;

void merge(int A[], int left, int mid, int right){
    int n1 = mid - left;
    int n2 = right - mid;
    int L[n1 + 1], R[n2 + 1];
    for(int i=0; i<n1; i++){
        L[i] = A[left + i];
    }
    for(int i=0; i<n2; i++){
        R[i] = A[mid + i];
    }
    L[n1] = MaxFact;
    R[n2] = MaxFact;
    int l=0, r=0;
    for(int i=left; i<right; i++){
        cnt++;
        if(L[l] <= R[r]){
            A[i] = L[l];
            l++;
        } else {
            A[i] = R[r];
            r++;
        }
    }
}
void mergesort(int A[], int left, int right){
    if(left + 1 < right){
        int mid = (left + right) / 2;
        mergesort(A, left, mid);
        mergesort(A, mid, right);
        merge(A, left, mid, right);
    }
}

int main(){
    int n;
    scanf("%d", &n);
    int A[n];
    for(int i=0; i<n; i++){
        scanf("%d", &A[i]);
    }
    mergesort(A, 0, n);
    int j;
    for(j=0; j<n-1; j++){
        printf("%d ", A[j]);
    }
    printf("%d\n", A[j]);
    cout << cnt << endl;


    return 0;
}


Measured memory_bytes: 7208
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <deque>
#define ll long long

using namespace std;

struct task {
	string name;
	int time;
};


int main() {

	int n, q; cin >> n >> q;
	int sum = 0;

	deque<task> t;

	for (int i = 0; i < n; i++) {
		task ts;
		cin >> ts.name >> ts.time;
		t.push_back(ts);
	}

	while (t.size() > 0) {
		task cur = t.front();
		t.pop_front();
		if (cur.time <= q) {
			sum += cur.time;
			cout << cur.name << " " << sum << endl;
		}
		else {
			sum += q;
			cur.time -= q;
			t.push_back(cur);
		}
	}




	return 0;

}





Measured memory_bytes: 6320
#include<bits/stdc++.h>
using namespace std;
long long i,n,b,a[100000001],m;
int main()
{
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>a[i];
        b+=a[i];
    }
    if(b>n)
    {
        cout<<"-1";
        return 0;
    }
    else cout<<n-b;

}


Measured memory_bytes: 3700
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<iomanip>
#include<queue>
using namespace std;

int main() {
    int n, m; cin >> n >> m;
    priority_queue<long long> q;
    for (int i = 0; i < n; i++) {
        int a; cin >> a;
        q.push(a);
    }
    for (int i = 0; i < m; i++) {
        long long v = q.top() / 2;
        q.pop();
        q.push(v);
    }
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans += q.top();
        q.pop();
    }
    cout << ans << endl;
}


Measured memory_bytes: 1400
//Sum of 4 Integers
#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, ans=0;
  while(scanf("%d", &n)!=EOF){
    ans=0;
    for(int a=0; a<=9; a++)
      for(int b=0; b<=9; b++)
        for(int c=0; c<=9; c++)
          for(int d=0; d<=9; d++)
            if(a+b+c+d==n)ans++;
    printf("%d\n", ans);
  }
  return 0;
}

Measured memory_bytes: 1188
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

def dfs(x):
    for i in tree[x]:
        if al[i]<0:
            al[i]=0
            dfs(i)
    
        
    
n,m=MI()
lis=[LI() for i in range(m)]
#print(lis)
cou=0
for i in range(m):
    tree=[[] for i in range(n)]
    for j in range(m):
        if i!=j:
            tree[lis[j][0]-1].append(lis[j][1]-1)
            tree[lis[j][1]-1].append(lis[j][0]-1)
    count=0
    for k in range(n):
        al=[-1]*n
        al[k]=0
        dfs(k)
        #print(al)
        if not -1 in al:
            count+=1
    if count!=n:
        cou+=1
print(cou)    

Measured memory_bytes: 55512
#include <stdio.h>

int main(void)
{
  int d;
  int n, sum;
  int i;

  while (scanf("%d", &d) != EOF) {
    n = 600 / d;
    sum = 0;
    for (i = 1; i < n; i++) {
      sum += ((d * i)*(d * i) * d);
    }
    printf("%d\n", sum);
  }

  return 0;
}

Measured memory_bytes: 592
#!/usr/bin/env python3
import sys, math, fractions, itertools


def solve(n: int, a: "List[int]"):
    r = [str(rr) for rr in list(reversed(a[::2]))]
    l = [str(rr) for rr in a[1::2]]
    if n % 2 == 1:
        print(' '.join(r + l))
    else:
        print(' '.join(list(reversed(r+l))))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(n) ]  # type: "List[int]"
    solve(n, a)

if __name__ == '__main__':
    main()


Measured memory_bytes: 49928
#include<bits/stdc++.h>
using namespace std;
int x[]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1,51};
int main()
{
  int k;
  cin>>k;
  k--;
  cout<<x[k]<<"\n";
  return 0;
}

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


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

	 if(n==0) break;

	 int a[1000];

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

	 int dif=1000001;

	 for(int i=0;i<n-1;i++){
		 for(int j=i+1;j<n;j++){
			 int d=abs(a[i]-a[j]);
			 if(dif>d) dif=d;
		 }
	 }

	 cout<<dif<<endl;

 }
	return 0;
}

Measured memory_bytes: 3092
#include <stdio.h>
int main(void){
    int a,sum;
    sum=1;

    while(sum!=0)
    {
        sum=0;
        while((a=getchar())!='\n')
            sum+=a-'0';
        if(sum==0)
            break;
        printf("%d\n",sum);
    }
    return 0;
}

Measured memory_bytes: 524
import java.util.Scanner;


public class Main {
	public static void main(String[] artgs){
		Scanner sn = new Scanner(System.in);
		int before = sn.nextInt();
		while(true){
			String op = sn.next();
			if(op.equals("=")) break;
			int after = sn.nextInt();
			if(op.equals("+")){
				before += after;
			} else  if(op.equals("-")){
				before -= after;
			}else  if(op.equals("*")){
				before *= after;
			}else  if(op.equals("/")){
				before /= after;
			}
		}
		System.out.println(before);
	}
}

Measured memory_bytes: 19528
from heapq import heappush, heappop
N, C, *L = map(int, open(0).read().split())
hq1 = []
hq2 = []
sushi = []
for x,y in zip(*[iter(L)]*2):
  sushi += [(x,y)]
sushi.sort()
x = 0
y = 0
for i in range(N-1,-1,-1):
  p,q = sushi[i]
  x += q
  heappush(hq1,(-x+(C-p),i))
  p,q = sushi[N-1-i]
  y += q
  heappush(hq2,(-y+p,N-1-i))
m = 0
ans1 = 0
for i in range(N):
  x,y = sushi[i]
  m += y
  n = m-x
  while hq1 and hq1[0][1]<=i:
    heappop(hq1)
  if hq1 and hq1[0][0]<-x:
    ans1 = max(ans1, n-hq1[0][0]-x)
  else:
    ans1 = max(ans1,n)
    

m = 0
ans2 = 0
for i in range(N-1,-1,-1):
  x,y = sushi[i]
  m += y
  n = m-(C-x)
  while hq2 and hq2[0][1]>=i:
    heappop(hq2)
  if hq2 and hq2[0][0]<-(C-x):
    ans2 = max(ans2, n-hq2[0][0]-(C-x))
  else:
    ans2 = max(ans2, n)
print(max(ans1,ans2))

Measured memory_bytes: 47132
#include <iostream>
#include <string>
#include <vector>

std::vector<uint64_t> primes{3};

int N;

uint64_t Prime() {
  for (uint64_t n = primes.back() + 2;; n += 2) {
    for (const auto p : primes) {
      if (n < p * p) {
        primes.push_back(n);
        return n;
      }

      if (n % p == 0) break;
    }
  }
}

uint64_t Next() {

  while (true) {
    const auto p = Prime();
    if (p % 15 == 1)
      return p;
  }
}

int main() {

  std::cin >> N;

  std::cout << Next();

  for (int i = 1; i < N; ++i)
      std::cout << " " << Next();

  std::cout << std::endl;

  return 0;
}


Measured memory_bytes: 892
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

template<class T> void read(T &x){
	int f=0; x=0; char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) f|=(ch=='-');
	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	if(f) x=-x;
}

const int N=5000005;
int a[N],n;
char s[N];
ll ans;

int main(){
	scanf("%s",s+1);
	n=strlen(s+1)+1;
	rep(i,1,n-1){
		if(s[i]=='<'){
			a[i+1]=max(a[i+1],a[i]+1);
		}
	}
	per(i,n-1,1){
		if(s[i]=='>'){
			a[i]=max(a[i],a[i+1]+1);
		}
	}
	rep(i,1,n){
		ans+=a[i];
	}
	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4864
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
  int A,B,C,D,E,F;
  cin>>A>>B>>C>>D>>E>>F;
  C-=E,D-=F;
  E=A*C,F=B*D;
  if(E<0)E*=-1,F*=-1;
  if(E+F>0)puts("0");
  else if(E+F==0)puts("infinity");
  else if(E%(-E-F))cout<<E/(-E-F)*2+1<<endl;
  else cout<<E/(-E-F)*2<<endl;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<(x)<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

template<typename T> inline void CHMAX(T& a, const T b) {if(a<b) a=b;}
template<typename T> inline void CHMIN(T& a, const T b) {if(a>b) a=b;}

constexpr ll MOD=1000000007ll;
// constexpr ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	// cout<<setprecision(10)<<fixed;
	int n, m;
	ll a[125252];
	cin>>n>>m;
	priority_queue<ll> q;
	REP(i, n){
		cin>>a[i];
		q.push(a[i]);
	}
	REP(i, m){
		ll t=q.top();
		q.pop();
		q.push(t/2);
	}
	ll ans=0;
	while(q.size()){
		ans+=q.top();
		q.pop();
	}
	cout<<ans<<'\n';
	return 0;
}


Measured memory_bytes: 1912
N = int(input())
inputstr = []
inputlist = []
for i in range(N):
    inputstr = str(input())
    inputint = inputstr.split()
    inputlist.append(inputint)

isJail = False
for i in range(len(inputlist)-2):
    if(inputlist[i][0] == inputlist[i][1]):
        if inputlist[i+1][0] == inputlist[i+1][1]:
            if inputlist[i+2][0]== inputlist[i+2][1]:
                 isJail = True

if isJail == True:
    print("Yes")
else:
    print("No")  


Measured memory_bytes: 9200
#include<bits/stdc++.h>
#include <algorithm>
#include <cctype>
#include <iostream>
#include <string>
using namespace std;

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

const ll MOD = 1e9+7;

// Combinationの使い方
// vector<vector<ll>> v(N+1, vector<ll>(N+1, 0));
// comb(v);
void comb(vector<vector<ll>> &v){
    for(int i = 0; i < v.size(); i++){
        v[i][0] = 1;
        v[i][i] = 1;
    }
    for(int k = 1; k < v.size(); k++){
        for(int j = 1; j < k; j++){
            v[k][j] = (v[k-1][j-1] + v[k-1][j]);
            //余りを求める問題は毎回計算ごとにやる
            // v[k][j] = (v[k-1][j-1] + v[k-1][j]) % MOD;
        }
    }
}

// Union Find
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

// vector<tuple<long,long>> items; // (value, weight)
// auto item = items[i];
// long v = get<0>(item);
// long w = get<1>(item);
// long v, w;
//   for( int i = 0; i < N; i++ ){
//     cin >> v >> w;
//     items.push_back( make_tuple(v, w) ); // item : (value, weight)
//   }

// 1 << 3 : int "3" change to bit "100"
// rep(pattern, 1 << N) if (pattern & (1 << x)) cnt++

int check(string s){
    int check7 = 0;
    int check5 = 0;
    int check3 = 0;
    if(s.find("7")!=string::npos) check7 = 1;
    if(s.find("5")!=string::npos) check5 = 1;
    if(s.find("3")!=string::npos) check3 = 1;
    if(check7*check5*check3==1) return 1;
    return 0;
}

int search(string s, ll N){
    ll cnt = 0;
    if(stol(s)>N) return 0;  
    if(check(s)) cnt++;

    cnt += search(s+"7", N);
    cnt += search(s+"5", N);
    cnt += search(s+"3", N);

    return cnt;
}

int main(){
    ll N;
    cin >> N;
    cout << search("3", N) + search("5", N) + search("7", N)<< endl;
    return 0;
}

Measured memory_bytes: 764
def action_handler(n, b_array)
  result = []
  for i in 0..n - 1
    if i == 0
      result.push(b_array[i])
    elsif i == n - 1
      result.push(b_array[i - 1])
    else
      result.push([b_array[i], b_array[i - 1]].min)
    end
  end
  return result.inject(:+)
end

n = gets.to_i
b_array = gets.chop.split.map(&:to_i)

print action_handler(n, b_array)

Measured memory_bytes: 1788
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Practice
{
    class Program
    {
        static void Main(string[] args)
        {
            SolveA(args);
            //SolveB(args);
            //SolveC(args);
            //SolveD(args);


        }
        private static int s_compareTotal = 0;
        static void SolveA(string[] args)
        {
            int.Parse(Console.ReadLine());
            int[] s = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            MergeSort(s, 0, s.Length);

     
            Console.WriteLine(string.Join(" ", Array.ConvertAll(s, a=>a.ToString())));
            Console.WriteLine(s_compareTotal);
        }
        static void Merge(int[] a , int left, int mid, int right)
        {
            int n1 = mid - left;
            int n2 = right - mid;
            int[] L = new int[n1 + 1];
            int[] R = new int[n2 + 1];
            for (int i=0;i<n1;++i)
            {
                L[i] = a[left + i];
            }
            for(int i=0;i<n2;++i)
            {
                R[i] = a[mid + i];
            }
            L[n1] = int.MaxValue;
            R[n2] = int.MaxValue;

            {
                int i = 0;
                int j = 0;
                for(int k=left;k<right;++k)
                {
                    s_compareTotal++;
                    if (L[i] <= R[j])
                    {
                        a[k] = L[i];
                        i = i + 1;
                    }
                    else
                    {
                        a[k] = R[j];
                        j = j + 1;
                    }
                }
            }
        }
        static void MergeSort(int[] a, int left, int right)
        {
            if( left + 1 < right)
            {
                int mid = (left + right) / 2;
                MergeSort(a, left, mid);
                MergeSort(a, mid, right);
                Merge(a, left, mid, right);
            }
        }
    }

}



Measured memory_bytes: 96936
imports System

Module Module1
  public Sub Main()

    Dim Money as long = Long.Parse(Console.ReadLine())

    Dim Result as long = 100

    for i as long = 1 to 100000000000000000

        Result =  Math.Truncate(Result * 1.01)

	if Money <= Result then 

		console.writeLine(i.tostring)
		exit for
	
	end if

    next

  End Sub
End Module


Measured memory_bytes: 27656
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i=(a); i<(b); i++)

int main() {
  int N;
  cin >> N;
  string S;
  cin >> S;
  int hidari_w[N];
  int totalw = 0;
  hidari_w[0] = 0;
  FOR(i,0,N-1) {
    if (S[i] == 'W') {
      hidari_w[i+1] = hidari_w[i]+1;
    }
    else hidari_w[i+1] = hidari_w[i];
  }
  FOR(i,0,N) {
    if(S[i] == 'W') totalw++;
  }
  int ans = N;
  //FOR(i,0,N) {
    //cout << hidari_w[i] << " " << endl;
    //cout << totalw << endl;
  //}
  FOR(i,0,N) {
    int hurimuki;
    if(S[i]== 'W') hurimuki = hidari_w[i] + ((N-totalw) - (i-hidari_w[i]));
    else hurimuki = hidari_w[i] + ((N-totalw) - (i-hidari_w[i]) -1);
    ans = min(ans,hurimuki);
  }
  cout << ans << endl;
    
  
  return 0;
}

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

using namespace std;

const int N = 2000 * 2000 + 5;

int n;
bitset<N> s;

void solve()
{
    s[0] = 1;
    cin >> n;
    int sum = 0;
    for(int i = 0; i < n; ++ i) {
        int a;
        cin >> a;
        sum += a;
        s |= s << a;
    }

    sum = (sum + 1) / 2;
    for(int i = sum; i < N; ++ i) {
        if (s[i]) {
            cout << i << endl;
            return;
        }
    }
}

int main()
{
    solve();
    return 0;
}


Measured memory_bytes: 1664
import java.util.*;

public class Main {
    public static void main(String[] args) {
      Scanner s = new Scanner(System.in);
        final String S = s.nextLine();
        final String T = s.nextLine();

        if (S.equals(T.substring(0, T.length() - 1))) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 26944
import java.util.*;
public class Main {
	
    public static Long gcd(Long x,Long y){
        if(x < y) return gcd(y, x);
        if(y == 0) return x;
        return gcd(y, x % y);
    }
    public static Long lcm(Long x,Long y){                                                              
        return x*(y/gcd(x,y));                                                                                                                                                                                                                
    }
    public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		Long [] in = new Long [a];
        for(int i=0;i<a;i++){
                             in[i] = sc.nextLong();
                            }
        Arrays.sort(in);
        Long ans = in[a-1];
        for(int i=0;i<a;i++){ans = lcm(ans,in[i]);
                              }        
		System.out.println(ans);
	}
}


Measured memory_bytes: 23892
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int count = 0;
        for(int i=1; i<=a; i++) {
            String b = Integer.toString(i);
            if(b.length() % 2 == 1) {
                count++;
            }
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 27988
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define true 1
#define false 0
#define LEN 500001
#define N 3
#define N2 9

typedef struct puzzle {
	int f[N2];
	int space;
	int path;
} Puzzle;

void enqueue(Puzzle);
Puzzle dequeue();

Puzzle Q[LEN];
int head = 0, tail = 0;
int V[LEN];
static const int dx[4] = {-1, 0, 1, 0};
static const int dy[4] = {0, -1, 0, 1};

int hash(Puzzle p) {
	int i, j;
	int key, count;
	int sum = 0;

	for ( i = 0, key = 1; i < N2; key *= ++i) {
		for ( j = 0, count = 0; j < i; j++) {
			if ( p.f[j] < p.f[i] ) count++;
		}
		sum += count * key;
	}
	return sum;
}

int isTarget(Puzzle p) {
	int i;
	for ( i = 0; i < N2; i++)
		if ( p.f[i] != ( i + 1 ) ) return false;
	return true;
}

int bfs(Puzzle s) {
	Puzzle u, v;
	int r;
	s.path = 0;
	enqueue(s);
	V[hash(s)] = true;

	while ( head != tail ){
		u = Q[head];
		dequeue();
		if ( isTarget(u) == true ) return u.path;
		int sx = u.space / N;
		int sy = u.space % N;
		for ( r = 0; r < 4; r++) {
			int tx = sx + dx[r];
			int ty = sy + dy[r];
			if ( tx < 0 || ty < 0 || tx >= N || ty >= N ) continue;
			v = u;
			int temp = v.f[u.space];
			v.f[u.space] = v.f[tx * N + ty];
			v.f[tx * N + ty] = temp;
			v.space = tx * N + ty;
			if ( V[hash(v)] != true ) {
				V[hash(v)] = true;
				v.path++;
				enqueue(v);
			}
		}
	}

	return -1;
}

int main() {
	Puzzle in;
	int i;

	for ( i = 0; i < N2; i++) {
		scanf("%d",&in.f[i]);
		if (in.f[i] == 0) {
			in.f[i] = N2;
			in.space = i;
		}
	}

	int ans = bfs(in);
	printf("%d\n",ans);

	return 0;
}

void enqueue(Puzzle x) {
	Q[tail] = x;
	tail = (tail + 1) % LEN;
}

Puzzle dequeue() {
	Puzzle x = Q[head];
	head = (head + 1) % LEN; 
	return x;
}


Measured memory_bytes: 11008
// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_dec_float.hpp>

using namespace std;

using i64 = long long;

const i64 MOD = 1e9 + 7;
const i64 INF = i64(1e18) + 7;


template <typename T>
bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}


void solve(long long a, long double b){
    boost::multiprecision::cpp_dec_float_100 aa(a), bb(b);
    cout << static_cast<int64_t>(a * b) << endl;
}


signed main(){
    long long A;
    scanf("%lld",&A);
    long double B;
    scanf("%Lf",&B);
    solve(A, B);
    return 0;
}


Measured memory_bytes: 3956
// キョウプロ.cpp : コンソール アプリケーションのエントリ ポイントを定義します。
//

#pragma once

#include <stdio.h>
#include <string>
#include <iostream>
#include <queue>
#include <algorithm>
#include <sstream>
#include <vector>
#include <math.h>
#include <set>

using namespace std;

long long A, B, C, D, M, N, X, Y, Z;
long long a[10000];


int main()
{

	cin >> N;
	M = 0;
	C = 0;

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

		if (M <= a[i]) {
			C++;
			M = a[i];
		}
	}


	cout << C << endl;

    return 0;
}



Measured memory_bytes: 256
#include<iostream>
using namespace std;
const int maxn=2e5+10;
const long long mod=998244353L;
long long t[maxn<<2],laz[maxn<<2],n,q,sum[maxn];
long long qpow(long long base,long long k){
	long long res=1;
	while(k){
		if(k&1){
			res=res*base%mod;
		}
		k/=2;
		base=base*base%mod;
	}
	return res%mod;
}
void make(int l,int r,int num){
	if(l==r){
		t[num]=qpow(10,n-l);
		laz[num]=0;
		return;
	}
	else{
		int mid=(l+r)>>1;
		make(l,mid,num<<1);
		make(mid+1,r,num<<1|1);
		t[num]=(t[num<<1]+t[num<<1|1])%mod;
	}
}
void update(int x,int y,int nv,int l,int r,int num){
	int mid=(l+r)/2;
	if(x<=l&&y>=r){
		laz[num]=nv;
		t[num]=(sum[n-l]-sum[n-r-1]+10*mod)%mod*nv%mod;
		return;
	}
	if(laz[num]){
		laz[num<<1]=laz[num<<1|1]=laz[num];
		t[num*2]=laz[num]*(sum[n-l]-sum[n-mid-1]+10*mod)%mod;
		t[num*2+1]=laz[num]*(sum[n-mid-1]-sum[n-r-1]+10*mod)%mod;
		laz[num]=0;
	}
	if(y<=mid) update(x,y,nv,l,mid,num*2);   /*注意找儿子的时候不能改动区间*/ 
	else if(x>mid) update(x,y,nv,mid+1,r,num*2+1);
	else{
		update(x,y,nv,l,mid,num*2);
		update(x,y,nv,mid+1,r,num*2+1);
	}
	t[num]=(t[num<<1]+t[num<<1|1])%mod;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	long long x=1;
	sum[0]=1;
	for(int i=1;i<=n;i++){
		x=x*10%mod;
		sum[i]=(sum[i-1]+x)%mod;
	}
	make(1,n,1);
	for(int i=1,x,y,w;i<=q;i++){
		cin>>x>>y>>w;
		update(x,y,w,1,n,1);
		cout<<t[1]<<endl;
	}
}

Measured memory_bytes: 13368
#!/usr/bin/env python3
import sys


def solve(R: int, G: int):
    # (R + X) / 2 = G
    print(2*G - R)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    R = int(next(tokens))  # type: int
    G = int(next(tokens))  # type: int
    solve(R, G)


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
n = int(input())
u = list(map(int, input().split()))
A = []
B = []
Af = [[i, -1] for i in range(100007)]
Bf = [[i, -1] for i in range(100007)]
for i in range(n):
    if i % 2 == 0:
        A.append(u[i])
        Af[u[i]][1] += 1
    else:
        B.append(u[i])
        Bf[u[i]][1] += 1

Af.sort(key=lambda x: -x[1])
Bf.sort(key=lambda x: -x[1])

Ae = 0
Be = 0
ans = 0
if Af[0][0] == Bf[0][0]:
    Ae = Af[0][0]
    Be = Bf[1][0]
    ans1 = 0
    for i in range(len(A)):
        if Ae != A[i]:
            ans1 += 1
    for i in range(len(B)):
        if Be != B[i]:
            ans1 += 1

    Ae = Af[1][0]
    Be = Bf[0][0]
    ans2 = 0
    for i in range(len(A)):
        if Ae != A[i]:
            ans2 += 1
    for i in range(len(B)):
        if Be != B[i]:
            ans2 += 1
    ans = min(ans1, ans2)
else:
    Ae = Af[0][0]
    Be = Bf[0][0]
    for i in range(len(A)):
        if Ae != A[i]:
            ans += 1
    for i in range(len(B)):
        if Be != B[i]:
            ans += 1

print(ans)

Measured memory_bytes: 36092
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;

class Program
{
    const string Yes = "Yes";
    const string No = "No";
    const long Mod = 1000000007;

    static void Main(string[] args) {
#if DEBUG
        MyDebugger.Test(process, "../TextFile1.txt");
#else
        object ret = process(new StreamReader(Console.OpenStandardInput()));
        Console.WriteLine(ret);
#endif
    }

    static object process(TextReader input) {
        var n = 100000;

        var sosu = new int[n + 1];

        for (int i = 2; i <= Math.Sqrt(n);) {
            if (sosu[i] == 0) {
                var x = 2 * i;
                while (x <= n) {
                    sosu[x] = 1;
                    x += i;
                }
            }
            i += i == 2 ? 1 : 2;
        }

        var li = new List<int>();

        for (int i = 3; i <= n; i += 2) {
            if (sosu[i] == 0) {
                var x = (i + 1) / 2;
                if (sosu[x] == 0)
                    li.Add(i);
            }
        }

        var q = int.Parse(input.ReadLine());
        for (int i = 0; i < q; i++) {
            var spl = input.ReadLine().Split(' ');
            var l = int.Parse(spl[0]);
            var r = int.Parse(spl[1]);
            var c = li.Count(x => l <= x && x <= r);
            Console.WriteLine(c);
        }
        return null;
    }

    static int[] ToIntArray(string strs, int n) {
        var ret = new int[n];
        var spl = strs.Split(' ');
        for (int i = 0; i < n; i++)
            ret[i] = int.Parse(spl[i]);
        return ret;
    }
}


Measured memory_bytes: 17852
import sys
d,g=map(int,input().split())
p=[0]*d
c=[0]*d
for i in range(d):
    p[i],c[i]=map(int,input().split())
ans=float('inf')
for i in range(1<<d):
    su=0
    left=-1
    cnt=0
    for j in range(d):
        if (i>>j)&1:
            su+=p[j]*(j+1)*100
            su+=c[j]
            cnt+=p[j]
        else:
            left=max(left,j)
    if su<g:
        for j in range(p[left]):
            su+=100*(left+1)
            cnt+=1
            if su>=g:
                break
    if su>=g:
        ans=min(ans,cnt)
print(ans)
    



Measured memory_bytes: 3188
#include <iostream>
#include <algorithm>
#include <string>
#include <tr1/unordered_set>
using namespace std;

int main() {
    int N; cin >> N;
    tr1::unordered_set<string> s;
    while(N--) {
        string t; cin >> t; s.insert(t);
    }

    int M; cin >> M;
    bool isOpen = false;
    while(M--) {
        string t; cin >> t;
        if(s.count(t)) {
            isOpen ^= 1;
            cout << (isOpen ? "Opened by " : "Closed by ") << t << endl;
        }
        else {
            cout << "Unknown " << t << endl;
        }
    }
}

Measured memory_bytes: 1240
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define puts(i) cout << i << endl
#define INF INT_MAX
#define INFL LLONG_MAX
typedef long long ll;
using namespace std;
int main(){

string s;

cin >> s;

if("SSS"==s){
  cout << 0 << endl;
}


else if("SRR"==s || "RRS"==s){
  cout << 2 << endl;
}


else if("RRR"==s){
  cout << 3 << endl;
}

else{
  cout << 1 << endl;
}
}


Measured memory_bytes: 3592
#include <iostream>
using namespace std;
typedef long long ll;

const ll MOD = 998244353;

ll a[3005];
ll dp[3005][3005];

int main()
{
    ll n, s;
    cin >> n >> s;
    for(int i = 0; i < n; i++) cin >> a[i];
    ll ans = 0;
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= s; j++) dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
        for(int j = a[i - 1]; j <= s; j++) dp[i][j] = (dp[i][j] + dp[i - 1][j - a[i - 1]]) % MOD;
        ans = (ans + dp[i][s]) % MOD;
        dp[i][0]++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 70656
#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);
	
	string s; cin >> s;
	auto check = [](const string &s){
		rep(i, s.size()) if(i % 2 && s[i] == 'R'
			|| i % 2 == 0 && s[i] == 'L') return 0;
		return 1;
	};
	cout << (check(s) ? "Yes" : "No") << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

int main(void){
    int a,b,c,N;

    scanf("%d",&N);
    a = N%10;
    b = ((N-a)/10)%10;
    c = (N - a - b)/100;

	if(a == 7 || b == 7 || c == 7){
    	printf("Yes");
	}else{
		printf("No");
	}
	
    return 0;
}

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

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SUM(a) accumulate(all(a), 0LL)
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define FOR(i, m, n) for(int (i)=(m); (i)<(n); i++)
#define FORR(i, m, n) for(int (i)=(n)-1; (i)>=(m); i--)
#define debug(x) cerr << #x << " = " << x << endl
//#define int long long

typedef long long ll;
//ll const MOD = 998244353;
ll const MOD = 1e9+7;
int const inf = 1e9;
ll const INF = 1e18;

inline void ios_(){cin.tie(0); ios::sync_with_stdio(false);}
template<typename T> int size(const T& a){return (int)a.size();}
template<typename T> T Div(T a, T b){return (a + b - 1) / b;}
template<typename T> bool chmin(T& a, const T& b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, const T& b){if(a < b){a = b; return true;} return false;}

class PrimeNumber{
public:
    int N;
    vector<ll> table;

    void makeTable(int n){
        N = n;
        vector<bool> v(n+1, true);
        v[0] = false;
        v[1] = false;
        int m = sqrt(n);
        for(int i=2; i<=m; i++){
            if(v[i]){
                int j = i*2;
                while(j <= n){
                    v[j] = false;
                    j += i;
                }
            }
        }
        for(int i=0; i<=n; i++){
            if(v[i]){
                table.push_back(i);
            }
        }
    }

    static bool is_prime(ll n){
        if(n < 2){
            return false;
        }
        ll m = sqrt(n);
        for(ll i=2; i<=m; i++){
            if(n%i == 0){
                return false;
            }
        }
        return true;
    }

    static map<ll,int> factorization(ll n){
        map<ll,int> mp;
        for(ll i=2; i*i<=n; i++){
            while(n%i == 0){
                n /= i;
                mp[i]++;
            }
        }
        if(n > 1){
            mp[n]++;
        }
        return mp;
    }
};

ll BinarySearch(ll ng, ll ok, function<bool(ll)> judge){
    while(abs(ok - ng) > 1){
        ll mid = (ok + ng) / 2;
        if(judge(mid)) ok = mid;
        else ng = mid;
    }
    return ok;
}


signed main(){
    ll n;
    cin >> n;

    auto mp = PrimeNumber::factorization(n);

    ll ans = 0;
    for(const auto& i : mp){
        ll x = i.second;
        int e = 1;
        while(x >= e){
            x -= e;
            e++;
            ans++;
        }
    }

    cout << ans << endl;

    
    return 0;
}


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

const int maxn=200007;
int n,k,cnt;
string s;
int sum[maxn];
stack<int> ans;

int ms(int l,int r){
    if (l==r) return l;
    int md=(l+r)>>1;
    if (sum[md]==sum[l-1]) return ms(md+1,r);
    else return ms(l,md);
}
int main(){
    cin>>n>>k>>s;
    cnt=n;
    for (int i=1;i<=n;++i){
        sum[i]=sum[i-1]+(s[i]=='0');
    }
    while (cnt>k){
        if (sum[cnt-k-1]==sum[cnt-1]){
            printf("-1");
            return 0;
        }
        int t=ms(cnt-k,cnt-1);
        ans.push(cnt-t);
        cnt=t;
    }
    ans.push(cnt);
//    printf("%d\n",ans.size());
    while (ans.size()){
        printf("%d ",ans.top());
        ans.pop();
    }
    return 0;
}

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

int main(int argc, const char * argv[]) {
    int N;
    int a[100000] = {0};
    int count = 0;
    
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    
    for (int i = 0; i < N; i++) {
        if (a[i] % 2 == 0) {
            count++;
        }
    }
    if (count == N) {
        cout << "second" << endl;
    } else {
        cout << "first" << endl;
    }
    return 0;
}

Measured memory_bytes: 640
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

//字符串中大小写转换，字母之外不用管
public class Main {
	public static String togglingCases(String input) {
		List<Character> lc = new ArrayList<>();
		String chg = "";
		for (int i = 0; i < input.length(); ++i) {
			char ch = input.charAt(i);
			if (Character.isLetter(ch)) {
				if (Character.isUpperCase(ch))
					ch = Character.toLowerCase(ch);
				else
					ch = Character.toUpperCase(ch);
			}
			chg += String.valueOf(ch);
		}
		return chg;
	}
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String input = scan.nextLine();
		String chg = togglingCases(input);
		System.out.println(chg);
	}
}



Measured memory_bytes: 31616
#include<bits/stdc++.h>
using namespace std;
int n,a[111111],memo[111111];
int dp(int x){
  if(memo[x]!=-1) return memo[x];
  if(x==n-1) return 0;
  if(x==n-2) return memo[x]=dp(x+1)+abs(a[x]-a[x+1]);
  return memo[x]=min(dp(x+1)+abs(a[x]-a[x+1]),dp(x+2)+abs(a[x]-a[x+2]));
}
int main(){
  memset(memo,-1,sizeof(memo));
  cin>>n;
  for(int i=0;i<n;i++) cin>>a[i];
  cout<<dp(0)<<endl;
  return(0);
}


Measured memory_bytes: 2688
wt = int(input())
w = [1]
for i in range(7):
    w.append(6 ** (i + 1))
for i in range(5):
    w.append(9 ** (i + 1))
n = len(w)
dp = [[float("inf") for i in range(wt + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    for j in range(wt + 1):
        if j >= w[i]:
            dp[i + 1][j] = min(dp[i + 1][j - w[i]] + 1, dp[i][j])
        else:
            dp[i + 1][j] = dp[i][j]
print(dp[n][wt])


Measured memory_bytes: 102780
#include <stdio.h>
#include <stdlib.h>
#define FOR(variable,a,b) for(variable=(a);variable<(b);variable++)

void swap(int* a,int* b) {
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
    return;
}

void reverse(int* target, int count) {
    int i;
    FOR(i, 0, count/2) {
        swap(&target[i], &target[(count-1)-i]);
    }
    return;
}

// sort method
int int_sort(const void* a, const void* b) {
    // now is 1, 2, 50, 60...
    // to become ..., 60, 50, 2, 1 running reverse(variable)
    // to cast variable from void
    if(*(int* )a < *(int* )b) {
        return -1;
    } else {
        if(*(int* )a == *(int* )b) {
             return 0;
        }
    }
  return 1;
}

void intsort(int* target, int count) {
    qsort((void* )target, count, sizeof(target[0]), int_sort);
    return;
}

int main(){
    // import phase
    int i;
    int target[5];
    
    FOR(i, 0, 5) {
        scanf("%d", &target[i]);
    }
    
    // calclate phase
    intsort(target, 5);
    reverse(target, 5);
        
    // output phase
    printf("%d %d %d %d %d\n",
           target[0],
           target[1],
           target[2],
           target[3],
           target[4]);

    return 0;
}

Measured memory_bytes: 600
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
//もう二度とつかわん//
//    ↓ ↓　↓　　 //
#define ll long long
//    ↑　↑　↑    //
//フェルマー方程式の恨み//
#define rep(i,n) for(int i=0;i<n;i++)
#define ggr getchar(); getchar();return 0;
using namespace std;
//素数判定
bool prime(ll n) {
	if (n == 1)return false;
	for (int i = 2; i*i <= n; i++) {
		if (n%i == 0)return false;
	}
	return true;
}
char a[214514], b[224514];
signed main() {
	ll n, q;
	string s;
	cin >> n >> q >> s;
	rep(i, q)cin >> a[i] >> b[i];
	ll left = 0, right = 0;
	for (int i = q - 1; i >= 0; i--) {
		if (a[i] == s[left] && b[i] == 'L') {
			left++;
		}
		if (left) {
			if (a[i] == s[left - 1] && b[i] == 'R') {
				left--;
			}
		}
		if (a[i] == s[n - 1 - right] && b[i] == 'R') {
			right++;
		}
		if (right) {
			if (a[i] == s[n - right] && b[i] == 'L') {
				right--;
			}
		}
	}
	cout << n - (left + right) << endl;
	ggr
}


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

ll factorial(ll n) {
  ll ret = 1;
  for (ll i = 1; i <= n; ++i) {
    ret *= i;
    ret %= mod;
  }
  return ret;
}

ll pow(ll n, ll k){
  ll ret = 1;
  while (k > 0) {
    if (k & 1) {
      ret = ret * n;
      ret %= mod;
    }
    n = n * n;
    n %= mod;
    k >>= 1;
  }
  return ret;
}

ll inv_factorial(ll n) {
  ll ret = factorial(n);
  ret = pow(ret, mod - 2);
  return ret;
}

ll route(ll x, ll y){
  ll ret = factorial(x + y);
  ret *= inv_factorial(x);
  ret %= mod;
  ret *= inv_factorial(y);
  ret %= mod;
  return ret;
}

int main (){
  ll r1, c1, r2, c2;
  cin >> r1 >> c1 >> r2 >> c2;
  ll ans = 0;
  ans += route(r2 + 1, c2 + 1) - 1;
  ans -= route(r2 + 1, c1) - 1;
  ans -= route(r1, c2 + 1) - 1;
  ans += route(r1, c1) - 1;
  while (ans < 0) ans += mod;
  ans %= mod;

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


Measured memory_bytes: 256