akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <deque>
#include <queue>
#include <functional>
//#include <boost/multiprecision/cpp_int.hpp>

#define rep(i, n) for(int i = 0; i < n; ++i)
#define REP(i, m, n) for(int i = m; i < n; ++i)
#define rrep(i,n) for(int i = n; i >= 0; --i)
#define RREP(i, m, n) for(int i = n; i >= m; --i)
#define llrep(i, n) for(ll i = 0; i < n; ++i)
#define llREP(i, m, n) for(ll i = m; i < n; ++i)
#define llrrep(i,n) for(ll i = n; i >= 0; --i)
#define llRREP(i, m, n) for(ll i = n; i >= m; --i)

using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<long long, long long>;
using pil = std::pair<int, long long>;
using pli = std::pair<long long, int>;
using plpii = std::pair<long long, std::pair<int, int>>;
using pdd = std::pair<double, double>;

const long long INF = 1000000000000000001;
const long long _MOD = 1000000007;
const long long MOD = 998244353;
const int ALPHABET = 27;
const double pi = 3.14159265358979;

using namespace std;
//namespace mp = boost::multiprecision;

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

	int n;
	cin >> n;
	ll* a = new ll[n];
	rep(i, n) cin >> a[i];
	ll sum = 0;
	rep(i, n) sum += a[i];
	ll l, r = 0;
	rep(i, n) {
		l = r;
		r += a[i];
		if (r * 2 >= sum) break;
	}

	cout << min(min(sum-l*2, (sum-l)*2-sum), min(r * 2 - sum, r - (sum - r))) << "\n";
}

Measured memory_bytes: 1792
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <bitset> 
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
 
#define int long long
#define ll long long 
#define F first
#define sqr(x) ((x) * (x))
#define S second
#define make make_pair
#define pb push_back
#define sz(x) (ll)(x.size()) 
#define all(x) x.begin (), x.end ()

using namespace std;
                        
typedef unsigned long long ull;
typedef long double ld;

const int MOD = (int)1e9 + 7;
const int MOD1 = (int)1e9 + 9;
const int N = (int)2e6+ 222;
const ll INF = (ll)1e18;
const int p = 997, p1 = 991;
const double eps = (double)1e-6;
     
int a[N];
int m, k;
int used[N];

int lg2 (int x) {
	int res = 0;
	while (x) {
		res ++;
		x /= 2;
	}
	return res - 1;
}
             
void solve () {                                                
	cin >> m >> k;
	if (m == 1 && k != 0) {
		cout << -1;
		return;
	}
	if (k == 0) {
		int pos = 0;
		for (int i = 1; i <= (1 << (m + 1)); i += 2) {
			cout << pos << " " << pos << " ";
			pos ++;		
       	}
       	return;
	}
	if ((1 << m) - 1 < k) {
		cout << -1;
		return;	
	}
	
	cout << 0 << " " << k << " " << 0 << " ";
	for (int i = 1; i <= (1 << m) - 1; ++i) {
		if (k != i) cout << i << " ";
	}	
	cout << k << " ";
	for (int i = (1 << m) - 1; i >= 1; --i) {
		if (k != i) cout << i << " ";
	}
}


signed main () {
    #ifdef Maga
        //freopen("input", "r", stdin);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);                                              
    int t = 1;
    while (t --) {
    	solve ();
    }
    return 0;
}





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

#define rep(X,N) for(ll X = 0; X < (N); X++)
#define PI (acos(-1.0))
#define pback push_back
#define mpair make_pair
#define MODN 1000000007
#define ALL(V) (V).begin(),(V).end()
#define CERR if(false) cerr
#define INT_MAX_HALF (INT_MAX / 2)
#define EPS (1e-10)

using namespace std;

typedef long long ll;

template<typename T>
class SegmentTree{
public:

    int basic_size;
    int segtree_size;
    function<T(T,T)> merge_function;
    vector<T> v;

    SegmentTree(){

    }

    SegmentTree(vector<T> &basic_v, function<T(T,T)> f){

        merge_function = f;
        basic_size = basic_v.size();

        segtree_size = 1;

        while(segtree_size < basic_size){
            segtree_size = segtree_size * 2;
        }
        segtree_size = segtree_size * 2;

        v = vector<T>(segtree_size);

        for(int i = segtree_size / 2; i < segtree_size / 2 + basic_size; i++){
            v[i] = basic_v[i - segtree_size / 2];
        }
    }

    T geti(int left, int right, int left_bound, int right_bound, int index){

        if(left == left_bound && right == right_bound){
            return v[index];
        }

        int middle = (left_bound + right_bound) / 2;

        if(right <= middle){

            return geti(left, right, left_bound, middle, index * 2);

        }else if(middle < left){

            return geti(left, right, middle + 1, right_bound, index * 2 + 1);

        }

        T a = geti(left, middle, left_bound, middle, index * 2);
        T b = geti(middle + 1, right, middle + 1, right_bound, index * 2 + 1);

        return merge_function(a,b);
    }
    
    T get(int left, int right){
        return geti(left, right, 0, segtree_size / 2 - 1, 1);
    }

    void updatei(int index){

        v[index] = merge_function(v[index * 2], v[index * 2 + 1]);

        if(index != 1){
            updatei(index / 2);
        }

    }

    void update(int index, T datum){

        int segtree_index = index + segtree_size / 2;
        v[segtree_index] = datum;

        updatei(segtree_index / 2);
    }

};


