akhauriyash/Code-Regression huggingface dataset:
// #define STOPIT
#include <bits/stdc++.h>
#define loop(n) for (lint ngtkana_is_a_genius = 0; ngtkana_is_a_genius < lint(n); ngtkana_is_a_genius++)
#define rep(i, begin, end) for (lint i = lint(begin); (i) < lint(end); i++)
#define all(v) v.begin(), v.end()
#define rand(l, r) std::uniform_int_distribution<>(l, r)(mt)
using lint = long long;
auto mt = std::mt19937_64(std::random_device{}());
auto cmn = [](auto& a, auto b){ if (a > b) {a = b; return true;} return false; };
auto cmx = [](auto& a, auto b){ if (a < b) {a = b; return true;} return false; };
void debug_impl() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_impl(Head head, Tail... tail) { std::cerr << " " << head; debug_impl(tail...); }
#ifndef STOPIT
#define debug(...)\
  do {\
    std::cerr << std::boolalpha << "[" << #__VA_ARGS__ << "]:";\
    debug_impl(__VA_ARGS__);\
    std::cerr << std::noboolalpha;\
  } while (false)
#else
#define debug(...) {}
#endif

template < template < typename ... > class Tuple,  typename... Args, std::size_t ... Inds, std::size_t = std::tuple_size< Tuple < Args ... > >::value >
std::istream& tuple_input_impl(std::istream& os, Tuple<Args...>& tuple, std::integer_sequence<std::size_t, Inds...>)
  { (void)std::initializer_list<int>{((void)(os >> std::get< Inds >(tuple)), 0)...}; return os; }
template < template < typename ... > class Tuple,  typename... Args, std::size_t = std::tuple_size< Tuple < Args ... > >::value >
std::istream& operator>> (std::istream& os, Tuple<Args...>& tuple)
  { return tuple_input_impl(os, tuple, std::index_sequence_for<Args...>()); }

template < template < typename ... > class Tuple,  typename... Args, std::size_t ... Inds, std::size_t = std::tuple_size< Tuple < Args ... > >::value >
std::ostream& tuple_output_impl(std::ostream& os, const Tuple<Args...>& tuple, std::integer_sequence<std::size_t, Inds...>)
  { os << "("; (void)std::initializer_list<int>{((void)(os << (Inds > 0 ? "," : "") << std::get< Inds >(tuple)), 0)...}; return os << ")"; }
template < template < typename ... > class Tuple,  typename... Args, std::size_t = std::tuple_size< Tuple < Args ... > >::value >
std::ostream& operator<< (std::ostream& os, const Tuple<Args...>& tuple)
 { return tuple_output_impl(os, tuple, std::index_sequence_for<Args...>()); }

int main() {
  std::cin.tie(0); std::cin.sync_with_stdio(false);
  auto det = [&] (auto&& p, auto&& q) {
    int a,b,c,d;
    std::tie(a,b) = p;
    std::tie(c,d) = q;
    return a*d - b*c;
  };

  auto inp = [&] (auto&& p, auto&& q) {
    int a,b,c,d;
    std::tie(a,b) = p;
    std::tie(c,d) = q;
    return a*c + b*d;
  };

  auto sub = [&] (auto&& p, auto&& q) {
    int a,b,c,d;
    std::tie(a,b) = p;
    std::tie(c,d) = q;
    return std::make_pair(a-c,b-d);
  };

  int q; std::cin >> q;
  loop(q) {
    std::pair<int,int> a,b,c,d;
    std::cin>>a>>b>>c>>d;
    auto p = sub(a,b);
    auto q = sub(c,d);
    if (det(p,q) == 0) {
      std::cout << 2 << std::endl;
    } else if (inp(p,q) == 0) {
      std::cout << 1 << std::endl;
    } else {
      std::cout << 0 << std::endl;
    }
  }
  return 0;
}


Measured memory_bytes: 3232
import java.util.*;
import java.io.*;
public class Main{
	public static void main(String[] args) throws IOException {

		try(BufferedReader kb = new BufferedReader(new InputStreamReader(System.in))){
			for (String in = kb.readLine(); in!=null; in=kb.readLine()) {
				int n= Integer.parseInt(in);
				in = kb.readLine();
				int[] arr = new int[n];
				StringTokenizer st= new StringTokenizer(in);
				for (int i = 0; i < n; i++) {
					arr[i]= Integer.parseInt(st.nextToken().trim());
				}
				System.out.println(solve(arr));
				
			}
		}
	}

	 static int solve(int[] arr) {
		 int grupos = 0;
		 if(arr.length<3)
			 return 1;
		 boolean mx = false, mn = false;

//		 if(arr[0]<arr[1])
//			 mx=true;
			 
		 for (int i = 0; i < arr.length-1; i++) {
			 if(arr[i]<arr[i+1]&&!mn){
				 mx=true;
			 }
			 else if(arr[i]>arr[i+1]&&!mx){
				 mn=true;
			 }
			 else if(arr[i]<arr[i+1]&&mn){
				 grupos++;
				 mx=false;
				 mn=false;
			 }
			 else if(arr[i]>arr[i+1]&&mx){
				 grupos++;
				 mn=false;
				 mx=false;
				 if(i+1==arr.length-1)
					 grupos++;
			 }
		}
		 if(mn||mx)
			 return grupos+1;
		return grupos;
		
	}

}

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

