akhauriyash/Code-Regression huggingface dataset:
#include<iostream>

using namespace std;
int main()
{
    string s;
    cin>>s;
    int i=0,s1=0,s2=0;
    while(s[i]!='\0'){
        if(s[i]=='A'){
            s1++;
        }
        if(s[i]=='B'){
            s2++;
        }
        i++;
    }
    if(s1>0 && s2>0){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }


    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
long gcd(long a,long b){
  long x = max(a,b);
  long y = min(a,b);
  while(x%y!=0){
    long z = x%y;
    x = y;
    y = z;
  }
  return y;
}
int main() {
  int n;
  long x;
  cin >> n;
  cin >> x;
  long* d = new long[100000];
  for(int i=0;i<n;i++){
    int in;
    cin >> in;
    d[i] = abs(x - in);
  }
  if(n==1){
    cout << d[0] << endl;
    return 0;
  }
  long ans = gcd(d[0],d[1]);
  for(int i=2;i<n;i++){
    ans = gcd(ans,d[i]);
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
int main()
{
    int a[105], b=0, n, i, m,d=0;
    float c;
    scanf("%d%d", &n, &m);
    for (i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        b += a[i];
    }
    c = 1.0 / (4.0 * m) * b;
    for (i = 0; i < n; i++)
    {
        if (a[i] >= c)
        {
            d++;
        }
    }
    if (d >= m)
    {
        printf("Yes");
    }
    else
    {
        printf("No");
    }
    return 0;
}


Measured memory_bytes: 128
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>

using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;

const int L=1e5+1;
vector<LL> ps;
vector<LL> ps2;

const LL up=1e10;
int main() {
	vector<bool> comp(L);
	for(LL i=2;i<L;i++){
		if(comp[i])continue;
		ps.push_back(i);
		ps2.push_back(i*i);
		for(LL j=i*i;j<L;j+=i){
			comp[j]=true;
		}
	}
	////cerr/g << ps.size() << endl;
	int N;
	cin >> N;
	map<P,int> r;
	bool cb=false;

	LL ret=0;
	for(int i=0;i<N;i++){
		LL s;
		cin >> s;
		//LL org=s;
		LL s0=pow(s,1.0/3)+0.5;
		if(s0*s0*s0==s){
			//cerr/g << "cb" << org << endl;
			cb=true;
			continue;
		}

		auto j=lower_bound(ps.begin(),ps.end(),s)-ps.begin();
		if(j<ps.size()&&ps[j]==s){
			//cerr/g << ps[j] << ", " << ps[j] << ", " << ps2[j] << endl;
			r[P(ps[j],ps2[j])]++;
			continue;
		}
		j=lower_bound(ps2.begin(),ps2.end(),s)-ps2.begin();
		if(j<ps2.size()&&ps2[j]==s){
			//cerr/g << ps2[j] << ", " << ps2[j] << ", " << ps[j] << endl;
			r[P(ps2[j],ps[j])]++;
			continue;
		}

		LL m0=1;
		LL m1=1;
		LL m2=1;
		bool over=false;
		for(int i=0;i<ps.size()&&s>1;i++){
			LL p3=ps[i]*ps2[i];
			if(p3>up||(m0*p3>up&&m2*p3>up)){
				over=true;
				break;
			}
			int c=0;
			while(s%ps[i]==0){
				s/=ps[i];
				m0*=ps[i];
				c++;
			}
			if(c==0)continue;
			c%=3;
			if(c==1){
				m1*=ps[i];
				m2*=ps2[i];
			}
			else if(c==2){
				m1*=ps2[i];
				m2*=ps[i];
			}
			if(m2>up){
				over=true;
				break;
			}
			auto j=lower_bound(ps.begin(),ps.end(),s)-ps.begin();
			if(j<ps.size()&&ps[j]==s){
				s/=ps[j];
				m0*=ps[j];
				m1*=ps[j];
				m2*=ps2[j];
				if(m2>up){
					over=true;
					break;
				}
			}
			j=lower_bound(ps2.begin(),ps2.end(),s)-ps2.begin();
			if(j<ps2.size()&&ps2[j]==s){
				s/=ps2[j];
				m0*=ps2[j];
				m1*=ps2[j];
				m2*=ps[j];
				if(m2>up){
					over=true;
					break;
				}
			}
		}
		if(over){
			//cerr/g << "over " << org << endl;
			ret++;
			continue;
		}
		r[P(m1,m2)]++;
		//cerr/g << org << ", " << m1 << ", " << m2 << endl;
	}
	if(cb){
		ret++;
	}
	set<P> done;
	for(auto p:r){
		if(done.count(p.first))continue;
		P k=P(p.first.second,p.first.first);
		//cerr/g << "p " << p.first.first << ", " << p.first.second << endl;
		//cerr/g << "k " << k.first << ", " << k.second << endl;
		auto it=r.find(k);
		if(it !=r.end()){
			ret+=max(p.second,it->second);
			done.insert(k);
			//cerr/g << k.first << ", " << k.second << endl;
		}
		else{
			ret+=p.second;
		}
	}
	cout << ret << endl;

	return 0;
}



Measured memory_bytes: 5760
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pi> vpi;
typedef vector<vi> vvi;
const int inf = 0x3f3f3f3f;
const ll linf = 123456789012345678;
const ll mod = 1000000007;
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl
#define sz(x) ((int)(x).size())


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

    ll n;
    cin >> n;

    if(n%2 == 1){
        cout << 0 << endl;
        return 0;
    }

    ll ans = 0;
    for(ll d = 10; d <= 1000000000000000000; d*=5)
        ans += n/d;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
 
int main(void){
	
	int a,b,c,d,e;
	
	scanf("%d",&a);
	
	b = a / 1000;
	c = (a / 100) % 10;
	d = (a / 10) % 10;
	e = a % 10;
	
	if((b==c && c==d)||(c==d && d==e)){
	printf("Yes\n");
	} else {
	printf("No\n");
	}
	return 0;
}

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

int main() {
    
    int A, B;
    cin >> A >> B;
    
    for(int i = 0; i < 1250; i++){
        if((i/10) == B && (i*8)/100 == A){
            cout << i << endl;
            return 0;
        }
    }
    
    cout << -1 << endl;
    
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define VI  vector<ll>
#define lf(i,a,b) for(ll i=a;i<=b;i++)
const ll mod=1e9+7;
double pi = 2 * acos(0.0);
#define FASTIO ios_base::sync_with_stdio(false);cout.tie(NULL);cout.tie(NULL);
ll max(ll a, ll b) { return (a > b) ? a : b; }
ll min(ll a, ll b) { return (a < b) ? a : b; }
bool cmp(pair<ll,ll> a,pair<ll,ll> b)
{
    return (a.first)<(b.first);
}
ll power(ll a,ll b)
{
        ll p=1;
        for(ll i=1;i<=b;i++)
        p*=a;

        return p;
}
ll gcd(ll a, ll b){
    if (a == 0)
        return b;
    return gcd(b % a, a);
 }
void bfs(map<ll,vector<ll> > &g,ll src,vector<ll> &c)
{
    queue<ll> q;
    map<ll,ll> p;
    q.push(src);
    p[src]=src;
    c[src]=1;
    while(!q.empty())
    {
        ll u=q.front();
        q.pop();
        ll i=1;
        for(auto v:g[u])
        {
            if(c[v]==-1)
            {
                q.push(v);
                p[v]=u;
                if(i==c[u]||i==c[p[u]])
                    i++;
                if(i==c[u]||i==c[p[u]])
                    i++;
                c[v]=i;
                i++;
            }
        }
    }
}
ll dp[105][100005],a[105][2];
ll fun(ll n, ll w)
{
    if(n==0||w==0) return 0;
    if(dp[n][w]!=-1) return dp[n][w];
    if(a[n-1][0]<=w)
        dp[n][w]=max(a[n-1][1]+fun(n-1,w-a[n-1][0]),fun(n-1,w));
    else dp[n][w]=fun(n-1,w);
    return dp[n][w];
}
int main()
{
    FASTIO;
    ll i,j,n,w;
    cin>>n>>w;
    memset(dp,-1,sizeof(dp));
    for(i=0;i<n;i++) cin>>a[i][0]>>a[i][1];
    cout<<fun(n,w)<<endl;
    return 0;
}


Measured memory_bytes: 82304
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i) = 0; (i) < (n); (i)++)
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 main() {
    int m;
    cin >> m;
    ll num_digit = 0, sum_digit = 0;

    rep(i,m){
        ll d, c;
        cin >> d >> c;
        num_digit += c;
        sum_digit += d * c;
    }
    num_digit--;
    sum_digit--;
    ll ans = num_digit;
    ans += (sum_digit / 9LL);
    cout << ans << endl;
}


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

class Program
{
    static void Main(string[] args)
    {
        int[] input = MyUtil.ReadIntArray();

        int max = input[1] < input[2] ? input[1] : input[2];
        int min = 0;

        if (input[1] > input[2])
        {
            int dif = input[0] - input[1];
            int r = input[2] - dif;
            if (r < 0)
            {
                r = 0;
            }
            min = r;
        }
        else
        {
            int dif = input[0] - input[2];
            int r = input[1] - dif ;
            if (r < 0)
            {
                r = 0;
            }
            min = r;
        }

        Console.WriteLine(max + " " + min);

        Console.ReadKey();
    }
}

static class MyUtil
{
    public static int[] ReadIntArray()
    {
        return Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
    }

    /// <summary>
    /// <see cref="IEnumerable{T}"/>の各要素を並べてコンソールに出力します。各要素の間には半角スペースが一つ入ります。
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="ts"></param>
    public static void WriteToConsole<T>(this IEnumerable<T> ts)
    {
        StringBuilder stringBuilder = new StringBuilder();
        foreach (T t in ts)
        {
            stringBuilder.Append(t.ToString());
            stringBuilder.Append(" ");
        }
        stringBuilder.Remove(stringBuilder.Length - 1, 1);
        Console.WriteLine(stringBuilder.ToString());
    }
}


Measured memory_bytes: 13396
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{   
    int A,B,C,D,E,F;
    cin>>A>>B>>C>>D>>E>>F;
    
    A*=100; B*=100;

    int W=-1,S;
    for(int a=0;a<=F;a+=A) 
    for(int b=0;a+b<=F;b+=B) 
    for(int c=0;a+b+c<=F;c+=C)
    for(int d=0;a+b+c+d<=F;d+=D){
        int w=a+b;
        int s=c+d;
        if(w==0) continue;
        if(s>w/100*E) continue;
        if(W==-1 or s*(W+S)>S*(w+s)){
            W=w; S=s;
        }
    }
    cout<<W+S<<' '<<S<<endl;

}


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

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

  if (a%3 == 0 || b%3 == 0 || (a+b)%3 == 0) {
    cout << "Possible" << endl;
  } else {
    cout << "Impossible" << endl;
  }
} 

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<math.h>
typedef long long ll;
using namespace std;
int main(){
	
	ll n,i;
	
	cin>>n;
	
	ll ar[104];
	
	for(i=1;i<=n;i++)
	cin>>ar[i];
	
	sort(ar+1,ar+1+n);
	
	
	cout << ar[n] - ar[1] << endl;
	
	return 0;
	
}

Measured memory_bytes: 256
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>
#include <chrono>
#include <cstring>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "\n" : " ");
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

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

int dp[5010][5010];

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	auto start = chrono::system_clock::now();
	auto split = chrono::system_clock::now();

	int N;
	cin >> N;
	string s;
	cin >> s;

	auto check = [&](int cut) {
		int res = 0;
		memset(dp, 0, sizeof(dp));
		for (int i = 0; i < cut; i++) {
			for (int j = cut; j < N; j++) {
				if (s[i] == s[j]) dp[i + 1][j + 1] = dp[i][j] + 1;
				chmax(res, dp[i + 1][j + 1]);
			}
		}
		return res;
	};

	// 3分探索
	int lb = 0, ub = N, ans = 0;
	while (chrono::duration_cast<chrono::milliseconds>(split - start).count() < 1000) {

		int t1 = (2.5 * lb + ub) / 3.5;
		int t2 = (lb + 2.5 * ub) / 3.5;

		int c1 = check(t1);
		int c2 = check(t2);
		if (c1 < c2) lb = t1;
		else ub = t2;

		chmax(ans, max(c1, c2));
		DMP(t1, t2);
		split = chrono::system_clock::now();
	}

	DMP(ub, lb);
	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 98432
#include <iostream>
using namespace std;
int main(void){
    int x = -1;
    int cnt = 1;
    while (true){
        cin >> x;
        if (x == 0){
            break;
        }
        cout << "Case " << cnt <<": " << x << endl;
        cnt++;
    }
    return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define per1(i,n) for(int i=n;i>0;i--)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    int A[101][2];
    rep(i,n) cin>>A[i][0]>>A[i][1];
    int z=0;
    rep(i,n-2) if(A[i][0]==A[i][1]&&A[i+1][0]==A[i+1][1]&&A[i+2][0]==A[i+2][1]) z=1;
    if(z) cout<<"Yes";
    else cout<<"No";
}

Measured memory_bytes: 3608
n = int(input())
A = list(map(int,input().split()))
B =[]
Br =[]
Bl =[]
for i in range(n):
    if i%2==0:
        Br.append(A[i])
    else:
        Bl.append(A[i])
        
if n%2==0:
    print(*(Bl[::-1]+Br))
else:
    print(*(Br[::-1]+Bl))

Measured memory_bytes: 26020
#include <bits/stdc++.h>
using namespace std;
#define fst first
#define snd second
#define mp make_pair
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()

template <typename T1, typename T2>
bool umin(T1 &x, const T2 &y){
	return (x>y ? (x=y,true):false);
}
template <typename T1, typename T2>
bool umax(T1 &x, const T2 &y){
	return (x<y ? (x=y,true):false);
}

template <typename T>
void read(T& x){
	char ch;
	T p=1;x=0;
	do{
		ch=getchar();
	}while(ch<=' ');
	if(ch=='-')p=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    x*=p;
}

void read(string& x){
	char ch;
	do{
		ch=getchar();
	}while(ch<=' ');
    while(ch>' ')x+=ch,ch=getchar();
}

void read(char& x){
	do{
		x=getchar();
	}while(x<=' ');
}
template<typename T, typename... R>
void read(T& x, R&... y) { read(x); read(y...); }

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int N=(int)1e6+3;
const int INF=(int)1e9+17;
const ll mod=(ll)1e9+7;
const ll LLINF=(ll)1e18+17;
const ld pi=(ld)acos(-1.0);
int n,m,a[N],b[N];

int main(){
	read(n);
	rep(i,0,n){
		read(a[i]);
		b[i]=a[i];
	}
	int mid=n/2-1;
	sort(b,b+n);
    rep(i,0,n){
    	if(b[mid]>=a[i])printf("%d\n",b[mid+1]);
		else printf("%d\n",b[mid]);
	}
	return 0;
}

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



signed main(){
    int n;
    cin >> n;
    int l[n];
    for(int i=0;i<n;i++)cin >> l[i];
    sort(l,l+n);
    int t=0;
    for(int i=0;i<n-1;i++)t+=l[i];
    if(t>l[n-1])cout <<"Yes";
    else cout << "No";
    return 0;
}

Measured memory_bytes: 764
N = int(input())

mem = dict()
for _ in range(N):
    s = ''.join(sorted(input()))
    if s in mem.keys():
        mem[s] += 1
    else:
        mem[s] = 1

ans = 0
for i in mem.values():
    ans += i * (i-1) // 2
print(ans)


Measured memory_bytes: 17852
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long,long long>
using namespace std;

int n,m,pos,num;
string ans;
bool ok[4];

int main()
{

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

    cin >> n >> m;
    ans.resize( n );

    for(int i=0; i<m; i++){
        cin >> pos >> num;
        pos--;
        if( !ok[pos] ) ok[pos] = true , ans[pos] = num+'0';
        if( ans[pos]-'0'!=num ){
            cout << -1;
            return 0;
        }
    }

    if( ok[0] && n>1 && ans[0]=='0' ){
        cout << -1;
        return 0;
    }
    if( !ok[0] && n>1 ) ans[0] = '1';
    if( !ok[0] && n==1 ) ans[0] = '0';
    for(int i=1; i<n; i++) if( !ok[i] ) ans[i] = '0';
    cout << ans;

    return 0;
}


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

 typedef struct node{
  int key;
  struct node *next , *prev;
} Node;

Node *nil;

Node* search(int key){
  Node *cur = nil->next;
  while(cur != nil &&  cur->key != key) cur= cur->next;
  return cur;
}

void init() {
  nil = (Node *)malloc(sizeof(Node));
  nil->next=nil;
  nil->prev=nil;
}

void print() {
  Node *cur = nil->next;
  int count = 0;
  while(1) {
    if(cur == nil ) break;
    if(count++ > 0) printf(" ");
    printf("%d",cur->key);
    cur = cur->next;
  }
  printf("\n");
}

void deleteNode(Node *t) {
  if(t == nil ) return;
  t->prev->next = t->next;
  t->next->prev = t->prev;
  free(t);
}

void deleteFirst() {
  deleteNode(nil->next);
}

void deleteLast() {
  deleteNode(nil->prev);
}
void deleteKey(int key) {
  deleteNode(search(key));
}

void insert(int key) {
  Node *x = (Node *)malloc(sizeof(Node));
  x->key = key;

  x->next = nil->next;
  nil->next->prev = x;
  nil->next = x;
  x->prev =nil;
}

int main() {
  int key,n,i,size=0;
  char com[20];
  int np = 0, nd=0;

  scanf("%d",&n);
  init();
  for(i = 0;i<n;i++) {
  scanf("%s%d",com , &key);
  if(com[0] == 'i') {
    insert(key);
    np++;
    size++;
  }
  else if (com[0] == 'd') {
    if(strlen(com) > 6) {
      if(com[6] == 'F') deleteFirst();
      else if(com[6] == 'L') deleteLast();
    } else {
      deleteKey(key); nd++;
    }
    size--;
  }
}
print();

return 0;
}

Measured memory_bytes: 31660
a,b,c,d = map(int,input().split())
import math
rad = math.fabs((c/12 - d/60 + d/720)*360)
rad = min(rad,360-rad)/180
cosine = math.cos(rad*math.pi)
print((a**2+b**2 - 2*a*b*cosine)**0.5)

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

int main(){
    int n,k,q; 
    cin>>n>>k>>q;
    vector<int> a(q);
    for(int i=0;i<q;i++){
        cin>>a[i];
        a[i]--;
    } 
    vector<int> p(n,k-q);
    for(int i=0;i<q;i++){
        p[a[i]]++;
    }
    for(int i=0;i<n;i++){
        if(p[i]<=0) cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }

}

Measured memory_bytes: 1408
def convolution(a, b, MOD=10**9+7):
    def butterfly(arr):
        n = len(arr)
        h = (n - 1).bit_length()
        sum_e = (911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601,
                 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 0, 0, 0, 0, 0, 0, 0, 0, 0)
        for ph in range(1, h + 1):
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            now = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = arr[i + offset]
                    r = arr[i + offset + p] * now
                    arr[i + offset] = (l + r) % MOD
                    arr[i + offset + p] = (l - r) % MOD
                now *= sum_e[(~s & -~s).bit_length() - 1]
                now %= MOD


    def butterfly_inv(arr):
        n = len(arr)
        h = (n - 1).bit_length()
        sum_ie = (86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543,
                  109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 0, 0, 0, 0, 0, 0, 0, 0, 0)
        for ph in range(1, h + 1)[::-1]:
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            inow = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = arr[i + offset]
                    r = arr[i + offset + p]
                    arr[i + offset] = (l + r) % MOD
                    arr[i + offset + p] = (MOD + l - r) * inow % MOD
                inow *= sum_ie[(~s & -~s).bit_length() - 1]
                inow %= MOD


    n = len(a)
    m = len(b)
    if not n or not m: return []
    if min(n, m) <= 50:
        if n < m:
            n, m = m, n
            a, b = b, a
        res = [0] * (n + m - 1)
        for i in range(n):
            for j in range(m):
                res[i + j] += a[i] * b[j]
                res[i + j] %= MOD
        return res
    z = 1 << (n + m - 2).bit_length()
    a += [0] * (z - n)
    b += [0] * (z - m)
    butterfly(a)
    butterfly(b)
    for i in range(z):
        a[i] *= b[i]
        a[i] %= MOD
    butterfly_inv(a)
    a = a[:n + m - 1]
    iz = pow(z, MOD - 2, MOD)
    for i in range(n + m - 1):
        a[i] *= iz
        a[i] %= MOD
    return a


def atcoder_practice2_f():
    import sys
    input = sys.stdin.buffer.readline

    N, M = map(int, input().split())
    A = [int(x) for x in input().split()]
    B = [int(x) for x in input().split()]

    print(*convolution(A, B, 998244353))


if __name__ == "__main__":
    atcoder_practice2_f()


Measured memory_bytes: 196616
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vlli vector<ll>
#define vi vector<int>
#define vs vector<string>
#define vplli vector< pair< ll,ll> >
#define plli pair< ll,ll >
#define vps vector< pair< string, string> >
#define vpi vector< pair< int, int> >
#define all(x) x.begin(), x.end()
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define forn(i,a,n) for(ll i=a;i<n;i++)
#define scan(arr,a,n) for(ll i=(a);i<(n);i++)cin>>(arr)[i];
#define print(arr,a,n) for(ll i=(a);i<(n);i++)cout<<(arr)[i]<<" ";

ll add(ll x, ll y) {ll res = x + y; return (res >= mod ? res - mod : res);}
ll mul(ll x, ll y) {ll res = x * y; return (res >= mod ? res % mod : res);}
ll sub(ll x, ll y) {ll res = x - y; return (res < 0 ? res + mod : res);}
ll power(ll x, ll y) {ll res = 1; x %= mod; while (y) {if (y & 1)res = mul(res, x); y >>= 1; x = mul(x, x);} return res;}
ll mod_inv(ll x) {return power(x, mod - 2);}

long double cald(plli x, plli y){
    return sqrt(pow(abs(x.F - y.F), 2) + pow(abs(x.S - y.S), 2));
}

int main(){
    fast;
    #ifndef ONLINE_JUDGE
    freopen("input1.txt","r",stdin);
    freopen("output1.txt","w",stdout);
    #endif
    long double n;
    long double sum = 0;
    cin>>n;
    string s = "";
    forn(i, 0, n){
        s+=char('0'+i);
    }
    long double a[(ll)n][(ll)n];
    long double x, y;
    vector< pair< long double, long double> > v;
    forn(i, 0, n){
        cin>>x>>y;
        v.pb(mp(x, y));

    }
    forn(i, 0, n){
        forn(j, i+1, n){
            a[i][j] = cald(v[i], v[j]);
            a[j][i] = a[i][j];
        }
    }
    long double tot = 0;
    do{
        tot++;
        forn(i, 1, n){
            sum = sum+a[(ll)(s[i] - '0')][(ll)(s[i-1] - '0')];
        }
    }while(next_permutation(all(s)));
    cout<< fixed << setprecision(10) << sum/tot<<endl;
}

Measured memory_bytes: 3720
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = n-1; i >= 0; i--)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<vector<int>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VP = vector<P>;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

