akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define e "\n"
#define MaRiaMa { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
#define fix(n) cout << fixed << setprecision(n);
using namespace std;
int main()
{
	MaRiaMa;
	ll n;
	ll p[1000];
	p[0]= 2;
	p[1]= 1;
	cin >> n;
	for (int i = 2; i <= n; i++)
	{
		p[i] = (p[i - 2] + p[i - 1]);
	}
	cout << p[n];
}

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

int main(){
  int N;
  cin >> N;
  int res = 0;
  int pre = -1;
  int cnt = 0;
  for(int i = 0 ; i < N ; i++){
    int a;
    cin >> a;
    if(a != pre){
      res += cnt/2;
      pre = a;
      cnt = 1;
    }
    else {
      cnt++;
    }
  }

  res += cnt/2; 
  
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	string s;
	scan(s);
	if(s[0]==s[1]||s[1]==s[2]||s[2]==s[3]) prin("Bad");
	else prin("Good");
	return 0;
}


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

using namespace std;

bool isPrime(int n) {
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) return false;
	}
	return true;
}
int main() {

	while (1) {
		int n;
		cin >> n;
		if (n == 0) break;

		for (int i = n - 2; i >= 0; i--) {
			if (isPrime(i) && isPrime(i + 2)) {
				cout << i << " " << i + 2 << endl;
				break;
			}
		}
	}
	return 0;
}


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

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

#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 MT make_tuple
#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,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;


using tp = tuple<LL,LL,LL>;

LL N, M, K;
LL A, B, C;
LL T;

LL calc(LL t, LL l){
  return min(l, t / A);
}

tp calc_next(tp tt){
  LL t, l, k;
  tie(k,t,l) = tt;

  --k;
  LL nl = l - k - 1;
  LL nt = t - (k+1) * C;
  LL nk = calc(nt, nl) + 1;
  
  return MT(nk, nt, nl);
}

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

  cin >> N >> M >> K;
  cin >> A >> B >> C;
  cin >> T;
  VL xs(M);
  REP(i,M){
	cin >> xs[i];
	--xs[i];
  }

  LL ans = 0;
  priority_queue<tp> pq;
  for(int i=0;i+1<M;++i){
	LL l = xs[i+1] - xs[i] - 1;
	LL t = T - xs[i] * B;
	LL k = calc(t, l);
	if(t < 0) continue;
	ans += k + 1;
	LL nl = l - k - 1;
	LL nt = t - (k+1) * C;
	LL nk = calc(nt, nl) + 1;
	if(nk <= 0 || nt < 0 || nl < 0){
	  continue;
	}
	pq.push(MT(nk,nt,nl));
  }

  VL buf;
  K -= M;
  for(int i=0;i<K && !pq.empty();++i){
	tp tt = pq.top();
	pq.pop();

	ans += get<0>(tt);
	tp nt = calc_next(tt);

	if(get<0>(nt) <= 0 || get<1>(nt) < 0) continue;
	pq.push(nt);
  }

  if((N-1)*B <= T) ++ans;
  // except for s.t. 1
  cout << ans-1 << endl;
  
  return 0;
}

Measured memory_bytes: 3244
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 1e9;
// const int MOD = 1e9 + 7;

int main() {
    int N, A, B;
    cin >> N >> A >> B;
    string S;
    cin >> S;
    int sum = 0;
    int b = 0;
    for (auto c : S) {
        if (c == 'a') {
            if (sum < A + B) {
                cout << "Yes\n";
                sum++;
            } else {
                cout << "No\n";
            }
        } else if (c == 'b') {
            if (sum < A + B && b < B) {
                cout << "Yes\n";
                b++;
                sum++;
            } else {
                cout << "No\n";
            }
        } else {
            cout << "No\n";
        }
    }
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(n); i++)
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(){
    ll n,k; cin>>n>>k;
    vector<ll> h(n);
    rep(i,n) cin>>h[i];
    sort(h.begin(),h.end(),greater<ll>());
    if(n<=k) cout<<0<<endl;
    else{
        ll res=0;
        for(ll i=k; i<n; i++){
            res+=h[i];
        }
        cout<<res<<endl;
    }
    return 0;
}

Measured memory_bytes: 1792
#include<stdio.h>

int main(void){
  int i;
  int a[50];
  int n,p,c;

  while(1){
      scanf("%d %d",&n,&p);
      if(!n && !p){break;}
      c = p;
      for(i=0;i<n;i++)a[i] = 0; //óâªàÂ¬ÎÌðú»

      i = 0;
      do{
	if(c>0){
	  a[i]++;
	  c--;
	}else{
	  c = a[i];
	  a[i] = 0;
	}
	i++;
	if(i==n)i=0;
      }while(a[i]<p);
	
      printf("%d\n",i);
      
    }
  return 0;
}

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ALL(a) begin(a),end(a)
#define COUNTOF(a) (sizeof(a)/sizeof(a[0]))
#define SP << " " <<
#define FMT(a) #a<<":"<<a 
#define FMT2(a,b) #a<<":"<<a<<", "<<#b<<":"<<b 
#define FMT3(a,b,c) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c 
#define FMT4(a,b,c,d) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c<<", "<<#d<<":"<<d 
typedef long long ll;
template<class T> istream& operator >> (istream& s, vector<T>& v) {
  for (T& x: v) s >> x;
  return s;
}
inline void Yes(bool f=true){cout<<(f?"Yes":"No")<<endl;}
inline void YES(bool f=true){cout<<(f?"YES":"NO")<<endl;}
#define ANS(a) cout<<a<<endl

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

    int H,W; cin>>H>>W;
    string C;
    rep(i,H) {
        cin>>C;
        cout<<C<<"\n"<<C<<"\n";
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) begin(x),end(x)

using namespace std;

