akhauriyash/Code-Regression huggingface dataset:
def run(N, K, A):
    '''
    K <= 10^12 ~= 2^40
    Kの2進数における各桁ごとの最大となるKを求めることができる(O(logK))
    Kの2進数における最初の1を0に変える位置をk_nとする
    最初に変える位置の前はすべてKと同じ、それ以降は最大を取るものを選択する(O(log(K)))
    k_nが0の場合は、全て同じパターンとしてスキップする
    上記の最大のものを習得する
    '''
    cnt1 = []

    # Kの2進数の桁を取得
    k_n = len(bin(K)) - 2

    # Aの2進数の最大桁を取得
    max_a = len(bin(max(A))) - 2
    max_a = max(max_a, k_n)

    # 数値をビットに変換
    K_bit = '{:b}'.format(K).zfill(max_a)
    A_bit = []
    for i in range(len(A)):
        A_bit.append('{:b}'.format(A[i]).zfill(max_a))

    # 2進数の各桁の値を事前計算
    bit_v = []
    for i in range(max_a):
        bit_v.append(2**(max_a-i-1))

    # A_bitの各桁の1の数を数える(O(NlogK))
    for j in range(max_a):
        cnt = 0
        for i in range(N):
            if A_bit[i][j] == '1':
                cnt += 1
        cnt1.append(cnt)

    # Kの上からi+1桁目を1=>0にすると考える
    # k_n+1桁目の場合はすべて同じ場合
    ret = 1
    for i in range(k_n+1):
        tmp1 = 0
        max_flg = False
        for j in range(max_a):
            if max_a - j == k_n - i:  # Kの対象桁を0とするパターン
                # 1だと0に変える、0だと0のまま
                tmp1 += bit_v[j] * cnt1[j]
                # 1=>0の時はフラグを付与
                if K_bit[j] == '1':
                    max_flg = True
            elif not max_flg:  # Kの各桁をそのままに使うパターン
                # K[j]が0だとcnt1[j]を、1だとN-cnt1[j]をかける
                tmp1 += bit_v[j] * (cnt1[j]**(1-int(K_bit[j]))) * ((N-cnt1[j])**(int(K_bit[j])))
            else:  # Kの前の桁で1=>0として、その後は最大になるようにとるパターン
                tmp1 += bit_v[j] * max(cnt1[j], N - cnt1[j])
        ret = max(ret, tmp1)
    return ret


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    print(run(N, K, A))


if __name__ == '__main__':
    main()


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

int main()
{
  char c;
  cin >> c;
  if(c >= 'A' && c <= 'Z'){
    cout << 'A' << endl;
  }
  else{
    cout << 'a' << endl;
  }
  return 0;
}


Measured memory_bytes: 3592
#include <stdio.h>

int main(){
  int N, i, j, ans;
  scanf("%d", &N);
  int A[N];
  double B=0.0;
  for(i=0; i<N; i++){
    scanf("%d", &A[i]);
    B += 1.0/(double)A[i];
  }
  
  printf("%.7f", 1.0/B);
  
  return 0;
}

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

signed main()
{
    long long n , r = 1 , two = 2;
    stack<int> s;

    cin >> n;

    if(n == 0){
        cout << "0\n";
    } else {
        while(n != 0){
            if(n % two != 0){
                n-=r;
                s.push(1);
            } else {
                s.push(0);
            }
            r = r * -2;
            two = two * 2;
        }

        while( !(s.empty()) ){
            cout << s.top();
            s.pop();
        }
        cout << endl;
    }

    return (0);
}

Measured memory_bytes: 3600
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

using namespace std;
#define ll long long
#define MOD 1000000007
#define INF (int)1e9+5
#define EPS 1e-9
/*
	Ok, I will learn dynamic programming properly :/
*/

int main(){
	ll n; cin>>n;
	vector<ll> dp(3);
	for(ll i=0;i<n;i++){
		vector<ll> temp(3,0),abc(3);
		for(ll j=0;j<3;j++){
			cin>>abc[j];
		}
		for(ll j=0;j<3;j++){
			for(ll k=0;k<3;k++){
				if(j!=k){
					temp[j]=max(dp[k]+abc[j],temp[j]);
				}
			}
		}
		dp=temp;
	}
	ll x=0;
	for(ll i=0;i<3;i++) x=max(x,dp[i]);
	cout<<x;
    return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<vector>
#include <algorithm>
#include<deque>
#include<queue>
#include<set>
#include <functional>
#include <cmath>


//マクロ
/*動かない・・・
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define REP(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _roverload3(_1,_2,_3,name,...) name
#define _rrep(i,n) repi(i,0,n)
#define rrepi(i,a,b) for(int i=int(a);i<int(b);++i)
#define RREP(...) _roverload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
//*/
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define REPS(i,n) for(int i=1; i<=(int)(n); ++i)
#define RREP(i,n) for(int i=(int)(n)-1; i>=0; --i)
#define RREPS(i,n) for(int i=(int)(n); i>0; --i)
#define FOR(i,s,e) for(int i=(int)(s); i<(int)(e); ++i)
#define RFOR(i,s,e) for(int i=(int)(e)-1; i>=(int)(s); --i)
//*/
#define All(a) (a).begin(),(a).end()
#define dump(x)  cerr << #x << " = " << (x) << endl;

//定数
#define INF 1e9
#define MOD (int)(1e9+7)

typedef long long ll;
typedef unsigned long long ull;
/*
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
//*/
using namespace std;

//とりあえず書いておく変数
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

//今回の変数
int n;
int h, w;
bool ans[80][80][6400];
int d[80][80];
deque<pair<int,int>> p;

//使用する関数
template<class T>bool chmax(T &a, const T &b) {
	if (a < b) { a = b; return 1; }
	return 0;
}
template<class T>bool chmin(T &a, const T &b) {
	if (a > b) { a = b; return 1; }
	return 0;
}

void bfs() {
	while(!p.empty()){
		pair<int, int> now = p.front();
		p.pop_front();
		int nh = now.first;
		int nw = now.second;
		if (nh != h - 1) {
			//printf("h nh+1=%d,nw=%d\n", nh+1, nw);
			REP(i, 6400) {
				if (ans[nh][nw][i]) {
					if (i + d[nh + 1][nw] < 6400) {
						ans[nh + 1][nw][i + d[nh + 1][nw]] = true;
						//printf("%d\n", i + d[nh + 1][nw]);
					}
					ans[nh + 1][nw][abs(i - d[nh + 1][nw])] = true;
					//printf("%d\n", abs(i - d[nh + 1][nw]));
				}
			}
			if (!p.empty()) {
				if (nw==0) {
					p.push_back(make_pair(nh + 1, nw));
				}
			}
			else {
				p.push_back(make_pair(nh + 1, nw));
			}
		}
		if (nw != w - 1) {
			//printf("w nh=%d,nw+1=%d\n", nh, nw+1);
			REP(i, 6400) {
				if (ans[nh][nw][i]) {
					if (i + d[nh][nw + 1] < 6400) {
						ans[nh][nw + 1][i + d[nh][nw + 1]] = true;
						//printf("%d\n", i + d[nh][nw + 1]);
					}
					ans[nh][nw + 1][abs(i - d[nh][nw + 1])] = true;
					//printf("%d\n", abs(i - d[nh][nw + 1]));
				}
			}
			p.push_back(make_pair(nh, nw + 1));
		}
	}

}

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

	REP(i, 80) {
		REP(j, 80) {
			REP(k, 6400) {
				ans[i][j][k] = false;
			}
		}
	}

	cin >> h>> w;
	int a[80][80], b[80][80];
	REP(i, h) {
		REP(j, w) {
			cin >> a[i][j];
		}
	}
	REP(i, h) {
		REP(j, w) {
			cin >> b[i][j];
			d[i][j] = abs(a[i][j] - b[i][j]);
		}
	}
	ans[0][0][d[0][0]] = true;
	p.push_back(make_pair(0, 0));
	bfs();

	REP(i, 6400) {
		if (ans[h - 1][w - 1][i]) {
			cout << i << endl;
			return 0;
		}
	}
}

