akhauriyash/Code-Regression huggingface dataset:
import sys
import math

def isExponential(i : int) -> bool:
    #math.ceil(math.sqrt(i))+1
    for j in range(2,i):       
        devidend = i
        devisor = j
        #print(devidend,devisor,"inFor") 
        while 1:
            #print(devidend,devisor,"inWhile")
            if devidend % devisor != 0:
                break
            else:
                if devidend == devisor:
                    return True
                else:
                    devidend //= devisor
    return False

x = int(input())
if x == 1:
    print(1)
for i in range(x,0,-1):
    if isExponential(i) == True:
        print(i)
        #print("wtf")
        break

Measured memory_bytes: 3060
#include<algorithm>
#include<math.h>
#include<cstdio>
#include<ctype.h>
#include<stdio.h>
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

int main() {
	ll N;
	cin >> N;
	vector<ll>v(N);
	ll sum = 0;
	ll cnt = 0;
	ll ans = 1000000000000000;
	for (ll i = 0; i < N; ++i)
	{
		cin >> v[i];
		sum += v[i];
	}
	for (ll i = 0; i < N; ++i) {
		cnt += v[i];
		if (i + 1 < N)
			ans = min(ans, abs(sum - cnt * 2));


	}
	cout << ans << endl;
}


Measured memory_bytes: 1792
#include<stdio.h>
int main(void)
{
	int n,m,a[101][101],b[101],c,i,j;
	scanf("%d %d", &n, &m);
	for(i=0; i<n; i++)
	{
		for(j=0; j<m; j++)
		scanf("%d", &a[i][j]);
	}
	for(i=0; i<m; i++)
	scanf("%d", &b[i]);
	for(i=0; i<n; i++)
	{
		c=0;
		for(j=0; j<m; j++)
		c+=a[i][j]*b[j];
		printf("%d\n", c);
	}
	
	return 0;
}


Measured memory_bytes: 2140
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

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

func getString() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, 1000000)

	N := getInt()
	a := make([]int, N)
	for i := 0; i < N; i++ {
		a[i] = getInt()
	}
	sort.Sort(sort.Reverse(sort.IntSlice(a)))

	sel := []int{0, 0}

	selected := 0
	cnt := 1
	for i := 1; i < len(a); i++ {
		if a[i] == a[i-1] {
			cnt++
		} else {
			cnt = 1
		}
		if cnt == 2 {
			sel[selected] = a[i-1]
			selected++
			cnt = 0
		}
		if selected >= 2 {
			break
		}
	}

	if selected == 2 {
		out(sel[0] * sel[1])
	} else {
		out(0)
	}
}


Measured memory_bytes: 3072
#include<stdio.h>
int main(void){
    int W,H,x,y,r;
    scanf("%d %d %d %d %d\n",&H,&W,&x,&y,&r);
    if(y<0||x<0||x>W||y>H||W<y+r||H<x+r){
        printf("No\n");
    }
    else {
        printf("Yes\n");
    }
}


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

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


int main()
{
    int N;
    cin >> N;
    vector<string> S(N);
    REP(i, N) cin >> S[i];

    set<string> kind;
    REP(i, N) kind.insert(S[i]);
    cout << kind.size() << endl;

    return 0;
}

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

int main()
{
	int n,m;
	cin>>n>>m;
	long long int a[n+2],b[m+2],k,sa[n+2]={0},sb[m+2]={0};
	cin>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sa[i]=sa[i-1]+a[i];
	}
	for(int i=1;i<=m;i++)
	{
		cin>>b[i];
		sb[i]=sb[i-1]+b[i];
	}
	a[n+1]=b[m+1]=1e+12;
	long long int t=0,ans=0,tans=0;
	for(int i=1;i<=n;i++)
	{
		t+=a[i];
		if(t>k)
			break;
		long long int x=k-t;
		int j=upper_bound(sb+1,sb+m+1,x)-sb;
		j--;
		tans=i+j;
		ans=max(ans,tans);
	}
	t=0;
	for(int i=1;i<=m;i++)
	{
		t+=b[i];
		if(t>k)
			break;
		long long int x=k-t;
		int j=upper_bound(sa+1,sa+n+1,x)-sa;
		j--;
		tans=i+j;
		ans=max(ans,tans);
	}
	cout<<ans;
}



Measured memory_bytes: 9844
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations, combinations, accumulate, count
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1


X = int(input())

s = 100
for year in count():
    if s >= X:
        break
    s = s * 101 // 100
print(year)


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

using namespace std;

inline bool is_digit(char c) {
	return c <= '9' && c >= '0';
}

inline int read() {
	int tmp = 0, f = 1;
	char c = getchar();
	while(!is_digit(c)) {
		if(c == '-') f = -f;
		c = getchar();
	}
	while(is_digit(c)) tmp = (tmp << 1) + (tmp << 3) + (c ^ 48), c = getchar();
	return tmp * f;
}

inline void write(int x) {
	if(x > 9) write(x / 10);
	putchar((x % 10) ^ 48);
}

string s;

int main() {
	cin >> s;
	cout << s[0] << s[1] << s[2] << endl;
	return 0;
}

Measured memory_bytes: 3592
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        // String S = sc.next();
        char[] S = in.next().toCharArray();
        // String T = sc.next();
        char[] T = in.next().toCharArray();
        int N_S = S.length;
        int N_T = T.length;
        long[] ruiseki_S = new long[N_S+1];
        long[] ruiseki_T = new long[N_T+1];
        for (int i=0;i<N_S;i++) {
            int add=0;
            if (S[i]=='A') add=1;
            else add=2;
            ruiseki_S[i+1] = ruiseki_S[i]+add;
        }
        for (int i=0;i<N_T;i++) {
            int add=0;
            if (T[i]=='A') add=1;
            else add=2;
            ruiseki_T[i+1] = ruiseki_T[i]+add;
        }

        int Q = in.nextInt();
        for (int i=0;i<Q;i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            int d = in.nextInt();
            if (((ruiseki_S[b]-ruiseki_S[a-1])-(ruiseki_T[d]-ruiseki_T[c-1]))%3==0) out.println("YES");
            else out.println("NO");
        }
        out.close();
    }

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

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

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

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

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

    }
}

Measured memory_bytes: 50944
n = int(input())
s = list(map(int, input().split()))
mod = 10**9 + 7
m = len(bin(max(s))) - 2
p = [0] * m
q = [0] * m

