akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    joushi = [0] * N
    for a in A:
        a -= 1
        joushi[a] += 1
    print("\n".join(map(str, joushi)))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N - 2 + 1)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()


Measured memory_bytes: 100508
#include<iostream>
#include<vector>
#include<utility>
#include<bitset>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

int main(){
	int n;
	cin >> n;
	vector<int> a;
	for(int i=0; i<n; i++){
		int ai;
		cin >> ai;
		a.push_back(ai);
	}
	sort(a.rbegin(), a.rend());
	int alice=0, bob=0;
	for(int i=0; i<n; i++){
		if(i%2)
			bob+=a[i];
		else
			alice+=a[i];
	}
	cout << alice-bob << '\n';
	return 0;
}

Measured memory_bytes: 256
MOD = 1000000007
H, W, K = map(int,input().split())
K -= 1

f_dic = {}
def f(x):
    if x in f_dic:
        return f_dic[x]
    elif x == 0:
        f_dic[0]=1
        return f_dic[0]
    elif x == 1:
        f_dic[1]=1
        return f_dic[1]
    else:
        f_dic[x] = f(x-1)+f(x-2)
        return f_dic[x]


if W == 1:
    print(1)

else:
    dp = [[0 for j in range(W)] for i in range(H+1)]
    dp[0][0] = 1
    for i in range(H):
        dp[i+1][0] += f(W-1)*dp[i][0]
        dp[i+1][1] += f(W-2)*dp[i][0]
        for j in range(1,W-1):
            dp[i+1][j-1] += f(j-1)*f(W-j-1)*dp[i][j]
            dp[i+1][j]   += f(j)  *f(W-j-1)*dp[i][j]
            dp[i+1][j+1] += f(j)  *f(W-j-2)*dp[i][j]
        dp[i+1][W-2] += f(W-2)*dp[i][W-1]
        dp[i+1][W-1] += f(W-1)*dp[i][W-1]
        for j in range(W):
            dp[i+1][j] %= MOD
    print(dp[H][K])


Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <stack>
#include <map>
const int MOD = 1e9+7;
#define PI 3.14159265359
typedef long long ll;
using namespace std;



int main(){
	int n;
	cin >> n;
	map<string, int> mp;
	for (int i = 0; i < n; i++){
		string s;
		cin >> s;
		mp[s]++;
	}
	cout << "AC x " << mp["AC"] << endl;
	cout << "WA x " << mp["WA"] << endl;
	cout << "TLE x " << mp["TLE"] << endl;
	cout << "RE x " << mp["RE"] << endl;

	return 0;
}

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

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

H_list = H_list[::-1]
pre_h = H_list[0]

c = 0
max_c = 0
for h in H_list[1:]:
    if pre_h <= h:
        c += 1
    else:
        c = 0
    pre_h = h
    if max_c < c:
        max_c = c
print(max_c)

Measured memory_bytes: 14224
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;
uint64_t gcd(uint64_t a, uint64_t b);
uint64_t lcm(uint64_t a, uint64_t b);

template <typename T>
static inline void ArrayInput(vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cin >> *itr;
}

template <typename T>
static inline void ArrayPut(const vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cout << *itr << " ";
  cout << endl;
}

bool Sec_compare(pair<uint64_t, uint64_t> a, pair<uint64_t, uint64_t> b) {
  if (a.second != b.second) {
    return a.second < b.second;
  } else {
    return a.first < b.first;
  }
}

int main() {
  uint64_t A, B;
  cin >> A >> B;
  cout << lcm(A, B);

  return 0;
}

uint64_t gcd(uint64_t a, uint64_t b) {
  if (a < b) {
    a ^= b;
    b ^= a;
    a ^= b;
  }

  return b ? gcd(b, a % b) : a;
}

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

Measured memory_bytes: 256
package main

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

type pair struct {
	a int
	b int
}
var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)
	N := nextInt()
	graph := make([][]int, N+1)
	for i := 1; i < N+1; i++ {
		graph[i] = make([]int, 0, N-1)
		for j := 0; j < N-1; j++ {
			graph[i] = append(graph[i], nextInt())
		}
	}
	queue := make([]pair, 0)
	for i := 1; i < N; i++ {
		if graph[graph[i][0]][0] == i && i < graph[i][0] {
			queue = append(queue, pair{i, graph[i][0]})
		}
	}
	ans := 0
	for cnt := 0; cnt < N*(N-1)/2; ans++ {
		if len(queue) == 0 {
			fmt.Println("-1")
			return
		}
		for b := len(queue); b > 0; b-- {
			n := queue[0].a
			graph[n] = graph[n][1:]
			if len(graph[n]) != 0 && graph[graph[n][0]][0] == n {
				queue = append(queue, pair{n, graph[n][0]})
			}
			n = queue[0].b
			graph[n] = graph[n][1:]
			if len(graph[n]) != 0 && graph[graph[n][0]][0] == n {
				queue = append(queue, pair{n, graph[n][0]})
			}
			queue = queue[1:]
			cnt++
		}
	}
	fmt.Printf("%d\n", ans)
}


Measured memory_bytes: 20352
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
static class Program{
	const int mod=1000000007;
	static void Main(){
		Sc sc=new Sc();
		int n=sc.I;
		int[] a=sc.Ia2;
		long[] r=new long[n+1];
		var hs=new Dictionary<long,int>();
		long ans=0;
		hs.Add(0,1);
		for(int i = 1;i<=n;i++) {
			r[i]=r[i-1]+a[i];
			if(hs.ContainsKey(r[i])){ans+=hs[r[i]];hs[r[i]]++;}
			else{hs.Add(r[i],1);}
		}
		Console.WriteLine("{0}",ans);
	}
}

public class Sc{
	public int I{get{return int.Parse(Console.ReadLine());}}
	public long L{get{return long.Parse(Console.ReadLine());}}
	public double D{get{return double.Parse(Console.ReadLine());}}
	public string S{get{return Console.ReadLine();}}
	public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
	public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()).Split(),int.Parse);}}
	public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
	public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()).Split(),long.Parse);}}
	public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
	public string[] Sa{get{return Console.ReadLine().Split();}}
}


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

