akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main()
{
	char num[] = "";	//数字の文字列
	char naa;
	int n;				//各桁の和
	int i;

	while (1)
	{
		

		n = 0;
		while (isalnum((naa = fgetc(stdin))))
		{
			n += naa - '0';
		}
		if (n == 0)
			break;
		printf("%d\n", n);
	}

    return 0;
}


Measured memory_bytes: 2112
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String s = sc.next();
		int x = 0;
		int max = 0;
		for(int i = 0; i < n; i++) {
			x += (s.charAt(i) == 'I') ? 1 : -1;
			max = (x > max) ? x : max;
		}
		System.out.println(String.valueOf(max));
	}
}

Measured memory_bytes: 9684
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

//vector string deque break continue
#define forn(i, s, f) for (int i = (int)s; i < (int)f; i++)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define fs first
#define sc second
#define pf push_front
#define pb push_back
#define pop_f pop_front
#define pop_b pop_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()

const int MOD = 1e9 + 7;

int add(int x, int y) {
    x += y;
    if (x >= MOD)
        return x - MOD;
    return x;
}

int sub(int x, int y) {
    x -= y;
    if (x < 0)
        return x + MOD;
    return x;
}

int mul(int x, int y) {
    return (1LL * x * y) % MOD;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    int ans = 1;
    multiset <int> a;
    forn (i, 0, 3)
        a.insert(-1);
    forn (i, 0, n) {
        int t;
        cin >> t;
        ans = mul(ans, a.count(t - 1));
        if (a.count(t - 1) == 0) {
            return cout << ans, 0;
        }
        a.erase(a.find(t - 1));
        a.insert(t);
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
 
int main()
{
    int e[101][101];
    int R, C, r, c;
    int s, total;
 
    scanf("%d%d", &R, &C);
    for (r = 1; r <= R; r++) {
        for (c= 1; c <= C; c++) scanf("%d", &e[r][c]);
    }
     
    for (r = 1; r <= R; r++) {
        s = 0;
        for (c = 1; c <= C; c++) s += e[r][c];
        e[r][0] = s;
    }
    total = 0;
    for (c = 1; c <= C; c++) {
        s = 0;
        for (r = 1; r <= R; r++) s += e[r][c];
        e[0][c] = s;
        total += s;
    }
    for (r = 1; r <= R; r++) {
        for (c = 1; c <= C; c++) printf("%d ", e[r][c]);
        printf("%d\n", e[r][0]);
    }
    for (c = 1; c <= C; c++) printf("%d ", e[0][c]);
    printf("%d\n", total);
    return 0;
}


Measured memory_bytes: 2056
#include <bits/stdc++.h>
using namespace std;
int n,i,j,b[1000100],r;
char a[1000100];
bool ok=false;
int main() {
  scanf("%d",&n);
  scanf("%s",a);
  for (i=0; i<n; i++) {
    a[i]=a[i]-'1';
    if (a[i]==1) ok=true;
    b[i+1]=b[i];
    for (j=i+1; j%2==0; j/=2) b[i+1]++;
  }
  if (!ok) for (i=0; i<n; i++) a[i]/=2;
  for (i=0; i<n; i++) if (a[i]==1 && b[n-1]==b[i]+b[n-1-i]) r^=1;
  if (!ok) r*=2;
  printf("%d\n",r);
  return 0;
}


Measured memory_bytes: 5120
import numpy as np
A = int(input())
B = int(input())

if A == 1:
    if B == 2:
        ans = 3
    else:
        ans = 2
elif A == 2:
    if B == 1:
        ans = 3
    else:
        ans = 1
else:
    if B == 1:
        ans = 2
    else:
        ans = 1
print(ans)

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

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    cout << (n + k - 3) / (k - 1) << endl;
}

Measured memory_bytes: 3568
H,W=map(int,input().split())
S=[]
for _ in range(H):
    S.append(list(input()))

from collections import deque

que=deque()
maxx=0

for i in range(H):
    for j in range(W):
        if S[i][j]=="#":
            continue
        ans=[[-1]*W for _ in range(H)]
        ans[i][j]=0
        que.append((i,j))
        while que:
            h,w=que.popleft()
            if h!=0 and S[h-1][w]==".":
                if ans[h-1][w]==-1:
                    ans[h-1][w]=ans[h][w]+1
                    que.append((h-1,w))
            if h!=H-1 and S[h+1][w]==".":
                if ans[h+1][w]==-1:
                    ans[h+1][w]=ans[h][w]+1
                    que.append((h+1,w))
            if w!=0 and S[h][w-1]==".":
                if ans[h][w-1]==-1:
                    ans[h][w-1]=ans[h][w]+1
                    que.append((h,w-1))
            if w!=W-1 and S[h][w+1]==".":
                if ans[h][w+1]==-1:
                    ans[h][w+1]=ans[h][w]+1
                    que.append((h,w+1))
            maxx=max(maxx,ans[h][w])
print(maxx)  


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

const long long MOD = 1000000007;
const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

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

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string s;
  cin >> s;
  int K;
  cin >> K;
  vector<string> vec;
  for (int i = 0; i < s.size(); i++)
  {
    for (int j = 1; j <= K; j++)
    {
      string tmp = s.substr(i, j);
      vec.push_back(tmp);
    }
  }
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
  cout << vec[K - 1] << endl;
  return 0;
}

// 辞書順K番目が長さKを超えることはない
// sortとunique, eraseで重複部分を削除する．


Measured memory_bytes: 1660
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

int main() {
	int N;
	cin >> N;
	vector<int> L(N);
	int longest_L = 0;
	int sum = 0;
	for (int i = 0; i < N; i++) {
		cin >> L[i];
		sum += L[i];
		longest_L = max(longest_L, L[i]);
	}
	if (2 * longest_L < sum) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 3584
#include<iostream>
using namespace std;
int main(){
    while(1){
         int n,aten=0,bten=0;
         cin>>n;
         if(n==0)break;
         for(int i=0;i<n;i++){
            int a,b;
            cin>>a>>b;
            if(a>b){
              aten+=a+b;
              }
            else if(a==b){
                   aten+=a;
                   bten+=b;
            }
            else if(a<b){
                   bten+=a+b;
            }
         }
         cout<<aten<<" "<<bten<<endl;
    }
}


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

int main(){
  int A,B;
  cin >> A >> B;
  
  if(0 >= A || 10 <= A || 0 >= B || 10 <= B){
    cout << -1 << endl;
  }else{
    cout << A*B << endl;
  }
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
const int MAX = 700000;
const int 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;
}
/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y) {
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}

