akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Linq;

public class Program
{
    static void Main()
    {
        long n = long.Parse(Console.ReadLine());
        for (int i = (int)Math.Sqrt(n); i >= 1; i--)
        {
            if (n % i == 0)
            {
                Console.WriteLine(n / i + i - 2);
                return;
            }
        }
    }
}

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

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

using namespace std;

int main(){
  ll x,y;
  cin>>x>>y;
  
  if(x==1 && y==1){
    cout<<1000000;
    return 0;
  }
  ll money = 0;
  if(x==1)money+= 300000;
  if(x==2)money+= 200000;
  if(x==3)money+= 100000;
  if(y==1)money+= 300000;
  if(y==2)money+= 200000;
  if(y==3)money+= 100000;

  cout<<money;
  return 0;
}

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

using namespace std;
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define PB(x, v) x.push_back(v);
#define M_P(a, b) make_pair(a, b)
#define pll pair<ll, ll>
#define ll long long
#define mll map<ll, ll>
#define vl vector<ll>
#define fa(x, v) for(auto x: v)
#define fr(i, a, b) for(int i= a;i <=b; i++)
#define TEST  ll Test; cin >> Test; while(Test--)

#define B_ begin()
#define E_ end()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define NL_ "\n"
#define F first
#define S second
#define FF first.first
#define FS first.second
#define SF second.first
#define SS second.second

#define mod(a) a%1000000007
#define MAX 2000000000
#define  ull unsigned long long

void solve()
{
   ll a, b;
   cin>> a >> b;
   if(a< b) swap(a, b);
   ll r= a - b;
   if(!r) {cout << 0<<NL_; return ;}
   ll i =1;
   while(true)
   {
       ll t = i*(i+1)/2;
       if((t-r)%2==0 and t-r>=0)
       {
           cout << i <<NL_;
           return ;
       }
       i++;
   }
}

bool check(ll n)
{
    if(n==2)
        return 1;
    for(ll i = 2; i*i<=n; i++)
    {
        if(n%i==0)
            return 0;
    }
    return 1;

}

int main()
{

    FAST;
    ll n;
    cin >> n;
    ll sum =0;
    ll r;
    ll mx =-1;
    fr(i, 1, n)
    {
        cin >> r;
        if(r<mx) sum+=mx-r;
        mx = max(r, mx);
    }

    cout << sum;



    return 0;
}


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

constexpr int inf = 0x3f3f3f3f;
constexpr ll linf = 0x3f3f3f3f3f3f3f3fLL;

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

    int h, w; cin >> h >> w;
    ll ans = linf;
    for (int i = h / 3; i <= h / 3 + 1; i++) {
        ll fi = (ll)i * w;
        ll rest = (ll)h * w - fi;
        ll se;
        if (rest % 2 == 0) se = rest / 2;
        else se = (ll)max(h - i, w) / 2 * min(h - i, w);
        ll th = rest - se;
        ans = min(ans, max({fi, se, th}) - min({fi, se, th}));
    }
    for (int i = w / 3; i <= w / 3 + 1; i++) {
        ll fi = (ll)i * h;
        ll rest = (ll)h * w - fi;
        ll se;
        if (rest % 2 == 0) se = rest / 2;
        else se = (ll)max(h, w - i) / 2 * min(h, w - i);
        ll th = rest - se;
        ans = min(ans, max({fi, se, th}) - min({fi, se, th}));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
# Aizu Problem ITP_1_6_B: Finding Missing Cards
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


cards = {s: set(range(1, 14)) for s in ['D', 'H', 'C', 'S']}
N = int(input())
for _ in range(N):
    suit, face = input().split()
    face = int(face)
    cards[suit].remove(face)

for suit in ['S', 'H', 'C', 'D']:
    for face in cards[suit]:
        print(suit, face)

Measured memory_bytes: 7728
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long ll;

int N;
int a, b, c, d, e, f;

ll W[6], V[6];

ll dp[6][5000 * 5000 + 100];
ll limit[5000 * 5000 + 100];

int main() {
	cin >> N >> a >> b >> c >> d >> e >> f;
	//交換レートを荷物に変換
	//前半三種類はA->B 後半三種類はB->Aに相当
	W[0] = a, V[0] = d;
	W[1] = b, V[1] = e;
	W[2] = c, V[2] = f;
	W[3] = d, V[3] = a;
	W[4] = e, V[4] = b;
	W[5] = f, V[5] = c;
	//初期条件更新
	for (int j = 0; j * W[0] <= N; j++) {
		dp[0][j * W[0]] = V[0] * j;

	}
	//limitとは、A->Bの時に得られたどんぐりの数の最大値で、B->Aの時のNの代わりのDPの上限となる
	//その値はたかだか2500^2
	ll limit = N;

	//個数制限なしナップサック前半
	for (int i = 1; i < 3; i++) {
		for (int j = 0; j <= N; j++) {
			if (j >= W[i]) {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - W[i]] + V[i]);
			}
			else dp[i][j] = dp[i - 1][j];
			if(i == 2)limit = max(limit, dp[i][j] + (N - j));
		}
	}
	//後半の個数制限ナップサックの初期条件の更新
	//Nのところをlimitに差し替えてる
	for (int j = 0; j * W[3] <= limit; j++) {
		dp[3][j * W[3]] = V[3] * j;
	}
	//後半の個数制限ナップサック
	for (int i = 4; i < 6; i++) {
		for (ll j = 0; j <= limit; j++) {
			if (j - W[i] >= 0)dp[i][j] = max(dp[i - 1][j], dp[i][j - W[i]] + V[i]);
			else dp[i][j] = dp[i - 1][j];
		}
	}

	ll ans = 0;
	for (ll i = 0; i <= limit; i++)ans = max(ans, dp[5][i] + (limit - i));
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 593280
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;

int main(){
    long long x, t;
    cin >> x >> t;
    long long left = x-t;
    if(left < 0){
        left = 0;
    }
    cout << left << endl;
    return 0;
}

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

int main()
{
    int A, B, C, X;
    cin >> A >> B >> C >> X;

    int count = 0;
    for (size_t i = 0; i <= A; i++)
    {
        for (size_t j = 0; j <= B; j++)
        {
            for (size_t k = 0; k <= C; k++)
            {
                if (500 * i + 100 * j + 50 * k == X)
                {
                    count++;
                }
            }
        }
    }

    cout << count << endl;
}


