akhauriyash/Code-Regression huggingface dataset:
void main() {
	auto N = ri;
	class Point { int x, y; bool done; this(int[] a) { x = a[0]; y = a[1]; done = false; }}
	Point[] red, blue;
	foreach(i; 0..N) red ~= new Point(readAs!(int[]));
	foreach(i; 0..N) blue ~= new Point(readAs!(int[]));
	blue.sort!"a.x < b.x";
	int count;
	foreach(b; blue) {
		Point r_ = new Point([int.min, int.min]);
		foreach(ref r; red) {
			if(b.x > r.x && b.y > r.y && !r.done && r_.y < r.y) r_ = r;
		}
		if(r_.x != int.min) {
			r_.done = true;
			count++;
		}
	}
	count.writeln;
}

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

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

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

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

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

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

T[] deepcopy(T)(T[] a) {
	static if(isArray!T) {
		T[] res;
		foreach(i; a) {
			res ~= deepcopy(i);
		}
		return res;
	} else {
		return a.dup;
	}
}

ulong[] generate_prime_list(T)(T N) if(isIntegral!T) {
	ulong[] prime_list = [2];
	bool not_prime = false;
	foreach(i; 3..N.to!ulong+1) {
		foreach(j; prime_list) {
			if(i % j == 0) {
				not_prime = true;
				break;
			}
		}
		if(!not_prime) prime_list ~= i;
		not_prime = false;
	}
	return prime_list;
}

class UnionFind(T) {
	T[] arr;
	this(ulong n) {
		arr.length = n+1;
		arr[] = -1;
	}
	T root(T x) {
		return arr[x] < 0 ? x : root(arr[x]);
	}
	bool same(T x, T y) {
		return root(x) == root(y);
	}
	bool unite(T x, T y) {
		x = root(x);
		y = root(y);
		if(x == y) return false;
		if(arr[x] > arr[y]) swap(x, y);
		arr[x] += arr[y];
		arr[y] = x;
		return true;
	}
	T size(T a) {
		return -arr[root(a)];
	}
}

Measured memory_bytes: 380
"use strict";

const main=(input)=>{
    const args= input.split('\n').map((n)=>parseInt(n,10));
    const coinA=args[0] ;
    const coinB=args[1] ;
    const coinC=args[2] ;
    const x = args[3];
    let count=0;

    for(let i=0;i<=coinA;i++){
        for(let e=0;e<=coinB;e++){
            for(let f=0;f<=coinC;f++)
            if(i*500+e*100+f*50===x){
                count++;
            }
        }
        }
        console.log(count);
    }

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

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

using namespace std;

#define DUMP(x) std::cout << (#x) << " = " << (x) << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define ALL(r) r.begin(), r.end()

using ll = std::int64_t;
using vint = std::vector<int>;
using pint = std::pair<int, int>;

constexpr std::int32_t INF = 1001001001;

void Main() {
    int n, m;
    cin >> n >> m;
    vector<pair<ll, ll>> ab(n);
    rep(i, n) {
        int a, b;
        cin >> a >> b;
        ab[i] = make_pair(a, b);
    }
    sort(ALL(ab));

    ll ans = 0;
    rep(i, n) {
        if (ab[i].second < m) {
            ans += ab[i].first * ab[i].second;
            m -= ab[i].second;
            continue;
        }
        else {
            ans += ab[i].first * m;
            break;
        }
    }

    cout << ans << endl;

}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


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

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
int n,a[N];
int sum[N],ans=1e9;
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1];
	for(int i=1;i<n;i++)ans=min(abs(a[n]-a[i]-a[i]),ans);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <climits>

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

  int N;
  cin >> N;
  ll A[N+1];
  ll cap[N+1]={1};
  rep(i,N+1) cin >> A[i];
  ll rest=1;
  ll node=0;

  rep(i,N+1){
    if(rest < A[i]) {
      cout << -1 << endl;
      return 0;
    }
    rest -= A[i];
    cap[i] = rest;
    rest *=2;
  }

  //can be construct! check the max!
  ll add=0;
  ll carry=0;

  for(int i=N; i>-1; i--){
    add = min(cap[i],carry);
    carry = add+A[i];
    node += carry;
    //cout << "i:" << i << ", carry:" << carry << ", node:" << node << endl;
  }

  cout << node << endl;


  return 0;
}

Measured memory_bytes: 5164
#include <bits/stdc++.h>
#include <tr1/unordered_map>
#define debug(x) (cout << "#x = " << (x) << endl)
#define lowbit(x) (x & -x)
#define Set(x, i) memset(x, i, sizeof x)
#define R register
#define For( i, j, k ) for(R int i = (j); i <= (k); ++i)
#define Rep( i, j, k ) for(R int i = (j); i >= (k); --i)
#define Cross( i, j, k ) for(R int i = (j); i; i = (k))
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll N = 100011;
const ll INF = 5e16;

namespace IO {

	#define dd ch = getchar()
	inline ll read() {
		ll x = 0; bool f = 0; char dd;
		for (; !isdigit (ch); dd) f ^= (ch == '-');
		for (; isdigit (ch); dd)  x = x * 10 + (ch ^ 48);
		return f? -x: x;
	}
	#undef dd

	inline void write ( ll x ) {
		if (x < 0) putchar ('-'), x = -x;
		if (x > 9) write (x / 10); putchar ( x % 10 | 48 );
	}

	inline void wrn ( ll x ) { write(x); putchar (' '); }

	inline void wln ( ll x ) { write(x); putchar ('\n'); }

	inline void wlnn ( ll x, ll y ) { wrn(x); wln (y); }

}

using namespace IO;

namespace Cesare {
	
	ll n, Ans;
	string s[N];
	
	tr1::unordered_map <ll, ll> mp[N], Vis;
	
	int main() {
		n = read();
		For ( i, 1, n ) cin >> s[i];
		For ( i, 1, n ) {
			ull Ha = 0, Base = 233;
			For ( j, 1, s[i].size() ) ++mp[i][s[i][j - 1]];
			For ( j, 'a', 'z' ) Ha = Ha * Base + mp[i][j];
			if (!Vis[Ha]) Vis[Ha] = 1; else Ans += Vis[Ha], ++Vis[Ha];
		} return wln(Ans), 0;
	}
	
}

