akhauriyash/Code-Regression huggingface dataset:
n, k = map(int, input().split())
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

maximum = max(c[1:])
if maximum < 0:
    print(maximum)
    exit()

used = [False] * (n+1)

ans = 0

for i in range(1, n+1):
    if used[i]:continue
    loop = [i]
    now = i
    while p[now] != i:
        now = p[now]
        loop.append(now)

    L = len(loop)
    S = sum(c[v] for v in loop)
    for a_ind in range(L):
        a = loop[a_ind]
        used[a] = True
        dist_ab = 0
        cost_ab = -c[a]
        for b_ind in range(a_ind, a_ind+L):
            b = loop[b_ind % L]
            cost_ab += c[b]
            max_cost = cost_ab + max(0, S) * ((k - dist_ab) // L)
            ans = max(ans, max_cost)
            dist_ab += 1
            if dist_ab > k:
                break

print(ans)

Measured memory_bytes: 69308
#include<stdio.h>

int main(){
  int j,n,maxv,minv;

  scanf("%d",&n);

  int R[n];

  for(j=0;j<n;j++){
    scanf("%d",&R[j]);
  }
  
  minv = R[0];
  maxv = R[1]-R[0];
  for(j=1;j<n;j++){
    if(maxv<R[j]-minv){
      maxv=R[j]-minv;
    }else{
      maxv=maxv;
    }
    if(minv>R[j]){
      minv=R[j];
    }else{
      minv=minv;
    }
  }
  printf("%d\n",maxv);
  return 0;
}



Measured memory_bytes: 2632
n,k,q=map(int,input().split())
b=[k-q]*n
for i in range(q):
    ai=int(input())
    b[ai-1]+=1
for j in range(n):
    if b[j]>0:
        print('Yes')
    else:
        print('No')
        
'''
n,k,q=map(int,input().split())
a=[int(input()) for _ in range(q)]

point_list=[k-q]*n
for i in range(q):
    point_list[a[i]-1]+=1

for i in range(n):
    if point_list[i]>0:
        print('Yes')
    else:
        print('No')
'''

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

using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second
#define SZ(u) ((int) (u).size())
#define ALL(u) (u).begin(), (u).end()

inline void proc_status()
{
    ifstream t("/proc/self/status");
    cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>()) << endl;
}

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline T read()
{
	register T sum = 0, fg = 1;
	register char ch(getchar());
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') fg = -1;
	for(;  isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) - '0' + ch;
	return sum * fg;
}

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

const int MAXN = (int) 100;

int n;

int a[MAXN + 5];

inline void input()
{
	n = read<int>();
	for(int i = 1; i <= n; ++i) a[i] = read<int>();
}

inline void solve()
{
	int ans = 0;
	for(int i = 2; i <= n; ++i) if(a[i] == a[i - 1]) a[i] = -1, ++ans;
	printf("%d\n", ans);
}

int main()
{
	input();
	solve();

	return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int n,a,b,i,k[20]={0};
  char c[20];
  scanf("%d %d %d",&a,&b,&n);
  for(i=10;i>-1;i--){
    c[i]=a%10-k[i]-b%10+'0';
    if(c[i]<'0'){
      c[i]+=10;
      k[i-1]=1;
    }
    a/=10;
    b/=10;
  }
  for(i=0;i<10;i++){
    if(k[i]&&n&&c[i]-'9'){
      c[i]++;
      n--;
    }
    }//*/
  for(i=0;c[i]=='0';i++);
  printf("%s\n",c+i);
  return 0;
}

Measured memory_bytes: 580
#include<cmath>
#include<cstdio>
using namespace std;
const int maxn=20000+10;
int p[maxn],q[maxn];
int a[maxn],b[maxn];
int n;
int main(){
	int b1,b2,b3,b4;
	scanf("%d",&n);
	for (b1=1;b1<=n;b1++){
		scanf("%d",&p[b1]);
	}
	for (b1=1;b1<=n;b1++){
		q[p[b1]]=b1;
	}
	a[1]=0;b[n]=0;
	for (b1=1;b1<=n-1;b1++){
		if (q[b1]<q[b1+1]){
			a[b1+1]=q[b1+1]-q[b1];
		} else{
			a[b1+1]=0;
		}
		if (q[b1]>q[b1+1]){
			b[b1]=q[b1]-q[b1+1];
		} else{
			b[b1]=0;
		}
	}
	for (b1=2;b1<=n;b1++){
		a[b1]=a[b1-1]+a[b1];
	}
	for (b1=n-1;b1>=1;b1--){
		b[b1]=b[b1+1]+b[b1];
	}
	for (b1=1;b1<=n;b1++){
		a[b1]=a[b1]+b1;
		b[n+1-b1]=b[n+1-b1]+b1;
	}
	for (b1=1;b1<=n-1;b1++){
		printf("%d ",a[b1]);
	}
	printf("%d\n",a[n]);
	for (b1=1;b1<=n-1;b1++){
		printf("%d ",b[b1]);
	}
	printf("%d\n",b[n]);
	
}

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

int main() {
  //入力
  int N;
  cin >> N;
  vector<int> vec(N);
  for(int i=0; i<N; i++) {
    cin >> vec.at(i);
  }
  
  sort(vec.begin(), vec.end());
  int count=0;
  for(int i=0; i<N-1; i++) {
    if(vec.at(i) != vec.at(i+1)) ++count;
  }
  
  cout << count+1 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <map>
#include <queue>
#include <cmath>
#include <iomanip>
#include <set>
#include <functional>

#define MOD (1000000007)

using namespace std;

typedef long long ll;
typedef pair<ll, ll> tup;
const int MAX = 510000;

long long fac[MAX], finv[MAX], inv[MAX];


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


// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

map<ll,ll> prime;//素因数分解でそれぞれの素数がいくつ出てきたかを保存するmap

//O(√n)
//整列済み(mapはkeyで自動で整列される)
void prime_factorize(ll n){
    if(n<=1) return;
    ll l=sqrt(n);
   for(ll i=2;i<=(ll)(l);i++) { //
        if(n%i==0){
            prime_factorize(i);prime_factorize(ll(n/i));return;
        }
    }
    //mapでは存在しないkeyの場合も自動で構築される
    prime[n]++;return;
}


vector<ll> A;
int main() {

    while(true) {
        int n, x;
        cin >> n >> x;

        if(n == 0 && x == 0) return 0;

        ll count = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = i+1; j <= n; j++) {
                for(int k = j+1; k <= n; k++) {
                    if(i + j + k == x) count++;
                }
            }
        }
        cout << count << endl;
    }


    return 0;    
}




