akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <numeric>
using namespace std;

bool complex_s(string& s, int a, int b, int c, int d) {
	if (c < d && s.find("##", a) > d || c < b && s.find("##", a) > c && s.find("##", b) > d) {
		return true;
	}
	else if (s.find("##", a) < max(c, d) || s.find("...", b - 1) >= d - 1) {
		return false;
	}
	else {
		return true;
	}
}

bool simple_solve(string& s, int a, int b, int c, int d) {
	if (c < d) {
		while (b < d) {
			if (s[b] == '#') return false;
			if (s[b + 1] == '.') {
				++b;
			}
			else b += 2;
		}
		while (a < c) {
			if (s[a] == '#') return false;
			if (s[a + 1] == '.') ++a;
			else a += 2;
		}
		return true;
	}

	while (b < d && s[b - 1] != '.' || s[b + 1] != '.') {
		if (s[b] == '#') return false;
		if (s[b + 1] == '.') {
			++b;
		}
		else b += 2;
	}
	if (s[b - 1] != '.' || s[b + 1] != '.') return false;
	while (a < c) {
		if (s[a] == '#') return false;
		if (s[a + 1] == '.'&& a + 1 != b) ++a;
		else a += 2;
	}
	return true;
}

string gen_random(const int len) {
	static const char alphanum[] =".#";
	string res(len, '.');
	for (int i = 0; i < len; ++i) {
		res[i] = alphanum[rand() % (sizeof(alphanum) - 1)];
	}

	return res;
}

int main()
{
	ios_base::sync_with_stdio(false);
	int n, a, b, c, d;
	cin >> n >> a >> b >> c >> d;
	--a;
	--b;
	--c;
	--d;
	string s;
	cin >> s;
	if (s.find("##", a) < c || s.find("##", b) < d || c > d && s.find("...", b - 1) > d - 1)
		cout << "No\n";
	else cout << "Yes\n";
	return 0;
}


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

int main()
{
	while(!cin.eof())
	{
		long a[8] = {0};
		for(int i = 0; i < 8; i++)
		{
			long x;
			cin >> x;
			for(int j = 0; j < 8; j++)
			{
				a[i] += (x % 10) << j;
				x /= 10;
			}
		}
		if(cin.eof())
			break;

		char c = 'A';
		for(int i = 0; i < 7; i++)
			for(int j = 0; j < 7; j++)
				if(a[i] == 3 << j)
					if(a[i + 1] == 3 << j)
						goto END;

		c = 'B';
		for(int i = 0; i < 5; i++)
			for(int j = 0; j < 8; j++)
				if(a[i] == (1 << j))
					if(a[i + 1] == (1 << j))
					{
						//cout << "B " << (1 << j) << endl;
						goto END;
					}

		c = 'C';
		for(int i = 0; i < 8; i++)
			for(int j = 0; j < 5; j++)
			{
				//cout << 'C' << ' ' << (15 << j) << endl;
				if(a[i] == 15 << j)
					goto END;

			}
		c = 'D';
		for(int i = 0; i < 6; i++)
			for(int j = 0; j < 7; j++)
				if(a[i] == 1 << j)
					if(a[i + 1] == 3 << j)
						goto END;

		c = 'E';
		for(int i = 0; i < 7; i++)
			for(int j = 0; j < 7; j++)
				if(a[i] == 3 << j)
					if(a[i + 1] == 3 << (j-1))
						goto END;

		c = 'F';
		for(int i = 0; i < 6; i++)
			for(int j = 0; j < 8; j++)
				if(a[i] == 1 << j)
					goto END;

		c = 'G';
		for(int i = 0; i < 7; i++)
			for(int j = 0; j < 6; j++)
				if(a[i] == 3 << j)
					if(a[i + 1] == 3 << (j + 1))
						goto END;

		cout << "error" << endl;
		break;

	END:
		cout << c << endl;
	}
	return 0;
}

Measured memory_bytes: 1152
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main(void)
{
	int A,B,C,D,P,all;
	scanf("%d %d %d %d %d",&A,&B,&C,&D,&P);
	if(P<=C){}
	else{
		B+=(P-C)*D;
	}
	all=min(A*P,B);
	printf("%d\n",all);
	return 0;
}


Measured memory_bytes: 3216
#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000000+7;
const long long INF=-mod;

//マクロ
//型エイリアス
using ll = long long;
using P=pair<long long,long long>;
using vl=vector<long long>;
//ショートカット
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,k,n) for(int i=k;i<n;i++) //半開区間
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
//入力
#define vin(v,N) for(long long i=0;i<N;i++) cin>>v.at(i)
#define lin(n) long long n;cin>>n
#define vlin(v,N) vector<long long>v(N);for(long long i=0;i<N;i++)cin>>v.at(i)

//関数
//最大公約数
long long gcd(long long m,long long n){
  long long a=max(m,n);
  long long b=min(m,n);
  long long r=a%b;
  while(r!=0){
    a=b; b=r; r=a%b;
  }
  return b;
}
// 最小公倍数
long long lcd(long long m,long long n){
  return m*n/gcd(m,n);
}
//xのn乗
long long power(long long x,long long N){
  long long ret=1;
  for(long long i=0;i<N;i++)   
    ret*=x;
  return ret;
}
//nCr
long long C(long long n, long long r);
//nCr (mod)
long long modC(long long n, long long r) {
    vector<long long> f(n+1),inv(n+1),invf(n+1);
    f[0]=f[1]=1;
    invf[0]=invf[1]=1;
    inv[1]=1;
    for (long long i=2;i<n+1;i++) {
        f[i]=(i*f[i-1])%mod;
        inv[i]=mod-((mod/i)*inv[mod%i])%mod;
        invf[i]=(inv[i]*invf[i-1])%mod;
    }
    long long cmb=f[n]*(invf[r]*invf[n-r]%mod)%mod;
    if (n>=r) return cmb;
    else return 0;
}
//素因数分解(mapで返す)
map<long long,long long> factor(long long p){
  ll p1=p;
  map<long long,long long>ret;
  for(long long i=2;i*i<=p1;i++){
     while(p%i==0){
      ret[i]++;
      p/=i;
    }
  }
  if(p!=1)
  ret[p]++;
  return ret;
}
//素数判定
bool is_prime(long long N){
  for(long long i=2;i*i<=N;i++){
    if(N%i==0)
      return false;
  }
  return true;
}
//最大値更新
void chmax(long long &a,long long b){
  a=max(a,b);
}
//最小値更新
void chmin(long long &a,long long b){
  a=min(a,b);
}

