akhauriyash/Code-Regression huggingface dataset:
// F.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <set>
#include <map>

using namespace std;

typedef long long LL;
typedef pair<LL, LL> LLLL;

class BIT {
	std::vector<LL> bit;
	LL size;
public:
	BIT() { }
	BIT(LL sz) { init(sz); }
	void init(LL sz) {
		bit = std::vector<LL>((size = sz) + 1);
	}
	LL sum(LL i) {
		LL s = 0;
		while (i > 0) {
			s += bit[i];
			i -= i & -i;
		}
		return s;
	}
	void add(LL i, LL x) {
		while (i <= size) {
			bit[i] += x;
			i += i & -i;
		}
	}
};


int main(int argc, char* argv[]) {
#ifdef _MSC_VER
	while (true)
#endif
	{
		LL n = -1, d, a, x, h, ans = 0;
		cin >> n >> d >> a;
		if (n <= 0) return 0;
		set<LL> s;
		vector<LLLL> v;
		for (LL i = 0; i < n; ++i) {
			cin >> x >> h;
			v.push_back({ x, h });
			s.insert(x);
			s.insert(x + 2 * d);
		}
		sort(v.begin(), v.end());
		LL sz = s.size() + 4;
		BIT bit(sz);
		map<LL, LL> m;
		LL seq = 2;
		for (LL x : s) {
			m[x] = seq;
			++seq;
		}
		for (LL i = 0; i < n; ++i) {
			LL j = m[v[i].first];
			LL cur = bit.sum(j);
			LL r = v[i].second - cur;
			if (r > 0) {
				LL need = (r + a - 1) / a;
				bit.add(m[v[i].first], need * a);
				bit.add(m[v[i].first + 2 * d] + 1, -need * a);
				ans += need;
			}
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 51180
import java.util.*;
class Main {
    public static void main (String[] args) throws java.lang.Exception {
        Scanner sc = new Scanner(System.in);
        double x1 = sc.nextDouble(), y1 = sc.nextDouble(), x2 = sc.nextDouble(), y2 = sc.nextDouble();
        System.out.printf("%.9f\n", Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
    }
}


Measured memory_bytes: 28316
n,m=map(int,input().split())
XYZ=[list(map(int,input().split())) for _ in range(n)]

ans=0
for i in range(2):
  for j in range(2):
    for k in range(2):
      tmp=[]
      for x,y,z in XYZ:
        tmp.append((-1)**i*x + (-1)**j*y + (-1)**k*z)
      tmp.sort()
      ans=max(ans,abs(sum(tmp[:m])))
print(ans)

Measured memory_bytes: 3316
import sys
input = sys.stdin.buffer.readline

def main():
    N,X = map(int,input().split())
    
    p = [1]
    al = [1]
    for i in range(N):
        p.append(p[-1]*2+1)
        al.append(al[-1]*2+3)

    def eat(N,X):
        if N == 0:
            if X <= 0:
                return 0
            else:
                return 1
        elif X <= 1+al[N-1]:
            return eat(N-1,X-1)
        else:
            return eat(N-1,X-al[N-1]-2)+1+p[N-1]
            
    print(eat(N,X))

if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

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

		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();

		for( int i = 0; i <= B; i++) {
			if((A*i) % B == C) {
				System.out.println("YES");
				return;
			}
		}
		System.out.println("NO");
	}
}


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

int main(){
  string n;
  cin >> n;
  int res = 0;
  int kaisuu = 0;
  int x = n.size();
  if(x%9==0) kaisuu = x/9;
  else kaisuu = x/9 +1;
  for(int i = 0; i<x; i+=9){
    string m = n.substr(i, 9);
    int a = stoi(m);
    while(a>0){
      res += a%10;
      a /= 10;
    }
    res %= 9;
  }
  if(res%9==0) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3716
import java.util.*;
public class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int i,j,k,x,c;
		int p=sc.nextInt();
		int [][]ps =new int[p][3];

		for(i=0;i<p;i++){
			for(j=0;j<3;j++){
				int s=sc.nextInt();
				ps[i][j]=s;
			}
		}
		
		int [][]sf = new int[p][3];
		
		for(i=0;i<p;i++){
			for(j=0;j<3;j++){
				sf[i][j]=ps[i][j];
			}
		}
		
		for(i=0;i<3;i++){
			for(j=0;j<p;j++){
				for(k=(j+1);k<p;k++){
					
					if(ps[j][i]==ps[k][i]){
						sf[j][i]=0;
						sf[k][i]=0;
					}
					
				}
			}
		}
		
		
		for(i=0;i<p;i++){
			for(j=1;j<3;j++){
				sf[i][0]=sf[i][0]+sf[i][j];
			}
			System.out.printf("%d\n",sf[i][0]);
		}
		
		
		sc.close();
		System.exit(0);
	}
}

Measured memory_bytes: 21152
package main

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

const (
	initialBufSize = 100000
	maxBufSize     = 1000000
)

var sc *bufio.Scanner

func initScanner(r io.Reader) *bufio.Scanner {
	buf := make([]byte, initialBufSize)

	sc := bufio.NewScanner(r)
	sc.Buffer(buf, maxBufSize)
	sc.Split(bufio.ScanWords) // bufio.ScanLines
	return sc
}

func main() {
	sc = initScanner(os.Stdin)
	fmt.Println(resolve(parseProblem()))
}

func parseProblem() int {
	n, m := scanInt(sc), scanInt(sc)
	tb := make([][]int, m)
	for i := 0; i < m; i++ {
		tb[i] = make([]int, n)
		l := scanInt(sc)
		for j := 0; j < l; j++ {
			tb[i][scanInt(sc)-1] = 1
		}
	}
	ps := make([]int, m)
	for i := 0; i < m; i++ {
		ps[i] = scanInt(sc)
	}
	num := 0
	for i := 0; i < 1<<uint(n); i++ {
		if accept(n, m, tb, ps, i) {
			num++
		}
	}
	return num
}

func accept(n, m int, tb [][]int, ps []int, idx int) bool {
	for i := 0; i < m; i++ {
		sum := 0
		for j := 0; j < n; j++ {
			if idx&(1<<uint(j)) == 0 {
				continue
			}
			sum += tb[i][j]
		}
		if ps[i] != sum%2 {
			return false
		}
	}
	return true
}

func resolve(n int) int {
	return n
}

// snip-scan-funcs
func scanInt(sc *bufio.Scanner) int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return int(i)
}
func scanString(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}


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

