akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <map>


using namespace std;
typedef long long int ll;

int main()
{
	int n; cin >> n;
	vector<int> v(n);
	map<int,int> m;

	for(int i = 0; i < n; ++i)
	{
		cin >> v[i];
		m[v[i]] += 1;
	}
	
	ll total = 0;
	for(auto& p : m)
	{
		ll count = p.second;
		total += (count * (count - 1)) / 2;
	}

	for(int i = 0; i < n; ++i)
	{
		ll count = m[v[i]];
		cout << total - (count - 1) << "\n";
	}
	
	return 0;
}
	


Measured memory_bytes: 8320
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define dd double
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep1(i,b) for(int i=1;i<=b;i++)
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define F first
#define S second
#define vec vector<int,int> 
#define int long long 
#define pii pair<int,int>
int visited[100001];

int ax,ay,bx,by,t_x0,t_y0;

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//ios_base& scientific (ios_base& str);
	
	int t=1;
	//cin>>t;
	while(t--){
		int n,k;
		cin>>n>>k;
		int arr[n];
		rep(i,n){
			cin>>arr[i];
		}
		sort(arr,arr+n);
		int dp[k+1]={0};
		dp[0]=1;
		for(int i=1;i<=k;i++){
			int ind=upper_bound(arr,arr+n,i)-arr;
			ind--;
			if(ind==-1){
				dp[i]=1;
			}
			else{
				bool flag=false;
				for(int j=0;j<=ind;j++){
					if(dp[i-arr[j]]){
						flag=true;
						break;
					}
				}
				if(flag){
					dp[i]=0;
				}
				else{
					dp[i]=1;
				}
			}
		}
		if(dp[k]==0){
			cout<<"First"<<endl;
		}
		else{
			cout<<"Second"<<endl;
		}
	}
	//exit();
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include<math.h>
#include<algorithm> 
#define rep(i,n) for (int i = 0; i < (n) ; ++i)
using namespace std;
using ll = long long ;
using P = pair<int, int> ;
#define PI 3.14159265358979323846264338327950
#define INF 1e18

int main() {
    int n, d ; 
    cin >> n >> d ;
    vector<vector<double>> za (d) ;
    rep(i, n){
        rep(j, d){
            double x ;
            cin >> x ;
            za[j].push_back(x) ;
        }
    }
    int ans = 0;
    for(int i = 0 ; i < n - 1; i++ ){
        for(int j = i + 1 ; j < n ; j++){
            double tot = 0 ;
            rep(p, d){
                tot += (pow(za[p][i] - za[p][j], 2)) ;
            }
            tot = sqrt(tot) ;
            int k = int(tot) ;
            if(k == tot){
                ans++ ;
            }
        }
    }
    cout << ans << endl ;
}

Measured memory_bytes: 3784
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for(ll i = (ll)(s); i < (ll)(t); i++)
#define rrep(i,s,t) for(ll i = (ll)(s-1);(ll)(t) <= i; i--)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
constexpr ll INF = numeric_limits<ll>::max()/4;
constexpr ll n_max = 2e5+10;
#define int ll

template <typename A, typename B>
string to_string(pair<A, B> p);
string to_string(const string &s) {return '"' + s + '"';}
string to_string(const char *c) {return to_string((string) c);}
string to_string(bool b) {return (b ? "true" : "false");}
template <size_t N>
string to_string(bitset<N> v){
    string res = "";
    for(size_t i = 0; i < N; i++) res += static_cast<char>('0' + v[i]);
    return res;
}
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for(const auto &x : v) {
        if(!first) res += ", ";
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p){return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}

void debug_out() {cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

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

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n; cin >> n;
    vector<string> s(n);
    rep(i,0,n){
        cin >> s[i];
    }

    vector<ll> cnt_col(n), cnt_row(n);
    rep(i,0,n){
        rep(j,0,n){
            cnt_col[j] += s[i][j] == '.';
            cnt_row[i] += s[i][j] == '.';
        }
    }

    ll ans = INF;
    ll l = 0;
    rep(i,0,n) 
        if(cnt_col[i]) l++;

    

    rep(i,0,n){
        ll t = cnt_row[i] + l;
        if(cnt_col[i] == n){
            t++;
        }
        chmin(ans, t);
    }

    if(accumulate(all(cnt_col), 0) == n * n){
        cout << -1 << endl;
        return 0;
    }
    cout << ans << endl;
}

Measured memory_bytes: 512
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

L = INT()

# for a in range(L):
#     for b in range():
a = L / 3
bc = L - a
b = bc / 2
c = bc - b
print(a * b * c)


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

namespace ProblemA
{
    class Program
    {
        static void Main()
        {
            string S = Console.ReadLine();

            for (int i = 0; i < 3; i++)
            {
                Console.Write(S[i]);
            }
            Console.WriteLine();
        }

        //入力関係のメソッド
        public static int GetInt() => int.Parse(Console.ReadLine());
        public static int[] GetIntArray() => Console.ReadLine().Split().Select(int.Parse).ToArray();
        public static double GetDouble() => double.Parse(Console.ReadLine());
        public static double[] GetDoubleArray() => Console.ReadLine().Split().Select(double.Parse).ToArray();
        public static long GetLong() => long.Parse(Console.ReadLine());
        public static long[] GetLongArray() => Console.ReadLine().Split().Select(long.Parse).ToArray();

        //出力関係のメソッド
        public static void OutIntArray(int[] values)
        {
            foreach (var value in values)
            {
                Console.WriteLine(value);
            }
        }
        public static void OutLongArray(long[] values)
        {
            foreach (var value in values)
            {
                Console.WriteLine(value);
            }
        }
        public static void OutList(List<object> list)
        {
            foreach (var value in list)
            {
                Console.WriteLine(value);
            }
        }

    }
}


Measured memory_bytes: 25892
#define _USE_MATH_DEFINES
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<cstring>
#include<stack>
#include<functional>
using namespace std;
const int INF = INT_MAX / 2;

typedef long long ll;

int N;
ll d[10], v[10];

