akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define Lens 1000100
#define Nil -1

using namespace std;

struct point
{
	int x;
	int y;
	int add;
};

struct node
{
	int lc;
	int rc;
	int key;
};

int N, q, h;
point p[Lens];
node T[Lens];
vector<int> ans;
bool lessx(point a, point b) { return a.x < b.x; }
bool lessy(point a, point b) { return a.y < b.y; }

int maketree(int l, int r, int depth)
{
	if (l >= r)
		return Nil;
	int mid = (l + r) / 2;
	if (depth % 2 == 0)
		sort(p + l, p + r, lessx);
	else
		sort(p + l, p + r, lessy);
	int t = h++;
	T[t].key = mid;
	T[t].lc = maketree(l, mid, depth + 1);
	T[t].rc = maketree(mid + 1, r, depth + 1);
	return t;

}

void findtree(int root, int lx, int hx, int ly, int ry, int depth)
{
	int tr = root;
	int tx = p[T[tr].key].x;
	int ty = p[T[tr].key].y;
	if (lx <= tx&&tx <= hx&&ly <= ty&&ty <= ry)
		ans.push_back(p[T[tr].key].add);
	if (depth % 2 == 0)
	{
		if (T[tr].lc != Nil&&lx <= tx)
			findtree(T[tr].lc, lx, hx, ly, ry, depth + 1);
		if (T[tr].rc != Nil&&tx <= hx)
			findtree(T[tr].rc, lx, hx, ly, ry, depth + 1);
	}
	else
	{
		if (T[tr].lc != Nil&&ly <= ty)
			findtree(T[tr].lc, lx, hx, ly, ry, depth + 1);
		if (T[tr].rc != Nil&&ty <= ry)
			findtree(T[tr].rc, lx, hx, ly, ry, depth + 1);
	}

}

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		scanf("%d %d", &p[i].x ,&p[i].y);
		p[i].add = i;
		T[i].lc = T[i].rc = T[i].key = Nil;

	}
	int root = maketree(0, N, 0);
	scanf("%d", &q);
	for (int i = 0; i < q; i++)
	{
		ans.clear();
		int lx, hx, ly, ry;
		scanf("%d %d %d %d", &lx, &hx,&ly,&ry);

		findtree(root, lx, hx, ly, ry, 0);
		sort(ans.begin(), ans.end());
		for (int i = 0; i < ans.size(); i++)
			printf("%d\n", ans[i]); 
		printf("\n");
	}
	return 0;
}


Measured memory_bytes: 14500
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    ll N;
    cin >> N;
    map<ll, ll> mp;
    ll sum = 0;
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        sum += a;
        mp[a]++;
    }
    ll Q;
    cin >> Q;
    for (int i = 0; i < Q; i++) {
        ll b, c;
        cin >> b >> c;
        ll cnt = mp[b];
        mp[b] = 0;
        sum -= cnt * b;
        sum += cnt * c;
        mp[c] += cnt;
        cout << sum << '\n';
    }

}


Measured memory_bytes: 9568
p = 10**9+7
N = int(input())
A = list(input().split())
B = [0 for _ in range(N)]
for i in range(N):
    a = A[i]
    b = bin(int(a))[2:]
    b = "0"*(60-len(b))+b
    B[i] = b
C = {i:0 for i in range(60)}
for j in range(60):
    cnt = 0
    for i in range(N):
        if B[i][j]=="1":
            cnt += 1
    C[j] = cnt
tot = 0
for j in range(60):
    n = C[j]
    k = (N*(N-1))//2-(n*(n-1))//2-((N-n)*(N-n-1))//2
    tot = (tot+k*(2**(60-1-j)))%p
print(tot)

Measured memory_bytes: 151784
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <map>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
typedef long long ll;
typedef long double ld;
int main(){
    ll INF=pow(10, 18);
    int h,w;cin>>h>>w;
    vector<vector<ll>> c(10,vector<ll> (10));
    REP(i,10)REP(j,10)cin>>c[i][j];
    REP(k,10)REP(i,10)REP(j,10)
        if(c[i][j]>c[i][k]+c[k][j])c[i][j]=c[i][k]+c[k][j];
    ll sum=0;
    REP(i,h)REP(j,w){
        ll a;cin>>a;
        if(a>=0){
            sum+=c[a][1];
        }
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 3628
// Best practice

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <functional> // for less 

#define int         long long
#define pb          emplace_back
#define pf          emplace_front
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),(a).rend()
#define x           first
#define y           second
#define endl        '\n'
#define tezz        ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
using namespace __gnu_pbds; 
 
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> pbds; 

#define fbo find_by_order
#define ook order_of_key

signed main() {
   tezz
   
   int n,k;
   cin >> n >> k;
   vector<int> a(n);
   for(int i=0; i<n; i++){
       cin >> a[i];
   }
   sort(all(a));
   int x = n-k;
   int c=0;
   for(int i=0; i<x; i++){
       c+=a[i];
   }
   cout << c << endl;
  
   return 0;
}




Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define int long long
#define MAX 100001
#define MOD 1000000007
using namespace std;

 
int32_t main()
{
    int h,w;
    cin>>h>>w;
    char a[h][w];
    for(int i= 0;i<h;++i)
    {
        for(int j=0;j<w;++j)
        {
            cin>>a[i][j];
        }
    }

    int dp[h+1][w+1];
    memset(dp,0,sizeof(dp));

    for(int i=1;i<=h;++i)
    {
        for(int j=1;j<=w;++j)
        {
            if(i==1 and j==1)
                dp[i][j] = 1;
            else if(a[i-1][j-1] == '.')
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;
            else
                dp[i][j] = 0;
        }
    }

    cout<< dp[h][w] <<endl;

    return 0;
}

Measured memory_bytes: 9088
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<set>
#include<algorithm>
#include<cmath>
#include<math.h>
#include<queue>
#define mem(x) memset(x,0,sizeof(x)) 
#define sca(x) scanf("%d",&x)
#define scaa(x,y) scanf("%d%d",&x,&y)
#define inf 0x7f7f7f7f
#define io ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#pragma GCC optimize(2)
using namespace std;
const double pi=acos(-1); 
const double eps=1e-6;
typedef pair<long,long> pll;
typedef pair<int,int> pii;
typedef long long ll;
typedef pair<string,string> pcc;
int main()
{
	int l,r,d;
	cin>>l>>r>>d;
	cout<<r/d-(l-1)/d<<endl;
}

Measured memory_bytes: 3592
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
typedef long long ll;
int n,a[N];
ll sum[N],b[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+a[i],b[i]=b[i-1]^a[i];
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        int l=1,r=i,s;
        while(l<=r)
        {
            int m=l+r>>1;
            ll sm=sum[i]-sum[m-1],xm=b[i]^b[m-1];
            if(sm==xm) s=m,r=m-1;
            else l=m+1;
        }
        ans+=(i-s+1);
    }
    printf("%lld\n",ans);
}


Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
typedef pair<int,int> P;
struct edge{int to, id;};
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1000000000000
 
