akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
struct BIT{
private:
  vector<ll> vec;
  ll n;
public:
  BIT(ll siz){
    n=siz;
    vec.resize(n+3,0);
  }
  void add(ll ps,ll x){
    ps++;
    while(ps<=n){
      vec[ps]+=x;
      ps+=ps&(-ps);
    }
  }
  ll sum(ll ps){
    ps++;
    ll res=0;
    while(ps>0){
      res+=vec[ps];
      ps-=ps&(-ps);
    }
    return res;
  }
};
ll tento_0(vector<ll> vec){
  ll n=vec.size(),res=0;
  BIT b(n+5);
  for(int i=1;i<=n;i++){
    ll val=vec[i-1];
    res+=b.sum(n+3)-b.sum(val);
    b.add(val,1);
  }
  return res;
}
int main(){
  string s;
  cin>>s;
  int cnt[26]={0};
  for(int i=0;i<s.length();i++) cnt[s[i]-'a']++;
  int kn=0;
  for(int i=0;i<26;i++) if(cnt[i]%2==1) kn++;
  ll kn2=s.length()%2;
  if(kn2-kn<0){
    cout<<-1<<endl;
    return 0;
  }
  int c2[26]={0};
  vector<ll> one,two,thr;
  for(int i=1;i<=s.length();i++){
    int c=s[i-1]-'a';
    if(cnt[c]%2==1){
      if(c2[c]*2+1==cnt[c]) two.push_back(i);
      else if(c2[c]<(cnt[c]/2)) one.push_back(i);
      else thr.push_back(i);
    }
    else{
      if(c2[c]*2<cnt[c]) one.push_back(i);
      else thr.push_back(i);
    }
    c2[c]++;
  }
  vector<ll> all;
  for(int i=0;i<one.size();i++) all.push_back(one[i]);
  for(int i=0;i<two.size();i++) all.push_back(two[i]);
  for(int i=0;i<thr.size();i++) all.push_back(thr[i]);
  ll ans=tento_0(all);


  vector<ll> v2;
  vector<ll> pos[26];
  reverse(thr.begin(),thr.end());
  for(int i=0;i<thr.size();i++){
    int d=s[thr[i]-1]-'a';
    pos[d].push_back(i+1);
  }
  for(int i=0;i<one.size();i++){
    int c=s[one[i]-1]-'a';
    int p=lower_bound(pos[c].begin(),pos[c].end(),0)-pos[c].begin();
    v2.push_back(pos[c][p]);
    pos[c][p]=-1;
  }
  ans+=tento_0(v2);
  cout<<ans<<endl;
}


Measured memory_bytes: 8124
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
#define F first
#define S second
#define random(x) (rand()%x)
const int maxn=100005,INF=0x3f3f3f3f,mod=1000000007;
struct eg{
	int x,y,w;
}nd[maxn];
vector<eg> e;
int fa[maxn];
inline bool cmp1(eg a,eg b){
	return a.x<b.x;
}
inline bool cmp2(eg a,eg b){
	return a.y<b.y;
}
inline bool cmp3(eg a,eg b){
	return a.w<b.w;
}
inline int fnd(int v){
	return v==fa[v]?v:fa[v]=fnd(fa[v]);
}
inline void jn(int a,int b){
	fa[fnd(a)]=fnd(b);
}
int main(){
	int n,cnt=1;
	ll ans=0;
	eg tmp;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&nd[i].x,&nd[i].y);
		nd[i].w=i;
		fa[i]=i;
	}
	sort(nd+1,nd+n+1,cmp1);
	for(int i=2;i<=n;i++){
		tmp.x=nd[i-1].w;
		tmp.y=nd[i].w;
		tmp.w=nd[i].x-nd[i-1].x;
		e.push_back(tmp);
	}
	sort(nd+1,nd+n+1,cmp2);
	for(int i=2;i<=n;i++){
		tmp.x=nd[i-1].w;
		tmp.y=nd[i].w;
		tmp.w=nd[i].y-nd[i-1].y;
		e.push_back(tmp);
	}
	sort(e.begin(),e.end(),cmp3);
	for(int i=0;i<e.size();i++){
		//printf("%d %d %d %d\n",e[i].x,e[i].y,e[i].w,i);
		if(fnd(e[i].x)==fnd(e[i].y)) continue;
		jn(e[i].x,e[i].y);
		cnt++;
		ans+=e[i].w;
		if(cnt==n) break;
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 6516
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
      Scanner input = new Scanner(System.in);
      int a = Integer.valueOf(input.next());
      int b = Integer.valueOf(input.next());

      if (a > b) {
        System.out.println("a > b");
      } else if (a < b) {
        System.out.println("a < b");
      } else if (a == b) {
        System.out.println("a == b");
      }
  }

  private static int secondToHour(int second) {
    return second / 3600;
  }

  private static int secondToMinute(int second) {
    return (second % 3600) / 60;
  }
}


Measured memory_bytes: 26144
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define l long
#define pb push_back
#define mp make_pair
#define mt make_tuple
int main() {
	// your code goes here
	//ifstream cin("input.txt");
	//ofstream cout("output.txt");
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
	ll n; cin>>n;
	ll ans = (n*(n+1))/2;
	ll tt = n/3;
	ans -= 3*( (tt*(tt+1))/2);
	tt = n/5;
	ans -= 5*( (tt*(tt+1))/2);
	tt = n/15;
	ans += 15*( (tt*(tt+1))/2);
	cout<<ans;
	return 0;
}


