akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

const int64_t MOD = 1e9+7;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}
void mul(int64_t& a, int64_t b){
    a = a*b % MOD;
}

int64_t power_mod(int64_t num, int64_t power){
    int64_t prod = 1;
    num %= MOD;
    while(power > 0){
        if(power&1) prod = prod * num % MOD;
        num = num * num % MOD;
        power >>= 1;
    }
    return prod;
}

int64_t extgcd(int64_t a, int64_t b, int64_t& x, int64_t& y){
    int64_t d = a;
    if(b != 0){
        d = extgcd(b, a%b, y, x);
        y -= (a/b) * x;
    }else{
        x = 1; y = 0;
    }
    return d;
}

int64_t inv_mod(int64_t a){
    int64_t x, y;
    extgcd(a, MOD, x, y);
    return (MOD + x%MOD) % MOD;
}

vector<int64_t> fact, fact_inv;

void create_mod_tables(int num){
    fact.resize(num+1, 1);
    fact_inv.resize(num+1, 1);
    for(int i=1; i<=num; i++) fact[i] = fact[i-1] * i % MOD;
    fact_inv[num] = inv_mod(fact[num]);
    for(int i=num; i>0; i--) fact_inv[i-1] = fact_inv[i] * i % MOD;
}

int64_t comb_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD * fact_inv[k] % MOD;
}

int64_t perm_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD;
}

int main(){
    int N;
    cin >> N;
    vector<int> edges[200000];
    for(int i=0; i<N-1; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }

    create_mod_tables(200000);

    // 1回目のDFS
    vector<int> num(N);
    vector<int64_t> dp(N);
    auto dfs1 = [&](auto&& dfs1, int i, int p)->void{
        dp[i] = 1;
        for(int j : edges[i]) if(j != p){
            dfs1(dfs1, j, i);
            num[i] += num[j];
            mul(dp[i], dp[j] * comb_mod(num[i], num[j]) % MOD);
        }
        num[i]++;
    };
    dfs1(dfs1, 0, -1);

    // 答えを求める2回目のDFS。引数uが、iの親pの「iの子としての」dp[p]の値を示す
    vector<int64_t> ans(N);
    auto dfs2 = [&](auto&& dfs2, int i, int p, int64_t u)->void{
        // pを子としてマージするときの係数を掛けて答えとする
        ans[i] = dp[i] * u % MOD * comb_mod(N-1, N-num[i]) % MOD;
        
        for(int j : edges[i]) if(j != p){
            // ans[i]から子jのマージの逆操作をした値を次に渡す
            int64_t u2 = ans[i] * inv_mod(dp[j]) % MOD * inv_mod(comb_mod(N-1, num[j])) % MOD;
            dfs2(dfs2, j, i, u2);
        }
    };
    dfs2(dfs2, 0, -1, 1);

    for(int i=0; i<N; i++) cout << ans[i] << endl;
    return 0;
}


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

int main()
{
	int a, b, c, k;
	cin >> a>> b>> c>> k;

	if (k <= a) {
		cout << k;
	}
	else {
		k -= a;
		if (k<=b) {
			cout << a;
		}
		else {
			k -= b;
			cout << (a - k);
		}
	}
	return 0;
}

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

#define min(a,b) ((a)<(b)?(a):(b))

#define LEN 100000

typedef struct
{
  char name[10];
  int time;
} process;

process Q[LEN];
int head,tail,n;

void enqueue(process inf);
process dequeue();

int main(void)
{
  process inf;
  
  int time=0;
  int data;
  int i,q;

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

  for(i=1;i<=n;i++)
    {
      scanf("%s",Q[i].name);
      scanf("%d",&Q[i].time);
    }

  head=1;
  tail=n+1;

  while(head!=tail)
    {
      inf=dequeue();
      data=min(q,inf.time);
      inf.time-=data;
      time+=data;
      if(inf.time>0)
	{
	  enqueue(inf);
	}
      else
	{
	  printf("%s %d\n",inf.name,time);
	}
    }
  return 0;
}

void enqueue(process inf)
{
  Q[tail]=inf;
  tail=(tail+1)%LEN;
}

process dequeue()
{
  process inf=Q[head];
  head=(head+1)%LEN;
  return inf;
}



Measured memory_bytes: 3304
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <string>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
#include <ctime> 
using namespace std;

#define pb push_back
#define All(a) a.begin(), a.end()
#define met(a, b) memset(a, b, sizeof(a))
#define rep1(i, l, r) for(int i = l; i <= r; ++i)
#define rep2(i, l, r) for(int i = l; i < r; ++i) 
#define per(i, r, l) for(int i = r; i >= l; --i)
typedef long long ll;
typedef double db;
typedef long double ldb;
const int NIL = -1;
const int oo = 0x3f3f3f3f;
const ll INF = 2e18;
const db eps = 1e-8;
const db PI = acos(-1.0);

inline ll read(void)
{
	ll x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9')	{ if(ch == '-') f = -1; ch = getchar(); } 
	while(ch >= '0' && ch <= '9') {	x = (x << 1) + (x << 3) + ch - '0';	ch = getchar();	}
	return x * f;
}

inline void write(int x)
{
	if(x < 0) { putchar('-'); x = -x; }
    if(x >= 10) write(x/10); 
	putchar(x%10+'0'); 
}

int main(void)
{
	ll n = read(), k = read();
	ll ans = 0;
	if(k&1)
	{
		if(n < k)
		{
			ans += 0;
		}
		else
		{
			ll m = (n - k) / k;
			m++;
			ans += m + m * (m - 1) * 3 + m * (m - 1) * (m - 2);
		}
	}
	else
	{
		if(n < k / 2)
		{
			ans += 0;
		}
		else
		{
			ll m = (n - k/2) / k;
			m++;
			ans += m + m * (m - 1) * 3 + m * (m - 1) * (m - 2);
		}
		if(n < k)
		{
			ans += 0;
		}
		else
		{
			ll m = (n - k) / k;
			m++;
			ans += m + m * (m - 1) * 3 + m * (m - 1) * (m - 2); 
		}
	}
	printf("%lld", ans);
	
	return 0;
} 

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <deque>
#include <ctime>