using namespace std;
vector<int> to[200002];
vector<int>ans;
void dfs(int v,int p)
{
    vector<int>::iterator u;
    for( u=to[v].begin();u<to[v].end();u++)
    {
        if(*u==p) continue;
        ans[*u]+=ans[v];
        dfs(*u,v);
    }
}
int main()
{
    int n,q;
    cin>>n>>q;
    for(int i=0;i<n-1;i++)
    {
        int d,f;
        cin>>d>>f;
        --d;
        --f;
        to[d].push_back(f);
        to[f].push_back(d);
    }
    ans.resize(n);
    for(int i=0;i<q;i++)
    {
        int e,r;
        cin>>e>>r;
        ans[e-1]+=r;
    }
    dfs(0,-1);
    for(int i=0;i<n;i++)
    {
        cout<<ans[i]<<' ';
    }
    return 0;
}


Measured memory_bytes: 23424
#include "bits/stdc++.h"

#define REP(i, n, N) for(ll i=(n); i<(N); i++)
#define RREP(i, n, N) for(ll i=(N-1); i>=(n); i--)
#define LREP(lst,itr) for(auto itr = lst.begin(); itr != lst.end(); ++itr)
#define CK(n, a, b) ((a)<=(n)&&(n)<(b))
#define ALL(v) (v).begin(),(v).end()
#define MCP(a, b) memcpy(b,a,sizeof(b))
#define P(s) cout<<(s)<<endl
#define P2(a, b) cout<<(a)<<" "<<(b)<<endl
#define V2(T) vector<vector<T>>
typedef long long ll;
using namespace std;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;

ll mood(ll a){
    return a%MOD;
}

ll modinv(ll a) {
    ll b = MOD, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= MOD;
    if (u < 0) u += MOD;
    return u;
}


ll kaisa(ll a1, ll a2, ll diff, ll n){
    return mood(a1+mood(mood((a2-diff)*(n-1))+mood(diff*mood(mood(n*(n-1))*modinv(2)))));
}

ll check(vector<int>& seq, int n){
    ll res=0;
    ll len=seq.size();
    REP(i,0,len*n){
        REP(j,i,len*n){
            if(seq[i%len]>seq[j%len]){
                res++;
            }
        }
    }
    return res;
}

int main(){

    ll N,K;
    cin >> N >> K;
    vector<int> seq(N);
    REP(i,0,N){
        cin >> seq[i];
    }
    int a,b,c,d,e,f;
    a=check(seq,1);
    b=check(seq,2);
    c=check(seq,3);
    d=b-a;
    e=c-b;
    f=e-d;
    ll ans=kaisa(a,d,f,K);
    P(ans);
}

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

int main() {
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        int max = 0, min = 0;
        int h; cin >> h;
        for (int i = 1; i < n; i++) {
            int last_h = h;
            cin >> h;
            int diff = h - last_h;
            max = (max > diff ? max : diff);
            min = (min > -diff ? min : -diff);
        }
        cout << max << ' ' << min << endl;
    }
    return 0;
}

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

const ll mod=1e9+7;
ll mu(ll a,ll b){
  return (ll)a*b%mod;
}
ll ad(ll a,ll b){
  if((a+=b)>=mod)a-=mod;
  return a;
}
ll pw(ll a,ll b,ll c=1LL){
  for(;b;b>>=1,a=mu(a,a))if(b&1)c=mu(c,a);
  return c;
}
ll dv(ll a,ll b){
  return mu(a,pw(b,mod-2));
}


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

  int n;
  cin >> n;
  int c[n];
  rep(i,n) cin >> c[i];
  int n_max=2e5+1;
  int Ind[n_max];
  int nInd[n];
  rep(i,n_max){
    Ind[i]=-1;
    nInd[i]=-1;
  }
  rep(i,n){
    if(Ind[c[i]]==-1){
      Ind[c[i]]=i;
    }
    else {
      nInd[Ind[c[i]]]=i;
      Ind[c[i]]=i;
    }
  }
  ll dp[n+1];
  rep(i,n+1) dp[i]=0;
  dp[0]=1;
  rep(i,n){
    if(nInd[i]==-1 || nInd[i]==i+1){
      dp[i+1] = ad(dp[i+1],dp[i]);
    }
    else{
      dp[nInd[i]] = ad(dp[nInd[i]],dp[i]);
      dp[i+1] = ad(dp[i+1],dp[i]);
    }
  }
  //  rep1(i,n) cout << dp[i] << " ";
  //  cout << "" << endl;
  cout << dp[n] << endl;
  
  return 0;
    

}


Measured memory_bytes: 4224
#include <cstdio>
#include <algorithm>

using namespace std;

int a[100001][3];