int main() {
	int n;
	cin >> n;
	string s;
	string s1;
	cin >> s >> s1;
	long long int sum = 1;
	int ver = -1;
	for (int i = 0; i < n; i++) {
		if (s[i] == s1[i]) {
			if (ver == 1) {
				sum = sum * 2;
				sum = sum % MOD;
				ver = 1;
			}
			else if(ver == -1){
				sum = sum * 3;
				ver = 1;
			}
			else {
				ver = 1;
			}
		}
		else {
			if (ver == 1) {
				sum = sum * 2;
				sum = sum % MOD;
				ver = 0;
			}
			else if(ver == 0){
				sum = sum * 3;
				sum = sum % MOD;
				ver = 0;
			}
			else {
				sum = sum * 6;
				ver = 0;
			}
			i = i + 1;
		}
	}
	cout << sum;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int LL;
typedef pair<int,int> P;
typedef pair<LL,LL> PL;

PL po(LL x){
  LL y=sqrt(x-1)+1;
  while((y-1)*(y-1)>=x)y--;
  if(x>y*(y-1))return PL(y,y);
  else return PL(y-1,y);
}
int main(){
  LL n;cin>>n;
  LL a=po(n).first,b=po(n).second;
  LL sa=a*b-n;
  cout<<0<<" "<<1<<" "<<a<<" "<<0<<" "<<a-sa<<" "<<b<<endl;
  return 0;
}


Measured memory_bytes: 256
import math
n = int(input())
if n % 2 == 1:
  print(0)
  quit()
if n == 0:
  print(0)
  quit()

l = int(math.log10(n))+1
cnt = 0
for i in range(1,10*l):
  cnt += (n // 5 ** i) // 2
print(cnt)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
namespace mine
{
    typedef long long ll;
    #define pr pair<ll,ll>
    #define FR first
    #define SE second
    #define MP make_pair
    #define PB push_back
    #define vc vector
    #define all(x) (x).begin(),(x).end()
    #define sz(x) ((int)(x).size())
    #define bin(x) (1ll<<(x))
    ll qread()
    {
        ll ans=0,f=1;char c=getchar();
        while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
        while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
        return ans*f;
    }
    void write(ll num)
    {
        if(num<0) putchar('-'),num=-num;
        if(num>=10) write(num/10);
        putchar('0'+num%10);
    }
    void write1(ll num){write(num);putchar(' ');}
    void write2(ll num){write(num);putchar('\n');}
    template<typename T> void chmax(T &x,const T y) {x=(x>y?x:y);}
    template<typename T> void chmin(T &x,const T y) {x=(x<y?x:y);}
    ll gcd(ll x,ll y){return y?gcd(y,x%y):0;}

    const int INF=0x3f3f3f3f;
    const int MOD=998244353;
    inline int mm(const int x){return x>=MOD?x-MOD:x;}
    inline ll qpower(ll x,ll e)
    {
        ll ans=1;
        while(e){if(e&1)ans=ans*x%MOD;x=x*x%MOD;e>>=1;}
        return ans;
    }
    ll invm(ll x){return qpower(x,MOD-2);}
    const int N=1e5+10;

	char mp[20][20];bool vis[40][40];
	int n,m;
	bool check(int x,int y)
	{
		vis[x][y]=1;
		if(x==n and y==m) return 1;
		int a=(mp[x+1][y]=='#');
		int b=(mp[x][y+1]=='#');
		if(a+b==1) return check(x+a,y+b); else return 0;
	}
	void main()
	{
		n=qread(),m=qread();
		for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
		if(mp[1][1]=='.' or !check(1,1)) {puts("Impossible");return;}
		for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(!vis[i][j] and mp[i][j]=='#')
			{puts("Impossible");return;}
		puts("Possible");
	}
};
int main()
{
	mine::main();
}

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

int main (){
	string s;
	cin>>s;
	if(s[0]=='S'&&s[1]=='U')puts("7");
	if(s[0]=='M')puts("6");
	if(s[0]=='T'&&s[1]=='U')puts("5");
	if(s[0]=='W')puts("4");
	if(s[0]=='T'&&s[1]=='H')puts("3");
	if(s[0]=='F')puts("2");
	if(s[0]=='S'&&s[1]=='A')puts("1");
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		//数取得
		int X = sc.nextInt();
		sc.close();

		int answer = 0;

		int fivehundred = X / 500 ;
		int five = (X - fivehundred*500) / 5;

		System.out.println(fivehundred*1000 + five*5);
	}

}


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

int main(){
	string s;
	cin >> s;
	int len = s.size();
	int ans = 1000000000;
	rep(i,len -2){
        string t;
		t.push_back(s[i]);
        t.push_back(s[i+1]);
        t.push_back(s[i+2]);
		int tnum = atoi(t.c_str());
		ans = min(ans,abs(753-tnum));
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;


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

	int n, i, j, k, m, a, b;
	cin >> n >> m;
	map<int, int> ct;
	while (m--) {
		cin >> a >> b;
		ct[a]++;
		ct[b]++;
	}
	bool valid = true;
	for (auto p : ct) {
		if (p.second % 2 == 1) valid = false;
	}
	if (valid) cout << "YES\n";
	else cout << "NO\n";
	   	 
	return 0;
}


Measured memory_bytes: 4352
#include <iostream>
#define FOR(i,k,n) for(int(i)=(k);(i)<(n);++(i))
#define NMAX 1100
using namespace std;

long factors[NMAX];

// n を素因数分解
void factorize(int n)
{
  int i = 2;
  while (n >= i*i) {
    while (n % i == 0) {
      factors[i] += 1;
      n = n / i;
    }
    ++i;
  }
  // 最後の n も素因数。
  // ただし 1 ならば無視。
  if (n != 1) factors[n] += 1;
}

int main()
{
  int N;
  cin >> N;
  FOR(i,0,NMAX) factors[i] = 0;

  // 2, ..., N の素因数分解
  FOR(i,2,N+1) factorize(i);

  // 正の約数の個数
  long ans = 1;
  FOR(i,2,N+1) {
    ans = ans * (1 + factors[i]);
    ans = ans % int(1e9 + 7);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
//二項係数の計算
int nCr(int A, int B) {
    ll ans = 1;
    for (int i = 0; i < B; i++) {
        ans *= A - i;
    }
    for (int i = 0; i < B; i++) {
        ans /= i + 1;
    }
    return ans;
}
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
int main() {
    ll N;
    cin>>N;
ll a= modpow(8, N, 1000000007) ;
 ll b=modpow(9, N, 1000000007) ;
 b*=2;
 ll c=modpow(10, N, 1000000007);
  ll d=a+c-b;
  d %= 1000000007;
  d+=1000000007;
  d%=1000000007;
  cout<<d<<endl;
}

Measured memory_bytes: 3604
public class Main {
	public static void main(String[] args) {
		int n = new java.util.Scanner(System.in).nextInt();
		
		for (int i = 0; i <= n / 4; i++) {
			// 4ドルのケーキの金額 (4ドル x i個)
			int a = i * 4;
			for (int j = 0; j <= n / 7; j++) {
				// 7ドルのケーキの金額(7ドル x j個)
				int b = j * 7;
				if (a + b == n) {
					System.out.println("Yes");
					return;
				}
			}
		}
		System.out.println("No");
	}
}

Measured memory_bytes: 23124
/*
[soundhound2018-summer-qual] C - Ordinary Beauty
*/

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

double solve(ll n, ll m, ll d) {
    ll r = (d == 0 ? n : (2 * (n - d)));
    return 1.0L * r * (m - 1) / (n * n);
}

int main() {
    ll n, m, d;

    cin >> n >> m >> d;

    cout << setprecision(10) << fixed << solve(n, m, d) << endl;

    return 0;
}


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

int main() {
  int D;
  cin >> D;
  string out;
  
  if (D==25) {
    out = "Christmas";
  }
  
  else if (D==24) {
    out = "Christmas Eve";
  }
  
  else if (D==23) {
    out = "Christmas Eve Eve";
  }
  
  else if (D==22) {
    out = "Christmas Eve Eve Eve";
  }
  
  cout << out;
}

Measured memory_bytes: 256
#include <cstdio>
#include<iostream>
#include<map>
#include<algorithm>
#include<vector>
#include <cmath>
#include <iomanip>
#include <regex>
#include <queue>
#include <set>
using namespace std;
using ll = long long;
using Lf = long double;
using plong = pair<ll,ll>;
const long MAX = 100000;
const long MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];



int main(){
    ll N;cin>>N;
    vector<ll> A(N);
    for(ll i=0;i<N;i++){
        cin>>A[i];
    }
    sort(A.begin(),A.end());
    if(N==2){
        cout<<A[1]<<" "<<A[0]<<endl;
        return 0;
    }
    
    ll _max = A[N-1];
    A.pop_back();
    ll s = _max/2;
    ll idx = upper_bound(A.begin(),A.end(),s)-A.begin();
    if(A[idx]-s>s-A[idx-1]){
        cout<<_max<<" "<<A[idx-1]<<endl;
    }else{
        cout<<_max<<" "<<A[idx]<<endl;
    }

}

Measured memory_bytes: 1024
#include <iostream>

using namespace std;
int main(int argc, char *argv[]) {
	string s;
	cin >> s;
	
	int ans = 0;
	for (int i = 1; i < s.size(); i++) {
		if (s[i] == s[i-1]) {
			ans += 1;
			s[i] = (s[i-1] - '0' + 1) % 2 + '0';
		}
	}
	
	cout << ans << endl;
}

Measured memory_bytes: 512
#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>

std::map<int,int> mp;

int n,a[200005];

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
		mp[a[i]]?(++mp[a[i]]):mp[a[i]]=1;
	}
	std::map<int,int>::iterator it=mp.end();
	--it;
	
	int ans=0,nw;
	while(1){
		if(it->second==0){
			goto loop;
		}
		nw=it->first;
		for(int i=30;i>=1;--i){
			while(it->second>=1&&(1<<i)-nw>=0&&mp[(1<<i)-nw]>=1&&(nw!=(1<<(i-1)))){
				--mp[(1<<i)-nw];
				it->second-=1;
				++ans;
			}
			while(it->second>=2&&nw==(1<<(i-1))){
				it->second-=2;
				++ans;
				
			}
		}
		loop:
			if(it==mp.begin()){
				break;
			}
			--it;
	}
	
	printf("%d\n",ans);
} 

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

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

using namespace std;

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

  int n, sol = 0;
  cin >> n;
  vector<int> a(n), b;
  map<int, int> f;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  b = a;
  sort(a.begin(), a.end());
  for (int i = 0; i < n; i++) {
    f[a[i]] = i % 2;
  }
  for (int i = 0; i < n; i++) {
    sol += (f[b[i]] != (i % 2));
  }
  cout << sol / 2 << "\n";
}


