akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    int n, a, b, c;
    cin >> n >> a >> b >> c;

    int topping[n];
    for(int i = 0; i < n; i++)  cin >> topping[i];

    sort(topping, topping+n);
    reverse(topping, topping+n);

    int cal = c, cost = a;
    for(int i = 0; i < n; i++){
        int ncal = cal + topping[i];
        int ncost = cost + b;
        if((double)ncal/ncost >= (double)cal/cost){
            cal = ncal, cost = ncost;
        }else{
            break;
        }
    }

    cout << cal/cost << endl;

    return 0;
}


Measured memory_bytes: 3140
N,C,K = map(int,input().split())
T = [int(input()) for i in range(N)]

T.sort()

ans = 1
bus = [T[0]]
for i in range(1,N):
    if T[i]-bus[0] <= K and len(bus) <= C-1:
        bus.append(T[i])
    else:
        bus = [T[i]]
        ans += 1
print(ans)


Measured memory_bytes: 7444
import java.io.*;

public class Main{
    public static void main(String[] args){
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        try{
        String in = reader.readLine();
        int x =Integer.parseInt(in);
        System.out.println(x*x*x);
        } catch (IOException e) {
            System.out.println(e);
        } catch (NumberFormatException e){
            System.out.println("No data");
        }
    }
}


Measured memory_bytes: 24164
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#include <string>

using namespace std;
typedef long long ll;

int main() {
    int n,k; cin >> n >> k;
    vector<ll> v(n);
    deque<ll> q;
    for(int i = 0; i < n; i++) {
        cin >> v[i];
        q.push_back(v[i]);
    }
    ll max = 0;
    // 何個取り出すか
    for(int out = 0; out <=n && out <=k; out++) {
        int in = min(out,k - out);
        // 何個左から出すか
        for(int left = 0; left <= out; left++) {
            deque<ll> qtmp = q;
            int right = out - left;
            priority_queue<ll, vector<ll>, greater<ll> > pq;
            for(int i = 0; i < left; i++) {
                pq.push(qtmp.front());
                qtmp.pop_front();
            }
            for(int i = 0; i < right; i++) {
                pq.push(qtmp.back());
                qtmp.pop_back();
            }
            for(int i = 0; i < in; i++) {
                if(pq.top() > 0)
                    break;
                pq.pop();
            }
            ll sum = 0;
            while(!pq.empty()) {
                sum += pq.top();
                pq.pop();
            }
            if(max < sum)
                max = sum;
        }
    }
    cout << max << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<int> a(3);
    rep(i,3) cin >> a[i];
    sort(a.begin(), a.end());
    cout << a[0] * a[1] / 2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main() {
  int A;
  int B;
  cin >>A>>B;
  int x=A+B;
  int y=B-A;
  if (B%A==0) {
cout << x << endl;
  }
else {
cout << y << endl;
}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define endl "\n"
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);

    int a;
    cin >> a;
    cout << a+(a*a)+(a*a*a) << endl;

    return 0;
}


Measured memory_bytes: 3644
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
 
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String num = br.readLine();
		String[] str = num.split(" ", 0);
		int n = Integer.parseInt(str[0]);
		int a = Integer.parseInt(str[1]);
		int b = Integer.parseInt(str[2]);
		int x = n - a;
		int y = n - b;
		x=Math.abs(x);
		y=Math.abs(y);
		if (x < y) {
			System.out.println("A");
		} else {
			System.out.println("B");
		}
	}
}

Measured memory_bytes: 25044
#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>

int main(){
    int a, b, angle;
    double s, l, h;

    scanf("%d %d %d", &a, &b, &angle);
    // sin(), cos(), tan()????§???????????????¢???
    // ?????°?????????????????¢??????????????????????§????(????????¢???)????§????(?????°)*??/180
    // ?????°??¨??????????????????????????math.h???define????????¨?????????
    // ?????????dandelion's log ?? VC++??§M_PI?????????????????£????????±?????? http://www.atinfinity.info/blog/archives/14
    h=b*sin(angle*M_PI/180.0);
    s=a*h/2;
    l=a+b+sqrt((a*a+b*b-2*a*b*cos(angle*M_PI/180.0)));
    printf("%f\n", s);
    printf("%f\n", l);
    printf("%f\n", h);

    return 0;
}

Measured memory_bytes: 636
#include<bits/stdc++.h>
using namespace std;
pair<int,int> pii;
vector<int> vec;
int main()
{
  int n,ans=0;
  int h[100005],q[100005]={};
  cin>>n;

  for(int i=0; i<n; i++){
    cin>>h[i];
  }

  for(int i=n-1; i>0; i--){
    if(h[i]>h[i-1])q[i-1]=0;
    else q[i-1]=q[i]+1;
  }

  for(int i=0; i<n; i++){
    ans=max(q[i],ans);
  }

  cout<<ans<<'\n';

  return 0;
}


Measured memory_bytes: 1024
#include "bits/stdc++.h"

using namespace std;

void Main() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N, 0);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    vector<int> B(N + 1, 0);
    for (int k = 0; k < K; ++k) {
        for (int i = 0; i < N; ++i) {
            B[max(0, i - A[i])] += 1;
            B[1 + min(N - 1, i + A[i])] -= 1;
        }
        for (int i = 1; i < N + 1; ++i) {
            B[i] += B[i - 1];
        }

        //for (int i = 0; i < N; ++i) {
        //    for (int j = max(0, i - A[i]); j <= min(N - 1, i + A[i]); ++j) {
        //        B[j] += 1;
        //    }
        //}

        bool horizon = true;
        for (int i = 0; i < N; ++i) {
            A[i] = B[i];
            B[i] = 0;
            if (A[i] != N) {
                horizon = false;
            }
        }
        if (horizon) {
            break;
        }
    }

    for (int i = 0; i < N; ++i) {
        if (i > 0) {
            cout << " ";
        }
        cout << A[i];
    }
    cout << endl;
}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 4756
inputa = input()

