akhauriyash/Code-Regression huggingface dataset:
#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 all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())

using namespace std;

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

inline void yes() { cout << "Yes" << endl; exit(0); }
inline void no() { cout << "No" << endl; 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) { if (min(a, b) == 0) return max(a, b); return a / gcd(a, b) * b; }
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) { x = max(x, y); }
template <typename T> inline void amin(T &x, T y) { x = min(x, y); }
template <typename T> inline T exp(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, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

void solve() {
  int n;
  cin >> n;
  vstr s(n);
  cin >> s;
  using P = pair<int, int>;
  vector<P> v;
  rep(i, n) {
    int m = sz(s[i]);
    int l = 0, r = 0;
    int now = 0;
    rep(j, m) {
      if (s[i][j] == ')') {
        now--;
        amin(l, now);
      } else {
        now++;
      }
    }
    amax(r, now - l);
    l *= -1;
    v.emplace_back(l, r);
  }
  vi32 o(n);
  iota(all(o), 0);
  sort(all(o), [&](int i, int j) {
    return v[i].first - v[i].second < v[j].first - v[j].second;
  });
  int sum = 0;
  int rsum = 0;
  rep(i, n) {
    if (v[i].first == 0) sum += v[i].second;
    if (v[i].second == 0) rsum += v[i].first;
  }
  // rep(i, n) {
  //   int l, r;
  //   tie(l, r) = v[o[i]];
  //   cerr << l << " " << r << endl;
  // }
  rep(i, n) {
    int l, r;
    tie(l, r) = v[o[i]];
    if (l == 0) continue;
    if (r == 0) continue;
    sum -= l;
    if (sum < 0) no();
    sum += r;
  }
  sum -= rsum;
  if (sum != 0) no();
  yes();
}


Measured memory_bytes: 46548
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <ctime>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <memory.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long double LD;
typedef long long LL;
typedef pair<LL, LL> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#ifdef LOCAL
#define DEBUG(x) { cerr << "# " << #x << ": " << x << endl;}
#else
#define DEBUG(x)
#endif
mt19937_64 mt(time(0));
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/

LL solve(LL x, LL k, LL d) {
  LL tmp = abs(x) / d;
  tmp = min(tmp, k);
  k -= tmp;
  if (x >= 0) {
    x -= tmp * d;
  } else {
    x += tmp * d;
  }
  if (k % 2 == 0) return abs(x);
  tmp = min(abs(x - d), abs(x+d));
  return tmp;
}





int main() {
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  cout.precision(10); cout << fixed;
#ifdef LOCAL
  freopen("../test.txt", "r", stdin);
    // freopen("../output.txt", "w", stdout);
#endif
  LL x, k, d;
  cin >> x >> k >> d;
  cout << solve(x, k, d) << '\n';







/*---------------------------------------Coding Space End------------------------------------------*/
#ifdef LOCAL
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." << endl;
#endif
  return 0;
}
/* author:  txingml */
/* picture is from hamayanhamayan(CF handle) */


Measured memory_bytes: 3192
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;

namespace AtCoder.ABC
{
	class QuestionB
	{
		public static Dictionary<NCR, long> NcrDict = new Dictionary<NCR, long>();

		public static void Main(string[] args)
		{
			var np = Console.ReadLine().Split(" ").Select(x => int.Parse(x)).ToArray();
			var n = np[0];
			var p = np[1];

			var a = Console.ReadLine().Split(" ").Select(x => int.Parse(x)).ToArray();

			var kisuuCount = 0;

			for (int i = 0; i < n; i++) {
				if(a[i] % 2 == 1) {
					kisuuCount++;
				}
			}

			var guusuuCount = n - kisuuCount;

			var sumGuusuu = 0L;

			for(int i = 0; i <= guusuuCount; i++) {
				sumGuusuu += nCr(guusuuCount, i);
			}

			var sumKisuu = 0L;

			for (int i = 0; i <= kisuuCount; i += 2) {
				sumKisuu += nCr(kisuuCount, i);
			}

			if(p == 1 && kisuuCount == 0) {
				sumKisuu = 0;
			}
			
			Console.WriteLine(sumKisuu * sumGuusuu);
			/*
			{
				var ruijou = 1L;

				for (int i = 0; i < n - 1; i++) {
					ruijou *= 2;
				}

				Console.WriteLine(ruijou);
			}
			*/
		}

		public class NCR
		{
			public int n;
			public int r;

			public NCR(int nn, int rr)
			{
				n = nn;
				r = rr;
			}

			public override int GetHashCode()
			{
				return n.GetHashCode() + r.GetHashCode() * 117;
			}

			public override bool Equals(object obj)
			{
				if(obj is null) {
					return false;
				}

				if(obj is NCR ncr) {
					return this.n == ncr.n && this.r == ncr.r;
				}

				return false;
			}
		}

		public static long nCr(int n, int r)
		{
			if(n < r) {
				throw new Exception();
			}

			r = Math.Min(r, n - r);

			var cr = new NCR(n, r);

			if (NcrDict.ContainsKey(cr)){
				return NcrDict[cr];
			}

			if (r == 1) {
				return n;
			} else if (r == 0) {
				return 1;
			}

			var temp = nCr(n - 1, r) + nCr(n - 1, r - 1);

			NcrDict.Add(cr, temp);

			return temp;
		}
	}
}


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

int main() {
    long long N, ans;
    cin >> N;
    vector<long long> A(N, 0);
    bool flag = false;

    for(int i = 0; i < N; i++){
        cin >> A[i];
        if(A[i] == 0){
            flag = true;
            break;
        }
    }

    if(flag){
        cout << 0 << endl;
        exit(0);
    }

    ans = 1;
    for(int i = 0; i < N; i++){
        ans = ans * A[i];
        if(ans < 0){
            cout << "-1" << endl;
            return 0;
        }
    }
    if(ans > 0 && ans <= 1000000000000000000){
        cout << ans << endl;
    }else{
        cout << "-1" << endl;
    }
}

Measured memory_bytes: 4384
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC optimize ("trapv")
using namespace std;

#define pii pair<int, int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define DEBUG 1
#define cerr if (DEBUG) cerr
#define test cerr << "hi\n";

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l, r) uniform_int_distribution<long long>(l, r)(rng)
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> OST;

