akhauriyash/Code-Regression huggingface dataset:
let N=stdin.ReadLine() |> int
let H=stdin.ReadLine().Split() |> Array.map int
let rec f i p a=
    if i=N then (max p a)
    elif H.[i]<=H.[i-1] then f (i+1) (p+1) a
    else f (i+1) 0 (max p a)
f 1 0 0 |> stdout.WriteLine

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

int main(){
    int ans=0;
    int x,y,z;
    cin >> x>>y>>z;

    while (x>=z){
        x -= y+z;
        ans++;
    }
    

    //cout <<fixed<<setprecision(16)<< << endl;
    cout << ans-1 << endl;

    //if(flag==1)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll i,j,k;

int main(){
    int n;cin>>n;
    
    bool seven=false;
    if(n/100==7){seven=true;}
    if((n/10)%10==7){seven=true;}
    if(n%10==7){seven=true;}

    if(seven){cout<<"Yes"<<endl;}
    else{cout<<"No"<<endl;}
    return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define ld long double
#define MOD 1000000007
#define endl "\n"
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(var) (var).begin(), (var).end()
#define MAXX 9000000000000000000
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vector<int> >
#define vpi vector<pair<int,int> > 
#define vvpi vector<vector<pair<int,int> > >

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif

	int n,i,j,x=1000,y,a[85];
	cin >> n;

	for(i=0;i<n;i++)
	{
		cin >> a[i];
	}
	y = x / a[0];
	x -= y * a[0];
	int cur = a[0];
	for(i=1;i<n;i++)
	{
		if(a[i] > cur)
		{
			x += y * a[i];
			y = 0;
			cur = MOD;
		}
		{
			x += y * (cur - a[i]);
			int tem = x / a[i];
			x -= tem * a[i];
			y += tem;
			cur = a[i];
		}
	}

	x += y * cur;
	cout << x;
	return 0;
}

Measured memory_bytes: 3580
n, m = map(int, input().split())
h = list(map(int, input().split()))
l_n = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    if h[a-1] == h[b-1]:
        l_n[a-1] = 1
        l_n[b-1] = 1
    elif h[a-1] > h[b-1]:
        l_n[b-1] = 1
    elif h[a-1] < h[b-1]:
        l_n[a-1] = 1
print(l_n.count(0)) 

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

using namespace std;

int main(int argc, char** argv)
{
        int n, k;
        scanf("%d%d", &n, &k);

        long long ans = k;
        for(int i = 1; i < n; i++){
            ans *= (k - 1);
        }

        printf("%lld", ans);
        return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		new Main().run();
	}
	
	long gcd(long a,long b) {
		return a==0?b:gcd(b%a,a);
	}
	
	long pow(long a,long n) {
		return n!=0?pow(a*a,n/2)*(n%2==1?a:1):1;
	}
	
	int[] f(long a) {
		int[] ret=new int[2];
		while (a%2==0) {
			ret[0]++;
			a/=2;
		}
		while (a%5==0) {
			ret[1]++;
			a/=5;
		}
		ret[0]=Math.min(ret[0], 9);
		ret[1]=Math.min(ret[1], 9);
		return ret;
	}

	void run() {
		Scanner sc = new Scanner(System.in);
		int N=sc.nextInt();
		long[][][][] cnt=new long[10][10][10][10];
		for (int i=0;i<N;++i) {
			double a=sc.nextDouble();
			long den=(long)1e9;
			long num=(long)Math.round(a*den);
			long gcd=gcd(num,den);
			num/=gcd;
			den/=gcd;
			int[] p=f(num);
			int[] q=f(den);
			cnt[p[0]][p[1]][q[0]][q[1]]++;
		}
		
		long ans=0;
		for (int i=0;i<10;++i) {
			for (int j=0;j<10;++j) {
				for (int k=0;k<10;++k) {
					for (int l=0;l<10;++l) {
						if (cnt[i][j][k][l]==0) continue;
						for (int i2=k;i2<10;++i2) {
							for (int j2=l;j2<10;++j2) {
								for (int k2=0;k2<=i;++k2) {
									for (int l2=0;l2<=j;++l2) {
										if (cnt[i2][j2][k2][l2]==0) continue;
										if (i==i2&&j==j2&&k==k2&&l==l2) continue;
										ans+=cnt[i][j][k][l]*cnt[i2][j2][k2][l2];
									}
								}
							}
						}
					}
				}
			}
		}
		
		ans/=2;
		for (int i=0;i<10;++i) {
			for (int j=0;j<10;++j) {
				long d=cnt[i][j][0][0];
				if (d==0) continue;
				ans+=d*(d-1)/2;
			}
		}
		
		System.out.println(ans);
		
	}	
	
	

	void tr(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}

}


Measured memory_bytes: 62500
use std::cmp::max;
use std::cmp::min;

#[allow(unused_macros)]
macro_rules! scan {
    () => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().to_string()
        }
    };
    (;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().split_whitespace().map(|s| s.to_string()).collect::<Vec<String>>()
        }
    };
    (;;$n:expr) => {
        {
            (0..$n).map(|_| scan!()).collect::<Vec<_>>()
        }
    };
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty;;$n:expr) => {
        (0..$n).map(|_| scan!($t;;)).collect::<Vec<_>>()
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
                    scan!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
                    scan!($($t),*)
        ).collect::<Vec<_>>()
    };
}

fn main() {
    let n = scan!(i64);
    let k = scan!(i64);
    let x = scan!(i64);
    let y = scan!(i64);
    println!("{}", x * min(n, k) + y * max(0, n - k));
}


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

#define REP(i, a, b) for (int i = (a); i < (b); i++)
#define REPR(i, a, b) for (int i = (a); i >= (b); i--)
#define ALL(container) (container).begin(), (container).end()

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;

const int INF = 1e9;

int N, Q;
string s;
char t[200005], d[200005];

bool isLeftFall(int pos) {
  REP(i, 0, Q) {
    if (s[pos] == t[i]) {
      if (d[i] == 'L') pos--;
      else pos++;
    }
    if (pos < 0) return true;
    if (pos >= N) return false;
  }
  return false;
}