int main(){

    int n,q;
    string s;
    cin >> n;
    cin >> s;
    cin >> q;

    if(n > 1){


    vector<int> initv(n);

    rep(i, n){
        int tmp = (1<<(s[i] - 'a'));

        initv[i] = tmp;

    }

    function<int (int, int)> f = [&](int a, int b) -> int{

        return a | b;
    }; 

    SegmentTree<int> st(initv, f);

    rep(i, n){
        st.update(i, st.get(i, i));
    }

    rep(i, q){
        int qi;
        cin >> qi;

        if(qi == 1){
            int iq;
            char cq;
            cin >> iq >> cq;

            int tmp = (cq - 'a');

            st.update(iq - 1, (1<<tmp));
        }else{
            int l,r;
            cin >> l >> r;

            int tmp = st.get(l - 1, r - 1);

            cout << __builtin_popcount(tmp) << endl;

        }

    }
    }else{

        rep(i, q){
            int tmp1, tmp2, tmp3;
            cin >> tmp1 >> tmp2 >> tmp3;

            if(tmp1 == 2) cout << 1 << endl;
        }
    }


    return 0;
}


Measured memory_bytes: 6916
#include <bits/stdc++.h>
typedef long long ll;
#define ALL(l)  (l).begin(),(l).end()
#define rep(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
using namespace std;

//const ll mod =  1000000007;
//const ll maxn = 1000000000;

//---------------------------------------------------------------------------------------------------
using vi = vector<int>; // intの1次元の型に vi という別名をつける
using vll = vector<ll>; // long longの1次元の型に vll という別名をつける
using vvll = vector<vll>; // long longの2次元の型に vvll という別名をつける
using vs = vector<string>; // stringの1次元の型に vs という別名をつける
using pll = pair<ll, ll>; // これ以降 pll という型名はpair<ll, ll> と同じ意味で使える
//---------------------------------------------------------------------------------------------------


int main() {
 vvll dp(2001,vll(2001,0));//桁数、合計
 ll s;
 cin>>s;
 
 dp.at(0).at(0)=1;
 rep2(i,1,s/3+1){
     rep2(j,0,s-2){
         if(dp.at(i-1).at(j)==0)continue;
         rep2(k,3,s+1){
             if(j+k<2001){
                dp.at(i).at(j+k)+=dp.at(i-1).at(j);
                dp.at(i).at(j+k) %=1000000007;
             }
         }
     }
 }

 
 ll ans=0;
 rep2(i,1,2001){
     ans+=dp.at(i).at(s);
     //cout<<i<<" "<<ans<<endl;
     ans%=1000000007;
 }

 cout<<ans<<endl;

}



Measured memory_bytes: 34488
// When you are hungry for something and you're determined and you're focused 
// and you're committed to something it's hard to surrender, isn't it?

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ll long long 
#define int ll
#define mod 1000000007
#define mod1 1000000006
#define modi 998244353
#define ff first
#define ss second
#define pb push_back
vector<ll> vi[300005];
int color[100005];
ll pa[500005];
ll si[500005];
#define pb push_back
bool visi[1000005]={false};
bool is[100005];
ll fac[10000001];
ll prime[400005];
ll bit[100005];
const long double eps = 1.0e-14;      // allowable error
#define fio ios_base::sync_with_stdio(false); cin.tie(NULL);
 
 
void fact(){
    fac[0]=1;
    for(int i=1;i<=10000000;i++){
        fac[i]=(fac[i-1]*i)%mod;
    }
    return ;
}
void sieve(){
    prime[0]=0;
    prime[1]=0;
    for(int i=2;i<400005;i++){
        prime[i]=1;
    }
    for(int i=2;i*i<400005;i++){
        if(prime[i]==1){
            for(int j=i*i;j<400005;j+=i){
                prime[j]=0;
            }
        }
    }
    
}
 
ll power(ll n , ll p ){
    if(p==0)
        return 1;
    
    ll res = power((n*n)%mod,p/2);
    if(p%2==1)
        res = (n*res)%mod;
    
    return res;
}
 
 
void upd(ll i,ll val,ll n) {
    for(;i<=n;i+=i&(-i))
        bit[i]+=val;
}
 
ll qry(ll i) {
    ll sum=0;
    for(;i>0;i-=i&(-i))
        sum+=bit[i];
    return sum;
}
 
 
ll fin(ll u) {
    if(pa[u]==u)
        return u;
    return fin(pa[u]);
}
 
void uni(ll u,ll v) {
    ll p1=fin(u);
    ll p2=fin(v);
    if(p1==p2)
        return;
    if(si[p1]<si[p2])
        swap(p1,p2);
    si[p1]+=si[p2];
    pa[p2]=p1;
    return;
}

bool check(string s) {
    
    int n=s.size(),flag=0;
    
    for(int i=0;i<n;i++){
        if(s[i]!=s[n-i-1]){
            flag = 1;
            break;
        }
    }
    if(flag)
    return false;
    else
    return true;
    
}
 
int32_t main() {
    fio

    string s;
    cin >> s;
    
    if(check(s)==true) {
        int n = s.size();
        int x = (n-1)/2;
        int y = (n+3)/2;
        string s1 = s.substr(0,x);
        string s2 = s.substr(y-1);
        
        if(check(s1)==true and check(s2)==true)
        cout << "Yes" << endl;
        else
        cout << "No" << endl;
        
    }
    else
    cout << "No" << endl;
    

	return 0;
    
}

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

int main() {
  int A, B;
  int counter = 0;
  cin >> A >> B;
  
  for(A; A<=B; A++){
    if(A/10000 == A%10 && (A/1000)%10 == (A%100)/10){
      counter++;
    }
  }
  
  cout << counter << endl;
}


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

over = 0
ans_f = 0
ans_e = 0
for c in s:
    if c == "(":
        over += 1
    else:  # )
        if over > 0:
            over -= 1
        else:
            ans_f += 1

ans_e = over

ans = ("(" * ans_f) + s + (")" * ans_e)
print(ans)


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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
template<typename T> using pq = priority_queue<T>;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto& i:mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template<class T>
void dump_debug(T list) {
#ifdef MY_DEBUG
    each(e, list) cout << e << " ";
    printf("\n");
#endif
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        ll a, b;
        cin >> a >> b;
        cout << max({a + b, a - b, a * b}) << endl;
#ifdef MY_DEBUG
    }
