akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define erep(e,v) for(auto && e :v)
#define all(in) in.begin(), in.end()
#define MP make_pair
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
#define EPS 0.0000000001
using namespace std;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
template<class T> void join(T a){for(auto itr :a){if(itr != *a.begin())cout << " "; cout << itr;} }
using ld  = long double;
using pii = pair<int,int>;
using piii = pair<int,pii>;
int W,H;
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
bool valid(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);}
template<class T, class Func = function<T(T, T)>>
class segtree {
    vector<T> obj;
    int offset;
    Func updater;
    T e;
    int bufsize(int num) {
        int i = 1;
        for (; num >i; i <<= 1);
        offset = i - 1;
        return (i << 1) - 1;
    }
    T query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l)return e;
        if (a <= l && r <= b)return obj[k];
        else return updater(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r));
    }
public:
    T query(int a, int b) {//[a,b)
        return query(a, b, 0, 0, offset + 1);
    }
    void updateall(int l = 0, int r = -1) {
        if (r < 0)r = offset + 1;
        l += offset, r += offset;
        do {
            l = (l - 1) >> 1, r = (r - 1) >> 1;
            for (int i = l; i < r; i++)obj[i] = updater(obj[i * 2 + 1], obj[i * 2 + 2]);
        } while (l);
    }
    void update(int k, T &a) {
        k += offset;
        obj[k] = a;
        while (k) {
            k = (k - 1) >> 1;
            obj[k] = updater(obj[k * 2 + 1], obj[k * 2 + 2]);
        }
    }
    segtree(int n, T e, const Func &updater = Func()) :obj(bufsize(n), e), e(e), updater(updater) {}
    segtree(vector<T> &vec, T e, const Func &updater = Func()) :obj(bufsize(vec.size()), e), e(e), updater(updater) {
        copy(vec.begin(), vec.end(), obj.begin() + offset);
        updateall();
    }
    typename vector<T>::reference operator[](int n) {
        return obj[n + offset];
    }
};
signed main(){
    int n,k; cin >> n >> k;
    vector<int>v(n); for(auto & e : v) cin >> e;
    sort(all(v));
    auto mini = segtree<int>(v,INF,[](int a, int b){return min(a,b);});
    auto maxi = segtree<int>(v,-INF,[](int a, int b){return max(a,b);});
    int ans = INF;
    for(int i = 0; i + k <= n;i++){
        cmin(ans, maxi.query(i, i+k) - mini.query(i,i+k));
    }
    cout << ans << endl;
}





Measured memory_bytes: 5120
#include <iostream>

int main () {
    using namespace std;
    int n,s, a;
    cin >> n;
    s = 0;
    for (int i=0;i<n;i++) {
        cin >> a;
        // cout << ((int) a & 1);

        if ((a & 1) != 1) {
            // cout << a;
            if ((a % 3 != 0) && (a % 5 != 0)) {
                s = 1;
            }
        }
    }
    if (s==0) cout << "APPROVED";
    else cout << "DENIED";
}

Measured memory_bytes: 3624
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
		int x,y;
		while(true) {
			int H=scan.nextInt();
			int W=scan.nextInt();
			if(H == 0 && W == 0) break;
			for(y=0;y<H;y++) {
				for(x=0;x<W;x++) {
					if(y==0 || y==H-1 || x==0 || x==W-1) {
					System.out.printf("#");
					}
					else
						System.out.printf(".");
				}
				System.out.printf("\n");
			}
			System.out.printf("\n");
		}
		scan.close();
}
}


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

/* 
 * g++ -std=c++17 A.cpp -o A
 */
int main() {
  ios_base::sync_with_stdio(false);
  int W, H, N;
  cin>>W>>H>>N;
  pair<int, int> low = {0, 0};
  pair<int, int> high = {W, H};
  for(int i = 0; i < N; i++) {
    int x, y, a;
    cin>>x>>y>>a;
    if (a == 1) {
      low.first = max(low.first, x);
    } else if (a == 2) {
      high.first = min(high.first, x);
    } else if (a == 3) {
      low.second = max(low.second, y);
    } else if (a == 4) {
      high.second = min(high.second, y);
    }
  }
  int res = max(0, high.first - low.first) * max(0, high.second - low.second);
  cout << res << endl;
}


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

#define INF (2e9)
#define FOR(i, a, b) for (ll (i) = (a); (i) < (b); ++(i))
#define REP(i, n) FOR(i, 0, n)

using namespace std;

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

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

using ll = long long;
using ld = long double;

#define ALL(x) (x).begin(), (x).end()
template<class T>
using vc = vector<T>;
using vi = vc<ll>;
using vvi = vc<vi>;

template<class T>
using va = valarray<T>;
using vad = va<ld>;
using vai = va<ll>;

using pii = pair<ll, ll>;

vi Read(ll n) {
    auto      v = vi(n);
    for (auto i = std::size_t(0); i < n; ++i) {
        cin >> v[i];
    }
    return v;
}

template<class T>
void DumpRow(const T& A) {
    for (const auto& value : A)
        cout << value << "\n";
}

template<class T>
void DumpColumn(const T& A) {
    auto isFirst = true;
    for (const auto& value : A) {
        if (isFirst) {
            cout << value;
            isFirst = false;
        } else {
            cout << " " << value;
        }

    }
    cout << endl;
}

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

    bitset<64> bit(0);

    int n;
    cin >> n;
    auto mask = vc<bitset<64>>(n);
    REP(i, n) {
        int k;
        cin >> k;
        REP(j, k) {
            int k;
            cin >> k;
            mask[i].set(k);
        }
    }

    int q;
    cin >> q;

    REP(i, q) {
        int query;
        unsigned int j;
        cin >> query >> j;
        switch (query) {
            case 0:
                cout << bit.test(j) << endl;
                break;
            case 1:
                bit |= mask[j];
                break;
            case 2:
                bit &= ~mask[j];
                break;
            case 3:
                bit ^= mask[j];
                break;
            case 4:
                cout << ((bit & mask[j]) == mask[j]) << endl;
                break;
            case 5:
                cout << (bit & mask[j]).any() << endl;
                break;
            case 6:
                cout << (bit & mask[j]).none() << endl;
                break;
            case 7:
                cout << (bit & mask[j]).count() << endl;
                break;
            case 8:
                cout << (bit & mask[j]).to_ullong() << endl;
                break;
        }
    }
    return 0;
}



