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

int win(string s, string t, int cur, int d){
	int a = 0;
	int b = d + 1;
	reverse(t.begin(), t.end());
	reverse(s.begin(), s.end());
	for(int i = 0; i < s.size(); i++){
		if(t[i] == 'L' || t[i] == 'U'){
			b++;
		} else if(t[i] == 'R' || t[i] == 'D'){
			a--;
		}
		a = max(a, 0);
		b = min(b, d+1);
		if(a >= b-1) return 1;
		if(s[i] == 'L' || s[i] == 'U'){
			a++;
		} else if(s[i] == 'R' || s[i] == 'D'){
			b--;
		}
		if(a >= b-1) return 1;
	}

	if(cur <= a || cur >= b) return 1;
	return 0;
}


int main(){
	int h, w, n;
	cin >> h >> w >> n;
	int sx, sy;
	cin >> sx >> sy;
	string s, t;
	cin >> s >> t;
	string s1, t1, s2, t2;
	for(int i = 0; i < n; i++){
		if(s[i] == 'L' || s[i] == 'R'){
			s1 += s[i]; s2 += 'X';
		} else {
			s1 += 'X'; s2 += s[i];
		}
		if(t[i] == 'L' || t[i] == 'R'){
			t1 += t[i]; t2 += 'X';
		} else {
			t1 += 'X'; t2 += t[i];
		}
	}
	if(win(s1, t1, sy, w) || win(s2, t2, sx, h)){
		cout << "NO" << '\n';
	} else {
		cout << "YES" << '\n';
	}
}

Measured memory_bytes: 2444
#include <bits/stdc++.h>
using namespace std;
int main(){
 int A,B,C,D;
 cin>>A>>B>>C>>D;
 int L,R;
 L= A+B;
 R= C+D;
 if(L>R){
  cout<<"Left"<<endl;
 }
 else if(L<R){
   cout<<"Right"<<endl;
 }
 else{
  cout<<"Balanced"<<endl;
 }
}

Measured memory_bytes: 3544
N = gets.to_i
A = gets.split(" ").map(&:to_i)
r = true

A.each do |a|
  next unless  a % 2 == 0

  unless (a % 3 == 0 or a % 5 == 0)
    r = false
    break
  end
end

if r
  puts("APPROVED")
else
  puts("DENIED")
end

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct union_find {
  std::vector<int> rank, par;
  int v_size;
  union_find() {}

  // 初期化
  union_find(int n) {
    v_size = n;
    rank.resize(n, 0);
    par.resize(n);
    for(int i=0;i<n;i++) {
      par[i] = i;
    }
  }

  // 木の根を求める
  int find(int x) {
    if(par[x] == x) {
      return x;
    } else {
      return par[x] = find(par[x]);
    }
  }

  // xとyの属する集合を併合
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;

    if(rank[x] < rank[y]) {
      par[x] = y;
    } else {
      par[y] = x;
      if(rank[x] == rank[y]) rank[x]++;
    }
  }

  // xとyが同じ集合に属するか否か
  bool same(int x, int y) {
    return find(x) == find(y);
  }

  // グループの個数を数える
  int count() {
    std::set<int> st;
    for(int i=0;i<v_size;i++) {
      st.insert(find(i));
    }
    return st.size();
  }

};
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n, m;
  cin >> n >> m;
  union_find uf(n);
  vector<int> v[m];
  for(int i=0;i<n;i++) {
    int k;
    cin >> k;
    for(int j=0;j<k;j++) {
      int li;
      cin >> li;
      li--;
      v[li].push_back(i);
    }
  }
  for(int i=0;i<m;i++) {
    for(int j=1;j<v[i].size();j++) {
      uf.unite(v[i][0], v[i][j]);
      //cout << "i: " << i << " j: " << j  <<" " << v[i][j] << endl;
    }
  }
  if(uf.count() > 1)
    cout << "NO" << endl;
  else
    cout << "YES" << endl;
  /*
  for(int i=0;i<n;i++) 
    cout << "find(i): " << uf.find(i) << endl;
    */
}


Measured memory_bytes: 4608
import  math
A, B, H, M = map(int, input().split())

s = 60 * H + M
r1 = 2 * math.pi * s / 720
r2 = 2 * math.pi * M / 60

r = abs(r1 - r2)
r = min (r, 2 * math.pi - r)

print( (A * A + B * B - 2 * A * B *math.cos(r)) ** 0.5)

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

void new_call(int n)
{
    for (int i = 1; i <= n; i++)
    {
        if (i % 3 == 0)
        {
            cout << " " << i;
            continue;
        }

        if (i % 10 == 3)
        {
            cout << " " << i;
            continue;
        }

        int x = i / 10;
        bool found = false;
        while (x > 0)
        {
            if (x % 10 == 3)
            {
                cout << " " << i;
                found = true;
            }
            if (found)
            {
                break;
            }
            x = x / 10;
        }
    }
    cout << endl;
}

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

    int n;
    cin >> n;
    new_call(n);

    return 0;
}



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

using namespace std;
#define ms(x,a) memset(x,a,sizeof x)
typedef long long ll;
typedef pair<int,int> pii;
const int mod=1e9+7,seed=131,MAXN=0;

int h,w,k; bool arr[6][6];

bool check(int a, int b){
    int cnt=0;
    for (int i=0;i<h;++i){
        for (int j=0;j<w;++j){
            cnt+=(!((1&(a>>i))||(1&(b>>j)))&&arr[i][j]);
        }
    }
    return cnt==k;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> h >> w >> k;
    for (int i=0;i<h;++i){
        for (int j=0;j<w;++j){
            char a; cin >> a;
            arr[i][j]=a=='#';
        }
    }
    int ans=0;
    for (int mask1=0;mask1<1<<h;++mask1){
        for (int mask2=0;mask2<1<<w;++mask2){
            ans+=check(mask1,mask2);
        }
    }
    cout << ans << '\n';
}