Measured memory_bytes: 3068
package main

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

func main() {
	sc := NewScanner()
	N := sc.NextInt()
	mp := map[string]bool{}
	l := uint8(' ')
	for i := 0; i < N; i++ {
		w := sc.NextLine()
		if l != ' ' && l != w[0] {
			fmt.Println("No")
			return
		}
		if _, ok := mp[w]; ok {
			fmt.Println("No")
			return
		}
		mp[w] = true
		l = w[len(w)-1]
	}
	fmt.Println("Yes")

}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r: rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}
func (s *Scanner) NextInt64() int64 {
	v, _ := strconv.ParseInt(s.Next(), 10, 64)
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf)+1; s.p++ {
		if s.p == len(s.buf) || s.buf[s.p] == ' ' {
			v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 0)
			result = append(result, int(v))
			start = s.p + 1
		}
	}

	return result
}
func (s *Scanner) NextInt64Array() []int64 {
	s.pre()
	start := s.p
	result := []int64{}
	for ; s.p < len(s.buf)+1; s.p++ {
		if s.p == len(s.buf) || s.buf[s.p] == ' ' {
			v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 64)
			result = append(result, v)
			start = s.p + 1
		}
	}
	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


Measured memory_bytes: 640
import sys
n=int(input())
if n==1:
  print(0)
  sys.exit()

#まず素数かどうか判定し、素数でない時に使う
import collections
def prime_fact(n):
    a=[]
    while n%2==0:
        a.append(2)
        n//=2
    f=3
    while f*f<=n:
        if n%f==0:
            a.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        a.append(n)
    return a

c=collections.Counter(prime_fact(n))
d=list(c.items())
num=0
for i in range(len(d)):
  z=int(d[i][1])
  j=1
  while z>=0:
    z=z-j
    j+=1
    if z<0:
      break
    else:
      num+=1
print(num)   

Measured memory_bytes: 66008
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std; 
 
#define NOT_FOUND -1
#define rep(i,n) for(int i=0;i<(int)(n); i++)
/*for文のマクロ定義
rep(i,回数){
    処理
}
*/
 
void swap(int *a, int *b){
	*b=*a-*b;
	*a-=*b;
	*b+=*a;
}
 
int sosu_judge(int N){
	/*素数ならば1
	  素数でなければ0を返す
	*/
	int i,j;
 
	if(N==2)   return 1;
	if(N%2==0) return 0;
 
	for(i=3;i<N && N%i!=0;i+=2);
 
	if(i>=N) return 1;
	
	return 0;
}
 
int factorial(int N){  //Nの階乗を求める関数
	int ans=1;
 
	while(N--) ans*=(N+1);
	return ans;
}
 
//クイックソートをする関数
void q_sort(int a[], int first, int last){
    int i,j;
    int x,t;
 
    x = a[(first + last) / 2];
    i = first; j=last;
 
    while(1){
        while( a[i] < x) i++;
        while( x < a[j]) j--;
        
        if( i >= j) break;
        
        swap(&a[i],&a[j]);
        i++; j--;
    }
    if(first < i-1) q_sort(a, first,i-1 );
    if(last > j+1)  q_sort(a, j+1,  last);
}
 
int b_search(int target, int array[],int right, int left){
    /*二分探索を行う関数である。
      戻り値は探索したい値の格納されている位置である。
      もし値が存在しない場合、NOT_FOUND(-1)を返す
    */
    int mid;
    while(left<right){
        mid=(right+left)/2;
        if(array[mid]<target) left =mid+1;
        else                  right=mid;
    }
    if(array[mid]==target) return mid;
    return NOT_FOUND;
}
 
unsigned long combination(int n, int r){
    /*nCrの値を求める関数である。
      値が巨大になる可能性があるため、戻り地はunsigned longである
    */
    int i,j;
    unsigned long a[17];
 
    if(n-r<r) r=n-r;
    if(r==0 ) return 1;
    if(r==1 ) return n;
    if(r>17 ) return 0;
    for(i=1;i<r;i++) a[i]=i+2;
    for(i=3;i<=n-r+1;i++){
        a[0]=i;
        for(j=1;j<r;j++)a[j]+=a[j-1];
    }
    return a[r-1];
}

int main(){
    string S;
    size_t len,tmp;
    int i,j,k;

    cin>>S;

    len=S.length();
    tmp=len;

    for(i=0;i<len/2;i++){
        if(S[i]!=S[len-i-1]){
            cout<<"No"<<endl;
            return(0);
        }
    }
    len=(len-1)/2;

    for(i=0;i<len/2;i++){
        if(S[i]!=S[len-i-1]){
            cout<<"No"<<endl;
            return(0);
        }
    }
    len=tmp;
    for(i=(len+3)/2;i<len;i++){
        if(S[i]!=S[len-i-1]){
            cout<<"No"<<endl;
            return(0);
        }
    }
    cout<<"Yes"<<endl;
    return(0);
}


Measured memory_bytes: 256
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n, a = II(), II()
    print(n*n-a)
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    A()


Measured memory_bytes: 39024
from itertools import combinations_with_replacement as cwp
N,M,Q=map(int, input().split())
A=[]
B=[]
C=[]
D=[]
for i in range(Q):
    a,b,c,d=map(int, input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)
ans=0
for t in cwp(range(1,M+1),N):
    now=0
    for i in range(Q):
        if t[B[i]-1]-t[A[i]-1]==C[i]:
            now+=D[i]
    ans=max(now, ans)
print(ans)

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

using namespace std;

