akhauriyash/Code-Regression huggingface dataset:
fn dfs(u: usize, p: usize, depth: &mut Vec<usize>, parent: &mut Vec<usize>, next: &Vec<Vec<usize>>) {
    for &v in &next[u] {
        if v != p {
            depth[v] = depth[u] + 1;
            parent[v] = u;
            dfs(v, u, depth, parent, next);
        }
    }
}
fn cnt(u: usize, p: usize, next: &Vec<Vec<usize>>) -> usize {
    next[u].iter().filter(|&v| *v != p).map(|&v| cnt(v, u, next)).sum::<usize>() + 1
}
fn main() {
    let n: usize = readln();
    let ps: Vec<(usize, usize)> = readlns(n-1);
    let mut next: Vec<Vec<usize>> = vec![vec![]; n];
    for (a, b) in ps {
        next[a-1].push(b-1);
        next[b-1].push(a-1);
    }
    let mut parent: Vec<usize> = vec![0; n];
    let mut depth: Vec<usize> = vec![0; n];
    parent[0] = 0;
    depth[0] = 0;
    dfs(0, 0, &mut depth, &mut parent, &next);
    let c = (depth[n-1] - 1) / 2;
    let mut root = n-1;
    for i in 0..c {
        root = parent[root];
    }
    let b = cnt(root, parent[root], &next);
    let a = n - b;
    println!("{}", if a <= b { "Snuke" } else { "Fennec" });
}

// --- template ---
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::HashSet;


pub trait FromLn {
    fn fromln(s: &str) -> Self;
}
pub fn readln<T: FromLn>() -> T {
    let mut buf = String::new();
    let _ = ::std::io::stdin().read_line(&mut buf).unwrap();
    T::fromln(buf.trim())
}
pub fn readlns<T: FromLn>(n: usize) -> Vec<T> {
    let mut vs = vec![];
    for _ in 0..n { vs.push(readln()); }
    vs
}
macro_rules! fromln_primitives {
    ($($t:ty),*) => { $(
        impl FromLn for $t {
            fn fromln(s: &str) -> $t {
                s.parse().unwrap()
            }
        }
    )* }
}
fromln_primitives!(String, bool, f32, f64, isize, i8, i16, i32, i64, usize, u8, u16, u32, u64);
impl<T> FromLn for Vec<T> where T: FromLn {
    fn fromln(s: &str) -> Vec<T> {
        s.split_whitespace().map(T::fromln).collect()
    }
}
impl FromLn for Vec<char> {
    fn fromln(s: &str) -> Vec<char> {
        s.chars().collect()
    }
}
macro_rules! fromln_tuple {
    ($($t:ident),*) => {
        impl<$($t),*> FromLn for ($($t),*) where $($t: FromLn),* {
            fn fromln(s: &str) -> ($($t),*) {
                let mut it = s.split_whitespace();
                let t = ($($t::fromln(it.next().unwrap())),*);
                assert_eq!(it.next(), None);
                t
            }
        }
    }
}
fromln_tuple!(A, B);
fromln_tuple!(A, B, C);
fromln_tuple!(A, B, C, D);
fromln_tuple!(A, B, C, D, E);
fromln_tuple!(A, B, C, D, E, F);

Measured memory_bytes: 18684
#include <cstdint>
#include <iostream>
#include <vector>

using namespace std;

class AbsBit
{
public:
    AbsBit(int64_t offset) : bit_(2 * offset + 2, 0), offset_(offset) {}

    void Add(int64_t pos);

    int64_t CountSmaller(int64_t pos) const;

private:
    static int64_t Lsb(int64_t num) { return num & -num; }

    vector<int64_t> bit_;
    int64_t offset_;
};

void AbsBit::Add(int64_t pos)
{
    pos += offset_;
    while (pos < (int64_t)bit_.size()) {
        bit_[pos] += 1;
        pos += Lsb(pos);
    }
}

int64_t AbsBit::CountSmaller(int64_t pos) const
{
    pos += offset_;

    int64_t count = 0;
    while (pos > 0) {
        count += bit_[pos];
        pos -= Lsb(pos);
    }
    return count;
}

int64_t CountBigSubs(int64_t med, const vector<int64_t> &vec)
{
    int64_t balance = 0;
    int64_t subs = 0;
    AbsBit bit(vec.size() + 1);

    bit.Add(0);
    for (const auto &num : vec) {
        balance += (num >= med ? 1 : -1);
        subs += bit.CountSmaller(balance);
        bit.Add(balance);
    }
    return subs;
}

bool SmallEnough(int64_t med, const vector<int64_t> &vec)
{
    int64_t total_subs = 1LL * vec.size() * (vec.size() - 1) / 2 + vec.size();
    int64_t half_subs = (total_subs + 1) / 2;

    return CountBigSubs(med, vec) >= half_subs;
}

int MedianOfMedians(const vector<int64_t> &vec)
{
    int res = 0;
    int pow = (1 << 30);

    while (pow > 0) {
        auto next_res = res + pow;
        pow >>= 1;

        if (SmallEnough(next_res, vec)) {
            res = next_res;
        }
    }
    return res;
}

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

    vector<int64_t> vec(n);
    for (auto &num : vec) {
        cin >> num;
    }

    auto res = MedianOfMedians(vec);
    cout << res << "\n";

    return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++) //for文マクロ
using namespace std;

typedef unsigned long ul;
typedef long long ll;
typedef pair<ul, ul> P; //ペア　タイプでふ

int main()
{
    // int A, B, T;
    // cin >> A;
    // cin >> B;
    // cin >> T;
    // cout << (int)(B * ((T - T % A) / A));
    int A, B, C;
    cin >> A >> B >> C;
    if (A > B)
        swap(A, B);
    if (A < C && C < B)
    {
        cout << "Yes";
    }
    else
    {
        cout << "No";
    }
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b){
  if (!a) return b;
	return gcd(b%a,a);	
}

int main(){
	ll a,b;
  	cin >>a >>b;
  	if (a < b)
  		cout << (a*b)/gcd(a,b)<<"\n";
	else
     	cout <<(a*b)/gcd(b,a)<<"\n";
  	
  	return 0;
     }


