akhauriyash/Code-Regression huggingface dataset:
CMD=0
VAL=1

class Node
  attr_accessor :value,:left,:right,:parent
  def initialize (value,parent)
    @value = value
    @parent = parent
    @left = nil
    @right = nil
  end

  def insert (value)
    if value < @value
      if @left.nil?
        @left = Node.new(value,self)
      else
        @left.insert(value)
      end
    else
      if @right.nil?
        @right = Node.new(value,self)
      else
        @right.insert(value)
      end
    end
  end

  def find(value)
    if value==@value
      print "yes\n"
    elsif value < @value
      if @left.nil?
        print "no\n"
      else
        @left.find(value)
      end
    else
      if @right.nil?
        print "no\n"
      else
        @right.find(value)
      end
    end
  end

  def delete(value)
     #p "before:#{@value}"
    if value == @value
      if @left.nil? or @right.nil?
         #p "removed"
        update_tree
      else
        @value = @right.get_new_value
         #p "after:#{@value}"
      end
    elsif value < @value
      @left.delete(value)
    else
      @right.delete(value)
    end
  end

  def get_new_value
    unless @left.nil?
      return @left.get_new_value
    else
      update_tree
      return @value
    end
  end
      
  def update_tree 
     #p "value: #{@value}"
     #p "@parent.value: #{@parent.value}"
    if @left.nil? and @right.nil?
      new_child = nil
    elsif @left.nil?
      new_child = @right
    elsif @right.nil?
      new_child =  @left
    else
      p "oops"
    end

    new_child.parent = @parent unless new_child.nil?

    if @value < @parent.value
      @parent.left  = new_child
       #p "parent left: #{@parent.left}"
    else
      @parent.right = new_child
       #p "parent right: #{@parent.right}"
    end
  end
  
  def print_inorder
    @left.print_inorder unless @left.nil?
    print " #{value}"
    @right.print_inorder unless @right.nil?
  end
  
  def print_preorder
    print " #{value}"
    @left.print_preorder unless @left.nil?
    @right.print_preorder unless @right.nil?
  end
end

num_of_cmd = STDIN.gets()
inputs = STDIN.read().split("\n").map{ |input| input.split(' ') }

root=nil
inputs.each do |input|
  if input[CMD] == 'insert'
    if root.nil?
      root = Node.new(input[VAL].to_i,nil)
    else
      root.insert(input[VAL].to_i)
    end
  elsif input[CMD] == 'find'
    root.find(input[VAL].to_i)
  elsif input[CMD] == 'delete'
    root.delete(input[VAL].to_i)
  else
    root.print_inorder unless root.nil?
    print "\n"
    root.print_preorder unless root.nil?
    print "\n"
  end
end

Measured memory_bytes: 211000
#include<stdio.h>
int a[111111],n,len;
int main(){
	scanf("%d%d",&n,&len);
	for(int i=1; i<=n; i++)
		scanf("%d",&a[i]);
	int s = -1;
	for(int i=1; i<n; i++)
		if(a[i] + a[i+1] >= len){
			s=i;
			break;
		}
	if(s==-1)
		puts("Impossible");
	else{
		puts("Possible");
		for(int i=1; i<s; i++)
			printf("%d\n",i);
		for(int i=n-1; i>s; i--)
			printf("%d\n",i);
		printf("%d\n",s);
	}
	return 0;
}

Measured memory_bytes: 1152
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,a,b = LI()
if (b-a) % 2 == 0:
    print((b-a)//2)
else:
    s = (a-1)+1
    s += ((b-(a-1)-1) - 1)//2
    t = (n-b)+1
    t += (n - (a + (n-b)+1))//2
    print(min(s,t))

Measured memory_bytes: 38256
'use strict';

function Main(input) {

  input = input.trim().split(" ").map(Number);
  let badKusuri = input[0];
  let goodKusuri = input[1];
  let goodPoison = input[2];
  
  for(;(goodKusuri>0)&&(goodPoison>0);){
  	goodKusuri--;
    goodPoison--;
  }
  
  if(goodPoison == 0){
  	goodKusuri = 0;
  } else {
  	for(;(badKusuri>0)&&(goodPoison>0);){
  		badKusuri--;
      	goodPoison--;
  	}
  }
  
  if(goodPoison > 0){
  	goodPoison--;
  }
  
  console.log((input[1] + input[2]) - (goodKusuri + goodPoison));
  
  
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		char[] o = scanner.next().toCharArray(), e = scanner.next().toCharArray();
		int len = o.length + e.length;
		char[] passwords = new char[len];
		int count = 0;
		for (int i = 0; i < len; i++) {
			if (count>=len) {
				break;
			}
			passwords[count] = o[i];
			count++;
			if (count>=len) {
				break;
			}
			passwords[count] = e[i];
			count++;
		}
		
		System.out.println(new String(passwords));
		scanner.close();
	}
}


Measured memory_bytes: 21716
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

dishes=[I() for i in range(0,5)]
rounded = []
for i in dishes:
    if i%10 != 0:
        i += 10 - i % 10
    rounded.append(i)
result=10**10
for i in range(len(dishes)):
    # order i in the end
    result = min(result, sum([r for ridx, r in enumerate(rounded) if ridx != i]) + dishes[i])
    
print(result)
    
    

Measured memory_bytes: 5464
from operator import mul
from functools import reduce


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


from collections import Counter
n, p = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(list(map(lambda x: x % 2, a)))
a = Counter(a)
ans = 0
if p == 1:
    for i in range(1, a[1] + 1, 2):
        for j in range(a[0] + 1):
            ans += combinations_count(a[1], i) * combinations_count(a[0], j)
if p == 0:
    for i in range(0, a[1] + 1, 2):
        for j in range(a[0] + 1):
            ans += combinations_count(a[1], i) * combinations_count(a[0], j)
print(ans)

