akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<cstdio>
#include<stack>
#include<queue>
#include<fstream>
#include<cstdio>
#include<deque>
#include<iomanip>
#include <numeric>

using namespace std;
#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);(i)--)
#define all(a) (a).begin(),(a).end()
#define reall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
const double pi = acos(-1.0);

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef deque<ll> dll;
typedef pair<string, int> P;
#define mod 1e9 + 7;
ll gcd(ll x, ll y)
{
	ll r;
	while ((r = x % y) != 0)
	{
		x = y;
		y = r;
	}
	return y;
}
ll lcm(ll x, ll y)
{
	x /= gcd(x, y);
	y /= gcd(x, y);
	return (x * y);
}

string in;
int v[510][510];
int main()
{
	ios_base::sync_with_stdio(false);
	ll n,x,ret=0;
	cin >> n >> x;
	REP(i,1, n+1) {
		REP(j,1, x+1) {
			cin >> v[i][j];
		}
	}
	vvi q;
	REP(i, 1, n + 1) {
		REP(j, 1, x + 1) {
			if (v[i][j] % 2 == 1) {
				if (i + 1 <= n) {
					q.pb({ i,j,i + 1,j });
					v[i + 1][j]++;
				}
				else if (j + 1 <= x) {
					q.pb({ i,j,i,j + 1 });
					v[i][j + 1]++;
				}
			}
		}
	}
	cout << q.size() << endl;
	rep(i, q.size()) {
		cout << q[i][0] << " " << q[i][1] << " " << q[i][2] << " " << q[i][3] << endl;
	}
	return 0;
}

Measured memory_bytes: 10032
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <bitset>
#include <stack>
#include <deque>
#include <set>
#include <unordered_set>
#include <list>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <climits>
#include <ctime>
#include <random>
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define eps 1e-9
#define inf 0x3f3f3f3f
#define mod 1000000007
using namespace std;

const int MSIZE = 2e5 + 5;

int parent[MSIZE];
int dsu_size[MSIZE];
int cnt;

void init() {
	for (int i = 0; i < MSIZE; ++i) {
		parent[i] = i;
		dsu_size[i] = 1;
	}
}

int get(int v) {
	if (parent[v] == v)return v;
	return parent[v] = get(parent[v]);
}

void dsu_union(int a, int b) {
	a = get(a), b = get(b);
	if (a == b)
		return;
	if (dsu_size[a] > dsu_size[b])
		swap(a, b);
	dsu_size[b] += dsu_size[a];
	parent[a] = b;
	--cnt;
}

int main() {
	speed;
	int n, m, a, b;
	cin >> n >> m;
	init();
	for (int i = 0; i < m; ++i) {
		cin >> a >> b;
		dsu_union(a, b);
	}
	int mx = 0;
	for (int i = 1; i <= n; ++i)
		mx = max(mx, dsu_size[get(i)]);
	cout << mx;
}

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> A(M);

  for (int i = 0; i < N; i++) {
      int K;
      cin >> K;
      for (int j = 0; j < K; j++) {
          int x;
          cin >> x;
          A.at(x-1)++;
      }
  }

  int count = 0;
  for (int i = 0; i < M; i++) {
      if(A.at(i)==N) count++;
  }
  cout << count << endl;
}


Measured memory_bytes: 256
# ARC097D - Equals
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(v: int, color: int) -> None:
    group[v] = color  # make vertex v searched
    for u in G[v]:  # search vertices available from v recursively
        if not group[u]:  # skip if already searched
            dfs(u, color)