ll solve(ll n){
    if(n == 1) return 1;
    else if(n > 1){
        //return 1+solve(n/2) * 2;
      if(n % 2 ==0) return 1+solve(n/2) * 2;
      else return 1+solve((n-1)/2) * 2;
    }
}
 
 int main(){
     ll n;
     cin >> n;
     ll ans = solve(n);
     cout << ans << endl;
 
 }

Measured memory_bytes: 3484
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> // Common file  
#include <ext/pb_ds/tree_policy.hpp>  
#include <functional> // for less
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    std::cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#define rep(i,a,n)    for(int i=a; i<=n; ++i)
#define rep1(i,a,n)   for(int i=a; i>=n; --i)
#define pb            push_back
#define mp            make_pair
#define int           long long
#define fr            first
#define sc            second
#define vc            vector
#define sz(v)         (int)v.size()
#define all(x)        (x).begin(),(x).end()
#define rall(x)       (x).rbegin(),(x).rend()
#define N             (int)(1e6+5)
#define M             1000000007
#define MM            998244353
#define PI            3.14159265358979
#define INF           1000000000000000

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mii;

int n,m,ans; string str;

int solve(){
    cin>>str;
    deque<char> v1,v2;
    int q; cin>>q;
    int f1=0;
    while(q--){
        int t; cin>>t;
        if(t==1){
            f1^=1;
        }
        else{
            int f; char s; cin>>f>>s;
            if(f==1){
                if(f1==0)
                    v1.push_front(s);
                else
                    v2.pb(s);
            }
            else{
                if(f1==0)
                    v2.pb(s);
                else
                    v1.push_front(s);
            }
        }
    }
    if(f1==0){
        rep(i,0,sz(v2)-1){
            str+=v2[i];
        }
        reverse(all(str));
        reverse(all(v1));
        rep(i,0,sz(v1)-1){
            str+=v1[i];
        }
        reverse(all(str));
    }
    else{
        reverse(all(str));
        swap(v1,v2);        
        // reverse(all(v1));
        reverse(all(v2));
        rep(i,0,sz(v2)-1){
            str+=v2[i];
        }
        reverse(all(str));
        rep(i,0,sz(v1)-1){
            str+=v1[i];
        }
        reverse(all(str));
    }
    cout<<str;
    return 0;
}

signed main() {
    ios::sync_with_stdio(0);
    //std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int t=1;
    // cin>>t;
    while(t--) solve();
    return 0;
}

Measured memory_bytes: 1040
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <algorithm>
#define pb push_back
#define ll typedef long long
#define fr(i,n) for(int i=0;i<n;i++)
using namespace std;