Measured memory_bytes: 5760
class TreeNode {
	TreeNode left_  = null;
	TreeNode right_ = null;
	public TreeNode left{
		get {
			return left_;
		}
		set {
			left_ = value;
		}
	}
	public TreeNode right{
		get {
			return right_;
		}
		set {
			right_ = value;
		}
	}
	
	int key_;
	public int key {
		get {
			return key_;
		}
	}
	public TreeNode(int i) {key_ = i;}
};

interface ITraverser {
	void run(TreeNode start);
};
class PreOrderTraverser : ITraverser {
	public void run(TreeNode visitedNode) {
		if (visitedNode != null) {
			System.Console.Write(" {0}", visitedNode.key);
			run(visitedNode.left);
			run(visitedNode.right);
		}
	}
};
class MidOrderTraverser : ITraverser {
	public void run(TreeNode visitedNode) {
		if (visitedNode != null) {
			run(visitedNode.left);
			System.Console.Write(" {0}", visitedNode.key);
			run(visitedNode.right);
		}
	}
};

class BinarySearchTree {
	
	static void insert (ref TreeNode root, TreeNode newNode)
	{
		TreeNode y = null;
		TreeNode x = root;
		while (x != null) {
			y = x; //???????¨????
			if (newNode.key < x.key) {
				x = x.left;
			}
			else {
				x = x.right;
			}
		}
		
		if (y == null) {// T???????????´???
		    root = newNode;
			//System.Console.WriteLine("root Assign: {0}",newNode.key); 
		}
		else if (newNode.key < y.key) {
			y.left = newNode; // newNode???y?????????????????????
			//System.Console.WriteLine("insert left: {0} -> {1}",y.key, newNode.key); 
		}
		else {
			y.right = newNode; // newNode???y?????????????????????
			//System.Console.WriteLine("insert right: {0} -> {1}",y.key, newNode.key); 
		}
	}

