akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define REP(i, n) for(int i = 0; i < (int)n; ++i)

using namespace std;

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

    int K;
    string S;
    cin >> K >> S;
    if (S.length() <= K) cout << S << endl;
    else {
        REP(i, K) cout << S[i];
        cout << "..." << endl;
    }
}

Measured memory_bytes: 3644
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int i,j,k,n,m,a[210001],ans;
int main(){
	scanf("%d%d",&n,&m);memset(a,0,sizeof(a));
	for (i=1;i<=n;i++) scanf("%d",&k),a[k]++;
	sort(a+1,a+1+n);ans=0;
	for (i=1;i<=n-m;i++) ans+=a[i];
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1024
import math
A,B,H,M = map(int, input().split())

a = abs((M*6)-((H*30)+(M*0.5)))%360
b = math.radians(min(a,abs(360-a)))
ans = -2*A*B*math.cos(b)+A**2+B**2

print(math.sqrt(ans))


Measured memory_bytes: 9344
#include <bits/stdc++.h>
using namespace std;
 
#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
#define MAXX 500005
#define INF INT_MAX

#define PI   3.14159265358979323846264338327950
 
#define PB push_back 
#define PF push_front
#define F first
#define S second
 
#define fixx(n) fixed << setprecision(n) 
 
#define ll 	 long long 
 
#define mod  1000000007



int main()
{
	FAST;
	string s;
	cin >> s;
	s[3] = '8';
	cout << s;
	return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <math.h>
using namespace std;
int main() {
int a,b,c,x;
int num =0;
cin>>a>>b>>c>>x;
for(int s=0;s<=a;s++){
  for(int t=0;t<=b;t++){
    for(int u=0;u<=c;u++){
      if(500*s+100*t+50*u==x)num++;
      }
    }
  }
      cout<<num<<endl;
return 0;
}
 

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

#define ALL(c) (c).begin(),(c).end()
#define SORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define IN(v) int v;cin>>v;
#define OUT(v) cout<<v<<endl

const int INF = 1000000000;
const string alphabet = "abcdefghijklmnopqrstuvwxyz";

int main() {
  IN(N);

  map<char, int> m;
  for (const auto& c : alphabet)
    m[c] = INF;
  REP(i, N) {
    string s;
    cin >> s;
    SORT(s);
    int count = 0;
    char before = ' ';
    for (const auto& c : alphabet) {
      int count = (int)(upper_bound(ALL(s), c) - lower_bound(ALL(s), c));
      m[c] = min(m[c], count);
    }
  }
  for (const auto& c : alphabet) {
    if (m[c] != INF)
      REP(i, m[c])
        cout << c;
  }
  cout << "\n";

  return 0;
}


Measured memory_bytes: 256
A,B,C = map(int, input().split())

"""
A+B+2(AB) < C
A+B-C < -2(AB)

1.A+B < C
&
(A+B-C)**2 < 4AB
"""

cond1 = A+B < C
cond2 = (C-A-B)**2 > 4*A*B


if cond1 and cond2:
  ans = 'Yes'
else:
  ans = 'No'

print(ans)

Measured memory_bytes: 2940
import java.util.Scanner;

class Main{
    static final int dayOfNormalYear = 195;
    static final int lastDay = 196471;


    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n = sc.nextInt();
        while(n > 0){
            int y = sc.nextInt();
            int m = sc.nextInt();
            int d = sc.nextInt();
            
            int countYearDivided3 = 0;
            int day = 0;
            for(int i=1;i<y;i++){
                if (i %3 == 0){
                    countYearDivided3 ++;
                }
            }
            day += (dayOfNormalYear*(y-1)) + (countYearDivided3*5);
            if(y % 3 == 0) {
                day += ((m-1) * 20) + d;
            } else {
                day += ((m-1) * 20) - Math.round((m-1)/2) + d;
            }

            System.out.println(lastDay - day);
            n--;
        }
    }
}


Measured memory_bytes: 26480
#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<stack>
#include<iomanip>

using namespace std;

#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPL(i,a,n) for(ll i=a;i<n;++i)
#define RUP(a,b) ((a+b-1)/(b))
#define ENT "\n"
#define SRTVG(v) sort(v.begin(),v.end(),greater<>())
#define SRTV(v) sort(v.begin(),v.end())
#define SRTAG(a,n) sort(a,a+n,greater<>())
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define INF LLONG_MAX/2

typedef long long ll;
typedef tuple<int,int,bool> Tb;
typedef pair<int,int> Pii;
typedef vector<int> Vi;

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;}}
template<class T> void YesNo(T& a) {if(a){cout << "Yes" << ENT;}else{cout << "No" << ENT;}}
template<class T> void YESNO(T& a) {if(a){cout << "YES" << ENT;}else{cout << "NO" << ENT;}}

int atcoder(){
    string s,t1="",t2="";
    cin>>s;
    int n = (int)s.length();
    REP(i,0,n){
        if(i%2==1){
            t1+="1";
            t2+="0";
        }else{
            t1+="0";
            t2+="1";
        }
    }
    int a=0,b=0;
    REP(i,0,n){
        if(s[i]!=t1[i]) a++;
        if(s[i]!=t2[i]) b++;
    }
    cout<<min(a,b)<<ENT;
    return 0;
}


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


Measured memory_bytes: 720
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <stdio.h>
#include <string.h>
#include <cstdlib>
#include <math.h>
#define INF 2000000000
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
#define ll long long
#define PL pair<long long, long long>
#define P pair<int,int>
#define mk make_pair
#define en endl;
#define WHITE 0
#define BLACK 2
#define GRAY 1
#define repi(start,end) for(int i=start; i<end; i++)
#define repj(start,end) for(int j=start; j<end; j++)
#define repk(start,end) for(int k=start; k<end; k++)
#define repl(start,end) for(int l=start; l<end; l++)
#define RE return 0;

