akhauriyash/Code-Regression huggingface dataset:
// AOJ 2804 Minimum Enclosing Rectangle
// 2018.5.5 bal4u

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

typedef struct { int x, y; } PP;

#define INF 1e18

#define MAX_N 100002
int xpos[MAX_N], ypos[MAX_N];
PP  pi[MAX_N<<2], po[MAX_N<<2]; int sz;

int cmp(PP *a, PP *b) {
	if (a->y - b->y) return a->y - b->y;
	return a->x - b->x;
}

PP vsub(PP p1, PP p2) { PP r; r.x = p1.x - p2.x, r.y = p1.y - p2.y; return r; }
long long cross(PP a, PP b) { return (long long)a.x * b.y - (long long)a.y * b.x; }
int convex_hull(int n, PP *ps, PP *po)
{
	int i, k, j = 0;

	qsort(ps, n, sizeof(PP), cmp);
	for (i = 0; i < n; i++) {
		while (j > 1 && cross(vsub(po[j-1], po[j-2]), vsub(ps[i], po[j-1])) <= 0) j--;
		po[j++] = ps[i];
	}
	k = j;
	for (i = n - 2; i >= 0; i--) {
		while (j > k && cross(vsub(po[j-1], po[j-2]), vsub(ps[i], po[j-1])) <= 0) j--;
		po[j++] = ps[i];
	}
	return j-1;
}

#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif
int in()
{
	int n = 0, c = gc();
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

void xypos(int id, int x, int y)
{
	xpos[id] = x, ypos[id] = y;
	pi[sz].x = x  , pi[sz].y = y,   sz++;
	pi[sz].x = x+1, pi[sz].y = y,   sz++;
	pi[sz].x = x,   pi[sz].y = y+1, sz++;
	pi[sz].x = x+1, pi[sz].y = y+1, sz++;
}

int main()
{
	int N, n, i, j, d, x, y;
	double delta, ans;
	double t, fx, fy, xmin, xmax, ymin, ymax, cosv, sinv;

	sz = 0;
	xypos(0, 0, 0);
	N = in();
	for (i = 1; i < N; i++) {
		n = in(), d = gc() & 0xf, gc();
		x = xpos[n], y = ypos[n];
		if      (d == 0) xypos(i, x-1, y);	// 左
		else if (d == 1) xypos(i, x, y+1);  // 下
		else if (d == 2) xypos(i, x+1, y);  // 右
		else             xypos(i, x, y-1);  // 上
	}

	n = convex_hull(sz, pi, po);
	po[n] = po[0];

	ans = INF;
	for (i = 0; i < n; i++) {
		delta = -atan2(po[i+1].y-po[i].y, po[i+1].x-po[i].x);
		cosv = cos(delta), sinv = sin(delta);
		x = po[i].x, y = po[i].y;
		xmin = ymin = INF, xmax = ymax = -INF;
		for (j = 0; j < n; j++) {
			fx = (po[j].x-x) * cosv - (po[j].y-y) * sinv;
			fy = (po[j].x-x) * sinv + (po[j].y-y) * cosv;
			if (fx < xmin) xmin = fx;
			if (fx > xmax) xmax = fx;
			if (fy < ymin) ymin = fy;
			if (fy > ymax) ymax = fy;
		}
		t = (xmax-xmin)*(ymax-ymin);
		if (t < ans) ans = t;
	}
	printf("%.10lf\n", ans);
	return 0;
}



Measured memory_bytes: 8540
import Data.Bits

type Mask = Int
type Pair = (Int, Mask)

base :: [Int]
base = [3, 5, 7]

mask :: [Mask]
mask = [1, 2, 4]

seed :: [Pair]
seed = zip base mask

conv :: Pair -> Pair -> Pair
conv (i, s) (j, t) = (i * 10 + j, s .|. t)

gen :: [Pair]
gen = seed ++ [conv pre post | pre <- gen, post <- seed]

ans :: [Int]
ans = [i | (i, s) <- gen, s == 7]

main :: IO ()
main = do
    n <- readLn
    print $ length $ takeWhile (<= n) ans


Measured memory_bytes: 3324
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, n) for (int i = 1; i <= (int)(n); i++)
using ll = long long;
 
/*
 string -> int : stoi(S);
 int -> string : to_string(N);
 Sのn文字以降をm文字取り出す : S.substr(n,m)
cout << fixed << setprecision(2) << 3.14 << endl; //3.1
 
 int: -2,147,483,648 ～ 2,147,483,647 (2×10^9)
 ll: -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 (9×10^18)
 
*/
 
int main() {
 
  double n, count=0, ans=0;
  string s;
 
  cin >> n;
  double pai = 3.1415926535;
  ans=2*n*pai;
 
 
  cout << fixed << setprecision(10) << ans << endl;
}

Measured memory_bytes: 3828
#include <stdio.h>
#pragma warning (disable:4996)

//prototype
int counter(int);

int main() {
	//input
	int N;
	(void)scanf("%d", &N);

	//output
	for (int i = 1; i <= N; i++) {
		printf("%d\n", counter(i));
	}
}

int counter(int i) {
	int count = 0;
	for (int x = 1; x * (x + 2) <= (i - 3); x++) {
		for (int y = 1; y * (x + y + 1) <= i - ((x * x) + x + 1); y++) {
			for (int z = 1; ((x * x) + (y * y) + (z * z) + (x * y) + (y * z) + (z * x)) <= i; z++) {
				if (((x * x) + (y * y) + (z * z) + (x * y) + (y * z) + (z * x)) == i)count++;
			}
		}
	}
	return count;
}

Measured memory_bytes: 1720
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
#define int long long