const int mod = 1000000007;
struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime mod
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main(){
    int n;
    cin >> n;
    mint ans = 1;
    mint n0 = 1, n9 = 1, n8 = 1;
    rep(i,n){
        ans *= 10;
        n0 *= 9;
        n9 *= 9;
        n8 *= 8;
    }
    ans = ans - ((n0 + n9) - n8);
    cout << ans << endl;
    return 0;
}

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

#define rep(i,m,n) for(int (i)=(int)(m);i<(int)(n);++i)
#define rep2(i,m,n) for(int (i)=(int)(n)-1;i>=(int)(m);--i)
#define REP(i,n) rep(i,0,n)
#define REP2(i,n) rep2(i,0,n)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define all(hoge) (hoge).begin(),(hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = (ll) 1e9 + 7;
//constexpr long long MOD = 998244353LL;
using ld=long double;
static const ld pi = 3.141592653589793L;
typedef vector<ll> Array;
typedef vector<Array> Matrix;


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

struct Edge {
	ll to, rev;
    long double cap;
	Edge(ll _to, long double _cap, ll _rev) {
	to = _to; cap = _cap; rev = _rev;
	}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

void add_edge(Graph& G, ll from, ll to, long double cap, bool revFlag, long double revCap) {
	G[from].push_back(Edge(to, cap, (ll)G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

void solve(){
    ll n;
    cin>>n;
    vec<ll> a(n);
    REP(i,n) cin>>a[i];
    string s;
    cin>>s;

    vec<ll> base;//基底
    
    REP2(i,n){
        for(auto b:base) chmin(a[i],a[i]^b);//baseで作れるときは置き換え
        if(a[i]){
            if(s[i]=='0'){
                base.push_back(a[i]);//基底で作れないときは基底に追加
            }else{
                cout<<1<<en;
                return;
            }
        }
    }
    cout<<0<<en;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	
	//solve();
	ll t;cin>>t;REP(i,t) solve();

    return 0;
}


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

// 比較演算子を自動生成
#define CAT(a, b) a ## b
#define COMP_1(v1) return lhs.v1 < rhs.v1
#define COMP_2(v1, ...) if (lhs.v1 != rhs.v1) COMP_1(v1); COMP_1(__VA_ARGS__)
#define COMP_3(v1, ...) if (lhs.v1 != rhs.v1) COMP_1(v1); COMP_2(__VA_ARGS__)
#define COMP_4(v1, ...) if (lhs.v1 != rhs.v1) COMP_1(v1); COMP_3(__VA_ARGS__)
#define COMP_5(v1, ...) if (lhs.v1 != rhs.v1) COMP_1(v1); COMP_4(__VA_ARGS__)
#define LESS_THAN(n, ...) bool operator<(const A & rhs) const { auto& lhs = *this; CAT(COMP_, n)(__VA_ARGS__); }

#define MAXC(c, x) (c = max(c, x))
#define MINC(c, x) (c = min(c, x))

#define FOR(i, s, n) for(ll i = (s); i < (ll)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(c) (c).begin(), (c).end()

// 10^x (by math)
#define TEN(x) ((ll)1e##x)

using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;

void solution(istream& cin, ostream& cout) {
	ll n; cin >> n;
	vector<pair<ll, ll>> p(n);
	REP(i, n) {
		string s; cin >> s;
		ll level = 0, mi_level = 0;
		REP(j, s.size()) {
			if (s[j] == '(') level++;
			else {
				level--;
				MINC(mi_level, level);
			}
		}
		p[i] = make_pair(level, mi_level);
	}

	ll sum = 0;
	REP(i, n) sum += p[i].first;
	if (sum != 0) {
		cout << "No" << endl;
		return;
	}

	sort(ALL(p), [&](auto lhs, auto rhs) {
		if (lhs.second == 0 && rhs.second == 0) return lhs.first > rhs.first;
		if (lhs.second == 0 || rhs.second == 0) return lhs.second > rhs.second;

		// 以降 どちらも second は負
		if (lhs.first * rhs.first < 0) return lhs.first > rhs.first;
		if (lhs.first > 0 && rhs.first > 0) {
			if (lhs.second != rhs.second) return lhs.second > rhs.second;
			return lhs.first > rhs.first;
		}
		if (lhs.first == 0 && rhs.first == 0) return lhs.second > rhs.second;
		if (lhs.first == 0 || rhs.first == 0) return lhs.first > rhs.first;

		// 以下 どちらも second も first も負
		ll lc = lhs.second - lhs.first;
		ll rc = rhs.second - rhs.first;
		if (lc == 0 && rc == 0) return lhs.first > rhs.first;
		if (lc != rc) return lc < rc;
		return lhs.first > rhs.first;
	});

	ll ans = 0;
	REP(i, n) {
		if (ans + p[i].second < 0) {
			cout << "No" << endl;
			return;
		}
		ans += p[i].first;
	}
	cout << "Yes" << endl;
	return;
}

int main() {
#ifdef INPUT_FROM_FILE
	ifstream cin("sample.in");
	ofstream cout("sample.out");
#endif
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(50);

	solution(cin, cout);
}


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

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  rep(i,N){
    cin >> A.at(i);
  }
  sort(A.begin(),A.end());
  reverse(A.begin(),A.end());

  int Alice = 0;
  int Bob = 0;
  for(int i = 0; i < N; i++){
    if(i %2 == 0){
      Alice += A.at(i);
    }else{
      Bob += A.at(i);
    }
  }
  cout << Alice - Bob << endl;
}





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

using namespace std;

typedef long long LL;
const int MOD = 1e9+7;
int N, K;

int main() {
    cin >> N >> K;
    LL ans=0;
    for (LL i=K; i<=N+1; i++) {
        LL diff;
        diff = i*(N-i+1) + 1;
        
        
        ans = (ans + diff) % MOD;
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 3644
#include<cstring>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstdio>

using namespace std;

typedef pair<int,int> P;
const int INF=100000000;
int h,w,n;
char maze[1005][1005];
int d[1005][1005];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
int ans;

int bfs(char charstart,char charend){
    int x,y;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(maze[i][j]==charstart){
                x=i;y=j;
            }
        }
    }
    queue<P> que;
    que.push(P(x,y));
    while(que.size()){
        x=que.front().first;
        y=que.front().second;
        que.pop();
        if(maze[x][y]==charend){
            return d[x][y];
        }
        for(int i=0;i<4;i++){
            int nx=x+dx[i],ny=y+dy[i];
            if(0<=nx&&nx<h&&ny>=0&&ny<w&&d[nx][ny]==0&&maze[nx][ny]!='X'){
                d[nx][ny]=d[x][y]+1;
                que.push(P(nx,ny));
            }
        }
    }
}

void solve(){
    scanf("%d%d%d",&h,&w,&n);
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin >> maze[i][j];
        }
    }
    ans+=bfs('S','1');
    for(int i=1;i<=n-1;i++){
        memset(d,0,sizeof(d));
        char s = char(i+48);
        char e = char(i+1+48);
        ans+=bfs(s,e);
    }
    printf("%d\n",ans);
}

int main(){
    solve();
    return 0;
}


Measured memory_bytes: 8172
#include <bits/stdc++.h>
#include<queue>
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef pair<string,string> Pstring;
typedef pair<double,double> Pdouble;

#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define Precision13 cout << fixed << setprecision(13)
const double PI=3.14159265358979323846;
const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];
char maze[310][310];
ll ans[310][310];
int main() {
  ll h,w,k;
  cin >> h >> w >> k;

  REP(i,h){
    REP(j,w){
      cin >> maze[i][j];
    }
  }

  ll icou=1;

  bool emp = false;
  bool pemp = false;


  REP(i,h){
    vector<ll> ichi;
    REP(j,w){
      if(maze[i][j] == '#'){
        ichi.push_back(j);
      }
    }

    if(ichi.size()>=1){
      emp = true;
    }
    
    
    REP(j,ichi.size()){
      if(j==0){
        for(int k=0;k<=ichi.at(j);k++){
          ans[i][k]=j+icou;
        }
      }
      if(j==ichi.size()-1){
        for(int k=ichi.at(j);k<w;k++){
          ans[i][k]=j+icou;
        }
      }
      if(j!=0){
        for(int k=ichi.at(j-1)+1;k<=ichi.at(j);k++){
          ans[i][k]=j+icou;
        }
      }
    }

    if(pemp==false&&emp==true){
      REP(j,i){
        REP(k,w){
          ans[j][k]=ans[i][k];
        }
      }
    }

    if(ichi.size()==0&&emp==true){
      REP(j,w){
        ans[i][j]=ans[i-1][j];
      }
    }

    icou+=ichi.size();
    pemp = emp;
  }
  
  REP(i,h){
    REP(j,w){
      if(j==w-1){
        cout << ans[i][j]<<endl;
      }else{
        cout << ans[i][j]<<" ";
      }
    }
  }
  
}

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

