akhauriyash/Code-Regression huggingface dataset:
#include <vector>
#include <string>
#include <map>
#include <tuple>
#include <iostream>
#include <queue>
using namespace std;

typedef unsigned long long ull;


class RollingHash{
private:
	const ull B = 100000007;
	vector<ull>P;
	vector<ull>H;
	string s;
public:
	RollingHash(string _s){
		s = _s;
		P.push_back(1);
		H.push_back(0);
		for(int i=1;i<=s.size();i++){
			P.push_back(P[i-1] * B);
			H.push_back(H[i-1] * B + s[i-1]);
		}
	}
	ull Get(int l, int r){//l<=x<r
		return H[r] - H[l] * P[r-l];
	}
};

void Manachar(string s, vector<int>*r){
	(*r).resize(s.size());
	int i=0, j=0;
	while(i < s.size()){
		while(i-j >= 0 && i+j < s.size() && s[i-j] == s[i+j])++j;
		(*r)[i] = j;
		int k = 1;
		while(i-k >= 0 && i+k < s.size() && k+(*r)[i-k]<j){
			(*r)[i+k]=(*r)[i-k];
			++k;
		}
		i += k;
		j -= k;
	}
}

string AddDollar(string s){
	string tmp = "$";
	for(int i=0;i<s.size();i++){
		tmp += s[i];
		tmp += "$";
	}
	return tmp;
}

int main(){
	
	string S;
	cin>>S;
	S = AddDollar(S);
	vector<int>S_Rad;
	Manachar(S, &S_Rad);
	RollingHash S_RH(S);
	map<ull, ull>S_Count;
	map<ull, int>S_Flg;
	priority_queue<tuple<int, int, int, ull> >S_Q;
	for(int i=0;i<S.size();i++){
		if(S_Rad[i]==1)continue;
 		ull h = S_RH.Get(i-S_Rad[i]+2, i+S_Rad[i]-1);
		S_Count[h]++;
		if(S_Flg[h])continue;
		S_Flg[h]=1;
		S_Q.push(make_tuple(S_Rad[i]-1,i-S_Rad[i]+2,i+S_Rad[i]-1,h));
	}
	
	while(!S_Q.empty()){
		int rad = get<0>(S_Q.top());
		int l = get<1>(S_Q.top());
		int r = get<2>(S_Q.top());
		ull h = get<3>(S_Q.top());
		S_Q.pop();
		if(rad<=2)break;
		l+=2;
		r-=2;
		ull nxt = S_RH.Get(l, r);
		S_Count[nxt]+=S_Count[h];
		if(S_Flg[nxt])continue;
		S_Flg[nxt]=1;
		S_Q.push(make_tuple(rad-2,l,r,nxt) );
	}
	
	string T;
	cin>>T;
	T = AddDollar(T);
	vector<int>T_Rad;
	Manachar(T, &T_Rad);
	RollingHash T_RH(T);
	map<ull, ull>T_Count;
	map<ull, int>T_Flg;
	priority_queue<tuple<int, int, int, ull> >T_Q;
	for(int i=0;i<T.size();i++){
		if(T_Rad[i]==1)continue;
 		ull h = T_RH.Get(i-T_Rad[i]+2, i+T_Rad[i]-1);
		T_Count[h]++;
		if(T_Flg[h])continue;
		T_Flg[h]=1;
		T_Q.push(make_tuple(T_Rad[i]-1,i-T_Rad[i]+2,i+T_Rad[i]-1,h));
	}
	
	ull sum = 0;
	
	while(!T_Q.empty()){
		int rad = get<0>(T_Q.top());
		int l = get<1>(T_Q.top());
		int r = get<2>(T_Q.top());
		ull h = get<3>(T_Q.top());
		T_Q.pop();
		if(S_Count.count(h)){
			sum += T_Count[h] * S_Count[h];
		}
		if(rad<=2)continue;
		l+=2;
		r-=2;
		ull nxt = T_RH.Get(l, r);
		T_Count[nxt]+=T_Count[h];
		if(T_Flg[nxt])continue;
		T_Flg[nxt]=1;
		T_Q.push(make_tuple(rad-2,l,r,nxt) );
	}
	
	cout<<sum<<endl;
	
	return 0;
}


Measured memory_bytes: 22128
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c> {i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
	~debug() { cerr << endl; }
	eni( != ) cerr << boolalpha << i; ris;
}
eni( == ) ris << range(begin(i), end(i));
}
sim, class b dor(pair < b, c > d) {
	ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
	*this << "[";
	for (auto it = d.b; it != d.e; ++it)
		*this << ", " + 2 * (it == d.b) << *it;
	ris << "]";
}
#else
	sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
template <typename T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long
#define ld long double
#define pb push_back
#define mp make_pair
#define in insert
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define mod 1000000007
#define sz(v) (int)(v.size())
#define all(x) x.begin(), x.end()
#define prec fixed << setprecision(12)
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define test int t; cin >> t; while(t--)
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef set<int> si;
typedef map<int, int> mii;
typedef vector<pii> vpi;
int _x[] = {0, 0, -1, 1, -1, 1, -1, 1};
int _y[] = { -1, 1, 0, 0, 1, -1, -1, 1};

void solve() {
    int n, x;
    cin >> n;
    int cnt = 0;
    for(int i=1; i<=n; ++i){
        cin >> x;
        if(x != i)
            cnt++;
    }
    if(cnt == 2 || cnt == 0) cout << "YES\n";
    else cout << "NO\n";
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
	// test
	solve();
	return 0;
}


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

