akhauriyash/Code-Regression huggingface dataset:
// atcoder/abc127/F/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; for (auto& i: v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { for (auto& i: v) is >> i; return is; }
template<typename T> ostream& operator << (ostream& os, set<T> s) { os << "#{"; for (auto& i: s) os << i << ","; os << "}"; return os; }
template<typename K, typename V> ostream& operator << (ostream& os, map<K, V> m) { os << "{"; for (auto& i: m) os << i << ","; os << "}"; return os; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

using lli = long long int;
using ull = unsigned long long;
using point = complex<double>;
using str = string;
template<typename T> using vec = vector<T>;

constexpr array<int, 8> di({0, 1, -1, 0, 1, -1, 1, -1});
constexpr array<int, 8> dj({1, 0, 0, -1, 1, -1, -1, 1});
constexpr lli mod = 1e9 + 7;

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.setf(ios_base::fixed);
  cout.precision(15);

  int q;
  while (cin >> q) {
    priority_queue<int, vector<int>, greater<int>> large;
    priority_queue<int, vector<int>, less<int>> small;
    lli l = 0;
    lli s = 0;
    lli sumb = 0;
    while (q--) {
      int op, a, b;
      cin >> op;
      if (op == 1) {
        cin >> a >> b;
        sumb += b;
        if (large.size() < small.size()) {
          large.push(a);
          l += a;
        } else {
          small.push(a);
          s += a;
        }
        if (large.size() && small.size()) {
          while (large.top() < small.top()) {
            int p = large.top(); large.pop();
            int q = small.top(); small.pop();
            l -= p; l += q; large.push(q);
            s -= q; s += p; small.push(p);
          }
        }
      }
      if (op == 2) {
        lli x = small.top();
        lli p = l - x * large.size();
        lli q = x * small.size() - s;
        cout << x << ' ' << p + q + sumb << endl;
      }
    }
  }

  return 0;
}


Measured memory_bytes: 3452
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#include <list>
#include <unordered_map>
#include <unordered_set>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
//#define cerr if(false) cerr
#ifdef DEBUG
#define show(...) cerr << #__VA_ARGS__ << " = ", debug(__VA_ARGS__);
#else
#define show(...) 42
#endif
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <typename T, typename S>
ostream& operator<<(ostream& os, pair<T, S> a) {
    os << '(' << a.first << ',' << a.second << ')';
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (auto x : v) os << x << ' ';
    return os;
}
void debug() {
    cerr << '\n';
}
template <typename H, typename... T>
void debug(H a, T... b) {
    cerr << a;
    if (sizeof...(b)) cerr << ", ";
    debug(b...);
}
set<string> ans;
int n;
void dfs(string &s, int id){
    if(s.size() == n){
        ans.insert(s);
        return;
    }
    for(int i = 0; i <= id+1; i++){
        s += 'a'+i;
        dfs(s, max(id,i));
        s.pop_back();
    }
}
int main(){
    cin >> n;
    string s = "a";
    dfs(s, 0);
    for(auto &x: ans){
        cout << x << "\n";
    }
}


Measured memory_bytes: 8704
using System;
class p
{
  static void Main()
  {
    string[] ipt = Console.ReadLine().Split(' ');
    int A = int.Parse(ipt[0]);
    int B = int.Parse(ipt[1]);
    int C = int.Parse(ipt[2]);
    int D = int.Parse(ipt[3]);
    int countA = (A % D == 0) ? (A / D) : (A / D) + 1;
    int countB = (C % B == 0) ? (C / B) : (C / B) + 1;
    Console.WriteLine(countB <= countA ? "Yes" : "No");
  }
}

Measured memory_bytes: 27524
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<cstdio>
#include<climits>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define ULL unsigned long long
int read(){
	int f=1,x=0;char c=getchar();
	while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
	while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return f*x;
}
const int MAXN=2000000;
const int INF=0x3f3f3f3f;
const int Mod=998244353;
#define mp make_pair
int fac[MAXN+5],inv[MAXN+5];
int Pow(int x,int y){
	int ret=1;
	while(y){
		if(y&1) ret=1ll*ret*x%Mod;
		x=1ll*x*x%Mod,y>>=1;
	}
	return ret;
}
int C(int n,int m){return 1ll*fac[n]*inv[m]%Mod*inv[n-m]%Mod;}
void Prepare(){
	int n=MAXN;
	fac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=1ll*fac[i-1]*i%Mod;
	inv[n]=Pow(fac[n],Mod-2);
	for(int i=n-1;i>=0;i--)
		inv[i]=1ll*inv[i+1]*(i+1)%Mod;
	return ;
}
int main(){
	Prepare();
	int n=read(),m=read();
	if(n<m) swap(n,m);
	int ans=0;
	for(int i=1;i<=m;i++)
		ans=(ans+1ll*C(2*i,i)*C(n+m-2*i,n-i)%Mod)%Mod;
	ans=1ll*ans*Pow(2,Mod-2)%Mod*Pow(C(n+m,n),Mod-2)%Mod;
	printf("%d\n",(ans+n)%Mod);
	return 0;
}

Measured memory_bytes: 19316
n = int(input())
h = list(map(int,input().split()))
count = 0
done = False
while done == False:
    for i in range(n):
        if h[i] >= 0:
            h[i] -= 1
        
        if i > 0 and h[i] < 0 and h[i-1] >= 0:
            count += 1

        if i == n-1 and h[i] >= 0:
            count += 1
    if max(h) <= 0:
        done = True
print(count)


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

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


int main(int, char**) {
        int K;
        std::cin >> K;
        int64_t sum = 0;
        for (int i=1; i<K+1; i++) {
                for (int j=i; j<K+1; j++) {
                        for (int k=j ; k<K+1; k++) {
                                int64_t v = gcd(gcd(i, j), k);
                                int a = 0;
                                if (i==j && j==k) {
                                        a = 1;
                                } else if (i==j || j==k) {
                                        a = 3;
                                } else {
                                        a = 6;
                                }
                                sum += v * a;
                        }
                }
        }
        std::cout << sum << std::endl;
        return 0;
}


