akhauriyash/Code-Regression huggingface dataset:
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

ans = 0

# 再帰で書くと遅い

# def bin_search(li_sorted, val):
#     global ans
#     m = len(li_sorted)
#     l = int(m / 2)
#     if val == li_sorted[l]:
#         ans += 1
#     elif m > 1:
#         li_left = li_sorted[:l]
#         li_right = li_sorted[l:]
#         bin_search(li_left, val)
#         bin_search(li_right, val)


# for i in range(q):
#     bin_search(S, T[i])

for i in range(q):
    val = T[i]
    left = 0
    right = n
    while left < right:
        mid = (left + right)//2
        if S[mid] == val:
            ans += 1
            break
        elif S[mid] < val:
            left = mid + 1
        else:
            right = mid

print(ans)



Measured memory_bytes: 16704
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <vector>
#include <string.h>

using namespace std;

int main(){
	char* ans[10];
	int ind = 0;
	string s;
	int m;
	while(true){
		cin >> s;
		if(s == "-") break;
		cin >> m;
		
		for(int i = 0; i < m; i++){
			int num;
			cin >> num;
			string cp1 = s.substr(0, num);
			string cp2 = s.substr(num, s.size()-num);
			s = cp2 + cp1 + "\0";
		}
		ans[ind] = (char*)calloc(s.size()+1, sizeof(char));
		strcpy(ans[ind], s.c_str());
		ind++;
	}
	
	for(int i = 0; i < ind; i++){
		cout << ans[i] << endl;
	}
}





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

int main() {
    int n, p[50];
    cin >> n;
    for (int i = 0; i < n; i++) cin >> p[i];

    int ans = 0;
    for (int i = 1; i + 1 < n; i++) {
        if (p[i] > p[i - 1] && p[i] < p[i + 1]) ans++;
        else if (p[i] < p[i - 1] && p[i] > p[i + 1]) ans++;
    }

    cout << ans << endl;
}

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

#define ll long long
#define mp make_pair
#define rep(i, a, b) for(int i = (a);i <= (b);i++)
#define per(i, a, b) for(int i = (a);i >= (b);i--)

using namespace std;

typedef pair<int, int> pii;
typedef double db;
const int N = 1e6 + 50;
int n, k, a[N], ans = 0,  cnt;
set <int> s;
set <int>::iterator it;
inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -1; ch = getchar();}
	while(ch >='0' && ch <='9'){x = (x<<3)+(x<<1)+(ch^48); ch = getchar();}
	return x*f;
}
void init(){
	n = read(); k = read();
	rep(i, 1, n) a[i] = read();
	rep(i, 1, k) s.insert(a[i]);
	rep(i, 2, n){
		if(a[i] > a[i-1]){
			int sum = 0;
			while(a[i] > a[i-1] && i <= n) i++, sum++;
			if(sum >= k-1) cnt ++;
		}
	}
	ans = n-k+1;
	int l = 1, r = k;
	while(l <= r && r <= n){
		r++;
		if(r > n) break;
		s.insert(a[r]);
		if(*(s.rbegin()) == a[r] && (*s.begin()) == a[l]) ans --;
		s.erase(a[l]); 
		l++;
	}
	if(!cnt) printf("%d\n", ans);
	else printf("%d\n", ans - cnt+1);
}
int main(){
//	freopen("input.in","r",stdin);
//	freopen("output.out","w",stdout);
	init();
	return 0;
}


Measured memory_bytes: 10368
import java.util.*;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int X = sc.nextInt();
    int N = sc.nextInt();
    Integer[] p = new Integer[N];
    for(int i=0;i<N;i++){
      p[i] = sc.nextInt();
    }
    int i=0;
    int abs = 0;
    while(true){
      if(!(Arrays.asList(p).contains(X-i))){
        abs = -i;
        break;
      }else if(!(Arrays.asList(p).contains(X+i))){
        abs = i;
        break;
      }
      i++;
    }
    System.out.println(X+abs);
  }
}

Measured memory_bytes: 35836
#pragma GCC optimize(3)
#pragma GCC optimize(fast)
#include<bits/stdc++.h>
using namespace std;
const int N=500005;
int n,k;
int tot;
struct tre{
	int ls,rs;
}t[N*14];
int rt[N];
int p,a[N],b[N];
struct edge{
	int r,next;
}e[N*41];
int rd[N*14],h[N*14],st,cd[N*14];
void add(int x,int y){
	rd[y]++;cd[x]++;
	e[++st].next=h[x];h[x]=st;e[st].r=y;
}
int tt,val[N];
void hins(int x){
//	printf("%d\n",x);
	val[++tt]=x;int k;
	for(int i=tt;a[val[i]]<a[val[i>>1]]&&(i>>1);k=val[i],val[i]=val[i>>1],val[i>>1]=k,i>>=1);
}
void hdel(){
	val[1]=val[tt--];
	int k;
	for(int i=1;(i<<1)<=tt;){
		int mn=i<<1;
		if((i<<1|1)<=tt){
			if(a[val[i<<1|1]]<=a[val[mn]])mn=i<<1|1;
		}
		if(a[val[mn]]<a[val[i]])k=val[mn],val[mn]=val[i],val[i]=k,i=mn;
		else break;
	}
}
void connect(int l,int r,int now,int ml,int mr,int k){
	if(!now)return;
	if(ml==l&&mr==r){
		add(now,k);
		return;
	}
	int mid=l+r>>1;
	if(ml>mid)connect(mid+1,r,t[now].rs,ml,mr,k);
	else if(mr<=mid)connect(l,mid,t[now].ls,ml,mr,k);
	else connect(l,mid,t[now].ls,ml,mid,k),connect(mid+1,r,t[now].rs,mid+1,mr,k);
}
void ins(int l,int r,int &now,int las,int pos,int k){
	if(cd[las]){
		now=++tot;
		t[now]=t[las];
	}
	else now=las;
	add(k,now);
	if(l==r)return;
	int mid=l+r>>1;
	if(mid>=pos)ins(l,mid,t[now].ls,t[las].ls,pos,k);
	else ins(mid+1,r,t[now].rs,t[las].rs,pos,k);
}
int read(){
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x;
}
int stpd[N*14],cnmd;
int main(){
//	freopen("bubble.in","r",stdin);
//	freopen("bubble.out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		p=read();
		a[p]=i;
	}
	tot=n;cd[0]=1;
	for(int i=1;i<=n;i++){
		connect(1,n,rt[i-1],a[i],min(a[i]+k-1,n),i);
		ins(1,n,rt[i],rt[i-1],a[i],i);
	}
	for(int i=1;i<=n;i++){
		if(!rd[i])hins(i);
	}
	for(int i=1;i<=n;i++){
		int x=val[1];
		while(x>n){
			hdel();
			for(int i=h[x];i;i=e[i].next){
				if(!(--rd[e[i].r])){
					if(e[i].r<=n)hins(e[i].r);
					else stpd[++cnmd]=e[i].r; 
				}
			}
			while(cnmd){
				x=stpd[cnmd--];
				for(int i=h[x];i;i=e[i].next){
					if(!(--rd[e[i].r])){
						if(e[i].r<=n)hins(e[i].r);
						else stpd[++cnmd]=e[i].r; 
					}
				}
			}
			x=val[1];
		}
		b[i]=a[x];
		hdel();
		for(int i=h[x];i;i=e[i].next){
			if(!(--rd[e[i].r])){
				if(e[i].r<=n)hins(e[i].r);
				else stpd[++cnmd]=e[i].r; 
			}
		}
		while(cnmd){
			x=stpd[cnmd--];
			for(int i=h[x];i;i=e[i].next){
				if(!(--rd[e[i].r])){
					if(e[i].r<=n)hins(e[i].r);
					else stpd[++cnmd]=e[i].r; 
				}
			}
		}
	}
	for(int i=1;i<=n;i++)a[i]=0;
	for(int i=1;i<=n;i++)a[b[i]]=i;
	for(int i=1;i<=n;i++)printf("%d\n",a[i]);
} 