for i in s:
    for j in range(m):
        if (i >> j) & 1 == 1:
            p[j] += 1
        else:
            q[j] += 1

res = 0
r = 1
for k in range(m):
    res += p[k] * q[k] % mod * r
    res %= mod
    r = r * 2 % mod
print(res)


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

using namespace std;

#define ll long long
#define rep(i,p,q) for(ll i = p;i < q;i++)

int main(void){
    ll n,k;
    cin >> n >> k;
    ll ans = 0;
    rep(i,k+1,n+1){
        ll p,r;
        p = n / i;
        r = n % i;
        ans += p * max((ll)0, i - k);
        ans += max((ll)0, r - k + 1);
    }
    if(k == 0) ans -= n;
    cout << ans << endl;
}

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

using namespace std;
typedef long long ll;
typedef long int li;
typedef long double lb;
#define rep(i,j,n) for (ll i = j; i < (n); i++)
#define repr(i,j,n) for(ll i = j; i >= (n); i--)
#define all(x) (x).begin(),(x).end()
#define CLR(mat,f) memset(mat, f, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const ll INF = 1LL<<60;

int main(){

  ll a,b;cin>>a>>b;
  out(a/b<<" "<<a%b<<" "<<fixed<<setprecision(10)<<(lb)a/b);

  return 0;
}



Measured memory_bytes: 3284
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> l;
vector<vector<int>> s;
void limput(int N){
  for(int i=0; i<N; i++){
    int tmp;
    cin>>tmp;
    l.push_back(tmp);
  }
  return;
}
vector<vector<int>> lsum;
void make(vector<int> v){
  for(int i=0; i<n; i++){
    vector<int> vi;
    for(int j=0; j<n; j++){
      vi.push_back(l.at(i)+l.at(j));
    }
    s.push_back(vi);
  }
}
int count(vector<vector<int>> S, vector<int> L, int N){
  int ans=0;
  for(int i=2; i<N; i++){
    for(int j=0; j<i-1; j++){
      for(int k=j+1; k<i; k++){
        if(L.at(i)<S.at(j).at(k)) ans++;
      }
    }
  }
  return ans;
}
          

int main() {
  cin>>n;
  limput(n);
  sort(l.begin(), l.end());
  make(l);
  cout<<count(s,l,n);
  return 0;
  
}
      

Measured memory_bytes: 33792
#include<stdio.h>
#include<stdlib.h>
int main(){
	int N, M;
	scanf("%d %d", &N, &M);
	int *node[100001], n_node[100001];
	for(int i = 0; i <= 100000; i++){
		node[i] = NULL;
		n_node[i] = 0;
	}
	for(int m = 1; m <= M; m++){
		int i, j;
		scanf("%d %d", &i, &j);
		n_node[i]++;
		n_node[j]++;
		node[i] = (int *) realloc(node[i], sizeof(int) * n_node[i]);
		if(node[i] == NULL){
			printf("failure_allocation\n");
			return 1;
		}
		node[i][n_node[i]-1] = j;
		node[j] = (int *) realloc(node[j], sizeof(int) * n_node[j]);
		if(node[j] == NULL){
			printf("failure_allocation\n");
			return 1;
		}
		node[j][n_node[j]-1] = i;
	}
	for(int i = 1; i <= N; i++)
		if(node[i] == NULL){
			printf("NULL ptr in graph");
			return 2;
		}

	int start = 1, vacant = 2, end = start, queue[100001];
	int state[100001];
  for(int i = 1; i <= N; i++)
    state[i] = -1;
	queue[1] = 1;
	state[1] = 1;
	while(start <= end){
		for(int current = start; current <= end; current++){
			for(int i = 0; i < n_node[queue[current]]; i++){
				if(state[node[queue[current]][i]] < 0){
					queue[vacant] = node[queue[current]][i];
					state[node[queue[current]][i]] = queue[current];
					vacant++;
				}
			}
		}
		start = end + 1; 
		end = vacant - 1;
	}
	printf("Yes\n");
	for(int n = 2; n <= N; n++)
		printf("%d\n", state[n]);
	return 0;
}

Measured memory_bytes: 8460
package main

import (
	"math/rand"
	"time"
	"os"
	"bufio"
	"fmt"
	"strconv"
	"strings"
)

var(
	sc = bufio.NewScanner(os.Stdin)
)

func init()  {
	rand.Seed(time.Now().UnixNano())
	buf := make([]byte, 0) //ここのサイズは何でもよさそう
	sc.Buffer(buf, 1000000009)
}


//||||||||||||||||||||||||||入力|||||||||||||||||||||||||||||||||||||||\
//数字一文字入力
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

//文字列を一行入力
func nextLine() string {
	sc.Scan()
	return sc.Text()
}

//空白区切りの文字列の入力
func spaceLine() []string {
	sc.Scan()
	return strings.Split(sc.Text()," ")
}

//数字を一行入力
func intLine() []int {
	str := spaceLine()
	buf := make([]int,len(str))
	for i,s:=range str{
		buf[i],_ = strconv.Atoi(s)
	}
	return buf
}

//|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

//ソートする
//sは最初のインデックス fは最後のインデックス
func Sort(ls []float64,l int,r int)  {
	if r - l <= 0{return}
	pipot := l + rand.Intn(r-l+1)
	ls[r],ls[pipot] = ls[pipot],ls[r]
	i := l
	for j:=l;j<r;j++{
		if ls[j] < ls[r]{
			ls[i],ls[j] = ls[j],ls[i]
			i ++
		}
	}
	ls[i],ls[r] = ls[r],ls[i]
	Sort(ls,l,i-1)
	Sort(ls,i+1,r)
}

//配列の大小を指定した要素で比較
//a < bならtrue
func sizeCheck(a []int,b []int,ls []int) bool {
	for _,i:= range ls{
		if a[i] < b[i]{
			return true
		} else if a[i] > b[i] {
			return false
		}
	}
	return false
}

//二次元配列のソート
func Sort2D(ls [][]int,l int,r int,index ...int)  {
	if r - l <= 0{return}
	pipot := l + rand.Intn(r-l+1)
	ls[r],ls[pipot] = ls[pipot],ls[r]
	i := l
	for j:=l;j<r;j++{
		if sizeCheck(ls[j],ls[r],index){
			ls[i],ls[j] = ls[j],ls[i]
			i ++
		}
	}
	ls[i],ls[r] = ls[r],ls[i]
	Sort2D(ls,l,i-1,index ...)
	Sort2D(ls,i+1,r,index ...)
}

