akhauriyash/Code-Regression huggingface dataset:
import sys
import copy
input = sys.stdin.readline
from collections import deque
H, W = [int(x) for x in input().split()]
S = []
for _ in range(H):
    S.append(list(input().rstrip()))
can = []
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            can.append([i, j])
ans = []
for u in can:
    S_ = copy.deepcopy(S)
    D = {}
    queue = deque([u])
    def bfs(u, S):
        S_2 = S[:]
        D[tuple(u)] = 0
        while queue:
            v = queue.popleft()
            S_2[v[0]][v[1]] = "#"
            x, y = v
            next_ = [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]
            for r in next_:
                if 0 <= r[0] < H and 0 <= r[1] < W:
                    if S_2[r[0]][r[1]] == ".":
                        S_2[r[0]][r[1]] = "#"
                        D[tuple(r)] = D[tuple(v)] + 1
                        queue.append(r)
        return max(D.values())
    ans.append(bfs(u, S_))
print(max(ans))








Measured memory_bytes: 3540
#include<iostream>
using namespace std;
int main()
{
    int d,t,s;
    int net=0;
    cin>>d>>t>>s;
    net=t*s;
    if(net>=d)
    {
        cout<<"Yes";
    }
    else
    {
        cout<<"No";
    }
    return 0;
}


Measured memory_bytes: 3600
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
using namespace std;


int main(){
  int a,b,sum,tmp;
  int flag=0;
  cin>>a>>b;
  sum=0;
  tmp=999999;
  for(int i=0;i<a;i++){
    sum+=b+i;
    if(tmp>abs(b+i)&&b+i>=0){
      tmp=abs(b+i);
    }else if(tmp>abs(b+i)&&b+i<0){
      tmp=abs(b+i);
      flag=1;
    }
  }
  if(flag==0){
    sum=sum-tmp;
  }else{
  	sum=sum+tmp;
  }
  cout<<sum<<endl;
}

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

#define ll long long

signed main() {
  int N,K,X,Y;
  cin >> N >> K >> X >> Y;
  int sum=0;
  if(N < K){sum = N*X;}
  else{sum = K*X + (N-K)*Y;}
  cout << sum << endl;
}

Measured memory_bytes: 3612
import java.util.*;
import java.io.*;

public class Main {	
	private static void solve(){
		//Implement solution here.
		int n = ni();
		String s = next();
		char[] ca = s.toCharArray();
		int result = 0;
		for(int i = 0; i < 1000; i++) {
			String target = String.format("%03d", i);
			int idx = 0;
			for(int j = 0; j < 3; j++) {
				boolean found = false;
				for(int k = idx; k < n; k++) {
					if(ca[k] == target.charAt(j)) {
						found = true;
						idx = k + 1;
						break;
					}
				}
				if(found) {
					if(j == 2)result++;
					continue;
				} else {
					break;
				}
			}
		}
		System.out.println(result);
	}

	
	//Switch input source (stdin/file)
	private static BufferedReader br;
	public static void main(String[] args){
		br = new BufferedReader(new InputStreamReader(System.in));
		String debugDataPath = System.getenv("DD_PATH");        
		if(debugDataPath != null){
			try{
				br = new BufferedReader(new InputStreamReader(new FileInputStream(new File(debugDataPath))));
			}catch(Exception e){
				throw new RuntimeException(e);
			}
		}
		solve();
	}

	//Input read utility
	private static StringTokenizer tokenizer = null;
	public static String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}
	//Get next single int
	private static int ni() {
		return Integer.parseInt(next());
	}
	//Get next single long
	private static long nl() {
		return Long.parseLong(next());
	}
	//Get next single double
	private static double nd() {
		return Double.parseDouble(next());
	}
	//Get next int array from one line
	private static int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}
	//Get next char array from one line
	private static char[] ns() {
		return next().toCharArray();
	}
	//Get next long array from one line
	private static long[] nal(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nl();
		return a;
	}
}

Measured memory_bytes: 25616
import sys
 
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
nas = lambda: stdin.readline().split()

h = ni()
w = ni()
n = ni()

ans = 0

while n:
    n -= max(h, w)
    if n < 0:
        n = 0
    ans += 1

