akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 1e3 + 5, M = 2e5 + 5;
int read() {
	int x = 0, f = 1; char ch;
	while(! isdigit(ch = getchar())) (ch == '-') && (f = -f);
	for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 3) + (x << 1) + (ch ^ 48));
	return x * f;
}
template <class T> T Max(T a, T b) { return a > b ? a : b; }
template <class T> T Min(T a, T b) { return a < b ? a : b; }
vector <int> v[N];
struct edge {int x, y;} e[M];
int n, m, vis[N], tag[N], g1[N][N], g2[N][N];
void dfs(int x, int rt) {
	g1[rt][x] = 1; vis[x] = 1;
	for(int i = 0; i < v[x].size(); ++ i) if(! vis[v[x][i]]) dfs(v[x][i], rt);
}
void dfs(int x, int col, int type, int rt) {
	vis[x] = 1;
	if(! type) tag[x] = col;
	else g2[rt][x] = tag[x] != col;
	for(int i = 0; i < v[x].size(); ++ i) if(! vis[v[x][i]]) dfs(v[x][i], col, type, rt);
}
signed main() {
	n = read(); m = read();
	for(int i = 1, x, y; i <= m; ++ i) {
		x = read(); y = read();
		v[x].push_back(y);
		e[i] = (edge){x, y};
	}
	for(int i = 1; i <= n; ++ i) {
		for(int j = 1; j <= n; ++ j) vis[j] = 0;
		dfs(i, i);
	}
	for(int i = 1; i <= n; ++ i) {
		for(int j = 1; j <= n; ++ j) tag[j] = vis[j] = 0; vis[i] = 1;
		for(int j = 0; j < v[i].size(); ++ j) if(! vis[v[i][j]]) dfs(v[i][j], j + 1, 0, i);
		for(int j = 1; j <= n; ++ j) vis[j] = 0; vis[i] = 1;
		for(int j = v[i].size() - 1; j >= 0; -- j) if(! vis[v[i][j]]) dfs(v[i][j], j + 1, 1, i);
	}
	for(int i = 1; i <= m; ++ i) puts(g1[e[i].y][e[i].x] ^ g2[e[i].x][e[i].y] ? "diff" : "same");
	return 0;
}


Measured memory_bytes: 23168
#include<iostream>
#include<string>
#include<array>
#include<vector>
#include<deque>
#include<chrono>

using namespace std;

using ull = unsigned long long int;

ull mod = 1000000007;

ull dp[101][8] = {};

int main(void) {

	int H, W, K;

	cin >> H >> W >> K;

	if (W == 1) {
		cout << 1 << endl;
		return 0;
	}

	dp[0][0] = 1;

	for (int i = 0; i < H; i++) {
		//今jにいる。
		for (int j = 0; j < W; j++) {

			for (int k = 0; k < (1 << W - 1); k++) {
				//つながっていない
				bool f = false;
				for (int m = 0; m < W - 2; m++) {
					if ((k & (1 << m)) && (k & (1 << (m + 1)))) {
						f = true;
						break;
					}
				}
				if (f)
					continue;

				if (j == 0) {
					if (k & (1 << j))
						dp[i + 1][j + 1] += dp[i][j];
					else
						dp[i + 1][j] += dp[i][j];


					dp[i + 1][j] %= mod;
					dp[i + 1][j + 1] %= mod;
				}
				else if (j == W - 1) {
					if (k & (1 << (j - 1)))
						dp[i + 1][j - 1] += dp[i][j];
					else
						dp[i + 1][j] += dp[i][j];

					dp[i + 1][j] %= mod;
					dp[i + 1][j - 1] %= mod;

				}
				else {

					if (k & (1 << j)) {
						dp[i + 1][j + 1] += dp[i][j];
					}
					else if (k & (1 << (j - 1))) {
						dp[i + 1][j - 1] += dp[i][j];
					}
					else {
						dp[i + 1][j] += dp[i][j];
					}

					dp[i + 1][j] %= mod;
					dp[i + 1][j + 1] %= mod;
					dp[i + 1][j - 1] %= mod;
				}
			}

		}
	}

	cout << dp[H][K - 1] << endl;

	return 0;
}

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

using namespace std;

typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = (ll)1e9 + 7;

int main()
{
  int N; scanf("%d", &N);
  vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    scanf("%d", &A[i]);
  }
  sort(A.begin(), A.end(), greater<int>());
  vector<int> score(2, 0);
  for (int i = 0; i < N; ++i) {
    score[i % 2] += A[i];
  }
  int ans = score[0] - score[1];
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 256
from collections import defaultdict, deque
from heapq import heappush, heappop, heapify
import math
import bisect
import random
import sys


def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
mod = 1000000007


n = I()
graph = [[] for _ in range(n)]
for _ in range(n-1):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a-1] += [[b-1, c]]
    graph[b-1] += [[a-1, c]]



q, k = LI()
q_ab = LIRM(q)



dist = n * [-1]
dist[k-1] = 0
que = deque([k-1])
while que:
    cur = que.pop()
    for nxt, c in graph[cur]:
        if dist[nxt] == -1:
            dist[nxt] = dist[cur] + c
            que += [nxt]



for a, b in q_ab:
    print(dist[a] + dist[b])

Measured memory_bytes: 96432
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <sstream>
#include <queue> 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> 
#include <numeric>  
#include <functional>
#include <cassert>
#include <bitset>
#include <cctype>  
#include <iomanip> 
#include <limits>  
#include <regex>
// std::numeric_limits<int>::max(), min()
// std::setprecision(X)
// std::islower(), std::isupper(), std::tolower, std::toupper
// std::accumulate(m.begin(), m.end(), 0LL);
// std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
// std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
// if ( std::regex_match(S, std::regex("(dream|dreamer|erase|eraser)*")) ) std::cout << "YES" << std::endl;
 
