akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const long long INF = 1e15;

#include <math.h>
#define PI 3.14159265358979323846264338327950L

bool isPrime(long long x) {
    if (x == 1) return true;
    for (long long i = 2; i*i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

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

vector<long long> common_divisors(long long a, long long b) {
    long long n = gcd(a, b);
    vector<long long> ans;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            if (n / i == i) {
                ans.push_back(i);
            }
            else {
                ans.push_back(n / i);
                ans.push_back(i);
            }
        }
    }
    return ans;
}
vector<int> get_divisors(long long n) {
    vector<int> ans;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            if (i == n / i) {
                ans.push_back(i);
            }
            else {
                ans.push_back(n / i);
                ans.push_back(i);
            }
        }
    }
    sort(ans.rbegin(), ans.rend());
    return ans;
}

bool is_sorted(vector<int> a) {
    int n = a.size();
    for (int i = 0; i < n - 1; i++) {
        if (a[i + 1] < a[i]) return false;
    }
    return true;
}

int mxN = 1e5;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> d(n + 1);
    d[0] = 0;
    int cnt = 1;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        d[i] = d[i - 1] + x;
        if (d[i] <= k) cnt++;
    }
    cout << cnt;
    return 0;
}

Measured memory_bytes: 3632
N,M = map(int,input().split())
sc = [list(map(int,input().split())) for m in range(M)]

for i in range(10**N):
  if len(str(i))==N and all(str(i)[s-1]==str(c) for s,c in sc):
    print(i)
    break
    
else:
  print(-1)

Measured memory_bytes: 3064
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

#define FOR(i, N) for (int i = 0; i < (int)N; i++)
#define FORIN(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
#define DEBUG(...) debug(__LINE__, ":" __VA_ARGS__)

using Pi = pair<int, int>;
using ll = long long;
const int INF = 1 << 28;

string to_string(string s) {
  return s;
}

template <class T>
string to_string(vector<T> v) {
  string ret = "{";
  for (int i = 0; i < v.size() - 1; ++i) {
    ret += to_string(v[i]) + ",";
  }
  if (v.size() > 0) {
    ret += to_string(v.back());
  }
  ret += "}";
  return ret;
}

void debug() {
  cerr << endl;
}

template <class Head, class... Tail>
void debug(Head head, Tail... tail) {
  cerr << to_string(head) << " ";
  debug(tail...);
}

void print() {
  cout << endl;
}

template <class Head, class... Tail>
void print(Head head, Tail... tail) {
  cout << to_string(head);
  print(tail...);
}

void get() {}

template <class Head, class... Tail>
void get(Head& head, Tail&... tail) {
  cin >> head;
  get(tail...);
}

template <class T>
void getv(vector<T>& vec) {
  for (int i = 0; i < vec.size(); ++i)
    cin >> vec[i];
}

int main() {
  int A, B, C;
  get(A, B, C);
  print(max(0, C - (A - B)));
  return 0;
}


Measured memory_bytes: 256
from collections import Counter
def prime_factorize(n):
    a = set()
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a
n = int(input())
input_list = list(map(int,input().split()))
num_count = Counter([prime for num in input_list for prime in prime_factorize(num)])
if len(num_count.values())==0:
    print("pairwise coprime")
    exit()
max_appear = max(num_count.values())
if max_appear == 1:
    print("pairwise coprime")
elif max_appear != n:
    print("setwise coprime")
else:
    print("not coprime")

Measured memory_bytes: 254800
P, Q, R = map(int, input().split())

min = P + Q

if R + Q < min:
    min = R + Q
    
if P + R < min:
    min = P + R

if Q + R < min:
    min = Q + R

if R + P < min:
    min = R + P

if Q + P < min:
    min = Q + P
    
print(min)

Measured memory_bytes: 3064
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<set>
#define mm(a,x) memset(a,x,sizeof(a))
#define sync std::ios::sync_with_stdio(false);std::cin.tie(0)
#define ll long long
using namespace std;
string s;
set<string>st;
int main(void)
{
    sync;
    int n;
    cin>>n;
    for(int i=0;i<n;++i)
    {
        cin>>s;
        st.insert(s);
    }
    cout<<st.size()<<endl;
    return 0;
}

Measured memory_bytes: 19244
#encoding:utf-8 No.0003 2014.9.29
num_of_data = gets.chomp
data = Array.new(num_of_data.to_i)

num_of_data.to_i.times do |i|
 each_sides = gets.split

 each_sides.length.times do |j|
  each_sides[j] = each_sides[j].to_i
 end

 data[i] = each_sides.sort
end

num_of_data.to_i.times do |i|
 if data[i][0] ** 2 + data[i][1] ** 2 == data[i][2] **2
  puts "YES"
 else
  puts "NO"
 end
end

Measured memory_bytes: 6112
import Control.Applicative
import Control.Monad
import System.IO.Unsafe
import Control.Monad.ST
import Data.Functor
import Data.Function
import Data.Monoid
import Data.Maybe
import Data.List
import Data.Foldable (foldMap)
import Data.List.Split
import Data.Bits
import Data.Char
import Data.Ix
import Data.Ratio
import Data.Ord
import Data.Tuple
import Data.Array
import Data.Array.IO
import Data.Array.ST
import Data.IORef
import Data.STRef
 
