akhauriyash/Code-Regression huggingface dataset:
// Last Change: 04/01/2019 19:12:27.
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

namespace NS {
void LoopUntilZeroInpput() {
  int hogegegege = 0;
  while (cin >> hogegegege && hogegegege != 0) {
  }
}
} // namespace NS

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

  if (N % 2 == 0) {
    cout << N;
  } else {
    cout << N * 2;
  }

  cout << endl;

  //NS::LoopUntilZeroInpput();
}


Measured memory_bytes: 256
import java.util.*;
import java.lang.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int f = 0;
        int m = n;
        while (m > 0) {
            f += m % 10;
            m /= 10;
        }
        if (n % f == 0) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }

}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
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;
}
template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts)
{
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v)
{
    for (auto &e : t)
        fill_v(e, v);
}
int main()
{
    ll N, K, ans = 0;
    cin >> N >> K;
    for (int b = K + 1; b <= N; b++)
    {
        ans += (N / b) * (b - K) + max(0LL, (N % b) - K + 1);
    }
    if (K == 0)
        ans -= N;
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
S = [input() for _ in range(N)]
from collections import Counter
c = Counter(S)
name = []
num = 0
for k,v in c.items():
    if v>num:
        num = v
        name = [k]
    elif v == num:
        name.append(k)
n_sort = sorted(name)
for i in range(len(n_sort)):
    print(n_sort[i])

Measured memory_bytes: 35472
import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main{
  public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] line = br.readLine().split(" ");
    int a = Integer.parseInt(line[0]);
    int b = Integer.parseInt(line[1]);
    String op = "==";
    if (a>b) {
      op = ">";
    }else if(a<b){
      op = "<";
    }
    System.out.println("a "+op+" b");
  }
}

Measured memory_bytes: 24056
#include<iostream>

using namespace std;

int main(){
	int x1,y1,x2,y2;
	int x3,y3,x4,y4;
	int turnX,turnY;
	cin >> x1 >> y1 >> x2 >> y2;
	turnX=x2-x1;
	turnY=y2-y1;
	x3=x2-turnY;
	y3=y2+turnX;
	x4=x1-turnY;
	y4=y1+turnX;
	cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
	char a, b;
	cin >> a >> b;
	if (a == 'H'&&b == 'H') {
		cout << "H" << endl;
	}
	else if (a == 'D'&&b == 'D') {
		cout << "H" << endl;
	}
	else {
		cout << "D" << endl;
	}
}

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

int main() {
    int a, b, c, d;
    scanf("%d %d %d %d", &a, &b, &c, &d);
    while (a > 0 && c > 0) {
        c -= b;
        if (c < 0) break;
        a -= d;
    }
    if (c <= 0) printf("Yes\n");
    else printf("No\n");
}

Measured memory_bytes: 1636
import math


def main():
    N = int(input())
    P = [None] * N
    for i in range(N):
        x, y = map(int, input().split())
        t = math.atan2(y, x)
        P[i] = (t, x, y)
    P.sort()
    P = P + P
    for i in range(N, 2*N):
        t, x, y = P[i]
        P[i] = (t+math.pi * 2, x, y)
    ans = 0
    for i in range(0, N):
        X, Y = 0, 0
        for j in range(i, N+i):
            _, x, y = P[j]
            X += x
            Y += y
            tmp = math.sqrt(X**2 + Y**2)
            ans = max(tmp, ans)

    print(ans)


if __name__ == "__main__":
    main()


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

#define REP(i, start, count) for(int i=(start); i<(int)(count); ++i)
#define rep(i, count) REP(i, 0, count)
#define ALLOF(c) (c).begin(), (c).end()

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> veci;
typedef vector<long long> vecll;
typedef vector<unsigned long long> vecull;

ll N;
vector<ll> A;

int main(void) {
    cin >> N;
    A.assign(N, 0);

    ll sum = 0;
    rep(i, N) {
        cin >> A[i];
        sum += A[i];
    }

    // X[0]を求める
    vecll X(N, 0);
    X[0] = sum;
    for (int i = 1; i < N; i += 2) {
        X[0] -= 2 * A[i];
    }

    for (int i = 1; i < N; ++i) {
        X[i] = 2 * A[i - 1] - X[i - 1];
    }

    rep(i, N) {
        cout << X[i] << ' ';
    }
    cout << endl;
    


    return 0;
}

Measured memory_bytes: 2944
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

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

template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

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

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

int calcSwaps(vector<int> array) {
    int cnt = 0;
    int size = array.size();

    for (int i = 0; i + 1 < size; ++i) {
        for (int j = i + 1; j < size; ++j) {
            if (array[j] < array[i]) {
                ++cnt;
            }
        }
    }

    return cnt;
}

long long mergecount(vector<int> &a) {
  long long count = 0;
  int n = a.size();
  if (n > 1) {
    vector<int> b(a.begin(), a.begin() + n/2);
    vector<int> c(a.begin() + n/2, a.end());
    count += mergecount(b);
    count += mergecount(c);
    for (int i = 0, j = 0, k = 0; i < n; ++i)
      if (k == c.size())       a[i] = b[j++];
      else if (j == b.size())  a[i] = c[k++];
      else if (b[j] <= c[k])   a[i] = b[j++];
      else                   { a[i] = c[k++]; count += (long long) (n/2 - j); }
  }
  return count;
}