Measured memory_bytes: 3204
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int main() {
	int N;
	cin >> N;
	
	if (N % 1000 == 0) {
		cout << 0 << endl;
	}
	else {
		cout << 1000 - (N % 1000) << endl;
	}
	return(0);
}


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

using namespace std;
typedef long long ll;
typedef pair <ll, ll> l_l;
typedef pair<int, int> i_i;

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

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

# define EPS (1e-7)
# define INF (1e9)
# define PI (acos(-1))
//const ll mod = 1000000007;

int N;
int P[10], Q[10];

bool eq(int x[], vector<int> y) {
    for (int i = 0; i < y.size(); ++i) {
        if (x[i] != y[i]) {
            return false;
        }
    }
    return true;
}

int main() {
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> P[i];
    for (int i = 0; i < N; ++i) cin >> Q[i];

    vector<int> v;
    for (int i = 1; i <= N; ++i) v.push_back(i);

    int a=0, b=0;
    bool fin_a = false, fin_b = false;
    do{
        if (!eq(P, v) && !fin_a) {
            a++;
        } else {
            fin_a = true;
        }
        if (!eq(Q, v) && !fin_b) {
            b++;
        } else {
            fin_b = true;
        }
    }while(next_permutation(v.begin(), v.end()));
    cout << (int)abs(a - b) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <ctime>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <complex>

using namespace std;
typedef complex<double> xy_t;
double x[4], y[4];

double cross_product(xy_t a, xy_t b) { return (conj(a)*b).imag(); }

bool three(double s, double t, double u){
	if(s * t > 0 && s * u > 0) return true;
	else return false;
}


int main(void){
	while(true){
		for (int i = 0; i < 4; ++i){
			cin >> x[i] >> y[i];
		}
		if(!cin) break;

		xy_t a(x[0], y[0]), b(x[1], y[1]), c(x[2], y[2]), p(x[3], y[3]);

		double apb, bpc, cpa;
		apb = cross_product(a - p, b - p);
		bpc = cross_product(b - p, c - p);
		cpa = cross_product(c - p, a - p);

		bool ok = three(apb, bpc, cpa);
		cout << (ok ? "YES" : "NO") << endl;
		
	}
	
    return 0;
}

Measured memory_bytes: 1220
#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#define MOD 1000000007
using namespace std;
int main(void){
    // Your code here!
    
    int a,b,c;
    cin >> a >> b >> c;
    
    if(a < c && c < b) cout << "Yes" << endl;
    else if (b < c && c < a) cout << "Yes" << endl;
    else cout << "No" << endl;
    
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))

mod = 10 ** 9 + 7

arr_sum = 0
for i in range(N):
    arr_sum = (arr_sum + A[i]) % mod

arr_sum_square = (arr_sum * arr_sum) % mod

individual_square_sum = 0
for i in range(N):
    individual_square_sum = (individual_square_sum + (A[i] * A[i]) % mod) % mod

ans = arr_sum_square - individual_square_sum
ans = ans * pow(2, mod - 2, mod)
ans %= mod
print(ans)


Measured memory_bytes: 30956
S = input()

cntMax = 0
cnt = 0

for s in S:
    #print(s)
    if s == 'A' or s == 'C' or s == 'G' or s == 'T':
        cnt += 1
    else:
        cntMax = max(cntMax, cnt)
        cnt = 0

cntMax = max(cntMax, cnt)

print(cntMax)

Measured memory_bytes: 3060
// inputに入力データ全体が入る
    function Main(inputString) {
    	// 1行目がinput[0], 2行目がinput[1], …に入る
        let inputNumber = inputString.trim();
        let sum = 0;
        for(let i = 1; i<=inputString; i++){
            for(let j = 1; j<=inputString; j++){
                for(let k = 1; k<=inputString; k++){
                    let tmpIjGcd = gcdFunction(i,j);
                    let tmpIjkGcd = gcdFunction(tmpIjGcd, k); 
                    sum += tmpIjkGcd;
                }
            }
        }

    	//出力
    	console.log(sum);
    }

    function gcdFunction(a, b) {
        if (b==0){
            return a;
        }
        // a < bでもここで入れ替わるのでおK
        return gcdFunction(b, a % b);
    }

    //*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
    Main(require("fs").readFileSync("/dev/stdin", "utf8"));
    // Main('200');