func main() {
	l := intLine()
	n,m := l[0],l[1]
	a := intLine()
	cost := make(map[int]int)
	for _,v:=range a{
		if _,check := cost[v];check {
			cost[v] ++
		} else {
			cost[v] = 1
		}
	}
	for i:= 0;i<m;i++{
		bc := intLine()
		if _,check := cost[bc[1]];check {
			cost[bc[1]] += bc[0]
		} else {
			cost[bc[1]] = bc[0]
		}
	}
	i := 0
	ls := make([][]int,len(cost))
	for key,value := range cost{
		ls[i] = make([]int,2)
		ls[i][0] = key
		ls[i][1] = value
		i ++
	}
	Sort2D(ls,0,len(ls)-1,0)
	ans := 0
	for i:=len(ls)-1;i>=0;i--{
		b,c := ls[i][1],ls[i][0]
		if n >= b{
			ans += b*c
			n -= b
		} else {
			ans += n * c
			break
		}
		if n <= 0{break}
	}
	fmt.Println(ans)
}

Measured memory_bytes: 20864
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a,b;
cin>>a>>b;
int ans=a+b-n;
if(ans>0)
cout<<min(a,b)<<" "<<ans;
else cout<<min(a,b)<<" 0";
return 0;
}


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



int main(){
int r,g,b;
cin >> r >> g >> b;
if((r*100+g*10+b)%4==0){
cout << "YES" << endl;
}
else{
cout << "NO" << endl;
}
	return 0;



}

Measured memory_bytes: 256
INTEGER H,W,CHECK
CHARACTER(200),ALLOCATABLE,DIMENSION(:)::S
READ*,H,W
ALLOCATE(S(H))
READ*,S
DO I=W,1,-1
  CHECK=0
  DO J=1,H
    IF(S(J)(I:I)=="#") CHECK=1
  END DO
  IF (CHECK==0)THEN
    DO J=1,H
    S(J)=TRIM(S(J)(1:I-1))//TRIM(S(J)(I+1:W))
    END DO
  END IF
END DO
DO J=1,H
  IF(TRIM(S(J))/=REPEAT(".", LEN_TRIM(S(J)) ) )PRINT"(A)",TRIM(S(J))
END DO
END


Measured memory_bytes: 256
// This  Program is made by Jan(Codezebra)
#include<bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
signed main(){
	//ios::sync_with_stdio(false);
	//cin.tie(0);
	int a,b;
	cin>>a>>b;
	cout<<max(max(a+b,2*a-1),2*b-1);
	return 0;
}



Measured memory_bytes: 256
import sys, math
from functools import lru_cache
from collections import deque

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    S = input()
    a, b, c = 0, 0, 0
    for char in S:
        if char == 'a':
            a += 1
        if char == 'b':
            b += 1
        if char == 'c':
            c += 1

    if max(a, b, c)-min(a, b, c) <= 1:
        print('YES')
    else:
        print('NO')

if __name__ == '__main__':
    main()


Measured memory_bytes: 9504
#include <bits/stdc++.h>
    using namespace std;
    int main() {
      int d,n;
      cin>>d>>n;

	  
      if(d==0){
		  if(n==100)
		  cout<<"101";
		  else
    	  cout<<n;
      }
      else if(d==1){
		  if(n==100)
		  cout<<"10100";
		  else
    	  cout<<n*100;
      }
      else{
		  if(n==100)
		  cout<<"1010000";
		  else
		  cout<<n*10000;
	  }
      
      return 0;
    }

Measured memory_bytes: 256
#include <stdio.h>
typedef long long ll;
int main(){
    ll N,A,B,ans,tmp;

    scanf("%lld%lld%lld",&N,&A,&B);

    ans = A * (N / (A + B));

    tmp = N % (A + B);
    if(tmp < A){
        ans += tmp;
    }else{
        ans += A;
    }

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

    return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int S = scan.nextInt();
		scan.close();
		int h = S / 3600;
		int m = (S - h * 3600) / 60;
		int s = S - h * 3600 - m * 60;
		System.out.println(h + ":" + m + ":" + s);
	}
}


Measured memory_bytes: 26124
global moved

nxt = [[0, 1], [1, 0], [0, -1], [-1, 0], [-1, -1], [1, 1], [-1, 1], [1, -1]]
def search(now_j, now_i):
  now =[[now_j,now_i]]
  while now:
    temp = []
    for k in now:
      #print(k)
      for a, b in nxt:
        #print(k, b, a)
        #print([k[0]+a, k[1]+b] )
        #print(k[0]+a < 0 , k[1]+b < 0 , k[0]+a >= w , k[1]+b >= h , [k[0]+a, k[1]+b] in moved)
        if k[0]+a < 0 or k[1]+b < 0 or k[0]+a >= h or k[1]+b >= w or [k[0]+a, k[1]+b] in moved:
          continue
        elif li[k[0]+a][k[1]+b] == 1:
 
          temp.append([k[0]+a, k[1]+b])
          moved.append([k[0]+a, k[1]+b])
    now = temp
ans_li = []

while 1:
  w, h= map(int, input().split())
  if w == 0 and h == 0:
    break
  li = [list(map(int, input().split())) for _ in range(h)]
  moved = []
  ans = 0

  for i in range(w):
    for j in range(h):
      if [j, i] not in moved and li[j][i] == 1:
        moved.append([j, i])
        #print(moved,j, i)
        search(j, i)  
        
        ans+=1
  ans_li.append(ans)

for i in ans_li:
  print(i)


Measured memory_bytes: 5724
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

g = [[] for _ in range(n)]
indeg = [0 for _ in range(n)]

for _ in range(m):
    x, y = map(int, input().split())
    g[x-1].append(y-1)
    indeg[y-1] += 1

dp = [0 for _ in range(n)]
q = deque([])

for i in range(n):
    if indeg[i] == 0:
        q.append(i)

while q:
    v = q.popleft()
    for w in g[v]:
        indeg[w] -= 1
        if indeg[w] == 0:
            q.append(w)
            dp[w] = max(dp[w], dp[v]+1)

print(max(dp))


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

#define REP(i ,n) for(int i=0 ;i < n; i++)
#define REPB(i ,n) for(int i=n; i >= 0; i--)
#define FOR(i ,m ,n) for(int i=m; i < n; i++)
#define FORB(i, m, n) for(int i=m; i>= n; i--)
#define ll long long
#define pb push_back
#define popb pop_back
#define debug(i) cout<< #i<< "= "<< i << endl
using namespace std;