int main(void){
  int N, ans = 0;
  cin >> N;
  vector<int> A, S;
  set<int> even;

  REP(i, N){
    int x;
    scanf("%d", &x);
    A.PB(x);
    S.PB(x);
  }

  SORT(S);
  for(int i=0;i<N;i++){
    if(i%2 == 0) even.insert(S[i]);
  }
  for(int i=0;i<N;i++){
    if(i%2 == 0)
      if(even.count(A[i]) == 0) ans++;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3316
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

int main() {
    int n, m; cin >> n >> m;
    vector<pair<int, int>> v(n, {0,0});
    int a = 0, b = 0;
    for (int i = 0; i < m; i++) {
        int p;
        string s;
        cin >> p >> s;
        if (s == "AC") {
            if (v[p - 1].first == 0) {
                a++;
                v[p - 1].first = 1;
            }
        }
        else {
            if (v[p - 1].first == 0) {
                v[p-1].second++;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (v[i].first == 1) {
            b += v[i].second;
        }
    }
    cout << a << " " << b << endl;
    return 0;
}

Measured memory_bytes: 1024
#include "cstdio"

int main (){
    int h,w;

    for(;;){
        scanf("%d%d",&h,&w);
        if(h==0&&w==0) break;
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                if(!((i+j)%2)){
                    printf("#");
                }else{
                    printf(".");
                }
            }
            printf("\n");
        }
        printf("\n");
    }
}

Measured memory_bytes: 2676
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<vector>
#include<cmath>
#include<cstdio>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define it ::iterator
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double ESP=1e-10;
using namespace std;
int main(){
  vector<int>in(6);
  rep(i,6)cin>>in[i];
  int a[6]={1,5,10,50,100,500};
  int sum=0;
  rep(i,6)sum+=a[i]*in[i];
  if(sum>=1000)cout<<1<<endl;
  else cout<<0<<endl;


}

Measured memory_bytes: 1196
import java.util.Scanner

import scala.math.BigDecimal.RoundingMode._
object Main extends App {

  val sc = new Scanner(System.in)
  while(sc.hasNext){
    val line = sc.nextLine()
    val n =  line.split(" ").map {_.toDouble}
    val a = n(0)
    val b = n(1)
    val c = n(2)
    val d = n(3)
    val e = n(4)
    val f = n(5)

    var x :BigDecimal = BigDecimal((b*f-e*c) / (b*d-a*e)).setScale(3, HALF_UP)
    var y :BigDecimal = ((c - a * x) / b).setScale(3, HALF_UP)

    if(x==0)x=0;
    if(y==0)y=0;
    println(f"$x%.3f $y%.3f")
  }
}

Measured memory_bytes: 45372
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
using llong = long long;

llong n;
llong cnt[10];

int main() {
    for (int i = 0; i < 4; i++) {
        cin >> n;
        cnt[n] = 1;
    }

    if (cnt[1] && cnt[9] && cnt[7] && cnt[4]) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}


Measured memory_bytes: 256
/**
 *	@file: B.cpp
 *	@author: Huy Le
 *	@created: 2020-08-29 19:21
**/

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

#define ll long long
#define ld long double
#define sz(x) (int)(x).size()
const char newl = '\n';

void DEBUGLOCAL() { cerr << ")" << newl; }
template<class A, class... B> 
void DEBUGLOCAL(A argc, B... argv) {
	cerr << argc;
	if(sizeof...(argv))
		cerr << ", ";
	DEBUGLOCAL(argv...);
}
#ifdef _DEBUG
#define dbg(...) cerr << "LINE(" << __LINE__ << ") [" << __FUNCTION__ << "] -> (" << #__VA_ARGS__ << "): (",DEBUGLOCAL(__VA_ARGS__)
#else
#define dbg(...) 0
#endif

int ts;
string s, t;

void solve() {
    int ans = 0;
    cin >> s >> t;
    for(int i=0; i+sz(t)-1<sz(s); ++i) {
        int cnt = 0;
        for(int j=0; j<sz(t); ++j) {
            if(s[i+j] == t[j])
                ++cnt;
            else {
                ans = max(cnt, ans);
            }
        }
        ans = max(ans, cnt);
    }
    cout << (sz(t) - ans) << newl;
}

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

		//++i,cout << "Case #" << i << ": ",
		solve();
}


Measured memory_bytes: 3600
from itertools import product
N, M = map(int,input().split())
S = []
for m in range(M):
    s = list(map(int,input().split()))
    S.append(s[1:])
P = list(map(int,input().split()))

ans = 0
for c in product([0,1],repeat=N):
    ok = True
    for m in range(M):
        sm = 0
        for s in S[m]:
            sm += c[s-1]
        if sm % 2 != P[m]:
            ok = False
            break
    if ok:
        ans += 1
print (ans)
        


Measured memory_bytes: 3064
import sys
sys.setrecursionlimit(10**7)

def main():
  r1,c1,r2,c2=map(int,input().split())
  mod=pow(10,9)+7

  # コンビネーション、さらに高速。あらかじめO(N)の計算をすることでのちの計算が早くなる
  def cmb(n, r, mod):
      if ( r<0 or r>n ):
          return 0
      r = min(r, n-r)
      return g1[n] * g2[r] * g2[n-r] % mod
  g1 = [1, 1] 
  g2 = [1, 1] 
  inverse = [0, 1]
  for i in range( 2, r2+c2+3):
      g1.append( ( g1[-1] * i ) % mod )
      inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
      g2.append( (g2[-1] * inverse[-1]) % mod )
  ans=0
  for r in range(r1,r2+1):
    ans+=cmb(r+c2+1,r+1,mod)-cmb(r+c1,r+1,mod)
    ans%=mod
  print(ans)

if __name__=='__main__':
  main()


Measured memory_bytes: 133516
import java.util.*;

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

        int n = sc.nextInt();
        int k = sc.nextInt();


        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> a - b);

        for(int i = 0; i < n; i++){
            q.add(sc.nextInt());
        }

        int ans = 0;

        for(int i = 0; i < k; i++){
            ans += q.poll();
        }

        System.out.println(ans);

    }
}