h,n = inputa.split()
H=int(h)
N=int(n)
inputb=input()
Attacks=inputb.split()
Attacks.sort(reverse=True)
# print(Attacks)
cnt=0
maxlen=len(Attacks)
for i in range(N):
  H=H-int(Attacks[maxlen-i-1])
  cnt=cnt+1

if(H >0):
  print("No")
else:
  print("Yes")


Measured memory_bytes: 10168
// in case of multiple test cases and N=1e5 don't intialize arrays as global except for graph vector-array
// always check whether or not you are doing mod of a negative number
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
 
using namespace __gnu_pbds;
using namespace std;

#define double      	long double
#define int         	long long
#define pb          	push_back
#define pii         	pair<int,int>
#define vi          	vector<int>
#define vii         	vector<pii>
#define mi          	map<int,int>
#define mii         	map<pii,int>
#define all(a)      	(a).begin(),(a).end()
#define sz(x)       	(int)x.size()
#define endl        	"\n"
#define repp(i,a,b) 	for(int i=a;i<b;i++)
#define rep(i,a,b) 		for(int i=a;i<=b;i++)
#define brep(i,a,b)     for(int i=a;i>=b;i--)
#define deb1(x)      	cout << #x << "=" << x << endl
#define deb2(x, y)  	cout << #x << "=" << x << "," << #y << "=" << y << endl
#define deb3(x, y, z)  	cout << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define trace(v) 		for(auto it=v.begin();it!=v.end();it++)cout<<*it<<" ";cout<<endl;
#define tracearr(a,l,r) for(int iii=l;iii<=r;iii++)cout << a[iii] << " ";cout << endl;
#define PI          	3.1415926535897932384626
#define F 				first
#define S 				second
#define clr(x,y) 		memset(x, y, sizeof(x))
#define IOS         	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);


typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
// *s.find_by_order(1) - gives the 2nd samllest element in set
// s.order_of_key(x)   - gives the number of elements in the set which are strictly smaller than x


const int N=1e5 + 5;
const int MOD=1e9 + 7;

int32_t main()
{
	IOS;
	int T=1;
	//cin >> T;
	// int numOfSetBits = __builtin_popcountll(n);
	std::cout << std::fixed << std::setprecision(12);
	while(T--)
	{
		int x,k,d;
		cin >> x >> k >> d;
		int f = abs(x);
		int cou = f/d;
		int xx = min(k,cou);
		int rem = k - xx;
		f -= xx*d;
		//deb2(cou,f);
		int even = f;
		int odd = f - d;
		if(rem%2==0)
			cout << abs(even);
		else
			cout << abs(odd);
	}
}