//メイン関数
int main(){
  //doubleの桁数
  cout<<fixed<<setprecision(10);
  
  lin(N);lin(M);
  char A[N][N];
  char B[M][M];
  rep(i,N){
    string s;cin>>s;
    rep(j,N){
      A[i][j]=s[j];
    }
  }
  rep(i,M){
    string s;cin>>s;
    rep(j,M){
      B[i][j]=s[j];
    }
  }
  
  bool OK=false;
  
  for(int sh=0;sh+M<=N;sh++){
    for(int sw=0;sw+M<=N;sw++){
      bool NG=false;
      for(int i=0;i<M;i++){
        for(int j=0;j<M;j++){
          if(A[i+sh][j+sw]!=B[i][j]){
            NG=true;
            //cout<<"NG "<<A[i+sh][j+sw]<<" "<<B[i][j]<<endl;
          }
          else{
           // cout<<"OK "<<A[i+sh][j+sw]<<" "<<B[i][j]<<endl;
          }
        }
      }
      if(!NG){
        OK=true;
        //cout<<sh<<" "<<sw<<endl;
      }
    }
  }
  
  if(OK)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
}

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

int p[8][3] = {
    {0,1,2},
    {3,4,5},
    {6,7,8},
    {0,3,6},
    {1,4,7},
    {2,5,8},
    {0,4,8},
    {2,4,6}
};

int main(){
    VI a(9);
    rep(i,9) cin >> a[i];
    int n;
    cin >> n;
    VI b(n);
    rep(i,n) cin >> b[i];

    rep(i,n){
        rep(j,9){
            if(b[i] == a[j]) a[j] = 0;
        }
    }

    bool bingo = false;
    rep(i,8){
        bool flag = true;
        rep(j,3){
            if(a[p[i][j]] != 0) flag = false;
        }
        if(flag) bingo = true;
    }

    if(bingo) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
N,Q=map(int,input().split())
ans=[0]*N
ki=[[] for _ in range(N)]
for i in range(N-1):
 a,b=map(int,input().split())
 ki[a-1].append(b-1)
 ki[b-1].append(a-1)
for i in range(Q):
 p,q=map(int,input().split())
 ans[p-1]+=q
# dfs
from collections import deque
stack =deque([0])
visited = ["False"] * N
while stack:
 ne = stack.popleft()
 if visited[ne] == "False":
  visited[ne] = "True"
  for j in ki[ne]:
   if visited[j] == "False":
    ans[j]+=ans[ne]
    stack.append(j)
print(*ans)


Measured memory_bytes: 93972
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,n) for(int i=1;i<=n;i++)
const ll MOD = 1000000007;
long long modinv(long long a, long long m=MOD) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
    /*MODの割り算の際に
    a/＝b;
    を
    a *= modinv(b,MOD);
    とする。
        */
}
int N;
const int MAXN = 200001;
const int MAXA = 1000005;
int dp[MAXA]; //dp[i][j] iをjで割ったあまり
int A[MAXN];