int main(){
    int n;
    ll ans = 0;
    vector<int>l;
    cin >> n;
    REP(i,n){
        int t;
        cin >> t;
        l.pb(t);
    }

    sort(l.begin(),l.end(),greater<int>());

    REP(i,(n-2)){
        FOR(j,(i+1),(n-1)){
            FOR(k,(j+1),n){
                if(l[i] < (l[j] + l[k])) ans++;
                else break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

A, B, C, K = LI()

ans = -mod
if A >= K:
    ans = K
elif A + B >= K:
    ans = A
else:
    ans = A - (K - A - B)
print(ans)

Measured memory_bytes: 10836
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define boost ios_base::sync_with_stdio(false)
#define pb push_back
#define e1 first
#define e2 second
#define x first
#define y second
#define tysiac 1010
#define milion 1000100
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define OUT(x) { cout << x; return 0; }
#define PRINT(x, y) {printf("%d %d\n", x, y); return;} 
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define scanf(...) scanf(__VA_ARGS__)?:0
typedef long long int ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef double ld;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair <ld, ld> PDD;
typedef pair <PII, PII> PP;
typedef pair <ll, int> PLI;
typedef pair <double, int> PDI;

int dp[2][102][102][102];
int pref[110][110], n, m;
char s[110][110];
inline int getSum(int a, int b, int c, int d)
{
	if (a > c || b > d) return 0;
	//cout << "Pytam: " << imie(a) << imie(b) << imie(c) << imie(d) <<  pref[d][c] + pref[a-1][b-1] - pref[c][b-1] - pref[a-1][d] << endl;
	return pref[c][d] + pref[a-1][b-1] - pref[c][b-1] - pref[a-1][d];
}	
	
inline void takeMax(int &x, int y){x = max(x, y);}

int main()
{
	scanf("%d%d", &n, &m);
	FOR(i, 1, n) scanf("%s", s[i]+1);
	int posx = 0, posy = 0;
	FOR(i, 1, n)
	{
		FOR(j, 1, m)
		{
			int zn = (s[i][j] == 'o')?1:0;
			pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1] + zn;
			if (s[i][j] == 'E') posx = i, posy = j;
		}
	}
	
	FOR(i, 0, posx-1)
	{
		FOR(j, 0, n-posx)
			FOR(k, 0, posy-1)
				FOR(l, 0, m-posy) dp[(i & 1)][j][k][l] = 0;
		
		FOR(j, 0, n-posx)
			FOR(k, 0, posy-1)
				FOR(l, 0, m-posy)
				{
					if (i > 0 && i + j <= posx-1) 
						takeMax(dp[i&1][j][k][l], dp[(i&1)^1][j][k][l] + getSum(posx-i, max(posy-k, l+1), posx-i, min(posy+l, m-k)));
					if (j > 0 && i + j <= n-posx) 
						takeMax(dp[i&1][j][k][l], dp[i&1][j-1][k][l] + getSum(posx+j, max(posy-k, l+1), posx+j, min(posy+l, m-k)));
					if (k > 0 && k + l <= posy-1) 
						takeMax(dp[i&1][j][k][l], dp[i&1][j][k-1][l] + getSum(max(posx-i, j+1), posy-k, min(posx+j, n-i), posy-k));
					if (l > 0 && k + l <= m-posy) 
						takeMax(dp[i&1][j][k][l], dp[i&1][j][k][l-1] + getSum(max(posx-i, j+1), posy+l, min(posx+j, n-i), posy+l));
						
					if (i > 0) takeMax(dp[i&1][j][k][l], dp[(i&1)^1][j][k][l]);
					if (j > 0) takeMax(dp[i&1][j][k][l], dp[i&1][j-1][k][l]);
					if (k > 0) takeMax(dp[i&1][j][k][l], dp[i&1][j][k-1][l]);
					if (l > 0) takeMax(dp[i&1][j][k][l], dp[i&1][j][k][l-1]);
					//if (dp[i&1][j][k][l] > 0) cout << imie(i) << imie(j) << imie(k) << imie(l) << " : " << dp[i&1][j][k][l] << endl;
				}
	}
	
	cout << dp[(posx-1)&1][n-posx][posy-1][m-posy];
}


Measured memory_bytes: 8448
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#include <string.h>
#include <iomanip>
#include <numeric>
#include <cstdlib>
#include <cstdint>
#include <cmath>
#include <functional>
#include <limits>
#include <cassert>
#include <bitset>

using namespace std;

/* template */

using ll = long long;

void debug_out() { std::cout << std::endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << H << " ";
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cout << "debug: "; debug_out(__VA_ARGS__)
#else
#define debug(...) 
#endif

#define rep(i, a, n) for (int i = (int)(a); i < (int)(n); i++)
#define rrep(i, a, n) for (int i = ((int)(n-1)); i >= (int)(a); i--)
#define Rep(i, a, n) for (long long i = (long long)(a); i< (long long)(n); i++)
#define RRep(i, a, n) for (long long i = ((long long)(n-1ll)); i>=(long long)(a); i--)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (std::size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}

struct Edge{
    int to;
    ll weight;
    Edge(int t, ll w) : to(t), weight(w){ }
};

struct edge{
    int from;
    int to;
    ll weight;
    edge(int f,int t,ll w) : from(f), to(t), weight(w){ }
};


using Graph = vector<vector<Edge>>;
using graph = vector<vector<int>>;
using edges = vector<edge>;

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>
T lcm(T a, T b){
    return (a*b)/gcd(a,b);
}

ll ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}

constexpr ll LNF = 1LL<<50;

constexpr int INF = 1e9+7;

const long double PI=3.14159265358979323846;


vector<int> dx = {1,0,-1,1,-1,0};
vector<int> dy = {1,1,1,0,0,-1};

/* template */

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int k; cin >> k;
    ll a = 0;
    vector<ll> m(k,0);
    rep(i,0,k){
        a = a*10ll + 7ll;
        a %= k;
        if(a==0){
            cout << i+1 << endl;
            return 0;
        }
        m[a]++;
        if(m[a]>1){
            break;
        }
    }
    cout << "-1" << endl;
} 

Measured memory_bytes: 11000
#include <bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define me0(a) memset(a,0,sizeof(a))
#define me1(a) memset(a,-1,sizeof(a))
#define op freopen("in.txt","r",stdin);
#define mp(x,y) make_pair(x,y)
#define pii pair<int,int>
void read(int &val) { int x = 0; int bz = 1; char c; for (c = getchar(); (c<'0' || c>'9') && c != '-'; c = getchar()); if (c == '-') { bz = -1; c = getchar(); }for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48; val = x * bz; }
const int INF = 0x3f3f3f3f;
const int maxn=1e6+7;
const int mod=1e9+7;
typedef long long LL;

int n,m;


int main(){
    read(n);read(m);
    int ans=0;
    LL d = 1LL*m*m;
    fo(i,1,n){
        int x,y;
        read(x);read(y);
        LL xx = 1LL*x*x+1LL*y*y;
        if(xx<=d) ans++;
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 3768
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <numeric>
#include <functional>
#include <set>
#include <map>
#include <list>
#define debug(x) cout << #x << ": " << (x) << endl
using namespace std;

const double PI  = 3.141592653589793238463;
const int INF = 1000000007;

using ull = unsigned long long;
using ll = long long;

using Int = int;
using Double = double;

using P = pair<Int, Int>;
using V = vector<Int>;
using M = vector<V>;

string solve(int sx, int sy, int tx, int ty){
    string res;
    int x = tx - sx;
    int y = ty - sy;
    for(int i = 0; i < x; i++){
        res.push_back('R');
    }
    for(int i = 0; i < y; i++){
        res.push_back('U');
    }
    for(int i = 0; i < x; i++){
        res.push_back('L');
    }
    for(int i = 0; i < y + 1; i++){
        res.push_back('D');
    }
    for(int i = 0; i < x + 1; i++){
        res.push_back('R');
    }
    for(int i = 0; i < y + 1; i++){
        res.push_back('U');
    }
    res.push_back('L');
    res.push_back('U');
    for(int i = 0; i < x + 1; i++){
        res.push_back('L');
    }
    for(int i = 0; i < y + 1; i++){
        res.push_back('D');
    }
    res.push_back('R');
    return res;
}

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

    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;

    cout << solve(sx, sy, tx, ty) << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(long long i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,n-1,0)
#define RREPS(i,n) RFOR(i,n,1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const int INF=1e18;
const int MOD=1e9+7;

signed main(){
    int n;cin>>n;
    int a[n],b[n];
    REP(i,n)cin>>a[i]>>b[i];
    sort(a,a+n);
    sort(b,b+n);
    double lm,hm;
    if(n%2==1){
        lm=a[n/2];
        hm=b[n/2];
    }
    else{
        lm=(a[n/2]+a[n/2-1])/2.0;
        hm=(b[n/2]+b[n/2-1])/2.0;
    }
    int ans;
    if(n%2==0)ans=(hm-lm)*2+1;
    else ans=hm-lm+1;
    cout<<ans<<endl;
}

Measured memory_bytes: 6720
import math
import itertools
def distance(x1,x2,y1,y2):
    return math.sqrt(((x2-x1)**2) + ((y2-y1)**2))
n = int(input())
x = [0 for _ in range(n)]
y = [0 for _ in range(n)]
t = [i for i in range(n)]
for i in range(len(x)):
    x[i],y[i] = map(int,input().split())
pattern = [_ for _ in itertools.permutations(t,n)]
dis_all = [0 for _ in range(len(pattern))]
for i in range(len(pattern)):
    for j in range(n-1):
        dis_all[i] += distance(x[pattern[i][j]],x[pattern[i][j+1]],y[pattern[i][j]],y[pattern[i][j+1]])
print(sum(dis_all)/len(dis_all))

Measured memory_bytes: 9332
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define ll long long
using namespace std;
int read(){
    char c;int s=0,t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}while(isdigit(c=getchar()));
    return s*t;
}
int ab(int x){return x>=0?x:-x;}
/*------------------------------------------------------------*/
#define double long double
const int inf=0x3f3f3f3f,maxn=100010;
int n,a[maxn];

int main(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	sort(a+1,a+n+1);
	int x=lower_bound(a+1,a+n+1,a[n]/2)-a;
	if(x==n)x--;
	if(x>1&&ab(a[x-1]-a[n]/2)<ab(a[x]-a[n]/2))x--;
	printf("%d %d",a[n],a[x]);
	return 0;
}

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

int as[10];
int bs[10];

int main() {
  while (1) {
    for (int i=0; i<10; i++) {
      if (scanf("%1d", &as[i]) != 1) return 0;
    }

    for (int i=0; i<9; i++) {
      for (int j=0; j<9-i; j++) {
        bs[j] = (as[j]+as[j+1])%10;
      }

      for (int j=0; j<9-i; j++) {
        as[j] = bs[j];
      }
    }

    printf("%d\n", as[0]);
  }
}

Measured memory_bytes: 2560
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rd read()
using namespace std;

const int N = 1e5 + 5;

int a[N], n;
int num[N], maxn1, ans, maxp1;
int maxn2, maxp2;
int maxn3, maxp3;
int maxn4, maxp4;

int read() {
	int X = 0, p = 1; char c = getchar();
	for ( ; c > '9' || c < '0'; c = getchar())
		if (c == '-' ) p = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		X = X * 10 + c - '0';
	return X * p;
}

void cmax(int &A, int B) {
	if (A < B)
		A = B;
}

int main()
{
	n = rd;
	for (int i = 1; i <= n; ++i) 
		a[i] = rd;
	for (int i = 1; i <= n; i += 2) 
		num[a[i]]++;
	for (int i = 1; i <= 1e5; ++i) {
		if (num[i] > maxn1) {
			maxp2 = maxp1;
			maxn2 = maxn1;
			maxn1 = num[i];
			maxp1 = i;
		}
		else if (num[i] > maxn2) {
			maxp2 = i;
			maxn2 = num[i];
		}
	}
	memset(num, 0, sizeof(num));
	for (int i = 2; i <= n; i += 2) 
		num[a[i]]++;
	for (int i = 1; i <= 1e5; ++i) {
		if (num[i] > maxn3) {
			maxp4 = maxp3;
			maxn4 = maxn3;
			maxn3 = num[i];
			maxp3 = i;
		}
		else if (num[i] > maxn4) {
			maxp4 = i;
			maxn4 = num[i];

		}
	}
	if (maxp1 != maxp3)
		printf("%d\n", n - maxn1 - maxn3);
	else printf("%d\n", n - max(maxn1 + maxn4, maxn3 + maxn2));
}


Measured memory_bytes: 896
# -*- coding: utf-8 -*-
s = [int(x) for x in input()]

if len(s) == 1:
    print(0)
else:
    # case: s[0] = 0
    cnt1 = 0
    for idx in range(0, len(s) - 1, 2):
        if s[idx] != 0:
            cnt1 += 1
        if s[idx + 1] != 1:
            cnt1 += 1
    if len(s) % 2 == 1 and s[-1] != 0:
        cnt1 += 1

    # case: s[0] = 1
    cnt2 = 0
    for idx in range(0, len(s) - 1, 2):
        if s[idx] != 1:
            cnt2 += 1
        if s[idx + 1] != 0:
            cnt2 += 1
    if len(s) % 2 == 1 and s[-1] != 1:
        cnt2 += 1

    print(min(cnt1, cnt2))

Measured memory_bytes: 3996
N = int(input())
S = input()

count = 0

for n in range(N):
    x = 0
    Sl = S[:n]
    Sr = S[n:]
    for a in set(S):
        if a in Sl and a in Sr:
            x += 1
    if count < x:
        count = x

print(count)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
//#include<unordered_map>
#define debug(x) (cout << "#x = " << (x) << endl)
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
//#define mid (l + r >> 1)
#define lowbit(x) (x & -x)
#define Set(x, i) memset(x, i, sizeof x)
#define R register
#define For( i, j, k ) for(R int i = (j); i <= (k); ++i)
#define foR( i, j, k ) for(R int i = (j); i >= (k); --i)
#define Cross( i, j, k ) for(R int i = (j); i; i = (k))using namespace std;
typedef long long ll;
using namespace std;
const ll N = 100011;
const ll Inf = 0x3f3f3f3f3f3f;

namespace IO {

	#define dd ch = getchar()
	inline ll read() {
		ll x = 0; bool f = 0; char dd;
		for (; !isdigit (ch); dd) f ^= (ch == '-');
		for (; isdigit (ch); dd)  x = x * 10 + (ch ^ 48);
		return f? -x: x;
	}
	#undef dd

	inline void write ( ll x ) {
		if (x < 0) putchar ('-'), x = -x;
		if (x > 9) write (x / 10); putchar ( x % 10 | 48 );
	}

	inline void wrn ( ll x ) { write(x); putchar (' '); }

	inline void wln ( ll x ) { write(x); putchar ('\n'); }

	inline void wlnn ( ll x, ll y ) { wrn(x); wln (y); }

}

using namespace IO;

namespace Cesare {
	
	ll n, D, cc = 0, A[N];
	
	int main() {
		n = read(), D = read();
		A[++cc] = D + 1;
		For ( i, D + 1, n ) 
			if (i - 2 * D - 1 == A[cc]) A[++cc] = i;
		if (A[cc] + D < n) ++cc;
		wln(cc);
		return 0;
	}
	
}

int main()
{
	return Cesare::main();
}

/*

*/



Measured memory_bytes: 256
// --------------------<optimizations>--------------------
#pragma GCC optimize("O3")
//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)\
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)\
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair<ll,ll>
#define vpii vector<pair<ll,ll> >
#define F first
#define S second
#define ld long double
#define built __builtin_popcountll
#define mst(a,i) memset(a,i,sizeof(a))
#define all(x) x.begin(),x.end()
#define itit(it,a) for(auto it=(a).begin(); it!=(a).end(); it++)
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define repr(i,a,b) for(ll i=a; i>b; i--)
#define reprr(i,a,b) for(ll i=a; i>=b; i--)
#define pi 3.14159265358979323846264338327950288419716939937510582097494459230
ll max3(ll x,ll y,ll z) {return max(max(x,y),z);}
ll min3(ll x,ll y,ll z) {return min(min(x,y),z);}
const ll M=2e5+10,M2=1e6+10,mod=1e9+7,inf=1e17+10;
void add(int& a, int b) {a+=b;if(a>=mod){a-=mod;}}
#define trace1(x)			 	 cerr<<#x<<": "<<x<<endl
#define trace2(x, y)		 	 cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)		 	 cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)	 	 cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)	 cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
int X[] = {0, 1, 0, -1};
int Y[] = {-1, 0, 1, 0};
ll power(ll x,ll n){ll result=1;while(n>0){if(n%2==1)result=(result*x)%mod; x=((x%mod)*(x%mod))%mod;n=n/2;}return result;}


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	string a,b,c;
	cin >> a >> b >> c;
	cout << a[0] << b[0] << c[0];
	return 0;
}
/* The judge is never wrong! Your code is buggy
   Look for:
 * * Read the problem carefully.
 * * Don't forget to sort(), mod, ll!!!!
 * * Initial value = +/- infinity instead of zero!!!
 * * an easier and alternate approach
 * * read the problem statement carefully
 * * if concept is correct and still WA, try with a different implementation
 * * special cases (n=1?)
 * * if you have no idea just guess the appropriate well-known algorithm instead of doing nothing :/
 */


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

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    if ((a - b == 0 && a - c == 0) || ((a != b) && (a != c) && (b != c))){
        cout << "No";
    } else cout << "Yes";
    return 0;
}

