akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

int main(){
	int a,b,min1,min2,max1,max2;
	cin>>a>>b;
  	min1=(a*25+1)/2;
  	max1=(25*a+24)/2;
  	min2=10*b;
  	max2=10*b+9;
  	if(min1<=max2){
    	if(min2<=max1){
        	cout<<max(min1,min2);
          	return 0;
        } else {
        	cout<<"-1";
          	return 0;
        }
    } else {
    	cout<<"-1";
      	return 0;
    }
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val nStr = readLine() ?: ""
    val n = nStr.toInt()
    val sumDigit = nStr.fold(0, {acc, c -> acc + c.toString().toInt()})
    val res = if (n % sumDigit == 0) "Yes" else "No"
    println(res)
}

Measured memory_bytes: 33780
#include<stdio.h>
#include<string.h>
#include<utility>
#include<iostream>
#include<queue>
#include<math.h>

using namespace std;
typedef long long ll;
 
#define REP(i,n) for(int i=0;i<(int)(n);i++)
 
int main()
{
    int prime[250000]={};
    long int rui[250000]={};
    REP(i,250000)prime[i]=1;
    prime[0]=0;
    prime[1]=0;
    for(int i=2;i<501;i++)
    {
        if(prime[i]==1)
        {
            for(int j=i*2;j<250000;j+=i)prime[j]=0;
        }
    }
    for(int i=1;i<250000;i++)
    {
        rui[i]=rui[i-1]+prime[i];
    }
    long int n;
    while(1==1)
    {
        scanf("%ld\n",&n);
        if(n==0)return 0;
        printf("%ld\n",rui[n*2]-rui[n]);
    }
    return 0;
}


Measured memory_bytes: 6156
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
    R int res,f=1;R char ch;
    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
    return res*f;
}
const int N=205,M=1e5+5,P=1e9+7;
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R int y){
	R int res=1;
	for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;
	return res;
}
int inv[N],p[N][M],a[N],id[N];
int n,x,fac,res;
int main(){
//	freopen("testdata.in","r",stdin);
	n=read(),x=read(),fac=1;
	fp(i,1,n)a[i]=read(),fac=mul(fac,i);
	sort(a+1,a+1+n);
	inv[0]=inv[1]=1;fp(i,2,n)inv[i]=mul(P-P/i,inv[P%i]);
	p[n+1][x]=1;
	fd(i,n,1)fp(j,0,x)
		p[i][j%a[i]]=add(p[i][j%a[i]],mul(p[i+1][j],inv[i])),
		p[i][j]=add(p[i][j],mul(p[i+1][j],P+1-inv[i]));
	fp(i,1,x-1)res=add(res,mul(p[1][i],i));
	printf("%d\n",mul(res,fac));
	return 0;
}

Measured memory_bytes: 81792
#include<stdio.h>

int main(){
int i=0;
  int numsize;
  scanf("%d",&numsize);
  int num[numsize];
  for(i=0;i<numsize;i++)scanf("%d,",&num[i]);

  int sum=0;

  for(i=0;i<numsize;i++)sum+=num[i]-1;

  printf("%d",sum);

  return 0;
}


Measured memory_bytes: 256
while line = gets do
  a, b, c, d, e, f = line.split.map(&:to_f)
  matrix = [[a, b], [d, e]]
  m2 = [[c], [f]]
  inv = [[matrix[1][1], matrix[0][1] * -1], [matrix[1][0] * -1, matrix[0][0]]]
  c = matrix[0][0] * matrix[1][1] - matrix[1][0] * matrix[0][1]
  2.times do |i|
    2.times do |j|
      inv[i][j] /= c
    end
  end

  x = inv[0][0] * m2[0][0] + inv[0][1] * m2[1][0]
  y = inv[1][0] * m2[0][0] + inv[1][1] * m2[1][0]
  puts "#{sprintf("%.3f", x)} #{sprintf("%.3f", y)}"
end

Measured memory_bytes: 8692
#include<iostream>
using namespace std;
int main()
{
	int n;
	cin >> n;
	int x = 0;
	if (n % 2 == 0){
		x = (n / 2) * (n / 2);
	}
	else if (n % 2 == 1){
		x = (n / 2) * ((n / 2) + 1);
	}
	cout << x << endl;
	return 0;
}

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

m=0;a=0;r=0;c=0;h=0

for i in range(n):
  s=input()
  if s[0]=='M':
    m+=1
  elif s[0]=='A':
    a+=1
  elif s[0]=='R':
    r+=1      
  elif s[0]=='C':
    c+=1      
  elif s[0]=='H':
    h+=1

#print(m,a,r,c,h)
ans=0
ans+=m*a*r
ans+=m*a*c
ans+=m*a*h
ans+=m*r*c
ans+=m*r*h
ans+=m*c*h
ans+=a*r*c
ans+=a*r*h
ans+=a*c*h
ans+=r*c*h

print(ans)



Measured memory_bytes: 3064
def main():
    N = int(input())
    h = list(map(int, input().split()))
    dp = [0] * N
    dp[1] = abs(h[0] - h[1])
    for i in range(2, N):
        dp[i] = min(
            abs(h[i] - h[i - 2]) + dp[i - 2],
            abs(h[i] - h[i - 1]) + dp[i - 1]
        )
    print(dp[-1])


main()


Measured memory_bytes: 13928
h,w=map(int,input().split())
s=[[+(i=='#')for i in input()]for j in range(h)]
c=[1000]*w*h
c[0]=s[0][0]
for i in range(h):
  for j in range(w):
    for k,l in [[i-1,j],[i,j-1]]:
      if k<0 or l<0:continue
      c[i*w+j]=min(c[i*w+j],c[k*w+l]+(s[k][l]==0)*(s[i][j]==1))
print(c[-1])

Measured memory_bytes: 3188
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<iomanip>
#include <math.h>
using namespace std;

int main(){
    long long int n,a=7,ans=-1;
    cin>>n;
for(long long int i=0;i<=n;i++){
        if(a%n==0){
            ans=i+1;
            break;
        }
        else{
            a=(a*10+7)%n;
        }
    }
    cout<<ans<<endl;
    return 0;
}


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

#define int long long
#define INF 9223372036854775807
#define M_PI 3.14159265358979323846
#define double long double

int mod = INF;