Measured memory_bytes: 3644
/*
author : seryu
title : ABC166C_"Peaks"
*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define reps(i,n) for(int i = 1; i <= n; i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ERASE(x,val) x.erase(remove(all(x), val), x.end())
typedef long long ll;
typedef pair<int, int> P;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
ll MOD = 1000000007;
int INF = 1001001001;

void solve()
{
	int n, m;
	cin >> n >> m;
	vector<ll> h(n);
	rep(i, n) cin >> h[i];
	vector<vector<int>> path(n);
	rep(i, m)
	{
		int a, b;
		cin >> a >> b;
		a--;b--;
		path[a].push_back(b);
		path[b].push_back(a);
	}
	int ans = 0;
	rep(i, n)
	{
		bool ok = true;
		for(auto e : path[i])
		{
			if(h[i] <= h[e])ok = false;
		}
		if(ok)ans++;
	}
	cout << ans << endl;

	return;
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}


Measured memory_bytes: 9196
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		
		if(A + B >= 10) {
			System.out.println("error");
		} else {
			System.out.println(A + B);
		}
		
	}
}


Measured memory_bytes: 22608
using System;
using System.Collections.Generic;
using System.Linq;
class Program{
  static void Main(){
    var n = int.Parse(Console.ReadLine());
    var dic = new Dictionary<string,int>(n);
    int max = 0, max2 = 0, diccnt=0;
    var maxword = "";
    for(int c=n; c>=max-max2 && c>0; c--){
      string input = Console.ReadLine();
      int count;
      if(dic.ContainsKey(input)){
        count = ++dic[input];
      }else{
        dic.Add(input, 1);
        count=1;
        diccnt++;
      }
      if(count>max){
        if(input!=maxword){
          max2 = max;
          maxword=input;
        }
        max = count;
      }else if (count>max2){
        max2 = count;
      }
    }
    var sss = dic.Where(a => a.Value == max).Select(a => a.Key).ToArray();
    Array.Sort(sss, StringComparer.Ordinal);
    foreach(var word in sss){
      Console.WriteLine(word);
    }
  }
}

Measured memory_bytes: 39732
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+34;
typedef pair<int,int> pi;
priority_queue <pi> q;
int a[maxn],b[maxn],n;
ll cnt;

int main(){
    cin >> n;
    for (int i=0;i<n;i++) cin >> a[i];
    for (int i=0;i<n;i++) cin >> b[i];
    for (int i=0;i<n;i++) if (a[i]>b[i]) {puts("-1");return 0;}
    for (int i=0;i<n;i++) if (a[i]!=b[i]) q.push((pi){b[i],i});
    while (!q.empty()){
        pi tmp=q.top(); q.pop();
        int x=tmp.second;
        int temp=(b[x]-a[x])/(b[(x+1)%n]+b[(x+n-1)%n]);
        if (temp==0){puts("-1");return 0;}
        cnt+=temp; b[x]-=temp*(b[(x+1)%n]+b[(x+n-1)%n]);
        if (b[x]>a[x]) q.push((pi){b[x],x});
    }
    cout << cnt << endl;
}


Measured memory_bytes: 7284
s = list(input())
s1 = [0]*len(s)
s0 = [1]*len(s)
for i in range(1,len(s), 2):
  s1[i] += 1
  s0[i] -= 1
n1 = 0
n0 = 0
for i in range(len(s)):
  if s1[i] != int(s[i]):
    n1 += 1
  elif s0[i] != int(s[i]):
    n0 += 1
print(min(n1, n0))

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

struct UnionFind {
  vector<int> par;
  UnionFind(int N) : par(N) {
    for(int i = 0; i < N; i++) par.at(i) = i;
  }
  
  int root(int x) {
    if(par[x] == x) return x;
    return par[x] = root(par[x]);
  }
  
  void unite(int x, int y) {
    int rx = root(x), ry = root(y);
    if(rx == ry) return;
    par[rx] = ry;
  }
  
  bool same(int x, int y) {
    int rx = root(x), ry = root(y);
    return (rx == ry);
  }
};

int main() {
  int N, M; cin >> N >> M;
  vector<int> p(N);
  for(int i = 0; i < N; i++) {
    cin >> p.at(i);
    p.at(i)--;
  }
  UnionFind tree(N);
  for(int i = 0; i < M; i++) {
    int x, y; cin >> x >> y; x--; y--;
    tree.unite(x, y);
  }
  int count = 0;
  for(int i = 0; i < N; i++) {
    if(tree.same(i, p.at(i))) count++;
  }
  cout << count << endl;
}

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

typedef long long ll;

ll C2(int x){
    return (ll)x * (x-1) / 2LL;
}

set<int> S;

int a[200005];
int pos[200005];
int n;

void input(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        pos[a[i]] = i;
    }
    S.insert(0);
    S.insert(n+1);
}

void pro(){
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        auto It = S.lower_bound(pos[i]);
        int r = *It, l = *(--It);
        //printf("i = %d, l = %d, r = %d\n",i,l,r);
        ans += (ll)(r-pos[i]) * (pos[i]-l) * i;
        S.insert(pos[i]);
    }
    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    input();
    pro();
}


Measured memory_bytes: 11264
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#define rad M_PI/3
#define N 2147483647
#define Max 500000
#define NTL -1
#define min(a,b) ((a>b)?b:a)
#define max(a,b) ((a<b)?b:a)

#include<stdio.h>
int main(){
  int i,n;
  long long int ans=1;
  scanf("%d",&n);
  for(i=n;i>=1;i--){
    ans*=i;
  }
  printf("%lld\n",ans);
  return 0;
}


Measured memory_bytes: 1912
from collections import defaultdict

N, M = map(int, input().split())
A = list(map(int, input().split()))
 
# 累積和
 
cumsum = [0]
for i in range(len(A)):
    cumsum.append(cumsum[i] + A[i])
 
mod_cumsum = []
for i in cumsum:
    mod_cumsum.append(i % M)

moddict = defaultdict(int)

ret = 0
for i in mod_cumsum:
    ret += moddict[i]
    moddict[i] += 1

    
print(ret)


Measured memory_bytes: 18856
#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;


int main(){
    string s;
    cin>>s;

    if(s=="Sunny")cout<<"Cloudy"<<endl;
    else if(s=="Cloudy")cout<<"Rainy"<<endl;
    else cout<<"Sunny"<<endl;



    return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	scanInit()

	n := nextStr()

	if len(n) == 1 {
		fmt.Println(n)
		return
	}

	// All 9
	all9 := 1
	base := 9*(len(n)-1) + (int(n[0]) - '0')
	for i := 1; i < len(n); i++ {
		if n[i] != '9' {
			all9 = 0
		}
	}
	if all9 == 1 {
		fmt.Println(base)
		return
	}

	fmt.Println(base - 1)

}

// ---- readfunc
func scanInit() {
	const cap = 200 * 1024 // Default=64
	var buf = make([]byte, cap)
	sc.Buffer(buf, cap)
	sc.Split(bufio.ScanWords)
	return
}
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 1780
"use strict";
var input = require("fs").readFileSync("/dev/stdin", "utf8");
var cin = input.trim().split(/ |\n/), cid = 0;

function main() {
    let a = +cin.shift();//jisin
    let b = +cin.shift();//hunsin
    let h = +cin.shift();
    let m = +cin.shift();
    let theta =  Math.PI * ((h / 6 +m/360) - m / 30);
    let xx = a * a + b * b - 2 * a * b * Math.cos(theta);
    let x = Math.sqrt(xx);
    console.log(x);
}
main();

Measured memory_bytes: 29748
n, k = gets.split.map(&:to_i)
mod = 10 ** 9 + 7

a = Array.new(k+1, 1)
b = [*0..k]

(k/2).downto(1) do |i| 
 cnt = (k/i).pow(n, mod)

 j = i*2
 while j <= k
  cnt = ( cnt - a[j] ) % mod
  j += i
 end

 a[i] = cnt
 b[i] = i * cnt % mod
end

puts b.inject(0, :+) % mod

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

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using P = pair<int, int>;

const int INF = 1e9;
const ll INFLL = 1e18;
const int MOD = 1e9 + 7;
const int NIL = -1;
const ld PI = acosl(-1);

#define rep(i,n) for(int i=0; i<(n); ++i)
#define all(n) n.begin(),n.end()

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	//cout << fixed << setprecision(6);
	ld a, b;
	cin >> a >> b;
	
	ll ans = a * b;

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

Measured memory_bytes: 3740
n,k = map(int,input().split())
if n == 1:
    print(k)
else:
    edges = {}
    for i in range(n-1):
        a,b = map(int,input().split())
        if a not in edges:
            edges[a] = [b]
        else:
            edges[a].append(b)

        if b not in edges:
            edges[b] = [a]
        else:
            edges[b].append(a)

    now = set([1])
    visited = set([1])
    goal = -1
    flag = False
    ans = k
    mod = 10**9+7
    while True:
        buf = set()
        if len(now) == 0:
            break
        for n in now:
            if n == 1:
                for i in range(len(edges[n])):
                    ans *= k-1-i
                    ans %= mod
                for nn in edges[n]:
                    if nn in visited:
                        continue
                    else:
                        buf.add(nn)
                        visited.add(nn)

            else:
                temp = 0
                for nn in edges[n]:
                    if nn in visited:
                        continue
                    else:
                        temp += 1
                        buf.add(nn)
                        visited.add(nn)
                for i in range(temp):
                    ans *= k - 2 - i
                    ans %= mod
        # print(buf)
        # print(ans)
        now = buf
    # print(visited)
    print(ans%mod)

    # def tree_bfs(start,goal,edges):
    #     now = set([start])
    #     visited = set([start])
    #     flag = False
    #     while True:
    #         buf = set()
    #         if len(now) == 0:
    #             break
    #         for n in now:
    #             for nn in edges[n]:
    #                 if nn in visited:
    #                     continue
    #                 else:
    #                     buf.add(nn)
    #                     visited.add(nn)
    #
    #                 if nn == goal:
    #                      flag =True
    #                      break
    #         if flag:
    #             break
    #         else:
    #             now = buf

Measured memory_bytes: 81880
N=int(input())
A=list(map(int,input().split()))
count=0
B=[A[0]]
for i in range(1,N) :
  if B[i-1]<A[i] :
    B.append(A[i])
  else :
    B.append(B[i-1])
ans=0
for i in range(N) :
  ans+=B[i]-A[i]
print(ans)

Measured memory_bytes: 32168
N,P = map(int,input().split())
A = list(map(int,input().split()))
A = [i%2 for i in A]
zero = A.count(0)
one = A.count(1)
ans = 0
def combinations(n, r):
    import math as ma
    return ma.factorial(n)//(ma.factorial(n-r)*ma.factorial(r))

if P == 0:
    ans += 2**zero
    a = 0
    for i in range(one//2):
        a += combinations(one, 2*(i+1))
    ans += a*(2**zero)
else:
    ans += 2**zero
    a = 0
    for i in range(one//2):
        a += combinations(one, 2*(i+1))
    ans += a*(2**zero)
    ans = 2**N - ans
print(ans)

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

int main(){
  int A, B;
  cin >> A >> B;
  
  if(A > 12){
    cout << B << endl;
  }
  else if(A > 5){
    cout << B /2 << endl;
  }
  else{
    cout << 0 << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using ll = long long;
using P = pair<int, int>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e18;
constexpr long long MOD = 1e9 + 7;

#define MAX 2500

signed main() {
    int n, m, s;
    cin >> n >> m >> s;
    using T = tuple<ll, ll, ll>;
    vector<T> G[n];
    int u, v, a, b;
    rep(i, m) {
        cin >> u >> v >> a >> b;
        u--;
        v--;
        G[u].emplace_back(v, a, b);
        G[v].emplace_back(u, a, b);
    }
    ll c[n], d[n];
    rep(i, n) {
        cin >> c[i] >> d[i];
    }
    ll dist[n][MAX + 1];
    fill(dist[0], dist[n], LINF);
    priority_queue<T, vector<T>, greater<T>> que;
    for (int j = 0;; j++) {
        int nxt = min(s + c[0] * j, (ll)MAX);
        dist[0][nxt] = d[0] * j;
        que.emplace(dist[0][nxt], nxt, 0);
        if (s + c[0] * j > MAX) break;
    }
    while (!que.empty()) {
        T t = que.top();
        que.pop();
        int cnt = get<1>(t), v = get<2>(t);
        if (dist[v][cnt] < get<0>(t)) continue;
        for (int i = 0; i < G[v].size(); i++) {
            int to = get<0>(G[v][i]), need = get<1>(G[v][i]);
            ll cost = get<2>(G[v][i]);
            if (cnt - need < 0) continue;
            for (int j = 0;; j++) {
                int nxt = min(cnt - need + c[to] * j, (ll)MAX);
                if (dist[to][nxt] > dist[v][cnt] + cost + d[to] * j) {
                    dist[to][nxt] = dist[v][cnt] + cost + d[to] * j;
                    que.emplace(dist[to][nxt], nxt, to);
                }
                if (cnt - need + c[to] * j > MAX) break;
            }
        }
    }
    for (int v = 1; v < n; v++) {
        ll ans = LINF;
        for (int j = 0; j <= MAX; j++) {
            ans = min(ans, dist[v][j]);
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 101724
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long ll;
const int N=100005;
int n;
ll a[N],s[N];
using namespace std;

int main()
{
	#ifdef Kay
		freopen ("code.in","r",stdin);
		freopen ("code.out","w",stdout);
	#endif
	scanf ("%d",&n);
	int i;
	for (i=1;i<=n;i++) scanf ("%lld",&a[i]);
	ll ans1=0,ans2=0;
	for (i=1;i<=n;i++)
	{
		s[i]=s[i-1]+a[i];
		if ((i&1))
		{
			if (s[i]<=0) ans1+=1ll-s[i],s[i]=1;
		}
		else
		{
			if (s[i]>=0) ans1+=s[i]+1ll,s[i]=-1;
		}
	}
	for (i=1;i<=n;i++)
	{
		s[i]=s[i-1]+a[i];
		if (!(i&1))
		{
			if (s[i]<=0) ans2+=1ll-s[i],s[i]=1;
		}
		else
		{
			if (s[i]>=0) ans2+=s[i]+1ll,s[i]=-1;
		}
	}
	cout<<min(ans1,ans2);
	return 0;
}


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

int main()
{
    //0 1 3 6 10 15
    int N;
    cin >> N;
    
    vector<int> data(N);
    vector<vector<int>> num(N + 1);
    for(int i = 0;i<N;i++)
    {
        cin >> data[i];
        num[data[i]].push_back(i);
    }
    long long ans = 0;
    for(int i = 1;i<=N;i++)
    {
        long long x = (long long)num[i].size();
        ans += x * (x - 1) / 2;
    }
    
    for(int i = 0;i<N;i++)
    {
        cout << ans +1 - num[data[i]].size() << endl;
    }
    
    
    return 0;
    
}

Measured memory_bytes: 12544
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC omodtimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<long long ,long long> ii; 	
typedef complex<long double> com;
 
const ll mod = 1e9+7;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ld a,b,c;
	cin >> a >> b >> c;
	if (c - a - b > 2  && 4*a*b < (c-a-b)*(c-a-b)){
		cout << "Yes" << endl;
	} else cout << "No" << endl;
}

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

const long Day_num = 365;
const long type_num = 26;

class Scoring {
public:
    Scoring(const long arg_days, const std::vector<long>& arg_costs, const std::vector<std::vector<long>>& arg_incentives);
    std::vector<long> score(const std::vector<long>& arg_types);
private:
    long days;
    std::vector<long> costs;
    std::vector<std::vector<long>> incentives;
};

std::vector<long> Scoring::score(const std::vector<long>& arg_types) {
    std::vector<long> result(days);
    long satisfy = 0;
    std::vector<long> last_days(type_num, 0);


    for (long day = 1; day <= days; ++day) {
        const auto exe_type = arg_types[day-1];
        satisfy += incentives[day-1][exe_type-1];
        last_days[exe_type-1] = day;
        for (long type = 1; type <= type_num; ++type) {
            satisfy -= costs[type-1] * (day - last_days[type-1]);
        }
        result[day-1] = satisfy;
    }
    return result;
}

Scoring::Scoring(const long arg_days, const std::vector<long>& arg_costs, const std::vector<std::vector<long>>& arg_incentives) {
    days = arg_days;
    costs = arg_costs;
    incentives = arg_incentives;
}

int main() {
    clock_t start_clock = clock();
    std::mt19937 engine(12345678);
    std::uniform_int_distribution<> type_random(1, type_num);
    std::uniform_int_distribution<> day_random(1, Day_num);
    long D;
    std::cin >> D;
    std::vector<long> costs(type_num);
    for (long type = 1; type <= type_num; ++type) {
        std::cin >> costs[type-1];
    }
    std::vector<std::vector<long>> incentives(D, std::vector<long>(type_num));
    for (long day = 1; day <= D; ++day) {
        for (long type = 1; type <= type_num; ++type) {
            std::cin >> incentives[day-1][type-1];
        }
    }

    Scoring scoring(D, costs, incentives);

    std::vector<long> types(D);
    for (long day = 1; day <= D; ++day) {
        types[day-1] = type_random(engine);
    }

    while (static_cast<double>(clock() - start_clock)/CLOCKS_PER_SEC*1000.0 < 2000.0-100.0) {
        const auto old_types = types;
        types[day_random(engine)-1] = type_random(engine);
        if (scoring.score(old_types).back() > scoring.score(types).back()) {
            types = old_types;
        }
    }

    for (long day = 1; day <= D; ++day) {
        std::cout << types[day-1] << std::endl;
    }
    //std::vector<long> types(D);
    //for (long day = 1; day <= D; ++day) {
    //    std::cin >> types[day-1];
    //}

    //long M;
    //std::cin >> M;

    //std::vector<std::array<long,2>> query(M);
    //for (long index = 0; index < M; ++index) {
    //    std::cin >> query[index][0];
    //    std::cin >> query[index][1];
    //}

    //Scoring scoring(D, costs, incentives);
    //for (long index = 0; index < M; ++index) {
    //    types[query[index][0]-1] = query[index][1];
    //    std::cout << scoring.score(types).back() << std::endl;
    //}
}

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

#define N 5005

int dp[2][N];

char s[N];
int n;

const int mod = 1e9 + 7;

void add(int &x, int y) {
	x += y;
	if (x >= mod) x -= mod;
}

int main() {
	dp[0][0] = 1;
	int u = 0, v = 1;
	scanf("%d %s", &n, s);
	int m = strlen(s);
	for (int i = 1; i <= n; i ++) {
		for (int j = 0; j < N; j ++) {
			dp[v][j] = 0;
			if (j > 0) add(dp[v][j], dp[u][j-1]);
			if (j+1 < N) add(dp[v][j], dp[u][j+1]), add(dp[v][j], dp[u][j+1]);
			if (j == 0) add(dp[v][j], dp[u][j]);
		}
		swap(u, v);
	}
	int ans = dp[u][m];
	printf("%d\n", ans);
	return 0;
}


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

typedef long long ll;
typedef vector<int> vi;

const int M = 1000000007, BIG = 0x3f3f3f3f;

int n;

bool Process() {
  

  return n >= 30;
}

void Output() { cout << (Process() ? "Yes\n" : "No\n"); }

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

  while (cin >> n)
    Output();

  return 0;
}

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

const int MAX_N = 300005;

int P[MAX_N], N, K;

int main() {
  scanf("%d%d", &K, &N);
  if (K % 2 == 0) {
    printf("%d ", K / 2);
    for (int i = 1; i < N; ++i) printf("%d ", K);
    puts("");
  } else {
    for (int i = 1; i <= N; ++i) P[i] = (K + 1) / 2;
    int rest = N / 2;
    if (K == 1) {
      for (int i = (N + 1) / 2 + 1; i <= N; ++i) P[i] = 0;
    } else {
      while (rest) {
	int last = N;
	while (P[last] == 0) last--;
	if (P[last] == 1) {
	  P[last] = 0;
	} else {
	  P[last]--;
	  for (int i = last + 1; i <= N; ++i) P[i] = K;
	}
	rest--;
      }
    }
    
    for (int i = 1; i <= N; ++i)
      if (P[i] != 0) printf("%d ", P[i]);
    puts("");
  }
  
  return 0;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
 
using namespace std;
 
#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplece_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define Edge pair< i_i, int>
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; scanf("%lld", &x);
#define int2(x, y) int x, y; scanf("%lld %lld", &x, &y);
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
 
//int dxy[5] = {0, 1, 0, -1, 0};
// assign
 
vi black, white;
int n;
vvi graph;
 
void dfsw(int pos, int dep)
{
    if (white[pos] != -1) return ;
    white[pos] = dep;
    rep(i, graph[pos].size()) {
        dfsw(graph[pos][i], dep+1);
    }
}
 
void dfsb(int pos, int dep)
{
    if (black[pos] != -1) return ;
    black[pos] = dep;
    rep(i, graph[pos].size()) {
        dfsb(graph[pos][i], dep+1);
    }
}
 
 
signed main()
{
    cin >> n;
    graph = vvi(n);
    black = vi(n, -1);
    white = vi(n, -1);
    rep(i, n-1) {
        int2(a, b);
        graph[a-1].pb(b-1);
        graph[b-1].pb(a-1);
    }
 
    dfsw(n-1, 0);
    dfsb(0, 0);
/*
    rep(i, n) {
        cout << white[i] << " ";
    }cout << endl;
    rep(i, n) {
        cout << black[i] << " ";
    }cout << endl;
*/
    int cnt = 0;
    rep(i, n) {
        cnt += (white[i] < black[i]) ? 1 : -1;
    }
    if (cnt < 0) {
        cout << "Fennec" << endl;
    } else {
        cout << "Snuke" << endl;
    }
 
    return 0;
}