Measured memory_bytes: 256
/*
Floyd Warshall Algorithm
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C
*/

#include <bits/stdc++.h>
#define si( x ) scanf("%d", &x)
#define sll( x ) scanf("%lld", &x)
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
using namespace std;

typedef long long ll;

int n, m, inf = 2000000001;
int cost[200][200];

int main(){
	int i, j, k;
	si(n), si(m);
	for(i = 0; i < n; i++){
		for(j = 0; j < n; j++){
			if(i == j) cost[i][j] = 0;
			else cost[i][j] = inf;
		}
	}
	for(i = 0; i < m; i++){
		int u,v,w;
		si(u), si(v), si(w);
		cost[u][v] = w;
	}
	for(k = 0; k < n; k++)
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++)
				if(cost[i][k] != inf && cost[k][j] != inf && cost[i][j] > (cost[i][k] + cost[k][j]))
					cost[i][j] = cost[i][k] + cost[k][j];
	
	for(i = 0; i < n; i++) if(cost[i][i] < 0){
		printf("NEGATIVE CYCLE\n");
		return 0;
	}
	
	for(i = 0; i < n; i++){
		if(cost[i][0] == inf) printf("INF");
		else printf("%d", cost[i][0]);
		for(j = 1; j < n; j++){
			if(cost[i][j] == inf) printf(" INF");
			else printf(" %d", cost[i][j]);
		}
		printf("\n");
	}
}


