akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#define MAXN 20

using namespace std;
typedef long long ll;

string S;
int N, DP[MAXN][2], DP1[MAXN][2], DP2[MAXN][2], DP3[MAXN][2], k, aux, ans;
int DP4[MAXN][2], DP5[MAXN][2], DP6[MAXN][2];

int main ()
{
	cin >> S;
	N = S.length();
	for ( int i = N; i >= 0; i-- )
	{
		for ( int f = 0; f <= 1; f++ )
		{
			if ( i == N )
				DP[i][f] = 1;
			else
			{
				if ( f == 1 )
					DP[i][f] = DP[i + 1][f] * 3;
				else
				{
					if ( S[i] >= '3' )
						DP[i][f] += DP[i + 1][(S[i] > '3')];
					if ( S[i] >= '5' )
						DP[i][f] += DP[i + 1][(S[i] > '5')];
					if ( S[i] >= '7' )
						DP[i][f] += DP[i + 1][(S[i] > '7')];
				}
			}
		}
	}

	for ( int i = N; i >= 0; i-- )
	{
		for ( int f = 0; f <= 1; f++ )
		{
			if ( i == N )
				DP1[i][f] = 1;
			else
			{
				if ( f == 1 )
					DP1[i][f] = DP1[i + 1][f] * 2;
				else
				{
					if ( S[i] >= '3' )
						DP1[i][f] += DP1[i + 1][(S[i] > '3')];
					if ( S[i] >= '5' )
						DP1[i][f] += DP1[i + 1][(S[i] > '5')];
				}
			}
		}
	}

	for ( int i = N; i >= 0; i-- )
	{
		for ( int f = 0; f <= 1; f++ )
		{
			if ( i == N )
				DP2[i][f] = 1;
			else
			{
				if ( f == 1 )
					DP2[i][f] = DP2[i + 1][f] * 2;
				else
				{
					if ( S[i] >= '3' )
						DP2[i][f] += DP2[i + 1][(S[i] > '3')];
					if ( S[i] >= '7' )
						DP2[i][f] += DP2[i + 1][(S[i] > '7')];
				}
			}
		}
	}

	for ( int i = N; i >= 0; i-- )
	{
		for ( int f = 0; f <= 1; f++ )
		{
			if ( i == N )
				DP3[i][f] = 1;
			else
			{
				if ( f == 1 )
					DP3[i][f] = DP3[i + 1][f] * 2;
				else
				{
					if ( S[i] >= '5' )
						DP3[i][f] += DP3[i + 1][(S[i] > '5')];
					if ( S[i] >= '7' )
						DP3[i][f] += DP3[i + 1][(S[i] > '7')];
				}
			}
		}
	}

	for ( int i = N; i >= 0; i-- )
	{
		for ( int f = 0; f <= 1; f++ )
		{
			if ( i == N )
				DP4[i][f] = 1;
			else
			{
				if ( f == 1 )
					DP4[i][f] = DP4[i + 1][f];
				else
				{
					if ( S[i] >= '3' )
						DP4[i][f] += DP4[i + 1][(S[i] > '3')];
				}
			}
		}
	}

	for ( int i = N; i >= 0; i-- )
	{
		for ( int f = 0; f <= 1; f++ )
		{
			if ( i == N )
				DP5[i][f] = 1;
			else
			{
				if ( f == 1 )
					DP5[i][f] = DP5[i + 1][f];
				else
				{
					if ( S[i] >= '5' )
						DP5[i][f] += DP5[i + 1][(S[i] > '5')];
				}
			}
		}
	}

	for ( int i = N; i >= 0; i-- )
	{
		for ( int f = 0; f <= 1; f++ )
		{
			if ( i == N )
				DP6[i][f] = 1;
			else
			{
				if ( f == 1 )
					DP6[i][f] = DP6[i + 1][f];
				else
				{
					if ( S[i] >= '7' )
						DP6[i][f] += DP6[i + 1][(S[i] > '7')];
				}
			}
		}
	}

	ans += DP[0][0];
	for ( int i = 1; i < N; i++ )
		ans += DP[i][1];

	ans -= (DP1[0][0] + DP2[0][0] + DP3[0][0]);
	for ( int i = 1; i < N; i++ )
		ans -= (DP1[i][1] + DP2[i][1] + DP3[i][1]);
	
	ans += (DP4[0][0] + DP5[0][0] + DP6[0][0]);
	for ( int i = 1; i < N; i++ )
		ans += (DP4[i][1] + DP5[i][1] + DP6[i][1]);

	cout << ans + aux << "\n";
	return 0;
}


Measured memory_bytes: 256
N, M = map(int, input().split())
ACs = [False]*N
WAs = [0]*N
for i in range(M):
  sp, S = input().split()
  p = int(sp)-1
  if S == "AC":
    ACs[p] = True
  elif S == "WA":
    if not ACs[p]:
      WAs[p] += 1
r1 = 0
r2 = 0
for i in range(N):
  if ACs[i]:
    r1 += 1
    r2 += WAs[i]
print(r1, r2)


Measured memory_bytes: 4596
#define rep(i, n) for (int i = 0; i < (n); i++)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int MOD = 1000000007;
// MAX int 2,147,483,647
// MAX O(n) 10^18

int main() {
    int n;
    cin >> n;
    vector<int> p(n);
    rep(i, n) cin >> p.at(i);

    int count = 0;
    rep(i, n - 2) {
        if (p.at(i) < p.at(i + 1) && p.at(i + 1) < p.at(i + 2) ||
            p.at(i + 2) < p.at(i + 1) && p.at(i + 1) < p.at(i)) {
            count++;
        }
    }

    cout << count << endl;

    return 0;
}


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

typedef long long ll;
#define REP(i, n) for(int i=0;i<n;i++)
#define FOR(i, a, b) for(int i=a; i<b; i++)