int main() {
  int n;
  cin >>n;
  if (n<1200){
  	  cout<<"ABC"<<endl;
  }else if(n<2800){
    cout<<"ARC"<<endl;
  }else{
    cout<<"AGC"<<endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using P = pair<lint, lint>;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
constexpr int MOD = 1000000007;
constexpr int INF = 2147483647;
void yes(bool expr) {
  cout << (expr ? "Yes" : "No") << "\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int a;
    cin >> a;
    cout << (a + a*a + a*a*a) << endl;
}

Measured memory_bytes: 3632
# ABC067D - Fennec VS. Snuke (ARC078D)
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(v: int, x: int, d: "List[int]") -> None:
    d[v] = x
    for u in G[v]:
        if not d[u]:
            dfs(u, x + 1, d)


def main():
    global G, DB, DW
    N = int(input())
    E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    G = [[] for _ in range(N + 1)]
    for v, u in E:
        G[v] += [u]
        G[u] += [v]
    DB, DW = [0] * (N + 1), [0] * (N + 1)
    dfs(1, 1, DB), dfs(N, 1, DW)
    b, w = 0, 0
    for i, j in zip(DB[1:], DW[1:]):
        if i <= j:
            b += 1
        else:
            w += 1
    flg = b > w
    print("Fennec" if flg else "Snuke")


if __name__ == "__main__":
    main()

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

int find_root(vector<int> &parent, int i){
    vector<int> path_nodes;
    int temp=i;
    while(true){
        if(parent[temp] == temp){
            for(int k=0;k<path_nodes.size();k++){
                parent.at(path_nodes.at(k))=temp;
            }
            return temp;
        }else{
            path_nodes.push_back(temp);
            temp=parent[temp];
        }
    }
}

void merge_trees(vector<int> &parent,int i, int j){
    int i_root = find_root(parent, i);
    int j_root = find_root(parent, j);
    if(i_root==j_root){
        return; // do nothing
    }else{
        if((i+j)%2==0){
        parent.at(i_root) = j_root;
        }else{
        parent.at(j_root) = i_root;
        }
        return;
    }

}
int main(){
    int N, M;
    cin>>N>>M;
    vector<int> P(N+1);
    vector<int> parent(N+1);
    for (int i=1;i<N+1;i++){
        cin>>P.at(i);
        parent.at(i) = i;
    }

    for (int i=0;i<M;i++){
        int x,y;
        cin>>x>>y;
        merge_trees(parent,x,y);
    }

    int tot_num=0;
    for (int i=1;i<N+1;i++){
        if(find_root(parent,i)==find_root(parent,P.at(i))){
            tot_num+=1;
        }
    }
    cout<<tot_num<<endl;



}

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

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

	int a=0, b=0, c=0, x, y, z;
	for (int i = K; i < N; i++) {
		if (v.at(i) > v.at(i-K)) std::cout << "Yes" << '\n';
		else std::cout << "No" << '\n';
	}
}


Measured memory_bytes: 4044
#include <bits/stdc++.h>
using namespace std;
#define uint unsigned int
#define llong long long int
#define ullong unsigned long long int
const static llong MOD = 1000000000 + 7;

bool judge(int a, int b, int c) {
    if ((a % 2 == 1) && (b % 2 == 1) && (c % 2 == 1)) {
        return true;
    }
    if ((a % 2 == 0) && (b % 2 == 0) && (c % 2 == 0)) {
        return true;
    }

    return false;
}

int main (int argc, char *argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int a, b, c;
    cin >> a >> b >> c;
    if ((a % 2 == 1) || (b % 2 == 1) || (c % 2 == 1)) {
        cout << 0 << endl;
        return 0;
    }
    if ((a == b) &&  (b == c) && (c == a)) {
        cout << -1 << endl;
        return 0;
    }

    int i = 0;
    while (1) {
        a /= 2;
        b /= 2;
        c /= 2;
        ++i;
        if (judge(a, b, c)) {
            int tmp1 = a, tmp2 = b, tmp3 = c;
            a = tmp2 + tmp3;
            b = tmp1 + tmp3;
            c = tmp1 + tmp2;
        } else {
            break;
        }
    }

    cout << i << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define lli long long int
#define L(i,s,e) for(lli i=s;i<=e;i++)
using namespace std;
lli r,c,k;
lli ip[7][7];
lli J(lli R,lli C)
{
	set<lli> h,w;
	lli k=0;
	while(R!=0)
	{
		if(R%2!=0)
		h.insert(k);
		R/=2;
		k++;
	}
	k=0;
	while(C!=0)
	{
		if(C%2!=0)
		w.insert(k);
		C/=2;
		k++;
	}
	lli ttl=0;
	L(i,0,r-1)
	{
		L(j,0,c-1)
		{
			if((h.find(i)==h.end()&&w.find(j)==w.end())&&ip[i][j])
			ttl++;
		}
	}
	return ttl;
}
int main()
{
	cin>>r>>c>>k;
	L(i,0,r-1)
	{
		string a;
		cin>>a;
		L(j,0,c-1)
		ip[i][j]=a[j]=='.'?0:1;
	}
	lli R=pow(2,r)-1,C=pow(2,c)-1,ans=0;
	L(i,0,R)
	{
		L(j,0,C)
		{
			if(J(i,j)==k)
			ans++;
		}
	}
	cout<<ans<<endl;
}

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

int main() {
	v(n); v(a); v(b);
	cout << (n - a + 1) * (n - b + 1) << endl;
}

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

using namespace std;

vector<int> a;

int binarySerch(int key){
    int left = 0;
    int right = (int)a.size() - 2;
    int mid;
    while (right >= left)
    {
        mid = left + (right - left) / 2;
        if (a[mid] == key)
        {
            return 0;
        }
        else if (a[mid] > key) right = mid - 1;
        else if (a[mid] < key) left = mid + 1;
        
    }
    return 1;
    
}

int main(int argc, char const *argv[])
{
    int s;
    cin >> s;
    a.emplace_back(s);
    int ans = 0;
    int key;
    do
    {
        ans++;
        if (a[ans - 1] % 2 == 0)
        {
            a.emplace_back(a[ans - 1] / 2);
        }else
        {
            a.emplace_back(3 * a[ans - 1] + 1);
        }
        key = a[ans];
        sort(a.begin(), a.end() - 1);
        
    } while (binarySerch(key) == 1);
    
    cout << ans + 1 << endl;

    return 0;
}

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

using namespace std;

#define _for(i,j,N) for(int i = (j);i < (N);i++)
#define _rep(i,j,N) for(int i = (j);i <= (N);i++)
#define ALL(x) x.begin(),x.end()
#define pb push_back
#define mk make_pair

typedef long long LL;
typedef pair<int,int> Interval;

template<typename T>
ostream& operator<<(ostream& os,const vector<T>& v) {
    _for(i,0,v.size()) os << v[i] << " ";
    return os;
}

template<typename T>
ostream& operator<<(ostream& os,const set<T>& v){
    for(typename set<T>::iterator it = v.begin();it != v.end();it++)
    os << *it <<" ";
    return os;
}

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& v){
    os << v.first <<" "<<v.second<<endl;
    return os;
}
int X,A;
int main()
{
    cin >> X >> A;
    if(X  < A) printf("0\n");
    else printf("10\n");

    return 0;
}


Measured memory_bytes: 256
/*

@author hasankamal

*/

#include <iostream>
#include <vector>
using namespace std;

typedef long long int ll;
typedef vector<ll> vi;

ll absol(ll x){
	return x < 0 ? -1 * x : x;
}

int main(){

	ios::sync_with_stdio(false);
	cin.tie(NULL);

	ll n;
	cin >> n;
	vi a(n);
	for(ll i = 0; i < n; i++)
		cin >> a[i];

	for(ll i = 0; i < n; i++){
		if(a[i] > i){
			cout << "-1";
			return 0;
		}
	}

	for(ll i = 1; i < n; i++){
		if(a[i - 1] < a[i] - 1){
			cout << "-1";
			return 0;
		}
	}

	ll ans = 0;
	ll i = n - 1;
	while(i > 0){
		if(a[i - 1] >= a[i]){
			ans += a[i];
			i -= 1;
		}else{
			ans += a[i];
			while(i - 1 >= 0 && a[i - 1] == a[i] - 1)
				i -= 1;
			if(i < 0)
				break;
			i -= 1;
		}
	}
	cout << ans;

	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    int n, x;
    cin >> n >> x;

    int i;
    vector<int> l(n+1);
    for(i=1; i<=n; i++) {
        cin >> l.at(i);
    }

    int d = 0;
    int cnt = 1;
    for(i=1; i<=n; i++) {
        if(d + l[i] > x)
            break;
        else {
            d += l[i];
            cnt++;
        }
    }
    cout << cnt << endl;

    return 0;
}

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO ?????????????????????????????????????????????
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int pasta = Integer.MAX_VALUE;
		int drink = Integer.MAX_VALUE;
		for(int i = 0; i < 3; i++){
			int tmp = Integer.parseInt(br.readLine());
			if(tmp < pasta){
				pasta = tmp;
			}
		}
		
		for(int i = 0; i < 2; i++){
			int tmp = Integer.parseInt(br.readLine());
			if(tmp < drink){
				drink = tmp;
			}
		}
		
		System.out.println(pasta + drink - 50);
	}

}