Measured memory_bytes: 3284
#include <cstdio>
#include <algorithm>

using namespace std;

#define MAX 200

int N, n, d, x[MAX], y[MAX];
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

int main() {
	while(1) {
		scanf("%d", &N);
		if(N == 0)
			return 0;
		x[0] = y[0] = 0;
		for(int i = 1; i < N; i++) {
			scanf("%d %d", &n, &d);
			x[i] = x[n] + dx[d];
			y[i] = y[n] + dy[d];
		}
		int xmax = -MAX, ymax = -MAX;
		int xmin =  MAX, ymin =  MAX;
		for(int i = 0; i < N; i++) {
			xmax = max(xmax, x[i]);
			ymax = max(ymax, y[i]);
			xmin = min(xmin, x[i]);
			ymin = min(ymin, y[i]);
		}
		printf("%d %d\n", xmax - xmin + 1, ymax - ymin + 1);
	}
}

Measured memory_bytes: 0
/*input
7
1
3
1
2
3
3
2
*/

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 3;
const int MOD = 1e9 + 7;
 
int add(int a, int b) {
  int r = a + b;
  if (r >= MOD) r -= MOD;
  return r;
}
 
int mul(int a, int b) {
  return int((long long)a * b % MOD);
}
 
int sub(int a, int b) {
  int r = MOD + a - b;
  if (r >= MOD) r -= MOD;
  return r;
}

