akhauriyash/Code-Regression huggingface dataset:
//#pragma GCC optimize ("-O3","unroll-loops")
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>


#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 SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
#define print(x) cout<<x<<'\n';
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
#define int long long
#define all(x) (x).begin(), (x).end()
//#define double long double

using namespace std;

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

const int MOD = 998244353;
const ll INF = 1e9;
const double pi = acos(-1);
const double EPS = 1e-10;
typedef pair<int, int>P;
const int MAX = 200020;

vector<double>v;
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N; cin >> N;
	v.resize(N);
	REP(i, N) {
		cin >> v[i];
	}
	VSORT(v);
	double ans = v[0] + v[1];
	ans /= 2.0;
	FOR(i, 2, N) {
		ans += v[i];
		ans /= 2.0;
	}
	cout << setprecision(10) << ans << endl;
}



Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
int sprime(int x)
{
	if(x==2)
	{
		return 1;
	}
	if(x<2||x%2==0)
	{
		return 0;
	}
	int i=3;
	while(i<=sqrt(x))
	{
		if(x%i==0)
		{
			return 0;
		}
		i+=2;
	}
		return 1;
}

int main(void)
{
  	int n=0;
	int i,j;
	scanf("%d",&n);
	int A[n];
	for(i=0;i<n;i++)
	{
		scanf("%d",&A[i]);
	}
	int count=0;
	for(i=0;i<n;i++)
	{
		if(sprime(A[i])==1)
		{
			count++;
		}
	}
	printf("%d\n",count);
  	return 0;
}


Measured memory_bytes: 2092
void main() {
	auto ip = readln.split, X = ip[0], Y = ip[1];
	if(X < Y) writeln("<");
	else if(X > Y) writeln(">");
	else writeln("=");
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.conv;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

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

// エイリアス
using  ll = long signed long;
using ull = long unsigned long;
using  ld = long double;
using   P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;

// 汎用マクロ
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOREACH(i,q) for (auto &i : q)
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
#define SZ(x) ((int)(x).size())
template <class T>inline bool chmin(T &a, const T b) {if (a > b) { a = b; return true;} return false;}
template <class T>inline bool chmax(T &a, const T b) {if (a < b) { a = b; return true;} return false;}
template <class T>inline void line_out(const vector<T> vec) {int n = SZ(vec); rep(i, n) { cout << vec[i]; if(i < n-1) cout << " ";}cout << endl;}
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 28;
const ll INF64 = 1ll << 55;
const int mod = 1000000007;
//const int mod = 998244353;
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
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint &operator++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};

int main()
{
  int h, w;
  cin >> h >> w;
  vector<string> s(h);
  rep(i, h) cin >> s[i];
  int white = 0;
  rep(i, h) rep(j, w) if(s[i][j] == '.') ++white;

  vector<vector<int>> dist(h, vector<int>(w, INF));
  queue<P> q;

  dist[0][0] = 1;
  q.push(P(0, 0));
  while(!q.empty()) {
    P now = q.front(); q.pop();
    int i = now.first, j = now.second;
    rep(k, 4) {
      int ni = i+di[k], nj = j+dj[k];
      if(ni < 0 || ni >= h || nj < 0 || nj >= w) continue;
      if(s[ni][nj] == '#') continue;
      if(chmin(dist[ni][nj], dist[i][j]+1)) {
        q.push(P(ni, nj));
      }
    }
  }

  if(dist[h-1][w-1] != INF) cout << white-dist[h-1][w-1] << endl;
  else cout << -1 << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 

ll n,cnt,ans,a[ohara],b[ohara],c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};
unordered_map<ll,ll> use;
bool vi[ohara];
int judge=0;

//-------------------------↓↓↓↓↓↓------------------------

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

    cin>>n;
    rep(i,n)cin>>a[i];
    rep(i,n)cin>>b[i];

    rrep(i,1,51)use[i]=1;

    rrrep(remove,50,1){
        use[remove]=0;
        V g[100];
        rrep(i,1,51){
            if(use[i]==0)continue;
            rrep(j,1,51){
                g[j].push_back(j%i);
            }
        }

        int ok=1;
        rep(i,n){
            rep(j,55)vi[j]=false;
            queue<ll> que;
            que.push(a[i]);

            while(!que.empty()){
                ll pa=que.front();
                que.pop();
                if(vi[pa])continue;
                vi[pa]=true;
                rep(i,Size(g[pa])){
                    ll to=g[pa][i];
                    que.push(to);
                }
            }

            if(vi[b[i]]==false){
                ok=0;
                break;
            }
        }

        if(!ok)use[remove]=1;
        else judge=1;
    }

    if(judge==0)Cout(-1);
    else{
    rep(i,51){
        if(use[i]){
            cnt=1;
            rep(j,i)cnt*=2;
            ans+=cnt;
        }
    }
    Cout(ans);
    }
    return 0;
}