bool isRightFall(int pos) {
  REP(i, 0, Q) {
    if (s[pos] == t[i]) {
      if (d[i] == 'L') pos--;
      else pos++;
    }
    if (pos >= N) return true;
    if (pos < 0) return false;
  }
  return false;
}

int main() {
  cin >> N >> Q >> s;
  REP(i, 0, Q) {
    cin >> t[i] >> d[i];
  }

  int l, r, mid, l_safe, r_safe;
  // 左に落ちる境界を探索
  l = -1, r = N;
  while (r - l > 1) {
    mid = (r+l) / 2;
    if (isLeftFall(mid)) l = mid;
    else r = mid;
  }
  l_safe = l+1;

  // 右に落ちる境界を探索
  l = -1, r = N;
  while (r - l > 1) {
    mid = (r+l) / 2;
    if (isRightFall(mid)) r = mid;
    else l = mid;
  }
  r_safe = r-1;

  cout << r_safe - l_safe + 1 << endl;

  return 0;
}


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

int n;
long long int x;

long long int f(int lv, long long int x) {
    if (lv == 0) return 1;

    long long int mid = 4*pow(2, lv-1)-1;

    if (x == 1) return 0;
    if (x < mid)  return f(lv-1, x-1);
    if (x == mid) return (2*pow(2, lv-1)-1) + 1;
    if (x > mid)  return f(lv-1, x-mid) + (2*pow(2, lv-1)-1) + 1;
}

int main() {
    cin >> n >> x;
    cout << f(n, x) << endl;
}

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

struct Precision{
  Precision(){
    cout<<fixed<<setprecision(12);
  }
}precision_beet;


template<typename T> 
struct BIT{
  Int n;
  vector<T> bit;
  //1-indexed
  BIT():n(-1){}
  BIT(Int n_,T d):n(n_),bit(n_+1,d){}
  
  T sum(Int i){
    T s=0;
    for(Int x=i;x>0;x-=(x&-x))
      s+=bit[x];
    return s;
  }
  void add(Int i,T a){
    if(i==0) return;
    for(Int x=i;x<=n;x+=(x&-x))
      bit[x]+=a;
  }
  
  Int lower_bound(Int w){
    if(w<=0) return 0;
    Int x=0,r=1;
    while(r<n) r<<=1;
    for(Int k=r;k>0;k>>=1){
      if(x+k<=n&&bit[x+k]<w){
	w-=bit[x+k];
	x+=k;
      }
    }
    return x+1;
  }
  
  T sum0(Int i){
    return sum(i+1);
  }
  void add0(Int i,T a){
    add(i+1,a);
  }
};

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<double> a(n),b(n),c(n);
  for(Int i=0;i<n;i++) cin>>a[i]>>b[i]>>c[i];

  vector<Int> ord(n);
  iota(ord.begin(),ord.end(),0);
  
  Int s=n*(n-1)/2;
  double ax=0,ay=0;

  for(Int t=0;t<2;t++){    
    
    auto count=[&](double x)->Int{
      vector<double> u(n);
      for(Int i=0;i<n;i++)
	u[i]=-(a[ord[i]]*x-c[ord[i]])/b[ord[i]];
      vector<double> v(u);
      sort(v.rbegin(),v.rend());
      v.erase(unique(v.begin(),v.end()),v.end());
      map<double, Int> idx;
      for(Int i=0;i<(Int)v.size();i++) idx[v[i]]=i;
      
      BIT<Int> bit(n+10,0);
      Int cnt=0;
      for(Int i=0;i<n;i++){
	cnt+=bit.sum0(idx[u[i]]);
	bit.add0(idx[u[i]],1);
	if(cnt>=(s+1)/2) return cnt;
      }
      return cnt;
    };
    
    sort(ord.begin(),ord.end(),
	 [&](Int i,Int j){return a[i]/b[i]<a[j]/b[j];});
    double l=-1e9,r=1e9;
    for(Int k=0;k<70;k++){
      double m=(l+r)/2;
      if(count(m)>=(s+1)/2) r=m;
      else l=m;
    }
    ax=l;
    swap(a,b);
    swap(ax,ay);
  }
  
  cout<<ax<<" "<<ay<<endl;
  return 0;
}


Measured memory_bytes: 7028
#include<stdio.h>
#include<string.h>
 
int main()
{
	char s[12];
	scanf("%s",s);
	int mark=0;
	int len=strlen(s);
	char c[12]={'\0'};
	int d = 0;
	
	for(int i = 0; i < len; i++){
		if(s[i]=='0'){
			c[d]='0';
			d++;
		}
		else if(s[i]=='1'){
			c[d]='1';
			d++;
		}
		else if(s[i]=='B'){
			if(d != 0){
				d--;
				c[d]='\0';
			}
		}
	}
	printf("%s", c);
	
	return 0;
}

Measured memory_bytes: 1692
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

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

ll n,d[10],v[10],ans;

ll gcd(ll a,ll b){
	if(!b)return a;
	return gcd(b,a%b);
}


