akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cmath>
using namespace std;
int n;
int main(){
    cin >> n;
    int digit=0;
    int tmp = n;
    for(int i=0;i<n;i++){
        tmp = tmp/10;
        digit ++;
        if(tmp <10){
            break;
        } 
    }
    if(n<10){
        digit = 0;
    }
    int surp =n-pow(10,digit); 
    int ans = 0;
    for(int i=0;i<digit;i=i+2){
        ans += pow(10,i+1) - pow(10,i);
        //cout << ans << endl;
    }
    if(digit%2 == 0){
        ans += surp+1;
    }
    cout << ans << endl;
    return 0;
}

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

bool compare(pair<int,int> a,pair<int,int> b){
  return a.first<b.first;
}
int main(){
  int N;
  long long K;
  pair<int,int> arr[100000];
  cin>>N>>K;
  for(int i=0;i<N;i++){
    int a,b;
    cin>>a>>b;
    arr[i].first=a;
    arr[i].second=b;
  }
  sort(arr,arr+N,compare);
  for(int i=0;i<N;i++){
    if(K<=arr[i].second) {
      printf("%d",arr[i].first);
      break;
    }
    else K-=arr[i].second;
  }
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const long long INF = 1LL << 60;
int ctoi(char c) {return c-'0';}/*char to int*/
int gcd(ll a,ll b){return b?gcd(b,a%b):a;}/*MAX*/
int lcm(ll a,ll b){return a*b/gcd(a,b);}/*MIN*/
bool primecheck(ll n){/*sosuu*/if(n < 2) return false;else{for(int i = 2; i * i <= n; i++){if(n % i == 0) return false;}return true;}}
string  reverserange(string s,ll a,ll b){reverse(s.begin()+a-1,s.begin()+b); return s;}
int  main(){
int n,q;
cin >> n >> q;
string s;
cin >> s;
vector<int>a(n+1,0);
for(int i=1;i<n;i++){
    int z=0;
    if(s.at(i-1)=='A'&&s.at(i)=='C')z++;
    a.at(i+1)=a.at(i)+z;
}
for(int i=0;i<q;i++){
    int l,r;
    cin >> l >> r;
    ll ans = a.at(r)-a.at(l);
    cout << ans << endl;
}
}



Measured memory_bytes: 1408
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()

A = LIST()
A_acc = list(accumulate([0]+A))
n = max(A).bit_length()

ans = 0
r = 0
tmp = 0

for l in range(N):
	while r < N and tmp^A[r] == A_acc[r+1] - A_acc[l]:
		tmp ^= A[r]
		r += 1
	ans += r-l
	tmp ^= A[l]

print(ans)

Measured memory_bytes: 33564
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
#define RF(x) freopen(x,"r",stdin)
#define WF(x) freopen(x,"w",stdout)
typedef long long LL;
using namespace std;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
const LL M = 1e9+7;
const int SIZE = 1e6+5;
const LL INF = 1LL<<60;
const double eps = 1e-4;
const double PI=3.1415926535897932;

LL x[100009];
LL ans[100009];
vector<int> d;
int n;

vector<int> mult(vector<int> a,vector<int> b){
	vector<int> ans;
	REP(i,n-1){
		ans.PB(b[a[i]]);
	}
	return ans;
}

vector<int> qmult(LL xx){
	if(xx==0){
		vector<int> ans;
		REP(i,n-1)ans.PB(i);
		return ans;
	}
	if(xx==1)return d;
	vector<int> h=qmult(xx/2);
	h=mult(h,h);
	if(xx%2)h=mult(h,d);
	return h; 
}

int main(){
	RI(n);
	REP(i,n)scanf("%lld",&x[i]);
	DRI(m);LL k;scanf("%lld",&k);
	REP(i,n-1)d.PB(i);
	REP(i,m){
		DRI(c);
		swap(d[c-1],d[c-2]);
	}
	d=qmult(k);
	ans[0]=x[0];
	REPP(i,1,n-1){
		ans[i]=ans[i-1]+x[d[i-1]+1]-x[d[i-1]];
	}
	ans[n-1]=x[n-1];
	REP(i,n)printf("%lld\n",ans[i]);
}


Measured memory_bytes: 4928
#include<vector>
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    int n; cin >> n;
    int p[200002];
    for(int i = 0; i < n; i++){
        cin >> p[i];
    }
    int f[200002] = {};
    int ans = 1;
    for(int i = 0; i < n; i++){
        f[ p[i] ] = 1;
        if(f[ p[i]-1 ] > 0) {
            f[p[i]] = f[p[i]-1] +1;
            if(ans < f[p[i]]) ans = f[p[i]];
        }
    }
    cout << n-ans;
    return 0;
}




Measured memory_bytes: 1792
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <math.h>
#include <sstream>
#include <numeric>
#include <string>
#include <cassert>
#include <bitset>

using namespace std;
typedef long long ll;

////////////////////////////////////////////////////////////
// Source
// https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a

// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
  long long res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

// a^{-1} mod を計算する
long long modinv(long long a, long long mod) {
  return modpow(a, mod - 2, mod);
}
////////////////////////////////////////////////////////////



const ll kMod = 1000000007;

ll Comb(ll n, ll a) {
  ll x = 1;
  for (int i = 0; i < a; ++i) {
    x = x * (n - i) % kMod;
  }
  for (int i = a; i >= 1; --i) {
    x = x * modinv(i, kMod) % kMod;
  }
  return x;
}

