akhauriyash/Code-Regression huggingface dataset:
def input_n
  gets.to_i               # 単一整数
end

def input_s
  gets.chomp              # 文字列。chompを付けないと改行文字がついてくる
end

def input_a
  gets.split.map(&:to_i)  # スペースで区切られた複数の整数
end

def input_o(num)
  num.times.map { gets.to_i }  # 縦に並んだ複数の整数。たまにある
end

def output_f(num)
  puts sprintf("%.12f", num)
end

require "prime"

n = input_n

if Prime.prime?(n)
  puts 1
  exit
end

if n == 1
  puts 0
  exit
end

cnt = 0
# 素因数分解
div = Prime.prime_division(n)

# 素数a, 素数の個数b
# 素数をいくつ使えるか(zとして表現可能か)数える
# ex. a = 2, b = 3 のとき、2^1 = 2と2^2 = 4 でcnt += 2
# ex. a = 2, b = 4 のとき、2^1 = 2と2^2 = 4 でcnt += 2
# ex. a = 2, b = 5 のとき、2^1 = 2と2^2 = 4 でcnt += 2
# ex. a = 2, b = 6 のとき、2^1 = 2と2^2 = 4と2^3 = 8 でcnt += 3
div.each do |a, b|
  100.times do |i|
    # cntにいくつ足すかを求めるループ
    # b を 1,2,3,...で減算するとaの乗数(上のexでいう2^x)で減算するのと同じ
    # 減算した回数が個数になるので、cntにループ回数であるiを足せばzを足したのと同義
    # ※bが負になるまで計算しているため、一回多く減算しているので-1が必要な点に注意)
    #   例えばb=5の場合、i=1,2,3...の3でb<0になる
    b -= i
    if b < 0
      cnt += i - 1
      break
    end
  end
end
puts cnt


