akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
    using namespace std;
     
    int main() {
      int A;
      cin >> A;
      int B;
      cin >> B;
      int count=0;
      int a1,a2,a3,a4;
      // ここにプログラムを追記
      for(int i=0;i<B-A+1;i++){
        a1=(A+i)/10000;
        a2=((A+i)%10000)/1000;
        a3=(((A+i)%10000)%1000)%100/10;
        a4=(((A+i)%10000)%1000)%100%10;
        if(a1==a4 && a2==a3){
          count++;
        }
      }
      cout << count << endl;
      
    }

Measured memory_bytes: 3592
///
// File:  alds1_4_d.cpp
// Author: ymiyamoto
//
// Created on Sat Oct  7 23:43:34 2017
//

#include <cstdint>
#include <iostream>
#include <vector>

using namespace std;

static vector<int64_t> array;

uint32_t packages(int64_t tracks, uint64_t P)
{
  size_t num = 0, weight = 0;
  for (uint32_t i = 0; i < tracks && num < array.size(); i++) {
    while (array[num] + weight <= P) {
      weight += array[num];
      num++;
      if (num == array.size()) return num;
    }
    weight = 0;
  }

  return num;
}

uint32_t binary_search(uint32_t k)
{
  uint64_t left = 0;
  uint64_t right = 100000 * 10000 + 1;
  while (left + 1 < right) {
    uint64_t mid = (left + right) / 2;
    uint32_t num = packages(k, mid);
    if (num >= array.size()) {
      right = mid;
    } else {
      left = mid;
    }
  }

  return right;
}

int32_t main()
{
  uint32_t n, k;
  cin >> n >> k;

  for (uint32_t i = 0; i < n; i++) {
    int64_t w;
    cin >> w;
    array.push_back(w);
  }

  cout << binary_search(k) << endl;

  return 0;
}

Measured memory_bytes: 3888
#include<stdio.h>

void QSort(int x[ ], int left, int right);
void Swap(int x[ ], int i, int j);

void QSort(int x[ ], int left, int right)
{
    int i, j;
    int pivot;

    i = left;                   
    j = right;                  

    pivot = x[(left + right) / 2];
    while (1) {                   

        while (x[i] < pivot)      
            i++;                  

        while (pivot < x[j])      
            j--;                  
        if (i >= j)               
            break;                

        Swap(x, i, j);            
        i++;                      
        j--;
    }

    if (left < i - 1)              
        QSort(x, left, i - 1);     
    if (j + 1 <  right)            
				QSort(x, j + 1, right);    
		}

void Swap(int x[ ], int i, int j)
{
    int temp;

    temp = x[i];
    x[i] = x[j];
    x[j] = temp;
}

int main(void)
{
	int i;
	int j;
	int k;
	int n;
	int d[20];
	int p[100];
	int sum;
	int ave;
	
	j=0;
	while(1){


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

		QSort(p,0,n-1);	
	
		sum = 0;
		for(i=1;i<n-1;i++){
			sum += p[i];
		}
			
			d[j] = sum / (n-2);
			j++;

	}
	
	for(k=0;k<j;k++)
		printf("%d\n",d[k]);

	return 0;
}

