akhauriyash/Code-Regression huggingface dataset:
h,w = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

cnt_h = [0]*w
cnt_w=0
ans=0
for i in range(h):
    for j in range(w):
        now = l[i][j]
        if now=="#":
            cnt_w=0
            cnt_h[j]=0
            continue

        if cnt_w==0:
            for k in range(j,w):
                if l[i][k] != "#":
                    cnt_w+=1
                else:
                    break
        if cnt_h[j] == 0:
            for x in range(i,h):
                if l[x][j] != "#":
                    cnt_h[j]+=1
                else:
                    break

        sm = cnt_w + cnt_h[j]
        if ans < sm:
            ans=sm
    cnt_w=0
print(ans-1)

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

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<string> vs;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpll = vector<pll>;
struct Edge {
	ll to;
 	ll cost;
 };
using Graph = vector<vector<Edge>>;

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
/***** define constant start *******/
const ll MOD = 1000000007;
const double PI = 3.1415926535897932;
const ll INF = LLONG_MAX;
string abc = "abcdefghijklmnopqrstuvwxyz";
string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
/****** define constant end ********/
/****** define variable start ******/
/*
string sa, sb, sc;
*/
string s;
/******* define variable end *******/
int solve() {
	/*
	cin >> sa >> sb >> sc;
	ll a = sa.size();
	ll b = sb.size();
	ll c = sb.size();
	ll a_ite = 0;
	ll b_ite = 0;
	ll c_ite = 0;
	ll turn = 0;
	while(!(turn == 0 && a == 0) && !(turn == 1 && b == 0) && !(turn == 2 && c == 0)){
		if(turn == 0){
			if(sa.substr(a_ite, 1) == "a"){
				a--;
				a_ite++;
				turn = 0;
			}else if(sa.substr(a_ite, 1) == "b"){
				a--;
				a_ite++;
				turn = 1;
			}else if(sa.substr(a_ite, 1) == "c"){
				a--;
				a_ite++;
				turn = 2;
			}
		}else if(turn == 1){
			if(sb.substr(b_ite, 1) == "a"){
				b--;
				b_ite++;
				turn = 0;
			}else if(sb.substr(b_ite, 1) == "b"){
				b--;
				b_ite++;
				turn = 1;
			}else if(sb.substr(b_ite, 1) == "c"){
				b--;
				b_ite++;
				turn = 2;
			}
		}else{
			if(sc.substr(c_ite, 1) == "a"){
				c--;
				c_ite++;
				turn = 0;
			}else if(sc.substr(c_ite, 1) == "b"){
				c--;
				c_ite++;
				turn = 1;
			}else if(sc.substr(c_ite, 1) == "c"){
				c--;
				c_ite++;
				turn = 2;
			}
		}
	}
	if(turn == 0 && a == 0){
		cout << "A" << endl;
	}else if(turn == 1 && b == 0){
		cout << "B" << endl;
	}else if(turn == 2 && c == 0){
		cout << "C" << endl;
	}
	*/
	cin >> s;
	vector<ll> chardist(26);
	REP(i, 26){
		ll dist = 0;
		ll dist_tmp = 0;
		REP(j, s.size()){
			if(s[j] == abc[i]){
				dist = max(dist, dist_tmp);
				dist_tmp = 0;
			}else{
				dist_tmp++;
			}
		}
		dist = max(dist, dist_tmp);
		chardist[i] = dist;
	}
	ll ans = INF;
	REP(i, 26){
		ans = min(ans, chardist[i]);
	}
	cout << ans << endl;
	return 0;
}