Measured memory_bytes: 256
n=int(input())
s=input()

ans=0
for i in range(n-2):
    if (s[i]=="R"):
        numG=s[i+1:].count("G")
        numB=s[i+1:].count("B")
        ans+=numG*numB
        for j in range(i+1,(n+1+i)//2):
            #print(j,i,s[j],s[2*j-i])
            if (s[j]!=s[j+(j-i)] and s[j]!="R" and s[2*j-i]!="R"):
                ans-=1
                
    elif (s[i]=="G"):
        numG=s[i+1:].count("R")
        numB=s[i+1:].count("B")
        ans+=numG*numB
        for j in range(i+1,(n+1+i)//2):
            if (s[j]!=s[j+(j-i)] and s[j]!="G" and s[2*j-i]!="G"):
                ans-=1
        
    else:
        numG=s[i+1:].count("R")
        numB=s[i+1:].count("G")
        ans+=numG*numB
        for j in range(i+1,(n+1+i)//2):
            if (s[j]!=s[j+(j-i)] and s[j]!="B" and s[2*j-i]!="B"):
                ans-=1

print(ans)

Measured memory_bytes: 68420
#include <bits/stdc++.h>
#ifdef DEBUG
#include "_debug.cpp"
#include "callable.hpp/callable.hpp"
#endif
#define endl '\n'
using namespace std;
using ll = long long;
#define N 50
int n, m;
bool adj[N+1][N+1];
void link(int u, int v) {
    adj[u][v] = true;
    adj[v][u] = true;
}
void unlink(int u, int v) {
    adj[u][v] = false;
    adj[v][u] = false;
}
bool vis[N+1];
int d[N+1];
int sz[N+1];
int p[N+1];
template <typename Function>
int dfs(int u, const Function& f, int depth=1) {
#ifdef DEBUG
    using actual_type = typename callable_traits<Function>::function_type;
    using expected_type = typename callable_traits<void(int)>::function_type;
    static_assert(is_same<actual_type, expected_type>::value, "dfs 'f' must be void(int)");
#endif
    int ans = 1;
    vis[u] = true;
    d[u] = depth;
    sz[u] = 1;
    f(u);
    for(int v = 1; v <= n; v++) {
        if(adj[u][v] and !vis[v]) {
            ans += dfs(v, f, depth + 1);
            sz[u] += sz[v];
            p[v] = u;
        }
    }
    return ans;
}
int dfs(int u, int depth=1) { return dfs(u, [](int u) {}, depth); }
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    vector<pair<int, int>> edges;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        edges.push_back({u, v});
        link(u, v);
    }
    int bridge = 0;
    for(auto& e : edges) {
        unlink(e.first, e.second);
        fill(vis, vis + n + 1, false);
        dfs(e.first);
        if(not vis[e.second]) {
            bridge++;
        }
        link(e.first, e.second);
    }
    cout << bridge << endl;
    return 0;
}


Measured memory_bytes: 256
/**
 *      ABC 94 C
 *      author  : kyomukyomupurin
 *      created : 2018/08/29
**/

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N; cin >> N;
    vector<int> v;
    for (int i = 0; i < N; ++i) {
        int x; cin >> x;
        v.push_back(x);
    }

    vector<int> vv;
    for (int i = 0; i < N; ++i) {
        vv.push_back(v[i]);
    }

    int left, right;

    sort(vv.begin(), vv.end());
    left = vv[(N / 2) - 1]; right = vv[N / 2];

    for (int i = 0; i < N; ++i) {
        if (v[i] <= left){
            cout << right << '\n';
        }
        else if (v[i] >= right){
            cout << left << '\n';
        }
    }

    return 0;
}

Measured memory_bytes: 3956
S = input()
d = int((len(S) - 1) / 2)
e = int((len(S) + 3) / 2)
if S == S[::-1] and S[0:d] == S[d - 1:: -1] and S[e - 1:] == S[int(len(S)): e - 2: -1]:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 9076
#include <iostream>

using namespace std;

int P[5];
bool B[3];
int R[5];

int main(int argc, char** argv)
{
	while( 1 )
	{
		cin >> P[0];

		if(P[0]==0) break;

		cin >> P[1];
		cin >> P[2];
		cin >> P[3];
		cin >> P[4];

		B[0] = false; B[1] = false; B[2] = false;
		for(int i=0; i<5; i++)
		{
			B[P[i]-1] = true;
		}

		if(B[0] && B[1] && B[2])
		{
			for(int i=0; i<5; i++)
			{
				R[i] = 3;
			}
		}
		else if(B[0] && B[1])
		{
			for(int i=0; i<5; i++)
			{
				if(P[i]==1) R[i] = 1;
				if(P[i]==2) R[i] = 2;
			}
		}
		else if(B[1] && B[2])
		{
			for(int i=0; i<5; i++)
			{
				if(P[i]==2) R[i] = 1;
				if(P[i]==3) R[i] = 2;
			}
		}
		else if(B[2] && B[0])
		{
			for(int i=0; i<5; i++)
			{
				if(P[i]==3) R[i] = 1;
				if(P[i]==1) R[i] = 2;
			}
		}
		else
		{
			for(int i=0; i<5; i++)
			{
				R[i] = 3;
			}
		}

		for(int i=0; i<5; i++)
		{
			cout << R[i] << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 0
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N = n()

D = []
for i in range(N):
    D.append(n())

D = sorted(D)

count = 1
prev = D[0]
for i in range(1, len(D)):
    if prev < D[i]:
        count += 1
    prev = D[i]
print(count)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
 
using namespace std;
 
#define repr(i,a,b) for (int i=a; i<b; i++)
#define rep(i,n) for (int i=0; i<  n; i++)
 
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; }
 
const long long INF = 1LL << 60;
#define PI 3.14159265359 
 
template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}
 
int gcd(int a, int b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}
 
long long lcm (int a, int b){
    return  (long long) a*b /gcd(a,b);
}

long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }



int collatz(int n){
    int a=n;
    if(a%2 == 0)a/=2;
    else a = a*3+1;
    return a;
}

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

    if(n == 1)cout <<"Hello World" << endl;
    else cout << a+b << endl;

}



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

#define pout(n)  printf ("%d\n", n)

#define rep(i,a,n) for (int i = a;i < n;i++)
#define per(i,n,a) for (int i = n-1;i >= a;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());

const int d4x[4] = {1, 0, -1, 0};
const int d4y[4] = {0, 1, 0, -1};
const int d8x[8] = { 1,1,0,-1,-1,-1,0,1 };
const int d8y[8] = { 0,1,1,1,0,-1,-1,-1 };

#define MAX_N (int)2e5+20
#define INF 1e12+20

typedef long long ll;
using namespace std;

int n, a[20];
 
bool solve(int x, int y){
    if(y==0) return true;
     
    if(x==n) return false;
     
    bool ret = solve(x+1, y) || solve(x+1, y-a[x]);
    return ret;
}
 
int main() {
    cin >> n;
    rep(i,0,n){
        cin >> a[i];
    }     
    int q;
    cin >> q;
    rep(i,0,q){
        int m;
        cin >> m;
        if(solve(0, m)) puts("yes");
        else puts("no");
    }
    return 0;
}


Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007 

int main() {
	string s;
	cin>>s;
	if(s=="ABC"){
		cout << "ARC";
	}
	else{
		cout << "ABC";
	}
	// your code goes here
	return 0;
}

Measured memory_bytes: 3624
n = int(input())
abc = []
for i in range(n):
    abc.append(list(map(int, input().split())))
h = [[0 for i in range(3)] for i in range(n)]
h[0] = abc[0]
for i in range(1, n):
    h[i][0] = max(h[i-1][1]+abc[i][0],h[i-1][2]+abc[i][0])
    h[i][1] = max(h[i-1][2]+abc[i][1],h[i-1][0]+abc[i][1])
    h[i][2] = max(h[i-1][0]+abc[i][2],h[i-1][1]+abc[i][2])
print(max(h[n-1]))

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


int main(void)
{
	int n;
	int q;
	int i;
	scanf("%d",&n);
	int s[n];
	for(i=0;i<n;i++)
	{
		scanf("%d",&s[i]);
	}
	scanf("%d",&q);
	int t[q];
	for(i=0;i<q;i++)
	{
		scanf("%d",&t[i]);
	}
	int j;
	int count=0;
	int count2;
	for(i=0;i<q;i++)
	{
		count2=0;
		for(j=0;j<n;j++)
		{
			if(t[i]==s[j])
			{
				if(count2==0)
				{
					count++;
					count2++;
				}
			}
		}
	}
	printf("%d\n",count);
	return 0;
}



Measured memory_bytes: 2048
import java.util.*;

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

        int sum = 0;
        for(int i=1;i<=N;i++){
            int n=i;
            int digSum=0;
            while(n>0){
                digSum += n%10;
                n/=10;
            }
            if(digSum>=A && digSum<=B){
                sum+=i;
            }
        }
        System.out.println(sum);
    }
}

Measured memory_bytes: 21972
#include<cstdio>
#include<cstring>
using namespace std;
int main(void){
   char c[10001];
   while(scanf("%s",c) != EOF){
      int i_cnt = 0,j_cnt = 0;
      for(int i = 0;i < strlen(c)-2;i++){
         if(c[i] == 'I' && c[i+1] == 'O' && c[i+2] == 'I') i_cnt++;
         if(c[i] == 'J' && c[i+1] == 'O' && c[i+2] == 'I') j_cnt++;
      }
      printf("%d\n%d\n",j_cnt,i_cnt);
   }
   return 0;
}

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

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

typedef long long int   ll;
typedef long double     ld;
typedef pair<ll, ll>    pll;

#define all(x)          x.begin(), x.end()
#define kill(x)         return cout << x << endl, 0;
#define X               first
#define Y               second
#define sep             ' '
#define endl            '\n'
#define fastio          ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define file_io         freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
#define ld_io           cout << setprecision(10) << fixed;

#undef pow
ll pow(ll a, ll b, ll mod) {
    if (!b)    return 1;
    if (b & 1) return a * pow(a * a % mod, b / 2, mod) % mod;
    return pow(a * a % mod, b / 2, mod) % mod;
}

const ll MAXN  = 1e2 + 10;
const ll INF   = 8e18;
const ll MOD   = 1e9 + 7; // 998244353;
const ll LOG   = 32;      // log2(1e9)
const ll BLOCK = 320;     // sqrt(1e5)
const ld PI    = acos(-1);
const ld SADAT = 7.84e-17;  // The most important constant ever

ll n, b[MAXN], ans;

int main() {
    fastio
    cin >> n;
    for (ll i = 0; i < n - 1; i++) {
        cin >> b[i];
    }
    ans += b[0];
    for (ll i = 1; i < n; i++) {
        ans += min(b[i - 1], b[i]);
    }
    ans += b[n - 2];
    cout << ans << endl;

    return 0;
}



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

int main(){
  int N;
  cin>>N;
  string temp;
  string A[N];
  
  cout<<0<<endl;
  cin>>temp;
  if(temp=="Vacant"){
    cout<<0<<endl;
    return 0;
  }
  if(temp=="Male"){
    A[0]="Male";
  }
  if(temp=="Female"){
    A[0]="Female";
  }
  
  cout<<N-1<<endl;
  cin>>temp;
  if(temp=="Vacant"){
    cout<<N-1<<endl;
    return 0;
  }
  if(temp=="Male"){
    A[N-1]="Male";
  }
  if(temp=="Female"){
    A[N-1]="Female";
  }
  int l=N-1;
  int r=0;
  int k=22;
  while(k){
    k--;
    int m=(l+r)/2;
    cout<<m<<endl;
    cin>>temp;
    if(temp=="Vacant"){
      cout<<m<<endl;
      return 0;
    }
    if(temp=="Male"){
      A[m]="Male";
    }
    if(temp=="Female"){
      A[m]="Female";
    }  
    if((l-m)%2 == 0 && A[l] == A[m]){
      l=m;
      continue;
    }
    if((l-m)%2 == 0 && A[l] != A[m]){
      r=m;
      continue;
    }    
    if((l-m)%2 == 1 && A[l] == A[m]){
      r=m;
      continue;
    }    
    if((l-m)%2 == 1 && A[l] != A[m]){
      l=m;
      continue;
    } 

   }
  cout<<3<<endl;

  return 0;
}


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