Measured memory_bytes: 1028
#include <bits/stdc++.h> //JuniorMonster a.k.a Sho10
#define ll long long int
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define all(a) (a).begin(), (a).end()
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define sz size
#define f first
#define s second
#define pb push_back
#define er erase
#define in insert
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define mod 1000000007
#define PI 3.14159265359
#define CODE_START  ios_base::sync_with_stdio();cin.tie();cout.tie();
using namespace std;
ll n,a[101],b[101],c[101],ans;
int32_t main(){
CODE_START;
cin>>n;
for(ll i=0;i<n;i++)
{
    cin>>a[i];
}
for(ll i=0;i<n;i++)
cin>>b[i];
for(ll i=0;i<n-1;i++)
cin>>c[i];
for(ll i=1;i<n;i++)
{
    if(a[i]-1==a[i-1]){
        ans=ans+c[a[i-1]-1];
    }
}
for(ll i=0;i<n;i++)
ans=ans+b[a[i]-1];
cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define L long long
#define pi pair<int,int>
#define pii pair<int,pi>
#define aa first
#define bb second
#define xx aa
#define yy bb.aa
#define zz bb.bb
#define pb push_back
#define mp make_pair
using namespace std;
const int q=1000000007;
int n,a[200010],p,r=1;
vector<int> x[200010];
pi u=mp(1,0);
pii f[200010];
inline void operator+=(pii &a,pii &b)
{
	if(a.zz<u.bb)
	  {
	   a.yy=0;
	   a.zz=u.bb;
	  }
	if(b.zz<u.bb)
	  {
	   b.yy=0;
	   b.zz=u.bb;
	  }
	a.xx+=b.xx;
	a.yy=(a.yy+b.yy)%q;
}
inline int power(int a,int b)
{
	if(!b)
	  return 1;
	int c=power(a,b>>1);
	c=(L)c*c%q;
	if(b&1)
	  c=(L)c*a%q;
	return c;
}
inline pii sum(int i)
{
	pii k={};
	for(;i;i^=i&-i)
	  k+=f[i];
	return k;
}
inline void add(int i,pii k)
{
	for(;i<=n;i+=i&-i)
	  f[i]+=k;
}
int main()
{
	//freopen("E.in","r",stdin);
	//freopen("E.out","w",stdout);
	int i,j,k;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	  {
	   scanf("%d",&a[i]);
	   x[a[i]].pb(i);
	  }
	for(i=n,k=1;i>0;i--)
	  {
	   k--;
	   j=x[i].size();
	   p=(p+((L)j*(j-1)/2+(L)j*k)%q*500000004)%q;
	   k+=j;
	   for(auto l:x[i])
	     {
	      pii w=sum(l-1);
	      p=(p+w.xx-(L)w.yy*u.aa)%q;
	     }
	   for(auto l:x[i])
	     add(l,mp(1,mp(power(u.aa,q-2),u.bb)));
	   if(k!=1)
	     u.aa=(L)u.aa*(1-power(k,q-2))%q;
	   else
	     u.bb++;
	   r=(L)r*k%q;
 	  }
 	p=(L)p*r%q;
 	p=(p+q)%q;
 	printf("%d\n",p);
	return 0;
}


Measured memory_bytes: 14336
#include <stdio.h>

int main(){
  int i,j,flag,minj;
  int n,a;
  int count = 0;

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

  for(i = 0;i < n-1;i++){
    int key;
    minj = i;
    flag = 0;
    for(j = i+1;j < n ;j++) {
      if(data[j] < data[minj]){
        minj = j;
	flag = 1;
      }
    }
      if(flag){
        key = data[minj];
        data[minj] = data[i];
        data[i] = key;
        count++;
      }
  }
  for(i = 0;i < n;i++){
  printf("%d",data[i]);
  if(i==n-1) break;
  printf(" ");
  }
  printf("\n");
  printf("%d\n",count);

  return 0;
}



Measured memory_bytes: 2108
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<int,ll>> G[150000];
vector<pair<int,int>> Q;
vector<int> QV[150000];
ll sum[150000];
int par[18][150000],dep[150000],ordl[150000],ordr[150000];
int N;
void dfs(int prev,int cur,ll val,ll add){
    sum[cur]=val;
    for(const auto p : QV[cur])
        add+=p;
    for(auto& p: G[cur]){
        if(p.first==prev)continue;
        p.second+=add;
        dfs(cur,p.first,val+p.second,add);
    }
    QV[cur].clear();
}
void efs(int prev,int cur,int d,int& ord){
    dep[cur]=d;
    par[0][cur]=prev;
    ordl[cur]=ord++;
    for(const auto p: G[cur]){
        if(p.first==prev)continue;
        efs(cur,p.first,d+1,ord);
        ord++;
    }
    ordr[cur]=ord;

}
void init(){
    for(int i=0;i<18;i++)
        for(int j=0;j<N;j++)par[i][j]=-1;
    int ord=0;
    efs(-1,0,0,ord);
    for(int i=1;i<18;i++)
        for(int j=0;j<N;j++){
            if(par[i-1][j]==-1)par[i][j]=-1;
            else par[i][j]=par[i-1][par[i-1][j]];
        }
}
int getLCA(int a,int b) {
   if (dep[a] > dep[b]) swap(a, b);
   for(int i=0;i<18;i++)
       if ((dep[b] - dep[a]) >> i & 1)
           b = par[i][b];
   if (a == b) return a;
   for(int i=17;i>=0;i--)
       if (par[i][a] != par[i][b])a = par[i][a], b = par[i][b];
   return par[0][a];
}

ll get(int v){
    ll ret=sum[v];
    for(const auto p : Q){
        int u=p.first,x=p.second;
        if(ordl[v]<ordl[u]||ordr[u]<ordl[v])continue;
        if(dep[u]<=dep[v])ret+=1LL*x*(dep[v]-dep[u]);
    }
    return ret;
}

int main(){
    cin>>N;
    int M;
    cin>>M;
    for(int i=0;i<N-1;i++){
        int a,b;
        cin>>a>>b;
        G[a].emplace_back(b,0);
        G[b].emplace_back(a,0);
    }

    init();
    for(int i=0;i<M;i++){
        if(i%1500==0){
            Q.clear();
            dfs(-1,0,0,0);
        }
        int t;
        cin>>t;
        if(t==1){
            int u,x;
            cin>>u>>x;
            Q.emplace_back(u,x);
            QV[u].emplace_back(x);

        }else{
            int u,v,lca;
            cin>>u>>v;
            lca=getLCA(u,v);
            //cout<<u<<" "<<v<<" "<<lca;
            cout<<get(u)+get(v)-2*get(lca)<<'\n';
        }
    }
}


Measured memory_bytes: 44132
#include<bits/stdc++.h>
#define rep(i,a,n) for(register int i=a;i<=n;++i)
#define per(i,a,n) for(register int i=a;i>=n;--i)
#define mem(a) memset(a,0,sizeof(a))
#define elif else if
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
inline ll read()
{
    ll f=1,x=0;
    char ch;
    do
    {
        ch=getchar();
        if(ch=='-')
        f=-1;
    }
    while(ch<'0'||ch>'9');
    do
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    while(ch>='0'&&ch<='9');
    return f*x;
}
string s;
int n,t,p;
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>s;
	n=s.size()-1;
	rep(i,0,n)
	if(s[i]=='A')
	{
		t=i;
		break;
	}
	per(j,n,0)
	if(s[j]=='Z')
	{
		p=j;
		break;
	}
	cout<<p-t+1;
//	fclose(stdin);
//	fclose(stdout);
    return 0;
}


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

int main(){
    int n,m;
    cin >> n >>m;
    int s,c,ans[n]={0};
    ans[0]=-1;
    for(int i = 0;i<m;i++){
        cin >> s >> c;
        if(ans[s-1]<=0){ans[s-1]=c;}
        else{
            if(ans[s-1]!=c){
                cout << -1 << endl;
                return 0;
            }
        }
    }
    
    if(ans[0]==-1){
        if(n==1){
            cout <<0<<endl;
            return 0;
        }else{
            ans[0]=1;
        }
    }
    if(ans[0]==0){
        if(n==1){
            cout <<0<<endl;
            return 0;
        }
        cout <<-1<<endl;
        return 0;
    }
    for(int i=0;i<n;i++) cout << ans[i];
    cout <<endl;
    return 0;
}

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

int main() {

	int n; cin >> n;
	deque<ll> dq;
	for (int i = 0; i < n; i++) {
		ll a; cin >> a;
		if (i % 2 == 0) dq.push_back(a);
		else dq.push_front(a);
	}
	if (n % 2 != 0) reverse(dq.begin(), dq.end());
	for (auto itr = dq.begin(); itr != dq.end(); ++itr) {
		cout << *itr << " ";
	}
	return 0;
}

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

using namespace std;
using namespace __gnu_pbds;
 
template<typename T> using id_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update> ;
template<typename T> using id_setp = tree<pair<T,T>,null_type,less<pair<T,T>>,rb_tree_tag,tree_order_statistics_node_update> ;