Measured memory_bytes: 3636
def main():
    _ = int(input())
    nega = 0
    posi = 0
    A = (int(i) for i in input().split())
    B = (int(i) for i in input().split())
    for a, b in zip(A, B):
        diff = a-b
        if diff < 0:
            nega += abs(diff)//2
        else:
            posi += diff
    if posi <= nega:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()


Measured memory_bytes: 42096
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);

	static boolean solve() {
		int n = in.nextInt();
		int q = in.nextInt();
		if (n + q == 0) return false;

		int[] cnt = new int[101];

		for (int i=0; i<n; i++) {
			int m = in.nextInt();
			for (int j=0; j<m; j++) {
				cnt[in.nextInt()]++;
			}
		}

		int max = q-1;
		int ans = 0;

		for (int i=1; i<101; i++) {
			if (max < cnt[i]) {
				max = cnt[i];
				ans = i;
			}
		}

		out.println(ans);

		return true;
	}

	public static void main(String[] args) {
		long start = System.currentTimeMillis();

		while(solve());
		out.flush();

		long end = System.currentTimeMillis();
		//trace(end-start + "ms");
		in.close();
		out.close();
	}

	static void trace(Object... o) { System.out.println(Arrays.deepToString(o));}
}

Measured memory_bytes: 68480
n, m = map(int, input().split())
slist = []
clist = []

def check(numlist, slist, clist):
    for i in range(m):
        if int(numlist[slist[i]]) != clist[i]:
            return False
    return True

for i in range(m):
    s,c = map(int, input().split())
    slist.append(s-1)
    clist.append(c)

start = 10**(n-1)
end = 10**n
if n == 1:
    start = 0
flag = 0
for num in range(start, end):
    numstring = str(num)
    numlist = list(numstring)
    if check(numlist, slist, clist):
        print(num)
        flag = 1
        break
if not flag:
    print(-1)



Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder
{
    class Programing
    {
        public static void Main()
        {
            var str = Console.ReadLine();
            if (str.Contains('A') && str.Contains('B'))
                Console.WriteLine("Yes");
            else
                Console.WriteLine("No");
        }
    }
}


Measured memory_bytes: 13268
n,a,b = map(int,input().split())
m=0
for i in range(n+1):
    l=0
    h=str(i)
    h = [int(k) for k in h] 
    for j in range(len(h)):
        l +=h[j]
    if l>=a and l<=b:
        m += i
print(m)

Measured memory_bytes: 3060
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/numeric/interval.hpp>
#include <boost/numeric/interval/io.hpp>
using namespace::std;
namespace mp = boost::multiprecision;
typedef mp::number<mp::cpp_dec_float<32,int64_t>> cfloat;
typedef mp::cpp_int cint;
typedef long long lint;
typedef long long ll;
typedef long double ldouble;
typedef vector<lint> vec;
typedef vector<vector<lint>> mat;
typedef vector<vector<vector<lint>>> mat3;
typedef vector<double> dvec;
typedef vector<vector<double>> dmat;
typedef vector<vector<vector<double>>> dmat3;
typedef vector<string> svec;
typedef vector<vector<string>> smat;
typedef vector<vector<vector<string>>> smat3;
typedef vector<pair<lint,lint>> pvec;
typedef vector<vector<pair<lint,lint>>> pmat;
typedef vector<vector<vector<pair<lint,lint>>>> pmat3;
#define rep(i, n) for(lint i = 0; i < (lint)(n); i++)
#define irep(i) for(lint i = 0;; i++)
#define irep1(i) for(lint i = 1;; i++)
#define irep2(i) for(lint i = 2;; i++)
#define rrep(i, n) for(lint i = (lint)(n-1); i >-1; i--)
#define rrepi(i,a,b) for(lint i = (lint)(b-1); i >a-1; i--)
#define repi(i,a,b) for(lint i=lint(a);i<lint(b);i++)
#define rep2(i,a,b,c) for(lint i=lint(a);i>lint(b);i+=c)
#define all(x) (x).begin(),(x).end()
#define sl(c) (('a')<=(c)&&(c)<=('z'))
#define ll(c) (('A')<=(c)&&(c)<=('Z'))
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define PI 3.141592653589793
#define cout (cout<<fixed<<setprecision(15))
#define makeupper(t) (transform(all(t),t.begin(),::toupper))
#define makelower(t) (transform(all(t),t.begin(),::tolower))
#define dist(x1,y1,x2,y2) (pow(pow(x2-x1,2)+pow(y2-y1,2),0.5))
#define NEXT_LINE string junk; getline(cin, junk);
#define output(v) do{rep(i,v.size())cout<<(i?" ":"")<<v[i];cout<<"\n";}while(0)
#define output2(v) rep(i,v.size()){rep(j,v[i].size()){cout<<(j?" ":"")<<v[i][j];}cout<<"\n";}
#define input(a,n) lint n;cin>>n;vector<lint>a(n);rep(i,n)cin>>a[i];
#define INF (1LL<<60)
#define IINF (1<<30)
#define LINF 9223372036854775807
#define MOD 1000000007
vector<lint> dx={-1,1,0,0,1,1,-1,-1};
vector<lint> dy={0,0,-1,1,1,-1,1,-1};
inline lint gcd(lint a,lint b){return b?gcd(b,a%b):a;}
inline lint lcm(lint a,lint b){return a*b/gcd(a,b);}
int main(){
    input(a,n);
    vec b(n);
    repi(i,1,n)a[i]+=a[i-1];
    lint m=LINF;
    rep(i,n-1){
        m=min(m,abs(a[i]*2-a[n-1]));
    }
    cout<<m;
}

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

