akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define int         long long
#define endl        "\n"
#define pii         pair<int, int>
#define dint        long double


void solve() {
    int n, k; cin >> n >> k;
    int a[n];
    for(int i=0; i<n; i++) {
        cin >> a[i]; a[i]--;
    }
    int logk = 0;
    while((1LL << logk) <= k) logk++;
    int nxt[n][logk];
    for(int i=0; i<n; i++) nxt[i][0] = a[i];
    for(int deg=1; deg<logk; deg++) {
        for(int i=0; i<n; i++) {
            nxt[i][deg] = nxt[nxt[i][deg-1]][deg-1];
        }
    }
    int to = 0;
    for(int deg=0; deg<logk; deg++) {
        if((1LL << deg) & k) {
            to = nxt[to][deg];
        }
    }
    cout << (to + 1) << endl;
}

signed main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(12);

    int T = 1;
    // cin >> T;
    for(int i=1; i<=T; i++) {
        solve();
    }
    return 0;
}

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



int x,y,z,sum;
void adds(char a){if(a=='r'){sum+=z;}else if(a=='s'){sum+=x;}else{sum+=y;}}

int main(void){
    sum=0;
    int n,k;
    cin>>n>>k;
    cin>>x>>y>>z;
    string s;
    cin>>s;
    
    string str;
    for(int i=0;i<k;i++){
        str="";
        for(int j=0;j*k+i<n;j++){
            str+=s[i+j*k];
        }
        char prev=' ';char tmp=' ';
        int strl=str.length();
        for(int m=0;m<strl;m++){
            tmp=str[m];
            if(tmp!=prev){
                adds(tmp);
                prev=tmp;
            }else{
                prev=' ';
            }
        }
    }
    cout<<sum<<endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <string>

constexpr int nil {-1};

struct Node
{
    int id;
    int parent {-1};
    std::vector<int> children;

    int dimention() const
    {
        return children.size();
    }

    std::string childrenStr() const
    {
        using namespace std;
        string str = "[";
        for (int i = 0; i < children.size(); ++i)
        {
            str += to_string(children[i]);
            if (i + 1 != children.size())
                str += ", ";
        }
        str += "]";

        return str;
    }
};

std::istream& operator>>(std::istream& is, Node& node)
{
    using std::vector;

    int k;
    is >> node.id >> k;

    node.children = std::vector<int>(k);

    for (auto& c : node.children)
        is >> c;

    return is;
}

class Tree
{
public:

    Tree(int nodeNum)
        : nodes {std::vector<Node>(nodeNum)}
    {}

    void add(const Node& node)
    {
        nodes[node.id] = node;
    }

    void add(const Node&& node)
    {
        nodes[node.id] = std::move(node);
    }

    void calcParent()
    {
        for (const auto& n : nodes)
        {
            for (int c : n.children)
            {
                nodes[c].parent = n.id;
            }
        }
    }

    int depth(int id)
    {
        if (nodes[id].parent == nil)
            return 0;
        else
            return depth(nodes[id].parent) + 1;
    }

    std::string type(int id)
    {
        const auto& n = nodes[id];

        if (n.parent == nil)
            return "root";
        else if (n.dimention() == 0)
            return "leaf";
        else
            return "internal node";
    }
    
    void show(int id)
    {
        using namespace std;

        const auto& n = nodes[id];

        cout << "node " << n.id << ": parent = " << n.parent << ", depth = " <<
            depth(n.id) << ", " << type(n.id) << ", " << n.childrenStr() << endl;
    }

    void showAll()
    {
        for (const auto& n : nodes)
            show(n.id);
    }


private:

    std::vector<Node> nodes;
};

void solve();

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

void solve()
{
    using namespace std;

    int n;
    cin >> n;

    Tree tree {n};

    for (int i = 0; i < n; ++i)
    {
        Node node;
        cin >> node;
        tree.add(move(node));
    }

    tree.calcParent();

    tree.showAll();
}



Measured memory_bytes: 7960
import java.util.*;

public class Main{
	public static void main(String[] args){
		HashMap<Long,Long> map = new HashMap<Long,Long>();
		HashMap<Long,Long> map2 = new HashMap<Long,Long>();
		Queue<Long> que = new ArrayDeque<Long>();

		try(Scanner sc = new Scanner(System.in)){
			Long N = sc.nextLong();
			{
				Long num = 0L;
				for(Long i = 0L; i < N; i++){
					num <<= 4;
					num += i + 1;
				}	
				map.put(num, 0L);
				que.add(num);
			}
			while(true){
				Long now = que.poll();
				if(now == null){
					break;
				}
				//System.out.println(now + " " + map.get(now));
				if(map.get(now) == 3){
					continue;
				}
				for(int i = 0; i < N; i++){
					for(int j = i + 1; j < N; j++){
						Long next = now;
						for(int k = 0; k < (j - i + 1) / 2; k++){
							Long num1 = (next >> ((i + k)*4)) % 16;
							next -= (num1 << ((i + k) * 4));
							Long num2 = (next >> ((j - k)*4)) % 16;
							next -= num2 << (((j - k) * 4));
							next += num2 << (((i + k) * 4));
							next += num1 << (((j - k) * 4));
						}
						if(!map.containsKey(next)){
							map.put(next, map.get(now) + 1);
							que.add(next);
						}
					}
				}
			}

			Long ans = N - 1;

			{
				Long num = 0L;
				for(Long i = 0L; i < N; i++){
					num <<= 4;
					num += sc.nextLong();
				}	
				map2.put(num, 0L);
				que.add(num);
			}
			while(true){
				Long now = que.poll();
				//System.out.println(now);
				if(now == null){
					break;
				}
				if(map2.containsKey(now)){
					if(map.containsKey(now) ){
						ans = Math.min(ans, map.get(now) + map2.get(now));
						continue;
					}
					if(map2.get(now) == 3) {
						continue;
					}
				}
				for(int i = 0; i < N; i++){
					for(int j = i + 1; j < N; j++){
						Long next = now;
						for(int k = 0; k < (j - i + 1) / 2; k++){
							Long num1 = (next >> ((i + k)*4)) % 16;
							next -= (num1 << ((i + k) * 4));
							Long num2 = (next >> ((j - k)*4)) % 16;
							next -= num2 << (((j - k) * 4));
							next += num2 << (((i + k) * 4));
							next += num1 << (((j - k) * 4));
						}
						if(!map2.containsKey(next)){
							map2.put(next, map2.get(now) + 1);
							que.add(next);
						}
					}
				}
			}
			System.out.println(ans);
		}
	}
}

Measured memory_bytes: 71824
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

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

    // input
    int x, y, z;
    cin >> x >> y >> z;
    x -= (2*z);

    int haba = y+z;
    int num = x / haba;
    int rest = x - num * haba;
    if(rest >= y){
        num++;
    }

    p(num);

    return 0;
}