def main():
    # check i and Pi are connected components or not
    global G, group
    N, M = tuple(map(int, input().split()))
    P = tuple(map(int, input().split()))
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    G = [[] for _ in range(N + 1)]  # construct a graph (1-idx)
    for v, u in E:
        G[v] += [u]
        G[u] += [v]
    group = [0] * (N + 1)
    color = 1
    for v in range(1, N + 1):  # connected components are in the same group
        if not group[v]:
            dfs(v, color)
            color += 1
    ans = sum(group[i] == group[p] for i, p in enumerate(P, 1))
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 90168
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &&x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define INSEG(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void PSUM(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

int dp[100002];
signed main() {
    REP(i, 100002) dp[i] = INF;
    int n;
    cin >> n;
    vector<int> h(n);
    cin >> h;
    dp[0] = 0;
    REP(i, n) {
        if (i + 1 < n) chmin(dp[i + 1], dp[i] + abs(h[i] - h[i + 1]));
        if (i + 2 < n) chmin(dp[i + 2], dp[i] + abs(h[i] - h[i + 2]));
    }
    cout << dp[n - 1] << endl;
    return (0^_^0);
}



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



Measured memory_bytes: 3088
X,Y = map(str,input().split())
XY = ["A","B","C","D","E","F"]
for i in range(6):
    if X == XY[i]:
        XX = i
    if Y == XY[i]:
        YY = i
if XX == YY:
    print("=")
elif XX > YY:
    print(">")
else:
    print("<")

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue> 

using namespace std;
#define rep(i, s, e) for (int(i) = (s); (i) <= (e); ++(i))
#define all(x) x.begin(),x.end()

#pragma region UnionFind
struct UnionFind
{
	vector<int> par;

	UnionFind(int n) : par(n, -1) {}
	void init(int n) { par.assign(n, -1); }

	int root(int x)
	{
		if (par[x] < 0) return x;
		else return par[x] = root(par[x]);
	}

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

	void merge(int x, int y)
	{
		x = root(x); y = root(y);
		if (x == y) return;
		if (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return;
	}

	int size(int x)
	{
		return -par[root(x)];
	}
};
#pragma endregion

int main()
{
	int n, m; cin >> n >> m;
	vector<int> p(n + 1);
	p[0] = 0;
	rep(i, 1, n)cin >> p[i];
	UnionFind uf(n + 1);
	rep(i, 0, m - 1)
	{
		int a, b;
		cin >> a >> b;
		uf.merge(a, b);
	}
	int res = 0;
	rep(i, 1, n)
	{
		if (uf.issame(p[i], i)) ++res;
	}
	cout << res << endl;
}

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

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

  sort(a, a+n);
  sort(b, b+n);

  int ans;
  if(n%2==1) {
    int mi = a[(n-1)/2];
    int ma = b[(n-1)/2];
    ans = ma-mi+1;
  }
  else {
    double mi = (a[n/2-1]+a[n/2])/2.0;
    double ma = (b[n/2-1]+b[n/2])/2.0;
    ans = 2*(ma-mi) +1;
  }


  cout<<ans<<endl;

  return 0;
}

Measured memory_bytes: 5116
package main

import (
    "fmt"
    "math"
)

func square(x float64) float64 {
    return x * x
}

func main () {
  var a,b,h,m int
  fmt.Scan(&a, &b, &h, &m)

  var m_theta, h_theta float64

  //fmt.Print(a, b, h ,m)
  
  m_theta = math.Pi * float64(m) / 30.0
  h_theta = math.Pi * (float64(h) / 6.0 + float64(m) / 360.0)
  
  dist := math.Sqrt(square(float64(a) * math.Sin(h_theta) - float64(b) * math.Sin(m_theta)) + square(float64(a) * math.Cos(h_theta) - float64(b) * math.Cos(m_theta)))
  fmt.Print(dist)
}

Measured memory_bytes: 1824
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int N;
    cin>>N;
    int a[N+1]={0};
    int b[N+1]={0};
    for(int i=2;i<=N;i++){
        cin>>a[i];
        b[a[i]]++;
    }
    for(int i=0;i<N;i++){
        if(i+1==N)cout<<"0\n";
        else cout<<b[i+1]<<"\n";
    }
}

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

int main()
{
    int a,b;

    cin >> a >> b;

    double n = (a+b)/2.0;
    int m = (int)(n*10)%10;
    if(m > 0) cout << (int)n+1 << endl;
    else cout << (int)n << endl;

    return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
p=10**9+7
if abs(n-m)>=2:
    print(0)
elif n==m:
    ans=1
    for i in range(1,n+1):
        ans=(ans*i)%p
    print((2*ans*ans)%p)
else:
    ans=1
    for i in range(1,n+1):
        ans=(ans*i)%p
    for i in range(1,m+1):
        ans=(ans*i)%p
    print(ans%p)


Measured memory_bytes: 63612
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
mod = 10**9 + 7
factorial = [1]*(n+1)
factorial_inv = [1]*(n+1)
for i in range(1,n+1):
    factorial[i] = factorial[i-1]*i%mod
factorial_inv[n] = pow(factorial[n],mod-2,mod)
for i in range(n,0,-1):
    factorial_inv[i-1] = factorial_inv[i]*i%mod

pa = [0]*(n+1)
dp = [1]*(n+1)
size = [1]*(n+1)
checked = []
stack = [i]
while stack:
    a = stack.pop()
    checked.append(a)
    for j in graph[a]:
        if pa[a] == j:   
            continue
        else:
            stack.append(j)
            pa[j] = a

for i in checked[::-1]:
    p = pa[i]
    s = size[i]
    dp[i] *= factorial[s-1]
    dp[i] %= mod
    dp[p] *= dp[i]*factorial_inv[s]
    dp[p] %= mod
    size[p] += s

size_ = [n-i+1 for i in size]
dp_ = [1]*(n+1)
for i in checked[1:]:
    p = pa[i]
    dp_[i] *= dp[p]
    dp_[i] *= factorial_inv[size[p]-1]
    dp_[i] *= pow(dp[i],mod-2,mod)
    dp_[i] *= factorial[size[i]]
    dp_[i] *= dp_[p]
    dp_[i] *= factorial_inv[size_[p]-1]
    dp_[i] *= factorial[size_[i]-2]
    dp_[i] %= mod
    
for i in range(1,n+1):
    ans = factorial[n-1]*dp[i]*dp_[i]*factorial_inv[size[i]-1]*factorial_inv[size_[i]-1]
    ans %= mod
    print(ans)

Measured memory_bytes: 83048
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,s,n) for(int i=s;i<=n;i++)
ll mod=1e9+7;

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

	int i = 0;
	while(1){
		if(a <= 0){
			cout << "No\n";
			break;
		}

		if(c <= 0){
			cout << "Yes\n";
			break;
		}

		if(i%2 == 0)c -= b;
		else a -= d;
		i++;
	}

	return 0;
}

Measured memory_bytes: 3636
#include <iostream>
using namespace std;
typedef unsigned long long u64;

int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  u64 a, b, c;
  cin >> a >> b >> c;
  if (a%2==0 || b%2==0 || c%2==0) cout << 0 << endl;
  else {
    cout << min(b*c, min(c*a, a*b)) << endl;
  }
  return 0;
}


Measured memory_bytes: 256
N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
point = [K-Q] * N
for i in A:
    point[i-1] = point[i-1] + 1
 
for i in range(N):
    if point[i] <= 0:
        print('No')
    else:
        print('Yes')

Measured memory_bytes: 10528
#include <bits/stdc++.h>
// #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 };

typedef long long ll;
using namespace std;

int main(){
  int x;
  cin >> x;
  int a[x];
  rep(i,0,x){
    cin >> a[i];
  }
  map<int,int>mp;
  rep(i,0,x){
    mp[a[i]]++;
  }
  int ans = 0;
  for(auto p: mp){
    int x = p.first;
    int n = p.second;
    if(n < x) ans += n;
    else ans += n-x;
  }
  pout(ans);
	return 0;
}


Measured memory_bytes: 5120
N,WW = list(map(int,input().split(" ")))