int main(){

	int v[32] = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };
	int n;

	cin>> n;

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, n) for(int i = 1; i < (int)(n); i++)
typedef long long ll;
#define NP next_permutation
#define MP make_pair
#define INT_MAX 1e9

int dp[100];

//最大公約数
int gcd(int x, int y){
  if(x % y == 0) return 1;
  return gcd(y, x % y);
}
//最小公倍数
int lcm(int x, int y){
  return x * y / gcd(x, y);
}
//フィボナッチ数列
//配列dpを-1で初期化する
int fib(int n){
  if(n == 0 || n == 1) return dp[n] = 1;
  if(dp[n] != -1) return dp[n];
  return dp[n] = fib(n - 1) + fib(n - 2);
}
//階乗計算(factorial)
int fact(int n){
  if(n = 1) return 1;
  return n * fact(n - 1);
}
//累乗計算(Exponentiation)
//x**y
ll expo(int x, int y){
  ll ans = 1;
  rep(i, y){
    ans *= x;
  }
  return ans;
}
//桁数
int keta(ll x){
  if(x == 0) return 1;
  int res = 0;
  while(x){
    x /= 10;
    res++;
  }
  return res;
}


int main(){
  int n;
  cin >> n;
  vector<int> v(n), c(n), m(n);
  rep(i, n) cin >> v[i];
  rep(i, n) cin >> c[i];
  rep(i, n) m[i] = v[i] - c[i];

  int ans = -INT_MAX;
  for(int i = 0; i < (1<<n); i++){
  	bitset<20> b(i);
  	int cost = 0;
  	rep(j, n){
  		if(b.test(j)) cost += m[j];
  	}
  	ans = max(ans, cost);
  }
  cout << ans << endl;
}


/*





















*/


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) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			String str;
			String[] arr;
			int a,b,c;
			int count=0;
			while((str=br.readLine())!=null){
				arr=str.split(" ");
				a=Integer.parseInt(arr[0]);
				b=Integer.parseInt(arr[1]);
				c=Integer.parseInt(arr[2]);
				for(int i=a;i<=b;i++) {
					if((c%i)==0)count++;
				}
				break;
			}
			System.out.println(count);
			br.close();
		} catch (IOException e) {
			// TODO 自動生成された catch ブロック
			e.printStackTrace();
		}

	}
}

Measured memory_bytes: 17032
//
// 長方形の面積と周の長さを求める
//
#include<iostream>
using namespace std;
 
int main(void)
{
    int a; // 縦の長さ
    int b; // 横の長さ 

    // 入力情報取得
    cin >> a;
    cin >> b;

    // 面積と周の長さを計算し出力する
    cout << a * b << " " << 2 * ( a + b)  << endl;

    return 0;		 
}


Measured memory_bytes: 3088
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define md 1000000007
#define ld long double
#define pi 3.14159265359
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n, i = 0, j= 0, k = 0, l = 0, m = 0, a = 0, b = 0, sum = 0, x = 0, y = 0, z = 0, c, p;
    cin >> a >> b;
    cout << a*b;



    return 0;
}


Measured memory_bytes: 3648
import sys

N, M = map(int, input().split())

S = []
C = []
for m in range(M):
  s, c = map(int, input().split())
  S.append(s)
  C.append(c)

for i in range(10**N):
  tes = str(i)

  if len(tes) != N:
    continue
  
  flag = True
  for s, c in zip(S, C):
    if tes[s-1] != str(c):
      flag = False
  if flag:
    print(tes)
    sys.exit()


print(-1)

Measured memory_bytes: 9144
import sys
line = sys.stdin.readline().strip()
n, z, w = map(int, line.split()[:3])
line = sys.stdin.readline().strip()
a = list(map(int, line.split()[:n]))
#print(n, z, w)
#print(a)

if n > 2:
  result = max(
    abs(a[-1] - w),
    abs(a[-2] - a[-1])
  )
else:
  result = abs(a[-1] - w)

print(result)


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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;


const ll LongINF=1e13+7;
const int INF=1e9+7;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template <class T, class Y>T GCD(T a, Y b){if(a<b){int c=a;a=b;b=c;}if (a % b == 0){return b;}return GCD(b, a % b);}
void clear(queue<pair<int, int>> &q){queue<pair<int, int>> empty;swap(q, empty);} //queueの中身の型は適時変更を忘れない

#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define rv reverse
#define ALL(a) (a).begin(),(a).end()

int main(){
    int N,M;
    cin>>N>>M;
    if(N==M)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

    return 0;
}

//a=97,z=122

Measured memory_bytes: 256
n=int(input())
a =[]
for i in range(n):
    a.append(int(input()))
 
a.sort()
s=sum(a)
if s%10==0:
    for i in a:
        if i%10>0:
            s-=i
            break
if s%10>0:
    print(s)
else:
    print(0)
 

Measured memory_bytes: 3060
# https://atcoder.jp/contests/agc013/tasks/agc013_a


def solve():
    n = int(input())
    A = [int(i) for i in input().split()]
    ans = 0
    cur = []
    flag = None
    for a in A:
        if not cur:
            cur.append(a)
            continue
        elif cur[-1] == a:
            cur.append(a)
        elif flag is None:
            if cur[-1] > a:
                flag = False
            elif cur[-1] < a:
                flag = True
            cur.append(a)
            continue
        elif flag:  # increasing
            if cur[-1] > a:
                ans += 1
                cur = [a]
                flag = None
            else:
                cur.append(a)
        elif not flag:  # decreasing
            if cur[-1] < a:
                ans += 1
                cur = [a]
                flag = None
            else:
                cur.append(a)
    if cur:
        ans += 1
    print(ans)


solve()


Measured memory_bytes: 90276
import math

A,B = map(int,input().split())
G = math.gcd(A,B)

N = G
#素因数分解
sep = []
for i in range(2,int(math.sqrt(N))+2,1):
    if N % i ==0:
        count = 0
        while N % i == 0:
            N = N//i
            count += 1
        sep.append([i,count])
if N != 1:
    sep.append([N,1])

print(len(sep)+1)

