akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using i64 = int64_t;

int N, arr[101010];

int main() {
    cin >> N;
    for (int j = 0; j < N; ++j) {
        cin >> arr[j];
    }
    sort(arr, arr+N);

    vector<i64> v;
    v.push_back(0);
    v.push_back(0);
    for (int j = 0; j < N-1; ++j) {
        if (arr[j] == arr[j+1]) {
            v.push_back(arr[j]);
            ++j;
        }
    }

    cout << v[v.size()-1] * v[v.size()-2] << endl;
    return 0;
}


Measured memory_bytes: 1276
<?php
for($a = 0; $a < 3; $a++) {
    $board[] = explode(' ', fgets(STDIN));
}
//var_dump($board);
fscanf(STDIN, '%d', $b);
for($n = 0; $n < $b; $n++) {
    fscanf(STDIN, '%d', $bn);
    $needle[] = $bn;
}
//var_dump($needle); exit;
$bingo[] = explode(' ', $board[0][0].' '.$board[0][1].' '.$board[0][2]);
$bingo[] = explode(' ', $board[1][0].' '.$board[1][1].' '.$board[1][2]);
$bingo[] = explode(' ', $board[2][0].' '.$board[2][1].' '.$board[2][2]);
$bingo[] = explode(' ', $board[0][0].' '.$board[1][0].' '.$board[2][0]);
$bingo[] = explode(' ', $board[0][1].' '.$board[1][1].' '.$board[2][1]);
$bingo[] = explode(' ', $board[0][2].' '.$board[1][2].' '.$board[2][2]);

$bingo[] = explode(' ', $board[0][0].' '.$board[1][1].' '.$board[2][2]);
$bingo[] = explode(' ', $board[0][2].' '.$board[1][1].' '.$board[2][0]);

$c = count($bingo);
$ans = 'No';
for($i = 0; $i < $c; $i++) {
    $b_count = 0;
    foreach($needle as $ne) {
        if(in_array($ne, $bingo[$i])) $b_count++;
    }
    if($b_count == 3) {
        $ans = 'Yes';
        break;
    }
}
echo $ans, PHP_EOL;

Measured memory_bytes: 4728
n = int(input())

x = list(map(float,input().split()))
y = list(map(float,input().split()))
D = []

sm = 0.0

for i in range(n):
    D.append(abs(x[i]-y[i]))
print('{:.08f}'.format(sum(D)))

for i in range(n):
    sm +=(x[i]-y[i])**2
print('{:.08f}'.format(sm**0.5))

sm = 0.0
for i in range(n):
    sm +=abs(x[i]-y[i])**3

print('{:.08f}'.format(sm**(1.0/3.0)))

print('{:.08f}'.format(max(D)))


Measured memory_bytes: 5672
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define setbits(x) __builtin_popcountll(x)
#define zerobits(x) __builtin_ctzll(x)
#define MOD 1000000007
#define inf 1e18
#define deb(x) cout << #x << " -> " << x << "\n";

#ifdef LOCAL_DEFINE
	mt19937 rng(228);
#else 
	mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

using ll = long long;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);	
	cout.precision(10);
	cout << fixed;
	int n;
	cin >> n;
	vector<int>	a(10005);
	for (int i = 1; i <= 105; i++) {
		for (int j = 1; j <= 105; j++) {
			for (int k = 1; k <= 105; k++) {
				int v = i * i + j * j + k * k + i * j + j * k + k * i;
				if (v < 10005) a[v]++;
			}
		}
	}
	for (int i = 0; i < n; i++) cout << a[i + 1] << "\n";
	return 0;
}


Measured memory_bytes: 3664
object Main extends App {

  val Array(n, a, b) = io.StdIn.readLine.split(" ").map(_.toInt)

  val ans = (1 to n).foldLeft(0)( (acc,i) => {

    val sum = (1 to 5).foldLeft((i,0))( (acc,_) => {
      if(acc._1 != 0) (acc._1 / 10, acc._2 + (acc._1 % 10))
      else  (0, acc._2)
    })._2

    if(a <= sum && sum <= b ) acc + i else acc
  })

  println(ans)
}

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

// a1, a2, a3, ... , a_3Nを昇順に並べ、A1 <= A2 <= A3 <= ... <= A_3Nとする。
// {Ai}から3つで一組のペアをN組作って、それらの強さをR1 <= R2 <= ... <= R_Nとする。
// この時、R_iの強さは、A_(N+2i-1)以上にはならない。
// よって、全体として、強さの総和はA_(N+1) + A_(N+3) + ... + A_(3N-1)以上にならない

