akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
int main(void){
	
	int a,b;
	while(scanf("%d%d",&a,&b)!=EOF){
		if(((a+b)/1000000)!=0){
			printf("7\n");	
		}
			else if((a+b)/100000!=0){
				printf("6\n");	
				}
				else if((a+b)/10000!=0){
					printf("5\n");	
					}
					else if((a+b)/1000!=0){
						printf("4\n");
					    }
					    else if((a+b)/100!=0){
							printf("3\n");
					    	}
					    	else if((a+b)/10!=0){
								printf("2\n");
					    		}
					    		else if((a+b)/1!=0){
									printf("1\n");
					    			}		
	}

	return 0;
}



Measured memory_bytes: 1996
fun main(args: Array<String>) {
    val c1 = readIntList()
    val c2 = readIntList()
    val c3 = readIntList()
    val v1 = listOf(c1[0], c2[0], c3[0])
    val v2 = listOf(c1[1], c2[1], c3[1])
    val v3 = listOf(c1[2], c2[2], c3[2])
    val diffH1 = c2.mapIndexed { index, i -> i - c1[index] }
    val diffH2 = c3.mapIndexed { index, i -> i - c2[index] }
    val diffV1 = v2.mapIndexed { index, i -> i - v1[index] }
    val diffV2 = v3.mapIndexed { index, i -> i - v2[index] }
    printYesOrNo(
            diffH1[0] == diffH1[1] && diffH1[0] == diffH1[2] &&
                    diffH2[0] == diffH2[1] && diffH2[0] == diffH2[2] &&
                    diffV1[0] == diffV1[1] && diffV1[0] == diffV1[2] &&
                    diffV2[0] == diffV2[1] && diffV2[0] == diffV2[2]
    )
}

fun printYesOrNo(flag: Boolean) {
    println(if (flag) "Yes" else "No")
}

fun readIntList(): List<Int> = readLine()!!.split(' ').map { it.toInt() }

fun readInt(): Int = readLine()!!.toInt()

fun err(print: Any) {
    System.err.println(print)
}

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

#define rep(i, N) for(int (i) = 0; (i) < (N); i++)
#define all(v) v.begin(), v.end()
using i64 = int_fast64_t;

int main(){
    string S;
    cin >> S;
    int left = 0, right = S.size() - 1;
    int ans = 0;
    while(left < right){
        if(left == right) continue;

        if(S[left] != S[right]) ans++;
        left++, right--;
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <string>
#include <cmath>
#include <complex>
#include <numeric>
#include <cassert>

#include <vector>
#include <array>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <utility>

#define PI 3.14159265358979323846
#define int64 long long
#define uint64 unsigned long long
#define coutfix(i) cout << fixed << setprecision(i)		//coutの浮動小数出力の桁数設定
using namespace std;

int main()
{
	int64 nn, m4 = 0, m2 = 0, ot = 0;
	cin >> nn;
	vector<int64> aa(nn);
	for(int64 ii = 0;ii < nn;ii++)
	{
		cin >> aa[ii];
		if(aa[ii] % 4 == 0)
		{
			m4++;
		}
		else if(aa[ii] % 2 == 0)
		{
			m2++;
		}
		else
		{
			ot++;
		}
	}
	if(m4 + m2 / 2 >= nn / 2)
	{
		puts("Yes");
	}
	else
	{
		puts("No");
	}
	return 0;
}

Measured memory_bytes: 3960
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.nextLine().toCharArray();
        for (int i=0; i<s.length; ++i) {
            String x = String.valueOf(s[i]);
            if (x.equals(x.toUpperCase())) {
                System.out.print(x.toLowerCase());
            } else if (x.equals(x.toLowerCase())) {
                System.out.print(x.toUpperCase());
            } else {
                System.out.print(x);
            }
        }
        System.out.println("");
        sc.close();
    }
}



Measured memory_bytes: 26748
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<(int)(n);i++)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