using namespace std;

using ll = long long;

struct State {
    int at;
    ll cost;
    //int prev;
    State(int at, ll cost/*, int prev*/) : at(at), cost(cost)/*, prev(prev)*/ {}
    bool operator>(const State& s) const {
        //if (cost != s.cost) return cost > s.cost;
        //if (prev != s.prev) return prev > s.prev; //最短経路を辞書順最小にする(省略可)
        //return at > s.at;
        return cost > s.cost;
    }
};

struct Edge {
    int to;
    ll cost;
    Edge(int to, ll cost) : to(to), cost(cost) {}
};

using Graph = vector<vector<Edge> >; //隣接リスト

const ll INF = 1e15;
//const int NONE = -1;

//sは始点、mincは最短経路のコスト、prevsは最短経路をたどる際の前の頂点
void dijkstra(int s, const Graph& graph, vector<ll>& minc/*, vector<int>& prevs*/){
    minc.assign(graph.size(), INF);
    //prevs.assign(graph.size(), NONE);

    priority_queue<State, vector<State>, greater<State> > pq;
    pq.emplace(s, 0/*, NONE*/);

    while(!pq.empty()) {
        State cur = pq.top();
        pq.pop();
        if (minc[cur.at] <= cur.cost) continue;

        minc[cur.at] = cur.cost;
        //prevs[cur.at] = cur.prev;

        for(const Edge& e : graph[cur.at]) {
            ll cost = cur.cost + e.cost;
            if (minc[e.to] <= cost) continue;
            pq.emplace(e.to, cost/*, cur.at*/);
        }
    }
}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    s--; t--;
    Graph g1(n), g2(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        ll a, b;
        cin >> u >> v >> a >> b;
        u--; v--;
        g1[u].emplace_back(v, a);
        g1[v].emplace_back(u, a);
        g2[u].emplace_back(v, b);
        g2[v].emplace_back(u, b);
    }
 
    vector<ll> minc1(n, INF), minc2(n, INF);
    dijkstra(s, g1, minc1);
    dijkstra(t, g2, minc2);
 
    vector<ll> ans(n, INF);
    for (int i = n - 1; i >= 0; i--) {
        ans[i] = min(ans[i], minc1[i] + minc2[i]);
        if (i < n - 1) ans[i] = min(ans[i], ans[i + 1]);
    }
 
    for (int i = 0; i < n; i++) {
        cout << INF - ans[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 19004
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Threading;

using Pair = System.Collections.Generic.KeyValuePair<int, int>;

class Program
{
	public Program() { }

	static void Main(string[] args)
	{
		new Program().prog();
	}
	Scanner cin;
	const int MOD = 1000000007;
	const int INF = int.MaxValue;
	const double EPS = 1e-7;
	const double PI = 3.1415926536;

	void prog()
	{
		cin = new Scanner();
		int[,] dir8 = new int[8, 2] { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 }, { 0, 1 }, { 1, -1 }, { 1, 0 }, { 1, 1 } };
		int[,] dir4 = new int[4, 2] { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };

		int N = cin.nextInt();
		int[] T = new int[N];
		int[] A = new int[N];
		bool[] d = new bool[N];
		int[] height = new int[N];
		for (int i = 0; i < N; i++)
		{
			T[i] = cin.nextInt();
		}
		for (int i = 0; i < N; i++)
		{
			A[i] = cin.nextInt();
		}
		d[0]= true;
		d[N - 1] = true;
		if (T[N - 1] != A[0])
		{
			Console.WriteLine(0);
			return;
		}
		for (int i = 1; i < N; i++)
		{
			if(T[i] > T[i - 1])
			{
				d[i] = true;
			}
			height[i] = T[i];
		}
		for (int i = N - 2; i >= 0; i--)
		{
			if(A[i] > A[i + 1])
			{
				if ((d[i] && A[i] != T[i]) || A[i] > height[i])
				{
					Console.WriteLine(0);
					return;
				}
				d[i] = true;
			}
			height[i] = Math.Min(height[i], A[i]);
		}
		long ans = 1;
		for (int i = 1; i < N - 1; i++)
		{
			if (d[i]) continue;
			ans *= height[i];
			ans %= MOD;
		}
		Console.WriteLine(ans);
	}
}

class Scanner
{
	string[] s;
	int i;

	char[] cs = new char[] { ' ' };

	public Scanner()
	{
		s = new string[0];
		i = 0;
	}

	public string next()
	{
		if (i < s.Length) return s[i++];
		string st = Console.ReadLine();
		while (st == "") st = Console.ReadLine();
		s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
		i = 0;
		return next();
	}

	public int nextInt()
	{
		return int.Parse(next());
	}

	public long nextLong()
	{
		return long.Parse(next());
	}

	public double nextDouble()
	{
		return double.Parse(next());
	}
}

Measured memory_bytes: 23400
N = int(input())
S = [input() for k in range(N)]
ans = 0
for s in S:
    ans += s.count("AB")


C = [[0,0] for k in range(N)]
for k in range(N):
    if S[k][0] == "B":
        C[k][1] = 1
    if S[k][-1] == "A":
        C[k][0] = 1
p = 0
q = 0
r = 0
for k in range(N):
    if C[k] == [0, 1]:
        p += 1
    elif C[k] == [1, 1]:
        q += 1
    elif C[k] == [1, 0]:
        r += 1
if p >= 1 and r >= 1 and q >= 1:
    print(ans + q+1 + min(p-1,r-1))
elif (p>=1 and r==0 and q>=1) or (p==0 and r>=1 and q>=1):
    print(ans + q)
elif p >= 1 and r >= 1 and q == 0:
    print(ans + min(p,r))
elif p == 0 and r == 0 and q >= 1:
    print(ans + q-1)
else:
    print(ans)

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

int main(){
    const int n=10;
    int h[n];
    for(int i=0;i<n;i++)
        cin >> h[i];
    sort(h,h+n);
    for(int i=0;i<3;i++)
        cout << h[n-1-i] << endl;
    return 0;
}

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

#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
#define int long long
#define double long double

#define all(a)      (a).begin(),(a).end()
#define sz(x)       (int)x.size()

#define ff first
#define ss second
#define mp make_pair

#define pb push_back
#define endl "\n"

#define f(i,l,r) for(int i=l;i<r;i++)
#define rf(i,r,l) for(int i=r;i>=l;i--)

#define bp builtin_popcountll
#define inf 1e18

const int N = 1e6 + 5;
const int M = 1e9 + 7;

int dii[N];

void solve(){
   int n;
   cin >> n;

   for(int i = 1 ; i<N ; i++) dii[i] = 1;

   for(int i = 1 ; i<N ; i++){
      for(int j=2*i ; j<N ; j+=i){
         dii[j] ++;
      }
   }

   int ans = 0;
   for(int i=1 ; i<=n-1 ; i++){
      int x = n - i;
      ans += dii[x];
   }
   cout << ans << endl;
}

signed main()
{
   FAST

   int t = 1;
   // cin>>t;
      #ifndef ONLINE_JUDGE
   freopen("input_sublime.txt", "r", stdin);
   freopen("output_sublime.txt", "w", stdout);
   #endif

   for (int tc = 1; tc <= t; tc++)
   {
      solve();
   }
}

Measured memory_bytes: 11432
#include<stdio.h>
int main(){
	int a,b,c,t;
	scanf("%d %d %d",&a,&b,&c);
	if(a==b&&b==c)
		printf("%d\n",a+b);
	else{
		if(b>a){
			t=a;a=b;b=t;
		}
		if(c>a){
			t=a;a=c;c=t;
		}
	printf("%d\n",b+c);
	}
	return 0;
}

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

#define ll long long

ll n, k;

vector<ll> vis(300000, -1);

int main()
{
    cin >> n >> k;
    vector<ll> a(n + 2);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }

    ll next = 1, unit;
    vis[next] = 0;
    for (ll i = 1; i <= k; i++)
    {
        next = a[next];

        if (vis[next] != -1)
        {
            unit = i - vis[next];
            break;
        }
        else
        {
            vis[next] = i;
        }
    }

    if (unit)
    {
        ll c = (k - vis[next]) / unit;

        for (ll i = vis[next] + c * unit + 1; i <= k; i++)
            next = a[next];
    }

    cout << next << endl;
}