Measured memory_bytes: 70836
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(double x){
  printf("%.15f",x);
}
template<class T> inline T pow2_L(T a){
  return a*a;
}
int N;
int X[8];
int Y[8];
double dist[8][8];
int main(){
  int i;
  int ind[8];
  double res = 0;
  double cnt = 0;
  rd(N);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){
      rd(X[Lj4PdHRW]);
      rd(Y[Lj4PdHRW]);
    }
  }
  for(i=(0);i<(N);i++){
    ind[i] = i;
  }
  for(i=(0);i<(N);i++){
    int j;
    for(j=(0);j<(N);j++){
      dist[i][j] = sqrt(pow2_L((X[i]-X[j]))+pow2_L((Y[i]-Y[j])));
    }
  }
  do{
    cnt++;
    for(i=(1);i<(N);i++){
      res += dist[ind[i-1]][ind[i]];
    }
  }
  while(next_permutation(ind,ind+N));
  wt_L(res/cnt);
  wt_L('\n');
  return 0;
}
// cLay varsion 20191111-2

// --- original code ---
// int N, X[8], Y[8];
// double dist[8][8];
// {
//   int ind[8];
//   double res = 0, cnt = 0;
//   rd(N,(X,Y)(N));
//   rep(i,N) ind[i] = i;
//   rep(i,N) rep(j,N) dist[i][j] = sqrt( (X[i]-X[j])**2 + (Y[i]-Y[j])**2 );
//   do{
//     cnt++;
//     rep(i,1,N) res += dist[ind[i-1]][ind[i]];
//   }while(next_permutation(ind,ind+N));
//   wt(res/cnt);
// }


Measured memory_bytes: 256
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


s = input()
def sub(c):
    ss = s[:]
    ans = 0
    while True:
        if all(c==ss[i] for i in range(len(ss))):
            break
        ans += 1
        tmp = []
        for i in range(len(ss)-1):
            if c in (ss[i], ss[i+1]):
                tmp.append(c)
            else:
                tmp.append(ss[i])
        ss = "".join(tmp)
    return ans
ans = float("inf")
for c in set(s):
    ans = min(ans, sub(c))
print(ans)

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

#define pb push_back
#define mp make_pair

typedef pair<int, int> pii;

int a[500][500];
vector<pair<pii, pii> > ans;

int main()
{
  int h, w;
  cin >> h >> w;
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      if(i % 2) cin >> a[i][w-j-1];
      else cin >> a[i][j];
    }
  }

  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      if(i == h-1 and j == w-1) break;

      int x = j, y = i;
      
      int nx = x == w-1 ? 0 : x+1;
      int ny = x == w-1 ? y+1 : y;

      if(a[i][j] % 2){
        a[ny][nx]++;

        if(y % 2) x = w-x-1;
        if(ny % 2) nx = w-nx-1;

        ans.pb(mp(mp(y+1, x+1), mp(ny+1, nx+1)));
      }
    }
  }

  cout << ans.size() << endl;
  for(auto u : ans){
    cout << u.first.first << " ";
    cout << u.first.second << " ";
    cout << u.second.first << " ";
    cout << u.second.second << endl;
  }

  return 0;
}


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

