akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;

ll mod = 1e9+7 ;
const ld error = 1e-8;
const ld PI = acosl(-1); //const ld PI = acosl(-1)

#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define eq(x, y) (fabs((x)-(y))<error)
#define bt(i) (1LL<<(i))

#define debug(x) cerr<<#x<<" = "<<(x)<<"\n"
#define hoise cerr<<"hoise - "<<__LINE__<<"\n"
#define tham getchar()
//mt19937 rng((unsigned)chrono::system_clock::now().time_since_epoch().count()); //mt199937_64 for ll
//mt19937 rng(199);

inline ll MOD(ll x, ll m = mod){
    ll y = x % m;
    return (y >= 0) ? y: y+m;
}

const int inf = 1e9;
const ll infl = 1e18+1;
const int nmax = 2e5+ 10;
///===========================================  template  =======================================================

vector<ll> v;
void factorize(ll n){
    v.clear();
    ll i;
    for(i = 1; i*i<n; i++){
        if(n % i == 0){
            v.push_back(i);
            v.push_back(n/i);
        }
    }
    if(n == i*i) v.push_back(i);
    return;
}

int main(){
    FASTIO;
    ll n;

    cin>>n;
    factorize(n-1);
    ll ans = v.size()-1;
    factorize(n);

    for(ll x: v){
        if(x == 1) continue;
        ll m = n;
        while(m % x == 0) m /= x;
        if(m % x == 1) ans++;
    }

    cout<<ans;
    return 0;
}


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


int main(){
	int n;
	cin >> n;
	vector<int> b(n);
	for(int i = 0; i < n; i++){
		cin >> b[i];
		b[i]--;
	}
	vector<int> ans;
	while(b.size() > 0){
		int z = -1;
		for(int i = 0; i < b.size(); i++){
			if(b[i] == i) z = i;
		}
		if(z == -1){
			cout << -1 << endl;
			exit(0);
		}
		ans.push_back(z);
		b.erase(b.begin() + z);
	}
	reverse(ans.begin(), ans.end());
	for(int x : ans){
		cout << x + 1 << '\n';
	}
}


Measured memory_bytes: 256
tmp = list(map(int,input().split()))
h , w = tmp[0],tmp[1]
n=int(input())
t=[]
ans =[]
As = list(map(int,input().split()))
for i in range(1,n+1):
  for j in range(As[i-1]):
    t.append(i)
for i in range(h):
  j = t[:w]
  if i %2:
    j.reverse()
  print(*j)
  t=t[w:]

Measured memory_bytes: 3828
#include<bits/stdc++.h> 
#define REP(i, b) for(int i = 0; i < (b); i++)
#define REPS(i, b) for(int i = 1; i <= (b); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;

signed main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    string S, T, U;
    ll A, B;
    cin >> S >> T >> A >> B >> U;
    if(U == S) A--;
    else B--;
    cout << A << " " << B << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
   long long int n,t,i,a[10000],sum=0;
   cin>>t;
   cin>>n;
   for(i=0;i<n;i++)
   {
       cin>>a[i];
       sum=sum+a[i];
   }
   if(t>sum)
       cout<<t-sum;
   else if(t==sum)
       cout<<"0";
   else
       cout<<"-1";
    return 0;
}

Measured memory_bytes: 3704
#include<cstdio>
#include<algorithm>
#define MN 110001
#define ll long long
using namespace std;

ll read_p,read_ca;
inline ll read(){
	read_p=0;read_ca=getchar();
	while (read_ca<'0'||read_ca>'9') read_ca=getchar();
	while (read_ca>='0'&&read_ca<='9') read_p=read_p*10+read_ca-48,read_ca=getchar();
	return read_p;
}
struct na{int x,p;}a[MN];
bool operator < (na a,na b) {return a.x==b.x?a.p<b.p:a.x>b.x;}
int n;
ll mmh[MN],k;
int main(){
	register int i,j;
	n=read();
	for (i=1;i<=n;i++) a[i].x=read(),a[i].p=i;
	sort(a+1,a+1+n);
	for (i=1;i<=n;){
		k=1LL*i*a[i].x;
		for (j=i+1;j<=n;k+=a[j].x,j++) if (a[j].p<a[i].p) break;
		mmh[a[i].p]+=k-1LL*(j-1)*a[j].x;i=j;
	}
	for (i=1;i<=n;i++) printf("%lld\n",mmh[i]);
}

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

        int main() {
          ll N, K;
          cin>> N >> K;
          
          if(K%2==1){
            cout<< (N/K)*(N/K)*(N/K) << endl;
          }else{
            ll a = (N/K);
            ll b= (2*N/K) -  (N/K); 
            cout<< a*a*a + b*b*b << endl;
          }

        }

Measured memory_bytes: 256
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def solve(X: int):
    ret = 0
    i = 100
    while i < X:
        i = int(i * 1.01)
        ret += 1
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    solve(X)

if __name__ == '__main__':
    main()


Measured memory_bytes: 63492
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi  vector<int> 
#define   dbg(x)  cerr << #x << " = " << x << '\n'
#define   sz(x)  (int)x.size()
#define   ff   first
#define   ss   second
#define   pii  pair<int,int>
using namespace std;

inline void solve(){ 
    int a,b,c,x,y,ans=0; 
    cin >> a >> b >> c >> x >> y ; 
    if (a+b>2*c){ 
        int f = min(x,y) ; 
        ans = f*2*c; 
        x -= f;y-=f; 
        if (x){ 
            if (c*2<=a) ans += x*c*2;
            else ans += x*a;
        }
        else {
            if (c*2 <= b) ans += c*2*y;
            else ans += y*b;
        }
    }
    else 
        ans = x*a+y*b;
    cout << ans << endl;
}

signed main()
{
    int n=1; // cin>>n;
    while (n--) solve();
    return 0;
}


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

int main()
{
  int H,W;
  cin>>H>>W;
  vector<string> cicada(H);
  vector< vector<int> > dp(H,vector<int>(W,0));
  for(int i=0;i<H;i++)cin>>cicada[i];
  for(int i=0;i<H;i++)for(int j=0;j<W;j++)cicada[i][j]-='0';
  for(int i=1;i<H;i++)dp[i][0]=dp[i-1][0]+cicada[i][0];
  for(int j=1;j<W;j++)dp[0][j]=dp[0][j-1]+cicada[0][j];
  for(int i=1;i<H;i++)for(int j=1;j<W;j++)dp[i][j]=min(dp[i-1][j],dp[i][j-1])+cicada[i][j];
  cout<<dp[H-1][W-1]<<endl;
}

