akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define mt              make_tuple
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define range(a,b)		substr(a,b-a+1)
#define w(x)            int x; cin>>x; while(x--)
#define trace(x) 		cerr<<#x<<": "<<x<<" "<<endl;
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

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

struct FenwickTree
{
	int N;
	vector<int> tree;

	FenwickTree(int n)
	{
		N = n;
		tree.assign(n + 1, 0);
	}

	void update(int idx, int val)
	{
		while (idx <= N)
		{
			tree[idx] += val;
			idx += idx & -idx;
		}
	}

	void updateMax(int idx, int val)
	{
		while (idx <= N)
		{
			tree[idx] = max(tree[idx], val);
			idx += idx & -idx;
		}
	}

	int pref(int idx)
	{
		int ans = 0;
		while (idx > 0)
		{
			ans += tree[idx];
			idx -= idx & -idx;
		}
		return ans;
	}

	int rsum(int l, int r)
	{
		return pref(r) - pref(l - 1);
	}

	int prefMax(int idx)
	{
		int ans = 0;
		while (idx > 0)
		{
			ans = max(ans, tree[idx]);
			idx -= idx & -idx;
		}
		return ans;
	}
};

int32_t main()
{
	FIO;
	int n; cin >> n;
	FenwickTree bit(n);

	mk(a, n + 1, int);
	mk(h, n + 1, int);

	for (int i = 1; i <= n; ++i)
		cin >> h[i];

	for (int i = 1; i <= n; ++i)
		cin >> a[i];

	int ans = 0;

	for (int i = 1; i <= n; ++i)
	{
		int val = a[i] + bit.prefMax(h[i] - 1);
		ans = max(ans, val);
		bit.updateMax(h[i], val);
	}

	cout << ans << '\n';

	return 0;
}

Measured memory_bytes: 7976
#include<bits/stdc++.h>
using namespace std;
#define int long long
//BEGIN CUT HERE
int MOD=1000000009LL; //<- alert!!!
typedef vector<int> arr;
typedef vector<arr> mat;
inline arr mul(mat a,arr& b,int mod){
  arr res(b.size(),0);
  for(int i=0;i<(int)b.size();i++)
    for(int j=0;j<(int)a[i].size();j++)
      (res[i]+=a[i][j]*b[j])%=mod;
  return res;
}
inline mat mul(mat& a,mat& b,int mod){
  mat res(a.size(),arr(b[0].size(),0));
  for(int i=0;i<(int)a.size();i++)
    for(int j=0;j<(int)b[0].size();j++)
      for(int k=0;k<(int)b.size();k++)
	(res[i][j]+=a[i][k]*b[k][j])%=mod;
  return res;
}
mat base;
inline mat mat_pow(mat a,int n,int mod){
  if(base.empty()){
    base=mat(a);
    for(int i=0;i<(int)a.size();i++)
      for(int j=0;j<(int)a[i].size();j++)
	base[i][j]=(i==j);
  }
  mat res(base);
  while(n){
    if(n&1) res=mul(a,res,mod);
    a=mul(a,a,mod);
    n>>=1;
  }
  return res;
}
mat memo[100];
void init(mat a,int mod){
  base=mat(a);
  for(int i=0;i<(int)base.size();i++)
    for(int j=0;j<(int)base.size();j++)
      base[i][j]=i==j;
  memo[0]=a;
  for(int k=1;k<70;k++)
    memo[k]=mul(memo[k-1],memo[k-1],mod);
}
inline mat mat_pow2(int w,int n,int mod){
  mat res(base);
  int k=0;
  while(n){
    if(n&1) res=mul(memo[k],res,mod);
    n>>=1;
    k++;
  }
  return res;
}
//END CUT HERE

typedef pair<int,int> P;
signed main(){
  int w,h,n,cnt=0;
  while(cin>>w>>h>>n,w||h||n){
    int x[n],y[n];
    for(int i=0;i<n;i++) cin>>x[i]>>y[i];
    P p[n];
    for(int i=0;i<n;i++) p[i]=P(y[i],x[i]);
    sort(p,p+n);
    for(int i=0;i<n;i++) x[i]=p[i].second,y[i]=p[i].first;
    arr a(w,0);
    a[0]=1;
    mat b(w,arr(w,0));
    for(int i=0;i<w;i++){
      for(int j=0;j<w;j++) b[i][j]=0;
      b[i][i]=1;
      if(i-1>=0) b[i][i-1]=1;
      if(i+1<w)  b[i][i+1]=1;
    }
    init(b,MOD);
    int d=1;
    for(int k=0;k<n;k++){
      if(y[k]==d) continue;
      //cout<<k<<endl;
      a=mul(mat_pow2(w,y[k]-d-1,MOD),a,MOD);
      int j=k;
      mat c=b;
      while(j<n&&y[k]==y[j]){
	for(int i=0;i<w;i++) c[x[j]-1][i]=0;
	j++;
      }
      a=mul(c,a,MOD);
      d=y[k];
      //cout<<"a:";for(int i=0;i<w;i++) cout<<a[i]<<" ";cout<<endl;
    }
    //cout<<"a:";for(int i=0;i<w;i++) cout<<a[i]<<" ";cout<<endl;
    a=mul(mat_pow2(w,h-d,MOD),a,MOD);
    //cout<<"a:";for(int i=0;i<w;i++) cout<<a[i]<<" ";cout<<endl;
    cout<<"Case "<<++cnt<<": "<<a[w-1]<<endl;
  }
  return 0;
}

/*
verified on 2017/06/29
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2397
*/

Measured memory_bytes: 6496
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder Newbuilt = new StringBuilder(); //????????????????????????????????????????????????
      //H??¨W?????\?????????????????????????????§???  
        while (true) {
            String[] array = sc.nextLine().split(" ");
            int H = Integer.parseInt(array[0]);
            int W = Integer.parseInt(array[1]);
            if (H == 0 && W == 0) break ;
      //????????¢?????¢???????¨???????????????¶ HxW
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    Newbuilt.append("#");
                }
                Newbuilt.append("\n");
            }
            Newbuilt.append("\n");
             
        }
       //StringBuilder?????????????????????????????????????????????????????????
        System.out.print(Newbuilt);
        
        sc.close();
    }
}

