akhauriyash/Code-Regression huggingface dataset:
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n,i,j,k,min1;
    cin>>n>>k;
    int a[n+1];
    for(i=1;i<=n;i++)
     cin>>a[i];
    int dp[n+1];
    dp[0]=0;
    dp[1]=0;
    dp[2]=abs(a[2]-a[1]);
    for(i=3;i<=n;i++)
    {min1=1000000000;
        for(j=1;j<=k;j++)
        {
            if((i-j)<1)
             break;
            min1=min(min1,dp[i-j]+abs(a[i]-a[i-j]));
        }
        dp[i]=min1;
    }
    cout<<dp[n];
    return 0;
}


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

int main()
{
    int n, m, b;
    long long a, answer = 0;
    std::vector<std::pair<long long, int>> pvec;
    std::cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        std::cin >> a >> b;
        pvec.push_back(std::make_pair(a, b));
    }
    std::sort(pvec.begin(), pvec.end(), [](std::pair<long long, int> l, std::pair<long long, int> r) { return l.first < r.first; });
    for (std::pair<long long, int> p : pvec)
    {
        if (m == 0) { break; }
        for (int count = p.second; count != 0; count--)
        {
            if (m == 0) { break; }
            answer += p.first;
            m--;
        }
    }
    std::cout << answer << std::endl;
    return 0;
}

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

using ll = long long;

constexpr ll MOD = 1e9+7;
constexpr ll INF = 1ll<<60;

#define FOR(i,a,b) for (ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

int main(int argc, char **argv)
{
	ll N; cin >> N;

	ll h, n, w;

	for (h = 1; h <= 3500; ++h)
	{
		for (n = 1; n <= 3500; ++n)
		{
			ll A = N*h*n;
			ll B = 4*h*n - N*(n+h);
			if (B == 0) continue;
			if (A % B == 0)
			{
				w = A / B;
				if (1 <= w && w <= 3500)
				{
					goto exit;
				}
			}
		}
	}
 exit:
	std::cout << h << " " << n << " " << w << " " << std::endl;
}

Measured memory_bytes: 384
// Shift-JIS（シフトジス）

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b)
{
    if (a < b)
    {
        a ^= b;
        b ^= a;
        a ^= b;
    }

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

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

int main()
{
    int A[3];
    cin >> A[0] >> A[1] >> A[2];
    cout << *max_element(A, A + 3) - *min_element(A, A + 3) << endl;
}

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

int dp[2][110][100050];
int seen[2][110][100050];
string digit;
int D, l;

int solve(int id, int can, int r)
{
	if(id == l) return !r;
	int num = digit[id] - '0', ans = 0;
	if(seen[can][r][id]) return dp[can][r][id];
	for(int i = 0; i < 10; i++)
		if(can or i <= num)
			ans = (ans + solve(id + 1, can or i < num, (r + (i % D)) % D)) % 1000000007LL;
	seen[can][r][id] = 1;
	return dp[can][r][id] = ans;
}

int32_t main()
{
	cin >> digit >> D;
	l = digit.size();
	int ans = (solve(0, 0, 0) - 1) % 1000000007LL;
	if(ans < 0) ans += 1000000007LL;
	cout << ans << '\n';

	return 0;
}

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

int main() {
  int N;
  cin >> N;
  
  int D, X;
  int A[N];
  cin >> D >> X;
  for (int i=0; i<N; i++) {
    cin >> A[i];
  }
  
  int count=0;
  for (int i=0; i<N; i++) {
    for (int j=0, k=0; j<D; j++) {
      if (j==k*A[i]) {
        count++;
        k++;
      }
    }
  }
  
  cout << count+X << endl;
  
  return 0;
}


Measured memory_bytes: 3584
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <numeric>
#include <limits>
#include <cmath>
#include <iomanip>
#include <sstream>
 
#define ALL(a)  (a).begin(),(a).end()
 
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

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

    ll n;
    cin >> n;

    vector<ll> l;
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        l.push_back (temp);
        sum += temp;
    }

    bool ok = true;

    for (int i = 0; i < n; i++) {
        if (2 * l[i] >= sum) ok = false; 
    }

    (ok) ? (cout << "Yes" << endl) : (cout << "No" << endl);


    

}

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

#define MAX(x,y) (x>y?x:y)
#define MIN(x,y) (x<y?x:y)
#define ABS(x) (x>0?x:-(x))

#define INF 1000000000

void swap(int* a, int* b)
{
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

int gcd(int a, int b)
{
	if (a < b)
		swap(&a, &b);

	if (a % b == 0)
		return b;
	else
		return gcd(b, a % b);
}

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

void bubble_sort(int* p, int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - i - 1; j++)
		{
			if (p[j] > p[j + 1])
				swap(&p[j], &p[j + 1]);
		}
	}
}

int array_max(int* p, int n)
{
	int max = 0;
	for (int i = 0; i < n; i++)
	{
		if (p[i] > max)
			max = p[i];
	}
	return max;
}

int binary_search(int* p, int key, int n)
{
	int low = 0, high = n - 1;
	int middle;

	while (low <= high)
	{
		middle = (low + high) / 2;

		//printf("low %d  middle %d  high %d\n", low, middle, high);

		//for (int i = 0; i < n; i++)
		//{
		//	if (i == middle)
		//		printf(" ^ ");
		//	else if (i == low)
		//		printf(" [ ");
		//	else if (i == high)
		//		printf(" ] ");
		//	else if (i == middle)
		//		printf(" ^ ");
		//	else
		//		printf("   ");
		//}
		//printf("\n");

		if (key == p[middle])
			return key;
		else if (key < p[middle])
			high = middle - 1;
		else if (key > p[middle])
			low = middle + 1;
	}

	//printf("low %d  middle %d  high %d\n", low, middle, high);
	return -1;
}

