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

int N, M;

int main() {
    cin >> N >> M;
    priority_queue<long long> A;
    long long sum = 0;
    long long a;
    for (int i = 0; i < N; i++) {
        cin >> a;
        A.push(a); sum += a;
    }
    for (int i = 0; i < M; i++) {
        a = A.top(); A.pop();
        sum -= (a - a / 2);
        A.push(a / 2);
    }
    cout << sum << endl;
}



Measured memory_bytes: 1400
//#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<set>
#include<queue>
#include<deque>
#include<map>
#include<stack>
#include<bitset>
#include<list>
#include<cassert>
#include<numeric>
#include<iomanip>
 
using namespace std;

const int N = 1e5 + 5;
int n, m;
int deg[N];

int main() 
{
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		deg[u - 1]++;
		deg[v - 1]++;
	}
	for (int i = 0; i < n; i++)
	{
		if (deg[i] % 2 == 1)
		{
			cout << "NO";
			exit(0);
		}
	}
	cout << "YES";



}

 

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
signed main(){
    int n;
    int l[100];
    cin>>n;
    int sum=0;
    rep(i,n){
        cin>>l[i];
        sum+=l[i];
    }
    sort(l,l+n);
    if(l[n-1]*2<sum){
        cout<<"Yes"<<endl;
    }
    else cout<<"No"<<endl;
}
//＼(^q^)／ｵﾜﾀ


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

int main(){
        string s,t,u;
        int a,b;
        cin >> s >> t >> a >> b >> u;

        if(u==s){
                a -= 1;
        }else{
                b -= 1;
        }

        cout << a << endl;
        cout << b << endl;
}

Measured memory_bytes: 384
#include<stdio.h>
int main(){
	int n,i,j,m,M=1e9+7,d[100010]={};
	long long s=1;
	scanf("%d",&n);
	for(i=2;i<=n;i++){
		m=i;
		for(j=2;j<=n;j++){
			for(;m&&m%j==0;m/=j)d[j]++;
		}
	}
	//for(i=0;i<=n;i++)printf("%d %d\n",i,d[i]);
	for(i=0;i<=n;i++)s=(s*(d[i]+1))%M;
	printf("%lld",s);
	return 0;
}

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

#define MOD 1000000007

int N, W;
int w[201];
int dp[202][10002];

int main(){
  while(cin >> N >> W){
    for(int i = 0; i < N; i++){
      cin >> w[i];
    }

    sort(w, w + N);
    memset(dp, 0, sizeof(dp));
    dp[N][0] = 1;

    for(int i = N; i > 0; i--){
      for(int j = 0; j <= W; j++){
        if(dp[i][j] == 0){
          continue;
        }

        if(j + w[i - 1] <= W){
          dp[i - 1][j + w[i - 1]] += dp[i][j];
          dp[i - 1][j + w[i - 1]] %= MOD;
        }
        dp[i - 1][j] += dp[i][j];
        dp[i - 1][j] %= MOD;
      }
    }

    int ans = 0;
    int sum = 0;

    for(int i = 0; i < N; i++){
      for(int j = W - w[i] - sum + 1; j <= W - (i == 0 ? 0 : w[i - 1]) - sum; j++){
        if(j < 0 || W < j){
          continue;
        }

        ans += dp[i][j];
        ans %= MOD;
      }
      sum += w[i];
    }

    cout << ans << endl;
  }
}

Measured memory_bytes: 0
N,K = map(int, input().split())
A = []
for i in range(N):
    a,b = map(int, input().split())
    A.append((a,b))
A.sort()
for i in range(N):
    K -= A[i][1]
    if K <= 0:
        print(A[i][0])
        exit()

Measured memory_bytes: 53208
#include <iostream>

using namespace std;

int main()
{
    int x,y,m[13]={13,1,2,3,4,5,6,7,8,9,10,11,12};
    cin>>x>>y;
    if(m[x-1]>m[y-1])
    {
        cout << "Alice" << endl;
    }
    else if(m[x-1]==m[y-1])
    {
        cout << "Draw" << endl;
    }
    else if(m[x-1]<m[y-1])
    {
        cout << "Bob" << endl;
    }
    return 0;
}


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

int n, m;
vector<int> dp;
vector<vector<int>> g;

int dfs(int v) {
    if (dp[v] != -1) return dp[v];          // 頂点 v が既に探索済み
    if (g[v].size() == 0) return dp[v] = 0; // 頂点 v からのパスが存在しない
    int res = 0;
    for (auto u : g[v]) res = max(res, dfs(u));
    return dp[v] = res + 1;
}