int main(){
    string s; cin >> s;
    string yy = s.substr(0,4);
    string mm = s.substr(5,2);
    string dd = s.substr(8,2);


    if(stoi(mm) < 4){
        cout << "Heisei" << endl;
        return 0;
    }
    if(stoi(mm) > 4){
        cout << "TBD" << endl;
        return 0;
    }

    if(stoi(mm) == 4){
        if(stoi(dd) <= 30){
            cout << "Heisei" << endl;
            return 0;
        }else{
            cout << "TBD" << endl;
        }
    }
    assert(false);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
constexpr int INF = 2e9;
template <typename T> struct LazySegmentTree {
  
  int n;
  vector<T> node, lazy;

  LazySegmentTree (int sz, T init = 0) {
    n = 1; while (n < sz) n <<= 1;
    node.assign(2*n, init);
    lazy.assign(2*n,-1); /*区間加算の時は0*/
  }

  void eval (int k) {
    if (lazy[k] == -1) return ;
    node[k] = lazy[k]; /*区間加算に注意*/
    if (k < n) {
      lazy[2*k+1] = lazy[k];
      lazy[2*k+2] = lazy[k];
    }
    lazy[k] = -1;
  }

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

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

};
int main() {
  int n, q;
  cin >> n >> q;
  LazySegmentTree<int> left(n, n), bottom(n, n);

  ll res = ll(n - 2) * (n - 2);
  while (q--) {
    int t, x;
    cin >> t >> x;
    x--;
    if (t == 1) {
      int b = bottom.query(x, x + 1);
      res -= max(0, b - 2);
      if (left.query(0, b) > x + 1) left.update(0, b, x + 1);
    } else {
      int l = left.query(x, x + 1);
      res -= max(0, l - 2);
      if (bottom.query(0, l) > x + 1) bottom.update(0, l, x + 1);
    }
  }
  cout << res << endl;
  return 0; 
}

Measured memory_bytes: 11408
#include<iostream>

#include<algorithm>

using namespace std;





int main(){
   

long long a,b,k;
cin>>a>>b>>k;

for(int i=a;i<=b;i++){
	if( (i-a<k  ) || (b-i<k) ){
		cout<<i<<endl;
	}
}

    return 0;
}


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


Measured memory_bytes: 256
n = int(input())
string = str(input())

s1 = ""
s2 = ""

if(n % 2 == 0):
    for i, st in enumerate(string):
        if i < n/2:
            s1 = s1 + st
        else:
            s2 = s2 + st

    if s1 == s2:
        print("Yes")
    else:
        print("No")
else:
    print("No")

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

int main(){
	int n, k;
	int sum = 0;
	cin >> n >> k;
	vector<int> v(n);
	for(int i = 0; i < n; i++) {
		int l;
		cin >> l;
		v[i] = l;
	}
	sort(v.begin(), v.end());
	for(int i = n - 1; i >= (n-k); i--) {
		sum += v[i];
	}
	cout << sum;
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std; 
int main(){
	int N; cin >> N; 
	long long int T[100010] = {}; 
	long long int A[100010] = {}; 
	long long int P = 1e9+7; 
	for(int i = 1; i <= N; i++){
		cin >> T[i]; 
	}
	for(int i = 1; i <= N; i++){
		cin >> A[i]; 
	}
	long long int ans = 1; 
	long long int m1[100010] = {}; 
	long long int m2[100010] = {}; 
	long long int M1[100010] = {}; 
	long long int M2[100010] = {}; 
	for(int i = 1; i <= N; i++){
		if(T[i] != T[i-1]){
			M1[i] = T[i]; m1[i] = T[i]; 
		}
		else{
			M1[i] = T[i]; m1[i] = 1; 
		}
	}
	for(int i = 1; i <= N; i++){
		if(A[i] != A[i+1]){
			M2[i] = A[i]; m2[i] = A[i]; 
		}
		else{
			M2[i] = A[i]; m2[i] = 1; 
		}
		long long int pos = max(min(M1[i], M2[i]) - max(m1[i], m2[i]) + 1, 0LL); 
		ans *= pos; 
		ans = ans % P; 
	}
	cout << ans << endl; 
}

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

int main(){
  int N;
  cin >> N;
  vector<vector<int>> candies(2,vector<int>(N));
  for(int i=0; i<2; i++){
    for(int j=0; j<N; j++){
      cin >> candies.at(i).at(j);
    }
  }

  vector<int> c_candies(N,0);
  for(int i=0; i<N; i++){
    int row,col;
    row = 0; col = 0;
    c_candies.at(i) += candies.at(0).at(0);
    for(int j=0; j<N; j++){
      if(i == j){
        row++;
      }else{
        col++;
      }
      c_candies.at(i) += candies.at(row).at(col);
    }
  }

  sort(c_candies.begin(),c_candies.end());
  cout << c_candies.at(N-1) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
int n,m,q;
int main(void) {
    cin >> n >> m >> q;
    int lst[n+1][n+1]={};
    int sum[n+1][n+1]={};    
    rep(i,m){
        int l,r;
        cin >> l >> r;
        lst[l][r]++;
    }
    rep(i,n+1)rep(j,n+1){
        if(j==0)continue;
        sum[i][j]=sum[i][j-1]+lst[i][j];
    }
    int input[q][2]={};
    rep(i,q){
        cin >> input[i][0] >> input[i][1];
    }
    rep(i,q){
        int res=0;
        for(int j=input[i][0];j<=input[i][1];j++){
            res+=sum[j][input[i][1]]-sum[j][input[i][0]-1];
        }        
        cout << res << endl;
    }
    return 0;
}


Measured memory_bytes: 3712
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue>
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cassert>
#include <cctype>  // std::islower(), std::isupper(), std::tolower, std::toupper
#include <iomanip> // std::std::setprecision(X)
#include <limits>  //std::numeric_limits<int>::max(), min()

typedef long long ll;

int main (void) {
  int R,G; std::cin >> R >> G;
  std::cout << 2*G-R << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>

using namespace std;

#define forsn(i,s,n) for (int i = (s);i < (int)(n);i++)
#define forn(i,n) forsn(i,0,n)
#define dforsn(i,s,n) for (int i = (n) - 1;i >= (int)(s);i--)
#define dforn(i,n) dforsn(i,0,n)
#define all(v) ((v).begin(), (v).end())
#define F first
#define S second

int num[200000];
int zeroes[200000];

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

	int n; cin >> n;
	forn(i,n) cin >> num[i];
	forn(i,n) zeroes[i] = (num[i] == 0);
	dforsn(i,1,n) if (zeroes[i - 1]) zeroes[i - 1] = zeroes[i] + 1;
	
	long long int tot = 0;
	
	forn(i,n) {
		int sum = 0, xorr = 0;
		forsn(j, i, n) {
			if (num[j] == 0) {
				tot += zeroes[j];
				j += zeroes[j];
				if (j == n) break;
			}
			
			sum += num[j], xorr ^= num[j];
			
			if (sum == xorr) tot++;
			else break;
		}
	}
	
	cout << tot << endl;
}


Measured memory_bytes: 1792
//i ll be the king
#include<bits/stdc++.h>
#define ll long long int
#define sync ios_base::sync_with_stdio(false); cin.tie(NULL) 
#define input(arr,n) for(ll i1=0;i1<n;i1++ )cin>>arr[i1]
#define rep(n) for(ll i2=0;i2<n;i2++)
#define vmp(v,a,b) v.push_back(make_pair(a,b))
#define si(a) scanf("%lld",&a)
#define pi(a) printf("%lld",a)
#define aset(a,n,k) for(ll i3=0;i3<n;i3++)a[i3]=k; 	
#define mod 1000000007
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
int main()
{
	sync;
	ll n,cap;
	cin>>n>>cap;
	ll w[n],v[n];
	for(ll i=0;i<n;i++)
	{
		cin>>w[i];
		cin>>v[i];
	}
	ll dp[n+1][cap+1];
	for(ll i=0;i<=n;i++)
	{
		for(ll j=0;j<=cap;j++)
		{
			
			if(i*j==0)
			dp[i][j]=0;
			else if(w[i-1]<=j)
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);
			else
			dp[i][j]=dp[i-1][j];
		}
	}
	cout<<dp[n][cap]<<endl;
}
	

Measured memory_bytes: 79232
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


d = int(input())
def main(d):
    from collections import defaultdict
    vals = defaultdict(int)
    vals2 = defaultdict(int)
    for i in range(10):
        for j in range(10):
            vals[i-j] += 1
            if j>0:
                vals2[i-j] += 1
    def sub(n):
        vs = []
        for i in range(n):
            if i>=n-i:
                break
            vs.append(pow(10,n-i) - pow(10,i))
    #     if 9*sum(vs)<d:
    #         return 0
        def _sub(val, i):
            """vs[i:]以降でvalを作る通り数
            """
            if i==len(vs):
                if val==0:
                    return 1
                else:
                    return 0
            ans = 0
            for j in range(-9, 10):
                if (vs[i]*j)%pow(10,i+1)==val%(pow(10,i+1)):
                    ans += _sub(val-vs[i]*j, i+1) * vals[j]
            return ans

        ans = 0
        for i in range(-9,10):
            if (vs[0]*i)%10==d%10:
                ans += _sub(d-vs[0]*i, 1) * vals2[i]
        if n%2==0:
            ans *= 10
        return ans
    ans = 0
    i = 1
    while True:
        val = sub(i)
        ans += val
        if i>20:
            break
    #     if pow(10,i)-1>d:
    #         break
        i += 1
    return ans
print(main(d))

Measured memory_bytes: 75156
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int k,a,b;

int main(){
	ios::sync_with_stdio(false);
	cin>>k>>a>>b;
	int tmp=b/k;
	if(tmp*k>=a)
		cout<<"OK";
	else
		cout<<"NG";
	
	
	return 0;
}

Measured memory_bytes: 3652
#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() {
    long double a,b;
    cin >> a >> b;
    cout << (int64)(a*b) << endl;
}

Measured memory_bytes: 3176
while True:
    H, W = [int(i) for i in input().split()]
    if H == W == 0:
        break
 
    for h in range(H):
        for w in range(W):
            if h == 0 or h == H -1 or w == 0 or w == W -1:
                print('#', end='')
            else:
                print('.', end='')
 
        print()
 
    print()

Measured memory_bytes: 9116
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int INT_INF = 1LL << 30;

ll H;
ll func(ll H){
  if(H == 1) return 1;
  return 1 + 2 * func(H/2);
}

int main(){
  cin >> H;
  cout << func(H) << endl;
}

Measured memory_bytes: 256
h = Hash.new
for c in 'a'..'z' do
  h[c] = 0
end

s = gets.chomp.split("")
s.each { |c| h[c] = 1}

for c in 'a'..'z' do
  if h[c] == 0 then
    puts c
    exit
  end
end

puts 'None'

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

int main()
{
    int N;
    cin >> N;
    int Ai;
    vector<int> A;
    for(int i=0;i<N;i++){
        cin >> Ai;
        A.push_back(Ai);
    }
    int bit = 0;
    int i_s = 0;
    long long res = N;
    for(int i=0;i<N;i++){
        if((A[i] & bit) == 0){
            bit |= A[i];
        }else{
            res += (i - i_s - 1);
            bit -= A[i_s];
            i_s++;
            i--;
        }
    }
    res += (long long)(N-i_s) * (long long)(N-i_s-1) / 2;
    cout<<res<<endl;

    return 0;
}


Measured memory_bytes: 1400
sen = input()

long = len(sen)
count = 0

if(long % 2 == 0):
    for i in range(int(long/2)):
        if(sen[i] != sen[-(i + 1)]):
            count += 1
else:
    for i in range(int((long - 1)/2)):
        if(sen[i] != sen[-(i + 1)]):
            count += 1

print(count)


Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T iabs(const T& x) { return max(x, -x); }
// #define abs gabs

int main() {
    int n, m;
    cin >> n >> m;
    cout << (n == m ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 888
import heapq
N, M = map(int, input().split())

A = list(map(int, input().split()))

hq = []

for i in range(N):
    heapq.heappush(hq, -(A[i]))


while(M):
    k = heapq.heappop(hq) * -1
    k = k // 2
    heapq.heappush(hq, -k)
    M -= 1
ans = 0
for i in range(N):
    ans += heapq.heappop(hq)

print(-ans)


Measured memory_bytes: 14184
use proconio::input;

fn main() {
    input! {
        (n, m, x): (usize, usize, usize),
        caas: [(usize, [usize; m]); n]
    };

    let mut ans = std::usize::MAX;

    'outer: for i in 0..=(2usize.pow(n as u32) - 1) {
        let mut cost = 0;
        let mut algo_total = vec![0; m];
        for j in 0..n {
            if (i & (1 << j)) > 0 {
                let (c, aa) = caas[j].clone();
                cost += c;
                for k in 0..m {
                    algo_total[k] += aa[k];
                }
            }
        }

        for a in algo_total {
            if a < x {
                continue 'outer;
            }
        }

        if cost < ans {
            ans = cost;
        }
    }

    if ans == std::usize::MAX {
        println!("-1");
    } else {
        println!("{}", ans);
    }
}


Measured memory_bytes: 2196
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    import math
    from collections import defaultdict

    mod = 1000000007

    N = int(input())

    zero_pair = 0
    zero_a = 0
    zero_b = 0
    pair_plus = defaultdict(int)
    pair_minus = defaultdict(int)
    for a, b in [tuple(map(int, input().split())) for _ in range(N)]:
        if a == 0 and b == 0:
            zero_pair += 1
            continue
        if a == 0:
            zero_a += 1
            continue
        if b == 0:
            zero_b += 1
            continue

        abs_a = abs(a)
        abs_b = abs(b)
        g = math.gcd(abs_a, abs_b)
        abs_a = abs_a//g
        abs_b = abs_b//g
        if a * b > 0:
            pair_plus[(abs_a, abs_b)] += 1
        else:
            pair_minus[(abs_a, abs_b)] += 1

    ans = 1
    ans *= (pow(2, zero_a, mod) + pow(2, zero_b, mod) - 1) % mod
    ans %= mod

    count_all = 0
    for item in pair_plus.items():
        a, b = item[0]
        cnt = item[1]
        if (b,a) in pair_minus:
            ans *= (pow(2, cnt, mod) + pow(2, pair_minus[(b,a)]) - 1) % mod
            ans %= mod
            del pair_minus[(b, a)]
        else:
            count_all += cnt

    for val in pair_minus.values():
        count_all += val

    ans = (ans * pow(2, count_all, mod)) % mod
    ans += zero_pair
    print((ans - 1) % mod)

main()




Measured memory_bytes: 71896
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int H[100010];
int main()
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) cin >> H[i];
	for (int i = N - 1; i > 0; i--) {
		if (H[i - 1] - H[i] >= 2) {
			cout << "No" << endl;
			return 0;
		}
		if (H[i - 1] > H[i]) H[i - 1]--;
	}
	cout << "Yes" << endl;
}