int main()
{
	int n, x, y, z;
	scanf("%d", &n);
	scanf("%d%d%d", &a[0][0], &a[0][1], &a[0][2]);
	for(int i=1;i<n;++i)
	{
		scanf("%d%d%d", &x, &y, &z);
		a[i][0] = max(a[i - 1][1], a[i - 1][2]) + x;
		a[i][1] = max(a[i - 1][0], a[i - 1][2]) + y;
		a[i][2] = max(a[i - 1][1], a[i - 1][0]) + z;
	}
	printf("%d\n", max(max(a[n-1][0], a[n-1][1]), a[n-1][2]));
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define N               200005
#define ff              first
#define ss              second
#define ll              long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<ll,ll>
#define vi              vector<ll>
#define mii             map<ll,ll>
#define pq_max          priority_queue<ll>
#define pq_min          priority_queue<ll,vi,greater<ll> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            ll x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;


void fio(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}

int main(){
    fio();

    string s,t;
    cin>>s>>t;

    int n = s.length(), m = t.length();

    int l = 0;
    for(int x=0;x<=n-m;x++){
        int j = 0, x1 = x;
        for(int y=0;y<m;y++){
            if(s[x1] == t[y]) ++j;
            x1++;
        }
        l = max(l, j);
    }

    cout<<m-l;

    return 0;
}

Measured memory_bytes: 3628
void main() {
	auto ip = readAs!(int[]), X = ip[0], t = ip[1];
	(X - t < 0 ? 0 : X - t).writeln;
}

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

import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	int l[n*2];
	for(int i=0;i<n*2;i++){
		cin>>l[i];
	}
	sort(l,l+n*2);
	int sum=0;
	for(int k=0;k<n;k++){
		sum=sum+l[k*2];
	}
	cout<<sum<<endl;
}


Measured memory_bytes: 256
import sys,queue,math,copy,itertools,bisect,collections,heapq



def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N, Q = LI()

    N0 = 2 ** (N-1).bit_length()

    stx = [N-1] * (N0*2)
    sty = [N-1] * (N0*2)

    def update(l,r,x,st):
        l += N0 - 1
        r += N0 - 1
        while l < r:
            st[l] = min(st[l],x)
            st[r] = min(st[r],x)

            l //= 2
            r = r // 2 - 1

        st[l] = min(st[l],x)

    def get_data(i,st):
        i += N0-1
        ret = N-1
        while i >= 0:
            ret = min(ret,st[i])
            i = (i-1) // 2
        return ret


    ans = (N-2) ** 2
    for _ in range(Q):
        c,p = LI()
        p -= 1
        if c == 1:
            s = get_data(p,sty)
            ans -= s - 1
            update(0,s-1,p,stx)
        else:
            s = get_data(p,stx)
            ans -= s - 1
            update(0,s-1,p,sty)

    print(ans)
if __name__ == '__main__':
    main()

Measured memory_bytes: 84856
#include<bits/stdc++.h>
using namespace std;
//datatypes
	#define int long long
	#define vi vector<int>
	#define si set<int>
	#define vii vector<ii>
	#define ii pair<int,int>
	#define mii map<int,int>
	#define M 1000000007
	#define pi 3.141592653589793
	#define in(x) int x; cin>>x;
	#define sz(x) (int)x.size()
	#define fr first
	#define sc second
	#define pb push_back
	#define mkp make_pair
	#define inputFile \
	    freopen("input.txt", "r", stdin); 
	#define outputFile \
	    freopen("output.txt", "w", stdout)
	#define rep(i,a,b) for(int i=a; i<b; i++)
	#define trav(a) for(auto &x:a)
	#define test cout<<"hello\n";
	#define all(x) (x).begin(),(x).end()
	#define mem0(x) memset(x, 0, sizeof(x))
	#define mem1(x) memset(x, -1, sizeof(x))
	#define sa(x) std::sort(all(x))
	#define sd(x) std::sort(all(x),greater<int>())
vi mx;
vector<vector<int>> adj;

int f(int o)
{
	//cout<<"called for "<<o<<endl;
	if(mx[o]!=-1)
		{
			//cout<<"Areturning "<<mx[o]<<" for "<<o<<endl;
			return mx[o];
		}
	else if(sz(adj[o])==0)
	{
		mx[o]=0;
			//cout<<"Breturning "<<mx[o]<<" for "<<o<<endl;

		return 0;
	}
	else
	{
		for(auto el:adj[o])
		{
			//cout<<"linked element "<<el<<endl;
			int k=f(el);
			if(k+1>mx[o])
				mx[o]=k+1;
		}
			//cout<<"Creturning "<<mx[o]<<" for "<<o<<endl;
		return mx[o];
	}
}

signed solve()
{
	int v;
	cin>>v;
	int e;
	cin>>e;
	mx.resize(v+1, -1);
	adj.resize(v+1);

	rep(i,0,e)
	{
		int x,y;
		cin>>x>>y;
		adj[y].pb(x);
	}
	rep(i,1,v+1)
	{
		f(i);
	}
	int ans=0;

	rep(i,1,v+1)
	if(mx[i]>ans)
		ans=mx[i];
	cout<<ans;
	return 0;
}

signed main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--) solve();
	//cout << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}

Measured memory_bytes: 9472
n, k = map(int, input().split())
d = dict()

for _ in range(n):
	ab = list(map(int, input().split()))
	if ab[0] not in d:
		d[ab[0]] = ab[1]
	else:
		d[ab[0]] += ab[1]

di = sorted(d)
s = 0

for key in di:
	s += d[key]
	if s >= k:
		break

print(key)

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

using namespace std;

typedef long long ll;

const int MOD=998244353;
const int N=3e5+10;

ll fac[N],rev[N],revfac[N];