long long x[100002];
int v[100002];
long long a[100002];
long long b[100002];

int main() {
  int n;
  ll c,ans=0;
  cin>>n>>c;
  
  x[0]=0;
  v[0]=0;

  repi(1, n+1) cin>>x[i]>>v[i];
  
  x[n+1]=c;
  v[n+1]=0;
  
  repi(1, n+1) a[i]=a[i-1]+v[i]-(x[i]-x[i- 1]);
  repi(1, n+1) a[i]=max(a[i], a[i-1]);
  
  for (int i=n; i>=1; i--) b[i] = b[i+1]+v[i]-(x[i+1]-x[i]);
  for (int i=n; i>=1; i--) b[i] = max(b[i], b[i+1]);
  
  //cout<<"b["<<1<<"]: "<<b[1]<<en
  repi(1, n+1) {
    ans=max(ans, a[i]);
    ans=max(ans, a[i]-x[i]+b[i+1]);
    //cout<<"    3  : "<<a[i]-x[i]+b[i+1]<<en
    ans=max(ans, b[i]);
    //cout<<"    2   b["<<i<<"]: "<<b[i]<<en
    ans=max(ans, b[i]-(c-x[i])+a[i-1]);
    //cout<<"    4  : "<<b[i]-(c-x[i])+a[i-1]<<en
  }
  
  cout<<ans<<en
  
  RE
}


Measured memory_bytes: 2944
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
template <class T>
using V = vector<T>;
template <class T>
inline void chmin(T &a, const T &b) { a = min(a, b); }
template <class T>
inline void chmax(T &a, const T &b) { a = max(a, b); }
template <class T>
inline bool kbit(const T &x, const int &k) { return ((x >> k) & 1LL); }
inline int popcount(const int &n) { return __builtin_popcount(n); }
inline ll popcountll(const ll &n) { return __builtin_popcountll(n); }
inline ll mask(const ll &k) { return (1LL << k) - 1LL; }
template <class T>
void zip(V<T> &v) {
    sort(all(v));
    v.erase(unique(all(v)), v.end());
}
template <class T>
int lwb(V<T> &v, const T &x) { return lower_bound(all(v), x) - v.begin(); }
void dump() {
    cerr << '\n';
}
template <class Head, class... Tail>
void dump(Head &&head, Tail &&... tail) {
    cerr << head << (sizeof...(Tail) == 0 ? " " : ", ");
    dump(std::move(tail)...);
}
template <class T>
void print(const vector<T> &v) {
    for (int i = 0; i < v.size(); i++) cout << v[i] << (i + 1 == v.size() ? '\n' : ' ');
}
template <class T>
void read(vector<T> &v) {
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}
constexpr char sp = ' ', newl = '\n';
constexpr int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll MOD = 1e9 + 7;
//////////////////////////////////////////////INSERT ABOVE HERE
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    V<int> a(n);
    read(a);
    int res = 0;
    sort(all(a));
    for (int i = 0; i < k; i++) {
        res += a[i];
    }
    cout << res << newl;
}

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

int main()
{
	//int h, w,   q, D, ax[90001], ay[90001], l[100000], r[100000];
	//long long int  i, j, k, l, a[100000], b[1000], c[1000], d[1000], e = 0, n, m, ten[1000] = { 0 }, ans = 0;
	//int  i, j, k, l, a[100002], b[1000], c[1000], d[1000], e = 0, n, m, ten[1000] = { 0 }, ans = 0;
	int a, b, c, d, e, f, g, masu[101][101];
	//string st[1000], stm[1000];

	cin >> a;
	cin >> b;
	cout << "100 100"<<endl;

	for (d = 0; d < 25; d++)
	{


		for (c = 0; c < 50; c++)
		{
			if (a > 1)
			{
				cout << ".#";
				a--;
			}
			else
			{
				cout << "##";
			}

		}
		cout << endl;
		for (e = 0; e < 50; e++)
		{
			cout << "##";

		}
		cout << endl;
	}
	for ( d = 0; d < 50; d++)
	{
		cout << "..";

	}
	cout << endl;

	for (d = 0; d < 24; d++)
	{


		for (c = 0; c < 50; c++)
		{
			if (b > 1)
			{
				cout << ".#";
				b--;
			}
			else
			{
				cout << "..";
			}

		}
		cout  << endl;
		for (e = 0; e < 50; e++)
		{
			cout << "..";

		}
		cout << endl;

	}
	for (d = 0; d < 50; d++)
	{
		cout << "..";

	}
	cout << endl;

	// 出力
	return 0;
}

Measured memory_bytes: 256
#define __USE_MINGW_ANSI_STDIO 0
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#define MOD 1000000007
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, A;
    cin >> N >> A;
    cout << N*N-A << "\n";
    return 0;
}

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

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using vint = vector<int>;
template<typename T> using uset = unordered_set<T>;
template<typename T1, typename T2> using umap = unordered_map<T1, T2>;

constexpr int INF = (1 << 30) - 1;
constexpr ll LLINF = 1LL << 60;
constexpr int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr char el = '\n';
constexpr int mod = 1000000007;

template<typename T> T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }
template<typename T> T lcm(T a, T b) { return (a / gcd(a, b) * b); }
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

int cnt[100005] = {};
int pc[100005] = {}; //jouyo
int cc[100005] = {};    //jouyo
int X[100005];
int main() {
        int N, M;

        cin >> N >> M;
        for (int i = 0; i < N; i++) {
                cin >> X[i];
                cnt[X[i]]++;
                if (cnt[X[i]] % 2 == 0) pc[X[i] % M]++;
                cc[X[i] % M]++;
        }

        int ans = 0;
        for (int i = 1; i < (M + 1) / 2; i++) {
                int num = min(cc[i], cc[M - i]);
                ans += num;
                ans += min((cc[i] - num) / 2, pc[i]);
                ans += min((cc[M - i] - num) / 2, pc[M - i]);
        }
        if (M % 2 == 0) ans += cc[M / 2] / 2;
        ans += cc[0] / 2;

        cout << ans << endl;
        return (0);
}

