akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}


int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, 0, n) cin >> a[i];
    mint ans = 0;
    mint sum = 0;
    rep(i, 0, n-1){
        sum += a[i];
        ans += sum*a[i+1];
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4048
n = int(input())
from collections import defaultdict
d=defaultdict(int)

max_cnt=-1
for _ in range(n):
    s=input()
    d[s]+=1
    max_cnt=max(max_cnt, d[s])


ans=sorted([k for (k,v) in d.items() if v==max_cnt])
    
for a in ans:
    print(a)

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

#define M 200005
#define MOD 1000000007
#define PI 3.14159265358979323846
#define ep emplace_back
#define mk make_pair
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

typedef long long int lli;
typedef unsigned long long int ulli;
typedef pair<int,int> PII;
typedef pair<lli,lli> PLL;

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

	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);

	int a[5];
	int ans = -1;
	for(int i=0;i<5;i++)
	{
		cin>>a[i];
		if(a[i]==0)
			ans = i+1;
	}

	cout<<ans<<"\n";

		
}

Measured memory_bytes: 3584
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100009;
int fa[N],n,m;
set<int>w;
int findl(int x)
{
    return fa[x]==x?x:(fa[x]=findl(fa[x]));
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x,y,tmp,tmp1;
        scanf("%d%d",&x,&y);
        tmp=findl(x),tmp1=findl(y);
        if(tmp!=tmp1)
            fa[tmp]=tmp1;
    }
    for(int i=1;i<=n;i++)
        w.insert(findl(i));
    printf("%d",w.size()-1);
    return 0;
}


Measured memory_bytes: 8104
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using vi = vector<i64>;
using vvi = vector<vi>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout.setf(ios::fixed);
    cout.precision(10);
    int t, x;
    cin >> t >> x;
    cout << 1.0 * t / x << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
#define rep(i,n) for(ll i = 0; i < ll(n); i++)
#define reep(i,n) for(ll i = n; i >-1; i--)
#define deb(variable) cout<<#variable<<"="<<variable<<endl;
#define pb push_back
const ll INF=99999999999999999;
const ll MAX_N=100010;
ll a,b,c,d,e,x,y,m,n,l,q,ans=0;
vl v,v1,v2;
int main(){
    cin>>a>>b>>c>>d>>e;
    v.push_back((a-1)%10);
    v.push_back((b-1)%10);
    v.push_back((c-1)%10);
    v.push_back((d-1)%10);
    v.push_back((e-1)%10);
    sort(v.begin(),v.end());
    cout<<((a-1)/10+(b-1)/10+(c-1)/10+(d-1)/10+(e-1)/10)*10+40+v[0]+1<<endl;
}


Measured memory_bytes: 256
h,w=map(int,input().split())
l=[list(input()) for i in range(h)]
connection=[[] for i in range(h*w)]

for i in range(h):
  for j in range(w):
    if l[i][j]=='.':
      if i!=0:
        if l[i-1][j]!='#':
          connection[i*w+j].append((i-1)*w+j)
      if i!=h-1:
        if l[i+1][j]!='#':
          connection[i*w+j].append((i+1)*w+j)
      if j!=0:
        if l[i][j-1]!='#':
          connection[i*w+j].append(i*w+j-1)
      if j!=w-1:
        if l[i][j+1]!='#':
          connection[i*w+j].append(i*w+j+1)

n=h*w
def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

ans=[]
for i in range(h*w):
  ans.append(max(bfs(i)))
print(max(ans))

Measured memory_bytes: 42604
using System;

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

            for (var i = X; i <= 100003; i++)
            {
                if (IsPrime(i))
                {
                    Console.WriteLine(i);
                    return;
                }
            }
            Console.WriteLine(0);
        }

        public static bool IsPrime(int num)
        {
            if (num < 2) 
                return false;
            else if 
                (num == 2) return true;
            else if 
                (num % 2 == 0) return false; 

            var sqrt = Math.Sqrt(num);
            for (int i = 3; i <= sqrt; i += 2)
            {
                if (num % i == 0)
                    return false;
            }

            return true;
        }
    }
}

Measured memory_bytes: 13140
N=int(input())
A=list(map(int,input().split()))


low=0
high=10**10

#binary search the value of rain onto Mountain1
while low<=high:
    mid=(low+high)//2

    cur=mid
    for i,a in enumerate(A):
        cur=a-cur
        if cur<0:#途中で足りなくなったら、midが大きすぎ
            break
       #break
    if cur>=mid:
        low=mid+1
    else:
        if i%2==0:
            high=mid-1
        else:
            low=mid+1


ans=[]
cur=high
for a in A:
    ans.append(cur*2)
    cur=a-cur
print(" ".join(map(str,ans)))



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

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

  int r;
  cin >> r;

  if (r < 1200) cout << "ABC\n";
  else if (r < 2800) cout << "ARC\n";
  else cout << "AGC\n";

  return (0);
}


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

using namespace std;

long long a[10005];

int find1(long long a){
	return a == 0? 0 : find1(a&(a-1)) + 1;
}

int main(){
	while(1){
		int n,m;
		cin>>n>>m;
		if(n==0)break;
		memset(a,0,sizeof(a));
		int _x;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				cin>>_x;
				a[j]|=_x;
				a[j]<<=1;
			}
		}
		for(int j=0;j<m;j++){
			a[j]>>=1;
		} 
		int ans = 0;
		for(long long base = 0;base <(1<<n); base++){
			int sum = 0;
			for(int j=0;j<m;j++){
				int sum0 = find1(base ^ a[j]);
				if(sum0 > n/2) sum0 = n-sum0;
				sum += sum0;
			}
			ans = max(ans, n*m-sum);
		} 
		
		cout<<ans<<endl;
	}
	return 0;
} 