using namespace std;


#define N 200005



int32_t main()
{
   // ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    vector < int > a(n);
    int sum=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    sort(a.begin(),a.end());
    sum-=a[n-1];
    if(sum <= a[n-1])
    {
        cout<<"No"<<endl;
    }
    else
    {
        cout<<"Yes"<<endl;
    }
    return 0;
}

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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

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

	string S[3];
	rep(i, 0, 3)cin >> S[i];
	
	cout << (char)('A'+S[0][0]-'a') << (char)('A' + S[1][0]-'a') << (char)('A' + S[2][0]-'a') << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
import java.util.function.Supplier;
import java.util.stream.IntStream;
import java.util.stream.Stream;
import java.util.Comparator;

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

        int[] x = new int[N];
        int[] y = new int[N];
        int[] a = new int[N];

        for (int i = 0; i < N; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
            a[i] = sc.nextInt();
        }

        Supplier<Stream<Integer>> rangeN = () -> IntStream.range(0, N).boxed();
        Stream<Integer> sorted1 = rangeN.get().filter(i -> a[i] == 1).map(i -> x[i]).sorted(Comparator.reverseOrder());
        Stream<Integer> sorted2 = rangeN.get().filter(i -> a[i] == 2).map(i -> x[i]).sorted();
        Stream<Integer> sorted3 = rangeN.get().filter(i -> a[i] == 3).map(i -> y[i]).sorted(Comparator.reverseOrder());
        Stream<Integer> sorted4 = rangeN.get().filter(i -> a[i] == 4).map(i -> y[i]).sorted();

        int minX = sorted1.findFirst().orElse(0);
        int maxX = sorted2.findFirst().orElse(W);
        int minY = sorted3.findFirst().orElse(0);
        int maxY = sorted4.findFirst().orElse(H);

        // System.out.println(String.format("%d %d %d %d", minX, maxX, minY, maxY));
        int width = maxX - minX;
        int height = maxY - minY;

        if (height < 0 || width < 0) {
            System.out.println(0);
        } else {
            System.out.println(width * height);
        }
    }
}