#define INF 0x3f3f3f3f3f3f3f3f
#define MAXN 300005
//#define MOD 998244353LL
#define MOD 1000000007LL

void solve() {
    int n, m;
    long long k;
    cin >> n >> m >> k;
    vector<long long> a(n), b(m), psa(n+1), psb(m+1);
    for (long long &x : a)
        cin >> x;
    for (long long &x : b)
        cin >> x;
    partial_sum(a.begin(), a.end(), psa.begin()+1);
    partial_sum(b.begin(), b.end(), psb.begin()+1);

    int ans = 0;

    for (int i = 0; i <= n; i++) {
        if (psa[i] > k) break;
        int pp = upper_bound(psb.begin(), psb.end(), k-psa[i]) - psb.begin();
//        cerr << i << ' ' << pp-1 << '\n';
        ans = max(ans, i+pp-1);
    }
    cout << ans << '\n';
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    auto start_time = clock();
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
//    cin >> t;
    for (int no = 1; no <= t; no++) {
//        cout << "Case #" << no << ": ";
        solve();
    }

#ifdef LOCAL
    cerr << "TIME ELAPSED: " << double(clock() - start_time) / CLOCKS_PER_SEC << '\n';
#endif
}

Measured memory_bytes: 9532
#!/usr/bin/env python3
import sys


def solve(S: str, T: str):
    count =0
    for s, t in zip(S, T):
        if s==t:
            count+=1
    print(count)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    T = next(tokens)  # type: str
    solve(S, T)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
////////////////////////// Author
////////////////////////// Nasim Hossain Rabbi
////////////////////////// JU-CSE28
////////////////////////// CF - imnasim3.1415
////////////////////////// UVA - imnasim3.1415
////////////////////////// Mail - imnasim3.1415@gmail.com
#include<bits/stdc++.h>
using namespace std;
#define sz size()
#define mk make_pair
#define clr clear()
#define B begin()
#define E end()
#define EM empty()
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,n) for(i=0;i<n;i++)
#define Rep(i,n) for(i=1;i<=n;i++)
#define all(cont) cont.begin(),cont.end()
#define pb push_back
#define endl '\n'
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pi 3.1415926535897932384626433832795
#define vi vector<int>
#define vl vector<long long>
#define vs vector<string>
#define vp(vi,x) cin>>x; vi.pb(x);
typedef long long LL;
typedef unsigned long long ULL;
template<typename T>
 T gcd(T a,T b)
{
    return b==0?a:gcd(b,a%b);
}
template<typename T>
 T lcm(T a,T b)
{
    LL g=gcd(a,b);
    return (a/g)*b;
}
int main()
{
//    fast;
    int i,j,k,n,m,l,s=0,y,tc=1;
    while(cin>>n)
    {
        LL x,c=1,cc=0;
        vl a;
        rep(i,n)
        {
            vp(a,x);
        }
        sort(all(a));
        rep(i,n-1)
        {
            if(a[i]==a[i+1]) c++;
            else
            {
                if(c%2==1 || c==0) cc++;
                c=1;
            }
        }
        if(c%2==1 || c==0) cc++;
        cout<<cc<<endl;
    }
}



Measured memory_bytes: 1400
/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using Pair = pair<int32_t, int32_t>;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  string S, T;
  cin >> S >> T;
  if(T.length() == S.length() +1 && S == T.substr(0, S.length())) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 3656
#include "bits/stdc++.h"
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
#include <tuple>
using namespace std;

#define FOR(i,init,a) for(int i=init; i<a; i++)
#define rep(i,a) FOR(i,0,a)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define rep1(i,a) for(int i=1; i<=a; i++)
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define mem(a,n) memset( a, n, sizeof(a))
#define all(a) a.begin(),a.end()
#define chmin(a,b) a=min(a,b);
#define chmax(a,b) a=max(a,b);

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;
static const double pi = 3.141592653589793;