Measured memory_bytes: 7176
#include <iostream>
#include <algorithm>
using namespace std;
int dp[3030];

int main() {
  int N, T, A, B; cin >> N >> T;
  pair<int, int> ps[N];
  for(int i = 0; i < N; ++i) {
    cin >> A >> B;
    ps[i].first = A, ps[i].second = B;
  }
  sort(ps, ps + N);
  
  for(auto p : ps)
    for(int j = T-1; j >= 0; --j)
      dp[min(T, j + p.first)] = max(dp[min(T, j + p.first)], dp[j] + p.second);
  cout << dp[T];
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,w;
	scanf("%d",&n);
	scanf("%d",&w);
	vector<int> v(n),cos(n);
	
	for(int i = 0; i < n; i++)
		scanf("%d %d",&v[i],&cos[i]);
	
	int lim = 0;
	for(int x : cos) lim += x;
	vector<int> dp(lim+1,-1);
	dp[0] = w;
	
	for(int i = 0; i < n; i++){
		for(int j = lim; j >= 0; j--){
			if(dp[j] - v[i] >= 0){
				dp[j+cos[i]] = max(dp[j+cos[i]], dp[j]-v[i]);
			//	printf("dp_j:%d dp_j+cos[%d]:%d -> %d\n",dp[j],i,dp[j+cos[i]],j+cos[i]);
			}
		}
	}
	int ans = 0;
	for(int i = 0; i <= lim; i++)
		if(dp[i] >= 0)
			ans = i;
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 3812
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/














int N, A[201010], B[201010];
//---------------------------------------------------------------------------------------------------
bool solve() {
	rrep(i, N, 1) {
		int other = 0;
		for (int x = i * 2; x <= N; x += i) if (B[x]) other++;
		
		if (other % 2 != A[i]) B[i] = 1;
	}

	return true;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 1, N + 1) cin >> A[i];

	if (!solve()) {
		printf("-1\n");
		return;
	}

	vector<int> ans;
	rep(i, 1, N + 1) if (B[i]) ans.push_back(i);

	int M = ans.size();
	printf("%d\n", M);
	rep(i, 0, M) {
		if(i) printf(" ");
		printf("%d", ans[i]);
	}
	printf("\n");
}







Measured memory_bytes: 2936
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  vector<char> moji(26);
  vector<int> count(26,0);
  for(int i = 0;i < s.size();i++){
    for(int j = 97;j < 122;j++){
      if(s[i] == j) count.at(j-97)++;
    }
  }
  bool answer = true;
  for(int i = 0;i < 26;i++){
    if(count.at(i) % 2 == 1){
      answer = false;
    }
  }
  if(answer == true) cout << "Yes" << endl;
  else cout << "No" << endl;
}


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

int top = 0;
vector<int> A(MAX);

void push(int x) {
    top++;
    A.at(top) = x;
}

int pop() {
    top--;
    return A.at(top + 1);
}

int main() {
    string c;
    int key;
    int a, b;

    while (cin >> c)
    {
        if (c == "+") {
            a = pop();
            b = pop();
            push(a + b);
        }
        else if (c == "*")
        {
            a = pop();
            b = pop();
            push(a * b);
        }
        else if (c == "-")
        {
            a = pop();
            b = pop();
            push(b-a);
        }
        else
        {
            key = stoi(c);
            push(key);
        }
        
    }
    cout << pop() << endl;
}



Measured memory_bytes: 3192
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws FileNotFoundException {

		//    	File file = new File("src/in.txt");
		//    	Scanner sc = new Scanner(file);

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int K = sc.nextInt();
		int[] H = new int[N];
		for(int i=0;i<N;i++) {
			H[i]= sc.nextInt();
		}
		if(K>=N) {
			System.out.println("0");
		} else {
			Arrays.sort(H);
			long ans = 0;
			for(int i=0;i<=N-1-K;i++) {
				ans += H[i];
			}
			System.out.println(ans);
		}


	}
}


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