readInt = read :: String -> Int
readDouble = read :: String -> Double
getInt = readLn :: IO Int
getInts = map readInt . words <$> getLine
getDouble = readLn :: IO Double
sjoin :: (Show a) => [a] -> String
sjoin = unwords . map show
cond :: a -> a -> Bool -> a
cond t f c = if c then t else f
apply2 :: (a -> a -> b) -> [a] -> b
apply2 f [x,y] = f x y
apply3 :: (a -> a -> a -> b) -> [a] -> b
apply3 f [x,y,z] = f x y z
fnBin :: (b -> c -> d) -> (a -> b) -> (a -> c) -> a -> d
fnBin op f g x = op (f x) $ g x
fnTuple :: (a -> b, a -> c) -> a -> (b, c)
fnTuple (f,g) a = (f a, g a)
replace :: (Eq a) => a -> a -> [a] -> [a]
replace x y = map (\z -> if z==x then y else z)
modifyArray :: (Ix i, MArray a e m) => a i e -> i -> (e -> e) -> m ()
modifyArray arr ix f = readArray arr ix >>= writeArray arr ix . f
-- end of templete



main = replicateM 2 getInts >>= print . maximum . map sum

Measured memory_bytes: 3700
#include <stdio.h>
int main(void){
	int W = 0, H = 0, x = 0, y = 0, r = 0;
	scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);
	if (x - r < 0 || y - r<0 || x + r > W || y + r > H){
		printf("No\n");
	}
	else{
		printf("Yes\n");
	}
}

Measured memory_bytes: 2684
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
using namespace std;
const long long int INF = 1e18;
const long long int mod = 1e9+7;

typedef pair<ll, ll> pairs;
typedef vector<pairs> p;

struct Edge{
    ll to, weight;
    Edge(ll t, ll w) : to(t), weight(w){}
};
using graph = vector<vector<ll>>;
using Graph = vector<vector<Edge>>;


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

ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}

ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

// 回文
bool kai(string S){
    bool flag = true;
    for(ll i=0;i<S.size()/2;++i){
        if(S[i] != S[S.size()-i-1]){
            flag = false;
            break;
        }
    }
    return flag;
}
// ---------------------------------------------

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

    for(ll t=0;t<k;++t){
        vector<ll> b(n, 0);
        for(ll i=0;i<n;++i){
            ll l = max((ll)0, i - a[i]);
            ll r = min(n, i + a[i] + 1);

            b[l]++;
            if(r < n){
                b[r]--;
            }
        }

        for(ll i=1;i<n;++i){
            b[i] += b[i-1];
        }

        a = b;
        ll flag = INF;
        for(ll i=0;i<n;++i){
            flag = min(flag, b[i]);
        }
        if(flag == n){
            break;
        }
    }
    for(ll i=0;i<n;++i){
        cout<<a[i]<<' ';
    }
    cout<<endl;

    return 0;
}

Measured memory_bytes: 6356
//#pragma GCC optimize "trapv"
#include<bits/stdc++.h>
#define ll long long int
#define fab(a,b,i) for(int i=a;i<b;i++)
#define pb push_back
#define db double
#define mp make_pair
#define endl "\n"
#define f first
#define se second
#define all(x) x.begin(),x.end()
#define MOD 1000000007
#define BIG 1e10
#define quick ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
ll dp[100005][105];
ll a[105],b[105],n,w;
ll recurse(ll val,int i)
{
	if(val<=0)
		return 0;

	if(i==n)
		return BIG;
	if(dp[val][i]!=-1)
		return dp[val][i];
	dp[val][i]=min(recurse(val,i+1),a[i]+recurse(val-b[i],i+1));

	return dp[val][i];
		


}
int main()
{ quick;

	//ll n,w;
	cin>>n>>w;
	
	fab(0,n,i)
	cin>>a[i]>>b[i];
	memset(dp,-1,sizeof(dp));
	for(int i=100002;i>=0;i--)
	{
			//cout<<recurse(i,0)<<endl;
			if(recurse(i,0)<=w)
				{cout<<i;
			return 0;}
		
	}

	return 0;
}

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

const int MAXN = 3002;

double dp[MAXN][MAXN],P[MAXN];
int vis[MAXN][MAXN],N;

double solve(int pos,int heads){
	
	if(heads < 0) return 0.0;

	if(pos == 0){
		return (heads == 0);
	}

	if(vis[pos][heads]) return dp[pos][heads];
	vis[pos][heads] = 1;

	return dp[pos][heads] =  (P[pos])*solve(pos-1,heads-1) + (1.0 - P[pos])*solve(pos-1,heads);

}

int main(){

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

	double tot = 0;
	for(int heads = 0;heads<=N;heads++){
		int tails = N - heads;
		if(heads > tails) tot += solve(N,heads);
	}

	printf("%.9lf\n",tot);

	return 0;

}

Measured memory_bytes: 105072
import sys
import math
sys.setrecursionlimit(1000000)

def slow_solve(A, B, N):
    ans = 0
    for x in range(1, N+1):
        d = math.floor( (x * A) / B) - A * math.floor(x / B)
        ans = max(ans,d)
    return ans

def solve(A, B, N):
    x = min(N, B - 1)
    d = math.floor( (x * A) / B) - A * math.floor(x / B)
    return d

#
# for A in range(1, 100):
#     print(A)
#     for B in range(1, 100):
#         for N in range(1, 100):
#             if slow_solve(A, B, N) != solve(A, B, N):
#                 print(A, B, N)
#                 print("fail")
#                 print(slow_solve(A, B, N))
#                 print(solve(A, B, N))
#                 exit(1)
#
# print("OK")

if __name__ == "__main__":
    A, B, N = tuple(map(int, input().split(" ")))
    print(solve(A, B, N))