int main() {
	// clock_t start = clock();
	cout << std::fixed << std::setprecision(10);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int end_solve = solve();
	/*
	clock_t end = clock();
	const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC *
	1000.0; printf("time %lf[ms]\n", time);
	*/

	return end_solve;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
int main(void)
{
    double x1,x2,y1,y2;
    double d1,d2;
    scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
    d1=pow(x2-x1,2);
    d2=pow(y2-y1,2);
    printf("%.8f\n",sqrt(d1+d2));
    
    return 0;
    
    
}



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

int cntone(int num) {
    if (num == 0) {
        return 0;
    }
    return cntone(num / 2) + num % 2;
}
int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> ks(M, vector<int>(N + 1));
    vector<int> p(M);

    rep(i, M) {
        cin >> ks[i][0];
        rep(j, ks[i][0]) { cin >> ks[i][j + 1]; }
    }

    rep(i, M) { cin >> p[i]; }

    vector<int> onbin(M);
    rep(i, M) {
        rep(j, ks[i][0]) { onbin[i] += pow(2, ks[i][j + 1] - 1); }
    }

    long long ans = 0;
    rep(i, pow(2, N)) {
        long long onlight = 0;
        rep(j, M) {
            if (cntone(i & onbin[j]) % 2 == p[j]) {
                onlight++;
            }
        }
        if (onlight == M) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(A: "List[int]"):
    if sum(A)>21:
        print('bust')
    else:
        print('win')


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = [int(next(tokens)) for _ in range(3)]  # type: "List[int]"
    solve(A)

if __name__ == '__main__':
    main()


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

int main() {
    int N, M;
    cin >> N >> M;
    int c[N];
    for (int x = 0; x < N; x++) {
        c[x] = 0;
    }
    for (int x = 0; x < M; x++) {
        int a, b;
        cin >> a >> b;
        c[a - 1]++;
        c[b - 1]++;
    }
    for (int x = 0; x < N; x++) {
        cout << c[x] << endl;
    }
    return 0;
}

Measured memory_bytes: 256
S = input()
N = len(S)
mod = 10 ** 9 + 7
dp1 = [0 for _ in range(N+1)]
dp2 = [0 for _ in range(N+1)]
dp3 = [0 for _ in range(N+1)]
dp4 = [0 for _ in range(N+1)]
dp1[0] = 1

for i in range(N):
    if S[i] == '?':
        dp1[i+1] += 3 * dp1[i]
        dp2[i+1] += 3 * dp2[i] + dp1[i]
        dp3[i+1] += 3 * dp3[i] + dp2[i]
        dp4[i+1] += 3 * dp4[i] + dp3[i]
    else:
        dp1[i+1] += dp1[i]
        dp2[i+1] += dp2[i]
        dp3[i+1] += dp3[i]
        dp4[i+1] += dp4[i]
    if S[i] == 'A':
        dp2[i+1] += dp1[i]
    if S[i] == 'B':
        dp3[i+1] += dp2[i]
    if S[i] == 'C':
        dp4[i+1] += dp3[i]
    dp1[i+1] %= mod
    dp2[i+1] %= mod
    dp3[i+1] %= mod
    dp4[i+1] %= mod

print(dp4[N])

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

template <typename T>
std::vector<T> Compress(std::vector<T> v) {
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
  return v;
}

template <typename T>
T Uncompress(const std::vector<T>& v, T x) {
  return std::lower_bound(v.begin(), v.end(), x) - v.begin();
}

template <typename T>
std::function<T(T)> Uncompressor(const std::vector<T>& v) {
  return [&v](T i) -> T { return Uncompress(v, i); };
}

// #undef DEBUG  // Uncomment this line to forcefully disable debug print.
#if DEBUG
template <typename T>
void debug(T value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define dbg(...)                              \
  do {                                        \
    cerr << #__VA_ARGS__ << ": ";             \
    debug(__VA_ARGS__);                       \
    cerr << " (L" << __LINE__ << ")" << endl; \
  } while (0)
#else
#define dbg(...)
#endif

void read_from_cin() {}
template <typename T, typename... Ts>
void read_from_cin(T& value, Ts&... args) {
  std::cin >> value;
  read_from_cin(args...);
}
#define in(type, ...) \
  type __VA_ARGS__;   \
  read_from_cin(__VA_ARGS__);

template <typename T>
void write_to_cout(const T& value) {
  std::cout << value << std::endl;
}
template <typename T, typename... Ts>
void write_to_cout(const T& value, const Ts&... args) {
  std::cout << value << ' ';
  write_to_cout(args...);
}
#define out(...) write_to_cout(__VA_ARGS__);

#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

using ll = long long;

using namespace std;

const ll INF = 1LL<<60;

void setmin(ll& a, ll b) {
  if (a > b) a = b;
}

int main() {
  in(ll, n, K);
  vector<ll> h(n);
  rep(i, n) cin >> h[i];

  h.push_back(0);
  vector<ll> hc = Compress(h);

  vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(K + 1, vector<ll>(hc.size(), INF)));
  dp[0][0][0] = 0;
  rep(i, n) {
    rep(j, K + 1) {
      rep(k, hc.size()) {
        if (j < K) {
          setmin(dp[i + 1][j + 1][k], dp[i][j][k]);
        }
        setmin(dp[i + 1][j][Uncompress(hc, h[i])], dp[i][j][k] + max(0LL, h[i] - hc[k]));
      }
    }
  }
  ll ans = INF;
  rep(i, K + 1) rep(j, hc.size()) setmin(ans, dp[n][i][j]);
  out(ans);
}


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


void solve(long long N, long long M, std::vector<long long> A, std::vector<long long> B){
    vector<pair<long long, long long>> pairs(N);
    for (int i=0; i<N; i++) {
        pairs[i] = make_pair(A[i], B[i]);
    }
    sort(pairs.begin(), pairs.end());
    long long ans = 0;
    long long ctr = 0;
    for (int i=0; i<M; i++) {
        if (pairs[ctr].second > 0) {
            ans += pairs[ctr].first;
            pairs[ctr].second--;
        } else {
            ctr++;
            i--;
        }
    }
    cout << ans <<endl;
}

// Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    std::vector<long long> A(N);
    std::vector<long long> B(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
        scanf("%lld",&B[i]);
    }
    solve(N, M, std::move(A), std::move(B));
    return 0;
}


Measured memory_bytes: 3328
using System;

class Program
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');

        int a = int.Parse(input[0]);
        int b = int.Parse(input[1]);

        if(a < 1 || b < 1 || 10000 < a || 10000 < b)
        {
            Console.WriteLine("数値が不正です");
            return;
        }

        var result = a * b;

        if(result % 2 == 1)
        {
            Console.WriteLine("Odd");
        }
        else
        {
            Console.WriteLine("Even");
        }
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;

int main() {
    ll X;
    cin >> X;
    double ratio = 1.01;
    ll m = 100;
    for (ll n = 1; n <= 3760; n++) {
        m *= ratio;
        if (m >= X) {
            cout << n << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 3652
#include <iostream>
#define lld long long int
using namespace std;
int main(){
	lld a, b, c, d;
    cin >> a >> b >> c >> d;
    lld x = a*c;
    lld y = a*d;
    lld z = b*c;
    lld u = b*d;
    lld max_ = x;
    max_ = max(max_, y);
    max_ = max(max_, z);
    max_ = max(max_, u);
    cout<<max_<<endl;
}

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

#define int long long

using namespace std;

signed main(void) {

  int n, m; cin >> n >> m;

  vector<int> a(n);
  int _a;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    if (i == 0)
      _a = a[i];
    else
      _a = min(_a, a[i]);
  }
  sort(a.begin(), a.end());

  vector<pair<int, int>> p; // (c, b)
  for (int i = 0; i < m; ++i) {
    int b, c; cin >> b >> c;
    if (c > _a)
      p.push_back(make_pair(c, b));
  }
  sort(p.begin(), p.end(), [](const pair<int, int> &a, const pair<int, int> &b){return a.first > b.first;});

  int _p = 0;
  for (int i = 0; i < n; ++i) {
    if (_p >= p.size())
      break;

    if (p[_p].second == 0)
      ++_p;
    if (_p >= p.size())
      break;

    if (p[_p].first <= a[i]) break;

    a[i] = p[_p].first;
    --p[_p].second;
  }
  cout << accumulate(a.begin(), a.end(), (int)0) << endl;;
    
  return 0;
}


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

using namespace std;


signed main()
{
	cout.tie(0), cin.tie(0), ios::sync_with_stdio(0);

	vector<int> a(3);
	cin >> a[0] >> a[1] >> a[2];
	sort(a.begin(), a.end());
	if (a[0] + a[1] == a[2])
		cout << "Yes";
	else
		cout << "No";

	return 0;
}


Measured memory_bytes: 256
N, K = map(int,input().split())
A = list(map(int,input().split()))
B = [0]*N
C = [0]*N

for k in range(N):
    for l in range(k+1,N):
        if A[k] > A[l]:
            B[k] += 1
    for m in range(k):
        if A[k] > A[m]:
            C[k] +=1

ans = 0
MOD = 10**9 + 7

for e in B:
    ans += e*(K*(K+1)//2)
    ans %= MOD

for e in C:
    ans += e*(K*(K-1)//2)
    ans %= MOD

print(ans)


Measured memory_bytes: 42604
#include <iostream>

using namespace std;

int main(){

    int a, b, c;
    cin >> a >> b;
    
    c = (a-(b*2));

    if(c < 0){
        c = 0;
    }

    cout << c << endl;

}

/*
12 4
4

20 15
0

20 30
0
*/

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

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REV(i,j,k) for(int i=j;i>=k;i--)
#define FORR(i,j,k,l) for(int i=j;i<=k;i+=l)
#define inf         freopen("in.txt", "r", stdin)
#define outf        freopen("out.txt", "w", stdout)
#define pf          printf
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c)    scanf("%d %d %d", &a, &b, &c)
#define clean(mat,n)   FOR(i,0,n) mat[i].clear()
#define minn          (long long)-1000000000000000000
#define maxx          (long long) 1000000000000000000
#define mod          1000000007
#define M_PI           3.14159265358979323846  /* pi */
#define LL           long long
#define NL '\n'
#define cnd tree[idx]
#define lnd (idx<<1)
#define rnd ((idx<<1)+1)
#define PB push_back
#define F first
#define S second
#define MAX 200010
#define MP make_pair
#define valid(nx,ny)  ((nx >= 0) && (nx < row) && (ny >= 0) && (ny < col))
typedef pair<int,int> PR;

LL bit[MAX + 10];
void update(int p, LL dv) ///change value of position p to v
{
	for (; p <= MAX; p += p & (-p)) bit[p] = max(bit[p], dv);
}
LL query(int p)
{
	LL rv = 0;
	for (; p; p -= p & (-p)) rv = max(rv, bit[p]);
	return rv;
}

int ara[MAX], val[MAX], n;
LL prin;

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

    cin >> n;
    FOR(i,0,n-1) cin >> ara[i];
    FOR(i,0,n-1) cin >> val[i];

    FOR(i,0,n-1)
    {
        LL v = query(ara[i] - 1);
        v += val[i];
        update(ara[i], v);
        prin = max(prin, v);
    }
    cout << prin << endl;

    return 0;
}



Measured memory_bytes: 3328
import java.util.*;
public class Main {
	Scanner in = new Scanner(System.in);
	public static void main(String[] args) {
		new Main();
	}

	public Main(){
		new C().doIt();
	}
	
	class C{
		int n,c;
		ArrayList<Pair> list;
		void doIt(){
			n = in.nextInt();
			c = in.nextInt();
			list = new ArrayList<Pair>();
			for(int i=0;i<c;i++)list.add(new Pair(in.nextInt(), in.nextInt()));
			Collections.sort(list);
//			System.out.println(list);
			int[] hyou = new int[n+1];
			for(int i=1;i<=n;i++){
				hyou[i] = hyou[i-1];
				for(int s=0;s<c;s++){
					if(list.get(s).a==i)hyou[i]+=1;
					else if(list.get(s).b==i)hyou[i]-=1;
				}
			}
			int memo = -1;
			for(int i=1;i<=n;i++){
				if(hyou[i]>0){
					if(memo==-1)memo = i; 
					hyou[i] = -1;
				}else{
					if(hyou[i-1]==-1){
						hyou[i] = memo;
						memo = -1;
					}
				}
			}
			int cnt = 0;
			for(int i=0;i<=n;i++){
				if(hyou[i]>0){
					cnt += (i-hyou[i])*2;
				}
				cnt++;
			}
			System.out.println(cnt);
		}
		
		class Pair implements Comparable<Pair>{
			int a,b;
			public Pair(int a,int b) {
				this.a = a;
				this.b = b;
			}
			
			public int compareTo(Pair o) {
				return this.b-o.b;
			}
			
			public String toString(){
				return "["+a+", "+b+"]";
			}
		}
		
	}
	
}

Measured memory_bytes: 21772
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] a = new int[N];
		Arrays.setAll(a, i -> sc.nextInt());
		int ans = 0, key = 1;
		for(int i = 0; i < N; i++) {
			if(a[i] == key) {
				key++;
			}
			else
				ans++;
		}
		System.out.println(key == 1 ? -1 : ans);

	}

}