int main()
{
  string S;
  cin >> S;
  if (S == "hi" || S == "hihi" || S == "hihihi" || S == "hihihihi" || S == "hihihihihi")
  {
    cout << "Yes" << endl;
  }
  else
  {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    a, b, c = map(int, input().split())
    if a + b == c or b + c == a or c + a == b:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 3060
#include <stdio.h>

/** Application main entry point. */
int main (
  int argc,
  char *argv[ ]
  )
{
  int no;
  double w, l;

  while ( scanf ( " %d,%lf,%lf", &no, &w, &l ) == 3 )
  {
    if ( w / l / l >= 25. )
    {
      printf ( "%d\n", no );
    }
  }

  return ( 0 );
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 1000000000000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



int main(){

	char buf[15];
	scanf("%s",buf);

	int head = 0,tail = 0;
	int table[15];

	for(int i = 0; buf[i] != '\0'; i++){

		if(buf[i] == 'B'){

			tail = max(0,tail-1);

		}else{

			table[tail++] = buf[i]-'0';
		}
	}

	for(int i = 0; i < tail; i++){

		printf("%d",table[i]);
	}
	printf("\n");

	return 0;
}


Measured memory_bytes: 256
n=int(input())
s=input()

r=s.count("R")
g=s.count("G")
b=s.count("B")

rgb = r*g*b

not_j2_num = 0

for i in range(len(s)-2):
    for j in range(i+1,len(s)-1):
        
        k=j+j-i
        
        # print(i,j,k)
        
        if k<len(s) and len(set([s[i],s[j],s[k]]))==3:
            
            not_j2_num += 1
            
print(rgb - not_j2_num)


Measured memory_bytes: 73864
//Daniel Grzegorzewski
#include <bits/stdc++.h>

#define MP make_pair
#define PB push_back
#define ST first
#define ND second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef long long LL;

void init_ios()
{
     ios_base::sync_with_stdio(0);
     cin.tie(0);
}

int f(int b, int n)
{
	if (n < b)
		return n;
	return n%b + f(b, n/b);
}

const int sq = 4*(int)1e5;
int n, s;

signed main()
{
    init_ios();
    cin >> n >> s;
    for (int b = 2; b <= min(n+1, sq); ++b)
    	if (f(b, n) == s) {
    		cout<<b<<"\n";
    		return 0;
    	}
    if (n < sq) {
    	cout<<"-1\n";
    	return 0;
    }
    if (s == 1) {
    	cout<<n<<"\n";
    	return 0;
    }
    if (s == n) {
    	cout<<n+1<<"\n";
    	return 0;
    }
    int k = (int)1e18;
    for (int a1 = 1; a1*a1 <= n; ++a1) {
    	int a0 = s-a1;
    	if (a0 < 0)
    		continue;
    	if (n-a0 > 0 && (n-a0)%a1 == 0 && n != a0+a1) {
    		int nowe = (n-a0)/a1;
    		if (nowe <= a0 || nowe <= a1)
    			continue;
    		k = min(k, (n-a0)/a1);
    	}
    }
    if (k == (int)1e18) {
    	cout<<"-1\n";
    	return 0;
    }
    cout<<k<<"\n";
}

Measured memory_bytes: 256
import java.io.*;
import java.math.BigInteger;
import java.util.*;

/**
 * Created by fcdkbear on 15.10.16.
 */
public class Main {

    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        new Task().solve(in, out);
        out.close();
    }


    static class Task {

        public void solve(InputReader in, PrintWriter out) {

            int n = in.nextInt();
            int[] p = new int[n];
            for (int i = 0; i < n; ++i) {
                p[i] = in.nextInt();
                p[i]--;
            }
            int[] a = new int[n];
            int[] b = new int[n];
            a[0] = 1;
            for (int i = 1; i < n; ++i) {
                a[i] = a[i - 1] + n + 1;
            }
            for (int i = 0; i < n; ++i) {
                b[i] = a[n - i - 1];
            }
            int sum = a[p[0]] + b[p[0]];
            for (int i = 1; i < n; ++i) {
                int currentSum = a[p[i]] + b[p[i]];
                b[p[i]] += sum + 1 - currentSum;
                sum++;
            }
            for (int i = 0; i < n; ++i) {
                if (i > 0) {
                    out.print(" ");
                }
                out.print(a[i]);
            }
            out.println();
            for (int i = 0; i < n; ++i) {
                if (i > 0) {
                    out.print(" ");
                }
                out.print(b[i]);
            }
            out.println();
        }

    }

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

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

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

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

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

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

    }

}


Measured memory_bytes: 15868
#include <iostream>
#include <math.h>

using namespace std;

int main(){
    int n;
    double x,y,d;
    int ans=0;
    cin>>n>>d;
    
    for(int i=0;i<n;i++){
		cin>>x>>y;
		if(sqrt(x*x+y*y)<=d){
			ans++;
			}
		}
	cout<<ans;
    return 0;	
	}


Measured memory_bytes: 3844
#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

use proconio::*;
use text_io::*;

const U_INF: usize = 1 << 60;
const I_INF: isize = 1 << 60;

fn main() {
    input! {
        n:usize,
        a:[usize;n],
    }

    let &max_num = a.iter().max().unwrap();
    
    fn gcd(mut a: usize, mut b: usize) -> usize {
        if a < b {
            swap(&mut a, &mut b)
        }

        if b == 0 {
            a
        } else {
            gcd(b, a % b)
        }
    }
    
    let is_set_wise = a.iter().fold(0, |acc, ai| acc.gcd(ai)) == 1;

    let era = Eratosthenes::new(max_num);
    let mut divisor_counter = vec![0; max_num + 1];

    for ai in a {
        let hm = era.factorization(ai);

        for (k, _v) in hm {
            divisor_counter[k] += 1;
        }
    }

    let is_pair_wise = *divisor_counter.iter().max().unwrap() <= 1;

    let ans = if is_pair_wise {
        "pairwise coprime"
    } else if is_set_wise {
        "setwise coprime"
    } else {
        "not coprime"
    };

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

use itertools::Itertools;
use num::Integer;
use rustc_hash::FxHashMap;
use smallvec::alloc::collections::BTreeMap;
use std::collections::HashMap;
use std::mem::swap;

/// 二分累乗法
pub fn pow(x: isize, n: usize) -> isize {
    if n == 0 {
        1
    } else if n == 1 {
        x
    } else if n % 2 == 1 {
        x * pow(x, n - 1)
    } else {
        pow(x * x, n / 2)
    }
}

/// エラトステネスの篩
/// 構築 O(N log log N)
/// 素因数分解 O(log N)
/// 素数判定 O(log N)
pub struct Eratosthenes {
    smallest_prime_factors: Vec<usize>,
}

impl Eratosthenes {
    pub fn new(n: usize) -> Self {
        let mut smallest_prime_factors = (0..=n).collect_vec();

        for i in 2..n {
            if i * i > n {
                break;
            }

            if smallest_prime_factors[i] != i {
                continue;
            }

            let mut j = i * i;
            while j <= n {
                if smallest_prime_factors[j] == j {
                    smallest_prime_factors[j] = i;
                }

                j += i;
            }
        }

        Self {
            smallest_prime_factors,
        }
    }

    pub fn factorization(&self, mut i: usize) -> BTreeMap<usize, usize> {
        assert_ne!(i, 0);

        let mut factors = BTreeMap::new();

        while i != 1 {
            let divisor = self.smallest_prime_factors[i];
            *factors.entry(divisor).or_insert(0) += 1;

            i /= divisor;
        }

        factors
    }

    pub fn is_prime(&self, i: usize) -> bool {
        i >= 2 && self.smallest_prime_factors[i] == i
    }
}


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

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

int main(){
  int n, m;
  cin >> n >> m;
  vector<int> a(m);
  rep(i,m) cin >> a[i];
  sort(a.begin(), a.end());
  vector<string> dp(n+1);
  int cost[]={0,2,5,5,4,5,6,3,7,6};
  int mn=9;
  rep(i,m){
    if(cost[a[i]]<=n){
	    dp[cost[a[i]]] = to_string(a[i]);
    	mn = min(mn,cost[a[i]]);
    }
  }
  for(int i=2*mn; i<=n; i++){
    rep(j,m){
      if(i-cost[a[j]]>=0){
        string tmp;  
        if(to_string(a[j])[0] >= dp[i-cost[a[j]]][0])
          tmp = to_string(a[j])+dp[i-cost[a[j]]];
        else
          tmp = dp[i-cost[a[j]]]+to_string(a[j]);
        if(tmp.size()>=dp[i].size())
          dp[i] = tmp;
      }
    }
  }
  cout << dp[n] << endl;
  return 0;
}

Measured memory_bytes: 32384
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

const int Q = 1e9 + 7;

const int MAXN = 2e3;

bool r[MAXN];
long long p[MAXN], b[MAXN];

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

    int pc = 0;
    for (int i = 2; i <= n; i++) {
        if (!r[i]) {
            p[pc] = i;
            pc++;
            for (int j = 2 * i; j <= n; j += i)
                r[j] = true;
        }
    }

    for (int i = 0; i < pc; i++) {
        long long k = p[i];
        long long sum = 0;
        while (n / k > 0) {
            sum += n / k;
            k *= p[i];
        }
        b[i] = sum;
    }

    long long res = 1;
    for (int i = 0; i < pc; i++)
        res = (res * (b[i] + 1)) % Q;
    cout << res;

    return 0;
}

Measured memory_bytes: 256
arr1, arr2 = [], []
x = 0
while true
    y = x ** 3
    arr1 << y if y <= 151200
    break if y > 151200
    x += 1
end
x = 0
while true
    y = x * (x + 1) * (x + 2) / 6
    arr2 << y if y <= 151200
    break if y > 151200
    x += 1
end

while true
    x = gets.to_i
    break if x == 0
    max = 0
    arr1.each{|a|
        arr2.each{|b|
            z = a + b
            break if z > x
            max = z if max < z
        }
    }
    puts max
end


Measured memory_bytes: 6876
#include "bits/stdc++.h"
using namespace std;


int main()
{
	int a, b;
	cin >> a >> b;

	int ans = 0;
	if (a > b) {
		ans = a + a - 1;
	} else if (a == b) {
		ans = a + b;
	} else {
		ans = b + b - 1;
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <math.h>
#include <climits>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#include <map> 
#include <set>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MD = 1000000007;

/* sample input

*/

int main()
{
	ll q, h, s, d;
	ll n;
	ll count;
	ll a[4];
	ll answer = 0;
	bool flug[4];
	cin >> q >> h >> s >> d;
	cin >> n;

	for (int i = 0; i < 4; i++) {
		flug[i] = true;
	}

	if (d > s * 2 || d > h * 4 || d > q * 8) {
		flug[0] = false;
	}
	if (s > h * 2 || s > q*4) {
		flug[1] = false;
	}
	if (h > q * 2) {
		flug[2] = false;
	}

	if (flug[0]) {
		count = n / 2;
		n = n-count*2;
		answer = d*count;
	}
	if (flug[1]) {
		count = n ;
		n = 0;
		answer += s*count;
	}
	else if(flug[2]){
		count = n*2;
		n = 0;
		answer += h*count;
	}
	else {
		count = n * 4;
		n = 0;
		answer += q*count;
	}

	cout << answer;

	return 0;
}

Measured memory_bytes: 256
// C++ program to find LCM of two numbers  
#include <iostream>  
using namespace std; 
typedef long long ll;
// Recursive function to return gcd of a and b  
class gfg 
{ 
 public : ll gcd(ll a, ll b){ 
    if (a == 0) 
        return b;  
    return gcd(b % a, a);  
 } 
  
   
// Function to return LCM of two numbers  
  ll lcm(ll a, ll b)  
 {  
    return (a*b)/gcd(a, b);  
 }  
} ; 
// Driver program to test above function  
int main()  
{  
    gfg g; 
    ll a,b;
	cin>>a>>b;  
    cout<<g.lcm(a, b);  
    return 0;  
}  

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

a = []
for i in range(n):
  arr = list(map(int, input().split()))
  a.append(arr)

INF = -10 ** 18

dp = [ [INF] * 3 for i in range(0, n+1)]
dp[0] = [0] * 3

for i in range(0, n):
  for j in range(0, 3):
    for k in range(3):
      if (j == k): continue
      dp[i+1][k] = max(dp[i+1][k], dp[i][j] + a[i][k])

print(max(dp[-1]))

Measured memory_bytes: 47344
import numpy as np
h,w=map(int, input().split())
a=[list(input()) for i in range(h)]
a=np.array(a)
for i in range(h):
    for j in range(w):
        if a[i][j]=='.':
            b=a[max(i-1,0):min(i+2,h),max(j-1,0):min(j+2,w)].flatten()
            a[i][j]=sum(b=='#')
for i in a:
    print(''.join(i))

Measured memory_bytes: 12468
import sys
input = sys.stdin.readline

n,m = map(int,input().split())
x = list(map(int,input().split()))

x.sort()

#p : 同じやつの組が何ペア
p = [0]*m
# mod M 何個
q = [0]*m

cnt = 1
for i in range(n):
    q[x[i]%m] += 1
    if i == n-1 or x[i] != x[i+1]:
        p[x[i]%m] += cnt//2
        cnt = 1
    else:
        cnt += 1

res = 0

for i in range(m):
    if i==0:
        res += q[0]//2
        continue
    if i > m-i:
        break
    if i == m-i:
        res += q[i]//2
        continue

    if q[i] >= q[m-i]:
        res += q[m-i]
        q[i] -= q[m-i]
        res += min(q[i]//2,p[i])
    else:
        res += q[i]
        q[m-i] -= q[i]
        res += min(q[m-i]//2,p[m-i])
print(res)


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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

/**
 * Author: Ludo Pulles, chilli, Simon Lindholm
 * Date: 2019-01-09
 * License: CC0
 * Source: http://neerc.ifmo.ru/trains/toulouse/2017/fft2.pdf (do read, it's excellent)
   Accuracy bound from http://www.daemonology.net/papers/fft.pdf
 * Description: fft(a) computes $\hat f(k) = \sum_x a[x] \exp(2\pi i \cdot k x / N)$ for all $k$. N must be a power of 2.
   Useful for convolution:
   \texttt{conv(a, b) = c}, where $c[x] = \sum a[i]b[x-i]$.
   For convolution of complex numbers or more than two vectors: FFT, multiply
   pointwise, divide by n, reverse(start+1, end), FFT back.
   Rounding is safe if $(\sum a_i^2 + \sum b_i^2)\log_2{N} < 9\cdot10^{14}$
   (in practice $10^{16}$; higher for random inputs).
   Otherwise, use NTT/FFTMod.
 * Time: O(N \log N) with $N = |A|+|B|$ ($\tilde 1s$ for $N=2^{22}$)
 * Status: somewhat tested
 * Details: An in-depth examination of precision for both FFT and FFTMod can be found
 * here (https://github.com/simonlindholm/fft-precision/blob/master/fft-precision.md)
 */
#pragma once

typedef complex<double> C;
typedef vector<double> vd;
void fft(vector<C>& a) {
	int n = sz(a), L = 31 - __builtin_clz(n);
	static vector<complex<long double>> R(2, 1);
	static vector<C> rt(2, 1);  // (^ 10% faster if double)
	for (static int k = 2; k < n; k *= 2) {
		R.resize(n); rt.resize(n);
		auto x = polar(1.0L, acos(-1.0L) / k);
		rep(i,k,2*k) rt[i] = R[i] = i&1 ? R[i/2] * x : R[i/2];
	}
	vi rev(n);
	rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
	rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
	for (int k = 1; k < n; k *= 2)
		for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {
			// C z = rt[j+k] * a[i+j+k]; // (25% faster if hand-rolled)  /// include-line
			auto x = (double *)&rt[j+k], y = (double *)&a[i+j+k];        /// exclude-line
			C z(x[0]*y[0] - x[1]*y[1], x[0]*y[1] + x[1]*y[0]);           /// exclude-line
			a[i + j + k] = a[i + j] - z;
			a[i + j] += z;
		}
}
vd conv(const vd& a, const vd& b) {
	if (a.empty() || b.empty()) return {};
	vd res(sz(a) + sz(b) - 1);
	int L = 32 - __builtin_clz(sz(res)), n = 1 << L;
	vector<C> in(n), out(n);
	copy(all(a), begin(in));
	rep(i,0,sz(b)) in[i].imag(b[i]);
	fft(in);
	for (C& x : in) x *= x;
	rep(i,0,n) out[i] = in[-i & (n - 1)] - conj(in[i]);
	fft(out);
	rep(i,0,sz(res)) res[i] = imag(out[i]) / (4 * n);
	return res;
}

int n;
ll p=200003,cnt[200005],ans;
vd a,b;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	cin>>n;
	rep(i,0,n){
		int a;
		cin>>a;
		cnt[a]++;
	}
	ll x=1;
	for(int i=0;i<p-1;i++){
		a.pb(cnt[x]);
		b.pb(cnt[x]);
		x=x*2%p;
	}
	vd c=conv(a,b);
	x=1;
	for(int i=0;i<sz(c);i++){
		ans+=x*ll(round(c[i]));
		x=x*2%p;
	}
	for(ll i=1;i<p;i++){
		ans-=((i*i)%p)*cnt[i];
	}
	cout<<ans/2LL<<endl;
}

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


// 辺 (to,cost)
using edge = pair<int,int>;

// graph : 隣接リスト
// start : 始点
vector<long long> bfs01(const vector<vector<edge>>& graph,int start){
    const long long inf = numeric_limits<long long>::max()/3;
    int N = graph.size();
    vector<long long> d(N,inf);
    deque<pair<int,long long>> deq;
    d[start] = 0;
    deq.push_front(make_pair(start,0));
    while(!deq.empty()){
        auto p = deq.front(); deq.pop_front();

        for(const auto q : graph[p.first]){
            if(d[q.first] <= p.second + q.second) continue;

            d[q.first] = p.second + q.second;
            if(q.second == 0) deq.push_front(make_pair(q.first,d[q.first]));
            if(q.second == 1) deq.push_back(make_pair(q.first,d[q.first]));
        }
    }
    return d;
}

int main(){
    int K; cin >> K;
    vector<vector<edge>> g(K);
    for(int i=0;i<K;i++){
        g[i].push_back(make_pair((i+1)%K,1));
        g[i].push_back(make_pair((i*10)%K,0));
    }

    auto dist = bfs01(g,1);
    cout << dist[0] + 1 << endl;
}


Measured memory_bytes: 7296
K=int(input())
S=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(S[K-1])

Measured memory_bytes: 3060
fact = [1]
for i in range(1,14):
    fact.append(fact[-1]*i)
n = int(input())
def dist(a,b):
    return ((a[0]-b[0])**2 + (a[1]-b[1])**2)**0.5
a = []
for i in range(n):
    x,y = map(int,input().split())
    a.append([x,y])
ans = 0;
for i in a:
    for j in a:
        ans+=(dist(i,j)*fact[n-1])
print(ans/fact[n])


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

int main() {
    vector<int> a(10, 0);
    for(int i = 0; i < 3; i++) {
        int inp; cin >> inp; a[inp]++;
    }
    if(a[5]==2 && a[7]==1) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}


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

int main(){
	int n,m,d,h,i,j,r;
	string str;
	for(;cin>>n,n;cout<<r<<endl){
		vector<int>monster(n);
		for(h=i=0;i<n;i++){
			cin>>monster[i];
			if(h<monster[i])h=monster[i];
		}
		vector<pair<int,int> >_all,_single;
		vector<int>all(h+1),single(h+1);
		map<int,int>all_iter;
		all_iter[0]=0;
		for(cin>>i;i--;){
			cin>>str>>m>>str>>d;
			if(d){
				if(str[0]=='A')_all.push_back(make_pair(m,d));
				else _single.push_back(make_pair(m,d));
			}
		}
		for(i=1;i<=h;i++){
			all[i]=9999999;
			single[i]=9999999;
			for(j=0;j<_all.size();j++){
				all[i]=min(all[i],all[max(0,i-_all[j].second)]+_all[j].first);
			}
			for(j=0;j<_single.size();j++){
				single[i]=min(single[i],single[max(0,i-_single[j].second)]+_single[j].first);
			}
			all_iter[all[i]]=i;
		}

		if(_single.empty()){
			r=all[h];
		}else{
			r=9999999;
			for(map<int,int>::iterator it=all_iter.begin();it!=all_iter.end();it++){
				h=it->first;
				for(j=0;j<monster.size();j++)h+=single[max(0,monster[j]-it->second)];
				if(r>h)r=h;
			}
		}
	}
}

Measured memory_bytes: 2120
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define sz(x) (int)(x.size())
vector<vector<int>> g(82);
vector<bool> visited(82, false);
void dfs(int v) {
    visited[v] = true;
    for (auto &u : g[v]) {
        if (!visited[u]) {
            dfs(u);
        }
    }
}

int ind(int i, int j) {
    return i * 8 + j;
}
pair<int, int> rind(int x) {
    return {x / 8, x % 8};
} 
signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int h, w;
    cin >> h >> w;
    string s[h];
    for (int i = 0; i < h; i++) {
        cin >> s[i];
    }
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (s[i][j] == '.') continue;
            if (i + 1 < h && s[i + 1][j] == '#'){
                g[ind(i, j)].push_back(ind(i + 1, j));
            } else if (j + 1 < w && s[i][j + 1] == '#'){
                g[ind(i, j)].push_back(ind(i, j + 1));
            }
        }
    }
    dfs(0);
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (s[i][j] == '#' && !visited[ind(i, j)]) {
                cout << "Impossible\n";
                return 0;
            }
        }
    }
    cout << "Possible\n";
}

