akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Math;

namespace CSharp
{
    static class Program
    {
        static void Main(string[] args)
        {
            int n, a, b;
            ReadInt(out n, out a, out b);
            int ans = Min(n * a, b);
            Console.WriteLine(ans);
        }

        #region Helpers

        static int[] ReadIntArray() => Console.ReadLine().Split().Select(s => int.Parse(s)).ToArray();
        static long[] ReadLongArray() => Console.ReadLine().Split().Select(s => long.Parse(s)).ToArray();

        static int[] ReadLineIntArray(int count) => Enumerable.Repeat(0, count).Select(_ => int.Parse(Console.ReadLine())).ToArray();
        static long[] ReadLineLongArray(int count) => Enumerable.Repeat(0, count).Select(_ => long.Parse(Console.ReadLine())).ToArray();

        static string ReadString() => Console.ReadLine();
        static int ReadInt() => int.Parse(Console.ReadLine());
        static long ReadLong() => long.Parse(Console.ReadLine());

        static void ReadInt(out int first)
        {
            var array = ReadIntArray();
            first = array[0];
        }

        static void ReadInt(out int first, out int second)
        {
            var array = ReadIntArray();
            first = array[0];
            second = array[1];
        }

        static void ReadInt(out int first, out int second, out int third)
        {
            var array = ReadIntArray();
            first = array[0];
            second = array[1];
            third = array[2];
        }

        static void ReadInt(out int first, out int second, out int third, out int fourth)
        {
            var array = ReadIntArray();
            first = array[0];
            second = array[1];
            third = array[2];
            fourth = array[3];
        }

        static void ReadLong(out long first)
        {
            var array = ReadLongArray();
            first = array[0];
        }

        static void ReadLong(out long first, out long second)
        {
            var array = ReadLongArray();
            first = array[0];
            second = array[1];
        }

        static void ReadLong(out long first, out long second, out long third)
        {
            var array = ReadLongArray();
            first = array[0];
            second = array[1];
            third = array[2];
        }

        static void ReadLong(out long first, out long second, out long third, out long fourth)
        {
            var array = ReadLongArray();
            first = array[0];
            second = array[1];
            third = array[2];
            fourth = array[3];
        }

        #endregion
    }
}

Measured memory_bytes: 13268
#include <iostream>
#include <algorithm>
#include <vector>
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;
const int INF = 1e9 + 5;
 
int main() {
	fast; 
    int n, k;
    cin >> n >> k;
    vector<int> stones(n);
    for (int i = 0; i < n; i++) cin >> stones[i];
    vector<int> dp(n, INF); 
    dp[0] = 0; 
    for (int i = 0; i < n; i++) 
    { 
        for (int j = i + 1; j <= i + k; j++) 
        {
            if (j < n)   dp[j] = min(dp[j], dp[i] + abs(stones[j] - stones[i]));
        }
    }
    cout << dp[n - 1];
    return 0;
}

Measured memory_bytes: 3960
N,L=map(int,input().split())
taste0=L
tasteN=L+N-1
Taste=N*(L+L+N-1)//2
if taste0<=0<=tasteN:
  print(Taste)
elif Taste>0:
  print(Taste-taste0)
else:
  print(Taste-tasteN)

Measured memory_bytes: 3060
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        new Program().Calc();
    }

    Scanner cin;

    public Program() { }

    bool chmax<T>(ref T a, T b) where T : IComparable<T> { if (a.CompareTo(b) < 0) { a = b; return true; } return false; }
    bool chmin<T>(ref T a, T b) where T : IComparable<T> { if (b.CompareTo(a) < 0) { a = b; return true; } return false; }

    void Calc()
    {
        cin = new Scanner();

        long x = cin.nextLong();

        long depo = 100;
        int year = 0;

        do
        {
            depo = (long)(depo * 1.01);
            ++year;
        } while (depo < x);

        WriteLine(year);
    }
}

public static class StringExtension
{
    public static char GetChar1(this string str, int indexOneBase)
    {
        return str[indexOneBase - 1];
    }
}

class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}


Measured memory_bytes: 27488
#include <bits/stdc++.h>  // clang-format off
using Int = long long;
#define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io;
#ifndef dump
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Mon Jun 22 00:11:16 JST 2020
 **/

signed main() {
    Int n;
    std::cin >> n;
    std::string ans;
    while (n) {
        n--;
        ans.push_back('a' + n % 26);
        n /= 26;
    }
    std::cout << std::string(ans.rbegin(), ans.rend()) << std::endl;
}


Measured memory_bytes: 3572
n,q = gets.split.map(&:to_i)
s = gets.chomp

count = Array.new(n+1, 0)
1.upto(n-1) do |i|
    count[i+1] = count[i] + (s[i-1] + s[i] == "AC" ? 1 : 0)
end

q.times do
    l,r = gets.split.map(&:to_i)
    puts count[r] - count[l]
end

Measured memory_bytes: 3324
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;

int N;
int x[100],y[100],h[100];

bool judge(int H,int Cx,int Cy){
	int i,H1;
	for(i=0;i<N;i++){
		if(abs(max(H-abs(x[i]-Cx)-abs(y[i]-Cy),0)-h[i])<1e-6)
		;
		else return 0;
	}
	return 1;    
	
}

int main(){
	int i,H;
	cin>>N;

	for(i=0;i<N;i++)
	    cin>>x[i]>>y[i]>>h[i];
	i=0;    
	while(1){
		if(h[i])
		    break;
		i++;    
	}
	for(int j=0;j<101;j++)
	    for(int k=0;k<101;k++){
	        H=h[i]+abs(x[i]-j)+abs(y[i]-k);
	        bool m=judge(H,j,k);
	        if(m){
	        	cout<<j<<" "<<k<<" "<<H;
	        	return 0;
			}
        }
    return 0;}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    L = SI()
    lower = 0
    equal = 1
    for x in L:
        if x == '1':
            lower = (lower * 3 + equal) % MOD
            equal = equal * 2 % MOD
        else:
            lower = lower * 3 % MOD
    ans = (lower + equal) % MOD
    return ans

