akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>
#define int long long
#define p (int)(1e9 + 7)

int MOD(int a){
	a %= p;
	return a >= 0 ? a : a + p;
}

int power(int a, int N){
	if(N == 0){
		return 1;
	}
	else if(N % 2 == 0){
		return power(MOD(a * a), N / 2);
	}
	else{
		return MOD(a * power(a, N - 1));
	}
}

int inverse(int a){
	return power(a, p - 2);
}

int main(){
	int N, Q, i, j;
	scanf("%lld%lld", &N, &Q);
	int *A = (int *)malloc(sizeof(int) * N);
	for(i = 0; i < N; i++){
		scanf("%lld", &A[i]);
	}
	int **dp = (int **)malloc(sizeof(int *) * N);
	for(i = 0; i < N; i++){
		dp[i] = (int *)malloc(sizeof(int) * N);
		for(j = 0; j < N; j++){
			if(A[i] > A[j]){
				dp[i][j] = 1;
			}
			else{
				dp[i][j] = 0;
			}
		}
	}
	int q, X, Y, inv2 = inverse(2);
	int *subOX = (int *)malloc(sizeof(int) * N);
	int *subOY = (int *)malloc(sizeof(int) * N);
	int *subXO = (int *)malloc(sizeof(int) * N);
	int *subYO = (int *)malloc(sizeof(int) * N);
	int subXY, subYX;
	for(q = 0; q < Q; q++){
		scanf("%lld%lld", &X, &Y);
		X--;
		Y--;
		for(i = 0; i < N; i++){
			subOX[i] = dp[i][X];
			subOY[i] = dp[i][Y];
			subXO[i] = dp[X][i];
			subYO[i] = dp[Y][i];
		}
		subXY = dp[X][Y];
		subYX = dp[Y][X];
		for(i = 0; i < N; i++){
			if(i != X && i != Y){
				dp[i][X] = MOD((subOX[i] + subOY[i]) * inv2);
				dp[i][Y] = MOD((subOX[i] + subOY[i]) * inv2);
				dp[X][i] = MOD((subXO[i] + subYO[i]) * inv2);
				dp[Y][i] = MOD((subXO[i] + subYO[i]) * inv2);
			}
		}
		dp[X][Y] = MOD((subXY + subYX) * inv2);
		dp[Y][X] = MOD((subXY + subYX) * inv2);
/*		printf("dp[%lld]:\n", q);
		for(i = 0; i < N; i++){
			for(j = 0; j < N; j++){
				printf("%lld ", dp[i][j]);
			}
			printf("\n");
		}
		printf("\n");
*/	}
	int ans = 0;
	for(i = 0; i < N; i++){
		for(j = 0; j < N; j++){
			if(i < j){
				ans = MOD(ans + dp[i][j]);
			}
		}
	}
	ans = MOD(ans * power(2, Q));
	printf("%lld\n", ans);
	return 0;
}

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

#define int long long
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}

string table[12]={"C","C#","D","D#","E","F","F#","G","G#","A","A#","B"};

int N,M;
int T[50010];
int S[50010];

bool ok;
bool dfs(int n,int m){
    if(m==M){
        if(N-n<=2){
            ok=true;
            return true;
        }
        return false;
    }
    if(ok)return true;

    //if((N-n+1)/2>M-m+1)return false;
    if(n>0&&(T[n-1]+11)%12==S[m]){
        if(dfs(n-1,m+1)){
            ok=true;
            return true;
        }
    }

    if(n+1<N&&T[n+1]==S[m]){
        if(dfs(n+1,m+1)){
            ok=true;
            return true;
        }
    }
    if(n+2<N&&(T[n+2]+1)%12==S[m]){
        if(dfs(n+2,m+1)){
            ok=true;
            return true;
        }
    }
    return false;
}



void solve(){
    cin>>N>>M;
    string hoge;
    rep(i,N){
        cin>>hoge;
        T[i]=find(table,table+12,hoge)-table;
    }
    rep(i,M){
        cin>>hoge;
        S[i]=find(table,table+12,hoge)-table;
    }

    ok=false;
    if(dfs(-1,0))cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

signed main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int T;cin>>T;
    while(T--)solve();
    return 0;
}

Measured memory_bytes: 5476
#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() {
  ll N;
  cin >> N;
  vector<ll> L(100000, 0);
  ll ans = 0;
  rep(i, N) {
    ll a;
    cin >> a;
    ans += a;
    L[a - 1]++;
  }

  ll Q;
  cin >> Q;
  rep(i, Q) {
    ll b, c;
    cin >> b >> c;
    ans += (c - b) * L[b - 1];
    L[c - 1] += L[b - 1];
    L[b - 1] = 0;
    cout << ans << endl;
  }

  return 0;
}


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

#define ll long long
//~ #define endl '\n'

void solve(){
	cout<<fixed<<setprecision(20);
	int n, k; cin>>n>>k;
	double n_ = n, ans = 0;
	for(int i = 1; i<=n; i++){
		double a = 1.0;
		int b = i;
		while(b < k){
			b = b * 2;
			a = a * 0.5;
		}
		//~ cout<<i<<" "<<(1.0 / n_)<<" "<<a<<endl;
		ans += ((1.0 / n_) * a);
	}
	cout<<ans<<endl;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t = 1; //cin>>t;
	while(t--){
		solve();
	}
	return 0;
}


Measured memory_bytes: 3772
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 1; i <= (n); i++)
#define pb push_back
const int maxn = 400 + 5;
const int INF32 = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7 = 1'000'000'007;
const int MOD9 = 1'000'000'009;

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

int h, w;
char mem[maxn][maxn];
int d[maxn][maxn];
int di[] = {0, -1, 0, 1};
int dj[] = {-1, 0, 1, 0};