void pr(ll ans){
    cout1(ans)
    exit(0);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll a,b,c;
    cin>>a>>b>>c;
    
    if(a==b&&b==c){
        if(a%2) pr(0);
        else pr(-1);
    }
    
    ll cnt=0, sum=a+b+c;
    while(a%2==0&&b%2==0&&c%2==0){
        ll na=(sum-a)/2;
        ll nb=(sum-b)/2;
        ll nc=(sum-c)/2;
        a=na;
        b=nb;
        c=nc;
        cnt++;
    }
    pr(cnt);
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int n,m;
int taro[100],hana[100];

void solve() {
  int tsum=0,hsum=0;
  for(int i=0;i<n;i++) {
    tsum += taro[i];
  }
  for(int i=0;i<m;i++) {
    hsum += hana[i];
  }
  sort(taro,taro+n);
  sort(hana,hana+m);
  int diff = tsum - hsum;
  int tans=0,hans=0;
  for(int i=0;i<n;i++) {
    for(int j=0;j<m;j++) {
      if((diff == 0 && hana[j] == taro[i]) || (diff < 0 && diff + (hana[j] - taro[i]) * 2 == 0) || (diff > 0 && diff - (taro[i] - hana[j]) * 2 == 0)) {
        tans = taro[i];
        hans = hana[j];
        break;
      }
    }
    if(tans != 0 && hans != 0) break;
  }
  if(tans != 0 && hans != 0) {
  cout << tans << " " << hans << endl;
  }
  else {
    cout << "-1" << endl;
  }
}

int main() {
  while(cin >> n >> m) {
    if(n==0&&m==0) break;
    for(int i=0;i<n;i++) {
      cin >> taro[i];
    }
    for(int i=0;i<m;i++) {
      cin >> hana[i];
    }
    solve();
  }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define int long long int
#define MOD(x) ((x % MOD_N) + MOD_N) % MOD_N
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define RFORE(i,a,b) for(int i=(b);i>=(a);--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(c) (c).begin(),(c).end()
#define RALL(c) (c).rbegin(),(c).rend()
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define SZ(c) (int)((c).size())
#define EACH(i,v) for(auto i=v.begin();i!=v.end();++i)
#define REACH(i,v) for(auto i=v.rbegin();i!=v.rend();++i)
#define LB(c,x) distance((c).begin(),lower_bound(ALL(c),x))
#define UB(c,x) distance((c).begin(),upper_bound(ALL(c),x))
#define COUNT(c,x) (lower_bound(ALL(c),x)-upper_bound(ALL(c),x))
#define UNIQUE(c) SORT(c); (c).erase(unique(ALL(c)),(c).end());
#define COPY(c1,c2) copy(ALL(c1),(c2).begin())
#define EXIST(s,e) (bool)((s).find(e)!=(s).end())
#define PB push_back
#define MP make_pair
#define DEL(v) decltype(v)().swap(v)
#define DUMP(x)  cerr<<#x<<" = "<<(x)<<endl;
#define NL cerr<<endl;
using namespace std;
template<typename T,typename U> using P=pair<T,U>;
template<typename T> using V=vector<T>;
template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<typename T>T sum(vector<T>&v){return accumulate(ALL(v),T());}
template<typename T>T sum(vector<T>&v,int a,int b){return accumulate(v.begin()+a,v.begin()+b,T());}
template<typename T>T max(vector<T>&v){return *max_element(ALL(v));}
template<typename T>T min(vector<T>&v){return *max_element(ALL(v));}
template<typename T>T max_index(vector<T>&v){return distance((v).begin(),max_element(ALL(v)));}
template<typename T>T min_index(vector<T>&v){return distance((v).begin(),min_element(ALL(v)));}

struct edge { int to, cost; };

template<typename T>auto&operator<<(ostream&s,const vector<T>&v){s<<"[";bool a=1;for(auto e:v){s<<(a?"":" ")<<e;a=0;}s<<"]";return s;}
template<typename T,typename U>auto&operator<<(ostream&s,const pair<T,U>&p){s<<"("<<p.first<<","<<p.second<<")";return s;}
template<typename T>auto&operator<<(ostream&s,const set<T>&st){s<<"{";bool a=1;for(auto e:st){s<<(a?"":" ")<<e;a=0;}s<<"}";return s;}
template<typename T,typename U>auto&operator<<(ostream&s,const map<T,U>&m){s<<"{";bool a=1;for(auto e:m){s<<(a?"":" ")<<e.first<<":"<<e.second;a=0;}s<<"}";return s;}

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

signed main()
{
   int N, Ma, Mb; cin >> N >> Ma >> Mb;
   V<int> a(N), b(N), c(N);
   REP(i, N) {
      cin >> a[i] >> b[i] >> c[i];
   }

   V<V<int>> dp(sum(a)+1, V<int>(sum(b)+1, INF));
   dp[0][0] = 0;
   REP(i, N) {
      RFORE(A, 0, sum(a)) {
         RFORE(B, 0, sum(b)) {
            if (A + a[i] <= sum(a) && B + b[i] <= sum(b)) {
               chmin(dp[A + a[i]][B + b[i]], dp[A][B] + c[i]);
            }
         }
      }
   }

   int ans = INF;
   for (int i = 1; Ma * i <= sum(a) && Mb * i <= sum(b); i++) {
      chmin(ans, dp[Ma * i][Mb * i]);
   }
   cout << (ans == INF ? -1 : ans) << endl;

   return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
#define ff(x,a,b) for(int x=a;x<=b;++x)
#define fff(x,a,b) for(int x=a;x>=b;--x)
using namespace std;
typedef long long ll;
void rd(int &v){char ch;for(ch='*';ch<'0'||ch>'9';ch=getchar());for(v=0;ch>='0'&&ch<='9';ch=getchar()) v=v*10+ch-'0';}
int n,maxx,max2,a[200005];
int main()
{
	cin>>n;
	ff(i,1,n)
	{
		rd(a[i]);
		if(a[i]>=a[maxx]) max2=maxx,maxx=i;
		else if(a[i]>a[max2]) max2=i;
	}
	ff(i,1,n)
	{
		if(maxx==i) printf("%d\n",a[max2]);
		else printf("%d\n",a[maxx]);
	}
}

Measured memory_bytes: 2432
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
using namespace std;
using lint = int64_t;

struct UnionFind {
    vector<int> par;
    UnionFind(int N) : par(N) {
        rep(i, N) par[i] = -1;
    }
    int root(int x) {
        if (par[x] < 0) return x;
        return par[x] = root(par[x]);
    }
    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return;
        if (par[rx] > par[ry]) swap(rx, ry);
        par[rx] += par[ry];
        par[ry] = rx;
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    int size(int x) {
        return -par[root(x)];
    }
};

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> S(M);
    rep(i, N) {
        int K;
        cin >> K;
        rep(j, K) {
            int L;
            cin >> L;
            --L;
            S[L].push_back(i);
        }
    }
    UnionFind UF(N);
    rep(i, M) {
        if (S[i].size() < 2) continue;
        rep(j, S[i].size() - 1) UF.unite(S[i][j], S[i][j + 1]);
    }
    if (UF.size(0) == N) cout << "YES\n";
    else cout << "NO\n";
    return 0;
}


Measured memory_bytes: 4608
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();
        int K = sc.nextInt();

        String ans = "No";
        int cnt = 0;

        for (; ; ) {
            if (A < B && B < C) {
                ans = "Yes";
                break;
            }
            if (cnt >= K) {
                break;
            }
            if (A >= B) {
                B = B * 2;
                cnt++;
                continue;
            }
            if (B >= C) {
                C = C * 2;
                cnt++;
                continue;
            }
        }

        System.out.println(ans);
    }
}


Measured memory_bytes: 27088
#include<bits/stdc++.h>
using namespace std;
typedef int sign;
typedef long long ll;
#define For(i,a,b) for(register sign i=(sign)(a);i<=(sign)(b);++i)
#define Fordown(i,a,b) for(register sign i=(sign)(a);i>=(sign)(b);--i)
const int N=2e5+5;
template<typename T>bool cmax(T &a,T b){return (a<b)?a=b,1:0;}
template<typename T>bool cmin(T &a,T b){return (a>b)?a=b,1:0;}
template<typename T>T read()
{
	T ans=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)&&ch!='-')ch=getchar();
	if(ch=='-')f=-1,ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch-'0'),ch=getchar();
	return ans*f;
}
template<typename T>void write(T x,char y)
{
	if(x==0)
	{
		putchar('0'),putchar(y);
		return;
	}
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	static char wr[20];
	int top=0;
	for(;x;x/=10)wr[++top]=x%10+'0';
	while(top)putchar(wr[top--]);
	putchar(y);
}
void file()
{
#ifndef ONLINE_JUDGE
	freopen("B.in","r",stdin);
	freopen("B.out","w",stdout);
#endif
}
int n,a[N];
void input()
{
	n=read<int>();
	For(i,1,n)a[i]=read<int>();
}
void work()
{
	int ans=0;
	sort(a+1,a+n+1);
	Fordown(i,30,0)
	{
		int r=n;
		For(l,1,r)
		{
			while(r>l&&a[r]+a[l]>(1<<i))r--;
			if(r<=l)break;
			if(a[l]+a[r]==(1<<i))a[l]=a[r]=0,ans++,r--;
		}
		int top=0;
		For(i,1,n)if(a[i])a[++top]=a[i];
		n=top;
	}
	write(ans,'\n');
}
int main()
{

	input();
	work();
	return 0;
}