Measured memory_bytes: 2304
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=1010010010010010000;
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;
}
//グリッド：（典型）dp,dfs,bfs,最短経路,その他
int main(){
    int n;cin >> n;
    string s;cin >> s;
    vi sumB(n+1),sumW(n+1);
    rep(i,n){
        if(s[i]=='#') sumB[i+1]=sumB[i]+1;
        else sumB[i+1]=sumB[i];
    }
    reverse(s.begin(),s.end());
    rep(i,n){
        if(s[i]=='.') sumW[i+1]=sumW[i]+1;
        else sumW[i+1]=sumW[i];
    }
    int ans=INF;
    for(int i=0;i<=n;i++){
        chmin(ans,sumB[i]+sumW[n-i]);
    }
    
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 2180
#include <bits/stdc++.h>
using namespace std;
#define repl(i, l, r) for (ll i = (l); i < (r); i++)
#define rep(i, n) repl(i, 0, n)
#define CST(x) cout << fixed << setprecision(x)
using ll = long long;
const ll MOD = 1000000007;
const int inf = 1e9 + 10;
const ll INF = 4e18 + 10;
const int dx[9] = {1, 0, -1, 0, 1, -1, -1, 1, 0};
const int dy[9] = {0, 1, 0, -1, 1, 1, -1, -1, 0};
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;
	int ans = 1;
	repl(i, 2, n + 1) {
		int p = i;
		rep(j, 1000) {
			p *= i;
			if (p <= n)
				ans = max(p, ans);
			else
				break;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
#define int long long int
#define nitro ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
#define pb push_back
#define PI 3.1415926535897932384626
#define MOD 1000000007
#define DEBUG false
#pragma GCC optimize "trapv"

using namespace std;
 
void dfs(vector<int> adj[],int dp[],int node,bool vis[]){
    vis[node]=true;
    for(int i=0;i<adj[node].size();i++)
    {
        if(!vis[adj[node][i]])
        dfs(adj,dp,adj[node][i],vis);
        
        dp[node]=max(dp[node],1+dp[adj[node][i]]);
    }
}
int findPath(vector<int> adj[],int n)
{
    int dp[n+1];
    memset(dp,0,sizeof(dp));
    bool vis[n+1];
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            dfs(adj,dp,i,vis);
        }
    }
    int ans=0;
    for (int i = 1; i <= n; i++) { 
        ans = max(ans, dp[i]); 
    } 
    cout<<ans;
}
 
int32_t main()
{
    nitro;
    int n,m;
    cin>>n>>m;
    vector<int> adj[n+1];
    int u,v;
    for(int i=0;i<m;i++)
    {
        cin>>u>>v;
        adj[u].pb(v);
    }
    findPath(adj,n);
return 0;
}

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

using namespace std;

struct node{
	string post;			//ポスト内容
	vector< int > chnode;	//子ノードのインデックス
	bool flg;
};

void output( vector<node> *tree, int indx, int depth ) {
	string s = "";
	s.append(depth, '.');

	if( tree -> at(indx).flg ) return;
	if( !tree -> at(indx).flg )
		cout << s << tree->at(indx).post << endl;

	tree -> at(indx).flg = true;

	if( tree->at(indx).chnode.size() > 0 )
		for(int i = 0; i < tree->at(indx).chnode.size(); i++)
			output( tree, tree->at(indx).chnode[i], depth+1);
}

int main(void){
	int n;
	cin >> n;
	
	vector< node > nlist;

	for(int i = 0; i < n; i++) {
		int k;
		string M;
		cin >> k >> M;

		node newnode;
		newnode.post = M;
		newnode.flg = false;

		if( k > 0 )
			nlist[k - 1].chnode.push_back( i );

		nlist.push_back( newnode );
	}
	output( &nlist, 0, 0 );
    return 0;
}

Measured memory_bytes: 2016
#include<stdio.h>
#include<vector>
#include<cmath>

using namespace std;

int main(){
  int n,a,i;
  const int c = pow(10,5) + 3;
  int max;

  scanf("%d", &n);
  vector<int> vi(c,0);
  for(i=0;i<n;++i){
    scanf("%d", &a);
    if(a) ++vi[a-1];
    else ++vi[0];
    --vi[a+2];
  }
  max = vi[0];
  for(i=0;i<c-1;++i){
    vi[i+1] += vi[i];
    if(max < vi[i+1]) max = vi[i+1];
  }
  printf("%d\n",max);
  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<ll,ll,ll> T;
const long long INF = 1LL<<60;
const int MOD = 1000000000+7;
#define rev(s) (string((s).rbegin(), (s).rend()))
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };
// cout << fixed << setprecision(10) << ans << endl;
// *min_element(c + l, c + r) *max_element(c + l, c + r)
// int dx[8]={1,1,0,-1,-1,-1,0,1};
// int dy[8]={0,1,1,1,0,-1,-1,-1};
// int dx[4]={1,0,-1,0};
// int dy[4]={0,1,0,-1};
// struct Edge {
//   int to, id;
//   Edge(int to, int id): to(to), id(id) {}
// };

int main() {
  int N;cin>>N;
  vector<vector<int>> happy(N,vector<int>(3,0));
  rep(i,N) cin >> happy[i][0] >> happy[i][1] >> happy[i][2];
  vector<vector<int>> dp(N + 1,vector<int>(3,0));
  rep(i,N) {
    rep(j,3) {
      chmax(dp[i + 1][(j + 1) % 3], dp[i][j] + happy[i][(j + 1) % 3]);
      chmax(dp[i + 1][(j + 2) % 3], dp[i][j] + happy[i][(j + 2) % 3]);
    }
  }
  int ans = 0;
  rep(i,3) chmax(ans, dp[N][i]);

  cout << ans << endl;
}


Measured memory_bytes: 14324
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
typedef long long ll;
 
 
int main(){
    ll n; cin>>n;
    ll ans=0;
    ans=n*(n-1)/2;
    cout<<ans<<endl;
 
}

Measured memory_bytes: 256
/* ---------- STL Libraries ---------- */

// IO library
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>
#include <random>

// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

/* ---------- Namespace ---------- */

using namespace std;

/* ---------- Type Abbreviation ---------- */

template <typename T>
using PQ = priority_queue<T>;
template <typename T>
using GPQ = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;

#define fst first
#define snd second
#define mp make_pair
#define mt make_tuple

/* ---------- conversion ---------- */

#define INT(c) static_cast<int>(c)
#define CHAR(n) static_cast<char>(n)
#define LL(n) static_cast<ll>(n)
#define DOUBLE(n) static_cast<double>(n)

/* ---------- container ---------- */

#define ALL(v) (v).begin(), (v).end()
#define SIZE(v) (LL((v).size()))

#define FIND(v, k) (v).find(k) != (v).end()
#define VFIND(v, k) find(ALL(v), k) != (v).end()

#define gsort(b, e) sort(b, e, greater<decltype(*b)>())

/* ----------- debug ---------- */

template <class T>
ostream& operator<<(ostream& os, vector<T> v) {
    os << "[";
    for (auto vv : v)
        os << vv << ",";
    return os << "]";
}

template <class T>
ostream& operator<<(ostream& os, set<T> v) {
    os << "[";
    for (auto vv : v)
        os << vv << ",";
    return os << "]";
}

template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> p) {
    return os << "(" << p.fst << "," << p.snd << ")";
}