Measured memory_bytes: 27236
#include <vector> 
#include <list> 
 #include <map>
 #include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#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)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << '=' << (x) << endl;
#define debug(x) cerr << #x << '=' << (x) << '('<<'L' << __LINE__ << ')' << ' ' << __FILE__ << endl;

string s,t;

int main(){
    cin>>s>>t;

    for(int i=0;i<s.size();i++){
        if(s[i]<t[i]){
            cout<<"<"<<endl;
            return 0;
        }
        else if(s[i]>t[i]){
            cout<<">"<<endl;
            return 0;
        }
        
    }

            cout<<"="<<endl;
    
    




}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define int long long

const int mod = 1e9 + 7;

int32_t main() {
	int s;
	cin >> s;
	int ans = 0;
	vector<vector<int>> c(s + 1, vector<int>(s + 1, 1));
	for (int i = 1; i <= s; ++i) {
		for (int j = 1; j < i; ++j) {
			c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
			c[i][j] %= mod;
		}
	}
	for (int i = 1; i < s; ++i) {
		if (s - i * 3 < 0) break;
		ans += c[s - i * 3 + i - 1][i - 1];
		ans %= mod;
	}
	cout << ans;
}

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

int main()
{
  int n;
  cin >> n;
  map<string, uint64_t> m;

  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    sort(begin(s), end(s));
    m[s]++;
  }

  uint64_t ans = 0;
  for (const auto& e : m) {
    uint64_t t = e.second;
    ans += t * (t - 1) / 2;
  }
  cout << ans << endl;
}


Measured memory_bytes: 11136
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;

long long N, X[1009], Y[1009], H[1009];
vector<tuple<long long, long long, long long>> vec;

int main(){
  cin >> N;
  tuple<long long, long long, long long> G = make_tuple(-1, -1, -1);
  for (int i = 1; i <= N; i++){
    cin >> X[i] >> Y[i] >> H[i];
    if (H[i] >= 1) G = make_tuple(X[i], Y[i], H[i]);
  }
  for (int i = 0; i <= 100; i++){
    for (int j = 0; j <= 100; j++){
      long long V = get<2>(G) + abs(get<0>(G) - i) + abs(get<1>(G) - j);
      V = max(V, 0LL);
      bool flag = true;
      for (int k = 1; k <= N; k++){
        long long VV = V - abs(X[k] - i) - abs(Y[k] - j);
        VV = max(VV, 0LL);
        if (H[k] != VV) flag = false;
      }
      if (flag == true) vec.push_back(make_tuple(i, j, V));
    }
  }
  if (vec.size() == 1){
    cout << get<0>(vec[0]) << " " << get<1>(vec[0]) << " " << get<2>(vec[0]) << endl;
  }
  return 0;
}


Measured memory_bytes: 256
import java.util.*;
 import java.math.BigInteger;
public class Main
{
	static int ans[];
	public static  void main(String args[])
	{
		Scanner sc=new Scanner(System.in);
		int k=Integer.parseInt(sc.nextLine());
		String n=sc.nextLine();
		if(n.length()<=k){System.out.println(n);}
		else{System.out.println(n.substring(0,k)+"...");}
		

	}
	
	// static int dfs4(int dp[], ArrayList<Pair>arr, int state, int gg[], int i, int x, int cost)

	// {
	// 	if(i==arr.size()){for(int j=0;j<gg.length;j++){if(gg[j]<x){return Integer.MAX_VALUE;}}return cost;}
	// 	if(dp[state]!=0){return dp[state];}
	// 	int a=dfs4(dp,arr,state,gg,i+1,x,cost);
	// 	int aa[]=new int[gg.length];
	// 	System.arraycopy(gg,0,aa,0,aa.length);
	// 	for(int j=0;j<arr.get(i).b.size();j++)
	// 	{
	// 		aa[j]+=arr.get(i).b.get(j);
	// 	}
	// 	// System.out.println(Arrays.toString(aa));
	// 	state=state+(int)Math.pow(2,i);
	// 	int b=dfs4(dp,arr,state,aa,i+1,x,cost+arr.get(i).a);
	// 	dp[state]=Math.min(a,b);
	// 	return Math.min(a,b);
	// }
	// static long get3(double n, int steps)
	// {
	// 	if(n<1){return Integer.MAX_VALUE;}
	// 	if(n==1){return steps;}

	// 	System.out.println(n);
	// 	return get3(n/2.0-1,steps+1);
	// }
	// static String get(long a, long b)
	// {long y=1;
	// 	while(true)
	// 	{

	// 		long z=y-a;
	// 		long q=get2(y,z);
	// 		// System
	// 		if(q==b){return y+" "+z;}
	// 		else if(q>b){return "-1";}
	// 		y+=1;
	// 	}
	// 	// return "-1";
	// }
	// static long get2(long y, long z)
	// {
	// 	return (long)(Math.pow(y,4)+Math.pow(y,3)*z+Math.pow(y,2)*Math.pow(z,2)+y*Math.pow(z,3)+Math.pow(z,4));
	// }
	// static void get(ArrayList<ArrayList<Integer>>arr, int i , int p,int val[], int arr1[], int len)
	// {
	// 	for(int j=0;j<arr.get(i).size();j++)
	// 	{
	// 		if(ans[arr.get(i).get(j)]==0 && arr.get(i).get(j)!=p){
	// 		if(val[arr.get(i).get(j)]>arr1[len-1])
	// 		{
	// 			arr1[len]=val[arr.get(i).get(j)];
	// 			ans[arr.get(i).get(j)]=len+1;
	// 			get(arr,arr.get(i).get(j),i,val,arr1,len+1);
				