Measured memory_bytes: 0
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<string>

using namespace std;

#define rep(i,n) for(int i=0;i<int(n);i++)
#define reps(i,n) for(int i=1;i<=int(n);i++)
#define sint(i) scanf("%d",&i);
#define sintt(i,j) scanf("%d%d",&i,&j);
#define sinttt(i,j,k) scanf("%d%d%d",&i,&j,&k);
#define sintttt(i,j,k,m) scanf("%d%d%d%d",&i,&j,&k,&m);

#define INF 1010000000
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

class S{
	public:
	int p,n;
	S(int p,int n):p(p),n(n){}
	
	bool operator<(const S& a)const{
		return n>a.n;
	}
};

////////////djk//////////////////////////////////////////
int main(){
	while(1){
		int n,m;
		sintt(n,m);
		if(n==0)break;
		vector<pair<int,int> > load[101];
		
		rep(o,m){
			int a;
			sint(a);
			if(a==1){
				int b,c,d;
				sinttt(b,c,d);
				load[b].push_back(make_pair(c,d));
				load[c].push_back(make_pair(b,d));
			}else{
				int s,g;
				sintt(s,g);
				
				priority_queue<S> que;
				que.push(S(s,0));
				
				int visit[101];
				rep(i,101)visit[i]=0;
				
				int ans=-1;
			
				while(1){
					if(que.empty()==1){
						break;
					}
					
					S u=que.top();
					que.pop();
					
					if(visit[u.p]==1){
						continue;
					}
					visit[u.p]=1;
					
					if(u.p==g){
						ans=u.n;
						break;
					}
					
					rep(i,load[u.p].size()){
						que.push( S( load[u.p][i].first,  u.n+load[u.p][i].second));
					}
				}
				printf("%d\n",ans);
			}
		}
	}
}

Measured memory_bytes: 984
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <cassert>

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

using namespace std;
typedef long long ll;
typedef unsigned long ul;
typedef pair<ul, ul> P;

int main() {
    int n;
    ll x;
    cin >> n >> x;
    vector<ll> a(n);
    for (auto &c : a) cin >> c;
    vector<ll> b = a;
    ll ans = 1e18;

    REP(i,n){
        REP(j,n){
            b[j] = min(b[j], a[(j-i+n)%n]);
        }
        ll buf = x*i;
        REP(j,n){
            buf += b[j];
        }

        ans = min(ans, buf);
    }
    cout << ans << endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip> // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple> // get<n>(xxx)
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set> // S.insert(M);
// if (S.find(key) != S.end()) { }
// for (auto it=S.begin(); it != S.end(); it++) { }
// auto it = S.lower_bound(M);
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib> // atoi(xxx)
using namespace std;

typedef long long ll;

//const int dx[4] = {1, 0, -1, 0};
//const int dy[4] = {0, 1, 0, -1};

// const int C ;
// const int M = 1000000007;

int main () {
  ll x, y;
  cin >> x >> y;
  vector<int> V;
  if (y+x >= 0) {
    V.push_back(y+x+1);
  }
  if (y-x > 0) {
    V.push_back(y-x);
  }
  if (-y+x >= 0) {
    V.push_back(-y+x+2);
  }
  if (-y-x > 0) {
    V.push_back(-y-x+1);
  }
  cout << *min_element(V.begin(), V.end()) << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<queue>
#include<map>
#include<string>
#include<vector>
#include<algorithm>
#define all(c) c.begin(),c.end()
#define pb push_back
#define INF 10000000
using namespace std;
typedef pair<int,int> P;
int w,h;
vector<string> s;
P d[10];
int antime;
P q;
map<int,int> mp;
string op;
int dp[20][20];
bool in(P n){
	if(n.second>=0&&n.second<w&&n.first>=0&&n.first<h)
		return true;
	return false;
}
int ans;
int ret(P b,int time){
	//cout<<b.first<<"  "<<b.second<<endl;
	if(time>400)
	return INF;
	if(dp[b.first][b.second]<=time){
		q.first=b.first;
		q.second=b.second;
		return time;
	}
	P nb;
	nb.first=b.first+d[op[time%op.size()]-'0'].first;
	nb.second=b.second+d[op[time%op.size()]-'0'].second;
	if(!in(nb))
		nb=b;
	return ret(nb,time+1);
}
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
void bfs(P a){
	queue<P> que;
	que.push(a);
	dp[a.first][a.second]=0;
	while(!que.empty()){
		P t=que.front(),nt;
		que.pop();
		//cout<<dp[t.first][t.second]<<endl;
		for(int i=0;i<4;i++){
			nt.first=t.first+dy[i];
			nt.second=t.second+dx[i];
			if(in(nt)&&dp[nt.first][nt.second]==INF&&s[nt.first][nt.second]!='#'){
				que.push(nt);
				dp[nt.first][nt.second]=dp[t.first][t.second]+1;
			}
		}
	}
}
int main(){
	d[5]=P(0,0);d[8]=P(-1,0);d[6]=P(0,1);d[4]=P(0,-1);d[2]=P(1,0);
	mp[0]=5;mp[1]=8;mp[2]=6;mp[3]=4;mp[4]=2;
	while(cin>>h>>w,h||w){
		s.clear();
		P a,b;
		antime=INF;
		//memset(dp,-1,sizeof(dp));
		for(int i=0;i<h;i++)
		for(int j=0;j<w;j++)
		dp[i][j]=INF;
		for(int i=0;i<h;i++){
			string t;
			cin>>t;
			s.pb(t);
			for(int j=0;j<t.size();j++){
				if(t[j]=='A'){
					a.first=i;a.second=j;
				}else if(t[j]=='B'){
					b.first=i;b.second=j;
				}
			}
		}
		cin>>op;
		bfs(a);
		int ans=ret(b,0);
		if(ans!=INF)
			cout<<ans<<" "<<q.first<<" "<<q.second<<endl;
		else
			cout<<"impossible"<<endl;
	}
	return 0;
}

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

int main(){
    string s;
    stack<int> box;
    while(cin >> s){
        if(s[0] == '+'){
            int num1, num2;
            num1 = box.top(); box.pop();
            num2 = box.top(); box.pop();
            box.push(num1 + num2);
        } else if(s[0] == '*'){
            int mul1, mul2;
            mul1 = box.top(); box.pop();
            mul2 = box.top(); box.pop();
            box.push(mul1 * mul2);
        } else if(s[0] == '-'){
            int sub1, sub2;
            sub1 = box.top(); box.pop();
            sub2 = box.top(); box.pop();
            box.push(sub2 - sub1);
        } else {
            box.push(stoi(s));
        }
    }
    cout << box.top() << endl;
    return 0;
}


Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
int main(){
  int X, N;
  cin >> X >> N;
  vector<int> p (N);
  for(int i =0; i < N; i++){
    cin >> p[i];
  }
  bool judge = true;
  vector<int> hantei(2);
  for(int i = X; i < X + 101; i++){
    for(int j = 0; j < N; j++){
      if(p[j]== i){
        judge = false;
        break;
      }
    }
    if(judge == true){
      hantei[0] = i;
      break;
    }else{
      judge = true;
    }
  }
  bool shinpan = true;
  for(int i = X; i > X - 101; i--){
    for(int j = 0; j < N; j++){
      if(p[j]== i){
        shinpan = false;
        break;
      }
    }
    if(shinpan == true){
      hantei[1] = i;
      break;
    }else{
      shinpan = true;
    }
  }
  if(hantei[0] - X < X - hantei[1]){
    cout << hantei[0] << endl;
  }else{
    cout << hantei[1] << endl;
  }
}
  

Measured memory_bytes: 3632
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

func main() {
	fsc := NewFastScanner()

	N := fsc.NextInt()
	var rates []int
	colors := map[int]int{}
	for i := 0; i < N; i++ {
		rates = append(rates, IntMin(8, fsc.NextInt()/400))
		if rates[i] <= 7 {
			colors[rates[i]] = 1
		}
	}
	sort.Ints(rates)
	resMin := IntMax(1, len(colors))
	resMax := len(colors)
	for i := 0; i < N; i++ {
		if rates[i] >= 8 {
			resMax++
		}
	}
	fmt.Println(resMin, resMax)
}

//template
type FastScanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewFastScanner() *FastScanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1024)
	return &FastScanner{r: rdr}
}
func (s *FastScanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *FastScanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *FastScanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}
func (s *FastScanner) NextInt64() int64 {
	v, _ := strconv.ParseInt(s.Next(), 10, 64)
	return v
}