/* ---------- Constants ---------- */

// const ll MOD = 1e9 + 7;
// const int INF = 1 << 25;
// const ll INF = 1LL << 50;
// const double PI = acos(-1);
// const double EPS = 1e-10;
// mt19937 mert(LL(time(0)));

/* ---------- Short Functions ---------- */

template <typename T>
T sq(T a) {
    return a * a;
}

template <typename T>
T gcd(T a, T b) {
    if (a > b) return gcd(b, a);
    return a == 0 ? b : gcd(b % a, a);
}

template <typename T, typename U>
T mypow(T b, U n) {
    if (n == 0) return 1;
    if (n == 1) return b /* % MOD */;
    if (n % 2 == 0) {
        return mypow(b * b /* % MOD */, n / 2);
    } else {
        return mypow(b, n - 1) * b /* % MOD */;
    }
}

ll pcnt(ll b) {
    return __builtin_popcountll(b);
}

/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */

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

    int t = b - a - 1;
    cout << t * (t + 1) / 2 - a << endl;
    return 0;
}


Measured memory_bytes: 256
s=input()
k=int(input())

if len(s)==1:
  print(k//2)
  exit()

cnt=0
i=1
while i <len(s):
  if i>0:
    if s[i]==s[i-1]:
      cnt+=1
      i+=2
    else:
      i+=1
  
if k==1:
  print(cnt)
  exit()
  
ss=s+s
cntcnt=0
i=1
while i <len(ss):
  if i>0:
    if ss[i]==ss[i-1]:
      cntcnt+=1
      i+=2
    else:
      i+=1
if k==2:
  print(cntcnt)
  exit()
  
sss=s+s+s
cntcntcnt=0
i=1
while i <len(sss):
  if i>0:
    if sss[i]==sss[i-1]:
      cntcntcnt+=1
      i+=2
    else:
      i+=1
if k==3:
  print(cntcntcnt)
  exit()
      

ssss=s+s+s+s
cntcntcntcnt=0
i=1
while i <len(ssss):
  if i>0:
    if ssss[i]==ssss[i-1]:
      cntcntcntcnt+=1
      i+=2
    else:
      i+=1
      
if k==4:
  print(cntcntcntcnt)
  exit()
  
if cntcntcntcnt-cntcntcnt==cntcntcnt-cntcnt:
  print(cntcnt+(cntcntcnt-cntcnt)*(k-2))
else:
  print(cnt-(cntcnt-cnt)*((1-k)//2)+(cntcntcnt-cntcnt)*(k-1)//2)
  


Measured memory_bytes: 3064
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;

#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define ROF(i,b,a) for (int i=(b);i>(a);--i)
#define REP(i,n) FOR(i,0,n)
#define PER(i,n) ROF(i,n-1,-1)

typedef int i32;
typedef long long int i64;
typedef unsigned long long int ui64;
typedef float f32;
typedef double f64;
typedef long double f128;
typedef pair<int,int> Pi;

constexpr int INF = 1e9 + 7;
constexpr int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};

int main() {
    int K; cin>>K;
    cout<<(K/2)*(K-K/2)<<endl;
}


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

ll val[110];
ll weight[110];
ll dp[110][100010] = {0};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	// cin >> t;
	while(t != 0) {
	    ll n, w;
        cin >> n >> w;
        ll MAX = 0;
        for(ll i = 1; i <= n; i++) {
            cin >> weight[i] >> val[i];
            MAX += val[i];
        }
        for(int j = 1; j <= MAX; j++) {
            dp[0][j] = INT_MAX;
        }
        for(ll i = 1; i <= n; i++) {
            for(ll j = 1; j <= MAX; j++) {
                dp[i][j] = dp[i-1][j];
                if(j >= val[i]) {
                    dp[i][j] = min(dp[i][j], weight[i] + dp[i-1][j-val[i]]);
                }
            }
        }
        ll ans = 0;
        // for(ll i = 0; i <= n; i++) {
        //     for(ll j = 0; j <= MAX; j++) {
        //         cout << dp[i][j] << " ";
        //     }
        //     cout << "\n";
        // }
        for(ll j = 1; j <= MAX; j++) {
            if(dp[n][j] <= w) {
                ans = j;
            }
        }
        cout << ans << "\n";
	    t--;
	}
	return 0;
}


Measured memory_bytes: 80128
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;

ll inf=9223372036854775806;

int main()
{
	//freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll i,n,s1=0,s2=0,ans=inf;
	string a;
	cin>>n>>a;
	for (i=0;i<a.size();i++){
		if (a[i]=='E'){
			s1++;
		}
	}
	for (i=0;i<a.size();i++){
		if (a[i]=='W'){
			ans=min(ans,s1+s2);
			s2++;
		}
		else {
			ans=min(ans,s1+s2-1);
			s1--;
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 720
#include <iostream>
#include <algorithm>
using namespace std;
signed main() {
	int a, b, x; cin >> a >> b >> x;
	a = min(a, b * 2);
	if (x % 500)x += 500 - (x % 500);
	cout << (x / 1000)*a + (x % 1000) / 500 * min(a, b) << endl;
}


Measured memory_bytes: 3124
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;

int N,M;
vector<vector<int> > G(101010);
const int B=0,W=1;
int color[101010];

void dfs(int v, int col){
  color[v]=col;
  rep(i,G[v].size()){
    if(color[G[v][i]]==-1) dfs(G[v][i],(col+1)%2);
  }
}

int check(){
  rep(i,N) rep(j,G[i].size()){
    if(color[i]==color[G[i][j]]) return 0;
  }
  return 1;
}

int main(){
  fill(color,color+101010,-1);
  cin>>N>>M;
  rep(i,M){
    int a,b; cin>>a>>b; a--,b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  dfs(0,B);
  if(check()){
    int cnt=0;
    rep(i,N) cnt+=color[i];
    cout<<1LL*cnt*(N-cnt)-M<<endl;
  }else{
    cout<<1LL*N*(N-1)/2-M<<endl;
  }
  return 0;
}


Measured memory_bytes: 6656
#include<iostream>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
const long long int mod1=1000000007;
const long long int mod2 = -1;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define pp pop_back                                       
#define ff first
#define ss second
#define ll long long int
#define ull unsigned long long int
#define ordered_set tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define ordered1 tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define inf mod1
ll gcd(ll a, ll b){
    ll c;
     while(b){
        c = b;
        b = a % b;
        a = c;
     }
     return a;
}
ll power1(ll a, ll b){
     if(b == 0) return 1;
     else if(b % 2) return a * power1(a, b - 1);
     else {
        ll temp = power1(a, b / 2);
        return temp * temp;
     }
}
ll power2(ll a, ll b, ll m){
     a %= m;
     if(b == 0) return 1;
     else if(b % 2) return (a * power2(a, b - 1, m)) % m;
     else{
        ll temp = power2(a, b / 2, m);
        return (temp * temp) % m;
     }
}
ll mod(ll x, ll p){
return (x % p + p) % p;
}
ll lcm(ll x, ll y){
return (x * y)/gcd(x, y);
}
int main(){
	fast;
	ll h = 1;
	//cin >> h;
    while(h--){
       ll n, m1;
       cin >> n >> m1;
       bool b[n] = {};
       map<ll,ll> m;
       for(int i = 0; i < m1; i++){
        ll p; string s;
        cin >> p >> s;
        if(b[p - 1]){

        }
        else{
            if(s == "AC"){
                b[p - 1] = 1;
            }
            else{
                if(!m.count(p - 1)){
                    m.insert({p - 1, 1});
                }
                else{
                    m[p - 1] ++;
                }
            }
        }
       }
       ll solv = 0;
       ll pen = 0;
       for(auto x : m){
         if(b[x.ff]){
            pen += x.ss;
         }
       }
       for(int i = 0; i < n; i++){
        if(b[i]){
            solv++;
        }
       }
       cout << solv << " " << pen << endl;
   }
}

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

int main() {
	int n,m,X,Y;cin>>n>>m>>X>>Y;
	vector<int> x(n),y(m);
	for(int i=0;i<n;i++){
		cin>>x[i];
	}
	x.push_back(X);
	for(int i=0;i<m;i++){
		cin>>y[i];
	}
	y.push_back(Y);
	sort(x.begin(),x.end());
	sort(y.begin(),y.end());
	if(x[n]<y[0]){
		cout<<"No War"<<endl;
	}else{
		cout<<"War"<<endl;
	}
	return 0;
}

Measured memory_bytes: 384
def m():
    n = int(input())
    i=1
    div = []
    while i*i <= n:
        if n % i == 0:
            div.append(i)
        i+=1
    a = max(div)
    b = n // a
    d = max(a,b)
    return len(str(d))

print(m())

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {

	public static int a = 0;

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String row = scan.next();
		if((row.equalsIgnoreCase("aaa"))||(row.equalsIgnoreCase("bbb"))) {
		    System.out.println("No");
		}
		else {
		    System.out.println("Yes");
		}
	}

}


Measured memory_bytes: 22868
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s,pre,tmp;
int main(){
    ios::sync_with_stdio(false);
    cin>>s;
    int ans = 0 ;
    for(int i=0;i<s.length();i++){
        tmp+=s[i];
        if(tmp!=pre){
            pre=tmp;
            ans++;
            tmp="";
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 720
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<endl;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b){ a = b; return 1; } return 0; }



int main(int argc, char const *argv[]) {
    int a,b,c,k; cin >> a >> b>> c >> k;
    ll ans = 0;
    ans += min(a, k);
    k -= min(a, k);
    if(k>0){
      k -= b;
      if(k>0){
        ans -= min(k, c);
      }

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


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

#define DEBUG(x) cout << '>' << #x << ':' << x  ;
#define mem(x,val) memset((x),(val),sizeof(x))
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define PI acos(-1.0) 
#define MAXN 11111

const int INF = 1 << 29 ;
typedef long long ll ;
typedef pair < int , int > pii ;

int main() {
    int a[10] ;
    for(int i = 0 ; i<4 ;i++) scanf("%1d" , &a[i]) ;
    if(a[0]+a[1]+a[2]+a[3] == 7)
        cout << a[0]<<'+' << a[1] << '+' << a[2] << '+' << a[3] ;
    else if(a[0]- a[1] + a[2] + a[3] == 7) 
        cout <<a[0] << '-' << a[1] << '+' << a[2] << '+' << a[3]   ;
    else if(a[0] + a[1] - a[2] + a[3] == 7) 
        cout << a[0] << '+' << a[1] << '-' << a[2] << '+' << a[3]   ;
    else if(a[0] - a[1] - a[2] + a[3] == 7) 
        cout <<a[0] << '-' << a[1] << '-' << a[2] << '+' << a[3]   ;
    else if(a[0] - a[1] + a[2] - a[3] == 7) 
        printf("%d-%d+%d-%d" , a[0] , a[1] , a[2] , a[3]) ;
    else if(a[0] - a[1] - a[2] - a[3] == 7) 
        printf("%d-%d-%d-%d", a[0] , a[1] , a[2] , a[3]) ;
    else if(a[0]+ a[1] + a[2]-a[3] == 7) 
        printf("%d+%d+%d-%d" , a[0] , a[1] , a[2] , a[3]) ;
    else printf("%d+%d-%d-%d" , a[0] , a[1] , a[2] , a[3]) ;
    printf("=7\n") ;

    return 0 ;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;
//const int mod = 998244353;

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

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int num = i * 108 / 100;
        if (num == n)
        {
            cout << i << endl;
            return 0;
        }
    }
    cout << ":(" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
#define drep(i,cc,n) for(int i=cc;i>=n;--i)
typedef long long ll;
using namespace std;
int main(){
    int n;
    cin>>n;
    int x[n];
    rep(i,0,n-1) cin>>x[i];
    ll min=1000000000;
    ll hoge = 0;
    sort(x,x+n);
    rep(i,1,x[n-1]){
        hoge = 0;
        rep(j,0,n-1){
            hoge += (x[j]-i)*(x[j]-i);
        }
        if(min>hoge){
            min = hoge;
        }
    }
    cout<<min<<endl;
    return 0;
}

Measured memory_bytes: 256
import sys
input=sys.stdin.readline
h,w,n=map(int,input().split())
sx,sy=map(int,input().split())
S=input(); T=input()
u,d=1,h; l,r=1,w
ans='YES'
for i in reversed(range(n)):
    if T[i]=='U':
        d=min(h,d+1)
    if T[i]=='D':
        u=max(1,u-1)
    if T[i]=='L':
        r=min(w,r+1)
    if T[i]=='R':
        l=max(1,l-1)
    if S[i]=='U':
        u+=1
        if u==h+1:
            print('NO')
            break
    if S[i]=='D':
        d-=1
        if d==0:
            print('NO')
            break
    if S[i]=='L':
        l+=1
        if l==w+1:
            print('NO')
            break
    if S[i]=='R':
        r-=1
        if r==0:
            print('NO')
            break
    if r<l or d<u:
        print('NO')
        break
else:
    if sx<u or sx>d or sy<l or sy>r:
        print('NO')
    else:
        print('YES')

Measured memory_bytes: 50156
/*
    Author: Alam Khan
    AUST CSE 40th Batch

*/

#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef deque<ll> dl;
typedef stack<ll> stl;
typedef set<ll> sl;
typedef map<string, ll> msl;
typedef map<ll,ll> mll;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
#define sf(n)     scanf("%lld",&n)
#define sff(n,m)     scanf("%lld %lld",&n,&m)
#define sfff(n,m,r)     scanf("%lld %lld %lld",&n,&m,&r)
#define sfs(n)     scanf("%s",n)
#define pf(n)     printf("%lld\n",n)
#define pff(n,m)     printf("%lld %lld\n",n,m)
#define pfff(n,m,r)     printf("%lld %lld %lld\n",n,m,r)
#define pfs(n)     printf("%s\n",n)
#define pfcs(i,n)     printf("Case %lld: %lld\n",i,n)
#define pb     push_back
#define prf     printf
#define inf     2e11
#define low     -1000000000000
#define PI        acos(-1.0)
#define rep1(i,n) for(i=1;i<n;i++)
#define rep0(i,n) for(i=0;i<n;i++)
#define rep(i,a,n) for(i=a;i<n;i++)
#define repe1(i,n) for(i=1;i<=n;i++)
#define repe0(i,n) for(i=0;i<=n;i++)
#define repe(i,a,n) for(i=a;i<=n;i++)
#define endl  "\n"
#define FAST  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define fr freopen("input.txt","r",stdin)
#define fw freopen("output.txt","w",stdout)
map<ll,ll> ma;
map<ll,ll> :: iterator it;
ll bitDiff(ll A,ll B)
{
    ll cnt = 0;
    for (ll i = 0; i < 32; i++)
    {
        if (((A >> i) & 1LL) != ((B >> i) & 1LL))
            cnt++;

    }
    return cnt;
}
ll dp[1009][5009];
ll key[1009];
ll cost[1009];
ll n,m;
ll sol(ll keyno,ll mask)
{
    if(dp[keyno][mask]!=-1)
    {
        return dp[keyno][mask];
    }
    if(keyno==m)
    {
        if(mask==(1<<n)-1)
            return dp[keyno][mask] =0;
        return dp[keyno][mask] =inf;
    }
    ll res = inf;
    if(bitDiff(mask,key[keyno])!=0)
    {
        res = min(res,cost[keyno]+sol(keyno+1,mask | key[keyno]));
    }
    res = min(res,sol(keyno+1,mask));

    return dp[keyno][mask] = res;
}
int main()
{
    ll i,t,k,j,x=0,y=0;
    FAST
    cin>>n>>m;

    for(i=0;i<m;i++)
    {
        ll cnt;
        cin>>cost[i]>>cnt;
        k = 0;
        while(cnt--)
        {
            cin>>x;
            k  =k| (1<<(x-1));
        }
        key[i] = k;

    }
    memset(dp,-1,sizeof dp);
    x = sol(0,0);
    if(x>=inf)
        cout<<-1<<endl;
    else cout<<x<<endl;

    return 0;
}



Measured memory_bytes: 43156
#include<stdio.h>
int main(void)
{
	int i,j,N,v[50],a;
	float sum=0.0;
	scanf("\n%d",&N);
	for (i=0;i<N;i++)
	{
	scanf("%d",&v[i]);
	}

	for (i=0;i<N-1;i++) 
	{
		for(j=0;j<N-i-1;j++)
		{
			if( v[j]>v[j+1] )
			{	a=v[j];
				v[j] = v[j+1];
				v[j+1]=a;
			}
		}
	}

        sum= (float) v[0]/2+(float)v[1]/2;
	if(N>2)
	{
	for(i=2;i<N;i++)
	{
		sum = sum/2 + (float)v[i]/2;
	}
	}
	printf("\n%f",sum);
	return 0;
}




Measured memory_bytes: 128
using System;

namespace _044_PrimeNumberII
{
	class Program
	{
		static void Main ( string[] args )
		{
			string inputStr;

			while ((inputStr = Console.ReadLine ()) != null)
			{
				int inputNum = int.Parse (inputStr);

				int number = inputNum - 1;

				while (!IsPrimeNumber (number))
				{
					number--;
				}

				Console.Write (number + " ");

				number = inputNum + 1;

				while (!IsPrimeNumber (number))
				{
					number++;
				}

				Console.WriteLine (number);
			}
		}

		static bool IsPrimeNumber ( int number )
		{
			if (number == 2)
			{
				return true;
			}

			bool isEven = number % 2 == 0;

			if (isEven)
			{
				return false;
			}

			int lp = 3;
			while (lp <= Math.Sqrt (number))
			{
				if (number % lp == 0)
				{
					return false;
				}

				lp += 2;
			}

			return true;
		}
	}
}

Measured memory_bytes: 9180
//
// Created by hans on 17/01/28.
//

#include <iostream>
using namespace std;
int N,A[100001]={},tmp;

int main() {
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> tmp;
        A[tmp]++;
    }
    int ans=0;
    for(int i=0;i<100001;i++){
        if(A[i]>1){
            ans+=(A[i]-1);
        }
    }

    cout << N-((ans%2==0)?(ans):(ans+1)) << endl;


    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
 using namespace std;
 typedef long long ll;
 #define rep(i, j, n) for(int i = j; i < (int)(n); i++)
 const ll MOD = 1000000007;
 const ll INF = 1LL << 60;

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

   vector<ll> a(N + 1), b(N + 1), c(N + 1);
   vector<vector<ll>> happy(3, vector<ll>(N + 1, 0));

   rep(i, 1, N + 1) cin >> a.at(i) >> b.at(i) >> c.at(i);

   happy.at(0).at(1) = a.at(1);
   happy.at(1).at(1) = b.at(1);
   happy.at(2).at(1) = c.at(1);

   rep(i, 2, N + 1) {
     happy.at(0).at(i) = max(happy.at(1).at(i - 1), happy.at(2).at(i - 1)) + a.at(i);
     happy.at(1).at(i) = max(happy.at(2).at(i - 1), happy.at(0).at(i - 1)) + b.at(i);
     happy.at(2).at(i) = max(happy.at(0).at(i - 1), happy.at(1).at(i - 1)) + c.at(i);
   }

   cout << max(happy.at(0).at(N), max(happy.at(1).at(N), happy.at(2).at(N))) << endl;
 }


Measured memory_bytes: 5760
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdlib>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C) (C).begin(),(C).end()
#define pb push_back

const int N = 401;
int len[N];
vector<vector<int> > path;

bool chlen(int val,int now,int *in,bool flag){
  bool ret=true;
  rep(i,now){
    int tmp=abs(val-in[i]);
    if(flag)len[tmp]++;
    else len[tmp]--;
    if (!flag&&len[tmp] < 0)ret=false;
  }

  if (!ret){
    rep(i,now){
      len[abs(val-in[i])]++;
    }
  }
  return ret;
}

bool canput(int val,int now,int *in){
  return chlen(val,now,in,false);
}

int buf[20];
const int sign[2]={1,-1};
void search(int n,int now,int *pos,int p){
  if (n == now){
    vector<int> tmp;
    rep(i,n)buf[i]=pos[i];
    sort(buf,buf+n);
    rep(i,n-1){
      tmp.pb(buf[i+1]-buf[i]);
    }
    path.pb(tmp);
    return ;
  }
  //rep(i,now)cout << pos[i] <<" ";cout << endl;
  
  while(p>0 && len[p]==0)p--;
  rep(k,2){
    rep(i,now){
      bool isok=true;
      int val=pos[i]+sign[k]*p;
      if (val > pos[1] || val <0)continue;
      rep(j,now){
	if (i!=j && pos[j] ==val){isok=false;break;}
	//if(pos[i] < pos[j] < val continue;for prune
      }
      //cout << pos[i]<<" " << sign[k]*p << " " << val <<" " << isok << endl;

      if (!isok)continue;
      if (canput(val,now,pos)){
	pos[now]=val;
	search(n,now+1,pos,p);
	chlen(val,now,pos,true);
      }
    }
  }
}

main(){
  int n;
  int pos[20];
  while(cin>>n && n){
    rep(i,N)len[i]=0;
    path.clear();
    int maxi=0;
    rep(i,n){
      REP(j,i+1,n){
	int tmp;cin>>tmp;len[tmp]++;maxi=max(maxi,tmp);
      }
    }
    pos[0]=0;
    pos[1]=maxi;
    len[maxi]--;

    search(n,2,pos,maxi);
    sort(ALL(path));
    //cout <<"before "<< path.size() << endl;
    path.erase(unique(ALL(path)),path.end());
    //cout <<"after "<< path.size() << endl;
    rep(i,path.size()){
      rep(j,path[i].size()){
	if (j)cout << " ";
	cout << path[i][j];
      }
      cout << endl;
    }
    cout << "-----"<<endl;
  }
  return false;
}

Measured memory_bytes: 0
use std::io::{stdin, Read};

macro_rules! parse {
    ($it: ident) => {
        $it.next().unwrap().parse().unwrap()
    };
    ($it: ident,2) => {
        (parse!($it), parse!($it))
    };
    ($it: ident,3) => {
        (parse!($it), parse!($it), parse!($it))
    };
    ($it: ident,4) => {
        (parse!($it), parse!($it), parse!($it), parse!($it))
    };
    ($it: ident, $n: expr) => {
        (&mut $it).take($n).map(|e| e.parse().unwrap()).collect();
    };
}

fn solve(s: &str) {
    let mut it = s.split_whitespace();
    let (n, m): (usize, usize) = parse!(it, 2);
    let mut a: Vec<usize> = parse!(it, n);
    a.sort();
    a.reverse();
    let s: usize = a.iter().sum();
    let t = s / (4 * m) + if s % (4 * m) == 0 { 0 } else { 1 };
    if a[m - 1] < t {
        println!("{}", "No");
    } else {
        println!("{}", "Yes");
    }
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    solve(&s);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_input() {
        let s = "
        ";
        solve(s);
    }
}


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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int h[] = new int[N+1];
		long dp[] = new long[N+1];
		for (int i = 1; i <= N; i++) {
			h[i] = sc.nextInt();
		}

		Arrays.fill(dp,1,N + 1, Integer.MAX_VALUE);
		dp[1] = 0;

		for (int i = 1; i < N; i++){
			for (int j = 1; j <= K; j++) {
				if (i <= N-j) {
					dp[i + j] = Math.min(dp[i + j], dp[i] + Math.abs(h[i] - h[i + j]));
				}
			}
//			dp[i + 1] = Math.min(dp[i + 1], dp[i] + Math.abs(h[i] - h[i + 1]));
		}
	  System.out.println(dp[N]);

	}
}


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

int A,B,C;


int main(void){
    cin >> A >> B >> C;
    int cnt = 0;
    int divisor = min(A,B);
    while(true){
        if(A%divisor==0 && B%divisor==0) cnt++;
        if(C<=cnt) break;
        divisor--;
    }

    cout << divisor << endl;
    return 0;
}

Measured memory_bytes: 256
function main(input) {
  const N = input.split("\n")[0];
  var nums = input.split('\n')[1].split(' ').map((n) => parseInt(n, 10));
  
var ans=1;

for(var i=1; i<N; i++){
  var temp=0;
  for(var j=0; j<i; j++){
    if(nums[j]<=nums[i]){
      temp++
    }
  }
  if(temp==i){
    ans++
  }
}

console.log(ans);

}


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


Measured memory_bytes: 7372
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
#define rep(i,n)for(int i=0;i<n;i++)
#define int long long
#define ggr getchar();getchar();return 0;
#define prique priority_queue
#define mod 1000000007
#define inf 1e15
#define key 1e9
using namespace std;
typedef pair<int, int>P;
void yes() { cout << "Yay!" << endl; }
void no() { cout << ":(" << endl; }
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y)* mod_pow(kai(y, y), mod - 2, mod) % mod;
}
struct edge { int to, cost; };
map<int, int>mp;
int n, q;
int a[114514];
int l[114514], r[114514];
signed main() {
	cin >> n >> q;
	rep(i, n)cin >> a[i];
	rep(i, q)cin >> l[i] >> r[i];
	sort(a, a + n);
	rep(i, q) {
		int p = upper_bound(a, a + n, r[i]) - a - 1;
		int q = lower_bound(a, a + n, l[i]) - a - 1;
		cout << p - q << endl;
	}
	ggr
}




Measured memory_bytes: 5504
s=input()
s=s.replace("RL","P")
ans=[]
cr=0
cl=0

import math
for i in s:
    if i=="R":
        ans.append(0)
        cr+=1
    elif i=="L":
        ans.append(0)
    else:
        ans.append(1+cr//2)
        ans.append(1+math.ceil(cr/2))
        cr=0
k=0

for i in range(1,1+len(s)):
    if s[-i]=="L":
        cl+=1
    elif s[-i]=="P":
        ans[-i-k]+=cl//2
        k+=1
        ans[-i-k]+=math.ceil(cl/2)
        cl=0

for i in range(len(ans)):
    if i!=len(ans)-1:
        print(ans[i],end=" ")
    else:
        print(ans[i])

Measured memory_bytes: 4900
#include<stdio.h>
int count = 0;
int L[500000];
int R[500000];

void merge(int *A,int left ,int mid ,int right){
int n1,n2,i,j,k;

n1 = mid - left;
n2 = right - mid;

for(i=0;i < n1; i++){
L[i] = A[left + i];
}
for(i=0;i < n2; i++){
R[i] = A[mid + i];
}

L[n1] = 1000000000;
R[n2] = 1000000000;

i=0;
j=0;

for(k = left ; k < right ; k++){

if(L[i]<= R[j]){
A[k]=L[i];
i = i+1;
count++;
}
else{
    A[k]=R[j];
    j=j+1;
count++;
}

}
}

void mergeSort(int *A,int left ,int right){
    int mid;
if((left + 1) < right){
 mid = (left + right) / 2;
  mergeSort(A,left,mid);
  mergeSort(A,mid,right);
  merge(A,left,mid ,right);

}

}
int main(){

int n,i,left,right;
int S[500000];

scanf("%d",&n);

for(i = 0;i < n;i++){

    scanf("%d",&S[i]);
}
left = 0;
right = n;

mergeSort(S,left,right);


for(i = 0;i < n;i++){

printf("%d",S[i]);

if(i+1 != n)
printf(" ");
}
printf("\n%d\n",count);
return 0;
}


Measured memory_bytes: 5632
n = int(input())

a = []


def func(s):
    if s:
        a.append(int(s))
    if len(s) == len(str(n)):
        return
    func(s + '3')
    func(s + '5')
    func(s + '7')


func('')

print(len([x for x in a if x <= n and len(set(str(x))) == 3]))


Measured memory_bytes: 4492
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		ScannerModule sm = new ScannerModule();
		int input_a = sm.scanInt();
		int input_b = sm.scanInt();
		int seki = input_a * input_b;
		if(seki % 2 == 0) {
			System.out.println("Even");
		}
		else {
			System.out.println("Odd");
		}
	}
}