Measured memory_bytes: 24280
#include <iostream>
#include <string>
 
using namespace std;
 
int main (void) {
  int n, a[100], b[100], sabun, temp;
  string mes;
  char ch;
 
  while(1) {
    cin >> n;
    if(n == 0) break;
 
    cin >> mes;
 
    for(int i = 0; i < n; i++) {
      cin >> a[i] >> b[i];
      a[i]--; b[i]--;
    }
 
    // decode
    for(int i = n-1; i >= 0; i--) {
      // susumeru
      sabun = (b[i] - a[i])%26;
 
      if(mes[a[i]] + sabun > 'z') {
    mes[a[i]] = 'a' + (mes[a[i]] + sabun - 1 - 'z');
      } else {
    mes[a[i]] += sabun;
      }
 
      if(mes[b[i]] + sabun > 'z') {
    mes[b[i]] = 'a' + (mes[b[i]] + sabun - 1 - 'z');
      } else {
    mes[b[i]] += sabun;
      }
 
      // change
      ch = mes[a[i]];
      mes[a[i]] = mes[b[i]];
      mes[b[i]] = ch;
    }
 
    cout << mes << endl;
  }
  return 0;
}

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

using namespace std;

int a[510][510],c[250250][4];
int h,w;


int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>h>>w;
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            cin>>a[i][j];
        }
    }
    int ans=0;
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w-1;j++)
        {
            if(a[i][j]%2==1)
            {
                c[ans][0]=i;
                c[ans][1]=j;
                c[ans][2]=i;
                c[ans][3]=j+1;
                ans++;
                a[i][j+1]++;
            }
        }
    }
    for(int i=0;i<h-1;i++)
    {
        if(a[i][w-1]%2==1)
        {
            c[ans][0]=i;
            c[ans][1]=w-1;
            c[ans][2]=i+1;
            c[ans][3]=w-1;
            ans++;
            a[i+1][w-1]++;
        }
    }
    cout<<ans<<endl;
    for(int i=0;i<ans;i++)
    {
        cout << c[i][0] + 1 << " " << c[i][1] + 1 << " " << c[i][2] + 1 << " " << c[i][3] + 1 << endl;
    }
    return 0;
}

Measured memory_bytes: 6912
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;