Measured memory_bytes: 3572
import std.stdio, std.conv, std.string, std.bigint;
import std.math, std.random, std.datetime;
import std.array, std.range, std.algorithm, std.container, std.format;
string read(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }

/*

（1からNではなく、0からN-1として考える）

0からiまでを並べ、s[0 .. i] に従い、最後が j で終わる場合の数をxs[i][j]とする

xs[0][0] = 1
xs[0][j] = 0

s[i] = '<' の場合
xs[i][j] = sum(j'; 0 .. j) xs[i - 1][j']

s[i] = '>' の場合
xs[i][j] = sum(j'; j .. i) xs[i - 1][j']

このsumは愚直にループを回すとTLEになるが、累積和ならOK

求めるものは sum(j; 0 .. j) xs[n][j]

----------------------------------------

*/

const mod = 1_000_000_007;

void main(){
	long n = read.to!long;
	string s = readln.chomp;
	
	long[][] xs = new long[][](n, n);
	xs[0][0] = 1;
	debug writeln("i:", 0, " xs:", xs);
	
	foreach(i; 1 .. n){
		if(s[i - 1] == '<'){
			long sum = 0;
			foreach(j; 0 .. i + 1){
				if(j > 0) sum += xs[i - 1][j - 1], sum %= mod;
				debug writeln("i:", i, " j:", j, " sum:", sum);
				xs[i][j] = sum;
			}
		}
		else{
			long sum = 0;
			foreach_reverse(j; 0 .. i + 1){
				if(j < i) sum += xs[i - 1][j], sum %= mod;
				debug writeln("i:", i, " j:", j, " sum:", sum);
				xs[i][j] = sum;
			}
		}
		debug writeln("i:", i, " xs:", xs);
	}
	
	long ans = 0;
	foreach(j; 0 .. n) ans += xs[n - 1][j], ans %= mod;
	
	ans.writeln;
}


Measured memory_bytes: 74108
class Dice:
    def __init__(self, eyes):
        self._eyes = ['dummy'] + eyes

    @property
    def eye(self):
        return self._eyes[1]

    def roll(self, direction):
        a = self._eyes
        if direction == 'N':
            self._eyes = ['dummy', a[2], a[6], a[3], a[4], a[1], a[5]]
        elif direction == 'S':
            self._eyes = ['dummy', a[5], a[1], a[3], a[4], a[6], a[2]]
        elif direction == 'W':
            self._eyes = ['dummy', a[3], a[2], a[6], a[1], a[5], a[4]]
        elif direction == 'E':
            self._eyes = ['dummy', a[4], a[2], a[1], a[6], a[5], a[3]]
        else:
            raise ValueError('NEWS箱推し')


eyes = input().split()
dice = Dice(eyes)

direction_text = input()
for d in direction_text:
    dice.roll(d)

print(dice.eye)



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

int main(){
  string S;
  cin >> S;
  char a,b;
  int acount = 0;
  int bcount = 0;
  a = S[0];
  if(S[1]!=a){
    b = S[1];
  }
  if(S[1]==a){
    if(S[2]!=a){
      b = S[2];
    }
    else{
      acount = 3;
      bcount = 3;
    }
  }
  for(int i=0;i<4;i++){
    if(S[i]==a){
      acount ++;
    }
    if(S[i]==b){
      bcount ++;
    }
  }
  if(acount == 2&&bcount == 2){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
  return 0;
}

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

#define ll              long long
#define pb              push_back
#define ff              first
#define ss              second
#define mp              make_pair

#define scan(a)         scanf("%d", &a)
#define scanl(a)        scanf("%lld", &a)
#define scand(a)        scanf("%lf", &a)
#define scan2(a, b)     scanf("%d %d", &a, &b)
#define scanl2(a, b)    scanf("%lld %lld", &a, &b)
#define scand2(a, b)    scanf("%lf %lf", &a, &b)

#define yes             cout << "Yes\n"
#define no              cout << "No\n"
#define Case(i)         cout << "Case " << int(i) << ": "

#define lop(n)          for(int i = 0; i < n; i++)
#define lopj(n)         for(int j = 0; j < n; j++)
#define lopr(a, n)      for(int k = a; k < n; k++)
#define lrev(n, a)      for(int i = n; i >= a; i--)

#define all(x)          x.begin(), x.end()
#define mem(a, b)       memset(a, b, sizeof(a))

#define vin             vector <int>
#define vll             vector <ll>
#define vst             vector <string>
#define pll             pair <ll, ll>
#define pss             pair <string, string>
#define vpll            vector <pll>

#define fread           freopen("input.txt", "r", stdin)
#define fwrite          freopen("output.txt", "w", stdout)
#define fastio          ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

#define mod             1000000007
#define PI              acos(-1.0)
#define inf             999999999999


using namespace std;


int main()
{
    fastio;

    int tt, n;

    cin >> tt;

    if(tt >= 30)
        yes;
    else
        no;
    

    return 0;
}



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

int main(){
    int N;
    cin >> N;
    vector<int> X(N),X2(N);
    rep(i,N){
        cin >> X[i];
        X2[i] = X[i];
    }
    sort(X.begin(),X.end());
    for(int i=0;i<N;i++){
        if(X2[i]<X[N/2]){
            cout << X[N/2] << endl;
        }else{
            cout << X[N/2-1] << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 3712
m = []
for _ in range(3):
	m.append(list(map(int, input().split())))
n = int(input())
nums = set()
for _ in range(n):
	nums.add(int(input()))

flag = True
#Row
for r in m:
	count = 0
	for elem in r:
		if elem in nums:
			count += 1
	if (count == len(r)):
		flag = False
		break

if flag:
	for r in zip(*m):
		count = 0
		for elem in r:
			if elem in nums:
				count += 1
		if (count == len(r)):
			flag = False
			break
if flag:
	count = 0
	for i in range(3):
		if m[i][i] in nums:
			count += 1
	if (count == 3):
		flag = False
if flag:
	if len({m[0][2],m[1][1],m[2][0]} & nums)==3:
		flag=False
if flag:
	print("No")
else:
	print("Yes")

Measured memory_bytes: 3064
# -*- coding: utf-8 -*-

# input
N, Y = map(int, input().split())

# solve
ans = [-1] * 3
for x in range(N + 1):
    for y in range(N + 1):
        z = N - x - y
        if 10000 * x + 5000 * y + 1000 * z == Y and z >= 0:
            ans = [x, y, z]
            break

# output
print(*ans)


Measured memory_bytes: 2940
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
using namespace std;
#define pie 3.141592653589793238462643383279
#define int long long
#define mod 1000000007
#define INF 1145141919364364
#define all(vec) vec.begin(),vec.end()
#define P pair<int,int>
#define S second
#define F first
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
bool prime(int x) {
	for (int i = 2; i <= sqrt(x); i++) {
		if (x%i == 0)return false;
	}
	return true;
}
int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1) * x % mod;
}
int mod_pow(int x, int y, int mood) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mood;
		}
		x = x * x % mood;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x)* mod_pow(kai(x - y), mod - 2, mod) % mod * mod_pow(kai(y), mod - 2, mod) % mod;
}

