akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
bitset<N>V;
int main()
{
    int n,s=0;
    scanf("%d",&n);
    V[0]=1;
    for(int i=0,x; i<n; i++)scanf("%d",&x),s+=x,V|=V<<x;
    for(int i=s/2;;i--)
    if(V[i])
    {
        printf("%d\n",s-i);
        return 0;
    }
}


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

using namespace std;

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

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

  // int min_idx = -1;
  // for (int i=0; i<n; i++) {
  //   if (a[i] == 1) {
  //     min_idx = i;
  //     break;
  //   }
  // }

  // int left_rem = min_idx;
  // int right_rem = a.size() - min_idx - 1;
  // int ans = ((left_rem + k-2) / (k-1)) + ((right_rem + k-2) / (k-1));

  // cout << ((left_rem + k-2) / (k-1)) << "," << ((right_rem + k-2) / (k-1)) << endl;

  int ans = ((a.size() - 1) + k-2) / (k-1);
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 640
def make_card(i, card):
    suit, value = card.split()
    return (int(value), i, card)


def partition_stable(a, p, r):
    x, i = a[r], p - 1
    for j in range(p, r):
        if a[j] <= x:
            i += 1
            a[i], a[j] = a[j], a[i]
    i += 1
    a[i], a[r] = a[r], a[i]
    return i


def partition_not_stable(a, p, r):
    x, i = a[r][0], p - 1
    for j in range(p, r):
        if a[j][0] <= x:
            i += 1
            a[i], a[j] = a[j], a[i]
    i += 1
    a[i], a[r] = a[r], a[i]
    return i


def quick_sort(a, p, r, func):
    if p < r:
        q = func(a, p, r)
        quick_sort(a, p, q - 1, func)
        quick_sort(a, q + 1, r, func)


n = int(input())
a = list(make_card(i, input()) for i in range(n))
b = a[:]

quick_sort(a, 0, n - 1, partition_not_stable)
quick_sort(b, 0, n - 1, partition_stable)
print(('S' if a == b else 'Not s') + 'table')
print('\n'.join(card[2] for card in a))



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

int main() {
    int n;
    cin >> n;
    vector<int> ds(n);
    rep(i,n) cin >> ds[i];
    int sum = accumulate(ds.begin(), ds.end(),0);
    int ans = 0;
    rep(i,n){
        ans += (sum-ds[i])*ds[i];
    }
    cout << ans/2 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define INF 999999999
#define rep(i,m,n) for(int i = m;i < n;i++)
#define pb(n) push_back(n)
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(20) << S << endl;
#define Vecpr vector<pair<lli,lli>>
#define mod 1000000007;
bool is_prime(lli x) {
  for(lli i = 2; i * i <= x; i++) {
    if(x % i == 0) return false;
  }
  return true;
}
int main() {
  lli A,B,C=0,D=0,E=0,F=0,G=0,H=0,N,M;
  cin >> N;
  vector<lli>P(N);
  rep(i,0,N)cin >> P[i];
  rep(i,0,N){
    if(i+1==P[i]){
      C++;
      if(P[i]!=N)swap(P[i],P[i+1]);
      else swap(P[i],P[i-1]);
    }
  }
  Out(C);
} 


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

#define INF 1001001001
#define LINF 1001001001001001001
#define MOD 1000000007
#define MOD2 998244353

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

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define rep1(i,a,b) for(int a_=(a),b_=(b),i=a_;i<b_;++i)
#define repr(i,n) for(int _i=(n),i=_i;i>0;--i)

#define db(x) cerr<<#x<<" = "<<x<<" ";
#define db2(x,y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<") ";
#define db3(x,y,z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = ("<<x<<", "<<y<<", "<<z<<") ";
#define ln cout<<endl;

#define all(a)  (a).begin(),(a).end()
#define dig(n)  to_string(n).length()

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define se second
#define fi first

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

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return (a*b)/gcd(a,b);}

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

int main(){
    bool flag=true;
    ll ans=0,sum=0;

    int n,m;
    cin >>n;

    rep(i,n){
        int ai;
        cin >> ai;

        if(ai%2==0){
            if(ai%3!=0 && ai%5!=0){
                flag=false;
                break;
            }
        }

    }



    //cout <<fixed<<setprecision(16)<< << endl;
    //cout<<ans<<endl;
    
    if(flag)cout << "APPROVED" <<endl;
    else cout << "DENIED" <<endl;
    
    return 0;
}


Measured memory_bytes: 256
function main(input) {
    // const number = Number(input.split("\n")[0]);
    const list = input.split(" ").map(v => Number(v));
    const result = { true:"YES",false:"NO" };

    const is575 = list => {
        // const has575 = [5, 7];
        const syllable575 = new Map();
        syllable575.set(5, 2);
        syllable575.set(7, 1);

        for (const syllable of syllable575.keys()) {
            if (list.filter(v => v === syllable ? true : false ).length !== syllable575.get(syllable)) {
                return(false);
            }
        }
        return(true);
    }
    console.log(result[is575(list)]) ;
}


// let input = "5 5 7";
// let input = "7 5 7";
// let input = "7 5 5";

// main(input);
main(require("fs").readFileSync("/dev/stdin","utf8"));
  

Measured memory_bytes: 29552
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
#define bit(n) (1LL << (n))
#define len(x) ((ll)(x).size())
#define debug(var) cout << "[" << #var << "]\n" << var << "\n\n"
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;
const double EPS = 1e-9;

template <typename T>
ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i];
    if (i < len - 1)
      s << ' ';
  }
  return s;
}

template <typename T>
ostream& operator<<(ostream& s, const vector<vector<T>>& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
    s << vv[i];
    if (i != len - 1)
      cout << '\n';
  }
  return s;
}

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;
}

__attribute__((constructor)) void initial() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}

