akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
struct UnionFind {
	vector<int> data;
	UnionFind(int n) : data(n, -1) {}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	bool merge(int x, int y) {
		x = root(x);
		y = root(y);
		if (x == y) return false;
		if (data[y] < data[x]) swap(x, y);
		data[x] += data[y];
		data[y] = x;
		return true;
	}
	int size(int x) {
		return -data[root(x)];
	}
};
int main() {
	int N, M;
	cin >> N >> M;
	vector<int> A(N);
	for (auto& x : A) cin >> x;
	UnionFind uf(N);
	for (int i = 0; i < M; ++ i) {
		int u, v;
		cin >> u >> v;
		uf.merge(u, v);
	}

	if (uf.size(0) == N) {
		cout << 0 << endl;
		return 0;
	}

	vector<priority_queue<int>> V(N);
	for (int i = 0; i < N; ++ i) {
		V[uf.root(i)].push(-A[i]);
	}
	long long r = 0;
	priority_queue<int> Q;
	int n = 0;
	for (int i = 0; i < N; ++ i) if (!V[i].empty()) {
		auto& q = V[i];
		r += -q.top(); q.pop();
		++ n;
		while (!q.empty()) {
			Q.push(q.top()); q.pop();
		}
	}
	if ((int)Q.size() < n-2) {
		cout << "Impossible" << endl;
	} else {
		for (int i = 0; i < n-2; ++ i) {
			r += -Q.top(); Q.pop();
		}
		cout << r << endl;
	}
}


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

int Time[10000][1300];
int last[10000][1000];
int N, M;
int r, q;
int t, n, m, s, ts, te, ans;

int main() {
  while(cin >> N >> M){
    if(N==0) break;
    memset(Time, 0, sizeof(Time));
    memset(last, 0, sizeof(last));

    cin >> r;
    rep(i, r){
      cin >> t >> n >> m >> s;
      n--; m--;
      if(s==1) last[m][n] = t;
      else REP(j, last[m][n], t) Time[m][j] = 1;
    }
    cin >> q;
    rep(i, q){
      ans = 0;
      cin >> ts >> te >> m;
      m--;
      REP(j, ts, te) ans += Time[m][j];
      cout << ans << endl;
    }
  }
  return 0;
}


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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ll << (b))
#define uniq(v) (v).erase(unique(all(v)), (v).end())

using namespace std;

using i32 = int;
using i64 = long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "-1" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { if (x < y) x = y; }
template <typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template <typename T> inline T power(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, const vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }

void solve() {
  int N, A, B;
  cin >> N >> A >> B;
  if (N - A + 1 < B || (N + A - 1) / A > B) no();
  vi32 ans(N);
  {
    int j = 0;
    for (int i = N - A + 1; i <= N; i++) {
      ans[j++] = i;
    }
    function<void(int, int, int)> crt = [&](int j, int R, int G) {
      if (R == G) {
        for (int i = R; i >= 1; i--) {
          ans[j++] = i;
        }
        return;
      }
      if (R - A < G - 1) {
        for (int i = G; i <= R; i++) {
          ans[j++] = i;
        }
        crt(j, G - 1, G - 1);
      } else {
        for (int i = R - A + 1; i <= R; i++) {
          ans[j++] = i;
        }
        crt(j, R - A, G - 1);
      }
    };
    crt(j, N - A, B - 1);
    cout << ans << '\n';
  }
}


Measured memory_bytes: 4480
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

int main() {
  string s; cin >> s;
  int d = s.size();
  int n[d];
  for (int i = 0; i < d; i++) n[i] = s[i] - '0';
  int k; cin >> k;

  int c = 1;
  int dp[d][k+1] = {};
  dp[0][0] = 1;
  dp[0][1] = n[0] - 1;
  for (int i = 1; i < d; i++) {
    dp[i][0] = 1;
    for (int j = 1; j <= k; j++) {
      dp[i][j] = dp[i-1][j-1] * 9 + dp[i-1][j];
    }
    if (n[i] > 0) {
      if (c <= k) dp[i][c] += 1;
      c++;
      if (c <= k) dp[i][c] += n[i] - 1;
    }
  }
  if (c == k) dp[d-1][k]++;

  cout << dp[d-1][k] << endl;
}

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

using namespace std;

int main(){
        int n,k,ans = 0;
        cin >> n >> k;

        int p[n];

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

        sort(p,p+n);

        for (int i = 0; i< k;i++){
                ans += p[i];
        }
        cout << ans << endl;

}

Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int arr[3][3] = {0};
    for(int i = 0;i < 3;i++)
        for(int j = 0;j < 3;j++)cin >> arr[i][j];
    int n;cin >> n;
    int ar[n];
    int k=n,cnt = 0;
    for(int i = 0;i < n;i++)cin >> ar[i];
    while(k--)
    {
        for(int i = 0;i < n;i++)
            for(int j = 0;j < n;j++)
                if(arr[i][j] == ar[k])arr[i][j] = 0;
    }
    for(int i = 0;i < 3;i++)
    {
        for(int j = 0;j < 3;j++)
        {
            if(arr[i][j] == 0)cnt++;
        }
        if(cnt == 3)
        {
            cout << "Yes" << endl;
            return 0;
        }
        else cnt = 0;
    }
    for(int i = 0;i < 3;i++)
    {
        for(int j = 0;j < 3;j++)
        {
            if(arr[j][i] == 0)cnt++;
        }
        if(cnt == 3)
        {
            cout << "Yes" << endl;
            return  0;
        }
        else cnt = 0;
    }
    if(arr[0][0] == 0 && arr[1][1] == 0 && arr[2][2] == 0)cout << "Yes" << endl;
    else if(arr[2][0] == 0 && arr[1][1] == 0 && arr[0][2] == 0)cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
  }


Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <complex>
#include <cstdint>
#include <tuple>
#include <numeric>
#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(); }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
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 MT make_tuple
#define SZ(a) int((a).size())
#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())
#define FILL(a, x) memset(a, x, sizeof(a))

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

