akhauriyash/Code-Regression huggingface dataset:
import std.stdio,
       std.string,
       std.conv,
       std.algorithm;

void main() {
    auto flag = true;
    int[][] a, b;
    while(!stdin.eof) {
        auto input = readln.chomp;
        if(input.length) {
            auto arr = function int[](string s) {
                    int[] ret;
                    foreach(c; s) {
                        ret ~= c.to!int - 48;
                    }
                    return ret;
                }(input);
            if(flag)
                a ~= arr, flag = !flag;
            else
                b ~= arr, flag = !flag;
        }
    }

    long h = b.length, w = a[0].length;
    long x = 0, y = 0;
    auto d = 'R';
    while(1) {
        switch(d) {
            case 'R':
                if(y - 1 >= 0 && b[y - 1][x])
                    y--, d = 'U';
                else if(x < w && a[y][x]) {
                    x++;
                }
                else if(y < h && b[y][x])
                    y++, d = 'D';
                else
                    x--, d = 'L';
                break;
            case 'U':
                if(x - 1 >= 0 && a[y][x - 1])
                    x--, d = 'L';
                else if(y - 1 >= 0 && b[y - 1][x])
                    y--;
                else if(x < w && a[y][x])
                    x++, d = 'R';
                else
                    y++, d = 'D';
                break;
            case 'L':
                if(y < h && b[y][x])
                    y++, d = 'D';
                else if(x - 1 >= 0 && a[y][x - 1])
                    x--;
                else if(y - 1 >= 0 && b[y - 1][x])
                    y--, d = 'U';
                else
                    x++, d = 'R';
                break;
            case 'D':
                if(x < w && a[y][x])
                    x++, d = 'R';
                else if(y < h && b[y][x])
                    y++;
                else if(x - 1 >= 0 && a[y][x - 1])
                    x--, d = 'L';
                else
                    y--, d = 'U';
                break;
            default:
                return;
        }
        d.write;
        if(x == 0 && y == 0)
            break;
    }
    writeln;
}

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

int main(){
    int N,flag=0;
    cin >> N;
    if(N%7==0||N%4==0)
    flag=1;
    while(N>7){
        N-=7;
        if(N%4==0){
            flag=1;
            break;
        }
    }
    if(flag)
    cout << "Yes" << endl;
    else
    cout << "No" << endl;
}

Measured memory_bytes: 256
N = int(input())
AB= [[int(i) for i in input().split()] for j in range(N)]
AB_sorted = sorted(AB, key=lambda x:x[1])
s = 0

for i in range(N):
    s += AB_sorted[i][0]
    if s > AB_sorted[i][1]:
        print('No')
        break
else:
    print('Yes')

Measured memory_bytes: 42836
n = int(input())
ans = 0
sb = []
fa = []

def ABCount(s):
    cnt = 0
    for i in range(len(s)-1):
        if s[i] == "A" and s[i+1] == "B":
            cnt += 1
    return cnt

for i in range(n):
    s = input()
    ans += ABCount(s)
    if s[0] == "B":
        sb.append(i)
    if s[-1] == "A":
        fa.append(i)

if len(sb) == len(fa) and len(sb) > 0:
    sb.sort()
    fa.sort()
    f = False
    for i in range(len(sb)):
        if not sb[i] == fa[i]:
            f = True
            break
    if f:
        ans += len(sb)
    else:
        ans += len(sb)-1
else:
    ans += min(len(sb),len(fa))

print(ans)


Measured memory_bytes: 3532
n = gets.to_i
nums = []
n.times { nums << gets.to_i }
copy = Marshal.load(Marshal.dump(nums))
nums.sort!.reverse!
biggest = nums[0]
second_biggest = nums[1]
copy.each do |n|
  if n == biggest
    puts second_biggest
  else
    puts biggest
  end
end


Measured memory_bytes: 8896
#include<iostream>
#include<functional>
#include<utility>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
int n, m;
string s;
vector<int> vec(100);
int ans = 0;


int main() {
	long long r;
	cin >> r;
	long long a[10];
	int temp = 0;
	int min = 0;//遅い番号
	for (int i = 0; i < 5; i++)
	{
		cin >> a[i];
		if (a[i]<a[min])
		{
			min = i;
		}
	}
	
	cout << (r+ a[min]-1) / a[min] + 4;
	
	
	
	

}

Measured memory_bytes: 256
def solve(n, a)
  w = (a.reduce{|acc, e| acc + e } / n.to_f).round
  a.reduce(0) do |acc, e|
    acc + (e - w)**2
  end
end

def main
  stdin = STDIN.gets
  n = stdin
  stdin = STDIN.gets
  a = stdin.split(/\s/).map!(&:to_i)

  puts solve(n, a)
end

main

Measured memory_bytes: 3836
M, K = map(int, input().split())

if M == 0 and K == 0:
    print(0, 0)
elif M == 1 and K == 0:
    print(0, 0, 1, 1)
elif M >= 2 and K < 2 ** M:
    tmp = []
    for n in range(2 ** M):
        if n != K:
            tmp.append(n)
    print(*tmp, K, *tmp[::-1], K)
else:
    print(-1)


Measured memory_bytes: 97688
#include <iostream>
using namespace std;
int main (void) {
    int N;
    int M;
    int X;

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

    cout << min(cnt, M - cnt) << endl;
    
    return 0;
}


Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var n, t, a float64
	fmt.Scan(&n, &t, &a)

	h := make([]float64, int(n))
	for i := 0; i < int(n); i++ {
		fmt.Scan(&h[i])
	}
	min := 1000.0
	numStore := 0

	for i := 0; i < int(n); i++ {
		localMin := a - (t - h[i]*0.006)
		if localMin < 0 {
			localMin *= -1
		}
		if min > localMin {
			min = localMin
			numStore = i
		}
	}
	fmt.Println(numStore + 1)
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 200005
#define INF 1000000005LL
#define MOD 1000000007

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

int n;
ll a[SIZE];
ll K;

