akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(a,b,c) for(int a = (b); a <= (c); a++)
#define RFOR(a,b,c) for(int a = (b); a >= (c); a--)
#define all(x) (x).begin(), (x).end()
#define vi vector <int>
#define vvi vector <vi>
#define ll long long
#define vll vector <ll>
#define vvl vector <vll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ep emplace
#define fs first
#define sd second
using namespace std;

int main() {
    FIO;
    int n, x, y;
    cin >> n >> x >> y;
    vi ans(n);
    FOR(i,1,n) {
        FOR(j, i + 1,n) {
            int v = min({j - i, abs(x - i) + abs(j - y) + 1, abs(y - i) + abs(j - x) + 1});
            ans[v]++;
        }
    }
    FOR(i,1,n - 1) cout << ans[i] << '\n';
    return 0;
}

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

int main(){
  int N,T;
  cin >>N>>T;
  int t[N+100];
  for (int i=0;i<N;i++){
    cin >> t[i];
  }
  t[N]=2000000000;
  int total=0;
  for (int i=0;i<N;i++){
    if(t[i+1]-t[i]>=T){
      total=total+T;
    }
    else total=total+t[i+1]-t[i];
  }
  cout<<total<<endl;
  return 0;
}

    

Measured memory_bytes: 1024
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <iomanip>
#include <array>
#include <numeric>
#include <regex>
#include <bitset>
#include <deque>
#include <cassert>

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

const int INF = 1e9;
const double PI = acos(-1.0);
const ll MOD = 1e9 + 7;

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define debug(x) cout << #x << ": " << x << endl;
#define popcnt __builtin_popcount


int main() {
    int N;
    cin >> N;
    string num = to_string(N);
    int sum = 0;
    for (int i = 0; i < sz(num); i++) {
        sum += (num[i] - '0');
    }
    if(N%sum==0)
        puts("Yes");
    else
        puts("No");

    return 0;
}

Measured memory_bytes: 256
package main

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

func intSlice(str string) []int {
	splitted := strings.Split(str, " ")
	ret := make([]int, len(splitted))

	for i, str := range splitted {
		if strings.TrimSpace(str) != "" {
			n, _ := strconv.Atoi(str)
			ret[i] = n
		}
	}

	return ret
}

func main() {

	stdin := bufio.NewScanner(os.Stdin)

	// 一行目
	stdin.Scan()
	line1 := stdin.Text()
	ints1 := intSlice(line1)
	length := ints1[0]
	n := ints1[1]

	stdin.Scan()
	line2 := stdin.Text()

	var head string
	var tail string

	if n == 1 {
		head = ""
	} else {
		head = line2[:n-1]
	}
	c := strings.ToLower(line2[n-1 : n])
	if n == length {
		tail = ""
	} else {
		tail = line2[n:]
	}

	fmt.Printf("%s%s%s\n", head, c, tail)
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
void solve(){
	int a,b,c,k;
	cin>>a>>b>>c;
	cin>>k;
	int x=0,y=0;
	if(a>=b){
		x=ceil((log(a/b)/log(2)));
		if(a>=b*pow(2,x))x++;
	}
	b*=pow(2,x);
	if(b>=c){
		y=ceil((log(b/c)/log(2)));
		if(b>=c*pow(2,y))y++;
	}
	//cout<<x<<" "<<y<<"\n";
	if(x+y>k)cout<<"No\n";
	else cout<<"Yes\n";	
}
int main(){
	FASTIO
//	int t;
//	cin>>t;
//	while(t--)solve();
	solve();
	return 0;
}


Measured memory_bytes: 4052
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <queue>
# define MOD 1000000000+7
# define INF 1000000000
#define rep(i,rept)	for(ll i = 0; i<rept;i++)
typedef long long ll;
using namespace std;
long long int a = 0, b = 0, c = 0, ans = 0, x = 0, y = 0, z = 0, n = 0, m = 0, maxy = -999999, mini = 99999999, counter = 0, counter2 = 0, endp = 0, checker = 0;

std::vector <char> vec{}, vecsec{}, vecth{};
long long int iremono[100001], sec[100001];
long long int iremono2[100001],iremono3[100001], check[100001];
std::vector<long long int>kinds{}, kaku{};
char maze[1000][1000];
int sx, sy;
int gx, gy;

bool relation[1000][1000];
int twod[1001][1001];
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
bool okada = false, okada2 = false;
std::string output, output2, input, input2, input3;
char rev[100001];


int ctoi(const char c) {
	if ('0' <= c && c <= '9') return (c - '0');
	return -1;
}
unsigned long long int LCM(unsigned long long int a, unsigned long long int b) {
	unsigned long long int i, j;
	i = a; j = b;
	while (true) {

		c = i % j;
		i = j;
		if (c != 0) {

			j = c;

		}
		else {
			break;
		}
	}
	return j * (a / j) * (b / j);
}
int kaizyo(int k) {
	int sum = 1;
	for (int i = 1; i <= k; ++i)
	{
		sum *= i;
	}
	return sum;
}

int N, M;//はんい
int bfs() {
	queue<pair<int, int>> que;
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= M; j++) {
			twod[i][j] = INF;
		}
	}
	que.push(pair<int, int>(sx, sy));
	twod[sx][sy] = 1;
	while (que.size()) {
		pair<int, int> p = que.front();
		que.pop();
		if (p.first == gy && p.second == gx) {
			break;
		}
		for (int i = 0; i < 4; i++) {
			int nx = p.first + dx[i], ny = p.second + dy[i];
			if (1 <= nx && nx <= N && 1 <= ny && ny <= M && maze[nx][ny] != '#'&&twod[nx][ny] == INF) {
				que.push(pair<int, int>(nx, ny));
				twod[nx][ny] = twod[p.first][p.second] + 1;
			}
		}
	}
	return twod[gy][gx];
}
vector <int> g[100100];
int main()
{
	cin >> a;
	rep(i, a) {
		cin >> iremono[i];
	}
	rep(j, a) {
		cin >> iremono2[j];
	}
	rep(i, a) {
		kaku.push_back(iremono[i] - iremono2[i]);
}
	for (int bit = 0; bit < (1 << ((int)kaku.size())); bit++) {
		for (int i = 0; i < (int)kaku.size(); i++) {
			if (bit & (1 << i)) {
				counter += kaku[i];
			}
		}
		if (maxy < counter) {
			maxy = counter;
		}
		counter = 0;
	}
	cout << maxy << endl;
}


