akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define x1 iodfasjdioq
#define x2 dfnauiohqwu
#define y1 djasuhqwuqw
#define y2 adjsijdwqio

const int N=2e3+50;
struct bit {
	int a[N][N];
	inline void inc(int x,int y) {
		for(int i=x;i<=2e3;i+=i&(-i))
			for(int j=y;j<=2e3;j+=j&(-j))
				a[i][j]++;
	}
	inline int ask(int x,int y,int rs=0) {
		for(int i=x;i;i-=i&(-i))
			for(int j=y;j;j-=j&(-j))
				rs+=a[i][j];
		return rs;
	}
	inline int ask(int x1,int y1,int x2,int y2) {
		return ask(x2,y2)-ask(x1-1,y2)-ask(x2,y1-1)+ask(x1-1,y1-1);
	}
} bit1,bit2,bit3;

int n,m,q;
char s[N][N];
int main() {
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) s[i][j]^='0';
		
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(s[i][j]) bit1.inc(i,j);
	for(int i=1;i<=n;i++) 
		for(int j=2;j<=m;j++)
			if(s[i][j] && s[i][j-1]) bit2.inc(i,j-1);
	for(int i=2;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(s[i][j] && s[i-1][j]) bit3.inc(i-1,j);
	for(int i=1;i<=q;i++) {
		int x1,y1,x2,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		int ans=bit1.ask(x1,y1,x2,y2);
		ans-=bit2.ask(x1,y1,x2,y2-1);
		ans-=bit3.ask(x1,y1,x2-1,y2);
		printf("%d\n",ans); 
	}
}

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

#define MAX 100000000

int main(){
  int n;
  while(cin >> n,n){
    int tmp=n;
    vector<pair<int,int> > pfact;
    for(int i=2;i*i<=tmp;++i){
      if(tmp%i==0){
	int cnt=0;
	while(tmp%i==0) cnt++,tmp/=i;
	pfact.push_back(make_pair(i,cnt));
      }
    }
    long long sum=1;
    for(int i=0;i<pfact.size();++i){
      int s;
      int a=pfact[i].first,b=pfact[i].second;
      if(tmp==i) s=((long long)pow(a,b+2)-1)/(a-1),tmp=0;
      else s=((long long)pow(a,b+1)-1)/(a-1);
      sum*=s;
    }
    if(tmp>1) sum*=(tmp+1);
    if(n==1) sum=0;
    sum-=n;
    
    if(sum==n) cout << "perfect number" << endl;
    else if(sum<n) cout << "deficient number" << endl;
    else cout << "abundant number" << endl;
  }
  
  return 0;
}



Measured memory_bytes: 3276
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;

int n,m;
vector<vector<int>> g(100005);
vector<int> ans(100005,0);
vector<bool> used(100005,false);
int solve(int from){
	for(int to = 0; to < g[from].size(); to++) {
		if (!(used[g[from][to]])){
			ans[from] = max(ans[from],1 + solve(g[from][to]));
			used[g[from][to]] = true;
		}
		else{
			ans[from] = max(ans[from],ans[g[from][to]] + 1);
		}
	}
	used[from] = true;
	return ans[from];
}

