akhauriyash/Code-Regression huggingface dataset:
N = int(input())
sX = input()

origin_count = sX.count('1')
one_r_count = origin_count -1
zero_r_count = origin_count +1

one_mod = 0
zero_mod =0
for b in sX:
    if one_r_count != 0:
        one_mod = (one_mod * 2 + int(b) )% one_r_count
    zero_mod = (zero_mod * 2  + int(b) )% zero_r_count

f = [0] * 220000
pop = [0]* 220000

for i in range(1,220000):
    pop[i] = pop[i//2] + i % 2
    f[i] = f[i % pop[i]] + 1

onepow = [1] * 220000
zeropow = [1]* 220000

for i in range(1,220000):
    if one_r_count != 0:
        onepow[i] = onepow[i-1] * 2 % one_r_count
    zeropow[i] = zeropow[i-1] * 2 % zero_r_count

for i in range(1,N+1):
    if sX[i-1] == '1':
        if one_r_count != 0:
            Xi_n = one_mod - onepow[N-i]
            Xi_n %= one_r_count
            print(f[Xi_n]+1)
        else:
            print(0)
    else:
        Xi_n = zero_mod + zeropow[N-i]
        Xi_n %= zero_r_count
        print(f[Xi_n]+1)

        

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

int main(void){
	int i,j,n=0;
	long long int A[200001];
	long long int t,p;

	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%lld",&A[i]);
	}
	p=n;
	t=A[0];
	i=0;
	j=1;
	while(j<n){
		while((t+A[j])==(t^A[j])&&j<n){
			t^=A[j];
			j++;
		}
		while((t+A[j])!=(t^A[j])||(j==n)&&(i<j)){
			t^=A[i];
			i++;
			p+=(long long int)(j-i);
		}
	}

	printf("%lld\n",p);

	return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
//const int N = 1000000;
const ll mod = 1000000007;
using Graph = vector<vector<int>>;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
  
ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}
ll lcm(ll A, ll B){
    return A * (B / gcd(A, B));
}
  
/*------------------------------------------------------------------*/
int main(){
    ll x, a, b; cin >> x >> a >> b;
    if(b - a <= 0) cout << "delicious" << endl;
    else if(b - a <= x)cout << "safe" << endl;
    else if(b - a > x)cout << "dangerous" << endl;
}

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

using namespace std;

typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;

constexpr int MAXNM = 100000;

char S[MAXNM + 2], T[MAXNM + 2];

int main() {
	int N, M;
	cin >> N >> M >> S >> T;
	int g = __gcd(N, M);
	for(int i = 0, j = 0; i < N; i += N / g, j += M / g)
		if(S[i] != T[j])
			goto imp;
	cout << ((ll)N * M / g) << endl;
	return 0;
imp:
	cout << -1 << endl;
}


Measured memory_bytes: 384
#include <stdio.h>

void sort(int x[]){

  int i, j, temp;
  int n = 5;

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

  }
}


int main(void)
{
  int a[20];
  char ch[50];
  int i;


  fgets(ch, 50, stdin);

  sscanf(ch, "%d %d %d %d %d\n", &a[0],&a[1],&a[2],&a[3],&a[4]);
  sort(a);

  for(i = 0; i < 4; i++){
	printf("%d ", a[i]);
  }
  printf("%d", a[4]);
  printf("\n");

  return 0;


}

Measured memory_bytes: 612
#include <stdio.h>
#include <math.h>
#define N 10000
#define T 1
#define F 0

int isprime(int x){
	
	int i;
	
  if (x == 2){
    return T;
    }

  if (x < 2 || x % 2 ==0){
    return F;
    }
    
    i=3;

  while (i <= sqrt(x)){
    if( x % i ==0) return F;
    
     i+= 2;
}
 return T;
  	
}

int main(){
	int i,n,sum=0;
	int a[N];

	scanf("%d",&n);
	
	for(i=0;i<n;i++) scanf("%d",&a[i]);
	
	for(i=0;i<n;i++) sum+=isprime(a[i]);
	
	printf("%d\n",sum);
	
	return 0;
	}

Measured memory_bytes: 632
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <math.h>
#include <map>
#include <stack>
using namespace std;
static const int INF = 1e9+7;
// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, a, b) for (int i =a; i < b; i++)
#define all(a) a.begin(), a.end()
#define PI 3.14159265359

int main(){
    int k, s; cin >> k >> s;
    int cnt = 0;
    rep(i, k+1){
        rep(j, k+1){
            int h = s - (i + j);
            if(0 <= h and h <= k) cnt++;
        }
    }

    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 3596
#include <iostream>
using namespace std;
 int main(){
   int A,B,K;
   cin>>A>>B>>K;

   int sum=0;

   for(int i=min(A,B);i>0;i--){
     if(A%i==0&&B%i==0){
       sum++;
   }

     if(sum==K){
       cout<<i<<endl;
       break;
     }

}


}

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

using namespace std;

typedef long long ll;

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

const ll MOD = 998244353;

ll mypow(ll a, ll b){
	if(b == 0) return 1;
	if(b % 2 == 1) return a * mypow(a, b - 1) % MOD;

	ll d = mypow(a, b / 2) % MOD;
	return d * d % MOD;
}

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

	ll n, s;
	cin >> n >> s;

	vector<ll> a(n);
	rep(i, n) cin >> a[i];

	ll INF = 1e17;
	ll dp[n+1][s+1];
	rep(i, n+1) rep(j, s+1) dp[i][j] = INF;
	dp[0][0] = mypow(2, n);

	ll inv2 = mypow(2, MOD - 2);

	rep(i, n){
		rep(j, s+1){

			if(dp[i][j] < INF){
				if(dp[i+1][j] == INF) dp[i+1][j] = 0;
				dp[i+1][j] += dp[i][j];
				dp[i+1][j] %= MOD;
			    
				if(j + a[i] <= s) {
					if(dp[i+1][j+a[i]] == INF) dp[i+1][j+a[i]] = 0;
					dp[i+1][j+a[i]] += dp[i][j] * inv2 % MOD;
					dp[i+1][j+a[i]] %= MOD;
				}
			}
		}
	}

	if(dp[n][s] == INF){
		cout << 0 << endl;
	}else{
		cout << dp[n][s] << endl;
	}
}