Measured memory_bytes: 1024
a,b=map(int,input().split())

table=[[0]*b for i in range(a)]

for j in range(a):
    l=list(map(int,input().split()))
    for k in range(b):
        table[j][k]=l[k]

for j in range(a):
    sum1=0
    for k in range(b):
        print("%d " %(table[j][k]), end="")
        sum1+=table[j][k]
    print("%d" %(sum1))

sum3=0
for k in range(b):
    sum2=0
    for j in range(a):
        sum2+=table[j][k]
    sum3+=sum2
    print("%d " %(sum2), end="")
print(sum3)


Measured memory_bytes: 6248
#!/usr/bin/env ruby
n = gets.chomp.to_i
s = gets.chomp

ans = 0
0.upto(9) do |i|
  first_i = s.chars.find_index(i.to_s)
  next if first_i.nil?
  0.upto(9) do |j|
    new_s = s[(first_i+1)..-1]
    first_j = new_s.chars.find_index(j.to_s)
    next if first_j.nil?
    0.upto(9) do |k|
      new_new_s = new_s[(first_j+1)..-1]
      first_k = new_new_s.chars.find_index(k.to_s)
      next if first_k.nil?
      ans += 1
    end
  end
end

puts ans


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

struct Node {
    int key;
    Node *parent, *left, *right;
};

Node *root, *NIL;

void insert(int k) {
    Node *x = root;
    Node *y = NIL;
    Node *z;

    z = (Node *)malloc(sizeof(Node));
    z->key = k;
    z->left = NIL;
    z->right = NIL;

    while (x != NIL) {
        y = x;
        if (z->key < x->key) {
            x = x->left;
        } else {
            x = x->right;
        }
    }

    z->parent = y;
    if (y == NIL) {
        root = z;
    } else {
        if (z->key < y->key) {
            y->left = z;
        } else {
            y->right = z;
        }
    }
}

Node * find(Node *u, int k) {
    while (u != NIL && u->key != k) {
        if (k < u->key) {
            u = u->left;
        } else {
            u = u->right;
        }
    }
    return u;
}

void inorder(Node *u) {
    if (u == NIL)
        return;
    inorder(u->left);
    printf(" %d", u->key);
    inorder(u->right);
}