Measured memory_bytes: 31624
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
using namespace std;
int main() {
  int n, k;
  long long a = 0, b = 0;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    if (i%k == 0) {
      a++;
    }
    if (i%k == (double)k/2) {
      b++;
    }
  }
  cout << a*a*a+b*b*b << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace Main
{
    public static class Program
    {
static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            var a = new List<int>(Console.ReadLine().Split(' ').Select(x=>int.Parse(x)));
            int[] array = new int[n+1];
            
            foreach(int t in a){
                array[t]++;
            }
            for(int i=1;i<n+1;i++){
                Console.WriteLine(array[i]);
            }
 
        }
        #region libraries
        private static int[] GetIntList(string line)
        {
            return line.Split(' ').Select(x => int.Parse(x)).ToArray();
 
        }
        private static double[] GetDoubleList(string line)
        {
            return line.Split(' ').Select(x => double.Parse(x)).ToArray();
 
        }
        private static ulong[] GetUlongList(string line)
        {
            return line.Split(' ').Select(x => ulong.Parse(x)).ToArray();
        }
        private static long[] GetLongList(string line)
        {
            return line.Split(' ').Select(x => long.Parse(x)).ToArray();
        }
        private static int SearchNearest(this IEnumerable<int> list, int target)
        {
            var min = list.Min(c => Math.Abs(c - target));
            return list.First(c => Math.Abs(c - target) == min);
        }
        public static bool IsOdd(int i)
        {
            return i % 2 == 1 ? true : false;
        }
        public static int Gcd(int a,int b)
        {
            if(a < b)
            {
                Gcd(b, a);
            }
            while (b != 0)
            {
                var rm = a % b;
                a = b;
                b = rm;
            }
            return a;
        }
        #endregion libraries
    }
}

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



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

    map<int, int>  d_map;
    for(int i=0;i<n;i++){
        int wk;
        cin>>wk;

        if(d_map.count(wk))
            d_map.at(wk)++;
        else
            d_map[wk]=1;
    }


    int m;
    cin>>m;
    bool flg=true;
    for(int i=0;i<m;i++){
        int t;
        cin>>t;

        if(d_map.count(t)){
            d_map.at(t)--;
            if(d_map.at(t)<0)
                flg=false;
        }
        else
            flg=false;
    }

    if(flg)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;

    return 0;
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long 
#define pb push_back
//#define mp make_pair
#define fr first
#define sc second
#define N ((ll)(2e6+100))
#define MAX ((ll)(1e16+100))
#define ARRS ((ll)(3e5+100))
#define MOD ((ll)(1e9+7))
#define M1 ((ll)(1001783))
#define M2 ((ll)(1001941))
#define M3 ((ll)(1002073))
#define pb push_back


ll n,m;
ll a[ARRS];
ll pr[ARRS];
ll b[ARRS];
string s;
vector<ll> v[ARRS];
ll k,p,c,d,t;

ll par(ll x){
	if(pr[x]==x)return x;
	else return pr[x]=par(pr[x]);
}

void join(ll x,ll y){
	x=par(x);
	y=par(y);
	pr[y]=x;
}


int main(){
	cin>>n>>m;
	for(int i=0; i<n; i++)
		cin>>a[i],pr[i]=i;
	for(int j=0; j<m; j++){
		cin>>k>>p;
		join(k,p);
	}
	for(int i=0; i<n; i++)
		v[par(i)].pb(a[i]);
	ll pas=0;
	vector<ll> ka;
	for(int i=0; i<n; i++){
		if(par(i)==i){
			sort(v[i].begin(),v[i].end());
			pas+=v[i][0];
			for(int j=1; j<v[i].size(); j++)ka.pb(v[i][j]);
			c++;
			//cout<<pas<<" "<<c<<endl; 
		}
	}
	if(c==1){
		cout<<0<<endl;
		return 0;
	}
	sort(ka.begin(),ka.end());
	if(ka.size()<c-2){
		cout<<"Impossible";
		return 0;
	}
	for(int i=0; i<c-2; i++)pas+=ka[i];
	cout<<pas;
}
 


Measured memory_bytes: 15872
package main

import (
  "fmt"
)

func main() {

 	var N int

 	fmt.Scan(&N)

	var answer int

  for C:= 1; C <= N; C += 2 {
		var num_of_divisors int
    for X := 1; X <= C; X++ {
			if C % X == 0 {
				num_of_divisors++
			}
		}
		if num_of_divisors == 8 {
			answer++
		}
	}
  fmt.Print(answer)
}

Measured memory_bytes: 512
n,m=map(int,input().split())
A=set(int(input()) for i in range(m))
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in A:dp[i]=0
print(dp[n])

Measured memory_bytes: 11884
#ifdef DEBUG

#else

#    pragma GCC optimize("O3,no-stack-protector")
#    pragma GCC optimize("unroll-loops")

#    if __cplusplus < 201703L
#        pragma GCC target("avx")
#    else
#        pragma GCC target("avx2")
#    endif

#endif
// 実数の場合
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;
typedef long double Ld;

using namespace std;
using Graph = vector<vector<Int>>;