int main() {
  int a, b; // 1 <= a,b <= 10000, a,bは整数
  
  cin >> a >> b ;

  if((a * b) % 2 == 0){
    cout << "Even" << endl;
  }else{
    cout << "Odd" << endl;
  }
  
}

Measured memory_bytes: 3572
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

int main (int argc, char *argv[]) {
    double d, e;
    while (cin>>d>>e, d||e) {
        double ans = 1000000.0;
        for (double x = 0.0; x <= d / 2; ++x) {
            double y = d - x;
            ans = min(ans, abs(sqrt(pow(x, 2)+pow(y, 2)) - e));
        }
        cout<<ans<<endl;
    }
    return 0;
}


Measured memory_bytes: 3200
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define per(i, n) for(ll i=((ll)(n))-1; i>=0; i--)
#define perf(i, n) for(ll i=((ll)(n)); i>0; i--)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
template<class T>bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
using namespace std;

int main(){
    Init();
    ll w, h, n; cin >> w >> h >> n;
    ll sx = 0, sy = 0, ex = w, ey = h;

    rep(i, n){
        ll x, y, a; cin >> x >> y >> a;
        if(a == 1){ if(sx < x) sx = x; }
        else if(a == 2){ if(ex > x) ex = x; }
        else if(a == 3){ if(sy < y) sy = y; }
        else if(ey > y) ey = y;
    }
    if(sx <= ex && sy <= ey) cout << (ex-sx)*(ey-sy) << endl;
    else cout << 0 << endl;
}

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

int main(){
  int N;
  string S;
  int x = 0,max = 0;
  cin >> N >> S;
  for(int i = 0; i < N; i++){
    if(S.at(i) == 'I'){
      if(x + 1 > max) max++;
      x++;
    }else{
      x--;
    }
  }
  cout << max <<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    int A, B, C, D;
    string ans;
    int i = 0;

    cin >> A >> B >> C >> D;

    
    while (true) {
        if (i % 2 == 0) {
            C -= B;
            if (C <= 0) {
                ans = "Yes";
                break;
            }
        } else {
            A -= D;
            if (A <= 0) {
                ans = "No";
                break;
            }
        }
        i++;
    }

    cout << ans << endl;
}


Measured memory_bytes: 3632
#include<iostream>
using namespace std;
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
     int h,w;
     cin>>h>>w;
     char mat[h+1][w+1];
     int i,j;
     for(i=1;i<=h;i++)
     {
		 for(j=1;j<=w;j++)
	       cin>>mat[i][j];
	 }
	 int left[h+1][w+1];
	 int right[h+1][w+1];
	 for(i=1;i<=h;i++)
	 {
		 int index=0;
		 for(j=1;j<=w;j++)
		 {
			 if(mat[i][j]=='#')
			    index=j;
			 left[i][j]=index;
		 }
     }
     for(i=1;i<=h;i++)
     {
		 int index=w+1;
		 for(j=w;j>=1;j--)
		 {
			 if(mat[i][j]=='#')
			    index=j;
			 right[i][j]=index;
		 }
	 }
	 int top[h+1][w+1];
	 int bottom[h+1][w+1];
	 for(j=1;j<=w;j++)
	 {
		 int index=0;
		 for(i=1;i<=h;i++)
		 {
			 if(mat[i][j]=='#')
			    index=i;
			 top[i][j]=index;
		 }
	 }
	 for(j=1;j<=w;j++)
	 {
		 int index=h+1;
		 for(i=h;i>=1;i--)
		 {
			 if(mat[i][j]=='#')
			    index=i;
			 bottom[i][j]=index;
		 }
	 }
	 int answer=0;
	 for(i=1;i<=h;i++)
	 {
		 for(j=1;j<=w;j++)
	     {
			 if(mat[i][j]=='.')
			 {
				 int x=left[i][j];
				 int y=right[i][j];
				 int p=top[i][j];
				 int q=bottom[i][j];
				 int val=y-x-1+(q-p-2);
				 answer=max(answer,val);
			 }
	     }
	 }
	 cout<<answer<<endl;
}


Measured memory_bytes: 66688
import java.util.Scanner;

/**
 * Created by donamphuong on 25/09/2016.
 */
public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);

        if(s.hasNext()) {
            String input = s.next();
            System.out.println(input.substring(0, 4) + " " + input.substring(4));
        }
    }
}


Measured memory_bytes: 9680
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <iomanip>
using namespace std;
#define INF 1e9
#define PI acos(-1)
typedef long long ll;



int main() {
	int a, b;
	cin >> a >> b;
	if (a + b == 15)cout << '+' << endl;
	else if (a*b == 15)cout << '*' << endl;
	else cout << 'x' << endl;
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("5 4");
            //Yay!
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("8 8");
            //Yay!
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("11 4");
            //:(
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();

        int A = wkArr[0];
        int B = wkArr[1];

        if (A <= 8 && B <= 8) {
            Console.WriteLine("Yay!");
        }
        else {
            Console.WriteLine(":(");
        }
    }
}


Measured memory_bytes: 13268
import numpy as np

#k ,n = list(map(int,(input().split())))
#a = list(map(int,(input().split())))
#a = np.array(a)
#sp = np.diff(a)
#print((sum(sp)))

s = list(input())
if s[2] ==  s[3] and s[4] == s[5] :
  print('Yes')
else:
  print('No')

Measured memory_bytes: 12488
#include"bits/stdc++.h"

using namespace std; 

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef pair<LL, LL> PLL;
typedef vector<PLL> VPLL;
typedef priority_queue<LL> PQ_DESC;
typedef priority_queue<LL, VL, greater<LL>> PQ_ASC;
typedef priority_queue<PII> PQ_DESC_PII;
typedef priority_queue<PII, vector<PII>, greater<PII>> PQ_ASC_PII;
typedef priority_queue<VL> PQ_DESC_VL;
typedef priority_queue<VL, vector<VL>, greater<VL>> PQ_ASC_VL;
typedef priority_queue<PLL> PQ_DESC_PLL;
typedef priority_queue<PLL, vector<PLL>, greater<PLL>> PQ_ASC_PLL;