Measured memory_bytes: 241152
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<iomanip>
typedef long long int ll;
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (unsigned int i=0;i<(n);i++)
#define EREP(i,n) for (int i=1;i<=(n);i++)
#define ALL(a) (a).begin(),(a).end()
//#define EVEL 1

#ifdef EVEL
#define DEB(X) cout << #X << ":" <<X<<" " ;
#define TF(f) f ? cout<<"true  " : cout<<"false ";
#define END cout<<"\n";
#else
#define DEB(X) {}
#define TF(f) {}
#define END {}
#endif
const int MOD =  1000000007 ;
const int INF = 2000000000;


    ll A,B,C,D;
    ll X[4];
    string S,T;
int main(){
    cin>>A>>B;
    cout<<A-B+1;
    return 0;
}

Measured memory_bytes: 256
n=int(input())
a=input()
b=input()
c=input()

ret = 0
for i in range(n):
    if a[i] == b[i] == c[i]:
        continue
    if a[i] == b[i] or b[i] == c[i] or a[i] == c[i] :
        ret += 1
    else:
        ret += 2

print(ret)

Measured memory_bytes: 3064
#include <stdio.h>
#include<stdlib.h>
int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}
int a, b, c, i, ans[3];
int main(void)
{
    scanf("%d%d%d", &a, &b, &c);
    ans[0] = a + b;
    ans[1] = a + c;
    ans[2] = b + c;
    qsort(ans, 3, sizeof(int), compare_int);
    printf("%d", ans[0]);
}

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


int main(){
    ll a,b;
    cin>>a>>b;
    ll A=a;
    char c[111][111];
    rep(i,0,100)rep(j,0,100)c[i][j]='o';
    ll i=0;
    while(a!=1){
        c[i/50*2][i%50*2]='.';
        c[i/50*2+1][i%50*2]='#';
        c[i/50*2][i%50*2+1]='#';
        c[i/50*2+1][i%50*2+1]='#';
        i++;
        a--;
    }
    while(b!=1){
        c[i/50*2][i%50*2]='.';
        c[i/50*2+1][i%50*2]='.';
        c[i/50*2][i%50*2+1]='.';
        c[i/50*2+1][i%50*2+1]='#';
        i++;
        b--;
    }
    cout<<100<<" "<<100<<endl;
    rep(i,0,100){
        rep(j,0,100){
            if(c[i][j]=='o')c[i][j]='.';
            if(A==1)c[99][99]='#';
            cout<<c[i][j];
        }
        cout<<endl;
    }
    
}

    









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


            int32_t main()
            {
         
                ios_base::sync_with_stdio(false);
                cin.tie(NULL);
         

                int r;
                cin>>r;

                cout<<fixed<<setprecision(4)<<2*M_PI*r;               



            }

Measured memory_bytes: 3804
<?php
$step = trim(fgets(STDIN));
$rows = [];

while (($row = trim(fgets(STDIN))) !== '') {
  $rows[] = explode(' ', $row);
}

$memo = [];

for ($i=0; $i < $step; $i++) {
  $result = 0;
  for ($j=0; $j <= $i; $j++) {
    $result += $rows[0][$j];
  }
  for ($j=$i; $j < $step; $j++) {
    $result += $rows[1][$j];
  }
  $memo[] = $result;
}

echo max($memo)."\n";


Measured memory_bytes: 3700
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[5005];

ll fun(ll l,ll r,vector<vector<ll>>&dp)
{
    if(l>r)return 0;
    if(l==r)return dp[l][r]=a[l];
    if(dp[l][r]!=-1)return dp[l][r];
    return dp[l][r]=max(a[l]-fun(l+1,r,dp),a[r]-fun(l,r-1,dp));
}

int main() {
	ll n,i,j,k;
	cin>>n;
	for(i=1;i<=n;i++)
	cin>>a[i];
	vector<vector<ll>>dp(n+1,vector<ll>(n+1,-1));
    cout<<fun(1,n,dp);
	return 0;
}