	// 		}
	// 		else
	// 		{
	// 			int index=bin(arr1, val[arr.get(i).get(j)], len-1);
	// 			ans[arr.get(i).get(j)]=len;
	// 			// int g=arr1[index];
	// 			arr1[index]=val[arr.get(i).get(j)];
	// 			get(arr,arr.get(i).get(j),i,val,arr1,len);
	// 			// arr1[index]=g;
	// 		}}

	// 	}
	// }
	// static int bin(int arr[], int val, int len)
	// {
	// 	if(arr[0]>=val){return 0;}
	// 	int l=0;
	// 	int r=len;
	// 	while (r - l > 1) { 
 //            int m = l + (r - l) / 2; 
 //            if (arr[m] >= val) 
 //                r = m; 
 //            else
 //                l = m; 
 //        } 
  
 //        return r; 
	// 	// return l;
	// }
	
	

}
class Pair
{
	int a;
int b;
	Pair(int e,int  f){
		a=e;
		b=f;
		
	}
}



	


Measured memory_bytes: 38624
/*
このコード、と～おれ!
Be accepted!
∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
		  　　　　　　　　　　(¸.·´ (¸.·'* ☆
					*/

#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
#include <random>
#include <map>
#include <unordered_map>
#include <queue>
#include <regex>
#include <functional>
#include <complex>
#include <list>
#include <cassert>
/*多倍長整数/cpp_intで宣言
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
*/

//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for(int i = 1; i <= (n); ++i)
#define rep2(i, n) for(int i = 2; i < (n); ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define reprm(i, n) for(int i = n - 1; i >= 0; --i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printin(a) printf(a ? "possible\n" : "imposible\n")
#define printdb(a) printf("%.50lf\n", a)//少数出力
#define printdbd(a) printf("%.16lf\n", a)//少数出力(桁少なめ)
#define prints(s) printf("%s\n", s.c_str())//string出力
#define all(x) (x).begin(), (x).end()
#define allsum(a, b, c) ((a + b) * c / 2)//等差数列の和、初項,末項,項数
#define pb push_back
#define priq priority_queue
#define rpriq priq<int, vector<int>, greater<int>>
#define deg_to_rad(deg) (((deg)/360.0)*2.0*PI)
#define rad_to_deg(rad) (((rad)/2.0/PI)*360.0)
#define Please return
#define AC 0
#define addf(T) [](T a, T b){return (a + b);}
#define minf(T) [](T a, T b){return min(a, b);}
#define maxf(T) [](T a, T b){return max(a, b);}


using ll = long long;

constexpr int INF = 1073741823;
constexpr int MINF = -1073741823;
constexpr ll LINF = ll(4661686018427387903);
constexpr ll MOD = 1000000007;
const long double PI = acos(-1.0L);

using namespace std;

void scans(string& str) {
	char c;
	str = "";
	scanf("%c", &c);
	if (c == '\n')scanf("%c", &c);//最初の改行対策
	while (c != '\n' && c != -1) {
		str += c;
		scanf("%c", &c);
	}
}

void scanc(char& str) {
	char c;
	scanf("%c", &c);
	if (c == -1)return;
	while (c == '\n') {
		scanf("%c", &c);
	}
	str = c;
}

double acot(double x) {
	return PI / 2 - atan(x);
}

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

ll lcm(ll number1, ll number2) {//lcmを求める
	return number1 / gcd(number1, number2) * number2;
}

ll LSB(ll n) { return (n & (-n)); }

/*-----------------------------------------ここからコード-----------------------------------------*/