void warshall_floyd(int n) 
{
  for (int k = 1; k <= n; k++)    
    for (int i = 1; i <= n; i++) 
      for (int j = 1; j <= n; j++) 
      {  
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
}

int solve()
{
	rep(i,h*w)
	rep(j,h*w)
	{
		if(i != j)
		{
			d[i][j] = INF32;
		}
		else
		{
			d[i][j] = 0;
		}
	}

	rep(i,h)
	rep(j,w)
	{
		if(i == j) continue;
		if(mem[i][j]=='.')
		{
			for(int k = 0; k < 4; k++)
			{
				int ni = i + di[k]; int nj = j + dj[k]; 
				if(ni < 1 || ni > h || nj < 1 || nj > w) continue;
				if(mem[ni][nj] == '.')
				{
					d[(i-1)*w+j][(ni-1)*w+nj] = 1;
					d[(ni-1)*w+nj][(i-1)*w+j] = 1;
				}
			}
		}
		else 
		{
			for(int k = 0; k < 4; k++)
			{
				int ni = i + di[k]; int nj = j + dj[k]; 
				if(ni < 1 || ni > h || nj < 1 || nj > w) continue;	
				d[(i-1)*w+j][(ni-1)*w+nj] = INF32;
				d[(ni-1)*w+nj][(i-1)*w+j] = INF32;
			}
		}
	}

	// for(int i = 1; i <= h*w; i++)
	// {
	// 	for(int j = 1; j <= h*w; j++)
	// 	{
	// 		printf("%d ", d[i][j]);
	// 	}
	// 	cout << endl;
	// }
	// cout << endl;

	warshall_floyd(h*w);

	// for(int i = 1; i <= h*w; i++)
	// {
	// 	for(int j = 1; j <= h*w; j++)
	// 	{
	// 		printf("%d ", d[i][j]);
	// 	}
	// 	cout << endl;
	// }


	int M = 0;
	for(int i = 1; i <= h*w; i++)
		for(int j = 1; j <= h*w; j++)
			if(d[i][j] > M && d[i][j] < INF32) M = d[i][j];
	return M;
}

int main()
{
	cin >> h >> w;
	char s;
	rep(i,h)
	rep(j,w)
	{
		cin >> mem[i][j];
	}

	cout << solve() << endl;
}

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

int main()
{
    int N;
    cin >> N;
    vector<int> V(N, 0);
    vector<int> C(N, 0);

    for(auto && v: V){
        cin >> v;
    }
    for(auto && c: C){
        cin >> c;
    }

    int max_v = 0;
    for (int i = 0; i < N; ++i){
        if( V[i] - C[i] > 0)
            max_v += V[i] - C[i];
    }

    cout << max_v << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A,B;
  cin >> A >> B;
 
  if (A <= 5){
    cout << 0 << endl;
  }
  else if (A >= 13){
    cout << B << endl;
  }
  else {
    cout << B/2 << endl;
  }
}  


Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))

S = [0]
for i in range(N):
        S.append(S[i]+A[i])

a = 1
c = 3
ans_tmp = []
for b in range(2,N-1):
        while abs(S[b]-S[a]-S[a]) > abs(S[b]-S[a+1]-S[a+1]):
                a += 1

        while abs((S[N]-S[c]) - (S[c]-S[b])) > abs((S[N]-S[c+1]) - (S[c+1]-S[b])):
                c += 1

        ans_tmp.append(max(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0])-min(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0]))

print(min(ans_tmp))

Measured memory_bytes: 31044
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, m, n) for(int i = (m); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1e9)
#define PI (acos(-1))
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl

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

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

template<class T> inline auto __lcm(T& a, T& b) 
{ return a * b / __gcd(max(a, b), min(a, b)); }


int main() {
    int N;  cin >> N;
    vector<ll> A(N);  rep(i, N) cin >> A[i];

    vector<ll> B(N);
    rep(i, N) {
        B[i] = A[i] - (i+1);
    }

    sort(all(B));
    ll ans = 0;
    rep(i, N) {
        ans += abs(B[i] - B[(N-1)/2]);
    }
    print(ans);
}


Measured memory_bytes: 3456
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;

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

    vector<int> cnt(20, 0);

    long long ans = 0;
    int cur = 0;
    int l = 0;
    for(int r=0; r<N; r++){
        for(int i=0; i<20; i++)
            if(A[r] & (1<<i))
                cnt[i]++;

        while(true){
            bool ok = true;
            for(int i=0; i<20; i++)
                if(cnt[i] > 1){
                    ok = false;
                    break;
                }
            if(ok) break;
            else{
                for(int i=0; i<20; i++)
                    if(A[l] & (1<<i))
                        cnt[i]--;
                l++;
            }
        }
        ans += r - l + 1;
    }
    cout << ans << endl;
    return 0;
}

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

namespace abc107_a
{
    class Program
    {
        static void Main(string[] args)
        {
            string []Ni = Console.ReadLine().Split(' ');
            int N = Convert.ToInt32(Ni[0]);
            int i = Convert.ToInt32(Ni[1]);
            Console.WriteLine(N - i + 1);
            Console.ReadLine();
        }
    }
}


Measured memory_bytes: 11220
#include <iostream>
#include <stdio.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>

using namespace std;
int main(){
	int n;
	while(1){
		cin >> n;
		if(n == 0) break;
		long long int a[5000], sum = 0, hold = 0;
		for(int i = 0;i < n;i++){
			cin >> a[i];
		}
		hold = a[0];
		for(int i = 0;i < n;i++){
			for(int j = i;j < n;j++){
				sum += a[j];
				if(hold < sum){
					hold = sum;
				}
			}
			sum = 0;
		}
		cout << hold << endl;

	}
	
	return 0;
}

Measured memory_bytes: 1192
#include <bits/stdc++.h>
//#define DEBUG
#define REP(i, nn ) for(int i = 0 ; i < (int) nn; i++)
#define deb(x) std::cerr << #x << " " << x << endl;
#define debl(x) std::cerr << #x << " " << x << " ";
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
//const ll LINF = 1001002003004005006ll;
//const int INF = 1001001001;
template<typename... T>
void read(T& ... a){
    ((cin >> a),...);
}
template<typename... T>
void write(T... a){
    ((cout << a << "\n"),...);
}

template<typename... T>
void write_space(T... a){
    ((cout << a << " "),...);
}
// constexpr int MOD = 1e9 + 7;
constexpr int mxN = 3000;
double dp[mxN][mxN];
void solve(){
    int n;
    read(n);
    vector<double> p(n+1);
    REP(i,n){
        cin >> p[i+1];
    }
    dp[1][1] = p[1];
    dp[1][0] = 1 - p[1];
    for(int i = 2; i <= n ; i++){
        dp[i][0] = dp[i-1][0] * (1-p[i]);
        for(int j = 1; j < i ; j++){
            dp[i][j] = dp[i-1][j] * ( 1 - p[i]) + dp[i-1][j-1] * p[i];
        }
        dp[i][i] = dp[i-1][i-1] * p[i];
    }
    double ans = 0;
    for(int i = n ; n - i < i ; i--){
        ans += dp[n][i];
    }
    cout << setprecision(10) <<  ans << endl;
}