signed main() {
  string s, t;
  cin >> s >> t;
  if (s == t) {
    cout << "Yes" << endl;
    return 0;
  }
  for (int i = 1; i < s.size(); i++) {
    string a = s.substr(0, i);
    string b = s.substr(i);
    if (t == (b + a)) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string S;
  cin >> S;
  int N = S.size()-1;
  int64_t sum = 0;
  for(int bit = 0; bit < (1 << N); bit++){
    vector<int> X(0);
    for(int i=0; i<N; i++){
      if(bit & (1 << i)){
        X.push_back(i);
      }
    }
    X.push_back(N);
    int j = 0;
    for(int i=0; i<X.size(); i++){
      while(j <= X.at(i)){
        int num = S.at(j) - '0';
        int pow_x = X.at(i) - j;
        sum += num *pow(10,pow_x);
        j++;
      }
    }
  }
  cout << sum << endl;
}    

Measured memory_bytes: 512
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define _USE_MATH_DEFINES
#include <math.h>
#define rep(i,n) for(int i = 0;i < n;i++)
#define NIL = -1;

ll gcd(long long a,long long b) {
    if (a < b) swap(a,b);
    if (b == 0) return a;
    
    return gcd(b,a%b);
}

ll lcm(ll a,ll b){
    a / gcd(a,b) * b;
}
const ll mod = 1e9 + 7;

int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

const ll INF = 1e9;
/////////////////////////////////////////////////////////////////////////////////////////
int dp[1000010];
int odd_dp[1000010];

int main(){
    int n,table[183];

    for (int i = 0;i < 183;i++) table[i] = i*(i+1)*(i+2)/6;

    vector<int> num(1000010);
    int cnt = 0,a;
    while(true){
        cin >> a;
        num[cnt] = a;
        cnt++;
        if (a == 0) break;
    }

    for (int i = 0;i < 1000010;i++){
        dp[i] = 20000000;
        odd_dp[i] = 20000000;
    }

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

    odd_dp[0] = 0;
    odd_dp[1] = 1;

    for (int i = 2;i < 1000000;i++){
        for (int k = 1;table[k] <= i;k++){
            dp[i] = min(dp[i],dp[i-table[k]] + 1);
            if (table[k] % 2 != 0){
                odd_dp[i] = min(odd_dp[i],odd_dp[i-table[k]] + 1);
            }
        }
    }

    for (int i = 0;i < cnt - 1;i++){
        cout << dp[num[i]] << " " << odd_dp[num[i]] << endl;
    }
}


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

using namespace std;

double my_abs(double x) {
  if (x >= 0) {
    return x;
  } else {
    return (-1)*x;
  }
}

int main() {
  int n;
  int i;
  long long a[100010];
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%lld", &a[i]);
  }
  sort(a, a+n);
  long long largest = a[n-1];
  double half = (a[n-1]*1.0) / 2;
  long long ans = a[0];
  for (i = 0; i < n; i++) {
    if (my_abs(half-a[i]) < my_abs(half-ans)) {
      ans = a[i];
    }
  }
  printf("%lld %lld", largest, ans); 
  return 0;
}
  
    

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1000000007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;

ld calc(ld a, ld b, ld theta){
    if(theta>PI/2.0-EPS) return 0.0;
    ld res=0.0;
    if(a*tan(theta)<=b){
        res = a*a*b-a*a*a*tan(theta)/2.0;
    }else{
        res = b*b/tan(theta)*a/2.0;
    }
    return res;
}


int main(void){
    ld a, b, x; cin >> a >> b >> x;

    ld lb=0.0, ub = PI/2.0;
    
    for(int i=0; i<=10000; i++){
        ld mid = (lb+ub)/2.0;
        if(calc(a, b, mid)<x) ub = mid;
        else lb = mid;
    }


    cout << fixed << setprecision(15) << ub/PI * 180 << endl;
}

Measured memory_bytes: 384
#include <stdio.h>
#include <set>
#include <algorithm>
using namespace std;
long long a[51];
int main()
{
	int n;
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
		scanf("%lld",a+i);
	sort(a+1,a+n+1);
	long long ans=0;
	while (a[n]>=n)
	{
		for (int i=n;i>=1;--i)
			if (a[i]>=n)
			{
				long long dec=(a[i]-n)/n+1;
				a[i]-=dec*n;
				for (int j=1;j<=n;++j)
					if (j!=i)
						a[j]+=dec;
				ans+=dec;
			}
		sort(a+1,a+n+1);
	}
	printf("%lld",ans);
	return 0;
}


Measured memory_bytes: 128
def max_grade(s):
    sum_grades = sum(s)
    if sum_grades % 10 == 0:
        aux = sorted(filter(lambda x: x % 10 != 0, s))
        if aux:
            return sum_grades - aux[0]
        else:
            return 0
    else:
        return sum_grades
    

if __name__ == '__main__':
    n = int(input())
    s = [int(input()) for _ in range(n)]
    print(max_grade(s))

Measured memory_bytes: 3064
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        long k = sc.nextLong();

        long ansA, ansB;
        if (a - k >= 0) {
            ansA = a - k;
        } else {
            ansA = 0;
        }
        k -= a;

        if (k > 0) {
            if (b - k >= 0) {
                ansB = b - k;
            } else {
                ansB = 0;
            }
        } else {
            ansB = b;
        }

        System.out.println(ansA + " " + ansB);
    }
}

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

const int MOD=1e9+7;

int main(){
  int n;
  cin>>n;
  vector<int> a(n);
  rep(i,n) cin>>a[i];
  vector<int> cnt(n,3);
  vector<int> used(n,0);
  ll ans=1;
  rep(i,n){
    if(a[i]==0) ans*=cnt[a[i]];
    else {ans*=used[a[i]-1];used[a[i]-1]--;}
    ans%=MOD;
    used[a[i]]++;
    cnt[a[i]]--;
  }
  cout<<ans<<endl;
}

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

#define f(i,x,y)			for(int i=x; i<y; i++)
#define ll 					long long 
#define mp 					make_pair
#define F 					first
#define S 					second
#define N 					100005
#define inf 				1e9+1

int main()
{
	
	string s,t;
	cin>>s;
	cin>>t;
	int m = s.size();
	int n = t.size();

	int dp[m+1][n+1];
	//memset(dp,0,sizeof(dp));

	f(i,0,m+1)
		f(j,0,n+1)
		{
			if(i==0 || j==0)
				dp[i][j] = 0;
			else if(s[i-1]==t[j-1])
				dp[i][j] = 1+dp[i-1][j-1];
			else
				dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
		}	
	

	int i=m,j=n;
	vector<char> ans(dp[m][n]);
	int in = 0;

	while(in<dp[m][n])
	{
		if(s[i-1]==t[j-1])
		{
			ans[in++] = s[i-1];
			i--; j--;
		}
		else if(dp[i-1][j] >= dp[i][j-1])
			i--;
		else
			j--;
	}
	reverse(ans.begin(),ans.end());

string r = "";
	f(x,0,ans.size())
		r+=ans[x];

cout<<r;
	return 0;
}