int main() {

	int n, t, a, ans;
	scanf("%d%d%d", &n, &t, &a);
	double u = INF, h;
	rep(i, n) {
		scanf("%lf", &h);
		h = t - h * 0.006;
		if (abs((double)a - h) < u) {
			ans = i + 1;
			u = abs((double)a - h);
		}
	}
	printf("%d\n", ans);

	Please AC;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define _GLIBCXX_DEBUG
#define rep(i, c) for (int i = 0; i < (int)c; i++)
#define debug(x) cout << #x << " = " << x << endl
#define print(x) cout << x << endl;
const ll MOD = 1000000007;

int main()
{
    long double A, B;
    cin >> A >> B;
    ll ans = A * B;
    cout << ans << endl;
}


Measured memory_bytes: 3744
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using Pll = pair<ll, ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
const int MOD = 1e9+7;
const int INF = 2e9;
template<class T> void print(const T& t){ cout << t << endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main(){
  ll n;
  cin >> n;
  ll count = 0;
  ll now;
  cin >> now;
  ll ans = 0;
  for (ll i = 1; i < n; i++){
    ll next;
    cin >> next;
    if (now >= next){
      count++;
      now = next;
    }
    else{
      count = 0;
      now = next;
    }
    chmax(ans, count);
  }
  print(ans);
}

Measured memory_bytes: 256
n = int(input())
A = [int(input()) for i in range(n)]
maxA = max(A)
if A.count(maxA) == 1:
  maxA_2 = max([i for i in A if i != maxA])
  for i in range(n):
    if A[i] != maxA:
      print(maxA)
    else:
      print(maxA_2)
else:
  for i in range(n):
    print(maxA)

Measured memory_bytes: 12588
N,M=map(int,input().split())
# N:売店数
# M:買う数
AB=[]
for i in range(N):
  ab=list(map(int,input().split()))
  AB.append(ab)
#AB[0]:A円，AB[1]:最大B本まで買える

list.sort(AB,key=lambda x:x[0])
#print(AB)

m=0 #買う数
cost=0 #かかる値段
for i in range(N):
 
 if M-m==AB[i][1]:
     m+=AB[i][1]
     cost+=AB[i][0]*AB[i][1]
     break
 elif M-m<AB[i][1] :
      for j in range(AB[i][1]+1):
         cost=cost+AB[i][0]*j
         m=m+j
         if m==M:
             break
         elif m<M:
             cost=cost-AB[i][0]*j
             m=m-j
 else:
      cost+=AB[i][0]*AB[i][1]
      m+=AB[i][1]
    
print(cost)

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


int main() {
  string s;
  cin >> s;
  if(s == "Sunny") {
    cout << "Cloudy" << endl;
  }
  else if (s == "Cloudy"){
    cout << "Rainy" << endl;
  }
  else{
    cout << "Sunny" << endl;
  }
  return 0;
}

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

#ifdef LOCAL
#include "debug.h"
#else
#define DEBUG(...)
#endif

using R = long double;
constexpr R eps = 1e-14;
int sgn(R a) { return (a > eps) - (a < eps); }
int sgn(R a, R b) { return sgn(a - b); }

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  R a, b, c;
  cin >> a >> b >> c;
  cout << (sqrt(a) + sqrt(b) + eps < sqrt(c) ? "Yes\n" : "No\n");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair<ll, ll>
#define F first
#define S second
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }
//sort(all(x))とするとソートできるよ
// 10^x は pow(10,(x)) 
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

double dp[310][310][310];
int N;

double rec(int i,int j,int k){
    if(dp[i][j][k] >= 0)return dp[i][j][k];
    if(i == 0 && j == 0 && k == 0)return 0.0;

    double res = 0.0;
    if(i > 0)res += rec(i-1,j,k) * i;
    if(j > 0)res += rec(i+1,j-1,k) * j;
    if(k > 0)res += rec(i,j+1,k-1) * k;
    res += N;
    res *= 1.0 / (i+j+k);

    return dp[i][j][k] = res;
}

int main(){
    cin >> N;
    int one = 0,two = 0,thr = 0;
    rep(i,N){
        int a;cin >> a;
        if(a == 1)one++;
        else if(a == 2)two++;
        else thr++;
    }


    memset(dp,-1,sizeof(dp));   //初期化

    cout << fixed << setprecision(10) << rec(one,two,thr) << endl;

}



Measured memory_bytes: 233088
#define _USE_MATH_DEFINES
#include  <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include<math.h>
#include<iomanip>
#include<stdio.h>
#include <stdlib.h>
#include<stdio.h>
#include <queue>
#include<map>
#include <sstream>
#include<set>
#include<stack>

//#include<bits/stdc++.h>


using namespace std;


pair<pair<int,int>,int>p[100005];
	int w[100005]={};
	int h[100005] = {};
int main() {
	
	int n, m;
	cin >> n >> m;
	
	for (int i = 0; i < m; i++) {

		int t, y;
		cin >> t >> y;
		
		w[i] = t;
//		h[y]  ++;
		p[i] = make_pair(make_pair(t, y), i);
	}

		sort(p,p+m);

		pair<int, int>ans[100005];
		int c = 1;
		h[0] = 1;
		for (int i = 1; i < m; i++) {
			if (i&&p[i].first.first == p[i - 1].first.first)h[i]=h[i-1]+1;
			else if (i) h[i] = 1;
		//	cout << p[i].first << p[i - 1].first << endl;
		}

		for (int i = 0; i < m; i++) {
			if (i&&p[i].second != p[i - 1].second)c++;
			else if(i) c = 1;
			ans[p[i].second] = make_pair(p[i].first.first, h[i]);
		}
	
		for (int i = 0; i < m; i++) {
			printf("%06d%06d\n", ans[i].first, ans[i].second);
//			cout<<ans[i].first << ans[i].second << endl;
		}

	


	return 0;



}

Measured memory_bytes: 4224
//#include "debug.h"
#include <string.h>
#include <limits.h>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 200000

int n;
int a[MAXN], b[MAXN], c[MAXN];

int input() {
	if (scanf("%d", &n) < 0) return 0;
	for (int i=0; i<n; i++) scanf("%d", &a[i]);
	return 1;
}

void init() {
}

int solve() {
	for (int i=0; i<n; i++) b[i] = i;
	sort(b, b+n, [](auto &x, auto &y) {
		return a[x] < a[y];
	});
	int k = n/2-1, j;
	for (int i=0; i<n; i++) {
		if (i<=k) j = k+1;
		else j = k;
		c[b[i]] = a[b[j]];
	}
	return 1;
}

void output(int ans) {
	for (int i=0; i<n; i++)
		printf("%d\n", c[i]);
}

void cleanup() {
}

int main() {
	//int ca; scanf("%d", &ca);
	while (input()) {
		init();
		output(solve());
		cleanup();
		break;
	}
}




Measured memory_bytes: 4480
N=int(input())
xy = [tuple(map(int,input().split())) for _ in range(N)]
ans = 0

def dist(tpl1, tpl2):
    return abs(tpl1[0] - tpl2[0]) + abs(tpl1[1] - tpl2[1])

f0 = []
f1 = []
for i in range(N):
    x, y = xy[i]
    f0.append(x-y)
    f1.append(x+y)
ans = max(ans,
        max(f0) - min(f0),
        max(f1) - min(f1))
print(ans)

Measured memory_bytes: 130656
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao Twitter/QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 10e16
#define MOD 1000000007
#define mod 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef long long int LL;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};
char dir[4]={'u','l','d','r'};
ll cmp1(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????统一类型        memset()!!!!!!!!!!!!       ペナを減らせ!!!!!!!!!!!!!
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    ll h;cin>>h;
    ll ans=0;
    ll dp[100000];
    ll cnt=1;ll i=1;
    memset(dp, 0, sizeof(dp));
    while(h>1){
        ans+=i;
        h/=2;
        i*=2;
    }
    ans+=i;
    cout<<ans<<endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------









Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long a,b,c,d,x,y,z,p,q;
    vector<long long>A;
    vector<long long>B;
    vector<long long>C;
    vector<long long>gt;
    cin>>x>>y>>a>>b>>c;
    for(long long i=0; i<a; i++)
    {
        cin>>p;
        A.push_back(p);
    }
    for(long long i=0; i<b; i++)
    {
        cin>>p;
        B.push_back(p);
    }
    for(long long i=0; i<c; i++)
    {
        cin>>p;
        C.push_back(p);
    }
    /* for(long long i=0; i<a; i++)
        cout<<A[i]<<endl;
       for(long long i=0; i<b; i++)
        cout<<B[i]<<endl;
          for(long long i=0; i<c; i++)
        cout<<C[i]<<endl;*/
    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
    //
    for(long long i=a-1; i>=a-x; i--)
    {
        p=A[i];
        C.push_back(p);
    }

    for(long long i=b-1; i>=b-y; i--)
    {
        p=B[i];
        C.push_back(p);
    }

     //cout<<"*"<<endl;
      //for(long long i=0; i<C.size(); i++)
        //cout<<C[i]<<endl;

    sort(C.begin(),C.end());
    long long sum=0;
    for(long long i=C.size()-1; i>=C.size()-(x+y); i--)
    {
        sum+=C[i];
             // C.push_back(p);
    }
    cout<<sum;

}


Measured memory_bytes: 8048
import sys
input=sys.stdin.readline
from collections import deque
class LCA:
    def __init__(self,v,Edges,root=0):
        self.v=v
        self.Edges=Edges
        self.maxLog=18
        self.Parent=[[-1]*v for _ in range(self.maxLog+1)]
        self.Depth=[0]*v
        self.__bfs(root)
        for i in range(self.maxLog):
            for j in range(v):
                if self.Parent[i][j]!=-1:
                    self.Parent[i+1][j]=self.Parent[i][self.Parent[i][j]]
    def __bfs(self,root):
        Visited=[False]*self.v
        Visited[root]=True
        q=deque([root])
        while q:
            fr=q.pop()
            for to in self.Edges[fr]:
                if Visited[to]:
                    continue
                self.Parent[0][to]=fr
                self.Depth[to]=self.Depth[fr]+1
                Visited[to]=True
                q.append(to)
    def lca(self,a,b):
        if self.Depth[a]>self.Depth[b]:
            a,b=b,a
        for i in range(self.maxLog):
            if (self.Depth[b]-self.Depth[a])&(1<<i):
                b=self.Parent[i][b]
        if a==b:
            return b
        for i in reversed(range(self.maxLog-1)):
            if self.Parent[i][a]!=self.Parent[i][b]:
                a=self.Parent[i][a]
                b=self.Parent[i][b]
        return self.Parent[0][a]

def Eulertour(Edges,n,root=0):
    Euler=[]
    Depth=[-1]*n
    Depth[root]=0
    que=deque([root])
    que2=deque()
    Visited=[False]*n
    while que:
        fr=que.pop()
        Euler.append((Depth[fr],fr))
        if Visited[fr]:
            continue
        for to in Edges[fr]:
            if Visited[to]:
                que.append(to)
            else:
                Depth[to]=Depth[fr]+1
                que2.append(to)
        que.extend(que2)
        que2=deque()
        Visited[fr]=True
    return Euler

n,q=map(int,input().split())
Edgedict=[dict() for _ in range(n)]
for _ in range(n-1):
    a,b,c,d=map(int,input().split())
    a-=1; b-=1
    Edgedict[a][b]=(c,d)
    Edgedict[b][a]=(c,d)
Queries=[tuple(map(int,input().split())) for _ in range(q)]
Euler=Eulertour(Edgedict,n)
lca=LCA(n,Edgedict)
Q=[[] for _ in range(n)]
for i,(x,y,u,v) in enumerate(Queries):
    u-=1; v-=1
    Q[u].append([i,x,y,True])
    Q[v].append([i,x,y,True])
    Q[lca.lca(u,v)].append([i,x,y,False])
Ans=[0]*q
dist=0
C_len=[0]*n
C_cnt=[0]*n
for i in range(1,len(Euler)):
    idx=Euler[i][1]
    c,l=Edgedict[Euler[i-1][1]][idx]
    if Euler[i-1][0]<Euler[i][0]:
        dist+=l
        C_len[c]+=l
        C_cnt[c]+=1
        for q_idx,x,y,flag in Q[idx]:
            if flag:
                Ans[q_idx]+=dist+C_cnt[x]*y-C_len[x]
            else:
                Ans[q_idx]-=(dist+C_cnt[x]*y-C_len[x])*2
    else:
        dist-=l
        C_len[c]-=l
        C_cnt[c]-=1
print(*Ans,sep='\n')

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

using namespace std;
using ll = long long;
constexpr long long MOD = 1e9 + 7;
long long factrial[10000];
long long Repeat(long long a, long long cnt) {
    if(cnt == 0) return 1LL;
    if(cnt % 2 == 1) {
        long long x = Repeat(a, cnt / 2);
        return (((a * x) % MOD) * x) % MOD;
    } else {
        long long x = Repeat(a, cnt / 2);
        return (x * x) % MOD;
    }
}

long long fact(long long a) {
    if(a == 0)
        return 1LL;
    else if(factrial[a] != 0)
        return factrial[a];
    else
        return factrial[a] = (a * fact(a - 1)) % MOD;
}

long long comb(long long a, long long b) {
    long long fa, fb, fab;
    fa = fact(a);
    fb = fact(b);
    fab = fact(a - b);
    fb = Repeat(fb, MOD - 2);
    fab = Repeat(fab, MOD - 2);
    return (((fa * fb) % MOD) * fab) % MOD;
}

int main(){
    ll N, K;
    cin >> N >> K;
    for(ll i = 1; i <= K;i++){
        if(N-K+1>=i)cout << comb(K - 1, i - 1) * comb(N - K + 1, i) % MOD << endl;
        else
            cout << 0 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
n = int(input())
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())))
c = sorted(list(map(int, input().split())))