Measured memory_bytes: 14516
#define _CRT_SECURE_NO_WARNINGS
/*                   وتزودوا فإن خير الزاد التقوى                    */
/*       وما تدري نفس ماذا تکسب غدا وما تدري نفس باي ارض تموت      */
#include <bits/stdc++.h>
#include<unordered_map>
#include<iomanip>
#include<fstream>
using namespace std;
#include<iostream>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define dll double
#define PI acos(-1)
#define watch(x) cout<<#x<<" = { "<<x<<" }\n"
#define sz(n) n.size()
#define M_Sayed fast() 
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define RT(v) return cout<<v,0
int dx[] = { 0, 1, 0, -1, 1, 1, -1, -1 };
int dy[] = { 1, 0, -1, 0, 1, -1, 1, -1 };
const double EPS = (1e-7);
ll Ceil(ll x, ll y) { return (x + y - 1) / y; }
void run() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#else
#endif
}
ll gcd(ll a, ll b) { return !b ? abs(a) : gcd(b, a % b); }
ll lcm(ll a, ll b) { return abs(a / gcd(a, b)) * b; }
ll power(ll x, ll y, ll mod) {
	if (y == 0) return 1;
	if (y == 1) return x % mod;
	ll r = power(x, y >> 1, mod);
	return (((r * r) % mod) * power(x, y & 1, mod)) % mod;
}
void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }
ll n, m, t;
int main()
{
	//run();
	M_Sayed;
	string s;
	map<ll, ll>mp;
	cin >> s;
	for (auto it : s) {
		mp[it]++;
	}
	if (sz(mp) > 1)RT("Yes"); RT("No");
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

int main(){
	ll n;
	cin>>n;
	vector<ll> A(n);
	for(int i=0;i<n;i++) cin>>A[i];

	ll sum=0,tmp=0,ans=0;
    for(int l=0,r=0;l<n;l++){
        while(r<n && (sum&A[r])==0){
			sum+=A[r++];
			tmp++;
        }
		sum-=A[l];
		ans+=max(0LL,tmp);
		if(tmp>=1) tmp--;
    }
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define eps 1e-6
#define ll long long
#define IOS cin.sync_with_stdio(false);cin.tie(0);cout.tie(0);
//#define int long long
#define MEM(x,y) memset(x,y,sizeof(x))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define fi first
#define se second
#define endl "\n"
const ll mod=1000000007;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
ll qpow(ll a,ll b){ll s=1;while(b>0){if(b%2==1){s=s*a;}a=a*a;b=b>>1;}return s;}
ll qpowmod(ll a, ll b, ll c){ll res, t;res=1;t=a%c;while(b){if(b & 1){res=res*t%c;}t=t*t%c;b>>=1;}return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline long long read(){long long k=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}return k*f;}
inline void write(long long x){if(x<0)x=-x,putchar('-');if(x>9)write(x/10);putchar(x%10+'0');}
using namespace std;
int main()
{
    int n;
    cin>>n;
    int sum=0;
    rep(i,1,n+1)
    {
        rep(j,1,n+1)
        {
            rep(k,1,n+1)
            {
                int a=gcd(i,j);
                int b=gcd(j,k);
                sum+=gcd(a,b);
            }
        }
    }
    cout<<sum;
    return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std ;
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define re register
#define int long long
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int N = 100 + 5 ;
int a[N << 1], n, he, ed, cnt ; 
signed main()
{
	n = gi() + 1 ; 
	ed = 99, he = 100, cnt = 0 ; int flag = 0 ;
	for( re int i = 50; i >= 0; -- i ) {
		int u = ( 1ll << i ) ;
		if( n & u ) {
			if( !flag ) flag = 1 ;
			else {
				a[++ ed] = ++ cnt, a[-- he] = ++ cnt ; 
			}
		}
		else if( !flag ) continue ; 
		else {
			a[++ ed] = ++ cnt ; 
		}
	}
	printf("%lld\n", cnt * 2 ) ;
	rep( i, he, ed ) printf("%lld ", a[i] ) ;
	rep( i, 1, cnt ) printf("%lld ", i ) ;
	return 0 ; 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
   ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   
   int n;cin>>n;
   
   set<string>s;
   
   for(int i=0;i<n;i++)
   {
       string str;
       cin>>str;
       
       if(s.find(str)==s.end())
       s.insert(str);
   }
   
   cout<<s.size()<<endl;
   return 0;
}


Measured memory_bytes: 19292
//This is getting accepted!
// I HATE BUG
// God Of The Bugs
#include<bits/stdc++.h>

using namespace std;

#define ms(s, n) memset(s, n, sizeof(s))
#define FI first
#define SE second
#define pb push_back
#define mp make_pair
#define ll long long
#define sz(a) ((int)(a).size())
#define __builtin_popcount __builtin_popcounll
#define ld long double

typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, pii> ppi;

const double PI = acos(0) * 2;
const double EPS = 1e-8;
const ll MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;
const int oo = 1e9;
const double foo = 1e30;

template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return __builtin_popcounll(s);}
template<class T> T sqr(T x) { return x * x; }

inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}

int H, W, vs[30][30];
string s[30];

void go(int i, int j) {
	if (i >= H || j >= W) return;
//	cout << i << " " << j << endl;
	vs[i][j] = 1;
	if (j < W - 1 && s[i][j + 1] == '#') go(i, j + 1);
	else if (i < H - 1 && s[i + 1][j] == '#') go(i + 1, j);
}

int main() {
//#ifndef ONLINE_JUDGE
//    freopen("inp.txt", "r", stdin);
////    freopen("out.txt", "w", stdout);
//#endif

	cin >> H >> W;
	for (int i=0; i<H; i++) {
		cin >> s[i];
	}
	
	int ok = 0;
	for (int i=0; i<H; i++) {
		for (int j=0; j<W; j++) {
			if (s[i][j] == '#' && !vs[i][j]) {
				if (!ok) go(i, j), ok = 1;
				else {
					cout << "Impossible";
					return 0;
				}
			} 
		}
	}
	
	cout << "Possible";


}


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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 1000010

template< typename T >
class CumulativeSum
{
public:
    CumulativeSum() {}
    CumulativeSum(int sz) : m_Data(sz, T(0)) {};
    CumulativeSum(int sz, int mod) : m_Data(sz, T(0)) {};

    // k に x を加える O(1)
    void Add(int k, T x) {
        assert(static_cast<int>(m_Data.size()) >= k);
        if(static_cast<int>(m_Data.size()) <= k) { m_Data.push_back(x); }
        else { m_Data[k] = (m_Data[k] + x); }
    }

    // 累積和の構築 O(m_Data.size())
    void Build() {
        for(int i = 1; i < static_cast<int>(m_Data.size()); i++) {
            m_Data[i] = (m_Data[i] + m_Data[i - 1]);
        }
    }

    // 区間 [0, k] の和を返す O(1)
    // 閉区間なので k が含まれることに注意
    T Query(int k) {
        if(k < 0) { return T(0); }
        return (m_Data[min(k, static_cast<int>(m_Data.size()) - 1)]);
    }

    // 区間 [l, h] の和を返す O(1)
    // 閉区間なので k が含まれることに注意
    T Query(int l, int h) {
        return (this->Query(h) - this->Query(l-1));
    }
private:
    vector< T > m_Data;
};

// 文字列 s の中から a -> b -> c の順番で現れるものの数を数える。
// また制限 k を与える。a ... b ... c となる文字列の長さを k 以内に抑える。
// (制限なしの場合は k = s.length() とする)
// あらかじめ a と b が s 中に含まれる数を累積和で求めておき、
// CumulativeSum::Build() 済みで渡すこと。
// 計算量 O(s.length())
ll GetCharPattern(string s, char a, char b, char c,
        ll k, CumulativeSum<ll>& cs_a, CumulativeSum<ll>& cs_b) {
    assert(s.length() >= 3 && k >= 3);
    ll ret = 0;
    ll l = 0, r = 1;
    ll prev_cnt = 0;
    if(s[l] == a && s[r] == b) { prev_cnt++; }
    // 最後が c であることに注目して、しゃくとり法で文字をカウント
    while(r < s.length() - 1) {
        // r の直後が c なら、 a ... b ... c の完成
        if(s[r + 1] == c) { ret += prev_cnt; }
        // r を右にずらす
        r++;
        if(s[r] == b) {
            // 新たな M が来たら、それより前の a の分だけ
            // a → M のパターンが増える
            prev_cnt += cs_a.Query(l, r-1);
        }
        // 範囲が k - 1 より大きいなら、 l も右にずらす
        if(r - l >= k - 1) {
            if(s[l] == a) {
                // a が削られるなら、それより後の b の分だけ
                // a → b のパターンが減る
                prev_cnt -= cs_b.Query(l+1, r);
            }
            l++;
        }
    }
    return ret;
}


signed main()
{
    ll N, Q;
    string S;

    cin >> N >> S >> Q;

    // 累積和の作成
    CumulativeSum<ll> cs_d(N);
    CumulativeSum<ll> cs_m(N);

    REP(i, N) {
        if(S[i] == 'D') { cs_d.Add(i, 1); }
        if(S[i] == 'M') { cs_m.Add(i, 1); }
    }
    cs_d.Build();
    cs_m.Build();

    REP(i, Q) {
        ll k;
        cin >> k;
        printf("%lld\n", GetCharPattern(S, 'D', 'M', 'C', k, cs_d, cs_m));
    }
    return 0;
}


Measured memory_bytes: 17924
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pll pair<ll, ll>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define endl '\n'
const int inf = 1000000007;
const ll INF = 1e18;
// int mod = 998244353;
int mod = 1000000007;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
template<typename T, typename U> T pow_(T a, U b) { return b ? pow_(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
ll modpow(ll a, ll b, ll _mod) { return b ? modpow(a * a % _mod, b / 2, _mod) * (b % 2 ? a : 1) % _mod : 1; }
template<class T, class U> ostream& operator << (ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<class T> ostream& operator << (ostream& os, const vector<T>& vec) { rep(i, sz(vec)) { if (i) os << " "; os << vec[i]; } return os; }
template<typename T> inline istream& operator >> (istream& is, vector<T>& v) { rep(j, sz(v)) is >> v[j]; return is; }
template<class T, class T2> inline void add(T &a, T2 b) { a += b % mod; if (a >= mod) a -= mod; }
template<class T> void operator += (vector<T>& v, vector<T> v2) { rep(i, sz(v2)) v.eb(v2[i]); }

void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(12); // debuged
    int T;
    T = 1;
    while (T--) solve();
}

// https://atcoder.jp/contests/arc100/submissions/15485873
void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    cin >> a;
    
    vector<ll> acc(n + 1);
    rep(i, n) acc[i + 1] = acc[i] + a[i];
    
    ll ans = INF;
    // 尺取でやってみる
    int it = lb(acc, acc[2] / 2);
    int it2 = lb(acc, acc[2] + (acc[n] - acc[2]) / 2);
    rep3(bi_, 2, n - 1) { // 全探索!!
        if (bi_ <= 1 || bi_ >= n - 1) continue;
        
        while (it + 1 < bi_ && acc[it + 1] < acc[bi_] / 2) ++it; // debuged
        while (it2 + 1 < n && acc[it2 + 1] < acc[bi_] + (acc[n] - acc[bi_]) / 2) ++it2;
        
        rep3(qu_, it - 1, it + 2) rep3(qu_2, it2 - 1, it2 + 2) {
            if (qu_ <= 0 || qu_ >= bi_) continue;
            if (qu_2 <= bi_ || qu_2 >= n) continue;
            
            vector<ll> v;
            v.eb(acc[qu_]);
            //(0+...+(bi_-1)) - (0+...+(qu_-1)) = (qu_+...+(bi_-1))
            v.eb(acc[bi_] - acc[qu_]);
            v.eb(acc[qu_2] - acc[bi_]);
            v.eb(acc[n] - acc[qu_2]);
            sort(all(v));
            chmin(ans, v[3] - v[0]);
        }
    }
    cout << ans << endl;
}



Measured memory_bytes: 5564
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)((x).size())
#define debug(x) cout << #x << ":" << x << ' ';
#define debugg(x) cout << #x << ":" << x << ' ' << "\n";
#define endl "\n"
#define L(X) ((X)<<1)
#define R(X) (((X)<<1)|1)
#define M(X,Y) (((X)+(Y))>>1)

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int MAXN = 2e5 + 5;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const long long int LLINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-9;
const double PI = acos(-1);

template<typename T>   T max_self(T& a, T b) { if (a < b) a = b; return a; }
template<typename T>   T min_self(T& a, T b) { if (a > b) a = b; return a; }
template<typename T>   T add(T x, T y) { return ((x % MOD)  + (y % MOD)) % MOD;}
template<typename T>   T mul(T x, T y) { return ((x % MOD) * (long long)(y % MOD)) % MOD;}
template<typename T>   T sub(T x, T y) { return add(x, -y + MOD);}
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 T>   vector<T> read(vector<T>& v, int n) {v.resize(n); for (auto &x : v)cin >> x;}
template<typename T>   void trav(vector<T> &v) {for (int i = 0 ; i < (int)v.size() ; ++i) {cout << v[i]; if (i != (int)v.size() - 1) cout << ' ';}}
int lg2(long long x)   {   return 64 - __builtin_clzll(x) - 1;	}
int lg2(int x)   {   return 32 - __builtin_clzll(x) - 1;	}

struct pair_hash{
	template<class T1, class T2>
	size_t operator() (const pair<T1, T2> &p) const {
		auto h1 = hash<T1>{}(p.first);
		auto h2 = hash<T2>{}(p.second);
		return h1 ^ h2;
	}
};

int x;
bool prime[MAXN + 1];

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

	set<int> pr;

	memset(prime, true, sizeof prime);


	prime[2] = true;

	for(int i = 2 ; i <= MAXN ; ++i) {
		if(prime[i]) {
			pr.insert(i);
			for(int j = 2 * i ; j <= MAXN ; j += i) {
				prime[j] = false;
			}
		}
	}

	int x;
	cin >> x;

	cout << *pr.lower_bound(x) << endl;

	return 0;
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
#include <unistd.h>
using namespace std;
#define nl cout<<"\n"
#define pb push_back
#define se second
#define fi first
#define pi =3.14159265358979323846264338327950L;
typedef long long int ll;
int mod=1e9+7;


int main(){
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen("input.txt", "r", stdin); 
    //freopen("output.txt", "w", stdout);
    int n;
    cin>>n;
    ll ans=1;
    ll ar[n];
    int zero=0;
    for(int i=0;i<n;i++){
		cin>>ar[i];
		if(ar[i]==0) zero++;
	}
	if(zero) cout<<"0"<<endl;
	else{
		bool flag=true;
		ll ans1=1;
		for(int i=0;i<n;i++){
			ans1=ans*ar[i];
			if(ans1>1000000000000000000ll || ans1<ans){
				flag=false;
				break;
			}
			else{
				ans=ans1;
			}
		}
		if(flag) cout<<ans<<endl;
		else cout<<"-1"<<endl;
	}
    return 0;
}


Measured memory_bytes: 4396
n,x=map(int,input().split())
a=list(map(int,input().split()))
cnt=0
for i in range(n-1):
    if a[i]+a[i+1]>x:
        cnt+=a[i]+a[i+1]-x
        if a[i]>x:
            a[i+1]=0
        else:
            a[i+1]-=a[i]+a[i+1]-x
print(cnt)


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

pairs = [[0] * 10 for _ in range(10)]
for i in range(1, N + 1):
    s = str(i)
    a, b = int(s[0]), int(s[-1])
    pairs[a][b] += 1

count = 0
for i in range(1, N + 1):
    s = str(i)
    a, b = int(s[0]), int(s[-1])
    count += pairs[b][a]

# print(pairs)
print(count)


Measured memory_bytes: 3064
from collections import deque
N = int(input())
d = deque([])
for i in range(N):
  a, b = map(int, input().split())
  d.appendleft([a, b])

cnt = 0
ans = 0
for n in d:
  if (n[0]+cnt) % n[1] != 0:
    ans += n[1] - ((n[0]+cnt)%n[1])
    cnt += n[1] - ((n[0]+cnt)%n[1])
print(ans)

Measured memory_bytes: 24468
S = set()

q = int(input())


for _ in range(q):
    
    command, *list_num = input().split()
    x = int(list_num[0])

    if   command == "0":
        # insert(x)
        S.add(x)
        print(len(S))
    elif command == "1":
        # find(x)
        if x in S:
            print(1)
        else:
            print(0)
    elif command == "2":
        if x in S:
            S.remove(x)
    else:
        raise



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

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD

def factorize(num: int) -> dict:
    """ 素因数分解 """
    from math import sqrt
    from collections import Counter

    d = Counter()
    # 終点はルート切り捨て+1
    for i in range(2, int(sqrt(num))+1):
        # 素因数分解：小さい方から割れるだけ割って素数をカウント
        while num % i == 0:
            num //= i
            d[i] += 1
        # 1まで分解したら終了
        if num == 1:
            break
    # 最後に残ったnumは素数(ただし1^1は1^0なので数に入れない)
    if num != 1:
        d[num] += 1
    return d

def mul(C1, C2):
    return C1 + C2

def div(C1, C2):
    return C1 - C2

def gcd(C1, C2):
    for k, v in C2.items():
        C1[k] = min(C1[k], v)
    return C1
    # return C1 & C2

def lcm(C1, C2):
    for k, v in C2.items():
        C1[k] = max(C1[k], v)
    return C1
    # これでもできるけど遅い
    # return C1 | C2

N = INT()
A = LIST()

# 素数冪の状態で全体のLCMを出す
A2 = [factorize(a) for a in A]
l2 = Counter()
for a in A2:
    l2 = lcm(l2, a)

# 通常の値に戻す
l = 1
for k, v in l2.items():
    l *= pow(k, v, MOD)
    l %= MOD

ans = 0
for a in A:
    ans += fermat(l, a, MOD)
    ans %= MOD
print(ans)


Measured memory_bytes: 7972
#include <string>
#include <iostream>
#include <set>       // 要素数は size() で取得
#include <algorithm> // count_ifに必要
#include <array>     // size固定の配列
#include <queue>

using namespace std;
// 問題が起こるまでintは使用禁止2020-04-13
using ll = long long;

ll gcd(ll x, ll y)
{
    if (y == 0)
        return x;
    else
        return gcd(y, x % y);
}

template <class InputIterator, class T>
bool contains(InputIterator iterator, const T &value)
{
    if (find(iterator.begin(), iterator.end(), value) == iterator.end())
        return false;
    else
        return true;
}

// =========ここまでテンプレ============

int main()
{
    ll n;
    ll k;
    cin >> n;
    cin >> k;
    vector<ll> count;
    count.push_back(n - 0 + 1);
    for (ll i = 1; i < n + 1; i++)
    {
        count.push_back(count[i - 1] + (n - i) - i);
    }
    ll sum = 0;
    for (ll j = k - 1; j < n + 1; j++)
    {
        sum = sum + count[j];
    }
    cout << sum % (1000000007);
}

Measured memory_bytes: 4960
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = int64_t;
using P = pair<ll, ll>;
template <class T>
using V = vector<T>;

int main() {
  ll x, k, d;
  cin >> x >> k >> d;
  x = abs(x);

  ll ans;
  ll num = x / d;
  if (num >= k) {
    ans = abs(x) - d * k;
    cout << abs(ans) << endl;
    return 0;
  }

  if (k % 2 == num % 2) {
    ans = x - d * num;
  } else {
    ans = x - d * (num + 1);
    ans = abs(ans);
  }
  cout << ans << endl;
}


Measured memory_bytes: 3600
fun main() {
    val n = readLine()!!.toInt()
    val resultMap = IntArray(n + 1) { 0 }

    for (a in 1..n) {
        if (a * a > n) continue
        for (b in 1..n) {
            if (a * a + b * b + a * b > n) continue

            (1..n).forEach { c ->
                val count = a * a + b * b + c * c + a * b + b * c + c * a
                if (count <= n) {
                    resultMap[count] += 1
                }
            }
        }
    }

    resultMap.takeLast(n).forEach { println(it) }
}

Measured memory_bytes: 41164
#include<bits/stdc++.h>
using namespace std;
#define  ft  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define  ll  long long
#define  pi  pair<int,int>
#define  pb  push_back
#define  F   first
#define  S   second
#define  B   begin()
#define  E   end()
const int N=2e5+3;
string s,p;
//vector<int>v;
//map<int,int>mp;

int main()
{
    ft
    int t,i,j,n,m,l,r;
    cin>>s>>p;
    n=s.size();
    l=0;
    for(i=0;i<n;i++)
    {
        if(s[i]!=p[i])
        {
            l++;
        }
    }
    cout<<l<<"\n";
    return 0;
}



Measured memory_bytes: 3800
A = int(input()) #500
B = int(input()) #100
C = int(input()) #50
X = int(input()) #sum
count = 0

for a in range(A + 1):
    for b in range(B + 1):
        for c in range(C + 1):
            if 500 * a + 100 * b + 50 * c == X:
                count += 1

print(count)


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

typedef long long ll;
const ll MOD = 1e9+7;
const int N = 1e5+5;

int n,m,dp[N];
vector<int>v[N],topo;
bool vis[N];

void dfs(int s){
    vis[s]=true;
    for(auto e:v[s]){
        if(!vis[e])dfs(e);
    }
    topo.push_back(s);
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;

    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
    }

    for(int i=1;i<=n;i++){
        if(!vis[i])dfs(i);
    }
    reverse(topo.begin(),topo.end());

    for(auto e:topo){
        for(auto t:v[e]){
            if(dp[t]<dp[e]+1){
                dp[t]=dp[e]+1;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)ans=max(ans,dp[i]);
    cout<<ans;

    return 0;
}


Measured memory_bytes: 8824
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
using namespace std;

int main()
{
    long long a;
    long long b, n;
    cin >> a >> b >> n;
    if (n < b) {
        cout << a * n / b << endl;
    } else {
        cout << a * (b - 1) / b << endl;
    }

    return 0;
}

Measured memory_bytes: 3164
/*
1 2 2 2 1
2 4
5 1
3
*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
main()
{
	vector<long long int>v, vp;
	long long int x, y, a, b, c;
	cin >> x >> y >> a >> b >> c;
	long long int r[a], q[b], p[c], i,  j;
	for(i=0;i<a;i++)
	cin >> r[i];
	for(i=0;i<b;i++)
	cin >> q[i];
		for(i=0;i<c;i++)
		{
	cin >> p[i];
vp.push_back(p[i]);
}
	sort(r, r+a);
	sort(vp.begin(), vp.end());
	sort(q, q+b);
	
	
 
	
	for(i=a-1;i>=0;i--)
	{
		v.push_back(r[i]);
		if(v.size()==x)
		break;
		}	
	
	for(i=b-1;i>=0;i--)
	{
		v.push_back(q[i]);
		if(v.size()== y+x)
		break;
	}	
	sort(v.begin(), v.end());
	 for(i=0;i<v.size();i++)
		{
			if(vp.size()!=0)
			{
				if(vp.back()>v[i])
				{
					v[i] = vp.back();
					vp.pop_back();
				}
			}
		}
		long long int ans = 0;
	for(i=0;i<v.size();i++)
	ans+=v[i];
	cout << ans;
	return 0;
}

Measured memory_bytes: 6644
#include <bits/stdc++.h>
using namespace std;
vector <string> str;
vector <int> cnt;
string key;
int pos;

bool check(string a,int x,int y){
  int ima=pos,i=0,j=0;
  if(cnt[x]<=cnt[y]&&pos!=1) return 0;
  while(key[ima]==a[i])ima++,i++;
  if((key[ima]=='.'||!key[ima])&&a[i]==':') {
    pos=ima+1;
    return 1;
  }
  return 0;
}

string bnf(){
  int idx=0;
  int par=0;
  while(pos<(int)key.size()){
    while(idx<(int)str.size()&&!check(str[idx],idx,par))idx++;
    if(idx==(int)str.size()) return "no such property";  
    par=idx;
  }


  if(str[idx][str[idx].size()-1]==':') return "object";
  string ans="string \"";
  int f=0;
  for(int i=0;i<str[idx].size();i++){
    if(str[idx][i]==':') f=1;
    else if(f==1&&str[idx][i]==' ')f=2;
    else if(f==2) ans+=str[idx][i];
  }
  ans+="\"";
  return ans;
}

int main(){
  cin>>key;
  string a;
  getline(cin,a);
  while(getline(cin,a))str.push_back(a);
  for(int i=0;i<str.size();i++){
    int j=0;
    while(str[i][j]==' ') j++;
    cnt.push_back(j+1);
    str[i]=str[i].substr(j,str[i].size()-j);
  }
  pos=1;
  cout << bnf()<<endl;
  return 0;
}
  
    

Measured memory_bytes: 1312
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>

using namespace std;

#define FOR(i,k,n) for(int i=k;i<n;i++)
#define FORR(i,k,n) for(int i=k;i<=n;i++)
#define scan(a) scanf("%d",&a)
#define scann(a,b) scanf("%d%d",&a,&b)
#define scannn(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define mst(a,n)  memset(a,n,sizeof(a))
#define ll long long
#define N 1005
#define mod 1000000007
#define INF 0x3f3f3f3f

const double eps=1e-8;
const double pi=acos(-1.0);


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

    int n;
    while(scan(n)!=EOF)
    {
        int cnt=0;
        int tmp;
        for(int i=0;i<n;i++)
        {
            scan(tmp);
            if(tmp&1) cnt++;
        }
        if(cnt&1)
            puts("NO");
        else
            puts("YES");
    }
    return 0;
}


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

void sw_str(char* str){
	char tmp = {0};
	int len = strlen(str), i, j;
	
	for(i=0, j=len-1; i<len/2; i++, j--){
		tmp = str[i];
		str[i] = str[j];
		str[j] = tmp;
	}	
}

int main(){
    long long   n, tmp;
    int         dig=0;  //桁数
    char        s[15]={0};

    scanf("%lld", &n);

    for(int i=0; i<15; i++){
        if( n==0 ){ break; }
        
        if( n%26==0 ){
            s[i] = 26;
            n = n /26 -1;
        }else{
            s[i] = n % 26;
            n /= 26;
        }
        dig++;
    }
    
    sw_str(s);
    for(int i=0; i<dig; i++){
        s[i] += 0x60;
    }
    printf("%s\n", s);
    
    return 0;
}

Measured memory_bytes: 1660
#include <stdio.h>
int main(void)
{
    int W,H,x,y,r;
    scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);
    W-=r,H-=r;
    if(r<=x && x<=W && r<=y && y<=H)
    printf("Yes\n");
    else printf("No\n");
    return 0;
}


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

using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'

typedef long long ll;
typedef pair<int, int> ii;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

int main(){ _
	
	string s; cin >> s;
	int n = s.size();
	int l = n, r = -1;
	for (int i = 0; i < n; i++){
		if (s[i] == 'A') l = min(l, i);
		if (s[i] == 'Z') r = max(r, i);
	}
	cout << r-l+1 << endl;
	
	exit(0);
}


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

int main() {
  int s, s1, s2, s3;
  cin >> s;
  s1 = s / 100;
  s2 = (s - 100 * s1) / 10;
  s3 = s - 100 * s1 - 10 * s2;
  cout << s1 + s2 + s3 << endl;
}

Measured memory_bytes: 256
import sys
from collections import Counter

input = sys.stdin.readline


def main():
    N = int(input())
    A = tuple(map(int, input().split()))

    c = Counter(A)
    M = len(c)
    if M % 2 == 1:
        ans = M
    else:
        ans = M - 1
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 22060
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,n,s) for(int i = s; i < (n); ++i)
#define rsrep(i,n,s) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<x<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;

int main() {
    string s;
    cin >> s;
    string a = "abcdefghijklmnopqrstuvwxyz";
    string ans = "";
    if (s == "zyxwvutsrqponmlkjihgfedcba") {puts("-1"); return 0;}
    if (s.length() < 26) {
        rep(i, 26) {
            bool check = true;
            for (char sa : s) if (sa == a[i]) check = false;
            if (check) {
                ans = s + a[i];
                break;
            }
        }
    }
    else {
        string tmp = s;
        next_permutation(all(tmp));
        rep(i, 26) {
            ans += tmp[i];
            if (tmp[i] != s[i]) break;
        }
    }

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l), i##end = (r);i <= i##end;++i)
using std::cin; using std::cout;
const int maxn = 200200;
typedef long long ll;
typedef std::pair<ll, ll> pr;
const int mod = 1e9 + 7;
std::set<pr> s[100];
ll f[100], x, y;
int q;
inline void dfs(ll x, ll y, int cnt) {
	if(cnt == 89) return ;
	if(s[cnt].count(pr(x, y))) return ;
	s[cnt].emplace(x, y);
	for(int i = 1;y * i + x <= f[cnt] + f[cnt + 3];++i) {
		dfs(y, y * i + x, cnt + 1);
	}
}
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	f[0] = f[1] = 1;
	for(int i = 2;i < 93;++i) f[i] = f[i - 1] + f[i - 2];
	dfs(1, 1, 0);
	cin >> q;
	rep(i, 1, q) {
		cin >> x >> y;
		if(x > y)
			std::swap(x, y);
		int cnt = 1;
		for(;f[cnt + 1] <= x && f[cnt + 2] <= y;) 
			++ cnt;
		if(cnt == 1) {
			cout << 1 << ' ' << x * y % mod << '\n';
		} else {
			int ans = 0;
			for(const pr&i : s[cnt - 1]) {
				if(i.second <= y) ans = (ans + (x - i.first) / i.second) % mod;
				if(i.second <= x) ans = (ans + (y - i.first) / i.second) % mod;
			}
			cout << cnt << ' ' << ans << '\n';
		}
	}
}


Measured memory_bytes: 4352
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <map>

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

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

using namespace std;

int inputValue(){
    int a;
    cin >> a;
    return a;
};

template<typename T>
void inputArray(T* p, int a){
    rep(i, a){
        cin >> p[i];
    }
};

template<typename T>
void inputVector(vector<T> * p, int a){
    rep(i, a){
        T input;
        cin >> input;
        p -> push_back(input);
    }
}

template <typename T>
void output(T a, int precision = 0) {
    if(precision > 0){
        cout << setprecision(precision)  << a << "\n";
    }
    else{
        cout << a << "\n";
    }
}

const int Max = 110000;
ll N, M;
ll A[Max], B[Max];
vector<pair<ll, ll>> stores;

int main(int argc, const char * argv[]) {
    N = inputValue();
    M = inputValue();
    stores.reserve(N);

    rep(i, N) {
        A[i] = inputValue();
        B[i] = inputValue();
        stores.push_back(make_pair(A[i], B[i]));
    }

    sort(stores.begin(), stores.end(), [](auto& l, auto& r) {return l.first < r.first; });

    // for (auto& store: stores) {
    //     printf("%lld, %lld\n", store.first, store.second);
    // }    


    ll ans = 0;
    ll count = 0;
    for (auto& store: stores) {
        ll buynum = min(M - count, store.second);
        if (buynum == 0) break;
        ans += buynum * store.first;
        count += buynum;
    }

    output(ans);
    

    return 0;
}

Measured memory_bytes: 3328
# -*- coding: utf-8 -*-
import random
random.seed(0)

D = int(input())
C = list(map(int, input().split()))
list_S = [list(map(int, input().split())) for _ in range(D)]

answer = []
L = [0 for _ in range(26)]
for S in list_S:
  contest_index = -1
  contest_manzoku = -10**9
  for i in range(26):
    i_manzoku = S[i]+C[i]+L[i]
    if i_manzoku > contest_manzoku:
      contest_index = i
      contest_manzoku = i_manzoku
  answer.append(contest_index)
  for i in range(26):
    if i==contest_index:
      L[i] = 0
    else:
      L[i] += C[i]

def manzoku(A):
  score = 0
  L = [0 for _ in range(26)]
  for i in range(D):
    contest_index = A[i]
    for j in range(26):
      if j==contest_index:
        L[j] = 0
        score += list_S[i][contest_index]
      else:
        L[j] += C[j]
        score -= L[j] 
  return score

manzoku_now = manzoku(answer)
answer_tmp = [answer[i] for i in range(D)]
for j in range(10000):
  day = j%D
  contest = random.randrange(26)
  answer_tmp[day] = contest
  manzoku_tmp = manzoku(answer_tmp)
  if manzoku_now < manzoku_tmp:
    manzoku_now = manzoku_tmp
    answer[day] = contest
  else:
    answer_tmp[day] = answer[day]

for index in answer:
  print(index+1)

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

"""
参考：https://atcoder.jp/contests/abc047/submissions/4077573
"""

import sys
def input(): return sys.stdin.readline().strip()
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, T = MAP()
aN = LIST()

mx = -INF
l = aN[0]
cnt = 0
for i in range(1,N):
    # 最低値更新なら始点を動かす
    if aN[i] < l:
        l = aN[i]
    else:
        # 最高値更新ならその場所が操作対象になる
        if aN[i] - l > mx:
            mx = aN[i] - l
            cnt = 1
        # 同率最高値なら操作対象が1つ増える
        elif aN[i] - l == mx:
            cnt += 1
print(cnt)


Measured memory_bytes: 15060
void main() {
	auto N = ri;
	if(N < 1200) {
		writeln("ABC");
	} else if(N < 2800) {
		writeln("ARC");
	} else writeln("AGC");
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.conv;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring> //memset(dp,0,sizeof(dp))
#include <functional>
#include <cctype>
#include <locale>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()
using namespace std;
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;}
typedef pair<int,int> P;
typedef pair<long long,long long> Pll;
#define fout(num) cout << fixed << setprecision(20) << (num) << endl
//s[i]=tolower(s[i]); islower(s[i]); cout << tolower(s[i])はバグ
//vector<vector<ll>> dp(n,vector<ll>(n))
//exist x map o setconst ll MOD = 1e9+7;return fac[n]*(finv[k]*finv[n-k] % MOD) % MOD;
//木の連結成分の個数は頂点数ー辺の数

signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int r,c,kk;
    cin >> r >> c >> kk;
    ll a[r][c];
    rep(i,r)rep(j,c)a[i][j]=0;
    rep(i,kk){
        int x,y; cin >> x >> y;
        x--; y--;
        ll v; cin >> v;
        a[x][y]=v;
    }
    vector<vector<vector<ll>>> dp(r, vector<vector<ll>>(c, vector<ll>(4, 0)));
    if(a[0][0]>0) dp[0][0][1]=a[0][0];
    
    rep(i,r){
        rep(j,c){
            rep(k,4){
                if(k==0){
                    if(i>0) chmax(dp[i][j][1],dp[i-1][j][0]+a[i][j]);
                    if(j>0) chmax(dp[i][j][1],dp[i][j-1][0]+a[i][j]);
                }else{
                    if(i>0) chmax(dp[i][j][1],dp[i-1][j][k]+a[i][j]);
                    if(j>0&&k<=2) chmax(dp[i][j][k+1],dp[i][j-1][k]+a[i][j]);
                }
                if(i>0) chmax(dp[i][j][k],dp[i-1][j][k]);
                if(j>0) chmax(dp[i][j][k],dp[i][j-1][k]);
            }
        }
    }
    ll ans=0;
    rep(i,4) chmax(ans,dp[r-1][c-1][i]);
    cout << ans << endl;
    
}


Measured memory_bytes: 706688
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef pair<ll, ll> PL;
typedef long double ldouble;
typedef tuple<int,int,int> t3;

int main()
{
  ll sum = 0;
  int N, nm = 1;
  scanf("%d", &N);
  if(N == 3) return !printf("2\n5\n63\n");
  for(int i = 1; i <= N; i++, nm++){
    while(nm%2 && nm%3) nm++;
    while(i == N && ((nm%2 && nm%3) || (sum+nm)%6)) nm++;
    while(i == N-1 && ((nm%2 && nm%3) || (sum+nm)%6 == 1 || (sum+nm)%6 == 5)) nm++;
    printf("%d\n", nm); sum += nm;
  }
}



Measured memory_bytes: 384
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO ?????????????????????????????????????????????
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int[] A = new int[n];
		
		String[] str = br.readLine().split(" ");
		for(int i = 0; i < n; i++){
			A[i] = Integer.parseInt(str[i]);
		}
		
		int count = 0;
		
		for(int i = 1; i < n; i++){
			boolean flag = true;
		
			while(flag){
				flag = false;
			
				for(int j = n - 1; j > i - 1; j--){
					if(A[j] < A[j - 1]){
						int tmp = A[j];
						A[j] = A[j - 1];
						A[j - 1] = tmp;
						flag = true;
						
						count++;
					}
				}
			}
		}
		
		for(int i = 0; i < n; i++){
			System.out.print(A[i]);
			
			if(i + 1 == n){
				System.out.print("\n");
			} else {
				System.out.print(" ");
			}
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 24332
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>
#include <cmath>
using namespace std; 
int main(int argc,char const* argv[])
{
  int n,m;
  long long int time1=0;
  long long int time2=0;
  int circuit=0;
  cin >> n >> m;
  circuit=100*n+1800*m;
  double times=1;
  for(int i=1;i<=m;i++)
    {
      times=(0.5)*times;
     }
  time1=circuit * times / ((1-(1-times))*(1-(1-times)));
  cout << time1 << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cctype>
#include<climits>
#include<bitset>
#include<bits/stdc++.h>
#define ld long double
#define ll long long int
#define ull unsigned long long intS
#define rep(i,n) for(int i=0;i<n;i++)
#define fin(ans) cout<<(ans)<<endl
#define in(n) cin>>n>>
#define INF INT_MAX
#define vi vector<int>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pair<int,int> >
#define vvi vector<vector<int> >
#define vvc vector<vector<char> >
#define vvs vector<vector<string> >
#define P 1000000007
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 LLINF=1LL<<60;
//set<int>::iterator it;


int main(void){ios::sync_with_stdio(false);cin.tie(0);
//////////////////////////////////////////////////////
    
    
    int  a,b,x;
    
    cin >> a >> b;
    
    x = (a+b)/2;
    
    
    if ((a+b)%2 == 0){
    
    
    cout << x << endl;
    
    }else{
    
    cout<< x+1 << endl;
    
    }
    
/////////////////////////////////////////////////////
return 0;}

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

#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define MIN(c) (*min_element(ALL(c))) 
#define MAX(c) (*max_element(ALL(c)))
#define ACC(c) (accumulate(ALL(c), 0))
#define MP(a, b) (make_pair((a), (b)))
#define ENDL "\n"
#define PRINT(x) cout << (x) << ENDL

using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;

inline int in(int& a) {return scanf("%d", &a);}
inline void out(int n) {printf("%d\n", n);}
template<typename T> inline void swap(T& a, T& b) {T tmp = a; a = b; b = tmp;}
auto pint_compare = [](pint x, pint y) -> bool{return (x.first < y.first);};


signed main(){
    int X, A;
    cin >> X >> A;
    if(X < A) PRINT("0");
    else PRINT("10");
    return 0;
}

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

int main(){
    int a,b,c,count;
    cin >> a >> b >> c;
    count = 0;
    for (int x = a; x <= b; x++) {
        if ((c % x) == 0) {
            count += 1;
        }
    }
    cout << count <<  endl;
    
    return 0;
}

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

int main(void)
{
	int num;
	int input;
	int lst[200000];
	int small;
	int large;
	int maximum;
	cin >> num;
	for(int i = 0; i < num; i++)
	{
		cin >> lst[i];

	}
	maximum = -2000000000;
	small = lst[0];
	large = lst[0];

	for (int i = 1; i < num; i++)
	{
		maximum = max(maximum, lst[i] - small);
		small = min(small, lst[i]);
	}
	cout << maximum << endl;
}

Measured memory_bytes: 1940
#include <bits/stdc++.h>
#define int long long
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define leng(n) (int)(log10(n)+1)
#define INF 9000000000000000000
using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}  //  最大公約数gcd
int lcm(int a,int b){return a/gcd(a,b)*b;}  //  最小公倍数lcm

signed main() {
  int n, d, x;
  cin >> n >> d >> x;
  int a;
  rep(i,0,n){
    cin >> a;
    x += (d-1)/a + 1;
  }
  cout << x << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
//---------------------------
using namespace std;
//---------------------------
#define REP(i,n) for(int i = 0; i < (n); i++)
#define P(x) cout << (x) << "\n"
#define fcout cout << fixed << setprecision(18)

#define MOD 1000000007 // 1e9+7
#define PI 3.1415926535
/*
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679
*/
#define ll long long int // 10^18
#define INF 1000000001 // 1e9+1
#define LINF 1000000000000000001 // 1e18+1

int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
//---------------------------
int N,M,i,j,k;
string S,T;

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

    return temp ? (a / temp * b) : 0;
}

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

  // ifstream in("input.txt");
  // cin.rdbuf(in.rdbuf());

  cin>>N>>M>>S>>T;
  ll ans = lcm(N,M);
  bool flag = gcd(N,M)>1 ? 1 : 0;
  ll g = gcd(N,M);
  ll l = lcm(N,M);
  ll ss = lcm(l/N, l/M);
  ll ln = l/N;
  ll lm = l/M;
  if(S[0]!=T[0]){
    ans=-1;//ここはOK
  }
  if(flag) {
      for(i = 0;i<l;i+=ss){
        if(S[i/ln]!=T[i/lm]){
          ans=-1;
        }
      }
  }
  // if(ans==-1){
  //   ans=lcm(M,N);
  // }else{
  //   ans=-1;
  // }
  P(ans);
  return 0;
}