Measured memory_bytes: 3988
#include<stdio.h>

int main(void){
	int H,W,a[100000],b,c=0,d=0,e=0;
	for(b=0;;b++){
		scanf("%d %d",&H,&W);
		a[b]=H;
		a[b+1]=W;
		if(a[b]+a[b+1]==0){
			break;
		}
		b++;
	}
	for(b=0;a[b]+a[b+1]!=0;b++){
		for(c=0;c<a[b];c++){
			if(c%2==0){
				for(e=0;e<a[b+1];e++){
					if(e%2==0){
						printf("#");
						if(c>=a[b]){
							printf("\n");
						}
					}else{
						printf(".");
						if(c>=a[b]){
							printf("\n");
						}
					}
				}
			}else{
				for(e=0;e<a[b+1];e++){
					if(e%2==0){
						printf(".");
						if(c>=a[b]){
							printf("\n");
						}
					}else{
						printf("#");
						if(c>=a[b]){
							printf("\n");
						}
					}
				}
			}
			printf("\n");
		}
		printf("\n");
		b++;
	}
		return 0;
}



Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)

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

  int n;
  cin >> n;
  string s[n];
  REP(i, n) cin >> s[i];

  map<char, int> mp;

  int cset[26];
  REP(i, 26) cset[i] = 55;

  REP(i, n){
    REP(j, s[i].size()) mp[s[i][j]]++;
    REP(k, 26){
      cset[k] = min(cset[k], mp['a' + k]);
      mp['a' + k] = 0;
    }
  }

  REP(i, 26){
    char q = 'a' + i;
    REP(j, cset[i]){
      cout << q;
    }
  }

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1000000007;
#define lcm(x, y) ((x) * (y) / __gcd((x), (y)))
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define debug(x) cout << #x << " : " << x << endl
#define part cout<<"----------------------------------\n";
#define mp make_pair
#include <iostream>
#define fastinput ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);