signed main() {
  int A, B, K;
  cin >> A >> B >> K;
  vector<int> AB(2);
  AB[0] = A, AB[1] = B;
  int ind = 0;
  rep(i, K) {
    if (AB[ind] % 2 == 1)
      AB[ind]--;

    AB[ind] /= 2;
    AB[(ind + 1) % 2] += AB[ind];

    ind++;
    ind %= 2;
  }

  cout << AB << "\n";
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp2
{

    class Program
    {
        static void Main(string[] args)
        {
            int len = int.Parse(Console.ReadLine());
            string S = Console.ReadLine();
            if (len % 2 != 0)
            {
                Console.WriteLine("No");
                return;
            }

            if (S.Substring(0, len/2) == S.Substring(len / 2, len/2))
            {
                Console.WriteLine("Yes");
                return;
            }
            else
            {
                Console.WriteLine("No");
                return;
            }

        }
    }
}

    




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

int N, A[5010];
vector<int>to[100005];
vector<pair<long long, int>> dp[5010];
int sz[5010];
/*
dp[cu][cut] := 頂点cuを根とした部分木について辺の削除をcut回行ったときに
{根と連結している頂点の電力の総和の最小値, 
根と連結しているグループが全てバッテリーにできるか}
*/
void marge(int cu, int to) {
	vector<pair<long long, int>>res(sz[cu] + sz[to] + 1, {1e18,0});
	for (int i = 0;i<sz[cu];++i) {
		for (int j = 0;j<sz[to]; ++j) {
			//
			res[i + j].first = min(res[i + j].first, dp[cu][i].first + dp[to][j].first);
			if (dp[cu][i].second and dp[to][j].second) { 
				res[i + j].second = 1; 
			}
			//
			if (dp[to][j].first < 0 or dp[to][j].second) {
				res[i + j + 1].first = min(res[i + j + 1].first, dp[cu][i].first);
			}
			if ((dp[to][j].first < 0 or dp[to][j].second) and dp[cu][i].second) { 
				res[i + j + 1].second = 1; 
			}
		}
	}
	swap(dp[cu], res);
	sz[cu] += sz[to] + 1;
}

void dfs(int v, int p = -1) {
	sz[v] = 1;
	dp[v].resize(1);
	dp[v][0] = { A[v], 0 < A[v] };
	for (int e : to[v]) {
		if (p == e) {
			continue;
		}
		dfs(e, v);
		marge(v, e);
	}
}


int main() {
	int N;
	cin >> N;
	for (int i = 0; i < N; ++i) {
		cin >> A[i];
	}
	for (int n = 0; n < N - 1; ++n) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		to[a].push_back(b);
		to[b].push_back(a);
	}
	dfs(0);
	int ans = 1e9;
	for (int i = 0; i < sz[0]; ++i) {
		if (dp[0][i].first < 0 or dp[0][i].second) {
			ans = min(ans, i);
		}
	}
	cout << ans << endl;
	return 0;
}


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

typedef long long ll;

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

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define ANS(n) cout << (n) << endl

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORR(i,a,b) for(int i=(a);i>=(b);i--)

#define ALL(obj) (obj).begin(),(obj).end()

#define pii pair<int,int>

#define pb(a) push_back(a)
#define mp make_pair

int main()
{
	int n;
	cin >> n;
	map<int,int>even,odd;
	FOR(i,0,n){
		int v;
		cin >> v;
		if(i % 2 == 0){
			if(even.find(v) == even.end()){
				even[v] = 1;
			}else{
				even[v]++;
			}
		}else{
			if(odd.find(v) == odd.end()){
				odd[v] = 1;
			}else{
				odd[v]++;
			}
		}
	}
	int ans = 0;
	int x = -1, y = -1;
	int xCount = 0, yCount = 0;
	FOR(i,1,100001){
		if(even[i] > xCount){
			y = x;
			yCount = xCount;
			x = i;
			xCount = even[i];
		}else if(even[i] > yCount){
			y = i;
			yCount = even[i];
		}
	}
	FOR(i,1,100001){
		if(i != x && i != y)
			ans += even[i];
	}
	int z = -1, w = -1;
	int zCount = 0, wCount = 0;
	FOR(i,1,100001){
		if(odd[i] > zCount){
			w = z;
			wCount = zCount;
			z = i;
			zCount = odd[i];
		}else if(odd[i] > wCount){
			w = i;
			wCount = odd[i];
		}
	}
	FOR(i,1,100001){
		if(i != z && i != w)
			ans += odd[i];
	}
	if(x != z){
		ans += yCount + wCount;
	}else{
		ans += min(xCount + wCount, yCount + zCount);
	}
	ANS(ans);
	return 0;
}


Measured memory_bytes: 9600
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll inf = 3e18;
const char sp = ' ';

int N, K, a[100000], tree[1 << 18];
ll s[100001];

int calc(int x) {
	x += (1 << 17);
	int t = 0;
	while (x) {
		t += tree[x];
		x /= 2;
	}
	return t;
}

void update(int l, int r, int p, int q, int k) {
	if (r < p || q < l)return;
	if (p <= l && r <= q)tree[k]++;
	else {
		update(l, (l + r) / 2, p, q, k + k);
		update((l + r) / 2 + 1, r, p, q, k + k + 1);
	}
}

int main() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		a[i] -= K;
	}
	vector<ll>v{ 0 };
	for (int i = 0; i < N; i++) {
		s[i + 1] = s[i] + a[i];
		v.push_back(s[i + 1]);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	ll res = 0;
	for (int i = 0; i <= N; i++) {
		res += calc(lower_bound(v.begin(), v.end(), s[i]) - v.begin());
		update(0, (1 << 17) - 1, lower_bound(v.begin(), v.end(), s[i]) - v.begin(), (1 << 17) - 1, 1);
	}
	cout << res << endl;
}


Measured memory_bytes: 5784
/**
*    created: 09.07.2020 22:16:13
**/
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>
// using bint = boost::multiprecision::cpp_int;
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pcnt(bit) __builtin_popcountll(bit)
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;}
const long double pi = acos(-1.0);
const int MAX = 1000010;
const int INF = 1LL << 60;
const int MOD = 1000000007;
// const int MOD = 998244353;