Measured memory_bytes: 73996
#include <iostream>
using namespace std;
int main(void){
    int n; //生徒の数
    double h; //生徒の慎重

    int c1 = 0, c2 = 0, c3 = 0, c4 = 0, c5 = 0, c6 = 0;
    /*
      c1は165.0cm未満の生徒数
      c2は165.0cm以上170.0cm未満の生徒数
      c3は170.0cm以上175.0cm未満の生徒数
      c4は175.0cm以上180.0cm未満の生徒数
      c5は180.0cm以上185.0cm未満の生徒数
      c6は185.0cm以上の生徒数
    */

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> h;

        if(h < 165.0) c1++;
        else if(165.0 <= h && h < 170.0) c2++;
        else if(170.0 <= h && h  < 175.0) c3++;
        else if(175.0 <= h && h  < 180.0) c4++;
        else if(180.0 <= h && h  < 185.0) c5++;
        else c6++;
    }

    cout << "1:";
    if(c1 > 0){
        for(int i = 1; i <= c1; i++)
            cout << '*';
    }
    cout << endl;

    cout << "2:";
    if(c2 > 0){
        for(int i = 1; i <= c2; i++)
            cout << '*';
    }
    cout << endl;

    cout << "3:";
    if(c3 > 0){
        for(int i = 1; i <= c3; i++)
            cout << '*';
    }
    cout << endl;

    cout << "4:";
    if(c4 > 0){
        for(int i = 1; i <= c4; i++)
            cout << '*';
    }
    cout << endl;

    cout << "5:";
    if(c5 > 0){
        for(int i = 1; i <= c5; i++)
            cout << '*';
    }
    cout << endl;

    cout << "6:";
    if(c6 > 0){
        for(int i = 1; i <= c6; i++)
            cout << '*';
    }
    cout << endl;
}


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

using namespace std;

vector<int> ans;

int main(){
	while(1){
		int ro,wo,c,r;
		cin >> ro >> wo >> c >>r;
		if(ro + wo + c + r == 0) break;
		int minr = wo * c;
		int i;
		for(i = 0;i*r+ro < minr;i++);
		ans.push_back(i);
	}
	for(int i = 0;i < ans.size();i++) cout << ans[i] <<endl;
	return 0;
}

Measured memory_bytes: 3044
#include <bits/stdc++.h>
#include <math.h>
#define ALL(a)    a.begin(), a.end() 
#define rep(i, K, N)  for(long long int i = K; i < N; i++)
#define ll long long int
#define PP 1000000007
using namespace std;

