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

int main(){
  int n;
  int c[500],f[500];
  long long s[500],s1[500];

  scanf("%d",&n);
  for(int i=0;i<n-1;i++){
    scanf("%d%lld%d",&c[i],&s[i],&f[i]);
  }
  s[n-1]=0;
  c[n-1]=0;
  f[n-1]=0;
  
  for(int i=0;i<n-2;i++){
    long long ans=s[i]+c[i];
    
    for(int j=i;j<n-2;j++){
      s1[j+1]=s[j+1];
      if(j<n-2&&ans>s[j+1]){
	while(ans>s1[j+1]){
	  s1[j+1]=s1[j+1]+f[j+1];
	  
	}
	ans=s1[j+1]+c[j+1];
      }
      else{
	ans=s[j+1]+c[j+1];
      }
    }
    printf("%lld\n",ans);
  }
  printf("%lld\n",c[n-2]+s[n-2]);
  printf("0\n");
	
	
    
  return 0;
}


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

using namespace std;
using ll = long long;

int main() {
	int x[4] = { 0, 4, 6, 8 };
	string a = "AKIHABARA";

	string s;
	cin >> s;
	for (int i = 0; i < (1<<4); ++i) {
		string tmp = "";
		int cnt = 0;
		for (int j = 0; j < a.size(); ++j) {
			if ((j == x[cnt]) && (i>>cnt & 1)) {
				continue;
			}
			if (j > x[cnt]) { ++cnt; }
			tmp += a[j];
		}
		cerr << "tmp = " << tmp << endl;
		if (tmp == s) {
			cout << "YES" << endl;
			return 0;
		}
	}

	cout << "NO" << endl;
	
	return 0;
}


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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int temp;
	for (int i=1; i<=5; ++i) {
		cin >> temp;
		if (!temp) {
			cout << i << '\n';
			return 0;
		}

	}
}


Measured memory_bytes: 3548
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from math import ceil
    d,g=map(int,input().split())
    g//=100
    P=[0]*d
    C=[0]*d
    for i in range(d):
        p,c=map(int,input().split())
        c//=100
        P[i],C[i]=p,c

    def check(S):
        comp=[0]*d
        for i in range(d):
            comp[i]=S&1
            S>>=1
        score=0
        cnt=0
        for i in range(d):
            if(comp[i]):
                score+=(i+1)*P[i]+C[i]
                cnt+=P[i]

        # コンプした問題だけでクリアしていれば返す
        if(score>=g):
            return cnt

        # そうでなければ、解いてない問題のうち最大点数のものを何問解くか考える
        idx=-1
        for i in range(d-1,-1,-1):
            if(comp[i]==0):
                idx=i
                break

        if(idx==-1):
            return False


        k=ceil((g-score)/(idx+1))
        if(k<P[idx]):
            return cnt+k
        else:
            return False


    # completeする問題を全て試す
    ans=INF
    for S in range(2**d):
        score=check(S)
        if(score): ans=min(score,ans)
    print(ans)
resolve()

Measured memory_bytes: 40048
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

n = input().rstrip()
k = int(input())

# dp[tight-loose][k][i-th item]
dp = [[[0] * len(n) for _ in range(k+1)] for _ in range(2)]

for i, ch in enumerate(n): 
    item = int(ch)
    if i == 0:
        # tight -> tight
        dp[0][1][0] = 1
        # tight -> loose with 0
        dp[1][0][0] = 1
        # tight -> loose without 0
        dp[1][1][0] = max(0, item - 1)
        continue
    for j in range(k+1):
        if item != 0:
            # tight -> loose with 0
            dp[1][j][i] += dp[0][j][i-1]
            # loose -> loose with 0
            dp[1][j][i] += dp[1][j][i-1]
            if j < k:
                # tight -> tight
                dp[0][j+1][i] += dp[0][j][i-1] 
                # tight -> loose without 0
                dp[1][j+1][i] += dp[0][j][i-1] * max(0, (item - 1))
                # loose -> loose without 0
                dp[1][j+1][i] += dp[1][j][i-1] * 9 
        else:
            # tight -> tight with 0
            dp[0][j][i] += dp[0][j][i-1] 
            # loose -> loose with 0
            dp[1][j][i] += dp[1][j][i-1] 
            if j < k:
                # loose -> loose without 0
                dp[1][j+1][i] += dp[1][j][i-1] * 9

print(dp[0][k][-1] + dp[1][k][-1])