#endif
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int n = 0;
    cin >> n;
    int a[n];
    for (int i=0; i<n; i++)
        cin >> a[i];
    for (int j=n-1; j>=0; j--) {
        if (j!=0) {
        cout << a[j] << ' ';
        } else {
            cout << a[j];
        }
    }
    cout << endl;
}

Measured memory_bytes: 3064
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
#include<bits/stdc++.h>
#include<bitset>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please
 
const int cm = 1 << 16;
char cn[cm], * ci = cn, ct;
inline int getint() {
    int A = 0;
    while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
    return A;
}
 
//bitset使ったことほぼないなぁ
bitset<6500> dp1[81];
 
int main() {
    //cin.tie(0);
    //ios::sync_with_stdio(false);
 
 
    fread(ci, 1, cm, stdin);
    int H, W;
    H = getint(), W = getint();
    char AB[80][80];
    rep(i, H) rep(j, W) {
        AB[i][j] = getint();
    }
    rep(i, H) rep(j, W) {
        AB[i][j] = abs(AB[i][j] - getint());
    }
 
    dp1[0][0] = true;
    for (int hw = 0; hw <= H + W - 2; hw++) {
        for (int w = min(hw, W - 1); w >= max(0, hw - H + 1); w--) {
            int h = hw - w;
            dp1[w] |= dp1[w] << AB[h][w] * 2;
            rep1(i, AB[h][w]) dp1[w][AB[h][w] + i] = (dp1[w][AB[h][w] + i] | dp1[w][AB[h][w] - i]);
            dp1[w] >>= AB[h][w];
            dp1[w + 1] |= dp1[w];
        }
    }
 
 
    rep(i, 81) {
        if (dp1[W - 1][i]) {
            printf("%d\n", i);
            return 0;
        }
    }
 
    Would you please return 0;
}

Measured memory_bytes: 384
a,b = map(int,input().split())
if a == b == 1:
    print("Draw")
elif a == 1:
    print("Alice")
elif b == 1:
    print("Bob")
else:
    if a > b:
        print("Alice")
    elif a < b:
        print("Bob")
    elif a == b:
        print("Draw")

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

const int N = 1e5;
const int M = 2 * (int)1e5;
vector<int> conns[N];
int dist[M];
int dep[N];

void dfs(int i, string& col) {
	for (int t : conns[i]) {
		if (dep[t] >= dep[i] && col[t] == '_') {
			col[t] = (col[i] == 'W' ? 'B' : 'W');
			dfs(t, col);
		}
	}
}

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

	int n, m;
	cin >> n >> m;

	vector<pair<int, int>> ds(n);
	for (int i = 0; i < n; ++i) {
		cin >> dep[i];
		ds[i] = {dep[i], i};
	}
	sort(ds.begin(), ds.end());
	int d0 = ds[0].first;

	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		conns[a].push_back(b);
		conns[b].push_back(a);
		dist[i] = max(dep[a], dep[b]);
	}

	bool fail = false;
	string col(n, '_');
	for (auto pr : ds) {
		int i = pr.second;
		if (col[i] == '_') {
			col[i] = 'W';
			dfs(i, col);
		}
		bool works = false;
		for (int t : conns[i]) works |= (dep[t] <= dep[i]);
		fail |= !works;
	}

	if (fail) {
		cout << -1 << '\n';
	} else {
		cout << col << '\n';
		for (int i = 0; i < m; ++i) cout << dist[i] << ' '; cout << '\n';
	}
}


Measured memory_bytes: 11392
#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *r;
  struct node *l;
  struct node *p;
  int key;
};
typedef struct node * Node;

Node root;

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

  z = malloc(sizeof(struct node));
  z->key = k;
  z->l = NULL;
  z->r = NULL;

  while(x!=NULL){
    y=x;
    if(z->key < x->key){
      x=x->l;
    }
    else {
      x=x->r;
    }
         }
  z->p=y;
  if(y==NULL){
    root=z;
  }
  else{
    if(z->key < y->key){
      y->l=z;
    }
    else{
      y->r=z;
    }
  }


}

void inorder(Node u){
  if(u==NULL)return ;
  inorder(u->l);
  printf(" %d",u->key);
  inorder(u->r);

}
void preorder(Node u){
  if(u==NULL)return ;
  printf(" %d",u->key);
  preorder(u->l);
  preorder(u->r);
}