Measured memory_bytes: 73996
#include<bits/stdc++.h>
using namespace std;
int main()
{
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);
	long long int n;
	cin>>n;
	long long int sum=0;
	unordered_map<long long int,long long int> m;
	for(long long int i=0;i<n;i++)
	{
		long long int p;
		cin>>p;
		sum+=p;
		m[p]++;
	}
	long long int q;
	cin>>q;
	while(q--)
	{
		long long int a,b;
		cin>>a>>b;
			m[b]+=m[a];
			sum = sum+(b-a)*m[a];
			m.erase(a);
		cout<<sum<<endl;
	}
	return 0;
}


Measured memory_bytes: 6624
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define clr(a, b) memset(a, b, sizeof(a))
#define Error(x) cout << #x << " = " << x << endl
#define iDEBUG freopen("in.txt", "r", stdin)
#define oDEBUG freopen("output.txt","w",stdout)
#define pb push_back
#define x first
#define y second
#define all(x) x.begin(),x.end()
#define hi cout<<"hi\n"
typedef long long ll;

using namespace std;
int gcd(int m, int n) { if((0 == m) || (0 == n)){return 0;} while(m != n){ if(m > n){m -= n;}else{n -= m;} } return m; }
int lcm(int m, int n) { if((0 == m) || (0 == n)){return 0;} return (m / gcd(m, n)) * n; }

int main()
{
    //iDEBUG; //oDEBUG;
    int n, m;
    string str;
    map<string, int> mp;
    map<string, int>::iterator iter;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> str;
        mp[str]++;
    }
    cin >> m;
    for(int i=0; i<m; i++){
        cin >> str;
        mp[str]--;
    }
    int ans = 0;
    for(iter=mp.begin(); iter!=mp.end(); iter++)
        ans = max(ans, iter->y);
    cout << ans << endl;

    return 0;
}


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

int N,A,B;
double ans = 0;
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> A >> B;

	ans = A*1.0 / B;

	printf("%.10f",ans);

}

Measured memory_bytes: 256
import * as fs from 'fs';

namespace AtCoder.hitachi2020 {

    export class Program {
        /**
         * in
         * 2 2 1
         * 3 5
         * 3 5
         * 2 2 2
         * out
         * 6
         */
        static main(inp: string): void {

            // a,bの最安値
            // クーポンを使ったときの値
            const [a, b, m]: number[] = inp.split('\n')[0].split(' ').map(Number);
            const aList: number[] = inp.split('\n')[1].split(' ').map(Number);
            const bList: number[] = inp.split('\n')[2].split(' ').map(Number);

            let ans1: number = 0;
            // ans1 = aList.sort()[0];
            // ans1 += bList.sort()[0];
            // ans1 = Math.min(...aList)
            // ans1 += Math.min(...bList)
            ans1 = aList.reduce((a, b) => Math.min(a, b));
            ans1 += bList.reduce((a, b) => Math.min(a, b));

            // クーポン
            const ww: string[] = inp.split('\n');
            for (let i: number = 0; i < m; i++) {
                const [x, y, c]: number[] = ww[i + 3].split(' ').map(Number);

                let wk: number = aList[x - 1] + bList[y - 1] - c;
                if (ans1 > wk) {
                    ans1 = wk;
                }
            }

            console.log(ans1);

        }
    }
}

AtCoder.hitachi2020.Program.main(fs.readFileSync('/dev/stdin', 'utf8').trim());


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

using namespace std;

int main()
{
	int a,b;
	cin >> a >> b;
	cout << (a<=5 ? 0:(a<=12 ? b/2:b)) << endl;




}


Measured memory_bytes: 256
x, y = map(int, input().split())
x_, y_ = x, y
ans = 0

def sign(n):
    if n == 0:
        return 0
    else:
        return int(n / abs(n))

if abs(x) > abs(y):
    if x > 0:
        x_ = -x
        ans += 1
else:
    if x < 0:
        x_ = -x
        ans += 1

ans += abs(abs(x) - abs(y))
x_ += abs(abs(x) - abs(y))
if sign(x_) != sign(y):
    ans += 1
print(ans)


    

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

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll longinf = 5LL << 60;
const ll mod = 1e9 + 7;