int main() {
	int n;
	cin >> n;
	int ma = -1;
	int ret = 0;
	REP(i, n) {
		int x;
		cin >> x;
		if (x >= ma) {
			ret++;
			ma = x;
		}
	}
	cout << ret << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(I,X,Y) for(long long (I)=(X);(I)<(Y);(I)++)
#define REP(I,X,Y) for(long long (I)=(Y)-1;(I)>=(X);(I)--)
#define ALL(X) (X).begin(),(X).end()
#define pb push_back
#define COUNT(V,X) upper_bound((V).begin(),(V).end(),X)-lower_bound((V).begin(),(V).end(),X)
#define debug(x0123456789) cerr<<#x0123456789<<':'<<x0123456789<<endl;
#define DEBUG(v) cerr<<#v<<':';for(auto x0123456789:v)cerr<<x0123456789<<' ';cerr<<endl;
#define INF 1000000007
#define LINF 1000000000000000007
#define EPS 1e-9
typedef long long ll;
typedef long double ld;

signed main(){
    int D;
    cin >> D;
    cout << "Christmas";
    FOR(i,0,25-D)cout << " Eve";
    cout << endl;
}

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

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int n;
  cin>>n;
  int a[10]={1,2,4,8,16,32,64,128,256,512};
  int f=0;
  for(int i=0;i<10;i++){
    if(a[i]<=n){
      f=a[i];
    }
  }
  cout<<f;
}



Measured memory_bytes: 256
n=int(input())
l=list(map(int,input().split()))
col=[False for i in range(8)]
val=0
count=0
for i in range(n):
  m=l[i]
  if m<400:
    col[0]=True
  if 400<=m<800:
    col[1]=True
  if 800<=m<1200:
    col[2]=True
  if 1200<=m<1600:
    col[3]=True
  if 1600<=m<2000:
    col[4]=True
  if 2000<=m<2400:
    col[5]=True
  if 2400<=m<2800:
    col[6]=True
  if 2800<=m<3200:
    col[7]=True
  if m>=3200:
    val+=1
for i in range(8):
  if col[i]:
    count+=1
print(max(1,count),count+val)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define repr(i,from,to) for(int (i)=(from);(i)<(to);(i)++)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
#define all(x) begin((x)), end((x))
#define vprint(x) for(auto a:(x)) cout << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
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;
}


int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,k;
    cin>>n>>k;
    vector<ll> snuke(n,0);
    rep(i,k) {
        ll d;
        cin>>d;
        rep(j,d) {
            ll tmp;cin>>tmp;tmp--;
            snuke[tmp]++;
        }
    }
    ll res = 0;
    rep(i,n) {
        res += (snuke[i] == 0);
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=100010;
double ans=0;
int main()
{
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    string x,u;
    cin>>x>>u;
    if(u=="JPY") ans+=stod(x);
    else ans+=(380000.0*stod(x));
    // cout<<ans<<endl;
    // cout<<0.1*380000.0<<endl;
  }
  printf("%.5lf\n",ans);
  return 0;
}


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

int main(){
    int n;
    string s;
    cin >> n >> s;
    int count = 0;
    int max = 0;
    for(int i = 0; i < n; i++){
        if(s[i] == 'I'){
            count += 1;
        }else if(s[i] == 'D'){
            count -= 1;
        }
        if(count > max){
            max = count;
        }
    }
    cout << max << endl;
    return 0;
}



Measured memory_bytes: 256
import heapq as hq

n,m = map(int,input().split())

A = []
for a in [int(_) for _ in input().split()]:
    hq.heappush(A, -a)

for _ in range(m):
    t = hq.heappop(A)
    hq.heappush(A, t / 2)
print(-sum([int(a) for a in A]))

Measured memory_bytes: 14180
#include <bits/stdc++.h>
#define PENKI_MAX   100
#define PENKI_NUM   3

int main(void)
{
    std::vector<int> A(PENKI_MAX, 0);
    for (int i = 0; i < PENKI_NUM; i++)
    {
        int N;
        std::cin >> N;
        A[N - 1]++;
    }

    std::cout << std::accumulate(A.begin(), A.end(), 0, [](int a, int v){
        if (0 < v)
        {
            return a + 1;
        }
        return a;
    }) << std::endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int n, m, c, b[28] = {}, z = 0;
    cin >> n >> m >> c;
    for (int i = 1; i <= m; i++) cin >> b[i];
    while (n--) {
        int a[28] = {}, d = 0;
        for (int i = 1; i <= m; i++) cin >> a[i];
        for (int i = 1; i <= m; i++) d += a[i] * b[i];
        if (d + c > 0) z++;
    }
    cout << z;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
using ll = unsigned long long int;
int main()
{
	int n, x;
	ll sum, ans;
	vector<int> output;


	cin >> n >> x;

	while(n != 0 || x != 0) {
		ans = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				for (int k = 1; k <= n; k++) {
					if (k > j && j > i) {
						sum = i + j + k;
						if (sum == x) ans++;
					}
				}
			}
		}
		cout << ans << endl;
		cin >> n >> x;
	}
}


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