Measured memory_bytes: 1792
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 200005
#define ll long long
#define ld double
#define mod 998244353
using namespace std;
int n, d;
int a[maxn];
struct eg
{
	int u, v;
	ll c;
	bool operator < (const eg &t)const
	{
		return c < t.c;
	}
}as[maxn * 20];
int ncnt = 0;
int fa[maxn];
int gfa(int a)
{
	if(fa[a] == a) return a;
	return fa[a] = gfa(fa[a]);
}
ll b[maxn];
void work(int l, int r)
{
	if(l == r) return;
	int mid = (l + r) >> 1;	
	int lmin = l, rmin = mid + 1;
	for(int i = l; i <= mid; i++)
	{
		b[i] = a[i] - 1ll * i * d;
		if(b[i] < b[lmin]) lmin = i;
	}
	for(int i = mid + 1; i <= r; i++)
	{
		b[i] = a[i] + 1ll * i * d;
		if(b[i] < b[rmin]) rmin = i;
	}
	for(int i = l; i <= mid; i++)
		as[ncnt].u = i, as[ncnt].v = rmin, 
		as[ncnt++].c = b[rmin] + b[i];
	for(int i = mid + 1; i <= r; i++)
		as[ncnt].u = i, as[ncnt].v = lmin, 
		as[ncnt++].c = b[lmin] + b[i];
	work(l, mid), 
	work(mid + 1, r);
}
int main()
{
	scanf("%d%d", &n, &d);
	for(int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	work(1, n);
	sort(as, as + ncnt);
	for(int i = 1; i <= n; i++)
		fa[i] = i;
	ll ans = 0;
	for(int i = 0; i < ncnt; i++)
	{
		int ufa = gfa(as[i].u), vfa = gfa(as[i].v);
		if(ufa != vfa)
			ans += as[i].c, fa[ufa] = vfa;
	}
	printf("%lld\n", ans);
	return 0;
} 

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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define lcm( a, b ) (a)/__gcd((a),(b))*(b)
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair< int, int > P;
typedef pair< LL, LL > LP;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;
static const int SIZE = 200005;

const int dx[] = {0, -1, 1, 0};
const int dy[] = {-1, 0, 0, 1};

LL fac[SIZE], finv[SIZE], inv[SIZE];
void combInit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for( int i = 2; i < SIZE; ++i ) {
        fac[i] = (fac[i - 1] * i) % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = (finv[i - 1] * inv[i]) % MOD;

    }
}

LL comb(int n, int k) {
    if( n < k ) return 0;
    if( n < 0 || k < 0 ) return 0;
    return (fac[n] * (finv[k] * finv[n - k] % MOD)) % MOD;

}

vector< int > Div( int n ) {
    vector< int > ret;
    for( int i = 1; i * i <= n; ++i ) {
        if( n % i == 0 ) {
            ret.pb( i );

            if( i * i != n ) ret.pb( n / i );
        }
    }
    sort( all( ret ) );
    return ret;
}

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

    LL n;
    cin >> n;
    if( n == 0 ) {
        cout << n << endl;
        return 0;

    }

    LL bi = 1;
    string s = "";
    while( n != 0 ) {
        if( n % (bi * (-2)) != 0 ) {
            n -= bi;
            s += '1';

        } else {
            s += '0';

        }
        bi *= (-2);

    }
    reverse(all(s));
    cout << s << endl;
    return 0;
}



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

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;

#define X first
#define Y second


const int N=1e2+5;

string s;
int n,pos[N][26];

int main(){
    cin>>s;
    int n=s.length();
    fill(pos[0],pos[0]+26,-1000);
    for(int i=1;i<=n;i++){
        for(int j=0;j<26;j++) pos[i][j]=pos[i-1][j];
        pos[i][s[i-1]-'a']=i;
    }
    int ans=n+1;
    for(int j=0;j<26;j++){
        int cans=0;
        while (1){
            bool okay=1;
            for(int i=cans;i<n;i++) if (i+1-pos[i+1][j]>cans) okay=0;
            if (okay) break;
            else cans++;
        }
//        cout<<char(j+'a')<<" "<<cans<<'\n';
        ans=min(ans,cans);
    }
    cout<<ans;
}


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

#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) for (int i=0;i<(n);++i)

using namespace std;