int main() {
	int X, Y;
	cin >> X >> Y;
	cout << X + Y / 2 << "\n";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <time.h>
#define ll long long
#define mp(a,b) make_pair(a,b)
#define si(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define ss(s) scanf("%s",&s)
#define pi(n) printf("%d\n",n)
#define pl(n) printf("%lld\n",n)
#define newline cout << endl;
using namespace std;

int main(){
  clock_t tStart = clock();
  ll n; sl(n);
  ll arr[n];
  for(ll i=0;i<n;i++) sl(arr[i]);
  sort(arr,arr+n);
  ll ans = abs(arr[0]-arr[n-1]);
  pl(ans);
  //printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
  return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(n) for ( int i =0; i < n ; i ++)
int N, L, sum, m;
//vector<int> l, d;
int main()
{
	scanf("%d", &N);
	rep(N)scanf("%d", &L), sum += L, m = max(m, L);
	printf(m < sum - m ? "Yes" : "No");
}

Measured memory_bytes: 504
#include <iostream>
#include <vector>
#include <array>
#include <stack>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <iomanip>

constexpr int NUM_TICKET = 8;
int n, m, p, a, b;
float costs[30][30] = {0};
std::array<int, NUM_TICKET> t;
float dp[1 << NUM_TICKET][30] = {0};

struct Node {
	float cost;
	int city;
	unsigned char tickets = 0b11111111;
};

int main() {
	while (std::cin >> n >> m >> p >> a >> b && (n || m || p || a || b)) {
		--a; --b;
		std::memset(dp, 0x7f, sizeof(float) * (1 << NUM_TICKET) * 30);
		std::memset(costs, 0, sizeof(float) * 30 * 30);
		for (int i = 0; i < n; i++) std::cin >> t[i];
		for (int i = 0; i < p; i++) {
			int x, y; float cost;
			std::cin >> x >> y >> cost;
			costs[--x][--y] = cost;
			costs[y][x] = cost;
		}

		//DFS
		std::stack<Node> s;
		s.push({ 0.f, a });
		bool isOk = false;
		float minCost = INFINITY;
		while (!s.empty()) {
			auto node = s.top(); s.pop();
			if (node.city == b) {
				minCost = std::min(minCost, node.cost);
				isOk = true;
				continue;
			}
			for (int i = 0; i < m; i++) { //?¬??????????
				if (!costs[node.city][i]) continue;
				//???????????????TICKET??§??????
				for (int j = 0; j < n; j++) {
					if (!((node.tickets >> j) & 1)) continue; //?????£????????????

					auto next = node;
					next.city = i;
					next.cost += costs[node.city][i] / t[j];
					next.tickets ^= (1 << j);
					if (dp[next.tickets][i] <= next.cost) continue;
					dp[next.tickets][i] = next.cost;
					s.push(next);
				}
			}
		}
		if (isOk) std::cout << std::fixed << std::setprecision(3) << minCost << std::endl;
		else std::cout << "Impossible" << std::endl;
	}
	return 0;
}

Measured memory_bytes: 3240
from bisect import bisect_right
import sys
input = sys.stdin.buffer.readline

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]

XH.sort()
X = [x for x, h in XH]

check = [0] * (N + 1)
index = 0
minus = 0
answer = 0

while 1:
  pt = XH[index][0] + 2 * D
  ht = (-(-XH[index][1] // A)) * A
  bi = bisect_right(X, pt)
  minus += ht
  answer += -(-XH[index][1] // A)
  check[bi] += ht

  flag = 1
  for i in range(index, N):
    minus -= check[i]
    XH[i][1] -= minus
    check[i] = 0
    if XH[i][1] > 0:
      index = i
      flag = 0
      break
  if flag:
    break
                 
print(answer)

Measured memory_bytes: 55700
#include <iostream>
using namespace std;
int main(void){
    int a,b;
    char op;
    while(true){
        cin >> a >> op >> b;
        if ( op == '?' ){
            break;
        }else if ( op == '+' ){
            cout << a+b;
            cout << endl;
        } else if ( op == '-' ){
            cout << a-b;
            cout << endl;
        } else if ( op == '*' ){
            cout << a*b;
            cout << endl;
        } else if ( op == '/' ){
            cout << a/b;
            cout << endl;
        } 
    }
}


Measured memory_bytes: 3072
//#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <math.h>
#include <list>
#define mod 1000000007
#define ms0(x) memset(x, 0, sizeof(x))
#define ms_1(x) memset(x, -1, sizeof(x))
using namespace std;
using ll = long long int;
using ull = unsigned long long int;

int main(){
    int n;
    cin>>n;
    int h[n];
    for(int i=0;i<n;i++) cin>>h[i];
    ll x[n];
    x[0] = 0;
    x[1] = abs(h[0]-h[1]);
    for(int i=2;i<n;i++){
        x[i] = min(x[i-1]+abs(h[i]-h[i-1]), x[i-2]+abs(h[i]-h[i-2]));
    }
    cout<<x[n-1];
    return 0;
}


Measured memory_bytes: 1408
N,M = map(int,input().split())
s_info = [[] for j in range(M)]
for i in range(M):
	l = list(map(int,input().split()))
	n_l = [x-1 for x in l]
	s_info[i] = n_l[1:]
cond = list(map(int,input().split()))


def dec2bin(n, d):
	ret = []
	for i in range(d):
		ret.append(n%2)
		n = n // 2
	return ret

ans = 0
for i in range(2**N):
	switch = dec2bin(i, N)
	flg = True
	for m in range(M):
		if sum([1 for n in range(N) if switch[n] == 1 and n in s_info[m]]) % 2 != cond[m]:
			flg = False

		
	if flg:
		ans += 1

print(ans)

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

int main(){
    int N;
    scanf("%d", &N);
    char str[N+1];
    fscanf(stdin, "%s", str);
    //printf("%s\n", str);
    int c = 1;
    if (N % 2 == 0){
        char str1[N/2+1];
        char str2[N/2+1];
        for (int i = 0; i < N/2; i++){
            str1[i] = str[i];
            str2[i] = str[i+N/2];
            if (str1[i] != str2[i]){
                c = 0;
                break;
            }
        }
        //printf("%s\n%s\n", str1, str2);
    } else {
        c = 0;
    }
    if (c == 1){
        printf("Yes");
    } else {
        printf("No");
    }
}

Measured memory_bytes: 128
from math import ceil

N, H = map(int, input().split())
An, Bn = [0] * N, [0] * N
for i in range(N):
    An[i], Bn[i] = map(int, input().split())

ans = 0
a_max = max(An)
for b in sorted(Bn, reverse=True):
    if b < a_max:
        break
    H -= b
    ans += 1
    if H <= 0:
        break

if H > 0:
    ans += ceil(H/a_max)

print(ans)


Measured memory_bytes: 12080
/*
        _            _                  _            _       _     _         _   _          _          _             _        
       / /\         / /\               / /\         / /\    / /\  /\ \      /\_\/\_\ _     /\ \       /\ \     _    /\ \      
      / /  \       / /  \             / /  \       / / /   / / /  \ \ \    / / / / //\_\   \ \ \     /  \ \   /\_\ /  \ \     
     / / /\ \__   / / /\ \           / / /\ \__   / /_/   / / /   /\ \_\  /\ \/ \ \/ / /   /\ \_\   / /\ \ \_/ / // /\ \_\    
    / / /\ \___\ / / /\ \ \         / / /\ \___\ / /\ \__/ / /   / /\/_/ /  \____\__/ /   / /\/_/  / / /\ \___/ // / /\/_/    
    \ \ \ \/___// / /  \ \ \        \ \ \ \/___// /\ \___\/ /   / / /   / /\/________/   / / /    / / /  \/____// / / ______  
     \ \ \     / / /___/ /\ \        \ \ \     / / /\/___/ /   / / /   / / /\/_// / /   / / /    / / /    / / // / / /\_____\ 
 _    \ \ \   / / /_____/ /\ \   _    \ \ \   / / /   / / /   / / /   / / /    / / /   / / /    / / /    / / // / /  \/____ / 
/_/\__/ / /  / /_________/\ \ \ /_/\__/ / /  / / /   / / /___/ / /__ / / /    / / /___/ / /__  / / /    / / // / /_____/ / /  
\ \/___/ /  / / /_       __\ \_\\ \/___/ /  / / /   / / //\__\/_/___\\/_/    / / //\__\/_/___\/ / /    / / // / /______\/ /   
 \_____\/   \_\___\     /____/_/ \_____\/   \/_/    \/_/ \/_________/        \/_/ \/_________/\/_/     \/_/ \/___________/    
                                                                                                                              
*/
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for(int i = 0;i < (n);++i)

#define endl '\n'
#define pb emplace_back
#define mkp make_pair
#define p_q priority_queue
#define INF 1000000000
#define PI 3.1415926
#define coutdb cout << fixed << setprecision(10)

const int dx[]={1,0,-1,0}, dy[]={0,-1,0,1};
const int dx_8[]={1,1,0,-1,-1,-1,0,1}, dy_8[]={0,-1,-1,-1,0,1,1,1};
const long long MOD = 1e9+7;

// typedef long long ll;
#define int long long

template <typename T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template <typename T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template <typename T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template <typename T> inline T nHr(T a,T b){return nCr(a+b-1,b);}

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

  int N, a[100000]; cin >> N;
  multiset<int> st;
  int ans = 0;
  REP(i, N){
    cin >> a[i];
    st.insert(a[i]);
    if(a[i] > (*st.begin())){
      auto itr = st.find(a[i]);
      itr--;
      st.erase(itr);
    }
  }
  cout << st.size() << endl;
}

Measured memory_bytes: 5760
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<deque>
#include<queue>
#include<stack>
using namespace std;
#define int long long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define dup(x,y) (((x)+(y)-1)/(y))
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef pair<int, int>P;
const int MOD = 1e9 + 7;
//const int MOD = 998244353;
const int INF = 1e18;
const long double PI = (acos(-1));


signed main() {
	int N;
	string S;
	cin >> N >> S;
	int left = 0;
	int right = 0;
	rep(i, S.size())if (S[i] == '.')right++;
	int ans = right;
	rep(i, N) {
		if (S[i] == '.')right--;
		else left++;
		ans = min(ans, left + right);
	}
	cout << ans << endl;
}

Measured memory_bytes: 3748
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {

    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}


fn main() {
    input!{
        s: chars,
        t: chars,
    }
    let mut count = 0;
    for i in 0..s.len(){
        if s[i] != t[i]{
            count += 1;
        }
    }
    println!("{}", count)
}


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

int run(int n, int a, int b, int c, int x, vector<int> &y, vector<int> &z) {
  int head = 0;
  rep (t, 10000+1) {
    if (y[head] == z[t]) head++;
    // if (t > 10000) return -1;
    if (head == n) return t;
  }
  return -1;
}

int main() {
  int n, a, b, c, x;
  while(cin >> n >> a >> b >> c >> x, n) {
    vector<int> y(n);
    vector<int> z(10000+1);
    z[0] = x;
    rep (i, n) cin >> y[i];

    for (int i=1; i<=10000+1; i++) z[i] = (a*z[i-1] + b) % c;

    // cout << "y: ";
    // rep (i, n) cout << y[i] << ' ';
    // cout << endl;
    // cout << "z: ";
    // rep (i, 300) cout << z[i] << ' ';
    // cout << endl;

    int ans = run(n, a, b, c, x, y, z);
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 3108
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    int N;
    cin >> N;
    vector<int> d(N);
    for(int i = 0; i < N; i++){
        cin >> d.at(i);
    }
    ll sum = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            sum += d.at(i) * d.at(j);
        }
        sum -= d.at(i) * d.at(i);
    }
    sum /= 2;
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
from itertools import product
from copy import deepcopy

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    D = list(map(int, input().split()))

    cnt = [0] * 13
    cnt[0] = 1
    for d in D:
        cnt[d] += 1

    P = []
    init_T = []
    for i in range(13):
        if i == 0 or i == 12:
            if cnt[i]:
                if cnt[i] == 1:
                    init_T.append(i)
                else:
                    print(0)
                    exit()
        else:
            if cnt[i]:
                if cnt[i] == 1:
                    P.append(i)
                elif cnt[i] == 2:
                    init_T.append(i)
                    init_T.append(24 - i)
                else:
                    print(0)
                    exit()

    res = 0
    for pattern in product([0, 1], repeat=len(P)):
        T = deepcopy(init_T)
        for idx, p in enumerate(pattern):
            if p == 0:
                T.append(P[idx])
            else:
                T.append(24 - P[idx])

        min_gap = f_inf
        for i in range(len(T)):
            for j in range(i + 1, len(T)):
                gap = abs(T[i] - T[j])
                min_gap = min(min_gap, min(gap, 24 - gap))

        res = max(res, min_gap)

    print(res)


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 3824
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <stack>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;

template<class T> inline bool chmax(T& a, T b){ if(a < b) { a=b; return 1; }return 0;}
template<class T> inline bool chmin(T& a, T b){ if(a > b) { a=b; return 1; }return 0;}


const long long INF = 1LL << 60;

//bucket1
// bool ch[10] = {0};
// bool check(int n){
//     while(n!=0){
//         if(ch[n%10]) return false;
//         n /= 10;
//     }
//     return true;
// }



// --------write my code!!!!!----------//


int main(){
    string s[3]; rep(i,3) cin >> s[i];
    int count[3]; rep(i,3) count[i] = 0;
    int turn = 0;
    int nextturn = 0;
    bool flag = true;
    while(flag){
        if(count[turn]>=s[turn].length()){
            break;
        }
        nextturn = s[turn][count[turn]] - 97;
        count[turn]++;
        turn = nextturn;
    }
    cout << char(turn+65) << endl;
} 


Measured memory_bytes: 256
#include<algorithm>
#include<string>
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;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 llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
 
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};
 
 
int main(){
    
    string s;
    cin >> s;
    if(s.size() == 2){
        cout << s << endl;
    }
    else if (s.size() == 3){
        char s1=s[0];
        s[0] = s[2];
        s[2] = s1;
        cout << s << endl;
    }

    return 0;
}

Measured memory_bytes: 256
import java.io.DataInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;


public class Main {
	
	public static void main(String[] args) throws IOException {
		Main m = new Main();
		m.input();
		m.solve();
		m.output();
	}
	
//	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	InputUtil in = new InputUtil();
	PrintWriter out = new PrintWriter(System.out);
	
	int N = 0;
	int K = 0;
	int[] A = null;
	int[] B = null;
	long ans = 0L;
	int[] bitmask = new int[32];
	int bitmaskPtr = 0;
	
	public void input() throws IOException {
		N = in.nextInt();
		K = in.nextInt();
		A = new int[N];
		B = new int[N];
		for(int i=0; i<N; i++) {
			A[i] = in.nextInt();
			B[i] = in.nextInt();
		}
	}

	public void solve() throws IOException {
		bitmask[bitmaskPtr++] = K;
		int bitmask_upper=0;
		for(int i=1<<30; i>0; i>>>=1){
			if((K & i) > 0){
				bitmask[bitmaskPtr++] =  bitmask_upper | (i-1);
				bitmask_upper |= i;
			}
		}
		
		for(int i=0; i<bitmaskPtr; i++) {
			long sum = 0;
			for(int j=0; j<N; j++){
				if((A[j] | bitmask[i]) == bitmask[i]) {
					sum += B[j];
				}
			}
			ans = Math.max(ans, sum);
		}
	}
	
	public void output() {
		out.println(ans);
		out.flush();
	}
}



class InputUtil {
	//Static Fields
	private static final int BUFSIZ = 100000;
	
	//Fields
	protected InputStream in;
	private byte[] buf = null;
	private int ptr = 0;
	private int max = -1;
	private DataInputStream dis = null;
	//Constructors
	public InputUtil() {this(System.in,BUFSIZ);}
	public InputUtil(InputStream in, int bufsiz) {
		initBuf(bufsiz);
		initIn(in);
	}
	
	//Methods
	//Initializer
	protected void initIn(InputStream in) {dis = new DataInputStream(this.in = in);}
	protected void initBuf(int bufsiz) {buf = new byte[bufsiz];}
	
	//buffer operation
	private void next() throws IOException {ptr++; readBuf();}
	private void readBuf() throws IOException {
		if(ptr >= max && dis.available()>0) {
			if(max>0) Arrays.fill(buf,0,max,(byte)0);
			max = dis.read(buf);
			ptr = 0;
		}
	}
	
	//Number Input Reader/Parser
	private boolean isNum(byte b) {return '0' <= b && b <= '9'; }
	private boolean isMinus(byte b) {return b=='-'; }

	private int _nextInt() throws IOException {
		int sign = 1;
		int res = 0;
		byte c;
		while (!isNum(c=buf[ptr]) && !isMinus(c)) 
			next();
		if (isMinus(buf[ptr])) {
			sign = -1;
			next();
		}
		while (isNum(c=buf[ptr])) {
			res *= 10;
			res += c - '0' ;
			next();
		}
		next();
		return sign * res;
	}
	
	public int nextInt() throws IOException {
		readBuf();
		return _nextInt();
	}

	public int[] nextInt(int[] result) throws IOException {
		readBuf();
		for(int i=0; i<result.length; i++) {
			result[i] = _nextInt();
		}
		return result;
	}
	
	//Close 
	public void close() throws IOException {
		if(!this.in.equals(System.in)) 
			this.in.close();
	}

}


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

using namespace std;
typedef long long LL;
int sum[1000000];

int main()
{
    LL n,m;
    while(scanf("%lld%lld",&n,&m)==2){
        LL x;
        sum[0]=0;
        for(LL i=1;i<=n;i++){
            scanf("%lld",&x);
            sum[i]=((sum[i-1]+x)%m+m)%m;
        }
        sort(sum,sum+n+1);
        LL s=1;
        long long ans=0;
        for(LL i=1;i<=n;i++){
            if(sum[i]==sum[i-1]) s++;
            else{
                ans+=s*(s-1)/2;
                s=1;
            }
        }
        ans+=s*(s-1)/2;
        printf("%lld\n",ans);
    }
    return 0;
}


Measured memory_bytes: 640
(let ((n (read))
      (a (make-array 0 :element-type 'integer
                       :adjustable t
                       :fill-pointer 0))
      (ans 0)
      temp)
     (dotimes (i n)
       (vector-push-extend (read) a))
     (dotimes (i n)
       (setf temp (read))
       (if (< 0 (- (aref a i) temp)) (incf ans (- (aref a i) temp))))
     (princ ans))

Measured memory_bytes: 3944
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using static System.Math;
using System.Text;
using System.Threading;
using System.Globalization;
using System.Runtime.CompilerServices;
using Library;

namespace Program
{
    public static class KEYENCE2020C
    {
        static public int numberOfRandomCases = 0;
        static public void MakeTestCase(List<string> _input, List<string> _output, ref Func<string[], bool> _outputChecker)
        {
        }
        static public void Solve()
        {
            var N = NN;
            var K = NN;
            var S = NN;
            var ary = Repeat(S, N).ToArray();
            if(S == 1) {
            for (var i = 0; i < N - K; i++)
            {
                ary[i] = S + 1;
            }
            }else {
            for (var i = 0; i < N - K; i++)
            {
                ary[i] = S - 1;
            }
            }
            Console.WriteLine(string.Join(" ", ary));
        }
        static class Console_
        {
            static Queue<string> param = new Queue<string>();
            public static string NextString() { if (param.Count == 0) foreach (var item in Console.ReadLine().Split(' ')) param.Enqueue(item); return param.Dequeue(); }
        }
        class Printer : StreamWriter
        {
            public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
            public Printer(Stream stream) : base(stream, new UTF8Encoding(false, true)) { base.AutoFlush = false; }
            public Printer(Stream stream, Encoding encoding) : base(stream, encoding) { base.AutoFlush = false; }
        }
        static public void Main(string[] args) { if (args.Length == 0) { Console.SetOut(new Printer(Console.OpenStandardOutput())); } var t = new Thread(Solve, 134217728); t.Start(); t.Join(); Console.Out.Flush(); }
        static long NN => long.Parse(Console_.NextString());
        static double ND => double.Parse(Console_.NextString());
        static string NS => Console_.NextString();
        static long[] NNList(long N) => Repeat(0, N).Select(_ => NN).ToArray();
        static double[] NDList(long N) => Repeat(0, N).Select(_ => ND).ToArray();
        static string[] NSList(long N) => Repeat(0, N).Select(_ => NS).ToArray();
        static IEnumerable<T> OrderByRand<T>(this IEnumerable<T> x) => x.OrderBy(_ => xorshift);
        static long Count<T>(this IEnumerable<T> x, Func<T, bool> pred) => Enumerable.Count(x, pred);
        static IEnumerable<T> Repeat<T>(T v, long n) => Enumerable.Repeat<T>(v, (int)n);
        static IEnumerable<int> Range(long s, long c) => Enumerable.Range((int)s, (int)c);
        static uint xorshift { get { _xsi.MoveNext(); return _xsi.Current; } }
        static IEnumerator<uint> _xsi = _xsc();
        static IEnumerator<uint> _xsc() { uint x = 123456789, y = 362436069, z = 521288629, w = (uint)(DateTime.Now.Ticks & 0xffffffff); while (true) { var t = x ^ (x << 11); x = y; y = z; z = w; w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); yield return w; } }
    }
}
namespace Library {
}


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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int h, w, n;
  cin >> h >> w >> n;
  
  cout << (max(h, w) + n - 1) / max(h, w) << '\n';
}