Measured memory_bytes: 9128
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define reps(i,a,b) for(int i=a;i<b;++i)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<typename T> inline bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T &a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U &u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U &u,const V... v){for(auto &e:u)fill_v<T>(e,v...);}

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

    int n, m, l;
    cin >> n >> m >> l;
    auto a = make_vec<ll>(n, m);
    auto b = make_vec<ll>(m, l);
    auto c = make_vec<ll>(n, l);
    rep(i, n) rep(j, m) cin >> a[i][j];
    rep(j, m) rep(k, l) cin >> b[j][k];
    rep(i, n) rep(k, l) rep(j, m) c[i][k] += a[i][j] * b[j][k];
    rep(i, n) rep(k, l) cout << c[i][k] << (k == l-1 ? '\n' : ' ');
}



Measured memory_bytes: 3272
//* AuThOr GaRyMr *//
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define niv vector<int>
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define KEEP while(1)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
typedef pair<mp,mp> superpair;
int up_bound,low_bound;
vector<int> each[200000+10];
int main() {
	int h,w;
	cin>>h>>w;
	int n;
	cin>>n;
	rep(i,n){
		int x,y;
		scanf("%d %d",&x,&y);
		each[y].PB(x);
	}
	int res;
	low_bound=h;
	up_bound=1;
	for(auto it: each[1]){
		low_bound=min(low_bound,it-1);
	}
	res=low_bound;
	rb(i,2,w){
		up_bound++;
		sort(each[i].begin(),each[i].end());
		for(auto it: each[i]){
			if(it>low_bound) break;
			if(it<up_bound) continue;
			if(it==up_bound) up_bound++;
			else low_bound=it-1; 
		}
		res=low_bound;
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 8704
import java.util.*;
public 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();
		if(A + B >= C) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}


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

int main() {
	vector<int>x;
	x.push_back(0);
	int N = 0;
	int num = 0;
	int counter = 0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> num;
		x.push_back(num);
	}

	for (int i = 1; i < x.size(); i++) {
		if (x[i] % 2 != 0 && i % 2 != 0) {
			counter++;
		}
	}
	cout << counter;
	return 0;
}

Measured memory_bytes: 3588
#include <stdio.h>
#include <iostream>

using namespace std;

int main()
{int a,b;
char op;
cin >>a>>op>>b;
switch(op){
case '+':
    cout << a+b;
break;
case '-':
    cout << a-b;
break;
default:
    cout << "wrong";
}

   return 0;
}

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

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

    if ((a + b) % 2 == 0)
    {
        cout << (a + b) / 2 << endl;
    }
    else
    {
        cout << (a + b) / 2 + 1 << endl;
    }

    return 0;
}

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

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

using namespace std;

template <class T, class U> void amax(T& x, U y) {if (x < y) x = y;}

int main(void)
{
    const int N_MAX = 100;
    const int W_MAX = 10000;
    int N, W;
    int v[N_MAX];
    int w[N_MAX];
    cin >> N >> W;
    REP(i, N) cin >> v[i] >> w[i];
    int dp[W_MAX + 1][N_MAX + 1];
    REP(i, W + 1) dp[i][0] = 0;
    REP(j, N + 1) dp[0][j] = 0;
    FOR(i, 1, W + 1) FOR(j, 1, N + 1) {
        dp[i][j] = dp[i][j - 1];
        if (i - w[j - 1] >= 0) {
            amax(dp[i][j], dp[i - w[j - 1]][j - 1] + v[j - 1]);
        }
    }
    cout << dp[W][N] << endl;
    return 0;
}


Measured memory_bytes: 7036
/******************************************
* AUTHOR : AAYUSH GARG*
* NICK : aayushgarg_03 *
* INSTITUTION : BIT MESRA *
******************************************/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define mod 1000000007
#define dd double
#define ld long double
#define for0(i, n) for(ll i = 0; i < n; i++)
#define for2(a,b,c) for(ll i=a;i<b;i+=c)
#define for1(i,n) for(ll i=1;i<=n;i++)
#define vec vector<ll>
#define pb push_back
#define mp make_pair
#define pii pair<ll,ll>
#define VP vector< pii >
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define F first
#define S second
#define ascii(c) (int)char (c)
#define all(v) (v).begin(),(v).end()
#define Sort(v) sort(v.begin(), v.end(), sortbysec)
#define MEM(a, b) memset(a, (b), sizeof(a))
#define N 1000000

ll prime[N];

ll mulmod(ll a, ll b, ll m) 
{ 
    ll res = 0;  
    a = a % m; 
    while (b > 0) 
    { 
       
        if (b % 2 == 1) 
            res = (res + a) % m; 
  
        
        a = (a * 2) % m; 
  
        
        b /= 2; 
    } 
  
    return res % m; 
} 

ll modInverse(ll a, ll m) 
{ 
    ll m0 = m; 
    ll y = 0, x = 1; 
  
    if (m == 1) 
      return 0; 
  
    while (a > 1) 
    { 
        
        ll q = a / m; 
        ll t = m; 
  
        m = a % m, a = t; 
        t = y; 
  
        
        y = x - q * y; 
        x = t; 
    } 
  
    
    if (x < 0) 
       x += m0; 
  
    return x; 
} 

ll power(ll x, ll y, ll p) 
{ 
    ll res = 1;     
  
    x = x % p;  
  
    while (y > 0) 
    { 
        
        if (y & 1) 
            res = (res*x) % p; 
  
         
        y = y>>1; 
        x = (x*x) % p;   
    } 
    return res; 
}

void sieve() {
    for(ll i = 0;i < N;i++)
        prime[i] = 1;
    prime[0] = 0;
    prime[1] = 0;
    for(ll i = 2;i*i < N;i++) {
        if(prime[i] == 0)
            continue;
        for(ll j = i*i;j < N;j+=i) {
            prime[j] = 0;
        }
    }
    for(ll i = 1;i < N;i++)
        prime[i] += prime[i-1];
}



bool sortbysec(const pair<ll,ll> &a, const pair<ll,ll> &b) 
{ 
    return (a.second < b.second); 
} 

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