struct UnionFind {
  vector<int> parent;
  vector<int> diff;
  UnionFind (int n) : parent(n, -1), diff(n, 0) {}
  int root(int x) {
    if (parent[x] < 0) {
      return x;
    } else {
      int r = root(parent[x]);
      diff[x] += diff[parent[x]];
      parent[x] = r;
      return r;
    }
  }
  bool merge(int x, int y, int diff_xy) {
    int oldx = x, oldy = y;
    x = root(x); y = root(y);
    if (x == y) return false;
    diff_xy += diff[oldy] - diff[oldx];
    if (parent[y] < parent[x]) {
      diff_xy = -diff_xy;
      swap(x, y);
    }
    if (parent[x] == parent[y]) --parent[x];
    parent[y] = x;
    diff[y] = -diff_xy;
    return true;
  }
};

int main() {
  while(1){
    int n,m;
    cin>>n>>m;
    if (!n) break;
    UnionFind uf(n);
    REP(i,m) {
      string c;
      cin>>c;
      if (c == "!") {
        int a,b,w;
        cin>>a>>b>>w;
        --a;--b;
        uf.merge(a,b,w);
      } else {
        int a,b;
        cin>>a>>b;
        --a;--b;
        if (uf.root(a) != uf.root(b)) {
          cout << "UNKNOWN" << endl;
        } else {
          cout << (uf.diff[a] - uf.diff[b]) << endl;
        }
      }
    }
  }
  return 0;
}

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

  vector<int> l(n) ,d(n+1);
  rep(i,n) cin >> l.at(i);

  for(int i = 1 ;i < n + 1 ;i++){
      d.at(0) = 0;
      d.at(i) = d.at(i-1) + l.at(i-1);
      if(d.at(i) <= x) s++;
  }
  s++;

  cout << s << endl;
  

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define each(a, b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define show(x) cout <<#x<<" = "<<(x)<<endl
#define spair(p) cout <<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout <<" "<<kbrni;cout<<endl

using namespace std;

typedef pair<int,int>P;

struct LazySegmentTree {
private:
    int n;
    vector<int> node, lazy;
    vector<bool> lazyFlag;

public:
    LazySegmentTree(vector<int> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1);
        lazy.resize(2*n-1, INF);
        lazyFlag.resize(2*n-1, false);

        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = min(node[i*2+1], node[i*2+2]);
    }

    void lazyEvaluate(int k, int l, int r) {
        if(lazyFlag[k]) {
            node[k] = lazy[k];
            if(r - l > 1) {
                lazy[k*2+1] = lazy[k*2+2] = lazy[k];
                lazyFlag[k*2+1] = lazyFlag[k*2+2] = true;
            }
            lazyFlag[k] = false;
        }
    }

    void update(int a, int b, int x, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        lazyEvaluate(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            lazy[k] = x;
            lazyFlag[k] = true;
            lazyEvaluate(k, l, r);
        }
        else {
            update(a, b, x, 2*k+1, l, (l+r)/2);
            update(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = min(node[2*k+1], node[2*k+2]);
        }
    }

    int find(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        lazyEvaluate(k, l, r);
        if(b <= l || r <= a) return INT_MAX;
        if(a <= l && r <= b) return node[k];
        int vl = find(a, b, 2*k+1, l, (l+r)/2);
        int vr = find(a, b, 2*k+2, (l+r)/2, r);
        return min(vl, vr);
    }
};


int main() {
    int n,q;
    cin >> n >> q;
    LazySegmentTree seg( vector<int>(n, INT_MAX) );
    rep(i,q){
        int query;
        cin >> query;
        if(query == 0){
            int s,t,x;
            cin >> s >> t >> x;
            seg.update(s,t+1,x);
        }
        else{
            int s, t;
            cin >> s >> t;
            cout << seg.find(s,t+1) << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 5144
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;

int main()
{
  int N, a, b;
  int64_t ta=0, tb=0;
  cin >> N;
  
  vector<int> A(N), B(N), D(N);
  for(int i = 0; i < N; i++){
    cin >> a;
    A.at(i) = a;
  }
  for(int i = 0; i < N; i++){
    cin >> b;
    B.at(i) = b;
  }
  
  for(int i = 0; i < N; i++) D.at(i) = B.at(i) - A.at(i);
  for(int i = 0; i < N; i++){
    if(D.at(i) < 0){
      tb -= D.at(i);
    }else if(D.at(i) > 0){
      ta += D.at(i) / 2;
    }
  }
  if(tb <= ta) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
  
  /*
  int64_t mai=0, plu=0;
  for(int i = 0; i < N; i++){
    if(D.at(i) < 0) mai += D.at(i);
    else plu += D.at(i);
  }
  plu = plu + mai * 2;
  if(plu > 0) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
  */
  /*
  //for(int i = 0; i < N; i++) cout << D.at(i) << endl;
  //cout << "-----------" << endl;
  for(di = 0, pi = 0; di < N; di++){
    //cout << D.at(di) << endl;
    if(D.at(di) < 0){
      while(1){
        if(D.at(pi) < 0){
          if(pi == N-1){
            cout << "No" << endl;
            return 0;
          }
          pi++;
        }else{
          D.at(pi) += D.at(di)*2;
          //cout << "p" << pi << endl;
          break;
        }
      }
    }else{
      cout << "Yes" << endl;
      return 0;
    }
  }
  */
  /*
  for(int i = 0; i < N; i++){
    diff = B.at(i) - A.at(i);
    cout << diff << endl;
    if(diff < 0){
      if(i + 1 == N){
        cout << "No" << endl;
        break;
      }else{
        A.at(i+1) += 2*(-1*diff);
      }
    }
  }
  */
}

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

using namespace std;

#define PB push_back
#define f first
#define s second

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

bool seen[101];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, k;
    cin >> n >> k;
    for(int i=0; i<k; i++)
    {
        int d;
        cin >> d;
        for(int j=0; j<d; j++)
        {
            int x;
            cin >> x;
            seen[x] = true;
        }
    }
    int ans = 0;
    for(int i=1; i<=n; i++)
    {
        if(!seen[i])
            ans++;

    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i=0;i<N;i++)cin >> A[i];
  sort(A.begin(),A.end());
  int cnt=0;
  for(int i=1;i<N;i++){
    if(A[i-1]==A[i])cnt++;
  }
  if(cnt%2==1){cnt++;}
  cout << N-cnt << endl;
}

Measured memory_bytes: 640
#include <stdio.h>

// 入力制約
#define NUM_MIN ( ( int ) 2 )
#define NUM_MAX ( ( int ) 200000 )
#define PRICE_MIN ( ( int ) 1 )
#define PRICE_MAX ( ( int ) 1000000000 )

// 制約判定結果
typedef enum
{
	kSuccess,
	kError
}Result;

// プロトタイプ宣言
Result checkNumRange( int num, int min, int max );
int calcMaxPrice( int num, int* pPrice );

//****************************************************/
// @brief  メイン関数
// @param  無し
// @return 正常終了なら0、異常終了なら-1を返す
//****************************************************/
int main( void )
{
	int i;
	int num;
	int price[NUM_MAX];

	// 価格数の入力判定
	scanf( "%d\n", &num );
	if( checkNumRange( num, NUM_MIN, NUM_MAX ) == kError )
	{
		return -1;
	}

	// 価格の入力判定
	for( i = 0; i < num; i++ )
	{
		scanf( "%d\n", &price[i] );
		if( checkNumRange( price[i], PRICE_MIN, PRICE_MAX ) == kError )
		{
			return -1;
		}
	}

	// 計算した最大利益を出力
	printf( "%d\n", calcMaxPrice( num, &price[0] ) );

	return 0;
}

//****************************************************/
// @brief  入力値の制約判定
// @param  num : 判定対象の入力値
//         min : 最小値
//         max : 最大値
// @return 制約内ならkSuccess、制約外ならkErrorを返す
//****************************************************/
Result checkNumRange( int num, int min, int max )
{
	return ( ( num >= min ) && ( num <= max ) ) ? kSuccess : kError;
}

//****************************************************/
// @brief  最大利益の計算
// @param  num    : 計算対象数値の個数
// @param  pPrice : 計算対象を格納した配列先頭へのポインタ
// @return 最大利益
//****************************************************/
int calcMaxPrice( int num, int* pPrice )
{
	int i;
	int maxPrice = pPrice[1] - pPrice[0];
	int minPrice = pPrice[0];

	// 最大利益と最少利益を計算
	for( i = 1; i <= num - 1; i++ )
	{
		maxPrice = ( maxPrice > ( pPrice[i] - minPrice ) ) ? maxPrice : ( pPrice[i] - minPrice );
		minPrice = ( minPrice < pPrice[i] ) ? minPrice : pPrice[i];
	}

	// 最大利益を返す
	return maxPrice;
}



Measured memory_bytes: 2568
#include<bits/stdc++.h>
using namespace std;
    int f[3000][3000]={};
    int a[3000]={};
    int x,y,n;
int main()
{
    cin >> n >> x >> y;
    for (int i=1;i<=n;i++)
        for (int j=i;j<=n;j++)
            f[i][j]=j-i;

    for (int i=1;i<=x;i++)
        for (int j=y;j<=n;j++)
            f[i][j]=f[i][x]+f[y][j]+1;

    for (int i=x+1;i<y;i++)
        for (int j=y;j<=n;j++)
            f[i][j]=min(f[i][j],f[x][i]+f[y][j]+1);

    for (int i=1;i<=x;i++)
        for (int j=x+1;j<y;j++)
            f[i][j]=min(f[i][j],f[i][x]+f[j][y]+1);

    for (int i=x;i<=y;i++)
        for (int j=i+1;j<=y;j++)
            f[i][j]=min(f[i][j],f[x][i]+f[j][y]+1);
    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++)
            a[f[i][j]]++;
    for (int i=1;i<=n-1;i++)
        printf("%d\n",a[i]);
}


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


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

    int x[n][d];
    rep(i,n) rep(j,d) cin >> x[i][j];

    int count = 0;

        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                double norm = 0;
                double length = 0;
                for (int k = 0; k < d; ++k) {
                    int diff = abs(x[i][k] - x[j][k]);
                    norm += pow(diff,2);
                }
                length = pow(norm,0.5);
                //print(length);
                if(fmod(length,1) == 0)count++;
            }
        }

    print(count);
}