#define rep(i, n) for(int i = 0; i < (int)(n);    i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;

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

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 998244353;
struct mint {
  typedef long long ll;
  ll x;
  mint(ll x=0):x((x%mod+mod)%mod){}
  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 {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=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 {
    mint res(*this);
    return res/=a;
  }
};


int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  int N; std::cin >> N;
  std::vector<int> D(N);
  rep(i,N) std::cin >> D[i];

  if ( D[0] != 0 ) {
    std::cout << 0 << std::endl;
    return 0;
  }

  std::vector<int> C(N);
  rep(i,N) C[D[i]]++;
  if ( C[0] >= 2 ) {
    std::cout << 0 << std::endl;
    return 0;
  }

  mint ans = 1;
  for(int i=1; i<N; i++) {
    mint k = 1;
    for(int j=0; j<C[i]; j++) k *= C[i-1];
    ans *= k;
  }
  std::cout << ans.x << std::endl;
  return 0;
}


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

using namespace std;
using ll =long long;
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
#define leftunique(a) {sort((a).begin(),(a).end());(a).erase(unique((a).begin(),(a).end()),(a).end());}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
static const ll INF = 1LL << 60;
//Write From this Line

int main()
{
	ll n;
	cin >> n;
	vector<ll> a(n);
	rep(i,n) cin >> a[i];
	
	vector<ll> ans(n);
	ans[0] = 0;
	rep(i,n){
		if(i%2==0) ans[0] += a[i];
		else ans[0] -= a[i];
	}
	For(i,1,n){
		ans[i] = 2 * a[i-1] - ans[i-1];
	}
	ans[n-1] = 2 * a[n-1] - ans[0] ;
	rep(i,n) cout << ans[i] <<" ";
	cout << endl;
}


Measured memory_bytes: 2944
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        A[i] *= -1;
    }
    vector<int> B;
    for (int i = 0; i < N; i++) {
        auto itr = upper_bound(B.begin(), B.end(), A[i]);
        if (itr == B.end()) {
            B.push_back(A[i]);
        } else {
            *itr = A[i];
        }
    }
    cout << B.size() << endl;
    return 0;
}

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> div(1e6+5, 0), a(n);
    rep(i,n){
        cin >> a[i];
        if(div[a[i]] != 0){
            div[a[i]] = 2;
            continue;
        }
        for(int j = a[i]; j < 1e6+5; j += a[i]) div[j]++;
    }
    int ans = 0;
    rep(i,n){
        if(div[a[i]] == 1) ++ans;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 7920
from collections import defaultdict
import itertools
from functools import reduce


def analyze(string):
  s_count = defaultdict(int)
  for s in string:
    s_count[s] += 1
  counts = tuple(s_count.values())
  return counts

N = int(input())
string = input()

def search(N, string):
    memo = {}
    def count(counts, num_set):
        if (counts, num_set) in memo:
            return memo[(counts, num_set)]

        if num_set == 1:
            ans = sum(counts)
        elif num_set == 2:
            num_sum = sum(counts)
            ans = 0
            for i in range(len(counts)):
                num_sum -= counts[i]
                ans += counts[i] * num_sum
        else:
            ans = 0
            for i in range(len(counts) - 1):
                ans += counts[i] * count(counts[i + 1:], num_set - 1)

        memo[(counts, num_set)] = ans
        return ans

    counts = analyze(string)
    ans = 0
    for i in range(1, len(counts) + 1):
        ans += count(counts, i)
    print(ans % (10**9 + 7))

search(N, string)


Measured memory_bytes: 3812
str = input()
dif = ("A","C","G","T")

isdif = False
maxlen = 0
tempdif = ""
for c in str:
    if c in dif:
        if isdif:
            tempdif += c
        else:
            tempdif = c
            isdif = True
    else:
        isdif = False
        if len(tempdif) > maxlen:
            maxlen = len(tempdif)
        tempdif = ""
    if len(tempdif) > maxlen:
        maxlen = len(tempdif)
print(maxlen)



Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    int a,b;
    int d,r;
    double f;

    cin >>a >>b;
    d = a/b;
    r = a%b;

    f = double(a)/b;


    cout << d <<" " << r  << " " <<fixed<<setprecision(5)<<f<<endl;

    return 0;

}



Measured memory_bytes: 3288
#include "bits/stdc++.h"
using namespace std;
using ll = long long;

struct line
{
	ll a, b;
	  line(ll m, ll c)
	{
		a = m;
		b = c;
	}
	ll operator[] (int x)
	{
		return a * x + b;
	}
	double operator*(line const &o)
	{
		return double(b - o.b) / (o.a - a);
	}
};

int main()
{
	cin.tie(0);
	cin.sync_with_stdio(0);

	int n;
	ll c;
	cin >> n >> c;
	
	vector<ll> h(n);
	for(auto& x: h)
	  cin >> x;
	
	vector<ll> dp(n);
	
	deque<line> d;
	d.emplace_back(-2*h[0], dp[0] + h[0] * h[0]);
	for(int i = 1; i < n; ++i) {
	  auto x = h[i];
	  while(d.size() > 1 && d[0][x] >= d[1][x])
	    d.pop_front();
	  dp[i] = d.front()[x] + (x * x + c);
	  auto l = line(-2*x, dp[i] + x * x);
	  while(d.size() > 1 && (d.back() * d[d.size() - 2u]) >= (l * d[d.size() - 2u]))
	    d.pop_back();
	  if(d.back() * l <= h.back())
	    d.emplace_back(l);
	}
	
	cout << dp.back();
}

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

using namespace std;