LL sum[500];
LL dp[500][500];

LL cal(LL left,LL right)
{
    if(left==right)
    {
        dp[left][right]=0;
    }
    else if(left==right-1)
    {
        dp[left][right]=sum[right]-sum[left-1];
    }
    else if(dp[left][right]==-1)
    {
        
        LL rightlimit=left;
        LL i;
        LL ans;
        for(i=rightlimit;i<right;i++)
        {
            if(dp[left][i]==-1)
            {
                dp[left][i]=cal(left,i);
            }

            if(dp[i+1][right]==-1)
            {
                dp[i+1][right]=cal(i+1,right);
            }


            if(i==rightlimit)
            {
                ans=dp[left][i]+dp[i+1][right];
            }
            else
            {
                ans=min(ans,dp[left][i]+dp[i+1][right]);
            }
            
        }

        dp[left][right]=ans+(sum[right]-sum[left-1]);
    }
    //cout<<"returning dp["<<left<<"]["<<right<<"] as "<<dp[left][right]<<endl;
    return dp[left][right];
}

int main()
{    
    fastinput;
    LL n,i,j,k;
    cin>>n;
    LL arr[n];
    sum[0]=0;

    for(i=0;i<500;i++)
    {
        for(j=0;j<500;j++)
        {
            dp[i][j]=-1;
        }
    }
    for(i=1;i<=n;i++)
    {
        cin>>arr[i];
        sum[i]=sum[i-1]+arr[i];
    }

    cout<<cal(1,n)<<endl;
    


    
    return 0;
}