bool in_range(int a, int b){
  return a >= 0 && a < b;
}

int main(){
  int H, W, N;
  cin >> H >> W >> N;
  int r, c;
  cin >> r >> c;
  --r,--c;
  string S, T;
  cin >> S >> T;
  string lrud = "LRUD";
  // map<char,int> M;
  // for(int i = 0; i < 4; ++i) M[lrud[i]] = i;
  int dx[] = {0,0,-1,1}, dy[] = {-1,1,0,0};
  bool f = true;
  for(int i = 0; i < 4; ++i){
    int x = r, y = c;
    for(int j = 0; j < N; ++j){
      if(S[j] == lrud[i]) x += dx[i], y += dy[i];
      if((not in_range(x,H)) or (not in_range(y,W))){
        //cerr << lrud[i] << " " << j << " " << x << " " << y << endl;
        f = false;
        break;
      }
      if(T[j] == lrud[i^1]) x += dx[i^1], y += dy[i^1];
      if((not in_range(x,H)) or (not in_range(y,W))){
        x -= dx[i^1], y -= dy[i^1];
      }
    }
  }
  if(f) cout << "YES" << endl;
  else cout << "NO" << endl;
}


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


def digit(i, j):
    """
    1 <= k <= N となる k で、先頭の桁が i , 末尾の桁が j となる物の数を返す
    """
    count = 0
    for k in range(1, N+1):
        if str(k)[0] == str(i) and k % 10 == j:
            count += 1
    return count


seen = {}
for i in range(1, 10):
    for j in range(1, 10):
        seen[(i, j)] = digit(i, j)

res = 0
for i in range(1, 10):
    for j in range(1, 10):
        res += seen[(i, j)] * seen[(j, i)]


print(res)

Measured memory_bytes: 73528
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = (ll)1e9;
const ll mod = (ll)1e9 + 7;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

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

	int n = s.length() - 1;

	ull res = 0;
	for (int bit = 0; bit < (1 << n); bit++)
	{
		ull sum = 0;
		int r;
		int l = 0;
		for (r = 0; r < n; r++)
		{
			if (bit & (1 << r))
			{
				sum += stoll(s.substr(l, r - l + 1));
				l = r + 1;
			}
		}

		sum += stoll(s.substr(l, r - l + 1));
		res += sum;
	}

	cout << res << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  
  unsigned long long n;
  unsigned long long a,b,c,d;
  
  cin >> n >> a >> b;
  
  c = n/(a+b);
  d = n%(a+b);
  
  if(d<=a)
    cout << a*c + d;
  else
    cout << a*c + a;
  
  
  
}

