akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#define MAX 100
#define NOT_FOUND -1
#define BLACK 1
#define WHITE 0
#define GRAY 2

void push(int);
int pop(void);
void DFS(int, int); //深さ優先探索
int adjust(int, int);

int adj[MAX+1][MAX+1] = {};
int s[MAX];
int top = 0;
int time = 0;
int color[MAX];
int d[MAX]; //発見時刻
int f[MAX]; //完了時刻

int main(){
  int n, u, k, v;
  int i, j;

  //1オリジンで
  scanf("%d", &n);
  for(i=0;i<n;i++){
    scanf("%d %d", &u, &k);
    for(j=0;j<k;j++){
      scanf("%d", &v);
      adj[u][v] = 1;
    }
  }

  //colorの初期化
  for(i=1;i<=n;i++){
    color[i] = WHITE;
  }

  //まだ訪問していないuを始点にする
  for(i=1;i<=n;i++){
    if(color[i] == WHITE) DFS(n, i);
  }

  for(i=1;i<=n;i++) printf("%d %d %d\n", i, d[i], f[i]);

  return 0;
}

void push(int x){
  top++;
  s[top] = x;
}

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

//uに隣接する頂点を探す
int adjust(int n, int u){
  int i;
  for(i=1;i<=n;i++){
    if(adj[u][i] == 1 && color[i] == WHITE) return i;
  }
  return NOT_FOUND;
}

void DFS(int n, int u){
  int v;
  
  push(u);
  color[u] = GRAY;
  time++;
  d[u] = time;

  while(top != 0){
    u = s[top];
    v = adjust(n, u);
    if(v != NOT_FOUND){
      if(color[v] == WHITE){
	color[v] = GRAY;
	time++;
	d[v] = time;
	push(v);
      }
    }
    else{
      pop();
      color[u] = BLACK;
      time++;
      f[u] = time;
    }
  }
}



Measured memory_bytes: 2108
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
int n, v, w, dep[105], ad = 105;
long long al;
vector<int> G[105];
void bfs(int s1, int s2 = 0){
	long long l = 1 + (s2 > 0);
	int t, d = 1, z = 0;
	queue<int> qu;
	fill(dep, dep+n+1, 0);
	dep[s1] = dep[s2] = 1;
	qu.push(s1);
	if(s2) qu.push(s2);
	while(!qu.empty()){
		t = qu.front(); qu.pop();
		if(d != dep[t]){
			l *= z;
			d++; z = 0;
		}
		z = max(z, (int)G[t].size()-1 + (!s2 && t == s1));
		for(int nx: G[t]) if(!dep[nx]){
			dep[nx] = d+1;
			qu.push(nx);
		}
	}
	if(ad > d){
		ad = d;
		al = l;
	}else if(ad == d) al = min(al,l);
}
int main(){
	scanf("%d", &n);
	rep(i,n-1){
		scanf("%d%d", &v, &w);
		G[v].push_back(w);
		G[w].push_back(v);
	}
	rep(i,n){
		bfs(i+1);
		for(int c: G[i+1]) if(c < i+1) bfs(c,i+1);
	}
	printf("%d %lld\n", ad, al);
}

Measured memory_bytes: 256
import java.util.*;
import java.io.PrintWriter;
import static java.lang.Integer.*;
import static java.lang.Long.*;
import static java.lang.Math.*;
import static java.lang.System.*;

public class Main {
	public static final int MOD = 1000000007;
	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(in);
		char[] s = sc.next().toCharArray();
		char[] t = sc.next().toCharArray();
		sc.close();
		int ans=0;
		for (i = 0; i < t.length; i++) {
			if(s[i]!=t[i])ans++;
		}
		out.println(ans);
	}
}


Measured memory_bytes: 32636
#include<iostream>

using namespace std;

bool check(int x, int y) {
	if (x >= 0 && x <= 9 && y >= 0 && y <= 9) {
		return true;
	}
	else {
		return false;
	}
}


int main() {
	int paper[10][10] = { 0 };
	int x, y, s;
	char d, h;
	while (cin >> x >> d >> y >> h >> s) {
		if (check(x, y)) {
			paper[x][y] += 1;
		}
		if (check(x - 1, y)) {
			paper[x - 1][y] += 1;
		}
		if (check(x + 1, y)) {
			paper[x + 1][y] += 1;
		}
		if (check(x, y - 1)) {
			paper[x][y - 1] += 1;
		}
		if (check(x, y + 1)) {
			paper[x][y + 1] += 1;
		}

		if (s != 1) {
			if (check(x-1,y-1)) {
				paper[x - 1][y - 1] += 1;
			}
			if (check(x - 1, y + 1)) {
				paper[x - 1][y + 1] += 1;
			}
			if (check(x + 1, y - 1)) {
				paper[x + 1][y - 1] += 1;
			}
			if (check(x + 1, y + 1)) {
				paper[x + 1][y + 1] += 1;
			}
		}

		if (s == 3) {
			if (check(x - 2, y)) {
				paper[x - 2][y] += 1;
			}
			if (check(x, y - 2)) {
				paper[x][y - 2] += 1;
			}
			if (check(x + 2, y)) {
				paper[x + 2][y] += 1;
			}
			if (check(x, y + 2)) {
				paper[x][y + 2] += 1;
			}

		}

	

	}
	int max = 0, blank = 0;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			if (paper[i][j] == 0) {
				blank += 1;
			}
			else {
				if (paper[i][j] > max) {
					max = paper[i][j];
				}
			}
		}
	}
	cout << blank << endl;
	cout << max << endl;

}


Measured memory_bytes: 3060
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()) {
            String ab = in.nextLine();
            String[] ls = ab.split(" ",0);
            int[] ls2 = new int[2];
            for (int i = 0 ; i < 2; i++) {
                ls2[i] = Integer.parseInt(ls[i]);
            }
            int c = ls2[0] + ls2[1];
            int ans = String.valueOf(c).length();
            System.out.println(ans);
        }
    }
}

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

int main() {
  vector <long> ll(87);
  int n; cin >> n;

  ll[0]=2;
  ll[1]=1;

  rep(i, n-1) {
    ll[i+2] = ll[i] + ll[i+1];
  }

  p(ll[n]);
}


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

using namespace std;