Measured memory_bytes: 3188
// https://atcoder.jp/contests/abc113/tasks/abc113_b
"use strict"
function Main(input) {
  const params = input.split('\n');
  const n = params[0];
  const t = params[1].split(' ')[0];
  const a = params[1].split(' ')[1];
  const hs = params[2].split(' ');

  let currentTemperatureDifference = Infinity;
  let currentIndex = 0;
  hs.forEach((h, index) => {
    const targetTemperatureDifference = Math.abs(a - (t - (h * 0.006)));
    if(targetTemperatureDifference < currentTemperatureDifference) {
      currentTemperatureDifference = targetTemperatureDifference;
      currentIndex = index;
    }
  });

  console.log(currentIndex + 1);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7628
import copy


# k = 1の場合の転倒数を求める
def bubble_sort(A):
    cnt = 0
    for i in range(len(A)):
        for j in range(len(A) - 1, i, -1):
            if A[j] < A[j - 1]:
                A[j], A[j - 1] = A[j - 1], A[j]
                cnt += 1
    return cnt


n, k = map(int, input().split())
a = list(map(int, input().split()))
# aはソートされてしまうので、元の並びを複製する
b = copy.deepcopy(a)
# k = 1の場合の転倒数が初項となる等差数列
initial = bubble_sort(a)
ans = initial
bigger = [0] * n
# bigger[i]: リストaに含まれる要素1つに着目した際に、その要素よりも小さい要素の個数
# ex. a = [1,3,4] のとき、 bigger[1] = 1
# 3より大きいのは4のみであるため。
for i in range(n):
    cnt = 0
    for j in b:
        if b[i] > j:
            cnt += 1
    bigger[i] = cnt
# biggerの合計が公差となる
d = sum(bigger)
# 等差数列の和の公式
ans = k * (2 * initial + d * (k - 1)) // 2
print(ans % (10 ** 9 + 7))

Measured memory_bytes: 3700
#include <bits/stdc++.h>
using namespace std;
#define rep2(i, m, n) for(int i=int(m); i<int(n); ++i)
#define drep2(i, m, n) for(int i=int(m-1); i>=int(n); --i)
#define rep(i, n) rep2(i, 0, n)
#define drep(i, n) drep2(i, n, 0)
#define all(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using Vbo = vector<bool>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using VVbo = vector<Vbo>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << " "; return os; }
template<typename T> inline int count_between(vector<T> &a, T l, T r) { return lower_bound(all(a), r) - lower_bound(all(a), l); } // [l, r)
inline int Log2(ll x) { int k; for (k = 0; x > 0; ++k) x >>= 1; return k; } // number of binary digits
const int INF  = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS   = 1e-10;
const int MOD  = int(1e9)+7;


int main() {
  ll n, q; cin >> n >> q;
  string s; cin >> s;
  vector<pair<char, int>> m(q);
  rep(i, q) {
    char x; cin >> m[i].first >> x;
    if (x == 'L') m[i].second = -1;
    if (x == 'R') m[i].second = 1;
  }

  auto fun = [&] (ll x) {
    if (x < 0) return false;
    if (x >= n) return true;
    rep(i, q) {
      if (s[x] == m[i].first) x += m[i].second;
      if (x < 0) return false;
      if (x >= n) return true;
    }
    return true;
  };

  ll ans = n;

  ll ok = n+2;
  ll ng = -1;
  while (llabs(ok - ng) > 1) {
    ll mid = (ok + ng) / 2;
    if (fun(mid)) ok = mid;
    else ng = mid;
  }
  ans -= ok;


  auto fun2 = [&] (ll x) {
    if (x >= n) return false;
    if (x < 0) return true;
    rep(i, q) {
      if (s[x] == m[i].first) x += m[i].second;
      if (x >= n) return false;
      if (x < 0) return true;
    }
    return true;
  };

  ok = -1;
  ng = n+2;
  while (llabs(ok - ng) > 1) {
    ll mid = (ok + ng) / 2;
    if (fun2(mid)) ok = mid;
    else ng = mid;
  }
  ans -= n-1-ok;

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2196
/*
░░░░░░░░░░░░░░░░▄▄█▀▀██▄▄░░░░░░░
░░░░░░░░░░░░░▄█▀▀░░░░░░░▀█░░░░░░
░░░░░░░░░░░▄▀░░░░░░░░░░░░░█░░░░░
░░░░░░░░░▄█░░░░░░░░░░░░░░░█░░░░░
░░░░░░░██▀░░░░░░░▄▄▄░░▄░█▄█▄░░░░
░░░░░▄▀░░░░░░░░░░████░█▄██░▀▄░░░
░░░░█▀░░░░░░░░▄▄██▀░░█████░██░░░
░░░█▀░░░░░░░░░▀█░▀█▀█▀▀▄██▄█▀░░░
░░░██░░░░░░░░░░█░░█░█░░▀▀▄█▀░░░░
░░░░█░░░░░█░░░▀█░░░░▄░░░░░▄█░░░░
░░░░▀█░░░░███▄░█░░░░░░▄▄▄▄█▀█▄░░
░░░░░▀██░░█▄▀▀██░░░░░░░░▄▄█░░▀▄░
░░░░░░▀▀█▄░▀▄▄░▄░░░░░░░███▀░░▄██
░░░░░░░░░▀▀▀███▀█▄░░░░░█▀░▀░░░▀█
░░░░░░░░░░░░▄▀░░░▀█▄░░░░░▄▄░░▄█▀
░░░▄▄▄▀▀▀▀▀█▀░░░░░█▄▀▄▄▄▄▄▄█▀▀░░
░▄█░░░▄██▀░░░░░░░░░█▄░░░░░░░░░░░
█▀▀░▄█░░░░░░░░░░░░░░▀▀█▄░░░░░░░░
█░░░█░░░░░░░░░░░░░░░░░░█▄░░░░░░░
*/
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define x first
#define y second
#define pi pair <int, int>
#define vi vector <int>
//#define =1e9 =(int)1e9
const ll mod = 1000000007;
const ll nmax=1000003;
#define int ll
int n, q;
int h[100001];
bool ctrl=1;

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n;
    for(int i=1; i<=n; i++) cin>>h[i];
    for(int i=1; i<=n; i++){
        if(h[i-1]<h[i]) h[i]--;
        //cout<<h[i]<<" ";
    }
    for(int i=1; i<=n; i++) if(h[i-1]>h[i]) ctrl=0;
    if(ctrl) cout<<"Yes"; else cout<<"No";
}


Measured memory_bytes: 1024
import java.math.BigDecimal

fun gcd(a: BigDecimal, b: BigDecimal): BigDecimal {
    var x = a
    var y = b
    while (true) {
        if (y.compareTo(x) < 0) {
            val z = x
            x = y
            y = z
        }
        if (x.signum() == 0) break
        y %= x
    }
    return y
}

fun lcm(a: BigDecimal, b: BigDecimal) = a * b / gcd(a, b)

fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    var tlcm = BigDecimal(readLine())
    repeat(n - 1) {
        val t = BigDecimal(readLine())
        tlcm = lcm(t, tlcm)
    }
    println(tlcm.toPlainString())
}


Measured memory_bytes: 33848
import java.util.*;
import java.math.*;
public class Main{