Measured memory_bytes: 3084
program knapsack_queries_on_a_tree
  implicit none
  integer, parameter :: m = 511
  integer :: n, q, u, l, i, j, k
  integer, dimension(2 ** 18 - 1) :: v = 0, w = 0
  integer(8) :: dp(0:m, 0:100000) = 0
  read(*,*) n
  do i = 1, n
    read(*,*) v(i), w(i)
  end do
  do j = 1, 100000
    do i = 1, m
      k = i / 2
      dp(i, j) = max(dp(k, j), merge(0_8, dp(k, j - w(i)) + v(i), j < w(i)))
    end do
  end do
  read(*,*) q
  do i = 1, q
    read(*,*) u, l
    write(*,'(i0)') query(u, l)
  end do
contains
  recursive integer(8) function query(i, j) result(res)
    integer, intent(in) :: i, j
    integer :: k
    if (i <= m) then
      res = dp(i, j)
      return
    end if
    k = i / 2
    res = max(query(k, j), merge(0_8, query(k, j - w(i)) + v(i), j < w(i)))
  end
end program knapsack_queries_on_a_tree

Measured memory_bytes: 404904
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;
const int MAX_N = 2 * 1e5;

struct UnionFind {

	int par[MAX_N]; // 親
	int depth[MAX_N]; // 木の深さ

	// n要素で初期化
	void init(int n) {
		rep(i, 0, n) {
			par[i] = i;
			depth[i] = 0;
		}
	}

	// 木の根を求める
	int find(int x) {
		if(par[x] == x) return x;
		else return par[x] = find(par[x]);
	}

	// xとyの属する集合を併合
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if(x == y) return;

		if(depth[x] < depth[y]) {
			par[x] = y;
		} else {
			par[y] = x;
			if(depth[x] == depth[y]) depth[x]++;
		}
	}

	// xとyが同じ集合に属するか否か
	bool same(int x, int y) {
		return find(x) == find(y);
	}
};

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

	UnionFind uf1, uf2;

	int N, K, L;
	cin >> N >> K >> L;
	uf1.init(N); uf2.init(N);

	rep(i, 0, K) {
		int p, q;
		cin >> p >> q;
		p--; q--;
		uf1.unite(p, q);
	}

	rep(i, 0, L) {
		int r, s;
		cin >> r >> s;
		r--; s--;
		uf2.unite(r, s);
	}

	vector<pair<int, int> > vp(N);
	map<pair<int, int>, int> mp;
	rep(i, 0, N) {
		vp[i].first = uf1.find(i);
		vp[i].second = uf2.find(i);
		mp[vp[i]]++;
	}

	rep(i, 0, N - 1) cout << mp[vp[i]] << " ";
	cout << mp[vp[N - 1]] << endl;



}


Measured memory_bytes: 16640
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
	int n;
	cin>>n;
	int t[100005],a[100005],b[100005];
	for(int i=1;i<=n;i++)
	{
		cin>>t[i]>>a[i]>>b[i];
	}
	int vis=0;
	for(int i=1;i<=n;i++)
	{
		if(((a[i]+b[i])>t[i]) || ((a[i]+b[i])%2)!=(t[i]%2))
		{
		    vis=2;
			break;
		}
		if(((a[i]+b[i])%2)==(t[i]%2))
		{
			vis=1;
		}
	}
	if(vis==1)  cout<<"Yes"<<endl;
	if(vis==2)  cout<<"No"<<endl;
	return 0;
}

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

const int MAXN = 1000 * 1000 + 10;
const long long INF = 1LL * 1000 * 1000 * 1000 * 1000 * 1000 * 1000 + 10;


int n;
double head[MAXN], dp[3007][3007]; //dp[coin index][number of coins];

void update(int coin_index)
{
    //cerr << "coin: " << coin_index << endl;

    //if(coin_index != 4){
        //dp[coin_index][coin_index / 2 - 1] += dp[coin_index - 2][coin_index / 2 - 3] * head[coin_index] * head[coin_index - 1];
    //}

    //dp[coin_index][coin_index / 2 - 1] += dp[coin_index - 2][coin_index / 2 - 1] * (1 - head[coin_index]) * (1 - head[coin_index - 1]);
    //dp[coin_index][coin_index / 2] += dp[coin_index - 2][coin_index / 2] * (1 - head[coin_index]) * (1 - head[coin_index - 1]);

    for(int i = 0; i < coin_index; i++){
        double add = 0.0;
        add += dp[coin_index - 2][i] * head[coin_index] * (1 - head[coin_index - 1]);
        add += dp[coin_index - 2][i] * head[coin_index - 1] * (1 - head[coin_index]);

        dp[coin_index][i + 1] += add;

        add = dp[coin_index - 2][i] * head[coin_index] * head[coin_index - 1];

        dp[coin_index][i + 2] += add;

        dp[coin_index][i] += dp[coin_index - 2][i] * (1 - head[coin_index]) * (1 - head[coin_index - 1]);

        //cerr << "i: " << i << ", i + 2: " << dp[coin_index][i + 2] << ", i + 1: " << dp[coin_index][i + 1] << endl;
    }

    dp[coin_index][coin_index + 2] = 0;
}

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

    cin >> n;

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

    dp[0][0] = 1 - head[0];
    dp[0][1] = head[0];

    dp[2][0] = dp[0][0] * (1 - head[2]) * (1 - head[1]);
    dp[2][1] += dp[0][1] * (1 - head[2]) * (1 - head[1]);
    dp[2][1] += dp[0][0] * (1 - head[2]) * (head[1]);
    dp[2][1] += dp[0][0] * (1 - head[1]) * (head[2]);
    dp[2][2] += dp[0][0] * head[2] * head[1];
    dp[2][2] += dp[0][1] * head[2] * (1 - head[1]);
    dp[2][2] += dp[0][1] * head[1] * (1 - head[2]);
    dp[2][3] += dp[0][1] * head[1] * head[2];


    for(int i = 4; i < n; i+=2){
        update(i);
    }

    double ans = 0.0;

    for(int i = n / 2 + 1; i <= n; i++){
        ans += dp[n - 1][i];
    }

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 27248
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD = 1000000007;
ll INFL = 1ll << 60;
ll INF = 1 << 30;
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[8] = {1, 1, 0, -1, -1, -1, 0, 1};

