akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
#define Priq priority_queue<int,vi,greater<int>>
#define pb push_back
#define mp make_pair
int N,A,B,C[100000];
int func(int X){
  int ret=0;
  rep(i,0,N) ret+=(max(0ll,(C[i]-B*X))+A-B-1)/(A-B);
  return ret;
}
signed main(){
  cin>>N>>A>>B;
  rep(i,0,N) cin>>C[i];
  int left=0,right=pow(10,10);
  while(left+1<right){
    int mid=(left+right)/2;
    if(func(mid)<=mid) right=mid;
    else left=mid;
  }
  int ans=right;
  if(func(left)<=left) ans=left;
  cout<<ans<<endl;
  }



Measured memory_bytes: 1024
#include<stdio.h>
main(){
  int temp,ww[100],i,w,n,a[100],b[100];
  scanf("%d %d",&w,&n);
  for(i=1;i<=w;i++){
    ww[i]=i;
  }
  for(i=1;i<=n;i++){
    scanf("%d,%d",&a[i],&b[i]);
  }
  for(i=1;i<=n;i++){
    temp=ww[a[i]];
    ww[a[i]]=ww[b[i]];
    ww[b[i]]=temp;    
  }
  for(i=1;i<=w;i++){
    printf("%d\n",ww[i]);
  }
  return 0;
}

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

using i64 = int64_t;

#define rep(i, x, y) for (i64 i = i64(x), i##_max_for_repmacro = i64(y); i < i##_max_for_repmacro; ++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf = 1.01e9;
const i64 inf64 = 4.01e18;
const double eps = 1e-9;

template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

template <typename T>
bool chmin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<typename T, size_t size> void fill(T (&ary)[size], const T& val){
    fill_n((T*)ary, size, val);
}

void solve() {
    //const i64 mod = 1'000'000'007;

    i64 N;
    cin >> N;

    vector<i64> A(N);
    rep(i,0,N) cin >> A[i];

    vector<vector<i64>> memo(N,vector<i64>(2,-inf64));
    vector<vector<bool>> done(N,vector<bool>(2,false));
    function<i64(i64,i64)> rec=[&](i64 i,i64 f){
        if(i==N) return i64(0);
        auto& res=memo[i][f];
        if(done[i][f]) return res;
        done[i][f]=true;

        i64 sgn=f==0?1:-1;
        {
            chmax(res,sgn*A[i]+rec(i+1,0));
        }
        {
            if(i+1<N) chmax(res,sgn*(-1)*A[i]+rec(i+1,1));
        }

        return res;
    };

    cout << rec(0,0) << endl;
}

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


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

using namespace std;
using ll = long long;

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

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

  vector<int> to[n];
  rep(i, n - 1) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    to[a].push_back(b);
    to[b].push_back(a);
  }

  vector<int> cnt(n);
  rep(i, nq) {
    int p, x;
    cin >> p >> x;
    --p;
    cnt[p] += x;
  }

  vector<int> ans(n), close(n);
  queue<int> q;
  q.push(0);

  while (!q.empty()) {
    int u = q.front();
    q.pop();
    close[u] = 1;
    ans[u] += cnt[u];

    for (auto v : to[u]) {
      if (close[v]) continue;
      cnt[v] += cnt[u];
      q.push(v);
    }
  }

  rep(i, n) printf("%d%c", ans[i], i == n - 1 ? '\n' : ' ');

  return 0;
}


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

using namespace std;

int main() {
	int A, B;
	cin >> A >> B;

	 if (A <= 8 && B <= 8) {
		cout << "Yay!" << endl;
	}
	else {
		cout << ":(" << endl;
	}

	return 0;
}

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

int main(){
  int a[3], n, mx;
  cin >> n;
  while(n--){
    cin >> a[0] >> a[1] >> a[2];
    mx = max(max(a[0],a[1]),a[2]);
    if(a[0]==mx)
      a[0]=0;
    else if(a[1]==mx)
      a[1]=0;
    else
      a[2]=0;
    if(mx*mx == a[0]*a[0]+a[1]*a[1]+a[2]*a[2])
      cout << "YES\n";
    else
      cout << "NO\n";
  }
  return 0;
}

Measured memory_bytes: 1124
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
ans = 0
for i in range(n):
    ans += b[i]

for i in range(n-1):
    if a[i+1] - a[i] == 1:
        ans += c[a[i]-1]

print(ans)

Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Linq;

class Progaram
{
    static void Main(string[] args)
    {
        var l = Console.ReadLine().Split(' ').Select(f => long.Parse(f)).ToArray();
        var x = l[0]; var y = l[1];
        var m = x;
        long res = 0;
        while (y >= m)
        {
            m = m * 2;
            res++;
        }
        Console.WriteLine(res);
    }
}

Measured memory_bytes: 13268
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class Main {


    public static void main(String[] args) throws IOException, InterruptedException {
        Scanner sc = new Scanner();
        PrintWriter out = new PrintWriter(System.out);
        int l = sc.nextInt();
       double ans = 1.0*l*l*l/27;
       out.println(ans);
        out.flush();
        out.close();
    }


    static class Scanner {
        BufferedReader br;
        StringTokenizer st;

        boolean ready() throws IOException {
            return br.ready();
        }

        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        Scanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        int nextChar() throws IOException {
            return next().charAt(0);
        }

        int[] nextIntArray(int n) throws IOException {
            int[] ans = new int[n];
            for (int i = 0; i < n; i++)
                ans[i] = nextInt();
            return ans;
        }

        long nextLong() throws IOException {
            return Long.parseLong(next());
        }

    }
}


Measured memory_bytes: 21204
#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()

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

int main(void) {
    int X, Y;
    cin >> X >> Y;

    bool flag = false;
    for (int a = 0; a <= X; ++a) {
        int t = a * 2 + (X - a) * 4;
        if (t == Y) {
            flag = true;
            break;
        }
    }

    if (flag) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 3620
import java.util.*;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Collections;

public class Main {
	public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        //ArrayList<Integer> list;
        List<Integer> list = new ArrayList<>();
        
        int number = sc.nextInt();
        int k = sc.nextInt(); 
        for(int i = 0; i < number ; i++){
            list.add(sc.nextInt());
        }

        Collections.sort(list);
        int min = number - k;
        long count = 0;
        if( min <= 0 ){
            System.out.println(count);
        }else{
            for(int i = 0; i<min; i++){
                count += list.get(i);
            }
            System.out.println(count);
        }
    
	}
}