	static int INF = 2 << 27;
	static int m;
	static int n;
	static int k;
	static int d;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int n = sc.nextInt();
			if(n == 0) break;
			Data[] data = new Data[n];
			for(int i = 0; i < n; i++) {
				data[i] = new Data(sc.nextInt(),sc.nextInt(),sc.nextInt(),sc.nextInt());
			}
			for(int i = 0; i < n; i++) {
				for(int j = i + 1; j < n; j++) {
					boolean check = check(data,i,j);
					if(check) data[j].up |= (1 << i);
				}
			}
			boolean[] dp = new boolean[1 << n];
			dp[0] = true;
			for(int i = 0; i < dp.length; i++) {
				if(!dp[i]) continue;
				ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
				for(int j = 0; j < 5; j++) {
					list.add(new ArrayList<Integer>());
				}
				for(int j = 0; j < n; j++) {
					if((i & (1 << j)) != 0 || (i & data[j].up) != data[j].up) continue;
					list.get(data[j].c).add(j);
				}
				for(int j = 1; j < 5; j++) {
					for(int k = 0; k < list.get(j).size()-1; k++) {
						for(int l = k + 1; l < list.get(j).size(); l++) {
							ArrayList<Integer> lX = list.get(j);
							int next = i | (1 << lX.get(k) | (1 << lX.get(l)));
							dp[next] = true;
						}
					}
				}
			}
			int max = 0;
			for(int i = 0; i < dp.length; i++) {
				if(dp[i]) max = Math.max(max, Integer.bitCount(i));
			}
			System.out.println(max);
			
		}
	}
	static boolean check(Data[] data, int a, int b) {
		int dis = (int)(Math.pow(data[a].x - data[b].x, 2) + Math.pow(data[a].y - data[b].y, 2));
		return dis < Math.pow(data[a].r + data[b].r,2);
	}
	static class Data {
		int up = 0;
		int x;
		int y;
		int r;
		int c;
		Data(int a, int b, int c, int d) {
			this.x = a;
			this.y = b;
			this.r = c;
			this.c = d;
		}
	}
}

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

typedef long long ll;
typedef string st;
typedef vector<int> vi;
typedef vector<st> vs;
#define rep(i, n) for(int i = 0; i < n; i++)
#define fogg(i,a,b) for(int i = (a); i <= (b); i++)
#define ford(i,a,b) for(int i = (a); i >= (b); i--)
#define test int t; cin >> t; while(t--)
#define debug(x) cout << '>' << #x << ':' << x << "\n";
#define endl '\n'
#define pb push_back
#define gp " "
#define ff first
#define ss second
#define mp make_pair



int main() {
    int a,b;
    cin >> a >> b;
    int i=0;
    int j=0;
    int ans=1;
    while(true){
        if(ans>=b){
            cout << i;
            break;
        }
        ans=ans-1+a;
        i++;
        
    }

return 0;
}

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

// const int 3100 = 3100;

char s[3100];
char t[3100];
int dp[3100][3100];
int rev[3100][3100];
const int mod = 1e9 + 7;
char ans[3100];

int main(){
	
	cin>>s>>t;
	int N = strlen(s);
	int M = strlen(t);
	for(int i=0; i<3100; i++)for(int j=0; j<3100; j++)dp[i][j] = -mod;
	dp[0][0] = 0;
	
	
	for(int i=0; i<=N; i++){
		for(int j=0; j<=M; j++){
			if(i+1<=N){
				if(dp[i+1][j]<dp[i][j]){
				dp[i+1][j] = dp[i][j];
				 rev[i+1][j] = 0;
			}
			}
			if(j+1<=M){
				if(dp[i][j+1]<dp[i][j]){
				dp[i][j+1] = dp[i][j];
				rev[i][j+1] = 1;
			}
			}
			if(i+1<=N && j+1<=M && s[i]==t[j]){
				if(dp[i+1][j+1]<dp[i][j] + 1){
					dp[i+1][j+1] = dp[i][j] + 1;
					rev[i+1][j+1] = 2;
				}
			}
		}
	}
		int ns= N;
		int nt = M;
		int at = dp[N][M]-1;
		
	while(ns||nt){
			if(rev[ns][nt]==0)ns--;
			else if(rev[ns][nt]==1)nt--;
			else{
				ns--; nt--;
				ans[at] = s[ns];
				at--;
			}
		}

	cout<<ans<<endl;
	system("PAUSE");
	return 0;
}
	

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

using namespace std;
using ll = long long;
using ld = long double;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
using Edge = pair<int, ld>;
using Graph = vector<vector<int> >;
using WeightedGraph = vector<vector<Edge>>;
const ll INF = 1LL << 60;
const int INF32 = 1 << 30;
const int MOD = 1e9+7;

struct UnionFind {
	vector<int> par;

	UnionFind(int n) : par(n, -1) { }
	void init(int n) { par.assign(n, -1); }

	int root(int x) {
		if (par[x] < 0) return x;
		else return par[x] = root(par[x]);
	}

	bool issame(int x, int y) {
		return root(x) == root(y);
	}

	bool merge(int x, int y) {
		x = root(x); y = root(y);
		if (x == y) return false;
		if (par[x] > par[y]) swap(x, y); // merge technique
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x) {
		return -par[root(x)];
	}
};

void pq_merge(priority_queue<ll>& dst, priority_queue<ll>& src) {
	if (src.size() > dst.size()) swap(src, dst);
	while (!src.empty()) {
		dst.push(src.top()); src.pop();
	}
}


int main() {
	ll N, M; cin >> N >> M;

	vector<ll> a(N);
	for (int i = 0; i < N; ++i) cin >> a[i];

	if (M == N - 1) {
		cout << 0 << endl;
		return 0;
	}


	UnionFind uf(N);
	for (int i = 0; i < M; ++i) {
		int a, b; cin >> a >> b;
		uf.merge(a, b);
	}

	vector<priority_queue<ll>> p_que(N);
	for (int i = 0; i < N; ++i) {
		int p = uf.root(i);
		p_que[p].push(-1 * a[i]);
	}

	ll cnt = 2 * (N - 1 - M);

	ll ans = 0;
	priority_queue<ll> que;
	for (int i = 0; i < N; ++i) {
		if (!p_que[i].empty()) {
			ans -= p_que[i].top(); p_que[i].pop();
			pq_merge(que, p_que[i]);
			--cnt;
		}
	}

	for (; cnt > 0; --cnt) {
		if (que.empty()) {
			ans = -1; break;
		}
		ans -= que.top(); que.pop();
	}
	if(ans == -1) cout << "Impossible" << endl;
	else cout << ans << endl;
	return 0;
}

Measured memory_bytes: 7680
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