int main() {
    int N;
    cin >> N;
    vector<int> A(3*N);
    for(size_t i = 0; i < 3*N; ++i) {
        cin >> A[i];
    }
    sort(A.begin(), A.end());
    long long res = 0LL;
    for(size_t i = 0; i < N; ++i) {
        res += A[N+2*i];
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 1536
#!/usr/bin/env python
"""<https://github.com/cheran-senthil/PyRival>"""
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase
from collections import Counter

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
else:
    _str = str
    str = lambda x=b"": x if type(x) is bytes else _str(x).encode()

MOD = 10**9 + 7


def main():
    k, d = list(map(int, input())), int(input())
    n = len(k)

    dp = [[0] * d for _ in range(n)]
    for m in range(10):
        dp[0][m % d] += 1
    for i in range(n - 1):
        for j in range(d):
            dp[i + 1][j] = sum(dp[i][(j - m) % d] for m in range(10)) % MOD

    res, cnt = 0, 0
    for i in range(n - 1):
        res = (res + sum(dp[-i - 2][(-m - cnt) % d] for m in range(k[i]))) % MOD
        cnt += k[i]
    res += sum((cnt + m) % d == 0 for m in range(k[-1] + 1))

    print((res - 1) % MOD)


# region template

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._buffer = BytesIO()
        self._fd = file.fileno()
        self._writable = "x" in file.mode or "r" not in file.mode
        self.write = self._buffer.write if self._writable else None

    def read(self):
        if self._buffer.tell():
            return self._buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()

    def flush(self):
        if self._writable:
            os.write(self._fd, self._buffer.getvalue())
            self._buffer.truncate(0), self._buffer.seek(0)


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", b" "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", b"\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip(b"\r\n")

# endregion

if __name__ == "__main__":
    main()


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

int main(){
	//宣言
	int n,k;
	string s;
	string ans;
	//入力
	cin >> n >> k;
	cin >> s;
	//計算
	s[k-1] = s[k-1] + 0x20;
	//出力
	cout << s << endl;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int N,X,i; scanf("%d %d",&N,&X);
  int L[N];
  for(i=0;i<N;++i)scanf("%d",&L[i]);
  int D[N+2]; D[0]=0;
  for(i=1;i<=N;++i)D[i]=D[i-1]+L[i-1];

  int answer=0;
  for(i=0;i<=N;++i){
    if(D[i]<=X)answer++;
  }
  printf("%d",answer);

}

Measured memory_bytes: 128
#include<stdio.h>
int main(){
  int n,k,x,y;
  int sum;
  scanf("%d %d %d %d",&n,&k,&x,&y);
  if(n>k){
    sum=x*k+y*(n-k);
  }else{
    sum=x*n;
  }
  printf("%d",sum);
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define all(v) v.begin(), v.end()
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    int cnt[4] = {};
    rep(i, 0, 3) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        cnt[a]++;
        cnt[b]++;
    }

    sort(cnt, cnt + 4);

    if (cnt[0] == 1 && cnt[1] == 1 && cnt[2] == 2 && cnt[3] == 2) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

#ifdef _DEBUG
#define DMP(x) cerr << #x << ": " << x << "\n"
#else
#define DMP(x) ((void)0)
#endif

const int MOD = 1000000007, INF = 1111111111; 
using namespace std;
typedef long long lint;

int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);

	int A, B;
	cin >> A >> B;

	cout << (B % A ? B - A : B + A) << "\n";

	return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
  ll L,R; cin >> L >> R;
  ll llim = min(L+2019,R);
  ll rlim = max(R-2019,L);
  ll ans = 2018;
  ll ipos = L;
  for (ll i = L; i <= llim; ++i) {
    for (ll j = R; j >= rlim; --j) {
      if (i!=j && (i*j)%2019 < ans) ans = (i*j)%2019;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
<?php
fscanf(STDIN, "%d%d", $a, $b);
for($i = 0; $i <= 50; $i++){
  for($j = 0; $j <= 25; $j++){
    if($i + $j == $a && $i*2+$j*4==$b){
      echo "Yes";exit;
    }
  }
}
echo "No";

Measured memory_bytes: 16100
#include <stdio.h>

int main() {
  int i, n;
  int fib[45];
  fib[0] = fib[1] = 1;
  for(i = 2; i < 45; ++i) {
    fib[i] = fib[i-1] + fib[i-2];
  }
  scanf("%d", &n);
  printf("%d\n", fib[n]);
  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1e9+7;
const LL LINF=1LL<<62;
const int INF=1<<30;

int main(){
    int n,k;
    cin >> n >> k;
    vector<int> a,b;
    a.pb(0);
    b.pb(0);
    for(int i=0;i<n;i++){
        int t;
        cin >> t;
        if(t>0) a.pb(t);
        else if(t==0) k--;
        else b.pb(t);
    }
    sort(ALL(a));
    sort(RALL(b));
    int ans=INF;
    for(int i=0;i<=k&&i<a.size();i++){
        if(k-i<b.size()) ans=min(ans,2*a[i]-b[k-i]);
    }
    for(int i=0;i<=k&&i<b.size();i++){
        if(k-i<a.size()) ans=min(ans,(-2)*b[i]+a[k-i]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1020
#整数Nを得る
N = int(input())
#list  Pを得る
P = list(map(int,input().split()))

c = 0

for i in range(1,N-1):
    #真ん中が最大値でも最小値でもなければ数える
    M = max(P[i-1],P[i],P[i+1])
    m = min(P[i-1],P[i],P[i+1])
    if P[i] != M and P[i] != m: c += 1

print(c)


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

int main(){
  int N, T, result = 100000;
  cin >> N >> T;
  int cost[2];
  rep(i, N){
    cin >> cost[0] >> cost[1];
    if (T >= cost[1]) {
      result = min(result, cost[0]);
    }
  }
  if (result == 100000) {
    cout << "TLE" << endl;
  }else{
    cout << result << endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define w while
#define loop(i,l,r) for(int i=l;i<r;i++)
#define ci cin>>
#define co cout<<
#define mm 1000000007
#define ll long long
using namespace std;
int main()
 {  ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin>>n>>m;
    char a[n][m];
    int dp[n][m];
    loop(i,0,n){
      loop(j,0,m){
        ci a[i][j];
        dp[i][j]=0;
      }
    }
    dp[0][0]=1;
    for(int i=1;i<n;i++){
      if(a[i][0]=='.')
      dp[i][0]=dp[i-1][0];
        }
    loop(j,1,m){
      if(a[0][j]=='.'){
        dp[0][j]=dp[0][j-1];
      }
      }
       loop(i,1,n){
         loop(j,1,m){
           if(a[i][j]=='.'){
             dp[i][j]=(dp[i-1][j]%mm+dp[i][j-1]%mm)%mm;
           }
          }
       }
      cout<<dp[n-1][m-1]%mm;
}


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

using namespace std;

int main()
{
    int N;
    cin >> N;
    long long H[100000] = {};

    long long preVal = -1;
    bool isYes = true;
    for(int i = 0; i < N; i++)
    {
        cin >> H[i];
        if(preVal == -1)
        {
            preVal = H[i] - 1;
            continue;
        }

        if(preVal < H[i])
        {
            preVal = H[i] -1;
            continue;
        }
        else if(preVal == H[i])
        {
            preVal = H[i];   
        }
        else if(H[i] < preVal)
        {
            isYes = false;
            break;
        }
    }
    if(isYes)
    {
        cout << "Yes" << endl; 
    }
    else
    {
        cout << "No" << endl;
    }
    
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;


int main(){
  int N, K;
  cin >> N >> K;

  int M = N;
  double ret = 0.0;
  if(N >= K){
    ret += (N-K+1.0) / N;
    M = K;
  }
  double p = 0.5;
  bool flg = false;
  if(M >= K) flg = true;
  while(true){
    int K2 = (K + 1) / 2;
    if(!flg && K2 <= M && M < K){
      flg = true;
      ret += p * (M-K2+1.0)/N;
      M = K2;
    }else{
      if(flg){
        ret += p * (M-K2+0.0)/N;
        M = K2;
      }
    }
    if(K2 <= 1) break;
    K = K2;
    p *= 0.5;
  }

  printf("%.12lf\n", ret);
  
  return 0;
}


Measured memory_bytes: 256
/*      ░░█ ▄▀█ █   █▀ █░█ █▀█ █▀▀ █▀▀   █▀█ ▄▀█ █▀▄▀█
        █▄█ █▀█ █   ▄█ █▀█ █▀▄ ██▄ ██▄   █▀▄ █▀█ █░▀░█     */

// Author : Udit "luctivud" Gupta @ (https://www.linkedin.com/in/udit-gupta-1b7863135/)


#include <bits/stdc++.h>
#pragma GCC optimize "trapv"

using namespace std;

typedef long long int lld;
typedef unsigned long long int llu;


#define       TESTCASES()  cin >> (T3X0); T353 = T3X0; while(T3X0--)
#define       _input(V3C)  for(auto &V3C_I7 : (V3C)) cin >> (V3C_I7)
#define mems(A77AY, V4LU)  memset((A77AY), (V4LU), sizeof((A77AY)))
#define  CH3K(I7, E4, S7)  (((S7)<0) ? (I7)>(E4) : (I7)<(E4))
#define for4(I7,S4,E4,S7)  for(auto I7=(S4); CH3K(I7,E4,S7); (I7)+=(S7))




void solveEachTest(lld T35TC453N = 1) {

	lld ans = 0ll;
	lld n; cin >> n;

	for (ans; ans * ans <= n; ans++) {

	}
	cout << (ans - 1ll) * (ans - 1ll);
	return;
}


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

	lld T3X0 = 0, T353 = 1;

	// TESTCASES()
	solveEachTest(T353 - T3X0);
	return 0;
}
// Random Thought :  null

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

Measured memory_bytes: 1812
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>

using namespace std;

#define PB push_back
#define ALL(v) (v).begin(), (v).end()
#define SZ size()
#define FOR(i, a, b) for(int (i) = (a); (i) < (b); (i)++)
#define REP(i, n) FOR((i), 0, (n))
#define GET(a) cin >> (a)
#define GET2(a, b) cin >> (a) >> (b)
#define GET3(a, b, c) cin >> (a) >> (b) >> (c)
#define SHOW(v) cout << (v) << endl
#define SHOW2(a, b) cout << (a) << " " << (b) << endl
#define SHOW3(a, b, c) cout << (a) << " " << (b) << " " << (c) << endl
#define MOD 1000000007
template<class T> void GETV(T &v) { REP(i, v.size()) { GET(v[i]); } }
template<class T> void SHOWV(T &v) { REP(i, v.size()) { SHOW(v[i]); } }

typedef long long ll;


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

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


#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()


using namespace std;
using namespace __gnu_pbds;

template<class T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
using ll  = long long;

using point = complex<double>;


void err(istream_iterator<string> it) {cerr << endl;}
template<typename T, typename... Args>void err(istream_iterator<string> it, T a, Args... args) {cerr << *it << " = " << a << endl;err(++it, args...);}


const double EPS = 1e-8;
const long long mod = 1e9+7;

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

const int N = 3e5 + 5;


int n , x;
vector<int>a,b,c;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> x;
        a.push_back(x);
    }
    for(int i = 0; i < n; ++i){
        cin >> x;
        b.push_back(x);
    }
    for(int i = 0; i < n; ++i){
        cin >> x;
        c.push_back(x);
    }
    sort(all(a));
    sort(all(b));
    sort(all(c));
    ll ans = 0;
    int ia, ic;
    for(int i = 0; i < n; ++i){
        ia = upper_bound(all(a),b[i]-1)-a.begin();
        ic = c.end() - lower_bound(all(c),b[i]+1);
        //error(ia,ic);
        ans = ans + (1ll * ia * ic);
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 1784
n = int(input())
word = []
for i in range(n) :
    word.append(input())
for i in range(1,n) :
    if word[i][0] != word[i-1][len(word[i-1]) - 1] :
        print("No")
        break
    if word[i] in word[:i] :
        print("No")
        break
else :
    print("Yes")


Measured memory_bytes: 9172
n = int(input())
a = list(map(int, input().split()))
o = [a[i] for i in range(2,n,2)]
e = [a[h] for h in range(1,n,2)]
if n%2 == 0:
    e.reverse()
    l = e + [a[0]] + o
    print(*l)
else:
    o.reverse()
    l = o + [a[0]] + e
    print(*l)

Measured memory_bytes: 30828
#include<cctype>
#include<cstdio>
#include<cstring>

using namespace std;

class Pattern{
public:
	int w,h;
	char fig[5][5];
	Pattern(){}
	Pattern(int ww,int hh):w(ww),h(hh){}
};

bool isMatch(const int f[5][5],const Pattern &p){
	int w=p.w,h=p.h;

	int c=0;
	for(int i=0;i<5;i++)for(int j=0;j<5;j++)	if(f[i][j]!=0)	c++;
	if(c!=6)	return false;

	for(int i=0;i<6-h;i++)for(int j=0;j<6-w;j++){
		int cnt[3]={};
		bool chk[7]={};
		for(int y=0;y<h;y++)for(int x=0;x<w;x++){
			if(!islower(p.fig[y][x]))	continue;
			if(f[i+y][j+x]<=0 || 6<f[i+y][j+x] || chk[f[i+y][j+x]])	goto NOMATCH;
			chk[f[i+y][j+x]]=true;
			cnt[p.fig[y][x]-'a']+=f[i+y][j+x];
		}

		if(cnt[0]==7 && cnt[1]==7 && cnt[2]==7)	return true;
		NOMATCH:;
	}

	return false;
}

int main(){
	char fig[11][5][6]={
		{" c  ",
		 "abab",
		 " c  "},
		{" c  ",
		 "abab",
		 "  c "},
		{" c  ",
		 "abab",
		 "   c"},
		{"  c ",
		 "abab",
		 "   c"},
		{"   c",
		 "abab",
		 "   c"},
		{"c   ",
		 "abab",
		 "   c"},
		{"ab  ",
		 " ca ",
		 "  bc"},
		{"aba  ",
		 "  cbc"},
		{"ab  ",
		 " cac",
		 "   b"},
		{"ab  ",
		 " cac",
		 "  b "},
		{"ab  ",
		 " cac",
		 " b  "}
	};

	Pattern ptn[88];
	ptn[ 0]=Pattern(4,3);
	ptn[ 1]=Pattern(4,3);
	ptn[ 2]=Pattern(4,3);
	ptn[ 3]=Pattern(4,3);
	ptn[ 4]=Pattern(4,3);
	ptn[ 5]=Pattern(4,3);
	ptn[ 6]=Pattern(4,3);
	ptn[ 7]=Pattern(5,2);
	ptn[ 8]=Pattern(4,3);
	ptn[ 9]=Pattern(4,3);
	ptn[10]=Pattern(4,3);
	for(int i=0;i<11;i++){
		int h=ptn[i].h;
		for(int k=0;k<h;k++)
			strcpy(ptn[i].fig[k],fig[i][k]);
	}

	for(int i=11;i<22;i++){
		ptn[i]=Pattern(ptn[i-11].w,ptn[i-11].h);
		int w=ptn[i].w;
		int h=ptn[i].h;
		for(int k=0;k<h;k++){
			for(int j=0;j<w;j++)
				ptn[i].fig[k][w-j-1]=ptn[i-11].fig[k][j];
		}
	}

	for(int t=1;t<4;t++){
		for(int i=22*t;i<22*(t+1);i++){
			ptn[i]=Pattern(ptn[i-22].h,ptn[i-22].w);
			int w=ptn[i-22].w;
			int h=ptn[i-22].h;
			for(int k=0;k<h;k++){
				for(int j=0;j<w;j++)
					ptn[i].fig[w-j-1][k]=ptn[i-22].fig[k][j];
			}
		}
	}

	int n;	scanf("%d",&n);
	while(n--){
		int f[5][5];
		for(int i=0;i<5;i++)for(int j=0;j<5;j++)	scanf("%d",f[i]+j);

		bool ok=false;
		for(int i=0;i<88;i++){
			if(isMatch(f,ptn[i])){ ok=true; break; }
		}
		puts(ok?"true":"false");
	}

	return 0;
}

Measured memory_bytes: 0
import Control.Monad
import Data.Array.IArray

sa :: Int -> Int -> Int -> Int
sa a1 a2 a3 = abs (a2 - a1) + abs (a3 - a2) - abs (a3 - a1)

main :: IO ()
main = do
    n <- readLn :: IO Int
    a <- map read . words <$> getLine :: IO [Int]
    let xx = sum $ zipWith (\x y -> abs (y-x)) (0:a) (a++[0])
        aa = listArray (0,n+1) ((0:a) ++ [0]) :: Array Int Int
    forM_ [1..n] $ \i -> do
        if (aa!(i-1) <= aa!i && aa!i > aa!(i+1)) ||
           (aa!(i-1) >= aa!i && aa!i < aa!(i+1))
           then print $ xx - (sa (aa!(i-1)) (aa!i) (aa!(i+1)))
           else print xx


Measured memory_bytes: 44284
#include<bits/stdc++.h>
using namespace std;
string s,t;
int num;
int main(){
	cin>>s>>t;
	if (s[0]==t[0]) num++;
	if (s[1]==t[1]) num++;
	if (s[2]==t[2]) num++;
	cout<<num<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
int main(){
	int isprime[50001] = {0};
	isprime[2] = 1;
	std::vector<int> v;
	v.push_back(2);
	for(int i=3;i<=50000;i+=2){
		bool f = true;
		for(int j=0;v[j]*v[j]<=i;j++){
			if(i % v[j] == 0){f=false;break;}
		}
		if(f){v.push_back(i),isprime[i] = 1;}
	}

	int n, res = 0;
	while(std::cin >> n, n){
		res = 0;
		for(int i=2;i<=n/2;i++){
			if(isprime[i] && isprime[n-i])res++;
		}
		std::cout << res << std::endl;
	}
	
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); ++ i)
#define rrp(i,a,b) for (int i = (a); i >= (b); -- i)
#define gc() getchar()
#define fir first
#define sec second
typedef pair<int,int> pii;
typedef long double db;
typedef long long ll;
template <typename tp>
inline void read(tp& x) {
  x = 0; char tmp; bool key = 0;
  for (tmp = gc(); !isdigit(tmp); tmp = gc())
    key = (tmp == '-');
  for (; isdigit(tmp); tmp = gc()) 
    x = (x << 3) + (x << 1) + (tmp ^ '0');
  if (key) x = -x;
}
template <typename tp>
inline void ckmn(tp& x,tp y) {
  x = x < y ? x : y;
}
template <typename tp>
inline void ckmx(tp& x,tp y) {
  x = x < y ? y : x;
}

int n;
int main() {
  read(n);
  if (n <= 2) {
    puts("No");
    return 0;
  }
  int key = 1;
  for (int i = 1; i <= n; i <<= 1)
    if (i == n) key = 0;
  if (!key) {
    puts("No");
    return 0;
  }
  puts("Yes");
  rep (i, 1, 2) printf("%d %d\n", i, i+1);
  printf("3 %d\n", 1 + n);
  rep (i, 1, 2) printf("%d %d\n", i+n, i+1+n);
  for (int i = 4; i+1 <= n; i += 2) {
    printf("%d %d\n", i, i+n+1);
    printf("%d %d\n", i+n, i+1);
    printf("%d %d\n", i, n+1);
    printf("%d %d\n", i+1, n+1);
  }
  if (n % 2 == 0) {
    int v = n ^ 1;
    rep (i, 2, n-1) if ((v ^ i) < n && (v ^ i) > 1) {
      printf("%d %d\n", (i == 2 ? i + n : i), n);
      printf("%d %d\n", ((v ^ i) == 2 ? (v ^ i) + n : (v ^ i)), n + n);
      break;
    }
  }
  return 0;
}


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

typedef long long ll;
typedef pair<ll,int> P;
typedef pair<ll,P> PP;
vector<PP> r;
ll a[100005];
ll b[100005];
int main() {
  int n;
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> a[i] >> b[i];
    r.push_back(PP(b[i]+a[i],P(a[i],i)));
  }

  sort(r.begin(),r.end());

  ll ans = 0;
  bool TorA = true;
  for(int i = n - 1; i >= 0; i--) {
    if(TorA) ans += a[r[i].second.second];
    else ans -= b[r[i].second.second];
    TorA = !TorA;
    
  }

  cout << ans << endl;
}


Measured memory_bytes: 5748
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;

// to container
template <class C>
void input(C &c)
{
    for_each(c.begin(), c.end(), [](auto &i) { cin >> i; });
}

// to number, string
template <class T>
T input()
{
    T data;
    cin >> data;
    return data;
}

int main()
{
    long N = input<long>();
    string S = input<string>();

    long res = 0;
    char pre = '.';
    for (int i = 0; i < N; i++)
    {
        if (S[i] != pre)
        {
            res++;
            pre = S[i];
        }
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 512
package main

import "fmt"

func main(){
	N := 3
	var temp int
	a := make([]int, N*N)
	hole := make([]bool, N*N)
	for i := 0 ; i < N*N ; i++ {
		fmt.Scan(&a[i])
	}
//fmt.Println(a)
	var n int
	fmt.Scan(&n)
	for i := 0 ; i < n ; i++ {
		fmt.Scan(&temp)
//fmt.Println(temp)
		for j := 0 ; j < N*N ; j++ {
			if temp == a[j] {
				hole[j] = true
			}
		}
	}
//fmt.Println(hole)
	//vir
	var ans bool
	if hole[0] && hole[4] && hole[8] {
		ans = true
	} else if hole[2] && hole[4] && hole[6] {
		ans = true
	}
	if ans != true{
		for i := 0 ; i < N ; i++ {
			if hole[i*3] && hole[i*3+1] && hole[i*3+2] {
				ans = true
				break
			}
			if hole[3*0+i] && hole[3*1+i] && hole[3*2+i] {
				ans = true
				break
			}
		}
	}
	if ans {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
ll mm=1000000000;ll MM=mm+7;
#define rep(i, n) for(int i=0;i<n;i++)

int main(){
 int n,k;
  cin >> n >> k;
  VI d(k);
  set<int> S;
  rep(i,k){
    cin >> d.at(i);
    VI a(d.at(i));
    rep(j,d.at(i)){
      cin >> a.at(j);
      S.insert(a.at(j));
    }
  }
  int m=S.size();
  cout << n-m << endl;
      
}

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

int main(){
  string S;
  cin >> S;
  bool a=false;
  if(S.at(0)==S.at(1) && S.at(2)==S.at(3) && S.at(0)!=S.at(2)){
    a=true;
  }
   else if(S.at(0)==S.at(2) && S.at(1)==S.at(3) && S.at(0)!=S.at(1)){
    a=true;
  }
   else if(S.at(0)==S.at(3) && S.at(1)==S.at(2) && S.at(0)!=S.at(1)){
    a=true;
  }
  
  if(a){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,K;
  string S;
  cin>>N>>S>>K;
  for(int i=0;i<N;i++){
    if(S[i]!=S[K-1])
      S[i]='*';
  }
  cout<<S<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()
#define pb push_back

template<class T> inline bool chmin(T &a, T b){
	if(a>b){a=b;return true;}
	return false;
}
template<class T> inline bool chmax(T &a, T b){
	if(a<b){a=b;return true;}
	return false;
}
constexpr int mod = 1e9+7;
constexpr int inf = 3e18;

int N,K;
int to[200005];
int cnt[200005];
int st,shu;
void dfs(int x){
	if(cnt[to[x]]==inf){
		cnt[to[x]]=cnt[x]+1;
		dfs(to[x]);
	}else {
		st=cnt[to[x]];
		shu=cnt[x]+1-cnt[to[x]];
	}
}
signed main() {
	cin.tie(0);ios::sync_with_stdio(false);
	cin>>N>>K;
	rep(i,N){
		cin>>to[i];
		to[i]--;
		cnt[i]=inf;
	}
	cnt[0]=0;
	dfs(0);
	if(K>=st)K=(K-st)%shu+st;
	rep(i,N){
		if(K==cnt[i]){
			cout<<i+1<<endl;return 0;
		}
	}
}


Measured memory_bytes: 6776
# -*- coding: utf-8 -*-

import sys
import math


debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        # for line in sys.stdin:
        #     lines.append(line)
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]

    s = lines[0]

    return (s, )


def solve(s):
    
    
    result = 'Yes'
    if s == 'AAA' or s == 'BBB':
        result = 'No'

    return result
    


def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':

    main()
	

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

int main()
{
    int r , c ;
    cin >> r >> c ;
    vector <int> v[r] ;
    vector <int> lastrow ;
    for(int i = 0 ; i < r ; i++)
    {
        int sumi = 0 ;
        for(int j = 0 ; j < c ; j++)
        {
            int G ;
            cin >> G ;
            v[i].push_back(G) ;
            sumi += G ;
        }
        v[i].push_back(sumi) ;
    }
    int SUM = 0 ;
    for(int i = 0 ; i < c ; i++)
    {
        int sumi = 0 ;
        for(int j = 0 ; j < r ; j++)
        {
            sumi += v[j][i] ;
        }
        lastrow.push_back(sumi) ;
        SUM += sumi ;
    }
    lastrow.push_back(SUM) ;
    for(int i = 0 ; i < r ; i++)
    {
        cout << v[i][0] ;
        for(int j = 1 ; j <= c ; j++) cout << " " << v[i][j] ;
        cout << endl ;
    }
    cout << lastrow[0] ;
    for(int i = 1 ; i <= c ; i++) cout << " " << lastrow[i] ;
    cout << endl ;
}


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

//par[i] contains the parent class of i 
vector<int> par;
 
int findpar(int n){
    //the root grandparent
	if(par[n]==n)
        return n;
	
    //updates all par[n] and all (parents of par[n]) to  same root grandparent
    return par[n]=findpar(par[n]);
}
 
void updaterelation(int a,int b){
    //find parent of a
	int p1=findpar(a);
    //find parent of b
	int p2=findpar(b);
    //make p1 as parent of p2 if already 
	par[p2]=p1;
}
 
int main(){

    int i,j,n,m,a,b;
    cin>>n>>m;

    par=vector<int>(n+1);

    //initially all members are root grandparent of themselves.
    for(i=1;i<=n;i++)
        par[i]=i;

    while(m--){ 
    	cin>>a>>b;
    	updaterelation(a,b);
    }
    
    set<int> s;
    for(i=1;i<=n;i++) {
        //find() is important to update all par[i] to their root grandparent values for uniformity.
        s.insert(findpar(i));
    }

    cout<<s.size()-1;
	return 0;
}

Measured memory_bytes: 7692
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define ll long long
#define ull unsigned long long
#define pb push_back
#define rr return 0
#define fi first
#define se second
#define vi vector<int>
#define all(x) (x).begin(), (x).end()
#define sz(s) s.size()
using namespace std;
//Debug template by livw
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif


//const int Nmax=1000005;
//int arr[Nmax];

int main() 
{
    int n,k,i,sum=0;
    cin>>n>>k;
    int arr[n];
    for(i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+n);
    for(i=0;i<k;i++)
    {
        sum+=arr[i];
    }
    cout<<sum;
}

Measured memory_bytes: 3632
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Main{
  public static void main(String[] args) throws Exception{
	  Scanner sc = new Scanner(System.in);
	  int n = sc.nextInt();
	  int k = sc.nextInt();
	  ArrayList<Integer> a = new ArrayList<Integer>();
	  while(n-- > 0) {
		  a.add(sc.nextInt());
	  }
	  Collections.sort(a);
	  int ans = 0;
	  for(int i = 0; i < k; i++) {
		  ans += a.get(i);
	  }
	  System.out.println(ans);
  }
}

Measured memory_bytes: 38820
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
??´?????????
"""

suits = {"S": 0, "H": 1, "C": 2, "D": 3}
nsuits = ["S", "H", "C", "D"]

cards = [[0 for i in range(13)] for j in range(4)]
n = int(input())

for i in range(n):
    inp = input().split(" ")
    s = inp[0]
    c = int(inp[1]) - 1
    cards[suits[s]][c] = 1

for i in range(4):
    for j in range(13):
        if cards[i][j] == 0:
            print("{0} {1}".format(nsuits[i], j+1))

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

int main(){
    int N; cin >> N;
    int a[N];
    int b[100010] = {};
    int ans = 0;
    for(int i = 0; i < N; i++){
        cin >> a[i];
        if(a[i] > 100000)ans++;
        else b[a[i]]++;
    }
    
    for(int i = 0; i < 100010; i++){
        if(b[i] >= i) ans += b[i] - i;
        else ans += b[i];
    }
    cout << ans << endl;


    return 0;
}

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

using namespace std;

int n,m;
const int MAXN = 2e5+5;
const int MOD = 1e9+7;
long long dp[MAXN];
long long s[MAXN];

map<long long, long long> mp;

int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	int last=-1;
	for(int i=0;i<n;i++){
		int tmp;
		cin>>tmp;
		if(tmp==last) continue;
		s[++m]=tmp;
		last=tmp;
	}
	dp[0]=dp[1]=1;mp[s[1]]=1;
	for(int i=2;i<=m;i++){
		//int siz=mp[s[i]].size();
		if(mp[s[i]]){
			dp[i]=(dp[i-1]+mp[s[i]])%MOD;
			mp[s[i]]=(mp[s[i]]+dp[i-1])%MOD;
		}
		else{
			dp[i]=dp[i-1];
			mp[s[i]]=dp[i-1];
		}
	}
	cout<<dp[m]%MOD<<endl;
/*	for(int i=0;i<=m;i++){
		cout<<i<<' '<<dp[i]<<endl;	
	}*/
	return 0;
}

Measured memory_bytes: 15872
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
typedef long long ll;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

int main () {

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

    int res = 0;
    for (int i = a; i < b+1; i++) {
        string s = to_string(i);
        if(s[0] == s[4] && s[1] == s[3]) {
            res += 1;
        } 
    }

    cout << res << endl;

    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<cmath>
#include<cstdio>

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

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    ll X=0;
    ll K=0;
    ll D=0;
    ll Ans=0;
    
    cin >> X >> K >> D;
    
    X = abs(X);
    
    ll M = X / D;

    if(M>K){
        Ans = X - (K * D);
    }else{
        K -= M;
        X -= M*D;
        
        if(K%2==1) X = abs(X-D);
        Ans = abs(X);
    }
    
    cout << Ans << endl;
    
    return 0;
}


Measured memory_bytes: 3160
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd_(ll a,ll b){if(a%b==0)return b;return gcd_(b,a%b);}
ll lcm_(ll a,ll b){ll c=gcd_(a,b);return ((a/c)*(b/c)*c);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e16)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))
//tie(a,b,c) = make_tuple(10,9,87);
#define pop_(a) __builtin_popcount((a))
ll keta(ll a){ll r=0;while(a){a/=10;r++;}return r;}


int main(){
  ll n,m;
  string s,t;

  cin >> n >> m >> s >> t;

  ll len = lcm_(n,m);

  FOR(i,0,100000){
    if(len > n*m)break;
    bool ok = true;
    FOR(k,0,n){
      if(k*m % n == 0){
        if(s[k]!=t[k*m/n])ok=false;
        if(not ok)break;
      }
    }
    if(ok){
      cout << len << endl;
      return 0;
    }
    len += lcm_(n,m); 
  }
  cout << -1 << endl;


}




Measured memory_bytes: 3740
#include "bits/stdc++.h"
using namespace std;
#include "atcoder/all"
using namespace atcoder;
#define int long long
#define REP(i, n) for (int i = 0; i < (int)n; ++i)
#define RREP(i, n) for (int i = (int)n - 1; i >= 0; --i)
#define FOR(i, s, n) for (int i = s; i < (int)n; ++i)
#define RFOR(i, s, n) for (int i = (int)n - 1; i >= s; --i)
#define ALL(a) a.begin(), a.end()
#define IN(a, x, b) (a <= x && x < b)
template<class T>istream&operator >>(istream&is,vector<T>&vec){for(T&x:vec)is>>x;return is;}
template<class T>inline void out(T t){cout << t << "\n";}
template<class T,class... Ts>inline void out(T t,Ts... ts){cout << t << " ";out(ts...);}
template<class T>inline bool CHMIN(T&a,T b){if(a > b){a = b;return true;}return false;}
template<class T>inline bool CHMAX(T&a,T b){if(a < b){a = b;return true;}return false;}
constexpr int INF = 1e18;

template <typename T>
struct SegmentTree{
  using F = function<T(T,T)>;
  int n;
  F f;
  T ti;
  vector<T> dat;

  SegmentTree(){}
  SegmentTree(F f,T ti):f(f),ti(ti){}

  void init(int n_){
	n=1;
	while(n<n_) n<<=1;
	dat.assign(n<<1,ti);
  }

  void build(const vector<T> &v){
	int n_=v.size();
	init(n_);
	for(int i=0;i<n_;i++) dat[n+i]=v[i];
	for(int i=n-1;i;i--)
	  dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }

  void set_val(int k,T x){
	dat[k+=n]=x;
	while(k>>=1)
	  dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);
  }

  T query(int a,int b){
	if(a>=b) return ti;
	T vl=ti,vr=ti;
	for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
	  if(l&1) vl=f(vl,dat[l++]);
	  if(r&1) vr=f(dat[--r],vr);
	}
	return f(vl,vr);
  }

  template<typename C>
  int find(int st,C &check,T &acc,int k,int l,int r){
	if(l+1==r){
	  acc=f(acc,dat[k]);
	  return check(acc)?k-n:-1;
	}
	int m=(l+r)>>1;
	if(m<=st) return find(st,check,acc,(k<<1)|1,m,r);
	if(st<=l&&!check(f(acc,dat[k]))){
	  acc=f(acc,dat[k]);
	  return -1;
	}
	int vl=find(st,check,acc,(k<<1)|0,l,m);
	if(~vl) return vl;
	return find(st,check,acc,(k<<1)|1,m,r);
  }

  template<typename C>
  int find(int st,C &check){
	T acc=ti;
	return find(st,check,acc,1,0,n);
  }
  //アウトの条件を渡す
};

signed main(){
	int N, K;
	cin >> N >> K;
	vector<int>a(N);
	cin >> a;
	SegmentTree<int>seg([](int a, int b){return max(a, b);}, 0);
	seg.build(vector<int>(300030));
	REP(i, N) {
		int l = max(0ll, a[i] - K);
		int r = min(300029ll, a[i] + K);
		int t = seg.query(l, r + 1);
		int pre = seg.query(a[i], a[i] + 1);
		seg.set_val(a[i], max(pre, t + 1));
	}
	out(seg.query(0, 300030));
}

Measured memory_bytes: 16232
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL mo=1e9+7;
const int N=1000;
int n,ok[N+10];
LL h[N+10],h2[N+1],f[N+10][N+10];
LL mul(LL x,LL y) {
    LL z=1;
    while (y) {
        if (y&1) z=z*x%mo;
        y>>=1;
        x=x*x%mo;
    }
    return z;
}
int main() {
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
        scanf("%lld",&h[i]);
        h2[i]=h[i];
    }
    sort(h2+1,h2+n+1);
    h2[0]=1;
    for (int i=n;i>=0;i--)
        if (i==n||h2[i]!=h2[i+1]) ok[i]=1;
    h2[n+1]=1e9;
    for (int i=0;i<=n;i++) {
        if (h2[i]>h[1]) break;
        if (!ok[i]) continue;
        if (h2[i+1]<=h[1]) f[1][i]=(mul(2,h[1]-h2[i])-mul(2,h[1]-h2[i+1]))*2%mo;
        else f[1][i]=mul(2,h[1]-h2[i])*2%mo;
    }
    for (int i=1;i<n;i++)
        for (int j=0;j<=n;j++) {
            if (f[i][j]==0) continue;
            if (h[i]<h[i+1]) {
                if (h2[j]==h[i])
                    for (int j2=j;j2<=n;j2++) {
                        if (!ok[j2]||h2[j2]>h[i+1]) continue;
                        LL now;
                        if (h2[j2+1]<=h[i+1])
                            now=f[i][j]*(mul(2,h[i+1]-h2[j2])-mul(2,h[i+1]-h2[j2+1]))%mo;
                        else now=f[i][j]*mul(2,h[i+1]-h2[j2])%mo;
                        f[i+1][j2]=(f[i+1][j2]+now*2)%mo;
                    }
                else f[i+1][j]=(f[i+1][j]+f[i][j]*mul(2,h[i+1]-h[i]))%mo;
                continue;
            }
            if (h2[j]>=h[i+1]) {
                int num=0;
                for (int j=n;j>=0;j--)
                    if (h2[j]==h[i+1]) {
                        num=j;
                        break;
                    }
                f[i+1][num]=(f[i+1][num]+f[i][j]*2)%mo;
            }
            else f[i+1][j]=(f[i+1][j]+f[i][j])%mo;
        }
    LL ans=0;
    for (int i=0;i<=n;i++)
        ans=(ans+f[n][i])%mo;
    ans=(ans%mo+mo)%mo;
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 768
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <numeric>

using namespace std;

/*-----------------------------------------------------------------------------
　定義
 -------------------------------------------------------------------------------*/
#define ALL(x)					(x).begin(),(x).end()
#define REP(i, n)				for (int (i) = 0 ; (i) < (ll)(n) ; ++(i))
#define REPN(i, m, n)			for (int (i) = m ; (i) < (ll)(n) ; ++(i))
#define INF						(int)2e9
#define MOD						(1000 * 1000 * 1000 + 7)
#define Ceil(x, n)				(((((x))+((n)-1))/n))		/* Nの倍数に切り上げ割り算 */
#define CeilN(x, n)				(((((x))+((n)-1))/n)*n)		/* Nの倍数に切り上げ */
#define FloorN(x, n)			((x)-(x)%(n))				/* Nの倍数に切り下げ */
#define IsOdd(x)				(((x)&0x01UL) == 0x01UL)			
#define IsEven(x)				(!IsOdd((x)))						
#define M_PI					3.14159265358979323846
typedef long long				ll;
typedef pair<ll, ll>			P;

/*-----------------------------------------------------------------------------
　処理
 -------------------------------------------------------------------------------*/
int main()
{
	ll N, H;
	cin >> N >> H;
	vector<P> p(2 * N);
	REP(i, N) {
		int a, b;
		cin >> a >> b;
		p[2 * i].first = a;
		p[2 * i].second = INF;
		p[2 * i + 1].first = b;
		p[2 * i + 1].second = 1;
	};
	sort(ALL(p));
	reverse(ALL(p));

	ll ans = 0;
	for (auto one : p) {
		ll damage = one.first * one.second;
		if (H <= damage) {
			ans += Ceil(H, one.first);
			break;
		}
		H -= damage;
		ans += one.second;
	}

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


Measured memory_bytes: 3328
import numpy as np
import math
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(): return list(imap())
def farr(): return list(fmap())
def sarr(): return sinput().split()

n = int(input())
A = iarr()
s = set(A)
if sum(A)==2*sum(s): print(pow(2, len(A)//2, int(1e9+7)))
else: print(0)


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

int main()
{
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    // vector<vector<bool>> isOk(h, vector<bool>(w, false));
    string ans = "Yes";

    for (auto i = 0; i < h; i++)
    {
        string str;
        cin >> str;
        s[i] = str;
    }

    for (auto i = 0; i < h; i++)
    {
        for (auto j = 0; j < w; j++)
        {
            if (s[i][j] == '#')
            {
                if (i > 0 && s[i - 1][j] == '#')
                {
                    // isOk[i][j] = true;
                    // isOk[i - 1][j] = true;
                    continue;
                }
                if (i < h - 1 && s[i + 1][j] == '#')
                {
                    // isOk[i][j] = true;
                    // isOk[i + 1][j] = true;
                    continue;
                }
                if (j > 0 && s[i][j - 1] == '#')
                {
                    // isOk[i][j] = true;
                    // isOk[i][j - 1] = true;
                    continue;
                }
                if (j < w - 1 && s[i][j + 1] == '#')
                {
                    // isOk[i][j] = true;
                    // isOk[i][j + 1] = true;
                    continue;
                }

                ans = "No";
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i , n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9;
using namespace std;
using ll = long long;
ll v[3000][3000] , mod = 1e9 + 7;
int main() {
    int n , k;
    cin >> n >> k;
	v[0][0] = 1;
	for(int i = 1; i <= n; i++){
		v[i][0] = 1;
		for(int j = 1; j <= i; j++){
			v[i][j] = (v[i - 1][j - 1] + v[i - 1][j]) % mod;
        }
	}
	for(int i = 1; i <= k; i++){
		cout << v[n - k + 1][i] * v[k - 1][i - 1] % mod << endl;
    }
	return 0;
}

Measured memory_bytes: 27184
import sys
input = sys.stdin.readline
import math
import itertools

def kyori(s,g):
    return math.sqrt( (s[0] - g[0])**2 + (s[1] - g[1])**2)

def average_length(pos,n):
    amount = 0
    count = 0
    for i in itertools.permutations(pos,n):
        for j in range(len(i)-1):
            amount += kyori(i[j],i[j+1])
        count += 1
    return amount/count

if __name__ == "__main__":
    n = int(input())
    pos = []

    for _ in range(n):
        x,y = map(int,input().split())
        pos.append((x,y))

    print(average_length(pos,n))


Measured memory_bytes: 3064
n = int(input())
s = input()
w = [0]*n
b = [0]*n
if s[0]=='.':
    w[0]=1
else:
    b[0]=1
for i in range(1,n):
    if s[i]=='.':
        w[i] = w[i-1]+1
        b[i] = b[i-1]
    else:
        w[i] = w[i-1]
        b[i] = b[i-1]+1
ans = min(w[-1],b[-1])
for i in range(n-1):
    ans = min(ans,w[-1]-w[i]+b[i])
print(ans)

Measured memory_bytes: 12808
#include <bits/stdc++.h>
#define rep(i, n) for (rint i = 1; i <= (n); i ++)
#define re0(i, n) for (rint i = 0; i < (int) n; i ++)
#define travel(i, u) for (rint i = head[u]; i; i = e[i].nxt)
#define rint register int
using namespace std;

typedef long long lo;

template<typename tp> inline void read(tp &x) {
    x = 0; char c = getchar(); int f = 0;
    for (; c < '0' || c > '9'; f |= c == '-', c = getchar());
    for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
    if (f) x = -x;
}
#define int long long

inline int calc(int x, int y, int z) {
	int l = x / 2, r = x - l;
	return (r - l) * y * z;
}

signed main(void) {
	int x, y, z;
	cin >> x >> y >> z;
	cout << min(calc(x, y, z), min(calc(y, x, z), calc(z, x, y))) << "\n";
}
				


Measured memory_bytes: 256