Measured memory_bytes: 40448
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define mp make_pair
#define endl "\n"
#define tab " "
#define pb push_back
#define F first
#define S second
#define watch(x) cout<<(#x)<<" = "<<x<<" "
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define pll pair<ll,ll>
#define pi 3.141592653589793238460

using namespace std;

int main()
{
  int m,d,ones,tens;
  cin>>m>>d;
  int c=0;
  for(int i=1;i<=m;i++)
  {
    for(int j=22;j<=d;j++)
    {
      ones=j%10;
      tens=j/10;
      if(ones>=2 && tens>=2){
      if(ones*tens==i){
        c++;
        // cout<<i<<"-"<<j<<endl;
      }
      } 
    }
  }
  
  cout<<c<<endl;
}


Measured memory_bytes: 256
def main():
    N = input()
    A = list(map(int, input().split()))
    ans = 0
    a = A[0]
    len_A = len(A)
    for i in range(1,len_A):
        if a > A[i]:
            ans += a - A[i]
        else:
            a = A[i]
    print(ans)


if __name__ == '__main__':
    main()



Measured memory_bytes: 32292
import hashlib
import math

class BloomFilter:

    def __init__(self, num_item, false_positive):
        assert 0 <= false_positive <= 1
        # Optimal number of bit array size and hash function
        # https://en.wikipedia.org/wiki/Bloom_filter#Optimal_number_of_hash_functions
        log2 = math.log(2)
        logp = math.log(false_positive)
        size = - num_item * logp / (log2 * log2)
        num_hash = size / num_item * log2

        self.size = int(math.ceil(size))
        self.num_hash = int(math.ceil(num_hash))

        self.array = self.BitArray(self.size)
        self.hash_functions = [self.HashFunction(i, self.size)
                               for i in range(self.num_hash)]

    def add(self, item):
        for hash_func in self.hash_functions:
            i = hash_func(item)
            self.array[i] = True

    def __contains__(self, item):
        return self.contains(item)

    def contains(self, item):
        for hash_func in self.hash_functions:
            i = hash_func(item)
            if self.array[i] is False:
                return False
        return True

    class BitArray:

        def __init__(self, length):
            # Allocate an object per a bit for simplicity
            self.array = [False for _ in range(length)]

        def __getitem__(self, index):
            return self.get(index)

        def get(self, index):
            return self.array[index]

        def __setitem__(self, index, bit):
            return self.set(index, bit)

        def set(self, index, bit):
            if bit > 0 or bit is True:
                self.array[index] = True
            else:
                self.array[index] = False

    class HashFunction:

        def __init__(self, seed, maximum):
            self.seed = seed.to_bytes(
                seed.bit_length() // 8 + 1, byteorder='big')
            self.maximum = maximum

        def __call__(self, byte_buffer):
            return self.call(byte_buffer)

        def call(self, byte_buffer):
            # MD5 is enough because I don't want to oneway hash function
            b = hashlib.md5(byte_buffer + self.seed).digest()
            i = int.from_bytes(b, byteorder='big', signed=False)
            return i % self.maximum

N = int(input())
L = list(map(int,input().split()))
bf = BloomFilter(num_item=5 * 10 ** 5, false_positive=0.001)

L = sorted(L)
for i in range(len(L) - 1):
    if L[i] == L[i+1]:
        print("NO")
        quit()
print("YES")


Measured memory_bytes: 216020
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define ff               first
#define ss               second
#define pb               push_back
#define all(x)           (x).begin(), (x).end()
#define mem0(x)          memset(x, 0, sizeof (x))
#define mem1(x)          memset(x, -1, sizeof (x))

typedef long long ll;
#define int ll
typedef vector <int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector <ii> vii;
typedef vector<vii> vvii;
typedef vector <ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;

vvii g;
vi p, vls;
vi comp, comp_size;
vll total, vis, max_con_sum;

void dfs(int u, int rep){
    vis[u] = 1;
    comp[u] = rep;
    comp_size[rep]++;
    total[comp[u]] += vls[u];
    for (ii v: g[u]){
        if (!vis[v.ff]) dfs(v.ff, rep);
    }
}

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    p.resize(n+1);
    comp.resize(n+1);
    total.assign(n+1, 0);
    comp_size.assign(n+1, 0);
    vis.assign(n+1, 0);
    max_con_sum.assign(n+1, 0);
    vls.resize(n+1);
    g.assign(n+1,vii());
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
    }
    int maxi = -1000000000;
    for (int i = 1; i <= n; ++i) {
        cin >> vls[p[i]];
        maxi = max(vls[p[i]], maxi);
    }
    if (maxi <= 0){
        cout << maxi;
        return 0;
    }
    for (int j = 1; j <= n; ++j) {
        g[p[j]].pb({p[p[j]], vls[p[p[j]]]});
    }
    for (int k = 1; k <= n; ++k) {
        if (!vis[k]) dfs(k, k);
    }
    ll ans = 0;
    vis.assign(n+1,  0);
    for (int l = 1; l <= n; ++l) {
        if (vis[comp[l]]) continue;
        vis[comp[l]] = 1;
        for (int len = 1; len <= min(k, comp_size[comp[l]]); ++len) {
            int p1 = l, p2 = l;
            int sum = 0;
            for (int i = 0; i < len; ++i) {
                sum += vls[p2];
                p2 = g[p2][0].ff;
            }
            for (int j = 0; j <= comp_size[comp[l]]; ++j) {
                if (total[comp[l]] > 0) ans = max(ans, sum + (k-len)/comp_size[comp[l]] * total[comp[l]]);
                else ans = max(ans, sum);
                sum += vls[p2];
                p2 = g[p2][0].ff;
                sum -= vls[p1];
                p1 = g[p1][0].ff;
            }
        }
    }
    cout << ans << "\n";
}

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