int main(){
    int n, m, p;
    while(cin >> n >> m >> p, n != 0){
        vector<int> v;
        int sum = 0;
        for(int i=0;i<n;++i){
            int x;
            cin >> x;
            v.push_back(x);
            sum += x;
        }
        cout << (v[m-1] ? sum * (100-p) / v[m-1] : 0) << endl;
    }

    return 0;
}


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

using namespace std;

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

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;

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

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

int bitCount(long bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h, w;  cin >> h >> w;
    string s[h];
    int cnt[h][w];
    rep(i, h) {
      rep(j, w) {
        cnt[i][j] = 0;
      }
    }

    rep(i, h) {
      cin >> s[i];
    }

    rep(i, h) {
      rep(j, w) {
        if (s[i][j] == '#') {
          if (j - 1 >= 0) {
            cnt[i][j - 1]++;
            if (i + 1 < h) {
              cnt[i + 1][j - 1]++;
            }
            if (i - 1 >= 0) {
              cnt[i - 1][j - 1]++;
            }
          }
          if (j + 1 < w) {
            cnt[i][j + 1]++;
            if (i + 1 < h) {
              cnt[i + 1][j + 1]++;
            }
            if (i - 1 >= 0) {
              cnt[i - 1][j + 1]++;
            }
          }
          if (i - 1 >= 0) {
            cnt[i - 1][j]++;
          }
          if (i + 1 < h) {
            cnt[i + 1][j]++;
          }
        }
      }
    }

    rep(i, h) {
      rep(j, w) {
        if (s[i][j] == '.') {
          s[i][j] = cnt[i][j] + '0';
        }
        cout << s[i][j];
      }
      cout << '\n';
    }

    return 0;
}


Measured memory_bytes: 256
def sumdigit(n):
    sum1 = 0
    while n > 0:
        sum1 += (n % 10)
        n //=10
    return sum1

N,A,B = map(int,input().split())
ans = 0
for i in range(1,N+1):
    sd = sumdigit(i)
    if A <= sd and sd <= B:
        ans += i

print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define N 100010
using namespace std;
int A[N];

int main(){
  int n,T;
  cin>>n>>T;
  for(int i=0,s,t;i<n;i++){
    cin>>s>>t;
    A[s]++;
    A[t]--;
  }

  for(int i=1;i<N;i++) A[i] += A[i-1];
  
  int ans = 0;
  for(int i=0;i<N;i++) ans = max(ans,A[i]);
  cout<<ans<<endl;
  
  return 0;
}

Measured memory_bytes: 3436
import sys
sys.setrecursionlimit(10000)

temp = [int(x) for x in input().split()]
N = temp[0]
if N < 1 or N > 100:
    sys.exit()
W = temp[1]
if W < 1 or W > 10000:
    sys.exit()
weight = [0]*N
value = [0]*N
temp1 = [0, 0]
for i in range(N):
    temp1 = [int(x) for x in input().split()]
    value[i] = temp1[0]
    if value[i] < 1 or value[i] > 1000:
        sys.exit()
    weight[i] = temp1[1]
    if weight[i] < 1 or weight[i] > 10000:
        sys.exit()

calls = [[-1 for x in range(W + 1)] for y in range(N + 1)] 

def comb(n, cap):
    if (n == N):
        return 0
    else:
        if calls[n][cap] == -1:
            a = comb(n + 1, cap)
            b = 0
            if (weight[n] <= cap):
                b = value[n] + comb(n + 1, cap - weight[n])
            calls[n][cap] = max(a, b)
        return calls[n][cap]

print(comb(0, W))


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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			double a[] = new double[6];
			for(int i=0;i<6;i++)a[i]=sc.nextDouble();
			double d = a[0]*a[4]-a[1]*a[3];
			double x = (a[4]*a[2]-a[1]*a[5])/d;
			double y = (a[0]*a[5]-a[2]*a[3])/d;
			if(x==0)x=0;
			if(y==0)y=0;
			System.out.printf("%.3f %.3f\n", x, y);
		}
	}
}

Measured memory_bytes: 28380
#include <iostream>
#include <string.h>
#include <string>
using namespace std;

int main()
{
	string a;
	getline(cin, a);
	for(int i = 0; i < ::strlen(a.c_str()); i++){
		if(isupper(a[i])){
			a[i] = ::tolower(a[i]);
		}
		else {
			a[i] = ::toupper(a[i]);
		}
	}
	cout << a << endl;

	return 0;
}

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

a_sub = input().split(" ")
a = [int(n0) for n0 in a_sub]
# print(a)

b_sub = input().split(" ")
b = [int(n0) for n0 in b_sub]
# print(b)

c_sub = input().split(" ")
c = [int(n0) for n0 in c_sub]
# print(c)

score = 0
for xi in range(N-1):
    score = score + b[xi]
    if a[xi+1]==a[xi]+1:
        score = score + c[a[xi]-1]
        # print(xi, c[xi])
score = score + b[N-1]
print(score)


Measured memory_bytes: 3064
#include "bits/stdc++.h"
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(s) s.begin(), s.end()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;
const int DIV = 1e9+7;

ll n;

int main()
{
    cin >> n;
    int res =  n;
    rep(i, n + 1){
        int val = i;
        int cnt = 0;
        while(val > 0){
            cnt += val % 6;
            val /= 6;
        }
        val = n - i;
        while(val > 0){
            cnt += val % 9;
            val /= 9;
        }
        res = min(res, cnt);
    }
    cout << res << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("03")
#include <bits/stdc++.h>
#define int int64_t

using namespace std;

int n, temp;
deque<int> q;

int32_t main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> temp;
		q.push_back(temp);
		
		while (q.size() > 2 and q.back() <= q[q.size() - 2] and \
			q[q.size() - 2] >= q[q.size() - 3])
		{
			temp = q.back() - q[q.size() - 2] + q[q.size() - 3];
			q.pop_back(); q.pop_back(); q.pop_back(); q.push_back(temp);
		}
	}
	
	int res = 0, i = 1;
	
	while (!q.empty())
	{
		if (q.front() >= q.back())
		{
			res += i * q.front();
			q.pop_front();
		}
		else
		{
			res += i * q.back();
			q.pop_back();
		}
		i = -i;
	}
	
	cout << res << "\n";
	
	return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;