func (s *FastScanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *FastScanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}

//Max,Min
func IntMax(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func Int64Max(a, b int64) int64 {
	if a < b {
		return b
	}
	return a
}
func Float64Max(a, b float64) float64 {
	if a < b {
		return b
	}
	return a
}

func IntMin(a, b int) int {
	if a > b {
		return b
	}
	return a
}

func Int64Min(a, b int64) int64 {
	if a > b {
		return b
	}
	return a
}
func Float64Min(a, b float64) float64 {
	if a > b {
		return b
	}
	return a
}

//Gcd
func IntGcd(a, b int) int {
	if a < b {
		b, a = a, b
	}
	if b == 0 {
		return a
	}
	return IntGcd(b, a%b)
}
func Int64Gcd(a, b int64) int64 {
	if a < b {
		b, a = a, b
	}
	if b == 0 {
		return a
	}
	return Int64Gcd(b, a%b)
}

func IntAbs(a int) int {
	if a < 0 {
		a *= -1
	}
	return a
}

func Int64Abs(a int64) int64 {
	if a < 0 {
		a *= -1
	}
	return a
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
int main(){
    string s,t,u;
    cin>>t;
    s=t;
    int a=0,y=0,A[200001];
    rep(i,t.size()) {
        if(t[i]=='x') t.erase(t.begin()+i),y++,i--;
        else A[a]=y,y=0,a++;
    }
    A[a]=y,y=0,a++;
    u=t;
    reverse(t.begin(),t.end());
    if(u!=t){
        cout<<-1;
        return 0;
    }
    ll ans=0;
    rep(i,a/2) ans+=max(A[i],A[a-1-i])-min(A[i],A[a-1-i]);
    cout<<ans;
}

Measured memory_bytes: 1024
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <iomanip>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;

int dp[150][80][10]={};
int main() {
while(1){
	int n=0,m=0;
	cin >> n >> m;
	vector<int> pos[150];
	vector<int> slip[150];
	if(n==0&&m==0)return 0;
	for(int i=0;i<n;i++){
		int k;
		cin >> k;
		for(int j=0;j<k;j++){
			int x,d;
			cin >> x >> d;
			pos[i].push_back(x);
			slip[i].push_back(d);
			for(int u=0;u<=m;u++){
				if(i==0){
					dp[i][u][j]=0;
					continue;
				}
				if(i==1&&u>0){
					dp[i][u][j]=0;
					continue;
				}
				dp[i][u][j]=1<<30;
				for(int r=0;r<pos[i-1].size();r++){
					int v=dp[i-1][u][r]+abs(pos[i-1][r]-x)*(slip[i-1][r]+d);
					dp[i][u][j]=min(dp[i][u][j],v);
				}
				if(u==0){
					continue;
				}
				for(int r=0;r<pos[i-2].size();r++){
					int v=dp[i-2][u-1][r]+abs(pos[i-2][r]-x)*(slip[i-2][r]+d);
					dp[i][u][j]=min(dp[i][u][j],v);
				}
				//cout << i << ", " << u << ", " << j << ": " << dp[i][u][j] << endl;
				//cout << pos[i].size() << endl;
			}
		}
	}
	int ret=1<<30;
	for(int i=0;i<pos[n-1].size();i++){
		ret=min(ret,dp[n-1][m][i]);
	}
	if(m>0){
		for(int i=0;i<pos[n-2].size();i++){
			ret=min(ret,dp[n-2][m-1][i]);
		}
	}
	cout << ret << endl;
}
}

Measured memory_bytes: 1720
def seki_day(m, d):
    d10 = d // 10
    d1 = d - d10 * 10

    if d1 >= 2 and m == d10 * d1:
        return 1
    else:
        return 0

M, D = [int(x) for x in input().split()]

count = 0
for m in range(1, M + 1):
    for d in range(22, D + 1):
        count += seki_day(m, d)

print(count)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,K;
  cin >> N >> K;
  int output = 0;
  for(int i=0;i<N;i++){
    int x;
    cin >> x;
    output += min(abs(x-K),x);
  }
  cout << output*2 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
int main(){
    int Tc;
    int a[9],b[9];
    double acnt,bcnt;
 
    cin >> Tc;
    while(Tc--){
	for(int i = 0 ; i < 9 ; i++){
	    cin >> a[i];
	}
	sort(a,a+9);
	for(int i = 0 ; i < 9 ; i++){
	    cin >> b[i];
	}
	acnt = bcnt = 0;
 
	do{
	    int aa = 0, bb = 0;
	    for(int i = 0 ; i < 9 ; i++){
		if(a[i] > b[i]) aa += a[i] + b[i];
		else bb += a[i] + b[i];
	    }
	    if(aa > bb) acnt++;
	    else bcnt++;
	}while(next_permutation(a,a+9));
	printf("%.6f %.6f\n",acnt/(acnt+bcnt),bcnt/(acnt+bcnt));
    }
    return 0;
}

Measured memory_bytes: 3036
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int a[] = new int[n];
        int count = 0 ;
        for(int i =0 ; i<n ;i++){
            a[i] = sc.nextInt();
            if(a[i]>=k)count++;
        }
        System.out.println(count);
    }
  
}