Measured memory_bytes: 9196
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ESequenceSum solver = new ESequenceSum();
        solver.solve(1, in, out);
        out.close();
    }

    static class ESequenceSum {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            // 入力
            long n = Long.parseLong(in.next());
            long x = Long.parseLong(in.next());
            long m = Long.parseLong(in.next());
            long ans = 0;
//        ans += x;
//        long a = (x * x) % m;
//        long cnt = 1;
//        while (true) {
//            if (cnt == n || a % m == 0) break;
//            ans += a;
//            a = (a * a) % m;
//            cnt++;
//        }
//
//        // 出力
//        out.println(ans);
            long[] sum = new long[1000001];
            int[] rem = new int[(int) m];
            int len = 0;
            int r = 0;
            long s = 0;
            while (true) {
                r = (int) (x % m);
                if (rem[r] != 0)
                    break;
                s += r;
                len++;
                rem[r] = len;
                sum[len] = s;
                x = (long) ((long) r * r);
            }
//        debug(r + " " + rem[r] + " " + len + " " + sum[len]);
            int cyc = len - rem[r] + 1;
//        debug(cyc);

            // 周回に入る前
            long a = 0;
            if (rem[r] != 0)
                a = sum[rem[r] - 1];

            // 周回部分
            long b = sum[len];
            if (rem[r] != 0)
                b -= sum[rem[r] - 1];
            n = n - rem[r] + 1;
            long c = n / cyc;

            // 1周に満たない
            long d = n % cyc;
            long e = sum[(int) (rem[r] + d - 1)] - sum[rem[r] - 1];

            ans = a + b * c + e;
            out.println(ans);
        }

    }
}



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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

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

    int3(a, b, c);

    if (a % 2 == b % 2 && b % 2 == c % 2) {
        int yui = max(a, max(b, c));
        cout << -((a - yui) + (b - yui) + (c - yui)) / 2 << endl;
    } else {
        if (a % 2 != b % 2 && a % 2 != c % 2) {
            b++; c++;
        } else if (b % 2 != a % 2 && b % 2 != c % 2) {
            a++; c++;
        } else if (c % 2 != a % 2 && b % 2 != c % 2) {
            a++; b++;
        }
        //cout << a << " " << b << " " << c << endl;
        int yui = max(a, max(b, c));
        cout << -((a - yui) + (b - yui) + (c - yui)) / 2 + 1 << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define inf 10000000000000000
#define mod 1000000007
typedef pair<int, int> P;

bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int mod_pow(int n, int p, int m) {
	if (p == 0) return 1;
	if (p % 2 == 0) {
		int t = mod_pow(n, p / 2, m);
		return (t * t) % m;
	}
	return n * mod_pow(n, p - 1, m) % m;
}

signed main() {
	int n, m, ans = 0;
	cin >> n >> m;
	int sum[100005];
	sum[0] = 0;
	rep(i, n) {
		int a;
		cin >> a;
		sum[i + 1] = sum[i] + a;
	}
	map<int, int>mp;
	rep(i, n + 1) {
		mp[sum[i] % m]++;
	}
	for (auto i = mp.begin(); i != mp.end(); i++) {
		int x = i->second;
		ans += x * (x - 1) / 2;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
  #include "_DEBUG.hpp"
#endif
#define int long long
const int INF = 1LL << 60;

signed main(){

  int n; cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }
  
  int ans = 1000, Min = INF;
  for(int i = 0; i < n; i++){
    if(Min < a[i]){
      int dis = ans / Min;
      ans = ans - dis * Min + dis * a[i];
      Min = a[i];
    }else{
      Min = a[i];
    }
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
const ll mod = 998244353;
ll ans;
int n;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		if (i % 3 && i % 5)ans += i;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3632
n = gets.to_i
row1 = gets.split.map(&:to_i)
row2 = gets.split.map(&:to_i)

max = -Float::INFINITY
(0...n).each do |i|
  x = row1[0..i].inject(0,:+) + row2[i..-1].inject(0,:+)
  max = [x,max].max
end

puts max


Measured memory_bytes: 1788
/*  ex9_1
    potter0723sw  */

#include <stdio.h>
#include <stdlib.h>
//スタックに格納するデータの最大数
#define SIZE 10

//スタックの定義
typedef struct stack{
    int size;
    int count;
    char data[SIZE];
    char *top;
} stack;

//スタックの初期化
void initialize_stack(stack *stk){
    stk->count = 0;
    stk->size = SIZE;
    stk->top = &(stk->data[SIZE]);
}

//データの追加
void push(stack *stk, char elem){
    if(stk->count >= stk->size){
        fprintf(stderr, "Error: stack overflow. (x=%c)\n", elem);
        exit(1);
    }
    else{
        stk->top--;
        *(stk->top) = elem;
        stk->count++;
    }
}

//データの取り出し
char pop(stack *stk){
    char latest;
    if(stk->count <= 0){
        fprintf(stdout, "Error: stack underflow.\n");
        exit(1);
    }
    else{
        latest = *(stk->top);
        stk->top++;
        stk->count--;
        return latest;
    }
}

int main(void){
    int i;
    stack stk;
    char input[11],ans[11];
    //スタックを初期化
    initialize_stack(&stk);
    //配列を初期化（入力で使われていない文字に変更）
    for(i=0; i<11; i++){
        input[i] = 'a';
        ans[i] = 'a';
    }
    scanf("%s", input);
    //iを初期化
    i=0;
    //入力を始めの方から処理
    while(input[i] != '\0'){
        if(input[i] == 'B'){
            if(stk.count != 0){//スタックに何もない場合はpopしない
                pop(&stk);
            }
        }else{
            push(&stk, input[i]);
        }
        i++;
    }
    //スタック内に残った文字を後ろからansに格納
    for(i = stk.count - 1; i >= 0; i--){
        ans[i] = pop(&stk);
    }
    //文字数分だけ出力
    i = 0;
    while(ans[i] != 'a'){
        printf("%c", ans[i]);
        i++;
    }
    //改行出力
    printf("\n");
    return 0;
}

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

using namespace std;

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

    int n;
    string s;

    cin >> n >> s;
    vector<pair<int, int>> cnt(n);
    for (int i = 1; i < n; ++i)
        cnt[i].first = (cnt[i - 1].first + (s[i - 1] == 'W' ? 1 : 0));
    for (int i = n - 2; i >= 0; --i)
        cnt[i].second = (cnt[i + 1].second + (s[i + 1] == 'E' ? 1 : 0));

    int ans = n;
    for (const auto &it : cnt) ans = min(ans, it.first + it.second);
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 2964
// Ballazt
//0a..brute force
//0b..greedy
//1..memorizatton of some sort	remember something cleverly
//2..sort
//3..binary search	keep check a particular solution
//4..dp				repeating strucutre,limited choices
//5..dfs/bfs		matrix with obstacles
//6..correlate to graph in some way		each state is a point
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl "\n"


int main()

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

	ll a[3];

	ll k;

	cin>>a[0]>>a[1]>>a[2]>>k;

	ll b[3]={1,0,-1};


	ll count;
	count=k;
	ll ans=0;

	//cout<<"intial  "<<k<<count<<endl;

	for(int i=0;i<3;i++)
	{
		if(a[i]<count)
		{
			//cout<<"loop 1 ent "<<i<<" "<<count<<" "<<ans<<endl;
			count=count-a[i];
			ans+=b[i]*a[i];
			//cout<<"loop 1 ex "<<i<<" "<<count<<" "<<ans<<endl;
		}

		else if(count<=a[i])
		{
			//cout<<"loop 2 ent "<<i<<count<<" "<<ans<<endl;
			ans+=b[i]*count;
			//cout<<count;
			//cout<<"loop 2 ex "<<i<<count<<" "<<ans<<endl;
			cout<<ans;
			return 0;
		}
	}

	cout<<ans;

	return 0;


}





	

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

/* snippet: useful macros and functions */
#define ARC(i, a, b) for(Int i = (a); i < (b); ++i)
#define RC(i, n) ARC(i, 0, n)
#define ARCH(i, a, b) for(Int i = (a) - 1; i >= (b); --i)
#define RCH(i, n) ARCH(i, n, 0)
template<class T> T ant(const T &a, const T &b){ return a > b ? a : b; }
template<class T> T ont(const T &a, const T &b){ return a < b ? a : b; }
template<class T> T rng(const T &a, const T &b){ return a < b ? b - a : a - b; }
template<class T> void th(T &a, const T &b, T (*f)(const T &, const T &)){ a = f(a, b); }
#define anth(a, b) th(a, b, ant)
#define onth(a, b) th(a, b, ont)

/* snippet: modint library */
template<class T, int MOD>
class Modint{
	T val;
public:
	Modint(T val = 0) : val(val % MOD + (val > 0 ? 0 : MOD)) {}
	operator T(){ return val; }
	Modint &operator+=(const Modint &a){ val += a.val; if(val >= MOD) val -= MOD; return *this; }
	Modint &operator-=(const Modint &a){ val -= a.val; if(val < 0) val += MOD; return *this; }
	Modint &operator*=(const Modint &a){ val = val * a.val % MOD; return *this; }
	void inverse(){T x[2]={MOD,val},a[2]={0,1};int i;for(i=0;x[!i];i^=1){a[i]-=x[i]/x[!i]*a[!i];x[i]=x[i]%x[!i];}if(!i)a[i]+= MOD;val=a[i];}
	Modint &operator/=(Modint a){ a.inverse(); return *this *= a; }
	friend Modint modpow(Modint a, int n){ Modint ret(1); while(n){ if(n & 1) ret *= a; a *= a; n >>= 1; } return ret; }
	friend Modint operator+(Modint a, const Modint &b){ return a += b; }
	friend Modint operator-(Modint a, const Modint &b){ return a -= b; }
	friend Modint operator*(Modint a, const Modint &b){ return a *= b; }
	friend Modint operator/(Modint a, const Modint &b){ return a /= b; }
	friend std::ostream &operator<<(std::ostream &os, const Modint &a){ return os << a.val; }
};

/* snippet: using declarations */
using Int = long long;
using std::cout;
using std::cin;
using std::endl;
using Mint = Modint<long long, 1000000007>;

int main(){
	Int x;
	cin >> x;
	Int k = 100;
	for(Int i = 0;; ++i){
		k += k / 100;
		if(k >= x){
			cout << i + 1 << endl;
			return 0;
		}
	}
}


Measured memory_bytes: 3636
fn main() {
    let v = read_vec::<i32>();
    let (n, y) = (v[0], v[1] / 1000);
    for a in 0..(n + 1) {
        for b in 0..(n + 1) {
            let c = n - a - b;
            if c < 0 {
                break;
            }
            if 10 * a + 5 * b + c == y {
                println!("{} {} {}", a, b, c);
                return;
            }
        }
    }
    println!("{} {} {}", -1, -1, -1);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}

Measured memory_bytes: 4352
import copy

n = int(input())

a = list(map(int,input().split()))
for i in range(n):
    a[i] -= i+1

asort = copy.copy(a)
asort.sort()

if n % 2 == 1:
    b = asort[(n//2)]
else:
    b = (asort[(n//2)-1] + asort[(n//2)]) // 2 + (asort[(n//2)-1] + asort[(n//2)]) % 2

ans = 0

for i in range(n):
    ans += abs(a[i]-b)

print(ans)

Measured memory_bytes: 31928
const input = require("fs").readFileSync("/dev/stdin", "utf8");

const data = input.split('\n')[0].split(' ');
const N = +data[0];
const L = +data[1];

const total = (n) => {
  return Array(n).fill(null).reduce((sum, _, i) => sum + i, 0);
};

const value = (n, l, remove) => {
  return l * (n - 1) + total(n) - remove;
};

if (L >= 0) {
  console.log(value(N, L, 0));
} else if(-L >= N) {
  console.log(value(N, L, N - 1));
} else {
  console.log(value(N, L, -L));
}


Measured memory_bytes: 21064
import java.io.*;
import java.util.*;
public class Main {
static long[][] memo;
static int I,J;
static String h,s;
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
	   h=sc.nextLine();
	   s=sc.nextLine();
	   I=h.length();
	   J=s.length();
	   memo=new long[I][J];
	   for(long []a:memo)
		   Arrays.fill(a,-1);
	  
	  
	   trace(0,0);
	}
	static void trace(int i,int j) {
		if(i==I || j==J)
			return ;
		
		
		if(i==I-1 && j==J-1) {
			if(s.charAt(j)==h.charAt(i))
				System.out.print(s.charAt(j));
			return;
			}
		if(i==I-1) {
			if(s.charAt(j)==h.charAt(i))
				System.out.print(s.charAt(j));
			else
				trace(i,j+1);
			return;
		}
		if(j==J-1) {
			if(s.charAt(j)==h.charAt(i))
				System.out.print(s.charAt(j));
			else
				trace(i+1,j);
			return;}
		if(h.charAt(i)==s.charAt(j)) {
			System.out.print(s.charAt(j));
			trace(i+1,j+1);
			return;
		}
		if(dp(i+1,j)>dp(i,j+1))
			trace(i+1,j);
		else
			trace(i,j+1);
			
	}
	static long dp(int i,int j) {
		if(i==I || j==J)
			return 0;
		if(memo[i][j]!=-1)
			return memo[i][j];
		if(i==I-1 && j==J-1) {
			if(s.charAt(j)==h.charAt(i))
				return memo[i][j]=1;
			return memo[i][j]=0;}
		if(i==I-1) {
			if(s.charAt(j)==h.charAt(i))
				return memo[i][j]=1;
			return memo[i][j]=dp(i,j+1);
		}
		if(j==J-1) {
			if(s.charAt(j)==h.charAt(i))
				return memo[i][j]=1;
			return memo[i][j]= dp(i+1,j);}
		if(h.charAt(i)==s.charAt(j)) {
			return memo[i][j]=1+dp(i+1,j+1);
		}
		return memo[i][j]=Math.max(dp(i,j+1),dp(i+1,j));
	}
	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}

Measured memory_bytes: 133608
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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; }



int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(25);

  int n;
  string s;
  cin >> n >> s;

  string a = s.substr(0, n), b = s.substr(n);
  reverse(b.begin(), b.end());
  map<pair<string, string>, ll> ma, mb;
  rep(i, (1 << n)) {
    pair<string, string> pa = {"", ""}, pb = {"", ""};
    rep(j, n) {
      if (i >> j & 1) {
        pa.first += a[j];
        pb.first += b[j];
      }
      else {
        pa.second += a[j];
        pb.second += b[j];
      }
    }
    ma[pa]++;
    mb[pb]++;
  }
  ll ans = 0;
  for (auto it = ma.begin(); it != ma.end(); it++) {
    ans += it->second * mb[it->first];
  }
  cout << ans << '\n';





  
  return 0;
}

Measured memory_bytes: 108288
#include <stdio.h>
int main(void){
    int h,m,hh,mm,k;
    scanf("%d%d%d%d%d",&h,&m,&hh,&mm,&k);
    h=h*60;
    h+=m;
    hh=hh*60;
    hh+=mm;
    h=hh-h;
    h-=k;
    printf("%d\n",h);
    return 0;
    
}


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


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

const int oo = 1e9 + 7;
const int mod = 1e9 + 7;


int main (){
    char a,b;
    cin >>a >> b;
    if (a == 'H'){
        cout << b << endl;
    }
    else {
        cout << (b == 'H'? 'D' : 'H') << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const long long LINF = 1e18;
const long long MOD = 1e9 + 7;

using ll = long long;
template <ll MOD = 1000000007>
struct Mint{
    ll x;

    Mint() : x(0) {}
    Mint(ll t){
        x = t % MOD;
        if(x < 0) x += MOD;
    }
    
    Mint pow(ll n){
        Mint res(1), t(x);
        while(n > 0){
            if(n & 1) res *= t;
            t *= t;
            n >>= 1;
        }
        return res;
    }

    Mint inv() const {
        ll a = x, b = MOD, u = 1, v = 0, t;
        while(b > 0){
            t = a / b;
            a -= t * b;
            swap(a, b);
            u -= t * v;
            swap(u, v);
        }
        return Mint(u);
    }

    Mint & operator += (Mint a){
        x += a.x;
        if(x >= MOD) x -= MOD;
        return *this;
    }
    Mint & operator -= (Mint a){
        x += MOD - a.x;
        if(x >= MOD) x -= MOD;
        return *this;
    }
    Mint & operator *= (Mint a){
        x = 1LL * x * a.x % MOD;
        return *this;
    }
    Mint & operator /= (Mint a){
        return (*this) *= a.inv();
    }

    Mint operator + (Mint a) const { return Mint(x) += a; }
    Mint operator - (Mint a) const { return Mint(x) -= a; }
    Mint operator * (Mint a) const { return Mint(x) *= a; }
    Mint operator / (Mint a) const { return Mint(x) /= a; }

    Mint operator - () const{ return Mint(-x); }

    bool operator == (const Mint a){ return x == a.x; }
    bool operator != (const Mint a){ return x != a.x; }
    bool operator < (const Mint a){ return x < a.x; }

    friend ostream & operator << (ostream & os, const Mint &a){
        return os << a.x;
    }

    friend istream & operator >> (istream & is, Mint &a){
        ll t;
        is >> t;
        a = Mint<MOD>(t);
        return (is);
    }
};

signed main(){
    int n;
    cin >> n;
    vector<int> man[n];
    REP(i,n){
        REP(j,n){
            int a;
            cin >> a;
            if(a == 1) man[i].emplace_back(1 << j);
        }
    }
    Mint<> dp[1 << n];
    dp[0] = 1;
    for(int S = 0; S < (1 << n) - 1; S++){
        int i = __builtin_popcount(S);
        for(auto woman : man[i]){
            if(S & woman) continue;
            dp[S | woman] += dp[S];
        }
    }
    cout << dp[(1 << n) - 1] << endl;
    return 0;
}

Measured memory_bytes: 16640
using System;
using System.Linq;

namespace ABC137A
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] AB = CIN.IntArray();
            Console.WriteLine(Math.Max(AB[0] + AB[1], Math.Max(AB[0] - AB[1], AB[0] * AB[1])));
        }
    }

    internal static class CIN
    {
        public static string String()
        {
            return Console.ReadLine();
        }

        public static int Int()
        {
            return int.Parse(Console.ReadLine());
        }

        public static int[] IntArray()
        {
            return Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        }

        public static long Long()
        {
            return long.Parse(Console.ReadLine());
        }

        public static long[] LongArray()
        {
            return Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
        }

        public static double[] DoubleArray()
        {
            return Console.ReadLine().Split(' ').Select(double.Parse).ToArray();
        }
    }
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(long i = 0; i < n; i++)
#define erep(i, n) for(long i = 1; i <= n; i++)
#define all(a) a.begin(), a.end()
#define show(ans)  cout << ans << endl;
const long MOD = 1000000007;


int main() {string n;
cin >> n;
rep(i, n.size()){
    if(n[i] == '1') n[i] = '9';
    else n[i] = '1';
}


show(n);
  return 0;
 
}



Measured memory_bytes: 256
N = gets.chomp.to_i
a = gets.chomp.split.map(&:to_i)

cnt = 0
flag = true
while flag do
    flag = false
    (N- 1).downto(1) do |j|
        if a[j] < a[j - 1] then
            tmp = a[j]
            a[j] = a[j - 1]
            a[j - 1] = tmp
            
            cnt += 1
            flag = true
        end
    end
end

puts a.join(' ')
puts cnt


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

signed main() {
  int n; cin >> n;
  int s[n];
  for(int i = 0; i < n; i++) cin >> s[i];

  int q, key, res = 0; cin >> q;
  for(int i = 0; i < q; i++) {
    cin >> key;
    bool flag = false;
    // l = left, r = right
    int l = 0, r = n;
    while(l < r) {
      int mid = (l + r) / 2;
      if(s[mid] == key) {
        flag = true;
        break;
      } else if(key < s[mid]) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    if(flag) res++;
  }

  cout << res << endl;
}



Measured memory_bytes: 3392
/*
#include<rabbit>;
using blueHulkStress;
using AceOfSpades;
*/
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
const double PI = acos(-1.0);
const double EPS = (1e-9);
typedef long long ll;
typedef unsigned long long ull;
#define flush fflush(stdout), cout.flush()
#define all(v) ((v).begin()),((v).end())
#define rall(v) ((v).rbegin()),((v).rend())
#define clr(v,line) memset(v,line,sizeof(v))
#define rep(i,n) for(int(i)=0;(i)<(int)(n);(i)++)
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lcm(a,b) (a*(b/__gcd(a,b)))
#define P 1000000007
#define endl '\n'
const int dx[] = {1,-1,0,0,1,-1,1,-1};
const int dy[] = {0,0,1,-1,1,-1,-1,1};
const int dxhorse[] = {-2,-2,-1,-1,1,1,2,2};
const int dyhorse[] = {1,-1,2,-2,2,-2,1,-1};

int N, arr[101];

int computeCost(int N, int X) 
{ 
    int cost = 0; 
    for (int i = 0; i < N; i++) 
        cost += (arr[i] - X) * (arr[i] - X); 
    return cost; 
} 

int solve() 
{ 
    int low, high; 
    low = high = arr[0]; 
    for (int i = 0; i < N; i++) { 
        if (low > arr[i]) 
            low = arr[i]; 
        if (high < arr[i]) 
            high = arr[i]; 
    } 
  
    while ((high - low) > 2) { 
        int mid1 = low + (high - low) / 3; 
        int mid2 = high - (high - low) / 3; 
  
        int cost1 = computeCost(N, mid1); 
        int cost2 = computeCost(N, mid2); 
        if (cost1 < cost2) 
            high = mid2; 
        else
            low = mid1; 
    } 
    return computeCost(N, (low + high) / 2); 
} 
int main(int argc, char const *argv[])
{
	
	cin>>N;
	rep(i,N)cin>>arr[i];
	cout<<solve();
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
int a[10000],i=0,j;

 for(i = 0;i < 10000;i++){
scanf("%d",&a[i]);

 if(a[i] == 0){
   break;
 }
 }

for(j = 0;j < i;j++){
printf("Case %d: %d\n",j+1,a[j]);
}

return 0;
}



Measured memory_bytes: 2040
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
using P = pair<int,int>;
 
int main(){
	int N;
    cin >> N;
    int ans = N * (N + 1) / 2;
    cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;
import java.util.Collections;


public class Main{
   
   

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int min=100000;
        for(int i=1;i<N;i++){
            int sum=0;
            int a=N-i;
            String aa=String.valueOf(a);
            String bb=String.valueOf(i);
            for(int j=0;j<aa.length();j++){
                sum+=Integer.parseInt(""+aa.charAt(j));
            }
            for(int j=0;j<bb.length();j++){
                sum+=Integer.parseInt(""+bb.charAt(j));
            }
            if(sum<min){
                min=sum;
            }
            


        }
        System.out.println(min);


        
        

    }

        
        
    }


Measured memory_bytes: 61800
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    n,m = map(int,input().split())
    s = list(map(int,input().split()))
    t = list(map(int,input().split()))
    
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    if s[0] == t[0]:
        dp[1][1] = 1
    else:
        dp[1][1] = 0
    for i in range(n):
        for j in range(m):
            if i == j == 0:
                continue
            if s[i] == t[j]:
                dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j] + 1)%MOD
            else:
                dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j] - dp[i][j])%MOD
    print((dp[-1][-1] + 1)%MOD)

if __name__ =='__main__':
    main()   


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

void input_matrix(int n, int m, vector<vector<int>> &matrix)
{
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      cin >> matrix.at(i).at(j);
    }
  }
}