int n,a;

int main()
{
    scanf("%d%d",&n,&a);    
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n-i;j++)
        {
            if(i*10000+j*5000+(n-i-j)*1000==a)
            {
                printf("%d %d %d\n",i,j,n-i-j);
                return 0;
            }
        }                          
    }        
    printf("-1 -1 -1\n");
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <utility>
#include <set>
#include <map>
#include <tuple> 
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <list>
using namespace  std;
using ll = long long;
using P = pair<ll, ll>;
#define REP(i, n) for(long long (i)=0, i_bound = (long long)(n); (i)<i_bound; ++i)
#define FOR(i, a, b) for(long long (i)=(a); (i)<(b); ++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
const long long MOD = static_cast<long long>(1e9) + 7LL;
const long long INF = 1234567891234567890LL;
int main(){
    cin.tie(0);
    cout.sync_with_stdio(false);
    int N; cin >> N;
    cout << N / 2 + N%2 << endl;
    return 0;
}

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

int main(){
  int N;
  cin >> N;
  vector<int> vec(N);
  for(int i=0; i<N; i++){
    cin >> vec.at(i);
  }
  map<int,int> mp;
  
  for(int i=0; i<=1; i++){
    for(int j=1; j*j<=vec.at(i); j++){
      if(vec.at(i) %j == 0){
        int x = vec.at(i) / j;
        int y = j;
        if(mp.count(x)){
          mp[x]++;
        }
        else{
          mp[x] = 1;
        }
        if(x != y){
          if(mp.count(y)){
            mp[y]++;
          }
          else{
            mp[y] = 1;
          }
        }
      }
    }
  }
  
  for(int i=2; i<N; i++){
    vector<int> no(0);
    for(auto itr = mp.begin(); itr != mp.end(); itr++){
      int a = itr->first;
      int b = itr->second;
      if(vec.at(i) %a != 0){
        no.push_back(a);
      }
    }
    for(int j=0; j<no.size(); j++){
      mp[no.at(j)]--;
      if(mp[no.at(j)] == 0){
        mp.erase(no.at(j));
      }
    }
  }
  
  int ans = 0;
  for(auto itr = mp.begin(); itr != mp.end(); itr++){    
    int a = itr->first;
      ans = max(ans,a);
  }
  cout << ans << endl;
}

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

int main() {
  string a;
  cin >> a;
  int count=0;
  if(a[0]=='1'){count++;}
  if(a[1]=='1'){count++;}
  if(a[2]=='1'){count++;}
  cout << count << endl;
}


Measured memory_bytes: 3628
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func max32(a, b int32) int32 {
	if a > b {
		return a
	}
	return b
}

var dp [][]int32
var maxL int

func makeTbl(N int, v, w []int) {
	N = min(N, len(v))
	dp = make([][]int32, N+1)
	for n := 0; n <= N; n++ {
		dp[n] = make([]int32, maxL+1)
	}
	// out(v, w, N)

	for n := 1; n < N; n++ {
		prev := n / 2
		// out("cur", n, "prev", prev)
		for i := 0; i <= maxL; i++ {
			if w[n] <= i {
				dp[n][i] = max32(dp[prev][i], dp[prev][i-w[n]]+int32(v[n]))
			} else {
				dp[n][i] = dp[prev][i]
			}
		}
		// out(n, dp[n][:10])
	}
}

func calc(s, L int, v, w []int) int {
	N := len(v)
	n := 1 << uint(N)
	ret := 0
L0:
	for i := 0; i < n; i++ {
		sumw := 0
		sumv := 0
		for j := 0; j < N; j++ {
			if (i>>j)%2 == 1 {
				sumw += w[j]
				sumv += v[j]
			}
			if sumw > L {
				continue L0
			}
		}
		// out(strconv.FormatInt(int64(i), 2), sumw, sumv, L)
		rest := L - sumw
		sumv += int(dp[s][rest])
		ret = max(ret, sumv)
	}
	return ret
}

func main() {
	sc.Split(bufio.ScanWords)
	N := getInt()
	v := make([]int, N+1)
	w := make([]int, N+1)
	for i := 1; i <= N; i++ {
		v[i], w[i] = getInt(), getInt()
	}

	Q := getInt()
	AV := make([]int, Q)
	AL := make([]int, Q)

	for i := 0; i < Q; i++ {
		AV[i], AL[i] = getInt(), getInt()
		maxL = max(maxL, AL[i])
	}

	const lv = 2048
	makeTbl(lv, v, w)

	wb := bufio.NewWriter(os.Stdout)
	defer wb.Flush()
	for i := 0; i < Q; i++ {
		L := AL[i]
		V := AV[i]
		// out(V, L, dp[V][:L])
		if V < lv {
			fmt.Fprintln(wb, dp[V][L])
			continue
		}
		val := make([]int, 0, 16)
		weight := make([]int, 0, 16)
		for V >= lv {
			val = append(val, v[V])
			weight = append(weight, w[V])
			V /= 2
		}
		// out(val, weight, V, L)
		ret := calc(V, L, val, weight)
		fmt.Fprintln(wb, ret)
	}
}


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

using namespace std;

#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define fore(i,a) for(auto &i:a)
typedef long long ll;
typedef pair <int, int> P;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
const int  INF = 2147483647;
const ll INFL = 9223372036854775807;
const ll mod = 1000000007;