Measured memory_bytes: 256
import sys
import resource
sys.setrecursionlimit(10**5)
n = int(input())
l = [[] for _ in range(n+1)]
s = [0 for _ in range(n+1)]
ll = []
for i in range(n-1):
  ai,bi = map(int,input().split())
  l[ai].append([bi,i])
  l[bi].append([ai,i])
  s[ai] += 1
  s[bi] += 1
mx = 0
for i in range(1,n+1):
  if s[i] > mx:
    mx = s[i]
    mxi = i
print(mx)
ans = [0 for _ in range(n-1)]
def dfs(a,b,c):
  i = 1
  for h,j in l[a]:
    if h != b:
      if i == c:
        i += 1
      ans[j] = i
      dfs(h,a,i)
      i += 1
  return
dfs(mxi,0,0)
for x in ans:
  print(x)

Measured memory_bytes: 78968
#include<bits/stdc++.h>
std::string a, b, c;
int main() {
    std::cin >> a >> b >> c;
    std::cout << (char)std::toupper(a[0])
              << (char)std::toupper(b[0])
              << (char)std::toupper(c[0])
              << std::endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli N=100009;
lli n, k, a;
string s;
int main()
{
	cin>>n>>k>>s;
	for(int i=1;i<n;i++)
	{
		if(s[i]==s[i-1])
		{
			a++;
		}
	}
	cout<<min(n-1, a+2*k);
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v;
int main() {
    for(int i=0;i<3;i++){
        int x; scanf("%d",&x); v.push_back(x);
    }
    sort(v.begin(),v.end());
    int ans=0;
    ans+=(v[2]-v[0])/2; v[0]+=(v[2]-v[0])/2*2;
    ans+=(v[2]-v[1])/2; v[1]+=(v[2]-v[1])/2*2;
    sort(v.begin(),v.end());
    if(v[1]==v[0]&&v[2]==v[1]) printf("%d\n",ans);
    if(v[1]==v[0]&&v[2]-v[1]==1) printf("%d\n", ans+1);
    if(v[1]-v[0]==1&&v[2]-v[1]==1) printf("%d\n", ans+3);
    if(v[1]-v[0]==1&&v[2]-v[1]==0) printf("%d\n", ans+2);
}



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

int main(){
  string a,b;
  cin >> a >> b;
  bool ok=false;
  vector<char>ave(a.size());
  vector<char>bve(b.size());
  for(int i=0;i<a.size();i++){
    ave.at(i)=a.at(i);
  }
  for(int i=0;i<b.size();i++){
    bve.at(i)=b.at(i);
  }
  for(int i=0;i<a.size();i++){
    char c=ave.at(ave.size()-1);
    ave.pop_back();
    reverse(ave.begin(),ave.end());
    ave.push_back(c);
    reverse(ave.begin(),ave.end());
    if(ave==bve){
      ok=true;
      break;
    }
  }
  cout << (ok?"Yes":"No") << endl;
  return 0;
}

Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int x, n, y, i;
	scanf("%d", &n);
	if(n>=1 && n<=100){
            	x=800*n;
		if(n>15){
	
			y=((n/15)*200);
			printf("%d", x-y);
		}
		else{
			printf("%d", x);
		}
	}
	else{
		printf("Error");
	}
	return 0;
}

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

// boost
#include <boost/multiprecision/cpp_int.hpp>
using boost::multiprecision::cpp_int;

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;
using vld = vector<ld>;
using vvld = vector<vld>;

typedef pair<ll, ll> P;

#define bit(n) (1LL << (n))

//#define int long long

#define all(v) v.begin(), v.end()

#define rep(i, n) for (ll i = 0; i < n; i++)
#define REP(i, n) for (ll i = 1; i < n; i++)

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORm(i, m) for (auto i = m.begin(); i != m.end(); i++)

template <class T>
inline void chmax(T& a, T b) {
  a = std::max(a, b);
}
template <class T>
inline void chmin(T& a, T b) {
  a = std::min(a, b);
}

#define mod (ll)(1e9 + 7)
// #define mod (998244353ll)

const long long INF = 1LL << 60;

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

  string s;
  cin >> s;

  ll ans = 0;
  for (auto c : s) {
    if (c == '1') {
      ans++;
    }
  }

  cout << ans << endl;

  return 0;
}


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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};