int main() {
  int a, b;
  cin >> a >> b;
  int count = 0;
  for (int i = a; i <= b; i++) {
    string s = to_string(i);
    string rs = s;
    reverse(rs.begin(), rs.end());
    if (s == rs)
      count++;
  }
  cout << count << endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long a = scanner.nextLong();
        long b = scanner.nextLong();

        long length = a + b;
        long count = 0;
        if (length == 0 || a == 0) {
            System.out.println(0);
        } else {
            count += ((long) Math.floor(n / length)) * a;
            count += Math.min(n % length, a);
            System.out.println(count);

        }

    }
}

Measured memory_bytes: 22996
#include<stdio.h>

int main(){
    int n;
    scanf("%d",&n);
    long long a[n+1],b[n+1],s=0,c;
    for(int i=0;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=0;i<n;i++){
        scanf("%lld",&b[i+1]);
        if(b[i+1]>=a[i]){
            b[i+1]-=a[i];
            s+=a[i];
        }
        else{
            s+=b[i+1];
            b[i+1]=0;
        }
        if(b[i+1]>=a[i+1]){
            s+=a[i+1];
            a[i+1]=0;
        }
        else{
            s+=b[i+1];
            a[i+1]-=b[i+1];
        }
    }
    printf("%lld\n",s);
}


Measured memory_bytes: 1664
import heapq

def pay2win():
  num = set()
  q = []
  heapq.heapify(q)
  heapq.heappush(q,( 0, N ))
  cost = N*D
  while q:
    c0, n0 = heapq.heappop(q)
    if n0 in num:
      continue
    num.add(n0)
    if n0 == 0:
      break
    if c0 >= cost:
      break
    cost = min(cost,c0+n0*D)
    #
    n2, m = divmod(n0, 2)
    if m == 0:
      heapq.heappush(q,( c0+A, n2 ))
    else:
      heapq.heappush(q,( c0+D+A, n2 ))
      heapq.heappush(q,( c0+D+A, n2+1 ))
    #
    n3, m = divmod(n0, 3)
    if m == 0:
      heapq.heappush(q,( c0+B, n3 ))
    elif m == 1:
      heapq.heappush(q,( c0+D+B, n3 ))
    else:
      heapq.heappush(q,( c0+D+B, n3+1 ))
    #
    n5, m = divmod(n0, 5)
    if m == 0:
      heapq.heappush(q,( c0+C, n5 ))
    elif m <= 2:
      heapq.heappush(q,( c0+D*m+C, n5 ))
    else:
      heapq.heappush(q,( c0+D*(5-m)+C, n5+1 ))
    #
  print(cost)
#

T = int(input())
for i in range(T):
  N,A,B,C,D = map(int, input().split())
  pay2win()
  

Measured memory_bytes: 10364
while(<>){
	chomp;
	next if($. == 1);
	@s = split(/ /, $_);
	$s[1] = sprintf("%03d", 100 - $s[1]);
	$f{"$s[0]$s[1]"} = $. - 1;
}

for (sort {$a cmp $b} keys %f){
	printf "$f{$_}" . "\n";
}

Measured memory_bytes: 512
import sys
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()))

x=INT()

for i in range(-500,501):
    for j in range(-500,501):
        if i**5-j**5==x:
            print(i,j)
            exit()

Measured memory_bytes: 9196
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(int i=a;i<=b;i++)
const int N=1e5+5;
int num;
int main()
{
	string s;
	cin>>s;
	int sz=s.size();
	rep(i,0,sz-1)
	{
		if(i==0&&s[i]!='A'){cout<<"WA";return 0;}
		if(i&&!islower(s[i])&&s[i]!='C'){cout<<"WA";return 0;}
		if(i&&s[i]=='C')
		{
			num++;
			if(i==1||i==sz-1){cout<<"WA";return 0;}
		}
	}
	if(num!=1){cout<<"WA";return 0;}
	cout<<"AC";
	return 0;
}


Measured memory_bytes: 256
// <------------- Template -----------------------> //

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
*/

#pragma optimization_level 3   									//Comment optimisations for an interatcive problem - use endl
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

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

#define fastio 			ios::sync_with_stdio(0);	cin.tie(0); cout.tie(0);  cout<<fixed;  cout<<setprecision(12);	
#define randomINT 		mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define	newl 			cout<<"\n"
#define DISP(as)		for(auto it : as) cout<<it<<" ";newl;
#define all(x)         	(x).begin(),(x).end()
#define mset(x,val)    	memset(x,val,sizeof(x))
#define newl           	cout<<"\n"
#define pb             	push_back
#define mp             	make_pair
#define f 				first
#define s 				second
#define dline          cerr<<"///REACHED///\n";
#define deb1(x)        cerr<<#x<<" = "<<x<<'\n';
#define deb2(x,y)      cerr<<'['<<#x<<','<<#y<<"] = "<<'['<<x<<','<<y<<']'<<'\n';
#define deb3(x,y,z)    cerr<<'['<<#x<<','<<#y<<','<<#z<<"] = "<<'['<<x<<','<<y<<','<<z<<']'<<'\n';

typedef long long 				ll;
typedef long double 			ld;
typedef vector<ll> 				vll;
typedef pair<ll ,ll> 			pll;
typedef pair<ld,ld> 			pld;
typedef unordered_map<ll,ll> 	um;
typedef vector<pll> 			vpll;