Measured memory_bytes: 35456
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
ll now,n,k,bit[55],res;
int main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=0;i<n;++i)
	{
	 ll tmp;
	 scanf("%lld",&tmp);
	 int t=0;
	 while(tmp)
	 {
	 	if(tmp&1)bit[t]++; 
	 	t++,tmp>>=1;
	 }
    }
    for(int i=50;i>=0;--i)
    {
    	if(now+(1ll<<i)>k)continue;
    	if(bit[i]>n/2)continue;
    	now+=(1ll<<i);
    	bit[i]=n-bit[i];
    }
    for(int i=50;i>=0;--i)res+=bit[i]*(1ll<<i);
    printf("%lld\n",res);
	return 0;
} 

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class Program
{
    static void Main()
    {
        var mb = new ModBinom(2000);
        var NK = ReadLine().Split().Select(int.Parse).ToArray();
        var N = NK[0];
        var K = NK[1];
        SetOut(new System.IO.StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        for (int i = 1; i <= K; i++)
        {
            WriteLine((mb.Binom(K - 1, i - 1) * mb.Binom(N - K + 1, i) % ((long)1e9 + 7)).ToString());
        }
        Out.Flush();
    }
}

class ModBinom
{
    long[] fac;
    long[] finv;
    int mod;

    public ModBinom(int N, int p = (int)1e9 + 7)//N < p  O(N)
    {
        N++;

        fac = new long[N];
        long[] inv = new long[N];
        finv = new long[N];

        fac[0] = fac[1] = 1;
        inv[1] = 1;
        finv[0] = finv[1] = 1;

        for (int i = 2; i < fac.Length; i++)
        {
            fac[i] = fac[i - 1] * i % p;
            inv[i] = p - inv[p % i] * (p / i) % p;
            finv[i] = finv[i - 1] * inv[i] % p;
        }

        mod = p;
    }

    [System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
    public long Binom(int n, int k)// O(1)
    {
        if (n < k) return 0;
        if (n < 0 || k < 0) return 0;
        return fac[n] * finv[k] % mod * finv[n - k] % mod;
    }
}


Measured memory_bytes: 13340
import math

a, b, h, m = map(int, input().split())

rad = math.pi * 2 * (h/12.0 + (m/60.0) / 12.0 - m/60.0)

ans = math.sqrt(a**2 + b**2 - 2*a*b*math.cos(rad))

print(ans)


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

const int INF=1e9+7;
int main(){
    int a,b,m;
    cin>>a>>b>>m;
    vector<int> ref;
    vector<int> rag;

    int min_ref=INF;
    int min_rag=INF;
    rep(i,a){
        int tmp;
        cin>>tmp;
        ref.push_back(tmp);
        min_ref=min(min_ref,tmp);
    }
    rep(i,b){
        int tmp;
        cin>>tmp;
        rag.push_back(tmp);
        min_rag = min(min_rag,tmp);
    }
    int ans=INF;
    rep(i,m){
        int x,y,c;
        cin>>x>>y>>c;
        ans = min(ans,ref[x-1]+rag[y-1]-c);
    }
    cout<<min(ans,min_ref+min_rag)<<endl;
    return 0;
}

Measured memory_bytes: 1400
import numpy as np
import sys


def main():
    input = sys.stdin.readline
    n, W = map(int, input().split())
    w, v = [0] * n, [0] * n
    for i in range(n):
        w[i], v[i] = map(int, input().split())
    ndp = np.zeros(W + 1, dtype=np.int64)
    for w, v in zip(w, v):
        np.maximum(ndp[:-w] + v, ndp[w:], out=ndp[w:])
    print(ndp[-1])


if __name__ == "__main__":
    main()

Measured memory_bytes: 20492
#include <bits/stdc++.h>
using namespace std;
int main() {
    long long n;
    cin >> n;
    long long h[n], s[n];
    for (long long i = 0; i < n; i++) cin >> h[i];
    s[0] = 0;
    for (long long i = 1; i < n; i++)
    {
        if (i == 1) s[1] = s[0] + abs(h[1] - h[0]);
        else
            s[i] = min(s[i - 1] + abs(h[i] - h[i - 1]), s[i - 2] + abs(h[i] - h[i - 2]));
    }
    cout << s[n - 1];
}

Measured memory_bytes: 5188
#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--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;


int main(){
    ll n, a, b;
    cin >> n >> a >> b;
    if ((b-a)%2==0) cout << (b-a)/2 << endl;
    else cout << min((b+a-1)/2, (2*n-b-a+1)/2) << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void) {
    vector<int> set;
    int n,a,q,k;
    cin >> n;
    for (int i=0;i<n;i++) {
        cin >> a;
        set.emplace_back(a);
    }
    auto begin = set.begin();
    auto end = set.end();
    cin >> q;
    for (int j=0;j<q;j++) {
        cin >> k;
        auto itr = lower_bound(begin,end,k);
        cout << itr-begin << endl;
    }
}



Measured memory_bytes: 3460
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int main()
{
    int n, r;
    cin >> n >> r;

    int ans;
    if (n >= 10) ans = r;
    else{
        ans = r + 100 * (10 - n);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main {
    public static void main(String[] args) {
      
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int T = sc.nextInt();
        int min = 1001;
      
      for(int i=0;i<N;i++){
        int c = sc.nextInt();  int t = sc.nextInt();
        if(t<=T){min = Math.min(c,min);}
      }
      System.out.println(min<1001?min:"TLE");
    }
}

Measured memory_bytes: 23764
from fractions import gcd

N = int(input())
a = list(map(int, input().split()))

g1 = [0]*N
g2 = [0]*N

g1[0] = a[0]
g2[N-1] = a[N-1]

for i in range(1, N):
    g1[i] = gcd(a[i-1], g1[i-1])
    g2[N-1-i] = gcd(a[N-i], g2[N-i])
    
g1[0] = g2[0]
g2[N-1] = g1[N-1]

g = [gcd(g1[i], g2[i]) for i in range(N)]
print(max(g))
    

Measured memory_bytes: 16160
#include<iostream>
    #include<map>
    #include<deque>
    #include<algorithm>
    #include<string>
    #include<cctype>
    using namespace std;
    #define REP(i,b,e) for(int i=(int)b;i<(int)e;i++)
    #define Rep(i,n) REP(i,0,n)
    typedef long long ll;
     
     
    string s,ans;
     
    int main(){
        cin>>s;
     
        Rep(i,s.size()){
            if(s[i]!='B'){
                ans+=s[i];
            }
            else{
                if(ans.size()){
                    ans.pop_back();
                }
            }
        }
        cout<<ans<<endl;
        return 0;
    }

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

using namespace std;

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

const double pi = 3.14159265358979323846;

// #define fio() cin.tie(0); ios::sync_with_stdio(false);
// 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 (a>b) { a = b; return 1; } return 0; }
#define MOD 1000000007LL
#define PS(p) cout << setprecision(15) << fixed << p << endl;
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
#define ALL(c) c.begin(), c.end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define TG0 get< 0 >
#define TG1 get< 1 >
#define TG2 get< 2 >
#define F first
#define S second
#define VL vector< ll >

// to_string(123)
// atoi("123"); atoi(s.c_str());
// "abc".size()
// s.find('+') == string::npos
// 1e18

ll A[3][3];

bool B[100];

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

  for (ll i = 0; i < 3; i++) {
    for (ll j = 0; j < 3; j++) {
      cin >> A[i][j];
    }
  }

  ll N;
  cin >> N;

  ll b;
  for (ll i = 0; i < N; i++) {
    cin >> b;

    B[b] = true;
  }

  bool bingo = true;

  for (ll i = 0; i < 3; i++) {
    bingo = true;

    for (ll j = 0; j < 3; j++) {
      b = A[j][i];
      if (!B[b]) {
        bingo = false;
        break;
      }
    }

    if (bingo) {
      cout << "Yes" << endl;
      return 0;
    }
  }

  // yoko ok
  for (ll i = 0; i < 3; i++) {
    bingo = true;

    for (ll j = 0; j < 3; j++) {
      b = A[i][j];
      if (!B[b]) {
        bingo = false;
        break;
      }
    }

    if (bingo) {
      cout << "Yes" << endl;
      return 0;
    }
  }

  if (B[A[0][0]] &&
      B[A[1][1]] &&
      B[A[2][2]]) {
    cout << "Yes" << endl;
    return 0;
  }

  if (B[A[0][2]] &&
      B[A[1][1]] &&
      B[A[2][0]]) {
    cout << "Yes" << endl;
    return 0;
  }

  cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <set>
using namespace std;
int main()
{
    int N, ans = 0;
    cin >> N;
    set<int> s;

    while (N--)
    {
        int t;
        cin >> t;
        if (s.find(t) != s.end())
            s.erase(s.find(t));
        else
            s.insert(t);
    }
    cout << s.size();
    return 0;
}

Measured memory_bytes: 4864
#include <iostream>
#include "algorithm"
#include "queue"
using namespace std;
static const int mx=10007;
static const int inf=(1<<21);

int n;
vector<pair<int, int> >adj[mx];//加权有向图的邻接表表示法

void dijkstra()
{
	priority_queue<pair<int,int> >pq;
	int d[mx],color[mx];
	
	for (int i=0;i<n;i++) {
		d[i]=inf;
		color[i]=0;
	}
	
	d[0]=0;
	color[0]=1;
	pq.push(make_pair(0,0));
	while (!pq.empty()) {
		pair<int , int>f=pq.top();pq.pop();
		int u=f.second;
		
		color[u]=2;
		
		//取出最小值，如果不是最短路径则忽略。	
		if(d[u]<f.first*(-1))continue;
		
		for(int j=0;j<adj[u].size();j++)
		{
			int v=adj[u][j].first;
			if(color[v]==2)continue;
			if(d[v]>d[u]+adj[u][j].second)
			{
				d[v]=d[u]+adj[u][j].second;
				///priority_queue默认优先较大值，因此要乘以-1；
				pq.push(make_pair(d[v]*(-1), v));
				color[v]=1;
			}
		}
	}
		for (int i=0;i<n;i++) 
			cout<<i<<" "<<(d[i]==inf?-1:d[i])<<endl;
}
int main(int argc, char *argv[]) {
	
	int k,c,u,v;
	cin>>n;
	for (int i=0;i<n;i++) {
		cin>>u>>k;
		for (int j=0;j<k;j++) {
			cin>>v>>c;
			adj[u].push_back(make_pair(v, c));
		}
	}
		
	dijkstra();
	
	return 0;
}


Measured memory_bytes: 8112
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define ALL(c) (c).begin(), (c).end()
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    string s;
    cin >> n >> s;
    int cnt = 0;
    rep(i,n-2)
    {
        if (s[i]=='A' && s[i+1]=='B' && s[i+2]=='C') cnt++;
    }
    cout << cnt << endl;
    
    
}




Measured memory_bytes: 256
typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}



int main() {
    ll r;
    std::cin >> r;
    std::cout << 3*r*r << std::endl;
}




Measured memory_bytes: 764
/*
 * Given an H*W-sized, 0/1-valued matrix, find the area of the largest
 * rectangle containing only 0s.
 *
 * 1 <= H, W <= 1400
 */

#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int m[1400][1400];

int main() {
  int h, w;
  cin >> h >> w;
  int A{0};
  for (int i = 0; i < h; ++i)
    for (int j = 0; j < w; ++j)
      cin >> m[i][j];
  vector<int> d(w, -1), l(w), r(w);
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j)
      if (m[i][j])
        d[j] = i;
    stack<int> st;
    for (int j = 0; j < w; ++j) {
      while (!st.empty() && d[st.top()] <= d[j])
        st.pop();
      l[j] = st.empty() ? -1 : st.top();
      st.push(j);
    }
    while (!st.empty())
      st.pop();
    for (int j = w - 1; j >= 0; --j) {
      while (!st.empty() && d[st.top()] <= d[j])
        st.pop();
      r[j] = st.empty() ? w : st.top();
      st.push(j);
    }
    for (int j = 0; j < w; ++j) {
      int least = min(i - d[j], (r[j] - l[j] - 1));
      A = max(A, least * least);
    }
  }
  cout << A << endl;
}