int main(){
	while(cin>>n&&n){
		rep(i,n)cin>>d[i]>>v[i];
		ll l=1;
		rep(i,n-1)l*=d[i+1]*v[0]/gcd(d[0]*l*v[i+1],d[i+1]*v[0]);
		rep(i,n)cout<<l*d[0]*v[i]/d[i]/v[0]<<endl;
	}
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(),(x).end()

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

    vector<ll> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(all(A));

    if (N == 2) {
        cout << abs(A[0] - A[1]) << endl;
        cout << A[1] << " " << A[0] << endl;
        return;
    }

    int numneg = 0, numpos = 0;
    for (int i = 0; i < N; i++) {
        if (A[i] < 0) {
            numneg++;
        } else {
            numpos++;
        }
    }

    int flag = 0;
    stack<int> pos, neg;
    vector<pair<int,int>> sousa;
    if (numneg == 0) {
        flag = 1;
        sousa.push_back(make_pair(A[0], A[N-1]));
        neg.push(A[0]-A[N-1]);
    }
    if (numpos == 0) {
        flag = 1;
        sousa.push_back(make_pair(A[N-1], A[0]));
        pos.push(A[N-1]-A[0]);
    }

    int startidx = flag;
    int endidx = N-flag;
    for (int i = startidx; i < endidx; i++) {
        if (A[i] < 0) {
            neg.push(A[i]);
        } else {
            pos.push(A[i]);
        }
    }

    // cout << numneg << numpos << endl;
    // cout << neg.size() << pos.size() << endl;
    if (numneg > numpos) {
        int n, p;
        n = neg.top(); neg.pop();
        p = pos.top(); pos.pop();
        sousa.push_back(make_pair(p, n));
        pos.push(p-n);
    }


    while (pos.size() != 1) {
        int n, p;
        n = neg.top(); neg.pop();
        p = pos.top(); pos.pop();
        sousa.push_back(make_pair(n, p));
        neg.push(n-p);
    }

    numneg = neg.size();
    for (int i = 0; i < numneg; i++) {
        int n, p;
        n = neg.top(); neg.pop();
        p = pos.top(); pos.pop();
        sousa.push_back(make_pair(p, n));
        pos.push(p-n);
    }

    cout << pos.top() << endl;
    for (int i = 0; i < (int)sousa.size(); i++) {
        cout << sousa[i].first << " " << sousa[i].second << endl;
    }

    return;
}

int main(int argc, char const* argv[])
{
    solve();
    return 0;
}


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

int main () {
    int N, K, X, Y;
    cin >> N >> K >> X >> Y;
    int sum;
    
    if (N >= K + 1) sum = X * K + Y * (N - K);
    else sum = X * N;

    cout << sum << endl;

    return 0; 
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
    int a,b,c,k,sum=0;
    cin>>a>>b>>c>>k;
    if(k<=a) sum=k;
    else if(k<=a+b) sum=a;
    else sum=a-(k-a-b);
    cout<<sum;
}

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



int main(){
int n,m,x;
cin >> n >> m >> x;

vector<int>c(n);
vector<vector<int>>a(n,vector<int>(m));

rep(i,n){
    cin >> c.at(i);
    rep(j,m){
        cin >> a.at(i).at(j);
    }
}
int ansn = 0;
int ans = 10000000;

for (int tmp = 0; tmp < (1 << 12); tmp++) {
  bitset<12> s(tmp);
  // (ビット列sに対する処理)
vector<int>master(m);
   // ビット列の1のビットに対応する整数を選んだとみなして総和を求める
    int sum = 0;
    for (int i = 0; i < n; i++) {
      if (s.test(i)) {
        rep(j,m){
            master.at(j) += a.at(i).at(j);
        }
        sum += c[i];
      }
    }
    //あるビット列に対して、成績を求めた。以下、成績評価
    bool over = true;
    rep(j,m){
        if(master[j]<x){
            over = false;
            break;
        }}
    if(over){
        if(ans > sum){
            ans = sum;
            ansn = tmp;}
    }
    
    
   
    
  }

if(ans >= 10000000) ans = -1;

  cout << ans << endl;
}

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

int main()
{
  string map[3];
  for(;cin>>map[0],map[0]!="0";)
    {
      cin>>map[1];
      cin>>map[2];
      string ans="NA";
      for(int i=0;i<3;i++)
	{
	  if(map[i][0]!='+' && map[i][0]==map[i][1]&&map[i][1]==map[i][2])
	    ans=map[i][0];
	  if(map[0][i]!='+' && map[0][i]==map[1][i]&&map[1][i]==map[2][i])
	    ans=map[0][i];
	}
      if(map[0][0]!='+' && map[0][0]==map[1][1]&&map[1][1]==map[2][2])
	ans=map[0][0];
      if(map[0][2]!='+' &&map[0][2]==map[1][1]&&map[1][1]==map[2][0])
	ans=map[0][2];
      cout<<ans<<endl;
    }
}