int main()
{
	return Cesare::main();
}

/*

*/



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

int main() {
  int n;
  cin >> n;
  vector<int> c(n - 1), s(n - 1), f(n - 1);
  for(int i = 0; i < n - 1; i++)
    cin >> c.at(i) >> s.at(i) >> f.at(i);
  for(int i = 0; i < n - 1; i++) {
    int t = s.at(i);
    for(int j = i; j < n - 2; j++) {
      t += c.at(j);
      t = max(s.at(j + 1), (t + f.at(j + 1) - 1) / f.at(j + 1) * f.at(j + 1));
    }
    t += c.at(n - 2);
    cout << t << endl;
  }
  cout << 0 << endl;
}

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

using ll = long long;

void read();
template<typename First, typename... Rest> void read(First& first, Rest&... rest);
void write();
template<typename First, typename... Rest> void write(First first, Rest... rest);
template<typename T> void write_vec(vector<T>& v, char divider);

int main(){
    int R;
    read(R);
    cout << fixed << setprecision(2) << 2 * M_PI * R;
    return 0;
}

//配列以外の入力を受け取る
void read(){

}
template<typename First, typename... Rest>
void read(First& first, Rest&... rest){
    cin >> first;
    read(rest...);
}
//
//配列以外を出力する
void write(){

}
template<typename First, typename... Rest>
void write(First first, Rest... rest){
    cout << first << " ";
    write(rest...);
}
//
//配列を区切って出力する
template<typename T>
void write_vec(vector<T>& v, char divider){
    for(size_t i = 0; i < v.size(); i++){
        cout << v[i] << divider;
    }
}
//

Measured memory_bytes: 3788
#include<stdio.h>
int main(void)
{
	int n,i,j,minj,tmp;
	int count=0;
	scanf("%d",&n);
	
	int A[n];
	
	for(i=0;i<n;i++)
	{
		scanf("%d",&A[i]);
	}
	
	for(i=0;i<n;i++)
	{
	
		minj=i;
		
		for(j=i;j<n;j++)
		{
	
			
				
			if(A[j]<A[minj])
			{
				minj=j;
				
			}
			
		}
				tmp=A[i];
				A[i]=A[minj];
				A[minj]=tmp;
		if(i!=minj)
		{
				count++;
		}
	}
	
	for(i=0;i<n;i++)
	{
		printf("%d",A[i]);
		if(i!=n-1)
		{
		printf(" ");
		}
	}
	printf("\n");
	printf("%d\n",count);
}



Measured memory_bytes: 2092
n=gets.to_i
a=[],s=[]
n.times{|i|a[i],s[i]=gets.split.map &:to_i}
ans=0
kai=0
for i in 0...n
  if a[i]==s[i]
    ans+=1
  else
    ans=0
  end
  kai=1 if ans==3
end
puts kai==1? :Yes: :No


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

using namespace std;

const int MOD = 1e9 + 7;

int i,h,w,a,b;
long long fact[200005];

long long get_pow(int s, int lv){
	if(lv == 0)
	return 1LL;
	long long res = get_pow(s, lv / 2);
	if(lv & 1)
	return ((res * res) % MOD * s) % MOD;
	return (res * res) % MOD;
}

long long inv(int s){
	return get_pow(s, MOD - 2);
}

long long ncr(int n, int r){
	return ((fact[n] * inv(fact[r])) % MOD * inv(fact[n - r])) % MOD;
}

int main(){
	scanf("%d%d%d%d", &h, &w, &a, &b);	
	a = h - a + 1;
	fact[0] = 1;
	for(i = 1; i <= h + w; i++)
	fact[i] = (fact[i - 1] * i) % MOD;
	long long ans = ncr(h + w - 2, h - 1);
	long long s = 0;
	for(i = 1; i <= b; i++){
		//at (a, i)
		long long now = ncr(a + i - 2, a - 1);
		//printf("NCR %d %d %lld\n", a + i - 2, a - 1, now);
		now = (now - s + MOD) % MOD;
		s = (s + now) % MOD;
		int x = h - a + 1;
		int y = w - i + 1;
		now = (now * ncr(x + y - 2, x - 1)) % MOD;
		ans = (ans - now + MOD) % MOD;
	}
	printf("%lld\n", ans);
}


Measured memory_bytes: 1792
def resolve():
    '''
    code here
    '''
    S_dash = input()
    T = input()

    is_flag = False

    res = ''
    res_list = ['zzzzz']
    for i in range(len(S_dash) - len(T) +1):
        res = S_dash[:i]
        # print(i, res)
        if len(S_dash) - len(res) >= len(T):
            for j in range(len(T)):
                if S_dash[i+j] == T[j] or S_dash[i+j] == '?':
                    res += T[j]
                else:
                    # print('bk')
                    break
            else:
                is_flag = True
                res += S_dash[i+len(T):]
                res_list.append(res)


    # print(res_list)

    res2_list = []
    for res in res_list:
        res = res.replace('?','a')
        res2_list.append(res)

    res2_list.sort()
    res = res2_list[0]

    print(res) if is_flag else print('UNRESTORABLE')     

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 3188
def main8():
    buf = int(input(""));
    result = 0;
    for i in range(buf):
        n = i + 1;
        if n % 2 == 1:
            kari = 0;
            for j in range(n):
                m = j + 1;
                if n % m == 0:
                    kari = kari + 1;
            if kari == 8:
                result = result + 1;
    print(result);

if __name__ == '__main__':
    main8()


Measured memory_bytes: 2940
# 2019/09/23

from collections import Counter
n=int(input())
d=Counter(list(map(int,input().split())))
m=int(input())
t=Counter(list(map(int,input().split())))

for k,v in t.items():
    d[k]=d.get(k,0)-v
    if d[k]<0:
        print('NO')
        exit()
print('YES')

Measured memory_bytes: 55264
#include "bits/stdc++.h"
#define rep(i,b) for(ll i=0;i<b;i++)
#define ll long long
using namespace std;
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#define debug(x) cerr<<#x<<" "<<x<<'\n';
bool cmp(pair<ll,ll> a, pair<ll,ll> b) { return a.second > b.second; }