const ll 	MAX5 	= 	1e+5+7;
const ll 	MAX7 	= 	1e+7+7;
const ll 	MAXN 	= 	MAX7;
const ll   	INF   	=  	0x7f7f7f7f7f7f7f7f;
const int  	INFi 	=  	0x7f7f7f7f;
const ll 	MOD		=  	1e+9+7;

vll adj[MAXN];ll visit[MAXN]={};
int dx8[]={0,1,1,1,0,-1,-1,-1}, dy8[]={1,1,0,-1,-1,-1,0,1};
int dx4[]={0,1,0,-1}, dy4[]={1,0,-1,0};

// <------------- Declare Variables Here ------------> //

ll t=1;
ll n,x,m,a,y,b,k,c;
string s;

// <------------- Implement Functions Here ----------> //



// <------------- Start of main() -------------------> //

void MAIN() {
	cin>>s;
	if(s[2]==s[3] && s[4]==s[5] ) cout<<"Yes";
	else cout<<"No";
}

int main() {
	fastio;randomINT;
	//cin>>t;
	while(t--) {
		MAIN();
	}
	return 0;
}


Measured memory_bytes: 235008
// Problem : B - Crane and Turtle
// Contest : AtCoder - AtCoder Beginner Contest 170
// URL : https://atcoder.jp/contests/abc170/tasks/abc170_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>

using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N, X;
	cin >> N >> X;
	for(int i = 0; i<=N; i++){
		if(i*2 + (N-i)*4 == X){
			cout << "Yes\n";
			return 0;
		}
	}
	cout << "No\n";
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef set<int> si;
typedef set<ll> sl;
typedef pair<int,int> pii;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define per(i,a,b) for(int i=(b)-1; i>=(a); --i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define S second

const ll MOD = 1e9+7;
const int MAX = 100050;
long long fac[MAX], finv[MAX], inv[MAX];
 
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//freopen("in.txt", "r", stdin);
	COMinit();
	int n;
	cin >> n;
	vi a(n+2);
	rep(i,1,n+2) {
		cin >> a[i];
	}
	set<int> r;
	int p, q;
	rep(i,1,n+2) {
		if(r.find(a[i]) != r.end()) {
			q = i;
			break;
		} else {
			r.insert(a[i]);
		}
	}
	rep(i,1,n+2) {
		if(a[i] == a[q]) {
			p = i;
			break;
		}
	}

	rep(k,1,n+2) {
		ll ret = (COM(n+1, k) - COM(n-q+p, k-1) + MOD) % MOD;
		cout << ret << '\n';
	}
	return 0;
}


Measured memory_bytes: 8704
///Bismillahir Rahmanir Rahim
#include "bits/stdc++.h"

#define                           ll                          long long
#define                           int                         ll
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<ll,ll>
#define                           clr(x)                      memset(x,0,sizeof(x));
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           show(x,y)                   cout<<x<<" : ";for(auto z:y)cout<<z<<" ";cout<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const ll inf=1e18;
const int mod=1e9+7;
const int M=100005;

 main()

{
    fast
    int d,t,s;
    cin>>d>>t>>s;
    if(s*t>=d)
    {
        cout<<"Yes\n";
    }
    else
    {
        cout<<"No\n";
    }
    return 0;

}





































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

char lower(char c){
  if('A' <= c && c <= 'Z') c = c - 'A' + 'a';
  return c;
}

int main(){
  string w,t;
  int flag,count = 0;
  int i;
  cin >> w;
  while(1){
    cin >> t;
    if(t == "END_OF_TEXT") break;
    flag = 1;
    if(w.size() != t.size()) flag = 0;
    else{
      for(i = 0;i < w.size(); i++){
        if(lower(w[i]) != lower(t[i])) flag = 0;
      }
    }
    if(flag) count += 1;
  }
  printf("%d\n", count);
}


Measured memory_bytes: 3340
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
/*
    s.find_by_order(k) ---> returns iterator to the element at index(from 0) k
    s.order_of_key(val) ---> number of elements that are strictly smaller than the given value
*/
typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<long long int> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long int>> vvl;
typedef pair<int, int> pii;
typedef pair<long long int, long long int> pll;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long int, long long int>> vll;
#define fastIO() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define test() long long int tc; cin >> tc; cin.ignore(); while(tc--) 
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define MOD 1000000007
#define SMOD 998244353
#define HASH 18014398241046527
#define pq priority_queue
#define all(x) x.begin(),x.end()
#define SP(x) setprecision(x)
#define sp " "
#define inp(a) ll a;cin>>a;cin.ignore()
#define inps(a,b) ll a,b;cin>>a>>b;cin.ignore()
#define out(a) cout<<SP(20)<<a<<'\n'
#define outs(a,b) cout<<SP(20)<<a<<" "<<b<<'\n'
#define ins insert
#define er erase
#define lb lower_bound
#define ub upper_bound
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define inpa(a,n) ll a[n]; for(int i=0; i<n; i++){cin>>a[i];}
#define inpv(a,n) vl a; for(int i=0; i<n; i++){inp(x);a.pb(x);}
#define outa(a,n) for(int i=0;i<n;i++){cout<<a[i]<<" ";}cout<<'\n';
#define outv(v) for(auto i:v){cout<<i<<" ";}cout<<'\n';
set<char> vow = {'a','e','i','o','u','A','E','I','O','U'};
ll xpow(ll n, ll m){if(m==0){return 1;}else{ll x = xpow(n, m/2);if(m&1){return x*x*n;}else{return x*x;}}}
ll xmod(ll a, ll m){return (((a%m)+m)%m);}
ll xmodpow(ll n, ll m, ll y){if(m==0){return 1;}else{ll x = xmodpow(n, m/2, y);if(m&1){return xmod((xmod((xmod(x,y)*xmod(x,y)),y)*xmod(n,y)),y);}else{return xmod((xmod(x,y)*xmod(x,y)),y);}}}
template <typename T>
ll SIZEOF(T a){return (ll)a.size();}
ll xlcm(ll a, ll b){return (a/__gcd(a, b))*b;}