int main(){
  int n, i, x;
  char c[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", c);
    if ( c[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( c[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }

  return 0;
}



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

using namespace std;
typedef long long ll;
typedef long int li;
typedef long double lb;
#define rep(i,j,n) for (ll i = j; i < (n); i++)
#define repr(i,j,n) for(ll i = j; i >= (n); i--)
#define all(x) (x).begin(),(x).end()
#define CLR(mat,f) memset(mat, f, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const ll INF = 1LL<<60;

int main(){

  ll s[6];rep(i,0,6)cin>>s[i];
  string o;cin>>o;

  rep(i,0,o.size()){
    char c=o[i];
    int b;
    if(c=='E'){
      b=s[0];
      s[0]=s[3];
      s[3]=s[5];
      s[5]=s[2];
      s[2]=b;
    }
    if(c=='W'){
      b=s[0];
      s[0]=s[2];
      s[2]=s[5];
      s[5]=s[3];
      s[3]=b;
    }
    if(c=='N'){
      b=s[0];
      s[0]=s[1];
      s[1]=s[5];
      s[5]=s[4];
      s[4]=b;
    }
    if(c=='S'){
      b=s[0];
      s[0]=s[4];
      s[4]=s[5];
      s[5]=s[1];
      s[1]=b;
    }
  }

  out(s[0]);


  return 0;
}



Measured memory_bytes: 3196
#include <iostream> 
#include <string> 
#include <vector> 
#include <algorithm> 
#include <utility> 
#include <tuple> 
#include <cstdint> 
#include <cstdio> 
#include <map> 
#include <queue> 
#include <set> 
#include <stack> 
#include <deque> 
#include <unordered_map> 
#include <unordered_set> 
#include <bitset> 
#include <cctype> 
using namespace std;

int main() {
	int M;
	cin >> M;
	cout << 48 - M << endl;
}

Measured memory_bytes: 256
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main{
	public static void main (String[] args){
		Scanner sc = new Scanner (System.in);
		int N = sc.nextInt();
		int T = sc.nextInt();
		int[] c = new int [N];
		int[] t = new int [N];
		int p = 1001;
		for (int i = 0; i < N; i++) {
			c[i] = sc.nextInt();
			t[i] = sc.nextInt();
		}
		for (int i = 0; i < N; i++) {
			if ((t[i] <= T) && (c[i] < p)) {
				p = c[i];
			}
		}
		if (p == 1001) {
			System.out.println("TLE");
		} else {
			System.out.println(p);
		}
	}
}

Measured memory_bytes: 23124
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val xs = List.fill(sc.nextInt())(sc.nextInt())
  val (alices, bobs) = xs.sorted.reverse.zipWithIndex.partition { case (_, i) => i % 2 == 0 }
  println(alices.map(_._1).sum - bobs.map(_._1).sum)
}


Measured memory_bytes: 25416
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int main()
{
    string S;
    cin >> S;
    int N = S.size();
    for (int i = 0; i < N / 2; ++i)
    {
        if (S[i] != S[N - 1 - i])
        {
            cout << "No" << endl;
            return 0;
        }
    }

    int len = (N - 1) / 2;
    for (int i = 0; i < len / 2; ++i)
    {
        if (S[i] != S[len - 1 - i])
        {
            cout << "No" << endl;
            return 0;
        }
    }

    int pos = ((N + 3) / 2) - 1;
    int num = N - pos;
    string sub = S.substr(pos, num);
    for (int i = 0; i < sub.size() / 2; ++i)
    {
        if (sub[i] != sub[sub.size() - 1 - i])
        {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}


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

using namespace std;
typedef long long ll;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n; cin >> n;
  for(int i = 1; i <= 9; ++i) {
    if(n % i) continue;
    if(max(i, n / i) <= 9) {
      cout << "Yes\n";
      return 0;
    }
  }
  cout << "No\n";
  return 0;
}


Measured memory_bytes: 256
import bisect
l,i,x=[],0,0
while i<10**7:
    i+=x
    x+=1
    l.append(i)
n=int(input())
x=bisect.bisect_left(l,n)
y=l[x]-n
for i in range(1,x+1):
    if i!=y:print(i)

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define pb push_back
#define eb emplace_back
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define __builtin_popcount __builtin_popcountll

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
    os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
    os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const map<S, T> &t) {
    os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class S, class T> pair<S,T> operator+(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first+t.first, s.second+t.second);}
template<class S, class T> pair<S,T> operator-(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first-t.first, s.second-t.second);}

const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;

class BIT {
    int n;
    vector<int> vs;
public:
    BIT(int size) {
        n = size;
        vs = vector<int>(n);
    }
    //O(log n)
    void add(int k, int a) {
        for(int i = k; i < n; i |= i + 1) {
            vs[i] += a;
            if (vs[i] < 0) vs[i] += MOD;
            if (vs[i] >= MOD) vs[i] -= MOD;
        }
    }
    //[s,t)	O(log n)
    int sum(int s, int t) {
        if (n < t) t = n;
        if(s > 0) return sum(0, t) - sum(0, s);
        int res = 0;
        for(int i = t - 1; i >= 0; i = (i & (i + 1)) - 1) {
            res += vs[i];
            if (res < 0) res += MOD;
            if (res >= MOD) res -= MOD;
        }
        return res;
    }
};

int T, n, m;

int main(int argc, char *argv[]){
    ios::sync_with_stdio(false);
    while(cin >> n >> m){
        BIT bit(m + 1);
        bit.add(m, 1);
        REP(i, n) {
            int x;
            cin >> x;
            REP(j, m) {
                bit.add(j, bit.sum(j + 1, j + x + 1));
            }
        }
        cout << bit.sum(0, 1) << endl;
    }
    return 0;
}


Measured memory_bytes: 640
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair< int, int> P;
struct edge{ll to, cost; };

static const double EPS = 1e-8;
static const double PI = 3.141592653589;
static ll INF = 999999999999;
int mod = 1000000007;

#define REP(i,n)	for(int i=0;i<(int)n;++i)
#define ALL(c)		(c).begin(),(c).end()
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define MIN(a,b)    (a) < (b) ? (a):(b)
#define MAX(a,b)    (a) > (b) ? (a):(b)
#define debug(x) cerr << #x << " = " << x << endl;
int dx[] = {1,-1,0,0,1,-1,1,-1};
int dy[] = {0,0,1,-1,-1,1,1,-1};

using namespace std;







int main() {

    string s[3];
    cin >> s[0];
    cin >> s[1];
    cin >> s[2];
    int i[3] = {0};
    int flag = 0;
    int turn = 0;

    while(1){
        if(i[0] == s[0].length() + 1) {
            flag = 1;
            break;
        }
        if(i[1] == s[1].length()  + 1){
            flag = 2;
            break;
        }
        if(i[2] == s[2].length() + 1){
            flag = 3;
            break;
        }
        int next = s[turn][i[turn]] - 'a';
        i[turn]++;
        turn = next;



    }
    char ans[5] = "0ABC";

    cout << ans[flag] << endl;

    return 0;
}

Measured memory_bytes: 256
pub fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

pub fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

pub fn read_vec2<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

pub fn read_col<T: std::str::FromStr>(n: usize) -> Vec<T> {
    (0..n).map(|_| read()).collect()
}

fn main() {
    let n: usize = read();
    let mut ab: Vec<Vec<i64>> = read_vec2(n);
    ab.sort_by(|x, y| (y[0] + y[1]).partial_cmp(&(x[0] + x[1])).unwrap());
    let l = ab.len();
    let mut ans: i64 = 0;
    for i in 0..l / 2 {
        ans += ab[2 * i][0] - ab[2 * i + 1][1];
    }
    if l % 2 == 1 {
        ans += ab[l - 1][0];
    }
    println!("{}", ans);
}


Measured memory_bytes: 10492
#include <bits/stdc++.h>
#include <complex>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define loop(i, x, n) for (int i = (x); i < (n); i++)
#define all(v) (v).begin(), (v).end()
#define EQ(a, b) (abs((a) - (b)) < EPS)
#define int long long
#define INF 1e9
#define MOD 1e9 + 7
using namespace std;

template<typename T> void cmin(T &a, T b) { a = min(a, b); }
template<typename T> void cmax(T &a, T b) { a = max(a, b); }

using P = complex<double>;
const double PI = acos(-1);
const double EPS = 1e-9;
// P p(a,b)=a+bi -> 点p(a,b)
namespace std {
  bool operator<(const P &a, const P &b) { return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b); }
  bool operator==(const P &a, const P &b) { return a.real() == b.real() && a.imag() == b.imag(); }
} // namespace std

//内積
double dot(P a, P b) { return real(conj(a) * b); }
//外戚
double cross(P a, P b) { return imag(conj(a) * b); }
// 2直線の直交判定 : a⊥b <=> dot(a, b) = 0
int IsOrthogonal(P a1, P a2, P b1, P b2) { return EQ(dot(a1 - a2, b1 - b2), 0.0); }
// 2直線の平行判定 : a//b <=> cross(a, b) = 0
int IsParallel(P a1, P a2, P b1, P b2) { return EQ(cross(a1 - a2, b1 - b2), 0.0); }

signed main() {

  int q;
  cin >> q;
  while (q--) {
    int a, b, c, d, e, f, g, h;
    cin >> a >> b >> c >> d >> e >> f >> g >> h;
    P A(a, b), B(c, d), C(e, f), D(g, h);
    if (IsOrthogonal(A, B, C, D))
      cout << 1 << endl;
    else if (IsParallel(A, B, C, D))
      cout << 2 << endl;
    else
      cout << 0 << endl;
  }
  return 0;
}



Measured memory_bytes: 3112
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <functional>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> P;

int main() {
    int N, T, A;
    scanf("%d\n%d %d", &N, &T, &A);

    int H[N];

    for (int i = 0; i < N; i++) {
        scanf("%d", &H[i]);
    }

    int min_i = 0;
    double min_T = abs(A - (T - H[0] * 0.006));

    for (int i = 1; i < N; i++) {
        if (abs(A - (T - H[i] * 0.006)) < min_T) {
            min_T = abs(A - (T - H[i] * 0.006));
            min_i = i;
        }
    }
    printf("%d\n", min_i + 1);
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int p[100005];
int find(int x){
	if(x!=p[x])p[x]=find(p[x]);
	return p[x];
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		p[i]=i;
	}
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		u=find(u),v=find(v);
		if(u!=v){
			p[u]=v;
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(p[i]==i){
			cnt++;
		}
	}
	printf("%d\n",cnt-1);
	return 0;
}

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


int main(void){
  string S;
  cin >> S;
  if(S == "SUN") cout << "7" << endl;
  if(S == "MON") cout << "6" << endl;
  if(S == "TUE") cout << "5" << endl;
  if(S == "WED") cout << "4" << endl;
  if(S == "THU") cout << "3" << endl;
  if(S == "FRI") cout << "2" << endl;
  if(S == "SAT") cout << "1" << endl;
}

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


long long int gcd(long long int m, long long int n )
{
	
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
       
	while( m != n )
	{
		if ( m > n ) m = m - n;
		else         n = n - m;
	}
	return m;
}


long long int lcm( long long int m, long long int n )
{
	
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	return ((m / gcd(m, n)) * n); 
}

int main(){
  long long int n,m;
  long long int l,i;
  char a,b;
  string s,t;
  cin>>n>>m;
  cin>>s>>t;
  l=lcm(n,m);
  if(l==n*m && s[0]==t[0]){
    cout<<l<<endl;
    return 0;
  }
  if(s[0]!=t[0]){
    cout<<-1<<endl;
    return 0;
  }
  for(i=0;i<l;i++){
    if(i%(l/n)==0) a=(s[i/(l/n)]);
    if(i%(l/m)==0) b=(t[i/(l/m)]);
    if(i%(l/n)==0 && i%(l/m)==0){
      if(a!=b){
	cout<<-1<<endl;
	return 0;
      }
    }
  }
  cout<<l<<endl;
      
  return 0;
}


Measured memory_bytes: 512
n, max_w = map(int, input().split())

w = []
v = []
for i in range(n):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

f_inf = float('inf')
max_v = 100000

dp = [f_inf]*(max_v+2)
dp[0] = 0

for i in range(1, n+1):
    for j in range(max_v+1, -1, -1):
        if j >= v[i-1]:
            dp[j] = min(dp[j], dp[j-v[i-1]]+w[i-1])

ans = 0
for i in range(max_v+1):
    if dp[i] <= max_w:
        ans = max(ans, i)
print(ans)

Measured memory_bytes: 94412
h,w = map(int,input().split())
n = int(input())
A = list(map(int,input().split()))
C =[[0]*w for i in range(h)] 

color = 1
for i in range(h):
  for j in range(w):
    if A[color-1] == 0:
      color += 1
    C[i][j] = color
    A[color-1] -= 1
    
for i in range(h):
  if i%2 == 0:
    print(*C[i])
  else:
    print(*reversed(C[i]))

Measured memory_bytes: 3912
from collections import Counter
N,C=map(int,input().split())
D=[list(map(int,input().split())) for _ in range(C)]
Grid=[[] for _ in range(3)]
for i in range(N):
  c=list(map(int,input().split()))
  for j in range(N):
    Grid[(i+j)%3].append(c[j])

for i in range(3):
  Grid[i]=Counter(Grid[i])

ans=float("inf")
for i in range(1,C+1):  
  for j in range(1,C+1):
    for k in range(1,C+1):
      if i!=j and j!=k and k!=i:
        an=0
        for g1 in Grid[0]:
          an+=D[g1-1][i-1]*Grid[0][g1]
        for g2 in Grid[1]:
          an+=D[g2-1][j-1]*Grid[1][g2]
        for g3 in Grid[2]:
          an+=D[g3-1][k-1]*Grid[2][g3]
        ans=min(ans,an)
        
print(ans)

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

int main(int argc, char const *argv[])
{
    string today;
    cin >> today;

    string tomorrow;
    if (today == "Sunny")
    {
        tomorrow = "Cloudy";
    }
    else if (today == "Cloudy")
    {
        tomorrow = "Rainy";
    }
    else
    {
        tomorrow = "Sunny";
    }

    cout << tomorrow << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using Weight = int;
using Flow = int;
struct Edge {
    int src, dst;
    Weight weight;
    Flow cap;
    Edge() : src(0), dst(0), weight(0) {}
    Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) {}
};
using Edges = std::vector<Edge>;
using Graph = std::vector<Edges>;
using Array = std::vector<Weight>;
using Matrix = std::vector<Array>;

void add_edge(Graph &g, int a, int b, Weight w = 1) {
    g[a].emplace_back(a, b, w);
    g[b].emplace_back(b, a, w);
}
void add_arc(Graph &g, int a, int b, Weight w = 1) { g[a].emplace_back(a, b, w); }


std::vector<int> tsort(const Graph &g) {
    int n = g.size();
    enum { YET, VISITED, DONE };
    std::vector<int> res, flg(n, YET);
    static const std::function<bool(int)> dfs = [&](int v) {
        if(flg[v] == VISITED)
            return false;
        else if (flg[v] == YET) {
            flg[v] = VISITED;
            for (auto &e : g[v])
                if (!dfs(e.dst)) return false;
            flg[v] = DONE;
            res.push_back(v);
        }
        return true;
    };
    for (int i = 0; i < n; ++i)
        if (flg[i] == YET && !dfs(i)) return {};
    std::reverse(res.begin(), res.end());
    return res;
}

using namespace std;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n,m;
    cin >> n >> m;
    Graph g(n);
    for(int i = 0; i < m; i++){
        int s,t;
        cin >> s >> t;
        g[s].emplace_back(s,t,0);
    }
    vector<int> ord = tsort(g);
    for(int i = 0; i < n; ++i){
        cout << ord[i] << '\n';
    }
}

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