int main() {
    cin >> n >> m;
    dp.assign(n, -1); // dp[i] = -1 : 頂点iが未探索
    g.resize(n);
    
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        g[x].push_back(y);
    }
    
    int ans = 0;
    for (int s = 0; s < n; s++) {
        ans = max(ans, dfs(s));
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8192
n = int(input())
a = list(map(int, input().split()))

dict_diffs1 = dict()
dict_diffs2 = dict()
for i in range(1, n+1):
  dict_diffs1[i+a[i-1]] = dict_diffs1.get(i+a[i-1], 0) + 1
  dict_diffs2[i-a[i-1]] = dict_diffs2.get(i-a[i-1], 0) + 1
total = 0
for j in range(1, n+1):
  total += dict_diffs1.get(j-a[j-1], 0)
  total += dict_diffs2.get(j+a[j-1], 0)
total = total//2
print(total)

Measured memory_bytes: 125676
length = int(input())
target = []
target = [int(n) for n in input().split(" ")]
target.sort()
answer = length
temp_len = 0
for i,t in enumerate(target):
    if i == 0:
        before = t
    elif before * 2 < t:
        before += t
        answer -= temp_len
        temp_len = 0
    else:
        before += t
    temp_len += 1
print(answer)
        
    


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

int main(){

  int a, cnt[101]={}, maxn=0;

  while(cin>>a){
    cnt[a]++;
    maxn=max(maxn, cnt[a]);
  }

  for(int i=1;i<=100;i++){
    if(maxn==cnt[i]) cout<<i<<endl;
  }

  return 0;
}

Measured memory_bytes: 2980
#include <bits/stdc++.h>
#ifdef DEMETRIO
#define deb(...) fprintf(stderr,__VA_ARGS__)
#define deb1(x) cerr << #x << " = " << x << endl
#else
#define deb(...) 0
#define deb1(x) 0
#endif
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define SZ(x) ((int)(x).size())
#define mset(a,v) memset(a,v,sizeof(a))
#define mcpy(a,b) memcpy(a,b,sizeof(a))
using namespace std;
typedef long long ll;

#define MOD 1000000007

int add(int a, int b){
	a+=b;
	if(a>=MOD)a-=MOD;
	return a;
}
int sub(int a, int b){
	a+=MOD-b;
	if(a>=MOD)a-=MOD;
	return a;
}

int n,k;
int f[100005],f2[100005],s[100005];

int main(){
	scanf("%d%d",&n,&k);
	f[0]=1;
	fore(_,0,n){
		int a;
		scanf("%d",&a);
		fore(i,0,k+1)s[i+1]=add(s[i],f[i]);
		fore(i,0,k+1)f2[i]=sub(s[i+1],s[max(i-a,0)]);
		mcpy(f,f2);
	}
	printf("%d\n",f[k]);
	return 0;
}

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

#define fo(i, x, y) for (int i = x; i <= y; ++i)
#define fd(i, x, y) for (int i = x; i >= y; --i)

const int maxn = 2e5 + 5;

int n, m;
int fa[maxn], siz[maxn];

int getint()
{
	char ch;
	int res = 0, p;
	while (!isdigit(ch = getchar()) && (ch ^ '-'));
	p = ch == '-'? ch = getchar(), -1 : 1;
	while (isdigit(ch))
		res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
	return res * p;
}

int getfa(int x)
{
	return x == fa[x]? x : fa[x] = getfa(fa[x]);
}

void merge(int u, int v)
{
	int fu = getfa(u), fv = getfa(v);
	if (fu == fv) return;
	if (siz[fu] < siz[fv]) fa[fu] = fv, siz[fv] += siz[fu];
		else fa[fv] = fu, siz[fu] += siz[fv];
}

int main()
{
	n = getint(); m = getint();
	fo(i, 1, n) fa[i] = i, siz[i] = 1;
	fo(i, 1, m)
	{
		int u, v;
		u = getint(); v = getint();
		merge(u, v);
	}
	int ans = 0;
	fo(i, 1, n)
		if (i == fa[i]) ans = max(ans, siz[i]);
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 5316
#include<bits/stdc++.h>
using namespace std;
int main() {
  long long a, b, c;
  cin >> a >> b >> c;
  long long k;
  cin >> k;
  for(long long i=0; i<k; i++) {
    if(c<=a || c<=b)
      c *= 2;
    else if(b<=a)
      b *= 2;
  }
  if(c>b && c>a && b>a)
    cout << "Yes";
  else
    cout << "No";
  return 0;
}

Measured memory_bytes: 3632
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <iomanip>

using namespace std;

int main(){
   long long A;
   string B;
   cin >> A >> B;
   int b = (B[0]-'0')*100+(B[2]-'0')*10+(B[3]-'0');
   A *= b;
   A/=100;
   cout << A << endl;
   return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
int main(){
	int N, K; cin >> N >> K; 
	long long int P = 1e9 + 7; 
	long long int B[2019][2019] = {}; 
	B[0][0] = 1; 
	for(int i = 1; i < 2010; i++){
		B[i][0] = 1; 
	}
	for(int i = 1; i < 2010; i++){
		for(int j = 1; j <= i; j++){
			B[i][j] = (B[i-1][j-1] + B[i-1][j]) % P; 
		}
	}
	for(int i = 1; i <= K; i++){
		cout << (B[N-K+1][i] * B[K-1][i-1]) % P << endl; 
	}
}

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

int main(){
  long long int a,b,k;
  cin>>a>>b>>k;
  if(a<k){
    b+=a-k;
    if(b<0) 
      b=0;
    a=0;
  }else{
  a-=k;
  }
  cout<<a<<" "<<b;
}

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

int main(){
    string s;
    long long k; 
    cin>>s>>k;
    int cnt=0;
    for(int i=0;i<s.length();i++){
        if(s[i]=='1') cnt++;
        else break;
    }
    if(cnt>=k) cout<<1<<endl;
    else cout<<s[cnt]<<endl;
}

Measured memory_bytes: 256
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//Abdulhamid Han
//Bismillahirrahmanirrahim
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█▄█
//█─█─█▄─█▄─█─█─█─█

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

typedef long long lo;
typedef pair< int,int > PII;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo MAX = -1000000000000000000;
const lo MIN = 1000000000000000000;
const lo inf = 1000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000007;

int n,m,b[li],a[li],k,flag,t;
int cev;
string s;
vector<int> v;

int main(void){
	fio();
	cin>>n;
	//~ scanf("%d",&n);
	cin>>s;
	if(n>=3200)cout<<s;
	else cout<<"red";
	return 0;
}


Measured memory_bytes: 892
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<algorithm>
#include<cmath>
//#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef vector<long long> vll;
template <class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}
template <class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
template <class T> inline T gcd(T a, T b) {if(a==0) return b; return gcd(b%a,a);}
template <class T> inline T lcm(T a, T b) {return a * b / gcd(a,b);}
template <class T> inline T sum(vector<T> &vec) {T res=0; for (int i = 0; i < vec.size(); i++) res += vec[i]; return res;}
template <class T> inline T mpow(T a, T b) {if(b==0)return 1; T c = mpow(a,b/2);if(b%2==1)return c*c*a; return c*c;}
const int INF = 1 << 30;
const long long INFLL = 1LL << 60;
typedef pair<int, int> P;

#define REP(i,n) for (int (i)=0;(i)<(n);(i)++)
#define FOR(i,n) for (int (i)=0;(i)<(n);(i)++)
#define REPB(i,n) for (int (i)=((n)-1);(i)>=0;(i)--)
#define FORB(i,n) for (int (i)=((n)-1);(i)>=0;(i)--)
#define SORT(A) sort((A).begin(),(A).end())

int main() {
    /*
    char c; cin >> c;
    cout << (char)(c+1) << endl;
   *//*
    int N, K, M; cin >> N >> K >> M;
    vint A(N-1);
    FOR(i,N-1) cin >> A[i];

    int res = N * M;
    FOR(i,N-1) res -= A[i];
    if (res > K) {
        cout << -1 << endl;
    } else if (res < 0) {
        cout << 0 << endl;
    } 
    else {
        cout << res << endl;
    }*/

    int N, M; cin >> N >> M;
    vint p(M); 
    vector<string> S(M);
    FOR(i,M) cin >> p[i] >> S[i];

    vint ac(N,0), pena(N,0);
    FOR(i,M) {
        if (S[i] == "AC") {
            ac[p[i]-1] = 1;
        } else {
            if (ac[p[i]-1] == 0) {
                pena[p[i]-1] += 1;
            } 
        }
    }
    int acs = 0, penas = 0;
    FOR(i,N) {
        if (ac[i]) {
            acs++; 
            penas += pena[i];
        }
    }
    cout << acs << " " << penas << endl;
}


Measured memory_bytes: 6912
S = input()
T = input()

length_s, length_t = len(S), len(T)

dif = length_s-length_t+1

res = 0
for i in range(dif):
    st = sum(1 if s == t else 0 for s, t in zip(S[i:i+length_t], T))
    res = max(res, st)

print(length_t-res)

Measured memory_bytes: 67828
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
/************************************************/
#define rep(i,n) for(int i=0;i<n;i++)
#define m_p make_pair
#define pb push_back
#define fr first
#define se second
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define sz(s) s.size()
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
#define mod 1000000007
/************************************************/
using namespace std;

long long get(){
	char c=getchar();
	long long x=0LL;
	while(c<'0'||c>'9')
	c=getchar();
	while(c>='0'&&c<='9'){
		x*=10LL;
		x+=(c-'0');
		c=getchar();
	}
	return x;
}
int n,a[101];
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	int sum=0,sum1=0;
	rep(i,n){
		cin>>a[i];
		sum+=a[i];
	}
	int ans=-1;
	rep(i,n){
		sum1+=a[i];
		if(ans==-1||abs(sum-sum1-sum1)<ans)
		ans=abs(sum-sum1-sum1);
	}
	cout<<ans;
	re 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
using namespace std;

int main()
{
  int n,r;
  int i,j,k;
  int p,c;
  int a[60];//a[0]??????
  int b[60];
  int x;

  while(1){
    cin>>n>>r;
    if(n==0 && r==0)break;
    for(i=0;i<n;i++)
      a[i]=n-i;

    for(i=0;i<r;i++){
      cin>>p>>c;
      for(j=0;j<c;j++)//c??????????????????
	b[j]=a[p-1+j];
      for(k=0;k<p-1;k++)//p-1???????????¨???
	b[j+k]=a[k];
      for(x=0;x<j+k;x++)//??????????????????
	a[x]=b[x];      
    }    
    cout<<a[0]<<endl;
  }
}

Measured memory_bytes: 1160
def f(n):
  if n < 105:
    return 0
  if n % 2 == 0:
    return 0
  c = 0
  for i in range(1, n + 1):
    if n % i == 0:
      c += 1
  if c == 8:
    return 1
  else:
    return 0

print(sum(map(lambda x:f(x), [x for x in range(1, int(input()) + 1)])))

Measured memory_bytes: 3060
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <stack>
#define rep(i, s, g) for (i = s; i < g; i++)
using namespace std;
using ll = long long;

int main(){

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

    int ans;

    //ans * 0.08 = A;
    //ans * 0.10 = B;

    rep(i,1,1001) {
        if((int)(i*0.08)==A){   //小数と整数を比べるとうまくいかない,intとdoubleを統一する
            if((int)(i*0.1)==B){
                ans =i;
                cout << ans << endl;
                return 0;
            }
        }
    } 
    cout << -1 << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
  public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);
    while(true) {
      int[] a = new int[21];
      int L;
      a[0] = cin.nextInt();
      L = cin.nextInt();
      if(a[0] == 0 && L == 0) { // 0 0なら終了
        break;
      }
      for(int i = 0; i < 20; i++) {
        int x = a[i];
        int[] dc = new int[10]; // 各桁の個数のカウンタ
        for(int j = 0; j < L; j++) {
          dc[x % 10]++;
          x /= 10;
        }
        int max = 0, min = 0;
        // 最大値
        for(int j = 9; j >= 0; j--){
          for(int k = 0; k < dc[j]; k++) {
            max = max * 10 + j;
          }
        }
        // 最小値
        for(int j = 0; j <= 9; j++){
          for(int k = 0; k < dc[j]; k++) {
            min = min * 10 + j;
          }
        }
        a[i + 1] = max - min;
      }
loop1:for(int i = 0; i <= 20; i++) {
        for(int j = 0;j < i; j++) {
          if(a[i] == a[j]) {
            System.out.println("" + j + " " + a[i] + " " + (i - j));
            break loop1;
          }
        }
      }
    }
  }
  
}