#define INF 1010001000
#define EPS 1e-10
#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back

typedef pair<int, int> i_i;
typedef long long int llong;
typedef pair<llong, llong> ll_ll;
typedef struct edge {int f, t;}Edge;


int main()
{
    int k, s;
    cin >> k >> s;
    llong ret = 0;
    for (int i = 0; i <= k; i++) {
        for (int j = i; j <= k; j++) {
            for (int l = j; l <= k; l++) {
                if (i + j + l == s) {
                    if (i == j && j == l) {
                        ret++;
                    } else if (i == j || j == l || i == l) {
                        ret += 3;
                    } else {
                        ret += 6;
                    }
                }
            }
        }
    }
    cout << ret << endl;


    return 0;
}


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

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if (a < b)
    {
        if (c < a)
        {
            cout << c << " " << a << " " << b << "\n";
        }
        else if (b < c)
        {
            cout << a << " " << b << " " << c << "\n";
        }
        else
        {
            cout << a << " " << c << " " << b << "\n";
        }
    }
    else if (b < a)
    {
        if (c < b)
        {
            cout << c << " " << b << " " << a << "\n";
        }
        else if (a < c)
        {
            cout << b << " " << a << " " << c << "\n";
        }
        else
        {
            cout << b << " " << c << " " << a << "\n";
        }
    }
    else
    {
        if (c < a)
        {
            cout << c << " " << a << " " << b << "\n";
        }
        else
        {
            cout << a << " " << b << " " << c << "\n";
        }
    }
}


Measured memory_bytes: 3088
from collections import deque
S=input()
Q=int(input())
front=deque()
back=deque()

reverse=False
for i in range(Q):
  ins=input()
  if len(ins)==1:
    if reverse:
      reverse=False
    else:
      reverse=True
  else:
    q,f,c=map(lambda x: x, ins.split())
    
    if f=="1":
      if reverse:
        back.append(c)
        
      else:
        front.appendleft(c)
        
    else:
      if reverse:
        front.appendleft(c)
      else:
        back.append(c)
        
back=list(back)
front=list(front)
if reverse:
  back=back[::-1]
  front=front[::-1]
  S=list(S)[::-1]
  print("".join(back)+"".join(S) +"".join(front))
else:
  print("".join(front)+S+"".join(back))
  
#print(reverse)
#print(front, back)

Measured memory_bytes: 6900
#include<bits/stdc++.h>
using namespace std;
int n;
int minCost(int ind, vector<int> &h, vector<int> &dp) {
    if (ind == n-1) {
        return 0;
    }
    if (dp[ind] != -1) {
        return dp[ind];
    }
    int costL = abs(h[ind]-h[ind+1]) + minCost(ind+1, h, dp);
    int costR = INT_MAX;
    if (ind+2<n) {
        costR = abs(h[ind]-h[ind+2]) + minCost(ind+2, h, dp);
    }
    return dp[ind] = min(costL, costR);
}
int main() {
    cin>>n;
    vector<int> h(n);
    vector<int> dp(n, -1);
    for (int i=0;i<n;i++) cin>>h[i];
    cout<<minCost(0, h, dp);
}


Measured memory_bytes: 10328
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