const int MAXN = 1E5;
int a[3 * MAXN];
bool isZero[3 * MAXN];

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < 3 * n; i++)
        cin >> a[i];
    priority_queue<int, vector<int>, greater<int>> leftHeap;
    priority_queue<pair<int, int>> maxHeap;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> rightHeap;
    long long cur = 0;
    for (int i = 0; i < n; i++)
    {
        leftHeap.push(a[i]);
        cur += a[i];
    }
    for (int i = n; i < 3 * n; i++)
    {
        maxHeap.push({a[i], i});
        cur -= a[i];
    }
    for (int i = 0; i < n; i++)
    {
        pair<int, int> pr = maxHeap.top();
        rightHeap.push(pr);
        cur += pr.first;
        isZero[pr.second] = true;
        maxHeap.pop();
    }
    long long ans = cur;
    for (int i = n; i < 2 * n; i++)
    {
        leftHeap.push(a[i]);
        cur += a[i];
        cur -= leftHeap.top();
        leftHeap.pop();
        if (!isZero[i])
        {
            cur += a[i];
            while (!isZero[rightHeap.top().second])
                rightHeap.pop();
            pair<int, int> pr = rightHeap.top();
            cur -= pr.first;
            isZero[pr.second] = false;
            rightHeap.pop();
        }
        else
        {
            isZero[i] = false;
        }
        ans = max(ans, cur);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 5360
n,p=map(int,input().split())
S=input()[::-1]
ans=0
if p==2:
    for i,s in enumerate(S):
        if int(s)%2==0:
            ans+=(n-i)
    print(ans)
    exit()

if p==5:
    for i,s in enumerate(S):
        if int(s)==0 or int(s)==5:
            ans+=(n-i)
    print(ans)
    exit()


sd=0
d=1
count=[0]*(p+1)
count[0]+=1
for s in S:
    sd+=int(s)*d
    d*=10
    sd%=p
    d%=p
    count[sd]+=1

for cnt in count:
    ans+=cnt*(cnt-1)//2

print(ans)



Measured memory_bytes: 3500
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)