/* stuff you should look for
    * int overflow, 
    * array bounds,
    * edge cases (constraints ZERO)
    * Overlapping of Indices on addition/subtraction
    * special cases (n=1?), set tle,
    * see nested loop does not have same LOOP CONTROL VARIABLES,
*/


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

int main() {
    string S;
    cin >> S;
    int t = S.size() , N = S.size();
    for(int i = 1; i < N; i++){
        if(S[i - 1] == S[i]){
            t--;
            i+=2;
        }
    }
    cout << t << endl;
}

Measured memory_bytes: 640
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let n: usize = iterator.next().unwrap().parse().unwrap();
    let h: usize = iterator.next().unwrap().parse().unwrap();
    let w: usize = iterator.next().unwrap().parse().unwrap();

    let ans = (n - h + 1) * (n - w + 1);
    return ans.to_string();
}


Measured memory_bytes: 2152
#include <bits/stdc++.h>
#define mset(a, b) memset(a, b, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))
#define rg register
using namespace std;
typedef long long LL;
const int MAXN = 4005;
const int MAXM = 200005;
const int O = 2000, OO = 4000;
const LL MOD = 1e9 + 7;
const LL INV2 = (MOD+1)>>1;

template <typename T> inline void read(T &AKNOI) {
	T x = 0, flag = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') flag = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	AKNOI = flag * x;
}

int n, m, a[MAXM], b[MAXM], st[MAXN][MAXN], ed[MAXN][MAXN];
LL fac[MAXM], inv[MAXM], finv[MAXM], dp[MAXN];

inline void Inc(LL &x, LL y) {
	x += y; if (x >= MOD) x -= MOD;
}

inline LL C(int x, int y) {
	return fac[x] * finv[y] % MOD * finv[x-y] % MOD;
}

void init() {
	read(n);
	for (int i=1;i<=n;++i) {
		read(a[i]); read(b[i]);
		++st[O-a[i]][O-b[i]];
		++ed[O+a[i]][O+b[i]];
	}
	fac[0] = fac[1] = inv[0] = inv[1] = finv[0] = finv[1] = 1;
	for (int i=2;i<MAXM;++i) {
		fac[i] = fac[i-1] * i % MOD;
		inv[i] = (MOD-MOD/i) * inv[MOD%i] % MOD;
		finv[i] = finv[i-1] * inv[i] % MOD;
	}
}

void solve() {
	LL ans = 0;
	for (int i=0;i<=OO;++i) {
		for (int j=0;j<=OO;++j) {
			Inc(dp[j], st[i][j]);
			if (j) Inc(dp[j], dp[j-1]);
			if (ed[i][j]) Inc(ans, dp[j] * ed[i][j] % MOD);
		}
	}
	for (int i=1;i<=n;++i) {
		ans = (ans - C(a[i]*2+b[i]*2, a[i]*2) + MOD) % MOD;
	}
	ans = ans * INV2 % MOD;
	printf("%lld\n", ans);
}

int main() {
	init();
	solve();
	return 0;
}


Measured memory_bytes: 74496
import collections
n, m = map(int, input().split())
par = list(range(2 * n))

# print(par)


# union find(parには0も入れているので、par[1]=1になる)
def find(x):

    while par[x] != x:
        tmp = par[x]
        par[x] = par[par[x]]
        x = par[x]

    return x


def union(x, y):
    x1 = find(x)
    y1 = find(y)
    if x1 != y1:
        par[x1] = y1


# 各要素をunionする
for j in range(m):
    a, b = map(int, input().split())
    union(a - 1, b - 1)

s = [0 for i in range(n + 5)]

# 1～nの親を探してsに入れていき、一番多い親を答えにする
for k in range(n):
    s[find(k)] += 1

print(max(s))


Measured memory_bytes: 26872
"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc082/tasks/arc082_d

aiが固定ならば、ただクエリをソートしてシミュレーションしながら答えを出せばよい
今回はそうでないので、方法を考える

一度でも砂が落ち切ってしまえば、その後はaiに関わらず、答えは等しくなる
おちきっていない場合、常に砂が移動し続けるので、初期値からの差分が常に等しくなる
よって、落ち切らないaの範囲を保持し、一度も落ち切らない場合の初期からの差分
& 落ち切ってしまった場合のシミュレーション結果を用いて答えればよい

→どのタイミング(区間)で落ち切るかでその後の動きが違くね？？？
→死

→aの区間は高々3つに分けられる
→ aが少なく、a=0と同じに収束する場合、 aが大きく、a=Xと同じに収束する場合。、一度も落ち切らない場合
→そして、a=0,a=Xと同じになる場合は、それぞれaの初期値の区間の両端から侵食していく
→よって、a=0のシミュ、a=Xのシミュ、落ち切らない差分シミュ。その時あるaがどれに属すかの区間
を用いてシミュレーションしながらdp的に処理してあげればよい