int main() {
	ll n, w, x = 0;
	cin >> n;
	w = n;
	while(0 < w) {
		x += w % 10;
		w /= 10;
	}

	if (n % x == 0) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

ll gcd(ll x, ll y) {
    if(y == 0) {
        return x;
    }
    return gcd(y, x%y);
}

ll lcm1(ll x, ll y) {
    return x/gcd(x, y)*y;
}

ll LCM(vl &v) {  // vの全要素のlcm
    ll res = 1;
    rep(i, v.size()) {
        res = lcm1(res, v[i]);
    }
    return res;
}
 
int main() {
    ll n, m;
    cin >> n >> m;

    vl a(n);
    rep(i, n) {
        cin >> a[i];
        a[i] /= 2;
    }

    /*ll u = 0;
    while(b[0]%2 == 0) {
        b[0] /= 2;
        u++;
    }
    exrep(i, 1, n-1) {
        ll x = 0;
        while(b[i]%2 == 0) {
            b[i] /= 2;
            x++;
        }
        if(u != x) {
            out(0);
            re0;
        }
    }*/

    ll lcm = LCM(a);
    rep(i, n) {
        if((lcm/a[i])%2 == 0) {
            out(0);
            re0;
        }
    }

    ll ans = m/(2*lcm);
    if(m%(2*lcm) >= lcm) {
        ans++;
    }
    
    out(ans);
    re0;
}

Measured memory_bytes: 1152
mod = 10**9+7
n,k = map(int, input().split())
a = list(map(int, input().split()))
b = [0]*2001
for i in a:
    b[i] += 1
for i in range(2000):
    b[i+1] += b[i]

ans = 0
for i in range(n):
    c = 0
    for j in range(i+1, n):
        if a[i] > a[j]:
            c += 1
    c *= k
    ans += (n-b[a[i]]) * k*(k-1)//2 % mod
    ans += c
    ans %= mod
print(ans)

Measured memory_bytes: 42220
#!/usr/bin/env python3
#ABC117 C

n,m = map(int,input().split())
x = list(map(int,input().split()))
x.sort()
#print(x)
if n >= m:
    print(0)
    quit()
y = [x[i+1]-x[i] for i in range(m-1)]
y.sort()
y.reverse()
#print(y)
print(sum(y[n-1:]))


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

//template<class T, size_t N> 
//size_t countof(const T (&array)[N]) { return N; }

int main() {
  int N;
  cin >> N;
  long long int a[N], b[N];

  for (int i=0; i < N; i++ ){
    cin >> a[i] >> b[i];
  }

  //  sort(a, a+N);
  //  sort(b, b+N);

  //  int ans=0;
  long long int sum=0;
  long long int min_tozan =INT_MAX;
  int flag=0;
  for (int i=0; i < N; i++ ){
    /*    if(a[i] <= b[i]){
      ans += a[i];
    }
    else{*/
    if(a[i] > b[i]){ 
      min_tozan =min(min_tozan, b[i]);
      flag=1;
    }
    sum += a[i];
  }
  
  if(flag==0){
    cout << 0 << endl;
    return 0;
  }
  else{
    cout << (sum - min_tozan) << endl;
  }

}


Measured memory_bytes: 512
//Created by Kira

#include<bits/stdc++.h>
using namespace std;

#define IOS cin.sync_with_stdio(0);cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pii pair<int,int> 
#define pb push_back
#define vi vector<int> 
using ll = long long;

const int mod = 1e9 + 7;
const int N = 2e5+10;

int n,k,c, L[N], R[N];

char s[N];

int main(){
   IOS

   cin>>n>>k>>c;

   int r = 1, i;


   for(i = 1; i <= n ; i++)cin>>s[i];
	
	
   for(i = 1; i <= n and r <= k; i++){
	   if(s[i] == 'o'){
		   L[r++] = i;
			i += c;
	   }
   }
	
   for(i = n, r = k; i >= 1 and r >= 1; --i){
	   if(s[i] == 'o'){
		   R[r--] = i;
		   i -= c;
	   }
   }

   for(int i = 1; i <= k; i++){
	   if(L[i] == R[i]){
		   cout<<L[i]<<"\n";
	   }
   }


}



Measured memory_bytes: 3328
import std.algorithm, std.array, std.container, std.range, std.bitmanip;
import std.numeric, std.math, std.bigint, std.random, core.bitop;
import std.string, std.conv, std.stdio, std.typecons;

void main()
{
  auto s = readln.chomp.to!int;
  writeln(s / (60 * 60), ":", s % (60 * 60) / 60, ":", s % 60);
}

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

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
constexpr int mod = 1e9 + 7;

struct mint {
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint &operator-=(const mint a) {
    if ((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint &operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res -= a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1) a *= *this;
    return a;
  }
  mint inv() const { return pow(mod - 2); }
  mint &operator/=(const mint a) { return (*this) *= a.inv(); }
  mint operator/(const mint a) const {
    mint res(*this);
    return res /= a;
  }
  friend ostream &operator<<(ostream &os, const mint &a) { return (os << a.x); }
};
struct combination {
  vector<mint> fact, ifact;
  combination(int n) : fact(n + 1), ifact(n + 1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * ifact[k] * ifact[n - k];
  }
};

vector<vector<int>> ship;
vector<bool> visited;

bool dfs(int s, int d, int c) {
  if (s == d) return true;

  if (visited[s]) return false;

  if (c >= 2) return false;

  visited[s] = true;

  vector<int> _ship = ship[s];

  for (auto it = _ship.cbegin(); it != _ship.cend(); ++it) {
    if (dfs(*it, d, c + 1)) return true;
  }

  return false;
}

int main() {
  int n, m;
  cin >> n >> m;
  ship = vector<vector<int>>(n + 1);
  visited = vector<bool>(n + 1, false);

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

    ship[a].push_back(b);
    ship[b].push_back(a);
  }

  if (dfs(1, n, 0))
    cout << "POSSIBLE" << endl;
  else
    cout << "IMPOSSIBLE" << endl;
}


Measured memory_bytes: 12400
var
  n,m,i,j,s,x,k:longint;
  a,b,c,d:array[0..70] of longint;
begin
  readln(n,m);
  for i:=1 to n do readln(a[i],b[i]);
  for i:=1 to m do readln(c[i],d[i]);
  for i:=1 to n do
    begin
      s:=1000000000;
      for j:=1 to m do
        begin
          x:=abs(a[i]-c[j])+abs(b[i]-d[j]);
          if x<s then begin s:=x;k:=j;end;
        end;
      writeln(k);
    end;
end.

Measured memory_bytes: 128
#include<bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
int main(){
  int H,W,i,j,a;scanf("%d%d",&H,&W);
  bool odd[H][W];
  for(i=0;i<H;i++){
    for(j=0;j<W;j++){
      scanf("%d",&a);
      odd[i][j] = a&1;
    }
  }
  bool coin = false;vector<pair<pair<int,int>,pair<int,int>>> v;
  i = 0;j = 0;int ni,nj;
  while(true){
    if((!(i&1)) && j+1 == W){
      ni = i+1;nj = j;
    }
    else if(i&1 && j == 0){
      ni = i+1;nj = j;
    }
    else if(!(i&1)){
      ni = i;nj = j+1;
    }
    else{
      ni = i;nj = j-1;
    }
    if(ni == H) break;
    if(odd[i][j]){
      if(coin == false){
        coin = true;
        v.push_back(make_pair(make_pair(i,j),make_pair(ni,nj)));
      }
      else{
        coin = false;
      }
    }
    else{
      if(coin == true){
        v.push_back(make_pair(make_pair(i,j),make_pair(ni,nj)));
      }
    }
    i = ni;j = nj;
  }
  printf("%d\n",v.size());
  for(i=0;i<v.size();i++) printf("%d %d %d %d\n",v[i].first.first+1,v[i].first.second+1,v[i].second.first+1,v[i].second.second+1);
}

Measured memory_bytes: 5504
#include <iostream>
#include <fstream>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-6;
const ll mod=1e9+7;
const vi emp;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,-0};
const int DX[8]={-1,-1,-1,0,0,1,1,1},DY[8]={1,0,-1,1,-1,1,0,-1};

int n,q;