using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define mp make_pair
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const ll LINF = 1e18;
const ll MOD = 86400;
double EPS = 1e-8;
const double PI = acos(-1);

string strN[60];
string strM[60];
int N,M;

int memo[60][60];

bool check(int x, int y){

	bool match = true;

	for(int i=x; i<x + M; i++){
		for(int j=y; j<y + M; j++){
			if(strN[i][j] != strM[i-x][j-y]){
				match = false;
			}
		}
	}

	return match;
}


bool dfs(int x, int y){
	if(memo[x][y]!=-1) return (bool)memo[x][y];

	if(x + M - 1>= N  or y + M - 1>= N ) return memo[x][y] = false;

	if(check(x, y)) return memo[x][y] = true;

	if(dfs(x + 1, y)) return memo[x][y] = true;
	if(dfs(x, y + 1)) return memo[x][y] = true;

	return memo[x][y] = false;
}



int main(){

	cin >> N >> M;

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

	for(int j=0; j<M; j++){
		cin >> strM[j];
	}
	rep(i, 60) rep(j, 60) memo[i][j] = -1;
	bool rlt = dfs(0, 0);

	if(rlt){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}

}











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

using namespace std;
typedef long long ll;
#define mp make_pair

const int N = 1e5;
ll n, a, b;
ll h[N];
ll t[N];

bool check(ll s) {
	ll sum = 0;
	for (int i = 0; i < n; i++) {
		t[i] = (h[i] - s * b + (a - b - 1)) / (a - b);
		if (t[i] < 0)
			t[i] = 0;
		sum += t[i];
	}
	return sum <= s;
}

int main() {
	//	freopen("input.txt", "r", stdin);
	//	freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);	
	cin >> n >> a >> b;
	for (int i = 0; i < n; i++)
		cin >> h[i];
	ll l = 0, r = 1e9 + 5;
	while (r - l > 1) {
		ll m = (l + r) / 2;
		if (check(m))
			r = m;
		else
			l = m;
	}
	cout << r << endl;
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
ll mod=1e9+7;
#define PI 3.1415926535897932385
#define INF 100000000000000000ll
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
string char_to_str(char c){string tem(1,c);return tem;}
 
typedef pair<long long, long long> ii;
#define S second
#define F first
ll max(ll a,ll b){if(a>b){return a;}return b;}
ll min(ll a,ll b){if(a<b){return a;}return b;}
#define MAXN 200005
// string to integer stoi() Remember: it takes string not character
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
 
// To compile--> g++ -std=c++0x -o output one.cpp
// To run--> ./output


int main() {

	fastio;
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);

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

	ll sum=0;
	for (auto i = m1.begin(); i != m1.end(); ++i)
	{
		if(i->S>1){
			sum = sum + ((i->S)*(i->S-1))/2;
		}
	}

	for (int i = 0; i < n; ++i)
	{
		ll ans = sum - (m1[a[i]]*(m1[a[i]]-1))/2;
		ll tot = m1[a[i]]-1;
		if(tot>1){
			ans = ans + (tot*(tot-1))/2;
		}
		cout<<ans<<endl;
	}

	return 0;
}

Measured memory_bytes: 11136
#include <stdio.h>          // printf(), scanf()
#include <stdbool.h>

#define MAX_V 20

int V;
int G[MAX_V][MAX_V];
bool visited[MAX_V];
int out[MAX_V];
int ix;

void
visit(int v)
{
	visited[v] = true;
	for (int u = 0; u < V; ++u)
	{
		if (G[v][u] && !visited[u])
			visit(u);
	}

	out[--ix] = v + 1;
}

void
solve()
{
	for (int u = 0; u < V; ++u)
		visited[u] = false;

	for (int u = 0; u < V; ++u)
		if (!visited[u])
			visit(u);
}

int
main(int argc, char **argv)
{
	scanf("%d", &V);
	for (int v = 0; v < V; ++v)
	{
		for (int u = 0; u < V; ++u)
			G[v][u] = false;
	}

	int E;
	scanf("%d", &E);
	for (int i = 0; i < E; ++i)
	{
		int s, t;
		scanf("%d%d", &s, &t);
		G[s - 1][t - 1] = true;
	}

	ix = V;
	solve();

	for (; ix < V; ++ix)
		printf("%d\n", out[ix]);

	return 0;
}