map<int,int> last;

int c[N], prv[N], dp[N];

int main(int argc, char const *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);

  int n;
  cin >> n;

  for (int i = 1; i <= n; ++i)
  {
    int x;
    cin >> x;
    int l = last[x];
    prv[i] = l;
    last[x] = i;
    c[i] = x;
  }

  dp[0] = 1;
  for (int i = 1; i <= n; ++i)
  {
    if (!prv[i] || (prv[i] + 1 == i)) {
      dp[i] = dp[i - 1];
      continue;
    }

    int p = prv[i];
    // cout << i << p << endl;
    dp[i] = add(dp[i - 1], dp[p]);
  }

  cout << dp[n];

  return 0;
} 

Measured memory_bytes: 12032
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

enum KIND {
    ROOT,
    NODE,
    LEAF,
};

struct Node {
    int id;
    enum KIND kind;
    int parent;
    vector<Node*> children;
    int depth;
};

#define MAX_N (100010)
int n;

Node T[MAX_N];

int main()
{
    int root_id;
    scanf("%d", &n);
    
    for ( int i = 0; i < n; i++ ) {
	T[i].id = i;
	T[i].parent = -1;
	T[i].kind = LEAF;
    }


    for ( int i = 0; i < n; i++ ) {
	int id, k;
	scanf("%d %d", &id, &k);
	for ( int j = 0; j < k; j++ ) {
	    int c;

	    scanf("%d", &c);
	    T[c].parent = id;	// ???????¨????

	    T[id].children.push_back( &T[c] );
	}
    }

    for ( int i = 0; i < n; i++ ) {
	if ( T[i].parent == -1 ) {
	    T[i].kind = ROOT;
	    root_id = i;
	}
	else if ( T[i].children.size() > 0 ) {
	    T[i].kind = NODE;
	}
    }

    queue<Node> Q;
    
    Q.push( T[root_id] );
    T[root_id].depth = 0;
    while ( !Q.empty() ) {
	Node nod = Q.front(); Q.pop();
	int depth = nod.depth;
	for ( int i = 0; i < nod.children.size(); i++ ) {
	    Node *p_child = nod.children[i];
	    p_child->depth = depth + 1;
	    Q.push( *p_child );
	}
    }

    for ( int i = 0; i < n; i++ ) { 
	Node nod = T[i];
	printf("node %d: parent = %d, depth = %d, ", i, nod.parent, nod.depth);
	if ( nod.kind == ROOT )	printf("root, ");
	else if ( nod.kind == NODE ) printf("internal node, ");
	else printf("leaf, ");
	
	printf("[");
	for ( int j = 0; j < nod.children.size(); j++ ) {
	    printf("%d", (nod.children[j])->id);
	    if ( j != nod.children.size() - 1 ) printf(", ");
	}
	printf("]\n");
    }

    return 0;
}

Measured memory_bytes: 12144
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

def check(sets):
  n = len(sets)
  data = [0]*n
  count = 0
  result_bit = 0
  for j in range(w):
    tmp = [0]*n
    for i in range(h):
      tmp[bisect.bisect_left(sets,i)]+=S[i][j]
      # ここ不安
    F = 0
    for i in range(n):
      if tmp[i] > K:return -1
      if data[i] + tmp[i] > K:
        F = 1
      else:
        data[i] += tmp[i]
    if F:
      result_bit |= (1<<j-1)
      for i in range(n):
        data[i] = tmp[i]
  return result_bit
    # if tmp > K:
    #   return -1
    # if count + tmp > K:
    #   result_bit |= (1 << j-1)
    #   count = tmp
    # else:
    #   count += tmp
  return  result_bit

h,w,K = map(int,input().split())
S = [list(map(int,input())) for i in range(h)]
for bit in range(2**(h-1)):
  sets = []
  for k in range(h-1):
    if (bit >> k) & 1:
      sets.append(k)
  sets.append(h)
  re = check(sets)
  # print(re)
  if re == -1: continue
  mans = min(mans,collections.Counter(bin(bit))["1"] + collections.Counter(bin(re))["1"])
  # print(bit,collections.Counter(bin(bit))["1"] + collections.Counter(bin(re))["1"],bit,re)
print(mans)

Measured memory_bytes: 51164
#include <bits/stdc++.h>
#define PI 3.1415926535897
using namespace std;
typedef long long ll;

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

    vector<int> W(N, 0);
    for (int i = 0; i < N; i++)
    {
        cin >> W.at(i);
    }

    int sum;
    for (int i = 0; i < N; i++)
    {
        sum += W.at(i);
    }

    int left, right;
    int T;
    int diff, min;
    min = sum;
    for (T = 0; T < N; T++)
    {
        //* left
        left = 0;
        for (int i = 0; i <= T; i++)
        {
            left += W.at(i);
        }

        //* right
        right = 0;
        for (int j = T + 1; j < N; j++)
        {
            right += W.at(j);
        }
        
        //* min = abs(left - right)
        diff = abs(left - right);
        // printf("left:%d - right:%d = %d ", left, right, diff);
        if (min > diff)
        {
            min = diff;
        }
    }

    cout << min << endl;
    return (0);
}