Measured memory_bytes: 256
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <ctype.h>
#include <stdint.h>
#include <string.h>
#include <wchar.h>
#include <math.h>

#define N_MAX (100)
#define P_MAX (100)
#define DP_ARRAY_SIZE (N_MAX * P_MAX / 32 + 1)

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define ABS(a) ((a) < 0 ? -(a) : (a))
#define ABSS(a, b) ((a) > (b) ? (a) - (b) : (b) - (a))

int compare_sz_desc(const void* a, const void* b) {
    return *((size_t*)a) > * ((size_t*)b) ? -1 : 1;
}

int compare_f(const void* a, const void* b) {
    return *((int64_t*)a) < *((int64_t*)b) ? -1 : 1;
}

int compare_f2(const void* a, const void* b) {
    return *((uint64_t*)a) > * ((uint64_t*)b) ? -1 : 1;
}

static size_t comb(const size_t n, const size_t r) {
    size_t result = 1;

    for (size_t i = 0; i < r; i++) {
        result *= n - i;
        result /= i + 1;
    }

    return result;
}

static uint64_t combU64(const uint64_t n, const uint64_t r) {
    uint64_t result = 1;

    for (uint64_t i = 0; i < r; i++) {
        result *= n - i;
        result /= i + 1;
    }

    return result;
}

static uint64_t gcdU64(uint64_t m, uint64_t n)
{
    uint64_t temp;

    while (m % n != 0) {
        temp = n;
        n = m % n;
        m = temp;
    }

    return n;
}

static size_t gcdZu(size_t m, size_t n) {
    size_t temp;

    while (m % n != 0) {
        temp = n;
        n = m % n;
        m = temp;
    }

    return n;
}

static size_t powSz(const size_t base, const size_t exp) {
    size_t result = 1;
    for (size_t i = 0; i < exp; i++) {
        result *= base;
    }
    return result;
}

int main(void) {
    size_t N, M;
    size_t k[10];
    size_t s[10][10];
    size_t p[10];

    scanf("%zu %zu\n", &N, &M);
    for (size_t i = 0; i < M; i++) {
        scanf("%zu ", &(k[i]));
        for (size_t j = 0; j < k[i]; j++) {
            scanf("%zu", &(s[i][j]));
            s[i][j]--;
            scanf(j < k[i] - 1 ? " " : "\n");
        }
    }
    for (size_t i = 0; i < M; i++) {
        scanf("%zu", &(p[i]));
        if (i < M - 1) {
            scanf(" ");
        }
    }

    const size_t lim = powSz(2, N);
    size_t result = 0;

    for (size_t i = 0; i < lim; i++) {
        size_t onBulbCnt = 0;

        for (size_t bulb = 0; bulb < M; bulb++) {
            size_t onCnt = 0;
            for (size_t sw = 0; sw < k[bulb]; sw++) {
                if (((i >> s[bulb][sw]) & 0x1) != 0) {
                    onCnt++;
                }
            }
            if (onCnt % 2 == p[bulb]) {
                onBulbCnt++;
            }
        }

        if (onBulbCnt == M) {
            result++;
        }
    }

    printf("%zu\n", result);

    return 0;
}


Measured memory_bytes: 128
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
using namespace std;

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

#define df(b, e) ((b) > (e))
#define fore(i, b, e) for (auto i = (b) - df(b, e); i != e - df(b, e); i += 1 - 2 * df(b, e))
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define f first
#define s second
#define pb push_back

using lli = long long;
using ld = long double;
using ii = pair<int, int>;
using vi = vector<int>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#ifdef LOCAL
const int N = 20;
#else
const int N = 1e5 + 5;
#endif

int mod = 2;

struct Modular {
  int v;
  Modular(lli x = 0) : v(x % mod) {}
  Modular operator + (const Modular &m) const { return Modular(v + m.v); }
  Modular operator - (const Modular &m) const { return Modular(v - m.v + mod); }
  Modular operator * (const Modular &m) const { return Modular(1LL * v * m.v); }
  void operator += (const Modular &m) { *this = *this + m; }
  void operator -= (const Modular &m) { *this = *this - m; }
  void operator *= (const Modular &m) { *this = *this * m; }
  friend ostream & operator << (ostream &os, const Modular &m) { return os << m.v; }
};

using mint = Modular;
vi graph[N];
mint dp[N], ans[N];
int n;

void dfs1(int u, int p = 0) {
  dp[u] = mint(1);
  for (int v : graph[u]) 
    if (v != p) {
      dfs1(v, u);
      dp[u] *= (dp[v] + 1);
    }
} 