ll n;
cin>>n;

ll a[n][3];
ll dp[n+1][3];

for0(i,n)
{
	for0(j,3)
	 cin>>a[i][j];
}

dp[0][0]=0;
dp[0][1]=0;
dp[0][2]=0;

for(ll i=1;i<=n;i++)
{
	dp[i][0] = a[i-1][0] + max(dp[i-1][1],dp[i-1][2]);

	dp[i][1] = a[i-1][1] + max(dp[i-1][0],dp[i-1][2]);

	dp[i][2] = a[i-1][2] + max(dp[i-1][0],dp[i-1][1]);
}

ll maxx = -N;

	for0(j,3)
	 maxx = max(maxx,dp[n][j]);

	 cout<<maxx;
	 



return 0;
}


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  map<long long, int> cnt;
  long long sm = 0;
  ++cnt[sm];
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    sm += x;
    ++cnt[sm];
  }
  long long res = 0;
  for (const auto &x : cnt) {
    res += x.second * (x.second - 1ll) / 2;
  }
  cout << res << '\n';
  return 0;
}


Measured memory_bytes: 16000
#include <iostream>

#define MAXN 1120
#define MAXP 187
#define MAXK 14

using namespace std;

int dp[MAXN+1][MAXP+1][MAXK+1];

int Prime(int p){
  int i,f;
  f = 0;
  if(p == 2) return 1;
  if(p % 2 == 0) return 0;
  for(i=3;i*i <= p;i += 2){
    if(p % i == 0) f = 1;
  }

  if(f == 0) return 1;
  else return 0;
}

int main(){
  int prime[MAXP+1],cnt,n,kk;
  cnt = 0;
  for(int i=2;i <= MAXN;i++){
    if(Prime(i)) prime[cnt++] = i;
  }
  
  for(int i=0;i <= MAXN;i++){
    for(int j=0;j < MAXP;j++){
      for(int k=0;k <= MAXK;k++){
        dp[i][j][k] = 0;
      if(prime[j] == i) dp[i][j][1] = 1;
      }
    }
  }
 for(int j=1;j < MAXP;j++){
  for(int i=0;i<=MAXN;i++){
      for(int k=1;k<=MAXK;k++){
        dp[i][j][k] += dp[i][j-1][k];
        if(i >= prime[j]) dp[i][j][k] += dp[i-prime[j]][j-1][k-1];
      }
    }
  }

  
  while(cin >> n >> kk){
    if(!(n|kk)) break;
    cout << dp[n][MAXP-1][kk] << endl;
  }

  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define MAX 100000
using namespace std;
int W, H;

int xy2l(int x, int y){
  return W*y + x;
}
pair<int, int> l2xy(int l){
  pair<int, int> res;
  res.first = W%l;
  res.second = W/l;
  return res;
}

int main(void){
  ios::sync_with_stdio(false);
  cin.tie(0);
  while(cin >> W >> H, W | H){
    vector< vector<int> > v(H*W, vector<int>(W*H, MAX));
    for(int i = 0; i < 2*H-1; i++){
      if(i % 2 == 0){
        for(int j = 0; j < W-1; j++){
          int wall; cin >> wall;
          if(wall == 0){
            v[xy2l(j, i/2)][xy2l(j+1, i/2)] = 1;
            v[xy2l(j+1, i/2)][xy2l(j, i/2)] = 1;
          }
        }
      }
      if(i % 2 == 1){
        for(int j = 0; j < W; j++){
          int wall; cin >> wall;
          if(wall == 0){
            v[xy2l(j, i/2)][xy2l(j, i/2+1)] = 1;
            v[xy2l(j, i/2+1)][xy2l(j, i/2)] = 1;
          }
        }
      }
    }

    vector<bool> used(H*W, false);
    vector<int> d(H*W, MAX);
    d[0] = 0;
    while(1){
      int s = -1;
      for(int u = 0; u < H*W; u++){
        if(!used[u] && (s == -1 || d[u] < d[s])) s = u;
      }
      if(s == -1) break;
      used[s] = true;
      for(int u=0; u < H*W; u++){
        d[u] = min(d[u], d[s] + v[s][u]);
      }
    }
    //for(int i = 0; i < d.size(); i++) cout << d[i] << endl;
    if(d[d.size()-1] == MAX) cout << 0 << endl;
    else cout << d[d.size()-1]+1 << endl;
  }
  return 0;
}

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

n, a, b, c = [int(x) for x in input().split()]
score = {}
score["A"] = a
score["B"] = b
score["C"] = c     
S = [input().rstrip() for _ in range(n)]
ans = []

for i in range(n - 1):
    s = S[i]
    next_s = S[i + 1]
    s1 = s[0]
    s2 = s[1]
    if score[s1] == 0 and score[s2] == 0:
        print("No")
        sys.exit()
    elif score[s1] == 0:
        ans.append(s1)
        score[s1] += 1
        score[s2] -= 1
    elif score[s2] == 0:
        ans.append(s2)
        score[s1] -= 1
        score[s2] += 1
    elif score[s1] == 1 and score[s2] == 1:
        if next_s == s:
            ans.append(s1)
            score[s1] += 1
            score[s2] -= 1
        elif s1 in next_s:
            ans.append(s1)
            score[s1] += 1
            score[s2] -= 1
        else:
            ans.append(s2)
            score[s2] += 1
            score[s1] -= 1
    else:
        if score[s1] >= score[s2]:
            ans.append(s2)
            score[s2] += 1
            score[s1] -= 1
        else:
            ans.append(s1)
            score[s1] += 1
            score[s2] -= 1
s = S[-1]
s1 = s[0]
s2 = s[1]

if score[s1] == 0 and score[s2] == 0:
        print("No")
        sys.exit()
elif score[s1] == 0:
    ans.append(s1)
    score[s1] += 1
    score[s2] -= 1
elif score[s2] == 0:
    ans.append(s2)
    score[s1] -= 1
    score[s2] += 1
else:
    ans.append(s1)
print("Yes")
for i in ans:
    print(i)






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

int main() {
  ll n,m; cin >> n >> m;
  vector<ll>v(m);
  ll sum = 0;
  for(ll i = 0; i<m; i++){
    cin >> v[i];
    sum+=v[i];
  }
  //ll sum = 0;
  //for(ll i = 0; i<m; i++){
    //sum+=v[i];
  //}
  //ll sum = accumulate(v.begin(),v.end(),0);
  if(n>=sum) cout << n-sum << endl;
  else cout << "-1" << endl;
  
    
  
  return 0;
}

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

#define ll long long
const int mod = 1e9 + 7;

vector <int> adj[100005];
ll int dp[100005][2];


ll int dfs(int node, int pn, int colour)
{
  if(dp[node][colour] != -1)
    return dp[node][colour];

  dp[node][colour] = 1;

  for(int i=0;i<adj[node].size();i++)
    if(adj[node][i] != pn)
    {
      if(colour)
      {
        dp[node][colour] = (dp[node][colour] * dfs(adj[node][i], node, 1-colour)) % mod;
      }
      else
      {
        ll int res = (dfs(adj[node][i], node, colour) + dfs(adj[node][i], node, 1-colour)) % mod;
        dp[node][colour] = (dp[node][colour] * res) % mod;
      }
    }

  return dp[node][colour] % mod;
}


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

  memset(dp, -1, sizeof dp);
  int n, x, y;
  cin>>n;

  for(int i=0;i<n-1;i++)
  {
    cin>>x>>y;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }

  cout<<(dfs(1, -1, 0) + dfs(1, -1, 1)) % mod <<endl;


  return 0;
}