int n, m, s, t;
vector<int> e[100010];
bool bl[100010][3];
int ans;

void bfs(int x, int y) {
	queue<P> que;
	que.push({ x,0 });
	while (!que.empty()) {
		P p = que.front(); que.pop();
		int c = p.first, d = p.second;
		if (c == y && !(d % 3)) {
			ans = d / 3;
			return;
		}
		if (!bl[c][d % 3]) {
			for (int i = 0; i < (int)e[c].size(); i++) {
				que.push({ e[c][i],d + 1 });
			}
		}
		bl[c][d % 3] = true;
	}
	ans = -1;
	return;
}

signed main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		e[a].push_back(b);
	}
	cin >> s >> t;
	bfs(s, t);
	cout << ans << endl;
}

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

int main()
{
	long long W, H, res = 0;
	cin >> W >> H;
	vector<long long> p(W), sum(W);
	for (int i = 0; i < W; i++) {
		cin >> p[i];
		res += p[i];
	}
	sort(p.begin(), p.end());
	sum[0] = p[0];
	for (int i = 1; i < W; i++) {
		sum[i] = sum[i - 1] + p[i];
	}
	for (int j = 0, qj; j < H; j++) {
		cin >> qj;
		res += qj;
		auto ub = upper_bound(p.begin(), p.end(), qj);
		if (ub != p.begin()) {
			res += sum[ub - p.begin() - 1];
			res += qj * (W - (ub - p.begin()));
		}
		else {
			res += qj * W;
		}
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 1792
#include<stdio.h>
#include <iomanip>
#include <iostream>
#include<string>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include <random>
#include <chrono>

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

using namespace std;
int main() {
	string s,ans;
	cin >> s;
	if (s == "Sunny")ans = "Cloudy";
	else if (s == "Cloudy")ans = "Rainy";
	else ans = "Sunny";
	cout << ans;

}

Measured memory_bytes: 256
n = gets.to_i
arr = gets.split(" ").map(&:to_i).sort

count = 0
n.times do |i|
  (n-i-1).times do |i2|
    j = i2 + i + 1
    (n-i-i2-1).times do |i3|
      k = i3 + i2 + i + 1
      if i != j && j != k && k != i && arr[i] != arr[j] && arr[j] != arr[k] && arr[k] != arr[i] && arr[i] + arr[j] > arr[k]
        count += 1
      end
    end
  end
end
      
puts count


Measured memory_bytes: 14352
//Andrew Yang
#include <iostream>
#include <stdio.h>
#include <sstream>
#include <fstream>
#include <string>
#include <string.h>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>	
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <climits>
using namespace std;
#define FOR(index, start, end) for(int index = start; index < end; ++index)
#define RFOR(index, start, end) for(int index = start; index > end; --index)
#define FOREACH(itr, b) for(auto itr = b.begin(); itr != b.end(); ++itr)
#define RFOREACH(itr, b) for(auto itr = b.rbegin(); itr != b.rend(); ++itr)
#define INF 1000000000
#define M 1000000007
typedef long long ll;
typedef pair<int, int> pii;
int a[100001];
int main(void)
{
	int n;
	scanf("%d", &n);
	FOR(i, 0, n)
	{
		scanf("%d", &a[i]);
	}
	int start = 0;
	int ans = 1;
	bool up = false;
	bool down = false;
	FOR(i, 0, n)
	{
		if (i - start >= 1)
		{
			if (a[i] > a[i - 1])
			{
				up = true;
				if (down)
				{
					start = i;
					ans++;
					up = false;
					down = false;
				}
			}
			else if (a[i] < a[i - 1])
			{
				down = true;
				if (up)
				{
					start = i;
					ans++;
					up = false;
					down = false;
				}
			}
		}
	}
	cout << ans	<< endl;
}

Measured memory_bytes: 640
#include <iostream>
#include<sstream>
#include<vector>
#include<iterator>
using namespace std;

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

	long long ret = min(N, M/2);
	ret += (M - 2*ret)/4;

	cout << ret << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <numeric>
#include <queue>
#include <string>
#include <vector>

int main(){
    int x;
    std::cin >> x;

    std::cout << ((x == 7 || x == 5 || x == 3) ? "YES" : "NO") << std::endl;

    return 0;
}

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


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

int main() {
    int x,y;
    cin>>x>>y;
    for (int i = 0; i <= x; i++){
        if(i*2+(x-i)*4==y){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
}

Measured memory_bytes: 3636
#include<stdio.h>
int n,A[50];
//入力値のMから選んだ要素を引いていく再帰関数
int solve(int i,int m){
    if(m==0) return 1;
    if(i >= n) return 0;
    int res = solve(i + 1,m) || solve(i+1,m-A[i]);
    return res;
}

int main(){
    int q,M,i;

    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d",&A[i]);
    scanf("%d",&q);
    for(i=0;i<q;i++){
        scanf("%d",&M);
        if(solve(0,M)) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}


Measured memory_bytes: 2144
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Edge = pair<int, int>;
using Graph = vector<vector<Edge>>;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
const ll MOD = 1000000007;
const ll nmax = 8;
const ll INF = 1e9;
bool graph[nmax][nmax];
vector<vector<ll>> dist = vector<vector<ll>>(nmax, vector<ll>(nmax, INF));
void warshall_floyd(ll n)
{
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            for (size_t k = 0; k < n; k++)
            {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
}

class UnionFind
{
  public:
    vector<ll> Parent;

    UnionFind(ll N)
    {
        Parent = vector<ll>(N, -1);
    }
    ll find(ll A)
    {
        if (Parent[A] < 0)
            return A;
        return Parent[A] = find(Parent[A]);
    }

    ll size(ll A)
    {
        return -Parent[find(A)];
    }

    bool Union(ll A, ll B)
    {
        A = find(A);
        B = find(B);
        if (A == B)
        {
            return false;
        }
        if (size(A) < size(B))
            swap(A, B);

        Parent[A] += Parent[B];
        Parent[B] = A;

        return true;
    }
};

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

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

ll mulMod(ll a, ll b)
{
    return (((a % MOD) * (b % MOD)) % MOD);
}

ll powMod(ll a, ll p)
{
    if (p == 0)
    {
        return 1;
    }
    else if (p % 2 == 0)
    {
        ll half = powMod(a, p / 2);
        return mulMod(half, half);
    }
    else
    {
        return mulMod(powMod(a, p - 1), a);
    }
}

ll ceil(ll a, ll b)
{
    return (a + b - 1) / b;
}


void solve(long long N, long long A, long long B){
    cout << min(N*A,B) << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    solve(N, A, B);
    return 0;
}


Measured memory_bytes: 256
N, M = map(int, input().split(' '))

ans = [-1] * N

for m in range(M):
    s, c = map(int, input().split(' '))
    if s == 1 and c == 0:
        if N == 1:
            print(0)
        else:
            print(-1)
        exit(0)
    if ans[s - 1] != -1 and ans[s - 1] != c:
        print(-1)
        exit(0)
    ans[s - 1] = c


if ans[0] == -1:
    if N == 1:
        print(0)
        exit(0)
    ans[0] = 1

if ans[0] == 0 and N != 1:
    print(-1)
    exit(0)

for i in range(1, N):
    if ans[i] == -1:
        ans[i] = 0

ANS = int(''.join(map(str, ans)))

print(ANS)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using vint = vector<int>;
using vll = vector<ll>;
using uint = unsigned int;
using ull = unsigned long long;
 
template<typename T> using uset = unordered_set<T>;
template<typename T1, typename T2> using umap = unordered_map<T1, T2>;
 
constexpr int INF = (1 << 30) - 1;
constexpr ll LLINF = 1LL << 60;
constexpr int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr char el = '\n';
constexpr int mod = 1000000007;
 
template<typename T> T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }
template<typename T> T lcm(T a, T b) { return (a / gcd(a, b) * b); }
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }
 
template<typename T>
ostream& operator <<(ostream &os, vector<T> &v) {
        for (auto &u : v) os << u << el;
        return (os);
}
 
template<typename T>
istream& operator >>(istream &is, vector<T> &v) {
        for (auto &u : v) is >> u;
        return (is);
}
 
template<typename T1, typename T2>
istream& operator >>(istream &is, pair<T1, T2> &p) {
        return (is >> p.first >> p.second);
}
 
int main() {
        int H, W; cin >> H >> W;
        vector<vint> S(H, vint(W)); cin >> S;
        vector<vint> sum(H, vint(W+1, 0));
        for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                        if (S[i][j] == 0) {
                                sum[i][j] = 1;
                                if (i) sum[i][j] += sum[i-1][j];
                        }
                }
                sum[i][W] = 0;
        }
         
        int maxv = 0;
        for (int i = 0; i < H; i++) {
                //longest area rectangle
                stack<Pi> st;
                for (int j = 0; j <= W; j++) {
                        int minv = j;
                        while (!st.empty() && st.top().first > sum[i][j]) {
                                auto dat = st.top(); st.pop();
                                chmax(maxv, dat.first * (j - dat.second));
                                chmin(minv, dat.second);
                        }
                        st.emplace(sum[i][j], minv);
                }
        }
        cout << maxv << endl;
        return (0);
}


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

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

    int n; cin >> n;
    vector<int> a(n);
    int sum = 0;
    int minV = 1e9;
    int maxV = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sum += a[i];
        minV = min(minV, a[i]);
        maxV = max(maxV, a[i]);
    }

    int ans = 1e9;
    for (int v = minV; v <= maxV; ++v) {
        int cost = 0;
        for (int i = 0; i < n; ++i) {
            cost += (a[i] - v) * (a[i] - v);
        }
        ans = min(ans, cost);
    }

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

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
using P = pair<ll, ll>;
using V = vector<ll>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i, n) for(ll i=1;i<=(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rep3(i, m, n) for(ll i=m;i<=(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define MOD 1000000007
#define INF 1000000000
#define LLINF 1000000000000000000

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

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const ll mod = MOD;
struct mint {
	ll x; // typedef long long ll;
	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 {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint a) const {
		mint res(*this);
		return res *= 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 {
		mint res(*this);
		return res /= a;
	}
};

ll dp[100005];

void solve_abc_d() {
	ll n;
	ll wm;

	cin >> n >> wm;
	V w(n), v(n);
	rep(i, n) {
		cin >> w[i] >> v[i];
	}

	dp[0] = 0;
	rep(i, n) {
		rrep(j, wm, 1) {
			if (j - w[i] >= 0) {
				chmax(dp[j], dp[j - w[i]] + v[i]);
			}
		}
	}

	cout << dp[wm] << "\n";

	return;
}

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

	solve_abc_d();

	return 0;
}


Measured memory_bytes: 4408
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<pair<string,int>> vpsi;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define fin(ans) cout<<(ans)<<endl
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p,q)
#define pb(n) push_back(n)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define Sort(a) sort(a.begin(),a.end())
#define Rort(a) sort(a.rbegin(),a.rend())
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 int P = 1000000007;
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;

bool isPrime(int x){
    int i;
    if(x < 2)return 0;
    else if(x == 2) return 1;
    if(x%2 == 0) return 0;
    for(i = 3; i*i <= x; i += 2) if(x%i == 0) return 0;
    return 1;
}

int main(void){ios::sync_with_stdio(false);cin.tie(0);
//////////////////////////////////////////////////////

int x;
cin >> x;
int i;
for(i=x;;++i){
    if(isPrime(i))break;
}
fin(i);

//////////////////////////////////////////////////////
return 0;}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    static Scanner sc = new Scanner(System.in);
    static int H, N, P, M, K;
 
    public static void main(String[] args) throws Exception {
        H = sc.nextInt();
        N = sc.nextInt();
        P = sc.nextInt() - 1;
        M = sc.nextInt();
        K = sc.nextInt();
        int[] bridge = new int[H];
        Arrays.fill(bridge, -1);
        for (int i = 0; i < M; ++i) {
            int A = sc.nextInt() - 1;
            int B = sc.nextInt() - 1;
            bridge[A] = B;
        }
        double[][] prob = new double[K + 1][N];
        prob[0][P] = 1.0;
        int rest = H - M;
        for (int i = H - 1; i >= 0; --i) {
            if (bridge[i] != -1) {
                for (int j = 0; j <= K; ++j) {
                    swap(prob[j], bridge[i], bridge[i] + 1);
                }
            } else {
                double[][] next = new double[K + 1][N];
                for (int j = 0; j <= K; ++j) {
                    double select = 1.0 * (K - j) / rest;
                    for (int k = 0; k < N; ++k) {
                        next[j][k] += prob[j][k] * (1.0 - select);
                    }
                    if (j < K) {
                        next[j + 1][0] += select * (prob[j][0] * (N - 2) / (N - 1) + prob[j][1] / (N - 1));
                        for (int k = 1; k < N - 1; ++k) {
                            next[j + 1][k] += select * (prob[j][k] * (N - 3) / (N - 1) + prob[j][k - 1] / (N - 1) + prob[j][k + 1] / (N - 1));
                        }
                        next[j + 1][N - 1] += select * (prob[j][N - 1] * (N - 2) / (N - 1) + prob[j][N - 2] / (N - 1));
                    }
                }
                prob = next;
                --rest;
            }
        }
        double ans = 0;
        for (int i = 0; i < N; ++i) {
            ans = Math.max(ans, prob[K][i]);
        }
        System.out.println(ans);
    }
 
    static void swap(double[] a, int i, int j) {
        double tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
 
}

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

int main(){
    int n;
    cin>>n;
    int ans=0;
    if(n==100000)ans=90909;
    else if(n<100000&&n>=10000)ans=909+(n-9999);
    else if(n<10000&&n>=1000)ans=909;
    else if(n<1000&&n>=100)ans=9+(n-99);
    else if(n<100&&n>=10)ans=9;
    else if(n<10)ans=n;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3636
//author rhythmicankur
                                                                  //god_is_almighty
#pragma GCC optimize("O3")
#pragma GCC target ("sse4")
#include<bits/stdc++.h>
#define f 		first
#define s 		second
#define int     long long
#define ll      int
#define ld 		long double
#define pb 		push_back
#define eb 		emplace_back
#define mk 		make_pair
#define vi 		vector<int>
#define pii 		pair<int,int>
#define pip             pair<int,pii>
#define vpi 		vector<pii>
#define sbcount(x) __builtin_popcountll(x)
#define REP(i,n) for (int i = 1; i <= n; i++)
#define trav(a, x)      for(auto& a : x)
#define all(x)          x.begin(), x.end()
#define fill(a,val)	memset(a,val,sizeof(a))
#define 	PI acos(-1)
#define coud(a,b) cout<<fixed << setprecision((b)) << (a)
#define M1 	998244353
#define M2 	1000000007
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;

template<typename T> T gcd(T a,T b) { if(a==0) return b; return gcd(b%a,a); } 
#define test4(x,y,z,a) 		    cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<"  |  "<<#a<<": "<<a<<endl;
#define test1(x)                cerr<<#x<<": "<<x<<endl
#define test2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define test3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
ll power(ll a,ll b,ll m=M2){ll answer=1;while(b){if(b&1)answer=(answer*a)%m;b/=2;a=(a*a)%m;}return answer;}
using namespace std;
void ctrl(){cout<<"Control"<<endl;}
int make_num(string p){stringstream geek(p); int x = 0; geek >> x;return x;}
string make_str(int x){ostringstream str1; str1 << x; string geek = str1.str(); return geek;}

signed main()
{	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin.exceptions(cin.failbit);
	int n;
    cin>>n;
    int cnt=0;
    vector<int>v;
    int nt=n;
    for(int i=2;i<=sqrt(n);i++)
    {
        while(nt%i==0)
        {
            nt=nt/i;
            cnt++;
        }
        
        if(cnt)
        {
            v.pb(cnt);
           // test2(i,cnt);
        }
        cnt=0;
    }
    if(nt!=1)
    {
        v.pb(1);
       // test2(n,1);
    }
    int ans=0;
    for(auto it:v)
    { //cout<<it<<" ";
        int x=it;
        for(int i=1;i<=it;i++)
        {
            if(x<i)
            break;
            x-=i;
            ans++;
        }
    }
    cout<<ans;

return 0;
}

Measured memory_bytes: 3660
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextStr() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)
	k := nextInt()
	n := nextInt()
	a := make([]int, n)
	for i := range a {
		a[i] = nextInt()
	}

	//通らない区間(隣り合う家の距離が最大)の距離を求める
	dist, max := 0, 0
	for i := 1; i < n; i++ {
		dist = a[i] - a[i-1]
		if dist > max {
			max = dist
		}
	}
	//1番目の家とN番目の家の距離は計算式が異なる
	if k - a[n-1] + a[0] > max {
		max = k - a[n-1] + a[0]
	}
	//湖の外周距離から通らない区間の距離を引く
	fmt.Println(k - max)
}


Measured memory_bytes: 3840
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM
import qualified Data.ByteString.Char8 as C
import Data.List
import Control.Monad

r' :: IO [Int]
r' = unfoldr (C.readInt . C.dropWhile (==' ')) <$> C.getLine


type UF = (Parent,Rank,Size)
type Parent = UM.IOVector Int
type Rank   = UM.IOVector Int
type Size   = UM.IOVector Int

makeset :: Int -> IO UF
makeset n = do
    par <- U.thaw (U.generate n id)
    rnk <- UM.replicate n 0
    siz <- UM.replicate n 1
    return (par,rnk,siz)

root :: UF -> Int -> IO Int
root uf@(par,_,_) n = do
    x <- UM.read par n
    if x == n then return x else root uf x

same :: UF -> Int -> Int -> IO Bool
same uf x y = do
    rx <- root uf x
    ry <- root uf y
    return (rx == ry)

size :: UF -> Int -> IO Int
size uf@(par,rnk,siz) x = do
    r <- root uf x
    UM.read siz r

unite :: UF -> Int -> Int -> IO ()
unite uf@(par,rnk,siz) x y = do
    b <- same uf x y
    when (not b) $ do
        tx <- root uf x
        ty <- root uf y        
        rx <- UM.read rnk tx
        ry <- UM.read rnk ty
        sx <- size uf tx
        sy <- size uf ty
        if rx < ry then UM.write par tx ty >> UM.write siz ty (sx+sy)
        else UM.write par ty tx >> when (rx == ry) (UM.modify rnk succ tx) >> UM.write siz tx (sx+sy)


main :: IO ()
main = do
    [n,m,k] <- r'

    uf <- makeset n
    fc <- UM.replicate n 0
    bc <- UM.replicate n 0

    replicateM_ m $ do
        [a,b] <- map pred <$> r'
        unite uf a b
        UM.modify fc succ a
        UM.modify fc succ b
    replicateM_ k $ do
        [c,d] <- map pred <$> r'
        b <- same uf c d
        when b $ do
            UM.modify bc succ c
            UM.modify bc succ d

    putStrLn =<< unwords <$> mapM (\i -> do
        s <- size uf i
        f <- UM.read fc i
        b <- UM.read bc i
        return $ show (s-f-b-1)
        ) [0..n-1]

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

int main() {
  int N, M, Q; cin >> N >> M >> Q;
  auto v = vector<vector<int>>(N + 2, vector<int>(N + 2, 0));
  for (int i = 0; i < M; ++i) {
    int L, R; cin >> L >> R;
    v[L][R] += 1;
  }
  for (int i = 0; i <= N; ++i) {
    for (int j = 0; j <= N; ++j) v[i + 1][j] += v[i][j];
  }
  for (int i = 0; i <= N; ++i) {
    for (int j = 0; j <= N; ++j) v[i][j + 1] += v[i][j];
  }
  for (int i = 0; i < Q; ++i) {
    int p, q; cin >> p >> q;
    cout << v[q][q] - v[p - 1][q] - v[q][p - 1] + v[p - 1][p - 1] << endl;
  }
  return 0;
}


Measured memory_bytes: 1920
n = int(input())
csf = [list(map(int, input().split())) for _ in range(n - 1)]

for i in range(n):
    t = 0
    for j in range(i, n - 1):
        if t < csf[j][1]:
            t = csf[j][1]
        else:
            if t % csf[j][2] != 0:
                t = (t // csf[j][2] + 1) * csf[j][2]
        t += csf[j][0]
    print(t)

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

int main() {
	uint32_t N, K;
	cin >> N >> K;
	
	vector<uint32_t>a(N);
	uint32_t mina = UINT32_MAX;
	
	for(uint32_t i=0; i<N; i++) {
		cin >> a[i];
		mina = min(mina, a[i]);
	}
	
	//sort(a.begin(), a.end());
	
	vector<bool> dp(K+1);

	for(uint32_t i=mina; i<=K; i++) {
		for(uint32_t j=0; j<N; j++) {
			if(a[j] > i) continue;
			if(!dp[i-a[j]]) {
				dp[i] = true;
				break;
			}
		}
	}
	
	string ans = dp[K] ? "First" : "Second";
	cout << ans;
	
	return 0;
}

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

using ll = long long;
using pii = pair<int, int>;

#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define x first
#define y second

const int MOD = 1e9 + 7;

void setIO() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
}

//ctrl q is comment
//ctrl b is run
//ctrl s is compile
//shift r is search & replace
//shift d is delete a line

bool comp(pii a, pii b){
    return a.x == b.x ? a.y < b.y : a.x < b.x;
}
int main(){
    setIO();
    ll n; cin >> n;
    int p26 = 0;
    ll mult = 26;
    ll temp = n;
    while(temp > mult){
        temp -= mult;
        mult *= 26;
        ++p26;
    }
    mult = 26;
    ll div = 1;
    string ans = "";
    for(int i = p26; i >= 0; --i){
        if(n % mult == 0){
            ans = 'z' + ans;
            n -= mult;
        }
        else{
            ans = (char)((n % mult) / div - 1 + 'a') + ans;
            n -= n % mult;
        }
        mult *= 26;
        div *= 26;
    }
    cout << ans << "\n";
}



Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,a,b) for(int i=(a); i<=(b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define chmin(a,b) if((a)>(b)) (a)=(b);
#define chmax(a,b) if((a)<(b)) (a)=(b);
#define vi vector<int>
#define pii pair<int,int>
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define pb push_back
#define pf push_front
int gcd(int a,int b){/*a>=0,b>=0,￢(a=b=0)*/
  while(min(a,b)>0){if(a<b)swap(a,b);a%=b;}return max(a,b);
}
int dx[]={1,0,-1,0,1,-1,-1,1};
int dy[]={0,1,0,-1,1,1,-1,-1};
const int MOD = 1e9+7;
const int INF = 1e18+10;

/*----------------------------------------------*/
int n;
vi a;

bool check(int k,int keta){
  vi ok(3,0);
  rep(i,keta){
    int z=k%10;
    rep(j,3){
      if(z==3+j*2) ok[j]=1;
    }
    k/=10;
  }
  if(ok[0]==1&&ok[1]==1&&ok[2]==1) return true;
  else return false;
}

void dfs(int k,int keta){
  if(k>n) return;
  if(check(k,keta)) a.pb(k);
  rep(i,3){
    dfs(10*k+i*2+3,keta+1);
  }
}

signed main(){
  cin>>n;
  dfs(0,0);
  cout<<a.size()<<endl;

  rep(i,a.size()){
  }
  return 0;
}


Measured memory_bytes: 640
import java.util.*;
 
class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    Integer a[] = new Integer[N];
    
    for(int i=0; i<N; i++){
      a[i]  = sc.nextInt();
    }
    
    Arrays.sort(a,Comparator.reverseOrder());
    
    int Alice = 0;
    int Bob = 0;
    
    for(int i = 0; i<N; i+=2){
      Alice += a[i];
    }
    for(int i = 1; i<N; i+=2){
      Bob += a[i];
    }
    
    System.out.println(Alice-Bob);
  }
}

Measured memory_bytes: 21716
class segTree:
  inf = 0
  def __init__(self, num):
    self.N = 1
    while self.N < num:
      self.N *= 2
    self.T = [self.inf] * (2 * self.N - 1)
  def do(self, l, r):
    #最大値
    return max(l, r)
  def set(self, L):
    for i in range(len(L)):
      self.update(i, L[i])
  def update(self, x, v):
    k = x + self.N - 1
    self.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      self.T[k] = self.do(self.T[2*k+1], self.T[2*k+2])
  def getV(self, l, r):
    return self.getVs(l, r, 0, 0, self.N - 1)
  def getVs(self, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return self.T[k]
    t = (kl + kr) // 2
    if l > t:
      return self.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return self.getVs(l, r , 2 * k + 1, kl, t)
    return self.do(self.getVs(l, r , 2 * k + 1, kl,t),
              self.getVs(l, r , 2 * k + 2, t + 1, kr))

import copy
N = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))