signed main() {

    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int n; cin >> n;
    int t = 0;
    while (true) {
        if (t*(t+1)/2 >= n) break;
        t++;
    }
    cout << t << endl;
    return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }
int main(int argc, char* argv[]) {
    vint a(3);
    cin >> a[0] >> a[1] >> a[2];
    sort(ALL(a));
    cout << a[0]+a[1] << endl;
    return 0;
}


Measured memory_bytes: 256
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
struct edge { int to, cap, rev; };
int V, E, used[109]; vector<edge> G[109];
void add_edge(int v1, int v2, int cap) {
	G[v1].push_back(edge{ v2, cap, (int)G[v2].size() });
	G[v2].push_back(edge{ v1, 0, (int)G[v1].size() - 1 });
}
int rec(int p, int t, int f) {
	if (p == t) return f;
	used[p] = 1;
	for (auto &e : G[p]) {
		if (used[e.to] || e.cap <= 0) continue;
		int res = rec(e.to, t, min(e.cap, f));
		if (res) {
			e.cap -= res, G[e.to][e.rev].cap += res;
			return res;
		}
	}
	return 0;
}
int max_flow(int s, int t) {
	int ret = 0;
	while (true) {
		fill(used, used + V, 0);
		int res = rec(s, t, 2147483647);
		if (!res) break;
		ret += res;
	}
	return ret;
}
int main() {
	cin >> V >> E;
	for (int i = 0; i < E; i++) {
		int s, t, u;
		cin >> s >> t >> u;
		add_edge(s, t, u);
	}
	cout << max_flow(0, V - 1) << endl;
}

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

int main()
{
	int n;
	string w[110];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> w[i];
	}
	bool ans = true;
	for (int i = 0; i < n - 1; i++) {
		if (w[i][w[i].length() - 1] != w[i + 1][0])
			ans = false;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (w[i] == w[j]) {
				ans = false;
			}
		}
	}
	if (ans) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
    return 0;
}



Measured memory_bytes: 256
s = input()
i = len(s)//2
count1 = 0
count2 = 0
if len(s)%2 == 0:
    s1 = '01'*i
    s2 = '10'*i
else:
    s1 = '01'*i + '0'
    s2 = '10'*i + '1'
for x,y,z in zip(s,s1,s2):
    if x != y:
        count1 += 1
    if x != z:
        count2 += 1
print(min(count1,count2))

Measured memory_bytes: 3316
lr=input().split()
l=int(lr[0])
r=int(lr[1])

mod=2018
for i in range(r-l):
    x=r-l-i
    if mod==0:
        break
    for j in range(x):
        if (l+j)%2019==0 or (r-i)%2019==0:
            mod=0
            break
        else:
            a=(l+j)*(r-i)
            b=a%2019
            if b<mod:
                mod=b

print(mod)


Measured memory_bytes: 3060
# -*- coding: utf-8 -*-
from sys import stdin
# import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


N = d_in()
V_list = ds_in()
C_list = ds_in()

ans = 0
for v, c in zip(V_list, C_list):
    diff = v - c
    if diff > 0:
        ans += diff
print(ans)


Measured memory_bytes: 3060
N = int(input())
L = list(map(int,input().split()))
dp = [10**10 for _ in range(N+3)]
dp[0] = L[0]
for i in range(N):
    try:
        dp[i+1] = min(dp[i]+abs(L[i]-L[i+1]),dp[i+1])
        dp[i+2] = min(dp[i]+abs(L[i]-L[i+2]),dp[i+2])
    except:
        pass
#print(dp)
print(dp[N-1]-dp[0])



Measured memory_bytes: 13976
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>

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)
inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

#define AMAX 1000000

int main(){
	ll N, K; cin >> N >> K;
	vector<pair<ll, ll> > vec;

	REP(i, N){
		ll a, b; cin >> a >> b;
		vec.push_back(make_pair(a, b));
	}

	sort(vec.begin(), vec.end());

	REP(i, vec.size()){
		K -= vec[i].second;
		if(K <= 0){
			cout << vec[i].first << endl;
			break;
		}
	}

	return 0;
}

Measured memory_bytes: 2420
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

using namespace std;

typedef long long ll;

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

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

vector<int> as;

int solve(const int N) {
    // {value, count}
    multiset<pair<int, int>> ms;

    for (auto &a : as) {
        auto it = ms.upper_bound({a, 0});
        pair<int, int> item;
        if (it == ms.begin()) {
            item = {a, 1};
            ms.insert(item);
        // } else if (it == ms.end()) {
        //     item = {a, 1};
        //     ms.insert(item);
        } else {
            it--;
            item = *it;
            ms.erase(it);
            item.first = a;
            item.second++;
            ms.insert(item);
        }
        // printf("added: {%d, %d}\n", item.first, item.second);
    }

    return (int) ms.size();
}

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

    as.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> as[i];
    }

    cout << solve(N) << endl;

    return 0;
}


Measured memory_bytes: 5376
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
ll a[200005];
int main(){
	ll n,i;
	cin>>n;
	for(i=0;i<n;i++)
		cin>>a[i];
	sort(a,a+n);
	int flag=1;
	for(i=1;i<n;i++){
		if(a[i]==a[i-1]){
			flag=0;break;
		}
	}
	if(flag)	cout<<"YES";
	else		cout<<"NO";
	return 0;
}

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

using namespace std;

#define COUNTOF(array) (sizeof(array) / sizeof(array[0]))
#define OUT(P) cout << (P) << endl
#define OUT2(P1, P2) cout << (P1) << " " << (P2) << endl

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

    for(int i=a; i<=b; i++) {
        if(abs(i-a) < k || abs(i-b)< k) {
            cout << i << endl;
        }
    }

    return 0;
}



Measured memory_bytes: 256
import sys
input = sys.stdin.readline

"""
後ろから、到達不可能距離の集合を見ていきたい。
集合を持つと厳しいが、最小値だけ持っておけばよい。
"""

N,dist = map(int,input().split())
D = [int(x) for x in input().split()]

# 各ターンの出発位置
start_dist = [dist]
for d in D:
    x = start_dist[-1]
    y = min(abs(x - d), x)
    start_dist.append(y)