ll p[55],t[55];

ll Calc(ll lv, ll maisuu)
{
    
    if(lv==0)
    {
        return 1LL;
    }
    if(maisuu<2)
    {
        return 0;
    }
    else if(maisuu<=t[lv-1]+1)
    {
        return Calc(lv-1, maisuu-1);
    }
    else if(maisuu <=t[lv-1]+2)
    {
        return p[lv-1]+1;
    }
    else
    {
        return p[lv-1]+ 1 + Calc(lv-1,maisuu-t[lv-1]-2);
    }
    
    return 0;
}

int main(){
    ll n,x,ans=0;
    cin>>n>>x;
    p[0]=1LL;
    t[0]=1LL;
    for(int i = 0; i < 52; i++)
    {
        p[i+1]=p[i]*2LL+1LL;
        t[i+1]=t[i]*2LL+3LL;
    }
    
    ans = Calc(n,x);

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

Measured memory_bytes: 256
from collections import defaultdict
dd = defaultdict(int)
n,p=map(int, input().split())
S = list(input().rstrip())
tmp = 0
r=1
su=0
dd[0]=1
if p==2 or p==5:
    c=n
    for s in S[::-1]:
        if int(s)%p==0:
            su+=c
        c-=1
    print(su)
else:
    for s in S[::-1]:
        tmp+=int(s)*r
        tmp%=p
        dd[tmp]+=1
        r*=10
        r%=p
    for i in dd.values():
        su += (i*(i-1))//2
    print(su)


Measured memory_bytes: 7328
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF (1e9)

int main() {
  map<int, int> counter;
  int n, a;
  cin >> n;

  for(int i = 2; i <= n; i++) {
    cin >> a;
    counter[a]++;
  }

  cout << counter[1];
  for(int i = 2; i <= n; i++) {
    if(counter.find(i) != counter.end()) {
      cout << " " << counter[i];
    } else {
      cout << " " << 0;
    }
  }
  cout << endl;

  return 0;
}

Measured memory_bytes: 12976
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>

using namespace std;

int main()
{
	int n,m,s,g1,g2;
	while(true)
	{
		cin >> n >> m >> s >> g1 >> g2;
		if(n==0)break;
		vector<vector<long long> > dist(n,vector<long long>(n,100000000));
		for(int i=0;i<n;i++)
			dist[i][i]=0;
		for(int i=0;i<m;i++)
		{
			int b1,b2,c;
			cin >> b1 >> b2 >> c;
			b1--;
			b2--;

			dist[b1][b2]=c;
		}

		for(int k=0;k<n;k++)
			for(int i=0;i<n;i++)
				for(int j=0;j<n;j++)
					dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);

		int ans=100000000;
		for(int i=0;i<n;i++)
		{
			int tmp=dist[s-1][i]+dist[i][g1-1]+dist[i][g2-1];
			ans=min(ans,tmp);
		}

		cout << ans << endl;
	}



}


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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pll> vpl;
typedef vector<vll> vvll;

#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define yes cout<<"Yes"<<endl
#define YES cout<<"YES"<<endl
#define no cout<<"No"<<endl
#define NO cout<<"NO"<<endl
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

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

  ll a,b,c,d;
  cin>>a>>b>>c>>d;

  ll t=c/b;
  if(c%b!=0)
    t++;

  ll ao=a/d;
  if(a%d!=0)
    ao++;

  if(t<=ao)
    yes;

  else
    no;

}



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