bool ok[MAXN];
int same[MAXA];
int main(){
    cin >> N;
    rep(i,N)cin >> A[i];
    rep(i,MAXA){        
        same[i] = 0;
        dp[i] = false;
    }

    sort(A,A+N);
    int ans = 0;
    rep(i,N){
        if(same[A[i]]!=0){
            same[A[i]] = 2;
            continue;
        }else{
            for(int j=A[i];j<MAXA;j+=A[i])same[j]++;
        }
    }
    rep(i,N) {
        if(same[A[i]]==1)ans++;
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 12204
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define MAXN 200005
//#define ivorysi
#define space putchar(' ')
#define enter putchar('\n')
using namespace std;
typedef long long int64;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 + c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
int N,P[MAXN],val[MAXN],ans[MAXN],curx,cury;
struct node {
    int maxv,L,R,lc,rc;
}tr[MAXN * 20];
int rt[2],Ncnt;
void build(int &u,int L,int R,int v) {
    u = ++Ncnt;
    tr[u].L = L;tr[u].R = R;
    tr[u].maxv = v;
    if(L == R) return;
    int mid = (L + R) >> 1;
    build(tr[u].lc,L,mid,v);
    build(tr[u].rc,mid + 1,R,v);
}
void Change(int u,int pos,int v) {
    if(tr[u].L == tr[u].R) {tr[u].maxv = v;return;}
    int mid = (tr[u].L + tr[u].R) >> 1;
    if(pos <= mid) Change(tr[u].lc,pos,v);
    else Change(tr[u].rc,pos,v);
    tr[u].maxv = max(tr[tr[u].lc].maxv,tr[tr[u].rc].maxv);
}
int Query(int u,int l,int r) {
    if(tr[u].L == l && tr[u].R == r) return tr[u].maxv;
    int mid = (tr[u].L + tr[u].R) >> 1;
    if(r <= mid) return Query(tr[u].lc,l,r);
    else if(l > mid) return Query(tr[u].rc,l,r);
    else return max(Query(tr[u].lc,l,mid),Query(tr[u].rc,mid + 1,r));
}
void Solve() {
    read(N);
    for(int i = 1 ; i <= N ; ++i) read(P[i]);
    int cur = 0,Q = 0;
    for(int i = 1 ; i <= N ; ++i) {
	cur = max(cur,P[i]);
	if(cur == P[i]) {val[i] = 2;++Q;}
	else val[i] = 1;
    }
    build(rt[0],1,N + 1,0);build(rt[1],1,N + 1,-2 * N);
    for(int i = N ; i >= 1 ; --i) {
	int tmp[2];
	for(int j = 0 ; j < 2 ; ++j) tmp[j] = Query(rt[j],P[i] + 1,N + 1);
	for(int j = 0 ; j < 2 ; ++j) {
	    if(tmp[j] + val[i] > 0) {
		int t = (tmp[j] + val[i]) & 1;
		Change(rt[t],P[i],tmp[j] + val[i]);
	    }
	}
    }
    int len[2] = {0,0},mx_num[2] = {0,0};
    for(int i = 1 ; i <= N ; ++i) {
	ans[i] = -1;
	Change(rt[0],P[i],0);Change(rt[1],P[i],-2 * N);
	if(val[i] == 2) --Q;
	for(int k = 0 ; k < 2 ; ++k) {
	    int nxt_len[2],nxt_mx_num[2];
	    memcpy(nxt_len,len,sizeof(len));
	    memcpy(nxt_mx_num,mx_num,sizeof(mx_num));
	    nxt_mx_num[k] = max(nxt_mx_num[k],P[i]);
	    if(nxt_mx_num[k] == P[i]) ++nxt_len[k];
	    if(i == N) {
		if(nxt_len[0] == nxt_len[1]) {ans[i] = k;break;}
		continue;
	    }
	    bool flag = 0;
	    
	    for(int j = 0 ; j < 2 ; ++j) {
		int t = nxt_len[j] - nxt_len[j ^ 1] + Q;
		if(t >= 0 && Query(rt[t & 1],nxt_mx_num[j ^ 1] + 1,N + 1) >= t) {flag = 1;break;}
	    }
	    if(flag) {
		ans[i] = k;
		memcpy(len,nxt_len,sizeof(len));
		memcpy(mx_num,nxt_mx_num,sizeof(mx_num));
		break;
	    }
	}
	if(ans[i] < 0) {
	    puts("-1");return;
	}
    }
    for(int i = 1 ; i <= N ; ++i) putchar('0' + ans[i]);
    enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}



Measured memory_bytes: 19456
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n; i >= 0; i--)
#define reprr(i, m, n) for (ll i = m; i < n; i++)
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;


int main()
{
    ll X, Y, Z, K; cin >> X >> Y >> Z >> K;
    vll A(X); rep(i, X) cin >> A[i];
    vll B(Y); rep(i, Y) cin >> B[i];
    vll C(Z); rep(i, Z) cin >> C[i];
    sort(all(A));
    reverse(all(A));
    sort(all(B));
    reverse(all(B));
    sort(all(C));
    reverse(all(C));

    priority_queue<pair<ll, vector<ll>>> que;
    vvll used;
    que.push({A[0] + B[0] + C[0], {0, 0, 0}});

    rep(i, K) {
        pair<ll, vector<ll>> elem;
        do {
            elem = que.top(); que.pop();
        } while (find(all(used), elem.second) != used.end());
        cout << elem.first << endl;
        used.push_back(elem.second);
        ll a = elem.second[0], b = elem.second[1], c = elem.second[2];
        //cout << "a: " << a << ", b: " << b << ", c: " << c << endl;
        //cout << "a: " << A[a] << ", b: " << B[b] << ", c: " << C[c] << endl;
        if (a < X - 1) que.push({A[a+1] + B[b] + C[c], {a+1, b, c}});
        if (b < Y - 1) que.push({A[a] + B[b+1] + C[c], {a, b+1, c}});
        if (c < Z - 1) que.push({A[a] + B[b] + C[c+1], {a, b, c+1}});
    }
    return 0;
}

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

int main(){
    ll n;
    cin >> n;
    vector<ll> vec(3*n);
    for(ll i = 0;i < 3*n;i++){
        cin >> vec[i];
    }
    sort(vec.begin(),vec.end());
    reverse(vec.begin(),vec.end());
    ll sum = 0;
    int i = 1;
    while(n){
        sum += vec[i];
        i += 2;
        n--;
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;


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


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

int main(){
    int n,pa=0,pb=0;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a.begin(),a.end(),greater<int>());
    for(int i=0;i<n;i++){
        if(i%2==0) pa+=a[i];
        else pb+=a[i];
    }
    cout<<pa-pb<<endl;
    return 0;
}

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

using namespace std;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

typedef long long  ll;
#define endl '\n'




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


const int MOD = 1000000007;

//////////////////////////////////////////


ll l, r;

void Input() {

    cin >> l >> r;
}



void Solve() {

    if(r - l > 2018) {

        cout << "0" << endl;
        return;
    }

    ll ans = 9000000000000;

    for(ll i = l; i < r; i++) {

        for(ll j = i+1; j <= r; j++) {

            ans = min(ans, (i%2019*j%2019) % 2019);
        }
    }

    cout << ans << endl;


}

int main() {

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


  return 0;

}



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

#define ll long long
#define pb push_back
#define vi vector<int>
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define sizeOf(A) (sizeof(A))/(sizeof(A[0]))
#define odd(x) ((x) % (2))

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

    int n;
    ll k;
    cin >> n >> k;
    vector<pair<int, int>> A;
    FOR(i, 0, n) {
        int a, b;
        cin >> a >> b;
        A.pb(make_pair(a, b));
    }

    sort(A.begin(), A.end());
    ll x = 0, i = 0;
    while (x < k && i < A.size()) {
        x += A[i].second;
        i++;
    }
    ll size = A.size();
    //int pointer = min(A.size(), i);
    cout << A[i-1].first << "\n";
    return 0;
}


Measured memory_bytes: 1400
#include <stdio.h>
#include <string.h>
#define LEN 100005
 
typedef struct pp {
  char name[100];
  int t;
} P;
 
P Q[LEN];
int head, tail, n;
 
void enqueue(P x) {
  Q[tail] = x;
  tail = (tail + 1) % LEN;
}
 
P dequeue() {
  P x = Q[head];
  head = (head + 1) % LEN;
  return x;
}
 
int min(int a,int b) {
  return a < b ? a : b; 
}
 
int main() {
  int elaps = 0, c;
  int i, q;
  P u;
  char str[64];
  
  scanf("%d %d",&n ,&q);
  for(i=1; i<=n; i++) {
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }
  head = 1; tail = n + 1;
 
  while(head != tail) {
    u = dequeue();
    c = min(q, u.t);
    u.t -= c;
    elaps += c;
    if(u.t > 0) enqueue(u);
    else {
      printf("%s %d\n",u.name,elaps);
    }
  }
  return 0;
}


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

#define sz(s) (int)(s).size()
#define re(i, n) for (int i = 1; i <= n; i ++)
#define pb push_back
#define finish(x) return cout << x << endl, 0
#define MP make_mair
#define trav(x, a) for(auto& x: a)
#define all(x) (x).begin,(x).end()
#define Sor(x) sort(all(x))
#define REV(x) reverse(all(x))
#define F first
#define S second
#define I insert
#define N 222222
#define MOD 100000007

using namespace std;

typedef long long ll;
vector <ll> vll;
template <class T> bool umin(T& a, T b) {if(a>b){a = b; return 1;}return 0;}
template <class T> bool umax(T& a, T b) {if(a<b){a=b; return 1;}return 0;}
template <class T, class TT> bool pal(T a, TT n){int k = 0; for(int i =0; i <= n / 2; i ++){if(a[i]!=a[n-i-1]){k=1;break;}}return k?0:1;}

ll powmod(ll a, ll b, ll m = MOD){ll r = 1;while(b>0){if(b&1)r=r*a%m;a=a*a%m;b>>=1;}return r;}


int main()
{	
	int n, m;
	cin >> n >> m;
	if (n < m)
	{
		cout << 1;
	}
	else
	{
		if (n % m == 0)
		{
			cout << n / m;
		}
		else
		{
			cout << (n / m) + 1;
		}
	}









	getchar();
	getchar();
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n) ; ++i)
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define emb emplace_back

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