Measured memory_bytes: 68152
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public final class Main {

    public static void main(String[] args) {
        final Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        String[] line = in.nextLine().split(" ");
        final int n = Integer.parseInt(line[0]);
        final int m = Integer.parseInt(line[1]);
        final long[][] cakes = new long[n][3];
        for (int i = 0; i < n; i++) {
            line = in.nextLine().split(" ");
            cakes[i][0] = Long.parseLong(line[0]);
            cakes[i][1] = Long.parseLong(line[1]);
            cakes[i][2] = Long.parseLong(line[2]);
        }
        long res = 0;
        for (int i = 0; i < 8; i++) {
            final List<Long> curr = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                long S = 0;
                for (int k = 0; k < 3; k++) {
                    if ((i & (1 << k)) != 0) {
                        S += cakes[j][k];
                    } else {
                        S -= cakes[j][k];
                    }
                }
                curr.add(S);
            }
            curr.sort(Comparator.reverseOrder());
            long currRes = 0;
            for (int j = 0; j < m; j++) { currRes += curr.get(j); }
            res = Math.max(res, currRes);
        }
        System.out.println(res);
    }
}


Measured memory_bytes: 40776
#include <iostream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

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

bool alive[1001];
int n,m;

int main(){
	while(cin>>n>>m&&n){
		fill(alive,alive+n+1,1);
		int cur=0,a=n;
		while(a>1){
			rep(i,m){
				cur++;
				if(cur>n)cur=1;
				while(!alive[cur]){
					cur++;
					if(cur>n)cur=1;
				}
			}
			alive[cur]=0;
			a--;
		}
		rep(i,n)if(alive[i+1])cout<<i+1<<endl;
	}
}

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