Measured memory_bytes: 3668
from __future__ import print_function

import sys

import re
import array
import copy
import functools
import operator

import math
import string
import fractions
from fractions import Fraction
from fractions import gcd
# fractions.gcd() を用いること
# math.log2()はatcoderでは対応していない．留意せよ．

import collections
import itertools
import bisect

import random
import time

import heapq
from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace
from queue import PriorityQueue as pq
from queue import Queue

from itertools import accumulate

from collections import deque
from collections import Counter

from operator import mul
from functools import reduce

input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return


def lcm(n, m):
    return int(n * m / gcd(n, m))


def coprimize(p, q):
    common = fractions.gcd(p, q)
    return (p // common, q // common)


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    S = input().strip()
    l = -1
    for i in range(len(S)):
        if S[i] == "A":
            l = i
            break
    for i in range(len(S)):
        if S[-(i+1)] == "Z":
            r = len(S)-i
            break
    print(r-l)


if __name__ == '__main__':
    main()


Measured memory_bytes: 61676
#include<iostream>
using namespace std;
int main(void) {
	int a, b;
	cin >> a >> b;
	if (a > b)cout << 2 * a - 1 << endl;
	else if (a < b) cout<<2 * b - 1 << endl;
	else cout << 2 * a << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i;
    long long a[101];
    a[0]=2;
    a[1]=1;
    cin>>n;
    for(i=2;i<=n;i++)
    a[i]=a[i-1]+a[i-2];
    cout<<a[n];
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include<stack>
#include <queue>
#include<map>
#include <set>
#include<math.h>
using namespace std;
#define int long long
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define loop(i,m,n) for(ll i=m;i<n;++i)
#define ggr getchar(); getchar();return 0;
#define pie 3.141592653589793238462643383279
#define elif else if
#define P pair<ll,ll>
const int inf = 1000000007;
int bin(int bina) {
	int ans = 0;
	for (int i = 0; bina > 0; i++)
	{
		ans = ans + (bina % 2) * pow(10, i);
		bina = bina / 2;
	}
	return ans;
}
bool prime(int n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1) * x % inf;
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	return kai(x)* mod_pow(kai(x - y), inf - 2, inf) % inf * mod_pow(kai(y), inf - 2, inf) % inf;
}
struct union_find {
	int par[200010], size_[200010];
	void init(int x) {
		rep(i, x) { par[i] = i; size_[i] = 1; }
	}
	int find(int x) {
		if (par[x] == x)return x;
		return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y)return;
		if (size_[x] < size_[y]) {
			par[x] = y;
			size_[y] += size_[x];
		}
		else {
			par[y] = x;
			size_[x] += size_[y];
		}
	}
};
int n;
vector<int>v[100010];
int d[100010], da[100010];
bool b[100010], ba[100010];
void dfs(int a) {
	b[a] = true;
	rep(i, v[a].size()) {
		if (!b[v[a][i]]) {
			d[v[a][i]] = d[a] + 1;
			dfs(v[a][i]);
		}
	}
}
void dfs2(int a) {
	ba[a] = true;
	rep(i, v[a].size()) {
		if (!ba[v[a][i]]) {
			da[v[a][i]] = da[a] + 1;
			dfs2(v[a][i]);
		}
	}
}
signed main() {	
	cin >> n;
	rep(i, n - 1) {
		int a, c;
		cin >> a >> c;
		a--;
		c--;
		v[a].push_back(c);
		v[c].push_back(a);
	}
	dfs(0);
	dfs2(n - 1);
	int ans = 0, ans2 = 0;
	rep(i, n) {
		if (d[i] > da[i]) {
			ans2++;
		}
		else ans++;
	}
	if (ans > ans2) {
		cout << "Fennec" << endl;
	}
	else cout << "Snuke" << endl;
}

Measured memory_bytes: 12160
N, K = map(int, input().split())
S = list(input())
S = list(map(int, S))
s = []
tmp = 0

for i in range(N):
    if S[i] == 1:
        if tmp != 0:
            s.append((tmp, i-1))
        tmp = 0
    else:
        tmp += 1
        if i == N-1:
            s.append((tmp, i))
if len(s) <= K:
    print(N)
    exit(0)
ans = 0
for i in range(len(s)-K+1):
    tmp = 0
    if i+K == len(s):
        tmp = N-1
    else:
        tmp = s[i+K][1]-s[i+K][0]

    if i != 0:
        tmp -= s[i-1][1]
    else:
        tmp += 1
    ans = max(ans, tmp)

print(ans)


Measured memory_bytes: 8960
#include <stdio.h>

int main(void)
{
  int N;
  scanf("%d",&N);
  int j,min,max;

  for(int i=1;i<=N;i++)
  {
    scanf("%d",&j);

    if(i==1)
    {
      max=j;
      min=j;
    }
    if(max<j)
    {
        max=j;

    }
    if(min>j)
    {
      min=j;
    }
  }
  printf("%d",(max-min));
}


Measured memory_bytes: 128
<?php
$input = trim(fgets(STDIN));
list($x_num, $y_num, $x, $y) = explode(' ', $input);
$input = trim(fgets(STDIN));
$xs = explode(' ', $input);
$input = trim(fgets(STDIN));
$ys = explode(' ', $input);

foreach(range($x+1, $y-1) as $z) {
    $ok = true;
    foreach($xs as $xn) {
        if($xn >= $z) {
            $ok = false;
        }
    }
    foreach($ys as $yn) {
        if($yn < $z) {
            $ok = false;
        }
    }

    if($ok) {
        echo 'No War';
        exit;
    }
}

echo 'War';


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

int main(){
  int a,b;
  cin >> a >> b;
  if(a==1)
    a=20;
  if(b==1)
    b=20;
  if(a>b)
    cout << "Alice" << endl;
  else if(a==b)
    cout << "Draw" << endl;
  else
    cout << "Bob" << endl;
}

Measured memory_bytes: 384
// ?????¬???????????¬??????

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long int

template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}

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

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
constexpr ll INF = 1001001001001001LL;
constexpr ll MOD = 1000000007LL;
constexpr double EPS = 1e-8;

double dp[1 << 12][12];