bc_count = [0] * n
ci = 0
for bi in range(n):
    while ci < n and b[bi] >= c[ci]:
        ci += 1
    bc_count[bi] = n-ci

for i in range(n-1, 0, -1):
    bc_count[i-1] += bc_count[i]

ans = 0
bi = 0
for ai in range(n):
    while bi < n and a[ai] >= b[bi]:
        bi += 1
    if bi < n: ans += bc_count[bi]
print(ans)



Measured memory_bytes: 22720
#include<bits/stdc++.h>
#define REP(x,y,z) for(int x=y;x<=z;x++)
#define FORD(x,y,z) for(int x=y;x>=z;x--)
#define MSET(x,y) memset(x,y,sizeof(x))
#define FOR(x,y) for(__typeof(y.begin()) x=y.begin();x!=y.end();x++)
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define SZ size()
#define M 
void RI(){}
template<typename... T>
void RI( int& head, T&... tail ) {
    scanf("%d",&head);
    RI(tail...);
}
using namespace std;
typedef long long LL;
int cnt(int x)
{
	int re=0;
	REP(i,1,x) if(x%i==0) re++;
	return re;
}
int main()
{
	int n;
	RI(n);
	REP(i,1,5000) if(cnt(i)==n)
	{
		printf("%d\n",i);
		break;
	}
	return 0;
}