public class Main{

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int[] Hs = new int[N+1];
		int INF = Integer.MAX_VALUE;
		Hs[0] = INF;
		int[] dp = new int[N+1];

		for (int i = 1; i <= N; ++i) Hs[i] = sc.nextInt();
		Arrays.fill(dp, INF);

		if(N == 2) {
			System.out.println(Math.abs(Hs[2]-Hs[1]));
		}else {

			for (int i = 2; i < 2 + K; ++i) {
				dp[i] = Math.abs(Hs[1]-Hs[i]);
			}

			for (int i = 2; i <= N; ++i) {
				for (int k = 1; k <= K; ++k) {
					if(i+k<=N)dp[i+k] = Math.min(dp[i+k], dp[i]+Math.abs(Hs[i+k]-Hs[i]));
				}
			}
			System.out.println(dp[N]);
		}
	}

}


Measured memory_bytes: 62144
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
int main(){
    ll n,m,ans=0;cin>>n>>m;
    vector<pair<ll,ll>> task(n+1);
    priority_queue<ll> availabletask;
    For(i,m) availabletask.push(0);
    For(i,n){
        cin>>task.at(i).first>>task.at(i).second;
    }
    task.at(n).first=MOD;
    ll i=0;
    sort(task.begin(),task.end());
    for(ll day=1;day<=m;day++){
        while(task.at(i).first==day){
            availabletask.push(task.at(i).second);
            i++;
        }
        ans+=availabletask.top();
        availabletask.pop();
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3956
#include<stdio.h>

int main()
{
    int n,i,digit=0,mod,num;

    scanf("%d",&n);

    for(i=1;i<=n;i++)
    {
        if(i<=9)
            digit++;

        else if(100<=i && i<=999)
            digit++;

        else if(10000<=i && i<=99999)///100000
            digit++;
    }

    printf("%d",digit);

    return 0;
}


Measured memory_bytes: 3200
#include<iostream>

using namespace std;

void merge(int A[],int left,int mid,int right);
void mergeSort(int A[],int left,int right);

int count;
const int Sentinel = 2000000000;

int main(){
	int n;
	cin>>n;
	int *A;
	A = new int[n];

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

	mergeSort(A,0,n);

	for(int i=0;i<n;i++){
		if(i) cout<<" ";
		cout<<A[i];
	}
	cout<<endl;

	cout<<count<<endl;

	delete [] A;

	cin.get();
	cin.get();
}

void merge(int A[],int left,int mid,int right){
	int n1 = mid-left; int n2 = right-mid;
	int *L,*R;
	L = new int[n1+1]; R = new int[n2+1];
	for(int i=0;i<n1;i++) L[i] = A[left+i];
	for(int i=0;i<n2;i++) R[i] = A[mid+i];
	L[n1] = R[n2] = Sentinel;
	int i = 0 , j = 0;
	for(int k=left;k<right;k++){
		count++;
		if(L[i]<=R[j]){
			A[k] = L[i++];
		}else{
			A[k] = R[j++];
		}
	}
	delete [] L; delete [] R;
}

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

Measured memory_bytes: 6816
package main

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

func main() {
	var n int
	fmt.Scan(&n)

	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	a := make([]int, n, n)

	for i := 0; i < n; i++ {
		scanner.Scan()		
		tmp, _ := strconv.Atoi(scanner.Text())
		a[i] = tmp
	}

	west := make([]int, n, n)
	east := make([]int, n, n)

	west[0] = a[0]
	east[0] = a[n - 1]
	for i := 1; i < n; i++ {
		west[i] = gcd(a[i], west[i - 1])
		east[i] = gcd(a[n - 1 - i], east[i - 1])
	}

	answer := 1
	for i := 0; i < n; i++ {
		var m int
		if i == 0 {
			m = east[n - 2]
		} else if i == n - 1 {
			m = west[n - 2]
		} else {
			m = gcd(west[i - 1], east[n - i - 2])
		}
		if m > answer {
			answer = m
		}
	}

	fmt.Println(answer)
}

func gcd(n1 int, n2 int) int {
	if n1 % n2 == 0 {
		return n2
	}
	return gcd(n2, n1 % n2)
}


Measured memory_bytes: 4736
import java.util.Scanner;

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

		int a = stdIn.nextInt();
		int b = stdIn.nextInt();
		int x = stdIn.nextInt();
		if((a+b < x) || (x < a))
			System.out.println("NO");
		else
			System.out.println("YES");
	}
}

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

#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())

#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG true
#define LL long long
#define MOD 1000000007

//cout << (c)?"Yay!":":(" << endl;

// sort(a.begin(), a.end(), std::greater<int>());
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, long long int> counter;
    map<int, long long int> ans;
    rep(i, n)
    {
        cin >> a[i];
        counter[a[i]]++;
    }
    long long int sum = 0;
    for (auto itr = counter.begin(); itr != counter.end(); itr++)
    {
        ans[itr->first] = itr->second * (itr->second - 1) / 2;
        sum += ans[itr->first];
    }
    rep(i, n)
    {
        long long int temp = 0;
        temp = sum - ans[a[i]] + (counter[a[i]] - 1) * (counter[a[i]] - 2) / 2;
        cout << temp << endl;
    }
    return 0;
}


Measured memory_bytes: 18176
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mod 1000000007
#define loop(n) for(int i=0;i<n;i++)
using namespace std;
void leftrotate(int arr[], int n, int d) 
{ 
    int g_c_d = gcd(d, n); 
    for (int i = 0; i < g_c_d; i++) { 
        /* move i-th values of blocks */
        int temp = arr[i]; 
        int j = i; 
  
        while (1) { 
            int k = j + d; 
            if (k >= n) 
                k = k - n; 
  
            if (k == i) 
                break; 
  
            arr[j] = arr[k]; 
            j = k; 
        } 
        arr[j] = temp; 
    } 
} 
void reverseArray(int arr[], int start, 
                            int end) 
{ 
    while (start < end) 
    { 
        std::swap(arr[start], arr[end]); 
        start++; 
        end--; 
    } 
} 
  