int main(){
ll N;cin >> N;
bool C = 0;
vector<pair<ll, ll>> V(N);

rep(i, 0, N){

    cin >> V[i].first >> V[i].second;

}

rep(i, 0, N - 2){
    if(V[i].first == V[i].second && V[i + 1].first == V[i + 1].second && V[i + 2].first == V[i + 2].second)C = 1;
}

if(C)cout << "Yes";

else cout <<"No";

}

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


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define f(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
int main(void){
	int n, ans = 0;
	double d, c1, c2;
	cin >> n >> d;
	while(n--){
		cin >> c1 >> c2;
		double tmp = sqrt(pow(c1, 2)+pow(c2,2));
//		cout << tmp << endl;
//		puts("----");
		if(tmp <= d)ans++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 3720
function Main(input) {
    var nums = Number(input);
    var cnt = 0;
    for(var i = 1;i <= nums;i++){
      if(i % 2 !== 0) {
        cnt++;
      }
    }
    console.log(cnt / nums);
 }
 
/* var input = `4`;
Main(input);
 */  
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

int main(){
	while(true){
		int H, W;
		cin >> H >> W;
		if(H == 0 && W == 0) break;
		for(int i = 0; i < H; i++){
			for(int j = 0; j < W; j++){
				cout << "#";
			}
			cout << endl;
		}
		cout << endl;
	}
}



Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
struct Edge {
  ll to;
  ll cost;
};
int main() {
  int W, H, N;
  cin >> W >> H >> N;
  vector<vector<int>> square(H, vector<int>(W, 0));
  REP(i, N) {
    int x, y, a;
    cin >> x >> y >> a;
    if (a == 1) {
      REP(i, H) REP(j, x) { square[i][j] = 1; }
    } else if (a == 2) {
      REP(i, H) for (int j = x; j < W; j++) { square[i][j] = 1; }
    } else if (a == 3) {
      REP(i, y) REP(j, W) { square[i][j] = 1; }
    } else {
      for (int i = y; i < H; i++) REP(j, W) {
          square[i][j] = 1;
        }
    }
  }
  ll ans = 0;
  REP(i, H) REP(j, W) {
    if (square[i][j] == 0) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)
#define VL vector<ll>
#define VS vector<string>
#define VB vector<bool>
#define VP vector<pair<ll,ll>>
#define VVL vector<vector<ll>>
#define VVP vector<vector<pair<ll,ll>>>
#define PL pair<ll,ll>
#define ALL(v) (v).begin(), (v).end()
ll d1[4] = {1, -1, 0, 0};
ll d2[4] = {0, 0, 1, -1};

int main(){
    ll n;
    cin >> n;
    VL a(n), b(n);
    ll sum = 0;
    rep(i, 0, n){
        cin >> a[i];
        sum ^= a[i];
    }
    rep(i, 0, n){
        b[i] = sum ^ a[i];
    }
    rep(i, 0, n){
        cout << b[i];
        if(i == n-1) cout << endl;
        else cout << " ";
    }
    return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define each(i, mp) for (auto &i : mp)
#define sz(x) int(x.size())

int main()
{
  int n;
  cin >> n;
  int last = n % 10;
  string ans;
  switch (last)
  {
  case 2 /* constant-expression */:
    /* code */
    ans = "hon";
    break;
  case 4 /* constant-expression */:
    /* code */
    ans = "hon";
    break;
  case 5 /* constant-expression */:
    /* code */
    ans = "hon";
    break;
  case 7 /* constant-expression */:
    /* code */
    ans = "hon";
    break;
  case 9 /* constant-expression */:
    /* code */
    ans = "hon";
    break;
  case 0 /* constant-expression */:
    /* code */
    ans = "pon";
    break;
  case 1 /* constant-expression */:
    /* code */
    ans = "pon";
    break;
  case 6 /* constant-expression */:
    /* code */
    ans = "pon";
    break;
  case 8 /* constant-expression */:
    /* code */
    ans = "pon";
    break;
  case 3 /* constant-expression */:
    /* code */
    ans = "bon";
    break;

  default:
    break;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3620
#include<stdio.h>

int main(){

  int n;

  scanf("%d", &n);


  int g[102][102],d[102];


  int i,j;
  for(i=1;i<=n;i++){
    for(j=1;j<=n;j++){
      g[i][j] = 0;
    }
    d[i]=-1;
  }

  int u,k;
  for(i=0;i<n;i++){
    scanf("%d %d", &u,&k);
    for(j=0;j<k;j++){
      int v;
      scanf("%d", &v);
      g[u][v] = 1;
    }
  }

  int Q[102];
  int head=0,tail;
  tail=head+1;

    Q[head]=1;
    //  tail+=1;
    d[Q[head]]=0;
    while(head!=tail){
      u=Q[head];
      head++;
      for(i=1;i<=n;i++){
	if(g[u][i]==1 && d[i]==-1){
	  g[u][i]=0;
	  d[i]=d[u]+1;
	  Q[tail++]=i;
	    }
	}
    }


  for(i=1;i<=n;i++){
    printf("%d %d\n", i, d[i]);
  }
  return 0;
}

Measured memory_bytes: 636
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;
using static System.Console;

namespace atcorder2
{
    class Program
    {
        public static long Read()
        {
            return long.Parse(ReadLine());
        }

        public static long[] Reads()
        {
            return ReadLine().Split().Select(long.Parse).ToArray();
        }


        public static long gcd(long x,long y)
        {
            if (y < x) gcd(y, x);
            while (y != 0)
            {
                var z = x % y;
                x = y;
                y = z;
            }
            return x;
        }
        static void Main(string[] args)
        {
            var sw = new StreamWriter(OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            var q = Reads();
            var n = q[0];
            var m = q[1];
            if (2 * n >= m) WriteLine(m/2);
            else WriteLine(n+(m-2*n)/4);

            

            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 18880
N = int(input())
f = 0
ans = 'No'
for i in range(N):
    x,y = map(int,input().split())
    if x == y:
        f += 1
    else:
        f = 0
    if f == 3:
        ans = 'Yes'
        print(ans)
        quit()
print(ans)

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

const char wall = '#';
vector<vector<char>> fields;
vector<vector<bool>> used;
vector<vector<ll>> dist;
const int dx[4] = {0, -1, 0, 1};
const int dy[4] = {1, 0, -1, 0};

vector<ll> A;
// vectorのリサイズ
// A.resize(N);

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return b/gcd(a,b)*b;}
ll ans = 0;

void bfs(ll t, ll x) {
  queue<P> q;
  q.push({0, 0});
  while(!q.empty()) {
    P end = q.front(); q.pop();
    if (end.first-(end.second+1) == x) {
      ans = end.second+1;
      break;
    }
    q.push({end.first-(end.second+1), end.second+1});

    if (end.first == x) {
      ans = end.second+1;
      break;
    }
    q.push({end.first, end.second+1});

    if (end.first+(end.second+1) == x) {
      ans = end.second+1;
      break;
    }
    q.push({end.first+(end.second+1), end.second+1});
  }
}

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

  ll x;
  cin >> x;
  cout << ceil((-1+sqrt(1+8*x))/2.0) << endl;
  return 0;
}


Measured memory_bytes: 256
n,p = gets.chomp.split(" ").map(&:to_i)
s = gets.chomp

if p == 2 || p == 5
  ans = 0
  (n-1).downto(0) do |i|
    ans += i+1 if s[i].to_i % p == 0
  end
  puts ans
else
  mods = Array.new(p,0)
  sum = 0
  bit = 1
  (n-1).downto(0) do |i|
    sum += s[i].to_i * bit
    sum %= p
    mods[sum] += 1
    bit = bit * 10 % p
  end
  ans = mods[0]
  for i in 0..p-1
    ans += mods[i] * (mods[i]-1) / 2
  end
  puts ans
end

Measured memory_bytes: 2300
import copy

H, W, K = map(int, input().split())
inputdata = [list(str(input())) for i in range(H)]
data = []
temp = []
give = 0

for x in inputdata:
  data.append(list(x))

for i in range(2 ** H):
  for j in range(2 ** W):
    ans = 0
    temp = copy.deepcopy(data)
    for m in range(H):
      for n in range(W):
        if ((int(bin(i)[2:]) >> m) & 1) or ((int(bin(j)[2:]) >> n) & 1):
          temp[m][n] = "@"
        if temp[m][n] == "#":
          ans += 1
    if ans == K:
      give += 1

print(give)

Measured memory_bytes: 9284
#include <iostream>
using namespace std;
int main(void){
    int m,f,r,sum;
    int a[50];
    while(1){
        cin >> m >> f >> r ;
        if(m==-1 && f==-1 && r==-1) break;
        sum=m+f;
        if(m==-1 || f==-1) cout << "F" << endl;
        else if(sum>=80) cout << "A" << endl;
        else if(sum>=65) cout << "B" << endl;
        else if(sum>=50) cout << "C" << endl;
        else if(sum>=30){
            if(r>=50) cout << "C" << endl;
            else cout << "D" << endl;
        }
        else cout << "F" << endl;
    }
    
}


Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 1000000007;
int main() {
    ll n,ans = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        //ans += (i%(n-i+1));
        ans += i;
    }
    cout << ans-n << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	public static void main(String[] args) throws java.io.IOException {
		Scanner scan = new Scanner(System.in);
		int n[] = new int[5];
		for(int i = 0; i<5 ; i++){
			n[i] = scan.nextInt();
		}
		int t = 0;
		for(int i = 0 ; i < 5 ; i++){
			for(int j = i+1 ; j < 5 ; j++){
				if(n[i] < n[j]){
					t = n[i];
					n[i] = n[j];
					n[j] = t;
				}
			}
		}
		for(int i = 0 ; i < 5 ; i++){
			if(i == 4){
				System.out.println(n[i]);
			}else{
				System.out.print(n[i] + " ");
			}
		}
	}
}

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

int read()
{
	int s=0;
	char c=getchar(),lc='+';
	while (c<'0'||'9'<c) lc=c,c=getchar();
	while ('0'<=c&&c<='9') s=s*10+c-'0',c=getchar();
	return lc=='-'?-s:s;
}
void write(int x)
{
	if (x<0)
	{
		putchar('-');
		x=-x;
	}
	if (x<10) putchar(x+'0');
	else
	{
		write(x/10);
		putchar(x%10+'0');
	}
}
void print(int x,char c='\n')
{
	write(x);
	putchar(c);
}

int main()
{
	int x=read();
	for (int i=1;;i++)
	if (360*i%x==0)
	return print(360*i/x),0;
}

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

int main()
{
    int N, n;
    int c = 0;
    cin >> N;
    n = N;
    while ( n > 0 ) c += n % 10, n /= 10;
    if ( N % c == 0 ) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return ( 0 );
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main() {
	int n; cin >> n;
	int a = 0, un = 0;
	bool b = true;
	for (int i = 0; i < n; i++){
		string str;
		cin >> str;
		if (str == "A")a++;
		else if (str == "Un")un++;
		if (a < un)b = false;
	}
	if (a > un)b = false;
	if (b)cout << "YES"; else cout << "NO";
	cout << endl;
	char c;
	cin >> c;
	return 0;
}

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

void _dfs(
    vector<int> &price,
    vector<vector<int>> &algorithm,
    int requirement,
    int &minPrice,
    int curPrice,
    int idx,
    vector<int> curstat
) {
    // check for sufficiency
    bool sufficient = true;

    for (int stat : curstat) {
        if (stat < requirement) {
            sufficient = false;
            break;
        }
    }

    if (sufficient) {
        minPrice = min(minPrice, curPrice);
        return;
    }

    // For each other books
    for (int i = idx + 1; i < price.size(); ++i) {
        vector<int> nextStat(curstat.size());
        
        // update next stat
        for (int j = 0; j < curstat.size(); ++j) {
            nextStat[j] = curstat[j] + algorithm[i][j];
        }

        _dfs(price, algorithm, requirement, minPrice, curPrice + price[i], i, nextStat);
    }
}

int main() {
    int n, m, x;

    cin >> n >> m >> x;
    vector<vector<int>> algorithm(n, vector<int>(m));
    vector<int> price(n);

    // read the table
    for (int i = 0; i < n; ++i) {
        cin >> price[i];

        for (int j = 0; j < m; ++j)
            cin >> algorithm[i][j];
    }

    int minPrice = INT_MAX;
    _dfs(price, algorithm, x, minPrice, 0, -1, vector<int>(m));

    cout << (minPrice == INT_MAX ? -1 : minPrice) << '\n';

    return 0;
}


Measured memory_bytes: 3544
#include "bits/stdc++.h"
using namespace std;
typedef long long li;

vector<li> divisors(li n) {
    vector<li> divisors;
    for (li x = 1; x * x <= n; x++) {
        if (n % x == 0) {
            divisors.push_back(x);
            if (n / x != x) {
                divisors.push_back(n / x);
            }
        }
    }
    return divisors;
}

bool ok(li n, li k) {
    while (n >= k) {
        if (n % k == 0) {
            n /= k;
        } else {
            return n % k == 1;
        }
    }
    return n == 1;
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    li n;
    cin >> n;

    auto divs = divisors(n);
    set<li> ans;
    for (li k : divisors(n - 1)) {
        if (k == 1) {
            continue;
        }
//        cerr << k << " a" << endl;
        ans.insert(k);
    }
    for (li k : divs) {
        if (k == 1) {
            continue;
        }
        if (ok(n, k)) {
//            cerr << k << " b" << endl;
            ans.insert(k);
        }
    }
    cout << ans.size() << endl;
//
//    for (int k = 2; k <= n; ++k) {
//        if (ok(n, k)) {
//            cerr << k << " naive" << endl;
//        }
//    }
    return 0;
}

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

int main()
{
	vector<int> v;
	int n; cin >> n;
	v.resize(n);
	for(int& x:v) cin >> x;
	
	int tg = round(accumulate(v.begin(), v.end(), 0) * 1.0 / n), ans = 0;
	for(int& x:v) ans += (tg-x)*(tg-x);
	cout << ans;
	return 0;
}


Measured memory_bytes: 256
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
   
//#include <x86intrin.h>
#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;

template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
     
#define F first
#define S second           
#define lb lower_bound               
#define ub upper_bound
#define pb push_back
#define pf push_front    
#define ppb pop_back
#define mp make_pair
#define bpp __builtin_popcountll                                                                                        
#define sqr(x) ((x) * (x)) 
#define al 0x3F3F3F3F
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define in insert
#define ppf pop_front
#define endl '\n'
//#define int long long
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
 
const int mod = (int)1e9 + 7;
const int N = (int)3e5 + 123;
const ll inf = (ll)1e18 + 1;

const double pi = acos (-1.0);
const double eps = 1e-7;                  
const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};

int n, k;
bool d[(1 << 20)];
vector <int> path[(1 << 20)];

inline void boost () {                    
   ios_base :: sync_with_stdio (NULL);
   cin.tie (NULL), cout.tie (NULL);          
}                                                     

inline void Solve () {
   cin >> n >> k;
   if (k >= (1 << n)) cout << -1, exit (0);
   if (n == 1 && k == 1) cout << -1, exit (0);
   if (k == 0) {
      for (int i = 0; i < (1 << n); i ++) cout << i << ' ' << i << ' ';
      exit (0);
   }
   cout << 0 << ' ' << k << ' ' << 0 << ' ';
   for (int i = 1; i <= (1 << n) - 1; i ++)
      if (i != k)
         cout << i << ' ';
   cout << k << ' ';
   for (int i = (1 << n) - 1; i >= 1; i --)
      if (i != k)
         cout << i << ' ';

}

main () {                                       
// freopen (".in", "r", stdin);    
// freopen (".out", "w", stdout);              
   boost ();
   int tt = 1;
   //cin >> tt;   
   while (tt --) {
      Solve ();
   }                                               
   return 0;      
}
                          

Measured memory_bytes: 26368
import sys
n = int(sys.stdin.readline())
for i in range(n):
    sides = [int(k) for k in sys.stdin.readline().split()]
    sides.sort()
    if sides[0] ** 2 + sides[1] ** 2 == sides[2] ** 2:
        print("YES")
    else:
        print("NO")

Measured memory_bytes: 6720
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.ComponentModel.Design;
using System.Globalization;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading;
using System.Threading.Tasks;
using System.Xml.Schema;
using static System.Console;

namespace ConsoleApp2
{
    class Program
    {
        static public int[] Sarray() { return ReadLine().Split().Select(int.Parse).ToArray(); }
        static public List<int> Slist() { return new List<int>(ReadLine().Split().Select(int.Parse)); }
        static void Main(string[] args)
        {
            var HWK = Sarray();
            var H = HWK[0];
            var W = HWK[1];
            var K = HWK[2];
            var chw = new char[H][];
            for(var i=0;i<H;i++)
            {
                chw[i] = ReadLine().ToCharArray();
            }
            var ans = 0;
            for(var maskR=0;maskR<(1<<H)-1;maskR++)
            {
                for (var maskC = 0; maskC < (1 << W) - 1; maskC++)
                {
                    var black = 0;
                    for(var i=0;i<H;i++)
                    {
                        for (var j = 0; j < W; j++)
                        {
                            if((((maskR>>i)&1)==0) && (((maskC >> j) & 1) == 0) && chw[i][j]=='#')
                            {
                                black++;
                            }
                        }
                    }
                    if (black == K) ans++;
                }
            }
            WriteLine(ans++);
        }
    }
}

Measured memory_bytes: 18888
import java.util.*;
import java.io.*;
import java.math.*;
public class Main{
	static int mod = (int)1e9+7;
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	public static void main(String sp[])throws IOException{
		FastReader sc = new FastReader();
		int n =sc.nextInt();
		ArrayList<Long> al = new ArrayList<>();
		for(int i=0;i<n;i++){
			al.add(sc.nextLong());
		}
		long max = 0;
		long count=0;
		for(int i=0;i<n-1;i++){
			if(al.get(i+1)<=al.get(i)){
			
				count++;
				max = Math.max(max,count);
			}else count=0;
			
		}
		System.out.println(max);
		out.close();
	}
	
	public static int partition(int [] arr, int s, int e){
		
		int index=s;
		int pivot = arr[e];
		for(int i=s;i<=e-1;i++){
			if(arr[i]<=pivot){
				arr = swap(arr, index, i);
				index++;
			}
		}
		swap(arr,index,e);
		print(arr);
		return index;
	}
	
	public static int[] swap(int[] arr, int low, int high){
		int temp = arr[low];
		arr[low]=arr[high];
		arr[high]=temp;
		return arr;
	}
	
	
	public static long gcd(long a, long b){
		if(a==0)
			return b;
		
		return gcd(b%a,a);
	}
	
	public static void print(int[] arr){
		for(int i=0;i<arr.length;i++)
			System.out.print(arr[i]+" ");
		System.out.println();
	}
	
	public static class pair{
		int ai;
		int bi;
	}
	
	public static class comp implements Comparator<pair>{
		public int compare(pair o1, pair o2){
			return o1.bi-o2.bi;
		}
	}
	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;
	
 
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception r) {
					r.printStackTrace();
				}
			}
			return st.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(next());//converts string to integer
		}
 
		double nextDouble() {
			return Double.parseDouble(next());
		}
 
		long nextLong() {
			return Long.parseLong(next());
		}
 
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception r) {
				r.printStackTrace();
			}
			return str;
		}
	}
	
}

Measured memory_bytes: 44148
N,M = map(int,input().split())

students = []
for _ in range(N):
  a,b = map(int,input().split())
  students.append((a,b))

points = []
for _ in range(M):
  c,d = map(int,input().split())
  points.append((c,d))

for n in range(N):
  a,b = students[n]
  index = -1
  best = 99999999999
  for m in range(M):
    c,d = points[m]
    dist = abs(a-c)+abs(b-d)
    if dist<best:
      best = dist
      index = m
  print(index+1)


Measured memory_bytes: 39280
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm> // sort
#include <math.h> // sort

#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const ll MOD = 1000000007;
static const ll INF = 1000000000000000000LL;
using namespace std;

int main(){
    //std::ifstream in("input.txt");
    //std::cin.rdbuf(in.rdbuf());
    ll r,g;
    cin >> r >> g;

    ll res;
    ll sa = g - r;

    res = r + 2 * sa;
    cout << res << endl;
    return 0;    

}



Measured memory_bytes: 256
N = int(input())

N_str = str(N)

if int(N_str[-1]) == 2 or int(N_str[-1]) == 4 or int(N_str[-1]) == 5 or int(N_str[-1]) == 9 or int(N_str[-1]) == 7:
    print('hon')
elif int(N_str[-1]) == 0 or int(N_str[-1]) == 1 or int(N_str[-1]) == 6 or int(N_str[-1]) == 8:
    print('pon')
else:
    print('bon')


Measured memory_bytes: 9140
def read_input():
    x, a, b = map(int, input().split())
    return x, a, b

def submit():
    x, a, b = read_input()

    if abs(x - a) < abs(x - b):
        print('A')
    else:
        print('B')

if __name__ == '__main__':
    submit()
    

Measured memory_bytes: 38256
//保留所有权利。
#include<iostream>
#include<stdio.h>//printするよ
#include<vector>
#include<algorithm>//辞書順はnext_permutationだよ
#include<set>
#include<string>
#include<string.h>
#include<time.h>
#include<random>
#include<cmath>
#include<math.h>
#include<queue>
#include<time.h>
#include<iomanip>
#include<utility>//swapで数値交換するよ
//END OF LIBRARIES.
#define rt "\n"//改行を最速化させるよ
#define rep(i,n) for(int i=0;i<n;i++)
#define rop(i,n) for(int i=1;i<=n;i++)
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define yes(ans) if(ans)cout<<"yes"<<rt;else cout<<"no"<<rt;
#define Yes(ans) if(ans)cout<<"Yes"<<rt;else cout<<"No"<<rt;
#define YES(ans) if(ans)cout<<"YES"<<rt;else cout<<"NO"<<rt;
#define vcin(v) for (int i = 0; i < (v).size(); i++) { cin >> (v)[i]; }
#define sort(s) sort(s.begin(),s.end())
#define reve(s) reverse(s.begin(),s.end())
#define asas int ans=0
#define llcncn llint cnt=0
#define llasas llint ans=0
#define cncn int cnt=0
#define smsm int sum=0
#define str srting
#define v vector
#define nn int n=0
#define please return
#define AC 0//おまじないだよ
#define Rapid cin.tie(0);ios::sync_with_stdio(false)
//END OF DEFINE.
using namespace std;
typedef vector<int> vint;
typedef vector<string> vstr;
typedef vector<char> vcha;
typedef vector<double> vdou;
typedef long long int llint;
typedef pair<int, int> pint;
typedef pair<llint, llint> pllint;
typedef vector<llint> vllint;
typedef vector<pint> vpint;
typedef vector<pair<llint, llint>> vpllint;
typedef vector<vector<int>> vvint;
typedef vector<vector<llint>> vvllint;
typedef vector<vector<string>> vvstr;
typedef vector<vector<pint>> vvpint;
typedef vector<bool> vbool;
//printf("%02d:%02d:%02d\n", h, m, s);・・・2文字は埋める・h、m、ｓ
//END OF TYPEDEF.

//最大公約数（GCD）を求めるよ
//最小公倍数（LCM）は＜＜　A × B ÷ GCD　 ＞＞で求まるよ

long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}
long long LCM(long long a, long long b) {
	return a * b / GCD(a, b);
}
int x = 0, y = 0, z = 0,n = 0;
asas;
cncn;
//BEGIN OF CODE.
int main(void){
	cin >> n;
	vint a(n);
	rep(i, n)cin >> a[i];
	rep(i, n - 1) {
		if (a[i] == a[i + 1]) {
			cnt++;
			i++;
		}
	}
	cout << cnt << rt;
	please AC;
}

Measured memory_bytes: 256
from itertools import combinations
n = int(input())

kind = [0] * n
word = {}
correct = 0
for i in range(n):
  word[i] = []
  for _ in range(int(input())):
    word[i].append(list(map(int,input().split())))
for i in range(2**n):#正直者を1で表す。高い桁から1番目の人
  ans = 1
  for j in range(n):#ある1人の人に注目する。
    if (i >> (n-1-j)) & 1:#j番目の人が正直者ならば，
      for k in range(len(word[j])):#j番目の人の発言に注目
        if word[j][k][1] == 1 and ((i>>(n-1-(word[j][k][0]-1))) & 1) == 0:#この人が「正直者である」といった発言に関して，その人が実は正直者でないならだめ。
          ans = 0
          break
        if word[j][k][1] == 0 and ((i>>(n-1-(word[j][k][0]-1))) & 1) == 1:#この人が「正直者である」といった発言に関して，その人が実は正直者でないならだめ。
          ans = 0
          break
  if ans:
    correct = sum(list(map(int,list(format(i, 'b')))))
print(correct)
    
      


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (int i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using PL = pair<long long, long long>;
const int INF = 1001001007;
const int MOD = 1000000007;
template <typename T>
void printvec(vector<T> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

void sihou(vector<vector<ll>> &p, int x, int y){
    p[x][y] = p[x][y+1] + p[x+1][y] + p[x][y-1] + p[x-1][y];
}

int main(){
    int n; cin >> n;
    vector<vector<int>> ti(n, vector<int>(10));
    rep(i,n)rep(j,10) cin >> ti[i][j];
    vector<vector<int>> pr(n, vector<int>(11));
    rep(i,n)rep(j,11) cin >> pr[i][j];
    ll mx = -1000000000;
    repp(i,1<<10,1){
        ll r = 0;
        vector<int> jo(10,0);
        rep(j,10){
            if (i>>j & 1) jo[j] = 1;
        }
        rep(j,n){
            int cnt = 0;
            rep(k,10) cnt += ti[j][k] * jo[k];
            r += pr[j][cnt];
        }
        mx = max(mx, r);
    }
    cout << mx << endl;
}

Measured memory_bytes: 256
main(){
    int h,w;
    for(int i=0;;i++){
        scanf("%d%d",&h,&w);
        if(h==0 && w==0)break;
        for(int j=0;j<h;j++){
            for(int k=0;k<w;k++){
                if((j+k)%2==0)printf("#");
                else printf(".");
            }
            printf("\n");
        }
        printf("\n");
    }
}


Measured memory_bytes: 2080
#include <bits/stdc++.h>
using namespace std;
int main() {
  string str;
  cin>> str;
  bool f = true;
  for ( int i = 0 ; i < 3 ; i++ ) {
    if ( str.at(i) == '7' ) {
      cout << "Yes" << endl;
      f = false;
      break;
    }
    
  }
  
  if (f) {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3624
import sys
import copy
from collections import Counter
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces
n = ni()

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def count(p):
    cnt = 0
    now = 1
    while p>0:
        if p < now:
            break
        p -= now
        cnt += 1
        now += 1
    return cnt

c = Counter(prime_factorize(n))
res = 0
for v in c.values():
    res += count(v)

print(res)

Measured memory_bytes: 68236
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int d = 0;

		for(; a <= b; a++){
			if(c%a == 0)
			d++;
		}

		System.out.println(d);
	}
}





Measured memory_bytes: 26420
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <valarray>
#include <vector>

#define EPS 1e-9
#define INF (1070000000LL*1070000000LL)
#define MOD 1000000007LL
#define fir first
#define foreach(it,X) for(__typeof((X).begin()) it=(X).begin();it!=(X).end();it++)
#define ite iterator
#define mp make_pair
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define pb push_back
#define sec second
#define sz(x) ((int)(x).size())

using namespace std;

struct timer{
	time_t start;
	timer(){start=clock();}
	~timer(){cerr<<1.*(clock()-start)/CLOCKS_PER_SEC<<" secs"<<endl;}
};

typedef istringstream iss;
typedef long long ll;
typedef pair<int,int> pi;
typedef stringstream sst;
typedef vector<int> vi;

int H,W;
char c[555][555];
int sy,sx,gy,gx;
ll dist1[555][555],dist2[555][555];
int dy[]={0,1,0,-1};
int dx[]={1,0,-1,0};

int main(){
	//cin.tie(0);
	//ios_base::sync_with_stdio(0);
	
	cin>>W>>H;
	rep(i,H)rep(j,W){
		cin>>c[i][j];
		if(c[i][j]=='s')sy=i,sx=j,c[i][j]='.';
		if(c[i][j]=='g')gy=i,gx=j;
	}
	rep(i,H)rep(j,W){
		dist1[i][j]=dist2[i][j]=INF;
	}
	dist1[gy][gx]=0;
	queue<pi> Q;
	Q.push(mp(gy,gx));
	while(sz(Q)){
		pi p=Q.front();Q.pop();
		int y=p.fir,x=p.sec;
		rep(d,4){
			int ny=y+dy[d],nx=x+dx[d];
			if(c[ny][nx]=='.' && dist1[ny][nx]==INF){
				dist1[ny][nx]=dist1[y][x]+1;
				Q.push(mp(ny,nx));
			}
		}
	}
	rep(i,H)rep(j,W)if(c[i][j]=='*'){
		dist2[i][j]=0;
		Q.push(mp(i,j));
	}
	while(sz(Q)){
		pi p=Q.front();Q.pop();
		int y=p.fir,x=p.sec;
		rep(d,4){
			int ny=y+dy[d],nx=x+dx[d];
			if(c[ny][nx]=='.' && dist2[ny][nx]==INF){
				dist2[ny][nx]=dist2[y][x]+1;
				Q.push(mp(ny,nx));
			}
		}
	}
	
	vector<ll> d1,d2;
	int start;
	rep(i,H)rep(j,W)if(c[i][j]=='.'){
		if(i==sy && j==sx)start=sz(d1);
		d1.pb(dist1[i][j]);
		d2.pb(dist2[i][j]);
	}
	
	long double lo=0,hi=1e15;
	rep(t,100){
		long double mi=(lo+hi)/2;
		long double sum=0;
		rep(i,sz(d1)){
			sum+=min((long double)d1[i],d2[i]+mi);
		}
		if(sum>mi*sz(d1))lo=mi;
		else hi=mi;
	}
	printf("%.16f\n",min((double)d1[start],(double)(d2[start]+hi)));
}

Measured memory_bytes: 10040
from collections import deque

n,m=map(int,input().split())
a=deque(map(int,input().split()))
bc=[list(map(int,input().split())) for _ in range(m)]
bc.sort(key=lambda x: x[1])
bc=bc[::-1]
l=0
for b,c in bc:
  if l>n:
    break
  else:
    d=[c]*b
    a.extend(d)
    l+=b


a=list(a)
#print(a)
a.sort(reverse=1)
a=a[:n]





print(sum(a))
#print(a)

Measured memory_bytes: 36460
#include<bits/stdc++.h>
constexpr long long INFL = 1LL << 60;
constexpr int INF = 1 << 30;

using namespace std;

using ll = long long;
using P = tuple<int, int>;
using iarr = valarray<int>;

int main()
{
    char c;
    cin >> c;
    if(c == 'a' || c == 'i' ||c == 'u' || c == 'e' ||c == 'o'){
        cout << "vowel" << endl;
    }else{
        cout << "consonant" << endl;
    }
    return 0;
}



Measured memory_bytes: 256
// +build ignore
package main

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

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []byte {
	return []byte(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

func run(input io.Reader, output io.Writer) int {
	sc := NewScanner()
	S := sc.nextStr()
	if S[2] == S[3] && S[4] == S[5] {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
	return 0
}

func main() {
	os.Exit(run(os.Stdin, os.Stdout))
}


Measured memory_bytes: 640
# import math
# import statistics
#a=input()
#b,c=int(input()),int(input())
#c=[]
#for i in a:
#   c.append(i)
#e1,e2,e3,e4 = map(int,input().split())
f = list(map(int,input().split()))
#g = [input() for _ in range(a)]

if 1 in f and 9 in f and 7 in f and 4 in f :
    print("YES")
else:
    print("NO")


Measured memory_bytes: 9076
#include <bits/stdc++.h> 
using namespace std; 
typedef long long int ll;
typedef long double ld;
typedef unsigned long long int ull;
const long long int m=pow(10,9)+7;

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int x ;
    cin >> x ;
    int num = x % 100 ;
    x /= 100 ;
    if ( 5 * x >= num ) cout << 1 << endl ;  
    else cout << 0 << endl ;  
    return 0;
}


Measured memory_bytes: 3580
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <cmath>
#include <stack>
#include <string>
#include <deque>
#include <map>
#include <algorithm>

using namespace std;
//--------------------
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

//------------
void func() {
    int N, K,oneIndex;
    cin >> N >> K;
    int arr[N];
    for (int i = 0; i < N; ++i) {
        cin >> arr[i];
        if (arr[i] == 1 ) {
            oneIndex = i;
        }
    }
//    int left = max(0,oneIndex + 1 - K);
    int ans = 1e6;
//    for (int j = left; j <= oneIndex; ++j) {
//        int right = N - 1 - min(N - 1,K + left - 1);
//        ans = min((left % K == 0 ? (left / K)  : (left / K + 1)) + (right % K == 0 ? (right / K) : (right / K + 1)),ans);
//    }
    cout << (N - K ) / (K - 1) + ((N - K) % (K - 1) == 0 ? 1 : 2) << endl;
}

int main() {
    func();
    return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
using namespace std;
long long ttt(long long n,long long x,long long *arr,long long *brr)
{
	if(x<=n)		//提前结束并不会使下面循环x<=0 
	{
		return 0;	
	}
	if(n==1)
	{
		if(x==1)
		{
			return 0;
		}
		else if(x==2)
		{
			return 1;
		}
		else if(x==3)
		{
			return 2;
		}
		else
		{
			return 3;
		}
		if(x==5)
		{
			return 3;
		}
	}
	if(n==0)
	{
		return 1;
	 } 
	 if(x==arr[n])
	 {
	 	return brr[n];
	 }
	while(1)
	{
		if(arr[n]/2==x)
		{
			return brr[n-1];
		}
		else if(arr[n]/2>x)
		{
			n--;
			x--;
		}
		else
		{
			break;
		}
	}
	long long sum=brr[n-1]+ttt(n-1,x-arr[n-1]-2,arr,brr)+1;//加中间那个肉片 
	return sum;
	
}
int main()
{
	long long n,x;
	cin>>n>>x;
	long long arr[51];
	long long brr[51];
	brr[0]=1;
	arr[0]=1;
	for(int i=1;i<=n;i++)
	{
		arr[i]=arr[i-1]*2+3;
		brr[i]=brr[i-1]*2+1;
	}
	long long sum=ttt(n,x,arr,brr);
	cout<<sum;
}

Measured memory_bytes: 256
n = int(input())
a = input().split()
max = -1000000
min = 1000000
sum = 0
for i in range(0,n):
	sum = sum + int(a[i])
	if int(a[i]) > max:
		max = int(a[i])
	if int(a[i]) < min:
		min = int(a[i])

print(str(min) + " " + str(max) + " " + str(sum))

Measured memory_bytes: 8308
#include <stdio.h>
#include <stdbool.h>

bool binarySearch(int A[], int n, int key)
{
    int left = 0;
    int right = n;
    int mid;

    while (left < right) {
        mid = (left + right) / 2;
        if (key == A[mid]) {
            return true;
        } else if (key > A[mid]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return false;
}

int main()
{
    int n, q, t;
    int A[100000];
    int sum = 0;

    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &A[i]);
    }

    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        scanf("%d", &t);
        if (binarySearch(A, n, t)) {
            sum++;
        }
    }

    printf("%d\n", sum);
    return 0;
}


Measured memory_bytes: 2104