Measured memory_bytes: 1172
n=int(input())

bt=0
bx=0
by=0
ans='Yes'
for i in range(n):
  t,x,y=map(int,input().split())
  dt=t-bt
  dx=abs(x-bx)
  dy=abs(y-by)

  if (dx+dy)>dt:
    ans='No'
  elif (dt-(dx+dy))%2==1:
    ans='No'

  bt=t
  bx=x
  by=y

print(ans)

Measured memory_bytes: 3064
/*** author: yuji9511 ***/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lpair = pair<ll, ll>;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i=(m);i<(n);i++)
#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)
#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
void print() {}
template <class H,class... T>
void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}
ll power(ll x, ll n, ll M){
    if(n == 0) return 1LL;
    ll res = power(x * x % M, n/2, M);
    if(n % 2 == 1) res = res * x % M;
    return res;
}

void solve(){
    ll N;
    cin >> N;
    string X;
    cin >> X;
    ll c1 = 0;
    rep(i,0,N){
        if(X[i] == '1') c1++;
    }
    ll amari1 = 0, amari2 = 0;
    ll pow_val = 1;
    rrep(i,N-1,0){
        amari1 += pow_val * (X[i] - '0') % (c1+1);
        amari1 %= (c1+1);
        pow_val *= 2;
        pow_val %= (c1+1);
    }
    pow_val = 1;
    rrep(i,N-1,0){
        if(c1 <= 1) break;
        amari2 += pow_val * (X[i] - '0') % (c1-1);
        amari2 %= (c1-1);
        pow_val *= 2;
        pow_val %= (c1-1);
    }
    rep(i,0,N){
        if(X[i] == '1'){
            if(c1 == 1){
                print(0);
                continue;
            }
            ll pow_val = power(2, N-1-i, c1-1);
            ll cur = (amari2 - pow_val + (c1-1)) % (c1-1);
            ll ans = 1;
            while(cur > 0){
                ll cnt = __builtin_popcount(cur);
                cur %= cnt;
                ans++;
            }
            print(ans);
        }else{
            ll pow_val = power(2, N-1-i, c1+1);
            ll cur = (amari1 + pow_val) % (c1+1);
            ll ans = 1;
            while(cur > 0){
                ll cnt = __builtin_popcount(cur);
                cur %= cnt;
                ans++;
            }
            print(ans);
        }
    }



    

}

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

Measured memory_bytes: 3780
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <numeric>
#include <string>
#include <bitset>
#include <functional>

using ld = long double;
using vld = std::vector<ld>;
using vvld = std::vector<vld>;
using vvvld = std::vector<vvld>;
using ll = long long;
using vll = std::vector<ll>;
using vvll = std::vector<vll>;
using vvvll = std::vector<vvll>;
using pll = std::pair<ll, ll>;
using vpll = std::vector<pll>;
using str = std::string;
using vstr = std::vector<str>;

template<typename T> bool chmin(T a, T &b) { return a < b ? b = a, true : false; }
template<typename T> bool chmax(T a, T &b) { return a > b ? b = a, true : false; }

constexpr ld PI = 3.141592653589793L;
constexpr ld EPS = std::numeric_limits<ld>::epsilon();

