akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define all(a) begin(a),end(a)
#define FOR(x,val,to) for(int x=(val);x<int((to));++x)
#define FORE(x,val,to) for(auto x=(val);x<=(to);++x)
#define FORR(x,arr) for(auto &x: arr)
#define FORS(x,plus,arr) for(auto x = begin(arr)+(plus); x != end(arr); ++x)
#define FORREV(x,plus,arr) for(auto x = (arr).rbegin()+(plus); x !=(arr).rend(); ++x)
#define REE(s_) {cout<<s_<<'\n';exit(0);}
#define GET(arr) for(auto &i: (arr)) sc(i)
#define whatis(x) cerr << #x << " is " << (x) << endl;
#define e1 first
#define e2 second
#define INF 0x7f7f7f7f
typedef std::pair<int,int> pi;
typedef std::vector<int> vi;
typedef std::vector<std::string> vs;
typedef int64_t ll;
typedef uint64_t ull;
#define umap unordered_map
#define uset unordered_set
using namespace std;
using namespace __gnu_pbds;

#ifdef _WIN32
#define getchar_unlocked() _getchar_nolock()
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
template<class L, class R> ostream& operator<<(ostream &os, map<L, R> P) { for(auto const &vv: P)os<<"("<<vv.first<<","<<vv.second<<")"; return os; }
template<class T> ostream& operator<<(ostream &os, set<T> V) { os<<"[";for(auto const &vv:V)os<<vv<<","; os<<"]"; return os; }
template<class T> ostream& operator<<(ostream &os, vector<T> V) { os<<"[";for(auto const &vv:V)os<<vv<<","; os<<"]"; return os; }
template<class L, class R> ostream& operator<<(ostream &os, pair<L, R> P) { os<<"("<<P.first<<","<<P.second<<")"; return os; }
inline int fstoi(const string &str){auto it=str.begin();bool neg=0;int num=0;if(*it=='-')neg=1;else num=*it-'0';++it;while(it<str.end()) num=num*10+(*it++-'0');if(neg)num*=-1;return num;}
inline void getch(char &x){while(x = getchar_unlocked(), x < 33){;}}
inline void getstr(string &str){str.clear(); char cur;while(cur=getchar_unlocked(),cur<33){;}while(cur>32){str+=cur;cur=getchar_unlocked();}}
template<typename T> inline bool sc(T &num){ bool neg=0; int c; num=0; while(c=getchar_unlocked(),c<33){if(c == EOF) return false;} if(c=='-'){ neg=1; c=getchar_unlocked(); } for(;c>47;c=getchar_unlocked()) num=num*10+c-48; if(neg) num*=-1; return true;}template<typename T, typename ...Args> inline void sc(T &num, Args &...args){ bool neg=0; int c; num=0; while(c=getchar_unlocked(),c<33){;} if(c=='-'){ neg=1; c=getchar_unlocked(); } for(;c>47;c=getchar_unlocked()) num=num*10+c-48; if(neg) num*=-1; sc(args...); }
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; //s.find_by_order(), s.order_of_key() <- works like lower_bound
template<typename T> using ordered_map = tree<T, int, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define N 1000001

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;
    sc(n);
    int a[n];
    GET(a);
    sort(a,a+n);
    cout << a[n-1] << ' ';
    int bs = -1;
    int cr = -1;
    FOR(i,0,n-1){
        int cc = min(abs(a[i]-1),abs(a[i]-a[n-1]));
        if(cc > bs){
            cr = a[i];
            bs = cc;
        }
    }
    cout << cr << '\n';
}



Measured memory_bytes: 640
// Maximum Difference
#include <iostream>
#include <algorithm>
using namespace std;

#define N 100

int main() {
    int n;
    int A[N];
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> A[i];
    int mi = A[0];
    int ma = A[0];
    for (int i = 0; i < n; ++i) {
        mi = min(mi, A[i]);
        ma = max(ma, A[i]);
    }
    cout << abs(ma-mi) << endl;
}

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

int main(){
    int x, y;
    cin >> x >> y;

    int group[13] = {-1,0,1,0,2,0,2,0,0,2,0,2,0};

    if(group[x]==group[y])  cout << "Yes" << endl;
    else                    cout << "No" << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main() {
	int A, B, C, D;
	cin >> A >> B >> C >> D;
	if (A + B > C + D) {
		cout << "Left";
	}

	else if(A + B == C + D) {
		cout << "Balanced";
	}
	else {
		cout << "Right";
	}
}

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

using namespace std;

#define int long long
#define endl "\n"

const long long INF = (long long)1e18;
const long long MOD = 1'000'000'007; 

string yn(bool f){return f?"Yes":"No";}
string YN(bool f){return f?"YES":"NO";}



signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int N;
	vector<int> C, S, F;
	
	cin>>N;
	
	C.resize(N);
	S.resize(N);
	F.resize(N);
	
	for(int i = 0; i < N-1; i++){
		cin>>C[i]>>S[i]>>F[i];
	}
	
	for(int i = 0; i < N; i++){
		int time = 0;
		
		for(int j = i; j < N-1; j++){
			if(time <= S[j]) time = S[j] + C[j];
			else {
				time = (time+F[j]-1)/F[j] * F[j] + C[j];
			}
		}
		
		cout<<time<<endl;
	}
	
	
	return 0;
}

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