Measured memory_bytes: 256
#include <stdio.h>

typedef struct { int v, m, c; } machine;

int normal[512];
machine defective[1024];

int main(void)
{
	int a, b, c;
	
	while (scanf("%d %d %d", &a, &b, &c), a != 0){
		int n;
		int len = 0;
		int i;
		
		for (i = 0; i <= a + b + c + 1; i++) normal[i] = 2;
		scanf("%d", &n);
		for (i = 0; i < n; i++){
			machine t;
			int r;
			
			scanf("%d %d %d %d", &t.v, &t.m, &t.c, &r);
			if (r == 1) normal[t.v] = normal[t.m] = normal[t.c] = 1;
			else defective[len++] = t;
		}
		for (i = 0; i < len; i++){
			machine t = defective[i];
			
			if (normal[t.m] == 1 && normal[t.c] == 1) normal[t.v] = 0;
			else if (normal[t.v] == 1 && normal[t.c] == 1) normal[t.m] = 0;
			else if (normal[t.v] == 1 && normal[t.m] == 1) normal[t.c] = 0;
		}
		for (i = 1; i <= a + b + c; i++) printf("%d\n", normal[i]);
	}
	
	return 0;
}

Measured memory_bytes: 612
#include <bits/stdc++.h>
using namespace std;
int k,a,b;
void solve(){
    for(int i=1;;i++){
        if(a<=k*i&&k*i<=b){
            cout<<"OK";
            return;
        }
        else if(k*i>=b){
            cout<<"NG";
            return;
        }
    }
    
    return;
}
int main(void){
    
    cin>>k;
    cin>>a>>b;
    solve();
    return 0;
}