signed main(void)
{
	string s;
	char color;
	int cnt;
	cin >> s;
	color = s[0];
	cnt = 0;
	for (int i = 1; i < s.size(); i++)
	{
		if (s[i] != color)
		{
			cnt++;
			color = s[i];
		}
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 512
def S(i):
    ans = 0
    while i // 10 > 0:
        ans += i % 10
        i //= 10
    ans += i
    return ans

K = int(input())
Ans, count, N = [], 0, 1
while count < K:
    N2, Nd = N, 1
    while N2//10 > 0:
        Nd += 1
        N2 //= 10
    minX, X = N/S(N), N
    for i in range(Nd+2):
        x = (N//10**(i+1) + 1) * 10**(i+1) -1
        if minX > x/S(x):
            minX, X = x/S(x), x
    Ans.append((minX, X))
    count += 1
    N = X+1

for i in range(K):
    print(Ans[i][1])

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
int a[100010];
void sieve()
{
    int i,j;
    for(i=0;i<100010;i++) a[i]=1;
    a[0]=a[1]=0;
    for(i=2;i*i<=100010;i++)
    {
        if(a[i]==1)
        {
            for(j=2;i*j<=100010;j++)
            {
                a[i*j]=0;
            }
        }
    }
}
int main()
{


    int x;
    cin>>x;
    sieve();
    if(a[x]==1) cout<<x<<endl;
    else{
        while(a[x]==0)
        {
            x++;
        }
        cout<<x<<endl;
    }
    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;

array<int,10000> A;
array<int, 100> b;

int main(){ _;
  int n,m;cin>>n>>m;
  REP(i,n*m)
    cin>>A[i];
  REP(i,m)
    cin>>b[i];
  REP(i,n){
    int sum=0;
    REP(j,m)
      sum+=A[i*m+j]*b[j];
    cout<<sum<<endl;
  }
}

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

void trace(int A[], int N) {
    for (int i = 0; i < N-1; i++) {
        cout << A[i] << ' ';
    }
    cout << A[N-1] << endl;
}

void insertionSort(int A[], int N) {
    int i, j, temp;

    for (i = 1; i < N; i++) {
        temp = A[i];
        j = i-1;

        while (j >= 0 && A[j] > temp) {
            A[j+1] = A[j];
            j--;
        }
        A[j+1] = temp;
        trace(A, N);
    }
}

int main(int argc, char const *argv[]) {
    int N;
    cin >> N;
    int A[N];

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

    trace(A, N);
    insertionSort(A, N);

    return 0;
}



Measured memory_bytes: 3072
#include <stdio.h>
int main(void){
  char a[11],b[11],c[11];
  scanf("%s%s%s",a,b,c);
  printf("%c%c%c\n",(char)((int)a[0]-32),(char)((int)b[0]-32),(char)((int)c[0]-32));
  return 0;
}

Measured memory_bytes: 128
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC120
{
    class A
    {
        static void Main(string[] args)
        {
            int[] lHW = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int[] hW = Console.ReadLine().Split().Select(int.Parse).ToArray();
            Console.WriteLine((lHW[0] - hW[0]) * (lHW[1] - hW[1]));
        }
    }
}


Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second

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

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const double EPS = 1e-8;

template<typename T> T chmax(T& a, const T& b){return a = (a > b ? a : b);}
template<typename T> T chmin(T& a, const T& b){return a = (a < b ? a : b);}

int main(){
    ll x;
    cin >> x;
    map<ll, ll> mp;
    rep(i, 1000) mp[(ll)i*i*i*i*i] = i;
    rep(i, 1000) mp[(ll)i*i*i*i*i*-1] = -i;
    rep(a, 1000) {
        ll a5 = (ll)a*a*a*a*a;
        ll tmp = a5-x;
        if(mp.count(tmp) == 0) continue;
        ll b = mp[tmp];
        cout << a << " " << b << '\n';
        return 0;
    }    
    return 0;
}

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

typedef vector<int> vi;
typedef pair<int, int> pi;

const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;

#define pb push_back
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REP2(i, b, e) for (int i = (b); i <= (int)(e); i++)
#define DEBUG(x) cout << #x << ": " << (x) << endl
#define DEBUGA(a) cout << #a << ": "; for (const auto& v: (a)) cout << v << endl

signed main() {
    int N, M;
    cin >> N >> M;

    vi A(N);
    priority_queue<int> Q;
    REP(i, N) {
        cin >> A[i];
        Q.push(A[i]);
    }
    REP(i, M) {
        int a = Q.top(); Q.pop();
        Q.push(a / 2);
    }
    ll sum = 0;
    while (!Q.empty()) {
        sum += Q.top(); Q.pop();
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 1276
#include<bits/stdc++.h>
clock_t t=clock();
namespace my_std{
	using namespace std;
	#define pii pair<int,int>
	#define fir first
	#define sec second
	#define MP make_pair
	#define rep(i,x,y) for (int i=(x);i<=(y);i++)
	#define drep(i,x,y) for (int i=(x);i>=(y);i--)
	#define go(x) for (int i=head[x];i;i=edge[i].nxt)
	#define templ template<typename T>
	#define sz 6300
	typedef long long ll;
	typedef double db;
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}
	templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
	templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}
	templ inline void read(T& t)
	{
		t=0;char f=0,ch=getchar();double d=0.1;
		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
		while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
		if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
		t=(f?-t:t);
	}
	template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}
	char __sr[1<<21],__z[20];int __C=-1,__zz=0;
	inline void Ot(){fwrite(__sr,1,__C+1,stdout),__C=-1;}
	inline void print(register int x)
	{
		if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;
		while(__z[++__zz]=x%10+48,x/=10);
		while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';
	}
	void file()
	{
		#ifdef NTFOrz
		freopen("a.in","r",stdin);
		#endif
	}
	inline void chktime()
	{
		#ifdef NTFOrz
		cout<<(clock()-t)/1000.0<<'\n';
		#endif
	}
	#ifdef mod
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}
	ll inv(ll x){return ksm(x,mod-2);}
	#else
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;}
	#endif
//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;

int n;
char a[sz];
int p1[sz],p2[sz],c1,c2;

string s[sz],dp[sz];
int link[sz],to[sz];

int book[sz],T;

int main()
{
	file();
	read(n);n*=2;
	cin>>(a+1);
	rep(i,1,n) if (a[i]=='a') p1[++c1]=i; else p2[++c2]=i;
	rep(i,1,n>>1) link[min(p1[i],p2[i])]=max(p1[i],p2[i]);
	rep(i,1,n) if (link[i])
	{
		if (a[i]=='a') { s[i]="ab",to[i]=link[i]; continue; }
		++T;book[i]=book[link[i]]=T;int R=link[i];
		rep(j,i,R) if (link[j]) book[j]=book[R=link[j]]=T;
		rep(j,i,R) if (book[j]==T) s[i]+=a[j];
		to[i]=R;
	}
	drep(i,n,1)
	{
		dp[i]=dp[i+1];
		if (link[i]) chkmax(dp[i],s[i]+dp[to[i]+1]);
	}
	cout<<dp[1];
	return 0;
}

Measured memory_bytes: 16384
#include<bits/stdc++.h>
#define endl '\n'
#define fastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//#define int long long int
using namespace std;
int gcd(int a, int b){
    if(b == 0) return a;
    return gcd(b,a % b);
}
int combination(int n, int k){
    int spaceOptimize[k+1];
    memset(spaceOptimize, 0, sizeof(spaceOptimize));
    spaceOptimize[0] = 1;
    for(int i=1;i<=n; i++){
        for(int j= min(i,k);j>0;j--){
            spaceOptimize[j] = spaceOptimize[j] + spaceOptimize[j-1];
        }
    }
    return spaceOptimize[k];
}
int count_permutation(int arr[], int n){
    int a[n];
    for(int i=0;i<n;i++){
        a[i] = i+1;
    }
    int count = 0;
    do {
        count++;
        if (std::equal(a, a + n, arr)){
            return count;
        }
    } while (next_permutation(a, a + n));
    return 0;
}
signed main(){
#ifndef ONLINE_JUDGE
    //freopen("input.txt","r", stdin);
#endif
    fastIO

    int n;
    cin >> n;
    int arr1[n],arr2[n];
    for(int i=0;i<n;i++) cin >> arr1[i];
    for(int i=0;i<n;i++) cin >> arr2[i];
    cout << abs(count_permutation(arr1,n) - count_permutation(arr2,n)) << endl;


    return 0;
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main{
	public static void main(String[] ards){
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int i=1;
		do{
			int x=i;
			if(x%3==0){
				System.out.print(" "+i);	
			}
			while(true){
			if(x%10==3){
				if(i%3!=0){
				System.out.print(" "+i);
				}	
				break;
			}
			x/=10;
			if(x!=0)continue;
			else break;
		}

		}while(++i<=n);

		System.out.println();

	}
}

Measured memory_bytes: 28828
N,M=map(int,input().split())
a=[list(map(int,input().split()))for i in range(N)]
money=0
a.sort()
flag=False
s=0
for i in range(N):
    if flag:
        break
    s+=a[i][1]
    count=a[i][1]
    if s>M:
        count-=s-M
        flag=True
    money+=count*a[i][0]
print(money)

Measured memory_bytes: 27880
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
bool query(Int n)
{
    char ch;
    cout << "? " << n << endl;
    cin >> ch;
    return ch == 'Y';
}
Int solve(function<bool(Int)> query)
{
    Int ng = 999999999, ok = 9999999999, mid;
    while (abs(ng - ok) > 1) {
        mid = (ng + ok) / 2;
        (query(mid * 10) ? ok : ng) = mid;
    }
    if (ok != 1000000000) {
        Int val = 1;
        for (int i = 0; i < 10; i++) {
            if (!query(val)) {
                return stoll(to_string(ok).substr(0, i));
            }
            val *= 10;
        }
    } else {
        Int val = 9;
        for (int i = 0; i < 10; i++) {
            if (query(val)) {
                return stoll(to_string(ok).substr(0, i+1));
            }
            val = val * 10 + 9;
        }
        return 1;
    }
    return -1;
}
int main()
{
    Int val = solve(query);
    cout << "! " << val << endl;
    return 0;
}


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

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << setprecision(20);
  int n, d;
  cin >> n >> d;
  int range = 2 * d + 1;
  cout << (n + range - 1)/range << endl;
  return 0;
}


Measured memory_bytes: 256
#include <vector>
#include <iostream>
#include <unordered_map>
#include <map>
#include <iomanip>
#include <functional>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <string>
#include <sstream>
#include <queue>
using namespace std;

#define x first
#define y second
#define ll long long
#define ld long double
#define pii pair<int,int>
#define wh(x) (x).begin(),(x).end()
#define ri(x) int x;cin>>x;
#define rii(x,y) int x,y;cin>>x>>y;
#define rl(x) ll x;cin>>x;
#define rv(v) for(auto&_cinv:v) cin>>_cinv;
#define wv(v) for(auto&_coutv:v) cout << _coutv << ' '; cout << endl;
#define ev(v) for(auto&_cerrv:v) cerr << _cerrv << ' '; cerr << endl;
#define MOD 1000000007

namespace std { 
template<typename T,typename U>struct hash<pair<T,U>>{hash<T>t;hash<U>u;size_t operator()(const pair<T,U>&p)const{return t(p.x)^(u(p.y)<<7);}};
}
template<typename T,typename F>T bsh(T l,T h,const F&f){T r=-1,m;while(l<=h){m=(l+h)/2;if(f(m)){l=m+1;r=m;}else{h=m-1;}}return r;}
template<typename T,typename F>T bsl(T l,T h,const F&f){T r=-1,m;while(l<=h){m=(l+h)/2;if(f(m)){h=m-1;r=m;}else{l=m+1;}}return r;}
template<typename T> T gcd(T a,T b) { if (a<b) swap(a,b); return b?gcd(b,a%b):a; }

int main(int,char**) {
    ios_base::sync_with_stdio(false);

    int H,W; cin >> H >> W;
    vector<string> S(H); rv(S);
    int c=0;
    int y=0;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < y; j++) {
            if (S[i][j] == '#') {
                cout << "Impossible" << endl;
                return 0;
            }
        }
        if (S[i][y] != '#') {
                cout << "Impossible" << endl;
                return 0;
            }

        for (; y < W && S[i][y] == '#'; y++);
        --y;

        for (int j = y+1; j < W; j++) {
            if (S[i][j] == '#') {
                cout << "Impossible" << endl;
                return 0;
            }
        }
    }

    
            if (S[H-1][W-1] != '#') {
                cout << "Impossible" << endl;
                return 0;
            } else {
                cout << "Possible" << endl;
            }
}