int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	int p[m];
	REP(i, m){
		scanf("%d", p+i);
	}
	ll a[n-1], b[n-1], c[n-1];
	REP(i, n-1){
		scanf("%lld%lld%lld", a+i, b+i, c+i);
	}

	int d[n-1];
	fill(d, d+n-1, 0);
	REP(i, m-1){
		int x = p[i], y = p[i+1];
		if(x>y) swap(x, y);
		x--; y--;
		FOR(j, x, y){
			d[j]++;
		}
	}

	ll sum = 0;
	REP(i, n-1){
		sum += min(a[i]*d[i], b[i]*d[i]+c[i]);
	}
	printf("%lld\n", sum);
}

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

using namespace std;

#define REP1(i,n) for(int i=1, i##_len=(n); i<i##_len; ++i)
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pow(x) x*x
#define ll long long
static const ll MAX = 1000000;
static const ll INFTY = 1e12;
static const ll MOD = 1000000007;

template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };

struct edge {
    ll to, cost;
};

using Graph = vector<vector<int>>;
using _Graph = vector<vector<edge>>;


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

// 深さ優先探索
vector<bool> seen;
vector<int> colors;

int H, W, N;
int sx, sy, gx, gy; 
vector<vector<char>> field;
vector<vector<int>> dist;
//vector<pair<int, int>> gx, gy;
deque<pair<int, int>> que;

typedef vector<vector<int> > Matrix;

const int INF = 100000000;


int main() {

    ll K;
    cin >> K;
    ll ans = 0;

    REP1(i, K+1){
        REP1(j, K+1){
            REP1(k, K+1){
                ans += __gcd(__gcd(i, j), k);
            }
        }
    }

    cout << ans << endl;
 




}
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         pass System Test!
*/


Measured memory_bytes: 3632
while True:
    n, x = map(int, raw_input().split())
    cnt = 0
    if n == x == 0:
        break
    for i in range(1, n-1):
        for j in range(i+1, n):
            for k in range(j+1, n+1):
                if i + j + k == x:
                    cnt+=1
    print cnt



Measured memory_bytes: 4636
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repd(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)

int fact(int num, int cnt)
{
  if (num % 2 != 0)
    return cnt;

  cnt++;
  return fact(num / 2, cnt);
}

int main()
{

  int N;
  cin >> N;
  int a[N];

  int cnt = 0;
  rep(i, N)
  {
    cin >> a[i];
    cnt = fact(a[i], cnt);
  }

  cout << cnt;

  return 0;
}

Measured memory_bytes: 256
drawRect :: Int -> Int -> IO ()
drawRect 0 w = putStrLn ""
drawRect h w = do
  putStrLn . take w . repeat $ '#'
  drawRect (h-1) w

main = do
  l <- getLine
  let (h:w:_) = map read . words $ l
  if h == 0 && w == 0 then return ()
  else drawRect h w >> main

Measured memory_bytes: 4064
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	long long n, k, x = 0;
	cin >> n >> k;
	if (n==0)
	return 0;
	long long arr[1000000];
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	if (k>=n)
	{
	    cout <<"0";
	}
	else {
	    sort (arr,arr+n);
	for (int i = 0; i < n-k; i++) {
		x=x+arr[i];
	}
	cout<<x;
	    
	}
}


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