Measured memory_bytes: 39160
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
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 (a>b) { a=b; return 1; } return 0; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

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

	int N, K; cin >> N >> K;
	int ans = 0;
	while(N) {
		N /= K;
		ans++;
	}
	cout << ans << endl;
	
    
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
unordered_set<int>a[200003];
bool vis[200003];
int dfs(int k){
   vis[k]=true;
   int sz=1;
   for(auto c:a[k]){
        if(!vis[c]){
    vis[c]=true;
    sz+=dfs(c);}
   }
   return sz;
}
int main(){
   int n,m;
   cin>>n>>m;
   while(m--){
    int x,y;
    cin>>x>>y;
    a[x].insert(y);
    a[y].insert(x);
   }
   int sz,ans=0;
   for(int i=1;i<=n;i++){
    if(!vis[i]){
        sz=dfs(i);
        ans=max(ans,sz);
    }
   }
   cout<<ans;
}


Measured memory_bytes: 39668
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize ("Ofast")
//#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define d long double
#define pii pair<int,int>
#define pb push_back
#define pf push_front
#define cases int t;cin>>t;while(t--)
#define N 100003
#define M 103
#define inf LLONG_MAX
//int mod=1e9+7;
//int mod=998244353;

signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    int a,b,c;
    cin>>a>>b>>c;
    int ans=b;
    ans+=min(c,a);
    c-=a;
    if(c>0)
    {
        ans+=min(b,c);
        c-=b;
        if(c>0)
            ++ans;
    }
    cout<<ans;


    return 0;
}


Measured memory_bytes: 256
import sys

input = sys.stdin.readline

N = int(input())
ab = [list(map(int,input().split())) for i in range(N-1)]

downnum = [0]*N
neighbor = [[] for i in range(N)]
for ai, bi in ab:
	downnum[ai-1] += 1
	neighbor[ai-1].append(bi-1)

K = max(max(downnum[1::])+1, downnum[0])
Kpre = [-1]*N
Kpre[0] = K
ansdict = {}
queue = [0]
knum = 1
while len(queue)>0:
	nq = []
	for i in queue:
		kk = Kpre[i]+1
		if kk>K: kk -= K
		for j in neighbor[i]:
			nq.append(j)
			ansdict[(i,j)] = kk 
			Kpre[j] = kk
			kk += 1
			if kk>K: kk -= K

	queue = nq

print(K)
for ai, bi in ab:
	print(ansdict[(ai-1,bi-1)])

Measured memory_bytes: 90136
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define MAXX 1000005
#define PI 3.14159265358979323846264338327950
#define ll signed long long int
using namespace std;
ll t , n, ans = 0, k, a[MAXX], b[MAXX]={0}, x, y, z, mn, mx, m = 0;
double f = 0.5;

int main()
{
	cin >> n >> y >> z;
	vector<ll> v(n + 5, y-z);
	for(ll i = 0; i < z; i++){
		cin >> k;
		b[k] ++;
	}
	for(ll i = 1; i <= n; i++){
		v[i] += b[i];
	}
	for(ll i = 1; i <= n; i++){
		if(v[i] > 0){
			cout << "Yes" << endl;
		}
		else{
			cout << "No" << endl;
		}
	}
	return 0;

}


Measured memory_bytes: 2176
n=gets.to_i
a = gets.chomp.split(" ").map!(&:to_i)
b = gets.chomp.split(" ").map!(&:to_i)
ex=[]
lack=0
ans = 0
n.times do |i|
  t=a[i]-b[i]
  ex << t if t>0
  if t<0
    lack+= -t
    ans+=1
  end
end
ex.sort!.reverse!
ex.each do |v|
  break if lack<=0
  lack-=v
  ans+=1
end
if lack<=0
  puts ans
else
  puts -1
end

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

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1e9
typedef long long ll;

vector<double> t;
vector<double> v;
vector<double> t_sum;
double ans;

//速度の上限が厳しいものに合わせて台形を追加
//その範囲を除いて再帰的に解いていく

void dfs(double l, double r, double h){//[l,r]はすでに速度hに達している
    //cout << l << ", " << r << ", " << h << endl;
    if(l>=r) return;

    int l_itr = upper_bound(ALL(t_sum), l) - t_sum.begin() - 1;//左端はどの区間か
    int r_itr = lower_bound(ALL(t_sum), r) - t_sum.begin() - 1;//右端はどの区間か
    //cout << "  " << l_itr << ", " << r_itr << endl;

    if(r_itr == l_itr){//[l,r]が同一区間内なら
        if(r-l > 2*(v[r_itr]-h)){
            ans += ((r-l) - (v[r_itr]-h)) * (v[r_itr]-h);
            return;
        }else{
            ans += (r-l)*(r-l)/4.0;
            return;
        }
    }

    double min_v = INF;
    int min_itr = -1;
    FOR(i,l_itr,r_itr+1){//区間内の最小速度を求める
        if(min_v > v[i]){
            min_v = v[i];
            min_itr = i;
        }
    }
    //cout << "    " << min_v << ", " << min_itr << endl;

    if((r-l) <= 2*(min_v-h)){//そもそも台形にならないなら＝最小の上限にすらたどり着かないなら
        ans += (r-l)*(r-l)/4.0;
        return;
    }

    double l1,r1,l2,r2;
    l1 = l+min_v-h;//台形の上底の両端の値
    r2 = r-min_v+h;

    r1 = t_sum[min_itr];//最小速度の両端の値
    l2 = t_sum[min_itr+1];

    ans += ((r-l) - (min_v-h))*(min_v-h);

    if(r2 < r1 || l2 < l1){//上記値の範囲で場合わけ
        dfs(l1, r2, min_v);
    }else{
        dfs(l1,r1,min_v);
        dfs(l2,r2,min_v);
    }
}

