akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace C
{
    class Program
    {
        static void Main(string[] args)
        {

            int n = RInt();

            int res = 0;
            int firstB = 0;
            int lastA = 0;
            int self = 0;
            for (int i = 0; i < n; i++)
            {
                string s = RSt();
                if (s[0] == 'B') firstB++;
                if (s[s.Length - 1] == 'A') lastA++;
                if (s[0] == 'B' && s[s.Length - 1] == 'A') self++;
                string rep = s.Replace("AB", "");
                res += (s.Length - rep.Length) / 2;
            }

            if (lastA != firstB)
            {
                res += Math.Min(firstB, lastA);
            }
            else
            {
                if (lastA == self && self > 0)
                {
                    res += lastA - 1;
                }
                else
                {
                    res += lastA;
                }
            }

            Console.WriteLine(res);

        }
        static string RSt() { return Console.ReadLine(); }
        static int RInt() { return int.Parse(Console.ReadLine().Trim()); }
        static long RLong() { return long.Parse(Console.ReadLine().Trim()); }
        static double RDouble() { return double.Parse(Console.ReadLine()); }
        static string[] RArSt(char sep = ' ') { return Console.ReadLine().Trim().Split(sep); }
        static int[] RArInt(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => int.Parse(e)); }
        static long[] RArLong(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => long.Parse(e)); }
        static double[] RArDouble(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => double.Parse(e)); }
        static string WAr<T>(IEnumerable<T> array, string sep = " ") { return string.Join(sep, array.Select(x => x.ToString()).ToArray()); }
    }
}


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

using namespace std;

#define MAX 10000
int arr[MAX+2],N;

int solve(int p){
  int lp = p, rp = p+1;

  while(true){
    if(lp <= 0 || rp >= N+1) break;
    int color = arr[lp],l,r;
    for(l = lp ; arr[l] == color ; l--);
    for(r = rp ; arr[r] == color ; r++);
    if((r-rp)+(lp-l) < 4) break;
    lp = l, rp = r;
  }
  return N - rp + lp + 1;
}

int main(){
  while(cin >> N, N){
    memset(arr,0,sizeof(arr));
    for(int i = 1 ; i <= N ; i++){
      cin >> arr[i]; 
    }
    int ans = MAX;
    for(int i = 1 ; i <= N ; i++){
      int tmp = arr[i];
      for(int j = 0 ; j < 3 ; j++){
        if(arr[i] == j+1) continue;
        arr[i] = j+1;
        ans = min(ans,solve(i));   
      }
      arr[i] = tmp;
    }
    cout << ans << endl;
  }

  return 0;
}

Measured memory_bytes: 1208
#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
  int tt,ta,at,aa;
  cin >> tt >> ta >> at >> aa;
  
  bool twin;
  while(true)
  {
    at -= ta;
    if(at<=0)
    {
      twin = true;
      break;
    }
    
    tt -= aa;
    if(tt<=0)
    {
      twin=false;
      break;
    }
  }
  
  if(twin)
  {
    cout << "Yes" << endl;
  }
  else
  {
        cout << "No" << endl;
  }
  
  return 0;
}

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


signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int L, R;
    cin >> L >> R;
    if (R - L >= 2018) {
        cout << 0 << endl;
        return 0;
    }
    int min = 1e9;
    for (int i = L; i < R; i++) {
        for (int j = i + 1; j <= R; j ++) {
            int tmp =(i * j) % 2019;
            if (tmp < min) {
                min = tmp;
            }
        }
    }
    cout << min << endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int n,i,m,d[1001],g,r,s;
  while(scanf("%d %d",&n,&m),n||m){
    for(i=0;i<n;i++)scanf("%d",&d[i+1]);
    g=1;
    r=0;
    for(i=0;i<m;i++){
      scanf("%d",&s);
      g+=s;
      if(g<n)g+=d[g];
      if(r==0&&g>=n)r=i;
    }
    printf("%d\n",r+1);
  }
  return 0;
}

Measured memory_bytes: 600
import itertools


n, m = map(int, input().split())
KS = []
for _ in range(m):
    ks = list(map(int, input().split()))
    KS.append(ks)
P = list(map(int, input().split()))

C = list(itertools.product((0, 1), repeat = n))

ans = 0
for c in C:
    l = 0
    for i in range(m):
        k = KS[i][0]
        o = 0
        for j in range(k):
            s = KS[i][j + 1]
            o += c[s - 1]
        if o % 2 == P[i]:
            l += 1
    if l == m:
        ans += 1

print(ans)


Measured memory_bytes: 3188
package main

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

func main() {
	N := nextInt()

	v := float64(0)

	for i := 0; i < N; i++ {
		a := nextInt()
		v += 1 / float64(a)
	}
	v = 1 / v
	fmt.Println(v)
}

var stdin = initStdin()

func initStdin() *bufio.Scanner {
	bufsize := 1 * 1024 * 1024 // 1 MB
	var stdin = bufio.NewScanner(os.Stdin)
	stdin.Buffer(make([]byte, bufsize), bufsize)
	stdin.Split(bufio.ScanWords)
	return stdin
}

func nextString() string {
	stdin.Scan()
	return stdin.Text()
}

func nextBytes() []byte {
	stdin.Scan()
	return stdin.Bytes()
}

func nextInt() int {
	i, _ := strconv.Atoi(nextString())
	return i
}

func nextInt64() int64 {
	i, _ := strconv.ParseInt(nextString(), 10, 64)
	return i
}