int main(){
    int n,k,j=0,a;
    string s = "";
    cin >> n >> k;
    if(1 <= k && k <= 10){
        while(1){
            if(n == pow(k,j)){
                a = abs(pow(k,j)-n);
                break;
            }
            if(n <= pow(k,j)){
                a = abs(pow(k,j)-n);
                j--;
                break;
            }else{
                j++;
            }
        }
        s += "1";
        fr(i,j){
            s += "0";
        }
    }
    cout << s.size() << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>

using namespace std;
#define int long  long int
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

signed main()
{
	int A, B;
	cin >> A >> B;
	if(B==1)
	{
		cout << 0;
		return 0;
	}
	int num = A;
	int cnt = 1;
	while (1)
	{
		if (num >= B)break;
		num += -1 + A;
		cnt++;
	}
	cout << cnt;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <iostream>
#include <string>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repR(i,n) for(ll i=n;i>=0;i--)
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define F first
#define S second
#define pb push_back
#define pu push
#define COUT(x) cout<<(x)<<endl
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,vector<ll>,greater<ll>>
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define mp make_pair
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define sz(x) (int)(x).size()
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MOD = 1000000007LL;
const ll INF = 1LL << 60;
using vll = vector<ll>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pll = pair<ll, ll>;
int main(){
  ll n;
  cin>>n;
  ll cu=0;
  vll a(n);
  ll f=MOD;
  rep(i,n) {
    cin>>a[i];
    if(a[i]%10!=0){
      f=min(a[i],f);
    }
    cu+=a[i];
  }
  if(cu%10!=0){
    COUT(cu);
  }
  else{
    if(f==MOD){
      COUT(0);
    }
    else{
      COUT(cu-f);
    }
  }
}
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int ll
using pii = pair<int, int>;
vector <pii> ctr, ctc;
vector <pii> mr, mc;
int h, w, m;
int hc[303030], wc[303030];
set <int> findW[303030];
int32_t main()
{
    usecppio
    cin >> h >> w >> m;
    for (int i = 0; i < m; i++)
    {
        int hi, wi;
        cin >> hi >> wi;
        hc[hi]++;
        wc[wi]++;
        findW[hi].insert(wi);
    }
    for (int i = 1; i<=h; i++)
        ctr.push_back({hc[i],i});
    for (int i = 1; i<=w; i++)
        ctc.push_back({wc[i],i});
    sort(all(ctr), greater<pii>());
    sort(all(ctc), greater<pii>());
    for (int i = 0; i<ctr.size(); i++)
    {
        if (ctr[i].first == ctr[0].first)
            mr.push_back(ctr[i]);
    }
    for (int i = 0; i<ctc.size(); i++)
    {
        if (ctc[i].first == ctc[0].first)
            mc.push_back(ctc[i]);
    }

    /*for (int i = 0; i<mr.size(); i++)
        printf("MR %lld : %lld\n",mr[i].second, mr[i].first);
    for (int i = 0; i<mc.size(); i++)
        printf("MC %lld : %lld\n",mc[i].second, mc[i].first);
*/
    if (mr.size() > mc[0].first)
    {
        //printf("MR DEAD\n");
        cout << mr[0].first + mc[0].first << '\n';
        return 0;
    }
    if (mc.size() > mr[0].first)
    {
        //printf("MC DEAD\n");
        cout << mr[0].first + mc[0].first << '\n';
        return 0;
    }
    for (int i = 0; i<mr.size(); i++)
    {
        for (int j = 0; j<mc.size(); j++)
        {
            int mrpos = mr[i].second;
            int mcpos = mc[j].second;
            if (findW[mrpos].find(mcpos) == findW[mrpos].end())
            {
                cout << mr[0].first + mc[0].first << '\n';
                return 0;
            }
        }
    }
    cout << mr[0].first + mc[0].first - 1 << '\n';
}

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


def solve(N: int, h: "List[int]"):
    cost = 0
    CUR = [0 for i in range(len(h))]
    for i in range(len(CUR)):
        while CUR[i] != h[i]:  # 花が成長しきっていないなら以下の処理を繰り返す
            l = i
            r = i
            for j in range(i, len(CUR)):
                if CUR[i] >= h[j]:
                    break
                r += 1
            grow = 10 ** 16
            for j in range(l, r):
                grow = min(grow, h[j] - CUR[j])
            #cost += 1
            for j in range(l, r):
                CUR[j] += grow
            cost += grow
    print(cost)
    return


# Generated by 1.1.3 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()
    N = int(next(tokens))  # type: int
    h = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, h)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int sq(int n)
{
    int t=sqrt(n);
    if(t*t==n)
    {
        return 1;
    }
    else
    {
        return 0;

    }
}
int main()
{
    int i,j,k=0;
    char a[10],b[5];
    cin>>a>>b;
    strcat(a,b);//cout<<a<<endl;

    int ara[strlen(a)];
    for(i=0;i<strlen(a);i++)
    {
        ara[i]=a[i]-'0';
    }

    for(i=strlen(a)-1,j=1;i>=0;i--)
    {
       k=k+ara[i]*j;
       j*=10;
    }
    //cout<<k;
    if(sq(k)==1)
    {
        cout<<"Yes";
    }
    else
    {
        cout<<"No";
    }

}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <cassert>
#include <memory>
#include <stack>
#include <set>
#include <map>
#include <cctype>

#define MAX_SIZE 100000000
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

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

  int W,H,N; cin>>W>>H>>N;
  int left_x = 0, right_x = W, top_y = H, bottom_y = 0;
  for(int i = 0; i < N; i++) {
    int x,y,a; cin>>x>>y>>a;
    switch(a) {
    case 1:
      left_x = max(left_x, x);
      break;
    case 2:
      right_x = min(right_x, x);
      break;
    case 3:
      bottom_y = max(bottom_y, y);
      break;
    case 4:
      top_y = min(top_y, y);
      break;
    default:
      exit(1);
    }
  }

  int diff_x = right_x - left_x;
  int diff_y = top_y - bottom_y;
  if(diff_x < 0 || diff_y < 0) {
    cout << 0 << endl;
  } else {
    cout << diff_x * diff_y << endl;
  }
}


Measured memory_bytes: 892
#include<cstdio>
#include <iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<complex>
#include <cstring>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<numeric>
#include<limits>
#include<climits>
#include<cfloat>
#include<functional>
#include<iterator>
#include <random>
#define inf  1000000000
#define mod  1073741824
#pragma GCC optimization ("O3")
using namespace std;
const long long int N = 6999999;
#define all(x) begin(x),end(x)
int main()
{
   
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  	long long int n,m = inf;
  	cin >> n;
  	vector <long long int> v(n);
  	for (int i = 0; i < n; ++i)
  	{
  		cin >> v[i];
  	}
  	for (int i = -100; i < 101; ++i)
  	{
  		long long int a = 0;
  		for (int j = 0; j < n; ++j)
  		{
  			a+= (v[j]-i)*(v[j]-i);
  		}
  		 m = min(m,a);
  	}
  	cout << m;
   	return 0;
}	

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