Measured memory_bytes: 28756
// -*- coding:utf-8-unix -*-

use proconio::input;

fn main() {
    input! {
        t: (i64, i64, i64, i64),
    }
    let a = t.0;
    let b = t.1;
    let c = t.2;
    let k = t.3;

    if k <= a {
        println!("{}", k);
    } else if k <= a + b {
        println!("{}", a);
    } else if k <= a + b + c {
        let p = k - a - b;
        println!("{}", a - p);
    }
}

Measured memory_bytes: 2116
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
	long long n,k,a[55],i,t,h=0;
	cin>>n>>k;
	for(i=1;i<=n;i++)
	cin>>a[i];
	sort(a+1,a+n+1);
	t=a[n-k+1];
	for(i=1;i<=n;i++){
		if(a[i]>=t)
		h+=a[i];
	}
	cout<<h<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <deque>
#define F first
#define S second
using namespace std;
typedef pair<int, int> ii;
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
int main() {
	int N, P;
	scanf("%d", &N);
	int dist[N + 2][N + 2], ans = 0;
	for (int i = 0; i < N + 2; ++i) {
		for (int j = 0; j < N + 2; ++j) dist[i][j] = min(min(i, N + 1 - i), min(j, N + 1 - j));
	}
	ii pos[N * N];
	bool emptied[N + 2][N + 2];
	for (int i = 0; i < N + 2; ++i) {
		for (int j = 0; j < N + 2; ++j) emptied[i][j] = true;
	}
	for (int i = 0; i < N * N; ++i) {
		scanf("%d", &P);
		pos[i] = ii((P - 1) / N + 1, (P - 1) % N + 1);
	}
	for (int i = 0; i < N * N; ++i) {
		emptied[pos[i].F][pos[i].S] = false;
		for (int j = 0; j < 4; ++j) dist[pos[i].F][pos[i].S] = min(dist[pos[i].F][pos[i].S], dist[pos[i].F + dx[j]][pos[i].S + dy[j]]);
		deque<ii> bfs;
		bfs.push_back(pos[i]);
		while (!bfs.empty()) {
			ii x = bfs.front();
			bfs.pop_front();
			for (int j = 0; j < 4; ++j) {
				if (emptied[x.F + dx[j]][x.S + dy[j]]) {
					if (dist[x.F][x.S] + 1 < dist[x.F + dx[j]][x.S + dy[j]]) {
						dist[x.F + dx[j]][x.S + dy[j]] = dist[x.F][x.S] + 1;
						bfs.push_back(ii(x.F + dx[j], x.S + dy[j]));
					}
				} else if (dist[x.F][x.S] < dist[x.F + dx[j]][x.S + dy[j]]) {
					dist[x.F + dx[j]][x.S + dy[j]] = dist[x.F][x.S];
					bfs.push_front(ii(x.F + dx[j], x.S + dy[j]));
				}
			}
		}
		ans += dist[pos[i].F][pos[i].S];
	}
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 7328
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <deque>

using namespace std;

#define rep1(i, n) for (long long i = 0; i < (long long)(n); i++)
#define rep2(i, n, m) for (long long i = (long long)(n); i <= (long long)(m); i++)
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 (a > b) { a = b; return 1; } return 0; }
const long long mod = 1e9 + 7;