int main() {
  ll N, A, B;
  cin >> N >> A >> B;
  ll P = modpow(2, N, kMod);
  ll Q = Comb(N, A);
  ll R = Comb(N, B);

  // ans = P - 1 - Q - R
  ll ans = P;
  ans = (ans - 1 + kMod) % kMod;
  ans = (ans - Q + kMod) % kMod;
  ans = (ans - R + kMod) % kMod;
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
//---------------------------
using namespace std;
//---------------------------
#define REP(i,n) for(int i = 0; i < (n); i++)
#define P(x) cout << (x) << "\n"

#define MOD 1000000007 // 1e9+7
#define PI 3.1415926525
#define ll long long int // 10^18
#define INF 1000000001 // 1e9+1

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

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

  // ifstream in("input.txt");
  // cin.rdbuf(in.rdbuf());

  int n;cin>>n;
  vector<int> coin9,coin6;
  REP(i,7){
    coin9.push_back(pow(9,i));
  }
  REP(i,8){
    coin6.push_back(pow(6,i));
  }
  reverse(coin6.begin(), coin6.end());
  reverse(coin9.begin(), coin9.end());
  int cntt=INF;
  for(int i=0;i<=n;i++){
    int cnt=0;
    int tmp=i;
    int ntmp=n-i;
    //i coin6
    int j=0,k=0;
    while(tmp>0){
      int minus6=tmp/coin6[j];
      cnt+=minus6;
      tmp=tmp-minus6*coin6[j];
      j++;
    }
    //n-i coin9
    while(ntmp>0){
      int minus9=ntmp/coin9[k];
      cnt+=minus9;
      ntmp=ntmp-minus9*coin9[k];
      k++;
    }
    cntt=min(cntt, cnt);
  }
  P(cntt);
  return 0;
}


Measured memory_bytes: 256
sx,sy,tx,ty=map(int,input().split())
x=tx-sx
y=ty-sy
ans=""
for k in range(y):
    ans+="U"
for k in range(x+1):
    ans+="R"
for k in range(y+1):
    ans+="D"
for k in range(x+1):
    ans+="L"
ans+="U"
ans+="L"
for k in range(y+1):
    ans+="U"
for k in range(x+1):
    ans+="R"
for k in range(y+1):
    ans+="D"
for k in range(x):
    ans+="L"
print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<string>
 
using namespace std;
 