signed main() {
    string s;
    while(getline(cin, s)) {
        double W;
        stringstream ss(s);
        ss >> W;

        vector<int> v;
        int N, val;
        while(ss >> val) {
            v.push_back(val);
        }

        N = v.size();
        rep(i,0,1<<N) rep(j,0,N) dp[i][j] = INF;
        dp[0][0] = 0;

        rep(bit,0,1<<N) rep(i,0,N) {
            if(dp[bit][i] == INF) continue;
            rep(k,0,N) {
                if(bit >> k & 1) continue;
                int nbit = bit | (1 << k);
                if(__builtin_popcount(nbit) == 1) {
                    dp[nbit][k] = v[k] * 2;
                }
                else {
                    chmin(dp[nbit][k], dp[bit][i] + 2 * sqrt(v[i] * v[k]) - v[i] + v[k]);
                }
            }
        }

        bool ok = false;
        rep(i,0,N) {
            if(dp[(1<<N)-1][i] <= W + EPS) {
                cout << "OK" << endl;
                ok = true;
                break;
            }
        }
        if(!ok) cout << "NA" << endl;
    }
    return 0;
}

Measured memory_bytes: 3672
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int[] f = new int[n];

		for (int i = 0; i < f.length; i++) {
			int tmp = 0;
			for (int j = 0; j < 10; j++) {
				tmp = tmp << 1;
				tmp += sc.nextInt();
			}
			f[i] = tmp;
		}

		int[][] p = new int[n][11];
		for (int i = 0; i < p.length; i++) {
			for (int j = 0; j < p[i].length; j++) {
				p[i][j] = sc.nextInt();
			}
		}
		int max = Integer.MIN_VALUE;
		for (int i = 1; i < 1 << 10; i++) {
			int profit = 0;
			for (int j = 0; j < p.length; j++) {
				profit += p[j][Integer.bitCount(i & f[j])];
			}
			if (profit > max) {
				max = profit;
			}
		}

		System.out.println(max);

		sc.close();
	}

}


Measured memory_bytes: 26072
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define FAST ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define dofloat cout<<fixed<<setprecision(8)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define bitcount _builtin_popcount
#define all(vec) vec.begin(),vec.end()
#define rall(vec) vec.rbegin(),vec.rend()
using namespace __gnu_pbds;
using namespace std;
//typedef
typedef long long ll;
typedef long double ld;
typedef vector<long long> vl;
typedef pair<long long,long long> pll;
typedef vector<pair<long long,long long> > vll;
typedef vector<pair<int,int> > vii;
typedef vector<int> vi;
typedef pair<int,int> ii;
//constants
const long long MOD=1000000007;
const long long MAX=100005;
const long double PI=3.14159265359;
const long double G=9.807;
const long long INF=1e18;
const long double EPS=1e-6;
// gcd of a and b
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
// distance between (a,b) and (c,d)
long double dis(long long a,long long b,long long c,long long d){return sqrt( ((a)-(c))*((a)-(c))+((b)-(d))*((b)-(d)) );}
// simple prime check
bool isprime(long long a){
if(a==2)return 1;
if(!(a&1))return 0;
for(ll i=3;i*i<=a;i+=2){
	if(a%i==0)return 0;
}
return 1;
}
// fast expo
long long mpow(long long base,long long exponent,long long modulus){
if(modulus==1)return 0;
long long result = 1;
base=base%modulus;
while(exponent){
		if(exponent%2 == 1)
			result=(result*base)%modulus;
		exponent=exponent>>1;
		base=(base*base)%modulus;
	}
return result;
}
// modular inverse
ll minv(ll a,ll mod){
	ll _gcd=gcd(a,mod);
	assert(_gcd==1);
	return mpow(a,mod-2,mod);
}

/*
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/

/*
ll dx[]={1,0,-1,0,1,1,-1,-1};
ll dy[]={0,-1,0,1,1,-1,-1,1};
*/

/*
void sieve(int N){
	for(int i=0;i<=N;i++){
		spf[i]=i;
	}
	for(int i=2;i*i<=N;i++){
		if(spf[i]==i){
			for(int j=i*i;j<=N;j+=i){
				spf[j]=min(spf[j],i);
			}
		}
	}
	return;
}
*/

/*
void nCr(ll n,ll k){
	ll i,j;
	for(i=0;i<=n;i++){
		for(j=0;j<=min(i,k);j++){

			if(j==0 or j==i)C[i][j]=1LL;
			else  C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;

		}
	}
	return;
}
*/
/*
ll ncr(ll N,ll K){
	if(N<K)return 0;
	if(K==0)return 1;
	if(N==0)return 0;

	ll den=1;
	for(ll i=1;i<=K;i++)den*=i;
	ll num=1;
	while(K--){
		num*=N;
		if(num%den==0){
			num/=den;
			den=1;
		}
		N--;
	}

	return num;
}
*/
ll n;
ll m;
vll shop;
int main(){FAST;

cin>>n>>m;

for(ll i=0;i<n;i++){
	ll x,y;cin>>x>>y;
	shop.pb({x,y});
}

sort(all(shop));

ll ans=0;

for(ll i=0;i<n;i++){
	ll del=min(m,shop[i].se);
	ans+=del*shop[i].fi;
	m-=del;
}
cout<<ans;
return 0;
}


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

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

const int INF = 1e9;
const int mod = 1e9+7;