int main() {
    int A, B, K, cnt = 0;
    cin >> A >> B >> K;
    for (int i = A; i >= 1; i--) {
        if (A % i == 0 && B % i == 0) {
            cnt += 1;
        }
        if (cnt == K) {
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
def gcd(p, q):
    if p < q:
        p, q = q, p
    while q > 0:
        p, q = q, p%q
    return p
n, x = map(int, input().split())
x_list = [abs(int(i)-x) for i in input().split()]
a = x_list[0]
for i in range(1, n):
    a = gcd(a, x_list[i])
print(a)

Measured memory_bytes: 14248
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
const ll MOD=1000000007;
const long double PI=3.14159265358979;
const ll MAX=0;

int main() {
  ll N,M,K,ans=0;
  cin>>N>>M>>K;
  ll n[N+1];
  n[0]=0;
  ll m[M];
  rep(i,N){
    cin>>n[i+1];
    if(i+1==0){
      continue;
    }
    n[i+1]+=n[i];
  }
  rep(i,M){
    cin>>m[i];
    if(i==0){
      continue;
    }
    m[i]+=m[i-1];
    //cout<<m[i]<<" ";
  }
  for(int i=0;i<=N;i++){
    ll k=K-n[i];
    if(k<0){
      continue;
    }
    auto itr=upper_bound(m,m+M,k);
    ll mm=itr-m;
    ans=max(ans,mm+i);
    //cout<<n[i]<<" "<<mm<<endl;
  }
  cout<<ans;
}


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

int main(){
    int n;
    string s;
    cin >> n >> s;
    int rb = 0, lb = 0, count = 0;
    string ans_r = "", ans_l = "";
    rep(i, n) {
        if (s[i]=='(') {
            rb++;
        } else {
            if (rb>0) rb--;
            else lb++;
        }
    }
    rep(i, lb) {
        cout << "(";
    }
    cout << s;
    rep(i, rb) {
        cout << ")";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.*;
import java.util.*;

public class Main{
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException{
        //キー入力
        getLine();
        List<String> strings = getStrOnLine();
        //計算
        int n = bubbleSort(strings);
        //出力
        String out = String.join(" ",strings);
        System.out.println(out);
        System.out.println(n);
    }

    private static int bubbleSort(List<String> list){ 
        boolean flag = true;
        int n = 0;
        while (flag){
            flag = false;
            for (int j = list.size() - 1 ; j >= 1; j--){
                int a = Integer.parseInt(list.get(j));
                int b = Integer.parseInt(list.get(j - 1));
                if (a < b){
                    String tmp = list.get(j);
                    list.set(j, list.get(j-1));
                    list.set(j - 1, tmp);
                    n++;
                    flag = true;
                }
            }
        }
        return n;
    }
    

    //キー入力メソッド
    public static String getLine() throws IOException {
        String str = br.readLine();
        return str;
    }
    
    //キー入力メソッド
    public static List<String> getStrOnLine() throws IOException {
        List<String> list = new ArrayList<>();
        String line = getLine();
        
        list.addAll(Arrays.asList(line.split(" ")));
        return list;
    }
}


Measured memory_bytes: 25900
#include <bits/stdc++.h>
#include <cstdlib>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

int main() {
    int n;
    unordered_map<string, int> mp;
    long long cnt = 0;
    cin >> n;
    string str[n];
    for(int i = 0; i < n; i++) {
      cin >> str[i];
    }
    for(int i = 0; i < n; i++) {
      sort(str[i].begin(), str[i].end());
      if(mp.find(str[i]) != mp.end()){
//        cout << str[i] << endl;
//        cout << "hit" << endl;
        cnt += mp[str[i]];
        mp[str[i]] += 1;
      }else {
        mp[str[i]] = 1;
//        cout << "new" << endl;
      }
    }
    cout << cnt;

    return 0;
}


Measured memory_bytes: 17572
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);
    
    int X = scanner.nextInt();
    
    int a = X / 500;
    X = X - a * 500;
    int b = X / 5;
    
    int answer = a * 1000 + b * 5;
    System.out.println(answer);
  }
}

Measured memory_bytes: 22740
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	a := make([][]int, 2)

	for i := range a {
		for j := 0; j < n; j++ {
			var tmp int
			fmt.Scan(&tmp)
			a[i] = append(a[i], tmp)
		}
	}

	max := 0
	for i := 0; i < n; i++ {
		sum := 0
		for j := 0; j < i+1; j++ {
			sum += a[0][j]
		}
		for j := i; j < n; j++ {
			sum += a[1][j]
		}
		if sum > max {
			max = sum
		}
	}
	fmt.Println(max)
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); 
	int n; ll x; cin>>n>>x;
	vector<pair<ll,ii> > vec;
	for(int i=0;i<n;i++)
	{
		ll b,l,r; cin>>b>>l>>r;
		vec.pb({b,{l,r}});
	}
	ll lo=0; ll hi=x*1LL*n-1;
	ll ans=x*1LL*n;
	while(lo<=hi)
	{
		ll mid=(lo+hi)>>1;
		//suppose i only study mid days
		ll full = mid/x;
		ll partial = mid%x;
		vector<ii> diff;
		ll sum=0;
		for(int i=0;i<n;i++)
		{
			sum+=-vec[i].fi*vec[i].se.fi;
			diff.pb({vec[i].se.se*(x-vec[i].fi)+vec[i].fi*vec[i].se.fi,i});
		}
		sort(diff.rbegin(),diff.rend());
		ll S = -ll(1e18);
		ll sumfirstfull = 0;
		ll sumsecondfull=0;
		for(int i=0;i<full;i++)
		{
			sumfirstfull+=diff[i].fi;
		}
		for(int i=0;i<full+1;i++)
		{
			sumsecondfull+=diff[i].fi;
		}
		for(int j=0;j<n;j++)
		{
			int i=diff[j].se;
			ll oricost=-vec[i].fi*vec[i].se.fi;
			ll newcost=max((partial-vec[i].fi)*vec[i].se.fi,(partial-vec[i].fi)*vec[i].se.se);
			if(j<full)
			{
				oricost=vec[i].se.se*(x-vec[i].fi);
				S=max(S,sum+sumsecondfull+newcost-oricost);
			}
			else
			{
				S=max(S,sum+sumfirstfull+newcost-oricost);
			}
		}
		if(S>=0)
		{
			ans=mid; hi=mid-1;
		}
		else lo=mid+1;
	}
	cout<<ans<<'\n';
}


