akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
using p = pair<int,int>;
using Graph = vector<vector<int>>;
int main(int argc, const char * argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin>>n;
    int p[n];
    rep(i,n){
        cin>>p[i];
    }
    int cnt=0;
    for(int i=1;i<n-1;i++){
        if((p[i]>p[i-1]&&p[i]<p[i+1])||(p[i]<p[i-1]&&p[i]>p[i+1]))cnt++;
    }
    cout<<cnt<<endl;

    return 0;
}

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

#define pout(n)  printf ("%d\n", n)

#define rep(i,a,n) for (int i = a;i < n;i++)
#define per(i,n,a) for (int i = n-1;i >= a;i--)
#define BIT(bit,a,n) for (int bit = a;bit < (1<<n);bit++) // {0, 1, ..., n-1} の部分集合の全探索 // n番目のフラグが立っている状態は (1<<n)

const int d4x[4] = {1, 0, -1, 0};
const int d4y[4] = {0, 1, 0, -1};
const int d8x[8] = { 1,1,0,-1,-1,-1,0,1 };
const int d8y[8] = { 0,1,1,1,0,-1,-1,-1 };

#define MAX_N (int)2e5+20

typedef long long ll;
using namespace std;

int h,w;
int ans = 1;
int main() {
    scanf("%d%d",&h,&w);
    char s[h][w];
    rep(i,0,h){
        rep(j,0,w){
            cin >> s[i][j];
        }
    }
    rep(i,0,h){
        rep(j,0,w){
            if(s[i][j] == '.'){
                int cnt = 0;
                rep(k,0,8){
                    int cx = i+d8x[k];
                    int cy = j+d8y[k];

                    if( cx >= 0 && cx < h && cy >= 0 && cy < w && s[cx][cy] == '#'){
                        cnt++;
                    }
                }
                printf("%d",cnt);
            }
            else{
                printf("%c",s[i][j]);
            }
        }
        printf("\n");
    }
    return 0;
}

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

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define MX              200005
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define pw(b,p)         pow(b,p) + 0.1

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    // cin>>t;
    // while(t--){
        
    //     cout<<'\n';
    // }
    int n;
    cin>>n;
    int ans=0;
    int d=n/500;
    ans+=(1000*(d));
    int x=n-(500*d);
    ans+=(x/5)*5;
    cout<<ans<<endl;
    return 0;
}




Measured memory_bytes: 256
#include <cstdio>
#include <vector>
using namespace std;

const double INF = 1e30;

typedef struct
{
  int P, T, V;
  double goal;
} Runner;

int main()
{
  int N, M, L;
  while (~scanf("%d %d %d", &N, &M, &L)) {
    vector<Runner> r(N);
    for (int i = 0; i < N; ++i) {
      scanf("%d %d %d", &r[i].P, &r[i].T, &r[i].V);
      if (r[i].V == 0)
	r[i].goal = INF;
      else
	r[i].goal = L / static_cast<double>(r[i].V);
    }

    vector<vector<double> > p(N, vector<double>(M+1, 1.0));
    for (int i = 0; i < N; ++i) {
      vector<vector<double> > dp(M+1, vector<double>(M+1, 0.0));
      dp[0][0] = 1.0;
      for (int j = 0; j < M; ++j) {
	for (int k = 0; k < M; ++k) {
	  dp[j+1][k]   += dp[j][k] * ((100 - r[i].P) / 100.0);
	  dp[j+1][k+1] += dp[j][k] * (r[i].P / 100.0);
	}
      }
      for (int j = 0; j < M+1; ++j)
	p[i][j] = dp[M][j];
    }

    vector<vector<double> > pp(N, vector<double>(M+1));
    for (int i = 0; i < N; ++i) {
      for (int j = M; j >= 0; --j) {
	pp[i][j] = p[i][j];
	if (j != M)
	  pp[i][j] += pp[i][j+1];
      }
    }

    vector<double> ans(N, 0.0);
    for (int i = 0; i < N; ++i) {
      if (r[i].goal == INF)
	continue;

      for (int j = 0; j < M+1; ++j) {
	double m_ans = p[i][j];
	double time = r[i].goal + r[i].T * j;
	for (int k = 0; k < N; ++k) {
	  if (i == k)
	    continue;
	  if (time - r[k].goal >= 0.0) {
	    int rest = static_cast<int>((time - r[k].goal) / static_cast<double>(r[k].T)) + 1;
	    if (rest > M || r[k].T == 0) {
	      m_ans = 0.0;
	      break;
	    }
	    m_ans *= pp[k][rest];
	  }
	}
	ans[i] += m_ans;
      }
    }

    for (int i = 0; i < N; ++i)
      printf("%.8f\n", ans[i]);
  }
  return 0;
}

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


def main():
    n = int(input())
    ans = 0

    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0 and (i ** 2) != n:
            m = n // i - 1

            if n // m == n % m:
                ans += m

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    string S; cin >> S;
    F0R(i, S.size()) {
    	if (S[i] == '1') {
    		S[i] = '9';
    	} else S[i] = '1';
    }
    cout << S << endl;
    
    return 0;
}

// read the question correctly (ll vs int)
// template by bqi343

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
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;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll mod=1e9+7;
const int inf=1<<30;

int main(){
  ll n; cin >> n;
  ll a=0;
  for(int i=1;i<=sqrt(n);i++){
    if(n%i==0) a=i;
  }
  ll b=n/a;
  ll ans=max(to_string(a).size(),to_string(b).size());
  cout << ans << endl;
  
}

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