double const pi = 3.1415926535;
int const mod = 1000000007;
int const inf = 2147483647;

int main() {

	int a, b, k; cin >> a >> b >> k;

	if (a + k - 1 < b - k + 1) {
		for (int i = a; i <= a + k - 1; i++)cout << i << endl;
		for (int i = b - k + 1; i <= b; i++)cout << i << endl;
	}
	else for (int i = a; i <= b; i++)cout << i << endl;

	//system("pause");
	return 0;
}

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

using namespace std;

void debug_out() { cerr << '\n'; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...);}
#define dbg(...) cerr << #__VA_ARGS__ << " ->", debug_out(_VA_ARGS_)
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(int =0;_<n;++)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"

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

const int DMAX = 1e5+10;

inline int two(int n) { return 1 << n; }
inline int test(int n, int pos) { return (bool) (n & two(pos)); }
inline void set_bit(int &n, int b) { n |= two(b); }
inline void unset_bit(int &n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }

vector <int> V[DMAX];

bool uz[10];

int n;

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

    int t,i,j;

    cin>>i>>j;
    uz[i]=true;
    uz[j]=true;
    for(i=1;i<=3;i++)
        if(!uz[i])
            cout<<i<<'\n';
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)

using namespace std;
using ll = long long;

struct HLD {
  struct foo {
    int label;
    int parent;
    int head;
  };
  vector<foo> vals;

  HLD(const vector<vector<int>> &g) : vals(g.size()) {
    const int n = g.size();
    vector<int> size(n, 1);
    auto dfs = [&](auto dfs, int u, int p) -> void {
      for (int v : g[u]) if (v != p) {
        dfs(dfs, v, u);
        size[u] += size[v];
      }
    };
    dfs(dfs, 0, -1);
    int k = 0;
    auto dfs2 = [&](auto dfs, int u, int p, int h) -> void {
      vals[u].label = k++;
      vals[u].head = h;
      vals[u].parent = p;
      pair<int, int> heavy(-1, -1);
      for (int v : g[u]) if (v != p) heavy = max(heavy, {size[v], v});
      if (heavy.first != -1) dfs(dfs, heavy.second, u, h);
      for (int v : g[u]) if (v != p && v != heavy.second) dfs(dfs, v, u, v);
    };
    dfs2(dfs2, 0, -1, 0);
  }

  int lca(int u, int v) {
    for (;;) {
      if (vals[u].label > vals[v].label) swap(u, v);
      if (vals[u].head == vals[v].head) return u;
      v = vals[vals[v].head].parent;
    }
  }
};

#define getchar getchar_unlocked
#define putchar putchar_unlocked

int i32() {
  int n, c;
  while ((c = getchar()) < '0') if (c == EOF) return -1;
  n = c - '0';
  while ((c = getchar()) >= '0') n = n * 10 + c - '0';
  return n;
}

void print(int n) {
  int res[11], i = 0;
  do { res[i++] = n % 10, n /= 10; } while (n);
  while (i) putchar(res[--i] + '0');
  putchar('\n');
}

int main() {
  int n = i32();
  int q = i32();
  vector<vector<int>> g(n);
  struct edge {
    int v, c, w;
  };
  vector<vector<edge>> g2(n);
  rep(i, n-1) {
    int u = i32() - 1;
    int v = i32() - 1;
    int c = i32();
    int w = i32();
    g[u].push_back(v);
    g[v].push_back(u);
    g2[u].push_back((edge){v, c, w});
    g2[v].push_back((edge){u, c, w});
  }
  HLD hld(g);
  vector<ll> ans(q);
  struct query {
    int x, y;
    int coeff;
    int i;
  };
  vector<vector<query>> qs(n);
  rep(i, q) {
    int x = i32();
    int y = i32();
    int u = i32() - 1;
    int v = i32() - 1;
    qs[u].push_back((query){x, y, 1, i});
    qs[v].push_back((query){x, y, 1, i});
    qs[hld.lca(u, v)].push_back((query){x, y, -2, i});
  }
  ll dist = 0;
  vector<ll> distc(n);
  vector<ll> cnt(n);
  auto dfs = [&](auto dfs, int u, int p) -> void {
    for (query q : qs[u]) {
      ans[q.i] += q.coeff * (dist - distc[q.x] + cnt[q.x] * q.y);
    }
    for (edge e : g2[u]) {
      if (e.v == p) continue;
      distc[e.c] += e.w;
      cnt[e.c]++;
      dist += e.w;
      dfs(dfs, e.v, u);
      dist -= e.w;
      cnt[e.c]--;
      distc[e.c] -= e.w;
    }
  };
  dfs(dfs, 0, -1);
  rep(i, q) {
    print(ans[i]);
  }
}


Measured memory_bytes: 55412
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, a, b) for(int i = (a); i >= (b); i--)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define RREP(i, n) for(int i = n; i >= n; i--)

#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))

#define endl "\n"
#define pb push_back
#define rtn return
#define elif else if

#define INF 2000000000	//int型は2 * 10^9ぐらいまで
#define MOD 1000000007
 
const int dx[]={1,0,-1,0}, dy[]={0,-1,0,1};

typedef long long ll;
typedef unsigned long long ull;

template <typename T>
inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template <typename T>
inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template <typename T>
inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template <typename T>
inline T nHr(T a,T b){return nCr(a+b-1,b);}
template <typename T>
inline T POW(T a,T b){int i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}

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

   int n, k, a = 1;
   cin >> n >> k;
   REP(i, n){
      if(a < k) a *= 2;
      else a += k;
   }
   
   cout << a << endl;
   rtn 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