int main(){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    while(true){
        c -= b;
        if(c <= 0){
            cout << "Yes" << endl;
            return 0;
        }
        a -= d;
        if(a <= 0){
            cout << "No" << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long res = 0;
  long long n,k;cin>>n>>k;
  vector<long long> arr(n+1);
  for(int i=1;i<=n;++i){cin>>arr[i];}
  for(int i=1;i<=n;++i){arr[i]+=arr[i-1];}
  map<int,int> mp1;
  for(int i=0;i<=n;++i){
    int curr = (arr[i]-i)%k;
    if(i>=k){
      int lst =  (arr[i-k]-i+k)%k;
      mp1[lst]--;
    }
    res+=mp1[curr];
    mp1[curr]++;
  }
  cout<<res<<endl;
  return 0;
}


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

void dfs(int &m, int p, int t, const vector<vector<int>> &frd, vector<bool> &ald, vector<int> &group){
    if(ald[p] == true){return;}
    ald[p] = true;
    m++;
    group[p] = t;
    for(int x:frd[p]){
        dfs(m, x, t, frd, ald, group);
    } 
    return;
} //DFS　

int main(){
    int N, M, K; cin >> N >> M >> K;
    vector<vector<int>> frd(N+1, vector<int>(0)); 
    vector<vector<int>> block(N+1, vector<int>(0)); 
    for(int i=0; i<M; i++){
        int k, l;
        cin >> k >> l;
        frd[k].emplace_back(l); frd[l].emplace_back(k); 
    }
    for(int i=0; i<K; i++){
        int k, l;
        cin >> k >> l;
        block[k].emplace_back(l); block[l].emplace_back(k); 
    }  //友達関係、ブロック関係の配列取得
    vector<bool> ald_f(N+1, false); //DFSしたかどうか
    vector<int> group(N+1); 
    vector<int> c(N);//何回目のDFSで到達したか
    int t = 0;
    for(int i=1; i<N+1; i++){
        if(ald_f[i] == false){
            int m = 0;
            dfs(m, i,t,frd,ald_f, group); 
            c[t] = m;
            t++; 
        }
    } //DFSを行いｔ個にグルーピング
    for(int i=1; i<N+1; i++){
        int max = c[group[i]];
        int h = group[i];
        int minus = frd[i].size();
        for(int x:block[i]){
            if(group[x] == h){minus++;}
        }
        cout << max - minus -1 << " ";
    }
      //所属するグループの要素数ー直接の友達ー同じグループでブロック関係の人数－１（自分）
    cout << endl;
}


Measured memory_bytes: 13824
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
// memo  fixed  setprecision(20);
using vvll = vector<vector<ll>>;
ll mod =1000000007;
/*"itob" int to "N"base */           template<typename TypeInt> string itob(const TypeInt v, int base){static const char table[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";string ret;static numeric_limits<TypeInt> t;TypeInt n = v;if (t.is_signed) {if (v < 0) n *= -1;}while (n >= base) {ret += table[n%base];n /= base;}ret += table[n];if (t.is_signed) {if (v < 0 && base == 10) ret += '-';}reverse(ret.begin(), ret.end());return ret;}
/*"chmin" a = MAX*/                  template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
/*"chmax" a = MIN*/                  template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
/*"ctoi"  char to int*/              int ctoi(char c) {return c-'0';}
/*"gcd"   MAX*/                      int gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*"lcm"   MIN*/                      int lcm(ll a,ll b){return a*b/gcd(a,b);}
/*"primecheck"If prime,return true.*/bool primecheck(ll n){if(n < 2) return false;else{for(int i = 2; i * i <= n; i++){if(n % i == 0) return false;}return true;}}
string  reverserange(string s,ll a,ll b){reverse(s.begin()+a-1,s.begin()+b); return s;}

int main(){
    ll n;
    cin >> n;
    vector<ll>a(n);
    map<ll,ll>ma;
    for(int i=0;i<n;i++){
        cin >> a.at(i);
        int z = a.at(i);
        if(ma.count(z)){
            ma.at(z)++;
        }
        else {
            ma[z]=1;
        }
    }
    ll che =0;
    for(int i=1;i<=2*10e5;i++){
        if(ma.count(i)){
            che+=ma.at(i)*(ma.at(i)-1)/2;
        }
    }

    for(int i=0;i<n;i++){
        ll d = ma.at(a.at(i));
        ll z = d*(d-1)/2; 
        z-=(d-1)*(d-2)/2;
        ll ans = che-z;
        cout << ans<<endl;
    }
}


Measured memory_bytes: 11648
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <iomanip>

using namespace std;

int main(){
   int N,K;
   cin >> N >> K;
   int p[N];
   for (int i = 0; i < N; i++)
   {
      cin >> p[i];
   }
   sort(p,p+N);
   int ans =0;
   for (int i = 0; i < K; i++)
   {

      ans+=p[i];
   }
   
   cout << ans << endl;
   return 0;
}


Measured memory_bytes: 3600
#include <stdio.h>
 
int main(void) {
	int x, y, a, b, c;
	scanf("%d %d %d", &a, &b, &c);
 
	if(a>b){
		x=a;
		a=b;
		b=x;
	}
	if(b>c){
		y=b;
		b=c;
		c=y;
	}
	if(a>b){
		x=a;
		a=b;
		b=x;
	}
 
	printf("%d %d %d\n", a, b, c);
 
	return 0;
}

Measured memory_bytes: 596
S = list(input())

ans = 0
for i in range(2**(len(S)-1)):
    plus = [""]*(len(S))
    fomula = ""
    for j in range(len(S)-1):
        if(i>>j & 1):
            plus[j] = "+"
    
    for i in range(len(S)):
        fomula += S[i] + plus[i]
    ans += eval(fomula)
    
print(ans)


Measured memory_bytes: 39280
#include <iostream>
//#include <iomanip>
#include <string>
//#include <vector>
//#include <algorithm>
//#include <utility>
//#include <set>
//#include <map>
//#include <queue>
//#include <bitset>
//#include <math.h>
using namespace std ;
//using ll = long long ;
//using ld = long double ;
//using vll = vector<ll> ;
//using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
//using pll = pair<ll,ll> ;

//ll mod = 1000000007 ;
//long double pie = acos(-1) ;

//string yorn(bool a){if(a) return"Yes" ; return "No" ;}
string YorN(bool a){if(a) return"YES" ; return "NO" ;}
//ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
//ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void mysort(vector<long long> &a){sort(a.begin(),a.end()) ;}
//void myrev(vector<long long> &a){reverse(a.begin(),a.end()) ;}

int main(){
	int n ; cin >> n ;
	int odd = 0 ;
	for(int i=0;i<n;i++){
		int a ; cin >> a ;
		if(a&1) odd++ ;
	}
	cout << YorN(odd%2==0) << endl ;
}


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<vector>
#include<set>
#include<algorithm>
#include<tuple>
#include<utility>
#include<cctype>
#include<climits>
#include<map>
#include<queue>
#include<functional>

using namespace std;
template<class T> void chmax(T& a, T b) {if(a < b){a=b;}}
template<class T> void chmin(T& a, T b) {if(a > b){a=b;}}

#define REP(i,a,n) for(int i=a;i<n;++i)
#define RUP(a,b) ((a+b-1)/(b))
#define ENT "\n"
#define REV(v) reverse(v.begin(),v.end())
#define SRTV(v) sort(v.begin(),v.end())
#define SRTA(a,n) sort(a,a+n)
#define MOD 1000000007

typedef long long ll;
typedef tuple<int,int,bool> Tb;

int atcoder(){
    //入力
    int n;
    cin >> n;
    map<int,int> mp;
    REP(i,0,n){
        int tmp;
        cin >> tmp;
        mp[tmp]++;
    }
    //処理
    
    //出力
    cout << mp.size() << ENT;
    return 0;
}

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


Measured memory_bytes: 256
mod=1000000007
H,W,K=map(int,input().split())
dp=[[0]*W for i in range(1+H)]
dp[0][0]=1
C=[0]*(W+1)
C[0]=1
c=[[0,0] for i in range(1+W)]
c[0][0]=1
for i in range(1,1+W):
    c[i][0]=c[i-1][0]+c[i-1][1]
    c[i][1]=c[i-1][0]
for w in range(1,1+W):
    C[w]=c[w][0]
for i in range(H):
    for k in range(W):
        for l in range(k-1,k+2):
            if l<0 or l>=W:
                continue
            x=dp[i][k]*C[min(k,l)]*C[W-1-max(k,l)]%mod
            dp[i+1][l]=(dp[i+1][l]+x)%mod
print(dp[H][K-1])

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 100005;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
vector<vector<int> > G(MAX, vector<int>());
/* function */
void bfs(int st, vector<int>& d) {
    queue<int> q;
    q.push(st);
    d[st] = 0;
    while (!q.empty()) {
        int from = q.front(); q.pop();
        for (int to : G[from]) {
            if (d[to] != NIL) continue;
            d[to] = d[from] + 1;
            q.push(to);
        }
    }
}
/* main */
int main(){
    int N, A, T;
    cin >> N >> T >> A;
    T--, A--;
    int u, v;
    for (int i = 0; i < N - 1; i++) {
        cin >> u >> v;
        u--, v--;
        G[v].push_back(u);
        G[u].push_back(v);
    }

    vector<int> disA(MAX, NIL), disT(MAX, NIL);
    bfs(T, disT);
    bfs(A, disA);

    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (disT[i] >= disA[i]) continue;
        ans = max(ans, disT[i] + max(0, disA[i] - disT[i] - 1));
    }
    cout << ans << '\n';
}


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

int main() {
    int n;
    cin>>n;
    vector<int> vt(n);
    REP(i,n) cin>>vt.at(i);
    int ans=0;
    REP(i,n) REP(j,n) REP(k,n){
        if (i<j && j<k){
            if(vt.at(i)==vt.at(j)) continue;
            if(vt.at(i)==vt.at(k)) continue;
            if(vt.at(k)==vt.at(j)) continue;
            if((ll)vt.at(i)+vt.at(j)+vt.at(k)>2*max({vt.at(i),vt.at(j),vt.at(k)})) ans++; 
        
        }
       
    }
    cout<<ans<<endl;
    return 0;
    
    
}

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

int main() {
	int N,K;
	double t,mE;
	cin >> N >> K;
	vector<double> p(N);

	rep(i,N) {
		cin >> t;
		rep(j,t)
			p.at(i) += (j+1)/t;
	}

	t = 0;
	rep(i,K)
		t += p.at(i);
	mE = t;
	
	rep(i,N-K) {
		t = t-p.at(i)+p.at(i+K);
		mE = max(mE, t);
	}

	cout << setprecision(30) << mE << endl;
}

Measured memory_bytes: 1792
import queue

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

ans = [-1 for _ in range(n)]
ans[0] = 0
q = queue.Queue()
q.put(0)
while not q.empty():
    start = q.get()
    for end in maze[start]:
        if ans[end] == -1:
            q.put(end)
            ans[end] = start

if -1 in ans[1:]:
    print('No')
else:
    print('Yes')
    for i in range(1,n):
        print(ans[i]+1)


Measured memory_bytes: 34988
n = int(input())
x = list(input())
bits = sum(list(map(int, x)))
if bits == 0:
    for i in range(n):
        print(1)
    exit()
if bits == 1:
    if x[-1] == '1':
        for i in range(n-1):
            print(2)
        print(0)
    else:
        for i in range(n-1):
            if x[i] == '1':
                print(0)
            else:
                print(1)
        print(2)
    exit()


def popcount(a):
    ret = 0
    while a > 0:
        if a % 2 == 1:
            ret += 1
        a //= 2
    return ret


## i bit 目を反転したときのbit +- 1 に対する余り
s_m = []
s_p = []

# x の bit+-1 に対する余り
bits_m = bits - 1
bits_p = bits + 1
surp_m = int(x[0]) % bits_m
surp_p = int(x[0]) % bits_p
# 2**i の bit+-1に対する余り
two_m = [1 % bits_m]
two_p = [1 % bits_p]
for i in range(1, n):
    surp_m = (2 * surp_m + int(x[i])) % bits_m
    surp_p = (2 * surp_p + int(x[i])) % bits_p
    two_m += [(two_m[i-1] * 2) % bits_m]
    two_p += [(two_p[i-1] * 2) % bits_p]

for i in range(n-1, -1, -1):
    s_m += [(surp_m - two_m[i]) % bits_m]
    s_p += [(surp_p + two_p[i]) % bits_p]

f = [0]
for i in range(1, n+1):
    f += [f[i % popcount(i)] + 1]


for i in range(n):
    if x[i] == '1':
        print(f[s_m[i]] + 1)
    else:
        print(f[s_p[i]] + 1)


Measured memory_bytes: 45580
s = input()
ls = len(s)

def check(x, y):
    count = 0
    for i in range(len(x)):
        if x[i] != y[i]:
            count += 1
    print(count)

if ls%2 == 0:
    if s[0] == '1':
        s1 = '10'*(ls//2)
        check(s, s1)
    if s[0] == '0':
        s2 = '01'*(ls//2)
        check(s, s2)
else:
    if s[0] == '1':
        s3 = '10'*(ls//2) + '1'
        check(s, s3)
    if s[0] == '0':
        s4 = '01'*(ls//2) + '0'
        check(s, s4)

Measured memory_bytes: 3188
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
int acs(const void *a, const void *b){return *(int*)a - *(int*)b;} /* 1,2,3,4.. */
int des(const void *a, const void *b){return *(int*)b - *(int*)a;} /* 8,7,6,5.. */
int cmp_char(const void *a, const void *b){return *(char*)a - *(char*)b;} /* a,b,c,d.. */
int cmp_str(const void *a, const void *b){return strcmp(*(const char **)a, *(const char **)b);} /* aaa,aab.. */
#define min(a,b) (a < b ? a: b)
#define max(a,b) (a > b ? a: b)
#define rep(i, l, r) for (int i = l; i < r; i++)
#define MAX 100001
#define MOD 1000000007

typedef long long int lli;

int main(void) {
  int d;
  scanf("%d", &d);
  if (d == 25) printf("Christmas\n");
  else if (d == 24) printf("Christmas Eve\n");
  else if (d == 23) printf("Christmas Eve Eve\n");
  else printf("Christmas Eve Eve Eve\n");
  return 0;
}


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

int main(int argc, const char * argv[])
{
    long long pNum, baseTime, tmp, total = 0, preTmp = -1;
    cin>>pNum>>baseTime;
    while(pNum > 0)
    {
        cin>>tmp;
        pNum --;
        if(preTmp == -1)
        {
            preTmp = tmp;
            continue;
        }
        if((preTmp + baseTime) <= tmp) total += baseTime;
        else total += (tmp - preTmp);
        preTmp = tmp;
    }
    total += baseTime;
    cout<< total<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long  table[1010][100010];
long long  val[110];
long long  wt[110];
int main()
{
    long long  n,w;
    cin>>n;
    cin>>w;
    for(long long  i=1;i<=n;i++)
    {
        cin>>wt[i];
        cin>>val[i];
    }
    for(long long  i=1;i<=n;i++)
    {
        for(long long  j=1;j<=w;j++)
        {
            if(wt[i]<=w && j-wt[i]>=0)
            {

                table[i][j]=max(table[i-1][j],val[i]+table[i-1][j-wt[i]]);
            }

            else
                table[i][j]=table[i-1][j];
        }
    }
//    for(int i=0;i<=n;i++)
//    {
//        for(int j=0;j<=w;j++)
//            cout<<table[i][j]<< " ";
//        cout<<endl;
//    }
    cout<<table[n][w]<<endl;
    return 0;
}



Measured memory_bytes: 79360
;; D - Semi Common Multiple

(defun main ()
  (let* ((N (read))
         (M (read))
         (A (loop repeat N collect (read))))
    (princ (solve N M A))
    (fresh-line)))

(defun solve (N M A)
  (let* ((H (mapcar #'(lambda (x) (floor x 2)) A)) ; a_i / 2
         (lcm (loop for x in H
                    for l = x then (lcm l x) while (<= l M)
                    finally (return l)))) ; Hの最小公倍数
    (if (and (<= lcm M)
             (every #'(lambda (x) (oddp (floor lcm x))) H)) ; 全要素の奇数倍
        (ash (1+ (floor M lcm)) -1) ; M以下のlcmの奇数倍の個数
        0)))

(main)


Measured memory_bytes: 61924
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

bool isprime(int p) {
	if (p == 1) return false;
	for (int i = 2; i < p; i++) {
		if (p % i == 0) return false;
	}
	return true;
}
int main() {
	int N;
	cin >> N;

	for (int i = 31; i <= 5555; i += 30) {
		if (isprime(i) == true) {
			if (i != 31) cout << " ";
			cout << i; N--;
		}
		if (N == 0) break;
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

void getAnswer( double a, double b, double c, double d, double e, double f, double* x, double* y );

int main( void )
{
	double a;
	double b;
	double c;
	double d;
	double e;
	double f;
	
	double x;
	double y;
	
	while( scanf( "%lf %lf %lf %lf %lf %lf", &a, &b, &c, &d, &e, &f ) != EOF )
	{
		getAnswer( a, b, c, d, e, f, &x, &y );
		printf( "%.3lf %.3lf\n", x + 0.0001, y + 0.0001 );
	}
	
	return (0);
}

void getAnswer( double a, double b, double c, double d, double e, double f, double* x, double* y )
{
	*x = ( b * f - c * e ) / ( b * d - a * e );
	*y = ( c - a * ( b * f - c * e ) / ( b * d - a * e ) ) / b;
}

Measured memory_bytes: 656
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int t[100002];
ll n;
ll arr[1000002];
int jump(int i)
{
	if(i>=n-1)
	return 0;
	if(t[i]!=-1)
	return t[i];
	else 
{
	if(i<n-2)
	return t[i]=min(abs(arr[i]-arr[i+1])+jump(i+1),abs(arr[i]-arr[i+2])+jump(i+2));
	else 
	return t[i]=abs(arr[i]-arr[i+1]);
	}
}
int main()
{
	memset (t,-1,sizeof(t));
	cin>>n;
	for(int i=0;i<n;i++)
	cin>>arr[i];
	int k=jump(0);
	cout<<k<<endl;
	return 0;
}

Measured memory_bytes: 7864
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF (1ll << 60)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
using vl = vector<ll>;
using vvl = vector<vl>;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
using ll = long long;
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}

int main() {
    ll N, x;
    cin >> N >> x;
    vector<ll> a(N);
    REP(i, N) { cin >> a[i]; }
    ll ans = 0LL;
    for(int i = 0; i < N - 1; i++) {
        while(a[i] + a[i + 1] > x) {
            if(a[i + 1] > 0) {
                int hoge = min(a[i + 1], a[i] + a[i + 1] - x);
                a[i + 1] -= hoge;
                ans += hoge;
            } else if(a[i] > 0) {
                a[i]--;
                ans++;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
#ifndef VS
#include<bits/stdc++.h>
#endif

using namespace std;
typedef long long LL;

#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}
}star;
#define DEBUG if(0)
#endif

#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}

class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }};

const int mod = 1e9 + 7;
typedef vector<LL> V;
typedef vector<V> VV;
int main() {
	string s;
	while (cin >> s) {
		VV dp(4, V(3, 0));
		dp[0][0] = 1;
		for (auto c : s) {
			VV nxt(4, V(3, 0));
			if (c == '0' || c == '?') {
				for (int i : range(4)) {
					nxt[i][1] += dp[i][0];
					nxt[i][2] += dp[i][1];
					nxt[i][1] += dp[i][2];
				}
			}
			if (c == '1' || c == '?') {
				for (int i : range(4)) {
					nxt[min(i + 1, 3)][0] += dp[i][0];
					nxt[i][0] += dp[i][1];
					nxt[i][1] += dp[i][2];
				}
			}
			for (auto &a : nxt)for (auto &b : a)b %= mod;
			swap(dp, nxt);
		}
		cout << (dp[3][0] + dp[3][1] + dp[3][2] + dp[2][0] + dp[2][1] + dp[1][0]) % mod << endl;
	}
	return 0;
}


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

int main() {
  int a,b;
  cin>>a>>b;
  int c;
  if(b<10){
    c=a*10+b;
  }
  if(10<=b&&b<100){
    c=a*100+b;
  }
  if(b==100){
    c=a*1000+b;
  }
  int z=sqrt(c);
  if(z*z==c){
    cout<<"Yes"<<endl;
    return 0;
  }
  cout<<"No"<<endl;
  return 0;
}

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

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(obj) (obj).begin(), (obj).end()
#define bit(n) (1LL << (n))

typedef long long ll;

using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int x,n;
  cin>>x>>n;
  // pに含まれない整数（0以上101以下）
  bool nps[102];
  
  rep(i,102) {
    nps[i] = true;
  }
  
  rep(i,n) {
    int p;
    cin>>p;
    
    nps[p] = false;
  }
  
  int diff = 1000;
  int ans = 1000;
  
  rep(i,102) {
    if(nps[i] == true) {
      // cout<<i<<endl;
      if(diff>abs(x-i)) {
        // cout<<i<<endl;
        diff = abs(x-i);
        ans = i;
      }
      
    } else {
      continue;
    }
  }
  
  cout<<ans;
  return 0;
}

Measured memory_bytes: 3688
#include <cstdio>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define pb push_back
#define fi first
#define se second
#define SIZE 100333
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;

int main() {
	ll n, mul = 1;
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++)	mul*=i, mul%=MOD;
	printf("%lld\n",mul);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define uniq(x) (x).erase(unique(ALL(x)),(x).end())
#define SORT(x) sort(ALL(x))
#define REV(x) reverse(ALL(x))
#define foreach(it,x) for(__typeof((x).begin()) it=(x).begin();it!=(x).end();it++)
#define debug(x) cerr<<#x<<"="<<(x)<<endl
#define gett() cerr<<"Time:"<<clock()<<"ms."<<endl
#define ri(x) scanf("%d",&x)
#define rl(x) scanf("%lld",&x)
#define rlcfpoj(x) scanf("%I64d",&x)
#define pi(x) printf("%d",x)
#define pl(x) printf("%lld",x)
#define plcfpoj(x) printf("%I64d",x)
#define lfd() printf("\n")
#define sp() printf(" ")
#define inrep(x) int x;scanf("%d",&x);while(x--)
#define testbit(mask,i) (((mask)>>(i))&1)
#define setbit(mask,i) ((mask)|(1<<i))
#define delbit(mask,i) ((mask)^(1<<i))
int k,x;
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>k>>x;
	for(int i=x-k+1;i<=x+k-1;i++)
		cout<<i<<' ';
	return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n = int(input())
a = [int(input()) for _ in range(n)]
dp = [float('inf')]*n
for i in range(n):
    x = bisect.bisect_right(dp,-a[i])
    dp[x] = -a[i]
c = dp.count(float('inf'))
print(n-c)


Measured memory_bytes: 54872
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s, t;
    cin>>s>>t;
    int ss = s.length(), tt = t.length();
    int dp[ss+1][tt+1];
    for(int i=0; i<=tt; i++)
        dp[0][i] = 0;
    for(int i=0; i<=ss; i++)
        dp[i][0] = 0;
    for(int i=1; i<=ss; i++){
        for(int j=1; j<=tt; j++){
            if(s[i-1] == t[j-1]){
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            else{
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    string ans = "";
    int i = ss, j = tt, val = dp[ss][tt];
    while(val > 0){
        if(dp[i][j] != dp[i-1][j] && dp[i][j] != dp[i][j-1]){
            i--; j--;val--;
            ans += s[i];
        }
        else{
            if(dp[i][j] == dp[i][j-1])
                j--;
            else
                i--;
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans;
}

Measured memory_bytes: 35456
a = input()
a = int(a)
 
line = [int(k) for k in input().split()]
for k in range(len(line)):
  if line[k] % 2 == 0:
    if not line[k] % 5 == 0 and not line[k] % 3 == 0:
      print("DENIED")
      break
  if k == a-1:
    print("APPROVED")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> l4;
//typedef pair<double, double> dd;
#define mp make_pair
#define pb push_back
#define debug(x) cerr << #x << " = " << x << " "

const int N = 11;
char s[N];
int n;
void dfs(int cur, int maxi)
{
  if (cur == n)
    {
      puts(s);
      return;
    }
  for (int nxt = 0; nxt <= maxi + 1; ++nxt)
    {
      s[cur] = 'a' + nxt;
      dfs(cur+1, max(maxi, nxt));
    }
}
int main()
{
  while (~scanf("%d", &n))
    {
      s[n] = '\0';
      dfs(0, -1);
    }
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
 
#define ff first
#define ss second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;

bool mark[10][100001];
int dp[10][100001];

int f(int i, int j) {
	if(j == 0) return true;
	if(i == 6) return false;
	if(mark[i][j]) return dp[i][j];
	mark[i][j] = true;

	int ret = f(i+1, j);
	if(j >= i+100) ret |= f(i, j-i-100);
	return dp[i][j] = ret;
}

int main() {
	int n;
 
	scanf("%d", &n);

	int ans = f(0,n);

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

    return 0;
}

Measured memory_bytes: 4864
#include<bits/stdc++.h>
#define endl "\n"
#define pb push_back
#define ll long long
#define d1(x)  cerr << #x << "--> " << x << endl
#define d2(x,y)  cerr << #x << "--> " << x << " | " << #y << "--> " << y <<endl
#define d3(x,y,z)  cerr << #x << "--> " << x << " | " << #y << "--> " << y <<" | " << #z << "--> "<< z<< endl
#define d4(x,y,z,w)  cerr << #x << "--> " << x << " | " << #y << "--> " << y <<" | " << #z << "--> "<< z << " | "<< #w << "--> " << w <<endl
#define vpll vector<pair<ll,ll>>
#define F first
#define S second
#define T ll tt; cin>>tt; while(tt--)
using namespace std;
ll mode=1e9+7;
const long long maxn=2*1e5;
const long long inf=99999999999;
ll __lcm(ll a, ll b){ return (a*b)/__gcd(a,b); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll getRand(ll l, ll r){ uniform_int_distribution<ll> uid(l, r); return uid(rng); }

vector<ll> adj[maxn];

void solve(){
	
	ll n,m;
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		ll a,b;
		cin>>a>>b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	set<ll> s;
	for (int i=2;i<=n;i++) s.insert(i);
	queue<ll> q;
	q.push(1);
	
	vector<ll> ans(n+1, 0);
	
	while(!q.empty()){
		ll u=q.front();
		q.pop();
		for (auto v:adj[u]){
			if (s.find(v)!=s.end()){
				s.erase(s.find(v));
				q.push(v);
				ans[v]=u;
			}
		}
	}
	
	if (s.size()==0){
		cout<<"Yes"<<endl;
		for (int i=2;i<=n;i++) cout<<ans[i]<<endl;
	}
	else{
		cout<<"No"<<endl;
	}
	
	
	
	return;
}

 
int main(){ 
    
    #ifndef ONLINE_JUDGE
	//	freopen("input.txt", "r", stdin);
    #endif
    srand(time(0)); 
    
    ios::sync_with_stdio(0);
    cin.tie(0);
 	
	//T{ solve(); }
	solve();
	
	
	return 0;
	
}

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

const int N = 1e5;
long long a[N + 7];
int b[N + 7];
int n;
long long wynik = 0;

int main() {
	ios_base::sync_with_stdio(0);
	cin >> n;
	for(int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
	
	for(int i = n; i > 0; --i) {
		a[i] += wynik;
		int c = a[i] % b[i];
		if(c != 0) {
			wynik += b[i] - c;
		}	
	}
	
	cout << wynik << endl;
	return 0;
}

Measured memory_bytes: 1408
N = int(input())
T = [int(input()) for i in range(N)]

def gcd(x,y):
    a = max(x,y)
    b = min(x,y)
    while b!=0:
        a,b = b,a%b
    return a

g = T[0]
for i in range(N-1):
    g = (g*T[i+1])//gcd(g,T[i+1])
print(g)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
using llong = long long;
using P = pair<int, int>;
const int inf = 1 << 20;
const int mod = 1e9 + 7;

int main() {
   while (true) {
      int h, w;
      cin >> h >>  w;
      if (h == 0 && w == 0)
         break;
      rep(i, h) {
         rep(j, w) { cout << '#'; }
         cout << endl;
      }
      cout << endl;
   }
   return 0;
}


Measured memory_bytes: 3032
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int x = sc.nextInt();
		int count = 1;
		int point = 0;
		
		for(int i=0;i<n;i++) {
			point += sc.nextInt();
			if(point <= x) {
				count++;
			}else {
				break;
			}
		}
		System.out.println(count);
	}

}


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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 9;
const int M = 2300;
const ll MX = (ll)1e10 + 5;

bitset<M> pr;
vector<int> lit;

ll mult(ll a, ll b){
  return min(MX,a*b);
}

map<pii, int> pri;

int main(){
  fastIO;
  for(int i = 2; i < M ; i++ ){
    if(pr[i] == 1) continue;
    for(int j = 2 * i ; j < M ; j += i){
      pr[j] = 1;
    }
  }
  for(int i = 2; i < M ; i ++ )
    if(pr[i] == 0)
      lit.push_back(i);
  int n;
  cin >> n;
  ll x;
  ll nw;
  int cnt;
  ll f;
  int ans = 0;
  int d = 0;
  int emp = 0;
  ll cur;
  for(int i = 1; i <= n; i ++ ){
    cin >> x;
    nw = 1;
    cur = 1;
    for(auto p : lit){
      cnt = 0;
      while(x % p == 0){
        x /= p;
        cnt++;
      }
      cnt %= 3;
      for(int t = 0;t < cnt; t ++ )
        cur *= p;
      if(cnt)
        for(int j = 0 ; j < 3 - cnt; j ++ )
          nw=mult(nw,p);
    }
    if(x > 1){
      f = sqrt(x);
      while(f * f < x){
        f ++ ;
      }
      if(f * f == x){
        nw = mult(nw, f);
        cur *= f * f;
      }
      else{
        cur *= x;
        nw = mult(nw, x);
        nw = mult(nw, x);
      }
    }
    if(nw == MX){
      ans ++ ;
    }
    else if(nw == 1){
      emp = 1;
    }
    else{
      pri[mp(cur, nw)] ++ ;
    }
  }
  for(auto x : pri){
    if(pri[x.fi] > pri[mp(x.fi.se, x.fi.fi)]){
      ans += x.se;
    }
    else if(pri[x.fi] == pri[mp(x.fi.se, x.fi.fi)]){
      d += x.se;
    }
  }
  cout << ans + d/2 + emp;
  return 0;
}

Measured memory_bytes: 10496
#include <stdio.h>
#include <strings.h>
int main() {
    int a,b;
    char s[15],t[15],u[15];
    scanf("%s %s", &s, &t);
    scanf("%d %d", &a, &b);
    scanf("%s", &u);
    if(strcmp(s,u) == 0) {
        --a;
    } else if(strcmp(t,u) == 0) {
        --b;
    }
    printf("%d %d\n", a, b);
    return 0;
}

Measured memory_bytes: 2144
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
string out[2]={"First", "Second"};
int main()
{
	string s;cin>>s;
	int n=s.size();if(s[0]==s[n-1]) n++;
	cout<<out[((n+1)%2)]<<endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
constexpr int mod=1000000007;
constexpr int mod1=998244353;
vector<int> dx={0,-1,0,1},dy={1,0,-1,0};
bool inside(int y,int x,int h,int w){
	if(y<h && y>=0 && x<w && x>=0) return true;
	return false;
}





int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	int ans = 0;
	for(int i = 1; i <= n; i++){
		int cnt = 0, k = i;
		while(k > 0){
			cnt++;
			k /= 10;
		}
		if(cnt % 2 == 1) ans++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#define INF 10000000
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>

using namespace std;

typedef long long ll;
typedef pair<int,string> P;

static const double eps = 1e-8;

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

		memset(path,0x3,sizeof(path));
		int m=-1;
		for(int i=0;i<n;i++){
			int from,to,cost;
			scanf("%d %d %d",&from,&to,&cost);
			path[from][to] = path[to][from] = min(path[from][to],cost);
			m = max(from,max(to,m));
		}

		for(int k=0;k<=m;k++){
			for(int i=0;i<=m;i++){
				for(int j=0;j<=m;j++){
					if(i==j) path[i][j] = 0;
					else path[i][j] = min(path[i][k]+path[k][j],path[i][j]);
				}
			}
		}

		int mincost = INF;
		int idx=0;
		for(int i=0;i<=m;i++){
			int sum=0;
			for(int j=0;j<=m;j++){
				sum+=path[i][j];
			}
			if(sum < mincost){
				mincost = sum;
				idx = i;
			}
		}

		printf("%d %d\n",idx,mincost);
	}
}

Measured memory_bytes: 0
#include<stdio.h>
int main()
{
  char s[4];
  int i,j,dem[4];
  scanf("%s", &s);
  for (i=0; i<4; i++)
    {
      dem[i]=1;
      for (j=0; j<4; j++)
        {
          if (i!=j)
            {
              if (s[i]==s[j]) dem[i]++;
            }
        }
    }
  if (dem[0]==2 && dem[1]==2 && dem[2]==2 && dem[3]==2) printf("Yes");
   else printf("No");
  return 0;
}


Measured memory_bytes: 128