D = segTree(N)
x = copy.deepcopy(h)
x.sort()
R = {}
for i in range(N):
  R[x[i]] = i

DP = [0] * N
for i in range(N):
  DP[i] = D.getV(0, R[h[i]]) + a[i]
  D.update(R[h[i]], DP[i])

print(max(DP))

Measured memory_bytes: 123496
# -*- coding: utf-8 -*-


def main():
    s = input()
    s_list = list(s)
    count = 0
    for i in range(len(s_list) - 1):
        if s_list[i] == s_list[i + 1]:
            if s_list[i + 1] == '0':
                s_list[i + 1] = '1'
            else:
                s_list[i + 1] = '0'
            count += 1

    print(count)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3956
# -*- coding: utf-8 -*-
# D

import sys
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
import math
import bisect
from itertools import accumulate
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

N = int(input())

def factorization(n):
    arr = defaultdict(int)
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt

    if temp!=1:
        arr[temp] = 1

    if arr==[]:
        arr[n] = 1

    return arr

if N == 1:
    print(0)
    sys.exit()

d = factorization(N)
# print(d)
max_d = max(d.values())
# print(max_d)

ref = [i for i in range(1, max_d+1)]
ref = list(accumulate(ref))
# print(ref)

ans = 0
for k, v in d.items():
    # print(k, v, bisect.bisect_right(ref, v))
    ans += bisect.bisect_right(ref, v)