Measured memory_bytes: 3644
function Main(input) {
    input = input.trim().split("\n").map(function(x) { return x.split(" ")});    
    var N = parseInt(input[0][0], 10);
    var W = parseInt(input[0][1], 10);
    var arr_vw = [];
    var arr_dp = [Array.from({length: W + 1}, () => 0)];
    var tmpW;
    for (var i = 0; i < N; i++){
        arr_vw.push(input[i + 1].map(e => parseInt(e, 10)));
        arr_dp.push([]);
        tmpVw = arr_vw[i];
        for (var j = 0; j <= W; j++){
            if (j < tmpVw[1]) arr_dp[i + 1].push(arr_dp[i][j]);
            if (j >= tmpVw[1]){
                arr_dp[i + 1].push(Math.max(arr_dp[i][j], arr_dp[i][j - tmpVw[1]] + tmpVw[0]));
            }
        }
    }
    console.log(arr_dp[N][W]);
}

Main(require("fs").readFileSync("/dev/stdin", "utf8")); 


Measured memory_bytes: 38860
N, M = map(int, input().split( ))
i = 1
ViewH = {}
H_list = input().split( )
countlist = []
while i <= N:
    ViewH[i] = int(H_list[i-1])
    countlist.append(0)
    i += 1
#print(ViewH)
#print(countlist)

for count in range(M):
    A, B = map(int, input().split())
    #print(str(A)+str(B))
    if ViewH[A] > ViewH[B]:
        countlist[B-1] = 1
    elif ViewH[A] == ViewH[B]:
        countlist[A-1] = 1
        countlist[B-1] = 1
    else:
        countlist[A-1] = 1
#print(countlist)
print(countlist.count(0))


Measured memory_bytes: 30940
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn main() {
    let n = read::<u64>();

    for i in 1..3501 {
        for j in 1..3501 {
            if 4 * i * j <= n * j + n * i {
                continue;
            }
            if (n * i * j) % (4 * i * j - n * j - n * i) == 0 {
                println!(
                    "{0} {1} {2}",
                    i,
                    j,
                    (n * i * j) / (4 * i * j - n * j - n * i)
                );
                return;
            }
        }
    }
}


Measured memory_bytes: 4476
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
#include<utility>
#include<cstring>
#define INF 1000000000
#define MAX_V 101
#define inf 1000000

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

struct edge{
	int to, cap, cost, rev;
	edge(int to, int cap, int cost, int rev) : to(to), cap(cap), cost(cost), rev(rev) {}
};
int N, M, V;
vector<edge> G[MAX_V];
int dist[MAX_V];
int prevv[MAX_V], preve[MAX_V];

void add_edge(int from, int to, int cap, int cost){
	G[from].push_back(edge(to, cap, cost, G[to].size()));
	G[to].push_back(edge(from, 0, -cost, G[from].size()-1));
}

int min_cost_flow(int s, int t){
	int res = 0;
	int f = INF;
	do{
		//Bellman-Ford
		fill(dist, dist+V, INF);
		dist[s] = 0;
		bool update = true;
		while(update){
			update = false;
			for(int v = 0; v < V; v++){
				if(dist[v] == INF) continue;
				for(int i = 0; i < G[v].size(); i++){
					edge &e = G[v][i];
					if(e.cap > 0 && dist[e.to] > dist[v] + e.cost){
						dist[e.to] = dist[v] + e.cost;
						prevv[e.to] = v;
						preve[e.to] = i;
						update = true;
					}
				}
			}
		}
		if(dist[t] == INF){
			return -1;
		}
		int d = f;
		for(int v = t; v != s; v = prevv[v]){
			d = min(d, G[prevv[v]][preve[v]].cap);
		}
		f -= d;
		res += dist[t];
		for(int v = t; v != s; v = prevv[v]){
			edge &e = G[prevv[v]][preve[v]];
			e.cap -= d;
			G[v][e.rev].cap += d;
		}
	}while(dist[t] < 0);
	return res;
}

int main(){
	cin>>N>>M;
	V = N+1;
	for(int i = 0; i < M; i++){
		int x, y, s;
		cin>>x>>y>>s;
		add_edge(x, y, INF, -s);
		add_edge(x, y, 1, -s-inf);
	}
	//longest path from 0 to N-1
	//Bellman-Ford
	fill(dist, dist+V, INF);
	dist[0] = 0;
	bool update = true;
	while(update){
		update = false;
		for(int v = 0; v < V-1; v++){
			if(dist[v] == INF) continue;
			for(int i = 0; i < G[v].size(); i++){
				edge &e = G[v][i];
				if(e.cap > 1 && dist[e.to] > dist[v] + e.cost){
					dist[e.to] = dist[v] + e.cost;
					prevv[e.to] = v;
					preve[e.to] = i;
					update = true;
				}
			}
		}
	}
	int D = -dist[N-1];
	add_edge(N-1, N, INF, D);
	cout<<min_cost_flow(0, N)+M*inf<<endl;
	return 0;
}

Measured memory_bytes: 3196
"use strict";
function main(input) {
    const N = parseInt(input.replace("\n", ""));
    let ans = 0;
    for (let i = 1; i < N + 1; i++) if (((Math.log10(i) | 0) + 1) % 2 == 1) ans++;
    console.log(ans);
    return;
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 32416
//#inclue<AMID>
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define endl '\n'
#define Endl '\n'
#define fi first
#define se second
#define mod 1000000007
using namespace std;
int n, m;
vector<int>v[300010];
bool vis[300010];
int dis[300010];
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x, y;
        scanf("%d%d",&x, &y);
        v[x].pb(y);
        v[y].pb(x);
    }
    queue<int>q;
    q.push(1);
    dis[1]=0; vis[1]=1;
    while(!q.empty()){
        int node=q.front(); q.pop();
        int sz=v[node].size();
        for(int i=0;i<sz;i++){
            int nx=v[node][i];
            if(!vis[nx]){
                vis[nx]=1;
                dis[nx]=dis[node]+1;
                q.push(nx);
            }
        }
    }
    if(dis[n]==2)cout<<"POSSIBLE"<<endl;
    else cout<<"IMPOSSIBLE"<<endl;
}


Measured memory_bytes: 15728
a1 = list(map(int, input().split()))
a2 = list(map(int, input().split()))
a3 = list(map(int, input().split()))