ng_dist = [None] * (N+1)
ng_dist[N] = 1

for i,d in enumerate(D[::-1]):
    x = ng_dist[N-i]
    y = x if x <= d//2 else x + d
    ng_dist[N-i-1] = y

input()
Q = [int(x) for x in input().split()]

answer = ['YES' if ng_dist[d] <= start_dist[d-1] else 'NO' for d in Q]

print('\n'.join(answer))

Measured memory_bytes: 106344
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); int max = 1;
		Map<String, Integer> map = new HashMap<String, Integer>();
		int rem = 0;
		for (int i = 0; i < n; i++) {
			String s = sc.next();
			if(map.containsKey(s)) {
				rem = map.get(s)+1;
				map.replace(s, rem);
				max = Math.max(max,rem);
			}else {
				map.put(s, 1);
			}
		}
		List<String> list = new ArrayList<String>();
		for(String key : map.keySet()) {
			if(map.get(key) == max)list.add(key);
		}
		Collections.sort(list);
		for(String key : list) {
			System.out.println(key);
		}
		sc.close();
	}
}

Measured memory_bytes: 82500
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] num = new int[n];

		for (int i = 0; i < n; i++) {
			num[i] = sc.nextInt();
		}

		int max = num[0];
		int min = num[0];
		long sum = 0;

		for (int a : num) {
			if (a > max) {
				max = a;
			}
			if (a < min) {
				min = a;
			}
			sum += a;
		}
		System.out.println(min + " " + max + " " + sum);
		sc.close();
	}

}


Measured memory_bytes: 41464
N=int(input())
S=input()
rgb={"R":0,"G":0,"B":0}
for s in S:
  rgb[s]+=1
ans=rgb["R"]*rgb["G"]*rgb["B"]
for dist in range(1,N//2+1):
  left=0
  while left+dist*2<N:
    if len(set([S[left],S[left+dist],S[left+dist*2]]))==3:
      ans-=1
    left+=1
print(ans)
  


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

using ll=long long;
#define int ll

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

int read(){
	int i;
	scanf("%lld",&i);
	return i;
}

signed main(){
	int N=read(),K=read();
	vector<int> a;
	map<int,int> b;
	REP(i,N){
		int tmp = read();
		a.push_back(tmp);
		if(!b[a.back()]){
			b[a.back()] = read();
		}
		else{
			b[a.back()] += read();
			a.pop_back();
		}
	}
	sort(a.begin(),a.end());
	
	REP(i,a.size()){
		K -= b[a[i]];
		if(K <= 0){
			cout << a[i];
			break;
		}
	}
	
	
}

Measured memory_bytes: 4728
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int five = 0,
            seven = 0;
        for(int i = 0; i < 3; i++){
            int x = sc.nextInt();
            switch(x){
                case 5:
                    five++;
                    break;
                case 7:
                    seven++;
            }
        }
        String answer;
        if(five != 2 || seven != 1){
            answer = "NO";
        } else{
            answer = "YES";
        }
        System.out.println(answer);
    }
}

Measured memory_bytes: 21844
#include <iostream>
using namespace std;
int main() {
  int n,a=0; cin>>n;
  for(int i=1; i<=n; i++){
    int c=0;
    for(int j=1; j<=i; j+=2) if(i%j==0) c++;
    if(c==8) a++; 
  }
  cout<<a;
}

Measured memory_bytes: 3632
from collections import deque
 
s = input()
q = int(input())
 
query = [input().split() for i in range(q)]
 
a = deque([s])
 
flag = True
 
for i in range(q):
    if query[i][0] == "1":
        flag = not(flag)
    else:
        if (query[i][1] == "1" and flag) or (query[i][1] != "1" and not(flag)):
            a.appendleft(query[i][2])
        else:
            a.append(query[i][2])
 
b = "".join(a)
if not(flag):
    b = b[::-1]
 
print(b)

Measured memory_bytes: 42996
import bisect

n = int(input())
a_list = list(map(int, input().split()))
a_list.sort()

med = a_list[-1] / 2
idx = bisect.bisect_left(a_list, med)

if (med - a_list[idx-1]) > (a_list[idx] - med):
    print('%d %d' % (a_list[-1], a_list[idx]))
else:
    print('%d %d' % (a_list[-1], a_list[idx-1]))


Measured memory_bytes: 14428
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int sum = 0;
        List<Integer> A = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            int a = sc.nextInt();
            A.add(a);
            sum += a;
        }

        int num = 0;
        for (int i = 0; i < N; i++) {
            if (sum <= A.get(i)*4*M) {
                num++;
            }
        }

        System.out.println(num >= M ? "Yes" : "No");
    }
}



Measured memory_bytes: 21844
def BinarySearch(A,key):
    left = 0
    right = len(A) 
    while left < right:
        mid = (left + right)//2
        if A[mid] == key:
            return True
        elif key < A[mid]:
            right = mid
        else:
            left = mid + 1
    return False


n = int(input())
S = list(map(int,input().split()))

q = int(input())
T = list(map(int,input().split()))

count = 0
for key in T:
    if BinarySearch(S,key):
        count += 1
print(count)


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vi lnum;
typedef long double ld;

#define ALL(V) V.begin(), V.end()
#define SZ(V) (ll)V.size()
#define pb push_back
#define mp make_pair
#define pi 3.14159265358979
#define fopen freopen("input.txt", "r", stdin); freopen("output.txt","w", stdout)
#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define FORR(i, b, a) for(ll i = (b) - 1; i >= (a); --i)
#define REP(i, N) FOR(i, 0, N)
#define REPR(i, N) RFOR(i, N, 0)
#define FILL(A,value) memset(A,value,sizeof(A))
#define code first
#define index second