Measured memory_bytes: 20264
a, b, c, d = gets.chomp.split(' ').map(&:to_i)

if a < c
  if c < b
    if b < d
      print "#{b-c}"
    else
      print "#{d-c}"
    end
  else
    print '0'
  end
else
  if a < d
    if b < d
      print "#{b-a}"
    else
      print "#{d-a}"
    end
  else
    print '0'
  end
end

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

typedef long long ll;

#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define tt int t; cin>>t; while(t--)
#define nl cout<<"\n";
#define sp cout<<" ";
#define rep(i, a, b) for(long long i=a; i<b; i++)

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
double PI = 4*atan(1);

int main()
{
    optimize();

    map < string, int >m;

    int n;
    cin>> n;
    string s[4] = {"AC", "WA", "TLE", "RE"}, t;

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

        m[t]++;
    }


    for(int i=0; i<4; i++)
        cout<< s[i]<< " x " << m[s[i]] << '\n';


    return 0;
}




Measured memory_bytes: 3636
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		int retu = scan.nextInt();
		Integer[] jun = new Integer[retu];
		int count = 0;

		for(int i=0;i<retu;i++) {
			jun[i] = scan.nextInt();
		}

		int re = 1;
		int min = jun[0];

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

			if(min >= jun[i]) {
				count++;
			}
			min = Math.min(min, jun[i]);
		}

		System.out.println(count);

		scan.close();
	}

}