print(ans)



Measured memory_bytes: 68460
#include <cstdio>
#include <algorithm>

using namespace std;

const int INF = 1000000000;
const int SIZE = 50;

int dp[SIZE+1][SIZE*1000+1];

int main(){
  int n, sum[SIZE+1], l[SIZE];
  
  scanf("%d",&n);

  sum[0] = 0;
  for(int i=0;i<n;i++){
    scanf("%d",l+i);
    sum[i+1] = sum[i] + l[i];
  }

  for(int i=0;i<=n;i++){
    for(int j=0;j<=sum[n];j++)
      dp[i][j] = INF;
    if(i < n) dp[i][sum[i]] = sum[i];
  }
  
  for(int i=1;i<n;i++){
    for(int j=0;j<=sum[i];j++){
      for(int k=i+1;k<=n;k++){
        if(dp[i][j] == INF) continue;

        int t = max(j, sum[k]-sum[i]);
        int p = min(dp[i][j], sum[k]-sum[i]);
        if(dp[k][t] == INF)
          dp[k][t] = p;
        else
          dp[k][t] = max(dp[k][max(j, sum[k]-sum[i])], p);
      }
    }
  }

  int ans = INF;
  
  for(int i=0;i<=sum[n];i++){
    if(dp[n][i] != INF)
      ans = min(ans, i - dp[n][i]);
  }
  

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

  return 0;
}