#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define MP make_pair
#define SORT_ASC(c) sort(ALL(c))
//#define SORT_DESC(c) sort(ALL(c), greater<typeof(*((c).begin()))>())
#define SORT_DESC(c) sort((c).rbegin(),(c).rend())
#define REV(c) reverse((c).begin(), (c).end())
#define SIZE(a) int((a).size())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ROF(i,a,b) for(int i=(b-1);i>=(a);--i)
#define REP(i,n) FOR(i,0,n)
#define PER(i,n) ROF(i,0,n)

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int LARGE_INT = 1e9+100;
const int INF = 2e9+100;
const LL INF_LL = (LL)INF*(LL)INF;
const int MOD = 1e9+7;

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

void Main()
{
    string s;cin>>s;
    int y,m,d;
    sscanf(s.c_str(),"%d/%d/%d",&y,&m,&d);

    if(y<2019){
        cout<<"Heisei"<<endl;
        return;
    }
    if(y>2019){
        cout<<"TBD"<<endl;
        return;
    }

    if(m<4){
        cout<<"Heisei"<<endl;
        return;
    }
    if(m>4){
        cout<<"TBD"<<endl;
        return;
    }

    
    if(d<=30){
        cout<<"Heisei"<<endl;
        return;
    }
    else{
        cout<<"TBD"<<endl;
        return;
    }


    
	return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
    return 0;
}

Measured memory_bytes: 3716
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
int main()
{
long int n,k;
int ip;
set< long int> s;
map<long int,long int> m;
cin>>n>>k;
int i;
for(i=0;i<n;i++)
{
    cin>>ip;
    s.insert(ip);
    m[ip]++;
}
map<long int,long int>::iterator it;
it=m.begin();
int c=s.size();
vector<int> a(n);
for(i=1;i<=c;i++)
{
    a[(*it).second]++;
    it++;
}
if(c<k)
{
    cout<<0;
}
else
{

 long int diff=c-k;
 long int change=0;
 it=m.end();
 int j=1;
 for(i=0;i<diff;i++)
 {
    while(1)
    {
        if(a[j]!=0)
        {
            change+=j;
            a[j]--;
            break;
        }
        else
        j++;
    }
 }
    cout<<change;
}
return 0;
}


Measured memory_bytes: 22912
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
using ll = long long;
using ld = long double;
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define rep3(i, n) for (ll i = 1; i < (ll)(n+1); i++)
#define rep4(i, s, n) for (ll i = (s); i < (ll)(n+1); i++)
#define repr(i,n) for (ll i = (n-1); i>=0;i--)
#define repr3(i,n) for(ll i = (n);i>0;i--)
#define stlen(s) ll s.size()-1
#define all(v) v.begin(), v.end()
#define cout(n) cout<<std::fixed<<std::setprecision(n)
using Graph = vector<vector<int>>;
#define INF1  INT_MAX;
#define INF2  LLONG_MAX;
#define PI  3.14159265358979323846;
 
vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0; // 指数

        // 割れる限り割り続ける
        while (N % a == 0) {
            ++ex;
            N /= a;
        }

        // その結果を push
        res.push_back({a, ex});
    }

    // 最後に残った数について
    if (N != 1) res.push_back({N, 1});
    return res;
}



int main() {
    long long N;
    cin >> N;
    //pairの書き換えが煩雑であるので、素数リストと指数連想配列に分ける
   map<ll,ll> prime_count;
   vector<ll> prime_list;
   rep3(j,N){
    //resに素数のペア(素数、その素数の指数）の配列が入る
    const auto  &res = prime_factorize(j);
    
   rep(i,res.size()){
       if(prime_count[res[i].first]==0){
           prime_list.push_back(res[i].first);
       }
       prime_count[res[i].first]+=res[i].second;
   }
   }
   ll ans=1,div=(ll)powl(10,9)+7;
   rep(i,prime_list.size()){
       ans*=prime_count[prime_list[i]]+1;
       ans%=div;


   }
   cout<<ans<<endl;
   
    

return 0;
}



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

using namespace std;

using ll = long long;
using vi = vector<int>;
using db = double;
#define pb push_back
#define fir first
#define sec second

ll a[5];

int main() {
	for (int i = 1; i <= 4; ++i)
		cin >> a[i];
	
	for (int i = 1; i <= 3; ++i)
		a[i + 1] = min(a[i + 1], a[i] * 2);
	
	ll n;
	cin >> n;
	n *= 4;
	
	ll s = 0;
	for (int i = 4; i >= 1; --i) {
		s += (n >> i - 1) * a[i];
		n -= n >> i - 1 << i - 1;
	}
	
	cout << s << endl;
	
	return 0;
}


Measured memory_bytes: 256
function Main(input) {
  input = input.split("\n");
  const N = parseInt(input[0],10);
  const changeInt = (n) => {
    return parseInt(n, 10);
  };
  const abc = [];
  for (var i = 0; i < N; i++) {
    abc.push(input[i + 1].split(' ').map(changeInt));
  }
  console.log(dp(N,abc));
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

function dp(N,abc) {
  const dp = Array(N).fill(0).map(n => {
    return Array(3).fill(0);
  });
  dp[0] = [...abc[0]];
  for (var i = 1; i < N; i++) {
    for (var j = 0; j < 3; j++) {
      for (var k = 0; k < 3; k++) {
          if (j === k) continue;
          dp[i][j] = Math.max(dp[i][j],abc[i][j] + dp[i - 1][k]);
      }
    }
  }
  return Math.max(...dp[N-1]);
}


Measured memory_bytes: 69120
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define printVec(v) printf("{"); for (const auto& i : v) { std::cout << i << ", "; } printf("}\n");
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; }
using namespace std;
using P = pair<int,int>;
using ll = long long;
const ll INF = 1LL<<60;
const double PI = 3.1415926535897932;
const int MOD = 1e9 + 7;