class Mod{
    static final int MOD = 1000_000_007;
    static final long[] fact = makeFactorialArray(1000000);
    static final long[] factInv = makeInversedArray(fact);

    public static long add(long a, long b){
        long tmp = (a+b)%MOD;
        return tmp>=0 ? tmp : tmp+MOD;
    }
    public static long sub(long a, long b){
        return add(a,-b);
    }
    public static long mult(long a, long b){
        long tmp = (a*b)%MOD;
        return tmp>=0 ? tmp : tmp+MOD;
    }
    public static long power(long a, long x){ //calculate a^x
        if(x<0)return 0;
        if(x==0)return 1;
        if(x%2==0) {
            long half = power(a,x/2);
            return mult(half,half);
        }
        return (a*power(a,x-1)) % MOD;
    }
    public static long inverse(long a){
        return power(a,MOD-2);
    }
    public static long div(long a, long b){
        return mult(a, inverse(b));
    }
    public static long[] makeFactorialArray(int size){
        long[] array = new long[size];
        array[0]=1;
        for(int i=1;i<size;i++){
            array[i]=mult(array[i-1],i);
        }
        return array;
    }
    public static long[] makeInversedArray(long[] original){
        long[] array = new long[original.length];
        for(int i=0;i<original.length;i++){
            array[i] = inverse(original[i]);
        }
        return array;
    }
    public static long combination(int n, int r){
        if(n<0 || r<0 || n<r) return 0;
        return mult(fact[n], mult(factInv[r],factInv[n-r]));
    }
    public static long gcd(long a, long b){
        if(a<b) return gcd(b,a);
        if(b==0) return a;
        if(a%b==0) return b;
        return gcd(b,a%b);
    }
    public static long lcm(long a, long b){
        return (a/gcd(a,b))*b;
    }

    public static List<Long> divisors(long N){
        LinkedList<Long> ans = new LinkedList<>();
        for(long n = (long)Math.sqrt(N)+1; n>0; n--){
            if(n*n>N) continue;
            if(n*n==N) ans.add(n);
            else if(N%n==0){
                ans.addFirst(n);
                ans.addLast(N/n);
            }
        }
        return ans;
    }

}

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();
        long D = Mod.gcd(A,B);

        List<Long> div = Mod.divisors(D);
        System.out.println(div.get(div.size()-K));
    }
}

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

int main(){
    int a, b, c, x; cin >> a >> b >> c >> x;
    int ans = 0;
    for(int i = 0; i <= a; i++) {
        for(int j = 0; j <= b; j++) {
            for(int k = 0; k <= c; k++) {
                if((500*i+100*j+50*k)==x) ans++;
            }
        }
    }
    cout << ans << endl;
}

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

// #define int long long

signed main(void) {
  int num; // num
  num = 0; // count, result
  // num = numeric_limits<int>::min(); // max
  // num = numeric_limits<int>::max(); // min
  int N;
  int M;
  
  array<int, 100000> P;
  array<int, 100000> Y;
  array<vector<int>, 100001> YD;

  cin >> N >> M;

  for (int i = 0; i < M; i++) {
    cin >> P[i] >> Y[i];
    YD[P[i] - 1].push_back(Y[i]);
  }

  for (int i = 0; i < N; i++) {
    sort(YD[i].begin(), YD[i].end());
  }
  
  for (int i = 0; i < M; i++) {
    cout << setfill('0') << setw(6) << right << P[i]
         << setfill('0') << setw(6) << right << (lower_bound(YD[P[i] - 1].begin(), YD[P[i] - 1].end(), Y[i]) - YD[P[i] - 1].begin()) + 1 << endl;
  }
  
  return 0;
}


Measured memory_bytes: 7808
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

char* gen_10_bits(int len){
	int i;
	char* bit_s;

	bit_s = (char *)malloc(sizeof(char)*len);

	for(i=0; i < len; i++){
		bit_s[i] = i%2 == 0 ? '1':'0';
	}

	return bit_s;
}

char* gen_01_bits(int len){
	int i;
	char* bit_s;

	bit_s = (char *)malloc(sizeof(char)*len);

	for(i=0; i < len; i++){
		bit_s[i] = i%2 == 1 ? '1':'0';
	}

	return bit_s;
}