#define INF (1 << 30)
#define INFL (1LL << 62)
#define MOD7 1000000007
#define MOD9 1000000009
#define EPS 1e-10

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pul pair<ull, ull>
#define all(a) (a).begin(), (a).end()
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);--i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define RREP(i,n) for (int i=(n)-1;i>=0;--i)

void YES() { cout << "YES" << endl; }
void NO() { cout << "NO" << endl; }
void Yes() { cout << "Yes" << endl; }
void No() { cout << "No" << endl; }
void yes() { cout << "yes" << endl; }
void no() { cout << "no" << endl; }
void digit(int d) { cout << fixed << setprecision(d); }
void IOup() { cin.tie(0); ios::sync_with_stdio(false); }

int main() {
	int n;
	cin >> n;
	cout << n * (n + 1) / 2 << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;


int main()
{
	char a;
	cin >> a;
	if(a >='A' && a<='Z')
	{
		cout << 'A';
	}
	else
	{
		cout << 'a';
	}
}



Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

int main()
{
  int a, b;
  cin >> a >> b;
  cout << max(max(a + b, a - b), a * b) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())

using namespace std;
using ll = long long;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline void dump(vector<T> v) { for (auto& x : v) cerr << x << " "; cerr << endl; }
template<class T> inline void dump(vector<pair<T, T>> v) { for (auto& p : v) cerr << p.first << " " << p.second << endl; }
template<class T> inline void dump(vector<vector<T>> vv) { for (auto& v : vv) {for (auto& x : v) cerr << x << " "; cerr << endl;} }

constexpr int INF = 1e9 + 5;
constexpr long long INFLL = 1LL << 62;
constexpr double eps = (1e-9);

double dp[305][305][305];
int flag[305][305][305];  // (c1, c2, c3) が計算済みである事をメモしておく

double f(const int& n, const int& c1, const int& c2, const int& c3) {
  if (flag[c1][c2][c3]) return dp[c1][c2][c3];  // 計算済みの結果を返す
  flag[c1][c2][c3] = 1;
  double p0 = (double)(n - c1 - c2 - c3) / n;
  double p1 = double(c1) / n;
  double p2 = double(c2) / n;
  double p3 = double(c3) / n;
  dp[c1][c2][c3] = 1 / (1 - p0);
  if (c1 > 0) dp[c1][c2][c3] += f(n, c1 - 1 , c2, c3) * p1 / (1 - p0);
  if (c2 > 0) dp[c1][c2][c3] += f(n, c1 + 1, c2 - 1, c3) * p2 / (1 - p0);
  if (c3 > 0) dp[c1][c2][c3] += f(n, c1, c2 + 1, c3 - 1) * p3 / (1 - p0);
  return dp[c1][c2][c3];
};

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

  int n;
  cin >> n;

  int c1 = 0, c2 = 0, c3 = 0;
  rep(i, n) {
    int x; cin >> x;
    if (x == 1) c1++;
    else if (x == 2) c2++;
    else c3++;
  }

  flag[0][0][0] = 1;

  printf("%.10f\n", f(n, c1, c2, c3));

  return 0;
}


Measured memory_bytes: 167584
<?php
  $n=fgets(STDIN);
  $h=explode(' ',fgets(STDIN));
  $c=0;
  $p=0;
  for($i=0;$i<$n;$i++)
  {
    $c+=$p<=$h[$i];
    if($p<=$h[$i])$p=$h[$i];
  }
  echo $c;

Measured memory_bytes: 3828
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <chrono>
#include <random>
#include <tuple>
#include <utility>
#include <fstream>
#include <complex>
#define _USE_CMATH_DEFINES

const long INF = (1l << 30);
const long LINF = (1l << 60); //1.15*10^18

long n;

std::vector<long> prime_factorize(long n){
    long div = 2;
    std::vector<long> ret;
    if(n < 2){
        printf("prime_factorize input invalid!\n");
        return ret;
    }
    while(div * div <= n){
        if(n % div == 0){
            ret.push_back(div);
            n /= div;
        }else{
            div++;
        }
    }
    ret.push_back(n);
    return ret;
}

int main(){
    scanf("%ld", &n);
    std::vector<long> p = prime_factorize(n);
    printf("%ld:", n);
    for(int i = 0; i < p.size(); i++){
        printf(" %ld", p[i]);
    }
    printf("\n");
}