Measured memory_bytes: 6400
#include<bits/stdc++.h>
#define ll long long
#define fo(i,n) for(i=0;i<n;++i)
#define forr(i,n) for(i=n-1;i>=0;--i)
using namespace std;

ll gcd(ll a,ll b){while(a&&b)a>=b?a%=b:b%=a;return a+b;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

ll binary(ll b[],ll low, ll high, ll key){
    ll mid;
    while(low<=high){
            mid = (low+high)/2;
            if(b[mid]==key)return mid;
            else if(b[mid]<key)return binary(b,mid+1,high,key);
            else return binary(b,low,mid-1,key);
    }
    return -1;
}


int main(){
 ll n;
 cin>>n;
 ll i, a[n], b[n];
 fo(i,n){
    cin>>a[i];
    b[i] = a[i];
 }
 sort(b,b+n);
 ll counter = 0;
 ll pos;
 fo(i,n){
    if(i%2==0)
        continue;
    pos = binary(b,0,n-1,a[i]);
    if(pos%2==0)
        counter++;
 }
 cout<<counter<<endl;
 return 0;
}


Measured memory_bytes: 1792
X, Y, A, B, C = list(map(int, input().split()))
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
R = list(map(int, input().split()))

P.sort(reverse=True)
Q.sort(reverse=True)

P = P[:X]
Q = Q[:Y]

# P.sort()
# Q.sort()
# R.sort(reverse=True)

S = []
S = P + Q + R
S.sort(reverse=True)
# print(S)
S2 = S[:X+Y]
ans = sum(S2)
print(ans)

Measured memory_bytes: 23328
#include "bits/stdc++.h"
#include<assert.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define int long long
const int inf = 1e17;
const int mod = 1000000007;
typedef pair<int, int> P;
typedef pair<int, P> PP;

signed main() {
	int n; cin >> n;
	cout << n*(n - 1) / 2 << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;
import java.util.Arrays;

class Main {

  int comparisons = 0;

  public void merge(int[] A, int left, int mid, int right) {
    int n1 = mid - left;
    int n2 = right - mid;
    int[] L = new int[n1+1];
    int[] R = new int[n2+1];
    for (int i = 0; i < n1; i++) {
      L[i] = A[left + i];
    }
    for (int i = 0; i < n2; i++) {
      R[i] = A[mid + i];
    }
    L[n1] = Integer.MAX_VALUE;
    R[n2] = Integer.MAX_VALUE;
    int i = 0;
    int j = 0;
    for (int k = left; k < right; k++) {
      this.comparisons++;
      if (L[i] <= R[j]) {
        A[k] = L[i];
        i = i + 1;
      } else {
        A[k] = R[j];
        j = j + 1;
      }
    }
  }

  public void mergeSort(int[] A, int left, int right) {
    if (left + 1 < right) {
      int mid = (left + right) / 2;
      mergeSort(A, left, mid);
      mergeSort(A, mid, right);
      merge(A, left, mid, right);
    }
  }

  public static void display(int[] A) {
    StringBuilder s = new StringBuilder("");
    for (int i = 0; i < A.length - 1; i++) {
      s.append(A[i] + " ");
    }
    s.append(A[A.length - 1]);
    System.out.println(s);
  }

  public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    int n = s.nextInt();
    int[] A = new int[n];
    for (int i = 0; i < n; i++) {
      A[i] = s.nextInt();
    }
    Main x = new Main();
    x.mergeSort(A, 0, A.length);
    display(A);
    System.out.println(x.comparisons);
  }
}



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

int main(){
    int n;
     cin >> n;
     vector <ll> a(n);
     vector <ll> b(n+1,0);
     vector <ll> fans(n);
     rep(i,n){
         cin >> a[i];
        ++b[a[i]];
     }
    
    ll ans;
    ans=0;
    rep(i,n+1){
        ans+=(b[i]*(b[i]-1)/2);
    }



    rep(i,n){
        fans[i]=ans-(b[a[i]]-1);
    }

    rep(i,n){
    cout << fans[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 7296
// ------------------------------------
// Date:2018/ 3/ 5
// Problem:ABC 082 RoundUpTheMean a.cpp
//
// ------------------------------------

#include <bits/stdc++.h>

using namespace std;

#define EACH(i,a) for (auto&& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl

typedef long long ll;

static const int MOD = 1000000007;

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

  int a, b;
  cin >> a >> b;
  int sum = a + b;
  
  cout << (sum / 2 + (sum%2==0?0:1)) << endl;
  
  return 0;
}



Measured memory_bytes: 256
package main

import (
	"fmt"
)

func solve(s string) int {
	max := 0
	cnt := 0
	for _, c := range s {
		char := fmt.Sprintf("%c", c)
		if char == `R` {
			cnt++
		}
		if max < cnt {
			max = cnt
		}
		if char == `S` {
			cnt = 0
		}
	}
	return max
}


func main() {
	var s string
	fmt.Scan(&s)

	result := solve(s)
	fmt.Println(result)
}


Measured memory_bytes: 1832
#define m(a,b)(a<b?a:b)
r;main(c,a,n){for(gets(&c);r=~scanf("%d%d%d",&c,&a,&n);printf("%d\n",r+n+(c-n*2)/3))r=m(c,m(a,n)),c-=r,a-=r,n=m(c/2,a);}

Measured memory_bytes: 604
#include <stdio.h>
main() {
	char pass[4];
	int a=0;
	scanf("%s",&pass );
	for (int i= 0; i<3; i++) {
		if (pass[i]!=pass[i+1]) {
			continue;
		} else {
			a=1;
		}
	}
	if (a==1) {
		printf("Bad");
	} else  {
		printf("Good");
	}
}

Measured memory_bytes: 1700
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <set>
using namespace std;
#define rep(i,n) for(int i = 0, i##_len=(n); i < i##_len; ++i)
typedef long long ll;

vector<int> x;
vector<int> y;
int main(){
	string s;
	cin >> s;

	int X, Y;
	cin >> X >> Y;

	bool f = true;
	int num = 0;
	rep(i, s.size()){
		if(s[i] == 'F'){
			num++;
		}else{
			if(f){
				x.push_back(num);
			}else{
				y.push_back(num);
			}
			f = !f;
			num = 0;
		}
	}
	if(f){
		x.push_back(num);
	}else{
		y.push_back(num);
	}

	if(x.size() == 0){
		bool ans = (X == 0 && Y == 0);
		cout << (ans ? "Yes" : "No") << endl;
		return 0;
	}

	set<int> st;
	st.insert(x[0]);
	for(int i = 1; i < x.size(); i++){
		vector<int> v;
		for(auto& a: st){
			v.push_back(a + x[i]);
			v.push_back(a - x[i]);
		}
		st.clear();
		for(auto& a: v){
			st.insert(a);
		}
	}

	if(y.size() == 0){
		bool ans = (st.count(X) && Y == 0);
		cout << (ans ? "Yes" : "No") << endl;
		return 0;
	}
	set<int> st2;
	st2.insert(y[0]);
	st2.insert(-y[0]);
	for(int i = 1; i < y.size(); i++){
		vector<int> v;
		for(auto& a: st2){
			v.push_back(a + y[i]);
			v.push_back(a - y[i]);
		}
		st2.clear();
		for(auto& a: v){
			st2.insert(a);
		}
	}
	/*
	for(auto& a: st){
		cout << "stX:" << a << endl;
	}
	for(auto& a: st2){
		cout << "stY:" << a << endl;
	}
	*/
	bool ans = (st.count(X) && st2.count(Y));
	cout << (ans ? "Yes" : "No") << endl;
	return 0;
}


Measured memory_bytes: 640
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <locale.h>
int main()
{
    int a,b;
    scanf("%d %d",&a, &b);
    if(b>a){
        int tep = b;
        b=a;
        a=tep;
    }
    for(int i=0;i<a;i++){
        printf("%d",b);
    }
}



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

int main() {
  ll n;
  cin >> n;
  map<ll,ll> m;
  ll ans=0;

  for(ll i=1;i<=n;i++){
      ll a ;
      cin >> a;
      ans += m[i-a];
      m[i+a]++;

  }

  cout << ans << endl;
}

Measured memory_bytes: 26288
#!usr/bim/python
#! -*- coding: utf-8 -*-

hwd = raw_input()
hwd = hwd.split()
h,w,d = map(int,hwd)

if d % 2 == 0:
    for i in range(h):
        s = ""
        for j in range(w):
            if i%(2*d) < d/2:
                if i%d <= j%(2*d) and j%(2*d) < d-i%d:
                    s += "R"
                elif d-i%d <= j%(2*d) and j%(2*d) < d+i%d:
                    s += "Y"
                elif d+i%d <= j%(2*d) and j%(2*d) < 2*d-i%d:
                    s += "G"
                else:
                    s += "B"
            elif i%(2*d) < d/2*2:
                if (d-i)%d <= j%(2*d) and j%(2*d) < d-(d-i)%d:
                    s += "G"
                elif d-(d-i)%d <= j%(2*d) and j%(2*d) < d+(d-i)%d:
                    s += "Y"
                elif d+(d-i)%d <= j%(2*d) and j%(2*d) < 2*d-(d-i)%d:
                    s += "R"
                else:
                    s += "B"
            elif i%(2*d) < d/2*3:
                if i%d <= j%(2*d) and j%(2*d) < d-i%d:
                    s += "G"
                elif d-i%d <= j%(2*d) and j%(2*d) < d+i%d:
                    s += "B"
                elif d+i%d <= j%(2*d) and j%(2*d) < 2*d-i%d:
                    s += "R"
                else:
                    s += "Y"
            else:
                if (d-i)%d <= j%(2*d) and j%(2*d) < d-(d-i)%d:
                    s += "R"
                elif d-(d-i)%d <= j%(2*d) and j%(2*d) < d+(d-i)%d:
                    s += "B"
                elif d+(d-i)%d <= j%(2*d) and j%(2*d) < 2*d-(d-i)%d:
                    s += "G"
                else:
                    s += "Y"
        print s
else:
    for i in range(h):
        s = ""
        for j in range(w):
            if (i+j)% 2 == 0:
                s += "R"
            else:
                s += "Y"
        print s


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

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		if(B - A <= 2){
			Console.WriteLine(K + 1);
			return;
		}
		
		if(K + 1 <= A){
			Console.WriteLine(K + 1);
			return;
		}
		long tot = A;
		K -= A - 1;
		
		long rest = K / 2;
		tot += rest * (B - A);
		
		K -= rest * 2;
		if(K == 1) tot++;
		
		Console.WriteLine(tot);
		
	}
	long K, A, B;
	public Sol(){
		var d = rla();
		K = d[0]; A = d[1]; B = d[2];
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


Measured memory_bytes: 11220
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
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; }
const int INF=1001001001;
vector<pair<int64_t,int64_t>>prime_factorize(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p; 
}
int main() {
  string s;
  cin>>s;
  int N=s.size();
  for(int i=N-1;i>=0;i--){
    string t=s.substr(0,i);
    int v=t.size();
    if(t.substr(0,v/2)==t.substr(v/2)){
      cout<<v<<endl;return 0;
    }
  }
 return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <deque>
#include <queue>
#include <stack>
#include <numeric>
#include <cmath>
#include <map>
#include <set>
#define ull unsigned long long
#define ll long long
using namespace std;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int a=0,b=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='0'){a++;}
        else if(s[i]=='1'){b++;}
    }
    cout << min(a,b)*2 << endl;

    return 0;
}