things = [list(map(int,input().split(" "))) for _ in range(N )]
W,v = things[0]
dic = {}
dic[W] = [v]
for i in range(1,4):
    dic[W + i] = []
for temp in things[1:]:
    w,v = temp
    dic[w].append(v)
ans = 0
l1 = len(dic[W])
l2 = len(dic[W + 1])
l3 = len(dic[W + 2])
l4 = len(dic[W + 3])
dic[W].sort(reverse=True)
dic[W + 1].sort(reverse=True)
dic[W + 2].sort(reverse=True)
dic[W + 3].sort(reverse=True)
for i1 in range(l1 + 1):
    for i2 in range(l2 + 1):
        for i3 in range(l3 + 1):
            for i4 in range(l4 + 1):
                temp = sum(dic[W][:i1]) + sum(dic[W+1][:i2]) + sum(dic[W+2][:i3]) + sum(dic[W+ 3][:i4])

                if  W * i1 +  (W +1) * i2 + (W +2) * i3 +  (W +3) * i4 <= WW:
                    ans = max(temp,ans)
print(ans)

Measured memory_bytes: 69720
#include <iostream>
#include <vector>
#include <numeric>//accumulate(v.begin(), v.end(), 0);
#include <algorithm>//sort(v.begin(),v.end());
#include <string>//
#include <cmath>
#include <iomanip> //setprecision(2)
using namespace std;
#define ll long long
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int main() {
        int m[4]={};
        int a,b;
        rep(i,3) {
                cin >> a >> b;
                m[a-1]++;
                m[b-1]++;
        }
        int res=0;
        rep(i,4){
                if(m[i]%2==1) res++;
        }
        if(res==2) cout << "YES"<<endl;
        else cout << "NO" <<endl;

}


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

using namespace std;

#define repl(i,a,b) for(int i=(int)a;i<(int)b;i++)
#define rep(i,n) repl(i,0,n)
#define maxch(a,b) a=max(a,b)

int n, p;
int c[50];

int main(int argc, char const *argv[])
{
  while(cin >> n >> p, n | p){
    memset(c, 0, sizeof(c));
    int cnt = 0, turn = 0;
    int tmp = p;
    while(true) {
      if (p > 0) {
        c[turn]++;
        p--;
        if(tmp == c[turn]) break; 
      } else {
        p = c[turn];
        c[turn] = 0;
      }
      cnt++;
      turn = (turn + 1) % n;
    }

    cout << turn << endl;
  }
  return 0;
}

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

int main() {
	
	int n, k;
	cin >> n >> k;
	printf("%d\n", (n % k == 0) ? 0 : 1);
	
	return 0;
}

Measured memory_bytes: 256
// A-F_20170707.cpp : アプリケーションのエントリ ポイントを定義します。
//

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>


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

using namespace std;

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

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

    if (a + b == 15)
    {
        cout << "+" << endl;
    }
    else if (a * b == 15) {
        cout << "*" << endl;
    }
    else {
        cout << "x" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007;
using ll = long long;
using namespace std;

int main(){
	ll n, k, q; cin >> n >> k >> q;
	map<ll, ll> mp;
	for( int i = 0; i < q; ++i ){
		int tmp; cin >> tmp;
		++mp[tmp];
	}
	for( int i = 1; i <= n; ++i ){
		if( k-q+mp[i] > 0 ) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
}


Measured memory_bytes: 6912
/*
 * written by Yaqi Zhang
 * University of Wisconsin-Madison
 * 2020
 */

#include<algorithm>
#include<cstring>
#include<iostream>
#include<map>
#include<set>
#include<stdio.h>
#include<vector>

#define INF 0x3f3f3f3f
typedef long long ll;

using namespace std;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        nums[i] = x;
    }
    sort(nums.begin(), nums.end());
    int ans = INF;
    int lo = nums.front(), hi = nums.back();
    for(int p = lo; p <= hi; ++p) {
        int cur = 0;
        for(int num : nums) cur += (p - num) * (p - num);
        ans = min(ans, cur);
    }
    cout << ans << "\n";

    return 0;
}



Measured memory_bytes: 256
#include <stdio.h>


int A[1000000],n;

//二分探索
int binarysearch(int k){
  int left=0;
  int mid;
  int right=n;

  while(left<right){
    mid=(left+right)/2;
    if(k==A[mid]) return 1;
    if(k<A[mid]) right=mid;
    else if(k>A[mid])left=mid+1;
  }
  return 0;

}

int main(){
  int i,p,keynumber,sum=0;

  //探索される数列Sを決定
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }

  //探索する数列Tを決定
  scanf("%d",&p);
  for(i=0;i<p;i++){
    scanf("%d",&keynumber);
    if(binarysearch(keynumber)) sum++;
  }

  printf("%d\n",sum);

  return 0;
}



Measured memory_bytes: 2108
#include<stdio.h>
#include<stdlib.h>
#define MAX 2000000
#define N 10000

int main(){
  
  unsigned short *A, *B;

  int C[N+1];
  
  int n, i, j;
  
  scanf("%d", &n);

  A = malloc(sizeof(short)*n+1);
  B = malloc(sizeof(short)*n+1);

  for ( i = 0; i <= N; i++ ) {
    C[i] = 0;
  }

  for ( i = 0; i < n; i++ ){
    
    scanf("%d", &A[i+1]);
    C[A[i+1]]++;
    
  }



  
  for ( i = 1; i <= N; i++ ) {
    C[i] = C[i] + C[i-1];
  }

  
  for ( j = 1; j <= n; j++ ){
    B[C[A[j]]] = A[j];
    C[A[j]]--;
      }

  
  for ( i = 1; i <= n; i++ ){
    if ( i > 1 ) printf(" ");
    printf("%d", B[i]);
  }
  
  printf("\n");
  return 0;
}