void dfs2(int u, int p = 0) {
  vector<mint> pref, suf;
  fore (it, 0, 2) {
    pref.pb(mint(1));
    for (int v : graph[u]) 
      pref.pb(pref.back() * (dp[v] + 1));
    swap(pref, suf);
    reverse(all(graph[u]));
  }
  ans[u] = pref.back();
  reverse(all(suf));

  auto without = [&](int i) -> mint {
    return pref[i] * suf[i + 1];
  };

  debug(u, pref, suf);

  for (auto &v : graph[u]) 
    if (v != p) {
      int i = &v - &graph[u][0];
      // re-root
      debug(i, v, graph[u][i]);
      dp[u] = without(i);
      debug(dp[u]);
      dfs2(v, u);
      // undo
      dp[u] = pref.back();
    }
}

int main() {
  cin.tie(0)->sync_with_stdio(0), cout.tie(0);

  cin >> n >> mod;
  fore (i, 0, n - 1) {
    int u, v;
    cin >> u >> v;
    graph[u].pb(v);
    graph[v].pb(u);
  }

  dfs1(1, 0);
  dfs2(1, 0);

  fore (u, 1, n + 1) 
    cout << ans[u] << '\n';

  return 0;
}

Measured memory_bytes: 25552
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

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

int main()
{
  int N;
  cin>>N;
  vector<int> A(N,0);
  REP(i,N) cin>>A[i];
  int cnt=0;
  bool Even=true;
  while(Even)
  {
      for (int i = 0; i < N; ++i)
      {
          if (A[i] % 2 != 0)
          {
              Even = false;
          }
          A[i] /= 2;
      }
      ++cnt;
  }
  cout<<cnt-1<<endl;
}


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

using namespace std;


void solve() {
    int N; cin >> N;
    int n = N / 1000;
    int ans = (n+1) * 1000 - N;
    ans %= 1000;
    cout << ans << endl;
}


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

Measured memory_bytes: 3624
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
a=0
H=0
W=0
count=1
for i in range(len(A)):
    #print(A[i],H,W)
    if A[i]==a:
        count+=1
    else:
        if count>=4:
            if H<A[i-1]:
                H=A[i-1]
            if W < A[i - 1]:
                W=A[i-1]
        elif count>=2:
            if H!=0:
                W=A[i-1]
            else:
                H=A[i-1]
        a=A[i]
        count=1
        if H!=0 and W!=0:
            print(H*W)
            exit(0)
if count>=4:
    if H<A[i-1]:
        H=A[i-1]
    if W < A[i - 1]:
        W=A[i-1]
elif count>=2:
    if H!=0:
        W=A[i-1]
    else:
        H=A[i-1]
print(H*W)

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

using namespace std;

int main(){
	int n;
	cin >> n;
	int graph[125][125];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			graph[i][j] = 0;
		}
	}
	for(int i=1;i<=n;i++){
		int num;
		int k;
		int tmp;
		cin >> num >> k;
		if(k !=0){
			for(int j=0;j<k;j++){
				cin >> tmp;
				graph[num][tmp] = 1;
			}
		}
	}
	for(int i = 1; i<=n;i++){
		for(int j= 1;j<=n;j++){
			if(j != n)cout << graph[i][j] <<" ";
			if(j == n) cout << graph[i][j] <<  endl;
		}
	}
}



Measured memory_bytes: 3144
#include<iostream>
using namespace std;
int main(){
    int money[4]={10,50,100,500};
    int n;
    bool flag = true;
    while(cin >> n,n){
        int coin[4];
        for(int i=0; i<4; i++){
            cin >> coin[i];
        }
        n = coin[0] * 10 + coin[1] * 50 + coin[2] * 100 + coin[3] * 500 - n;
        int num[4];
        for(int i=3; i>=0; i--){
            num[i] = n/money[i];
            n -= num[i]*money[i];
        }
        if(flag) flag = false;
        else cout << endl;
        for(int i=0; i<4; i++){
            if(coin[i]>num[i]) cout << money[i] << ' ' << coin[i] - num[i] << endl;
        }
    }
}



Measured memory_bytes: 3072
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
	char a[100];
	cin>>a;
	for(int i=0;i<6;i++){
		if(i==0){
		cout<<"2018";
		}
		cout<<a[i+4];
	}
	cout<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define dF(i,a,b) for(int i=a;i>=(b);--i)
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define pb push_back
#define maxnkp make_pair
#define fi first
#define se second
#define eps 1e-6
using namespace std;
typedef long long ll;
const int mods = 1e9+7;
const int maxn = 2e5+10;
const int N = 1e5+10;
const int E = 1e6+10; 
int n,k;
double p[maxn];
double pre[maxn];

int main(){
	cin>>n>>k;
	F(i,1,n){
		cin>>p[i];
		p[i] = (p[i]+1)/2.0;
		pre[i]=pre[i-1]+p[i];
	}
	double sum = 0;
	F(i,1,n-k+1){
		sum = max(sum,pre[i+k-1]-pre[i-1]);
	} 
	printf("%.8lf\n",sum);
}


Measured memory_bytes: 3328
#include <iostream>

using namespace std;

int pow_int(int a, int n) {
    int r = 1;
    for (int i = 0; i < n; i++) {
        r *= a;
    }
    return r;
}

int main(void) {
    int D, N;
    cin >> D >> N;

    if (N == 100) {
        cout << 101 * pow_int(100, D) << endl; // 101, 10100, 1010000
    }
    else {
        cout << N * pow_int(100, D) << endl;
    }

    return 0;
}

Measured memory_bytes: 256
N = int(input())
rs = []
for no in range(N):
    S, P = [i for i in input().split()]
    rs.append((S, int(P), no+1))
rs = sorted(rs, key=lambda x: x[1], reverse=True)
rs = sorted(rs, key=lambda x: x[0])
for r in rs:
    print(r[2])


Measured memory_bytes: 38384
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < int, int >
#define F first
#define S second
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize ("Ofast")
using namespace std;
/// khodaya komak kon
/// ya navid navid
/// ye tec khaphan ke yadam bemone : age jayi didi soale masir hamiltoni mikhad rasasho bokon yal oilery;
/// age ye ja mikhasti to dp az ozv i k ta entekhab koni bejash ye log bezan (nominal) hamoon 2**k va o 1 ent kon