print(main())

Measured memory_bytes: 3188
//要するに最大公約数を求めようとしたがアルゴリズムがゴミだから一つのデータセットでタイムアウトする
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<tuple>
#include<limits>//ex numeric_limits<int>::max()
#include<unordered_set>
#include<math.h>
// #include"gcd.h"
#define lli long long int

using namespace std;

int gcd(int,int);

int main(void){
    int result=0;
    int N,X;
    cin >> N;
    cin >> X;
    int first;
    int second;
    cin >> first;
    first=abs(X-first);
    for (int i = 0; i < N-1; ++i)
    {
        cin >> second;
        first=gcd(abs(X-second),abs(first));
    }
    cout << first << endl;
}

int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}


Measured memory_bytes: 256
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
#define rep(i,s,t) for(ll i = (ll)(s); i < (ll)(t); i++)
#define rrep(i,s,t) for(ll i = (ll)(s-1);(ll)(t) <= i; i--)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
constexpr ll INF = numeric_limits<ll>::max()/4;
constexpr ll n_max = 2e5+10;
#define int ll

template <typename A, typename B>
string to_string(pair<A, B> p);
string to_string(const string &s) {return '"' + s + '"';}
string to_string(const char *c) {return to_string((string) c);}
string to_string(bool b) {return (b ? "true" : "false");}
template <size_t N>
string to_string(bitset<N> v){
    string res = "";
    for(size_t i = 0; i < N; i++) res += static_cast<char>('0' + v[i]);
    return res;
}
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for(const auto &x : v) {
        if(!first) res += ", ";
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p){return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}

void debug_out() {cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

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

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n,q; cin >> n >> q;
    atcoder::dsu uf(n);
    rep(i,0,q){
        ll t,u,v; cin >> t >> u >> v;
        if(t == 0){
            uf.merge(u, v);
        }
        else{
            cout << (uf.same(u, v) ? 1 : 0) << "\n";
        }
    }
}

Measured memory_bytes: 3940
#include<iostream>
#include<cstring>
using namespace std;
int ball[10];
int l,r;
bool flag;
void dfs(int num,int l,int r){
	if(num==10) return ;
	if(flag) return ;
	if(ball[num]>l) dfs(num+1,ball[num],r);
	else if(ball[num]>r) dfs(num+1,l,ball[num]);
	else{
		flag=true;
		return ;
	}
}
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<10;j++){
			cin>>ball[j];
		}
		l=0,r=0;
		flag=false;
	    dfs(0,l,r);
		if(flag){
			cout<<"NO"<<endl;
		}else{
			cout<<"YES"<<endl;
		} 
	}
}

Measured memory_bytes: 3068
<?php
function isPrime( $x )
{
    if( 2 == $x ) return true;
    if( 0 == $x%2 ) return false;
    for( $i=3; $i*$i<=$x; $i++ ) {
        if( 0 == $x%$i ) { return false; }
    }
    return true;
}
	$n = trim( fgets( STDIN ) );
	$cnt = 0;
	$primes = [];
	while( $n-- ) {
		$num = trim( fgets( STDIN ) );
		if(  FALSE !== array_search( $num, $primes ) || isPrime( $num ) ) {
			array_push( $primes, $num );
			$cnt++;
		}
	}
	print $cnt;
?>

Measured memory_bytes: 15420
#include<stdio.h>
#include<string.h>
int main(){
  int i,j,k,l,n,r;
  char s[74],s1[74],d[800][74];
  scanf("%d",&n);
  while(n--){
    scanf("%s",s);
    l=strlen(s);
    r=0;
    for(i=1;i<l;i++){
      for(j=0;j<8;j++){
	if(j==0){
	  for(k=0;k<i;k++)s1[    k]=s[k];
	  for(   ;k<l;k++)s1[    k]=s[k];
	}
	if(j==1){
	  for(k=i;k<l;k++)s1[  k-i]=s[k];
	  for(k=0;k<i;k++)s1[l-i+k]=s[k];
	}
	if(j==2){
	  for(k=0;k<i;k++)s1[i-k-1]=s[k];
	  for(   ;k<l;k++)s1[    k]=s[k];
	}
	if(j==3){
	  for(k=i;k<l;k++)s1[  k-i]=s[k];
	  for(k=0;k<i;k++)s1[l-k-1]=s[k];
	}
	if(j==4){
	  for(k=0;k<i;k++)s1[    k  ]=s[k];
	  for(   ;k<l;k++)s1[l+i-k-1]=s[k];
	}
	if(j==5){
	  for(k=i;k<l;k++)s1[l-k-1]=s[k];
	  for(k=0;k<i;k++)s1[l-i+k]=s[k];
	}
	if(j==6){
	  for(k=0;k<i;k++)s1[  i-k-1]=s[k];
	  for(   ;k<l;k++)s1[l+i-k-1]=s[k];
	}
	if(j==7){
	  for(k=i;k<l;k++)s1[  k-i]=s[k];
	  for(k=0;k<i;k++)s1[l-i+k]=s[k];
	}
	s1[l]=0;
	//printf("%d %s\n",j,s1);
      	for(k=0;k<r;k++){
	  if(strcmp(d[k],s1)==0)break;
	}
	if(k==r)strcpy(d[r++],s1);
      }
    }
    printf("%d\n",r);
  }
  return 0;
}

Measured memory_bytes: 656
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define PI 3.141592
#define MOD 1000000007
#define LL_INF 9000000000000000000
#define LL_MINF -9000000000000000000
#define INT_INF 2000000000
#define INT_MINF -2000000000
#define all(a) (a).begin(), (a).end()
#define fi first
#define se second
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int main(){
    int N;
    cin >> N;
    map<string,int> S;
    for(int i = 0; i < N; i++){
        string s;
        cin >> s;
        S[s]++;
    }
    cout << S.size() << endl;

}


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