typedef long long ll;
typedef pair<int, int> pii;
 
#define fst first
#define snd second
#define pb(a) push_back(a)
#define mp(a, b) std::make_pair(a, b)
#define debug(...) fprintf(stderr, __VA_ARGS__)
 
template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
 
const int oo = 0x3f3f3f3f;
 
template<typename T> T read(T& x) {
    int f = 1; x = 0;
    char ch = getchar();
    for(;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48; 
    return x *= f;
}

const int N = 200;
const int mo = 1e9 + 7;

int n, k, ans;
char st[N + 5];
bool mark[N + 5];
int x[N + 5], y[N + 5], r[N + 5];

int binom[N + 5][N + 5];

void init() {
    for(int i = 0; i <= N; ++i) {
        binom[i][0] = binom[i][i] = 1;
        for(int j = 1; j < i; ++j) {
            binom[i][j] = (binom[i-1][j] + binom[i-1][j-1]) % mo;
        }
    }
}

int dp[N + 5][N + 5][N + 5];

int calc(int p, int q) {
    for(int i = 0; i <= 90; ++i) 
    for(int j = 0; j <= 90; ++j) 
    for(int t = 0; t <= 90; ++t) dp[i][j][t] = 0;

    int m = n - (p+q-1) - q;

    dp[0][0][0] = 1;
    for(int i = 0; i < m; ++i) {
        for(int j = 0; j <= p; ++j) {
            for(int l = 0; l <= m; ++l) if(dp[i][j][l]) {
                for(int t = 0; j + t <= p && l + (2*i+1) * t <= m; ++t) {
                    if(t && y[p-j-t+1] < (l-j)/2 + t*i) {
                        break;
                    }

                    (dp[i+1][j + t][l + (2*i+1) * t] += 1ll * binom[j + q + t][t] * dp[i][j][l] % mo) %= mo;
                }
            }
        }
    }

    int res = 0;
    for(int i = 0; i <= m; ++i) {
        res = (res + 1ll * binom[n + 2*p + 1][i + 3*p + 2*q] * dp[m][p][i]) % mo;
    }
    return res;
}

int main() {
#ifdef Wearry
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif

    init();
    read(n), read(k);
    scanf("%s", st + 1);

    for(int i = 1; i <= k; ++i) 
        if(st[i] == 'r') r[++ r[0]] = i;

    for(int i = 0; i <= r[0]; ++i) {
        for(int j = 0; i+j <= r[0]; ++j) {

            memset(mark, 0, sizeof mark);
            for(int t = 1; t <= i+j; ++ t) mark[r[t]] = true;

            int cur = 0, flag = 0;
            for(int t = 1; t <= i; ++ t) {
                chkmax(cur, r[t]);
                while(cur <= k && (st[cur] == 'r' || mark[cur])) ++ cur;
                if(cur > k) { flag = 1; break; }

                mark[x[t] = cur] = true;
            }
            if(flag) continue;

            for(int t = 1; t <= i; ++ t) {
                y[t] = 0;
                for(int l = x[t]; l <= k; ++ l) {
                    y[t] += !mark[l];
                }
            }
            ans = (ans + calc(i, j)) % mo;
        }
    }
    printf("%d\n", ans);

    return 0;
}


Measured memory_bytes: 15872
#include<iostream>
#include<algorithm>
#include<cassert>
#include<vector>
#include<fstream>
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<queue>
#include<map>

using namespace std;
#define REP(i,m,n) for(long long i=m;i<n;++i)
#define INF 10000000000000000
#define MOD 1000000007
#define ll long long
#define mp make_pair
#define all(v) v.begin(),v.end()

vector<pair<int, int>>edge[10];
vector<int>dist(10);
vector<int>dijkstra(10, 1000000000);

int main() {
	int h, w;
	cin >> h >> w;
	REP(i, 0, 10) {
		REP(j, 0, 10) {
			int tmp;
			cin >> tmp;
			edge[i].push_back(mp(j, tmp));
		}
	}
	REP(i, 0, 10) {
		REP(j, 0, 10) {
			dijkstra[j] = 1000000000;
		}
		if (i == 1) {
			dist[1] = 0;
		}
		else {
			queue<int>q;
			q.push(i);
			dijkstra[i] = 0;
			while (!q.empty()) {
				int tmp = q.front(); q.pop();
				REP(j, 0, edge[tmp].size()) {
					if (dijkstra[edge[tmp][j].first] > dijkstra[tmp] + edge[tmp][j].second) {
						dijkstra[edge[tmp][j].first] = dijkstra[tmp] + edge[tmp][j].second;
						q.push(edge[tmp][j].first);
					}
				}
			}
			dist[i] = dijkstra[1];
		}	
	}
	int ans = 0;
	REP(i, 0, h) {
		REP(j, 0, w) {
			int tmp;
			cin >> tmp;
			if (tmp != -1) {
				ans += dist[tmp];
			}
		}
	}
	cout << ans << endl;
	return 0;
}

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

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

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

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

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

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

ll cmb(ll x, ll y){
    if(y>x||y<0) return 0LL;
    ll c = 1;
    for(ll i = 0LL; i < y; i++) {
        c *= (x-i);
        c /= i+1;
    }
    return c;
}

int main() {
    ll N,P;
    cin>>N>>P;
    vector<ll> v(N);
    rep(i,N) {
        cin>>v[i];
        v[i] %= 2LL;
    }
    ll a=0,b=0;
    rep(i,N){
        if(v[i] == 0) a++;
        else b++;
    }
    ll cnt = 0;
    for(ll i = 0; i <= b;i += 2){
        cnt += cmb(b,i)*(1LL<<a);
    }
    if(P==1) cout<<(1LL<<N)-cnt<<endl;
    else cout<<cnt<<endl;
}


Measured memory_bytes: 3616
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;

long long n, t[1000], a[1000], ta = 0, mu = 0, rin = 0;
signed main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> t[i] >> a[i];
	}
	ta = t[0];
	mu = a[0];
	for (int i = 1; i < n; i++) {
		rin = max(ta / t[i], mu / a[i]);
		if (t[i] * rin >= ta && a[i] * rin >= mu) {
			ta = t[i] * rin;
			mu = a[i] * rin;
		}
		else {
			ta = t[i] * (rin + 1);
			mu = a[i] * (rin + 1);
		}
	}
	cout << ta + mu << endl;
	getchar(); getchar();
	return 0;
}

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