int main() {
	ll n, x;
	cin >> n >> x;
	VLL a(n), b(n);
	REP(i, n)cin >> a[i];
	REP(i, n)b[i] = a[i];
	ll ans = INFL;

	REP(i, n) {
		ll res = i * x;
		REP(j, n)b[j] = min(b[j], a[(j - i + n) % n]);
		REP(j, n)res += b[j];
		ans = min(ans, res);
	}
	
	cout << ans << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 200005
#define INF 1000000005LL
#define MOD 1000000007

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

int n;
vector<int> p,q,r;

int main(){

  cin >> n;
  rep(i,0,n) r.push_back(i+1);
  rep(i,0,n){
    int a;
    cin >> a;
    p.push_back(a);
  }
  rep(i,0,n){
    int a;
    cin >> a;
    q.push_back(a);
  }
  int a=0,b=0,c=0;

  do{
    bool P=true,Q=true;
    rep(i,0,n){
      P &= (r[i] == p[i]);
      Q &= (r[i] == q[i]);
    }
    if(P)a=c;
    if(Q)b=c;
    c++;
  }while(next_permutation(r.begin(),r.end()));

  cout << abs(a-b) << endl;

  return 0;
}


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

using namespace std;

typedef long long ll;

// union-find tree with size(struct)
struct UnionFind{
    vector<int> par; // 親ノード
    vector<int> rank; // ランク
	vector<int> size; // 連結成分のサイズ

    UnionFind(int n = 1) {
        init(n);
    }

    void init(int n = 1) {
        par.resize(n);
		rank.resize(n);
		size.resize(n);
        for (int i = 0; i < n; ++i){
			par[i] = i;
			rank[i] = 0;
			size[i] = 1;
		}
    }

    int find(int x) {
        if (par[x] == x)  return x;

        int r = find(par[x]);
        return par[x] = r;
    }

    bool issame(int x, int y) {
        return find(x) == find(y);
    }

    bool unite(int x, int y) {
	    x = find(x);
		y = find(y);
	    if (x == y) return false;

	    if (rank[x] < rank[y]) swap(x, y);
	    if (rank[x] == rank[y]) ++rank[x];
	    par[y] = x;
		size[x] += size[y];
	    return true;
    }

	int getSize(int x){
		return size[find(x)];
	}

	int getRank(int x){
		return rank[find(x)];
	}
};


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

	int n, m;
	cin >> n >> m;

	vector<int> p(n);
	rep(i, n) {
		cin >> p[i];
		p[i]--;
	}

	UnionFind uf(n);
	rep(i, m){
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		uf.unite(x, y);
	}

	int ans = 0;
	rep(i, n){
		if(uf.issame(i, p[i])) ans++;
	}

	cout << ans << endl;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define ll long long
int arr[60];
int n, p;

int main() {
	int n;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	vector<int> orderedarr = arr;
	sort(orderedarr.rbegin(), orderedarr.rend());
	for (int i = 0; i < n; i++) {
		cout << (arr[i]
				< orderedarr[n / 2 - 1] ?
						orderedarr[n / 2 - 1] : orderedarr[n / 2]) << "\n";
	}
}


Measured memory_bytes: 4768
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define vec_input(v) for(auto it=v.begin();it!=v.end();it++){cin>>*it;}
#define vec_output(v) for(auto it=v.begin();it!=v.end();it++){if(it!=v.begin())cout<<" ";cout<<*it;}cout<<endl;
#define vec_debug(v) for(auto it=v.begin();it!=v.end();it++){cerr<<*it<<" ";}cerr<<endl;
#define yn(ans) cout<<(ans?"Yes":"No")<<endl
#define YN(ans) cout<<(ans?"YES":"NO")<<endl
#define umap unordered_map
#define uset unordered_set
using namespace std;
using ll = long long;
template <typename T>T digitsum(T n);
template <typename T>bool isPrime(T n);
template <typename T>vector<pair<T, T>> prime_factor(T n);
long long int intpow(long long int,long long int);
template <typename T>T intlog(T);
long long int combination(long long int,long long int);
long long int arith_sum1(long long int,long long int,long long int);
long long int arith_sum2(long long int,long long int,long long int);
long long int series_sum(long long int);

int main(){
    int n;
    cin>>n;
    vector<int> vec(n),check(1000001,0);
    rep(i,n){
        cin>>vec[i];
        check[vec[i]]++;
    }
    sort(all(vec));
    rep(i,n){
        if(check[vec[i]]>=1){
            for(int j=2*vec[i];j<=vec[vec.size()-1];j+=vec[i]){
                check[j]=0;
            }
        }
    }
    cout<<count(all(check),1)<<endl;
}

Measured memory_bytes: 7980
#include <iostream>
#include <cstdlib>

using namespace std;

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

  unsigned long long res = 1;
  for (int i = 1; i <= n; i++) {
    res = (res * i) % 1000000007;
  }
  cout << res << endl;
  return EXIT_SUCCESS;
}


Measured memory_bytes: 256
N = int(input())
A = [list(map(int, input().split()))]
A.append(list(map(int, input().split())))

C = []
for i in range(len(A)):
  for j in range(len(A[i])):
    if i == 0:
      if j == 0:
        B = [A[i][j]]
      else:
        B.append(B[j-1] + A[i][j])
    else:
      if j == 0:
        B = [A[i][j] + C[i-1][j]]
      else:
        v = max(B[j-1], C[i-1][j])
        B.append(v + A[i][j])
  C.append(B)
print(C[-1][-1])

Measured memory_bytes: 3064
import java.util.Scanner;
import java.util.Arrays;
public class Main { 
    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
      	String S = reader.next();
      	int[] X = new int[10];
        for (int k = 0; k < S.length(); k++ ) {
        	X[k] = Integer.parseInt(Character.toString(S.charAt(k)));
        }
        
      	int[] nearSevenDG = new int[10];
      	int minGap = 1000;
      	for (int i = 0; i < S.length() - 2; i++) {
          int gap = Math.abs((X[i]*100 + X[i+1]*10 + X[i+2]) - 753);
          
          if (gap < minGap) {
          	minGap = gap;
          }
		}
      System.out.print(minGap);
      
    }
}