int main() {
    int N; cin >> N;
    t.assign(N,0);
    v.assign(N,0);
    t_sum.assign(N+1,0);
    REP(i,N) cin >> t[i];
    REP(i,N) cin >> v[i];

    REP(i,N) t_sum[i+1] += t_sum[i] + t[i];
    ans = 0.0;
    dfs(0,t_sum[N],0);
    cout << fixed << setprecision(10) << ans << endl;
    return 0;
}

Measured memory_bytes: 3784
#include <stdio.h>

int main(void)
{
    int h, w, i, j;

    while (1) {
        scanf("%d %d", &h, &w);

        if (h == 0 || w == 0)
            break;

        for (i = 1; i <= h; i++) {
            for (j = 1; j <= w; j++) {
                printf("#");
                if (j == w)
                    printf("\n");
            }
        }

        printf("\n");
    }

    return 0;
}

Measured memory_bytes: 572
# ABC 128: B – Guidebook
N = int(input())

shops = []
for i in range(N):
    s = input().split()
    shops.append([i + 1, s[0], int(s[1])])

shops.sort(key = lambda x:x[2], reverse = True)
shops.sort(key = lambda x:x[1])

for k in [shop[0] for shop in shops]:
    print(k)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
 
typedef pair<int,int> P;
int done[510][510];

int cost[510][510][4];
int W,H,N;
 
int valid(int x,int y){
    if( x < 0 || y < 0 || x >= W || y >= H ) return 0;
    return 1;
}
int main(){
    cin >> W >> H >> N;
    int sx,sy;
    int gx,gy;
    cin >> sx >> sy;
    cin >> gx >> gy;
	
	#define L 0
	#define D 1
	#define R 2
	#define U 3
	
    for(int i = 0 ; i < N ; i++){
        int x,y;
        int t;
        string p;
        cin >> x >> y >> t >> p;
        for(int j = 0 ; j < t ; j++){
            for(int k = 0 ; k < p.size() ; k++){
                int tx = x;
                int ty = y;
                if( p[k] == 'L' )tx--;
                if( p[k] == 'R' )tx++;
                if( p[k] == 'U' )ty--;
                if( p[k] == 'D' )ty++;
                if( valid(tx,ty) ){
                    if( p[k] == 'D' ){
						cost[x][y+1][R]++;
						cost[x+1][y+1][L]++;
                    }else if( p[k] == 'R' ) {
						cost[x+1][y][D]++;
						cost[x+1][y+1][U]++;

                    }else if( p[k] == 'U' ){
						cost[tx][ty+1][R]++;
						cost[tx+1][ty+1][L]++;
                    }else{
						cost[tx+1][ty][D]++;
						cost[tx+1][ty+1][U]++;
                    }
                    x = tx;
                    y = ty;
                }

 
            }
        }
    }
	for(int i = 0 ; i < 510 ; i++)
		for(int j = 0 ; j < 510 ; j++)
			done[i][j] = 1e9;
    /*
    ooo
    ooo
    ooo
    */
    priority_queue<pair<int,P> , vector< pair<int,P> > , greater< pair<int,P> > > Q;
    Q.push({0,{sx,sy}});
	done[sx][sy] = 0;
    int ok = 0;
    while( Q.size() ){
        pair<int,P> q = Q.top(); Q.pop();
        int x = q.second.first;
        int y = q.second.second;
        
        if( done[x][y]< q.first ) continue;
 
        if( x == gx && y == gy){
            cout << q.first << endl;
       		 return 0;
        }
        int dx[] = {-1,0,1,0};
        int dy[] = {0,1,0,-1};
        for(int i = 0 ; i < 4 ; i++){
			if( x+dx[i] < 0 || x+dx[i] > W || y+dy[i] < 0 || y+dy[i] > H ) continue;
            int c = q.first + cost[x][y][i];
			if( done[x+dx[i]][y+dy[i]] > c ){
				done[x+dx[i]][y+dy[i]] = c;
				Q.push(make_pair(c,P(x+dx[i],y+dy[i])));
			}
        }
             
    }
 
}

Measured memory_bytes: 10240
n, m = map(int, input().split())
A = [0]*n
B = [0]*n
for i in range(n):
    A[i], B[i] = map(int, input().split())

r = 0
kA = sorted(range(n), key=lambda k: A[k])
for i in range(n):
    r += A[kA[i]]*min(m, B[kA[i]])
    m -= B[kA[i]]
    if m <0:
        break
print(r)

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