vector<pair<double, double>> circle_intersections(double cx1, double cy1, double r1, double cx2, double cy2, double r2) {
    double dx = cx2 - cx1;
    double dy = cy2 - cy1;
    double dx_2 = dx * dx;
    double dy_2 = dy * dy;
    double d_2 = dx_2 + dy_2;
    double d = sqrt(d_2);
    if (d > r1 + r2 || d < abs(r1 - r2)) {
        return { };
    }
    double r1_2 = r1 * r1;
    double r2_2 = r2 * r2;
    double D = r1_2 * r2_2 - pow(r1_2 + r2_2 - d_2, 2) / 4;
    if (D < 0) {
        return { };
    }
    double C = (r1_2 - r2_2) / d_2;
    double Ax = ((cx1 + cx2) + dx * C) / 2;
    double Ay = ((cy1 + cy2) + dy * C) / 2;
    double E = sqrt(D) / d_2;
    double Bx = dy * E;
    double By = dx * E;
    double x1 = Ax + Bx;
    double x2 = Ax - Bx;
    double y1 = Ay - By;
    double y2 = Ay + By;
    return { make_pair(x1, y1), make_pair(x2, y2) };
}

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

    constexpr int C_MAX = 100;
    constexpr int ABS_X_MAX = 1000;

    int N, K;
    cin >> N >> K;
    vector<int> x(N), y(N), c(N);
    REP(i, N) {
        cin >> x[i] >> y[i] >> c[i];
    }

    double low = 0;
    double high = C_MAX * (ABS_X_MAX * 2);
    while (high - low > 1e-10) {
        double t = (low + high) / 2;
        vector<pair<double, double>> points;
        REP(i, N) {
            points.emplace_back(x[i], y[i]);
        }
        REP(i, N) FOR(j, i + 1, N) {
            double ri = t / c[i];
            double rj = t / c[j];
            auto intersections = circle_intersections(x[i], y[i], ri, x[j], y[j], rj);
            for (auto &[a, b] : intersections) {
                points.emplace_back(a, b);
            }
        }
        bool is_enough_time = false;
        for (auto &[a, b] : points) {
            int n_in = 0;
            REP(i, N) {
                double r = t / c[i];
                if (pow(x[i] - a, 2) + pow(y[i] - b, 2) <= r * r + 1e-9) {
                    ++n_in;
                }
            }
            if (n_in >= K) {
                is_enough_time = true;
                break;
            }
        }
        if (is_enough_time) {
            high = t;
        } else {
            low = t;
        }
    }
    double t = (low + high) / 2;

    cout << setprecision(20) << fixed << t << endl;

    return 0;
}


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

int main() {
    int n; cin >> n;
    int p; cin >> p;
    vector<int> a(n);
    for (int &ai: a) cin >> ai;
    // dp[i][j] := i 個選んで j (j = 0 なら偶数, 1 なら奇数) となる選び方
    vector<vector<long long>> dp(n + 1, vector<long long>(2, 0));
    dp[0][0] = 1;   // 何も選ばない
    for (int i = 0; i < n; i++) {
        if (a[i] % 2 == 0) {
            dp[i + 1][0] = dp[i][0] + dp[i][0];     // 選ぶ・選ばない
            dp[i + 1][1] = dp[i][1] + dp[i][1];
        } else {
            dp[i + 1][0] = dp[i][1] + dp[i][0];
            dp[i + 1][1] = dp[i][0] + dp[i][1];
        }
    }
    cout << dp[n][p] << endl;   // n 個選んで p となる選び方
    return 0;
}

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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repr(i, n) for(int i = (n-1); i >= 0; --i)

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

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

const int MAX = 200005;
const int INF = 1001001001;
const int MOD = 1000000007;

pair<int, int> input() {
    int l, r;
    cin >> l >> r;
    l--;
    return P(l, r);
}

void print(const int i, const multiset<int> &st) {
    if (st.size() == 0) puts("-1");
    else cout << *st.begin() + i + 1 << endl;
}

int main(){
    int H, W;
    cin >> H >> W;

    map<int, int> mp;
    multiset<int> st;
    rep(i, W) {
        mp[i] = 0;
        st.insert(0);
    }

    auto calc = [&](int l, int r, map<int, int> &mp, multiset<int> &st) {
        if (r == W) {
            auto itr = mp.lower_bound(l);
            while (itr != mp.end()) {
                int c = itr->second;
                itr = mp.erase(itr);
                st.erase(st.find(c));
            }
            return;
        }

        auto itr = mp.lower_bound(l);
        int res = INF;
        while (itr != mp.end() && itr->first <= r) {
            int x = itr->first, c = itr->second;
            itr = mp.erase(itr);
            st.erase(st.find(c));
            chmin(res, c + r - x);
        }
        if (res != INF) {
            mp[r] = res;
            st.insert(res);
        }
    };

    rep(i, H) {
        auto [l, r] = input();

        calc(l, r, mp, st);

        print(i, st);
    }
}

Measured memory_bytes: 22364
(n, x) = list(map(int, input().split()))
x_list = list(map(int, input().split()))

if x in x_list:
    pass
else:
    x_list.append(x)
    x_list.sort()

min_diff = 99999999999
for i in range(len(x_list) - 1):
    diff = x_list[i + 1] - x_list[i]
    if min_diff > diff:
        min_diff = diff

# 差分の最小を約分していく
x_diff = [xx - x_list[0] for xx in x_list]

for i in range(1, min_diff):
    if min_diff % i != 0:  # 約分できない場合は次の数に進む
        continue
    xx = min_diff // i
    is_divided = [j for j in x_diff if j % xx != 0]
    if len(is_divided) == 0:
        print(xx)
        exit()
print(1)


Measured memory_bytes: 14252
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <array>
#include <tuple>
#include <string>
#include <algorithm>
#include <functional> // greater など
#include <cmath>      // abs など
#include <numeric>    // accumulate, gcd など
#include <cassert>    // assert
#include <stdexcept>
#include <bitset>
using namespace std;

// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
// typedef int128_t ll;
// typedef cpp_int ll;

// GCC, 配列のアクセスなど
#define _GLIBCXX_DEBUG
// Clang, 配列のアクセスなど
#define _LIBCPP_DEBUG 0

// #define NDEBUG 1
// debug用出力 https://trap.jp/post/998/
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
    cerr << H << " ";
    debug_out(T...);
}
#ifdef NDEBUG
#define debug(...)
#else
#define debug(...) debug_out(__VA_ARGS__)
#endif

//////////////// //////////////// //////////////// //////////////// ////////////////
//////////////// //////////////// //////////////// //////////////// ////////////////

constexpr int max_n = 100'000 + 5;
ll n,m;
vector<pair<int,int>> edges;
vector<ll> ress;