const double pi = M_PI;
const Int MOD = 1000000007;

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

    Int n;
    cin >> n;

    Int ans = 0;

    if (!(n & 1)) {
        Int d = 10;
        while (d <= n) {
            ans += n / d;
            d *= 5;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 384
n=int(input())
a=[]
b=[i+1 for i in range(n)]
for i in range(n):
  m,l=(j for j in input().split())
  a.append([m,int(l)])
for i in range(n):
  for j in range(n-1):
    if a[j+1][0]<a[j][0] or (a[j+1][0]==a[j][0] and a[j][1]<a[j+1][1]):
                 c=a[j]
                 a[j]=a[j+1]
                 a[j+1]=c
                 d=b[j]
                 b[j]=b[j+1]
                 b[j+1]=d
for i in range(n):
  print(b[i])


Measured memory_bytes: 3064
#include <cmath>
#include <iostream>

int main(int argc, char const* argv[])
{
    uint64_t a, b, x;
    std::cin >> a >> b >> x;

    uint64_t max_len = b - a + 1;
    uint64_t start = a;
    uint64_t result = 0;

    if(a == 0)
    {
        start = 0;
        result++;
        goto calc;
    }

    for(uint64_t i = 0; (x * i) <= b; ++i)
    {
        uint64_t tmp = x * i;
        if(a <= tmp)
        {
            start = tmp;
            result++;
            goto calc;
        }
    }

    /*
    for (uint64_t i = 0; i < max_len; ++i)
    {
        if ((a + i) % x == 0) {
            start = a + i;
            result++;
            break;
        }
    }
    */

calc:
    result += ((b - start)) / x;
print:
    std::cout << result << std::endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int h,w;
  cin>>h>>w;
  string a[h];
  for(int i=0;i<h;i++) cin>>a[i];
  int x=h+w-1,c=0;
  for(int i=0;i<h;i++)
    c+=count(a[i].begin(),a[i].end(),'#');
  if(x==c) cout<<"Possible"<<endl;
  else cout<<"Impossible"<<endl;
    
  return 0;
}


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

ll w[102], v[102], dp[102][100005];

int main() {
	int n;
	ll W;
	scanf("%d %lld", &n, &W);
	for (int i = 1; i <= n; i++) {
		scanf("%lld %lld", &w[i], &v[i]);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= W; j++) {
			dp[i][j] = dp[i - 1][j];
			if (j >= w[i]) {
				dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
			}
		}
	}
	printf("%lld", dp[n][W]);
}

Measured memory_bytes: 78336
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <vector>
#include <stdio.h>
#include <iostream>
#include <unordered_set>
#include <algorithm>
#include <bitset>
#include <set>
#include <map>
#include <random>
#include <time.h>
#include <cassert>

#define prev askdnsajd
#define rank asasdmdnasd
#define next lsjndajbs
#define hash asmdklansd
#define index asdklnas
#define right sld
#define left sldl
using namespace std;

typedef long long ll;
typedef long double dbl;

template<class T>
void print(vector<T> s){
    for (T x : s)
        cout << x << " ";
    cout << endl;
}

int main(){
    srand(17);
    ios_base::sync_with_stdio(0);
  	int n;
  	cin >> n;
  	vector<int> s(n);
  	map<int, int> cnt;
  	set<int> diff;
  	for (int i = 0; i < n; i++){
  		cin >> s[i];
  		diff.insert(s[i]);
  		cnt[s[i]]++;
  	}
  	if (n % 3 != 0){	
  		int t = *(diff.begin());
  		if (diff.size() == 1 && t == 0)
  			cout << "Yes\n";
  		else
  			cout << "No\n";
  		return 0;
  	}
  	if (diff.size() == 3){
  		int cur = 0;
  		for (auto x : cnt){
  			cur ^= x.first;
  			if (x.second != n / 3){
  				cout << "No\n";
  				return 0;
  			}
  		}
  		if (cur == 0)
  			cout << "Yes\n";
  		else
  			cout << "No\n";
  		return 0;
  	}
  	if (diff.size() == 2){
  		for (auto x : cnt){
  			if (x.second % (n / 3) != 0){
  				cout << "No\n";
  				return 0;
  			}
  			if (x.second == n / 3 && x.first != 0){
  				cout << "No\n";
  				return 0;
  			}
  		} 	
  		cout << "Yes\n";
  		return 0;	
  	}
  	if (diff.size() == 1){
  		int t = *(diff.begin());
  		if (t == 0)
  			cout << "Yes\n";
  		else
  			cout << "No\n";
  	}
  	else
  		cout << "No\n";
    return 0;
}

Measured memory_bytes: 7808
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)


void solve(long long N, long long K, std::vector<long long> h){
    lint dp[N];
    lint dst;
    REP(i, N) {dp[i] = 1LL<<60;}
    dp[0] = 0LL;
    REP(i, N-1) {
        REP(j, K+1){
            dst = i + j;
            if(dst >= N) continue;
            dp[dst] = min(dp[dst], dp[i] + abs(h[i] - h[dst]));
        }
    }
    cout << dp[N-1] << "\n";
}

int main(){

    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    std::vector<long long> h(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&h[i]);
    }
    solve(N, K, std::move(h));
    return 0;
}



Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
using namespace std;