int main() {
	int N,M;
	int s,c;
	int ans[3];
	bool flag = false;
	cin >> N >> M;
	for(int i=0;i<3;i++)ans[i] = -1;
	for(int i=0;i<M;i++){
		cin >> s >> c;
		if(ans[s-1]==-1 || ans[s-1]==c){
			ans[s-1]=c;
		}else{
			flag = true;
		}
	}
	if(flag || (ans[0]==0 && N > 1)){
		cout << "-1" << endl;
	}else{
		if(ans[0]==-1){
			if(N == 1){
				cout << "0" << endl;
				return 0;
			}
			ans[0]=1;
		}
		for(int i=1;i<N;i++){
			if(ans[i]==-1){
				ans[i]=0;
			}
			ans[0]=ans[0]*10+ans[i];
		}
		cout << ans[0] << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#D
n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
nxt = 1
loop = []
tset = set()
final = -1
while 1:
    loop.append(nxt)
    tset.add(nxt)
    nxt = a[nxt-1]
    if nxt in tset:
        final = nxt #重複した町
        break
m = -1
for i in range(len(loop)):
    if loop[i]==final:
        m = i
        break
l = len(loop)
if k < m:
    print(loop[k])
else:
    print(loop[(k-m)%(l-m)+m])
# print(loop[(k+1)%l])

Measured memory_bytes: 32380
#include <iostream>
#include <string>
using namespace std;
int main(void)
{
    int A, B, C;
    cin >> A >> B >> C;
    int K;
    cin >> K;
    int maxima = max(A, B);
    maxima = max(maxima, C);
    int sum = A + B + C;
    sum = sum - maxima;
    for (int i = 0; i < K; i++)
        maxima *= 2;
    sum = sum + maxima;
    cout
        << sum;
    return 0;
}

Measured memory_bytes: 256
N,K = map(int,input().split())
bucket = [0] * (10**5 + 1)
for i in range(N):
	a,b = map(int,input().split())
	bucket[a] += b
count = 0
ans = -1
for u in bucket:
	count += u
	ans += 1
	if count < K:
		continue
	else:
		print(ans)
		break
	

Measured memory_bytes: 5748
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
X = [0] * 3001
pre = 0
ans = 0
P = 998244353
for i, a in enumerate(A):
    for j in range(S, a, -1):
        X[j] = (X[j] + X[j-a]) % P
    X[a] = (X[a] + i + 1) % P
    ans = (ans + (X[S] - pre) * (N - i)) % P
    pre = X[S]
print(ans)

Measured memory_bytes: 42348
import java.util.*;
import java.io.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import static java.lang.Math.*;
//dp[i][j] := dp[s[0]...s[i-1]?????§][t[0]....t[j-1]?????§]???LCS
//(1<=i<=ls, 1<=j<=lt)
 
public class Main {
  public static void main(String[] args) {
    int n = 1000;
    int i, j, k;
    int dp[][] = new int[n+1][n+1];
    String s, t;
    Scanner sc = new Scanner(System.in);
    int q = Integer.parseInt(sc.next());
    for (k=0; k<q; k++) {
      s = sc.next();
      t = sc.next();

      for (i=0; i<=n; i++)
        Arrays.fill(dp[i], 0);
      for (i=1; i<=s.length(); i++)
        for (j=1; j<=t.length(); j++) {
          if (s.charAt(i-1)==t.charAt(j-1)) 
            dp[i][j] = dp[i-1][j-1] + 1;
          else
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
      System.out.println(dp[s.length()][t.length()]);  
    }
  }
}

Measured memory_bytes: 26852
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		int n = s.length();
		if(n < 5 && n >= 10) {
			System.out.println("NO");
			return;
		}
		for(int i = 0 ; i < n ; i++) {
			if(s.charAt(i) != 'A' && s.charAt(i) != 'K' && s.charAt(i) != 'H' && s.charAt(i) != 'B'&& s.charAt(i) != 'R' && s.charAt(i) != 'I') {
				System.out.println("NO");
				return;
			}
		}
		// チェック様
		int[] a = new int[5];
		for(int i = 0 ; i < n ; i++) {
			if(s.charAt(i) == 'K') {
				a[0]++;
			} else if(s.charAt(i) == 'I') {
				a[1]++;
			} else if(s.charAt(i) == 'H') {
				a[2]++;
			} else if(s.charAt(i) == 'B') {
				a[3]++;
			} else if(s.charAt(i) == 'R') {
				a[4]++;
			}
		}
		for(int i = 0 ; i < 5 ; i++) {
			if(a[i] >= 2) {
				System.out.println("NO");
				return;
			}
		}
		for(int i = 0 ; i < n ; i++) {
			for(int j = i + 1 ; j < n ; j++) {
				for(int k = j + 1 ; k < n ; k++) {
					for(int l = k + 1 ; l < n ; l++) {
						for(int x = l + 1 ; x < n ; x++) {
							if(s.charAt(i) == 'A' && s.charAt(j) == 'A' && j == i + 1 || s.charAt(j) == 'A' && s.charAt(k) == 'A' && k == j + 1|| s.charAt(k) == 'A' && s.charAt(l) == 'A' && l == k + 1 || s.charAt(l) == 'A' && s.charAt(x) == 'A' && x == l + 1) {
								System.out.println("NO");
								return;
							}
							if((s.charAt(i) == 'K' && s.charAt(j) == 'A' && j == i + 1) || (s.charAt(i) == 'I' && s.charAt(j) == 'A' && j == i + 1)) {
								System.out.println("NO");
								return;
							}
						}
					}
				}
			}
		}
		for(int i = 0 ; i < n ; i++) {
			for(int j = i + 1 ; j < n ; j++) {
				for(int k = j + 1 ; k < n ; k++) {
					for(int l = k + 1 ; l < n ; l++) {
						for(int x = l + 1 ; x < n ; x++) {
							if(s.charAt(i) == 'A' || s.charAt(j) == 'A' || s.charAt(k) == 'A' || s.charAt(l) == 'A' || s.charAt(x) == 'A') {
								continue;
							}
							if(s.charAt(i) == 'K' && s.charAt(j) == 'I' && s.charAt(k) == 'H' && s.charAt(l) == 'B' && s.charAt(x) == 'R') {
								System.out.println("YES");
								return;
							}
						}
					}
				}
			}
		}
		System.out.println("NO");
	}
}


Measured memory_bytes: 23636
#include <bits/stdc++.h>
const long long MOD = 1000000007;
const int INF = INT_MAX / 2;
const long double PI = 3.1415926;
#define FOR(i, r, n) for(int i=(ll)(r); i<(ll)(n); i++) 
#define REP(i, n) FOR(i, (0), n)
#define ALL(r) r.begin(), r.end()
#define ll long long int
#define vci vector<ll>
#define vcs vector<string>
#define vcp vector<pair<ll, ll>>
#define vct vector<tuple<ll, ll, ll>>
using namespace std;
//vector<vector<ll>> vv(n, vector<ll>(n));

typedef int Weight;
struct Edge
{
	int from, to; Weight cost;
	bool operator < (const Edge& e) const { return cost < e.cost; }
	bool operator > (const Edge& e) const { return cost > e.cost; }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
void add_edge(Graph &g, int from, int to, Weight cost)
{
	g[from].push_back(Edge{ from, to, cost });
}

int main()
{
	ll a, b, c;
	cin >> a >> b >> c;
	if (abs(a - b) > abs(a - c)) cout << "B" << endl;
	else cout << "A" << endl;
}


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

typedef long long ll;

int main(){
    string S;
    cin >> S;
    ll K;
    cin >> K;
    
    ll n=0;
    for(ll i=0; i<S.length(); i++){
        if(S[i]=='1'){
            n++;
        }
        else {
            if(K<=n){
                cout << 1 << endl;
            }
            else {
                cout << S[i] << endl;
            }
            return 0;
        }
    }
    
    cout << 1 << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;

#define MOD 1000000007

ll dp[110][100100];

int main() {
	ll n,W;
  cin>>n>>W;
  vector<pair<ll,ll> > v;
  rep(i,0,n){
    ll a,b;
    cin>>a>>b;
    v.pb(mp(a,b));
  }
  clr(dp,-1);
  dp[0][0] = 0;
  rep(i,0,n){
    rep(j,0,100100){
      if(dp[i][j]!=-1){
        dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
        if(j+v[i].fi<100100){
          dp[i+1][j+v[i].fi] = max(dp[i+1][j+v[i].fi],dp[i][j]+v[i].se);
        }
      }
    }
  }
  ll mx = 0;
  rep(i,0,W+1){
    mx = max(mx,dp[n][i]);
  }
  cout << mx << endl;
	return 0;
}

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

int main() {
  int H, W;
  cin >> H >> W;
  string S[50];
  for (int i = 0; i < H; i++) cin >> S[i];

  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      int n = 0;

      for (int k = -1; k <= 1; k++) {
        for (int l = -1; l <= 1; l++) {
          if (i + k < 0 || i + k >= H || j + l < 0 || j + l >= W) continue;
          if (S[i + k][j + l] == '#') n++;
        }
      }

      if (S[i][j] == '#') cout << "#";
      else cout << n;
    }

    cout << endl;
  }

  return 0;
}

Measured memory_bytes: 256
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N = int(sys.stdin.buffer.readline())
S = sys.stdin.buffer.readline().decode().rstrip()

dp = [set() for _ in range(3)]
for i, c in enumerate(S):
    for s in dp[1]:
        dp[2].add(s + c)
    for s in dp[0]:
        dp[1].add(s + c)
    dp[0].add(c)
print(len(dp[2]))


Measured memory_bytes: 42092
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    int n;
    cin >> n;
    int cnt[5] = {};
    rep(i, 0, n) {
        string s;
        cin >> s;
        if (s[0] == 'M') cnt[0]++;
        if (s[0] == 'A') cnt[1]++;
        if (s[0] == 'R') cnt[2]++;
        if (s[0] == 'C') cnt[3]++;
        if (s[0] == 'H') cnt[4]++;
    }
    ll ans = 0;
    rep(i, 0, 3) {
        rep(j, i + 1, 4) {
            rep(k, j + 1, 5) {
                ans += (ll)cnt[i] * cnt[j] * cnt[k];
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
// g++ -std=c++17 -D LOCAL A.cpp
// Date: 14:02:01 31 05 2020
// Author: bonelord
#include <bits/stdc++.h>
using namespace std;

void solve(){
	int a,b;
	cin>>a>>b;
	cout<<a*b<<"\n";
}

main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.setf(ios::fixed);
#ifdef LOCAL
	freopen("in", "r", stdin);
	freopen("err", "w", stderr);
#endif
//	int t; cin>>t; while (t--)
	solve();
}


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

// long long gcd(long long a, long long b) { return b != 0 ? gcd(b, a % b) : a;
// }

// int binary_search(int key) {
//     int ng = -1;
//     int ok = (int)a.size();
//     while(abs(ok - ng) > 1) {
//         int mid = (ok + ng) / 2;
//         if(isOK(mid, key))
//             ok = mid;
//         else
//             ng = mid;
//     }
//     return ok;
// }

// cout << fixed << setprecision(10);
// vector<vector<int>> vec(H, vector<int>(W))    // int H*W
// int MOD = 1000000007;

int main() {
    long long a,b,c;
    cin >> a >> b >> c;
    string ans = "No";
    if (a + b + 2*sqrtl(a*b) < c) ans ="Yes";

    cout << ans << endl;

}

Measured memory_bytes: 888
import math


def main():
    N, P = map(int, input().split())
    rt = math.floor(math.sqrt(P))
    cnt = {}
    for i in range(2, rt+1):
        while P % i == 0:
            if i not in cnt:
                cnt[i] = 0
            cnt[i] += 1
            P //= i
    if P != 1:
        cnt[P] = 1
    ans = 1
    for c in cnt:
        ans *= c**(cnt[c]//N)
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 38512
#include<stdio.h>
#include<iostream>
#include<vector>
#include<math.h>
#include<queue>
#include<map>
#include<algorithm>
#include<string.h>
#include<functional>
#include<limits.h>
#include<stdlib.h>
#include<string>
using namespace std;

#define intmax INT_MAX
#define lmax LONG_MAX
#define uintmax UINT_MAX
#define ulmax ULONG_MAX
#define llmax LLONG_MAX
#define ll long long
#define rep(i,a,N) for((i)=(a);(i)<(N);(i)++)
#define rrp(i,N,a) for((i)=(N)-1;(i)>=(a);(i)--)
#define llfor ll i,j,k
#define sc(a) cin>>a
#define pr(a) cout<<a<<endl
#define pY puts("YES")
#define pN puts("NO")
#define py puts("Yes")
#define pn puts("No")
#define pnn printf("\n")
#define sort(a) sort(a.begin(),a.end())
#define push(a,b) (a).push_back(b)
#define llvec vector<vector<ll>>
#define charvec vector<vector<char>>
#define sizeoof(a,b) (a,vector<ll>(b))
#define llpvec vector<pair<ll,ll>>
/*最大公約数*/ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*最小公倍数*/ll lcm(ll x,ll y){return x/gcd(x,y)*y;}
/*n乗*/ll llpow(ll x,ll n){ll i,ans=1;rep(i,0,n)ans*=x;return ans;}
/*階乗*/ll fact(ll x){ll i,ans=1;rep(i,0,x)ans*=(x-i);return ans;}
/*nCr*/ll ncr(ll n,ll r){return fact(n)/fact(r)/fact(n-r);}
/*nPr*/ll npr(ll n,ll r){return fact(n)/fact(n-r);}
/*primejudge*/bool prime(ll a){if(a<=1)return false;ll i;for(i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
ll ans=0;llfor;///////////////////////////////////////////////////////////
int main(){
 char s[110];sc(s);
 ll k;sc(k);
 ll len=strlen(s);
 ll ans=0; 
 ll flag;
 ll a=1,b=1;
 ll c=1;
 char aa=s[0],bb=s[len-1];
 rep(i,0,len){
  if(s[i]!=s[i+1])break;
  a++;
 }
 if(a==len){pr(a*k/2);return 0;}
 rrp(i,len,0){
  if(s[i]!=s[i-1])break;
  b++;
 }
 char now=s[0];
 rep(i,1,len){
  if(now==s[i])c++;
  else{
   now=s[i];
   ans+=c/2;
   //pr(c);cout<<"ans: "<<ans<<endl;
   c=1;
  }
  if(i==len-1){
   now=s[i];
   ans+=c/2;
   //pr(c);cout<<"ans: "<<ans<<endl;
  }
 }
 if(aa!=bb)ans*=k;
 else ans=ans*k-(a/2+b/2-(a+b)/2)*(k-1);
 pr(ans);
  return 0;}

Measured memory_bytes: 3640
A=input() 
B=input() 
C=input() 

i=0
j=-1
k=-1
c=0

while(True):
    if(c==0):
        if(i>=(len(A))):
            print("A")
            exit()
        if(A[i]=="a"):
            i+=1
            c=0
        elif(A[i]=="b"):
            j+=1
            c=1
        else:
            k+=1
            c=2

    elif(c==1):
        if(j>=(len(B))):
            print("B")
            exit()
        if(B[j]=="a"):
            i+=1
            c=0
        elif(B[j]=="b"):
            j+=1
            c=1
        else:
            k+=1
            c=2
    else:
        if(k>=(len(C))):
            print("C")
            exit()
        if(C[k]=="a"):
            i+=1
            c=0
        elif(C[k]=="b"):
            j+=1
            c=1
        else:
            k+=1
            c=2


    



Measured memory_bytes: 3064
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define PI 3.141592
#define MOD7 1000000007
#define LL_INF 9000000000000000000
#define LL_MINF -9000000000000000000
#define INT_INF 2000000000
#define INT_MINF -2000000000
#define all(a) (a).begin(), (a).end()
#define fi first
#define se second
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int main(){
    int N, M;
    cin >> N >> M;
    vector<int> X(M);
    for(int i = 0; i < M; i++) cin>> X[i];
    if(N >= M){
        puts("0");
        return 0;
    }

    sort(all(X));
    vector<int> dist(M - 1);
    for(int i = 0; i < M - 1; i++){
        dist[i] = X[i + 1]- X[i];
    }
    sort(all(dist));
    ll sum = 0;
    for(int i = 0; i < M - N; i++){
        sum += dist[i];
    }
    cout << sum << endl;
}

Measured memory_bytes: 3960
#include<queue>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include <cstring>
#include <string.h>
#include <cmath>
#include <math.h>
#include <time.h>
#define ll long long
#define N 3003
#define M 103
#define db double
#define P putchar
#define G getchar
using namespace std;
char ch;
void read(int &n)
{
	n=0;
	ch=G();
	while((ch<'0' || ch>'9') && ch!='-')ch=G();
	ll w=1;
	if(ch=='-')w=-1,ch=G();
	while('0'<=ch && ch<='9')n=(n<<3)+(n<<1)+ch-'0',ch=G();
	n*=w;
}

int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
ll abs(ll x){return x<0?-x:x;}
ll sqr(ll x){return x*x;}
void write(ll x){if(x>9) write(x/10);P(x%10+'0');}

int f[N][N][2],n,m,ans;

void add(int& a,int b)
{
	a=(a+b)%1000000007;
}

int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	
	read(n);read(m);
	
	f[0][0][1]=1;
	for(int i=1;i<=n;i++)
		f[0][i][0]=1;
	
	for(int i=0;i<m;i++)
		for(int j=0;j<=n;j++)
			for(int k=0;k<=1;k++)
			{
				if(j)add(f[i+1][j-1][!(j-1)|k],f[i][j][k]);
				if(n-j)add(f[i+1][j+1][k],f[i][j][k]);
				if(j)add(f[i+1][j][k|(j==1)],f[i][j][k]);
				if(n-j)add(f[i+1][j][k],f[i][j][k]);
			}
	
	ans=0;
	for(int i=0;i<=n;i++)
		add(ans,f[m][i][1]);
	
	write(ans);
	
	return 0;
}


Measured memory_bytes: 70656
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val a = IntArray(n)
    for (i in 0 until n) {
        a[i] = sc.nextInt()
    }
    println(a.joinToString(" "))
    insertionSort(a)
}

fun insertionSort(a: IntArray) {
    for (i in 1 until a.size) {
        val v = a[i]
        var ti = i
        for (j in i - 1 downTo 0) {
            if (v < a[j]) {
                a[j + 1] = a[j]
                ti = j
            }
        }
        a[ti] = v
        println(a.joinToString(" "))
    }
}



Measured memory_bytes: 31572
#include<stdio.h>
#include<algorithm>
using namespace std;
   int a[5];
   int main()
   {
   for(int i=0;i<3;i++) 
      scanf("%d",&a[i]);
   sort(a,a+3);
   if(a[0]==5&&a[1]==5&&a[2]==7)
   printf("YES\n");
   else
   printf("NO\n");
   } 
//


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

using namespace std; 

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef pair<LL, LL> PLL;
typedef vector<PLL> VPLL;
typedef priority_queue<int> PQ_DESC;
typedef priority_queue<int, vector<int>, greater<int>> PQ_ASC;
typedef priority_queue<PII> PQ_DESC_PII;
typedef priority_queue<PII, vector<PII>, greater<PII>> PQ_ASC_PII;

#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define MP make_pair
#define SORT_ASC(c) sort(ALL(c))
//#define SORT_DESC(c) sort(ALL(c), greater<typeof(*((c).begin()))>())
#define SORT_DESC(c) sort((c).rbegin(),(c).rend())
#define REV(c) reverse((c).begin(), (c).end())
#define SIZE(a) int((a).size())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ROF(i,a,b) for(int i=(b-1);i>=(a);--i)
#define REP(i,n) FOR(i,0,n)
#define PER(i,n) ROF(i,0,n)

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int LARGE_INT = 1e9+100;
const int INF = 2e9+100;
const LL INF_LL = (LL)INF*(LL)INF;
const int MOD = 1e9+7;

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

LL modpow(LL a, LL n) {
    LL res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

void Main()
{
    int k,s;cin>>k>>s;

    LL result=0;
    REP(i,k+1){
        REP(j,k+1){
            if(i+j > s || i+j < s-k){
                continue;
            }
            result++;
        }
    }
    cout<<result<<endl;
	return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
    return 0;
}

Measured memory_bytes: 384
#include<cstdio>
#include<iostream>
using namespace std;
int H(int n) {
	if (n == 1) return 1;
	return H(n - 1) + n;
}
int main() {
	int a, b;
	cin >> a >> b;
	printf("%d", H(b - a) - b);
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
using namespace std;
long long int factorialDP(int n)
{
	int a[n+1],i; // factorials array
	a[0]=1;
	
	for(i=1;i<=n;i++) 
	{
		a[i] = i * a[i-1];
	}
	
	return a[n];
}
int main(void){
    // Your code here!
int n;
cin >> n;
int posA=1;
vector<int> A,B;
int posB=1;
int min=1;
for(int i=0;i<n;i++)
   {
       int x;
       cin >> x;
       int smlalrd=0;
       for(auto y:A)
          if(y<x)
             smlalrd++;
       posA+=(x-smlalrd-1)*factorialDP(n-i-1);
     
       A.push_back(x);
       if(x==min)
         min++;
   }
   min=1;
   for(int i=0;i<n;i++)
   {
       int x;
       cin >> x;
       int smlalrd=0;
      for(auto y:B)
         if(y<x)
           smlalrd++;
        
       posB+=(x-smlalrd-1)*factorialDP(n-i-1);
       
    
       B.push_back(x);
       if(x==min)
         min++;
   }
   cout << abs(posA-posB);
}


Measured memory_bytes: 256
#include <cstdio>

int arr[2001];
int n, z, w;

int abs(int x){
	return x>0?x:-x;
}
int max(int a, int b){
	return a>b?a:b;
}

int main(){
	scanf("%d %d %d", &n, &z, &w);
	for(int i=1; i<=n; i++)
		scanf("%d", &arr[i]);
	if(n == 1)
		printf("%d\n", abs(w-arr[n]));
	else
		printf("%d\n", max(abs(w-arr[n]), abs(arr[n-1]-arr[n])));
}


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

using namespace std;

typedef long long lli;
typedef double lld;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<double> vdl;
typedef vector<vector<lli>> mat;
typedef vector<vdl> mad;
typedef unordered_map<lli,unordered_map<lli,lli>> graph;
typedef complex<double> cmp;
typedef vector<cmp> vcl;

lli n,q;
vll a,b,c;
multiset<lli> l,r;
lli ans = 0;
lli p,x,y;

int main(){
  cin >> n >> q;
  a = vll(2*n);
  b = vll(2*n);
  c = vll(2*n);
  for(lli i = 0;i < 2*n;i++) cin >> a[i];
  for(lli i = 0;i < 2*n;i++) cin >> b[i];
  for(lli i = 0;i < 2*n;i++) c[i] = a[i]-b[i];
  ans = accumulate(a.begin(),a.end(),0ll);
  for(lli i = 1;i < 2*n-1;i++){
    if(c[i] < 0){
      r.insert(c[i]);
    }else{
      l.insert(c[i]);
    }
  }

  for(lli x : r){
    ans -= x;
  }
  for(lli i = 0;i < q;i++){
    cin >> p >> x >> y;
    p--;
    if(p >= 1 && p < 2*n-1){
      if(l.find(c[p]) != l.end()) l.erase(l.find(c[p]));
      else if(r.find(c[p]) != r.end()){
        r.erase(r.find(c[p]));
        ans += c[p];
      }
    }
    ans -= a[p];
    a[p] = x;
    b[p] = y;
    c[p] = a[p]-b[p];
    ans += a[p];
    if(p >= 1 && p < 2*n-1){
      if(c[p] < 0){
        r.insert(c[p]);
        ans -= c[p];
      } else l.insert(c[p]);
    }
    if(r.size()%2 == 1 && *r.rbegin()+*l.begin() < 0) cout << ans-*l.begin() << endl;
    else if(r.size()%2 == 1 && *r.rbegin()+*l.begin() >= 0) cout << ans+*r.rbegin() << endl;
    else cout << ans << endl;
  }
}


Measured memory_bytes: 15744
from enum import Enum
import sys
import math

#0:中央,1:南,2:東,3:西,4:北,5:裏側
class Dice():

    def __init__(self):
        self.number = [i for i in range(6)]
        self.work = [i for i in range(6)]
        self.order = 'NNNNWNNNWNNNENNNENNNWNNN'

    def setNumber(self,n0,n1,n2,n3,n4,n5):
        self.number[0] = n0
        self.number[1] = n1
        self.number[2] = n2
        self.number[3] = n3
        self.number[4] = n4
        self.number[5] = n5

    def roll(self,loc):
        for i in range(6):
            self.work[i] = self.number[i]

        if loc == 'E':
            self.setNumber(self.work[3],self.work[1],self.work[0],self.work[5],self.work[4],self.work[2])
        elif loc == 'N':
            self.setNumber(self.work[1],self.work[5],self.work[2],self.work[3],self.work[0],self.work[4])
        elif loc == 'S':
            self.setNumber(self.work[4],self.work[0],self.work[2],self.work[3],self.work[5],self.work[1])
        elif loc == 'W':
            self.setNumber(self.work[2],self.work[1],self.work[5],self.work[0],self.work[4],self.work[3])

    def query(self,top_num,front_num):
        self.save_data = [i for i in range(6)]
        for i in range(len(self.number)):
            self.save_data[i] = self.number[i]
        ret =-1

        for i in range(len(self.order)):
            self.roll(self.order[i])
            if self.number[0] == top_num and self.number[1] == front_num:
                ret = self.number[2]
                break
        for i in range(len(self.number)):
            self.number[i] = self.save_data[i]

    def equal(self,another):
        ret = False;

        for i in range(len(self.order)):
            self.roll(self.order[i])
            FLG=True
            for k in range(6):
                if self.number[k] != another.number[k]:
                    FLG = False
                    break
            if FLG == True:
                return True

        return ret;

num_dice=int(input())
DICE=[]

for i in range(num_dice):
    table = list(map(int,input().split()))
    tmp_dice=Dice()
    tmp_dice.setNumber(table[0],table[1],table[2],table[3],table[4],table[5])
    DICE.append(tmp_dice)

FLG = True

for i in range(num_dice-1):
    for k in range(i+1,num_dice):
        if DICE[i].equal(DICE[k])==True:
            FLG = False
            break
            
if FLG == True:
    print("Yes")
else:
    print("No")
    


Measured memory_bytes: 6388
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
#define all(q) (q).begin(),(q).end()
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll dp[105][105][400],n,w,cost[105],weight[105];
ll recur(int pos,int taken,int k)
{
    if(weight[0]*taken+k>w)
        return INT_MIN;
    if(pos==n)
        return 0;
    ll &ret=dp[pos][taken][k];
    if(ret!=-1)
        return ret;
    ret=max(recur(pos+1,taken,k),recur(pos+1,taken+1,k+weight[pos]-weight[0])+cost[pos]);
    return ret;
}
int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
    memset(dp,-1,sizeof(dp));
    cin>>n>>w;
    for(int i=0; i<n; i++)
        cin>>weight[i]>>cost[i];
    cout<<recur(0,0,0)<<endl;


    return 0;
}


Measured memory_bytes: 38064
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<string>
#define rep(i,n,m) for(int i=(n);i<(int)(m);i++)
#define reps(i,n,m) for(int i=(n);i<=(int)(m);i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define lb lower_bound
#define ub upper_bound
#define LB(a,x) lb(all(a), x) - a.begin()
#define UB(a,x) ub(all(a), x) - a.begin()
#define MOD 1000000007
#define itn int
#define enld endl
#define ednl endl
#define icn cin
using namespace std;
typedef long long ll;
const double pi = 3.141592653589793;
using Graph = vector<vector<int>>;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return 1;} return 0;}
template<class T> bool chmin(T &a, const T &b){if(b<a){a=b; return 1;} return 0;}
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    ll X,K,D; cin>> X >>K >> D;
    if(X == 0){
        if(K % 2 == 0) cout << 0 << endl;
        else cout << D << endl;
        return 0;
    }else{
        if(X < 0) X *= -1;
        ll t = (X+D-1)/D;
        if(t >= K){
            cout << abs(X - K*D) << endl;
            return 0;
        }else{
            K -= t;
            if(K % 2 == 0){
                cout << abs(X - D*t) << endl;
            }else{
                cout << abs(X - D*t + D) << endl;
            }
        }
    }
}

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


/* Raiyan Noory Rady,CSE'17,RUET
Email:raiyannooryrady@gmail.com
Smile->Desire->Unity->Effort->Struggle->Success->Again smile :)
*/

#define ll long long int
#define pf push_front
#define mod  1000000007
#define inf  1000000000000000000
#define pi  acos(-1.0)
#define maxn  1000009
#define sorted(s)  sort(s.begin(),s.end())
#define sortarr(a) sort(a,a+n)
#define slc(n) scanf("%I64d", &n)
#define sl(n)  scanf("%lld", &n)
#define sf(n)  scanf("%lf", &n)
#define si(n)  scanf("%d", &n)
#define sch(n)  scanf(" %c", &n)
#define ss(n)  scanf("%s", n)
#define prf printf
#define pb  push_back
#define fr first
#define sc second
#define all(a)  a.begin(),a.end()
#define forl(n) for(i=0;i<n;i++)
/*STL library functions

sort(first_iterator, last_iterator) � To sort the given vector.

reverse(first_iterator, last_iterator) � To reverse a vector.

*max_element (first_iterator, last_iterator) � To find the maximum element of a vector.

*min_element (first_iterator, last_iterator) � To find the minimum element of a vector.

accumulate(first_iterator, last_iterator, initial value of sum) � Does the summation of vector elements

count(first_iterator, last_iterator,x) � To count the occurrences of x in vector.

find(first_iterator, last_iterator, x) � Points to last address of vector ((name_of_vector).end())
 if element is not present in vector.

binary_search(first_iterator, last_iterator, x) � Tests whether x exists in sorted vector or not.

lower_bound(first_iterator, last_iterator, x) � returns an iterator pointing to the first element in the range [first,last)
which has a value not less than �x�.

upper_bound(first_iterator, last_iterator, x) � returns an iterator pointing to the first element in the range [first,last)
 which has a value greater than �x�.

arr.erase(position to be deleted) � This erases selected element in vector and shifts and resizes the vector elements accordingly.

arr.erase(unique(arr.begin(),arr.end()),arr.end()) � This erases the duplicate occurrences in sorted vector in a single line.

distance(first_iterator,desired_position) � It returns the distance of desired position from the first iterator.
This function is very useful while finding the index.

next_permutation(first_iterator, last_iterator) � This modified the vector to its next permutation.

prev_permutation(first_iterator, last_iterator) � This modified the vector to its previous permutation.
*/

using namespace std;

int main()
{

    ll n,i,v;
    cin>>n;
    ll a[n+5];
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    v=0;
    for(i=0;i<n;i++)
    {
        if(a[i]==v+1)
        {
            v++;
        }
    }
    if(v)
    cout<<n-v<<endl;
    else
        cout<<-1<<endl;

    return 0;
}






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

template<class T> struct SegmentTree {
    using F = function<T(T, T)>;
    int n;
    T id;
    vector<T> data;
    F f;
    F g;

    SegmentTree(int sz, F f, F g, T def) : f(f), g(g) {
        n = 1; id = def;
        while (n < sz) n *= 2;
        data = vector<T>(2*n-1, id);
    }

    SegmentTree(vector<T> v, F f, F g, T def) : f(f), g(g) {
        n = 1; id = def;
        while (n < (int)v.size()) n *= 2;
        data = vector<T>(2*n-1, id);
        for (int i = 0; i < (int)v.size(); i++) data[i+n-1] = v[i];
        for (int i = n-2; i >=0; i--) data[i] = f(data[i*2+1], data[i*2+2]);
    }

    void update (int i, T x) {
        i += n - 1;
        data[i] = g(data[i], x);
        while (i > 0) {
            i = (i - 1) / 2;
            data[i] = f(data[i * 2 + 1], data[i * 2 + 2]);
        }
    }

    T query(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r < 0) r = n;
        if (r <= a || b <= l) return id;
        if (a <= l && r <= b) return data[k];
        T vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
        T vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return f(vl, vr);
    }

};

template<typename T> T GCD(T a, T b) {
    if (b == 0) return a;
    if (a % b == 0) return b;
    return (GCD(b, a % b));
}

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    auto f = [](long long a, long long b) { return GCD(a, b); };
    auto g = [](long long a, long long b) { return b; };
    SegmentTree<long long> sg(a, f, g, 0);
    
    long long ans = -1;
    for (int i = 0; i < n; i++) {
        ans = max(ans, GCD(sg.query(0, i), sg.query(i+1, n)));
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3840
#!/usr/bin/python3
import sys
input = lambda: sys.stdin.readline().strip()
n = int(input())
a = [0, *(int(x) for x in input().split())]
divisors = [[] for i in range(n + 1)]
for i in range(1, n + 1):
    for j in range(i, n + 1, i):
        divisors[j].append(i)
ans = []
for i in reversed(range(1, n + 1)):
    if a[i]:
        for j in divisors[i]:
            a[j] ^= 1
        ans.append(i)
print(len(ans))
print(*ans)


Measured memory_bytes: 153348
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <cctype>
#include <string>
#include <map>
#include <set>
#include <math.h>
#include <cmath>
#define ll long long
#define lli long long int

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

int main(){

  int N;
  cin >> N;
  double ans = 0;
  vector<double> X(N);
  vector<double> Y(N);
  vector<int> v(N);

  for (int i = 0; i < N; i++) {
    cin >> X.at(i) >> Y.at(i);
    v.at(i) = i+1;
  }

  double sum;
  int num = 0;
  do {
    for(int n = 1; n < N; n++){

      int i = v.at(n)-1;
      int j = v.at(n-1)-1;

      sum += sqrt(pow(X.at(i) - X.at(j),2.0)+pow(Y.at(i) - Y.at(j),2.0));
      // cout << sum << endl;
    }
    num++;
  } while (next_permutation(v.begin(), v.end()));

  ans = sum/num;

  printf("%.6lf\n", ans);

  return 0;
}

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

int main(){
    int n, l;
    cin >> n >> l;
    vector<string> S(n);
    copy_n(istream_iterator<string>(cin), n, S.begin());
    sort(S.begin(), S.end());

    copy(S.begin(), S.end(), ostream_iterator<string>(cout));
    cout << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long int
#define nl cout << endl
#define pb push_back
#define ff first
#define ss second
#define all(ar) ar.begin(), ar.end()
#define Sort(x) sort(all(x))
#define print_vector(my_vector_name) for(int i=0; i<my_vector_name.size(); i++) cout << my_vector_name[i] << " ";nl
//debugger
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

#define hang while (1)

int main() {
	fast;
	int n;
	cin >> n;
	std::vector<int> v(n);
	int x=0;
	for (int i=0; i<n; i++) {
		cin >> v[i];
		x^=v[i];
	}
	for (int i=0; i<n; i++) {
		cout << (x^v[i]) << " ";
	}
	nl;
	return 0;
}

//notes
/*
 value of INT_MAX and INT_MIN is fixed and they are
 INT_MAX = 2147483647
 INT_MIN = -2147483648
 use these format of input when number of inputs not provided
 *while(scanf("%lld",&n)!=EOF)
 *while using getline(cin,s) for taking input of a string which is 
 having white space characters just write cin>>ws; before geline(cin,s)
 to make it work properly
*/

/*
 use 2-D vector for representing the pair<int,pair<int,int> > kind of things
*/

Measured memory_bytes: 3972
#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

#define REP(a, i, n) for (int i = a; i < n; ++i)

int abs(int X, int Y) {
    return X > Y ? X - Y : Y - X;
}

int median(int* A, int n) {
    if (n % 2 == 1) {
        return A[(n + 1) / 2 - 1];
    } else {
        return (A[n / 2 - 1] + A[n / 2]) / 2;
    }
}

int main() {
    int N;
    cin >> N;

    int A[N];
    REP(0, i, N) {
        cin >> A[i];
    }

    int B[N];
    REP(0, i, N) {
        B[i] = A[i] - i;
    }

    sort(B, B + N);
    int b = median(B, N);

    long ans = 0;
    REP(0, i, N) {
        ans += abs(B[i] - b);
    }

    printf("%ld\n", ans);

    return 0;
}


Measured memory_bytes: 1792
class CalcService
  def initialize(s)
    @s = s
    @memo = {}
  end

  def execute
    j = 1
    answer = {}
    ans = 0
    while true do
      ans = a(j)
      answer[ans] ||= []
      answer[ans] << j
      break if answer[ans].length > 1
      j += 1
    end
    puts j
  end

  def a (i)
    return @s if i == 1
    f(a(i-1))
  end

  def f (n)
    return @memo[n] if @memo.key?(n)
    if n % 2 == 0
      return n/2
    else
      return 3*n + 1
    end
  end
end
s = gets.to_i
CalcService.new(s).execute


Measured memory_bytes: 1788
n = int(input())
seq = [int(x) for x in input().split()]
dp = [0]*n
dp[1] = abs(seq[1] - seq[0])
for i in range(2, n):
  dp[i] = min(dp[i-1] + abs(seq[i] - seq[i-1]),  dp[i-2] + abs(seq[i] - seq[i-2]))
print(dp[-1])

Measured memory_bytes: 13800
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
int main()
{
    int n,k;
    scanf("%d %d",&n,&k);
    vector<int> h(n);
    for(int& i:h)
       {

        scanf("%d",&i);}
        vector<int> dp(n,inf);
        dp[0]=0;
        for(int i=0;i<n;i++)


        {

                for(int j =i+1;j<=i+k;j++)
        {if(j<n)
        {dp[j]=min(dp[j],dp[i]+abs(h[i]-h[j]));

        }

        }

        }
        cout<<dp[n-1]<<endl;


}

Measured memory_bytes: 4036
#include <stdio.h>
#include <stdlib.h>
int main(void) {
    int n;
    static int h[1000000];
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%d", &h[i]);
    }

    static int dp[1000000] = {};
    dp[0] = 0;
    dp[1] = abs(h[1] - h[0]);
    for (int i = 2; i < n; i++) {
        dp[i] = dp[i - 1] + abs(h[i] - h[i - 1]);
        if (dp[i] > dp[i - 2] + abs(h[i] - h[i - 2])) {
            dp[i] -= dp[i - 1] + abs(h[i] - h[i - 1]);
            dp[i] = dp[i - 2] + abs(h[i] - h[i - 2]);
        }
    }

    printf("%d\n", dp[n - 1]);
    return 0;
}

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

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

signed main() {
  ll M, D, ans=0;
  cin >> M >> D;
  for (ll m = 1; m <= M; m++) {
    for (ll d = 1; d <= D; d++) {
      ll d1 = d % 10;
      ll d2 = (d / 10) % 10;
      if (m == d1 * d2 && d1 >= 2 && d2 >= 2) {
        ans++;
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#include <queue>
#include <stack>
#include <vector>
#define loop(n) for(ll i=0;i<n;i++)
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
typedef long long int ll;


int main()
{
    fastio;
    ll n,k;
    cin>>n>>k;
    ll arr[n];
    for(ll i=0;i<n;i++)
		cin>>arr[i];
	
	ll dp[k+1][n];
	
	for(ll i=0;i<=k;i++)
	{
		bool one = false;
		for(ll j=0;j<n;j++)
		{
			if(i==0)
				dp[i][j] = 0;
			else
			{
				if(one)
					dp[i][j] = 1;
				else
				{
					if(i - arr[j] == 0)
					{
						dp[i][j] = 1;
						one = true;
					}
					else if(i - arr[j] < 0)
						dp[i][j] = 0;
					else
					{
						if(dp[i-arr[j]][n-1] == 1)
							dp[i][j] = 0;
						else
						{
							dp[i][j] = 1;
							one = true;
						}
					}
				}
			}
		}
	}
	
	if(dp[k][n-1] == 1)
		cout<<"First"<<endl;
	else
		cout<<"Second"<<endl;
	
				
				
    return 0;
}


Measured memory_bytes: 81696