akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define pb emplace_back
#define N 100010
using namespace std;
int d[N],n,x,y,a[N],na;
vector<int> e[N];
void jb(int x,int y){e[x].pb(y);d[x]++;}
void get(int x,int fa){
	a[++na]=e[x].size();
	for (auto y:e[x])
		if (y!=fa&&e[y].size()>1)get(y,x);
}
bool ch(){
	for (int i=0;i<=na;i++){if (a[na-i]>a[i]) return 0;if (a[i]>a[na-i])return 1;}
	return 0;
}
int main(){
	cin>>n;
	for (int i=1;i<n;i++){cin>>x>>y;jb(x,y);jb(y,x);}
	for (int i=1;i<=n;i++)if (e[i].size()==1)d[e[i][0]]--;
	for (int i=1;i<=n;i++)if (d[i]>2){puts("-1");return 0;}
	if (n==2){puts("1 2");return 0;}
	for (int i=1;i<=n;i++)if (e[i].size()>1&&d[i]<2){get(i,0);break;}
	for (int i=1;i<=na;i++)a[i]-=2;
	na++;
	if (ch())reverse(a,a+na+1);
	for (int i=0,su=0;i<=na;i++){
		for (int j=su+1;j<=su+a[i];j++)cout<<j+1<<' ';
		su+=a[i]+1;cout<<su-a[i]<<' ';
	}
	return 0;
}

Measured memory_bytes: 11776
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using ld = long double;
#define ALL(x) x.begin(),x.end()
#define P pair<int,int>
#define mod 1000000007

class mint {
    long long x;
public:
    mint(long long x=0) : x((x%mod+mod)%mod) {}
    mint operator-() const {
      return mint(-x);
    }
    mint& operator+=(const mint& a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const  mint& a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint& a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res/=a;
    }

    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
};

mint choose(int n, int k) {
  mint res = 1;
  rep(i, k) {
    res = res * (n - k + i + 1) / (i + 1);
  }
  return res;
}