int main()
{
	cin >> n;
	rep(i,0,n) cin >> a[i];
	ll r = 1;
	ll v = a[0];
	vector<ll> s;
	ll ans = 0;
	rep(i,0,n) {
		while(r<n) {
			if(v+a[r] == (v^a[r])){
				//cout << v+a[r] << " " << (v^a[r]) << endl;
				v += a[r];
				r++;
			}else{
				break;
			}
		}
		ll k = (ll)(r-i);
		ans += k;
		//cout << i << " " << r << endl;
		v -= a[i];
	}
	cout << ans << endl;


	return 0;
}


Measured memory_bytes: 1792
code = r"""
# distutils: language=c++
# distutils: include_dirs=[/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
from libcpp cimport bool
from libcpp.vector cimport vector
cdef extern from "<atcoder/dsu>" namespace "atcoder" nogil:
    cdef cppclass dsu:
        dsu(int n)
        int merge(int a, int b)
        bool same(int a, int b)
        int leader(int a)
        int size(int a)
        vector[vector[int]] groups()
from cython.parallel cimport prange
from libc.stdio cimport getchar, putchar
cdef inline int read() nogil:
    cdef int b, c = 0
    while 1:
        b = getchar() - 48
        if b < 0: break
        c = c * 10 + b
    return c
cdef int i
cdef dsu *d = new dsu(read())
for i in prange(read(), nogil=1):
    if read():
        if d.same(read(), read()): putchar(49)
        else: putchar(48)
        putchar(10)
    else: d.merge(read(), read())
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

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

const ll maxs = 1e6+5;
const ll lmaxs = 22;
ll mod = 1e9+7;
ll oo = 1e15;

#define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define I insert
#define endl '\n'


void pre(){

}

vector<ll> div(ll n){
    vector<ll> res;
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            res.pb(i);
            if(i != n/i)
                res.pb(n/i);
        }
    }
    sort(res.begin(),res.end());
    return res;
}

void solve(){
    ll n;
    cin>>n;
    ll ans=0;
    vector<ll> DIV_N = div(n);
    for(auto k : DIV_N){
        if(k==1)
            continue;
        ll m = n;
        while(m%k==0) m/=k;
        if(m%k==1)ans++;
    }
    vector<ll> DIV_N_1 = div(n-1);
    ans += DIV_N_1.size();
    ans--; // for 1;
    cout << ans;
}

int main(){
    
    IOS;
    pre();
    ll T = 1;
    //cin>>T;
    while(T--){
        solve();   
    }
    return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<bitset>
#include<set>
#define N (1000010)
#define P (1000000007)
#define M ()
#define inf (0x7f7f7f7f)
#define rg register int
#define Label puts("NAIVE")
#define spa print(' ')
#define ent print('\n')
#define rand() (((rand())<<(15))^(rand()))
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
typedef long double ld;
typedef long long LL;
typedef unsigned long long ull;
using namespace std;
namespace fastIO1{
	inline char read(){
		static const int IN_LEN=1000000;
		static char buf[IN_LEN],*s,*t;
		return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
	}
	template<class T>
	inline void read(T &x){
		static bool iosig;
		static char c;
		for(iosig=false,c=read();!isdigit(c);c=read()){
			if(c=='-')iosig=true;
			if(c==-1)return;
		}
		for(x=0;isdigit(c);c=read())x=((x+(x<<2))<<1)+(c^'0');
		if(iosig)x=-x;
	}
	inline char readc(char &c){
		for(c=read();!isalpha(c)&&!isdigit(c);c=read())
		if(c==-1)return 0;
	}
	const int OUT_LEN = 10000000;
	char obuf[OUT_LEN],*ooh=obuf;
	inline void print(char c){
		if(ooh==obuf+OUT_LEN)fwrite(obuf,1,OUT_LEN,stdout),ooh=obuf;
		*ooh++=c;
	}
	template<class T>
	inline void print(T x){
		static int buf[30],cnt;
		if(x==0)print('0');
		else{
			if(x<0)print('-'),x=-x;
			for(cnt=0;x;x/=10)buf[++cnt]=x%10+48;
			while(cnt)print((char)buf[cnt--]);
		}
	}
	inline void flush(){fwrite(obuf,1,ooh-obuf,stdout);}
}
namespace fastIO2{
	template<class T>
	inline void read(T &x){
		static bool iosig;
		static char c;
		for(iosig=false,c=getchar();!isdigit(c);c=getchar()){
			if(c=='-')iosig=true;
			if(c==-1)return;
		}
		for(x=0;isdigit(c);c=getchar())x=((x+(x<<2))<<1)+(c^'0');
		if(iosig)x=-x;
	}
}
using namespace fastIO1;
int n,f[N][3],ans,jc[N],inv[N];
int C(int n,int m){
	return 1ll*jc[n]*inv[m]%P*inv[n-m]%P;
}
int ksm(int a,int p){
	int res=1;
	while(p){
		if(p&1)res=1ll*res*a%P;
		a=1ll*a*a%P,p>>=1;
	}
	return res;
}
int main(){
	read(n),jc[0]=inv[0]=1,f[0][0]=1;
	for(int i=1;i<=n;i++)jc[i]=1ll*jc[i-1]*i%P,inv[i]=ksm(jc[i],P-2);
	for(int i=1;i<=n;i++)
	for(int j=0;j<3;j++)for(int k=0;k<3;k++)
	if(j!=k)(f[i][j]+=f[i-1][k])%=P;
	int INV=ksm(ksm(3,n-1),P-2);
	for(int i=1;i<=n;i++){
//		cout<<f[i][1]<<endl;
		int F=1ll*C(n,i)*f[i][1]%P*INV%P;
		(ans+=1ll*F*ksm(3,P-2)%P*ksm(n,P-2)%P*ksm(i,P-2)%P)%=P;
	}
	cout<<ans;
}

Measured memory_bytes: 20736
import sys

def cross(p0, p1, p2):
  dx1, dx2 = p1[0] - p0[0], p2[0] - p0[0]
  dy1, dy2 = p1[1] - p0[1], p2[1] - p0[1]
  return dy2 * dx1 - dy1 * dx2
 
for line in iter(sys.stdin.readline, ''):
  l = [float(r) for r in line.split(',')]
  a, b, c, d = l[0:2], l[2:4], l[4:6], l[6:8]
  print 'YES' if (cross(a, c, b) * cross(a, c, d)) < 0 and (cross(b, d, a) * cross(b, d, c) < 0) else 'NO'

Measured memory_bytes: 4272
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int cnt[111];
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N; cin >> N;
  int x[N], y[N];
  FOR(i,0,N) cin >> x[i] >> y[i];
  int MAX = 200000;
  FOR(i,0,MAX){
    double theta = 2 * M_PI * i / MAX;
    double mx = -2e9;
    int k = 0;
    FOR(j,0,N){
      if(mx < x[j]*cos(theta)+y[j]*sin(theta)){
        k = j;
        mx = x[j]*cos(theta)+y[j]*sin(theta);
      }
    }
    cnt[k]++;
  }
  FOR(i,0,N){
    cout << setprecision(20) << (double) cnt[i] / MAX << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef long  l;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
const int INF=1000000001;
const double PI=3.141592653589;


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

  return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ref(i,x,y)for(int i=x;i<=y;++i)
#define def(i,x,y)for(int i=x;i>=y;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)x.size())
typedef vector<int> vint;
typedef pair<int,int> PII;
int read(){
	char c=getchar();int d=0,f=1;
	for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
	for(;c>='0'&&c<='9';d=d*10+c-48,c=getchar());
	return d*f;
}
const int N=200010;
const int mod=998244353;
int n,m,q;
vector<PII> q0,q1,qq;
int fa[N];
int ask(int x){return fa[x]==x?x:fa[x]=ask(fa[x]);}
int main(){
	n=read(),m=read(),q=read();
	ref(i,1,q){
		int x,y,z;x=read()+1,y=read()+1,z=read();
		if(z==0)q0.pb(mp(x,y));
		if(z==1)q1.pb(mp(x,y));
	}
	ref(i,1,n)fa[i]=i;
	ref(i,0,SZ(q0)-1){
		int x=q0[i].fi,y=q0[i].se;
		x=ask(x);y=ask(y);
		if(x!=y)fa[y]=x,qq.pb(q0[i]);
	}
	q0=qq;
	if(SZ(q1)){
		vector<int> pp;
		ref(i,1,n)if(fa[i]==i)pp.pb(i);
		ref(i,0,SZ(q1)-1){
			if(ask(q1[i].fi)==ask(q1[i].se)){
				cout<<"No"<<endl;
				return 0;
			}
		}
		if(SZ(pp)==2){
			cout<<"No"<<endl;
			return 0;
		}
		long long up=1LL*SZ(pp)*(SZ(pp)-1)/2+SZ(qq);
		//cout<<SZ(pp)<<" "<<SZ(qq)<<endl;
		if(m>=n&&m<=up)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}else{
		vector<int> pp;
		ref(i,1,n)if(fa[i]==i)pp.pb(i);
		long long up=1LL*SZ(pp)*(SZ(pp)-1)/2+SZ(qq);
		if(m>=n-1&&m<=up)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
}

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

const int N = 100000;
const int W = 10000;

int get_capacity(int P, int n, int k, int w[]) {
  int i, weight;
  i = 0;
  
  for (int j = 0; j < k; j++) {
    weight = 0;
    while (weight + w[i] <= P) {
      weight += w[i++];
      if (i == n) return n;
    }
  }

  return i;
}

int get_P(int n, int k, int w[]) {
  int left, right, mid, cap;

  left = 0;
  right = N * W + 1;

  while (left + 1 < right) {
    mid = (left + right) / 2;
    cap = get_capacity(mid, n, k, w);
    if (cap >= n) right = mid;
    else left = mid;    
  }

  return right;
}

int main() {
  int n, k;
  int w[N];

  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> w[i];

  cout << get_P(n, k, w) << endl;

  return 0;
}


Measured memory_bytes: 3476
#include <stdio.h>
#include <random>
int D;
int c[26];
int l[367][26];
int s[366][26];
int t[366];
long long m;
int  p, q, d, k;
int md[3000001];
int mq[3000001];
int ans, bans;
unsigned long long a;
int main() {
	scanf("%d", &D);
	for (int i = 0; i < 26; i++) {
		scanf("%d", c + i);
	}
	for (int i = 1; i <= D; i++) {
		for (int j = 0; j < 26; j++) {
			scanf("%d", s[i] + j);
		}
	}
	std::mt19937_64 rd(468);
	for (int i = 1; i <= D; i++) {
		a = rd();
		t[i] = a % 26;
	}
	m = 3000000;
	for (int i = 0; i < 3000000; i++) {
		a = rd();
		md[i] = a % D + 1;
		mq[i] = a % 26;
	}
	for (int i = 1; i <= D; i++) {
		ans += s[i][t[i]];
		for (int j = 0; j < 26; j++) {
			l[i][j] = l[i - 1][j] + 1;
		}
		l[i][t[i]] = 0;
		for (int j = 0; j < 26; j++) {
			ans -= c[j] * l[i][j];
		}
	}
	for (long long i = 0; i < m; i++) {
		q = mq[i];
		d = md[i];
		p = t[d];
		if (p != q) {
			bans = ans;
			t[d] = q;
			ans -= s[d][p];
			ans += s[d][q];
			k = d;
			while (l[k][q] && k <= D) {
				ans -= c[q] * (k - d - l[k][q]);
				l[k][q] = k - d;
				k++;
			}
			k = d;
			do {
				ans -= c[p] * (l[k - 1][p] + 1 - l[k][p]);
				l[k][p] = l[k - 1][p] + 1;
				k++;
			} while (l[k][p] && k <= D);
			a = rd();
			if (ans < bans && (a % (m * m)) < 2 * m * i - i * i) {
				mq[i + 1] = p;
				md[i + 1] = d;
			}
		}
	}
	for (int i = 1; i <= D; i++) {
		printf("%d\n", t[i] + 1);
	}
}

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

N, K = map(int, input().split())
A = list(map(int, input().split()))

count = {}
for val in A:
    if val in count:
        count[val] += 1
    else:
        count[val] = 1

ans = 0
diff = len(set(A)) - K
if diff > 0:
    count_sorted = sorted(count.items(), key=lambda x:x[1])
    for k,v in count_sorted:
        ans += v
        diff -= 1
        if diff == 0:
            break

print(ans)

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

#define ll long long
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const ll mod=1000000007;

using namespace std;

string a,b;
int d[3010][3010];

void lcs(int n,int m){
    for (int i=0;i<=n;i++){
        for (int j=0;j<=m;j++){
            if (j==0 or i==0)d[i][j]=0;
            else if (a[i-1]==b[j-1])d[i][j]=d[i-1][j-1]+1;
            else d[i][j]=max(d[i-1][j],d[i][j-1]);
        }
    }
    string ans;
    int i=n,j=m;
    while(i>0 and j>0){
        if (a[i-1]==b[j-1]){
            i--,j--;
            ans+=a[i];
            continue;
        }
        if (d[i-1][j]>d[i][j-1])i--;
        else j--;
    }
    reverse(ans.begin(),ans.end());
    cout<<ans;
}

int main(){
    cin>>a>>b;
	lcs(a.size(),b.size());
	return 0;
}
/*
AGGTAB
GXTXAYB
*/


Measured memory_bytes: 35584
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double PI=acos(-1);
const double EPS=1e-10;

int main(){
	cin.tie(0);ios::sync_with_stdio(false);
	ll n;
	cin>>n;
	vector<P> a(n);
	rep(i,n){
		cin>>a[i].fi;
		a[i].se=i;
	}
	sort(begin(a),end(a),greater<P>());
	vector<vector<ll>> dp(n+1,vector<ll>(n+1,-inf));
	dp[0][0]=0;
	rep(i,n)rep(j,i+1){
		if(dp[i][j]==-inf) continue;
		chmax(dp[i+1][j+1],dp[i][j]+abs(a[i].se-j)*a[i].fi);
		chmax(dp[i+1][j],dp[i][j]+abs(a[i].se-(n-i+j-1))*a[i].fi);
	}
	ll ans=0;
	rep(j,n+1) chmax(ans,dp[n][j]);
	cout<<ans<<endl;
}

Measured memory_bytes: 34628
#include <algorithm>
#include <climits>
#include <functional>
#include <iterator>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#ifdef _MSC_VER
using ll = __int64;
using ull = unsigned __int64;
#else
using ll = long long int;
using ull = unsigned long long int;
#endif

// 二乗を計算する。
ll sq(ll x) { return x * x; }

// 領域内にいるか。
bool within(ll x, ll min, ll max) {
	return min <= x && x <= max;
}

// container の中から key より小さい値を見つける。
// 見つからない場合は container.end() を返す。
template<typename T>
typename T::iterator less_than(T& container, typename T::key_type& key) {
	typename T::iterator prev = container.lower_bound(key);
	if (prev == container.begin()) prev = container.end();
	else prev--;
	return prev;
}

// container の中から key より大きい値を見つける。
// 見つからない場合は container.end() を返す。
template<typename T>
typename T::iterator greater_than(T& container, typename T::key_type& key) {
	return container.upper_bound(key);
}

// b^e (mod m) を求める
ll modpow(ll b, ll e, ll m) {
	ll result = 1;
	while (e > 0) {
		if ((e & 1) == 1) result = (result * b) % m;
		e >>= 1;
		b = (b * b) % m;
	}
	return result;
}


// ここから解法


int main(void) {
	int N, L;
	
	cin >> N >> L;

	int sum = 0;
	for(int i = 1; i <= N; ++i) {
		sum += L + i - 1;
	}

	int sum_orig = sum;
	int diff_min = 1000000;
	int ans = sum;
	for (int i = 1; i <= N; ++i) {
		int t = L + i - 1;
		sum -= t;
		int diff = abs(sum - sum_orig);
		if (diff < diff_min) {
			ans = sum;
			diff_min = diff;
		}
		sum += t;
	}

	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<long long,long long>
#define vl vector<long long>
#define vll vector<pll>
#define vi vector<int>
#define vii vector<pii>
#define sws ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
#define tcase int tt; cin>>tt; while(tt--)
#define tcase2 int tt; cin>>tt; for(int qq=1;qq<=tt;qq++)
using namespace std;
typedef long long int ll;
typedef  unsigned long long int ull;
typedef long double ld;
const int MAX = 1000010;
const int MOD2 = 998244353;
const int MOD = 1000000007; 
const int INF = 1e8;    
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ld EPS = 1e-7;
// Extra
#define forn(i, n) for(int i = 0; i < (int)n; i++)
#define forne(i, a, b) for(int i = a; i <= b; i++)
#define all(x) x.begin(), x.end()   
#define trav(a, x) for(auto& a : x)
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr<< *it << " = " << a << endl;
	err(++it, args...);
}
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main()
{
    sws
   ll n;
   cin>>n;
    map<int,int> m;
    ll sum=0;
    forn(i,n){
        int k;
        cin>>k;
        sum+=k;
        m[k]++;
    }
    int q;
    cin>>q;
    forn(i,q)  
    {
        int b,c;
        cin>>b>>c;
        sum+=(c-b)*m[b];
        m[c]+=m[b];
        m[b]=0;
        cout<<sum<<endl;
    }
    return 0;
}


Measured memory_bytes: 8072
#include <stdio.h>
using namespace std;

int main() {
    
    int w, h, x, y, r;
    
    scanf("%d %d %d %d %d", &w, &h, &x, &y, &r);
    
    if((x >= r && x <= w-r) && (y >= r && y <= h-r))
        printf("Yes\n");
    else{
        printf("No\n");
    }
}



Measured memory_bytes: 2692
#include<bits/stdc++.h>
#define ll long long 

#define maxn 10005
using namespace std;
ll a[maxn][3]={0};
string s[maxn];
string st="";
int main(){
	ll n;
	cin>>n;
	
	for(ll i =0;i<n;i++){
	cin>>s[i];
	if(s[i][0] == 'B')
	   a[i][0]++;
	if(s[i][s[i].size()-1]=='A')
	   a[i][1]++;
	   }
	   
	ll flag = 0;
	
	for(ll i=0;i<n;i++){
		if(a[i][0] == 0&&a[i][1]!=0){
			flag = 1;
			st+=s[i];
			a[i][2] = -1;
			break;
		}
	}
	
	ll q = 0;
	//1
	if(flag == 1){
		for(ll i=0;i<n;i++){
			if(a[i][2] == -1){
				continue;
			}
			else{
				if(a[i][0]!=0&&a[i][1]!=0){
					st+=s[i];
					a[i][2] = -1;
				}
			}
		}
		for(ll i=0;i<n;i++){
			if(a[i][2]==-1){
				continue;
			}
			else{
			if(a[i][0]!=0){
				st+=s[i];
				a[i][2]=-1;
				break;
			}	
			}
		}
		for(ll i=0;i<n;i++){
			if(a[i][2]==-1){
				continue;
			}
			else{
				if(q%2==0){
					if(a[i][1]!=0){
						st+=s[i];
						a[i][2] =-1;
						i=-1;
						q++;
					}
				}
				else{
					if(a[i][0]!=0){
						st+=s[i];
						a[i][2]=-1;
						i=-1;
						q++;
					}
				}
			}
		}
		for(ll i=0;i<n;i++){
			if(a[i][2]!=-1){
				st+=s[i];
				a[i][2]=-1;
			}
		}
	}
	
	
	//2
	if(flag ==0){
		for(ll i=0;i<n;i++){
			if(a[i][1]!=0&&a[i][2]!=-1){
				st+=s[i];
				a[i][2] =-1;
				break;
			}
		}
		for(ll i=0;i<n;i++){
			if(a[i][2]==-1){
				continue;
			}
			else{
				if(a[i][0]!=0&&a[i][1]!=0){
					st+=s[i];
					a[i][2]=-1;
				}
			}
		}
		for(ll i=0;i<n;i++){
			if(a[i][2]==-1){
				continue;
			}
			else{
				if(a[i][0]!=0){
					st+=s[i];
					a[i][2]=-1;
				}
			}
		}
		for(ll i=0;i<n;i++){
			if(a[i][2]!=-1){
				st+=s[i];
				a[i][2]=-1;
			}
		}
	}
	
	
	
	ll num =0;
	for(ll i=0;i<st.size()-1;i++){
		if(st[i]=='A'&&st[i+1]=='B'){
			num++;
		}
	}
	cout<<num<<endl;
	return 0;
}

Measured memory_bytes: 1152
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws IOException{
        final BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String str;
        int a[]=new int[26];
        while((str=br.readLine())!=null){
         
        str=str.toLowerCase();
         
        for(int i=0;i<str.length();i++){
            char ch=str.charAt(i);
            if(ch<='z'&&ch>='a') a[ch-97]++;
        }
        }
        for(int i=0;i<26;i++){
            System.out.println((char)('a'+i) +" : "+a[i]);
        }
         
         
    }
}

Measured memory_bytes: 24160
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<vector>
#include<tuple>
#include<sstream>
#include<functional>
#include<list>
#include<queue>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> p;
typedef pair<int, pair<int, pair<int, int>>> PP;
typedef vector<int> vec;
using Graph = vector<vector<int>>;
using graph = vector<vector<ll>>;

const long long INF = 1LL << 60;
const int inf = 1e9;
const long long MOD = 1e9+7;

ll modpow(ll a, ll b, ll mod) {
	ll res = 1;
	while (b) {
		if (b & 1)res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

int main() {
	vector<ll> v(4),V;
	rep(i, 4)cin >> v[i];
	V.push_back(v[0] * v[2]);
	V.push_back(v[0] * v[3]);
	V.push_back(v[1] * v[2]);
	V.push_back(v[1] * v[3]);
	sort(all(V));
	cout << V[3] << endl;;
	return 0;
}

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

using namespace std;

int main(){
  int N;
  cin >> N;
  
  int min = 200005;
  int count = 0;
  vector<int> p(N);
  for(int i=0; i<N; i++){
    cin >> p[i];
    if(min > p[i]){
      min = p[i];
      ++count;
    }
  }
  
  cout << count;
  return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<iomanip>
#include<math.h>
using namespace std;
int gcd(int a,int b){
    int g;

    while(a!=b){
        if(a>b){
            a-=b;
        }
        else{
            b-=a;
        }
    }

    return a;
    
}

int main(){
    int n;
    int i,j,k;//preparation for
    int64_t s;

    cin>>n;
    s=0;

    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            for(k=1;k<=n;k++){
                s+=gcd(gcd(i,j),k);
            }
        }
    }

    cout<<s;
    
    return 0;
}

Measured memory_bytes: 3620
N = int(input())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    a.sort(reverse = True)
    return a

a = prime_factorize(n = N)
ans = 'Yes'


if len(a) == 0:
    if N > 9:
        ans = 'No'
elif len(a) > 4:
    if N / 8 > 9:
        ans = 'No'
elif len(a) == 3:
    if a[1] * a[2] > 9:
        ans = 'No'
else:
    n = N
    b = []
    for i in a:
        n = n / i
        b.append(n)

    if a[0] > 9:
        ans = 'No'
    if N > 81:
        ans = 'No'
    
print(ans)


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

using namespace std;
typedef long long ll;
typedef vector<ll> vl ;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;

#define rep(i,N) for(int i=0; i < (int)N; i++)
#define all(v) (v).begin(),(v).end()

const int INF = 100000002;

int main(){
	int n, k, c; cin >> n >> k >> c;
	string s; cin >> s;
	vector<int> l(k), r(k);
	int cnt = 0;
	int day = 1;
	while(cnt<k){
		if(s[day-1] == 'x') day ++;
		else{
			l[cnt] = day;
			day += c+1;
			cnt ++;
		}
	}

	cnt = k-1;
	day = n;
	while(cnt>=0){
		if(s[day-1] == 'x') day --;
		else{
			r[cnt] = day;
			day -= c+1;
			cnt --;
		}
	}
	//rep(i, k) cout << l[i] << " " << r[i] << endl;
	rep(i,k){
		if(l[i]==r[i]) cout << l[i] << endl;
	}
}

Measured memory_bytes: 3332
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;

struct edge {
    int to, cost;
    edge(){}
    edge(int _to, int _cost) : to(_to), cost(_cost) {}
};
const int INF = 1e15;
typedef vector<vector<edge>> Graph;

int N, M, L, K, s, t;
vector<bool> canFreeze;
Graph G;

VV dijkstra() {
    priority_queue<TUPLE, vector<TUPLE>, greater<TUPLE>> que;   // cost, vertex, life
    VV d(N, V(M + 1, INF));
    d[s][M] = 0;
    que.push(TUPLE(0, s, M));

    while (!que.empty()) {
        int c, v, m;
        tie(c, v, m) = que.top(); que.pop();
        if (d[v][m] < c) continue;

        // charge
        if (canFreeze[v]) {
            rep2(nm, m + 1, M + 1) {
                int nc = c + (nm - m);
                if (d[v][nm] > nc) {
                    d[v][nm] = nc;
                    que.push(TUPLE(nc, v, nm));
                }
            }
        }

        // move
        for (auto e : G[v]) {
            int nv = e.to;
            int nm = m - e.cost;
            int nc = c + e.cost;
            if (nm < 0) continue;  // die
            if (d[nv][nm] > nc) {
                d[nv][nm] = nc;
                que.push(TUPLE(nc, nv, nm));
            }
        }
    }
    return d;
}

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

    while (cin >> N >> M >> L >> K >> s >> t, N) {
        canFreeze.clear();
        canFreeze.resize(N, false);
        canFreeze[s] = canFreeze[t] = true;
        rep(i, L) {
            int l;
            cin >> l;
            canFreeze[l] = true;
        }

        G.clear();
        G.resize(N);
        rep(i, K) {
            int x, y, c;
            cin >> x >> y >> c;
            G[x].emplace_back(y, c);
            G[y].emplace_back(x, c);
        }

        auto d = dijkstra();
        int ans = INF;
        rep(j, M + 1) ans = min(ans, d[t][j]);

        // rep(i, N) {
        //     rep(j, M + 1) {
        //         cout << (d[i][j] == INF ? -1 : d[i][j]) << " ";
        //     }
        //     cout << endl;
        // }

        if (ans == INF) {
            cout << "Help!" << endl;
        } else {
            cout << ans << endl;
        }

        // cout << endl;

    }

}

Measured memory_bytes: 3492
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            try
            {
                Solve.Answer();
            }
            catch (Exception ex)
            {
                WriteLine(ex.ToString());
            }
        }
    }

    public class Solve
    {
        public static void Answer()
        {
            var KN = IO_ShortCut.ReadSplitInt;
            var K = KN[0];
            var N = KN[1];
            var A = IO_ShortCut.ReadSplitInt;

            var ans = 1000010;
            for (int i = 0; i < N; i++)
            {
                if (i == 0)
                {
                    ans = ans > A.Last() - A.First() ? A.Last() - A.First() : ans;
                    continue;
                }
                ans = ans > K - (A[i] - A[i - 1]) ? K - (A[i] - A[i - 1]) : ans;
            }
            WriteLine(ans);
        }
    }

    public class IO_ShortCut
    {
        #region Input
        public static string ReadString => ReadLine();
        public static int ReadInt => int.Parse(ReadLine());
        public static long ReadLong => long.Parse(ReadLine());
        public static double ReadDouble => double.Parse(ReadLine());

        public static List<string> ReadSplitString => ReadLine().Split().ToList();
        public static List<int> ReadSplitInt => ReadLine().Split().Select(s => int.Parse(s)).ToList();
        public static List<long> ReadSplitLong => ReadLine().Split().Select(s => long.Parse(s)).ToList();
        public static List<double> ReadSplitdouble => ReadLine().Split().Select(s => double.Parse(s)).ToList();
        #endregion

        #region Output
        public static void OutJoinSpace<T>(IEnumerable<T> list) => WriteLine(string.Join(" ", list));
        #endregion
    }

    public class Mod
    {
        // 割る数の定義
        private readonly static long M = 1000000007;

        // 足し算?
        public static long Add(long a, long b)
        {
            var result = a + b;
            if (a + b < 0)
                return result % M == 0 ? result % M : result % M + M;
            else if (a + b >= M)
                return result % M;
            else
                return result;
        }
        // 引き算
        // 割られる数が負になると余りの定義的にダメなので実装
        public static long Sub(long a, long b) => (a - b) % M >= 0 ? (a - b) % M : (a - b) % M + M;
        // 掛け算
        //    public static long Multi(long a, long b)
        //    {

        //    }
    }

}

Measured memory_bytes: 34780
from collections import deque
k = int(input())
d = deque([1,2,3,4,5,6,7,8,9])

ans = []
while len(ans) < k:
    a = d.popleft()
    ans.append(a)
    l = [a%10-1, a%10, a%10+1]
    for i in l:
        if i==-1 or i==10:
            continue
        d.append(a*10 + i)

print(ans[k-1])

Measured memory_bytes: 16628
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define REP(i,m,n) for(ll i=(ll)(m) ; i < (ll) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define square(x) pow(x 2.0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define max_queue(x) priority_queue<x>
#define min_queue(x) priority_queue<x, vector<x>, greater<x>>
#define big_sort(v) sort(all(v), [](int a, int b) { return a > b; })//大きい順にソート
using ll = long long;
using vi = vector<ll>;
using vvi = vector<vi>;
using vs = vector<string>;
// aよりもbが大きいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
/*
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
*/
int main() {
  ll x,i=0,t;
  cin >> x;
  map<ll,ll> mp;
  while(true){
    t=i*i*i*i*i;
    if(mp.count(t-x)){
      cout << i << " " << mp[t-x] << endl;
      return 0;
    }
    mp[t]=i;
    mp[(-1)*t]=(-1)*i;

    i++;
  }
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n; i>-1; --i)
#define ALL(a) (a).begin(),(a).end()
#define INIT(a,n,x); REP(i,(n)){ (a)[i]=(x); }
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define INIT2(a,n,m,x); REP(i,(n)){ REP(j,(m)){(a)[i][j]=(x);} }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }
#define LINY "YES\n"
#define Liny "Yes\n"
#define LINN "NO\n"
#define Linn "No\n"
#define umap unordered_map
//cout << setfill('0') << right << setw(4) << 12; // "0012"

ll min(ll x,ll y){return (x<y ? x:y);}
ll max(ll x,ll y){return (x>y ? x:y);}
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
int keta_wa(ll x){ if(x<10){return x;} else{return keta_wa(x/10) + x%10;} }
int ctoi(char c){ return ( (c>='0' && c<='9')? c - '0': 0 );}
ll gcd(ll a,ll b){if(a<b)swap(a,b); return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){if(a<b){swap(a,b);} return a*b /gcd(a,b);}

int main(){
  int N,K; cin>>N>>K;
  string s; cin>>s;
  s[K-1] += ('a'-'A');
  cout <<s <<"\n";
}

Measured memory_bytes: 256
n=int(input())
s=[input() for i in range(n)]
m=int(input())
t=[input() for i in range(m)]
ans=0
for i in range(n):
	tmp=0
	for j in range(n):
		if s[i]==s[j]:
			tmp+=1
	for j in range(m):
		if s[i]==t[j]:
			tmp-=1
	ans=max(ans,tmp)
print(ans)
		

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)  
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){

  int a,b,c;
  cin>>a>>b>>c;
  int ans = 0;
  ans = b/a;
  cout<<min(ans,c)<<endl;


 

  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>

#define INF 1e18
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> PP; 
int dx[4]={0,-1,0,1};
int dy[4]={1,0,-1,0};
int fie[510][510];
int dist[2][510][510];
int w,h;
vector<PP> vec;
int sx,sy,gx,gy;
typedef long long ll;

void bfs(int y=-1,int x=-1){
	queue<P> que;
	int type=0;
	if(y==-1)type=1;
	memset(dist[type],-1,sizeof(dist[type]));
	if(type==0){
		dist[type][y][x]=0;
		que.push(P(y,x));
	}else{
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				if(fie[i][j]==1){
					dist[type][i][j]=0;
					que.push(P(i,j));
				}
			}
		}
	}
	while(que.size()){
		P p=que.front();
		que.pop();
		for(int i=0;i<4;i++){
			int nx=p.second+dx[i],ny=p.first+dy[i];
			if(abs(fie[ny][nx])!=1 && dist[type][ny][nx]==-1){
				dist[type][ny][nx]=dist[type][p.first][p.second]+1;
				que.push(P(ny,nx));
			}
		}
	}
}

ll cnt=0;
ll all=0;
ll okave=0;
ll ngave=0;

long double calc(int v){
	if((dist[0][sy][sx]!=-1 && dist[0][sy][sx]<=dist[1][sy][sx]+v) || dist[1][sy][sx]==-1)return dist[0][sy][sx];
	else{
		if(cnt==0)return INF;
		long double va=(long double)okave/all;
		va*=(double)1.0*all/cnt;
		long double vb=(long double)ngave/((long double)(all-cnt));
		vb*=(long double)1.0*all/cnt;
		vb-=(long double)ngave/((long double)(all-cnt));
		return (long double)va+vb+dist[1][sy][sx];
	}
}

int main(void){
	scanf("%d%d%*c",&w,&h);
	memset(fie,0,sizeof(fie));
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			char c;
			scanf("%c",&c);
			if(c=='#')fie[i][j]=-1;
			if(c=='s')sy=i,sx=j;
			if(c=='g')gy=i,gx=j;
			if(c=='*')fie[i][j]=1;
		}
		scanf("%*c");
	}
	bfs(gy,gx);
	bfs();
	if(dist[1][sy][sx]==-1 || (dist[0][sy][sx]<=dist[1][sy][sx] && dist[0][sy][sx]!=-1)){
		printf("%.10f\n",(double)dist[0][sy][sx]);
		return 0;
	}
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(fie[i][j]==0 && (i!=gy || j!=gx)){
				all++;
				if(dist[0][i][j]!=-1 && dist[1][i][j]!=-1)vec.push_back(PP(dist[0][i][j]-dist[1][i][j],P(i,j)));
				else if(dist[0][i][j]==-1)ngave+=dist[1][i][j];
				else{
					okave+=dist[0][i][j];
					cnt++;
				}
			}
		}
	}
	sort(vec.begin(),vec.end());
	long double res=INF;
	for(int i=0;i<vec.size();i++){
		ngave+=dist[1][vec[i].second.first][vec[i].second.second];
	}
	for(int i=0;i<=vec.size();i++){
		if(i==vec.size())res=min(res,calc(514514));
		else if(all!=cnt || cnt!=0)res=min(res,calc(vec[i].first));
		if(i!=vec.size()){
			ngave-=dist[1][vec[i].second.first][vec[i].second.second];
			cnt++;
			okave+=dist[0][vec[i].second.first][vec[i].second.second];
		}
	}
	printf("%.10f\n",(double)res);
	return 0;
}

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

int n,m,f[N];
vector<int> q[N];

void modify(int x,int t){
	if (x>m) return;
	f[x]+=t;modify(x+(x&-x),t);
}

int query(int x){
	if (!x) return 0;
	return f[x]+query(x-(x&-x));
}

int read(){
	int x=0,f=1;char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-f;
	for (;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x*f;
}
 
int main(){
	n=read();m=read();
	for (int i=1;i<=n;i++){
		int l=read(),r=read();
		q[r-l+1].push_back(l);
	}
	for (int i=1;i<=m;i++){
		for (int j=0;j<(int)q[i].size();j++)
			modify(q[i][j],1),modify(q[i][j]+i,-1);
		n-=q[i].size();
		int ans=0;
		for (int j=i;j<=m;j+=i)
			ans+=query(j);
		printf("%d\n",n+ans);
	}
	return 0;
}

Measured memory_bytes: 30592
import math
N,K=[int(i) for i in input().split()]
res=0
for i in range(1,N+1):
	if i<K:
		po=math.ceil(math.log2(K/i))
		j=math.pow(0.5,po)
	else:
		j=1
	res+=j
print(res/N)

Measured memory_bytes: 3060
#define debug_interval ','
#define dump_interval ' '
#define debug_toggle 1
//{
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INT_MAX LLONG_MAX
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define fi first
#define se second
#define mp make_pair
#define rev reverse
#define dans dump(ans)
#define MOD 1000000007
#define amp(v,n) (v).count(n)?v[n]++:v[n]=1;

//{
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class...A> inline void dump(){cout<<endl;}
template<class...A> inline void dump_rest() {cout<<endl;}
template<class T, class...A> inline void dump_rest(const T& first, const A&... rest){cout<<dump_interval<<first;dump_rest(rest...);}
template<class T,class...A> inline void dump(const T&first,const A&...rest){cout<<first;dump_rest(rest...);}
template<class...A> inline void debug(){cerr<<endl;}
template<class...A> inline void debug_rest() {cerr<<endl;}
template<class T, class...A> inline void debug_rest(const T& first, const A&... rest){cerr<<debug_interval<<first;debug_rest(rest...);}
template<class T,class...A> inline void debug(const T&first,const A&...rest){if(debug_toggle)cerr<<first,debug_rest(rest...);}
//}

typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
template<int m>class mint{private:int i;public:mint() : i(0){}mint(int i): i((i%m+m)%m){}mint operator+(const mint& o){return o.i+i;}mint operator*(const mint& o){return o.i*i;}mint operator-(){return -i;}operator int() {return i;}};

main(){
	int a,b;
	cin>>a>>b;
	dump(a+b/2);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N;
vector<ll> G[100005];
vector<ll> C[100005];
ll A[100005];
ll root;
void dfs(ll id, ll pr){
  for( ll to : G[id] ){
    if( to == pr ) continue;
    C[id].push_back( to );
    dfs( to, id );
  }
}

bool valid(){
  queue<ll> q;
  vector<ll> r;
  q.push( root );
  while( !q.empty() ){
    ll p = q.front(); q.pop();
    r.push_back( p );
    for(ll to : C[p] ) 
      q.push( to );
  }

  reverse( r.begin(), r.end() );
    
  for( ll id : r ){
    if( C[id].empty() ) continue;
    ll sum = 0;
    ll maxi = 0;
    for(ll to : C[id] ){
      sum += A[to];
      maxi = max( maxi, A[to] );
    }
    ll k = sum - A[id];
    if( k < 0 ) return false;
    if( sum-maxi < k ) return false;
    if( A[id] < sum-2LL*k ) return false;
    A[id] = sum - 2LL * k;
    if( A[id] < 0 ) return false;
  }
  return A[root] == 0LL;
}

int main(){
  cin >> N;
  for(ll i=0;i<N;i++)
    cin >> A[i];
  for(ll i=0;i<N-1;i++){
    ll a,b;cin >> a >> b; --a; --b;
    G[a].push_back( b );
    G[b].push_back( a );
  }

  if( N == 2 ){
    if( A[0] == A[1] ) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
  }
  
  for(ll i=0;i<N;i++)
    if( G[i].size() > 1 ){
      dfs( root = i, i ); break;
    }
  
  
  
  if( valid() ) cout << "YES" << endl;
  else cout << "NO" << endl;
}


Measured memory_bytes: 18428
import sys
input = sys.stdin.readline
N, K = (int(i) for i in input().split())
#B = [int(x) for x in stdin.readline().rstrip().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]

nc = N
for i in range(nc):
    if N < K:
        break
    else:
        N = N-(N//K)*K

for i in range(nc):
    if abs(N-K) < N:
        N = abs(N-K)
    else:
        break



print(N)


Measured memory_bytes: 38384
//↓見なくていいよ！ここから--------------------------------------------------
var read = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
var obj;
var inLine = [];
read.on('line', function(input){inLine.push(input);});
read.on('close', function(){
  obj = init(inLine);
  console.error("\n");
  var start = new Date();
  Main();
  var end = new Date() - start;
  
  myerr("time : " + (end) + "ms");
  myerr("memory : " + Math.round(process.memoryUsage().heapTotal / 1024) + "KB");
});
function nextInt(){return myconv(next(),1);} function nextStrArray(){return myconv(next(),2);}
function nextIntArray(){return myconv(next(),4);} function nextCharArray(){return myconv(next(),6);}
function next(){return obj.next();} function hasNext(){return obj.hasNext();}
function init(input){  
  var returnObj = {
    list : input, index : 0, max : input.length,
    hasNext : function(){return (this.index < this.max);},
    next : function(){if(!this.hasNext()){throw "ArrayIndexOutOfBoundsException これ以上ないよ";}else{var returnInput = this.list[this.index];this.index++;return returnInput;}}
  };
  return returnObj;
}
function myout(s){console.log(s);}
function myerr(s){console.error("debug:" + require("util").inspect(s,false,null));}
//[no]要素の扱い。数値型
//不明値、異常時:引数そのまま返す 1:数値へ変換
//2:半角SPで分割 4:半角SPで分割し、数値配列へ
//6:1文字で分割  7:1文字で分割し、数値配列へ
//8:半角SPで結合 9:改行で結合 0:文字なしで結合
function myconv(i,no){try{switch(no){case 1:return parseInt(i);case 2:return i.split(" ");case 4:return i.split(" ").map(Number);case 6:return i.split("");case 7:return i.split("").map(Number);case 8:return i.join(" ");case 9:return i.join("\n");case 0:return i.join("");default:return i;}}catch(e){return i;}}


//↑見なくていいよ！ここまで--------------------------------------------------
function Main(){
	var D = nextInt();
	var clist = nextIntArray();
	var output = new Array(D);
	for(var i = 0; i < D; i++){
		var list = nextIntArray();
		var max = -1;
		var maxIndex = -1;
		for(var j = 0; j < list.length; j++){
			if(max < list[j]){
				max = list[j];
				maxIndex = j;
			}
		}
		output[i] = maxIndex + 1;
	}
	myout(myconv(output,9));
}


Measured memory_bytes: 31176