typedef long long int ll;
using namespace std;
int main(){
	int N,L,sum=0,che=10000000,ans=0;
	cin >> N >>L;
	vector<int> Ap(N,0);
	for(int i=0;i<N;i++){
		Ap[i]=L+i;
	}
	sum=accumulate(Ap.begin(),Ap.end(),0);
	for(int i=0;i<N;i++){
		if(che>abs(sum-(sum-Ap[i]))){
			che=abs(sum-(sum-Ap[i]));
			ans=sum-Ap[i];
		}
	}
	cout << ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
int main(){
  ll X,Y,Z,K,i,j,k;scanf("%lld%lld%lld%lld",&X,&Y,&Z,&K);
  ll A[X],B[Y],C[Z];
  for(i=0;i<X;i++) scanf("%lld",&A[i]);
  for(j=0;j<Y;j++) scanf("%lld",&B[j]);
  for(k=0;k<Z;k++) scanf("%lld",&C[k]);
  sort(A,A+X,greater<ll>());
  sort(B,B+Y,greater<ll>());
  sort(C,C+Z,greater<ll>());
  vector<ll> ans;
  for(i=0;i<X && i+1 <= K;i++){
    for(j=0;j<Y && (i+1)*(j+1) <= K;j++){
      for(k=0;k<Z && (i+1)*(j+1)*(k+1) <= K;k++){
        ans.emplace_back(A[i]+B[j]+C[k]);
      }
    }
  }
  sort(ans.begin(),ans.end(),greater<ll>());
  for(i=0;i<K;i++) printf("%lld\n",ans[i]);
}

Measured memory_bytes: 4328
import std;

alias sread = () => readln.chomp();
alias lread = () => readln.chomp.to!long();
alias aryread(T = long) = () => readln.split.to!(T[]);
//aryread!string();
void main()
{
    string s;
    scan(s);
    // writeln(s[0]);
    long x;
    long y;
    foreach (i; 0 .. s.length)
    {
        if (s[i] == '0')
        {
            x += 1;
        }
        else if (s[i] == '1')
        {
            y += 1;
        }
    }
    writeln(2 * (min(x, y)));
}

void scan(L...)(ref L A)
{
    auto l = readln.split;
    foreach (i, T; L)
    {
        A[i] = l[i].to!T;
    }
}

void arywrite(T)(T a)
{
    a.map!text.join(' ').writeln;
}


Measured memory_bytes: 3856
from fractions import gcd

n = int(input())
a_array = [int(x) for x in input().split()]

gcd_array = []
for index in range(n):
    if index == 0:
        gcd_array.append(a_array[0])
    else:
        gcd_array.append(gcd(gcd_array[index - 1], a_array[index]))
gcd_reversed_array = []
for index in range(n):
    if index == 0:
        gcd_reversed_array.append(a_array[index - 1])
    else:
        gcd_reversed_array.append(gcd(gcd_reversed_array[index - 1], a_array[-(index + 1)]))

res = 0
for i in range(n):
    if i == 0:
        res = max(res, gcd_reversed_array[-2])
    elif i == n - 1:
        res = max(res, gcd_array[-2])
    else:
        res = max(res, gcd(gcd_array[i - 1], gcd_reversed_array[-i - 1 -1]))
print(res)


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

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

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

int main(int argc, char *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    string S;
    cin >> S;

    bool flag = true;
    if (S[0] != 'A') {
        flag = false;
    }

    ll memo = 0;
    ll count = 0;
    for (ll i = 2; i < S.size()-1; i++) {
        if (S[i] == 'C') {
            count++;
            memo = i;
        }
    }

    if (count != 1 || S[S.size()-1] == 'C') {
        flag = false;
    }

    rep (i, S.size()) {
        if (i == 0 || i == memo) {
            ;
        } else {
            if(!islower(S[i])) {
                flag = false;
            }
        }
    }

    if (flag) {
        cout << "AC" << endl;
    } else {
        cout << "WA" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
n = int(input())
h = list(map(int,input().split()))
c = 0
for i in range(n-1):
    if h[i] - h[i+1] >= 2:
        print("No")
        c = 1
        break
    elif h[i] - h[i+1] == 1:
        h[i+1] += 1
    else:
        continue
if c == 0:
    print("Yes")

Measured memory_bytes: 14252
import random
import time

def down_score(d, c, last_d, score):
    sum = 0
    for i in range(26):
        sum = sum + c[i]*(d-last_d[i])
        
    return int(score - sum)


def main():
    D = int(input())

    c = list(map(int, input().split()))

    s = [list(map(int, input().split())) for i in range(D)]

    start = time.time()
    
    last_d = [0 for i in range(26)]
    
    ans = []
    
    score1 = 0
    
    for i in range(D):
        max = 0
        idx = 0
        for j in range(26):
            if max < (s[i][j] + c[j] * (i-last_d[j])*(i-last_d[j]+1)/2) and c[j] != 0:
                max = s[i][j] + c[j] * (i-last_d[j])*(i-last_d[j]+1)/2
                idx = j
            elif max == (s[i][j] + c[j] * (i-last_d[j])*(i-last_d[j]+1)/2) and c[j] * (i-last_d[j])*(i-last_d[j]+1)/2 > c[idx]* (i-last_d[idx])*(i-last_d[idx]+1)/2:
                idx = j
            
        last_d[idx] = i+1
        score1 += s[i][j]
        score1 = down_score(i+1,c,last_d,score1)
        
        ans.append(idx)


    while time.time() - start < 1.9:
        idx = random.randint(0,25)
        d = random.randint(0,D-1)
        tmp = ans[d]
        ans[d] = idx
        last_d = [0 for i in range(26)]
        score2 = 0    
        for i in range(D):
            score2 += s[i][ans[i]-1]
            last_d[ans[i]-1] = i+1
            score2 = down_score(i+1, c, last_d, score2)
        
        if score1 > score2:
            ans[d] = tmp
    
    for i in range(D):
        print(ans[i]+1)  

if __name__ == "__main__":
    main()


Measured memory_bytes: 9596
import java.util.Scanner;


public class Main {
	public static void main(String[] args){
		try(Scanner sc = new Scanner(System.in)) {
		
			int n = sc.nextInt();
			String s = sc.next();
			String t = sc.next();
			
			for(int i = 0 ; i < n ; i++ ) {
				System.out.print(s.charAt(i));
				System.out.print(t.charAt(i));
			}

		}
	}

}

Measured memory_bytes: 35824
import Control.Monad
import Data.List

main = do
    n <- readLn :: IO Int
    xn <- map read . words <$> getLine :: IO [Int]
    let minN = minimum xn
    let maxN = maximum xn
    print $ minimum $ map (\p -> sum $ map (\x -> (x - p)^2) xn ) [minN..maxN]

Measured memory_bytes: 4340
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define FOR(n) for(int i=0;i<n;i++)
#define FORJ(n) for(int j=0;j<n;j++)
#define PRN(n) printf("%d\n",n)
#define PRF(n) printf("%lf\n",n)
#define PRL(n) printf("%lld\n",n)
#define PRS(s) printf("%s\n",s)
#define PRC(c) printf("%c",c)
#define INF 10000000000
#define mod 1000000007
#define X 1000000
typedef long long int ll;
ll finv[X];
ll fac[X];
ll inv[X];
ll usort(const void *a, const void *b){return *(ll*)a-*(ll*)b;}
ll dsort(const void *a, const void *b){return *(ll*)b-*(ll*)a;}
ll ssort(const void *a, const void *b){return strcmp((char*)a,(char*)b);}
ll min(ll a,ll b){
  if(a>b)return b;
  return a;
}
ll max(ll a,ll b){
  if(a>b)return a;
  return b;
}
ll z(ll a){return max(a,-a);}
ll gcd(ll a,ll b){if(!b){return a;}else{return gcd(b,a%b);}}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll kt(ll a){
  ll sum=0;
  while(a){
    a/=10;
    sum++;
  }
  return sum;
}
ll ks(ll a){
  ll sum=0;
  while(a){
    sum+=a%10;
    a/=10;
  }
  return sum;
}
ll nCr(int n,int k){
  fac[0]=fac[1]=1;
  finv[0]=finv[1]=1;
  inv[1]=1;
  for (int i=2;i<X;i++){
    fac[i]=fac[i-1]*i%mod;
    inv[i]=mod-inv[mod%i]*(mod/i)%mod;
    finv[i]=finv[i-1]*inv[i]%mod;
  }
  return fac[n]*(finv[k]*finv[n-k]%mod)%mod;
}
int main(void){
  char s[2];
  scanf("%s",s);
  PRC(s[0]+1);
  return 0;
}


Measured memory_bytes: 128
from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)
from collections import defaultdict


def main():
    N = int(input())
    A = [0]*N
    dic = defaultdict(int)
    for i in range(N):
        A[i] = "".join(sorted((input()[:-1])))
        dic[A[i]] +=1
    ans = 0
    for k in dic:
        if dic[k] >= 2:
            ans += dic[k]*(dic[k]-1)//2
    print(ans)






if __name__ == "__main__":
    main()


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

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

  // x: 10000, y: 5000, z: 1000
  for (int x = 0; x <= N; x++) {
    for (int y = 0; y <= N - x; y++) {
      int z = N - x - y;
      int sum = 10000 * x + 5000 * y + 1000 * z;
      if (sum == Y) {
        cout << x << " " << y << " " << z << endl;
        return 0;
      }
    }
  }

  cout << "-1 -1 -1" << endl;
  return 0;
}

Measured memory_bytes: 256
lx = list(map(int,input().split(" ")))
lb = list(map(int,input().split(" ")))
#la = [li[0]][li[1]]
la = []
cnt = 0

for i in range(0, lx[0]):
    tmp = lx[2]
    la.append(list(map(int,input().split(" "))))
    for j in range(0, lx[1]):
        tmp += la[i][j] * lb[j]
    if (tmp > 0):
        cnt += 1

print(cnt)

Measured memory_bytes: 3188
import java.util.Scanner;
        
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int l = sc.nextInt();
        int r = sc.nextInt();
        int d = sc.nextInt();
        int count = 0;

        for (int i = l; i < r + 1; i++) {
            if (i % d == 0) {
                count++;
            }    
        }
        System.out.println(count);
    }
}

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