int main() {
    int t, n;
    while (cin >> t, t) {
        cin >> n;
        int s, f, sum = 0;
        for (int i=0; i<n; ++i) {
            cin >> s >> f;
            sum += f - s;
        }
        if (t <= sum) {
            cout << "OK" << endl;
        } else {
            cout << t - sum << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <string>
#include <algorithm>
#define ll long long
using namespace std;

ll m=1e9+7;
ll dp[1001][1001];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int r, c;
    cin >> r >> c;
    for(int i=1; i<=r; i++)
    {
        string str;
        cin >> str;
        for(int j=1; j<=c; j++)
        {
            if(str[j-1]=='#')
                dp[i][j]=-1;
        }
    }
    dp[0][1]=1;
    for(int i=1; i<=r; i++)
    {
        for(int j=1; j<=c; j++)
        {
            if(dp[i][j]==-1) continue;
            if(dp[i][j-1]==-1 && dp[i-1][j]==-1) dp[i][j]=-1;
            else if(dp[i][j-1]==-1) dp[i][j]=dp[i-1][j];
            else if(dp[i-1][j]==-1) dp[i][j]=dp[i][j-1];
            else dp[i][j]=(dp[i-1][j]+dp[i][j-1])%m;
        }
    }
    if(dp[r][c]<=0){
        cout << 0; return 0;
    }
    cout << dp[r][c];
}


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


int main(){
  int m[101][101], p[101];
  int n, l, i, j, k, q;

  scanf("%d", &n);

  for(i = 1; i <= n; i++){
    scanf("%d%d", &p[i-1], &p[i]);
  }

  for(i = 1; i <= n; i++) m[i][i] = 0;
  
  for(l = 2; l <= n; l++){
    for(i = 1; i <= n - l + 1; i++){
      j = i + l - 1;
      m[i][j] = (int)INFINITY;
      for(k = i; k <= j - 1; k++){
	q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
	m[i][j] = fmin(m[i][j], q);
      }
    }
  }

  printf("%d\n", m[1][n]); 
  return 0;
}



Measured memory_bytes: 2132
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        sc.nextLine();
        
        int count = 0;
        int p;
        for(int i = 1; i <= n; i++){
            p = sc.nextInt();
            if(p != i){
                count++;
            }
        }
        
        if(count == 0 || count == 2){
            System.out.println("YES");
        }else{
            System.out.println("NO");
        }
    }
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 4005


struct Info{

	bool operator<(const struct Info &arg) const{
		return diff_value < arg.diff_value;
	}
	ll weight,base_value,diff_value;
};

int N;
int minimum[NUM];
ll W;
ll dp[NUM][NUM]; //dp[何番目までの歌を見たか][時間の合計]
Info info[NUM];

int main(){

	scanf("%d %lld",&N,&W);

	info[0].base_value = 0;
	info[0].diff_value = 0;
	for(int i = 1; i <= N; i++){
		scanf("%lld %lld %lld",&info[i].weight,&info[i].base_value,&info[i].diff_value);
	}

	if(N == 1){
		printf("%lld\n",info[1].base_value);
		return 0;
	}

	sort(info,info+N+1);

	for(int i = 0; i <= N; i++){
		dp[i][0] = 0;
		for(int k = 1; k <= W; k++){
			dp[i][k] = -HUGE_NUM;
		}
	}

	dp[0][0] = 0;

	ll min_weight = BIG_NUM;
	ll ans = 0;

	//各歌が先頭になる値をまず計算
	for(int i = 1; i <= N; i++){
		dp[i][info[i].weight] = info[i].base_value;
		ans = max(ans,info[i].base_value);
		min_weight = min(min_weight,info[i].weight);
	}
	ll max_pre_value;
	int pre_deq_index;

	ll a,x,pre_x;

	for(int i = 0; i <= W; i++){
		minimum[i] = 0;
	}

	int debug = -1;
	ll tmp_weight;

	for(int song = 1; song <= N; song++){ //歌のループ
	//for(int song = 1; song <= 3; song++){

		a = info[song].diff_value;

		for(ll w = 1 ; w <= W; w++){ //重みのループ

			dp[song][w] = max(dp[song][w],dp[song][w-1]);
			if(w < info[song].weight)continue;

			max_pre_value = -HUGE_NUM;
			tmp_weight = w-info[song].weight;

			for(int i = minimum[tmp_weight]; i < song; i++){
				if(dp[i][tmp_weight] == -HUGE_NUM){
					continue;
				}
				x = info[i].diff_value;
				if(max_pre_value < dp[i][w-info[song].weight]+(2*a*x-x*x)){
					max_pre_value = dp[i][w-info[song].weight]+(2*a*x-x*x);
					pre_deq_index = i;
					pre_x = x;
				}
			}

			if(max_pre_value == -HUGE_NUM)continue;

			dp[song][w] = max(dp[song][w],dp[pre_deq_index][tmp_weight]+(2*a*pre_x-pre_x*pre_x)+info[song].base_value-a*a);
			ans = max(ans,dp[song][w]);

			//以後、最適になることのない値はDEQUEから論理削除する
			while(minimum[tmp_weight] < pre_deq_index){
				minimum[tmp_weight]++;
			}
			debug = pre_deq_index;
		}
	}

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

	return 0;
}




Measured memory_bytes: 120692
import sys
input = sys.stdin.readline

A, B, K = map(int, input().split())

M = max(A,B)
N = min(A,B)

ans = []
while(N != 0):
    M, N = N, M%N
s = 0
MAX = M + 0
current = 0
for i in range(1,101):
    if M%i == 0:
        ans.append(int(i))
ans.sort(reverse=True)
print(ans[K-1])


Measured memory_bytes: 38384
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<numeric>
#include<deque>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=1e9+7;
const int MOD=998244353;
const int N = 1e6 + 5;
const ll inv2=499122177;
const double pi=acos(-1);
ll a[1000005],f[1000005];
ll n,k,ans;
bool cmp(ll a,ll b)
{
	return a>b;
}
int solve(ll o)
{
	ll sum=0;
	for(ll i=0;i<n;i++)
	{
		ll p=o/f[i];
		if(p<a[i])
			sum+=a[i]-p;
	}
	if(sum<k)
		return -1;
	else if(sum>k)
		return 1;
	else
		return 0;
}
int main()
{
	ll sum=0;
	scanf("%lld%lld",&n,&k);
	for(ll i=0;i<n;i++)
	{
		scanf("%lld",&a[i]);
		sum+=a[i];
	}
	sort(a,a+n);
	for(ll i=0;i<n;i++)
	{
		scanf("%lld",&f[i]);
	}
	sort(f,f+n,cmp);
	ll L=0,R=1e12,mid;
	while(L<=R)
	{
		mid=(L+R)/2;
		if(solve(mid)==-1)
		{
			R=mid-1;
		}
		else if(solve(mid)==1)
		{
			L=mid+1;
		}
		else
		{
			break;
		}
	}
	while(solve(mid)==0||mid==-1)
		mid--;
	while(solve(mid)==1)
		mid++;
	if(k>=sum)
		mid=0;
	printf("%lld\n",mid);
    return 0;
}



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

using namespace std;
typedef long long ll;

int main(){
  int N;
  cin >> N;
  vector<int> ans(N+1, 0);
  for (int x=1; x<=100; x++){
    for (int y=1; y<=100; y++){
      for (int z=1; z<=100; z++){
        int f = x*x + y*y + z*z + x*y + y*z + z*x;
        if (f <= 10000){
          ans[f]++;
        }
      }
    }
  }
  for (int i=0; i<N; i++){
    cout << ans[i+1] << "\n";
  }
  return 0;
}

Measured memory_bytes: 3488
///*****************************************************///
///*.......................Faiyaj Bin Amin............................*///
///*...................................................................*///
///*.........................KUET CSE 2K17......................*///
///*...................................................*///
///*****************************************************///

#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define fastio      ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define ret return
#define rep(q, i, n) for(int q=i; q<n; q++)
#define forn(i, n) for(int i=0; i<n; i++)
#define mems(a,x) memset(a,x,sizeof(a))
#define ll long long
#define pb push_back
#define em emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()
#define ff first
#define ss second
#define pii pair<int,int>
#define pdd pair<double, double>

#define see(x)        cerr<< __LINE__ << ": " << (#x) << " is "<< (x) <<'\n';
#define seecontent(v) for(auto x : v) { cout << x << " ";} cout << "\n\n";

#define PI 2*acos(0.0)
#define lcm(a, b)  ((a / __gcd(a, b) ) * b)

#define filein freopen ("input.txt", "r", stdin)
#define fileout freopen ("output.txt", "w", stdout)

#define mx 100005
#define INF 1e18
#define MOD 1000000007
#define MIN 0

//template <typename T>  using orderedSet =
//    tree<T, null_type, less_equal<T>,
//    rb_tree_tag, tree_order_statistics_node_update>; //find_by_order, order_of_key


/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0}; // Directional
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*---------------------------------------------------------------------*/