ll C(ll n,ll m){
        if (m>n||m<0) return 0;
        return fac[n]*revfac[m]%MOD*revfac[n-m]%MOD;
}
void prepare(){
        fac[0]=1;
        for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%MOD;
        rev[1]=1;
        for(int i=2;i<N;i++) rev[i]=MOD-(MOD/i)*rev[MOD%i]%MOD;
        revfac[0]=1;
        for(int i=1;i<N;i++) revfac[i]=revfac[i-1]*rev[i]%MOD;

}
ll n,p1,p2,sum;
int main(){
        prepare();
        ll ans=0;
        cin>>n>>p1>>p2>>sum;
        for(int u1=0;u1<=n;u1++){
                ll rem=sum-u1*p1;
                if (rem<0) break;
                if (rem%p2) continue;
                ll u2=rem/p2;
                ans=(ans+C(n,u1)*C(n,u2))%MOD;
        }
        cout<<ans;
}


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

B=[0]*N
for i in range(N):
    B[i]=A[i]-i
    
B.sort()
X=B[int(N/2)]

ans=0
for i in range(N):
    ans+=abs(X-B[i])
    
print(ans)

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

public class Main {
    private static final int MOD = 1_000_000_007;
    private static final String YES = "Yes";
    private static final String NO = "No";

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

        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] A = new int[N];
        for (int i=0; i<N; i++) {
            A[i] = sc.nextInt();
        }

        System.out.println(solve2(N, K, A));
    }

    private static long solve2(int N, int K, int[] A) {
        long count = 0;
        Arrays.sort(A);
        long[] fact = factInit(N, MOD);


        for (int i=0; i<N-K+1; i++) {
            long comb = combination(N-i-1, K-1, MOD, fact);
            count -= A[i] * comb % MOD;
            count %= MOD;
            // System.err.println("min:" + A[i] + ", comb:" + comb + ", count:" + count);
        }


        for (int i=N-1; i>=K-1; i--) {
            long comb = combination(i, K-1, MOD, fact);
            count += A[i]*comb%MOD;
            count %= MOD;
            // System.err.println("max:" + A[i] + ", comb:" + comb + ", count:" + count);
        }


        return (count + MOD)%MOD;
    }

    public static long combination(int n, int r, long p, long[] fact) {
        if (n == 0 && r == 0) return 1;
        if (n < r || n < 0)   return 0;

        return (fact[n] * power((fact[r]), p-2, p) % p) * power(fact[n-r], p-2, p) % p;
    }

    public static long[] factInit(int n, long p) {
        long[] fact = new long[n+1];
        fact[0] = 1;
        fact[1] = 1;
        for (int i=2; i<=n; i++) {
            fact[i] = i * fact[i-1] % p;
        }

        return fact;
    }

    public static long power(long base, long t, long p) {
        long ans = 1;

        while (t > 0) {
            if (t%2 == 1) {
                ans = ans * base % p;
            }

            t /= 2;
            base = base * base % p;
        }

        return ans;
    }
}

Measured memory_bytes: 49144
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <string.h>
#define ll long long int

int main(void)
{
 int N;
 scanf("%d",&N);
 int div =  N/2;
 int remain =  N%2;
 printf("%d",div+remain);
    return EXIT_SUCCESS;
}


Measured memory_bytes: 128
import java.util.*;

public class Main 
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        logic(sc);
    }
    
    public static void logic(Scanner sc)
    {
        int ans = 0;
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] mArr = new int[m+1];
        for(int i=1;i<=n;i++)
        {
            int ki = sc.nextInt();
            for(int j=1;j<=ki;j++)
            {
                mArr[sc.nextInt()]++;
            }
        }
        for(int i=0;i<mArr.length;i++)
            if(mArr[i]==n)
                ans++;
        
        sc.close();
        System.out.print(ans);
    }
}