Measured memory_bytes: 3620
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		int m;
		
		int[] v;
		int[] num;
		int[][] dp;
		int g;
		
		while(true){
			m = scan.nextInt();
			if(m == 0)break;
			
			v = new int[m + 1];
			num = new int[m + 1];
			for(int i = 1; i <= m; i++){
				v[i] = scan.nextInt();
				num[i] = scan.nextInt();
			}
			
			dp = new int[m+1][1001];
			dp[0][0] = 1;
			
			for(int i = 1; i <= m; i++){
				for(int k = 0; k < 1001; k++){
					for(int s = 0; s <= num[i]; s++){
						if(k - v[i] * s < 0)break;
						dp[i][k] += dp[i - 1][k - s * v[i]];
					}
				}
			}
			g = scan.nextInt();
			while(g-- != 0)System.out.println(dp[m][scan.nextInt()]);
		}
	}
}

Measured memory_bytes: 27260
using System;
using System.Linq;
using System.Collections.Generic;
using System.Text;

public class AtCoderC
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        string[] strs = new string[n];
        for (int i = 0; i < n; i++)
        {
            string s = Console.ReadLine();
            strs[i] = string.Join("", s.OrderBy(c => c));
        }

        Array.Sort(strs, new StringComparator());

        long answer = 0;
        string before = strs[0];
        long count = 1;
        for (int i = 1; i < n; i++)
        {
            if (before.Equals(strs[i]))
            {
                count++;
            }
            else
            {
                answer += count * (count - 1) / 2;
                count = 1;
                before = strs[i];
            }
        }
        answer += count * (count - 1) / 2;

        Console.WriteLine(answer);
    }

    // 文字列比較のComparator
    class StringComparator : IComparer<string>
    {
        int IComparer<string>.Compare(string a, string b)
        {
            for (int i = 0; i < Math.Min(a.Length, b.Length); i++)
            {
                if (a[i] < b[i])
                {
                    return -1;
                }
                else if (a[i] > b[i])
                {
                    return 1;
                }
            }
            if (a.Length < b.Length)
            {
                return -1;
            }
            else if (a.Length > b.Length)
            {
                return 1;
            }
            else
            {
                return 0;
            }
        }
    }
}