	public static void Main() {
		var line = System.Console.ReadLine();
		int inputCount = int.Parse(line);
		
		TreeNode root = null;
		ITraverser[] traverser = new ITraverser[2];
		traverser[0] = new MidOrderTraverser();
		traverser[1] = new PreOrderTraverser();
		for (int i = 0; i < inputCount; ++i) {
			line = System.Console.ReadLine();
			string[] input = line.Split(' ');
			switch (input[0]) {
			  case "insert":
				int value = int.Parse(input[1]);
				insert(ref root, new TreeNode(value));
				break;
			  case "print":
				traverser[0].run(root);
				System.Console.WriteLine("");
				traverser[1].run(root);
				System.Console.WriteLine("");
				break;
			  default: //bkyk
				System.Console.WriteLine("What?? readline = {0}", line);
				break;
			}
		}
	}
};

Measured memory_bytes: 40172
#define _USE_MATH_DEFINES
 
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
 
using namespace std;
 
typedef pair<long long int, long long int> P;
long long int INF = 1e18;

#define MAX_V 110000

int N;

struct edge{
	int to;
	long long int cost;
};

vector<edge> G[MAX_V];
long long int d[MAX_V];

// 速さはO(|E|log|V|)

void shortest_path(int s, int V){ // Vは頂点数
	
	priority_queue<P, vector<P>, greater<P> > que;
	
	for(int i = 0; i < V; i++){
		d[i] = INF;
	}
	d[s] = 0;
	
	que.push(P(0, s));
	
	while(!que.empty()){
		
		P p = que.top();
		que.pop();
		
		int v = p.second;
		
		if(d[v] < p.first){
			continue;
		}
		
		for(int i = 0; i < G[v].size(); i++){
			edge e = G[v][i];
			if(d[e.to] > e.cost + d[v]){
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		} // 頂点への最小コストを更新
	}
}

int main(){
	
	cin >> N;
	
	for(int i = 0; i < N; i++){
		int num;
		cin >> num;
		if(num != 0){
			edge e;
			e.to = i + num;
			e.cost = 0;
			G[i].push_back(e);
		}else{
			edge e;
			e.cost = 1;
			e.to = i + 1;
			G[i].push_back(e);
			e.to = i + 2;
			G[i].push_back(e);
			e.to = i + 3;
			G[i].push_back(e);
			e.to = i + 4;
			G[i].push_back(e);
			e.to = i + 5;
			G[i].push_back(e);
			e.to = i + 6;
			G[i].push_back(e);
		}
	}
	
	shortest_path(0, N + 10);
	
	cout << d[N - 1] << endl;
	
	return 0;
}


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

using namespace std;

#define M 1000000007
#define pb push_back
#define f first
#define s second
#define rep(i, st, ed) for(int i=st; i<ed; i++)
#define repn(i, st, ed) for(int i=st; i<=ed; i++)
#define repb(i, ed, st) for(int i=ed; i>=st; i--)

typedef long long ll;
typedef unsigned long long int llt;
typedef long double ld;

const long double PI  =3.141592653589793238463;
const int N = 5e5 + 10;

vector<int> g[N];
bool viss[N];
int vis[N];

// Normal DFS
void dfs(int curr, int par)
{
  for(auto x: g[curr])
    if(x != par)
      dfs(x, curr);
}

// DFS with visiting status
void dfs1(int curr, int par)
{
  viss[curr] = 1;
  for(auto x: g[curr])
    if(!viss[x])
      dfs1(x, curr);
}

// DFS with strongly connected component
void dfs2(int curr, int par, int num)
{
  vis[curr] = num;
  for(auto x: g[curr])
    if(vis[x] == 0)
      dfs2(x, curr, num);
}

// XOR from 0 to n
ll fxor(ll n)
{
  if(n < 0) return 0;
  if(n % 4 == 3) return 0;
  else if(n % 4 == 0) return n;
  else if(n % 4 == 1) return n^(n-1);
  else if(n%4 == 2) return n^(n-1)^(n-2);
}

// Power in logn with mod 1000000007
llt ppow(llt x, llt y)
{
  llt res = 1;
  while(y > 0){
    if(y&1)
      res = (res * x)%M;
    y = y >> 1;
    x = (x * x)%M;
  }
  return res;
}

// Factorial with dp
llt factdp[N];
llt fact(llt x)
{
  if(x == 0) return 1;
  if(x == 1) return 1;
  if(factdp[x] != -1) return factdp[x];
  return factdp[x] = (x*fact(x-1))%M;
}

// String return to base b
string ansConv ="";
void convert10tob(llt N, int b)
{
     if (N == 0)
        return;
     int x = N % b;
     N /= b;
     if (x < 0)
        N += 1;
     convert10tob(N, b);
     ansConv += to_string(x);
     return;
}

// Convert string to num wiht base b
llt convertstrtob(string a, int b)
{
  llt aa = 0;
  llt mul = 1;
  for(int i=a.length()-1; i>=0; i--)
  {
    int curr = a[i] - '0';
    aa += (curr * mul);
    mul *= b;
  }
  return aa;
}

// Union Find algo with array
// Find()
int findpar(int curr, int arr[])
{
  while(arr[curr] != curr) curr = arr[curr];
  return curr;
}
// Union()
void Union(int b, int spa, int arr[])
{
  while(arr[b] != b)
  {
    int c = arr[b];
    arr[b] = spa;
    b = c;
  }
  arr[b] = spa;
}

// Main Code
bool comp(llt a, llt b)
{
  return a>b;
}

ll dp[51][51];

int main()
{
  int n, a, b;
  cin>>n>>a>>b;
  vector<double> v(n);
  rep(i, 0, n)
  {
    cin>>v[i];
  }
  sort(v.begin(), v.end(), greater<double>());
  double sum = 0.0;
  rep(i, 0, a)
    sum += v[i];
  double ans = sum / (double) a;
  cout<<setprecision(10)<<ans<<endl;
  double last = v[a-1];
  int total = 0, taken = 0;
  rep(i, 0, n)
  {
    if(v[a-1] == v[i])
    {
      total++;
      if(i < a) taken++;
    }
  }
  repn(i, 0, n) dp[i][i] = 1;
  rep(i, 0, n)
  {
    dp[i+1][0] = 1;
    rep(j, 1, i+1)
    {
      dp[i+1][j] = dp[i][j] + dp[i][j-1];
    }
  }
  if(v[0] == v[a-1])
  {
    ll ans = 0;
    repn(i, a, b) ans += dp[total][i];
    cout<<ans<<endl;
  }
  else
  {
    cout<<dp[total][taken]<<endl;
  }
  return 0;
}


Measured memory_bytes: 12288
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <map>
#include <numeric>
#include <random>

using namespace std;

const int MOD = 1000000007;
typedef long long ll;

map<ll,int> prime_factor(ll n) {
  map<ll,int> ret;
  for(ll i=2;i*i<=n;i++) {
    while(n%i==0) {
      ret[i]++;
      n/=i;
    }
  }
  if(n!=1) ret[n]=1;
  return ret;
}

const int MAX = 510000;
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;
}