void preorder(Node *u) {
    if (u == NIL)
        return;
    printf(" %d", u->key);
    preorder(u->left);
    preorder(u->right);
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        if (s == "insert") {
            int x;
            cin >> x;
            insert(x);
        } else if (s == "find") {
            int k;
            cin >> k;
            if (find(root, k) != NIL) {
                cout << "yes" << endl;
            } else {
                cout << "no" << endl;
            }
        } else {
            inorder(root);
            cout << endl;
            preorder(root);
            cout << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 22012
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
signed main()
{
	 ios_base::sync_with_stdio(false);
	 cin.tie(NULL);
	 cout.tie(NULL);
	 int a,b,c,d;
	 cin>>a>>b>>c>>d;
	 cout<<max(a*b,c*d)<<endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;
int main(int argc, char *argv[]) {
    	int n,x,i;
		int m[100];
		int add = 0;
		int count = 0;
		scanf("%d %d",&n,&x);
		for(i = 0; i < n;i++){
			scanf("%d",&m[i]);
			add += m[i];
		}
		count = n;
		x -= add;
		sort(m,m+n);
		
		i = 1;
		while((x - m[0] * i) >= 0){
			i++;
		}

		count += i-1;

		printf("%d\n",count);
		
}

Measured memory_bytes: 256
n = gets
*array = gets.chomp.split(' ').map(&:to_i)
puts array.join(' ')

class Array
  def swap!(a, b)
    self[a], self[b] = self[b], self[a]
    self
  end
end

array.each_with_index do |key, key_index|
  next if key_index.zero?
  array[0..key_index].each_with_index do |comp, comp_index|
    if key < comp
      array.swap! key_index, comp_index
      next
    end
  end
  puts array.join(' ')
end


Measured memory_bytes: 6948
#include <bits/stdc++.h>
using namespace std;
int n,cnt,ans;
string s;
int main()
{
	int i;
    cin>>n>>s;
    for(i=0;i<n;i++)
        if(s[i]=='W')
            cnt++;
    for(i=n-cnt;i<n;i++)
        if(s[i]!='W')
            ans++;
    cout<<ans;
    return 0;
}

Measured memory_bytes: 3736
#include <iostream>
#include <algorithm>
using namespace std;
 
int main(void) {
  int N;
  int a[300010];
  cin >> N;
  for (int i = 0; i < 3*N; i++) cin >> a[i];
  sort(a, a+3*N, greater<int>());
  //reverse(a, a+3*N);
  long int sum = 0;
  for (int i = 1; i < 2*N; i += 2) {
    sum += a[i];
    //cout << a[i] << endl;
  }
  cout << sum << endl;
  
  return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
using ll = long long;
constexpr i64 INF = 1010000000000000017LL;
constexpr i64 MOD = 1000000007LL;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))
template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) xmax = x; return true;
    return false;
}
template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) xmin = x; return true;
    return false;
}
struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;
    ProconInit() {
        cin.tie(nullptr); ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH) cout << unitbuf;
    }
} PROCON_INIT;

void solve() {
    ll n; cin >> n;
    vector<ll> a(n); FOR(i, 0, n) cin >> a[i];

    ll ret = 0;
    ll right = 0;
    ll sum = 0;
    FOR(left, 0, n) {
        while (right < n && (sum ^ a[right]) == (sum + a[right])) {
            sum += a[right];
            ++right;
        }
        ret += right - left;

        if (left == right) ++right;
        else sum -= a[left];
    }
    cout << ret << endl;
}

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

Measured memory_bytes: 1792
import bisect
def main():
    A, B, Q = map(int, input().split())
    s = []
    for _ in range(A):
        s.append(int(input()))
    t = []
    for _ in range(B):
        t.append(int(input()))
    for _ in range(Q):
        x = int(input())
        i = bisect.bisect_left(s, x)
        j = bisect.bisect_left(t, x)
        if i == 0:
            i_d = [s[i] - x]
        elif i == A:
            i_d = [s[i-1] - x]
        else:
            i_d = [s[i-1] - x, s[i] - x]
        if j == 0:
            j_d = [t[j] - x]
        elif j == B:
            j_d = [t[j-1] - x]
        else:
            j_d = [t[j-1] - x, t[j] - x]
        m = 10**12
        for y in i_d:
            for z in j_d:
                if y * z < 0:
                    m = min(m, abs(y)*2 + abs(z), abs(y) + abs(z)*2)
                else:
                    m = min(m, max(abs(y), abs(z)))
        print(m)
main()


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