あとは実装が面倒そう
"""
from collections import deque
X = int(input())
K = int(input())

r = list(map(int,input().split()))
#番兵
r.append(float("inf"))
r.append(0)

ta = deque([])
Q = int(input())

for i in range(Q):
    t,a = map(int,input().split())
    ta.append([t,a])

ZA = 0 #初期がa=0の時のシミュ結果
XA = X #初期がXの時
D  = 0 #差分計算
Zmax = 0 #aがZmax以下ならZAと等しくなる
Xmin = X #aがXmin以上ならXAと等しくなる

for i in range(K+1):

    time = r[i] - r[i-1]

    #クエリの処理(r[i]以下に関して)
    if i % 2 == 0: #Aが減っていく
        
        while len(ta) > 0 and ta[0][0] <= r[i]:
            t,a = ta.popleft()
            td = t - r[i-1]

            if a <= Zmax:
                print (max( 0 , ZA-td ))
            elif a >= Xmin:
                print (max (0 , XA-td ))
            else:
                print (max (0 , a+D-td))

        D -= time
        Zmax = max(Zmax,-1*D)
        ZA = max(0,ZA-time)
        XA = max(0,XA-time)

    else: #Aが増えていく
        
        while len(ta) > 0 and ta[0][0] <= r[i]:
            t,a = ta.popleft()
            td = t - r[i-1]

            if a <= Zmax:
                print (min( X , ZA+td ))
            elif a >= Xmin:
                print (min (X , XA+td ))
            else:
                print (min (X , a+D+td))

        D += time
        Xmin = min(Xmin,X-D)
        ZA = min(X,ZA+time)
        XA = min(X,XA+time)


    


Measured memory_bytes: 103444
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c;
  int d[10000],q=0;
  cin>>a>>b>>c;
  for(int i=1;i<=max(a,b);i++){
    if(a%i==0&&b%i==0) d[q]=i,q++;
  }
  sort(d,d+q,greater<int>());
  cout<<d[c-1]<<"\n";
}


Measured memory_bytes: 256
#include <stdio.h>

typedef long long ll;

int main(void)
{
	int N, N2, Q, B, C, i, sub, sum;
	ll ans = 0;
	scanf("%d\n", &N);

	int a[100001] = {0};

	for (i = 0; i < N; i++)
	{
		scanf("%d", &N2);
		a[N2]++;
		ans += N2;
	}
	scanf("%d\n", &Q);
	for (i = 0; i < Q; i++)
	{
		scanf("%d %d", &B, &C);
		sub = C - B;
		sum = a[B] * sub;
		a[C] += a[B];
		a[B] = 0;
		ans += sum;
		printf("%lld\n", ans);
	}

	return (0);
}

Measured memory_bytes: 2128
import java.util.*;

public class Main {
public static void main(String[] args) {
		
		Scanner keyboard = new Scanner(System.in); 
		
		int N  = keyboard.nextInt();
		int K  = keyboard.nextInt();
		int[] p = new int[N];
		
		for(int i = 0; i < N ; i++) {
			p[i] = keyboard.nextInt();
		}
		
		Arrays.sort(p);
		int ans = 0;
		
		for(int j = 0; j < K; j++) {
			ans += p[j];
		}
		
		System.out.println(ans);
		keyboard.close();	
	}
}


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

using namespace std;

using u128 = __uint128_t;

#define int long long
#define MOD 1000000007

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

    int n;
    cin>>n;
    int count = 0;
    for(int i = 1; n!= 0; i*=2){
        count +=i;
        n /= 2;
    }
    cout<<count<<endl;
    return 0;
}

Measured memory_bytes: 256
N,D=map(int, raw_input().split())
X=[ map(int, raw_input().split()) for _ in range(N) ]

ans=0
for i in range(N):
	for j in range(i+1,N):
		t=0
		for x, y in zip(X[i],X[j]):
			t+=(x-y)**2	

		for h in range(1,10000):
			if t==h**2:
				ans+=1
				break

print ans

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

int main(){
    int N, K;
    long long time=0;
    cin >> N;
    pair<int, int> v[N];
    bool flag=true;

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

    sort(v, v+N);
    
    for(int i=0; i<N; i++){
	time += v[i].second;
	if(time > v[i].first){
	    flag = false;
	    break;
	    
	}
    }

    if(flag)
	puts("Yes");
    else
	puts("No");
}



Measured memory_bytes: 1792
#include "bits/stdc++.h"
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define repf(i, x, n) for (int i = (int)(x); i < (int)(n); i++)
#define repfr(i, x, n) for (int i = (int)(x)-1; i >= (int)(n); i--)
#define INF 1e9
using ll = int64_t;
template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T> bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return true;
  }
  return false;
}

//10^9 + 7
#define yojo 1000000007

std::int64_t gcd(std::int64_t a, std::int64_t b) {
  // a >= b && b != 0
  std::int64_t c;
  do {
    c = a % b;
    a = b;
    b = c;
  } while (c);

  return a;
}
std::int64_t gcd_s(std::int64_t aa, std::int64_t bb) {
  std::int64_t a = max(aa, bb);
  std::int64_t b = min(aa, bb);
  std::int64_t c;
  if (b == 0) {
    return -1;
  }
  do {
    c = a % b;
    a = b;
    b = c;
  } while (c);

  return a;
}
void rle(std::vector<std::pair<char, std::int64_t>> &data, std::string str) {
  char now = str[0];
  std::int64_t count = 0;
  for (std::int64_t i = 0; i < str.size() + 1; i++) {
    if (i == str.size()) {
      data.push_back(make_pair(str[i - 1], count));
      break;
    } else if (now != str[i]) {
      data.push_back(make_pair(now, count));
      now = str[i];
      count = 0;
    }
    count++;
  }

  return;
}

#define MAX_NUM 200001

void Main() {
  //自動整形防止用コメント
  string s;
  cin >> s;
  sort(all(s));
  std::cout << (s[0] == s[1] && s[2] == s[3] && s[1] != s[2]? "Yes" : "No") << std::endl;

  return;
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  Main();
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> bool cmax(T& a, U b) { if (a<b) {a = b; return true;} else return false; }
template<class T, class U> bool cmin(T& a, U b) { if (a>b) {a = b; return true;} else return false; }

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

  ll n;
  cin >> n;
  vl a(n);
  vector<vl> x(n), y(n);
  rep(i, n) {
    cin >> a[i];
    rep(j, a[i]) {
      ll xx, yy;
      cin >> xx >> yy;
      xx--;
      x[i].push_back(xx);
      y[i].push_back(yy);
    }
  }

  ll ans = 0;
  rep(bit, 1LL<<n) {
    bool f = 1;
    rep(i, n) {
      if (f && (bit & 1LL<<i)) {
        rep(j, a[i]) {
          if ((bool)y[i][j] != (bool)(bit & 1LL<<(ll)(x[i][j]))) {
            f = 0;
//            cerr << "ij" << endl;
//            cerr << i << " " << j << endl;
//            cerr << x[i][j] << " " << y[i][j] << endl;
            break;
          }
        }
      }
    }

//    cerr << bit << endl;
//    cerr << f << endl;
//    cerr << __builtin_popcount(bit) << endl << endl;
    if (f) {
      cmax(ans, __builtin_popcount(bit));
    }
  }

  cout << ans << endl;
}


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

int hantei(int i){
    if(i==5){
        return 2;
    }
    if(i==7){
        return 1;
    }
    return 0;
}

int main(void){
    int A, B, C;
    cin >> A >> B >> C;
    if(hantei(A)+hantei(B)+hantei(C)==5){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
}


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

using namespace std;

int a[10005],b[10005];

int main()
{
    int n;
    long long s=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=0;i<n;i++)
    {
        scanf("%d",&b[i]);
    }
    for(int i=0;i<n;i++)
    {
        if(a[i]>b[i])
        {
            s-=(a[i]-b[i]);
        }
        else if(a[i]<b[i])
        {
            s+=(b[i]-a[i])/2;
        }
    }
    if(s>=0)
        printf("Yes\n");
    else
        printf("No\n");
	return 0;
}


Measured memory_bytes: 384
H, W = map(int, input().split())
a = list(input() for _ in range(H))

ans = []
for i in range(H + 2):
  if i == 0 or i == H + 1:
    ans.append("#" * (W + 2))
  else:
    ans.append("#" + a[i - 1] + "#")

for j in ans:
  print(j)

Measured memory_bytes: 3060
#include <stdio.h>

int main(){

  char ch;
  while(1){
    scanf("%c",&ch);
    if(ch=='\n')break;
 
    if(isupper(ch)) {
      ch=tolower(ch);
    } else if(islower(ch)) {
      ch=toupper(ch);
    }
    printf("%c",ch);
  }
  printf("\n");
  return 0;
}

Measured memory_bytes: 524
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define REP(i, d, n) for(int i=(d); i<(n); ++i)
#define all(v) v.begin(), v.end()
using ll = long long;
using P = pair<int, int>;

int main() {

    string s;
    cin >> s;

    if(s[2] == s[3] && s[4] == s[5]){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<set>

using namespace std;

int main()
{
	set <int> s;

	for (int i = 1; i < 10; i++)
	{
		for (int j = 1; j < 10; j++)
		{
			s.insert(i * j);
		}
	}
	int n;

	cin >> n;

	if (s.count(n)) cout << "Yes";
	else cout << "No";

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define all(v) v.begin(), v.end()
#define sz(v) v.size()
#define INF 100000000000000 //10^14
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll 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 { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= 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 { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

vector<mint> fac(2000003, 1);
void calc(int n){
  rep(i, n){
    fac.at(i+1) = fac.at(i) * (i+1);
  }
  return;
}

mint mcom(int r, int c){ // (r+c)!/(r!c!)
  mint a = fac.at(r+c);
  mint b = fac.at(r);
  mint d = fac.at(c);
  mint ans = a / (b * d);
  return ans;
  }

mint mpow(mint x, ll y){
  if(y == 0){
    return 1;
  }
  if(y % 2 == 0){
    mint a = mpow(x, y / 2);
    return a * a;
  }
  else{
    mint a = mpow(x, y / 2);
    return a * a * x;
  }
}

mint mperm(ll x, ll y){
  mint a = fac.at(x);
  mint b = fac.at(x-y);
  return a / b;
}

int main()
{
  ll N, M;
  cin >> N >> M;
  calc(2000000);
  mint ans = 0;
  rep(i, N+1){
    ans += mpow(-1, i) * mcom(N-i, i) * mperm(M-i, N-i);
  }
  cout << ans * mperm(M, N) << endl;
}

Measured memory_bytes: 18696
def solve(k, a, b):
    for i in range(a, b+1):
        if i % k == 0:
            return 'OK'
    return 'NG'

if __name__ == "__main__":
    k = int(input())
    a, b = map(int, input().split(' '))
    print(solve(k, a, b))

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

#define ll long long 
#define debug if (debug_message)

#define file_io 0
#define debug_message 0

ll i,t,j;
ll n,nt,sum,x;

int main(){
	if (file_io){
		freopen(".in","r",stdin);
		freopen(".out","w",stdout);
	}
	
	scanf("%lld",&n);
	
	for (i=1; i<=n; ++i){
		t=i,j=n-(n%i);
		x=(t+j)*((j-t)/i+1)/2; 
	
		sum+=x;
	}
	
	printf("%lld\n",sum);
	
	return 0;
}
/*

*/

Measured memory_bytes: 1736
#include <iostream>

using namespace std;

int main(int argc, char* argv[])
{
    int N; cin >> N;
    
    int highest_hotel = 0, hotel = 0;
    for (int i = 0; i < N; i++) {
        int H; cin >> H;
        if (highest_hotel <= H) {
            highest_hotel = H;
            hotel++;
        }
    }

    cout << hotel << endl;
    return 0;
}


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

typedef pair<int,int> P;

int main(){
    ll n;
    cin >> n;
    vector<ll> v(n+1);
    ll sum = 0;
    for (ll i = 0; i <= n; i++){
        cin >> v[i];
        sum += v[i];
    }

    if (n == 0){
        if (v[0] == 1) cout << 1 << "\n";
        else cout << -1 << "\n";

        return 0;
    }

    ll o = 1;
    ll res = 0;
    for (ll i = 0; i <= n; i++){
 //       cout << i << "\n";
        res += o;
        ll noruma = v[i];

        if (o <= noruma && !(i == n && o == noruma)){
            res = -1;
//            cout <<"break\n";
            break;
        }else{
//            cout << o;
            o -= noruma;
            sum -= noruma;
//            cout << "-" << noruma << "=" << o << "\n";
        }

        o *= 2;
        if (o > sum){
            o = sum;
//            cout << "sum  o = " << o << "\n";
        }
    }

    cout << res << "\n";
}

Measured memory_bytes: 4052
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))


A.append(0)
C.append(C[0])

satis = sum(B) 

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

		satis += C[j]

print(satis)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define pb push_back
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define yoi cout<<"yo"<<endl;
#define debug(x) cerr << #x << " is " << x << endl;
#define all(x) x.begin(),x.end()
const lli inf=1e18;
const int mod=1e9+7;
int main(){
IOS;
lli n;
cin>>n;
n=n*n*n;
cout<<n<<endl;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main
{
	public static void main(String[] args) throws NumberFormatException, IOException
	{
		// TODO 自動生成されたメソッド・スタブ
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int a = Integer.parseInt(br.readLine());
		long b = 1;
		for(int i = 0; i < a; i++)
		{
			b = (b * (i + 1)) % 1000000007;
		}
		System.out.println(b);
	}
}

Measured memory_bytes: 23252
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
	int n;
	scanf("%d",&n);
	int a,b,c=0;
	scanf("%d %d",&a,&b);
	c=__gcd(a,b);
	while(n-2){
		int x;scanf("%d",&x);
		if(x%c){
			c=x%c;
		}
		n--;
	}
	printf("%d",c);
	return 0;
} 

Measured memory_bytes: 128
/**
 *      purpose : Tenka1 Programmer Beginner Contest B
 *      author  : kyomukyomupurin
 *      created : 2018-11-02 22:59:32
**/

#include <bits/stdc++.h>
using namespace std;
#define int64 long long
#define print(x) cout << (x) << '\n'

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int A, B, K; cin >> A >> B >> K;

    for (int i = 1; i <= K; ++i) {
        if (i % 2 == 1){
            if (A % 2 == 1){
                --A; B += (A / 2); A /= 2;
            }
            else if (A % 2 == 0) {
                B += (A / 2); A /= 2;
            }
        }
        else if (i % 2 == 0){
            if (B % 2 == 1){
                --B; A += (B / 2); B /= 2;
            }
            else if (B % 2 == 0){
                A += (B / 2); B /= 2;
            }
        }
    }
    cout << A << " " << B << '\n';
    
    return 0;
}


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

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll,ll> lll;

const ll MOD = 1000000007;
const ll INF = 1e9+5;
const double eps = 1e-7;
const double PI = acos(-1.0);

#define FOR(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
#define RFOR(i,a,b) for(long long i = (long long)(a); i >= (long long)(b); i--)
#define ull unsigned long long
#define deb(x )     cerr << #x << " = "<< x << endl;
#define endl    "\n"
#define coud(a,d) cout << fixed << showpoint << setprecision(d) << a;
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define fill(x, y) memset(x, y, sizeof(y))
#define all(x) (x).begin(), (x).end()
#define bitcount(x) __builtin_popcount(x)
#define cps CLOCKS_PER_SEC
#define verify(x) if(x >= MOD) x -= MOD;

inline void debug_vi(vi a) {FOR(i, 0, a.size()) cout<<a[i]<<" ";}
inline void debug_vll(vll a) {FOR(i, 0, a.size()) cout<<a[i]<<" ";}
inline void print_case(int tn) {cout<<"Case #"<<tn<<": ";}

template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

template<typename T>
using maxpq = priority_queue<T>;
/*----------------------------------------------------------------------*/

int main(){
    std::ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int n,k; cin>>n>>k;
    vi arr(n);
    FOR(i, 0, n) {
        cin>>arr[i]; arr[i]--;
    }
    ll res = 0; map<int, ll> cnt; cnt[0] = 1;
    ll prefs[n + 1]; prefs[0] = 0;
    FOR(i, 0, n) {
        prefs[i + 1] = (prefs[i] + arr[i])%k;
        if(i >= k - 1) {
            cnt[prefs[i - k + 1]]--;
        }
        if(cnt.count(prefs[i + 1])) {
            res += 1LL * cnt[prefs[i + 1]];
            cnt[prefs[i + 1]]++;
        } else {
            cnt.insert({prefs[i + 1], 1});
        }
    }
    cout << res;
    return 0;
}

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

using namespace std;

template <typename T>
T gcd(T a, T b) {
  if (a == 0) return b;
  if (b == 0) return a;
  return (b ? gcd(b, a % b) : a);
}

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A[i];

  vector<int> L(N + 1);  // L[i] = gcd(A[0], ..., A[i - 1])
  vector<int> R(N + 1);  // R[i] = gcd(A[i], ..., A[N - 1])
  L[0] = 0;
  R[N] = 0;
  for (int i = 0; i < N; i++) {
    L[i + 1] = gcd(L[i], A[i]);
  }
  for (int i = N - 1; i >= 0; i--) {
    R[i] = gcd(R[i + 1], A[i]);
  }

  int answer = 0;
  for (int i = 0; i < N; i++) {
    answer = max(answer, gcd(L[i], R[i + 1]));
  }
  cout << answer << endl;

  return 0;
}


Measured memory_bytes: 1408