int main()
{
    int n;
    cin >> n;
    int a[n+10];
    for(int i = 0; i < n; i++) cin >> a[i];
    
    ll front[n+10],back[n+10],ans = 1e18;
    front[0] = a[0],back[n-1] = a[n-1];
    for(int i = 1; i < n; i++) front[i] = front[i-1] + a[i];
    for(int i = n-2; i >= 0; i--) back[i] = back[i+1] + a[i];
    for(int i = 0; i < n-1; i++) ans = min(ans,abs(front[i]-back[i+1]));

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4096
let pair f s = s |>
               Str.split (Str.regexp " ") |>
               List.map f |>
               (function | [a; b] -> (a, b)
                         | _ -> failwith "invalid input")

let box (h, w) =
  let rec rows i acc =
    let row = (String.make w '#') ^ "\n" in
    if i > 0 then rows (i-1) (row :: acc) else acc in
  String.concat "" (rows h [])

let rec loop () =
  match read_line () with
  | "0 0" -> ()
  | line -> loop (print_endline (box (pair int_of_string line)))

let () = loop ()

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

int main() {

  int N , M ;
  cin >> N >> M ;
  int ans = 0 ;
  while( N > 0 ){
    N /= M ;
    ans++ ;
  }
  cout << ans << endl;
}

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

#define int long long

int N, X;

int Solve(int a, int b)
{
	if (b == 0) return -a;
	return (a/b)*b*2 + Solve(b, a % b);
}

signed main()
{
	cin >> N >> X;
	printf("%lld\n", N + Solve(N - X, X));
	return 0;
}

Measured memory_bytes: 256
import numpy as np

H,W = [int(i) for i in input().split()]

s=[]

for i in range(H):
    s.append(str(input()))
    
# s[i][0] to s[i][W-1] 

pat_mat=[]

for i in range(H):
    if i ==0:
        if s[0][0] == ".":
            pat_mat.append([0])
        else:
            pat_mat.append([1])
        if W>1:
            for j in range(1,W):
                if s[0][j] == ".":
                    pat_mat[0].append(pat_mat[0][j-1])
                else:
                    if s[0][j-1]==s[0][j]:
                        pat_mat[0].append(int(pat_mat[0][j-1]))
                    else:
                        pat_mat[0].append(int(pat_mat[0][j-1]+1))
    else:
        if s[i][0] == ".":
            pat_mat.append([pat_mat[i-1][0]])
        else:
            if s[i-1][0]==s[i][0]:
                pat_mat.append([pat_mat[i-1][0]])
            else:
                
                pat_mat.append([pat_mat[i-1][0]+1])
        if W>1:
            for j in range(1,W):
                if s[i][j] == ".":
                    pat_mat[i].append(min(pat_mat[i][j-1],pat_mat[i-1][j]))
                else:
                    if s[i][j-1]==s[i][j]:
                        cand_l = pat_mat[i][j-1]
                    else:
                        cand_l = pat_mat[i][j-1]+1
                    if s[i][j]==s[i-1][j]:
                        cand_t= pat_mat[i-1][j]
                    else:
                        cand_t= pat_mat[i-1][j]+1

                    pat_mat[i].append(min(cand_l,cand_t))
                        
                    
print(int(pat_mat[H-1][W-1]))

Measured memory_bytes: 14436
#include <bits/stdc++.h>
#define N 1000000007
using namespace std;

string s;
int d;
//桁番号、less、あまり
// 1はs以下確定、0は未確定
long long dp[10001][2][100] = {0};

int main() {
  cin >> s >> d;
  dp[0][0][0] = 1;
  for(int i = 1; i <= s.size(); ++i) {
    for(int j = 0; j < d; ++j) {
      for(int k = 0; k < 10; ++k) {
        // i桁目の数字をkにしたときに、それが指定された数字のi桁目の数字
        //より大きいか小さいか
        if(k < s[i - 1] - '0')
          dp[i][1][(j + k) % d] +=
              (dp[i - 1][1][j] + dp[i - 1][0][j]) % N;
        else if(k == s[i - 1] - '0') {
          dp[i][1][(j + k) % d] += dp[i - 1][1][j];
          dp[i][0][(j + k) % d] += dp[i - 1][0][j];
        }
        else
          dp[i][1][(j + k) % d] += dp[i - 1][1][j];
        dp[i][1][(j + k) % d] %= N;
        dp[i][0][(j + k) % d] %= N;
      }
    }
  }
  // 0が含まれているので０を排除
  cout << (N+dp[s.size()][1][0] + dp[s.size()][0][0] - 1) % N
       << endl;
  return 0;
}


Measured memory_bytes: 15872
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll,ll> P;
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 M 1000000007
#define all(a) (a).begin(),(a).end()
#define rep(i,n) reps(i,0,n)
#define reps(i,m,n) for(int i=(m);i<(n);i++)
int main(){
  int n;string s;
  cin>>n>>s;
  int c=0;
  rep(i,n-2){
    if(s.substr(i,3)=="ABC")c++;
  }
  cout<<c;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
#define what_is(x) cerr << #x << " is " << x << endl;
#define ll long long
#define int long long
#define ld double
#define pii pair<int,int>
#define rand() abs((rand()<<15)|rand())
#define randll() abs(((long long)rand()<<30)|rand())
const int MOD = 1'000'000'007;

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	long long seed;
	asm("rdtsc" : "=A"(seed));
	srand(seed);

	int n;
	cin >> n;
	vector<int> a(n);
	for(auto &x: a)
		cin >> x;
	int ans = 0;
	int cnt = 1;
	for(int i = 1; i < n; i++) {
		if(a[i]==a[i-1]) cnt++;
		else {
			ans+=cnt/2;
			cnt=1;
		}
	}
	ans += cnt/2;
	cout << ans << endl;
}

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

#define int long long int
#define mp make_pair
using namespace std;

string s,t;
int dp[3002][3002];
int l1 ,l2;
int fun(int pos1 , int pos2)
{
    if(pos1 == l1){
        return 0;
    }
    if(pos2 == l2){
        return 0;
    }
    if(dp[pos1][pos2] != -1){
        return dp[pos1][pos2];
    }
    if(s[pos1] == t[pos2]){
        dp[pos1][pos2] = 1 + fun(pos1 + 1 , pos2 + 1);
    }
    else{
        dp[pos1][pos2] = max(fun(pos1 + 1 , pos2) , fun(pos1 , pos2 + 1));
    }
    return dp[pos1][pos2];
}

void path(int i , int j)
{
    if(i == l1){
        return ;
    }
    if(j == l2){
        return ;
    }
    if(s[i] == t[j]){
        cout << s[i];
        path(i+1 , j+1);
    }
    else{
        if(dp[i+1][j] > dp[i][j+1]){
            path(i + 1 , j);
        }
        else{
            path(i , j+1);
        }
    }
    return ;
}

int32_t main() {
    cin >> s >> t;
    l1 = s.length();
    l2 = t.length();
    for (int i = 0; i < 3002; ++i) {
        for (int j = 0; j < 3002; ++j) {
            dp[i][j] = -1;
        }
    }
    int ans1 = fun(0,0);
    path(0 , 0);
    return 0;
}

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

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SUM(a) accumulate(all(a), 0LL)
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define FOR(i, m, n) for(int (i)=(m); (i)<(n); i++)
#define FORR(i, m, n) for(int (i)=(n)-1; (i)>=(m); i--)
#define debug(x) cerr << #x << " = " << x << endl
//#define int long long

typedef long long ll;
//ll const MOD = 998244353;
ll const MOD = 1e9+7;
int const inf = 1e9;
ll const INF = 1e18;

inline void ios_(){cin.tie(0); ios::sync_with_stdio(false);}
template<typename T> int size(const T& a){return (int)a.size();}
template<typename T> T Div(T a, T b){return (a + b - 1) / b;}
template<typename T> bool chmin(T& a, const T& b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, const T& b){if(a < b){a = b; return true;} return false;}



signed main(){
    int n;
    cin >> n;
    vector<int> v(n);
    for(auto& i : v) cin >> i;

    sort(all(v));

    cout << v[n/2] - v[n/2 - 1] << endl;
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REPL(i,0,n)
#define all(v) v.begin(), v.end()
// template<class t, class u>
// ostream& operator<<(ostream& os, const pair<t, u>& p) {
//   return os << "{" << p.first << ", " << p.second << "}";
// }
// template<class t> ostream& operator<<(ostream& os, const vector<t>& v) {
//   os << "{";
//   rep(i, v.size()) { if(i) os << ", "; os << v[i]; }
//   return os << "}";
// }
// template<class t> ostream& operator<<(ostream& os, const set<t>& se) {
//   os << "{";
//   auto itr = se.begin();
//   rep(i, se.size()) { if(i) os << ", "; os << *itr; itr++; }
//   return os << "}";
// }
// template<class t, class u>
// ostream& operator<<(ostream& os, const map<t, u>& mp) {
//   os << "{";
//   auto itr = mp.begin();
//   rep(i, mp.size()) { if(i) os << ", "; os << *itr; itr++; }
//   return os << "}";
// }
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {

  vector< vector<ll> > A;
  REP(i, 0, 3) {
    vector<ll> a;
    ll temp;
    REP(j, 0, 3) {
      cin >> temp;
      a.push_back(temp);
    }
    A.push_back(a);
  }
  ll N;
  cin >> N;
  vector<ll> b;
  ll temp;
  REP(i, 0, N) {
    cin >> temp;
    // b.push_back(temp);
    // pick number
    REP(j, 0, 3) {
      REP(k, 0, 3) {
        if (temp == A[j][k]) {
          A[j][k] = 0;
        }
      }
    }
  }

  // check bingo
  // ll ans_ = 1; // 1 is bingo
  // REP(i, 0, 3) {
  //   ll bingo = 1; // 1 is bingo
  //   REP(j, 0, 3) {
  //     if (A[i][j] != 0) {
  //       bingo = 0; // 0 is not bingo
  //     }
  //   }
  //   if (bingo == 0) {
  //     ans_ = 0;
  //   }
  // }

  ll ans_ = 0; // 0 is no bingo
  REP(i, 0, 3) {
    ll sum = 0;
    REP(j, 0, 3) {
      sum += A[i][j];
    }
    if (sum==0) {
      ans_ = 1;
      break;
    }
  }
  REP(j, 0, 3) {
    ll sum = 0;
    REP(i, 0, 3) {
      sum += A[i][j];
    }
    if (sum==0) {
      ans_ = 1;
      break;
    }
  }
  if (A[0][0] + A[1][1] + A[2][2] == 0) {
    ans_ = 1;
  }
  if (A[2][0] + A[1][1] + A[0][2] == 0) {
    ans_ = 1;
  }

  if (ans_ == 0) {
    cout << "No" << endl;
  }
  else {
    cout << "Yes" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
b = [0] * n
for i in range(n):
    count = 0
    multi = 1
    if n - i == 0:
        count = sum(b)
    else:
        while (n - i) * multi <= n:
            count += b[(n - i) * multi - 1]
            multi += 1
    if count % 2 != a[n - i - 1]:
        b[n - i - 1] += 1
print(sum(b))
if sum(b) == 0:
    exit()
for i in range(n):
    if b[i] == 1:
        print(i + 1, end=' ')

Measured memory_bytes: 7248
import java.util.Scanner

object Main extends App {
  val sc = new Scanner(System.in)

  val mod = 1000L * 1000L * 1000L + 7

  val m, n = sc.nextInt

  println(solve(m, n))

  def solve(m: Int, n: Int): Long = {
    val mc = p(m)
    val nc = p(n)

    (m, n) match {
      case _ if m == n + 1 || m + 1 == n =>
        (mc * nc) % mod
      case _ if m == n => (((mc * nc) % mod) * 2) % mod
      case _ => 0L
    }
  }

  def p(i: Int): Long = {
    Range(1, i + 1)
      .map(_ * 1L)
      .reduce((a, b) => (a * b) % mod)
  }
}


Measured memory_bytes: 40572
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < n; i++)

using namespace std;

int main(void) {
  string S;
  cin >> S;
  long foo = 0;
  long bar = 0;
  rep (i, S.size()) {
    char current = S[i];
    char expected = i % 2 ? '0' : '1';
    if (current == expected) foo++;
    else bar++;
  }
  cout << min(foo, bar) << endl;
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>*/
 
#define pb push_back
#define mp make_pair
#define sz(s) ((int)(s.size()))
#define all(s) s.begin(), s.end()
#define rep(i, a, n) for (int i = a; i <= n; ++i)
#define per(i, n, a) for (int i = n; i >= a; --i)
#define onlycin ios_base::sync_with_stdio(false); cin.tie(0) 
using namespace std;
// using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
/*typedef tree<
pair < int, int >,
null_type,
less< pair < int, int > >,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;*/
// find_by_order() order_of_key()
const int MAXN = (int)5e5+228;
const char nxtl = '\n';
const int mod = (int)1e9+7;
const double eps = (double)1e-7;
template<typename T> inline bool updmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
template<typename T> inline bool updmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}

int k, d[MAXN];

void solve() {
	cin >> k;
	rep(i, 0, k) d[i] = mod;
	set < pair < int, int > > S;
	rep(i, 1, min(9, k)) {
		d[i] = i;
		S.insert(mp(d[i], i));
	}
	while(!S.empty()) {
		int v = S.begin()->second; S.erase(S.begin());
		rep(dig, 0, 9) {
			int u = (v * 10ll + dig) % k;
			if(d[u] > d[v] + dig) {
				S.erase(mp(d[u], u));
				d[u] = d[v] + dig;
				S.insert(mp(d[u], u));
			}
		}
	}
	cout << d[0] << nxtl;
}

int main() {
	#ifdef accepted
		freopen(".in", "r", stdin);
		freopen(".out", "w", stdout);
	#endif
	onlycin;
	solve();
	return 0;
	int score, t; cin >> score >> t;
	rep(i, 1, t) solve();
	/*unsigned int FOR;
	asm("rdtsc" : "=A"(FOR));
	srand(FOR);
	cout << 49 << ' '<< 10 << nxtl;
	int len = rand() % 10000 + 90001;
	rep(i, 1, len) cout << (char)((i - 1) % 26 + 'a');
	cout << nxtl;
	rep(ii, 2, 10) {
		int len = rand() % 10000 + 90001;
		rep(i, 1, len) cout << (char)(rand() % 26 + 'a');
		cout << nxtl;
	}*/

	return 0;
}


Measured memory_bytes: 4480
#include <bits/stdc++.h>
#include <vector>
#include <string>
#include <map>
using namespace std;

int main(){
  long N,M;
  cin >> N >> M;
  long counter = 0;
  
  vector<vector<long>> data(N,vector<long>(2));
  
  for(int i = 0;i < N;i++){
    cin >> data[i][0] >> data[i][1];
  }

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

  for(long i = 0;i < N;i++){
    if(M > data[i][1]){
      M -= data[i][1];
      counter += data[i][1] * data[i][0];
    }
    else{
      counter += M * data[i][0];
      break;
    }
  }

  cout << counter << endl;
}

Measured memory_bytes: 5760
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
const long long INF = 1LL << 60;

int main(){
    int N,D;
    cin>>N>>D;
    int ans=0;
    int cover = 2*D+1;

    ans = (N+cover-1)/cover;
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <complex>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

typedef complex<double> point_t;
typedef pair<point_t,double> circle_t;

const double eps=1e-9;

circle_t cs[62];
point_t meats[62];
double hardness[62];

int N,K;

void add_intersect(const circle_t & c1,const circle_t & c2,vector<point_t> & v){
    auto d=abs(c1.first-c2.first);
    auto rc=(d*d+c1.second*c1.second-c2.second*c2.second)/(2*d);
    auto diff=c1.second*c1.second-rc*rc;

    if (abs(diff)<eps) diff=0.;

    if (diff<0.) return;
    auto rs=sqrt(diff);

    auto dir=(c2.first-c1.first)/d;

    if (diff==0.) v.push_back(c1.first+dir*point_t(rc,rs));
    else {
        v.push_back(c1.first+dir*point_t(rc,rs));
        v.push_back(c1.first+dir*point_t(rc,-rs));
    }
}

int cnt(const point_t &  p){
    int ret=0;

    for(int i=1;i<=N;i++){
        // printf("r=%lf\n",cs[i].second);
        auto dist=abs(cs[i].first-p);
        // printf("dist=%lf\n",dist);
        if (dist < cs[i].second + eps) ret++;
    }
    // printf("pos=%lf,%lf ret=%d\n",p.real(),p.imag(),ret);
    return ret;
}

bool valid(){
    vector<point_t> candidate;
    for(int i=1;i<=N;i++) candidate.push_back(meats[i]);

    for(int i=1;i<=N;i++)
        for(int j=i+1;j<=N;j++)
             add_intersect(cs[i],cs[j],candidate);

    for(auto &p:candidate) if (cnt(p)>=K) return true;

    return false;
}

int main(){
    scanf("%d%d",&N,&K);

    if (K==1) {
        puts("0");
        return 0;
    }
    for(int i=1;i<=N;i++){
        double x,y,c;
        scanf("%lf%lf%lf",&x,&y,&c);
        meats[i]=point_t(x,y);
        hardness[i]=c;

    }
    
    double l=0.0,r=1e6;
    int i=0;
    while(r-l>=1e-6){
        i++;
        auto mid=(l+r)/2.;
        for(int i=1;i<=N;i++)
            cs[i]=circle_t(meats[i],mid/hardness[i]);

        if (valid()) r=mid;
        else l=mid;
    }

    printf("%.7lf\n",r);
    return 0;
}

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

ll gcd(ll a, ll b) {
    if (a < b)swap(a, b);
    ll r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

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

int main()
{
    ll N, M;
    cin >> N >> M;
    vector<ll> as(N);
    rep(i, N)cin >> as[i];

    ll base = 1;
    bool flag = false;
    REP(i, 1, N) {
        ll diff = abs(as[0] - as[i]) / 2;
        ll g = gcd(as[0], as[i]);
        if (diff%g != 0)flag = true;
    }
    for (auto a : as) {
        base = lcm(base, a / 2);
        if (base > 1e11)break;
    }
    if (base > M || flag) {
        cout << 0 << endl;
    }
    else {
        cout << 1 + (M - base) / (2 * base) << endl;
    }
    return 0;
}


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

int main(){
  int H, W;
  cin >> H >> W;
  //配列に変換
  vector<vector<char>> grid(H,vector<char>(W));
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      cin >> grid.at(i).at(j);
    }
  }
  
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      if(grid.at(i).at(j) == '.'){
        grid.at(i).at(j) = '0';
        for(int dx = -1; dx <= 1; dx++){
          for(int dy = -1; dy <= 1; dy++){
            int nx = i + dx, ny = j + dy;
            if(0<= nx && 0 <= ny && nx < H && ny < W){
              if(grid.at(nx).at(ny) == '#'){
                grid.at(i).at(j)++;
              }
            }
          }
        }
      }
    }
  }
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      cout << grid.at(i).at(j);
    }
    cout << endl;
  }
  return 0;
}
  

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