int main(){
  int n; cin>>n;
  map<int,int> mp;
  rep(i,n){
    int a; cin>>a;
    if(mp[a]!=0){
      mp[a]=0;
    }else{
      mp[a]=1;
    }
  }
  int ans=0;
  for(auto x : mp){
    if(x.second==1){
      ans++;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 8160
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
vector<lint> zyo,rz;
lint mo=998244353;
lint extgcd(lint a, lint b, lint &x, lint &y) {
  lint g = a; x = 1; y = 0;
  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
  return g;
}
lint invMod(lint a, lint m) {
  lint x, y;
  if (extgcd(a, m, x, y) == 1) return (x + m) % m;return 0;
}
lint co(int a,int b){
	if(a<0 || b<0 || a<b) return 0;
	return ((zyo[a]*rz[b])%mo*rz[a-b])%mo;
}
int main()
{
	int n;lint a,b,k,out=0;
	cin>>n>>a>>b>>k;
	zyo.pb(1);rep(i,300100) zyo.pb((zyo[i]*(i+1))%mo);
	rep(i,300100) rz.pb(invMod(zyo[i],mo));
	rep(i,n+1){
		if((k-a*i)%b!=0) continue;
		lint nb=(k-a*i)/b;
		if(nb<0 || nb>n) continue;
		//cout<<i<<' '<<nb<<endl;
		out+=co(n,i)*co(n,nb);
		out%=mo;
	}
	cout<<out%mo<<endl;
}


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

#define SORT(v) sort(v.begin(),v.end())
#define si(n) scanf("%d",&n)
#define sii(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define ss(cad) scanf("%s",cad)
#define PB push_back
#define fst first
#define scn second
#define DBG(x) cerr << #x << " = " << (x) << endl; 
#define M 1000000007
#define N_MAX 100010

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef pair<int,int> pi;
typedef vector<pi> vp;

char cad[100];

int main(){
	int n;
	si(n);
	ss(cad);
	vector<pi> vec1(1<<n), vec2(1<<n);
	map<string, int> mapa;
	int pos = 0;
	for(int mask = 0; mask < (1<<n); mask++){
		string a, b;
		for(int i = n-1; i >= 0; i--){
			if((mask&(1<<i)) == 0)
				a.push_back(cad[n-1-i]);
			else
				b.push_back(cad[n-1-i]);
		}
		reverse(b.begin(), b.end());
		if(mapa.count(a) == 0)
			mapa[a] = pos++;
		if(mapa.count(b) == 0)
			mapa[b] = pos++;
		vec1[mask] = {mapa[a], mapa[b]};
	}

	for(int mask = 0; mask < (1<<n); mask++){
		string a, b;
		for(int i = n-1; i >= 0; i--){
			if((mask&(1<<i)) == 0)
				a.push_back(cad[n+n-1-i]);
			else
				b.push_back(cad[n+n-1-i]);
		}
		reverse(b.begin(), b.end());
		if(mapa.count(a) == 0)
			mapa[a] = pos++;
		if(mapa.count(b) == 0)
			mapa[b] = pos++;
		vec2[mask] = {mapa[b], mapa[a]};
	}
	sort(vec1.begin(), vec1.end());
	sort(vec2.begin(), vec2.end());
	ll ans = 0;
	for(int i = 0; i < vec1.size(); i++){
		int cnt = upper_bound(vec2.begin(), vec2.end(), vec1[i]) - lower_bound(vec2.begin(), vec2.end(), vec1[i]);
		ans += cnt;
	}
	printf("%lld\n", ans);	
	return 0;
}


Measured memory_bytes: 71368
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
#define sim template < class c
#define int long long
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << '\n'; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
typedef tree< pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
const ll MOD = 1e9 + 7 ;
const ll N = 2e5 + 10 ;
const ll INF = 1e18 + 10 ;
string s ;
int k ; 
int n ; 
int dp[101][101][3] ;
int dfs(int x, int cur, int flag){
    if ( x == n ){
        if ( cur == k ) return 1;
        return 0 ;
    }
    if ( dp[x][cur][flag] != -1 ) return dp[x][cur][flag] ;
    int ans = 0 ;
    int digit = s[x] - '0' ;
    if ( !flag ){
        for(int i = 0; i <= digit; i++){
            if ( i == digit ){
                if ( i == 0 ){
                    ans += dfs(x + 1, cur, 0) ;
                }
                else{
                    ans += dfs(x + 1, cur + 1, 0) ;
                }
            }
            else{
                if ( i == 0 ){
                    ans += dfs(x + 1, cur, 1) ;
                }
                else{
                    ans += dfs(x + 1, cur + 1, 1) ;
                }
            }
        }
    }
    else{
        for(int i = 0; i <= 9; i++){
            if ( i == 0 ) {
                ans += dfs(x + 1, cur, flag) ;
            }
            else ans += dfs(x + 1, cur + 1, flag) ;
        }
    }
    return dp[x][cur][flag] = ans ; 
}
signed main(){
    fastio
    memset(dp, -1 , sizeof dp) ;
    cin >> s >> k ; 
    n = (int) s.size() ;
    int ans = dfs(0, 0, 0) ;
    cout << ans << endl ;
    return 0; 
}

Measured memory_bytes: 3872
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b; }
template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b; }
void debug_out() { cout << "\n"; }
template <class T, class... Args>
void debug_out(const T &x, const Args &... args) { cout << x << " "; debug_out(args...);}
#ifdef _DEBUG
  #define debug(...) debug_out(__VA_ARGS__)
#else
  #define debug(...) 
#endif

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  ll h,w;
  cin >> h >> w;
  if (h % 3 == 0 || w % 3 == 0) {
    cout << 0 << endl;
    return 0;
  }
  ll ans = 1LL<<60;
  for (ll x = 1; x < w; ++x) {
    vector<ll> S = {((h+1)/2)*x, h*(w-x), h*w - ((h+1)/2)*x - h*(w-x)};
    sort(all(S));
    chmin(ans, llabs(S[0] - S[2]));
    S = {h*x, h*((w-x+1)/2), h*w - h*x - h*(w-x+1)/2};
    sort(all(S));
    chmin(ans, llabs(S[0] - S[2]));
  }
  swap(h,w);
  for (ll x = 1; x < w; ++x) {
    vector<ll> S = {((h+1)/2)*x, h*(w-x), h*w - ((h+1)/2)*x - h*(w-x)};
    sort(all(S));
    chmin(ans, llabs(S[0] - S[2]));
    S = {h*x, h*((w-x+1)/2), h*w - h*x - h*(w-x+1)/2};
    sort(all(S));
    chmin(ans, llabs(S[0] - S[2]));
  }
  cout << ans << endl;
  return 0;
}

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