Measured memory_bytes: 256
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		new Main().run();
	}

	void run() {
		Scanner sc = new Scanner(System.in);
		String line = sc.nextLine();
		String[] lineArr = line.split(" ");

		Deque<String> stack = new ArrayDeque<String>();
		for (String s : lineArr) {
			if ("+".equals(s)) {
				int a = Integer.parseInt(stack.pop());
				int b = Integer.parseInt(stack.pop());
				stack.push(String.valueOf(a + b));
			} else if ("-".equals(s)) {
				int a = Integer.parseInt(stack.pop());
				int b = Integer.parseInt(stack.pop());
				stack.push(String.valueOf(b - a));
			} else if ("*".equals(s)) {
				int a = Integer.parseInt(stack.pop());
				int b = Integer.parseInt(stack.pop());
				stack.push(String.valueOf(a * b));
			} else {
				stack.push(s);
			}
		}
		System.out.println(stack.pop());
	}
}

Measured memory_bytes: 26332
#import <Foundation/Foundation.h>

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        NSData *stdinData = [[NSFileHandle fileHandleWithStandardInput] availableData];
        NSString *s = [[NSString alloc] initWithData:stdinData encoding:NSUTF8StringEncoding];
        NSArray *l = [s componentsSeparatedByString:@" "];
        NSString *A = [l objectAtIndex:0];
        NSString *B = [l objectAtIndex:1];
        NSString *C = [l objectAtIndex:2];
        
        NSString *ab = [A substringWithRange:NSMakeRange([A length]-1,1)];
        NSString *ba = [B substringWithRange:NSMakeRange(0,1)];
        NSString *bb = [B substringWithRange:NSMakeRange([B length]-1,1)];
        NSString *ca = [C substringWithRange:NSMakeRange(0,1)];
        NSString *answer = ([ab isEqualToString:ba] && [bb isEqualToString:ca])?@"YES":@"NO";
        
        NSFileHandle *fileHandle = [NSFileHandle fileHandleWithStandardOutput];
        [fileHandle writeData:[answer dataUsingEncoding:NSUTF8StringEncoding]];
        [fileHandle writeData:[@"\n" dataUsingEncoding:NSUTF8StringEncoding]];
        [fileHandle closeFile];
    }
    return 0;
}