int main() {
    string s;
    cin >> s;
    long long count = 0;
    char prev = s.at(0);
    rep2(i, 1, s.length() - 1) {
        char current = s.at(i);
        if (prev != current) count++;
        prev = current;
    }
    cout << count << endl;
}

Measured memory_bytes: 512
// Winners don't quit and Quitters don't win
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define mod 998244353
#define MAX 100005
vll adj[MAX];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll f,n,m,k,x,y,i,j,c=0,h;
    ll a[MAX];
    cin>>n>>m;
    for(i=1;i<=n;++i){
    	cin>>a[i];
	}
	for(i=0;i<m;++i){
		cin>>x>>y;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	for(i=1;i<=n;++i){
		if(adj[i].size()==0){
			c++;
			continue;
		}
		h=a[i];
		f=1;
		for(j=0;j<adj[i].size();++j){
			if(a[adj[i][j]]>=h){
				f=0;
				break;
			}
		}
		if(f){
			c++;
		}
	}
	cout<<c;
}

Measured memory_bytes: 10244
def examC():
    N = I()
    S = [I() for _ in range(N)]
    S1 = []
    for s in S:
        if s%10==0:
            continue
        S1.append(s)
    if S1==[]:
        print(0)
        return
    S1.sort()
    ans = sum(S)
    if ans%10==0:
        ans -= S1[0]
    print(ans)
    return