Measured memory_bytes: 3276
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int HPINT,HPMAX;
int N,M;
char ch[1010][1010];
int A[1010][1010];
char ch1[1201];
int dp[1010][4100];
int Q;
int P[1010];
int U;
int K;
int po[2010];
#define oo 1000000000
int main()
{
    int i,j,k;
    int a,b,s;
    int T;
    while(scanf("%d%d",&HPINT,&HPMAX)!=EOF)
    {
        if(HPINT==0&&HPMAX==0) break;
        scanf("%d%d",&N,&M);
        for(i=0;i<N;i++)
        {
            scanf("%s",ch[i]);
        }
        scanf("%d",&T);
        for(int t=0;t<T;t++)
        {
            scanf("%s%d",ch1,&s);
            for(i=0;i<N;i++)
            {
                for(j=0;j<M;j++)
                {
                    if(ch[i][j]==ch1[0])
                    {
                        A[i][j]=s;
                    }
                }
            }
        }
        scanf("%d",&Q);
        k=1;
        for(i=0;i<Q;i++)
        {
            scanf("%s%d",ch1,&s);
            if(ch1[0]=='U') a=0;
            else if(ch1[0]=='R') a=1;
            else if(ch1[0]=='D') a=2;
            else a=3;
            for(j=0;j<s;j++,k++)
            {
                P[k]=a;
            }
        }
        K=k-1;
        scanf("%d",&U);
        for(i=0;i<U;i++) scanf("%d",&po[i]);
        for(i=0;i<=K;i++)
            for(j=0;j<(1<<U);j++)
                dp[i][j]=-oo;
        dp[0][(1<<U)-1]=HPINT;
        int y=0,x=0;
        for(i=1;i<=K;i++)
        {
            for(j=(1<<U)-1;j>=0;j--)
            {
                dp[i][j]=dp[i-1][j];
                for(k=0;k<U;k++)
                {
                    if((j&(1<<k))==0)
                    {
                        dp[i][j]=max(dp[i][j],min(dp[i][j|(1<<k)]+po[k],HPMAX));
                    }
                }
            }
            if(P[i]==0) y--;
            else if(P[i]==1) x++;
            else if(P[i]==2) y++;
            else x--;
            for(j=0;j<(1<<U);j++)
            {
                if(dp[i][j]>A[y][x]) dp[i][j]-=A[y][x];
                else dp[i][j]=-oo;
            }
        }
        bool ju=false;
        for(j=0;j<(1<<U);j++) if(dp[K][j]>0) ju=true;
        if(ju) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

Measured memory_bytes: 21644
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int k,n;
	cin>>k>>n;
	int A[n];
	for(int i=0;i<n;i++)
	{
		cin>>A[i];
	}
	int d[n];
	for(int i=0;i<n-1;i++)
	{
		d[i]=A[i+1]-A[i];
	}
	d[n-1]=k-A[n-1]+A[0];
	int m=INT_MIN;
	int store=0;
	for(int i=0;i<n;i++)
	{
		m=max(m,d[i]);
		if(m==d[i])
		{
			store=i;
		}
	}
	int sum=0;
	for(int i=0;i<n;i++)
	{
		sum+=d[i];
	}
	sum-=d[store];
	cout<<sum<<endl;
	
}

Measured memory_bytes: 5156
#include <iostream>
#include<algorithm>
#include<string>
using namespace std;
int main() {
	int n;
	cin >> n;
	string a;
	cin >> a ;
	int ans[100] = { 0 };
	for (int i = 0; i < n-1; i++) {
		for (int j = 0; j <= i; j++) {
			int x = 0;
			for (int k = 0; k < j; k++) {
				if (a[j] == a[k]) x = 1;
			}
			if(x==0){
				for (int k = i + 1; k < n; k++) {
					if (a[k] == a[j]) {
						ans[i]++;
						break;
					}
				}
			}
		}
	}
	int abc = 0;
	for (int i = 0; i < n; i++) if (ans[i] > abc) abc = ans[i];
	cout << abc;
}

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

int main()
{
    int h, w, k;
    int res = 0;
    cin >> h >> w >> k;
    vector<vector<char>> v(h, vector<char>(w));
    
    for(int i = 0; i < h; ++i)
    {
        for(int j = 0; j < w; ++j)
        {
            cin >> v[i][j];
        }
    }
    
    // iterate for all subset of rows h{0, 1, ..., h-1}
    for(int br = 0; br < (1 << h); ++br)
    {
        // iterate for all subset of columns w{0, 1, ..., w-1}
        for(int bc = 0; bc < (1 << w); ++ bc)
        {
            int black_count = 0;
            
            // check each grid if the row and column is not painted red AND
            // the grid is black
            for(int i = 0; i < h; ++i)
            {
                for(int j = 0; j < w; ++j)
                {
                    // v[i][j] is not red and the grid is black
                    if(!(br & (1 << i)) && !(bc & (1 << j)) && v[i][j] == '#')
                    {
                        black_count++;
                    }
                }
            }
            if(black_count == k)
            {
                res++;
            }
        }
    }
    
    cout << res << "\n";
    
    return 0;
}


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

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

    int n, c1 = 0, c2 = 0, c3 = 0, c4 = 0;
    cin >> n;
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        if(s == "AC") {
            c1++;
        }
        if(s == "WA") {
            c2++;
        }
        if(s == "TLE")
            c3++;

        if(s == "RE")
            c4++;

    }
    cout << "AC x " << c1 << "\n";
    cout << "WA x " << c2 << "\n";
    cout << "TLE x " << c3 << "\n";
    cout << "RE x " << c4 << "\n";
    return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const ll MAX = 1e+9;
/* global variables */
/* function */
/* main */
int main(){
    ll X;
    cin >> X;

    int lower = -120;
    int upper = 120;
    for (int i = lower; i <= upper; i++) {
        ll p = pow(i, 5);
        for (int j = lower; j <= upper; j++) {
            ll q = pow(j, 5);
            if (p - q == X) {
                cout << i << ' ' << j << '\n';
                return 0;
            }
        }
    }
}

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

#ifdef LOCAL
#include "debug.h"
#else
#define DEBUG(...)
#endif

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  map<int, int> mp;
  auto res = 0LL;
  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    res += mp[i - a];
    ++mp[i + a];
  }
  cout << res << '\n';
}


Measured memory_bytes: 20572
#include <bits/stdc++.h>
using ll = long long;
using itn = int;
using namespace std;
int GCD(int a, int b){
    return b ? GCD(b, a%b) : a;
}
int main(){
    int n;
    cin >> n;
    int w[n];
    for(int i=0; i<n; i++){
        cin >> w[i];
    }
    int minw=1e9;
    for(int i=1; i<n; i++){
        int tmp1=0;
        int tmp2=0;
        for(int j=0; j<i; j++){
            tmp1+=w[j];
        }
        for(int j=i; j<n; j++){
            tmp2+=w[j];
        }
        minw=min(minw,abs(tmp1-tmp2));
    }
    cout << minw << endl;
}

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


int main(){
	int A[4];
	
	cin >> A[0] >> A[1] >> A[2] >> A[3];
	
	sort(A,A+4);
	if(A[0]==1&&A[1]==4&&A[2]==7&&A[3]==9) cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}

Measured memory_bytes: 256
'''
参考
https://note.com/tanon_cp/n/n9b0a77fcda7d
https://qiita.com/u2dayo/items/90a0693f31524e7b4cd0#c%E5%95%8F%E9%A1%8Ch-and-v
bit全探索を使用する
'''
from itertools import product

H, W, K = map(int, input().split())
c = [list(input()) for _ in range(H)]

ans = 0