a = list(map(int, input().split()))
a.sort(reverse=True)

ans = a[0]

cnt = 1
i = 1
while cnt < n-1:
    cnt += 2
    ans += a[i] * 2
    i += 1

if cnt == n:
    ans -= a[i-1]

print(ans)    



Measured memory_bytes: 105140
#include <stdio.h>
 
int main() {

	int A,B,X;

	scanf("%d %d %d",&A,&B,&X);

	if(X<A){
	printf("NO\n");
	}
	else{
		if(A+B>=X){
		printf("YES\n");
		}
		else{
		printf("NO\n");
		}
	}

		return 0;
	}

Measured memory_bytes: 128
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;

typedef long long ll;
//typedef pair<int,int> Pint;
typedef pair<ll, ll> P;
//typedef pair<int, pair<int, int>> P;
//typedef tuple<int,int,int> T;
typedef vector<ll> vec;
typedef vector<vec> mat;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define revrep(i, n) for(ll i = n-1; i >= 0; i--)
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}

ll INFL = 1000000000000000010;//10^18 = 2^60
int INF = 1000000000;//10^9
ll MOD  = 1000000007;
//vector<int> dy = {0,0,1,-1};
//vector<int> dx = {1,-1,0,0};


int main(){
  vector<int> group(13);
  group[1] = 1;
  group[2] = 3;
  group[3] = 1;
  group[4] = 2;
  group[5] = 1;
  group[6] = 2;
  group[7] = 1;
  group[8] = 1;
  group[9] = 2;
  group[10] = 1;
  group[11] = 2;
  group[12] = 1;
  int a, b; cin >> a >> b;
  if(group[a] == group[b]){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }



}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define debug(var)  do{std::cout << #var << " : "; view(var);}while(0)
using namespace std;
typedef long long ll;
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){for(const auto& v : vv){ view(v); } }
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void viewarr(T arr[], int n) { for(int i = 0; i < n; ++i) std::cout << arr[i] << " "; std::cout << std::endl; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int INF = 1e9;

int main() {
    int A, B, K;
    cin >> A >> B >> K;
    rep(i,K) {
        if(i % 2 == 0){
        if(A % 2 == 1) --A;
        B += A/2;
        A /= 2;
    }else{
        if(B % 2 == 1) --B;
        A += B/2;
        B /= 2;
    }}
    printf("%d %d\n", A, B);
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>

const int MAXN = 1e5 + 5;

int n;
char s[MAXN];
int num[MAXN], left[MAXN], right[MAXN];

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (int i = 1; i <= n; ++i) {
        if (s[i] == 'L') {
            for (int j = i - 1; j; --j) {
                while (left[j]) {
                    j = left[j];
                }
                if (s[j] == 'R') {
                    left[i] = j;
                    if ((i - j) & 1)
                        ++num[j + 1];
                    else
                        ++num[j];
                    break;
                }
            }
        }
    }
    for (int i = n; i; --i) {
        if (s[i] == 'R') {
            for (int j = i + 1; j <= n; ++j) {
                while (right[j])
                    j = right[j];
                if (s[j] == 'L') {
                    right[i] = j;
                    if ((j - i) & 1)
                        ++num[j - 1];
                    else 
                        ++num[j];
                    break;
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        printf("%d ", num[i]);
    }
    return 0;
}

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

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

    vector<int> X(N);
    int mean = 0;
    for(int i = 0; i < N; i++){
        cin >> X.at(i);
        mean += X.at(i);
    }
    
    int m1,m2,m3;
    m1 = mean/N;
    m2 = m1+1;
    m3 = m1-1;
    int ans = 0;
    int a1=0,a2=0,a3=0;
    for(int i = 0; i < N; i++){
        a1 += pow((X.at(i)-m1),2);
        a2 += pow((X.at(i)-m2),2);
        a3 += pow((X.at(i)-m3),2);
    }
    ans = min(a1,a2);
    ans = min(ans,a3);
    cout << ans << endl;
    
}

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

struct SCard {
    char suit;
    int num;
};

void BubbleSort(std::vector<SCard> &v)
{
    int size = v.size();
    for (int i = 0; i < size; ++i) {
        for (int j = size - 1; j >= 0; --j) {
            if (v[j].num < v[j-1].num) {
                SCard tmp = v[j];
                v[j] = v[j-1];
                v[j-1] = tmp;
            }
        }
    }
}

void SelectionSort(std::vector<SCard> &v)
{
    int size = v.size();
    for (int i = 0; i < size; ++i) {
        int minj = i;
        for (int j = i; j < size; ++j) {
            if (v[j].num < v[minj].num) {
                minj = j;
            }
        }
        if (i != minj) {
            SCard tmp = v[i];
            v[i] = v[minj];
            v[minj] = tmp;
        }
    }
}

void PrintCards(const std::vector<SCard>& v)
{
    int size = v.size();
    for (int i = 0; i < size; ++i) {
        std::cout << (i ? " " : "") << static_cast<char>(v[i].suit) << v[i].num;
    }
    std::cout << std::endl;
}

int main(void)
{
    int n;
    std::cin >> n;
    
    std::vector<SCard> cards(n);
    for (int i = 0; i < n; ++i) {
        std::string tmp;
        std::cin >> tmp;
        cards[i].suit = tmp[0];
        cards[i].num = tmp[1] - '0';
    }
    std::vector<SCard> cardsSel = cards;
    
    BubbleSort(cards);
    PrintCards(cards);
    std::cout << "Stable" << std::endl;

    SelectionSort(cardsSel);
    PrintCards(cardsSel);
    bool isStable = true;
    for (int i = 0; i < n; ++i) {
        if (cards[i].suit != cardsSel[i].suit) {
            isStable = false;
            break;
        }
    }
    std::cout << (isStable ? "Stable" : "Not stable") << std::endl;
    return 0;
}

Measured memory_bytes: 1228
import java.util.Scanner;

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

	    for(int i=0; i<N; ++i) {
	        stones[i] = sc.nextInt();
        }

	    int r = minimumTotalCost(stones, N);
	    System.out.println(r);
    }

    public static int minimumTotalCost(int[] s, int N) {
        int[] v = new int[N];
        v[0] = 0;
        v[1] = Math.abs(s[0]-s[1]);

        for(int i=2; i<N; ++i) {
            v[i] = Math.min(Math.abs(s[i-1]-s[i]) +v[i-1], Math.abs(s[i-2]-s[i]) +v[i-2]);
        }

        return v[N-1];
    }
}


Measured memory_bytes: 49096
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b;
  int c[10005];
  cin>>a>>b;
  int d=a;
  for(int i=0;i<b;i++){
    cin>>c[i];
    d-=c[i];
  }
  if(d<0)
    cout<<-1<<endl;
  else
    cout<<d<<endl;
  return 0;
}

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

