akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>

long a[300010], s[64][300010][2];
int main()
{
    int n; scanf("%d", &n);
    for(int i=0; i<n; ++i) {
        scanf("%ld", a+i);
        for(int j=0; j<61; ++j) {
            int k=(a[i]>>j)&1;
            if (k==0) {
                s[j][i+1][0]=s[j][i][0]+1;
                s[j][i+1][1]=s[j][i][1];
            }
            else {
                s[j][i+1][0]=s[j][i][0];
                s[j][i+1][1]=s[j][i][1]+1;
            }
        }
    }

    const long mod=1e9+7;
    long res=0;
    for(int i=0; i<n; ++i) {
        for(int j=0; j<61; ++j) {
            long t=0;
            int x=(a[i]>>j)&1;
            t+=s[j][n][!x]-s[j][i][!x];
            t%=mod;
            (t*=(1L<<j)%mod)%=mod;
            (res+=t)%=mod;
        }
    }
    printf("%ld\n", res);
}


Measured memory_bytes: 290176
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    a,b,c,d=INTM()
    if (a-d<=c<=a+d) or (a-d<=b<=a+d and c-d<=b<=c+d):
        print('Yes')
    else:
        print('No')
if __name__ == '__main__':
    do()

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

int main(){
    int n,cnt;
    cin>>n;
    vector<int> p(n);

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

    cnt=0;
    for(int i=1; i<n-1; i++){
        if(p[i-1]<p[i] && p[i]<p[i+1]){
            cnt++;        
        }
        if(p[i-1]>p[i] && p[i]>p[i+1]){
            cnt++;
        }
    }

    cout<<cnt<<endl;

    return 0;
}


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

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

int main() {

    int n;
    cin >> n;

    vector<char> colors(n);

    rep(i, n) {
        char c;
        cin >> c;
        colors[i] = c;
    }

    char a = ' ';
    int count = 0;
    for (char c : colors) {
        if (c != a) {
            count++;
            a = c;
        }
    }

    cout << count << endl;

}



Measured memory_bytes: 384
use std::io::*;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn main() {
    traveling_budget();
}

fn traveling_budget() {
    let a: i64 = read();
    let b: i64 = read();
    let c: i64 = read();
    let d: i64 = read();
    let ab = min_i64(a, b);
    let cd = min_i64(c, d);
    println!("{}", ab + cd);
}

fn min_i64(n: i64, m: i64) -> i64 {
    let diff = n - m;
    match diff {
        diff if diff > 0 => m,
        _                => n
    }
}

Measured memory_bytes: 4352
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<random>
#include<iomanip>
#include<vector>
#include<functional>
#include<algorithm>
#include<cstdio>
#include<stdlib.h>
#include<unordered_map>
#include<time.h>
#define rep(i,a,n) for (int (i)=(a);(i)<(n);(i)++)
#define int long long
using namespace std;
typedef long long ll;
typedef long double ld;
const int inf = 999999999999999999;
using namespace std;
int n, a[100001], b[100001];
vector<int>e[100001];
signed main(){
	cin >> n;
	for (int i = 1; i <= n; i++) {
		a[i] = inf, b[i] = inf;
		if (i != n) {
			int a, b;
			cin >> a >> b;
			e[a].push_back(b);
			e[b].push_back(a);
		}
	}
	queue<int>q;
	q.push(1);
	a[1] = 0;
	while (!q.empty()) {
		int t = q.front(); q.pop();
		for (int i = 0; i < e[t].size(); i++) {
			if (a[e[t][i]] > a[t] + 1) {
				a[e[t][i]] = a[t] + 1;
				q.push(e[t][i]);
			}
		}
	}
	int sum = 0, sum2 = 0;
	q.push(n);
	b[n] = 0;
	while (!q.empty()) {
		int t = q.front(); q.pop();
		if (a[t] <= b[t]) sum++;
		else sum2++;
		for (int i = 0; i < e[t].size(); i++) {
			if (b[e[t][i]] > b[t] + 1) {
				b[e[t][i]] = b[t] + 1;
				q.push(e[t][i]);
			}
		}
	}
	if (sum > sum2) cout << "Fennec\n";
	else cout << "Snuke\n";
	getchar(); getchar();
}

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

int main() {
	int n, m, c;
	cin >> n >> m;
	int a[n][m], b[m];

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

	for (int i = 0; i < m; i++)
		cin >> b[i];

	for (int i = 0; i < n; i++) {
		c = 0;
		for (int j = 0; j < m; j++)
			c += a[i][j] * b[j];
		cout << c << endl;
	}

	return 0;
}

Measured memory_bytes: 1200
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>

struct person{
	long long h;
	long long p;
};

int main(){
	int n;
	int ans=0;
	std::vector<person> list;
	std::vector<long long> dpList;

	std::cin>>n;
	list.resize(n);
	dpList.resize(n+1, -1);
	dpList[0]= 0;

	for(int i=0; i<n; i++)
		std::cin>>list[i].h>>list[i].p;
	
	std::stable_sort(list.begin(), list.end(), [](const person& x, const person& y){return x.p+ x.h< y.p + y.h;});

	for(int i=0; i<n; i++){
		for(int j=i; j>=0; j--){
			if(dpList[j]==-1)
				continue;

			if(dpList[j]>list[i].h)
				continue;

			if(dpList[j+1]==-1)
				dpList[j+1]=dpList[j]+list[i].p;
			else
				dpList[j+1]=std::min(dpList[j]+list[i].p, dpList[j+1]);
		}
	}

	for(int i=n; i>=0; i--){
		if(dpList[i]!=-1){
			ans= i;
			break;
		}

	}

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

	return 0;
	
}

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

using namespace std;

int main() {
  int n, result = 0;
  cin >> n;
  int dp[n + 1][3],a[n + 1][3];
  for(int i = 1;i <= n;i++){
    cin >> a[i][0] >> a[i][1] >> a[i][2];
  }
  dp[0][0] = dp[0][1] = dp[0][2] = 0;
  for(int i = 1;i <= n;i++){
    dp[i][0] = max(dp[i - 1][1],dp[i - 1][2]) + a[i][0];
    dp[i][1] = max(dp[i - 1][0],dp[i - 1][2]) + a[i][1];
    dp[i][2] = max(dp[i - 1][0],dp[i - 1][1]) + a[i][2];
  }
  cout << max(dp[n][0],max(dp[n][1],dp[n][2]));
}