template<typename T> void pv(vector<T> vec) {
  cout << "[";
  for(auto& v : vec) { cout << v << ","; }
  cout << "]" << endl;
}

template<>
void pv(vector<P> vec) {
  cout << "[";
  for(auto& v : vec) {
    cout << "<" << v.fi << ","<< v.se << ">" << ",";
  }
  cout << "]" << endl;
}

int main() {
  int k,x;
  cin >> k >> x;
  if(k*500 >= x) cout << "Yes" <<endl;
  else cout << "No" <<endl;

  return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<time.h>
#include<sstream>
#define MINN -1e8 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll INF=0x3f3f3f3f3f3f;
const int P=1e9+7;
const int MAXN=32000;
//const int MINN=-1e8;
//const ll mod=;

//map<string,ll> m;
//map<ll,ll> m;

//set<ll> s;

//vector<ll> v;

//scanf("%lld",&t);
//scanf("%lld%lld",&,&);
int a[200005],b[200005]={0},c[200005]={0},que[200005];
int n,k;
int main(void)
{
	cin>>n>>k;
	int cnt=n-k+1;
	for(int i=0;i<n;i++)scanf("%d",&a[i]);
	
	
	for(int i=0,h=0,t=0;i<n;i++)
 	{
		while(t>h&&a[que[t-1]]>=a[i])
			t--;
		que[t++]=i;
 		if(i<k-1)continue;
 		else
 		{
 			if(i!=k-1)
 			{
 				while(que[h]<i-k+1)
				h++;
			}
	 		b[i]=a[que[h]];
		}
		
	}
	for(int i=0,h=0,t=0;i<n;i++)
 	{
		while(t>h&&a[que[t-1]]<=a[i])
			t--;
		que[t++]=i;
 		if(i<k-1)continue;
 		else
 		{
 			if(i!=k-1)
 			{
 				while(que[h]<i-k+1)
				h++;
			}
	 		c[i]=a[que[h]];
		}
		
	}
//
//	for(int i=0;i<n;i++)
//	cout<<b[i]<<" ";
//	cout<<endl;
//	for(int i=0;i<n;i++)
//	cout<<c[i]<<" ";
//	cout<<endl;



	//cout<<maxn<<" "<<minn<<endl;
	for(int i=k-1;i<n-1;i++)
	{
		if(a[i-k+1]==b[i]&&a[i+1]>=c[i])cnt--;
	}
	int tmp=0,cur=1;
	for(int i=1;i<n;i++)
	{
		if(a[i]>a[i-1])cur++;
		else
		{
			if(cur>=k)tmp++;
			cur=1;
		}
	}
	if(cur>=k)tmp++;
	//cout<<cnt<<endl;
	if(tmp>0)cnt=cnt-tmp+1;
	//cout<<tmp<<endl;
	cout<<cnt;
	return 0;
}
//ll n,m,t,a,x,ans,res;
//ll powmod(ll a,ll b)     //快速幂 
//{
//	ll tmp=a%mod;
//	ll ans=1;
//	while(b)
//	{
//		if(b&1)ans=ans*tmp%mod;
//		tmp=tmp*tmp%mod;
//		b>>=1;
//	}
//	return ans%mod;
//}


//bool is_prime(ll a)     //判断素数 
//{
//	if(a==2)return 1;
//	else if(a==1||a%2==0)return 0;
//	else
//	{
//		for(ll i=3;i*i<=a;++i)
//		{
//			if(a%i==0)return 0;
//		}
//	}
//	return 1;
//}



Measured memory_bytes: 3328
# coding: utf-8
# Your code here!


N = int(input())
S = input()
K = int(input())

char = S[K - 1]
# print(char)

ret = ''

for i in range(len(S)):
    if S[i] != char:
        ret += '*'
    else:
        ret += S[i]

print(ret)


Measured memory_bytes: 2940
# include<iostream>
# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std;
int main()
{
    int a,b,t;
	scanf("%d %d",&a,&b);
    t=a-b;
    if(t<=0)t=0;
    printf("%d\n",t);
    return 0;
}

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

vector<int> dw = {1, 0, -1, 0};
vector<int> dh = {0, 1, 0, -1};

struct Edge { ll h, w, cost; };
vector<Edge> G[1001][1001];

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

  ll H; cin >> H;
  ll W; cin >> W;
  ll Ch; cin >> Ch; Ch--;
  ll Cw; cin >> Cw; Cw--;
  ll Dh; cin >> Dh; Dh--;
  ll Dw; cin >> Dw; Dw--;

  vector<vector<ll>> cells(H, vector<ll>(W, 0));
  vector<vector<ll>> times(H, vector<ll>(W, 1e15));
  for (ll i = 0; i < H; i++) {
    string S; cin >> S;
    for (ll j = 0; j < W; j++) {
      if (S[j] == '#') cells[i][j] = 1;
    }
  }

  for (ll i = 0; i < H; i++) {
    for (ll j = 0; j < W; j++) {
      for (ll k = 0; k < 4; k++) {
        ll nh = i + dh[k];
        ll nw = j + dw[k];
        if (nh < 0 || nw < 0 || nh >= H || nw >= W) continue;
        if (cells[nh][nw] > 0) continue;
        G[i][j].emplace_back(Edge({nh, nw, 0}));
      }

      for (ll k = -2; k <= 2; k++) {
        for (ll l = -2; l <= 2; l++) {
          ll nh = i + k;
          ll nw = j + l;
          if (nh < 0 || nw < 0 || nh >= H || nw >= W) continue;
          if (cells[nh][nw] > 0) continue;
          G[i][j].emplace_back(Edge({nh, nw, 1}));
        }
      }
    }
  }

  priority_queue<P, vector<P>, greater<P>> q;
  times[Ch][Cw] = 0;
  q.push(P(0, {Ch, Cw}));

  while (!q.empty()) {
    P p = q.top(); q.pop();
    int h = p.second.first, w = p.second.second;
    if (times[h][w] < p.first) continue;
    for (int i = 0; i < G[h][w].size(); i++) {
      Edge e = G[h][w][i];
      if (times[e.h][e.w] > times[h][w] + e.cost) {
        times[e.h][e.w] = times[h][w] + e.cost;
        q.push(P(times[e.h][e.w], {e.h, e.w}));
      }
    }
  }

  ll ans = times[Dh][Dw];
  if (ans >= 1e15) ans = -1;
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 524104
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
P=[i for i in range(N+1)]
size=[1 for i in range(N+1)]

def find(a):
    if a==P[a]:
        return a
    else:
        return find(P[a])
        
def union(b,c):
    B=find(b)
    C=find(c)
    if P[B]<P[C]:
        P[C]=P[B]
    else:
        P[B]=P[C]
L=[]
for i in range(M):
    a,b=map(int,input().split())
    L.append([a,b])
    union(a,b)

p=[i for i in range(N+1)]
for i in range(1,N+1):
    p[i]=find(i)
One=0
Two=0
Other=0
for i in range(1,N+1):
    if p[i]==2:
        Two+=1
    elif p[i]==1:
        One+=1
    else:
        Other+=1
if One>Two:
    One+=Other
else:
    Two+=Other

print((One*(One-1)//2)+(Two*(Two-1)//2)- M)


Measured memory_bytes: 129312
#include<iostream>
#include<algorithm>

using namespace std;
int main() {
	string S, T;
	cin >> S >> T;
	int ans = 2e6;
	for (int i = 0; i + T.length() <= S.length(); i++) {
		int temp = 0;
		for (int j = 0; j < T.length(); j++) {
			if (S[i + j] != T[j]) {
				temp++;
			}
		}
		ans = min(ans, temp);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3576
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC080A
{
    class Program
    {
        static void Main(string[] args)
        {
            int n, a, b, p1, p2, x;

            var word = Console.ReadLine().Split(' ');

            n =int.Parse(word[0]);
            a = int.Parse(word[1]);
            b = int.Parse(word[2]);

            x = a * n;

            x = b;

            if (a * n < b)
                x = a * n;

            else if (a * n > b) 
                x = b;

            Console.WriteLine(x);

            Console.ReadKey();

        }
    }
}


Measured memory_bytes: 13140
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long ll;

int main() {
    int n;  cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    sort(a.begin(), a.end(), greater<ll>());
    if (n % 2) {
        ll ans = 0;
        for (int i = 0; i <= n/2 - 2; i++)
            ans += 2*a[i];
        ans += a[n/2-1] + a[n/2];
        for (int i = n/2+1; i < n; i++)
            ans -= 2 * a[i];
        ll tmp = 0;
        sort(a.begin(), a.end());
        for (int i = 0; i <= n/2 - 2; i++)
            tmp -= 2*a[i];
        tmp -= a[n/2-1] + a[n/2];
        for (int i = n/2+1; i < n; i++)
            tmp += 2 * a[i];
        ans = max(ans, tmp);
        cout << ans << endl;
        return 0;
    }
    else {
        ll ans = 0;
        for (int i = 0; i < n/2-1; i++)
            ans += 2*a[i];
        ans += a[n/2-1];
        ans -= a[n/2];
        for (int i = n/2+1; i < n; i++)
            ans -= 2*a[i];
        cout << ans << endl;
        return 0;
    }
}

Measured memory_bytes: 4032
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    double A = Math.log(N) / Math.log(K);
    int B=(int)A;
    System.out.println( B+1 );  
  }
}


Measured memory_bytes: 21588
def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b

N, T = getMN()

maxtime = 10000000000
roots = []
for i in range (N):
    a,b = getMN()
    roots.append((a,b))

for root in roots:
    if root[1] <= T:
        if root[0] < maxtime:
            maxtime = root[0]

if maxtime > 10000000:
    print("TLE")
else:
    print(maxtime)



Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <set>
#include <iomanip>
using namespace std;

int main() {
    int N; cin >> N;
    vector<int> v(N);
    long ans=0;
    for(int i=0; i<N; ++i){
        cin >> v[i];
        ans += abs(v[i]);
    }
    sort(v.begin(), v.end());
    int p=0;
    while(p<N){
        if(v[p]>=0) break;
        ++p;
    }
    if(p%2==1){
        if(p<N) cout << ans+2*max(v[p-1], -v[p]) << endl;
        else cout << ans+2*v[p-1] << endl;
    }
    else cout << ans << endl;
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); ++(i))
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<int, lint> pil;
typedef pair<lint, int> pli;
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T>bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod*mod;
constexpr int MAX = 300010;

vector<int> min_factor(MAX, 0), prime;

void sieve(){
        For(i, 2, MAX){
                if(min_factor[i]==0) {
                        min_factor[i] = i;
                        prime.push_back(i);
                }
                for(int x: prime){
                        if(x>i || i*x>=MAX) break;
                        min_factor[i*x]=x;
                }
        }
}

int main(){
        int n;
        sieve();
        while(scanf("%d", &n) && n){
                auto s=upper_bound(prime.begin(), prime.end(), n);
                auto t=upper_bound(prime.begin(), prime.end(), 2*n);
                printf("%d\n", t-s);
        }
}


Measured memory_bytes: 4304
#include<bits/stdc++.h>
const int MAXN = 3e5;
int N;
int A[MAXN];
int main() {
scanf("%d", &N);
for (int i = 0; i < N; i++) scanf("%d", &A[i]);
for (int i = 0; i < N; i++) A[i] -= i;
std::sort(A, A + N);
int b = A[N / 2];
long long r = 0;
for (int i = 0; i < N; i++) r += abs(A[i] - b);
std::cout << r << '\n';
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007;
using ll = long long;
using namespace std;

const int bound = 1000;
vector<int> g[bound*bound];

// トポロジカルソート
// 入次数が 0 のものから DFS する

int h[bound*bound];		// 入次数
int cnt = 0;

void tps( int p ){
	if( h[p] <= 1  ){
		++cnt;
		if( h[p] == 1 ) h[p] = 0;
		for( auto next : g[p] ) tps( next );
	} else {
		--h[p];
	}
}

// DAG 上の最長経路を求める
// メモ化再帰，EDPC-G

int dist[bound*bound];
bool besucht[bound*bound];

int dfs( int p ){
	if( besucht[p] ) return dist[p];
	besucht[p] = true;
	int res = 0;
	for( auto nextp : g[p] ){
		res = max(res, dfs(nextp)+1);
	}
	return dist[p] = res;
}

int main(){
	int n; cin >> n;
    set<int> candy;
	int prev = 0, cur = 0;
	for( int i = 0; i < n; ++i ){
		for( int j = 0; j < n-1; ++j ){
			prev = cur;
			int a = i, b; cin >> b; --b;
			if( a > b ) swap(a, b);
			cur = bound*a+b;
			candy.insert(cur);
			if( j == 0 ) continue;
			g[prev].push_back(cur);
			++h[cur];
		}
	}
	vector<int> zerocandy;
	for( auto p : candy ) if( h[p] == 0 ) zerocandy.push_back(p);
	for( auto p : zerocandy ) tps(p);
	// トポロジカルソートが完了する ⇔ DAG であるから cnt を見て閉路判定
	if( cnt != candy.l_ength() ){
		cout << -1 << endl;
		return 0;
	}
	int ans = 0;
	for( auto p : candy ) ans = max(ans, dfs(p));
	cout << ans+1 << endl;
}

Measured memory_bytes: 71552
#include <stdio.h>
#include <math.h>
int main(void){
    double a,b,x;
    double ans;
    scanf("%lf%lf%lf",&a,&b,&x);
    if(a*a*b<=2*x){
        ans=atan((a*a*b-x)*2.0/a/a/a);
    }
    else{
        ans=atan(b/(x*2.0/b/a));
    }
    printf("%f\n",ans*180/M_PI);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)
#define debug(x) cerr<<#x<<":"<<x<<endl

typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 100


struct Edge{
	Edge(int arg_to,int arg_capacity,int arg_cost,int arg_rev_index){
		to = arg_to;
		capacity = arg_capacity;
		cost = arg_cost;
		rev_index = arg_rev_index;
	}

	int to,capacity,cost,rev_index;
};

int V;
vector<Edge> G[NUM];
int dist[NUM];
int pre_node[NUM],pre_edge[NUM];


void add_edge(int from,int to,int capacity,int cost){
	G[from].push_back(Edge(to,capacity,cost,G[to].size()));
	G[to].push_back(Edge(from,0,-cost,G[from].size()-1));
}

int min_cost_flow(int source,int sink,int flow){
	int ret = 0;
	while(flow > 0){

		for(int i = 0; i < V; i++)dist[i] = BIG_NUM;
		dist[source] = 0;
		bool update = true;
		while(update){
			update = false;
			for(int node_id = 0; node_id < V; node_id++){
				if(dist[node_id] == BIG_NUM)continue;
				for(int i = 0; i < G[node_id].size(); i++){
					Edge &e = G[node_id][i];
					if(e.capacity > 0 && dist[e.to] > dist[node_id]+e.cost){
						dist[e.to] = dist[node_id]+e.cost;
						pre_node[e.to] = node_id;
						pre_edge[e.to] = i;
						update = true;
					}
				}
			}
		}

		if(dist[sink] == BIG_NUM){
			return -1;
		}

		int tmp_flow = flow;
		for(int node_id = sink; node_id != source; node_id = pre_node[node_id]){
			tmp_flow = min(tmp_flow,G[pre_node[node_id]][pre_edge[node_id]].capacity);
		}
		flow -= tmp_flow;
		ret += tmp_flow*dist[sink];
		for(int node_id = sink; node_id != source; node_id = pre_node[node_id]){
			Edge &e = G[pre_node[node_id]][pre_edge[node_id]];
			e.capacity -= tmp_flow;
			G[node_id][e.rev_index].capacity += tmp_flow;
		}
	}
	return ret;
}

int main(){

	int E,F;
	scanf("%d %d %d",&V,&E,&F);

	int from,to,capacity,cost;
	for(int loop = 0; loop < E; loop++){
		scanf("%d %d %d %d",&from,&to,&capacity,&cost);
		add_edge(from,to,capacity,cost);
	}

	printf("%d\n", min_cost_flow(0,V-1,F));

	return 0;
}



Measured memory_bytes: 3256
#include<iostream>

using namespace std;

int main(void) {

	int a[100], n;

	cin >> n;

	for (int i = 0; i < n; i++) {

		cin >> a[i];

	}

	for (int i = n-1; i >= 0; i--) {

		cout << a[i];

		if (i > 0)
			cout << " ";

		else
			cout << endl;
	}

	

}

Measured memory_bytes: 3068
#A問題
A,B,C=input().split(' ')
#input() 入力を受け付ける
#split() 空白区切り

A=int(A)
B=int(B)
C=int(C)
numberList=[A,B,C]

numberList.sort(reverse=True)

sum=0
sum=numberList[0]*10+numberList[1]+numberList[2]

print(sum)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
#define pb push_back
template<class T>void chmax(T &a,T b){if(a<b)a=b;}
template<class T>void chmin(T &a,T b){if(a>b)a=b;}
constexpr int INF=1000000000000000000;
constexpr int mod=1000000007;
constexpr double eps=1e-12;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
bool prime(int a){
    if(a==1)return false;
    for(int i=2;i*i<=a;i++){
        if(a%i==0)return false;
    }
    return true;
}
vector<int>kaijo;
void init_fact(int n){
    kaijo.resize(n+1);
    kaijo[0]=1;
    for(int i=1;i<=n;i++){
        kaijo[i]=kaijo[i-1]*i;
        kaijo[i]%=mod;
    }
}
int modpow(int a,int b){
    if(b==0)return 1;
    if(b%2)return modpow(a,b-1)*a%mod;
    int memo=modpow(a,b/2);
    return memo*memo%mod;
}
int comb(int a,int b){
    //if(!kaijo[0])init_fact(2000010);
    return kaijo[a]*modpow(kaijo[a-b],mod-2)%mod*modpow(kaijo[b],mod-2)%mod;
}
int inv(int x){
    x=modpow(x,mod-2);
    return x;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){
    double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
    double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
    double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
    double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
    return tc*td<0&&ta*tb<0;
}
bool parallel(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){
    return abs((by-ay)*(dx-cx)-(dy-cy)*(bx-ax))<eps;
}
signed main(){
    int n;
    cin>>n;
    rep(i,n){
        double ax,ay,bx,by,cx,cy,dx,dy;
        cin>>ax>>ay>>bx>>by>>cx>>cy>>dx>>dy;
        if(parallel(ax,ay,bx,by,cx,cy,dx,dy))puts("YES");
        else puts("NO");
    }
    /*
    int n;
    double a[1010],b[1010],c[1010],d[1010];
    cin>>n;
    rep(i,n)cin>>a[i]>>b[i]>>c[i]>>d[i];
    rep(i,n){
        for(int j=i+1;j<n;j++){

        }
    }*/
    return 0;
}


Measured memory_bytes: 3048
#include<bits/stdc++.h>
using namespace std;
int main()
{
 int a,b,c;
  cin>>a>>b>>c;
  if((a==5&&b==7&&c==7)||(a==7&&b==7&&c==5)||(a==7&&b==5&&c==7))
    cout<<"NO"<<endl;
  else
    cout<<"YES\n";
}


Measured memory_bytes: 3584
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int T,n;
ll a[203],num[64];
int s[203];
bool ins(ll x)
{
	for(int i=62;i>=0;i--)
		if((x>>i)&1)
		{
			if(num[i]==0)
			{
				num[i]=x;
				return true;
			}
			x^=num[i];
		}
	return false;
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%lld",&a[i]);
		for(int i=1;i<=n;i++)
			scanf("%1d",&s[i]);
		memset(num,0,sizeof(num));
		int ans=0;
		for(int i=n;i;i--)
		{
			if(s[i]==0) ins(a[i]);
			else if(ins(a[i]))
			{
				ans=1;
				break;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 3716
# coding: utf-8
# Your code here!
K,N=map(int,input().split())

A=list(map(int,input().split()))
B=list(map(lambda x:x+K,A))

A+=B
#print(A)
ans=10**9
for i in range(N):
    ans=min(ans,A[i+N-1]-A[i])
    #print(ans)

print(ans)

Measured memory_bytes: 89904
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef vector<pair<ll,ll>> vp;
#define rep(i,n) for(ll i = 0; i < ll(n); i++)
#define all(v) v.begin() , v.end()
#define inputv(v,n) rep(i,n){\
    ll x;\
    cin>>x;\
    v.push_back(x);\
    }
const ll INF=99999999999999;
const ll MOD=1000000007;
 
int main() {

  int n;
  cin >> n;
  int a,b;
  vector<pair<int,int>> v;
  rep(i,n){
  cin >> a >> b;
  v.push_back(make_pair(b,a));
  }
  sort(v.begin(),v.end());
  int sum = 0;
  bool ans = true;
  rep(i,n){
    sum += v[i].second;
    if(sum > v[i].first){
      ans = false;
    }
  }
  
    if(ans){
    cout << "Yes";
  } else {
    cout << "No";
  }


 
 
 return 0;
}


Measured memory_bytes: 2420
import java.text.ParseException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws ParseException {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String[] lines = sc.nextLine().split("[., ]");
            int c = 0;
            for (int i = 0; i < lines.length; i++) {
                if (lines[i].length() > 2 && lines[i].length() < 7) {
                    System.out.print((c++ == 0 ? "" : " ") + lines[i]);
                }
            }
            if (c > 0) {
                System.out.println();
            }
        }
    }
}


Measured memory_bytes: 25940
using System;
using System.Collections.Generic;
using System.Text;

namespace AtCoder.ABC170
{
    public class Problem1
    {
        public static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(" ");

            var i = Array.IndexOf(input, "0") + 1;

            Console.WriteLine(i.ToString());
        }
    }
}


Measured memory_bytes: 25864
import math
N = int(input())
X = [int(_) for _ in input().split()]

cor_1 = math.ceil(sum(X) / N)
cor_2 = math.floor(sum(X) / N)
ans_1 = [(int(_) - cor_1) ** 2 for _ in X]
ans_2 = [(int(_) - cor_2) ** 2 for _ in X]

ans = min(sum(ans_1), sum(ans_2))
print(ans)


Measured memory_bytes: 3060
#include <iostream>

int main(void){
  int i;
  float a,b,t;
  int sum = 0;
  std::cin >> a >> b >> t;
  for(i = a; i < t+0.5; i = i + a){
    sum += b;
  }
  std::cout << sum << std::endl;
  return 0;
}

Measured memory_bytes: 256
using System;

namespace aoj
{
    class Program
    {
        static void Main(string[] args)
        {
            var count = 0;
            var length = int.Parse(Console.ReadLine());
            for (var i = 0; i < length; ++i)
            {
                var input = int.Parse(Console.ReadLine());
                if (IsPrime(input))
                {
                    ++count;
                }
            }

            Console.WriteLine(count);
        }
        
        static bool IsPrime(int _num)
        {
            if (_num == 2) { return true; }

            if (_num < 2 || _num % 2 == 0) { return false; }

            for (var i = 3; i <= Math.Sqrt(_num); i += 2)
            {
                if (_num % i == 0) { return false; }
            }

            return true;
        }
    }
}



Measured memory_bytes: 17972
n, k = map(int,input().split())
num = [list(map(int, input().split())) for i in range(n)]
num.sort()
sum_a = 0

for i in range(10**5+1):
  sum_a += num[i][1]
  ans = num[i][0]
  if sum_a >= k:
    print(ans)
    break


Measured memory_bytes: 27872
#include <iostream>
#include <cstdio>
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
using namespace std;
typedef long long ll;

int main(void) {
  ll x;
  cin >> x;
  ll t;
  for(t = 1; t*(t+1)/2 < x; ++t)
    ;
  cout << t << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){
	int data,num[100]={0},max,i;

	while(scanf("%d",&data)!=EOF){
			num[data-1]++;
	}

	max=num[0];
	for(i=0;i<100;i++)
		if(num[i]>max)
			max=num[i];

	for(i=0;i<100;i++)
		if(max==num[i])
		printf("%d\n",i+1);

	return 0;
}

Measured memory_bytes: 596
#==========================================================
def General_Binary_Search(L,R,cond,Mode=True,Integer=True,ep=1/(1<<20)):
    """一般的な二部探索を行う.
    L:解の下限
    R:解の上限
    cond:条件(1変数関数,広義単調減少 or 広義単調減少を満たす)
    Mode:True->広義単調増加,False->広義単調減少
    Integer:解を整数に制限するか?
    ep:Integer=Falseのとき,解の許容する誤差
    """

    if Integer:
        if Mode:
            if not cond(R):
                return R+1
            L-=1
        else:
            if not cond(L):
                return L-1
            R+=1

        while R-L>1:
            C=L+(R-L)//2
            if cond(C)^Mode:
                L=C
            else:
                R=C
        if Mode:
            return R
        else:
            return L
    else:
        C=L+(R-L)/2
        while (R-C)>ep:
            if cond(C)^Mode:
                L=C
            else:
                R=C
            C=L+(R-L)/2
        return C
#==========================================================
def g(x):
    S=A[x]
    for i in range(N):
        if i!=x:
            if A[i]<=2*S:
                S+=A[i]
            else:
                return False
    return True
#==========================================================
N=int(input())
A=list(map(int,input().split()))

A.sort()

if not g(N-1):
    print(0)
elif g(0):
    print(N)
else:
    print(N-General_Binary_Search(0,N-1,g,True))

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

using ll = long long;

constexpr ll e9 = 1e9;
vector<ll> x{0, e9, 0};
vector<ll> y{0, 1, 0};
ll S;

void check() {
	ll dx1 = abs(x[0]-x[1]);
	ll dx2 = abs(x[0]-x[2]);
	ll dy1 = abs(y[0]-y[1]);
	ll dy2 = abs(y[0]-y[2]);
	assert(S == abs(dx1 * dy2 - dx2 * dy1));
}

int main() {
	cin >> S;
	y[2] = (S + e9 - 1) / e9;
	x[2] = (e9 - S % e9) % e9;
	for (int i = 0; i < 3; i++) {
		if (i) cout << " ";
		cout << x[i] << " " << y[i];
	}
	cout << endl;
	check();
}

Measured memory_bytes: 256
from _collections import deque


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
import scipy
from collections import deque
#https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_b?lang=en
#B - Counting of Trees
"""
sort, and then check how many next levels we have against the previes level
keep a prevcount, and each level is prev level ** cur elvel
"""
N = gi()
cnt = [0] * N
dist = [0] * N

MOD = 998244353

max_d = 0

for i in range(N):
    dist[i] = gi()
    cnt[dist[i]] += 1
    max_d = max(max_d, dist[i])


def run():
    if cnt[0] != 1 or dist[0] > 0:
        print(0)
        return

    ans = 1
    for i in range(1, max_d + 1):
        if cnt[i] == 0:
            print(0)
            return
        for _ in range(cnt[i]):
            ans *= cnt[i - 1]
            ans %= MOD

    print(ans)


run()


Measured memory_bytes: 24084
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) { // ??¨??????\???????????????????????????????????????
        Scanner sc = new Scanner(System.in);
        int w = sc.nextInt();
        int n = sc.nextInt();
        int[] values = new int[w];
        for (int i = 0; i < values.length; i++) {
            values[i] = i + 1;
        }
        for (int i = 0; i < n; i++) {
            String str = sc.next();
            String[] ab = str.split(",");
            int a = Integer.parseInt(ab[0]) - 1;
            int b = Integer.parseInt(ab[1]) - 1; // a???¨b?????????£???values??????????????????
 
            int c = values[a];
            values[a] = values[b];
            values[b] = c;
        }
        for (int i = 0; i < w; i++) {
            System.out.println(values[i]);
        }
    }
}

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

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            var l = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int h = l[0], w = l[1], k = l[2];
            var map = Enumerable.Repeat(0, h).Select(_ => Console.ReadLine()).ToArray();
            var ans = Enumerable.Repeat(0, h).Select(_ => new int[w]).ToArray();
            
            var no = 0;
            for (var i = 0; i < h; i++) {
               if (!map[i].Contains('#')) {
                  if (i >= 1 && map[i-1][0] != 0) {
                      ans[i] = ans[i-1]; 
                  }
                  
                  continue;
               }
               
               no++;
               var isFirst = true;
               for (var j = 0; j < w; j++) {
                   if (map[i][j] == '#') {
                       if (isFirst)
                           isFirst = false;
                       else
                           no++;
                   }
               
                   ans[i][j] = no;
               }
            }
            
            for (var i = h - 2; i >= 0; i--) {
               if (ans[i][0] == 0)
                   ans[i] = ans[i+1];
            }
            
           foreach (var v in ans) Console.WriteLine(string.Join(" ", v));
        }
    }
}