int solve(string str)
{
    stack<char> colorStack;
    for(auto ele : str)
    {
        if(colorStack.empty()) colorStack.push(ele);
        
        else if(colorStack.top() != ele) colorStack.pop();
        else colorStack.push(ele);
    }
    
    return str.length() - colorStack.size();
}
int main() {
    string str;
    cin >> str;
    cout << solve(str) << endl;
	return 0;
}

Measured memory_bytes: 512
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		int N = sc.nextInt();
		int[] L = new int[N];
		for (int i = 0; i < N; i++) {
			L[i] = sc.nextInt();
		}
		sc.close();

		Arrays.sort(L);

		int ans = 0;

		for (int i = 0; i < N - 2; i++) {
			for (int j = i + 1; j < N - 1; j++) {
				int x = lowerBound(L, j + 1, N, L[i] + L[j]) - 1;
				ans += x - j;
			}
		}

		out.println(ans);

	}

	public static void main(String[] args) {
		new Main()._main(args);
	}

	private static int lowerBound(int[] a, int st, int ed, int k) {
		if (st == ed - 1) {
			if (a[st] < k) {
				return st + 1;
			} else {
				return st;
			}
		}

		int m = (ed - st) / 2 + st;
		if (a[m] < k) {
			// 右側
			return lowerBound(a, m, ed, k);
		} else {
			// 左側
			return lowerBound(a, st, m, k);
		}
	}
}


Measured memory_bytes: 26176
import Data.List
main = getLine >>= print . fst . foldl' ff (0, (0, 0))

ff :: (Int, (Int, Int)) -> Char -> (Int, (Int, Int))
ff (n, (g, p)) 'g'
    | p == g = (n, (g + 1, p))
    | p < g = (n + 1, (g, p + 1))
    | otherwise = error "unreachable"
ff (n, (g, p)) _
    | p == g = (n - 1, (g + 1, p))
    | p < g = (n, (g, p + 1))
    | otherwise = error "unreachable"


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

int main(){
    int Q;
    cin >> Q;
    vector<int> sum(100001,0);
    for(int i=2;i<=100001;i++){
        map<int,int> m;
        int n = i;
        for(int j=2;j*j<=i;j++){
            while(n%j==0){
                m[j]++;
                n /= j;
            }
        }
        if(n!=1) m[n]++;
        if(m.size()==1){
            if((m.begin()->second)>=4) sum[i]++;
        }else if(m.size()>=3) sum[i]++;
        else{
            bool ok = false;
            for(auto x:m) if(x.second>=2) ok = true;
            sum[i] += ok;
        }
    }
    for(int i=1;i<=100000;i++) sum[i] += sum[i-1];
    for(int i=1;i<=Q;i++){
        int N;
        cin >> N;
        cout << sum[N] << endl;
    }

}


Measured memory_bytes: 3108
#include <iostream>
#include <cmath>