Measured memory_bytes: 50132
#include <iostream>
#include <math.h>
#include <stdlib.h>

using namespace std;

typedef long long int lli;

lli a, b, c;
lli p, q, r, s;

bool solve()
{
	if(a == 0) return false;
	
	if(c == 0)
	{
		if(a != 1)
		{
			p = a;
			q = b;
			r = 1;
			s = 0;
			return true;
		}
		else
		{
			p = 1;
			q = max(b, (lli)0);
			r = 1;
			s = min(b, (lli)0);
			return true;
		}
	}

	for(lli i=1; i<=a; i++)
	{
		if(i * i > a) break;

		if(a%i==0)
		{
			p = a / i;
			r = i;
			for(lli j=1; j<=abs(c); j++)
			{
				if(c%j==0)
				{
					lli qt = c / j;
					lli st = j;
					if(p * st + r * qt == b)
					{
						q = qt;
						s = st;
						if(p == r) q = max(qt, st), s = min(qt, st);
						return true;
					}
					else if(p * qt + r * st == b)
					{
						q = st;
						s = qt;
						if(p == r) q = max(qt, st), s = min(qt, st);
						return true;
					}
					else if(- p * st - r * qt == b)
					{
						q = -qt;
						s = -st;
						if(p == r) q = max(-qt, -st), s = min(-qt, -st);
						return true;
					}
					else if(- p * qt - r * st == b)
					{
						q = -st;
						s = -qt;
						if(p == r) q = max(-qt, -st), s = min(-qt, -st);
						return true;
					}
				}
			}
		}
	}
	
	return false;
}

int main()
{
	while( 1 )
	{
		cin >> a >> b >> c;
		if(a==0 && b==0 && c==0) break;
		if(solve()) printf("%lld %lld %lld %lld\n", p, q, r, s);
		else printf("Impossible\n");
	}
}

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

vector<int> d;
vector<int> f;
int t;

void dfs(int p, vector<vector<int>> dst) {
  d[p] = t;
  for (int x : dst[p]) {
    if (!d[x]) {
      ++t;
      dfs(x, dst);
    }
  }
  f[p] = ++t;
}

int main() {
  int n;
  cin >> n;
  // bug
  vector<vector<int>> dst;
  dst = vector<vector<int>>(n + 1);
  d = vector<int>(n + 1, 0);
  f = vector<int>(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    int u, k;
    cin >> u >> k;
    for (int j = 0; j < k; j++) {
      int v;
      cin >> v;
      dst[u].push_back(v);
    }
  }
  t = 0;
  // bug:未発見の頂点が残る場合を考えていなかった。
  // dfs(1, 1);
  for (int i = 1; i <= n; i++) {
    if (!d[i]) {
      ++t;
      dfs(i, dst);
    }
  }
  for (int i = 1; i <= n; i++) {
    cout << i << ' ' << d[i] << ' ' << f[i] << endl;
  }
}



Measured memory_bytes: 3584
def f(n):
    for i in range(1,n):
        n*=i
    return n
        
        
while True:
    n=int(input())
    if n==0:
        break
    else:
        a=str(f(n))
        s=0
        l=len(a)
        for i in range(l-1,-1,-1):
            if a[i]=="0":
                s+=1
            else:
                break
        print(s)


Measured memory_bytes: 5712
#include<cstdio>
using namespace std;

int m, nmin, nmax, p[200];
int diff, ans;

int main() {
  while (1) {
    scanf("%d%d%d", &m, &nmin, &nmax);
    if (m == 0) break;
    diff = -1;
    for (int i = 0; i < m; i++) scanf("%d", &p[i]);
    for (int i = nmin-1; i <= nmax-1; i++) {
      if (p[i] - p[i+1] >= diff) {
        ans = i;
        diff = p[i] - p[i+1];
      }
    }
    printf("%d\n", ans + 1);
  }
}



Measured memory_bytes: 2616
/*
氏名：鈴木丈人
学籍番号：190441067
概要：時間の変換プログラム
*/
#include<stdio.h>
int main(void)
{
	int seconds;   //秒
	int minutes;   //分
	int hours;     //時

	scanf("%d", &seconds);   //秒入力
	hours = seconds / 3600;   //時間を求める
	minutes = (seconds / 60) % 60;   //分を求める
	seconds = seconds - hours * 3600 - minutes * 60;   //秒を求める
	printf("%d:%d:%d\n", hours, minutes, seconds);   //表示

	return 0;   //終わり
}


Measured memory_bytes: 2060
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define int long long
#define ld long double
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define LOL cout << '\n';
#define sz(x) ((int)x.size())
#define INF LONG_LONG_MAX
#define NINF LONG_LONG_MIN
#define deb(x) cout << "[" << (#x) << "=" << x << "]" << '\n';
#define deb2(x,y) cout << "[" << (#x) << "=" << x << "] [" << (#y) << "=" << y << "]" << '\n';
#define deb3(x,y,z) cout << "[" << (#x) << "=" << x << "] [" << (#y) << "=" << y << "] [" << (#z) << "=" << z << "]" << '\n';

void solve(){
  int x; cin>>x;
  cout<<(x==0?1:0);LOL
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  int _ = 1; //cin >> _;
  for(int i = 1 ; i <= _ ; i++){
    //cout << "Case #" << i << ": ";
    solve();
  }
  return 0;
}

Measured memory_bytes: 3636
#include <stdio.h>
int main (void){
    while (1){
    int i,ny[10000]={0},ny2[10000]={0},sum=0,sum2=0;
    scanf ("%d",&i);
    if (i==0) break;
    for ( int s=0;s<i;s++){
        scanf ("%d%d",&ny[s],&ny2[s]);
}
for (int s=0;s<i;s++){
    if (ny[s]>ny2[s]){
        sum=sum+ny[s]+ny2[s];
    }
    else if (ny[s]<ny2[s]){
        sum2=sum2+ny[s]+ny2[s];
    }
    else if (ny[s]==ny2[s]){
        sum=sum+ny[s];
        sum2=sum2+ny2[s];
    }
}
    printf ("%d %d\n",sum,sum2);
}
return 0;
}