/* Function to right rotate arr[] 
of size n by d */
void rightrotate(int arr[], int n, int d)
{ 
    reverseArray(arr, 0, n-1); 
    reverseArray(arr, 0, d-1); 
    reverseArray(arr, d, n-1); 
} 
  
int main()
{
  string a;
  cin>>a;string s="ABC";
  if(s.compare(a)==0)
  cout<<"ARC\n";
  else
  cout<<"ABC\n";

}

Measured memory_bytes: 3576
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
class Program
{
    static void Main(string[] args)
    {
            // 考察
            // 2点間の距離(a, b),(c, d)は
            //   √((c - a) ^ 2 + (d - b) ^ 2)で取得可能
            // 角度θと半径rから位置(x, y)取得可能
            //   (x, y) = (rcosθ, rsunθ)
            // 例:10:40の時針の角度10 / 12 * 360 + 40 / 60 * 360 / 12 = 320°
            //    10:40の分針の角度40 / 60 * 360 = 240°
            // から
            //    (H / 12 * 360 + M / 60 * 360 / 12) * (Math.PI / 180)  で時針の角度(ラジアン)
            //    (M / 60 * 360) * (Math.PI / 180)                      で分針の角度(ラジアン)
            // が判明。尚、度からラジアンに変更しないとMath.Cos Math.Sinは使用できない

            // 入力
            string[] sS = System.Console.ReadLine().Trim().Split(' ');
            double iA = double.Parse(sS[0]);                                                        // 時針の長さ
            double iB = double.Parse(sS[1]);                                                        // 分針の長さ
            double iH = double.Parse(sS[2]);                                                        // 時
            double iM = double.Parse(sS[3]);                                                        // 分

            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();

            // 解析
            double iHx = 0d, iHy = 0d;
            double iMx = 0d, iMy = 0d;
            iHx = iA * Math.Cos((iH / 12d * 360d + iM / 60d * 360d / 12d) * (Math.PI / 180d));      // 時針の角度ラジアンからX位置
            iHy = iA * Math.Sin((iH / 12d * 360d + iM / 60d * 360d / 12d) * (Math.PI / 180d));      // 時針の角度ラジアンからY位置
            iMx = iB * Math.Cos((iM / 60d * 360d) * (Math.PI / 180d));                              // 分針の角度ラジアンからX位置
            iMy = iB * Math.Sin((iM / 60d * 360d) * (Math.PI / 180d));                              // 分針の角度ラジアンからY位置
            double iDef = 0d;
            iDef = Math.Sqrt(Math.Pow(iMx - iHx, 2) + Math.Pow(iMy - iHy, 2));                      // 2点間の距離

            // 出力
            System.Console.WriteLine("{0}", iDef.ToString().Trim());

            sw.Stop();
#if DEBUG
            Console.WriteLine();
            Console.WriteLine("{0}", sw.Elapsed.ToString());
            Console.WriteLine("続行するには何かキーを押してください．．．");
            Console.ReadKey();
#endif
    }

}


Measured memory_bytes: 27852
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define gc(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
#define ms(a,b) memset(a,b,sizeof(a));
char _;
typedef long double dl;
using namespace std;

dl arr[3000];
dl dp[3000][3000];
dl headsprob(int tosses, int heads){
    if(tosses<0||heads<0){
        return 0;
    }
    else if(dp[tosses][heads]!=-1){
        return dp[tosses][heads];
    }
    else{
        if(heads>tosses){
            dp[tosses][heads]=0;
        }
        else{
            dp[tosses][heads]=headsprob(tosses-1,heads-1)*(arr[tosses]);
            dp[tosses][heads]+=headsprob(tosses-1,heads)*((dl)1-arr[tosses]);
        }
        return dp[tosses][heads];
    }
}

int main()
{
    ms(dp,-1);
    dp[0][0]=1;
    int n; cin>>n;
    for(int i = 0; i < n; ++i){
        dl a; cin>>a;
        arr[i+1]=a;
    }
    dl const1=0;
    for(int i = n/2+1; i<=n; ++i){
        const1+=headsprob(n,i);
    }

    cout<<setprecision(16)<<const1<<"\n";
    return 0;
}


Measured memory_bytes: 141056
import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner(System.in);
        int n = sc.nextInt();
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0; i < n; i++){
            set.add(sc.nextInt());
        }
        System.out.println(set.size());
    }
}

class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;
    public FastScanner(InputStream in) {
        reader = new BufferedReader(new InputStreamReader(in));
        tokenizer = null;
    }

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

    public String nextLine() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken("\n");
    }

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

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

    public double nextDouble() {
         return Double.parseDouble(next());
    }
    
    public String[] nextArray(int n) {
        String[] a = new String[n];
        for (int i = 0; i < n; i++)
            a[i] = next();
        return a;
    }

    public int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = nextInt();
        return a;
    }

    public long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = nextLong();
        return a;
    } 
}


Measured memory_bytes: 25428
# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy
 
# 入力
#A, B, C, D = map(int, input().split())
#L = list(map(int, input().split()))
#S = list(str(input()))
#N = int(input())
S = str(input())

T = "ACGT"

S2 = ""
for i in range(len(S)) :
  if S[i] in T :
    S2 += "#"
  else :
    S2 += " "
S3 = list(map(str, S2.split()))
#print (S2)
l = 0
for i in range(len(S3)) :
  l = max(l, len(S3[i]))
  
print (l)



Measured memory_bytes: 38384
n, m = map(int, input().split())

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

for _ in range(m):
    a, b = map(int, input().split())
    d[a] += 1
    d[b] += 1

for i in range(1, n + 1):
    print(d[i])

Measured memory_bytes: 38256
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;