Measured memory_bytes: 10368
BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

N,M = map(int,input().split())

A = [[] for i in range(N)]

for i in range(N):
    A[i] = list(map(int,input().split()))

B = [[0]*1 for i in range(M)]

for i in range(M):
    B[i] = int(input())


for row in range(N):
    tmp = 0
    for col in range(M):
        tmp += A[row][col]*B[col]
    print("%d"%(tmp))


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

int main() {
  long long a,b;
  cin>>a>>b;
  long long A=0;
  for(long long i=a;i<=b;i++){
    string s=to_string(i);
    if(s.at(0)==s.at(4)&&s.at(1)==s.at(3)){
      A++;
    }
  }
  cout<<A<< endl;
}
    

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

int diceProduct(int d1, int d2);

int diceProduct(int d1, int d2){
    int tmp;
    bool modifier = false;
    int tmpProduct;
    
    if(2 < d1){
        d1 = 5 - d1;
        modifier = !modifier;
    }
    
    if(2 < d2){
        d2 = 5 - d2;
        modifier = !modifier;
    }
    
    if(d1 == d2) return 0;
    
    if(d2 < d1){
        tmp = d1;
        d1 = d2;
        d2 = tmp;
        
        modifier = !modifier;
    }
    
    if(d1 == 0 && d2 == 1) tmpProduct = 2;
    if(d1 == 1 && d2 == 2) tmpProduct = 0;
    if(d1 == 0 && d2 == 2) tmpProduct = 4;
    
    if(!modifier) return tmpProduct;
    else return (5 - tmpProduct);
}