print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
const long long inf = 2000000000;
struct line
{
    long long l,r;
}edge[100005];
bool cmd(line a,line b)
{
    return a.l < b.l;
}
long long sm[100005];
int main()
{
    long long n;
    cin >> n;
    if(n == 0)
    {
        puts("0");
        return 0;
    }
    if(n == 1)
    {
        long long l,r;
        cin >> l >> r;
        cout << r-l+1 << endl;
        return 0;
    }
    long long mn = inf,k;
    long long mx = 0;
    for(long long i = 1;i <= n;i++)
    {

        long long l,r;
        scanf("%lld%lld",&edge[i].l,&edge[i].r);
        mx = max(edge[i].r-edge[i].l+1,mx);
        if(edge[i].r < mn)
        {
            mn = edge[i].r;
            k = i;
        }
    }
    edge[0] = edge[k];
    edge[k].l = inf;
    sort(edge+1,edge+n+1,cmd);
    long long l = 0;
    long long r = inf;
    long long ans;
    ans = max(mx,max(max(0ll,edge[0].r-edge[n-1].l+1)+mx,max(0ll,edge[0].r-edge[n-2].l+1)+edge[n-1].r-edge[n-1].l+1));
    if(edge[0].l >= edge[n-1].l)
    {
        cout << (edge[0].r-edge[0].l+1)+mx;
        return 0;
    }
    for(long long i = n-1;i > 0;i--)
    {
        l = max(l,edge[i].l);
        r = min(r,edge[i].r);
        sm[i] = max(0ll,r-l+1);
    }
    for(long long i = 0;i < n-1;i++)
    {
        if(edge[i].l > edge[0].r) break;
        else
        {
            ans = max(ans,edge[0].r-max(edge[i].l,edge[0].l)+1+sm[i+1]);
        }
        
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2560
package main

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

var (
	readString func() string
	stdout     *bufio.Writer
)

func init() {
	readString = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = readInt()
	}
	return b
}

func readLengthAndSlice() []int {
	n := readInt()
	return readIntSlice(n)
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}

func minInt(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func minUint(a, b uint) uint {
	if a < b {
		return a
	}
	return b
}

func minInt64(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func minUint64(a, b uint64) uint64 {
	if a < b {
		return a
	}
	return b
}

func maxInt(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func maxUint(a, b uint) uint {
	if a < b {
		return b
	}
	return a
}
func maxInt64(a, b int64) int64 {
	if a < b {
		return b
	}
	return a
}

func maxUint64(a, b uint64) uint64 {
	if a < b {
		return b
	}
	return a
}

func absInt(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func absInt64(a int64) int64 {
	if a < 0 {
		return -a
	}
	return a
}

// readString() string
// readInt() int
// readIntSlice(n int) []int
// readLengthAndSlice() []int
type pair struct {
	x, y int
}

func main() {
	defer stdout.Flush()

	h := readInt()
	w := readInt()

	s := make([]string, h)
	var nw, nb int
	for i := range s {
		s[i] = readString()
		for _, r := range s[i] {
			if r == '.' {
				nw++
			} else {
				nb++
			}
		}
	}

	f := make([][]int, h)
	for i := range f {
		f[i] = make([]int, w)
		for j := range f[i] {
			f[i][j] = math.MaxInt32
		}
	}

	q := make([]pair, 0)
	push := func(x, y int) {
		q = append(q, pair{x, y})
	}
	pop := func() (int, int) {
		r := q[0]
		q = q[1:]
		return r.x, r.y
	}
	dx := []int{-1, 0, 1, 0}
	dy := []int{0, 1, 0, -1}

	push(0, 0)
	f[0][0] = 0
	for len(q) != 0 {
		x, y := pop()
		if x == h-1 && y == w-1 {
			break
		}
		for d := 0; d < len(dx); d++ {
			nx, ny := x+dx[d], y+dy[d]
			ns := f[x][y] + 1
			if 0 <= nx && nx < h && 0 <= ny && ny < w && s[nx][ny] == '.' && ns < f[nx][ny] {
				f[nx][ny] = ns
				push(nx, ny)
			}
		}
	}

	score := f[h-1][w-1]
	if score == math.MaxInt32 {
		println(-1)
		return
	}
	println(nw - score - 1)
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef pair<int, int> ii;
typedef pair<ll, ll> pll;

int main( int argc, char *argv[] ) {
	int x, y;
	cin >> x >> y;
	cout << (x + y/2) << "\n";

	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String[] args) {
        //変数
        int count = 0;
        boolean sw = false;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        int answer=0;

        List<Integer> list1 = new ArrayList<>();
        List<String> list2 = new ArrayList<>();
        int array1[] = new int[5];
        int array2[] = new int[5];

        //入力
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int T = sc.nextInt();

        //処理
        int a=T/A;
        //System.out.println(a);
        int b=B*a;
        answer=b;

        //Collections.sort(a);
        //System.out.println(Arrays.toString(list1.toArray()));
        //System.out.println(Arrays.toString(array1));
		//System.out.println(Arrays.deepToString(a));
        System.out.println(answer);
    }
}

Measured memory_bytes: 21844
#include <iostream>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;

int main() {
    ll a, b, k;
    cin >> a >> b >> k;
    ll x = min(a, k);
    a -= x, k -= x;
    ll y = min(b, k);
    cout << a << " " << b - y << endl;
    return 0;
}


Measured memory_bytes: 256
import math

def gcd(a, b, c):
    return math.gcd(a, math.gcd(b, c))

n = int(input())
x = n*(n+1)//2
y = sum([math.gcd(i, j) for i in range(1, n+1) for j in range(i+1, n+1)])*6
z = sum([gcd(i, j, k) for i in range(1, n+1) for j in range(i+1, n+1) for k in range(j+1, n+1)])*6
print(x+y+z)

Measured memory_bytes: 19092
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define sz(x) int(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define INF 2e9
#define LINF 1e18
template<class T> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> P;

int main() {
    int n, k; cin >> n >> k;
    int mx = (n-1)*(n-2)/2;
    if (mx < k) {
        puts("-1");
        return 0;
    }
    vector<P> ans;
    //star型を作る
    rep(i, n-1) {
        ans.push_back(P(i+1, n));
    }
    int add = mx-k;
    vector<P> edge;
    rep(i, n-1)rep(j, i) edge.push_back(P(i+1, j+1));
    rep(i, add) ans.push_back(edge[i]);
    cout << sz(ans) << endl;
    rep(i, sz(ans)) {
        cout << ans[i].first << " " << ans[i].second << endl;
    }
}

Measured memory_bytes: 384
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;

namespace AOJ
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }

        static void Main(string[] args)
        {
            var NM = Sarray();
            var N = NM[0];
            var M = NM[1];
            var rin = new List<long>[N];
            for (var i = 0; i < N; ++i)
            {
                rin[i] = new List<long>();
            }
            for(var i=0;i<M;++i)
            { 
                var fr = Sarray();
                rin[fr[0]].Add(fr[1]);
                rin[fr[1]].Add(fr[0]);
            }
            var d = new long[N];
            var uni = 0;
            for (var j = 0; j < N; ++j)
            {
                if (d[j] != 0) continue;
                var q = new Queue<long>();
                q.Enqueue(j);
                ++uni;
                d[j] = uni;
                while (q.Any())
                {
                    var v = q.Dequeue();
                    foreach (var n in rin[v])
                    {
                        if (d[n] == 0)
                        {
                            q.Enqueue(n);
                            d[n] = uni;
                        }
                    }
                }
            }
            var Q = Sarray()[0];
            for (var i = 0; i < Q; ++i)
            {
                var st = Sarray();
                if (d[st[0]] == d[st[1]] && d[st[0]] != -1)
                    WriteLine("yes");
                else
                    WriteLine("no");
            }
        }
    }
}


Measured memory_bytes: 34512
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    n, x = f()
    m = []
    for i in range(n):
        m.append(f()[0])
    
    m = sorted(m)
    print(n + (x-sum(m))//m[0])


solve()
 

Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
vector<int> a[1000003];
bool vis[1000003];
int tot=0;
void dfs(int x)
{
    vis[x]=1,++tot;
    for(auto y:a[x]) if(!vis[y]) dfs(y);
}
int main()
{
    int n=read(),m=read(),ans=0;
    while(m--)
    {
        int u=read(),v=read();
        a[u].push_back(v);
        a[v].push_back(u);
    }
    for(int i=1; i<=n; i++) if(!vis[i]) tot=0,dfs(i),ans=max(ans,tot);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 39664
#include <stdio.h>

int main()
{
	int i,j,cnt=0,K;

	scanf("%d",&K);
	for(i=1;i<=K;i+=2){
		for(j=2;j<=K;j+=2){
			cnt++;
		}
	}

	printf("%d\n", cnt);
	return 0;
}

Measured memory_bytes: 128
W,a,b=map(int,input().strip().split(" "))

if(a>b):
    if(b+W<=a):
        print(a-(b+W))
    elif(b+W>a):
        print("0")
elif(a<b):
    if(a+W<=b):
        print(b-(a+W))
    else:
        print("0")
else:
    print("0")
        


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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int INF = 1e9;

int main() {
  int a[3], b[3], c[3][3];

  rep(i, 3) rep(j, 3) cin >> c[i][j];

  rep(i, 3) {
    a[i] = min({c[i][1], c[i][2], c[i][2]});
    rep(j, 3) c[i][j] -= a[i];
  }
  bool flg = true;
  rep(i, 3) if (!(c[0][i] == c[1][i] && c[2][i] == c[1][i])) flg = false;
  cout << (flg ? "Yes" : "No") << endl;
  return 0;
}


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

typedef long long int ll;
ll MOD = 1000000007;
ll INFL = 1ll << 60;
ll INF = 1 << 28;

// ====================================================================

int main() {
  int n;
  cin >> n;
  vector<int> v(n);
  for (int i = 0; i < n; i++) { cin >> v[i]; }
  sort(v.begin(), v.end());

  if (v[n / 2] == v[n / 2 - 1]) {
    cout << 0 << endl;
  } else {
    cout << v[n / 2] - v[n / 2 - 1] << endl;
  }
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <set>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

using namespace std;
typedef long long int lli;
const int MAX=1e5;

int main(){
	int A,B,C;
	cin>>A>>B>>C;
	int ans=MAX;
	rep(i,52){
		int x=0,y=0,z=0;
		if(i<=A)x=A-i;
		else if((A-i)%2==0)x=(i-A)/2;
		else x=(i-A)/2+2;
		if(i<=B)y=B-i;
		else if((B-i)%2==0)y=(i-B)/2;
		else y=(i-B)/2+2;
		if(i<=C)z=C-i;
		else if((C-i)%2==0)z=(i-C)/2;
		else z=(i-C)/2+2;
		ans=min(ans,x+y+z);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
const long long INF = 9999999999999999;
using ll = long long;
vector <ll> soin;
vector <ll> soin2;
void bnki(ll n){
  for(ll i = 2;i*i<=n;i++){
    if((i*i) == n){
      soin.push_back(i);
    }
    else if((n%i) == 0){
      soin.push_back(i);
    }
  }
  soin.push_back(n);
}

void bnki2(ll n){
  for(ll i = 2;i*i<=n;i++){
    if((i*i) == n){
      soin2.push_back(i);
    }
    else if((n%i) == 0){
      soin2.push_back(i);
      soin2.push_back(n/i);
    }
  }
  soin2.push_back(n);
}

int main(){
  ll N;
  cin>>N;
  if(N == 2){
    cout << 1 << endl;
    return 0;
  }
  bnki(N);
  bnki2(N-1);
  ll ans = 0;
  for(int i = 0;i<soin.size();i++){
    ll p = N;
    while((p%soin[i]) == 0){
      p /= soin[i];
    }
    if(p%soin[i] == 1){
      ans++;
    }    
  }
  
  cout << ans+soin2.size() << endl;
  return 0;
}

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

using namespace std;

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

#define ALL(obj)	(obj).begin(),(obj).end()

typedef unsigned int 			uint;
typedef unsigned long long int	ull;
typedef long long int 			ll;

typedef pair<int,int>			P;

#define LINF		((ll)1 << 63 -1)
#define INF 		2000000007
#define MINF		-2000000007
#define MAX 		100005

const int MOD = 1e9+7;
// テンプレ終了
//====================================================================//


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

	vector<int> color(9,0);
	REP(i,N){
		A[i] /= 400;
		A[i] = min(A[i],8);
		color[(A[i]<8 ? A[i] : 8)]++;
	}

	int ans = 0;
	REP(i,8)if(color[i] > 0)ans++;

	cout << (ans ? ans : 1) << " " << (ans+color[8]) << endl;

	return 0;
}




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

using namespace std;

using int64 = long long;

constexpr int64 P = 1000000007;

struct FiniteField {
 private:
  int64 x;
 public:
  FiniteField(int64 x) : x(x) {
    if (x > P || x < 0) { cerr << "Invalied FiniteField!" << endl; exit(1); }
  }
  FiniteField() : x(0) {}
  int64 Value() const { return x; }
  inline FiniteField operator+(FiniteField o) const {
    FiniteField r(*this); r += o; return r;
  }
  inline FiniteField operator-(FiniteField o) const {
    FiniteField r(*this); r -= o; return r;
  }
  inline FiniteField operator* (FiniteField o) const {
    FiniteField r(*this); r *= o; return r;
  }
  inline FiniteField operator/ (FiniteField o) const {
    FiniteField r(*this); r /= o; return r;
  }
  inline void operator+= (FiniteField o) { x = (x + o.x) % P; }
  inline void operator-= (FiniteField o) { x = (x + P - o.x) % P; }
  inline void operator*= (FiniteField o) { x = (x * o.x) % P; }
  void operator/=(FiniteField o) {
    int64 p = P - 2; while (p) { if (p % 2) { *this *= o; } o *= o; p /= 2; }
  }
};

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

  int n;
  cin >> n;
  string s;
  cin >> s;
  vector<int> count(26);
  for (char c : s) {
    count[c - 'a']++;
  }
  FiniteField ans = 1;
  for (int i = 0; i < 26; i++) {
    ans *= count[i] + 1;
  }
  ans -= 1;
  cout << ans.Value() << endl;
}

Measured memory_bytes: 512
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        set の最悪計算量は O(N) なので size 指定のほうが若干速い
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :return:
        """
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return

        # rank が小さい方が下
        if self._ranks[x] > self._ranks[y]:
            # x が root
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            # y が root
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def root(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.root(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.root(x)]


N, M = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))
XY = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

uf = UnionFind(size=N)
for x, y in XY:
    uf.unite(x, y)

# N-M 個の木がある
if N - M == 1:
    print(0)
    exit()
if (N - M - 1) * 2 > N:
    print('Impossible')
    exit()

A = np.array(A, dtype=int)
idx = A.argsort()

ans = 0
cnt = 0
used_n = np.zeros(N, dtype=bool)
used_root = np.zeros(N, dtype=bool)
for i in idx:
    if not used_root[uf.root(i)]:
        used_root[uf.root(i)] = True
        used_n[i] = True
        ans += A[i]
        cnt += 1

for i in idx:
    if not used_n[i]:
        ans += A[i]
        cnt += 1
    if cnt >= (N - M - 1) * 2:
        break
print(ans)


Measured memory_bytes: 46568
#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	long long int n,k,x,l(1);cin>>n;
  k=pow(10,18);
  for(int i=0;i<n;i++)
  {
    cin>>x;
    if(x==0)
    {
      l=0;
      k=1;break;
    }
    k=k/x;
    l*=x;
  }
  if(k==0)
  {
    cout<<"-1";
  }
  else cout<<l;
}

Measured memory_bytes: 3640
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>

using namespace std;
using ll = long long;

int main(){
    int a,b;
    cin >> a >> b;
    for(int i=0; i<1001; i++){
        if(a==floor(i*0.08) and b==floor(i*0.1)){
            cout << i << endl;
            exit(0);
        }
    }
    cout << -1 << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

/**
 * 逆元を利用する
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        sc.close();

        int total = 0;

        int[] count = new int[2019];
        count[0]++;
        int ans = 0;
        int ten = 1;

        for (int i = 1; i <= s.length(); i++) {
            total += (s.charAt(s.length() - i) - '0') * ten;
            ten = ten * 10 % 2019;
            total %= 2019;
            count[total] += 1;
        }

        for (int i = 0; i < 2019; i++) {
            ans += count[i] * (count[i] - 1) / 2;
        }

        System.out.println(ans);
    }
}

Measured memory_bytes: 40508
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define mkp make_pair
#define pr(num) cout << num << "\n"
#define max(a, b) ((a)>(b) ? (a):(b))
#define min(a, b) ((a)<(b) ? (a):(b))
#define INF 1000000000000000000
#define MOD 1000000007LL
#define MAX 100010
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef map<ll, ll> Map;

ll N, A, B;
ll a[44], b[44], c[44];
ll dp[44][444][444];

int main(void) {
    ll i, j, k;
    cin >> N >> A >> B;
    
    for(i=0; i<N; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }
    
    for(i=0; i<=N; i++) {
        for(j=0; j<404; j++) {
            for(k=0; k<404; k++) {
                dp[i][j][k]=INF;
            }
        }
    }
    
    dp[0][0][0]=0;
    for(i=0; i<N; i++) {
        for(j=0; j<404; j++) {
            for(k=0; k<404; k++) {
                dp[i+1][j][k]=min(dp[i+1][j][k], dp[i][j][k]);
                dp[i+1][j+a[i]][k+b[i]]=min(dp[i][j+a[i]][k+b[i]], dp[i][j][k]+c[i]);
            }
        }
    }
    
    ll ans=INF;
    for(i=1; i*max(A, B)<404; i++) {
        ans=min(ans, dp[N][i*A][i*B]);
    }
    
    if(ans==INF) pr(-1);
    else pr(ans);
    
}

Measured memory_bytes: 63616
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

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;
}

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------

int N, M;
set<int> to1, ton;

int main() {
  cin >> N >> M;
  rep(i, 0, M) {
    int a, b;
    cin >> a >> b;
    if (a == 1) {
      to1.insert(b);
    }
    if (b == N) {
      ton.insert(a);
    }
  }

  for (auto e : ton) {
    if (e == 1) {
      continue;
    }
    if (to1.count(e) == 1) {
      cout << "POSSIBLE";
      return 0;
    }
  }

  cout << "IMPOSSIBLE";
}


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

int n,w;
int we[100];
ll v[100];

//dp[i]: 무게 i안에 넣을 수 있는 최댓값
ll dp[100001];

int main(){
	cin>>n>>w;
	for(int i=0; i<n; i++){
		scanf("%d %lld",we+i,v+i);
	}
	for(int i=0;i<n;i++){
		for(int j=w; j>=we[i]; j--){
			dp[j]=max(dp[j],dp[ j-we[i] ]+v[i]);
		}
	}
	cout<<*max_element(dp,dp+w+1);
	
	return 0;
}

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

using namespace std;
#define DBG(x)                         \
    (void)(cout << "L" << __LINE__     \
                << ": " << #x << " = " \
                << (x) << '\n')

typedef long long ll;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const int INF = 0x3f3f3f3f;
const int maxn = 1100000;
int main()
{
    //检查有没有特判0,有没有越界限.
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setiosflags(ios::fixed) << setprecision(12);
    int ans = 0;
    int n;
    cin >> n;
    string s;
    cin >> s;
    for (int i = 0; i < n;)
    {
        if (s[i] == 'A' && i < n - 2)
        {
            if (s[i + 1] == 'B' && s[i + 2] == 'C')
            {
                ans++;
                i += 3;
            }
            else
                i++;
        }
        else
            i++;
        //DBG(i);
    }
    cout << ans << "\n";
    return 0;
}

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

using namespace std;
typedef long long lint;

#define RPT(i, b, e) for (int i = ((int)b); i <= ((int)e); i++)
#define RPT0(i, n) RPT(i, 0, ((int)n) - 1)
#define RPT1(i, n) RPT(i, 1, (n))
#define EACH(it, v) for (const auto& it : v)
#define ALL(v) v.begin(), v.end()

void resolve()
{
    string T;
    cin >> T;

    RPT0(i, T.length())
    {
        cout << ((T[i] == '?') ? 'D' : T[i]);
    }

    cout << endl;
}

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


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

int main(){
  int N;
  cin >> N;
  vector<int> a(N);
  for(int i = 0; i < N; i++){
    cin >> a.at(i);
  }
  std::sort(a.begin(),a.end());
  std::reverse(a.begin(),a.end());
  int pt = 0;
  for(int i = 0; i + 1 < N; i+=2){
    pt += a.at(i) - a.at(i+1);
  }
  if(N&1){
    pt += a.at(N-1);
  }
  cout << pt << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<utility>
#include<set>
#include<stack>
#include<list>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<cmath>
#include<cctype>


#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ren(i,a,b) for(int i=a;i>=b;i--)
#define ff first
#define ss second
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vll vector<long long int>
#define vii vector<int>
#define gi(n) scanf("%d",&n)
#define gll(n) scanf("%lld",&n)
#define gstr(n) scanf("%s",n)
#define gl(n) cin >> n
#define oi(n) printf("%d",n)
#define oll(n) printf("%lld",n)
#define ostr(n) printf("%s",n)
#define ol(n) cout << n
#define os cout<<" "
#define on cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define all(n) n.begin(),n.end()
#define present(s,x) (s.find(x) != s.end())
#define cpresent(s,x) (find(all(s),x) != s.end())
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
using namespace std;

typedef unsigned long long int ull;
typedef long long int ll;
typedef long double ld;
typedef vector<vector<ll> > mat;

int main()
{ios_base::sync_with_stdio(false);

int n;
cin>>n;
ll m=1e9+7,ans=1;

string s1,s2;
cin>>s1>>s2;

rep(i,0,n-1)
{
	if(s1[i]==s2[i])
	{
		if(i==0)ans=(ans*3)%m;
		else
		{
			if(s1[i-1]==s2[i-1])ans=(ans*2)%m;
		}
	}
	else
	{
		if(i==0)ans=(ans*6)%m;
		else
		{
			if(s1[i-1]==s2[i-1])ans=(ans*2)%m;
			else
			ans=(ans*3)%m;
		}
		i++;
	}
	//ol(ans);on;
}
ol(ans);
return 0;
}



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

int main(){
    int a,b,k;
    string K;
    cin >> a >> b;

    if ((a+b)%2!=0){
        cout << "IMPOSSIBLE" << endl;
    } 
    else {
        cout << (a+b)/2 << endl;
    }
    return 0;
}

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

int table[] = {0, 1, 2, 3, 5, 7, 8, 9};

int main()
{
  vector<int> num;
  int n;
  while (scanf("%d ", &n) == 1) {
    if (n == 0) {break;}
    num.clear();
    while (n > 0) {
      num.push_back(n % 8);
      n /= 8;
    }
    reverse(num.begin(), num.end());
    for (int i = 0; i < num.size(); i++) {
      printf("%d", table[num[i]]);
    }
    printf("\n");
  }
  return 0;
}

Measured memory_bytes: 940
while true
    n, m = gets.chomp.split.map(&:to_i)
    break if [n, m] == [0, 0]
    value = []
    n.times{
        d, v = gets.chomp.split.map(&:to_i)
        value[d] = v if value[d].nil? || value[d] < v
    }
    puts value[1..m].inject(:+)
end


Measured memory_bytes: 6848
#include <stdio.h>
#define A 1000

int main(void){
	int a[3], count = 0, count2 = 0, i;
	scanf("%d%d%d", &a[0], &a[1], &a[2]);
	for (i = 0; i < 3; i++){
		if (a[i] == 5) count++;
		if (a[i] == 7) count2++;
	}
	if (count == 2 && count2 == 1)
		printf("YES\n");
	else
		printf("NO\n");
    return 0;
}

Measured memory_bytes: 128
K = int(input())
amari = 0
res = set()
tmp = 7
flag = False
for i in range(10**6):
    if i == 0:
        if tmp % K == 0:
            flag = True
        else:
            tmp = tmp % K
            res.add(tmp)
            amari += tmp
    else:
        tmp = (tmp * 10) % K
        amari += tmp
        amari = amari % K
        if amari == 0:
            flag = True
    if flag:
        break
if flag:
    print(i + 1)
else:
    print(-1)

Measured memory_bytes: 9208
#include<stdio.h>
int main(void)
{
	int a,b,count=0;
	scanf("%d",&a);
	b=a;
	while(a>0){
		count=count+a%10;
		a=a/10;
	}
	if(b%count==0){
		printf("Yes\n");
	}
	else{
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define QOEINDIEDIS freesteed
#define rep(i,a,n) for (int i=a;i<n;i++)
#define pb push_back
#define fill(x,c) memset(x,c,sizeof(x))
#define fi first
#define se second
#define sz(A) (int)(A.size())
#define all(x) (x).begin(),(x).end()
#define caset int ___T; cin>>___T; for(int cs=1;cs<=___T;cs++)
#define get(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
const ll mod=1e9+7;
const int Max = 1e6+10;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int N, M, K, p[20][1010],res=1010;
string s;
int sum(int L1,int R1,int L2,int R2){
    return  p[L2][R2] + p[L1 - 1][R1 - 1] - p[L1 - 1][R2] - p[L2][R1 - 1] ;
}
void solve(){
	cin>>N>>M>>K;
	rep(i,0,N){
		cin>>s;
		rep(j,0,M)if(s[j]=='1')p[i+1][j+1] = 1;
	}
	for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) p[i][j] += p[i][j - 1]; }
    for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) p[i][j] += p[i - 1][j]; }
	for(int bits = 0 ;bits<(1<<(N-1));bits++){
		if(__builtin_popcount(bits)>=res)continue;//剪枝 7ms ~ 3ms 
		VI cut;for(int i=0;i<N-1;i++)if((bits>>i)&1)cut.pb(i+1);cut.pb(N);	
		int  pcol = 1,ans=sz(cut)-1,ok = 1;
		for(int i=1;i<=M;i++){
			int f=1,prow=1;
			for(int j=0;j<sz(cut);j++){
				if(sum(prow,pcol,cut[j],i)>K){
					f = 0;
					break;
				}
				prow = cut[j]+1;
			}
			if(!f){
				ans++;
				if(ans>=res||pcol==i){//剪枝 3ms ~ 2ms 
					ok = 0;
					break;
				}
				pcol = i;
			}
		}
		if(ok)res = min(res,ans);
	}
	cout<<res;
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
  	return 0;
}

Measured memory_bytes: 256
{-# OPTIONS_GHC -O #-}
import Control.Monad
import Data.List
import Data.Array
import Data.Array.IO

solve n = do
    a6 <- newListArray (1,6) [6,36,216,1296,7776,46656] :: IO (IOArray Int Int)
    a9 <- newListArray (7,11) [9,81,729,6561,59049] :: IO (IOArray Int Int)
    --
    a <- newArray ((0,0),(n,11)) 0 :: IO (IOUArray (Int,Int) Int)
    forM_ [1..n] $ \j -> writeArray a (j,0) j
    --
    forM_ [(j,i)|i<-[1..6], j<-[0..n]] $ \(j,i) -> do
        p <- readArray a6 i
        m <- liftM minimum $ forM [k|k<-[0..5],k*p<=j] $ \k -> do
            (+k) <$> readArray a (j-k*p,i-1)
        writeArray a (j,i) m
    --
    forM_ [(j,i)|i<-[7..11], j<-[0..n]] $ \(j,i) -> do
        p <- readArray a9 i
        m <- liftM minimum $ forM [k|k<-[0..8],k*p<=j] $ \k -> do
            (+k) <$> readArray a (j-k*p,i-1)
        writeArray a (j,i) m
    --
    readArray a (n,11)

main = do
    n <- readLn :: IO Int
    print =<< solve n

Measured memory_bytes: 15740
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {

		java.util.Scanner scan = new Scanner(System.in);

		int masu = scan.nextInt();
		long[] height = new long[masu];
		boolean flg = false;
		long max = 0;

		for(int i=0;i<masu;i++) {
			height[i] = scan.nextLong();
		}

		for(int i=0;i<masu-1;i++) {
			max = Math.max(max,height[i]);
			if(height[i] > height[i+1]) {
				if(height[i]-1 > height[i+1] || height[i]-1 !=max-1) {
				flg = true;
				}
			}
		}
		System.out.println(flg?"No":"Yes");
		scan.close();
	}

}


Measured memory_bytes: 50444
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b;
  cin >> a >> b;
  if (fmod(a*b,2) == 0) {
    cout << "Even" << endl;
  }
   else {
    cout << "Odd" << endl;
  }
    
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
int main(){
   string s, t;
   cin >> s >> t;
   int l = s.length();
   int count = 0;
   for(int i = 0; i < l; i++){
       if(s[i] != t[i]) count++;
   }
   cout << count << endl;
} 


Measured memory_bytes: 3828
#include <bits/stdc++.h>
#define rep(i, n) for (lli i = 0; i < (n); i++)
#define rrep(i, n) for (lli i = (n)-1; i >= 0; i--)
using namespace std;
using lli = long long int;
#define int long long int
void YESNO(bool), YesNo(bool);
template <class T1, class T2>
bool chmin(T1 &l, const T2 &r);
template <class T1, class T2>
bool chmax(T1 &l, const T2 &r);
lli M;
lli dp[100005];
lli ans[100005];
vector<int> e[100005];
template <class T>
class segtree
{
public:
  lli n;
  vector<T> dat;
  function<T(T, T)> func;
  T dummy;
  segtree<T>(lli _n, T ini, function<T(T, T)> f, T dummy) : func(f), dummy(dummy)
  {
    n = 1;
    while (n < _n)
    {
      n = n * 2;
    }
    dat.assign(2 * n - 1, ini);
  }
  void update(lli k, T a)
  {
    k += n - 1;
    dat[k] = a;
    while (k > 0)
    {
      k = (k - 1) / 2;
      dat[k] = func(dat[k * 2 + 1], dat[k * 2 + 2]);
    }
  }
  T query(int a, int b)
  {
    return query(a, b, 0, 0, n);
  }
  // [a,b)の何かを求める.
  T query(int a, int b, int k, int l, int r)
  {
    //交差しないときはダミー
    if (r <= a || b <= l)
      return dummy;
    if (a <= l && r <= b)
      return dat[k];
    else
    {
      T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
      T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
      return func(vl, vr);
    }
  }
  T get(int a)
  {
    return query(a, a + 1, 0, 0, n);
  }
};
lli dfs1(int u, int p)
{
  // uがblack

  lli ret = 1; /* 全部white */
  for (auto s : e[u])
  {
    if (s == p)
      continue;
    ret *= (dfs1(s, u) + 1);
    ret %= M;
  }
  dp[u] = ret;
  return ret;
}
void dfs2(int u, int p, lli val)
{
  // uがblack

  lli ret = 1; /* 全部white */
  for (auto s : e[u])
  {
    if (s == p)
    {
      ret *= val + 1;
    }
    else
    {
      ret *= (dp[s] + 1);
    }
    ret %= M;
  }
  ans[u] = ret;
  auto f = [](lli a, lli b) { return (a * b) % M; };
  lli first = 1;
  segtree<lli> seg(e[u].size(), first, f, first);
  rep(i, e[u].size()) if (e[u][i] != p) seg.update(i, dp[e[u][i]] + 1);

  rep(i, e[u].size())
  {
    int s = e[u][i];
    if (s == p)
      continue;
    lli v = seg.query(0, i) * seg.query(i + 1, e[u].size()) % M * (val + 1) % M;
    dfs2(s, u, v);
  }
}
void solve(long long N, long long MM, std::vector<long long> x,
           std::vector<long long> y)
{
  M = MM;
  rep(i, N - 1) e[x[i] - 1].push_back(y[i] - 1);
  rep(i, N - 1) e[y[i] - 1].push_back(x[i] - 1);
  dfs1(0, -1);
  dfs2(0, -1, 0);
  rep(i, N)
  {
    cout << ans[i] << endl;
  }
}

signed main()
{
  long long N;
  scanf("%lld", &N);
  long long M;
  scanf("%lld", &M);
  std::vector<long long> x(N - 1);
  std::vector<long long> y(N - 1);
  for (int i = 0; i < N - 1; i++)
  {
    scanf("%lld", &x[i]);
    scanf("%lld", &y[i]);
  }
  solve(N, M, std::move(x), std::move(y));
  return 0;
}

// -- lib
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }

template <class T1, class T2>
bool chmin(T1 &l, const T2 &r)
{
  return (l > r) ? (l = r, true) : false;
}

template <class T1, class T2>
bool chmax(T1 &l, const T2 &r)
{
  return (l < r) ? (l = r, true) : false;
}


Measured memory_bytes: 89600
#include<bits/stdc++.h>
using namespace std;
/*
using ll = long long;
using ull = unsigned long long;
using V = vector<int>;
using VV = vector<vector<int>>;
using VVV = vector<vector<vector<int>>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VVVL = vector<vector<vector<ll>>>;
using pq = priority_queue<int>;
template<class T>
using P = pair<T, T>;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,k,n) for(int i=(k);i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define output(x,y) cout << fixed << setprecision(y) << x << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
*/
typedef vector<int> V;
typedef vector<vector<int> > VV;
#define rep(i,n) for(int i=0;i<(n);i++)
/*
int under = (1 << 31);
int upper = under - 1;
ll UNDER = (1LL << 63);
ll UPPER = UNDER - 1;
*/
const int MOD = 1e9 + 7;
const long double pi = 3.141592653589793;
void add(int& a, int b) {
	a += b;
	if (a >= MOD) a -= MOD;
}
int main() {
	string s, t;
	cin >> s >> t;
	int x = s.size();
	int y = t.size();
	VV dp(x + 2, V(y + 2, 0));
	dp[0][0] = 1;
	rep(i, x) rep(j, y + 1) {
		add(dp[i + 1][j], dp[i][j]);
		if (s[i] == t[j]) add(dp[i + 1][j + 1], dp[i][j]);
	}
	cout << dp[x][y] << endl;
	return 0;
}


Measured memory_bytes: 6888
#include <bits/stdc++.h>
#include <iomanip>
 
using namespace std;
 
typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLDLD;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<char> VB;
 
#define FOR(i,a,b) for(int i=(a);i<(int)(b);++i)
#define REP(i,n) FOR(i,0,n)
#define CLR(a) memset((a), 0 ,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define endl "\n"
 
const LD EPS=1e-10;
const long long INFLL=(LL)(1e9)*(LL)(1e9);
const int INF=1e9+7;

template<class T>
void chmin(T& a, const T b)
{
	if(a>b)
		a=b;
}
template<class T>
void chmax(T& a, const T b)
{
	if(a<b)
		a=b;
}
 
const LL powLL(const LL p, const LL q)
{
	LL t=1;
	for(int i=0;i<q;i++)
		t*=p;
	return t;
}

template <typename T>
struct has_iter
{
	private:
		template <typename U>
		static constexpr true_type check(typename U::iterator*);
		template <typename U>
		static constexpr false_type check(...);

	public:
		static constexpr bool value = decltype(check<T>(nullptr))::value;
};


template<typename T, typename U = typename T::iterator>
void print(const T& container)
{
		auto&& first=begin(container), last=end(container);
		auto&& back=prev(last);
		for(auto e=first; e!=last; e=next(e))
			cout<<*e<<" \n"[e==back];
}


extern void* enabler;
template<typename Head, typename enable_if<!has_iter<Head>::value>::type*& = enabler>
void print(const Head& head)
{
	cout<<head<<endl;
}

template<> void print<string>(const string& container)
{
	cout<<container<<endl;
}

template<typename Head, typename... Tail>
void print(const Head& head, const Tail&... tail)
{
	cout<<head<<" ";
	print(tail...);
}

void io_speedup()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
}

template<typename T>
istream& operator >> (istream& is, vector<T>& vec)
{
	for(T& x: vec) is >> x;
	return is;
}


template<typename T, typename U>
ostream& operator << (ostream& os, const pair<T, U>& p)
{
	os<<'('<<p.first<<", "<<p.second<<')';
	return os;
}

template<typename T>
vector<T> read(int n)
{
	vector<T> t(n);
	cin>>t;
	return t;
}

template<typename T>
T read()
{
	T t;
	cin>>t;
	return t;
}

template<typename Head, typename... Tail>
struct vector_demensions
{
	using type=vector<typename vector_demensions<Tail...>::type>;
};

template<typename Head>
struct vector_demensions<Head> { using type=Head; };

template<typename T>
vector<T> make_vectors(int size, T val)
{
	return vector<T>(size, val);
}

template<typename T=int, typename... Args>
auto make_vectors(int size, Args... tail)
	-> typename vector_demensions<Args..., T>::type
{
	auto val=make_vectors<T>(forward<Args>(tail)...);
	return vector<decltype(val)>(size, val);
}



int main()
{
	int n;
	cin>>n;
	auto a(read<int>(n));
	int ans=0;
	FOR(i,1,n)
	{
		if(a[i]==a[i-1])
		{
			a[i]=-1;
			ans++;
		}
	}
	print(ans);
}


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

#define froop1(a,n) for(int i = a;i < n;i++)
#define froop2(a,n) for(int i = a;i > n;i--)

#define ll long long

#define pq(name,type) priority_queue<type> name
#define vec(name,type,length,value) vector<type> name(length,value)
#define vec2(name,type,length,width,value) vector<vector<type>> name(length,vector<type>(width,value));

int main(){
	long long N,M;
  cin >> N >> M;
  if(abs(N - M) >= 2){
    cout << 0 << endl;
    return 0;
  }
  long long n = 1;
  if(N == M){
    n *= 2;
    for(long long i = N;i > 0;i--){
      n *= i;
      n %= 1000000007;
    }
    for(long long i = M;i > 0;i--){
      n *= i;
      n %= 1000000007;
    }
    cout << n << endl;
  }else{
   for(long long i = N;i > 0;i--){
      n *= i;
      n %= 1000000007;
    }
    for(long long i = M;i > 0;i--){
      n *= i;
      n %= 1000000007;
    }
    cout << n << endl;
  }
    
      
  

return 0;
}

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

int main(void){
	string s;
	int a[2];
	for(;;){
		cin >> s;
		if(s[0] == '0')break;
		a[0] = 0; a[1] = 0;
		for(int i = 1;i < s.size();++i)++a[s[i] - 'A'];
		cin >> s;
		++a[s[0] - 'A'];
		printf("%d %d\n", a[0], a[1]);
		
		a[0] = 0; a[1] = 0;
		for(int i = 1;i < s.size();++i)++a[s[i] - 'A'];
		cin >> s;
		++a[s[0] - 'A'];
		printf("%d %d\n", a[0], a[1]);
		a[0] = 0; a[1] = 0;
		for(int i = 1;i < s.size();++i)++a[s[i] - 'A'];
		if(a[0] == 10 && a[1] < 10)++a[0];
		if(a[1] == 10 && a[0] < 10)++a[1];
		if(a[0] >= 10 && a[1] >= 10)++a[a[0] < a[1]];
		printf("%d %d\n", a[0], a[1]);
	}
}

Measured memory_bytes: 3136
#include <stdio.h>
#include <stdlib.h>
 
int linearSearch(int *, int, int);
 
main(){
  int n,q,i,findN=0;
  int *sAry, *tAry;
 
  scanf("%d", &n);
  sAry = (int *)malloc((n+1)*sizeof(int)); //番兵用に+1
  for(i=0; i<n; i++) scanf("%d", sAry+i);
  scanf("%d", &q);
  tAry = (int *)malloc(q*sizeof(int));
  for(i=0; i<q; i++) scanf("%d", tAry+i);
 
  for(i=0; i<q; i++) findN+=linearSearch(sAry, n, tAry[i]);
 
  printf("%d\n", findN);
 
  return 0;
}
 
int linearSearch(int *ary, int n, int a){
  int i=0;
  ary[n]=a;
  while(ary[i]!=a) i++;
  if(i==n) return 0;
  return 1;
}

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

vector<ll> pa(200000),pb(200000);
vector<ll> ra(200000),rb(200000);
void init(ll n,vector<ll> &par,vector<ll> &ran){
  rep(i,n){
    par.at(i)=i;
    ran.at(i)=0;
  }
}
ll find(ll x,vector<ll> &par){
  if(par.at(x)==x){
    return x;
  }else{
    return par.at(x)=find(par.at(x),par);
  }
}
void unite(ll x,ll y,vector<ll> &par,vector<ll> &ran){
  x=find(x,par);
  y=find(y,par);
  if(x==y) return;
  if(ran.at(x)<ran.at(y)){
    par.at(x)=y;
  }else{
    par.at(y)=x;
    if(ran.at(x)==ran.at(y)) ran.at(x)++;
  }
}

int main(){
  ll N,K,L;
  cin>>N>>K>>L;
  init(N,pa,ra);
  rep(i,K){
    ll p,q;
    cin>>p>>q;
    unite(p-1,q-1,pa,ra);
  }
  init(N,pb,rb);
  rep(i,L){
    ll p,q;
    cin>>p>>q;
    unite(p-1,q-1,pb,rb);
  }
  priority_queue<P> A;
  rep(i,N){
    A.push(P(find(i,pa),find(i,pb)));
  }
  map<P,ll> B;
  while(!A.empty()){
    ll k=1;
    P a=A.top();
    A.pop();
    while(!A.empty()&&a==A.top()){
      k++;
      A.pop();
    }
    B[a]=k;
  }
  rep(i,N){
    cout << B.at(P(find(i,pa),find(i,pb))) << " ";
  }
  cout << endl;
}

Measured memory_bytes: 23776
from collections import Counter
from itertools import accumulate
import bisect
n = int(input())
a = list(map(int,input().split()))
c = list(Counter(a).items())
c = list(list(zip(*c))[1])
c.sort()
xls = [0]*(n+1)
for i in range(1,n+1):
  geqx = len(c)-bisect.bisect_left(c,i)
  xls[i] = xls[i-1]+geqx
xlsacc = list(accumulate(xls))
for k in range(1,n+1):
  l = 0
  r = n+1
  while l+1<r:
    x = (l+r)//2
    if k*x <= xls[x]:
      l = x
    else:
      r = x
  print(l)

Measured memory_bytes: 150832
#include <iostream>
#include <algorithm>

using namespace std;

int N;
int V[50 + 10];
int C[50 + 10];

int solve(int index, int v, int c) {
	if (index == N) {
		return v - c;
	}
	int x = 0;
	x = max(x, solve(index + 1, v + V[index], c + C[index]));
	x = max(x, solve(index + 1, v, c));
	return x;
}

int main(void) {
	cin >> N;
	for (int i = 0; i < N; ++i) {
		cin >> V[i];
	}
	for (int i = 0; i < N; ++i) {
		cin >> C[i];
	}
	cout << solve(0, 0, 0) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, c, d, L, R;
  cin >> a >> b >> c >> d;  
 
  L = a + b;
  R = c + d;
  
  if (L == R){
    cout << "Balanced" << endl;
  }else if (L > R){
    cout << "Left" << endl;
  }else{
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 384