///\\\///\\\///\\\\\\\\\\\\\\\\\///\\\///\\\///

const int N=2e5,mod=1e9+7;
ll a[N];

int32_t main(){
    ll n,t;
    cin >> n >> t;
    for (int i=0;i<n;i++){
        cin >> a[i];
    }
    ll p1=0;
    ll ans=0;
    for (int i=0;i<n;i++){
        p1=max(p1,a[i]);
        ans+=a[i]+t-p1;
        p1=a[i]+t;
    }
    cout << ans;
}
















Measured memory_bytes: 1792
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <deque>
#include <queue>
using namespace std;

typedef long long ll;
int cnt[105];

int main(){
    int N;
    cin >> N;
    for(int i = 2; i <= N; i++){
        int num = i;
        for(int j = 2; j <= sqrt(i); j++){
            while(num%j == 0){
                num /= j;
                cnt[j]++;
            }
        }
        if(num != 1) cnt[num]++;
    }

    int cnt3 = 0, cnt5 = 0, cnt15 = 0, cnt25 = 0, cnt75 = 0;
    for(int i = 2; i <= N; i++){
        if(cnt[i] >= 74) cnt75++;
        if(cnt[i] >= 24) cnt25++;
        if(cnt[i] >= 14) cnt15++;
        if(cnt[i] >= 4) cnt5++;
        if(cnt[i] >= 2) cnt3++;
    }
    int ans = 0;
    ans += cnt75;
    ans += cnt25*(cnt3-1);
    ans += cnt15*(cnt5-1);
    ans += cnt5*(cnt5-1)*(cnt3-2)/2;
    cout << ans << endl;
}



Measured memory_bytes: 256
/*#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 deque<ll> dll;
typedef pair<ll, ll> P;
#define mod 1e9 + 7;
ll gcd(ll x, ll y)
{
	ll r;
	while ((r = x % y) != 0)
	{
		x = y;
		y = r;
	}
	return y;
}
ll lcm(ll x, ll y)
{
	x /= gcd(x, y);
	y /= gcd(x, y);
	return (x * y);
}
int main(){
    ll b=0,c=0,d=0,ans=0,ret=M,n,m;
	string s;
	bool x = false;
	cin >> n >> m;
	vi v(n);
	rep(i,n)
		cin >> v[i];
	
	sort(v.begin(),v.end());
	rep(j,n-m+1){
		ret = min(ret,(ll)v[j+m-1] - v[j]);
		//cout << ret << endl;
	}
	
	cout << ret << endl; 
    return 0;
}  


Measured memory_bytes: 640
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define rep1(i, n) for(ll (i) = 1; (i) <= (n); (i)++)
#define rrep(i, n) for(ll (i) = (n) - 1; (i) >= 0; (i)--)
#define rrep1(i, n) for(ll (i) = (n); (i) >= 1; (i)--)
const ll INF = 1145141919;
const ll MOD = 1000000007;
template<class T> void chmax(T &a, const T &b){if(a < b){a = b;}}
template<class T> void chmin(T &a, const T &b){if(a > b){a = b;}}

int main(){

    ll h, w;
    cin >> h >> w;
    rep(i, h){
        string s;
        cin >> s;
        cout << s << endl;
        cout << s << endl;
    }

    return 0;
}

Measured memory_bytes: 896
#include<stdio.h>
int main()
{
	int k,s;
	scanf("%d %d",&k,&s);
	int i,j,l;
    int count = 0;
	int number;
	for(i = 0;i<=k;i++)
	{
		for(j = 0;j<=k;j++)
		{
			if(s-i-j >= 0&& s-i-j<=k) count++;
		}
	}
	printf("%d",count);
	return 0;
}

Measured memory_bytes: 128
/* code by AbhiTaker  */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define M 1000000007
#define N 1000016
#define ff first.first
#define fs first.second
#define sf second.first
#define ss second.second
#define f first
#define s second
#define inf 9000000000000000000