Measured memory_bytes: 89776
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define mod 1000000007
#define pii pair<ll,ll>
#define inf 1000000000000000000
#define bpc(x) __builtin_popcountll(x)
#define autoit(x,it) for(auto it = x.begin(); it != x.end(); it++)
#define rep(n) for(ll i = 0; i < n; i++)
#define repi(i,n) for(ll i = 0; i < n; i++)

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

using namespace std;
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());

ll find(ll x, ll par[])
{
    if(x == par[x])
        return x;
    return par[x] = find(par[x], par);
}
 
void unio(ll x, ll y, ll par[], ll rank[])
{
    x = find(x,par);
    y = find(y,par);
    if(x == y)
        return;
    if(rank[x]>rank[y])
    {
        //siz[x]+=siz[y];
        rank[x] = max(rank[x], rank[y] + 1);
        par[y] = x;
    }
    
    else
    {
        //siz[y]+=siz[x];
        rank[y] = max(rank[y], rank[x] + 1);
        par[x] = y;
    }
}

int main()
{
  FAST/**/
   
   ll n,m;
   cin>>n>>m;
   
   ll par[n], rank[n];
   rep(n)
        par[i] = i, rank[i] = 0;
   
   rep(m)
   {
       ll a,b;
       cin>>a>>b;
       a--,b--;
       unio(a,b,par,rank);
   }
   set<ll> st;
   rep(n)
        st.insert(find(i,par));
   cout<<(ll)st.size() - 1;        
   
   return 0;        
}  

  
          
   

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

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

const int MAX = 2e9 + 10;
const int INF = 1e9;
const int MOD = 1e9 + 7;

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int f(int a, int b) {
  if (a > b) return MAX;
  return b - a;
}

int main() {
  // 入力
  int x, y;
  cin >> x >> y;

  int ans = MAX;
  ans = min(ans, f(x, y));
  ans = min(ans, f(-x, y) + 1);
  ans = min(ans, f(x, -y) + 1);
  ans = min(ans, f(-x, -y) + 2);

  // 解答
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
DIR = ((0, 1), (0, -1), (1, 0), (-1, 0))

H, W = list (map (int, input().split()))
G = []
for i in range (H) :
    G.append(list (input()))

ans = 0

for i in range (H) :
    for j in range (W) :
        if G[i][j] == '.' :
            use = [[False for ii in range (W)] for jj in range (H)]
            q = [(i, j, 0)]
            use[i][j] = True
            path = 0

            while len (q) :
                node = q.pop(0)
                path = max (path, node[2])
                for k in range (4) :
                    x, y = node[0] + DIR[k][0], node[1] + DIR[k][1]
                    if x < 0 or y < 0 or x >= H or y >= W :
                        continue
                    if use[x][y] or G[x][y] == '#':
                        continue
                    use[x][y] = True
                    q.append((x, y, node[2] + 1))
            ans = max (ans, path)

print(ans)


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

namespace AtCoder2 {
	class Program {
		static void Main(string[] args) {

	
			var inputArray = retreiveLongArray();
			var inputCount = 2;

			// 不正な入力は処理しない
			if (inputArray.Length != inputCount) {
				Console.WriteLine("invalid input");
				return;
			}

			var A = inputArray[0];
			var B = inputArray[1];
			//答えの出力
			var ans = getLcm(A,B);
			Console.WriteLine(ans);

		}
		/// <summary>
		/// 最小公倍数を返す
		/// </summary>
		/// <param name="a"></param>
		/// <param name="b"></param>
		/// <returns></returns>
		private static long getLcm(long a, long b) {
			return (a * b / getGcd(a, b));
		}

		/// <summary>
		/// 最大公約数
		/// </summary>
		/// <param name="a"></param>
		/// <param name="b"></param>
		/// <returns></returns>
		static long getGcd(long a, long b) {
			if (a < b) {
				return getGcd(b, a);
			}
			if (b > 0) {
				return getGcd(b, a % b);
			}
			else {
				return a;
			}
		}
		/// <summary>
		/// スペースで区切られた文字列配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static string[] retreiveStringArray() {
			var inputArray = Console.ReadLine().Split(' ');
			return inputArray;
		}

		/// <summary>
		/// スペースで区切られた整数配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static long[] retreiveLongArray() {
			var inputArray = Console.ReadLine().Split(' ');
			var longArray = inputArray.Select(s => long.Parse(s));
			return longArray.ToArray();
		}
	}
}