Measured memory_bytes: 10728
import java.util.*;
import java.util.function.Consumer;
import java.util.stream.Collectors;

public class Main {
    private static final Scanner scanner = new Scanner(System.in);
    private static final Consumer<List<String>> consumer = solve();

    public static void main(String[] args) {
        consumer.accept(readInput());
    }

    private static List<String> readInput() {
        final List<String> lineList = new ArrayList<>();
        while (scanner.hasNextLine()) {
            lineList.add(scanner.nextLine());
        }
        return lineList;
    }

    private static Consumer<List<String>> solve() {
        return args -> {
            int N = Integer.valueOf(args.get(0).split(" ")[0]);
            if (N == 1) {
                System.out.println(1);
                return;
            }

            List<List<Long>> xyList = args.stream().skip(1)
                    .map(x -> Arrays.stream(x.split(" "))
                            .map(Long::valueOf)
                            .collect(Collectors.toList()))
                    .collect(Collectors.toList());

            Map<String, Integer> keyToCnt = new HashMap<>();
            for (int i = 0; i < xyList.size(); i++) {
                for (int j = 0; j < xyList.size(); j++) {
                    if (i == j) continue;
                    Long xd = xyList.get(i).get(0) - xyList.get(j).get(0);
                    Long yd = xyList.get(i).get(1) - xyList.get(j).get(1);
                    String key = String.format("%d:%d", xd, yd);
                    keyToCnt.put(key, keyToCnt.getOrDefault(key, 0) + 1);
                }
            }

            int max = keyToCnt.values().stream().mapToInt(Integer::intValue).max().getAsInt();
            System.out.println(N - max);
        };
    }

}