void print_result(vector<vector<int>> &a, vector<vector<int>> &b)
{
  for (int n = 0; n < a.size(); n++)
  {
    for (int l = 0; l < b.at(0).size(); l++)
    {
      long long sum = 0;
      for (int m = 0; m < b.size(); m++)
      {
        sum += a.at(n).at(m) * b.at(m).at(l);
      }
      cout << sum;
      if (l != b.at(0).size() - 1)
      {
        cout << ' ';
      }
      else
      {
        cout << endl;
      }
    }
  }
}

int main()
{
  int n, m, l;
  cin >> n >> m >> l;

  vector<vector<int>> a(n, vector<int>(m));
  vector<vector<int>> b(m, vector<int>(l));
  input_matrix(n, m, a);
  input_matrix(m, l, b);

  print_result(a, b);
}



Measured memory_bytes: 3176
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S):

    W = 0
    E = S.count('E')
    ans = E + W
    for s in S:
        if s == 'E':
            E -= 1

        ans = min(E + W, ans)

        if s == 'W':
            W += 1

    return ans


def main():
    N = read_int()
    S = read_str()
    print(slv(N, S))


if __name__ == '__main__':
    main()


Measured memory_bytes: 6732
#include "bits/stdc++.h"
using namespace std;
using ll     = long long;
using pii    = pair<int, int>;
using pll    = pair<ll, ll>;
using vi     = vector<int>;
using vl     = vector<ll>;
using vvi    = vector<vi>;
using vvl    = vector<vl>;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}
template <class C>
void print(const C &c, std::ostream &os = std::cout) {
    std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, " "));
    os << std::endl;
}