int main(void){
    int input[6];
    int i;
    int q;
    int top, south;
    int topIndex, southIndex, eastIndex;
    for(i = 0; i < 6; i++){
        cin >> input[i];
    }
    
    cin >> q;
    
    for (i = 0; i < q; i++){
        cin >> top >> south;
        for(topIndex = 0; topIndex < 6; topIndex++){
            if(input[topIndex] == top) break;
        }
        
        for(southIndex = 0; southIndex < 6; southIndex++){
            if(input[southIndex] == south) break;
        }
        eastIndex = diceProduct(topIndex, southIndex);
        cout << input[eastIndex] << endl;
    }

    return 0;
}

Measured memory_bytes: 3092
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

bool isAllDark(int H,int W,vector<vector<char>> m) {
    REP(i,H) {
        REP(j,W) {
            if (m[i+1][j+1]!='#') return false;
        }
    }
    return true;
}


void printVec(const int H, const int W,const vector<vector<char>> &v) {
    REP(i,H+2){
        REP(j,W+2) {
            cout << v[i][j];
        }
        cout << endl;
    }
}

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

    // create queue <position,depth>
    queue<pair<pair<int,int>,int>> que;

    int count = 0;
    //create map
    vector<vector<char>> m(H+2,vector<char>(W+2,'x'));
    REP(i,H) {
        string s;
        cin >> s;
        REP(j,W) {
            m[i+1][j+1] = s[j];
            // push to que
            if (s[j] == '#') {
                count++;
                auto pos = make_pair(i+1,j+1);
                auto q_el = make_pair(pos,1);
                que.push(q_el);
            }
        }
    }


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

    if (count == H*W) {
        cout << 0 << endl;
        return 0;
    }
    // bfs
    while(!que.empty()) {
        //printVec(H,W,m);
        //cout << endl;
        auto q_el = que.front(); que.pop();
        auto depth = q_el.second;
        auto pos = q_el.first;

        if (m[pos.first][pos.second]=='x') continue;
        if (m[pos.first][pos.second]=='.') return 2;

        // inject
        REP(i,4) {
            if (m[pos.first+dx[i]][pos.second+dy[i]]=='.'){
                m[pos.first+dx[i]][pos.second+dy[i]]='#';
                count++;
                auto next_pos = make_pair(pos.first+dx[i],pos.second+dy[i]);
                auto next_q_el = make_pair(next_pos,depth+1);
                que.push(next_q_el);
            }
        }
        if (count == H*W) {
            cout << depth << endl;
            return 0;
        }
    }
    return 1;
}