a = a1
a.extend(a2)
a.extend(a3)

cnt = [0,0,0,0]
for ax in a:
  if ax == 1:
    cnt[0] += 1
  elif ax == 2:
    cnt[1] += 1
  elif ax == 3:
    cnt[2] += 1
  elif ax == 4:
    cnt[3] += 1
if set(cnt) == set([1,1,2,2]):
  print("YES")
else:
  print("NO")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main() {
  string c[3];
  for (int i = 0; i < 3; i++) {
    cin >> c[i];
  }
  cout << c[0][0];
  cout << c[1][1];
  cout << c[2][2];
  cout << endl;
  return 0;
}

Measured memory_bytes: 256
// how many numbers from a to b with sum of digits = k?
// code inspired from : https://github.com/flash7even/Programming-Contest/blob/master/Code%20Repository/Dynamic%20Programming/Digit%20DP/Digit-DP.cpp

#include <bits/stdc++.h>
#define ll long long
using namespace std;

string s;
int dp[102][5][2], k;

ll dpsolve(int pos, int cnt, int f) {
    if (cnt > k) return 0;

    if (pos == (int)s.length()) {
        if (cnt == k) return 1;
        return 0;
    }

    if (dp[pos][cnt][f] != -1) return dp[pos][cnt][f];

    ll ans = 0; int lmt;

    if (f == 0) {
        // Digits we placed so far matches with the prefix of b
        // So if we place any digit > num[pos] in the current position, then the number will become greater than b
        lmt = s[pos] - '0';
    }
    else {
        // The number has already become smaller than b. We can place any digit now.
        lmt = 9;
    }

    // Try to place all the valid digits such that the number doesn't exceed b
    for (int dgt = 0; dgt <= lmt; dgt++) {
        int nf = f;
        int ncnt = cnt;
        if (dgt != 0) ncnt++;
        if (f == 0 && dgt < lmt) nf = 1; /// The number is getting smaller at this position
        if (ncnt <= k) ans += dpsolve(pos + 1, ncnt, nf);
    }

    return dp[pos][cnt][f] = ans;
}

int main() {
    cin >> s >> k;
    memset(dp, -1, sizeof(dp));
    ll res = dpsolve(0, 0, 0);
	cout << res << "\n";
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){

  int a,b;

  while(scanf("%d",&a) != EOF){
    scanf("%d",&b);
    while(1){
      if(a<b){
	swap(a,b);
      }
      if(a%b == 0){
	printf("%d\n",b);
	break;
      } else {
	swap(a,b);
	b = b%a;
      }
    }
  }
  return (0);
}

Measured memory_bytes: 2600
#include <stdio.h>
#include <cmath>
#include <bits/stdc++.h>



using namespace std;

typedef vector<int> VI;
typedef vector<string> VS;


//container util
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)