Measured memory_bytes: 1828
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    int minj = a[0];
    int cnt = 1;
    for(int i = 1; i < n; i++){
        if(minj > a[i - 1])
        minj = a[i - 1];
        if(minj >= a[i])
        cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 1024
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    A = set()
    for _ in range(N):
        S = input().rstrip('\n')
        A.add(S)
    print(len(A))


if __name__ == '__main__':
    main()


Measured memory_bytes: 86796
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define MIN(a,b) ((a) <= (b) ? (a) : (b))
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort( ALL(v) )

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


int main()
{

    ll sum = 0 ;
    int k ; cin>>k;
    for(int i = 1 ; i<= k ; i++)
    {
        for(int j = 1 ; j<= k ; j++){
            for(int h = 1 ; h<=k ; h++)
            {
                int x=  __gcd(i,j);
                sum +=  __gcd(x,h);
            }
        }

    }

    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 3624
import java.io.BufferedReader;
import java.io.InputStreamReader;

//public class Problem0004_SimultaneousEquation {
public class Main {
	public static void main(String[] args) {
		try {
		//	Problem0004_SimultaneousEquation test = new Problem0004_SimultaneousEquation();
			Main test = new Main();
			BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
			
			String line;
			while((line = reader.readLine()) != null) {
				try {
					String[] textArray = line.split(" ");
					double[] numbers = new double[6];
					for(int i = 0; i < textArray.length; i++) {
						numbers[i] = Double.parseDouble(textArray[i]);
					}
					test.showAnswer(numbers);
				} catch(NumberFormatException e) {
					break;
				}
			}
		} catch(Exception e) {
			e.printStackTrace();
		}
	}
	void showAnswer(double[] array) {
		checkLength(array);
		
		double x = getX(array);
		double y = getY(array);
		
		
		System.out.printf("%.3f %.3f%n", x, y);
	}
	double getX(double[] array) {
		checkLength(array);
		
		double x = (array[2]*array[4] - array[1]*array[5]) / (array[0]*array[4] - array[3]*array[1]);
		x = round(x);
		
		return x;
	}
	double getY(double[] array) {
		checkLength(array);
		
		double y = (array[2]*array[3] - array[0]*array[5]) / (array[1]*array[3] - array[0]*array[4]);
		y = round(y);
		
		return y;
	}
	private double round(double number) {
		int large = (int)(number * 10000);
		int small = (int)(number * 1000) * 10;
		double result;
		
		if(large - small < 5) {	//ツ静伉づィツ可コツつー
			result = small;
		} else {	//ツ静伉づィツ湘」ツつー
			result = small + 10;
		}
		result = result/10000;
		return result;
	}
	private void checkLength(double[] array) {
		if(array.length != 6) {
			throw new IllegalArgumentException();
		}
	}
}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
	using namespace std;
	#define all(c) c.begin(),c.end()
	#define init(c) memset(c,0,sizeof c)
	#define S second
	#define F first
	typedef long long ll;
	typedef pair<int,int> pii;
	typedef pair<ll,ll> pll;
	typedef vector<int> vi;
	typedef vector<ll> vl;
	const int N=20000005;
	int n,k,x,t,a,b,m;
	string s;
	vi v;
	int main(){

		cin >> n >> m;
		for(int i =0;i<m;i++){
			cin >> x;
			n-=x;
		}
		if(n<0){
			cout << -1;
		}else{
			cout << n;

		}
	
		
		return 0;
	}

Measured memory_bytes: 3632
import sys
input = sys.stdin.readline
N, x  = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
ans = 0
for i in range(N):
    if a[i] > x:
        ans += a[i] - x
        a[i] = x
for j in range(1, N):
    if a[j] + a[j-1] > x:
        ans += a[j] + a[j-1] - x
        a[j] -= a[j] + a[j-1] - x
print(ans)

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

typedef long long ll;
const int mod=19260817;
const int p=423;

char s[200005];
ll h[200005];
ll pw[200005];
int n;
int l;
ll pr;
int cnt;

ll gh(int cl,int cr){
    return (h[cr]-h[cl-1]*pw[cr-cl+1]%mod+mod)%mod;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>s+1;
    n=strlen(s+1);
    pw[0]=1;
    for(int i=1;i<=n;i++){
        pw[i]=pw[i-1]*p%mod;
        h[i]=(h[i-1]*p+s[i]-'a'+1)%mod;
    }
    l=1;
    pr=-1;
    for(int i=1;i<=n;i++){
        if(gh(l,i)!=pr){//cout<<i<<endl;
            cnt++;
            pr=gh(l,i);
            l=i+1;
        }
    }
    cout<<cnt<<endl;

    return 0;
}

Measured memory_bytes: 4096
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define reps(i,n) for(int i=1;i<(int)(n);i++)

typedef long long ll;
using namespace std;

int gcd(int a, int b) { //最大公約数
  if (b==0) return a;
  else return gcd(b, a%b);
}

int lcm(int a, int b) { //最小公倍数
  return a * b / gcd(a, b);
}


int main()
{
  string s;
  cin>>s;
  ll ans=0;
  rep(i,s.length()){
    ans+=s[i]-'0';
  }

  if(atoi(s.c_str())%ans==0){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
  return 0;
}


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

int main() {
int X,Y;
  cin >> X >> Y;
  if (Y % 2 == 1){
    cout << "No";
  }
  else if (2 * X <= Y && Y <= 4 * X ){
    cout << "Yes";
  }
  else{
    cout << "No";
  }
}

Measured memory_bytes: 3636
n=int(input())
M=['M','A','R','C','H']
S = {'M':0,'A':0,'R':0,'C':0,'H':0}
for _ in range(n):
  a = input()
  if a[0] in S:
  	S[a[0]] +=1
ANS=0
for i in range(len(M)):
  for j in range(i+1,len(M)):
    for k in range(j+1,len(M)):
      ANS += (S[M[i]] * S[M[j]]* S[M[k]])
print(ANS)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int n, k;
const int MAXN = 1e5 + 5;
int vis[MAXN];
vector < int > arr;
int main(){
    cin >> n >> k;
    arr.resize(n);
    for(int i = 0; i < n; i++) cin >> arr[i];
    for(int i = 0; i <= k; i++)
        for(auto val : arr)
            if(i - val >= 0 && !vis[i - val])
                vis[i] = true;
    puts(vis[k] ? "First\n" : "Second\n");
}


Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int b=100;
    int sum=0;
    for(int i=0;i<n;i++){
      	sum=0;
        int a;
        cin>>a;
        for(int j=0;j<100;j++){
            if(a%2==0){
                sum++;
                a=a/2;
            }
            else{
                break;
            }
        }
        if(b>sum){
            b=sum;
        }
    }
    cout<<b<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define printYes() cout << "Yes" << endl;
#define printNo() cout << "No" << endl;
#define printVector(v) rep(i, v.size()) cout << v[i] << endl;

int main()
{
  int N;
  cin >> N;
  vector<int> A(N);
  rep(i, N)
  {
    cin >> A[i];
  }
  sort(A.begin(), A.end());
  string ans = "YES";
  rep(i, N - 1)
  {
    if (A[i] == A[i + 1])
      ans = "NO";
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
import sys
from bisect import bisect_left,bisect_right

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

N = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
for b in range(N):
    for a in range(b):
        ab = L[a] + L[b]
        r = bisect_left(L, ab)
        l = b + 1
        ans += max(0, r - l)

print(ans)


Measured memory_bytes: 74244
#include "bits/stdc++.h"

#define ll          long long
#define pb          push_back
#define pii         pair<ll int,ll int>
#define vpii        vector< pii >
#define vi          vector<ll int>
#define vs			vector< string >
#define vvi         vector< vector< ll > >
#define inf			1'010'000'000'000'000'017LL
#define all(it,a)   for(auto it=(a).begin();it!=(a).end();it++) 
#define sz(x)       (ll int)x.size()
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define repr(i,a,b) for(ll int i=a;i>b;i--)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define mp          make_pair
#define whatis(x)   cout << #x << " is " << x << "\n";
#define graph(n)    adj(n,vector< ll > () )

using namespace std;

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


void Main()
{
	ll N;
	cin >> N;
	vi A(N, 0);
	rep(i, 0, N) cin >> A[i];

	sort(A.begin(), A.end());
	A.push_back(0);

	ll ans = 0;
	vector<bool> dp(A[N - 1] + 1, false);
	rep(i, 0, N) {
		if (dp[A[i]]) continue;
		if (A[i] != A[i + 1]) ans++;
		for (ll k = A[i]; k < dp.size(); k += A[i])
		{
			dp[k] = true;
		}
	}
	cout << ans << endl;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);

	Main();
	return 0;
}

Measured memory_bytes: 6248
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())  #空白あり

N = I()
xyh = [tuple(MI()) for i in range(N)]

for i in range(101):  # ピラミッドの中心座標のx座標
    for j in range(101):  # ピラミッドの中心座標のy座標
        for k in range(N):
            x,y,h = xyh[k]
            if h != 0:
                H = h + abs(x-i) + abs(y-j)
                break
        for k in range(N):
            x,y,h = xyh[k]
            if h != max(H - abs(x-i) - abs(y-j),0):
                break
        else:
            print(i,j,H)
            exit()


Measured memory_bytes: 74100
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>

#define max 200000

//qsort(str, n, sizeof(int), up_comp);
int up_comp(const void *a, const void *b){return *(int*)a - *(int*)b;}
int down_comp(const void *a, const void *b){return *(int*)b - *(int*)a;}
int count_digit(int a){int i=0;while(a!=0){a=a/10;i++;}return i;}
int euclid( int a, int b ){int temp;if(a<b){temp=a;a=b;b=temp;}if(b<1)return -1;if(a%b==0) return b;return euclid(b,a%b);}

int main()
{
    long long int i, j, n, time, tmp=LLONG_MAX, h;
    //double h;
    
    scanf("%lld", &n);
    
    h=sqrt(n);
    
    for (i=h; i>0; i--) {
        if (n%i==0) {
            j=n/i;
            time=i+j-2;
            if (time<tmp) {
                tmp=time;
            }
        }
    }
    
    printf("%lld", tmp);
    
    return 0;
}



Measured memory_bytes: 128
import sys
input=sys.stdin.readline
H,W,D=map(int,input().split())
cost=[[0 for _ in range((H*W)//D+1)] for i in range(D)]
L=[0]*(H*W)
for i in range(H):
  L1=list(map(int,input().split()))
  for j in range(W):
    L[L1[j]-1]=[i,j]
    if L1[j]%D!=0:
      cost[L1[j]%D][L1[j]//D]=[i,j,0]
    else:
      cost[L1[j]%D][(L1[j]//D)-1]=[i,j,0]
for i in range(D):
  for j in range(1,len(cost[i])):
    if cost[i][j]!=0:
      cost[i][j][2]=cost[i][j-1][2]+abs(cost[i][j][0]-cost[i][j-1][0])+abs(cost[i][j][1]-cost[i][j-1][1])
Q=int(input())
for i in range(Q):
  A,B=map(int,input().split())
  c=A%D
  a=A//D
  b=B//D
  if c==0:
    a,b=a-1,b-1
  print(cost[c][b][2]-cost[c][a][2])

Measured memory_bytes: 35428
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep2(i, m, n) for(int i=int(m); i<int(n); ++i)
#define drep2(i, m, n) for(int i=int(m-1); i>=int(n); --i)
#define rep(i, n) rep2(i, 0, n)
#define drep(i, n) drep2(i, n, 0)
#define all(a) a.begin(), a.end()
#define fst first
#define snd second
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
template<typename T> inline bool chmin(T& a, T b) {if(a>b) {a=b; return true;} return false;}
template<typename T> inline bool chmax(T& a, T b) {if(a<b) {a=b; return true;} return false;}
inline int Log2(ll x) {int k; for(k=0; x>0; ++k) x>>=1; return k;} // number of binary digits
template<typename T> inline int count_between(vector<T>& a, T l, T r) {
  return lower_bound(all(a), r) - lower_bound(all(a), l); // [l, r)
}
template<typename T> istream& operator>>(istream& is, vector<T>& v) {
  rep(i, v.size()) is >> v[i]; return is;
}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
  rep(i, v.size()) os << v[i] << " "; os << endl; return os;
}
const int INF  = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS   = 1e-10;
const int MOD  = int(1e9)+7;


int main() {
  ll q; cin >> q;

  priority_queue<int> l;
  priority_queue<int, V, greater<int>> r;

  ll sb = 0, sl = 0, sr = 0;

  rep(i, q) {
    int t; cin >> t;
    if (t == 2) {
      ll ans = (sr-sl)/2 + sb;
      printf("%d %lld\n", l.top(), ans);
      // cout << l.top() << " " << ans << endl;
    }
    else {
      int a, b; cin >> a >> b;
      l.push(a);
      r.push(a);
      sl += a;
      sr += a;

      int lt = l.top();
      int rt = r.top();
      if (lt > rt) {
        l.pop();
        r.pop();
        l.push(rt);
        r.push(lt);
        sl += rt - lt;
        sr += lt - rt;
      }
      sb += b;
    }
  }
  return 0;
}


Measured memory_bytes: 3828
#!/usr/bin/env python3
import sys
import itertools
INF = float("inf")


def solve(N: int, M: int, xyz):
    ans = []
    # 正負のパターンが8つ。
    for p1, p2, p3 in itertools.product([-1, 1], repeat=3):
        # 全部正が良い
        m = -INF

        def f(x): return x[0]*p1+x[1]*p2+x[2]*p3

        xyz.sort(key=f, reverse=True)
        ans.append(sum([f(x) for x in xyz[:M]]))

    print(max(ans))
    return


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
    M = int(next(tokens))  # type: int
    xyz = [[]] * (N)  # type: "List[int]"
    for i in range(N):
        xyz[i] = [int(next(tokens)), int(next(tokens)), int(next(tokens))]
    solve(N, M, xyz)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3308
from fractions import gcd

N, X = map(int, input().split())
x = map(int, input().split())

if N == 1:
    ans = abs(X-next(x))
else:
    ans = gcd(abs(X-next(x)), abs(X-next(x)))
    for i in x:
        ans = gcd(ans, abs(X-i))
print(ans)


Measured memory_bytes: 13080
#include <bits/stdc++.h>
using namespace std;
#define iinf 2000000000
#define linf 1000000000000000000LL
#define ulinf 10000000000000000000ull
#define MOD1 1000000007LL
#define mpr make_pair
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned long UL;
typedef unsigned short US;
typedef pair < int , int > pii;
clock_t __stt;
inline void TStart(){__stt=clock();}
inline void TReport(){printf("\nTaken Time : %.3lf sec\n",(double)(clock()-__stt)/CLOCKS_PER_SEC);}
template < typename T > T MIN(T a,T b){return a<b?a:b;}
template < typename T > T MAX(T a,T b){return a>b?a:b;}
template < typename T > T ABS(T a){return a>0?a:(-a);}
template < typename T > void UMIN(T &a,T b){if(b<a) a=b;}
template < typename T > void UMAX(T &a,T b){if(b>a) a=b;}
char s[200005];
int n;
int main(){
    // inputting start
    // 数据结构记得初始化！ n，m别写反！
    int i,j,k;
	scanf("%s",s);
	n=strlen(s);
    #ifdef LOCAL
        TStart();
    #endif
    // calculation start
    // 数据结构记得初始化！ n，m别写反！
    LL res=0ll;
	int pos=n-1;
	for(i=n-1;i>=0;--i){
		if(s[i]=='B'){
			res+=(LL)(pos-i);
			--pos;
		}
	}
	printf("%lld\n",res);
    #ifdef LOCAL
        TReport();
    #endif
    return 0;
}

Measured memory_bytes: 384
#include<stdio.h>
#define N 44
int fibonach(int );

int main()
{
  int fn,n;

  scanf("%d",&n);

  fn = fibonach(n);

  printf("%d\n",fn);
  
  return 0;
}


int fibonach(int n)
{
  int i,a[N];

  for(i=0;i<=n;i++)
    {
      if(i == 0) a[i] = 1;
      else if(i == 1) a[i] = 1;
      else a[i] = a[i-2] + a[i-1];
    }

  return a[i-1];
}



Measured memory_bytes: 2104
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=40005;
int n;
double a[N],b[N],c[N];
struct node{
	double k,b;
	bool operator <(const node &pr)const{
		if(k*pr.k<0)return k<=0;
		return k>=pr.k;
	}
}e[N];
struct sub{
	double x;int id;
	bool operator <(const sub &pr)const{return x<pr.x;}
}w[N];
int tr[N];
inline void add(int sta,int t){
	for(int i=sta;i<=n;i+=(i&(-i)))tr[i]+=t;
}
inline int qry(int sta){
	int ret=0;
	for(int i=sta;i>=1;i-=(i&(-i)))ret+=tr[i];
	return ret;
}
inline double solve(){
	sort(e+1,e+n+1);
	double l=-1e12,r=1e12,mid;
	int lim=(n*(n-1)/2+1)/2,cnt=0;
	while(l<r){
		cnt++;if(cnt==100)break;
		mid=(l+r)/2;
		for(int i=1;i<=n;i++)w[i]=(sub){(mid-e[i].b)/e[i].k,i};
		sort(w+1,w+n+1);
		int sum=0;
		for(int i=1;i<=n;i++){
			sum+=qry(w[i].id);
			add(w[i].id,1);
		}
		for(int i=1;i<=n;i++)add(w[i].id,-1);
		if(sum<lim)l=mid;
		else r=mid;
	}
	return l;
}
void work()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lf%lf%lf",&a[i],&b[i],&c[i]);
		c[i]=-c[i];
	}
	for(int i=1;i<=n;i++){
		e[i].k=-a[i]/b[i];
		e[i].b=-c[i]/b[i];
	}
	double y=solve();
	for(int i=1;i<=n;i++){
		e[i].k=-b[i]/a[i];
		e[i].b=-c[i]/a[i];
	}
	double x=solve();
	printf("%.10lf %.10lf\n",x,y);
}

int main()
{
	work();
	return 0;
}


Measured memory_bytes: 2816
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        Main m = new Main(sc);
        m.show(m.solve());
        sc.close();
    }
    
	//フィールド
    Scanner sc;
    int A;
    int B;
    
    //入力
    Main(Scanner sc) {
        this.sc = sc;
        this.A = sc.nextInt();
        this.B = sc.nextInt();
    }
    
    //解答処理
    private String solve() {
        String answer = null;
        
        if (A != 1 && B != 1) {
        	if (A > B) {
        		answer = "Alice";
        	} else if (A < B) {
        		answer = "Bob";
        	} else {
        		answer = "Draw";
        	}
        } else if (A == 1 && B != 1) {
        	answer = "Alice";
        } else if (A != 1 && B == 1) {
        	answer = "Bob";
        } else {
        	answer = "Draw";
        }
        
        return answer;
    }
    
    //出力
    public void show(String answer) {
        System.out.println(answer);
    }

}


Measured memory_bytes: 35676
//Code by: Nikhil Shukla, MMMUT GKP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define V vector
#define pb push_back
#define all x x.begin(),x.end()
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL);
#define tc ll t; cin>>t; while(t--)
#define tc1 ll tt=1; while(tt--)
#define fir first
#define sec second
#define mod 1000000007
#define out1(x) cout<<x<<"\n";
#define out2(x,y) cout<<x<<" "<<y<<"\n";
#define debug() cout<<"I am in\n";
#define Vll vector<long long>
#define FOR(i,x,n) for(ll i=x;i<n;i++)
#define RFOR(i,x,n) for(ll i=x;i>=n;i--)
////////////////////////////////////////////////////////////////////////////////////////
/*vector<ll>graph[100001];
vector<ll>temp;
vector<bool>visited(100001,false);
//long long count=0;
void dfs(long long node,ll dp[])
{
        visited[node]=1;
        for(ll i=0;i<graph[node].size();i++)
        {
            if(!visited[graph[node][i]])
            dfs(graph[node][i],dp);
            dp[node]=max(dp[node],1+dp[graph[node][i]]);
        }
}*/


void solve(double p[],ll n)
{
    ll i,j;
    double ans=0;
    double dp[n+1][n+1];
    for(i=0;i<=n;i++)
    {
        dp[0][i]=0;
    }
    dp[0][0]=1;
    for(i=1;i<=n;i++)
    {
        for(j=0;j<=n;j++)
        {
            if(j==0)
            dp[i][j]=(1.0-p[i-1])*dp[i-1][j];
            else
            dp[i][j]=p[i-1]*dp[i-1][j-1]+(1.0-p[i-1])*dp[i-1][j];
        }
    }
    for(ll heads=0;heads<=n;heads++)
    {
        ll tails=n-heads;
        if(heads>tails)
        {
            ans+=dp[n][heads];
        }
    }
    printf("%.9f",ans);
}
int main()
{
    fast()
    tc1
    {
        ll n;
        cin>>n;
        double p[n];
        FOR(i,0,n)
        cin>>p[i];
        solve(p,n);
    }
    
    return 0;
}


Measured memory_bytes: 74136
#B
from operator import itemgetter
N = int(input())
L = []
for i in range(N):
    n = i + 1
    s, p = input().split()
    s = str(s)
    p = int(p)
    tmp = (s,p,n)
    L.append(tmp)
ls = sorted(L, key = itemgetter(1), reverse = True)
ls = sorted(ls, key = itemgetter(0))
for itm in ls:
    print(itm[2])


Measured memory_bytes: 3064
#pragma once
#include <stdio.h>
#include <sstream>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <limits>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define bit(x,v) ((ll)x << v)

const ll INF = 1000000007;
const ll MAX = 210000;
const ll MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int pr[100010];
void uini(int n) {
	for (size_t i = 0; i <= n; i++)
	{
		pr[i] = i;
	}
}

int parent(int x) {
	if (x == pr[x]) return x;
	return pr[x] = parent(pr[x]);
}

bool unit(int x, int y) {
	int px = parent(x);
	int py = parent(y);

	if (px == py) return false;
	if (px < py) {
		pr[py] = px;
	}
	else {
		pr[px] = py;
	}
	return true;
}

// res[i][c] := i 文字目以降で最初に文字 c が登場する index (存在しないときは n)
vector<vector<int> > calcNext(const string & S) {
	int n = (int)S.size();
	vector<vector<int> > res(n + 1, vector<int>(26, n));
	for (int i = n - 1; i >= 0; --i) {
		for (int j = 0; j < 26; ++j) res[i][j] = res[i + 1][j];
		res[i][S[i] - 'a'] = i;
	}
	return res;
}
// mod 1000000007 の世界で a += b する関数
void add(long long& a, long long b) {
	a += b;
	if (a >= MOD) a -= MOD;
}
const ll ainf = 998244353;
string calc(string v, char in) {
	string res = v + in;
	sort(res.begin(), res.end(),greater<char>());
	return res;
}

void solv() {
	int n,m;
	cin >> n >> m;
	int a[10];

	for (size_t i = 0; i < m; i++)
	{
		cin >> a[i];
	}

	int ta[] = {0, 2,5,5,4,5,6,3,7,6 };
	string dp[10010];
	for (size_t i = 0; i <= 10000; i++)
	{
		dp[i] = "x";
	}
	dp[0] = "";
	for (size_t i = 0; i < m; i++)
	{
		int num = ta[a[i]];
		char v = a[i] + '0';
		for (int j = 0; j <= 10000; j++)
		{
			if (j - num >= 0 && dp[j - num] != "x") {
				if (dp[j] == "x") dp[j] = "";
				if (dp[j].size() > dp[j - num].size() + 1) continue;
				string val = calc(dp[j - num], v);
				int si1 = val.size();
				int si2 = dp[j].size();
				if (si1 > si2)
					dp[j] = val;
				else if (si1 == si2 && val > dp[j])	
				{
					dp[j] = val;
				}
			}
		}
	}
	cout << dp[n] << endl;
}

int main() {
	//COMinit();
	solv();

	return 0;
}


Measured memory_bytes: 27008
package main

import (
	"fmt"
	"strconv"
)

func main() {
	var N int
	fmt.Scanf("%d\n", &N)
	r := [10][10]int{}
	for i := 1; i <= N; i++ {
		sn := []rune(fmt.Sprint(i))
		a, _ := strconv.Atoi(string(sn[0]))
		b, _ := strconv.Atoi(string(sn[len(sn)-1]))
		r[a][b]++
	}
	ans := 0
	for i := 1; i <= 9; i++ {
		for j := 1; j <= 9; j++ {
			ans = ans + r[i][j]*r[j][i]
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 5504
#coding:utf-8
#1_2_C

def BubbleSort(cards, n):
    for i in range(n):
        for j in range(n-1, i, -1):
            if cards[j][1] < cards[j-1][1]:
                cards[j], cards[j-1] = cards[j-1], cards[j]
    return cards

def SelectionSort(cards, n):
    for i in range(n):
        minj = i
        for j in range(i, n):
            if cards[minj][1] > cards[j][1]:
                minj = j
        cards[i], cards[minj] = cards[minj], cards[i]
    return cards

n = int(input())
cardsR = input().split()
cardsS = cardsR[:]

print(' '.join(BubbleSort(cardsR, n)))
print("Stable")
print(*SelectionSort(cardsS, n))
print("Stable" if cardsR == cardsS else "Not stable")

Measured memory_bytes: 6740