import java.lang.Integer;
import java.lang.StringBuilder;
import java.lang.Math;

class Node {
  Node left;
  Node right;
  int value;

  public Node (int x) {
    this.value = x;
    this.left = null;
    this.right = null;
  }

  public void insert(int x) {
    if (x < this.value) {
      if (left == null) {
        left = new Node(x);
        return;
      } else {
        left.insert(x);
        return;
      }
    } else {
      if (right == null) {
        right = new Node(x);
        return;
      } else {
        right.insert(x);
        return;
      }
    }
  }

  public void printInOrder(){
    if (left != null) {
      left.printInOrder();
    }

    process();

    if (right != null) {
      right.printInOrder();
    }
  }

  public void printPreOrder(){
    process();

    if (left != null) {
      left.printPreOrder();
    }

    if (right != null) {
      right.printPreOrder();
    }
  }


  private void process() {
    System.out.print(" ");
    System.out.print(value);
  }
}

class BinaryTree {
  Node root;

  public BinaryTree() {}

  public void insert(int x) {
    if (root == null) {
      root = new Node(x);
      return;
    }

    if (x < root.value) {
      if (root.left == null) {
        root.left = new Node(x);
        return;
      } else {
        root.left.insert(x);
        return;
      }
    } else {
      if (root.right == null) {
        root.right = new Node(x);
        return;
      } else {
        root.right.insert(x);
        return;
      }
    }
  }

  public void printInOrder() {
    if (root != null) {
      root.printInOrder();
    }
    System.out.println();
  }

  public void printPreOrder() {
    if (root != null) {
      root.printPreOrder();
    }
    System.out.println();
  }

  public void print() {
    printInOrder();
    printPreOrder();
  }
}



public class Main {
  private static int N;
  final static String INSERT = "insert";
  final static String PRINT = "print";

  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int N = in.nextInt();
    BinaryTree tree = new BinaryTree();

    for (int i = 0; i < N; i++) {
      String cmd = in.next();
      switch(cmd) {
        case INSERT:
          tree.insert(in.nextInt());
          break;
        case PRINT:
          tree.print();
          break;
        default:
          System.out.println("Error");
          System.exit(1);
      }
    }
  }
}

Measured memory_bytes: 252660
#include <bits/stdc++.h>
using Int = int64_t;
using UInt = uint64_t;
using C = std::complex<double>;
#define rep(i, n) for(Int i = 0; i < (Int)(n); ++i)
#define guard(x) if( not (x) ) continue;
#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif

int main() {
   Int xss[3][3] = {{}};
   rep(i,3) {
      rep(k,3) {
         std::cin >> xss[i][k];
      }
   }
   bool res = true;
   rep(i,2) {
      rep(k,3) {
         res = res and xss[i+1][k] - xss[i][k] == xss[i+1][0] - xss[i][0];
      }
   }
   rep(i,3) {
      rep(k,2) {
         res = res and xss[i][k+1] - xss[i][k] == xss[0][k+1] - xss[0][k];
      }
   }
   puts(res ? "Yes" : "No");
}



Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#define ll long long
using namespace std;

ll n, s;

ll f(ll b, ll n)
{
  if (n < b)
    return n;
  else
    return n % b + f(b, n / b);
}

ll solve(ll n, ll s)
{
  if (n == s)
    return n + 1;
  if (n < s)
    return -1;

  ll b = 2;
  for (; b * b <= n; b++) {
    if (f(b, n) == s)
      return b;
  }
  for (; b > 0; b--) {
    if ((n - s) % b == 0 && f((n - s) / b + 1, n) == s)
      return (n - s) / b + 1;
  }

  return -1;
}

int main()
{
  cin >> n >> s;
  cout << solve(n, s) << endl;
  return 0;
}