Measured memory_bytes: 12636
#include <stdio.h>

int main(void)
{
    int x, top3[3], i, j;

    for(i=0; i<3; i++){
        top3[i]=0;
    }

    for(i=0; i<10; i++){
        scanf("%d", &x);

        if(top3[2] >= x){ continue; }
        for(j=1; j>=0 && top3[j]<x; j--){
            top3[j+1] = top3[j];
        }
        top3[j+1] = x;
    }

    for(i=0; i<3; i++){
        printf("%d\n",top3[i]);
    }

    return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
#define ll long long int
#define pii pair<int,int>
#define F first
#define S second
#define mod 1000000007
///distance(s.begin(),s.lower_bound(101))
using namespace std;
///dp[i][j]=j lessons skipped in first i days.
///mn[i][j]=min hours needed to spend in ith day to skip skip exactly j lessons.



int main(){
    int k,n;cin >>k>>n;
    int arr[n+1];
    for(int i=0;i<n;i++)cin >> arr[i];
    arr[n]=arr[0]+k;
    sort(arr,arr+n);
    ll ans=10000000;
    for(int i=0;i<n;i++){
        ans=min(ans,(ll)k-abs(arr[i+1]-arr[i]));
    }
    cout <<ans<<endl;

}


Measured memory_bytes: 1024
#include <iostream>
#include <string>

int main(int argc, char* argv[]) {
  std::string str;
  std::string searchStr = ("AC");
  int searchStr_i = 0;
  int strLength = 0;
  int searchCounts[100000] = {};
  int searchCount = 0;
  int questionNumber = 0;
  int question_i = 0;
  int ACGTLengthStart = 0;
  int ACGTLengthEnd = 0;
  int char_i = 0;
  
  std::cin >> strLength >> questionNumber;
  std::cin >> str;

  for(char_i = 0; char_i < (int)str.length()-1;  char_i++)
  {
    if( ('A' == str[char_i]) && ('C' == str[char_i+1]) )
    {
      searchCount++;
    }
    searchCounts[char_i+1] = searchCount;
  }
  
  for(question_i = 0; question_i < questionNumber; question_i++)
  {
    std::cin >> ACGTLengthStart >> ACGTLengthEnd;
    std::cout << searchCounts[ACGTLengthEnd-1] - searchCounts[ACGTLengthStart-1] << std::endl;
  }
  
  return 0;
}

Measured memory_bytes: 1408
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <tuple>
#include <random>
using namespace std;

#define endl '\n'
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef complex<double> comp;
typedef vector< vector<ld> > matrix;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const int inf = 1e9 + 9;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);