long long FAC(int n){
  return fac[n];
}

int main()
{

  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N,M,ans=1;
  cin>>N>>M;
  COMinit();
  map<ll,int> mp=prime_factor(M);
  for(auto e : mp){
    if(e.second!=0){
      ans *= COM(N-1+e.second,e.second);
      ans %= MOD;
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 12160
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;

namespace AIZU {
	class Program {
		#region Reserve
		static int cin() { return cin(-1); }
		static int cin(int D) {
			string s = Console.ReadLine();
			if (string.IsNullOrEmpty(s))
				return D;
			return int.Parse(s);
		}
		static int[] cins(char spliter) {
			string s = Console.ReadLine();
			if (string.IsNullOrEmpty(s))
				return new int[] { };
			string[] ss = s.Split(spliter);
			int[] Res = new int[ss.Length];
			for (int i = 0; i < ss.Length; i++)
				Res[i] = int.Parse(ss[i]);
			return Res;
		}
		static int[] cins() { return cins(' '); }
		static void print(object j) { Console.WriteLine(j.ToString()); }
		static void print(string j) { Console.WriteLine(j); }
		#endregion
		
		static void Main(string[] args) {
			bool[] used = new bool[26];
			char[] X = Console.ReadLine().ToCharArray();
			bool Res = true;
			foreach (char c in X) {
				int index = c - 97;
				if (used[index]) { Res = false; break; } else used[index] = true;
			}
			print(Res?"yes":"no");
		}
		
	}
}

Measured memory_bytes: 13140
# -*- coding: utf-8 -*-
H, N = map(int, input().split(' '))

lim = float('inf')
powers = [lim for _ in range(H+1)]
powers[0] = 0

for _ in range(N):
    A, B = map(int, input().split(' '))
    for i in range(H):
        if powers[i] != lim:
            if i+A > H:
                powers[H] = min(powers[H], powers[i] + B)
            else:
                powers[i+A] = min(powers[i+A], powers[i] + B)


# print(powers)
print(powers[H])

Measured memory_bytes: 51292
#include <bits/stdc++.h>
typedef long long LL;
#define SORT(c) sort((c).begin(),(c).end())

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

using namespace std;
int main(void)
{
  for(;;){
    int n,m;
    cin >> n >> m;
    if(!n&&!m) return 0;
    int a[100][2],b[100][2];
    REP(i,n) cin >> a[i][0] >> a[i][1];
    REP(j,m) cin >> b[j][0] >> b[j][1];
    if(n==1 && m==1){
      cout << "YES" << endl;
      continue;
    }
    int axmax=0,axmin=1048576,bxmax=0,bxmin=1048576;
    REP(i,n){
      axmax=max(axmax,(a[i][0]));
      axmin=min(axmin,(a[i][0]));
    }
    REP(j,m){
      bxmax=max(bxmax,(b[j][0]));
      bxmin=min(bxmin,(b[j][0]));
    }
    if(axmax<bxmin || axmin>bxmax){
      cout << "YES" << endl;
      continue;
    }
    bool flag=false;
    REP(i,n) REP(j,i){
      if(flag) break;
      LL ho=a[j][0]-a[i][0];
      LL ve=a[j][1]-a[i][1];
      bool aup=true,alo=true,bup=true,blo=true;
      int val=a[i][0]*ve-a[i][1]*ho;
      REP(k,n){
	if(a[k][0]*ve-a[k][1]*ho > val) alo=false;
	if(a[k][0]*ve-a[k][1]*ho < val) aup=false;
      }
      if(!alo&&!aup) continue;
      REP(k,m){
	if(b[k][0]*ve-b[k][1]*ho >= val) blo=false;
	if(b[k][0]*ve-b[k][1]*ho <= val) bup=false;
      }
      if(aup&&blo || alo&&bup){
	flag=true;
      }
    }
    REP(i,m) REP(j,i){
      if(flag) break;
      LL ho=b[j][0]-b[i][0];
      LL ve=b[j][1]-b[i][1];
      bool aup=true,alo=true,bup=true,blo=true;
      int val=b[i][0]*ve-b[i][1]*ho;
      REP(k,n){
	if(a[k][0]*ve-a[k][1]*ho >= val) alo=false;
	if(a[k][0]*ve-a[k][1]*ho <= val) aup=false;
      }
      if(!alo&&!aup) continue;
      REP(k,m){
	if(b[k][0]*ve-b[k][1]*ho > val) blo=false;
	if(b[k][0]*ve-b[k][1]*ho < val) bup=false;
      }
      if(aup&&blo || alo&&bup){
	flag=true;
      }
    }
    if(flag) cout << "YES" << endl;
    else cout << "NO" << endl;
  }
}

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

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

int MOD=1e9+7;
ll INF=1e18;

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

static const int black=1;
static const int white=-1;

int main(){
    while(1){
        int n, m, p; cin>>n>>m>>p;
        if(n==0) return 0;

        int c[20][20][20];
        memset(c, 0, sizeof(c));

        string ans="Draw";
        int sum=0;
        bool f=true;
        for(int i=0; i<p; i++){
            int cx, cy, cz; cin>>cx>>cy;
            cx--, cy--;
            for(int z=0; z<10; z++){
                if(c[cx][cy][z]==0){
                    c[cx][cy][z]=(i%2==0?black:white);
                    cz=z;
                    break;
                }
            }

            for(int z=-1; z<=1; z++){
                for(int j=0; j<9; j++){
                    if(z==0 && j==8) continue;
                    int nx=cx, ny=cy, nz=cz;
                    int cnt=1;
                    for(int k=0; k<10; k++){
                        nx+=dx[j], ny+=dy[j], nz+=z;
                        if(0<=nx && nx<n && 0<=ny && ny<n && 0<=nz && nz<n){
                            if(c[nx][ny][nz]==(i%2==0?black:white)) cnt++;
                            else break;
                        }
                        else break;
                    }
                    nx=cx, ny=cy, nz=cz;
                    for(int k=0; k<10; k++){
                        nx-=dx[j], ny-=dy[j], nz-=z;
                        if(0<=nx && nx<n && 0<=ny && ny<n && 0<=nz && nz<n){
                            if(c[nx][ny][nz]==(i%2==0?black:white)) cnt++;
                            else break;
                        }
                        else break;
                    }

                    if(cnt>=m && f){
                        ans=(i%2==0?"Black":"White");
                        sum=i+1;
                        f=false;
                    }
                }
            }
        }
        cout << ans;
        if(sum!=0) cout << " " << sum;
        cout << endl;

        /*
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                for(int k=0; k<n; k++){
                    cout << c[j][k][i] << " ";
                }
                cout << endl;
            }
        }
        */
    }
}


Measured memory_bytes: 3228
#include<stdio.h>

void insert(int *a,int i,int j){//i番めの要素をj番めの要素のとこに挿入(i,j is index)i>j
    int k,val;
    val = a[i];
    if(i==j){
        return;
    }
    for(k=i;k>j;k+=-1){
        a[k] = a[k-1];
    }
    a[j] = val;
    return;
}

int *insertion_sort(int *a,int size){
    int i,insert_place,val;
    for(i=0;i<size;i++){
        insert_place = i-1;
        while(insert_place>=0 && a[i]<a[insert_place]){
            insert_place += -1;
        }
        insert_place += 1;
        insert(a,i,insert_place);
    }
    return a;
}

int main(void){
    int a[3];
    scanf("%d %d %d",&a[0],&a[1],&a[2]);
    int *b;
    b= insertion_sort(a,3);
    int i,counter=0;
    for(i=0;i<2;i++){
        counter = counter + a[i]-a[i+1];
    }
    printf("%d\n",counter*-1);
    return 0;

}

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

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define REP(i, N) FOR(i, 0, N)
#define RREP(i, N) RFOR(i, N, 0)
#define FILL(A,value) memset(A,value,sizeof(A))
#define endl '\n'

#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define watch(x) cout << (#x) << " is " << (x) << endl
#define pb push_back
#define mp make_pair
#define Pi 3.14159265358979
#define A first
#define B second

typedef long long ll;
typedef vector <int> vi;
typedef vector<ll> vl;
typedef pair <int, int> pi;
typedef pair <ll, int> pl;
typedef pair <ll, ll> pll;
typedef pair <double, double> pd;

//change these according to prob constraints
const int INF = 0x3f3f3f3f;
const int MAX = 100005;
const int MAX1 = 1005;
const int MAX2 = 105;
const int LEN = 105;
const int BASE = 1000000000;
const double EPS = 1e-7;
const int MOD = 1000000007;
//g++ -std=c++11 your_file.cpp -o your_program

ll mypow(ll a, ll b){
	ll ans=1;
	while(b){
		if(b&1)
			ans=(ans*a)%MOD;
		b/=2;
		a=(a*a)%MOD;
	}
	return ans;
}

vi G[2 * MAX];

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ifstream in("");
	ofstream out("");
	clock_t begin = clock();
	int n, q;
	cin >> n >> q;
	REP(i, n - 1){
		int a, b;
		cin >> a >> b;
		G[a].pb(b);
		G[b].pb(a);
	}
	int arr[n + 1];
	FILL(arr, 0);
	while (q--){
		int v, x;
		cin >> v >> x;
		arr[v] += x;
	}
	bool vis[n + 1];
	FOR(i, 1, n + 1) vis[i] = 0;
	queue<int> Q;
	Q.push(1);
	while (!Q.empty()){
		int node = Q.front();
		Q.pop();
		vis[node] = 1;
		for (auto nxt : G[node]){
			if (vis[nxt]) continue;
			arr[nxt] += arr[node];
			Q.push(nxt);
		}
	}
	FOR(i, 1, n + 1){
		cout << arr[i] << endl;
	}
	clock_t end = clock();
    double esecs = double(end - begin) / CLOCKS_PER_SEC;
    //cout << esecs << " seconds" << endl;
	return 0;	
}

Measured memory_bytes: 15732
#![allow(non_snake_case)]
#![allow(unused_imports)]
#![allow(dead_code)]

use proconio::{input, fastout};
use proconio::marker::*;
use whiteread::parse_line;
use std::collections::*;
use num::*;
use num_traits::*;
use superslice::*;
use std::ops::*;

use itertools::Itertools;
use itertools_num::ItertoolsNum;


#[fastout]
fn solve() {
    const MOD: usize = 1_000_000_007;
    const INF: usize = std::usize::MAX;
    
    input!{
        c: char,
    }

    // let alphabet: Vec<char> = (97..97+26).map(|x| std::char::from_u32(x).unwrap()).collect();

    println!("{}", std::char::from_u32(c as u32 +1).unwrap());
}

fn main() {
    solve()
}

#[cfg(test)]
mod test {
    use super::solve;
}


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

int main() {
    while (true) {
        bool seen[100][100] = {false};
        vector<vector<int>> field;
        stack<pair<int, int>> to_visit;
        int cnt = 0;

        int w, h;
        cin >> w >> h;

        if (w == 0 || h == 0) {
            break;
        }

        field.assign(h, vector<int>(w, 0));
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> field[i][j];
            }
        }

        // for (int i = 0; i < h; i++) {
        //     for (int j = 0; j < w; j++) {
        //         if (field[i][j] == 0) {
        //             cout << "^";
        //         }
        //         else {
        //             cout << "O";
        //         }
        //     }
        //     cout << endl;
        // }

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (field[i][j] == 0) {
                    continue;
                }
                if (seen[i][j] == true) {
                    continue;
                }

                cnt++;
                to_visit.push(make_pair(i, j));
                seen[i][j] = true;
                while (to_visit.empty() == false) {
                    pair<int, int> cur_pos = to_visit.top(); to_visit.pop();
                    int cur_h = cur_pos.first;
                    int cur_w = cur_pos.second;
                    for (int dh = -1; dh <= 1; dh++) {
                        for (int dw = -1; dw <= 1; dw++) {
                            if (dh == 0 && dw == 0) {
                                continue;
                            }

                            int next_h = cur_h + dh;
                            int next_w = cur_w + dw;
                            if (next_h < 0 || next_h >= h || next_w < 0 || next_w >= w) {
                                continue;
                            }
                            if (seen[next_h][next_w] == true) {
                                continue;
                            }
                            if (field[next_h][next_w] == 0) {
                                continue;
                            }
                            to_visit.push(make_pair(next_h, next_w));
                            seen[next_h][next_w] = true;
                        }
                    }
                }
            }
        }

        cout << cnt << endl;
    }

    return 0;
}