const ll mod = 998244353;
//const ll mod = 2 * (1000 * 1000 * 1000 + 7);
const ll MOD91 = 1e9+9;
const ll MOD12 = 1e12+39LL;
const ll MOD15 = 1e15+37LL;
const ll INF = 1000 * 1000 * 1000;
const ll LINF = 1000LL*1000*1000*1000 * 1000 * 1000;
const ll base = 1e9;
const ll MAX = 2e5;
const double EPS = 1e-10;
const double EPS2 = 1e-9;
int fact[300001];
int mult(int a , int b)
{
	return ((ll)a * b) % mod;
}
int add(int a , int b)
{
	return a + b >= mod ? a + b - mod : a + b;
}
ll N , A , B , K , X , Y;
ll gcdExtended(ll a, ll b, ll *x, ll *y);

// Function to find modulo inverse of a
ll modInverse(ll a, ll m)
{
    ll x, y;
    ll g = gcdExtended(a, m, &x, &y);
    if (g != 1)
        cout << "Inverse doesn't exist";
    else
    {
        // m is added to handle negative x
        ll res = (x%m + m) % m;
        return res;
    }
}

// C function for extended Euclidean Algorithm
ll gcdExtended(ll a, ll b, ll *x, ll *y)
{
    // Base Case
    if (a == 0)
    {
        *x = 0, *y = 1;
        return b;
    }

    ll x1, y1; // To store results of recursive call
    ll gcd = gcdExtended(b%a, a, &x1, &y1);

    // Update x and y using results of recursive
    // call
    *x = y1 - (b/a) * x1;
    *y = x1;

    return gcd;
}
int C(int n , int k)
{
	return mult(fact[n] , mult(modInverse(fact[k] , mod), modInverse(fact[n - k] , mod) ) );
}
int main()
{
	fact[0] = 1;
	for(int i = 1; i <= 300000; i++)
	{
		fact[i] = mult(fact[i - 1] ,  i);
	}
	cin >> N >> A >> B >> K;
	int ans = 0;
	for(int i = 0; i <= N; i++)
	{
		ll lft = K - A * i;
		if(lft >= 0 && !(lft % B))
		{
			int j = lft / B;
			if(j <= N)
				ans = add(ans , mult(C(N , i) , C(N , j)));
		}
	}



	cout << ans;
	return 0;
}





Measured memory_bytes: 1408
n,x,m=map(int,input().split())

def f(ai,m):
    return (ai*ai)%m

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=f(ai,m)
#        ai=(ai*ai)%m
        asum+=ai
    print(asum)   
else:
    aa=[]
    ai,icnt,asum=x,0,0
#    icnt=0
#    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=f(ai,m)
#        ai=(ai*ai)%m
        icnt+=1
    ai0,icnt0,asum0=x,0,0
#    icnt0=0
#    asum0=0
    if ai!=x:
        for i in range(icnt+1):
            asum0+=ai0
            ai0=f(ai0,m)
#            ai0=(ai0*ai0)%m
            icnt0+=1
            if ai0==ai:
                break
    icntk=icnt-icnt0
#    print("1:",ai,asum,icnt,ai0,asum0,icnt0)
    n0=n-1-icnt0
    nk=n0//icntk
    nr=n0%icntk
    asumk=asum-asum0
    air,asumr=ai,0
#    asumr=0
    for i in range(nr):
        asumr+=air
        air=f(air,m)
#        air=(air*air)%m
    asumr+=air
       
    ans=asum0+asumk*nk+asumr    
    print(ans)       
        


Measured memory_bytes: 69220
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <list>

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;

#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()
#define rall(a) (a).rbegin(), (a).rend()

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

int main() {
    string s;
    cin >> s;
    string ans;
    bool isStart = false;
    int ss, g;
    rep(i, s.size()) {
        if (s[i] == 'A' && !isStart) {
            ss = i;
            isStart = true;
        }
        else if(s[i] == 'Z') g = i;
    }

    cout << g-ss+1 << endl;
}

Measured memory_bytes: 640
#include <iostream>

using namespace std;

int main()
{
    string s[3];
    int i;

    for (i = 0; i < 3; i++) {
        cin >> s[i];
    }

    if ((s[0] == s[1] && s[0] != s[2] && s[1] != s[2]) ||
        (s[0] != s[1] && s[0] == s[2] && s[1] != s[2]) ||
        (s[0] != s[1] && s[0] != s[2] && s[1] == s[2])) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
import math
import queue
import bisect
import heapq
import time
import itertools

mod = int(1e9+7)

def swap(a,b):
    return (b,a)

def my_round(a,dig=0):
    p = 10 ** dig
    return (a * p * 2 + 1) // 2 / p

def gcd(a,b): #最大公約数
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b): #最小公倍数
    return a/gcd(a,b)*b

def divisors(a): # 約数列挙
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def is_prime(a): #素数判定
    if a<2:
        return False
    elif a==2:
        return True
    elif a%2==0:
        return False
    sqrt_num = int(a**0.5)
    for i in range(3,sqrt_num+1,2):
        if a%i==0:
            return False
    return True

def prime_num(a): #素数列挙
    pn = [2]
    for i in range(3,int(a**0.5),2):
        prime = True
        for j in pn:
            if i%j==0:
                prime = False
                break
        if prime:
            pn.append(i)
    return pn

def prime_fact(a): #素因数分解
    sqrt = math.sqrt(a)
    res = []
    i = 2
    if is_prime(a):
        res.append(a)
    else:
        while a!=1:
            while a%i==0:
                res.append(i)
                a //= i
            i += 1
    return res

def main():
    x = int(input())
    if x == 7 or x == 5 or x == 3:
        print('YES')
    else:
        print('NO')
    return

if __name__=='__main__':
    main()