using namespace std;

#define EPS (1e-10)

int main()
{
    double xa, xb, xc, xd;
    double ya, yb, yc, yd;

    while (cin >> xa >> ya >> xb >> yb
           >> xc >> yc >> xd >> yd) {
        xb -= xa;
        yb -= ya;
        xd -= xc;
        yd -= yc;

        if (abs(xb * xd + yb * yd) < EPS)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    
    return 0;
}

Measured memory_bytes: 1216
using System;
using System.Collections.Generic;
using System.Linq;
using BitArray = System.Collections.BitArray;
using BigInteger = System.Numerics.BigInteger;

namespace AtCoderProject
{
    public struct Cake
    {
        public long val;
        public bool type;
    }

    public class Program
    {
        public object Calc()
        {
            var line = consoleReader.ReadLineSplitInt32();
            var A = line[0];
            var B = line[1];
            var C = line[2];

            return (A==B && B==C) ?"Yes":"No";
        }

        private readonly ConsoleReader consoleReader;
        public Program() : this(new ConsoleReader()) { }
        public Program(ConsoleReader consoleReader) { this.consoleReader = consoleReader; }
        static void Main() => Console.WriteLine(new Program().Calc());
    }

    public class ConsoleReader
    {
        public virtual string ReadLine() => Console.ReadLine();
        public int ReadLineInt32() => int.Parse(ReadLine());
        public long ReadLineInt64() => long.Parse(ReadLine());
        public ulong ReadLineUInt64() => ulong.Parse(ReadLine());
        public double ReadLineDouble() => double.Parse(ReadLine());
        public string[] ReadLineSplit() => ReadLine().Split().ToArray();
        public int[] ReadLineSplitInt32() => ReadLine().Split().Select(s => int.Parse(s)).ToArray();
        public long[] ReadLineSplitInt64() => ReadLine().Split().Select(s => long.Parse(s)).ToArray();
        public ulong[] ReadLineSplitUInt64() => ReadLine().Split().Select(s => ulong.Parse(s)).ToArray();
        public double[] ReadLineSplitDouble() => ReadLine().Split().Select(s => double.Parse(s)).ToArray();

        public IEnumerable<string> RepeatReadLines(int count)
        {
            for (int i = 0; i < count; i++)
                yield return ReadLine();
        }
        public IEnumerable<int> RepeatReadLinesInt32(int count)
        {
            for (int i = 0; i < count; i++)
                yield return ReadLineInt32();
        }
        public IEnumerable<long> RepeatReadLinesInt64(int count)
        {
            for (int i = 0; i < count; i++)
                yield return ReadLineInt64();
        }
        public IEnumerable<string[]> RepeatReadLinesSplit(int count)
        {
            for (int i = 0; i < count; i++)
                yield return ReadLineSplit();
        }
    }
    static class DicExt
    {
        public static V GetOrDefault<K, V>(this Dictionary<K, V> dic, K key, V defaultValue = default(V))
        {
            V val;
            return dic.TryGetValue(key, out val) ? val : defaultValue;
        }
    }
}


Measured memory_bytes: 13268
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
typedef long long ll;
#define MOD 1000000007
using namespace std;
ll h, w, n;
ll check(ll x, ll y, ll i, ll j, map<pair<ll, ll>, ll> &mp) {
    ll count = 0;
    for(ll k = x - i; k < x - i + 3; k++) {
        for(ll l = y - j; l < y - j + 3; l++) {
            if(k < 0 || k >= h || l < 0 || l >= w) {
                return -1;
            } else {
                if(mp.find(make_pair(k, l)) != mp.end()) {
                    count++;
                }
            }
        }
    }
    return count;
}
int main() {
    cin >> h >> w >> n;
    map<pair<ll, ll>, ll> mp;
    for(int i = 0; i < n; i++) {
        ll a, b;
        cin >> a >> b;
        a--, b--;
        mp[make_pair(a, b)] = 1;
    }
    vector<ll> ans(10, 0);
    for(auto e : mp) {
        ll x = e.first.first;
        ll y = e.first.second;
        // cout << x << ":" << y << endl;
        for(ll i = 0; i < 3; i++) {
            for(ll j = 0; j < 3; j++) {
                ll count = check(x, y, i, j, mp);
                if(count != -1) {
                    ans[count]++;
                }
            }
        }
    }
    ll sum = 0;
    for(int i = 1; i < 10; i++) {
        ans[i] /= i;
        sum += ans[i];
    }
    ans[0] = (h - 2) * (w - 2) - sum;
    for(auto e : ans) {
        cout << e << endl;
    }
}


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

	//for(i=0;i<n;++i){}
	
	int main()
	{
		ios_base::sync_with_stdio(0);
		cin.tie(0);
		//int t; cin>>t; while(t--){	}
		 char x; 
    cin >> x; 
    if (isupper(x))  
        cout << "A"<<"\n"; 
    else 
        cout << "a"<<"\n"; 
	    return 0;
	
	}

Measured memory_bytes: 3608
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    N = int(readline())
    A = [int(i) for i in readlines()]
    B = sorted(A) 
    mx = B[-1]
    mx2 = B[-2]
    for i in A:
        if mx == i:
            print(mx2)
        else:
            print(mx)
if __name__ == '__main__':
    main()


Measured memory_bytes: 20516
//============================================================================
// Name        : ALDS1_3_D.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct LAKE {
	int start;	// start is negasitive integer.
	int end;	// end is positive integer.
	int square;
};