Measured memory_bytes: 8460
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		String S = sc.next();
		String ans = "";

		if (S.equals("ABC")) {
			ans = "ARC";
		} else {
			ans = "ABC";
		}

		// 出力
		System.out.println(ans);
	}
}

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

int main(){
  int A[5];
  for (int i=0;i<5;i++){
    cin >>A[i];
  }
  int total=0;
  for (int i=0;i<5;i++){
      total=total+ceil((float)A[i]/10)*10;
  }
  int maxA=0;
  for (int i=0;i<5;i++){
    if(!(A[i]%10==0)){
      maxA=max(maxA,10-A[i]%10);
    }
  }
  cout<< total-maxA<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1000000007;
#define lcm(x, y) ((x) * (y) / __gcd((x), (y)))
#define sz(a) (long long)((a).size())
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define debug(x) cout << #x << " : " << x << endl
#define part cout << "----------------------------------\n";
#define mp make_pair
#include <iostream>
#define fastinput                     \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);

LL dp[100 + 2][2 * 100000 + 1];
LL sum[100 + 2][2 * 100000 + 1];

int main()
{
    fastinput;
    LL n, i, j, k, t, temp;
    //state=[spent][child_left]
    cin >> n >> k;
    //debug(n);
    //debug(k);
    LL a[n + 1];
    for (i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    //cout << "taking inputs" << endl;

    for (i = 0; i <= n; i++)
    {
        for (j = 0; j <= 2 * k + 1; j++)
        {
            dp[i][j] = 0;
            sum[i][j] = 0;
        }
    }
	//ways to spend j candies among first i people is dp state
    dp[0][0] = 1;
    for (i = 0; i <= n - 1; i++)
    {
        for (j = 0; j <= k; j++)
        {
            
            sum[i + 1][j] += (dp[i][j]) % MOD;
            sum[i + 1][j] %= MOD;
            if (j + a[i + 1] + 1 <= k)
            {
                sum[i + 1][j + a[i + 1] + 1] -= (dp[i][j]) % MOD;
                sum[i + 1][j + a[i + 1] + 1] %= MOD;
            }
        }

        for (j = 0; j <= k; j++)
        {
            //cout << "sum[" << i + 1 << "][" << j << "] is " << sum[i + 1][j] << endl;
        }
        dp[i + 1][0] = sum[i + 1][0];
        for (j = 1; j <= k; j++)
        {
            dp[i + 1][j] = (dp[i + 1][j - 1] + sum[i + 1][j])%MOD;
            //cout << "dp[" << i + 1 << "][" << j << "] is " << dp[i + 1][j] << endl;
        }
    }

    cout << (dp[n][k]+MOD)%MOD << endl;

    return 0;
}


Measured memory_bytes: 317696
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>
// *テンプレート*
#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define P pair<int, int>
// aよりbの方が小さかったら、aの値をbの値に置き換える。(swapではない！)
template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
// aよりbの方が大きかったら、aの値をbの値に置き換える。
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

using namespace std;
typedef long long ll;
using Graph = vector<vector<int>>;
//最大公約数
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
//最小公倍数
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
// 素数かどうか判定
bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}

const long long MOD = 1000000007;
const long long INF = 1LL << 60;
// *テンプレートここまで*

// pair -> vector<pair<int,int>> 
//		   AandB.push_back(make_pair(a[i],b[i]))


struct edge {
	int from, to, cost;
};

int n, m;
int a, b, c;
int d[110][110];
vector<edge>vec;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			d[i][j] = INF;
		}
	}
	rep(i, m) {
		cin >> a >> b >> c;
		d[a][b] = min(d[a][b], c);
		d[b][a] = min(d[b][a], c);
		vec.push_back({ a,b,c });
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
	int ans = 0;
	for (edge e : vec) {
		if (d[e.from][e.to] < e.cost) {
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 384
# -*- coding: utf-8 -*-

X, Y = map(int, input().split())
ans = 0
if X == 1:
    ans += 300000
elif X == 2:
    ans += 200000
elif X == 3:
    ans += 100000
    
if Y == 1:
    ans += 300000
elif Y == 2:
    ans += 200000
elif Y == 3:
    ans += 100000

if X == 1 and Y == 1:
    ans += 400000
print(ans)

Measured memory_bytes: 3064
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int main()
{
  int n;
  while (~scanf("%d", &n)) {
    if (n == 0)
      break;

    vector<int> S(n);
    for (int i = 0; i < n; ++i)
      scanf("%d", &S[i]);

    int cnt = 0;
    for ( ; ; ) {
      vector<int> C(n);
      map<int, int> freq;

      for (int i = 0; i < n; ++i)
	++freq[S[i]];
      for (int i = 0; i < n; ++i)
	C[i] = freq.find(S[i])->second;

      bool same = true;
      for (int i = 0; i < n; ++i) {
	if (S[i] != C[i])
	  same = false;
      }
      
      if (same)
	break;
      ++cnt;
      swap(C, S);
    }
    printf("%d\n", cnt);
    for (int i = 0; i < n-1; ++i)
      printf("%d ", S[i]);
    printf("%d\n", S[n-1]);
  }
  return 0;
}

Measured memory_bytes: 0
import java.util.Scanner;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt(), k = scanner.nextInt();
			Set<Integer> set = IntStream.rangeClosed(1, n).boxed().collect(Collectors.toSet());
			IntStream.range(0, k).forEach(i -> {
				int d = scanner.nextInt();
				IntStream.range(0, d).forEach(j -> set.remove(scanner.nextInt()));
			});
			System.out.println(set.size());
		}
	}
}


Measured memory_bytes: 46780
#include<bits/stdc++.h>
#define ll long long
#define nl "\n"
#define pi acos(-1)
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define pcase printf("Case %d: ",c)
int c=1;
using namespace std;
int arr[10000005];
long long nod(long long n){
    ll sum =0;
    for(ll i =1;i*i<=n;i++){
        if(i*i==n){sum+=1;}
        else{
            sum+=2;
        }

    }
    return sum;
}
void dev(ll n){
   for (int i = 1; i <= n; ++i)
   for (int j = i; j <= n; j += i)
  ++arr[j];
}