Measured memory_bytes: 256
n, m = map(int, input().split())
a = [input() for i in range(n)]
b = [input() for i in range(m)]

for i in range(n-m+1):
    for j in range(n-m+1):
        if a[i][j] == b[0][0]:
            cnt = 0
            for k in range(m):
                if a[i+k][j:j+m] == b[k]: cnt+=1
            if cnt == m:
                print("Yes")
                exit()
print("No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
 
#define rep(i,n) for(ll i=0;i<n;++i)
#define all_map(pos,mp) for(ll pos=mp.begin();pos!=mp.end();pos -++)
#define ALL(a) (a).begin(),(a).end()

using namespace std;
using ll  = long long;
using pll = pair<ll, ll>;

const ll MOD  = 1e9 + 7;
const ll LINF = 1LL << 62;
const int INF = 1e9 + 7;

ll n, k;
vector<vector<ll>> g(100010);

ll dfs(ll v, ll p){
    ll ret = 1;
    ll colors = k-2;
    for(ll vi : g[v]){
        if(vi == p)continue;

        ret *= (colors * dfs(vi, v)) % MOD;
        ret %= MOD;

        colors--;
    }

    return ret;
}
int main(){
    cin >> n >> k;

    rep(i, n-1){
        ll a, b;
        cin >> a >> b;
        a--, b--;

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

    ll ans = k;
    ll colors = k-1;
    for(ll vi : g[0]){
        ans *= (colors * dfs(vi, 0)) % MOD;
        ans %= MOD;

        colors--;
    }

    cout << ans << endl;
}

Measured memory_bytes: 14512
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text.RegularExpressions;

namespace ConsoleApplication1
{
    class Program
    {
        /// <summary>
        /// プログラムのエントリポイント
        /// </summary>
        /// <param name="args"></param>
        static void Main(string[] args)
        {
            int[] val = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            int daily = val[0];
            int weekly = val[1];
            int must = val[2];

            int ans = 0;
            int weeklyCoin = daily * 7 + weekly;

            int getCoin = 0;

            // 
            ans += (must / weeklyCoin) * 7;
            getCoin = weeklyCoin * ans / 7;

            int remain = must - getCoin;

            if(remain > daily * 6)
            {
                ans += 7;
            }
            else
            {
                ans += remain / daily;
                if (remain % daily != 0)
                    ans++;
            }

            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 17920
#include <stdio.h>
#include <iostream>
#include <string>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <vector>

#define rep(i,a,b) for(long long i=a;i<b;i++)

using namespace std;


int main(void) {

	long long N = 0, K = 0, H = 0, W = 0, C = 0;
	char a[100][100] = {};
	int b[100] = {};
	long long c[300] = { 0 };
	long long d[300] = { 0 };
	//long long y[20] = {};
	string s;
	
	vector<vector<int>> xx;
		
	long long min = 0, min2 = 0;
	long long dif = 0;
	long long hoge = 0;
	long long sum = 0;
	long long up = 0;

	cin >> N;
	
	if(N%2 == 0)
	cout << (N/2)*(N/2) << endl;
	else
		cout << ((N / 2)+1)*(N / 2) << endl;

	return 0;
	
}



Measured memory_bytes: 256
n = int(input())
a = [int(input()) for i in range(n)]
used = [False]*n
f = True
cur = 0
cnt = 0
while f:
    cnt += 1
    cur = a[cur]-1
    if cur == 1:
        break
    if used[cur]:
        f = False
        cnt = -1
    else:
        used[cur] = True
print(cnt)

Measured memory_bytes: 7852
import math

a, b = map(int, input().split())
ans = float('inf')

for i in range(1, 1001):
    if math.floor(i * 0.08) == a and math.floor(i * 0.1) == b:
        if ans > i:
            ans = i

if ans == float('inf'):
    print(-1)
else:
    print(ans)


Measured memory_bytes: 3060
import queue


def m():
    N, M = map(int, input().split())
    q = queue.PriorityQueue()
    A = list(map(int, input().split()))
    ans = []
    for a in A:
        q.put(-a)
    while M > 0:
        x = -q.get()
        x = -(x >> 1)
        M -= 1
        q.put(x)
    while not q.empty(): ans.append(q.get())
    return abs(sum(ans))


print(m())


Measured memory_bytes: 15292
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

vi G[MAX_N];
int ans[MAX_N];
int c[MAX_N];
int f[MAX_N];

void dfs(int x, int sum){
    sum += c[x];
    ans[x] = sum;
    f[x] = 1;
    rep(i,G[x].size()){
        if(f[G[x][i]]==0){
            dfs(G[x][i], sum);
        }
        
    }
}

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

    rep(i,n-1){
        int a,b; cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    rep(i,q){
        int p,x; cin >> p >> x;
        c[p] += x;
    }
    
    queue<P> que;
    que.push(P(1,0));

    while(que.size()>0){
        P p = que.front();
        que.pop();
        p.second += c[p.first];
        ans[p.first] = p.second;
        f[p.first] = 1;
        rep(i,G[p.first].size()){
            if(f[G[p.first][i]]==0){
                que.push(P(G[p.first][i], p.second));
            }  
        }
    }

    srep(i,1,n+1){
        cout << ans[i] << endl;
    }

    return 0;
}
 
 


Measured memory_bytes: 17140
#include<bits/stdc++.h>
using namespace std;
long ncrmodp(long n,long r,long p){
    long ans = 1;
    for(long i=n-r+1;i<=n;i++){
        ans *= i;
        ans %= p;
    }
    long tmp = 1;
    for(long i=2;i<=r;i++){
        tmp *= i;
        tmp %= p;
    }
    for(long i=1;i<=p-2;i*=2){
        if(i & p-2){
            ans *= tmp;
            ans %= p;
        }
        tmp *= tmp;
        tmp %= p;
    }
    return ans;
}
int main(){
    int n,k;
    cin >> n >> k;
    long const mod = 1e9+7;

    for(int i=1;i<=k;i++){
        long tmp = ncrmodp(n-k+1,i,mod);

        tmp *= ncrmodp(k-1,i-1,mod);
        tmp%=mod;
        cout << tmp<<endl;
        
    }
    
}

Measured memory_bytes: 256