using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define INF 1000000007
// cin.eof() 入力個数の問題
int main(){
ll a,b,c;
cin>>a>>b>>c;
ll count=0;
while(a%2==0&&b%2==0&&c%2==0){
ll A=a,B=b,C=c;
a=(B+C)/2;
b=(A+C)/2;
c=(A+B)/2;
count++;
//cout<<a<<b<<c<<endl;
if(count==100007){
    cout<<-1<<endl;
    return 0;
}
}


cout<<count<<endl;
  return 0;
}


Measured memory_bytes: 256
NK = input().split()
N = int(NK[0])
K = int(NK[1])

RSP = input().split()
R = int(RSP[0])
S = int(RSP[1])
P = int(RSP[2])
tab = {'r':R, 's':S, 'p':P}
T = input()

from collections import defaultdict
counter = defaultdict(int)

if len(T) <= K:
  pass
else:
  ts = [T[i::K] for i in range(K)]
  for tt in ts:
    duplicate = True
    prev = tt[0]
    for t in tt[1:]:
      if prev == t:
        if duplicate:
          counter[t] += 1
          duplicate = False
        else:
          duplicate = True
      else:
        duplicate = True
      prev = t
score = (T.count('r')-counter['r'])*P\
+(T.count('s')-counter['s'])*R\
+(T.count('p')-counter['p'])*S
print(score)

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

int main(void)
{
  char s[101];
  int i,n;

  scanf("%s",s);

  n=strlen(s);
  for(i=0;i<n;i++){
   if(i%2==0){
    if(s[i]=='L'){
     printf("No\n");
     return 0;
   }
  }
   else {
    if(s[i]=='R'){
     printf("No\n");
     return 0;
    } 
   }
  }

  printf("Yes\n");

  return 0;
}

     


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define pb          push_back
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define endl        "\n"
#define fast        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int         long long int
#define mod         1000000007
#define test        int t;cin>>t;while(t--)
#define REP(i,a,b)  for(int i=a,i<=b;i++)
#define MAXN        200001

int32_t main()
{
    vector<string> mp={"SUN","MON","TUE","WED","THU","FRI","SAT"};
    
    string str;cin>>str;
    int idx=0;
    for(int i=0;i<mp.size();i++){
        if(mp[i]==str){
            idx=i;
            break;
        }
    }

    cout<<7-idx<<endl;

    return 0;
}

Measured memory_bytes: 3580
/*
          , -- 、
        /;;;;;;', 　　　
        i二二二i
      , ' 　    ヽ ???
     i　ﾉﾉﾉﾉﾉﾍ .', 　　
     〉ﾘi' ﾟ ヮﾟﾉﾚく　 WAyon..........
  ○⊂}〈lﾄ--ｲl〉{つ● 　　
      ,ｒ/ー i-ヽヽ 　　　
     ｀｀i_ﾗi_ﾗ
*/



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

const int INF=(long long)1e12;
const int mod=(int)1e9+7;
#define all(a) (a).begin(),(a).end()
typedef vector<vector<int>> graph;
int sz=262144;complex<double> y[262160],A[262160],B[262160];
#define int long long

void dft(complex<double> *x,bool inv);
#define P pair<int,int>





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

    int n;cin >>n;
    int x,y;cin >>x>>y;
    vector<int> a(n+10);
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            int sho=min({abs(j-i),abs(x-i)+abs(y-j)+1,abs(y-i)+abs(x-j)+1});
            a[sho]++;
        }
    }
    for(int i=1;i<n;i++)cout <<a[i]<<endl;
}

void dft(complex<double> *x,bool inv){
    for(int i=sz>>1;i>=1;i>>=1){
        complex<double> zeta=polar(1.0,2.0*acos(-1)*i/sz*(inv?-1.0:1.0)),now=1;
        for(int j=0;2*j<sz;j+=i){//i飛ばし
            rep(k,i) {
                y[k+j]=x[2*j+k]+now*x[2*j+i+k];
                y[j+k+(sz/2)]=x[2*j+k]-now*x[2*j+i+k];//sz/2以上のやつ。原点対称を利用
            }
            now*=zeta;
        }
        rep(i,sz)x[i]=y[i];//探索の区間の幅を狭める前にこぴー
    }

    if(inv)rep(i,sz)x[i]/=sz;

}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //ai>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //ai>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define REV(x) (reverse(x.begin(),x.end())) //reverse
#define TO(x,t,f) ((x)?(t):(f))
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define FILV(x,a) fill(x.begin(),x.end(),a)
#define FILA(ar,N,a) fill(ar,ar+N,a)
#define NEXTP(x) next_permutation(x.begin(),x.end())
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define pb push_back
#define pri(aa) cout<<(aa)<<endl
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
const ll INF=1e18+7;
const ll MOD=1e9+7;


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N,M;
	cin >> N >> M;
	vector< pair< int ,pair<int,int> > > si(M);
	FOR(i,0,M){
		pair< int ,pair<int,int> > p;
		int pp,yy;
		cin >> pp >> yy;
		p.first = yy;
		p.second.first = pp;
		p.second.second = i;
		si[i]=p;
	}
	SORT(si);
	vector< int > zyu(N+1,1);
	vector<string> ans(M);
	FOR(i,0,M){
		string s1="",s2="";
		s1 = to_string(si[i].second.first);
		while(s1.size()!=6)s1='0'+s1;
		s2 = to_string(zyu[si[i].second.first]);
		while(s2.size()!=6)s2='0'+s2;
		zyu[si[i].second.first]++;
		ans[si[i].second.second] = s1+s2;
	}
	for(string x:ans){
		cout << x << endl;
	}
}


Measured memory_bytes: 10240
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
using namespace std;
constexpr int kMod = 1000000007;
typedef long long LL;