int main(void) {
  int d, g;
  cin >> d >> g;
  vector<int> p(d), c(d);
  rep(i, d)
    cin >> p.at(i) >> c.at(i);
  
  int ans = 10000;
  for (int tmp = 0; tmp < (1 << d); tmp++) {
    bitset<10> s(tmp);
    
    int score = 0;
    int solve = 0;
    rep(i, d) {
      if (s.test(i)) {
        score += (100 * (i + 1)) * p.at(i) + c.at(i);
        solve += p.at(i);
      }
    }
    
    bool fin = false;
    if (score >= g) {
      ans = min(ans, solve);
      continue;
    }
    else {
      for (int i = d - 1; i > -1; i--) {
        if (!s.test(i)) {
          rep(j, p.at(i) - 1) {
            score += 100 * (i + 1);
            solve++;
            if (score >= g) {
              ans = min(ans, solve);
              fin = true;
              break;
            }          
          }
        }
        
        if (fin)
          break;
      }
    }
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

n = getN()
INF = 100000000000
nums = [INF] + getList() + [INF]
ans = 0
for i, j in zip(nums, nums[1:]):
    ans += min(i, j)

print(ans)



Measured memory_bytes: 38256
#include<bits/stdc++.h>
#define mp make_pair
// #define pb push_back
#define ll long long
#define endl "\n"
using namespace std;

vector<vector<ll> > graph(100001);
ll dp[100001];


ll solve(ll i){
	if(graph[i].size()==0){
		return 0;
	}
	if(dp[i]!=-1){
		return dp[i];
	}
	vector<ll>::iterator it;
	dp[i]=0;
	ll ans=LLONG_MIN;
	for(it=graph[i].begin();it!=graph[i].end();it++){
		ans=max(ans,solve(*it));
	}
	dp[i]=ans+1;
	return dp[i];
}


int main() {
	ll n,m;
	cin>>n>>m;
	while(m--){
		ll x,y;
		cin>>x>>y;
		graph[x].push_back(y);
	}
	memset(dp,-1,sizeof(dp));
	for(int i=1;i<=n;i++){
		if(dp[i]==-1){
			ll x=solve(i);
		}
	}
	ll ans=0;
	for(ll i=1;i<=n;i++){
		ans=max(ans,dp[i]);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 12100
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
using namespace std;
long long MOD = 1e9 + 7;

int N;
string S;
int L[100000];
int R[100000];
int ans[100000];

int main() {
	cin >> S;
	N = S.size();
	for (int n = 0; n < N; n++) {
		if (S[n] == 'R')R[n] = n;
		else L[n] = n;
	}
	for (int n = 1; n < N; n++) {
		R[n] = max(R[n], R[n - 1]);
	}
	for (int n = N - 1; n >= 0; n--) {
		if (L[n] == 0)L[n] = L[n + 1];
	}
	for (int n = 0; n < N; n++)ans[n] = 0;
	for (int n = 0; n < N; n++) {
		if (S[n] == 'R') {
			int t = L[n] - n;
			if (t % 2 == 0)ans[L[n]]++;
			else ans[L[n] - 1]++;
		}
		else {
			int t = n - R[n];
			if (t % 2 == 0)ans[R[n]]++;
			else ans[R[n] + 1]++;
		}
	}
	for (int n = 0; n < N; n++) {
		cout << ans[n] << " ";
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 1792
package main

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

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func nextStr() string {
	sc.Scan()
	s := sc.Text()
	return s
}

func main() {
	sc.Split(bufio.ScanWords)
	N := nextInt()
	A := make([]int, N)
	for i := 0; i < N; i++ {
		A[i] = nextInt()
	}
	sort.Sort(sort.Reverse(sort.IntSlice(A)))
	larger := 0
	smaller := 0
	for i := 0; i+1 < N; i++ {
		if A[i] == A[i+1] {
			if larger == 0 {
				larger = A[i]
				i++
				continue
			}
			if smaller == 0 {
				smaller = A[i]
				break
			}
		}
	}

	fmt.Println(larger * smaller)
}


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

struct node{
  unsigned int key;
  struct node *next;
  struct node *prev;
};

typedef struct node * NodePointer;

NodePointer nil;

NodePointer listSearch(int key){
  NodePointer p = nil;
  while(1) {
    if(p->next == nil) return nil;
    
    p = p->next;
    if(p->key == key) return p;
  }
}

void init(){
  nil = malloc(sizeof(struct node));
  nil->next = nil;
  nil->prev = nil;
}

void printList(){
  NodePointer cur = nil->next;
  int isf = 1;
  while(1){
    if ( cur == nil ) break;
    if ( isf == 0)  printf(" ");
    printf("%d", cur->key);
    cur = cur->next;
    isf = 0;
  }
  printf("\n");
}

void rprintList(){
  NodePointer cur = nil->prev;
  int isf = 1;
  while(1){
    if ( cur == nil ) break;
    if ( isf == 0)  printf(" ");
    printf("%d", cur->key);
    cur = cur->prev;
    isf = 0;
  }
  printf("\n");
}

void deleteNode(NodePointer t){
  t->next->prev = t->prev;
  t->prev->next = t->next;
  free(t);
}

void deleteFirst(){
  NodePointer t = nil->next;
  if ( t == nil ) return;
  deleteNode(t);
}

void deleteLast(){
  NodePointer t = nil->prev;
  if ( t == nil ) return;
  deleteNode(t);
}

void delete(int key){
  NodePointer t = listSearch(key);
  if(t == nil) return;
  deleteNode(t);
}

void insert(int key){
  NodePointer x;
  x = malloc(sizeof(struct node));
  x->key = key;
  x->prev = nil;
  nil->next->prev = x;
  x->next = nil->next;
  nil->next = x;
}

int main(){
  int key, n, i;
  int size = 0;
  char com[20];
  int np = 0, nd = 0;
  scanf("%d", &n);
  init();
  for ( i = 0; i < n; i++ ){
    scanf("%s%d", com, &key);
    if ( com[0] == 'i' ) {insert(key); np++; size++;}
    else if ( com[0] == 'd' ) {
      if (strlen(com) > 6){
	if ( com[6] == 'F' ) deleteFirst();
	else if ( com[6] == 'L' ) deleteLast();
      } else {
	delete(key); nd++; 
      }
      size--;
    }
  }

  printList();
  return 0;
}

Measured memory_bytes: 31660
def divisors(n):
    ret=[]
    for i in range(1,int(n**0.5)+1):
        if n%i==0:
            ret.append(i)
            if i!=n//i:
                ret.append(n//i)
    return ret

mod=10**9+7    
n,k=map(int,input().split())
cnt=[0]*(k+1)
for i in range(k,1,-1):
    divs=divisors(i)
    cnt[i]+=pow(k//i,n,mod)
    for val in divs:
        if val==i:
            continue
        else:
            cnt[val]-=cnt[i]
cnt[1]+=pow(k,n,mod)
ans=0
for i in range(1,k+1):
    ans+=i*(cnt[i])%mod
    ans%=mod
print(ans)

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

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

	int n;
	cin >> n;

	for(int i = 0; i < n; ++i) {
		int y, m, d;
		cin >> y >> m >> d;

		int cnt = 0;
		for(int i = y; i < 1000; ++i) {
			for(int j = m; j <= 10; ++j) {
				const int limit = !(j & 1) && i % 3 > 0 ? 19 : 20;
				for(int k = d; k <= limit; ++k)
					++cnt;

				d = 1;
			}
			m = 1;
		}

		cout << cnt << endl;
	}

	return EXIT_SUCCESS;
}

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

bool water[33] , sugar[3333];
double mx = 1e9 , ans, su;

main()
{
	double  a , b , c , d , e , f;
	cin >> a >> b >> c >> d >> e >> f;
	double o = 100.0 / e;
	
	//cout << den << endl;
	
	water[0] = 1;
	sugar[0] = 1;
	
	
	for(int i = 1; i <= 33; i ++)if(water[ i - (int)a ] )water[i] = 1;
	for(int i = 1; i <= 33; i ++)if(water[ i - (int)b ] )water[i] = 1;
	for(int i = 1; i <= 3333;i++)if(sugar[ i - (int)c ] )sugar[i] = 1;
	for(int i = 1; i <= 3333;i++)if(sugar[ i - (int)d ] )sugar[i] = 1;
	
	
	
	
	for(int i = 1; i <= 33; i ++)
	{
		if( water[i] )
		{
			
			for(int j = 1; j <= 3333; j ++)
			{
					if( sugar[j] )
				{
							if( i * 100 + j <= f )
					{
								if( o * j <= (i * 100) && i*100 - o*j < mx)
								{
									mx = i*100 - o*j;
									ans = i*100 + j;
									su = j;
								}
								
					}
						
				}
			}
		}
	}
	
	if(ans != 0)
	cout << ans << " " << su << endl;
	else
	cout << 100 * a << " " << 0;
	
	
	
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <functional>
#include <set>
#include <vector>
#include <array>

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

using namespace std;

class TimePoint {
public:
    int t = 0, x = 0, y = 0;

    TimePoint() { t = 0; x = 0, y = 0; };
    TimePoint(int t0, int x0, int y0) {
        t = t0, x = x0, y = y0;
    }
    int distance (const TimePoint &another) {
        return abs(x - another.x) + abs(y - another.y);
    }
    bool possible (const TimePoint &another) {
        int d = distance(another);
        int dt = abs(t - another.t);

        bool can = true;
        if (dt < d) { can = false; };
        if (dt % 2 != d % 2) { can = false; };
        return can;
    }
    bool operator<(const TimePoint &another) {
        return t < another.t;
    }
};

int main() {
    int n, t, x, y;

    scanf("%d", &n);
    vector<TimePoint> v;
    v.emplace_back(0, 0, 0);
    r(i, n) {
        scanf("%d %d %d", &t, &x, &y);
        auto tp = TimePoint(t, x, y);
        v.push_back(tp);
    }
    sort(v.begin(), v.end());

    bool possible = true;
    for(int i = 1; i < (n + 1); i++) {
        possible = v[i].possible(v[i-1]);
        if(!possible)
            break;
    }

    printf(possible ? "Yes" : "No");

    return 0;
}

Measured memory_bytes: 1912
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
  int n,k;
  cin>>n>>k;
  int ar[n];
  for(int i=0;i<n;i++)cin>>ar[i];
  int dp[n];
  dp[0]=0;;
  for(int i=1;i<n;i++)
  {
      dp[i]=INT_MAX;
      for(int j=1;j<=k;j++)
      {
        if(i-j>=0)  
        dp[i]=min(dp[i-j]+abs(ar[i-j]-ar[i]),dp[i]);
        else
        break;
      }
  }
 // for(int i=0;i<n;i++)
  cout<<dp[n-1]<<"\n";
    return 0;
}

Measured memory_bytes: 1024
fun main(args: Array<String>) {
    val tiles = readLine()!!
    val l = tiles.length

    var b = Array(l){'0'}
    var w = Array(l){'1'}
    for (i in 0 until l){
        if(i % 2 == 0){
            b[i] = '0'
            w[i] = '1'
        }else{
            b[i] = '1'
            w[i] = '0'
        }
    }

    var bc = 0
    var wc = 0

    tiles.forEachIndexed { index, c ->
        if(c != b[index]){
            bc++
        }

        if(c != w[index]){
            wc++
        }
    }

    println(Math.min(bc, wc))
}


Measured memory_bytes: 36272
n=int(input())
a=[int(i) for i in input().split()]
b=[None for i in range(n)]
if n==0:
    if a[0]==1:
        print(1)
    else:
        print(-1)
else:
    a.reverse()
    for i in range(n):
        b[i]=(a[i]+1)//2
        a[i+1]+=b[i]
    if a[-1]>1:
        print(-1)
    else:
        a.reverse()
        b.reverse()
        b.append(0)
        res=a[n]
        ma=[100000000000000000000 for i in range(n+1)]
        ma[0]=1
        for i in range(1,n+1):
            ma[i]=min((ma[i-1]-a[i-1]+b[i-1])*2,ma[i])
        for i in range(n-1,-1,-1):
            a[i]=min(ma[i],a[i+1]+a[i]-b[i])
            res+=a[i]
        print(res)


Measured memory_bytes: 89904
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

pub fn read_n<T: FromStr>(n: usize) -> Vec<T> {
    read_n_logic::<T>(n, vec![])
}

pub fn read_n_logic<T: FromStr>(n: usize, mut a: Vec<T>) -> Vec<T> {
    match n {
        0 => a,
        _ => {
            a.push(read::<T>());
            read_n_logic(n - 1, a)
        }
    }
}
use std::cmp::{max, min};
use std::collections::BinaryHeap;
use std::collections::VecDeque;

fn main() {
    let n: usize = read();
    let m: usize = read();
    let mut a: Vec<usize> = read_n(n);
    let sum: usize = a.iter().sum();
    a.sort();
    a.reverse();
    if a[m - 1] < (sum as f64 / (4.0 * m as f64)).ceil() as usize {
        println!("{}", "No")
    } else {
        println!("{}", "Yes")
    }
}


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

int main() {
	int i;
	int j;
	int N;
	int K;
	int q;
	int q11;
	int q22;
	long long p;
	long long p1;
	long long p2;
	long long p3;
	long long p4;
   
	cin >> N >> K;
	int a[N];
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
    sort(a, a + (N), greater<int>());  // a[0:N] を大きい順にソート
  	if (K==1){
		cin >> a[0];
 		p=1000000007;
      	p+=a[0];
		p=p%1000000007;
		cout << p << endl;
      return 0;
    }
	if (((K%2)==1)&&(a[0]<=0)){
		p=1;
		for(int i=0;i<K;i++){
			p*=a[i];
			p=p%1000000007;
		}
		p+=1000000007;
		p=p%1000000007;
		cout << p << endl;
		return 0;
	}
	q=0;
	q11=(K%2);
	q22=N-1;
	for(int i=(K%2);i<K;i++){
		if(a[q11]>-a[q22]) {
			q11++;
		} else {
			q22--;
			q++;
		}
	}
 	if ((q%2)==1){
 		p1=a[q11-1];
		p2=a[q11];
		p3=a[q22];
		p4=a[q22+1];
		if(p1*p2<p3*p4) {
			q11--;
			q22--;
		} else {
			q11++;
			q22++;
		}
	}
  	p=1;
	while (q11 > 0) {
		q11--;
		p*=a[q11];
		p=p%1000000007;
	}
	while (q22 < N-1) {
		q22++;
		p*=a[q22];
		p=p%1000000007;
	}
	p+=1000000007;
	p=p%1000000007;
	cout << p << endl;
	return 0;
}


Measured memory_bytes: 4384
#include<stdio.h>
#define N 36
typedef struct{
  char suit;
  char value;
}Card;

main(){
  Card C1[N], C2[N], change;
  int i, j, k, mini;
  char ch;
  scanf("%d%c", &k, &ch);
  for(i = 0;i < k;i++){
    scanf("%c%c%c", &C1[i].suit, &C1[i].value, &ch);
    C2[i] = C1[i];
  }
  for(i = 0;i < k;i++){
    for(j = k-1;j > i;j--){
      if(C1[j].value < C1[j-1].value){
	change = C1[j];
	C1[j] = C1[j-1];
	C1[j-1] = change;
      }
    }
  }
  for(i = 0;i < k-1;i++){
    printf("%c%c ", C1[i].suit, C1[i].value);
  }
  printf("%c%c\nStable\n", C1[k-1].suit, C1[k-1].value);
  
  for(i = 0;i < k;i++){
    mini = i;
    for(j = i;j < k;j++){
      if(C2[j].value < C2[mini].value){
	mini = j;
      }
    }
    if(mini != i){
      change = C2[i];
      C2[i] = C2[mini];
      C2[mini] = change;      
    }
  } 
  for(i = 0;i < k-1;i++){
    printf("%c%c ", C2[i].suit, C2[i].value);
  }
  printf("%c%c\n", C2[k-1].suit, C2[k-1].value);
  for(i = 0;i < k;i++){
    mini = 0;
    if(C1[i].suit != C2[i].suit){
      printf("Not stable\n");
      mini++;
      break;
    }
    else if(i == k-1&&mini == 0){
      printf("Stable\n");
    }
  }
  return 0;
}

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

namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            int n, k;
            {
                var val = Console.ReadLine().Split(' ');
                n = int.Parse(val[0]);
                k = int.Parse(val[1]);
            }
            var h = new int[n];
            {
                var val = Console.ReadLine().Split(' ');
                for (int j = 0; j < n; j++)
                {
                    h[j] = int.Parse(val[j]);
                }
            }

            int r = 0;
            foreach (int i in h)
            {
                if (i >= k) r++;
            }

            Console.Write(r);

        }
    }
}


Measured memory_bytes: 15968
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e15;

#include <math.h>
#define PI 3.14159265358979323846264338327950L
const int mxN = 1e9 + 7;


int main() {
    int n, m;
    cin >> n >> m;
    vector<bool> d(100001);
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        d[x] = true;
    }
    int cnt = 0;
    bool ok = true;
    for (int i = 1; i <= n; i++) {
        if (d[i]) cnt++;
        else cnt = 0;
        if (cnt >= 2) ok = false;
    }
    if (!ok) {
        cout << 0;
        return 0;
    }
    vector<long long> dp(100001);
    if (!d[1]) dp[1] = 1;
    if (!d[2]) {
        if (d[1]) dp[2] = 1;
        else dp[2] = 2;
    }
    for (int i = 3; i <= n; i++) {
        if (dp[i - 1] == 0) {
            dp[i] = dp[i - 2];
            continue;
        }
        else {
            if (!d[i]) dp[i] = dp[i - 1] + dp[i - 2];
        }
        dp[i] %= MOD;
    }
    cout << dp[n] % MOD;
    
    return 0;
}

Measured memory_bytes: 3956
#define DEBUG
#include <bits/stdc++.h>
#include <ext/numeric>
using namespace std; using __gnu_cxx::power;
using ll = long long; using ull = unsigned long long; using ld = long double;
const ll llinf = (1ll<<61)-1; const double eps = 1e-6, ldeps = 1e-9;
#define all(x) begin(x), end(x)
#define sl(a) int(strlen(a))
#define sz(a) int(a.size())
#define TCC template<class C
struct Dbg { static constexpr auto &os = cout;   // replace by cerr in interactive.
#define ENI typename enable_if<
#define DTOR , Dbg&>::type operator<<
#define RIS return *this
TCC> static auto o(C *x)->decltype(os << *x, 0);
TCC> static char o(...);
TCC> ENI sizeof o<C>(0)!=1 DTOR(const C &x) {os<<x; RIS;}
TCC> Dbg &dump(C b, C e) {
    int ii = 0;
    for(C i = (os << "\n[", b); i!=e and ii<26; i++, ii++) *this << ", "+2*(i==b) << *i;
    RIS << ']';
}
TCC> ENI sizeof o<C>(0)==1 DTOR(const C &x) {
    return dump(all(x));
}
TCC, size_t X> ENI !is_same<C, const char>::value DTOR(C (&x)[X]) {
    return dump(all(x));
}
TCC, class D> Dbg &operator<<(const pair<C, D> &x) {RIS<<'{'<<x.first<<", "<<x.second<<'}';}
Dbg &operator<<(ostream&(*x)(ostream&)) { os << x; RIS; }
} dbg;
void err(istringstream *iss) { delete iss; }
TCC, class... Args> void err(istringstream *iss, const C &val, const Args &... args) {
    string name; *iss >> name; if (name.back()==',') name.pop_back();
    dbg << name << " = " << val << "; ", err(iss, args...);
}
#ifdef DEBUG
#define bug(args...) dbg << __LINE__ << ": ", err(new istringstream(#args), args), dbg << endl
#else
#define bug(args...) 0
#endif
#define ASSERT(a, o, b, args...) if (!((a)o(b))) bug(a, b, ##args), assert((a)o(b));
int T = 1, Q, cn;
const int inf = 1000000007, mxn = 200005;

int n,K,a[mxn];

signed main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); cout.precision(11), cout.setf(ios::fixed);
    // cin >> T;
    auto inputAll = [&]()->void {
        
    };
    auto kase = [&]()->void {
        // cout << "Case " << cn << ": ";
        cin>>n>>K;
        for(int i=1;i<=n;i++)cin>>a[i];
        int lo=1,hi=inf-7,mid,ans=-1;
        while(lo<=hi){
            mid=(lo+hi)>>1;
            ll mincut=0;
            for(int i=1;i<=n;i++)mincut+=(a[i]-1)/mid;
            if(mincut<=K)ans=mid,hi=mid-1;
            else lo=mid+1;
        }
        cout<<ans<<'\n';
    };
    auto resetAll = [&]()->void {
        
    };
    while (cn++!=T) inputAll(), kase(), resetAll();
}


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

public class Main {
    public static void main(String[] args) throws Exception {
        FastReader sc = new FastReader();
        int n=sc.nextInt();
        Set<String> s=new HashSet<>();
        for (int i=0;i<n;i++)s.add(sc.next());
        System.out.println(s.size());
    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

Measured memory_bytes: 66432
import java.util.Scanner;

class Main{
	public static void main(String[] args){
		Scanner stdIn = new Scanner(System.in);
		int a = stdIn.nextInt();
		int b = stdIn.nextInt();
		int c = stdIn.nextInt();
		int d = stdIn.nextInt();
		int train_min = a;
		int bus_min = c;
		if(train_min > b)
			train_min = b;
		if(bus_min > d)
			bus_min = d;
                int ans = train_min + bus_min;
		System.out.println(ans);
	}
}

Measured memory_bytes: 22868
#include <stdio.h>
#include <string.h>

int main(void){
    char str1[200], str2[100], str3[100];

    scanf("%s", &str1);
    scanf("%s", &str2);

    //str１をstr３にコピー
    strcpy(str3, str1);

    //str1とstr3を結合
    strcat(str1, str3);
    //printf("%s\n", str1);

    //str1とstr2を比較
    if (strstr(str1, str2) == NULL){
        printf("No\n");
    } else {
        printf("Yes\n");
    }

    return (0);
}


Measured memory_bytes: 2688
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
typedef long long int64;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
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; }
int dx[] = { 0, 0, -1, 1 };
int dy[] = { 1, -1, 0, 0 };


int power(int n) {
	int y = 1;
	rep(i, n) {
		y *= 10;
	}
	return y;
}

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

	int N, M;
	int number = 0;
	cin >> N;
	cin >> M;

	vi vecs;
	vi vecc;
	int s, c;
	rep(i, M) {
		cin >> s >> c;
		if (N != 1 && s == 1 && c == 0) {
			dame;
		}
		vecs.push_back(s);
		vecc.push_back(c);
	}
	rep(i, M) {
		rep(j, M) {
			if (i == j)continue;
			if (vecs.at(i) == vecs.at(j) && vecc.at(i) == vecc.at(j)) {
				vecs.at(j) = 0;
				vecc.at(j) = 0;
			}
			if (vecs.at(i) == vecs.at(j) && vecc.at(i) != vecc.at(j)) {
				dame;
			}
		}
	}

	rep(i, M) {
		number += power(N - vecs.at(i)) * vecc.at(i);
	}
	if (N == 1 && number == 0) {
		cout << 0;
		return 0;
	}
	if (number < power(N - 1)) {
		number += power(N - 1);
	}
	cout << number;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <vector>
#include <list>
#include <unordered_set>
#include <set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <cassert>
#include <cmath>
#include <algorithm>
#include <stdlib.h>
#include <stdio.h>
#include <fstream>
#include <tuple>

//....................................................................................................................//

using std::cin;
using std::cout;
using std::vector;
using std::list;
using std::unordered_set;
using std::set;
using std::map;
using std::unordered_map;
using std::multimap;
using std::unordered_multimap;
using std::pair;
using std::make_pair;
using std::min;
using std::max;
using std::swap;
using std::stack;
using std::deque;
using std::queue;
using std::ios_base;
using std::ifstream;
using std::ofstream;
using std::string;
using std::tuple;
using std::make_tuple;
using std::get;
using std::upper_bound;
using std::lower_bound;
using std::max_element;
using std::min_element;
using std::multiset;
using std::greater;
using std::priority_queue;
using std::less;

//....................................................................................................................//

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned long ul;

[[maybe_unused]] const string endl = "\n";
[[maybe_unused]] const string sep = " ";
[[maybe_unused]] const string yes = "YES\n";
[[maybe_unused]] const string no = "NO\n";
[[maybe_unused]] const string ng = "NG\n";
[[maybe_unused]] const string ok = "OK\n";
[[maybe_unused]] const double pi = acos(-1);
[[maybe_unused]] const ull modular = 998244353;

//....................................................................................................................//


int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    cout.precision(15);
    int a, b, h, m;
    cin >> a >> b >> h >> m;
    double angle_for_minute = pi * m / 30;
    double angle_for_hour = (60 * h + m) * pi / 360;
    cout << sqrt(a * a + b * b - 2 * a * b * cos(angle_for_hour - angle_for_minute));
}


Measured memory_bytes: 3616
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>

#define Rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define Sort(a) sort(a.begin(), a.end())
#define Reverse(a) reverse(a.begin(), a.end())

#define eb emplace_back
#define dbg(x) cout<<#x" = "<<((x))<<endl
#define fs first
#define sc second
     
using namespace std;
     
     
typedef long long ll;
typedef pair<ll, ll> P;
     
     
int main(){
  ll N;

  cin >> N;

#ifdef DEBUG
  cout << "N=" << endl;
#endif

  ll arr[N];
  ll max = 0;
  ll max2 = 0;
  int max_index = 0;
  for(int i = 0; i < N; i++){
    cin >> arr[i];
    if(arr[i] > max){
      max2 = max;
      max = arr[i];
      max_index = i;
    } else if (arr[i] > max2){
      max2 = arr[i];
    }
  }

  for(int i = 0; i < N; i++){
    if(i == max_index) cout << max2 << endl;
    else cout << max << endl;
  }
  
  return 0;
}


Measured memory_bytes: 3200
#include <iostream>
#include <cmath>
using namespace std;
int dist[100001];
int distC[100001];
int moving[100000];
int pm(int value){
	if(value<0)
	return -1;
	else
	return 1;
}
int main() {
	// your code goes here
	int n,m,now=1,sum=0;
	cin >> n >> m;
	for(int i=2;i<=n;i++){
	cin >> dist[i];
	distC[i]=distC[i-1]+dist[i];
	}
	for(int i=0;i<m;i++){
	cin >> moving[i];
	int a=now;
	now+=moving[i];
	int b=min(now,a);
	a=max(now,a);
	sum=(sum+distC[a]-distC[b])%100000;
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 2332
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pint = pair<int,  int>;
using pll = pair<ll, ll>;
using edge = pair<int, ll>;
using Graph = vector<vector<int>>; 
using WeightedGraph = vector<vector<edge>>;
const ll INF = 1LL << 60;
const int INF32 = 1 << 29;
const ll MOD = 1000000007;

int main(){
  int a,b;cin >> a >> b;
  string ans = "Impossible";
  if(a%3==0||b%3==0||(a+b)%3==0){
    ans = "Possible";
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define bit(n,m)(((n)>>(m))&1)
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p)pom(a,p-2,p)

ll n,a,b,c,d;
char s[200010];
int main(){
	scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d);
	a--,b--,c--,d--;
	scanf("%s",s);
	ll flag=1;
	if(c>d){
		//入れ替わる
		//現在から移動できる範囲内に空きが3連続必要
		flag=0;
		rep(i,b,d+1)if(s[i-1]=='.'&&s[i]=='.'&&s[i+1]=='.')flag=1;
	}
	//それぞれの移動経路に#が連続する箇所だあったらダメ
	rep(i,a,c)if(s[i]=='#'&&s[i+1]=='#')flag=0;
	rep(i,b,d)if(s[i]=='#'&&s[i+1]=='#')flag=0;
	puts(flag?"Yes":"No");
}

Measured memory_bytes: 384
#include<iostream>
using namespace std;
int main()
{
    // 整数の入力
    int N;
    cin >> N;

    int maxdig = 10000000;
    for(int i=1;i<N;i++){//1からN-1まで
        int diga = i%10 + (i/10)%10 + (i/100)%10 + (i/1000)%10 + (i/10000)%10 + (i/100000)%10;

        int b=N-i;
        int digb = b%10 + (b/10)%10 + (b/100)%10 + (b/1000)%10 + (b/10000)%10 + (b/100000)%10;
        if (diga + digb < maxdig)maxdig = diga + digb;
    }


    // 出力
    cout << maxdig << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/*---define tricks---*/
#define ALL(v) v.begin(),v.end()
#define UN(v) sort(ALL(v)),v.erase(unique(ALL(v)),v.end())
#define FILL(x,y) memset(x,y,sizeof(x))
#define EACH(v,it) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define FIO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define revsort(b,e) sort(b,e),reverse(b,e)
/*---define types---*/
typedef long long ll;
typedef unsigned int uint;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
/*---define variables---*/
int n;
ll a[100005];
ll ans;
/*---define function---*/

/*---main code---*/
int main()
{
	FIO;
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>a[i];	
	}
	for(int i=1;i<=n;++i)
	{
		ans+=a[i]/2ll;
		a[i]%=2;
		if(a[i]==1&&a[i+1]>0)
		{
			++ans;
			a[i+1]--;
			a[i]=0;
		}
	}
	cout<<ans<<'\n';
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>

using namespace std;
using ll = long long;

int gcd(int a, int b) { return (b == 0) ? a : gcd(b, a % b); }

#define CIN(T, x) T x; cin >> x;
#define CINS(T, x, N) vector<T> x(N); for(int i = 0; i < (N); i++) { cin >> x[i]; }
#define SHOW(x) for(int i = 0; i < x.size(); i++) { cout << x[i] << " "; } cout << "\n";
#define SHOW2(x) for(int j = 0; j < x.size(); j++) { SHOW(x[j]); } cout << "\n";

vector<int> wb(1e5, -1);

struct node {
    int to;
    int dist;
};
vector<node> d[100000];

void dfs(int v) {
    while(!d[v].empty()) {
        node node;
        node = d[v].back();
        d[v].pop_back();
        if (wb[node.to] > -1) continue;

        if ( node.dist % 2 == 0 ) {
            wb[node.to] = wb[v];
        } else {
            wb[node.to] = 1- wb[v];
        }
        dfs(node.to);
    }
    return ;
}


int main() {

    CIN(int, N);

    for (int i = 0; i < N - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;

        node node;
        node.dist = w;
        node.to = v;
        d[u].push_back(node);

        node.to = u;
        d[v].push_back(node);
    }

    wb[0] = 0;
    dfs(0);

    for (int i = 0; i < N; i++) {
        cout << wb[i] << "\n";
    }
    return 0;
}

Measured memory_bytes: 7552
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vvi vector<vector<int>> 
#define vi vector<int> 
#define vpii vector<pair<int,int>> 
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define ffor(i,n) for(int i = 0; i < n; ++i)
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    string s,t;
    cin >> s >> t;
    int n1 = s.length(),n2 = t.length();
    vvi dp(n1 + 1,vi(n2 + 1));
    for(int i = 1; i <= n1; ++i)
    {
        for(int j = 1; j <= n2; ++j)
        {
            if(s[i - 1] == t[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else
            {
                dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
            }
        }
    }
    string ans;
    int i = n1,j = n2;
    while(i > 0 && j > 0)
    {
        if(dp[i][j] > dp[i - 1][j] && dp[i][j] > dp[i][j - 1])
        {
            ans += s[i - 1];
            --i,--j;
        }
        else if(dp[i - 1][j] > dp[i][j - 1])
        {
            --i;
        }
        else
        {
            --j;
        }
    }
    reverse(all(ans));
    cout << ans;
}

Measured memory_bytes: 70784
line = input().split()
N = int(line[0])
M = int(line[1])
broken = []
count = 0
step = []
def check(value):
  if count < M:
    return broken[count]==value
  else:
    return False
for i in range(M):
  a = int(input())
  broken += [a]
if check(1):
  step+=[0]
  count += 1
else:
  step +=[1]
if check(2):
  step += [0]
  count += 1
else:
  step += [1+step[0]]
for j in range(2, N):
  if check(j+1):
    step += [0]
    count += 1
  else:
    step += [step[j-2]+step[j-1]]
ans = step[N-1]%(10**9+7)
print(ans)


Measured memory_bytes: 470920
#include <iostream>
#include <stack>
#include <cstring>
#include <algorithm>
#include <vector> 
#include <map>
#include <string>
using namespace std;
int a[100001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	int i = a[n / 2];
	int j = a[n / 2 - 1];

	int ans = 0;
	for (int k = j+ 1; k <= i; k++) {
		ans++;
	}
	cout << ans << '\n';



}

Measured memory_bytes: 768
/**
*	  Name: Ajay
*	  Institute: IIITH 
*/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <deque>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <string.h>
#define ll long long
#define inf 0x7fffffff
#define mod 1000000007
#define pb push_back
#define ppi pair<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vii vector<ppi>
#define vll vector<ll>
#define mp make_pair
#define fi first
#define se second
using namespace std;

void fastio()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}
void input()
{
  #ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  #endif
}

int check(int a[],int b[],int n){

	for(int i=0;i<n;i++){
		if(a[i]!=b[i])
			return -1;
	}
	return 1;
}

int main()
{      
  fastio();
  int n,m,i,j,t;
  cin>>n;
  int b[n],c[n];
  for(i=0;i<n;i++)
  	cin>>b[i];
  for(i=0;i<n;i++)
  	cin>>c[i];
  int a[n];
  for(int i=0;i<n;i++)
  	a[i]=i+1;
  int cnt=1,f,s;
  do{
  	int r=check(a,b,n);
  	if(r==1)
  	{
  		f=cnt;
  		break;
  	}
  	cnt++;
  }while(next_permutation(a,a+n));
  cnt=1;
  sort(a,a+n);
  do{
  	int t=check(a,c,n);
  	if(t==1)
  	{
  		s=cnt;
  		break;
  	}
  	cnt++;
  }while(next_permutation(a,a+n));

  cout<<abs(f-s);
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>

using namespace std;

int gcd(int a, int b) {
	if (b == 0) {
		return a;
	} else {
		return gcd(b, a % b);
	}
}

int main() {
	int n;
	cin >> n;

	long long result = 0;
    
    for (int i = 1; i <= n; i++) {
    	for (int j = 1; j <= n; j++) {
    		for (int k = 1; k <= n; k++) {
    			result += gcd(gcd(i, j), k);
    		}
    	}
    }

    cout << result << endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)

int main(){
  int n, k;
  cin >> n >> k;

  ll x[n];

  int p = - 1;

  REP(i, n){
    cin >> x[i];
    if(x[i] < 0) p = i;
  }

  ll T[k], S[k];

  REP(i, k){
    T[i] = -1;
    S[i] = -1;
  }

  if(p == - 1) cout << x[k - 1];
  else if(p == n - 1) cout << - x[n - k];
  else{
    for(int i = 1; i <= k; i++){
      if(p + i <= n - 1 && p - (k - i) + 1 >= 0){
        T[i - 1] = 2 * x[p + i] - x[p - (k - i) + 1];
      }
      if(p + k - i <= n - 1 && p - i + 1 >= 0){
        S[i - 1] = - 2 * x[p - i + 1] + x[p + k - i];
      }
    }

    SORT(T, k);
    SORT(S, k);

    ll anst, anss;

    REP(i, k){
      if(T[i] >= 0){
        anst = T[i];
        break;
      }
    }

    REP(i, k){
      if(S[i] >= 0){
        anss = S[i];
        break;
      }
    }

    if(anst < anss) cout << anst;
    else cout << anss;
  }


}


Measured memory_bytes: 2560
import math
a,b,x=map(int,input().split())
S=x/a
if S<=a*b/2:
    h=2*S/b
    answer=math.degrees(math.atan(b/h))
    print(answer)
else:
    T=a*b-S
    h=2*T/a
    answer=math.degrees(math.atan(h/a))
    print(answer)
    

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1000000007;

int main()
{
	ll n, k;
	cin >> n >> k;

	if (n > k) {
		ll r1 = n % k;
		ll q = n / k;
		ll r2 = k * (q + 1) % n;
		cout << (r1 < r2 ? r1 : r2) << endl;
	}
	else if (n == k) cout << 0 << endl;
	else {
		double tmp = k / 2;
		if (n <= k / 2) cout << n << endl;
		else cout << k - n << endl;
	}
}

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

int main(){
    int N;
    int A[101];
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> A[i];
    sort(A, A + N, greater<int>());
    int Alice=0;
    int Bob = 0;
    for(int i = 0; i<N;++i){
        if(i%2==0){
            Alice += A[i];
        }else{
            Bob +=A[i];
        }
    }
    int t =0;
    t = Alice - Bob;
    cout << t << endl;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main () {

        int H,W;
        cin >> H >> W;
        while (H || W) {
                for (int i = 0; i < H; i++) {
                        for (int j = 0; j < W; j++) {
                                if ((i ^ j) & 1) {
                                        cout << ".";
                                } else {
                                        cout << "#";
                                }
                        }
                        if (W > 0) {
                                cout << endl;
                        }
                }
                cout << endl;
                cin >> H >> W;
        }

        return 0;

}

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

#define mod 1000000007

#define INF 100000000

int main() {
    // oh hi mark
    string s; cin >> s;
    int n = s.size();
    long long ans = 0;
    for(int i = 0; i < n; i++) {
        if(s[i] == '>') {
            long long cnt = 0;
            for(i = i; i < n; i++) {
                
                if(s[i] == '>') {
                    cnt++;
                    continue;
                }
                break;
            }
            
            i--;
           // cout << "cnt " << cnt << endl;
            ans += (cnt) * (cnt + 1) /2;
        }else{
            long long cnt1 = 0;
            for(; i < n; i++) {
                
                if(s[i] == '<') {
                    cnt1++;
                    continue;
                }
                break;
            }
            long long cnt2 = 0;
            for(; i < n; i++) {
                
                if(s[i] == '>') {
                    cnt2++;
                    continue;
                }
                break;
            }
            i--;
            long long mx = max(cnt1, cnt2);
          //  cout << mx << " max " << cnt1 << " " << cnt2 << endl;
            cnt1--;
            cnt2--;
            ans += (cnt1)*(cnt1+1)/2;
            ans += (cnt2)*(cnt2+1)/2;
            ans += mx;
        }


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


Measured memory_bytes: 900
fn main() {
    let x: u64 = read();

    for n in x..100004 {
        let mut check = false;
        for i in 2..n - 1 {
            if n % i == 0 {
                check = true;
                break;
            }
        }
        if !check {
            println!("{}", n);
            return;
        }
    }
}

use std::io::stdin;
use std::io::Read;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let cin = stdin();
    let cin = cin.lock();
    let token: String = cin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}


Measured memory_bytes: 4352