Measured memory_bytes: 3120
import sys
import bisect
from operator import itemgetter

input = sys.stdin.readline


def main():
    N, D, A = [int(x) for x in input().split()]
    XH = []
    X = []
    R = [0] * (N * 2)
    for _ in range(N):
        x, h = [int(x) for x in input().split()]
        XH.append((x, h))
        XH.append((x + 2 * D + 1, -float("inf")))
        X.append(x)
        X.append(x + 2 * D + 1)

    X.sort()
    XH.sort(key=itemgetter(0, 1))

    ans = 0
    ruiseki = 0

    for i in range(N * 2):
        x, h = XH[i]
        if h != -float("inf"):
            if h > ruiseki:
                tmpruiseki = -(-(h - ruiseki) // A) * A
                ans += -(-(h - ruiseki) // A)
                ruiseki += tmpruiseki
                nx = bisect.bisect_left(X, x + 2 * D + 1)
                if XH[nx][1] == -float("inf"):
                    R[nx] -= tmpruiseki
                else:
                    R[nx + 1] -= tmpruiseki
            else:
                continue
        else:
            ruiseki += R[i]

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 101572
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <math.h>
#include <string>
#include <string.h>
#include <stack>
#include <queue>
#include <vector>
#include <utility>
#include <set>
#include <map>
#include <stdlib.h>
#include <iomanip>

using namespace std;

#define ll long long
#define vi vector<int>
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define pi 3.14159265359


ll gcd(ll a, ll b)
{
	ll c;
	while (a != 0) {
		c = a; a = b % a;  b = c;
	}
	return b;
}

int main() {
	ll N;
	
	cin >> N;
	
	if (N > 999) {
		cout << "ABD";
	}
	else {
		cout << "ABC";
	}
	cin >> N;

	return 0;


}

Measured memory_bytes: 256
import bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()

cnt = 0

for i in range(n - 1, 0, -1):
    for j in range(i - 1, -1, -1):
        base = l[i] - l[j]
        idx = bisect.bisect_right(l, base)
        cnt += max(j - idx, 0)
print(cnt)




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

int main(){
    int r, c;
    cin>>r >>c;
    vector<vector<int> > g(r+1, vector<int>(c+1));
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cin>>g[i][j];
        }
    }
    
    int sum;
    for(int i=0;i<r;i++){
        sum=0;
        for(int j=0;j<c;j++){
            sum+=g[i][j];
        }
        g[i][c]=sum;
    }
    
    for(int j=0;j<c+1;j++){
        sum=0;
        for(int i=0;i<r;i++){
            sum+=g[i][j];
        }
        g[r][j]=sum;
    }
    
    for(int i=0;i<=r;i++){
        for(int j=0;j<=c;j++){
            cout<<g[i][j];
            if(j!=c)cout<<' ';
        }
        cout<<endl;
    }
    return 0;
}



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