def examD():
    N, A, B = LI()
    H = [I() for _ in range(N)]
    H.sort()
    l = 0; r = (H[-1]-1)//B + 1
    while(r-l>1):
        now = (l+r)//2
        cur = 0
        for i in H:
            if i-now*B>0:
                cur += ((i-now*B-1)//(A-B) +1)
        if cur>now:
            l = now
        else:
            r = now
    ans = r
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Measured memory_bytes: 46172
n = input()
m = len(n)
K = int(input())
#状態をもつ：i桁目まで見たときのj（その値は指定された値未満かどうか）において0でない数字がk個ある状態
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(m + 1)]
dp[0][0][0] = 1

for i in range(1, m+1):
    l = int(n[i-1])
    for k in range(K+1):
        #その値通りだった時、l=0だと0の数を増やせないのでi-1桁目でk個になってる個数を引き継ぐ
        #l!=0の場合にはまだ増やせるのでi-1桁目でk-1個になってる個数を引き継ぐ
        if k >= 1 and l != 0:
            dp[i][0][k] = dp[i-1][0][k-1]
        elif l == 0:
            dp[i][0][k] = dp[i-1][0][k]
        
        #base
        dp[i][1][k] = dp[i-1][1][k]

        #l!=0の時はi-1桁目でk個になってる個数を足すk=3 1000 -> 10002
        if l != 0:
            dp[i][1][k] += dp[i-1][0][k]

        #i-1桁目の個数から*9したものをたす(lがなんでも。どうせ未満だから)
        if k >= 1:
            dp[i][1][k] += 9 * dp[i-1][1][k-1]
            if l != 0:
                dp[i][1][k] += (l-1)*dp[i-1][0][k-1]
        

        