int main(){
	double d;
	cin>>d;
	if(d>=1.0)d=max(1.0+(int)d,sqrt(2)*d);
	else d=sqrt(2)*d;
	printf("%.11f\n",d);
}

Measured memory_bytes: 3284
#include<bits/stdc++.h>
#define ll long long 
#define inf 0x7fffffff
#define clr(c) memset(c,0,sizeof(c))
using namespace std;
int mod=998244353;
const int M=1e6+10;
const int N=5e5+10;
inline ll read(){
    ll b=1,sum=0; char c=getchar();
    while(!isdigit(c)){if(c=='-') b=-1; c=getchar();}
    while(isdigit(c)){sum=sum*10+c-'0'; c=getchar();}
    return b*sum;
}
int n,m,k,T;
int len,ans;
int a[N];
bool cmp(int x,int y){return x>y;}
int main() 
{
    int i,j;
    n=read(),m=read();
    ll sum=0;
    for(i=1;i<=n;i++) {
        a[i]=read();
        sum+=a[i];
    }
    sort(a+1,a+n+1,cmp);
    int he=0;
    if(sum%(4*m)==0) sum=sum/(4*m);
    else sum=sum/(4*m)+1;
    for(i=1;i<=n;i++) {
        if(a[i]>=sum) he++;
        else break;
    }
    if(he>=m) printf("Yes");
    else printf("No");
    return 0;
}


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

using namespace std;

struct node {
    int idx, zero, one;
    double val() const {
        if(!one)
            return 1e9;
        return (double)zero / one;
    }
    bool operator < (const node &that) const {
        if(val()==that.val())
            return idx<that.idx;
        return val() > that.val();
    }
};

int32_t main() {
    // atentie la ifstream , n = 1 , long long la inversiuni
    //ifstream cin("data.in");
    int n;
    cin >> n;
    vector<int>p(n, -1);
    for(int i = 1; i < n; i++) {
        cin >> p[i];
        p[i]--;
    }
    vector<int>v(n);
    for(int i = 0; i < n; ++i)
        cin >> v[i];

    multiset<node>pq;

    vector<int>c0(n), c1(n);
    if(v[0] == 1)
        c1[0] = 1;
    else
        c0[0] = 1;


    vector<int>dsu(n);
    for(int i = 0; i < n; ++i)
        dsu[i] = i;

    function<int(int)>get = [&] (int u) {
        if(u == dsu[u])
            return u;
        return dsu[u] = get(dsu[u]);
    };
    long long inv = 0;
    auto join = [&] (int u, int v) {
        u = get(u), v = get(v);
        inv += 1LL * c1[u] * c0[v];
        dsu[v] = u;
        c1[u] += c1[v];
        c0[u] += c0[v];
    };

    for(int i = 1; i < n; i++) {
        if(v[i] == 0)
            pq.insert(node{i, 1, 0}), c0[i] = 1;
        else
            pq.insert(node({i, 0, 1})), c1[i] = 1;
    }
    while(!pq.empty()) {
        node u = *pq.begin();
        int par = p[get(u.idx)];
        par = get(par);
        pq.erase(pq.begin());
        if(par > 0) {
            auto it = pq.find(node{par, c0[par], c1[par]});
            pq.erase(it);
            join(par, u.idx);

            pq.insert(node{par, c0[par], c1[par]});
        } else
            join(par, u.idx);

    }
    cout << inv;
}


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

int main() {
  int n;
  cin >> n;
  vector<int> t(n+1);
  vector<int> x(n+1);
  vector<int> y(n+1);
  t.at(0) =0;
  x.at(0)=0;
  y.at(0)=0;
  for(int i=0; i<n;i++){
    cin >> t.at(i+1) >> x.at(i+1) >> y.at(i+1);
  }
  
  bool good =true;
  
  for(int i=0;i<n;i++){
    int t_abs=abs(t.at(i)-t.at(i+1) );
    int x_abs=abs(x.at(i)-x.at(i+1) );
    int y_abs= abs(y.at(i)-y.at(i+1) );
    if( (t_abs <(x_abs+y_abs)) ||( (t_abs%2) != (x_abs+y_abs)%2)){
      good =false;
      break;
    }
  }
  if(good) cout << "Yes" <<endl;
  else cout << "No" <<endl;
}


Measured memory_bytes: 1408
//#pragma once
#include <stdio.h>
#include <string>
#include <iostream>
#include <queue>
#include <algorithm>
#include <sstream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <numeric>
#include<bitset>
#include <iomanip>

using namespace std;
#define modd 1000000007


typedef pair<long long, long long> pl;



#define ll long long




/*
class UnionFind {
public:
	vector <ll> par;
	vector <ll> siz;
	vector <ll> gr;

	// Constructor
	UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) ,gr(sz_){
		for (ll i = 0; i < sz_; ++i) par[i] = i;
	}
	void init(ll sz_) {
		par.resize(sz_);
		siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
		for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
	}

	// Member Function
	// Find
	ll root(ll x) { // 根の検索
		while (par[x] != x) {
			x = par[x] = par[par[x]]; // x の親の親を x の親とする
		}
		return x;
	}

	// Union(Unite, Merge)
	bool merge(ll x, ll y) {
		x = root(x);
		y = root(y);
		if (x == y) return false;

		// merge technique（データ構造をマージするテク．小を大にくっつける）
		if (siz[x] < siz[y]) swap(x, y);
		siz[x] += siz[y];
		par[y] = x;
		return true;
	}



	bool issame(ll x, ll y) { // 連結判定
		return root(x) == root(y);
	}

	ll size(ll x) { // 素集合のサイズ
		return siz[root(x)];
	}


};*/


long long N, M, K, a, b, c, d, e, H, W, L;
long long A[200005] = {};
long long B[5005][5] = {};
long long C[205][205] = {};
long long x[200005] = {};
long long y[200005] = {};
bool f, ff;
string S[2];
set <long long>sll;
pl bufpl;
vector <long long>vl[3];
vector <pl>vpl;
vector <string> vs;
set<ll> llset;