Measured memory_bytes: 1188
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int>Z(N+1,1);
  for(int i=2; i<=N; i++){
    int k=i;
    for(int j=2; j<=k/j; j++){
      if(k%j==0){
        Z[j]++;
        k/=j;
        j--;
      }
    }
    Z[k]++;   
  }
  long long ans=1;
  for(int i=2; i<=N; i++){
    ans*=Z[i];
    ans%=1000000007;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
import heapq
n,m = map(int,input().split())
l = list(map(int,input().split()))

for i in range(n):
  l[i] *= -1

heapq.heapify(l)
for i in range(m):
  new = heapq.heappop(l)
  heapq.heappush(l,-((-new)//2))

print(-sum(l))

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

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin>>N;
    vector<pair<int,int>>v;
    for(int i = 0 ; i < N ; i++){
        int a,b;
        cin>>a>>b;
        v.push_back({a-b,a+b});
    }
    sort(v.begin(),v.end(),[](pair<int,int> a , pair<int,int>b){
        return a.second<b.second;
    });

    int last = -1e9;
    int ans = 0;
    for(auto i : v){
        if(i.first>=last){
            last = i.second;
            ans++;
        }
    }
    cout<<ans<<'\n';
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int N = 1000000;
const ll mod = 1000000007;
using Graph = vector<vector<int>>;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}
ll lcm(ll A, ll B){
    return A * B / gcd(A, B);
}

/*------------------------------------------------------------------*/

int main(){
    ll x; cin >> x;
    ll max = 1e17;
    ll mi_max = -1e17;
    for(ll i = 0; ll(pow(i, 5)) < max; i++){
        for(ll j = 2000; ll(pow(j, 5)) > mi_max; j--){
            if(ll(pow(i, 5)) - ll(pow(j, 5)) == x){
                cout << i << " " << j << endl;
                return 0;
            }
        }
    }
}

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

int main() {
    string s;
    cin >> s;

    int a[3] = {};

    a[s[0] - 'a'] = 1;
    a[s[1] - 'a'] = 1;
    a[s[2] - 'a'] = 1;

    if (a[0] && a[1] && a[2]) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cmath>	

using namespace std;

int main(){
	double x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	cout << fixed << setprecision(9) << sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) << endl;
}

Measured memory_bytes: 3256
#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
using namespace std;
int main(){
    string s;
    cin>>s;
    int n=0;
    int w=0;
    int ss=0;
    int e=0;
    for(int i = 0;i<s.length();i++){
        if(s[i]=='N'){
            n++;
        }else if(s[i]=='W'){
            w++;
        }else if(s[i]=='S'){
            ss++;
        }else{
            e++;
        }
    }
    if(((n==0)&&(ss!=0))||((w==0)&&(e!=0))||((n!=0)&&(ss==0))||((w!=0)&&(e==0))){
        cout<<"No"<<endl;
    }else{
        cout<<"Yes"<<endl;
    }
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    int L = sc. nextInt();
    int[] ans= new int[3];

    ans[0] = N + M;
    ans[1] = M + L;
    ans[2] = L + N;

    int min = 999999999;
    for(int i = 0; i < 3; i++) {
    	min = Math.min(min, ans[i]);
    }
    System.out.println(min);
  }
}


Measured memory_bytes: 23764
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <complex>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <iterator>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <regex>
#include <limits>
#include <time.h>
#include <cstdint>
using namespace std;
using pii  = pair<int,int>;
using ll=long long;
using ld=long double;
#define pb push_back
#define mp make_pair
#define sc second
#define fr first
#define stpr setprecision
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,n) for(ll i=0;i<(n);++i)
#define Rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,n) for(ll i=n-1;i>=0;i--)
#define rRep(i,a,b) for(ll i=b-1;i>=a;i--)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define endl '\n'
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b, a%b));}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll MOD=1000000007;
constexpr ll INF=1000000011;
constexpr ll MOD2=998244353;
constexpr ll LINF = 1001002003004005006ll;
constexpr ld EPS=10e-8;
template <class T, class U> inline bool chmax(T& lhs, const U& rhs) { if (lhs < rhs) { lhs = rhs; return 1; } return 0; }
template <class T, class U> inline bool chmin(T& lhs, const U& rhs) { if (lhs > rhs) { lhs = rhs; return 1; } return 0; }
template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}
template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}
template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}
template<class T> ostream& operator<<(ostream& os, vector<T>& v){
  for(auto i=begin(v); i != end(v); ++i){
    if(i !=begin(v)) os << ' ';
    os << *i;
  }
  return os;
}

string S;

int main(){
  cin >>S ;
  if(S[1]=='R'){
    cout << "ABC" << endl;
  }
  else{
    cout << "ARC" << endl;
  }
}

Measured memory_bytes: 3624
if __name__ == "__main__":
    N = int(input())
    S = input()

    dp = [[0] * 5005 for i in range(5005)]

    for i in range(N, 0, -1):
        for j in range(N, 0, -1):
            if S[i-1] != S[j-1]:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j+1] + 1

    result = 0
    for i in range(N):
        for j in range(N):
            if i >= j:
                continue
            now = min(dp[i][j], j-i)
            result = max([now, result])

    print(result)