#define f(i,x,n) for(i=x;i<n;i++)
#define fr(i,x,n) for(i=x;i>=n;i--)
#define pu push_back           
#define pp pop_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define SP(x) fixed<<setprecision(x)
#define IOS() ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
const long long MOD=1e9+7;
const long double PI = acos(-1);
const long long INF=INT_MAX;
const long long LINF=LLONG_MAX;
const long long N=1e5+1;
 
typedef long long ll;
typedef long double ld;
 
int main()
{
    IOS();
    ll h,i,j=1,ans=0;
    cin>>h;
    while(h>0)
    {
        ans+=j;
        h=h/2;
        j*=2;
    }
    cout<<ans<<'\n';

    return 0;
}


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

using namespace std;
int main() {
	int a_arr[3] = {1, 2, 3}, A, B, s;
	vector<int> v(a_arr, end(a_arr));
	cin >> A;
	cin >> B;
	auto rema = remove_if(v.begin(), v.end(), [&](int value) {return value == A; });
	auto remb = remove_if(v.begin(), v.end(), [&](int value) {return value == B; });
	v.erase(rema, v.end());
	v.erase(remb, v.end());
	cout << v[0] << endl;
	return 0;
}

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

int main()
{
	int a,b,c;
	cin >> a >> b >> c;
	if (a + b + c >= 22)
	{
		cout << "bust" << endl;
	}
	else
	{
		cout << "win" << endl;
	}
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    istream& in(cin);
    ostream& out(cout);
    int n;
    string f,c;
    in>>n;
    cout<<"? ";
    Fr(i,n) cout<<i<<" ";
    cout<<endl;
    cin>>f;
    int l=0,r=n,m;
    while(r-l>1){
        m=(l+r)>>1;
        cout<<"? ";
        Fr(i,n) cout<<(i>m?i+n:i)<<" ";
        cout<<endl;
        cin>>c;
        if(c==f) r=m;
        else l=m;
    }
    vector<string> ans(2*n+1);
    ans[r]=f;
    ans[r+n]=(f=="Red"?"Blue":"Red");
    for(int i=r+1;i<r+n;++i){
        cout<<"? ";
        Fr(j,l) cout<<j<<" ";
        for(int j=r+n+1;j<=2*n;++j) cout<<j<<" ";
        cout<<i<<endl;
        cin>>ans[i];
    }
    Fr(j,l){
        cout<<"? ";
        for(int i=r+1;i<r+n;++i) cout<<i<<" ";
        cout<<j<<endl;
        cin>>ans[j];
    }
    for(int j=r+n+1;j<=2*n;++j){
        cout<<"? ";
        for(int i=r+1;i<r+n;++i) cout<<i<<" ";
        cout<<j<<endl;
        cin>>ans[j];
    }
    cout<<"! ";
    Fr(i,2*n) cout<<ans[i][0];
    cout<<endl;
}

Measured memory_bytes: 724
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a),i##formax=(b);i<i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formax=(b);i>=i##formax;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)
#define show(x) cout<<#x<<" = "<<x<<endl;
#define all(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))
#define bitComb(a,n,k) for(int a##x,a##y,a=(1<<k)-1;a<(1<<n);a##x=a&-a,a##y=a+a##x,a=(((a&~a##y)/a##x)>>1)|a##y)
#define uniq(v) sort(all(v));v.erase(unique(all(v)), v.end())
#define bit(n) (1LL<<(n))
#define randInt(l,r) (uniform_int_distribution<ll>(l,r)(rnd))
#define randDouble(l,r) (uniform_real_distribution<double>(l,r)(rnd))
#define dout(d) printf("%.12f\n",d)

typedef long long ll;
typedef __int128_t lll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>ostream& operator<<(ostream& o,const pair<T,Y>& p){return o<<"("<<p.fi<<", "<<p.se<<")";}
template<typename A,size_t N,typename T>void Fill(A (&array)[N],const T&v){fill((T*)array,(T*)(array+N),v);}
lll gcd(lll a,lll b,lll &x,lll &y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll gcd(ll a,ll b){lll x=0,y=0;return gcd(a,b,x,y);}
ll modInv(ll a,ll m){lll x,y;gcd(a,m,x,y);return (x%m+m)%m;}
ll modPow(lll a,lll n,ll m){if(!a)return a;lll p=1;for(;n>0;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return(ll)p;}
bool isPrime(ll n){if(n<2||n%2==0)return n==2;lll t=n-1,d=t/(t&-t);for(lll a:{2,325,9375,28178,450775,9780504,1795265022})if(a%n){for(t=d,a=modPow(a,t,n);t!=n-1&&a!=1&&a!=n-1;a=a*a%n,t=t*2%n);if(a!=n-1&&t%2==0)return 0;}return 1;}
const int IINF = 1e9+6;
const ll LINF = 1e18;
const int MOD = 1e9+7;
const double PI = acos(-1);
const double EPS = 1e-10;
static random_device rd;
static mt19937 rnd(rd());

const int N = 1e5;
int n, ans=IINF;
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n;
  FOR(i, 0, n){
    int a;
    cin >> a;
    mins(ans, __builtin_ctz(a));
  }
  cout << ans << endl;
}

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

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define LOOP(i) while(i--)
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);

	int N=in();
	map<int,int> C;
	REP(i,N){
		C[in()]++;
	}

	int sum = 0;
	for(auto& x:C){
		if(x.second>x.first){
			sum += x.second-x.first;
		}
		else if(x.second<x.first){
			sum += x.second;
		}
	}

	out(sum);
	return 0;
}

Measured memory_bytes: 4736
#include<cstdio>
int n,k,m,j,p,i;long f[333][333][333];main(){scanf("%d%d%d",&n,&k,&m);for(f[i=0][1][0]=1;i<=n;++i)for(j=1;j<=k;++j)for(p=i;~p;--p)(f[i+1][j][p]+=f[i][j][p]*(p+1))%=m,((p?f[i][j][p-1]:f[i][j+1][i])+=f[i][j][p])%=m;printf("%d",f[n][k+1][n]);}