Measured memory_bytes: 640
/*by freesteed*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define pb push_back
#define fill(x,c) memset(x,c,sizeof(x))
#define fi first
#define se second
#define sz(A) (int)(A.size())
#define all(x) (x).begin(),(x).end()
#define caset int ___T; cin>>___T; for(int cs=1;cs<=___T;cs++)
#define get_be(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
//get_be biger & equal
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
const ll mod=1e9+7;
const ll oo=1e9+10;
const int Max = 1e6+10;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
//ll a[Max];
ll n;
void solve(){
	int a,b,c;
	cin>>a>>b>>c;
	cout<<(a+b+c>=22?"bust":"win");
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//caset{
		solve();
	//}
  	return 0;
}





Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,k;
  string s;
  cin >> n >> k >> s;
  if(s.at(k-1) == 'A'){
    s.at(k-1) = 'a';
  }else if(s.at(k-1) == 'B'){
    s.at(k-1) = 'b';
  }else{
    s.at(k-1) = 'c';
  }
  cout << s << endl;
}

Measured memory_bytes: 256
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();
		int area = a*b;
		int length = 2*(a+b);
		System.out.println(area + " " + length);
	}
}

Measured memory_bytes: 26004
#include <stdio.h>
int main(){
    bool prime[1000000];
    int n,ans;
    prime[2]=true;
    for(int i=3;i<1000000;i+=2)prime[i]=true;
    for(int i=3;i<=1000;i+=2){
        if(prime[i]){
            for(int j=i*i;j<1000000;j+=i)
                prime[j]=false;
        }
    }
    while(scanf("%d",&n)!=EOF){
        ans=1;
        if(n<3){printf("%d\n",n-1);
            continue;}
    for(int i=3;i<=n;i+=2)if(prime[i])ans++;
        printf("%d\n",ans);
    }
}

Measured memory_bytes: 3584
#include <iostream>
#include <algorithm>

using namespace std;

int solve1(long long h, long long w) {
	long long tmp = 1e9, s[3] = {};
	for (int i = 1; i < h; ++i) {
		s[0] = w * i;
		s[1] = (w / 2) * (h - i);
		s[2] = h * w - s[0] - s[1];
		tmp = min(tmp, *max_element(s, s + 3) - *min_element(s, s + 3));
	}
	return tmp;
}

int solve2(long long h, long long w) {
	long long tmp = 1e9, s[3] = {};
	for (int i = 1; i < h; ++i) {
		s[0] = w * i;
		s[1] = w * ((h - i) / 2);
		s[2] = h * w - s[0] - s[1];
		tmp = min(tmp, *max_element(s, s + 3) - *min_element(s, s + 3));
	}
	return tmp;
}

int main() {
	long long h, w; cin >> h >> w;
	long long minhw = min(h, w), maxhw = max(h, w);
	int ans = 1e9;
	ans = min({ ans, solve1(h, w), solve1(w, h) });
	ans = min({ ans, solve2(h, w), solve2(w, h) });
	cout << ans << endl;

	return 0;
}

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

using namespace std;

const int MOD = 1000000007;
typedef pair<int, int> P;
typedef long long ll;
#define rep(i, n) for(int i=0;i<n;i++)
#define rep2(i, m, n) for(int i=m;i<n;i++)
#define rrep(i, n, m) for(int i=n;i>=m;i--)
using Graph = vector<vector<int>>;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
#ifdef __DEBUG

#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    int N, D;
    cin >> N >> D;
    vector<vector<int>> a(N);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < D; ++j) {
            int s;
            cin >> s;
            a[i].push_back(s);
        }
    }
    ll ans = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = i; j < N; ++j) {
            if (i == j) {
                continue;
            }else{
                ll tmp = 0;
                for (int d = 0; d < D; ++d) {
                    int y = a[i][d];
                    int z = a[j][d];
                    tmp += pow(abs(z-y) , 2);
                }
                for (int x = 1; x <= tmp; ++x) {
                    if (pow(x, 2) == tmp) {
                        ans ++;
                        break;
                    }
                }
            }
        }
    }
    cout << ans << endl;

}

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


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

Frg = True #True => 'Yes'

for i in range(N-1, 1,-1):
  if H[i-1] > H[i]:
    H[i-1] -= 1
    if H[i-1] > H[i]:
      Frg = False
      break

print('Yes' if Frg else 'No')

Measured memory_bytes: 15020
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
long N,X,D,ans;
long L[2<<17],R[2<<17];
long gcd(long a,long b){return b?gcd(b,a%b):a;}
vector<pair<long,int> >A[2<<17];
main()
{
	cin>>N>>X>>D;
	if(D==0)
	{
		cout<<(X==0?1:N+1)<<endl;
		return 0;
	}
	long g=gcd(X>0?X:-X,D>0?D:-D);
	X/=g;
	D/=g;
	long diff=D>0?D:-D;
	for(long i=0;i<=N;i++)
	{
		L[i]=i*(i-1)/2;
		R[i]=L[i]+(N-i)*i;
		L[i]+=i/D*X;
		R[i]+=i/D*X;
		int j=i%diff;
		A[j].push_back(make_pair(L[i],1));
		A[j].push_back(make_pair(R[i]+1,-1));
	}
	for(int i=0;i<=N&&i<diff;i++)
	{
		if(A[i].empty())continue;
		sort(A[i].begin(),A[i].end());
		int cnt=A[i][0].second;
		long pre=A[i][0].first;
		for(int j=1;j<A[i].size();j++)
		{
			if(cnt>0)
			{
				ans+=A[i][j].first-pre;
			}
			cnt+=A[i][j].second;
			pre=A[i][j].first;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 20992
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

n = int(input())

sum_ = 0
for a in range(1, n+1):
  for b in range(1, n+1):
    for c in range(1, n+1):
      sum_ += gcd(a, b, c)
    
print(sum_)

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

int main(){
    int h, w;
    cin >> h >> w;
    vector<string> p;
    rep(hi, 0, h+2){
        string s = "";
        rep(wi, 0, w+2){
            s += "#";
        }
        p.push_back(s);
    }
    rep(i, 1, h+1){
        string s;
        cin >> s;
        p[i] = '#' + s + '#';
    }
    for (auto pi:p){
        cout << pi << endl;
    }
   return 0;
}

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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(), (v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)

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

struct edge {
	int to,cost;
	edge(int t,int c):to(t),cost(c) {}
};

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

ll mypow(ll x,ll n,ll m) {	//xのn乗をmで割った余り
	if(n==0) return 1;
	if(n%2==0) return mypow(x*x%m,n/2,m);
	else return x*mypow(x,n-1,m)%m;
}

//-----------------------------------------------------------------------------

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

	string s;
	cin>>s;
	deque<int> dq;
	REP(i,s.size()) {
		if(s[i]!='B') dq.pb(s[i]-'0');
		else if(dq.size()) dq.pop_back();
	}
	REP(i,dq.size()) cout<<dq[i];
	cout<<endl;

	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int main()
{
    // input
    int n, a, b;
    std::cin >> n >> a >> b;
    std::string str;
    // input end

    int sum = 0;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        str = std::to_string(i);
        for (auto s : str) { sum += s - '0'; }
        if (a <= sum && sum <= b) { ans += i; }
        sum = 0;
    }

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

Measured memory_bytes: 256
#include <stdio.h>

int main(int argc, char const *argv[])
{
	int a, b, count, sum;
	while(scanf("%d%d", &a, &b)!=EOF) {
		count = 1;
		sum = a+b;
		while((sum/=10)!=0) {
			count++;
		}
		printf("%d\n", count);
	}
	return 0;
}

Measured memory_bytes: 2580
n = int(input())
w = list(map(int,input().split()))
#print(w)
#print(sum(w))
a=[]
for i in range(n):
  before = sum(w[:i+1])
  #print(before)
  after = sum(w[i+1:])
  #print(after)
  a.append(abs(before - after))
  #print(a)
print(min(a))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define INF 1000000007
int u[1100000];
vector<int> y;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a,b,c,d=0,e=0,f=0,g=0;
  cin >>a>>b;
  if(a%b>0) cout <<"1\n";
  else cout <<"0\n";
  return (0);
}


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

int main(){
    string s;
    cin >> s;
    ll n = s.size()+1;

    vector<ll> a(n,0);
    vector<ll> b(n,0);
    ll ans = 0;

    for(ll i=0; i<n-1; i++){
        if(s[i] == '<'){
            a[i+1] = a[i] + 1;
        }
    }

    for(ll i=n-2; i>=0; i--){
        if(s[i] == '>'){
            b[i] = b[i+1] + 1;
        }
    }

    rep(i,n){
        ans += max(a[i], b[i]);
    }

    cout << ans << endl;
}

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

typedef long long ll;
const ll INF = 1010000000000000017LL;
const ll MOD = 1000000007LL;

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

//#define DEBUG(fmt, ...)
#define DEBUG(fmt, ...) fprintf(stderr, fmt "\n", ##__VA_ARGS__)

int main(){
    std::cout<<std::fixed<<std::setprecision(10);

    ll N;
    ll M;
    ll K;

    cin >> N >> M >> K;

    vector<unordered_set<ll>> friends(N+1, unordered_set<ll>());
    REP(i, M){
        ll A, B;
        cin >> A >> B;
        friends[A].insert(B);
        friends[B].insert(A);
    }

    vector<bool> visited(N+1, false);
    vector<unordered_set<ll>> clasters;
    queue<ll> q;
    REP(i, N){
        if( visited[i+1] == false){
            unordered_set<ll> claster;
            q.push(i+1);
            visited[i+1] = true;
            claster.insert(i+1);
            while(!q.empty()){
                ll cur = q.front();
                q.pop();
                for(auto f : friends[cur]){
                    if( !visited[f] ){
                        claster.insert(f);
                        q.push(f);
                        visited[f] = true;
                    }
                }

            }
            clasters.push_back(claster);
        }
    }

    vector<ll> candidates(N+1, 0);
    vector<const unordered_set<ll>*> pClaster(N+1, NULL);
    for( auto const &claster : clasters ){
        for( auto f : claster){
            candidates[f] = claster.size() - friends[f].size() - 1;
            pClaster[f] = &claster;
        }
    }


    REP(i, K){
        ll C, D;
        cin >> C >> D;
        if( pClaster[C]->find(D) != pClaster[C]->end() ){
            candidates[C]--;
            candidates[D]--;
        }
    }

    REP(i, N){
        cout << candidates[i+1] << " ";
    }
    cout << endl;

    return 0;

}


Measured memory_bytes: 27980
#include <bits/stdc++.h>
using namespace std;
  
int main(){
  int n,a;
  cin>>n>>a;
  cout<<n*n-a<<endl;
  return 0;
}
   
 
      
 
  
   
  
	
	  
	  
	  
	  
	  
	  
     
  
  
  
  
  

  

 
  


 

    
  


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int W, H, x, y, r, x1, y1;
    cin>>W>>H>>x>>y>>r;
    y1=H-r;
    x1=W-r;
    if(y<=y1 && x<=x1 && x>=r && y>=r)
    cout<<"Yes"<<endl;
    else
    cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 3116
#include <iostream>
#include <fstream>
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <numeric>
#include <functional>
#include <string> 
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>

using namespace std;
using ll = long long;

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;

#define REP(i,n) for(int i = 0; i < int(n); i++)
#define FOR(i, m, n) for(int i = int(m);i < int(n);i++)
#define ALL(obj) (obj).begin(),(obj).end()

const ll MOD = (ll)1e9 + 7;
const ll HINF = (ll)1e18;
const ll LINF = (ll)1e9;
const long double PI = 3.1415926535897932384626433;

vector<int> dy = { 0,0,1,-1 };
vector<int> dx = { 1,-1,0,0 };

template<class T> void corner(bool flg, T hoge) {
	if (flg) {
		cout << hoge << endl;
		exit(0);
	}
	else return;
}

template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {
	o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;
}

template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {
	o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;
}

template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {
	o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;
}

template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {
	o << "{" << obj.first << ", " << obj.second << "}"; return o;
}

template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {
	o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;
}

void print(void) {
	cout << endl;
}

template <class Head> void print(Head&& head) {
	cout << head;
	print();
}

template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {
	cout << head << " ";
	print(forward<Tail>(tail)...);
}

void YN(bool flg) {
	cout << ((flg) ? "YES" : "NO") << endl;
}

void Yn(bool flg) {
	cout << ((flg) ? "Yes" : "No") << endl;
}

void yn(bool flg) {
	cout << ((flg) ? "yes" : "no") << endl;
}


int main() {
	int N; cin >> N;
	V<P<ll, ll>> ord(N);
	REP(i,N) {
		ll A, B; cin >> A >> B;
		ord[i] = { A,B };
	}
	sort(ALL(ord));
	ll ans = ord[N - 1].first + ord[N - 1].second;
	cout << ans << endl;

	
	return 0;
}



Measured memory_bytes: 1792
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;

double Sines(double a, double b, double Z){
	double S = a * b * sin(Z) / 2;
	return S;
}

double Cosines(double a, double b, double Z){
	double c = sqrt( a * a + b * b - 2 * a * b * cos(Z) );
	return c;
}

int main(){
	double a, b;
	int C;
	cin >> a >> b >> C;
	double Z = M_PI * C / 180;
	double S = Sines(a, b, Z);
	double c = Cosines(a, b, Z);
	double L = a + b + c;
	double h = 2 * S / a;
	cout << fixed << setprecision(8) << S << endl << L << endl << h << endl;
	return 0;
}

Measured memory_bytes: 1340
H,W,K=map(int,input().split())
mat=[input() for _ in range(H)]

ans=0
for matR in range(2**H):
    for matC in range(2**W):
        cnt=0
        for i in range(H):
            for j in range(W):
                if (matR>>i)&1 and (matC>>j)&1:
                    if mat[i][j]=="#":
                        cnt+=1
        if cnt==K:
            ans+=1

print(ans)

Measured memory_bytes: 9108
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <cstring>
#include <string>
#include <bitset>
#include <stdlib.h>
#include <time.h> 
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void wenjian(){freopen("concatenation.in","r",stdin);freopen("concatenation.out","w",stdout);}
void tempwj(){freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){a %= mod;ll ans = 1;while(b){if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp{bool operator()(const pii & a, const pii & b){return a.second > b.second;}};
int lb(int x){return  x & -x;}

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+7;
const int maxn = 1e5+5;
ll cnt[maxn];

int main()
{
	int n;
	scanf("%d",&n);
	ll sum = 0;
	for (int i = 1; i <= n; i ++ )
	{
		int x;
		scanf("%d",&x);
		sum += x;
		cnt[x] ++ ;
	}
	int m;
	scanf("%d",&m);
	while(m -- )
	{
		int x,y;
		scanf("%d%d",&x,&y);
		sum -= cnt[x] * x;
		sum += cnt[x] * y;
		cnt[y] += cnt[x];
		cnt[x]  =0;
		printf("%lld\n",sum);
	}
}

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

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

#define pb push_back
#define rep(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, n) for(int i = a; i < (n); i++)
#define mod (ll)(1e9+7)
#define int ll

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
	ll n, a;
  set<int> num;
  cin >> n;
  rep(i, n) {
    cin >> a;
    auto itr = num.find(a);
    if (itr != num.end() && *itr == a) {
      num.erase(a);
    } else {
      num.insert(a);
    }
  }
  cout << num.size() << endl;
}

Measured memory_bytes: 4992
# (1)ABが含まれる個数・・・まず単純にカウント
# (2)Aで終わるけどBで始まらないものの個数
# (3)Bで始まるものAで終わらないもののの個数
# (4)Bで始まってAで終わるものの個数 の個数 - 1
# (4)が1以上ある場合、(2),(3)を一つずつ使うことでそれぞれ+1
# それでも(2)(3)のペアが作れればペアごとに+1

import sys
readline = sys.stdin.readline

N = int(readline())
ans = 0
a_end = 0
b_start = 0
a_end_b_start = 0

for i in range(N):
  s = readline().rstrip()
  ans += s.count("AB")
  if s[-1] == "A" and s[0] == "B":
    a_end_b_start += 1
  elif s[-1] == "A":
    a_end += 1
  elif s[0] == "B":
    b_start += 1

if a_end_b_start > 0:
  ans += a_end_b_start - 1
  if a_end > 0:
    a_end -= 1
    ans += 1
  if b_start > 0:
    b_start -= 1
    ans += 1

ans += min(a_end,b_start)
print(ans)

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

#define INF 1E18



int main(){
    ll n,m;
    cin>>n>>m;
    vector<ll> p(m);
    vector<string> s(m);
    rep(i,m){
        cin>>p[i];
        cin>>s[i];
    }

    vector<string> judge(n+1,"non");
    vector<int> wa_count(n+1);
    int ac  = 0;
    int wa = 0;

    rep(i,m){
        if(judge[p[i]]=="AC") continue;
        else{
            if((s[i]=="WA")){
                judge[p[i]] = "WA";
                ++wa_count[p[i]];
            }
            else if((s[i]=="AC")){
                judge[p[i]] = "AC";
                ++ac;
                wa += wa_count[p[i]];
            }
        }
    }

    cout << ac << " " << wa << endl;

    return 0;
}


Measured memory_bytes: 10648
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_macros)]
#![allow(unused_imports)]

use std::str::FromStr;
use std::io::*;
use std::collections::*;
use std::cmp::*;

struct Scanner<I: Iterator<Item = char>> {
    iter: std::iter::Peekable<I>,
}

macro_rules! exit {
    () => {{
        exit!(0)
    }};
    ($code:expr) => {{
        if cfg!(local) {
            writeln!(std::io::stderr(), "===== Terminated =====")
                .expect("failed printing to stderr");
        }
        std::process::exit($code);
    }}
}

impl<I: Iterator<Item = char>> Scanner<I> {
    pub fn new(iter: I) -> Scanner<I> {
        Scanner {
            iter: iter.peekable(),
        }
    }

    pub fn safe_get_token(&mut self) -> Option<String> {
        let token = self.iter
            .by_ref()
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        if token.is_empty() {
            None
        } else {
            Some(token)
        }
    }

    pub fn token(&mut self) -> String {
        self.safe_get_token().unwrap_or_else(|| exit!())
    }

    pub fn get<T: FromStr>(&mut self) -> T {
        self.token().parse::<T>().unwrap_or_else(|_| exit!())
    }

    pub fn vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
        (0..len).map(|_| self.get()).collect()
    }

    pub fn mat<T: FromStr>(&mut self, row: usize, col: usize) -> Vec<Vec<T>> {
        (0..row).map(|_| self.vec(col)).collect()
    }

    pub fn char(&mut self) -> char {
        self.iter.next().unwrap_or_else(|| exit!())
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.get::<String>().chars().collect()
    }

    pub fn mat_chars(&mut self, row: usize) -> Vec<Vec<char>> {
        (0..row).map(|_| self.chars()).collect()
    }

    pub fn line(&mut self) -> String {
        if self.peek().is_some() {
            self.iter
                .by_ref()
                .take_while(|&c| !(c == '\n' || c == '\r'))
                .collect::<String>()
        } else {
            exit!();
        }
    }

    pub fn peek(&mut self) -> Option<&char> {
        self.iter.peek()
    }
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin.bytes().map(|c| c.unwrap() as char));
    let s: Vec<char> = sc.chars();
    let N = s.len();
    let K: usize = sc.get();
    let mut sub = BTreeSet::new();
    for w in 1..min(N+1, K+1) {
        for l in 0..N-w+1 {
            let sub_s = &s[l..l+w];
            sub.insert(sub_s);
        }
    }
    let mut sub: Vec<&[char]> = sub.into_iter().collect();
    sub.sort();
    let ans: String = sub[K-1].iter().map(|&c| c).collect();
    println!("{}", ans);
}


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

int main()
{
  long long n, a, b;
  cin >> n >> a >> b;
  if(n == 1)
  {
    if(a == b)cout << 1 << endl;
    else cout << 0 << endl;
  }
  else if(a > b)
  {
    cout << 0 << endl;
  }
  else
  {
    cout << (n-2)*(b-a)+1 << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
  int n, i, j, k;
  int x = 0;
  int y = 0;
  char s[100] = {};

  scanf("%d", &n);

  for(i=0; i<n; i++)
  {
    scanf("%s", &s[i]);
    if(s[i] == '(')
    {
      x++;
    }
    else
    {
      if(x > 0)
      {
        x--;
      }
      else
      {
        y++;
      }
    }
  }
  for(j=0; j<y; j++)
  {
    printf("(");
  }
  printf("%s", s);
  for(k=0; k<x; k++)
  {
    printf(")");
  }
}


Measured memory_bytes: 128
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, K = list(map(int, sys.stdin.buffer.readline().split()))
S = sys.stdin.buffer.readline().decode().rstrip()

if '1' not in S or '0' not in S:
    print(N)
    exit()

ans = 0
l = 0
r = S.index('0')
k = 0
while r < N:
    while r < N and k < K:
        while r < N and S[r] == '0':
            r += 1
        while r < N and S[r] == '1':
            r += 1
        k += 1
    ans = max(ans, r - l)
    k -= 1
    while l < N and S[l] == '1':
        l += 1
    while l < N and S[l] == '0':
        l += 1
print(ans)


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

#define int long long
using namespace std;
#define rep(i, n) for(int i=0;i<(n);++i)
typedef pair<int, int> pii;
const int INF = 1l << 60;


signed main() {
    int x, y;
    cin >> x >> y;
    int ans = 0;
    if (x <= 3)ans += 400000 - 100000 * x;
    if (y <= 3)ans += 400000 - 100000 * y;
    if (x == 1 && y == 1)ans += 400000;
    cout << ans << endl;
    return 0;
}


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

//#define int long long
#define DBG 1
#define dump(o) if(DBG){cerr<<#o<<" "<<(o)<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);

//?´?????????????????§????
class UnionFind {
public:
	vector<int> parent;
	int size;
	UnionFind(int n) :parent(n, -1), size(n) {}
	bool unite(int x, int y) {
		x = root(x); y = root(y);
		if (x == y)return false;
		if (set_size(x) < set_size(y))swap(x, y);
		parent[x] += parent[y]; parent[y] = x; size--;
		return true;
	}
	bool same(int x, int y) { return root(x) == root(y); }
	int root(int x) { return parent[x] < 0 ? x : parent[x] = root(parent[x]); }
	int set_size(int x) { return -parent[root(x)]; }
};

signed main() {
	int n, q; cin >> n >> q;
	UnionFind UF(n);
	rep(i, 0, q) {
		int com, x, y; cin >> com >> x >> y;
		if (com == 0)UF.unite(x, y);
		else cout << (UF.same(x, y) ? 1 : 0) << endl;
	}
	return 0;
}

Measured memory_bytes: 3136
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

c = 0

for i in range(len(b)):
  if b[i] > a[i]:
    c += a[i]
    b[i] = b[i] - a[i]
    a[i] = 0
  else:
    c += b[i]
    a[i] = a[i] - b[i]
    b[i] = 0
  
  if a[i] == 0:
    if b[i] > a[i+1]:
      c += a[i+1]
      b[i] = b[i] - a[i+1]
      a[i+1] = 0
    else:
      c += b[i]
      a[i+1] = a[i+1] - b[i]
      b[i] = 0
  

print(c)


Measured memory_bytes: 82148
#include <bits/stdc++.h>
using namespace std;
int N,K;
int pow(int a,int b){
  int ans=1;
  if(b==0){
    return 1;
  }
  else{
    for(int i=0;i<b;i++){
      ans = a*ans;
    }
    return ans;
  }
}

int main(){
  cin >> N >> K;
  cout << K*pow(K-1,N-1) << endl;
  return 0;
}


Measured memory_bytes: 256
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();
        int area = a * b;
        int length = 2*(a+b);
        System.out.println(area + " " + length);
    }
}


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

// using INF = INT_MAX / 2;

#define DEBUG
#ifdef DEBUG
#define dump(x) cout << "[*] " #x ": " << x << endl
#define debug(x) x
#else
#define dump(x)
#define debug(x)
#endif

constexpr int MAX = 100000;
// dp[day][act] := day 日目に act の行動をとった時の幸福度
int dp[MAX][3];

int main() {
    int N;
    cin >> N;
    vector<int> a(N+1);
    vector<int> b(N+1);
    vector<int> c(N+1);
    a[0] = b[0] = c[0] = 0;
    for (int i = 1; i <= N; ++i) {
        cin >> a[i] >> b[i] >> c[i];
    }

    for (int d = 1; d <= N; ++d) {
        dp[d][0] = max(dp[d-1][1] + a[d], dp[d-1][2] + a[d]);
        dp[d][1] = max(dp[d-1][0] + b[d], dp[d-1][2] + b[d]);
        dp[d][2] = max(dp[d-1][1] + c[d], dp[d-1][0] + c[d]);
    }
    const int ans = max({dp[N][0], dp[N][1], dp[N][2]});
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 2560
s=input()
list_ = ["A","C","G","T"]
mn = 0
for i in range(len(s)):
    count = 0
    while True:
        if i >= len(s):
            break
        else:
            if not s[i] in list_ :
                break
            else :
                count += 1
                i += 1
    if mn < count:
        mn = count
print(mn)

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

int main(){
  int n;
  cin >>n;
  vector<ll> a(n);
  rep(i,n) cin >>a[i];
  sort(a.begin(), a.end());
  ll ans = 1;
  rep(i,n){
    if(a[i]==0){
      cout << 0 << endl;
      return 0;
    }
    if(a[i]<=1000000000000000000/ans){
      ans *= a[i];
    }
    else {
      cout << -1 << endl;
      return 0;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4052
#include<bits/stdc++.h>
using namespace std;;
int main(){
  int v=0;
  string A;
  cin >> A;
  int j=A.size();
  for(int i=0;i<j-1;i++){
    if(A[i]==A[i+1]){
      cout << "Bad" << endl;
      v=1;
      break;
    }
  }
  if(v!=1)cout << "Good" << endl;
}


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

#define rep(i, n) REP(i, 0, n)
#define REP(i, k, n) for(auto i = k; i != n; i++)
#define rrep(i, n) RREP(i, n, 0)
#define RREP(i, n, k) for(auto i = n; i != k; i--)
#define all(x, r) (x), (x)+(r)
#define ALL(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " " << x << endl
#define exst(x, data) (data).find(x) != (data).end()
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define np next_permutation
#define b32 bitset<32>

using ll = long long;
using Pii = pair<int,int>;
using Tiii = tuple<int, int, int>;
template<class T>using V = vector<T>;

int N, Q;
V<ll> a, x;
ll ans;

void shakutori(ll k) {
    ans = 0;
    int right = 1;
    for(int left=1; left<N+1; left++) {
        while(right < N+1 && a[right]-a[left-1] <= k) {
            right++;
        }

        ans += right - left;
        // cout << right - left << " ";

        if(left == right) right++;
    }
    // cout << endl;
}

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

    cin >> N >> Q;
    a = V<ll>(N+1,0); REP(i,1,N+1) cin >> a[i]; REP(i,2,N+1) a[i] += a[i-1];
    x = V<ll>(Q+1); REP(i,1,Q+1) cin >> x[i];

    REP(i,1,Q+1) {
        shakutori(x[i]);
        cout << ans << endl;
    }

    // rep(i,N+1) cout << a[i] << " "; cout << endl;
    // rep(i,Q+1) cout << x[i] << " "; cout << endl;
    return 0;
}



Measured memory_bytes: 3600
// #include <algorithm>
#include <stdio.h>
#include <vector>
#include <math.h>
#include <stdlib.h>
using namespace std;

enum State{
  FREE, NOT_FREE,
};

#define NOTHING -1

vector<int> row;  // The x-y position (j=col,i=row) of a queen: row[i] = j
vector<State> col;  // threatened by other queen
vector<State> dpos; // threatened by other queen
vector<State> dneg; // threatened by other queen
vector<int> iniRow;

void place(int i, int j){
  row[i] = j;
  col[j] = dpos[i+j] = dneg[i-j+8-1] = NOT_FREE;
}
void placeInit(int i, int j){
  iniRow[i] = j;
  col[j] = dpos[i+j] = dneg[i-j+8-1] = NOT_FREE;
}

void printBoard(){
  for(int y = 0 ; y < 8 ; y++ ){
    for(int x = 0; x < 8 ; x++){
      if(row[y]==x){
        printf("Q");
      }else{
        printf(".");
      }
    }  
    printf("\n");
  }
}
void putQueen(int i){
  if( i == 8 ){
    printBoard();
    exit(0); 
  }

  if(iniRow[i] == NOTHING){
    for(int j = 0 ; j < 8 ; j++){
     if( col[j] == NOT_FREE || dpos[i+j] == NOT_FREE
         || dneg[i-j+8-1] == NOT_FREE){
        continue;
      }
      place(i, j);
      putQueen(i+1);
      col[j] = dpos[i+j] = dneg[i-j+8-1] = FREE;
    }
  }else{
      place(i, iniRow[i]);
      putQueen(i+1);
  }
  return;
}

int main(){
  // initilize
  row.resize(8, NOTHING);
  col.resize(8, FREE);
  dpos.resize(15, FREE);
  dneg.resize(15, FREE);
  iniRow.resize(8, NOTHING);

  int kline;
  scanf("%d" ,&kline);
  for(int cnt = 0 ; cnt < kline ; cnt++){
    int rp, cp; // row place, column plcae
    scanf("%d %d" ,&rp ,&cp );
    placeInit(rp, cp);
  }
  putQueen(0);

  return 0;
}



Measured memory_bytes: 2708
#include <bits/stdc++.h>
#define int long long
#define ALL(v) (v).begin(),(v).end()
#define Vi vector<int>
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repeq(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define repreq(i,a,b) for(int i=a;i>=b;i--)
#define leng(n) (int)(log10(n)+1)
#define INF 9000000000000000000
#define MOD 1000000007
#define PAI 3.14159265358979
// ver1.6
using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}  //  最大公約数gcd
int lcm(int a,int b){return a/gcd(a,b)*b;}  //  最小公倍数lcm

signed main() {
  cout << fixed << setprecision(14);
  int n,m;
  cin >> n >> m;
  int memo1,memo2;
  map<int,int> ans;
  rep(i,0,m){
    cin >> memo1 >> memo2;
    if(memo1==1) ans[memo2]++;
    if(memo2==n) ans[memo1]++;
  }
  
  for (auto p : ans) {
    auto k = p.first;
    auto v = p.second;
    if(v==2) {
      cout << "POSSIBLE" << endl;
      return 0;
    }
  }

  cout << "IMPOSSIBLE" << endl;
  return 0;
}


Measured memory_bytes: 12800
#include <stdio.h>

int main()
{
    int n,k;
    scanf("%d %d", &n, &k);
    int a[n];
    for(int i = 0; i < n; i++){
        scanf("%d", a+i);
    }
    printf("%d\n", (n-1)/(k-1)+((n-1)%(k-1)!=0));
    return 0;
}


Measured memory_bytes: 512
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <iomanip>
#include <string.h>
#include <set>
#include <algorithm>
#include <cmath>
#include <map>
#include <string>
using namespace std;

typedef double LD;
typedef long long LL;
typedef pair<int, int> PII;
#define MP make_pair
#define PB push_back
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); --i)
#define REP(i, t) FOR(i,0,t)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())

const LL MOD = 1000000007;
const int INF = 1000000007;
const LL LINF = 1LL * INF * INF;
const int MAXN = 17;
const LD EPS = 1e-7;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//freopen("In.txt", "r", stdin);
	int n, d, x;
	LD s = 0;
	cin >> n >> d >> x;
	REP(i, n)
		s += (i + 1.0) / (n - i);
	cout << fixed << setprecision(10) << s * (d + (n - 0.5) * x);
	//cout << endl; system("pause");
	return 0;
 }
/*
1
5
26
154
1044 / 36 = 29
8028 / 36 = 223
69264 / 144 = 481
663696 / 144 = 4609
*/

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int mod=1e9+7;
const int INF=1001001001;