Measured memory_bytes: 18768
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    ll n,t,x,i,j,k,l,dp[100001],a[100001];
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
        if(i==1)
            dp[i]=0;
        else if(i==2)
            dp[i]=abs(a[i]-a[i-1]);
        else
            dp[i]=min({dp[i-2]+abs(a[i]-a[i-2]),dp[i-1]+abs(a[i]-a[i-1])});
    }
    cout<<dp[n]<<endl;
    return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<n;i++)
int main(){
  ll a,b,k;
  cin >> a >> b >> k;
  rep(i,b-a+1){
    if(i<k||(b-a-i)<k)cout << i+a << endl;
  }
}

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

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define Debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long LL;
typedef long double LD;
typedef unsigned int uint;
typedef pair <int, int> pii;
typedef unsigned long long uLL;

template <typename T> inline void Read(T &x) {
  char c = getchar();
  bool f = false;
  for (x = 0; !isdigit(c); c = getchar()) {
    if (c == '-') {
      f = true;
    }
  }
  for (; isdigit(c); c = getchar()) {
    x = x * 10 + c - '0';
  }
  if (f) {
    x = -x;
  }
}

template <typename T> inline bool CheckMax(T &a, const T &b) {
  return a < b ? a = b, true : false;
}

template <typename T> inline bool CheckMin(T &a, const T &b) {
  return a > b ? a = b, true : false;
}

const int N = 100005;

vector <int> adj[N];
int n, r;

inline int DFS(int x, int p) {
  int r = 0, c = 0;
  for (auto y : adj[x]) {
    if (y != p) {
      int v = DFS(y, x);
      r += v, c += !v;
    }
  }
  return r + max(c - 1, 0);
}

int main() {
#ifdef wxh010910
  freopen("d.in", "r", stdin);
#endif
  Read(n);
  for (int i = 1, x, y; i < n; ++i) {
    Read(x), Read(y);
    adj[x].pb(y), adj[y].pb(x);
  }
  for (; r < n && adj[r].size() <= 2; ++r);
  if (r == n) {
    puts("1");
  } else {
    printf("%d\n", DFS(r, -1));
  }
#ifdef wxh010910
  Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
  return 0;
}


Measured memory_bytes: 7424
# coding : utf-8

import numpy

n = int( input() )

lim_j = int(numpy.sqrt(n))

#素数判定
flag = True
for i in range(1, lim_j+1)[::-1]:
    if( n % i == 0 ):
        flag = False
        x = i
        y = int(n/i)
        break
if flag:
    print(n-1)
else:
    print( (x-1) + (y-1) )

Measured memory_bytes: 21088