Measured memory_bytes: 262144
#include<bits/stdc++.h>
using namespace std;
template<class T>inline void init(T&x){
	x=0;char ch=getchar();bool t=0;
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);
	if(t) x=-x;return;
}
const int N=1000;
char S[N];
int main()
{
	int n;init(n);
	scanf("%s",S);
	int a=0,b=0;
	for(int i=0;i<n;++i){
		if(S[i]=='R') ++a;
		else if(S[i]=='B') ++b;
	}
	if(a>b) puts("Yes");
	else puts("No");
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define sf(i,s) for(i=0;s[i]!='\0';i++)
#define watch(x) cout << (#x) << " is " << (x) << endl
#define inf INT_MAX
#define pb push_back
#define mp make_pair
#define gcd(x,y) __gcd(x,y)
#define bc(x) __builtin_popcountll(x)
//cin.ignore(1, '\n');
ll power(ll a,ll b)
{
    if(b==0)
    return 1;
    if(b==1)
    return a;
    else
    {
        ll t=power(a,b/2);
        if(b%2==0)
        return ((t%mod)*(t%mod))%mod;
        else
        return ((((t%mod)*(t%mod))%mod)*((a%mod)%mod))%mod;
    }
}
void solve()
{
  ll n,w,i,j;
  cin>>n>>w;
  ll dp[n+1][w+1],wi[n+1],val[n+1];
  f(i,1,n+1)
  {
      cin>>wi[i]>>val[i];
  }
  f(i,0,w+1)
  dp[0][i]=0;
  f(i,0,n+1)
  dp[i][0]=0;
  f(i,1,n+1)
  {
      f(j,1,w+1)
      {
          if(i==0||j==0)
          {
              dp[i][j]=0;
          }
          else
          {
              if(wi[i]<=j)
              {
                  dp[i][j]=max(dp[i-1][j],dp[i-1][j-wi[i]]+val[i]);
                  //if(wi[i]==j)
                    //watch(dp[i][j]);
              }
              else
                dp[i][j]=dp[i-1][j];
          }
      }
  }
  cout<<dp[n][w];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}


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

using namespace std;

int N;
int idx[100005];
set<int> st;

int main(){
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for(int i =1; i<=N; i++){
        int n;
        cin >> n;
        idx[n] = i;
    }
    st.insert(0), st.insert(N+1);
    long long ans = 0;
    for(int n = N; n>0; n--){
        int p = idx[n];
        int lb = *(--st.lower_bound(p));
        int ub = *(st.upper_bound(p));
        if(lb){
            int t = *(--st.lower_bound(lb));
            ans += 1LL*n*(lb-t)*(ub-p);
        }
        if(ub != N+1){
            int t = *(st.upper_bound(ub));
            ans += 1LL*n*(p-lb)*(t-ub);
        }
        st.insert(p);
    }
    cout << ans << endl;
}


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

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

	for (int i = 0; i < a; i++) {
		if (s[i] == '-') {
			cout << "No" << endl;
			return 0;
		}
	}

	for (int i = a + 1; i < a + b + 1; i++) {
		if (s[i] == '-') {
			cout << "No" << endl;
			return 0;
		}
	}
	
	if (s[a] == '-') cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(N: int, a: "List[int]"):
    all = 0
    for i in a:
        all ^= i
    
    ans =[]
    for i in a:
        ans.append(all ^ i)

    aa = [str(an) for an in ans]
    print(" ".join(aa))

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()


Measured memory_bytes: 107100
#include<stdio.h>
#define Maxn 100000
#define Maxq 50000

int main()
{
  int i=0,k=0,n,q,mid,left,right;
  int A[Maxn],B[Maxq];
  
  scanf("%d",&n);
  for(i=0;i<n;i++)
    {
      scanf("%d",&A[i]);
    }
  scanf("%d",&q);
  for(i=0;i<q;i++)
    {
      scanf("%d",&B[i]);
    }

  
  for(i=0;i<q;i++)
    {
      left=0;
      right=n;

      
      while(left<right)
	{
	  mid=(left+right)/2;
	  if(B[i]==A[mid])
	    {
	      k++;
	      break;
	    }
	  if(B[i]>A[mid])
	    {
	      left=mid+1;
	    }
	  else if(B[i]<A[mid])
	    {
	      right=mid;
	    }
	}
    }
  printf("%d\n",k);

  return 0;
}

Measured memory_bytes: 1184
n = int(input())
al = list(map(int, input().split(' ')))

alp1 = []
for a in al:
    alp1.append(a + 1)

alm1 = []
for a in al:
    alm1.append(a - 1)

ass = alm1 + al + alp1

d = {}
for i in ass:
    d.setdefault(i, 0)
    d[i] += 1

print(max(d.values()))


Measured memory_bytes: 29640
open System
let arrLen = stdin.ReadLine () |> System.Int32.TryParse |> snd
let halfArrLen = arrLen / 2
let numArr =
  let str = stdin.ReadLine ()
  str.Split [|' '|]
  |> Array.map (System.Int32.TryParse >> snd)


let indexedNumArr = Array.zip [|0..arrLen-1|] numArr
let evenArr, oddArr = 
  Array.partition (fun (index, _) -> index % 2 = 0 ) indexedNumArr
let genCountMap arr =
  let increment map num =
    match Map.tryFind num map with
    | Some cnt -> Map.add num (cnt + 1) map
    | None -> Map.add num 1 map
  Array.fold increment Map.empty arr

let evenMap = Array.map (fun (_, num) -> num) evenArr |> genCountMap
let oddMap = Array.map (fun (_, num) -> num) oddArr |> genCountMap

let evenSorted = Map.toList evenMap |> List.sortByDescending (fun (_, cnt) -> cnt) 
let oddSorted = Map.toList oddMap |> List.sortByDescending (fun (_, cnt) -> cnt)

let ans =
  match List.head evenSorted, List.tail evenSorted, List.head oddSorted, List.tail oddSorted with
  | (el1, cnt1), _, (el2, cnt2), _ when el1 <> el2 -> arrLen - cnt1 - cnt2
  | _, [], _, [] -> halfArrLen
  | _, [], _, (_, cnt) :: _ 
  | _, (_, cnt) :: _, _, [] -> arrLen - halfArrLen - cnt
  | (_, cnt1), (_, cnt2) :: _, (_, cnt3), (_, cnt4) :: _ ->
    if cnt2 > cnt4 then arrLen - cnt2 - cnt3
    else arrLen - cnt1 - cnt4
    
printfn "%i" ans

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

int main() {
  int N, M, X, Y;
  cin >> N >> M >> X >> Y;

  int x[N];
  int y[M];
  for (int i = 0; i < N; i++) {
    cin >> x[i];
  }
  for (int i = 0; i < M; i++) {
    cin >> y[i];
  }

  sort(x, x+N);
  sort(y, y+M);

  string ans = "War";
  for (int z = -99; z <= 100; z++) {
    if(!( X < z )) continue;
    if(!( z <= Y )) continue;
    if(!( x[N-1] < z )) continue;
    if(!( z <= y[0] )) continue;
    ans = "No War";
    break;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3640
n, m = [int(x) for x in input().split()]
nac = 0
nwa = 0
past = {}
for i in range(m):
    p, s = [x for x in input().split()]
    d = p + s
    if (p + 'AC') in past:
        next
    else:
        if s == 'WA':
            past[d] = 1 if d not in past else past[d] + 1
        else:
            past[d] = 1
            nac += 1
            nwa += 0 if (p + 'WA') not in past else past[p + 'WA']
print(nac, nwa)

Measured memory_bytes: 17168
import itertools
N = int(input())
C = {"M":0,"A":0,"R":0,"C":0,"H":0}
for _ in range(N):
    s = input().strip()
    x = s[0]
    if x in C:
        C[x] += 1
D = list(C.values())
cnt = 0
for y in itertools.combinations(range(5),3):
    cnt += D[y[0]]*D[y[1]]*D[y[2]]
print(cnt)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  vector<int> vec(20);
  for(int i = 0; i < n; i++){
    cin >> vec.at(i);
  }
  
  int count;
  count = n;
  
         for (int i = 1; i < n; ++i) {
          for (int j = 0; j < i; j++){
            if(vec.at(i) < vec.at(j)){
              count--;
              break;
            }
          }
         }
  cout << count << endl;
}

        
 

Measured memory_bytes: 256
n, m, x = map(int,input().split())
ca = [list(map(int,input().split())) for i in range(n)]
import itertools
import numpy as np
from collections import deque

ca = np.array(ca)
bit_all = list(itertools.product(range(2),repeat=n))
ans = deque()

for bit in bit_all:
    bit = bit*(m+1)
    bit = np.array(bit).reshape([m+1,n]).T
    buy =  ca * bit
    buy = list(np.sum(buy,axis=0))
    if min(buy[1:]) >= x:
        ans.append(buy[0])

ans = list(ans)
if len(ans) == 0:
    print(-1)
else:
    print(min(ans))

Measured memory_bytes: 27640
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
using P = pair<int,int>;
vector<pair<int,ll>> ki[110000];
vector<int> even,odd;

void dfs(int now,int last,ll d){
    if(d%2 == 0)even.push_back(now);
    else odd.push_back(now);
    for(pair<int,ll> x:ki[now]){
        int next = x.first;
        ll dist = x.second;
        if(next == last)continue;
        dfs(next,now,d+dist);
    }
}
int main()
{
    int n;
    cin >> n;
    rep(i,n-1){
        int u,v;
        ll w;
        cin >> u >> v >> w;
        u--;v--;
        ki[u].push_back(pair<int,ll>(v,w));
        ki[v].push_back(pair<int,ll>(u,w));
    }
    dfs(0,-1,0);
    vector<int> ans(n);
    rep(i,even.size())ans[even[i]] = 0;
    rep(i,odd.size())ans[odd[i]] = 1;
    rep(i,n)cout << ans[i] << endl;


    return 0;
}

Measured memory_bytes: 11388
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author JustLive
 */

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int mod = 1000000007;
const int inf = 1000000000;
const ll infll = (ll)inf * (ll)inf;

class TaskC {
public:
    void solve(istream& in, ostream& out) {
        ll n, y;
        in >> n >> y;
        for (ll a = 0; a <= n; a++) {
            for (ll b = 0; b <= n; b++) {
                ll c = n - a - b;
                if (c < 0) {
                    continue;
                }
                if (a * 10000 + b * 5000 + c * 1000 == y) {
                    out << a << " " << b << " " << c;
                    return;
                }
            }
        }
        out << "-1 -1 -1";
    }
};


int main() {
    TaskC solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}


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

using namespace std;

typedef long long ll;

const double eps = 0.00001;
const int MOD = 1000000007; //998244353
const int INF = 1070000055;
const long long LINF = 1223372000000000555;
const int N = 1050555;
const int M = 6525;

vector<int> g[N];

bool used[N];
int cnt = 0;
void dfs(int v){
    cnt++;
    used[v] = true;
    for (int q : g[v]){
        if (!used[q]) dfs(q);
    }
}

void solve(){
    int n, m;
    cin >> n >> m;

    while (m--){
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    int ans = 0;
    for (int i = 1; i <= n; i++){
        if (used[i]) continue;
        cnt = 0;
        dfs(i);
        ans = max(ans, cnt);
    }

    cout << ans;

}


int main() {
    ios_base::sync_with_stdio(false);
#ifdef dddxxz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else

#endif

    int T = 1;
    //cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}

Measured memory_bytes: 40900
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF 2 << 29
#define MOD 1000000007
#define Yes(f) puts((f)? "Yes" : "No")
#define YES(f) puts((f)? "YES" : "NO")
int gcd(int a, int b) {
	if (b != 0)return gcd(b, a % b);
	return a;
}
int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}

int main(){
	string s; cin >> s;
	if(s == "ABC") cout << "ARC" << endl;
	else cout << "ABC" << endl;
}

Measured memory_bytes: 3596
#include <iostream>
using namespace std;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
  
    int n, x=0;
    cin >> n;
    int l[n], r[n];
    for(int i=0;i<n;i++){
        cin >> l[i] >> r[i];
        x+=r[i]-l[i]+1;
    }
    cout << x << "\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>
#include <ios>
#include <cctype>
#include <cstdio>
#include <functional>
#include <cassert>
#include <fstream>

using namespace std;
using ll = long long;

#define REP(i,a) for(int i = 0;i < (a);++i)
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define FORR(i,a,b) for(int i = (a) - 1;i >=(b);--i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SIZE(obj) (int)(obj).sizeT()
#define YESNO(cond,yes,no){cout <<((cond)?(yes):(no))<<endl; }
#define SORT(list) sort(ALL((list)));
#define RSORT(list) sort((list).rbegin(),(list).rend())
#define ASSERT(cond,mes) assert(cond && mes)

constexpr int MOD = 1'000'000'007;
constexpr int INF = 1'050'000'000;

template<typename T>
T round_up(const T& a, const T& b) {
    return (a + (b - 1)) / b;
}

template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
}

template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2>& p) {
    os << p.first << p.second;
    return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    REP(i, (int)v.size())is >> v[i];
    return is;
}

template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
    REP(i, (int)v.size())os << v[i] << endl;
    return os;
}

template <typename T>
T clamp(T& n, T a, T b) {
    if (n < a)n = a;
    if (n > b)n = b;
    return n;
}

template <typename T>
static T GCD(T u, T v) {
    T r;
    while (v != 0) {
        r = u % v;
        u = v;
        v = r;
    }
    return u;
}

template <typename T>
static T LCM(T u, T v) {
    return u / GCD(u, v) * v;
}

std::vector<int> enum_div(int n) {
    std::vector<int> ret;
    for (int i = 1; i*i <= n; ++i) {
        if (n%i == 0) {
            ret.push_back(i);
            if (i != 1 && i*i != n) {
                ret.push_back(n / i);
            }
        }
    }
    return ret;
}

template<typename T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

struct ToUpper {
    char operator()(char c) { return toupper(c); }
};

struct ToLower {
    char operator()(char c) { return tolower(c); }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);


    string S;
    cin >> S;

    bool e = false, w = false, s = false, n = false;
    REP(i, S.length()) {
        if (S[i] == 'E')e = true;
        if (S[i] == 'W')w = true;
        if (S[i] == 'S')s = true;
        if (S[i] == 'N')n = true;
    }

    bool b = (e && w) || (!e && !w);
    b = b && ((s && n) || (!s && !n));
    YESNO(b, "Yes", "No");

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include <cstdio>
#include<vector>

using namespace std;

int main(){
    long n,a,b,c,d,e;
    long min = 1000000000000000;
    for (int i =0; i < 6; i++){
        long tmp;
        cin >> tmp;
        if (i == 0){
            n = tmp;
        }
        else
        {
            if (tmp < min){
                min = tmp;
            }
        }
    }
    if (n % min == 0){
        cout << n / min + 4 << endl;
    }else{
        cout << n / min + 5 << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
char s[110];
int n,pos,maxn;
int main(){
    scanf("%d%s",&n,s+1);
    for(int i=1;i<=n;++i){
        if(s[i]=='I') ++pos;
        else --pos;
        maxn=max(maxn,pos);
    }
    printf("%d\n",maxn);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); ++i)
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using Graph = vector<vi>;  // vi <=> vl
using P = pair<int, int>;  // int <=> ll
const int MOD = 1e9+7;
const double EPS = 1e-9;

int main() {
  int H, W;
  cin >> H >> W;
  Graph G(H, vi(W));
  rep(i,H) rep(j,W) cin >> G[i][j];

  Graph move;
  rep(i,H) {
    rep(j,W-1) {
      if (G[i][j]%2) {
        ++G[i][j+1];
        vi tmp = {i+1, j+1, i+1, j+2};
        move.push_back(tmp);
      }
    }
  }
  rep(i,H-1) {
    if (G[i][W-1]%2) {
      ++G[i+1][W-1];
      vi tmp = {i+1, W, i+2, W};
      move.push_back(tmp);
    }
  }

  cout << move.size() << endl;
  rep(i,move.size()) {
    rep(j,4) {
      cout << move[i][j];
      if (j<3) cout << " ";
      else cout << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 10032
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<iomanip>
#include<set>
#include<numeric>
#include<sstream>
#include<random>
#include<cassert>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
const int inf = 1e9 + 7;
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
#define ceil(a, b) a / b + !!(a % b)

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int v[n];
    rep(i, n) cin >> v[i];
    int ans = 0;
    rep(i, n) {
        int tmp;
        cin >> tmp;
        v[i] -= tmp;
        if (v[i] > 0) ans += v[i];
    }
    cout << ans << endl;
    
}




Measured memory_bytes: 256
from collections import deque
S=input()
Q=int(input())

X=deque(S)
f=1
for _ in range(Q):
    A=list(input().split())
    if A[0]=="1":
        f*=-1
    if A[0]=="2":
        if A[1]=="1":
            if f==1:
                X.appendleft(A[2])
            if f==-1:
                X.append(A[2])
        if A[1]=="2":
            if f==-1:
                X.appendleft(A[2])
            if f==1:
                X.append(A[2])

if f==-1:
    print("".join(list(reversed(X))))
else:
    print("".join(list(X)))

Measured memory_bytes: 8692
#include <iostream>

using namespace std;

int main(int argc, const char * argv[]) {
    int R;
    
    cin >> R;
    if (R <= 1199) {
        cout << "ABC" << endl;
    }
    else if (R <= 2799 && R > 1199) {
        cout << "ARC" << endl;
    }
    else {
        cout << "AGC" << endl;
    }
    
    return 0;
}


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

int main() {
  
  int n,min,max,ans,l,k;
  cin>>n;
  vector<int> vec(n);
  for(int i=0; i<n; i++){
    cin>>vec.at(i);
  }
  ans=0;
  sort(vec.begin(), vec.end());
  
  for(int i=0; i<n-1; i++){
    for(int j=i+1; j<n; j++){
      min=vec.at(j)-vec.at(i)+1;
      max=vec.at(j)+vec.at(i)-1;
  
  
  
  
   
  
  
  
  
  
  
  
  
  
  
  
    size_t len = vec.size();
    

    // 二分探索
    auto iter_lower = lower_bound(vec.begin(), vec.end(), min);
    auto iter_upper = upper_bound(vec.begin(), vec.end(), max);

    // インデックスを取得
    long idx_lower = distance(vec.begin(), iter_lower);  // vec[idx_lower] = vec[7] = 6
    long idx_upper = distance(vec.begin(), iter_upper);  // vec[idx_upper] = vec[8] = 8

    // lower_bound で要素数を数える
   
    
    if( idx_lower<j+1){
      l=j+1;
    }
      else{
        l=idx_lower;
      }
      if(idx_upper-l>0){
        ans=ans+idx_upper-l;
      }
      
      
      
    
      
      
      
      
      
      
    }
  }
      
      
      cout<<ans;
}
  

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

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}


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

    // dmg,cost
    vector<pair<int,ll>> magics(N);
    REP(i,N) {
        int a,b;
        cin >> a >> b;
        magics[i] = make_pair(a,b);
    }

    // life[k] kを削るためにかかる最小の魔力
    vector<ll> life(H+1,INF);

    FOR(i,1,H+1) {
        REP(j,N) {
            auto last = i - magics[j].first;
            if (last <= 0) {
                chmin(life[i],magics[j].second);
                continue;
            }
            chmin(life[i],magics[j].second+life[last]);
        }
    }

    cout << life[H] << endl;




    return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<vector>
long long int const mod=1e9+7;
using namespace std;

long long int  recur(long long int  s,vector<long long int >&dp){
    if(s==0){
        return 0;
    }
    if(s==1||s==2){
        return -1;
    }
    if(dp[s]!=-1){
        return dp[s];
    }
    else
    {
        long long int  result=1;
        for(long long int  i=3;i<=s;i++)
        {
            if(s-i>=3)
            {
                long long int  p=recur(s-i,dp);
                result+=p;
                result%=mod;
            }
            
        }
        dp[s]=result;
    }
    return dp[s];
}


int  main(){
    long long int  s;
    cin>>s;
    if(s<3){
        cout<<"0";
        return 0;
    }
    vector<long long int >dp(s+1,-1);
    cout<<recur(s,dp);
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define vi vector<ll>
#define vvi vector<vi>
#define BITLE(n) (1LL<<(n))
#define BITCNT(n) (__builtin_popcountll(n))
#define SUBS(s,f,t) ((s).substr((f)-1,(t)-(f)+1))
#define ALL(a) (a).begin(),(a).end()
using namespace std;
struct Grid{ll x,y,t;};
struct Edge{ll to,cost;};
struct Graph{vector<vector<Edge>>E;int V;
  const ll Inf = llINF;const int MAX_V=201010;vector<ll>d;
  Graph(int n):E(n){d.resize(MAX_V);E.resize(n);V=n;}
  void init(){for(int i=0;i<MAX_V;i++)d[i]=Inf;}
  void add_edge(ll from,ll to,ll cost){E[from].pb({to,cost});}
};
struct UF
{
  vector<int> par; // 親のインデックスを記憶する配列
  vector<int> sz; // サイズを記憶する。
  vector<int> rank;
  // 初期化
  UF(int n):par(n),sz(n),rank(n){
    for(int i = 0; i < n; i++){
      par[i] = i;sz[i] = 1;rank[i] = 0;
    }
  }
  // 親を求める
  int find(int x) {
    if (par[x] == x) return x;
    else return par[x] = find(par[x]);
  }
  // xとyの属する集合を併合
  void merge(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    if(rank[x] < rank[y]){
      par[x] = y;
      sz[y] += sz[x];
    }
    else{
      par[y] = x;
      sz[x] += sz[y];
      if(rank[x] == rank[y])rank[x]++;
    }
  }
  // xとyが同じ集合ならtrue
  bool same(int x, int y) { return find(x) == find(y); }
  // 素の集合のサイズを求める
  int size(int n){return sz[find(n)];}
};
vi edg(222222);
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n,m;cin>>n>>m;
  UF uni(n+10);
  for(int i=0;i<m;i++){
    ll a,b;cin>>a>>b;
    edg[a]++;
    uni.merge(a,b);
  }
  ll anum=uni.size(1);
  ll bnum=uni.size(2);
  ll cnt=n-(anum+bnum);
  ll ans=0;
  ll acn=0;
  ll bcn=0;
  for(int i=0;i<n;i++){
    if(i==1||i==0)continue;
    if(uni.find(i+1)==uni.find(1)){
      acn++;
    }else if(uni.find(i+1)==uni.find(2)){
      bcn++;
    }
  }
  // cout<<anum<<" "<<bnum<<" "<<cnt<<" "<<m<<endl;
  cout<<max(((anum+cnt)*(anum+cnt-1)/2)+((bnum)*(bnum-1)/2)-m,
	    ((anum)*(anum-1)/2)+(bnum+cnt)*(bnum+cnt-1)/2-m)<<endl;
  return 0;
}


Measured memory_bytes: 3200
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

int n,k,t,l,r,mid;

bool check(int p)
{
	return n-1<=(long long)p*(k-1);
}

int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&t);
		
	l=0,r=n-1;
	while(l<r-1)
	{
		mid=(l+r)>>1;
		if(check(mid))r=mid;
		else l=mid;
	}
	
	printf("%d",r);
	
	return 0;
}

Measured memory_bytes: 256
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>


using namespace std;


int n,a[110],ans=1;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>a[i];
    sort(a,a+n);
    for(int i=1;i<n;i++)
    if(a[i]!=a[i-1])
    ans++;
    cout<<ans;
    system("pause");
    return 0;
}       