Measured memory_bytes: 8756
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); ++i)
using namespace std;
int main() {
  string s;
  cin >> s;
  int n=s.size();
  string ans;
  rep(i,n) {
    if(i%2==0) ans+=s[i];
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 512
n,m=map(int, input().split())
h=list(map(int,input().split()))
G=[[] for _ in range(n+1)]
for i in range(m):
    a,b=map(int, input().split())
    G[a].append(b)
    G[b].append(a)
ans=0
for i in range(1,n+1):
    hi=h[i-1]
    c=0
    for j in G[i]:
        if h[j-1]>=hi:
            c=1
    if c==0:
        ans+=1
print(ans)

Measured memory_bytes: 92976
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main(){
    int a,b,c,n;

    scanf("%d%d%d",&a,&b,&c);
    
    n=c-(a-b);
    if(n<0){
        n=0;
    }
    
    printf("%d",n);
    return 0;
}

Measured memory_bytes: 256
n = gets.chomp.to_i
a = []
n.times do
  a.push gets.chomp.to_i
end
done = {1 => 1}
cur = 0
loop do
  nex = a[cur]
  if nex == 2
    puts done.size
    exit
  end
  if done[nex]
    puts '-1'
    exit
  end
  cur = nex - 1
  done[nex] = nex
end


Measured memory_bytes: 9084
;; -*- coding:utf-8 -*-

(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter O3 '(optimize (speed 3) (safety 0) (debug 0)))
  (defparameter O2 '(optimize (speed 3) (safety 1))))

(defmacro print-line (obj &optional (stream '*standard-output*))
  `(prog1 (princ ,obj ,stream) (terpri ,stream)))


;; Hauptteil

(defun split-by-one-space (str dest-arr)
  (declare #.O3
           (simple-string str)
  	   ((simple-array unum (*)) dest-arr))
  (loop for idx from 0 below (length dest-arr)
     for pos1 = 0 then (1+ pos2)
     for pos2 = (position #\space str :start pos1 :test #'char=)
     do (setf (aref dest-arr idx)
	      (parse-integer str :start pos1 :end pos2))
     finally (return dest-arr)))

(deftype unum nil `(integer 0 ,(expt 10 9)))
(defun main ()
  (declare #.O3)
  (let* ((n (read))
	 (cache (make-hash-table))
	 (arr (make-array n :element-type 'unum))
	 (a-lst nil))
    (split-by-one-space (read-line) arr)
    (loop for a across arr do
	 (multiple-value-bind (num p)
	     (gethash a cache)
	   (declare (unum num))
	   (if p
	       (setf (gethash a cache) (+ num 1))
	       (progn (setf (gethash a cache) 1)
		      (push a a-lst)))))
    (print-line
     (loop for a of-type unum in a-lst
	sum (let ((num (gethash a cache)))
	      (declare (unum num))
	      (if (>= num a)
		  (- num a)
		  num))))
  ))

#-swank(main)


;; Für Test
(defun get-clipbrd ()
  (with-output-to-string (out)
    (run-program "C:/msys64/usr/bin/cat.exe" '("/dev/clipboard") :output out)))

(defun test ()
  (with-input-from-string (*standard-input* (delete #\return (get-clipbrd)))
    (main)))


;; Für Benchmark
(defparameter *file-path* *load-pathname*)
(defparameter *dir-path* (pathname (directory-namestring *file-path*)))
(defparameter *dat-path* (merge-pathnames "test.dat" *dir-path*))

#+swank
(defun gendat ()
  (with-open-file (out *dat-path*
		       :direction :output :if-exists :supersede)
    ))

(defun bench ()
  (let ((*standard-output* (make-broadcast-stream)))
    (with-open-file (*standard-input* *dat-path*)
      (time (main)))))


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

int main()
{
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    vector<ll> p;
    rep(i, 2) rep(j, n) p.push_back(a[j]);
    ll ans1 = 0, ans2 = 0, ans = 0;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (a[i] > a[j])
                ans1++;
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = n; j < 2 * n; j++)
        {
            if (p[i] > p[j])
                ans2++;
        }
    }
    ans = ans1 * k + (k * (k - 1) / 2 % mod) * ans2 % mod;
    ans %= mod;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll inf=(1ll<<61);
const int MX=3e5+9;
int n,t[2],x[2],y[2];
int main(){
    scanf("%d",&n);
    t[0]=x[0]=y[0]=0;
    for(int i=0;i<n;i++){
        scanf("%d%d%d",&t[1],&x[1],&y[1]);
        int dis=abs(x[1]-x[0])+abs(y[1]-y[0]);
        int time=t[1]-t[0];
        if(dis==time)continue;
        if(dis>time){
            puts("No");
            return 0;
        }
        if(dis%2==time%2)continue;
        puts("No");
        return 0;
        t[0]=t[1];
        x[0]=x[1];
        y[0]=y[1];
    }
    puts("Yes");
}


Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#define rep(i,a,n) for(int i=(a);i<(n);i++)
using namespace std;

int main() {
	string a[3];
	int null;
	rep(i, 0, 3)cin >> a[i];
	int x = 0;
	for (;;) {
		if(a[x].size()==0){
			null = x;
			break;
		}
		int s = x;
		x = a[s][0] - 97;
		a[s].erase(0, 1);
	}
	string ans;
	if (null == 0)ans = "A";
	else if (null == 1)ans = "B";
	else ans = "C";
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
long long n,d,x,y,i,p=0;
int main(void)
{
  scanf("%lld%lld",&n,&d);
  d*=d;
  for(i=0;i<n;i++){
    scanf("%lld%lld",&x,&y);
    if(d>=(x*x)+(y*y)){
      p++;  
  }
  }
  printf("%d\n",p);
  return 0;
}

Measured memory_bytes: 1736
#include <stdio.h>
int main(void){
	int x,y;
	while(1){
		scanf("%d %d",&x,&y);
		if(x==0&&y==0){
			break;
		}
		if(x > y){
			printf("%d %d\n",y,x);
		}
		else{
			printf("%d %d\n",x,y);
		}
	}
	return 0;
}

Measured memory_bytes: 600
/*
  Motto - try hard to become an expert
*/
#include <bits/stdc++.h>
#include <map>
#include <algorithm>
#include <vector>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <chrono>
#include <thread>
#include <iomanip>
 
//define
#define rep(i,n)    for(int i=0;i<n;i++)
#define repu(i,k,n) for(int i=k;i<=n;i++)
#define repd(i,k,n) for(int i=k;i>=n;i--)
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define INF (int)INT_MAX
#define all(v)  v.begin(), v.end()
#define endl "\n"
 
//typedef
typedef long long int ll;
typedef long double ld;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
typedef std::vector< pii > vii;
typedef std::vector< ll > vll;
typedef std::vector< std::pair < pii, int > > vpp;
 
const int N = 3*1e5 +5 ;
const long long MOD = 998244353;
const long long inf = 1e18;
 
using namespace std;
 
ll MAXN=100001;
ll spf[100001]; 
 
ll modpow(ll x,ll n){
    ll res=1;
    while(n>0){
        if(n&1) res=res*x%MOD;
        x=x*x%MOD;
        n>>=1;
    }
    return res;
}
 
ll modFact(ll n, ll p) 
{ 
    if (n >= p) 
        return 0; 
  
    ll result = 1; 
    for (ll i = 1; i <= n; i++) 
        result = (result * i) % p; 
  
    return result;  
} 
 
bool isPrime(int x)
{
    if(x%2==0)
        return 0;
    for(int i=3;i<=sqrt(x);i+=2)
    {
        if(x%i==0)
            return 0;
    }
    return 1;
}
 

 
void solve()
{
	int n ; 
	cin>>n ;
	cout<<n*n*n<<endl; 	

}
 
int main() {
    // #ifndef ONLINE_JUDGE
    //     // for getting input from input.txt
    //     freopen("input.txt", "r", stdin);
    //     // for writing output to output.txt
    //     freopen("output.txt", "w", stdout);
    // #endif
    
    // ios_base::sync_with_stdio(0);
    // cin.tie(NULL);
    int t = 1;
    // cin>>t;
    while(t--)
    {
        solve();
    } 
    // cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Measured memory_bytes: 256
def main():
    a, b, k = list(map(int, input().split()))

    ans_a = a - k
    if ans_a < 0:
        k = ans_a * -1
        ans_a = 0
    else:
        k = k - a

    k = 0 if k < 0 else k

    b = b - k if b - k > 0 else 0

    print(ans_a, b)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define ll long long
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define F first
#define S second
#define P pair
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define V vector
#define RE return
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define PB emplace_back
#define PF emplace_front
#define FILL(a,b) memset(a,b,sizeof(a))
#define lwb lower_bound
#define upb upper_bound
using namespace std;
bool f[105];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,x,p,ans=1e9,ansp;
	cin>>p>>n;
	FOR(i,1,n){
		cin>>x;f[x]=1;
	}
	if(p+1<ans){
		ansp=-1;ans=p+1;
	}
	FOR(i,0,100){
		if(!f[i]){
			if(abs(i-p)<ans){
				ans=abs(i-p);
				ansp=i;
			} 
		}
	}
	if(101-p<ans){
		ansp=101;
		ans=101-p;
	}
	cout<<ansp;
	RE 0;
}




Measured memory_bytes: 3664
#include<bits/stdc++.h>
using namespace std;
struct Info{int nu,we,qq;}a[1000010];
bool comp(const Info &a,const Info &b){return a.nu<b.nu;}
int n,b[1000010];long long ansn;bool c;
int main(){
	cin>>n;
	for (int i=1;i<=n;i++){cin>>a[i].nu>>a[i+n].nu;a[i].we=a[i+n].we=i;a[i].qq=1;a[i+n].qq=2;}
	sort(a+1,a+n+n+1,comp);
	for (int i=1;i<=n;i++){ansn+=a[i].nu;b[a[i].we]++;if (b[a[i].we]==2) c=true;}
	bool d=true,e=true;
	for (int i=2;i<=n;i++)if (a[i].qq!=a[1].qq)d=false;
	for (int i=2;i<n;i++) if (a[i].qq!=a[1].qq)e=false;
	if (c||d)cout<<ansn<<endl;
	else {
		if (a[n].we==a[n+1].we&&!e){ansn-=a[n].nu+a[n-1].nu;cout<<min(ansn+a[n-1].nu+a[n+2].nu,ansn+a[n].nu+a[n+1].nu);}
		else{cout<<ansn-a[n].nu+a[n+1].nu;}
	}
	return 0;
}

Measured memory_bytes: 6784
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

const int INF=1e12;

void solve(int N)
{
    vector<int> h(N);
    for(int i=0;i<N;i++) cin>>h[i];

    int M; cin>>M;
    vector<int> m1,d1,m2,d2;
    for(int i=0;i<M;i++){
        string s,t;
        int x,y;
        cin>>s>>x>>t>>y;
        if(t=="Single") m1.push_back(x),d1.push_back(y);
        else m2.push_back(x),d2.push_back(y);
    }
    // for(int i:m1) cout<<i<<' '; cout<<endl;
    // for(int i:d1) cout<<i<<' '; cout<<endl;
    // for(int i:m2) cout<<i<<' '; cout<<endl;
    // for(int i:d2) cout<<i<<' '; cout<<endl;
    int maxH=*max_element(h.begin(),h.end());
    vector<int> dp1(maxH+1,INF),dp2(maxH+1,INF);
    dp1[0]=dp2[0]=0;
    for(int i=0;i<m1.size();i++){
        for(int j=0;j<=maxH;j++){
            int damage=min(j+d1[i],maxH);
            chmin(dp1[damage],dp1[j]+m1[i]);
        }
    }
    for(int i=0;i<m2.size();i++){
        for(int j=0;j<=maxH;j++){
            int damage=min(j+d2[i],maxH);
            chmin(dp2[damage],dp2[j]+m2[i]);
        }
    }
    for(int i=maxH-1;i>=0;i--) chmin(dp1[i],dp1[i+1]);
    for(int i=maxH-1;i>=0;i--) chmin(dp2[i],dp2[i+1]);
    int ans=INF;
    for(int i=0;i<=maxH;i++){
        int sum=dp2[i];
        for(int j=0;j<N;j++) sum+=dp1[max(0LL,h[j]-i)];
        chmin(ans,sum);
    }
    cout<<ans<<endl;
}
signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    while(true){
        int N; cin>>N;
        if(N==0) break;
        solve(N);
    }
    return 0;
}


Measured memory_bytes: 4496
#include <iostream>
#include <vector>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#define myfor(i,N) for(i=0;i<N;i++)
#define myforFL(i,f,l) for(i=f;i<l;i++)
#define myforInv(i,N) for(i=N;i>=0;i--)
#define myforFLInv(i,f,l) for(i=f;i>l;i--)
#define myIfBetween(x,a,b) if(x >= a && x <= b)

using namespace std;

int main(){
	int X;
	cin >> X;
	int i;
	myfor(i,8){
		myIfBetween(X,400+i*200,599+i*200)cout << 8-i << endl;
	}
	return 0;
}




Measured memory_bytes: 3540
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define rep(i,a,b) for(i=(ll)a;i<(ll)b;i++)
#define revrep(i,a,b) for(i=(ll)a;i>=(ll)b;i--)
#define strep(it,v) for(it=v.begin();it!=v.end();++it)
#define ii pair<ll,ll>
#define MP make_pair
#define pb push_back
#define f first
#define se second
#define ll long long int
#define vi vector<int>
#define rs resize
ll modexp(ll a,ll b){ ll res = 1;  while(b>0){  if(b&1)  res = (res*a)%mod;  a = (a*a)%mod;  b/=2;  }  return res; }
int main()
{
   std::ios::sync_with_stdio(false);
   ll n,b,c,i,sum = 0;
   cin>>n;
   ll a[n];
   rep(i,0,n) cin>>a[i],sum += a[i];
   cin>>n;
   rep(i,0,n){
      cin>>b>>c;
      cout<<(sum - a[b - 1] + c)<<endl;
   }
   return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,x,y) for(ll i=x;i<=y;i++)
#define imin INT_MIN
#define imax INT_MAX
int mod =1e9+7;
//~ vector<bool> cats;

//~ ll ans;
//~ ll n,m;
//~ void dfs(vector<vector<int>>& graph,int s,int consCats,int parent){
	//~ if(consCats>m) return;
	//~ if(graph[s].size()==1 && graph[s][0]==parent)
	//~ {
		//~ if(cats[s]) consCats++;
		//~ if(consCats<=m) ans++;
		//~ return;
	//~ }
	//~ if(!cats[s]) consCats=0;
	//~ else consCats++;
	//~ for(auto val:graph[s]){
		//~ if(val!=parent)
		//~ dfs(graph,val,consCats,s);
	//~ }


int main(){
	cin.tie(NULL);
    ios_base::sync_with_stdio();

	string s;
	cin>>s;
	int cnt=0;
	int ans=0;
	rep(i,0,2){
		if(s[i]=='R') cnt++;
		else cnt=0;
		ans=max(ans,cnt);
	}
	cout<<ans<<endl;
	
	return 0;
}


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

int main() {
    int N;
    cin >> N;
    set<ll> num;
    ll res = 0;
    map<ll, ll> answers;
    rep(i, N)  {
        string s;
        ll ans = 1;
        cin >> s;
        rep(i, 10) {
            char c;
            c = s[i];
            if (c == 'a') {ans *= 2;}
            else if (c=='b') { ans*=3;}
            else if (c=='c') {ans*=5;}
            else if (c=='d') {ans*=7;}
            else if (c=='e') {ans*=11;}
            else if (c=='f') {ans*=13;}
            else if (c=='g') {ans*=17;}
            else if (c=='h') {ans*=19;}
            else if (c=='i') {ans*=23;}
            else if (c=='j') {ans*=29;}
            else if (c=='k') {ans*=31;}
            else if (c=='l') {ans*=37;}
            else if (c=='m') {ans*=41;}
            else if (c=='n') {ans*=43;}
            else if (c=='o') {ans*=47;}
            else if (c=='p') {ans*=53;}
            else if (c=='q') {ans*=59;}
            else if (c=='r') {ans*=61;}
            else if (c=='s') {ans*=67;}
            else if (c=='t') {ans*=71;}
            else if (c=='u') {ans*=73;}
            else if (c=='v') {ans*=79;}
            else if (c=='w') {ans*=83;}
            else if (c=='x') {ans*=89;}
            else if (c=='y') {ans*=97;}
            else if (c=='z') {ans*=101;}
        }
        if (num.count(ans)) {
            answers[ans]++;
        }
        else {
            answers[ans] = 1;
            num.insert(ans);
        }
    }
    for (auto p : answers) {
        ll count = p.second;
        res += ((count-1)*count)/2;
    }
    cout << res << endl;
}

Measured memory_bytes: 11136
// Problem : D - equeue
// Contest : AtCoder - AtCoder Beginner Contest 128
// URL : https://atcoder.jp/contests/abc128/tasks/abc128_d
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
using namespace std; 
#define ll long long int
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>
#define INF LLONG_MAX
#define PI acos(-1)
const ll MOD = 1e9 + 7;
#define fir first
#define sec second
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(c,a,b) for(ll c=a;c<b;c++)
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define min_heap priority_queue<pll,vector<pll>,greater<pll> >
ll dx4[]={-1,1,0,0};
ll dy4[]={0,0,-1,1};
ll dx8[]={-1,-1,-1,0,1,1,1,0};
ll dy8[]={-1,0,1,1,1,0,-1,-1};
bool isvalid(ll x,ll y,ll n,ll m)
{
    return (x>=0 and y>=0 and x<n and y<m);
}
ll isprime[1000];
vector<ll> prime;
void sievetoprime(ll n)
{
    mem(isprime,true);
    for(ll p=2;p*p<=n;p++)
    {
        if(isprime[p]==true)
        {
            for(ll i=p*p;i<=n;i+=p)
                isprime[i]=false;
        }
    }
}
ll lcm(ll a,ll b)
{
    return (a/__gcd(a,b))*b;
}
ll v[51];
ll n,k;
ll f(ll a,ll b)
{
	vector<ll> s;
	rep(i,0,a)
		s.pb(v[i]);
	rep(i,0,b)
		s.pb(v[n-i-1]);
	sort(all(s));
	ll sum=0;
	for(auto i:s)
		sum=sum+i;
	for(ll i=0;i<min(a+b,k-a-b);i++)
	{
		if(s[i]<0)
		{
			sum-=s[i];
		}
	}
	return sum;
}
void solve()
{
    cin>>n>>k;
    rep(i,0,n)
    {
    	cin>>v[i];
    }
    ll ans=0;
    for(ll a=0;a<=min(n,k);a++)
    {
    	for(ll b=0;a+b<=min(n,k);b++)
    	{
    		if(a+b>n)
    			continue;
    		ll x=f(a,b);
    		ans=max(ans,x);
    	}
    }
    cout<<ans;
}
int main()
{
    ll inpoup = 0;
    if(inpoup==1)
    {
        #ifndef ONLINE_JUDGE
            freopen("input.txt","r",stdin);
            freopen("output.txt","w",stdout);
        #endif
    }
    IOS
    ll t;
    t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
}

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

typedef unsigned long ul;
typedef long long int ll;
typedef pair<ll, ll> P;
#define pb push_back
#define mp make_pair
#define REP(i,n) REPN(i,0,n)
#define REPN(i,m,n) for(int i=m; i<(n); i++)
#define dump(x) cout << #x << " = " << (x) << endl

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

    int n;
    int h[200];
    cin >> n;
    REP(i, n) {
        cin >> h[i];
    }

    int ans = 0;

    REP(i, n) {
        while (h[i] > 0) {
            int j = i;
            while (h[j] > 0) {
                h[j] -= 1;
                j++;
            }
            ans++;
        }
    }

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
void err() {
  cout << -1 << endl;
  exit(0);
}
void dfs (int crr, int dpt, vector<vector<int>>& grh, long long& cnt) {
  cnt += dpt;
  for (int nxt : grh[crr]) {
    dfs(nxt, dpt + 1, grh, cnt);
  }
}
int main() {
  int n;
  cin >> n;
  vector<long long> d(n);
  map<long long, int> mp;
  for (int i = 0; i < n; i++) {
    cin >> d[i];
    mp[d[i]] = i;
  }
  sort(d.begin(), d.end());
  vector<long long> sz(n, 1);
  vector<vector<int>> grh(n);
  for (auto it = d.rbegin(); next(it) != d.rend(); it++) {
    auto i = mp[*it];
    long long ptv = *it - n + 2 * sz[i];
    auto jt = lower_bound(d.begin(), d.end(), ptv);
    if (jt == d.end() || *jt != ptv) err();
    auto p = mp[*jt];
    grh[p].push_back(i);
    sz[p] += sz[i];
  }
  long long cnt = 0;
  int rt = mp[d[0]];
  dfs(rt, 0, grh, cnt);
  if (d[0] != cnt) err();
  for (int crr = 0; crr < n; crr++) {
    for (int nxt : grh[crr]) {
      cout << crr + 1 << ' ' << nxt + 1 << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 17024
import queue,sys,collections,math,random;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M = Is()
mat = [[] for _ in range(N) ]
for _ in range(M):
    a,b = Is()
    a,b = a-1, b-1
    mat[a].append(b)
    mat[b].append(a)

c = 0
def dfs(visited,now):
    if len(visited) == N:
        global c
        c += 1
    else:
        q = mat[now]
        for e in q:
            if not e in visited:
                dfs(visited+[e],e)
dfs([0],0)
print(c)


Measured memory_bytes: 5100
n,k = map(int, input().split())
t = 0
for i in range(k, n+2):
  up = i*(2*n +1 -i)/2
  down = i*(i-1)/2
  s= up - down + 1 
  t += s
ans = t % (10**9 +7)
print(int(ans))

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

int main(){
  int n;
  cin >> n;
  double p[n];
  rep(i,n) cin >> p[i];
  double dp[n+1][n+1];
  rep(i,n+1)rep(j,n+1)dp[i][j]=0;
  dp[0][0]=1.0;
  rep(i,n){
    rep(j,i+1){
      dp[i+1][j] += dp[i][j]*(1.0-p[i]);
      dp[i+1][j+1] += dp[i][j]*p[i];
    }
  }
  double ans=0.0;
  for(int i=n/2+1;i<n+1;i++)ans += dp[n][i];
  cout << fixed << setprecision(9) << ans << endl;
  return 0;
}

Measured memory_bytes: 70528
#include<bits/stdc++.h>
#define ll long long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
static const ll MAX = 1000000000000000;
static const int NIL = -1;
using namespace std;
const long double EPS = 0.0000000001;
const long double PI = (acos(-1));
const int MOD = 1000000007;

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

vector<ll> m(1001,0);

int main(){
    ll h,w,k; cin >> h >> w >> k;
    ll wp = 0,hp = 1,c = 1,flag = false,flag2 = false;
    vector<vector<char>> s(h,vector<char>(w));
    vector<vector<ll>> ans(h,vector<ll>(w));


    rep(i,h){
        rep(j,w) {
            cin >> s[i][j];
            ans[i][j] = 0;
        }
    }

    rep(i,h){
        flag = false;
        flag2 = false;
        wp = 0;
        rep(j,w) {
            if (s[i][j] == '#' && !flag) {
                flag = true;
                flag2 = true;
            } else if (s[i][j] == '#' && flag) {
                for (int k = wp; k < j; k++) {
                    for (int t = 0; t < hp; t++) {
                        ans[i - t][k] = c;
                    }
                    wp = j;
                }
                c++;
            }
        }
        if(flag){
            for(int k = wp; k < w; k ++){
                for(int t = 0; t < hp; t ++){
                    ans[i-t][k] = c;
                }
            }
            c ++;
        }

        if(!flag2) hp ++;
        else hp = 1;
    }

    rep(i,h){
        rep(j,w) {
            if(ans[i][j] == 0) {
                cout << ans[i-1][j] << " ";
                ans[i][j] = ans[i-1][j];
            }else {
                cout << ans[i][j] << " ";
            }
        }
        cout << endl;
    }

}

Measured memory_bytes: 4444
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
#define MOD (1000000007)
#define INF (1e9)
#define INFL (1e18)
 
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
template<class T>using arr=vector<vector<T>>;
template<class T>void pr(T x){cout << x << endl;}
template<class T>void prvec(vector<T>& a){rep(i, a.size()-1){cout << a[i] << " ";} cout << a[a.size()-1] << endl;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main()
{
    ll n; cin >> n;
    ll m = n;

    if(m%2==0){
        n /= 2;
        m /= 2;
        while(m!=1 && m%2==0){
            m /= 2;
        }
    }
    // pr(m);
    for(ll div=3; div*div<m; div+=2){
        if(m%div==0){
            // pr(div);
            n = n*(div-1)/div;
            m/=div;
            while(m!=1 && m%div==0) m/=div;
        }
    }

    if(m>1) n=n*(m-1)/m;

    pr(n);
    return 0;}


Measured memory_bytes: 3116
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
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<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int n;
vl a;

int main(){
	cin>>n;
	a=vl(n);
	for(auto &i:a) cin>>i;
	sort(a.begin(),a.end());
	if(a[0]==0) cout<<0<<endl;
	else{
		ll t=1;
		for(auto i:a){
			if(t<=1000000000000000000/i) t*=i;
			else t=0;
		}
		if(t==0) t=-1;
		cout<<t<<endl;
	}
}

Measured memory_bytes: 4064
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
#include <string>
using namespace std;

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

	vector<int32_t> a(N);
	int32_t cnt_mul2 = 0, cnt_mul4 = 0, cnt_other = 0;
	for (int32_t i = 0; i < N; i++) {
		cin >> a[i];
		if (a[i] % 4 == 0)
			cnt_mul4++;
		else if (a[i] % 2 == 0)
			cnt_mul2++;
	}
	cnt_other = N - cnt_mul2 - cnt_mul4;

	string res;
	if (cnt_other <= cnt_mul4)
		res = "Yes";
	else if (cnt_other == cnt_mul4 + 1 && cnt_mul2 == 0)
		res = "Yes";
	else
		res = "No";

	cout << res << endl;
	return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;

class Main
{

    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();
        int D = sc.nextInt();
        int E = sc.nextInt();

        if (A < 0) {
            System.out.println((A * -1) * C + B * E + D);
        } else {
            System.out.println((B - A) * E);
        }
        if (A == 0) {
            System.out.println(B * E + D);
        }

    }

}



Measured memory_bytes: 26164
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	static int[][] map;
	static int[][] directions8= {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
	static int[][] directions4= {{-1,0},{1,0},{0,-1},{0,1}};
	static int ans;
	static int[] parent;//union-find用
	static int[] rank;//union-find用

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

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long D = sc.nextInt();

		long[] X = new long[N];
		long[] Y = new long[N];

		for(int i = 0;i<N ; i++) {
			X[i] = sc.nextInt();
			Y[i] = sc.nextInt();
		}

		ans = 0;

		for(int i = 0;i<N ; i++) {
			if(D*D >= X[i]*X[i]+Y[i]*Y[i]) {
				ans++;
			}
		}


		System.out.println(ans);
	}

	//素数判定
	public static boolean isPrime(long num) {
		if (num < 2) return false;
		else if (num == 2) return true;
		else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

		double sqrtNum = Math.sqrt(num);
		for (int i = 3; i <= sqrtNum; i += 2)
		{
			if (num % i == 0)
			{
				// 素数ではない
				return false;
			}
		}

		// 素数である
		return true;
	}

	//BFS用に二つの配列を足し算する
	static int[] addArrayElms(int[] a, int[] b) {
		int[] c = new int[a.length];
		for(int i = 0; i < a.length; i++) {
			c[i] = a[i] + b[i];
		}
		return c;
	}

	//	//二分探索
	//k <= num となる最小の配列要素kのインデックスを返す
	static private int binarySearch(long num, long[] orderedArray){
		int lowerBorder = -1;
		int upperBorder = orderedArray.length;
		int mid;

		while(upperBorder - lowerBorder >1) {
			mid = (upperBorder + lowerBorder)/2;
			if(orderedArray[mid]<=num) {
				lowerBorder = mid;
			}else {
				upperBorder = mid;
			}
		}
		return lowerBorder;
	}

	//二分探索
	//k <= num となる最小のList要素kのインデックスを返す
	static private int binarySearch(long num, ArrayList<Long> orderedList){
		int lowerBorder = -1;
		int upperBorder = orderedList.size();
		int mid;

		while(upperBorder - lowerBorder >1) {
			mid = (upperBorder + lowerBorder)/2;
			if(orderedList.get(mid)<=num) {
				lowerBorder = mid;
			}else {
				upperBorder = mid;
			}
		}
		return lowerBorder;
	}

	//aとbの最小公倍数を求める
	public static int gcd(int a, int b) {
		return b == 0 ? a: gcd(b, a % b);
	}
	public static long gcd(long a, long b) {
		return b == 0 ? a: gcd(b, a % b);
	}

	//Union-Find用の配列を要素数nで初期化
	static void ufInit(int n){
		parent = new int[n];
		rank = new int[n];
	}

	//Union-Findの要素の最上位の親（グループ名）を返す
	static int ufFind(int a) {
		if(parent[a]==a) {
			return a;
		}else {
			return ufFind(parent[a]);
		}
	}

	//Union-Find木を連結する
	static void ufUnite(int a, int b) {
		a = parent[a];
		b = parent[b];

		if(a==b) {
			return;
		}
		if(rank[a] > rank[b]){
			parent[b]=a;
		}else {
			parent[a]=b;
			if(rank[a]==rank[b]) {
				rank[b]++;
			}
		}
	}

	static boolean ufSame(int a, int b) {
		return ufFind(a)==ufFind(b);
	}
}


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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout.setf(ios::fixed);
    cout.precision(10);
    
    ll H, W;
    cin >> H >> W;
    
    if (H == 1 || W == 1) {
        cout << 1 << endl;   
    } else {
        ll total = H * W;
        if (total % 2 == 1) total++;
        cout << (total / 2LL) << endl;
    }
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)

int main()
{
	int A, B;
	int need = 0;

	cin >> A >> B;

	if (B > 1) {
		need++;
	}

	B -= A;

	while (B > 0) {
		need++;
		B -= A - 1;
	}

	cout << need << endl;

	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <utility>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
  int n,ma,mb;
  cin >> n >> ma >> mb;
  int a[n];
  int c[n];
  for(int i=0;i<n;i++){
    int p,q;
    cin >> p >> q >> c[i];
    a[i] = p*mb - q*ma;
  }

  int min0 = 4100;
  int cost[8001];
  for(int i=0;i<8001;i++)
    cost[i] = 4100;
  cost[4000] = 0;

  for(int i=0;i<n;i++){
    if(a[i]>0){
      for(int j=8000;j>=4000;j--){
        if(j - a[i]>=4000){
          cost[j] = min(cost[j-a[i]] + c[i] , cost[j]);
        }
      }
    }else if(a[i]<0){
      for(int j=0;j<4000;j++){
        if(j - a[i]<=4000){
          cost[j] = min(cost[j-a[i]] + c[i] , cost[j]);
        }
      }
    }
  }

  for(int i=0;i<n;i++){
    if(a[i]==0)
      min0 = min(min0,c[i]);
  }
  cost[4000]= min0;

  int ans = 4100;
  for(int i=0;i<4001;i++){
    if(cost[i]!=4100 && cost[8000-i]!=4100)
      ans = min(ans,cost[i]+cost[8000-i]);
  }
  ans = min(ans,cost[4000]);

  if(ans == 4100)
    cout << -1 << endl;
  else
    cout << ans << endl;

  return 0;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;

static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const ll INF = 1023456789;

#define REP(i,n)	for(int i=0;i<n;++i)
#define REPR(i,n)	for(int i=n-1;i>=0;--i)
#define FOR(i,s,n)	for(int i=s;i<n;++i)
#define FORR(i,s,n)	for(int i=n-1;i>=s;--i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define F			first
#define S			second

ll n, q, l, r;
string s;
ll d[100001];

int main(int argc, char **argv) {
	cin >> n >> q >> s;
	d[0] = 0;
	REP(i, n-1) d[i+1] = d[i] + (s[i] == 'A' && s[i+1] == 'C' ? 1 : 0);
	REP(i, q) {
		cin >> l >> r;
		--l; --r;
		cout << (d[r] - d[l]) << endl;
	}
	return 0;
}


Measured memory_bytes: 4528