int main(){

    ll n;
    cin>>n;
     dev(n);
    ll x =0;
    for(ll i =1;i<=n;i++){
        x=x+(i*arr[i]);
    }
    cout<<x<<endl;

}


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

using namespace std;

int main()
{
    int k,a,b;
    cin >> k >> a >> b;
    if(k == 1 || b % k == 0 || a % k == 0 || b - a >= k - 1 || b > k > a)  cout << "OK" << endl;
    else if(k > b) cout << "NG" << endl;
    else if(a%k > b%k) cout << "OK" << endl;
    else cout << "NG" << endl;
}

Measured memory_bytes: 3632
# パスカルの三角形
def pascal_triangle(n):
    pascal =[[]]
    pascal[0].append(1)
    for i in range(1, n + 1):
        pascal[i - 1].append(0)
        pascal.append([])
        for j in range(i + 1):
            pascal[i].append((pascal[i - 1][j - 1] + pascal[i - 1][j]) % (10**9 + 7))
    return pascal

# n個からr個を選ぶ組合せ
def comb(n, r, pascal_triangle):
    r = min(r, n - r)
    if r == 0:
        return 1
    if r == 1:
        return n
    result = pascal_triangle[n][r]
    return result

# n種類からr個を選ぶ重複組合せ
def homo(n, r, pascal_triangle):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return comb(n + r - 1, r, pascal_triangle)

def main(n, k, i, pascal_triangle):
    # 青玉k個のうち、まずi箇所に1個ずつ配置
    # 残りの(k - i)個を、ゼロを許容してi箇所に配置 => i種類から(k - i)個を選ぶ重複組合せ
    result = homo(i, k - i, pascal_triangle)
    # 赤玉(n - k)個のうち、まず(i - 1)個は青玉を区切るために配置
    # 残りの(n - k - i + 1)個を、ゼロを許容して(i + 1)箇所に配置 => (i + 1)種類から(n - k - i + 1)個を選ぶ重複組合せ
    # ただし、そもそも赤玉が(i - 1)個未満の場合は、論外
    if (n - k) < (i - 1):
        return 0
    result *= homo(i + 1, n - k - i + 1, pascal_triangle)
    result = result % (10**9 + 7)
    return int(result)

N, K = [int(x) for x in input().split()]
pascal_triangle = pascal_triangle(N)
for i in range(K):
    print(main(N, K, i + 1, pascal_triangle))

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

int main(){
 long long k;
 string s;
 cin>>k;
 cin>>s;
 if(k>=s.size()){
     cout<<s<<endl;
 }
 else{
     cout<<s.substr(0,k)<<"..."<<endl;
 }

    return 0;
}

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

int n,m;
vector <pair<int,int> > a[200002];
long long loc[100001];
bool vis[100001];

bool dfs(int n) {
	if (vis[n]) return true;
	vis[n]=true;
	for (int i=0;i<a[n].size();i++) {
		if (vis[a[n][i].first]&&loc[a[n][i].first]!=loc[n]+(long long)a[n][i].second) {
			return false;
		}
		loc[a[n][i].first]=loc[n]+(long long)a[n][i].second;
		if (!dfs(a[n][i].first)) return false;
	}
	return true;
}

int main(){
	memset(vis,false,sizeof(vis));
	cin>>n>>m; 
	int tmp=-1;
	for (int i=0;i<m;i++) {
		int x,y,z;
		cin>>x>>y>>z;
		if (tmp==-1) tmp=x;
		a[x].push_back(make_pair(y,z));
		a[y].push_back(make_pair(x,-z));
	}
	loc[tmp]=0;
	for (int i=1;i<=n;i++) if (!vis[i]) 
	if (!dfs(i)){
		cout<<"No"<<endl;
		return 0;
	}
	cout<<"Yes"<<endl;
	return 0;
}

Measured memory_bytes: 14848
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

const ll MOD = 1e9 + 7;
ll n;

ll up(ll x, ll k)
{
	ll res = 1;
	while (k--)
		res = (res * x) % MOD;
	return res;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	cout << (up(10, n) - 2 * up(9, n) + up(8, n) + 10 * MOD) % MOD;
}

Measured memory_bytes: 3632
#include<iostream>
#include<vector>
using namespace std;
long long GCD(long long a,long long b){return b ? GCD(b,a%b):a;}

int main(){
    int N; cin>>N;
    vector<long long> A(N);
    for(int i=0;i<N;i++)cin>>A[i];
    long long res=A[0];
    for (int i=0;i<N;i++){
        res=GCD(res,A[i]);
    }
    cout<<res<<endl;
}

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



int main(){
	int ans=0;
	int flag=0;
	int H,W;
	cin>>H>>W;
	int mp[51][51]={0};
	int mp_f[51][51]={0};
	int f_f[51][51]={0};
	for(int i=1;i<=H;i++){
		for(int j=1;j<=W;j++){
			cin>>mp[j][i];
		}
	}
	for(int i=1;i<=H;i++){
		for(int j=1;j<=W;j++){
			cin>>mp_f[j][i];
		}
	}
	int h,w;
	cin>>h>>w;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			cin>>f_f[j][i];
		}
	}
	for(int i=1;i<=H;i++){
		for(int j=1;j<=W;j++){
			mp[j][i]+=mp[j-1][i];
		}
	}
	for(int j=1;j<=W;j++){
		for(int i=1;i<=H;i++){
			mp[j][i]+=mp[j][i-1];
		}
	}
	
	
	for(int i=1;i<=H-h+1;i++){
		for(int j=1;j<=W-w+1;j++){
			int t=1;
			for(int k=1;k<=h;k++){
				for(int l=1;l<=w;l++){
					if(f_f[l][k]!=mp_f[j+l-1][i+k-1])t=0;
				}
			}
			if(t){
				int tmp=mp[j-1+w][i-1+h]-mp[j-1][i-1+h]-mp[j-1+w][i-1]+mp[j-1][i-1];
				if(flag==0){
					flag=1;
					ans=tmp;
				}
				else{
					ans=max(ans,tmp);
				}
			}
		}
	}
	if(flag)cout<<ans<<endl;
	else cout<<"NA\n";
	return 0;
}