int main()
{
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   ll l,r,i,cnt=0;
    cin>>l>>r;
   i = l;
   while(i<=r)
   {
       cnt++;
       i *=2;
   }

   cout<<cnt<<"\n";


    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define retunr return
#define pb push_back
#define mp make_pair
#define null NULL
#define sc(x) scanf("%d", &x)
#define sc64(x) scanf("%I64d", &x)
#define pr(x) printf("%d", (x))
#define sp putchar(' ')
#define ln putchar('\n')
#define pr64(x) printf("%I64d", (x))
#define rep(i,l,r) for (int i = l, lim = r;i <= lim; ++i)
#define repr(i,l,r) for (int i = r, lim = l;i >= lim; --i)
#define fi first
#define se second
#define SET(__set, val) memset(__set, val, sizeof __set)
#define prf(x) printf("%.20f", x)
typedef unsigned int uint;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define N 100010
#define M 1024
#define MOD 1000000007
void _add(int &a, int b){a = (a+b)%MOD;}
void _sub(int &a, int b){a = (a+MOD-b)%MOD;}
void _mul(int &a, int b){a = (ll)a*b%MOD;}
void _max(int &a, int b){a = max(a,b);}
void _min(int &a, int b){a = min(a,b);}
ll gcd(ll a, ll b){if(!b)return a;return gcd(b,a%b);}
ll pw(ll a, ll b){ll res(1);while(b){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
ll pwM(ll a, ll b, ll mod){ll res(1);while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}

const int infi = 2147483647;
const ll infl = 9223372036854775807ll;
const db PI = 3.14159265358979323846;

/*
struct E{
	int v, w, n;
}G[N];
int cnt, point[N];
void adde(int u, int v, int w = 0){
	G[++cnt]=(E){v,w,point[u]},point[u]=cnt;
	G[++cnt]=(E){u,w,point[v]},point[v]=cnt;
}
void Ginit(){
	cnt = 0;
	SET(point,0);
}
*/
/*
struct hh{
	int a, b;
	bool operator < (const hh &x) const{
		if(a==x.a)return b<x.b;
		return a<x.a;
	}
}a[N];
*/
int n, m, k,q;
int a[N], ab[N], abc[N];
string s;
int main(){
//	freopen("1", "r", stdin);
	cin>>s;
	n = s.length();
	s = "0" + s;
	int tmp = 1;
	rep(i,1,n){
		if(s[i] == 'A'){
			a[i] = (a[i-1] + tmp)%MOD;
			ab[i] = ab[i-1];
			abc[i] = abc[i-1];
		}else
		if(s[i] == 'B'){
			a[i] = a[i-1];
			ab[i] = (ab[i-1]+a[i-1])%MOD;
			abc[i] = abc[i-1];
		}else
		if(s[i] == 'C'){
			a[i] = a[i-1];
			ab[i] = ab[i-1];
			abc[i] = (abc[i-1]+ab[i-1])%MOD;
		}else{
			a[i] = (3ll*a[i-1]%MOD+tmp)%MOD;
			ab[i] = (3ll*ab[i-1]%MOD+a[i-1])%MOD;
			abc[i] = (3ll*abc[i-1]%MOD+ab[i-1])%MOD;
			_mul(tmp,3);
		}
	}
	pr(abc[n]),ln;
/*
	int Case;
	sc(Case);
	rep(ca, 1, Case){
	    printf("Case #%d: ", ca);
	}
*/
	return 0;
}


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

int main()
{
	string s;
	cin >>s;
	if(s[0] == 'R' && s[1] == 'R' && s[2] == 'R')
		cout <<"3\n";
	else if(s[0] == 'R' && s[1] == 'R' || 
		s[1] == 'R' && s[2] == 'R')
		cout <<"2\n";
	else if(s[0] == 'R' || s[1] == 'R' || s[2] == 'R')
		cout <<"1\n";
	else 
		cout <<"0\n";

}


Measured memory_bytes: 3600
#include <stdio.h>

int main() 
{ 
    int A; 
    int H; 
    int Res=0; 
    scanf("%d %d", &H, &A); 
    Res = (H/A); 
    if(H%A) 
    { 
        Res++; 
    } 
    printf("%d", Res); 
    return 0; 
}

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

ll res[200000];
int N,c[200000],s[200000],p[200000],t[200000];
vector<int>v[200000],k[200000];
stack<int>st[200000];

void dfs(int x,int from){
	p[x]=from;
	s[x]=1;
	if(from!=-1){
		st[c[from]].push(x);
	}
	if(!st[c[x]].empty())k[st[c[x]].top()].push_back(x);

	for(int i:v[x]){
		if(i==from)continue;
		dfs(i,x);
		s[x]+=s[i];
	}
	if(st[c[x]].empty()){
		t[c[x]]-=s[x];
	}
	if(from!=-1){
		st[c[from]].pop();
	}

}

int main(){
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>c[i];
		c[i]--;
	}
	for(int i=1;i<N;i++){
		int a,b;
		cin>>a>>b;
		a--;
		b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for(int i=0;i<N;i++){
		t[i]=N;
		res[i]=(ll)N*(N+1)/2;
	}
	dfs(0,-1);
	for(int i=0;i<N;i++){
		res[i]-=(ll)t[i]*(t[i]+1)/2;
	//	cout<<t[i]<<endl;
	}
	for(int i=1;i<N;i++){
		int a=s[i];
		for(int j:k[i]){
			a-=s[j];
		}
		res[c[p[i]]]-=(ll)a*(a+1)/2;
	}
	for(int i=0;i<N;i++){
		cout<<res[i]<<endl;
	}
}


Measured memory_bytes: 180972
import sys, re
from math import ceil, floor, sqrt, pi, factorial#, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    n = i_input()

    max_num = 0
    for i in range(1,n+1):
        for j in range(2,int(sqrt(n+1))):
            tmp = pow(i, j)
            if tmp <= n:
                max_num = max(max_num, tmp)
        
    print(max_num if max_num != 0 else 1)

if __name__ == '__main__':
    main()


Measured memory_bytes: 41564
#include<bits/stdc++.h>
using namespace std;
long long int a[100005];
long long int b[100005];
long long int c[100005];

int main()
{
    int i,j,n,m,t;
    cin>>t;
    for(i=1;i<=t;i++){
        cin>>a[i]>>b[i]>>c[i];
        a[i]=a[i]+max(b[i-1],c[i-1]);
        b[i]=b[i]+max(a[i-1],c[i-1]);
        c[i]=c[i]+max(b[i-1],a[i-1]);
    }
    cout<<max(max(a[t],b[t]),c[t])<<endl;
}


Measured memory_bytes: 2560
a,b,c,x,y = map(int, input().split())

mi = a*x+b*y
#ABピザを買う枚数で全探索（探索範囲に注意）
for i in range(0,200000+1,2):
	#ABピザが2i枚であるとき、AピザおよびBピザはそれぞれi枚
	#それぞれ必要な枚数
	num_a = max(x - i//2, 0)
	num_b = max(y - i//2, 0)
	price = num_a*a + num_b*b + i*c
	if price < mi:
		mi = price

print(mi)

Measured memory_bytes: 39792
def solve(arr):
    t1 = arr[1]/2 - arr[0];
    t2 = 2*arr[0] - arr[1]/2;
    if arr[1]%2==1 or t1<0 or t2<0:
        return "No"
    return "Yes"
        

arr = list(map(int,input().split()))

print(solve(arr))

Measured memory_bytes: 61880
# ヒント　dp[i]=(石の個数がi個の時直後の手番の人が勝てるか？)
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*(k+1)
for i in range(1,k+1):
    for j in range(n):
        if i-a[j]>=0 and dp[i-a[j]]==0:
            dp[i]=1
print("First" if dp[k] else "Second")

Measured memory_bytes: 41708
fun main(args: Array<String>) {
    val N = readLine()!!.toInt()
    val A = readLine()!!.split(" ").map(String::toDouble)

    var sum = 0.0
    for(i in 0 until A.size) {
        sum += 1.0 / A[i]
    }
    println(1.0 / sum)
}

Measured memory_bytes: 38000
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


def print_matrix(mat):
    for i in range(len(mat)):
        print(*mat[i])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    K, N = MI()
    A = LI()
    A.append(A[-1] + (K - A[-1]) + A[0])
    N = N + 1
    diff_sum = 0
    diff = -1
    target = -1

    for i in range(N-1):
        v = abs(A[i] - A[i+1])
        diff_sum += v

        if diff < v:
            diff = v
            target = i

    # print(A, diff, diff_sum, target)
    print(diff_sum - diff)

    # a = 0
    # for i in range(target+1, N-1):
    #     a += abs(A[i] - A[i+1])
    #     print('a', a, i, i + 1)

    # for i in range(0, target):
    #     a += abs(A[i] - A[i+1])
    #     print('a', a, i, i + 1)

    # b = 0
    # for i in range(target, 0, -1):
    #     b += abs(A[i] - A[i-1])
    #     print('b', i, i - 1)

    # for i in range(N-1, target+1, -1):
    #     b += abs(A[i] - A[i-1])
    #     print('b', i, i - 1)

    # print(a, b)
    # print(min(a, b))


if __name__ == '__main__':
    main()


Measured memory_bytes: 73124
#include<cstdio>
#include<algorithm>
#include<queue>

using namespace std;

typedef long long ll;

const int INF = 1000000000;

int prime[100000];
int primeNumber;

int d[1011][1011];
int xData[1030001];
int yData[1030001];
int p[1011][1011];

int dp[1000001];
bool used[1000001];
int m, n;

int main(){
  prime[0] = 2;
  primeNumber = 1;
  for (int i = 3; i <= 1000000; i++) {
    bool flag = true;
    for (int j = 0; j < primeNumber; j++) {
      if (i < prime[j] * prime[j]) break;
      if (i % prime[j] == 0) {
        flag = false;
        break;
      }
    }
    if (flag) prime[primeNumber++] = i;
  }

  int x = 505, y = 505; // 1(505, 505)
  int counter = 2; // max move : counter / 2
  int tempCounter = 1;
  int moveDirection = 0; // right 0 up 1 left 2 down 3
  for (int num = 1; num <= 1010000; num++) {
    d[x][y] = num; xData[num] = x; yData[num] = y;
    tempCounter--;
    if (moveDirection == 0) x++;
    if (moveDirection == 1) y--;
    if (moveDirection == 2) x--;
    if (moveDirection == 3) y++;
    if (tempCounter == 0) {
      counter++;
      tempCounter = counter / 2;
      moveDirection = (moveDirection + 1) % 4;
    }
  }

  for (int i = 0; i < 1011; i++)
    for (int j = 0; j < 1011; j++)
      p[i][j] = 0;

  for (int i = 0; i < primeNumber; i++)
    p[xData[prime[i]]][yData[prime[i]]] = 1;

  while (1) {
    scanf("%d%d", &m, &n);
    if (m == 0) break;
    
    for (int i = 0; i < 1000001; i++)
        dp[i] = -1;

    for (int i = 0; i < 1000001; i++) used[i] = false;

    queue<int> que;
    que.push(n);
    dp[n] = p[xData[n]][yData[n]];
    int ans[2] = {0, 0};
    if (dp[n] == 1) {
      ans[0] = 1;
      ans[1] = n;
    }
    while (!que.empty()) {
      int z = que.front(); que.pop();
      if (used[z]) continue;
      used[z] = true;
      for (int i = -1; i <= 1; i++) {
        int x = xData[z] + i, y = yData[z] + 1;
        int s = d[x][y];
        if (s > m) continue;
        if (dp[s] >= dp[z] + p[x][y]) continue;
        dp[s] = dp[z] + p[x][y];
        que.push(s);
        if (ans[0] < dp[s]) {
          ans[0] = dp[s];
          if (p[x][y] == 1) ans[1] = s;
        }
        else if (ans[0] == dp[s] && ans[1] < s && p[x][y] == 1) ans[1] = s;
      }
    }
    if (ans[0] == 0) ans[1] = 0;
    printf("%d %d\n", ans[0], ans[1]);
  }
}


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

int main() {
  int N;
  cin>>N;
  vector<int> Ais(N);
  for(int i=0;i<N;i++){cin>>Ais.at(i);}
  int gcd=Ais.at(0);
  for(int i=1;i<N;i++){gcd=__gcd(gcd,Ais.at(i));}
  cout<<gcd<<endl;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		sc.close();

		int cnt = 0;
		if (a == b) cnt++;
		if (a == c) cnt++;
		if (b == c) cnt++;
		if (cnt == 1) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}


Measured memory_bytes: 23764
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
static const ll maxLL = (ll)1 << 62;

int main(){
    int n,m,ans=0;
    cin>>n>>m;
    vpint a(m);
    rep(i,0,m){
        int x,y;
        cin>>x>>y;
        a[i]=pint(y,x);
    }
    sort(a.begin(),a.end());
    int minV=-1;
    rep(i,0,m){
        int en=a[i].fi,st=a[i].se;
        if(minV<=st)minV=en,ans++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1152
#include <stdio.h>
#include <string.h>

int main(){
  char str1[51];
  char str2[51];
  char str[102];
  int k = 0;
  int j = 0;

  scanf("%s", str1);
  scanf("%s", str2);

  int y = strlen(str1);
  int x = strlen(str2);

  if(y == x){

    for(int i = 0; i < y; ++i){
      str[k] = str1[i];
      k+=2;
    }

    k = 1;
    for(int i = 0; i < y; ++i){
      str[k] = str2[i];
      k+=2;
    }
    str[k-1] = '\0';
    printf("%s", str);
  }

  else if(y < x){

    for(int i = 0; i < y; ++i){
      str[k] = str1[i];
      k+=2;
    }

    k = 1;
    for(int i = 0; i < y; ++i){
      str[k] = str2[i];
      k+=2;
      ++j;
    }
    str[k-1] = '\0';
    printf("%s", str);

    for(int l = j; l < x; ++l)
      printf("%c", str2[l]);
    printf("\n");
  }

  else{
    for(int i = 0; i < y; ++i){
      str[k] = str1[i];
      k+=2;
      ++j;
    }

    k = 1;
    for(int i = 0; i < y; ++i){
      str[k] = str2[i];
      k+=2;
    }
    str[k-1] = '\0';
    printf("%s", str);
    for(int l = j; l < y; ++l)
      printf("%c", str1[l]);
    printf("\n");
  }


  return 0;
}


Measured memory_bytes: 128
import java.io.InputStreamReader;
import java.util.Scanner;

class Main {
	public static void main(String[] args) throws Exception {

		Scanner scanner = new Scanner(System.in);


		while (true) {
			int count = 0;
			int n = scanner.nextInt();
			int x = scanner.nextInt();
			if (n == 0 && x == 0) {
				break;
			} for(int i = 1; i <= (n - 2); i++){
				for(int j = i + 1; j <= (n - 1); j++){
					for(int k = j + 1; k <= n; k++){
						if((i + j + k) == x){
							count++;
						}
					}
				}
			}
			System.out.println(count);
		}
	}
}

Measured memory_bytes: 26556
n, x = gets.split(' ').map{|i| i.to_i}
a = gets.split(' ').map{|i| i.to_i}.sort

count = 0
if a.inject(&:+) == x
  count = n
elsif a.inject(&:+) < x
  count = n-1
else
  a.each do |k|
    x -= k
    if x >= 0
      count += 1
    else
      break
    end
  end
end

puts count

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
//ifstream cin("lineup.in");
//ofstream cout("lineup.out");
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
int main(){
  IOS;
    int n;
    cin>>n;
    char a[2*n];
    string s,t;
    cin>>s>>t;
    for(int i=0;i<n;i++){
	a[i*2]=s[i];
	a[i*2+1]=t[i];
    }
    for(int i=0;i<2*n;i++){
	cout<<a[i];
    }
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

class Main {

    public static void main(String[] args) throws Exception {

        try {

            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

            String[] inputString = br.readLine().split(" ");
            int cookieCount = Integer.parseInt(inputString[0]);
            int numberOfPeople = Integer.parseInt(inputString[1]);
            Map<Integer, Integer> cookieCountPerOnePerson = new HashMap<>();

            for (int i = 1; i <= numberOfPeople; i++) {
                cookieCountPerOnePerson.put(i, 0);
            }

            while (true) {
                for (int i = 1; i <= numberOfPeople; i++) {
                    if (cookieCount > 0) {
                        cookieCountPerOnePerson.put(i, cookieCountPerOnePerson.get(i).intValue() + 1);
                        cookieCount -= 1;
                    }
                }

                if (cookieCount <= 0) {
                    break;
                }
            }

            int result = cookieCountPerOnePerson.get(1).intValue() - cookieCountPerOnePerson.get(numberOfPeople).intValue();
            System.out.println(result);

        } catch (IOException | NumberFormatException e) {
            e.printStackTrace();
            System.exit(0);
        } catch (final Exception e) {
            e.printStackTrace();
            System.exit(0);
        }
    }
}

Measured memory_bytes: 22996
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define il inline
int b[26];
int main(){
	int n;cin>>n;
	mst(b,0x3f);
	string a[n];
	for(int i=0;i<n;i++)
		cin>>a[i];
	for(int i=0;i<n;i++){
		int tmp[26]={};
		for(int j=0;j<a[i].size();j++){
			tmp[a[i][j]-'a']++;
		}
		for(int j=0;j<26;j++)
			if(b[j]>tmp[j]) b[j]=tmp[j];
	}
	string ans;
	for(int i=0;i<26;i++)
	{
		for(int j=0;j<b[i];j++) ans.push_back(i+'a');
	}
	sort(ans.begin(),ans.end());cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3632
/*
* Welcome to my code!
*---------------------------------------------*
* author : lynmisakura(twitter : @andoreiji11)
*/

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <cassert>

using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define repn for(int i = 0;i < n;i++)
#define ain(a) for(auto& i : a)cin >> i;
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x.size()) 
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define cont continue

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using pi = pair<int,int>;
using vpi = vector<pi>;
using pl = pair<ll,ll>;
using vpl = vector<pl>;

template<class T> bool chmin(T& a,T b){if(a > b){a = b;return true;}else return false;}
template<class T> bool chmax(T& a,T b){if(a < b){a = b;return true;}else return false;}
template<class T> void print(std::vector<T> a){ int sz = a.size();
for(int i=0;i<a.size();i++)cout << a[i] << (i < sz-1 ? ' ' : '\n'); }
void ioboost(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}
///////////////////////////////////////////////////////////
int main(int argc, char const *argv[])
{
	ioboost();

	int n;cin >> n;
	map<ll,ll> M[4];

	vector<ll> a(n);
	rep(i,n)cin >> a[i];

	rep(i,n){
		M[0][i - a[i]]++;
		M[1][-i - a[i]]++;
	}
	ll ans = 0;
	rep(i,n){
		ans += M[0][a[i] + i];
		ans += M[1][a[i] - i];
	}
	cout << ans/2 << '\n';
	return 0;
}

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

const int P = 1000000007;
int n, ans, cnt[26];
char s[100010];

int main() {
    scanf("%d %s", &n, s + 1);
    for (int i = 1; i <= n; i++) {
        int tmp = 1;
        for (int j = 0; j < 26; j++) {
            if (s[i] - 'a' == j) continue;
            tmp = 1LL * tmp * (cnt[j] + 1) % P;
        }
        cnt[s[i] - 'a']++, (ans += tmp) %= P;
    }
    printf("%d\n", ans);
    return 0;
}

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

int main ()
{
	int a,b,c,d;   cin>>a>>b>>c>>d;
	
	if(abs(a-c)<=d||(abs(a-b)<=d && abs(b-c)<=d)){
		cout<<"Yes"<<endl;
	}
	
	else 
	cout<<"No"<<endl;


}



Measured memory_bytes: 3616
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
typedef long long int ll;
using namespace std;
#define INF 1234567890
#define LIMIT 1

int main() {
	int N;
	cin >> N;
	vector<string> vc(N);
	cout << 0 << endl;
	cin >> vc[0];
	int left = 0, right = N;
	int mid = 0;
	while (vc[mid] != "Vacant")
	{
		mid = (left + right) / 2;
		cout << mid << endl;
		cin >> vc[mid];
		if (((mid - left) & 1 ) ^ (vc[left] == vc[mid])) 
			left = mid;
		else 
			right = mid;
	}



	return 0;
}



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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a, b, c, k;
  cin >> a >> b >> c >> k;
  for(int x = 0; x <= k; x++) {
    for(int y = 0; y <= k; y++) {
      if(x + y <= k) {
        int bb = b*pow(2, x);
        int cc = c*pow(2, y);
        if(bb>a && cc>bb) {
          cout << "Yes\n";
          return 0;
        }
      }
    }
  }
  cout << "No\n";
  return 0;
}


Measured memory_bytes: 4120
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <climits>
#include <set>
#include <map>
#include <iomanip>
#include <cassert>
#include <functional>
#include <cstring>

using namespace std;

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;
}

typedef pair<int, int> P;
#define mp make_pair
#define FOR(i, a, b) for(int (i)=a;(i)<(b);++(i))
#define rep(i, n)  FOR(i,0,n)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort((v).begin(), (v).end());					//小さい順
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());		//大きい順
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define all(c) (c).begin(),(c).end()
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vs vector<string>
#define vc vector<char>
#define vvc vector<vector<char>>
#define Print(p) cout<<(p)<<endl
#define F first
#define S second
#define pb push_back
#define mod 1000000007LL
#define INF 12345678901234567

const int maxn = 1e5 + 10;

ll dp[1005] = { -INF };
vector<pair<ll,ll>> g[5000];
bool mugen = false;

void dfs(ll to, ll from, ll cost,vb check)
{
	if (check[to])
	{
		mugen = true;
	}
	else {
		dp[to] = max(dp[to],cost);
		//cout << to << " " << dp[to] << endl;
		check[to] = true;
		for (auto i : g[to])
		{
			dfs(i.first, to, cost + i.second, check);
		}
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	// your code is here

	string a, b, c; cin >> a >> b >> c;

	if (a[a.length() - 1] == b[0] && b[b.length() - 1] == c[0]) YES;
	else NO;


	return 0;
	
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

int main() {
    ll x, k, d;
    cin >> x >> k >> d;

    x = abs(x);
    ll t = min(k, x / d);
    x -= t * d;
    k -= t;
    k %= 2;
    if (k == 1) x -= d;

    cout << abs(x) << endl;

    return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int iINF = 1001001001;
const long long llINF = 1LL << 60;
int main()
{
	int n; cin >> n;
	vector<int> ans(10001);
	for (int x = 1; x <= 100; ++x) {
		for (int y = 1; y <= 100; ++y) {
			for (int z = 1; z <= 100; ++z) {
				int a = x*x + y*y + z*z + x*y + y*z + z*x;
				if (10000 < a) continue;
				ans[a]++;
			}
		}
	}
	rep(i, n) {
		cout << ans[i + 1] << endl;
	}


	return 0;
}

Measured memory_bytes: 3588
from itertools import product
N = int(input())
d = len(str(N))
ans = []
for i in range(3, d+1):
    cs = product([3,5,7], repeat=i)
    for c in cs:
        if set(c) == {3, 5, 7}:
            if i < d or (i == d and int(''.join(map(str, c))) <= N):
                ans.append(c)
print(len(ans))


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

#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
#define repi(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define mt make_tuple
#define mp make_pair
template<class T1, class T2> bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); }
template<class T1, class T2> bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using P = pair<ll, ll>;
using ld = long double;  using vld = vector<ld>; 

int main(void) {
	
	ll x,a,b; cin >>x>>a>>b;
	cout <<x-a-(x-a)/b*b <<endl;
	
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define sz(x) (int)x.size();
#define all(x) (x).begin(), (x).end()
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i, n) for(int i =0 ; i < n; ++i)
#define Rep(i,a,b) for(int i=a;i<=b;i++)
#define pii pair < int, int >
typedef vector<int> vi;
typedef  long long ll;
const int inf = int(1e9);
const int mod =1e9+7;
const int N = (int)2e5 + 5;

void solve(){
	int n,m;
	cin>>n>>m;
	int a[n];
	double sum=0;
	rep(i,n)cin>>a[i],sum+=a[i]*1.0;
	double z=(double)sum*1.0/(4.0*m);
	int cnt=0;
	rep(i,n){
		if(a[i]*1.0>=z*1.0)cnt++;
	}
	cout<<(cnt>=m?"Yes":"No");


}
int main(){
	Red;
	int t=1;
	//cin>>t;
	while(t--)
	solve();
	return 0;
}

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

int main(){
  double A, B;
  cin >> A >> B;
  for(int i= 1; i <= 1009; i++){
    double x = i * 0.08;
    double y = i * 0.1;
    if( (int)x == A && (int)y == B ){
      cout << i << endl;
      return 0;
    }
  }
  cout << -1 << endl;
}

Measured memory_bytes: 256