akhauriyash/Code-Regression huggingface dataset:
package main

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

func main() {
	l := ReadInt() + ReadInt()
	r := ReadInt() + ReadInt()
	if l > r {
		fmt.Println("Left")
	} else if l < r {
		fmt.Println("Right")
	} else {
		fmt.Println("Balanced")
	}
}

var sc = bufio.NewScanner(os.Stdin)

func init()        { sc.Buffer(make([]byte, 256), 1e9); sc.Split(bufio.ScanWords) }
func Read() string { sc.Scan(); return sc.Text() }

func ReadInt() int {
	v, e := strconv.Atoi(Read())
	if e != nil {
		panic(e.Error())
	}
	return v
}


Measured memory_bytes: 1772
#include<bits/stdc++.h>
#include<string.h>
 
typedef long long int ll;
#define all(x) (x).begin(), (x).end()
 
using namespace std;

int nxt() {
    int x;
    cin >> x;
    return x;
}

ll nxtl(){
    ll x;
    cin>>x;
    return x;
}
 
void SieveOfEratosthenes(int n,vector <int> &primes) 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          primes.push_back(p);
} 
 
ll max(ll a,ll b)
{
    if(a>b)
        return a;
    return b;
}
 
ll power(ll x, ll y,ll mod) 
{ 
    ll temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2,mod); 
    if (y%2 == 0) 
        return (temp*temp)%mod; 
    else
        return (((x*temp)%mod)*temp)%mod; 
} 

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n=nxt(),m=nxt();
    cout<<(n*(n-1))/2+(m*(m-1))/2<<endl;

    return 0;   
}


 
 


Measured memory_bytes: 256
#include<stdio.h>
//小さい順にソート
int c[100002];
void merge(int i,int j,int *s){
  if(i!=j){
    merge(i,(i+j)/2,s);
    merge((i+j)/2+1,j,s);
    int a=i,b=(i+j)/2+1;
    int d;
    for(d=i;d<=j;d++){
      if((i+j)/2<a){
        c[d]=s[b];
        b++;
      }
      else if(j<b){
        c[d]=s[a];
        a++;
      }
      else if(s[a]<s[b]){
        c[d]=s[a];
        a++;
      }
      else{
        c[d]=s[b];
        b++;
      }
    }
    for(d=i;d<=j;d++)
      s[d]=c[d];
  }
}

int main(){
  int n,i;
  scanf("%d",&n);
  int a[n+1];
  for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
  merge(1,n,a);
  int b,c=1000000000;
  for(i=1;i<n;i++){
    if(a[i]<a[n]/2)
      b=a[i];
    else{
      c=a[i];
      break;
    }
  }
  if(a[n]/2-b<c-a[n]/2)
    printf("%d %d\n",a[n],b);
  else
    printf("%d %d\n",a[n],c);
  return 0;
}


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