Measured memory_bytes: 2652
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;


class Program
{
    static void Main(string[] args)
    {
        // 入力
        //var s = Console.ReadLine();
        long n = long.Parse(Console.ReadLine());
        string[] s = new string[n];
        for (long i = 0; i < n; i++)
        {
            s[i] = Console.ReadLine();
        }

        long ans = 0;
        for (long i = 0; i < n; i++)
        {
            var tmp = s[i].Replace("AB", "");
            if (tmp.Length < s[i].Length) ans += (s[i].Length - tmp.Length) / 2;
        }

        long a = 0;
        long b = 0;
        long x = 0;
        for (long i = 0; i < n; i++)
        {
            if (s[i][s[i].Length - 1] == 'A') a++;
            if (s[i][0] == 'B') b++;
            if (s[i][s[i].Length - 1] == 'A' && s[i][0] == 'B') x++;
        }

        if (a != 0 && a == b && b == x) ans += a - 1;
        else ans += Math.Min(a, b);

        // 出力
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 27864
#include <bits/stdc++.h>
using namespace std;
#define LL long int

int main(){
    LL a,b;

    cin >> a >> b;
    LL aa = a,bb = b;

    queue<LL> qa;
    queue<LL> qb;

    qa.push(1);
    qb.push(1);

    cerr << "a";
    for(LL i = 2; i <= sqrt(aa); ++i){//cerr << "c" << i << "v";
        if(a % i == 0){cerr << i << " ";
            qa.push(i);
            while(a % i == 0) a /= i;
        }
    }
    cerr << a;
    if(a != 1) qa.push(a);

    cerr << "\nb";
    for(LL i = 2; i <= sqrt(bb); ++i){
        if(b % i == 0){cerr << i << " ";
            qb.push(i);
            while(b % i == 0) b /= i;
        }
    }
    cerr << b;
    if(b != 1) qb.push(b);
    cerr << endl;

    LL ans = 0;

    while(!(qa.empty() || qb.empty())){
        if(qa.front() == qb.front()){
            //cerr << qa.front() << " ";
            ans++;
            qa.pop();
            qb.pop();
        }else{
            if(qa.front() < qb.front()){
                qa.pop();
            }else{
                qb.pop();
            }
        }
    }
    cerr << endl;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){
    char A;
    cin>>A;

    if(A=='A'){
        cout<<'T'<<endl;
    }else if (A=='T')
    {
        cout<<'A'<<endl;
    }else if (A=='C')
    {
        cout<<'G'<<endl;
    }else{
        cout<<'C'<<endl;
    }
    
    
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cassert>
#include <map>
#include <numeric>
#include <cstring>
#include <set>
#include <ctime>
#include <queue>

using namespace std;

const int INF = 1000000;
const int MAXN = 800;

char a[1 + MAXN][1 + MAXN];
int best[1 + MAXN][1 + MAXN];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main () {
    //ifstream cin("input.in");
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            best[i][j] = INF;
    queue<pair<int, int> > q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] + 1;
        for (int j = 1; j <= m; j++)
            if (a[i][j] == 'S') {
                q.push(make_pair(i, j));
                best[i][j] = 0;
            }
    }
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int x0 = x + dx[i], y0 = y + dy[i];
            if (x0 >= 1 && x0 <= n && y0 >= 1 && y0 <= m && a[x0][y0] != '#' && best[x0][y0] > best[x][y] + 1) {
                best[x0][y0] = best[x][y] + 1;
                q.push(make_pair(x0, y0));
            }
        }
    }
    int answer = INF;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (best[i][j] <= k) {
                int l = min(min(i - 1, n - i), min(j - 1, m - j));
                if (l == 0)
                    answer = 1;
                else
                    answer = min(answer, 1 + (l - 1) / k + 1);
            }
    cout << answer << "\n";
    return 0;
}





Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mpp make_pair
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main()
{

    ll n,x,t;
    cin>>n>>x>>t;
    if(n%x==0)
    {
        cout<<(n/x)*t<<endl;
    }
    else
    {
       cout<<((n/x)+1)*t<<endl;
    }

}


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