Measured memory_bytes: 232072
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<climits>
#include<numeric>
#include<cmath>
#include<cstring>
#include<deque>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define VSORT(v) sort(v.begin(), v.end());
#define VE vector<int>
#define VEP vector<pair<int,int>>
#define llong long long
#define pb(a) push_back(a)
using namespace std;
int main() {
	int a, b;
	cin >> a >> b;
	if (b == 1) {
		cout << 0 << endl;
	}
	else { cout << a - b << endl; }
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb push_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef multiset<ll> S;
typedef priority_queue<ll> PQ;
typedef priority_queue<P,vector<P>,greater<P>> SPQ;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
const ll inf=1001001001001001;
const int INF=1001001001;
const int mod=1000000007;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<endl;}
template<class T> void outvp(T v){rep(i,v.size())outp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> void outvv(T v){rep(i,v.size()){rep(j,v[i].size()){if(j)cout<<' ';cout<<v[i][j];}cout<<endl;}}
int main(){
    ll a,b,c,d;cin>>a>>b>>c>>d;
    out((a-1)/b+1);
}

Measured memory_bytes: 256
#include<stdio.h>
#define N 2
 
int main(void){

	double x[N][N+1];
	double su1=0,su2=0;
	int i,j,k;
	char str[100];
    
	for( ;fgets(str,sizeof(str),stdin)!=NULL; ){
		sscanf(str,"%lf %lf %lf %lf %lf %lf",&x[0][0],&x[0][1],&x[0][2],&x[1][0],&x[1][1],&x[1][2]);
		for(k=0;k<=N-2;k++){
			for(j=k+1;j<=N-1;j++){
				su1=x[k][k];
				su2=x[j][k];
				for(i=0;i<=2;i++){
					x[j][i]=x[j][i]-x[k][i]*su2/su1;
				}
			}
		}	
		for(k=0;k<=N-2;k++){
			for(j=k+1;j<=N-1;j++){
				su1=x[1-k][1-k];
				su2=x[1-j][1-k];
				for(i=0;i<=2;i++){
					x[1-j][i]=x[1-j][i]-x[1-k][i]*su2/su1;
				}
			}
		}
		su1=0;
		for(j=0;j<=N-1;j++){
		su1=x[j][j];
			for(i=0;i<=N;i++){
			x[j][i]=x[j][i]/su1;
			}	
		}
		for(i=0;i<N;i++){
			if(i) printf(" ");
			printf("%3.3f",x[i][N]);
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 664
#[allow(unused_imports)]
use std::{cmp::Reverse, collections::*};

#[allow(unused_imports)]
use proconio::{
    fastout, input,
    marker::{Chars, Usize1},
};

#[allow(unused_imports)]
use itertools::Itertools;

#[allow(unused_imports)]
use num::Integer;

#[fastout]
pub fn main() {
    input! {
        n: usize,
        b: [i32; n - 1],
    }

    let mut prev = b[0];
    let mut sum = b[0];
    for i in 1..(n - 1) {
        sum += b[i].min(prev);
        prev = b[i];
    }
    sum += b[n - 2];
    println!("{}", sum);
}


Measured memory_bytes: 2168
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int a=in.nextInt();
        int b=in.nextInt();
        if(a<=b){
            System.out.println("unsafe");
        }else{
            System.out.println("safe");
        }
    }
}

Measured memory_bytes: 35620
#include <iostream>
#include <complex>
#include <vector>

using namespace std;

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

#define EPS 1e-8

typedef complex<double> P;

double dot(P a,P b){
	return real(a)*real(b)+imag(a)*imag(b);
}

double cross(P a,P b){
	return real(a)*imag(b)-imag(a)*real(b);
}

double sq(double x){
	return x*x;
}

int main(){
	int n;
	while(cin>>n,n){
		vector<P> v(n);
		rep(i,n){
			double a,b;
			cin>>a>>b;
			v[i]=P(a,b);
		}
		int ans = 1;
		rep(i,n){
			rep(j,i){
				// cout<<i<<" "<<j<<" "<<abs(v[j]-v[i])<<endl;
				if(abs(v[j]-v[i])-2>EPS) continue;
				P c = v[j]-v[i];
				P n1 = (c*P(0,+1))/abs(c);
				P n2 = (c*P(0,-1))/abs(c);
				double d = sqrt(1-sq(abs(v[j]-v[i])/2));
				// cout<<"d "<<d<<endl;
				n1*=d;
				n2*=d;
				n1 += (v[j]-v[i])/2.0;
				n2 += (v[j]-v[i])/2.0;
				// cout<<"n1 "<<n1.real()<<" "<<n1.imag()<<endl;
				int tmp1=0;
				int tmp2=0;
				rep(k,n){
					if(1-abs(n1-v[k]+v[i])>-EPS) tmp1++;
					if(1-abs(n2-v[k]+v[i])>-EPS) tmp2++;
				}
				ans=max(ans,tmp1);
				ans=max(ans,tmp2);
			}
		}
		cout<<ans<<endl;
		// break;
	}
}

Measured memory_bytes: 3216
#include<iostream>
using namespace std;
char s[7];
int main(){
    cin>> s + 1;
    if(s[1] == s[2] && s[3] == s[4] && s[1] != s[3]){
        cout<<"Yes";
        return 0;
    }
    if(s[1] == s[3] && s[2] == s[4] && s[1] != s[2]){
        cout<<"Yes";
        return 0;
    }
    if(s[1] == s[4] && s[3] == s[2] && s[1] != s[2]){
        cout<<"Yes";
        return 0;
    }
    cout<<"No";
}


Measured memory_bytes: 256
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, k = map(int, input().split())
    print(k * pow(k - 1, n - 1))
resolve()

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

#define M_PI       3.14159265358979323846

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
inline int readInt() { int x; scanf("%d", &x); return x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;


//container util

//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a)*(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()

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

#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)


struct Edge {
    int to, from;
    ll cost;
    Edge(int from, int to, ll cost): from(from), to(to), cost(cost) {}
};

typedef vector<vector<Edge>> AdjList;
AdjList graph;

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

    vector<int> v;

    int A, B; cin >> A >> B;
    cout << max({A+B, A-B, A*B}) << endl;
    return 0;

}

Measured memory_bytes: 256
import math
a,b,h,m = map(int, input().split())

rad = min(abs(6*m - 30*h - 0.5*m), 360-abs(6*m -30*h - 0.5*m))

cosc = math.cos(math.radians(rad))


ans = (a*a + b*b - 2*a*b*cosc) ** 0.5
print(ans)

Measured memory_bytes: 62604
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <math.h>
#include <algorithm>

using namespace std;

char buf[2001][2001];
int memo[2001][2001];
int main()
{
  int W, H;
  cin >> H >> W;
  for (int i=0;i<H;i++) {
    cin >> buf[i];
  }
  int maxV = 0;
  int XV = -1;
  for (int x=0;x<W;x++) {
    for (int y=0;y<H;y++) {
      if (buf[y][x] == '#') continue;
      int YV = 1;
      int ey = H;
      for (int i=y+1;i<H;i++) {
        if (buf[i][x] == '#') {
          ey = i;
          break;
        }
        YV++;
      }
      for (int i=y;i<ey;i++) {
        memo[i][x] = YV;
      }
      y = ey;
    }
  }
  for (int y=0;y<H;y++) {
    XV = -1;
    for (int x=0;x<W;x++) {
      if (buf[y][x] == '#') {
        XV = -1;
        continue;
      }
      if (XV < 0) {
        XV = 1;
        for (int i=x+1;i<W;i++) {
          if (buf[y][i] == '#') break;
          XV++;
        }
      }
      int value = XV + memo[y][x] -1;
      if (value > maxV) maxV = value;
    }
  }
  cout << maxV << endl;
  return 0;
}


Measured memory_bytes: 19840
#include <iostream>
#include <string>
int main(){
int a,c,b;
std::cin >> a >> b >> c;
if(a==7 && b==5 && c==5)
std::cout << "YES" << std::endl;
else if(b==7 && a==5 && c==5)
std::cout << "YES" << std::endl;
else if(c==7 && b==5 && a==5)
std::cout << "YES" << std::endl;
else
std::cout << "NO" << std::endl;
}


Measured memory_bytes: 256
#include<stdio.h>
typedef long long ll;
int main(){
    ll N,K,i;
    ll A[200002];
    scanf("%lld%lld",&N,&K);
    for(i=1;i<=N;i++){
        scanf("%lld",&A[i]);
    }
    for(i=1;i<=N-K;i++){
        if(A[i]<A[K+i]){
            printf("Yes\n");
        }else{
            printf("No\n");
        }
    }
    return 0;
}

Measured memory_bytes: 3228
import Control.Monad
import Data.List

bil n = replicateM n [0,1]

chk [] = True
chk [_] = True
chk (a:b:r) | a==1 && b==1 = False
chk (_:r) = chk r

ami1 ([],_) = Nothing
ami1 ([a],_) = Just(a, ([],[]))
ami1 (a:b:u, 1:r) = Just(b, (a:u,r))
ami1 (a:u, _:r) = Just(a, (u,r))

amitr pr = map (unfoldr ami1 . (,) pr)

amisum = foldl' (\al bl->map (\(a,b)->(a+b)`mod`1000000007) $ zip al bl)

amih bl ac = amisum ac $ amitr ac bl

main = do
    (h:w:k:_)<-map read.words<$>getLine::IO[Int]
    let bl = filter chk $ bil $ w-1
    print $ (!! (k-1)) $ (!! h) $ iterate (amih $ tail bl) $ 1:replicate (w-1) 0


Measured memory_bytes: 2300
import java.util.ArrayDeque

fun main() {
    val (n, m) = readLine()!!.split(" ").map(String::toInt)

    val map = Array(n) { mutableListOf<Int>() }

    repeat(m) {
        val (a, b) = readLine()!!.split(" ").map { it.toInt() - 1 }
        map[a].add(b)
        map[b].add(a)
    }

    val ans = Array(n) { 0 }
    ans[0] = 0

    val que = ArrayDeque<Int>()
    que.addLast(0)

    while (que.isNotEmpty()) {
        val v = que.removeFirst()

        map[v].forEach {
            if (ans[it] != 0) return@forEach

            ans[it] = v + 1
            que.addLast(it)
        }
    }

    println("Yes")
    ans.takeLast(n - 1).forEach {
        println(it)
    }
}

Measured memory_bytes: 84152
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fip ios_base::sync_with_stdio(false); cin.tie(NULL) 
#define reptUsual(b) for(i=0; i<b; ++i)
#define rept(i,a,b) for(i=a; i<b; ++i)
#define pb(a) push_back(a)
#define newln cout<<"\n"
#define bigPrime 1000000007
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef pair<ll , ll> pll;
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>  new_data_set;
// continue // break // greater // string // length // while //iterator //first //second //size //begin //end
 
/*
void funct(int *dp,int *ar, int n){
    if( dp[n]!=0) return;
    else{
        int res=1;
        for(int i=n-1;i>=0;i--){
            
            if(ar[n]>ar[i]){
                funct(dp,ar,i);
                res=max(res, dp[i]+1);
            }
 
        }
        dp[n]=res;
    }
}

bool cmp(pair<int, int>& a, 
         pair<int, int>& b) 
{ 
    return a.second > b.second; 
}
*/

void dfs2(vector <vi> &v, vector<vi> &vis, vi &ancestors, int a,int b){

    
}


int dfs(vector <vi> &v, int n, vector<vi> &vis, vi &ancestors){
    int i,cnt=0;
    ancestors.pb(n);
    reptUsual(v[n].size()){
        if(vis[n][v[n][i]]==0)  {
            for(int j=0;j<ancestors.size();j++) if(ancestors[j]==v[n][i]){ dfs2(v,vis,ancestors,n,v[n][i]);}
            for(int j=0;j<ancestors.size();j++) vis[ancestors[j]][v[n][i]]=1;
            cnt+=dfs(v,v[n][i],vis,ancestors)+1;            
            
            }
    }
    return cnt;

}


int main()
{
    fip;
    double n,d;
    int i;
    int nn;
    cin>>nn>>d;
    n=nn;
    int cnt=0;
    reptUsual(nn){
        double x,y;
        cin>>x>>y;
        if( (sqrt)(pow(x,2.0) +pow(y,2.0) ) <=(double)(d) ) cnt++;
    }
    cout<<cnt;

    return 0;
}

Measured memory_bytes: 3860
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define endl "\n"
using namespace std;


int32_t main() {

    fast
    int n;
    cin>>n;

    string s;
    cin>>s;

    int left=0, right=n-1;
    int ans=0;

    while(left<right){
        if(s[left]=='W' && s[right]=='R'){
            ans++,left++,right--;
        }
        if(s[left]=='R')left++;
        if(s[right]=='W')right--;
    }
    cout<<ans<<endl;


    return 0;
}



Measured memory_bytes: 3744
// -----------------------------------
// Author     : MatsuTaku
// Country    : Japan
// Created    : 04/11/20 07:29:12
// -----------------------------------

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

  string s; cin>>s;
  ll ans = 0;
  int i = 0;
  ll acnt = 0;
  while (i<s.size()) {
    if (s[i] == 'A') {
      ++acnt;
      ++i;
    } else if (s[i] == 'B' and i+1<s.size() and s[i+1]=='C') {
      ans += acnt;
      i+=2;
    } else {
      acnt = 0;
      ++i;
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 720
#include<cstdio>

using namespace std;


int field[100000];
int method[100000];
int n,m;

int distance(int prevpos,int nextpos){
	//printf("called %d %d\n",prevpos,nextpos);
	int dis=0;
	for(int lp=prevpos;prevpos<nextpos;prevpos++){
		dis+=field[prevpos];
	}
	return dis;
}


int main(void){
	int mostfar=0;
	int answer=0;
	int prevpos=0;
	int nextpos=0;
	scanf("%d %d",&n,&m);
	for(int lp=0;lp<n-1;lp++){
		scanf("%d",&field[lp]);
	}
	for(int lp=0;lp<m;lp++){
		scanf("%d",&method[lp]);
	}
	for(int day=0;day<m;day++){
		nextpos=prevpos+method[day];
		//printf("prevpos %d nextpos %d\n",prevpos,nextpos);
		if(prevpos<nextpos){
			answer+=distance(prevpos,nextpos);
		}else{
			answer+=distance(nextpos,prevpos);
		}
		//printf("answer is %d\n",answer);
		prevpos=nextpos;
		if(answer>100000){
			answer=answer%100000;
		}
		
	}
		
	printf("%d\n",answer%100000);
}
	

Measured memory_bytes: 3536
from collections import Counter
from statistics import median
N = int(input())
a_lis = list(map(int, input().split()))

new_lis = [item - i - 1 for i, item in enumerate(a_lis)]

mode = median(new_lis)

count = 0
for i in range(N):
    count += abs(a_lis[i] - mode - i - 1)
    
print(int(count))

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


bool vis[105];

signed main()
{
	int n,k;
	while(cin>>n>>k){
		for(int i=1;i<=k;i++){
			int a,b;
			cin>>a;
			for(int i=1;i<=a;i++){
				cin>>b;
				vis[b]=1;
			}
		}
		int sum=0;
		for(int i=1;i<=n;i++)
		if(!vis[i])sum++;
		cout<<sum<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
const double PI=acos(-1);

int main(){
    ll n; cin >> n;
    vector<ll> l(n);
    rep(i, n) cin >> l[i];
    sort(l.rbegin(), l.rend());
    ll cnt = 0;
    rep(i, n){
        for(ll j = i+1; j < n; ++j){
            ll a1 = l[i] - l[j], a2 = l[j] - l[i], a3 = l[i] + l[j];
            
            ll ok = j, ng = n;
            while(abs(ok - ng) > 1){
                ll mid = (ok+ng) / 2;
                if(a1 < l[mid] && a2 < l[mid] && l[mid] < a3) ok = mid;
                else ng = mid;
            }
            cnt += ok - j;
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    char sea[15];
    cin >> sea;
    int ring;
    cin >> ring;
    int okring = 0;
    for(int i = 0;i < ring;i++){
        char str[30];
        cin >> str;
        for(int j = 0;j < 10;j++){
            str[10+j] = str[j];
        }
        if(strstr(str,sea) != NULL){
            okring++;
        }
    }
    cout << okring << endl;
    return 0;
}

Measured memory_bytes: 3080
#81b
n=int(input())
a=list(map(int,input().split()))
ans=0
flag=True

while flag:
    for i in range(n):
        if a[i]%2==0:
            a[i]=a[i]//2
            ans+=1
        else:
            print(ans//n)
            flag=False
            break




Measured memory_bytes: 2940
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func getNextLine(scanner *bufio.Reader) string {
	var buffer string
	for {
		line, isPrefix, _ := scanner.ReadLine()
		buffer += string(line)
		if isPrefix == false {
			break
		}
	}
	return buffer
}

func getIntList(scanner *bufio.Reader) []int {
	list := strings.Split(getNextLine(scanner), " ")
	l := len(list)
	result := make([]int, l)
	for i := 0; i < l; i++ {
		result[i], _ = strconv.Atoi(list[i])
	}
	return result
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := bufio.NewReader(fp)

	var n int
	fmt.Sscan(getNextLine(scanner), &n)
	aaa := make([]int, n)
	sum := 0
	for i := 0; i < n; i++ {
		fmt.Sscan(getNextLine(scanner), &aaa[i])
		sum += aaa[i]
	}
	dp1 := chokudai(3, sum, n, aaa)
	dp2 := chokudai(2, sum, n, aaa)
	ans := int64(0)
	for i := 0; i <= sum; i++ {
		ans += dp1[i]
		if sum%2 == 0 && i == sum/2 {
			ans += dp2[i] * 3
		}
		if i >= (sum+sum%2)/2 {
			ans -= 3 * dp1[i]
		}
		if ans < 0 {
			ans += 998244353
		}
		ans %= 998244353
	}
	fmt.Println(ans)
}

func chokudai(sp int, sum int, n int, aaa []int) []int64 {
	prev := 0
	current := 1
	sp--
	var dp [2][]int64
	dp[prev] = make([]int64, sum+1)
	dp[current] = make([]int64, sum+1)
	dp[prev][0] = 1
	dp[current][0] = 1
	for i := 0; i < n; i++ {
		for j := 0; j <= sum; j++ {
			dp[current][j] = dp[prev][j] * int64(sp)
			if aaa[i] <= j {
				dp[current][j] += dp[prev][j-aaa[i]]
			}
			dp[current][j] %= 998244353
		}
		prev, current = current, prev
	}
	return dp[prev]
}


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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;

const ll MOD = 1e9+7;
const int NMAX = 100100;

int N;
vector<int> edges[NMAX];

pii dfs(int u, int p) {

	pii f = pii(1, 1);
	
	for(auto& v : edges[u]) {
		if(v == p) continue;
		pii res = dfs(v, u);
		f.first = (f.first*res.second)%MOD;
		f.second = (f.second*(res.second+res.first))%MOD;
	}
	
	return f;
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N;
	for(int i=0;i<N-1;++i) {
		int x, y;
		cin >> x >> y;
		edges[x].push_back(y);
		edges[y].push_back(x);
	}

	pii a = dfs(1, 0);
	cout << (a.first+a.second)%MOD << endl;

	return 0;
}


Measured memory_bytes: 12672
#gcdは3.4.3だとfractionsにある
from fractions import gcd
import math

from math import factorial as f

from math import ceil,floor,sqrt


import bisect
import re
import heapq


from copy import deepcopy
import itertools

from sys import exit

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

yes = "Yes"
no = "No"

def main():
    a = []
    for i in range(3):
        atmp = li()
        a.append(atmp)
    n = ii()
    b = []
    for i in range(n):
        tmp = ii()
        b.append(tmp)
    
    for i in b:
        for itr in range(3):
            for itritr in range(3):
                if a[itr][itritr] == i:
                    a[itr][itritr] = 0

    for i in range(3):
        if sum(a[i]) == 0:
            print(yes)
            exit()
    for i in range(3):
        if a[0][i]+a[1][i]+a[2][i] == 0:
            print(yes)
            exit()
    if a[0][0]+a[1][1]+a[2][2] == 0 or a[0][2]+a[1][1]+a[2][0] == 0:
        print(yes)
        exit()
    print(no)



main()



Measured memory_bytes: 5244
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n, k int
	fmt.Scan(&n, &k)
	a := make([]int, n)
	for i := range a {
		fmt.Scan(&a[i])
	}

	x := map[int]int{}
	for _, v := range a {
		x[v]++
	}

	var xx []int
	for _, v := range x {
		xx = append(xx, v)
	}

	ans := 0
	nowN := len(xx)
	sort.Ints(xx)
	for _, v := range xx{
		if nowN > k {
			ans += v
			nowN -= 1
		} else {
			break
		}
	}

	fmt.Println(ans)
}


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

using ll = long long;
using pii = pair<int, int>;

#define vt          vector
#define sz(x)       (int)(x).size()
#define all(x)      (x).begin(), (x).end()
#define rall(x)     (x).rbegin(), (x).rend()
#define fi          first
#define se          second

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

    int n, k, c;
    cin >> n >> k >> c;
    string s;
    cin >> s;

    vt<int> pos;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'o') pos.push_back(i);
    }

    vt<int> lo(k), hi(k);
    lo[0] = 0, hi.back() = n - 1;
    for (int i = 1, cur = 0; i <= k; i++) {
        auto it = upper_bound(all(pos), cur + c);

        if (i != k) lo[i] = cur = *it;
        else if (it != pos.end()) return 0;
    }
    for (int i = k - 2, cur = n - 1; i >= 0; i--) {
        auto it = lower_bound(all(pos), cur - c);

        hi[i] = cur = *--it;
    }

    for (int i = 0; i < k; i++) {
        if (lo[i] == hi[i]) cout << lo[i] + 1 << '\n';
    }
}


Measured memory_bytes: 5636
#include<bits/stdc++.h>
#define time Time
#define pii pair<int,int>    
#define x first    
#define y second 
#define N 10000005   
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))    
#define sqr(x) ((x)*(x))
typedef long long LL;  
using namespace std;
const int mod=1e9+7;
long long int f_pow(int a,int b){
	LL res=1,temp=a;
	while(b){
		if(b&1)res*=temp;
		temp=temp*temp%mod;
		res%=mod;
		b>>=1;
	}
	return res;
}
int main(){
	int n;
	scanf("%d",&n);
	if(n%2==1){
		int a[100005];
		memset(a,0,sizeof(a));
		for(int i=0;i<n;i++)
		{
			int b;
			scanf("%d",&b);
			a[b]++;
		}
		int ok=1;
		if(a[0]!=1)
		ok=0;
		for(int i=2;i<n;i+=2)
		if(a[i]!=2)
		ok=0;
		if(!ok)
		printf("0\n");
		else
		printf("%lld\n",f_pow(2,n/2));
	}
	if(n%2==0){
		int a[100005];
		memset(a,0,sizeof(a));
		for(int i=0;i<n;i++)
		{
			int b;
			scanf("%d",&b);
			a[b]++;
		}
		int ok=1;
		for(int i=1;i<=n;i+=2)
		if(a[i]!=2)
		ok=0;
		if(!ok)
		printf("0\n");
		else
		printf("%lld\n",f_pow(2,n/2));
	}
}


Measured memory_bytes: 1148
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>

using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = n;i >= m;i--)
#define REPO(i, n) for(int i = 1;i <= n;i++)
#define ll long long
#define INF 1999999999
#define MINF -1999999999
#define ALL(n) n.begin(),n.end()

int main() {
	string a, b;
	cin >> a >> b;
	if (a[0] == b[2] && a[1] == b[1] && a[2] == b[0]) cout << "YES" << endl;
	else cout << "NO" << endl;
}

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

int main(){
  ll n;
  cin>>n;
  int rn=sqrt(n);
  int max=1;
  for(int i=1;i<=rn;i++) if(n%i==0) max=i;
  max=n/max;
  int ans=1;
  while(max/10!=0){
    ans++;
    max/=10;
  }
  cout << ans;
}

Measured memory_bytes: 3652
#include <algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>
using ll = long long;
using namespace std;
struct work{
  ll a;
  ll b;
};
bool comp(const work &a,const work &b){
  return a.b < b.b;
}
int main(){
  ll n,ii,cost;
  vector<work> w;
  ll flg =0;
  cin >> n;

  w.resize(n);

  for(ii=0;ii<n;ii++){
    cin >> w[ii].a >> w[ii].b;
  }

  sort(w.begin(),w.end(),comp);

  cost = 0;
  for(ii=0;ii<n;ii++){
    cost += w[ii].a;
    if(cost > w[ii].b){
      flg = 1;
      break;
    }
  }

  if(flg == 0){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 3328
#include<stdio.h>
#include<algorithm>
#include<string.h>
 
using namespace std;
 
long long gcd( long long m, long long n )
{
  long long a=m, b=n, tmp, r;
if(a<b){
  tmp = a;
  a = b;
  b = tmp;
}
r = a % b;
while(r!=0){
  a = b;
  b = r;
  r = a % b;
}
  return b;
 
}
 
int main() {
  int t;
  scanf("%d", &t);
  long long A[t], B[t], C[t], D[t];
  for (int i = 0; i < t; i++) {
    scanf("%lld %lld %lld %lld", &A[i], &B[i], &C[i], &D[i]);
  }
 
  for (int i = 0; i < t; i++) {
    long long d = gcd(B[i], D[i]);
    long long cri;
    if ((C[i]-A[i])%d == 0) {
      cri = (C[i]-A[i])/d+1;
    } else {
      cri = (C[i]-A[i])/d;
    }
    if (cri > 0) cri++;
 
    if (A[i]<B[i] || D[i]<B[i]) {
      printf("No\n");
    } else if (C[i]-A[i] < cri*d && cri*d < B[i]-A[i]) {
      printf("No\n");
    } else {
      printf("Yes\n");
    }
  }
 
  return 0;
}

Measured memory_bytes: 128
N, X = map(int, input().split())
L = [1 for _ in range(N+1)]
S = [1 for _ in range(N+1)]
for n in range(1, N+1):
    L[n] = L[n-1] * 2 + 3
    S[n] = S[n-1] * 2 + 1

def rec(level, K):
    if level == 0:
        return 1
    if K == 1:
        return 0
    elif K <= L[level-1] + 1:
        return rec(level-1, K-1)
    elif K == L[level-1] + 2:
        return S[level-1] + 1
    elif K <= L[level-1] * 2 + 2:
        return rec(level-1, K - L[level-1] - 2) + S[level-1] + 1;
    else:
        return S[level-1] * 2 + 1

print(rec(N, X))


Measured memory_bytes: 9168