int main() {
  string moji;
  cin >> moji;
  ll ans = 0;
  

  int wnumber = 0; ///左から見て何番目のWか
  rep(i, moji.length()){
    if (moji[i] == 'W') {
      ans += i - wnumber;
      wnumber ++;
      }
    }
    cout << ans << endl;
  }


Measured memory_bytes: 3748
#include <iostream>

int main() {
    int n, m, x;

    std::cin >> n >> m >> x;

    int costL = 0;
    int costR = 0;
    for (int i=0; i<m; ++i) {
        int a;
        std::cin >> a;
        if (a < x) {
            costL++;
        } else {
            costR++;
        }
    }

    std::cout << std::min(costL, costR) << std::endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int min = Integer.MAX_VALUE;
        for (int i = 1; i < N; i++) {
            int a = i;
            int b = N - i;

            int sum = 0;
            while (a > 0) {
                sum += a % 10;
                a /= 10;
            }

            while (b > 0) {
                sum += b % 10;
                b /= 10;
            }
            min = Math.min(sum, min);
        }
        System.out.println(min);
    }
}


Measured memory_bytes: 21716
dic = {0:"A", 1:"B", 2:"C", 3:"D", 4:"E"}
while True:
  sa = list(map(int, input().split()))
  if sa == [0, 0]:
    break
  lst = [sum(sa)]
  for _ in range(4):
    lst.append(sum(map(int, input().split())))
  print(dic[lst.index(max(lst))], max(lst))