ll gcd(ll n, ll m) { return m ? gcd(m, n % m) : n; }
ll lcm(ll n, ll m) { return n / gcd(n, m) * m; }
bool is_prime(ll n) {
    if (n == 1) return false;
    for (ll i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

/*------------------------------------------------------------------------*/

const vll dy = { -1, 0, 1, 0 }, dx = { 0, 1, 0, -1 };

void solve();

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cout << std::setprecision(15);

    solve();
}

void solve() {
    ll h, w;
    std::cin >> h >> w;

    vstr s(h);
    for (ll i = 0; i < h; i++)
        std::cin >> s[i];

    auto bfs = [&](ll sy, ll sx) -> ll {
        vvll dist(h, vll(w, -1)); dist[sy][sx] = 0;
        std::queue<pll> que; que.push({ sy, sx });

        while (!que.empty()) {
            pll p = que.front(); que.pop();
            ll cy = p.first, cx = p.second;
            for (ll i = 0; i < 4; i++) {
                ll ny = cy + dy[i], nx = cx + dx[i];
                if (0 <= ny && ny < h && 0 <= nx && nx < w
                    && s[ny][nx] == '.' && dist[ny][nx] == -1) {
                    dist[ny][nx] = dist[cy][cx] + 1;
                    que.push({ ny, nx });
                }
            }
        }

        ll max_dist = 0;
        for (ll i = 0; i < h; i++) for (ll j = 0; j < w; j++)
            chmax(dist[i][j], max_dist);

        return max_dist;
    };

    ll ans = 0;
    for (ll i = 0; i < h; i++) for (ll j = 0; j < w; j++)
        if (s[i][j] == '.')
            chmax(bfs(i, j), ans);

    std::cout << ans << '\n';
}


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

int main()
{
    int n;
    cin >> n;
    vector<double> v(n);
    rep(i, n) {
        cin >> v.at(i);
    }

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

    double ans = v.at(0);
    for (int i = 1; i < n; i++) {
        ans += v.at(i);
        ans /= 2;
    }

    cout << fixed << setprecision(10) << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long GCD_(long long a, long long b) {
    return b ? GCD_(b, a % b) : a;
}
int arr[100005];
long long dp[100005];
int n;
long long solve(int i){
   if(dp[i]!=-1) return dp[i];
   if(i == n) return dp[i] = 0;
   if(i+1 == n) return dp[i] = solve(i+1) + abs(arr[i+1] - arr[i]);
   return dp[i] = min(solve(i+1) + abs(arr[i+1]-arr[i]),solve(i+2) + abs(arr[i] - arr[i+2]));
}
int main(){
    memset(dp,-1,sizeof(dp));
    cin>>n;
    for(int i=1;i<=n;i++) cin>>arr[i];
    cout<<solve(1);
 return 0;
}


Measured memory_bytes: 2944
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second
#define mp make_pair
 
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll INF = 1ll << 60;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

bool Prime[int(1e5 + 5)];
int Sum[int(1e5 + 5)], Q, L, R;

int main(){
  Prime[2] = true;
  for (int i = 3; i < 1e5 + 5; i++){
    Sum[i] = Sum[i - 1];
    if (i % 2 == 0) continue;

    Prime[i] = true;
    for (int j = 2; j * j <= i; j++){
      if (i % j == 0) {
        Prime[i] = false; break;
      }
    }
    
    if (Prime[i] && Prime[(i + 1) / 2]) Sum[i]++;
  }

  scanf("%d", &Q);
  for (int i = 0; i < Q; i++){
    scanf("%d%d", &L, &R);
    printf("%d\n", Sum[R] - Sum[L-1]);
  }

  return 0;
}


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

void selectionSort(int a[],char b[],int n){
    for(int i=0;i<n-1;i++){
    int min = i;
        for(int k=i+1;k < n;k++){
            if(a[min] > a[k])
                min = k;
        }
        if(min != i){
            // 文字と数字の入れ替え
            swap(a[i],a[min]);
            swap(b[i],b[min]);
        }
    }
    for(int i=0;i<n;i++){
        if(i) cout << " ";
         cout << b[i] << a[i]; 
    }
    cout << endl;
}

void bubbleSort(int a[],char b[],int n){
    for(int i=0;i<n-1;i++){
    int min = i;
        for(int k=n-1;k > 0;k--){
            if(a[k] < a[k-1]){
                swap(a[k],a[k-1]);
                swap(b[k],b[k-1]);
            }
        }
    }
    for(int i=0;i<n;i++){
        if(i) cout << " ";
         cout << b[i] << a[i]; 
    }
    cout << endl << "Stable" << endl;
}

int main(){
   
    int n;
    cin >> n;
    int s[n],b[n];
    char m[n],bm[n];
    for(int i=0;i<n;i++){
        string A;
        cin >> A;
        m[i] = A[0];
        bm[i] = A[0];
        s[i] = (int)A[1] - '0';
        b[i] = (int)A[1] - '0';
    }
    bubbleSort(b,bm,n);
    selectionSort(s,m,n);

    for(int i=0;i<n;i++){
        if(m[i] != bm[i]){
            cout << "Not stable" << endl;
            return 0;
        }
    }
    cout << "Stable" << endl;
    return 0;
}


Measured memory_bytes: 3156
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <array>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <cstdint>
#include <unordered_set>
#include <ctime>
#include <numeric>

typedef long long int llint;

int main(void){

  int n;
  std::cin >> n;
  std::vector<llint> A(n);
  std::map<int, llint> data;

  for(int i=0; i<n; i++){
    std::cin >> A[i];
    if(data.find(A[i]-i) == data.end()) data[A[i]-i] = 0;
    data[A[i]-i]++;
  }

  llint count = 0;
  for(int i=0; i<n; i++){
    llint temp = A[i]+i;
    if(data.find(-temp) == data.end()) continue;
    count += data[-temp];
  }
  std::cout << count << std::endl;

  return 0;
}


Measured memory_bytes: 16280
// #include C/C++ {
#include <bits/stdc++.h>
// }
using namespace std;
// #typedef {
typedef long long int64;
typedef pair <int, int> PII;
typedef pair <int64, int64> PLL;
// }

// #parameter{
#ifdef DEBUG_MODE

#define TYPE decltype
#define RF(filename) {freopen((filename), "r", stdin);}
#define WF(filename) {freopen((filename), "w", stdout);}
#define DF(filename) {freopen((filename), "w", stderr);}
#define eprintf printf

#else

#define TYPE __typeof
#define RF(filename) {;}
#define WF(filename) {;}
#define DF(filename) {;}
#define eprintf(...)
#define fprintf(...)

#endif

// #define {
#define SZ(a) ((int)(a).size())
#define X first
#define Y second
#define MP make_pair
#define L(x) ((x)<<1)
#define R(x) ((x)<<1 | 1)
#define max3(x, y, z) (max(max((x), (y)), (z)))
#define min3(x, y, z) (min(min((x), (y)), (z)))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(it) (it).begin(), (it).end()
#define FILL(__space, __val) memset(__space, __val, sizeof(__space))
#define MOVE(__spaceTo, __spaceFrom) memmove(__spaceTo, __spaceFrom, sizeof(__spaceTo))
#define UNIQUE(__vector) sort(ALL(__vector)), __vector.resize(unique(ALL(__vector)) - __vector.begin())
#define FOR(it, c) for( TYPE((c).begin()) it = (c).begin(); it != (c).end(); it++)
/////////////////////////////////////////////////////////////
const double PI = acos(-1.0);
const double EPS = 1e-6;

#define MAX_N 1005
#define MAX_M 55
#define MOD (int)(1e9+7)
#define INF ((1 << 30) - 1)
#define BINF ((1LL << 62) - 1LL)
#define NONE -1
#define NIL 0
// }

/////////////////////////////////////////////////////////////
int H[MAX_N];
/////////////////////////////////////////////////////////////
int main() {
	RF("input.txt");
	//  WF("output.txt");
	DF("err.txt");

	int N;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) scanf("%d", H + i);
	int res = 1;
	int block = H[0];
	for (int i = 1; i < N; i++) {
		if (H[i] >= block) {
			res++;
			block = H[i];
		}
	}
	printf("%d\n", res);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define BIT(n) (1LL << (n))
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPB(i, n) for (int i = 0; i < BIT(n); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); 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 FORA(i, n) for (auto &&i : n)
#define FORS(i, m, n) for (int i = m; i <= n; i++)
#define DEBUG(x) cerr << #x <<": "<<x<<"\n"
#define ALL(v) v.begin(), v.end()
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define epb emplace_back
#define int long long
using namespace std;
//using template <class T>vec = vector<T>;
template <class T> using vec = std::vector<T>;
template <class T = int> T in(){T x; cin>>x;return(x);}
template <class T > void print(T& x){cout<<x<<"\n";}
typedef long long ll;
const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N=in<int>();
  vec<int>a(N);
  vec<int>ans(N,-1);
  REP(i,N){
	  a[i]=in<int>();
  }
int count=0;
  REPR(i,N-1){
	  int id = i+1;
	  int MAXID= id*(N/id);
	  int sum=0;
	  for (;MAXID!=id;MAXID-=id){
		  sum+=ans[MAXID-1];
	  }
	  sum%=2;
	  ans[i]=(a[i]-sum+2)%2;
	  if (ans[i]%2==1)count++;
  }

  print(count);
  REP(i,N){
	  if (ans[i]%2==1)cout<<i+1<<" ";
  }
  cout<<"\n";

}

Measured memory_bytes: 3968
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e6 + 5;
const int mod = 1e9 + 7;
ll n, s, a[maxn], ss, val, ans;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (ll i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            a[++s] = i;
            if (i != n / i) a[++s] = n / i;
        }
        if ((n - 1) % i == 0) {
            a[++s] = i;
            if (i != (n - 1) / i) a[++s] = (n - 1) / i;
        }
    }
    sort(a + 1, a + 1 + s);
    int cnt = unique(a + 1, a + 1 + s) - a;
    for (int i = 1; i < cnt; i++) {
        if (a[i] == 1) continue;
        val = n;
        while (val % a[i] == 0) {
            val = val / a[i];
        }
        if ((val - 1) % a[i] == 0) ss++;
    }
    cout << ss << endl;
    return 0;
}


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