// calculates nCk
struct CombinationD {
    vector<vector<ll>> fac;
    CombinationD(ll maxN) {
        fac.resize(maxN + 2, vector<ll>(maxN + 2, 0));
        fac[0][0] = 1;
        for (int i = 1; i <= maxN; ++i) {
            fac[i][0] = fac[i - 1][0];
            for (int j = 1; j <= i + 1; ++j) {
                fac[i][j] = (fac[i - 1][j] + fac[i - 1][j - 1]);
            }
        }
    }
    ll operator()(ll n, ll k) { return fac[n][k]; }
};

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    vl v(n);
    map<ll, int> cnt;
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
        cnt[v[i]]++;
    }
    cout << fixed << setprecision(10);
    sort(v.begin(), v.end(), greater<ll>());
    double mean = 0;
    ll curr    = -1;
    int idx     = -1;
    for (int i = 0; i < a; ++i) {
        mean += v[i];
        if (curr != v[i]) {
            curr = v[i];
            idx  = i;
        }
    }
    mean /= double(a);
    ll used = a - 1 - idx + 1;
    ll tot  = cnt[curr];
    CombinationD nCk(50);
    if (v[0] == v[a - 1]) {
        tot    = cnt[curr];
        ll num = 0;
        for (int i = a; i <= min(ll(b), tot); ++i) {
            num += nCk(tot, i);
        }
        cout << mean << "\n";
        cout << num << "\n";
        return 0;
    }
    ll num = nCk(tot, used);
    cout << mean << "\n";
    cout << num << "\n";
    return 0;
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/optional.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>