Measured memory_bytes: 5600
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <vector>

using namespace std;

int main(){
   int n[3];
   cin>>n[0]>>n[1]>>n[2];
   sort(n,n+3,greater<int>());
   int ans=0;
   if(((n[0]-n[1])+(n[0]-n[2]))%2==0){
      ans += n[0]-n[1]+(n[0]-(n[2]+n[0]-n[1]))/2;
   }
   else {
      ans += n[0]-n[1]+(n[0]-(n[2]+n[0]-n[1]))/2+2;
   }
   cout<<ans<<endl;
   
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define ldb long double
#define mt meke_tuple
template<typename T> bool ckmn(T &a, T b){ T c=a;a=min(a,b);return a!=c;}
template<typename T> bool ckmx(T &a, T b){ T c=a;a=max(a,b);return a!=c;}
const int N=100050;
int b[N],l[N],u[N],id[N],my[N];
ll mx[N],sum[N],suf[N],ord[N];
ll Get(int x, int y)
{
	ll ans=sum[x]+suf[x+1];
	if(my[y]>x) ans+=ord[y];
	return ans;
}
int main()
{
	int n,x;
	scanf("%i %i",&n,&x);
	priority_queue<pair<int,pair<int,int>>> pq;
	//ll tmp=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%i %i %i",&b[i],&l[i],&u[i]);
		//pq.push({l[i],{i,0}});
		//tmp-=(ll)b[i]*l[i];
		id[i]=i;
		mx[i]=(ll)(x-b[i])*u[i];
		ord[i]=mx[i]+(ll)b[i]*l[i];
	}
	/*ll sol=0;
	while(pq.size() && tmp<0)
	{
		pair<int,pair<int,int>> p=pq.top();
		pq.pop();
		int w=p.first;
		int i=p.second.first;
		int sz=b[i];
		if(p.second.second==1) sz=x-b[i];
		printf("i: %i\n",i);
		if(tmp+(ll)w*sz<0)
		{
			tmp+=(ll)w*sz;
			sol+=sz;
			if(p.second.second==0)
			{
				pq.push({u[i],{i,1}});
			}
		}
		else
		{
			int top=sz,bot=0,ans,mid;
			while(top>=bot)
			{
				mid=top+bot>>1;
				if(tmp+(ll)w*mid>=0) ans=mid,top=mid-1;
				else bot=mid+1;
			}
			tmp+=(ll)w*ans;
			sol+=ans;
			break;
		}
	}
	printf("%i\n",sol);*/
	sort(id+1,id+1+n,[&](int x, int y){ return ord[x]>ord[y];});
	for(int i=1;i<=n;i++) my[id[i]]=i;
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+mx[id[i]];
	for(int i=n;i>=1;i--) suf[i]=suf[i+1]+mx[id[i]]-ord[id[i]];
	ll sol=9e18;
	for(int i=1;i<=n;i++)
	{
		int top=n,bot=0,mid,ans=n;
		while(top>=bot)
		{
			mid=top+bot>>1;
			if(Get(mid,i)>=0) ans=mid,top=mid-1;
			else bot=mid+1;
		}
		ll tmp=Get(ans,i);
		tmp-=mx[i];
		ll cur=(ll)ans*x;
		if(my[i]<=ans) cur-=x;
		top=x,bot=0,mid,ans=x;
		while(top>=bot)
		{
			mid=top+bot>>1;
			ll add=0;
			if(mid<=b[i]) add=(ll)(mid-b[i])*l[i];
			else add=(ll)(mid-b[i])*u[i];
			if(tmp+add>=0) ans=mid,top=mid-1;
			else bot=mid+1;
		}
		cur+=ans;
		sol=min(sol,cur);
	}
	printf("%lld\n",sol);
	return 0;
}