/*struct ST
{
	long long Kati;
	int bangou;

	bool operator<(const ST& another) const
	{
		return Kati < another.Kati;//比較
	};

};



vector <ST> vst;
ST st[200005];
ST bufst;
bitset<5000> bits;*/


long long modinv(long long aa, long long mm) {
	long long bb = mm, uu = 1, vv = 0;
	while (bb) {
		long long tt = aa / bb;
		aa -= tt * bb; swap(aa, bb);
		uu -= tt * vv; swap(uu, vv);
	}
	uu %= mm;
	if (uu < 0) uu += mm;
	return uu;
}


ll minn, maxx;

int main() {

	cin >> N>>a;

	if (N < a) {
		cout << 0 << endl;
	}
	else {
		cout << 10 << endl;
	}



	return 0;

}


Measured memory_bytes: 256
from itertools import accumulate
from bisect import bisect

H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

q = [[] for _ in range(D)]
for y, a in enumerate(A):
    for x, s in enumerate(a):
        q[s%D].append((s, x, y))

q = [sorted(q_i) for q_i in q]
# print(q)
t = [[q_j[0] for q_j in q_i] for q_i in q]
p = []
for q_i in q:
    p.append([])
    bx, by = 0, 0
    for q_j in q_i:
        _, x, y = q_j
        p[-1].append(abs(x-bx)+abs(y-by))
        bx, by = x, y
    p[-1] = [0] + list(accumulate(p[-1][1:]))

# print(p)
# print(t)

for l, r in LR:
    start = bisect(t[l%D], l)-1
    end = bisect(t[l%D], r)-1
    print(p[l%D][end]-p[l%D][start])
    # print(start, end, t[l%D], p[l%D])


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

vector<vector<int>> c(1001,vector<int>(1001));

int lcs(string &X,string &Y){
    int m=X.size();
    int n=Y.size();
    X=' '+X;
    Y=' '+Y;
    for(int i=0;i<m+1;i++) c[i][0]=0;
    for(int i=1;i<n+1;i++) c[0][i]=0;
    for(int i=1;i<m+1;i++){
        for(int j=1;j<n+1;j++){
            if(X[i]==Y[j]){
                c[i][j]=c[i-1][j-1]+1;
            }
            else{
                c[i][j]=max(c[i][j-1],c[i-1][j]);
            }
        }
    }
    return c[m][n];
}

int main(){
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        string X,Y;
        cin>>X>>Y;
        cout<<lcs(X,Y)<<endl;
    }
}


Measured memory_bytes: 6700
#include <bits/stdc++.h>
using namespace std;
int main(){
  string a, b, c;
  cin >> a >> b >> c;
  printf("%c%c%c\n", a[0] - 'a' + 'A', b[0] - 'a' + 'A', c[0] - 'a' + 'A');
  return 0;
}


Measured memory_bytes: 256
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <bitset>    // bitset
#include <cctype>    // isupper, islower, isdigit, toupper, tolower
#include <cstdint>   // int64_t, int*_t
#include <cstdio>    // printf
#include <deque>     // deque
#include <iostream>  // cout, endl, cin
#include <map>       // map
#include <queue>     // queue, priority_queue
#include <set>       // set
#include <stack>     // stack
#include <string>    // string, to_string, stoi
#include <tuple>     // tuple, make_tuple
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <utility>       // pair, make_pair
#include <vector>        // vector
using namespace std;

int main() {
    string S, T;
    cin >> S >> T;
    cout << T << S << endl;

    return 0;
}

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

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

Measured memory_bytes: 256
//                                               KEEP GRINDING
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>  
#include <ext/pb_ds/tree_policy.hpp>   
using namespace std;
using namespace __gnu_pbds;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 

#define int long long
#define ld long double
#define MOD 1000000007
#define precise(i) fixed << setprecision(10) << i
#define f(i,a,b) for(int i=a;i<b;++i)

#define endl '\n'
#define debug cout<<"\n========================================\n";
#define err1(a) cout<<#a<<" "<<a<<endl;
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl;
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl;
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<endl;

#define all(a) a.begin(),a.end()
#define show(a) for(auto xyz:a)cout<<xyz<<" ";cout<<endl;
#define PQ priority_queue
#define LB lower_bound  
#define UB upper_bound   

#define fr first
#define sc second
#define sz(x) (int)(x).size()

#define MAXN 200010
#define INF 9223372036854775807

void solve(){
	int n;
	cin>>n;
	map<int,int> map;
	f(x,1,105)f(y,1,105)f(z,1,105)map[ x*x + y*y + z*z + x*y + y*z + z*x ]++;
	f(i,1,n+1)cout<<map[i]<<endl;
}
signed main(){
    fastio
    int t=1;
    for(;t--;solve());
}

Measured memory_bytes: 6256
#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_variables)]
#![allow(unused_mut)]
#![allow(unused_assignments)]
use proconio::input;
use proconio::marker::Usize1;
use std::collections::*;
use std::cmp::*;
use std::f64::consts::*;

const MOD: u64 = 1000000007;
const INF: usize = std::usize::MAX / 4;

fn main() {
    input! {
        N: usize,
        A: [i64; N],
    }

    let mut cnt: HashMap<i64, usize> = HashMap::new();
    let mut ans: usize = 0;

    for (i, &a) in A.iter().enumerate() {
        ans += *cnt.entry((i as i64) - a).or_default();
        *cnt.entry((i as i64) + a).or_insert(0) += 1;
    }

    println!("{}", ans);
}


Measured memory_bytes: 18396
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<cstdio>
#include<stack>
#include<queue>
#include<fstream>
#include<cstdio>
#include<deque>
#include<iomanip>
#include <numeric>
//#include<bits/stdc++.h>