Measured memory_bytes: 888
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int a,b;
    cin>>a>>b;
    if((a>0 && a<10)&&(b>0 && b<10)){
        cout<<a*b<<endl;
    }else{
        cout<<-1<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define _GLIBCXX_DEBUG
const int INF=1e18;

signed main(){
  	string S;cin>>S;
    if(S[0]==S[2])cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
int n;
vector<vector<pair<int, ll>>> ps;
vector<map<int, ll>> memo, memo2;

ll dfs2(int i, int from);
ll dfs(int i, int from) {
  if (memo[i].find(from) != memo[i].end()) {
    return memo[i][from];
  }
  if ((from == -1 && ps[i].size() == 0) || (from != -1 && ps[i].size() == 1)) {
    return memo[i][from] = 0;
  }
  memo[i][from] = 0;
  for (auto &v : ps[i]) {
    if (v.first == from)
      continue;
    ll d = dfs(v.first, i);
    if (d == 0) {
      memo[i][from] += v.second;
    } else {
      memo[i][from] += d + v.second * 3;
    }
  }
  return memo[i][from];
}
ll dfs2(int i, int from) {
  if (memo2[i].find(from) != memo2[i].end()) {
    return memo2[i][from];
  }
  if ((from == -1 && ps[i].size() == 0) || (from != -1 && ps[i].size() == 1)) {
    return memo2[i][from] = 0;
  }
  memo2[i][from] = 0;
  vector<pair<ll, ll>> cs;
  for (auto &v : ps[i]) {
    if (v.first == from)
      continue;
    ll d1 = dfs(v.first, i);
    ll d2 = dfs2(v.first, i);
    if (d1 == 0) {
      memo2[i][from] += v.second;
      cs.push_back(make_pair(v.second, v.second));
    } else {
      memo2[i][from] += d1 + 3 * v.second;
      cs.push_back(make_pair(d1 + 3 * v.second, d2 + 2 * v.second));
    }
  }
  ll diff = 0;
  for (auto &v : cs) {
    diff = max(diff, v.first - v.second);
  }
  memo2[i][from] -= diff;
  return memo2[i][from];
}

int main() {
  while (true) {
    cin >> n;
    if (n == 0) {
      break;
    }
    vector<ll> p(n), d(n);
    ps.clear();
    ps.resize(n);
    for (int i = 1; i < n; i++) {
      cin >> p[i];
      p[i]--;
    }
    for (int i = 1; i < n; i++) {
      cin >> d[i];
    }
    for (int i = 1; i < n; i++) {
      ps[p[i]].push_back(make_pair(i, d[i]));
      ps[i].push_back(make_pair(p[i], d[i]));
    }
    memo.clear();
    memo.resize(n);
    memo2.clear();
    memo2.resize(n);
    ll ans = dfs2(0, -1);
    for (int i = 1; i < n; i++) {
      ans = min(ans, dfs2(i, -1));
    }
    cout << ans << endl;
  }
  return 0;
}



Measured memory_bytes: 3704
#include<stdio.h>
#include<math.h>

double dxy(int);
double dmax(void); 

int i,n=0;
int x[100],y[100]={0};

int main(void){
	
	scanf("%d",&n);
	for(i=0;i<n;i++)scanf("%d",&x[i]);
	for(i=0;i<n;i++)scanf("%d",&y[i]);
	
	printf("%lf\n%lf\n%lf\n%lf\n",dxy(1),dxy(2),dxy(3),dmax());
	
	return 0;
}

double dxy(int p){
	double d=0;
	for(i=0;i<n;i++){
		d=d+pow(fabs(x[i]-y[i]),p);
	}
	d=pow(d,1.0/p);
	
	return d;
}

double dmax(void){
	double max,z=0;
	for(i=0;i<n;i++){
		z=fabs(x[i]-y[i]);
		if(max<z)max=z;
	}
	return max;
}


Measured memory_bytes: 2128
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
 int q,p,w[1000001],u[1000001],o;
 string a;
 int main()
 {
     cin>>a;
     for (int i=0;i<a.size();i++)
     {
         if (a[i]=='C') 
         {
             p++;
             u[p]=i+1;
         }
         else if (a[i]=='F')
         {
            q++;
             w[q]=i+1;
         }
     }
     if (q>=1 && p>=1)
     {
     for (int i=1;i<=p;i++)
     {
         for (int j=1;j<=q;j++)
         {
             if (u[i]<w[j])
             {
                 o=1;
             }
         }
     }
     if (o==1) 
        cout<<"Yes"<<endl;
     else 
        cout<<"No"<<endl;  
     }
     else 
        cout<<"No"<<endl;
    return 0;
 }

Measured memory_bytes: 2304
s = input()
n = len(s)
sum = [0] * (n + 1)
sum[0] = (s[0] == 'B')
for i in range(1 , n):
	sum[i] = sum[i-1] + (s[i] == 'B')
ans = 0
for i in range(n - 1, -1 ,-1):
	if s[i] == 'W':
		ans += sum[i]
print(ans)
	

Measured memory_bytes: 16748
fn main() {
    let mut stdin = String::new();
    std::io::Read::read_to_string(&mut std::io::stdin(), &mut stdin).unwrap();
    let mut stdin = stdin.split_whitespace();
    let mut get = || stdin.next().unwrap();
    macro_rules! get {
        ($t:ty) => {
            get().parse::<$t>().unwrap()
        };
        () => {
            get!(i64)
        };
    }

    let (n, m) = (get!(), get!());
    let mut a = vec![];
    for _ in 0..n {
        a.push(get!());
    }
    let sum = a.iter().sum::<i64>();
    let b = (sum as f64 / (4 * m) as f64).ceil();
    let v = a.into_iter().filter(|&x| x as f64 >= b).collect::<Vec<i64>>();
    if v.len() >= m as usize {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 4352
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int a[5001],n,k;
bool able[5001],tmp[5001];
bool check(int x)
{
	memset(able,0,sizeof(able));
	able[0]=true;
	for (int i=1;i<=n;++i)
		if (i!=x)
		{
			memset(tmp,0,sizeof(tmp));
			for (int j=0;j<k;++j)
				if (able[j]&&j+a[i]<=k)
					tmp[j+a[i]]=true;
			for (int j=0;j<=k;++j)
				if (tmp[j])
					able[j]=true;
		}
	for (int i=max(0,k-a[x]);i<k;++i)
		if (able[i])
			return false;
	return true;
}
int main()
{
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;++i)
		scanf("%d",a+i);
	sort(a+1,a+n+1);
	int l=0,r=n+1;
	while (l+1<r)
	{
		int m=(l+r)/2;
		if (check(m))
			l=m;
		else
			r=m;
	}
	printf("%d",l);
	return 0;
}


Measured memory_bytes: 128
package main

import "fmt"

func main() {
	var N int
	fmt.Scan(&N)

	ret := "No"
	if N%10 == 7 || (N-(N%10))%100 == 70 || int(N/100) == 7 {
		ret = "Yes"
	}

	fmt.Println(ret)
}


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

int main(){
  int a;
  cin >> a;
  double cnt=0;
  for(int i=1;i<=a;i++){
    if(i%2==1){
      cnt++;
    }
  }
  cout << fixed << setprecision(10);
  cout << cnt/a << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<double> head(N+1);
  double p;
  cin >> p;
  head[0] = 1-p;
  head[1] = p;
  for(int i = 1; i < N; ++i){
    cin >> p;
    for(int j = i+1; j >= 0; --j){
      head[j] *= (1-p);
      if(j > 0) head[j] += head[j-1]*p;
    }
  }
  double ret = 0;
  for(int i = (N+1)/2; i <= N; ++i) ret += head[i];
  cout << fixed << setprecision(10) << ret;
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <math.h>
#include <deque>
using ll = long long;
using namespace std;

ll factorial(int n){
    ll ans = 1;
    for (int i = 1; i <= n; i++) {
        ans *= i;
        ans %= 1000000007;
    }
    return ans;
}

int main(){
    int n, m;
    cin >> n >> m;
    if(abs(n-m)>1){
        cout << 0 << endl;
        return 0;
    }
    if(n==m){
        cout << (factorial(n) * factorial(m) * 2) % 1000000007 << endl;
        return 0;
    }
    else{
        cout << factorial(n) * factorial(m) % 1000000007 << endl;
        return 0;
    }
}


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

#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = (n)-1; i >= 0; i--)
#define rep1(i,n) for(int i = 1; i <= (n); i++)
#define rrep1(i,n) for(int i = (n); i > 0; i--)

#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>

#define MOD 1000000007
#define INF 1000000000000000LL

using namespace std;

int main(){
  int n,m;cin>>n>>m;
  vector<int>a(n);
  rep(i, n)cin>>a[i];
  double sum = 0;
  rep(i, n)sum+=a[i];
  int count = 0;
  for(auto p:a){
    double line = sum/(double)(4*m);
    if(p>= line)count++;
//cout<<p<<' '<<line<<' '<<sum/(4*m)<<' '<<count<<endl;
  }

  if(count>=m)cout<<"Yes";
  else cout<<"No";

  return 0;
}


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

int main(){
    string S;  cin >> S;
    string cand[8] = {
        "KIHBR", "AKIHBR", "KIHABR","AKIHABR","KIHBAR","AKIHBAR","KIHABAR","AKIHABAR"
    };
    for(int i=0; i<8; i++){
        if(S==cand[i] || S==cand[i]+"A"){
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
}

Measured memory_bytes: 256
s=list(input())
s.reverse()
judge=True
i=0
while i<=len(s)-5:
	box=[]
	for j in range(5):
		box+=s[i+j]
	if box==["m","a","e","r","d"] or box==["e","s","a","r","e"]:
		i+=5
		#print(box)
	else:
		box+=s[i+5]
		#print(box)
		if box==["r","e","s","a","r","e"]:
			i+=6
		else:
			box+=s[i+6]
			if box==["r","e","m","a","e","r","d"]:
				i+=7
			else:
				judge=False
				break
if judge:
	print("YES")
else:
	print("NO")


Measured memory_bytes: 3956
#include<bits/stdc++.h>
using namespace std;
#define ll long long int

int main(){
    string s;
    cin>>s;
    int ans=0;
    for(int i=1;i<s.length();i++){
        if(s[i-1]==s[i]){
            ans++;
            if(s[i-1]=='1')s[i]='0';
            else if(s[i-1]=='0')s[i]='1';
        }
        //cout<<s<<endl;
    }   
    cout<<ans;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)

long long modinv(long long a, long long m=MOD) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
    /*MODの割り算の際に
    a/＝b;
    を
    a *= modinv(b,MOD);
    とする。
        */
}

int countDigit(int n)
{
  int digit = 1;
  while((n /= 10) != 0)digit++;
  return digit;
}

int swap(int a){
    string S = to_string(a);
    int len = S.length();
    char tmp = S[0];
    S[0] = S[len-1] ;
    S[len-1] = tmp;
    return  stoi(S);
}

int N;
#define MAXN 200000
int data[100] = {0};
int ans  =0;
int first(int a){
    string S = to_string(a);
    return S[0] - '0';
}
int last(int a){
    string S = to_string(a);
    int len = S.length();
    return S[len-1] - '0';
}

void solve(){
    for(int i=1;i<=N;i++){
        int tmp = first(i)*10 + last(i);
        if(i>10 && first(i) == last(i)){
            data[tmp] += 1;
        }else data[tmp] += 1;
        
    }
}

int main(){
    cin >> N;
    solve();
    ans = 0;
    for(int i=1;i<100;i++){
        if(i==swap(i)){
            ans += data[i]*data[i];
        }else ans += data[i]*data[swap(i)];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
def solve():
    N = int(input())
    A = list(map(int,input().split()))
    A.sort(reverse=True)
    
    ans = 0
    for i in range(N-1):
        if i == 0:
            ans += A[0]
        else:
            if i % 2 == 0:
                ans += A[i//2]
            else:
                ans += A[i//2 + 1]
    
    print(ans)

if __name__ == '__main__':
    solve()

Measured memory_bytes: 105092
n=int(input())
page=[]
for i in range(n):
    s,p=input().split()
    page.append((s,i+1,int(p)))
page.sort()
#print(page)
gen=page[0][0]
i=0
while i<n:
    town=[]
    while i!=n:
        #print("i="+str(i))
        if gen!=page[i][0]:
            break
        town.append(page[i])
        i+=1
    for j in range(len(town)):
        town[j]=town[j][::-1]
    town.sort(reverse=True)
    #print(town)
    for j in range(len(town)):
        print(town[j][1])
    
    if i!=n:gen=page[i][0]
    #print(gen)

Measured memory_bytes: 3064
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MOD 1000000007

int n, m;
int p[111111];

int br[4][4] = {1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1};
int tr[4][4] = {1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 2};

struct Matrix{
	int A[4][4];
	void clear(){memset(A, 0, sizeof(A));}
	void init(){for(int i = 0; i < 4; i++) A[i][i] = 1;}
	Matrix operator* (const Matrix a)const{
		static Matrix tmp;
		tmp.clear();
		for(int i = 0; i < 4; i++)
			for(int k = 0; k < 4; k++)
				for(int j = 0; j < 4; j++)
					tmp.A[i][j] = (tmp.A[i][j] + 1ll * A[i][k] * a.A[k][j]) % MOD;
		return tmp;
	}
}ts, tb, Ans;

Matrix Pow(Matrix a, int b){
	static Matrix tm;
	tm.clear(), tm.init();
	for(; b; b >>= 1, a = a * a)
		if(b & 1) tm = tm * a;
	return tm;
}

int main(){
	scanf("%d %d", &n, &m);
	memcpy(ts.A, tr, sizeof(tr));
	memcpy(tb.A, br, sizeof(br));
	for(int i = 1; i <= m; i++) scanf("%d", &p[i]);
	p[++m] = n;
	Ans.A[0][0] = 1;
	int ls = 0;
	
	for(int i = 1; i <= m; i++){
		Ans = Ans * Pow(ts, p[i] - ls);
		if(i != m) Ans = Ans * tb;
		ls = p[i] + 1;
	}
	
	printf("%d\n", Ans.A[0][3]);
	return 0;
}

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

using namespace std;

typedef long long int ll;

ll fib(int x);
ll f[100]={0};

int main(){

	int H,W,K;
	cin>>H>>W>>K;
	
	ll dp[H+1][W+1];
	for(int i=0;i<=H;i++){
		for(int j=0;j<=W;j++){
			dp[i][j] = 0;
		}
	}	
	
	dp[0][1] = 1;

	for(int i=0;i<H;i++){
		for(int j=1;j<=W;j++){
			
			dp[i+1][j] = fib(j)*fib(W-j+1)*dp[i][j];
			dp[i+1][j] += fib(j)*fib(W-j)*dp[i][j+1];			
			dp[i+1][j] += fib(j-1)*fib(W-j+1)*dp[i][j-1];
			dp[i+1][j] = dp[i+1][j]%1000000007;
		}	
	}


	cout << dp[H][K] << endl;

	return 0;

}


ll fib(int x){
	
	if(x == 0){
		return 0;
	}
	else if(x == 1){
		return 1;
	}else if(f[x] != 0){
		return f[x];
	}
	return f[x] = fib(x-1) + fib(x-2);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define all(in) in.begin(), in.end()
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
#define EPS 0.0000000001
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
using ld  = long double;
using pii = pair<int,int>;
using piii = pair<int,pii>;
int W,H;
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
bool valid(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);}
signed main(){
    int N; cin >> N;
    int cnt[10][10] = {};
    int ans = 0;
    for(int i = 0; i <= N; ++i){
        string t =to_string(i);
        cnt[t.front() - '0'][t.back() - '0']++;
    }
    for(int i = 1; i <= N; ++i)
        ans += cnt[to_string(i).back() - '0'][to_string(i).front() - '0'];
    cout << ans << endl;
}


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

using namespace std;

typedef long long int lli;

const int MAX_K = 1e5;
const int MAX_N = 100;

lli mod = 1e9 + 7;

lli dp[MAX_N][MAX_K + 1];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    lli n, k, i, j, ii;
    
    cin >> n >> k;
    
    //lli dp[n][k + 1];
    
    lli a[n];
    
    for(i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    
    for(i = 0; i <= k; ++i)
    {
        if (a[0] >= i)
        {
            dp[0][i] = 1;
        }
        else
        {
            dp[0][i] = 0;
        }
    }
    
    for(i = 1; i < n; ++i)
    {
        dp[i][0] = dp[i - 1][0];
        for(j = 1; j <= k; ++j)
        {
           if (j - a[i] <= 0)
           {
               dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % mod;
           }
           else
           {
               dp[i][j] = ((((dp[i][j - 1] + dp[i - 1][j]) % mod) - dp[i - 1][j - a[i] - 1]) + mod) % mod;
           }
        }
    }
    
    
    cout << dp[n-1][k];
    
    
}

Measured memory_bytes: 78336
from collections import defaultdict
S = input()
n = len(S)
N = defaultdict(int)
x = 0
for i in reversed(range(n)):
    x += int(S[i])*pow(10,(n-i-1),2019)
    x %= 2019
    N[x] += 1
ans = N[0]
for j in N.values():
    ans += j*(j-1)//2
print(ans)

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

int main(){
	int n;
	cin >> n;
	vector<int> a(n+1);
	rep(i,n+1) cin >> a[i];
	vector<int> b(n);
	rep(i,n) cin >> b[i];
	ll ans = 0;
	rep(i,n+1){
		int x = min(a[i],b[i]);
		ans += x;
		b[i] -= x;
		int y = min(a[i+1],b[i]);
		ans += y;
		a[i+1] -= y;
	}
	cout << ans << endl;
}

// cout << fixed << setprecision(15) <<  << endl;

Measured memory_bytes: 3972
#include <iostream>

using namespace std;

int main(){
    int n,k;
    cin >> n >> k;
    int l[50];
    int ans=0;
    for(int j=0;j<n;j++){
        cin >> l[j];
    }
    for(int i=0;i<k;i++){
        int mlong=0;
        int id=0;
        for(int j=0;j<n;j++){
            if (l[j]==0){
                continue;
            }
            if (mlong<l[j]){
                mlong=max(mlong,l[j]);
                id=j;
            }
        }
        ans+=mlong;
        l[id]=0;
    }



    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <stack>
#include <istream>
#include <map>
#include <set>
#include <queue>
#define rep0(i,n) for (int i = 0; i <= (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)
#define REP(i,a,b) for (int i = a; i <= (b); ++i) 
#define MOD 10e9 + 7
#define INF 2147483646
#define INFLL 9223372036854775807
typedef long long ll;
using namespace std;
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	/*
		　　　  　 ,ﾍ／L──- 、
		　　　   　Lﾆ)r_」=＝= ｲ
		　　 　,ﾍ、i ﾉノλﾉﾊﾉﾍ
		　　   ,'　｀(ﾊﾘ ﾟ ヮﾟﾉi)　',
		　　 .i　　 >〈(つ,i!と)　　i
		　　  vﾍγk´_/___i,ゝﾍノ
		　　　　　 ｀ﾞr_,ｨ_ｧﾞ´
	*/
	int x = 0;
	int nowmax = 0;
	int n;
	cin >> n;
	string s;
	cin >> s;
	rep0(i, n - 1) {
		if (s[i] == 'I')x++;
		else x--;
		nowmax = max(x, nowmax);
	}
	cout << nowmax << endl;
	return 0;
}


Measured memory_bytes: 896
use std::io::Read;
use std::cmp::min;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let n: usize = iterator.next().unwrap().parse().unwrap();

    if n % 2 != 0 {
        return "0".to_string();
    }

    let ans = min(g2(n), g5(n));
    return ans.to_string();
}

fn g2(n: usize) -> usize {
    return g(n / 2, 2) + n / 2;
}

fn g5(n: usize) -> usize {
    return g(n / 2, 5);
}

fn g(n: usize, p: usize) -> usize {
    if n == 0 {
        return 0;
    }
    return n / p + g(n / p, p);
}


Measured memory_bytes: 4352