signed main() {
    int paa=0,ans=0;
    string s;
    cin>>s;
    rep(i,s.size()){
        if(s[i]=='g'){
            if(paa>0){
                ans++;
                paa--;
            }else{
                paa++;
            }
        }else{
            if(paa>0){
                paa--;
            }else{
                paa++;
                ans--;
            }
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define what_is(x) cerr << #x <<" is " << x << endl;
typedef long long ll;
const int MOD = 998244353;
const double PI = 3.141592653589793;
const int INF =  1e9 + 7;
const int nax = 200005;

ll power(ll a, ll b, ll mod = MOD) {
	ll ans = 1;
	while (b) {
		if (b & 1) {
			ans = (ans * a) % mod;
		}
		a = (a * a) % mod;
		b = b >> 1;
	}
	return ans;
}


vector<ll> f(nax, 1);
void init() {
	for (int i = 2; i < nax; i++) {
		f[i] = (i * f[i - 1]) % MOD;
	}
}

ll inv(ll x) {
	return power(x, MOD - 2);
}

ll nCr(ll n, ll r) {
	ll ans = f[n];
	ans = (ans * inv(f[r])) % MOD;
	ans = (ans * inv(f[n - r])) % MOD;
	return ans;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tc = 1;
	init();
	// cin >> tc;
	while (tc--) {
		ll n, m, k;
		cin >> n >> m >> k;
		ll ans = 0;
		for (ll p = n - k; p <= n; p++) {
			// ans += ((nCr(n - 1, p - 1) * m) % MOD * power(m - 1, p - 1)) % MOD;
			ll ans1 = power(m - 1, p - 1) % MOD;
			ans1 = (ans1 * m) % MOD;
			ans1 = (ans1 * nCr(n - 1, p - 1)) % MOD;
			ans = (ans + ans1) % MOD;
		}
		cout << ans;
	}
	return 0;
}




















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

int main(int argc, char const *argv[])
{
	int n;
	cin>>n;
	int a[n];
	for (int i = 0; i < n; ++i)
	{
		cin>>a[i];
	}
	long long ans=0LL;
	int i=0,j=1,now=a[0];
	for (int i = 0; i < n; ++i)
	{
		while ((now&a[j])==0&&j<n)
		{
			now|=a[j];
			++j;
		}
		ans+=(long long)j-i;
		if (i==j)
		{
			++j;
		}
		else
		{
			for (int k = 0; k < 25; ++k)
			{
				if ((a[i]&(1<<k))!=0)
				{
					now^=(1<<k);
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
// #include <cstdlib>
#define MAXN 100005
using namespace std;
int a[MAXN];
int main() {
    int n, m;
    int l, r, cnt = 0, mn = 100000, mx = -1;
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        cin >> l >> r;
        if(l > mx) mx = l;
        if(r < mn) mn = r;
    }
    if(mn >= mx)
        cout << mn-mx+1 << "\n";
    else
        cout << "0\n";
    return 0;
}

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

string lcs(string a, string b){
  vector<vector<int>> DP(a.size()+1, vector<int>(b.size()+1));
  for(size_t i=0; i<a.size(); i++) DP[i][0] = 0;
  for(size_t i=0; i<b.size(); i++) DP[0][i] = 0;
  for(size_t i=1; i<=a.size(); i++){
    for (size_t j = 1; j <= b.size(); j++) {
      if(a[i-1] == b[j-1])
        DP[i][j] = 1 + DP[i-1][j-1];
      else
        DP[i][j] = max(DP[i][j-1], DP[i-1][j]);
    }
  }
  string res(DP[a.size()][b.size()], '0');
  int index = res.size()-1, i=a.size(), j=b.size();
  while(index>=0){
    if(a[i-1]==b[j-1]){
      res[index--] = a[i-1];
      i--, j--;
    } else {
      if(DP[i-1][j]>DP[i][j-1])
        i--;
      else
        j--;
    }
  }
  return res;
}

int main(){
  string a, b;
  cin >> a >> b;
  cout << lcs(a, b) << endl;
}


Measured memory_bytes: 35584
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(long long i=0;i<(n);i++)
#define REP1(i,n) for(long long i=1;i<=(n);i++)

typedef long long ll;
#define MAXN 100000
ll n,m,l[MAXN],r[MAXN];

int main(){
	
    cin>>n>>m;
	REP(i,m) cin>>l[i]>>r[i];
	ll lres=l[0],rres=r[0];
	REP(i,m){
		if(i==0) continue;
		lres=max(lres,l[i]);
		rres=min(rres,r[i]);
	}
	if(lres<=rres)
		cout<<(rres-lres)+1<<endl;
	else
		cout<<0<<endl;
		
    return 0;

}


Measured memory_bytes: 1792
import itertools
n, k = map(int, input().split())
a = list(map(int, input().split()))
M = 10**9 + 7

dp = [[None] * (k + 1) for _ in range(n + 1)]
def dfs(i=0, at=k):
    if dp[i][at] is not None:
        return dp[i][at]

    if i == n:
        r = int(at == 0)
        dp[i][at] = r
        return r

    cnt = 0
    for v in range(a[i] + 1):
        if v > at:
            break
        cnt += dfs(i + 1, at - v)
    dp[i][at] = cnt
    return cnt
#
# print(dfs())
# for v in dp:
#     print(v)

def fm(array):
    return ["*" if v is None else v for v in array]

def mod(v):
    if v >= M:
        return v % M
    return v

# def addmod(a, b):
#     return mod(a + b)

# for at in range(k + 1):
for i in reversed(range(n + 1)):
    for at in range(k + 1):
        if i == n:
            dp[i][at] = int(at == 0)
            continue
        cnt = 0
        # print(*fm(dp[i]), end=" -> ")
        # for v in range(min(a[i], at) + 1):
        #     cnt += dp[i + 1][at - v]
        # dpcnt = cnt
        cnt = cs[at] - cs[at - min(a[i], at) - 1]
        dp[i][at] = mod(cnt)
        # print(*fm(dp[i]), "@", at - min(a[i], at), "~", at)
        # print(cnt, "@", at - min(a[i], at), "~", at, ":", *fm(dp[i + 1])[at - min(a[i], at):at + 1])
        # print(dpcnt, cnt)
    # cs = list(itertools.accumulate(dp[i], func=addmod)) + [0]
    cs = list(itertools.accumulate(dp[i])) + [0]
    cs = [mod(v) for v in cs]
    # print(*cs, "cs")
    # print(*dp[i], "dp")
    # print("-----")
print(dp[0][k] % M)

# for v in dp:
#     print(*fm(v))


Measured memory_bytes: 307208
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            StringBuilder sb = new StringBuilder();

            string input;

            while (!string.IsNullOrEmpty(input = Console.ReadLine()))
            {
                decimal[] temp = Array.ConvertAll(input.Split(' '), decimal.Parse);

                decimal ax = temp[0] - temp[2];
                decimal ay = temp[1] - temp[3];
                decimal bx = temp[4] - temp[6];
                decimal by = temp[5] - temp[7];

                bool isOrthogonal = ax * bx + ay * by == 0.0M;

                sb.AppendLine(isOrthogonal ? "YES" : "NO");
            }
            Console.Write(sb);
        }
    }
}

Measured memory_bytes: 9220
#include <bits/stdc++.h>
using namespace std;
int main(void){
  string S;
  cin >> S;
  const int N = S.size();
  bool tf = false;
  for(int i=0; i<N; i++){
    for(int j=i; j<N; j++){
      // keyofscience
      //   i     j
      // -> ke ence
      string t = S;
      string left = t.substr(0, i);
      string right = t.substr(j);
//      cout << left + right << endl;
      if((left + right) == "keyence") {
        tf = true;
        break;
      }
    }
    if(tf) break;
  }
  if(tf) cout << "YES" << endl;
  else cout << "NO" << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
map <string,string> mp;
map <string,int> in;

string find(string  x){
  if(mp[x] != x) mp[x] = find(mp[x]);
  return mp[x];
}

void unite(string x,string y){
  x=find(x),y=find(y);
  if(in[x]<in[y]) swap(x,y);
  mp[x] = mp[y];
}

int main() {
  int n,m,a;
  string str,str2;
  cin >> n;
  for(int i=0;i<n;i++) {
    cin >> str >> a;
    in[str] = a;
    mp[str] = str;
  } 

  cin >> m;
  for(int i=0;i<m;i++)cin >> str >> str2,unite(str,str2);

  int ans =0;
  map<string,int> :: iterator it;
  for(it=in.begin();it!=in.end();it++) ans += in[find(it->first)];
  cout << ans <<endl;
  return 0;
}

Measured memory_bytes: 2100
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
    int p;
    int ans = 10000;
    for(int i = 0;i < 3; i++){
        scanf("%d",&p);
        ans = min(ans,p);
    }
    int j1,j2;
    scanf("%d%d",&j1,&j2);
    (j1 > j2) ? ans += j2 : ans+=j1;

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

    return 0;
}

Measured memory_bytes: 1020
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <iomanip>
#include <cassert>
//#include <utility>
//#include <memory>
//#include <functional>
//#include <deque>
//#include <cctype>
//#include <ctime>
//#include <numeric>
//#include <list>
//#include <iomanip>

//#if __cplusplus >= 201103L
//#include <array>
//#include <tuple>
//#include <initializer_list>
//#include <forward_list>
//
//#define cauto const auto&
//#else

//#endif

using namespace std;


typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()
#define DEBUG
#ifdef DEBUG
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#else
#define dump(x) 
#define debug(x) 
#endif

#define MOD 1000000007LL
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)

void mainmain(){
    int n;
    while(cin>>n,n){
        vint v(n);
        rep(i,n) cin>>v[i];
        sort(ALL(v));
        ll sum = 0;
        reep(i,1,n-1){
            sum += v[i];
        }
        // cout<<sum<<endl;
        cout << sum/(n-2) << endl;
    }
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(20);
    mainmain();
}

Measured memory_bytes: 3080
from itertools import accumulate
def resolve():
    N, K = map(int, input().split())
    S = input()

    # even:1
    # odd:0
    # 1-0-1-0-1 の配列にする. 両端は1にする
    L = []
    pre = "1"
    cnt = 0
    for i in range(N):
        if pre == S[i]:
            cnt += 1
        else:
            L.append(cnt)
            cnt = 1
        pre = S[i]
    L.append(cnt)
    # 最後が0で終わっていたら、仮の1を付け足す。(値が0なので影響ない)
    if pre == "0":
        L.append(0)

    # 1-0-1-0-1の配列を作成し、K＝2だとする。
    # 0を2個含めた個数は, 1＝3、0＝2の長さが作成できる
    length = 2 * K + 1

    # 0をすべて変換できる
    if len(L) <= length:
        return print(N)

    # 1-0-1-0-1の配列なので間に0を含んだ数え上げ
    # なので偶数とびに1を起点に数え上げ
    # 累積
    acc = [0] + list(accumulate(L))
    ans = 0
    for i in range(0, len(L), 2):
        left = i
        right = min(i + length, len(L))
        tmp = acc[right] - acc[left]

        ans = max(ans, tmp)

    print(ans)


if __name__ == "__main__":
    resolve()


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

int abcount(string str){
  int c=0;
  while(str.find("AB")!=-1){
    c++;
    str.replace(str.find("AB"),2,"**");
  }
  return c;
}

int main(){
  int N; cin >> N;
  string s[10000];
  for(int i=0; i<N; i++) cin >> s[i];
  
  //もともとあったABの個数
  long long result=0;
  for(int i=0; i<N; i++){
    result+=abcount(s[i]);
  }
  
  //並べたときに--A+B--となった個数
  int cc[4]={};
  for(int i=0; i<N; i++){
    if(s[i][0]=='B'){
      if(s[i][s[i].size()-1]=='A'){
        cc[3]++;
      }else{
        cc[1]++;
      }
    }else{
      if(s[i][s[i].size()-1]=='A'){
        cc[2]++;
      }else{
        cc[0]++;
      }
    }
  }
  
  if(cc[3]>0){
    result+=(cc[3]-1);
    if(cc[2]>0){
      result++;
      cc[2]--;
    }
    if(cc[1]>0){
      result++;
      cc[1]--;
    }
    result+=min(cc[1],cc[2]);
  }else{
    result+=min(cc[1],cc[2]);
  }
  
  cout << result << endl;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<bool> vb;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define in insert
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define Maxn 4000007
const int INF = 1e9 + 5;
const int  N = 2e5 + 314;
void foo(){
    int n, m;
    cin>>n>>m;
    cout<<n*(n-1)/2+m*(m-1)/2;
}
int main(){
    speed;
    int t=1;
    //cin>>t;
    while(t--)foo();
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=(int)(l);i<(int)(r);i++)

typedef long long ll;
ll MOD = 1000000007;

int main()
{
    double n, tmp, ans = 1, d = 0;
    cin >> n;
    vector <double> a(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        ans *= tmp;
        a[i] = tmp;
    }
    for (int i = 0; i < n; i++) {
        d += ans / a[i];
    }
    cout << setprecision(10) << ans/d << endl;

    return 0;
}


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

int main() {
    int n, m, k;
    string ans = "No";
    cin >> n >> m >> k;
    rep(i, n+1) rep(j, m+1) {
        if (k == i * (m - j) + j * (n - i)) ans = "Yes";
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
class Node
  attr_accessor :parent
  def initialize(n)
    @parent = n
  end
end

class UnionFindTree
  attr_accessor :nodes, :parents
  def initialize(n)
    @nodes = (1..n).to_a.map{|i| Node.new(i)}
  end
  def find(x)
    #ループ版
    #while @nodes[x-1].parent != x
    #  x = @nodes[x-1].parent
    #end
    #return @nodes[x-1].parent = x

    #再帰版
    return x if x == @nodes[x-1].parent
    return @nodes[x-1].parent = find(@nodes[x-1].parent)
  end

  def union(a,b)
    return if find(a) == find(b)
    $ans -= 1
    return @nodes[find(b)-1].parent = find(a)
  end

  def parents
    @nodes.map(&:parent)
  end
end

n,m = gets.split.map(&:to_i)
tree = UnionFindTree.new(n)

$ans = n
m.times do |i|
  x,y,z = gets.split.map(&:to_i)
  tree.union(x,y)
end

p $ans


Measured memory_bytes: 10108
#include <bits/stdc++.h>
// #include <iostream>
// #include <vector>
// #include <map>
// #include <algorithm>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())

template<typename T>
T mod(T a, T b){
    return (a + b) % b;
}

template<typename T>
T gcd(T a, T b){
    if (b == 0) return a;
    return gcd(b, a % b);
}

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

// n を素因数分解
map<ll, ll> factor(ll n){
    map<ll, ll> mp;
    for (ll i = 2; i*i <= n; i++) {
        while (n % i == 0) {
            mp[i]++;
            n /= i;
        }
    }

    if (n > 1) {
        mp[n]++;
    }

    return mp;
}

// 文字列に "hoge" が含まれているか
// string str = "hogepiyo";
// if (str.find("hoge") != string::npos) {
//     cout << "文字列が含まれています" << endl;
// }

// char to string
// char c = 'a';
// string str = {c};

void solve(){
    int N;
    cin >> N;

    int ans = 1, H, maxH;
    cin >> H;
    maxH = H;
    for (int i = 1; i < N; i++) {
        cin >> H;
        if (maxH <= H) {
            ans++;
        }
        maxH = max(maxH, H);
    }

    cout << ans << endl;

    return;
}

int main(int argc, char const* argv[])
{
    solve();
    return 0;
}


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

int main(void){
  int a, b, c, k, flag=0;
  scanf("%d %d %d %d", &a, &b, &c, &k);
  for(int i=0; i<k+1; i++){
	for(int j=0;j<k-i+1;j++){
      for(int l=0;l<k-i-j+1;l++){
        a=pow(2, i)*a;
        b=pow(2, j)*b;
        c=pow(2, l)*c;
        if(b>a && c>b){
          	flag=1;
      		break;
    	}
        a=a/pow(2, i);
        b=b/pow(2, j);
        c=c/pow(2, l);
      }
    }
	
  }
  if(flag==1){
    printf("Yes");
  }else{
    printf("No");
  }
  return 0; 
}

Measured memory_bytes: 2580
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		if(n == 1){
			System.out.println("Hello World");
		}else{
			int A = sc.nextInt();
			int B = sc.nextInt();
			
			System.out.println(A + B);
		}
		
		
		
		
		
		
		
		
	}
}


Measured memory_bytes: 23636
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define INF 1e12

#define PB push_back
#define PF push_front
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vpi vector<pii>
#define vll vector<ll>
#define vpl vector<pll>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define MX(x) *max_element(all(x))
#define MN(x) *min_element(all(x))
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pr_d(x) cout << fixed << setprecision(15) << x << endl
#define ud(c, x) distance(c.begin(), upper_bound(all(c), x))
#define ld(c, x) distance(c.begin(), lower_bound(all(c), x))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define rep3(i, n) for (int i = (n - 1); i >= 0; --i)
#define rep4(i, a, b) for (int i = (a); i > (b); --i)
#define pb push_back
#define out(x) cout << x << "\n"
bool odd(int i) { return i % 2; }

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

int gcd(int a, int b) { return __gcd(a, b); }
int lcm(int a, int b) { return a * (b / gcd(a, b)); }
void Yes_No(bool f) {
  if (f)
    printf("Yes\n");
  else
    printf("No\n");
}
void YES_NO(bool f) {
  if (f)
    printf("YES\n");
  else
    printf("NO\n");
}

template <typename T>
void deb1(T x) {
  cout << x << "\n";
}

template <typename T>
bool chmax(T& a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T& a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
//-------------------ここから回答する-----------------------

void solve(void) {
  int h, w, m;
  cin >> h >> w >> m;
  vi x(w), y(h);
  set<pii> s;
  rep(v, m) {
    int i, j;
    cin >> i >> j;
    y[--i]++;
    x[--j]++;
    s.emplace(i, j);
  }

  int mx = 0, my = 0;
  rep(i, h) chmax(my, y[i]);
  rep(i, w) chmax(mx, x[i]);
  vi cx, cy;
  rep(i, h) if (y[i] == my) cy.pb(i);
  rep(i, w) if (x[i] == mx) cx.pb(i);
  int ans = mx + my;
  for (int i : cy) {
    for (int j : cx) {
      if (s.count({i, j})) continue;
      cout << ans << endl;
      return;
    }
  }
  --ans;
  cout << ans << endl;
  return;
}
int main(void) { solve(); }


Measured memory_bytes: 23784
N=int(input())
ans=0
A=int(input())
ans+=int(A/2)
A=A%2
for i in range(N-1):
    B=int(input())
    if B==0:
        A=0
    else:
        if A==1:
            B=B-1
            ans+=1
            ans+=int(B/2)
            A=B%2
        else:
            ans+=int(B/2)
            A=B%2
            
print(ans)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			
			int H = sc.nextInt();
			int W = sc.nextInt();
			
			if(H==0&&W==0)break;

	for ( int i = 0; i < H; i++ ){
		    for ( int j = 0; j < W; j++ ){
		        if( i!=0&&i!=H-1 && j!=0&&j!=W-1     ){
		            System.out.print(".");
		        } else {
		            System.out.print("#");
		        }
		    }
		    System.out.println("");
		}
	System.out.println("");
	

	
	}
	
	}
	
}



Measured memory_bytes: 32272
#include<bits/stdc++.h>
using namespace std;
string s,t;
set<string> st;
set<string>::iterator ip;
int l,k;
int main()
{
    cin>>s;
    l=s.length();
    cin>>k;
    for(int i=0;i<=l;i++)
    {
        for(int le=1;le<=k&&i+le-1<l;le++)
        {
            t=s.substr(i,le);
            st.insert(t);
        }
        
    }
    ip=st.begin();
    for(int i=1;i<k;i++) ip++;
    cout<<*ip;
}

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

using namespace std;

const int OO = 1e9;
const double EPS = 1e-9;

#define ndl cout << '\n'
#define sz(v) int(v.size())
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define present(a, x) (a.find(x) != a.end())
#ifdef LOCAL
#define db(...) ({cout << "> Line " << __LINE__  \
		<< ": "; _db(#__VA_ARGS__, __VA_ARGS__);})
#define RNG() rng()
#else
#define db(...) true
#define RNG() true
#endif

template<class T>
void _db(const char *dbStr, T e) {
	cout << dbStr << " = " << e << endl;
}
template<class T, class... L>
void _db(const char *dbStr, T e, L... r) {
  while(*dbStr != ',') cout << *dbStr++;
  cout << " = " << e << ','; _db(dbStr + 1, r...);
}
template<class S, class T>
ostream& operator<<(ostream& o, const map<S, T>& v) {
	o << "["; int i = 0;
	for (const pair<S, T>& pr : v) o << (!i++ ? "" : ", ") << "{"
	<< pr.fs << " : " << pr.sc << "}"; return o << "]";
}
template<template <class, class...> class S, class T, class... L>
ostream& operator<<(ostream& o, const S<T, L...>& v) {
	o << "["; int i = 0;
	for (const auto& e : v) o << (!i++ ? "" : ", ") << e;
	return o << "]";
}
template<class S, class T>
ostream& operator<<(ostream& o, const pair<S, T>& pr) {
	return o << "(" << pr.fs << ", " << pr.sc << ")";
}
ostream& operator<<(ostream& o, const string& s) {
	for (const char& c : s) o << c;
	return o;
}

template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
template<class T> using VVV = VV<V<T>>;
using ll = long long;
using pii = pair<int, int>;
using vi = V<int>;
using vii = V<pii>;
using vvi = VV<int>;
using mii = map<int, int>;
using umii = unordered_map<int, int>;
using si = set<int>;
using usi = unordered_set<int>;





int main() {
	#ifdef LOCAL
	auto stTime = clock();
//	freopen("in.txt", "r", stdin);
	mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
	#endif
	ios::sync_with_stdio(false);
	cout.precision(10);
	cin.tie(0);

	int N, K;

	cin >> N >> K;

	vi p(N + 1);

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

	int ans = 0, sum = 0;
	for (int i = 1; i <= K; ++i) {
		sum += p[i];
	}
	ans = sum;
	for (int i = 2; i <= N - K + 1; ++i) {
		sum -= p[i - 1];
		sum += p[i + K - 1];
		ans = max(ans, sum);
	}

	cout << fixed << (ans + K) / 2.0 << '\n';

	#ifdef LOCAL
	cout << "\n\n\nExecution time: " <<
		(clock() - stTime) * 1e3 / CLOCKS_PER_SEC << " ms" << endl;
	#endif
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef complex <double> cp;
#define debug(a) cout<<#a<<":"<<a<<endl;
#define fr freopen("in.txt","r",stdin);
#define Fill(x,a) memset(x,a,sizeof(x))
#define cpy(a,b) memcpy(a,b,sizeof(a))
const double PI = acos(-1);
const int INF=0x3f3f3f3f;
const int N=1e6+7;
const int mod=1e9+7;
int maxn,minn;
int T,n,m,q;

int main(){
	cin >> n;
	cout<< (n ^ 1) << endl;

	return 0;
}

Measured memory_bytes: 3592
import sys

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = list(input())
T = list(input())

LS = len(S)
LT = len(T)

if LS == (LT - 1) and S == T[:-1]:
    print("Yes")
else:
    print("No")


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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll, ll> Pll;
typedef pair<int, Pii > P1;

#define rep(i,n) for(int i=0;i<n;i++)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define mp1(a,b,c) P1(a,P(b,c))
#define get_arsize(a) (sizeof(a)/sizeof(a[0]))

const ll MOD = 1000000007;
const double EPS = 1e-10;
const int MAX = 200000;

int main() {
	ll n, k;
	cin >> n >> k;
	ll amari = n % k;
	if (amari >= k - amari) amari = k - amari;
	cout << amari << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using s64 = int64_t;
using u64 = uint64_t;

int main() {
	u64 N;
	cin >> N;
	
	map<u64, u64> As;
	vector<u64> A(N);
	for(u64 i=0; i<N; i++) {
		cin >> A[i];
		As[A[i]] = As[A[i]] + 1;
	}
	
	u64 sum = 0;

	for(const auto& as : As) {
		u64 tsum = as.second * (as.second - 1) / 2;
		sum += tsum;
	}
	
	for(u64 i=0; i<N; i++) {
		auto as = As[A[i]];
		
		u64 tsum0 = as * (as - 1) / 2;
		u64 tsum1 = (as > 1) ? (as - 2) * (as - 1) / 2 : 0;
		
		cout << sum - tsum0 + tsum1 << endl;
	}
	
	return 0;
}

Measured memory_bytes: 11008
# 幅優先探索（行きがけ）
import collections
import sys
import copy
import re


def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    a = I()

    print(a+a**2+a**3)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9892
nN = int(input())
 
sListA = []
nListA = [ 0 for i in range(202)]
 
for i in range(nN):
  sTmp = input()
  if sTmp in sListA:
    nTmp = sListA.index(sTmp)
    nListA[nTmp] += 1
  else:
    sListA.append(sTmp)
    nTmp = sListA.index(sTmp)
    nListA[nTmp] += 1
 
    
nN = int(input())
sListB = []
nListB = [ 0 for i in range(nN)]
 
for i in range(nN):
  sTmp = input()
  if sTmp in sListA:
    nTmp = sListA.index(sTmp)
    nListA[nTmp] -= 1
  else:
    sListA.append(sTmp)
    nTmp = sListA.index(sTmp)
    nListA[nTmp] -= 1
 
nMax = max(nListA)
# print(sListA)
print(nMax)



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

int main(){
	int n,min=10000000,ans=0;
	string s;
	vector<pair<int,int>>a(1000000);
	vector<pair<int,int>>b(1000000);
	cin>>n>>s;
	for(int i=0;i<s.size();i++){
		if(s[i]=='E'){
			a[0].first++;
		}
		else{
			a[0].second++;
		}
	}
	for(int i=1;i<s.size()+1;i++){
		a[i].first=a[i-1].first;
		a[i].second=a[i-1].second;
		b[i].first=b[i-1].first;
		b[i].second=b[i-1].second;
		if(s[i-1]=='E'){
			a[i].first--;
			b[i].first++;
		}
		else{
			a[i].second--;
			b[i].second++;
		}
	}
	for(int i=1;i<s.size()+1;i++){
		if(min>a[i].first+b[i-1].second){
			min=a[i].first+b[i-1].second;
			ans=min;
		}
		//cout<<a[i].first<<a[i].second<<b[i-1].first<<b[i-1].second<<endl;
		
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 16516
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=998244353;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

#include<atcoder/segtree>
using namespace atcoder;

const int M=300001;
int n,m;

int op(int x,int y){return max(x,y);}
int e(){return 0;}

int main(){
	cin>>n>>m;
	segtree<int,op,e> st(M);
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		int l=max(0,x-m),r=min(M,x+m+1);
		int t=st.prod(l,r);
		st.set(x,t+1);
	}
	cout<<st.all_prod()<<endl;
}

Measured memory_bytes: 8540
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
  int n;
  cin >> n;
  ll dp[100] = {};
  dp[0] = 2;
  dp[1] = 1;
  for (int i = 2; i <= n; i++){
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  cout << dp[n] << "\n";
  return 0;
}

Measured memory_bytes: 256
N,M = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(M)]

num = ["0"]*N

for i in l:
    num[i[0]-1] = str(i[1])
    
ans = "".join(num)

for i in l:
    if N!=1 and i[0] == 1 and i[1] == 0:
        print(-1)
        exit()
    if ans[i[0]-1] != str(i[1]):
        print(-1)
        exit()
if N !=len(str(int((ans)))):
    if N == 3:
        ans = int(ans)+100
    if N == 2:
        ans = int(ans)+10
print(int(ans))

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


int main(){
  ll N,M;
  cin >> N >> M;
  if(N == 1 && M == 1)puts("1");
  else if( min(N,M) == 1) cout << max(N,M) - 2 << endl;
  else cout << (N - 2) * (M - 2) << endl; 
  return 0;
}

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

#ifdef LOCAL
#define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define dbg(...) 17;
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) { return os << "(" << p.first << ", " << p.second << ")"; }
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) { bool f = true; os << "{"; for (const auto &x : c) { if (!f) os << ", "; f = false; os << x; } return os << "}"; }
template<typename T> void debug(string s, T x) { cerr << s << " = " << x << "\n"; }
template<typename T, typename... Args> void debug(string s, T x, Args... args) { cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...); }

int main() {
    const int MOD = 2019;
    ios_base::sync_with_stdio(0); cin.tie(0);
    string s; cin >> s;
    int n = s.size();
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = s[i] - '0';
    }
    reverse(a.begin(), a.end());
    vector<ll> pre(n);
    ll base = 1;
    map<int, int> cnt;
    cnt[0] = 1;
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            pre[i] = a[i];
        } else {
            pre[i] = (pre[i - 1] + base * a[i]) % MOD;
        }
        cnt[pre[i]]++;
        base *= 10;
        base %= MOD;
    }
    ll ans = 0;
    for (auto x: cnt) {
        ll num = x.second;
        ans += num * (num - 1) / 2;
    }
    cout << ans << '\n';
    return 0;
}


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