Measured memory_bytes: 1200
N, X = [int(x) for x in input().split()]
h = [1]
b = [1]
for i in range(N):
    h.append(3 + h[i] * 2)
    b.append(1 + b[i] * 2)
def rec(n: int, x: int):
    if (n == 0):
        return 0 if x <= 0 else 1
    mid = 1 + h[n-1] + 1
    if (x < mid):
        return rec(n-1, x-1)
    if (x == mid):
        return b[n-1] + 1
    if (mid < x):
        return b[n-1] + 1 + rec(n-1, x-mid)
print(rec(N, X))


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

using namespace std;

#define REP(i,n) for(int i = 0; i < n; i++)
#define RREP(i,n) for(int i = n - 1; i >= 0; i--)

#define ALL(v) v.begin(),v.end()
#define pb push_back
#define mp make_pair
#define F first
#define S second

#define UNIQUE(v) do{sort(v.begin(), v.end()); v.erase( unique(v.begin(), v.end()), v.end() );} while(0)


#define y0 y3487465
#define y1 y8687969

#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,63,sizeof(x))

typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pi> vpi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

double EPS = 1e-9;
int INFi = 1000000005;
long long INFll = 1000000000000000005ll;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};
ll MOD = 1000000007;

// return x^n % p  O(log n)

ll mod_pow(ll x, ll n, ll p) {
  if(n == 0) return 1;
  ll res = mod_pow(x * x % p, n / 2, p);
  if(n & 1) res = res * x % p;
  return res;
}

string L;

int main(){
  cin >> L;
  int l = L.size();
  ll dp0[l + 1], dp1[l + 1];
  dp0[0] = 1; dp1[0] = 0;
  REP(i, l) {
    if(L[i] == '1') {
      dp0[i + 1] = dp0[i] * 2 % MOD;
      dp1[i + 1] = (dp1[i] * 3 % MOD + dp0[i]) % MOD;
    } else {
      dp0[i + 1] = dp0[i];
      dp1[i + 1] = dp1[i] * 3 % MOD;
    }
  }

  cout << (dp0[l] + dp1[l]) % MOD << endl;

  return 0;
}


Measured memory_bytes: 2048
#include<iostream>
#include<math.h>
#include <algorithm>
#include<float.h>
#include <limits>
#include <numeric>
using namespace::std;
int main(){

 long long int A;
 long long int B;
 long long int C;
 long long int D;
  cin>>A>>B>>C>>D;
 long long int tmp;
 long long int tc=C;
 long long int td=D;
  

  
  if(tc<td){
    tmp=td;
    td=tc;
    tc=tmp;
  }
  
  tmp=tc%td;
  while(tmp!=0){
    tc=td;
    td=tmp;
    tmp=tc%td;
  }
  if(A==B){
    cout<<((A%C)&&(A%D));
  }else{
  long long int L=C*D/td;
    
   long long int BC = B/C;
   long long int BD = B/D;
    long long int BL = B/L;
    long long int AC = (A-1)/C;
    long long int AD = (A-1)/D;
    long long int AL = (A-1)/L;
 
  cout<<B-A+1-(BC-AC)-(BD-AD)+(BL-AL);
  }
}


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

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

// #define DEBUG_IS_VALID

#ifdef DEBUG_IS_VALID
#define DEB 1 
#else
#define DEB 0
#endif
#define DUMPOUT cout
#define dump(...) if(DEB) DUMPOUT<<"  "<<#__VA_ARGS__<<" :["<<__LINE__<<":"<<__FUNCTION__<<"]"<<endl<<"    "; if(DEB) dump_func(__VA_ARGS__)
template<typename T1,typename T2>ostream& operator << (ostream& os, pair<T1,T2> p){cout << "(" << p.first << ", " << p.second << ")"; return os;}
template<typename T>ostream& operator << (ostream& os, vector<T>& vec) { os << "{"; for (int i = 0; i<vec.size(); i++) os << vec[i] << (i + 1 == vec.size() ? "" : ", "); os << "}"; return os; }
template<typename T>ostream& operator << (ostream& os, set<T>& st){for(auto itr = st.begin(); itr != st.end(); itr++) cout << *itr << (next(itr)!=st.end() ? ", " : ""); cout << "}"; return os;}
template<typename T1,typename T2>ostream& operator << (ostream& os, map<T1,T2> mp){cout << "{"; for(auto itr = mp.begin(); itr != mp.end(); itr++) cout << "(" << (itr->first) << ", " << (itr->second) << ")" << (next(itr)!=mp.end() ? "," : ""); cout << "}"; return os; }

void dump_func(){DUMPOUT << endl;}
template <class Head, class... Tail>void dump_func(Head&& head, Tail&&... tail){ DUMPOUT << head; if (sizeof...(Tail) == 0) { DUMPOUT << " "; } else { DUMPOUT << ", "; } dump_func(std::move(tail)...);}
template<class T> inline void chmax(T& a,T const& b){a=max(a,b);}
template<class T> inline void chmin(T& a,T const& b){a=min(a,b);}

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;