Measured memory_bytes: 23124
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
int H,W;
vector<string> s;
int dx[4] = {1,1,-1,-1};
int dy[4] = {1,-1,-1,1};
bool is(int x,int y){
	return 0<=x&&x<H&&0<=y&&y<W;
}
int count3(){
	int ans = 0;
	rep(i,H) rep(j,W) if(s[i][j]=='#') rep(d,4){
		for(int k=1;;k++){
			int x1 = i+dx[d]*k, y1 = j+dy[d]*k;
			int x2 = i+dx[(d+1)%4]*k, y2 = j+dy[(d+1)%4]*k;
			if(!is(x1,y1) || !is(x2,y2)) break;
			if(s[x1][y1]=='#' && s[x2][y2]=='#') ans++;
		}
	}
	return ans;
}
const int N = 700;
bool S[N][N];
int ac[N][N+1];
void rot(){
	bool s[N][N] = {};
	rep(i,N) rep(j,N) s[i][j] = S[j][N-1-i];
	rep(i,N) rep(j,N) S[i][j] = s[i][j];
	rep(i,N){
		ac[i][0] = 0;
		rep(j,N) ac[i][j+1] = ac[i][j] + S[i][j];
	}
}
ll solve(){
	int res = 0;
	rep(i,N){
		rep(r,N) if(S[i][r]){
			rep(l,r) if(S[i][l]){
				int d = r-l;
				int j = i+d;
				if(j>=N) continue;
//				for(int x=l;x<=r;x++) if(S[j][x]) res++;
				res += ac[j][r+1] - ac[j][l];
			}
		}
	}
	return res;
}
int main(){
	cin>>H>>W;
	s.resize(H);
	rep(i,H) cin>>s[i];
	ll ans = -count3();
	rep(i,H) rep(j,W) S[i+j][i-j+W] = s[i][j]=='#';
	rep(t,4){
		rot();
		ans += solve();
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3328
#include<stdio.h>
int main()
{
    int n;
    scanf("%d", &n);
    char s[111];
    scanf("%s", s);
    int i, j, k, x;
    int max = 0;
    for (i = 0; i < n - 1; i++)
    {
        x = 0;
        for (j = 0; j < 26; j++)
        {
            int p;
            p = 0;
            for(k=0;k<=i;k++)
                if (s[k] == 'a' + j)
                {
                    p++;
                    break;
                }
            if (p == 0)
                continue;
            p = 0;
            for(k=i+1;k<n;k++)
                if (s[k] == 'a' + j)
                {
                    p++;
                    break;
                }
            if (p > 0)
                x++;
        }
        if (max < x)
            max = x;
    }
    printf("%d\n", max);
    return 0;
}

Measured memory_bytes: 128
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Kamol Paul
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>
using namespace std;
#define long long long
typedef pair < long , long > pii;

class CCC {
public:
	void solve(std::istream& in, std::ostream& out) {
	    int n;
	    in>>n;
	    vector<int> data(n);
	    for(int& x: data)in>>x;
	    vector <int> des(n);
	    for(int& x: des) in>>x;
	    int ans=0;
	    if(des<data) swap(des,data);
	    while (true){
            if(data==des) break;
            next_permutation(data.begin(),data.end());
	        ans++;
	    }
	    out<<ans<<"\n";

	}
};


int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
	CCC solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	Scanner sc = new Scanner(System.in);
	final int MOD = 1000000007;
	final int MAX = Integer.MAX_VALUE;
	final long LMAX = Long.MAX_VALUE;
	int LEN = (int)1e6 + 1;

	void doIt() {
		System.out.println((sc.nextInt() * 500 >= sc.nextInt())?"Yes":"No");
	}
	
	public static void main(String[] args) {
		new Main().doIt();
	}

}


Measured memory_bytes: 23252
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
const int inf=1e9+7;
const ll INF=1LL<<61;
const ll mod=1e9+7;


int main(){
  int i,j;
  ll n;
  cin>>n;
  ll y=1;
  for(i=0;i<n;i++){
    ll x;
    cin>>x;
    if(y==x) y++;
  }
  if(n-y+1!=n) {
    cout<<n-y+1<<endl;
    return 0;
  }
  cout<<-1<<endl;
  return 0;
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
ll mod = 1000000007;
ll INF = 1000000099;



signed main(){
    ll n,ans=0;
    cin>>n;
    vector<pair<ll,ll>> cnt(n);//隣接頂点数、頂点番号,昇順
    vector<ll> w(n+1,0);//頂点→書き込んだ数
    vector<vector<ll>> v(n+1,vector<ll>(0));//隣接頂点リスト
    vector<ll> c(n);//書き込む数、降順

    for(ll i=0;i < n;i++)
    {
        cnt.at(i)={0,i+1};
    }//初期化

    
    for(ll i=0;i < n-1;i++)
    {
        ll a,b;
        cin>>a>>b;
        v.at(a).pb(b);
        v.at(b).pb(a);
        cnt.at(a-1).fi++;
        cnt.at(b-1).fi++;
    }

    
    for(ll i=0;i < n;i++)
    {
        cin>>c.at(i);
    }
    sort(c.begin(),c.end());
    for(ll i=0;i < n-1;i++)
    {
        ans+=c.at(i);
    }
    reverse(all(c));
    

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

    queue<ll> q;
    q.push(cnt.at(n-1).se);//4入り
    
    ll count=0;
    while(q.size()>0){
        ll x=q.front();
        q.pop();

        w.at(x)=c.at(count);
        //cout << w.at(x) << endl;
        count++;

        for(ll i=0;i < (ll)(v.at(x).size());i++)
        {
            if(w.at(v.at(x).at(i))==0 ){
                //cout << x<<":"<<v.at(x).at(i)<< endl;
                q.push(v.at(x).at(i));
            }
        }
    }
    
    cout << ans <<endl;

    for(ll i=1;i <= n;i++)
    {
        cout<<w.at(i)<<" ";
    }
    cout << endl;
}


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

using namespace std;

typedef long long ll;

ll n, res;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> res;
	while (--n) {
		ll x; cin >> x;
		res = __gcd(res, x);
	}
	cout << res;
	
	return 0;
}


Measured memory_bytes: 256
from collections import Counter


while True:
    m, n = (int(s) for s in input().split())
    if not m:
        break

    objs = [int(input(), 2) for i in range(n)]
    dp = [bytearray(1 << m) for i in range(1 << m)]
    bits = [1 << i for i in range(m)]

    for mask in reversed(range((1 << m) - 1)):
        s = Counter(obj & mask for obj in objs)
        for masked, count in s.items():
            if count > 1:
                dp[mask][masked] = min(max(dp[mask + b][masked],
                                           dp[mask + b][masked + b]) + 1
                                       for b in bits if not b & mask)
    print(dp[0][0])

Measured memory_bytes: 15080
def next_koch(n):
    turn60 = 0.5 + 3 ** 0.5 * 0.5j
    n_next = [n[0]]
    for i in range(1, len(n)):
        s = (n[i - 1] * 2 + n[i]) / 3
        t = (n[i - 1] + n[i] * 2) / 3
        u = (t - s) * turn60 + s
        n_next +=[s, u, t, n[i]]
    return n_next

p1 = 0 + 0j
p2 = 100 + 0j
koch = [p1, p2]

n = int(input())
for i in range(n):
    koch = next_koch(koch)

for z in koch:
    print("{:.8f} {:.8f}".format(z.real, z.imag))


Measured memory_bytes: 5740
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <string>
#include <queue>
#include <numeric>
#include <ctype.h>
#include <limits>
#include <iomanip>

#define rep(i,n) for (int i = 0; i < n; i++)
#define all(x) (x).begin(),(x).end()
using namespace std;

typedef long long ll;

int main()
{
	/*int n, x, t;
	cin >> n >> x >> t;
	cout << (n + x - 1) / x * t;*/


	string s;
	cin >> s;
	int sum = 0;
	rep(i, s.size()) {
		sum += int(s[i] - '0');
	}
	if (sum % 9 == 0)puts("Yes");
	else puts("No");
	return 0;
}

Measured memory_bytes: 3748
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout<<#x<<" : "<<x<<'\n';
#define int long long
#define PI 3.141592653589793238

void solve()
{
	int n; cin>>n;
	int final_ans=1;
	int maxi = 1e18;
	int rem = maxi/final_ans;
	vector<int> a(n);
	bool flag=false;
	for(int i=0;i<n;i++){
		cin>>a[i];
		if(!a[i])
			flag=true;
	}
	if(flag){
		cout<<"0\n";
		return;
	}
	for(int i=0;i<n;i++){
		int x=a[i];
		if(x>rem){
			cout<<"-1\n";
			return;
		}
		else{
			final_ans*=x;
			rem=maxi/final_ans + (maxi%final_ans==0);
		}
	}
	cout<<final_ans<<'\n';
}

main()
{
	int t=1;
	while(t--)
		solve();
}

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

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    rep(ti,t){
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        if(a < b || d < b){
            cout << "No" << endl;
            continue;
        }
        ++c;
        if(c >= b){
            cout << "Yes" << endl;
            continue;
        }
        a %= b;
        d %= b;
        ll g = gcd(d, b);
        a += (b - a - 1) / g * g;
        if(a < b && c <= a) cout << "No" << endl;
        else cout << "Yes" << endl;
    }
    return 0;
}