int n, m;
int a[1010], b[1010];

ll solve() {
    sort(a, a+n);
    sort(b, b+m);

    int t = n * m;
    int i = n-1, j = m-1;
    if (!(a[i] == t && b[j] == t)) return 0;
    
    ll res = 1;
    while (i >= 0 || j >= 0) {
        //cerr << a[i] << " " << b[j] << " " << t << endl;
        if ((i > 0 && a[i] == a[i-1]) || (j > 0 && b[j] == b[j-1])) {
            return 0;
        }

        if (i >= 0 && a[i] == t && j >= 0 && b[j] == t) {
            i--;
            j--;
        } else if (i >= 0 && a[i] == t) {
            res *= (m - j - 1);
            res %= mod;
            i--;
        } else if (j >= 0 && b[j] == t) {
            res *= (n - i - 1);
            res %= mod;
            j--;
        } else {
            int sz = (m-j-1) * (n-i-1);
            int f = n * m - t;
            if (f >= sz) return 0;
            res *= (sz - f);
            res %= mod;
        }

        t--;
    }

    for (int i = 1; i <= t; i++) {
        res *= i;
        res %= mod;
    }
    return res;
}

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

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

    input();
    cout << solve() << endl;
}


Measured memory_bytes: 256
from bisect import bisect_right
import sys
input = sys.stdin.buffer.readline

