akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long ll;

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

const int MAX_V = 1000;

int V;
bool G[MAX_V][MAX_V];
int match[MAX_V];
bool used[MAX_V];

bool dfs(int v) {
	used[v] = true;
	for(int i = 0; i < V; i++) {
		if(!G[v][i]) continue;
		int u = i, w = match[u];
		if(w < 0 || (!used[w] && dfs(w))) {
			match[v] = u;
			match[u] = v;
			return true;
		}
	}
	return false;
}

int bipartite_matching() {
	int res = 0;
	memset(match, -1, sizeof(match));
	for(int v = 0; v < V; v++) {
		if(match[v] < 0) {
			memset(used, 0, sizeof(used));
			if(dfs(v)) {
				res++;
			}
		}
	}
	return res;
}

int b[500];
int r[500];

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

	int m, n;
	while(cin >> m >> n, m + n) {
		for(int i = 0; i < m; i++) {
			cin >> b[i];
		}
		for(int i = 0; i < n; i++) {
			cin >> r[i];
		}
		V = m + n;
		memset(G, 0, sizeof G);
		for(int i = 0; i < m; i++) {
			for(int j = 0; j < n; j++) {
				if(gcd(b[i], r[j]) > 1) {
					G[i][j + m] = G[j + m][i] = true;
				}
			}
		}

		cout << bipartite_matching() << endl;
	}
}

Measured memory_bytes: 4156
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
#define int long long
#define pb push_back
#define fi first
#define se second
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define all(x) x.begin(), x.end()
#define IO ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define sz(x) (int)x.size()
const int mod = 1e9 + 7;
const int mod1 = 998244353;
typedef long double f80;

#ifndef LOCAL
#pragma GCC optimize ("O2")
#define endl '\n'
#endif

template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r){
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}