Measured memory_bytes: 3580
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {

	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int M = sc.nextInt();

System.out.println(48-M);

	}

	//以下、自作ライブラリ

	//指定した値以上の要素が最初に現れる位置
	//要素の数は+1（配列のズレ)
	public static long lowerBound(int n, long[] x, long y) {
		int left = 0;
		int right = n;
		while (left < right) {
			int mid = (left + right) / 2;
			if (x[mid] < y) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		return left;
	}

	//指定した値より大きい要素が最初に現れる位置
	//要素の数は+1（配列のズレ)
	public static long upperBound(int n, long[] x, long y) {
		int left = 0;
		int right = n;
		while (left < right) {
			int mid = (left + right) / 2;
			if (x[mid] <= y) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		return left;
	}

	//最大公約数
	public static long gcd(long a, long b) {
		if (a < b)
			return gcd(b, a);
		long c = 0;
		c = a % b;
		if (c == 0)
			return b;
		return gcd(b, c);
	}

	//最小公倍数
	public static long lcm(long m, long n) {
		return m * n / gcd(m, n);
	}

	//素数判定
	public static boolean isPrime(int n) {
		if (n < 2)
			return false;
		if (n == 2)
			return true;
		if (n % 2 == 0)
			return false;

		for (int i = 3; i * i <= n; i += 2) {
			if (n % i == 0)
				return false;
		}
		return true;
	}
}

//以下、高速スキャナークラス
class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}


Measured memory_bytes: 24660
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
constexpr ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int>P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);

void chmin(int &a, int b) {
	a = min(a, b);
}
void chmax(int &a, int b) {
	a = max(a, b);
}
ll mod_pow(ll a, ll n, ll m = mod) {
	a %= m;
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }
const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}

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


void solve() {
	ll a, b, c, k; cin >> a >> b >> c >> k;
	ll ans = 0;
	ans += min(a, k);
	k -= min(a, k);
	k -= min(b, k);
	ans -= min(c, k);
	cout << ans << "\n";
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//init_f();
	//init();
	solve();
	stop
		return 0;
}


Measured memory_bytes: 7760
import sys

input = sys.stdin.readline

N, Q = map(int, input().split())
s = input()

Query = [input().split() for i in range(Q)]

left, right = 0, N - 1

for t, d in reversed(Query):
    if d == "L":
        if t == s[left]:
            left += 1
        if right < N - 1 and t == s[right + 1]:
            right = min(right + 1, N - 1)
    else:
        if left > 0 and t == s[left - 1]:
            left = max(left - 1, 0)
        if t == s[right]:
            right -= 1
print(max(right - left + 1, 0))


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

using namespace std;

#define int long long