Measured memory_bytes: 17024
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

long long int power(long long int x, long long int n, long long int M) {
	long long int tmp = 1;

	if (n > 0) {
		tmp = power(x, n / 2, M);
		if (n % 2 == 0) tmp = (tmp*tmp) % M;
		else tmp = (((tmp*tmp) % M)*x) % M;
	}
	return tmp;
}

long long int N, M, K, Q, W, H, L, R;
long long int ans;

long long int num[200001];
set < long long int >s;
long long int box;
long long int l, r;
long long int comb;
long long int mi;

int main() {
	//ios::sync_with_stdio(false);
	l = -1;
	cin >> N;
	for (int i = 0; i <= N; i++) {
		cin >> num[i];
		if (!(s.insert(num[i]).second))box = num[i];
	}
	for (int i = 0; i <= N; i++) {
		if(num[i]==box){
			if (l == -1) {
				l = i;
			}
			else r = i;
		}
	}
	comb = N + 1;
	mi = 1;
	cout << comb - mi << endl;
	for (int i = 2; i <= N+1; i++) {
		comb = comb * (N - i + 2);
		comb %= MOD;
		comb *= power(i, MOD - 2, MOD);
		comb %= MOD;
		if (i + (r - l)-1 <= N) {
			mi = mi*(N - (r - l) - i + 2);
			mi %= MOD;
			mi *= power(i - 1, MOD - 2, MOD);
			mi %= MOD;
		}
		else mi = 0;
		cout << (comb + MOD - mi) % MOD << endl;
	//	cout << mi << endl;
	}
	return 0;
}

Measured memory_bytes: 6656
import java.io.*;

public class Main{
    public static void main(String[]args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true){
            String[] str = br.readLine().split(" ");
            int a = Integer.parseInt(str[0]);
            int b = Integer.parseInt(str[2]);
            if(str[1].equals("?")){
                break;
            }else if( str[1].equals("+") ){
                System.out.println(a + b);

            }else if( str[1].equals("-") ){
                System.out.println(a - b);

            }else if( str[1].equals("*") ){
                System.out.println(a * b);

            }else if( str[1].equals("/") ){
                System.out.println(a / b);
            }else break;
        }



    }
}

Measured memory_bytes: 24296
A = [[int(a) for a in input().split()] for _ in range(3)]
N = int(input())
B = [int(input()) for _ in range(N)]
    
for i in range(N):
    for j in range(3):
        for k in range(3):
            if B[i] == A[j][k]:
                A[j][k] = 0

L = []
for i in range(3):
    L.append(A[i])
for j in range(3):
    L.append([])
    for i in range(3):
        L[-1].append(A[i][j])

if [0, 0, 0] in L:
    ans = "Yes"
elif A[0][0] == 0 and A[1][1] == 0 and A[2][2] == 0:
    ans = "Yes"
elif A[0][2] == 0 and A[1][1] == 0 and A[2][0] == 0:
    ans = "Yes"
else:
    ans = "No"
print(ans)

Measured memory_bytes: 3064
#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <bitset>

#include <queue>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <fstream>
#include <random>
//#include <time.h>
#include <ctime>
#pragma endregion //#include
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)
#define ALL(X) X.begin(), X.end()
/////////
#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef std::pair<LL,LL> PLL;//
typedef std::pair<int,int> PII;//
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)1e18+20;
const LD PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;

void solve(){
	string str1,str2;
	cin >> str1;
	str2 = str1;
	reverse(str2.begin(),str2.end());
	int size = str2.size();
	string word = "bpdq";
	for(int i=0;i<size;++i){
		for(int j=0;j<4;++j){
			if( str2[i] == word[j] ){
				str2[i] = word[(j+2)%4];
				break;
			}
		}
	}
	
	cout << (str1==str2?"Yes":"No") << endl;
}

#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}
#pragma endregion //main()

Measured memory_bytes: 512
#include<iostream>
#include <iomanip>
#include <ios>
#include <vector>
#include <string>
#include <algorithm>
#include <string>
#include<limits>
#include<cstdlib>
#include<functional>
#include<cassert>
#include <cstdio>
#include <stack>
#include <queue>
#include <map>
#define fi(p) for(int i=0;i<(p);i++)
#define ce(d) cout<<d<<endl;
#define ll long long
#define sorts(c) sort((c).begin(),(c).end());

using namespace std;