Measured memory_bytes: 5376
import numpy as np

n, p = map(int, input().split())
a = np.array(list(map(int, input().split())))
a = np.sum(a[a % 2 == 1])

if a == 0:
    if p == 0:
        print(2 ** n)
    else:
        print(0)
else:
    print(2 ** (n - 1))

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

using namespace std;

int main()
{
// #ifndef ONLINE_JUDGE
//     freopen("input.txt","r",stdin);
// #endif
    
    int a,b;
    cin>>a>>b;
    if(a<b)cout<<"0"<<endl;
    else if(a>=b)
    {
        cout<<"10"<<endl;
    }
    return 0 ;
}

Measured memory_bytes: 256
#include<iostream>
#include<numeric>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<iomanip>
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define pll pair<ll,ll>
#define rep(i,from,to) for(int i=from;i<to;i++)
#define repd(i,from,till) for(int i=from;i>=till;i--)
#define waste ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define inf 1e9+1
#define mod 1e9+7
#define inf1 1e18+1
#define pie 3.14159265358979323846
#define N 100005
using namespace std;

int solve(){
	int n,mxwt;
	cin>>n>>mxwt;
	int w[n],v[n];
	int sum[n];
	rep(i,0,n){
		cin>>w[i]>>v[i];
		if(i==0)sum[i]=v[i];
		else sum[i]=sum[i-1]+v[i];
	}
	int dp[n][sum[n-1]+5];
	rep(i,0,n){
		rep(j,0,sum[n-1]+1){
			if(j==0)dp[i][j]=0;
			else dp[i][j]=inf;
		}
	}
	dp[0][v[0]]=w[0];
	rep(i,1,n){
		rep(j,0,sum[i]+1)dp[i][j]=dp[i-1][j];
		rep(j,0,sum[i]-v[i]+1){
			if(j==0)dp[i][v[i]]=min(dp[i][v[i]],w[i]);
			else dp[i][j+v[i]]=min(dp[i-1][j+v[i]],w[i]+dp[i-1][j]);
		}
	}
	repd(i,sum[n-1],0){
		if(dp[n-1][i]<=mxwt){
			cout<<i;
			return 0;
		}
	}
}
int main()
{
	//waste;
	int t;
	//cin>>t;
	t=1;
	while(t--){
		solve();
	}
}