int main(){
  string s;
  cin >> s;

  int n;
  n = s.size();

  vector<int> ans(n, 0);
  int cnt;
  rep(ri, 2){
    cnt = 0;
    rep(i, n){
      if(s[i] == 'R'){
        cnt++;
      }else{
        ans[i] += cnt / 2;
        ans[i-1] += (cnt + 1) / 2;
        cnt = 0;
      }
    }
    reverse(ans.begin(), ans.end());
    reverse(s.begin(), s.end());
    rep(i, n){
      if(s[i] == 'L'){
        s[i] = 'R';
      }else{
        s[i] = 'L';
      }
    }
  }

  rep(i, n){
    if(i) cout << " ";
    cout << ans[i];
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 1152
import re

S = input().replace('?', '.')
T = input()
for i in range(len(S)-len(T), -1, -1):
    if re.match(S[i:i+len(T)], T):
        S = S.replace('.', 'a')
        print(S[:i] + T + S[i+len(T):])
        exit()
print('UNRESTORABLE')


Measured memory_bytes: 3188
a, b, k = map(int, input().split())

if a > b:
  a, b = b, a
ans = 0
count = 0
for n in range(a, 0, -1):
  if a % n == 0 and b % n == 0:
    count += 1
    if count == k:
      ans = n
      break
print(ans)

Measured memory_bytes: 3064
// Round Up the Mean

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main(){
	int a,b;
	cin >> a >> b;

	if ((a+b) % 2)
		cout << (a+b)/2 + 1 << endl;
	else
		cout << (a+b)/2 << endl;

	return 0;
}

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

int main()
{
    int n, m;
    cin >> n >> m;
    int l = 0, r = n - 1;
    for (int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        l = max(l, a);
        r = min(r, b);
    }
    int ans = max(0, r - l + 1);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
while 1:
 a=[list(map(int,input()))for _ in[0]*8]
 y=[sum(r)for r in a]
 x=[sum(c)for c in zip(*a)]
 if 4 in x:print('B')
 elif 4 in y:print('C')
 elif 1 in y:print('DF'[a[y.index(1)][x.index(2)]])
 elif 1 in x:print('GE'[a[y.index(2)][x.index(1)]])
 else:print('A')
 try:input()
 except:break


Measured memory_bytes: 5616
#include<iostream>
using namespace std;
#include<stdio.h>
#include<cstdio>

int main(){
    
    int num = 0;
    char fig[1001];
    
    while(1){
        scanf( "%s",fig );
        if ( fig == "0" ) break;
        for ( int i = 0; fig[i] != '\0'; i++){
            num += fig[i] - '0';
        }
        if ( num == 0) break;
        printf ( "%d\n", num );
        num = 0;
    }
    return 0;
}



Measured memory_bytes: 3192
#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<iomanip>

using namespace std;

double H_rad(double h, double m) {
    return h/12 * 2 * M_PI + m/60 * 2 * M_PI / 12;
}

double M_rad(double m) {
    return m/60.0 * 2.0 * M_PI;
}

double radDiff(double a, double b) {
    if (a < b) swap(a, b);
    return a - b;
}

int main() {
    double a, b, h, m;
    cin >> a >> b >> h >> m;
    double theta = radDiff(H_rad(h, m), M_rad(m));
    double result = sqrt( (b * cos(theta) - a) * (b * cos(theta) - a) + (b * sin(theta)) * (b * sin(theta)) );
    cout << fixed << setprecision(10) << result << endl;
}


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

int main(){
    ll X;
    cin >> X;
    // 留まった場所より右のジャンプの数だけ+1される
    ll now = 0;
    ll s = 0;
    while(1){
        s += now;
        if(s>=X){
            cout << now << endl;
            return 0;
        }
        now++;
    }
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

namespace Problem_C
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            var inputs = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int n = inputs[0], k = inputs[1];
            var nums = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            var dict = new Dictionary<int, int>();

            foreach (var num in nums)
            {
                if (dict.ContainsKey(num)) dict[num] += 1;
                else dict.Add(num, 1);
            }

            if (dict.Keys.Count > k)
            {
                var delCount = 0;
                var sorted = dict.OrderBy(num => num.Value).ToArray();
                for (var i = 0; i < dict.Keys.Count - k; i++)
                {
                    delCount += sorted[i].Value;
                }
                Console.WriteLine($"{delCount}");
            }
            else Console.WriteLine("0");
        }
    }
}


Measured memory_bytes: 43976
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
#define int long long
int m;
int a[10];
int b[10];
int memo[1001][10];
int dp(int v,int now)
{
	if(v==0)return 1;
	if(now==m||v<0)return 0;
	if(memo[v][now]!=-1)return memo[v][now];
	int ans=0;
	for(int i=0;i<=b[now];i++)
	{
		ans+=dp(v-i*a[now],now+1);
	}
	return memo[v][now]=ans;
}
signed main()
{
	while(cin>>m&&m)
	{
		for(int i=0;i<1001;i++)for(int j=0;j<10;j++)memo[i][j]=-1;
		for(int i=0;i<m;i++)
		{
			cin>>a[i]>>b[i];
		}
		int g;cin>>g;
		for(int i=0;i<g;i++)
		{
			int n;
			cin>>n;
			cout<<dp(n,0)<<endl;
		}
	}
}

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> A(M);
    for(auto &e : A) cin >> e;
    int sum = accumulate(A.begin(), A.end(), 0);
    int ans = N - sum;
    if(ans < 0) ans = -1;
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++){
    cin >> A[i];
  }
  vector<int> B = A;
  sort(B.begin(), B.end());
  map<int, int> mp;
  for (int i = 0; i < N; i++){
    mp[B[i]] = i;
  }
  for (int i = 0; i < N; i++){
    A[i] = mp[A[i]];
  }
  int ans = 0;
  for (int i = 0; i < N; i += 2){
    if (A[i] % 2 == 1){
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 8788
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl

int main(){
	FAST_IO;
    int n; 
    cin >> n; 
    int a[n], b[n], c[n]; 
    for(int i=0; i < n; i++){
        cin >> a[i] >> b[i] >> c[i]; 
    }
    int dp[3][n]; 
    dp[0][0] = a[0];
    dp[1][0] = b[0];
    dp[2][0] = c[0];
    for(int i=1; i < n; i++){
        dp[0][i] = a[i] + max(dp[1][i-1], dp[2][i-1]);
        dp[1][i] = b[i] + max(dp[0][i-1], dp[2][i-1]);
        dp[2][i] = c[i] + max(dp[0][i-1] , dp[1][i-1]); 
    }
    int ans = max(dp[0][n-1], max(dp[1][n-1] , dp[2][n-1]));
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define pb push_back
#define cmin(a,b) (a>b?a=b:a)
#define cmax(a,b) (a<b?a=b:a)
#define lop(i,s,t) for(int i=s;i<(t);++i)
#define rep(i,s,t) for(int i=s;i<=(t);++i)
#define dec(i,s,t) for(int i=s;i>=(t);--i)
#define fore(i,v) for(int i=g[v],d=es[i].d;i;i=es[i].nxt,d=es[i].d)
#define use(x) using std::x
use(swap); 
use(cin);
use(cout);
use(endl);

#define Pr(f,...) printf(f,##__VA_ARGS__),fflush(stdout)

typedef double db;
typedef long long ll;

const int N=1e6+60,G=3,P=998244353;

int mul(int a,int b){ return 1ll*a*b%P; }
int add(int a,int b){ a+=b; return a>=P?a-P:a; }
int sub(int a,int b){ a-=b; return a<0?a+P:a; }
int pwr(int a,int k){
	int res=1;
	for(;k;k>>=1,a=mul(a,a))
		if(k&1)res=mul(res,a);
	return res;
}
int inverse(int x){ return pwr(x,P-2); }

int ans,n,m,fac[N],inv[N],inv2;

int C(int n,int m){
	if(m<0||m>n)return 0;
	return mul(fac[n],mul(inv[m],inv[n-m])); 
}

int main(int argc,char *argv[]){
#ifdef CURIOUSCAT
	freopen("dat.in","r",stdin);
	freopen("my.out","w",stdout);
#endif
	int n,m;
	cin>>n>>m;
	if(n>m)swap(n,m);
	fac[0]=1; lop(i,1,N)fac[i]=mul(fac[i-1],i);
	inv[1]=1; lop(i,2,N)inv[i]=mul(P-P/i,inv[P%i]);
	inv2=inv[2];
	inv[0]=1; lop(i,1,N)inv[i]=mul(inv[i-1],inv[i]);

	rep(i,1,n){
		ans=add(ans,mul(mul(C(i+i,i),C(n-i+m-i,n-i)),inv2));
	}
	ans=mul(ans,inverse(C(n+m,n)));
	ans=add(ans,m);

	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 8192
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie();cout.tie();
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll inf = 9223372036854775807;
const ll mininf = -9223372036854775807;
const ll nax = 0;
int n, m;

int main(){
	IOS
	cin >> n >> m;
	vector<int>arr(n+5);
	for(int i=1;i<=n;i++){
		cin >> arr[i];
	}
	bool vis[n+5];
	memset(vis, 1, sizeof vis);
	while(m--){
		int a, b;
		cin >> a >> b;
		if(arr[b]<=arr[a]){
			vis[b]=0;
		}
		if(arr[a]<=arr[b]){
			vis[a]=0;
		}
	}
	int total=0;
	for(int i=1;i<=n;i++){
		if(vis[i]){
			total++;
		}
	}
	cout << total << '\n';
}

Measured memory_bytes: 3768
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <stack>
#include <set>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()

const int N = 1234567;

ll mpow(ll a, ll b){
	if(b==0) return 1;
	else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
	else return mpow(a,b-1) * a % MOD;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b, a%b);
}
vector<ll> kaijo_memo;
ll kaijo(ll n){
	if(kaijo_memo.size() > n) return kaijo_memo[n];
	if(kaijo_memo.size() == 0) kaijo_memo.push_back(1);
	while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD);
	return kaijo_memo[n];
}
ll nCr(ll n, ll r){
	if(n < r || r < 0) return 0;
	ll ret = 1;
	ret *= kaijo(n); ret %= MOD;
	ret *= mpow(kaijo(r), MOD-2); ret %= MOD;
	ret *= mpow(kaijo(n-r), MOD-2); ret %= MOD;
	return ret;
}

int main(void){
	int x1,x2,y1,y2;
	cin>>x1>>y1>>x2>>y2;
	int x3,y3,x4,y4;
	x3 = x2 - (y2-y1);
	y3 = y2 + (x2-x1);
	x4 = x3 - (y3-y2);
	y4 = y3 + (x3-x2);
	cout<<x3<<" "<<y3<<" "<<x4<<" "<<y4<<endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順
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; }

vector<vector<int>> DP;
#define INF 1<<30

int main() {
    int H,W; cin >> H >> W;
    DP.assign(H, vector<int>(W, INF));
    vector<string> G(H);
    rep(i,H) cin >> G.at(i);
    DP[0][0] = (G[0][0] == '#') ? 1 : 0;
    int dx[] = { 1, 0,-1, 0};
    int dy[] = { 0, 1, 0,-1};
    rep(i,H) {
        rep(j,W) {
            char c = G[i][j];
            rep(k,4) {
                int z = DP[i][j]; // z must be refreshed every k loop
                int nx = j + dx[k];
                int ny = i + dy[k];
                if (nx < 0 || nx >= W) continue;
                if (ny < 0 || ny >= H) continue;
                char d = G[ny][nx];
                if (c == '.' && d == '#') z++; // z broken here
                chmin(DP[ny][nx], z);
            }
        }
    }
    cout << DP[H-1][W-1] << endl;
}


Measured memory_bytes: 3660
fn main() {
  let n = read_num();
  let h = read_nums();
  let mut r = 1;
  let mut max_h = h[0];
  for i in 1..n as usize {
    if h[i] >= max_h {
      r += 1;
      max_h = h[i];
    }
  }
  println!("{}", r);
}

fn read_line() -> String {
  let mut buf = String::new();
  std::io::stdin().read_line(&mut buf).ok();
  buf
}

fn read_num() -> i32 {
  read_line().trim().parse().unwrap()
}

fn read_nums() -> Vec<i32> {
  read_line().split_whitespace().map(|x| x.parse().unwrap()).collect()
}

Measured memory_bytes: 4352
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#include<numeric>

using namespace std;

int main(){
    string a, b;
    cin >> a >> b;
    vector<string> vec;
    vec.push_back(a);
    vec.push_back(b);

    sort(vec.begin(),vec.end());


    for(int i = 0; i < stoi(vec[1]); i++){
        cout << vec[0];
    }

}

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

int main() {
   int N, D;
   cin >> N >> D;
   int v[D][N];
   int count=0;

   for(int i=0; i<N; i++) {
      for(int j=0; j<D; j++) {
         cin >> v[j][i];
      }
   }

   for(int i=0; i<N-1; i++) {
      for(int j=i+1; j<N; j++) {
         int sum = 0;
         for(int k=0; k<D; k++) {
            sum += pow((abs(v[k][i]-v[k][j])), 2);
         }
         int r = (int)(sqrt(sum));
         if(r * r == sum) {
            count++;
         }
      }
   }
   cout << count << endl;
}

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

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

using pii = pair<int,int>;

vector<pii> po[25252];
int cnt[525][525];
const int C = 205;

bool dvdv(pii p, pii q){
	int m,n,x,y;
	tie(m,n) = p;
	tie(x,y) = q;
	// printf("(%d,%d), (%d,%d) -> %d vs %d\n", m,n,x,y,__gcd(m*x+n*y,m*y-n*x),x*x+y*y);
	if(abs(__gcd(m*x+n*y, m*y-n*x)) % (x*x+y*y) == 0){
		return true;
	}else{
		return false;
	}
}

int main(){
	// maeshori
	vector<pii> v;
	FOR(m,-200,200)FOR(n,-200,200)if(m*m+n*n != 0 && m*m+n*n < 20000){
		v.push_back(pii(m,n));
		po[m*m+n*n].push_back(pii(m,n));
	}
	FOR(i,1,20000){
		int it = i;
		while(it < 20000){
			for(pii p : po[it])for(pii q : po[i]){
				int m,n;
		    tie(m,n) = p;
				if(dvdv(p,q))cnt[m+C][n+C]++;
			}
			it += i;
		}
	}
	int t;
  scanf("%d", &t);
	while(t--){
		int m,n;
		scanf("%d%d",&m,&n);
		puts(cnt[m+C][n+C]==8 ? "P" : "C");
	}
	return 0;
}




Measured memory_bytes: 5088
#include <iostream>

using namespace std;

int main()
{
   int A,B;
   cin>>A>>B ;
if (A==B) cout <<"Draw";
 if(A>B || A==1 ){
     if(B!=1) cout<<"Alice";}
 if(B>A || B==1){
     if(A!=1) cout<<"Bob";
 }
  
    return 0;
}

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

using namespace std;
#define ll long long int

ll dp[100005],ara[100005];

int main()
{
    ll n,k,i,j;
    cin>>n>>k;
    dp[0]=0;
    for(i=1; i<=n; i++)
    {
        cin>>ara[i];
        dp[ara[i]]=1;
    }
    for(i=1; i<=k; i++)
    {
        if(dp[i]==1) continue;
        for(j=1; j<=n; j++)
        {
            if(i<ara[j]) continue;
            if(!dp[i-ara[j]])
            {
                dp[i]=1;
                break;
            }
        }
    }
    if(dp[k]==1) cout<<"First"<<endl;
    else cout<<"Second"<<endl;
    return 0;



}




Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
    static Scanner scan = new Scanner(System.in);

    public static void main(String[] args) {
        int N, M ,P;
        while((N=scan.nextInt())!=0 | (M=scan.nextInt())!=0 | (P=scan.nextInt())!=0){
            int member = 0;
            int[] voteNum = new int[N+1];
            for(int i=1; i<=N; i++){
                voteNum[i] = scan.nextInt();
                member += voteNum[i];
        }

            if(voteNum[M] == 0){
                System.out.println(0);
                continue;
            }

            int pool = member*(100-P);

            System.out.println(pool/(voteNum[M]));
        }
    }
}

Measured memory_bytes: 27736
//package Qe
import java.util.*
import java.math.*
import java.lang.Math.*

private val readString: ()->String = {readLine()!!}
private val readInt: ()->Int = {readLine()!!.toInt()}
private val readLong: ()->Long = {readLine()!!.toLong()}
private val readIntArray: ()->IntArray = {readLine()!!.split(' ').map{it.toInt()}.toIntArray()}
private val readLongArray: ()->LongArray = {readLine()!!.split(' ').map{it.toLong()}.toLongArray()}
private val errPrintln: (String)->Unit = {msg -> System.err.println(msg)}
private val MOD = 1e9.toLong()+7
private val INF = Int.MAX_VALUE/2
private val LINF = Long.MAX_VALUE/2


fun solveE(W: IntArray, V: IntArray, WLim: Int): Int {
    val VSUM = V.sum()
    val N = W.size
    val dp = Array(N+1){LongArray(VSUM+4){0} }
    // dp[i][j] := [0,i) の品物から j 以上の価値を取れる最小重さ

    for (i in 0..N) {
        dp[i][0] = 0
    }
    for (j in 1 .. VSUM) {
        dp[0][j] = LINF
    }

    for (i in 0 until N) {
        for (j in 0 .. VSUM) {
            dp[i + 1][j] = dp[i][j]
            if (j >= V[i]) {
                dp[i + 1][j] = min(dp[i][j], dp[i][j - V[i]] + W[i])
            }
        }
    }

    var res = 0
    for (j in 0 .. VSUM) {
        if (dp[N][j] <= WLim.toLong()) {
            res = max(res, j)
        }
    }

    return res
}


fun main(args: Array<String>) {
    val (N, M) = readIntArray()
    val W = IntArray(N); val V = IntArray(N)
    for (i in 0 until N) {
        val (w, v) = readIntArray()
        W[i] = w; V[i] = v
    }

    val ans = solveE(W, V, M)

    println(ans)
}


Measured memory_bytes: 154700
while True:
    n, m = map(int, input().split())
    if n == m == 0:
        break
    students = [0 for _ in range(n)]
    for _ in range(m):
        scores = list(map(int, input().split()))
        for i in range(n):
            students[i] += scores[i]
    print(max(students))


Measured memory_bytes: 5648
N,Y = map(int, input().split())

res10000 = -1
res5000 = -1
res1000 = -1
n=0
s=0

for i in range(N+1):
  for j in range(N-i+1):
    n = N - i - j
    s = 10000*i+5000*j+1000*n
    if s == Y:
      res10000 = i
      res5000 = j
      res1000 = n
      break
print(res10000,res5000,res1000)

Measured memory_bytes: 40684
#include<stdio.h>
#include<string.h>

int main()
{
char s[28];
int i,j,c=0;

gets(s);

for(i=0;i<strlen(s);i++){
    for(j=i+1;j<strlen(s);j++){
        if(s[i]==s[j])
            c++;
        }
    }
if(c>0)
    printf("no");
else
    printf("yes");

return 0;
}


Measured memory_bytes: 1604
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define cout (cout<<fixed<<setprecision(10))

double E(int i){//i面サイコロの期待値
  return (1+i)/2.0;
}

int main(){
  int N, K;cin>>N>>K;

  double sum = 0;
  queue<double> sumq;
  int buf;
  for(int i=0; i<K; i++){
    cin>>buf;
    sumq.push(E(buf));
    sum += E(buf);
  }
  double ans = sum;

  double Ef;
  for(int i=K; i<N; i++){
    cin>>buf;
    Ef = sumq.front();sumq.pop();
    sum += (E(buf) - Ef);
    sumq.push(E(buf));
    ans = max(ans, sum);
  }

  cout<<ans<<endl;
  /*
  WAの原因：coutはデフォだと6桁までしか表示しない
  */
  //printf("%lf\n", ans);
}

Measured memory_bytes: 1920
#include<bits/stdc++.h>
//#define ll long long int32_t 
#define int long long int
#define getFaster ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define rep(i,init,n) for(int i=init;i<n;i++)
#define rev(i,n,init) for(int i=n;i>=init;i--)
#define MAXN 200005
#define MOD2 998244353
#define MOD1 1e9+7
#define f first
#define s second
#define endl '\n'
#define pii pair<int,int>
#define piii pair<pii,int>
#define precise(i) cout<<fixed<<setprecision(i)
using namespace std;
const double PI = atan(1.0)*4;
const int64_t INF=1000000000000000003;
const int32_t LOG=21;
const int MOD=MOD1;
int dp[100005][3];
int a[100005][3];
int32_t main()
{ 
      getFaster;
      int tests=1;
      //cin>>tests;
      rep(ii,0,tests)
      {
           int n;
           cin>>n;
           rep(i,0,n)cin>>a[i][0]>>a[i][1]>>a[i][2];
           dp[0][0]=a[0][0],dp[0][1]=a[0][1],dp[0][2]=a[0][2];
           rep(i,1,n)
           {
           	   rep(j,0,3)
           	   {
           	   	    rep(k,0,3)
           	   	    {
           	   	    	if(k!=j)
           	   	    	dp[i][j]=max(dp[i][j],a[i][j]+dp[i-1][k]);	
           	   	    }
           	   }
           }
           int ans=max({dp[n-1][0],dp[n-1][1],dp[n-1][2]});
           cout<<ans<<endl;           
      }
      return 0;     
}


Measured memory_bytes: 4992
"""Dodecagon Program
"""
import sys

def calc_area(num):
    """Calcurate area Method
    """
    if isinstance(num, float):
        return
    if (num < 1) or (num > 100):
        return
    return 3 * num * num

if __name__ == "__main__":
    try:
        num = int(input())
    except ValueError:
        sys.exit(1)
    print(calc_area(num))
    sys.exit(0)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
	ll a, b, x;
	cin >> a >> b >> x;
	if (a != 0) {
		cout << (b / x) - ((a - 1) / x) << endl;
	}
	else {
		cout << (b / x) - ((a) / x)+1 << endl;
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
using P = pair<int,int>;

int main() {
    int a,b,ans;
    cin>>a>>b;
    if (a >= 13) ans=b;
    else if(a <= 5) ans=0;
    else ans=b/2;
    cout<<ans<<endl;
}

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

const int64_t MOD = 1000000007;
typedef long long ll;
typedef unsigned long long ull;

#define FOR(i, start, end) for(uint64_t i=start; i<end; i++)
#define REP(i, n) FOR(i, 0, n)

// 最大公約数gcd
// 最小公倍数lcm=m*n/gcd
uint64_t gcd(uint64_t m, uint64_t n) {
  uint64_t temp;
  while (m % n != 0){
    temp = n;
    n = m % n;
    m = temp;
  }
  return n;
}

uint64_t lcm(uint64_t m, uint64_t n) {
  return (m*n)/gcd(m,n);
}

// vector<vector<uint64_t> > v(n+1, vector<uint64_t>(n+1, 0))
// v[n][k]に組み合わせ数が入る。
void comb(vector<vector <uint64_t> > &v){
  for(uint64_t i = 0;i <v.size(); i++){
    v[i][0]=1;
    v[i][i]=1;
  }
  for(uint64_t k = 1;k <v.size();k++){
    for(uint64_t j = 1;j<k;j++){
      v[k][j]=(v[k-1][j-1]+v[k-1][j]);
    }
  }
}

// 掛け算オーバーフロー判定
bool is_product_overflow(uint64_t a, uint64_t b) {

	uint64_t prod = a * b;
	
	return (prod / b != a);
}

//素因数分解
void primeFactorization(uint64_t a, list<uint64_t> &factors){ //素因数分解を出力するプログラム
  long i,sq;
  if(a%2==0){ //偶数の場合
    factors.push_back(2);
    primeFactorization(a/2,factors); //2で割った値で再帰
    return;
  }
  sq = sqrt(a);
  for(i=3;i<=sq;i+=2){ //3以上√a以下の奇数の場合
	if(a%i==0){
	  factors.push_back(i);
      primeFactorization(a/i,factors); //割れた値で再帰
      return;
	}
  }
  //偶数でも3以上√a以下の奇数の場合でも割り切れない場合
  if(a!=1){ //aが1でないなら、a自身は素数
    factors.push_back(a);
  }
}

// フェルマーの小定理
// mod. m での a の逆元 a^{-1} を計算する
// (a/b)%m = a*movinv(b,m)%m  
int64_t modinv(int64_t a, int64_t m) {
    int64_t b = m, u = 1, v = 0;
    while (b) {
        int64_t t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

// 円周率
// M_PI

// #include <iomanip> // setprecisionを使用するのに必要
// cout << std::fixed << std::setprecision(15) << y << endl;

// 昇順
// priority_queue<int, vector<int>, greater<int> > queue;

signed main() {
  ll n, m;
  cin >> n >> m;
  
  vector< pair<ll,ll> > store(n);
  ll a,b;
  for(int i=0;i<n;i++){
    cin >> a >> b;
    store[i] = make_pair(a,b);
  }
  sort(store.begin(), store.end());
  
  ll purchasedCount = 0;
  ll totalCost = 0;
  ll storeIdx = 0;
  while(purchasedCount<m){
    if( (m-purchasedCount)>store[storeIdx].second){
      totalCost += store[storeIdx].first*store[storeIdx].second;
      purchasedCount += store[storeIdx].second;
    }
    else{
      totalCost += store[storeIdx].first*(m-purchasedCount);
      purchasedCount += m-purchasedCount;
    }
    //cout << totalCost << ":" << purchasedCount << endl;
    storeIdx++;
  }
  cout << totalCost << endl;
  return 0;
}



Measured memory_bytes: 4664
#include <stdio.h>
#define N 44
int main()
{
  int count,answer,F[N],i;
  while(1)
    {
      scanf("%d",&count);
      if(count>=0 && count<=N)
	break;
    }
  F[0]=1;
  F[1]=1;
  for(i=2;i<=count;i++)
    F[i]=F[i-2]+F[i-1];
  printf("%d\n",F[count]);
  return 0;
}



Measured memory_bytes: 2108
#include<stdio.h>

int main(){
        char right[]="yuioplkjhnm";
        char c[35];
        int cou;
        int i,j,l;
        int left=-1;
        while(scanf("%s",c),*c!='#'){
                cou = -1;
                i=-1;
                left = -1;
                while(c[++i] != '\n' && c[i] != '\0'){
                        l=-1;
                        while(right[++l] != '\0'){
                                if(c[i] == right[l] )break;
                        }
                        if(l==11){
                                if(left != 1) cou++;
                                left = 1;
                        }else{
                                if(left != 0) cou++;
                                left = 0;
                        }
                }
                printf("%d\n",cou);
        }
        return 0;
}

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

int main() {
  int a,b;
  cin >> a >> b;
  int s = 0;
  
  if(a-b >0){
    s += a;
    a--;
    if(a - b >0) {
      s += a;
    }
    else {
      s += b;
    }
  }
  else {
    s += b;
    b--;
    if(a - b >0) {
      s += a;
    }
    else {
      s += b;
    }
  }
  
  cout << s << endl;
}
    
      

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <cstdarg>
#include <sys/time.h>
#include <fstream>
//#include "cout.h"

using namespace std;

#define SZ(x) ((int)x.size())
#define MSET(x,a) memset(x, a, (int)sizeof(x))
#define PB push_back
#define VI vector < int >
#define PII pair < int, int >
#define LL long long
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(), (v).end()
#define FIT(it,v) for (__typeof((v).begin()) it = (v).begin(); it != (v).end(); it++)
#define OUT(A) cout << #A << " = "<< (A) << endl
#define OUT2(A, B) cout << "(" << #A << ", " << #B << ") = (" << (A) << ", "<< (B) << ")" << endl
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }

#define present(c, e) ((c).find((e)) != (c).end())
#define cpresent(c, e) (find(ALL(c), (e)) != (c).end())


int cnt[101];
int n;

void init() {

}

void input() {

}

int num(int a) {
  int res = 0;
  REP(i, 101) if (cnt[i] >= a) res++;
  return res;
}

void solve() {
  cin >> n;
  REP(i, 101) cnt[i] = 0;
  for(int i = 2; i <= n; i++) {
    int x = i;
    for(int j = 2; ; j++) {
      while (x%j == 0) {
        cnt[j]++;
        x /= j;
      }
      if (x == 1) break;
    }
  }
  REP(i, 101) cnt[i]++;

  int res = 0;
  res += num(75);
  res += num(25) * (num(3)-1);
  res += num(15) * (num(5)-1);
  res += num(5) * (num(5)-1) / 2 * (num(3)-2);

  cout << res << endl;

}

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


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

using namespace std;

int f(int x) {
  int res = 0;
  while (x > 0) {
    res += x % 10;
    x /= 10;
  }
  return res;
}

int main() {
  int N;
  cin >> N;
  int fx = f(N);
  cout << (N % fx == 0 ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main()
{
	int N;
	cin >> N;
	vector<int> v(N);
	REP(i, N) cin >> v[i];

	sort(ALL(v));
	v.erase(unique(ALL(v)), v.end());
	cout << v.size() << endl;
}

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

long long gcd(long long a,long long b){
    return b != 0 ? gcd(b, a % b) : a;
}
long long lcm(long long a,long long b){
    return a*b/gcd(a,b);
}
long long nlcm(long long *f,int n){
    return n==0? f[0] : lcm(f[n-1],nlcm(f,n-1));
}
int main(){
    long long n;
    cin >> n;
    long long f[n];
    for(long long i=0;i<n;i++) cin >> f[i];
    cout << nlcm(f,n) << endl;
    return 0;
}



Measured memory_bytes: 3088
import math

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

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
a, b = map(int, input().split())
c = math.gcd(a, b)
d = factorization(c)
if a == 1 or b == 1:
    print(1)
else:
    print(len(d)+1)

Measured memory_bytes: 63684
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

s = input()
n = len(s)
for i in range(n):
    tmp = s[:-1-i]
    l = len(tmp)
    if l%2:
        continue
    if tmp[:l//2] == tmp[l//2:]:
        print(l)
        break

Measured memory_bytes: 38384
import numpy as np
para = str(input()).split()
hour = int(para[2])
minute = int(para[3])
#print(hour, ' ', minute)
angleH = (30 * hour + 30 * (minute/60))
angleM = (minute/60) * 360
angle = abs(angleM-angleH)
rad = angle * np.pi / 180
cosR = np.cos(rad)
l1 = int(para[0])
l2 = int(para[1])
line = np.sqrt(l1 * l1 + l2 * l2 - 2*l1*l2*cosR)
print(line)



Measured memory_bytes: 27168
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
priority_queue<long long> q;
map<long long,int> ans;
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=0;i<n;i++)
        {

            long long t;scanf("%lld",&t);
            q.push(t);
        }
        long long a=0,b=0,t;
        t=q.top();q.pop();
        while(q.size()>0)
        {
            long long x=q.top();q.pop();
            if(x==t)
            {
                if(!a)a=t;
                else b=t;
                t=0;
            }
            else t=x;
            if(a&&b)break;
        }
        printf("%lld\n",a*b);
    }
}


Measured memory_bytes: 1400
N = int(input())
AB = []
for i in range(N):
  AB.append(list(map(int, input().split())))

AB.sort()
if N % 2 == 0:
  l1 = AB[N//2][0] 
  l2 = AB[N//2 - 1][0]
else:
  l = AB[N//2][0]
AB.sort(key = lambda x: x[1])
if N % 2 == 0:
  r1 = AB[N//2][1] 
  r2 = AB[N//2 - 1][1]
else:
  r = AB[N//2][1]
  
if N % 2 == 0:
  ans = (r1 + r2) - (l1 + l2)
  ans += 1
  print(ans)
else:
  print(r - l + 1)


Measured memory_bytes: 112604
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const LL MAX=1e15;
const LL N=200005;
LL n,d;
LL a[N];
struct qt
{
	LL c,id;
	qt () {};
	qt (LL _c,LL _id)	{c=_c;id=_id;}
};
struct qq
{
	LL l,r;
	qt c[2];
	LL s1,s2;
}tr[N*2];LL num;
qt Merge (qt x,qt y)	{return x.c<y.c?x:y;}
void bt (LL l,LL r)
{
	LL now=++num;
	tr[now].l=l;tr[now].r=r;
	if (l==r)	
	{
		tr[now].c[0].c=a[l]-l*d;
		tr[now].c[1].c=a[l]+l*d;
		tr[now].c[0].id=l;
		tr[now].c[1].id=l;
		return ;
	}
	LL mid=(l+r)>>1;
	tr[now].s1=num+1;bt(l,mid);
	tr[now].s2=num+1;bt(mid+1,r);
	tr[now].c[0]=Merge(tr[tr[now].s1].c[0],tr[tr[now].s2].c[0]);
	tr[now].c[1]=Merge(tr[tr[now].s1].c[1],tr[tr[now].s2].c[1]);
}
vector<LL> vec[N];
qt t[N];//这个连通块连谁最好 
LL tot=0;
LL fa[N];
LL find_fa (LL x)	{return fa[x]==x?x:fa[x]=find_fa(fa[x]);}
qt get (LL now,LL l,LL r,LL o)
{
	if (l>r)	return qt(MAX,MAX);
	if (tr[now].l==l&&tr[now].r==r)	return tr[now].c[o];
	LL s1=tr[now].s1,s2=tr[now].s2;
	LL mid=(tr[now].l+tr[now].r)>>1;
	if (r<=mid) return get(s1,l,r,o);
	else if (l>mid) return get(s2,l,r,o);
	else return Merge(get(s1,l,mid,o),get(s2,mid+1,r,o));
}
int main()
{
	scanf("%lld%lld",&n,&d);
	for (LL u=1;u<=n;u++) scanf("%lld",&a[u]);
	bt(1,n);
	tot=n;
	for (LL u=1;u<=n;u++) 	
	{
		vec[u].push_back(u);
		qt x=get(1,1,u-1,0),y=get(1,u+1,n,1);
		x.c=x.c+a[u]+u*d;
		y.c=y.c+a[u]-u*d;
		t[u]=Merge(x,y);
		fa[u]=u;
		//printf("YES:%lld %lld %lld %lld\n",u,t[u].id,x.id,y.id);
	}
	LL ans=0;
	while (tot!=1)
	{	
		for (LL i=1;i<=n;i++)
		{
			if (find_fa(i)!=i) continue;
			LL x=find_fa(t[i].id);
			if (x==i) continue;//已经连过了 
			ans=ans+t[i].c;
			fa[i]=x;
			//printf("link%lld %lld\n",i,x);
			LL siz=vec[i].size();
			for (LL j=0;j<siz;j++)	vec[x].push_back(vec[i][j]);
		}
		tot=0;
		for (LL i=1;i<=n;i++)
		{
			if (find_fa(i)!=i) continue;
			tot++;
			LL siz=vec[i].size();
			sort(vec[i].begin(),vec[i].end());
			LL lst=0,j=0;
			qt now=qt(MAX,MAX),x,y;
			t[i]=qt(MAX,MAX);
			for (LL u=0;u<siz;u++)
			{
				if (u==siz-1||vec[i][u+1]!=vec[i][u]+1)//需要合并 
				{
					x=get(1,lst+1,vec[i][j]-1,0);
					y=get(1,vec[i][j],vec[i][u],1);
					//printf("YES:%lld %lld %lld\n",lst+1,vec[i][j]-1LL,x.id);
					now=Merge(now,x);
					qt lalal;
					lalal.id=now.id;
					lalal.c=y.c+now.c;
					t[i]=Merge(t[i],lalal);
					j=u+1;lst=vec[i][u];
				}
			}
			now=qt(MAX,MAX);
			lst=n+1;j=siz-1;
			for (LL u=siz-1;u>=0;u--)
			{
				if (u==0||vec[i][u-1]!=vec[i][u]-1)//需要合并 
				{
					x=get(1,vec[i][j]+1,lst-1,1);
					y=get(1,vec[i][u],vec[i][j],0);
					now=Merge(now,x);
					qt lalal;
					lalal.id=now.id;
					lalal.c=y.c+now.c;
					t[i]=Merge(t[i],lalal);
					j=u-1;lst=vec[i][u];
				}
			}
			//printf("%lld %lld\n",i,t[i].id);
		}
		//system("pause");
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 68396
a, b = io.read("*n", "*n")
c, k = io.read("*n", "*n")
local mmi, mma = math.min, math.max
r = 0
v = mmi(a, k)
r = r + v
k = k - v

v = mmi(b, k)
k = k - v
v = mmi(c, k)
r = r - v
print(r)


Measured memory_bytes: 2728
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <fstream>
#include <unistd.h>
#include <string>
#include <numeric>
#include <queue>
#include <deque>
#include <sstream>
#include <iomanip>
#include <set>
#include <stack>
#include <cassert>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vvb> vvvb;
typedef vector<vvvb> vvvvb;
typedef vector<string> vs;
typedef vector<vs> vvs;
typedef vector<vvs> vvvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> vp;
typedef vector<PL> vpl;
typedef vector<vector<P>> vvp;
typedef vector<vector<PL>> vvpl;
const int INF = 1001001001;
const ll LINF = 1e17;
const double pi = 3.1415926535897932;
const string endstr = "\n";
#define FOR(i, a, b) for(ll i = (a); i < b; i++)
#define RFOR(i, a, b) for(ll i = (a); i > b; i--)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define RREP(i, n) for(ll i = n-1; i > -1; i--)
#define FORMAP(it, m) for(auto it = m.begin(); it != m.end(); it++)
#define ff first
#define ss second
#define pb push_back
#define epb emplace_back

template <typename T>
T gcd(T a, T b) {
    return (a == 0) ? b : gcd(b%a, a);
}
template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

bool p_comp_fs(const PL p1, const PL p2){ return p1.first < p2.first;};
bool p_comp_fg(const PL p1, const PL p2){ return p1.first > p2.first;};
bool p_comp_ss(const PL p1, const PL p2){ return p1.second < p2.second;};
bool p_comp_sg(const PL p1, const PL p2){ return p1.second > p2.second;};
template <typename T>
vector<T> uniquen(vector<T> vec){
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}

vl e[100100];
ll N;
ll dp[100100][2];

const ll mod = 1e9+7;

void dfs(ll x, ll par = -1){
    dp[x][0] = 1; dp[x][1] = 1;
    for(ll to : e[x]){
        if(to == par) continue;
        dfs(to, x);
        dp[x][0] *= dp[to][0] + dp[to][1];
        dp[x][1] *= dp[to][0];
        dp[x][0] %= mod;
        dp[x][1] %= mod;
    }
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    REP(i, N-1){
        ll x, y; cin >> x >> y; x--; y--;
        e[x].pb(y); e[y].pb(x);
    }
    REP(i, 100100) REP(j, 2) dp[i][j] = 0;
    dfs(0);
    
    cout << (dp[0][0] + dp[0][1]) % mod << endstr;
    return 0;
}


Measured memory_bytes: 14208
#include <stdio.h>

int main(int argc, const char * argv[])
{

    int i, j;
    for (i = 1; i <= 9; i++) {
        for (j = 1; j <= 9; j++) {
            printf("%dx%d=%d\n", i, j, i * j);
        }
    }
    return 0;
}

Measured memory_bytes: 524
R=range
l=[[[0 for i in R(10)]for j in R(3)]for s in R(4)]
for i in R(int(input())):b,f,r,v=map(int,input().split());l[b-1][f-1][r-1]+=v
for i in R(4):
 for k in l[i]:print("",*k)
 if i!=3:print("#"*20)

Measured memory_bytes: 7720
import sys
input = sys.stdin.readline
A, B = [int(x) for x in input().split()]
import numpy as np
a = np.arange(A, B + 1)
a = np.array(a, np.object)
ans = 0
for i in a:
    i = str(i)
    if i[0] == i[4] and i[1] == i[3]:
        ans += 1
print(ans)

Measured memory_bytes: 16224
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int N;
	cin >> N;
	double x = N / 1.08;
	int a = (int) x;
	int b = ((int) x) + 1;
	if ((int) (a * 1.08) == N)
	{
		cout << a << endl;
	} else if ((int) (b * 1.08) == N)
	{
		cout << b << endl;
	} else {
		cout << ":(" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
const double PI = 3.14159265358979323846;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  int ans = min(a+b, min(b+c, a+c));
  cout << ans << endl;
}

Measured memory_bytes: 3672
#include<bits/stdc++.h>
#define LL long long
#define Max 100005
#define Mod 1e9+7
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
using namespace std;
char a[15],ch[15];
int main()
{
	scanf("%s",ch);
	int now=-1;
	for(int i=0;ch[i];i++)
	{
		if(ch[i]=='0')
		{
			a[now+1]='0';
			now++;
		}
		else if(ch[i]=='1')
		{
			a[now+1]='1';
			now++;
		}
		else if(now>=0)
			now--;
	}
	for(int i=0;i<=now;i++)
		printf("%c",a[i]);
    return 0;
}


Measured memory_bytes: 256
N = int(input())
H = [int(n) for n in input().split()]

def main():

    h = H
    max_h = max(h)

    ans = 0
    curr_h = 0

    while curr_h <= max_h:
        prev_h = 0
        for n in h:
            if n > curr_h and prev_h <= curr_h:            
                ans += 1
            prev_h = n
        curr_h += 1

    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
// D.

#include <iostream>
#include <algorithm>
#include <sstream>
#include <vector>

using namespace std;

typedef long long LL;

static const LL MOD = 1000000007;

struct modll {
	long long x;
	modll() { }
	modll(long long _x) : x(_x) { }
	operator int() const { return (int)x; }
	modll operator+(const modll &r) { return (x + r.x) % MOD; }
	modll operator+=(const modll &r) { return x = (x + r.x) % MOD; }
	modll operator-(const modll &r) { return (x + MOD - r.x) % MOD; }
	modll operator-=(const modll &r) { return x = (x + MOD - r.x) % MOD; }
	modll operator*(const modll &r) { return (x * r.x) % MOD; }
	modll operator*(int r) { return (x * r) % MOD; }
	modll operator*=(const modll &r) { return x = (x * r.x) % MOD; }
	static modll modinv(int a) { return modpow(a, MOD - 2); }
	static modll modpow(int a, int b) {
		modll x = a, r = 1;
		for (; b; b >>= 1, x *= x) if (b & 1) r *= x;
		return r;
	}
};

static modll fact[300003], inv[300003];

modll combination(LL n, LL r) {
	modll x = 0;
	if (n >= r) {
		x = fact[n];
		x *= inv[r];
		x *= inv[n - r];
	}
	return x;
}

int main(int argc, char *argv[]) {
	fact[0] = 1;
	inv[0] = 1;
	for (int i = 1; i <= 300002; ++i) {
		fact[i] = fact[i - 1] * i;
		inv[i] = modll::modinv(fact[i]);
	}

	int n, d;
	cin >> n;
	vector<int> pos(n + 1, -1);

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

	for (int i = 1; i <= n + 1; ++i) {
		modll ans = combination(n + 1, i);
		ans -= combination(n - d, i - 1);
		cout << ans << endl;
	}
	return 0;
}


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

using ll = long long;

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


	ll n;
	cin >> n;

	ll cur = n;
	ll ans = 0;
	for (int i = 2; i <= 1000005; ++i) {
		if (cur % i != 0) continue;
		int num = 0;
		while (cur % i == 0) {
			cur /= i;
			++num;
		}
		int cans = 0;
		while (cans * (cans + 1) / 2 <= num) {
			++cans;
		}
		--cans;
		ans += cans;
	}
	if (cur != 1) ans++;

	cout << ans << '\n';

	return 0;
}

Measured memory_bytes: 3652