ll GCD(ll a, ll b)
{
	if(b == 0) return a;
	return GCD(b, a % b);
}

ll LCM(ll a, ll b)
{
	return a / GCD(a, b) * b;
}

int main(){
	while(cin >> N, N)
	{
		int K;
		int cnt[10] = {};
		for(int i = 0; i < N; i++)
		{
			cin >> K;
			cnt[K]++;
		}
		for(int i = 0; i < 10; i++)
		{
			if(cnt[i] == 0) puts("-");
			else
			{
				for(int j = 0; j < cnt[i]; j++)
				{
					printf("*");
				}
				puts("");
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1124
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <queue>
#include <string>
#include <vector>
using namespace std;
using ll = int64_t;
#define rep(i, j, n) for (int i = j; i < (int)n; ++i)
#define rrep(i, j, n) for (int i = (int)n - 1; j <= i; --i)

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

  int n = (int)s.size();
  vector<int> l(n + 1), r(n + 1);
  rep(i, 0, n) l[i] = s[i] == 'L';
  rep(i, 0, n) r[i] = s[i] == 'R';
  rep(i, 0, n) if (s[i] == 'R') r[i + 1] += r[i];

  rrep(i, 1, n) if (s[i] == 'L') l[i - 1] += l[i];

  vector<int> ans(n);
  if (s[0] == 'L') ans[0] = l[0];
  rep(i, 0, n - 1) if (s[i] == 'R' && s[i + 1] == 'L') {
    ans[i] = (r[i] + 1) / 2 + l[i + 1] / 2;
    ans[i + 1] = r[i] / 2 + (l[i + 1] + 1) / 2;
  }
  if (s[n - 1] == 'R') ans[n - 1] = r[n];
  rep(i, 0, n) cout << ans[i] << " \n"[i == n - 1];
  return 0;
}

Measured memory_bytes: 4556
// At Corder.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <algorithm>
#include <iostream>
using namespace std;

#include <vector>
#include <numeric>
#include <math.h>
#define ld long double
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;
using p = pair<int, int>;//<key,value>


	int main()
	{ 
		int n;
		cin >> n;
		rep(i, 1000) {
			if (1000 * i >= n) {
				cout << 1000 * i - n << endl;
				return 0;
			}
		}
		
	}


// プログラムの実行: Ctrl + F5 または [デバッグ] > [デバッグなしで開始] メニュー
// プログラムのデバッグ: F5 または [デバッグ] > [デバッグの開始] メニュー

// 作業を開始するためのヒント:
//    1. ソリューション エクスプローラー ウィンドウを使用してファイルを追加/管理します
//   2. チーム エクスプローラー ウィンドウを使用してソース管理に接続します
//   3. 出力ウィンドウを使用して、ビルド出力とその他のメッセージを表示します
//   4. エラー一覧ウィンドウを使用してエラーを表示します
//   5. [プロジェクト] > [新しい項目の追加] と移動して新しいコード ファイルを作成するか、[プロジェクト] > [既存の項目の追加] と移動して既存のコード ファイルをプロジェクトに追加します
//   6. 後ほどこのプロジェクトを再び開く場合、[ファイル] > [開く] > [プロジェクト] と移動して .sln ファイルを選択します


Measured memory_bytes: 3632
#include<bits/stdc++.h>
typedef long long     ll;
#define fast          ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fr            first
#define sc            second
#define com(i,n)      for(int i=0;i<n;i++)
#define dom(i,n)      for(int i=1;i<=n;i++)
#define mom(i,n)      for(int i=n;i>=0;i--)
#define sortI(a,n)    sort(a,a+n)
#define sortD(a,n)    sort(a,a+n,greater<int>())
#define sortvi(a)     sort(a.begin(),a.end())
#define sortvd(a)     sort(a.begin(),a.end(),greater<int>())
#define sumall(a,x)   accumulate(a.begin(),a.end(),x)
#define pi            3.14159265358979323846264338327950
using namespace std;
map<ll,ll>mp;
int main()
{
    string s;
    cin>>s;
    char c;
    c=s[0];
    if(c<=90 && c>=65)
        cout << "A\n";
    else
        cout << "a\n";
}


Measured memory_bytes: 3568
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>

using namespace std;

#define mod 1000000007

int main()
{
	int n, k;
	string s;
	cin >> n >> k >> s;
	deque<int> qu;
	for(int i = 0; i < n; i++){
		if(s[i] == 'A') qu.push_back(0);
		else qu.push_back(1);
	}
	int reversenum = 0;
	for(int i = 0; i < min(2 * n, k); i++){
		int top = (qu[0] + reversenum % 2) % 2;
		if(top == 0){
			qu[0] = (1 + reversenum % 2) % 2;
		} else {
			qu.pop_front();
			reversenum++;
			qu.push_back(0 + reversenum % 2);
		}
	}
	if(k <= 2 * n){
		while(!qu.empty()){
			cout << (char)('A' + (qu[0] + reversenum % 2) % 2);
			qu.pop_front();
		}
	} else {
		if(k % 2 == 1){
			if((qu[0] + reversenum % 2) % 2 == 0){
				qu[0] = 1;
			} else {
				qu.pop_front();
				reversenum++;
				qu.push_back(0 + reversenum % 2);
			}
		}
		while(!qu.empty()){
			cout << (char)('A' + (qu[0] + reversenum % 2) % 2);
			qu.pop_front();
		}
	}
	cout << endl;
}

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }


int main() {
  ll L, A, B, M; cin >> L >> A >> B >> M;
  ll dl[18] = {}; rep(i,18) dl[i] = min((ll)L, max((ll)0, ((ll)pow(10,i+1)-A+(B-1))/B));
  ll fn[18] = {}; rep(i,18) fn[i] = (max(A,pow(10,i+1)<=A ? -1 : ((ll)pow(10,i)-A+(B-1))/B*B+A))%M;
  per(i,17) dl[i+1] -= dl[i];
  // debug(dl,dl+18); debug(fn,fn+18);

  ll p10[18] = {}; rep(i,18) p10[i] = i==0 ? 10%M : (p10[i-1]*10)%M;
  ll arr[3] = {0,1,B};
  rep(i,18) {
    arr[1] = fn[i];
    ll mat[3][3] = {{p10[i],1,0},{0,1,1},{0,0,1}};
    ll now = 1;
    while (dl[i]>=now) {
      if (dl[i]&now) {
        ll ta[3] = {}; rep(j,3) rep(k,3) ta[j] =(ta[j]+mat[j][k]*arr[k])%M ;
        rep(j,3) arr[j] = ta[j];
      }
      ll tm[3][3] = {}; rep(j,3) rep(k,3) rep(l,3) tm[j][k] = (tm[j][k]+mat[j][l]*mat[l][k])%M;
      rep(j,3) rep(k,3) mat[j][k] = tm[j][k];
      now *= 2;
    }
    // cout << i+1 << ": "; debug(arr,arr+3);
  }
  ll result = arr[0];
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 256
from operator import mul
from functools import reduce

MOD = 10 ** 9 + 7

def cmb(n, r):
    if n < r:
        return 0
    r = min(n - r, r)
    if r == 0:
        return 1
    numer = reduce(mul, range(n, n - r, -1))
    denom = reduce(mul, range(1, r + 1))
    return numer // denom % MOD
N, K = map(int, input().split())

for i in range(1, K + 1):
    print(cmb(K - 1, i - 1) * cmb(N - K + 1, i) % MOD)


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

using namespace std;

#define REP(var, n)  for (int var = 0; var < (n); var++)
#define RREP(var, n)  for (auto var = n - 1; var != static_cast<int>(-1); var--)
#define FOR(var, a, b)  for (auto var = (a); var < (b); var++)
#define RFOR(var, a, b)  for (auto var = b - 1; var != a; var--)

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pii;

#define all(c) begin(c),end(c)

#define D(x) do { std::cerr << x << " "; } while (0)
#define D2(x) do { std::cerr << #x << ": " << x << std::endl; } while (0)


template<typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) {
    if (!v.empty()) {
        out << '[';
        std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
        out << "\b\b]";
    }
    return out;
}


template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    return os << '(' << p.first << ',' << p.second << ')';
}


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;
}