Measured memory_bytes: 39788
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define  For(i,a,b) for(int i=a,i##E=b;i<=i##E;++i)
#define rFor(i,a,b) for(int i=a,i##E=b;i>=i##E;--i)
using namespace std;
typedef long long LL;
const int N=2010;
template<typename T>inline T chkmax(T A,T B){return A>B?A:B;}
template<typename T>inline T chkmin(T A,T B){return A<B?A:B;}
template<typename T>inline void read(T &x)
{
	x=0;int _f(0);char ch=getchar();
	while(!isdigit(ch))_f|=(ch=='-'),ch=getchar();
	while( isdigit(ch))x=x*10+ch-'0',ch=getchar();
	x=_f?-x:x;
}
inline void file()
{
#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
}
int H,W,ans;
char str[N][N];
int s[2][N][N],fa[N],sz[N];
struct node
{
	int x,h;
	node(){}
	node(int x,int h):x(x),h(h){}
}a[N];
bool operator<(node A,node B){return A.h>B.h;}
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void merge(int x,int y)
{

	fa[x=find(x)]=(y=find(y));
	sz[y]+=sz[x];
}
int main()
{
	read(H),read(W);
	For(i,1,H)scanf("%s",str[i]+1);
	ans=chkmax(H,W);
	rFor(i,W,1)
	{
		For(j,1,H-1)
		if(str[j][i]==str[j+1][i])
			s[0][i][j]=s[0][i+1][j]+1;
		else
			s[1][i][j]=s[1][i+1][j]+1;
	}
	For(i,1,W)
	{
		int tot=0;
		For(j,1,H-1)
		{
			a[++tot]=node(j,chkmax(s[0][i][j],s[1][i][j]));
		}
		For(j,1,H)fa[j]=j,sz[j]=1;
		sort(a+1,a+tot+1);
		For(i,1,tot)
		{
			merge(a[i].x,a[i].x+1);
			ans=chkmax(ans,a[i].h*sz[find(a[i].x+1)]);
		}
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 35712
N, K = map(int, input().split())
d = []
A = []
for _ in range(K):
    d.append(int(input()))
    A.append(list(map(int, input().split())))

cnt = {}
for i, Ai in enumerate(A):
    for j, Aij in enumerate(Ai):
        key = str(Aij)
        cnt.setdefault(key, 0)
        cnt[key] += 1

ans = 0
for i in range(1, N + 1):
    key = str(i)
    cnt.setdefault(key, 0)
    ans += int(cnt[key] == 0)

print(ans)

Measured memory_bytes: 9156
# -*- coding: utf-8 -*-
def main():
    N = int(input())
    count = 0
    for i in range(N):
        L = []
        L = [int(i+1) for c in str(i+1)]
        if len(L)%2 != 0:
            count += 1
    print(count)
if __name__ == '__main__':
    main()

Measured memory_bytes: 2940
package main
import (
	"fmt"
	"os"
	"bufio"
	"strconv"
	"strings"
)
 
func main() {
	stdin := bufio.NewScanner(os.Stdin)
	stdin.Scan()
	text := stdin.Text()
	s := strings.Split(text, " ")
	a, _ := strconv.Atoi(s[0])
	b, _ := strconv.Atoi(s[1])
	if a > 9 || b > 9 {
		fmt.Println(-1)
	} else {
		fmt.Println(a * b)
	}
}

Measured memory_bytes: 640
#include <iostream>

using namespace std;

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

    auto operations = 0;
    for (auto i = 0; i < n; i += 1) {
        int num;
        cin >> num;

        while (num > 0 && (num & 1) == 0) {
            operations += 1;
            num >>= 1;
        }
    }

    cout << operations << "\n";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<ll,ll> Pi;
const int INF=(ll)(1LL<<31)-1;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
//int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

ll n,a,b;

int main(){
	cin>>n>>a>>b;
	if(b<a||(n==1&&a!=b))cout<<0<<endl;
	else{
		cout<<(b-a)*(n-2)+1;
	}
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T = int> void print(vector<T> v){for(auto a:v)cout<<a<<" ";cout<<endl;}

/*
銀貨の数だけ新たなグラフを作る
*/

ll n,m,s,d[51][2501],gc[51],gt[51];
vector<ll> v[51],c[51],t[51];


int main(void){
	cin>>n>>m>>s;
	rep(i,m){
		ll x,y,a,b;
		cin>>x>>y>>a>>b;
		v[x].push_back(y);
		v[y].push_back(x);
		c[x].push_back(a);  // 消費コイン
		c[y].push_back(a);  //
		t[x].push_back(b);  // 消費時間
		t[y].push_back(b);  //
	}
	reg(i,1,n)cin>>gc[i]>>gt[i];
	rep(i,51)rep(j,2501)d[i][j]=1e15;
	s = min(s,2500LL);
	d[1][s]=0;
	priority_queue<pair<ll,pair<ll,ll>>, vector<pair<ll,pair<ll,ll>>>, greater<pair<ll,pair<ll,ll>>> > q;
	q.push({0,{1,s}});
	while(!q.empty()){
		auto x = q.top();q.pop();
		auto y = x.second;
		ll cur_t = x.first, p = y.first, cur_c = y.second;
		if(d[p][min(2500LL,cur_c+gc[p])] > d[p][cur_c] + gt[p]){  // コイン補充
			d[p][min(2500LL,cur_c+gc[p])] = d[p][cur_c] + gt[p];
			q.push({d[p][min(2500LL,cur_c+gc[p])], {p,min(2500LL,cur_c+gc[p])}});
		}
		rep(i,v[p].size()){  // 移動
			ll r = v[p][i], dt = t[p][i], dc = c[p][i];
			if(cur_c - dc>=0 && d[r][cur_c - dc] > d[p][cur_c] + dt){
				d[r][cur_c - dc] = d[p][cur_c] + dt;
				q.push({d[r][cur_c - dc], {r,cur_c - dc}});
			}
		}
	}
	reg(i,2,n){
		ll ans=1e18;
		rep(j,2501){
			ans=min(ans,d[i][j]);
		}
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 7292
import java.util.Scanner

import scala.collection.mutable.ArrayBuffer

object Main {
  def main(args: Array[String]): Unit = println(solve(new Scanner(System.in)))

  def solve(in: String): String = solve(new Scanner(in))

  def p(a: Seq[Seq[Boolean]]) = {
    println("---")
    println(a.map(_.map(a => if (a) "o" else "x").mkString("")).mkString("\n"))
  }

  def solve(sc: Scanner): String = {
    val H = sc.nextInt
    val W = sc.nextInt
    val a = ArrayBuffer.fill(H)(ArrayBuffer.fill(W)(sc.nextInt % 2 != 0))

    val result = new ArrayBuffer[String]()
//    p(a)
    for (y <- 0 until H; x <- 0 until W) {
      if (a(y)(x)) {
        if (x < W - 1) {
          a(y)(x) = false
          a(y)(x + 1) = !a(y)(x + 1)
          result += "%d %d %d %d".format(y + 1, x + 1, y + 1, x + 2)
//          p(a)
        } else if (y < H - 1) {
          a(y)(x) = false
          a(y + 1)(x) = !a(y + 1)(x)
          result += "%d %d %d %d".format(y + 1, x + 1, y + 2, x + 1)
//          p(a)
        }
      }
    }

    result.length.toString + "\n" + result.mkString("\n")
  }
}


Measured memory_bytes: 135024
#include <bits/stdc++.h>
#define pb push_back
#define fs first
#define sc second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

int main() {
    ll i, a[7], ans;
    for(i=0; i<7; i++) scanf("%lld", &a[i]);
    ans=a[1]+2*(a[0]/2+a[3]/2+a[4]/2);
    if(a[0]&&a[3]&&a[4]) {
        a[0]--; a[3]--; a[4]--;
        ans=max(ans, 3+a[1]+2*(a[0]/2+a[3]/2+a[4]/2));
    }
    printf("%lld\n", ans);
    return 0;
}

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

long long c[51][51], ans;
int n, a, b;
vector<double> v;
double avg;
int main() {
	scanf("%d%d%d",&n,&a,&b);
	c[0][0] = 1;
	for(int i = 1; i <= n; i++) {
		c[i][0] = c[i][i] = 1;
		for(int j = 1; j < i; j++) c[i][j] = c[i-1][j-1]+c[i-1][j];
	}
	v.resize(n);
	for(int i = 0; i < n; i++) scanf("%lf",&v[i]);
	sort(v.begin(), v.end(), greater<double>());
	for(int i = 0; i < a; i++) avg += v[i];
	avg /= a;
	int x = 0, y = 0;
	for(int i = 0; i < n; i++) if(v[i] == v[a-1]) {
		x++;
		if(i < a) y++;
	}
	if(v[0] != v[a-1]) ans = c[x][y];
	else {
		for(int k = a; k <= min(x, b); k++) ans += c[x][k];
	}
	printf("%lf\n%lld\n", avg, ans);
}


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

ll p(ll a , ll b)
{
    ll ans = 1 ;
    while(b)
    {
        if(b%2)
        {
            ans *= a ;
        }
        a *= a ;
        b /= 2 ;
    }
    return ans ;
}

int main()
{
    string s ;
    cin >> s ;
    ll ans = 0 ;
    for(int i = 0 ; s[i] != '\0' ; i++)
    {
         int x = (int)s[i] - 48 ;
         ans += x ;
         ans %= 9 ;
    }
    if(ans == 0)
    {
         cout << "Yes\n" ;
    }
    else
    {
         cout << "No\n" ;
    }
}


Measured memory_bytes: 3708
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <functional>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <string>
#define SIZE 20
#define BT 1<<16
#define MOD 1000000007

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

ll dp[BT],rt[SIZE];
ll nxt[BT],memo[SIZE][SIZE];
ll cnt[SIZE][BT];
ll nt[BT];
bool use[SIZE][SIZE];


int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;i++)
	{
		int x,y;
		scanf("%d %d",&x,&y);x--,y--;
		use[x][y]=true;
	}
	for(int i=0;i<n;i++)
	{
		for(int S=0;S<1<<n;S++)
		{
			cnt[i][S]=0;
			for(int j=0;j<n;j++)
			{
				if(use[i][j]&&(S>>j&1))
				{
					cnt[i][S]=(cnt[i][S]*2LL+1)%MOD;
				}
			}
		}
	}
	for(int S=0;S<1<<n;S++)
	{
		nt[S]=1;
		for(int i=0;i<n;i++)
		{
			if(S>>i&1)
			{
				for(int j=i+1;j<n;j++)
				{
					if(S>>j&1)
					{
						if(use[i][j]) nt[S]=nt[S]*2LL%MOD;
					}
				}
			}
		}
	}
	memset(dp,0,sizeof(dp));
	dp[0]=1;
	ll ret=0;
	for(int i=0;i<n;i++)
	{
		memset(nxt,0,sizeof(nxt));
		for(int S=0;S<1<<n;S++)
		{
			if(dp[S]==0) continue;
			int T=(1<<n)-S-1;
			for(int K=T;K>0;K=T&(K-1))
			{
				int zan=T-K;
				ll way=dp[S];
				for(int j=0;j<n;j++)
				{
					if(zan>>j&1)
					{
						way=way*cnt[j][K]%MOD;
					}
					else if(K>>j&1)
					{
						way=way*(cnt[j][zan]+1)%MOD;
					}
				}
				nxt[S+K]+=way;
				if(nxt[S+K]>=MOD) nxt[S+K]>=MOD;
				if((K>>0&1)&&(K>>1&1))
				{
					ret+=way*nt[zan]%MOD;
					if(ret>=MOD) ret-=MOD;
				}
			}
		}
		for(int S=0;S<1<<n;S++) dp[S]=nxt[S];
	}
	ll all=1;
	for(int i=0;i<m;i++) all=all*2LL%MOD;
	printf("%lld\n",(all-ret+MOD)%MOD);
	return 0;
}


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

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

//最後にどの桁を見たか
//現時点で何文字を残すと決めたか
//現時点で残すと決まった部分の文字列
bool dp[30010][4][1010];

int main() {

    int n; cin >> n;
    string s; cin >> s;

    dp[0][0][0] = true;

    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= 3; ++j) {
            for (int k = 0; k < 1000; ++k) {
                if (dp[i][j][k] == false) {
                    continue;
                }

                dp[i+1][j][k] = true; //文字を残さない場合（消す場合）

                if (j <= 2) {
                    dp[i+1][j+1][k * 10 + (s[i] - '0')] = true; //文字を残す場合
                }
            }
        }
    }

    int ans = 0;

    for (int i = 0; i < 1000; ++i) {
        if (dp[n][3][i] == true) {
            ++ans;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 118656
/*input
2 10 20
*/
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int,int>
#define pb push_back
#define f first
#define s second
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

signed main() {
	IOS;
	int r,d,x;
	cin>>r>>d>>x;
	for(int i=0;i<10;i++){
		int t = r * x - d ;
		cout << t << endl;
		x = t; 
	}
return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    int N;
    int time[100];
    int sum1, sum2;
    int i, j;
    int t;
    
    while (scanf("%d", &N) != EOF){
        for (i = 0; i < N; i++){
            scanf("%d", &time[i]);
        }
        for (i = 0; i < N; i++){
            for (j = 0; j < N - 1; j++){
                if (time[j] > time[j + 1]){
                    t = time[j];
                    time[j] = time[j + 1];
                    time[j + 1] = t;
                }
            }
        }

        sum1 = sum2 = 0;
        for (i = 0; i < N; i++){
//printf("[%d]", time[i]);
            sum1 += time[i];
            sum2 += sum1;
        }
        
        printf("%d\n", sum2);
    }
    return (0);
}

Measured memory_bytes: 600
import numpy as np


w, h, n = map(int, input().split())
m = np.zeros((h, w), int)
while n:
    x, y, a = map(int, input().split())
    m[y*(a>3):h*(a^3) or y, x*(a==2): w*~-a or x]=1
    n -= 1
print(w*h-m.sum())

Measured memory_bytes: 12508
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s;cin >> s;
	int g=0,p=0;
	rep(i,s.size()){
		if(s.at(i)=='g') g++;
		else p++;
	}
	cout << (g-p)/2 << endl;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#include<time.h>
#include<stdlib.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4")
#define pb push_back
#define mp make_pair
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll int
#define pll pair<ll,ll>
#define vll vector<ll,ll>
#define all(a) (a).begin(),(a).end()
#define ff first
#define ss second
#define sz(x) (ll)x.size()
#define hell 1000000007
#define repf(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>b;i--)
#define lbnd lower_bound
#define ubnd upper_bound
#define bs binary_search
#define gcd(a,b) __gcd((a),(b))
#define EPS 1e-12
#define lcm(a,b) ((a)*(b))/__gcd((a),(b))
#define sqrt sqrtl
#define cbrt cbrtl
using namespace std;
ll n,k;
int main()
{
  IOS
  cin>>n>>k;
  ll i;
  vector<ll> a;
  ll sum=0;
  for(i=1;i<=n;i++)
  {
    ll x;
    cin>>x;
    a.pb(x);
    sum+=x;
  }
 
    sort(all(a));
    ll cnt=0;
    for(i=0;i<n;i++)
      if(k>=a[i])
      {
        k-=a[i];
        cnt++;
      }
      else
      {
        cout<<i;
        return 0;
      }
      if(k==0)
        cout<<n;
      else
        cout<<n-1;
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <cstdint>
#include <cinttypes>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>

using namespace std;
static const long k10E7 = 1000000007;

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

    vector<long> dn(n);
    for(long& di : dn){
        cin >> di;
    }

    sort(dn.begin(), dn.end());

    long abc_last = dn[n/2-1];
    long arc_first = dn[n/2];

    cout << arc_first - abc_last << endl;

    return 0;
}



Measured memory_bytes: 1024
import * as fs from 'fs';

export class Reader {
    lines: string[];
    currentLine: number;

    constructor() {
        this.lines = fs.readFileSync("/dev/stdin", "utf8").trim().split("\n");
        this.currentLine = 0;
    }

    readLine(): string {
        return this.lines[this.currentLine++];
    }

    readInt(): number {
        return Number(this.readLine());
    }

    readInts(): number[] {
        return this.readLine().split(" ").map(Number);
    }
}

function div(a: number, b: number): number {
	return Math.floor(a/b);
}


function solve(): number[] {
	let reader = new Reader();
	let answer = 0;
	let K = reader.readInt();
	let A = reader.readInts();
	let L: number[] = new Array(K+1).fill(0),
		R: number[] = new Array(K+1).fill(0);
	L[K] = 2;
	R[K] = 2;
	for(let i=K-1; i>=0; i--) {
		let X = Math.ceil(L[i+1]/A[i])*A[i],
			Y = Math.floor(R[i+1]/A[i])*A[i];
		if (Y < X)
			return [-1];
		L[i] = X;
		R[i] = Y+A[i]-1;
	}
	return [L[0], R[0]];
}

console.log(...solve());


Measured memory_bytes: 44044
#include <stdio.h>

int n;
char t[11];
void f(int k,int c){
	if(k==n){
		puts(t);
		return;
	}
	for(int i=0;i<c;i++){
		t[k]='a'+i;
		f(k+1,c);
	}
	t[k]='a'+c;
	f(k+1,c+1);
}

int main(){
	scanf("%lld",&n);
	f(0,0);
}

Measured memory_bytes: 1408
#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#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;
using P = pair<int, int>;

ll f(ll n) {
  return n % 2 == 0 ? n / 2 : 3 * n + 1;
}

int main(void) {
  ll s;
  cin >> s;

  map<ll, int> a;
  a[s]++;
  ll ans = 1;
  ll old = s;
  while (true) {
    ll next = f(old);
    a[next]++;
    ans++;
    if (a[next] == 2) {
      break;
    }
    old = next;
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin>>s;
int counto=0,countz=0;
for(int i=0;i<s.size();i++)
{
    if(s[i]=='1')
    counto++;
    else
    countz++;
}
if(countz>counto)
{
    cout<<2*counto;
}
else
cout<<2*countz;


}


Measured memory_bytes: 512
import java.util.Scanner;

 class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
//		int n = sc.nextInt();
		String num = sc.nextInt()+"";
		String ans = "";
		for (int i = 0; i < num.length(); i++)
			ans = ans + (num.charAt(i) == '1' ? 9 : 1);
		System.out.println(ans);
	}
}

Measured memory_bytes: 23252