public class Main {
	Scanner in = new Scanner(System.in);
	int n1, n2;
	int[] array1, array2;
	
	public void run() {
		while (true) {
			n1 = in.nextInt(); n2 = in.nextInt();
			if (n1 == 0 && n2 == 0) break;
			array1 = new int[n1+1]; array2 = new int[n2+1];
			
			for (int i = 0; i < n1; i++)
				array1[i] = in.nextInt();
			for (int i = 0; i < n2; i++)
				array2[i] = in.nextInt();
			
			Arrays.sort(array1); Arrays.sort(array2);
			
			int ans = 0;
			int i = n1, j = n2;
			while (array1[i] != 0 || array2[j] != 0) {
				if (array1[i] == array2[j]) {
					ans += array1[i--]; j--;
				} else if (array1[i] < array2[j]) {
					ans += array2[j--];
				} else {
					ans += array1[i--];
				}
			}
			System.out.println(ans);
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}

}

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

bool binary_search(vector<int>& S,int st, int en, int key) {
  int bi;
  while(true) {
    bi = (st + en) / 2;
    if(S[bi] == key) {
      return true;
    }

    if(st == bi || en == bi) {
      break;
    }
    else if(S[bi] > key) {
      en = bi;
    }
    else if(S[bi] < key) {
      st = bi + 1;
    }
  }
  return false;
}

int main() {
  int n,q;
  vector<int> S,T;

  cin >> n;
  for(int i=0;i<n;i++) {
    int s;
    cin >> s;
    S.push_back(s);
  }
  cin >> q;
  for(int i=0;i<q;i++) {
    int t;
    cin >> t;
    T.push_back(t);
  }

  int C = 0;
  for(int t_itr=0;t_itr<q;t_itr++) {
    if(binary_search(S,0,n,T[t_itr])) {
      C++;
    }
  }

  cout << C << endl;
}

Measured memory_bytes: 1800
use std::collections::HashSet;
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let s: String = read();
    println!(
        "{}",
        if s.len() == s.chars().collect::<HashSet<_>>().len() {
            "yes"
        } else {
            "no"
        }
    );
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
long long i,n,k,a[100000];
int gcd(long long x,long long y){
  return y?gcd(y,x%y):x;
}
main(){
  long long x=1;
  long maxa=0;
  int ggg=0;
  cin>>n>>k;
  for(i=0;i<n;i++){
    cin>>a[i];
    x*=a[i];
    if(a[i]>maxa) maxa=a[i];
    ggg=gcd(ggg,a[i]);
  }
  if(maxa<k){
    cout<<"IMPOSSIBLE"<<endl;
    return 0;
  }
  // cout<<x<<endl;
  
  /* for(i=0;i<n;i++){
    if(k%gcd(x/a[i],a[i])==0){
      cout<<"POSSIBLE"<<endl;
      return 0;
    }
    }*/
  if(k%ggg==0){
    cout<<"POSSIBLE"<<endl;;
    return 0;
  }
  cout<<"IMPOSSIBLE"<<endl;
  return 0;

  
}


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

typedef long long ll;
typedef long double ld;
#define pi 3.14159265359;
#define inf (1 << 21);
#define mod 1000000007;

int main() {
    int N, K; cin >> N >> K;
    int ans = 1;
    for (int i = 0; i < N; i++) {
        if (ans > K) {
            ans += K;
        }
        else {
            ans *= 2;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256