int fastPow(int b, int e){int r = 1;while(e){if(e%2 == 1){r*=b;r%=mod;}b*=b;b%=mod;e/=2;}return r;}
int pgcd(int a, int b){ if(a%b == 0) return b; else return pgcd(b, a%b);}
int sign(int a){if(a < 0){ return -1;}if(a == 0) {return 0;}if(a > 0) {return 1;}}
bool isPrime(int a){if(a == 1) {return false;}int f = sqrt(a);for(int i = 2; i<=f; i++){if(a%i == 0){return false;}}return true;}
int toInt(string s){int tot = 0;for(int i = s.size()-1; i >= 0; i--){tot+=((s[i]-'0')%mod)*fastPow(10,i);tot%=mod;}return tot;}
string toString(int a){string s = "";while(a){s = (char)('0'+a%10) + s;a/=10;}return s;}

int memo[3009][3009];

string s, t;

int dp(int a, int b){
    if(a <= -1 || b <= -1) return 0;
    if(memo[a][b] != -1) return memo[a][b];
    if(s[a] == t[b]){
        return memo[a][b] = dp(a-1,b-1)+1;
    }else{
        return memo[a][b] = max(dp(a-1,b),dp(a,b-1));
    }
}

void rec(int a, int b){
    if(a <= -1 || b <= -1) return;
    if(s[a] == t[b]){
        rec(a-1,b-1);
        cout << s[a];
        return;
    }else if(memo[a][b] == dp(a-1,b)){
        rec(a-1,b);
    }else{
        rec(a,b-1);
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    cin >> t;
    for(int i = 0; i < 3009; i++){
        for(int j = 0; j < 3009; j++){
            memo[i][j] = -1;
        }
    }
    dp(s.size()-1, t.size()-1);
    rec(s.size()-1, t.size()-1);
    cout << endl;
}


Measured memory_bytes: 71296
package main 

import (
	"fmt"
	)

func sort(a int, b int, c int) (int,int,int) {
	// 小さい順に並べる
	if b > c {
		b,c = c,b
	}
	if a > b {
		a,b = b,a
	}
	if b > c {
		b,c = c,b
	}
	return a,b,c
}

func scan() (a int, b int, c int) {
	fmt.Scan(&a, &b, &c)
	return
}

func main() {
	var a,b,c, x,y,z int
	a,b,c = sort(scan())


	if a % 2 == 0 {
		x = a/2
		y = b
		z = c
		a /= 2
	} else if b % 2 == 0 {
		x = a
		y = b/2
		z = c
		b /= 2
	} else if c % 2 == 0 {
		x = a
		y = b
		z = c/2
		c /= 2
	} else {
		if c > 1 {
			x = a
			y = b
			z = (c+1)/2
			c -= z
		} else if b > 1 {
			x = a
			y = (b+1)/2
			z = c
			b -= y
		} else if a > 1 {
			x = (a+1)/2
			y = b
			z = c
			a -= x
		} else {
			fmt.Println("Error")
		}
	}
	fmt.Println(x*y*z - a*b*c)
}


Measured memory_bytes: 512
#include<iostream>
using namespace std;
#include<string>
#include<stdio.h>

#define A 1355471101  // large prime number 1.
#define B 1466700101  // large prime number 2.
#define M 1522101101  // large prime number 3, larger than A and B.

int main()
{
    int i, j, H, W, R, C;
    string *T;

    scanf("%d %d", &H, &W);
    T = new string [H];
    for(i = 0; i < H; i++){ cin >> T[i]; }
    scanf("%d %d", &R, &C);

    long long hash[1000][1000];
    long long s;

    char P[1000];
    for(i = 0; i < R; i++){
        s = 0;
        scanf("%s", P);
        for(j = 0; j < C; j++){
            s = (s * B + P[j]) % M;
            hash[i][j] = s;
        }
    }
    for(j = 0; j < C; j++){
        s = 0;
        for(i = 0; i < R; i++){
            s = (s * A + hash[i][j]) % M;
            hash[i][j] = s;
        }
    }
    long long last_has = hash[R - 1][C - 1];

    for(i = 0; i < H; i++){
        s = 0;
        for(j = 0; j < W; j++){
            s = (s * B + T[i][j]) % M;
            hash[i][j] = s;
        }
    }
    for(j = 0; j < W; j++){
        s = 0;
        for(i = 0; i < H; i++){
            s = (s * A + hash[i][j]) % M;
            hash[i][j] = s;
        }
    }

    long long power_a, power_b, power_c, x, y, z;
    x = A, y = R, z = 1;
    for( ; y; y >>= 1){ if((y & 1) != 0){ z = (z * x) % M; } x = (x * x) % M; }
    power_a = z;
    x = B, y = C, z = 1;
    for( ; y; y >>= 1){ if((y & 1) != 0){ z = (z * x) % M; } x = (x * x) % M; }
    power_b = z;
    power_c = (power_a * power_b) % M;

    long long block1, block2, block3;
    for(i = R - 1; i < H; i++){
        for(j = C - 1; j < W; j++){
            block1 = ((i >= R ? hash[i - R][j] : 0) * power_a) % M;
            block2 = ((j >= C ? hash[i][j - C] : 0) * power_b) % M;
            block3 = M - ((((i >= R && j >= C) ? hash[i - R][j - C] : 0) * power_c) % M);
            if(hash[i][j] == (block1 + block2 + block3 + last_has) % M){
            printf("%d %d\n", i - R + 1, j - C + 1);
            }
        }
    }
	delete [] T;
    return 0;
}

Measured memory_bytes: 10096
#include<stdio.h>
#include<ctype.h>
#include<string.h>
int main(){
int count=0,j,n;
char moji[11];
char text[50];
scanf("%s",moji);
while(1){
 scanf("%s",text);
 if(strcmp(text,"END_OF_TEXT")==0) break;
 n=strlen(text);
  for(j=0;j<n;j++){
   text[j]=tolower(text[j]);
 }
 if(strcmp(moji,text)==0) count++;
}
printf("%d\n",count);
return 0;
}


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

typedef long long LL;

#define FOR(i, a, b) for (int i = (a), i##_END_ = (b); i <= i##_END_; i++)
#define DNF(i, a, b) for (int i = (a), i##_END_ = (b); i >= i##_END_; i--)

template <typename Tp> void in(Tp &x) {
	char ch = getchar(), f = 1; x = 0;
	while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
	if (ch == '-') ch = getchar(), f = -1;
	while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	x *= f;
}

template <typename Tp> void out(Tp x) {
	if (x > 9) out(x / 10);
	putchar(x % 10 + '0');
	return;
}

template <typename Tp> Tp Max(const Tp &x, const Tp &y) {return x > y ? x : y;}
template <typename Tp> Tp Min(const Tp &x, const Tp &y) {return x < y ? x : y;}
template <typename Tp> bool chkmax(Tp &x, Tp y) {return x >= y ? 0 : (x=y, 1);}
template <typename Tp> bool chkmin(Tp &x, Tp y) {return x <= y ? 0 : (x=y, 1);}

const int MAXN = 200010;

int n;
int A[MAXN];
LL sum[MAXN];
LL p[MAXN];

LL calc(int l1, int r1, int l2, int r2, int l3, int r3, int l4, int r4)
{
	p[1] = sum[r1] - sum[l1 - 1];
	p[2] = sum[r2] - sum[l2 - 1];
	p[3] = sum[r3] - sum[l3 - 1];
	p[4] = sum[r4] - sum[l4 - 1];
	std::sort(p + 1, p + 5);
	return p[4] - p[1];
}

int main()
{
	in(n);
	FOR(i, 1, n) in(A[i]);
	FOR(i, 1, n) sum[i] = sum[i - 1] + A[i];

	LL ans = 0x3f3f3f3f3f3f3f3fLL;
	
	FOR(i, 2, n - 2) {
		int L = 1, R = i - 1, pos = 1;
		while (L <= R) {
			int mid = (L + R) >> 1;
			if (sum[mid] <= sum[i] - sum[mid]) pos = mid, L = mid + 1;
			else R = mid - 1;
		}
		L = i + 1, R = n; int pos2 = i + 1;
		while (L <= R) {
			int mid = (L + R) >> 1;
			if (sum[mid] - sum[i] <= sum[n] - sum[mid]) pos2 = mid, L = mid + 1;
			else R = mid - 1;
		}
		
		chkmin(ans, calc(1, pos, pos + 1, i, i + 1, pos2, pos2 + 1, n));
		if (pos < i - 1) chkmin(ans, calc(1, pos + 1, pos + 2, i, i + 1, pos2, pos2 + 1, n));
		if (pos2 < n - 1) chkmin(ans, calc(1, pos, pos + 1, i, i + 1, pos2 + 1, pos2 + 2, n));
		if (pos < i - 1 && pos2 < n - 1)
			chkmin(ans, calc(1, pos + 1, pos + 2, i, i + 1, pos2 + 1, pos2 + 2, n));
	}

	printf("%lld\n", ans);
	
	return 0;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define ll long long
#define read(x) scanf("%d",&x);
#define readll(x) cin>>x;
#define FOR(x,a,b) for(int x=a;x<b;x++)
#define MP make_pair
#define PB push_back
#define pii pair<int,int>
#define readN(N,X) for(int i=0;i<N;i++) cin>>X[i];
#define pff pair<double,double>
using namespace std;

long long fastpow(int a, int b, int MOD)
{
    long long x=1,y=a; 
    while(b > 0)
    {
        if(b%2 == 1)
        {
            x=(x*y) % MOD;
        }
        y = (y*y) % MOD;
        b /= 2;
    }
    return x;
}

long long InverseEuler(int n, int MOD)
{
    return fastpow(n,MOD-2,MOD);
}
 
long long f[300000];
bool init;
long long C(int n, int r, int MOD)
{
    if (!init){
        init=1;
        f[0]=1;
        for (int i=1; i<300000;i++)
            f[i]= (f[i-1]*i) % MOD;
        
    }
    return (f[n]*((InverseEuler(f[r], MOD) * InverseEuler(f[n-r], MOD)) % MOD)) % MOD;
}


int N;
int a[100005];
string S;
int main(){
   std::ios::sync_with_stdio(false); 
   cin>>S;
   N = S.length();
   for (int i=0;i<N - 8;i++) cout<<S[i];
    cout<<endl;

}

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

int main(){
	#ifndef ONLINE_JUDGE 

	// For getting input from input.txt file 
	freopen("/home/devanshi/AtCoderDPproblems/Frog2input.txt", "r", stdin); 

	// Printing the Output to output.txt file 
	freopen("/home/devanshi/AtCoderDPproblems/Frog2output.txt", "w", stdout); 

	#endif 

	int n,k;
	cin>>n>>k;
	int*h=new int[n];

	for(int i=0;i<n;i++){
		cin>>h[i];
	}
	
	int*dp=new int[n];
	dp[0]=0;
	dp[1]=abs(h[0]-h[1]);

	for(int i=2;i<n;i++){
		dp[i]=INT_MAX;
		for(int j=i-1;j>=i-k;j--){
			if(j<0){
				break;
			}
			dp[i]=min(dp[i],dp[j]+abs(h[i]-h[j]));
		}
	}

	cout<<dp[n-1]<<endl;
}

Measured memory_bytes: 4336
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
#include<functional>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;


int main()
{
	int N,Q;
	string S;
	cin>>N>>Q;
	cin>>S;
	vector<int>C(N,0);
	for(int i=1;i<N;i++)
	{
		if(S[i]=='C'&&S[i-1]=='A')
		{
			C[i]=C[i-1]+1;
		}
		else
		{
			C[i]=C[i-1];
		}
	}

	for(int i=0;i<Q;i++)
	{
		int l,r;
		cin>>l>>r;
		cout<<C[r-1]-C[l-1]<<endl;
	}
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;


using namespace std;

#define debug(x) cout << '>' << #x << ':' << x << endl;
#define loop(i,n) for(int i=0;i<(int)(n);i++)
#define foi(i,k,n) for(int i=(k); i<(int)(n); i+=1)
#define fod(i,n,k) for(int i=k; i>=(int)n; i-=1)
#define fast_io ios_base::sync_with_stdio(false) , cin.tie(NULL);
#define all(x) x.begin(), x.end()
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define endl "\n"

#define int long long
#define INF 0x3f3f3f3f
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007

#define fir first
#define sec second
#define pb push_back
#define mp make_pair

typedef long long llint;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<llint> VL;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef map<int,int> MII;
typedef set<int> SI;
string tostr(int n) {stringstream rr;rr<<n;return rr.str();}
llint toint(string s) {stringstream ss(s); llint x; ss >> x; return x;}
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
//gp_hash_table<string, llint> table;


//int mpow(llint base, llint exp) {
  //base %= MOD;
  //llint result = 1;
  //while (exp > 0) {
    //if (exp & 1) result = ((llint)result * base) % MOD;
    //base = ((llint)base * base) % MOD;
    //exp >>= 1;
  //}
  //return result;
//}


//void makegraph(int n, int m){
	//int i, u, v;
	//while(m--){
		//cin>>u>>v;
		//u--, v--;
		//g[u].pb(v);
		//g[v].pb(u);
	//}
//}

//void dfs(int u, int par){
	//for(int v:g[u]){
		//if (v == par) continue;
		//dfs(v, u);
	//}
//}


// ------------------------------------------------------------------ILB----------------------------------------------------------------  //

	//5 6 2 4 93 5 
	
	//0 93 6 6 5 5 5 5

void solve(){
	int n;
	cin >> n;
	VI v(n);
	
	loop(i, n) cin >> v[i];
	
	sort(all(v), greater<int>());
	int ans = 0;
	ans += v[0];
	
	int k = 1;
	
	loop(i, n - 2){
		//debug(k);
		ans += v[k];
		if(i % 2) k++;
	}
	
	cout << ans;
}




int32_t main() {
	fast_io;
    int t = 1;
    //cin >> t;
    //int xx = 0
    while(t--) {
		//xx++;
		//cout << "Case ";
      solve();
    }
    return 0;
}



Measured memory_bytes: 4776
N = int(input(""))
a = input("").split(" ")
a = [int(i) for i in a]
m = 1000
list_ = []

for j in range(0, N-1):
    if a[j] < a[j + 1]:
        n = m // a[j]
        k = (a[j + 1] - a[j]) * n
        m = m + k

print(m)

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

ll h, w, k;

vector<string> s;
vector<ll> acc[10][10];   // acc[i][j][x]   :  s[i..j][0..x-1] にある1の数
vector<ll> max_w[10][10]; // max_w[i][j][x] :  s[i..j][x..x+mw-1] の1の個数がk個以下であるmwのうち最も大きいもの
vector<pii> stk;

ll min_split = 10*1000+1;

// 垂直方向の分割を試す
void test(){
	int x = 0;
	ll hsplit = stk.size()-1;
	ll vsplit = -1;
	
	while ( x < w ){
		ll ww = w;
		for ( auto &it : stk ){
			ww = min(ww,max_w[it.first][it.second][x]);
		}
		if ( ww == 0 )
			return;
		x += ww;
		vsplit++;
	}
	
	//cout << "test ";
	//for ( auto it : stk )
	//	cout << it.first << "-" << it.second << ", ";
	//cout << hsplit << " " << vsplit << endl;
	
	min_split = min( min_split, hsplit+vsplit );
}

// 水平方向の直線で分割する方法をいろいろ試す
void dfs( int i, int j ){
	stk.push_back({i,j});
	if ( j == h-1 ){
		test();
	}
	else {
		for ( int k = j+1; k < h; k++ ){
			dfs(j+1, k);
		}
	}
	stk.pop_back();
}


int main(){
	cin >> h >> w >> k;
	
	s.resize(h);
	for ( int i = 0; i < h; i++ )
		cin >> s[i];
	
	// acc
	for ( int i = 0; i < h; i++ ){
		for ( int j = 0; j < h; j++ ){
			acc[i][j].resize(w+1);
			acc[i][j][0] = 0;
		}
	}
	for ( int i = 0; i < h; i++ ){
		ll sum = 0;
		for ( int x = 0; x < w; x++ ){
			sum += s[i][x]-'0';
			acc[i][i][x+1] = sum;
		}
	}
	for ( int i = 0; i < h; i++ ){
		for ( int j = i+1; j < h; j++ ){
			for ( int x = 0; x < w; x++ ){
				acc[i][j][x+1] = acc[i][j-1][x+1] + acc[j][j][x+1];
			}
		}
	}
	
	//for ( int i = 0; i < h; i++ ){
	//	for ( int j = i; j < h; j++ ){
	//		cout << i << "-" << j << " ";
	//		for ( size_t x = 0; x < acc[i][j].size(); x++ ){
	//			cout << acc[i][j][x] << " ";
	//		}
	//		cout << endl;
	//	}
	//}
	
	// max_w 
	for ( int i = 0; i < h; i++ ){
		for ( int j = i; j < h; j++ ){
			max_w[i][j].resize(w);
			int r = 0;
			vector<ll> &ac = acc[i][j];
			for ( int l = 0; l < w; l++ ){
				while ( r <= w && ac[r]-ac[l] <= k )
					r++;
				r--;
				max_w[i][j][l] = r - l;
			}
		}
	}
	//for ( int i = 0; i < h; i++ ){
	//	for ( int j = i; j < h; j++ ){
	//		cout << i << "-" << j << " ";
	//		for ( size_t x = 0; x < max_w[i][j].size(); x++ ){
	//			cout << max_w[i][j][x] << " ";
	//		}
	//		cout << endl;
	//	}
	//}
	
	
	// if max_w == 0 then error
	for ( int i = 0; i < h; i++ )
		dfs( 0, i );
	
	cout << min_split << endl;
	
	return 0;
}



Measured memory_bytes: 4880
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define loop(i, a, n) for(int i = (a); i < (n); i++)
#ifdef _DEBUG
#define dd(x) cout << #x << " : " << x << endl
#else
#define dd(x)
#endif
using namespace std;
using ll = int64_t;

int main(){
    int n; cin >> n;
    ll max_a = -1;
    ll ans = 0;
    rep(i, n) {
        ll a; cin >> a;
        if(a > max_a) max_a = a;
        else {
            ans += max_a - a;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <sstream>
#include <string>
#include <cstdio>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cstring>
#include <tuple>
#include <utility>
#include <list>
#include <cmath>

using namespace std;

typedef long long LL;
typedef vector<int> Array;
typedef pair<int, int> P;

const int INF = 1 << 29;
const LL MOD = 100000;
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define all(c) (c).begin(), (c).end()

struct edge{ int to, cost; edge(int t, int c) :to(t), cost(c){} };

int dxk[] = { 1, 1, 1, 0, -1, 0 };
int dxg[] = { 0, 1, 0, -1, -1, -1 };
int dy[] = { -1, 0, 1, 1, 0, -1 };

//Shopping in JOI Kingdom
int main()
{
	int n;
	while (cin >> n && n)
	{
		int m, k; cin >> m >> k;
		vector<vector<edge>> graph(n);
		rep(i, m)
		{
			int f, t, d; cin >> f >> t >> d;
			f--; t--;
			graph[f].push_back(edge(t, d));
			graph[t].push_back(edge(f, d));
		}

		vector<int> dists(n, INF);
		priority_queue<P, vector<P>, greater<P>> que;
		rep(i, k)
		{
			int x; cin >> x;
			x--;
			dists[x] = 0;
			que.emplace(0, x);
		}

		while (!que.empty())
		{
			P p = que.top(); que.pop();
			int d = p.first, node = p.second;
			if (d > dists[node]) continue;
			for (auto& e : graph[node]) if (d + e.cost < dists[e.to])
			{
				dists[e.to] = d + e.cost;
				que.emplace(d + e.cost, e.to);
			}
		}

		int ans = 0;

		rep(i, graph.size()) for (auto& e : graph[i]) ans = max(ans, (dists[i] + dists[e.to] + e.cost + 1) / 2);
		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 4172
#include<bits/stdc++.h>
using namespace std;
string s;
int d,maxd=-1,ans;

int main(){
  cin>>s;
  s+='#';
  for(int i=0;i<s.size();i++){
    if(s[i]=='e'){
      if(s[i+3]=='e'||s[i+3]=='#'){
	if(maxd<d)maxd=d,ans=0;
	d=0;
      }else d++;
      i+=2;
    }else{
      if(s[i+7]=='c'||s[i+7]=='#'){
	if(maxd<d)maxd=d,ans=1;
	d=0;
      }else d++;
      i+=6;
    }    
  }
  if(!ans)cout<<"egg"<<endl;
  else cout<<"chicken"<<endl;
  return 0;
}

Measured memory_bytes: 1192
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <ctype.h>
#include <math.h>
#include <stack>
#include <string>
#include <string.h>
using namespace std;
double PI = 3.1415926535897932;
long mod = 1000000007;

const long INF = 1e9 + 1;

int main() {
  long a,b,k;
  cin >> a >> b >> k;
  
  if(a > k) cout << a-k << " " << b << endl;
  else cout << 0 << " " << max((long)0, b-(k-a)) << endl;
}

Measured memory_bytes: 3576
N = list(input())
N = [int(i) for i in N]
for i in range(2**3):
    cur = bin(i)[2::].zfill(3)
    c = N[0]
    n = []
    for i in range(3):
        if cur[i]=='0':
            n.append('+')
            c += N[i+1]
        else:
            n.append('-')
            c -= N[i+1]
    if c==7:
        m = '='
        print(N[0],n[0],N[1],n[1],N[2],n[2],N[3],m,c,sep=(''))
        break

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

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

	int a = n % (2 * d + 1);
	int ans = 0;
	if (a == 0) {
		ans = n / (2 * d + 1);
	}
	else {
		ans = ((n - a) / (2 * d + 1)) + 1;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
def main():
	arr =[]
	for i in range(int(input())):
		arr.append(int(input()))
	ans = 0
	now = 0
# (arr[i]+arr[i+1])//2 >= (arr[i]/2)+(arr[i+1]/2)
	for i in arr:
		if i==0:
			ans = ans +(now//2)
			now = 0
		else:
			now = now+i
	ans= ans+(now//2)
	print(ans)
if __name__ =="__main__":
	main()

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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int32 N;
	string s;
	cin >> N >> s;
	map<pair<string, string>, int64> mp;
	REP(i, 1<<N){
		string t = "", t2 = "";
		REP(j, N){
			if(i >> j & 1){
				t += s[j];
			}else{
				t2 += s[j];
			}
		}
		reverse(all(t2));
		mp[make_pair(t, t2)]++;
	}
	int64 res = 0;
	REP(i, 1 << N){
		string t = "", t2 = "";
		REP(j, N){
			if(i >> j & 1){
				t += s[j+N];
			}else{
				t2 += s[j+N];
			}
		}
		reverse(all(t));
		res += mp[make_pair(t, t2)];
	}
	cout << res << endl;
}


Measured memory_bytes: 87040
#include<stdio.h>
#include<string.h>

#define M 1000005
#define L 14

char H[M][L]; /* Hash Table */

int getChar(char ch) {
  if (ch == 'A')
    return 1;
  else if (ch == 'C')
    return 2;
  else if (ch == 'G')
    return 3;
  else if (ch == 'T')
    return 4;
}

// hash function
long long getKey(char str[]) {
  long long sum = 0, p = 1, i;

  for (i = 0; i < strlen(str); i++) {
    sum += p * (getChar(str[i]));
    p *= 5;
  }

  return sum;
}

int h1(int key) {
  return key % M;
}

int h2(int key) {
  return 1 + (key % (M - 1));
}

int find(char str[]) {
  long long cur, key, counter = 0;

  key = getKey(str);

  while (1) {
    cur = (h1(key) + counter * h2(key)) % M;

    if (!strcmp(str, H[cur]))
      return 1;
    if (!strlen(H[cur]))
      return 0;

    counter++;
  }
}

void insert(char str[]) {
  long long cur, key, counter = 0;

  key = getKey(str);

  while (1) {
    cur = (h1(key) + counter * h2(key)) % M;

    if (!strcmp(str, H[cur]))
      return;
    if (!strlen(H[cur])) {
      strcpy(H[cur], str);
      return;
    }

    counter++;
  }
}

int main() {
  int i, n, h;
  char str[L], com[9];

  for (i = 0; i < M; i++)
    H[i][0] = '\0';

  scanf("%d", &n);

  for (i = 0; i < n; i++ ) {
    scanf("%s %s", com, str);

    if (!strcmp(com, "insert")) {
      insert(str);
    } else {
      if (find(str))
        printf("yes\n");
      else
        printf("no\n");
    }
  }
}



Measured memory_bytes: 15408
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int W = scanner.nextInt();
        int[] w = new int[n];
        int[] v = new int[n];
        for (int i = 0; i < n; ++i) {
            w[i] = scanner.nextInt();
            v[i] = scanner.nextInt();
        }
        System.out.println(solve(W, w, v));
//        System.out.println(solve2(W, w, v));
    }

    private static long solve(int W, int[] w, int[] v) {
        long[][] dp = new long[w.length][W + 1];
        for (int i = 0; i < dp.length; ++i)
            Arrays.fill(dp[i], -1);
//        return findMax(0, w, v, W, new HashMap<>());
        return findMaxArr(0 , w, v, W, dp);
    }

    private static long findMax(int ind, int[] w, int[] v, int W, Map<Integer, Map<Integer, Long>> cache) {
        if (ind > w.length - 1)
            return 0;
//        String key = ind + "_" + W;
        Map<Integer, Long> cache2 = cache.get(ind);
        if (cache2 != null && cache.get(ind).containsKey(W))
            return cache.get(ind).get(W);
        long res;
        if (w[ind] > W) {
            res = findMax(ind + 1, w, v, W, cache);
        } else {
            res = Math.max(
                    v[ind] + findMax(ind + 1, w, v, W - w[ind], cache),
                    findMax(ind + 1, w, v, W, cache));
        }
//        System.out.println("ind:" + ind + " W:" + W);
        if (cache2 == null) {
            cache2 = new HashMap<>();
        }
        cache2.put(W, res);
        cache.put(ind, cache2);
        return res;
    }

    private static long findMaxArr(int ind, int[] w, int[] v, int W, long[][] dp) {
        if (ind > w.length - 1)
            return 0;
        if (dp[ind][W] > -1)
            return dp[ind][W];
        long res;
        if (w[ind] > W) {
            res = findMaxArr(ind + 1, w, v, W, dp);
        } else {
            res = Math.max(
                    v[ind] + findMaxArr(ind + 1, w, v, W - w[ind], dp),
                    findMaxArr(ind + 1, w, v, W, dp));
        }
        dp[ind][W] = res;
        return res;
    }

    private static long solve2(int W, int[] w, int[] v) {
//        for (int ind = w.length - 1; ind >= 0; --ind) {
//            for (int i = 0)
//        }
        long[][] dp = new long[w.length][W + 1];
        for (int i = 0; i < dp.length; ++i)
            Arrays.fill(dp[i], 0);
        for (int ww = 1; ww <= W; ++ww) {
            for (int ind = 0; ind < w.length; ++ind) {
                if (w[ind] <= ww) {
                    if (ind == 0) {
                        dp[ind][ww] = v[ind];
                    } else {
                        dp[ind][ww] = Math.max(v[ind] + dp[ind - 1][ww - w[ind]], dp[ind - 1][ww]);
                    }
                } else if (ind > 0) {
                    dp[ind][ww] = dp[ind - 1][ww];
                }
            }
        }
        return dp[w.length - 1][W];
    }
}


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

int main(){
  ll n,i,s;
  cin >> n;
  s=0;
  vector<ll> a(n);
  for(i=0;i<n;i++){
    cin >> a.at(i);
    if(i!=0&&a.at(i)<a.at(i-1)){
      s += a.at(i-1)-a.at(i);
      a.at(i)=a.at(i-1);
    }
  }
  
  cout << s << endl;
}

Measured memory_bytes: 4776
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;
#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
using ll = long long;
using P = pair<int,int>;

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

  if(s=="Sunny") cout << "Cloudy" << endl;
  if(s=="Cloudy") cout << "Rainy" << endl;
  if(s=="Rainy") cout << "Sunny" << endl;
  return 0;
}

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

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

    int res = 100000000, tmp;
    for (int i = 0; i <= (s.size()-t.size()); i++) {
        if (s.substr(i, t.size()) == t) {
            cout << 0 << endl;
            return 0;
        } else {
            tmp = 0;
            int index = i;
            for (int j = 0; j < t.size(); j++) {
                if (t.at(j) != s.at(index)) tmp++;
                index++;
            }
            res = min(res,tmp);
        }
    }

    cout << res << endl;

    return 0;
}


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

#pragma warning(disable : 4996)

typedef long long ll;
#define all(x) (x).begin(), (x).end()  // sortなどの引数を省略
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define max3(x, y, z) max(x, max(y, z))
#define min3(x, y, z) min(x, min(y, z))

#ifdef _MSC_FULL_VER  //デバッグ出力
#define dout cout
#define debug() if (true)
#define check(x) std::cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) std::cout << "☆" << x << endl
#else
#define dout \
  if (false) cout
#define debug() if (false)
#define check(x) \
  if (false) cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) \
  if (false) cout << "☆" << x << endl
#endif

using namespace std;
//#define int long long;

double dist(double x1, double y1, double x2, double y2) {
  return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
ll idist(ll x1, ll y1, ll x2, ll y2) {
  return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

signed main() {
  ll N;
  cin >> N;
  cout << (1 + N - 1) * (N - 1) / 2;
}


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

def d_sum(n):
    ret = 0
    while(n>0):
        ret += n%10
        n //= 10
    return ret

ans = N
for i in range(1, N//2+2):
    ans = min(ans, d_sum(i)+d_sum(N-i))

print(ans)


Measured memory_bytes: 73508
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define sort(A) sort(A.begin(),A.end())
#define reverse(A) reverse(A.begin(),A.end());

typedef long long ll;

int main(){
  int n,x,y;
  cin >> n >> x >> y;
  map<int,int> ans;
  rep1(i,n-1) ans[i] == 0;
  rep1(i,n){//i番目の頂点と
    for(int j=i+1;j<=n;j++){//j番目の頂点
      int dist = j-i;
      
      //ショートカットを使える場合
      int dist2 = abs(x-i);//xに着くまで
      dist2 ++;//yに移動
      dist2 += abs(y-j);
      
      ans[min(dist,dist2)] ++;
    }
  }
  for(auto p : ans){
    cout << p.second << endl;
  }
}

Measured memory_bytes: 384
n,m=map(int,input().split())
graph=[[]for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  graph[a].append(b)
  graph[b].append(a)
cost=[0]*n
visited=[False]*n
for i in range (m):
  p,x=map(int,input().split())
  p=p-1
  cost[p]=cost[p]+x
from collections import deque
quest=deque([0])
visited[0]=True
while len(quest)!=0:
  a=quest.popleft()
  for i in graph[a]:
    if visited[i]==True:
      continue
    quest.append(i)
    visited[i]=True
    cost[i]=cost[i]+cost[a]
print(*cost)

Measured memory_bytes: 56168
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000;
bitset<maxn*maxn+1>s;
int main()
{
    int N,x,ans;
    while(~scanf("%d",&N))
	{
        s.reset(); ans=0;
        s[0]=1;
        for(int i=1;i<=N;i++)
		{
            scanf("%d",&x);
            s|=(s<<x);
            ans+=x;
        }
        for(int i=(ans+1)/2;;i++)
        if(s[i])
		{
            printf("%d\n",i);
            break;
        }
    }
    return 0;
}

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

int getans()
{
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    if( k < a ) return k;
    if( k >= a && k <= a + b ) return a;
    return a - (k - ( a + b ));
}

int main()
{
    int ans = getans();
    cout << ans;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b) - 1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)

#define PB push_back
#define INF (1<<29)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define CLR(a) memset(a,0,sizeof(a))
const int dx[] = {-1,0,0,1},dy[] = {0,1,-1,0};

typedef long long int ll;

using namespace std;

int main(){
    while(true){
	int n;
	map<char,char> dic;
	cin >> n;
	if(n==0) break;
	REP(i,n){
	    char a,b;
	    cin >> a >> b;
	    dic[a] = b;
	}
	cin >> n;
	string ans = "";
	REP(i,n){
	    char a;
	    cin >> a;
	    if(dic.find(a) != dic.end()){
		ans += dic[a];
	    }else ans += a;
	}
	cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 1340
def num2alpha(num):
    if num <= 26:
        return chr(64+num)
    elif num % 26 == 0:
        return num2alpha(num//26-1)+chr(90)
    else:
        return num2alpha(num//26)+chr(64+num % 26)


def main():
    N = int(input())

    print(num2alpha(N).lower())


if __name__ == "__main__":
    main()


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

#define For(i, j, k) for(int i = j; i <= k; i++)
#define Forr(i, j, k) for(int i = j; i >= k; i--)

using namespace std;

const int N = 200010;

int n, k;
char S[N], T[N];

void print(int l){
	Forr(i, n, n - l + 1) T[i] = 'A' + ((n - i) & 1);
	For(i, 1, n - l) T[i] = l & 1 ? 'B' - S[i + l] + 'A' : S[i + l];
	puts(T + 1);
	exit(0);
}

int main(){
	scanf("%d%d%s", &n, &k, S + 1);

	For(i, 1, n){
		if((S[i] == 'B') ^ (i & 1)){
			--k;
			S[i] = 'B' - S[i] + 'A';
			if(!k) print(i - 1);
		}
		--k;
		if(!k) print(i);
	}
	if((k & 1) && n % 2 == 1) putchar('B'), --n, print(n);
	else print(n);

	return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <functional>
#include <set>
#include <map>
#define rep(i,n) for(int (i) = 0;(i) < (n);(i)++)

bool toB(char c){
    if(c=='#'){
        return true;
    }else{
        return false;
    }
}

int dir[4][2]={{0,-1},{0,1},{-1,0},{1,0},};


int dmap[1005][1005];

struct node{
    int i,j;
    bool operator>(const node& other) const{
        if(i != other.i){
            return i > other.i;
        }else if(this->j != other.j){
            return j > other.j;
        }else{
            return false;
        }
    }
    
    bool operator<(const node &other) const{
        if(i != other.i){
            return this->i < other.i;
        }else if(this->j != other.j){
            return this->j < other.j;
        }else{
            return false;
        }
    }
};

using namespace std;
int main(){
    int H,W;
    string m[1005];
    scanf("%d %d",&H,&W);
    rep(i,H){
        cin>>m[i];
    }
    priority_queue<pair<int,node> ,vector<pair<int,node> > ,greater<pair<int,node> > > pq;

    rep(i,H){
        rep(j,W){
            dmap[i][j]=3000;
            if(toB(m[i][j])){
                pq.push(make_pair(0,(node){i,j}));
            }
        }
    }
    
    int ans = 0;
    while(!pq.empty()){
        pair<int,node> temp = pq.top();
        pq.pop();
        int dist = temp.first;
        node pl=temp.second;
        if(dmap[pl.i][pl.j]<=dist){
            continue;
        }
        dmap[pl.i][pl.j] = dist;
        ans = max(ans,dist);
        rep(d,4){
            int ni = pl.i + dir[d][0];
            int nj = pl.j + dir[d][1];
            if(ni>=0&&ni<H&&nj>=0&&nj<W){
                if(dmap[ni][nj] > dist+1)
                    pq.push(make_pair(dist+1,(node){ni,nj}));
            }
        }
    }
    cout<<ans<<endl;

}


Measured memory_bytes: 31464
//! ----------------------------------------------
//! Framework <https://github.com/vain0x/procon>
//!
//! See the bottom of file for solution.
//! ----------------------------------------------

#![allow(unused_imports)]
#![allow(non_snake_case)]

use std::cell::RefCell;
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Display, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;

/// Print values to standard error if debug mode.
#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), stderr());
            writeln!(err, "\x1B[33m{}\x1B[0m = {:?}", e, $e).unwrap()
        })*
    };
}

/// Read from standard input and parse each word.
/// - `read!(T, U, ..)` parses a line as a tuple of words.
/// - `read![[T]]` parses a line as an array of words.
/// - `read![..; N]` parses `N` lines, using `read!(..)` repeatedly.
#[allow(unused_macros)]
macro_rules! read {
    ([$t:ty] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ($($t:ty),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ([$t:ty]) =>
        (rl().split_whitespace().map(|w| w.parse().unwrap()).collect::<Vec<$t>>());
    ($($t:ty),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(w.next().unwrap().parse::<$t>().unwrap()),*)
    }};
}

/// Read a line from standard input.
#[allow(dead_code)]
fn rl() -> String {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();

    #[allow(deprecated)]
    buf.trim_right().to_owned()
}

// -----------------------------------------------
// Solution
// -----------------------------------------------

fn main() {
    let N = read!(usize);

    let mut map = BTreeMap::new();
    for _ in 0..N {
        let mut S = rl().chars().collect::<Vec<_>>();
        S.sort();
        *map.entry(S).or_insert(0) += 1;
    }

    let mut count = 0_i64;
    for (_, n) in map {
        count += n * (n - 1) / 2;
    }

    println!("{}", count)
}


Measured memory_bytes: 14588
#include <iostream>
#include<cmath>
#include<string>
#include<algorithm>
#include<ctime>
#include<functional>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<map>
#include<set>
#include<tuple>
#include<cassert>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<iomanip>
#include<climits>
#include<typeinfo>
#include<utility>
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,n) for(ll i=0;i<n;i++)
#define For(i,m,n) for(int i=m;i<n;i++)
#define FOR(i,m,n) for(ll i=m;i<n;i++)
double pi = 3.141592653589793238;
using ll = long long;
using namespace std;

ll LGCD(ll x, ll y) { if (x % y == 0) return y;else return LGCD(y, x % y); }
ll LLCM(ll x, ll y) { return x * y / LGCD(x, y); }

int GCD(int x, int y) { if (x % y == 0) return y;else return GCD(y, x % y); }
int LCM(int x, int y) { return x * y / GCD(x, y); }
ll dpcombination[10000][10000];

ll modi = 1000000007;
ll combination(ll n, ll r) {
	if (n == r) { return dpcombination[n][n] = 1; }
	else if (r == 0) { return dpcombination[n][0] = 1; }
	else if (r == 1) { return dpcombination[n][1] = n; }
	else if (dpcombination[n][r]) { return dpcombination[n][r]; }
	else { return dpcombination[n][r] = combination(n - 1, r - 1) % modi + combination(n - 1, r) % modi; }
}

void clockman(int time1) {

	cout << 1.0*(clock() - time1) / CLOCKS_PER_SEC << endl;
	return;
}
//cout << fixed << setprecision(10)

int GD(ll num) {
	return log10(num) + 1;
}

int main() {



	int n;
	cin >> n;
	ll ans = 1;
	vector<ll> a(n);


	for (int i = 0;i < n;i++) {
		cin >> a[i];
		if (a[i] == 0) {
			cout << 0 << endl;
			return 0;
		}

	}
	for (int i = 0;i < n;i++) {



		//cout << GD(ans) + GD(a[i]) << endl;
		ans = ans * a[i];
	}
	if (ans <= 1000000000000000000 && ans > 0) {
		cout << ans << endl;
	}
	else cout << -1 << endl;
	return 0;
}


Measured memory_bytes: 4004
while(True):
    N = int(input())
    if N == 0:
        quit()
    data = []
    emp = [[0,10**9]]
    for _____ in range(N):
        tmp = input().split()
        if tmp[0] == "W":
            c,k = int(tmp[1]),int(tmp[2])
            while(k):
                if (emp[0][1]-emp[0][0]) > k:
                    data.append([c,[emp[0][0],emp[0][0]+k]])
                    emp[0] = [emp[0][0]+k,emp[0][1]]
                    break
                elif (emp[0][1]-emp[0][0]) == k:
                    data.append([c,[emp[0][0],emp[0][0]+k]])
                    del(emp[0])
                    break
                else:
                    data.append([c,emp[0]])
                    k -= (emp[0][1]-emp[0][0])
                    del(emp[0])
        elif tmp[0] == "D":
            emp += [i[1] for i in data if i[0] == int(tmp[1])]
            data = [i for i in data if i[0] != int(tmp[1])]
            emp.sort()
        else:
            ans = True
            s = int(tmp[1])
            for i in data:
                if i[1][0]<=s<i[1][1]:
                    print(i[0])
                    ans = False
                    break
            if ans:
                print(-1)
    print()



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

#define PI 3.14159265358979323846264338327950288419

using namespace std;

int n;
char s3[4][6] = {
	"aab",
	"c.b",
	"cdd"};
char s4[5][6] = {
	"abcc",
	"abdd",
	"eegh",
	"ffgh"};
char s5[6][6] = {
	"aabcc",
	"d.bhh",
	"deii.",
	".eg.j",
	"ffg.j"};

void print_grid(char grid[][6], int pos, int dim){
	for(int i = 0; i < dim; i++){
		for(int j = 1; j <= n; j++){
			if(j >= pos && j < pos + dim){
				printf("%c", grid[i][j - pos]);
			}else{
				printf(".");
			}
		}
		puts("");
	}
}

int main(){
	scanf("%d", &n);
	if(n == 2){
		printf("-1\n");
	}else if(n == 3 || n == 6){
		for(int i = 1; i <= n; i += 3){
			print_grid(s3, i, 3);
		}
	}else if(n == 7 || n == 11){
		// first row
		char str[7] = "xxyyzz";
		printf(".%s", str);
		if(n == 11){
			printf("....");
		}
		puts("");
		for(int i = 0; i < 6; i++){
			printf("%c", str[i]);
			for(int j = 0; j < n - 1; j++){
				int piv = i / 3 * 3;
				if(j >= piv && j < piv + 3){
					printf("%c", s3[i - piv][j - piv]);
				}else{
					printf(".");
				}
			}
			puts("");
		}
		if(n == 11){
			print_grid(s4, 8, 4);
		}
	}else{
		int five = n % 4;
		for(int i = 1; i <= n; i++){
			if(five > 0){
				print_grid(s5, i, 5);
				five--;
				i += 4;
			}else{
				print_grid(s4, i, 4);
				i += 3;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1280
#include <iostream>
#include <vector>
#include<algorithm>
#include<string>
#include<map>
using namespace std;

int main(){
    string S, T;
    cin >> S >> T;
    map<char, char> table1;
    map<char, char> table2;    
    for(int i = 0; i < S.size(); i++){
        if(table1.find(S[i]) == table1.end() || table1[S[i]] == T[i]){
            table1[S[i]] = T[i];
        }else{
            cout << "No" << endl;
            return 0;
        }
        if(table2.find(T[i]) == table2.end() || table2[T[i]] == S[i]){
            table2[T[i]] = S[i];
        }else{
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;

}

Measured memory_bytes: 776
int N,M;
int A[1<<17];
main()
{
	scanf("%d%d",&N,&M);
	for(int i=0;i<N;i++)scanf("%d",&A[i]);
	int L=1,R=1<<30;
	long X=0;
	while(R-L>1)
	{
		int i=L+R>>1;
		int d=M;
		long k=0;
		for(int j=0;j<N;j++)
		{
			int a=A[j];
			while(i<=a)
			{
				a/=2;
				d--;
			}
			k+=a;
		}
		if(d>=0)
		{
			R=i;
			X=k-i/2*d;
		}
		else L=i;
	}
	printf("%ld\n",X>0?X:0);
}


Measured memory_bytes: 512
import sys
input = sys.stdin.readline

class Graph():  #non-directed
    def __init__(self, n, edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - 1].append((e[1] - 1, e[2]))
            self.graph[e[1] - 1].append((e[0] - 1, e[2]))

    def warshall_floyd(self, INF=10**18):
        dist = [[INF for j in range(self.n)] for i in range(self.n)]
        for i in range(self.n):
            dist[i][i] = 0
        for i in range(self.n):
            for j, cost in self.graph[i]:
                dist[i][j] = cost
        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][k] != INF and dist[k][j] != INF:
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        return dist

INF = 10**18

N, M, L = map(int, input().split())
E = [tuple(map(int, input().split())) for _ in range(M)]

G = Graph(N, E)
D = G.warshall_floyd()

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        if D[i][j] > L:
            D[i][j] = INF
        else:
            D[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            if D[i][k] != INF and D[k][j] != INF:
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])

Q = int(input())

for _ in range(Q):
    s, t = map(int, input().split())
    if D[s - 1][t - 1] != INF:
        print(D[s - 1][t - 1] - 1)
    else:
        print(-1)

Measured memory_bytes: 67164
n = int(input())
if n%2:
    h = n//2
else:
    h = n//2+1
count=0
for i in range(h+1,0,-1):
    judge = n//i
    if n%i == 0:
        count=count+judge-1
    else:count += judge
for i in range(h+2,n):
    count+=1

print(count)

Measured memory_bytes: 9148
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<pair<int, int>, char> p;
int main() {
	int n;
	while (cin >> n, n) {
		p a[20];
		for (int i = 0; i < n; i++) {
			cin >> a[i].second;
			a[i].first.first = 0;
			a[i].first.second = n;
			for (int j = 1; j < n; j++) {
				int k; cin >> k;
				if (!k)a[i].first.first++;
				else if (k == 1)a[i].first.second--;
			}
		}
		for (int i = n; i >= 1; i--)
			for (int j = 1; j < i; j++)
				if (a[j - 1].first < a[j].first)swap(a[j - 1], a[j]);
		for (int i = 0; i < n; i++)
			cout << a[i].second << endl;
	}
	return 0;
}


Measured memory_bytes: 2996
N = gets.chomp.to_i
D,X = gets.chomp.split.map(&:to_i)
A = Array.new(N)
N.times do |n|
	A[n] = gets.chomp.to_i
end

sum = 0
A.each do |a|
	sum += (D-1)/a+1
end
print "#{sum+X}\n"

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

count = 0
for n in range(1, N + 1):
  if (n % 2 == 0):
    continue
  m_count = 0
  for m in range(1, n + 1):
    if (n % m == 0):
      m_count += 1
  
  if (m_count == 8):
    count += 1

print(count)

Measured memory_bytes: 3060