Measured memory_bytes: 504
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = Integer.parseInt(s.next());
        int[] v = new int[n];
        int[] c = new int[n];
        int[] dp = new int[n];


        for (int i = 0; i < n; i++) {
            dp[i] = 0;
        }
        for (int i = 0; i < n; i++) {
            v[i] = Integer.parseInt(s.next());
        }
        for (int i = 0; i < n; i++) {
            c[i] = Integer.parseInt(s.next());
        }

        dp[0] = 0;

        for (int i = 1; i < n; i++) {
            int tmp = dp[i - 1] + (v[i - 1] - c[i - 1]);
            dp[i] = tmp > dp[i - 1] ? tmp : dp[i - 1];
        }

        int tmp = dp[n - 1] + (v[n - 1] - c[n - 1]);
        dp[n - 1] = tmp > dp[n - 1] ? tmp : dp[n - 1];

        System.out.println(dp[n - 1]);
    }
}

Measured memory_bytes: 21716
#include<iostream>
#include<iomanip>

using namespace std;
using ll=long long;

int main(){
  std::cin.tie(nullptr);                  // 標準入出力高速化
  std::ios_base::sync_with_stdio(false);  // SとS++の入出力出力を非同期
  std::cout << std::fixed << std::setprecision(15);  // 小数を10進数表示
  ll n,m;
  cin>>n>>m;
  cout<<(m>2*n?n:m/2)+max(m-2*n,0ll)/4;
}

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