int main(){
	cin>>n>>q;
	vb a(n);
	int I=0;
	a[0]=1;
	a[1]=1;
	for(int i=0;i<q;i++){
		int A,B;
		cin>>A>>B;
		A--;B--;
		swap(a[A],a[B]);
		if(I==A) I=B;
		else if(I==B) I=A;
		if(I-1>=0) a[I-1]=1;
		if(I+1<n) a[I+1]=1;
	}
	int ans=0;
	for(int i=0;i<n;i++) if(a[i]) ans++;
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int ans[15];
int end1=0x3f3f3f3f;
int c[15];
int a[15][15];
int main()
{
    int n,m,x;cin>>n>>m>>x;
    for(int i=1;i<=n;i++)
    {
    	cin>>c[i];
    	for(int j=1;j<=m;j++)
    	{
    		cin>>a[i][j];
		}
	}
    for(int i=0;i<(1<<n);i++) //´Ó0¡«2^n-1¸ö×´Ì¬
    {
    	int hua=0;
        for(int j=0;j<n;j++) //±éÀú¶þ½øÖÆµÄÃ¿Ò»Î»
        {
            if(i&(1<<j))//ÅÐ¶Ï¶þ½øÖÆµÚjÎ»ÊÇ·ñ´æÔÚ
            {
                hua+=c[j+1];
                for(int k=1;k<=m;k++)
                {
                	ans[k]+=a[j+1][k];
				}
            }
        }
        int flag=1;
        for(int k=1;k<=m;k++)
        {
        	if(ans[k]<x)
        	{
        		flag=0;
			}
		}
		if(flag==1)
		{
			end1=min(end1,hua);
		}
		memset(ans,0,sizeof(ans));
        //cout<<endl;
    }
    if(end1==0x3f3f3f3f)
	{
		cout<<"-1";
	}else cout<<end1;
}

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

const double PI = 3.14159265358979323846;
//using namespace boost::multiprecision;
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 1e15;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

std::istream &operator>>(std::istream &in, set<int> &o) {
    ll a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
const int mod = 1000000007;
//const ll mod = 1e10;
typedef priority_queue<long long, vector<long long>, greater<long long> > PQ_ASK;

class CumulativeSum {
    vector<ll> numbers;
    vector<ll> sums;

public:
    CumulativeSum(int n) {
        numbers.resize(n);
        sums.resize(n);
    }

    void set(int i, ll value) {
        numbers[i] = value;
    }

    ll getSum(int i) {
        if (i == -1) return 0;
        if (i == sums.size()) return 0;
        return sums[i];
    }

    ll getSectionSum(int start, int end) {
        return getSum(end) - getSum(start - 1);
    }

    void calculate() {
        for (int i = 0; i < numbers.size(); i++) {
            sums[i] = getSum(i - 1) + numbers[i];
        }
    }

};


int main() {
    int n;
    cin >> n;
    vector<ll> creatures(n);
    rep(i, n) cin >> creatures[i];
    sort(creatures.begin(), creatures.end());

    CumulativeSum cs(n);
    rep(i, n) cs.set(i, creatures[i]);
    cs.calculate();

    int r = 0;
    rep(i, n - 1) {
        ll sum = cs.getSum(i);
        ll border = sum * 2;
        ll next_creature = creatures[i + 1];
        if (border < next_creature) {
            r = i + 1;
        }
    }
    cout << n - r << endl;

}

Measured memory_bytes: 2560
import java.util.Scanner;

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

    int n = sc.nextInt();
    int a[] = new int [n];

    for(int k=0; k<n; k++){
      a[k]=sc.nextInt();
    }

    for (int k=n-1; k>=0; k--){
      if(k==0)System.out.print(a[k]);
      else System.out.print(a[k]+" ");
    }
    System.out.printf("\n");
  }
}



Measured memory_bytes: 26220
using System;

public class MatrixMultiplication
{
    //n??m ????????? A ??¨ m??l ????????? B ?????\??????????????????????????§?????? n??l ????????? C ???????????????
    static void Main(string[] args)
    {
        /*---??£?¨???¨---*/
        string[] buffer;
        int[] elementNum = new int[3];
        int highIndex;
        int widthIndex;
        int caluculationCount;
        long sum;
        /*---??£?¨???¨---*/

        /*????´???°???????????????????????¨???????¬???????????????????*/
        buffer = Console.ReadLine().Split(' ');
        elementNum[0] = int.Parse(buffer[0]);
        elementNum[1] = int.Parse(buffer[1]);
        elementNum[2] = int.Parse(buffer[2]);

        int[,] aMatrix = new int[elementNum[0], elementNum[1]];
        int[,] bMatrix = new int[elementNum[2], elementNum[1]];

        /*???????????????*/
        //A???????????????
        for(highIndex = 0; highIndex < elementNum[0]; highIndex++)
        {
            buffer = Console.ReadLine().Split(' ');
            for (widthIndex = 0; widthIndex < elementNum[1]; widthIndex++)
            {
                aMatrix[highIndex, widthIndex] = int.Parse(buffer[widthIndex]);
            }
        }
        //B???????????????
        for (highIndex = 0; highIndex < elementNum[1]; highIndex++)
        {
            buffer = Console.ReadLine().Split(' ');
            for (widthIndex = 0; widthIndex < elementNum[2]; widthIndex++)
            {
                bMatrix[widthIndex, highIndex] = int.Parse(buffer[widthIndex]);
            }
        }

        /*?¨????????????¨???*/
        for(highIndex = 0; highIndex < elementNum[0]; highIndex++)
        {
            for (caluculationCount = 0; caluculationCount < elementNum[2]; caluculationCount++)
            {
                sum = 0;
                for (widthIndex = 0; widthIndex < elementNum[1]; widthIndex++)
                {
                    sum += aMatrix[highIndex, widthIndex] * bMatrix[caluculationCount, widthIndex];
                }

                if (caluculationCount < (elementNum[2] - 1))
                    Console.Write("{0} ", sum);
                else
                    Console.WriteLine("{0}", sum);
            }
        }
    }
}

Measured memory_bytes: 9364
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <cassert>
#include <complex>
#include <iomanip>
#include <random>

using namespace std;

typedef long long ll;
#define int ll

const int M = 998244353;
#define msum(a, b) ((a) + (b) >= M ? (a) + (b) - M : (a) + (b))
#define msub(a, b) ((a) - (b) < 0 ? (a) - (b) + M : (a) - (b))
#define mmult(a, b) (((a) * (b)) % M)

typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define mmin(a, b) a = min(a, (b))
#define mmax(a, b) a = max(a, (b))
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define SZ(a) ((int)(a).size())
#define watch(x) cout << (#x) << " = " << (x) << endl;

const double PI = 2 * acos(0.0);
const int oo = 1e9 + 100;
const string DIGITS = "0123456789";
const string ALPH = "abcdefghijklmnopqrstuvwxyz";


#define N 300001

int gcd(int a, int b)
{
	while (a)
	{
		if (a < b)
			swap(a, b);
		a %= b;
	}
	return b;
}


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

	int n, k;
	cin >> n >> k;
	vi a(n);
	cin >> a[0];
	int u = a[0];
	bool flag = false;
	for (int i = 1; i < n; i++)
	{
		cin >> a[i];
		u = gcd(a[i], u);
	}
	sort(ALL(a));
	if (k <= a[n - 1] && k % u == 0)
		cout << "POSSIBLE";
	else
		cout << "IMPOSSIBLE";

	
	
}

Measured memory_bytes: 1024
x,k,d=map(int,input().split())
if(x<0):
    x=x*-1
if(x>=k*d):
    print(x-(k*d))
else:
    r=x%d
    g=x//d
    k=k-g;
    if(k%2==0):
        print(r)
    else:
        ans=abs(r-d)
        print(ans)


Measured memory_bytes: 9060
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
constexpr double PI = 3.1415926535897932;   // acos(-1)
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

using ld = double;
ld dp[3000][3000];

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

    int n;
    cin >> n;
    vector<ld> p(n);
    for(int i = 0; i < n; ++i)  cin >> p[i];

    dp[0][0] = 1.0;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j <= i; ++j){
            dp[i + 1][j] += dp[i][j] * (1.0 - p[i]);
            dp[i + 1][j + 1] += dp[i][j] * p[i];
        }
    }

    ld ans = 0.0;
    for(int i = ceil((ld)n / 2); i <= n; ++i) ans += dp[n][i];
    cout << fixed << setprecision(10);
    cout << ans << endl;
}

Measured memory_bytes: 68992
# ABC125C - GCD on Blackboard
from fractions import gcd


def segfunc(x, y):  # modify for each case
    return gcd(x, y)


class SegmentTree:
    def __init__(
        self,
        init_val: "initial value: Array or str",
        ide_ele: "identity element corresponding init_val" = 0,
    ):
        self.size = 1 << (len(init_val) - 1).bit_length()
        self.ide_ele = ide_ele
        self.tree = self._build(init_val)

    def _build(self, init_val: "Array or str"):
        tree = [self.ide_ele] * (2 * self.size)

        for idx, val in enumerate(init_val):  # set
            # modify val if needed (e.g. str -> ord())            
            tree[idx + self.size - 1] = val

        for idx in range(self.size - 2, -1, -1):  # build
            tree[idx] = segfunc(tree[2 * idx + 1], tree[2 * idx + 2])
        return tree

    def update(self, idx: int, val):
        idx += self.size - 1
        # modify val if needed as same as in _build()
        self.tree[idx] = val
        while idx > 0:
            idx = (idx - 1) // 2
            self.tree[idx] = segfunc(self.tree[2 * idx + 1], self.tree[2 * idx + 2])

    def query(self, left: int, right: int):
        left += self.size
        right += self.size
        ret = self.ide_ele
        while left < right:
            if left & 1:
                ret = segfunc(ret, self.tree[left - 1])
                left += 1
            if right & 1:
                right -= 1
                ret = segfunc(ret, self.tree[right - 1])
            left >>= 1
            right >>= 1
        return ret


def main():
    N, *A = map(int, open(0).read().split())
    seg = SegmentTree(A)
    ans = 0
    for i in range(N):
        ans = max(ans, gcd(seg.query(0, i), seg.query(i + 1, N)))
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 16172
/************************************
/ AUTHOR : YATHARTH GOSWAMI         /  
/ ALIAS : hacker_yg                 /
/ INSTITUTE : IIT Kanpur            /
************************************/
//          TEMPLATE                //

#include <bits/stdc++.h>

#define ll long long
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define F first
#define S second

using namespace std;

int main(){
    ll x;
    int flag =1;
    cin >> x;
    for (int i = 0; i <= 200; i++){
        for (int j = -199; j <= 199; j++) {
            if ((ll)pow(i,5) - (ll)pow(j,5) == x) {
                cout << i << ' ' <<  j << endl;
                flag = 0;
                break;
            }
            if (!flag) break;
        }
    }
    return 0;
}




Measured memory_bytes: 4096
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define deb(x) cout << #x << " = "<< x << "\n";