# bit全探索
for b_row in product([0, 1], repeat=H):             # 行の塗りつぶし全パターンを0か1で列挙
    for b_col in product([0, 1], repeat=W):         # 列の塗りつぶし全パターンを0か1で列挙
        cnt = 0
        for i in range(H):
            for j in range(W):                      # 全ての「i行目j列目」について調べる
                if b_row[i] == 0 and b_col[j] == 0: # 塗りつぶされないマス
                    if c[i][j] == '#':              # 黒のままだったらカウントアップ
                        cnt += 1
        if cnt == K:                                # 全ての「i行目j列目」についてカウント終了、黒マス数がKと一致したら
            ans += 1                                # 解答をカウントアップ

print(ans)


Measured memory_bytes: 9068
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
vector<pair<ll, ll> > pairs;
#define print1(x) cerr << "x = " << x << endl;
#define print2(x, y) cerr<< "x,y = "  << x << "," << y << endl;
#define print3(x, y, z) cerr << "x,y,z = " << x << "," << y << "," << z << endl;
#define print4(x, y, z, w) cerr << "x,y,z,w = " << x << "," << y << "," << z << "," << w << endl;
#define MAX_V int(2e5 + 1)
const ll mod = ll(1e9+7);

struct edge{int to, cost;};

vector<edge> G[MAX_V];
vector<bool> seen;
vector<ll> bunshi;
int N;

// O(log n)
ll mod_pow(ll x, ll n, ll mod){
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

//ax + by = gcd(a, b) �𖞂��� x, y ��Ԃ�
ll extgcd (ll a, ll b, ll& x, ll& y){
    ll d = a;
    if (b != 0){
        d = extgcd(b, a % b, y, x);
        y -= (a/b) * x;
    } else {
        x = 1; y = 0;
    }
    return d;
}

// O(log n)
// ax == 1 (mod m)�𖞂��� x
ll mod_inverse(ll a, ll m){
    return mod_pow(a, m - 2, m);
    ll x, y;
    extgcd(a, m, x, y);
    return (m + x % m) % m;
}

int dfs(int v) {
    // �s�����������C���N�������g���Ȃ��烁��
    int res, tot = 0; // �c��[����������
    ll x = 0, y = mod_pow(2, N - 1, mod);
    ll sum = 1;
    //fprintf(stderr, "v = %d\n", v);
    seen[v] = true; // v ��K��ςɂ���
    for (auto e: G[v]){
        //fprintf(stderr, " %d -> %d\n", v, e.to);
        if (seen[e.to]) continue; 
        res = dfs(e.to);
        
        x = mod_pow(2, res, mod);
        (y += mod - x) %= mod;
        
        tot += res;
        
        sum += mod - mod_pow(mod_inverse(2, mod),N - 1 - res,mod);
        sum%=mod;
    }
    res = N - 1 - tot;
    if (res > 0){
        x = mod_pow(2, res, mod);
        (y += mod - x) %= mod;
        
        sum += mod - mod_pow(mod_inverse(2, mod),N - 1 - res,mod);
        sum%=mod;

    }
    (y += G[v].size() - 1) %= mod;
#if 0    
    sum += (G[v].size()-1) * modpow(inv[2],n-1,mod);
    sum %= mod;
    bunshi[v] = sum;
#endif
    bunshi[v] = y;
    if (G[v].size() <= 1){
        bunshi[v] = 0;
    }
    return tot + 1;
}

////////////////////////////////////////

int main() {
    cin >> N;
    vector<int> A(N), B(N);
    
    rep(i, N - 1){
        cin >>  A[i] >> B[i];
        G[A[i] - 1].push_back((edge){B[i] - 1, 0});
        G[B[i] - 1].push_back((edge){A[i] - 1, 0});
    }
    
    //dijkstra(S);
    seen.assign(N, false); // �S���_���u���K��v�ɏ�����
    bunshi.assign(N, 0); // �S���_��0�ɏ�����
    dfs(0);
    ll bunshi0 = 0;
    ll bunbo = mod_pow(2, N, mod);
    
    rep(i, N){
        //fprintf(stderr, "%d, %d/%d\n", i, bunshi[i], bunbo);
        bunshi0 += bunshi[i];
        bunshi0 %= mod;
    }
    //fprintf(stderr, "bunshi = %d, bunbo = %d\n", bunshi0, bunbo);
    // (bunbo) * x == 1 (mod m)�𖞂��� x
    ll x = mod_inverse(bunbo, mod);
    
    ll ans = bunshi0 * mod_pow(mod_inverse(2, mod), N, mod) % mod;
    //ll ans = x * bunshi0 % mod;
    cout << ans;
    return 0;
}


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

#define pb(n) push_back(n)
#define fi first
#define se second
#define X real()
#define Y imag()
#define all(r) (r).begin(),(r).end()
#define gsort(st,en) sort((st),(en),greater<int>())
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using dict = map<string,int>;
using comd = complex<double>;
using pii = pair<int,int> ;

constexpr int imax = ((1<<30)-1)*2+1 ;
constexpr int inf = 100000000;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0};
const int dx[] = {0,-1,0,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

double CalcDist(comd p1, comd p2){
  return sqrt(pow(p1.X - p2.X,2.0) + pow(p1.Y -p2.Y,2.0));
}

  template <typename T>
void out(deque < T > d)
{
  for(size_t i = 0; i < d.size(); i++)
  {
    debug(d[i]);
  }
}

template<typename T>
T ston(string& str, T n){
  istringstream sin(str) ;
  T num ;
  sin >> num ;
  return num ;
}
char c[101][101];
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int H,W;
  while(cin >> H >> W){
    if(H+W == 0) break;
    set<pii> f;
    pii P(0,0);
    rep(i,H){
      rep(j,W){
        cin >> c[i][j];
      }
    }
    while(c[P.fi][P.se] != '.'){
      auto check = f.insert(P);
      if(c[P.fi][P.se] == '>'){
        P.se++;
      }
      else if(c[P.fi][P.se] == 'v'){
        ++P.fi;
      }
      else if(c[P.fi][P.se] == '^'){
        --P.fi;
      }
      else if(c[P.fi][P.se] == '<'){
        --P.se;
      }
      else{
        break;
      }
      if(!check.se ){
        cout << "LOOP" << endl;
        W = -1;
        break;
      }
    }
    if(W != -1){
      cout << P.se<< " " << P.fi<<endl;
    }
  }
  return 0;
}

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