//cin.tie(0);ios::sync_with_stdio(false);
int main() {
  int n;
  cin >> n;
  vector<int> C(n - 1);
  vector<int> S(n - 1);
  vector<int> F(n - 1);
  rep (i, n - 1) {
    cin >> C[i] >> S[i] >> F[i];
  }

  for (int i = 0; i < n - 1; i++) {
    ll ans = 0;
    for (int j = i; j < n - 1; j++) {
      if (j == i) {
          ans += C[j] + S[j];
      } else {
        if (ans < S[j]) {
          ans += S[j] - ans;
        } else {
          int tmp = ans % F[j];
          if (tmp != 0) {
            ans += F[j] - tmp;
          }
        }
        ans += C[j];
      }
    }
    cout << ans << endl;
  }
  cout << 0 << endl;
  
  return 0;
}


Measured memory_bytes: 3588
n,a[100],dp[1<<17];
i,j,l;
main(k)
{
	for(scanf("%d%d",&n,&k);~scanf("%d",a+j++););
	for(;i++<k;)
	{
		for(j=0;j<n&&a[j]<=i;j++)dp[i]|=3-dp[i-a[j]];
	}
	puts(dp[k]&1?"First":"Second");
}

Measured memory_bytes: 512
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics.CodeAnalysis;
using System.Threading;
using System.IO.Pipes;
using System.ComponentModel;
using System.Drawing;
using Microsoft.VisualBasic;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            long N = long.Parse(Console.ReadLine());
            long[] Arr = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();

            long tall = 0;
            long ans = 0;

            foreach (long l in Arr) 
            {
                if (tall > l)
                {
                    ans += tall - l;
                }
                else 
                {
                    tall = l;
                }
            }

            Console.WriteLine(ans);

        }

    }
}


Measured memory_bytes: 47788
#include<iostream>
#include<vector>
 
using namespace std;
int main(){
 
  int n,k,d,a;
  cin>>n;cin>>k;
  vector<int> man(n+1,0);
  for(int i=0;i<k;i++){
    cin>>d;
    for(int j=0;j<d;j++){
      cin>>a;man[a]++;
    }
  }
  int ans=0;
  for(int i=1;i<=n;i++){
    if(man[i]==0){ans++;}
  }
  cout<<ans;
  return 0;
}

Measured memory_bytes: 3572
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<int> ve;

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

	ve a(n + 5);

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

	int d[100005];
	ll p = 0;

	for (int i = 1; i <= 100000; i++) {
		d[i]=0;
	}
	for (int i = 0; i < n; i++) {
		d[a[i]] += 1;
		p += a[i];
	}

	for (int i = 0; i < q;i++) {

		int b, c;
		cin >> b >> c;

		p += d[b]*(c-b);

		d[c] += d[b];
		d[b] = 0;

		cout << p<<endl;
	}


	return 0;
}

Measured memory_bytes: 4052
#include<bits/stdc++.h>
using namespace std;
int main(){
	int N,max = 1,num,rec = 0;
	int i;
	int a[110];
	cin >> N;
	a[0] = 0;

	for(i = 1;i <= N;++i){
		a[i] = 0;
		num = i;
		while(num % 2 == 0){
			num = num / 2;
			++a[i];
		}
	}

	for(i = 1;i <= N;++i){
		if(a[i] > rec){
			max = i;
			rec = a[i];
		}
		else;
	}
	
	cout << max << endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    int K = sc.nextInt();
    ArrayList<String> list = new ArrayList<>();
    for (int i = 0; i < s.length(); i++) {
      for (int j = i + 1; j <= Math.min(s.length(), i + K); j++) {
        String tmp = s.substring(i, j);
        if (!list.contains(tmp)) {
          list.add(tmp);
        }
      }
    }
    Collections.sort(list);
    System.out.println(list.get(K - 1));
  }
}

Measured memory_bytes: 24652
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <queue>
#include <numeric>
#include <deque>
#include <cstring>
#include <iterator>
#include <map>
#include <cstdlib>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <complex>
#include <bitset>
#include <chrono>
#include <random>
#include <assert.h>

using namespace std;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define eb emplace_back
#define el '\n'
typedef  long long  ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<bool> vb;


//const int mod=1000000007;
//const int mod=998244353;
ll mod;

vvi adj;
vb mark;
vll black;
vll mul;
vi no;
void dfs1(int u,int p){
    vll pref,suff;
    int id=0;
    for(auto it: adj[u]){
        if(it!=p){
            dfs1(it,u);
            pref.pb(1+black[it]);
            suff.pb(1+black[it]);
            no[it]=id++;
            black[u]*=1+black[it];
            black[u]%=mod;
        }
    }
    for(int i=1; i<id; i++){
        pref[i]*=pref[i-1];
        pref[i]%=mod;
    }
    for(int i=id-2; i>=0; i--){
        suff[i]*=suff[i+1];
        suff[i]%=mod;
    }
//    cout << id << ' ' << "id" <<  el;
//    print(pref);
    for(auto it: adj[u]){
        if(it!=p){
//            cout << it << ' ' << "it" ;
            if(suff.size()==1){
                mul[it]=1;
                break;
            }
            if(no[it]==0){
                mul[it]=suff[1];
            }
            else if(no[it]==(int)pref.size()-1){
                mul[it]=pref[pref.size()-2];
            }
            else{
                mul[it]=pref[no[it]-1]*suff[no[it]+1]%mod;
            }
//            cout << mul[it] << el;
        }
    }
    pref.clear();
    suff.clear();
}



void dfs2(int u, int p, ll val){
    val%=mod;
    black[u]*=val;
    black[u]%=mod;
    for(auto it: adj[u]){
        if(it!=p){
            dfs2(it , u ,1+val*mul[it]);
        }
    }
}

int main()
{   ios_base::sync_with_stdio(false);cin.tie(NULL);
    ll t,n,m,k,q,x,a,b,c,d,y,l,r;
    cin >> n >> mod;
    adj.resize(n+1);
    mark.resize(n+1);
    black.assign(n+1,1);
    no.resize(n+1);
    mul.resize(n+1);
    for(int i=1; i<n; i++){
        cin >> a >> b;
        adj[a].pb((int)b);
        adj[b].pb((int)a);
    }
    dfs1(1,1);
    for(auto it: adj[1]){
        dfs2(it, 1, 1+mul[it]);
    }
//    print(mul);
//    print(black);
//    mul[1]=1;
//    print(black);
    for(int i=1; i<=n; i++)
        cout << black[i] << el;
    
    return 0;
}