template<typename T>
istream& operator >> (istream& is, vector<T>& vs){
  for(T& v: vs) is >> v;
  return is;
}

int main() {
  int N;  cin >> N;
  map<int, int> pos;
  for (int i = 0; i < N; ++i) {
    int P; cin >> P;
    pos[P] = i;
  }

  multiset<LL> s;
  s.insert(-1), s.insert(-1);
  s.insert(N), s.insert(N);
  LL ans = 0;
  for (LL x = N; x > 0; --x) {
    LL i = pos[x];
    auto it = s.lower_bound(i);

    LL r1 = *it;
    ++it;
    LL r2 = *it;

    --it; --it;
    LL l2 = *it;
    --it;
    LL l1 = *it;

    ans += x * (l2 - l1) * (r1 - i);
    ans += x * (i  - l2) * (r2 - r1);

    s.insert(i);
  }
  cout << ans << endl;
  return 0;
}


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

struct Node{int parent,left,right;};
Node T[25];

void PreOrder(int root_id){
    if(root_id!=-1){
        cout <<" "<< root_id;
        PreOrder(T[root_id].left);
        PreOrder(T[root_id].right);
    }
}
void InOrder(int root_id){
    if(root_id!=-1){
        InOrder(T[root_id].left);
        cout << " " << root_id;
        InOrder(T[root_id].right);
    }
}

void PostOrder(int root_id){
    if(root_id!=-1){
        PostOrder(T[root_id].left);
        PostOrder(T[root_id].right);
        cout << " " << root_id;
    }
}

int main(){
    int n;
    cin >> n;
    for(int i=0;i<=n-1;i++)T[i].parent=-1;
    for(int i=0;i<=n-1;i++){
        int id, left, right;
        cin >> id >> left >> right;
        T[id].left =left;
        T[id].right=right;
        T[left].parent=id;
        T[right].parent=id;
    }
    int root;
    for(int i=0;i<=n-1;i++){
        if(T[i].parent==-1){
            root=i;
            break;
        }
    }
    cout << "Preorder"<< endl;
    PreOrder(root);
    cout << endl;
    cout << "Inorder"<< endl;
    InOrder(root);
    cout << endl;    
    cout << "Postorder"<< endl;
    PostOrder(root);
    cout << endl;
}


Measured memory_bytes: 3100
x, y = map(int, input().split())

if 2 * y < x:
	print(0)
elif y > 2 * x:
	print(0)
elif (x + y) % 3 != 0:
	print(0)
else:
	p = 10**9 + 7
	s = int((2 * x - y) / 3)
	t = int((2 * y - x) / 3)
	u = min(s, t)
	v = s + t
	
	inv = [0] * (u + 1)
	inv[0] = 0
	ans = 1
	for i in range(1, u + 1):
		inv[i] = pow(i, p - 2, p)
		ans = (ans * (v - i + 1) * inv[i]) % p
	
	print(ans)

Measured memory_bytes: 16196
#include<bits/stdc++.h>
#define ll long long int
#define ve vector<int>
#define vl vector<long long int>
#define vs vector<string>
#define vve vector<vector<int>>
#define all(a) a.begin(),a.end()
using namespace std;

int main(){
  int n;
  cin>>n;
  ve deta(n),color(12);
  for(int i=0;i<n;i++){
  	cin>>deta[i];
    deta[i]/=400;
    color[deta[i]]++;
  }
  int A=0,B=0;
  for(int i=0;i<8;i++){
    if(color[i]!=0) A++;
  }
  for(int i=8;i<13;i++){B+=color[i];}
  if(A==0){
  	A++;
    B--;
  }
  cout<<A<<' '<<A+B<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int a,i,ans=0;
    scanf("%d",&a);
    if(a%2==0){for(i=1;i<a/2;i++){ans+=i;}ans=ans*2+i;}
    if(a%2!=0){for(i=1;i<(a+1)/2;i++){ans+=i;}ans*=2;}
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
int main(void)
{
	int n;
	int a[1000];
	int i,j;
	int v;
	
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	
	for(i=1;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			printf("%d",a[j]);
			if(j!=n-1){
				printf(" ");
			}
			else
			{
				printf("\n");
			}
		}
		
		v=a[i];
		j=i-1;
		while(j>=0 && a[j]>v)
		{
			a[j+1]=a[j];
			j--;
			a[j+1]=v;
		}
	}
	for(j=0;j<n;j++)
	{
		printf("%d",a[j]);
		if(j!=n-1){
			printf(" ");
		}
		else
		{
			printf("\n");
		}
	}
	return 0;
}


Measured memory_bytes: 2068
#include <stdio.h>

int main(void) {
    int H, N, A, S, i;
    scanf("%d%d", &H, &N);
    S=0;
    for (i=0; i<N; i++) {
        scanf("%d", &A);
        S+=A;
    }
    if (S>=H) printf("Yes");
    else printf("No");
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <queue>
#include <vector>
#include <cmath>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <set>
#include <map>
#include <stack>

using namespace std;

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;}

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repl(i, n) for(LL i = 0; i < (LL)(n); i++)

int main(void){
  string s, t;
  cin >> s;
  cin >> t;

  rep(i, s.length()) {
    if (s[i] != t[i]) {
      cout << "No";
      return 0;
    }
  }
  cout << "Yes";
  return 0;
};

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> x(m);
    rep(i,m) cin >> x[i];

    if(n >= m) cout << 0 << endl;
    else{
        sort(x.begin(),x.end());
        vector<int> y(m-1);
        rep(i,m-1) y[i] = x[i+1]-x[i];

        sort(y.begin(),y.end());
        int64_t ans = 0;
        rep(i,m-n) ans += y[i];
        cout << ans << endl;
    }
}


Measured memory_bytes: 1024
n, m = map(int, input().split())
l= [[0, 0, 0] for _ in range(m)]

for i in range(m):
  p, y = map(int, input().split())
  l[i][0] = p
  l[i][1] = y
  l[i][2] = i