int popcount(int v) {
    int r = 0;
    while (v > 0) {
        r += v % 2;
        v >>= 1;
    }
    return r;
}

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

    const int MOD = 1e9 + 7;

    vvi a = vvi(N, vi(N, 0));
    REP(i, N) {
        REP(j, N) {
            cin >> a[i][j];
        }
    }

    int S = (1 << N);
    vvll dp = vvll(N + 1, vll(S, 0));
    dp[0][0] = 1;

    unordered_map<int,vi> grp;
    REP(s,S) {
        grp[popcount(s)].push_back(s);
    }

    REP(i, N) {
        for(auto&&s:grp[i]) {
            REP(j, N) {
                if (a[i][j] == 1) {
                    dp[i + 1][s | (1 << j)] += dp[i][s] ;
                    dp[i + 1][s | (1 << j)] %= MOD;
                }
            }
        }
    }

    return dp[N][S-1];
}


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

//    cout << (solve() ? "First" : "Second") << endl;
//    cout << (solve() ? "YES" : "NO") << endl;
    cout << solve() << endl;
//    solve();

    return 0;
}

Measured memory_bytes: 377216
# abc109_c

from functools import reduce


def mcd(x, y):
    if x > y:
        big = x
        small = y
    else:
        big = y
        small = x
    while True:
        rest = big % small
        if rest == 0:
            return small
        else:
            big = small
            small = rest


def solve(seq):
    satisfy = []  # find distances to satisfy
    for i in range(len(seq) - 1):
        satisfy.append(abs(seq[i] - seq[i + 1]))

    if len(satisfy) == 1:
        return satisfy[0]

    return reduce(mcd, satisfy)


if __name__ == "__main__":
    firstline_input = list(map(int, input("").split(" ")))
    seq = list(map(int, input("").split(" ")))
    seq.insert(0, firstline_input[1])
    print(solve(seq))


Measured memory_bytes: 14748
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
using namespace std;
using Int = unsigned long long;
typedef pair<int,int> P; typedef pair<Int,Int> Pl;
int const mod = 1e9+7;
#define END {cout<<(ans)<<'\n'; return 0;}
#define ALL(vec) vec.begin(),vec.end()
#define Pr(type) priority_queue<type>
#define gPr(type) priority_queue<type,vector<type>,greater<type>>
#define V(type) vector<type>
#define rep(i,n) for(int i=0; i<n; i++)
#define rer(i,s,n) for(int i=s; i<n; i++)
#define gnr(i,l,r) for(int i=r; i>=l; i--)
#define eb emplace_back
#define fi first
#define se second
#define pri1(a) cout<<a<<'\n'
#define pri2(a,n) rep(i,(n)-1)cout<<a[i]<<' '; cout<<a[(n)-1]<<'\n';
#define prip(p) cout<<(p).first<<' '<<(p).second<<'\n'
template<class T> inline bool cmin(T& a, T b) { if (a > b) { return a = b; } return false; }
template<class T> inline bool cmax(T& a, T b) { if (a < b) { return a = b; } return false; }

int n,m,q,_,x,y;
string s,sb;
bool ok;
char ch;

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

  cin>>n; Int a[n],c[n+1]={}; rep(i,n){cin>>a[i]; c[i+1]=c[i]+a[i];}
  unordered_map<Int,Int>p;
  rep(i,n+1)p[c[i]]++;
  Int ans=0;
  for(Pl i:p)ans+=(i.se-1)*i.se/2;
  END
}

Measured memory_bytes: 11592
// #include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <vector>

#define rep(i,n) for (int i = 0; i < n; ++i)
#define repr(i,n) for (int i = n; i > 0; --i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

const int MAX = 100;
const int INF = (1<<12);


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