Measured memory_bytes: 13396
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;

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

// Self settings
// clang-format off
#define MAX_N 30
#define MAX_M 30
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SLN(i,N) (i == N-1 ? "\n" : " ")
// clang-format on
int N, M;
int K[MAX_M];
int A[MAX_M][MAX_N];
bool Q[MAX_M];

void solve()
{
  fill(Q, Q + MAX_M, true);
  int cnt = 0;
  REP(q, 30)
  {
    bool n = true;
    REP(i, N)
    {
      sort(A[i], A[i] + K[i]);
      bool s = binary_search(A[i], A[i] + K[i], q + 1);
      n &= binary_search(A[i], A[i] + K[i], q + 1);
    }
    if (n) cnt++;
  }
  cout << cnt << endl;
}

int main(void)
{
  cin >> N >> M;
  REP(i, N)
  {
    cin >> K[i];
    REP(j, K[i]) { cin >> A[i][j]; }
  }
  solve();
  return 0;
}


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

int main(void) {
    string s;
    bool flag = true;
    cin >> s;
    if(s.find("N") != string::npos) {
        if(s.find("S") == string::npos) flag = false;
    }
    if(s.find("S") != string::npos) {
        if(s.find("N") == string::npos) flag = false;
    }
    if(s.find("E") != string::npos) {
        if(s.find("W") == string::npos) flag = false;
    }
    if(s.find("W") != string::npos) {
        if(s.find("E") == string::npos) flag = false;
    }

    if(flag) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
ks = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k = int(input())
print(ks[k-1])

Measured memory_bytes: 3060
S = input()
count = 0

if S[0] == "R":
  if S[1] == "R":
    if S[2] == "R":
      print("3")
    elif S[2] == "S":
      print("2")
  elif S[1] == "S":
    if S[2] == "R":
      print("1")
    elif S[2] == "S":
      print("1")
elif S[0] == "S":
  if S[1] == "R":
    if S[2] == "R":
      print("2")
    elif S[2] == "S":
      print("1")
  elif S[1] == "S":
    if S[2] == "S":
      print("0")
    elif S[2] == "R":
      print("1")

Measured memory_bytes: 61888
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
cin >> n;
  n%=28;
  if (n==0)cout <<"Yes"<<endl;
  else if (n==4)cout <<"Yes"<<endl;
  else if (n==7)cout <<"Yes"<<endl;
  else if (n==8)cout <<"Yes"<<endl;
  else if (n==11)cout <<"Yes"<<endl;
  else if (n==12)cout <<"Yes"<<endl;
  else if (n==14)cout <<"Yes"<<endl;
  else if (n==15)cout <<"Yes"<<endl;
  else if (n==16)cout <<"Yes"<<endl;
  else if (n==18)cout <<"Yes"<<endl;
  else if (n==19)cout <<"Yes"<<endl;
  else if (n==20)cout <<"Yes"<<endl;
  else if (n==21)cout <<"Yes"<<endl;
  else if (n==22)cout <<"Yes"<<endl;
  else if (n==23)cout <<"Yes"<<endl;
  else if (n==24)cout <<"Yes"<<endl;
  else if (n==25)cout <<"Yes"<<endl;
  else if (n==26)cout <<"Yes"<<endl;
  else if (n==27)cout <<"Yes"<<endl;
  else cout <<"No"<<endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
long long a[3];
int main(void){
  cin >> a[0] >> a[1] >> a[2];
  sort(a,a+3);
  if(a[0]%2 && a[1]%2 && a[2]%2){
    cout << a[0]*a[1];
  }else{
    cout << 0 << endl;
  }
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#define inf 0x3f3f3f3f;
using namespace std;

template <typename Tp> inline void getint(Tp &num){
	register int ch, neg = 0;
	while(!isdigit(ch = getchar())) if(ch == '-') neg = 1;
	num = ch & 15;
	while(isdigit(ch = getchar())) num = num * 10 + (ch & 15);
	if(neg) num = -num;
}

int N, L[200005], R[200005], ans = inf;
char str[200005];

int main(){
	getint(N), scanf("%s", str + 1);
	for(register int i = 1; i <= N; i++) L[i] = L[i - 1] + (str[i] == '#');
	for(register int i = N; i >= 1; i--) R[i] = R[i + 1] + (str[i] == '.');
	for(register int i = 0; i <= N; i++) ans = min(ans, L[i] + R[i + 1]);
	return printf("%d\n", ans), 0;
}


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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2018/02/14  Problem: 080_abc_c / Link: https://abc080.contest.atcoder.jp/tasks/abc080_c?lang=en  ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */

int popcount2(int x) {
	int ret = 0;
	while (x) {
		x &= x - 1;
		++ret;
	}
	return ret;
}
LL N;

LL ans = 0LL;

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

	cin >> N;
	VI shop(N, 0);
	FOR(i, 0, N) {
		int ret = 0;
		FOR(j, 0, 10) {
			int a; cin >> a;
			ret <<= 1;
			ret += a;
		}
		shop[i] = ret;
	}
	VVI pro(N, VI(11));
	FOR(i, 0, N) {
		FOR(j, 0, 11) {
			cin>>pro[i][j];
		}
	}

	ans = -LINF;
	FOR(bit, 0, 1 << 10) {
		if (popcount2(bit) == 0)continue;
		LL ret = 0;
		FOR(i, 0, N) {
			int state = bit&shop[i];
			int cnt = popcount2(state);
			ret += pro[i][cnt];
		}
		ans = max(ans, ret);
	}
	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 256
import numpy as np

n = int(input())
x = list(map(int, input().split()))

p = [int(np.mean(x)), int(np.mean(x)) + 1]
xnp = np.array(x)

min_xp = -1
for pi in p:
    if min_xp == -1:
        min_xp = np.square(xnp - pi).sum()
    elif min_xp > np.square(xnp - pi).sum():
        min_xp = np.square(xnp - pi).sum()
print(min_xp)

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

int main(){
    long int H,W;
    cin >> H >> W;
    long int ans;

    if(H == 1 || W == 1){
        cout << 1 << endl;
    }

    else{
        cout << (H * W + 1)/2 << endl;
    }

}

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

int main(){
    int w,h,x,y,r;
    cin >> w >> h >> x >> y >> r;
    if(r <= x && x <= w-r && r <= y && y <= h-r){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}


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


#define li          long long int
#define rep(i,to)   for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)    for(li i=(li)(start);i<((li)(to));i++)
#define pb          push_back
#define sz(v)       ((li)(v).size())
#define bgn(v)      ((v).begin())
#define eend(v)     ((v).end())
#define allof(v)    (v).begin(), (v).end()
#define dodp(v,n)       memset(v,(li)n,sizeof(v))
#define bit(n)      (1ll<<(li)(n))
#define mp(a,b)     make_pair(a,b)
#define rin rep(i,n)
#define EPS 1e-12
#define ETOL 1e-8
#define MOD 1000000007
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)     idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)       idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)        idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)   for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)      idp p2((x).F, (x).S)
#define dump(x,n)   idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)  idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)    idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)   idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)   rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)   rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}