Measured memory_bytes: 20096
#include <iostream>
#include <string>
int main(){
std::string S;
std::cin >> S;
if(S[0]=='Y' && S[1]=='A' && S[2]=='K' && S[3]=='I')
std::cout << "Yes" << std::endl;
else
std::cout << "No" << std::endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll solve1(ll x) {
    ll ret=1;
    for (ll i=2;i*i<=x;i++){
        if (x%i==0){
            ret+=2;
            if (x/i==i)ret--;
        }
    }
    return ret;
}
ll solve2(ll x) {
    ll ret=1,tp;
    for (ll i=2;i*i<=x;i++) {
        if (x%i==0){
            ll tmp=x/i;
            tp=x;
            while (tp%i==0){
                tp/=i;
            }
            if (tp>i)tp%=i;
            ret+=(tp==1);
            if (tmp!=i) {
                tp=x;
                while(tp%tmp==0){
                    tp/=tmp;
                }
                if (tp>tmp)tp%=tmp;
                ret+=(tp==1);
            }
        }
    }
    return ret;
}
int main(){
	ll n;
    cin>>n;
    if (n==2) {
        cout << 1;
        return 0;
    }
    cout<<solve1(n-1)+solve2(n);
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
  
  int ha,ma,hb,mb,k;
  int time;
  cin >> ha >> ma >> hb >> mb >> k;
  
    ha = ha + 1;
    hb = hb - ha;//勉強可能時間
	time = hb * 60 + (60-ma) + mb - k;
  	cout << time;
    
    return 0;
}


Measured memory_bytes: 3624
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<map>
#define mod 1000000007
typedef long long ll;
using namespace std;

int main(){
  string s; cin >> s;
  if(s=="SAT") cout << 1 << endl;
  else if(s=="FRI") cout << 2 << endl;
  else if(s=="THU") cout << 3 << endl;
  else if(s=="WED") cout << 4 << endl;
  else if(s=="TUE") cout << 5 << endl;
  else if(s=="MON") cout << 6 << endl;
  else if(s=="SUN") cout << 7 << endl;
  return 0;
}

Measured memory_bytes: 256
// In the name of God

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9+7;

long long fact[(int)5e7];

long long fast_pow(long long x, long long y) {
	long long ret = 1;
	for(;y;y>>=1) {
		if(y&1) ret=(ret*x)%mod;
		x=(x*x)%mod;
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	long long x, y;
	cin >> x >> y;
	if( (2*y-x)%3 || (2*x-y)%3 ) {
		cout << 0;
		exit(0);
	}
	long long a = (2*y-x)/3;
	long long b = (2*x-y)/3;
	if(a < 0 || b < 0) {
		cout << 0;
		exit(0);
	}
	fact[0] = 1;
	for(int i=1;i<=5e7;i++) fact[i]=(fact[i-1]*i)%mod;
	cout << (((fact[a+b]*fast_pow(fact[a], mod-2))%mod)*fast_pow(fact[b], mod-2))%mod;
	return 0;
}


Measured memory_bytes: 390912
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll dp[1000005][2];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n;
    string s;
    cin>>n>>s;
    for(ll i=0;i<n;i++)
    if(s[i]=='.'){
        dp[i+1][0]=dp[i][0];
        dp[i+1][1]=min(dp[i][0],dp[i][1])+1;
    }
    else{
        dp[i+1][1]=min(dp[i][0],dp[i][1]);
        dp[i+1][0]=dp[i][0]+1;
    }
    cout<<min(dp[n][0],dp[n][1]);
}

Measured memory_bytes: 4628
S = input()

res = 0
cur = 0
N = len(S)
ACGT = ["A", "C", "G", "T"]
for i in range(N):
  if S[i] in ACGT:
    cur += 1
  else:
    cur = 0
  if cur > res:
    res = cur

print(res)


Measured memory_bytes: 2940
#include <iostream>
#include <string>
#define FOR(i,k,n) for (int (i)=(k);(i)<(n);(i)++)
using namespace std;

int main()
{
  string o, e;
  cin >> o >> e;

  FOR (i, 0, e.size()) {
    cout << o[i] << e[i];
  }

  // o の方が長かったら、最後の一文字を出力
  if (o.size() > e.size()) {
    int i;
    i = o.size() - 1;
    cout << o[i];
  }

  cout << endl;

  return 0;
}


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

typedef long long ll;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    char c1, c2;
    cin >> c1 >> c2;
    string s1 = "", s2 = "";
    for (int i = 0; i < c2 - '0'; ++i) {
        s1 += c1;
    }
    for (int i = 0; i < c1 - '0'; ++i) {
        s2 += c2;
    }
    cout << min(s1, s2) << endl;
    return 0;
}



Measured memory_bytes: 256
// C - Splitting Pile
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
#define rp(i,s,e) for(int i=(s);i<(e);++i)

int main(){
	int N; cin>>N;
	vl X(N+1);//累積和
	rp(i, 1, N+1){
		int a; cin>>a;
		X[i] = X[i-1] + a;
	}
	ll ans = LLONG_MAX;
	rp(i, 1, N) ans = min(ans, abs(X[i]*2 - X[N]));
	cout<< ans <<endl;
}

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

int main() {
	int a,b=0;
  	cin >> a;
  	string s = to_string(a);
  	for(int i = 0; i< s.size(); i++) {
		b += (int)(s[i] - '0');
    }
  	cout << (a%b == 0 ? "Yes" :"No") << endl;
}

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

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

#define MOD 1000000007

int main() {
    ll n;
    cin >> n;
    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }
    ll a = 1;
    rep(i, n) {
        a *= 10;
        a %= MOD;
    }
    ll b = 1;
    rep(i, n) {
        b *= 9;
        b %= MOD;
    }
    b *= 2;
    b %= MOD;
    ll c = 1;
    rep(i, n) {
        c *= 8;
        c %= MOD;
    }
    ll ans = a - b;
    ans %= MOD;
    if (ans < 0) {
        ans += MOD;
    }
    ans %= MOD;
    ans += c;
    ans %= MOD;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3600
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Node {
    int key;
    struct Node *right, *left, *parent;
};
typedef struct Node Node;