# print(dp)
print(dp[m][0][K] + dp[m][1][K])

Measured memory_bytes: 3064
//============================================================================
// Name        : d.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll;
int main() {
	ll a,b;cin>>a>>b;
	vector<ll> v;
	for(long long i=1;i*i<=a;i++){
		if(a%i==0){
			v.push_back(i);
		}
	}
	ll vs=v.size();
	for(int i=0;i<vs;i++){
		v.push_back(a/v[i]);
		if(v[i]*v[i]==a){
			v.pop_back();
		}
	}
	reverse(v.begin(),v.end());
	vector<ll> v2;
	set<ll> s;
	for(int i=0;i<v.size();i++){
		if(b%v[i]==0){
			v2.push_back(v[i]);
			s.insert(v[i]);
		}
	}
	ll ans=1;
	s.erase(1);
	v2.pop_back();
	vector<ll> p;
	while(v2.size()){
		ll temp=v2.back();
		v2.pop_back();
		int flag=1;
		for(int i=0;i<p.size();i++){
			if(temp%p[i]==0)flag=0;
		}
		if(flag){
			p.push_back(temp);
		}
		ans+=flag;

	}

//	while(s.size()){
//		ans++;
//		auto itr=s.begin();
//		ll temp=*itr;
//		itr++;
//		vector<ll> e;
//		e.push_back(temp);
//		while(itr!=s.end()){
//			if((*itr)%temp==0){
//				e.push_back(*itr);
//			}
//			itr++;
//		}
//		for(int i=0;i<e.size();i++){
//			s.erase(e[i]);
//		}
//
//	}
	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=100010, inf=2e9;
int n, A[MX], sum;
int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n;
	for(int i=1; i<=n; i++) cin>>A[i];
	A[n+1]=0;
	for(int i=1, p=0; i<=n+1; i++){
		sum+=abs(A[i]-p);
		p=A[i];
	}
	for(int i=1; i<=n; i++){
		cout<<(sum-abs(A[i]-A[i-1])-abs(A[i]-A[i+1])+abs(A[i-1]-A[i+1]))<<'\n';
	}
	return 0;
}