int main(){
    int H,W;
    scanf("%d %d",&H,&W);
    vector<string> S(H);
    int i,j;
    for(i=0;i<H;i++){
        cin >> S[i];
    }
    
    int left[H][W],right[H][W],up[H][W],down[H][W];
    for(i=0;i<H;i++){
        for(j=0;j<W;j++){
            if(S[i][j]=='#'){
                left[i][j] = 0;
                up[i][j] = 0;
            }else{
                if(j==0) left[i][j] = 1;
                else left[i][j] = left[i][j-1] + 1;
                if(i==0) up[i][j] = 1;
                else up[i][j] = up[i-1][j] + 1;
            }
        }
    }
    for(i=H-1;i>=0;i--){
        for(j=W-1;j>=0;j--){
            if(S[i][j]=='#'){
                right[i][j] = 0;
                down[i][j] = 0;
            }else{
                if(j==W-1) right[i][j] = 1;
                else right[i][j] = right[i][j+1] + 1;
                if(i==H-1) down[i][j] =1;
                else down[i][j] = down[i+1][j] + 1;
            }
        }
    }

    int maxLamp=0;
    int lamp;
    for(i=0;i<H;i++){
        for(j=0;j<W;j++){
            lamp = left[i][j] + up[i][j] + down[i][j] + right[i][j] - 3;
            if(maxLamp < lamp) maxLamp = lamp;
            
        }
    }

    printf("%d\n",maxLamp);

    return 0;
}