int hamm_dist(char *s0, const char *s1, const char * s2){
	int n;

	if(!*s1 && !*s2){
		*s0 = '\0';
		return 0;
	}
	
	if(!*s1 || !*s2 || (n = hamm_dist(s0 + 1, s1 + 1, s2 + 1)) == -1) return -1;
	if(*s1 == *s2) *s0 = ' ';
	else{
		*s0 = '|';
		++ n;
	}
	return n;
}
 
int main(void){
	int A,B;
	int i;
	int l;
	int flag_msb_0 = 0;
	int res1,res2;

	char N[1000000];
	char s[1000000];
 
 	scanf("%s", N);

 	/*
 	if(list[0] == '0'){
 		flag_msb_0 = 1;
 	}
 	*/

 	l = strlen(N);

 	res1 = hamm_dist(s, gen_01_bits(l), N);
 	res2 = hamm_dist(s, gen_10_bits(l), N);

 	if(res1 < res2){
		printf("%d\n", res1);
	}else{
		printf("%d\n", res2);
	}
 
	return 0;
}

Measured memory_bytes: 3712
import fractions
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

count=a[0]
for i in range(n-1):
    count=lcm(count,a[i+1])
ans=0
for i in range(n):
    ansa=count//a[i]
    ans+=ansa
    
print(ans%mod)

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

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Set<String> set = new HashSet<String>();

        for (int i=0; i<n; ++i) {
            String dir = sc.next();
            String s = sc.next();
            if (dir.equals("insert")) {
                set.add(s);
            } else {
                System.out.println((set.contains(s) ? "yes" : "no"));
            }
        }
        sc.close();
    }
}



Measured memory_bytes: 253620
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(x) cerr << #x << " = " << x << endl


int main(int qtd, char* nome[])
{
	ios::sync_with_stdio(false);
	cin.tie(0);
 
	ll n, k;
	cin >> n >> k;
	cout << min(n, min(k-n%k, n%k)) << endl;
	
	return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")

#define rep(i,n) for(int i = 0;i<n;i++)
const long long MOD = 1000000007;

int main(){
  int n; cin >> n;
  long long fib[n+1];
  fib[0] = 1; fib[1] = 1;
  for(int i = 2; i<=n;i++){
    fib[i] = fib[i-1] + fib[i-2];
  }
  cout << fib[n] << "\n";
}



Measured memory_bytes: 3120
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int y = sc.nextInt();
		int answer1 = x*y;
		int answer2 = (x+y)*2;
	System.out.println(answer1 +" "+answer2);
	}
}


Measured memory_bytes: 26204
n = int(input())
robots = [list(map(int,input().split())) for _ in range(n)]

robots.sort()

max_point = 0
count = 0

for i,elem in enumerate(robots):
    if i == 0:
        max_point = elem[0]+elem[1]
        prev_elem = elem
    else:
        if max_point <= elem[0]-elem[1]:
            max_point = elem[0] + elem[1]
            prev_elem = elem
        else:
            count += 1
            if max_point >= elem[0] + elem[1]:
                max_point = elem[0] + elem[1]
                prev_elem = elem

print(n-count)

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

int M;
int bit[1000010];
void add(int a, int w){
    for(int x = a; x <= M; x += x & -x) bit[x] += w;
}
int sum(int a){
    int ret = 0;
    for(int x = a; x > 0; x -= x & -x) ret += bit[x];
    return ret;
}


pair<int, int> lr[300000];
pair<int, int> dn[300000];

int main(){
    int N;
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        cin >> lr[i].first >> lr[i].second;
        dn[i].first = lr[i].second - lr[i].first + 1;
        dn[i].second = i;
    }
    sort(dn, dn+N);
    int cntLessThanD = 0;
    for(int d = 1; d <= M; d++){
        while(cntLessThanD < N && dn[cntLessThanD].first < d){
            int n = dn[cntLessThanD].second;
            add(lr[n].first, 1);
            add(lr[n].second + 1, -1);
            cntLessThanD++;
        }
        int ans = 0;
        for(int i = 1; i * d <= M; i++){
            ans += sum(i * d);
        }
        ans += N - cntLessThanD;
        cout << ans << endl;
    }
}


Measured memory_bytes: 7040
//AUTHOR:- Avinash//
#include<iostream>
using namespace std;
#define ll long long int
#define lll long long
#define fo(i,n) for(int i=0;i<n;i++)
#define take(a,i,n) for(int i=0;i<n;i++) cin>>a[i]
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ld long long double
#define d1(x) cout<<(x)<<endl
#define T int t;cin>>t;while(t--)
#define hell 1000000007
#define ex endl;
#define F first
#define maxn 200001
#define pi 3.14159265
#define S second
#define P pair<int,int>
#define PP pair<int,pair<int,int>>
#define pb push_back
#define in insert
#define vec vector<ll>
#define vec2 vector<vector<int>>
#define s(a,n) sort(a,a+n);
#define sv(a) sort(a.begin(),a.end());
#define MAX 1000
//Author:-Avinash//

ll power(ll x, ll y, ll m)
{
    if (y == 0)
        return 1;
    ll p = power(x, y/2, m) % m;
    p = (p * p) % m;
    return (y%2 == 0)? p : (x * p) % m;
}
ll sum_of_natural_no(ll n )
{
    return (n *(n+1))/2;
}

ll modInverse(ll a, ll m)
{
    return power(a, m-2, m);
}
int main(){
   FAST
   int x;
   cin>>x;
   if(x==0)
   {
    cout<<"1"<<endl;
   }
   if(x==1)
   {
    cout<<"0"<<endl;
   }
   return 0;
}

Measured memory_bytes: 3088
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<string.h>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int, int>P;