const int mod = 1e9 + 7;

void solve() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector <int> cnt(n);
    int ans = 1;
    if (a[0] != 0) {
        cout << 0;
        return;
    }
    cnt[0] = 1;
    vector <int> used(n);
    for (int i = 1; i < n; ++i) {
        //cout << a[i] << ' ' << cnt[a[i] - 1] << '\n';
        if (a[i] == 0) {
            if (cnt[0] == 3) {
                cout << 0;
                return;
            }
            ++cnt[0];
            continue;
        }
        //cout << a[i] << ' ' << a[i] - 1 << ' ' << cnt[a[i] - 1] << ' ' << used[a[i] - 1] << '\n';
        ans *= max(0ll, cnt[a[i] - 1] - used[a[i] - 1]);
        ++used[a[i] - 1];
        ans %= mod;
        ++cnt[a[i]];
    }
    if (cnt[0] == 3) ans *= 6;
    if (cnt[0] == 1) ans *= 3;
    if (cnt[0] == 2) ans *= 6;
    cout << ans % mod;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}


Measured memory_bytes: 2560
import sys
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import heapq
import bisect
import copy
# import math
def warshall_floyd(d, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i * N +j] = min(d[i * N +j], d[i * N + k] + d[k * N + j])
    return d

def main():
    n = getN()
    lucky = str(input().strip())
    one = [0 for i in range(10)]
    two = [0 for i in range(100)]
    thr = [0 for i in range(1000)]
    # print(lucky)
    for s in lucky:
        # print(s)
        for tin, tis in enumerate(two):
            if tis == 1:
                thr[int(str(tin) + s)] = 1

        for oin, ois in enumerate(one):
            if ois == 1:
                # print(int(str(tin) + s))
                two[int(str(oin) + s)] = 1
        one[int(s)] = 1


    print(sum(thr))
if __name__ == '__main__':
    main()



Measured memory_bytes: 42220
W,H,x,y,r=map(int,input().split())
judge=True
if (x-r<0) or (y-r<0):
    judge=False
if y+r>H:
    judge=False
if x+r>W:
    judge=False
if judge==True:
    print("Yes")
if judge==False:
    print("No")


Measured memory_bytes: 5596
from itertools import accumulate

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0

a_accum = [0] + list(accumulate(a))
b_accum = [0] + list(accumulate(b))

j = m
for i in range(n+1):
  while k < a_accum[i] + b_accum[j] and j >= 1:
    j -= 1
  if k >= a_accum[i] + b_accum[j] and ans < i + j:
    ans = i + j

print(ans)

Measured memory_bytes: 49120
//Ruthless Coding 
#include <bits/stdc++.h>

#define uni(x)      (x).resize(unique(all(x)) - (x).begin())
#define fprint(v)   for(auto x : v) cout << x << ' '
#define ALL(x)      (x).begin(), (x).end()
#define MP(x, y)    make_pair(x, y)
#define PII         pair<int, int>
#define SZ(x)       int((x).size())
#define PB(x)       push_back(x)
#define ll          long long
#define S           second 
#define F           first
#define nl          '\n'

using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
mt19937_64 rnd;

const int N = 2e5 + 5;

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;
    cin >> n;
    map<string, int> seen;
    n -= 1;
    string x;
    cin >> x;
    seen[x] = 1;
    char last = x.back();
    while(n--){
        cin >> x;
        if(!seen.count(x) && last == x[0]){
            seen[x] = 1;
            last = x.back();
        }else{
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
    return 0;
}


Measured memory_bytes: 256
import math
K=int(input())

# def gcb(l):
#     gcb=0
#     for i in range(1,min(l)+1):
#         if sum([l[n]%i for n in range(len(l))])==0:
#             gcb=i
#     return gcb

s=0
#全て同じ
for a in range(K+1):
    s+=a
#二つ同じ：
for a in range(1,K+1):
    for b in range(a+1,K+1):
        s+=math.gcd(a,b)*6
#全て異なる
for a in range(1,K+1):
    for b in range(a+1,K+1):
        for c in range(b+1,K+1):
            s+=math.gcd(c,(math.gcd(a,b)))*6

print(s)

Measured memory_bytes: 9204
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using V = vector<int>;
using Vll = vector<ll>;
using VV = vector<V>;
using VVV = vector<VV>;
#define rep2(i, m, n) for (int i = (m); i < (n); ++i)
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define rep(i, n) rep2(i, 0, n)
#define drep(i, n) drep2(i, n, 0)
#define all(a) (a).begin(), (a).end()
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 &os, const vector<T> &v) { for (auto &e : v) os << e << '\n'; return os; }
inline int popcount(const int x) { return __builtin_popcount(x); }
const int INF  = 1<<30;
const ll INFll = 1ll<<62;


int main() {
  int n; cin >> n;
  VV xy(2, V(n));
  Vll p(n);
  rep(i, n) cin >> xy[0][i] >> xy[1][i] >> p[i];

  int N = 1<<n;
  VVV dst(2, VV(n, V(N, INF)));

  rep(i, 2) rep(S, N) {
    rep(j, n) chmin(dst[i][j][S], abs(xy[i][j]));
    rep(j, n) rep(k, n) if (S>>k&1) chmin(dst[i][j][S], abs(xy[i][j]-xy[i][k]));
  }

  Vll ans(n+1, INFll);

  rep(S, N) drep(T, S+1) {
    T &= S;
    int U = S^T;
    ll res = 0;
    rep(i, n) res += p[i] * min(dst[0][i][T], dst[1][i][U]);
    int k = popcount(S);
    chmin(ans[k], res);
  }

  cout << ans;
  return 0;
}


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