Measured memory_bytes: 3604
#include <iostream>
static void B_Palindrome_philia(const std::string& S)
{
    auto it = S.begin();
    auto rit = S.rbegin();

    const size_t num = S.length() / 2;
    size_t count = 0;
    for (size_t i = 0; i < num; ++i)
    {
        if (*(it++) != *(rit++))
            ++count;
    }
    std::cout << count;
}
int main(int, char**)
{
  std::string S;
  std::cin >> S;
  B_Palindrome_philia(S);
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdint>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <map>
#include <queue>
#include <tuple>

constexpr size_t m1 = -1;
constexpr size_t di[4] = {m1, 0, 1, 0};
constexpr size_t dj[4] = {0, m1, 0, 1};

int main() {
  size_t H, W;
  scanf("%zu %zu", &H, &W);

  std::vector<std::string> A(H);
  using zahyo = std::pair<size_t, size_t>;
  std::queue<zahyo> q;
  constexpr int inf = 1e9;
  std::vector<std::vector<int>> dp(H, std::vector<int>(W, inf));
  for (size_t i = 0; i < H; ++i) {
    char buf[1024];
    scanf("%s", buf);
    A[i] = buf;
    for (size_t j = 0; j < W; ++j) {
      if (A[i][j] == '#') {
        q.emplace(i, j);
        dp[i][j] = 0;
      }
    }
  }

  while (!q.empty()) {
    size_t i, j;
    std::tie(i, j) = q.front();
    q.pop();

    for (int k = 0; k < 4; ++k) {
      size_t ni = i+di[k];
      size_t nj = j+dj[k];
      if (!(ni < H && nj < W)) continue;
      if (dp[ni][nj] <= dp[i][j] + 1) continue;

      dp[ni][nj] = dp[i][j] + 1;
      q.emplace(ni, nj);
    }
  }

  int res = 0;
  for (const auto& ai: dp)
    res = std::max(res, *std::max_element(ai.begin(), ai.end()));

  printf("%d\n", res);
}


Measured memory_bytes: 21556
#include "bits/stdc++.h"
using namespace std;

int main() {
	int N;
	while (cin >> N) {
		if (N == 0) break;
		vector<int> A(N);
		for (int i = 0; i < N; i++) cin >> A[i];
		sort(A.begin(), A.end());
		int ANS = 100000000;
		for (int i = 0; i < N - 1; i++) {
			ANS = min(ANS, A[i + 1] - A[i]);
		}
		cout << ANS << endl;
	}
}


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

int N,D;

double dist(vector<int> a,vector<int> b){
  int sum = 0;
  rep(i,D){
    sum += pow((a[i] - b[i]),2);
  }
  return sqrt((double)sum);

}

int main(){
  cin >> N >> D;
  vector<vector<int>> points(N);
  rep(i,N){
    int point;
    points[i].resize(D);
    rep(d,D){
      cin >> points[i][d];
    }
  }

  int ans = 0;
  for(int i=0;i<N-1;i++){
    for(int j=i+1;j<N;j++){
      double result = dist(points[i],points[j]);

      if (ceil(result) == floor(result)) ans += 1;
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        int n = in.nextInt();
        int m = in.nextInt();
        Vertex[] vs = new Vertex[n + 1];
        for (int i = 1; i <= n; i++) {
            vs[i] = new Vertex(i);
        }
        for (int i = 0; i < m; i++) {
            int x = in.nextInt();
            int y = in.nextInt();
            vs[x].adj.add(vs[y]);
        }

        Set<Vertex> visited = new HashSet<>();
        Stack<Vertex> st = new Stack<>();
        for (int i = 1; i <= n; i++) {
            if (!visited.contains(vs[i]))
                dfs(vs[i], visited, st);
        }
        List<Vertex> sorted = new ArrayList<>();
        while (!st.isEmpty()) {
            sorted.add(st.pop());
        }
        int ans = 0;
        int[] dp = new int[n + 1];
        for (int i = 0; i < sorted.size(); i++) {
            Vertex v = sorted.get(i);
            for (Vertex ne : v.adj) {
                dp[ne.i] = Math.max(dp[ne.i], dp[v.i] + 1);
                ans = Math.max(ans, dp[ne.i]);
            }
        }
        out.println(ans);
        out.close();
    }

    private static void dfs(Vertex v, Set<Vertex> visited, Stack<Vertex> st) {
        visited.add(v);
        for (Vertex n : v.adj) {
            if (!visited.contains(n))
                dfs(n, visited, st);
        }
        st.add(v);
    }

    static class Vertex {
        int i;

        public Vertex(int i) {
            this.i = i;
        }

        List<Vertex> adj = new ArrayList<>();
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}


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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int mod = (int)1e9 + 7;
void dbg(){ cerr << "\n"; }  
template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
ll gcd(ll x, ll y){ return y==0? x: gcd(y, x%y); }

int main()
{
	
	//cin.tie(0); ios_base::sync_with_stdio(false);
	int n, x;
	cin >>n >>x;
	ll ans = 0;
	rep(i, n){
		int c; cin >>c;
		if(i==0) ans = abs(x-c);
		ans = gcd(ans, abs(x-c));
	}
	
	cout << ans << endl; 
	return 0;
}


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

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  
    ll n;
  cin>>n;
  ll s=0,i;
  for(i=1;i<=n;i++)
  {
   if(i%3!=0&&i%5!=0)
   {s+=i;}
  }   
  
  cout<<s;
return 0;}

Measured memory_bytes: 3652
#include <iostream>

using namespace std;

int main() {

  int n,d;
  cin>>n>>d;

  int ms = 2*d + 1;

  if(n%ms == 0) {
    cout<<n/ms<<endl;
  } else {
    cout<< (n/ms+1)<<endl;
  }


  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main () {
  int A, B;
  cin >> A >> B;
  
  if ( A > B && B != 1 || A==1&&B!=1){
    cout << "Alice" << endl;
  }
  else if ( A < B && A != 1 || B==1&&A!=1 ) {
    cout << "Bob" << endl;
  }
  else {
    cout << "Draw" << endl;
  }
}

Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
  val sc = Scanner(System.`in`)
  val a = sc.nextDouble()
  val b = sc.nextDouble()
  val x = sc.nextInt()

  var ok = Math.PI / 2.0
  var ng = 0.0
  for (i in 1..100000) {
    var mid = (ok + ng) / 2.0
    if (f(a, b, mid) < x) ok = mid
    else ng = mid
  }

  println(ok / Math.PI * 180)

}

private fun f(a: Double, b: Double, theta: Double): Double {
  val eps = 0.0000000001;
  if (theta > Math.PI / 2.0 - eps) {
    return 0.0
  }
  var ret: Double
  if (a * Math.tan(theta) <= b) {
    ret = a * a * b - a * a * a * Math.tan(theta) / 2.0
  } else {
    ret = b * b / Math.tan(theta) * a / 2.0
  }
  return ret
}


Measured memory_bytes: 38016
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

const long MOD = 1000000007;
typedef pair<int, int> P;
typedef long long ll;

ll gcd(ll a, ll b){
    if(b>a){
        ll t = a;
        a = b;
        b = t;
    }

    ll sa = a;
    ll sb = b;

    // ここでr=1で初期化しておかないと、直後のr!=0がtrueになってしまうことがある
    ll r = 1;
    while(r!=0){
        r = a % b;
        a = b;
        b = r;
    }

    ll gcd = a;
    return gcd;
}

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

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

    int l[N], r[N];
    l[0] = A[0];
    r[N-1] = A[N-1];
    for(int i=1; i<N; i++){
        l[i] = gcd(l[i-1], A[i]);
    }

    for(int i=N-2; i>=0; i--){
        r[i] = gcd(r[i+1], A[i]);
    }

    int ans = 0;
    ans = max(l[N-2], r[1]);
    for(int i=1; i<N-1; i++){
        int t = gcd(l[i-1], r[i+1]);
        ans = max(ans, t);
    }

    cout << ans << endl;

    return 0;
}


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

using namespace std;

int main()
{
	int N;
	cin >> N;
	vector < int >a(N);
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}

	int n = 1;
	int ans = 0;

	for (int i = 0; i < N; i++) {
		if (a[i] == n) {
			n++;
		} else {
			ans++;
		}
	}

	cout << (ans == N ? -1 : ans) << endl;

	return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}