void Main()
{
	int K;
	std::cin >> K;
	std::vector<boost::optional<int>> dp(K);
	dp[1] = 1;
	std::deque<std::pair<int, int>> deque;
	deque.emplace_front(10, 1);
	deque.emplace_back(2, 2);
	while (deque.size())
	{
		auto top = deque.front();
		deque.pop_front();
		auto v = top.first % K;
		auto d = top.second;
		if (dp[v])
		{
			continue;
		}
		dp[v] = d;
		deque.emplace_front(10 * v, d);
		deque.emplace_back(v + 1, d + 1);
	}
	std::cout << *dp[0] << std::endl;
}

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


Measured memory_bytes: 1920
#include <stdio.h>
#include <iostream>
#include <string>

using namespace std;

int main() {
	int n;
	string d;
	int kari;

	while (1) {
		cin >> n;
		if (n == 0) {
			break;
		} else {
			cin >> d;
			int ba = 0;
			int hito[10] = {0};
			int t;
			for (int i = 0; i < 100; i++) {
				t = i % n;
				if (d[i] == 'S') {
					ba = ba + hito[t] + 1;
					hito[t] = 0;
				} else if (d[i] == 'L') {
					hito[t] = hito[t] + ba + 1;
					ba = 0;
				} else {
					hito[t]++;
				}
			}

			for (int i = n-1; i >= 0; i--) {
				for (int j = 0; j < i; j++) {
					if (hito[j] > hito[j+1]) {
						kari = hito[j];
						hito[j] = hito[j+1];
						hito[j+1] = kari;
					}
				}
			}

			for (int i = 0; i < n; i++) {
				cout << hito[i] << " ";
			}
			cout << ba << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1204
/*
O(EV^2) 実際はこれより早い

参考
https://ei1333.github.io/luzhiled/snippets/graph/dinic.html
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;

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

template<typename T>
struct Dinic{
    struct edge{
        int to;
        T cap;
        int rev;
    };
    const T inf;
    const T zero;
    int sz;
    vector< vector<edge> > graph;
    vector<int> dist,iter;

    Dinic(const int n,const T inf,const T zero) : inf(inf),zero(zero),graph(n),sz(n){}

    void add_edge(const int from,const int to,const T cap){
        graph[from].emplace_back((edge){to,cap,(int)graph[to].size()});
        graph[to].emplace_back((edge){from,0,(int)graph[from].size()-1});
    }

    bool bfs(int s,int t){
        dist.assign(sz,-1);
        queue<int> que;
        dist[s]=0;
        que.push(s);
        while(!que.empty() && dist[t]==-1){
            int now=que.front();
            que.pop();
            for(auto &e:graph[now]){
                if(e.cap>0 && dist[e.to]==-1){
                    dist[e.to]=dist[now]+1;
                    que.push(e.to);
                }
            }
        }
        return dist[t]!=-1;
    }

    T dfs(int idx,const int t,T flow){
        if(idx==t) return flow;
        for(int &i=iter[idx];i<graph[idx].size();i++){
            edge &e=graph[idx][i];
            if(e.cap>0 && dist[idx]<dist[e.to]){
                T d=dfs(e.to,t,min(flow,e.cap));
                if(d>0){
                    e.cap-=d;
                    graph[e.to][e.rev].cap+=d;
                    return d;
                }
            }
        }
        return zero;
    }

    T max_flow(int s,const int t){
        T ret=0;
        while(bfs(s,t)){
            iter.assign(sz,0);
            T f=0;
            while((f=dfs(s,t,inf))>zero) ret+=f;
        }
        return ret;
    }
};

signed main(){
    int v,e;
    cin>>v>>e;
    Dinic<int> d(v,(1<<30),0);
    for(int i=0;i<e;i++){
        int s,t,c;
        cin>>s>>t>>c;
        d.add_edge(s,t,c);
    }
    cout<<d.max_flow(0,v-1)<<endl;
}


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

class Dice
{
private:
  /*
    pip[0] = top, pip[1] = south, pip[2] = east
    pip[3] = bottom, pip[4] = north, pip[5] = west
  */
  int pip[6];
public:
  enum { TOP, SOUTH, EAST, BOTTOM, NORTH, WEST };

  Dice(int top = 1, int south = 2, int east = 3)
  {
    pip[TOP] = top;
    pip[SOUTH] = south;
    pip[EAST] = east;
    pip[BOTTOM] = 7 - top;
    pip[NORTH] = 7 - south;
    pip[WEST] = 7 - east;
  }

  // east:+, west:-
  void rotateX(int r)
  {
    if (r < 0)
      r += 4 * (-(r/4) + 1);
    r %= 4;
    for (int i = 0; i < r; ++i) {
      int tmp = pip[TOP];
      pip[TOP] = pip[WEST];
      pip[WEST] = pip[BOTTOM];
      pip[BOTTOM] = pip[EAST];
      pip[EAST] = tmp;
    }
  }

  // north:, south:-
  void rotateY(int r)
  {
    if (r < 0)
      r += 4 * (-(r/4) + 1);
    r %= 4;
    for (int i = 0; i < r; ++i) {
      int tmp = pip[TOP];
      pip[TOP] = pip[SOUTH];
      pip[SOUTH] = pip[BOTTOM];
      pip[BOTTOM] = pip[NORTH];
      pip[NORTH] = tmp;
    }
  }

  // right:+, left:-
  void rotateZ(int r)
  {
    if (r < 0)
      r += 4 * (-(r/4) + 1);
    r %= 4;
    for (int i = 0; i < r; ++i) {
      int tmp = pip[SOUTH];
      pip[SOUTH] = pip[EAST];
      pip[EAST] = pip[NORTH];
      pip[NORTH] = pip[WEST];
      pip[WEST] = tmp;
    }
  }
 
  inline int get(int p) const
  {
    return pip[p];
  } 
};

int main()
{
  ios::sync_with_stdio(false);
  int n;
  while (cin >> n) {
    if (n == 0)
      break;

    int ans = 1;
    Dice dice;
    for (int i = 0; i < n; ++i) {
      string op;
      cin >> op;
      if (op == "North")
	dice.rotateY(1);
      else if (op == "East")
	dice.rotateX(1);
      else if (op == "South")
	dice.rotateY(-1);
      else if (op == "West")
	dice.rotateX(-1);
      else if (op == "Right")
	dice.rotateZ(1);
      else 
	dice.rotateZ(-1);
      ans += dice.get(Dice::TOP);
    }
    cout << ans << endl;
  }
  return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<int>data(n);
  vector<long long>sum(n+1,0);
  long long ans = 0;
  for(int i = 0;i < n;i++){
    int a;
    cin >> a;
    data[i] = a;
    sum[a]++;
    ans += sum[a]-1;
  }
  for(int i = 0;i < n;i++){
    cout << ans-(sum[data[i]]-1) << endl;
  }
}


Measured memory_bytes: 4992