Measured memory_bytes: 31500
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MN = 5555;
const ll MOD = 1e9+7;
ll dp1[MN];
ll dp2[MN];
ll pw(ll a, ll e) {
    ll res = 1;
    for(; e; e/=2) {
        if(e&1) res *= a, res %= MOD;
        a *= a, a %= MOD;
    }
    return res;
}
int main() {
    int n;
    cin>>n;
    string s;
    cin>>s;
    dp1[0] = 1;
    for(int i = 0; i < n; ++i) {
        dp2[0] += dp1[0];
        dp2[1] += dp1[0]*2;
        for(int j = 1; j < n; ++j) {
            dp2[j-1] += dp1[j];
            dp2[j+1] += dp1[j]*2;
        }
        for(int j = 0; j <= n; ++j) {
            dp1[j] = dp2[j]%MOD;
            dp2[j] = 0;
        }
    }
    ll ans = dp1[s.size()];
    for(int i = 0; i < s.size(); ++i) {
        ans = ans * pw(2, MOD-2) % MOD;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 384
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(void)
{
  int h,w,k;
  char c[7];
  int table[6][6]={{0}};
  int a[6]={0};
  int b[6]={0};
  int num;
  int ans=0;
  int i,j;
  scanf("%d %d %d",&h,&w,&k);
  for(i=0;i<h;i++)
  {
    scanf("%s",c);
    for(j=0;j<w;j++)
    {
      if(c[j]=='#')
      {
        table[i][j]=1;
      }
    }
  }

  for(a[0]=0;a[0]<=1;a[0]++){
  for(a[1]=0;a[1]<=1;a[1]++){
  for(a[2]=0;a[2]<=1;a[2]++){
  for(a[3]=0;a[3]<=1;a[3]++){
  for(a[4]=0;a[4]<=1;a[4]++){
  for(a[5]=0;a[5]<=1;a[5]++){
    for(b[0]=0;b[0]<=1;b[0]++){
    for(b[1]=0;b[1]<=1;b[1]++){
    for(b[2]=0;b[2]<=1;b[2]++){
    for(b[3]=0;b[3]<=1;b[3]++){
    for(b[4]=0;b[4]<=1;b[4]++){
    for(b[5]=0;b[5]<=1;b[5]++){
      num=0;
      for(i=0;i<h;i++)
      {
        for(j=0;j<w;j++)
        {
          if(a[i]==1 && b[j]==1 && table[i][j]==1) num++;
        }
      }
      if(num==k) ans++;
    }}}}}}
  }}}}}}

  ans /= pow(2,12-h-w);

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

  return 0;
}

Measured memory_bytes: 2552
#include <iostream>
#include <vector>

using namespace std;

int main()
{
  int n, m;
  cin >> n >> m;
  
  vector<bool> from1(n + 1, false);
  vector<bool> ton(n + 1, false);

  for (int i = 0; i < m; i++)
  {
	int from, to;
	cin >> from >> to;
	if (from > to) swap(from, to);
	if (from == 1) from1[to] = true;
	if (to == n) ton[from] = true;
  }

  for (int i = 1; i <= n; i++)
  {
	if (from1[i] && ton[i])
	{
	  cout << "POSSIBLE" << endl;
	  return 0;
	}
  }
  cout << "IMPOSSIBLE" << endl;
  return 0;
}


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

int main(){
        int n, m;
        scanf("%d %d", &n, &m);
        int a[n+1];
        memset(a, 0, sizeof(a));
        for(int i=0; i<m; i++){
                int l, r;
                scanf("%d %d", &l, &r);
                a[l-1]++;
                a[r]--;
        }
        for(int i=0; i<n; i++) a[i+1] += a[i];

        int ans = 0;
        for(int i=0; i<=n; i++) ans += (a[i]==m);
        printf("%d\n", ans);
        return 0;
}

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

int main() {
  int N, M, P;

  while (cin >> N >> M >> P, N != 0) {
    int num = 0;
    int sum = 0;
    for (int i = 0; i < N; i++) {
      int X;
      cin >> X;

      if (i == M - 1) {
        num = X;
      }

      sum += X;
    }

    cout << (num != 0 ? sum * (100 - P) / num : 0) << endl;
  }

  return 0;
}

Measured memory_bytes: 3072
#include "bits/stdc++.h"
using namespace std;

int main() {
    string s;
    cin >> s;
    int ans = 0;
    stack<char>st;
    if(s.size() == 1){cout << 0;return 0;}
    st.push(s[0]);
    for(int i = 1;i < s.size();i++){
      if(st.size() == 0){st.push(s[i]);continue;}
      if(st.top() == '0' && s[i] == '1' || st.top() == '1' && s[i] == '0'){st.pop();ans+=2;}
      else st.push(s[i]);
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<string.h>
#include<vector>
#include<list>
#include<stdio.h>
#include<math.h>
#include<iomanip>
#include<map>
#include<stack>
#include<queue>
#include<algorithm>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define debug(x) cout << "debug " << x << endl;
using namespace std;

struct data{
    int num;
    int p;
    int q;
    int r;
    int kcal;
};

int main(){
    int n;
    struct data data[10005];
    while(cin >> n, n){
        bool c = true;
        rep(i,n){
            cin >> data[i].num >> data[i].p >> data[i].q >> data[i].r;
            data[i].kcal = (data[i].p + data[i].r) * 4 + data[i].q * 9;
        }
        cin >> data[n].p >> data[n].q >> data[n].r >> data[n].kcal;
        rep(i,n){
            if(data[i].p <= data[n].p && data[i].q <= data[n].q && data[i].r <= data[n].r && data[i].kcal <= data[n].kcal){
                cout << data[i].num << endl;
                c = false;
            }
        }
        if(c){
            cout << "NA" << endl;
        }
    }
}

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

typedef vector<int> vi;  
typedef pair<int,int> ii;  
typedef vector<ii> vii;  
typedef list<int> li;  
typedef unordered_map<int,int> mii;

#define ll long long
#define rep(i,n) for (int i = 0; i < (n); i++)  
#define rrep(i,n) for (int i = (n)-1; i >= 0; i--)
#define rap(i,a,n) for (int i = a; i < (n); i++) 
#define rrap(i,n,a) for (int i = (n)-1; i >= a; i--) 

vi v;
int main() {
    ios_base::sync_with_stdio(false);
    string s;
    ll su=0;
    cin >> s;
    int first=0,co=0,second=0,so=0;
    if (s[0] == '<') {
        second = 0;
        v.push_back(0);
        co=1;
    }
    else {
        first=0;
        co=-1;
    }
    rap(i,1,(int)s.size()) {
        if (s[i]=='<' && s[i-1]=='<') {
            v.push_back(co);
            co++;
        }
        else if (s[i]=='<' && s[i-1]=='>') {
            second = i;
            v.push_back(max((-1)*co,so));
            co++;
            for (int j=first+1;j<i;j++) {
                v.push_back((-1)*co);
                co++;
            }
            v.push_back(0);
            co = 1;
        }
        else if (s[i]=='>' && s[i-1]=='>') {
            co--;
        }
        else {
            so = co;
            co = -1;
            first = i;
        }
    }
    if ((int)v.size() < (int)s.size()+1) {
            if (s[(int)s.size()-1]=='<') {
                for (int j=second;j<(int)s.size()+1;j++) {
                    v.push_back(co);
                    co--;
                }
            }
            else {
                for (int j=first;j<(int)s.size()+1;j++) {
                    v.push_back((-1)*co);
                    co++;
                }
            }
    }
    rep(i,(int)s.size()+1) {
        //cout << v[i] << " ";
        su+=v[i];
    }
    //cout << '\n';
    cout << su << '\n';

    return 0;

    //compile: g++ -std=c++14 -O2 -Wall NAME.cpp -o NAME
}

Measured memory_bytes: 6932
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MON 1000000007
#define INF (1<<29)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

#define max(x, y) ((x)>(y)?(x):(y))
#define min(x, y) ((x)<(y)?(x):(y))


class Vec{
public:
  double x, y;
  Vec(double x = 0, double y = 0):x(x),y(y){}

  void read(){
    cin >> x >> y;
  }

  void print(){
    printf("%.10lf %.10lf\n", x, y);
  }
  
  Vec operator+(const Vec &other)
  {
    Vec result = *this;
    result.x += other.x;
    result.y += other.y;
    return result;
  }

  Vec operator-(const Vec &other)
  {
    Vec result = *this;
    result.x -= other.x;
    result.y -= other.y;
    return result;
  }

  Vec operator*(const double &k)
  {
    Vec result = *this;
    result.x *= k;
    result.y *= k;
    return result;
  }

  Vec operator/(const double &k)
  {
    Vec result = *this;
    result.x /= k;
    result.y /= k;
    return result;
  } 
  
  double cross(const Vec &other)
  {
    return x*other.y - y*other.x;
  }

  double dot(const Vec &other){
    return x*other.x + y*other.y;
  }
  
  bool operator==(const Vec &other) const
  {
    return abs(x - other.x) < EPS && abs(y - other.y) < EPS;
  }

  double norm()
  {
    return sqrt(x*x+y*y);
  }

  double norm2()
  {
    return x*x+y*y;
  }

  Vec standard(){
    Vec result = *this;
    return result/result.norm();
  }
};

//ccw:1, cw:-1, other:0
Int CCW(Vec a, Vec b, Vec c){
  b = b - a;
  c = c - a;
  if(b.cross(c) > EPS)return -1;
  if(b.cross(c) < -EPS)return 1;
  return 0;
}

double dist(Vec a, Vec b){
  return (a-b).norm();
}
			

class Line{
public:
  Vec a, b;
  Vec vect;
  Line(Vec a = Vec(), Vec b = Vec()):a(a),b(b),vect(b-a){}

  //projection
  Vec proj(Vec p){
    p = p - a;
    return a + vect * vect.dot(p) / vect.norm2();
  }

  //reflection
  Vec reflect(Vec p){
    return proj(p) * 2 - p;
  }

  bool onSegment(Vec p){
    return abs((p-a).cross(b-a)) < EPS && (p-a).dot(p-b) < EPS;
  }

  //other -> LineSegment(not inclusive), this -> Line
  bool _intersect(Line &other){
    return CCW(a, b, other.a) * CCW(a, b, other.b) < 0;
  }

  //other, this: both are LineSegment(inclusive)
  bool intersect(Line &other){
    return onSegment(other.a) || onSegment(other.b) || other.onSegment(a) || other.onSegment(b) || _intersect(other) && other._intersect(*this);
  }

  //low accuracy
  Vec crossPoint(Line &other){
    double ratio = (a - other.a).cross(vect) / other.vect.cross(vect);
    return other.a + other.vect * ratio;
  }

  double dist(Vec p){
    Vec pp = proj(p);
    if(onSegment(pp))return ::dist(p, pp);
    else return min(::dist(p, a), ::dist(p, b));
  }
  
  double dist(Line &other){
    if(intersect(other))return 0;
    return min(min(dist(other.a), dist(other.b)), min(other.dist(a), other.dist(b)));
  }
};


int main(){
  Int q;
  cin >> q;
  while(q--){
    Vec p0, p1, p2, p3;
    p0.read();
    p1.read();
    p2.read();
    p3.read();
    Line l1(p0, p1), l2(p2, p3);
    l1.crossPoint(l2).print();
  }
  return 0;
}


Measured memory_bytes: 3296
#include "bits/stdc++.h"
using namespace std;

string s[50];
bool f[26];
pair<int,int> tyouten[26][2];//最初に見つかった位置と最後に見つかった位置
int main()
{
	int d;
	int h,w;
	cin>>d;
	for(int cnt=0;cnt<d;cnt++)
	{
		cin>>h>>w;
		if(h==0)
			break;
		for(int i=0;i<h;i++)
			cin>>s[i];
		fill(f,f+26,true);
		fill(tyouten[0],tyouten[26],make_pair(-1,-1));
		//sを全走査して使われている文字を列挙する
		for(int i=0;i<h;i++)
		{
			for(int j=0;j<w;j++)
			{
				if(s[i][j]!='.')
				{
					if(f[s[i][j]-'A'])
					{
						f[s[i][j]-'A']=false;
						tyouten[s[i][j]-'A'][0]=make_pair(i,j);
						tyouten[s[i][j]-'A'][1]=make_pair(i,j);
					}else{
						tyouten[s[i][j]-'A'][0]=make_pair(min(tyouten[s[i][j]-'A'][0].first,i),min(tyouten[s[i][j]-'A'][0].second,j));
						tyouten[s[i][j]-'A'][1]=make_pair(max(tyouten[s[i][j]-'A'][1].first,i),max(tyouten[s[i][j]-'A'][1].second,j));
					}
				}
			}
		}
		//使われている文字から最初から長方形のものを探す
		bool ans=true;
		while(ans)
		{
			ans=false;
			for(int i=0;i<26;i++)
			{
				if(!f[i])
				{
					bool flag=true;
					//範囲を調べる
					for(int j=tyouten[i][0].first;j<tyouten[i][1].first+1;j++)
					{
						for(int k=tyouten[i][0].second;k<tyouten[i][1].second+1;k++)
						{
							if(!(s[j][k]=='A'+i || s[j][k]=='?'))
							{
								flag=false;
								break;
							}
						}
						if(!flag)
							break;
					}
					//無事長方形だったならその部分を?で埋める
					if(flag)
					{
						ans=true;
						f[i]=true;
						for(int j=tyouten[i][0].first;j<tyouten[i][1].first+1;j++)
						{
							for(int k=tyouten[i][0].second;k<tyouten[i][1].second+1;k++)
							{
								s[j][k]='?';
							}	
						}
					}	
				}
			}
		}
		//処理終わり
		ans=true;
		for(int i=0;i<26;i++)
		{
			if(!f[i])
				ans=false;
		}
		if(ans)
			cout<<"SAFE"<<endl;
		else
			cout<<"SUSPICIOUS"<<endl;
	}
	return 0;
}


Measured memory_bytes: 3120
<?php
$n = trim(fgets(STDIN));
$a[] = trim(fgets(STDIN));
$a[] = trim(fgets(STDIN));
$a[] = trim(fgets(STDIN));
$a[] = trim(fgets(STDIN));
$a[] = trim(fgets(STDIN));
$min = min($a);
printf("%15d", ceil($n / $min) + 4);

Measured memory_bytes: 4604
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B;
string S;
const ll MOD = 998244353;
//const ll MOD = (1e+9) + 7;
const ll INF = 1LL<<60;
typedef pair<ll, ll> P;

int main() {
    cin>>N;
    ll ans = (N / 500);
    N -= ans * 500;
    ans *= 1000;
    cout<<ans + (N / 5) * 5<<endl;
}

Measured memory_bytes: 384
#include<iostream>
#include<string>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N;
	string S;
	cin >> N >> S;
	int ans = N;
	for (int i = 1; i < N; i++){
		if (S[i - 1] == S[i]) {
			ans--;
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 512
#include<cstdio>
#include<vector>
#include<algorithm>
#include<utility>
#include<numeric>
#define _USE_MATH_DEFINES

#include<math.h>

#define min(a,b) (a)>(b)?(b):(a)
#define max(a,b) (a)>(b)?(a):(b)

using namespace std;

int main()
{
	int n;
	vector<int> a, b;
	
	while (true)
	{
		int ta, tb;
		scanf("%d %d", &ta, &tb);

		if (ta == 0 && tb == 0)
		{
			break;
		}
		else
		{
			a.push_back(ta);
			b.push_back(tb);
		}
	}

	for (int i = 0; i != a.size(); i++)
	{
		for (int j = 0; j < a[i]; j++)
		{
			for (int k = 0; k < b[i]; k++)
			{
				if (1 <= j && 1 <= k&&j < (a[i] - 1) && k < (b[i] - 1))
				{
					printf(".");
				}
				else
				{
					printf("#");
				}
			}
			printf("\n");
		}
		printf("\n");
	}

	return 0;
}

Measured memory_bytes: 2564
#include <iostream>
#include <cstdio>

using namespace std;

int K, f[11][10];

int main() {
	scanf("%d", &K);
	for (int i = 0; i < 10; i++) f[1][i] = 1;
	for (int i = 2; i <= 10; i++) {
		for (int j = 0; j < 10; j++) {
			f[i][j] += f[i - 1][j];
			if (j) f[i][j] += f[i - 1][j - 1];
			if (j < 9) f[i][j] += f[i - 1][j + 1];
		}
	}

	int n, s = 0;
	for (int i = 1; i <= 10; i++) {
		for (int j = 1; j < 10; j++) s += f[i][j];
		if (s >= K) {
			n = i;
			break;
		}
	}
	for (int i = 1; i < n; i++)
		for (int j = 1; j < 10; j++) K -= f[i][j];
	int L = 1, R = 9;
	for (int i = n; i; i--) {
		for (int j = L; j <= R; j++) {
			if (f[i][j] >= K) {
				printf("%d", j);
				L = max(0, j - 1), R = min(j + 1, 9);
				break;
			} else K -= f[i][j];
		}
	}
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
const ll mo = 1e10 +7;
const int M = 100+50;
int main(){
	int n;
	string a,b,c;
	scanf("%d",&n);
	cin>>a;
	cin>>b;
	cin>>c;
	int ans=0;
	int mark=0;
	for(int i=0;i<n;i++){
		int mark=0;
		if(a[i]==b[i])
		    mark++;
		if(a[i]==c[i])
		    mark++;
		if(b[i]==c[i])
		    mark++;
		if(mark==3)
		    continue;
		if(mark==1)
		    ans+=1;
		if(mark==0)
		    ans+=2;
	}
	printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int i,n;
    int64_t lucas[87];
    lucas[0]=2;
    lucas[1]=1;
    cin >> n;
    for (i = 2; i <= n; i++){
        lucas[i]=lucas[i-1]+lucas[i-2];
    }
    

    cout << lucas[n] <<endl;
    return 0;
}


Measured memory_bytes: 256
suuretsu = 0
list = []
i = 0
input = gets.chomp.split(" ").map{|x|x.to_i}


baseNum,suuretsuNum = input


if suuretsuNum != 0
  suuretsu = gets.chomp.split(" ").map{|x|x.to_i}

  while true
    if suuretsu.include?(baseNum - i)
    else
      puts baseNum - i
      break
    end
    if suuretsu.include?(baseNum + i)
    else
      puts baseNum + i
      break
    end
    i += 1
  end
else
  puts baseNum
end


Measured memory_bytes: 14368
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ul;

int main() {
  long a,b,c,d;
  cin >> a;
  cin >> b;
  cin >> c;
  cin >> d;
  
  long ac = a * c;
  long ad = a * d;
  long bc = b * c;
  long bd = b * d;
  long m = ac;
  if(m < ad){
    m = ad;
  }
  if(m < bc){
    m = bc;
  }
  if(m < bd){
    m = bd;
  }
  cout << m << endl;
}


Measured memory_bytes: 3632
#include<stdio.h>

void maxHeapify(int);
int A[500000],n;
int main(){
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d",&A[i]);
    for(i=n/2;i>=1;i--){
        maxHeapify(i);
    }
    for(i=1;i<=n;i++){ 
        printf(" %d",A[i]);
    }
    printf("\n");
return 0;
}

void maxHeapify(int i){
    int l,r,largest,x;
    l=i*2;
    r=(i*2)+1;
    if(l<=n && A[l]>A[i]) largest=l;
    else largest=i;
    if(r<=n && A[r]>A[largest]) largest=r;
    if(largest!=i){
        x=A[i];
        A[i]=A[largest];
        A[largest]=x;
        maxHeapify(largest);
    }
}



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

int main() {
	
	int a;
	int b;
	char op;
	
	while (true) {
		cin >> a >> op >> b;
		switch (op) {
		case '+':
			cout << (a + b) << endl;
			break;
		case '-':
			cout << (a - b) << endl;
			break;
		case '*':
			cout << (a * b) << endl;
			break;
		case '/':
			cout << (a / b) << endl;
			break;
		default:
			return 0;
		}
	}
	
	return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
double dp[3010][3010] = {0};

int main(){
    LL N;
    cin >> N;
    vector<double>    p(N);
    for(int i = 0;i < N;i++)    cin >> p[i];
    dp[0][0] = 1.0;
    for(int i = 0;i < N;i++)   dp[i+1][0] = dp[i][0]*(1.0-p[i]);
    for(int i = 0;i < N;i++){
        for(int j = 0;j <= i;j++){
            dp[i+1][j+1] = dp[i][j]*p[i]+dp[i][j+1]*(1.0-p[i]);
        }
    }
    double ans = 0.0;
    for(int i = (N+1)/2;i <= N;i++)  ans += dp[N][i];
    cout << setprecision(20) << ans << endl;
}

Measured memory_bytes: 69120
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_C main
#include "bits/stdc++.h"
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using psi = pair<string, int>;
// functions

#endif


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

    int N; cin >> N;
    vs S(N); REP(i, N) cin >> S[i];

    int xa = 0, bx = 0, bxa = 0;
    int cnt = 0;
    REP(i,N) {
        int L = S[i].size();
        REP(j, L-1) {
            if (S[i][j] == 'A' && S[i][j + 1] == 'B') cnt++;
        }

        if (S[i][0]=='B' && S[i][L-1]=='A') {
            bxa++;
        } else {
            if (S[i][L - 1] == 'A') xa++;
            if (S[i][0] == 'B') bx++;
        }
    }

    int ans = cnt;
    if (bxa >= 2) {
        ans += bxa - 1;
        bxa = 1;
    }
    if (bxa > 0) {
        if (xa >0 && bx>0) {
            ans+=2;
            xa--;
            bx--;
        } else if (xa>0) {
            ans++;
        } else if (bx>0) {
            ans++;
        }
    }
    ans += min(xa, bx);

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 768
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>

using namespace std;

int main(void) {
	int A;
	cin >> A;
	if(A<10){
		cout << A;
	}
	else if (A < 100) {
		cout << 9;
	}
	else if (A < 1000) {
		cout << 9 + A - 99;
	}
	else if (A < 10000) {
		cout << 9 + 900;
	}
	else if (A < 100000) {
		cout << 909 + A - 9999;
	}
	else {
		cout << 9 + 900 + 90000;
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
long long fac(ll a){
    long long ans=1;
    while(a>1){
        ans*=a;
        ans%=1000000007;
        a--;
    }
    return ans;
}
int main(){
    vl a(3),b(3),c(3);
    rep(i,3)cin >> a[i];
    rep(i,3)cin >> b[i];
    rep(i,3)cin >> c[i];
    ll count=0;
    if(a[0]-a[1]==b[0]-b[1]&&b[0]-b[1]==c[0]-c[1])count++;
    if(a[1]-a[2]==b[1]-b[2]&&b[1]-b[2]==c[1]-c[2])count++;
    if(a[0]-a[2]==b[0]-b[2]&&b[0]-b[2]==c[0]-c[2])count++;
    if(a[0]-b[0]==a[1]-b[1]&&a[1]-b[1]==a[2]-b[2])count++;
    if(b[0]-c[0]==b[1]-c[1]&&b[1]-c[1]==b[2]-c[2])count++;
    if(c[0]-a[0]==c[1]-a[1]&&c[1]-a[1]==c[2]-a[2])count++;
    if(count==6){
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

ans = 0
ab = sorted(ab, key=lambda x: x[1])
n = 0
for i in range(M):
    if ab[i][0] >= n:
        n = ab[i][1]
        ans += 1
print(ans)

Measured memory_bytes: 29852
from collections import Counter

n = int(input())
d = Counter(list(map(int, input().split())))
m = int(input())
t = Counter(list(map(int, input().split())))

valid = True
for i in t:
    if d[i] < t[i]:
        valid = False

if valid: print("YES")
else: print("NO")

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

const int INF = (int)1.01e9;


int main() {
#ifdef HOME
    freopen("in", "r", stdin);
#endif

    int p = 41;
    int cc = p * p + p + 1;
    vector<vector<int> > ans(cc);

    for (int i = 0; i <= p; i++) ans[0].push_back(i);
    for (int i = 0; i < p; i++) {
        ans[1 + i].push_back(0);
        for (int j = 0; j < p; j++) {
            ans[1 + i].push_back(1 + p + i * p + j);
        }
    }
    for (int i = 0; i < p; i++) {
        for (int j = 0; j < p; j++) {
            ans[1 + p + i * p + j].push_back(1 + i);
            for (int t = 0; t < p; t++) {
                ans[1 + p + i * p + j].push_back(1 + p + p * t + (i * t + j) % p);
            }
        }
    }


    for (int i = 0; i < (int)ans.size(); i++) {
        assert(ans[i].size() == ans[0].size());
        sort(ans[i].begin(), ans[i].end());
        ans[i].resize(unique(ans[i].begin(), ans[i].end()) - ans[i].begin());
    }
    vector<int> cnt(cc);
    for (auto v : ans) for (int x : v) cnt[x]++;
    for (int i = 0; i < cc; i++) assert(cnt[i] == cnt[0]);

    /*for (int i = 0; i < (int)ans.size(); i++) {
        for (int j = i + 1; j < (int)ans.size(); j++) {
            int cnt = 0;
            for (int x : ans[j]) cnt += binary_search(ans[i].begin(), ans[i].end(), x);
            assert(cnt == 1);
        }
    }*/

    cout << ans.size() << " " << ans[0].size() << endl;
    for (auto v : ans) {
        for (int i = 0; i < (int)v.size(); i++) cout << v[i] + 1 << " \n"[i + 1 == (int)v.size()];
    }


#ifdef HOME
    cerr << clock() / (double)CLOCKS_PER_SEC << endl;
#endif
    return 0;
}

Measured memory_bytes: 1024
n, m, c = map(int, input().split())
l = [0] + list(map(int, input().split()))
w = [tuple(map(int, input().split())) for _ in range(n)]
w.sort(key = lambda x:x[1], reverse = True)
v = 0
p = 0
for i in range(n):
    if l[w[i][0]]:
        l[w[i][0]] -= 1
        v += w[i][1]
        p += 1
        if p == m:
            break
print(v)


Measured memory_bytes: 23236
N,K = map(int, input().split())
lst = list(map(int, input().split()))
dp = [0 for i in range(N)]
for i in range(1,N):
    mn = 999999999999999999
    for j in range(max(i-K,0), i):
        mn = min(mn,dp[j] + abs(lst[i] - lst[j]))
    dp[i] = mn
print(dp[-1])

Measured memory_bytes: 56544