int main()
{
	int H, W;
	int h, w;

	scanf("%d%d%d%d", &H, &W, &h, &w);

	printf("%d\n", H * W - (h * W + w * H) + h*w);

	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
long long sum(long long n){return n*(n+1)/2;}

int main(){
 
            int n;
            cin>>n;
            ll ans=0;
            for(int i=1;i<=n;i++){
                 for(int j=1;j<=n;j++){
                     for(int k=1;k<=n;k++){
                          ans+= gcd(k,gcd(i,j));
                     }
                 }
            }
            cout<<ans<<endl;
}

Measured memory_bytes: 3592
#include <iostream>
#include <string>

using namespace std;


int main(void){
    string a,b,c;
    cin>>a>>b>>c;
    if(a[a.size()-1]==b[0]&&b[b.size()-1]==c[0]){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <cmath>

#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <map>
#include <set>
#include <vector>

using namespace std;

int main() {
#ifdef _DEBUG
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif

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

  cout.precision(16);
  cout << fixed;

  int n;
  cin >> n;

  vector<int> a(n);
  for (auto&& i : a)
    cin >> i;

  int cnt = 0;

  for (int i = 0; i < n; ++i) {
    if (a[i] != i + 1)
      ++cnt;
  }

  if (cnt <= 2) {
    cout << "YES";

    return 0;
  }

  cout << "NO";
}


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

using namespace std;

#define ll long long

pair<ll, ll> track(int n, string op, ll j) {
	ll x = j;
	ll y = 1;
	for (int i = 0; i < op.length(); i++) {
		char c = op[i];
		ll x_, y_;
		if (x <= (ll)pow(2, n - i - 1)) {
			if (c == 'R') {
				x_ = x;
				y_ = y;
			}
			else {
				x_ = (ll)pow(2, n - i - 1) - x + 1;
				y_ = (ll)pow(2, i + 1) - y + 1;
			}
		}
		else {
			if (c == 'L') {
				x_ = x - (ll)pow(2, n - i - 1);
				y_ = y;
			}
			else {
				x_ = (ll)pow(2, n - i) - x + 1;
				y_ = (ll)pow(2, i + 1) - y + 1;
			}
		}
		x = x_;
		y = y_;
	}
	pair<ll, ll> p;
	p.first = x;
	p.second = y;
	return p;
}

string ans(int n, ll i, ll j) {
	if (n == 1) {
		if (i == 1 && j == 1) return "L";
		if (i == 1 && j == 2) return "R";
		if (i == 2 && j == 1) return "R";
		if (i == 2 && j == 2) return "L";
	}
	string temp;
	if (i <= (ll)pow(2, n - 1)) {
		temp = ans(n - 1, (ll)pow(2, n - 1) - i + 1, (j + 1) / 2);
		pair<ll, ll> p = track(n, temp, j);
		if (p.first == 1) {
			temp += 'L';
			return temp;
		}
		return temp + 'R';
	}
	temp = ans(n - 1, i - (ll)pow(2, n - 1), (j + 1) / 2);
	pair<ll, ll> p = track(n, temp, j);
	if (p.first == 1) {
		temp += 'R';
		return temp;
	}
	return temp + 'L';
}

int main() {
	int n;
	ll i, j;
	cin >> n >> i >> j;
	while (true){
		if (n == 0 && i == 0 && j == 0) break;
		cout << ans(n, i, j) << endl;
		cin >> n >> i >> j;
	}
	return 0;
}


Measured memory_bytes: 3292
#include <stdio.h>

int main() {
  char base, ans;
  scanf("%c", &base);
  if (base == 'A') {
    ans = 'T';
  } else if (base == 'C') {
    ans = 'G';
  } else if (base == 'T') {
    ans = 'A';
  } else {
    ans = 'C';
  }
  printf("%c\n", ans);
  return 0;
}


Measured memory_bytes: 128
#include<stdio.h>
int main()
{
	int a[3];
	int i,sum;
	for(i=0;i<3;i++){
		scanf("%d",&a[i]);
	}
	sum=0;
	for(i=0;i<3;i++){
		sum+=a[i];
	}
	if(sum>=22){
		printf("bust\n");
	}
	else{
		printf("win\n");
	}
	return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <queue>
using namespace std;

int n, k, m = 1, j = 0, mt = 0, mx = 1;
string s;
queue<pair<int, int>> t;

void rm() {
	if (j <= k)
		mx = mt;
	else {
		if (t.front().first == 1) {
			mt -= t.front().second;
			t.pop();
		}
		if (t.front().first == 0) {
			mt -= t.front().second;
			t.pop();
			j--;
		}

		if (mx < mt)
			mx = mt;
	}
}

int main()
{
	cin >> n >> k >> s;

	for (int i = 0; i < n - 1; i++) {
		if (s[i] == s[i + 1])
				m++;
		else {
			t.push(make_pair(s[i] - '0', m));
			mt += m;
			m = 1;

			if(s[i] == '0')
				j++;
			else
				rm();
		}
	}

	mt += m;

	if (s[n - 1] == '0')
		j++;

	rm();

	cout << mx << endl;
	
	return 0;
}


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

#include <algorithm>
#include <cassert>
#include <vector>

namespace atcoder {

// Implement (union by size) + (path compression)
// Reference:
// Zvi Galil and Giuseppe F. Italiano,
// Data structures and algorithms for disjoint set union problems
struct dsu {
  public:
    dsu() : _n(0) {}
    dsu(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

  private:
    int _n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> parent_or_size;
};

}  // namespace atcoder

using namespace std;
using namespace atcoder;
int main(int argc, char const *argv[])
{
	int n,q;
	cin>>n>>q;
	atcoder::dsu d(n);
	int u,a,b;
	while(q--){
		cin>>u>>a>>b;
		if(u==1){
			cout<<d.same(a,b)?"1":"0";
			cout<<"\n";
		}else{
			d.merge(a,b);
		}
	}
	return 0;
}


Measured memory_bytes: 3876
n=int(input())
k=int(input())
d=len(str(n))
from math import factorial as f
def c(n):
  if n<2:
    return 0
  else:
    return f(n)//(f(n-2)*f(2))
def kk(n):
  dd=len(str(n))
  s=9*(dd-1)
  s+=int(str(n)[0])
  return s
def kkk(n):
  d=len(str(n))
  s=81*(d-1)*(d-2)//2
  s+=9*(d-1)*(int(str(n)[0])-1)
  s+=kk(int(str(n)[1:]))
  return s

if d==1 and k!=1:
  print(0)
else:
  if k==1:
    ans=kk(n)
  elif k==2:
    ans=kkk(n)
  else:
    t=0
    for i in range(2,d-1):
      t+=c(i)
    ans=729*t
    ans+=81*c(d-1)*(int(str(n)[0])-1)
    ans+=kkk(int(str(n)[1:]))
  print(ans)

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

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

    long long a[5], N;
    cin >> N >> a[0] >> a[1] >> a[2] >> a[3] >> a[4];

    long long mn = a[0];
    int mn_idx = 0;
    for (int i = 1; i < 5; i++)
    {
        if (a[i] < mn)
        {
            mn = a[i];
            mn_idx = i;
        }
    }

    long long ans = 5;
    if (N > a[mn_idx])
    {
        if (N % a[mn_idx] == 0)
        {
            ans += N / a[mn_idx] - 1;
        }
        else
        {
            ans += N / a[mn_idx];
        }
    }
    cout << ans << endl;

    return 0;
}

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

int main(){
    
    long long int N, i, sum, ans;
    cin >> N;
    long long int a[N], b[N];
    sum = 0;
    
    for (i = 0; i < N; i++){
        cin >> a[i];
        if (i == 0){
            b[i] = a[i];
        } else {
            b[i] = (b[i - 1] + a[i]) % ((long long int)pow(10, 9) + 7);
        }
   }
    
    for (i = 1; i < N; i++){
        sum += a[i] * b[i - 1];
        sum %= ((long long int)pow(10, 9) + 7);
    }
    
    
    cout << sum;

    return 0;
}


Measured memory_bytes: 6708
#include <bits/stdc++.h>
using namespace std;
int main(){
  int H,W;cin>>H>>W;
  vector<vector<string>>c(H,vector<string>(W));
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin>>c.at(i).at(j);
      if(c.at(i).at(j)=="snuke"){
        char x='A';x+=j;cout<<x<<i+1<<endl;i=H;break;
      }
    }
  }
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

namespace CSharpSample01
{

    
    
    class Program
    {

        static int Euclidean(int big, int smoll)
        {
            if(big < smoll)
            {
                int tmp = big;
                big = smoll;
                smoll = tmp;
            }

            while(smoll > 0)
            {
                int amari = big % smoll;
                big = smoll;
                smoll = amari;
            }

            return big;
        }


        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int a = int.Parse(input[0]);
            int b = int.Parse(input[1]);

            Console.WriteLine(Euclidean(a, b));

        }
    }
}


Measured memory_bytes: 17928
#include <bits/stdc++.h>
using namespace std;
int main(){
int A,B;
  cin>>A>>B;
  if(A%3==0 || B%3==0 || (A+B)%3 ==0){
cout<<"Possible"<<endl;
  }
else{
cout<<"Impossible"<<endl;
}
return 0;
}

Measured memory_bytes: 256
var input = '';
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function(chunk) {
    input += chunk;
});
process.stdin.on('end', function() {
    var lines = input.split('\n');
    lines.sort(function(a, b){return b - a})
    lines.slice(0, 3).forEach(function(x) {
        console.log(x);
    });
});

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

using i64 = int64_t;

int main(){
    int n, p;
    cin >> n >> p;
    string s;
    cin >> s;

    if(p == 2 || p == 5){
        i64 ans = 0;
        for(int i=0;i<n;++i){
            if((s[i]-'0')%p == 0)ans += (i+1);
        }
        cout << ans << endl;
        return 0;
    }

    reverse(s.begin(), s.end());
    map<int, i64> mp;
    mp[0] = 1;
    i64 x = 0, ans = 0, b = 1;
    for(int i=0;i<n;++i){
        x = (b*(s[i]-'0') + x) % p;
        ans += mp[x];
        mp[x]++;
        b *= 10;
        b %= p;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1028
$N=<>;/ /,push@{$`},$' for<>;map$q[$_]+=$q[$i]/@$i,@{$i=$_}for++$q[1]..$N;while(--$N){$s=$m=0;$m=($~=$e[$_])>$m?$~:$m,$s+=$~for@$N;$e[$N]=1+$s/@$N;$a<($t=$q[$N]*=$#$N&&($s-$m)/$#$N-$s/@$N)or$a=$t}print"@e"+$a

Measured memory_bytes: 42368
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,i,k,j;
    cin>>n>>k;
    long long int h[n];
    for(i=0;i<n;i++)
        cin>>h[i];
    long long int dp[n];
    dp[0]=0;
    dp[1]=abs(h[1]-h[0]);
    for(i=2;i<n;i++)
    {
        dp[i] = abs(h[i]-h[i-1])+dp[i-1];
        for(j=1;j<=k;j++)
        {
            if(i-j>=0)
            {
                dp[i]=min(dp[i],abs(h[i]-h[i-j])+dp[i-j]);
            }
            else
                break;
        }
    };
    cout<<dp[n-1];
    return 0;
}


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

//Chu_Liu_Edmonds
typedef pair<int,int> point;
typedef pair<int,point> edge;

#define inf 1e9

int solve(vector<edge> &g,int v,int r){
	vector<point> mins(v,point(inf,-1));
	for(int i=0;i<g.size();i++){
		edge tmp = g[i];
		point p = tmp.second;
		mins[p.second]  =  min(mins[p.second],point(tmp.first,p.first));
	}
	mins[r] = point(-1,-1);	
	vector<int> grop(v,0);
	vector<bool> cycle(v,false);
	int cnt=0;
	
	vector<bool> used(v,false);
	for(int i=0;i<v;i++){
		if(used[i])continue;
		vector<int> chain;
		int now = i;
		while(now !=-1&&!used[now]){
			//元を辿る
			used[now]= true;
			chain.push_back(now);
			now = mins[now].second;
		}
		if(now !=-1){
			bool incycle = false;
			for(int j=0;j<chain.size();j++){
				grop[chain[j]]=cnt;
				if(chain[j]==now){
					cycle[cnt] = true;
					incycle = true;
				}
				if(!incycle)cnt++;
			}
		 if(incycle)cnt++;
		}else{
			for(int j=0;j<chain.size();j++){
					grop[chain[j]] = cnt;
					cnt++;
			}	
		}

	}
	if(cnt==v){
		//because root is -1 
		int ans =1;
		for(int i=0;i<v;i++)ans+=mins[i].first;
		return ans;
	}
	int res = 0;
	for(int i=0;i<v;i++){
		if(i != r && cycle[grop[i]])res += mins[i].first;
	}
	//cycle exist ,so make new graph
	vector<edge> newg;
	for(int i=0;i<g.size();i++){
		edge e = g[i];
		point p = e.second;
		int to = p.second;
		int gfrom = grop[p.first];
		int gto = grop[p.second];
		if(gfrom ==gto)continue;
		else if(cycle[gto])	newg.push_back(edge(e.first-mins[to].first,point(gfrom,gto)) );
		else 	newg.push_back(edge(e.first,point(gfrom,gto) ) );
	}
	return res + solve(newg,cnt,grop[r]);
}


int main(){
	int v,e,r;
	cin>>v>>e>>r;
	vector<edge> g;
	for(int i=0;i<e;i++){
		int s,t,w;
		cin>>s>>t>>w;
		point p = point(s,t);
		g.push_back( edge(w,p) );
	}
	cout<<solve(g,v,r)<<endl;
	return 0;
}


Measured memory_bytes: 3280
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int n;
string s;
int a[101]={};
int r,l;

int main(){
	cin>>n>>s;
	for(int i=0;i<n;i++){
		if(s[i]=='('){
			a[i]=1;
		}else if(s[i]==')'){
			a[i]=2;
		}
	}
	for(int i=0;i<n;i++){
		if(a[i]==1){
			for(int j=i+1;j<n;j++){
				if(a[j]==2){
					a[i]=0;
					a[j]=0;
					break;
				}
			}
		}
	}
	for(int i=0;i<n;i++){
		if(a[i]==1){
			r++;
		}else if(a[i]==2){
			l++;
		}
	}
	for(int i=0;i<l;i++){
		cout<<'(';
	}
	cout<<s;
	for(int i=0;i<r;i++){
		cout<<')';
	}
	cout<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

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

		int N = scan.nextInt() ;
		int A = scan.nextInt() ;
		int B = scan.nextInt() ;
		int ans = 0;

		if ( (N * A) <= B) {
			ans = N * A;
		} else {
			ans = B;
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 21588
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>g;

int dfs(int cur,int depth){
	if(depth==g.size())return 1;
	int res=0,temp=-1,temp2=-1;
	for(auto&&i:g.at(cur)){
		if(g.at(i).front()==-1)continue;
		swap(temp,i);
		swap(temp2,g.at(cur).front());
		res+=dfs(temp,depth+1);
		swap(temp2,g.at(cur).front());
		swap(temp,i);
	}
	return res;
}

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n,m; cin>>n>>m;
	g.resize(n);
	for(int i=0;i<m;++i){
		int a,b; cin>>a>>b; --a,--b;
		g.at(a).emplace_back(b);
		g.at(b).emplace_back(a);
	}
	cout<<dfs(0,1)<<"\n"s;
}


Measured memory_bytes: 3664
a, b, k = map(int, input().split())
arr = []
for i in range(k):
    if int((b - a) / 2 + 0.5) >= i:
        arr.append(a + i)
        arr.append(b - i)
    else:
        break
arr = list(set(arr))
arr.sort()
for i in arr:
    print(i)

Measured memory_bytes: 3060
#include<iostream>
#include<cmath>
#include<vector>
#include<set>
#include<algorithm>
#include<tuple>
#include<utility>
#include<cctype>
#include<climits>
#include<map>
#include<queue>
#include<functional>
#include <ios>
#include <iomanip>

using namespace std;
template<class T> void chmax(T& a, T b) {if(a < b){a=b;}}
template<class T> void chmin(T& a, T b) {if(a > b){a=b;}}

#define REP(i,a,n) for(int i=a;i<n;++i)
#define RUP(a,b) ((a+b-1)/(b))
#define ENT "\n"
#define REV(v) reverse(v.begin(),v.end())
#define SRTV(v) sort(v.begin(),v.end())
#define SRTAG(a,n) sort(a,a+n,greater<>())
#define MOD 1000000007

typedef long long ll;
typedef tuple<int,int,bool> Tb;
typedef tuple<ll,ll,ll> Tl;

int atcoder(){
    //入力
    ll n,m;
    cin >> n >> m;
    ll x[m];
    REP(i,0,m) cin >> x[i];
    sort(x,x+m);
    ll l[m];
    REP(i,0,m-1) l[i]=x[i+1]-x[i];
    sort(l,l+(m-1));
    if(n>=m) cout << 0 << ENT;
    else{
        ll ans=0;
        REP(i,0,m-n) ans += l[i];
      	cout << ans << ENT;
    }
    return 0;
}

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


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

int main(){
  map<int,bool> A,B;
  
  int N,M;
  cin>>N>>M;
  for(int i=0;i<M;i++){
    int a,b;
    cin>>a>>b;
    if(a>b)swap(a,b);
    if(a==1)A[b]=true;
    if(b==N)B[a]=true;
  }
  for(int i=1;i<=N;i++){
    if(A[i]&&B[i]){
      cout<<"POSSIBLE"<<endl;
      return 0;
    }
  }
  cout<<"IMPOSSIBLE"<<endl;
  return 0;
}


Measured memory_bytes: 18944
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;

signed main(){
    cin.tie(0); 
    ios::sync_with_stdio(false);
    double n;
    int tmp_i;
    double tmp_f;
    double comp;
    cin>>n;
    while( n>=0.0 ){
        char binari[20],temp;
        comp = 0.5;
        tmp_i = (int)n;
        tmp_f = n-(float)tmp_i;
        for(int i=0;i<8;i++){
            if(tmp_i % 2 == 0){
                binari[i] = '0';
            }else{
                binari[i] = '1';
            }
            tmp_i = tmp_i / 2;
        }
        for(int i=0;i<4;i++){
            temp = binari[i];
            binari[i] = binari[8-i-1];
            binari[8-i-1] = temp;
        }
        binari[8] = '.';
        for(int i=0;i<4;i++){
            if(tmp_f >= comp){
                binari[8+i+1] = '1';
                tmp_f = tmp_f - comp;
            }else{
                binari[8+i+1] = '0';
            }
            comp = comp / 2;
        }
        if( ((float)tmp_i + tmp_f) == 0.0){
            cout<<binari<<"\n";
        }else{
            cout<<"NA\n";
        }
        cin>>n;
    }
    return 0;
}




Measured memory_bytes: 3196
#include<iostream>
#include<string>
#include<vector>
#include<numeric>
#include<math.h>
#include<algorithm>
#include<iomanip>
#include<bitset>
using namespace std;

int main() {

	string S;
	cin >> S;

	if (S == "ABC") {
		cout << "ARC" << endl;
	}
	else {
		cout << "ABC" << endl;
	}

	return 0;
}


Measured memory_bytes: 3624
/**
                 MD.Faysal Hasan
                Comilla Univesity               **/

#include<bits/stdc++.h>
#include<algorithm>
#include<string>
#include <stdlib.h>
using namespace std;

typedef long long int         lli;
typedef long long             ll;
typedef unsigned long long    ull;
typedef long double           ldb;
const   ll   N = 2e5+5;

#define         rep(i,n)       for ( i=0 ; i<n ; i++ )
#define         rep1(i,n)      for ( i=1 ; i<=n ; i++ )
#define         sajo(str)      sort(str.begin(),str.end())
#define         rsajo(str)     reverse(str.begin(),str.end())
#define         pi             3.14159265359
#define         nel            printf("\n");
#define         gcd(a,b)       __gcd(a,b)
#define         lcm(a,b)       (a/gcd(a,b))*b
#define         yes            cout<<"Yes"<<"\n";
#define         no             cout<<"No"<<"\n";
#define         pb             push_back
#define         pii            pair< ll , ll >
#define         ppi            pair< pii , ll >
#define         ff             first
#define         ss             second
#define         Faysal         ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int fact(int n)
{
   if(n==0)
      return(1);
   return(n*fact(n-1));
}
int prm(ll n)
{
    ll j=0;
    while (n % 2 == 0){
        j++;
        n = n/2;}
    for (ll i = 3; i*i <= n ; i = i + 2){
        while (n % i == 0){
           j++;
        n = n/i;}
    }
    if (n > 2)
        j++;
    return j;
}

int main(){Faysal

    ll ans,cnt,sum,mx,mn,chk;

    ll n,q,a,b,x,y,i,j,k;

    bool f;

    cin>>a>>n;
    vector<ll>v(n);
    cnt=0;
    rep(i,n)
    {cin>>v[i];
    cnt+=v[i];}

    if(cnt>=a) {yes;}
    else no;

    return 0;

}


Measured memory_bytes: 1024
k = gets.to_s.to_i

q = Array.new(9){|i| i+1 }

(k-1).times do
  s = q.shift
  -1.upto(1) do |i|
    a = s % 10 + i
    q.push s * 10 + a if 0 <= a && a <= 9
  end
end

p q[0]

Measured memory_bytes: 3964
#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<double> v(N);
    rep(i, N) cin >> v[i];

    sort(v.begin(), v.end());
    rep(i, N-1) {
        v[i+1] += v[i];
        v[i+1] /= 2.0;
    }

    cout << fixed << setprecision(10);
    cout << v[N-1] << endl;

    return 0;
}

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

int main() {
  
	string s;	
	cin >> s;
	int N = s.size();

	if(N == 3){
		if(s.at(0) == s.at(2)){
			cout << "Yes" << endl;
			return 0;
		}
		else{
			cout << "No" << endl;
			return 0;
		}
	}

		if(N == 5){
		if(s.at(0) == s.at(1) && s.at(0) == s.at(3) && s.at(0) == s.at(4)){
			cout << "Yes" << endl;
			return 0;
		}
		else{
			cout << "No" << endl;
			return 0;
		}
	}

	if(N >= 7 && N % 4 == 1){
		for(int i = 1; i <=(N-3)/4+1;i++){
			if(s.at(i-1) != s.at((N-(2*i-1))/2-1) || s.at(i-1) != s.at((N+(2*i+1))/2-1) || s.at(i-1) != s.at(N-i)){
				cout << "No" << endl;
				return 0;
			}
		}
		cout << "Yes" << endl;
	}

	if(N >= 7 && N % 4 == 3){
		for(int i = 1; i <=(N-3)/4+1;i++){
			if(s.at(i-1) != s.at((N-(2*i-1))/2-1) || s.at(i-1) != s.at((N+(2*i+1))/2-1) || s.at(i-1) != s.at(N-i)){
				cout << "No" << endl;
				return 0;
			}
		}
		cout << "Yes" << endl;
	}
}


Measured memory_bytes: 256
function Main(input) {
  var arr = input.split(" ");
  
  var count5 = 0;
  var count7 = 0;
  
  for(var a of arr) {
    if(a == 5){
      count5++;
    }else if(a == 7){
      count7++;
    }
  }

  if(count5 == 2 && count7 == 1){
    console.log("YES");
    }else{
    console.log("NO");
  }
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7372
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdio.h>

using namespace std;

//typedefリスト
typedef vector<long long int> vint;
typedef vector<vector<long long int>> vvint;
typedef vector<string> vstr;
typedef long long int llint;

llint gcd(llint x, llint y) {
	while (y != 0) {
		if (x > y) {
			llint r = x % y;
			x = y;
			y = r;
		}
		else {
			llint r = y % x;
			y = r;
		}
	}
	return x;
}

int main(void) {
	int m, f, b,cost;
	cin >> m >> f >> b;
	cost = b - m;
	if (cost <= f) {
		if (cost < 0)cost = 0;
		cout << cost << endl;
	}
	else {
		cout << "NA" << endl;
	}
}



Measured memory_bytes: 3112
#include<stdio.h>
#define MAX 500000
#define INFTY  2000000000

int L[MAX/2+2], R[MAX/2+2];
int cnt;

void merge(int A[], int left, int mid, int right){
  int i, j, k, n1, n2;

  n1 = mid - left;
  n2 = right - mid;
  for( i = 0 ; i < n1 ; i++ ){
    L[i] = A[left+i];
  }
  for( i = 0 ; i < n2 ; i++ ){
    R[i] = A[mid+i];
  }
  L[n1] = R[n2] = INFTY;
  i = j = 0;
  for( k = left ; k < right ; k++ ){
    cnt++;
    if( L[i] <= R[j] ){
      A[k] = L[i];
      i = i +1;
    }
    else {
      A[k] = R[j];
      j = j + 1;
    }
  }
}

void mergeSort(int A[], int left, int right){
  int mid;
  if( left + 1 < right ){
    mid = ( left + right ) / 2;
    mergeSort(A, left, mid);
    mergeSort(A, mid, right);
    merge(A, left, mid, right);
  }
}

int main(){
  int A[MAX], n, i;
  cnt = 0;

  scanf("%d", &n);
  for( i = 0 ; i < n ; i++ ){
    scanf("%d", &A[i]);
  }

  mergeSort(A, 0, n);

  for( i = 0 ; i < n ; i++ ){
    if( i ) printf(" ");
    printf("%d", A[i]);
  }
  printf("\n");
  printf("%d\n", cnt);
  return 0;
}



Measured memory_bytes: 5616
#include <string>
#include <iostream>
#include <set>
#include <array>
#include <queue>
 
using namespace std;
 
// 文字列一つ受け取る場合
// string s;
// 整数(max 2^31-1 or 10^9)一つ受け取る場合
// int x;
int k;
// int n;
// set<int> a;
 
 
 
int main(){
    cin >> k;
    //  array<long int, 10> row{0,1,1,1,1,1,1,1,1,1};
    queue<long int> q;
    for(int i = 1;i<10;i++){
        q.push(i);
    }
    int count = 0;
    long int output;
    while(true){
        long int x = q.front();
        q.pop();
        count++;
        // 今xに入ってるやつがcountばんめ
        if(count == k){
            output = x;
            break;
        }
        int r = x % 10;
        if(r!=0){
            q.push(x*10+r-1);
        }
        q.push(x*10+r);
        if(r!=9){
            q.push(x*10+r+1);
        }
    }
    cout << output;  
}

array<long int, 10> nextRow(array<long int, 10> row){
    long int n0 = row[0] + row[1];
    long int n1 = row[0] + row[1] + row[2];
    long int n2 = row[3] + row[1] + row[2];
    long int n3 = row[3] + row[4] + row[2];
    long int n4 = row[3] + row[4] + row[5];
    long int n5 = row[6] + row[4] + row[5];
    long int n6 = row[6] + row[7] + row[5];
    long int n7 = row[6] + row[7] + row[8];
    long int n8 = row[9] + row[7] + row[8];
    long int n9 = row[9] + row[8];
    array<long int,10> next{n0,n1,n2,n3,n4,n5,n6,n7,n8,n9};
    return next;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <functional>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
bool I[32][100009]; int N, C, s[100009], t[100009], c[100009], dp[100009];
int main() {
	cin >> N >> C;
	for (int i = 0; i < N; i++) {
		cin >> s[i] >> t[i] >> c[i];
		for (int j = s[i]; j < t[i]; j++)I[c[i]][j] = true;
	}
	for (int i = 1; i <= C; i++) {
		int F = 0;
		for (int j = 1; j <= 100008; j++) {
			if (I[i][j - 1] == false && I[i][j] == true)F = j;
			if (I[i][j - 1] == true && I[i][j] == false) {
				dp[j]--; dp[F - 1]++;
			}
		}
	}
	for (int i = 1; i <= 100008; i++)dp[i] += dp[i - 1];
	int maxn = 0;
	for (int i = 0; i <= 100008; i++)maxn = max(dp[i], maxn);
	cout << maxn << endl;
	return 0;
}


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

int main( void )
{
    int x;
    cin >> x;
    
    if ( x < 1200 )
        cout << "ABC" << endl;
    else
        cout << "ARC" << endl;
    
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<iomanip>

using namespace std;

int main() {
    int n, x, y;
    double p1=0, p2=0, p3=0, pm=0;
    int X[101], Y[101];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        X[i] = x;
    }
    for (int j = 0; j < n; j++) {
        cin >> y;
        Y[j] = y;
    }
    for (int k = 0; k < n; k++) {
        p1 += fabs(X[k]-Y[k]);
        p2 += pow(fabs(X[k]-Y[k]), 2);
        p3 += pow(fabs(X[k]-Y[k]), 3);
        pm = (pm < fabs(X[k]-Y[k]) ? fabs(X[k]-Y[k]) : pm);
    }
    printf("%.6f\n", p1);
    printf("%.6f\n", sqrt(p2));
    printf("%.6f\n", cbrt(p3));
    printf("%.6f\n", pm);
    return 0;
}



Measured memory_bytes: 3340
#include <bits/stdc++.h>
using namespace std;
#define __ <<" "<<
#define ___ <<" "
#define bash push_back
#define ALL(x) x.begin(),x.end()
//#define int long long

struct IoSetup {
    IoSetup() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout <<fixed<<setprecision(12);
        cerr <<fixed<<setprecision(12);
    }
}IoSetup;

typedef long long ll;
typedef pair < int , int >  pii;
static constexpr const signed int INF = 0x3f3f3f3f;
static constexpr const signed long long LINF = 0x3f3f3f3f3f3f3f3fLL;
static constexpr const signed int MOD = 1000000007;
static constexpr const signed int dx[]={1,0,-1,0,1,1,-1,-1};
static constexpr const signed int dy[]={0,-1,0,1,-1,1,-1,1};

bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && x<w && y<h);}
template<class T>T abs(T &x){return x<0 ? -x : x;}
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 (b<a) { a=b; return 1; } return 0; }
int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}

int n, t;
int a[3030],b[3030];
vector<pii> x;
int mem[3030][3030];

int dp(int i, int j) {

    if(i==n) return 0;
    if(j>=t) return 0;

    if(~mem[i][j])
        return mem[i][j];    
    
    return mem[i][j] = max(dp(i+1, j), dp(i+1, j+x[i].first)+x[i].second);
    
}

signed main() {

    cin >> n >> t;

    for(int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        x.bash(pii(a[i],b[i]));
    }

    
    sort(ALL(x));

    memset(mem,-1,sizeof(mem));

    cout << dp(0,0) << endl;
    
    return 0;
}



Measured memory_bytes: 36480
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
vector<ll> convert(ll i){
    vector<ll> a;
    while(i>0){
        a.push_back(i%2);
        i/=2;
    }
    reverse(a.begin(),a.end());
    return a;
}
ll binpow(ll x,ll y){
    ll res=1;
    while(y>0){
        if(y&1)
            res*=x;
        y>>=1;
        x*=x;
    }
    return res;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll n,m,i,k,j,temp,num,bit,ans=0,flag=0;
    cin>>n>>m;
    vector<ll> adj[15];
    ll arr[m],count=0;
    for(i=0;i<m;i++){
        cin>>k;
        for(j=0;j<k;j++){
            cin>>temp;
            adj[i].push_back(temp);
        }
    }
    for(i=0;i<m;i++)
        cin>>arr[i];
    num=binpow(2,n);
    num-=1;
    bit=ll(log2(num))+1;
    for(i=0;i<=num;i++){
        flag=0;
        vector<ll> a;
        a=convert(i);
        ll rem=bit-a.size();
        a.insert(a.begin(),rem,0);
        for(j=0;j<m;j++){
            count=0;
            for(k=0;k<adj[j].size();k++){
                if(a[adj[j][k]-1]==1)
                    count+=1;
            }
            if(arr[j]==0 && count%2==0)
                flag=0;
            else if(arr[j]==1 && count%2==1)
                flag=0;
            else
                flag=1;
            if(flag==1)
                break;
        }
        if(flag==0)
            ans+=1;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

int main(void) {
    int S, W;
    cin >> S >> W;
    if(S <= W) {
        cout << "unsafe" << endl;
    } else {
        cout << "safe" << endl;
    }
    return 0;
}


Measured memory_bytes: 3620
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Integer a = nextInt(sc);
        if(a < 105) {
            System.out.println(0);
        }else{
            int num = 1;
            for(int i = 107;i <= a;i+=2){
                if(result(i)) num++;
            }
            System.out.println(num);
        }
        sc.close();
    }

    static int nextInt(Scanner sc){
        return Integer.parseInt(sc.next());
    }

    static boolean result(Integer a){
        int count = 0;
        for (int i = 1;i <= a;i++){
            if(a % i == 0) {
                count++;
                if(count > 8){
                    return false;
                }
            }
        }
        if(count == 8) {
            return true;
        }else{
            return false;
        }
    }

}



Measured memory_bytes: 23252
#include <algorithm>
#include <cassert>
// #include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
// #include <random>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

/*
unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 g1.seed(seed1);
*/
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<pii, pii> ppiipii;
typedef pair<int, ppiipii> pippiipii;
typedef pair<int, pii> pipii;
typedef pair<pii, int> ppiii;
typedef pair<int, ppiii> pippiii;
typedef pair<int, ll> pill;
typedef pair<int, double> pid;
typedef pair<string, string> pss;
// note to self, the below two triggers someone
typedef pair<ll, ll> pll;
typedef pair<ll, int> plli;
typedef long double ld;

int a[100005];
int b[100005];
int c[100005];

int main() {
  int n;
  scanf("%d", &n);
  for(int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  for(int i = 0; i < n; i++) {
    scanf("%d", &b[i]);
  }
  for(int i = 0; i < n; i++) {
    scanf("%d", &c[i]);
  }
  sort(a, a+n);
  sort(b, b+n);
  sort(c, c+n);
  ll ret = 0;
  int aCan = 0;
  int cCan = n;
  for(int i = 0; i < n; i++) {
    while(aCan < n && a[aCan] < b[i]) aCan++;
    while(cCan > 0 && c[n-cCan] <= b[i]) cCan--;
    ret += aCan * (ll)cCan;
  }
  printf("%lld\n", ret);
}


Measured memory_bytes: 1408
tmp = (input().split(" "))
H = int(tmp[0])
W = int(tmp[1])

datas = [input() for i in range(0, H, 1)]

array = []

for data in datas:
  tmp = [x for x in list(data)]
  array.append(tmp)

for i in range(0, H, 1):
  for j in range(0, W, 1):
    
    cnt = 0
    
    #空きマスでない場合
    if array[i][j] == "#":
      continue
      
    else:

      for l in range(-1, 2, 1):
        for m in range(-1, 2, 1):
                
          no1 = i + l
          no2 = j + m

          if i == no1 and j == no2:
            continue

          try:

            if no1 < 0 or no2 < 0:
              continue
              
            else:
              if array[no1][no2] == "#":
                cnt += 1
              else:
                pass
            
          except:
            pass
          
      array[i][j] = str(cnt)
      
for x in (array):
  print("".join(x))
      

        
        
        

Measured memory_bytes: 3188
#include<iostream>
using namespace std;
int main (void){
  	long long a,b,c=0,d=0 ,r=0,tmp=0;

  std::cin >> a >> b;
	c = a;
  	d = b;
  /* 自然数 a > b を確認・入替 */
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }

  /* ユークリッドの互除法 */
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
  std::cout << (c*d)/b;
return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3


def read_h(typ=int):
    return list(map(typ, input().split()))


def read_v(n, m=1, typ=int):
    return [tuple(map(typ, input().split())) if m > 1 else typ(input()) for _ in range(n)]


def main():
    N, = read_h()
    s = read_v(N, typ=str)
    M, = read_h()
    t = read_v(M, typ=str)

    cnt = {}
    for si in s:
        cnt[si] = cnt.get(si, 0) + 1
    for ti in t:
        cnt[ti] = cnt.get(ti, 0) - 1

    ans = max(0, *cnt.values())
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; 
#define INF 1000000000
#define mod 1000000007
using ll=long long;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
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 (b<a) { a=b; return 1; } return 0; }
#define int ll

struct UnionFind{
    vector<int> par;
    vector<int> siz;
    int c;//親の個数(グループ数)
    void init(int n){
        c=n;
        for(int i=0;i<n;i++){
            par.push_back(i);
            siz.push_back(1);
        }
    }
    UnionFind(int n){
        init(n);
    }
    int root(int x){
        //根を返す
        return(par[x]==x?x:(par[x]=root(par[x])));
    }
    bool sameParent(int x,int y){
        return(root(x)==root(y));
    }
    void unite(int x, int y){
        x=root(x);y=root(y);
        if(x==y)    return;
        if(siz[x]<siz[y]) swap(x,y);
        siz[x] += siz[y];par[y]=x;c--;
    }
    int size(int x){
        return siz[root(x)];
    }
};
//一番上の親探るときはparじゃなくてroot使え

int geta=100000;
vector<pair<ll,ll>> cnt(geta*2,make_pair(0,0));
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);

    UnionFind uf(geta*2);
    int n;cin>>n;
    rep(i,n){
        int x,y;cin>>x>>y;x--,y--;
        uf.unite(x,y+geta);
    }

    rep(i,geta){
        cnt[uf.root(i)].first++;
    }
    rep(i,geta){
        cnt[uf.root(i+geta)].second++;
    }
    ll ans=0;
    rep(i,geta*2){
        ans+=cnt[i].first*cnt[i].second;
    }
    ans-=n;
    cout<<ans<<endl;
    return 0;
}


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

typedef long long ll;
#define ALL(l)  (l).begin(),(l).end()
#define rep(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define pb push_back
using namespace std;

//const ll mod =  1000000007;
//const ll maxn = 1000000000;

//---------------------------------------------------------------------------------------------------
using vi = vector<int>; // intの1次元の型に vi という別名をつける
using vll = vector<ll>; // intの1次元の型に vi という別名をつける
using vvll = vector<vll>; // intの2次元の型に vvi という別名をつける
using vs = vector<string>; // stringの1次元の型に vs という別名をつける
using pll = pair<ll, ll>; // これ以降 pii という型名はpair<ll, ll> と同じ意味で使える
//---------------------------------------------------------------------------------------------------

int main() {
    ll n,ans=2;
    cin>>n;
    cout<<n<<": ";
    vll a;
    while(1){
        if(n%ans==0){
            //cout<<ans<<" ";
            a.pb(ans);
            n/=ans;
        }else{
            ans++;
        }
        if(ans>100000)break;
    }
    if(n>1)a.pb(n);
    rep(i,a.size()-1){
        cout<<a.at(i)<<" ";
    }
    cout<<a.at(a.size()-1)<<endl;
}


Measured memory_bytes: 3160
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,k;
    cin>>a>>b>>c>>k;

    if(a>b && a>c)
        cout<<(a*pow(2,k))+b+c;
    else if(b>c)
        cout<<a+(b*pow(2,k))+c;
    else
        cout<<a+b+(c*pow(2,k));
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define DEBUG(x) cout << #x << " = " << x << endl
#define pb push_back
using namespace std;
typedef long long ll;


const int MAXN = 400005;
ll a[MAXN];
ll l[MAXN];
ll r[MAXN];
ll INF = 1e16;
multiset<ll> ms;

int main()
{
    //freopen("input.txt", "r", stdin);
    int n;
    cin >> n;
    for (int i = 0; i < 3*n; i++)
        cin >> a[i];

    ll sum = 0;
    for (int i = 0; i < n; i++)
    {
        ms.insert(a[i]);
        sum += a[i];
    }
    l[n-1] = sum;

    for (int i = n; i < 2*n; i++)
    {
        if (a[i] > *(ms.begin()))
        {
            sum -= *(ms.begin());
            ms.erase(ms.begin());
            sum += a[i];
            ms.insert(a[i]);
        }
        l[i] = sum;
    }

    ms.clear();
    sum = 0;
    for (int i = 2*n; i < 3*n; i++)
    {
        ms.insert(-a[i]);
        sum += a[i];
    }
    r[2*n] = sum;


    for (int i = 2*n-1; i >= n; i--)
    {
        if (a[i] < -(*(ms.begin())))
        {
            sum += *(ms.begin());
            ms.erase(ms.begin());
            sum += a[i];
            ms.insert(-a[i]);
        }
        r[i] = sum;
    }

    ll ans = -INF;
    for (int i = n-1; i < 2*n; i++)
    {
        ans = max(l[i] - r[i+1], ans);
    }

    cout << ans;
    return 0;
}



Measured memory_bytes: 12288
#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++)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int		main(void)
{
	int a, b, c;
	cin >> a >> b >> c;
	cout << (a+b+c >21 ? "bust" : "win");
}


Measured memory_bytes: 256
//問題やり直し
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string T[4] = {"maerd", "remaerd", "esare", "resare"};

int main(void)
{
  string S;
  cin >> S;
  reverse(S.begin(),S.end());
  // cout << S << endl;

  while(S.length() != 0){
    for(int i=0; i<4; i++){
    if(S.compare(0,T[i].length(),T[i]) == 0){
      S.erase(0,T[i].length());
      break;
    }
    if(i==3){
      cout << "NO\n";
      return 0;
    }
  }
}
  cout << "YES\n";
  return 0;
}


Measured memory_bytes: 512
#include<cstdio>
#include <string.h>
#include<math.h>
#include<algorithm>


using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
const int INF=1001001001;
int A,B;
int N;
long long int DP[20][20];


int main(){
	while(1){
	memset(DP,0,sizeof(DP));
	scanf("%d %d",&A,&B);
	if(A==0&&B==0)break;
	scanf("%d",&N);

	rep(i,N){
		int a,b;
		scanf("%d %d",&a,&b);
		DP[a-1][b-1]=-1;
	}
	rep(i,A){
		rep(j,B){
			if(DP[i][j]==-1)continue;
			if(i==0&&j==0){DP[0][0]=1;continue;}
			if(i==0){if(DP[i][j-1]>0)DP[i][j]=1;continue;}
			else if(DP[i-1][j]!=-1)DP[i][j]+=DP[i-1][j];
			if(j==0){if(DP[i-1][j]>0)DP[i][j]=1;continue;}
			else if(DP[i][j-1]!=-1)DP[i][j]+=DP[i][j-1];
		}
	}
	printf("%lld\n",DP[A-1][B-1]);
	
	}
}

Measured memory_bytes: 1032
# -*- coding: utf-8 -*-
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    L = [0] * N
    for i in range(N):
        s, p = i2s().split()
        L[i] = (s, int(p), i + 1)

    L.sort(key=lambda x: (x[0], -x[1]))
    for l in L:
        print(l[2])

main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#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++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
const ll inf=1e9+7;
const ll INF=1e18;

int main(){
    string s;cin>>s;
    int g=0;int p=0;int ans=0;
    rep(i,s.size()){
        if(g==p){
            if(s[i]=='p')ans--;
            g++;
        }
        else{
            if(s[i]=='g')ans++;
            p++;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3748