int main() {
  int N;
  cin>>N;
  vector<int>C(N-1),S(N-1),F(N-1);
  for(int i=0;i<N-1;i++){
    cin>>C[i]>>S[i]>>F[i];
  }
  for(int i=0;i<N;i++){
    int time=0;
    for(int j=i;j<N-1;j++){
      if(time>=S[j]){
        time=(time+F[j]-1)/F[j]*F[j];
        time+=C[j];
      }
      else{
        time=S[j];
        time+=C[j];
      }
    }
    cout<<time<<endl;
  }
  return 0;  
}

Measured memory_bytes: 3636
import bisect
from collections import deque
import sys
MAX_INT = int(10e9)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,K = IL()
a = IL()

cnt = 0
for left in range(N):
  for right in range(left+1,N):
    if a[left] > a[right]:
      cnt += 1
cnt = (cnt*K) %mod

a.sort()
tmp = 0
for i in range(N-1):
  if a[i+1] > a[i]:
    tmp = i+1
  cnt += ((tmp*K*(K-1))//2) %mod

print(int(cnt) %mod)

"""
2 1000000006
2 1

10 3
10 9 8 7 6 5 4 3 2 1
"""

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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

const int64 mod = 1e9+7;

class Union_find{
private:
	vector<int32> par;
	int32 n;

public:
	Union_find(int32 n):n(n){
		par.resize(n, -1);
	}

	int32 find(int32 x){
		return par[x] < 0 ? x : par[x] = find(par[x]);
	}

	int32 size(int32 x){
		return -par[find(x)];
	}

	void unite(int32 x, int32 y){
		x = find(x);
		y = find(y);
		if(x == y) return;
		if(size(x) < size(y)) swap(x, y);
		par[x] += par[y];
		par[y] = x;
	}

	bool same(int32 x, int32 y){
		return find(x) == find(y);
	}
};
vector<int64> fact(1010, 0), inv(1010, 0); 

int64 mpow(int64 a, int64 b){
	if(b == 0) return 1;
	if(b%2) return a*(mpow(a, b-1))%mod;
	int64 ret = mpow(a, b/2);
	return ret*ret%mod;
}

int64 comb(int64 a, int64 b){
	return fact[a]*inv[a-b]%mod*inv[b]%mod;
}

void init(){
	fact[0] = inv[0] = 1;
	REP(i, 1009){
		fact[i+1] = (fact[i]*(i+1))%mod;
		inv[i+1] = mpow(fact[i+1], mod-2);
	}
}

int main(void){

	init();
	int32 N, M;
	int64 X;

	cin >> N >> M >> X;
	int64 pat = 0;
	FOR(i, 1, N-1){
		pat += comb(N-1, i);
		pat %= mod;
	}
	using taplis = tuple<int64, int64, int64>;
	vector<taplis> edge;
	REP(i, M){
		int64 u, v, w;
		cin >> u >> v >> w; u--; v--;
		if(u > v) swap(u, v);
		edge.push_back(taplis(w, u, v));
	}
	sort(all(edge));
	vector<int64> wei;
	REP(i, M){
		Union_find uf(N);
		int64 w, u, v;
		tie(w, u, v) = edge[i];
		int64 sum = w;
		uf.unite(u, v);
		REP(j, M){
			tie(w, u, v) = edge[j];
			if (!uf.same(u, v)) {
				uf.unite(u, v);
				sum += w;
			}
		}
		wei.push_back(sum);
	}
	int32 cnt = 0;
	int32 c2 = 0;
	REP(i, wei.size()){
		if(wei[i] < X){
			cnt++;
		}
		if(wei[i] == X){
			c2++;
		}
	}
	if(c2 == 0){
		cout << 0 << endl;
	}else if(cnt == 0){
		cout << mpow(2, M-c2)*((mpow(2, c2)-2+mod)%mod)%mod << endl;
	}else{
		cout << ((mpow(2, c2+1)-2+mod)%mod*mpow(2, M-c2-cnt))%mod << endl;
	}
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <string>
#define FIN freopen("inputs.txt", "r", stdin)
using namespace std;
typedef pair<int, int> P;
int a, b;
int main(){
//FIN;
    cin>>a>>b;
    // force a > b
    if(a < b) swap(a, b);
    for (int i = 0; i < a; i++)
    {
        cout<<b;
    }
    cout<<'\n';
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

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

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))


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

    string s, t;
    cin >> s >> t;

    int ans = t.size();
    rep (i, s.size() - t.size() + 1)
    {
        int temp = 0;
        rep (j, t.size())
        {
            if (s[i + j] != t[j]) ++temp;
        }
        ans = min(ans, temp);
    }

    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define MAXN 200005
#define ll long long

using namespace std;

int n;
ll h[MAXN], a[MAXN], arvore[MAXN];





ll soma(ll x)
{
	ll sum = 0;
	for (ll i = x; i > 0; i -= (i & -i))
	{
		sum = max(arvore[i], sum);
	}

	return sum;
}


void update(ll x, ll sum)
{
	for (ll i = x; i < MAXN; i += (i & -i))
	{
		arvore[i] = max(arvore[i], sum);
	}	


}



int main()
{
	
	cin >> n;

	memset(arvore, 0, sizeof(arvore));

	for (int i = 1; i <= n; ++i)
		cin >> h[i];
	for (int i = 1; i <= n; ++i)
		cin >> a[i];

	for (int i = 1; i <= n; ++i)
	{
		ll x = soma(h[i]);
		update(h[i], a[i] + x);
	}


	cout << soma(n) << endl;















	return 0;
}

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

using namespace std;

long long int mod = 1000000007;

long long int modpow(long long int a, long long int n) {
	long long int res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

int main(){

	long long int n, k, tmp, tmp2, ans = 0;
	vector<long long int> v;

	cin>> n >> k;
	v.resize(k+1);

	for (int i = k;i > 0;i--) {
		tmp = k / i;
		tmp2 = modpow(tmp, n);
		for (int j = 2;j <= tmp;j++) {
			tmp2 += mod;
			tmp2 -= v[j*i];
			tmp2 = tmp2 % mod;
		}
		v[i] = tmp2;
		ans += (i*tmp2)%mod;
		ans = ans % mod;
		//cout << i << " " << v[i] << endl;
	}

	cout<< ans << endl;

	return 0;
}


Measured memory_bytes: 4052
import java.util.Scanner

import scala.annotation.tailrec

object Main extends App {
  val sc = new Scanner(System.in)

  val n = sc.nextInt
  val hl = Seq.fill(n)(sc.nextInt)


  val res = cntLoop(hl)
  println(res)

  @tailrec
  def cntLoop(list: Seq[Int] , cnt: Int = 0): Int = {
    if (list.forall(_ == 0) ) cnt
    else cntLoop(elementMinusOne(list), cnt + separate(list).size)
  }

  @tailrec
  def separate(list: Seq[Int], lists: Seq[Seq[Int]] = Seq.empty): Seq[Seq[Int]] = {
    list match {
      case Nil => lists
      case nonEmpty => {
        val target = nonEmpty.dropWhile(_ == 0)
        val (take, drop) = target.span(_ > 0)
        val next = drop.dropWhile(_ == 0)
        separate(next, lists :+ take)
      }
    }
  }

  def elementMinusOne(list: Seq[Int]): Seq[Int] = {
    list.map{
      case 0 => 0
      case e => e - 1
    }
  }
}

Measured memory_bytes: 30648
open System

let N : int = stdin.ReadLine() |> int

let d : int list = List.init N (fun _ -> stdin.ReadLine() |> int) |> List.sort

let ans,_ = List.fold (fun (cnt,p) v -> if p <> v then (cnt+1,v) else (cnt,v)) (0,0) d

printfn "%d" ans


Measured memory_bytes: 14940
#include <bits/stdc++.h>
using namespace std;
template <typename T> bool chmax(T &u, const T z) { if (u < z) {u = z; return true;} else return false; }
template <typename T> bool chmin(T &u, const T z) { if (u > z) {u = z; return true;} else return false; }
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
//解説写し
const int INF = 1001001001;
// Segment tree
struct F { // min func
  typedef int TT;
  TT d;
  F(TT d=INF):d(d) {}
  F& operator+=(const F& f) {
    chmin(d, f.d);
    return *this;
  }
  F operator+(const F& f) const { return F(*this) += f;}
};
struct seg {
  vector<F> d; int n;
  seg(){}
  seg(int mx) {
    n = 1; while (n < mx) n <<= 1;
    d = vector<F>(n<<1);
  }
  void upd(int i) { d[i] = d[i<<1]+d[i<<1|1];}
  F& operator[](int i) { return d[n+i];}
  void init() { for(int i=n-1;i;--i) upd(i);}
  void add(int i, F f) { for (i+=n,d[i]+=f,i>>=1;i;i>>=1) upd(i);}
  void set(int i, F f) { for (i+=n,d[i]=f,i>>=1;i;i>>=1) upd(i);}
  F get(int l, int r) {
    l += n; r += n;
    F lf, rf;
    while (l < r) {
      if (l&1) lf += d[l++];
      if (r&1) rf = d[--r] + rf;
      l >>= 1; r >>= 1;
    }
    return lf += rf;
  }
};
//
int main() {
  int h,w;
  scanf("%d%d",&h,&w);
  map<int,int> s;
  rep(i,w) s[i] = i;
  seg t(w+5);
  rep(i,w) t.set(i,F(0));
  rep(i,h) {
    int l,r;
    scanf("%d%d",&l,&r);
    --l;
    auto it = s.lower_bound(l);
    int x = -INF;
    while (it != s.end() && it->first < r) {
      chmax(x,it->second);
      t.set(it->first,F(INF));
      s.erase(it++);
    }
    if (r < w && x != -INF) {
      if (!s.count(r)) s[r] = -INF;
      chmax(s[r],x);
      t.set(r,F(r-s[r]));
    }
    int ans = t.get(0,w).d+i+1;
    if (ans >= INF) ans = -1;
    printf("%d\n",ans);
  }
  return 0;
}

Measured memory_bytes: 14552