int main() {
  int n, a;
  cin >> n;
  vector<int> input;
  array<int, 1000002> dp{};
  for (int i=0; i<n; ++i) {
    cin >> a;
    input.push_back(a);
  }
  for (auto& e: input) {
    ++dp[e-1];
    ++dp[e];
    ++dp[e+1];
  }
  int res = 0;
  for (auto& e: dp) {
    res = max(res, e);
  }
  cout << res << endl;
}


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

using namespace std;

int main() {
  int64_t H, W, N;
  cin >> H >> W >> N;
  unordered_set<int64_t> blacks;
  for (int i = 0; i < N; i++) {
    int64_t y, x;
    cin >> y >> x;
    int64_t p = y << 32 | x;
    blacks.insert(p);
  }

  vector<int64_t> counts(10, 0);
  unordered_set<int64_t> checked;
  for (int64_t p : blacks) {
    int y = p >> 32;
    int x = p & 0xffffffff;

    for (int dy = -2; dy <= 0; dy++) {
      for (int dx = -2; dx <= 0; dx++) {
        int64_t sx = x + dx;
        int64_t sy = y + dy;
        int64_t sp = sy << 32 | sx;
        if (checked.count(sp)) continue;
        if (sx - 1 < 0 or W <= sx + 1 or sy - 1 < 0 or H <= sy + 1) continue;

        checked.insert(sp);

        int count = 0;
        for (int dy2 = 0; dy2 <= 2; dy2++) {
          for (int dx2 = 0; dx2 <= 2; dx2++) {
            int64_t x2 = sx + dx2;
            int64_t y2 = sy + dy2;
            int64_t p2 = y2 << 32 | x2;
            count += blacks.count(p2);
          }
        }
        counts[count]++;
      }
    }
  }

  int64_t sum = accumulate(counts.begin(), counts.end(), 0);
  counts[0] += (H - 2) * (W - 2) - sum;

  for (int i = 0; i < 10; i++) {
    printf("%ld\n", counts[i]);
  }

  return 0;
}


Measured memory_bytes: 40720
S=input()
N = len(S)
A = [0]*N
C = [0]*N
L = [0]*N
R = [0]*N
for i in range(1,N):
    A[i] = A[i-1] + (S[i-1] == "A")
    L[i] = L[i-1] + (S[i-1] == "?")
    C[N-1-i] = C[N-i] + (S[N-i] == "C")
    R[N-1-i] = R[N-i] + (S[N-i] == "?")