int main() {
	int n;
	cin >> n;
	int a;
	ll sum = 0;
	int count = 0;
	int mina = 1000000009;
	for (int i = 0; i < n; i++) {
		cin >> a;
		if (a < 0) {
			a *= -1;
			count++;
		}
		sum += a;
		mina = min(a, mina);
	}
	if (count % 2 == 1) {
		cout << sum - mina * 2 << endl;
	}
	else {
		cout << sum << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  string S;
  cin >> N >> S;
  
  vector<pair<int, char>> alp;
alp = {make_pair(0, 'A')
, make_pair(1, 'B')
, make_pair(2, 'C')
, make_pair(3, 'D')
, make_pair(4, 'E')
, make_pair(5, 'F')
, make_pair(6, 'G')
, make_pair(7, 'H')
, make_pair(8, 'I')
, make_pair(9, 'J')
, make_pair(10, 'K')
, make_pair(11, 'L')
, make_pair(12, 'M')
, make_pair(13, 'N')
, make_pair(14, 'O')
, make_pair(15, 'P')
, make_pair(16, 'Q')
, make_pair(17, 'R')
, make_pair(18, 'S')
, make_pair(19, 'T')
, make_pair(20, 'U')
, make_pair(21, 'V')
, make_pair(22, 'W')
, make_pair(23, 'X')
, make_pair(24, 'Y')
, make_pair(25, 'Z')};
  
  string S_ans = "";
  for(char c : S){
    int num;
    for(auto a : alp){
      if(a.second == c){
        num = a.first;
      }
    }
    num += N;
    if(num >= 26){
      num -= 26;
    }
    S_ans += alp.at(num).second;
  }
  
  cout << S_ans << endl;
}

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

inline unsigned int _Int() {
        char c = getchar();
        while (c < '0' || c > '9')c = getchar();
        unsigned x = (c - '0');
        while ((c = getchar()) >= '0' && c <= '9')x = ((x << 3) + (x << 1)) + c - '0';
        return x;
}
/**
MO's Algorithm
Given an array of N integers and Q intervals
In each interval how many distinct values are there
**/
const int M = 5 * 1e5 + 7; /// maximum array size

int n, qryC;
int A [ M ];
int blockSize;

struct interval {
        int index;
        int u, v;
        void set(int a, int b, int c) {
                index = a, u = b, v = c;
        }
        bool operator < (const interval &R) const {
                int b1 = u / blockSize, b2 = R.u / blockSize;
                if ( b1 != b2 ) return (b1 < b2);
                return v < R.v;
        }
} q[ M ];

int fr[ 1000000 + 7 ];

int distinctValues;
void element(int x, int f) /// f{1,-1} = add or remove flag
{
        fr[ x ] = fr[ x ] + f;
        if ( f == +1 && fr[x] == 1 ) distinctValues++;
        if ( f == -1 && fr[x] == 0 ) distinctValues--;
}
int Ans[ M ];

void Main()
{
        n = _Int();
        blockSize = sqrt(n + 1);
        qryC = _Int();
        for (int i = 1; i <= n; i++) A[i] = _Int();
        for (int i = 0, u, v; i < qryC; i++) {
                u = _Int();
                v = _Int();
                q[i].set(i, u, v);
        }
        sort( q, q + qryC );
        int left = 0, right = 0;
        distinctValues = 0;
        for (int x = 0; x < qryC; x++) {
                while ( right < q[x].v ) element( A[ ++right ],  1 );
                while ( right > q[x].v ) element( A[ right-- ], -1 );
                while ( left  < q[x].u ) element( A[ left++ ],  -1 );
                while ( left  > q[x].u ) element( A[ --left ],   1 );
                Ans[ q[x].index ] = distinctValues;
        }
        for (int i = 0; i < qryC; i++) {
                printf("%d", Ans[i] );
                putchar(10);
        }
}
int main()
{
#ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
#endif
        Main();
        return 0;
}

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

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

    int res = 0;
    for (int i = 1; i <= x/100; i++) {
        if (100*i <= x && x <= 105*i) res = 1;
    }

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 3612
#include <stdio.h>

int main(void){
    int h, n;
    int a[100000];
    int i,sum;
    
    scanf("%d %d", &h, &n);
    sum = 0;
    for(i = 0; i < n; i++){
        scanf("%d", &a[i]);
        sum += a[i];
    }
    
    if(sum >= h){
        puts("Yes");
    }else{
        puts("No");
    }
    
    return 0;
}

Measured memory_bytes: 512
import sys
import bisect
from functools import lru_cache
from collections import defaultdict
import itertools
inf = float('inf')
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
#def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
h,w,k1=reads()
c=[]
for i in range(h):
  c.append(input())
res=0
for i in range(2**h):
  for j in range(2**w):
    selrows,selcolumn=[],[]
    k=0
    s=i
    while(True):  
      if s==0:
        break
      if s%2==1:
        selrows.append(k)  
      s//=2
      k+=1
    k=0
    t=j
    while(True):  
      if t==0:
        break
      if t%2==1:
        selcolumn.append(k)     
      t//=2
      k+=1
    blacknumber=0
    for k in range(h):
      for l in range(w):
        if c[k][l]==".":
          continue
        elif k in selrows or l in selcolumn:
          continue
        else:
          blacknumber+=1

    if blacknumber==k1:
      res+=1
print(res)


Measured memory_bytes: 69596
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
const long long INF = 1LL << 60;
int main() 
{
    int A, B, C;
    int q[5];

    std::priority_queue<long long> Q;
  
    rep(i,3){
        cin >> q[i];
        Q.push(q[i]);
    }

    A = Q.top();
    Q.pop();
    B = Q.top();
    Q.pop();
    C = Q.top();

    if(A%2 == (C+A-B)%2){
        cout << A-B + (B-C)/2 << endl;
    }
        else
        {
            cout << A-B + 1 + (B-C+1)/2 << endl;
        }
        
}

Measured memory_bytes: 256
/*
digu_J - Digvijay Janartha
NIT Hamirpur - INDIA
 
***********************IN COLABRATION WITH -----AJrockstar   :)*********************
*/
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
 
using namespace std;
using namespace __gnu_pbds;
 
//template<typename T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
//template<typename T> using MinPriorityQueue = priority_queue <T, vector <T>, greater <T>>;
 
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef complex<double> com;
 
#define eb emplace_back
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define loop(x,n) for(ll x = 0; x < n; x++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define unique_sort(x) (sort(x.begin(), x.end()), x.resize(distance(x.begin(), unique(x.begin(), x.end()))))
#define fast_io() ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
const ll LINF = LLONG_MAX, SZ = 1e3, MOD = 1e9 + 7, N = 1e5 + 5, M = 1e3 + 5, LG = 21;
const int INF = INT_MAX;
const db PI = acos(-1), EPS = 1e-6;
//mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
 
 
 
 
 ll w=1000000;
 ll isPrime[1000000+1];
int main() {
	
    fast_io();
    ll i,j,t,n,p,k,q,o,ca=0,cb=0,x,y,c,s;
    
    
    cin>>n>>k;
    
    ll a[n],dp[n+1];
    for(j=0;j<n;j++)
    {
    	cin>>a[j];	
    }
    dp[0]=0;
   // dp[1]=abs(a[0]-a[1]);
    
    for(i=1;i<n;i++)
    {
    	p=dp[i-1]+abs(a[i]-a[i-1]);
    	for(j=i-2;j>=i-k&&j>=0;j--)
    	{
    		p=min(p,dp[j]+abs(a[i]-a[j]));
		}
		//cout<<p<<" ";
		dp[i]=p;
	}
	
	cout<<dp[n-1];
    
    return 0;
}
 
 

Measured memory_bytes: 1792
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>

#include <bits/stdc++.h>
#include <cmath>
#include <limits>

using namespace std;

int C[502] = {0};
int S[502] = {0};
int F[502] = {0};

long long wt(int i, long long t){
	long long ret;
	if(t <= S[i]){
		ret = S[i] - t;
	}
	else{
		ret = F[i] - ((t % F[i]) % F[i]) ;
		ret = ret % F[i] ;
	}
	return ret;
}

int main(int argc, char* argv[]){
	int N;

	cin >> N;
	for(int i=1; i<=N-1; i++){
		cin >> C[i] >> S[i] >> F[i] ;
	}

	long long t = 0;
	for(int i=1; i<=N; i++){
		t = 0;
		for(int j=i; j<=N-1; j++){
			t += wt(j, t);
			t += C[j];
		}
		cout << t << endl;
	}
	return 0;
}

Measured memory_bytes: 256
A, B = map(int, input().split())
ans = 0
for num in range(A,B+1,1):
    target = str(num)
    index, _ = divmod(len(target),2)
    count = 0
#     print(index)
    for i in range(index):
        if target[i] == target[-i-1]:
            count += 1
            if count == index:
                ans += 1
#                 print(target)
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cout << x;}
void __print(long x) {cout << x;}
void __print(long long x) {cout << x;}
void __print(unsigned x) {cout << x;}
void __print(unsigned long x) {cout << x;}
void __print(unsigned long long x) {cout << x;}
void __print(float x) {cout << x;}
void __print(double x) {cout << x;}
void __print(long double x) {cout << x;}
void __print(char x) {cout << '\'' << x << '\'';}
void __print(const char *x) {cout << '\"' << x << '\"';}
void __print(const string &x) {cout << '\"' << x << '\"';}
void __print(bool x) {cout << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cout << '{'; __print(x.first); cout << ','; __print(x.second); cout << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __print(i); cout << "}";}
void _print() {cout << "\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
#define debug(x...) cout << #x << " = "; _print(x)
typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll;
#define rep(i,a,b) for (ll i = (a); i < (b); ++i)
#define per(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define all(x) begin(x), end(x)
#define mp make_pair 
#define pb push_back
#define ff first
#define ss second
#define fast ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL) 

int solve(){
	string a, b;
	cin>> a>> b;
	if(b.substr(0, a.size()) == a)
		cout<< "Yes\n";
	else
		cout<< "No\n";
	return 0;
}
 
int main()
{
	fast;
	int t = 1;
	//cin>> t;
	while(t--){  
		solve();
	}
	return 0;
}
//v.clear(), vis.clear(); vis.resize(n + 1, 0), v.resize(n + 1);
 
/*	inv[1] = 1; // inv is ll
	for(int i=2; i<=mxn; ++i)
		inv[i]=mod-mod/i*inv[mod%i]%mod;*/


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

int main() {
    int n;
    cin>>n;
    vector<int> a(n);
    rep(i,n){
        cin>>a[i];
    }
    for(int i=n-1; i>0; i--){
        printf("%d ", a[i]);
    }
    printf("%d\n", a[0]);
    return 0;
    
   
}



Measured memory_bytes: 3204
n, k = gets.chomp.split(" ").map(&:to_i)
k = k-1
ary = []
n.times do |i|
  ary << gets.chomp.to_i
end
ary.sort!
sa = []
ary.count.times do |i|
  if ary.count <= i+k
    break
  end
  sa << ary[i+k] - ary[i] 
end
puts sa.min

Measured memory_bytes: 4328
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int x; cin>>x;
	if (x==7||x==5||x==3) cout<<"YES";
	else cout<<"NO"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int i,j,n,m,mas[200005],rez,l;
map<int,int> ab;
int main()
{
    std::cin.sync_with_stdio(false);
    std::cin.tie(0);
    cin >> n;
    i=0;
    while (i<n)
    {
        cin >> mas[i];
        i++;
    }
    i=0;
    while (i<n)
    {
        ab[mas[i]]=max(ab[mas[i]-1]+1,ab[mas[i]]);
        //rez=max(rez,ab[mas[i]]);
        if (ab[mas[i]]>rez)
        {
            rez=ab[mas[i]];
            l=mas[i];
        }
        //cout << i << " " << mas[i] << " " << ab[mas[i]] << "\n";
        i++;
    }
    cout << n-rez << "\n";
    return 0;
}


Measured memory_bytes: 11960
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define vvll vector<vll>
#define all(v) v.begin(),v.end()
#define itr(r,v) for(auto r=v.begin();r!=v.end();r++)
#define W while
#define FOR(i,n) for(ll i=0;i<n;i++)
#define ffor(i,a,b) for(ll i=a;i<=b;i++)
#define rfor(i,a,b) for(ll i=a;i>=b;i--)
#define space cout<<"\n\n";
#define endl "\n"
#define pqmx priority_queue<ll>
#define pqmn priority_queue<ll,vll,greater<ll>>
#define fps(x,y) fixed<<setprecision(y)<<x
#define merg(a,b,c) set_union(a.begin(),a.end(),b.begin(),b.end(),inserter(c,c.begin()))
#define set_ar(arr,v) memset(arr,v,sizeof(arr))
#define ctime auto start = high_resolution_clock::now()
#define etime auto stop = high_resolution_clock::now()
#define ptime auto z1z = duration_cast<microseconds>(stop-start); cout<<"Time elapsed : "<<z1z.count()<<" microseconds\n"
#define go_t ll testcases; cin>>testcases; while(testcases--)
#define dbg1(x)             cout <<#x<<": "<<x<<'\n';
#define dbg2(x, y)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<'\n';
#define dbg3(x, y, z)       cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<'\n';
#define dbg4(a, b, c, d)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<'\n';
#define dbg5(a, b, c, d, e) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<<": "<<e<<'\n';
using namespace std;
using namespace std::chrono;

const ll MOD = 1e9 + 7;
const ll N = 2005;
const ll maxN = 1e5 + 5;
const ll MAX_SIZE = 1e8 + 8;

ll power(ll x, ll y, ll M = MOD) // default argument
{ll v = 1; x = x % M; while (y > 0) {if (y & 1)v = (v * x) % M; y = y >> 1; x = (x * x) % M;} return v;}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("input2.txt", "r", stdin);
	freopen("output2.txt", "w", stdout);
#endif
	// WHILE(!(SUCCEED == TRY()));
	// BEFORE WRITING MAKE SURE YOU HAVE ANALYSED THE CONSTRAINTS
	// AND THINK THROUGH THE LOGIC ONCE MORE
	FIO
	ll n; cin >> n;
	map<ll, ll> ar;
	ll sum = 0;
	FOR(i, n) {
		ll x;
		cin >> x;
		ar[x]++;
		sum += x;
	}
	//
	//
	ll q; cin >> q;
	W(q--) {
		ll b, c; cin >> b >> c;
		ll kk = ar[b];
		// dbg1(kk);
		if (kk == 0) cout << sum << "\n";
		else {
			sum -= (kk * b);
			sum += (kk * c);
			cout << sum << "\n";
			ar.erase(b);
			ar[c] += kk;
		}
	}
	return 0;
}


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

using namespace std;
const int INF=1e9+5;
const int MOD=1e9+7;
typedef long long ll;

int main(){
	int n;
	cin>>n;
	double a[n];
	for(int i=0;i<n;i++)
		cin>>a[i];
	double dp[n+1][n+1];
	for(int i=1;i<=n;i++)
		dp[0][i]=0;
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=n;j++){
			if(j>i)  dp[i][j]=0;
			else if(j==0)  dp[i][j]=dp[i-1][j]*(1-a[i-1]);
			else {
				dp[i][j]=dp[i-1][j-1]*a[i-1]+dp[i-1][j]*(1-a[i-1]);
			}
		}
	}
	cout<<endl;
	double sum=0;
	for(int i=ceil((float)n/2);i<=n;i++)
		sum+=dp[n][i];
	printf("%0.10f\n",sum);
	} 