int main() {
    li l, r;
    cin >> l >> r;
    if (l / 2019 != r / 2019) {
        cout << 0 << endl;
        return 0;
    }

    li res = 2019;
    repp(i, l, r + 1) {
        repp(j, i + 1, r + 1) {
            res = min(res, ((i % 2019) * (j % 2019)) % 2019);
        }
    }
    cout << res << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000000;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

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

ll N;
ll x[MAX], y[MAX], h[MAX];

bool ch(ll X, ll Y, ll H) {
	repn(i, N) {
		if (max(H - abs(X - x[i]) - abs(Y - y[i]), 0) != h[i]) { return false; }
	}
	return true;
}





int main() {
	cin >> N;
	repn(i, N) cin >> x[i] >> y[i] >> h[i];

	rep(X, 101) {
		rep(Y, 101) {
			for (ll H = h[1]; H <= h[1] + 200; H++) {
				if (ch(X, Y, H)) { cout << X << " " << Y << " " << H; }
			}
		}
	}


	system("PAUSE");
}

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int x, y;
  cin >> x >> y;
  int ans = 0;
  if (x == 3) {
    ans += 100000;
  } else if (x == 2) {
    ans += 200000;
  } else if (x == 1) {
    ans += 300000;
  }
  if (y == 3) {
    ans += 100000;
  } else if (y == 2) {
    ans += 200000;
  } else if (y == 1) {
    ans += 300000;
  }
  if (x == 1 && y == 1) {
    ans += 400000;
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

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

    int n; cin >> n;
    int arr[n]; for(auto &i : arr) cin >> i;

    long long ans = 0;
    for(int d = 1; d < n / 2; ++d)
    {
        int t = 0; long long ps = 0;
        while(1)
        {
            ps += arr[t] + arr[n - t - 1];
            ans = max(ps, ans);
            t += d;
            if(n - t - 1 <= d || (n - 1) % d == 0 && (n - 1) <= 2 * t) break;
        }
    }

    cout << ans;
}


Measured memory_bytes: 640
import bisect
N = int(input())
L = list(map(int,input().split()))
L.sort()
ans = 0
for b in range(N):
    l = b + 1
    for a in range(b):
        maxL = L[a] + L[b]
        r = bisect.bisect_left(L, maxL)
        ans += max(0, r-l)
print(ans)

Measured memory_bytes: 3188
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<list>
using namespace std;
long long int inf = 1e18;

int main() {

  int n; cin >> n;
  vector<int> a(n);
  for(int i=0; i<n; i++) cin >> a[i];
  vector<int> b;
  vector<int> c;
  for(int i=0; i<n; i++){
    if( i % 2 == 0 ) b.push_back(a[i]);
    else c.push_back(a[i]);
  }
  vector<int> d;
  for(int i=0; i<c.size(); i++){
    d.push_back(c[c.size()-1-i]);
  }
  for(int i=0; i<b.size(); i++){
    d.push_back(b[i]);
  }

  if( n % 2 == 1 ) reverse(d.begin(), d.end());

  for(int i=0; i<d.size(); i++){
    if(i!=n-1)cout << d[i] << " ";
    else cout << d[i] << endl;
  }


  return 0;
}


Measured memory_bytes: 4592
#include <iostream>
#include <fstream>
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <numeric>
#include <functional>
#include <string> 
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <random>
#include <chrono>

using namespace std;

using ll = long long;
using ull = unsigned long long;

#define REP(i,n) for(long long i = 0; i < (n); i++)
#define FOR(i, m, n) for(long long i = (m);i < (n); ++i)
#define ALL(obj) (obj).begin(),(obj).end()

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;

const ll MOD = (ll)1e9 + 7;
const ll MOD2 = 998244353;
const ll LLINF = (ll)1e18;
const ll INTINF = (ll)1e9;
const long double PI = 3.1415926535897932384626433;

template <class T> void corner(bool flg, T hoge) { if (flg) { cout << hoge << endl; exit(0); } }
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) { o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o; }
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) { o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o; }
template <class T>ostream &operator<<(ostream &o, const multiset<T>&obj) { o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o; }
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) { o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o; }
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) { o << "{" << obj.first << ", " << obj.second << "}"; return o; }
template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) { o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o; }
void print(void) { cout << endl; }
template <class Head> void print(Head&& head) { cout << head; print(); }
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) { cout << head << " "; print(forward<Tail>(tail)...); }
template <class T> void chmax(T& a, const T b) { a = max<T>(a, b); }
template <class T> void chmin(T& a, const T b) { a = min<T>(a, b); }
void YN(bool flg) { cout << ((flg) ? "YES" : "NO") << endl; }
void Yn(bool flg) { cout << ((flg) ? "Yes" : "No") << endl; }
void yn(bool flg) { cout << ((flg) ? "yes" : "no") << endl; }