ll pwr(ll a,ll b, ll mod){
    a %= mod;
    int ans = 1;
    while(b){
        if(b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

string to_string(string s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

void solve(){
	int n;
	cin >> n;
	int ans = 0;
	for(int i = 1; i * i <= n; i++){
		if(n % i == 0){
			int m = i - 1;
			if(m != 0 && n % m == (n / m))
				ans++;
			m = (n / i) - 1;
			if(m != 0 && n % m == (n / m))
				ans += m;
		}
	}
	cout << ans;
}
signed main(){
    IO;
    #ifdef LOCAL
        freopen("inp.txt","r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    cout << setprecision(10) << fixed;
    int t = 1;
    // cin >> t;
    fr(tt, 1, t){
        solve();
    }
    return 0;
}

Measured memory_bytes: 256
// Problem : A - Connection and Disconnection
// Contest : AtCoder - AtCoder Grand Contest 039
// URL : https://atcoder.jp/contests/agc039/tasks/agc039_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
using namespace std; 
#define ll long long int
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>
#define INF LLONG_MAX
#define PI acos(-1)
const ll MOD = 1e9 + 7;
#define fir first
#define sec second
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(c,a,b) for(ll c=a;c<b;c++)
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define min_heap priority_queue<pll,vector<pll>,greater<pll> >
ll dx4[]={-1,1,0,0};
ll dy4[]={0,0,-1,1};
ll dx8[]={-1,-1,-1,0,1,1,1,0};
ll dy8[]={-1,0,1,1,1,0,-1,-1};
bool isvalid(ll x,ll y,ll n,ll m)
{
    return (x>=0 and y>=0 and x<n and y<m);
}
ll isprime[1000];
vector<ll> prime;
void sievetoprime(ll n)
{
    mem(isprime,true);
    for(ll p=2;p*p<=n;p++)
    {
        if(isprime[p]==true)
        {
            for(ll i=p*p;i<=n;i+=p)
                isprime[i]=false;
        }
    }
}
ll lcm(ll a,ll b)
{
    return (a/__gcd(a,b))*b;
}
void solve()
{
    string s;
    cin>>s;
    ll k;
    cin>>k;
    ll n=s.size();
    string str="";
    str+=s[0];
    ll ans=0;
    vector<ll> v;
    rep(i,1,n)
    {
    	if(s[i]!=s[i-1])
    	{
    		v.pb(str.size());
    		ans=ans+(str.size())/2;
    		str=s[i];
    	}
    	else
    		str+=s[i];
    }
    ans=ans+(str.size())/2;
    v.pb(str.size());
    bool ok=0;
    if(s[0]==s[n-1] and v.size()>1)
    {
    	ans=ans*k;
    	ans=ans-((v[0]/2)+(v[v.size()-1]/2))*(k-1);
    	ans=ans+((v[0]+v[v.size()-1])/2)*(k-1);
    	ok=1;
    	cout<<ans;
    	return;
    }
    if(v.size()==1)
    {
    	cout<<(k*n)/2;
    	return;
    }
    
    cout<<ans*k;
}
int main()
{
    ll inpoup = 0;
    if(inpoup==1)
    {
        #ifndef ONLINE_JUDGE
            freopen("input.txt","r",stdin);
            freopen("output.txt","w",stdout);
        #endif
    }
    IOS
    ll t;
    t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>//sort,reverse
#include<utility>//pair
#include<queue>//queue,priority_queue
#include<deque>//double_ended queue
#include<map>//map
using namespace std;
typedef long long LL; 
typedef pair<LL,LL> P;//Pでpair<-,->を表す。
const LL MAX=2000010;
const LL MOD=1000000007;
typedef map<LL,LL>::iterator Itr;

int atoi(char c){
    return c-'a';
}

int main()
{ 
    LL n,Q;
    string s;
    cin>>n;
    cin>>s;
    cin>>Q;
    map<LL,LL> m[26];
    vector<int> ans;
    for(int i=0;i<n;i++){
        m[atoi(s[i])].insert(P(i,0));
    }
    for(int i=0;i<Q;i++){
        int a;
        cin>>a;
        if(a==1){
            int b;
            char c;
            cin>>b>>c;
            b=b-1;
            m[atoi(s[b])].erase(b);
            m[atoi(c)].insert(P(b,0));
            s[b]=c;
        }
        else{
            int b,c;
            cin>>b>>c;
            b=b-1;c=c-1;
            int cnt=0;
            for(int i=0;i<26;i++){
                if(!m[i].empty()){
                    if(m[i].lower_bound(b)!=m[i].upper_bound(c)){
                        cnt++;
                    }
                }
            }
            ans.push_back(cnt);
        }
    }
    reverse(ans.begin(),ans.end());
    while(!ans.empty()){cout<<ans.back()<<endl;ans.pop_back();}
    return 0;
}

Measured memory_bytes: 32260
#include<stdio.h>
 
int main()
{
  int N,M,i,a;
 
  scanf("%d",&N);
  scanf("%d",&M);
  
  for(i=0;i<M;i++){
    scanf("%d", &a);
    N-=a;
  }
  
  if(N>=0)
    printf("%d",N);
  else
    printf("-1");
  
  return 0;
}

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

int op[32][32];
int dist[32][32][4];
int c[4];

struct State {
	int i, j, dir, dist;
	const bool operator<(const State& s) const {
		return dist > s.dist;
	}
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	for (;;) {
		int w, h; cin >> w >> h;
		if (!w && !h) break;
		
		// reset
		rep(i, 0, 32) rep(j, 0, 32) op[i][j] = -1;
		rep(i, 0, 32) rep(j, 0, 32) rep(k, 0, 4) dist[i][j][k] = 999999;

		rep(i, 0, h) rep(j, 0, w) cin >> op[i][j];
		rep(i, 0, 4) cin >> c[i];

		priority_queue<State> pq;
		dist[0][0][0] = 0;
		pq.push(State {0, 0, 0, 0});

		while (!pq.empty()) {
			State st = pq.top(); pq.pop();
			if (st.dist > dist[st.i][st.j][st.dir])
				continue;
			for (int dd = 0; dd < 4; dd++) {
				int ndir = (st.dir + dd) % 4;
				int cost = op[st.i][st.j] != dd ? c[dd] : 0;
				int ni = st.i + dir[ndir][0], nj = st.j + dir[ndir][1];
				if (0 <= ni && ni < h && 0 <= nj && nj < w && st.dist + cost < dist[ni][nj][ndir]) {
					//printf("(%d, %d, %d) -> (%d, %d, %d) = %d\n", st.i, st.j, st.dir, ni, nj, ndir, st.dist + cost);
					dist[ni][nj][ndir] = st.dist + cost;
					pq.push(State {ni, nj, ndir, st.dist + cost});
				}
			}
		}

		int ans = 9999999;
		rep(i, 0, 4) ans = min(ans, dist[h - 1][w - 1][i]);
		cout << ans << endl;
	}
}



Measured memory_bytes: 3308
#include<bits/stdc++.h>
const int maxn = 1e2 + 5;
using namespace std;

int n,x1,x2;
char s[maxn];

int main(){
	scanf(" %s", s + 1);
	n = strlen(s + 1);
	x1 = (n - 1) / 2;
	x2 = (n + 3) / 2;
	bool flag = 1;
	for(int i = 1; i <= x1; i++){
		if(s[i] != s[x1 - i + 1]) flag = 0;
	}
	for(int i = x2; i <= n; i++){
		if(s[i] != s[n - i + 1]) flag = 0;
	}
	if(flag) printf("Yes");
	else printf("No");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for(int i=0; i<n; i++)
#define rep2(i, s, e) for(int i=s; i<e; i++)
#define print(i) cout << i << endl;

int main(){

    int n; cin >> n;

    ll ans = 0;
    rep(i, n-1){
        ans += i+1;
    }

    cout << ans;

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int n,i,x;
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    if(i%3==0){
      printf(" %d",i);
	}else{
      x=i;
      while(x>0){
	if(x%10==3){
	  printf(" %d",i);
	  x=0;
	}
	x=x/10;
    }
 
 }
  }
  printf("\n");
  return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
    cin>>n;
    int temp,count=0;
    unordered_map<int,int>mp;
    for(int i=0;i<n;i++)
    {
        cin>>temp;
        mp[temp]++;
    }
    for(auto itr= mp.begin();itr != mp.end();itr++) 
    {
        if(itr->first != itr->second)
        {
            if(itr->second>itr->first)
                count += (itr->second-itr->first);
            else
                count += itr->second;
        }
            
    }
    cout<<count<<endl;
}

Measured memory_bytes: 7124
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <functional>
#include <queue>
#include <unordered_set>
#include <climits>
#include <set>
#include <list>
#include <cmath>
#include <map>

using namespace std;
typedef long long ll;

int main()
{
	ll N, M, Q;
	static ll L[200000];
	static ll R[200000];
	static ll p[200000];
	static ll q[200000];
	cin >> N >> M >> Q;
	for(int i = 0; i < M; i++){
		cin >> L[i] >> R[i];
	}
	for(int i = 0; i < Q; i++){
		cin >> p[i] >> q[i];
	}
	
	ll Section[502][502];
	ll SectionSum[502][502];
	for(int i = 0; i <= N+1; i++){
		for(int j = 0; j <= N+1; j++){
			Section[i][j] = 0;
			SectionSum[i][j] = 0;
		}
	}
	
	for(int i = 0; i < M; i++){
		Section[L[i]][R[i]]++;
	}
	
	for(int i = 0; i <= N+1; i++){
		for(int j = 1; j <= N+1; j++){
			SectionSum[i][j] = SectionSum[i][j-1] + Section[i][j];
		}
	}
	
	// 計算量：O(Q*N)
	for(int query = 0; query < Q; query++){
		ll ans = 0;
		for(int i = p[query]; i <= q[query]; i++){
			// i からスタートして、i〜q[query]までの区間で終わる列車の総和 をi=p[query]〜q[query]まで足す
			ans += SectionSum[i][q[query]] - SectionSum[i][i-1];
		}
		cout << ans << endl;
	}
	
	return 0;
}

Measured memory_bytes: 10368
#include <iostream>
  #include <complex>
  #include <vector>
  #include <string>
  #include <algorithm>
  #include <cstdio>
  #include <numeric>
  #include <cstring>
  #include <ctime>
  #include <cstdlib>
  #include <set>
  #include <map>
  #include <unordered_map>
  #include <unordered_set>
  #include <list>
  #include <cmath>
  #include <bitset>
  #include <cassert>
  #include <queue>
  #include <stack>
  #include <deque>
 #include <iomanip>
 
  using namespace std;
   

//abcdefghijklmnopqrstuvwxyz
//ABCDEFGHIJKLMNOPQRSTUVWXYZ
  typedef long long ll;
  typedef long double lld;
//   typedef string str;
//   typedef unsigned long long ull;
  ll INF = INT_MAX;
  ll mod = 1000000007;
  // lld PI = 3.141592653;

// const int N = 2e5 + 5;

// int a[N];
// int n,k;
  
 

  int main()
  {
      ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 int n;
 cin>>n;
 set<string> a;
 while(n--){
  string s;
  cin>>s;
  a.insert(s);
 }
 cout<<a.size()<<endl;

}
  

Measured memory_bytes: 15584
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
using namespace std;
namespace mp = boost::multiprecision;
#define rep(i,n) for (int i=0; i<(int)(n); ++i)
#define rep0(i,n) for (int i=0; i<=(int)(n); ++i)
#define rep1(i,n) for (int i=1; i<=(int)(n); ++i)
#define rrep(i,n) for (int i=(int)(n)-1; i>=0; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using Graph = vector<vi>;
using llGraph = vector<vl>;
using vb = vector<bool>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int MOD = 1e9+7;
const int MOD2 = 998244353;
const double EPS = 1e-9;

template<typename T>
struct is_vector : false_type{};

template<typename T>
struct is_vector<vector<T>> : true_type{};

template<typename T>
ostream &operator << (ostream &ostr, const vector<T> &vec) {
  if (vec.empty()) {
    return ostr;
  }
  ostr << vec.front();
  for (auto itr = ++vec.begin(); itr != vec.end(); ++itr) {
    if (is_vector<T>()) ostr << "\n" << *itr;
    else ostr << ' ' << *itr;
  }
  return ostr;
}

template<typename T>
bool CompareBySecond(pair<T, T> a, pair<T, T> b) {
  if (a.second != b.second) {
    return a.second < b.second;
  } else {
    return a.first < b.first;
  }
}

template<typename T>
bool CompareBySlope(pair<T, T> a, pair<T, T> b) {
// counterclockwise from 12 o'clock direction
  if (a.first * b.first < 0) {
    return a.first < b.first;
  }
  if (a.first == 0) {
    if (a.second >= 0) {
      return true;
    }
    return a.first < b.first;
  }
  if (b.first == 0) {
    if (b.second >= 0) {
      return false;
    }
    return a.first < b.first;
  }
  return a.second * b.first < a.first * b.second;
}

template<typename T>
T GCD(T a, T b) {
  T c = a % b;
  while (c != 0) { a = b; b = c; c = a % b; }
  return b;
}


/* -------- <templates end> -------- */


struct edge {
  int from, to, color, idx;
};

void solve() {
  int n; cin >> n;
  vector<edge> Tree(n-1);
  Graph G(n);
  int idx = 0;
  for (auto &v : Tree) {
    int a, b; cin >> a >> b; --a; --b;
    v.from = a; v.to = b; v.idx = idx++;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  sort(ALL(Tree), [](const edge &a, const edge &b) {
    if (a.from == b.from) {
      return a.to < b.to;
    }
    return a.from < b.from;
  });

  size_t k = 0;
  rep(i,n) k = max(k, G[i].size());

  vi parent(n);
  parent[0] = 0;
  idx = 0;

  rep(i,n) {
    rep1(j,n) {
      if (idx == n-1 || Tree[idx].from != i) break;
      if (parent[i] == j) continue;
      Tree[idx].color = parent[Tree[idx].to] = j;
      ++idx;
    }
  }

  sort(ALL(Tree), [](const edge &a, const edge &b) {
    return a.idx < b.idx;
  });

  cout << k << "\n";
  rep(i,n-1) cout << Tree[i].color << "\n";
}


/* -------- <programs end> -------- */


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


Measured memory_bytes: 7936
#include <cstdio>
#include <cstring>
#define ll long long int
ll mabs(ll x)
{
	if(x<0) return -x;
	return x;
}
ll X, K, D, ans;
int main()
{
	scanf("%lld%lld%lld", &X, &K, &D);
	if(X<0)
	    X = -X;
	if(X>=0)
	{
		ll k = (X/D)+1;
		ll a = X-k*D, b = X-k*D+D;    //k步到a (k-1)步到b 
//		printf("xiaok = %lld\n", k);
		if(K>=k)
		{
			K -= k;
			if(K%2==0)
		    	printf("%lld\n", mabs(a));
		    else
		        printf("%lld\n", mabs(b));
		}
		else
		{
			printf("%lld\n", X-K*D);
		}
	}
/*	else///////
	{
		X = -X;
		ll k = (X/D)+1;
		ll a = X-k*D, b = X-k*D+D;
		if(K>=k)
		{
			K -= k;
			if(K%2==0)
		    	printf("%lld\n", mabs(a));
		    else
		        printf("%lld\n", mabs(b));
		}
		else
		{
			printf("%lld\n", X-K*D);
		}
	}*/
	return 0;
}

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

using namespace std;


int main (void) 
{

  int a, b; // input
  int sur;
  int x;    // output

  cin >> a >> b;

  sur = (a+b) %2;
  x   = (a+b) /2;
  if(sur == 1)
  {
    x += 1;
  }

  cout << x << endl;

  return 0;

}

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

int main(){
	int p1,p2,p3,j1,j2,pm,jm;
	pm=jm=2100;
	cin>>p1>>p2>>p3>>j1>>j2;
	pm=min(pm,p1);
	pm=min(pm,p2);
	pm=min(pm,p3);
	jm=min(jm,j1);
	jm=min(jm,j2);
	cout<<pm+jm-50<<endl;
	return 0;
}


Measured memory_bytes: 3076
#include<iostream>    
#include<cstdio>  
#include<stdio.h>  
#include<cstring>    
#include<cstdio>    
#include<climits>    
#include<cmath>   
#include<vector>  
#include <bitset>  
#include<algorithm>    
#include <queue>  
#include<map> 
#define inf 9999999; 
using namespace std;

int a[105],i,n;
int main()
{
	cin>>n;
	for(i=1;i<=n;i++)
		cin>>a[i];
	sort(a+1,a+1+n);
	cout<<a[n]-a[1]<<endl;
}

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



int main() {
    int N, M;
    cin >> N >> M;
    
    vector<int> h(N);
    // 1dame
    vector<int> hi(N);

    for(int i = 0; i < N; i++) {
        cin >> h.at(i);
    }
    
    for(int i = 0; i < M; i++) {
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        
        if(h.at(a) > h.at(b))
            hi.at(b) = 1;
        else if(h.at(a) < h.at(b))
            hi.at(a) = 1;
        else
            hi.at(a) = hi.at(b) = 1;
    }
    
    int cnt = 0;
    for(int i = 0; i < N; i++) {
        if(hi.at(i) == 0)
            cnt++;
    }
    
    cout << cnt << endl;
    
    return 0;
}


Measured memory_bytes: 4048
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <map>
#include <queue>
#include <cmath>
#include <iomanip>
#include <functional>

#define MOD (1000000007)

using namespace std;

typedef long long ll;
typedef pair<ll, ll> tup;
const int MAX = 510000;

long long fac[MAX], finv[MAX], inv[MAX];


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


// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; 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;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

map<ll,ll> prime;//素因数分解でそれぞれの素数がいくつ出てきたかを保存するmap

//O(√n)
//整列済み(mapはkeyで自動で整列される)
void prime_factorize(ll n){
    if(n<=1) return;
    ll l=sqrt(n);
   for(ll i=2;i<=(ll)(l);i++) { //
        if(n%i==0){
        prime_factorize(i);prime_factorize(ll(n/i));return;
        }
    }
    //mapでは存在しないkeyの場合も自動で構築される
    prime[n]++;return;
}


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

    string S;
    cin >> S;

    vector<bool> RL(N, false);
    vector<bool> LR(N, false);
    ll RLCount = 0, LRCount = 0, LastR = 0, FirstL = 0, LastL = 0, FirstR=0;
    ll current_happiness = 0;
    for(int i = 1; i < N; i++) {
        if(S[i] == S[i-1]) current_happiness++;
        if(S[i] == 'L' && S[i-1] == 'R') {
            RL[i-1] = true;
            RLCount++;
        }
        if(S[i] == 'R' && S[i-1] == 'L') {
            LR[i-1] = true;
            LRCount++;
        }
    }
    if(S[N-1] == 'R') LastR=1;
    else LastL = 1;
    if(S[0] == 'L') FirstL=1;
    else FirstR = 1;

    ll firstSwap = min(K, min(LRCount, RLCount));
    current_happiness += firstSwap * 2;

    if(K-firstSwap > 0) {
        current_happiness += max(min(RLCount - firstSwap, LastL + FirstR), min(LRCount - firstSwap, LastR + FirstL));
    }

    //cout << current_happiness << "," << LRCount << "," << RLCount << endl;
    //cout << current_happiness + min(K, min(LRCount, RLCount)) * 2 + min({LastR + FirstL ,LRCount - min(LRCount, RLCount), K - min(LRCount, RLCount)});
    cout << current_happiness << endl;

    return 0;    
}



Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define RFOR(i,a,b) for(int i=(b-1); i>=(a); i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define pb push_back
using ll = long long;
using D = double;
using LD = long double;
using P = pair<int, int>;
const int mod = 1e9+7;
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; }

int main(){
    int a,b; cin >> a >> b;
    rep(i,2000){
        if(i*8/100 == a && i/10 == b){
            cout << i << endl;
            return 0;
        }
    }
    cout << "-1" << endl;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;


public class Main {
	static int[] numStack = new int[100];
	static int numOfs= 0;
	static ArrayList<String> strList = new ArrayList<String>();
	static ArrayList<Integer> intList = new ArrayList<Integer>();

	public static void main(String[] args) throws Exception {
		BufferedReader breader = getReader();
		int[] elm = getIntAry(breader);
		int num = elm[0];
		int quantum = elm[1];
		for(int i = 0 ; i < num ; i++ ) {
			String[] ps = getAry(breader);
			strEnqueue(ps[0]);
			intEnqueue(Integer.valueOf(ps[1]));
		}
		String ps = strDequeue();
		int elapse = 0;
		while( ps != null) {
			int ms = intDequeue();
			if ( ms > quantum ) {
				strEnqueue(ps);
				intEnqueue(ms-quantum);
				elapse += quantum;
			} else {
				elapse += ms;
				System.out.println(ps + " " + elapse);
			}
			ps = strDequeue();
		}
	}
	public static void strEnqueue(String str) {
		strList.add(str);
	}
	public static void intEnqueue(int num) {
		intList.add(num);
	}
	public static String strDequeue() {
		String val;
		if ( strList.size() > 0 ) {
			val = strList.get(0);
			strList.remove(0);
		} else {
			val = null;
		}
		return val;
	}
	public static int intDequeue() {
		int val;
		if ( intList.size() > 0) {
			val = intList.get(0);
			intList.remove(0);
		} else {
			val = -1;
		}
		return val;
	}
	public static void numPush(int n) {
		numStack[numOfs++] = n;
	}
	public static int numPop() {
		return(Integer.valueOf(numStack[--numOfs]));
	}
	public static BufferedReader getReader() {
		return( new BufferedReader(new InputStreamReader(
				System.in)));
	}
	public static int getInt(BufferedReader br)throws Exception {
		String line = br.readLine();
		return Integer.valueOf(line);
	}
	public static String[] getAry(BufferedReader br)throws Exception {
		String line = br.readLine();
		String[] nstr = line.split(" ");
		return nstr;
	}
	public static int[] getIntAry(BufferedReader br)throws Exception {
		String line = br.readLine();
		String[] nstr = line.split(" ");
		int[] n = new int[nstr.length];
		for( int i=0 ; i < nstr.length ; i++ ) {
			n[i] = Integer.valueOf(nstr[i]);
		}
		return n;
	}
	public static int cardComp(String left, String right) {
		char l = left.charAt(1);
		char r = right.charAt(1);
		return(l-r);
	}
	public static int[] getAryMl(BufferedReader br)throws Exception {
		int n = getInt(br);
		int[] ary = new int[n];
		for( int i=0 ; i < n ; i++ ) {
			ary[i] = getInt(br);
		}
		return ary;
	}
	public static void putAry(int[] ary, int num) {
		for( int i = 0; i < num ; i++ ) {
			System.out.print(ary[i]);
			if ( i < num-1) {
				System.out.print(" ");
			}
		}
		System.out.println("");
	}
	public static void putAry(int[] ary) {
		putAry(ary, ary.length ) ;
	}
	public static boolean isPrime(int n) {
		int r = (int)Math.sqrt((double)n)+1;
		for( int j = 2 ; j < r ; j += 1) {
			if ( n%j == 0 ) {
				return false;
			}
		}
		return true;
	}

}

Measured memory_bytes: 61944
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;


int main(){
  ll A;
  string SB;
  cin >> A >> SB;

  ll B = (SB[0]-'0') * 100 + (SB[2]-'0') * 10 + (SB[3]-'0');

  ll AB = A*B / 100;

  cout << AB << endl;
  return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> using vt = vector<T>;
template<class T> using vvt = vector<vt<T>>;
template<class T> using ttt = tuple<T,T>;
using tii = tuple<int,int>;
using vi = vector<int>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define mt make_tuple
#define ALL(a) (a).begin(),(a).end()
#define FST first
#define SEC second
#define DEB cerr<<"!"<<endl
#define SHOW(a,b) cerr<<(a)<<" "<<(b)<<endl
#define DIV int(1e9+7)
const int INF = (INT_MAX/2);
const ll LLINF = (LLONG_MAX/2);
const double eps = 1e-8;
const double PI = M_PI;  
inline ll pow(ll x,ll n,ll m){ll r=1;while(n>0){if((n&1)==1)r=r*x%m;x=x*x%m;n>>=1;}return r%m;}
inline ll lcm(ll d1, ll d2){return d1 / __gcd(d1, d2) * d2;}

/* Coding Space*/
int main(){
  int n,k,x,y; cin >> n >> k >> x >> y;
  ll ans = 0;
  for(int i = 1; i <= n; i++){
    if(i <= k)
      ans += x;
    else
      ans += y;
  }
  cout << ans << endl;
}

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


int main() {
	int N;
    cin>>N;
    double dp[N+1][N+1][N+1];
    memset(dp,0.0,sizeof(dp));
    vector<int> count(4,0);
    for (int i=0;i<N;i++){
    	int x;
    	cin>>x;
    	count[x]++;
    }
    int max_ones=count[1]+count[2]+count[3];
    int max_twos=count[2]+count[3];
    int max_threes=count[3];
    int i=0,j=0,k=0;
    for (int c=0;c<=max_threes;c++){
    	for(int b=0;b<=max_twos-c;b++){
    		for (int a=0;a<=max_ones-b-c;a++){
    			if (a+b+c==0) continue;
    			double n=a+b+c;
    			dp[a][b][c]=(double)N/n;
    			if (a>0) {
    				dp[a][b][c]=dp[a][b][c]+(dp[a-1][b][c]*(double)a)/n;
    			}
    			if (b>0) {
    				dp[a][b][c]=dp[a][b][c]+(dp[a+1][b-1][c]*(double)b)/n;
    			}
    			if (c>0) { 
    				dp[a][b][c]=dp[a][b][c]+(dp[a][b+1][c-1]*(double)c)/n;
    			}
    			i=a,j=b,k=c;
       		}
    	}
    }
	cout<< setprecision(16)<<dp[i][j][k]<<endl;
    return 0; 
}


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

typedef long long ll;

int main()
{
    ll n;
    cin >> n;
    ll i,j;
    string first = "a";
    queue<pair<string,int>> que;
    que.emplace(first,0);
    vector<string> ans;
    while(!que.empty()){
        string s = que.front().first;
        if(s.size() == n){
            ans.push_back(s);
            que.pop();
            continue;
        }
        int num = que.front().second;
        for(i = 0;i <= num+1;++i){
            
            string new_s = s + (char)(97 + i);
            if(i != num+1){
                que.emplace(new_s, num);
            }else{
                que.emplace(new_s, num+1);
            }
        }
        que.pop();
    }
    sort(ans.begin(),ans.end());
    for(i = 0;i < ans.size();++i){
        cout << ans.at(i) << endl;
    }
    return 0;
}

Measured memory_bytes: 9852
import itertools
import math

N = int(input())
Fac = math.factorial(N)
x = []
y = []
X = []
Y = []
leng = []
tmp = 0
for i in range(N):
    tmp = list(map(int,input().split()))
    x.append(tmp[0])
    y.append(tmp[1])
for i in itertools.permutations(x):
    X.append(i)
for i in itertools.permutations(y):
    Y.append(i)
for i in range(Fac):
    try:
        leng.append(((((X[i][0]-X[i][1]) ** 2) + ((Y[i][0]-Y[i][1]) ** 2)) ** 0.5))
    except:
        pass
tmp = 0
for i in range(Fac):
    tmp += leng[i]
tmp *= (N-1)
ans = tmp / Fac
print(ans)

Measured memory_bytes: 49904
const teststr = 
"""
33
"""

function lines()
  Channel{String}(32) do ch
	ll = readlines()
    lines = isempty(ll) ? split(teststr, "\n") : ll
    for s in lines
      put!(ch, s)
    end
  end
end

function main()
  ch = lines()
  X = parse(Int, take!(ch))
  maxA = 10^10
  for A in (x for absx in 0:maxA for x in (absx, -absx))
    B5 = A^5 - X
    Bf = Float64(abs(B5))^(1.0/5)
    B5 < 0 && (Bf = -Bf)
    B = round(Int, Bf)
    if A^5 - B^5 == X
      println("$A $B")
      exit(0)
    end
  end
end

main()
      

Measured memory_bytes: 189224
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace テスト
{
    class Program
    {
        static void Main(string[] args)
        {
            int N, i, x;

            var word = Console.ReadLine().Split(' ');
            N = int.Parse(word[0]);
            i = int.Parse(word[1]);

            x = N+1-i;
            Console.WriteLine(x);
            Console.ReadLine();

        }
    }
}

Measured memory_bytes: 13140
// ※※※ 解答不能 ※※※
// alkhwarizmi氏.
// https://atcoder.jp/contests/keyence2020/submissions/14501140
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int a[20], b[20];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    rep(i, N) scanf("%d", &b[i]);
    
    // 2. 初期化.
    vvi dp(N, vi(1 << N, 1e9));
    rep(i, N) dp[i][1 << i] = 0;
    
    // 3. dp更新.
    rep(mask, 1 << N){
        int p = __builtin_popcount(mask);
        rep(i, N){
            int x = (i % 2 == (p - 1) % 2) ? a[i] : b[i];
            rep(j, N){
                if(mask & (1 << j)) continue;
                int y = (j % 2 == p % 2) ? a[j] : b[j];
                if(x > y) continue;
                dp[j][mask | (1 << j)] = min(dp[j][mask | (1 << j)], dp[i][mask] + __builtin_popcount(mask >> j));
            }
        }
    }
    
    // 4. 最小値取得.
    int ans = 1e9;
    rep(i, N) ans = min(ans, dp[i][(1 << N) - 1]);
    if(ans > 1e8) ans = -1;
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 22780
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>
#include <functional>
#include <vector>
#include <iomanip>
#include <numeric>
using namespace std;

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

	string ans = "Alice";
	
	if ((A - B) % 2 != 0)
	{
		ans = "Borys";
	}
	
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<string>
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<map>
using namespace std;
typedef long long int llint;
#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
const int mod=1000000007;
const llint big=1e18+10;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-9;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
int gcd(int a,int b){if(a%b==0){return b;}else return gcd(b,a%b);}//a>b
class in_t{public:
	int a;in_t(){cin>>a;}
	operator int() {return a;}
};
class lin_t{public:
	llint a;lin_t(){cin>>a;}
	operator llint() {return a;}
};
class ld_t{public:
	long double a;ld_t(){cin>>a;}
	operator long double() {return a;}
};
int main(void){
	in_t n;
	string str;cin>>str;
	str.pub(str[0]);
	//o->SSS,WSW
	string ans;
	ans.res(n+2);
	for(int ba=0;ba<4;ba++){
		if(ba==0){ans[0]='S',ans[1]='S';}
		if(ba==1){ans[0]='S',ans[1]='W';}
		if(ba==2){ans[0]='W',ans[1]='S';}
		if(ba==3){ans[0]='W',ans[1]='W';}
		for(int i=1;i<=n;i++){
			int bi=0;
			if(ans[i-1]=='W'){bi++;}
			if(ans[i]=='W'){bi++;}
			if(str[i]=='x'){bi++;}
			if(bi%2==0){ans[i+1]='S';}
			else{ans[i+1]='W';}
		}
		if(!(ans[0]==ans[n]&&ans[1]==ans[n+1])){continue;}
		ans.pob();ans.pob();
		cout<<ans<<endl;return 0;
	}
	cout<<"-1"<<endl;
	return 0;
}


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

using namespace std;

int main(){
	int n; scanf("%d", &n);
	bool cek = 0;
	int haha;
	while(n > 0){
		haha = n % 10;
		if(haha == 9){
			cek = 1; break;
		}
		n/=10;
	}
	if(cek) printf("Yes\n");
	else printf("No\n");
	return 0;
}

Measured memory_bytes: 256
N = int(input())
masu = list(map(int, input().split()))
cnt = 0
masu2 = []
for i in range(N-1):
    if masu[i] < masu[i+1]:
        masu2.append(cnt)
        cnt = 0
    else:
      cnt += 1
else:
  masu2.append(cnt)
print(max(masu2))

Measured memory_bytes: 14252
N = int(input())
buttons = []
for i in range(N) :
    buttons.append(int(input()))

push_index = 1
push_count = -1
count = 0
for i in range(N) :
    push_index = buttons[push_index-1]
    count += 1
    if (push_index == 2) :
        push_count = count
        break

print(push_count)

Measured memory_bytes: 7084
#include <iostream>
#include <string>

using namespace std;

int main() {
  int H, W;
  string line;
  cin >> H >> W;
  cout << string(W+2, '#') << endl;
  for (int h = 0; h < H; ++h) {
    cin >> line;
    cout << '#' << line << '#' << endl;
  }
  cout << string(W+2, '#') << endl;
  
  return 0;
}


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

int straight(int card[])
{
	for(int i=1; i<9; i++){
		if(((card[0]==i)&&(card[1]==i+1)&&(card[2]==i+2)&&(card[3]==i+3)&&(card[4]==i+4)) || 
			(card[0]==1&&card[1]==10&&card[2]==11&&card[3]==12&&card[4]==13))
			return 1;
	}
	return 0;
}

int main(){
	int c[5], n;
	char k;

	while(1){
		cin>>c[0]>>k>>c[1]>>k>>c[2]>>k>>c[3]>>k>>c[4];
		if(cin.eof())break;
		n=0;
		sort(c, c+5);

		for(int i=0; i<4; i++){
			for(int j=i+1; j<5; j++){
				if(c[i]==c[j])
					n++;
			}
		}
		switch(n){
			case 1:
				cout<<"one pair\n";
				break;
			case 2:
				cout<<"two pair\n";
				break;
			case 3:
				cout<<"three card\n";
				break;
			case 4:
				cout<<"full house\n";
				break;
			case 6:
				cout<<"four card\n";
				break;
			case 10:
				cout<<"four card\n";
				break;
			default:
				if(straight(c))
					cout<<"straight\n";
				else
					cout<<"null\n";
				break;
		}
	}

	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<math.h>
#include<map>
using namespace std;
using ll = long long;
int main() {
    int n;
    cin >> n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    int count = 0;
    for(int i=1;i<=n;i++){
        if(i % 2 != 0 && a[i] % 2 != 0){
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 3620
n = int(input())
a = [int(i) for i in input().split()]

a.sort(reverse=True)
ans = a[0]

tmp = n-2

for i in range(n):
    if tmp == 0:
        break
    if tmp >= 2:
        ans += a[i+1]*2
        tmp -= 2
    elif tmp == 1:
        ans += a[i+1]
        tmp -= 1
    #print(ans,tmp)
        
print(ans)

Measured memory_bytes: 94220
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <bits/stdc++.h>

using namespace std;
using ll = long long ;
const int INF = 1001001001;

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

   cout << a*b << endl;


    return 0 ;
}

Measured memory_bytes: 3636
# import math
# N = int(input())
# A_list = [int(i) for i in input().split()]


# def divide_list(num_list):
#   left = 0
#   right = len(num_list)
#   minimum = 10**9

#   while True:
#     c = (left+right)//2
#     left_sum = sum(num_list[:c])
#     right_sum = sum(num_list[c:])
#     diff = abs(left_sum - right_sum)

#     if minimum > diff:
#       minimum = diff
#       minimum_left = left
#       minimum_right = right
    
#     if left_sum > right_sum:
#       right = c
#     elif left_sum < right_sum:
#       left = c
#     else:
#       return num_list[:c], num_list[c:]

#     if c==left or c==right:
#       c = (minimum_left+minimum_right)//2
#       return num_list[:c], num_list[c:]

# tmp1_list, tmp2_list = divide_list(A_list)
# print(tmp1_list, tmp2_list)
# tmp11_list, tmp12_list = divide_list(tmp1_list)
# tmp21_list, tmp22_list = divide_list(tmp2_list)
# print(tmp11_list, tmp12_list, tmp21_list, tmp22_list)

# ans_list = [sum(tmp11_list), sum(tmp12_list), sum(tmp21_list), sum(tmp22_list)]
# ans_list.sort()

# print(ans_list[-1] - ans_list[0])


#102_D
N = int(input())
A = list(map(int, input().split()))
s = 0
AS = []
for i in range(N):
    s += A[i]
    AS.append(s)
#尺取り法
Ans = AS[N-1]+1
L = 0
R = 2
for Mid in range(1, N-2):
    Sum_L = AS[Mid]
    Sum_R = AS[N-1]-Sum_L
    while abs(Sum_L-2*AS[L]) > abs(Sum_L-2*AS[L+1]):
        L += 1

    while abs(AS[N-1]-2*AS[R]+AS[Mid]) > abs(AS[N-1]-2*AS[R+1]+AS[Mid]):
        R += 1
    P = AS[L]
    Q = AS[Mid]-AS[L]
    S = AS[R]-AS[Mid]
    T = AS[N-1]-AS[R]
    #print(Mid,L,R,abs(max(P,Q,S,T)-min(P,Q,S,T)))
    Ans = min(Ans, abs(max(P, Q, S, T)-min(P, Q, S, T)))
print(Ans)


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

using namespace std;

int main(int argc, char *argv[]) {
	int n;
	cin >> n;
	vector<tuple<string, int, int>> sp;
	for (int i = 0; i < n; i++) {
		string s;
		int p;
		cin >> s >> p;
		sp.emplace_back(s, p, i + 1);
	}
	
	sort(sp.begin(), sp.end(), [](const auto &lhs, const auto &rhs)
		{
			if (std::get<0>(lhs) != std::get<0>(rhs)) return std::get<0>(lhs) < std::get<0>(rhs);
			return std::get<1>(lhs) > std::get<1>(rhs);
		}
	);
	
	for (int i = 0; i < n; i++) {
		cout << get<2>(sp[i]) << endl;
	}
}

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


/**
 * AIZU ONLINE JUDGE
 * 0631
 *  2020/5/5
 */
public class Main {


    boolean main() throws IOException {

        Scanner sc = new Scanner(systemin);

        int N = sc.nextInt();
        int M = sc.nextInt();
        
        int sum = 0;
        int max = 0;
        
        for(int i = 0; i < M; i++) {
            int A = sc.nextInt();
            int B = sc.nextInt();
            
            int cnt = Math.max(N - A, 0);
            sum += cnt;
            max = Math.max(max, cnt);
        }

        result.printf("%d\n", sum - max);

        sc.close();
        return false;
    }



    PrintStream log;
    PrintStream result = System.out;
    BufferedReader systemin;

    static Main instance = new Main();

    Main() {
        systemin = new BufferedReader(new InputStreamReader(System.in));
        log = new PrintStream(new OutputStream() { public void write(int b) {} } );
    }

    public static void main(String[] args) throws IOException {

        instance.main();
        instance.systemin.close();
    }


}




Measured memory_bytes: 32860
#include<bits/stdc++.h>
#define maxn 4010
#define INF 2147483647
using namespace std;
char s[maxn];
int sum, head[maxn], nxt[maxn], a[maxn], edge, f[maxn], g[maxn], diff[maxn];
void create(int u, int v)
{
	edge++; a[edge] = v; nxt[edge] = head[u]; head[u] = edge;
}
void get_f(int u, int fa)
{
	f[u] = 0; g[u] = 0; diff[u] = 0;
	if (s[u] == '1') diff[u] = 1;
	int mx = 0, son = 0;
	for (int i = head[u]; i; i = nxt[i])
	{
		int v = a[i];
		if (v != fa)
		{
			get_f(v, u);
			diff[u] += diff[v];
			g[u] += g[v] + diff[v];
			if (g[v] + diff[v] > mx) {mx = g[v] + diff[v]; son = v;}
		}
	}
	if (mx * 2 <= g[u])
	{
		if (g[u] % 2) f[u] = 1;
		else f[u] = 0;
	}
	else f[u] = max(0, f[son] + diff[son] - (g[u] - mx));
	if (g[u] % 2 && f[u] == 0) f[u] = 1;
}
int main()
{
	int n;
	scanf("%d", &n);
	scanf("%s", s + 1);
	for (int i = 1; i <= n - 1; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		create(u, v); create(v, u);
	}
	int res = INF;
	for (int i = 1; i <= n; i++)
	{
		get_f(i, 0);
		if (f[i] == 0) res = min(res, g[i] / 2);
	}
	if (res == INF) res = -1;
	printf("%d\n", res);
	return 0;
}

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


int main(){

string s;
cin >> s;
int count;
rep(i,3)if(s.at(i)=='1')count++;
cout << count << endl;
return 0;
}






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

struct Edge {
    int to;     // 辺の行き先
    int weight; // 辺の重み
    Edge(int t, int w) : to(t), weight(w) { }
};
using Graph = vector<vector<Edge>>;

vector<int> color;

vector<bool> seen;
void dfs(const Graph &G, int v, int dist) {
    seen[v] = true;
    if (dist % 2 == 0) {
	color[v] = 1;
    } else {
	color[v] = 0;
    }

    for (auto e : G[v]) {
        if (seen[e.to]) continue;
        dfs(G, e.to, dist + e.weight);
    }
}

int main() {
    // 頂点数と辺数
    int N, M;
    cin >> N;
    M = N - 1;

    // グラフ
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int from, to, weight;
        cin >> from >> to >> weight;
        G[from-1].push_back(Edge(to-1, weight));
	G[to-1].push_back(Edge(from-1, weight));
    }

    seen.assign(N, false);
    color.resize(N);
    
    dfs(G, 0, 0);

    for (int i = 0; i < N; i++) {
	cout << color[i] << endl;
    }
    return 0;
}



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

const int INF = 1001001001;
int main() {
    int n,m;
    cin >> n >> m;
    vector<vector<int>>g(n);
    rep(i,m) {
        int a,b;
        cin >> a >> b;
        a--;b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int>prev(n,-1);
    vector<int>dist(n,INF);
    dist[0] = 0;
    queue<int>q;
    q.push(0);
    while(!q.empty()) {
        int v = q.front();q.pop();
        for(auto nv : g[v]) {
            if(dist[nv] == INF) {
                dist[nv] = dist[v] + 1;
                q.push(nv);
                prev[nv] = v;
            }
        }
    }
    for(int i = 1;i<n;i++) {
        if(prev[i] == -1) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    for(int i = 1;i<n;i++) {
        cout << prev[i] + 1 << endl;
    }
}
    




Measured memory_bytes: 10552
import numpy as np
stdin = open(0)

A = np.fromstring(stdin.read(), np.int64, sep=' ')[1:]
A = A[A % 2 == 0]
if np.all((A % 3 == 0) | (A % 5 == 0)):
    print('APPROVED')
else:
    print('DENIED')

Measured memory_bytes: 27116
using System;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            string S = Console.ReadLine();

            int K = int.Parse(Console.ReadLine());

            char[] c = S.ToCharArray();

            char rchar = c[K-1];

            for(int i=0;i < N;i++)
            {
                if (c[i] != rchar)
                    c[i] = '*';
            }


            Console.WriteLine(new string(c));
        }
    }
}


Measured memory_bytes: 11092
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,a,i,s=0,t,m,p,d;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        if(i%3!=0 && i%5!=0)
            s+=i;
    }
    cout<<s<<endl;

    return 0;
}


Measured memory_bytes: 3632
#ifdef DEBUG

#else

#    pragma GCC optimize("O3,no-stack-protector")
#    pragma GCC optimize("unroll-loops")

#    ifdef __cplusplus < 201703L
#        pragma GCC target("avx")
#    else
#        pragma GCC target("avx2")
#    endif

#endif
// 実数の場合
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;

using namespace std;
using Graph = vector<vector<Int>>;

const double pi = M_PI;
const Int MOD = 1000000007;

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

    int a, b;
    cin >> a >> b;
    string s;
    cin >> s;

    bool ans = true;
    for (int i = 0; i < a + b + 1; i++) {
        if (i == a) {
            if (s[i] != '-') {
                ans = false;
                break;
            }
        } else {
            if (s[i] == '-') {
                ans = false;
                break;
            }
        }
    }

    if (ans) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
  int n;
  scanf("%d",&n);
  int d, problem[100001]={};
  for(int i=0;i<n;i++){
    scanf("%d",&d);
    problem[d]++;
  }
  int abc = 0, ans = 0;
  for(int k=2;k<=100000;k++){
    abc += problem[k-1];
    if(abc == n/2) ans++;
  }
  printf("%d",ans);
}

Measured memory_bytes: 512
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T

main :: IO ()
main = do
  (n : _) <- map unsafeSignedDecimal . T.words <$> T.getLine :: IO [Int]
  let
    n' = toRational n :: Rational
    x' = n' * 100 / 108 :: Rational
    x0 = floor $ x' :: Int
    x1 = x0 + 1
    n0 = floor $ toRational x0 * 108 / 100 :: Int
    n1 = floor $ toRational x1 * 108 / 100 :: Int
  putStrLn $ if n0 == n then show x0 else if n1 == n then show x1 else ":("

unsafeSignedDecimal :: T.Text -> Int
unsafeSignedDecimal s = case T.signed T.decimal s of
  Right (n, _) -> n


Measured memory_bytes: 508
#include <iostream>

int main()
{
	int n; std::cin >> n;
	
	long long int* DP = new long long int[n+1];
	DP[0] = DP[1] = 1;
	for (int i=2; i<=n; i++) DP[i] = DP[i-1] + DP[i-2];
	
	std::cout << DP[n] << std::endl;
	
	delete[] DP;
	
	return 0;
}



Measured memory_bytes: 3100
import heapq

def Yen(s):
    Cost = [float("inf") for i in range(n)]
    V = [False for i in range(n)]
    Q = [(0, s-1)]
    Cost[s-1] = 0
    while Q:
        tempCost, tempNode = heapq.heappop(Q)
        V[tempNode] = True
        for node in A[tempNode]:
            if V[node[1]] == False:
                if Cost[node[1]] > tempCost + node[0]:
                    Cost[node[1]] = tempCost + node[0]
                    heapq.heappush(Q, (Cost[node[1]], node[1]))
    return Cost

def Snuuk(t):
    Cost = [float("inf") for i in range(n)]
    V = [False for i in range(n)]
    Q = [(0, t-1)]
    Cost[t-1] = 0
    while Q:
        tempCost, tempNode = heapq.heappop(Q)
        V[tempNode] = True
        for node in B[tempNode]:
            if V[node[1]] == False:
                if Cost[node[1]] > tempCost + node[0]:
                    Cost[node[1]] = tempCost + node[0]
                    heapq.heappush(Q, (Cost[node[1]], node[1]))
    return Cost

n, m ,s, t = map(int, input().split())
ini = 10 ** 15
A = [[] for i in range(n)]
B = [[] for i in range(n)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    u, v = u-1, v-1
    A[u].append((a, v))
    A[v].append((a, u))
    B[u].append((b, v))
    B[v].append((b, u))

Yen, Snuuk = Yen(s), Snuuk(t)
total, minCost = [], []
tempmin = float("inf")
for i in reversed(range(n)):
    total.append(Yen[i] + Snuuk[i])
    tempmin = min(tempmin, Yen[i] + Snuuk[i])
    minCost.append(tempmin)

for i in reversed(range(n)):
    print(ini - minCost[i])

Measured memory_bytes: 85976