Measured memory_bytes: 70528
#include<bits/stdc++.h>
#define vll vector<ll>
#define vi vector<int>
#define vpll vector<pair<ll,ll>>
#define pii pair<int,int>
#define REP(i,a) for(int (i)=0; (i)<(a); (i)++)
#define RREP(i,a) for(int (i)=a-1; (i)>=(0); (i)--)
#define REP2(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
#define m0(x) memset(x,0,sizeof(x))
typedef long long ll;

using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int N;
  cin >> N;
  double ans = 1.0 - (double)((int)(N/2))/N;
  cout << setprecision(8) << ans << endl;

  return 0;
}

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

using namespace std;
//using namespace atcoder;
using usize = ::std::size_t;
using u64 = ::std::int_least64_t;
//using u64 = long long;
static constexpr u64 Inf = ::std::numeric_limits<u64>::max() / 2;

int getrandmax() {
    static uint32_t y = time(NULL);
    y ^= (y << 13); y ^= (y >> 17);
    y ^= (y << 5);
    return abs((int)y);
}
int getrand(int l, int r) { // [l, r]
    return getrandmax() % (r - l + 1) + l;
}


int main(int argc, char *argv[])
{
    
    
    cin.tie(0) ;
    ios::sync_with_stdio(false) ;
    
    int n;
    cin >> n;
    vector<int> A(n), B(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> B[i];
    }
    sort(B.begin(), B.end(), greater<int>());
    
    int i = 0;
    bool found = false;
    while (i < n && clock() < 1.95 * CLOCKS_PER_SEC) {
        if (A[i] == B[i]) {
            int j = getrand(i, n - 1);
            if (B[j] == B[i]) {
                j = getrand(0, i);
                if(B[j] != A[i] && B[i] != A[j]){
                    swap(B[i], B[j]);
                }
            } else {
                swap(B[i], B[j]);
            }
            i--;
        }
        i++;
        found = (i == n);
    }
    
    if (found) {
        cout << "Yes" << endl;
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                cout << B[i];
            } else {
                cout << " " << B[i];
            }
            if(i == n - 1){
                cout << endl;
            }
        }
    } else {
        cout << "No" << endl;
    }
    
    
    return 0;
    
}