int main() {
	string s;
	int n, k;
	cin >> n >> k;
	cin >> s;

	int x = k - 1;
	if (s[x] == 'A') {
		s[x] = 'a';
	} else if (s[x] == 'B') {
		s[x] = 'b';
	} else if (s[x] == 'C') {
		s[x] = 'c';
	}

	cout << s << endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
int arr[n];
int ans[n];
for(int i=1;i<n;i++)  {cin>>arr[i]; ans[i]=0;}
for(int i=1;i<n;i++)   ans[arr[i]]++;
for(int i=1;i<n;i++)  cout<<ans[i]<<endl;
cout<<0;
return 0;
}


Measured memory_bytes: 5204
#include<bits/stdc++.h>
using namespace std;
long long read()
{
	char ch=getchar();long long x=0,ff=1;
	while(ch<'0'||ch>'9') {if(ch=='-') ff=-ff;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*ff;
}
void write(long long aa)
{
	if(aa<0) putchar('-'),aa=-aa;
	if(aa>9) write(aa/10);
	putchar(aa%10+'0');
	return;
}
int n;
long long ans;
int tot,head[200005],nx[400005],to[400005];
int dep[200005][3],sz[200005];
char s[200005];
void jia(int aa,int bb)
{
	tot++;
	nx[tot]=head[aa];
	to[tot]=bb;
	head[aa]=tot;
	return;
}
void dfs(int rt,int fa)
{
	dep[rt][0]=dep[rt][0]=0;dep[rt][2]=n+1;
	if(s[rt]=='1') sz[rt]=1,dep[rt][2]=0;
	for(int i=head[rt];i;i=nx[i])
	{
		int yy=to[i];
		if(yy==fa) continue;
		dfs(yy,rt);
		sz[rt]+=sz[yy];
		int qwq=dep[yy][0]+1;
		if(qwq>dep[rt][0]) dep[rt][1]=dep[rt][0],dep[rt][0]=qwq;
		else if(qwq>dep[rt][1]) dep[rt][1]=qwq;
		if(sz[yy]) dep[rt][2]=min(dep[rt][2],qwq);
	}
	return;
}
void getans(int rt,int fa,int DD)
{
	int mx=max(dep[rt][0],DD),mn=dep[rt][1],alb=dep[rt][2];
	if(DD==mx) mn=dep[rt][0];
	else mn=max(mn,DD);
	if(sz[1]-sz[rt]) alb=min(alb,DD);
	
	if(s[rt]=='1') ans+=mn+1;
	else if(mn+1>alb) ans+=mn-alb+1;
	
	for(int i=head[rt];i;i=nx[i])
	{
		int yy=to[i];
		if(yy==fa) continue;
		int wzp=dep[rt][1]+1;
		if(dep[yy][0]+1!=dep[rt][0]) wzp=dep[rt][0]+1;
		if(max(DD+1,wzp)>dep[yy][0]+1&&sz[yy]) ans++;
		else if(max(DD+1,wzp)<dep[yy][0]+1&&sz[1]-sz[yy]) ans++;
		else if(max(DD+1,wzp)==dep[yy][0]+1) ans++;
		
		getans(yy,rt,max(DD+1,wzp));
	}
	return;
}
int main()
{
	n=read();
	for(int i=1;i<n;++i)
	{
		int x=read(),y=read();
		jia(x,y);jia(y,x);
	}
	scanf("%s",s+1);
	dfs(1,1);
	getans(1,1,0);
	write(ans);
	return 0;
}

Measured memory_bytes: 17024
from math import factorial

MOD = 10**9 + 7

N = int(input())
As = list(map(int, input().split()))

invs = [1] * (N+1)
for x in range(2, N+1):
    invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD

accInvs = [0] * (N+1)
for i, inv in enumerate(invs[1:], 1):
    accInvs[i] = (accInvs[i-1] + inv) % MOD

ans = 0
for i, A in enumerate(As):
    coef = (accInvs[i+1] + accInvs[N-i] - 1) % MOD
    ans += coef * A
    ans %= MOD

factN = factorial(N) % MOD
print(ans*factN % MOD)


Measured memory_bytes: 16044
// Problem : A - Can't Wait for Holiday
// Contest : AtCoder - AtCoder Beginner Contest 146
// URL : https://atcoder.jp/contests/abc146/tasks/abc146_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

//Macros

#define ll long long
#define db long double
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define mi map<int,int>
#define mii map<pii,int>
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define sz(x) (int)x.size()
#define mod 1000000007
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define inf 1e10
#define PI acos(-1.0)
#define int long long
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define N 100005

//Solution

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

signed main(){
    io;
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    int tests;
    //cin>>tests;
    tests = 1;
    while(tests--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 3628
#include<iostream>
#include <iomanip>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include <numeric>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

#define big ((ll)(1e9)+7)

int main()
{
  ll a,b,n;
  cin >> a >> b >> n;
  ll x = min(n,b-1);
  cout << (a*(x))/b - a*((x)/b) << endl;
}


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

int main(){

  int n;
  cin >> n;
  
  int* h = new int[n];
  
  for(int i=0; i<n ; i++){
  	cin>>h[i];
  }
  
  // if you are at stone i
  // min cost to get there 
  // by i-1 or i-2 (whatever will give the min value, choose it)
  
  
  int* dp = new int[n];
  dp[0] = 0;
  dp[1] = abs(h[1]-h[0]);
  
  for(int i=2 ; i<n ; i++){
  	dp[i] = min( dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]));
  }
  
  //for(int i=0 ; i<n ; i++){
  //	cout<<dp[i]<< " ";
  //}
  
  cout<<dp[n-1]<<endl;
  

}



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

 using namespace std;
int N;


int factorial(int n)
{
    int x = 1; // 0! = 1

    for (int i = 1; i <= n; ++i)
        x *= i;

    return x;
}

int order(vector<int>P){
  int sum=0;
  sum++;
  for(int i=0;i<N;i++){
    int count=1;
    for(int j=0;j<i;j++){
      if(P[j]<P[i])count++;
    }
  sum+=(P[i]-count)*(factorial(N-i-1));
  }
  
 
  return sum;
}
int main(){
  cin>>N;
  vector<int>P(N);
  vector<int>Q(N);
  for(int i=0;i<N;i++)cin>>P[i];
  for(int i=0;i<N;i++)cin>>Q[i];
  int a=order(P);
  int b=order(Q);
  //cout<<a<<" "<<b<<endl;
  int ans=a-b;
  if(ans<0)ans*=-1;
  cout<<ans<<endl;
}


Measured memory_bytes: 256