Measured memory_bytes: 640
s=input()
n=len(s)
winFlag=True

for i,it in enumerate(s):
    if i%2==1:
        if not (it in "LUD") :
            winFlag=False
    else:
        if not (it in "RUD"):
            winFlag=False
if(winFlag==True):
    print("Yes")
else:
    print("No")


Measured memory_bytes: 2940
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int k,n,m,p,dat[15000],cnt;
	double ans=0;
	cin>>k>>n>>m>>p;
	for(int i=0;i<k;i++){
		cin>>dat[i];
	}
	sort(dat,dat+n+1,greater<int>());
	ans=p/n;
	for(int i=0;i<k;i++){
		cnt+=dat[i];
		if((cnt+p)/(n+(i+1)*m)>=ans){
			ans=(cnt+p)/(n+(i+1)*m);
		}
		else{
			break;
		}
		}
		cnt=ans;
		cout<<cnt<<endl;
		return 0;
	}

Measured memory_bytes: 1184
#include<stdio.h>
int main()
{
	char x,y;
	scanf("%c %c",&x,&y);
	if(x<y){
		printf("<\n");
	}
	else if(x==y){
		printf("=\n");
	}
	else{
		printf(">\n");
	}
	return 0;
}

Measured memory_bytes: 1620
n = int(input())

buf = [["a",97]]
a = 97

for i in range(n-1):
    next = []
    for b in buf:
        for j in range(97,b[1]+1):
            next.append([b[0]+chr(j),b[1]])
        next.append([b[0]+chr(b[1]+1),b[1]+1])
    buf = next

ans = [b[0] for b in buf]

ans.sort()
# print(ans)
#
# print(buf)
# print(len(buf))
for a in ans:
    print(a)



Measured memory_bytes: 25716