Measured memory_bytes: 24852
#include <stdio.h>
#include <vector>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <cstring>
using namespace std;
using ll = long long;

int main(){
  std::vector<int> v(3);
  for (size_t i = 0; i < 3; i++) {
    cin >> v[i];
  }
  sort(v.begin(),v.end());
  if (v[0] + v[1] == v[2]) {
    puts("Yes");
  } else{
    puts("No");
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
  
  int a,b;
  cin>>a>>b;
  
  if(a<b) cout<<"a < b"<<endl;
  else if(a>b) cout<<"a > b"<<endl;
  else cout<<"a == b"<<endl;
  
  return 0;
  
}



Measured memory_bytes: 3104
from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
from fractions import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 10**5+10
MOD = 10**9+7
spf = [i for i in range(MAXN)]
spf[0]=spf[1] = -1
def sieve():
    for i in range(2,MAXN,2):
        spf[i] = 2
    for i in range(3,int(MAXN**0.5)+1):
        if spf[i]==i:
            for j in range(i*i,MAXN,i):
                if spf[j]==j:
                    spf[j]=i
def fib(n,m):
    if n == 0:
        return [0, 1]
    else:
        a, b = fib(n // 2)
        c = ((a%m) * ((b%m) * 2 - (a%m)))%m
        d = ((a%m) * (a%m))%m + ((b)%m * (b)%m)%m
        if n % 2 == 0:
            return [c, d]
        else:
            return [d, c + d]

def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))