#define int long long
#define ct(n) cout << n << endl;
#define cts(n) cout << n << " ";
#define cte cout << endl;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repo(i,o,n) for(int i=o;i<n;i++)
#define repm(i,n) for(int i=n-1;i>=0;i--)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define vcopy(v1,v2) copy((v1).begin(), (v1).end(), back_inserter((v2)));
#define pb(n) push_back(n);

int n,ans;

main() {
    cin >> n;
    rep1(i,n) ans += i;
    ct(ans)
}



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

int main()
{
  int a, b, c, temp;

  cin >> a >> b >> c;

  if(a > b){
    temp = a;
    a = b;
    b = temp;
  }
  if(a > c){
    temp = a;
    a = c;
    c = temp;
  }
  if(b > c){
    temp = b;
    b = c;
    c = temp;
  }
  cout << a << " " << b << " " << c << endl;
  return 0;
}

Measured memory_bytes: 1164
#include<iostream>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
bool a[30];
int b;
int main(){
	rep(i,30)a[i]=false;
	rep(i,28){cin>>b;a[b-1]=true;}
	rep(i,30)if(!a[i])cout<<i+1<<endl;
	return 0;
}

Measured memory_bytes: 3092
// 1187.cpp - ICPC Ranking
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct team {
    int id;
    int solved;
    int penalty;
    vector<int> not_accepted;

    team(int id, int n_problems):
        id(id), solved(0), penalty(0), not_accepted(n_problems) {}

    bool operator<(const team& rhs) const {
        if (solved != rhs.solved)
            return solved > rhs.solved;
        if (penalty != rhs.penalty)
            return penalty < rhs.penalty;
        return id > rhs.id;
    }
};

int main()
{
    ios::sync_with_stdio(false);

    int M, T, P, R;
    while (cin >> M >> T >> P >> R, M) {
        vector<team> teams;
        for (int t = 0; t < T; ++t) {
            teams.emplace_back(t + 1, P);
        }

        for (int r = 0; r < R; ++r) {
            int m, t, p, j;
            cin >> m >> t >> p >> j;
            team& team = teams[t - 1];
            if (j == 0) {
                team.solved += 1;
                team.penalty += m + team.not_accepted[p - 1] * 20;
            } else {
                team.not_accepted[p - 1] += 1;
            }
        }

        sort(teams.begin(), teams.end());

        for (int t = 0; t < T; ++t) {
            if (t > 0) {
                if (teams[t].solved  == teams[t - 1].solved &&
                    teams[t].penalty == teams[t - 1].penalty)
                    cout << "=";
                else
                    cout << ",";
            }
            cout << teams[t].id;
        }
        cout << endl;
    }
}

Measured memory_bytes: 1216
b1 = list(map(int, input().split()))
b2 = list(map(int, input().split()))
b3 = list(map(int, input().split()))
b4 = [b1[0],b2[0],b3[0]]
b5 = [b1[1],b2[1],b3[1]]
b6 = [b1[2],b2[2],b3[2]]
b7 = [b1[0],b2[1],b3[2]]
b8 = [b1[2],b2[1],b3[0]]

N = int(input())
num = []
for i in range(N):
  num += [int(input())]

if set(b1) <= set(num) or set(b2) <= set(num) or set(b3) <= set(num) or set(b4) <= set(num) or set(b5) <= set(num) or set(b6) <= set(num) or set(b7) <= set(num) or set(b8) <= set(num):
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3064
def main():
    n = int(input())

    s = [0 for i in range(n)]
    for i in range(n):
        s[i] = input()

    a = 0
    w = 0
    t = 0
    r = 0
    
    for i in range(n):
        if (s[i] == 'AC'):
            a += 1
        elif (s[i] == 'WA'):
            w += 1
        elif (s[i] == 'TLE'):
            t += 1
        else:
            r += 1

    print('AC x ' + str(a))
    print('WA x ' + str(w))
    print('TLE x ' + str(t))
    print('RE x ' + str(r))
    
main()


Measured memory_bytes: 16324
#include <stdio.h>
#include <math.h>

int main()
{
	int n,m,i,j,x,c=0;
	scanf("%d",&n);
	
	int a[n];
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	
	scanf("%d",&m);
	for(i=0;i<m;i++)
	{
		scanf("%d",&x);
		
		for(j=0;j<n;j++){
			if(a[j]==x)
			{
				c=c+1;
				break;
			}
		}
	}
	
	printf("%d\n",c);
	
	return 0;
}


Measured memory_bytes: 2084
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k;
  cin>>n>>k;
  k=k-1;
  string s;
  cin>>s;
  if(s.at(k)=='A'){
    s.at(k)='a';
  }
  else if(s.at(k)=='B'){
    s.at(k)='b';
  }
  else if(s.at(k)=='C'){
    s.at(k)='c';
  }
  cout<<s<<endl;
}


Measured memory_bytes: 3620
#pragma region
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <iomanip>
#include <cstdint>
#include <bitset>

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))
#define all(x) x.begin(),x.end()

#pragma region UnionFind
struct UnionFind
{
	vector<int> par;

	UnionFind(int n) : par(n, -1) {}
	void init(int n) { par.assign(n, -1); }

	int root(int x)
	{
		if (par[x] < 0) return x;
		else return par[x] = root(par[x]);
	}

	bool issame(int x, int y)
	{
		return root(x) == root(y);
	}