class ScannerModule {
	Scanner scanner = new Scanner(System.in);
	int scanInt() {
		return scanner.nextInt();
	}
	String scanString() {
		return scanner.next();
	}
}

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

int main()
{
  int n;
  string s;
  cin >>n >> s;
  char str[100];
  int flag = 0;
  for(int i = 0 ;i < (n/2); i++)
  {
    if(n%2 == 1)break;
    str[i] = s[i];
    if(str[i] == s[(n/2) + i])flag = 1;
    else
    {
      flag = 0;
      break;
    }
  }
  if(flag == 1)cout << "Yes" << endl;
  else cout << "No" << endl;
 
  return 0;
}


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

int main() {
  string s;
  int K;
  cin >> s>>K;
  int n=s.size();


  long ans1=0;
  int tmp1=999;
  string jtd1=s;
  for(int i=0;i<n-1;i++){
    if(jtd1[i]==jtd1[i+1]) {
      ans1++;
      jtd1[i+1]= tmp1%10;
      tmp1 --;
  }
}
if(K==1){
  cout<<ans1<<endl;
  return 0;
}

long ans2=0;
int tmp2=999;
string jtd2 = s+s;
int n2=jtd2.size();
for(int i=0;i<n2-1;i++){
  if(jtd2[i]==jtd2[i+1]) {
    ans2++;
    jtd2[i+1]= tmp2%10;
    tmp2 --;
}
}

if(K==2){
  cout<<ans2<<endl;
  return 0;
}

long ans3=0;
int tmp3=999;
string jtd3 = s+s+s;
int n3=jtd3.size();
for(int i=0;i<n3-1;i++){
  if(jtd3[i]==jtd3[i+1]) {
    ans3++;
    jtd3[i+1]= tmp3%10;
    tmp3 --;
}
}

if(K==3){
  cout<<ans3<<endl;
  return 0;
}

long ans4=0;
int tmp4=999;
string jtd4 = s+s+s+s;
int n4=jtd4.size();
for(int i=0;i<n4-1;i++){
  if(jtd4[i]==jtd4[i+1]) {
    ans4++;
    jtd4[i+1]= tmp4%10;
    tmp4 --;
}
}

if(K==4){
  cout<<ans4<<endl;
  return 0;
}

long d1 = ans2-ans1;
long d2 = ans3-ans2;
long d3 = ans4-ans3;

if(d1==d2) cout<<(ans2-ans1)*(K-1)+ans1<<endl;
else{
  if(K%2==1){
  long m1=d1*((K)/2);
  long m2=d2*((K)/2);
  //cout<<m1<<endl;
  //cout<<m2<<endl;
  long tans=m1+m2+ans1;
  cout<<tans<<endl;
}
else{
  long m1=d1*((K)/2);
  long m2=d2*((K-1)/2);
  //cout<<m1<<endl;
  //ut<<m2<<endl;
  long tans=m1+m2+ans1;
  cout<<tans<<endl;
}

}


}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define lld long long
#define N 200005
#define INF 1e18
#define INF2 1e16
#define mod 998244353
lld power(lld a,lld b,lld c){
  lld ans=1;
  while(b){
    if(b&1){
      ans=ans*a%mod;
    }
    a=a*a%mod;
    b=b/2;
  }
  return ans;
}
vector<string> ans;
void f(int n,int ind,string s)
{
	if(n==0){
		ans.push_back(s);
		return;
	}
	for(int i=0;i<ind;++i)
	{
		string b=s;
		char cc=(char)(97+i);
		b.push_back(cc);
		f(n-1,ind,b);
	}
	char cc=(char)(97+ind);
	string pp=s;
	pp.push_back(cc);
	f(n-1,ind+1,pp);	
}
int main() {
int n; cin>>n;
string s="";
f(n,0,s);
sort(ans.begin(),ans.end());
for(int i=0;i<ans.size();++i)cout<<ans[i]<<endl;
}