ll dx[] = {1, 0, -1, 0};
ll dy[] = {0, 1, 0, -1};





void SOLVE(){
    inp(n);
    map <string, ll> m;
    for(ll i=0; i<n; i++){
        string s;
        cin >> s;
        m[s]++;
    }
    cout << "AC x " << m["AC"] << '\n';
    cout << "WA x " << m["WA"] << '\n';
    cout << "TLE x " << m["TLE"] << '\n';
    cout << "RE x " << m["RE"] << '\n';
}

int main() {
	fastIO();
	// #ifndef ONLINE_JUDGE
    //     freopen("i.txt", "r", stdin);
    //     freopen("o.txt", "w", stdout);
	// #endif

    ll TC = 1;
    // cin >> TC;
    for(ll tc1=1; tc1<=TC; tc1++){
        // cout << "Case #" << tc1 << ": ";
        SOLVE();
    }
    printclock;
}

Measured memory_bytes: 3828
#include <iostream>

using namespace std;
typedef long long ll;

ll N, K, aux, ans, cnt;

int main ()
{
	cin >> N >> K;
	
	aux = (N / K);
	ans = (aux * aux * aux);
	if ( K % 2 == 0 )
	{
		if ( N % K >= K / 2 )
			aux++;
		ans += (aux * aux * aux);
	}
	cout << ans << "\n";
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 510000;
const int V = 100005;
ll dy[8] = {0,1,0,-1,1,-1,1,-1};
ll dx[8] = {1,0,-1,0,1,-1,-1,1};
const double pi = acos(-1);
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << endl;}
#define INT_MAX 1<<30
const int mod = 1e9+7;



int main(){
    ll k; cin >> k;
    vector<vpl> G(k);
    rep(i,k){
        if(i<k-1) G[i].emplace_back(i+1,1);
        else G[k-1].emplace_back(0,1);
    } 
    ll tmp = 1;
    rep(i,11){
        tmp *= 10;
        rep(j,k){
            ll t = j*(tmp%k)%k;
            G[j].emplace_back(t,0);
        }
    }
    priority_queue<P,vector<P>,greater<P>> pq;
    pq.emplace(1,1);
    vl d(k,inf);
    d[1] = 1;
    while(!pq.empty()){
        P p = pq.top(); pq.pop();
        ll u = p.second;
        for(auto v : G[u]){
            if(d[v.first] > d[u] + v.second){
                d[v.first] = d[u] + v.second;
                pq.emplace(d[v.first],v.first);
            }
        }
    }
    cout << d[0] << endl;
}


Measured memory_bytes: 31872
#include<stdio.h>
int fibonacci(int);
int fib[45];
int main(){
  int n,i;
  scanf("%d",&n);
  for(i = 0; i < 45; i++) fib[i] = -1;
  printf("%d\n",fibonacci(n));
  return 0;
}

int fibonacci(int n){
  if(n == 0 || n == 1) return fib[n] = 1;
  if(fib[n] != -1) return fib[n];
  return fib[n] = fibonacci(n-1) + fibonacci(n-2);
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) (int)(x.size())
#define REP(i, n) for(int i=0;i<(n);++i)
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RREP(i, n) for(int i=(int)(n)-1;i>=0;--i)
#define RFOR(i, a, b) for(int i=(int)(b)-1;i>=(a);--i)
#define ALL(a) a.begin(),a.end()
#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;
const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
template <typename T1, typename T2>
bool chmax(T1 &a, const T2 &b) {
    if (a < b) { a = b; return true; }
    return false;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2 &b) {
    if (a > b) { a = b; return true; }
    return false;
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "[";
    REP(i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &mp) {
    os << "{";
    int a = 0;
    for (auto &tp : mp) {
        if (a) os << ", "; a = 1;
        os << tp;
    }
    return os << "}";
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    os << p.first << ":" << p.second;
    return os;
}

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

    const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
    const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};

    for (;;) {
        int H, W; cin >> H >> W;
        if (H == 0) break;
        vector<string> S(H);
        REP(i, H) cin >> S[i];
        map<string,int> mp;

        REP(si, H) REP(sj, W) {
            REP(k, 8) {
                string s;
                int i = si, j = sj;
                do {
                    s += S[i][j];
                    mp[s] += 1;
                    (i += H + di[k]) %= H;
                    (j += W + dj[k]) %= W;
                } while (i != si or j != sj);
            }
        }
        int maxlen = 0;
        for (auto &tp : mp) {
            if (tp.second > 1) {
                chmax(maxlen, tp.first.size());
            }
        }
        if (maxlen == 1) {
            cout << 0 << endl;
            continue;
        }

        string ans;
        for (auto &tp : mp) {
            if (tp.second > 1 and tp.first.size() == maxlen) {
                ans = tp.first;
                break;
            }
        }
        cout << ans << endl;

    }

    return 0;

}



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

struct abtyp {int a; long b;};

int asbc(const void *x, const void *y) {
  return (*(struct abtyp *)x).b - (*(struct abtyp *)y).b;
}

int main(){
   int i,n,t;
   struct abtyp ab[200000];
    
   scanf("%d",&n);
   for (i=0;i<n;i++) scanf("%d %d",&(ab[i].a),&(ab[i].b));
   qsort(ab,n,sizeof(struct abtyp),asbc);

   for (t=i=0;i<n;i++) {
      t+=ab[i].a;
      if (t>ab[i].b) {
         puts("No");
         return 0;
      }
   }
   puts("Yes");
   return 0;
}