Measured memory_bytes: 512
# Code for A - Fifty-Fifty
# Use input() to fetch data from STDIN
from collections import defaultdict

s = input()
m = defaultdict(int) 

for c in s:
    m[c] += 1

if len(m.keys()) != 2:
    print("No")
    exit()

if all([v == 2 for v in m.values()]):
    print("Yes")
    exit()

print("No")


Measured memory_bytes: 3316
n, q = map(int, input().split())
s = input()
t = [0]*(n+1)
for i in range(n):
    if s[i:i+2] == 'AC':
        t[i+1] = t[i]+1
    else:
        t[i+1] = t[i]

for _ in range(q):
    l,r = map(int, input().split())
    print(t[r-1]-t[l-1])

Measured memory_bytes: 6188
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:18:25 2019

@author: screamLab
"""

n = int(input())
s = input()
k = int(input())

mark = s[k - 1]
new = []
for i in range(n):
    new.append(s[i])
for i in range(n):
    if(new[i] != mark):
       new[i] = '*'
print(''.join(new))

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

int main(){
    int N, M;
    cin >> N >> M;
    int road[60]={0};
    for (int i=0; i<M; i++){
        int a, b;
        cin >> a >> b;
        road[a-1]++;
        road[b-1]++;
    }
    for (int i=0; i<N; i++){
        cout << road[i]<< endl;
    }
}



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

using namespace std;

long long dp[2][2019];

int main() {
    long long ans = 0;
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        int digit = s[i] - '0';
        for (int j = 0; j < 2019; j++) {
            dp[1][((j * 10) + digit) % 2019] += dp[0][j];
        }
        dp[1][digit]++;
        ans += dp[1][0];
        for (int j = 0; j < 2019; j++) {
            dp[0][j] = dp[1][j];
            dp[1][j] = 0;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3780
#include <stdio.h>

int main(void)
{
    int w, h, x, y, r;
    scanf("%d %d %d %d %d", &w, &h, &x, &y, &r);

    if ((r <= x) && (x <= w - r) && (r <= y) && (y <= h -r))
        printf("Yes\n");
    else
        printf("No\n");

    return 0;
}

Measured memory_bytes: 2684
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define irep(i, n) for (int i = (n); i >= 0; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 30;
int m[102][102]; 
int r[102][102];
int main() {
	int h,w;
	cin >> h >> w;
	rep(i,h) rep(j,w) {
		char c; cin >> c;
		m[i][j] = (c == '#');
	}
	
	rep(i,h) {
		rep(j,w) {
			if (i==0 && j == 0) r[i][j] = m[i][j];
			else {
				int p = i ? r[i-1][j]+(m[i][j]>m[i-1][j]) : 200;
				int q = j ? r[i][j-1]+(m[i][j]>m[i][j-1]) : 200;
				r[i][j] = min(p,q); 
			}
		} 
	}
	cout << r[h-1][w-1] << endl;
  return 0;
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long int
#define FIO  ios::sync_with_stdio(false); cin.tie(0);   cout.tie(0);
#define all(in) in.begin(), in.end()
typedef pair<ll, ll> pll;


void solve(){
    ll a, b, c, d;  cin >> a >> b >> c >> d;
    ll ans = max(a * c, a * d);
    ans = max(ans, b * c);
    ans = max(ans, b * d);
    cout << ans << endl;
}

int main(){
    FIO;
    ll t = 1;//   cin >> t;
    while(t--){
        solve();
    }

    return 0;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
int main() {
    ll n;
    cin >> n;
    vector<ll>a(n);
    for(ll i=0;i<n;i++){
        cin >> a[i];
    }
    sort(a.begin(),a.end());
    map<ll,ll>mp;
    for(ll i=0;i<n;i++){
        mp[a[i]]++;
    }
    bool ok=false;

    if(mp.size()==1){
        if(a[0]==0) ok=true;
    }
    else if(mp.size()==2){
        if(mp[0]==n/3&&mp[a[n-1]]==2*n/3&&n%3==0){
            ok=true;
        }
    }
    else if(mp.size()==3){
        ll x=0;
        for(auto p:mp){
            auto k=p.first;
            x^=k;
        }
        if(x==0&&n%3==0){
            bool b=true;
            for(auto p:mp){
                auto v=p.second;
                if(v!=n/3){
                    b=false;
                }
            }
            if(b) ok=true;
        }
    }
    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 8728
a = list(range(5))
a[0] = int(input())
a[1] = int(input())
a[2] = int(input())
a[3] = int(input())
a[4] = int(input())
k = int(input())
c = 0
for i in range(4):
    for j in range(1+i, 5):
        if(abs(a[i]-a[j])>k):
            c+=1
if(c>0):
    print(":(")
else:
    print("Yay!")

Measured memory_bytes: 3064
/**
*    created: 13.06.2020 21:27:52
**/

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
const int inf =1000000000;
/*
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i, n){
        cin >> a[i];
    }
    //k = min(k, 2 + (int)log2(n));
    for (int l = 1; l <= k;l++)
    {
        vector<int> b(n);
        rep(i,n){
        b[min(i + a[i]+1, n)] --;
        b[max(0, i - a[i])] ++;
        }
        bool ok = 1;
        for (int i = 1; i < n; i++)
        {
            b[i] += b[i - 1];
            ok &= b[i] == n;
            a[i] = b[i];
            }
            a[0] = b[0];
            if (ok)    break;
            /*
        rep(i,n)cout <<"b "<< b[i] << endl;
        k = min(k, 2 + (int)log2(n));
        for (int i = 1; i < k; i++)
        {
            vector<int> e(n);
            rep(i,n){
                e[i] = b[i];
            }
            rep(i, n)
            {
                //cout << "i  "<<i << endl;
                int x = c[i];
                int y = d[i];
                c[i] = min(i + e[i], n);
                d[i] = max(0, i - e[i]);
                for (int j = d[i]; j < y; j++){
                    b[j]++;
                // cout << "j,b[j] "<<j<<" "<<b[j] << endl;
                }
                for (int j = x+1; j <= c[i]; j++){
                    b[j]++;
                }
            }
        }
    }
    rep(i,n)cout << a[i] <<" ";
    cout << endl;
}
*/
int main()
{
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    rep(i,N)cin >> A[i];
    rep(t, K)
    {
        vector<int> imos(N + 1);
        rep(i, N)
        {
            imos[max(i - A[i], 0)]++;
            imos[min(i + A[i] + 1, N)]--;
        }
        rep(i, N) imos[i + 1] += imos[i];
        imos.pop_back();
        if (A == imos) break;
        A = imos;
    }
    rep(i, N) cout << A[i] << ' ';
    cout << '\n';
}

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

using namespace std;

long long x, k, d;

void solve(){
    cin>>x>>k>>d;
    x = abs(x);
    long long dd = x/d;
    if(k > dd)  k -= dd, x -= dd*d;
    else
    {
        x -= d*k, k = 0;
    }
    
    if(k%2) cout<<abs(x - d);
    else
    {
        cout<<x;
    }
    

}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int TC;
    //cin>>TC;
    TC=1;
    while(TC--){
        solve();
    }
}

Measured memory_bytes: 3648
s = input()
k = int(input())
substrings = []

for i in range(len(s)):
    for j in range(i, min(len(s), i+5)):
        if s[i:j+1] not in substrings: substrings.append(s[i:j+1])

substrings.sort()
print(substrings[k-1])

Measured memory_bytes: 3944
#include <stdio.h>
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<17, stdin), p1 == p2) ? EOF : *p1++)
char buf[(1 << 17)], *p1 = buf, *p2 = buf;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int ab[100001];
int main(int argc, char *argv[])
{
	int i;
	int n = read(),m = read();
	for (i = 0; i < m; ++i) {
		int a = read(),b = read();
		if (*(ab+b) < a) {*(ab+b) = a;}
	}
	int ans = 0;
	int k = 1;
	for (i = 1; i <= n; ++i) {
		if (k <= *(ab+i)) {
			k = i;
			++ans;
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 640
"""
500 -> 1000
5 -> 5
"""
ans = 0
n = int(input())
if n >= 500:
    goh = n // 500
    zan = n % 500
    ans += goh*1000
    n = zan
if n < 500 and n != 0:
    g = n // 5
    ans += g*5

print(ans)

Measured memory_bytes: 9032
#include <bits/stdc++.h>
#define PI acos(-1.0)
#define mem(a,b) memset((a),b,sizeof(a))
#define TS printf("!!!\n")
#define pb push_back
#define inf 1e9
//std::ios::sync_with_stdio(false);
using namespace std;
//priority_queue<int,vector<int>,greater<int>> que; get min
const double eps = 1.0e-10;
const double EPS = 1.0e-4;
typedef pair<int, int> pairint;
typedef long long ll;
typedef unsigned long long ull;
//const int maxn = 3e5 + 10;
const int  maxn = 100005;
const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}};
const int turn2[8][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}, {1, -1}, { -1, -1}, {1, 1}, { -1, 1}};
//priority_queue<int, vector<int>, less<int>> que;
//next_permutation
int main()
{
        ll a, b;
        cin >> a >> b;
        if (a > b)
        {
                swap(a, b);
        }
        if (a == 1)
        {
                if (b == 1)
                {
                        cout << 1 << endl;
                }
                else if (b == 2)
                {
                        cout << 0 << endl;
                }
                else
                {
                        cout << b - 2 << endl;
                }
        }
        else if (a == 2)
        {
                cout << 0 << endl;
        }
        else
        {
                ll anser = a * b;
                anser -= 2 * b + 2 * (a - 2);
                cout << anser << endl;
        }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define ff           first
#define ss           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;

// Most important thing in CP - Have Fun :)

void solve(){
	//write here
    int n;
    cin>>n;
    int arr[n][3];
    rep(i,0,n){
        cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
    }
    rep(i,1,n){
        arr[i][0] += max(arr[i-1][1],arr[i-1][2]);
        arr[i][1] += max(arr[i-1][0],arr[i-1][2]);
        arr[i][2] += max(arr[i-1][0],arr[i-1][1]);
    }
    int mval = max({arr[n-1][0],arr[n-1][1],arr[n-1][2]});
    cout<<mval<<endl;
}

int main(){
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	//insert code
	
		solve();
	return 0;
}

Measured memory_bytes: 4820
#include<bits/stdc++.h>
#define _LIBCPP_DEBUG 0
using namespace std;
typedef long long int ll;
ll MOD = 1e9 + 7;
int INF = 1 << 30;


int main(void){

    int N,M; cin>>N>>M;

    if(N>=M){
        cout<<0<<endl;
        return 0;
    }

    vector<int> X(M);
    for (int i = 0; i < M; ++i) {
        cin>>X[i];
    }
    sort(X.begin(),X.end());
    vector<int> Sa(M-1);
    for (int i = 0; i < M-1; ++i) {
        Sa[i] = X[i+1]-X[i];
    }
    sort(Sa.begin(),Sa.end(),greater<int>());

    int ans = 0;
    for (int i = N-1; i < M-1; ++i) {
        ans += Sa[i];
    }

    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <bitset>
#include <iomanip>

using namespace std;

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

    bool contanins7 = false;
    for (int i = 0; i < 3; ++i) {
        if (N[i] == '7') {
            contanins7 = true;
            break;
        }
    }
    cout << (contanins7 ? "Yes" : "No") << endl;
    //cout << setprecision(15) << endl;
    return 0;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
#include<cmath>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
typedef long long ll;
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(ll i=num, i##_len=(n); i<i##_len; ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define print(x) cout << (x) << endl;
#define pb push_back
#define mp make_pair
#define sz(x) int(x.size())
 
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int INF = 1e9;
const ll LLINF = 1e16;

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}
 
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};



const int mod = 1e9 + 7;



int main(void){
    cout.tie(0);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(10);
    ll n;
    cin >> n;
    vector<ll> p(n);
    vector<ll> q(n);
    rep(i, n) cin >> p[i];
    rep(i, n) cin >> q[i];
    vector<ll> tmpp(n);
    vector<ll> tmpq(n);
    rep(i, n) tmpp[i] = p[i];
    rep(i, n) tmpq[i] = q[i];
    sort(all(tmpp));
    sort(all(tmpq));
    ll a = 0;
    ll b = 0;
    do {
      bool flag = true;
      a++;
      rep(i,n){
        if(tmpp[i] != p[i]) flag = false;
      }
      if(flag) break;
    } while (next_permutation(tmpp.begin(), tmpp.end()));

    do {
      b++;
      bool flag = true;
      rep(i,n){
        if(tmpq[i] != q[i]) flag = false;
      }
      if(flag) break;
    } while (next_permutation(tmpq.begin(), tmpq.end()));

    print(abs(a - b));
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define int ll
#define double long double
#define YES cout<<"YES"<<'\n'
#define NO cout<<"NO"<<'\n'
#define Yes cout<<"Yes"<<'\n'
#define No cout<<"No"<<'\n'
#define yes cout<<"yes"<<'\n'
#define no cout<<"no"<<'\n'
void YN(bool flg) {cout<<(flg?"YES":"NO")<<'\n';}
void Yn(bool flg) {cout<<(flg?"Yes":"No")<<'\n';}
void yn(bool flg) {cout<<(flg?"yes":"no")<<'\n';}
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
#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 out(n) cout << n << '\n'
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<VI> VVI;
const int MOD = 1000000007;
const long long INF = 10e10;
const double PI = acos(-1.0);
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; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>U COUNT(const T& a, const U& v) { return count(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }
int POW(int a, int n) { int r = 1; while (n > 0) { if (n & 1)r *= a; a *= a; n >>= 1; }return r; }
int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*素因数分解*/map< int, int >prime_factor(int n){map< int, int > ret;for(int i = 2; i * i <= n; i++) {while(n % i == 0) {ret[i]++;n /= i;}}if(n != 1) ret[n] = 1;return ret;}
/*約数列挙*/vector<int> divisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------ライブラリとか----------------

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(15);

    string s,t; cin >> s >> t;
    out(t+s);

    return 0;
}

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

int main(){
  int K,N;
  int max = 0;
  cin >> K >> N;
  vector<int> A(N);
  for(int i = 0;i < N;i++){
    cin >> A.at(i);
  }
  
  for(int i = 0;i < N;i++){
    if(i == N-1){
      if(max < K - A.at(N-1) + A.at(0)){
        max = K - A.at(N-1) + A.at(0);
      }
    }else{
      if(max < A.at(i+1) - A.at(i)){
        max = A.at(i+1) - A.at(i);
      }
    }
  }
  
  cout << K-max << endl;
}

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

#define fi first
#define se second
#define be begin
#define en end
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ALL(a) (a).be() , (a).en()
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)        //repeat n times
#define REP2(i,s,n) for(int (i)=(s);(i)<(n);(i)++)   //repeat from s to n 
#define REPD(i,n) for(int (i)=(n);(i)>=0;(i)--)      //repeat from n to 0
#define REPD2(i,s,e) for(int (i)=(s);(i)>=(e);(i)--) //repeat from s to e
#define RANGE(i,v) for(auto &(i):v)                  //repeat range
#define ASIZE(a) (sizeof(a) / sizeof(a[0]))          //array size

using LL = long long;

int main(){
    string S;
    LL K;
    cin>>S>>K;

    if(S[0] == '1'){
        LL cnt = 0;
        char T;
        REP(i,S.size()){
            if(S[i] == '1'){
                cnt++;
            }else{
                T = S[i];
                break;
            }
        }
        if(K<=cnt){
            cout<<1<<endl;
        }else{
            cout<<(char)T<<endl;
        }
    }else{
        cout<<S[0]<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,s,e) for (int i=s;i<(e);i++)
#define All(v) (v).begin(),(v).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
using namespace std;
typedef long long llint;
typedef pair<int, int> P;
const int MOD = (int)1e9 + 7;
const int INF = 999999999;

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

    int N, H;
    cin >> N >> H;
    vector<int> b(N);
    int a = -1;
    REP(i, N){
        int x;
        cin >> x >> b[i];
        a = max(a, x);
    }
    llint ans = 0;
    sort(All(b));
    reverse(All(b));
    REP(i, N){
        if(b[i] < a) break;
        H -= b[i];
        ans++;
        if(H <= 0) break;
    }
    if(H > 0){
        ans += H/a;
        if(H%a) ans++;
    }
    cout << ans << "\n";
    return 0;
}

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

int main() {
  int H,W;
  cin >> H >> W;
  vector<string> pixels(H);
  for (int i = 0; i < H; i++) {
    cin >> pixels.at(i);
  }
  for (int i = 0; i < W + 2; i++) {
    cout << '#';
  }
  cout << endl;
  for (int i = 0; i < H; i++) {
    cout << '#' << pixels.at(i) << '#' << endl;
  }
  for (int i = 0; i < W + 2; i++) {
    cout << '#';
  }
}


Measured memory_bytes: 3612
#include <iostream>
#include <cstdio>
#include <vector>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
using namespace std;

int main() {
    string s;

    cin >> s;
    string output = (s[2] == s[3] && s[4] == s[5]) ? "Yes" : "No";
    cout << output  << endl;

    return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<bitset>
#include<iostream>
#include<iomanip>
#include<set>
#include<string>
#include<math.h>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long int ll;
typedef pair<int, ll> P;

//--------------
///#define DEBUG
//--------------

#ifdef DEBUG
	#define debugprint(x) cout<<x<<" "
	#define debugendl cout<<endl
	#define debug(x) x
#else
	#define debugprint(x)
	#define debugendl
	#define debug(x)
#endif

class zahyo{
	public:
	int x;
	int y;
	zahyo(){
		x=0;
		y=0;
	}
	zahyo(int x_,int y_){
		x=x_;
		y=y_;
	}
	void print(){
		cout<<x<<" "<<y;
	}
	zahyo operator+(zahyo add){
		add.x=this->x+add.x;
		add.y=this->y+add.y;
		return add;
	}
	zahyo operator-(zahyo add){
		add.x=this->x-add.x;
		add.y=this->y-add.y;
		return add;
	}
	zahyo operator*(int t){
		zahyo temp;
		temp.x=this->x*t;
		temp.y=this->y*t;
		return temp;
	}
	zahyo operator%(int t){
		zahyo temp(this->x%t,this->y%t);
		return temp;
	}
	zahyo operator/(int t){
		zahyo temp(this->x/t,this->y/t);
		return temp;
	}
	bool operator==(const zahyo add) const{
		if(add.x==this->x and add.y==this->y){return true;}
		else{return false;}
	}
	bool operator!=(const zahyo add) const{
		if(add.x==this->x or add.y==this->y){return false;}
		else{return true;}
	}
	bool operator<(const zahyo add) const{
		if(this->x<add.x){return true;}
		else if(this->x==add.x and this->y<add.y){return true;}
		else{return false;}
	}
	bool operator>(const zahyo add) const{
		if(this->x>add.x){return true;}
		else if(this->x==add.x and this->y>add.y){return true;}
		else{return false;}
	}
	void input(){
		cin>>x>>y;
	}
};

bool IsInBoard(int x,int maxx, int y,int maxy){
	if(x>=0 and x<maxx and y>=0 and y<maxy){
		return true;
	}
	else{
		return false;
	}
}

int dpall[1000001];
int dpodd[1000001];

int sqnum(int n){
	return (n*(n+1)*(n+2))/6;
}

int main(){
	int n;
	dpall[0]=0;dpodd[0]=0;
	for(int i=1;i<1000000;i++){
		dpall[i]=i;
		dpodd[i]=i;
	}
	for(int i=1;i<=1000000;i++){
		for(int j=1;j<200;j++){
			if(sqnum(j)>i){break;}
			else{
				dpall[i]=min(dpall[i],dpall[i-sqnum(j)]+1);
				if(sqnum(j)%2==1){
					dpodd[i]=min(dpodd[i],dpodd[i-sqnum(j)]+1);
				}
			}
		}
	}
	while(1){
		cin>>n;
		if(n==0){break;}
		cout<<dpall[n]<<" "<<dpodd[n]<<endl;
	}
	return 0;
}



Measured memory_bytes: 10904
import math
n, d = map(int, input().split())
x = []
y = []
c = 0
for i in range(n):
    xy = []
    xy[len(xy):len(xy)] = input().split()
    x.append(xy[0])
    y.append(xy[1])

for i in range(n):
    if d >= math.sqrt(int(x[i])**2 + int(y[i])**2):
        c += 1

print(c)


Measured memory_bytes: 37392
local r_shift = bit.rshift
local b_and = bit.band

local N = io.read("*n", "*l")
local X = io.read("*l")
local b_0 = string.byte("0")
local X_s = {}
local popcountX = 0
for i = 1, N do
	local byte = X:byte(i)
	if byte == b_0 then
		X_s[i] = 0
	else
		popcountX = popcountX + 1
		X_s[i] = 1
	end
end

local popcountXPlus1, popcountXMinus1 = popcountX + 1, popcountX - 1
--- 2^i%(Xの1の数+1)の配列(i=1,2,3,...,N)
local pow2ModPopcountXPlus1 = {}
pow2ModPopcountXPlus1[1] = 1
for i = 2, N do
	pow2ModPopcountXPlus1[i] = (pow2ModPopcountXPlus1[i-1] * 2) % popcountXPlus1
end
--- 2^i%(Xの1の数-1)の配列(i=1,2,3,...,N)
local pow2ModPopcountXMinus1 = {}
pow2ModPopcountXMinus1[1] = 1
if popcountXMinus1 > 0 then
	for i = 2, N do
		pow2ModPopcountXMinus1[i] = (pow2ModPopcountXMinus1[i-1] * 2) % popcountXMinus1
	end
end

--- X%(Xの1の数+1)
local xModPopcountXPlus1 = 0
for digit = 1, N do
	local pos = N + 1 - digit
	-- あらかじめ計算しておいた桁ごとの余りを利用してX%(Xの1の数+1)を求めていく
	if X_s[pos] == 1 then
		xModPopcountXPlus1 = xModPopcountXPlus1 + pow2ModPopcountXPlus1[digit]
		xModPopcountXPlus1 = xModPopcountXPlus1 % popcountXPlus1
	end
end
--- X%(Xの1の数-1)
local xModPopcountXMinus1 = 0
-- (Xの1の数-1)は0,-1の可能性があるからその排除
if popcountXMinus1 > 0 then
	for digit = 1, N do
		local pos = N + 1 - digit
		if X_s[pos] == 1 then
			xModPopcountXMinus1 = xModPopcountXMinus1 + pow2ModPopcountXMinus1[digit]
			xModPopcountXMinus1 = xModPopcountXMinus1 + popcountXMinus1
		end
	end
end

local function popcount(num)
	local count = 0
	while num > 0 do
		if b_and(num, 1) == 1 then
			count = count + 1
		end
		num = r_shift(num, 1)
	end
	return count
end

--- メモ化の配列
local f = {}
local function getF(num)
	if num == 0 then
		return 0
	end
	if f[num] and f[num] > 0 then
		return f[num]
	end
	local ans = 1 + getF(num % popcount(num))
	f[num] = ans
	return ans
end

for pos = 1, N do
	local digit = N + 1 - pos

	--- (Xの左からi桁目の01を反転した値)%(Xの1の数+-1)
	local modXi = 0
	if X_s[pos] == 0 then
		modXi = xModPopcountXPlus1 + pow2ModPopcountXPlus1[digit]
		modXi = modXi % popcountXPlus1
		local ans = 1 + getF(modXi)
		print(ans)
	elseif popcountXMinus1 > 0 then
		-- +popcountXMinus1はあまりをだすときにmodXiが負にならないようにする
		modXi = xModPopcountXMinus1 + (popcountXMinus1 - pow2ModPopcountXMinus1[digit])
		modXi = modXi % popcountXMinus1
		local ans = 1 + getF(modXi)
		print(ans)
	else
		print(0)
	end
end


Measured memory_bytes: 10320
n = gets.to_i
a = gets.split.map(&:to_i)
puts a.join(" ")
for i in 1 .. n-1 
    v = a[i]
    j = i - 1
    while j >= 0 && a[j]>v
        a[j+1] = a[j]
        j -= 1
    end
    a[j+1] = v
    puts a.join(" ")
end


Measured memory_bytes: 6900
#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 Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B;
string S;
const ll MOD = 998244353;
//const ll MOD = (1e+9) + 7;
const ll INF = 1LL<<60;
typedef pair<ll, ll> P;

ll extgcd(ll a, ll b, ll &x, ll &y){
    ll d = a;
    if(b != 0){
        d = extgcd(b, a%b, y, x);
        y -= (a/b) * x;
    }else{
        x=1;
        y=0;
    }
    return d;
}

int main() {
    cin>>N;
    mat gcd(N+1, vec(N+1));
    reps(i,1,N+1){
        reps(j,1,i+1){
            ll x, y;
            gcd[i][j] = gcd[j][i] = extgcd(i, j, x, y);
        }
    }
    ll sum = 0;
    reps(i,1,N+1){
        reps(j,1,N+1){
            reps(k,1,N+1){
                sum += gcd[gcd[i][j]][gcd[i][k]];
            }
        }
    }
    cout<<sum<<endl;
}

Measured memory_bytes: 3944
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
        ifstream in("input.txt");
        //ofstream out("output.txt");
        #define cin in
        //#define cout out
#endif
int const MAXN=110, MAXK=100100, M=1000000007;
long long int n, k, c[MAXN], dp[MAXK][MAXN], prefix[MAXK][MAXN];
void compute_prefix(int col){
	long long int current=0LL;
	for(int row=0;row<=k;row++){
		prefix[row][col]=(dp[row][col]+current);
		current+=(dp[row][col]);
	}
}
int sum(int start, int end, int where){
	if(start==0) return prefix[end][where]%M;
	return (prefix[end][where]-prefix[start-1][where])%M;
}
void print(){
	cout<<"DP state:\n";
	for(int i=0;i<=k;i++){
		for(int j=0;j<n;j++)
			cout<<dp[i][j]<<" ";
		cout<<"\n";
	}
	cout<<"Prefix Sums:\n";
	for(int i=0;i<=k;i++){
		for(int j=0;j<n;j++)
			cout<<prefix[i][j]<<" ";
		cout<<"\n";
	}
}
int main(){
	cin>>n>>k;
	for(int i=0;i<n;i++)
		cin>>c[i];
	for(int col=n-1;col>=0;col--){
		if(col==n-1){
			for(int row=0;row<=c[col];row++)
				dp[row][col]=1;
		}
		else{
			for(int row=0;row<=k;row++){
				int start=0, end=min(row,(int)c[col]);
				int add=max(0,row-(int)c[col]);
				start+=add, end+=add;
				dp[row][col]=sum(start,end,col+1);
			}
		}
		compute_prefix(col);
	}
	cout<<dp[k][0];
} 

Measured memory_bytes: 172288
package main

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

var N int
var xs, ys []int
var hs []int

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	fmt.Sscanf(scanner.Text(), "%d", &N)

	xs = make([]int, N)
	ys = make([]int, N)
	hs = make([]int, N)
	for i := 0; i < N; i++ {
		scanner.Scan()
		fmt.Sscanf(scanner.Text(), "%d %d %d", &xs[i], &ys[i], &hs[i])
	}

	for cx := 0; cx <= 100; cx++ {
		for cy := 0; cy <= 100; cy++ {
			isConsistent := true
			shouldH := -1
			for i := 0; i < N; i++ {
				if hs[i] > 0 {
					H := hs[i] + abs(xs[i]-cx) + abs(ys[i]-cy)
					if shouldH < 0 {
						shouldH = H
					} else if H != shouldH {
						isConsistent = false
						break
					}
				}
			}

			if isConsistent {
				isAns := true
				for i := 0; i < N; i++ {
					if hs[i] != max(shouldH-abs(xs[i]-cx)-abs(ys[i]-cy), 0) {
						isAns = false
					}
				}
				if isAns {
					fmt.Println(cx, cy, shouldH)
					return
				}
			}
		}
	}
}

func abs(n int) int {
	if n >= 0 {
		return n
	}
	return -n
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}


Measured memory_bytes: 640
#include<cstdio>

int main() {
    int N, X, ans;
    int min_m = 10000;

    scanf("%d %d", &N, &X);

    int m[N];
    for (int i = 0; i < N; i++) {
        scanf("%d", &m[i]);
        X -= m[i];
        if (m[i] < min_m) min_m = m[i];
    }

    ans = N + (X / min_m);

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

    return 0;
}


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

int main() {
    ll n,b,c,t,s=0,i,l; cin>>n; ll a[10001];
    map<ll,ll>m;
    for(i=1;i<=n;i++) {cin>>l; m[l]++; s+=l;}
    cin>>t; 
    while(t--)
    {
        cin>>b>>c; s+=(m[b]*(c-b)); 
        m[c]+=m[b]; m.erase(m.find(b));
        cout<<s<<endl;
    }
    return 0;
}

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    rep(i,m){
        int a, b;
        cin >> a >> b; a--; b--;
        g[a].push_back(b);
    }
    for(int d:g[0]){
        for(int e:g[d]){
            if(e==n-1){
                cout<<"POSSIBLE"<<endl;
                return 0;
            }
        }
    }
    cout << "IMPOSSIBLE" << endl;
    return 0;
}

Measured memory_bytes: 8576
import java.util.*;
import java.lang.Math;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
	char key[] = {'k','e','y','e','n','c','e'};
    int key_count = 0;
    int st_count;
    int el = 0;
    boolean ans = false;
    boolean con = true;
    boolean con2;
    
    for(int i = 0;i < s.length() && con; i++){
    	if(s.charAt(i) == key[key_count] && el == 0) {
          key_count++;
          if(key_count == 7) {
            con = false;
          	ans = true;
          }
        } else if(el == 0) {
          el = 1;
          i = s.length() -(7-key_count)-1;
        }
      	else if(s.charAt(i) == key[key_count]){
          el = 2;
          key_count++;
          if(key_count == 7) {
            con = false;
          	ans = true;
          }
        }
      	else if(el == 2) con = false;    	
    }
     	
    if(ans) System.out.println("YES");
  	else System.out.println("NO");
  }
}


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

int main()
{
    int N;
    cin >> N;
    double a = N;
    if (N == 1)
    {
        cout << 1 << endl;
    }
    else if (N % 2 == 0)
    {
        cout << 0.5 << endl;
    }
    else
    {
        cout << (double)(((a + 1) / 2) / a) << endl;
    }
}

Measured memory_bytes: 256