Measured memory_bytes: 66816
import sys, copy, math, collections, itertools

n = int(input())
a, b = (int(i) for i in input().split())
p = list(map(int, input().split()))

n1 = len([i for i in p if i <= a])
n2 = len([i for i in p if a < i <= b])
n3 = len([i for i in p if b < i])
print(min(n1,n2,n3))



Measured memory_bytes: 3700
from collections import Counter

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

n = int(input())

li = prime_factorize(n)

c = Counter(li)

ans = 0
for v in c.values():
  num = 1
  cnt = 2
  while v >= num:
    ans += 1 
    num += cnt
    cnt += 1

# print(list(c.items()))

print(ans)
  

Measured memory_bytes: 9464
n,l = map(int, input().split())
a = list(map(int, input().split()))
ans = "Impossible"
last = 0

for i in range(n-1):
    A = a[i]+a[i+1]
    if A>=l:
        ans= "Possible"
        last = i+1
        break

if ans=="Impossible":
    print(ans)
else:
    print(ans)

    if last!=1:
        for i in range(last-1):
            print(i+1)

    if last!=n-1:
        for i in reversed(range(last+1,n)):
            print(i)

    print(last)

Measured memory_bytes: 14052
#include<iostream>

using namespace std;


int main() {
	int n, m, l;
	int**A;
	int**B;
	long long**C;

	cin >> n >> m >> l;

	//new
	A = new int*[n];
	for (int i = 0; i < n; i++)A[i] = new int[m];

	B = new int*[m];
	for (int i = 0; i < m; i++)B[i] = new int[l];

	C = new long long*[n];
	for (int i = 0; i < n; i++)C[i] = new long long[l];

	//C????????????
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < l; j++) {
			C[i][j] = 0;
		}
	}

	//cin
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> A[i][j];
		}
	}

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

	//??????
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < l; j++) {
			for (int k = 0; k < m; k++) {
				C[i][j] += A[i][k] * B[k][j];
			}
		}
	}

	//??????
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < l; j++) {
			if (j != 0)cout << " ";
			cout << C[i][j];
		}
		cout << endl;
	}

	//delete
	for (int i = 0; i < n; i++) {
		delete[]A[i];
		A[i] = 0;
	}
	delete[]A;
	A = 0;

	for (int i = 0; i < m; i++) {
		delete[]B[i];
		B[i] = 0;
	}
	delete[]B;
	B = 0;

	for (int i = 0; i < n; i++) {
		delete[]C[i];
		C[i] = 0;
	}
	delete[]C;
	C = 0;

	return 0;
}