int main() {
  int N, S;
  S = 0;
  cin >> N;
  for (int i = 0; i < N; i++) {
    int l, r;
    cin >> l >> r;
    S += (r - l + 1);
  }
  cout << S << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std ;
typedef  long long int ll ;
#define inf 9e18
#define mod 1000000007
#define mod1 998244353
#define mod2 999983
long long int power(long long int a,long long int n,long long int m) ;
long long int power(long long int a,long long int n,long long int m)
{  if(n==0)
   return 1 ;
   long long int x=power(a,n/2,m) ;
   if(n%2!=0)
    return (((a*x)%m)*(x)%m)%m ;
    else return (x*x)%m ;
}
//map<ll,ll>::iterator it ;

int main()
{ int n,i,j,x,y,m,k,t,sum,count,cnt,b,c,d,j1,z,a,o,temp;
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  string s1,s2 ;
  cin>>s1>>s2 ;
  if(s1==s2.substr(0,s1.size()))
    cout<<"Yes" ;
  else cout<<"No" ;
return 0; }


Measured memory_bytes: 3616
import sys
input = sys.stdin.readline
from collections import deque

def bfs():
    dist = [-1]*(3*N)
    dist[serial[S][0]] = 0
    q = deque([serial[S][0]])
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                q.append(nv)
    
    return dist[serial[T][0]]

N, M = map(int, input().split())
serial = [[-1]*3 for _ in range(N)]
c = 0

for i in range(N):
    for j in range(3):
        serial[i][j] = c
        c += 1

G = [[] for _ in range(3*N)]

for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    G[serial[u][0]].append(serial[v][1])
    G[serial[u][1]].append(serial[v][2])
    G[serial[u][2]].append(serial[v][0])

S, T = map(int, input().split())
S -= 1
T -= 1
ans = bfs()

if ans==-1:
    print(-1)
else:
    print(ans//3)


Measured memory_bytes: 88976
#include<bits/stdc++.h>
#define LiangJiaJun main
#define ll long long
using namespace std;
ll n,m,d;
double g,p;
int LiangJiaJun(){
    scanf("%lld%lld%lld",&n,&m,&d);
    g=1.0*(n-d)*(m-1);
    if(d!=0)g*=2.0;
    p=(1.0*n*n);
    printf("%.6lf\n",g/p);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int llint;
typedef long int lint;
typedef vector<int> vint;
typedef vector<vector<int>> vvint;
int main(){
  lint n,i;
  llint fjk;//中央値から2分探索
  llint sum,sumnext;
  cin>>n;
  vint a(n);
  for(i=0;i<n;i++){
    cin>>a[i];a[i]-=i;a[i]--;//a[i]=a[i]-b に変換
  }
  sort(a.begin(),a.end());int fl=0;//0:(b>b+1) 1:(b<b+1) fl!=flでbreak;
  fjk=a[n/2];sum=-1;sumnext=-1;
  while(1){
    if(sum=-1){sum=0;for(i=0;i<n;i++){sum+=abs(a[i]-fjk);}}
    if(sumnext=-1){sumnext=0;for(i=0;i<n;i++){sumnext+=abs(a[i]-fjk-1);}}
    
    if(sum>sumnext){if(fl){cout<<sumnext<<endl;break;}sum=sumnext;sumnext=-1;fl=0;fjk++;}
    else if(sum<sumnext){if(!fl){cout<<sum<<endl;break;}sumnext=sum;sum=-1;fl=1;fjk--;}
    else if(sum=sumnext){
      if(fl){sumnext=sum;sum=-1;fjk--;}
      else{sum=sumnext;sumnext=-1;fjk++;}
    }
  }
  
}

Measured memory_bytes: 1024
n=gets.to_i
a=gets.split.map(&:to_i).sort
while !a.empty?
  c = a.shift
  c2 = a.shift
  if !c2.nil?
    tmp = (c.to_f + c2.to_f)/2
    a<<tmp
    a.sort!
  else
    puts c
  end
end

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

using ll = long long;
using ull = unsigned long long;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
void Yes(bool f){cout<<(f?"Yes":"No")<<endl;}

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

    int N, K, Q; cin >> N >> K >> Q;

    vector<int> count(N + 1, 0);
    int A;
    rep(i, Q) {
        cin >> A;
        count[A]++;
    }
    rep1(i, N + 1) {
         Yes(Q - count[i] < K);
    }
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for(long long int i = 0; i < n; i++)
#define print(n) std::cout << n << std::endl
#define _print(n) std::cout << n
using namespace std;
typedef long long ll;
const int N = 1000000;

int main() {
    ll n,x; cin >> n >> x;
    ll a[n + 100];

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

    ll num = 0;
    sort(a, a + n);

    while(x > 0 && num < n){
        x -= a[num];
        if(x > 0){
            num++;
        }else if(x == 0){
            num++;
            break;
        }else{
            break;
        }
    }
    if(x > 0)print(num - 1);
    else print(num);
    
}

Measured memory_bytes: 256
import Control.Applicative
import Control.Monad
import Data.List

p = 10 ^ 9 + 7

f :: Int -> [Int]
f n = unfoldr g n
  where
    g 1 = Nothing
    g k = let (_, r:_) = break ((== 0) . (k `mod`)) [2 .. n]
          in Just (r, k `div` r)

main :: IO ()
main = do
    n <- readLn :: IO Int
    let as = concatMap f [1 .. n]
    let bs = fmap ((+ 1) . length) . group $ sort as
    let ans = foldr (\x a -> (x * a) `mod` p) 1 bs
    print ans

Measured memory_bytes: 1916
from collections import Counter

n,k = map(int, input().split())
A = Counter(map(int, input().split()))

rep_n = len(A)-k

if rep_n<=0:
  print(0)
else:
  ans = 0
  for k, v in A.most_common()[::-1]:
    ans += v
    rep_n -= 1
    if rep_n==0:
      break
  print(ans)

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

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define BUFF ios::sync_with_stdio(false);

typedef long long int ll;
typedef long double ld;
typedef vector < int > vi;
typedef vector < vi > vvi;
typedef pair < int, int > ii;
typedef vector < ii > vii;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1e9+7;
const ld pi = acos(-1);

int v[10];
int main() { BUFF
  memset(v, 0, sizeof(v));
  int x; 
  cin >> x;
  v[x]++;
  cin >> x;
  v[x]++;
  cin >> x;
  v[x]++;
  if(v[5] == 2 and v[7] == 1)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;

  return 0;
}


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

typedef long long ll;

int N, M;
vector<int> S;
map<int, int> R;

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

	S.resize(N + 1);
	S[0] = 0;
	for (int i = 1; i <= N; ++i) {
		int a;
		cin >> a;
		S[i] = (a + S[i - 1]) % M;
	}

	for (int i = 1; i <= N; ++i)
		++R[S[i]];
	
	ll ans = (ll)0;
	map<int, int>::iterator itr;
	for (itr = R.begin(); itr != R.end(); ++itr) {
		int n = itr->second;
		ans += (ll)n * (n - 1) / 2;
		if (itr->first == 0)
			ans += (ll)n;
	}

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


Measured memory_bytes: 3584
s=io.read()
len=s:len()

for i=1,len do
  if i%2==0 then
    l=s:sub(i, i)
    if not (l=="L" or l=="U" or l=="D") then
      print("No")
      os.exit()
    end
  else
    r=s:sub(i, i)
    if not (r=="R" or r=="U" or r=="D") then
      print("No")
      os.exit()
    end
  end
end

print("Yes")

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

using namespace std;

int a,b,k;
std::vector <int> v;
std::vector <int> book;

int main(){

	cin>>a>>b>>k;

	int sum=0;
	for (int i=a;i<=b;i++){
		if (sum==k) break;
		cout<<i<<endl;
		book.push_back(i);
		sum++;
	}

	sum=0;
	for (int i=b;i>=a;i--){
		if (sum==k) break;
		v.push_back(i);
		sum++;
	}

	bool check=false;
	for (int i=v.size()-1;i>=0;i--){
		check=false;
		for (int j=book.size()-1;j>=0;j--){
			if (book[j]==v[i]) {check=true;break;}
		}
		if (!check) cout<<v[i]<<endl;
	}

	return 0;

}

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

int main(){
	ll x, k, d;
  	cin >> x >> k >> d;
  
  	x = abs(x); 
  	ll ans = 0;
  	if(x/d >= k) ans = x - k * d;
	else {
    	ll a = x/d;
      	k -= a;
      	x -= a * d;
      	if(k % 2 == 1) x = abs(x-d);
      	ans = x;
    }
  
  	cout << ans << endl;
}

Measured memory_bytes: 3596
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int s1, s2, s3;
	int re = 0, rh = 0;

	while (scanf("%d,%d,%d", &s1, &s2, &s3) != EOF)
	{
		if (s1*s1 + s2*s2 == s3*s3) re++;
		if (s1 == s2) rh++;
	}

	cout << re << "\n" << rh << endl;

	return 0;
}

Measured memory_bytes: 1216
#include <bits/stdc++.h>
using namespace std;
#define ll          long long int
#define pb          push_back
#define pll         pair<ll,ll>
#define pq          priority_queue
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mod         1000000007
#define inf         INT_MAX-100
#define vl          vector<ll>
#define vvl         vector<vector<ll>>
#define F           first
#define S           second
#define db          double
#define sz(x)       (ll)x.size()
#define fix(n)      cout<<fixed<<setprecision(n)
#define rep(i,a,b)  for(ll i=a;i<b;i++)
//const int N;

void solve()
{
    ll n; cin>>n;
    ll a[n],b[n],c[n];
    rep(i,0,n) cin>>a[i]>>b[i]>>c[i];
    ll d1[n],d2[n],d3[n];
    d1[0]=a[0],d2[0]=b[0],d3[0]=c[0];
    rep(i,1,n)
    {
        d1[i]=a[i]+max(d2[i-1],d3[i-1]);
        d2[i]=b[i]+max(d1[i-1],d3[i-1]);
        d3[i]=c[i]+max(d1[i-1],d2[i-1]);
    }
    cout<<max(d1[n-1],max(d2[n-1],d3[n-1]));
}
int main()
{
    ll T=1;
    //cin>>T;
    while(T--)
        solve();
}


Measured memory_bytes: 4992
#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 emplace_back
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< pii >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define in(x, a, b) ((a) <= (x) && (x) < (b))
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

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

    int2(n, k);
    string st;
    cin >> st;
    
    rep(i, n) {
        if (i == k-1) {
            cout << (char)(st[i] + ('a' - 'A'));
        } else {
            std::cout << st[i];
        }
    }

    cout << endl;

    return 0;
}


Measured memory_bytes: 256
import java.net.StandardSocketOptions;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeSet;

import org.omg.Messaging.SyncScopeHelper;
import org.omg.PortableInterceptor.SYSTEM_EXCEPTION;

public class Main {
	Scanner sc = new Scanner(System.in);
	public static void main(String[] args){
		new Main();
	}
	public Main(){
		new Test_200().doIt();
	}
	class Test_200{
		void doIt() {
			int Wa[] = new int[100001];
			Pa_10(Wa);
			int ans = Integer.MAX_VALUE;
			int N = sc.nextInt();
			for(int i = 1;i <= N/2;i++) {
				ans = Math.min(ans, Wa[N - i] + Wa[i]);
			}
			System.out.println(ans);
		}
		void Pa_10(int Wa[]){
			for(int i = 0;i <= 100000;i++) {
				Wa[i] = i % 10;
				Wa[i] = Wa[i] + ((i / 10) % 10);
				Wa[i] = Wa[i] + ((i / 100) % 10);
				Wa[i] = Wa[i] + ((i / 1000) % 10);
				Wa[i] = Wa[i] + ((i / 10000) % 10);
				Wa[i] = Wa[i] + ((i / 100000) % 10);
			}
		}
	}
}


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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

#define en "\n"

const double EPS = 1e-9;
const double PI  = acos(-1.0);
const int INF = 2147483647;
const long long LINF = 1LL<<60;
const long long MOD = 1000000007; // 998244353

#define CLR(a) memset((a), 0, sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

vector<long long> make_divisors(long long n){
    vector<long long> divisors;
    for(long long i=1; i*i<=n; i++){
        if(n%i == 0){
            divisors.push_back(i);
            if(i*i != n) divisors.push_back(n/i);
        }
    }
    // sort(divisors.begin(), divisors.end());
    return divisors;
}

int main(void){
    int N,K; cin >> N >> K;
    VI A(N); REP(i,N) cin >> A[i];
    int S = 0; REP(i,N) S += A[i];
    auto v = make_divisors(S);
    SORT(v); REVERSE(v);
    int ans = 0;
    for(int q : v){
        VI B(A);
        REP(i,N) B[i] %= q;
        SORT(B);
        VI S1(N-1,0), S2(N-1,0);
        S1[0] = B[0]; REP(i,N-2) S1[i+1] = S1[i] + B[i+1];
        S2[N-2] = q-B[N-1]; REP(i,N-2) S2[N-3-i] = S2[N-2-i] + q - B[N-2-i];
        bool flag = false;
        REP(i,N-1){
            if(S1[i] <= K && S2[i] <= K && S1[i]%q==S2[i]%q) chmax(ans, q);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int a,b;

    cin>>a>>b;

    if (a+b >= a-b && a+b>a*b)
        cout<<a+b;
    else if (a-b>=a+b && a-b>a*b)
        cout<<a-b;
    else
        cout<<a*b;




}


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

int main(void) {
  int a, b;
  string str;
  cin >> a >> b;
  bool flag = true;
  cin >> str;
  for (int i = 0; i < str.length(); i++) {
    if (i != a) {
      if ((int)(str[i] - '0') < 10 && (int)(str[i] - '0' >= 0)) {
        flag = true;
      } else {
        flag = false;
        break;
      }
      if (str[i] == '-') {
        flag = false;
        break;
      }
    }
  }
  if (str[a] == '-') {

  } else {
    flag = false;
  }
  if (str.length() != a + b + 1) {
    flag = false;
  }
  if (flag) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}



Measured memory_bytes: 256
/**
 * @author: shashankchdhry
 * @made:   2020-03-31 14:16:57 
**/
#include <bits/stdc++.h>

using namespace std;

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

    int n, k;
    cin >> n >> k;

    int ans = k * pow(k-1, n-1);

    cout << ans << "\n";

    return 0;
}

Measured memory_bytes: 256
#pragma comment (linker, "/STACK:256000000")
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define BUGAVOID(x) x
#define rep(...) BUGAVOID(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define sz(c) (int)(c.size())
#define all(c) c.begin(),c.end()
#define mp make_pair
#define write(x) cout<<(x)<<"\n"
using namespace std; typedef long long ll;
typedef vector<int> vi; typedef vector<ll> vll; template<class T, class U>using vp = vector<pair<T, U>>;
template<class T>using vv = vector<vector<T>>; template<class T, class U>using vvp = vv<pair<T, U>>;
template<class T>vv<T> vvec(const size_t n, const size_t m, const T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; }return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; }return 0; }
constexpr ll pow2(const int n) { return 1ll << n; }
constexpr int INF = 1 << 28; constexpr ll LINF = 1ll << 60;
constexpr int MAX = 1e5 + 5; constexpr int MOD = 1e9 + 7; constexpr double EPS = 1e-6;
constexpr int dy[4] = { 0,1,0,-1 }; constexpr int dx[4] = { 1,0,-1,0 };
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); }; }aaaa;