int main()
{
    //making data IO Fast
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    /****************************/
    solve();
    return 0;
}



Measured memory_bytes: 49940
#include <stdio.h>

int main(void) {
	int base_n, mid_n, q;
	int a, v, b;
	int index, value, end, i, k;

	scanf("%d %d", &base_n, &q);

	int base[base_n];
	for (i = 0; i < base_n; i++) {
		base[i] = 0;
	}

	mid_n = (base_n / 1000) + 1;
	int midway[mid_n];
	for (i = 0; i < mid_n; i++) {
		midway[i] = 0;
	}

	while (q--) {
		scanf("%d %d", &a, &v);
		a--;

		base[a] += v;

		b = a - a % 1000;

		index = b;
		value = base[index];
		end = (b + 1000) < base_n ? (b + 1000) : base_n;
		for (i = b; i < end; i++) {
			if (value < base[i]) {
				value = base[i];
				index = i;
			}
		}
		midway[b/1000] = index;

		index = midway[0];
		value = base[index];
		for (i = 0; i < mid_n; i++) {
			k = midway[i];
			if (value < base[k]) {
				value = base[k];
				index = k;
			}
		}

		printf("%d %d\n", index+1, value);
	}
	return 0;
}

Measured memory_bytes: 4504
h, w = map(int, input().split())
n = int(input())
a = list(map(int, input().split()))
ans = [[] for i in range(h)]
inc = True
r = 0
for i in range(n):
    while(a[i] > 0):
        if(inc):
            if(r <= h - 1):
                ans[r].append(i + 1)
                r += 1
            else:
                r = h - 1
                ans[r].append(i + 1)
                r -= 1
                inc = False
        else:
            if(r >= 0):
                ans[r].append(i + 1)
                r -= 1
            else:
                r = 0
                ans[r].append(i + 1)
                r += 1
                inc = True
        a[i] -= 1
for x in ans:
    for i in x:
        print(i, end = " ")
    print()



Measured memory_bytes: 46040
if !ENV['RUBY_THREAD_VM_STACK_SIZE']
  exec({'RUBY_THREAD_VM_STACK_SIZE'=>'1000000000'}, '/usr/bin/ruby', $0)
else
  # util functions

  # debug
  $debugFlag = ( ARGV[0] != nil )
  p "==== DEBUG MODE ====" if $debugFlag

  def pd(str)
    p str if $debugFlag
  end

  # input
  inputs = []
  lc = 0
  l = $stdin.gets
  while l = $stdin.gets do
    if false
      inputs << l.chomp.split(" ").map(&:to_s)
    else
      inputs << l.chomp.split(" ").map(&:to_i)
    end
    lc += 1
  end

  # input check
  if $debugFlag
    p "--- INPUT (begin) ---"
    inputs.each do |l_i|
      p l_i
    end
    p "--- INPUT (end) ---"
    print "\n"
  end

  # body

  seq = inputs[0]
  nseq = []
  pre = nil
  seq.length.times do |i|
    nseq << seq[i] if seq[i] != pre
    pre = seq[i]
  end

  pd "nseq: #{nseq}"

  def proc( arr, cnt )
    if arr.size == 1
      return cnt
    end
    
    mono_incr = (arr[0] < arr[1])

    idx = 0
    idx_max = arr.size - 1
    while idx < idx_max do
      if (mono_incr and arr[idx] < arr[idx + 1]) or (!mono_incr and arr[idx] > arr[idx + 1])
        idx += 1
      else
        break
      end
    end

    if idx == idx_max
      return cnt
    else
      return proc( arr[idx + 1..-1], 1 + cnt )
    end
  end

  puts proc( nseq, 1 )
end


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

using namespace std;

int n, sum;
bitset<4000010> dp;

int main()
{
	ios::sync_with_stdio(false);
	cin >> n;
	dp.set(0);
	for (int i = 1; i <= n; i++)
	{
		int x; cin >> x;
		sum += x;
		dp |= (dp << x);
	}
	for (int i = (sum + 1) / 2; ; i++)
		if (dp[i])
		{
			cout << i << endl;
			break;
		}
	return 0;
}