	bool merge(int x, int y)
	{
		x = root(x); y = root(y);
		if (x == y) return false;
		if (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x)
	{
		return -par[root(x)];
	}
};
#pragma endregion
#pragma region GCD
int gcd(int a, int b)
{
	if (a%b == 0)return b;
	return gcd(b, a%b);
}
#pragma endregion
#pragma region chmin
template<class T> inline bool chmin(T& a, T b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma region chmax
template<class T> inline bool chmax(T& a, T b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma endregion


int main()
{
	int k, t; cin >> k >> t;
	vector<int> a(t); rep(i, t)cin >> a[i];
	sort(all(a), greater<int>());
	cout << max(a[0] - 1 - (k - a[0]), 0) << endl;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		scan.close();
		ArrayList<Integer> list = new ArrayList<Integer>();
		list.add(1);
		listMoney(list, N, 6);
		listMoney(list, N, 9);
		Collections.sort(list);
		if(N <= 10) {
			if(N <= 5) {
				System.out.println(N);
				System.exit(0);
			}else if(N <= 8) {
				System.out.println(N - 5);
				System.exit(0);
			}else {
				System.out.println(N - 8);
				System.exit(0);
			}
		}

		int []m = new int[N + 1];
		m[1] = 1;
		m[2] = 2;
		m[3] = 3;
		m[4] = 4;
		m[5] = 5;
		m[6] = 1;
		m[7] = 2;
		m[8] = 3;
		m[9] = 1;
		int t = 0;
		for(int i = 10; i <= N; i++) {
			if(isCheck(i, 9)) {
				m[i] = 1;
			}else if(isCheck(i, 6)) {
				m[i] = 1;
			}else {
				t = i;
				int k = 100000;
				int a;
				for(int j = 0; j < list.size(); j++) {
					a = t - list.get(j);
					if(a >= 0) {
						if(k > m[a] + 1) {
							k = m[a] + 1;
						}
					}else {
						break;
					}
				}
				m[i] = k;
			}
		}
		System.out.println(m[N]);

	}
	public static void listMoney(ArrayList<Integer> list, int N, int k) {
		int t = 0;
		int i = 1;
		while(N - t >=0) {
			t = (int) Math.pow(k, i);
			list.add(t);
			i ++;
		}
	}
	public static boolean isCheck(int n, int k) {
		int t = 0;
		int i = 0;
		while(n - t >= 0) {
			t = (int) Math.pow(k, i);
			i ++;
			if(n - t == 0) {
				return true;
			}
		}

		return false;
	}
}

Measured memory_bytes: 26324
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
using namespace std;

#define ABS(a) (((a) >= 0) ? (a) : -(a))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define RFOR(i, a, b) for (int i = a; i > b; --i)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define int long long

typedef long long ll;
typedef pair<int, int> Pair;

// const int kMaxN;

int X;
int ans = 1;

signed main() {
  cin >> X;

  FOR(i, 2, 40) {
    int j = i*i;
    while (j <= X) {
      ans = MAX(ans, j);
      j *= i;
    }
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL << 60;
const ll C = 1e9+7;

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

    ll ans = 0;
    sort(A.begin(), A.end());

    for(int i=0; i<=N-K; i++) {
        ans += A[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 4008
#include <iostream>
#include<algorithm>
using namespace std;
int main(void){
    int N;
    int L[100];
    int i;
    int max=0;
    int sum=0;
    cin>>N;
    for(i=0;i<N;i++)
    {
        cin>>L[i];
        if(max<L[i])    max=L[i];
        sum+=L[i];
    }
    
    if(max<(sum-max))   //もっとも長い辺が短い場合
    {
        cout<<"Yes";
    }
    else    cout<<"No";

    
    
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.nextLine();
		String[] spl = s.split(" ");
		int A = Integer.parseInt(spl[0]);
		int B = Integer.parseInt(spl[1]);
		sc.close();
		if(A < 6){
			B = 0;
		}else if(A >= 6 && A < 13){
			B = B / 2;
		}
		System.out.println(B);
	}

}

Measured memory_bytes: 23252
s = int(input())

def factorial_cor(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact

mod = 10**9+7
ans = 0
# 項数i
for i in range(1,s//3+1):
    ans += factorial_cor((s-3*i)+i-1)//(factorial_cor(s-3*i)*factorial_cor(i-1))
    ans = ans%mod
print(ans)

Measured memory_bytes: 9184
#include <iostream>
using namespace std;
int n, m, x, y, a, mx, my;
int main() {
	cin>>n>>m>>x>>y;
	mx = x, my = y;
	while(n--) {
		cin>>a;
		mx = max(mx, a);
	}
	while(m--) {
		cin>>a;
		my = min(my, a);
	}
	cout<<(mx<my ? "No " : "")<<"War";
	return 0;
}

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

/* MACROS SAMPAH */
#define Jehian using
#define Norman namespace
#define Saviero std
#define cepet {ios_base::sync_with_stdio(0);cin.tie(0);}

Jehian Norman Saviero;

/* MACROS FOR TYPE */
typedef long l;
typedef long double ld;
typedef long long ll;
typedef unsigned long ul;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<l> vl;
typedef vector<ll> vll;
typedef pair<int, int> pi;
typedef pair<l,l> pl;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;

/* MACROS FOR PRINT */
#define nl printf("\n");
#define sp printf(" ");

/* MACROS FOR FUNCTION AND METHOD */
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define mp make_pair
#define eb emplace_back
#define RESET(x) memset((x), 0, sizeof(x))
#define SET(x,y) for(int _je = sizeof(x)/sizeof(x[0]); _je--;) x[_je] = y
#define SQR(x) (x)*(x)
#define CUBE(x) SQR(x)*(x)

/* MACROS FOR ATTRIBUTE */
#define fi first
#define se second

/* MACROS FOR SCAN */
#define scc(x) scanf("%c", &x)
#define scd(x) scanf("%Lf", &x)
#define scf(x) scanf("%f", &x)
#define sci(x) scanf("%d", &x)
#define scl(x) scanf("%ld", &x)
#define scll(x) scanf("%lld", &x)
#define scld(x) scanf("%Lf", &x)
#define scui(x) sci(x)
#define scul(x) scl(x)
#define scull(x) scll(x)

int main(){
	ll N, A, B;
	cin >> N >> A >> B;
	cout << min(N*A,B) << endl;
	return 0;
}

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

using namespace std;

int main(){
  int a,b;
  string s;
  cin >> a >> b;
  a--;
  b--;
  cin >> s;
  transform(s.begin()+b,s.end()-a+b,s.begin()+b,::tolower);
  cout << s;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
	int A,B,C,ans;
	scanf("%d %d %d",&A,&B,&C);
	ans=10*A+B+C;
	if(ans<A+10*B+C) ans=A+10*B+C;
	if(ans<A+B+10*C) ans=A+B+10*C;
	printf("%d",ans);
}
	

Measured memory_bytes: 128