void search(){
	for(int i = 1; i <= n; i++) {
		if (!(used[i])){
			solve(i);
			used[i] = true;
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i = 0; i < m; i++) {
		int x,y;cin>>x>>y;
		g[x].pb(y);
	}
	search();
	int res = -1;
	for(int i = 1; i <= n; i++) {
		res = max(res,ans[i]);
		// cout << ans[i] << endl;
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 9472
N = int(input())
S = input()

l = 0
r = len(S) - 1

W = 'W'
R = 'R'

cnt = 0
while l < r:
    if S[l] == R:
        l += 1
        continue
    else:
        while l < r:
            if S[r] == W:
                r -= 1
                continue
            else:
                cnt += 1
                l += 1
                r -= 1
                break

print(cnt)


Measured memory_bytes: 67388
from collections import deque

N, M = [int(s) for s in input().split()]
edge = [[int(s) - 1 for s in input().split()] for _ in range(M)]
graph = [[] for _ in range(N)]
for i, j in edge:
    graph[i].append(j)
    graph[j].append(i)

dq = deque([0])
visited = [False] * N
visited[0] = True
parent = [0]*N
while(dq):
    search_obj = dq.pop()
    for candidate_obj in graph[search_obj]:
        if not visited[candidate_obj]:
            dq.appendleft(candidate_obj)
            parent[candidate_obj] = search_obj
            visited[candidate_obj] = True

total_visited = sum(visited)
if total_visited < N:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(parent[i]+1)

Measured memory_bytes: 55684
N = int(input())

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

l_max = max(l_arr)

for i in range(len(l_arr)):
    if l_arr[i] == l_max:
        break

l_arr.pop(i)

if sum(l_arr) > l_max:
    print("Yes")
else:
    print("No")



Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <cstring>

#define MAX_V 100000
#define HMAX 102
#define WMAX 102
#define INF (int)1e9

using namespace std;

int H,W;
char S[HMAX][WMAX];
static const int dx[] = {0,1,0,-1},dy[] = {1,0,-1,0};

struct edge{int to,cap,rev;};
vector<edge> G[MAX_V];
bool used[MAX_V];

void add_edge(int from,int to,int cap){
	G[from].push_back((edge){to,cap,(int)G[to].size()});
	G[to].push_back((edge){from,0,(int)G[from].size()-1});
}

int dfs(int v, int t,int f){
	if(v == t) return f;
	used[v] = true;
	for (int i = 0; i < G[v].size(); ++i)
	{
		edge &e = G[v][i];
		if(!used[e.to] && e.cap > 0){
			int d = dfs(e.to,t,min(f,e.cap));
			if(d > 0){
				e.cap -= d;
				G[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}

int number(int a,int b,int c){
	return a*W+b+1+H*W*c;
}

int max_flow(int s, int t){
	int flow = 0;
	for(;;){
		memset(used,0,sizeof(used));
		int f = dfs(s,t,INF);
		if(f == 0) return flow;
		flow += f;
	}
}
int main(){
	cin >> H >> W;
	for (int i = 0; i < H; ++i)
	{
		for (int j = 0; j < W; ++j)
		{
			cin >> S[i][j];
			if(S[i][j] != 'X'){
				add_edge(number(i,j,0),number(i,j,1),1);
			}else{
				add_edge(0,number(i,j,0),INF);
				add_edge(number(i,j,0),number(i,j,1),INF);
			}
			if(i == 0 || i == H-1 || j == 0 || j == W-1){
				add_edge(number(i,j,1),H*W*2+1,INF);
				if(S[i][j] == 'X'){
					cout << "-1\n";
					return 0;
				}
			}
			for (int k = 0; k < 4; ++k)
			{
				if(i+dx[k] >= 0 && i+dx[k] < H && j+dy[k] >= 0 && j+dy[k] < W){
					add_edge(number(i,j,1),number(i+dx[k],j+dy[k],0),INF);
				}
			}
		}
	}
	int ans = max_flow(0,H*W*2+1);
	cout << ans << endl;
	return 0;
}

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

const int mxK = 1e4 + 5, mxD = 110, mod = 1e9 + 7;
string K;
int n, D;
ll dp[mxK][mxD][2];
vector<int> digits;

ll rec(int idx, int sum, int flag)
{
	if (idx == n)
	{
		if (sum % D == 0)
			return 1;
		return 0;
	}
	if (dp[idx][sum][flag] != -1)
		return dp[idx][sum][flag];
	ll ans = 0;
	int lim = (flag == 1) ? digits[idx] : 9;
	for (int i = 0; i <= lim; i++)
	{
		if (i == digits[idx])
		{
			ans = (ans + rec(idx + 1, (sum + i) % D, flag)) % mod;
		}
		else
		{
			ans = (ans + rec(idx + 1, (sum + i) % D, 0)) % mod;
		}
	}
	return dp[idx][sum][flag] = ans;
}

int main()
{
	ios_base::sync_with_stdio(false);

	cin >> K >> D;
	for (auto it : K)
	{
		digits.push_back(it - '0');
	}
	n = digits.size();
	memset(dp, -1, sizeof(dp));
	ll answer = rec(0, 0, 1);
	answer -= 1;
	if (answer < 0)
		answer += mod;
	cout << answer;

	return 0;
}

Measured memory_bytes: 21912
n = gets.to_i
ans = 0
array = Array.new(10).map{Array.new(10){0}}
for i in 1..n
  array[i.to_s[0].to_i][i.to_s[-1].to_i] += 1
end

for i in 1..9
  for j in 1..9
    ans += array[i][j] * array[j][i]
  end
end

puts ans

Measured memory_bytes: 1788
#include <iostream>
using namespace std;
#define ll long long
int main() {
	ll n,k;
	cin>>n>>k;
	ll ans=0;
	ll j;
	if(k%2==0){
		ll f=k/2;
		ll t=(n/f)-(n/k);
		ans=t*t*t;
	}
		j=k;
		ll s=n/j;
		ans+=(s*s*s);
		cout<<ans;
	
	// your code goes here
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main
{
  public static void main(String args[])
  {
    Scanner sc=new Scanner(System.in);
    String s=sc.nextLine();
    
    if(s.charAt(2)==s.charAt(3)&s.charAt(4)==s.charAt(5))
      System.out.println("Yes");
    else System.out.println("No");
  }
}

Measured memory_bytes: 23764
mod=10**9+7
s=input()
s=s[::-1]
dp=[[0]*13 for _ in range(len(s)+1)]
dp[0][0]=1
for i in range(len(s)):
	p=pow(10,i,13)
	if s[i]=="?":	
		for k in range(13):
			for j in range(10):
				dp[i+1][(k+p*j)%13]+=dp[i][k]
				dp[i+1][(k+p*j)%13]%=mod
	else:
		for k in range(13):
			dp[i+1][(k+p*int(s[i]))%13]+=dp[i][k]
			dp[i+1][(k+p*int(s[i]))%13]%=mod
print(dp[-1][5])


Measured memory_bytes: 62044
N = gets.to_i
A = gets.split.map(&:to_i).sort!

edge,tmp = [],nil
A.reverse_each do
  if _1 == tmp
    tmp = nil
    edge << _1
    break if edge.size == 2
  else
    tmp = _1
  end
end
puts edge.inject(:*) || 0

Measured memory_bytes: 21680
import sys

input = sys.stdin.readline

def main():
    S = input().rstrip('\n')
    l = len(S)
    ws = bs = ''
    for i in range(l):
        if i%2 == 0:
            ws += '0'
            bs += '1'
        else:
            ws += '1'
            bs += '0'
    wsc = bsc = 0
    for i in range(l):
        if S[i] != ws[i]:
            wsc += 1
        if S[i] != bs[i]:
            bsc += 1
    print(min(wsc, bsc))

if __name__ == '__main__':
    main()

Measured memory_bytes: 3444
#include <bits/stdc++.h>
#define sz(arr) (int)arr.size()
#define all(arr) arr.begin(), arr.end()

using namespace std;
typedef long long ll;

void _cin() {}
template <class Head, class... Tail>
void _cin(Head&& head, Tail&&... tail) {
  cin >> head;
  _cin(forward<Tail>(tail)...);
}

#define Cin(T, ...) \
  T __VA_ARGS__;    \
  _cin(__VA_ARGS__)

int main() {
  Cin(int, n);

  ll power = 1;
  for (int i = 1; i <= n; ++i) {
    power *= i;
    power %= (ll)(1e+9 + 7);
  }

  cout << power << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int x,n=360,a=2,b=1;
  cin >> x;
  while(a<180){
    if(x%a==0&&n%a==0){
      x/=a; n/=a; b*=a;
    }else{
      a++;
    }
  }
  cout << 360/b << endl;
}

Measured memory_bytes: 3488
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b; }
template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b; }
void print() { cout << "\n"; }
template <class T, class... Args>
void print(const T &x, const Args &... args) { cout << x << " "; print(args...);}
void debug_out() { cout << "\n"; }
template <class T, class... Args>
void debug_out(const T &x, const Args &... args) { cout << x << " "; debug_out(args...);}
#ifdef _DEBUG
  #define debug(...) debug_out(__VA_ARGS__)
#else
  #define debug(...) 
#endif

const int mod = 1000000007;
// const int mod = 998244353;
struct mint {
  ll x;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
  bool operator==(const mint rhs) const { return x == rhs.x; }
  bool operator!=(const mint rhs) const { return x != rhs.x; }
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  int h, w, a, b;
  cin >> h >> w >> a >> b;
  combination comb(h+w);
  mint ans = 0;
  for (int x = b+1; x <= w; ++x) {
    int y = h-a;
    ans += comb(x-1+y-1,x-1)*comb(a-1+w-x,a-1);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr long long INFL = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;


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

    int N,M;
    cin >> N;
    string S[N];
    map<string,int> m;
    rep(i,N){
        string x;
        cin >> x;
        m[x]++;
    }
    cin >> M;
    rep(i,M){
        string y;
        cin >> y;
        m[y]--;
    }
    int ans=0;
    for(auto P:m){
        ans=max(ans,P.second);
    }
    cout << ans << endl;



}


Measured memory_bytes: 256
import sys
import math
input = sys.stdin.readline

# def prime_table(m: int) -> list:
#     prime = [False] * (m + 1)
#     prime[0] = False
#     prime[1] = False
#     for i in range(2, (m + 1)):
#         if prime[i]:
#             continue
#         for j in range(i, (m + 1)):
#             if i * j > m:
#                 break
#             prime[i * j] = True
#     return prime

n = int(input())
def is_prime(n: int) -> bool:
    if n == 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

if __name__ == "__main__":
    res = 0
    for i in range(n):
        if is_prime(int(input())):
            res += 1
    print(res)



Measured memory_bytes: 5676
#include <utility>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
#include <numeric>
#include <limits>
#include <queue>
#include <cstdint>
#define ll long long int
#define rep(i,rept) for (int (i) = 0; (i) < rept; (i)++)
#define Yes(b) std::cout<< (b ? "Yes" : "No")<<std::endl
#define YES(b) std::cout<< (b ? "YES" : "NO")<<std::endl
#define fr first
#define se second
#define lolo 92233720368547757
#define susu 1000000007
typedef std::pair<int, int> pp;
using namespace std;
int main() {

	ll n, m, a[100001], b[100001], k = 0, mini = lolo, count = 0;
	cin >> n >> m;
	rep(i, n) {
		cin >> b[i];
		if (i > 0) {
			a[i - 1] = abs(b[i - 1] - b[i]);
			k += a[i - 1];
		}
		if (i == m - 1) {
			mini = k + min(abs(b[i]), abs(b[count]));

		}
		if (i >= m) {
			k -= (a[i - m]);

			mini = min(k + min(abs(b[i]), abs(b[count + 1])), mini);

			count++;

		}

	}
	cout << mini;
	return 0;
}


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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

LL n, k, w[100000], d[100000];

bool f(LL x) {
	LL c = 0;
	inc(i, n) {
		if(x >= w[i]) { c += (x - w[i]) / d[i] + 1; }
	}
	return (c >= k);
}

int main() {
	cin >> n >> k;
	inc(i, n) { cin >> w[i] >> d[i]; }
	
	LL l = 0, h = 2e18;
	while((h - l) > 1) {
		LL m = (l + h) / 2;
		(f(m) ? h : l) = m;
	}
	
	cout << h << endl;
	
	return 0;
}


Measured memory_bytes: 1792
fun main() {
    println(solve())
}

val solve: () -> Any = {
    val (A, B, C, K) = readLongList()
    when {
        K in 0..A -> K
        K in A..A+B -> A
        else -> 2*A+B-K
    }
}

val mod: Int = 1_000_000_007


fun readString() = readLine()!!
fun readStringList() = readLine()!!.split(" ")
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readIntList() = readLine()!!.split(" ").map(String::toInt)
fun readLongList() = readLine()!!.split(" ").map(String::toLong)

fun <T> T.alsoPrintln() = also { println(this) }

fun Boolean.toYesOrNo(yes: String = "Yes", no: String = "No") = if (this) yes else no

fun <E> List<E>.toPair() = this[0] to this[1]

fun <T> readPair(t: (String) -> T) = readPair(t, t)
fun <S, T> readPair(s: (String) -> S, t: (String) -> T) =
    readLine()!!.split(" ").let { Pair(s(it[0]), t(it[1])) }

fun Int.pow(n: Int) = Math.pow(this.toDouble(), n.toDouble())
fun Int.powInt(n: Int) = pow(n).toInt()

fun minAndMax(a: Int, b: Int) = if (a < b) a to b else b to a


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

int main() {

  int n,k,q,a;
  cin >> n >> k >> q;
  
  vector<int> A(n);
  
  for ( int i = 0; i < q; i++){
    cin >> a;
    A[a-1]++;
  }
   
  for ( int i = 0; i < n; i++){
    if ( k - q + A[i] > 0 ){
      cout << "Yes" << endl;
    }else{
      cout << "No" << endl;
    }
  }
  
}


Measured memory_bytes: 1024
#include "bits/stdc++.h"

using namespace std;

#define int long long int
#define cont continue;
#define ff first
#define ss second
#define pb push_back
#define ins insert
#define mp make_pair
#define endl '\n'


typedef vector<int> vi;
typedef set<int> si;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef map<int, int> mi;

//const
#define EPS 1e-9
#define INF LLONG_MAX
const int mod = 1000 * 1000 * 1000 + 7; //1e9+7
const double PI = 3.14159265358979323846264;
const pi steps[] = {{1, 0}, {0, 1}, { -1, 0}, {0, -1}, {1, -1}, {1, 1}, { -1, -1}, { -1, 1}}; //for (auto [dx,dy] : steps)
//const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};

// inputs & output & debug
#define w(t) int t; cin>> t; while(t--)

#define deb(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}

//useful functions
//#define deb(x) cout<<#x<<": "<<x<<endl;
#define isPowOfTwo(x) return (x && (!(x&(x-1))));
#define sz(a) (int)((a).size())
#define present(c,x) ((c).find(x) != (c).end())
#define ip_arr(a,n)   for(int i=0;i<n;i++) cin>>a[i];
#define op_arr(arr,n) for(int i=0;i<n;i++) cout<<arr[i]<<"\n"; cout<<endl;
#define fill_arr(arr,n,i) fill(arr,arr+n,i)
#define fill_vec(v,n,i) fill(v.begin(),v.begin()+n,i);
#define sortv(a) sort(a.begin(),a.end())

void fio()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}

void setUpLocal()
{
#ifndef ONLINE_JUDGE
	freopen("/Users/asuryana/Documents/CP/input.txt", "r", stdin);
	freopen("/Users/asuryana/Documents/CP/output.txt", "w", stdout);
#else
#define cerr if(0) cerr
#endif
}

const int maxN = (int)1e5 + 7;
// vi gp[gp_size];
// int vis[gp_size];
// int cnt[gp_size];

int n;
int a[maxN], b[maxN], c[maxN];
int dp[maxN][4];

int calc(int day, int prev)
{
	if (day == n)
		return 0;

	if (dp[day][prev] != -1)
		return dp[day][prev];

	int ans = INT_MIN;

	if (prev == 0) //a
	{
		int c1 = calc(day + 1, 1) + b[day];
		int c2 = calc(day + 1, 2) + c[day];
		ans = max(c1, c2);
	}
	else if (prev == 1) //b
	{
		int c1 = calc(day + 1, 0) + a[day];
		int c2 = calc(day + 1, 2) + c[day];
		ans = max(c1, c2);
	}
	if (prev == 2) //c
	{
		int c1 = calc(day + 1, 1) + b[day];
		int c2 = calc(day + 1, 0) + a[day];
		ans = max(c1, c2);
	}
	if (prev == 3) //first day: choose any
	{
		int c1 = calc(day + 1, 1) + b[day];
		int c2 = calc(day + 1, 2) + c[day];
		int c3 = calc(day + 1, 0) + a[day];
		ans = max(c1, max(c2, c3));
	}

	return dp[day][prev] = ans;

}


void solve()
{

	cin >> n;

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

	memset(dp, -1, sizeof(dp));

	cout << calc(0, 3);

}

int32_t main()
{
	fio();
	//setUpLocal();
	return solve(), 0;
}


Measured memory_bytes: 13796
import java.util.*;
import java.io.*;
import java.nio.charset.StandardCharsets;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		int r = Integer.parseInt(in.readLine());
		System.out.println((r * r));
	}
}


Measured memory_bytes: 22996
#include<iostream>
#include<algorithm>

using namespace std;

int main(){
  int N,Y;
  int a,b;
  bool x = false;
  cin >> N >> Y;
  for(a=0;a<=N;a++)
    for(b=0;b<=N-a;b++)
      if(10000*a+5000*b+1000*(N-a-b) == Y){
        x = true;
        goto END;
      }
  END:;
  if(x) cout << a << " " << b << " " << N-a-b << endl;
  else cout << "-1 -1 -1" << endl;
}

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

#define N 20
#define MAX (1 + (1<<6))
#define inf 0x7fffffff
int arr[N];
int tree[MAX];
int lazy[MAX];

bool prime[1000003];
bool sieve() {
    memset(prime, true, sizeof(prime));
    for(int i = 2; i * i < 1000003; ++i){
        if(prime[i]){
            for(int j = 2 * i; j < 1000003; j += i){
                prime[j] = false;
            }
        }
    }
}

void build_tree(int node, int a, int b) {
    if(a > b) return;
    if(a == b) { 
        tree[node] = arr[a];
        return;
    }
    build_tree(2*node, a, (a+b)/2);
    build_tree(2*node+1, (a+b)/2 + 1, b);
    tree[node] = max(tree[2*node], tree[2*node+1]);
    return;
}

void update_tree(int node, int a, int b, int i, int j, int val) {
    if(lazy[node] != 0) {
        tree[node] += lazy[node];
        if(a != b) {
            lazy[2*node] += lazy[node];
            lazy[2*node+1] += lazy[node]; 
        } 
        lazy[node] = 0;
    }
    if(a > b || a > j || b < i) {
        return;
    }
    if(a >= i && b <= j) {
        tree[node] += val;
        if(a != b) {
            lazy[2*node] += val;
            lazy[2*node+1] += val;    
        }
        return;
    }
    update_tree(2*node, a, (a+b)/2, i ,j, val);
    update_tree(2*node+1, (a+b)/2+1, b, i ,j, val);
    tree[node] = max(tree[2*node], tree[2*node+1]);
    return;
}

int query_tree(int node, int a, int b, int i, int j) {
    if(a > b || a > j || b < i) return -inf;
    if(lazy[node] != 0) {
        tree[node] += lazy[node];
        if(a != b) {
            lazy[2*node] += lazy[node];
            lazy[2*node+1] += lazy[node];
        }
        lazy[node] = 0;
    }
    if(a >= i && b <= j) {
        return tree[node];
    }
    return max(query_tree(2*node, a, (a+b)/2, i, j), query_tree(2*node+1, (a+b)/2+1, b, i, j));

}

int main() { 

    ios_base::sync_with_stdio(0);cin.tie(0);
    
    int n, k;
    cin >> n >> k;
    int r, s, p;
    cin >> r >> s >> p;
    string t;
    cin >> t;
    int ans = 0;
    string t2;
    for(int i = 0; i < t.length(); ++i) {
        if(i < k) {
        
            ans += (t[i] == 'r')? p:0 + (t[i] == 'p')? s:0 + (t[i] == 's')? r:0; 
            t2 +=  (t[i] == 'r')? 'p':((t[i] == 'p')? 's':'r');
        
        } else {
            
            if(t[i] == 'r' && t2[i-k] == 'p') {
                t2 += 'x';
            } else if(t[i] == 'r') {
                t2 += 'p'; 
                ans += p;
            } else if(t[i] == 'p' && t2[i-k] == 's') {
                t2 += 'x'; 
            } else if(t[i] == 'p') {
                t2 += 's'; 
                ans += s;
            } else if(t[i] == 's' && t2[i-k] == 'r') {
                t2 += 'x'; 
            } else if(t[i] == 's') {
                t2 += 'r'; 
                ans += r;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <numeric>
#include <tuple>
#include <stack>

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define print(s) cout << s << endl
typedef long long ll;
using namespace std;

int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

int main() {
	string s; cin >> s;
	cout << (s[0] == s[2]? "Yes": "No") << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<float.h>
#include<tuple>
#include<string.h>
#include<iomanip>
#include<stack>
#include<queue>

using namespace std;
#define ll long long
#define rep(i,n) for(ll i=0;i<n;i++)
#define ALLOF(c) (c).begin(), (c).end()
#define Pa pair<ll,ll>
const ll mod=10e9+7;
const ll INF=10e12;
const ll inf=-1;
ll ABS(ll a){return max(a,-a);}
ll min(ll a,ll b){
  if(a<b) return a;
  else return b;
}

int main(void){
    ll X,Y,Z,K;
    cin>>X>>Y>>Z>>K;
    vector<ll> A(X),B(Y),C(Z),ABsum(0),ABcut(3000,0),total(0);
    rep(i,X) cin>>A.at(i);
    rep(i,Y) cin>>B.at(i);
    rep(i,Z) cin>>C.at(i);
    rep(i,X){
        rep(j,Y){
            ABsum.push_back(A.at(i)+B.at(j));
        }
    }
    sort(ALLOF(ABsum));
    reverse(ALLOF(ABsum));
    ll cutting=min(K,ABsum.size());
    rep(i,cutting) ABcut.at(i)=ABsum.at(i);
    rep(i,cutting){
        rep(j,Z){
            total.push_back(ABcut.at(i)+C.at(j));
        }
    }
    sort(ALLOF(total));
    reverse(ALLOF(total));
    rep(i,K){
        cout<<total.at(i)<<endl;
    }
    return 0;
}

Measured memory_bytes: 42984
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
  int arr[5];
  for(int i=0; i<5; i++)  cin>>arr[i];
  for(int i=0; i<5; i++)
  {
    if(arr[i] == 0)
      cout<<i+1;
  }
  return 0;
}


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

int main() {
  int N, M;
  cin >> N;
  map<string, int> MA;
  string S;
  while (N-- && cin >> S) MA[S]++;
  cin >> M;
  M = 0;
  while (cin >> S) MA[S]--;
  for (auto [a, b] : MA) M = max(M, b);
  cout << M << "\n";
}

Measured memory_bytes: 3616
n=int(input())
s=input()
e=0
w=0
for i in range(n):
  if s[i]=='E':
    e+=1
  else:
    w+=1
if s[0]=='E':
  ans=e-1
  temp=e-1
else:
  ans=e
  temp=e
for i in range(1,n):
  if s[i]=='E':
    temp-=1
  if s[i-1]=='W':
    temp+=1
  if temp<ans:
    ans=temp
print(ans)

Measured memory_bytes: 3784
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long int
#define rep(i, n) for(int i = 0; i < n; i++)
#define repp(i, n) for(int i = 1; i <= n; i++)
#define sort(v) sort((v).begin(), (v).end())
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define riverse(v) reverse((v).begin(), (v).end())
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
using vll = vector<ll>;
const ll MOD = 1e9+7;
vi alphabet = {'a','b','c','d','e','f','g','h','i','j','k','l','m',
               'n','o','p','q','r','s','t','u','v','w','x','y','z'};

int main() {
    string N;
    int K;
    cin >> K >> N;
    if (N.size() <= K)cout << N << endl;
    else {
        N = N.substr(0, K);
        N = N + "...";
        cout << N << endl;
    }
}

Measured memory_bytes: 3628
#!/mnt/c/Users/moiki/bash/env/bin/python
n = int(input())
v = list(map(int, input().split()))
vodd = []
dodd = {}
veve = []
deve = {}

kind = 0
inst_kinds = {}
for e,i in enumerate(v):
    if e % 2 == 0:
        # veve.append(i)
        if not i in deve:
            deve[i] = 1
        else:
            deve[i] += 1
    else:
        # vodd.append(i)
        if not i in dodd:
            dodd[i] = 1
        else:
            dodd[i] += 1


for k in deve:
    veve.append((deve[k], k))
veve.append((0,0))
veve.sort()
veve.reverse()
for k in dodd:
    vodd.append((dodd[k], k))
vodd.append((0,0))
vodd.sort()
vodd.reverse()
from functools import reduce
from operator import add

# sum = reduce(add, [k[0] for k in vodd])
sum = n
# sum += reduce(add, [k[0] for k in veve])


if vodd[0][1] != veve[0][1]:
    sum -= vodd[0][0] + veve[0][0]
else:
    sum = min(n - vodd[1][0] - veve[0][0], 
             n - vodd[0][0] - veve[1][0])

print(sum)







Measured memory_bytes: 20892
k = int(input())
s = input()
n = len(s)
mod = 10**9 + 7

m = [1]*(k+1)
M = [1]*(k+1)
h = [1]*(k+1)
for i in range(k):
    m[i+1] = (m[i] * 25)%mod
    M[i+1] = (M[i] * 26)%mod
    h[i+1] = (h[i]*(n+i)*pow(i+1,mod-2,mod))%mod

ans = 0
for i in range(k+1):
    ans += m[i]*M[k-i]%mod*h[i]%mod
    ans %= mod
print(ans)


Measured memory_bytes: 196364
#include<bits/stdc++.h>
using namespace std;
#define MS(x, i) memset(x, i, sizeof x)
#define debug(x) cout << #x << ": " << x << endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define NOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

char F[200];

int nums[maxn];

ll f[maxn];
ll inv[maxn];

ll n, aa, bb;

inline ll read() {
    ll ret = 0, sgn = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-') sgn = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9'){
        ret = ret*10 + ch - '0';
        ch = getchar();
    } 
    return ret*sgn;
}

inline void write( ll x ) {
    ll tmp = x > 0 ? x : -x;
    if(x < 0) putchar('-');
    int cnt = 0;
    while(tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while(cnt > 0) putchar(F[--cnt]);
}

ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    ll res = exgcd(b, a % b, y, x);
    y -= (a / b) * x;

    return res;
}

ll Inv(ll a)
{
    ll d, x, y;
    d = exgcd(a, mod, x, y);
    if(d == 1)
        return (x % mod + mod) % mod;
    return -1;
}

ll qpow(ll a, ll b)
{
    ll base = a;
    ll ans = 1;
    
    while(b)
    {
        if(b & 1)
            ans = (ans * base) % mod;
        
        b >>= 1;
        base = (base * base) % mod;
    }

    return ans;
}

void init()
{
    f[0] = f[1] = 1;
    for(int i = 2; i < maxn; i++)
        f[i] = (f[i - 1] * i) % mod;
    
    inv[maxn - 1] = Inv(f[maxn - 1]);
    inv[0] = 1;

    for(int j = maxn - 2; j >= 1; j--)
        inv[j] = (inv[j + 1] * (j + 1)) % mod;
}

ll C(ll n, ll m)
{
    return (f[n] * (inv[m] * inv[n - m] % mod)) % mod;
}

int main()
{
    NOS
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    init();

    int n, k;
    cin >> n >> k;

    ll ans = 0;

    for(int i = 0; i <= min(n - 1, k); i++)
    {
        ans = (ans + C(n, i) * C(n - 1, n - i - 1)) % mod;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3328
#include <iostream>
#include <algorithm>
#include <cmath>
#include <functional>
#include <string>
#include <vector>
using namespace std;

#define int long long
#define rep(n, i) for (int i = 0; i < n; i++)
#define rep2(m, n, i) for (int i = m; i < n; i++)
#define rep_r(n, i) for (int i = n - 1; i >= 0; i--)

const int INF = 1L << 50;
const int MAX_N = 3001;

signed main() {
    int x, y, z, k;
    cin >> x >> y >> z >> k;
    int a[MAX_N], b[MAX_N], c[MAX_N];
    fill(a, a + MAX_N, -INF);
    fill(b, b + MAX_N, -INF);
    fill(c, c + MAX_N, -INF);
    int lossa[MAX_N], lossb[MAX_N], lossc[MAX_N];
    rep(x, i) {
        cin >> a[i];
    }
    rep(y, i) {
        cin >> b[i];
    }
    rep(z, i) {
        cin >> c[i];
    }
    sort(a, a + MAX_N, greater<int>());
    sort(b, b + MAX_N, greater<int>());
    sort(c, c + MAX_N, greater<int>());
    rep(MAX_N, i) {
        lossa[i] = a[i] - a[0];
        lossb[i] = b[i] - b[0];
        lossc[i] = c[i] - c[0];
    }
    sort(lossa, lossa + MAX_N, greater<int>());
    sort(lossb, lossb + MAX_N, greater<int>());
    sort(lossc, lossc + MAX_N, greater<int>());
    int pa = 0, pb = 0, pc = 0;
    vector<int> va, vb, vc;
    va.push_back(a[pa++]);
    vb.push_back(b[pb++]);
    vc.push_back(c[pc++]);
    while (pa * pb * pc <= min(1LL << 20, x * y * z)) {
        int next = 0;
        int maxi = lossa[pa];
        if (lossb[pb] > maxi) {
            next = 1;
            maxi = lossb[pb];
        }
        if (lossc[pc] > maxi) {
            next = 2;
            maxi = lossc[pc];
        }
        if (next == 0) {
            va.push_back(a[pa++]);
        } else if (next == 1) {
            vb.push_back(b[pb++]);
        } else {
            vc.push_back(c[pc++]);
        }
    }
    vector<int> vsum;
    rep(pa, i) {
        rep(pb, j) {
            rep(pc, k) {
                vsum.push_back(va[i] + vb[j] + vc[k]);
            }
        }
    }
    sort(vsum.begin(), vsum.end(), greater<int>());
    rep(k, i) {
        cout << vsum[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 18924
/**
 * author:    Ziel
 * created:   23.04.2020 20:19:46
**/

// ~zaletaet~

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>

#define fi first
#define se second
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back

using namespace std;

using ll = long long;
using ull = unsigned long long;
// using big = __int128_t; // -10^38...10^38
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;

const ll N = 1e5 + 123, MOD = 1e9 + 7, oo = 1e9 + 9, INF = 1e18 + 9;
const double EPS = 1e-9, PI = acos(-1); // 3.14159265358979323846
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1}, dy[] = {0, 0, 1, -1, 1, -1, -1, 1};

main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ll x;
	cin >> x;
	ll cur = 100;
	ll ans = 0;
	while (cur < x) {
		cur += (cur / 100);
		ans++;
	}
	cout << ans;
	return 0;
}

/*
	Raise your standard.
*/

Measured memory_bytes: 3668
#include <bits/stdc++.h>
#define x real()
#define y imag()
using namespace std;
typedef complex <double> point;
vector <point> po;
double dot(point a,point b){return a.x*b.x+a.y*b.y;}
double cross(point a,point b){return a.x*b.y-a.y*b.x;}

double get_area(){
  double res=0;
  for(int i=0;i<po.size();i++)res+=cross(po[i],po[(i+1)%po.size()])/2;
  return res;
}


int main(){
  int n;
  cin>>n;
  for(int i=0,a,b;i<n;i++)cin>>a>>b,po.push_back(point(a,b));
  printf("%.1f\n",get_area());
  return 0;
}

Measured memory_bytes: 1228
#include <bits/stdc++.h>
#define ll long long
using namespace std ;
#define MAX 800
const int N = 1e6 + 5 ;
//int arr[ N ] , L[ N ];
vector < ll > vc;
int main()
{
   string a , b ;
   cin >> a >> b ;
   string s = a + b ;
   stringstream num( s );
   int ab = 0 ;
   num >> ab ;
   int sq = sqrt( ab ) ;
   if(sq * sq == ab)
    cout << "Yes" << endl ;
   else
    cout << "No" << endl ;
}


Measured memory_bytes: 764
N = int(input())
T = list(map(int, input().split()))
M = int(input())
P = [list(map(int, input().split())) for i in range(M)]

sum = 0

for i in range(len(P)):
    t = T[P[i][0] - 1]
    T[P[i][0] - 1] = P[i][1]
    for j in T:
        sum += j
    print(sum)
    sum = 0
    T[P[i][0] - 1] = t


Measured memory_bytes: 3064
//----------------------------templates
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("tune=native")
    #pragma GCC target ("avx")
    //----------------------------
    #include <bits/stdc++.h>
    using namespace std;

    typedef long long ll;
    typedef unsigned long long ull;
    #define int ll

    #define FOR(i,j,n) for (int i=(int)(j);i<(n);i++)
    #define REP(i,n) for (int i=0;i<(int)(n);i++)
    #define REPS(i,n) for (int i=1;i<=(int)(n);i++)
    #define REPN(i,n) for (int i=(int)(n)-1;i>=0;i--)
    #define REPNS(i,n) for (int i=(int)(n);i>0;i--)

    #define I(n) scanf("%lld", &(n))
    #define LL(n) scanf("%lld", &(n))
    #define pb(n) push_back((n))
    #define mp(i,j) make_pair((i),(j))
    #define eb(i,j) emplace_back((i),(j))
    #define y0 y3487465
    #define y1 y8687969
    #define j0 j1347829
    #define j1 j234892
    #define uniq(v) v.erase( unique(v.begin(), v.end()), v.end() )

    #define all(x) (x).begin(),(x).end()
    #define sz(x) ((int)(x).size())

    typedef vector<int> vi;
    typedef pair<int,int> pi;
    typedef vector<pi> vpi;
    typedef vector<vi> vvi;
    typedef vector<vpi> vvpi;
    typedef vector<vvi> vvvi;

    const int mod = 1000000007;

//--------------------------------------------

ll facts[200010],invs[200010];
ll powll(ll base,ll power){
    ll ans = 1;
    while (power){
        if (power&1) ans = (base*ans)%mod;
        base = (base*base)%mod;
        power >>= 1;
    }
    return ans;
}
int ni,mi,k,n;
signed main(){
    I(ni); I(mi); I(k);
    n = ni*mi;

    ll f = 1;
    facts[0] = 1;
    FOR(i,1,n+1){
        f *= i;
        f %= mod;
        facts[i] = f;
    }
    ll inv = powll(f,mod-2);
    invs[n] = inv;
    REPNS(i,n){
        inv *= i;
        inv %= mod;
        invs[i-1] = inv;
    }

    int ret = 0;
    REP(i,ni) REP(j,mi){
        int dist = 0;
        
        dist += i * (i+1) / 2 * mi;
        int negi = ni-i-1;
        dist += negi * (negi+1) / 2 * mi;
        dist += j * (j+1) / 2 * ni;
        int negj = mi-j-1;
        dist += negj * (negj+1) / 2 * ni;
        dist %= mod;

        ret = (ret + dist) % mod;
    }
    int nck = (facts[n] * invs[k]) % mod;
    nck = nck * invs[n-k] % mod;
    int n1ck1 = (facts[n-1] * invs[k-1]) % mod;
    n1ck1 = n1ck1 * invs[n-k] % mod;
    cerr << nck << " " << n1ck1 << " " << ret << endl;

    int n1inv =  powll(n-1,mod-2);
    int ninv =  powll(n,mod-2);
    
    // ret = (ret * n1ck1) % mod;
    // ret = ret * n1inv % mod;
    // cerr << ret << endl;
    ret = ret * (k-1) % mod;
    cerr << ret << endl;

    ret = (ret * n1inv) % mod;
    cerr << ret << endl;

    ret = (ret * nck) % mod;
    ret = ret * k % mod;
    ret = ret * ninv % mod;

    ret = ret * powll(2,mod-2) % mod;
    // ret = ret * powll(n+1-k, mod-2) % mod;

    cout << ret << endl;
}

Measured memory_bytes: 3328
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <cstring>
#include <map> 
#include <set>
#include <queue>
#include <iomanip>
#include <sstream>
typedef long long ll;

#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;

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; }

const long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<ll, ll> P;
ll ma = 1000000000 + 7;
ll mx = 1000003;
ll h,n, w,m,t; string s;
ll R, C;
ll sy, sx, gy, gx;
char maze[510][510];
ll dis[20][20];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll gcd(ll x, ll y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);
}
ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
void comb(vector<vector <ll> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll 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])%ma;
		}
	}
}

ll GetDigit(ll num) {
	return log10(num) + 1;
}
ll Combination(int n, int r)
{
	if (n - r < r) r = n - r;
	if (r == 0) return 1;
	if (r == 1) return n;

	vector<ll> numerator(r);
	vector<ll> denominator(r);

	for (int k = 0; k < r; k++)
	{
		numerator[k] = n - r + k + 1;
		denominator[k] = k + 1;
	}

	for (int p = 2; p <= r; p++)
	{
		int pivot = denominator[p - 1];
		if (pivot > 1)
		{
			int offset = (n - r) % p;
			for (int k = p - 1; k < r; k += p)
			{
				numerator[k - offset] /= pivot;
				denominator[k] /= pivot;
			}
		}
	}

	ll result = 1;
	for (int k = 0; k < r; k++)
	{
		if (numerator[k] > 1) result *= numerator[k];
		result %= ma;
	}

	return result;
}
/*
ll bfs() {
	queue<P> que;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) dis[i][j] = INF;
	}
	que.push(P(sy - 1, sx - 1));
	dis[sy - 1][sx - 1] = 0;

	while (que.size() > 0) {
		P p = que.front();
		que.pop();
		if (p.first == gy - 1 && p.second == gx - 1) break;
		for (ll i = 0; i < 4; i++) {
			ll ny = p.first + dy[i];
			ll nx = p.second + dx[i];
			if (0 <= ny && ny < R && 0 <= nx && nx < C && maze[ny][nx] == '.' && dis[ny][nx] == INF) {
				que.push(P(ny, nx));
				dis[ny][nx] = dis[p.first][p.second] + 1;
			}
		}
	}
	return dis[gy - 1][gx - 1];
}*/

int main() {
	cin >> n;
	ll cnt = 0;
	ll p = n;
	ll flg = 1;
	for (ll i = 2; i*i <= n; i++) {

		ll k = 0; ll j = 0;
		while (n % i == 0) {
			if (j >= k) {
				++k;
				cnt++;
				j = 0;
			}
			else {
				j++;
			}
			n /= i;
		}
	}
	if (n > 1)++cnt;
	cout << cnt << endl;
}

Measured memory_bytes: 3740
#include<cstdio>
#include<iostream>
#include<map>
#include<algorithm>
#include<cstring>
#include<set>
using namespace std;
set<int> S;
const int N=2e5+11;
int len,nxt[N][26],now[26],now_tot[N],tot,tmp;
char s[N],ans[N];
int main(){
//	freopen("ex.in","r",stdin);
	scanf("%s",s+1);len=strlen(s+1);
	for(int i=len;i;i--){
		S.insert(s[i]-'a');
		now_tot[i]=tot;
		if(S.size()==26) tot++,S.clear();
	}
	if(!tot){
		for(int i=0;i<26;++i) if(S.count(i)==0){
			printf("%c",i+'a');
			return 0;
		}
	}
	for(int i=len;i;i--){
		for(int j=0;j<26;++j) nxt[i][j]=now[j];
		now[s[i]-'a']=i;
	}
	for(int i=0;i<26;++i){
		if(S.count(i)==0){
			printf("%c",i+'a');
			tmp=now[i];
			break;
		}
	}
	for(int i=1;i<=tot;++i){
		for(int j=0;j<26;++j){
			if(now_tot[tmp]-1==now_tot[nxt[tmp][j]]){
				printf("%c",j+'a');
				tmp=nxt[tmp][j];
				break;
			}
		}
	}
	for(int i=0;i<26;++i){
		if(nxt[tmp][i]==0){
			printf("%c",i+'a');
			break;
		}
	}
	return 0;
}

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

int main() {
 int n;
    cin >> n;
    vector<int> ans(n+1);
    
    for(int i = 1; i <= sqrt(n);i++) {
     for(int j = 1; j<= sqrt(n);j++){
       for(int k = 1; k<=sqrt(n);k++){
          int s = i*i+j*j+k*k+i*j+j*k+i*k;
           if(s > n) {
            break;
           }
           ans[s]++;   
      }
     }
    }
    
    for(int i = 1; i<=n;i++) {
     cout << ans[i] << endl;
    }
    
}

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

using namespace std;

#define N_CONTEST   (26)
#define N_DAY       (365)

static void get_input (int &D, vector<int> &c, vector<vector<int>> &s) {
    cin >> D;
    assert(D == N_DAY);
    for ( int i = 1; i <= N_CONTEST; i++ ) {
        cin >> c.at(i);
    }
    for ( int i = 1; i <= N_DAY; i++ ) {
        for ( int j = 1; j <= N_CONTEST; j++ ) {
            cin >> s.at(i).at(j);
        }
    }
}

static int calc_greedy_ans (vector<int> &c, vector<vector<int>> &s, vector<int> &last, int day) {
    int max_score = INT_MIN;
    int ans_c = 1;

    for ( int con = 1; con <= N_CONTEST; con++ ) {
        int score = s.at(day).at(con);
        for ( int con_ = 1; con_ <= N_CONTEST; con_++ ) {
            if ( con_ == con ) {
                continue;
            }
            score -= c.at(con_) * (day - last.at(con_));
        }
        if ( score > max_score ) {
            max_score = score;
            ans_c = con;
        }
    }

    last.at(ans_c) = day;

    return ans_c;
}

int main (void) {
    int D;
    vector<int> c(N_CONTEST+1);
    vector<vector<int>> s(N_DAY+1, vector<int>(N_CONTEST+1, 0));

    get_input(D, c, s);

    vector<int> last(N_CONTEST+1, 0);
    for ( int d = 1; d <= N_DAY; d++ ) {
        int greedy_c = calc_greedy_ans(c, s, last, d);
        cout << greedy_c << endl;
    }

    return 0;
}


Measured memory_bytes: 3652
n,m = map(int, input().split())
a = [input() for _ in range(n)]
b = [input() for _ in range(m)]
for i in range(n-m+1):
    for j in range(n-m+1):
        window = [x[i:i+m] for x in a[j:j+m]]
        if window == b:
            print('Yes')
            quit()
print('No')

Measured memory_bytes: 3060
from collections import deque

h, w = map(int, input().split())
grid = [input() for _ in range(h)]
visited = [[0]*w for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))

ans = 0
for i in range(h):
    for j in range(w):
        if not visited[i][j]:
            bcnt, wcnt = 0, 0
            q = deque([(i, j)])
            while q:
                cx, cy = q.popleft()
                if visited[cx][cy]:
                    continue
                if grid[cx][cy] == "#":
                    bcnt += 1
                else:
                    wcnt += 1
                visited[cx][cy] = 1
                for (dx, dy) in moves:
                    if 0 <= cx + dx < h and 0 <= cy + dy < w and not visited[cx + dx][cy + dy] and grid[cx + dx][cy + dy] != grid[cx][cy]:
                        q.append((cx + dx, cy + dy))
            ans += bcnt * wcnt
print(ans)

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

// #define multitest 1
#define Debug 1
#ifdef Debug
#define db(...) ZZ(#__VA_ARGS__, __VA_ARGS__);
template <typename Arg1>
void ZZ(const char *name, Arg1 &&arg1)
{
	std::cerr << name << " = " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void ZZ(const char *names, Arg1 &&arg1, Args &&... args)
{
	const char *comma = strchr(names + 1, ',');
	std::cerr.write(names, comma - names) << " = " << arg1;
	ZZ(comma, args...);
}
#else
#define db(...)
#endif

typedef long long ll;
typedef long double ld;
#define f first
#define s second
#define pb push_back
const long long mod = 1000000007;

ll power(int base, int index)
{
	if (index == 0)
		return 1;
	ll temp = power(base, index / 2);
	temp = (temp * temp) % mod;
	if (index & 1)
		temp *= base;
	return temp % mod;
}

string l;
ll solve(int index, int length)
{
	if (length == 1)
	{
		if (index >= l.length())
		{
			cout << "Wrong";
			exit(0);
		}
		if (l[index] == '0')
			return 1;
		else
			return 3;
	}
	ll answer = 0;
	if (l[index] == '1')
		answer += power(3, length - 1);
	answer %= mod;
	if (l[index] == '1')
		answer = (answer + 2 * solve(index + 1, length - 1)) % mod;
	else
		answer = (answer + solve(index + 1, length - 1)) % mod;
	// db(length, answer);
	return answer;
}

void solve()
{
	cin >> l;
	// int n = 0;
	// for (char c : l)
	// 	n = n * 2 + (c - '0');
	// int cnt = 0;
	// for (int i = 0; i <= n; ++i)
	// 	for (int j = 0; j <= n; ++j)
	// 	{
	// 		if (i + j <= n)
	// 		{
	// 			if ((i + j) == (i ^ j))
	// 			{
	// 				cnt++;
	// 				cout << i << ' ' << j << '\n';
	// 			}
	// 		}
	// 	}
	// cout << cnt << '\n';
	cout << solve(0, l.length()) << '\n';
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
#ifdef multitest
	cin >> t;
#endif
	while (t--)
		solve();
	return 0;
}

Measured memory_bytes: 5200
N = int(input())
h = list(map(int,input().split()))
dp = [0,abs(h[0]-h[1])]
for i in range(2,N):
  a = dp[i-1] + abs(h[i]-h[i-1])
  b = dp[i-2] + abs(h[i]-h[i-2])
  dp.append(min(a,b))
print(dp[N-1])

Measured memory_bytes: 13908