Measured memory_bytes: 6396
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
#include <iomanip>
#include <functional>
#include <queue>
#include <stack>
#include <cmath>
#define INF 10000000000000000
#define MOD 1000000007
using namespace std;




int main(){
    int a,b,c;
    cin >> a>>b>>c;
    int k;
    cin>>k;
    int x=1;
    for(int i=0; i<k; i++){
        x*=2;
    }
    
    cout<<max(a*x+b+c,max(a+b*x+c,a+b+c*x))<<endl;
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>

using namespace std;

bool pred(const pair<int,string> &left, const pair<int,string> &right){
  if(left.first != right.first){
    return left.first < right.first;
  }else{
    return left.second < right.second;
  }
}

int main(void){
  int n;
  while(cin >> n && n){
    bool table[40][40]; 
    vector< pair<int,string> > person(n);
    memset(table, false, sizeof(table));
    int d,tmp;

    for(int i=0;i<n;i++){
      person[i].first = 0;
      cin >> person[i].second >> d;
      for(int j=0;j<d;j++){
	cin >> tmp;
	table[i][tmp] = true;
      }
    }

    int cnt;
    for(int i=0;i<30;i++){
      cnt = 0;
      for(int j=0;j<n;j++){
	if(table[j][i]) cnt++;
      }
      for(int j=0;j<n;j++){
	if(table[j][i]) person[j].first += n - cnt + 1;
      }
    }
    sort(person.begin(), person.end());
    cout << person[0].first << " " <<  person[0].second << endl;
  }
}

Measured memory_bytes: 0
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M = list(map(int, sys.stdin.buffer.readline().split()))
S = sys.stdin.buffer.readline().decode().rstrip()
T = sys.stdin.buffer.readline().decode().rstrip()

g = gcd(N, M)
ok = True
for c, d in zip(S[::N//g], T[::M//g]):
    ok &=c == d
if ok:
    print(N*M//g)
else:
    print('-1')



Measured memory_bytes: 13624
n = int(input())

s = {}
for i in range(n):
  a = input()
  if a in s:
    s[a] += 1
  else:
    s[a] = 1

max = max(s.values())
s = sorted(s.items())
for i in s:
  if i[1] == max:
    print(i[0])


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

int main(){
    ll n,h;cin>>n>>h;
    ll ans=0;
    ll max_a=0;
    ll max_a_b=0;
    vector<ll> b;
    for(int i=0;i<n;i++){
        ll aa,bb;cin>>aa>>bb;
        if(max_a<aa){
            max_a=aa;
            b.push_back(max_a_b);
            max_a_b=bb;
        }
        else if(max_a==aa){
            if(max_a_b>bb){
                b.push_back(max_a_b);
                max_a_b=bb;
            }
            else b.push_back(bb);
        }
        else b.push_back(bb);
    }
    sort(b.begin(),b.end(),greater<ll>());
    for(int i=0;i<n-1;i++){
        if(b[i]<max_a) break;
        h-=b[i];
        ans++;
        if(h<=0) break;
    }
    if(h<=0) ans--;
    h-=max_a_b;ans++;
    while(true){
        if(h<=0) break;
        h-=max_a;
        ans++;
    }
    cout<<ans<<endl;
}

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

using namespace std;

int main(){

    int n, point, out;
    bool base[3];
    string ivent;

    cin >> n;

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

        point = 0;
        out = 0;
        memset(base, false, sizeof(base));

        while(out < 3){

            cin >> ivent;

            if(ivent == "HIT"){

                if(base[2]) point++;
                for(int j = 2; j >= 0; --j)
                    base[j] = base[j - 1];
                base[0] = true;

            }
            else if(ivent == "HOMERUN"){

                for(int j = 0; j < 3; ++j)
                    if(base[j]) ++point;
                ++point;
                memset(base, false, sizeof(base));

            }
            else if(ivent == "OUT"){

                ++out;

            }

        }

        cout << point << endl;

    }

}

Measured memory_bytes: 1208
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define Rep(i,a,b) for(register int i=(a);i<=int(b);++i)
#define Dep(i,a,b) for(register int i=(a);i>=int(b);--i)
#define rep(i,a,b) for(register int i=(a);i<int(b);++i)
#define mem(x,v) memset(x,v,sizeof(x))
#define gc getchar
#define pc putchar
#define fi first
#define se second
#define debug(x) cout << #x" = " << x << endl;
#define pp(x,y) cout << "pp: " << x << " " << y << endl;
#define rank __RANK
inline ll read(){
	register ll x=0,f=1;register char c=gc();
	for(;!isdigit(c);c=gc())if(c=='-')f=-1;
	for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);
	return x*f;
}
#define rd read
void write(ll x){if(x<0)x=-x,pc('-');if(x>=10)write(x/10);putchar(x%10+'0');}
void writeln(ll x){write(x);puts("");}
const int maxn = 2005;
const int mod = 1e9+7;
int f[maxn][maxn],n,k;
int main(){
	n = rd(),k = rd();
	f[1][0] = 1;
	Rep(i,1,k){
		Rep(j,i,n){
			f[i][j] = f[i-1][j];
			if(j!=0) (f[i][j] += f[i][j-1])%=mod;
		} 
	}
	ll ans = f[k][n];
	Rep(i,1,n-k-1)ans=ans*2%mod;
	writeln(ans);
}


Measured memory_bytes: 15360
#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
#define ip(arr, n) for(int i=0; i<n; i++) cin>>arr[i];
#define op(arr, n) for(int i=0; i<n; i++) cout<<arr[i]<<" ";
#define fstIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define MAX 3005

int n;
ll *arr, dp[MAX][MAX];

ll solve(int i, int j){
    if(i>j) return 0;
    if(dp[i][j] != -1) return dp[i][j];

    ll opt1 = arr[i]-solve(i+1, j);
    ll opt2 = arr[j]-solve(i, j-1);

    return dp[i][j] = max(opt1, opt2);
}

void topDown(){
    memset(dp, -1, sizeof(dp));
    cout<<solve(0, n-1)<<endl;
}

int main(){
    fstIO;
    cin>>n;
    arr = new ll[n+1];
    ip(arr, n);
    topDown();
    return 0;
}

Measured memory_bytes: 71040
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define MOD (1000000007)
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vi>
#define vvl vector<vl>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pb push_back

#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

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

ll keta(ll n){
  string s = to_string(n);
  ll num = s.size();
  return num;
}

const ll INF = 1LL << 60;

const int dh[4] = {1,0,-1,0};
const int dw[4] = {0,1,0,-1};

struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w){}
};
using Graph = vector<vector<Edge>>;
using P = pair<ll, int>;