vector<int> uf_par(max_n);
vector<int> uf_rk(max_n);
vector<int> uf_size(max_n); // 部分木のサイズ
void uf_init(int n)
{
    rep(i, n)
    {
        uf_par[i] = i;
        uf_rk[i] = 1;
        uf_size[i] = 1;
    }
}
int uf_find(int x)
{
    if (x == uf_par[x])
    {
        return x;
    }
    return uf_par[x] = uf_find(uf_par[x]);
}
void uf_unite(int x, int y)
{
    x = uf_find(x);
    y = uf_find(y);
    if (x == y)
    {
        return;
    }
    if (uf_rk[x] < uf_rk[y])
    {
        uf_par[x] = y;
        uf_size[y] += uf_size[x];
    }
    else
    {
        uf_par[y] = x;
        uf_size[x] += uf_size[y];
        if (uf_rk[x] == uf_rk[y])
        {
            uf_rk[x]++;
        }
    }
}
bool uf_same(int x, int y)
{
    return uf_find(x) == uf_find(y);
}

int main()
{
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(15); // 浮動小数の表示の精度

    cin>>n>>m;
    rep(i,m) {
        int a,b; cin>>a>>b;
        edges.push_back({a,b});
    }
    reverse(edges.begin(), edges.end());

    uf_init(n);
    ress.push_back(n*(n-1)/2);
    rep(i,m-1) {
        int a,b; tie(a,b) = edges[i];
        ll prevres = ress[i];
        if (uf_same(a, b)) { ress.push_back(prevres); continue; }
        int ap = uf_find(a), bp = uf_find(b);
        ress.push_back(prevres - uf_size[ap] * uf_size[bp]);
        uf_unite(ap, bp);
    }
    reverse(ress.begin(), ress.end());
    rep(i,m) {
        cout<<ress[i]<<'\n';
    }

    return 0;
}


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

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

  vector<int> a(N, 0);
  for (int i; i < N; i++) {
    cin >> a[i];
  }

  int ans = -1, tmp = 0;

  for (int i = 0; i < N; i++) {
    tmp = a[tmp] - 1;
    if (tmp == 1) {
      ans = i + 1;
      break;
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 640
import sys

input = sys.stdin.readline

N = int(input())
xyh = []
for _ in range(N):
    xyh.append(list(map(int, input().split())))


xyh.sort(key=lambda x: x[2], reverse=True)
for cx in range(101):
    for cy in range(101):
        H = xyh[0][2] + abs(xyh[0][0] - cx) + abs(xyh[0][1] - cy)
        flag = True
        for i in range(1, N):
            x, y, h = xyh[i]
            if h > 0:
                if H != h + abs(x - cx) + abs(y - cy):
                    flag = False
                    break
            else:
                if H > abs(x - cx) + abs(y - cy):
                    flag = False
                    break
        if flag:
            ans = [cx, cy, H]
            print(*ans)
            exit()
        

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

void countingSort(vector<int> &A, vector<int> &B, int k)
{
    vector<int> C(k + 1, 0);
    for (int i = 0; i < A.size(); i++)
    {
        C[A[i]]++;
    }

    for (int i = 1; i < C.size(); i++)
    {
        C[i] += C[i - 1];
    }

    // 安定性のためにカウントダウンしていく
    for (int i = A.size() - 1; i >= 0; i--)
    {
        B[C[A[i]] - 1] = A[i];
        C[A[i]]--;
    }

    // for (int i = 0; i < A.size(); i++)
    // {
    //     B[C[A[i]] - 1] = A[i];
    //     C[A[i]]--;
    // }

    return;
}

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

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

    vector<int> B(n);
    countingSort(A, B, *max_element(A.begin(), A.end()));

    // for (int i = 0; i < n; i++)
    // {
    //     cout << B[i];
    //     if (i < n - 1)
    //     {
    //         cout << " ";
    //     }
    // }
    // cout << endl;

    for (int i = 0; i < n; i++)
    {
        printf("%d", B[i]);
        if (i < n - 1)
        {
            printf(" ");
        }
    }
    printf("\n");

    return 0;
}


Measured memory_bytes: 18380
using System;
class ProgramC
    {
        static void Main(string[] args)
        {
            
            string[] input = Console.ReadLine().Split(' ');
            int L = int.Parse(input[0]);
            int R = int.Parse(input[1]);

            int Lr = L % 2019;
            int Rr = R % 2019;
            
            if(R - L >= 2018)
                Console.WriteLine("0");
            else if(Lr < Rr)
                if(Lr <= 3 && Rr >= 673)
                    Console.WriteLine("0");
                else 
                {
                    int result = 2018;
                    for(int i = Lr;i < Rr;i++)
                        for(int j = Lr + 1;j <= Rr;j++)
                        {
                            int test = (i * j) % 2019;
                            if(test <= result)
                                result = test;
                        }
                    Console.WriteLine(result);
                }
            else if(Lr > Rr)
                Console.WriteLine("0");

        }
    }

Measured memory_bytes: 11092
#include <stdio.h>

int main(void){
	int side1 , side2 , line , rectangle = 0 , diamond = 0;
	while(scanf("%d,%d,%d" , &side1 , &side2 , &line)!=EOF){
		if(side1 == side2) diamond++;
		else if(side1 * side1 + side2 * side2 == line * line) rectangle++;
	}
	printf("%d\n%d\n" , rectangle , diamond);
	return 0;
}

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

int main() {
	int A, B, C;
	
	cin >> A >> B;
	
	int AB = A*B;
	
	if(AB%2==0) cout << "No";
	else if(AB%2==1) cout << "Yes";
	
	cout << endl;
	
	return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
lang={i:[] for i in range(1,m+1)}
for _ in range(n):
    x=list(map(int,input().split()))
    K=x[0]
    for i in range(1,K+1):
        lan=x[i]
        lang[lan].append(_+1)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())



uni=UnionFind(n)
for i in range(1,m+1):
    lis=lang[i]
    if lis:
        x=lis[0]
        for i in range(1,len(lis)):
            uni.union(x,lis[i])
if uni.group_count()==2:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 25428
n = int(input())
A = list(map(int,input().split()))
mul = 1
c = 0
A.sort()
limit = int(10**18)
for i in range(n):
	mul *= A[i]
	if mul>limit:
		c = 1
		break
if c:
	print(-1)
else:
	print(mul)

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

typedef long long int ll;
typedef long int li;

const ll mod = 1000000007;
const ll inf = 1000000000000000000;

typedef vector<int> vi;
typedef vector<li> vli;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef vector<vli> vvli;
typedef vector<vll> vvll;
typedef vector<vs> vvs;
typedef map<ll, ll> mll;
typedef map<ll, string> mls;
typedef map<string, ll> msl;

#pragma GCC optimize ("-O3")
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define PI 3.14159265358979323846
#define pb push_back
#define mp make_pair
#define fs first
#define sec second
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define tol(s) transform(s.begin(), s.end(), s.begin(), ::tolower);
#define tou(s) transform(s.begin(), s.end(), s.begin(), ::toupper);
#define all(v) v.begin(), v.end()
#define FOR(i, j, k, in) for(li i=j; i<k; i+=in)
#define RFOR(i, j, k, de) for(li i=j; i>=k; i-=de)
#define rep(i,j,k) FOR(i, j, k, 1)
#define rrep(i,j,k) RFOR(i, j, k, 1)
#define repc(v) for(auto it=v.begin(); it!=v.end(); it++)
#define T ll t; cin>>t; while(t--)

int main(){
  FAST

  int n,m;
  cin>>n>>m;
  int ar[n];
  rep(i,0,n)
    cin>>ar[i];
  
  li sum=0;
  rep(i,0,n)
    sum+=ar[i];
  
  float s=(sum/4.0)/m;
  int c=0;
  rep(i,0,n)
    if(ar[i]>=s)
      c++;
  
  if(c>=m)
    cout<<"Yes";
  
  else cout<<"No";
  
  return 0;
}








Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
char a[10005];
int n;
int main(){
    scanf("%s%d",a,&n);
    for(int i=0;i<strlen(a);i+=n)cout<<a[i];
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>

int n, k, r, s, p;
char T[100002];

int score(char c){
  switch(c){
    case 'r': return p;
    case 's': return r;
    case 'p': return s;
  }
  return -1;
}

int main(){
  scanf("%d%d%d%d%d", &n, &k, &r, &s, &p);
  scanf("%s", T);

  long long int ans = 0;

  for(int i = 0; i < k; i++){
    char prev = 0;
    for(int j = i; j < n; j += k){
      if(T[j] != prev){
        prev = T[j];
        ans += score(T[j]);
      }
      else {
        prev = 0;
      }
    }
  }

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

  
  return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))

s = sum(A)
c = 0
for i in range(2, N, 2):
    c += A[i]

a = [s - 2 * c]

for i in range(1, N):
    a.append((A[i] - a[-1] // 2) * 2)

ans = [a[-1]]
ans.extend(a[:-1])

print(*ans)


Measured memory_bytes: 15128
local function lltonumber(str)
  local ret = 0LL
  local sign = str:sub(1, 1) ~= "-"
  local begin = sign and 1 or 2
  for i = begin, #str do
    ret = ret * 10LL
    ret = ret + tonumber(str:sub(i, i))
  end
  if not sign then ret = ret * -1LL end
  return ret
end

local function llprint(llnumber)
  local str = tostring(llnumber):gsub("LL", "")
  print(str)
end

local str = io.read()
local n, kstr = str:match("(%d+) (%d+)")
n = tonumber(n)
local k = lltonumber(kstr)
local a, f = {}, {}
local asum = 0LL
for i = 1, n do
  a[i] = io.read("*n")
  asum = asum + a[i]
end
for i = 1, n do
  f[i] = io.read("*n")
end
table.sort(a)
table.sort(f, function(x, y) return x > y end)
if asum <= k then
  print(0)
else
  local mfl, mma = math.floor, math.max
  local function solve(x)
    local cnt = 0LL
    for i = 1, n do
      local c = mfl(x / f[i])
      if c < a[i] then
        cnt = cnt + a[i] - c
      end
    end
    return cnt <= k
  end
  local min = 0
  local max = a[1] * f[1]
  for i = 2, n do
    max = mma(max, a[i] * f[i])
  end
  while 1 < max - min do
    local mid = mfl((min + max) / 2)
    if solve(mid) then
      max = mid
    else
      min = mid
    end
  end
  print(max)
end


Measured memory_bytes: 12800
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T> using vec = std::vector<T>;

int main() {
    int W, a, b;
    cin >> W >> a >> b;
    if(abs(a-b)<=W) {
        cout << 0 << '\n';
        return 0;
    }
    vec<int> r(4);
    r[0] = a;
    r[1] = b;
    r[2] = a+W;
    r[3] = b+W;
    sort(all(r));
    cout << r[2]-r[1] << '\n';
}


Measured memory_bytes: 3540
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int t[2];
int ire(int a,int b){
	t[0]=b;t[1]=a;
}
main(){
	int n1,n2,a1,a2;
	while(cin>>n1>>n2){
		t[0]=max(n1,n2);
		t[1]=min(n1,n2);
		for(int i=0;;++i){
			t[0]=t[0]-t[1];
			if(t[0]==0){
				a1=t[1];
				break;
			}
			if(t[0]<t[1])ire(t[0],t[1]);
		}
		a2=(n1/a1)*n2;
		cout<<a1<<" "<<a2<<endl;
	}
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i = (a);i <= (b);i++)
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5 + 5;
const int maxm = 1e6 + 5;
const double eps = 1e-8;
const double pi = acos(-1.0);
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a * b / gcd(a,b);}
ll poww(ll x,ll y,ll p){ll ans = 1;while(y){if(y & 1) ans = ans * x % p;x = x * x % p;y >>= 1;}return ans % p;}
bool isp(ll x){if(x <= 1) return 0; for(ll i = 2;i * i <= x;i++){if(x % i == 0) return 0;}return 1;}
int h,a;
int main(){
 	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> h >> a;
	cout << (h + a - 1) / a << endl;
 	return 0;
}
//do smt instead of nothing! never give up!
//take care of long long!
//take care of upper or lower case e.g "yes" or "YES"?
//boundary condition! e.g. n = 0?
//brute force is always the first choice!
// print the ans to look for patterns in the data!

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin>>N;
  vector<long long>vec(10000);
  for(int X=1;X<=100;X++){
    for(int Y=1;Y<=100;Y++){
      for(int Z=1;Z<=100;Z++){
        if(X*X+Y*Y+Z*Z+X*Y+X*Z+Y*Z<10001){
          vec[X*X+Y*Y+Z*Z+X*Y+X*Z+Y*Z-1]++;
        }
      }
    }
  }
  for(int X=0;X<N;X++){
    cout<<vec.at(X)<<endl;
  }
}


Measured memory_bytes: 3568
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using Graph = vector<vector<pii>>;
const int INF = 1e9 + 1;
const ll LLINF = 1e18;
const int MOD = 1e9 + 7;

int main() {
    int N;
    cin >> N;
    vector<int> cnt(60);
    for(int i = 0; i < N; ++i) {
        ll A;
        cin >> A;
        for(int j = 0; ((ll)1 << j) <= A; ++j)
            if(A & ((ll)1 << j))
                cnt[j]++;
    }

    ll ans = 0, n = 1;
    for(int i = 0; i < 60; ++i) {
        ans += ((ll)cnt[i] * (N - cnt[i]) % MOD) * n % MOD;
        ans %= MOD;
        n <<= 1;
        n %= MOD;
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
s = input()
q =int(input())
ten = 0
r = []
l = []
for _ in range(q):
    ls = tuple(map(str, input().split()))
    if len(ls)==1:
       ten +=1
    else:
        if ls[1] =='1':
            if ten%2 ==0:
                l.append(ls[2])
            else:
                r.append(ls[2])
        else:
            if ten%2 ==1:
                l.append(ls[2])
            else:
                r.append(ls[2])
s = ''.join(reversed(l))+s+''.join(r)
if ten%2 ==1:
    s = s[::-1]
print(s)

Measured memory_bytes: 12252
n=n1=int(input())
k=int(n**0.5)
a=[]

while n%2==0:
    a.append(2)
    n=n/2

for i in range(3, k, 2):
    while n%i==0:
        a.append(i)
        n=int(n/i)

    if n==1:
        break
    if i*i>n:
        break

if n!=1:
    a.append(n)

print(n1,":",sep="", end="")

for i in range(len(a)):
    print(" ", end="")
    print(a[i], end="")

print("") 


Measured memory_bytes: 5640
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define lli long long int   //used int to avoid mle
#define ulli unsigned long long int 
#define ld long double
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define loop(i,a,b) for(lli i=a;i<b;i++)
#define initialize(array,size,value) for(lli i=0;i<size;i++) array[i]=value
#define couta(array,size) for(lli i=0;i<size;i++) cout<<array[i]<<" "
#define vl vector<lli>
#define vp vector< pair <lli,lli> >
#define sl set<lli>
#define spl set<pll>
#define msl multiset <lli>
#define msp multiset <pll>
#define pll pair<lli, lli>
#define mll map<lli, lli>              //for( map<lli, lli>::iterator i=temp.begin();i!=temp.end();i++)cout<<i->fi<<" "<<i->se<<endl;
#define mvl map<lli, vl>
#define umll unordered_map<lli, lli>
#define vt vector<pair<lli, pll >  >
#define vf vector<pair<pll,pll > >
#define qu queue<lli>
#define pq priority_queue<lli>
#define dq deque <lli>
#define ptr vector<lli>::iterator
#define bs(array,x) binary_search(array.begin(),array.end(),x)
#define lb(array,x) lower_bound(array.begin(),array.end(),x)
#define ub(array,x) upper_bound(array.begin(),array.end(),x)
#define nobw(array,i,j) upper_bound(array.begin(), array.end(), j)-lower_bound(array.begin(), array.end(), i) //number of numbers between i & j
#define vc clear()
#define endl '\n'
#define sp system("pause");
#define INF 9223372036854775807
#define MINF -9223372036854775808
#define start_routine() int begtime = clock();
#define end_routine() int endtime = clock(); cerr << endl << "Time elapsed: " << (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms"; return 0
lli mod=1000000007;

int main()
{
 	ios::sync_with_stdio(0);
    cin.tie(0);
   
    lli n,m;
    cin>>n>>m;
    if(n>m)swap(n,m);
    for(lli i=0;i<m;i++)cout<<n;
    
}

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

ll x = 1e9 + 7; 

int main() {
  ll x;
  cin >> x;
  ll ans = 0;
  ans += 1000 * (x/500);
  x %= 500;
  ans += 5 * (x/5);
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3588
import java.util.Scanner;

public class Main
{
    public static void main(String [] args)
    {
        Scanner key = new Scanner(System.in);
        String s = key.nextLine();
        boolean flag = false;
        for(int i = 0; i<s.length(); i++)
        {
            
            if(s.charAt(i)== '7')
                flag = true;
        }
        if(flag == true)
        {
            System.out.println("Yes");
        }
        else
            System.out.println("No");
    }
}

Measured memory_bytes: 35600
#include <cstdio>
#include <climits>
#include <cassert>
#include <cmath>
#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
#include <tuple>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <vector>
#include <iterator>
#include <regex>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define FOR(x,xs) for(auto &x: xs)

using namespace std;
typedef long long ll;
typedef pair<int,int> PI;
typedef pair<ll,ll> PL;
typedef vector<int> VI;
typedef vector<ll> VL;

template <class T, template <class, class> class C, class charT = char>
void vdump(const C<T, allocator<T>> &v, const charT* delimiter = ", ",
           ostream &stream = cout) {
  copy(v.begin(), v.end(), ostream_iterator<T>(stream, delimiter));
  stream << endl;
}
struct UnionFind {
  vector<int> par;
  vector<int> rank;
  UnionFind(int n): par(n), rank(n) {
    for(int i=0; i<n; i++) {
      par[i] = i;
      rank[i] = 0;
    }
  }
  int find(int x) {
    if(par[x] == x) {
      return x;
    }
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(rank[x] < rank[y]) {
      par[x] = y;
    } else {
      par[y] = x;
      if(rank[x] == rank[y]) {
        rank[x]++;
      }
    }
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
};

int main() {
  ios::sync_with_stdio(false);
  int h, w;
  cin >> h >> w;
  vector<string> ss(h);
  FOR(s,ss) {
    cin >> s;
  }
  UnionFind uf(h * w);
  REP(i,0,h-1) {
    REP(j,0,w) {
      if (ss[i][j] != ss[i+1][j]) {
        uf.unite(i * w + j, (i + 1) * w + j);
      }
    }
  }
  REP(i,0,h) {
    REP(j,0,w-1) {
      if (ss[i][j] != ss[i][j+1]) {
        uf.unite(i * w + j, i * w + j + 1);
      }
    }
  }
  VL black(h * w, 0);
  VL white(h * w, 0);
  REP(i,0,h) {
    REP(j,0,w) {
      if (ss[i][j] == '#') {
        black[uf.find(i * w + j)]++;
      } else {
        white[uf.find(i * w + j)]++;
      }
    }
  }
  ll ans = 0;
  REP(i,0,h) {
    REP(j,0,w) {
      int id = i * w + j;
      if (id == uf.find(id)) {
        ans += black[id] * white[id];
      }
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 4224
import java.util.*;

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

        int A = scanner.nextInt();
        int B = scanner.nextInt();

        char[] nums = {'1', '2', '3', '4', '5', '6', '7', '8', '9', '0'};
        HashSet<Character> hashSet = new HashSet<>();
        for(char c: nums){
            hashSet.add(c);
        }

        String str = scanner.next();

        for(int i=0; i<str.length(); i++){
            if(i != A){
                if(!hashSet.contains(str.charAt(i))){
                    System.out.println("No");
                    return;
                }
            }else{
                if(str.charAt(i) != '-'){
                    System.out.println("No");
                    return;
                }
            }
        }
        System.out.println("Yes");
    }
}


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

#include <algorithm>
#include <iomanip>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

int main() {

    long long int a, b, c, d;
    cin >> a >> b >> c >> d;

    while( true ) {

        c -= b;
        if ( c <= 0 ) {
            cout << "Yes" << endl;
            return 0;
        }

        a -= d;
        if ( a <= 0 ) {
            cout << "No" << endl;
            return 0;
        }

    }

    return 0;

}


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

int main() {
  vector<int> v(3), a = {5, 5, 7};
  cin >> v.at(0);
  cin >> v.at(1);
  cin >> v.at(2);
  sort(v.begin(), v.end());
  if(v == a)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}

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

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

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

int getRand(int l, int r)
{
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}
  
#define int long long 
#define pb push_back
#define S second
#define F first
#define f(i,n) for(int i=0;i<n;i++)
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define vi vector<int>
#define pii pair<int,int>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define precise(x) fixed << setprecision(x) 

const int MOD = 1e9+7;

int mod_pow(int a,int b,int M = MOD)
{
    int res = 1;
    
    while(b)
    {
        if(b&1) res=(res*a)%M;
        a=(a*a)%M;
        b>>=1;
    }
    
    return res;
}


void solve()
{
   
    int a,b,c,k;
    cin >> a >> b >> c >> k;
    
    int res = 0;
    
    swap(a,c);
    
    int t = min(k,c);
    res+=t;
    k-=t;
    
    t = min(k,b);
    k-=t;
    
    t = min(k,a);
    res-=t;
    k-=t;
    
    cout << res;
}

signed main()
{
    fast;
    
    int t = 1;
    
//    cin >> t;
    
    while(t--)
        
    solve();
}

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

int main() {
  string s;
  bool state = 0;
  cin >> s;
  for(int i = 0; i < s.size(); i++) {
      if(s[i] == 'C' && state == 0) {
          state = 1;
      }else if(s[i] == 'F' && state == 1) {
          cout << "Yes" << endl;
          return 0;
      }
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
int main() {
    int ans=0,n,k;
    cin >> n >> k;
    vector<int> l(n);
    rep(i,n) cin >> l[i];
    sort(l.begin(),l.end());
    reverse(l.begin(),l.end());
    rep(i,k) ans += l[i];
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
def gcd(a, b):
    if a%b ==0:
        return b
    else:
        return gcd(b, a%b)

n = int(input())
a = list(map(int, input().split()))
a.sort()
for i in range(n-1):
    a[i+1]  = gcd(a[i], a[i+1])
print(a[n-1])

Measured memory_bytes: 14252
N,K=map(int,raw_input().split())
K-=1
s={}
for i in range(N):
    a,b=map(int,raw_input().split())
    if a in s:
        s[a] += b
    else:
        s[a] = b

c=sorted(s.items())

index = 0
for i in c:
    index += i[1]
    if K<index:
        print i[0]
        break

Measured memory_bytes: 16556
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define ALL(a) a.begin(),a.end()
typedef long long ll;
#define INF 1<<30

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

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


int main()
{
    ll A,B;
    cin >> A >> B;
    cout << lcm(A,B) << endl;
    return 0;
}

Measured memory_bytes: 256