class Test
{
    public struct Data
    {
        public string suit;
        public int rank;
    }

    static void Main()
    {
        string[] ss;
        string su;
        int ra;
        List<Data> g = new List<Data>();

        int n = int.Parse(Console.ReadLine());
        for ( int i = 0; i < n; i++)
        {
            ss = Console.ReadLine().Split();
            su = ss[0];
            ra = int.Parse(ss[1]);

            g.Add(new Data { suit = su, rank = ra });
        }

        string m = "";
        for ( int i = 0; i < 4; i++)
        {
            switch (i)
            {
                case 0:m = "S";
                    break;
                case 1:m = "H";
                    break;
                case 2:m = "C";
                    break;
                case 3:m = "D";
                    break;

            }
            for (int j = 1; j <= 13; j++)
            {
                if (!g.Contains(new Data { suit = m, rank = j }))
                {
                    Console.WriteLine("{0} {1}", m, j);
                    continue;
                }
            }
        }
    }
}


Measured memory_bytes: 15984
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;

int bit_length(int x) {
    int len = 0;
    while ((1 << len) <= x) ++len;
    return len;
}

int main() {
    int n; cin >> n;
    multiset<int> se;
    while (n--) {
        int a; cin >> a; se.emplace(a);
    }
    int cnt = 0;
    while (!se.empty()) {
        int a = *se.rbegin();
        se.erase(--se.end());
        int b = (1 << bit_length(a)) - a;
        auto it = se.find(b);
        if (it == se.end()) continue;
        se.erase(it);
        cnt++;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 9600
#include"bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long INT;
double PI = 3.14159265;


const long long INF = 1LL << 60;

int main() {
    int n, a[200010] = {}, b;

    cin >> n;

    for (int i = 2; i <= n;i++) {
        cin >> b;
        a[b]++;
    }
    
    for (int i = 1; i <= n; i++)cout << a[i] << endl;

    return 0;
}

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

int main()
{
    int K,A,B;cin >> K >> A >>B;
    bool can=false;
    for (int i=A;i<B+1;i++)
    {
        if (i%K==0)
        {
            can=true;
            break;
        }
    }
    if (can) cout << "OK" << endl;
    else cout << "NG" << endl;
    return 0; 
}

Measured memory_bytes: 3572
//エラトステネスのふるいを使う
#include<iostream>
#include<cmath>

using namespace std;

int main(void){
	int i,min,so,low,high;
	double data[60000],max,cnt=0;

	//素数を配列に埋め込む
	for(i=2;i<60000;i++)
		data[i]=1;
	min=2;
	max=60000;
	while(1){
		if(sqrt(max)<min)	break;
		for(i=min;i<max;i++){
			if(i%min==0){
				data[i]=0;
			}
		}
		data[min]=1;
		for(i=min+1;i<60000;i++){
			if(data[i]==1){
				if(cnt==0)	min=i;
				else	max=i;
				cnt=1;
			}
		}
		cnt=0;
	}

	while(cin>>so){
		for(i=2;i<60000;i++){
			if(data[i]==1){
				if(so>i)	low=i;
				if(so<i){
					high=i;
					cnt=1;
				}
			}
			if(cnt==1)	break;
		}
		cout<<low<<' '<<high<<endl;
		cnt=0;
	}

	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<climits>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<stdio.h>
#include <string>
#include <complex>
#include <functional>
using namespace std;
typedef pair<int,int> P;
double dat[100][100];
int dp[6][1010];//動的計画法
int prime[10000001];
char str[1010][1010];
vector<pair<int,int> > pc[100001];
int ABS(int a){return max(a,-a);}
int main(){
	int n,k;
	long long ans;
	cin>>n>>k;
	ans=k;
	for(int i=1;i<n;i++){
		ans*=(k-1);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 4352
/* author :: eSeF */
using System;
class AC
{
    static void Main()
    {
        var ABC = Csin.Input<int, int, int>();
        if (ABC == (5, 5, 7) || ABC == (5, 7, 5) || ABC == (7, 5, 5))
        {
            Console.WriteLine("YES");
        }
        else
        {
            Console.WriteLine("NO");
        }

    }
}
/* for input */
static class Csin
{
    public static string[] StrArray() => Console.ReadLine().Split();
    public static string[] StrArray(char separator) => Console.ReadLine().Split(separator);

    private static T Conv<T>(string value) => (T)Convert.ChangeType(value, typeof(T));
    public static (T, U) ReadTuple<T, U>(string[] input) => (Conv<T>(input[0]), Conv<U>(input[1]));
    public static (T, U, V) ReadTuple<T, U, V>(string[] input) => (Conv<T>(input[0]), Conv<U>(input[1]), Conv<V>(input[2]));
    public static (T, U, V, W) ReadTuple<T, U, V, W>(string[] input) => (Conv<T>(input[0]), Conv<U>(input[1]), Conv<V>(input[2]), Conv<W>(input[3]));
    public static (T, U, V, W, X) ReadTuple<T, U, V, W, X>(string[] input) => (Conv<T>(input[0]), Conv<U>(input[1]), Conv<V>(input[2]), Conv<W>(input[3]), Conv<X>(input[4]));

    public static (T, U) Input<T, U>() => ReadTuple<T, U>(StrArray());
    public static (T, U, V) Input<T, U, V>() => ReadTuple<T, U, V>(StrArray());
    public static (T, U, V, W) Input<T, U, V, W>() => ReadTuple<T, U, V, W>(StrArray());
    public static (T, U, V, W, X) Input<T, U, V, W, X>() => ReadTuple<T, U, V, W, X>(StrArray());
}


Measured memory_bytes: 17904
let s = read_line ()

let k = "keyence"

let s_len = String.length s

let () =
  for i = 0 to s_len - 1 do
    for j = i to s_len - 1 do
      if (String.sub s 0 i) ^ (String.sub s j (s_len - j)) = "keyence" then begin
        print_endline "YES";
        exit 0
      end
    done
  done;
  print_endline "NO"

Measured memory_bytes: 2432
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define ull unsigned long long
#define N 100005
#define mod 1000000007
//#define mod 1e18
#define boost ios_base::sync_with_stdio(false);cin.tie(0)
#define prec(n) fixed<<setprecision(n)

#define mii map<int,int>
#define mll map<ll,ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi  first

#define se second
#define pb push_back
#define mp make_pair
#define pp pop_back
#define vii vector<int>
#define vll vector<ll>
#define vpii vector<pii>
#define vpll vector<pll>
#define all(c) c.begin(),c.end()
#define tr(it,c) for(it = c.begin() ; it!=c.end() ; it++)
int inf = INT_MAX ;
ll modulo(ll num,ll MOD=mod){ return ((num%MOD)+MOD)%MOD;} // for negative integer
ll power(ll b,ll e,ll MOD=mod){ll ans=1; while(e){if(e%2) ans=(ans*b)%MOD; b=(b*b)%MOD; e/=2;} return ans;}
ll inv(ll num,ll MOD=mod){ return power(modulo(num),MOD-2,MOD); }
ll gcd(ll a,ll b){ return ((b==0) ? a:gcd(b,a%b));}
int n;
int arr[22][22];
ll dp[(ll)1e7];

ll solve(int j,ll k){
	if(j == n){
		return 1;
	}
	
	if(dp[k]!=-1){
		return dp[k];
	}	
	
	ll ans = 0;
	for(int i = 0;i<n;i++){
		if(!((1<<i)&k)){
			if(arr[j][i]==1){
				ans = (ans + solve(j+1,(1<<i)|k))%mod;
			}
		}
	}
	
	dp[k] = ans;
	return ans;
}

int main(){
	boost;
	cin>>n;
	memset(dp,-1,sizeof(dp));
	
	for(int i = 0;i<n;i++){
		for(int j = 0;j<n;j++){
			cin>>arr[i][j];
		}
	}
	
	ll ans = solve(0,0);
	cout<<ans;
	return 0;
}



Measured memory_bytes: 81748
def get_i() #空白区切の入力を数値(整数)の配列で返す
  return gets.chomp.split(" ").map(&:to_i)
end
def get_f() #空白区切の入力を数値(実数)の配列で返す
  return gets.chomp.split(" ").map(&:to_f)
end
def get() #空白区切の入力を文字列の配列で返す
  return gets.chomp.split(" ")
end
def get_nsp() #入力されたものを一文字ずつに区切った文字列の配列で返す
  return gets.chomp.split("")
end
def yn_judge(bool,y="Yes",n="No") #boolに真偽を投げることで、trueならy、falseならnの値を出力する
  return bool ? y : n 
end
def array(size,n=1,init=nil) #nに配列の次元数、sizeに配列の大きさ、initに初期値を投げることでその配列を返す
  if n==1
    return Array.new(size){init}
  else
    return Array.new(n).map{Array.new(size){init}}
  end
end

n=gets.to_i
a=get_i
a.insert(0,0)
dis=array(n,1,0)
n.times do|i|
  dis[i]=(a[i+1]-a[i]).abs
end
sum=dis.inject(:+)+a[n].abs
for i in 1..n-1
  puts sum-dis[i-1]-dis[i]+(a[i+1]-a[i-1]).abs
end
puts sum-dis[n-1]-a[n].abs+a[n-1].abs

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

lli n;

int main(void){
	cin >> n;
	vector<lli> a(n);
	lli sum = 0;
	rep(i, n) cin >> a[i], sum+=a[i];
	lli s = 0;
	lli ans = 1e18;
	for(int i = 0; i < n-1; i++){
		s+=a[i];
		lli x = s;
		lli y = sum-s;
		ans = min(ans, abs(x-y));
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 4776
import itertools                                               
import sys                                                     
                                                               
                                                               
def solve(C):                                                  
    for cc, cn in itertools.combinations(C, 2):                
        for c_c, c_n in itertools.combinations(zip(cc, cn), 2):
            if c_c[0] + c_n[1] != c_c[1] + c_n[0]:             
                return "No"                                    
    else:                                                      
        return "Yes"                                           
                                                               
if __name__ == "__main__":                                     
    C = [list(map(int, input().split())) for _ in range(3)]    
    print(solve(C))                                            

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll> 
#define P pair<ll,ll>
#define rep(i,n) for(ll (i)=0; (i)<(n); ++(i))
#define print(a) cout << (a) << endl

ll n;
vector<lvector> G(n);
map<P,ll> cost;
lvector dist(n,0);

void dfs(ll v, ll d=0, ll p=-1) {
  dist[v]=d;
  for(ll u:G[v]) {
    if(u==p) continue;
    dfs(u,d+cost[P(u,v)],v);
  }
  return;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,u,v,w;cin>>n;
  G.resize(n); dist.resize(n);
  rep(i,n-1) {
    cin>>u>>v>>w;
    u--;v--;
    G[v].emplace_back(u);
    G[u].emplace_back(v);
    cost[P(u,v)]+=w;
    cost[P(v,u)]+=w;
  }
  dfs(0);
  rep(i,n) {
    if(dist[i]%2==0) print(0);
    else print(1);
  }
  return 0;
}

Measured memory_bytes: 23296
#include <stdio.h>

int main (void)
{
  int i, n, k, num = 1;

  scanf("%d", &n);
  scanf("%d", &k);

  for (i = 0; i < n; i++) {
    if (num*2 - num > k) {
      num += k;
    } else {
      num *= 2;
    }
  }
  printf("%d", num);

  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi 2*acos(0.0)
#define f first
#define s second
#define pb push_back
#define gap ' '
#define fastio {ios_base::sync_with_stdio(false);cin.tie(NULL);}
#define mod 1000000007

const int N=3005;
int n;
ll ara[N];
ll dp[N][N];
ll solve(int i,int l)
{
    if(i==n) return 0;
    int r=n-1-(i-l);
    if(dp[i][l]!=-1) return dp[i][l];
    dp[i][l]=max(ara[l]-solve(i+1,l+1),ara[r]-solve(i+1,l));
    return dp[i][l];
}
int main()
{
    fastio;
    cin>>n;
    for(int i=0;i<n;i++) cin>>ara[i];
    memset(dp,-1,sizeof dp);
    cout<<solve(0,0)<<endl;

}


Measured memory_bytes: 74364
import math
H = int(input())
if H%2==0:
  ans=0
  l=1
  while True:
    ans+=l
    H=H//2
    l*=2
    if H==0:
      print(ans);break
else:
  ans=0
  l=1
  while True:
    ans+=l
    H=math.floor(H//2)
    l*=2
    if H==0:
      print(ans);break

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

int N;

vector<int> A,B;
vector<vector<int>> Nary;
vector<vector<bool>> C;
vector<int>ans;


void paint(int tgt, int parent_color, int parent_index);


int main()
{

	cin >> N;

	Nary = vector<vector<int>>(N+1);
	A = vector<int>(N-1);
	B = vector<int>(N-1);
	ans = vector<int>(N - 1);

	int color = 0;

	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a;
		cin >> b;

		A[i] = a;
		B[i] = b;

		Nary[a].push_back(i);
		Nary[b].push_back(i);

		color = max((int)Nary[a].size(), color);
		color = max((int)Nary[b].size(), color);
	}

	C = vector<vector<bool>>(N,vector<bool>(color));

	paint(1,-1,-1);


	cout << color << endl;
	for (int i = 0; i < N - 1; i++) {
		cout << ans[i] << endl;
	}

	return 0;


}

void paint(int tgt,int parent_color,int parent_index)
{
	int c = 1;

	for (int i = 0; i < Nary[tgt].size(); i++) {
		int n = Nary[tgt][i];

		if (n == parent_index) { continue; }

		if (c == parent_color) { c++; }
		ans[n] = c;


		int child = A[n] == tgt ? B[n] : A[n];

		paint(child, c,n);

		c++;

	}

	return ;
}


Measured memory_bytes: 315772
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader bf =new BufferedReader(new InputStreamReader(System.in));
		String t;double v,y;
		while((t=bf.readLine())!=null){
			v=Double.parseDouble(t);
			y=(v*v/19.6+5)/5;
			System.out.println((int)Math.ceil(y));
		}
	}
}

Measured memory_bytes: 9336
def m():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    B = [0] * N
    B[0] = A[0]
    for i in range(1, N):
        B[i] = B[i - 1] + A[i]
    prob = 0
    for i in range(N - 1):
        if B[i] * 2 < A[i + 1]:
            prob = 0
            continue
        prob += 1
    return prob+1


print(m())


Measured memory_bytes: 63856
#include <iostream>

using namespace std;

int main(){

	int n,m,p;
		while(cin>>n>>m>>p){
			if(n==0&&m==0&&p==0)break;

				int *x;
				x = new int[n];
				int sum=0;
				for(int i=0;i<n;i++){
					cin>>x[i];
					sum += x[i]*100;
				}

				sum *= (100-p);

				if(x[m-1]==0){
					cout<<0<<endl;
				}
				else{
					cout<<sum/x[m-1]/100<<endl;
				}
			
		}
	return 0;
}

Measured memory_bytes: 1208
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AOJ
{
	class Program
	{
		static void Main(string[] args)
		{
			while (true)
			{
				var n = int.Parse(Console.ReadLine());
				if (n == 0) break;
				long[] a = new long[5000];
				long max, tmp;
				for (int i = 0; i < n; i++) a[i] = int.Parse(Console.ReadLine());
				max = a[0];
				tmp = 0;
				for (int i = 0; i < n; i++)
				{
					for (int j = i; j < n; j++)
					{
						tmp += a[j];
						if (max < tmp)
							max = tmp;
					}
					tmp = 0;
				}
				Console.WriteLine(max);
			}
		}
	}
}

Measured memory_bytes: 5920