int main() {
  double PI = acos(-1);
  double a, b, x;
  cin >> a >> b >> x;
  x /= a;
  double rad;
  if (a * b / 2 < x) {
    x = a * b - x;
    double h = x * 2 / a;
    rad = atan(h / a);
  } else {
    double w = x * 2 / b;
    rad = atan(b / w);
  }
  printf("%.6f\n", rad * 180 / PI);
  return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define vl vector<long long int>
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vb vector<bool>
#define vvl vector<vector<ll> >
#define vvi vector<vector<int> >
#define pl pair<ll,ll>
#define pb push_back
#define PI 3.14159265
#define mod 998244353
#define pb push_back
#define mp make_pair
#define fri(s,n) for(int i=s;i<n;i++)
#define frj(s,n) for(int j=s;j<n;j++)
#define T(i) int i=1;cin>>i;while(i--)
#define vsi vector<set<int> >
#define pii pair<int,int>
#define inf 1e9
#define vpii vector<pair<int,int> >


ll power(ll a,ll b){
    if(b==0)
        return 1;
    if(b&1)
        return a*power(a,b-1);
    ll temp=power(a,b/2);
    return temp*temp;
    }
ll mycompare(ll a,ll b){
    return a>b;
    }

ll mincost(int level,vi &height,vi &dp){
    if(level==0)
        return 0;
    if(level==1)
        return abs(height[0]-height[1]);
    if(dp[level]!=-1)
        return dp[level];
    return dp[level]=min(abs(height[level]-height[level-1])+mincost(level-1,height,dp),abs(height[level]-height[level-2])+mincost(level-2,height,dp));
    }
int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    fast;
        int n;
        cin>>n;
        vi height(n);
        fri(0,n)
            cin>>height[i];
        vi dp(n,-1);
        cout<<mincost(n-1,height,dp);
    }


Measured memory_bytes: 7164
#include <bits/stdc++.h>
const int N=100005;
char s[N],t[N];
int a[N],b[N],Q,n,m,l1,r1,l2,r2;
int main(){
	scanf("%s",s+1);
	scanf("%s",t+1);
	n=strlen(s+1),m=strlen(t+1);
	for (int i=1;i<=n;i++) a[i]=a[i-1]+1+(s[i]=='A');
	for (int i=1;i<=m;i++) b[i]=b[i-1]+1+(t[i]=='A');
	scanf("%d",&Q);
	while (Q--){
		scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
		if ((a[r1]-a[l1-1])%3==(b[r2]-b[l2-1])%3) 
			puts("YES");
		else puts("NO");
	}
	return 0;
}

Measured memory_bytes: 1536
N,H=map(int,input().split())
a=0
b=[]
for _ in range(N):
    A,B=map(int,input().split())
    a=max(a,A)
    b.append(B)
b=sorted(b,reverse=True)
ans=0
for i in range(N):
    if b[i]<=a:
        break
    H-=b[i]
    ans+=1
    if H<=0:
        print(ans)
        exit()
print(ans-(-H//a))

Measured memory_bytes: 14172
#ifdef __LOCAL
  #define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
template<typename T> bool chmax(T &a,T b) {if(a<b) {a=b; return true;} return false;}
template<typename T> bool chmin(T &a,T b) {if(a>b) {a=b; return true;} return false;}
#define itn int
#define fi first
#define se second
#define intmax numeric_limits<int>::max()
#define llmax numeric_limits<ll>::max()
#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 rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(int)(n);i>=1;i--)
#define all(vec) vec.begin(),vec.end()
#define sortt(vec) sort((vec).begin(),(vec).end())
#define rsort(vec) sort((vec).rbegin(), (vec).rend())
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef tuple<ll,ll,ll> tlll;
typedef tuple<int,int,int> tiii;
const ll mod=1e9+7;
const int inf=1<<30;
const ll lnf=1ll<<60;

ll val[60][100010];
ll to[60][100010];

int main(){
  ll n,x,m;
  cin >> n >> x >> m;
  rep(j,m){
    val[0][j]=j;
    to[0][j]=(ll)j*j%m;
  }
  rep(i,60-1)rep(j,m){
    val[i+1][j]=val[i][j]+val[i][to[i][j]];
    to[i+1][j]=to[i][to[i][j]];
  }
  ll next=x,ans=0;
  for(int i=60-1;i>=0;i--){
    if((n>>i)&1){
      ans+=val[i][next];
      next=to[i][next];
    }
  }
  cout << ans << endl;
}

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

using namespace std;

using i64 = int64_t;

const i64 INF = 1e18 + 7;

signed main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(auto& x : a)
        cin >> x;
    vector<vector<i64>> dp(n, vector<i64>(4, INF));
    for(int i = 0; i < 4; ++i)
        dp[0][i] = i;
    for(int i = 0; i < n - 1; ++i){
        for(int j = 0; j < 4; ++j){
            int mi = max(0, a[i] - j);
            for(int k = mi; k < 4; ++k)
                dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + k * 2);
        }
    }
    i64 ans = INF;
    for(int i = 0; i < 4; ++i)
        ans = min(ans, dp.back()[i] + max(0, a.back() - i));
    cout << ans << endl;
}



Measured memory_bytes: 3304
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int K = sc.nextInt();
		sc.close();
		int turn = 1;
		for(int i = 0; i < K; i++) {
			if(turn == 1) {
				if(A % 2 == 1) {
					A--;
				}
				A /= 2;
				B += A;
			}else {
				if(B % 2 == 1) {
					B--;
				}
				B /= 2;
				A += B;
			}
			turn *= -1;
		}
		System.out.println(A +" " + B);
	}
}

Measured memory_bytes: 23124
//Apparat : drobucs, aleonov, vit_72
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <iomanip>
#include <algorithm>
#include <string>
#include <queue>
#include <numeric>

//#pragma warning(disable : 4996)
//#pragma GCC optimize("O3")

using namespace std;

#define nptr nullptr
#define all(x) (x).begin(), (x).end()
#define drobucs ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define ff first
#define ss second
#define pb push_back
#define sz(x) (int)(x).size()

typedef  long long ll;

const int maxn = (int)1e7 + 13;
const ll INFL = 9223372036854775807;
const ll INF = 2147483647;
const ll MOD = (int)1e9 + 7, MOD2 = 998244353;//1e9 + 21, 1e9 + 33, 1e9 + 87, 1e9 + 93
const ll base = 101, base2 = 37;
ll sieve[maxn];
int main() {
	drobucs;
	ll n;
	cin >> n;
	ll ans = 0;
	for (ll i = 1; i <= n; ++i) {
		for (ll j = i; j <= n; j += i) sieve[j]++;
		ans += i * sieve[i];
	}
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 81692
#include <iostream>
#include "stdio.h"

using namespace std;

int main() {
  int s;

  scanf("%d", &s);

  int h = s / (60*60);
  s %= (60*60);

  int m = s / 60;
  s %= 60;

  printf("%d:%d:%d\n", h,m,s);

  return 0;
}



Measured memory_bytes: 3216
#include <bits/stdc++.h>
using namespace std;
 
using ll=long long;
 
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
const ll MOD = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    int ans = 0, cnt2 = 0;
    unordered_map<int, int> mp; 
    rep(i, n) {
        int a; cin >> a;
        mp[a]++;
    }
    for (auto& p : mp) {
        int a = p.second; 
        if (a%2) {
            ans += a/2;
        } else {
            ++cnt2;
            ans += (a-1)/2;
        }
    } 
    ans += (cnt2+1) / 2;
    cout << n - 2*ans << endl;
    return 0;
}