Measured memory_bytes: 256
def resolve():
    from bisect import bisect_left
    n,k=map(int,input().split())
    a=sorted(list(map(int,input().split())))
    m=bisect_left(a,0)
    MOD=10**9+7
    ans=1
    if m==0 or (m==n and k%2==1):
        for i in a[-k:]:
            ans=(ans*i)%MOD
    elif m==n and k%2==0:
        for i in a[:k]:
            ans=(ans*i)%MOD
    else:
        ans=1
        l,r=0,-1
        lm=a[0]*a[1]
        rm=a[-1]*a[-2]
        for i in range(k//2):
            if lm>=rm:
                ans*=lm%MOD
                l+=2
                if l<=n-2:
                    lm=a[l]*a[l+1]
            else:
                ans*=rm%MOD
                r-=2
                if 1<=n+r:
                    rm=a[r]*a[r-1]
            ans%=MOD
        if k%2==1:
            ans*=a[r]
            ans%=MOD
    print(ans)

if __name__ == '__main__':
    resolve()

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

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

template<class T> inline void chmin(T &a, const T &b) { if(a > b) a = b; }

int cube(int x) {
	return x * x * x;
}

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

	for(int z; cin >> z && z;) {
		const int z3 = cube(z);

		int ans = z3;
		REP(x, 1, z) {
			const int x3 = cube(x);

			REP(y, x, z) {
				const int y3 = cube(y);
				if(z3 - y3 >= x3) chmin(ans, z3 - (x3 + y3));
			}
		}

		cout << ans << endl;
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1192
#include<bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define mod 998244353
#define pi 3.1415926535
#define fi first
#define se second
#define vll vector<ll>
#define vpll vector<pair <ll,ll> >
#define vvll vector< vll >
#define str string
#define umap unordered_map
#define uset unordered_set
#define rep(i,n) for(ll i=0;i<n;i++)
#define repA(i,s,n) for(ll i=s;i<=n;i++)
#define repD(i,s,n) for(ll i=s;i>=n;i--)
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define elif else if
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ALL(v) v.begin(),v.end()
#define sortA(v) sort(ALL(v))
#define sortD(v) sort(ALL(v),greater <ll> ())
#define print(v) for(auto itr:v) cout<<*itr<<" ";
#define sz size()
#define nl cout<<"\n";
using namespace std;
ll factorial(ll n){return (n==1||n==0)?1:n*factorial(n-1);}
ll power(ll x,ll y){ll res=1;while(y>0){if(y&1)res=res*x;y=y>>1;x=x*x;}return res;}
ll powerMod(ll x,ll y,ll m){if(y==0)return 1;ll p=powerMod(x,y/2,m)%m;p=(p*p)%m;return (y%2==0)?p:(x*p)%m;}
ll modInverse(ll a,ll m){return powerMod(a,m-2,m);}
ll gcd(ll a,ll b){if(a==0){return b;}else if(b==0){return a;}else{if(a>b){return gcd(a%b,b);}else{return gcd(b%a,a);}}}

int main(){
    fast
    str s;
    cin>>s;
    int res=0,ma=0;
    for(int i=0;i<3;){
        int x=0;
        if(s[i]=='R'){
            while(s[i]=='R'){
                x++;
                i++;
            }
            ma=max(ma,x);
        }
        else i++;
    }
    cout<<ma;
    return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define ll long long
#define ld long double
#define N 100005
vector<int> a[N];
bool used[N], ap[N];
int par[N], low[N], disc[N];
int vtime;
void find_ap(int u)
{
    int child=0;
    used[u]=true;
    low[u]=disc[u]=vtime++;
    for(auto v:a[u])
    {
        if(!used[v])
        {
            child++;
            find_ap(v);
            par[v]=u;
            low[u]=min(low[u],low[v]);
            if(par[u]==-2 && child>1)
            {
                ap[u]=true;
            }
            if(par[u]!=-2 && low[v]>=disc[u])
            {
                ap[u]=true;
            }
            continue;
        }
        if(v!=par[u])
        {
            low[u]=min(low[u],disc[v]);
        }
    }
}
void init()
{
    for(auto &it:a)
    {
        it.clear();
    }
    memset(used,0,sizeof used);
    memset(low,0,sizeof low);
    memset(disc,0,sizeof disc);
    memset(ap,0,sizeof ap);
    vtime=1;
    for(auto &it:par)
    {
        it=-1;
    }
    par[0]=-2;
}
void solve()
{
    init();
    int n,m;
    scanf("%d%d",&n,&m);
    int i;
    int x,y;
    for(i=0;i<m;i++)
    {
        scanf("%d%d",&x,&y);
        a[x].pb(y);
        a[y].pb(x);
    }
    find_ap(0);
    int ans=0;
    for(i=0;i<n;i++)
    {
        if(ap[i])
        {
            cout<<i<<endl;
        }
    }
}
int main()
{
    solve();
    return 0;
}

Measured memory_bytes: 8132
#include<bits/stdc++.h>
#define REP(x,y,z) for(int x=y;x<=z;x++)
#define MSET(x,y) memset(x,y,sizeof(x))
#define M 
using namespace std;
int main()
{
    int x,a;
    while (~scanf("%d %d", &x,&a)) {
        if (x<a) puts("0");
        else puts("10");
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

vector<int> make_vector(int n,int s,int w){
    vector<int> a(n);
    int g = s;
    rep(i,n){
        a[i] = (g/7) % 10;
        if( g%2 == 0 ) { g = (g/2); }
        else           { g = (g/2) ^ w; }
    }
    return a;
}

void solve(int n,int s, int w, int q){
    vector<int> a = make_vector(n,s,w);
    if(q==2||q==5){
        ll ans=0;
        int ok=0;
        rep(i,n){
            if(a[i])++ok;
            if(a[i]%q==0)ans+=ok;
        }
        cout<<ans<<endl;
        return;
    }
    vector<ll> sum(n);
    ll d = 1;
    for(int i=n-1;i>=0;--i){
        sum[i]=a[i]*d%q;
        d = d * 10 % q;
    }
    rep(i,n-1){
        (sum[n-i-2]+=sum[n-i-1])%=q;
    }
    ll ans=0;
    map<int,ll> cnt;
    rep(i,n){
        ans += cnt[sum[i]];
        if(a[i])cnt[sum[i]]++;
    }
    ans+=cnt[0];
    cout<<ans<<endl;
}

int main(){
    int n,s,w,q;
    while(cin>>n>>s>>w>>q,n)solve(n,s,w,q);
    return 0;
}


Measured memory_bytes: 9532
#include<stdio.h>

int main(void){
    
    int a,b,c,i;
    int count=0;
    
    scanf("%d",&a);
    scanf("%d",&b);
    scanf("%d",&c);

    if (1>a || 1>b || 1>c || a>10000 || b>10000 || c>10000 || a>b) {
        exit(1);
    }else{
        for (i=a; i<=b; i++) {
            if (c%i==0) {
                count++;
            }
        }
    }
    
    printf("%d\n",count);
    
    return 0;
}

Measured memory_bytes: 596
using System;
using System.Linq;

class Program {
  static void Main() {
    var arr = Console.ReadLine().Split().Select(int.Parse).ToArray();
    int a = arr[0];
    int b = arr[1];
    int x = arr[2];
    Console.WriteLine(a <= x && x <= a + b ? "YES" : "NO");
  }
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef pair<int,ll> type;// 1: query, 0: end, -1: begin
typedef pair<ll,type> event;

int main(){
  int N,Q;
  cin >> N >> Q;
  vector<event> v;
  rep(i,N) {
    int s,t,x;
    cin >> s >> t >> x;
    v.push_back({s-x, type(-1,x)});
    v.push_back({t-x, type(0,x)});
  }
  rep(i,Q) {
    int d;
    cin >> d;
    v.push_back({d, type(1,i)});
  }
  sort(v.begin(), v.end());

  vector<ll> res(Q);
  multiset<ll> se;

  for (auto p : v) {
    ll x = p.first;
    int type = p.second.first;
    ll val = p.second.second;
    if (type == -1) se.insert(val);
    else if (type == 0) se.erase(se.lower_bound(val));
    else res[val] = (se.empty() ? -1 : *(se.begin()));
  }
  for (auto e : res) cout << e << endl;
  return 0;
}

Measured memory_bytes: 27876
#include<iostream>

using namespace std;

struct Point{

   int x, y;
};

int main(){

   int W, H, N;
   cin>> W>> H>> N;
   int x[N], y[N], a[N];
   for(int i=0; i<N; i++) cin>> x[i]>> y[i]>> a[i];

   Point bl, tr;// bottomleft, topright
   bl.x=bl.y=0;
   tr.x=W; tr.y=H;
   for(int i=0; i<N; i++){
      switch(a[i]){
         case 1: bl.x=max(bl.x, x[i]); break;
         case 2: tr.x=min(tr.x, x[i]); break;
         case 3: bl.y=max(bl.y, y[i]); break;
         case 4: tr.y=min(tr.y, y[i]); break;
      }
      if(!(bl.x<tr.x&&bl.y<tr.y)){
         cout<< 0<< endl;
         return 0;
      }
   }

   cout<< (tr.x-bl.x)*(tr.y-bl.y)<< endl;

   return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define ll long long
#define LEFT(a) ((a)<<1)
#define RIGHT(a) (LEFT(a) + 1)
#define MID(a,b) ((a+b)>>1)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))

using namespace std;

ll POWER (ll x, ll y, ll mod){
    ll ans = 1, c = x;
    while (y){
        if ((y & 1) == 1)
            ans = ans * c % mod;
        c = c * c % mod;
        y /= 2;
    }
    return ans;
}

const int N = 25, M = 4e6 + 6, MOD = 1e9 + 7;
const double C = 1;

int n, m;
int g[N][N];
int B[M];
int dp[M];
vector < int > V[N];

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    m = (1<<n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin>>g[i][j];
    V[0].pb (0);
    for (int i = 1; i < m; i++){
        B[i] = 1 + B[(i & (i - 1))];
        V[B[i]].pb (i);
    }
    dp[0] = 1;
    for (int I = 1; I <= n; I++)
        for (int i = 1; i <= n; i++){
            int x = (1<<(i - 1));
            if (g[I][i])
                for (int bb: V[I - 1])
                    if ((bb & x) == 0){
                        dp[(bb ^ x)] += dp[bb];
                        if (dp[(bb ^ x)] >= MOD)
                            dp[(bb ^ x)] -= MOD;
                    }
        }
    cout<<dp[m - 1]<<endl;
    return 0;
}


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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod= int(1e9)+7;
//const int mod=998244353;
using P = pair<int,int>;
using Pll = pair<ll,ll>;
using ld=long double;

int main() {
   ll x;cin >>x;
   ll ans=0;
   ans+=(x/500)*1000;
   x%=500;
   ans+=(x/5)*5;
   cout <<ans <<endl;
}

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

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

const int maxn = 1e6 + 5;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    vector<bool> is_prime(maxn, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= maxn; i++) {
        if (is_prime[i] && (ll)i * i <= maxn) {
            for (int j = i * i; j <= maxn; j += i)
                is_prime[j] = false;
        }
    }

    vector<int> primes;
    for(int i=2; i <= maxn; i++) {
        if(is_prime[i]) primes.push_back(i);
    }

    vector<bool> found(maxn, false);
    int n, all = 0, flag = 1;
    cin >> n;
    while(n--) {
        int num;
        cin >> num;
        if(all == 0) all = num;
        else all = __gcd(all, num);
        for (ll p : primes) {
            if (p * p > num)
                break;
            int count = 0;
            while (num % p == 0) {
                count++;
                num /= p;
            }
            if(count > 0) {
                if(found[p]) flag = 0;
                else found[p] = true;
            }
        }
        if (num > 1) {
            if(found[num]) flag = 0;
            else found[num] = true;
        }
    }

    if(flag == 1) cout << "pairwise coprime" << endl;
    else if(all == 1) cout << "setwise coprime" << endl;
    else cout << "not coprime" << endl;

    return 0;
}

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

using vi=vector<int>;
using vvi=vector<vector<int>>;
vvi c(200001);
vi ans(200001);

void dfs(int v,int p){
  for(int x : c.at(v)){
    if(x!=p){
      ans.at(x)+=ans.at(v);
      dfs(x,v);
    }
  }
}

int main(){
  int n,q;cin>>n>>q;
  rep(i,n-1){
    int a,b;cin>>a>>b;
    a--;b--;
    c.at(b).push_back(a);
    c.at(a).push_back(b);
  }
  rep(i,q){
    int c,d;
    cin>>c>>d;
    ans.at(c-1)+=d;
  }
  dfs(0,-1);
  rep(i,n){
    if(i)cout<<" ";
    cout<<ans.at(i);
  }
}


Measured memory_bytes: 26624
#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>
#include<sstream>
#include<iterator>
#include<list>

using namespace std;

typedef  long long int lint;

#define rep(i, n) for (lint i = 0; i < n; i++)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)
#define mp make_pair
#define IP pair<int,int>
#define enld endl

int main() {
	double a;
	while (cin >> a) {
		if (a <= 48) {
			cout << "light fly" << endl;
		}
		else if (a <= 51) {
			cout << "fly" << endl;
		}
		else if (a <= 54) {
			cout << "bantam" << endl;
		}
		else if (a <= 57) {
			cout << "feather" << endl;
		}
		else if (a <= 60) {
			cout << "light" << endl;
		}
		else if (a <= 64) {
			cout << "light welter" << endl;

		}
		else if (a <= 69) {
			cout << "welter" << endl;
		}
		else if (a <= 75) {
			cout << "light middle" << endl;
		}
		else if (a <= 81) {
			cout << "middle" << endl;
		}
		else if (a <= 91) {
			cout << "light heavy" << endl;
		}
		else {
			cout << "heavy" << endl;
		}
	}
}


Measured memory_bytes: 3164
import java.math.*;
import java.util.*;
import java.util.stream.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int X = sc.nextInt();
    int Y = sc.nextInt();
    int A = sc.nextInt();
    int B = sc.nextInt();
    int C = sc.nextInt();
    List<Integer> p = new ArrayList<>(A);
    List<Integer> q = new ArrayList<>(B);
    List<Integer> r = new ArrayList<>(C);
    for (int i = 0; i < A; i++) p.add(sc.nextInt());
    for (int i = 0; i < B; i++) q.add(sc.nextInt());
    for (int i = 0; i < C; i++) r.add(sc.nextInt());
    sc.close();

    long ans = Stream.concat(Stream.concat(
        p.stream().sorted(Comparator.reverseOrder()).limit(X),
        q.stream().sorted(Comparator.reverseOrder()).limit(Y)),
        r.stream())
      .sorted(Comparator.reverseOrder()).limit(X + Y)
      .mapToLong(Long::valueOf)
      .reduce(Long::sum)
      .getAsLong();

    System.out.println(ans);
  }
}

Measured memory_bytes: 101504
a, b = map(str,input().split())
if (a == "H")and(b == "H"):
    print("H")
if (a == "H")and(b == "D"):
    print("D")
if (a == "D")and(b == "H"):
    print("D")
if (a == "D")and(b == "D"):
    print("H")


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

int main() {
	int H, W, x, y;
	string a[300];
	string b[300];
	for (int i = 0; i < 150; i++) {
		a[i * 2] = "#";
		a[i * 2 + 1] = ".";
		b[i * 2] = ".";
		b[i * 2 + 1] = "#";
	}
	cin >> H >> W;
	while (!(H == 0 && W == 0)) {
		x = H % 2;
		y = (H - x) / 2;
		for (int j = 0; j < y; j++) {
			for (int k = 0; k < W; k++) {
				cout << a[k];
			}
			cout << endl;
			for (int l = 0; l < W; l++) {
				cout << b[l];
			}
			cout << endl;
		}
		if (H % 2 == 1) {
			for (int m = 0; m < W; m++) {
				cout << a[m];
			}
			cout << endl;
		}
		cout << endl;
		cin >> H >> W;
	}
	return 0;
}

Measured memory_bytes: 3148
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>
#include <deque>
#include <iterator>
#include <map>
#include <queue>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
template<class T> inline bool chmax(T& a, T b) {if (a<b) {a=b; return true;} return false;}
template<class T> inline bool chmin(T& a, T b) {if (a>b) {a=b; return true;} return false;}

vll a(3000);
vvll dp(3000, vll(3000, 0));
V<V<bool> > flag(3000, V<bool>(3000, false));

ll f(ll l, ll r) {
  if (flag.at(l).at(r)) return dp.at(l).at(r);
  flag.at(l).at(r) = true;
  if (l == r) return dp.at(l).at(r) = a.at(l);
  return dp.at(l).at(r) = max(a.at(l)-f(l+1, r), a.at(r)-f(l, r-1));
}

int main() {
  ll n; cin >> n;
  REP(i, n) cin >> a.at(i);
  ll ans = f(0, n-1);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 72064
#define _GLIBCXX_DEBUG
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <stack>
#include <random>
#include <utility>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <bitset>
#include <sstream>

using namespace std;

#define REP(i, x) for (int i = 0; i < (x); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define MOD 1'000'000'007
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main(int argc, const char *argv[])
{
    ll a, b;
    cin >> a >> b;

    ll c = a + 1;
    while (c > a)
    {
        c = a;
        a = a % b;
    }
    a = min(llabs(a), llabs(a - b));
    cout << a << endl;

    return 0;
}


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

int main()
{
	int n;
	string s;
	cin>>n;
	cin>>s;
	if(n<s.size()){
		cout<<s.substr(0,n)<<"...";
	}
	else{
		cout<<s.substr(0,n);
	}
	return 0;
}

Measured memory_bytes: 3608
n = int(input())
t, a = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]
l = [(i, abs(a - (t - x * 0.006))) for i, x in enumerate(h)]
target = min(l, key = lambda x: x[1])
print(target[0]+1)

Measured memory_bytes: 3188
from sys import stdin
import math
inp = lambda : stdin.readline().strip()

n = int(inp())
a = [int(x) for x in inp().split()]
ans = 0
for i in range(1, n):
	if a[i] < a[i-1]:
		ans += a[i-1] - a[i]
		a[i] += a[i-1] - a[i]
print(ans)

Measured memory_bytes: 103872
A = list(input())
B = list(input())
C = list(input())
count = [0, 0, 0]
people = [A, B, C]
turn = 0
while True:
    if count[turn] == len(people[turn]):
        if turn == 0:
            print('A')
            break
        if turn == 1:
            print('B')
            break
        else:
            print('C')
            break
    else:
        if people[turn][count[turn]] == 'a':
            count[turn] += 1
            turn = 0
        elif people[turn][count[turn]] == 'b':
            count[turn] += 1
            turn = 1
        elif people[turn][count[turn]] == 'c':
            count[turn] += 1
            turn = 2

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

int gcd(int x, int y)
{
  if(x<y){
    swap(x, y);
  }

  while(y>0){
    int r = x%y;
    x = y;
    y = r;
  }

  return x;
}

int main()
{
  int x, y;
  cin >> x >> y;

  cout << gcd(x, y) << endl;

  return 0;
}



Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
 
    string s;
    cin>>s;

    int cnt0=0,cnt1=0;
  	for(int i=0;i<s.size();i++){
          if(s.at(i)=='0')
            cnt0++;
          else
            cnt1++;
      }

    cout<<min(cnt1,cnt0)*2<<endl;
    return 0;
}  

Measured memory_bytes: 512
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
#define REP(i, x, y) for(ll i = x; i < y; i++)
#define PER(i, x, y) for(ll i = x; i > y; i--)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-11;

struct edge {
    ll to;
    double cost;
};

int V;
vector<edge> G[1000000];
double d[1000000];

void addedge(int st, int ed, double co) {
    edge e;
    e.to = ed;
    e.cost = co;
    G[st].push_back(e);
}

void dijkstra(int s) {
    priority_queue<pdlg, vector<pdlg>, greater<pdlg> > que;
    fill(d, d + V + 10, (double)inf);
    d[s] = 0;
    que.push(pdlg(0, s));

    while (!que.empty()) {
        pdlg p = que.top();
        que.pop();
        ll v = p.second;
        if (d[v] < p.first) {
            continue;
        }
        int len = G[v].size();
        for (int i = 0; i < len; i++) {
            edge e = G[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(pdlg(d[e.to], e.to));
            }
        }
    }
}

int main() {
    double xs, ys, xt, yt;
    cin >> xs >> ys >> xt >> yt;
    ll N;
    cin >> N;
    double x[N], y[N], r[N];
    REP(i, 0, N) {
        cin >> x[i] >> y[i] >> r[i];
    }
    V = N + 2;
    REP(i, 0, N) {
        double dis = max((double)0, sqrt((x[i] - xs) * (x[i] - xs)
                                 + (y[i] - ys) * (y[i] - ys)) - r[i]);
        addedge(0, i + 1, dis);
        addedge(i + 1, 0, dis);
    }
    REP(i, 0, N) {
        double dis = max((double)0, sqrt((x[i] - xt) * (x[i] - xt)
                                 + (y[i] - yt) * (y[i] - yt)) - r[i]);
        addedge(N + 1, i + 1, dis);
        addedge(i + 1, N + 1, dis);
    }
    REP(i, 0, N) {
        REP(j, i + 1, N) {
            double dis = max((double)0, sqrt((x[i] - x[j]) * (x[i] - x[j])
                                     + (y[i] - y[j]) * (y[i] - y[j])) - r[i] - r[j]);
            addedge(i + 1, j + 1, dis);
            addedge(j + 1, i + 1, dis);
        }
    }
    double dissted = sqrt((xs - xt) * (xs - xt) + (ys - yt) * (ys - yt));
    addedge(0, N + 1, dissted);
    addedge(N + 1, 0, dissted);
    dijkstra(0);
    double ans = d[N + 1];
    cout << setprecision(13);
    cout << ans << endl;
}


Measured memory_bytes: 47600
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map.Entry;

import java.util.PriorityQueue;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
	
	public static void main(String[] args) throws IOException {	
		try(final Scanner sc = new Scanner(System.in)){
			final String s = sc.next();
			if(s.equals("Sunny")) {
				System.out.println("Cloudy");
			}else if(s.equals("Cloudy")) {
				System.out.println("Rainy");
			}else {
				System.out.println("Sunny");
			}
			
		}
	}

	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() throws IOException {
			while(!hasNext()){
				tok = new StringTokenizer(br.readLine());
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public int[] nextIntArray(int n) throws IOException {
			final int[] ret = new int[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextInt();
			}
			return ret;
		}

		public long[] nextLongArray(int n) throws IOException {
			final long[] ret = new long[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextLong();
			}
			return ret;
		}

		public void close() throws IOException {
			br.close();
		}
	}
}

Measured memory_bytes: 21076
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

string s;
LL dp[100002][2];
 
LL rec(int k=0,bool t=true){
    if(k==s.length()) return 1;
    int x=s[k]-'0';
    int mx=t?x:1;
    if(~dp[k][t]) return dp[k][t];
    LL res=0LL;
    for(int i=0;i<=mx;i++){
        if(i==1) res=(res+2*rec(k+1,t&&i==mx))%mod;
        else res = (res+rec(k+1,t&&i==mx))%mod;
    }
    return dp[k][t]=res%mod;
}
 


int main(){
    cin >> s;
    memset(dp,-1,sizeof(dp));
    cout << rec()%mod << endl;
    return 0;
}



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

const int mod=1e9+7;
int dp[2005];

int32_t main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int n;
    cin >> n;
    for(int i=3;i<=n;i++){
        for(int j=3;j<i;j++)
            dp[i]=(dp[i]+dp[i-j])%mod;
        dp[i]=(dp[i]+1)%mod;
    }
    cout << dp[n];
}

Measured memory_bytes: 3656
import java.util.*;

public class Main {
	public static void main(String... args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int cnt = 0;
		for (int i = 0 ; i < n ; i++) {
			int a = sc.nextInt();
			while (a % 2 == 0) {
				a = a / 2;
				cnt++;
			}
		}
		System.out.println(cnt);
	}
}


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

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

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

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int INF = 1<<30;
const ll mod = 1000000007LL;

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

ll pow(ll a, ll n, ll m) {
	ll ret = 1LL;
	for (; n > 0LL; n >>= 1LL, a = a * a % m) {
		if (n % 2LL == 1LL) {
			ret = ret * a % m;
		}
	}
	return ret;
}

int main() {
    int N;
    string X;
    cin>>N>>X;
    vector<ll> ans(200005,0LL);
    rep(i,200005){
        if(i==0) continue;
        int t = i;
        int s = t % __builtin_popcount(t);
        ans[t] = ans[s]+1;
    }
    int cnt = 0;
    rep(i,N) {
        if(X[i] == '1') cnt++;
    }
    if(cnt!=0&&cnt!=1){
        int A = 0,B=0;
        int p = 1,q = 1;
        rep(i,N){
            int l = N-i-1;
            if(X[l]=='1'){
                A = (A+p)%(cnt+1);
                B = (B+q)%(cnt-1);
            }
            p = (p*2LL)%(cnt+1);
            q = (q*2LL)%(cnt-1);
        }
        rep(i,N){
            int l = N-i-1;
            int x=0;
            if(X[i]=='1'){
                x = (B-pow(2LL,l,cnt-1))%(cnt-1);
                if(x<0) x += cnt-1;
                cout<<ans[x]+1<<endl;
            }
            else {
                x = (A+pow(2LL,l,cnt+1))%(cnt+1);
                if(x<0) x += cnt+1;
                cout<<ans[x]+1<<endl;
            }
        }
    }
    if(cnt==0){
        rep(i,N) cout<<1<<endl;
    }
    if(cnt==1){
        int A = 0;
        int p = 1;
        rep(i,N){
            int l = N-i-1;
            if(X[l]=='1'){
                A = (A+p)%(cnt+1);
            }
            p = (p*2LL)%(cnt+1);
        }
        rep(i,N){
            int l = N-i-1;
            int x=0;
            if(X[i]=='1'){
                cout<<0<<endl;
            }
            else {
                x = (A+pow(2LL,l,cnt+1))%(cnt+1);
                if(x<0) x += cnt+1;
                cout<<ans[x]+1<<endl;
            }
        }
    }
}

Measured memory_bytes: 5236
#prag\
ma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	long long n,m;
	cin>>n>>m;
	if(n>1&&m>1) cout<<n*m-2*(n-1+m-1);
	else if(n==1&&m>1) cout<<m-2;
	else if(n>1&&m==1) cout<<n-2;
	else cout<<1;
}

Measured memory_bytes: 256
N = int(input())
Q = []
for _ in range(N):
    Q.append(list(map(int, input().split())))

dp = [[0, 0, 0] for _ in range(N)]
dp[0] = Q[0]
for i in range(1, N):
    dp[i][0] = Q[i][0]+max(dp[i-1][1], dp[i-1][2])
    dp[i][1] = Q[i][1]+max(dp[i-1][0], dp[i-1][2])
    dp[i][2] = Q[i][2]+max(dp[i-1][0], dp[i-1][1])
print(max(dp[-1]))

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

#define IOS ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(0)
#define endl "\n"
#define int long long
typedef vector<int> vi;
#define all(x) x.begin(),x.end()
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
#define OO 1e9
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
typedef long long ll;
#define in_range(x, y, r, c) ((x >= 0 && x < r && y >= 0 && y < c))


const double eps=1e-9;
const int MOD=998244353;
const int N=(int)3*1e5+9;
const int inf = 1<<30;


template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
int est[N],west[N];
int n;
int32_t main() {
IOS;
string s;
cin>>n>>s;
FOR(i,1,n){ 
    west[i]=west[i-1]+(s[i-1]=='W');
    est[i]=est[i-1]+(s[i-1]=='E');
}
int ans=inf;
for (int  i = 1; i <= n; i++)
{
    
        ans=min(ans,west[i-1]+est[n]-est[i]);
   

}
cout<<ans<<endl;


}

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

#define int long long
#define double long double

using namespace std;

#define REP(i, a, b) for (int(i) = (a); i < (b); (i)++)
#define rep(i, n) REP(i, 0, n)
#define PER(i, a, b) for (int(i) = (a - 1); i >= (b); (i)--)
#define per(i, n) PER(i, n, 0)
#define each(i, n) for (auto &i : n)
#define clr(a) memset((a), 0, sizeof(a))
#define mclr(a) memset((a), -1, sizeof(a))
#define all(a) (a).begin(), (a).end()
#define dum(val) cerr << #val " = " << val << " ";
#define dump(val) cerr << #val " = " << val << endl;
#define FILL(a, v) fill(a, a + sizeof(a) / sizeof(*a), v)

typedef pair<int, int> P;

const int mod = 1e9 + 7;
const int INF = 1e18;

signed main() {

  // 0 1 4 0 2 4 2

  int n;
  cin >> n;

  int sum = 0;
  map<int, int> mp;
  mp[0] = 1;

  int ans = 0;
  rep(i, n) {
    int a;
    cin >> a;
    sum += a;
    if (mp.count(sum)) {
      ans += mp[sum];
    }
    mp[sum]++;
  }

  cout << ans << endl;
}


Measured memory_bytes: 12800