Node *root, *NIL;

void insert(int k) {
    Node *y = NIL;
    Node *x = root;
    Node *z;
    
    z = (Node *)malloc(sizeof(Node));
    z->key   = k;
    z->left  = NIL;
    z->right = NIL;
    
    while(x != NIL) {
        y = x;
        if(z->key < x->key) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    
    z->parent = y;
    if(y == NIL) {
        root = z;
    } else {
        if( z->key < y->key) {
            y->left = z;
        } else {
            y->right = z;
        }
    }
}

Node * find(Node *u, int k) {
    while(u != NIL && k != u->key) {
        if(k < u->key) u = u->left;
        else u = u->right;
    }
    return u;
}

void inorder(Node *u) {
    if(u == NIL) return;
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
}
void preorder(Node *u) {
    if(u == NIL) return;
    printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
}
    
int main(void) {
    int n, i, x;
    char com[16];
    scanf("%d",&n);
    
    for(i=0;i<n;i++) {
        scanf("%s",com);
        if(com[0] == 'f') {
            scanf("%d",&x);
            Node *t = find(root,x);
            if(t != NIL) printf("yes\n");
            else printf("no\n");
        } else if(!strcmp(com,"insert")) {
            scanf("%d",&x);
            insert(x);
        } else if(!strcmp(com,"print")) {
            inorder(root);
            printf("\n");
            preorder(root);
            printf("\n");
        }
    }

    return 0;
}


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

int main(){
  string n;
  cin >> n;
  if(n[0] == n[1] && n[1] == n[2] || n[1] == n[2] && n[2] == n[3]) cout << "Yes" << endl;
  else cout << "No" << endl;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ld, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int main(){
  fastIO;
  string t;
  ll k;
  cin >> t >> k;
  if(t.size() == 1){
    cout << k/2 << "\n";
    return 0;
  }
  else if(t.size() == 2){
    if(t[0] == t[1]){
      cout << k << "\n";
      return 0;
    }
    else{
      cout << 0 << "\n";
      return 0;
    }
  }
  ll a = 1, b = 1;
  for(int i = 1 ; i < t.size() ; i ++ ){
    if(t[i] == t[i - 1]) a ++ ;
    else break;
  }
  ll n = t.size();
  for(int i = n - 2; i >= 0 ; i -- ){
    if(t[i] == t[i + 1]) b ++ ;
    else break;
  }
  if(a == n){
    cout << (n*k)/2ll;
    return 0;
  }
  ll res = 0;
  int tot = 1;
  for(int i = 1; i < n; i ++ ){
    if(t[i] == t[i - 1]){
      tot ++ ;
    }
    else{
      res += tot/2;
      tot = 1;
    }
  }
  res += tot/2;
  if(t[0] != t[n-1]){
    res *= k;
    cout << res;
    return 0;
  }
  res -= a/2;
  res -= b/2;
  cout << res * 1ll * k + (a/2) + (b/2) + ((a+b)/2) * 1ll * (k-1);
  return 0;
}

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

ll dp[31];
ll memo[31];

ll rec(ll n){
    if(n < 0) return 0;
    if(n < 2) return 1;
    if(memo[n]) return memo[n];
    
    return memo[n] = rec(n - 1) + rec(n - 2) + rec(n - 3);

}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    while(true){
        ll n;
        cin >> n;
        
        if(n == 0) return 0;
        
        rep(i,31){
            memo[i] = 0;
        }
        
        cout << rec(n)/3650 + 1<< endl;
    }
}


Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
int64_t MOD=10000007;

int main() {
  int N,M;
  cin>>N>>M;
  vector<int> A(N);
  for(int i=0;i<N;i++) cin>>A.at(i);
  sort(A.begin(),A.end());
  vector<pair<int,int>> S(M);
  for(int i=0;i<M;i++){
    int a,b;
    cin>>a>>b;
    S.at(i)= make_pair(b,a);
  }
  sort(S.begin(), S.end());
  reverse(S.begin(), S.end());
  vector<int> D;
  bool finished=false;
  for(int i=0;i<M;i++){
    for(int j=0;j<S.at(i).second;j++){
      D.push_back(S.at(i).first);
      if(D.size()>=A.size()){
        finished=true;
        break;
      }
    }
    if(finished) break;
  }
  int Ds=D.size();
  for(int i=0;i<min(N,Ds);i++){
    if(A.at(i)<=D.at(i)) A.at(i)=D.at(i);
    else break;
  }
  int64_t total=0;
  for(int i=0;i<N;i++){
    total+=A.at(i);
  }
  cout<<total;
}


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

int main(){
  int N;
  double ans = 0.0;
  cin >> N;
  vector<double> V(N);

  for (int i = 0; i < N; i++){
    cin >> V[i];
  }
  sort(V.begin(), V.end());
  ans = V[0];
  for (int i = 1; i < N; i++){
    ans = (ans + V[i])/2;
  }
  cout << ans << endl; 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fo(i, a, b) for (int i = a; i < b; i++)
#define re(i, n) fo(i, 0, n)
using namespace std;
typedef long long ll;
int main()
{
  int n;
  cin >> n;
  vector<int> a(n);
  re(i, n) cin >> a[i];

  int x = 0, c = 0;
  while (x == 0) {
    re(i, n) {
      if (a[i] % 2 != 0) x++;
    }
    c += 1;
    re(i, n) a[i] /= 2;
  }

  cout << c - 1 << endl;

  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<cmath>
#include<algorithm>

int main(){
    int n,tmp,count = 0,limit;
    scanf("%d", &n);

    for(int i=0; i<n; i++){
        scanf("%d", &tmp);
        limit = sqrt(tmp);
        for(int j=2; j<= limit; j++){
            if(tmp%j == 0){
                count++;
                break;
            }
        }
    }
    printf("%d\n", n-count);
}


Measured memory_bytes: 2736