int get_pattern(int w) {
    if (w < 2) return 1;
    else if (w == 2) return 2;
    else if (w == 3) return 3;
    else {
        int cnt = 1;
        rep(i, w - 1) {
            cnt += get_pattern(w - i - 2);
            cnt %= MOD;
        }
        return cnt;
    }
}

int H, W, K;
vv<int> table;
vv<ll> dp;

int main() {
    cin >> H >> W >> K;
    table = vvec(W, W, 0);
    rep(i, W) {
        rep(j, W) {
            if (abs(i - j) == 1) {
                int itmp = i, jtmp = j;
                if (itmp > jtmp) swap(itmp, jtmp);
                int ret = get_pattern(itmp) * get_pattern(W - jtmp - 1);
                table[i][j] = ret % MOD;
            }
            else if (i == j) {
                int ret = get_pattern(i) * get_pattern(W - j - 1);
                table[i][j] = ret % MOD;
            }
        }
    }

    dp = vvec<ll>(H + 1, W, 0);
    dp[0][0] = 1;

    rep(i, 1, H + 1) {
        rep(j, W) {
            // 左
            if (j > 0) {
                dp[i][j - 1] += dp[i - 1][j] * table[j][j - 1];
                dp[i][j - 1] %= MOD;
            }
            // 直下
            dp[i][j] += dp[i - 1][j] * table[j][j];
            dp[i][j] %= MOD;
            // 右
            if (j < W - 1) {
                dp[i][j + 1] += dp[i - 1][j] * table[j][j + 1];
                dp[i][j + 1] %= MOD;
            }
        }
    }

    write(dp[H][K - 1]);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=1LL<<60;
const double EPS = 1e-10;
const ll mod=1000000007;

ll W[200010]={},B[200010]={};

int main(void){
    ll n;
    string s;
    cin>>n>>s;
    for(int i=0;i<n;i++){
        if(i>0) W[i]=W[i-1];
        if(s[i]=='.') W[i]++;
    }
    for(int i=n-1;i>=0;i--){
        if(i!=n-1) B[i]=B[i+1];
        if(s[i]=='#') B[i]++;
    }
    ll ans=min(n-W[n-1],n-B[0]);
    for(int i=0;i<n-1;i++){
        ans=min(ans,n-W[i]-B[i+1]);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 6860
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        int ans = s.length;
        for (int i = 0; i < s.length - 1; i++) {
            if(s[i] != s[i+1]){
                ans = Math.min(ans, Math.max(i+1, s.length - (i+1)));
            }
        }
        System.out.println(ans);
        sc.close();
    }

}


Measured memory_bytes: 26496
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const int N = 1e5 + 5, mod = 1e9 + 7;
int n, k, ans, dp[N];
ll sub(int a, int b){
    return (((a - b) % mod) + mod) % mod;
}
int add(int a, int b){
    return (a + b) % mod;
}
int mul(int a, int b){
    return (1ll * a * b) % mod;
}
ll fp(ll b, ll p){
    if(!p) return 1;
    ll res = fp(b, p / 2);
    res = mul(res, res);
    if(p & 1) res = mul(res, b);
    return res;
}
int main()
{
    cin >> n >> k;
    for(int i = k; i > 0; i--){
        dp[i] = add(dp[i], fp(k / i, n));
        for(int j = 1; j <= sqrt(i); j++){
            if(i % j == 0){
                if(j != i)
                    dp[j] = sub(dp[j], dp[i]);
                if(i / j != j && i / j != i)
                    dp[i / j] = sub(dp[i / j], dp[i]);
            }
        }
        ans = add(ans, mul(dp[i], i));
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 4020
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <ctime>
#include <map>
#include <queue>

using namespace std; using ll=long long; using P=pair<ll,ll>; const int INF=1e9; const ll LNF=1e18;

int main(){
  ll n,k; cin>>n>>k;
  ll an=0;
  for(ll b=k+1;b<=n;b++) {
    for(ll u=0;u<=n;u+=b) {
      ll pl = min(n, u + b-1) - (u + k - 1);
      pl = max(0LL, pl);
      if (k == 0 && u == 0) pl--;
      //cout<<b<<" "<<u<<"  "<<u+b-1<<" "<<u+k<<" "<<pl<<endl;
      an += pl;
    }
  }
  cout<<an<<endl;
}


Measured memory_bytes: 256
# coding: utf-8
# Your code here!

n = int(input())
cards = {}
for i in range(n):
    card = input()
    cards[card] = 1
    
for c in ['S','H','C','D']:
    for n in range(1,14):
        key = c + ' ' + str(n)
        if not key in cards:
            print(key)


Measured memory_bytes: 5600
#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1000000007;
using ll = long long;

// return a^n % mod
ll mod_pow(ll a, ll n) {
    ll ret = 1;
    ll tmp = a;
    while(n > 0) {
        if(n % 2) {
            ret *= tmp;
            ret %= mod;
        }
        tmp = tmp * tmp;
        tmp %= mod;
        n /= 2;
    }
    return ret;
}

int dp[3000][3000][2];

int main () {
    int n, m;
    cin >> n >> m;
    if(n == 1) {
        cout << mod_pow(2, m + 1) << endl;
        return 0;
    }
    if(m == 1) {
        cout << 4 << endl;
        return 0;
    }
    n--; m--;
    for(int i = 1; i <= m; i++) for(int j = 0; j <= n; j++) for(int k = 0; k <= 1; k++) {
        if(i == 1) { // 初期条件
            if(k == 1) {
                if(j == 0) dp[i][j][k] += 2;
                if(j == 1) dp[i][j][k]++;
            } else {
                if(j != 0) dp[i][j][k] += 2;
                if(j != 0 && j != 1) dp[i][j][k]++;
                if(j != n) dp[i][j][k]++;
            }
        } else { // 遷移
            ll val = 0;
            if(k == 1) {
                if(j == 0) val += 2LL * (dp[i - 1][j][0] + dp[i - 1][j][1]);
                else val += 2LL * dp[i - 1][j][1];
                if(j == 1) val += dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1];
                else if(j != 0) val += dp[i - 1][j - 1][1];
                if(j != n) val += dp[i - 1][j + 1][1];
            } else {
                if(j != 0) val += 2LL * dp[i - 1][j][0];
                if(j != 0 && j != 1) val += dp[i - 1][j - 1][0];
                if(j != n) val += dp[i - 1][j + 1][0];
            }
            dp[i][j][k] = val % mod;
        }
    }
    ll ans = 0;
    for(int i = 0; i <= n; i++) ans += dp[m][i][1];
    ans += dp[m][0][0];
    cout << (4LL * ans) % mod << endl; // 問題の言い換えで答えが 1/4 になっていたので
}


Measured memory_bytes: 70528
import sys
readline = sys.stdin.readline
from operator import itemgetter

def main():
    N = int(readline())
    R = [tuple(map(int, readline().rstrip().split())) for _ in range(N)]
    B = [tuple(map(int, readline().rstrip().split())) for _ in range(N)]

    B.sort(key=itemgetter(0))
    R.sort(key=itemgetter(1), reverse=True)
    ans = 0
    for c, d in B:
        for a, b in R:
            if a < c and b < d:
                ans += 1
                R.remove((a, b))
                break
    
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
n,k,q=map(int,input().split())
a=[int(input()) for _ in range(q)]
l=[k]*n
c=0
for i in range(q):
    l[a[i]-1]+=1
    c+=1
for i in range(n):
    if l[i]-c<=0:print('No')
    else:print('Yes')

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

int dec(int L,int M){
  if(L==-1)return 0;
  return L/M+1;
}

signed main(){
  int A,B,X;
  cin>>A>>B>>X;
  cout<<dec(B,X)-dec((A-1),X)<<endl;
  return 0;
}

Measured memory_bytes: 3608
# -*- coding: utf-8 -*-
i = input()
n = len(i)
ans = 0
for j in range(n + 1):
  if j == n and j % 2 == 1 and j == 1:
    ans += int(i)
  elif j == n and j % 2 == 1:
    ans += int(i) - int(str(9) * (j - 1))
  elif j == 1:
    ans += 9
  elif j % 2 == 1:
    ans += 10 ** j - int(str(9) * (j - 1)) - 1
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP2(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(v) (v).begin(),(v).end()
#define INF 2e9
typedef long long ll;

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

  cout<<6-a-b<<endl;

  return 0;
}

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

using namespace std;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define TRAV(a, x) for(const auto& a : x)
#define ALL(x) x.begin(), x.end()
#define NEXT_PERM(x) while(next_permutation(ALL(x))) // 순열 알고리즘(오름)
#define PREV_PERM(x) while(prev_permutation(ALL(x))) // 순열 알고리즘(내림)
#define PRINT(x) cout << x
#define PRINT_LN(x) cout << x << endl;
#define DUMP(a, n) REP(_i, n) printf("%d%c", a[_i], _i + 1 == n ? '\n' : ' ')
#define DUMP2D(a, n, m) REP(_i, n) REP(_j, m) printf("%d%c", a[_i][_j], _j + 1 == m ? '\n' : ' '); puts("")

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

int gcd(int a, int b);
int lcm(int a, int b);


void solve() {
  int n;
  cin >> n;
  const ll INF = 2e9;

  vi p(n);
  REP(i,n) cin >> p[i];
  int cnt = 0;
  int now_min = INF;
  REP(i,n) {
    if(now_min > p.at(i)) {
      now_min = p.at(i);
      cnt++;
    } 
  }
  cout << cnt;
}

int main() {
  solve();
  return 0;
}

int gcd(int a, int b){
	while(b!=0){
		int r = a%b;
		a= b;
		b= r;
	}
	return a;
}

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


Measured memory_bytes: 1024
#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define  ff first
    #define  ss second
     
    int main(){
        int A,B,X;
        cin>>A>>B>>X;
        if(A+B>=X&&A<=X)
            cout<<"YES";
        else
            cout<<"NO";
        return 0;
    }

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

Measured memory_bytes: 256
import java.util.*;

public class Main{
	private static final Scanner scan = new Scanner(System.in);
	public static void main(String[] args){
		int[] arr = new int[3];
		for(int i = 0; i < 3; i++){
			arr[i] = scan.nextInt();
		}

		for(int i = 0; i < arr.length - 1; i++){
			for(int j = arr.length - 1; j > i; j--){
				if(arr[j] < arr[j - 1]){
					int big = arr[j - 1];
					arr[j - 1] = arr[j];
					arr[j] = big;
				}
			}
		}
		System.out.printf("%d %d %d\n", arr[0], arr[1], arr[2]);
	}
}

Measured memory_bytes: 26220
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 100
void initialize(void);
int Empty(int);
int isFull(int);
void push(int, int*);
int pop(void);
int top=0, S[100];

int main(){
  int x;
  char s[100];

  while( scanf("%s", s) != EOF ){
    if ( s[0] == '+' ){
      S[top-1] += pop();
    } else if ( s[0] == '-' ){
      S[top-1] -= pop();
    } else if ( s[0] == '*' ){
      S[top-1] *= pop();
    } else {
      x = atoi(s);
      push(x,S);
    }
  }
  printf("%d\n", S[top]);

  return 0;
}

void push(int x, int *S){
  top++;
  S[top] = x;
}
  
void initialize(void){
  int top = 0;
}

int isEmpty(int top){
  return top == 0;
}

int isFull(int top){
  return top >= MAX - 1;
}

int pop(void){
  top--;
  return S[top+1];
}

Measured memory_bytes: 548
#include<bits/stdc++.h>
using namespace std;
int main() {
  int n,ans;
  cin>>n;
  if(n<10) ans=n;
  else if(n<100) ans=9;
  else if(n<1000) ans=n-99+9;
  else if(n<10000) ans=909;
  else if(n<100000) ans=n-9999+909;
  else if(n==100000) ans=90909;
  cout<<ans<<endl;
}

Measured memory_bytes: 256
N = gets.to_i
ary = gets.split.map(&:to_i).reverse
 
 
(0..N-2).each do |i|
  next if ary[i] >= ary[i+1]
  ary[i+1] -= 1
  next if ary[i] == ary[i+1]
  puts "No"
  exit
end
 
puts "Yes"

Measured memory_bytes: 9348
import copy
def main():
    H,W,K = map(int, input().split())
    road = [[0]*W for _ in range(H)]
    for i in range(H):
        c = input()
        for j in range(W):
            if c[j]=='.':
                road[i][j] = 0
            else:
                road[i][j] = 1
    ans = 0
    for h in range(2**H):
        for w in range(2**W):
            harr = [0]*H
            warr = [0]*W
            for i in range(H):
                harr[H-i-1] = (h>>i)&1
            for i in range(W):
                warr[W-i-1] = (w>>i)&1
            tmp = 0
            for i in range(H):
                for j in range(W):
                    if harr[i]==0 and warr[j]==0 and road[i][j]==1:
                        tmp += 1
            if tmp==K: ans += 1
    print(ans)

main()


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

using namespace std;

typedef long long int ll;

const ll MAXN = 1e5 + 5;

vector < vector < ll > > adj(MAXN, vector < ll > ());

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

  ll x;
  cin >> x;
  for(int i = -200; i <= 200; i++){
    ll a = pow(i, 5);
    for(int j = -200; j <= 200; j++){
      ll b = pow(j, 5);
      if(a - b == x){
        cout << i << " " << j << endl;
        return 0;
      }
    }
  }
}


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

#define ll long long
#define ull unsigned long long 
#define endl '\n'
#define pii pair<int, int>
#define all(a) a.begin(),a.end()

template <typename T>
inline T gcd(T a, T b) { while (b != 0) swap(b, a %= b); return a; }

int main(){
    int n;
    cin >> n;
    map<int, int> m1, m2;  
    for(int i=0; i<n; ++i){
        int x; cin >> x;

        if(i&1)
            ++m1[x];
        else
            ++m2[x];
    }

    pii m1l={0,0}, m2l={0,0};

    for(auto x:m1)
        m1l = max(m1l, {x.second, x.first});
    for(auto x:m2)
        m2l = max(m2l, {x.second, x.first});
    
    if(m1l !=m2l){
        cout << n-m1l.first-m2l.first;
    }
    else{
        int e1=0, e2=0;
        for(auto x:m1)
            if(x.first != m1l.second)
                e1 = max(e1, x.second);

        for(auto x:m2)
            if(x.first != m2l.second)
                e2 = max(e2, x.second);

        if(m1l.first+e2 >= m2l.first+e1){
            cout << n-m1l.first-e2;
        }
        else{
            cout << n-m2l.first-e1;
        }
    }
}


Measured memory_bytes: 8300
#include "iostream"
#include "algorithm"
#include "string"
#include "vector"
#include "cmath"
#include "bitset"
#include "queue"
#include "functional"
#include "map"
#include "unordered_map"
#include "set"
#include "stack"
 
#define lp(n) for (int i = 0; i < n; i++)
#define LP(n,i) for (int i = 0; i < n; i++)
#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define nyan "(=^･ω･^=)"
typedef long long ll;
using namespace std;

int n,a[300][300];
ll ans;
bool gb[300][300];

int main(){
	cin>>n;
	lp(n)
		LP(n,j){
			cin>>a[i][j];
			gb[i][j]=true;
		}
	lp(n){
		LP(n,j){
			if(j!=i)
				LP(n,k){
					if(k!=j&&k!=i){
						if(a[i][k]+a[k][j]<a[i][j]){
							cout<<-1<<endl;
							return 0;
						}
						if(a[i][k]+a[k][j]==a[i][j])
							gb[i][j]=false;
					}
				}
		}
	}
	ans=0;
	lp(n)
		LP(n,j)
			if(gb[i][j])
				ans+=a[i][j];
	cout<<ans/2<<endl;
	return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>


using namespace std;


int main(){

    char s[3];
    cin >> s;

    sort(s, s + 3);

    string l = s;

    if( l == "abc"){
        cout << "Yes";
    }
    else{
        cout << "No";
    }
    
  
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int sum[300], num[300][5];

int main(void)
{
	int n, i, j, k, c;
	
	scanf("%d", &n);
	
	for (i = 0; i < n; i++){
		for (j = 0; j < 3; j++){
			scanf("%d", &num[i][j]);
		}
	}
	for (k = 0; k < 3; k++){
		for (i = 0; i < n; i++){
			
			c = 0;
			
			for (j = 0; j < n; j++){
				if (i != j && num[i][k] == num[j][k]){
					num[j][k] = 0;
					c = 1;
				}
			}
			if (c == 1){
				num[i][k] = 0;
			}
		}
		for (j = 0; j < n; j++){
				sum[j] += num[j][k];
		}
	}
	for (i = 0; i < n; i++){
		printf("%d\n", sum[i]);
	}
	
	return (0);
}

			

Measured memory_bytes: 600
#include<iostream>
using namespace std;
long long A[100010]={0},B[100010]={0};
int main(){
	int N;
	cin>>N;
	for(int i=0;i<=N;i++){
		cin>>A[i];
	}//怪兽 
	for(int i=0;i<N;i++){
		cin>>B[i];
	}//英雄 
	long long ans=0;
	for(int i=0;i<N;i++){
		if(A[i]>B[i]){
			ans=ans+B[i];
		}else{
			ans=ans+A[i];
			B[i]=B[i]-A[i];
			if(B[i]>=A[i+1]){
				ans=ans+A[i+1];
				A[i+1]=0;
			}else{
				ans=ans+B[i];
				A[i+1]=A[i+1]-B[i]; 
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

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

typedef long long ll;
const ll MOD = 1000000007;

int main() {
  int N;
  std::string S1, S2;
  std::cin >> N >> S1 >> S2;

  ll ans = 1;
  int last = 0;
  for(int i = 0; i < N; ++i) {
    if(S1[i] == S2[i]) {
      switch(last) {
        case 0:
          ans *= 3; ans %= MOD;
          break;
        case 1:
          ans *= 2; ans %= MOD;
          break;
        case 2:
          break;
      }
      last = 1;
    } else {
      switch(last) {
        case 0:
          ans *= 6; ans %= MOD;
          break;
        case 1:
          ans *= 2; ans %= MOD;
          break;
        case 2:
          ans *= 3; ans %= MOD;
          break;
      }
      last = 2;
      ++i;
    }
  }

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


Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::{Ordering};

#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};

#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, Write};

#[allow(unused_imports)]
use std::iter::FromIterator;

#[allow(unused_macros)]
macro_rules! min {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::min($x, min!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! max {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        std::cmp::max($x, max!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! get { 
    ([$t: ty]) => { 
        { 
            let mut line = String::new(); 
            stdin().read_line(&mut line).unwrap(); 
            line.split_whitespace().map(|t|t.parse::<$t>().unwrap()).collect::<Vec<_>>()
        }
    };
    ([$t: ty];$n: expr) => {
        (0..$n).map(|_|get!([$t])).collect::<Vec<_>>()
    };
    ($t: ty) => {
        {
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t: ty),*) => {
        { 
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            ($(iter.next().unwrap().parse::<$t>().unwrap(),)*)
        }
    };
    ($t: ty; $n: expr) => {
        (0..$n).map(|_|get!($t)).collect::<Vec<_>>()
    };
    ($($t: ty),*; $n: expr) => {
        (0..$n).map(|_|get!($($t),*)).collect::<Vec<_>>()
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*).unwrap();
    }
}

const BIG_STACK_SIZE: bool = true;

#[allow(dead_code)]
fn main() {
    use std::thread;
    if BIG_STACK_SIZE {
        thread::Builder::new()
            .stack_size(32 * 1024 * 1024)
            .name("solve".into())
            .spawn(solve)
            .unwrap()
            .join()
            .unwrap();
    } else {
        solve();
    }
}

fn solve() {
    let (n,l) = get!(isize, isize);

    let sum = n*(l-1)+n*(n+1)/2;
    let mut mn = std::isize::MAX;
    let mut taste = 0;
    for i in 1..n+1 {
        if mn > (l+i-1).abs() {
            mn = (l+i-1).abs();
            taste = sum-(l+i-1);
        }
    }
    println!("{}", taste);
}


Measured memory_bytes: 8572
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,ans = 0;
    cin>>n;
    for(i = 1;i <= n;i++)
    {
        int tmp = i,sum = 0;
        while(tmp!=0)
        {
            sum++;
            tmp/=10;
        }
        if(sum%2!=0)
            ans++;
    }
    cout<<ans<<endl;
    return 0;
}


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

class UnionFind {
private:
  std::vector<long long int> data;
public:
  UnionFind(const int size):data(size,-1){}
  void union_set(long long int x, long long int y){
    x = this->get_root(x);
    y = this->get_root(y);
    
    if (x != y) {
      if (this->data[y] < data[x]) {
        swap(x, y);
      }
      this->data[x] += this->data[y];
      this->data[y] = x;
    }  
  }
  bool is_same(const long long int x, const long long int y){
    return this->get_root(x) == this->get_root(y);
  }
  int get_root(const long long int x){
    return this->data[x] < 0 ? x : this->data[x] = this->get_root(this->data[x]);
  }
  int get_size(long long int x){
    return -this->data[this->get_root(x)];
  }
};

int main(){
    long long int N, M;
    cin >> N >> M;

    long long int A[M], B[M];
    for(long long int i = M-1; i >= 0; --i){
        cin >> A[i] >> B[i];
    }

    UnionFind uf(N+1);
    vector<long long int> ans(M+1);
    ans[0] = N*(N-1)/2;
    for(long long int i = 0; i < M; ++i){
        long long int a = uf.get_size(A[i]);
        long long int b = uf.get_size(B[i]);
        ans[i+1] = ans[i] + a*(a-1)/2 + b*(b-1)/2;
        if(uf.is_same(A[i], B[i])){
            ans[i+1] -= a*(a-1)/2;
        }

        uf.union_set(A[i], B[i]);
        long long int c = uf.get_size(A[i]);
        if(c == N){
            for(long long int j = i+1; j <= M; ++j) ans[j] = 0;
            break;
        }else{
            ans[i+1] -= c*(c-1)/2;
        }
    }

    for(long long int i = M-1; i >= 0; --i){
        cout << ans[i] << endl;
    }
}

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

int main(){
	int H, S;


	for (;;){
		cin >> H >> S;

		if (H == 0 && S == 0){
			break;
		}

		for (int i = 0; i < H; i++){
			if (i % 2 == 0){
				for (int o = 0; o < S; o++){
					if (o % 2 == 0){
						cout << "#";
					}
					else{
						cout << ".";
					}
				}
			}
			else{
				for (int o = 0; o < S; o++){
					if (o % 2 == 1){
						cout << "#";
					}
					else{
						cout << ".";
					}
				}
			}
			cout << endl;
		}
		cout << endl;
	}
}


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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) (r).begin(),(r).end()
#define gsort(st,en) sort((st),(en),greater<int>())
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using dict = map<string,int>;
using pii = pair<int,int> ;

constexpr int imax = ((1<<30)-1)*2+1 ;
constexpr int inf = 100000000;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0};
const int dx[] = {0,-1,0,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

template<typename T>
void Unique(vector<T> &v){
  sort(all(v));
  v.erase(unique(all(v)),v.end());
}

template<typename T>
T ston(string& str, T n){
  istringstream sin(str) ;
  T num ;
  sin >> num ;
  return num ;
}

void Ans(bool f){
  if(f) cout << "YES"<<endl;
  else cout << "NO"<<endl;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s;
  int a;
  map<string,vector<int>> m;
  while(cin >> s >> a){
    m[s].pb(a);
  }
  for(auto it = m.begin(); it != m.end(); ++ it){
    sort(all((*it).second));
    cout << it->fi<<endl;
    rep(i,(*it).second.size()-1){
      cout << it->second[i] << " ";
    }
    cout << it->second[it->se.size()-1] << endl;
  }
  return 0;
}

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

void solve()
{
    long long n, k;
    cin>>n>>k;
    vector<long long> v(n);
    for( long long i=0; i<n; i++)
    {
        cin>>v[i];
    }
    if(n<=k)
    {
        cout<<0<<endl;
        return;
    }
    sort(v.begin(),v.end()); long long sum=0;
    for(long long i=0; i<v.size()-k; i++)
    {
        sum += v[i];
    }
    cout<<sum<<endl;
}
int main()
{
    int t;
    t=1;
    while(t--)
    {
        solve();

    }
return 0;
}


Measured memory_bytes: 1792
<?php

class Calculator
{
    private $N;
    private $minv;
    private $maxv;

    public function __construct()
    {
        $this->N = trim(fgets(STDIN));
        $this->minv = trim(fgets(STDIN));
        $this->maxv = 1 - 10**9;
    }

    public function ObtainMaximumProfit()
    {
        $N = $this->N;
        $minv = $this->minv;
        $maxv = $this->maxv;

        for ($i = 1; $i < $N; $i++) {
            $n = trim(fgets(STDIN));
            $profit = $n - $minv;

            if ($maxv < $profit) {
                $maxv = $profit;
            }

            if ($n < $minv) {
                $minv = $n;
            }
        }
        echo $maxv . PHP_EOL;
    }
}

$calculator = new Calculator();
$calculator->ObtainMaximumProfit();


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

#define _CRT_SECURE_NO_WARNINGS
#define TLong long long
#define TBMod 1000000007

TLong gcd(TLong a,TLong b){
	if(!(a % b)) return b;
	return gcd(b,a % b);
}

// qsort(array, size, sizeof(int),comp);
TLong comp(const TLong *a,const TLong *b){
	return (*a - *b);
}

int main(int argc, char const *argv[])
{
	TLong n,*a;
 
	scanf("%lld",&n);
	a = (TLong *)malloc(sizeof(TLong) * n);
	for (int i = 0; i < n; ++i){
		scanf(" %lld",&a[i]);
	}
	qsort(a,n,sizeof(TLong),comp);
	if(a[0] == 0){
		puts("1");
	}
	else{
		for (int i = 0; i < n; ++i)	a[i] = gcd(a[i],a[0]);
		qsort(a,n,sizeof(TLong),comp);
		printf("%lld\n", a[0]);
	}
	return 0;
}


Measured memory_bytes: 1788
#include<iostream>
#include<string>
using namespace std;
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ll long long
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		s=(s<<1)+(s<<3)+(ch^48);
		ch=getchar();
	}
	return s*w;
}
int main()
{
	int ans=0;
	string a,b;
	cin>>a>>b;
	f(i,0,a.length()-1)
	{
		if(a[i]!=b[i])++ans;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 3836
//ThakurAnurag
//TemplateCode

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

#define ll long long int
#define ull unsigned long long int
#define fo(i,a,n) for(ll i=a;i<n;i++)
#define fo2(i,a,n) for(ll i=n;i>=a;i--)
#define endl "\n"
#define sp " "
#define f first
#define s second
#define pb push_back
#define buffer ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define mod 1000000007
#define lower(str) transform(str.begin(), str.end(), str.begin(), ::tolower);
#define upper(str) transform(str.begin(), str.end(), str.begin(), ::toupper);
#define init(arr,val) memset(arr,val,sizeof(arr))
#define vecl(v) vector<ll> v
#define vecs(v) vector<string> v
#define vecp(v) vector < pair <ll,ll> > v

int main()
{
	ll a,b,c,d,e;
	cin>>a>>b>>c>>d>>e;

	if(a==0) cout<<"1"<<endl;
	else if(b==0) cout<<"2"<<endl;
	else if(c==0) cout<<"3"<<endl;
	else if(d==0) cout<<"4"<<endl;
	else cout<<"5"<<endl;
	return 0;
}

Measured memory_bytes: 3588
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

N = int(input())
A = list(map(int,(input().split())))
flag = 0

if N != 0:

    if A[0] != 0:
        flag = -1
    if A[-1] == 0:
        flag = -1

    S = [-1]*N
    S[0] = sum(A)
    for i in range(1,N):
        S[i] = S[i-1] - A[i]

    M = [-1]*N
    M[0] = 2
    for i in range(1,N):
        M[i] = (M[i-1]-A[i])*2
        if M[i] <= 0:
            flag = -1
    #print(S,M)

    if flag != -1:
        V = [-1]*N
        for i in range(N):
            if S[i] > M[i]:
                V[i] = M[i]
            else:
                V[i] = S[i]
        ans = sum(V)+1

        if S[-1] <= M[-1]:
            #print(V)
            print(ans)
        else:
            print(-1)
    else:
        print(-1)

else:
    if A[0] == 1:
        print(1)
    else:
        print(-1)

Measured memory_bytes: 703160