Measured memory_bytes: 13456
list1 = input().split()
list2 = input().split()
list3 = input().split()
flag = 0
for i in range(len(list1)):
  list1[i] = int(list1[i])
  i = i + 1
i=0
for i in range(len(list2)):
  list2[i] = int(list2[i])
  i = i + 1
i=0
for i in range(len(list3)):
  list3[i] = int(list3[i])
  i = i + 1
i=0
for i in range(len(list1)):
  j = 0
  for j in range(len(list2)):
    k = 0
    for k in range(len(list3)):
      if(list1[i] == list2[j] == list3[k]):
        print("NO")
        flag = 1
        break
if flag == 0:
  print("YES")

Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<algorithm>
typedef long long int ll;
using namespace std;

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define EREP(i,a) for (int i=1;i<=(a);i++)
const ll MOD = (10*10*10*10*10*10*10*10*10+7);

    int A,B,C;
    int N,M;
    int ans;
    bool f=true;

int main(){
    cin>>N;
    EREP(i,N){ans+=i;}
    cout<<ans<<endl;
    return 0;
}


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

int main() {
	int a=0, b=0, i, len;
	char *ptr, S[100010];
	scanf("%s", &S);
	len = strlen(S);

	for (i=0;i<26;i++) {
		ptr = memchr(S, i+97, sizeof(char)*len);
		while (ptr != NULL) {
			if (*(ptr+1) == i+97) {
				a = ptr - S;
				b = a + 1;
				break;
			} else if (*(ptr+2) == i+97) {
				a = ptr - S;
				b = a + 2;
				break;
			}
			ptr = memchr(ptr+1, i+97, sizeof(char)*(len-(ptr-S)));
		}
	}
	if (a == 0 && b == 0) {
		a = -2; b = -2;
	}

	printf("%d %d\n", a+1, b+1);
	return 0;
}


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