// auto mod int
int mod = 1000000007;
struct mint
{
    long long x;
    mint(long long x = 0) : x(x % mod) {}
    mint &operator+=(const mint a)
    {
        if ((x += a.x) >= mod)
            x -= mod;
        return *this;
    }
    mint &operator-=(const mint a)
    {
        if ((x += mod - a.x) >= mod)
            x -= mod;
        return *this;
    }
    mint &operator*=(const mint a)
    {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const
    {
        mint res(*this);
        return res += a;
    }
    mint operator*(const mint a) const
    {
        mint res(*this);
        return res *= a;
    }
    mint pow(long long t) const
    {
        if (!t)
            return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1)
            a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const
    {
        return pow(mod - 2);
    }
    mint &operator/=(const mint a)
    {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const
    {
        mint res(*this);
        return res /= a;
    }
};

// 箱根駅伝DPというらしい
// ペアを組んでいく問題で使う。保留したものを区別しなくてよい。
// 上からi段目
// j個保留
// スコアがk
// iが1進むとスコアkが j * 2増える。交換なので2倍。

mint dp[55][55][2605];
int main(void)
{
    int n, score;
    cin >> n >> score;
    dp[0][0][0] = 1;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i + 1; j++)
        {
            for (int k = 0; k < score + 1; k++)
            {
                { // i番目の数字は入れ替わりなし 〇-------〇
                    dp[i + 1][j][k + j * 2] += dp[i][j][k];
                }
                { // i番目の数字をともに保留 〇・ ・〇
                    dp[i + 1][j + 1][k + j * 2 + 2] += dp[i][j][k];
                }
                {                                                   // i番目の数字を過去に保留しているものと交換 〇---/ ・〇
                    dp[i + 1][j][k + j * 2] += dp[i][j][k] * j * 2; // 左右両方あるので2倍
                }
                { // i番目の数字を過去に保留しているものと交換 〇--/ \-〇
                    if (0 <= (j - 1))
                    {
                        dp[i + 1][j - 1][k + j * 2 - 2] += dp[i][j][k] * j * j;
                    }
                }
            }
        }
    }
    cout << dp[n][0][score].x << endl;
    return 0;
}

Measured memory_bytes: 61952
#include<iostream>
using namespace std;
 