Measured memory_bytes: 256
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
#include <stack>
using namespace std;
#define ll int64_t
const long mod = 1e9 + 7;


const long LINF = 1e13;
const long LLINF = 1e18;
const long ALPHABET = 26;

template <class T>
void Swap(T& r, T& l) {
  T tmp = r;
  r = l;
  l = tmp;
}

template<typename T>
istream& operator >> (istream& is, vector<T>& vec) {
  for (T& x : vec) is >> x; //for(int i=0; i<vec.size(); i++) is >> x[i]; とかでもいい
  return is;
}


int main() {
  ll x, y, z, k;


  cin >> x >> y >> z >> k;
  vector<ll> a(x, 0);
  vector<ll> b(y, 0);
  vector<ll> c(z, 0);


  cin >> a;
  cin >> b;
  cin >> c;

  vector<pair<ll, ll>> s(x + y + z);
  for (int i = 0; i < x; ++i) {
    s.push_back(make_pair(a[i], 0));
  }
  for (int i = 0; i < y; ++i) {
    s.push_back(make_pair(b[i], 1));
  }
  for (int i = 0; i < z; ++i) {
    s.push_back(make_pair(c[i], 2));
  }
  //x * y * z 通り
  //x,y,zの各パラメータがabc

  sort(a.begin(), a.end(), greater<ll>());
  sort(b.begin(), b.end(), greater<ll>());
  sort(c.begin(), c.end(), greater<ll>());


  vector<ll> v1;
  for (auto a1 : a) {
    for (auto b1 : b) {
      v1.push_back(a1 + b1);
    }
  }

  sort(v1.begin(), v1.end(), greater<ll>());
  vector<ll> an;
  for (int v = 0; v < min((int)k,(int)v1.size()); v++) { //10^6
    for (auto c1 : c) {// 10^3
      an.push_back(v1[v] + c1);
    }
  }

  sort(an.begin(), an.end(), greater<ll>());

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





}




















Measured memory_bytes: 43524