mod = 10**9+7
d={0:1}
def pow_mod(x,n):
    if d.get(n,False) :return d[n]
    if n<0: return pow_mod(x,mod-1+n)
    if n%2  :
        d[n] = (x*pow_mod(x,n-1))%mod
    else:
        d[n] = (pow_mod(x,n//2)**2)%mod
    return d[n]
ans = 0
for i in range(1,N-1):
    if S[i] in "B?":
        ans += (3*A[i]+L[i])*(3*C[i]+R[i])*pow_mod(3,L[i]+R[i]-2)
        ans %= mod
print(ans)

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

#define INF 1e9
using namespace std;
typedef long long ll;

int main() {

    int a, b, c; cin >> a >> b >> c;

    int mx = max({a, b, c});

    int diff = mx - a + mx - b + mx - c;

    int ans = 0;
    if (diff % 2 == 0) {
        ans = diff / 2;
    } else {
        ans = diff / 2 + 2;
    }

    cout << ans << endl;
}

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

int main(){
    int n;
    cin>>n;
    for (int i=1;i<10;i++){
        if (n%i == 0 && n/i<10){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No";
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <vector>
using namespace std;
typedef long long ll;
int main(){
	int A,B,T;
	cin >> A >> B>>T;

	cout <<T/A*B<< endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
	using namespace std;
	#define IOS ios::sync_with_stdio(false), cin.tie(0)
	#define REP(i, n) for (int i = 0; i < n; i++)
	#define FOR(i, a, b) for (int i = a; i < b; i++)
	#define ALL(x) (x).begin(), (x).end()
	#define dump(x) cout << (x) << endl
	#define LMAX 9223372036854775807LL
	#define LMIN -9223372036854775807LL

	using ll = long long;
	template<typename T>
	using vec = vector<T>;
	using P = pair<ll, ll>;

	template <typename A, size_t N, typename T>
	void Fill(A (&array)[N], const T &val){
		fill((T *)array, (T *)(array + N), val);
	}
	
	const ll INF = 1e18;
	const ll mod = 1e9 + 7;

	//int dx[4] = {1,0,-1,0};
	//int dy[4] = {0,1,0,-1};
	//ll pas[51][52];
	
	signed main(){
		IOS;
		ll n;
		cin >> n;
		map<ll,ll> mp1,mp2;
		REP(i,n){
			int x;
			cin >> x;
			if(i % 2)mp1[x]++;
			else mp2[x]++;
		}
		vec<P> p1,p2;
		for(auto it = mp1.begin();it != mp1.end();it++){
			ll a = it->first;
			ll b = it->second;
			p1.push_back(P(b,a));
		}
		for(auto it = mp2.begin();it != mp2.end();it++){
			ll a = it->first;
			ll b = it->second;
			p2.push_back(P(b,a));
		}
		sort(ALL(p1),greater<P>());
		sort(ALL(p2),greater<P>());
		ll ans = 0;
		int s = p1.size();
		int t = p2.size();
		for(int i = 0;i < min(2, s);i++){
			for(int j = 0;j < min(2, t);j++){
				if(p1[i].second == p2[j].second)continue;
				ans = max(ans,p1[i].first + p2[j].first);
			}
		}
		if(ans == 0){
			dump(n / 2);
			return 0;
		}
		dump(n - ans);
	}

Measured memory_bytes: 8824
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
	int n,v;
	cin >> n;
	int A[100];
	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}

	for (int i = 0; i < n - 1; i++) {
		cout << A[i] << " ";
	}
	cout << A[n - 1] << endl;

	int j;
	for (int i = 1; i < n; i++) {
		v = A[i];
		j = i - 1;
		while (j >= 0 && A[j] > v) {
			A[j + 1] = A[j];
			j--;
		}
		A[j + 1] = v;

		//結果表示
		for (int i = 0; i < n-1; i++) {
			cout << A[i] << " ";
		}
		cout << A[n-1] << endl;
	}

	return 0;
}


Measured memory_bytes: 3104
const solve = (m, list) => {
  list.sort((a, b) => a[0] - b[0])
  let rest = m
  let result = 0
  for (var i = 0; i < list.length; i++) {
    const [yen, num] = list[i]
    if (rest < num) {
      result += rest * yen
      break
    } else {
      result += yen * num
      rest = rest - num
    }
  }
  return result
  // ...
}
const main = (input) => {
  const [head, ...rest] = input.split("\n")
  const [n, m] = head.split(" ").map(Number)
  const list = rest.map((m) => m.split(" ").map(Number))

  return solve(m, list)
}

if (process.env.NODE_ENV !== "test") {
  const input = require("fs").readFileSync("/dev/stdin", "utf8")
  console.log(main(input.trim()))
}


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

int main()
{
	int n, m, d, t = 0;
	string s[100];

	cin >> n >> m >> d;

	for (int i = 0; i < n; i++)
		cin >> s[i];

	for (int i = 0; i < n; i++) {
		int ct = 0;
		for (int j = 0; j < m; j++) {
			if (s[i][j] == '.')
				ct++;
			else {
				if (ct >= d)
					t += ct - d + 1;
				ct = 0;
			}
		}

		if (ct >= d)
			t += ct - d + 1;
	}

	for (int j = 0; j < m; j++) {
		int ct = 0;
		for (int i = 0; i < n; i++) {
			if (s[i][j] == '.')
				ct++;
			else {
				if (ct >= d)
					t += ct - d + 1;
				ct = 0;
			}
		}

		if (ct >= d)
			t += ct - d + 1;
	}

	cout << t << endl;

	return 0;
}


Measured memory_bytes: 3160
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){

    int x,y,z,c=0;
    cin>>x>>y>>z;
    for(int i=x;i<=y;i++){
        if(i%z==0){
            c++;
        }
    }
    cout<<c<<endl;





}


Measured memory_bytes: 3588
/*
  AOJ 0276
  Title:
  @kankichi573
*/
#include <stdio.h>


int max_,min_;


main()
{
        int i;

        for(i=0;i<7;i++)
        {
                scanf("%d %d",&max_,&min_);
                printf("%d\n",max_-min_);
        }

  return(0);
}

Measured memory_bytes: 600
N = int(input())
size = [list(sorted(map(int, input().split()))) for i in range(3)]
dp = [[1] * (N + 1), [0] * (N + 1), [0] * (N + 1)]
dp[0][0] = 0
for i in range(1, 3):
	pos = 1
	for j in range(1, N + 1):
		dp[i][j] += dp[i][j - 1]
		for k in range(pos, N + 1):
			if size[i][j - 1] <= size[i - 1][k - 1]:
				break
			dp[i][j] += dp[i - 1][k]
			pos += 1
print(sum(dp[2]))


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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
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 vector_finder(std::vector<ll> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

int main() {
  int n, m; cin >> n >> m;
  vector<int> c(m); REP(i, m) cin >> c[i];
  int dp[30][50010];
  REP(i, 30) {
    REP(k, 50010) {
      dp[i][k] = 10000010;
    }
  }
  for(int i = 0; i < m; ++i) {
    dp[1][c[i]] = 1;
  }
  for(int i = 0; i < m; ++i) {
    for(int k = 0; k <= n; ++k) {
      if(k - c[i] >= 0) {
        chmin(dp[i + 1][k], dp[i][k - c[i]] + 1);
        chmin(dp[i + 1][k], dp[i + 1][k - c[i]] + 1);
      }
      chmin(dp[i + 1][k], dp[i][k]);
    }
  }
  cout << dp[m][n] << endl;
}


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

const int N = 1e5 + 5;

int n, ans = 0, mx = -1;
int a[N];

int32_t main()
{
	IOS;
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
		if(a[i] >= mx)
			ans++;
		mx = max(mx, a[i]);
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
  int n,k;
  for(;cin>>n>>k,n;)
    {
      int d[n];
      for(int i=0;i<n;i++)
	cin>>d[i];
      int sum=0;
      int i;
      for(i=0;i<k;i++)
	{
	  sum+=d[i];
	}
      int max=sum;
      for(;i<n;i++)
	{
	  sum+=d[i];
	  sum-=d[i-k];
	  if(max<sum)
	    max=sum;
	}

      cout<<max<<endl;
    }
}

Measured memory_bytes: 1548
#include <iostream>
using namespace std;
int main(void){
    
    int a,b,c,d=0;
    cin >>a>>b>>c;
    
    for(int i = b; b <=c; b++){
        
        
        if(a % b == 0){
            d++;
        }
        
        
        
    }
    
    cout<<d<<endl;
}




Measured memory_bytes: 3104
#include <stdio.h>
#include <memory.h>
int map[29],n,sum;
void set(int sign){
    int i,o;
    if(map[sign]==1){
        for(i=sign;i>=0;i--)
            if(map[i] != 1){
                sign=i;
                break;
            }
        if(sign != i)
            return;
    }
    for(sum=0,i=0;i<sign;i++)
        sum+=map[i];
    sum+=--map[sign];
    sum=n-sum;
    for(i=sign+1;sum!=0;i++){
        if(sum <= map[i-1]){
            map[i]=sum;
            break;
        }
        else{
            map[i]=map[i-1];
            sum-=map[i];
        }
    }
    for(o=0;o<=i;o++)
        printf("%d%s",map[o],o==i?"\n":" ");
    set(i);
}
int main(void){
    for(;memset(map,0,sizeof(map)),scanf("%d",&n),n;){
        map[0]=n;
        printf("%d\n",n);
        set(0);
    }
    return 0;
}

Measured memory_bytes: 600
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author alireza_kaviani
 */

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef pair<ld, ld> pld;
typedef pair<string, string> pss;

#define all(x)                      (x).begin(),(x).end()
#define Sort(x)                     sort(all((x)))
#define X                           first
#define Y                           second
#define Mp                          make_pair
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << " = " << x << endl
#define SZ(x)                       ll(x.size())
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define set_random                  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

inline ll input() {
    ll n;
    cin >> n;
    return n;
}

ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}

set_random;

const ll MAXN = 50 + 10;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;

template <ll SIZE>
struct DSU
{
    ll par[SIZE] , sz[SIZE];
    DSU(){
        fill(par , par + SIZE , -1);
        fill(sz , sz + SIZE , 1);
    }

    ll Find(ll v){
        return (par[v] == -1 ? v : par[v] = Find(par[v]));
    }

    ll Union(ll v , ll u){
        ll pv = Find(v) , pu = Find(u);
        if(pv == pu)    return 0;
        par[pu] = pv;
        sz[pv] += sz[pu];
        return 1;
    }

    ll getSize(ll v){
        return sz[Find(v)];
    }
};

ll n , ans = INF;
pll point[MAXN];
set<pll> diff;

int main() {
    fast_io;

    cin >> n; ans = n;
    for(ll i = 0 ; i < n ; i++) cin >> point[i].X >> point[i].Y;
    sort(point , point + n);

    for(ll i = 0 ; i < n ; i++){
        for(ll j = 0 ; j < i ; j++){
            diff.insert({point[i].X - point[j].X , point[i].Y - point[j].Y});
        }
    }

    for(auto &p : diff){
        DSU<MAXN> dsu;
        for(ll i = 0 ; i < n ; i++){
            for(ll j = 0 ; j < n ; j++){
                if(Mp(point[i].X - point[j].X , point[i].Y - point[j].Y) == p){
                    dsu.Union(i , j);
                }
            }
        }

        ll comps = 0;
        for(ll i = 0 ; i < n ; i++){
            if(dsu.Find(i) == i)    comps++;
        }
        ans = min(ans , comps);
    }
    cout << ans << endl;

    return 0;
}
/*
todo :
    1- set constants
    2- check TimeLimit and MemoryLimit
    3- check special test cases
    4- don't forget BS can help you that is good idea(use for loop for floats)
    5- don't forget printf and scanf can help you in your code speed
*/


Measured memory_bytes: 384
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>

using namespace std;
typedef long long int ll;
    
int main()
{
    string S[3];
    cin >> S[0] >> S[1] >> S[2];

    int turn = 0;
    while (true) {
        if (S[turn].size() == 0) {
            if (turn == 0) cout << 'A' << endl;
            if (turn == 1) cout << 'B' << endl;
            if (turn == 2) cout << 'C' << endl;
            return 0;
        }
        if (S[turn][0] == 'a') {
            S[turn].erase(S[turn].begin());
            turn = 0;
        }
        else if (S[turn][0] == 'b') {
            S[turn].erase(S[turn].begin());
            turn = 1;
        }
        else if (S[turn][0] == 'c') {
            S[turn].erase(S[turn].begin());
            turn = 2;
        }
    }
    return 1;
}


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

using namespace std;

const int mod = 1e9 + 7; // 1,000,000,007

int main()
{
	int N, M;
	cin >> N >> M;
	vector<bool> isStep(N, true);
	
	for (int i = 0; i < M; i++)
	{
		int a;
		cin >> a;
		// a段目は壊れている
		isStep[a] = false;
	}
	
	// 動的計画法を用いる
	// 上記のテーブル
	vector<int> dp(N + 1, 0);
	
	// 初期化条件 0段目
	dp[0] = 1;
	// 1段目
	if (isStep[1] == true)
	{
		dp[1] = 1;
	}
	
	// 2段目以降はループ
	for (int i = 2; i <= N; i++)
	{
		// i - 1段目から来るパターン
		if (isStep[i - 1] == true) {
			dp[i] += dp[i - 1]; // 通りの加算
		}
		// i - 2段目から来るパターン
		if (isStep[i - 2] == true) {
			dp[i] += dp[i - 2]; // 通りの加算
		}
		
		dp[i] %= mod;
	}
	
	int answer = dp[N];
	
	cout << answer << endl;
	
	return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main(void){
    int n,count;
    int v[100];
    int c[100];
    int sum=0;

    scanf("%d",&n);
    for(count=1;count<=n;count++){
        scanf("%d",&v[count]);
    }
    for(count=1;count<=n;count++){
        scanf("%d",&c[count]);
    }
    for(count=1;count<=n;count++){
        if(v[count]-c[count]>=0){sum=sum+v[count]-c[count];}
    }
    printf("%d\n",sum);
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll long long
#define N 100005 
using namespace std;
struct lbc{
	int x,y;
	bool operator <(const lbc &a)const{
		return y-x>a.y-a.x;
	}
}a[N];
struct heap{
	priority_queue<int> q;
	int sz;
	ll s;
	void resize(int _sz){
		sz=_sz; s=0;
		while (!q.empty()) q.pop();
	}
	void insert(int x){
		q.push(-x); s+=x;
		if (q.size()>sz)
			s+=q.top(),q.pop();
	}
	ll query(){
		if (q.size()!=sz) return -1e18;
		return s;
	}
}jdb;
int x,y,z;
ll ans,v[N];
int main(){
	scanf("%d%d%d",&x,&y,&z);
	for (int i=1;i<=x+y+z;i++){
		int v;
		scanf("%d%d%d",&a[i].x,&a[i].y,&v);
		a[i].x-=v; a[i].y-=v; ans+=v;
	}
	sort(a+1,a+x+y+z+1);
	jdb.resize(y);
	for (int i=1;i<=x+y+z;i++){
		jdb.insert(a[i].y);
		v[i]=jdb.query();
	}
	jdb.resize(x);
	for (int i=x+y+z;i;i--){
		jdb.insert(a[i].x);
		v[i-1]+=jdb.query();
	}
	ll tmp=-1e18;
	for (int i=1;i<x+y+z;i++)
		tmp=max(tmp,v[i]);
	printf("%lld\n",tmp+ans);
}

Measured memory_bytes: 2428
#include <stdio.h>
#include <string.h>

int main()
{
	char str[1024];
	while(scanf("%s", str), strcmp(str, "0"))
	{
		int sum = 0;
		for(int i = 0; str[i]; ++i)
		{
			sum += str[i] - '0';
		}
		printf("%d\n", sum);
	}
	return 0;
}


Measured memory_bytes: 2104
#include <bits/stdc++.h>
// #include "/usr/local/include/cxx_pretty_print/cxx_pretty_print.hpp"

using namespace std;
/* type aliases */
using i32 = int32_t; using ui32 = uint32_t; using i64 = int64_t; using ui64 = uint64_t; using i128 = __int128;
using f32 = float;   using f64  = double;   using f80 = long double;
using PII = pair<i32, i32>; using PLL = pair<i64, i64>; using PFF = pair<f32, f32>; using PDD = pair<f64, f64>;
using VB  = vector<bool>;   using VS  = vector<string>;
using VI  = vector<i32>;    using VL  = vector<i64>;    using VF  = vector<f32>;    using VD  = vector<f64>;
using VVI = vector<VI>;     using VVL = vector<VL>;     using VVF = vector<VF>;     using VVD = vector<VD>;
using VPI = vector<PII>;    using VPL = vector<PLL>;    using VPF = vector<PFF>;    using VPD = vector<PDD>;
/* constants */
constexpr i64 mod = 1000000007;                                // 10^9+7
constexpr i64 inf = 9000000000000000000;                       // 9*10^18
/* macros */
#define MAX(c)        *max_element(ALL(c))
#define MIN(c)        *min_element(ALL(c))
#define SIZE(c)       (i64)((c).size())                        // unsined int (size_t) -> int64_t
#define ALL(c)        (c).begin(), (c).end()
#define RALL(c)       (c).rbegin(), (c).rend()
#define REP(i, n)     for (i64 i=0; i<(i64)(n); ++i)           // 0 to n-1
#define REPD(i, n)    for (i64 i=(i64)(n)-1; i>=0; --i)        // n-1 to 0
/* debug */
#define debug(x)      cerr << #x << ": " << (x) << '\n'
#define debugvec(v)   for (size_t _ = 0; _ < (v).size(); ++_) {cerr << #v << '[' << _ << "]: " << (v)[_] << '\n';}
/* useful output */
auto print = [](auto x) {cout << (x) << '\n';};
template <class T> void printvec(T v, string sep=" ", string end="\n") {REP(i, SIZE(v)-1) cout << v[i] << sep; cout << v[SIZE(v)-1] << end;}
/* useful input */
VS splitstr(string s, char delim=' ') {VS v; string buf; stringstream ss{s}; while (getline(ss, buf, delim)) v.push_back(buf); return v;}


i32 num = 0;

void postorder_traverse(const VVI& adj, VI& order, i32 u, i32 prev) {
    for (auto v: adj[u]) {
        if (v != prev) postorder_traverse(adj, order, v, u);
    }
    order[u] = num;
    num++;
}



void Main() {
    i32 n;
    cin >> n;
    VVI adj(n, VI());
    REP(i, n-1) {
        i32 a, b;
        cin >> a >> b;
        adj[a-1].push_back(b-1);
        adj[b-1].push_back(a-1);
    }
    VI c(n, 0);
    REP(i, n) cin >> c.at(i);
    
    VI order(n, -1);
    postorder_traverse(adj, order, 0, -1);
    
    // ans
    sort(ALL(c));
    print(accumulate(ALL(c), 0) - c[SIZE(c) - 1]);
    REP(i, n) cout << c[order[i]] << ' ';
    cout << endl;
}


signed main() {
    cin.tie(nullptr);                                         // cin と cout の tie を切り高速化
    cout << fixed << setprecision(15);                        // 浮動小数点数が 1e-006 のように表示されることを防ぐ
    Main();
}

Measured memory_bytes: 4544
N = int(input())

dict = {}
strings = []
for i in range(N):
    x = input()
    if x in dict.keys():
        dict[x] += 1
    else:
        dict[x] = 1

maximum = 1
for i in dict:
    maximum = max(maximum,dict[i])

for word in dict:
    if dict[word] == maximum:
        strings.append(word)
strings.sort()
for word in strings:
    print(word)

Measured memory_bytes: 35284
#include <stdio.h>

#define N 100

int main(){

  int u,v,n,k,i,j,A[N][N];

  scanf("%d",&n);

  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      A[i][j] =0;

  for(i=0;i<n;i++){
    scanf("%d%d",&u,&k);
    for(j=0;j<k;j++){ 
      scanf("%d", &v);
      A[u-1][v-1] = 1;
    }
  }

  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      printf("%d", A[i][j]);
      if(j!=n-1) printf(" ");
    }
    printf("\n");
  }

  return 0;
}

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


long long dp[111][100111];
long long w[111];
long long u[111];

int main()
{
	long long N, W;
	cin >> N >> W;
	
	for(int i = 1; i <= N; i++)
	{
		cin >> w[i] >> u[i];
	}
	
	for(int i = 0; i <= W; i++) dp[0][i] = 0;
	for(int j = 0; j <= N; j++) dp[j][0] = 0;
	
	for(int j = 1; j <= N; j++)
	{
		for(int i = 1; i <= W; i++)
		{
			if(i >= w[j]) dp[j][i] = max(dp[j-1][i], u[j] + dp[j-1][i - w[j]]);
			else dp[j][i] = max(dp[j][i], dp[j-1][i]);
		}
	}
	cout << dp[N][W];
	return 0;
}

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

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

using namespace std;

using ll = long long;
using ul = unsigned long long;
ll mod = 1000000007;

int main() {
source:
    ll n;
    cin >> n;
    ll temp = 10;
    bool judge = false;
    while (temp <= n) {
        if (temp == n) {
            judge = true;
            break;
        }
        temp *= 10;
    }

    if (judge) {
        cout << 10 << endl;
    } else {
        ll ans = 0;
        while (n) {
            ans += n % 10;
            n /= 10;
        }
        cout << ans << endl;
    }
    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<map>

using namespace std;

int i,j,k,N,M,X,ans;

void dfs(int s,int t,int u, long long  X)
{
  if(X>N) return;
  else if(s>0 && t>0 && u>0) ans++;
  
  X*=10;
  X+=3;
  s++;
  dfs(s,t,u,X);
  X-=3;
  s--;
  
  X+=5;
  t++;
  dfs(s,t,u,X);
  X-=5;
  t--;

  X+=7;
  u++;
  dfs(s,t,u,X);
  X-=7;
  u--;
  
}


int main()
{
  cin>>N;
  ans=0;
  dfs(0,0,0,0);
  
  
  
  cout <<ans;
  
  
  
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
    ll x, k, d, p;
    cin >> x >> k >> d;
    if (x < 0)
        x = -x;
    p = x / d;
    if (p <= k)
    {
        if ((k - p) % 2)
            cout << d - (x % d) << endl;
        else
            cout << (x % d) << endl;
    }
    else
        cout << x - k * d;
}

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

int main(){
  long double a;
  cin >> a;
  
  long double b = 0;
  b = a/3 * a/3 * a/3;
  
  cout <<fixed << setprecision(15) << b << endl;
}


Measured memory_bytes: 256
int main(void)
{
  int N;
  scanf("%d",&N);
  N=N%100;
  N=N%10;
   switch (N){
    case 1:
      printf("pon\n");
      break;
     case 2:
      printf("hon\n");
      break;
     case 3:
      printf("bon\n");
      break;
     case 4:
      printf("hon\n");
      break;   
     case 5:
      printf("hon\n");
      break;
     case 6:
      printf("pon\n");
      break;
     case 7:
      printf("hon\n");
      break;
     case 8:
      printf("pon\n");
      break;  
     case 9:
      printf("hon\n");
      break;
     case 0:
      printf("pon\n");
      break;  
   }
    return 0;
}

Measured memory_bytes: 1644
def main():
    N, K = [int(s) for s in input().split()]
    p = [int(s) for s in input().split()]
    s = sum(p[:K])
    res = s
    for i in range(1,N):
        if i+K > N:
            break
        s = s + p[i+K-1]
        s = s - p[i-1]
        res = max(s,res)
    print((res+K)/2)

main()

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

using namespace std;

using ll = long long;

int main() {
    int N, M;
    cin >> N >> M;
    valarray<int> votes(N);
    for (auto& x : votes) {
        cin >> x;
    }
    sort(begin(votes), end(votes));
    reverse(begin(votes), end(votes));
    if (votes[M - 1] * 4 * M >= votes.sum()) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


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

#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

int main() {
    int64_t n;
    cin >> n;

    unordered_map<int64_t, int64_t> m;
    for (auto _ : irange(0L, n)) {
        int64_t a;
        cin >> a;
        ++m[a];
    }

    int64_t t = 0;
    for (const auto& kv : m) {
        t += max(0L, kv.second - 1);
    }

    cout << n - (t + 1) / 2 * 2 << endl;
}

Measured memory_bytes: 4388
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define rvisort(v) sort(v.begin(), v.end(), greater<int>());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
// #define int long long
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())
 
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using ul = unsigned long;
 
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; }
 
ll GCD(ll a, ll b) { return b ? GCD(b, a%b) : a; }
ll LCM(ll a, ll b) { return a / GCD(a, b)* b; }
 
const int dy[] = {0, 1, 0, -1, -1, 1, 1, -1};
const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
 
inline bool inside(int y, int x, int H, int W) {
    return (y >= 0 && x >= 0 && y < H && x < W);
}
 
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
 
signed main()
{
  int n,k; cin>>n>>k;
  ll ans=0;
  reps(b,n){
    int p=n/b;
    int r=n%b;
    ans+=(ll)p*max(0,b-k);
    ans+=(ll)max(0,r-k+1);
  }
  if(k==0) ans=(ll)n*n;
  cout<<ans<<endl;
}

Measured memory_bytes: 256
function Main(input) {
  input = input.split("\n");
  var N = parseInt(input[0].split(" ")[0]);
  var A = parseInt(input[0].split(" ")[1]);
  var x = input[1].split(" ").map(i => parseInt(i));
  var sum=0;
  for(var i=0;i<N;i++){
    sum+=x[i];
  }
  var map=new Array(sum+1);
  for(var i=0;i<sum+1;i++){
    var tmp=new Array(N+1).fill(0);
    
    map[i]=tmp;
  }
  map[0][0]=1;
  for(var k=0;k<N;k++){
    for(var i=N;i>0;i--){
      for(var j=sum+1;j-x[k]>=0;j--){
        if(map[j-x[k]][i-1]!=0){
          map[j][i]=map[j][i]+map[j-x[k]][i-1];
        }
      }
    }
  }
  var ans=0;
  for(var i=1;i<=N;i++){
    if(i*A<=sum){
      ans+=map[i*A][i];
    }
  }
  console.log('%s', ans);
  return ans;
}

function debug(n){
  var input = document.getElementById("input"+n).value;
  var ans=Main(input);
  var result="WA";
  if(ans==document.getElementById("output"+n).value.split("\n")[0]){
    result="AC";
  }
  document.getElementById("result"+n).innerHTML=result;
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

int main(){
	int a, b, k;
	cin >> a >> b >> k;
	int c = b - a;
	if (c <= k) {
		for ( int i = 0; i <= c; i++){
			cout << a + i << endl;
		}
	}
	else {
		for (int i = 0; i <= k - 1; i++) {
			cout << a + i << endl;
		}
		int numA = a + k - 1;
		int numB = b - (k - 1);
		for (int i = 0; i <= k - 1; i++) {
			int numB2 = numB + i;
			if (numA == numB + i) continue;
				cout << numB + i << endl;
			}
		}
	}

Measured memory_bytes: 256
#!/usr/bin/env python3
from collections import deque

# input
n, m = map(int, input().split())
a = [-1 for _ in range(m)]
b = [-1 for _ in range(m)]
to = [[] for _ in range(n+1)]
for i in range(m):
    a[i], b[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1
    to[a[i]].append(b[i])
    to[b[i]].append(a[i])

# calc
inf = 1001001001
dist = [inf for _  in range(n)]
pre = [-1 for _ in range(n)]
dist[0] = 0 
q = deque()
q.append(0)

while q:
    v = q.popleft()
    for u in to[v]:
        if dist[u] != inf:
            continue
        dist[u] = dist[v]+1
        pre[u] = v 
        q.append(u)

# output
print('Yes')
for i in range(n):
    if i == 0:
        continue
    ans = pre[i]
    ans +=1 
    print(ans)


Measured memory_bytes: 38352
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define endl "\n"

const ll mod = 1e9 + 7;
// const ll mod = 998244353;
const ll sz = 1e6 + 5;
vector<ll> fac(sz, 1);

ll powmod(ll a, ll b) { ll res=1; a%=mod; assert(b>=0); for(;b;b>>=1) { if(b&1) res=res*a%mod; a=a*a%mod; } return res; }
ll nCr(ll n, ll r) { return ( ( ( (fac[n] * powmod(fac[n-r], mod-2)) % mod ) * powmod(fac[r], mod-2) ) % mod ); }
ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a; }
ll lcm(ll a, ll b) { return (a / gcd(a,b)) * b; }
ll extended_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll xx, yy;
    ll res = extended_gcd(b, a%b, xx, yy); x = yy; y = xx - yy * (a / b);
    return res;
}

// * ALways PASS arrays, strings etc to functions BY REFERENCE

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    // for (ll i = 2; i < sz; i++)
    //     fac[i] = (fac[i-1] * i) % mod;
    
    int t = 1;
    // cin >> t;

    while(t--) {
        int n;
        cin >> n;
        
        vector<pair<int,int>> arr(n);
        for (auto &p: arr)
            cin >> p.fi >> p.se;
        
        bool f;
        for (int i = 0; i <= n-3; i++) {
            f = true;
            for (int j = i; j <= i+2; j++) {
                if (arr[j].fi != arr[j].se) {
                    f = false;
                    break;
                }
            }
            if (f)
                break;
        }
        
        cout << (f ? "Yes" : "No") << endl;
    }
    
	return 0;
}


Measured memory_bytes: 10956
import java.util.*;

class Main{
  public static void main(String args[]){
    Scanner sc=new Scanner(System.in);
    int k=sc.nextInt();
    int x=sc.nextInt();
    int f=Math.max(x+1-k,-1000000);
    int t=Math.min(x-1+k,1000000);
    for(int i=f;i<=t;i++){
      System.out.println(i);
    }
  }
}

Measured memory_bytes: 21844
import sys
from fractions import gcd
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

INF = 10**18
N, M, *A = map(int, read().split())

lcm = 1
for a in A:
    a //= 2
    lcm *= a // gcd(lcm, a)
    
    if lcm > M:
        print(0); sys.exit()
for a in A:
    if lcm % a == 0:
        print(0); sys.exit()

print((M // lcm +1) // 2)


Measured memory_bytes: 14508
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include <cmath>
#include <map>


using namespace std;
const long long INF = (long long) (1e18)+1;

int main() {
  int n; // 桁数
  int m; // iのかず

  cin >> n >> m;
  map<int, int> nums;
  // map<string, int> words;
  // vector<int> nums;
  // int m = 1; 
  bool flag = false;
  for(int i=0; i<m; ++i){
    int a, b;
    cin >> a >> b;
    if (n != 1 && a == 1 && b == 0){
      flag = true;
    }
    if (nums.count(a) && nums[a] != b) {
      flag = true;
    }
    nums[a] = b;
  }
  if (flag) {
    cout << -1 << endl;
    return 0;
  } else if (n == 1 && m == 0) {
    cout << 0 << endl;
    return 0;
  }


  string ans = "";
  for (int i=1; i<=n; ++i){
    if (nums.count(i)) {
      ans += to_string(nums[i]);
    } else if (i==1) {
      ans += "1";
    } else {
      ans += "0";
    }
  }

  cout << ans << endl;
}


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

cnt=0
i=0
while i<n:
    if i!=n-1:
        if i+1==a[i]:
            cnt+=1
            i+=2
        else:
            i+=1
    else:
        if i+1==a[i]:
            cnt+=1
        i+=1
print(cnt)
        




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

using namespace std;

using int64 = long long;

vector<int> Solve() {
  int64 n;
  cin >> n;
  if (n == 1) {
    return vector<int>({1, 1});
  }
  vector<char> ops;
  while (n > 1) {
    if (n % 2 == 1) {
      ops.push_back('*');
      n--;
      n /= 2;
    } else {
      ops.push_back('+');
      n--;
    }
  }
  reverse(ops.begin(), ops.end());

  int k = ops.size() + 1;
  deque<int> q;
  q.push_back(1);
  for (int i = 2; i <= k; i++) {
    char op = ops[i - 2];
    if (op == '+') {
      q.push_front(i);
    } else {
      q.push_back(i);
    }
  }
  
  vector<int> v;
  for (int i = 1; i <= k; i++) {
    v.push_back(i);
  }
  v.insert(v.end(), q.begin(), q.end());
  return v;
}

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

  auto v = Solve();
  cout << v.size() << endl;
  for (int x : v) {
    cout << x << " ";
  }
  cout << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
//#define ll long long
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define rep(i, n) REP(i, 0, n)
#define rep_rev(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
ll t1,t2;
const ll mod = 1000000007;
const int INF = 1e9;
const ll INFLONG = 1e18;
void swap(ll *x,ll *y){
  ll tmp;
  tmp = *x;
  *x = *y;
  *y = tmp;
}



class DisjointSet{
public:
  vector<ll> rank,p;
  DisjointSet(ll k){
    rank.resize(k);
    p.resize(k);
    rep(i,k){
      makeSet(i);
    }
  }
  void makeSet(ll x){
    rank[x] = 0;
    p[x] = x;
  }
  bool same(ll x,ll y){
    return findSet(x) == findSet(y);
  }
  void unite(ll x,ll y){
    ll px = findSet(x);
    ll py = findSet(y);
    link(px,py);
  }

  void link(ll x,ll y){
    if(rank[x] == rank[y]){
      p[y] = x;
      rank[x]++;
    }else if(rank[x] > rank[y]){
      p[y] = x;
    }else{
      p[x] = y;
    }
  }

  ll findSet(ll x){
    if(p[x] != x){
      return p[x] = findSet(p[x]);
    }
    return x;
  }
};

class Edge{
public:
    ll s;
    ll t;
    ll w;
    Edge(ll s,ll t,ll w):
    s(s),t(t),w(w){

    }
    const bool operator < (const Edge e) const{
      return w < e.w;
    }
};

int main(){
  ll n,m;
  cin >> n >> m;
  DisjointSet ds = DisjointSet(n);
  vector<Edge> E;
  ll s,t,w;
  rep(i,m){
    cin >> s >> t >> w;
    E.emplace_back(Edge(s,t,w));
  }
  sort(all(E));
  ll piv = 0;
  ll ans = 0;
  ll cou = 0;
  while(cou != n-1){
    if(!ds.same(E[piv].s,E[piv].t)){
      ds.unite(E[piv].s,E[piv].t);
      ans += E[piv].w;
      cou++;
      //cout << E[piv].s << E[piv].t << E[piv].w << endl;
    }
    piv++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 6148
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

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

typedef long long lint;

using namespace std;

int main(){
  lint H,W;
  cin>>H>>W;
  if(H==1 or W==1)cout<<1<<endl;
  else cout<<(H*W+1ll)/2ll<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void){
  int flg = 0;
  int a,b;
  cin >> a >> b;
  
  for (int c=1; c<=3; c++){
    if ((a*b*c)%2==1) flg = 1;
  }
  cout << (flg?"Yes":"No") << endl;
  return 0;
}


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

int n,x[200005];
pair<int,int> a1[200005],a[200005];

bool cmp(pair<int,int> a,pair<int,int> b)
{
    return a.second<b.second;
}

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

    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i];
        a[i]={x[i],i};
        a1[i]={x[i],i};
    }
    sort(a+1,a+1+n);
    int m=a[n/2].first,M=a[n/2+1].first;
    for(int i=1;i<=n;i++)
    {
        a1[a[i].second].second=i;
    }
    /*for(int i=1;i<=n;i++)
        cout<<a1[i].first<<" "<<a1[i].second<<endl;*/
    for(int i=1;i<=n;i++)
    {
        if(a1[i].second<=n/2)
            cout<<M<<endl;
        else if(a1[i].second>=n/2+1)
            cout<<m<<endl;
    }

    return 0;
}


Measured memory_bytes: 7460
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <deque>

#define mp make_pair
#define x first
#define y second
#define pb push_back
using namespace std;

char s[105];

int main()
{
    cin >> (s+1); int n = strlen(s+1);
    int yes = 1;
    for(int i=1; i<=n; ++i) if ( ((i&1) && s[i]=='L') || ((i&1)==0 && s[i]=='R') ) yes = 0;
    yes ? puts("Yes") : puts("No");
}


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

int main() {
	string S;
	cin >> S;
	int ans = 999;
	for (int i = 0; i <= S.size() - 3; i++) {
		int num = (S[i] - '0') * 100 + (S[i + 1] - '0') * 10 + S[i + 2] - '0';
		ans = min(ans, abs(num - 753));
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb           push_back
#define pii          pair<int,int>
#define vi           vector<int>
#define vpii         vector<pair<int,int>>
#define gph          map<int, vector<int>>
#define mp           make_pair
#define FOR(i, n) for (int i = 0; i <  (int)(n); i++)
#define FOR1(i, n) for (int i = 1; i <= (int)(n); i++)
#define FORD0(i, n) for (int i = (int)n; i >= 0; i--)
#define FORD1(i, n) for (int i = (int)n; i >= 1; i--)
#define FORS(i, n) for(; i < (int)(n); i++)
#define debug(X) { cout << #X << " = " << (X) << endl; }
#define printArr(A,n) { cout << #A << " = "; FOR(i,n) cout << A[i] << ' '; cout << endl; }
using namespace std;
#define int long long int


int a, b;
vector<int> visited;
bool fail = false;
int n;
map<pii, bool> edges;
int cnt = 0;
void dfs(int cur, bool turn){
    //debug(cur);
    if(visited[cur] == turn)return;
    if(visited[cur] != -1 && visited[cur] ==  !turn){
        fail = true;
        return; 
    }
    visited[cur] = turn;
    if(turn)a++;
    else b++;
    FOR(i, n){
        if(i == cur)continue;
        if(!edges[{i, cur}]){
            cnt++;
            dfs(i, !turn);
        }
        if(fail)return;
    }
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    //freopen("2.txt", "r", stdin);
    cin >> n;
    visited = vector<int>(n + 5, -1);
    int m;cin >> m;
    int u, v;
    FOR(i, m){
        cin >> u >> v;
        u--,v--;
        edges[mp(u, v)] = true;
        edges[mp(v, u)] = true;
    }
    vector<pii> options;
    a = 0, b= 0;
    FOR(i, n){
        if(visited[i] == -1)dfs(i, false);
        if(fail){
            cout << -1 <<endl;
            return 0;
        }
        if(a + b > 0)options.pb(mp(a, b));
        a = 0, b= 0;
    }
    const int lim = (n)/2;
    assert(m*2 + cnt == (n*(n-1)));
    vector<bool> dp(lim + 1);
    dp[0] = true;
    int sum = 0;
    for(pii x: options){
        vector<bool> dp2(lim+1);
        sum += x.first + x.second;
        FORD1(i, lim){
            if(x.first <= i)dp2[i] =dp2[i] |  dp[i - x.first];
            if(x.second <= i)dp2[i] = dp2[i] | dp[i - x.second]; 
        }
        dp = dp2;
    }
    assert(sum == n);
    FORD1(i, lim){
        if(dp[i]){
            cout << i*(i-1)/2 + (n-i)*(n-i-1)/2 <<endl; 
            return 0;
        }
    }

}




Measured memory_bytes: 30848
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int):
    print("YNeos"["9" not in str(N)::2])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<int,int>;

const int MOD = 1000000007;
void add(long long &a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

int main(void){
    int n;
    cin >> n;
    ll dp[n+1][5][5][5]; // 直前の3文字が i, j, kのとき 長さnをどれだけ作れるか。
    // 普通にSTLのvector使わなかったらこれはでたらめに初期化される。
    for(int i = 0; i < n+1; i++){
        for(int j = 0; j < 5; j++){
            for(int k = 0; k < 5; k++){
                for(int l = 0; l < 5; l++){
                    dp[i][j][k][l] = 0;
                }
            }
        }
    }
    dp[0][0][0][0] = 1;
    for(int nn = 0; nn < n; nn++){
        for(int i = 0; i < 5; i++){
            for(int j = 0; j < 5; j++){
                for(int k = 0; k < 5; k++){
                    for(int l = 1; l < 5; l++){
                        if(i == 1 && k == 2 && l == 3) continue;
                        if(i == 1 && j == 2 && l == 3) continue;
                        if(j == 1 && k == 2 && l == 3) continue;
                        if(j == 1 && k == 3 && l == 2) continue;
                        if(j == 2 && k == 1 && l == 3) continue;
                        add(dp[nn+1][j][k][l], dp[nn][i][j][k]);
                    }
                }
            }
        }
    }

    ll ans = 0;
    for(int i = 1; i < 5; i++){
        for(int j = 1; j < 5; j++){
            for(int k = 1; k < 5; k++){
                add(ans, dp[n][i][j][k]);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3676