signed main()
{
	//freopen("in,txt", "r",stdin);
	//freopen("out.txt" ,"w", stdout);
	
	int n; cin >> n;
	int a[n+1];
	iota(a, a+n+1, 0);
	vector<int> v;
	v.push_back(1);
	int six = 6;
	while(six <= n)
	{
		v.push_back(six);
		six *= 6;
	}
	int nine = 9;
	while(nine <= n)
	{
		v.push_back(nine);
		nine *= 9;
	}
	sort(v.begin(), v.end());
	
	for(int i = 1; i <= n; i++)
	{
		for(int x : v)
		{
			if(x > i) break;
			a[i] = min(a[i], a[i-x] + 1);
		}
	}
	cout << a[n] << "\n";
	
	
	
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll mod = 1000000007;

ll r(ll x, ll y) {
  if (y == 0) return 1;
  else if (y % 2 == 0) return r(x, y/2) * r(x, y/2) % mod;
  else return x * r(x, (y-1)/2) % mod * r(x, (y-1)/2) % mod;
}
  
int main() {
  int n, k;
  cin >> n >> k;
  int m = min(n, k);
  int M = max(n, k);
  for (int i = 0; i < M; i++) {
    cout << m;
  }
  cout <<endl;
} 


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

typedef long long int ll;
typedef vector<int> vi;            
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef pair<int, int>     pii;
typedef vector<bool> vb;
#define endl '\n'
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size()
#define MOD 1000000007
#define F first
#define S second
#define pb push_back
#define pf push_front
#define rb pop_back
#define rf pop_front
#define in insert
#define mp make_pair
#ifdef LOCAL
    #include "../../trace.h"
#else
    #define trace(args...)
#endif

ll div_floor(const ll &a,const ll &b) { return a / b - (((a ^ b) < 0) and a % b);}
ll div_ceil(const ll &a,const ll &b) { return a / b + (((a ^ b) >= 0) and a % b);}

void solve(){
    int n; cin>>n;
    vl a(n); for(auto &e: a) cin>>e;
    sort(all(a));
    int ans = 0;
    for(int i = 0; i<n; i++)
        for(int j = i+1; j<n; j++)
            for(int k = j+1; k<n; k++)
                ans += (a[i]+a[j])>a[k] && (a[i]!=a[j]) && (a[j]!=a[k]);
    cout<<ans<<endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    #ifdef LOCAL
        freopen(".inp.txt", "r", stdin);
        freopen(".out.txt", "w", stdout);
        freopen(".err.txt", "w", stderr);
    #endif
    int t=1;
    // cin>>t;
    while(t--)
        solve();
}

Measured memory_bytes: 3680
import java.util.Scanner;

public class Main {
	static int[] di = {0,-1,0,1};
	static int[] dj = {1,0,-1,0};
	static char[] tank = {'>','^','<','v'};
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int n = sc.nextInt();
		for(int i=0;i<n;i++) {
			if (i > 0) {
				System.out.println();
			}
			solve();
		}
	}
	
	public static void solve() {
		int h = sc.nextInt();
		int w = sc.nextInt();
		char[][] m = new char[h][];
		for(int i=0;i<h;i++) {
			m[i] = sc.next().toCharArray();
		}
		int n = sc.nextInt();
		char[] c = sc.next().toCharArray();
		int ni = -1,nj = -1;
		int dir = -1;
		for(int i=0;i<h;i++) {
			for(int j=0;j<w;j++) {
				char cc = m[i][j];
				if (cc == '^' || cc == 'v' || cc == '<' || cc == '>') {
					switch (cc) {
					case '^':
						dir = 1;
						break;
					case '<':
						dir = 2;
						break;
					case 'v':
						dir = 3;
						break;
					case '>':
						dir = 0;
						break;
					}
					ni = i;
					nj = j;
					m[i][j] = '.';
				}
			}
		}
		for(int t=0;t<n;t++) {
			switch (c[t]) {
			case 'U':
				dir = 1;
				break;
			case 'D':
				dir = 3;
				break;
			case 'L':
				dir = 2;
				break;
			case 'R':
				dir = 0;
				break;
			}
			if (c[t] != 'S') {
				int xi = ni + di[dir];
				int xj = nj + dj[dir];
				if (xi < 0 || xi >= h || xj < 0 || xj >= w || m[xi][xj] != '.') {
					continue;
				}
				ni = xi;
				nj = xj;
			}else{
				int bi = ni;
				int bj = nj;
				while(0 <= bi && bi < h && 0 <= bj && bj < w) {
					if (m[bi][bj] == '*') {
						m[bi][bj] = '.';
						break;
					}else if(m[bi][bj] == '#') {
						break;
					}
					bi += di[dir];
					bj += dj[dir];
				}	
			}
		}
		m[ni][nj] = tank[dir];
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<h;i++) {
			sb.append(m[i]);
			sb.append('\n');
		}
		System.out.print(sb.toString());
	}
}

Measured memory_bytes: 29204
#include<bits/stdc++.h>
using namespace std;
int n;
char s[1000100];
char t[1000100];
queue<int>q;
int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	scanf("%s",t+1);
	int ans=0;
	for(int i=1;i<=n;++i)
		if(s[i]!=t[i]){ans=1;break;}
	if(!ans)
	{
		puts("0");
		return 0;
	}
	for(int up=n,dn=n;dn;--dn)
	{
		while(t[dn-1]==t[dn])dn--;
		up=min(up,dn);
		while(s[up]!=t[dn]&&up)up--;
		if(!up)
		{
			puts("-1");
			return 0;
		}
		while(!q.empty())
		{
			if(q.front()-q.size()+1>dn)q.pop();
			else break;
		}
		if(up!=dn)q.push(up);
		ans=max(ans,(int)q.size()+1);
	}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 6272
from collections import Counter 

a,b = map(int,input().split())
l = ''
for i in range(a):
    t = input()
    l+=t

c = Counter(list(l))
# print(c)
dp = [0,0,0]
for i in c:
    if c[i]%2 ==1:
        dp[0] +=1
    elif c[i]%4 == 0:
        dp[2] += 1
    elif c[i]%2 == 0:
        dp[1] += 1
# print(dp)
ans = 'No'
if a%2 ==1 and b%2 ==1:
    A = 1
    B = (a+b-2)//2
    if A >= dp[0] and B >= dp[1]:
        ans = 'Yes'
elif  a%2 ==0 and b%2 ==0:
    A = 0
    B= 0
    if A >= dp[0] and B >= dp[1]:
        ans = 'Yes'
elif a%2 ==0 and b%2 ==1:
    A = 0
    B = a//2
    if A >= dp[0] and B >= dp[1]:
        ans = 'Yes'
else:
    A=0
    B= b//2
    if A >= dp[0] and B >= dp[1]:
        ans = 'Yes'
print(ans)


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

main(){
    int n; 
    cin >> n;
    int r = 0;
    
    for ( int i = 0; i < n; i++){
        int s; 
        cin >> s;
        if ( s % 2 == 0 ){
            r++;
        }
    }
    cout << r << endl;
}


Measured memory_bytes: 3124