/**------------------------------------BITMASK------------------------------------------**/
//int Change(int N, int pos){return N= N^(1<<pos);}
//bool Check(int N, int pos){return (bool)(N &(1<<pos));}  /// check bit 0 or 1
/**-----------------------------------------------------------------------------------------------**/

//using namespace __gnu_pbds;
using namespace std;

int main()
{
    fastio;

    int n;
    cin>>n;

    int a[n], g[n], r[n];
    forn(i, n)
    {
        cin >> a[i];
    }
    sort(a, a+n);

    g[0]=a[0];
    r[n-1]=a[n-1];
    for(int i=1; i<n; i++)
    {
        g[i] = __gcd(g[i-1], a[i]);
    }

    for(int i=n-2; i>=0; i--)
    {
        r[i] = __gcd(r[i+1], a[i]);
    }

    int maxi=g[n-1];
    if(n>1)
    {
        maxi = max(maxi, r[1]);
        maxi = max(maxi, g[n-2]);
    }
    for(int i=1; i<n-1; i++)
    {
        if(a[i]!=a[i+1])
        {
            maxi = max(maxi, __gcd(g[i-1], r[i+1]));
        }
    }

////    seecontent(a);
////    seecontent(g);
////    seecontent(r);

    cout << maxi << "\n";

    return 0;
}


Measured memory_bytes: 4800
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
constexpr int MOD = 1000000000 + 7;
constexpr int INF = 2000000000;
using namespace std;


int main() {
	long long n, a, b;
	cin >> n >> a >> b;
	if (a > b)cout << 0 << endl;
	else if (n == 1) {
		if (a != b)cout << 0 << endl;
		else cout << 1 << endl;
	}
	else {
		cout << (b - a)*(n - 2) + 1 << endl;
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
int main(void){
    unsigned long long  n,m;cin>>n>>m;unsigned long long ans;
    if(n==1||m==1)ans=(n*m-2);
    else if(n==2||m==2)ans=0;
    else ans=(n*m-(n-1)*2-(m-1)*2);
    if(n==1&&m==1)ans=1;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))
Cs = list(map(int, input().split()))
ans = 0
for i in range(0, n):
    ans += Bs[As[i]-1]
    if i>=1:
        if As[i] - As[i-1] == 1:
            ans+=Cs[As[i-1]-1]
print(ans)

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,pair<ll,ll>> pii;
typedef pair<ll,ll> pi;
typedef vector<ll> vl;

#define matrix vector<vector<ll>>
#define llmax LLONG_MAX
#define llmin LLONG_MIN
#define rep(i,n) for(ll (i)=0;(i)<n;++(i))
#define crep(i,m,n) for(ll (i)=m;(i)<n;++(i))
#define zero(a) memset((a),0,sizeof((a)))
#define minus(a) memset((a),-1,sizeof((a)));
#define sq(a) ((a)*(a))
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define ff first
#define ss second

ll global=0;

// return nCr value
long long C(int n, int r) {
	if(r>n) return 0;
    if(r > n - r) r = n - r; // because C(n, r) == C(n, n - r)
    long long ans = 1;
    int i;
    for(i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
    }
    return ans;
}

// return whether number is prime or not
vector<ll> sieve(ll n){
    vector<ll> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i] && (long long)i * i <= n) {
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }
    return is_prime;
}