Measured memory_bytes: 1776
A, B, C, D, E, F = map(int, input().split())
ans1 = 100 * A
ans2 = 0
n = 0
for x in range(100, F+1, 100):
    for y in range(F+1):
        if x + y == 0:
            continue        
        if x + y > F:
            continue
        if (x / 100) * E < y:
            continue

        s = []
        for i in range((y//C)+1):
            for j in range((y//D)+1):
                if y == i * C + j * D:
                    s.append((i, j))
                    break
            if len(s):
                break
        if len(s) == 0:
            continue

        w = []
        for i in range((x//(100*A))+1):
            for j in range((x//(100*B))+1):
                if x == 100 * A * i + 100 * B * j:
                    w.append((i, j))
                    break
            if len(w):
                break

        if len(w) == 0:
            continue

        if n < (y/(x+y)):
            n = y/(x+y)
            ans1 = x + y
            ans2 = y

print(ans1, ans2)


Measured memory_bytes: 46812
import java.math.BigDecimal;
import java.util.*;
import java.util.stream.Collectors;

class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a1 = new int[n];
        int[] a2 = new int[n];
        for (int i = 0; i < n; i++) {
            a1[i] = sc.nextInt();

        }
        for (int i = 0; i < n; i++) {
            a2[i] = sc.nextInt();

        }
        int result = 0;
        int before = 0;
        for (int i = 0; i < n; i++) {
            int candies = a1[i] + before;

            for (int j = i; j < n; j++) {
                candies += a2[j];
            }

            if (candies > result) {
                result = candies;
            }

            before += a1[i];
        }
        System.out.println(result);
    }
}

Measured memory_bytes: 23124
n,q = map(int, input().split())
s = input()
li = [0]*(n+1)
for i in range(n):
    if s[i:i+2] == "AC":
        li[i+1] = li[i] + 1
    else:
        li[i+1] = li[i]

for i in range(q):
    l, r = map(int, input().split())
    print(li[r-1] - li[l-1])

Measured memory_bytes: 6188
num = [0,1,2,3,4,5,6,7,8,9]
while (str = gets) != "0 0\n" do
	strArr = str.split("\s")
	tmp = 0
	num.combination(strArr[0].to_i).each do |i|
		if i.inject{|sum, n| sum + n} == strArr[1].to_i then
			tmp += 1
		end
	end
	p tmp
end

Measured memory_bytes: 6108
#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60, lmod = 1e9+7;

const int MAX_N = 2003;

int N,K,c[MAX_N][MAX_N],s[MAX_N][MAX_N];

void prepare(){
  REP(x,1,2*K+2)
    REP(y,1,2*K+2) s[x][y] = c[x][y] + s[x-1][y] + s[x][y-1] - s[x-1][y-1];
}

int query(int x1,int y1,int x2,int y2){
  // return sum(x1<=x<=x2,y1<=y<=y2)
  if(x1>x2||y1>y2) return 0;
  else return s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> N >> K;
  fill(c[0],c[MAX_N-1],0);
  rep(i,N){
    int x,y; char cc;
    cin >> x >> y >> cc;
    if(cc=='B') x += K;
    x %= (2*K); y %= (2*K);
    c[x+1][y+1]++;
  }
  prepare();
  int ans = -INF;
  REP(x,1,K+1) REP(y,1,K+1){
    int temp = query(x,y,x+K-1,y+K-1) + query(x+K,y+K,2*K,2*K) + query(1,1,x-1,y-1)
               + query(x+K,1,2*K,y-1) + query(1,y+K,x-1,2*K);
    ans = max(ans,max(temp,N-temp));
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 31616
package main

import "fmt"

func nextInt() int {
	var x int
	fmt.Scan(&x)
	return x
}

func main() {
	a := nextInt()
	b := nextInt()

	if b%a == 0 {
		fmt.Println(a + b)
	} else {
		fmt.Println(b - a)
	}
}


Measured memory_bytes: 512
//Number 1159
#include <stdio.h>

int main(void)
{
  int i, n, p, stone = 0;
  int human[50] = {0};

  while(1)
    {
      scanf("%d %d", &n, &p);

      stone = p;
      if(n == 0 && p == 0)
	break;

      for(i=0; i<n; i++)
	human[i] = 0;

      i = 0;
      while(human[i]!=p)
	{
	  if(stone==0)
	    {
	      stone = human[i];
	      human[i] = 0;
	    }
	  else
	    {
	      human[i]++;
	      stone--;
	    }
	  i++;
	  if(i==n)
	    i = 0;
	}

      printf("%d\n", i);

    }

  return 0;
}

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

int main() {
  int S;
    
cin >> S;
  int Ans = 0;
  while(S>=500){
    Ans +=1000;
    S -=500;  
  }
  
  while(S>=5){
    Ans +=5;
    S -=5;  
  }
  
  cout << Ans;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

// RMQ ans RUQ
struct SqrtDecomposition{
    const int INF = (1LL << 31) - 1;
    int n, sqrtn, k;
    VI dat, buk, lazy;
    vector<bool> lazyflag;

    void init(int x){
        n = x;
        sqrtn = sqrt(n);
        k = (n + sqrtn - 1) / sqrtn;
        dat.assign(sqrtn * k, INF);
        buk.assign(k, INF);
        lazy.assign(k, 0);
        lazyflag.assign(k, false);
    }

    void eval(int b){
        if (!lazyflag[b]) return;
        lazyflag[b] = false;
        FOR(i, sqrtn * b, sqrtn * (b+1) - 1){
            dat[i] = lazy[b];
        }
    }

    // [l, r)
    void update(int l, int r, int x){
        REP(b,k){
            int p = sqrtn * b;
            int q = sqrtn * (b+1);
            if (q <= l || r <= p) continue;
            if (l <= p && q <= r){
                buk[b] = x;
                lazyflag[b] = true;
                lazy[b] = x;
            }else{
                eval(b);
                FOR(i,max(l,p),min(r,q)-1){
                    dat[i] = x;
                }
                buk[b] = INF;
                FOR(i,p,q-1){
                    buk[b] = min(buk[b], dat[i]);
                }
            }
        }
    }

    // [l, r)
    int query(int l, int r){
        int ret = INF;
        REP(b,k){
            int p = sqrtn * b;
            int q = sqrtn * (b+1);
            if (q <= l || r <= p) continue;
            if (l <= p && q <= r){
                ret = min(ret, buk[b]);
            }else{
                eval(b);
                FOR(i,max(l,p),min(r,q)-1){
                    ret = min(ret, dat[i]);
                }
            }
        }
        return ret;
    }
};

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

    SqrtDecomposition sd;

    sd.init(n);

    while (q--){
        int t, l, r;
        scanf("%d %d %d", &t, &l, &r);
        if (t == 0){
            int x;
            scanf("%d", &x);
            sd.update(l,r+1,x);
        }else{
            printf("%d\n", sd.query(l,r+1));
        }
    }



    return 0;
}

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

int n, a[1000000], ans = 0;
map<int, int> m;

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], m[a[i]]++;
    map<int, int>::iterator it;
    for (it = m.begin(); it != m.end(); it++){
        if (it->first > it->second) ans += it->second;
        else ans += it->second - it->first;
    }
    cout << ans;
}

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


int main()
{

     ll i,j=0,n,m,k;
      cin>>n>>k;
      ll ara[n];
      for(i=0;i<n;i++)
      {

          cin>>ara[i];
      }

     sort(ara,ara+n,greater<ll>());
     for(i=0;i<k;i++)
     {

         j+=ara[i];
     }
     cout<<j<<endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
class Main{
    static void solve(int n[]){

    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] c = in.next().toCharArray();
        int temp;
        for(int bit = 0; bit < 8; bit++){
            temp  = c[0] - '0';
            for(int i = 0; i < 3; i++){
                if((bit & (1 << i)) != 0)  temp += c[i+1] - '0';
                else temp -= c[i+1] - '0';
            }
            if(temp == 7){
                System.out.print(c[0]);
                for(int i = 0 ; i < 3; i++){
                    if((bit & (1 << i)) != 0) System.out.print("+" + c[i+1]);
                    else System.out.print("-"+ c[i+1]);
                }
                System.out.println("=7");
                return;
            }
        }
    }
}

Measured memory_bytes: 21844
E = ["S", "H", "C", "D"]
n = int(input())
A = [[0 for j in range(14)] for i in range(4)]
for j in range(n):
    a, b = input().split()
    a = E.index(a)
    b = int(b)
    A[a][b] = 1

for z in range(4):
    for c in range(1, 14):
        if A[z][c] == 0:
            print(f"{E[z]} {c}")


Measured memory_bytes: 5612
#３つの整数aa、bb、ccを読み込み、aaから bbまでの整数の中に、
# ccの約数がいくつあるかを求めるプログラム

list = input().split()
count = 0
a = int(list[0]); b = int(list[1]); c = int(list[2])

while a <= b:
	if c % a == 0:
		count += 1
	a += 1

print(count)


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

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

    int L;
    cin >> L;

    int sum=0;

    for(int i=1; i<=N; i++){
        sum += L+i-1;
    }

    if(L>=0){
        cout << sum-L << endl;
    }

    else if(N<1-L){
        cout << sum-L-N+1 << endl;
    }

    else{//sum-L+1
        cout << sum << endl;
    }

}

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

int main(void){
	int h,w,k,count=0;
	scanf("%d %d %d",&h,&w,&k);
	char c[h][w+1];
	char a;
	
	for(int i=0;i<h;i++){
		scanf("%c",&a);
		c[i][w]=0;
		for(int j=0;j<w;j++){
			scanf("%c",&c[i][j]);
			if(c[i][j]=='#'){
				c[i][w]++;
				count++;
			}
		}
	}
	
	int num,numnum,ans=0;
	
	for(int i=0;i<pow(2,h);i++){
		num=count;
		for(int j=0;j<h;j++){
			if(i&(1<<j)){
				num-=c[j][w];
				if(num<k){
					break;
				}
			}
		}
		for(int l=0;l<pow(2,w);l++){
			numnum=num;
			for(int m=0;m<w;m++){
				if(l&(1<<m)){
					for(int n=0;n<h;n++){
						if(c[n][m]=='#'&&!(i&(1<<n))){
							numnum-=1;
						}
					}
					if(numnum<k){
						break;
					}
				}		
			}
			if(numnum==k){
				ans++;
			}
		}
		
	}
	printf("%d",ans);
}

Measured memory_bytes: 2596
bingo_int_list = [[int(i) for i in input().split()] for _ in range(3)]
N = int(input())
num_int_list = [int(input()) for _ in range(N)]
num_int_set = set(num_int_list)

bingo_bin_list = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

for i in range(3):
    for j in range(3):
        if bingo_int_list[i][j] in num_int_set:
            bingo_bin_list[i][j] = 1

# check row
for i in range(3):
    if sum(bingo_bin_list[i]) == 3:
        print('Yes')
        exit()

# check column
for i in range(3):
    if bingo_bin_list[0][i] + bingo_bin_list[1][i] + bingo_bin_list[2][i] == 3:
        print('Yes')
        exit()

# check diagonal
if bingo_bin_list[0][0] + bingo_bin_list[1][1] + bingo_bin_list[2][2] == 3 or bingo_bin_list[0][2] + bingo_bin_list[1][
    1] + bingo_bin_list[2][0] == 3:
    print('Yes')
    exit()

print('No')


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

int k[20];

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

	string s;
	cin >> s;

	int idx = 0;
	string ss;
	bool minus = false;
	while(idx < s.size()) {
		while(idx < s.size() && s[idx] != '+' && s[idx] != '-') ss += s[idx++];
		//cout << ss << endl;

		int t = 0;
		int i = 0;
		bool flag = false;
		while(i < ss.size() && ss[i] != 'x') {
			t = t * 10 + ss[i++] - '0';
			flag = true;
		}
		if(!flag) t = 1;
		if(minus) t *= -1;

		int d = 0;
		if(i < ss.size()) {
			i++;// x
			if(i == ss.size()) {
				d = 1;
			}
			else {
				i++; // ^
				d = ss[i] - '0';
			}
		}
		k[d] = t;
		if(idx < s.size()) {
			minus = s[idx] == '-';
			idx++;
		}
		ss = "";
	}
	vector<ll> ans;
	for(ll i = 5000; i >= -5000; i--) {
		ll sum = 0;
		for(int j = 0; j <= 5; j++) {
			if(k[j] == 0) continue;
			ll p = 1;
			for(int c = 0; c < j; c++) {
				p *= i;
			}
			sum += k[j] * p;
		}
		if(i != 0 && sum == 0) {
			if(i > 0) cout << "(x" << -i << ")";
			else cout << "(x+" << -i << ")";
		}
	}
	cout << endl;
}

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

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const int MC = 3003;
LL fct[MC+1];
LL invfct[MC+1];
int N;
LL M;
LL dp[MC][MC];

void build(){
	fct[0] = fct[1] = 1;
	repp(i,2,MC+1){
		fct[i] = fct[i-1] * i % M;
	}
	LL x = fct[MC];
	invfct[MC] = 1;
	for(int i = M - 2 ; i > 0 ; i >>= 1){
		if(i % 2 == 1) (invfct[MC] *= x) %= M;
		(x *= x) %= M;
	}
	repm(i,MC,0){
		invfct[i-1] = invfct[i] * i % M;
	}
}

int main(){
	cin >> N >> M;
	build();
	dp[0][0] = 1;
	repp(i,1,N+1){
		dp[i][0] = 1;
		repp(j,1,N+1) dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] * (j+1)) % M;
	} 
	LL ans = 0;
	LL p = 2 , q = 1;
	repm(i,N,-1){
		LL c = (i&1?M-1:1) * p % M * fct[N] % M * invfct[i] % M * invfct[N-i] % M;
		repp(j,0,N+1){
			(ans += dp[i][j] * c) %= M;
			c = c * q % M;
		}
		p = p * p % M;
		q = q * 2 % M;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 70656
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvv vector<vvl>
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvvl(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

vvl G = vv(1001, 0, 0, ll);
vll tmp, ans(1001, 0);
vll use(1001, 0), par(1001, -1);

void dfs(ll now, ll st){
  use[now] = 1;
  for(int i=0;i<G[now].size();i++){
    ll to = G[now][i];
    if(use[to]&&to!=st) return;
  }
  for(int i=0;i<G[now].size();i++) {
    ll to = G[now][i];
    if(to==st){
      tmp = vll();
      ll k = now;
      while(k!=-1){
        tmp.push_back(k);
        k = par[k];
      }
      if(ans.size()>tmp.size()) ans = tmp;
      return;
    }
  }
  for(int i=0;i<G[now].size();i++){
    par[G[now][i]] = now;
    dfs(G[now][i], st);
  }
  use[now] = 0;
}
int main(int argc, char const *argv[]) {
  ll a, b, n, m;std::cin >> n >> m;
  re(i, m){
    std::cin >> a >> b;
    G[a].push_back(b);
  }

  for(int i=1;i<=n;i++){
    re(j, n+1) par[j] = -1, use[j] = 0;
    dfs(i, i);
  }
  if(ans.size()==1001) std::cout << -1 << '\n';
  else{
    std::cout << ans.size() << '\n';
    re(i, ans.size()) std::cout << ans[ans.size()-1-i] << '\n';
  }
  return 0;
}


Measured memory_bytes: 504
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,a[N],pos[N];
void init()
{
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;++i) scanf("%d",&a[i]),pos[a[i]]=i;
}
void work()
{
    int i,cnt=0,now=0;
    for(i=n-1;i;--i)
    {
        if(!cnt)
        {
            if(pos[i]>pos[i+1]) ++cnt,now=i+1;
            continue;
        }
        if(pos[now]<=pos[i]&&pos[i]<=pos[i+1]) continue;
        if(pos[i]<=pos[i+1]&&pos[i+1]<=pos[now]) continue;
        if(pos[i+1]<=pos[now]&&pos[now]<=pos[i]) continue;
        ++cnt,now=i+1;
    }
    printf("%d\n",cnt);
}

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

Measured memory_bytes: 1792
S = input()
alpha = 'abcdefghijklmnopqrstuvwxyz'
if S == alpha[::-1]:
    print(-1)
else:
    rest = sorted(list(set(alpha) - set(S)))
    if rest:
        print(S + rest[0])
    else:
        for i in range(len(S)-1, 0, -1):
            if S[i-1] < S[i]:
                break
        rest = sorted([s for s in S[i:] if s > S[i-1]])
        print(S[:i-1] + rest[0])

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

using namespace std;

int main(){
    int A,B,C,X,count=0;
    cin>>A>>B>>C>>X;
    for(int i=0;i<=A;i++){
        for(int j=0;j<=B;j++){
            for(int k=0;k<=C;k++)
            if(i*500+j*100+k*50==X){
                count++;
                break;
            }
        }
    }
    cout <<count <<endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>

using namespace std;

int main()
{
    int n, ans = 0, x;
    scanf("%d", &n);
    while(n--)
    {
        scanf("%d", &x);
        while(!(x&1))
            ++ans, x>>=1;
    }
    printf("%d\n", ans);
}


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

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

  string s;
  cin >> s;

  int ans = 0;
  rep(v, 1000) {
    vector<int> a(3);
    a[0] = v / 100;
    a[1] = v / 10 - (v / 100) * 10;
    a[2] = v % 10;

    int now = 0;
    rep(i,n) {
      if ((int)(s[i] - '0') == a[now]) now++;
      if (now == 3){
        ans++;
        break;
      }
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3684
from functools import reduce
import math


def length(p1, p2):
    sub2 = [(a - b)**2 for a, b in zip(p1, p2)]
    return math.sqrt(sum(sub2))


def r_center(lines):
    lines_sum = reduce(lambda a, b: a + b, lines)
    s = lines_sum / 2
    area = math.sqrt(s * (s - lines[0]) * (s - lines[1]) * (s - lines[2]))
    return 2 * area / (lines_sum)


def r_length(lines, r_center):
    x = (lines[0] + lines[2] - lines[1]) / 2
    b_l = math.sqrt(x**2 + r_center**2)
    a_l = math.sqrt((lines[2] - x)**2 + r_center**2)
    c_l = math.sqrt((lines[0] - x)**2 + r_center**2)
    return [a_l, b_l, c_l]


while True:
    positions = list(map(int, input().split()))
    if reduce(lambda a, b: a | b, positions) == 0:
        break
    p1, p2, p3 = [[i, j] for i, j in zip(positions[::2], positions[1::2])]

    lines = [length(a, b) for a, b in ((p1, p2), (p2, p3), (p3, p1))]
    lines_sum = reduce(lambda a, b: a + b, lines)

    r_c = r_center(lines)
    round_half = lines_sum / 2
    rc_len = r_length(lines, r_c)

    r1 = r_c * (round_half + rc_len[0] - r_c - rc_len[1] -
                rc_len[2]) / (2 * (round_half - lines[0]))
    r2 = r_c * (round_half + rc_len[1] - r_c - rc_len[0] -
                rc_len[2]) / (2 * (round_half - lines[1]))
    r3 = r_c * (round_half + rc_len[2] - r_c - rc_len[1] -
                rc_len[0]) / (2 * (round_half - lines[2]))

    print(r2, r3, r1)


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


int main() {
	int n;
	while (cin >> n, n) {
		string s; cin >> s;
		rep(j, n) {
			int cnt = 0; char back = s[0];
			ostringstream oss;
			rep(i, s.size()) {
				if (s[i] == back)cnt++;
				else {
					oss << cnt << back;
					cnt = 1; back = s[i];
				}
			}
			oss << cnt << back;
			s = oss.str();
		}
		cout << s << endl;
	}
	return 0;
}

Measured memory_bytes: 3344
#include <stdio.h>
#define M 2000000
#define INF -1
int N,S[M+1];
void MaxHeapify(int i){
  int left,right,lmax,tmp;
  left=2*i;
  right=2*i+1;
  if(left<=N && S[left]>S[i]) lmax=left;
  else lmax=i;
  if(right<=N && S[right]>S[lmax]) lmax=right;
  if(lmax!=i){
    tmp=S[i];
    S[i]=S[lmax];
    S[lmax]=tmp;
    MaxHeapify(lmax);
  }
}
int extractMax(){
  int maxvalue;
  if(N<1)return INF;
  maxvalue=S[1];
  S[1]=S[N--];
  MaxHeapify(1);
  return maxvalue;
}
void increaseKey(int i,int key){
  int tmp;
  if(key<S[i])return;
  S[i]=key;
  while(i>1 && S[i/2]<S[i]){
    tmp=S[i];
    S[i]=S[i/2];
    S[i/2]=tmp;
    i=i/2;
  }
}
void insert(int key){
  N++;
  S[N]=INF;
  increaseKey(N,key);
}
int main(){
  int key;
  char com[10];
  while(1){
    scanf("%s",com);
    if(com[0]=='e' && com[1]=='n') break;
    if(com[0]=='i'){
      scanf("%d",&key);
      insert(key);
    }
    else printf("%d\n",extractMax());
  }
  return 0;
}

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

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

int main() {

    int n; cin >> n;
    int t = n % 10;

    if (t == 3) {
        puts("bon");
    } else if (t == 0 || t == 1 || t == 6 || t == 8) {
        puts("pon");
    } else {
        puts("hon");
    }
}

Measured memory_bytes: 3636
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD 998244353
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

map<pair<i64, int>, i64> memo;

i64 solve(i64 bits, int len)
{
	if (len == 0) return 1;
	if (memo.count({ bits, len })) return memo[{bits, len}];

	i64 ret = solve(bits >> 1, len - 1) * ((bits & 1) + 1) % MOD;
	for (int l = 1; l <= len / 2; ++l) {
		i64 mask = (1LL << l) - 1;
		i64 sh = bits & mask;
		for (int j = l; j <= len - l; j += l) {
			sh &= (bits >> j) & mask;
			ADD(ret, solve(sh, l) * solve(bits >> (j + l), len - j - l));
		}
	}

	return memo[{bits, len}] = ret;
}

char S[110];
int N;

i64 apply(i64 bits, int top, int l)
{
	for (int i = 0; i < l; ++i) {
		if (S[i + top] == '0') bits &= ~(1LL << i);
	}
	return bits;
}

map<int, i64> memo2;

i64 solve(int top)
{
	if (top == N) return 1;
	if (memo2.count(top)) return memo2[top];

	i64 ret = solve(top + 1) * (S[top] == '1' ? 2 : 1) % MOD;
	for (int l = 1; l <= (N - top) / 2; ++l) {
		i64 mask = (1LL << l) - 1;
		i64 sh = apply(mask, top, l);
		for (int j = l; j <= (N - top) - l; j += l) {
			sh = apply(sh, j + top, l);
			ADD(ret, solve(sh, l) * solve(top + j + l));
		}
	}

	return memo2[top] = ret;
}

int main()
{
	scanf("%s", S);
	N = strlen(S);

	printf("%lld\n", solve(0));

	return 0;
}


Measured memory_bytes: 3072
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

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

ans = []
while len(arr) > 0:
    pos = -1
    for i in range(len(arr)):
        if arr[i] == i + 1:
            pos = i
    if pos == -1:
        print(-1)
        sys.exit(0)
    # print("arr, pos = ", arr, pos )
    ans.append(pos + 1)
    arr = arr[:pos] + arr[pos+1:]
ans.reverse()
for a in ans:
    print(a)




Measured memory_bytes: 7116
N = int(input())
Vi = list(map(int, input().split()))

s_Vi = sorted(Vi)

i = 1

while i < N:
    s_Vi2 = s_Vi[2:]
    s_Vi2.append(sum(s_Vi[:2])/2)
    s_Vi = sorted(s_Vi2)
    i += 1

print(s_Vi[0])

Measured memory_bytes: 3060
#include <algorithm>     //sort,二分探索,など
#include <bitset>        //固定長bit集合
#include <cmath>         //pow,logなど
#include <complex>       //複素数
#include <deque>         //両端アクセスのキュー
#include <functional>    //sortのgreater
#include <iomanip>       //setprecision(浮動小数点の出力の誤差)
#include <iostream>      //入出力
#include <map>           //map(辞書)
#include <numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include <queue>         //キュー
#include <set>           //集合
#include <stack>         //スタック
#include <string>        //文字列
#include <unordered_map> //イテレータあるけど順序保持しないmap
#include <unordered_set> //イテレータあるけど順序保持しないset
#include <utility>       //pair
#include <vector>        //可変長配列

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int mod = 1e+9 + 7;

//マクロ
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPD(i, n) for (ll i = (ll)(n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define FORD(i, a, b) for (ll i = (a); i >= (b); i--)
#define ALL(x) (x).begin(), (x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size())      //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000
#define MOD 10000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

int main()
{
  ll n, k;
  cin >> n >> k;
  ll nonover = n / k;
  ll over = nonover + 1;
  ll ans1 = n - nonover * k;
  ll ans2 = over * k - n;
  ll ans = min(ans1, ans2);
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 888
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x) (x).begin(), (x).end()
#define rep(i, s, n) for (i64 i = (s), i##_limit = (n); i < i##_limit; ++i)
#define repr(i, s, t) for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define repc(i, s, t) for (i64 i = (s), i##_limit = (t); i <= i##_limit; ++i)
#define var(type, ...) \
    type __VA_ARGS__;  \
    read(__VA_ARGS__);
#ifndef DBG
#define dump(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U>
inline bool chmax(T &a, const U &b) {
    return b > a && (a = b, true);
}
template <class T, class U>
inline bool chmin(T &a, const U &b) {
    return b < a && (a = b, true);
}
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
inline vector<T> makeV(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto makeV(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(makeV<T>(initValue, args...))>(
        sz, makeV<T>(initValue, args...));
}

template <class T>
inline istream &operator>>(istream &is, vector<T> &vec) {
    for (auto &e : vec) is >> e;
    return is;
}

inline void read() {}

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

inline void print() { cout << "\n"; }

template <class Head, class... Tail>
inline void print(Head &&head, Tail &&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream &operator<<(ostream &os, const vector<T> &vec) {
    static constexpr const char *delim[] = {" ", ""};
    for (const auto &e : vec) os << e << delim[&e == &vec.back()];
    return os;
}

template <class Container>
struct Rev {
    Container &x_;
    inline Rev(Container &x) : x_(x) {}
    inline auto begin() { return rbegin(x_); }
    inline auto end() { return rend(x_); }
};
// }}} End Header

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.setf(ios_base::fixed);
    cout.precision(12);

    var(i64, N, K);
    vector<int> P(N), C(N);
    read(P, C);

    rep(i, 0, N) P[i]--;

    i64 ans = -LINF;

    rep(start, 0, N) {
        int cur = start;
        vector<i64> buff;
        i64 total = 0;

        do {
            cur = P[cur];
            buff.push_back(C[cur]);
            total += C[cur];
        } while (cur != start);

        const int len = buff.size();

        if (total > 0) {
            i64 s = 0;
            rep(i, 0, min<i64>(K, len)) {
                s += buff[i];
                const int n = (K - (i + 1)) / len;
                chmax(ans, s + total * n);
            }
        } else {
            i64 s = 0;
            rep(i, 0, min<i64>(K, len)) {
                s += buff[i];
                chmax(ans, s);
            }
        }
    }

    print(ans);

    return 0;
}


Measured memory_bytes: 3812
#include<bits/stdc++.h>
using namespace std;
int main(){
  bool flag = true;
  while(flag){
    int a, b;
    cin >> a >> b;
if( a == 0 && b ==0) break;
    for(int i = 0; i<a;i++){
       for(int j = 0; j<b; j++){
           cout << '#';
}
cout << endl;
}
cout << endl;
}
}


Measured memory_bytes: 3076
import java.util.Scanner;

public class Main {
    public static void main(final String[] args) {
        final int p = 2;
        switch (p) {
        case 2:
            B.answer();
            break;
        case 1:
            A.answer();
            break;
        }
    }
}

class B {

    static void answer() {
        final Scanner sc = new Scanner(System.in);
        final int n = sc.nextInt();
        final int[] arrayA = new int[n];
        for (int i = 0; i < n; i++) {
            arrayA[i] = sc.nextInt();
        }
        final int[] arrayB = new int[n];
        for (int i = 0; i < n; i++) {
            arrayB[i] = sc.nextInt();
        }
        final int[] arrayC = new int[n];
        for (int i = 0; i < n - 1; i++) {
            arrayC[i] = sc.nextInt();
        }
        final int res = calc(arrayA, arrayB, arrayC);
        System.out.println(res);
    }

    static int calc(final int[] arrayA, final int[] arrayB, final int[] arrayC) {
        int total = 0;
        int prevRyori = -100;
        for (int i = 0; i < arrayA.length; i++) {
            final int ryoriNo = arrayA[i];
            final int manpuku = arrayB[ryoriNo - 1];
            total += manpuku;
            if (ryoriNo - prevRyori == 1) {
                total += arrayC[prevRyori - 1];
            }
            prevRyori = ryoriNo;
        }

        return total;
    }
}
class A {
    static void answer() {
        final Scanner sc = new Scanner(System.in);
        final int n = sc.nextInt();
        final int res = calc(n);
        System.out.println(res);
    }

    static int calc(final int n) {
        return n * n * n;
    }
}

Measured memory_bytes: 21844
<?php
fscanf(STDIN, "%s", $s);
fscanf(STDIN, "%s", $t);
$ans = 0;
for($i=0; $i< strlen($s) ;$i++){
  if(substr($s,$i,1) !== substr($t,$i,1)){
      $ans++;
  }
}
echo $ans;

?>

Measured memory_bytes: 16792
/*
 * ID: adityaa
 * LANG: C++
 */
#include <bits/stdc++.h>
using namespace std;

#define fio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(x, y) memset(x, y, sizeof x);
#define pii pair<int , int>
#define asdfg y1
#define int long long
#define double long double
#define endl '\n'
#define PI 3.14159265359

/*-----------------------------------------------------------------------*/

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

/*-----------------------------------------------------------------------*/

// check base cases n = 0 , n = 1
// max / min questions - check for binary search
const int maxn = (int) 1e6 + 6;
const double EPS = 1e-9;
const int INF = (int)1e18 + 18;
const int mod = (int) 1e9 + 7;
int n , a[410] , dp[410][410] , prefix[410];

signed main() {
    
    fio;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        prefix[i] = prefix[i - 1] + a[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++){
            dp[i][j] = INF;
        }
    }
    for(int i = 1; i <= n; i++){
        dp[i][i] = 0;
    }
    for(int len = 1; len <= n; len++){
        for(int i = 1; i <= n - len; i++){
            int j = i + len;
            for(int k = j - 1; k >= i; k--){
                dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k + 1][j] + prefix[j] - prefix[i - 1]);
            }
        }
    }
    
    cout << dp[1][n] << endl;
    
    
    
    return 0;
    
}


Measured memory_bytes: 1536
#ifdef DEBUG_IS_VALID
#define DEB 1 
#define _LIBCPP_DEBUG 0
#else
#define DEB 0
#define NDEBUG
#endif

#include <bits/stdc++.h>
using namespace std;

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back
#define fi first
#define se second
#pragma GCC optimize ("-O3")

using namespace std;

#define DUMPOUT cout
#define dump(...) if(DEB) DUMPOUT<<"  "<<#__VA_ARGS__<<" :["<<__LINE__<<":"<<__FUNCTION__<<"]"<<endl<<"    "; if(DEB) dump_func(__VA_ARGS__)
template<typename T1,typename T2>ostream& operator << (ostream& os, pair<T1,T2> p){cout << "(" << p.first << ", " << p.second << ")"; return os;}
template<typename T>ostream& operator << (ostream& os, vector<T>& vec) { os << "{"; for (int i = 0; i<vec.size(); i++) os << vec[i] << (i + 1 == vec.size() ? "" : ", "); os << "}"; return os; }
template<typename T>ostream& operator << (ostream& os, set<T>& st){cout << "{"; for(auto itr = st.begin(); itr != st.end(); itr++) cout << *itr << (next(itr)!=st.end() ? ", " : ""); cout << "}"; return os;}
template<typename T1,typename T2>ostream& operator << (ostream& os, map<T1,T2> mp){cout << "{"; for(auto itr = mp.begin(); itr != mp.end(); itr++) cout << "(" << (itr->first) << ", " << (itr->second) << ")" << (next(itr)!=mp.end() ? "," : ""); cout << "}"; return os; }

void dump_func(){DUMPOUT << endl;}
template <class Head, class... Tail>void dump_func(Head&& head, Tail&&... tail){ DUMPOUT << head; if (sizeof...(Tail) == 0) { DUMPOUT << " "; } else { DUMPOUT << ", "; } dump_func(std::move(tail)...);}
template<class T> inline bool chmax(T& a,T const& b){if(a>=b) return false; a=b; return true;}
template<class T> inline bool chmin(T& a,T const& b){if(a<=b) return false; a=b; return true;}

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<Pl>;
using vvp = vector<vp>;

const int INF = 1<<29;
const long long LINF=1LL<<59;


void solve(long long N){
  if(N%2){
    cout << N/2 << endl;
  }else{
    cout << (N-1)/2 << endl;
  }
}

int main(){
  std::cout << std::fixed << std::setprecision(15);
  long long N;
  scanf("%lld",&N);
  solve(N);
  return 0;
}


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

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i < (ll)(n); i++)
#define INF 1000000000000
#define MOD 1000000007
using ll = long long;

int main(){
  int n; cin>>n;
  string S; cin>>S;
  rep(i,(int)S.size()){
    cout<<(char)((S.at(i)-'A'+n)%26+'A');
  }
  cout<<endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
	int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

int l, r;

int main() {
	read(l), read(r);
	if (r - l >= 2019) {
		puts("0");
		return 0;
	} else {
		int ans = (l % 2019) * (r % 2019) % 2019;
		for (int i = l; i <= r; ++i)
			for (int j = i + 1; j <= r; ++j)
				ans = min(ans, (i % 2019) * (j % 2019) % 2019);
		write(ans);
		putchar('\n');
	}
	return 0;
}

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

int main(){
    int sum=0;
    for(int i=0;i<3;i++){
        int a;
        cin>>a;
        sum+=a;
    }
    if(sum>21){
        cout<<"bust";
    }else{
        cout<<"win";
    }
    cout<<endl;
    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);
		int a=sc.nextInt();

		int[] mono_bit=new int[a+1];
		int tmp=0;
		int[] bits= {1,2,4};
		for(int i=0; i<3; i++) {
			int kazu=sc.nextInt();
			for(int j=0; j<kazu; j++) {
				tmp=sc.nextInt();
				mono_bit[tmp]+=bits[i];
			}
		}
		int ninzu=0;

		for(int i=1; i<=a; i++) {
			if(mono_bit[i]==4 || mono_bit[i]==6 || mono_bit[i]==7) {
				ninzu++;
			}
		}
		System.out.println(ninzu);
	}
}


Measured memory_bytes: 26500
import java.io.IOException;
import java.io.InputStream;
import java.util.Collections;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {

	public static void main(String[] args) {

		FastScanner sc = new FastScanner();
		int N = sc.nextInt();
		int M = sc.nextInt();
		Queue<Integer> A = new PriorityQueue<>(Collections.reverseOrder());
		for (int i = 0; i < N; i++)
			A.add(sc.nextInt());

		long min = 0;

		for (int i = 0; i < M; i++)
			A.add(A.poll() / 2);

		for (int i = 0; i < N; i++)
			min += A.poll();

		System.out.println(min);

	}
}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}

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


Measured memory_bytes: 26992