using namespace std;
using ll = long long;

double n;
double a[205];

int main(){
  cin >> n;
  double ave = 0;
  for(int i = 0; i < n; ++i){
    cin >> a[i];
    ave += a[i];
  }
  ave /= n;
  ll in_ave = int(ave);
  //cout << in_ave << endl;
  ll c;
  if(in_ave + 1 - ave < ave - in_ave){
    c = in_ave + 1;
  }else{
    c = in_ave;
  }
  //cout << c << endl;
  ll ans = 0;
  for(int i = 0; i < n; ++i){
    //cout << abs(c - a[i]) << endl;
    ans += pow(abs(c - a[i]), 2);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
// vacations.cpp
#include<iostream>
#include<cstring>
#include<climits>
using namespace std;


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

	if(n==0) return 0;
	int dp[n][3];
	memset(dp,0,sizeof(dp));
	int a,b,c;
	int arr[n][3];
	for(int i=0;i<n;i++){
		cin >> a>>b>>c;
		arr[i][0] = a;
		arr[i][1] = b;
		arr[i][2] = c;
	}

	dp[0][0] = arr[0][0];
	dp[0][1] = arr[0][1];
	dp[0][2] = arr[0][2];

	for(int i=1;i<n;i++){
		dp[i][0] = max(dp[i-1][1],dp[i-1][2]) + arr[i][0];
		dp[i][1] = max(dp[i-1][0],dp[i-1][2]) + arr[i][1];
		dp[i][2] = max(dp[i-1][1],dp[i-1][0]) + arr[i][2];
	}
	
	cout << max(dp[n-1][0], max(dp[n-1][1], dp[n-1][2]));




	return 0;
}

Measured memory_bytes: 5928
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> llP;

int main() {
  ll n,m;
  cin>>n>>m;
  if(n==1 and m==1){
    cout<<1<<endl;
  }
  else if(n==1){
    cout<<m-2<<endl;
  }
  else if(m==1){
    cout<<n-2<<endl;
  }
  else{
    cout<<(n-2)*(m-2)<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
n,k=map(int, input().split())
a=list(map(int, input().split()))
a2=[i for i in a if i>=0]
b=sorted([-1*i for i in a])
b2=[i for i in b if i>=0]
ans=10**9
for i in range(n-k+1):
    if a[i]>=0:ans=min(ans,a2[k-1])
    else:
        ans=min(ans,a[k+i-1]-a[i]*2)
for i in range(n-k+1):
    if b[i]>=0:ans=min(ans,b2[k-1])
    else:
        ans=min(ans,b[k+i-1]-b[i]*2) 
print(ans)

Measured memory_bytes: 14844
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<functional>
#include<iomanip>
#include<cmath>
#include<queue>
#include<limits>
#include<cassert>
#include<set>
#include<tuple>
#include<map>
#include<list>

#define PB push_back
#define ALL(a)  (a).begin(),(a).end()
#define DWN(a)  (a).begin(),(a).end(), greater<int>()
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

using namespace std;
typedef long long ll;


bool f_sort(pair<int, int> a, pair<int, int> b) { return a.first < b.first; };
bool s_sort(pair<int, int> a, pair<int, int> b) { return a.second < b.second; };

int main()
{
	int n;
	cin >> n;
	pair<int, int> red[100], blue[100];
	REP(i, n) {
		cin >> red[i].first >> red[i].second;
	}
	REP(i, n) {
		cin >> blue[i].first >> blue[i].second;
	}
	sort(red, red + n, s_sort); //赤のy座標小さい順
	sort(blue, blue + n, f_sort); //青のx座標小さい順
	int ans = 0;
	bool f[100] = {}; //使ったか
	for(int i = 0; i < n; i++) {
		for(int j = n - 1; j >= 0; j--) {
			if (f[j]) continue;
			if (blue[i].first > red[j].first && blue[i].second > red[j].second) {
				ans++; //pairがある
				f[j] = true; //使った
				break;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import collections

H, W = map(int, input().split(" "))
mp = []
for _ in range(H):
    mp.append(input().strip())


def bfs(sh, sw, mp):
    que = collections.deque()
    que.append((sh, sw))
    dist = [[-1 for _ in range(W)] for _ in range(H)]
    dist[sh][sw] = 0

    while que:
        h, w = que.popleft()
        for (dh, dw) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            if h + dh < 0 or w + dw < 0 or h + dh >= H or w + dw >= W:
                continue
            if mp[h + dh][w + dw] == '.' and dist[h + dh][w + dw] == -1:
                dist[h + dh][w + dw] = dist[h][w] + 1
                que.append((h + dh, w + dw))

    ans = 0
    for row in dist:
        ans = max(ans, max(row))
    return ans


ans = 0
for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            ans = max(ans, bfs(h, w, mp))
print(ans)

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

namespace AtCorder
{
	public class Program
	{
		static int[] dp = new int[10001];

		static void Main(string[] args)
		{
			List<int> nm = Console.ReadLine().Split(' ').Select(int.Parse).ToList();
			int n = nm[0];
			int m = nm[1];
			List<long> x = Console.ReadLine().Split(' ').Select(long.Parse).ToList();
			if (n >= m) {
				Console.WriteLine(0);
				return;
			}

			x.Sort();
			var y = x.Zip(x.Skip(1), (p, s) => s - p).ToList();
			y.Sort();
			long ans = y.Take(m - n).Sum();
			Console.WriteLine(ans);
		}
	}

	
}


Measured memory_bytes: 20704
#include <algorithm>
#include <bits/stdc++.h>
#include <bitset>
#include <cassert>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
#define REP(i, n) for (int64_t i = 0; i < (int64_t)n; i++)
#define REP_FOR(i, a, b) for (int64_t i = (int64_t)a; i < (int64_t)b; i++)
#define REP_REV(i, a, b) for (int64_t i = (int64_t)a; i > (int64_t)b; i--)
#define FORALL(v) (v).begin(), (v).end()
#define mp(a, b) make_pair(a, b)
#define eb(x) emplace_back(x)
#define F first
#define S second
typedef long long ll;
typedef long double ld;
typedef pair<int64_t, int64_t> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int64_t> vii;
typedef vector<vii> vvii;
const ll mod = 1e9 + 7;
const int64_t infi = 1147483600;
const ll infl = 4e18 + 5;
const char EOL = '\n';
//cout << fixed << setprecision(17) << res << endl;
const ll MOD = 998244353;

 #include <vector>
 
#define ll long long int

#define M 1000000007

int main() {
    ll n;
    cin >> n;
    vector<ll> P(n), Pos(n+1, 0);
    for (ll i = 0; i < n; ++i) {
        cin >> P[i];
        Pos[P[i]] = i + 1;
    }

    ll res = 0;
    multiset<ll> s;
    s.insert(0);
    s.insert(0);
    s.insert(n+1);
    s.insert(n+1);

    for (ll now = n; now >= 1; now--){
        auto it = s.lower_bound(Pos[now]);
        ll pos_r = *it;

        it++;
        ll pos_rr = *it;

        it--;
        it--;
        ll pos_l = *it;

        it--;
        ll pos_ll = *it;

        res += now*(pos_r-Pos[now])*(pos_l-pos_ll);
        res += now*(pos_rr-pos_r)*(Pos[now]-pos_l);

        s.insert(Pos[now]);
    }
    cout<<res<<endl;
}


Measured memory_bytes: 6528
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<utility>
#include<algorithm> // sort
#include<map> // pair
#include<cmath>
#include<cstring>
#include<set>
using namespace std;
using ll = long long;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
const ll mod = 1e9+7;
const int INF = 1e9;
const ll INFLONG = 1e18;
ll sum;
ll x;
int main(){
  ll n;
  cin >> n >> x;
  ll a[n+1];//the number of p
  ll b[n+1];//the number of all
  a[0] = 1;
  b[0] = 1;
  rep(i,n){
    a[i+1] = a[i]*2+1;
    b[i+1] = b[i]*2+3;
  }
  sum = 0;
  for(int i=n;i>=0;i--){
    if(x >= b[i]){
      if(x > b[i]){
        sum++;
        x--;
      }
      sum += a[i];
      x -= b[i];
      //cout << sum << " " << x << " " << i <<  endl;
      i++;
    }else{
      x--;
    }
  }
  cout << sum;
}


Measured memory_bytes: 256
from collections import deque
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


sa = deque(list(S()))
sb = deque(list(S()))
sc = deque(list(S()))

turn = 'a'
while True:
    if turn == 'a':
        if len(sa) == 0:
            ans = 'A'
            break
        turn = sa.popleft()
    elif turn == 'b':
        if len(sb) == 0:
            ans = 'B'
            break
        turn = sb.popleft()
    elif turn == 'c':
        if len(sc) == 0:
            ans = 'C'
            break
        turn = sc.popleft()

print(ans)


Measured memory_bytes: 9428
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <cmath>
#include <vector>
#include <numeric>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <tuple>

using ll = long long int;
using ul = unsigned long long int;
const ll LL_MAX (1LL<<60);
const ll MOD (1000000007);

#define rep(i,s,e) for(ll i=(s); i<(e); i++) 

using namespace std;

using T = tuple<ll,ll>;
using Graph = vector<vector<T>>;

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

    ll h, w;
    cin >> h >> w;

    if (h == 1 || w == 1)
    {
        cout << 1 << endl;
        return 0;
    }

    //ll h2 = h/2;
    ll h2 = (h % 2==0) ? h/2 : h/2+1;
    ll w2 = (w % 2==0) ? w/2 : w/2+1;

    //cout << "h2=" << h2 << endl;
    //cout << "w2=" << w2 << endl;

    cout << w2 * h2 + (w-w2) * (h-h2) << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int pow(int a, int b) {
	unsigned int ret = 1;
	for(int i = 0; i<b; ++i)
		ret *= a;

	return ret;
}

int main(int argc, char const *argv[]) {
	unsigned int a, b, c, k, max, sum;
	cin >> a >> b >> c >> k;

	max = a;
	if(max < b) 
		max = b;
	if(max < c)
		max = c;

	sum = a + b + c + max * pow(2, k) - max;
	cout << sum;

	return 0;
}

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

using namespace std;
typedef pair<int,int> pii;
typedef long long int ll;

#define INF 1 << 30
#define REP(i,n) for(ll i=0; i<(int)(n); i++)
#define FOR(i,k,n) for(ll i=(k);i<(int)(n);i++)



vector<bool> gen_sosuu(vector<bool> sosuu){
  int size = sosuu.size();
  REP(i,size){
    sosuu[i] = true;
  }
  sosuu[0] = false;
  sosuu[1] = false;
  sosuu[2] = true;
  FOR(i,2,sqrt(size)+1){
    if(sosuu[i] == false) continue;
    for(int j = 2; i*j<size;j++){
      sosuu[i*j] =false;
    }
  }
  return sosuu;
}

int n,k;

int main(){
  cin >> n >> k;
  if(n%k==0) cout << 0 <<endl;
  else cout << 1 <<endl;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")

#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;

#define ll long long int
#define pb push_back
#define mp make_pair
#define ld long double
#define sz(a) (ll)(a).size()

typedef tree<pair<ll,ll> ,null_type,less<pair<ll,ll> >,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//K-th smallest
//cout << k << "kth smallest: " << *A.find_by_order(k-1) << endl;
//NO OF ELEMENTS < X
//cout << "No of elements less than " << X << " are " << A.order_of_key(X) << endl;

const int MAXN = 100005;

ll n, a[MAXN], b[MAXN], c[MAXN], dp[MAXN][4];        // Maximum points from i to n-1 with previous day activity in second column

ll rec(ll ind, ll prev)
{
	if(ind == n) return 0;
	if(dp[ind][prev] != -1) return dp[ind][prev];
	ll ans = 0;
	if(prev != 0) ans = max(ans, a[ind] + rec(ind + 1, 0)); 
	if(prev != 1) ans = max(ans, b[ind] + rec(ind + 1, 1)); 
	if(prev != 2) ans = max(ans, c[ind] + rec(ind + 1, 2)); 
	return dp[ind][prev] = ans;
}

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

 	cin >> n;
 	for(int i=0;i<n;i++) cin >> a[i] >> b[i] >> c[i];
 	memset(dp, -1, sizeof(dp));
 	cout << rec(0, 3) << endl;   
    return 0;
}

Measured memory_bytes: 9600
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv, std.math,
    std.functional, std.numeric, std.range, std.stdio, std.string, std.random,
    std.typecons, std.container, std.format;

// dfmt off
T lread(T = long)(){return readln.chomp.to!T();}
T[] lreads(T = long)(long n){return generate(()=>readln.chomp.to!T()).take(n).array();}
T[] aryread(T = long)(){return readln.split.to!(T[])();}
void scan(TList...)(ref TList Args){auto line = readln.split();
foreach (i, T; TList){T val = line[i].to!(T);Args[i] = val;}}
alias sread = () => readln.chomp();enum MOD = 10 ^^ 9 + 7;
alias PQueue(T, alias less = "a<b") = BinaryHeap!(Array!T, less);
// dfmt on

void main()
{
    long N, K;
    scan(N, K);
    auto H = lreads(N);
    H.sort();
    long ans = long.max;
    foreach (i; 0 .. N)
    {
        if (i + K - 1 < N)
        {
            ans = ans.min(H[i + K - 1] - H[i]);
        }
    }
    writeln(ans);
}


Measured memory_bytes: 3964
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int comp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}
int main() {
  int n,a[100000],i;
  double x,y[2];
  scanf("%d",&n);
  for (i=0;i<n;i++) {
    scanf("%d",&a[i]);
  }
  qsort(a, n, sizeof(int), comp);
  x=(double)a[n-1]/2;
  y[1]=a[n-1];
  for (i=0;i<n;i++) {
    y[0]=fabs(a[i]-x);
    if (y[0]>y[1]) {
      printf("%d %d\n",a[n-1],a[i-1]);
      return 0;
    }
    y[1]=y[0];
  }
  printf("%d %d\n",a[n-1],a[0]);
  return 0;
}

Measured memory_bytes: 892
#include "iostream"
#include "vector"
#include "map"

#define N_MAX 55


using namespace std;

vector<int> eratos(int n) {
    vector<int> arr(n + 1);

    for (int i = 0; i <= n; i++) arr[i] = 1;

    for (int i = 2; i <= n; i++) {
        if (arr[i] != 0) {
            for (int j = 2; i * j <= n; j++) {
                arr[i * j] = 0;
            }
        }
    }

    vector<int> ret;
    for (int i = 2; i <= n; i++) {
        if(arr[i] != 0) {
            ret.push_back(i);
        }
    }
    return ret;
}

int N;

int main() {

    cin >> N;

    vector<int> primes = eratos(55555);

    vector<int> ans;
    for (int i = 0; i < primes.size(); i++) {
        if (primes[i] % 5 == 1) {
            ans.push_back(primes[i]);
        }
    }

    for (int i = 0; i < N - 1; i++) {
        cout << ans[i] << " ";
    }
    cout << ans[N - 1];
}

Measured memory_bytes: 512
x,y=list(map(int, input().split()))
s=[list(map(str,list(input()))) for i in range(x)]

count=0
for i in range(x):
	for j in range(y):
		count=0
		if s[i][j]=='.':
			if i>0 and j>0 and s[i-1][j-1]=='#':
				count=count+1
			if i>0 and s[i-1][j]=='#':
				count=count+1
			if i>0 and j<y-1 and s[i-1][j+1]=='#':
				count=count+1
			if j>0 and s[i][j-1]=='#':
				count=count+1
			if j<y-1 and s[i][j+1]=='#':
				count=count+1
			if i<x-1 and j>0 and s[i+1][j-1]=='#':
				count=count+1
			if i<x-1 and s[i+1][j]=='#':
				count=count+1
			if i<x-1 and j<y-1 and s[i+1][j+1]=='#':
				count=count+1
			s[i][j]=count
for a in s:
	print(*a,sep='')

Measured memory_bytes: 3444
from itertools import combinations

N = int(input())
S = [input() for _ in range(N)]
init = {}
count = 0

for s in S:
    if s[0] in ["M", "A", "R", "C", "H"]:
        if s[0] not in init:
            init[s[0]] = 1
        else:
            init[s[0]] += 1

if len(init) < 3:
    print(0)
else:
    for comb in combinations(init.values(), 3):
        count += comb[0] * comb[1] * comb[2]

    print(count)

Measured memory_bytes: 9776
#include <bits/stdc++.h>
using namespace std;
 
int main() {

  int N,K,X,Y;

  cin >>  N >> K >> X >> Y ;


  if(N<=K) cout << N*X << endl;

  else{
    int M=N-K;
    cout << K*X+M*Y << endl;
  }
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
#define inf 2000000000
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
ll mod=1e9+7;			
	   
int main() {
			fast
			

			
				ll n;
                cin>>n;
                ll arr[n];
                for(ll i=0;i<n;i++)
                cin>>arr[i];

				ll money=1000;
				ll stock=0;
				
				for(ll i=0;i<n-1;i++)
				{
					if(arr[i+1]>arr[i])
					{
						
						stock+=(money/arr[i]);
						money=money%arr[i];

					}
					else if(arr[i+1]<arr[i])
					{
						money+=(stock*arr[i]);
						stock=0;
					}
				}
				cout<<money+stock*arr[n-1]<<endl;
                
			
			return 0;
		 }	




Measured memory_bytes: 3604
//
//AtCoder Beginner Contest 082
//B
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <functional>
#include <cassert>
#include <bitset>

using namespace std;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define SIZE(x) (int)(x).size()
#define SIZEL(x) (ll)(x).size()
#define MSG(a) cout << #a << " " << a << endl;

using ll = long long;
using ld = long double;
using Graph = vector<vector<int>>;

const double PI = 3.14159265358979323846;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll gcd(ll x, ll y) { return (x % y)? gcd(y, x % y): y; }    //最大公約数
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }            //最小公倍数

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

    sort(ALL(s));
    sort(RALL(t));
    if (s<t){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 3624
#include<iostream>
#include<string>
#define LL long long
int N;
LL x;
LL A[100010];
LL ans;
int main() {
	std::cin >> N >> x;
	for (int i = 1; i <= N; i++)std::cin >> A[i];
	for (int i = 2; i <= N; i++) {
		if (A[i - 1] + A[i] > x) {
			ans += A[i - 1] + A[i] - x;
			A[i] -= A[i - 1] + A[i] - x;
			if (A[i] < 0) {
				A[i] = 0;
			}
		}
	}
	std::cout << ans << std::endl;
	return 0;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<algorithm>
#include<functional>
#include<cstring>
using namespace std;
int main(void)
{
	int i,n,h,a;
	long long sum;
	scanf("%d",&n);
	scanf("%d",&a);
	h=a;
	sum=0;
	for(i=1;i<n;i++)	{
		scanf("%d",&a);
		if(h>a)	sum+=h-a;
		else h=a;
	}
	printf("%lld\n",sum);
	return 0;
}

Measured memory_bytes: 1736
#define _USE_MATH_DEFINES
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

void abc_160a();

void abc_161a();

void abc_162a();

void abc_163a();

void abc_164a();

void abc_165a();

void abc_166a();

void abc_167a();

int main()
{
  //abc_160a();
  //abc_161a();
  //abc_162a();
  //abc_163a();
  //abc_164a();
  //abc_165a();
  //abc_166a();
  abc_167a();


}

void abc_160a()
{
  string S;
  cin >> S;

  if (S[2] == S[3] && S[4] == S[5]) cout << "Yes\n";
  else cout << "No\n";
}

void swap(int& a, int& b)
{
  int tmp;
  tmp = a;
  a = b;
  b = tmp;
}

void abc_161a()
{
  int x, y, z;
  cin >> x >> y >> z;

  swap(x, y);
  swap(x, z);

  cout << x << " " << y << " " << z << "\n";
}

void abc_162a()
{
  string s;
  cin >> s;
  for (char c : s)
  {
    if (c == '7')
    {
      cout << "Yes\n";
      return;
    }
  }

  cout << "No\n";
}

void abc_163a()
{
  int R;
  cin >> R;

  cout << (double)(2 * R * M_PI);
}

void abc_164a()
{
  int s, w;
  cin >> s >> w;

  if (s <= w) cout << "unsafe\n";
  else cout << "safe\n";
}

void abc_165a()
{
  int k, a, b;
  cin >> k >> a >> b;

  for (int i = a; i <= b; ++i)
  {
    if (i % k == 0)
    {
      cout << "OK\n";
      return;
    }
  }

  cout << "NG\n";
}

void abc_166a()
{
  string s;
  cin >> s;

  if (s == "ABC") cout << "ARC\n";
  if (s == "ARC") cout << "ABC\n";

}

void abc_167a()
{
  string s, t;
  cin >> s >> t;

  for (int i = 0; i < s.size(); ++i)
  {
    if (s[i] != t[i])
    {
      cout << "No\n";
      return;
    }
  }

  if ('a' <= t[t.size() - 1] && t[t.size() - 1] <= 'z') cout << "Yes\n";
  else cout << "No\n";

}


Measured memory_bytes: 3632
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string.h>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <math.h>
#include <algorithm>
#include <numeric>

using namespace std;

// マクロ&定数 ============================================================
typedef unsigned int uint;
typedef long long ll;
//typedef pair<int, int> P;

typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<bool> vbool;
typedef vector<string> vstring;

typedef vector<pair<int, int>> vpint;
typedef vector<pair<ll, ll>> vpll;
typedef vector<pair<double, double>> vpdouble;

typedef vector<vector<int>> vvint;
typedef vector<vector<ll>> vvll;
typedef vector<vpint> vvpint;
typedef vector<vpll> vvpll;
typedef vector<vector<double>> vvdouble;
typedef vector<vector<string>> vvstring;
typedef vector<vector<bool>> vvbool;

typedef vector<vector<vector<ll>>> vvvll;

const int c_YET = -1;
const int INF = 1e9 + 1;
const ll LLINF = 1e17 + 1;
const int DX[9] = { 0,0,1,-1, 1, 1, -1, -1, 0 }; // 4;４近傍
const int DY[9] = { 1,-1,0,0, 1, -1, 1, -1, 0 }; // 8:８近傍 9:(0,0)を含む
const ll MOD = 1e9 + 7; //10^9 + 7
const ll MAX = 1e9;
const double PI = 3.14159265358979323846264338327950288;
//========================================================================





int main() {

	////==================================
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(30);
	////==================================
	

	ll K, T;
	cin >> K >> T;
	vll A(T);
	for (int i = 0; i < T; i++)
	{
		cin >> A[i];
	}


	ll max_A = 0;
	for (int i = 0; i < T; i++)
	{
		max_A = max(max_A, A[i]);
	}

	cout << max((max_A - 1) - (K - max_A), (ll)0) << endl;



}





Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
using static Scanner;

class Program
{
    static void Main(string[] args) {
        var writer = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
        Console.SetOut(writer);
        Solve();
        Console.Out.Flush();
    }
    static void Solve() {
        var N = ScanInt();
        var set = new HashSet<int>();
        for (int i = 0; i < N; i++) {
            var num = ScanInt();
            if (set.Contains(num)) set.Remove(num);
            else set.Add(num);
        }
        Console.WriteLine(set.Count);
    }
}

public static class Scanner
{
    static readonly Stream stream = Console.OpenStandardInput();
    static readonly byte[] buffer = new byte[1024];
    static int length, p;
    static bool isEof;
    private static byte ConsoleIn() {
        if (isEof) return 0;
        if (p < length) return buffer[p++];
        p = 0;
        if ((length = stream.Read(buffer, 0, 1024)) > 0) return buffer[p++];
        isEof = true;
        return 0;
    }
    public static char GetChar() {
        var by = ConsoleIn();
        while ((by < '!' || '~' < by) && !isEof) by = ConsoleIn();
        return (char) by;
    }
    public static int ScanInt() {
        var temp = 0;
        for (var ch = GetChar(); '0' <= ch && ch <= '9'; ch = (char) ConsoleIn()) {
            temp = temp * 10 + ch - '0';
        }
        return temp;
    }
}

Measured memory_bytes: 27672
#include <iostream>
#include <algorithm>
#include<vector>
#include <queue>
using namespace std;
int main()
{
	long n, a, b;
	cin >> n >> a >> b;
	int o, s;
	cin >> o;
	long ans = 0;
	for (int i = 1; i < n; i++) {
		cin >> s;
		if (a * (s - o) > b)ans+=b;
		else ans += a * (s - o);
		o = s;
	}
	cout << ans << endl;
}

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

def calcdistance(point1,point2):
    total = 0
    for i in range(len(point1)):
        total += (point1[i]-point2[i])**2
    return total**(0.5)
    
points = []
for i in range(N):
    points.append(list(map(int, input().split())))

ans = 0
for i in range(N):
    for j in range(i,N):
        if i == j:
            continue
        else:
            distance = calcdistance(points[i],points[j])
            if distance.is_integer():
                ans += 1
print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
# define maxi 100000
# define maxw 100000
# define maxn 100000

int main() {
  long long n,a[maxn],dp[maxn]={0};
  cin>>n; for(long long i(0);i<n;i++){
    cin>>a[i];
  }
  dp[1]=abs(a[0]-a[1]);
  for(long long i(2);i<n;i++){
    dp[i]=min(dp[i-2]+abs(a[i]-a[i-2]),dp[i-1]+abs(a[i]-a[i-1]));
  }
  cout<<dp[n-1];
}


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

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

const int MAX_N = 100005;

int N, M;
string S, T;

int lcm( int m, int n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	return ((m / __gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}//lcm

signed main()
{
    cin >> N >> M;
    cin >> S;
    cin >> T;

    if(S[0] != T[0]) {
        cout << -1 << endl;
        return 0;
    }

    int LCM = lcm(N, M);

    int l = LCM/N;
    int r = LCM/M;

    int ll = 0, rr = 0;
    while(ll < N && rr < M) {
        if(S[ll] != T[rr]) {
            cout << -1 << endl;
            return 0;
        }
        ll += r; rr += l;
    }

    cout << LCM << endl;

    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int n,k;
int a[200001],b[200001];
int main() {
	cin>>n>>k;
	
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	    b[a[i]]++;
	}
	sort(b+1,b+n+1);
	int ans=0;
	for (int i=1;i<=n-k;i++){
		ans+=b[i];
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef vector < vector < int > > vvi;
int n;
vvi calc(int n){
	if(n==1){
		vvi ret;
		ret.clear();
		return ret;
	}
	vvi A,B,R;
	R.clear();
	A=calc(n/2);
	B=calc((n+1)/2);
	R.resize(max(A.size(),B.size())+1);
	int i,j;
	for(i=0;i<(int)R.size();++i) R[i].resize(n);
	for(i=0;i<n/2;++i) R[0][i]=1;
	for(i=1;i<(int)R.size();++i){
		if((i-1)<(int)A.size()){
			for(j=0;j<n/2;++j) R[i][j]=A[i-1][j];
		}
		if((i-1)<(int)B.size()){
			for(j=n/2;j<n;++j) R[i][j]=B[i-1][j-n/2];
		}
	}
	return R;
}
int main(){
	int i,j,k;
	scanf("%d",&n);
	vvi col=calc(n);
	for(i=0;i<n-1;++i){
		for(j=i+1;j<n;++j){
			for(k=0;k<(int)col.size();++k){
				if(col[k][i]!=col[k][j]) break;
			}
			printf("%d ",k+1);
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <numeric>
#include <iomanip>
#include <cmath>
#define ll long long
#define intm INT_MAX
#define llm LLONG_MAX

using namespace std;
int MOD = 998244353;
const int mxN = 40 + 9;

ll ar[mxN];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll N;
	cin >> N;
	vector<ll> divisor;
	for(ll i=1; i <= sqrt(N); i++){
        if( N % i == 0 ){
            if( N / i == i ) divisor.push_back(i);
            else{
                divisor.push_back(i);
                divisor.push_back(N/i);
            }
        }
	}
	sort(divisor.begin(), divisor.end());
	vector<ll> pow;
	for(auto &i: divisor){
        if( i != 1 ){
        ll cnt = 0;
        while( N % i == 0 ){
            N /= i;
            ++cnt;
        }
        if( cnt != 0 ) pow.push_back(cnt);
        }
	}
	/*for(auto &c: pow) cout << c << " ";
	cout << endl;*/
	ll ans = 0;
	ar[1] = 1;
	for(ll i=2; i <= 40; i++) ar[i] = ar[i-1] + i;
	for(auto c: pow){
        int L = 1; int R = 40;
        int tmpans = 1;
        while( L <= R ){
            int mid = (R+L)/2;
            //cout << "mid = " << mid  << " " << ar[mid] << endl;
            if( ar[mid] == c ){
                tmpans = mid; break;
            }
            else if( ar[mid] > c ) R = mid-1;
            else if( ar[mid] < c ){
                tmpans = mid;
                L = mid+1;
            }

        }
        //cout << tmpans << " ";
        ans += tmpans;
	}
	cout << ans;




}


Measured memory_bytes: 3656
#include "bits/stdc++.h"
#define ll long long
using namespace std;
const ll INF = 1e18L + 5;
void max_self(ll &a, ll b){
    a = max(a, b);
}

void min_self(ll &a, ll b){
    a = min(a, b);
}
int main() {
    int n, W;
    scanf("%d%d", &n, &W);
    vector<int> weight(n), value(n);
    for(int i = 0; i < n; ++i) {
        scanf("%d%d", &weight[i], &value[i]);
    }
    int sum_value = 0;
    for(int x : value) {
        sum_value += x;
    }
    vector<ll> dp(sum_value + 1, INF); // 0 ... W
    dp[0] = 0;
    // dp[i] - the minimum total weight of items with total value exactly i
    for(int item = 0; item < n; ++item) {
        for(int value_already = sum_value - value[item]; value_already >= 0; --value_already) {
        //~ for(int weight_already = 0; weight_already <= W - weight; ++weight_already) {
            min_self(dp[value_already+value[item]], dp[value_already] + weight[item]);
        }
    }
    ll answer = 0;
    for(int i = 0; i <= sum_value; ++i) {
        if(dp[i] <= W) {
            answer = max(answer, (ll) i);
        }
        //~ min_self(answer, dp[i]);
    }
    printf("%lld\n", answer);
}

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

vector<int> seat;
vector<bool> fix;
int Ns;
vector<int> movex={0,0,-1,1};
vector<int> movey={-1,1,0,0};

void optimize(int);



int main() {
  int N;
  cin >> N;
  Ns=N+2;
  int MN=N*N;
  int MN2=(N+2)*(N+2);
  seat=vector<int>(MN2);
  fix=vector<bool>(MN2,true);
  for(int i=0;i<N;i++){
   for(int j=0;j<N;j++){
    seat.at((i+1)*Ns+j+1)=min(min(i,N-i-1),min(j,N-j-1)); 
    
   }
  
  }
  
  
  
  int hate=0;
  int next;
  
  for(int i=0;i<MN;i++){
    cin >> next;
    next--;
    next=((next/N)+1)*Ns+(next%N)+1;
    
    hate+=seat.at(next);
    fix.at(next)=false;
    optimize(next);
    
    
  }
  
  cout << hate << endl;
  
  
}


void optimize(int N){
  int hit=seat.at(N)+fix.at(N);
  for(int i=0;i<4;i++){
    int around=movey.at(i)*Ns+movex.at(i)+N; 
    if (seat.at(around)>hit){
      seat.at(around)=hit;
      optimize(around);
    }
  }
  
}

Measured memory_bytes: 15508
n = int(input())
a = list(map(int,input().split()))

ans = []
b = [0]*n
for i in range(n-1,-1,-1):
    if sum(b[i::i+1])%2 == 1:#iから最後までをi+1個おきに
        if a[i] == 0:
            b[i] += 1
            ans.append(i+1)
    else:
        if a[i] == 1:
            b[i] += 1
            ans.append(i+1)

print(len(ans))
print(*ans)
        

Measured memory_bytes: 18056
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
	int n;
	cin>>n;
	vector<int> s(n);
	rep(i,n)cin>>s[i];
	sort(all(s));
	int q;
	cin>>q;
	vector<int> t(q);
	rep(i,q)cin>>t[i];
	int ans = 0;
	rep(i,q){
		if(*lower_bound(all(s), t[i]) == t[i])++ans;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3320
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 合計は同じ、0,0の場所が選ばれたら終わり
# 次のものに渡しておく
N, A, B, C = lr()
S = [sr() for _ in range(N)]
answer = []
for i, s in enumerate(S):
    if s == 'AB':
        if A == B == 0:
            print('No'); exit()
        elif A == 0:
            answer.append('A')
            A += 1; B -= 1; continue
        elif B == 0 or i == N-1:
            answer.append('B')
            B += 1; A -= 1; continue
        ne = S[i+1]
        if 'A' in ne:
            answer.append('A')
            A += 1; B -= 1
        else:
            answer.append('B')
            B += 1; A -= 1
    elif s == 'BC':
        if C == B == 0:
            print('No'); exit()
        elif C == 0:
            answer.append('C')
            C += 1; B -= 1; continue
        elif B == 0 or i == N-1:
            answer.append('B')
            B += 1; C -= 1; continue
        ne = S[i+1]
        if 'C' in ne:
            answer.append('C')
            C += 1; B -= 1
        else:
            answer.append('B')
            B += 1; C -= 1
    elif s == 'AC':
        if A == C == 0:
            print('No'); exit()
        elif A == 0:
            answer.append('A')
            A += 1; C -= 1; continue
        elif C == 0 or i == N-1:
            answer.append('C')
            C += 1; A -= 1; continue
        ne = S[i+1]
        if 'A' in ne:
            answer.append('A')
            A += 1; C -= 1
        else:
            answer.append('C')
            C += 1; A -= 1

print('Yes')
print(*answer, sep='\n')


Measured memory_bytes: 86316
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
using ll = long long;

#define REP(i,s,N) for(ll i=s;i<N;++i)

ll operate(vector<ll> &x) {
	
}
int main() {
	ll N;
	cin >> N;
	vector<ll> a(N,0);
	REP(i,0,N) scanf("%lld", &a[i]);

	//
	// 2で割る操作, 3をかける操作
	// 
  // 1. 整数になれば良い -> odd number => 3をかける操作のみ. even ならば どちらの操作も可能
	// even => 2 pattern
	// odd  => 1 pattern
	//
	// 2. 全て3をかける,という操作は許されない. 
	//
	// 3. 1セット操作すると、操作後の値に対して次の操作を行うことになる.
	// -> 終了条件は全てが奇数となる場合.
	// -> a[i]が2のべき乗で表される回数で決まってくる.
	// -> 1<=i<=N のどれかについてevenがあれば操作は可能であるから, べき乗をカウントすれば良い
	//
	ll ans = 0;
	REP(i,0,N) {
		while (a[i] % 2 == 0) {
			ans++;
			a[i] /= 2;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 384