Measured memory_bytes: 4388
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int h,w,k;
  cin>>h>>w>>k;
  vector<string> ss(h);
  for(Int i=0;i<h;i++) cin>>ss[i];

  vector< vector<Int> > ans(h);
  Int c=1;
  for(Int i=0;i<h;i++){
    if(ss[i]==string(w,'.')) continue;
    ans[i].assign(w,0);
    for(Int j=0;j<w;j++){
      ans[i][j]=c;
      if(ss[i][j]=='#') c++;
    }
    for(Int j=w-1;j>=0;j--){
      if(ss[i][j]=='#') break;
      ans[i][j]--;
    }
  }
  assert(c==k+1);

  for(Int i=1;i<h;i++)
    if(ans[i].empty()) ans[i]=ans[i-1];

  for(Int i=h-2;i>=0;i--)
    if(ans[i].empty()) ans[i]=ans[i+1];

  for(Int i=0;i<h;i++){
    for(Int j=0;j<w;j++){
      if(j) cout<<" ";
      cout<<ans[i][j];
    }
    cout<<endl;
  }
  return 0;
}


Measured memory_bytes: 1664
N, M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]

s = set()
indices = [0] * N
nums = dict(zip(range(1, M+1), [[] for i in range(M)]))
nn, mm = 0, 0
for i, idx in enumerate(indices):
  m = A[i][idx]
  nums[m].append(i)
  if len(nums[m]) > nn:
    nn = len(nums[m])
    mm = m

ans = nn
for _ in range(M-1):
  s.add(mm)
  for i in nums[mm]:
    idx = indices[i] + 1
    m = A[i][idx]
    while m in s:
      idx += 1
      m = A[i][idx]
    indices[i] = idx
    nums[m].append(i)
  nums.pop(mm)
  nn = 0
  for k in nums:
    if len(nums[k]) > nn:
      nn = len(nums[k])
      mm = k
  ans = min(ans, nn)

print(ans)

Measured memory_bytes: 4312
s = input()
n = len(s)
m = 2019
a = [0] * (n + 1)
b = [0] * (n + 1)
b[0] = 1
for i in range(1, n + 1):
    b[i] = b[i - 1] * 10 % m
c = [0] * m
c[0] += 1
ans = 0
for i in range(n - 1, -1, -1):
    w = (a[i + 1] + (ord(s[i]) - ord('0')) * b[n - 1 - i]) % m
    ans += c[w]
    c[w] += 1
    a[i] = w
print(ans)

Measured memory_bytes: 79920
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)