Measured memory_bytes: 7796
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    String X = sc.next();
    sc.nextLine();
    int[] coordinates = Arrays.stream((X + " " + sc.nextLine()).split(" "))
      .mapToInt(Integer::parseInt)
      .sorted()
      .toArray();
    Set<Integer> distanceSet = new HashSet<>();
    for (int i = 0; i < coordinates.length-1; i++) {
      distanceSet.add(Math.abs(coordinates[i] - coordinates[i+1]));
    }
    int minGCD = 0;
    int preDistance = 0;
    for (Integer curDistance : distanceSet) {
      if (preDistance == 0) {
        minGCD = curDistance;
        preDistance = curDistance;
        continue;
      }
      minGCD = Math.min(minGCD, getGCD(curDistance,preDistance));
      if (minGCD == 1) break;
    }
    System.out.println(minGCD);
  }
  private static int getGCD(int a, int b) {
    if (a < b) {int t = a; a = b; b = t;}
    if (b < 1) return -1;
    if (a%b == 0) return b;
    return getGCD(b, a%b);
  }
}

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

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

typedef long long LL;

int main(){
  string s;
  cin >> s;
  if(s.length()<4){
    cout << "No" << endl;
    return 0;
  }
  if(s[0]=='Y'&&s[1]=='A'&&s[2]=='K'&&s[3]=='I'){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/range/adaptor/reversed.hpp>

using namespace std;
typedef long long int ll;

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

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define dumparr(x) cerr << #x ; for(auto elem: x){cerr << " " << elem;} cerr << endl;
#define dumppairs(x) cerr << #x ; for(auto elem: x){cerr << "(" << elem.first << " " << elem.second << ") ";} cerr << endl;
#define dumpline cerr << "**********************" << endl;
#define dumpwline(x) cerr << "******** " << #x << "=" << (x) << " ********" << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

int main(void){
    int n; cin >> n;
    unordered_map <string, ll> cnt;
    REP(i, n){
        string s; cin >> s;
        sort(s.begin(), s.end());
        cnt[s]++;
    }
    ll ans = 0;
    for(auto c: cnt){
        ans += c.second*(c.second-1)/2;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 10660
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=0;(i)<(n);i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define MOD 1000000007
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define ALL(v) v.begin(), v.end()
typedef long long ll;


int main(){

int n;
cin >> n;

string s;
cin >> s;

int count=0;

for(int i=0;i<n-1;i++){
    if(s.at(i)!=s.at(i+1)){
        count++;
    }
}

cout << count +1 << endl;
return 0;
}



Measured memory_bytes: 512