P f(int x) {
  int a = x%10;
  int b = 0;
  while (x) {
    b = x;
    x /= 10;
  }
  return P(a,b);
}

int main() {
  int n;
  cin >> n;
  map<P,int> freq;
  for (int i = 1; i <= n; ++i) {
    P p = f(i);
    freq[p]++;
  }
  ll ans = 0;
  for (int i = 1; i <= n; ++i) {
    P p = f(i);
    P q(p.second, p.first);
    ans += freq[q];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
long long n,k,L,R,M;
long long t[100000];

int check(long long);

int main(){

  int i;

  scanf("%d %d",&n,&k);

  L=1;
  for(i=0;i<n;i++){
    scanf("%d",&t[i]);
    L=(L<t[i]?t[i]:L);
  }
  
  R=1000000000LL;
  while(L<R){
    M=(L+R)/2;
    if(check(M)==-1){
      R=M;
    }else{
      L=M+1;
    }
  }

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

  return 0;

}

int check(long long x){

  long long i,id=0,cnt=0;

  for(i=0;i<n;i++){
    if(cnt+t[i]>x){
      cnt=t[i];
      id++;
    }else{
      cnt+=t[i];
    }
    if(id==k)return 0;
  }
  return -1;
}

Measured memory_bytes: 1376
N = int(input())
D = [input().split() for i in range(N)]

ans = 'No'
for i in range(N-2):
    if D[i][0] == D[i][1] :
        if D[i+1][0] == D[i+1][1] :
            if D[i+2][0] == D[i+2][1] :
                ans = 'Yes'

print(ans)

Measured memory_bytes: 9184
//
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
//
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

// solution 
use std::collections::HashMap;
#[allow(unused_mut)]
#[allow(non_snake_case)]
fn main() {
    input! {
        n: usize,
        a: [i64; n],
    }
    let mut dic = HashMap::new();

    for &ai in a.iter() {
        for aa in ai-1 .. ai+2 {
            let mut entry = dic.entry(aa).or_insert(0);
            *entry += 1;
        }
    }

    let max = dic.values().into_iter().max().unwrap();
    println!("{}", max);
}


Measured memory_bytes: 12540
#include<bits/stdc++.h>
using namespace std;
int n,sum,x;
bitset<4000010> dp;
int main(){
    cin>>n;
    dp[0]=1;
    for(int i=0;i<n;i++){
		cin>>x;
		sum+=x;
		dp|=dp<<x;
	}
    for(int i=(sum+1)/2;i<=sum;i++)
        if(dp[i]){
            cout<<i;
            return 0;
        }
    return 0;
}

Measured memory_bytes: 1664
n = int(input())
num = list(map(int, input().split()))
cnt = 0
flag = 0
while cnt != len(num):
    for i in range(len(num)-1, cnt, -1):
        if num[i] < num[i-1]:
            num[i], num[i-1] = num[i-1], num[i]
            flag+=1
    cnt+=1
print(" ".join(map(str,num)))
print(flag)


Measured memory_bytes: 5600
#include<iostream>
using namespace std;
int main()
{
    int n,k,a=1,b=1;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        a=a*2;
        b=b+k;
        if(a<b)
            b=a;
        else
            a=b;
    }
    if(a<b)
        cout<<a<<endl;
    else
        cout<<b<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define Repr(e, b, i) for(int i = e; i >= b; i--)
#define rep(n, i) Rep(0, n-1, i)
#define repr(n, i) Repr(n-1, 0, i)
#define all(v) (v).begin(), (v).end()
#define pb(v) push_back(v)
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define bitcnt(x) __builtin_popcount(x)
#define fst first
#define snd second
#define Pqaz(T) priority_queue<T,vector<T>,greater<T>>
#define Pqza(T) priority_queue<T>
#define ENJYU std::ios::sync_with_stdio(false);std::cin.tie(0);


struct UnionFind {
    //number of parents(par[i] = i => root)
    vector <int> par;
    //rank of tree
    vector <int> rank;

    UnionFind(int n) : par(n), rank(n, 1) {
        //initialize
        rep(n, i) par[i] = i;
    }

    //find root (keiroasshuku at the same time)
    int root(int x){
        if (par[x] == x) return x;
        else return par[x] = root(par[x]);
    }

    //unite
    void unite(int x, int y){
        x = root(x);
        y = root(y);
        if (x == y) return;
        if (rank[x] > rank[y]) swap(x, y);
        par[x] = y;
        if (rank[x] == rank[y]) rank[y]++;
    }

    //same tree?
    bool same(int x, int y){
        return root(x) == root(y);
    }
};


void solve(void){
	int N, Q;
	cin >> N >> Q;
	UnionFind uf(N);
	while(Q--) {
		int c, x, y;
		cin >> c >> x >> y;
		if (c) cout << uf.same(x, y) << endl;
		else uf.unite(x, y);
	}
}

int main(void){
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}



Measured memory_bytes: 3184