bool isInLake(int left, int right, vector<LAKE>& L, int& targetL) {
	for(int i=0; i<(int)L.size(); ++i) {
		if(L[i].start > left && L[i].end > right) {
			targetL=i;
			return true;
		}
	}
	targetL = -1;
	return false;
}

int main() {
	int n,max,min,h,k=0,S=0,idxL;
	string buf;
	LAKE tempL;
	vector<LAKE> L;
	vector<queue<int> > land;
	cin >> buf;
	n=(int)buf.size()+1;
	land.resize(2*n);
	h=0;
	max=n;
	min=n;
	for(int i=1; i<=n; ++i) {
		if(buf[i-1]=='/' ) {
			if(i!=1&&buf[i-2]=='/') ++h;
			land[n+h].push(i);
			if(n+h>max) { max=n+h; }
		} else if (buf[i-1]=='\\') {
			if(i!=1&&buf[i-2]!='/') --h;
			land[n+h].push(-i);
			if(n+h<min) { min=n+h; }
		} else if (buf[i-1]=='_') {
			if(i!=1&&buf[i-2]=='/') {
				++h;
			}
		}
	}
	for(int i=max; i>=min; --i) {
		int temp_l,temp_r;
		while(!(land[i].empty())) {
			temp_l=land[i].front();
			land[i].pop();
			if(temp_l<0 && !(land[i].empty()) ) {
				temp_r=land[i].front();
				land[i].pop();
				if(isInLake(temp_l,temp_r,L,idxL)==false) {
					tempL.start=temp_l;
					tempL.end=temp_r;
					tempL.square=temp_r+temp_l;
					L.push_back(tempL);
					++k;
				} else {
					L[idxL].square+=temp_r+temp_l;
				}
			}
		}
	}
	sort(L.begin(),L.end(),[](LAKE L1,LAKE L2) {
		return L1.end<L2.end;
	});
	for(int i=0; i<k; ++i) {
		S+=L[i].square;
	}
	printf("%d\n%d",S,k);
	for(int i=0; i<k; ++i) {
		printf(" %d",L[i].square);
	}
	printf("\n");
	return 0;
}

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

vector<ll> to[200000];

int main(){
    ll n,m;cin>>n>>m;
    ll h[100010];
    rep(i,0,n)cin>>h[i];
    rep(i,0,m){
        ll a,b;cin>>a>>b;
        a--;b--;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    ll an=0;
    rep(i,0,n){
        if(to[i].size()==0){
            an++;
            continue;
        }
        int ok=1;
        rep(j,0,to[i].size()){
            if(h[i]<=h[to[i][j]])ok=0;
        }
        if(ok)an++;
    }
    cout<<an<<endl;
}
    









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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n; cin >> n;
  vector<int> a(n + 1);
  vector<int> b(n + 1);
  for (int i = 1; i < n + 1; i++) cin >> a[i];
  for (int i = 1; i < n + 1; i++) cin >> b[i];
  for (int i = 0; i < n; i++) {
    a[i+1] += a[i]; b[i+1] += b[i];
  }
  int res = 0;
  for (int i = 1; i < n + 1; i++) {
    res = max(res, a[i] + b[n] - b[i-1]);
  }
  cout << res << '\n';
  return 0;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const int INF = 1000000005;
const long double EPS = 1e-10;

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

  if (n == 1) {
    cout << 4 << endl;
    return 0;
  }
  else if (n == 2) {
    cout << 16 << endl;
    return 0;
  }

  ll dp[n][4][4][4][4];
  memset(dp, 0, sizeof(dp));
  rep(j, 4) {
    rep(k, 4) {
      rep(l, 4) {
        if (j == 1 && k == 2 && l == 0) continue;
        if (j == 2 && k == 1 && l == 0) continue;
        if (j == 1 && k == 0 && l == 2) continue;
        dp[2][j][k][l][0] = 1;
      }
    }
  }

  FOR(i, 3, n) {
    rep(j, 4) {
      rep(k, 4) {
        rep(l, 4) {
          if (j == 1 && k == 2 && l == 0) continue;
          if (j == 2 && k == 1 && l == 0) continue;
          if (j == 1 && k == 0 && l == 2) continue;
          rep(m, 4) {
            if (j == 1 && k == 2 && m == 0) continue;
            if (j == 1 && l == 2 && m == 0) continue;
            rep(o, 4) {
              dp[i][j][k][l][m] = (dp[i][j][k][l][m] + dp[i - 1][k][l][m][o]) % mod;

            }
          }
        }
      }
    }
  }

  ll ans = 0;
  rep(j, 4) {
    rep(k, 4) {
      rep(l, 4) {
        rep(m, 4) {
          ans = (ans + dp[n - 1][j][k][l][m]) % mod;
        }
      }
    }
  }
  cout << ans << endl;

  
  
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<long long> vll;
typedef pair<int,int> pint;
typedef pair<long long, long long> pll;

#define MP make_pair
#define PB push_back
#define ALL(s) (s).begin(),(s).end()
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << 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; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P) 
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P) 
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P) 
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s; }



int n, m, a;

int main() {
    while (cin >> n >> m) {
        if (n == 0 && m == 0) break;
        vector<pint> res(m);
        for (int i = 0; i < m; ++i) res[i] = pint(0, i+1);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                cin >> a;
                res[j].first -= a;
            }
        sort(ALL(res));
        for (int i = 0; i < m; ++i) {
            cout << res[i].second;
            if (i != m-1) cout << " ";
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 1200