int main(){
	long long n,p,q,a,b;
	cin >> n;
	for(long long i = 1;i <= 3500;i++){
		for(long long j = 1;j <= i;j++){
			a = i,b = j;
			p = 4 * a * b - n * a - n * b;
			q = n * a * b;
			if(p > 0 && q % p == 0 && q / p <= 3500){
				cout << i << ' ' << j << ' ' << q / p;
				return 0;
			}
		}
	}
}

Measured memory_bytes: 384
def main():
  import sys
  n=int(input())
  AA=tuple(map(int,sys.stdin.readline().split()))
  b=[None]*n
  I=1
  for index in AA:
    b[index-1]=I
    I+=1
  print(" ".join(map(str,b)))
if __name__=="__main__":
  main()

Measured memory_bytes: 18316
#include<bits/stdc++.h>
#include<bitset>
using namespace std;
#define SZ(v) ((int)(v).size())
#define zero(v) memset(v,0,sizeof(v))
#define rep(i,n) for(int i=0;i<(n);i++)
#define foreach(it,c) for(__typeof(c.begin()) it=c.begin();it!=c.end();it++)
#define all(v) (v).begin(),(v).end()
template<typename T>inline bool chkmin(T &a,const T &b){return a>b?a=b,1:0;}
template<typename T>inline bool chkmax(T &a,const T &b){return a<b?a=b,1:0;}
typedef long long ll;
typedef unsigned uint;
const int INF=0x3f3f3f3f;
const double EPS=1e-10;
typedef pair<int,int> pii;
int inline in(){int x=0,c;for(;(uint)((c=getchar())-'0')>=10;)
{if(c=='-')return -in();if(!~c)throw ~0;}do{x=(x<<3)+(x<<1)+(c-'0');}
while((uint)((c=getchar())-'0')<10);return x;}
int n;
const int Maxn=2e5+5;
bitset<32>a[Maxn],restore[Maxn];
int main(){
	cin>>n;
	rep(i,n){
		int x;
		cin>>x;
		a[i]=x;
	}
	rep(i,32){
		int sum1=0;
		rep(j,n){
			restore[j][i]=a[j][i];
			if(restore[j][i]==1)sum1++;
		}
		bool out=false;
		rep(j,n){
			if(restore[j][i]==0){
				if(a[j][i]!=sum1%2){
					out=true;break;
				}
			}else{
				if(a[j][i]!=(sum1-1)%2){
					out=true;break;
				}
			}
		}
		if(!out)continue;
		rep(j,n)restore[j].flip(i);
	}
	rep(i,n)cout<<restore[i].to_ulong()<<' ';cout<<endl;
	return 0;
}

Measured memory_bytes: 6768
#include<stdio.h>

int main(void){
    int m,s;
    int i,j;
    int count=0;

    scanf("%d%d", &m,&s);

    for(i=0;i<=m;i++){
        for(j=0;j<=m;j++){
            if(i+j<=s && s-i-j<=m){
                count +=1;
            }
            
            
        }
    }

    printf("%d", count);

    return 0;
}

Measured memory_bytes: 128
//abc141D
int compare_int(const void *a, const void *b) {
  return *(int*) a - *(int*) b;
}

int main(void) {
  int n, m, i, cou=0;
  long long sum=0;
  scanf("%d %d", &n, &m);
  int a[n];
  for(i=0; i < n; i++) scanf("%d", &a[i]);

  qsort(a, n, sizeof(int), compare_int);
  i=n - 1;
  while(cou < m){//チケットを使った回数がm回未満の間
    if(i == -1) i=n - 1;//配列の先頭を超えたら末尾から再開
    else if((i == n - 1) || (a[i] > a[n-1])) a[i--]/=2, cou++;//末尾OR末尾の要素より大なら1/2
    else{//1/2しようとした要素が最大の要素でなければ再ソートして末尾から再開
      qsort(a, n, sizeof(int), compare_int);
      i=n - 1;
    }
  }
  for(i=0;i<n;i++)sum+=a[i];
  printf("%lld",sum);
}

Measured memory_bytes: 1012
import sys


def read():
    return sys.stdin.readline().rstrip()


def main():
    n, m = map(int, read().split())
    a = sorted(int(i) for i in read().split())
    bc = [(0, 0) for _ in range(m)]
    for i in range(m):
        b, c = map(int, read().split())
        bc[i] = (c, b)
    bc.sort(reverse=True)
    k = 0
    d = []
    for c, b in bc:
        if k + b > n:
            d += [c] * (n - k)
            break
        d += [c] * b
        k += b
    for i in range(len(d)):
        if a[i] < d[i]:
            a[i] = d[i]
        else:
            break
    print(sum(a))


if __name__ == '__main__':
    main()


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

class UnionFind {
public:
  vector<int> parent;
  UnionFind(int n) { parent = vector<int>(n, -1); }
  int root(int a) {
    if(parent[a] < 0)
      return a;
    return parent[a] = root(parent[a]);
  }
  int size(int a) { return -parent[root(a)]; }
  bool connect(int a, int b) {
    a = root(a);
    b = root(b);
    if(a == b)
      return false;
    if(size(a) < size(b))
      swap(a, b);
    parent[a] += parent[b];
    parent[b] = a;
    return true;
  }
};