Measured memory_bytes: 1344
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>
#include<math.h>
#include<bitset>
#include<queue>
#include<set>
#include<iomanip>
#include<math.h>
#include<assert.h>
#include<string>
#include<cstdlib>
//#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long INF = 1LL << 40;
const double INFD = 1e100;
const ll mod = 1000000007;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}


// ----------------------------------------------------------------------------
int main(){
  string S;
  vector<int> alpha(26,0);
  while(getline(cin,S)){
    for(int i=0; i<S.size(); i++){
      if(isupper(S[i])){
        alpha[S[i] - 'A']++;
      }else if(islower(S[i])){
        alpha[S[i] - 'a']++;
      }
    }
  }
  for(int i=0; i<26; i++){
    cout << (char)(i+'a') << " : " << alpha[i] << endl;
  }
  return 0;
}



Measured memory_bytes: 3180
# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline

A, B, C, X = [int(input()) for _ in range(4)]


# cnt = sum(1 for a in range(A+1) if X - 500*a >=0 for b in range(B+1) if 0 <= X-500*a-100*b <= 50*C)
cnt = sum(0 <= X-500*a-100*b <= 50*C for a in range(A+1) if X - 500*a>=0 for b in range(B+1))
print(cnt)

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

#define int long long
#define endl '\n'

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n; cin >> n;
    vector<int> a(n);
    int xr = 0;
    for (auto &i: a)
        cin >> i, xr ^= i;
    for (auto i: a)
        cout << (xr ^ i) << ' ';
}

Measured memory_bytes: 4756