int main(){
  int n,t,e;
  int x[100];
 
  cin >> n >> t >> e;
 
  for(int i=0;i<n;i++)cin >> x[i];
 
  for(int i=0;i<n;i++){
    int tmp = x[i];
    while(tmp<t-e)tmp += x[i];
    if(tmp<=t+e){
      cout << i+1 << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}

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

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)

using namespace std;

lli dp[201010];
int main(){

	lli n;
	cin>>n;
	vector<lli> p(n);
	REP(i,0,n)cin>>p[i];
	
	lli ans=0;
	REP(i,0,n){
		lli now = p[i];
		dp[now] = dp[now-1]+1;
		ans = max(ans,dp[now]);
	}

	cout<< n-ans<<endl;
	return 0;

}

Measured memory_bytes: 3328
#include <iostream>
#include <string>
#include<queue>
using namespace std;
class Proc{
public:
    string nam;
    int tim;
    Proc(){ nam=""; tim=0; }
};
int main()
{
    queue<Proc> que;
    int n, q;
    cin >> n >> q;
    for(int i=0; i<n; i++){ 
        Proc p; 
        cin >> p.nam >> p.tim;
        que.push(p);
    }
    int total_tim = 0;
    while(!que.empty()){ 
        Proc p = que.front(); que.pop();
        if(p.tim<=q){ 
            total_tim += p.tim;
            cout << p.nam << ' ' << total_tim << endl; 
        }else{ 
            total_tim += q;
            p.tim -= q;
            que.push(p); }
    }
    return 0;
}


Measured memory_bytes: 6280
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

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

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
const ll mod = 1e9 + 7;



int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  double tot = 0;
  double t = 1800*m+100*n;
  double p = pow(2, -m);
  // sum t * i * p * (1-p)^(i-1)
  REP(i, 1, 40 * 32) {
    tot += t * i * p * pow(1 - p, i - 1);
  }
  cout << tot << endl;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define forn(i,n) for(int i=0; i < int(n); ++i)
#define all(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back
#define fst first
#define snd second

const ll N = 1e5+20;

ll n, xs[N];

ll count(ll median) {
    ll countgt0 = 0;
    ll ans = 0;
    ll offset = 0;
    unordered_map<ll, ll> M;
    forn(i, n) {
        if (xs[i] >= median) {
            --offset;
            ++M[offset+1];
            countgt0 += M[offset] + 1;
        }
        else {
            ++offset;
            countgt0 -= M[offset-1];
            ++M[offset-1];
        }
        ans += countgt0;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    forn(i, n) cin >> xs[i];
    ll nn = 1ll*n*(n-1)/2 + n;
    ll lo = *min_element(xs, xs+n);
    ll hi = *max_element(xs, xs+n);
    while (lo < hi) {
        ll mid = (lo + hi + 1) / 2;
        if (2*count(mid) >= nn)
            lo = mid;
        else
            hi = mid - 1;
    }
    cout << lo << '\n';
}


Measured memory_bytes: 4516
//by Judge
#include<bits/stdc++.h>
#define P pair<int,int>
#define fp(i,a,b) for(register int i=(a),I=(b)+1;i<I;++i)
#define ll long long
using namespace std;
const int M=1e5+3;
#ifndef Judge
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
char buf[1<<21],*p1=buf,*p2=buf;
inline ll read(){ ll x=0,f=1; char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
} int n,cnt,q,f[M]; ll m; vector<P> e[2];
inline void ask(bool x){ if(x) printf("No\n"),exit(0); }
int find(int x){ return x^f[x]?f[x]=find(f[x]):x; }
inline ll Sum(int x){return 1ll*x*(x-1)/2;}
inline void merge(int x,int y){
	x=find(x),y=find(y); if(x^y) ++cnt,f[y]=x;
}
int main(){ n=read(),m=read(),q=read(); fp(i,1,n) f[i]=i; int x,y,c;
	fp(i,1,q) x=read()+1,y=read()+1,c=read(),e[c].push_back(P(x,y));
	for(auto x: e[0]) merge(x.first,x.second);
	for(auto x: e[1]) ask(find(x.first)==find(x.second));
	ll Mn=e[1].size()?n:n-1,Mx=cnt+Sum(n-cnt);
	return ask(m>Mx||m<Mn),!printf("Yes\n");
}

Measured memory_bytes: 3320
#include <atcoder/all>
#include <bits/stdc++.h>

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define rep(i, n) repd(i, 0, n)

using namespace std;

using ll = long long;
using ul = unsigned long long;
using ld = long double;
const ul mod = 1000000007;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, m;
    cin >> n >> m;
    atcoder::dsu d(n);

    rep(i, m) {
        ll a, b;
        cin >> a >> b;
        a--;
        b--;
        d.merge(a, b);
    }
    ll ans = 0;

    rep(i, n) {
        if (d.leader(i) == i) {
            ans++;
        }
    }
    ans--;
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3760
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a;
	cin>>a;
	int p=a;
	int sum=0;
	while(p>0)
	{
		sum+=p%10;
		p/=10;
	}
	if(a%sum==0)
		cout<<"Yes";
	else
		cout<<"No";
	return 0;
 } 

Measured memory_bytes: 256
n=int(input())
q=[list(map(int,input().split())) for _ in range(n)]
MAX=100010
p=[1]*MAX
p[0]=0;p[1]=0
for i in range(2,MAX):
  if not p[i]:continue
  for j in range(i*2,MAX,i):p[j]=0
a=[0]*MAX
for i in range(MAX):
  if i%2==0:continue
  if p[i] and p[int((i+1)/2)]:a[i]=1
s=[0]*(MAX+1)
for i in range(MAX):
  s[i+1]=s[i]+a[i]
for i in range(n):
  print(s[q[i][1]+1]-s[q[i][0]])

Measured memory_bytes: 32764
#include <iostream>

using namespace std;

int main()
{
  	bool ok = 1;
  	int n, x;
  	cin >> n;
  	for (int i = 1; i <= n; ++i)
    {
    	cin >> x;
      	if (x % 2 == 0 && !(x % 5 == 0 || x % 3 == 0))
        {
        	cout << "DENIED";
          	return 0;
        }
    }
  	cout << "APPROVED";
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define erep(i,N) for(int i = N; i >= 0; i--)
const ll INF = 1000000000;
const ll mod = 1000000007;
#define PI 3.1415926535
using Graph = vector<vector<int>>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true;} return false;}
typedef pair<int, int> pair;
bool seen[100000];
void dfs(const Graph &G, int v) {
    seen[v] = true; // v を訪問済にする
 
    // v から行ける各頂点 next_v について
    for (auto next_v : G[v]) { 
        if (seen[next_v]) continue; // next_v が探索済だったらスルー
        dfs(G, next_v); // 再帰的に探索
    }
}