Measured memory_bytes: 23636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    

    int n;
    cin >> n;
    
    if ((n/10) % 111 == 0 || n%1000%111 == 0)
    {
        cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}


}


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

int main()
{
    int n = 0, sum = 0;

    scanf("%d", &n);

    int a[20], c[20], b;

    for(int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    for(int i = 0; i < n; ++i)
    {
        scanf("%d", &b);
        sum += b;
    }
    for(int i = 0; i < n - 1; ++i)
        scanf("%d", &c[i]);

    for(int i = 1; i < n; ++i)
        if(a[i] - 1 == a[i - 1])
            sum += c[a[i - 1] - 1];

    printf("%d", sum);

    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define IFOR(i, m, n) for(int i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
const ll INF = 1e18;
/* テンプレートここまで */

int main() {
  ll n; cin >> n;
  vector<ll> s(n); REP(i, n) cin >> s[i];
  ll ans = 0;
  FOR(c,1,n-1){
    ll l = 0;
    ll r = n-1;
    ll score = 0;
    if((n-1)%c == 0){
      for( ; l<r ; l+=c, r-=c){
        score += s[l] + s[r];
        ans = max(ans,score);
      }
    }else{
      for(; r>c ;l+=c, r-=c){
        score += s[l] + s[r];
        ans = max(ans,score);
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1024
use proconio::{input, fastout, marker::Chars};

#[fastout]
fn main() {
    input! {
        h: usize,
        w: usize,
        k: usize,
        c: [Chars; h],
    }
    let mut res = 0;

    for i in 0..((2 as usize).pow(h as u32)) {
        for j in 0..((2 as usize).pow(w as u32)) {
            let mut temp_c = c.clone();
            for ii in 0..h {
                if ((i+1) & (1 << ii)) > 0 {
                    for i_j in 0..w {
                        temp_c[ii][i_j] = 'r';
                    }
                }
            }
            for jj in 0..w {
                if ((j+1) & (1 << jj)) > 0 {
                    for j_i in 0..h {
                        temp_c[j_i][jj] = 'r';
                    }
                }
            }

            // cnt #
            let mut temp_cnt_k = 0;
            for cnt_i in 0..h {
                for cnt_j in 0..w {
                    if temp_c[cnt_i][cnt_j] == '#' {
                        temp_cnt_k += 1;
                    }
                }
            }
            if temp_cnt_k == k {
                res += 1;
            }
        }
    }

    println!("{:?}", res);
}


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

int main() {
	int N;
	cin >> N;
	int n = N;
	
	int a = 0;
	int b = 0;
	
	while(n != 0){
	a += n % 6;
	n /= 6;
	}
	for(int i = 1;i <= N;i++){
		b = 0;
		int na = N - i;
		int nb = i;
		while(na != 0){
			b += na % 6;
			na /= 6;
		}
		while(nb != 0){
			b += nb % 9;
			nb /= 9;
		}
		a = min(a,b);
	}
	cout << a << endl;
}

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


using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define fore(i,a) for(auto &i:a)

typedef pair <int, int> P;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
const int  INF = 1 << 30;
const ll INFL = 1LL<<60;
const ll mod = 1000000007;		




int main() {

	string s;
	int n, k;
	cin >> n >> k >> s;
	VI v;

	char c = s[0];
	int cnt = 1;

	FOR(i, 1, n) {
		if (s[i] == c)cnt++;
		else {
			v.push_back(cnt);
			cnt = 1;
			c = s[i];
		}
	}
	v.push_back(cnt);

	int m = v.size();

	bool b;
	if (s[0] == '0')b = false;
	else b = true;

	VI cs(m + 1);
	cs[0] = 0;

	int ans = 0;


	REP(i, m) cs[i + 1] = cs[i] + v[i];

	

	REP(i, m) {
		int res;
		if (b) {
			res = cs[min(2 * k + 1 + i,m)] - cs[i];
			b = false;
		}
		else {
			res = cs[min(m, 2 * k + i)] - cs[i];
			b = true;
		}

		ans = max(ans, res);

	}


	cout << ans << endl;

	return 0;
}

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

using namespace std;
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define mp make_pair
#define ld long double
typedef pair<int, int> pii;
typedef priority_queue<int, vector<int>, greater<int> > small_heap;
typedef priority_queue<int> big_heap;
const int N = 1e6 + 100;
int T;
int n, k, s, t;
int m, a[250];
ll c[250][250];
int cnt[1 << 18], vis[1 << 18];

ll calc(int x) {
    for (int i = 1; i <= n; i++) {
        ++cnt[a[i] & x];
    }
    ll tot = 0;
    for (int i = 1; i <= n; i++) {
        int cc = a[i] & x;
        if (vis[cc])continue;
        vis[cc] = 1;
        for (int j = 1; j <= k; ++j) {
            tot += c[cnt[cc]][j];
        }
    }
    for (int i = 1; i <= n; ++i) {
        vis[a[i] & x] = cnt[a[i] & x] = 0;
    }
    return tot;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> k >> s >> t;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        bool ok = true;
        for (int j = 0; j < 18; j++) {
            if ((s >> j) & 1 && !((x >> j) & 1) || !((t >> j) & 1) && (x >> j) & 1) {
                ok = false;
                break;
            }
        }
        if (ok)a[++m] = x;
    }

    for (int i = 0; i < 18; i++) {
        if (((s >> i) & 1) && (!(t >> i) & 1)) {
            puts("0");
            return 0;
        }
    }

    if (!n) {
        puts("0");
        return 0;
    }
    c[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        c[i][0] = 1;
        for (int j = 1; j <= i; j++)
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }

    n = m;
    ll ans = 0;
    for (int i = s ^t;; i = (i - 1) & (s ^ t)) {
        ans += __builtin_popcount(i) & 1 ? -calc(i) : calc(i);
        if (!i)break;
    }
    cout << ans << endl;
    return 0;
}

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

#define STR_MAX 1001

int main(void) {
  unsigned i, j, ans, best_ans = STR_MAX;
  char S[STR_MAX], T[STR_MAX];

  scanf("%s\n%s", S, T);
  for (i = 0; i <= strlen(S) - strlen(T); i++) {
    ans = 0;
    for (j = 0; j < strlen(T); j++) {
      if (S[i + j] != T[j]) ans++;
    }
    if (ans < best_ans) best_ans = ans;
  }
  printf("%d\n", best_ans);
  return 0;
}


Measured memory_bytes: 2156
#include<cmath>
#include<cstdio>
int main()
{
	long long n;
	scanf("%lld",&n);
	long long sqr=(long long)sqrt(n);
	for(long long i=sqr;i>=1;i--){
		if(n%i==0){
			printf("%lld\n",i-1+n/i-1);
			return 0;
		}
	}
	return 0;
}

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

int main(){
	int n,m; cin>>n>>m;
	vector<pair<ll,ll>> vp(n);
	rep(i,n){
		int a,b; cin>>a>>b;
		vp[i]=make_pair(a,b);
	}
	sort(all(vp));
	int i=0;
	ll ans=0;
	while(m>0){
		if(m>=vp[i].second){
			ans+=vp[i].first*vp[i].second;
			m-=vp[i].second;
			i++;
		}else{
			ans+=vp[i].first*m;
			m=0;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 4772
#include<iostream>
#include<cmath>
using namespace std;
int a[2007];
int main(){
	int i,j,k;
	int n,x,y,y2;
	int b,c;
	int s=0;
	cin>>n>>x>>y;
	for(i=0;i<n;i++){
		cin>>a[i];
	}
	b=abs(y-a[n-1]);
	if(n==1)c=0;
	else c=abs(a[n-2]-a[n-1]);
	s=b>c?b:c;
	cout<<s<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <functional>
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
 
int main () {
  string a, b;
  cin >> a >> b;
  int s = stoi(a+ b);
  bool f = false;
  for (int i =1; i <=320; i++){
    if (i*i==s){
      f = true;
      break;
    }
  }
  if (f == true){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}

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


int main() {

	int N, T, A;
	cin >> N;
	cin >> T >> A;

	vector<int> high(N);

	for (int i = 0;i < N;i++)
		cin >> high.at(i);

	int ans;
	for (int i = 0;i < N;i++) {
		double near_i = fabs(A - T + 0.006 * high.at(i));
		if (i == 0)
			ans = 0;

		else if (fabs(A - T + 0.006 * high.at(ans)) > near_i)
			ans = i;
	}

	cout << ans+1;
}


Measured memory_bytes: 256
#![allow(non_snake_case)]
#![allow(unused_variables)]
#![allow(dead_code)]

fn main() {
    let (N, K): (usize, usize) = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        let mut iter = line.split_whitespace();
        (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
        )
    };
    let a: Vec<i64> = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|x| x.parse().unwrap())
            .collect()
    };

    let s: Vec<i64> = {
        let mut s = vec![];
        for i in 0..N {
            let mut acc = 0;
            for j in i..N {
                acc += a[j];
                s.push(acc);
            }
        }
        s
    };
    let M = s.len();
    let mut useable = vec![true; M];
    let mut res: i64 = 0;
    for k in (0..50).rev() {
        if (0..M)
            .filter(|&i| useable[i] && ((s[i] >> k) & 1) == 1)
            .count()
            >= K
        {
            for i in 0..M {
                useable[i] &= ((s[i] >> k) & 1) == 1;
            }
            res += 1 << k;
        }
    }
    let ans = res;

    println!("{}", ans);
}


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

typedef int Capacity;
struct Edge {
    int src, dst;
    Capacity cap;
    Edge(int src_, int dst_, Capacity cap_) :
        src(src_), dst(dst_), cap(cap_) { }
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
struct Dinic {
    int n, s, t;
    vector<int> level, prog, que;
    vector<vector<Capacity>> cap, flow;
    vector<vector<int>> g;
    Capacity inf;
    Dinic(int n)
        : n(n), cap(n, vector<Capacity>(n)), flow(n, vector<Capacity>(n)),
          g(n, vector<int>()), inf(numeric_limits<Capacity>::max()/8){}
    Dinic(const Graph &graph){
        *this = Dinic(graph.size());
        for(int i = 0; i < n; i++) for(auto &e : graph[i]) addEdge(e.src, e.dst, e.cap);
    }
    void addEdge(int u, int v, Capacity c){
        cap[u][v] += c; cap[v][u] += c; flow[v][u] += c;
        g[u].push_back(v); g[v].push_back(u);
    }
    inline Capacity residue(int u, int v){ return cap[u][v] - flow[u][v]; }
    Capacity solve(int s, int t){
        this->t = t, this->s = s;
        que.resize(n+1);
        Capacity res = 0;
        while(levelize()){
            prog.assign(n, 0);
            res += augment(s, inf);
        }
        return res;
    }
    bool levelize(){
        int l = 0, r = 0;
        level.assign(n, -1); level[s] = 0;
        que[r++] = s;
        while(l != r){
            int v = que[l++];
            if(v == t) break;
            for(const int &d : g[v]){
                if(level[d] != -1 || residue(v,d) == 0) continue;
                level[d] = level[v] + 1; que[r++] = d;
            }
        }
        return level[t] != -1;
    }
    Capacity augment(int v, Capacity lim){
        Capacity res = 0;
        if(v == t) return lim;
        for(int &i = prog[v]; i < (int)g[v].size(); i++){
            const int &d = g[v][i];
            if(residue(v,d) == 0 || level[v] >= level[d]) continue;
            const Capacity aug = augment(d, min(lim, residue(v,d)));
            flow[v][d] += aug; flow[d][v] -= aug;
            res += aug; lim -= aug;
            if(lim == 0) break;
        }
        return res;
    }
};

int main(){
    int N,M;
    cin >> N >> M;
    Graph g(N);
    rep(i,M){
        int a,b,c;
        cin >> a >> b >> c;
        g[a].emplace_back(a,b,c);
    }
    Dinic ek(g);
    cout << ek.solve(0,N-1) << endl;
}

Measured memory_bytes: 1352
import java.util.Scanner;
public class Main{
	static int left(int x,int[] fee) {
		int cnt = 0;
		
		for(int i = x; i >= 0; i--) {
			for(int j = 0; j < fee.length;j++)
			if(i == fee[j]) {
				cnt++;
			}
		}
		return cnt;
	}
	static int right(int x,int n,int[] fee) {
		int cnt = 0;
		
		for(int i = x; i <=n+1; i++) {
			for(int j = 0; j < fee.length;j++)
				if(i == fee[j]) {
					cnt++;
				}
		}
		return cnt;
	}
	
	
	
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int n = stdIn.nextInt(); //マスの数-1
		int m = stdIn.nextInt(); //料金所の数
		int x = stdIn.nextInt(); //今いるマスの場所
		
		int [] fee = new int[m];
		for(int i = 0; i < m; i++) {
			fee[i] = stdIn.nextInt();
		}
		int a = left(x,fee)<right(x,n,fee)?left(x,fee):right(x,n,fee);
		System.out.println(a);
		
		
		
		
		
	}

}


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

int c[2][100001];

int main()
{
  int n;

  cin >> n;
  for(int i = 0; i < n; i++){
    int v;
    cin >> v;

    c[i%2][v]++;
  }

  int c1 = 0, c2 = 0;
  for(int i = 1; i <= 100000; i++){
    if(c[0][c1] <= c[0][i]) c1 = i;
    if(c[1][c2] <= c[1][i]) c2 = i;
  }

  int cc1 = 0, cc2 = 0;
  int ans;
  if(c1 == c2){
    for(int i = 1; i <= 100000; i++){
      if(c[0][cc1] <= c[0][i] && i != c1) cc1 = i;
      if(c[1][cc2] <= c[1][i] && i != c2) cc2 = i;
    }
    ans = n - max(c[0][cc1] + c[1][c2], c[0][c1] + c[1][cc2]);
  } else {
    ans = n - (c[0][c1] + c[1][c2]);
  }

  cout << ans << endl;

  return 0;
}

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

int main() {
  int a1, b1, c1;
  int a2, b2, c2;
  int cnt = 0;

  scanf("%d %d %d", &a1, &b1, &c1);

  if (((a1 % 2) != 0) || ((b1 % 2) != 0) || ((c1 % 2) != 0)) {
    cout << 0 << endl;
    return 0;
  } else if (a1 == c1 && a1 == b1) {
    cout << -1 << endl;
    return 0;
  }

  while (((a1 % 2) == 0) && ((b1 % 2) == 0) && ((c1 % 2) == 0)) {
    a2 = (b1 + c1) / 2;
    b2 = (c1 + a1) / 2;
    c2 = (a1 + b1) / 2;
    cnt++;
    a1 = a2;
    b1 = b2;
    c1 = c2;
  }
  cout << cnt << endl;

  return 0;
}





Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
  int n,a,i,min=1000000000,max=0;
  cin >> n;
  for (i=0;i<n;i++){
    cin >> a;
    if (min>a) min=a;
    if (max<a) max=a;
  }
  cout << max-min << endl;
  return 0;
}

Measured memory_bytes: 256
n,t=map(int,input().split())
tici=[]
for i in range(n):
	ci,ti=map(int,input().split())
	if(ti<=t):
		tici.append([ci,ti])
if(len(tici)==0):
	print('TLE')
else:
	tici.sort()
	print(tici[0][0])

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

using namespace std;
typedef long long ll;
vector<int> a;

bool is_valid(int idx, vector<int> &cnts) {
  for (int i = 0; i < 20; ++i) {
    if (a[idx] >> i & 1 && cnts[i] > 0) return false;
  }
  return true;
}

int main() {
  int n;
  cin >> n;
  a.assign(n, 0);
  for (int i = 0; i < n; ++i) cin >> a[i];

  vector<int> cnts(n, 0);
  ll ans = n;
  int right = 0;
  for (int left = 0; left < n - 1; ++left) {
    while (right < n && is_valid(right, cnts)) {
      for (int j = 0; j < 20; ++j) {
	if (a[right] >> j & 1) cnts[j]++;
      }
      right++;
    }
    ans += (right - left - 1);
    if (right == left) ++right;
    for (int j = 0; j < 20; ++j) {
      if (a[left] >> j & 1) cnts[j]--;
    }
  }
  cout << ans << endl;
  return 0;
}


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

int main() {
	int n;
	while (cin >> n, n) {
		double y; cin >> y;
		double Max = 0;
		int index;
		rep(i, n) {
			int b, t; double r; cin >> b >> r >> t;
			if (t == 1) {
				double d = 1. + y*(r / 100);
				if (Max < d) {
					Max = d;
					index = b;
				}
			}
			else {
				double d = pow(1. + r / 100, y);
				if (Max < d) {
					Max = d;
					index = b;
				}
			}
		}
		cout << index << endl;
	}
}

Measured memory_bytes: 3520
S=int(input())
a=S%100
b=(S-a)/100
if 1<=a<=12:
  if 1<=b<=12:
    print('AMBIGUOUS')
  else:
    print('YYMM')
else:
    if 1<=b<=12:
      print('MMYY')
    else:
      print('NA')

Measured memory_bytes: 2940
def main():
    from collections import defaultdict

    N = int(input())
    D = tuple(map(int, input().split()))
    M = int(input())
    T = tuple(map(int, input().split()))

    d = defaultdict(int)
    for D_ in D:
        d[D_] += 1

    for T_ in T:
        d[T_] -= 1
        if d[T_] < 0:
            return 'NO'

    return 'YES'


if __name__ == '__main__':
    print(main())


Measured memory_bytes: 41308
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

lim = 2*10**6
fact = [1]*(lim+1)
for n in range(1, lim+1):
	fact[n] = n*fact[n-1]%mod

fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod

H, W, A, B = MAP()

ans = 0
for n in range(B, W):
	way = C(H-A-1+n, n)*C(W-n-1+A-1, A-1)%mod
	ans = (ans+way)%mod

print(ans)


Measured memory_bytes: 162176