const int mod=1e9+7,INF=1<<29;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<59; 

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N,M; cin >> N >> M ;
  vector<vector<bool>> graph(N,vector<bool>(N,false));
  rep(i,M){
    int a,b; cin >> a >> b ;
    a--; b--;
    graph[a][b] = graph[b][a] = true;
  }
  vvi cog(N);
  rep(i,N-1) REP(j,i+1,N){
    if(!graph[i][j]){
      cog[i].pb(j); cog[j].pb(i);
    }
  }
  vector<int> color(N,-1);
  vvi x;
  dump(cog);
  vi ss(2);
  function<int(int,int)> dfs = [&](int u,int c){
    dump(u,c);
    color[u] = c;
    ss[c]++;
    c ^= 1;
    int res = 0;
    for(auto v:cog[u]){
      if(color[v]==-1){
        int temp = dfs(v,c);
        if(temp==-1) return -1;
      }else if(color[v]!=c){
        return -1;
      }
    }
    return res;
  };
  rep(i,N){
    if(color[i]!=-1) continue;
    ss[0] = ss[1] = 0;
    int s = dfs(i,0);
    if(s<0){
      cout << "-1" << endl;
      return 0;
    }
    dump(ss);
    vi nxt(2); nxt = ss;
    x.pb(nxt);
  }
  dump(color);
  dump(x);
  bitset<700> dp;
  dp[0] = 1;
  for(auto xx : x){
    dp = (dp<<xx[0]) | (dp<<xx[1]);
  }
  for(int i=N/2;i>=0;i--){
    if(dp[i]){
      cout << i*(i-1)/2+(N-i)*(N-i-1)/2 << endl;
      break;
    }
  }
  return 0;
}

Measured memory_bytes: 3200
function Main(input) {
    const S = input[0];
    
    var currentA = 0;
    var sum = 0;
    var prevB = false;
    
    for (var index = 0; index < S.length; index++) {
        var element = S.charAt(index);
        if(element === "A") {
            if(prevB) {
                currentA = 0;
            }
            currentA++;
        }else if(element === "B") {
            if(prevB) { 
                currentA = 0;
            }
        } else {
            if(prevB) {
                sum += currentA;
            } else {
                currentA = 0;
            }
        }
        prevB = element === "B";
    }

    console.log(sum);
    
}

// 1行入力の場合
// Main(require("fs").readFileSync("/dev/stdin", "utf8").trim());

// 改行で分割
// Main(require("fs").readFileSync("/dev/stdin", "utf8").trim().split(/\n/));

// 改行・空白で分割
Main(require("fs").readFileSync("/dev/stdin", "utf8").trim().split(/\n|\s/));

Measured memory_bytes: 7500
import java.util.*;
public class Main {
public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	String s = sc.next();
  	int l = s.length();
  	if(l/2==0) System.exit(0);
  	if((l<3)||(99<l)) System.exit(0);
  
  	if (kaibunCheck(s)) {
      if (kaibunCheck(s.substring(0,(l-1)/2))) {
        if (kaibunCheck(s.substring((l+3)/2-1,l))) {
        	System.out.println("Yes");
          	System.exit(0);
      	}
      }
    }
      System.out.println("No");
	}
  
public static boolean kaibunCheck(String str){
  	int len = str.length();
  	char[] c = new char[len];
  	for(int i=0;i<len;i++){
      c[i] = str.charAt(i);
    }
  	for(int j=0;j<len;j++){
      if(c[j]!=c[len-j-1]) return false;
    }
  	return true;
}
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<unsigned int mod_>
struct ModInt{
	using uint = unsigned int;
	using ll = long long;
	using ull = unsigned long long;

	constexpr static uint mod = mod_;

	uint v;
	ModInt():v(0){}
	ModInt(ll v):v(normS(v%mod+mod)){}
	explicit operator bool() const {return v!=0;}
	static uint normS(const uint &x){return (x<mod)?x:x-mod;}		// [0 , 2*mod-1] -> [0 , mod-1]
	static ModInt make(const uint &x){ModInt m; m.v=x; return m;}
	ModInt operator+(const ModInt& b) const { return make(normS(v+b.v));}
	ModInt operator-(const ModInt& b) const { return make(normS(v+mod-b.v));}
	ModInt operator-() const { return make(normS(mod-v)); }
	ModInt operator*(const ModInt& b) const { return make((ull)v*b.v%mod);}
	ModInt operator/(const ModInt& b) const { return *this*b.inv();}
	ModInt& operator+=(const ModInt& b){ return *this=*this+b;}
	ModInt& operator-=(const ModInt& b){ return *this=*this-b;}
	ModInt& operator*=(const ModInt& b){ return *this=*this*b;}
	ModInt& operator/=(const ModInt& b){ return *this=*this/b;}
	ll extgcd(ll a,ll b,ll &x,ll &y) const{
		ll u[]={a,1,0},v[]={b,0,1};
		while(*v){
			ll t=*u/ *v;
			rep(i,3) swap(u[i]-=t*v[i],v[i]);
		}
		if(u[0]<0) rep(i,3) u[i]=-u[i];
		x=u[1],y=u[2];
		return u[0];
	}
	ModInt inv() const{
		ll x,y;
		extgcd(v,mod,x,y);
		return make(normS(x+mod));
	}
	bool operator==(const ModInt& b) const { return v==b.v;}
	bool operator!=(const ModInt& b) const { return v!=b.v;}
	friend istream& operator>>(istream &o,ModInt& x){
		ll tmp;
		o>>tmp;
		x=ModInt(tmp);
		return o;
	}
	friend ostream& operator<<(ostream &o,const ModInt& x){ return o<<x.v;}
};
using mint = ModInt<998244353>;

int main(){
	int N;
	cin>>N;
	V<ll> a(N);
	rep(i,N) cin>>a[i];
	sort(all(a));
	mint res = 1;
	rep(i,N){
		res *= __gcd(a[i],(ll)i);
	}
	cout<<res<<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main() {
  ll N, K, Q;
  cin >> N >> K >> Q;
  vector<ll> vec(N, K);
  for(ll i = 0; i < Q; i++) {
    ll A;
    cin >> A;
    vec.at(A - 1)++;
  }
  for(ll i = 0; i < N; i++) {
    if(vec.at(i) > Q) {
      cout << "Yes" << endl;
    }
    else {
      cout << "No" << endl;
    }
  }
}

Measured memory_bytes: 4060
#define LOCAL
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
  out << "(" << a.first << "," << a.second << ")";
  return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
  return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
  return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }

struct fast_ios {
  fast_ios() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
  };
} fast_ios_;

int main() {
  int x, v, y, w, t;
  cin >> x >> v >> y >> w >> t;
  if (w >= v) {
    cout << "NO" << endl;
  } else {
    if (1LL * (v - w) * t >= abs(x - y)) {
      cout << "YES" << endl;
    } else {
      cout << "NO" << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 3100
n,k=map(int,input().split())
l=list(map(int,input().split()))
for i in range(n,100000):
    s=str(i)
    d=list(map(int,s))
    f=0
    for j in range(len(d)):
        if(d[j] in l):
            f=1
    if(f==0):
        print(i)
        exit()


Measured memory_bytes: 73632
#include<stdio.h>
int main(){
char a[100][101],b[102][102];
int H,W,i,j;
scanf("%d %d",&H,&W);
for(i=0;i<H;i++){
scanf("%s",a[i]);
}
for(i=0;i<H+2;i++){
 for(j=0;j<W+2;j++){
 b[i][j]='#';
 }
}
for(i=0;i<H;i++){
  for(j=0;j<W;j++){
  b[i+1][j+1]=a[i][j];
  }
}
for(i=0;i<H+2;i++){
  for(j=0;j<W+2;j++){
  printf("%c",b[i][j]);
  }
  printf("\n");
}
return 0;
}

Measured memory_bytes: 128
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<stack>
using namespace std;
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B
//if it is not fully connected component
#define N 105
vector<int> nebors[N];//start from 1
int start[N]; // start form 1
int end[N]; //end with 1
int vis_nei[N]; // neighbor
stack<int> s;
int dfs(int k,int d){
	start[k] = (++d);

	for(int i = 0; i<nebors[k].size(); i++){
		int temp = nebors[k].at(i);
		if(start[temp]==-1) d = dfs(temp,d);
	}
	end[k] = (++d);
	return d;
}

int main(){
	int n;
	scanf("%d",&n);
	memset(start,-1,sizeof(start));
	memset(end,-1,sizeof(end));
	memset(vis_nei,-1,sizeof(vis_nei));
	//vis_nei
	for(int i = 1; i<=n; i++){
		int id,num;
		scanf("%d %d",&id, &num);
		for(int j = 0; j<num; j++){
			int temp;
			scanf("%d",&temp);
			nebors[id].push_back(temp);
			//nebors[temp].push_back(id);
		}
	}
	//check each node for the (unfully connected)
	int d = 0;
	for(int i = 1; i<n; i++){
		if(start[i]==-1){
			d = dfs(i,d);
		}
	}
	
	for(int i = 1; i<=n; i++){
		printf("%d %d %d\n",i,start[i],end[i]);
	}
}



Measured memory_bytes: 2808
#include <stdio.h>

typedef long long ll;


int main(){

	ll N,M;

	scanf("%lld %lld",&N,&M);

	ll l=0;
	ll r=1000000000000ll;

	ll ans=0ll;

	while(l<r){
		ll mid=(l+r)/2ll;
		if(mid-N<=(M-(2ll*mid))/2ll && M>=2ll*mid){
			l=mid+1;
			if(ans<mid){ans=mid;}
		}
		else{
			r=mid;
		}
	}
	printf("%lld\n",ans);

	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) (v).begin(), (v).end()

using namespace std;
using ll = long long;

int main()
{
  ll x, y; cin >> x >> y;

  int ans = 1<<30;
  pair<ll, ll> v[4] = {{-x, -y}, {-x, y}, {x, -y}, {x, y}};
  for (int i = 0; i < 4; ++i) {
    int cnt = 0, xx = v[i].first, yy = v[i].second;

    if (xx * x < 0) cnt++;
    if (yy * y < 0) cnt++;
    if (xx <= yy) ans = min({ans, cnt + yy - xx});
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
fn main() {
    use proconio::input;
    use proconio::marker::Usize1;
    use std::collections::BTreeMap;
    input!(r: usize, c: usize, k: usize);
    let items = {
        let mut tmp = BTreeMap::new();
        for _ in 0..k {
            input!(x: Usize1, y: Usize1, v: usize);
            tmp.insert((x, y), v);
        }
        tmp
    };

    let mut dp = vec![0; c * 2 * 4];
    let index_of = |x: usize, y: usize| -> usize {
        if x % 2 == 0 {
            y * 4
        } else {
            y * 4 + c * 4
        }
    };
    for x in 0..r {
        for y in 0..c {
            let idx = index_of(x, y);
            if x != 0 {
                let old = index_of(x - 1, y);
                for i in 0..4 {
                    // x が変わったので拾った数はリセット
                    dp[idx] = std::cmp::max(dp[idx], dp[old + i]);
                }
            }
            if y != 0 {
                let old = index_of(x, y - 1);
                for i in 0..4 {
                    dp[idx + i] = std::cmp::max(dp[idx + i], dp[old + i]);
                }
            }
            if let Some(v) = items.get(&(x, y)) {
                // 拾うケース
                for i in 0..3 {
                    let idx = idx + 2 - i;
                    dp[idx + 1] = std::cmp::max(dp[idx + 1], dp[idx] + v);
                }
            }
            // println!("{:?}", dp);
        }
    }

    let rc_idx = index_of(r - 1, c - 1);
    let mut ans = 0;
    for i in 0..4 {
        ans = std::cmp::max(ans, dp[rc_idx + i])
    }

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


Measured memory_bytes: 13988