int main() {
	int N,Q; cin >> N >> Q;
	string S; cin >> S;
	S = "." + S;
	V<int> a(N + 1, 0);
	for(int i = 1; i < N+1; ++i){
		if (S[i - 1] == 'A' && S[i] == 'C') a[i]++;
	}
	for (int i = 1; i < N+1; ++i) {
		a[i]+=a[i-1];
	}
	REP(i,Q){
		int l, r; cin >> l >> r;
		l--;
		cout << a[r] - a[l] -(S[l]=='A'&&S[l+1]=='C'?1:0) << endl;
	}
	return 0;
}


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

#define each(i, c) for (auto& i : c)
#define mkp(a, b) make_pair(a, b)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> Pll;
const ll MOD = 1e9+7;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << ": " << p.second << ")"; return os; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ", "; os << ")"; return os; }
template<typename K, typename V> ostream& operator << (ostream& os, map<K, V> m) { os << "{"; each (i, m) os << i << ", "; os << "}"; return os; }

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

  string s;
  cin >> s;

  queue<ll> q;
  bool zero = false;
  ll count = 0;
  for (ll i = 0; i < s.size(); ++i) {
    if (zero && s[i] == '1') {
      zero = false;
      q.push(count);
      count = 0;
    }
    if (s[i] == '0') zero = true;
    ++count;
  }
  q.push(count);

  ll ans = 0;
  zero = false;
  count = 0;
  for (ll i = 0; i < s.size(); ++i) {
    if (s[i] == '1') {
      zero = false;
    } if (!zero && s[i] == '0') {
      zero = true;
      --k;
    }

    if (k < 0) {
      ans = max(ans, count);
      count -= q.front();
      q.pop();
      k = 0;
    }

    ++count;
  }
  ans = max(ans, count);

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 768
from math import factorial
n,m=map(int,input().split())
mod=10**9+7
if abs(n-m)>=2:
  print(0)
elif abs(n-m)==1:
  print((factorial(n)%mod*factorial(m)%mod)%mod)
else:
  print((2*factorial(n)%mod*factorial(m)%mod)%mod)

Measured memory_bytes: 4092
#include<bits/stdc++.h>
using namespace std;
const int q=1000000007;
int n,f[200010],s[200010],a[200010];
struct point
{
	int x,v;
}w[200010];
struct line
{
	int l,r;
}x[200010];
inline bool cmp(point a,point b)
{
	return a.x<b.x;
}
inline bool cmp2(line a,line b)
{
	return a.r<b.r || a.r==b.r && a.l<b.l;
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int i,j;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	  {
	   scanf("%d%d",&w[i].x,&w[i].v);
	   a[i]=w[i].v;
	  }
	sort(w+1,w+n+1,cmp);
	sort(a+1,a+n+1);
	for(i=1,j=w[1].v;i<=n;i++,j=max(j,w[i].v))
	  x[i].r=lower_bound(a+1,a+n+1,j)-a;
	for(i=n,j=w[n].v;i>0;i--,j=min(j,w[i].v))
	  x[i].l=lower_bound(a+1,a+n+1,j)-a;
	sort(x+1,x+n+1,cmp2);
	f[0]=s[0]=1;
	for(i=1;i<=n;i++)
	  {
	   for(j=x[i-1].r+1;j<=x[i].r;j++)
	     s[j]=s[j-1];
	   j=(s[x[i].r]-(x[i].l==1?0:s[x[i].l-2]))%q;
	   f[x[i].r]=(f[x[i].r]+j)%q;
	   s[x[i].r]=(s[x[i].r]+j)%q;
	  }
	printf("%d\n",(f[n]+q)%q);
	return 0;
}


Measured memory_bytes: 5760
N = int(input())
A = list(map(int, input().split()))

AA = [0] * (N)
for i in range(N):
    AA[i] = list(format(A[i], 'b').zfill(42))

ans = [0] * 42
ma = 0
for i in range(N):
    AA[i].reverse()
    for j in range(len(AA[i])):
        ma = max(ma, j)
        ans[j] += int(AA[i][j])

ret = []
for i in range(N):
    temp = 0
    for j in range(ma):
        if (ans[j] + int(AA[i][j])) & 1 == 1:
            temp += 1 << j

    ret.append(temp)

print(*ret)


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

int main(){
	vector<int> vec;
	int n;
	int max = -1; 
	cin>>n;
	for(int i=0;i<n;i++){
		int a;
		cin>>a;
		if(max < a){
			vec.push_back(a);
			max = a;
			
		}else{
			vector<int>::iterator itr = lower_bound(vec.begin(),vec.end(),a);
			int idx = vec.size()-1;
			*itr = a;
			max = vec[idx];
		}
	}
	cout<<vec.size()<<endl;
	return 0;
}

Measured memory_bytes: 1672
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