def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))

def ncr(n,r):
    num=den=1
    for i in range(r):
        num = (num*(n-i))%MOD
        den = (den*(i+1))%MOD

    return (num*(pow(den,MOD-2,MOD)))%MOD

def flush():
    return sys.stdout.flush()

'''*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*'''

d = {}
def fun(n):

    if n==1:
        return 1
    if d.get(n):
        return d[n]
    ans = 0
    ans+=1+2*fun(n//2)

    d[n] = ans
    return d[n]

n = int(input())
print(fun(n))

Measured memory_bytes: 9880
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <queue>
#include <stack>
#include <utility>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;

const int64_t MOD = std::pow(10, 9) + 7;
void OutputError(std::string s) {
  cerr << "\033[93m" << s << "\033[m" << endl;
  return;
}

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

  int n;
  cin >> n;

  int64_t dp[100][4][4][4] = {};
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
      for (int k = 0; k < 4; k++) {
        dp[2][i][j][k] = 1;
      }
    }
  }
  dp[2][0][2][1] = 0;
  dp[2][0][1][2] = 0;
  dp[2][2][0][1] = 0;

  for (int i = 3; i < n; i++) {
    for (int j = 0; j < 4; j++) {
      for (int k = 0; k < 4; k++) {
        for (int l = 0; l < 4; l++) {
          for (int m = 0; m < 4; m++) {
            if (k == 0 && l == 2 && m == 1) continue;
            if (k == 2 && l == 0 && m == 1) continue;
            if (k == 0 && l == 1 && m == 2) continue;
            if (j == 0 && l == 2 && m == 1) continue;
            if (j == 0 && k == 2 && m == 1) continue;
            dp[i][k][l][m] += dp[i - 1][j][k][l];
            dp[i][k][l][m] %= MOD;
          }
        }
      }
    }
  }

  int64_t sum = 0;
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
      for (int k = 0; k < 4; k++) {
        if (i == 2 && j == 0 && k == 1)
          continue;
        else if (i == 0 && j == 1 && k == 2)
          continue;
        sum += dp[n - 1][i][j][k];
        sum %= MOD;
      }
    }
  }
  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
class P
{
    static void Main()
    {
        long[] xy = Console.ReadLine().Split().Select(long.Parse).ToArray();
        Console.WriteLine(Math.Abs(xy[0] - xy[1]) > 1 ? "Alice" : "Brown");
    }
}

Measured memory_bytes: 13268
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        sc.nextInt();
        String S = sc.next();

        System.out.println(solve(S));

        sc.close();
    }

    static String solve(String S) {
        int prefixLength = 0;
        int depth = 0;
        for (char ch : S.toCharArray()) {
            if (ch == '(') {
                ++depth;
            } else if (depth == 0) {
                ++prefixLength;
            } else {
                --depth;
            }
        }

        int suffixLength = depth;

        return String.format("%s%s%s", repeat('(', prefixLength), S, repeat(')', suffixLength));
    }

    static String repeat(char ch, int count) {
        return IntStream.range(0, count).mapToObj(i -> String.valueOf(ch)).collect(Collectors.joining());
    }
}

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