void dfs(int v, vvi &G, vb &seen){
  if(seen[v]) return;
  seen[v] = true;
  for(auto nv : G[v]) {
    dfs(nv, G, seen);
  }
}
int main(){
  int n,m,p; cin >> n >> m >> p;
  vvi G(n),rG(n);
  vector<tuple<int,int,int>> edges;
  rep(i,m) {
    int a,b,c; cin >> a >> b >> c;
    a--; b--;
    c -= p;
    c = -c;
    edges.emplace_back(a,b,c);
    G[a].pb(b);
    rG[b].pb(a);
  } 

  vb seen1(n,false),seen2(n,false),ok(n);

  dfs(0, G, seen1);
  dfs(n-1, rG, seen2);

  rep(i,n) ok[i] = seen1[i]&seen2[i];

  vi dist(n,1e9);
  dist[0] = 0;
  int step = 0;
  for(bool upd = true; upd; step++) {
    upd = false;
    rep(i,m) {
      int a,b,c;
      tie(a,b,c) = edges[i];
      if(!ok[a] || !ok[b]) continue;
      if(chmin(dist[b], dist[a] + c)) upd = true;
      if(step > n){
        cout << -1 << endl;
        return 0;
      }
    }
  }
  
  cout << max(-dist[n-1],0) << endl;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
#define il inline
#define RG register
#define ll long long
#define N (100005)

using namespace std;

struct edge{ int nt,to; }g[N<<1];

int head[N],vis[N],col[N],fa[N],st[N],sz[N],k[N],S,T,n,m,num,tot,top,res,ans,fg;

il int gi(){
  RG int x=0,q=1; RG char ch=getchar();
  while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
  if (ch=='-') q=-1,ch=getchar();
  while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
  return q*x;
}

il void insert(RG int from,RG int to){
  g[++num]=(edge){head[from],to},head[from]=num; return;
}

il void dfs(RG int x,RG int p){
  vis[x]=1,col[x]=col[p]^1;
  tot+=(sz[x]=col[x]?1:-1);
  for (RG int i=head[x],v;i;i=g[i].nt){
    v=g[i].to; if (v==p) continue;
    if (!vis[v]) dfs(v,x);
    else S=x,T=v,fg=col[x]==col[v];
  }
  return;
}

il void find(RG int x,RG int p){
  for (RG int i=head[x],v;i;i=g[i].nt){
    v=g[i].to; if (v==p) continue;
    if (x==S && v==T) continue;
    if (x==T && v==S) continue;
    find(v,x),sz[x]+=sz[v],k[x]+=k[v];
  }
  return;
}

int main(){
  n=gi(),m=gi();
  for (RG int i=1,u,v;i<=m;++i)
    u=gi(),v=gi(),insert(u,v),insert(v,u);
  dfs(1,0); if (m==n-1 && tot) puts("-1"),exit(0);
  if (m==n && fg && (abs(tot)&1)) puts("-1"),exit(0);
  if (m==n && !fg && tot) puts("-1"),exit(0);
  if (m==n && fg) sz[S]-=tot/2,sz[T]-=tot/2,ans=abs(tot)/2;
  if (m==n && !fg) k[S]=1,k[T]=-1; find(1,0);
  for (RG int i=1;i<=n;++i)
    !k[i]?(ans+=abs(sz[i])):(st[++top]=k[i]*sz[i]);
  st[++top]=0,sort(st+1,st+top+1),res=st[(top+1)>>1];
  for (RG int i=1;i<=top;++i) ans+=abs(st[i]-res);
  cout<<ans; return 0;
}


Measured memory_bytes: 6656
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long A,v,B,w,t;
  cin >> A >> v >> B >> w >> t;
  long long x1=0,x2=0;
  if(A < B){
    x1 = A + v*t;
    x2 = B + w*t;
    if(x1 >= x2){
      cout << "YES" << endl;
    }
    else{
      cout << "NO" << endl;
    }
  }
  else if(A > B){
    x1 = A - v*t;
    x2 = B - w*t;
    if(x1 <= x2){
      cout << "YES" << endl;
    }
    else{
      cout << "NO" << endl;
    }
  }
  else{ //A = B
    cout << "YES" << endl;
  }    
    
}



Measured memory_bytes: 3624
' Imports System.Collections.Generic
' Imports System.Text.RegularExpressions

Class Main
    Public Shared Sub Main()
        Dim S As String = Console.ReadLine()
        Console.WriteLine(7 - Array.IndexOf({"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"}, S))
        Return
    End Sub
End Class


Measured memory_bytes: 25808
#include<bits/stdc++.h>
using namespace std;
#define cs const
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
#define bg begin