Measured memory_bytes: 2560
#include<iostream>

#include<bits/stdc++.h>


using namespace std;

int main(){
  int h,n;
  cin>>h>>n;

  int arr[n];
  int sum=0;
  for(int i=0;i<n;i++){
     cin>>arr[i];
     sum+=arr[i];
  }
  if(sum>=h)cout<<"Yes";
  else cout<<"No";
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
using namespace std;
ll n,raod,a[300005],b[300005];
ll kk(ll x){
    if(x == 1)return b[n] + b[2];
    if(x == n)return b[1] + b[n - 1];
    return b[x - 1] + b[x + 1];
}
set<pair<ll,ll> >st;
set<pair<ll,ll> >::iterator it;
int main(){
    cin >> n;
    
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    
    for(int i=1; i<=n; i++){
        cin >> b[i];
        st.insert(make_pair(b[i] , (ll)i));
    }
    
    while(st.size()){
        it = st.end();
        it--;
        pair<ll,ll>p = (*it);
        if(p.f == a[p.s]){
            st.erase(it);
            continue;
        }
        if(p.f < a[p.s]){
            cout << "-1";
            return 0;
        }
        st.erase(it);
        ll ff = 0;
        if(p.s == 1)ff = max(b[n] , b[2]);
        if(p.s == n)ff = max(b[n-1] , b[1]);
        ff = max(b[p.s-1]  ,b[p.s+1]);
        ff = max(ff , a[p.s]);
        ll g = (b[p.s] - ff) / kk(p.s);
        g = max(g , 1LL);
        b[p.s] -= g * kk(p.s);
        raod+=g;
        if(b[p.s] < a[p.s]){
            cout << "-1";
            return 0;
        }
        st.insert(make_pair(b[p.s] , p.s));
    }
    
    cout << raod << endl;
    
    
    
    return 0;
}


Measured memory_bytes: 16384
#include <bits/stdc++.h>
#define fi first
#define se second
#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 srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define print(x)cout<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

int main() {
  double d;
  cin>>d;
  double ans = 2*d*3.1415926535;
  printf("%.10f\n",ans);
  return 0;
}

Measured memory_bytes: 3784
#include<stdio.h>
int main(void){
    int a,b;
    scanf("%d %d",&a,&b);
    if(a<b){
        printf("a < b");
    }else if(a>b){
        printf("a > b");
    }else{
        printf("a == b");
    }
    printf("\n");
    return 0;
}

Measured memory_bytes: 584
#include <bits/stdc++.h>
using namespace std;
#define LL long long int
LL A, B, C, D;
map<LL, LL> memo;
LL INF = (LL)5e18;
LL solve(LL n){
    if(n==0) return 0;
    if(n==1) return D;
    if (memo.count(n)) return memo[n];
    LL l2 = (n/2)*2;
    LL r2 = ((n+1)/2)*2;
    
    LL l3 = (n/3)*3;
    LL r3 = ((n+2)/3)*3;
    
    LL l5 = (n/5)*5;
    LL r5 = ((n+4)/5)*5;
    
    LL res = INF;
    if(n < res/D){
        res = n*D;
    }
    
    res = min(res, llabs(l2-n)*D + A + solve(l2/2));
    res = min(res, llabs(r2-n)*D + A + solve(r2/2));
    
    res = min(res, llabs(l3-n)*D + B + solve(l3/3));
    res = min(res, llabs(r3-n)*D + B + solve(r3/3));
    
    res = min(res, llabs(l5-n)*D + C + solve(l5/5));
    res = min(res, llabs(r5-n)*D + C + solve(r5/5));
    
    return memo[n] = res;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    int T;
    cin >> T;
    for (int t = 0; t < T; t++) {
        memo.clear();
        LL N;
        // See Editorial...
        cin >> N;
        cin >> A >> B >> C >> D;
        cout << solve(N) << "\n";
    }
    
    return 0;
}

Measured memory_bytes: 4444
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define fi first
#define se second
#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)
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=1010010010010010000;
template<class T> inline bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
//グリッド：（典型）dp,dfs,bfs,最短経路,その他
int main(){
    ll x,y,a,b,c;cin >> x >> y >> a >> b >> c;
    vl p(a),q(b),r(c);
    rep(i,a) cin >> p[i];
    rep(i,b) cin >> q[i];
    rep(i,c) cin >> r[i];
    sort(p.rbegin(),p.rend());
    sort(q.rbegin(),q.rend());
    sort(r.rbegin(),r.rend());
    ll ans=0;
    vl num;
    rep(i,x) num.push_back(p[i]);
    rep(i,y) num.push_back(q[i]);
    rep(i,c) num.push_back(r[i]);
    sort(num.rbegin(),num.rend());
    rep(i,x+y){
        ans+=num[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8816
#include <stdio.h>

int main(void){
    int n,x;
    int l[101] = {};
    int i,len = 0, count = 0;
    
    scanf("%d %d", &n, &x);
    for(i = 1; i <= n; i++){
        scanf("%d", &l[i]);
    }
   
    i = 0;
    while(i <= n){
        len += l[i++];
        if(len > x){
            break;
        }
        count++;
    }
    
    printf("%d\n", count);

    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <deque>
#include <queue>
#include <functional>
//#include <boost/multiprecision/cpp_int.hpp>

#define rep(i, n) for(int i = 0; i < n; ++i)
#define REP(i, m, n) for(int i = m; i < n; ++i)
#define rrep(i,n) for(int i = n; i >= 0; --i)
#define RREP(i, m, n) for(int i = n; i >= m; --i)
#define llrep(i, n) for(ll i = 0; i < n; ++i)
#define llREP(i, m, n) for(ll i = m; i < n; ++i)
#define llrrep(i,n) for(ll i = n; i >= 0; --i)
#define llRREP(i, m, n) for(ll i = n; i >= m; --i)

using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<long long, long long>;
using pil = std::pair<int, long long>;
using pli = std::pair<long long, int>;
using plpii = std::pair<long long, std::pair<int, int>>;
using pdd = std::pair<double, double>;

const long long INF = 1000000000000000001;
const long long _MOD = 1000000007;
const long long MOD = 998244353;
const int ALPHABET = 27;
const double pi = 3.14159265358979;

using namespace std;
//namespace mp = boost::multiprecision;

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

	int n;
	cin >> n;
	string s;
	cin >> s;

	int* sumR = new int[n];
	int* sumW = new int[n];
	
	sumR[0] = 0;
	sumW[0] = 0;
	if (s[0] == 'R') ++sumR[0];
	else ++sumW[0];
	REP(i, 1, n) {
		sumR[i] = sumR[i - 1];
		sumW[i] = sumW[i - 1];

		if (s[i] == 'R') ++sumR[i];
		else ++sumW[i];
	}

	int ans = min(sumR[n-1],sumW[n-1]);
	rep(i, n-1) {
		ans = min(ans, max(sumW[i], sumR[n - 1] - sumR[i]));
	}

	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 5324
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>

#define REP(i,n) for(long long i=0;i<n;++i)
#define REPR(i,n) for(long long i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(long long i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define INF 999999999
#define SUR 1000000007
#define pb push_back
#define pf push_front
#define MP make_pair
#define SV(v) {for(long long sitr=0;sitr<v.size();++sitr){cin>>v[sitr];}}

int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

using namespace std;

typedef pair<int,int> pii;

int main(){

  int n, K;
  cin >> n >> K;

  vector<llong> h(n);
  REP(i,n){
    cin >> h[i];
  }

  llong dp[100001] = {};
  REP(i,100001){
    dp[i] = INF;
  }

  dp[0] = 0;
  REP(i,n){
    FOR(k,1,K+1)
      if(i+k < n)
        dp[i+k] = min(dp[i+k], dp[i] + abs(h[i] - h[i+k]));
  }

  cout << dp[n-1] << endl;
  return 0;
}



Measured memory_bytes: 1792
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

int main(){
	vector<pll> v(4);
	vl a = {8, 4, 2, 1};
	rep(i, 4) {
		cin >> v[i].fi;
		v[i].fi *= a[i];
		v[i].se = i;
	}
	sort(all(v));
	ll ans = 0LL;
	int n;
	cin >> n;
	ans += v[0].fi * (n / 2);
	if(n&1) {
		if(v[0].se == 3) ans += v[1].fi/2;
		else ans += v[0].fi/2;
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
n = int(input())
a = [1,2,3,4,5,6,7,8,9]
b = [1,2,3,4,5,6,7,8,9]

ans = []
for i in range(len(a)):
    for j in range(len(b)):
        ans.append(a[i]*b[j])

if n in ans:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
# Strange Bank
# https://atcoder.jp/contests/abc099/tasks/abc099_c

# 個数制限なしナップサックDP
class KnapsackDPSolver
  def main
    upper_w = gets.chomp.to_i

    # 品物（引き出し単位金額）のリストを生成
    items = []
    w = 1
    while w <= upper_w
      items << w
      w *= 6
    end
    w = 9
    while w <= upper_w
      items << w
      w *= 9
    end
    # pp items

    n = items.length

    # 金額wを引き出すのに必要な最小の回数を格納
    # dp[i][w] = v
    # ★【最小の】回数を格納するので初期値はINT_MAX的な値に
    dp = Array.new(n+1) { Array.new(upper_w+1, 1 << 29) }
    # ★左端を全部0に。0円は0回で引き出せるので。
    0.upto(n) do |i|
      dp[i][0] = 0
    end

    0.upto(n-1) do |i|
      0.upto(upper_w) do |w|
        dp[i+1][w] =
            if w < items[i]
              # 現在の重さより左側は現在のアイテム（金額）を使えないので
              # 上から下ろす or 既に有る値
              [dp[i][w], dp[i+1][w]].min
            else
              # 現在の重さ以上の部分（右側）は
              # 重さ分左のvalue + 現在value or 下ろすだけ
              [dp[i+1][w - items[i]] + 1, dp[i][w]].min
            end
      end
      # pp "#{i+1}: #{dp[i+1]}"
    end

    puts dp[n][upper_w]
  end
end

if __FILE__ == $0
  KnapsackDPSolver.new.main
end


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

int main(void){
    int N;
    cin >> N;
    vector<int> vec(N);
    for(int i=0;i<N;i++) cin >> vec[i];
    sort(vec.begin(),vec.end());
    
    int ans=10000000;
    for(int i=vec[0];i<=vec[N-1];i++){
        int power = 0;
        for(int j=0;j<N;j++){
            power += (vec[j]-i)*(vec[j]-i);
        }
        ans = min(ans,power);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <set>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }


int main(){
    long long N, a, b, c, d, e;
    cin>>N>>a>>b>>c>>d>>e;
    long long f = min({a, b, c, d, e});
    long long t = N/f + (N%f>0 ? 1 : 0);
    t+=4;
    cout<<t<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <limits.h>
using namespace std;

int main() {
    int temp;
    int maxLen = INT_MIN;
    int sum = 0;
    int N;
    cin >> N;
    for (int i = 0; i < N; ++i) {
        cin >> temp;
        sum += temp;
        if (temp > maxLen)
            maxLen = temp;
    }
    sum -= maxLen;
    if (maxLen < sum)
        cout << "Yes";
    else
        cout << "No";
  
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <cassert>
#include <functional>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
const int INF = 1<<29;
#define LNF __LONG_LONG_MAX__
const ll MOD = 1000000007;
const int MAX = 200000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
// 法mでのaの逆元を計算
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
//最大公約数
int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }
//最小公倍数
int lcm(int x, int y) { return x / gcd(x, y) * y; }
// nが大きく,kが10^7程度の時の二項係数
long long com[200005];
void combination(long long n,long long k){
    com[0] = 1;
    for(int i=1;i<=k;i++){
        com[i] = (com[i-1]*(n-i+1)%MOD)*modinv(i,MOD)%MOD;
    }
}

int main(){
    int N,D,X; cin >> N >> D >> X;
    vector<int> A(N);
    ll out=0;
    for(int i=0;i<N;i++){ cin >> A[i];}
    for(int i=0;i<N;i++){
        int tmp=1;
        int c=1;
        while(tmp<=D){
            out++;
            tmp = c*A[i]+1;
            c++;
        }
        //cerr << out << "\t";
    }
    cout << out+X << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define in insert
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define all(x) (x).begin(), (x).end()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = 1e9 + 5;
int main(){
    int n, k;
    cin >> n >> k;
    int a[n];
    int d[n];
    for(int i = 0; i < n; i++) cin >> a[i];
    d[0] = 0;
    for(int i = 1; i < n; i++){
        d[i] = INF;
        for(int j = 1; j <= k; j++){
            if(i-j >= 0){
                d[i] = min(d[i], d[i-j] + abs(a[i] - a[i-j]));
            }
        }
    }
    cout << d[n-1];
}

Measured memory_bytes: 1024
import java.util.*;
public class Main{
    public static void main(String[] args){
	new Main().run();
    }
    Scanner sc = new Scanner(System.in);

    Yield[] yield;
    int n;

    void run(){
	while(sc.hasNext()){
	    n = sc.nextInt();
	    if(n==0) break;
	    yield = new Yield[n];
	    for(int i=0; i<n; i++)
		yield[i] = new Yield();

	    sort();
	    show();
	    System.out.println("#");
	}
    }

    void sort(){
	// バブルか何かのソート書く
	for(int i=0; i<n-1; i++){
	    for(int k=n-1; k>i; k--){
		double e1 = yield[i].getEffi();
		double e2 = yield[k].getEffi();
		if(e1<e2){
		    Yield tmp = yield[i];
		    yield[i] = yield[k];
		    yield[k] = tmp;
		}
		else if(e1==e2 &&
			yield[i].getName().compareToIgnoreCase(yield[k].getName())>0){
		    Yield tmp = yield[i];
		    yield[i] = yield[k];
		    yield[k] = tmp;
		}
	    }
	}
    }
	
    void show(){
	for(int i=0; i<n; i++)
	    System.out.println(yield[i].getName()/*+" "+yield[i].getEffi()*/);
    }
    
    class Yield{
	String name;
	double p, a, b, c, d, e, f, s, m;
	double time, made;
	double effi;

	Yield(){
	    name = sc.next();
	    effi = calc();
	}
	String getName(){ return name; }
	double getEffi(){ return effi; }

	double calc(){
	    p = sc.nextInt();
	    a = sc.nextInt();
	    b = sc.nextInt();
	    c = sc.nextInt();
	    d = sc.nextInt();
	    e = sc.nextInt();
	    f = sc.nextInt();
	    s = sc.nextInt();
	    m = sc.nextInt();

	    time = a+b+c;
	    made = 0;
	    for(int i=0; i<m; i++){
		time += (d+e);
		made += f;
	    }

	    made = made*s - p;
	    return made/time;
	}
    }
}

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

int main()
{
	long long int a, b, c, ans;
	cin >> a >> b >> c;
	if (a % 2 == 0 || b % 2 == 0 || c % 2 == 0)
		cout << 0;
	else
	{
		if (a >= b && a >= c)
		{
			if (a % 2 == 0)
				ans = 0;
			else
				ans = b * c;
		}
		else if (b >= a && b >= c)
		{
			if (b % 2 == 0)
				ans = 0;
			else
				ans = a * c;
		}
		else if (c >= a && c >= b)
		{
			if (c % 2 == 0)
				ans = 0;
			else
				ans = a * b;
		}
		cout << ans;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#define INF 100000000

using namespace std;

int main(void) {
	int N,M;
	while (cin >> N >> M, N) {
		vector<int> C(M);
		for (int i = 0; i < M; ++i) {
			cin >> C[i];
		}
		vector<int> x(N);
		for (int i = 0; i < N; ++i) {
			cin >> x[i];
		}

		vector< vector<int> > dp(256,vector<int>(N+1));
		for (int i = 0; i < 256; ++i) {
			for (int j = 0; j < N+1; ++j) {
				dp[i][j] = INF;
			}
		}
		dp[128][0] = 0;

		for (int j = 0; j < N; ++j) {
			for (int i = 0; i < 256; ++i) {
				if (dp[i][j] != INF) {
					for (int k = 0; k < M; ++k) {
						if (C[k]+i > 255) {
							dp[255][j+1] = min(dp[255][j+1],dp[i][j]+(int)pow(x[j]-255,2));
						}
						else if (C[k]+i < 0) {
							dp[0][j+1] = min(dp[0][j+1],dp[i][j]+(int)pow(x[j]-0,2));
						}
						else {
							dp[C[k]+i][j+1] = min(dp[C[k]+i][j+1],dp[i][j]+(int)pow(x[j]-C[k]-i,2));
						}
					}
				}
			}
		}

		int res = INF;
		for (int i = 0; i < 256; ++i) {
			if (dp[i][N] < res) {
				res = dp[i][N];
			}
		}
		cout << res << endl;
	}
	return 0;
}

Measured memory_bytes: 22780
import itertools as it
n = int(input())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
d = []
ans = []
for i in range(1,n+1):
    d.append(i)
for i in it.permutations(d,n):
    ans.append(list(i))
print(abs(ans.index(p)-ans.index(q)))

Measured memory_bytes: 10228
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

def f(l, s):
    return s if l % s == 0 else f(s, l % s)

z = f(max(a), min(a))
for i in a:
    z = f(i, z)
if max(a) >= k and k % z == 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Measured memory_bytes: 14252
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
using namespace std;
 
#define dump(x)  cout << #x << " = " << (x) << endl;
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl
 
#define SANKOU(n,a,b) cout << ((n) ? (#a) : (#b) ) << endl
 
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
 
#define FOREACH(x,a) for(auto& (x) : (a) )
 
#define WFA(d,v) REP(k,v)REP(i,v)REP(j,v)d[i][j]=min(d[i][j],d[i][k]+d[k][j])
 
#define SCOUT(x) cout<<(x)<<" "
#define ENDL cout<<endl
 
#define VECCIN(x) for(auto&youso_: (x) )cin>>youso_
#define VECIN2(x,y) REP(i,x.size())cin>>x[i]>>y[i]
#define VECCOUT(x) for(auto&youso_: (x) )cout<<youso_<<" ";cout<<endl
 
#define ALL(obj) (obj).begin(),(obj).end()
 
#define EXIST(n,x) (find(ALL(n),x)!=n.end())
#define UNIQUE(obj) sort(ALL( obj )); obj.erase(unique(ALL(obj)),obj.end())
#define COUT(x) cout<<(x)<<endl
void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail){
    cin>>head;
    CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)
 
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision; // cpp_int
 
#define P pair<int,int>
#define V vector<ll>
#define M map<int,int>
#define S set<int>
#define L list<int>
 
#define pb(a) push_back(a)
#define mp make_pair

int main(){

  CIN(n);V a(n);VECCIN(a);
  ll ans=LINF;
  FOR(i,-100,101){
    ll cost = 0;
    REP(j,n)if(i!=a[j])cost+=pow(i-a[j],2);
    ans=min(ans,cost);
  }
  COUT(ans);

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define F(i,n) for (int i = 0; i < n; ++i)
#define F1(i,n) for (int i = 1; i <= n; ++i)
#define dbg(x) cerr << #x << " = " << x << endl
#define dbgg(x) cerr << #x << " = " << x << ' '
#define T(x) x[pool]
#define mineq(x,y) { if ((x) > (y)) (x) = (y); }
#define maxeq(x,y) { if ((x) < (y)) (x) = (y); }
#define MEOW cout << "meowwwww" << '\n'; system("pause");
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;

template<typename T>
ostream& operator <<(ostream &s, const vector<T> &c)
{
	s << "[ "; for (auto it : c) s << it << " "; s << "\b]\n";
	return s;
}

template<typename T>
ostream& operator <<(ostream &s, const pair<int, T> &c)
{
	s << "[ "; cout << c.fi << " , " << c.se << " ] ";
	return s;
}

const int maxn = 123456, maxkk = 2345;
int n, k, x[maxn], y[maxn], c[maxn], diff[maxkk][maxkk];
void input()
{
	cin >> n >> k;
	F1 (i, n)
	{
		char C;
		cin >> x[i] >> y[i] >> C;
		c[i] = C == 'B'; 
	} 
}

void pre(int x, int y, int e)
{
	diff[1][1] += e;
	diff[1][y + 1] -= e;
	diff[x + 1][1] -= e;
	diff[x + 1][y + 1] += e;
} 

void add(int a, int b, int c, int d)
{
	++a, ++b, ++c, ++d;
	if (b < a || d < c) return;
	pre(a - 1, d, -1);
	pre(b, c - 1, -1);
	pre(a - 1, c - 1, 1);
	pre(b, d, 1);
}

void solve()
{
	int ans = 0;
	F1 (i, n)
	{
		int v[2];
		vector<pii> v0[2], v1[2];
		v[0] = x[i] % (k + k), v[1] = y[i] % (k + k); 
		F (t, 2)
		{
			if (v[t] < k)
			{
				v0[t].pb(mp(0, k - v[t] - 1));
				v0[t].pb(mp(k + k - v[t], k + k - 1));
				v1[t].pb(mp(k - v[t], k + k - v[t] - 1));
			} else
			{
				v0[t].pb(mp(k + k - v[t], k + k + k - v[t] - 1));
				v1[t].pb(mp(0, k + k - v[t] - 1));
				v1[t].pb(mp(k + k + k - v[t], k + k - 1));
			}
		}
		if (c[i])
		{
			for (auto xx : v0[0]) for (auto yy : v0[1])
				add(xx.fi, xx.se, yy.fi, yy.se);
			for (auto xx : v1[0]) for (auto yy : v1[1])
				add(xx.fi, xx.se, yy.fi, yy.se);
		} else
		{
			for (auto xx : v0[0]) for (auto yy : v1[1])
				add(xx.fi, xx.se, yy.fi, yy.se);
			for (auto xx : v1[0]) for (auto yy : v0[1])
				add(xx.fi, xx.se, yy.fi, yy.se);
		}
	}
	F1 (i, k + k) F1 (j, k + k)
		ans = max(ans, diff[i][j] += 
			diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1]);
	cout << ans << '\n';
}

main()
{
	input();
	solve();
}

Measured memory_bytes: 20992
#include <stdio.h>
 
int main(void)
{
    int n,i;
     long int a=0;
  
    scanf("%d",&n);
  
    for(i=1;i<=n;i++){
        if(((i%3)!=0)&&((i%5)!=0)) a=a+i;
    }
    
     printf("%ld\n",a);
  
     return 0;
}  

Measured memory_bytes: 1688
#include <bits/stdc++.h>
#define MAX_N 200000
using namespace std;
typedef long long lnt;
const lnt INF = 0x3f3f3f3f3f3f3f3fLL;
template <class T> inline void read(T &x) {
	x = 0; int c = getchar(), f = 1;
	for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
	for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n; lnt s[MAX_N+5], mi, mx, ans = INF;
int main() {
	read(n);
	for (int i = 1; i <= n; i++)
		read(s[i]), s[i] += s[i-1];
	for (int l = 1, p = 2, r = 3; p < n; p++) {
		mi = INF;
		for (; l < p; l++)
			if (abs(s[l]-(s[p]-s[l])) < mi)
				mi = abs(s[l]-(s[p]-s[l]));
			else break;
		mi = INF;
		for (r = max(r, p+1); r <= n; r++)
			if (abs((s[r]-s[p])-(s[n]-s[r])) < mi)
				mi = abs((s[r]-s[p])-(s[n]-s[r]));
			else break;
		l--, r--;
		mi = min(min(s[l], s[p]-s[l]), min(s[r]-s[p], s[n]-s[r]));
		mx = max(max(s[l], s[p]-s[l]), max(s[r]-s[p], s[n]-s[r]));
		ans = min(ans, mx-mi);
	}
	return printf("%lld\n", ans), 0;
}


Measured memory_bytes: 1792
import Control.Applicative
import Control.Monad
import Text.Printf


type Process = (String, Int)

roundRobin :: Int -> Int -> [Process] -> [Process] -> [Process] -> [Process]
roundRobin q t [] []  ys = reverse ys
roundRobin q t [] xs' ys = roundRobin q t (reverse xs') [] ys
roundRobin q t ((name, time) : xs) xs' ys
  | time <= q = roundRobin q (t + time) xs xs' ((name, t + time) : ys)
  | otherwise = roundRobin q (t + q) xs ((name, time - q) : xs') ys

main :: IO ()
main = do
  [n, q] <- map read . words <$> getLine
  xs <- map (toTuple . words) <$> replicateM n getLine
  mapM_ (\(n, t) -> printf "%s %d\n" n t) $ roundRobin q 0 xs [] []
    where toTuple [n, t] = (n, read t)



Measured memory_bytes: 45176
N,A,B = list(map(int, input().split()))
dict_sum_of_integers = {}
Answer = 0

for i in range(1, N+1):
    sum_of_digits = 0
    quotient = i
    while True:
        if quotient//10 > 0:
            sum_of_digits += quotient%10
            quotient = quotient//10
        else:
            sum_of_digits += quotient%10
            break
    dict_sum_of_integers[i] = sum_of_digits

for k in dict_sum_of_integers.keys():
    if A<=dict_sum_of_integers[k]<=B:
        Answer += k

print(Answer)

Measured memory_bytes: 3796
#include<bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(ll i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i, h)cin >> s.at(i);
    ll ans = 0, x, y, dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
    rep(i,  h){
        rep(j, w){
            if(s[i][j] == '#')continue;
            ll a[h][w], ma = -1;
            rep(k, h){
                rep(l, w){
                    if(s[k][l] == '#')a[k][l] = -1;
                    else a[k][l] = inf;
                }
            }
            a[i][j] = 0;
            queue<P> que;
            que.push({i, j});
            while(!que.empty()){
                P p = que.front();
                que.pop();
                x = p.first; y = p.second;
                for(int i = 0; i < 4; i++) {
                    ll nx = x + dx[i], ny = y + dy[i];
                    if (nx < 0 || nx >= h || ny < 0 || ny >= w)continue;
                    if (a[nx][ny] == inf) {
		                a[nx][ny] = a[x][y] + 1;
                        ma = max(ma, a[nx][ny]);
		                que.push({ nx,ny });
                    }
                }
            }
            ans = max(ans, ma);
        } 
    }
    cout << ans;
}


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

int main() {
  
  int K=0, X=0;
  
  cin >> K >> X;
  
  int ans = 500*K;
  
  if(X<=ans) {
    
    cout << "Yes" << endl;
    
  } else {
    
    cout << "No" << endl;
    
  }
  
  return 0;
  
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
	int n, i, j, count=0, tmp;
	scanf("%d", &n);
	int a[n];
	for(i=0; i<n; i++){
		scanf("%d", &a[i]);
	}
	for(i=0; i<n-1; i++){
		for(j=n-1; j>i; j--){
			if(a[j-1]>a[j]){
				tmp=a[j-1];
				a[j-1]=a[j];
				a[j]=tmp;
				count++;
			}
		}
	}
	for(i=0; i<n-1; i++){
		printf("%d ", a[i]);
	}
	
	printf("%d\n", a[n-1]);
	
	printf("%d\n", count);
	
	return 0;
}


Measured memory_bytes: 2060
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<algorithm>
#include<iostream>
#include<cstring>
#include<fstream>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define INF 0X3F3F3F3F
#define N 305
#define M 200005
#define LL long long
#define ULL unsigned long long
#define FF(i, a, b) for(int i = a; i <= b; ++i)
#define RR(i, a, b) for(int i = a; i >= b; --i)
#define FJ(i, a, b) for(int i = a; i < b; ++i)
#define SC(x) scanf("%d", &x)
#define SCC(x, y) scanf("%d%d", &x, &y)
#define SCCC(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define SS(x) scanf("%s", x)
#define PR(x) printf("%d\n", x)
#define CL(a, x) memset(a, x, sizeof(a))
#define _P fd[rt]
#define _L fd[rt << 1]
#define _R fd[rt << 1 | 1]
#define MID int mid = ((l + r) >> 1)
#define lson rt<<1 ,l, mid
#define rson rt<<1 | 1, mid + 1, r
#define VI vector<int>
#define db long double
#define PII pair<int, int>
#define PLL pair<unsigned long long, unsigned long long>
#define MP make_pair
#define PB push_back
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
using namespace std;
const int MOD = 1000000007;
const double PI = acos(-1.0);
const double EPS = 1e-8;
inline void II(int &n){char ch = getchar(); n = 0; bool t = 0;
for(; ch < '0'; ch = getchar()) if(ch == '-') t = 1;
for(; ch >= '0'; n = n * 10 + ch - '0', ch = getchar()); if(t) n =- n;}
inline void OO(int a){if(a < 0) {putchar('-'); a = -a;}
if(a >= 10) OO(a / 10); putchar(a % 10 + '0');}
inline int sgn(double x){return (x > EPS) - (x < -EPS);}
int f[1005][5005], w[1005], g[1005], n, x;
vector<int> e[1005];
inline void up(int &x, int y){
    if(x > y) x = y;
}
int main(){
    //IN;
    SC(n);
    FF(i, 2, n){
        SC(x);
        e[x].PB(i);
    }
    memset(g, 0x3f, sizeof(g));
    FF(i, 1, n) SC(w[i]);
    RR(i, n, 1){
        int sz = e[i].size();
        for(int i = 0; i <= sz; ++i) memset(f[i], 0x3f, sizeof(f[i]));
        f[0][0] = 0;
        for(int j = 0; j < sz; ++j){
            int v = e[i][j];
            for(int k = 0; k <= w[i]; ++k){
                if(k >= g[v]) up(f[j + 1][k], f[j][k - g[v]] + w[v]);
                if(k >= w[v]) up(f[j + 1][k], f[j][k - w[v]] + g[v]);
            }
        }
        int ret = INF;
        for(int k = 0; k <= w[i]; ++k) up(ret, f[sz][k]);
        if(ret == INF) break;
        g[i] = ret;
    }
    if(g[1] == INF) puts("IMPOSSIBLE");
    else puts("POSSIBLE");
    return 0;
}


Measured memory_bytes: 19840
#include<iostream>
#include<vector>

using namespace std;

int main(){
  int N; cin >> N;
  vector<int> p(N);
   for(int i = 0; i < N; i++){
     cin >> p[i];}
  int cnt = 0;
  for(int i = 0 ; i <= N - 3; i++){
    if( p[i] <= p[i+1] && p[i+1] <= p[i+2] ){ cnt++;}
    else if( p[i] >= p[i+1] && p[i+1] >= p[i+2] ) { cnt++; }}
  
  cout << cnt << endl; return 0;}

Measured memory_bytes: 256
import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        String s = sc.next();
        String t = sc.next();
        System.out.println(t.startsWith(s)&&t.length() == s.length()+1?"Yes":"No");
    }
}


Measured memory_bytes: 35684
#![allow(unused_imports)]
use std::cmp::*;
use std::collections::*;
use itertools::Itertools;
use num::clamp;
use proconio::{input, marker::*, fastout};
use superslice::*;

#[fastout()]
fn main() {
    input! {
        n: usize,
        a: [u64; n]
    }
    let m = 1_000_000_007u64;

    let mut ap = Vec::new();
    for mut v in a {
        let mut vp = HashMap::new();
        for p in 2.. {
            if p * p > v {
                break;
            }
            let mut count = 0;
            while v % p == 0 {
                count += 1;
                v /= p;
            }
            if count > 0 {
                vp.insert(p, count);
            }
        }
        if v != 1 {
            vp.insert(v, 1);
        }
        ap.push(vp);
    }

    let mut lcm_map = HashMap::new();
    for vp in &ap {
        for (&p, &count) in vp.iter() {
            lcm_map.entry(p).and_modify(|c| *c = max(*c, count)).or_insert(count);
        }
    }

    let mut lcm_int = 1;
    for (&p, &count) in &lcm_map {
        for _ in 0..count {
            lcm_int *= p;
            lcm_int %= m;
        }
    }

    let mut ans = 0;
    for vp in ap {
        let mut res = lcm_int;
        for (&p, &count) in &vp {
            for _ in 0..count {
                res *= mod_inverse(p, m);
                res %= m;
            }
        }
        ans += res;
        ans %= m;
    }
    println!("{}", ans);
}
#[allow(dead_code)]
pub fn gcd(a: u64, b: u64) -> u64 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}
#[allow(dead_code)]
/// (gcd, x, y)
pub fn extgcd(a: i64, b: i64) -> (i64, i64, i64) {
    if b == 0 {
        (a, 1, 0)
    } else {
        let (gcd, x, y) = extgcd(b, a % b);
        (gcd, y, x - (a / b) * y)
    }
}
#[allow(dead_code)]
pub fn mod_inverse(a: u64, m: u64) -> u64 {
    let (_, x, _) = extgcd(a as i64, m as i64);
    ((m as i64 + x) as u64 % m) % m
}


Measured memory_bytes: 4180
#include<iostream>
using namespace std;
int main()
{
  int n,i,c=0,f=0;
  
  cin>>n;
  int a[n],b[n];
  for(i=0;i<n;i++)
  {
    cin>>a[i];
    cin>>b[i];
  }
  for(i=0;i<n-2;i++)
  {
    if(a[i]==b[i] && a[i+1]==b[i+1] && a[i+2]==b[i+2])
    {
      f=1;
      break;
    }
  }
  if(f==1)
    cout<<"Yes";
  else
    cout<<"No";
}
    

Measured memory_bytes: 3136
#include <bits/stdc++.h>
using namespace std;
int n,x,b[100005],l[100005],u[100005],perm[100005];
long long a,p[100005];
bool cmp(int a,int b)
{
	return p[a]>p[b];
}
bool check(long long h)
{
	int idx=h/x;
	long long sum=0,na=a;
	for (int i=0;i<idx;i++)
	{
		sum+=1LL*u[perm[i]]*x;
		na+=1LL*(u[perm[i]]-l[perm[i]])*b[perm[i]];
	}
	if (sum>=na)
	return 1;
	for (int i=idx;i<n;i++)
	{
		if (sum+1LL*l[perm[i]]*(h%x)>=na || sum+1LL*u[perm[i]]*(h%x)>=na+1LL*(u[perm[i]]-l[perm[i]])*b[perm[i]])
		return 1;
	}
	sum+=1LL*u[perm[idx]]*x;
	na+=1LL*(u[perm[idx]]-l[perm[idx]])*b[perm[idx]];
	for (int i=0;i<idx;i++)
	{
		if (sum+1LL*u[perm[i]]*(h%x-x)>=na || sum-1LL*u[perm[i]]*x+1LL*l[perm[i]]*(h%x)>=na-1LL*(u[perm[i]]-l[perm[i]])*b[perm[i]])
		return 1;
	}
	return 0;
}
int main()
{
	scanf("%d%d",&n,&x);
	for (int i=0;i<n;i++)
	{
		scanf("%d%d%d",&b[i],&l[i],&u[i]);
		a+=1LL*b[i]*l[i];
		p[i]=1LL*u[i]*x+1LL*b[i]*(l[i]-u[i]);
		perm[i]=i;
	}
	sort(perm,perm+n,cmp);
	long long st=0,en=1LL*n*x;
	while (st!=en)
	{
		long long mid=(st+en)/2;
		if (check(mid))
		en=mid;
		else
		st=mid+1;
	}
	printf("%lld",st);
}

Measured memory_bytes: 6160
#include<bits/stdc++.h>
using namespace std;
#define db double
db n, m, d;

int main(){
    cin >> n >> m >> d;
    db ans = ((db)1 - d/n) * ((m - (db)1)/n);
    cout << fixed << setprecision(10) << (d != 0 ? (db)2 : (db)1) * ans << endl;
    return 0;
}

Measured memory_bytes: 256
from sys import stdin
N, K = map(int, stdin.readline().split())
pos_a = []
for i in range(1, K+1):
    if (-2*i) % K == 0:
        pos_a.append(i)
ans = 0
for a in pos_a:
    tmp = (-a) % K
    count = len(range(a, N+1, K))
    ans += count * len([i for i in range(tmp, N+1, K) if i > 0])**2
print(ans)


Measured memory_bytes: 11032
N = int(input())
A = [0] + [int(input()) for _ in range(N)]

x = 1
visited = set([1])
answer = 0

while True:
  x = A[x]
  if x in visited:
    answer = -1
    break
  visited.add(x)
  answer += 1
  if x == 2:
    break
    
print(answer)

Measured memory_bytes: 56792
#include <bits/stdc++.h>
#define el_cucuy ios_base::sync_with_stdio(0), cout.tie(0); cin.tie(0);
#define llong long long
#define pb push_back
#define bpc __builtin_popcount

const llong mxn = 1e6 + 7;
const llong mod = 1e9 + 7;
const llong inf = 1e18 + 9;

using namespace std;

llong n, k, a[mxn], dp[mxn];

int main(){
    el_cucuy
    cin >> n >> k;
    for (int i = 1; i <= n; i ++){
        cin >> a[i];
    }dp[1] = 0;
    dp[2] = abs(a[1] - a[2]);
    int m = k;
    for (int i = 3; i <= n; i ++){
        dp[i] = inf;
        for (int j = 1; j <= min(i - 1, m); j ++){
            dp[i] = min(dp[i], dp[i - j] + abs(a[i] - a[i - j]));
        }
    }cout << dp[n];
    return 0;
}


Measured memory_bytes: 5120
// +build ignore
package main

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

func solve(sc *scanner, wr *bufio.Writer) int {
	H := sc.i()
	W := sc.i()
	K := sc.i()
	C := make([][]int, H)
	for h := 0; h < H; h++ {
		C[h] = make([]int, W)
		s := sc.s()
		for w, c := range s {
			if c == '#' {
				C[h][w] = 1
			}
		}
	}

	total := 0

	var fn func(r []int)
	var fn2 func(r, c []int)

	fn = func(r []int) {
		if len(r) > H {
			return
		}

		fn2(r, []int{})

		v := 0
		if len(r) > 0 {
			v = r[len(r)-1] + 1
		}
		for i := v; i < H; i++ {
			fn(append(r, i))
		}
	}

	fn2 = func(r, c []int) {
		if len(c) > W {
			return
		}

		count := 0
		for i := 0; i < H; i++ {
			foundR := false
			for _, v := range r {
				if v == i {
					foundR = true
				}
			}
			if foundR {
				continue
			}
			for j := 0; j < W; j++ {
				foundC := false
				for _, v := range c {
					if v == j {
						foundC = true
					}
				}
				if foundC {
					continue
				}

				count += C[i][j]
			}
		}

		if count == K {
			total++
		}

		// fmt.Println("count", count, "total", total, "r", r, "c", c)

		v := 0
		if len(c) > 0 {
			v = c[len(c)-1] + 1
		}
		for i := v; i < W; i++ {
			fn2(r, append(c, i))
		}
	}

	fn([]int{})

	fmt.Println(total)

	return 0
}

func main() {
	sc := newScanner(os.Stdin)
	wr := bufio.NewWriter(os.Stdout)
	ret := solve(sc, wr)
	wr.Flush()
	os.Exit(ret)
}

// I/O
type scanner struct {
	sc *bufio.Scanner
}

func newScanner(input io.Reader) *scanner {
	sc := bufio.NewScanner(input)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &scanner{sc}
}

func (s *scanner) s() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *scanner) i() int {
	i, e := strconv.Atoi(s.s())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *scanner) f() float64 {
	f, e := strconv.ParseFloat(s.s(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *scanner) bs() []byte {
	return []byte(s.s())
}

func (s *scanner) is(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.i()
	}
	return res
}

func (s *scanner) fs(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.f()
	}
	return res
}


Measured memory_bytes: 1864
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
int main(){
  vector<int>l;
  set<int> s;
  int n,m,a;
  cin>>n>>m;
  for(int i=0;i<n;i++){
    int a;
    cin>>a;
    l.push_back(a);
  }
  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    if(l.at(a-1)>l.at(b-1)){
      s.insert(b);
    }
    else if(l.at(a-1)==l.at(b-1)){
      s.insert(a);
      s.insert(b); 
    }
    else{
      s.insert(a);
    }
  }
  a=n-s.size();
  cout<<a;
}

Measured memory_bytes: 6436
"""https://atcoder.jp/contests/hokudai-hitachi2019-1/tasks/hokudai_hitachi2019_1_a
Time Limit: 30 sec / Memory Limit: 1024 MB
"""


def get_orders(order_time):
    n_new_order = int(input())
    orders = []
    for _ in range(n_new_order):
        order_id, destination = map(int, input().split())
        orders.append((order_id, order_time, destination))
    return orders


def get_input():
    n_vertices, n_edges = map(int, input().split())
    graph = [[] for i in range(n_vertices+1)]
    for _ in range(n_edges):
        u, v, d = map(int, input().split())
        graph[u].append((v, d))
        graph[v].append((u, d))
    time_max = int(input())
    orders = []
    for time_index in range(time_max):
        new_orders = get_orders(time_index)
        for order in new_orders:
            orders.append(order)
    return n_vertices, n_edges, graph, time_max, orders


def main():
    n_vertices, n_edges, graph, time_max, orders = get_input()
    for i in range(time_max):
        print(-1)


if __name__ == "__main__":
    main()


Measured memory_bytes: 56152
def compare(x, y):
    for i in range(6):
        order = [0, 0, 0]
        for j in range(3):
            if {x[j], x[-j-1]} != {y[z[i][j]], y[-z[i][j]-1]}:
                break
            if x[j] == y[z[i][j]]:
                order[j] = 1
                if x[j] == x[-j-1]:
                    order[j] = 2
        else:
            if 2 in order:
                return True
                break
            if z[i][3] in [0, 3] and sum(order) % 2:
                return True
                break
            if z[i][3] == 1 and not sum(order) % 2:
                return True
                break
    return False
 
n = int(input())
x = [[] for i in range(n)]
for i in range(n):
    x[i] = list(map(int, input().split()))
z = [[0, 1, 2, 3], [0, 2, 1, 1], [1, 0, 2, 1], [2, 0, 1, 0], [1, 2, 0, 0], [2, 1, 0, 1]]
different = True
for i in range(n):
    for j in range(i+1, n, 1):
        if compare(x[i], x[j]):
            different = False
            break
    if not different:
        break
if different:
    print('Yes')
else:
    print('No')

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

int main()
{
    int a[5] = {};
    for(int i = 0; i < 5; i++){
        cin >> a[i];
    }
    int mi = 10;
    int num;
    for(int i = 0; i < 5; i++){
        if(a[i]%10 != 0){
            if(a[i]%10 < mi){
                mi = a[i]%10;
                num = i;
            }
        }
    }
    // cout << mi << " " << num << endl;
    int ans = 0;
    for(int i = 0; i < 5; i ++){
        if(num != i && a[i]%10 != 0){
            ans += a[i]+(10-a[i]%10);
        }else{
            ans += a[i];
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
int main() {
  string s;
  cin >> s;
  int cnt = 0;
  char c = 'A';
  rep(i,(int)s.size()) {
    if( (c-'A') >= (s[i]-'A') ) ++cnt;
    c = s[i];
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 3224