int main() {
  int h, w, d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  cin >> h >> w;
  vector<vector<int>> bw(h, vector<int>(w));
  UnionFind uni(h * w);
  for(int i = 0; i < h; i++) {
    for(int j = 0; j < w; j++) {
      char c;
      cin >> c;
      if(c == '.')
        bw.at(i).at(j)++;
    }
  }
  for(int i = 0; i < h; i++) {
    for(int j = 0; j < w; j++) {
      for(int k = 0; k < 4; k++) {
        int y = i + d[k][0], x = j + d[k][1];
        if(0 <= y && y < h && 0 <= x && x < w)
          if(bw.at(i).at(j) != bw.at(y).at(x))
            uni.connect(w * i + j, w * y + x);
      }
    }
  }
  vector<pair<ll, ll>> p(h * w);
  for(int i = 0; i < h * w; i++) {
    if(bw.at(i / w).at(i % w))
      p.at(uni.root(i)).second++;
    else
      p.at(uni.root(i)).first++;
  }
  ll o = 0;
  for(int i = 0; i < h * w; i++)
    o += p.at(i).first * p.at(i).second;
  cout << o << endl;
}

Measured memory_bytes: 3968
#include<iostream>
#include <list>
#include<stack>
#include<queue>
#include <vector>
#include <set>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<string>
#include <functional>
#include<fstream>

#define FOR(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define LL long long
#define CLR(a) memset((a),0,sizeof(a))
#define SZ(x) (int((x).size()))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<<str<<endl
using namespace std;

const LL MOD = 1000000007;// 10^9+7
const int INF = (1 << 30);



//計算
void calc(const vector<string> f)
{
	//variable
	int res = 0;
	bool bodyFloor = true;
	pair<bool, bool> footFloor = { true,true };
	
	//calc
	for (auto s : f) {
		bool left = (s[0] == 'l');
		bool floor = (s[1] == 'd');
		//move
		if (left) {
			footFloor.first = floor;
		}
		else {
			footFloor.second = floor;
		}
		//count
		if (bodyFloor != footFloor.first&&
			bodyFloor != footFloor.second) {
			res++;
			bodyFloor = footFloor.first;
		}
	}


	//output
	cout << res << endl;
}


//デバッグ
void debug()
{
	int N;
	cin>>N;
}


//メイン関数
int main()
{
	while (true) {
		int n;
		vector<string> f;
		cin >> n;
		if (n == 0)break;
		f.resize(n);
		REP(i, n)cin >> f[i];
		calc(f);
	}
	debug();
	
	return 0;
}




Measured memory_bytes: 3016
import sys
readline = sys.stdin.readline

class BIT:
    #1-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.p = 2**(n.bit_length() - 1)
        self.dep = n.bit_length()
    def get(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
    
    def bl(self, v):
        if v <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < v:
                s += k
                v -= self.tree[s+k]
            k //= 2
        return s + 1
    
    def reset(self):
        self.tree = [0]*(self.size+1)

N = int(readline())
INF = 2e8 + 10
EPS = 1e-9

Points = [tuple(map(int, readline().split())) for _ in range(N)]
Points.sort(key = lambda x: -x[0]/x[1])
XA = [-a/b for a, b, _ in Points]
XB = [c/b for _, b, c in Points]
Points.sort(key = lambda x: -x[1]/x[0])
YA = [-b/a for a, b, _ in Points]
YB = [c/a for a, _, c in Points]
con = -(-N*(N-1)//4)
T = BIT(N)

ng = -INF
ok = INF
nf = con
of = con


while abs(ok-ng)/max(1, min(abs(ok), abs(ng))) > EPS:
    med = (ok*nf+ng*of)/(of+nf)
    T.reset()
    res = 0
    for idx in sorted(range(N), key = lambda x: XA[x]*med + XB[x]):
        res += T.get(idx+1)
        T.add(idx+1, 1)
    if res >= con:
        ok = med
        of = ((res - con)*2 + 1) ** 0.3
    else:
        ng = med
        nf = ((con - res)*2) ** 0.3

X = ok

ng = -INF
ok = INF
nf = con
of = con

cnt = 1
while abs(ok-ng)/max(1, min(abs(ok), abs(ng))) > EPS:
    cnt += 1
    med = (ok*nf+ng*of)/(of+nf)
    T.reset()
    res = 0
    for idx in sorted(range(N), key = lambda x: YA[x]*med + YB[x]):
        res += T.get(idx+1)
        T.add(idx+1, 1)
    if res >= con:
        ok = med
        of = ((res - con)*2 + 1) ** 0.3
    else:
        ng = med
        nf = ((con - res)*2) ** 0.3

Y = ok

print(X, Y)


Measured memory_bytes: 130880
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
const int MAXN=2005;
vector<int> nxt[MAXN];
int cal[MAXN],vis[MAXN],n,id[MAXN];
bool cmp(int n1,int n2){return cal[n1]<cal[n2];}
priority_queue<pii> hp;
int gcd(int a,int b){return a==0?b:gcd(b%a,a);}
int du[MAXN];
void dfs(int x,int up)
{
	if(up)nxt[up].push_back(x),++du[x];vis[x]=1;
	for(int i=1;i<=n;i++)if(!vis[id[i]]&&gcd(cal[id[i]],cal[x])!=1)
		dfs(id[i],x);
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)cal[i]=read(),id[i]=i;
	sort(id+1,id+1+n,cmp);
	for(int i=1;i<=n;i++)if(!vis[id[i]])
		hp.push(mp(cal[id[i]],id[i])),dfs(id[i],0);
	while(!hp.empty())
	{
		int x=hp.top().second;hp.pop();pr1(cal[x]);
		for(int k=0;k<nxt[x].size();k++)
		{
			int y=nxt[x][k];
			--du[y];if(!du[y])hp.push(mp(cal[y],y));
		}
	}
	return 0;
}


Measured memory_bytes: 512
#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>;

int main(){
    int n;
    string s;
    cin >> n;
    cin >> s;
    int ans;
    ans=0;
    rep(i,n-1){
        if(s[i]==s[i+1]){
            ++ans;
        }
    }
    
cout << n-ans << endl;
    return 0;
}

Measured memory_bytes: 512