signed main(){
    int k,s;cin>>k>>s;
    int res=0;
    rep(i,k+1){
        rep(j,k+1){
            if(s-i-j>=0&&s-i-j<=k){
                res++;
            }
        }
    }
    cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
const int N=2200;


int b[N],n,k,num;
long long bb[N*N],dd[N][N],pp,ans,f[N][N],p=1000000007;
long long xxx;
long long do3(long long x){
	long long s=x,t=x;

	for(int i=2; i<=num; i++){
		s=s*s%p;
		if(b[i]==1) t=t*s%p;
		
	}
	
	return t%p;
}

void do1(int x,int y){
	int mm=k-2;
	int nn=n*k-x-(y-1)*(k-1)-1;
	
//	printf("ccc%d %d %d %d\n",x,y,nn,mm);
	
	long long ans=1,a=1,b=1;
	
	a=bb[nn];
	//b=do3(bb[mm])*do3(bb[nn-mm])%p;
	b=xxx*do3(bb[nn-mm])%p;
//	printf("ccc2  %d %I64d %I64d\n",nn, a,b);
	
	ans=b*a%p;
	
//	printf("ccc3  %I64d\n",ans);
	
	dd[x][y]=ans;
	
}

void do2(){
	long long a=f[n][n];
	
	for(int i=1; i<=n; i++){
		a=a*i%p;
	}
	
	f[n][n]=a;
}

void f1(int x,int y){ 

//	printf("11 %d %d\n",x,y);

	if(x==0){
		f[x][y]=1;
		return;
	}
	if(y==0){
		f[x][y]=1;
		return;
	}
//	printf("22 %d %d\n",x,y);
	
	if(f[x-1][y]==-1 and x-1>=y) f1(x-1,y);
	if(f[x][y-1]==-1 and x>=y-1) f1(x,y-1);
	
//	printf("%d %d %I64d %I64d \n",x, y, f[x-1][y],f[x][y-1]);
	
	f[x][y]=0;
	if(x-1>=y) f[x][y]=(f[x][y]+f[x-1][y])%p;
	
	if(dd[x][y]==-1) do1(x,y);
//	printf("aaa%d %d %I64d %I64d\n",x, y, f[x][y-1], dd[x][y]);
	f[x][y]+=f[x][y-1]*dd[x][y]%p;
	f[x][y]=f[x][y]%p;
//	printf("%d %d %I64d \n",x, y, f[x][y]);
	return;
}



int main(){
//	freopen("leftmost ball.in","r",stdin);
//	freopen("leftmost ball.out","w",stdout);

	scanf("%d%d",&n,&k);
	
	if(k==1){
		printf("1"); 
		return 0;
	}
	bb[0]=1;
	bb[1]=1;
	for(int i=2; i<=n*k; i++){
		bb[i]=bb[i-1]*i%p;
	}
	
	pp=1000000005;
	num=0;
	while(pp>0){
		b[++num]=pp%2;
		pp=pp/2;
	}
	
//	for(int i=num; i>=1; i--) printf("%d",b[i]); printf("\n");
	memset(dd,-1,sizeof(dd));
	memset(f,-1,sizeof(f));
	xxx=do3(bb[k-2]);
	f1(n,n);
	
//	for(int i=0; i<=n; i++){
//		for(int j=0; j<=n; j++){
//			printf("%I64d ",dd[i][j]);
//		}printf("\n");
//	}
	
	do2();
	
	f[n][n]=f[n][n]%p;

	printf("%I64d",f[n][n]);
	
	
	return 0;
}

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

const ll LINF = 1e18;
const int INF = 1e9;
const ll MOD = 1000000007;

int main(){

    int n, m;
    cin >> n >> m;
    vector<pair<ll,ll>> s(n), p(m);
    for(int i = 0; i < n; i++){
        ll a, b;
        cin >> a >> b;
        s[i] = make_pair(a,b);
    } 
    for(int i = 0; i < m; i++){
        ll c, d;
        cin >> c >> d;
        p[i] = make_pair(c,d);
    } 

    for(int i = 0; i < n; i++){
        ll d = LINF;
        int point = 0;
        for(int j = 0; j < m; j++){
            if(d > abs(s[i].first - p[j].first) + abs(s[i].second - p[j].second)){
                d = abs(s[i].first - p[j].first) + abs(s[i].second - p[j].second);
                point = j + 1;
            }
        }
        cout << point << endl;
    }
    return 0;
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
#define ls ch[x][0]
#define rs ch[x][1]
#define int ll
#define PII pair<int,int>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;

const int maxn=400010,mod=998244353,G=3;
int n,a[maxn],t[maxn],A[maxn],B[maxn];vector<int>f[maxn];
int x,len,R[maxn],invG,inv2;
int ksm(int x,int y){
    int ans=1;while(y){if(y&1)ans=1ll*ans*x%mod;x=1ll*x*x%mod;y>>=1;}return ans;
}
void NTT(int *A,int flag){
    for(int i=0;i<x;i++)if(i<R[i])swap(A[i],A[R[i]]);
    for(int mid=1;mid<x;mid<<=1){
        int g;if(flag)g=ksm(G,(mod-1)/(mid<<1));
        else g=ksm(invG,(mod-1)/(mid<<1));
        for(int j=0;j<x;j+=(mid<<1)){
            int sum=1;
            for(int k=0;k<mid;k++){
                int A1=A[j+k],A2=1ll*sum*A[j+k+mid]%mod;
                A[j+k]=(A1+A2)%mod;A[j+k+mid]=((A1-A2)%mod+mod)%mod;sum=1ll*sum*g%mod;
            }
        }
    }
    if(!flag){
        int X=ksm(x,mod-2);
        for(int i=0;i<x;i++)A[i]=1ll*A[i]*X%mod;
    }
}
void polymul(int *a,int *b,int n,int m){
    x=1;len=0;while(n+m>=x)x<<=1,len++;
    for(int i=0;i<x;i++)R[i]=(R[i>>1]>>1)|((i&1)<<len-1);
    NTT(a,1);NTT(b,1);for(int i=0;i<=x;i++)a[i]=1ll*a[i]*b[i]%mod;NTT(a,0);
}priority_queue<PII>que;
int fac[maxn],finv[maxn],inv[maxn];
void init(){
	fac[0]=fac[1]=finv[1]=finv[0]=inv[1]=1;
	for(int i=2;i<=200000;i++){
		fac[i]=1ll*fac[i-1]*i%mod;
		finv[i]=ksm(fac[i],mod-2);
	}
}
int C(int n,int m){
	return 1ll*fac[n]*finv[n-m]%mod*finv[m]%mod;	
}
signed main(){
	scanf("%d",&n);invG=ksm(G,mod-2);init();inv2=(mod+1)/2;
	for(int i=1;i<=2*n;i++)scanf("%d",&a[i]),t[a[i]]++;int id=0;
	for(int i=1;i<=100000;i++)
		if(t[i]){
			++id;
			for(int j=0;j<=t[i]/2;j++)
				if(j)f[id].pb(fac[t[i]]*finv[t[i]-2*j]%mod*finv[j]%mod*ksm(ksm(2,j),mod-2)%mod);
				else f[id].pb(1);
			que.push(mp(-t[i]/2,id));
		}
	while(que.size()!=1){
		PII nx=que.top();que.pop();
		PII ny=que.top();que.pop();
		int lenx=-nx.fi,leny=-ny.fi;
		for(int i=0;i<=lenx;i++)A[i]=f[nx.se][i];
		for(int i=0;i<=leny;i++)B[i]=f[ny.se][i];
		polymul(A,B,lenx,leny);f[nx.se].clear();
		for(int i=0;i<=lenx+leny;i++)f[nx.se].push_back(A[i]);
		for(int i=0;i<=x;i++)A[i]=B[i]=0;
		que.push(mp(-(lenx+leny),nx.se));
	}PII nx=que.top();int ans=0;
	for(int i=0;i<f[nx.se].size();i++){
		if(i&1)ans=(ans-1ll*f[nx.se][i]*fac[2*n-2*i]%mod*finv[n-i]%mod*ksm(ksm(2,n-i),mod-2)%mod+mod)%mod;
		else ans=(ans+1ll*f[nx.se][i]*fac[2*n-2*i]%mod*finv[n-i]%mod*ksm(ksm(2,n-i),mod-2)%mod)%mod;
	}cout<<ans;return 0;
}

Measured memory_bytes: 28232
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 110;
int n, a[MAXN<<1], ans;

inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	for(; !isdigit(ch); ch = getchar()) if(ch=='-') f=-1;
	for(; isdigit(ch); ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x * f;
}

int main() {
	int i;
	n = read();
	for(i = 1; i <= (n<<1); i++) a[i] = read();
	sort(a+1, a+(n<<1)+1);
	for(i = 1; i <= n; i++) 
		ans += min(a[(i<<1)-1], a[i<<1]);
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>

#define pi acos(-1)

#define Rep(i,x,y) for (int i=x,_Lim=y;i<=_Lim;i++)
#define Dep(i,x,y) for (int i=x,_Lim=y;i>=_Lim;i--)

using namespace std;

inline int read(){
	int f=1,res=0,ch=getchar();
	while (ch<'0' || ch>'9'){
		if (ch=='-') f=-1;ch=getchar();
	}
	while (ch>='0' && ch<='9') res=res*10+ch-48,ch=getchar();
	return f*res;
}

typedef long long ll;

const int N=100005;

int n,a[N];
ll l[N],r[N];
int main(){
	n=read();
	Rep(i,1,n) a[i]=read();
	l[n]=2,r[n]=2;
	Dep(i,n,1){
		ll l_=(l[i]-1)/a[i]+1;
		ll r_=r[i]/a[i];
		if (l_>r_){
			puts("-1");return 0;
		}
		l[i-1]=l_*a[i];
		r[i-1]=(r_+1)*a[i]-1;
	}
	printf("%lld %lld\n",l[0],r[0]);
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int x;
  int y;
  cin >>x;
  cin >>y;
  int z;
  z = x % 500;
  if (z <= y){
    cout <<"Yes"<<endl;
  }
  else{
    cout <<"No"<<endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	int goukei = 0;
	int i;
	for (i = 0; i < 5; i++) {
		int x;
		if (scanf("%d" ,&x) != 1) return 1;
		goukei += x;
	}
	printf("%d\n", 15 - goukei);
	return 0;
}


Measured memory_bytes: 1708
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<complex>
#include<functional>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<stack>
#include<set>

using namespace std;
#define endl '\n'
#define eb emplace_back
#define fst first
#define scd second
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define YES(n) cout << ((n) ? "YES" : "NO" ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No" ) << endl

constexpr int MOD = 1000000007;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

// value
int N, K;


void solve() {

	cin >> N >> K;

	cout << N - K + 1 << endl;

	return;

}

int main() {

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

	solve();

	return 0;

}

Measured memory_bytes: 256
from collections import Counter
N,K = list(map(int, input().split()))
A = list(map(int, input().split()))
mod = int(1e9+7)

cnt1 = 0
for i in range(N):
  for j in range(i+1,N):
    if A[i] > A[j]:
      cnt1 += 1

cnt2 = 0
for i in range(N):
  for j in range(N):
    if A[i] > A[j]:
      cnt2 += 1
    
print((cnt1 * K % mod + ((cnt2 * K * (K-1)) ) // 2 ) % mod)

Measured memory_bytes: 9680
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <iostream>

using namespace std;

#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N;
i64 A[101010], B[101010];
i64 V[101010];

multiset<i64> sw;
i64 minf;

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) scanf("%lld", A + i);
	for (int i = 0; i < N; ++i) scanf("%lld", B + i);
	for (int i = 0; i < N; ++i) V[i] = A[i] - B[i];

	minf = 0;
	for (int i = 0; i <= N + 10; ++i) {
		sw.insert(0);
	}
	i64 pos = 0;
	for (int i = 0; i < N; ++i) {
		pos -= V[i];
		
		// add |x - pos|
		i64 b = *(sw.begin());
		if (pos < b) {
			sw.insert(pos);
		} else {
			sw.erase(sw.begin());
			minf += pos - b;
			sw.insert(pos);
			sw.insert(pos);
		}
	}
	i64 ret = minf;
	i64 last = *(sw.begin());
	int d = 0;
	for (auto a : sw) {
		a = min(a, pos);
		ret += d * (a - last);
		last = a;
		++d;
		if (a == pos) break;
	}
	printf("%lld\n", ret);

	return 0;
}


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

struct suretu
{
    int basho = 0;
    int nakami = 0;
};

int main()
{
    int N; cin >> N;
    vector<int> p(N);
    for (int i = 0; i < N; i++)
    {
        cin >> p.at(i);
    }

    suretu youso;
    int changetimes = 0;
    for(int i = 1; i <= N; i++)
    {
        if(i != p.at(i-1))
        {
            if(youso.nakami == 0)
            {
                youso.nakami = p.at(i-1);
                youso.basho = i;
                changetimes++;
            }
            else
            {
                if(youso.basho == p.at(i-1) && youso.nakami == i)
                {
                    changetimes++;
                }
                else
                {
                    cout << "NO" << endl;
                    return 0;
                }
                youso.nakami = 0;
                youso.basho = 0;
            }
        }
    }
    if(changetimes == 0 || changetimes == 2)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include<string>
#include <bitset>
#include <vector>
#include <functional>
#include <climits>
#include <iomanip>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <numeric>
#include <stack>
#include <map> // pair
#include <cstdlib>  // abs() for integer
#include <cmath>    // abs() for float, and fabs()
typedef std::stack<int> IntStack;
typedef std::stack<char> charStack;

using namespace std;
using ll = long long;
typedef pair <ll, ll > pll;

int main()
{
	ll a = 0, b = 0, c = 0, d = 0, e = 0, f = 0, g = 0, h = 0, ans = 0;
	ll n, m, K;
	ll memo[200005] = {};
	ll memo2[10004] = {};
	string s;
	string s1, s2;
	//IntStack yStack;
	//charStack Stack;
	//vector<pair<int, int> > pairs(a);
	cin >> a;
	cin >> b;
	for (int i = 0; i < a; i++)
	{
		cin >> c;
		for (int k = 0; k < c; k++)
		{
			cin >> d;
			memo[d]++;
		}
	}
	for (int i = 0; i <= b; i++)
	{
		if (memo[i]==a)
		{
			ans++;
		}
	}
	cout << ans << endl;

	////std::cout << std::fixed;
	//cout << std::setprecision(20) << << endl;
	//cout << d+1 << endl;
	//cout << "" << endl;

	return 0;
}
//char型の文字数字は、-'0'で数値に変換できる
//accumulate(x, x + a, 0);//int型までの配列の合計
//memcpy(x, visited, sizeof(ll)*n);
//void kansuu(ll num, ll visited[10]) {}
//kansuu(1, zz);
//cout << setprecision(15) << v << endl;
//cout << char(z - 'a');
//log10(i) + 1 //10進数の桁数を取得

//int temp;
//for (int i = 0; i < n - 1; i++) {
//	for (int j = n - 1; j > i; j--) {
//		if (w[j - 1] < w[j]) {  /* 前の要素の方が大きかったら */
//			temp = w[j];        /* 交換する */
//			w[j] = w[j - 1];
//			w[j - 1] = temp;
//		}
//	}
//}

//最小公倍数
//ll x = a * b;
//ll tmp;
///* 自然数 a > b を確認・入替 */
//if (a<b) {
//	tmp = a;
//	a = b;
//	b = tmp;
//}
///* ユークリッドの互除法 */
//ll r = a % b;
//while (r != 0) {
//	a = b;
//	b = r;
//	r = a % b;
//}
//a = x / b;//答え

Measured memory_bytes: 1792
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string>
#include <climits>
#include <tuple>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple< int,int,int > T;
int main(){
  int a,b;
  cin>>a>>b;
  if(a<=b)cout<<a<<endl;
  else cout<<a-1<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
const long long INF = LLONG_MAX / 2;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i, r, n) for(int i=(ll)(r); i<(ll)(n); i++) 
#define REP(i, n) FOR(i, (0), n)
#define ll long long int
using namespace std;
ll ans = 0, sum = 0, n, k, counter = 0, w, h;
string s;
vector<ll> v;
vector<pair<ll, ll>> vp;
vector<vector<ll>> vv(50, vector<ll>(50, INF));

int main() {
  ll a, b;
  cin >> n >> a >> b;
  v.resize(n);
  REP(i, n) cin >> v[i];
  sort(v.begin(), v.end());
  REP(i, v.size()) if (a > v[i] || v[i] >= b) ans++;
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int nax = 1000 * 1007;
int n;
char wcz[nax];
int tab[nax];
long long ans;
int main(void)
{
	scanf("%s", wcz + 1);
	n = strlen(wcz + 1);
	n++;
	for (int i = 1; i < n; i++)
	{
		if (wcz[i] == '<')
			tab[i + 1] = max(tab[i + 1], tab[i] + 1);
	}
	for (int i = n - 1; i; i--)
	{
		if (wcz[i] == '>')
		{
			tab[i] = max(tab[i], tab[i + 1] + 1);
		}
	}
	for (int i = 1; i <= n; i++)
	{
		ans += tab[i];
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 4608
import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt(),k=sc.nextInt(),s=sc.nextInt();

        for(int i=0;i<k;i++){
            System.out.print(s+" ");
        }

        int other = 1000000000;
        if(s>=1000000000)other =1;
        for(int i=0;i<n-k;i++){
            System.out.print(other+" ");
        }

    }
}


Measured memory_bytes: 44924
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <math.h>
#include <cmath>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
#include <random>
#include <deque>
#include <bitset>
#include <string>
#include <queue>
#include <complex>

//#define int long long

#define mp(a, b) make_pair(a, b)
#define all(v) (v).begin(), (v).end()

#define endl '\n'

using namespace std;
typedef long long ll;
typedef long double ld;

mt19937 mrand(random_device{}());

double PI = acos((double)-1);
const double eps = 1e-8;
const ll inf0 = 1023 * 1024 * 1024;
const ll inf = inf0 * inf0;
const ll mod = 1e9 + 7;
//const ll mod2 = 998244353;

void solve();
void scan();

signed main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cout << fixed; cout.precision(15);
	solve();
	return 0;
}

void solve() {
	vector<char> a(26);
	for (int i = 0; i < 26; i++) {
		a[i] = (char)(i + 'A');
	}	
	int t; cin >> t;
	string s; cin >> s; int n = s.size();
	vector<char> f(n);
	for (int i = 0; i < n; i++) {
		int l = s[i] - 'A';
		f[i] = a[(l + t) % 26];
	}
	for (char c : f) cout << c;
	cout << endl;
}


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

int main(){

	int N;

	do {
		cin >> N;
	} while (N < 100 || N > 999);

	int a = 0;
	int b = 0;
	int c = 0;

	while (N > 100) {
		N -= 100;
		a++;
	}
	while (N > 10) {
		N -= 10;
		b++;
	}
	while (N > 0) {
		N -= 1;
		c++;
	}
	if (a == 7 || b == 7 || c == 7) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 3636
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	private static List<Long> getStrings(Scanner sc, int num) {
		List<Long> stringList = new ArrayList<>();
		while(num>0) {
			long nextInt = sc.nextLong();
			stringList.add(nextInt);
			num--;
		}
		return stringList;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		List<Long> array = getStrings(sc, n);
		array.sort(Long::compareTo);
		long sum = 0;
		for (int i = 0; i < k; i++) {
			sum+=array.get(i);
		}
		System.out.println(sum);
	}

}


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

#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define repi(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define uniqueV(x)          \
  sort(x.begin(), x.end()); \
  x.erase(unique(x.begin(), x.end()), x.end());
#define debug(x) cerr << #x << ": " << x << '\n'
#define debug2(x, y) cerr << "(" << #x << ", " << #y << ") = " \
                          << "(" << x << ", " << y << ")" << '\n'

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

const long long INF = 3e18 + 12;
const int inf = 1e9;

// ----------------------------------------------

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

  string S;
  cin >> S;

  ll N = S.size();
  int P = 2019;

  if (P == 2 || P == 5) {
    long long res = 0;
    for (int i = 0; i < N; ++i)
      if ((S[N - i - 1] - '0') % P == 0) res += N - i;
    return res;
  }
  vector<long long> val(P, 0);
  long long tenfactor = 1;
  long long cur = 0;
  val[cur]++;
  for (int i = 0; i < N; ++i) {
    cur = (cur + (S[N - i - 1] - '0') * tenfactor) % P;
    tenfactor = (tenfactor * 10) % P;
    val[cur]++;
  }
  long long res = 0;
  for (int p = 0; p < P; ++p)
    res += val[p] * (val[p] - 1) / 2;

  cout << res << endl;
}

Measured memory_bytes: 3748
mod = 10**9 + 7


n = int(input())

def satisfy(s):
    for i in range(4):
        S = list(s)
        if i >= 1:
            S[i - 1], S[i] = S[i], S[i - 1]
        if "AGC" in "".join(S):
            return False
    return True

def dfs(depth, last4):
    if depth == n:
        if satisfy(last4):
            return 1
        else:
            return 0
    if last4 in MEMO[depth]:
        return MEMO[depth][last4]
    if satisfy(last4):
        ret = 0
        for c in "ACGT":
            ret += dfs(depth + 1, last4[1:] + c)
            ret %= mod
        MEMO[depth][last4] = ret
        return ret
    else:
        return 0

MEMO = [{} for _ in range(n + 1)]
print(dfs(0, "TTTT"))


Measured memory_bytes: 6096
list_n=[0]+list(map(int,input()))
l = len(list_n)

pay=0
back=0
for i in range(l-1,-1,-1):
    #l-1から0まで
    now = list_n[i]
    if now in [0,1,2,3,4] or (now == 5 and list_n[i-1]<5):
        pay+=now
        list_n[i]=0
    elif now in [6,7,8,9] or (now == 5 and list_n[i-1]>=5):
        back+=10-now
        list_n[i]=0
        list_n[i-1] +=1
    elif now==10:
        list_n[i]=0
        list_n[i-1] +=1
print(pay+back)

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

using namespace std;
using ll = long long;


int main()
{
	int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; i++)cin >> a[i];
	auto itr = unique(a.begin(), a.end());
	a.resize(itr - a.begin());
	n = a.size();
	//for(int i = 0; i < n; i++)cout << a[i];

	if(n < 3) {
		cout << 1 << endl;
		return 0;
	}

	int cnt = 1;
	for(int i = 1; i < n - 1; i++) {

		if((a[i - 1] < a[i] && a[i] > a[i + 1]) || (a[i - 1] > a[i] && a[i] < a[i + 1])) {

			//cout << a[i] << endl;
			cnt++;
			i++;
		}

	}
	cout << cnt << endl;
}

Measured memory_bytes: 640
#include<cstdio>
#define neko 2010
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
#define rf(i,a,b) for(register int i=(a);i>=(b);i=~(-(i)))
typedef long long ll;
ll dp[neko][neko],fac[neko*neko],ifac[neko*neko];
const ll mod=1e9+7;
int n,k;
ll ADD(ll x,ll y){return (x+=y)>=mod?x-mod:x;}
ll spow(ll m,ll n)
{
	ll b=1;
	for(;n;n>>=1,m=m*m%mod)if(n&1)b=b*m%mod;
	return b;
}
ll C(ll m,ll n){if(m<n)return 1;if(!n)return 1;return fac[m]*ifac[n]%mod*ifac[m-n]%mod;}
int main()
{
	scanf("%d%d",&n,&k);
	if(k==1)return printf("1\n"),0;
	fac[0]=ifac[0]=1;
	f(i,1,4000005)fac[i]=fac[i-1]*i%mod;
	ifac[4000005]=spow(fac[4000005],mod-2);
	rf(i,4000004,1)ifac[i]=ifac[i+1]*(i+1)%mod;
	dp[0][0]=1;
	f(i,0,n)
	 f(j,i,n)
	 {
		if(i)dp[i][j]=ADD(dp[i-1][j],dp[i][j]);
		if(j)dp[i][j]=ADD(dp[i][j],dp[i][j-1]*C(i+(j-1)*(k-1)+k-2,k-2)%mod);
	 }return printf("%lld\n",(dp[n][n]*fac[n]%mod+mod)%mod),0;
}

Measured memory_bytes: 94464
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long int lli;
typedef long double ld;
const int oo = 1e9;
int n, k;

const int nx = 1e5+5;
ll ac[nx][2];
ll dp[105][nx];
ll go(ll i, ll w){
	if(w>k) return -oo;
	if(i == n) return 0;
	if(dp[i][w] != -1) return dp[i][w];
	ll& ans = dp[i][w];
	ans = max(ans, go(i+1,w));
	if(w+ac[i][0]<=k) ans = max(ans, go(i+1,w+ac[i][0])+ac[i][1]);
	return ans;
}
int main(){
	
	cin>>n>>k;
	memset(dp, -1, sizeof dp);
	for(int i=0; i<n; i++) cin>>ac[i][0]>>ac[i][1];
	cout<<go(0,0)<<"\n";
}

Measured memory_bytes: 82304
#include<iostream>
#include<bits/stdc++.h>
#include<iomanip>
#include<math.h>
#include<vector>
#include<cctype>
#include<string>
#include<set>
#include<map>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
std::string line;
typedef long long ll;

int main(){

   string n;
   cin >> n;

   rep(i,3){
      if(n[i] == '1') n[i] = '9';
      else if(n[i] == '9') n[i] = '1';
   }
   cout << n << endl;



   return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;

public class Main {
	private static void solve(){
	//Implement solution here.
		int a = ni();
		int b = ni();
		int c = ni();
		System.out.println(b / a > c ? c : b/a);
	}

    //Switch input source (stdin/file)
	private static Scanner scanner = new Scanner(System.in);
	public static void main(String[] args){
        String debugDataPath = System.getenv("DD_PATH");        
        if(debugDataPath != null){
            try{
                scanner = new Scanner(new BufferedReader(new InputStreamReader(new FileInputStream(new File(debugDataPath)))));
            }catch(Exception e){
                throw new RuntimeException(e);
            }
        }
        solve();
	}

    //Input read utility
	private static StringTokenizer tokenizer = null;
	public static String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(scanner.nextLine());
			} catch (Exception e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}
    //Get next single int
	private static int ni() {
		return Integer.parseInt(next());
	}
    //Get next single long
	private static long nl() {
		return Long.parseLong(next());
	}
    //Get next single double
	private static double nd() {
		return Double.parseDouble(next());
	}
    //Get next int array from one line
	private static int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}
	//Get next char array from one line
	private static char[] ns() {
		return next().toCharArray();
	}
    //Get next long array from one line
	private static long[] nal(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nl();
		return a;
	}
}

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

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

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 4000001;
const long double eps = 1E-14;

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

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

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a % b);
}

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

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

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 pw(mint a, ll b) {
	if (b == 0) { return 1; }
	mint ret = pw(a, b >> 1);
	ret *= ret;
	if (b & 1) { ret *= a; }
	return ret;
}

typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;

typedef vector<mint> vmint;
typedef vector<vector<mint>> vvmint;
typedef vector<vector<vector<mint>>> vvvmint;

//////////////////////////////////////
ll N, M;
vvll g;

vll con;

bool dfs(ll v) {
	for (ll w : g[v]) {
		if(con[w]!=-1){
			if (con[v] == con[w]) { return false; }
		}

		else {
			con[w] = 1 - con[v];
			bool b=dfs(w);
			if (!b) { return false; }
		}
	}

	return true;
}

int main() {
	cin >> N >> M;
	g.resize(N + 1);
	repn(i, M) {
		ll a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	con.resize(N + 1, -1);
	con[1] = 0;
	bool b = dfs(1);
	
	ll sum = N * (N - 1) / 2;
	if (b) {
		ll count = 0;
		repn(i, N) {
			if (con[i] == 1) { count++; }
			//cout << con[i] << endl;
		}
		sum = count * (N - count);
	}

	cout << sum-M << endl;
}


Measured memory_bytes: 10092
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int main(){
    string s;
    cin >> s;
    int count = 0, ans = 0;
    for(int i=0; i<3; i++){
        if(s.at(i) == 'R'){
            count++;
            ans = max(count,ans);
        }else{
            ans = max(count,ans);
            count = 0;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3624
#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    char a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int s,t=0;
    if(n%2==0)
    {
    s=n/2;
    for(int i=s;i<n;i++)
    {
        if(a[i-s]==a[i])
        {
            t++;
        }

    }
    if(t==s)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
    }
    else
    {
        cout<<"No"<<endl;
    }
    return 0;
}


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

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define st first
#define nd second
#define endl '\n'
#define what_is(x) cerr << #x << " is " << x << endl;
#define what_is_v(x) cerr << #x << " is "; for(auto&e: (x)) cerr << e << ' '; cerr << '\n'; //vector, set
#define what_is_a(x, n) cerr << #x << " is "; for(int i=0;i<n;i++) cerr << x[i] << ' '; cerr <<  '\n'; //n first element of array
#define cerr_pair(x) '{' << x.st << ", " << x.nd << '}'
#define pwhat_is(x) cerr << #x << " is " << cerr_pair(x) << endl;
#define pwhat_is_v(x) cerr << #x << " is "; for(auto&e: (x)) cerr << cerr_pair(e) << ' '; cerr << '\n'; //vector, set
#define pwhat_is_a(x, n) cerr << #x << " is "; for(int i=0;i<n;i++) cerr << cerr_pair(x[i]) << ' '; cerr <<  '\n'; //n first element of array
#define int long long
// #define pow mypow

typedef pair<int,int> pii;
const int N = 1e6+5;
const int INF = 1e9+5;
const int MOD = 1e9+7;

bool is_prime(int x){ // x>=2
	if (x < 2) return 0;
	for(int i=2; i*i <=x; i++){
		if (x%i == 0) return false;
	}
	return true;
}
int n;
int solve(int m){
	int res = 1;
	while(res*(res+1) <= 2*m) res++;
	return res-1;
}
int32_t main()
{
	IOS
	// freopen("input.txt", "r", stdin);
	cin >> n;
	if (n == 1) return 0*puts("0");
	if (is_prime(n)) return 0*puts("1");
	set<int> divisors;
	vector<int> cnt(N, 0);
	for(int i=2; i*i<=n; i++){
		while (n%i == 0){
			divisors.insert(i);
			cnt[i]++;
			n = n / i;
		}
	}
	int ans = 0;
	if (n > 1) ans++;
	for(int d:divisors) ans += solve(cnt[d]);
	cout << ans << endl;
	return 0;
}


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

int main() {

	int m, n;
	cin >> m >> n;
	
	int arr[n];
	
	for (int i=0; i<n; i++) cin >> arr[i];
	
	sort(arr, arr+n);
	
	int diff[n-1];
	
	for (int i=0; i<n-1; i++) {
		diff[i] = arr[i+1] - arr[i];
	}
	
	sort(diff, diff+n-1);
	int s = 0;
	
	for (int i=0; i<n-m; i++) {
		s += diff[i];
	}
	
	cout << s << endl;
	
}


Measured memory_bytes: 1024
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int maxn=30;
int n;
struct tree
{
    int parent;
    int left,right;
};
tree node[maxn];
vector <int> ve[3];
void init ()
{
    memset (node,-1,sizeof(node));
}
void Ftraverse(int x)
{
    if(x==-1)
        return;
    ve[0].push_back(x);
    Ftraverse (node[x].left);
    Ftraverse (node[x].right);
}
void Mtraverse(int x)
{
     if(x==-1)
        return;
    Mtraverse (node[x].left);
    ve[1].push_back(x);
    Mtraverse (node[x].right);
}
void Etraverse(int x)
{
     if(x==-1)
        return;
    Etraverse (node[x].left);
    Etraverse (node[x].right);
    ve[2].push_back(x);
}
void print()
{
    char s[4][15]={"Preorder","Inorder","Postorder"};
    for (int i=0;i<3;i++)
    {
        printf("%s\n",s[i]);
        for (int j=0;j<ve[i].size();j++)
             printf(" %d",ve[i][j]);
        printf("\n");
    }
}
int main()
{
    scanf("%d",&n);
    init();
    for (int i=0;i<n;i++)
    {
        int x,left,right;
        scanf("%d%d%d",&x,&left,&right);
        left==-1? :node[x].left=left,node[left].parent=x;
        right==-1? :node[x].right=right,node[right].parent=x;
    }
    int parent;
    for (int i=0;i<n;i++)
        if(node[i].parent==-1)
        {
            parent=i;
            break;
        }
    Ftraverse(parent);
    Mtraverse(parent);
    Etraverse(parent);
    print();
    return 0;
}



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

int main(){
    int n;
    cin >> n;
    int digit = n % 10;
    if(digit == 2 || digit == 4 || digit == 5 || digit == 7 || digit == 9){
        cout << "hon" << endl;
    }
    if(digit == 0 || digit == 1 || digit == 6 || digit == 8){
        cout << "pon" << endl;
    }
    if(digit == 3){
        cout << "bon" << endl;
    }
}


Measured memory_bytes: 3576