int main(){
    int n, z, w;
    cin >> n >> z >> w;
    vector<int> v(n);
    rep(i, n) cin >> v[i];

    //全部取る
    int ans = abs(v[n-1] - w);
    //n-1枚取る
    if(n >= 2) chmax(ans, abs(v[n-2] - v[n-1]));

    cout << ans << endl;
}

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

int main() {
    int n, q;

    cin >> n;
    int s[n];

    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }

    cin >> q;
    int t[q];

    for (int j = 0; j < q; j++) {
        cin >> t[j];
    }

    int res = 0;

    for (int i = 0; i < q; i++) {
        for (int j = 0; j < n; j++) {
            if (t[i] == s[j]) {
                res++;
                break;
            }
        }
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 3132
// C - こだわり者いろはちゃん / Iroha's Obsession https://atcoder.jp/contests/abc042/tasks/arc058_a

  import scala.io.Source

  object Main extends App {
    val xs = Source.stdin.getLines()
    val Array(n, k) = xs.next().split(' ').map(_.toInt)
    val ds = xs.next.split(' ').map(_.toInt)

    println(solve(n, ds))

    def solve(n: Int, ds: Seq[Int]): String = {
      def check(n: Int): Boolean = {
        var f = true
        var nn = n
        while (nn > 0) {
          val nnn = nn % 10
          if (ds.contains(nnn))
            f = false
          nn = nn / 10
        }
        f
      }

      var a = ""
      for (i <- n to 100000) {
        if (check(i)) {
          return i.toString
        }
      }
      a
    }
  }


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

typedef long long ll;
typedef pair<ll, ll> P;

const int MAX_N = 110;
const int MAX_V = 1e5 + 10;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int N, W, w[MAX_N], v[MAX_N];
ll dp[MAX_N][MAX_V];

int main(){
    cin >> N >> W;
    rep(i, N) cin >> w[i] >> v[i];

    int V = accumulate(v, v + N, 0);

    rep(i, N + 1)rep(j, V + 1) dp[i][j] = INF;
    dp[0][0] = 0;

    rep(i, N){
        rep(j, V + 1){
            dp[i + 1][j + v[i]] = min(dp[i + 1][j + v[i]], dp[i][j] + w[i]);
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
        }
    }

    int ans = 0;
    for(int i = V; i >= 0; --i){
        if(dp[N][i] <= W){
            ans = i;
            break;
        }
    }

    cout << ans << endl;
}

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

int main(){
    char b;
    cin >> b;

    if(b == 'A') {
        cout << 'T' << endl;
    } else if(b == 'T') {
        cout << 'A' << endl;
    } else if(b == 'G') {
        cout << 'C' << endl;
    } else if(b == 'C') {
        cout << 'G' << endl;
    }
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String S = in.next();
		List<Integer> list = new ArrayList<>(S.chars().mapToObj(n -> Integer.valueOf(n)).collect(Collectors.toList()));

		int ans = solv(list);
		System.out.println(ans);
	}

	private static int solv(List<Integer> list) {
		int ret = 0;
		for (int index = 1; index < list.size(); index++) {
			if (list.get(index - 1) != list.get(index)) {
				list.remove(index);
				list.remove(index - 1);
				index = Math.max(0, index - 2);
				ret += 2;
			}
		}
		return ret;
	}
}


Measured memory_bytes: 31980
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<climits>
#include<set>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;
typedef pair<ll, ll> pll;
int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };
#define MOD 1000000007
#define ARRAY_MAX 100015

//const int INF = 1e9 + 7;


ll dp[2][ARRAY_MAX];

int main() {

	ll n, c;
	cin >> n >> c;

	vector<ll> x(ARRAY_MAX,0), v(ARRAY_MAX,0);

	for (int i = 1; i <= n; i++)
	{
		cin >> x[i] >> v[i];
	}
	x[0] = 0;
	x[n + 1] = c;

	ll cal = 0;
	for (int i = 1; i <= n; i++)
	{
		//時計回り方向の累積和
		dp[0][i] = dp[0][i - 1] + v[i] - (x[i] - x[i - 1]);
	}

	for (int i = 1; i <= n; i++)
	{
		//反時計回り方向のi番目までのカロリーの最大
		dp[0][i] = max(dp[0][i], dp[0][i-1]);
	}
	
	cal = 0;
	for (int i = n; i >= 1; i--)
	{
		//反時計回り方向の累積和
		dp[1][i] = dp[1][i + 1] + v[i] - (x[i + 1] - x[i]);
	}

	for (int i = n; i >= 1; i--)
	{
		//反時計回り方向のi番目までのカロリーの最大
		dp[1][i] = max(dp[1][i], dp[1][i + 1]);
	}

	ll maxi = 0;

	for (int i = 0; i <= n; i++)
	{
		//時計周りスタート
		maxi = max(maxi, dp[0][i] + dp[1][i + 1] - x[i]);

		//反時計回りスタート
		maxi = max(maxi, dp[0][i] + dp[1][i + 1] - (c - x[i + 1]));
	}
	cout << maxi << endl;

	return 0;
}


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


int main(){
    int N,K;
    vector<long> D;
    cin>>N>>K;
    D.resize(N);
    for(int i=0;i<N;i++)cin>>D[i];
    long ans=0;
    for(int i=0;i<=min(N,K);i++){
        for(int j=0;j<=min(N,K)-i;j++){
            long pre=0;
            vector<long> H(i+j);
            for(int k=0;k<i;k++)H[k]=D[k];
            for(int k=0;k<j;k++)H[i+k]=D[N-1-k];
          if(i!=0 || j!=0){
            sort(H.begin(),H.end());
            reverse(H.begin(),H.end());
            for(int k=0;k<K-(i+j);k++)if(H[H.size()-1]<0)H.pop_back();
            for(int k=0;k<H.size();k++)pre+=H[k];
          }
            ans=max(ans,pre);
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256