void test_case();
int main(){
    ios::sync_with_stdio(0);    
    cin.tie(0); cout.tie(0);
    ll t=1;
    // cin >> t;
    for(ll T=0;T<t;T++){
        test_case();
    }
    //**************************************************************************//
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

void self_max(ll &a, ll b){
    a = max(a,b);
}

void test_case(){
    ll n,W;cin>>n>>W;
    std::vector<ll>dp(W+1,0);
    rep(i,n){
        ll wt,val;
        cin>>wt>>val;
        for(ll weight_already = W-wt;weight_already>=0;--weight_already){
            self_max(dp[weight_already+wt], dp[weight_already]+val);
        }
    }
    ll ans=-1;
    rep(i,W+1){
        self_max(ans, dp[i]);
    }
    cout<<ans;
}


Measured memory_bytes: 3984
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
using namespace std;
#define mod 1000000007

int main(void) {
	// your code goes here
	int a,b,g[101][101],i,j;
	cin >> a >> b;
	cout << "100 100" << endl;
	for(i=1;i<=50;i++){
		for(j=1;j<=100;j++) g[i][j]=0;
	}
	for(i=51;i<=100;i++){
		for(j=1;j<=100;j++) g[i][j]=1;
	}
	
	for(i=1;i<=a-1;i++) g[2*((i-1-(i-1)%50)/50)+1][2*((i-1)%50)+1]=1;
	for(i=1;i<=b-1;i++) g[101-(2*((i-1-(i-1)%50)/50)+1)][101-(2*((i-1)%50)+1)]=0;
	
	for(i=1;i<=100;i++){
		for(j=1;j<=100;j++){
			if(g[i][j]==1) cout << ".";
			else cout << "#";
		}
		cout << endl;
	}
	return 0;
}


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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
//#define int long long
#define ll long long
#define REP(i,a,b) for (int i=a; i<b; i++)
#define fcout cout << fixed << setprecision(15)

using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pi;

signed main() {
  IOS;
  int N,K;
  double ans=0;
  cin >> N >> K;
  REP(i, 1, N+1) {
    if (i >= K) {
      ans += 1.0/N;
      continue;
    }
    int a = (int)ceil(log((double)K/i) / log(2));
//    cout << i << " " << a << " " << pow(0.5,a) << endl;
    ans += pow(0.5,a) / N;
  }
  fcout << ans << endl;
  return 0;
}


Measured memory_bytes: 640
// =========
use std::cmp::{max, min};
use std::collections::{HashMap, HashSet};
use std::process::exit;

const MOD: usize = 1000000007;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    // var... 変数の識別子, $t...型を一つよむ
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        //ここで繰り返し
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    //
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    // 配列の最後のNestではここで型が指定されてparseされる
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// =========

fn main() {
    input! {
        a: usize,
        b: usize,
    }
    println!("{:?}", 6 - a - b);
}


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

namespace geometry {
	using Real = double;
	using Point = complex<Real>;
	constexpr Real EPS = 1e-9;
	struct Circle {
		Point p;
		Real r;
		Circle(const Point p, const Real r) : p(p), r(r) {}
	};
	struct Line {
		Point a, b;
		Line(const Point a, const Point b) : a(a), b(b) {}
	};
	// 内積
	inline Real dot(const Point& lhs, const Point& rhs) {
		return (conj(lhs) * rhs).real();
	}
	// 外積
	inline Real cross(const Point& lhs, const Point& rhs) {
		return (conj(lhs) * rhs).imag();
	}
	// 円の交点
	vector<Point> intersect(const Circle& c1, const Circle& c2) {
		const Real dist = abs(c1.p - c2.p);
		vector<Point> ret;
		if(dist > c1.r + c2.r) return ret;
		if(dist < abs(c1.r - c2.r)) return ret;
		const Real rc = (dist * dist + c1.r * c1.r - c2.r * c2.r) / (2 * dist);
		const Real rs = sqrt(c1.r * c1.r - rc * rc);
		const Point vec = (c2.p - c1.p) / dist;
		ret.emplace_back(c1.p + vec * Point(rc, rs));
		ret.emplace_back(c1.p + vec * Point(rc, -rs));
		return ret;
	}
	// a の b に対する正射影ベクトル
	inline Point projection(const Point& a, const Point& b) {
		return b * dot(a, b) / norm(b);
	}
	// 点pから直線lに下ろした垂線の足
	inline Point projection(const Line& l, const Point& p) {
		return projection(p - l.a, l.b - l.a) + l.a;
	}
	// 直線lを対称軸として点pと線対称な点
	inline Point reflection(const Line &l, const Point &p) {
		return p + (projection(l, p) - p) * 2.0;
	}
	// 反時計回り(a -> b -> c)
	static constexpr int COUNTER_CLOCKWISE = 0b00001;
	// 時計回り(a -> b -> c)
	static constexpr int CLOCKWISE = 0b00010;
	// 同一直線上(c -> a -> b)
	static constexpr int ONLINE_BACK = 0b00100;
	// 同一直線上(a -> b -> c)
	static constexpr int ONLINE_FRONT = 0b01000;
	// 同一直線上(a -> c -> b)
	static constexpr int ON_SEGMENT = 0b10000;
	// 3点の位置関係
	int ccw(const Point &a, Point b, Point c) {
		b = b - a, c = c - a;
		if(cross(b, c) > EPS) return COUNTER_CLOCKWISE;
		if(cross(b, c) < -EPS) return CLOCKWISE;
		if(dot(b, c) < 0) return ONLINE_BACK;
		if(norm(b) < norm(c)) return ONLINE_FRONT;
		return ON_SEGMENT;
	}


	// 直線の交点
	// Point intersect(const Line& l1, const Line& l2) {
	// 	const Point v1 = l1.p2 - l1.p1;
	// 	const Point v2 = l2.p2 - l2.p1;

	// }

	inline istream& operator>>(istream& is, Point& p) {
		Real x, y;
		is >> x >> y;
		p = Point(x, y);
		return is;
	}
	inline ostream& operator<<(ostream& os, const Point &p) {
		return os << fixed << setprecision(15) << p.real() << " " << p.imag();
	}
}

using namespace geometry;
int main() {
	Point p0, p1; cin >> p0 >> p1;
	int q; cin >> q;
	while(q--) {
		Point p2; cin >> p2;
		int ret = ccw(p0, p1, p2);
		string ans;
		if(ret & COUNTER_CLOCKWISE) ans = "COUNTER_CLOCKWISE";
		if(ret & CLOCKWISE) ans = "CLOCKWISE";
		if(ret & ONLINE_BACK) ans = "ONLINE_BACK";
		if(ret & ONLINE_FRONT) ans = "ONLINE_FRONT";
		if(ret & ON_SEGMENT) ans = "ON_SEGMENT";
		cout << ans << '\n';
	}
	return 0;
}


Measured memory_bytes: 3304
def func(x):
  if x==2:
    return True
  
  for i in range(2,x):
    if i*i > x:
      return True
    elif x%i == 0:
      return False
    else:
      continue

X=int(input())

while(True):
  if func(X):
    print(X)
    break
  else:
    X+=1

Measured memory_bytes: 2940
import bisect
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
ans = 0
for i in B:
    a = bisect.bisect_left(A, i)
    b = bisect.bisect_right(C, i)
    ans += a * (N - b)
print(ans)

Measured memory_bytes: 23360
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace _20170409_AOJ
{
    class Program
    {
        static void Main(string[] args)
        {
            double[] dArr = Console.ReadLine().Split(' ').Select(s => double.Parse(s)).ToArray();
            double x1 = dArr[0];
            double y1 = dArr[1];
            double x2 = dArr[2];
            double y2 = dArr[3];
            double d = Math.Sqrt(Math.Pow(x2 - x1, 2) + Math.Pow(y2 - y1, 2));

            Console.WriteLine(d);

            Console.ReadLine();
        }
    }
}

Measured memory_bytes: 9736
import numpy as np
S = input()
K = int(input())
seq = []
init = 1
def seq_count(strings, lst):
    init = 1
    for i in range(len(strings)-1):
        if strings[i] == strings[i+1]:
            init += 1
        else:
            lst.append(init)
            init = 1
    lst.append(init)
seq_count(S, seq)
if S[0] != S[-1]:
    array = np.array(seq)
    ans = array // 2
    print(int(np.sum(ans))*K) 
else:
    seq2 = seq[1:-1]
    array = np.array(seq2)
    part_ans = array // 2
    if len(seq) > 1:
        print(int(np.sum(part_ans))*K+((seq[0]+seq[-1])//2)*(K-1)+(seq[0]//2)+(seq[-1]//2))
    else:
        print((seq[0]*K)//2)

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

#define MP make_pair
#define PB push_back
#define ALL(x)      (x).begin(),(x).end()
#define REP(i,n)    for(int i=0;i<(n);i++)
#define REP1(i,n)   for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n)   for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};


void solve(long long N, long long M, std::vector<long long> A){
    priority_queue<LL> memo;
    REP(i, N) {
        memo.push(A[i]);
    }

    REP(i, M) {
        LL x = memo.top();
        memo.pop();
        memo.push(x/2);
    }

    LL ans = 0;
    while(!memo.empty()) {
        ans += memo.top();
        memo.pop();
    }

    cout << ans << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    solve(N, M, std::move(A));
    return 0;
}



Measured memory_bytes: 2168
from collections import Counter as D, defaultdict as dd
from math import factorial as ft, ceil as aron, log
from fractions import gcd as pg 
from bisect import insort as ins, bisect_left as bl, bisect_right as br
import sys

#sys.stdin=open("./testfile1.py","r")
raw_input=sys.stdin.readline

f1=lambda : map(int,raw_input().split())
f2=lambda : map(int,list(raw_input()))
f3=lambda : int(raw_input())
f4=lambda : raw_input().rstrip()
f5=lambda : raw_input().split()


def main():
    a=f1()
    a.sort()
    print sum(a[:2])
    


if __name__ == '__main__':
	main()

Measured memory_bytes: 34792
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int Mod=1e9+7;

int n,c[200010],nxt[200010],lst[200010];
int dp1[200010],dp2[200010];
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",c+i);
	int tmp=0;
	for (int i=1;i<=n;i++) if (i==1||c[i]!=c[i-1]) c[++tmp]=c[i];
	n=tmp;
	for (int i=1;i<=n;i++) nxt[i]=lst[c[i]],lst[c[i]]=i;
	dp1[0]=1;
	for (int i=1;i<=n;i++)
	{
		dp1[i]=dp1[i-1];
		if (nxt[i])
		{
//			printf("nxt %d is %d\n",)
			dp1[i]=(dp1[i]+dp2[nxt[i]])%Mod;
			dp2[i]=dp2[nxt[i]];
		}
		dp2[i]=(dp2[i]+dp1[i-1])%Mod;
//		printf("dp1 %d = %d   %d\n",i,dp1[i],dp2[i]);
	}
	printf("%d\n",dp1[n]);
	return 0;
}

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

using namespace std;

int main(int argc, char* argv[])
{
  int row, line, input,result;
  cin >> row >> line;
  vector<vector<int>> matrix1(row);
  vector<int> matrix2;
  for(int i=0;i<row;i++)
  {
    for(int j=0;j<line;j++)
    {
      cin >> input;
      matrix1[i].push_back(input);
    }
  }
  for(int i=0;i<line;i++)
  {
    cin >> input;
    matrix2.push_back(input);
  }
  for(int i=0;i<row;i++)
  {
    result = 0;
    for(int j=0;j<line;j++)
    {
      result+=matrix1[i][j]*matrix2[j];
    }
    cout << result << endl;
  }
}

Measured memory_bytes: 3184
#include <iostream>
#include <string>
#include <math.h>
using namespace std;
int check_text (string s, char x) ;
int main() {
    int a , b , x ;
    cin >> a >> b >> x ;
    if (x >= a && b >= (x-a)){
        cout << "YES" ;
    }
    else {
        cout << "NO" ;
    }
    return 0 ;
}


Measured memory_bytes: 3652
S=input()
s0=""
s1=""
for i in range(len(S)):
  if i%2==0:
    s0+="0"
    s1+="1"
  else:
    s0+="1"
    s1+="0"

s0c=0
s1c=0
for i in range(len(S)):
  if S[i]!=s0[i]:
    s0c+=1
  if S[i]!=s1[i]:
    s1c+=1
    
print(min(s0c,s1c))


Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
#define nl cout<<'\n';

int main()
{
    string e="Yes",n="No";
    int x,y;
    cin>>x>>y;
    for(int i=0; i<=100; i++)
    {
        for(int j=0;j<=100;j++)
        {
           if(i+j!=x)
            continue;
           if(i*2+j*4==y)
           {
              cout<<e;
              nl;
              return 0;
           }
        }
    }
    cout<<n;
    nl;
    return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;

main() {
  string s;
  cin >> s;
  
  int64_t n = s.size();
  auto r = irange(1L, n + 1);
  auto ans = *partition_point(r.begin(), r.end(), [&](int64_t k) {
    if (k <= n / 2) {
      return true;
    }

    auto c = s[n - k];
    for (auto i : irange(n - k, k)) {
      if (s[i] != c) {
        return false;
      }
    }
    
    return true;
  }) - 1;
  
  cout << ans << endl;
}

Measured memory_bytes: 512
s = gets.chomp.chars

ans_a = ans_b = 0

s.size.times do |i|
  c = s[i].to_i
  ans_a += 1 if i.even? && c == 0 || i.odd? && c == 1
  ans_b += 1 if i.even? && c == 1 || i.odd? && c == 0
end

puts ans_a <= ans_b ? ans_a : ans_b


Measured memory_bytes: 6908
#include <bits/stdc++.h>
#include <iomanip>
#define ll long long
using namespace std;
 
int main() {
  ll N;
  cin >> N;
  
  vector<ll> d(N);
  
  for(ll i = 0; i < N; i++) cin >> d.at(i);
  
  sort(d.begin(), d.end());

  if(N % 2 != 0) cout << 0 << endl;
  else {
    if(d.at(N / 2) == d.at(N / 2 - 1)) cout << 0 << endl;
    else cout << d.at(N / 2) - d.at(N / 2 - 1) << endl;
  }
}

Measured memory_bytes: 1024