namespace IO{

cs int RLEN=1<<22|1;
char ibuf[RLEN],*ib,*ob;
inline char gc(){
	(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob)?EOF:*ib++;
}
inline int read(){
	char ch=gc();
	int res=0;bool f=0;
	while(!isdigit(ch))f=ch=='-',ch=gc();
	while(isdigit(ch))res=(res*10)+(ch^48),ch=gc();
	return f?-res:res;
}
inline ll readll(){
	char ch=gc();
	ll res=0;bool f=0;
	while(!isdigit(ch))f=ch=='-',ch=gc();
	while(isdigit(ch))res=(res*10)+(ch^48),ch=gc();
	return f?-res:res;
}
inline int readstring(char *s){
	int top=0;char ch=gc();
	while(isspace(ch))ch=gc();
	while(!isspace(ch)&&ch!=EOF)s[++top]=ch,ch=gc();
	s[top+1]='\0';return top;
}

}
using IO::read;
using IO::readll;
using IO::readstring;

template<typename tp>inline void chemx(tp &a,tp b){(a<b)?(a=b):0;}
template<typename tp>inline void chemn(tp &a,tp b){(a>b)?(a=b):0;}

cs int mod=1e9+7;
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(int a,int b){return a<b?a-b+mod:a-b;}
inline int mul(int a,int b){return (ll)a*b%mod;}
inline void Add(int &a,int b){a=a+b>=mod?a+b-mod:a+b;}
inline void Dec(int &a,int b){a=a<b?a-b+mod:a-b;}
inline void Mul(int &a,int b){a=(ll)a*b%mod;}
inline int ksm(int a,int b,int res=1){for(;b;b>>=1,Mul(a,a))if(b&1)Mul(res,a);return res;}

cs int N=5005;
int f[N][2],g[N][2],s[N];
int n,a,b;
int main(){
	#ifdef Stargazer
	freopen("lx.in","r",stdin);
	#endif
	n=read(),a=read(),b=read();
	if(a>b)swap(a,b);
	f[0][0]=f[0][1]=1;
	for(int i=1;i<=n;i++)
	for(int t=0;t<2;t++)
	for(int j=(t?1:a);j<=i;j++)Add(f[i][t],f[i-j][t^1]);
	s[0]=1;
	for(int i=1;i<=n;i++)s[i]=add(f[i][0],f[i][1]);
	int res=0;
	for(int i=1;i<n;i++){
		if(i<a)Add(g[i][0],1);
		for(int j=1;j<min(i,a);j++)Add(g[i][0],g[i-j][1]);
		if(i<b)Add(g[i][1],s[i-1]);
		for(int j=1;j<min(i,b);j++)
		Add(g[i][1],mul(j==1?1:s[j-2],g[i-j][0]));
		if(n-i<b)Add(res,mul(g[i][0],s[n-i-1]));
		if(n-i<a)Add(res,g[i][1]);
	}cout<<dec(ksm(2,n),res)<<'\n';return 0;
}

Measured memory_bytes: 3736
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	int n; scanf("%d", &n);
	std::string s; cin >> s;

	int ans = 0;
	for(int i = 0; i < (int)s.size() - 2; i++) {
		ans += (s.substr(i, 3) == "ABC");
	}
	
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100003,INF=1<<30;

int main(){
    
    int N;
    string S;cin>>N>>S;
    map<pair<string,string>,ll> M;
    
    for(int bit=0;bit<(1<<N);bit++){
        string A,B;
        for(int i=0;i<N;i++){
            if(bit&(1<<i)) A+=S[i];
            else B+=S[i];
        }
        M[make_pair(A,B)]++;
    }
    
    ll ans=0;
    
    for(int bit=0;bit<(1<<N);bit++){
        string A,B;
        for(int i=0;i<N;i++){
            if(bit&(1<<i)) A+=S[2*N-1-i];
            else B+=S[2*N-1-i];
        }
        if(M[make_pair(A,B)]) ans+=M[make_pair(A,B)];
    }
    
    cout<<ans<<endl;
    
    
}




Measured memory_bytes: 91904
#include<bits/stdc++.h>
 
using namespace std;
using S = set<long long>;
using D = deque<long long>;
using L = vector<long long>;
using M = map<int,long long>;
using A = vector<vector<long long>>;
using Q = priority_queue<long long>;
using U = unordered_map<int,long long>; //mapとの違いはkeyの順番を保持していない

#define sorted(vector) sort(vector.begin(),vector.end()) //O(nlongn)
#define vmin(vector) *min_element(vector.begin(),vector.end()) //O(N)
#define vmax(vector) *max_element(vector.begin(),vector.end()) //O(N)
#define vsum(vector) accumulate(vector.begin(),vector.end(),0) //O(N)
#define vcount(vector,a) count(vector.begin(), vector.end(),a) //O(N)
#define bisect_left(vector,a) (lower_bound(vector.begin(),vector.end(),a)-vector.begin())
#define bisect_right(vector,a) (upper_bound(vector.begin(),vector.end(),a)-vector.begin())
#define vfind(vector,a) find(vector.begin(), vector.end(), a) != vector.end() //遅いからあんまり使うな
//存在確認はmap!!!!!!!!!!!!!か配列に埋め込んでcontinueで回避
//__gcd(a,b)はコンパイラがGCC時のみ

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    long long w,h,x,y;
    cin>>w>>h>>x>>y;
    cout<<w*h/2.0<<" ";
    if (x*2==w and y*2==h){
        cout<<"1"<<endl;
    }else{
        cout<<"0"<<endl;
    }
}
    


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e7 + 1;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
typedef long long int ll;
typedef vector<ll> vi;
typedef vector < pair<ll, ll > > vp;
typedef vector <string> vs;
typedef vector <char> vc;
typedef list <ll> lst;

ll n, m, k, ans = 0, sum = 0, cnt = 0;
string s;
char c;

#define Endl endl

/*--------------------template--------------------*/

int main()
{
	cin >> n;
	vi v(n);
	REP(i, n) cin >> v[i];
	REP(i, n)
	{
		if (v[i] % 4 == 0) {
			cnt++;
		} else if (v[i] % 2 == 0) {
			sum++;
		}
	}
	cnt += sum / 2;
	if (cnt >= n / 2) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 1024