int M,N;
bool T[8000001];

int solve() {
	for (int i = 0; i < 8000000; i++) T[i] = false;
	int m = M;
	while (1) {
		if (T[m] == false) {
			if (N == 0) {
				cout << m << endl;
				return 0;
			}
			N--;
			int m2 = m * 2;
			while (m2 < 8000000) {
				T[m2] = true;
				m2 += m;
			}
		}
		m++;
	}
}

int main() {
	cin >> M >> N;
	while (M) {
		solve();
		cin >> M >> N;
	}
}


Measured memory_bytes: 10904
#include <bits/stdc++.h>
using namespace std;
#define reps(i, a, n) for (int i = (a); i < (n); ++i)
#define rep(i, n) reps(i, 0, n)
#define deps(i, a, n) for (int i = (a); i >= (n); --i)
#define dep(i, n) deps(i, n, 0)
#define inf 2147483647
#define int long long

signed main(void)
{
	int x; cin >> x;
	if (x) cout << "0" << endl;
	else cout << "1" << endl;
}


Measured memory_bytes: 3620
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

struct packet {
	int t, s, d;
	packet(int t = 0, int s = 0, int d = 0):t(t), s(s), d(d) {}

	bool operator<(const packet& p) const {
		return t < p.t;
	}
};

const int MAX = 20001;
bool infected[MAX];

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

	for(int n, m; cin >> n >> m, n;) {
		vector<packet> packets;
		packets.reserve(m);
		for(int i = 0; i < m; ++i) {
			int t, s, d;
			cin >> t >> s >> d;
			packets.push_back(packet(t, s, d));
		}

		sort(packets.begin(), packets.end());
		memset(infected, false, sizeof(infected));
		infected[1] = true;
		for(int i = 0; i < m; ++i)
			infected[packets[i].d] |= infected[packets[i].s];

		cout << count(infected, infected + MAX, true) << endl;
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1472
import           Control.Applicative
import           Control.Monad
import qualified Data.Vector                   as V

main :: IO ()
main = do
  n  <- readLn
  bs <- replicateM n readLn

  print $ f n (V.fromList bs) 1 [0 ..]

f n bs o (i : is) | i > n              = -1
                  | bs V.! (o - 1) == 2 = i + 1
                  | otherwise          = f n bs (bs V.! (o - 1)) is

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

int main() {
	int k;
	string s;
	cin >> k >> s;
	if (s.size() <= k) cout << s << endl;
	else {
		rep(i, k) {
			cout << s[i];
		}
		cout << "..." << endl;
	}
	return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long> vll;
typedef vector<vll> vvll;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<pair<long long,long long> > vpll;
typedef vector<vector<pair<ll,ll> > > vvpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;

#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define all(x) x.begin() , x.end()
#define pb push_back
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define F first
#define S second
#define left (node << 1)
#define right (node << 1) + 1
#define pii pair<int,int> 
#define mii map<int,int>
#define vi vector<int>
#define umii unordered_map<int,int>
#define mod1 998244353
#define mod2 1000000007
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<": " <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define FILL(name,val) memset(name , val , sizeof(name))
#define repo(i,o,e) for(int i = o ; i < e ; i++)
#define rep(n) for(int i = 0 ; i < n ; i++)
const ll sz = 2e5+5;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

const ll inf = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;

void solve(){
    ll n , W;
    cin >> n >> W;
    ll dp[n+1][W+1];
    ll wt[n] , val[n];
    rep(n){
        cin >> wt[i] >> val[i];
    }
    for(int i = 0 ; i <= n ; ++i){
        for(int w = 0 ; w <= W ; ++w){
            if(i == 0 or w == 0){
                dp[i][w] = 0;
            }
            else if(wt[i-1] <= w){
                dp[i][w] = max(val[i-1] + dp[i-1][w - wt[i-1]] , dp[i-1][w]);        
            }
            else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    cout << dp[n][W] << endl;
    return;
}



int main(){
     FIO;
    //     freopen("input.txt", "rt", stdin);
    //     freopen("output.txt", "wt", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 79232
#include <bits/stdc++.h>
//For ordered_set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define MOD 1000000007
#define test int t; cin>>t; while(t--)
#define init(arr,val) memset(arr,val,sizeof(arr))
#define loop(i,a,b) for(int i=a;i<b;i++)
#define loopr(i,a,b) for(int i=a;i>=b;i--)
#define loops(i,a,b,step) for(int i=a;i<b;i+=step)
#define looprs(i,a,b,step) for(int i=a;i>=b;i-=step)
#define ull unsigned long long int
#define ll long long int
#define P pair
#define PLL pair<long long, long long>
#define PII pair<int, int>
#define PUU pair<unsigned long long int, unsigned long long int>
#define L list
#define V vector
#define D deque
#define ST set
#define MS multiset
#define M map
#define UM unordered_map
#define mp make_pair
#define pb push_back
#define pf push_front
#define MM multimap
#define F first
#define S second
#define IT iterator
#define RIT reverse_iterator
#define FAST ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define FILE_READ_IN freopen("input.txt","r",stdin);
#define FILE_READ_OUT freopen("output.txt","w",stdout);
#define all(a) a.begin(),a.end()
using namespace std;
// For ordered_set
using namespace __gnu_pbds;
template <typename T>
using ord_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll maxn = 1e5;
const ll inf = 1e9;
const double pi = acos(-1);

void solve()
{
    int n,q; cin >> n >> q;
    string s; cin >> s;
    int sum[n] = {0};
    int count = 0;
    loop(i,1,s.size())
    {
        if (s[i] == 'C')
        {
            if (s[i-1]=='A')
            {
                count++;
                sum[i] = count;
            }
            else
            {
                sum[i] = count;
            }
        }
        else
        {
            sum[i] = count;
        }
        
    }

    // for (int i = 0; i < n; i++)
    // {
    //     cout << sum[i] << " ";
    // }
    

    loop(i,0,q)
    {
        int l,r; cin >> l >> r;
        cout << sum[r-1] - sum[l-1] << "\n";
    }
}

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

Measured memory_bytes: 1488
N = int(input())
S = input()

w = [0] * N
b = [0] * N
wc = 0
bc = 0
for i in range(N):
  if S[i] == "#":
    wc += 1
  w[i] = wc
for i in range(N - 1, -1, -1):
  if S[i] == ".":
    bc += 1
  b[i] = bc

Ans = w[N - 1]
for i in range(N):
  t = 0
  if i > 1:
    t += w[i - 1]
  t += b[i]
  Ans = min(Ans, t)
print(Ans)


Measured memory_bytes: 12808
s = input()
t = input()
List=[]
ListS= list(s)
ListT = list(t)
ListS.sort()
ListT.sort(reverse= True)
S = ""
T = ""
for i in range(len(ListS)):
  S += ListS[i]  
for i in range(len(ListT)):
  T += ListT[i]
if S == T:
  print("No")
else:
  List.append(S)
  List.append(T)
  List.sort()
  if List[0]==S:
    print("Yes")
  else:
    print("No")

Measured memory_bytes: 9080
#include <stdio.h>
#include <ctype.h>

int main(void){
    char s;
    int ch;
    while(1){
        s = getchar();
        if (s=='\n') break;
        if (islower(s)!=0) {
            ch=toupper(s);
            printf("%c",ch);
        } else {
            printf("%c",s);
        }
    }
    printf("\n");
    return 0;
}

Measured memory_bytes: 524
#include <bits/stdc++.h>
#define MAXS 500007
#define INF 2147483647

#define mp(a, b) make_pair(a,b)
#define pb(a) push_back(a)
#define INP freopen("input.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define STREE int bch = no*2, mid = (l+r)/2
#define ALL(a) a.begin(), a.end()

using namespace std;
typedef long long ll;
typedef vector < int > vi;
typedef pair < int, int > pii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n;
ll arr[MAXS];
ll dp[MAXS];



int main(){
  // cin >> n;
  // memset(arr, 0, sizeof arr);
  // for(int i = 1; i <= n; ++i){
  //   cin >> arr[i];
  // }
  // memset(dp, -1, sizeof dp);
  // dp[0] = dp[1] = 0;
  // for(int i = 2; i <= n; ++i){
  //   dp[i] = min(dp[i-1]+abs(arr[i]-arr[i-1]), dp[i-2]+abs(arr[i] - arr[i-2]));
  // }
  cin>>n;
    for(int i = 1; i <= n; i++)
        cin>>arr[i];
    dp[1] = 0;
    for(int i = 2; i <= n; i++){
        dp[i] = dp[i-1] + abs (arr[i] - arr[i-1]);
        if(i > 2){
            dp[i] = min(dp[i], dp[i-2] + abs(arr[i] - arr[i-2]));
        }
    }
    cout << dp[n]<<endl;
  // cout << dp[n] << endl;
}

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

typedef long long int ll;

using namespace std;

int main(void)
{
    vector<string> s;

    string temp;
    cin>>temp;
    s.push_back(temp);
    cin>>temp;
    s.push_back(temp);
    cin>>temp;
    s.push_back(temp);

    int prev=0,next = 0;
    while(!s[next].empty())
    {
	prev = next;
	next = s[next][0]-'a';
	s[prev].erase(s[prev].begin());
    }

    if(next == 0)
	cout<<"A"<<endl;
    else if(next == 1)
	cout<<"B"<<endl;
    else
	cout<<"C"<<endl;

    return 0;
}



Measured memory_bytes: 256
n = int(input())
A = list(map(int,input().split()))
ans = 0
temp = [A[0]]

for a in A[1:]:
    if a != temp[-1]:
        if len(temp)>=2:
            ans += int(len(temp)/2)
            temp.clear()
        else:
            temp.clear()
    temp.append(a)
    

ans += int(len(temp)/2)
            
print(ans)

Measured memory_bytes: 3064
N = int(input())
S = list(input())
Q = int(input())

l = 2**((N-1).bit_length())
#data = [Counter([]) for i in range(2*l)]
data = [0] * (2*l)

str2bin = lambda x : 1 << (ord(x) - ord('a'))
    
for i in range(N):
    data[l+i] = str2bin(S[i])
for i in range(l-1,0,-1):
    data[i] = data[2*i] | data[2*i+1]

for cnt in range(Q):
    a,b,c = input().split()
    a = int(a)
    b = int(b)
    if a == 1:
        n = l + b - 1
        data[n] = str2bin(c)
        n //= 2
        while n > 0:
            data[n] = data[2*n] | data[2*n+1]
            n = n // 2
    else:
        c = int(c)
        i = b + l -1
        j = c + l
        res = 0
        while j-i > 0:
            if i & 1:
                res |= data[i]
                i += 1
            if j & 1:
                res |= data[j-1]
                j -= 1
            i //= 2
            j //= 2
        print(bin(res).count('1'))



Measured memory_bytes: 99688