int main() {
  char a, b;
  cin >> a >> b;
  int s = 0;
  int t = 0;

  if (a == 'H') {
    s = 1;
  } else {
    s = -1;
  }

  if (b == 'H') {
    t = 1;
  } else {
    t = -1;
  }

  if(s * t == 1) {
    cout << 'H' << endl;
  } else {
    cout << 'D' << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <algorithm>
#include <bitset>  
using namespace std;

//======================================================
#define for1(i,n)  for (int i = 0; i < (int)(n); ++i)
#define for2(i,n)  for (int i = 1; i <=(int)(n); ++i)
#define forr1(i,n)  for (int i = n - 1 ;i <= 0; --i)
#define forr2(i,n)  for (int i = n  ;i < 0; --i)
#define all(v)	   ((v).begin()), ((v).end())
#define allr(v)	   ((v).rbegin()), ((v).rend())
#define clr(v,d)   memset(v, d, sizeof(v))
#define ull        unsigned long long
#define MP(a,b)	   make_pair(a,b)
#define S          second
#define F          first
#define PI         3.14159265359
#define ll         long long
#define sz(v)	   v.size()
#define pb         push_back
#define pp         pop_back
#define bgn        begin
#define N          100000+5
#define	MOD        1e9+7
#define inf        1e18
//======================================================
int dx[] = { 0,  0, 1, -1 ,  1,  -1,  1,  -1 };
int dy[] = { 1, -1, 0,  0 , -1,   1,  1,  -1 };
//======================================================
ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
ll power(ull a, ull b, ull ret = 1LL) {
	while (b--) ret = (ret * a);
	return ret;
}
//======================================================





int main()
{

	int n;
	cin >> n;
	vector<int> v(n + 1);
	for (size_t i = 1; i <= n; i++)
	{
		cin >> v[i];
	}
	vector<int> dp(n + 1);
	dp[1] = 0;
	dp[2] = abs(v[2] - v[1]);
	for (size_t i = 3; i <=n; i++)
	{
		dp[i] = min(dp[i - 1] + abs(v[i] - v[i - 1]) , dp[i - 2] + abs(v[i] - v[i - 2]));
	}
	cout << dp[n];



}




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

void printReversedArrayInOneLine(int A[], int n) {
    for (int i = n - 1; i >= 0; i--) {
        if (i != n - 1) cout << " ";
        cout << A[i];
    }
    cout << endl;
}

void printArrayInMultipleLines(int A[], int n) {
    for (int i = 0; i < n; i++) {
        cout << A[i] << endl;
    }
}

int insertionSort(int A[], int n, int g) {
    int cnt = 0;
    for (int i = g; i <= n - 1; i++) {
        int v = A[i];
        int j;
        for (j = i - g; j >= 0 && A[j] > v; j -= g) {
            A[j + g] = A[j];
            cnt++;
        }
        A[j + g] = v;
    }
    return cnt;
}

int shellSort(int A[], int G[], int m, int n) {
    int cnt = 0;
    for (int i = m - 1; i >= 0; i--) {
        cnt += insertionSort(A, n, G[i]);
    }
    return cnt;
}

void generateGaps(int G[], int &m, int n) {
    int h = 1;
    for (m = 0; h <= n; m++) {
        G[m] = h;
        h = 3 * h + 1;
    }
}

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

    int G[n];
    int m;
    generateGaps(G, m, n);
    cout << m << endl;
    printReversedArrayInOneLine(G, m);

    cout << shellSort(A, G, m, n) << endl;
    printArrayInMultipleLines(A, n);

    return 0;
}



Measured memory_bytes: 7036
h, w = [int(x) for x in input().split()]
d1 = min(max(w1 * h, (w - w1) * (h // 2), (w - w1) * ((h + 1) // 2))
       - min(w1 * h, (w - w1) * (h // 2), (w - w1) * ((h + 1) // 2)) for w1 in range(1, w))
d2 = min(max(w1 * h, ((w - w1) // 2) * h, ((w - w1 + 1) // 2) * h) 
       - min(w1 * h, ((w - w1) // 2) * h, ((w - w1 + 1) // 2) * h) for w1 in range(1, w))
d3 = min(max(h1 * w, (h - h1) * (w // 2), (h - h1) * ((w + 1) // 2)) 
       - min(h1 * w, (h - h1) * (w // 2), (h - h1) * ((w + 1) // 2)) for h1 in range(1, h))
d4 = min(max(h1 * w, ((h - h1) // 2) * w, ((h - h1 + 1) // 2) * w) 
       - min(h1 * w, ((h - h1) // 2) * w, ((h - h1 + 1) // 2) * w) for h1 in range(1, h))
print(min(d1, d2, d3, d4))

Measured memory_bytes: 3064
n = int(input())
p_t = 0
p_h = 0
for i in range(n):
    c_t,c_h = map(str,input().split())
    if c_t > c_h:
        p_t += 3
    elif c_t < c_h:
        p_h += 3
    else:
        p_t += 1
        p_h += 1
print(p_t,p_h)

Measured memory_bytes: 7640
#include<stdio.h>
#define MAX 100005
#define NIL -1
struct Node_struct{int p, l, r;}; /*p: 親(parent), l: 一番左の子(left child), r:右の兄弟(right sibling)*/
typedef struct Node_struct Node;
Node T[MAX];
int D[MAX];

void print(int u){
 int i, c;
 printf("node %d: parent = %d, depth = %d, ", u, T[u].p, D[u]);

 if(T[u].p == NIL) printf("root, ");
 else if(T[u].l == NIL) printf("leaf, ");
 else printf("internal node, ");

 printf("[");
 for (i=0, c = T[u].l; c != NIL; i++, c = T[c].r){
   if(i) printf(", ");
   printf("%d", c);
 }
 printf("]\n");

}

void calcDepth(int u, int p){
 D[u] = p;
 if(T[u].r != NIL) calcDepth(T[u].r,p);
 if(T[u].l != NIL) calcDepth(T[u].l,p+1);
}

int main(){
 int i, j, k;
 int n;
 int id, sib, child;
 int root = NIL;
 scanf("%d", &n);
 for(i=0; i<n; i++) T[i].p = T[i].l = T[i].r = NIL;

 for(i=0; i<n; i++){
   scanf("%d %d", &id, &k);
   for(j = 0, sib = NIL; j<k; j++){ //子を入力する (input children)
     scanf("%d", &child);
     T[child].p = id;
     if(j == 0) T[id].l = child; //idの一番左の子 (the most left child of id)
     else T[sib].r = child; //左の兄弟に繋げる (connect to left sibling)
     sib = child;//次の子供の左の兄弟 (the left sibling of the next child)
   }
 }

 //根を求める (find the root)
 for(i=0; i<n; i++){
   if(T[i].p == -1) root = i;
    }

 //それぞれのノードの深さを求める (find depth of each node)
 calcDepth(root, 0);

 //出力 (output)
 for(i=0; i<n; i++) print(i);

 return 0;
}



Measured memory_bytes: 6484