Measured memory_bytes: 68208
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

using namespace std;
typedef long long int lli;
//const int MAX=;

int main(){
	int a,b;
	cin>>a>>b;
	int d=b-a;
	cout<<d*(d+1)/2-b;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define MAX 1000000007
using namespace std;


double calc_angle(double a, double b, double ang){
	double work;
	if(a == 0 && b == 0)return 0.0;
	if(b > 0) work = acos(a/sqrt(a*a+b*b));
	else work = -acos(a/sqrt(a*a+b*b));

	while(!(ang <= work && work <= ang+2*M_PI)){
		if(work < ang) work += 2*M_PI;
		else work -= 2*M_PI;
	}
	return work;
}

bool cmp(const pair<double,double> a, const pair<double,double> b){
	return calc_angle(a.first,a.second,0) > calc_angle(b.first,b.second,0);
}

int main(void){
	int n;
	cin >> n;
	vector<pair<double,double> > work(n);
	rep(i,n) cin >> work[i].first >> work[i].second;
	sort(work.begin(),work.end(),cmp);


	//rep(i,n)cout << work[i].first << " " << work[i].second << endl;
	double ans = 0;
	rep(i,n){
		double ang = calc_angle(work[i].first,work[i].second,0);
		//cout << "iter:" << i << endl;
		//cout << "x = " << work[i].first << " ,y = " << work[i].second << " ,angle= "<< ang << endl; 
		int j = (i-1+n)%n;
		double wx=work[i].first,wy=work[i].second;
		//cout << "check right:" << endl;
		//cout << "x = " << work[j].first << " ,y = " << work[j].second << " ,angle= "<< calc_angle(work[j].first,work[j].second,ang) << endl; 
		//cout << calc_angle(work[j].first,work[j].second,ang)-ang << endl;
		if(ans < sqrt(wx*wx+wy*wy))ans = sqrt(wx*wx+wy*wy);
		while(calc_angle(work[j].first,work[j].second,ang)-ang <= M_PI && i != j){
			wx += work[j].first;
			wy += work[j].second;
			j = (j-1+n)%n;
			//cout << "check right:" << endl;
			//cout << "x = " << work[j].first << " ,y = " << work[j].second << " ,angle= "<< calc_angle(work[j].first,work[j].second,ang) << endl; 
			//cout << calc_angle(work[j].first,work[j].second,ang)-ang << endl;
			if(ans < sqrt(wx*wx+wy*wy))ans = sqrt(wx*wx+wy*wy);
		}
		//cout << endl;


		j = (i+1)%n;
		//cout << "check left:" << endl;
		//cout << "x = " << work[j].first << " ,y = " << work[j].second << " ,angle= "<< calc_angle(work[j].first,work[j].second,ang-2*M_PI) << endl; 
		//cout << ang - calc_angle(work[j].first,work[j].second,ang-2*M_PI) << endl;
		wx = work[i].first;
		wy = work[i].second;
		while(ang - calc_angle(work[j].first,work[j].second,ang-2*M_PI) <= M_PI && i != j){
			wx += work[j].first;
			wy += work[j].second;
			j = (j+1)%n;
			//cout << "check left:" << endl;
			//cout << "x = " << work[j].first << " ,y = " << work[j].second << " ,angle= "<< calc_angle(work[j].first,work[j].second,ang-2*M_PI) << endl; 
			//cout << ang - calc_angle(work[j].first,work[j].second,ang-2*M_PI) << endl;
			if(ans < sqrt(wx*wx+wy*wy))ans = sqrt(wx*wx+wy*wy);

		}
		//cout << endl;
	}

	printf("%16.16f\n",ans);
	return 0;
}


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

int main() {
  int n;
  ll k;
  cin >> n >> k;
  vector<P> ab(n);
  rep(i,n) {
    int a, b;
    cin >> a >> b;
    ab[i]=make_pair(a,b);
  }
  sort(ab.begin(),ab.end());
  ll sum=0;
  for(auto p : ab) {
    sum+=p.second;
    if(sum>=k) {
      cout << p.first << endl;
      return 0;
    }
  }
}


Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<string>
#include<utility>
#include<array>
#include<set>
#include <numeric>
#include <stdio.h>
#include <map>
#include <iomanip>
#include <sstream>
//#include <boost/math/common_factor_rt.hpp>
#include<fstream>
#define EPS (1e-7)
using namespace std;
#define ll long long



class Employee {
public:
	int id;
	int parent;
	vector<int> children;
	int salary;

	Employee() {
		
	}

	Employee(int num, int nparent) {
		id = num;
		parent = nparent;
		salary = -1;
	}



};



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



int main() {

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

	int ls, lt;
	ls = s.size();
	lt = t.size();


	vector<int> inner(ls + 1, 0);
	vector<vector<int>> dp(lt + 1, inner);

	string ans = "";
	for (auto i = 0; i < lt; i++)
	{
		for (auto j = 0; j < ls; j++)
		{
			if (s[j] == t[i]) {
				dp[i + 1][j + 1] = dp[i][j] + 1;

			}
			else {
				dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);

			}
		}
	}
	int x = ls, y = lt;
	while (x > 0 && y > 0) {
		
		if (dp[y][x] == dp[y - 1][x]) {
			y--;
		}
		else if (dp[y][x] == dp[y][x - 1]) {
			x--;
		}
		else {
			ans += s[x-1];
			y--;
			x--;
		}


	}
	reverse(ans.begin(), ans.end());
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 35584
macro_rules! read( () => { read!("{}") }; ($text:expr) => {{ let value; scan!($text, value); value }}; ($text:expr, $input:expr) => {{ let value; scan!($input => $text, value); value }}; );
macro_rules! scan( ($text:expr, $($arg:ident),*) => { scan!(std::io::stdin().bytes().map(|c| c.unwrap()) => $text, $($arg),*) }; ($input:expr => $text:expr, $($arg:ident),*) => {{ use std::io::Read; use std::str::FromStr; /* typesafe macros :) */ let text: &'static str = $text; let stdin: &mut Iterator<Item = u8> = &mut ($input); let mut text = text.bytes(); $( loop { match text.next() { Some(b'{') => match text.next() { Some(b'{') => assert_eq!(Some(b'{'), stdin.next()), Some(b'}') => { let s: Vec<u8> = match text.next() { Some(c) => stdin.take_while(|&ch| ch != c).collect(), None => stdin.take_while(|ch| !b"\t\r\n ".contains(ch)).collect(), }; let s = match std::str::from_utf8(&s) { Ok(s) => s, Err(e) => { let n = e.valid_up_to(); if n == 0 { panic!("input was not valid utf8: {:?}", s); } else { panic!("input was only partially valid utf8: \"{}\" followed by {:?}", std::str::from_utf8(&s[..n]).unwrap(), &s[n..]); } } }; $arg = FromStr::from_str(s).expect(&format!("could not parse {} as target type of {}", s, stringify!($arg))); break; } Some(_) => panic!("found bad curly brace"), None => panic!("found single open curly brace at the end of the format string"), }, Some(c) => assert_eq!(Some(c), stdin.next()), None => panic!("Bad read! format string: did not contain {{}}"), } })* for c in text { assert_eq!(Some(c), stdin.next()); } }}; );

fn main() {
    let (a, b): (i32, i32);
    scan!("{} {}\n", a, b);

    let ans = if a <= 8 && b <= 8 { "Yay!" } else { ":(" };
    println!("{}", ans);
}


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

bool checkDigits(int n) {
  int result = 1;
  int tmp = n % 10;
  while (n > 0) {
    if (tmp != n % 10) {
      result = 0;
      break;
    }
    n /= 10;
  }
  return result;
}

int main() {
  int N, ans;
  cin >> N;
  for (int i = N; i < 1000; i++) {
    if (checkDigits(i)) {
      ans = i;
      break;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using st=string;
using ch=char;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<ch> vc;
typedef vector<vc> vvc;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(ll i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
#define pb push_back
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
st abc="abcdefghijklmnopqrstuvwxyz";
st ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct edge{ll to,cost;};
struct edge2{ll from,to,cost;};

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

ll pow_mod(ll x,ll y){
  if(y==0){
    return 1;
  }
  else if(y%2==0){
    ll t=pow_mod(x,y/2);
    return t*t%MOD;
  }
  else{
    return pow_mod(x,y-1)*x%MOD;
  }
}

int main() {
    int N;
    cin >> N;
    vl A(N),B(N);
    map<P,ll> p;
    rep(i,N){
        ll a,b;
        cin >> a >> b;
        if(a==0||b==0){
            if(a!=0){
                a=1;
            }
            else if(b!=0){
                b=1;
            }
        }
        else{
            ll x=gcd(a,b);
            a/=x;
            b/=x;
            if(a<0){
                a*=-1;
                b*=-1;
            }
        }
        A[i]=a;
        B[i]=b;
        p[{a,b}]++;
    }
    ll ans=1;
    ll Z=0;
    for(auto t:p){
        auto key=t.first;
        auto value=t.second;
        ll x0=key.first,x1=key.second;
        ll z;
        p[{x0,x1}]=0;
        if(value<=0){
            continue;
        }
        if(!(x0==x1&&x0==0)){
            if(x0*x1!=0){
                z=p[{abs(x1),-abs(x1)/x1*x0}];
                p[{abs(x1),-abs(x1)/x1*x0}]=0;
            }
            else if(x0==0){
                z=p[{1,0}];
                p[{1,0}]=0;
            }
            else{
                z=p[{0,1}];
                p[{0,1}]=0;
            }
            ans=ans*(pow_mod(2,z)+(ll)pow_mod(2,value)-1)%MOD;
        }
        else{
            Z=value;
            p[{0,0}]=0;
        }
    }
    cout << (MOD+ans+Z-1)%MOD << endl;
}


Measured memory_bytes: 31332
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String t = scanner.next();
        if (t.charAt(2) == t.charAt(3) && t.charAt(4) == t.charAt(5)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }

}

Measured memory_bytes: 21844
//
//  main.cpp
//  contest_code
//
//  Created by wubw555 on 2017/10/08.
//  Copyright © 2017年 wubw555. All rights reserved.
//
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <cassert>
#include <fstream>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

const ll mod = 1e9 +7;

vector<vector<long long>> warshall_floyd(const vector<vector<long long>>& dist)
{
    vector<vector<long long>> ret = dist;
    for (int i = 0; i < ret.size(); ++i)
    {
        for (int j = 0; j < ret.size(); ++j)
        {
            for (int k = 0; k < ret.size(); ++k)
            {
                ret[j][k] = min(ret[j][k], ret[j][i] + ret[i][k]);
            }
        }
    }
    return ret;
}

int main() {
    
    
    ll n, m, l;
    cin >> n >> m >> l;
    
    vector<vector<ll>> d(n, vector<ll>(n, mod));
    
    for (int i = 0; i < n; ++i)
    {
        d[i][i] = 0;
    }
    
    for (int i = 0; i < m; ++i)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        if (c <= l)
        {
            d[a][b] = c;
            d[b][a] = c;
        }
    }
    
    vector<vector<ll>> amd = warshall_floyd(d);
    vector<vector<ll>> sp(n, vector<ll>(n, mod));
    
    for (int i = 0; i < n; ++i)
    {
        sp[i][i] = 0;
    }
    
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (amd[i][j] <= l)
            {
                sp[i][j] = 1;
            }
        }
    }
    
    vector<vector<ll>> ms = warshall_floyd(sp);
    
    ll q;
    cin >> q;
    
    for (int i = 0; i < q; ++i)
    {
        ll s, t;
        cin >> s >> t;
        s--;
        t--;
        if (ms[s][t] < mod)
        {
            cout << ms[s][t] - 1 << endl;
        }
        else
        {
            cout << -1 << endl;
        }
    }
    
    
    return 0;
}



Measured memory_bytes: 3456
#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;

int main(){
	char s[200], p[100];
	int len;\
	cin >> s;
	cin >> p;
	
	len = strlen(s);
	for(int i = 0; i < len; i++){
		s[len+i] = s[i];
	}

	
	if(strstr(s, p) != NULL){
		cout << "Yes" << endl;
	}else {
		cout << "No" << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1144
N, K = map(int, input().split())
dp = [[[0]*N**2*3 for a in range(N+1)] for b in range(N+1)]

dp[0][0][0] = 1
for i in range(N):
    for j in range(N):
        for k in range(N**2):
            dp[i+1][j+1][k+2*j+2] += dp[i][j][k]
            dp[i+1][j][k+2*j] += dp[i][j][k] * (2*j+1)
            if j: dp[i+1][j-1][k+2*j-2] += dp[i][j][k] * j**2

print(dp[N][0][K] % (10**9+7))

Measured memory_bytes: 334088
using System;
using System.Collections.Generic;
using System.Linq;

namespace Test01
{
    class Program
    {
        static void Main(string[] args)
        {
            //入力1(N)
            int N = int.Parse(Console.ReadLine());
            //各ダムの水の量
            int[] dam = new int[N + 1];
            string[] input = Console.ReadLine().Split(' ');
            for (int i = 1; i <= N; i++) dam[i] = int.Parse(input[i - 1]);

            //mt[i] := i番目の山に降る雨の量
            int[] mt = new int[N + 1];

            //sum = b[1] + b[2] + ... b[N-1] + b[N]
            //b[i] + b[i + 1] = 2dam[i]
            //mt[1] = sum - 2(dam[2] + dam[4] + ... dam[N - 2] + dam[N])
            long sum = (long)dam.Select(x => (long)x).Sum();

            for (int i = 1; i <= N; i++) if (i % 2 == 0) sum -= 2 * dam[i];

            mt[1] = (int)sum;

            //b[1]から残りのbを求める
            for (int i = 2; i <= N; i++) mt[i] = 2 * dam[i - 1] - mt[i - 1];

            //表示
            Console.Write($"{mt[1]}");
            for (int i = 2; i <= N; i++) Console.Write($" {mt[i]}");
            Console.WriteLine();
        }
    }
}


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

int main() {
  int sum=0;
  string s;
  while(cin >> s) {
    int x=0;
    for(int i=0; i<s.size(); i++) {
      if(s[i]>='0' && s[i]<='9'){
	x*=10;
	x+=s[i]-'0';
      } else {
	sum+=x;
	x=0;
      }
    }
    sum+=x;
  }
  cout << sum << endl;
  return 0;
}


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

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

    rep(i, 8) {
        if (s.substr(0, i) + s.substr(s.size() + i - 7) == "keyence") {
            cout << "YES" << endl;
            return 0;
        }
    }

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define se second
#define fi first
#define ll long long
#define INF INT_MAX
#define mod 1000000007
#define chutiyaap ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
ll pw(ll a, ll b) {
    if (b == 0) return 1;
    ll t = pw(a, b / 2);
    if (b % 2 == 0) return (t * t)%mod;
    else return ((t * t)%mod * a)%mod;
}
int main()
{
	int n;cin>>n;
	string s;cin>>s;
	int ans=1;
	for(int i=1;i<n;i++){
		if(s[i]!=s[i-1])ans++;
	}
	cout<<ans<<"\n";
	return 0;
}


Measured memory_bytes: 3728
#include <bits/stdc++.h>
#define rep(i,a) for(int i=0;i<int(a);++i)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
using ll = long long;
using itn = int;
using namespace std;
using Graph = vector<vector<int>>;
int GCD(int a, int b){
    return b ? GCD(b, a%b) : a;
}
int main() {
	int N;
	cin>>N;
	map<char,int> S;
	rep(i,N){
		char tmp; cin>>tmp;
		S[tmp]++;
	}
	if(S.size()==3){
		cout << "Three" << endl;
	}else if(S.size()==4){
		cout << "Four" << endl;
	}
	return 0;
}

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

#define TABLE_SIZE 16777216
#define ORDER_LENGTH 7
#define STR_LENGTH 13

using namespace std;

int translateChar(char ch){
	int ret;
	switch(ch){
	case 'A':
		ret = 1;
		break;
	case 'C':
		ret = 2;
		break;
	case 'G':
		ret = 3;
		break;
	case 'T':
		ret = 4;
		break;
	}
	return ret;
}


int translateStr(char buf[]){
	int sum = 0;
	int mult = 1;
	for(int i = 0; buf[i] != '\0'; i++){
		sum += translateChar(buf[i])*mult;
		mult *= 4;
	}
	return sum - 1;
}

int main(){

	int n;
	scanf("%d",&n);
	char order[ORDER_LENGTH],str[STR_LENGTH];

	char* check_table = new char[TABLE_SIZE];

	for(int i = 0; i < n; i++){
		scanf("%s %s",order,str);
		if(strcmp(order,"insert") == 0){
			check_table[translateStr(str)] = 'Y';
		}else{
			if(check_table[translateStr(str)] == 'Y'){
				printf("yes\n");
			}else{
				printf("no\n");
			}
		}
	}

	delete[] check_table;
}

Measured memory_bytes: 4152
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main(){
    string s;
    cin>>s;
    int cnt=1;
    bool flg=false;
    for(int i=1;i<s.size();i++){
        if(s[i-1]==s[i]){
            cnt++;
        }else{
            cnt=1;
        }
        if(cnt>=3){
            flg=true;
        }
    }
    cout<<(flg?"Yes":"No")<<endl;
    return 0;
}

Measured memory_bytes: 3608
#include"iostream"
#include"cstdio"
#include"algorithm"


#define MAXN
using namespace std;
#define INF 0x7fffffff

int a[500];

int main()
{
	int n, x;
	cin >> n >> x;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a + 1, a + 1 + n);
	int ans = 0;
	for(int i = 1; i <= n; i++)
	{
		if(i == n)
		{
			if(x == a[i])
				ans++;
			continue;
		}
		if(a[i] <= x)
		{
			ans++;
			x -= a[i];
		}
		else
			break;
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int w,h;
string s;
main(){
  cin>>h>>w;
  for(int i=0;i<w+2;i++)cout<<"#";
  cout<<endl;
  for(int i=0;i<h;i++)
  {
    cin>>s;
    cout<<"#"<<s<<"#"<<endl;
  }
  for(int i=0;i<w+2;i++)cout<<"#";
  cout<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define endl "\n"
using namespace std;

int32_t main() {

    fast

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

    int maxLen = 0;
    int j;
    for(int i = 0; i < s.size(); i++) {
        int curr = 0;
        for(j = 0; j < t.size() && i + j < s.size(); j++) {
            if(s[i + j] == t[j]) {
                curr++;
            }
        }
        if(j == t.size())
            maxLen = max(maxLen, curr);
    }
    cout << (t.size() - maxLen);


    return 0;
}



Measured memory_bytes: 3644
#include<bits/stdc++.h>
#define maxn 500010
#define N 2000000
#define ll long long
#define mod 1000000007
using namespace std;
int val[maxn], sum[maxn], f[maxn], res[2][N], nxt[maxn], h[N];
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &val[i]);
		val[i] ^= val[i - 1];
	}
	for (int i = n; i >= 1; i--)
	{
		nxt[i] = h[val[i]];
		h[val[i]] = i;
	}
	for (int i = 1; i <= n; i++)
		sum[i] = sum[i - 1] + (val[i] == 0);
	for (int i = n; i >= 1; i--)
	{
		if (val[i] == 0) continue;
		if (nxt[i] == 0)
		{
			if (val[n] == 0) f[i] = 1;
			else if (i == n) f[i] = 1;
		}
		else
		{
			f[i] = (res[1][val[i]] - (ll)res[0][val[i]] * sum[i] % mod + mod) % mod;
			if (val[n] == 0) f[i] = (f[i] + 1) % mod;
		}
		res[0][val[i]] = (res[0][val[i]] + f[i]) % mod;
		res[1][val[i]] = (res[1][val[i]] + (ll)f[i] * sum[i] % mod) % mod;
	}
	int res = 0;
	for (int i = 1; i <= n; i++)
		res = (res + f[i]) % mod;
	if (val[n] == 0)
	{
		int tmp = sum[n - 1], cur = 1;
		for (int i = 1; i <= tmp; i++)
			cur = (ll)cur * 2 % mod;
		res = (res + cur) % mod;
	}
	printf("%d\n", res);
	return 0;
}

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

int main() {
  int n,jud = 0,d1,d2;
  cin >> n;
  
  for(int i = 0; i < n;i++){
    cin >> d1 >> d2;
    
    if(d1 == d2){
      jud++;
    }else{
      jud = 0;
    }
    if(jud == 3) break;
  }
  
  if(jud == 3){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3620
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
int cnt[2005][2005];
int ans[2005];
int vis[2005];
struct node
{
    int p, val;
    node() {}
    node(int p, int val) : p(p), val(val) {}
    // bool operator<(const node &b)
    // {
    //     return this->val > b.val;
    // }
    friend bool operator<(node a, node b)
    {
        return a.val > b.val;
    }
};
int s, n, x, y;
void bfs()
{
    priority_queue<node> q;
    q.push(node(s, 0));
    memset(vis, 0, sizeof(vis));
    while (!q.empty())
    {
        node now = q.top();
        q.pop();
        if (vis[now.p])
            continue;
        vis[now.p] = 1;
        ans[now.val]++;
        if (now.p - 1 >= 1)
            q.push(node(now.p - 1, now.val + 1));
        if (now.p + 1 <= n)
            q.push(node(now.p + 1, now.val + 1));
        if (now.p == x)
            q.push(node(y, now.val + 1));
        if (now.p == y)
            q.push(node(x, now.val + 1));
    }
}
int main()
{

    cin >> n >> x >> y;
    for (int i = 1; i <= n; i++)
    {
        s = i;
        bfs();
    }
    for (int i = 1; i <= n - 1; i++)
        cout << ans[i] / 2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#define ll long long 
using namespace std;
int main()
{
  ll s,first,sec,third,fourth;
  cin>>s;
  first = s/1000;
  sec = (s/100)%10;
  third = (s/10)%10;
  fourth = s%10;
  if(first==sec||sec==third||third==fourth)
    cout<<"Bad";
  else
    cout<<"Good";
  return 0;
}

Measured memory_bytes: 384
#include<iostream>
using namespace std;
int main(int a,int b, int c) {
    cin >> a >> b >> c;
    if(a <= b) {
        if(c <= a) {
            cout << c << " " << a << " " << b << endl;
        }
        else if(b <= c){
            cout << a << " " << b << " " << c << endl;
        }
        else {
            cout << a << " " << c << " " << b << endl;
        }
    }
    else {
        if(a <= c){
            cout << b << " " << a << " " << c <<endl;
        }
        else if(c <= b){
            cout << c << " " << b << " " << a <<endl;
        }
        else {
            cout << b << " " << c << " " << a << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3116
# include <iostream>
# include <cstring>
# include <string>
# include <vector>
# include <cmath>
# include <sstream>
# include <iomanip>
# include <algorithm>
using namespace std;

# define repl(i, a, b)	for(int i=(int)(a);i<(int)(b);i++)
# define rep(i, n)	repl(i, 0, n)
typedef long long ll;

int main(){
	cin.sync_with_stdio(false);
	ll h, w, n;
	cin >> h >> w >> n;

	pair<int, int> bl[100001];
	vector<pair<int, int> > v;
	ll out[10];

	rep(i, n){
		cin >> bl[i].first >> bl[i].second;
		bl[i].first--;
		bl[i].second--;
	}

	rep(i, n){
		ll bly = bl[i].first;
		ll blx = bl[i].second;
		for(int dx=-2 ; dx <= 0 ; dx++){
			for(int dy=-2 ; dy <= 0 ; dy++){
				ll nx = blx + dx;
				ll ny = bly + dy;
				if(nx >= 0 && ny >= 0 && nx+2 < w && ny+2 < h){
					v.push_back(make_pair(ny, nx));
				}
			}
		}
	}
	sort(v.begin(), v.end());
	int prev = 0, next = 0;
	while(next < v.size()){
		while(next < v.size() && v[prev] == v[next])next++;
		out[next-prev]++;
		prev = next;
	}
	out[0] = (w-2)*(h-2);
	repl(i, 1, 10)
	out[0] -= out[i];

	rep(i, 10){
		cout << out[i] << endl;
	}
	return 0;

}

Measured memory_bytes: 9324
import sys

x, n, *ppp = map(int, sys.stdin.buffer.read().split())
ppp = set(ppp)

if len(ppp) == 0:
    print(x)
    exit()

s = min(ppp)
t = max(ppp)

ans = s - 1
y = abs(x - ans)
for z in range(s, t + 2):
    if z in ppp:
        continue
    d = abs(x - z)
    if d < y:
        ans = z
        y = d

print(ans)


Measured memory_bytes: 9128
#include <iostream>
#include <string>
#include <vector>

using namespace std;
string a[7] = {
  "Monday",
  "Tuesday",
  "Wednesday",
  "Thursday",
  "Friday",
  "Saturday",
  "Sunday"};
int main(void){
  int aa,b;
  int mon[12] = {31,29,
		 31,30,
		 31,30,
		 31,31,
		 30,31,
		 30,31};
  while(cin>>aa>>b,aa+b){
    int d = b;
    for(int i = 0 ; i < aa-1 ; i ++){
      d += mon[i];
      //cout<<d<<endl;
    }
    
    cout<<a[(d+2)%7]<<endl;
  }
  //*/
}

Measured memory_bytes: 1192
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define N  99999
#define f first 
#define em emplace
#define s second
using lint=long long int;

typedef pair<lint, lint> pii;
typedef pair<double, double> pdd;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<string> vs;
using ll= long long ;
 
#define fori(n) for(int i=0; i<int(n); i++)
 
#define cins(s) string s; cin>>s;
#define cini(i) lint i; cin>>i;
#define cind(d) double d; cin>>d;
#define cinai(a, n) vi a(n); fori(n) { cin>>a[i]; }
#define cinas(s, n) vs s(n); fori(n) { cin>>s[i]; }
#define cinad(a, n) vd a(n); fori(n) { cin>>a[i]; }
#define z 1000000007 
const ll INF=1e18+5;

void solve(){
  
   cini(n); cini(w);
   vector<lint> dp(100002,INF);

   dp[0]=0;
   

   fori(n){

       lint weight; cin>>weight; lint value; cin>>value;

      for(lint j=100001;j>=value;j--){

          dp[j]=min(dp[j],dp[j-value]+weight);
      }
   }
   for(int j=100001;j>=0;j--)
    if(dp[j]<=w) { cout<<j<<endl; break;}
 }


   
    

 
 
int main()
{ 
  fast;

  



  solve();
 }

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

#define rep(i,n) for(int i=0;i<n;i++)
#define mkp make_pair
#define F first
#define S second

int main(){
	int n;
	int m;
	// int a[40]={0};
	while(cin>>n,n){
		vector<pair<char,char> > v;
		rep(i,n){
			char t1,t2;
			cin>>t1>>t2;
			v.push_back(mkp(t1,t2));
		}
		cin>>m;
		rep(i,m){
			char t;
			cin>>t;
			rep(i,n){
				if(v[i].F==t){
					t=v[i].S;
					break;
				}
			}
			cout<<t;
		}
		cout<<endl;
	}
	return 0;
}

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

int main()
{
	int n, k;
	cin >> n >> k;
	int x[n];
	for (int i = 0; i < n; ++i)
	{
		cin >> x[i];
	}
	
	int sum = 0;
	for (int i = 0; i < n; ++i)
	{
		sum += 2 * min(x[i], k - x[i]);
	}
	
	cout << sum << endl;
	
	return 0;
}


Measured memory_bytes: 256
#Educational DP Contest
#I-Coins

n = int(input())
lst1 = list(map(float,input().split()))

#dp table
dp = [[0.0]*(n+1) for _ in range(n+1)] #確率を0で初期化(2次元)
dp[0][0] = 1.0 #0番目は存在しないので1で初期化(単位元のような感じ。乗算だから単位元は1)


#process1
#dp[i][j]は、i回までのコインを投げて、j枚が表の確率。
#つまり、ループの内側がn回表の確率、外側がコインの枚数となる
#但し、i回までのコインでi枚以上の表は出ないので、jのループはi迄とする。
"""
図にするとこんなかんじ
    0回表,1回表,2回表...
0枚目[[1.0, 0.0, 0.0, 0.0],
1枚目[0.7, 0.3, 0.0, 0.0], #0.7で1枚中0枚が表,0.3で1枚中1枚が表
2枚目[0.28, 0.54, 0.18, 0.0],
3枚目[0.056, 0.33, 0.468, 0.144]] #0.056+0.33で半分未満が表、0.468+0.144で半分以上が表
"""
for i in range(1,n+1):
    for j in range(i+1): #jはピラミッド状に増えていく
        dp[i][j] = dp[i-1][j]*(1-lst1[i-1]) #裏になる確率
        if j > 0: #j-1を参照できるなら
            dp[i][j] += dp[i-1][j-1]*lst1[i-1] #表になる確率

#output process
#問題はdp[i][j] >= 0.5となる確率なので、j>= 0.5 = 表の枚数/全体の枚数
#となるj以上の確率の合計が答え(ちなみに、任意のdp[i]の合計sum(dp[i]) == 1となる)
ans = 0.0
for i in range((n+1)//2,n+1): #j(表が出る枚数)が半分以上のところから全部のところまでの確率の合計
    ans += dp[-1][i]
print(ans)

Measured memory_bytes: 111708
#include <cstdio>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define all(a) (a).begin(), (a).end()

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int N, K;
int p[200010], S[200010];

int getSum( int l, int r )
{ return S[r]-S[l]; }

int main()
{
  scanf( "%d%d", &N, &K );
  rep( i, N )
    scanf( "%d", p+i ), ++p[i];

  rep( i, N )
    S[i+1] = S[i]+p[i];

  int ans = 0;
  rep( i, N-K+1 )
    chmax( ans, getSum( i, i+K ) );

  printf( "%.11f\n", ans/2.0 );

  return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define no_solution {cout << "0\n"; return 0;}

using namespace std;

const int Mod = 1e9 + 7, Nmax = 2e5 + 5;
typedef long long ll;

int n, i, cnt, x, y, edge[Nmax], X, Y, w[Nmax], forbx, forby;
bool used[Nmax], root[Nmax];
vector<int> v[Nmax], comp, before[Nmax];
ll dp[Nmax], fact[Nmax], ifact[Nmax], ans = 1;

ll power(ll a, int b)
{
    if(!b) return 1;
    if(b&1) return a * power(a*a%Mod, b/2) % Mod;
    return power(a*a%Mod, b/2);
}

void dfs(int node, int dad = 0)
{
    cnt += 2;
    cnt -= v[node].size();
    used[node] = 1;
    comp.push_back(node);

    for(auto it : v[node])
        if(!used[it]) dfs(it, node);
            else if(it != dad) X = node, Y = it;
}

void Clear()
{
    before[0].clear(); edge[0] = -1;
    for(auto it : comp) before[it].clear(), root[it] = 1, edge[it] = 0;
}

void select(int node)
{
    for(auto it : v[node])
        if(it == edge[node]) break;
            else before[node].push_back(it), root[it] = 0;

    for(auto it : v[node])
        if(!edge[it] && !(node == forbx && it == forby))
        {
            edge[it] = node;
            select(it);
        }
}

int comb(int n, int k)
{
    return fact[n] * ifact[k] % Mod * ifact[n-k] % Mod;
}

void answer(int node)
{
    dp[node] = 1;
    if(before[node].empty())
    {
        w[node] = 1;
        return;
    }

    w[node] = 0;
    for(auto it : before[node]) answer(it);

    for(auto it : before[node])
    {
        dp[node] = dp[node] * dp[it] % Mod * comb(w[node] + w[it], w[it]) % Mod;
        w[node] += w[it];
    }

    ++w[node];
}

ll solve(int x, int y)
{
    forbx = x, forby = y;
    Clear();
    edge[x] = y;
    select(x);

    for(auto it : comp)
        if(root[it]) before[0].push_back(it);
    answer(0);
    return dp[0];
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    cin >> n;
    for(i=1; i<=2*n; ++i)
    {
        cin >> x >> y; y += n;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    for(i=1; i<=2*n; ++i) sort(v[i].begin(), v[i].end());

    fact[0] = ifact[0] = 1;
    for(i=1; i<=2*n; ++i) fact[i] = fact[i-1] * i % Mod;
    ifact[2*n] = power(fact[2*n], Mod-2);
    for(i=2*n-1; i; --i) ifact[i] = ifact[i+1] * (i+1) % Mod;

    int what = 0;
    for(i=1; i<=2*n; ++i)
        if(!used[i])
        {
            comp.clear();
            dfs(i);
            if(cnt) no_solution;

            ans *= (solve(X, Y) + solve(Y, X));
            ans %= Mod;
            ans *= comb(what + comp.size(), comp.size());
            ans %= Mod;
            what += comp.size();
        }

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


Measured memory_bytes: 32632
class UnionFind:
    def __init__(self, n):
        self.nodes = n
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
        self.rank = [0] * n

    def find(self, i): # どの集合に属しているか（根ノードの番号）
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i]) # 経路圧縮
            return self.parents[i]

    def unite(self, i, j): # 二つの集合を併合
        pi = self.find(i)
        pj = self.find(j)
        if pi != pj:
            if self.rank[pi] < self.rank[pj]:
                self.sizes[pj] += self.sizes[pi]
                self.parents[pi] = pj
            else:
                self.sizes[pi] += self.sizes[pj]
                self.parents[pj] = pi
                if self.rank[pi] == self.rank[pj]:
                    self.rank[pi] += 1
    def same(self, i, j): # 同じ集合に属するかを判定
        return self.find(i)==self.find(j)

    def get_parents(self): # 根ノードの一覧を取得
        for n in range(self.nodes): # findで経路圧縮する
            self.find(n)
        return self.parents

adj = []
N, M = map(int,input().split())
for m in range(M):
    a,b = map(int,input().split())
    adj.append([a-1,b-1])

ans = 0
for i in range(M): # 取り除く辺番号
    uf = UnionFind(N)
    for j in range(M):
        if (i==j): # 辺を追加しない（取り除く）
            continue
        uf.unite(*adj[j])
    
    if len(set(uf.get_parents()))!=1: # 複数の集合にわかれているか確認
        ans += 1
print (ans)

Measured memory_bytes: 9304
#include<bits/stdc++.h>
using namespace std;
#define all(v) ((v).begin()),((v).end())
#define ll long long
#define fastIO cout << fixed << setprecision(9), ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
double const EPS = 1e-9, PI = acos(-1);
const int N = 1e5 + 9, M = 5e2 + 9, OO = 1e9 + 7, MOD = 1e9 + 7;
const ll inf = 1e18;

ll dp[N], arr[N];

ll add(ll a, ll b) {
  a += b;
  if(a >= MOD)
    a -= MOD;
  if (a < 0)
    a += MOD;
  return a;
}

int main() {
  fastIO;
#ifdef LOCAL
  freopen("input.in", "rt", stdin);
#endif
  int n, k, x;
  cin >> n >> k;
  dp[0] = 1;
  for (int i = 0; i < n; ++i) {
    cin >> x;
    memset(arr, 0, sizeof arr);
    for (int j = k; j >= 0; --j) {
//      for (int l = min(x, k - j); l >= 1; --l)
//        dp[l + j] = add(dp[l + j], dp[j]);
      int L = 1 + j, R = min(x, k - j) + j, val = dp[j];
      if(L <= R && val)
        arr[L] = add(arr[L], val), arr[R + 1] = add(arr[R + 1], -val);
    }
    for (int j = 1; j <= k; ++j)
      arr[j] = add(arr[j], arr[j - 1]);
    for (int j = 0; j <= k; ++j)
      dp[j] = add(dp[j], arr[j]);

  }
  cout << dp[k];
  return 0;
}


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

int main(){
  int N;cin >> N;
  vector<int> S;
  while(1){
    if(N%2==0){
      S.push_back(0);
    }else{
      S.push_back(1);
      N = N - 1;
    }
    N = N / (-2);
    if(N==0){
      for(int i=S.size()-1;i>=0;i--){
        cout << S[i];
      }
      cout << endl;
      return 0;
    }
  }
}

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

using namespace std;


int main()
{
  int M, N;
  int X1[100], Y1[100], X2[100], Y2[100];

  while(cin >> M >> N, M) {
    vector< int > nums;
    for(int i = 0; i < M; i++) cin >> X1[i] >> Y1[i];
    for(int i = 0; i < N; i++) cin >> X2[i] >> Y2[i];
    for(int i = 0; i < M; i++) nums.push_back(X1[i]);
    for(int i = 0; i < N; i++) nums.push_back(X2[i]);
    sort(begin(nums), end(nums));
    nums.erase(unique(begin(nums), end(nums)), end(nums));
    int a = max(*min_element(X1, X1 + M), *min_element(X2, X2 + N));
    int b = min(*max_element(X1, X1 + M), *max_element(X2, X2 + N));
    double ret = 0;

    auto f = [](int *x, int *y, int sz, double v)
    {
      double small = 1e9, large = -1e9;
      for(int i = 0; i < sz; i++) {
        int xx = x[i], yy = y[i];
        int nx = x[(i + 1) % sz], ny = y[(i + 1) % sz];
        if(xx != nx && (xx - v) * (nx - v) <= 0) {
          double vv = yy + (ny - yy) * (v - xx) / (nx - xx);
          small = min(small, vv);
          large = max(large, vv);
        }
      }
      return (max(0.0, large - small));
    };

    for(int i = 1; i < nums.size(); i++) {
      int left = nums[i - 1], right = nums[i];
      double mid = (left + right) * 0.5;
      if(a <= mid && mid <= b) {
        double aa = f(X1, Y1, M, left) * f(X2, Y2, N, left);
        double bb = f(X1, Y1, M, right) * f(X2, Y2, N, right);
        double cc = f(X1, Y1, M, mid) * f(X2, Y2, N, mid);
        ret += (right - left) / 6.0 * (aa + bb + 4.0 * cc);
      }
    }
    cout << fixed << setprecision(10) << ret << endl;
  }
}

Measured memory_bytes: 3304
#include<iostream>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip>//setprecision
#include<math.h>
#include <functional>
#include<climits>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i)
int main(){ 
  int a,b=0,e,d=0;cin>>a;
  rep(i,a){
    b+=(i+1);
    if(b>=a){
      d=i+1;
      break;
    }
  }
  cout<<d;
}


Measured memory_bytes: 256
#include <iostream>
#include<algorithm>
#include<utility>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
const ll MAX_N=1e5,MAX_Q=1e5;
ll N,Q,psm[MAX_N];
char S[MAX_N+1];
int main(){
    scanf("%lld %lld",&N,&Q);
    scanf("%s",S);
    REP(i,N-1){
        psm[i+1]=psm[i]+(S[i]=='A' && S[i+1]=='C');
    }
    REP(i,Q){
        ll l,r;
        scanf("%lld %lld",&l,&r);
        cout<<psm[r-1]-psm[l-1]<<endl;
    }
}


Measured memory_bytes: 1664
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
	    int H = sc.nextInt();
	    int W = sc.nextInt();
	    
	    for (int i=0; i<H; i++){
	    	String S = sc.next();
	    	System.out.println(S);
	    	System.out.println(S);
	    }
	    sc.close();
	}

}


Measured memory_bytes: 24532
n = input()

intn = int(n)

if len(n) == 1:
    print(intn)
elif len(n) == 2:
    print("9")
elif len(n) == 3:
    print(intn - 100 + 1 + 9)
elif len(n) == 4:
    print(900+9)
elif len(n) == 5:
    print(intn - 10000+ 1 + 900 +9)
else:
    print("90909")

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

int h, w, k;
vector<string> c;

int main() {
    cin >> h >> w >> k;
    c.resize(h);
    for (int i = 0; i < h; i++) {
        cin >> c.at(i);
    }

    int res = 0;

    for (int bit_i = 0; bit_i < (1 << h); bit_i++) {
        for (int bit_j = 0; bit_j < (1 << w); bit_j++) {
            int num_black = 0;
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (!(bit_i & (1 << i)) && !(bit_j & (1 << j)) && c.at(i).at(j) == '#') {
                        num_black++;
                    }
                }
            }
            if (num_black == k) res++;
        }
    }

    cout << res << endl;
}

Measured memory_bytes: 3632
#include<stdio.h>
#include<math.h>
int main()
{
    long long int n,d,x,y,count=0,i,j;
    double k;
    scanf("%lld %lld",&n,&d);
    for(i=0;i<n;i++){
        scanf("%lld %lld",&x,&y);
        k=sqrt((x*x)+(y*y));
        if(k<=d)
            count++;
    }
    printf("%d\n",count);
    return 0;
}


Measured memory_bytes: 2104
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();
        char[] ch = sc.next().toCharArray();
        for (int i = a - 1 ; i < c - 1 ; i++) {
            if (ch[i] == '#' && ch[i + 1] == '#') {
                System.out.println("No");
                return;
            }
        }
        for (int i = b - 1 ; i < d - 1 ; i++) {
            if (ch[i] == '#' && ch[i + 1] == '#') {
                System.out.println("No");
                return;
            }
        }

        if (c > d) {
            for (int i = b - 1 ; i < d; i++) {
                if (ch[i - 1] == '.' && ch[i] == '.' && ch[i + 1] == '.') {
                    System.out.println("Yes");
                    return;
                }
            }
            System.out.println("No");
            return;
        }

        System.out.println("Yes");

    }

}


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

typedef long long ll;
typedef pair<ll,ll> P;
ll N,x;
ll A[2001];
ll C[2001][2001];
P D[2001][2001];

int main(){
	cin >> N >> x;
	for(int i=0;i<N;i++){
		cin >> A[i];
		C[0][i] = A[i];
	}
	for(int k=1;k<N;k++){
		for(int i=0;i<N;i++){
			C[k][i] = min(A[(i-k+N)%N],C[k-1][i]);
		}
	}
	ll ans = 1e18;
	for(int k=0;k<N;k++){
		ll now = 0;
		for(int i=0;i<N;i++){
			now += C[k][i];
		}
		ans = min(ans,x*k + now);
	}
	cout << ans << endl;
}

Measured memory_bytes: 32640