Measured memory_bytes: 39296
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef long double ld;

int main() {
	
	cin.tie(0); cout.tie(0);
	ll n, k, s = 0, p, m = 0; cin >> n >> k;
	for(ll i = 0; i < n; i ++) {
		cin >> p;
	} 
   	n -= k;
   	s++;
   	k--;
   	if(n != 0){
   		m = (n / k);
   	}
   	if(n % k != 0) s++; 	
   	s += m;
   	cout << s; 
 	return 0;                        
}

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

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

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

int main() {
#ifdef FASTIO
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(false);
#endif
#ifdef FILEINPUT
    ifstream ifs("./in_out/input.txt");
    cin.rdbuf(ifs.rdbuf());
#endif

    int N;
    cin >> N;
    Vi A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        --A[i];
    }

    int cnt = 0;
    for (int i = 0; i < N; i++) {
        if (A[A[i]] == i) {
            ++cnt;
        }
    }

    cout << cnt / 2 << endl;

    return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100005
int n;
bool mi(int a,int b)
{
    return a>b;
}
int main()
{
    int X,Y,A,B,C;
    int r[N],g[N],w[N];
    cin>>X>>Y>>A>>B>>C;
    for(int i=1;i<=A;i++)
        cin>>r[i];
    for(int i=1;i<=B;i++)
        cin>>g[i];
    for(int i=1;i<=C;i++)
        cin>>w[i];
    sort(r+1,r+A+1,mi);
    sort(g+1,g+B+1,mi);
    sort(w+1,w+C+1,mi);
    int tem[3*N];
    for(int i=1;i<=X;i++)
        tem[i]=r[i];
    for(int i=X+1;i<=X+Y;i++)
        tem[i]=g[i-X];
    for(int i=X+Y+1;i<=X+Y+C;i++)
        tem[i]=w[i-X-Y];
    sort(tem+1,tem+X+Y+C+1,mi);
    long long int sum=0;
    for(int i=1;i<=X+Y;i++)
    sum+=tem[i];
    cout<<sum;



}


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

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	double ans=0;
	for(int i=0;i<n;i++){
		double x;
		cin>>x;
		ans+=1/x;
	}
	cout<<fixed<<setprecision(10)<<1/ans<<endl;
}


Measured memory_bytes: 256
def make_divisors(n):
    """自然数nの約数を列挙したリストを出力する
    計算量: O(sqrt(N))
    入出力例: 12 -> [1, 2, 3, 4, 6, 12]
    """
    divisors = []
    for k in range(1, int(n**0.5) + 1):
        if n % k == 0:
            divisors.append(k)
            if k != n // k:
                divisors.append(n // k)
    divisors = sorted(divisors)
    return divisors


n = int(input())
ans = make_divisors(n)
res = 10**18
for i in range(len(ans)):
    tmp = ans[i] + n // ans[i] - 2
    res = min(tmp, res)
print(res)

Measured memory_bytes: 39792
import qualified Data.Map as M
import Data.List

data RecItem = RecItem {
    riStart :: Int
  , riEnd :: Int
  , riChannel :: Int
  } deriving (Show)

data EventType = ETStart | ETEnd
                           deriving (Eq, Ord)

data Event = Event {
    evTime :: Int
  , evType :: EventType
} deriving (Eq, Ord)

calc :: M.Map Int [RecItem] -> Int -> Int
calc ris numC =
  countPara $ sort $ concat [eventList ris c | c <- [1 .. numC]]

eventList :: M.Map Int [RecItem] -> Int -> [Event]
eventList ris c = 
  concat [[Event s ETStart, Event e ETEnd] |
          RecItem s e _ <- paste $ sortOn riStart $ ris M.! c]
  where 
    ffilt (RecItem s e c') = c == c'
    paste = paste2 []
    paste2 acc [] = reverse acc
    paste2 [] (ri : ris) = paste2 [ri] ris
    paste2 acc@((RecItem sA eA c) : risA) (riB@(RecItem sB eB _) : ris)
      | eA == sB  = paste2 ((RecItem sA eB c) : risA) ris
      | otherwise = paste2 (riB : acc) ris

--    paste = foldr gen []
--    gen ri [] = [ri]
--    gen ri1@(RecItem s1 e1 _) ris2@((RecItem s2 e2 c) : ris)
--      | e1 == s2  = RecItem s1 e2 c : ris
--      | otherwise = ri1 : ris2

countPara :: [Event] -> Int
countPara evs = f 0 0 evs
  where f cur vMax [] = vMax
        f cur vMax ((Event t ETStart) : evs) = f (cur + 1) vMax' evs
          where vMax' = if cur == vMax then vMax + 1 else vMax
        f cur vMax ((Event t ETEnd)   : evs) = f (cur - 1) vMax evs

main :: IO ()
main = do
  x <- getLine
  let [numRI, numC] = [read w | w <- words x]
  ris <- readData numRI numC
  putStrLn $ show $ calc ris numC

readData :: Int -> Int -> IO (M.Map Int [RecItem])
readData numRI numC = do
  f numRI (M.fromList [(c, []) | c <- [1 .. numC]])
  where
    f :: Int -> M.Map Int [RecItem] -> IO (M.Map Int [RecItem])
    f n acc | n == 0    = return acc
            | otherwise = do
                x <- getLine
                let [s, e, c] = [read w | w <- words x]
                f (n - 1) (M.adjust ((RecItem s e c) :) c acc)


Measured memory_bytes: 113020
import java.util.Scanner

object Main extends App {
  val sc = new Scanner(System.in)

  val n = sc.nextInt
  val d = sc.nextInt
  val xl =
    List.fill(n){
      List.fill(d)(sc.nextInt)
    }.zipWithIndex

  val sqrtList = (1 to 136).map(n => n * n)

  val res = (
      for {
        x <- xl
        y <- xl
        if x._2 != y._2
      }yield distanceSqrt(x._1,y._1)
    ).count(sqrtList.contains(_)) / 2

  println(res)


  def distanceSqrt(xl: List[Int], yl: List[Int]): Int = {
    (xl zip yl).map{case (x,y) =>
      val z = x - y
      z * z
    }.sum
  }
}


Measured memory_bytes: 25792