using namespace std;
#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);(i)--)
#define all(a) (a).begin(),(a).end()
#define reall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
const double pi = acos(-1.0);

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef deque<ll> dll;
typedef pair<ll, ll> P;
const ll mod = 1e9 + 7;
ll dx[4] = { 1,0,-1,0 };
ll dy[4] = { 0,1,0,-1 };

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

	ll n, m, k, ans = 0;
	cin >> n >> k;
	vll dp(n,M),v(n);
	rep(i, n) cin >> v[i];
	dp[0] = 0;
	rep(i,n) {
		rep(j,k+1) if(i-j > -1) dp[i] = min(dp[i - j] + abs(v[i] - v[i - j]), dp[i]);
	}
	//rep(i, n) cout << dp[i] << " ";
	//cout << endl;
	cout << dp[n-1] << endl;
	return 0;
}


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

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            //[summary]C - Replacing Integer
            var line = ReadLine();
            var N = line[0];
            var K = line[1];

            var min = long.MaxValue;

            var numbers = new Dictionary<long, int>();

            N %= K;

            while (true)
            {
                N = Math.Abs(N - K);

                if (!numbers.ContainsKey(N))
                {
                    numbers.Add(N, 1);
                    min = Math.Min(min, N);
                }
                else
                {
                    break;
                }
            }

            Console.WriteLine(min);
        }

        static List<long> ReadLine()
        {
            var line = Console.ReadLine();
            var arr = line.Split(' ');

            return arr.Select(x => long.Parse(x)).ToList();
        }
    }
}

Measured memory_bytes: 11360
from collections import defaultdict
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree


class Point:
 
    def __init__(self, index, x, y):
        self.index = index
        self.x = x
        self.y = y


def create_graph(N, points):
    # Caclulate costs
    costs = defaultdict(int)
    costs_defined = defaultdict(int)
    # Sort by `x` and create edges between adjacent nodes
    points = sorted(points, key=lambda p: p.x)
    for i in range(N - 1):
        p = points[i]
        next_p = points[i + 1]
        cost = next_p.x - p.x
        min_index, max_index = min([p.index, next_p.index]), max([p.index, next_p.index])
        costs[(min_index, max_index)] = cost
        costs_defined[(min_index, max_index)] = 1
    # Sort by `y` and create edges between adjacent nodes
    points = sorted(points, key=lambda p: p.y)
    for i in range(N - 1):
        p = points[i]
        next_p = points[i + 1]
        cost = next_p.y - p.y
        min_index, max_index = min([p.index, next_p.index]), max([p.index, next_p.index])
        current_cost = costs[(min_index, max_index)]
        if costs_defined[(min_index, max_index)]:
            new_cost = min([cost, current_cost])
            costs[(min_index, max_index)] = new_cost
        else:
            costs[(min_index, max_index)] = cost
    # Create csgraph
    rows = list()
    cols = list()
    data = list()
    for node_pair, cost in costs.items():
        rows.append(node_pair[0])
        cols.append(node_pair[1])
        data.append(cost)
    return csr_matrix((data, (rows, cols)), shape=(N, N))

 
def main():
    N = int(input())
    points = list()
    for index in range(N):
        x, y = list(map(int, input().split(' ')))
        points.append(Point(index, x, y))
    graph = create_graph(N, points)
    mst = minimum_spanning_tree(graph)
    print(int(mst.sum()))
 
 
if __name__ == '__main__':
    main()

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

int main(){
  int n,d;
  int f[50];
  while(cin>>n,n){
    vector<int> day[30];
    for(int i=0;i<n;i++){
      cin>>f[i];
      for(int j=0;j<f[i];j++){
	cin>>d;
	day[d-1].push_back(i);
      }
    }
    bool gather=false;
    set<int> a; set<int> b[n];
    for(int i=0;i<n;i++) b[i].insert(i);
    for(int i=0;i<30;i++){
      for(int j=0;j<day[i].size();j++)
	set_union(a.begin(),a.end(),b[day[i][j]].begin(),b[day[i][j]].end(),
		  inserter(a,a.end()));
      if(a.size()==n){
	cout<<i+1<<endl; gather=true; break;
      }
      for(int j=0;j<day[i].size();j++) b[day[i][j]]=a;
      a.clear();
    }
    if(!gather) cout<<-1<<endl;
  }
}


Measured memory_bytes: 1340
#include<stdio.h>
int main()
{
  int n, i, j, k, v, x, cnt=0, m=0;
  int A[1000000];
  int G[1000000];

  scanf("%d", &n);
   
  for(i = 0 ; i < n ; i++) {
    scanf("%d", &A[i]);
  }
   
  G[0] =1 ;
  for(i = 1 ; G[i-1] <= n ; i++) {
    m++;
    G[i] = G[i-1] * 3 + 1;
    if(m > 100) break;
  }
  for(i = 0 ; i< m/2 ; i++) {
    x = G[i];
    G[i] = G[m-i-1];
    G[m-i-1] = x;
  }
   
   
  for(i = 0 ; i < m ; i++) {
    for(j = G[i] ; j < n ; j++) {
      v = A[j];
      k = j - G[i];
      while(k >= 0 && A[k] > v) {
        A[k+G[i]] = A[k];
        k = k - G[i];
        cnt++;
      }
      A[k+G[i]] = v;
    }
  }
   
  printf("\n%d\n", m);
  for(i = 0  ; i < m ; i++) {
    printf("%d ", G[i]);
  }
  printf("\n%d\n", cnt);
  for(i = 0 ; i < n ; i++) {
    printf("%d\n", A[i]);
  
  }
  return 0;
}


Measured memory_bytes: 5684
#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;
#define EPS 1.0e-10

int main(){
    long double a,b,h,m;
    scanf("%Lf %Lf %Lf %Lf", &a, &b, &h, &m);
    long double Theta = (h / 6 - m * 11 / 360) * M_PI;
    long double dAns = sqrt(a * a + b * b - 2 * a * b * cosl(Theta));
    printf("%.15Lf", dAns);   
    
    return 0;
}


Measured memory_bytes: 3564