template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}
inline int read(){
	int x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
	return x*f;
}
inline ll readll(){
	ll x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
	return x*f;
}
const int maxn=1e6+10,mod=998244353;
int ksm(int x,int y){
	int res=1;
	while(y){
		if(y&1) res=(ll)res*x%mod;
		x=(ll)x*x%mod;
		y>>=1;
	}
	return res;
}
int fac[maxn],ifac[maxn];
inline int C(int n,int m){
	if(n<m || m<0 || n<0) return 0;
	return (ll)fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main(){
	int n=read(),m=read();
	if(n<m) swap(n,m);
	fac[0]=1;
	REP(i,1,n*2) fac[i]=(ll)fac[i-1]*i%mod;
	ifac[2*n]=ksm(fac[2*n],mod-2);
	DREP(i,n*2,1) ifac[i-1]=(ll)ifac[i]*i%mod;
	int ans=0;
	REP(i,1,m) ans=(ans+(ll)C(n+m-i*2,n-i)*C(2*i,i))%mod;
	ans=(ll)ans*ksm(C(n+m,n),mod-2)%mod*(mod+1)/2%mod;
	ans=(ans+n)%mod;
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 8064
#include <iostream>


using namespace std;

int main(void)
{
    int N,M;
    double s=0,sum=0;
    cin>>N>>M;
    double A[N];
    for(int i=0;i<N;i++)
    {
        cin>>A[i];
        sum+=A[i];
    }

    for(int i=0;i<N;i++)
    {
        if(A[i]>=sum/(4*M))
        {
            s++;
        }

    }
    
    if(s>=M){
        cout<<"Yes"<<endl;
    }else cout<<"No"<<endl;


    return 0;
}

Measured memory_bytes: 256
N,M,C = map(int,input().split())
Bs = list(map(int, input().split()))
As = list(list(map(int, input().split())) for _ in range(N))

cnt = 0
for a in As:
    ans = 0
    for i in range(len(a)):
        ans += Bs[i]*a[i]
    ans += C
    
    if ans > 0:
        cnt += 1
print(cnt)

Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <numeric>
#define ALL(c) (c).begin(), (c).end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pdi = pair<double, int>;

string S;

int main() {
	cin >> S;
	const int m = 753;
	int ans = 9999;
	for (int i = 0; i < S.size()-2; i++)
	{
		int s = (S[i] - '0') * 100 + (S[i+1] - '0') * 10 + (S[i+2] - '0') * 1;
		ans = min(ans, abs(m - s));
	}
	cout << ans << endl;
	return 0;
}


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

int main(){
    ll n;
    cin >> n;
    vector<ll> t(5);
    ll mn = 1e17;
    rep(i, 0, 5){
        cin >> t[i];
        mn = min(mn, t[i]);
    }

    ll ans;
    if(n % mn != 0){
        ans = 4 + (ll)(n/mn+1); 
    }else{
        ans = 4 + (ll)(n/mn);
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
  int n,l;
  cin >> n >> l;
  vector<string> s(n);
  for(int i = 0; i < n; i++)cin >> s.at(i);
  sort(s.begin(),s.end());
  for(int i = 0;i < n; i++)cout << s.at(i);
  cout << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#define pi 3.14159265358979
 
int main(void) {
  double a, b, c, d, s;
  scanf("%lf%lf%lf", &a, &b, &c);
  c = c / 180 * pi;
  d = sqrt(a * a + b * b - 2 * a * b * cos(c));
  s = a * b / 2 * sin(c);
  printf("%f\n%f\n%f\n", s, a + b + d, s * 2 / a);
  return 0;
}



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

typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, n) for(int (i)=0; (i)<(n); (i)++)
#define FOR1(i, n) for(int (i)=1; (i)<=(n); (i)++)
#define FORI(i, n) for(int (i)=n-1; (i)>=0; (i)--)

int main(int argc, char** argv) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << setprecision(15);
    if (argc == 2 && atoi(argv[1]) == 123456789) {
        freopen("d:\\code\\cpp\\contests\\stdin", "r", stdin);
        //freopen("d:\\code\\cpp\\contests\\stdout", "w", stdout);
    }

    int N;
    cin >> N;
    string s;
    cin >> s;
    int cnt = 0;
    FOR1(i, N-1)
        cnt += s[i] != s[i-1];
    cout << cnt+1 << endl;

    if (argc == 2 && atoi(argv[1]) == 123456789)        cerr << clock()*1.0/CLOCKS_PER_SEC << " sec\n";
    return 0;
}

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

int main() {
	int N;
	cin >> N;
	vector<int> vec(N);
	for(int i=0;i<N;i++){
		cin >> vec.at(i); 
	}
	sort(vec.begin(), vec.end(), greater<int>());
	vec.erase(unique(vec.begin(), vec.end()),vec.end());

	cout << vec.size() << endl;
}

Measured memory_bytes: 3628
n = int(input())

a = list(map(int, input().split()))

minv = min(a)
maxv = max(a)

val = minv

min_d = 100000000
for i in range(maxv-minv+1):
  d=0
  val = minv + i
  for j in range(len(a)):
    d += (a[j] - val)**2
  if d<min_d:
    mindv = val
    min_d = d

print(min_d)



Measured memory_bytes: 3060
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	s=RD()
	n=len(s)

	dp=[[0]*4 for _ in range(n+1)]
	dp[0][0]=1


	for i,ss in enumerate(s):
		if s[i]=="A":
			dp[i+1][0]=dp[i][0]
			dp[i+1][1]=dp[i][0]+dp[i][1]
			dp[i+1][2]=dp[i][2]
			dp[i+1][3]=dp[i][3]
		elif s[i]=="B":
			dp[i+1][0]=dp[i][0]
			dp[i+1][1]=dp[i][1]
			dp[i+1][2]=dp[i][1]+dp[i][2]
			dp[i+1][3]=dp[i][3]
		elif s[i]=="C":
			dp[i+1][0]=dp[i][0]
			dp[i+1][1]=dp[i][1]
			dp[i+1][2]=dp[i][2]
			dp[i+1][3]=dp[i][2]+dp[i][3]
		else:
			dp[i+1][0]=dp[i][0]*3
			dp[i+1][1]=dp[i][0]+dp[i][1]*3
			dp[i+1][2]=dp[i][1]+dp[i][2]*3
			dp[i+1][3]=dp[i][2]+dp[i][3]*3

		for j in range(4):
			dp[i+1][j]%=10**9+7


	print(dp[-1][-1])











if __name__ == "__main__":
	main()


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

int main(){
    int N, A, B;
    cin >> N >> A >> B;
    int digit_sum;
    int number, reminder;
    int sum = 0;

    for(int i=1; i<=N; i++){
        number = i;
        digit_sum = 0;
        do{
            reminder = number % 10;
            digit_sum += reminder;
            number /= 10;
        } while(number != 0);

        if(digit_sum >= A && digit_sum <= B){
            sum += i;
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
S = input()
N = len(S)
zero_start, one_start = '', ''
for i in range(N):
    if i % 2 == 0:
        zero_start += '0'
        one_start += '1'
    else:
        zero_start += '1'
        one_start += '0'
zero_ans = 0
for i in range(N):
    if S[i] != zero_start[i]:
        zero_ans += 1
print(min(zero_ans, N-zero_ans))


Measured memory_bytes: 3316
from itertools import accumulate
def inpl(): return list(map(int, input().split()))

N, M = inpl()
A = [a-1 for a in inpl()]
S = [0]*(M+1)
T = [0]*(M+1)

tmp = 0
for i in range(N-1):
    T[A[i+1]] += (A[i+1] + M - A[i])%M - 1
    if A[i] < A[i+1]:
        S[A[i]+1] += 1
        S[A[i+1]] -= 1
        tmp += A[i+1] - A[i]
    else:
        tmp += A[i+1] + 1
        S[0] += 1
        S[A[i+1]] -= 1
        S[A[i]+1] += 1

S = list(accumulate(S))
ans = tmp*1
for i in range(1, M):
    tmp2 = tmp + T[i-1] - S[i-1]
    ans = min(ans, tmp2)
    tmp = tmp2
print(ans)

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

int main() {
  long int n, k;
  double ans=0;
  cin >> n >> k;
  vector<double> a(n), b(n), c(n,0.0); /*期待値の配列b*/
  for(int i=0; i<n; i++){
    cin >> a[i];
    b[i]=(a[i]+1)/2;
  }

  for(int i=0; i<k; i++){
    c[0] += b[i];
  }

  for(int i=1; i<n-k+1; ++i){
    c[i] = c[i-1] - b[i-1] + b[i+k-1]; 
  }

  for(int i=0; i<n; i++){
    ans=max(ans, c[i]);
  }

  
  cout << fixed << setprecision(12) << ans << endl;

  return 0;
}

Measured memory_bytes: 4992
def read():
    K, N = list(map(int, input().strip().split()))
    A = list(map(int, input().strip().split()))
    return K, N, A

def solve(K, N, A):
    A.append(A[0] + K)
    B = [A[(i+1)] - A[i] for i in range(N)]
    B = sorted(B)
    return sum(B[:-1])


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


Measured memory_bytes: 26444
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include<bits/stdc++.h>
#define ll long long
using namespace std;

int root(int arr[],int i){
    while(arr[i]!=i){
         arr[i]=arr[arr[i]];
        i=arr[i];
    }
    return i;
}
void Union(int arr[],int Size[],int a,int b){
int rootA=root(arr,a);
int rootB=root(arr,b);
if(Size[rootA]<Size[rootB]){
    arr[rootA]=arr[rootB];
    Size[rootB]+=Size[rootA];
}else{
arr[rootB]=arr[rootA];
Size[rootA]+=Size[rootB];
}
}
bool findRoot(int a,int b,int arr[]){
 if(root(arr,a)==root(arr,b))return true;
 else return false;
}
 vector<vector<int> >adj(105);
bool nCyc=false;
/*void dijkstra(int v,long long dis[]){
dis[v]=0;
multiset<pair<int,int> >s;
s.insert({0,v});
while(!s.empty()){
    pair<int,int>p= *s.begin();
    s.erase(s.begin());
    int x=p.second;
  if(vis[x])continue;
    vis[x]=1;
    for(int i=0;i<adj[x].size();i++){
        int e=adj[x][i].first,w=adj[x][i].second;
      //  cout<<dis[e]<<" "<<dis[x]+w<<endl;
        if(dis[e]>dis[x]+w){
            dis[e]=dis[x]+w;
            s.insert(make_pair(dis[e],e));
        }
    }
}
}*/
/*void bfs(int s){
    queue<int>q;
    q.push(s);
    while(!q.empty()){
        int v=q.front();
        q.pop();
        for(int i=0;i<adj[v].size();i++){
            if(!vis[adj[v][i]]){
                 q.push(adj[v][i]);
                 vis[adj[v][i]]=1;
            }
        }
    }
}*/
int vis[55][55];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
/*bool isVal(int i,int j){
      if(i<0 || j<0 || j>=m || i>=n)return false;
      return true;
}*/
/*void dfs(int i,int j) {

    if(!isVal(i,j) || vis[i][j] || arr[i][j]=='#')return;
      vis[i][j]=1;
	  if(arr[i][j]=='G'){
	  check++;
	  }
	  if(arr[i][j]=='B'){
        b=1;
        return;
	  }
	for(int k=0;k<4;k++){
     int pos1=i+dx[k],pos2=j+dy[k];
   //  cout<<pos1<<" "<<pos2<<endl;
     if( isVal(pos1,pos2) && (arr[pos1][pos2]=='#'))continue;
               dfs(pos1,pos2);
	}
}
void dfs2(int i,int j){
 if(isVal(i,j)==false || arr[i][j]!='.')return;
  arr[i][j]='#';
}*/
/*
double prim(int x){
    priority_queue<pair<double,int>,vector<pair<double,int> >,greater<pair<double,int> > >q;
    double min_cost=0.0;
    pair<double,int>p;
     q.push(make_pair(0.0,x));
     while(!q.empty()){
      p=q.top();
      q.pop();
      x=p.second;
      if(vis[x])continue;
      min_cost+=p.first;
      vis[x]=1;
      for(int i=0;i<adj[x].size();i++){
         int y=adj[x][i].second;
         if(!vis[y]){
            q.push(adj[x][i]);
        }
      }
     }
     return min_cost;
}*/
int n,k,arr[100005],dp[100005],ans=0;
int solve(int i){
    if(i==n-1)return 0;
    if(dp[i]!=-1)return dp[i];
    int ret=INT_MAX;
    for(int m=1;m<=k;m++){
        if(i+m<n)ret=min(ret,solve(i+m)+abs(arr[i]-arr[i+m]));
    }
    return dp[i]=ret;
}
int freq[1000005],check[1000005];
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>arr[i];
    memset(dp,-1,sizeof dp);
    cout<<solve(0);
return 0;
}


Measured memory_bytes: 10612
#include <bits/stdc++.h>
#define rep(i, n) for(int i= 0; i < (n); i++)
using ll= long long int;
using namespace std;
template <class T> inline bool chmax(T &a, T b) {
  if(a < b) {
    a= b;
    return 1;
  }
  return 0;
}
template <class T> inline bool chmin(T &a, T b) {
  if(a > b) {
    a= b;
    return 1;
  }
  return 0;
}
ll mod= 1e9 + 7;

double dp[310][310][310];
int n;

double rec(int a, int b, int c) {
  if(dp[a][b][c] >=0) return dp[a][b][c];
  if(a == 0 && b == 0 && c == 0) return 0.0;
  double res= 0.0;
  if(a > 0) res+= rec(a - 1, b, c) * a;
  if(b > 0) res+= rec(a + 1, b - 1, c) * b;
  if(c > 0) res+= rec(a, b + 1, c - 1) * c;
  res+= n;
  res*= 1.0 / (a + b + c);

  return dp[a][b][c]= res;
}

int main() {
  cin >> n;
  int v[3]= {};
  rep(i, n) {
    int g;
    cin >> g;
    v[g - 1]++;
  }

  memset(dp, -1, sizeof(dp));
  printf("%.12lf\n",rec(v[0],v[1],v[2]));
}


Measured memory_bytes: 233088
num = input()
predicted_value = 0
finished = False
i = 1
while i < len(num):
    if num[i] != num[i-1]:
        num = num[:i-1] + num[i+1:]
        predicted_value += 2
        if i > 1:
            i -= 2
        elif i == 1:
            i = 0
    i += 1
print(predicted_value)

Measured memory_bytes: 3424
maxi=-10**99 
n=int(input())
import heapq 
l=[int(i) for i in input().split()]
k=n
sm=sum(l[0:n])
z1=[0]*(n+1)
z2=[0]*(n+1)
h=[]
z1[0]=sm 
j=1 
heapq.heapify(h)
for i in range(n):
    heapq.heappush(h,l[i])
for i in range(n,2*n):
    p=l[i]
    if p>h[0]: 
        sm+=p 
        sm-=h[0]
        heapq.heappop(h)
        heapq.heappush(h,p)
    else:
        pass 
    z1[j]=sm 
    j+=1 
sm=sum(l[2*n:3*n])
h=[]
heapq.heapify(h)
sm=0 
for i in range(2*n,3*n):
    heapq.heappush(h,-l[i])
    sm+=(l[i])
j=n 
z2[j]=sm  
j-=1 
#print(h[0])
#print(sm)
for i in range(2*n-1,n-1,-1): 
    p=-l[i]
    if p>h[0]:
        #print('jif')
        sm=sm+h[0]-p
        heapq.heappop(h)
        heapq.heappush(h,p)
        
    else:
        pass 
    z2[j]=sm 
    j-=1 
maxi=-(10**99)
#print(z1)
#print(z2)
for i in range(n+1):
    maxi=max(maxi,z1[i]-z2[i])
print(maxi)

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

int N, K;
vector<int> l = {};

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

  for (int i = 0; i < N; i++)
  {
    int x;
    cin >> x;
    l.push_back(x);
  }

  sort(l.begin(), l.end());
  reverse(l.begin(), l.end());

  int ans = 0;
  for (int i = 0; i < K; i++)
  {
    ans += l[i];
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
K = int(input())
seven = 7 % K
c = 0
p = 1 % K
found = False
for i in range(K + 1):
  c = (c + p % K) % K
  if ((seven * c) % K == 0):
    found = True
    print(i + 1)
    break
  p = (p * (10 % K) ) % K
  #print(i, p)

if not found:
  print(-1)


Measured memory_bytes: 9184
#include <bits/stdc++.h>
using namespace std;
signed main(){
  	int x,y,ans,rank[3]={300000,200000,100000};
  	cin>>x>>y;
  	if(x < 4)
      ans+=rank[x-1];
  	if(y < 4)
      ans+=rank[y-1];
  	if(x == y && x == 1)
      ans+=400000;
  	
  	cout<<ans<<endl;
  	return(0);
}

Measured memory_bytes: 256
import math
n,k = map(int, input().split())
s = 0
ans = 0
for x in range(1,n+1):
  if x >= k:
    a = 0
  else:
    a = math.ceil(math.log2(k/x))
  b = (1 / n) * ((0.5) ** a)  
  ans += b
  
   
print(ans)

Measured memory_bytes: 9188
package main

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

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	//予備
	R := iScan()
	C := iScan()
	K := iScan()
	r := make([]int, K)
	c := make([]int, K)
	v := make([]int, K)
	var dp [3001][3001][4]int
	var ma [3001][3001]int
	for i := 0; i < K; i++ {
		r[i] = iScan()
		c[i] = iScan()
		v[i] = iScan()
		r[i]--
		c[i]--
		ma[r[i]][c[i]] = v[i]
	}
	dp[0][0][0] = 0
	dp[0][0][1] = ma[0][0]
	for i := 0; i < R; i++ {
		for j := 0; j < C; j++ {
			dp[i][j+1][0] = max([]int{dp[i][j][0], dp[i][j+1][0]})
			dp[i][j+1][1] = max([]int{dp[i][j][1], dp[i][j+1][1], dp[i][j][0] + ma[i][j+1]})
			dp[i][j+1][2] = max([]int{dp[i][j][2], dp[i][j+1][2], dp[i][j][1] + ma[i][j+1]})
			dp[i][j+1][3] = max([]int{dp[i][j][3], dp[i][j+1][3], dp[i][j][2] + ma[i][j+1]})

			dp[i+1][j][0] = max([]int{dp[i][j][0], dp[i][j][1], dp[i][j][2], dp[i][j][3], dp[i+1][j][0]})
			dp[i+1][j][1] = max([]int{dp[i][j][0] + ma[i+1][j], dp[i][j][1] + ma[i+1][j], dp[i][j][2] + ma[i+1][j], dp[i][j][3] + ma[i+1][j], dp[i+1][j][1]})
		}
	}
	fmt.Println(max([]int{dp[R-1][C-1][0], dp[R-1][C-1][1], dp[R-1][C-1][2], dp[R-1][C-1][3]}))
}


Measured memory_bytes: 373232
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,A,B,L;
string S;
string alpha = "abcdefghijklmnopqrstuvwxyz";
string ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ll MOD = 998244353;
const ll MAX_N = 100010;
typedef pair<ll,ll> P;

int main() {
    cin>>N;
    map<string,ll> m;
    ll ans = 0;
    rep(i,N){
        cin>>S;
        sort(S.begin(),S.end());
        auto ite = m.find(S);
        if(ite == m.end()){
            m.insert(mp(S,1));
        }else{
            ans += m[S];
            ++m[S];
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 11136
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<string>
#include<queue>
#define re register
#define ll long long 
#define maxn 10010000
#define mod 6662333 
#define inf 2147483647
#define mem(p) memset(&p,0,sizeof(p))
using namespace std;
inline int read()
{ 
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} 
    while(isdigit(c)){x=x*10+c-48;c=getchar();}
    return x*f;
}
inline void put(ll x)
{
     if(x<0) putchar('-'),x=-x;
     if(x>9) put(x/10);
     putchar(x%10+'0');
}
char a[maxn],b[maxn];
int sum;
int main()
{
    cin>>a;
    sum=strlen(a);//求字符数组a的长度 
    sum-=1;
    for(int i=0;a[i]!='\0';i++)
	{
        if(a[i]=='b') b[sum]='d';
        if(a[i]=='d') b[sum]='b';
        if(a[i]=='p') b[sum]='q';
        if(a[i]=='q') b[sum]='p';
        sum--;
    }
    if(strcmp(a,b)==false) cout<<"Yes";
	else cout<<"No";
    return 0;
}

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

int main(){
	int n, m;
	cin >> n;
	map<string, int> mp;
	rep(i, n){
		string a;
		cin >> a;
		mp[a]++;
	}
	
	cin >> m;
	rep(i, m){
		string s;
		cin >> s;
		mp[s]--;
	}

	int ans = 0;
	for(pair<string, int> p : mp){
		string key = p.first;
		int value = p.second;
		ans = max(ans, value);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
n=int(input())
h=list(map(int,input().split()))
cnt=1
for i in range(1,len(h)):
  hotel=h[i]
  c=True
  for j in range(0,i):
    if h[i]<h[j]:
      c=False
      break
  if c:
    cnt+=1
print(cnt)

Measured memory_bytes: 3064
#include <stdio.h>

int main( void ) {


	char S[3];
	int sum = 700;

 	scanf("%s", S);

 	if(S[0] == 'o') {
 		sum += 100;
 	}

 	if(S[1] == 'o') {
 		sum += 100;
 	}

 	if(S[2] == 'o') {
 		sum += 100;
 	}

 	printf("%d", sum);

}

Measured memory_bytes: 128