//dpTable
int dp[100050];

int main(){
    int N;
    cin >> N;
    vector<int> L(N);
    rep (i,N) cin >> L.at(i);
    if (N < 3) cout << 0 << endl;
    else {
        sort(L.begin(),L.end());
        int ans = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                for (int k = j + 1; k < N; k++) {
                    if ((L.at(i) != L.at(j)) && (L.at(i) != L.at(k)) && (L.at(j) != L.at(k))) {
                        if ((L.at(i) + L.at(j)) > L.at(k)) ans++;
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 3620
n = int(input())
d,x = map(int,input().split())
a = [int(input()) for i in range(n)]
lst = []

for i in range(n):
  for j in range(1,101):
    tmp = j*a[i]+1
    if tmp > d:
      lst.append(j)
      break
      
      
print(sum(lst) + x)

Measured memory_bytes: 3060
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<map>
#include<bitset>
#include<iomanip>
#include<list>
#include <numeric>
using namespace std;
typedef unsigned long long int ulint;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define RE return 0
//ios::sync_with_stdio(false);
//std::cin.tie(0);
//<< setprecision(20)
const int mod=(int)1e9+7;
const llint big=(llint)(2.19e15+1);
const long double pai=3.141592653589793238462643383279502884197;
const long double ena=2.71828182845904523536;
const long double eps=1e-7;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
template <class T> void soun(T& ar)
{sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());}
llint gcd(llint a,llint b){if(a%b==0){return b;}else{return gcd(b,a%b);}}
llint lcm(llint a,llint b){return a/gcd(a,b) *b;}
template<class T,class U> auto LB(T& ve,U in){return lower_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto UB(T& ve,U in){return upper_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto LBI(T& ve,U in){return LB(ve,in)-ve.begin();}
template<class T,class U> auto UBI(T& ve,U in){return UB(ve,in)-ve.begin();}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
int main(void){
	int i,n;cin>>n;
	for(i=1;i<=n;i++){
		int x=i;
		bool aa=(i%3==0);
		while(x){if(x%10==3){aa=true;}x/=10;}
		if(aa){cout<<" "<<i;}
	}
	cout<<endl;
	RE;
}


Measured memory_bytes: 3096
#include <stdio.h>

int D,G;
int p[10];
int c[10];

int pow2(int n)  { return 1 << n;}

int main(){
	scanf("%d %d",&D,&G);
	for(int i = 0; i < 10; i++){
		p[i] = c[i] = 0;
	}
	for(int i = 0; i < D; i++){
		scanf("%d %d",p+i,c+i);
	}

	int mincnt = 100000;
	for(int n = 0; n < pow2(D); n++){
		int cnt = 0;
		int score = 0;
		// complete block
		for(int i = 0; i < D; i++){
			if(n & pow2(i)){
				score += c[i] + (i+1)*100*p[i];
				cnt   += p[i];
			}
		}	
		// non-complete block

		for(int i = D-1; i >= 0; i--){
			if(n & pow2(i) || p[i]==0) continue;

			if(G-score > (i+1)*100*(p[i]-1)){
				score += (i+1)*100*(p[i]-1);
				cnt   += p[i]-1;
			}else{
				if(G >= score){
					if( (G-score) % ((i+1)*100) == 0)
						cnt += (G-score)/ ((i+1)*100);
					else
						cnt += 1 + (G-score)/ ((i+1)*100);
					score += cnt*((i+1)*100);
				}else {}
				break;
			}
		}
		if(G > score) cnt = 10000;
		//printf("(n=%d, cnt=%d)\n",n,cnt);
		if (mincnt > cnt) mincnt = cnt;
	}
	printf("%d\n",mincnt);
}	

Measured memory_bytes: 128
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<map>
using namespace std;
int main()
{
	int a,b,c,t;
	cin>>a>>b>>c;
	if(a<b)
	{
		t=a;a=b;b=t;
	}
	if(a<c)
	{
		t=a;a=c;c=t;
	}
	if(b<c)
	{
		t=b;b=c;c=t;
	}
	cout<<a*10+b+c;
	return 0;
}


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

using namespace std;

const int INF = 100000000;

int main(){
    typedef pair<int,int> P;
    int H,W,i,j,n=0;
    
    scanf("%d%d", &H, &W);
    
    queue<P> que;
    char A[1000][1000];
    int d[1000][1000];
    for(i=0;i<H;i++) for(j=0;j<W;j++){
        scanf(" %c", &A[i][j]);
        d[i][j] = INF;
        if(A[i][j]=='#'){ 
            que.push(P(i,j));//黒点をキューに入れる
            d[i][j]=0;
        }
    }
    int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
    int ans = 0;
    while(que.size()){
        P p = que.front(); que.pop();
        //移動4方向をループ
        for(i=0;i<4;i++){
            //黒塗りにする点をnx,nyとする
            int ny = p.first + dy[i], nx = p.second + dx[i];

            //移動判定
            if(0<=nx && nx<W && 0<=ny && ny<H && A[ny][nx] != '#' && d[ny][nx] == INF){
                que.push(P(ny,nx));
                d[ny][nx] = d[p.first][p.second] + 1;
                ans = max(ans,d[ny][nx]);
            }
        }
    }
    printf("%d",ans);
}

Measured memory_bytes: 13328