Measured memory_bytes: 1664
import collections
N = int(input())
A = list(map(int, input().split()))

A_num = collections.Counter(A)
values, counts = zip(*A_num.most_common())

ans = 0

for i in values :
  num = int(A_num[i])
  ans += num * (num - 1 ) // 2

for j in A :
  print(ans - int(A_num[j]) + 1 )

Measured memory_bytes: 37012
#include <iostream>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=1;i<=n;i++)

int gcd(int a, int b) {
  if(a < b) return gcd(b, a);
  int r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

int main(){
	int k;
	cin >> k;
	int sum =0;
	rep(a,k){
		rep(b,k){
			rep(c,k){
				sum += gcd(a,gcd(b,c));
			}
		}
	}
	
	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG true
// sort(a.begin(), a.end(), std::greater<int>());

/*
std::vector<std::string> split(const std::string &input, char delimiter)
{
    std::istringstream stream(input);

    std::string field;
    std::vector<std::string> result;
    while (std::getline(stream, field, delimiter))
    {
        result.push_back(field);
    }
    return result;
}
*/

int main()
{
    int n;
    map<int, int> a;
    cin >> n;
    rep(i, n)
    {
        int temp;
        cin >> temp;
        a[temp]++;
    }
    int ans = 0;
    for (auto it = begin(a); it != end(a); ++it)
    {
        if (it->second % 2== 1)
            ans++;
    }
    cout << ans << endl;
    return 0;
}


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

using ll=long long;
const ll MOD=1000000007;

int main() {
  double N,M;
  cin >> N >> M;
  vector<int> a(N);
  int sum=0;
  for(int i=0;i<N;i++){
    cin >> a[i];
    sum +=a[i];
  }
  sort(a.begin(),a.end());
  reverse(a.begin(),a.end());
  if(a[M-1]<sum/(4*M))
    cout << "No" << endl;
  else
    cout << "Yes" << endl;
}

Measured memory_bytes: 256
H = int(input())
memo = {}
def attack(h):
  if h in memo: return memo[h]

  if h <= 1:
    memo[h] = 1
    return memo[h]
  else:
    memo[h//2] = attack(h//2)
    return 1 + memo[h//2] + memo[h//2]

print(attack(H))

Measured memory_bytes: 38448