void solve() {
	ll N;

	cin >> N;

	vector<ll> B(N-1);

	fi(N-1) {
		cin >> B[i];
	}

	ll res = B[0];

	for (int i = 0; i < N - 2; i++) {

		if (B[i] <= B[i + 1]) {
			res += B[i];
		}
		else {
			res += B[i + 1];
		}
	}
	
	if (N == 2) {
		res += B[0];
	}

		if (N > 2) {
		res += B[B.size() - 1];
	}
	
	ce(res);
}



int main()
{

	solve();

	int a;//止める用
	cin >> a;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>

using namespace std;

typedef long long int ll;
typedef long int li;


int main(void){
    li n,m;
    li ans=0;
    cin >> n >> m;
    li x[m];
    for(li i=0;i<m;i++)cin >> x[i];
    sort(x,x+m);
    li y[m-1];
    for(li i=0;i<m-1;i++)y[i]=x[i+1]-x[i];
    sort(y,y+m-1);
    for(li i=0;i<m-n;i++)ans+=y[i];
    cout << ans << endl;
}



Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
const int inf = (1 << 30) - 1;
const ll infll = (1LL << 61) - 1;

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

// 0 - indexed
template <typename Monoid>
struct Segmenttree
{
    using F = function<Monoid(Monoid, Monoid)>;
    const Monoid e;
    const F f;

    int sz;
    vector<Monoid> seg;

    // size, operator, unit
    Segmenttree(int N, const F f, const Monoid e) : f(f), e(e)
    {
        sz = 1;
        while (sz < N)
            sz *= 2;
        seg.assign(2 * sz - 1, e);
    }

    void set(int k, const Monoid &x) { seg[k + sz - 1] = x; }
    void build()
    {
        for (int k = sz - 2; k >= 0; k--)
        {
            seg[k] = f(seg[2 * k + 1], seg[2 * k + 2]);
        }
    }

    void update(int k, const Monoid &x)
    {
        k += sz - 1;
        seg[k] = x;
        while (k > 0)
        {
            k = (k - 1) / 2;
            seg[k] = f(seg[k * 2 + 1], seg[k * 2 + 2]);
        }
    }

    Monoid sub_query(int a, int b, int k, int l, int r)
    {
        if (r <= a || b <= l)
            return e;

        if (a <= l && r <= b)
            return seg[k];
        else
        {
            Monoid vl = sub_query(a, b, k * 2 + 1, l, (l + r) / 2);
            Monoid vr = sub_query(a, b, k * 2 + 2, (l + r) / 2, r);
            return f(vl, vr);
        }
    }

    // [l, r)
    Monoid query(int l, int r)
    {
        return sub_query(l, r, 0, 0, sz);
    }

    Monoid operator[](const int &k) const
    {
        return seg[k + sz];
    }
};

int main()
{
    int N;
    cin >> N;
    Segmenttree<int> seg(N, [](int a, int b) { return gcd(a, b); }, 0);
    for (int i = 0; i < N; i++)
    {
        int a;
        cin >> a;
        seg.update(i, a);
    }
    seg.build();

    int ans = 0;
    for (int i = 0; i < N; i++)
    {
        ans = max(gcd(seg.query(0, i), seg.query(i + 1, N)), ans);
    }
    cout << ans << endl;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repeat(i,s,n) for(int (i)=s; (i)<(n); (i)++)
#define revrep(i,n) for(int (i)=(n)-1;i>=0; i--)

ll man_dist(ll x1, ll y1, ll x2, ll y2) {
  return abs(x1-x2)+abs(y1-y2);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<setprecision(std::numeric_limits<float>::max_digits10);
  int n;
  cin>>n;
  vector<ll> x(n);
  vector<ll> y(n);
  vector<ll> p(n);
  rep(i,n)cin>>x[i]>>y[i];
  rep(i,n) p[i]=(abs(x[i])+abs(y[i]))%2;
  rep(i,n) {
    if(p[i]!=p[0]) {
      cout << "-1" << endl;
      return 0;
    }
  }
  vector<ll> ds;
  ll t = 1;
  rep(i,39) {
    ds.push_back(t);
    t*=2;
  }
  if(p[0]==0) ds.push_back(1);
  sort(ds.begin(),ds.end());
  reverse(ds.begin(),ds.end());
  cout << ds.size() << endl;
  for(auto& d : ds) {
    cout << d << " ";
  }
  cout << endl;
  rep(i,n) {
    stringstream ss;
    ll cx=0;
    ll cy=0;
    for(auto& d : ds) {
      vector<tuple<ll,char, ll, ll>> t;
      t.push_back(make_tuple(man_dist(x[i],y[i],cx+d,cy),'R',cx+d,cy));
      t.push_back(make_tuple(man_dist(x[i],y[i],cx-d,cy),'L',cx-d,cy));
      t.push_back(make_tuple(man_dist(x[i],y[i],cx,cy+d), 'U',cx,cy+d));
      t.push_back(make_tuple(man_dist(x[i],y[i],cx,cy-d), 'D',cx,cy-d));
      sort(t.begin(),t.end());
      ll md;
      char direction;
      ll nx,ny;
      tie(md,direction,nx,ny)=t[0];
      ss<<direction;
      cx=nx;
      cy=ny;
    }
    cout << ss.str() << endl;
  }
  return 0;
}


Measured memory_bytes: 384
# 2019/05/19
# AtCoder Beginner Contest 126 - C

import math

# Input
n, k = map(int,input().split())

# Init
bl = list()
for i in range(18):
    bl.append(2 ** i)

# Calc
ans = 0
for i in range(1, n + 1):

    for j in range(18):
        wval = i * bl[j]
        if wval >= k:
            break
    ans += (1 / n) * (1 / bl[j])

# Output
print(ans)


Measured memory_bytes: 3060
import java.util.Scanner;


import java.util.Comparator;
import java.util.Arrays;
import java.util.ArrayList;



public class Main {
	static long [][] createdp(int n) {
		long [][] dp = new long [n][n];
		for (int i = 0; i<n;i++) {
			dp[0][i] = 1;
			dp[i][0] = i+1;
		}
		for(int i = 1; i<n;i++) {
			for(int j = 1; j<n;j++) {
				dp[i][j] = dp[i][j-1]+dp[i-1][j];
				if(dp[i][j] > 1000*1000*1000 + 7) {
					dp[i][j] -= 1000*1000*1000 + 7;
				}
			}
		}
		return dp;
	}
	static int result(int n, int k, int i, long [][] dp){
		if(i > (n-k+1)) {
			return 0;
		}
		else if(i == n-k+1) {
			if(k == i) {
				return 1;
			}else {
				return (int)dp[i-1][k-i-1];
			}
			
		}
		else if(k == i) {
			return (int)dp[i][n-k-i];
		}
		else {
			long tmp;
			tmp = dp[i][n-k-i] * dp[i-1][k-i-1] % (1000*1000*1000 + 7);
			return (int)tmp;
		}

	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		long [][] dp = new long [n][n];
		if(k == n) {
			System.out.println(1);
			for(int i = 2; i<=k ;i++) {
				System.out.println(0);
			}
		}else {
			dp = createdp(n);
			for(int i = 1; i<=k ;i++) {
				System.out.println(result(n, k, i, dp) );
			}
		}
		
		
	}
}


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

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> kind(M, 0);

  rep(i, N) {
    int K;
    cin >> K;
    rep(j, K) {
      int A;
      cin >> A;
      A--;
      kind[A]++;
    }
  }

  int ans = 0;
  rep(i, M) if (kind[i] == N) ans++;

  cout << ans << endl;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include <unordered_map>
//#include"testlib.h"
#define endl "\n"
#define all(v) v.begin(),v.end()
#define allr(s) s.rbegin(),s.rend()
#define RT(s) return cout<<s,0
#define watch(x) cout << (#x)<<" = "<<x<<endl
#define sz(s)    (int)(s.size())
#define PI acos(-1)
#define EPS 1e-100
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
int dy[] = { 1, -1, 0, 0, -1, 1, 1, -1 };
int dx[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
void file() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
#else
	//freopen("street.in", "r", stdin);
	//freopen("out.txt", "w", stdout);
#endif
}
void fast() {
	std::ios_base::sync_with_stdio(0);
	cin.tie(NULL);
}


int main() {
//	file();
	fast();
	int n; cin >> n;
	vi v1(n);
	for (auto& it : v1)
		cin >> it;
	vi arr(n);
	iota(all(arr), 1);
	int dif = 0;
	for (int i = 0; i < n; i++)
		if (v1[i] != arr[i])
			dif++;
	if (dif == 2 || dif == 0)
		cout << "YES" << endl;
	else cout << "NO" << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const auto INF = (ll)1e9;
using v = vector<ll>;
using m = map<int,int>;
using vv = vector<v>;

int main(){
    int n,k;
    cin >> n >> k;
    auto a = v(n,0);
    for (int i = 0; i < n; i++)
    {
        int t =0;
      	cin >> t;
        a[t-1]++;
    }
    sort(a.begin(),a.end(),greater<ll>());
    auto ans =0;
    for (int i = 0; i < a.size(); i++)
    {	
      	if(i<k) continue;
      	else if(a[i] == 0) break;
        ans +=a[i];
    }
    cout << ans;
    

}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void) {
  int n, c, maxt = 200001;
  cin >> n >> c;
  vector<vector<int> > memo(c, vector<int>(maxt, 0));
  for (int i = 0; i < n; i++) {
    int s, t, cn;
    cin >> s >> t >> cn;
    for (int j = s * 2 - 1; j <= t * 2; j++) {
      memo[cn - 1][j] = 1;
    }
  }
  int ans = 0;
  for (int i = 0; i < maxt; i++) {
    int sum = 0;
    for (int j = 0; j < c; j++) {
      sum += memo[j][i];
    }
    ans = max(ans, sum);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 24576
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<cmath>
#include<queue>
#include<cstring>
#include<climits>
#include<sstream>
#include<deque>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<bitset>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;

int main() {
  int n;
  cin >> n;
  vector<ll> a(n);
  ll sum = 0;
  rep(i,n) {
    cin >> a[i];
    sum += a[i];
  }
  ll maxi = LLONG_MAX;
  ll cur = 0;
  rep(i,n-1) {
    cur += a[i];
    maxi = min(maxi,llabs(cur-(sum-cur)));
  }
  cout << maxi << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    map<int, int> mm;
    for (int i = 0; i < m; ++i) {
        long b, c;
        cin >> b >> c;
        mm[c] += b;
    }
    vector<pair<int, int>> v(mm.rbegin(), mm.rend());
    sort(a.begin(), a.end());
    long answer = 0;
    for (int i = 0, j = 0; i < n; ++i) {
        if (j < v.size() && v[j].first > a[i] && v[j].second > 0) {
            answer += v[j].first;
            if (--v[j].second == 0) ++j;
        } else {
            answer += a[i];
        }
    }
    cout << answer << endl;
}


Measured memory_bytes: 6144
S = list(input())
N = int(S[-1])
if N == 2 or N == 4 or N == 5 or N == 7 or N == 9:
    print("hon")
elif N == 0 or N == 1 or N == 6 or N == 8:
    print("pon")
else:
    print("bon")

Measured memory_bytes: 9176
#ifndef Local
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/STACK:1024000000,1024000000")
#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define popCnt(x) (__builtin_popcountll(x))
typedef long long Long;

const int N = 2e4 + 5;

int perm[N];
int a[N];
int b[N];

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifdef Local
  freopen("test.in", "r", stdin);
#else
#define endl '\n'
#endif

  int n;
  cin >> n;

  for (int i = 1; i <= n; ++i) {
    cin >> perm[i];
  }

  for (int i = 1; i <= n; ++i) {
    a[i] = i * N;
    b[i] = (n - i + 1) * N;
  }

  for (int i = 1; i < n; ++i) {
    int x = perm[i];
    int y = perm[i + 1];
    int delta = max((a[x] + b[x]) - (a[y] + b[y]) + 1, 0);
    a[y] += delta / 2;
    b[y] += (delta + 1) / 2;
  }

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


Measured memory_bytes: 896