int main(void){

	char N[5]; scanf("%s", &N);

	bool flag = false;

	if(N[0] == N[1] and N[1] == N[2]) flag = true;
	else if(N[1] == N[2] and N[2] == N[3]) flag = true;

	if(flag) printf("Yes\n");
	else printf("No\n");



	return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define between(a,x,b) ((a)<=(x)&&(x)<=(b))
using namespace std;

int main(){
  int n, m, d;
  char name[256];
  while(scanf("%d", &n) && n){
    vector< pair<int, string> >res(n);
    vector< vector<int> >in(n);
    vector<int>num(30);
    rep(i, n){
      scanf("%s%d", name, &m);
      res[i] = make_pair(0, name);
      rep(j, m){
	scanf("%d", &d);
	in[i].push_back(d);
	num[d]++;
      }
    }
    /*    rep(i, n){
      printf("%s", res[i].second.c_str());
      for(int j = 0; in[i][j] != 0; ++j) printf(" %d", in[i][j]);
      puts("");
      } */
    //   rep(i, n) printf("%d %s\n", res[i].first, res[i].second.c_str());
    rep(i, n){
      rep(j, in[i].size()){
	res[i].first += n + 1 - num[in[i][j]];
      }
    }
    //    rep(i, n) printf("%d %s\n", res[i].first, res[i].second.c_str());
    sort(res.begin(), res.end());
    //    rep(i, n) printf("%d %s\n", res[i].first, res[i].second.c_str());
    printf("%d %s\n", res[0].first, res[0].second.c_str());
  }
  return 0;
}

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

int N, K;
vector<int> u, v;
int a[1000010];

int main()
{
    int n;
    cin >> n;
    int i = 1;
    while (a[n] != 1)
    {
        if (n % 2 == 0)
            a[n]++, n = n / 2;
        else
            a[n]++, n = 3 * n + 1;
        i++;
    }
    cout << i << endl;
}

Measured memory_bytes: 256
s = input()

def f(s, c):
    result = 0
    while len(set(s)) != 1:
        t = ''
        for i in range(len(s) - 1):
            if s[i] == c or s[i + 1] == c:
                t += c
            else:
                t += s[i]
        s = t
        result += 1
    return result

result = float('inf')
for c in set(s):
    result = min(result, f(s, c))
print(result)


Measured memory_bytes: 3060
// 基本テンプレート
 
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;
 
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

int dp[25][15][265];
 
signed main() {
    int N, K, S;
    while(cin >> N >> K >> S, N) {
        memset(dp, 0, sizeof(dp));
        dp[0][0][0] = 1;
        for(int i=1; i<=N; i++) {
            for(int k=0; k<=min(i, K); k++) {
                for(int s=0; s<=S; s++) {
                    // use
                    if(s+i <= S && k+1 <= K) dp[i][k+1][s+i] += dp[i-1][k][s];

                    // do not use
                    dp[i][k][s] += dp[i-1][k][s];
                }
            }
        }
        cout << dp[N][K][S] << endl;
    }
    return 0;
}


Measured memory_bytes: 3900
// AOJ 0654 Circle Cross Stamps
// 2019.3.28 bal4u

#include <stdio.h>
#include <stdlib.h>

char S[100005]; int N;

int main()
{
	int f, ans;
	char *s;

	scanf("%d%s", &N, S);
	ans = f = 0;
	s = S; while (*s) {
		if (f) {
			if (*s != *(s - 1)) f = 0, ans++;
		}
		else f = 1;
		s++;
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 2112
n, m = map(int,input().split())
PY = []
for _ in range(m):
    PY.append(list(map(int,input().split())))
sortedPY = sorted(PY, key=lambda x: x[1])

d = {}
o = [1]*(n+1)
for i in sortedPY:
    d[(i[0],i[1])] = o[i[0]]
    o[i[0]] += 1

for i in PY:
    print(str(i[0]).zfill(6) + str(d[(i[0],i[1])]).zfill(6))


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

public class Main {

    public static void main(String[] args)throws Exception {
        InputReader in = new InputReader (System.in);
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        // Code starts from here //
        int t = in.nextInt();
        int ac = 0, wa = 0, tle = 0, re = 0;
        for (int i = 0; i < t; i++) {
            String s = in.next();
            if(s.equals("AC")) ac++;
            else if(s.equals("WA")) wa++;
            else if(s.equals("TLE")) tle++;
            else if(s.equals("RE")) re++;
        }
        pw.printf("AC x %d\n", ac);
        pw.printf("WA x %d\n", wa);
        pw.printf("TLE x %d\n", tle);
        pw.printf("RE x %d\n", re);


        pw.close();
    }





    /****************************************
     ******* IO STUFF STARTS FROM HERE ******
     ****************************************/

    static void debug(Object...obj) {
        System.err.println(Arrays.deepToString
                (obj));
    }

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

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

        //InputReader in = new InputReader(new FileReader("File_Name"));
        public InputReader(FileReader file) {
            reader = new BufferedReader(file);
            tokenizer = null;
        }

        public String next() {

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

        public String nextLine() {
            String line = null;
            try {
                tokenizer = null;
                line =  reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return line;
        }

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

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

        public long nextLong() {
            return Long.parseLong(next());
        }

        public boolean hasNext(){
            try {
                while (tokenizer == null || !
                        tokenizer.hasMoreTokens())
                    tokenizer = new StringTokenizer
                            (reader.readLine());
            }
            catch (Exception e) {
                return false;
            }
            return true;
        }
    }
}

Measured memory_bytes: 48156
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<utility>
#include<tuple>
#include<algorithm>
#include<cmath>
using namespace std;

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

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  rep(i, N) cin >> a[i];
  int ans=0, num=1;
  for(int i=1; i<N; i++) {
    if(a[i] == a[i-1])
      num++;
    else {
      if(num > 1)
        ans += num/2;
      num = 1;
    }
  }
  if(num>1)
    ans += num/2;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
//return x's divisor as vector
vector<int> divisor(int x){
  vector<int> res;
  for(int i=1;i*i<=x;++i){
    if(x%i==0){
      res.push_back(i);
      if(i!=x/i){
	res.push_back(x/i);
      }
    }
  }
  sort(res.begin(), res.end());
  return res;
}

int main()
{
  int n,k;cin >> n >> k;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  int sum = 0;
  rep(i,n) sum += a[i];

  int res = 0;
  vector<int> div = divisor(sum);
  rep(i,div.size()) {
    vector<int> mi(n), pl(n);
    rep(j,n) {
      mi[j] = a[j] % div[i];
      pl[j] = div[i] - mi[j];
    }
    sort(mi.begin(), mi.end());
    sort(pl.begin(), pl.end());
    vector<int> msum(n+1), psum(n+1);
    msum[0] = 0;
    psum[0] = 0;
    rep(j,n) {
      msum[j+1] = msum[j] + mi[j];
      psum[j+1] = psum[j] + pl[j];
    }

    rep(j,n+1) {
      if(msum[j] > k) break;
      if(msum[j] == psum[n-j]) res = max(res, div[i]);
    }
  }
  cout << res << "\n";
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<climits>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

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


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 V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


#define ARRAY_MAX 100005
const int INF = INT32_MAX / 3;
const ll MOD = 1e9 + 7;

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


/******************************************************************************************/


//繋げる方向を一方向にする
typedef struct union_find {

	vector<ll> pa;//親
	vector<ll> ra;//木の深さ
	vector<ll> siz;
	//n要素で初期化
	void init(ll n) {
		pa.resize(n);
		ra.resize(n);
		siz.resize(n);
		for (ll i = 0; i < n; i++) {
			pa[i] = i;/*各ノードに番号を振る,この時par[x]=xとなる時は木の根となる*/
			ra[i] = 0LL;/*各ノード自体の高さは0*/
			siz[i] = 1LL;
		}
	}
	//木の根を求める
	ll find(ll x) {
		if (pa[x] == x) {
			return x;/*根ならそのノードの番号を返す*/
		}
		else {
			return pa[x] = find(pa[x]);/*根でないならさらにノードの根を探す*/
		}
	}

	//xとyの属する集合を併合する
	void unite(ll x, ll y) {
		x = find(x);//xの根の番号を探す
		y = find(y);//yの根の番号を探す
		if (x == y) {//一致すればつながっている
			return;
		}
		pa[y] = x;
		siz[x] += siz[y];
	}

	//xとyが同じ集合に属するか判定
	bool same(ll x, ll y) {
		return find(x) == find(y);//同じ集合なら1、違うなら0が返る
	}
}UF;


int main() {

	ll n,q;
	cin >> n >> q;

	UF tree;
	tree.init(n+10);

	for (int i = 0; i < q; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		if (b > c) {
			swap(b, c);
		}
		if (a == 0) {
			//unite
			tree.unite(b, c);
		}
		else
		{
			cout << tree.same(b, c) << endl;
		}
	}
	
	

	
	return 0;
}


Measured memory_bytes: 3220
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define REP2(i,x,n) for (int i = x; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);



int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  REP(i,n) cin >> a[i];

  REP2(i,1,n){
    a[i] = __gcd(a[i],a[i-1]);
  }

  cout << a[n-1] << endl;
  return 0;
}


Measured memory_bytes: 3760
/* << IN THE NAME OF GOD >> */
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pob pop_back
#define ft first
#define ftt ft.ft
#define ftc ft.sc
#define sc second
#define err(x) cerr << #x  << " = "<<  x << '\n'
#define out(x) cout << x << '\n'
#define forp(i, r, l) for(int i = int(r); i < int(l); i++)
#define forn(i, r, l) for(int i = int(r); i > int(l); i--)
#define FAST ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
#define ctz __builtin_ctz
typedef pair<int, int> pii;
typedef pair<ll ,ll> pll;
const int maxn = 1e3;
 



ll n ,res ,tmp;
bool sel[maxn];
pll a[maxn] ,b[maxn];
int main(){FAST;

    cin >> n;   
    int x ,y;
    forp(i ,0 ,n)
         cin >> a[i].ft >>  a[i].sc;
    forp(i ,0 ,n)
        cin >> x >> y ,b[i].ft = y ,b[i].sc = x;
                
    sort(a ,a + n);
    sort(b ,b + n);

    for(int i = 0; i < n; i++){
        tmp = -1;
        for(int j = 0; j < n; j++)
            if(a[n - i - 1].ft < b[j].sc && a[n - i - 1].sc < b[j].ft && !sel[j] && tmp == -1)
                tmp = j;
        if(tmp != -1)
          res++, sel[tmp] = true;
    }


    out(res);
   return 0;
}
 












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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

template<typename T> vector<T> make_vector(size_t sz){
	return vector<T>(sz);
}

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

template<typename T,typename U,typename... V> 
typename enable_if<is_same<T, U>::value!=0>::type 
fill_value(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_value(U &u, const V... v){
	for(auto &e:u){
		fill_value<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 pid_t pid = getpid();
// Problem Specific Parameter:

const int limit = 100010;
bool aused[limit];
bool bused[limit];

int main(void){
	int n, k;
	cin >> n >> k;

	if (2 * k - 1 > n) {
		cout << -1 << endl;
		return 0;
	}

	const int fa = k;
	const int ta = k + n - 1;

	const int fb = k + n;
	const int tb = k + 2 * n - 1;
	
	const int fc = k + 2 * n;
	const int tc = k + 3 * n - 1;


	vector<int> a, b, c;
	rep(i, n) c.push_back(fc + i);

	int aval = fa;
	while(aval <= ta){
		a.push_back(aval);
		aval += 2;
	}

	aval = fa + 1;
	while(aval <= ta){
		a.push_back(aval);
		aval += 2;
	}

	const int bthr = fb + (n - 1) / 2;
	int bval = bthr;
	while(bval >= fb){
		b.push_back(bval);
		bval--;
	}

	bval = tb;
	while(bval > bthr){
		b.push_back(bval);
		bval--;
	}
	
	bool ok = true;
	rep(i, n){
		if(a[i] + b[i] > c[i]){
			ok = false;
		}
	}

	if(ok){
		rep(i, n) cout << a[i] << " " << b[i] << " " << c[i] << endl;
	} else {
		cout << -1 << endl;
	}

	return 0;
}

Measured memory_bytes: 3576
from itertools import permutations


n = int(input())
x_y = [list(map(int, input().split())) for _ in range(n)]
n_idx = [i for i in range(n)]
n_idx_per = list(permutations(n_idx))
ans = 0
for idx in n_idx_per:
    for i in range(len(idx) -1):
        ans += ((x_y[idx[i]][0] - x_y[idx[i+1]][0]) ** 2 +\
            (x_y[idx[i]][1] - x_y[idx[i+1]][1]) ** 2) ** 0.5
print(ans / len(n_idx_per))


Measured memory_bytes: 8052
a, b, k = map(int, input().split())
res = set()
for i in range(a, a + k):
    res.add(min(b, i))

for i in range(b, b - k, -1):
    res.add(max(a, i))

res = sorted(list(res))
for i in range(len(res)):
    print(res[i])


Measured memory_bytes: 9088
#include<iostream>
#include<iomanip>
#include<fstream>
#include<algorithm>
using namespace std;
int a,b;
string s;
int main()
{
	char ch;
	cin>>a>>ch>>b;
	if(ch=='+')
	cout<<a+b;
	if(ch=='-')
	cout<<a-b;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=s;i<n;i++)
typedef long long ll;
const ll mod = 1e9 + 7;
int main(){
    double n, k, s = 0;
    cin >> n >> k;
    vector<double> e_rui(n+1);
    rep(i,n){
        double p; cin >> p;
        p = (p + 1)/2;
        s += p;
        e_rui[i+1] = s;
    }
    //rep(i,n+1)cout << e_rui[i] << " ";
    cout << endl;
    double r = 0;
    REP(i, k, n+1)r = max(r, e_rui[i] - e_rui[i-k]);
    printf("%.10f\n", r);
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
const int inf = 1000000000; //10^9

int main(){
    int N, A, B;
    cin >> N >> A >> B;
    string s;
    cin >> s;
    int pass = 0;
    int passB = 0;
    for (int i = 0; i < N; i++)
    {
        if(s[i] == 'a' && pass < (A + B)){
            pass++;
            cout << "Yes" << endl;
        }else if(s[i] == 'b' && pass < (A + B)){
            if(passB < B){
                passB++;
                pass++;
                cout << "Yes" << endl;
            }else{
                cout << "No"<<endl;
            }
        }else{
            cout << "No" << endl;
        }
    }
}

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

const int MAX = 100010;
typedef long long ll;
int a[MAX];

int main() {
    int n, tmp, x;
    cin >> n >> x;
    for (int i=0;i<n;i++) {
        cin >> a[i+1];
    }
    a[0] = 0;
    ll tot = 0;
    for (int i=0;i<n;i++) {
        if (a[i] + a[i+1] > x) {
            tot += (a[i+1]+a[i] - x);
            a[i+1] -= (a[i+1]+a[i] - x);
        }
    }
    cout << tot << endl;
}


Measured memory_bytes: 640
#include <stdio.h>

int n;
int s[100];

bool input() {
  int i;
  int a, b, c, d, e;

  scanf("%d", &n);
  if(!n) return false;

  for (i = 0; i < n; i++) {
    scanf("%d %d %d %d %d", &a, &b, &c, &d, &e);
    s[i] = a + b + c + d + e;
  }

  return true;
}


int main() {
  int i, min, max;

  while (input()) {
    min = s[0];
    max = s[0];
    for (i = 1; i < n; i++) {
      if (min > s[i]) min = s[i];
      if (max < s[i]) max = s[i];
    }
    printf("%d %d\n", max, min);
  }

}

Measured memory_bytes: 0
#include<cstdio>
#include<cstring>
char s[20];
int main(){
	int n,i,res=0;
	scanf("%s",s);
	n=strlen(s);
	for(i=0;i<n;++i)if(s[i]=='x')++res;
	puts(res<=7?"YES":"NO");
	return 0;
}

Measured memory_bytes: 128
package main

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

var sc = bufio.NewScanner(os.Stdin)

func readInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

var perms [][]int

func main() {
	sc.Split(bufio.ScanWords)
	n := readInt()

	rest := make([]int, n)
	p := make([]int, n)
	for i := 0; i < n; i++ {
		p[i] = readInt()
		rest[i] = i + 1
	}
	q := make([]int, n)
	for i := 0; i < n; i++ {
		q[i] = readInt()
	}

	perms = make([][]int, 0)
	perm([]int{}, rest)

	pi, pq := 0, 0
	for i := 0; i < len(perms); i++ {
		if equal(perms[i], p) {
			pi = i
		}
		if equal(perms[i], q) {
			pq = i
		}
	}
	fmt.Println(abs(pi - pq))
}

func abs(x int) int {
	if x < 0 {
		return x * -1
	}
	return x
}

func equal(x, y []int) bool {
	if len(x) != len(y) {
		return false
	}
	n := len(x)
	for i := 0; i < n; i++ {
		if x[i] != y[i] {
			return false
		}
	}
	return true
}

func perm(head, rest []int) []int {
	if len(rest) == 0 {
		perms = append(perms, head)
		return head
	}
	res := make([]int, 0)
	for i := 0; i < len(rest); i++ {
		restx := make([]int, len(rest))
		copy(restx, rest)

		headx := make([]int, len(head))
		copy(headx, head)

		headx = append(headx, restx[i])
		restx = append(restx[:i], restx[i+1:]...)
		res = perm(headx, restx)
	}
	return res
}


Measured memory_bytes: 10880
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <utility>
#include <algorithm>
using namespace std;

int main(void){

    unsigned long long int n;
    cin>>n;
     unsigned long long int t=n;
     
    unsigned long long int sum=0;
    
    while(t!=0){
        sum+=t%10;
        t/=10;
    }
    
    if(n%sum==0){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}


Measured memory_bytes: 256
# import numpy as np
# import scipy as sp
# print(a,b,c,sep="") # 半角スペースなしで出力(abc)
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 文字列の二次元配列入力
# s = [list(map(int, input().split())) for i in range(n)] # 数値の二次元配列入力
# import sys ; sys.exit() # プログラム終了
# from copy import deepcopy ; b=deepcopy(a)
# chr(ord('a') + 1)
# s.sort(key=lambda x: x[1], reverse=False) # 2番目の要素で昇順にソート（Trueなら降順）
#

n = int(input())
h = list(map(int, input().split()))
INF = float("inf")
dp = [INF]*n
dp[0] = 0
for i, hh in enumerate(h):
    try:
        dp[i+1] = min(dp[i+1], dp[i]+abs(h[i+1]-h[i]))
        dp[i+2] = min(dp[i+2], dp[i]+abs(h[i+2]-h[i]))
    except:
        pass
print(dp[-1])


Measured memory_bytes: 52984
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

def main():
    r,c,k=map(int,input().split())
    rcv=[list(map(int,input().split())) for i in range(k)]

    dpn=[[0]*4 for i in range(c+1)]

    dic={}
    for i in range(k):
        r1,c1,v=rcv[i]
        dic[(r1,c1)]=v

    for i in range(r):
        for j in range(c):
            dpn[j+1][0]=max(dpn[j+1][0],max(dpn[j+1]))
            if (i+1,j+1) in dic:
                for k in range(3)[::-1]:
                    dpn[j+1][k+1]=max(dpn[j+1][k]+dic[(i+1,j+1)],dpn[j][k]+dic[(i+1,j+1)])
            for k in range(4):
                dpn[j+1][k]=max(dpn[j+1][k],dpn[j][k])
        # print(dpn)
    print(max(dpn[-1]))

main()

Measured memory_bytes: 137720
while 1:
    try:
        count = 0
        answer = ""
        N = list(input())
        for i in N:
            if i == "@":
                answer += int(N[count + 1]) * N[count + 2]
                del N[count], N[count + 1]
            else:
                answer += N[count]
            count += 1
        print(answer)
    except:
        break


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

using namespace std;

int main(void)
{
	string s;
	int ans=0;

	cin>>s;

	for(int i=0;i<s.size();i++){
		if(s[i]=='+') ans++;
		if(s[i]=='-') ans--;
	}

	cout<<ans<<endl;

	return 0;
}


Measured memory_bytes: 256
def getls():
    return [ipt for ipt in input().split()]
def getlsi():
    return [int(ipt) for ipt in input().split()]
[n,m,x] = getlsi()
ls = []
cs = []
for i in range(n):
    tmp = getlsi()
    cs.append(tmp[0])
    ls.append(tmp[1:])
xs = [x] * m
for i in range(n):
    for j in range(m):
        xs[j] -= ls[i][j]
if len([k for k in xs if k > 0]) > 0:
    print(-1)
else:
    cost = 10 ** 5 * 13
    for i in range(1,2 ** n):
        tmp_cost = 0
        tmp_ls = [0] * m
        tmp = "{:0"+str(n)+"b}"
        tmp = tmp.format(i)
        for j in range(n):
            if tmp[j] == "1":
                for k in range(m):
                    tmp_ls[k] += ls[j][k]
                tmp_cost += cs[j]

        if min(tmp_ls) >= x and tmp_cost < cost:
            cost = tmp_cost
    print(cost)


Measured memory_bytes: 68768
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>

int main(){
    int n;
    std::cin >> n;
    std::vector<int> c(n), s(n), f(n);
    for(int i = 0; i < n - 1; i++){
        std::cin >> c[i] >> s[i] >> f[i];
    }

    for(int i = 0; i < n - 1; i++){
        int res = 0;
        for(int j = i; j < n - 1; j++){
            if(res < s[j]){
                res = s[j];
            }else if(res % f[j] == 0){
            }else{
                res += f[j] - res % f[j];
            }
            res += c[j];
        }
        std::cout << res << std::endl;
    }
    std::cout<< 0 << std::endl;
    return 0;
}


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

int main()
{
    int n,k;
    while(cin>>n>>k)
    {
        if(n<k)cout<<1;
        else if(n%k==0)cout<<0;
        else if(n>k)cout<<1;
    }
    return 0;
}


Measured memory_bytes: 256
s = input()

l = len(s)

if l%2:
    #odd
    center = s[l//2]
    res = l//2+1
    for i in range(1,l//2+1):
        if s[l//2-i]==s[l//2+i] and s[l//2-i]==center:
            res+=1
        else:
            break
    print(res)
else:
    center = s[l//2]
    res = l//2
    for i in range(1,l//2+1):
        if s[l//2-i]==center and center == s[l//2+i-1]:
            res+=1
        else:
            break
    print(res)


Measured memory_bytes: 3188
def bin(n, size)
  ar = Array.new(size, 0)
  for i in 0..(size-1)
    ar[i] = n/(2**(size-1-i))
    n -= 2**(size-1-i) * ar[i]
  end
  return ar
end

n = gets.to_i
a = Array.new(n)
x = Array.new(n).map{Array.new(0)}
y = Array.new(n).map{Array.new(0)}
for i in 0..(n-1)
  a[i] = gets.to_i
  x[i], y[i] = a[i].times.map{gets.split.map(&:to_i)}.transpose
end

max = 0
for i in 0..(2**n-1)
  bits = bin(i, n)
  flag = 1
  for j in 0..(n-1)
    if bits[j] == 1
      for k in 0..(a[j]-1)
        if bits[x[j][k]-1] != y[j][k]
          flag = 0
          break
        end
      end
    end
  end
  if flag == 1
    cnt = 0
    bits.each{|bn| cnt += bn}
    max = [cnt,max].max
  end
end
puts max

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

template<class t> void vin(vector<t>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

int main() {
    int n, k;
    cin >> n >> k;
    ll tmp = n/k;
    if (k%2) {
        cout << tmp*tmp*tmp << endl;
    }
    else {
        ll tmp2 = 0;
        for (int i=1; i<=n; ++i) {
            if (i%k == k/2) tmp2++;
        }
        cout << tmp*tmp*tmp+tmp2*tmp2*tmp2 << endl;
    }
    return 0;
}


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

int search_length_h(int w, vector<int> sharps){
    int size = sharps.size();
    int left = 0;
    int right = size-1;

    // int count = 0;
    while(right - left > 1){
        // count++;
        int itr = (right + left)/2;
        if(sharps[itr] < w){
            left = itr;
        }else{
            right = itr;
        }

        // if(count > 100)return -1;
    }

    return sharps[right] - sharps[left] - 1;
}

int search_length_w(int h, vector<int> sharps){
    int size = sharps.size();
    int left = 0;
    int right = size-1;

    // int count = 0;
    while(right - left > 1){
        // count++;
        int itr = (right + left)/2;
        if(sharps[itr] < h){
            left = itr;
        }else{
            right = itr;
        }

        // if(count > 100)return -1;
    }

    return sharps[right] - sharps[left] - 1;
}

int main(){
    int H,W;
    cin >> H >> W;

    string s[H];
    vector<vector<int> > sharp_h(H+2);
    vector<vector<int> > sharp_w(W+2);
    for(int i = 0; i < H; i++) {
        cin >> s[i];
    }

    for(int i = 0; i < H; i++) {
        sharp_h[i+1].push_back(0);
        for(int j = 0; j < W; j++) {
            if(s[i][j] == '#')
                sharp_h[i+1].push_back(j+1);
        }
        sharp_h[i+1].push_back(W+1);
    }

    for(int i = 0; i < W; i++) {
        sharp_w[i+1].push_back(0);
        for(int j = 0; j < H; j++) {
            if(s[j][i] == '#')
                sharp_w[i+1].push_back(j+1);
        }
        sharp_w[i+1].push_back(H+1);
    }

    int ans = 0;
    for(int i = 1; i <= H; i++) {
        for(int j = 1; j <= W; j++) {
            if(s[i-1][j-1] == '#')continue;

            int cnt = 0;
            cnt += search_length_h(j, sharp_h[i]);
            cnt += search_length_w(i, sharp_w[j]);
            cnt--;


            ans = max(ans, cnt);
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 38528
// 基本テンプレート
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;
 
signed main() {
    int N; cin >> N;
    multiset<int> S;
    for(int i=0; i<N; i++) {
        int val; cin >> val;
        S.insert(val);
    }

    int ans = 0;
    while(S.size()) {
        int val = *(--S.end());
        int pw = 1; while(pw < val) pw *= 2;
        pw -= val; if(pw == 0) pw = val;

        S.erase(S.find(val));
        auto itr = S.find(pw);
        if(itr != S.end()) {
            ans++;
            S.erase(itr);
        }
    }
    cout << ans << endl;
    return 0;
}


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

//def
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
#define repeat(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define revrepeat(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define revrep(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define foreach(e, v) for (auto &e : v)
#define all(x) (x).begin(), (x).end()
#define CYES cout << "Yes" << endl
#define CNO cout << "No" << endl
#define SPC(x) cout << fixed << setprecision(x)
#define ZERO(a) memset(a, 0, sizeof(a))
#define MINUS(a) memset(a, 0xff, sizeof(a))

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<vector<ll>> vll;
typedef pair<int, int> P;
constexpr int MOD = 1e9 + 7;
constexpr int INF = __INT_MAX__;               // 2^31 - 1
constexpr long long INFLL = __LONG_LONG_MAX__; // 2^61 - 1
constexpr int MAX_N = 1e5 + 5;
constexpr double PI = acos(-1);

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

    ll n;
    cin >> n;
    out((n * (n - 1)) / 2);

    return 0;
}


Measured memory_bytes: 256
//https://atcoder.jp/contests/dp/tasks/dp_k
#include<bits/stdc++.h>
using namespace std;
int n,k;
int dp[100002];
int arr[101];
int main()
{
    cin>>n>>k;
    int i,j,flag;
    for(i=0;i<n;i++)cin>>arr[i];
    dp[0]=2;
    sort(arr,arr+n);
    for(i=1;i<=k;i++)
    {
        if(i<arr[0])
        {
            dp[i]=2;
            continue;
        }
        else
        {
            flag=0;
            for(j=0;j<n;j++)
            {
                if(i-arr[j]<0)
                    break;
                else
                {
                    if(dp[i-arr[j]]==2)
                    {
                        flag=1;
                        dp[i]=1;
                        break;
                    }
                }
            }
            if(flag==0)
                dp[i]=2;
        }
    }
    //for(int i=0;i<=k;i++)cout<<dp[i]<<' ';
    if(dp[k]==1)
        cout<<"First\n";
    else
        cout<<"Second\n";
}


Measured memory_bytes: 640
import java.util.Scanner;
public class Main {
public static void main(String[]srgs) {
	Scanner scan=new Scanner(System.in);
	int a=scan.nextInt();
	boolean bool=true;
	if(a==1||a==2||a==3||a==5||a==6||a==9||a==10||a==13||a==17) {
		bool=false;
	}
	System.out.println(bool?"Yes":"No");
}
}

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

using namespace std;

using ll = long long;

int main(){
    ll n, y;
    cin >> n >> y;
    for(ll i = 0; i <= n; ++i){
        for(ll j = 0; j <= n; ++j){
            ll k = n - i - j;
            if(k < 0)k = 0;
            if(i * 10000 + j * 5000 + k * 1000 == y && i + j + k == n){
                cout << i << " " << j << " " << k;
                return 0;
            }
        }
    }
    cout << 1 - 2 << " " << -1 << " " << -1;
    return 0;
}


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

int main() {
  int n; cin >>n;
  long long v = 0;
  vector<int> ac(100001, 0);
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    v += a;
    ac[a] += 1;
  }

  int q; cin >>q;
  for (int j = 0; j < q; j++) {
    int b, c;
    cin >>b >>c;
    if (ac[b] > 0) {
      v += (long long)(ac[b] * (c - b));
      ac[c] += ac[b];
      ac[b] = 0;
    }
    cout << v << endl;
  }
  return 0;
}


Measured memory_bytes: 3744
/**
 * Copyright (c) 2017, xehoth
 * All rights reserved.
 * 「ARC 071D」井井井 20-08-2017
 *
 * @author xehoth
 */
#include <bits/stdc++.h>

namespace Task {

#define long long long

const int MAXN = 100000;
const int MOD = 1e9 + 7;
int x[MAXN + 1], y[MAXN + 1];

inline void solve() {
    std::ios::sync_with_stdio(false), std::cin.tie(NULL), std::cout.tie(NULL);
    register int n, m, sumX = 0, sumY = 0;
    std::cin >> n >> m;
    for (register int i = 1; i <= n; i++) std::cin >> x[i];
    for (register int i = 1; i <= m; i++) std::cin >> y[i];
    for (register int i = 1; i < n; i++)
        sumX = (sumX + (long)(x[i + 1] - x[i]) * i % MOD * (n - i)) % MOD;
    for (register int i = 1; i < m; i++)
        sumY = (sumY + (long)(y[i + 1] - y[i]) * i % MOD * (m - i)) % MOD;
    std::cout << (long)sumX * sumY % MOD;
}

#undef long
}

int main() {
    Task::solve();
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <set>
#include <queue>
#include <map>
using namespace std;

#define mod 1000000007
#define ten5 100005
#define ten52 200005
#define ten6 1000005
#define PI 3.1415926

typedef long long int ll;

//ll num[ten52];
ll num[10][10];

int main(void)
{
    long long int sum=0,range=0,ceiling;
    double ans=0.0,half;
    long long int m,n,o,i,j,k=0,money;
    long long int a1=0,a2=0,a3=0,ar,as,at1;
    char c;
    //vector <int> v;
    //float f,g,h;
    //int c,d,big=0;
    string s,s1;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        j=i;
        a1=j%10;    //LSB
        while(j>=10)
        {
            j/=10;
        }
        a2=j%10;    //MSB
        num[a2][a1]++;
    }
    for(i=1;i<10;i++)
    {
        for(j=1;j<10;j++)
        {
            if(i==j)
            {
                sum+=num[i][j]*num[i][j];
            }
            else
            {
                sum+=num[i][j]*num[j][i];
            }
        }
    }
    cout<<sum;
    return 0;
}





Measured memory_bytes: 256