l.sort()  
#print(l)

c = l[0][0]
x = 0

new_l = [[0, 0] for _ in range(m)]

for j in range(m):
  if l[j][0] != c:
    x = 1
    c = l[j][0]
  else:
    x += 1
  new_l[j][0] = str(l[j][0]).zfill(6)+str(x).zfill(6)
  new_l[j][1] = l[j][2]

new_l.sort(key=lambda x: x[1])
for i in range(m):
  print(new_l[i][0])
               
  

Measured memory_bytes: 88736
#include <iostream>
#include <string>
#include <vector>
using ll=long long;
using namespace std;

ll mod=1e9+7;
const int maxS=2e6+5;
ll fact[maxS];
ll invfact[maxS];

long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

ll comb(ll a,ll b){
    ll res=fact[a]*invfact[b]%mod;
    res=res*invfact[a-b]%mod;
    return res;
}

ll g(ll r,ll c){
    return comb(r+c+2,r+1)-1;
}

int main(){
    ll r1,c1,r2,c2;
    cin>>r1>>c1>>r2>>c2;
    r1--;c1--;

    fact[0]=1;
    invfact[0]=1;
    for(int i=1;i<r2+c2+3;i++){
        fact[i]=fact[i-1]*i%mod;
        invfact[i]=invfact[i-1]*modinv(i,mod)%mod;
    }

    ll ans=g(r2,c2);
    ans+=mod;
    ans%=mod;
    ans-=g(r2,c1);
    ans+=mod;
    ans%=mod;
    ans-=g(r1,c2);
    ans+=mod;
    ans%=mod;
    ans+=g(r1,c1);
    ans+=mod;
    ans%=mod;

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

Measured memory_bytes: 34784
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

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

struct t_piece {
	int n, w, d;
	t_piece(int _n, int _w, int _d) {
		n = _n;
		w = _w;
		d = _d;
	}
};
bool operator<( const t_piece &l, const t_piece &r ) {
	if( l.n == r.n ) {
		return l.w*l.d < r.w*r.d;
	} else {
		return l.n < r.n;
	}
}

bool sortByS( const t_piece &l, const t_piece &r ) {
	return l.w*l.d < r.w*r.d;
}

int main() {
	int n, w, d;
	while(cin >> n >> w >> d, n||w||d) {
		vector<t_piece> ps;
		ps.push_back(t_piece(-1,0,0));
		ps.push_back(t_piece(0,w,d));
		rep(i, n) {
			int p, s;
			cin >> p >> s;
			if( s%(ps[p].w+ps[p].d) < ps[p].w ) {
				t_piece np(i+1, s%(ps[p].w+ps[p].d), ps[p].d);
				ps[p].n = i+1;
				ps[p].w -= np.w;
				ps.push_back(np);
			} else {
				t_piece np(i+1, ps[p].w, (s%(ps[p].w+ps[p].d))-ps[p].w);
				ps[p].n = i+1;
				ps[p].d -= np.d;
				ps.push_back(np);
			}
			sort( ps.begin(), ps.end() );
		}
		sort( ps.begin(), ps.end(), sortByS );
		if(n==0) {
			cout << w*d << endl;
		} else {
			cout << ps[1].w * ps[1].d;
			for(int i=2; i<ps.size(); i++) {
				cout << ' ' << ps[i].w * ps[i].d;
			}
			cout << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1204
package main

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

func main() {
	N, _ := ReadInt(), ReadInt()
	S := make([]string, N)
	for i := 0; i < N; i++ {
		S[i] = ReadString()
	}
	sort.Strings(S)
	for _, s := range S {
		fmt.Printf(s)
	}
	fmt.Println()
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }


Measured memory_bytes: 1848
#include<cstdio>
#include<algorithm>
const int N = 2e5 + 9, P = 1e9 + 7;
struct poi { int x, v; }p[N], d[N];
bool cmp (const poi &A, const poi &B) { return A.x < B.x; }
bool cmp2 (const poi &A, const poi &B) { return A.v < B.v || (A.v == B.v && A.x < B.x); }
int n, l[N], r[N], now, f[N], i, j;
void up (int &x, int y) { x += y; if (x >= P) x -= P; }
int main () {
	for (scanf ("%d", &n), i = 1; i <= n; ++i) scanf ("%d%d", &p[i].x, &p[i].v);
	for (std :: sort (p + 1, p + n + 1, cmp2), i = 1; i <= n; ++i) p[i].v = i;
	for (std :: sort (p + 1, p + n + 1, cmp), i = 1; i <= n; d[i++].v = now) now = (i == 1 || p[i].v > now) ? p[i].v : now;
	for (i = n; i; d[i--].x = now) now = (i == n || p[i].v < now) ? p[i].v : now;
	for (std :: sort (d + 1, d + n + 1, cmp2), f[0] = i = j = 1; i <= n; ++i) {
		for (; j <= n && d[j].v == i; ++j) {
			up (f[i], f[i]), up (f[i], f[i - 1]);
			if (d[j].x > 1) up (f[i], P - f[d[j].x - 2]);
		}
		if (i < n) up (f[i], f[i - 1]);
	}
	return printf ("%d\n", f[n]), 0;
}

Measured memory_bytes: 4352
#include <cstdio>
#include <tr1/unordered_set>
using namespace std;
int a[50000],b[50000],o[50000];
int main(){
	int H,W,q;
	while(scanf("%d%d%d",&H,&W,&q)&&H){
		int ans = 0;
		for(int i = 0 ; i < q ; i++)
			scanf("%d%d%d",&a[i],&b[i],&o[i]);
		tr1::unordered_set<int> g[2];
		for(int i = q-1 ; i >= 0 ; i--){
			if(a[i]==0){
				if(!g[a[i]].count(b[i]) && o[i]) ans += W - g[!a[i]].size();
				g[a[i]].insert(b[i]);
			}else{
				if(!g[1].count(b[i]) && o[i]) ans += H - g[0].size();
				g[1].insert(b[i]);
			}
		}
		printf("%d\n",ans);
	}
}

Measured memory_bytes: 0
#include<map>
#include<iostream>
using namespace std;
#define df 0

int main(){
  if(df) printf("*debug mode*\n");
  int n,k,q; cin >>n >>k >>q;
  map<int,int> mp;
  for(int i=0;i<q;i++){
    int a; cin >>a;
    mp[a]++;
  }
  for(int i=1;i<=n;i++){
    if(q-mp[i]<k) printf("Yes\n");
    else printf("No\n");
  }
}
/// confirm df==0 ///

Measured memory_bytes: 5376
#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/03/03  Problem: code-festival-2016-qual-b_c / Link: https://code-festival-2016-qualb.contest.atcoder.jp/tasks/codefestival_2016_qualB_c?lang=en  ----- */
/* ------問題------

xy平面上の0≦x≦W,0≦y≦Hをみたす領域にあるx,yともに整数である点すべてに、ひとつずつ家があります。
x座標が等しくy座標の差が1であるか、y座標が等しくx座標の差が1であるような2点の組のうち、両方の点に家が存在するような全てのものに対し、その2点の間には舗装されていない道路があります。
座標(i,j)と(i+1,j)にある家の間の道路を舗装するのにはjの値にかかわらずコストがpi、 座標(i,j)と(i,j+1)にある家の間の道路を舗装するのにはiの値にかかわらずコストがqjかかります。
高橋君は、このうちいくつかの道路を舗装し、舗装された道路のみを通って任意の2つの家の間を行き来できるようにしたいです。 かかるコストの総和の最小値を求めてください。

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



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

LL W, H;

LL ans = 0LL;

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

	cin >> W >> H;
	vector<PLL> a;
	FOR(i, 0, W) {
		int v; cin >> v;
		a.push_back(PLL(v, 0));
	}
	FOR(i, 0, H) {
		int v; cin >> v;
		a.push_back(PLL(v, 1));
	}

	SORT(a);
	H++, W++;

	FOR(i, 0, SZ(a)) {
		if (a[i].second == 0) {
			ans += H*a[i].first;
			W--;
		}
		else {
			ans += W*a[i].first;
			H--;
		}
	}

	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 6512
import java.util.*;

public class Main {
    public static void main(String []args) throws Exception {
    	Main o = new Main();
        o.run();
    }

	void run() throws Exception {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int m = Math.max(a, Math.max(b, c));
		System.out.println(a + b + c - m);
	}
}


Measured memory_bytes: 22868
#include <bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;
using ui64 = uint_fast64_t;
#define REP(i, n) for (i64 (i) = 0; (i) < (n); ++(i))
#define FOR(i, a, b) for (i64 (i) = (a); (i) < (b); ++(i))

signed main() {

    int N;
    cin >> N;

    vector<i64> A(N), C(N + 1, 0), D(N + 1, 0), F(N, 0);
    vector<i64> D_acc(N + 2, 0), kD_acc(N + 2, 0);
    
    REP(i, N) cin >> A[i];
    REP(i, N) C[A[i]]++;
    REP(i, N + 1) D[C[i]]++;
    REP(i, N + 1) D_acc[i + 1] = D_acc[i] + D[i];
    REP(i, N + 1) kD_acc[i + 1] = kD_acc[i] + i * D[i];
    FOR(i, 1, N + 1) F[i - 1] = (kD_acc[i + 1] + i * (D_acc[N + 1] - D_acc[i + 1])) / i;
    REP(i, N) F[i] = -F[i];
    FOR(k, 1, N + 1) {
        auto itr = upper_bound(F.begin(), F.end(), -k);
        cout << distance(F.begin(), itr) << endl;
    }

    return 0;
    REP(i, N + 1) cerr << C[i] << " \n"[i == N];
    REP(i, N + 1) cerr << D[i] << " \n"[i == N];
    REP(i, N + 2) cerr << D_acc[i] << " \n"[i == N + 1];
    REP(i, N + 2) cerr << kD_acc[i] << " \n"[i == N + 1];
    REP(i, N) cerr << F[i] << " \n"[i == N - 1];

}


Measured memory_bytes: 14976
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>
#include <queue>
#include <utility>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define LL long long
#define INF 1000000001
#define mod 1000000007
using namespace std;
int keta(int n,int k){return (n/int(pow(10,double(k-1)))) % 10;} //nの下からk桁目
ll gcd(ll n,ll m){
	if(n<m){ll a=m;m=n;n=a;}
	ll r=n%m;
	while(r!=0){
		n=m;
		m=r;
		r=n%m;
	}
	return m;
}
ll lcm(ll n,ll m){
	return n*m/gcd(n,m);
}

int main(){
	
	int n;
	cin>>n;
	int a=0;
	int x,y;
	rep(i,n){
		cin>>x>>y;
		a+=y-x+1;
	}
	cout<<a<<endl;

	
}




Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define dunk(n) cout << n << endl
#define all(v) v.begin(), v.end()
typedef long long ll;



int main() {
    ll n, k;
    cin >> n >> k;
    
    vector<int> vec(n);
    int x;
    rep(i,n){
        cin >> x;
        x--;
        vec.at(i) = x;
    }
    
    map<ll,int> mp;
    map<int,ll> flag;
    mp[0] = 0;
    flag[0] = 1;
    int now = 0;
    
    ll i = 2;
    while(i <= k+1){
        now = vec.at(now);
//        dunk(now << ":" << flag[now]);
        if(flag[now] != 0) break;
        else{
            mp[i] = now;
            flag[now] = i;
        }
        i++;
    }
    
    if(i == k+1) dunk(++now);
    else{
        ll interval = i - flag[now];
        ll rem = (k-flag[now]+1) % interval;
        
//        dunk(i);
//        dunk(interval);
//        dunk(rem);
        dunk(++mp[rem+flag[now]]);
    }
    
    return 0;
}



Measured memory_bytes: 24056