Measured memory_bytes: 1792
#define DIN freopen("input.txt","r",stdin);
#define DOUT freopen("output.txt","w",stdout);
#include <bits/stdc++.h>
#include <cstdio>
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define REP_(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
using namespace std;
typedef long long LL;
typedef std::vector<int> VI;
typedef std::pair<int,int> P;
int read()
{
    int x=0,flag=1; char c=getchar();
    while((c>'9' || c<'0') && c!='-') c=getchar();
    if(c=='-') flag=0,c=getchar();
    while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return flag?x:-x;
}

char s[1005],t[1005];

int main()
{
    scanf("%s %s",s+1,t+1);
    int ns=strlen(s+1),nt=strlen(t+1);
    int ans=1e9;
    for(int i=1;i+nt-1<=ns;i++)
    {
        int cnt=0;
        for(int j=i,k=1;k<=nt;k++,j++)
            if(s[j]!=t[k])
                cnt++;
        ans=min(ans,cnt);
    }
    cout<<ans;

    return 0;
}


Measured memory_bytes: 3760
def solve():
  N, M, X, Y = map(int, input().split())
  x = list(map(int, input().split()))
  y = list(map(int, input().split()))

  x = sorted(x)
  y = sorted(y)
  
  if x[-1] < y[0]:
    # Zが存在する
    if X < y[0] <= Y:
      print('No War')
    else:
      print('War')
  else:
    print('War')


solve() 

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

int output(vector<int> A, int N) {
  for (int i = 0; i < N; i++) {
    if (i == N - 1) {
      cout << A.at(i) << endl;
    } else {
      cout << A.at(i) << " ";
    }
  }
}

int insertionSort(vector<int>A, int N) {
  int v, j;

  for (int i = 0; i < N; i++) {
    v = A.at(i);
    j = i - 1;

    while (j >= 0 && A.at(j) > v) {
      A.at(j + 1) = A.at(j);
      j--;
    }

    A.at(j + 1) = v;

    output(A, N);
  }
}

int main() {
  int N;
  vector<int> A(N);

  cin >> N;

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

  insertionSort(A, N);
}



Measured memory_bytes: 3284
N, K = map(int, input().split())
MOD = 10**9 + 7
 
if N < K:
    print(0)
else:
    p = q = 1
    for i in range(N-K):
        p = p * (N-1-i) % MOD
        q = q * (i+1) % MOD
 
    print(p * pow(q, MOD-2, MOD) % MOD)


Measured memory_bytes: 5596
n,m = list(map(int,input().split()))
bridge = list()
for i in range(0,m):
    bridge.append(list(map(int,input().split())))

ans = list()
ans.append(n*(n-1)/2)
size = [1 for i in range(0,n+1)]

tree = [i for i in range(0,n+1)]

def find(x):
    if tree[x] == x:
        return x
    else:
        tree[x] = find(tree[x])
        return tree[x]

def unite(x,y):
    fx = find(tree[x])
    fy = find(tree[y])
    if fx > fy:
        fx,fy = fy,fx
    d = size[fx]*size[fy]
    size[fx] += size[fy]
    size[fy] = 0
    tree[fy] = fx
    return d

for i in reversed(range(0,m)):
    de = 0
    if find(bridge[i][0]) != find(bridge[i][1]):
        de = unite(bridge[i][0],bridge[i][1])
        ans.append(ans[m-i-1]-de)
    else:
        ans.append(ans[m-i-1])

for i in reversed(range(0,m)):
    print(int(ans[i]))

Measured memory_bytes: 36500
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
	int w;
	while (cin >> w)
	{
		if (w < 0) break;
		if (w <= 10)		cout << 3130 << endl;
		else if (w <= 20)	cout << 3130 - (w-10) * 125 << endl;
		else if (w <= 30)	cout << 1880 - (w-20) * 140 << endl;
		else				cout << 480 - (w-30) * 160 << endl;
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int previous_rate;
  int goal_rate;
  int required_rate;
  cin >> previous_rate;
  cin >> goal_rate;
  //goal_rate = (previous_rate + required_rate)/2
  //required_rate = 2*goal_rate - previous_rate
  required_rate = 2*goal_rate - previous_rate;
  
  cout << required_rate << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include<string.h>
int main()
{
    char s[101];
    int k;
    scanf("%s",s);
    scanf("%d",&k);
    int n=strlen(s);

    int start=1;
    int end=1;
    int count=1;
    int subtotal=0;
    long long int total=0;
    for ( start = 1; start < n; start++)
    {
        if(s[start-1]!=s[start])break;
    }
    if(start==n)
    {
        total=(long long int)n*k/2;
        printf("%lld\n",total);
        return 0;
    }
    for ( end = 1; end < n; end++)
    {
        if(s[n-end]!=s[n-end-1])break;
    }

    if(s[0]==s[n-1])
    {
        total+=(long long int)((start+end)/2)*(k-1)+start/2+end/2;

    }
    else
    {
        total+=(long long int)(start/2+end/2)*k;

    }
    for (int i = start; i <= n-end-1; i++)
    {
        if(s[i]==s[i+1])count++;
        else
        {
            subtotal+=count/2;
            count=1;
        }
    }

    total+=(long long int)subtotal*k;
    printf("%lld\n",total);
    return 0;   
}

Measured memory_bytes: 128
#include <stdio.h>
#define S 100

int main(void)
{
    int n, i, N[S], c=0, temp;
    int flag=1;
    scanf("%d", &n);
    for(i=0; i<n; i++) scanf("%d", &N[i]);
    while(flag){
        flag=0;
    for(i=n-1; i>0; i--)
    {
        if(N[i]<N[i-1]){
            temp=N[i];
            N[i]=N[i-1];
            N[i-1]=temp;
            c++;
            flag=1;
        }
    }
    }
    for(i=0; i<n; i++){
        if(n-1==i) printf("%d\n", N[i]);
        else printf("%d ", N[i]);
    }
    printf("%d\n", c);
    return 0;
}


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

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

  vector<int> D(N); // N個の数学の点数データ
  int height = 1;
    
  // 数学の点数データを受け取る
  for (int i = 0; i < N; i++) {
    cin >> D.at(i);
  }

  
  sort(D.begin(), D.end());
  for (int i = 0; i < N-1; i++) {
    if (D.at(i) != D.at(i+1)) height++;
  }
  
  cout << height << endl;
}


Measured memory_bytes: 3540
#!/usr/bin/perl

use strict;
use warnings;

my @s;
{
    my $in = <STDIN>;
    @s = split("", $in);
}
my $n = @s+1;
my @v;
{
    for (my $i=0; $i<$n; $i++)
    {
        $v[$i] = 0;
    }
}
my $c = 0;
for (my $i=0; $i<$n-1; $i++)
{
    if ($s[$i] eq '<')
    {
        $v[$i] = $c;
        $c++;
        $v[$i+1] = $c;
    }
    else
    {
        $c = 0;
    }    
}
$c = 0;
@s = reverse(@s);
@v = reverse(@v);
for (my $i=0; $i<$n-1; $i++)
{
    if ($s[$i] eq '>')
    {
        $v[$i] = $c;
        $c++;
        if ($v[$i+1]<=$c)
        {
            $v[$i+1] = $c;
        }
    }
    else
    {
        $c = 0;
    }    
}
@s = reverse(@s);
@v = reverse(@v);

my $ans = 0;
for (my $i=0; $i<$n; $i++)
{
    $ans += $v[$i];
}
print $ans."\n";

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

typedef long long ll;
typedef long double ld;
typedef vector<vector<int>> Graph;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
#define pi 3.14159265359
#define inf 2147483647
#define INF 9223372036854775807
#define mod 1000000007
#define mod2 998244353

int main() {
	string w; cin >> w;
	map<char, int> m;
	string ans = "Yes";
	for(int i = 0; i < w.size(); i++) {
		if(!m.count(w[i])) m[w[i]] = 1;
		else m[w[i]]++;
	}
	for(auto p: m) {
		if(p.second % 2 != 0) ans = "No";
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3608
/*
 * @Author: Kaizyn
 * @Date: 2020-03-22 19:58:48
 * @LastEditTime: 2020-03-22 20:14:00
 */
#include <bits/stdc++.h>

// #define DEBUG

using namespace std;

const int N = 2e5+7;
const int MOD = 1e9+7;
const double eps = 1e-7;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;

int n;
int a[N], t[N];

inline void solve()
{
    cin >> n;
    long long res = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        ++t[a[i]];
    }
    for (int i = 1; i <= n; ++i) {
        res += t[i]*(t[i]-1ll)/2;
    }
    for (int i = 1; i <= n; ++i) {
        if (t[a[i]] <= 1) {
            cout << res << endl;
        } else {
            cout << res-t[a[i]]*(t[a[i]]-1ll)/2+(t[a[i]]-1ll)*(t[a[i]]-2ll)/2 << endl;
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int testcase = 1;
    // cin >> testcase;
    for (int i = 1; i <= testcase; ++i) {
        solve();
    }
    return 0;
}

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

typedef long long ll;
typedef pair<int,int> P;
int dx[] = {-1, 1, 0,  0};
int dy[] = { 0, 0, 1, -1};

 
int main(){
  ll a, b;
  cin >> a >> b;
  ll anum, bnum;
  if(a==0){
    switch(b%4){
      case 0:
        bnum = b;
        break;
      case 1:
        bnum = 1;
        break;
      case 2:
        bnum = 1^b;
        break;
      case 3:
        bnum = 0;
        break;
      default:
        break;
    }
    cout << bnum << endl;
    return 0;
  }
  switch((a-1)%4){
    case 0:
      anum = a-1;
      break;
    case 1:
      anum = 1;
      break;
    case 2:
      anum = 1^a-1;
      break;
    case 3:
      anum = 0;
      break;
    default:
      break;
  }
  switch(b%4){
    case 0:
      bnum = b;
      break;
    case 1:
      bnum = 1;
      break;
    case 2:
      bnum = 1^b;
      break;
    case 3:
      bnum = 0;
      break;
    default:
      break;
  }
  ll ans = anum^bnum;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3640
import java.util.ArrayDeque;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = Integer.parseInt(sc.nextLine());
    String s = sc.nextLine();
    sc.close();
    int i = 0;
    int count = 0;
    while (i < n) {
      char head = s.charAt(i++);
      while (i < n && s.charAt(i) == head) i++;
      count++;
    }
    System.out.println(count);
  }
}

Measured memory_bytes: 27988
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define RREP(i,n) for(int (i)=(int)(n)-1;i>=0;i--)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
typedef long long ll;


int main () {

    int N; cin >> N;
    vector < int > a(N);
    REP(i,N) cin >> a[i];

    vector < int > sub;
    int cnt = 0;
    int col = -1;
    REP(i,N) {
        if (col != a[i]) {
            if (i != 0) {
                sub.push_back(cnt);
            }
            cnt = 1;
            col = a[i];
            if (i == N - 1) {
                sub.push_back(cnt);
            }
        } else {
            cnt++;
            if (i == N - 1) {
                sub.push_back(cnt);
            }
        }
    }

    int ans = 0;
    REP(i,sub.size()) {
        ans += sub[i] / 2;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
H, W = map(int, input().split())

A = []
for i in range(H):
    s = input()
    if '#' in s:
        A.append(list(s))

H = len(A)
B = []
for i in range(W):
    s = []
    for j in range(H):
        s.append(A[j][i])
    if "#" in s:
        B.append(s)

W = len(B)
for i in range(H):
    s = ""
    for j in range(W):
        s += B[j][i]
    print(s)


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

int main() {
    string s;
    cin >> s;
    
    if((s[2] == s[3]) && (s[4] == s[5]))
    {
        cout << "Yes" << endl;
    }
  	else
    {
      cout << "No" << endl;
    }
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <limits>
#include <climits>
#include <utility>
#include <algorithm>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

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

    vector<int> A(N);
    vector<int> B(N);
    vector<int> C(N-1);

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

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

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

    int ans = 0;
    for (int i = 0; i < N; ++i) {
        ans += B[i];
    }

    for (int i = 0; i < N-1; ++i) {
        if (A[i+1] == A[i] + 1) {
            ans += C[A[i]];
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 888
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
	int targ, square[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
	vector<int> num;
	while(cin >> targ)
	{
		if(targ == 0) break;

		for(int i = 9; i >= 0; i--)
		{
			if(targ >= square[i])
			{
				num.push_back(i);
				targ -= square[i];
			}
		}

		for(int i = num.size()-1; i >= 0; i--)
		{
			cout << square[ num[i] ];
			if(i != 0) cout <<" ";
			else cout << endl;
		}
		num.clear();
	}
}

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

/*
一回しか下にいけないので、どのタイミングでしたに行くかを考えればよい。
it is O(N).
*/

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

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

    int maxv = 0;
    for (int i = 0; i < N; i++)
    {
        int sum = 0;
        for (int t = 0; t <= i; t++)
        {
            sum += A[0][t];
        }

        for (int j = i; j < N; j++)
        {
            sum += A[1][j];
        }

        maxv = max(maxv, sum);
    }
    cout << maxv << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<sstream>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<cmath>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<numeric>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};

int main()
{

    int N,K;
    cin >> N  >> K;
    int h[N];
    for (int i=0; i<N; ++i)
    {
        cin >> h[i];
    }
    int dp[N+K];
    for (int i=0; i<N; ++i)
    {
        dp[i] = inf;
    }

    dp[0] = 0;
    for (int i=0; i<N; ++i)
    {
        for (int k=1; k<K+1; ++k)
        {
            if (dp[i+k] > (dp[i] + abs(h[i+k]-h[i])))
            {
                dp[i+k] = dp[i] + abs(h[i+k]-h[i]);
            }
        }
    }

    cout << dp[N-1] << endl;
    return 0;
}

Measured memory_bytes: 1024
// Author: getharshkumar

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const ll N = 1e6 + 6, M = 1e9 + 7;
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    ll n, a, b;
    cin >> n >> a >> b;
    cout << min(n * a, b);
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;

using namespace std;
#define N 55
ll s[N],c[N];
ll f(ll n,ll x){
    if(n==0)return 0;
    if(x==0)return 0;
    else if(x==1)return 1;
    else if(x<=1+s[n-1])return 1+f(n-1,x-1);
    else if(x==2+s[n-1])return 1+c[n-1];
    else if(x<=2+2*s[n-1])return 1+c[n-1]+f(n-1,x-(2+s[n-1]));
    else return c[n];
}
int main(){
    s[0]=1;
    lol(i,N-1)s[i+1]=s[i]*2+3;
    c[0]=0;
    lol(i,N-1)c[i+1]=c[i]*2+2;
    ll n,x;cin>>n>>x;
    cout<<x-f(n,x)<<endl;
    return 0;
}


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

int descending_compare(const void *a, const void *b){
    if (*(int*)a > *(int*)b){
        return -1;
    }else if (*(int*)a == *(int*)b){
        return 0;
    }else{
        return 1;
    }
}

int ascending_compare(const void *a, const void *b){
    if (*(int*)a < *(int*)b){
        return -1;
    }else if (*(int*)a == *(int*)b){
        return 0;
    }else{
        return 1;
    }
}


int lower_bound(int *a, int n, int key){
    int left, mid, right;
    left = 0, right = n;
    mid = (left + right)/2;
    while ((left+1 != mid || mid+1 != right) && mid != left){
        if (key > a[mid]){
            left = mid;
        }else{
            right = mid+1;
        }
        mid = (left + right)/2;
    }
    if (a[left] >= key)return left;
    if (a[mid] >= key)return mid;
    if (a[right] >= key)return right;
    return n;
}

unsigned long  gcd(unsigned long x, unsigned long y)
{
        if (y == 0) {
                return x;
        } else {
                return gcd(y, x % y);
        }
}

long long kaijou(int x){
    long long rtn = 1;
    int i;
    for (i = x; i > 1; i--){
        rtn = (rtn*i);
    }
    return rtn;
}


int main(void){
    int n;
    int d[105];
    int i;
    int cnt = 1;
    scanf("%d", &n);
    for (i = 0; i < n; i++){
        scanf("%d", &d[i]);
    }
    qsort(d, n, sizeof(int), descending_compare);
    for (i = 0; i < n-1; i++){
        if (d[i] > d[i+1]){
            cnt++;
        }
    }

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


}


Measured memory_bytes: 128
#include <iostream>
using namespace std;
int main()
{
	int e[8] = {0}, i;
	double l, r;
	while (cin >> l)
	{
		if (cin.eof()) break;
		cin >> r;
		if (l >= 1.1)		e[0]++;
		else if (l >= 0.6)	e[2]++;
		else if (l >= 0.2)	e[4]++;
		else				e[6]++;
		if (r >= 1.1)		e[1]++;
		else if (r >= 0.6)	e[3]++;
		else if (r >= 0.2)	e[5]++;
		else				e[7]++;
	}
	for (i = 0; i < 4; i++)
	{
		cout << e[i*2] << " " << e[i*2+1] << endl;
	}
}

Measured memory_bytes: 0
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int map[10][10];
int vis[10];
int n,m,sum;
void dfs(int x,int num)
{
	if(num==n)
	{
		sum++;
		return;
	}
	vis[x]=1;
	for(int i=1;i<=n;i++)
	{
		if(vis[i]==0&&map[x][i]==1)
		{
			vis[i]=1;
			map[x][i]=0;
			dfs(i,num+1);
			vis[i]=0;
			map[x][i]=1;
		}
	}
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(map,0,sizeof(map));
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=m;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			map[a][b]=1;
			map[b][a]=1;
		}
		sum=0;
		dfs(1,1);
		printf("%d\n",sum);
	}
	return 0;
}

Measured memory_bytes: 256
require 'prime'
require 'set'
require 'tsort'
include Math
ALP = ('a'..'z').to_a
INF = 0xffffffffffffffff
def max(a,b);              a > b ? a : b                              end
def min(a,b);              a < b ?  a : b                             end
def swap(a,b);             a, b = b, a                                end
def gif;                   gets.to_i                                  end
def gff;                   gets.to_f                                  end
def gsf;                   gets.chomp                                 end
def gi;                    gets.split.map(&:to_i)                     end
def gf;                    gets.split.map(&:to_f)                     end
def gs;                    gets.chomp.split.map(&:to_s)               end
def gc;                    gets.chomp.split('')                       end
def pr(num);               num.prime_division                         end
def pr?(num);              Prime.prime?(num)                          end
def digit(num);            num.to_s.length                            end
def array(s,ini=nil);      Array.new(s){ini}                          end
def darray(s1,s2,ini=nil); Array.new(s1){Array.new(s2){ini}}          end
def rep(num);              num.times{|i|yield(i)}                     end
def repl(st,en,n=1);       st.step(en,n){|i|yield(i)}                 end

a,b,c = gi

puts case
when a == b
  c
when a == c
  b
when b == c
  a
end


Measured memory_bytes: 2300
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  vector<int> f(n,0);
  for (int x = 1; x < 100; x++)
  {
    for (int y = 1; y < 100; y++)
    {
      for (int z = 1; z < 100; z++)
      {
        int w = x*x+y*y+z*z+x*y+y*z+z*x;
        if (w <= n)
        {
          f[w-1]++;
        }else
        {
          break;
        }
        
        
      }
      
    }
    
  }
  for (int i = 0; i < n; i++)
  {
    cout << f[i] <<endl;
  }
  
  return 0;
}

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

constexpr int si = 1001 * 1001;
int n, m, k, ar[500][500], pos[500], cnts[500], av_sport[500], ba[500];

int sol() {
   if (1 == n) return 1;
   if (1 == m) return n;

   int ret = 0;
   for (int i = 1; i <= n; i++) pos[i] = 1;
   for (int i = 1; i <= m; i++) av_sport[i] = 1;

   {//init
      for (int p = 1; p <= n; p++) {
         const auto& sp = ar[p][1];
         ret = max(ret, ++cnts[sp]);
      }
   }

   for (;;) {
      int cand = 0, cn=0;
      for (int j = 1; j <= m; j++) {
         if (ret <= cnts[j]) {
            ba[cn++] = j; av_sport[j] = 0; cnts[j] = 0;
         }
      }
      for (int i = 1; i <= n; i++) {
         int &po = pos[i];
         int sp = ar[i][po];
         if (0 == av_sport[sp]) {
            while (0 == av_sport[sp]) {
               if (n < ++po)
                  return ret;
               sp = ar[i][po];
            }
            ++cnts[sp];
         }
      }
      for (int i = 1; i <= m; i++) {
         cand = max(cand, cnts[i]);
      }

      ret = min(ret, cand);
   }
}

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

   while (cin >> n >> m)
   {
      for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> ar[i][j];
      memset(cnts, 0, sizeof cnts);
      int s = sol();
      cout << s << '\n';
   }
   return 0;
}

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

/* 大文字を小文字に変換 */
char tolower(char c) {return (c + 0x20);}
/* 小文字を大文字に変換 */
char toupr(char c) {return (c - 0x20);}

// if('A'<=s[i] && s[i]<='Z') s[i] += 'a'-'A';

/*
string s = "abcdefg"
s.substr(4) "efg"
s.substr(0,3) "abc"
s.substr(2,4) "cdef"

// イテレータ要素のインデックス
distance(A.begin(), itr);
*/

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

    int ans = 0;
    for(char c1='0'; c1<='9'; c1++){
        for(char c2='0'; c2<='9'; c2++){
            for(char c3='0'; c3<='9'; c3++){
                int cnt = 0;
                rep(i,n){
                    if(cnt == 0 && s[i] == c3){
                        cnt++;
                        continue;
                    }else if(cnt == 1 && c2 == s[i]){
                        cnt++;
                        continue;
                    }else if(cnt == 2 && c1 == s[i]){
                        cnt++;
                        break;
                    }
                }
                if(cnt == 3) ans++;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3664
#include<iostream>
#include<vector>
#define _USE_MATH_DEFINES
#include<math.h>
#include<algorithm>
#include<memory>
#include<string>
typedef long long ll;
#define Rep(i,n) for(int i = 0;i < (n);i++)	

int gcd(int a, int b) { if (b == 0)  return a;  else  return gcd(b, a % b);  }
int lcm(int a, int b) { return a * b / gcd(a, b); }
void swap(int& a, int& b) { int temp = a; a = b; b = temp; return; }
int ncr(int n, int r) { int a = 1; Rep(i, r) a = (a * (n - i)) / (i + 1); return a; }
int npr(int n, int r) { int a = 1; Rep(i, r) a *= n - i; return a; }
int mod(int a, int b) { return a % b; }

int main() {
	/*double a;
	std::cin >> a;
	printf("%10.10f", 2 * a * M_PI);*/

	int n, m;
	std::vector<int> A;
	std::cin >> n >> m;
	int sum = 0;
	Rep(i, m) {
		int k;
		std::cin >> k;
		sum += k;
	}
	if (sum <= n) {
		std::cout << n - sum << std::endl;
	}
	else {
		std::cout << -1 << std::endl;
	}
	return 0;
}

Measured memory_bytes: 3672
sd = input()
t = input()
lsd = len(sd)
lt = len(t)
for i in range(lsd-lt,-1,-1):
  for j in range(lt):
    if sd[i+j] != "?" and sd[i+j] != t[j]:
      break
  else:
      print((sd[:i]+t+sd[i+lt:]).replace("?","a"))
      break
else:
  print("UNRESTORABLE")


Measured memory_bytes: 3064
if __name__ == "__main__":
    n = int(input())
    s = input()

    if n == 2:
        if s[0] == s[1]:
            print(1)
            exit()
        else:
            print(0)
            exit()

    ans = 0
    for i in range(1, n):
        front = set(s[0:i])
        back = set(s[i:n])

        tmp = 0
        for f in front:
            if f in back:
                tmp += 1
        if ans < tmp:
            ans = tmp

    print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define rep(i,n); for(long long i = 0;i < (n);i++)
using ll = long long;
using P = pair<long long,long long>;
template <class T> using vec = vector<T>;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n; cin >> n;
    ll f[100005];
    for(ll i = 1;i<=n;i++){
        for(ll j = i;j<=n;j++){
            for(ll k = j;k<=n;k++){
                ll r = i*i + j*j + k*k + i*j + j*k + k*i;
                if(r > n)break;
                if(i == j && i == k)f[r]++;
                else if(i == j || j == k || k == i)f[r] += 3;
                else f[r] += 6;
            }
        }
    }
    rep(i,n)cout << f[i+1] << endl;
}

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

#define ll long long
#define pb push_back
#define endl '\n'
#define fcin ios::sync_with_stdio(false); cin.tie(nullptr);
#define inf 0x3f3f3f3f

int main(){
    fcin;
    ll r, d, x2k;
    cin >> r >> d >> x2k;
    for(int i = 0; i < 10; i++){
        ll ans = r*x2k - d;
        cout << ans << endl;
        x2k = ans;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int mod=1000000007;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repl(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define reprl(i, n) for(ll i = n; i >= 0; i--)
#define fori(i, m, n) for(int i = m; i < (int)n; i++)
#define forl(i, m, n) for(ll i = m; i < (ll)n; i++)
#define all(v) v.begin(), v.end()
ll gcd(ll a,ll b) {
  return b? gcd(b,a%b): a;  
}
ll lcm(ll a,ll b) {
  return a*b/gcd(a,b);
}
bool isLowerCase(char c){
  return (c>='a'&&c<='z');
}
const string yesno(bool ans){
  return (ans?"Yes":"No");
}

int main() {
  int tbl[3][3];
  rep(i,3){
    rep(j,3){
      cin>>tbl[i][j];
    }
  }
  int n;cin>>n;
  vector<int> b(n);
  rep(i,n){
    int b;
    cin>>b;
    rep(j,3){
      rep(k,3){
        if(tbl[j][k]==b){
          tbl[j][k]=0;
        }
      }
    }
  }
  bool ans=false;
  rep(i,3){
    int sum=0;
    rep(j,3){
      sum+=tbl[i][j];
    }
    if(sum==0){
      ans=true;
      break;
    }
    sum=0;
    rep(j,3){
      sum+=tbl[j][i];
    }
    if(sum==0){
      ans=true;
      break;
    }
  }
  if(!ans){
    int sum=tbl[0][0]+tbl[1][1]+tbl[2][2];
    if(sum==0){
      ans=true;
    }
  }
  if(!ans){
    int sum=tbl[0][2]+tbl[1][1]+tbl[2][0];
    if(sum==0){
      ans=true;
    }
  }
  cout<<yesno(ans)<<endl;
  return 0;
}


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

int main() {
  ll Ans = 0;  // 回答
  ll N; cin >> N; // 数値の数
  vector<ll> A(N);   // 各ボールに書かれた整数
  map<ll,ll> Cnt;   // 各ボールの値毎の球数
  rep(i,N){
    cin >> A.at(i);
    Cnt[A.at(i)]++;
  }

  // P1:N 個の中から、同じ数字を取り出す組み合わせ数
  //    →各数値毎の玉の数を数えておいて、M*(M-1) の合計
  // P2:N 個の中から、k 番目のボールと同じ値のボールを２個取り出す組み合わせ数
  //    → P*(P-1)/2
  // P3:N-1 個の中から、k 番目のボールと同じ値のボールを取り出す組み合わせ数
  //    → (P-1)*(P-2)/2
  //  -P*(P-1)/2+(P-1)*(P-2)/2 = (P-1)*(P-2-P)/2 = -(P-1)
  ll P1=0;
  for(auto m:Cnt){
    if (m.second>=2){
      P1 += m.second * (m.second-1) /2 ;
    }
  }
//  cout << "P1:" << P1 << endl;

  rep(k,N){   // k が除かれるボールの番号：０～Ｎ－１
    Ans = 0;
    if(Cnt[A.at(k)]>=2){
      Ans = P1 - (Cnt[A.at(k)]-1);
    } else {
      Ans = P1;
    }
    cout << Ans << endl;
  }
}


Measured memory_bytes: 11008
N = gets.to_i
abc = N.times.map {gets.split.map &:to_i}

dp = Array.new(N + 1) {Array.new(3) {0}}
N.times do |i|
  3.times do |j|
    3.times do |k|
        dp[i + 1][k] = [dp[i + 1][k], dp[i][j] + abc[i][k]].max if j != k
    end
  end
end

puts dp[N].max

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

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

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;


//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}


int main(){
  int N;
  cin >> N;
  vector<int> a(N);
  int odd = 0,even = 0;
  rep(i,N){
    cin >> a[i];
    if(a[i] % 2 == 1) odd++;
    else even++;
  }

  if(even == N){
    cout << "second" << endl;
  }else{
    cout << "first" << endl;
  }

  return 0;
}


Measured memory_bytes: 640
#include<stdio.h>
int main(void){
  int a, b, c, d;

  scanf("%d %d %d %d", &a, &b, &c, &d);

  if(a+b>c+d){
    printf("Left");
  }
  else if(a+b==c+d){
    printf("Balanced");
  }
  else{
    printf("Right");
  }

  return 0;
}


Measured memory_bytes: 128
n=int(input())
a=list(map(int,input().split()))
a.sort()
stack=a[-1]
ans=[]
for i in range(n-2,-1,-1):
  if len(ans)==2:
    break
  if a[i]==stack:
    ans.append(stack)
    stack=-1
  else:
    stack=a[i]
if len(ans)==2:
  print(ans[0]*ans[1])
else:
  print(0)

Measured memory_bytes: 14672
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct trnode{
	int lc,rc,c;
}tr[25000010];int tot=0,root[300010];
int n,m;
struct node{
	int l,r;
}a[300010];
bool cmp(node a,node b) {return a.l<b.l;}
void update(int &x,int l,int r,int k,int c)
{
	tr[++tot]=tr[x];x=tot;
	if(l==r) {tr[x].c+=c;return;}
	int mid=(l+r)/2;
	if(k<=mid) update(tr[x].lc,l,mid,k,c);
	else update(tr[x].rc,mid+1,r,k,c);
	tr[x].c=tr[tr[x].lc].c+tr[tr[x].rc].c;
}
int findans(int x,int l,int r,int fl,int fr)
{
	if(!x) return 0;
	if(l==fl&&r==fr) return tr[x].c;
	int mid=(l+r)/2;
	if(fr<=mid) return findans(tr[x].lc,l,mid,fl,fr);
	else if(fl>mid) return findans(tr[x].rc,mid+1,r,fl,fr);
	return findans(tr[x].lc,l,mid,fl,mid)+findans(tr[x].rc,mid+1,r,mid+1,fr);
}
void add(int &x,int l,int r,int c)
{
	update(x,1,n,l,c);
	if(r!=n) update(x,1,n,r+1,-c);
}
int main()
{
	scanf("%d %d",&m,&n);
	for(int i=1;i<=m;i++) scanf("%d %d",&a[i].l,&a[i].r);
	sort(a+1,a+m+1,cmp);
	int p=0;
	for(int i=1;i<=m;i++) add(root[0],a[i].l,a[i].r,1);
	for(int i=1;i<=n;i++)
	{
		root[i]=root[i-1];
		while(p<m&&a[p+1].l==i) p++,add(root[i],a[p].l,a[p].r,-1);
	}
	//printf("ok\n");
	for(int i=1;i<=n;i++)
	{
		int ans=0;
		//printf("solve:%d\n",i);
		for(int j=i;j<=n;j+=i) ans+=findans(root[j-i],1,n,1,j);//printf("%d->%d %d\n",j-i,j,ans);
		printf("%d\n",ans);
	}
}

Measured memory_bytes: 254848
#include <algorithm>
#include <iostream>

using namespace std;

uint64_t a[100'000];
uint64_t minB[100'000];
uint64_t maxB[100'000];

int main()
{
    int k;
    cin >> k;
    for (int i = 0; i < k; i++)
    {
        cin >> a[i];
    }

    if (a[k - 1] > 2)
    {
        cout << -1 << endl;
        return 0;
    }

    for (int i = k - 1; i >= 0; i--)
    {
        if (i == k - 1)
        {
            minB[i] = maxB[i] = 2;
            continue;
        }

        minB[i] = (minB[i + 1] + a[i] - 1) / a[i] * a[i];
        maxB[i] = (maxB[i + 1] + a[i + 1] - 1) / a[i] * a[i];

        if (minB[i] > maxB[i])
        {
            cout << -1 << endl;
            return 0;
        }

        //cout << minB[i] << ", " << maxB[i] << endl;
    }

    cout << minB[0] << " " << maxB[0] + a[0] - 1 << endl;
    return 0;
}

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

#define ll long long int
#define fl(i,n) for(int i = 0; i < (n); i++)
#define fls(i,s) for(int i = 0; s[i] != '\0'; i++)

int main() {
    int h1,m1,h2,m2,k;
    scanf("%d %d %d %d %d", &h1, &m1, &h2, &m2, &k);
    int duration;
    if(h1 > h2){
        duration = ((h1-h2)*60) + m1-m2;
    }else if(h2 > h1){
        duration = ((h2-h1)*60) + m2-m1;
    }else{
        if(m1 > m2){
            duration = (m1-m2);
        }else{
            duration = (m2-m1);
        }
    }
    duration -= k;
    printf("%d\n", duration);
    
    return 0;
}


Measured memory_bytes: 3224
import fractions

def lcm(a,b):
    res = a*b // fractions.gcd(a,b)
    return res
def f(x,y,z):
    res = x
    res -= x//y
    res -= x//z
    res += x//lcm(y,z)
    return res


A, B, C, D = map(int, input().split())
ans1 = f(B,C,D)
ans2 = f(A-1,C,D)
ans = ans1 - ans2
print(int(ans))


Measured memory_bytes: 5076