public class Main {
	private static void solve(){
		//Implement solution here.
		int n = ni();
		int m = ni();
		Map<Integer,Integer> map = new HashMap<Integer,Integer>();
		for(int i = 0; i < n; i++) {
			int a = ni();
			if(map.containsKey(a)) {
				map.put(a, map.get(a) + 1);
			}else {
				map.put(a, 1);
			}
		}
		
		for(int i = 0; i < m; i++) {
			int b = ni();
			int c = ni();
			if(map.containsKey(c)) {
				map.put(c, map.get(c) + b);
			}else {
				map.put(c, b);
			}
		}
		
		Set<Integer> keySet = map.keySet();
		Integer[] keyArray = keySet.toArray(new Integer[keySet.size()]);
		Arrays.sort(keyArray);
		
		int cnt = 0;
		int kidx = keyArray.length - 1;
		long result = 0;
		while(cnt < n) {
			int d = keyArray[kidx];
			int dcnt = map.get(d);
			
			if(cnt + dcnt <= n) {
				result += (long)d * (long)dcnt;
				cnt += dcnt;
			} else {
				result += (long)d*(long)(n - cnt);
				cnt = n;
			}
			kidx--;
		}
		System.out.println(result);
	}

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

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

Measured memory_bytes: 60648
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
//二項係数の計算
int nCr(int A, int B) {
    ll ans = 1;
    for (int i = 0; i < B; i++) {
        ans *= A - i;
    }
    for (int i = 0; i < B; i++) {
        ans /= i + 1;
    }
    return ans;
}
int main() {
  int a,b;
  cin>>a>>b;
  if(10<=b){
    if(100<=b){
    	b+=a*1000;  
    }
    else{
      b+=a*100;
    }
  }
  else{
    b+=a*10;
  }
  long double d=int(sqrt(b))*int(sqrt(b));
  if(d==b){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 3684
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<math.h>
#include<map>
#include<iomanip>
#include<queue>

using namespace std;

int main(){
	vector<int> a(4);
	for(int i=0;i<4;i++)cin >> a[i];
	if(a[0]==a[2])cout << 0 << endl;
	else cout << 1 << endl;
	return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define fastIO (cin.tie(0), cout.tie(0), ios::sync_with_stdio(false))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define precise(i) fixed << setprecision(i)
using li = unsigned long long int;
using namespace std;

int main() {
    fastIO;
    string a, b;
    cin >> a >> b;
    if (a == b)
        cout << "EQUAL";
    else if (a.size() > b.size())
        cout << "GREATER";
    else if (a.size() < b.size())
        cout << "LESS";
    else {
        if (a[0] > b[0])
            cout << "GREATER";
        else if (a[0] < b[0])
            cout << "LESS";
    }
}

Measured memory_bytes: 3592
#include<bits/stdc++.h>
#define MAX 300001
using namespace std;
int segtree[MAX*4],dp[MAX+1];
void update(int l,int r, int k, int point, int value)
{
	if(point>r||point<l)
		return;
	if(l==r)
	{
		segtree[k] = max(segtree[k],value);
		return;
	}
	int m = (l+r)/2;
	update(l,m,2*k+1,point,value);
	update(m+1,r,2*k+2,point,value);
	segtree[k] = max(segtree[2*k+1],segtree[2*k+2]);
}
int query(int ls,int rs,int lq,int rq,int k)
{
	if(rs<lq||rq<ls)
		return 0;
	if(lq<=ls&&rs<=rq)
		return segtree[k];
	int m = (ls+rs)/2;
	return max(query(ls,m,lq,rq,2*k+1),query(m+1,rs,lq,rq,2*k+2));
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,k;
	cin>>n>>k;
	int v[n],r = 0;
	for(int i=0;i<n;++i)
		cin>>v[i], r = max(r,v[i]);
	for(int i=n-1;i>=0;--i)
	{
		dp[i] = 1+query(0,r,v[i]-k,v[i]+k,0);
		update(0,r,0,v[i],dp[i]);
		dp[i] = max(dp[i],dp[i+1]);
	}
	cout<<dp[0]<<endl;
	return 0;
}

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

int main() {
  int W, a, b;
  cin >> W >> a >> b;

  int x = min(a, b);
  int y = max(a, b);
  if (x + W >= y)
    cout << 0 << endl;
  else
    cout << y - (W + x) << endl;

  return 0;
}


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

void fnInput(int& rnMaxNum)
{
  cin >> rnMaxNum;
}

bool fnDgt753_Check(llong nRecNum)
{
  int nDgt3 = 0, nDgt5 = 0, nDgt7 = 0;

  while (nRecNum)
  {
    int n1stDgt = nRecNum % 10;

    if      (n1stDgt == 3) nDgt3++;
    else if (n1stDgt == 5) nDgt5++;
    else if (n1stDgt == 7) nDgt7++;

    nRecNum /= 10;
  }

  if (nDgt3 && nDgt5 && nDgt7)
    return true;
  else
    return false;
}

void fnDfs(int nMaxNum, llong nRecNum)
{
  static int stn753DgtCnt = 0;

  if (nRecNum > nMaxNum) return;
  if (fnDgt753_Check(nRecNum)) stn753DgtCnt++;

  fnDfs(nMaxNum, 10 * nRecNum + 3);
  fnDfs(nMaxNum, 10 * nRecNum + 5);
  fnDfs(nMaxNum, 10 * nRecNum + 7);

  if (!nRecNum) cout << stn753DgtCnt << endl;
}

int main()
{
  int nMaxNum;

  fnInput(nMaxNum);
  fnDfs(nMaxNum, 0);

  return 0;
}

Measured memory_bytes: 256