int main()
{
  int n, a, b;
  cin >> n >> a >> b;
  mint res = 2;
  res = res.pow(n);
  res = res - 1 - choose(n, a) - choose(n, b);

  cout << res << endl;

  return 0;
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define REPD(i,a,b) for (int i=(a);i<(b);i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef set<int> si;
typedef vector<si> vsi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pi;
typedef queue<int> qi;
typedef queue<pi> qpi;
typedef pair<ll, ll> pll;
typedef queue<pll> qpll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const int mod = 1000000007;
const int INF = 1001001001;
// 小数点　<< fixed << setprecision(0) <<
// sort降順　sort(ALL(),greater<int>());
// 円周率　M_PI
// 文字判定　isupper islower
// 文字変換　
// 順列　do {} while(next_permutation(ALL(X)));
// 最大値　LLONG_MAX
// a内でx以上　auto iter = lower_bound(ALL(a), x);
// a内でxより大きい　auto iter = upper_bound(ALL(a), x);
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
struct edge {
    int from; //出発点
    int to;   //到達点
    int cost; //移動コスト
};
typedef struct edge se;
typedef vector<edge> ve;
unsigned euclidean_gcd(unsigned a, unsigned b) {
  if(a < b) return euclidean_gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

int main() {
  int a,b;
  cin >> a >> b;
  cout << a * b << endl;
  return 0;
}


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

int main() {
    string s, t;
    cin >> s >> t;
    sort(s.begin(), s.end());
    sort(t.rbegin(), t.rend());
    if ( t>s ) {
        cout << "Yes" << '\n';
    } else {
        cout << "No" << '\n';
    }
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
//#include<unordered_map>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 100005;
#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define CLR(a) memset(a,0,sizeof a)
#define repf( i , a , b ) for ( int i = a ; i <= b ; ++ i )
template <class T>
void in(T& x) {
	static char ch; static bool neg;
	for (ch = neg = 0; ch < '0' || '9' < ch; neg |= ch == '-', ch = getchar());
	for (x = 0; '0' <= ch && ch <= '9'; (x *= 10) += ch - '0', ch = getchar());
	x = neg ? -x : x;
}



int main()
{
	//freopen("in.txt", "r", stdin);
	ll n;
	in(n);
	if (n >= 1 && n <= 9)cout << n;
	else if (n <= 99)cout << "9";
	else if (n <= 999)cout << n - 90;
	else  if (n <= 9999)cout << "909";
	else if (n <= 99999)cout << n - 9090;
	else   cout << (99999 - 9090);
	




	return 0;
}

Measured memory_bytes: 256
//
//  main.cpp
//  A
//
//  Created by Hashizo on 2020/04/04.
//  Copyright © 2020 Hashizo. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <regex>
#include <cmath>

using namespace std;
 
#undef LONG_MAX
#undef LONG_MIN
 
#define LONG_MAX    9223372036854775807
#define LONG_MIN    (-LONG_MAX  -1)
 
#define ll long long
 
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
 
#define SORT(c) sort((c).begin(), (c).end())
#define REVERSE(v) reverse((v).begin(), (v).end())

int main(int argc, const char * argv[]) {
	
	
	ll x,y,z;
	cin >> x >> y >> z;
	

	cout << z << ' ' << x << ' ' << y << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef long long ll;
struct edge { ll s, t, x; };
typedef pair<ll, ll> P;
typedef pair<ll,P> event;
const ll MAX = 510000;
const ll MOD = 1000000007;
#define INF (ll)1000000000000
//この設定だとn<10^7が限界。maxの０を一個増やせば100msかかるが一桁増やせる。
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(ll n, ll k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main() {
  COMinit();
  ll N,M,K;
  cin>>N>>M>>K;
  ll memo=COM(N*M-2ll,K-2ll);
  ll x=1ll;
  ll y=1ll;  
  x=N*(N-1ll)*(N+1ll);
  x/=6ll;
  x%=MOD;
  x*=M;
  x%=MOD;
  x*=M;
  x%=MOD;
  y=M*(M-1ll)*(M+1ll);
  y/=6ll;
  y%=MOD;
  y*=N;
  y%=MOD;
  y*=N;
  y%=MOD;
  ll ans=x+y;
  ans%=MOD;
  ans*=COM(N*M-2ll,K-2ll);
  ans%=MOD;
  cout<<ans;
}


Measured memory_bytes: 15556
import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;

public class Main {
    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        int N = sc.nextInt();
        int Q = sc.nextInt();
        String S = sc.next();
        int [] ans = new int [Q];
        int [] ref = new int [N];
        int sum = 0;
        for (int i = 0; i < N-1; i++) {
            if (S.charAt(i) == 'A' && S.charAt(i+1) == 'C') {
                sum++;
                ref[i+1] += sum;
            } else {
                ref[i+1] += sum;
            }
        }
        for (int i = 0; i < Q; i++) {
            int start = sc.nextInt() - 1;
            int fin = sc.nextInt() - 1;
            ans[i] = ref[fin] - ref[start];
        }
        for (int i = 0; i < Q; i++) {
            System.out.println(ans[i]);
        }
    }
}


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

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, K, Q;
    cin >> N >> K >> Q;
    vector<ll> nums(N);
    vector<pll> sortNums;
    for (int i = 0; i < N; i++)
    {
        ll A;
        cin >> A;
        nums.at(i) = A;
    }
    ll answer = 1e12;
    for (int i = 0; i < N; i++)
    {
        ll minValue = nums.at(i);
        vector<vector<ll>> dividedNums;
        dividedNums.push_back(vector<ll>());
        for (int j = 0; j < N; j++)
        {
            if (nums.at(j) < minValue)
            {
                dividedNums.push_back(vector<ll>());
            }
            else
            {
                dividedNums.back().push_back(nums.at(j));
            }
        }
        vector<ll> kouhoNums;
        for (auto dividedNum : dividedNums)
        {
            if (dividedNum.size() < K)
            {
                continue;
            }
            sort(dividedNum.begin(), dividedNum.end());
            for (int j = 0; j < min(Q, (ll)dividedNum.size() - K + 1); j++)
            {
                kouhoNums.push_back(dividedNum.at(j));
            }
        }
        if (kouhoNums.size() < Q)
        {
            continue;
        }
        sort(kouhoNums.begin(), kouhoNums.end());
        answer = min(answer, kouhoNums.at(Q - 1) - kouhoNums.at(0));
    }
    cout << answer << endl;
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>

#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = Y-1;(X) >= 0;--(X))
#define repa(X,A,Y) for (int (X) = A;(X) <= (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define mod(n, m) (((n)%(m)+(m))%m)
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
const int INFINT = 1 << 30;                          // 1.07x10^ 9
const ll INFLL = 1LL << 60;                          // 1.15x10^18
const double EPS = 1e-10;
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

const int MAX_N = 100000;   
int N;
int happiness[MAX_N][3];
int dp[MAX_N][3];

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

  cin >> N;
  rep(i, N) cin >> happiness[i][0] >> happiness[i][1] >> happiness[i][2];

  rep(i, 3) dp[0][i] = happiness[0][i];

  for (int i = 1; i < N; ++i) {
      dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + happiness[i][0];
      dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + happiness[i][1];
      dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + happiness[i][2];
  }

  int ans = 0;
  rep(i, 3) ans = max(ans, dp[N-1][i]);

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1005,M=1e9+7;
int n,A,B,C,D,fac[N],inv[N],dp[N][N];
int ksm(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=x*x%M)
		if (y&1)(ans*=x)%=M;
	return ans;	
}
signed main(){
	scanf("%lld%lld%lld%lld%lld",&n,&A,&B,&C,&D);
	dp[0][A-1]=1;
	fac[0]=inv[0]=1;
	for (int i=1;i<=n;i++)fac[i]=fac[i-1]*i%M,inv[i]=ksm(fac[i],M-2);
	for (int i=0;i<=n;i++)
		for (int j=A;j<=B;j++){
			dp[i][j]=dp[i][j-1];
			for (int k=C,p=ksm(inv[j],C);k<=D;k++,(p*=inv[j])%=M){
				if (i-j*k<0)break;
				(dp[i][j]+=dp[i-j*k][j-1]*p%M*inv[k])%=M;
			}
		}
	printf("%lld\n",dp[n][B]*fac[n]%M);
} 


Measured memory_bytes: 8064
#include <iostream>
using namespace std;
typedef long long ll;

int main()
{
    int n,w;
    cin >> n >> w;
    
    ll weight[n], value[n];
    
    for(int i=0; i<n; i++){
        cin >> weight[i] >> value[i];
    }
    
    ll dp[n+1][w+1];
    
    for(int i=0; i<=n; i++){
        for(int j=0; j<=w; j++){
            if(i==0 || j==0) dp[i][j] = 0;
            else if(weight[i-1]<=j) dp[i][j] = max(dp[i-1][j], value[i-1] + dp[i-1][j-weight[i-1]]);
            else dp[i][j] = dp[i-1][j];
        }
    }
    cout << dp[n][w];
}

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

typedef long long ll;

const int MN = 100010;

int N;
int A[MN];
char B[MN];
ll psum[MN];

ll calc(int l, int r) {
    return psum[r] - (l? psum[l - 1] : 0);
}

int main() {
    scanf("%d", &N);

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

    for(int i = 0; i < N; i++) {
        psum[i] = A[i];
        if(i) psum[i] += psum[i - 1];
    }

    ll ans = -1e18;
    ll sum = A[0];

    for(int i = 1; i < N; i++) {
        if(B[i] == '-') {
            ll tmp = A[i];
            int j;
            for(j = i + 1; j < N; j++) {
                if(B[j] == '-') break;
                tmp += A[j];
            }

            ans = max(ans, sum - tmp + calc(j, N - 1));
            sum -= A[i];
        }
        else sum += A[i];
    }
    ans = max(ans, sum);
    printf("%lld", ans);
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N;
    scanf("%d", &N);
    for(int n = 1; n <= 3500; n++){
        for(int h = 1; h <= 3500; h++){
            long long bot = 4ll * h * n - 1ll * h * N - 1ll * N * n;
            if(bot <= 0) continue;
            long long top = 1ll * N * h * n;
            if(top % bot != 0) continue;
            printf("%d %d %lld\n", n, h, (top / bot));
            return 0;
        }
    }
    assert(false);
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

using namespace std;

int main()
{
    int a, x = 0, y = 0;
    for(int i = 1; i <= 3; i++) {
        scanf( "%d", &a );
        if(a == 5) x++;
        else if(a == 7) y++;
    }
    if(x == 2 && y == 1){
        printf("YES");
    }
    else
        printf("NO");
    return 0;
}


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


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

typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;

int main() {
  string s;
  cin >> s;

  int ans;
  if (s == "SSS") {
    ans = 0;
  } else if (s == "RSS" || s == "RSR" || s == "SSR" || s == "SRS") {
    ans = 1;
  } else if (s == "RRR") {
    ans = 3;
  } else {
    ans = 2;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3624
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

LL gcd(LL a, LL b)
{
	if (a < b) std::swap(a, b);
	LL r = a % b;
	while (r != 0)
	{
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}

LL lcm(LL a, LL b)
{
	return a / gcd(a, b) * b;
}

int main()
{
	LL N, M;
	in >> N >> M;
	std::vector<LL>a(N);
	rep(i, N) in >> a[i];

	LL L = a[0];
	rep(i, N) L = lcm(L, a[i]);
	auto L_ = L;
	while (L > 0)
	{
		bool f1 = false, f2 = false;
		rep(i, N)
		{
			if ((L / a[i]) % 2 == 0) f2 = true;
			else f1 = true;
		}
		if (f1 && f2)
		{
			out << 0 << std::endl;
			return 0;
		}
		if (!f1 && f2) L /= 2;
		if (f1 && !f2)
		{
			L /= 2;
			if (L > M) out << 0 << std::endl;
			else out << (M - L) / L_ + 1 << std::endl;
			return 0;
		}
	}
	out << 0 << std::endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int,int>
#define PIL pair<int,LL>
#define PLI pair<LL,int>
#define PIII pair<int,PII>
#define PLL pair<LL,LL>
#define PLII pair<LL,PII>
#define VI vector<int>
#define VVI vector<VI>
#define VL vector<LL>
#define VVL vector<VL>
#define VPII vector<PII>
#define FF first
#define SS second
#define MP make_pair
#define PB push_back
#define all(x) x.begin(),x.end()
#define watch(x) cout<<(#x)<<" = "<<(x)<<'\n'
#define mset(a,v) memset(a,v,sizeof(a))
#define setp(x) cout<<fixed<<setprecision(x)
#define EPS 0.00000000001
#define PI acos(-1)
#define loop(i,b,n) for(int i=b;i<n;++i)
#define rev_loop(i,b,n) for(int i=b;i>=n;--i)
using namespace std;

const int MOD = 1e9 + 7;
const LL MX = 1000;
const LL INF = 1e9;

void print_a(VI v)
{
    if(v.size()) cout<<v[0];
    loop(i,1,v.size()) cout<<' '<<v[i];
    cout<<'\n';
}

VVI init_vvi(int n, int m, int val)
{
    return VVI(n,VI(m,val));
}

VVL init_vvl(int n, int m, LL val)
{
    return VVL(n,VL(m,val));
}

int main()
{
    //ofstream out("output.txt");
    //ifstream in("input.txt");
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int n;
    cin>>n;
    string s;
    int c[4] = {0};
    loop(i,0,n)
    {
        cin>>s;
        if(s == "AC") ++c[0];
        else if(s == "WA") ++c[1];
        else if(s == "TLE") ++c[2];
        else ++c[3];
    }

    cout<<"AC x "<<c[0]<<'\n';
    cout<<"WA x "<<c[1]<<'\n';
    cout<<"TLE x "<<c[2]<<'\n';
    cout<<"RE x "<<c[3]<<'\n';

    /*
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        int a[n];
        loop(i,0,n)
        {
            cin>>a[i];
        }
    }
    */

    /*
    int n;
    cin>>n;
    int a[n];
    loop(i,0,n)
    {
        cin>>a[i];
    }
    */

    /*
    cout<<ans<<'\n';

    if(f) cout<<"YES\n";
    else cout<<"NO\n";

    if(f) cout<<"Yes\n";
    else cout<<"No\n";
    */

    return 0;
}


Measured memory_bytes: 3652
import sys
import math
input = sys.stdin.readline
##
n, r = input().rstrip().split()
n, r = int(n), int(r)
while n + r > 0:
    yama = list(range(1, n + 1))[::-1]
    for _ in range(r):
        p, c = input().rstrip().split()
        p, c = int(p), int(c)
        top = yama[:p - 1]
        mid = yama[p - 1:p - 1 + c]
        yama[:c] = mid
        yama[c:p - 1 + c] = top
    print(yama[0])
    n, r = input().rstrip().split()
    n, r = int(n), int(r)



Measured memory_bytes: 5720
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include<cmath>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;

int main(){
    int A,B,C;
    cin >> A >> B >> C;
    
    int ans = max(0,C - A + B);
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <numeric>
#include <vector>
#include <array>
#include <map>

template <int MOD>
struct ModInt {
    using lint = long long;
    int val;

    // constructor
    ModInt(lint v = 0) : val(v % MOD) {
        if (val < 0) val += MOD;
    };

    // unary operator
    ModInt operator+() const { return ModInt(val); }
    ModInt operator-() const { return ModInt(MOD - val); }
    ModInt inv() const { return this->pow(MOD - 2); }

    // arithmetic
    ModInt operator+(const ModInt& x) const { return ModInt(*this) += x; }
    ModInt operator-(const ModInt& x) const { return ModInt(*this) -= x; }
    ModInt operator*(const ModInt& x) const { return ModInt(*this) *= x; }
    ModInt operator/(const ModInt& x) const { return ModInt(*this) /= x; }
    ModInt pow(lint n) const {
        auto x = ModInt(1);
        auto b = *this;
        while (n > 0) {
            if (n & 1) x *= b;
            n >>= 1;
            b *= b;
        }
        return x;
    }

    // compound assignment
    ModInt& operator+=(const ModInt& x) {
        if ((val += x.val) >= MOD) val -= MOD;
        return *this;
    }
    ModInt& operator-=(const ModInt& x) {
        if ((val -= x.val) < 0) val += MOD;
        return *this;
    }
    ModInt& operator*=(const ModInt& x) {
        val = lint(val) * x.val % MOD;
        return *this;
    }
    ModInt& operator/=(const ModInt& x) { return *this *= x.inv(); }

    // compare
    bool operator==(const ModInt& b) const { return val == b.val; }
    bool operator!=(const ModInt& b) const { return val != b.val; }

    // I/O
    friend std::istream& operator>>(std::istream& is, ModInt& x) noexcept { return is >> x.val; }
    friend std::ostream& operator<<(std::ostream& os, const ModInt& x) noexcept { return os << x.val; }
};

constexpr int MOD = 1e9 + 7;
using mint = ModInt<MOD>;

using lint = long long;

void solve() {
    int n;
    std::cin >> n;

    std::map<std::pair<lint, lint>, std::array<int, 2>> cnt;
    mint zero = 0;

    while (n--) {
        lint x, y;
        std::cin >> x >> y;

        if (x == 0 && y == 0) {
            zero += 1;
            continue;
        }

        if (x < 0 || (x == 0 && y < 0)) {
            x = -x, y = -y;
        }

        int side = 0;
        if (y <= 0) {
            side = 1;
            auto nx = -y;
            auto ny = x;
            x = nx, y = ny;
        }

        if (x == 0) {
            y /= y;
        } else if (y == 0) {
            x /= x;
        } else {
            auto g = std::gcd(x, y);
            x /= g, y /= g;
        }

        auto p = std::make_pair(x, y);
        if (!cnt.count(p)) cnt[p] = {0, 0};
        cnt[p][side] += 1;
    }

    mint ans = 1;
    for (const auto& p : cnt) {
        ans *= mint(2).pow(p.second[0]) + mint(2).pow(p.second[1]) - 1;
    }
    ans += zero;

    std::cout << ans - 1 << std::endl;
}

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

    solve();

    return 0;
}


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

#define int long long

const int inf = 1e18;

signed main(){
  int N;
  vector<pair<int,int>> in;
  vector<pair<int,int>> hoge;

  map<int,int> cona, conb;
  set<int> a, b;

  int ans = inf;

  cin>>N;

  in.resize(N);
  hoge.resize(N);

  for(int i = 0; i < N; i++){
    cin>>in[i].first>>in[i].second;

    hoge[i] = in[i];

    if(hoge[i].first < hoge[i].second) {
      swap(hoge[i].first, hoge[i].second);


    }
    a.insert(hoge[i].first);
    b.insert(hoge[i].second);

    cona[hoge[i].first]++;
    conb[hoge[i].second]++;

    hoge[i].second *= -1;
  }

  sort(hoge.begin(), hoge.end());


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

    hoge[i].second *= -1;

    //cout<<hoge[i].first<<" "<<hoge[i].second<<endl;
  }

  for(int i = 0; i <= N; i++){
    int bmin = *b.begin();
    int bmax = *(--b.end());
    int amin = *a.begin();
    int amax = *(--a.end());

    ans = min(ans, (bmax - bmin) * (amax - amin));

    //cout<<"i = "<<i<<" <> "<<endl;
    //cout<<"bmax = "<<bmax<<" bmin = "<<bmin<<endl;
    //cout<<"amax = "<<amax<<" amin = "<<amin<<endl;
    /*
    for(int y : a){
      cout<<y<<" ";
    }
    cout<<endl;

    for(int y : b){
      cout<<y<<" ";
    }
    cout<<endl;
    */

    if(i == N) break;

    cona[hoge[i].first]--;
    cona[hoge[i].second]++;


    conb[hoge[i].first]++;
    conb[hoge[i].second]--;

    a.insert(hoge[i].second);
    b.insert(hoge[i].first);

    if(cona[hoge[i].first] == 0){

      a.erase(hoge[i].first);
    }

    if(conb[hoge[i].second] == 0){

      b.erase(hoge[i].second);
    }



  }

  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 75264
#include<stdio.h>
int main(){
int i,n;
int no[30];
for(i=0;i<28;i++){
scanf("%d",&n);
no[n-1]=1;
}
for(i=0;i<30;i++){
if(no[i]==0) printf("%d\n",i+1);
}
return 0;
}

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

int main() {
    int N; cin >> N;
    vector<int> A(N);
    rep(i, 0, N) cin >> A[i];
    sort(A.begin(), A.end());
    using P = pair<int, int>;
    vector<P> ans;
    rep(i, 1, N - 1) {
        if(A[i] > 0) {
            ans.push_back({A[0], A[i]});
            A[0] -= A[i];
        } else {
            ans.push_back({A[N - 1], A[i]});
            A[N - 1] -= A[i];
        }
    }
    ans.push_back({A[N - 1], A[0]});
    cout << A[N - 1] - A[0] << '\n';
    for(auto &a : ans) cout << a.first << " " << a.second << '\n';
    return 0;
}


Measured memory_bytes: 3188
/*
author : seryu
title : AGC029A_"Irreversible operation"
*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define reps(i,n) for(int i = 1; i <= n; i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ERASE(x,val) x.erase(remove(all(x), val), x.end())
typedef long long ll;
typedef pair<int, int> P;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
ll MOD = 1000000007;
int INF = 1001001001;

void solve()
{
	string s;
	cin >> s;
	int n = sz(s);
	ll num_w = 0;
	vector<int> pw;
	rep(i, n)
	{
		if(s[i] == 'W')
		{
			num_w++;
			pw.push_back(i+1);
		}
	}
	ll ans = 0;
	if(num_w == 0 || num_w == n)
	{
		cout << 0 << endl;
		return;
	}
	else
	{
		rep(i, sz(pw))ans += pw[i];
		ans -= num_w*(num_w+1)/2;
	}
	cout << ans << endl;
	return;	
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}


Measured memory_bytes: 1680
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;

#define rep(i,a) for(int i=0; i<a; i++)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define loop3(i,j,k,a) for(int i=0; i<a; i++)for(int j=0; j<a; j++)if(i!=j)for(int k=0; k<a; k++)if(i!=k&&j!=k)
#define loop4(i,j,k,l,a) for(int i=0; i<a; i++)for(int j=0; j<a; j++)if(i!=j)for(int k=0; k<a; k++)if(i!=k&&j!=k)for(int l=0; l<a; l++)if(i!=l&&j!=l&&k!=l)
#define rep1(i,a) for(int i=1; i<=a; i++)

#define scnd1(a) scanf("%d", &a)
#define scnd2(a,b) scanf("%d%d", &a,&b)
#define scnd3(a,b,c) scanf("%d%d%d", &a,&b,&c)
#define scnd4(a,b,c,d) scanf("%d%d%d%d", &a,&b,&c,&d)

#define cin1(a) cin >> a;
#define cin2(a,b) cin >> a >> b;
#define cin3(a,b,c) cin >> a >> b >> c;
#define cin4(a,b,c,d) cin >> a >> b >> c >> d;
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define prtd1(a) printf("%d\n", a)
#define prtd2(a,b) printf("%d %d\n", a,b)
#define prtd3(a,b,c) printf("%d %d %d\n", a,b,c)
#define prtd4(a,b,c,d) printf("%d %d %d %d\n", a,b,c,d)

#define mem(a,n) memset( a, n, sizeof(a))
typedef long long ll;


int main() {
    int nums[3][3];
    
    rep(i, 3){
        rep(j, 3) {
            cin >> nums[i][j];
        }
    }
    bool f = true;
    
    if ( nums[0][0]-nums[0][1] != nums[1][0]-nums[1][1] || nums[0][0]-nums[0][1] != nums[2][0]-nums[2][1]) f = false;
    if ( nums[0][1]-nums[0][2] != nums[1][1]-nums[1][2] || nums[0][1]-nums[0][2] != nums[2][1]-nums[2][2]) f = false;
    
    if (f) {
        cout1("Yes");
    }else {
        cout1("No");
    }
}

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

using namespace std;


string str;

void input(){

}

int main(void) {
	int i = 0;
	while (cin >> str) {
		if (i != 0) {
			cout << " ";
		}
		i++;
		for (int i = 0; i < str.size(); i++) {
			if (str.substr(i, 5) == "apple") {
				cout << "peach";
				i += 4;
			}
			else {
				if (str.substr(i, 5) == "peach") {
					cout << "apple";
					i += 4;
				}
				else {
					cout << str[i];
				}
			}
		}
	}


	cout << endl;
	return 0;
}

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

#define INF 1000000000

using namespace std;


int main()
{
    int n;
    cin >> n;
    int x = (1/1.08)*n;
    int b = x+1;
    if(floor(x*1.08) == n)
    {
        cout << x << endl;
    }
    else if( floor(b*1.08) == n)
    {
        cout << b << endl;
    }
    else
    {
        cout << ":(" << endl;
    }
    
   return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define LiangJiaJun main
using namespace std;
double p[3004],f[3004][3004];
int n;
int w33ha(){
    for(int i=1;i<=n;i++)scanf("%lf",&p[i]);
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            f[i][j]=0;
    f[0][0]=1;
    for(int i=1;i<=n;i++)f[i][0]=f[i-1][0]*(1.0-p[i]);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            f[i][j]+=f[i-1][j-1]*p[i]+f[i-1][j]*(1.0-p[i]);
        }
    }
    double ans=0;
    for(int i=0;i<=n;i++)if(n-i>i)ans+=f[n][n-i];
    printf("%.10lf\n",ans);
    return 0;
}
int LiangJiaJun(){
    while(scanf("%d",&n)!=EOF)w33ha();
    return 0;
}


Measured memory_bytes: 70656
#include "bits/stdc++.h"
using namespace std;
int main() {
	long long N;
	cin >> N;
	vector<long long>A(N);
	for (long long i = 0; i < N; i++) {
		cin >> A.at(i);
	}
	sort(A.begin(), A.end());
	long long Num = A.at(0), Sum = 1;
	long long ans = 0;
	for (long long i = 1; i < N; i++) {
		if (A.at(i - 1) != A.at(i)) {
			if (Sum < Num) ans += Sum;
			else ans += Sum - Num;
			Num = A.at(i);
			Sum = 1;
		}
		else Sum++;
	}
	if (Sum != Num) {
		if (Sum < Num) ans += Sum;
		else ans += Sum - Num;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1024
x = sorted(list(map(int, input().split())))
ans = 0
if x[0]%2 == x[1]%2:
    ans += (x[1] - x[0])//2
    ans += (x[2] - x[1])
else:
    ans += 1
    ans += (x[1] - x[0] + 1)//2
    ans += (x[2] - x[1])
print(ans)


Measured memory_bytes: 3060
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
int i,l,r,mid,p,v,a[nmax],b[nmax],d[nmax],m,n,rs,nr,x,id;
ll tot;
/*bool ok(int id)
{
	ll tot=1LL*v*m;
	int i,nr=0,x;
	for(i=1;i<=n;i++)b[i]=a[i],d[i]=0;
	for(i=id;i>=1;i--)
	{
		if(tot>=m)tot-=m,b[i]+=m;
		else 
		{
			b[i]+=tot,tot=0;
			break;
		}
	}
	for(i=id+1;i<=n;i++)
	{
		x=b[id]-b[i];
		x=min(x,m);
		if(x<0)break;
		if(tot>=x)tot-=x,b[i]+=x,d[i]+=x;
		else
		{
			d[i]+=tot,b[i]+=tot,tot=0;
			break;
		}
	}
	for(i=n;i>=1;i--)
	{
		x=m-d[i];
		if(tot>=x)tot-=x,b[i]+=x;
		else 
		{
			b[i]+=tot,tot=0;
			break;
		}
	}
	for(i=id+1;i<=n;i++)
	{
		if(id==2)cout<<b[i]<<" ";
		if(b[i]>b[id])
		{
			nr++;
		}
		//if(id==2)cout<<i<<endl;
	}
	cout<<endl;
	if(nr<p)return 1;
	return 0;
}*/
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>m>>v>>p;
	for(i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+n+1);
	l=1,r=n;
	while(l<=r)
	{
		mid=(l+r)/2;
		//cout<<l<<" "<<r<<endl;
		tot=1LL*v*m;
		id=mid,nr=0;
		for(i=1;i<=n;i++)b[i]=a[i],d[i]=0;
		for(i=id;i>=1;i--)
		{
			if(tot>=m)tot-=m,b[i]+=m;
			else 
			{
				b[i]+=tot,tot=0;
				break;
			}
		}
		for(i=id+1;i<=n;i++)
		{
			x=b[id]-b[i];
			x=min(x,m);
			if(x<0)break;
			if(tot>=x)tot-=x,b[i]+=x,d[i]+=x;
			else
			{
				d[i]+=tot,b[i]+=tot,tot=0;
				break;
			}
		}
		for(i=n;i>=1;i--)
		{
			x=m-d[i];
			if(tot>=x)tot-=x,b[i]+=x;
			else 
			{
				b[i]+=tot,tot=0;
				break;
			}
		}
		for(i=id+1;i<=n;i++)
		{
			if(b[i]>b[id])nr++;
		}
		if(nr<p)rs=n-mid+1,r=mid-1;
		else l=mid+1;
	}
	cout<<rs<<endl;
	return 0;
}


Measured memory_bytes: 1408
if __name__ == '__main__':
    MOD = 10 ** 9 + 7
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    for i in range(60):
        flag1 = sum([1 for x in a if x & (1 << i)])
        flag0 = n - flag1
        ans += (1 << i) * (flag1 * flag0)
        ans %= MOD
    print(ans)


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

using namespace std;
int main(){
    int n,a,b,fist = 0,second = 0,three = 0;
    cin>>n>>a>>b;
    for(int i = 0; i < n;i++){
        int k;
        cin>>k;
        if(k <= a){
            fist++;
        }else if(a < k && k <= b){
            second++;
        }else if(k >= b + 1){
            three++;
        }
    }
    cout<<min(fist,min(second,three))<<endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
ans = ''
for i in range(1,100):
    if n <= 26**i:
        n -= 1
        for j in range(i): #下の位から桁を決める
            ans += chr(ord('a')+ n % 26) #演算子は足し算より掛け算系優先
            n //= 26
        break
    else:
        n -= 26**i
print(ans[::-1]) #[::-1]で反転できる

#ord()は文字の番号を示す
#chr()はその番号の文字を示す
#bin(),oct(),hex()はそれぞれ2,8,16進数に変換し、数字の前に0b,0o,0xがつく

Measured memory_bytes: 9052
#include<bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, c, k;
  cin >> a >> b >> c >> k;
  if(k <= a) cout << k << endl;
  else if(k <= a + b) cout << a << endl;
  else cout << a - (k - a - b) << endl;
  return 0;
}

Measured memory_bytes: 3684
#include<bits/stdc++.h>
using namespace std;
#define mx 1000000000000000000
#define ll long long int
//ll a[40001000];
//ll number[20],used[20];
int main()
{
    ll a,b;
    cin>> a >> b;
    if(a>=0 && a<=9 &&(b>=0 && b<=9))
        cout << a*b << endl;
    else
        cout << "-1" << endl;
    return 0;
}


Measured memory_bytes: 3600
n = int(input())
lis = list(map(int, input().split()))
flug = 0
for i in lis:
    if i % 2 == 0:
        if (i % 3 == 0) or (i % 5 == 0):
            pass
        else:
            flug = 1

if flug == 0:
    print("APPROVED")
else:
    print("DENIED")

Measured memory_bytes: 3060
import sys
n,k = map(int,input().split())
d = list(map(int,input().split()))
 
for i in range(100000):
    s = str(i)
    n2 = len(s)
    fl = 0
    for j in range(len(s)):
        for k in d:
            if s[j] == str(k):
                fl = 1
                
    if fl == 0:
        if i >= n:
            print(i)
            break

Measured memory_bytes: 41324
#include <iostream>

using namespace std;

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

    char a[H][W];
    bool del[H][W];

    for (int i=0; i<H; i++) {
        for (int j=0; j<W; j++) {
            cin >> a[i][j];
        }
    }


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

        bool f = false;
        for (int j=0; j<W; j++) {
            if(a[i][j] == '#') {
                f = true;
            }
        }

        for (int j=0; j<W; j++) {
            del[i][j] = f;
        }
    }


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

        bool f = false;
        for (int j=0; j<H; j++) {
            if(a[j][i] == '#') {
                f = true;
            }
        }

        for (int j=0; j<H; j++) {
            if(del[j][i]) {
                del[j][i] = f;
            }
        }
    }


    for (int i=0; i<H; i++) {
        bool ret = false;
        for (int j=0; j<W; j++) {
            if(del[i][j]) {
                cout << a[i][j];
                ret = true;
            }
        }
        if (ret) {
            cout << "\n";
        }
    }
  
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  int a,b,c,d,e,f=-101,g=1000;
  cin>>a>>b>>c>>d;
  for(int i=0;i<a;i++){
    cin>>e;
    f=max(e,f);
  }
  for(int i=0;i<b;i++){
    cin>>e;
    g=min(e,g);
  }
  if(f<g){
  if(c<=f&&g<d)
      cout<<"No War"<<endl;
    else
      cout<<"War"<<endl;
  }else
    cout<<"War"<<endl;
}


Measured memory_bytes: 256
(n,m),*d = [list(map(int, s.split())) for s in open(0)]

d.sort()
l = [0] * n
for i in range(m):
    d[i] = [d[i][0]-1, d[i][1]-1]
    l[d[i][0]] += 1

p = [0] * n
p[0] = 1
for x in d:
    p[x[1]] += p[x[0]]/l[x[0]]

e = [0] * n
index = d[-1][0]
max_in_index = 0
max_reduce_e = 0

for x in d[::-1] + [[-1, -1]]:
    if index != x[0]:
        if l[index] > 1:
            max_reduce_e = max(max_reduce_e, 
                               p[index] * (e[index]/l[index] - (e[index] - max_in_index)/(l[index] - 1)))
        e[index] /= l[index]
        index = x[0]
        max_in_index = 0
    max_in_index = max(max_in_index, e[x[1]] + 1)
    e[x[0]] += e[x[1]] + 1

print(e[0] - max_reduce_e)

Measured memory_bytes: 44836
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ALL(x) x.begin(), x.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
random_device rnd;
mt19937 mt(rnd());
using ll = long long;
using lld = long double;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using PII = pair<int, int>;
const int IINF = 1 << 30;
const ll INF = 1ll << 60;
const ll MOD = 1000000007;

int main()
{
    int n;
    cin >> n;
    map<int, bool> mp;
    rep(i, n)
    {
        int t;
        cin >> t;
        mp[t] = !mp[t];
    }
    int ans = 0;
    for (auto x : mp)
    {
        if (x.second)
            ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4992
short t[3600];w,h,c,z;f(x,i){for(t[x]=0;i;t[z=x+"<>xyz\1\2"[--i]-61]&1&&f(z,8));}main(i){for(;scanf("%d%d",&w,&h)*h;printf("%d\n",c)){for(i=h;c=i;)scanf(" %[^\n]",i--*60+1+t);for(;h;--h)for(i=w;i;)t[z=h*60+i--]&1&&++c-f(z,8);}}

Measured memory_bytes: 0
from functools import reduce
n, k = map(int, input().split())

heights = []
for _ in range(n):
	heights.append(int(input()))

heights.sort()

diff = [0]*n

for i in range(k-1,len(heights)):
	diff[i] = heights[i]-heights[i-k+1]
	
print(reduce(min, diff[k-1:], 1000000002))

Measured memory_bytes: 12300
#include <iostream>

using namespace std;

int main(){
  int N; cin >> N;
  for(int i=0;i<N;++i){
	int a, b, c; cin >> a >> b >> c;
	cout << ((a*a+b*b==c*c || b*b+c*c==a*a || a*a+c*c==b*b)? "YES": "NO") << endl;
  }
}

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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

int x[4], y[4];

int main() {
	inc(i, 2) { cin >> x[i] >> y[i]; }
	
	int dx = x[1] - x[0];
	int dy = y[1] - y[0];
	
	x[2] = x[1] - dy;
	y[2] = y[1] + dx;
	x[3] = x[2] - dx;
	y[3] = y[2] - dy; 
	
	printf("%d %d %d %d\n", x[2], y[2], x[3], y[3]);
	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;

int main() {
    int64 x;
    cin >> x;
    int64 m = 100;
    int ans = 0;
    while(m < x) {
        m = m * (long double)1.01;
        ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3224
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solve(int N, int A, int B){
    vector<int> res(N), used(N+1, 0);
    for(int dec=1;;dec++){
        int start = max(1, N-dec*A+1);
        for(int i=0;i<A;i++){
            int idx = (dec-1)*A+i;
            if(idx >= N) return vector<int>();
            if(dec > 1 && dec-1+N-idx == B){
                int v = N;
                for(int j=idx;j<N;j++){
                    while(used[v]) --v;
                    res[j] = v--;
                }
                return res;
            }
            res[idx] = start + i;
            used[start+i] = 1;
        }
        if(A == N && B == 1) return res;
    }
    return vector<int>();
}

int main(){
    int N, A, B;
    while(cin >> N >> A >> B){
        auto v = solve(N, A, B);
        if(v.empty()){
            cout << -1 << endl;
        } else {
            cout << v[0];
            for(int i=1;i<v.size();i++) cout << " " << v[i];
            cout << endl;
        }
    }
}

Measured memory_bytes: 3336
#include <stdio.h>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <math.h>
#include <queue>
#include <string.h>
#include <stdlib.h>

using namespace std;
typedef unsigned long long ull;
typedef  long long ll;

int lcs(string x, string y) {
	//puts("c");
	vector<vector<int>> c;
	c.resize(1001);
	for (int i = 0; i < c.size(); i++) {
		c[i].resize(1001);
	}
	//puts("b");
	x = ' ' + x;
	y = ' ' + y;
	//puts("a");
	for (int i = 0; i < x.size(); i++) {
		c[i][0] = 0;
	}
	for (int i = 0; i < y.size(); i++) {
		c[0][i] = 0;
	}
	for (int i = 1; i < x.size(); i++) {
		for (int j = 1; j < y.size(); j++) {
			if (x[i] == y[j]) {
				c[i][j] = c[i - 1][j - 1] + 1;
			}
			else {
				c[i][j] = max(c[i - 1][j], c[i][j - 1]);
			}
		}
	}
	return c[x.size() - 1][y.size() - 1];
	
}

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		string a,b;
		cin >> a;
		cin >> b;
		cout << lcs(a,b) << endl;
	}
	return 0;

}


Measured memory_bytes: 7160
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,d[100005],e[100005];
	cin>>a>>b>>c;
	int a1=0,b1=0;
	for(int i=1;i<=a;i++)
	{
		cin>>d[i];
		if(i==1){
			a1=d[i];
		}
		else
		{
			if(a1>d[i])
			a1=d[i];
		}
	}
	for(int i=1;i<=b;i++)
	{
		cin>>e[i];
		if(i==1){
			b1=e[i];
		}
		else
		{
			if(b1>e[i])
			b1=e[i];
		}
	}
	int mi=a1+b1;
	for(int i=0;i<c;i++)
	{
		int h1,h2,h3;
		cin>>h1>>h2>>h3;
		if(d[h1]+e[h2]-h3<mi)
		mi=d[h1]+e[h2]-h3;
	}
	cout<<mi;
}

Measured memory_bytes: 1024
def all_part_string(s):
    r = range(len(s))
    return [s[i:j+1] for i in r for j in r if s[i:j+1] != '']

def contains_only(s, l):
    return False if [a for a in [e for e in s if e not in l] if a != ''] else True

if __name__ == '__main__':
    s = input()
    ss = all_part_string(s)
    o = [e for e in ss if contains_only(e, "ACGT")]
    print(0 if len(sorted(o, key=len, reverse=True)) == 0 else len(sorted(o, key=len, reverse=True)[0]))


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int G[10][10];
int n,m;
int used[10];

bool check(){
  for(int i=0;i<n;i++) if(used[i] == 0) return 0;
  return 1;
}

int dfs(int pos){
  if(check()) return 1;
  
  int res=0;
  for(int i=0;i<n;i++){
    if(G[pos][i] == 0|| used[i]) continue;
    used[i] = 1;
    res+=dfs(i);    
    used[i] = 0;
  }
  return res;
}

int main(){

  cin>>n>>m;					
  for(int i=0,a,b;i<m;i++){
    cin>>a>>b;a--,b--;
    G[a][b] = G[b][a] = 1;
  }
  used[0] = 1;
  cout <<dfs(0)<<endl;

  return 0;
}


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

using namespace std;

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

    for (int i=0; i<=n; i++) {
        for (int j=0; j<=m; j++) {
            int area = (n - i) * j + (m - j) * i;
            if (area == k) return cout << "Yes" << endl, 0;
        }
    }
    cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define sync ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ll long long int
#define mod 100000007
using namespace std;


int main()
{
    
    // freopen("C:\\Users\\Akarshan\\Desktop\\cp-temp\\running_on_fumes_chapter_1_input.txt","r",stdin);
    // freopen("C:\\Users\\Akarshan\\Desktop\\cp-temp\\output.txt","w",stdout);
   ll n,d;
   cin>>n>>d;
    ll ctr=0;
   for(int i=1;i<=n;i++)
   {
       ll x,y;
       cin>>x>>y;
       if((x*x+y*y)<=(d*d))
        ctr++;
   }
   cout<<ctr<<endl;
}

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

int main() {
  ll H,W;
  cin>>H>>W;
  vector<vector<ll>> a(H,vector<ll>(W));
  vector<vector<ll>> b(H,vector<ll>(W));
  vector<vector<ll>> c(H,vector<ll>(W));
  rep(i,H)rep(j,W) cin>>a[i][j];
  rep(i,H)rep(j,W) cin>>b[i][j];
  rep(i,H)rep(j,W) c[i][j]=b[i][j]-a[i][j];
  vector<vector<vector<bool>>> dp(H,vector<vector<bool>>(W,vector<bool>(82*(H+W),false)));
  dp[0][0][abs(c[0][0])]=true;
  
  rep(i,H)rep(j,W)rep(k,82*(H+W)){
    if (i<H-1 && dp[i][j][k]){
      dp[i+1][j][k+abs(c[i+1][j])]=true;
      dp[i+1][j][abs(k-abs(c[i+1][j]))]=true;
    }
    if (j<W-1 && dp[i][j][k]){
      dp[i][j+1][k+abs(c[i][j+1])]=true;
      dp[i][j+1][abs(k-abs(c[i][j+1]))]=true;
    }
  }
  
  ll ans=INF;
  rep(i,82*(H+W)){
    if (dp[H-1][W-1][i]) ans=i<ans ? i : ans;
  }
  cout<<ans<<endl;
  
  return 0;
}


Measured memory_bytes: 11136
function Main(input) {
	input = input.split("\n");
	tmp = input[0].split(" ");
	var a = parseInt(tmp[0], 10);
	var b = parseInt(tmp[1], 10);
	var c = parseInt(tmp[2], 10);
	var answer = 0;
	if(c > a-b){
      answer = c-(a-b);
    }else{
      answer = 0;
    }
	console.log(answer);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 9420
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <utility>
using namespace std;

typedef pair<int,int> pii; // expectation,distance

int main(void){
	int N,M;
	int a,b;
	std::priority_queue<pii,vector<pii>,less<pii> > root;
	while(cin>>N>>M,N||M){
		for(int i=0;i<N;i++){
			cin>>a>>b;
			root.push(std::make_pair(b,a));
		}
		while(!root.empty()&&M>0){
			pii a=root.top();root.pop();
			if(M>=a.second){
				M-=a.second;
			}else{
				a.second-=M;
				root.push(a);
				M=0;
			}
		}
		int k=0;
		while(!root.empty()){
			pii a=root.top();root.pop();
			k+=a.first*a.second;
		}
		cout<<k<<endl;
	}
	return 0;
}

Measured memory_bytes: 3196
N,x,y = gets.split.map(&:to_i)
ary = []

x -=1
y -=1
ans = Array.new(N,0)
0.upto(N-1) do |n|
  n.upto(N-1) do |g|
    d1 = g-n
    d2 = (x-n).abs + 1 + (y-g).abs
    dis = [d1,d2].min
    ans[dis] += 1
  end
end
1.upto(N-1) do |n|
  puts ans[n]
end



Measured memory_bytes: 1916