Measured memory_bytes: 4756
#include<iostream>
#include<string>
using namespace std;
int main(){
 long long  cnt=1,h[200]={};
  string a;
  cin>>a;
  for(int i=0;i<a.size();i++)h[a[i]]++;
  for(int i=0;i<200;i++)for(int j=i+1;j<200;j++)if(i!=j)cnt+=h[i]*h[j];
  cout<<cnt;
  return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<cstdlib>
#include<vector>
#include<set>
#include<deque>
#include<queue>
#include<math.h>
#include<chrono>
#include<list>
#include<random>
#include<bitset>
#include<assert.h>
#include<ctime>
#include<cstdio>
#include <unordered_map>

using namespace std;

#define fast_input() {ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); }
//#define ll long long
using ll = long long;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/*
MIKUNO - 15/02/1999
*/
const int N = 1e5 + 5;
//	priority_queue <ll, vector<ll>, greater<ll> > q;
//int n, m, k, cnt, rs, q;

int main()
{
	fast_input();
	int n, W;
	cin >> n >> W;
	vector<ll>dp(W + 1, 0);
	for (int i = 0; i < n; ++i) {
		int w, v;
		cin >> w >> v;
		for (int weight = W - w; weight >= 0; --weight) {
			dp[weight + w] = max(dp[weight + w], dp[weight] + v);
		}
	}
	cout << dp[W];
}

Measured memory_bytes: 1024
#include<iostream>
#include<cstring>
#include<cstdio>
#define MN 2000
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char s[MN+5][MN+5];
int r[MN+5],n,m,ans,top;
pair<int,int> q[MN+5];
int main()
{
    n=read();ans=m=read();
    for(int i=1;i<=n;++i) scanf("%s",s[i]+1);
    for(int i=1;i<=m;++i)
    {
        q[top=1]=make_pair(1,0);
        for(int j=2;j<=n;++j)
        {
            r[j]=r[j]>=i?r[j]:i;int stat=s[j][i]!=s[j-1][i];
            while(r[j]<m&&((s[j-1][r[j]+1]==s[j][r[j]+1])^stat)) ++r[j];
            int len=r[j]-i+1;
            while(top&&len<=q[top].second) ans=max(ans,(j-q[top-1].first)*q[top].second),--top;
            q[++top]=make_pair(j,len);
        }
        while(top) ans=max(ans,(n-q[top-1].first+1)*q[top].second),--top;
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 4224
// 基本テンプレート

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long int

template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}

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

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
constexpr ll INF = 1001001001001001LL;
constexpr ll MOD = 1000000007LL;

signed main() {
    int N, K; cin >> N >> K;
    vector<pii> v;
    rep(i,0,N) {
        int a, b; cin >> a >> b;
        v.push_back(pii(a, b));
    }
    sort(v.begin(), v.end());

    int cnt = 0;
    rep(i,0,N) {
        if(cnt + v[i].second >= K) {
            cout << v[i].first << endl;
            return 0;
        }
        cnt += v[i].second;
    }
    return 0;
}

Measured memory_bytes: 2420
from sys import stdin


def main() -> None:
    a = next_int()
    b = next_int()

    ab = int(str(a) + str(b))
    sqrt = int(ab ** 0.5)

    print("Yes" if sqrt ** 2 == ab else "No")


def next_int() -> int:
    return int(next_str())


def next_str() -> str:
    result = ""
    while True:
        tmp = stdin.read(1)
        if tmp.strip() != "":
            result += tmp
        elif tmp != '\r':
            break
    return result


if __name__ == '__main__':
    main()

Measured memory_bytes: 3188
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

r = INT()

print(r**2)

Measured memory_bytes: 61804
def main():
    import sys
    import copy
    input = sys.stdin.readline
    H, W, K = [int(x) for x in input().strip().split()]
    C = [[0] * W for h in range(H)]
    sum_ = 0
    for h in range(H):
        C[h] = list(input().strip())
        sum_ += sum([1 if s == '#' else 0 for s in C[h]])

    ans = 0
    for i in range(2**H):
        sum_t = sum_
        D = copy.deepcopy(C)
        for ii in range(H):
            if (i >> ii) % 2:
                for c in range(W):
                    if D[ii][c] == '#':
                        sum_t -= 1
                        D[ii][c] = '.'
        if sum_t < K:
            continue
        # print(D)
        for j in range(2**W):
            E = copy.deepcopy(D)
            sum_t2 = sum_t
            for jj in range(W):
                if (j >> jj) % 2:
                    for c in range(H):
                        if E[c][jj] == '#':
                            sum_t2 -= 1
                            E[c][jj] = '.'
            # print('i={}, j={}, sum_t={}, sum_t2={}'.format(i, j, sum_t, sum_t2))
            # for t in range(H):
            #     print(E[t])
            if sum_t2 == K:
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()

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

int N;
long long C[100000];

int main(){
  std::cin>>N;
  long long ans=0;
  for(int i=0;i<N;++i){
    long long a,b;
    std::cin>>a>>b;
    C[i]=a+b;
    ans-=b;
  }
  std::sort(C,C+N);
  for(int i=N-1;i>=0;i-=2){
    ans+=C[i];
  }
  std::cout<<ans<<std::endl;
  return 0;
}


Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.UncheckedIOException;
import java.util.StringTokenizer;

class Main{
	public static void main(String[] args) {
		SC sc=new SC(System.in);
		int N=sc.nextInt();
		long[] As=new long[N];
		long[] Bs=new long[N];
		int[] jyunjyo=new int[N];
		for(int i=0; i<N; i++) {
			As[i]=((long)(i+1))*30000;
			Bs[i]=((long)(N-i))*30000;
		}
		for(int i=0; i<N; i++) {
			jyunjyo[i]=sc.nextInt()-1;
		}
		for(int i=0; i<N; i++) {
			Bs[jyunjyo[i]]+=i;
		}
		for(int i=0; i<N-1; i++) {
			p(As[i]+" ");
		}
		pl(As[N-1]);
		for(int i=0; i<N-1; i++) {
			p(Bs[i]+" ");
		}
		pl(Bs[N-1]);
	}
	static class SC {
		private BufferedReader reader = null;
		private StringTokenizer tokenizer = null;
		public SC(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
		}
		public String next() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
	}
	public static void pl(Object o) {
		System.out.println(o);
	}
	public static void p(Object o) {
		System.out.print(o);
	}
}

Measured memory_bytes: 32232