class BIT:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)

    def add(self, index):
        while index <= self.size:
            self.tree[index] += 1
            index += index & (-index)

    def sum(self, index):
        ret = 0
        while index:
            ret += self.tree[index]
            index -= index & (-index)
        return ret

    def search(self, value):
        i = 0
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.tree[i + step] < value:
                i += step
                s += self.tree[i]
            step //= 2
        return i + 1

N, K = map(int, input().split())
A = [int(input()) - K for _ in range(N)]

accA = [0] * (N + 1)
for i, a in enumerate(A, start=1):
    accA[i] = accA[i - 1] + a

sToI = {s: i for i, s in enumerate(sorted(list(set(accA))))}
tree = BIT(len(sToI))

ans = 0
for a in map(lambda a: sToI[a] + 1 ,accA):
    ans += tree.sum(a)
    tree.add(a)
print(ans)


Measured memory_bytes: 54576
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#define rep(i,n) for (int i=0;i<n;i++)
using ll = long long;
using namespace std;

void solve(){

}
int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin >> s;
    int ans = 700;

    rep(i,3){
        if(s[i]=='o'){
            ans+=100;
        }
    }

    cout << ans;

    return 0;
}

Measured memory_bytes: 256
//https://atcoder.jp/contests/abc145/tasks/abc145_a
#include<bits/stdc++.h>
using namespace std;
#define aakriti long long int 
int main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        aakriti r ;
        cin >> r ;
        cout << r * r ;
}

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tt=1;
    //cin>>tt;
    while(tt--)
    {
        int k;
        cin>>k;
        for(int i=0;i<k;++i)
        cout<<"ACL";
    }
}

Measured memory_bytes: 3584