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

template<typename First, typename Second, typename Third>
struct triple {
   First first;
   Second second;
   Third third;
};
using namespace std;
void solve(){
    int n,d,x,h;
    cin>>n>>d>>x;
    int c=0;
    for(int i=0;i<n;i++){
        cin>>h ;
        for(int j=0;;j++){
            if(j*h+1>d)
               break;
           // cout<<(j*h+1)<<" ";
            c++;
        }
      cout<<endl;
    }
    cout<<c+x;
}

int main(){
    std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdio>
 
using namespace std;
 
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define pb push_back
#define pf push_front
 
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
 
ll gcd(ll x, ll y) {
	ll r;
	while ((r = x % y) != 0) {
		x = y;
		y = r;
	}
	return y;
	}
ll lcm(ll x, ll y) {
	x /= gcd(x, y);
	y /= gcd(x, y);
	return (x*y);
}

int main()
{
    int a,b,c,x,n,cnt=0;
    vi sum;
    cin >> a >> b >> c >> x;
    rep(i,a+1){
        rep(j,b+1){
            rep(k,c+1){
                n=500*i+100*j+50*k;
                sum.pb(n);     
            }
        }
    }
    rep(i,sum.size()){
        if(sum[i]==x) cnt++;
    }
    cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 1400
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long

using namespace std;

ll mod = 1000000007;

bool comp(const int lh, const int rh) {

	return abs(lh) > abs(rh);
}
bool comp2(const int lh, const int rh) {

	return abs(lh) < abs(rh);
}

int main(int argc, char *argv[]) {
	int n, k;
	cin >> n >> k;
	vector<ll> a(n);
	bool neg = true;
	rep(i, n) {
		cin >> a[i];
		if (a[i] >= 0)neg = false;
	}

	if (n == k) {

		sort(a.begin(), a.end(), comp);
		ll ans = a[0];
		rep(i, k) {
			if (i == 0)continue;
			ans *= a[i];
			ans %= mod;
		}
		if (ans >= 0) {
			cout << ans;
		}
		else {
			cout << mod + ans;
		}
		return 0;

	}

	if (neg && k % 2 == 1) {
		sort(a.begin(), a.end(), comp2);

		ll ans = a[0];
		rep(i, k) {
			if (i == 0)continue;
			ans *= a[i];
			ans %= mod;
		}
		cout << mod + ans;
		return 0;

	}

	sort(a.begin(), a.end(), comp);
	ll ans = a[0];
	int minm = -1;
	int minp = -1;
	rep(i, k) {
		if (a[i] < 0)minm = i;
		if (a[i] >= 0)minp = i;
		if (i == 0)continue;
		ans *= a[i];
		ans %= mod;

	}

	if (ans < 0) {
		//最小の正を除いて最大の負を入れる
		//最小の負を除いて最大の正を入れる
		//二つ計算して大きいほう
		int maxm = 0;
		int maxp = 0;
		for (int i = k; i < n; i++) {
			if (maxm == 0 && a[i] < 0)maxm = i;
			if (maxp == 0 && a[i] >= 0)maxp = i;
			if (maxm != 0 && maxp != 0)break;
		}

		ll t1 = -1, t2 = -1;
		if (maxp != 0 && minm != -1) {
			t1 = a[maxp] * a[minp];
		}
		if (maxm != 0 && minp != -1) {
			t2 = abs(a[maxm]) * abs(a[minm]);
		}
		//a/b>c/d
		//a*d>c*b
		//cout << t1 << "," << t2 << endl;
		if (t1 > t2) {
			ans = a[maxp];
			rep(i, k) {
				if (i == minm)continue;

				ans *= a[i];
				ans %= mod;
			}
		}
		else {
			ans = a[maxm];
			rep(i, k) {
				if (i == minp)continue;

				ans *= a[i];
				ans %= mod;
			}
		}
		cout << ans;

	}
	else {
		cout << ans;
	}

	//while (1);

	return 0;
}


Measured memory_bytes: 4816
s = str(input())

checker = True
if 'hi' not in s:
    checker =False

while 'hi' in s:
    s = s.replace('hi','XX')

for i in range(1,len(s)-1):
    if s[i] =='X':
        if s[i-1] == 'i' or s[i-1] == 'h'or s[i+1] == 'i' or s[i+1] == 'h':
            checker = False
            break

if checker:
    print('Yes')
else:
    print('No')

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

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REV(i,j,k) for(int i=j;i>=k;i--)
#define FORR(i,j,k,l) for(int i=j;i<=k;i+=l)
#define inf         freopen("in.txt", "r", stdin)
#define outf        freopen("out.txt", "w", stdout)
#define pf          printf
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c)    scanf("%d %d %d", &a, &b, &c)
#define clean(mat,n)   FOR(i,0,n) mat[i].clear()
#define minn          (long long)-1000000000000000000
#define maxx          (long long) 1000000000000000000
#define mod          1000000007
#define M_PI           3.14159265358979323846  /* pi */
#define LL           long long
#define NL '\n'
#define cnd tree[idx]
#define lnd (idx<<1)
#define rnd ((idx<<1)+1)
#define PB push_back
#define F first
#define S second
#define MAX 1000010
#define MP make_pair
#define valid(nx,ny)  ((nx >= 0) && (nx < row) && (ny >= 0) && (ny < col))
typedef pair<int,int> pr;


int lev[MAX], dis[MAX], st[MAX], col, en[MAX], vis[MAX], in[MAX];
vector<int> mat[MAX], cost[MAX], ty[MAX];
stack<int> stk;

int dfs(int p)
{
    ///cout << p << endl;
    st[p] = col;

    int temp = 0;

    FOR(i,0,(int)mat[p].size()-1)
    {
        int x = mat[p][i];

        if(st[x] != col)
        {
            if(ty[p][i])
            {
                dis[x] = dis[p] + cost[p][i];
                temp = max(temp ,dfs(x));
            }
            else
            {
                dis[x] = dis[p] - cost[p][i];
                temp = max(temp ,dfs(x));
            }
        }
        else
        {
            if(ty[p][i])
            {
                int v = dis[x] - dis[p];
                if(v != cost[p][i]) return 1;
            }
            else
            {
                int v = dis[p] - dis[x];
                if(v != cost[p][i]) return 1;
            }
        }

    }

    en[p] = col;

    return temp;
}

int main()
{
    ios::sync_with_stdio(false);
    //inf;
    ///outf;

    int n, m, a, b, c, x, y, z;

    cin >> n >> m;

    FOR(i,0,m-1)
    {
        cin >> a >> b >> c;
        mat[a].PB(b);
        cost[a].PB(c);
        ty[a].PB(1);

        mat[b].PB(a);
        cost[b].PB(c);
        ty[b].PB(0);

    }
    
    col = 1;
    FOR(i,1,n)
    {
        if(st[i]==0)
        if(dfs(i))
        {
            cout << "No" << endl;
            return 0;
        }   
    }

    cout << "Yes";

    return 0;
}



Measured memory_bytes: 96256
from itertools import accumulate

N = int(input())
S = input()

B = [0] * N
W = [0] * N

for i, s in enumerate(S):
    if s == '#':
        B[i] = 1
    else :
        W[i] = 1

B = [0] + B
B = list(accumulate(B)) # -- 位置を左から進めて、左側にある黒の数
W = [0] + W[::-1]
W = list(accumulate(W))[::-1] # -- 位置を左から進めて、右側にある白の数

ans = []
for i in range(N+1):
    ans.append(B[i] + W[i])
print(min(ans))

Measured memory_bytes: 29176
#include <stdio.h>
#include <limits.h>
int main()
{
int n;
scanf("%d", &n);

long min = LONG_MAX;
long max = LONG_MIN;
long total = 0;

for(int i = 0; i < n; ++i)
{
long k;
scanf("%ld",&k);

total+=k;
if( min > k) min = k;
if( max < k) max = k;
}

printf("%ld %ld %ld\n", min, max, total);

return 0;
}

Measured memory_bytes: 1028
#include <bits/stdc++.h>
using namespace std;
int main(){
    string A;
    cin>>A;
    bool contain_A=false;
    bool contain_B=false;
    for(int i=0;i<A.size();i++){
        if(A[i]=='A')
            contain_A=true;
        else if(A[i]=='B')
            contain_B=true;
        if(contain_A==true&&contain_B==true){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
/*                         _
                        _ooOoo_
                       o8888888o
                       88" . "88
                       (| -_- |)
                       O\  =  /O
                    ____/`---'\____
                  .'  \\|     |//  `.
                 /  \\|||  :  |||//  \
                /  _||||| -:- |||||_  \
                |   | \\\  -  /'| |   |
                | \_|  `\`---'//  |_/ |
                \  .-\__ `-. -'__/-.  /
              ___`. .'  /--.--\  `. .'___
           ."" '<  `.___\_<|>_/___.' _> \"".
          | | :  `- \`. ;`. _/; .'/ /  .' ; |
          \  \ `-.   \_\_`. _.'_/_/  -' _.' /
===========`-.`___`-.__\ \___  /__.-'_.'_.-'================

                  Please give me AC.
*/

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <string>
#include <sstream>
#include <complex>
#include <bitset>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <chrono>
#include <random>

using namespace std;

using int64 = long long;
using uint64 = unsigned long long;
using vi = vector<int>;
using vl = vector<int64>;
using pii = pair<int, int>;
using pll = pair<int64, int64>;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define print(x) cout << (x) << '\n'
#define print2(x, y) cout << (x) << ' ' << (y) << '\n'
#define print3(x, y, z) cout << (x) << ' ' << (y) << ' ' << (z) << '\n'
#define printn(v) rep(i, (v).size() - 1) cout << (v)[i] << ' '; cout << (v)[n - 1] << '\n';
#define debug(x) cerr << #x << ": " << (x) << '\n'
#define debug2(x, y) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v) for (size_t _ = 0; _ < v.size(); ++_){cerr << #v << "[" << _ << "] : " << v[_] << '\n';}
// constant
const int INF = (1<<30) - 1;
const int64 INF64 = (1LL<<62) - 1;

template<typename T> T gcd(T a, T b) {
    if (a < b) return gcd(b, a);
    T r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

template<typename T> T lcm(const T a, const T b) {
    return a / gcd(a, b) * b;
}

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

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

// End of template.

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

    int64 a;
    double x;
    cin >> a >> x;

    print(a * (int64)round(100 * x) / 100);

    return 0;
}

/*
  ___   ___ _ __  _ __
 / __| / __| '_ \| '_ \
| (__ | (__| |_) | |_) |
 \___(_)___| .__/| .__/
           |_|   |_|
*/


Measured memory_bytes: 3748
# Here your code !
h, w = gets.chomp.split.map &:to_i
n = gets.chomp.to_i
a = gets.chomp.split.map &:to_i
ans = Array.new(h){Array.new(w,0)}
f = 0
y = x = 0
table = []
a.each.with_index(1) do |d, i|
  d.times{table.push(i)} 
end
i = 0
while true
  break if(i == table.size)
  if(x >= w)
    x = w - 1
    f = 1
  elsif(y >= h)
    y = h - 1
    f = 2
  elsif(x < 0)
    x = 0
    f = 3
  elsif(y < 0)
    y = 0
    f = 0
  elsif(ans[y][x] != 0)
    case f
    when 0 then
      x -= 1
    when 1 then
      y -= 1
    when 2 then
      x += 1
    when 3 then
      y += 1
    end
    f += 1
    f %= 4
  else
    ans[y][x] = table[i] 
    i += 1
  end
  case f
  when 0 then
    x += 1
  when 1 then
    y += 1
  when 2 then
    x -= 1
  when 3 then
    y -= 1
  end
end
ans.each{|aa|puts aa.join(" ")}

Measured memory_bytes: 4476
#include <iostream>

using namespace std;

int main() {
    int a,b,c,d,e,f,g,h;
    cin >>a>>b>>c>>d;
    e=a*b;
    f=c*d;
    if(e>f){
        cout<<e;
    }
    else{
        cout<<f;
    }
}

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

#define ll long long
#define vi vector<int>
#define vll vector<long long>
#define FOR_(i, a, b, x) for (int i = a; (x > 0) ? i < b : i > b; i += x)
#define FOR_1(e) FOR_(i, 0, e, 1)
#define FOR_2(i, e) FOR_(i, 0, e, 1)
#define FOR_3(i, a, e) FOR_(i, a, e, 1)
#define FOR_4(i, a, e, b) FOR_(i, a, e, b)
#define G5(a, b, c, d, e, ...) e
#define FOR_5(...) G5(__VA_ARGS__, FOR_4, FOR_3, FOR_2, FOR_1)
#define FOR(...)       \
    FOR_5(__VA_ARGS__) \
    (__VA_ARGS__)
#define IN(a, b) for (auto &a : b)

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    cout << (n % 1000 ? 1000 - n % 1000 : 0);
}

Measured memory_bytes: 3632
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef double db;
typedef long long ll;

const int N=55;

int n,c,l[N],p[N];
ll f[N*6][35];

ll Dp() {
	fo(i,0,n*c) fo(s,0,(1<<n-1)-1) f[i][s]=0;
	f[n*l[n]][0]=1;
	fo(i,0,n*c-1) {
		if (!(i%n)) continue;
		int x=p[i%n];
		fo(s,0,(1<<n-1)-1) {
			if (s&(1<<x-1)) continue;
			fo(j,i,n*c) f[min(n*c,max(j,i+n*l[x]))][s|(1<<x-1)]+=f[j][s]; 
		}
	}
	return f[n*c][(1<<n-1)-1];
}

int main() {
	scanf("%d%d",&n,&c);
	fo(i,1,n) scanf("%d",&l[i]);
	sort(l+1,l+n+1);
	fo(i,1,n-1) p[i]=i;
	db ans=0;
	do {ans+=Dp();} while (next_permutation(p+1,p+n));
	fo(i,1,n-1) ans/=i*c*1.0;
	printf("%.12lf\n",ans);
	return 0;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

use std::collections::BinaryHeap;

fn main() {
    let mut map: Vec<Vec<i64>> = vec![vec![0; 3]; 3];

    for i in 0..3 {
        for j in 0..3 {
            map[i][j] = read();
        }
    }

    for a1 in 0..100 {
        let b1 = map[0][0] - a1;
        let b2 = map[0][1] - a1;
        let b3 = map[0][2] - a1;

        let a2 = map[1][0] - b1;
        let a3 = map[2][0] - b1;

        if b2 + a2 == map[1][1]
            && b3 + a2 == map[1][2]
            && b2 + a3 == map[2][1]
            && b3 + a3 == map[2][2]
        {
            println!("Yes");
            return;
        }
    }
    println!("No");
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define lf long double
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef pair <ll,ll> ii;
typedef vector <ll> vi;
typedef vector <ii> vii;
typedef vector <bool> vb;
typedef vector <vector <ll> > vv;
typedef vector <string> vs;
typedef vector <lf> vf;
#define tr1(x) cerr << #x << ": " << x << endl
#define tr2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl
#define tr3(x,y,z) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define mod 1000000007
#define inf 9999999999999999ll
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n;
    cin>>n;
    cout<<n*n<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll= long long;
using vi= vector<int>;
using vvi= vector<vi>;
using vd= vector<double>;
using vvd= vector<vd>;
using vc= vector<char>;
using vs= vector<string>;
using vb= vector<bool>;
using vl= vector<ll>;
#define rep(i,x,n) for(int i=x; i<n; i++)
#define all(x) x.begin(), x.end()

int main(){
  char a;
  rep(i,0,3){
    cin >> a;
    if(a=='1'){
      cout << "9";
    }else{
      cout << "1";
    }
  }
  
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>pat[100000];
bool flag[100000];
bool ans = true;
int dfs(int node)
{
	if (flag[node])return 0;
	flag[node] = true;
	int c = 0;
	for (int i = 0; i < pat[node].size(); i++)c += dfs(pat[node][i]);
	if (c >= 2)ans = false;
	return c ^ 1;
}
int main()
{
	int num;
	scanf("%d", &num);
	for (int i = 0; i < num - 1; i++)
	{
		int za, zb;
		scanf("%d%d", &za, &zb);
		za--, zb--;
		pat[za].push_back(zb);
		pat[zb].push_back(za);
	}
	printf((1 - dfs(0)) && ans ? "Second\n" : "First\n");
}

Measured memory_bytes: 5888
#include <bits/stdc++.h>
// atoi : atoi(str.c_str())
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vc = vector<char>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using pii = pair<int, int>;
#define fix10 cout << fixed << setprecision(10);
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define MOD 1000000007

int main(){
  int n;
  cin >> n;
  vector<char> s(n);
  rep(i,n){
    cin >> s.at(i);
  }
  sort(s.begin(),s.end());
  
  char c = s.at(0);
  long count = 1;
  long answer = 1;
  for(int i=1;i<n;i++){
    if(s.at(i) == c){
      count++;
    }else{
      answer *= count+1;
      answer %= MOD;
      c = s.at(i);
      count = 1;
    }
  }
  answer *= count+1;
  answer %= MOD;
  answer--;
  cout << answer << endl;
}


Measured memory_bytes: 384
#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;

const ll mod = 1e9 + 7;
const int N = 200010;
VI e[N];
int depth[N];

void dfs(int now, int past, deque<VL> &dq){
    int h = 0;
    for (int next : e[now]){
        if (next == past) continue;
        depth[next] = depth[now] + 1;
        deque<VL> dq_next;
        dfs(next, now, dq_next);
        if (dq_next.size() > dq.size()){
            dq.swap(dq_next);
        }
        h = max(h, (int)dq_next.size());
        VVL tmp;
        while (!dq_next.empty()){
            VL va = dq.front(); dq.pop_front();
            VL vb = dq_next.front(); dq_next.pop_front();
            VL dp(3);
            dp[0] = (va[0] * vb[0]) % mod;
            dp[1] = (va[0] * vb[1] + va[1] * vb[0]) % mod;
            dp[2] = (va[2] * ((vb[0] + vb[1] + vb[2]) % mod) + va[1] * ((vb[1] + vb[2]) % mod) + va[0] * vb[2]) % mod;
            tmp.push_back(dp);
        }
        reverse(ALL(tmp));
        for (VL v : tmp) dq.push_front(v);
    }
    VVL tmp;
    REP(i,h){
        VL v = dq.front();
        dq.pop_front();
        v[0] = (v[0] + v[2]) % mod;
        v[2] = 0;
        tmp.push_back(v);
    }
    FORR(i,h-1,0) dq.push_front(tmp[i]);
    VL v({1, 1, 0});
    dq.push_front(v);

    // cout << "now " << now << endl;
    // REP(_,dq.size()){
    //     VL v = dq.front();
    //     dq.pop_front();
    //     cout << v[0] << " ";
    //     dq.push_back(v);
    // }
    // cout << endl;
    // REP(_,dq.size()){
    //     VL v = dq.front();
    //     dq.pop_front();
    //     cout << v[1] << " ";
    //     dq.push_back(v);
    // }
    // cout << endl;
}

int main() {
    int n;
    cin >> n;
    n++;
    FOR(i,1,n-1){
        int p;
        scanf("%d", &p);
        e[i].push_back(p);
        e[p].push_back(i);
    }

    deque<VL> dq;
    dfs(0, -1, dq);

    VL cnt(n+1);
    REP(i,n) cnt[depth[i]]++;

    VL two(n+1);
    two[0] = 1;
    REP(i,n) two[i+1] = (two[i] * 2) % mod;

    ll ans = 0;
    REP(i,n+1){
        VL v = dq.front();
        dq.pop_front();
        ans = (ans + v[1] * two[n - cnt[i]]) % mod;
        if (dq.empty()) break;
    }

    cout << ans << endl;


    return 0;
}





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

int n, a[5000], sz[5000];
vector<int> adj[5000];
vector<long long> dp1[5000], dp2[5000];
const long long INF = 1LL<<60;

void solve(int u, int p) {
    sz[u] = 1;
    dp1[u].resize(1, INF);
    dp2[u].resize(1, INF);
    if (a[u] > 0) dp1[u][0] = a[u];
    dp2[u][0] = a[u];
    for (int v : adj[u]) {
        if (v == p) continue;
        solve(v, u);
        sz[u] += sz[v];
        vector<long long> temp1(sz[u], INF), temp2(sz[u], INF);
        for (int i = 0; i < sz[u]-sz[v]; i++) {
            for (int j = 0; j < sz[v]; j++) {
                if (dp1[u][i] < INF && dp1[v][j] < INF)
                    temp1[i+j] = min(temp1[i+j], dp1[u][i] + dp1[v][j]);
                if (i+j+1 < sz[u] && dp1[u][i] < INF && (dp1[v][j] < INF || dp2[v][j] < 0))
                    temp1[i+j+1] = min(temp1[i+j+1], dp1[u][i]);
                temp2[i+j] = min(temp2[i+j], min(dp2[u][i] + dp2[v][j], INF));
                if (i+j+1 < sz[u] && (dp1[v][j] < INF || dp2[v][j] < 0))
                    temp2[i+j+1] = min(temp2[i+j+1], dp2[u][i]);
            }
        }
        dp1[u].swap(temp1);
        dp2[u].swap(temp2);
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        adj[u-1].push_back(v-1);
        adj[v-1].push_back(u-1);
    }
    solve(0, -1);
    int ans = 0;
    while (dp1[0][ans] == INF && dp2[0][ans] >= 0) ans++;
    cout << ans << endl;
}


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

#define rep(i, s, n) for (int i = s; i <= n; i++)

int H, W, K;
char S[10][1001];
int sums[10][1000];

int getNumWChoko(int pre_w,int pre_h,int now_w,int now_h)
{
    int ret;
    ret = sums[now_h][now_w];
    if(pre_w) ret-=sums[now_h][pre_w-1];
    if(pre_h) ret-=sums[pre_h-1][now_w];
    if(pre_w&&pre_h) ret+=sums[pre_h-1][pre_w-1];

    return ret;
}

int main()
{
    scanf("%d %d %d", &H, &W, &K);
    for (int i = 0; i < H; i++)
    {
        scanf("%s", S[i]);
    }

    //set sums
    rep(i, 0, H - 1)
    {
        rep(j, 0, W - 1)
        {
            sums[i][j] = S[i][j] == '0' ? 0 : 1;
        }
    }
    rep(i, 0, H - 1)
    {
        rep(j, 1, W - 1)
        {
            sums[i][j] += sums[i][j - 1];
        }
    }
    rep(i, 1, H - 1)
    {
        rep(j, 0, W - 1)
        {
            sums[i][j] += sums[i - 1][j];
        }
    }
    //test sums
    /*rep(i,0,H-1){
    rep(j,0,W-1){
      printf("%d ",sums[i][j]);
    }
    printf("\n");
  }*/


    int ans = 100000000;

    // 横全パターンに対し
    int counter = 0;
    int counter_max = pow(2, H - 1);

    rep(i, 0, counter_max - 1)
    {
        //横パターン用意
        int cut_pos_h[H + 1];
        int cut_num_h = 0;
        int cut_pos_now=0;
        int tmp=i;        
        while(tmp>0){
            if(tmp&1)
            {
                cut_pos_h[cut_num_h] = cut_pos_now;
                cut_num_h++;
            }
            cut_pos_now++;
            tmp /=2;
        }
        cut_pos_h[cut_num_h] = H-1;
        cut_pos_h[cut_num_h+1] = -1;

        //ex: cut_pos_h = {0,3,H-1,-1}        

        //横パターンに対応する縦チェック
        int cut_pos_w[W + 1];
        int cut_num_w = 0;
        int pre_w = 0;
        int ok=1;
        rep(j, 0, W - 1)
        {
            int pre_h=0, now_h;
            rep(k,0,H-1){
                now_h=cut_pos_h[k];
                if(now_h==-1) break;

                int num = getNumWChoko(pre_w,pre_h,j,now_h);
                if(num>K)
                {
                    pre_w=j;
                    cut_pos_w[cut_num_w]=j;
                    cut_num_w++;
                    num = getNumWChoko(pre_w,pre_h,j,now_h);
                    if(num>K)
                    {
                        ok=0;break;
                    }

                }

                pre_h=now_h+1;
            }
            if(!ok) break;
        }

        //okなら回数記録
        if(ok)
        {
            /*
            //test
            rep(j,0,cut_num_h-1)
            {
                printf("h%d, ",cut_pos_h[j]);
            }
            rep(j,0,cut_num_w-1)
            {
                printf("w%d, ",cut_pos_w[j]);
            }
            printf("\n");*/

            int tmp_ans=cut_num_w+cut_num_h;
            if(tmp_ans<ans) ans=tmp_ans;
        }

    }

    printf("%d",ans);


    return 0;
}

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

using namespace std;

void solve()
{
    char c;
    cin >> c;
    if (c >= 'A' && c <= 'Z') c = 'A';
    if (c >= 'a' && c <= 'z') c = 'a';
    cout << c << endl;
}

int main() 
{
    int tt = 1;
    //cin >> tt;
    while (tt--) solve();
}


Measured memory_bytes: 3524
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<utility>
#include<tuple>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define BIL ((ll)1e9)
#define MOD ((ll)1e9+7)
#define INF (1LL<<62)           //1LL<<63でオーバーフロー

int main(int argc,char* argv[]){
    int n;
    cin >> n;
    string s;
    cin >> s;

    int count=0;
    for(int i=0;i<n;i++){
        static int rp=n-1;
        if(s[i]=='W'){
            for(rp;rp>=0;rp--){
                if(i>=rp)break;
                if(s[rp]=='R'){
                    s[i]='R';
                    s[rp]='W';
                    count++;
                    rp--;
                    break;
                }
            }
        }
        if(i>=rp)break;
    }

    cout << count << endl;

    return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n); i >= 0; i--)
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int INF = 2100100100;
const int MOD = 1e9 + 7;

// 多次元 vector 生成
template <class T> vector<T> make_vec(size_t a) { return vector<T>(a); }
template <class T, class... Ts> auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

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

    int n;
    double t, a;
    cin >> n >> t >> a;
    vector<double> h(n);
    REP(i, n) { cin >> h.at(i); }

    REP(i, n) { h[i] = abs((t - 0.006 * h[i]) - a); }
    cout << min_element(ALL(h)) - h.begin() + 1 << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<deque>
#include<tuple>
#include<queue>
#include<map>
#include<cstdint>
#include<unordered_map>
//#include<boost/multiprecision/cpp_int.hpp>


#define rep(i, n) for(int i = 0; i < ( int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define F first
#define S second


//namespace mp = boost::multiprecision;

//using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

int size(int n) {
	int count = 0;
	while (n > 0) {
		n /= 10;
		count++;
	}
	return count;
}

typedef pair<int, int> P;

bool ps1(const P& element1, const P& element2)
{//first昇順
	return element1.first < element2.first;
}
bool ps2(const P& element1, const P& element2)
{//first降順
	return element1.first > element2.first;
}
bool ps3(const P& element1, const P& element2)
{//second昇順
	return element1.second < element2.second;
}
bool ps4(const P& element1, const P& element2)
{//second降順
	return element1.second > element2.second;
}
int main() {
	int N;
	int ret=scanf("%d", &N);
	int sizeN = size(N);
	string S357 = "357";
	int i = 21;
	int ans = 0;
	while (i < pow(4, sizeN)) {
		deque<char>tmpS;
		vector<int>count(3);
		int tmp = i;
		bool flag = true;
		while (tmp > 0) {
			int ttmp = tmp % 4;
			rep(j, 3) {
				if (ttmp  == j + 1) {
					tmpS.push_front(S357[j]);
					count[j]++;
				}
				else if (ttmp == 0) {
					flag = false;
					break;
				}
			}
			tmp /= 4;
		}
		if (*min_element(all(count)) > 0&&flag) {
			string s = "";
			rep(j, tmpS.size()) {
				s += tmpS[j];
			}
			int aa = stoi(s);
			if (aa <= N) {
				ans++;
			}
		}

		i++;
	}
	printf("%d\n", ans) ;

}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
	    Scanner scanner = new Scanner(System.in);

	    int N = Integer.parseInt(scanner.next());
	    int[] A = new int[N];

	    for (int i=0; i<N; i++) {
	    	A[i] = Integer.parseInt(scanner.next());
	    }

	    int max = Integer.MAX_VALUE;
	    for (int i=0; i<N-1; i++) {
	    	int a = uclid(A[i], A[i+1]);
	    	if (max > a) {
	    		max=a;
	    	}
	    }
	    
	   
	    System.out.println(max);
	}
	
	public static int uclid(int m, int n) {
		if (m<n) {
			m ^= n;
			n^=m;
			m^=n;
		}
		
		while (true) {
			int t=m%n;
			if (t==0) {
				return n;
			} else {
				m=n;
				n=t;
			}
		}
	}

}

Measured memory_bytes: 59724
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <iomanip>
#include <cmath>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using ll = long long;
namespace mp = boost::multiprecision;

ll BASE_NUM = 1000000007;

int main()
{
    // 整数の入力
    ll a,b,c;
    cin >> a >> b >> c;
    ll diff = c- a -b;
    if (diff <= 0){
        cout << "No" << endl;
    }else if(4 * a * b < diff * diff){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
   return 0;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define INF 0x6fffffff
#define INFL 0x6fffffffffffffffLL

int main() {
	ll		a,b,c,h,i,j,k,l,m,n,x,y;
	ll		ans = 0;
	string	s;
	cin >> x >> y;
	for(i=0;i<=x;i++) {
		if ((i*2 + (x-i)*4) == y) {
			cout << "Yes" << endl;
			return 0;
		}
	} 
	//vector<ll>	aa(n);
	//for(i=0;i<n;i++) cin >> aa[i];
	//vector<ll>	dp(n+1,INFL);
	//vector<vector<ll>>	dp2(x , vector<ll>(y,INFL));

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


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

int main() {
  int A, B;
  cin >> A >> B;
  vector<bool> ans(4, true);
  ans[A] = false;
  ans[B] = false;
  for (int i = 1; i <= 3; ++i) {
    if (ans[i]) cout << i << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
    int n,k;string s;
    cin>>n>>s>>k;
    char c=s[k-1];
    for(int i=0;i<n;i++){
        if(s[i]==c) cout<<c;
        else cout<<'*';
    }
}

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

int main(){
  int D;
  cin >> D;
  if(D == 25) cout << "Christmas\n";
  if(D == 24) cout << "Christmas Eve\n";
  if(D == 23) cout << "Christmas Eve Eve\n";
  if(D == 22) cout << "Christmas Eve Eve Eve\n";
  return 0;
}


Measured memory_bytes: 256
s = input()
length = len(s)
count = 0
for i in range(len(s)) :
    s = s[:-1]
    count += 1
    if len(s) % 2 == 1:
        continue
    elif s[:len(s) // 2] == s[len(s) // 2:] :
        print(length-count)
        break

Measured memory_bytes: 3060
#include<stdio.h>

int main()
{
	int n ;
	while( scanf( "%d", &n ) != EOF )
	{
		printf( "3C" ) ;
		n %= 39 ;

		if( n )
			n < 10 ? printf( "0%d\n" ,n ) : printf( "%d\n" ,n ) ;
		else
			printf( "39\n" ) ;

	}

	return 0 ;

}

Measured memory_bytes: 604
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <utility>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
#include <climits>
#include <numeric>
#include<stdio.h>
#include <queue>
#include <iomanip>
#include <float.h>
#include <set>
#include<functional>
#include <stack>
#include <time.h>
#include <climits>
#include <bitset>
#include <fstream>
using namespace std;
typedef pair<int, int>p;
long long gcd(long long a, long long b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
vector<long long> divisor(long long n) {
	vector< long long> ret;
	for (long long i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			ret.push_back(i);
			if (i * i != n) ret.push_back(n / i);
		}
	}
	sort(begin(ret), end(ret));
	return (ret);
}
struct LazySegmentTree {
private:
	int n;
	vector<int> node, lazy;
	vector<bool> lazyFlag;

public:
	LazySegmentTree(vector<int> v) {
		int sz = (int)v.size();
		n = 1; while (n < sz) n *= 2;
		node.resize(2 * n - 1);
		lazy.resize(2 * n - 1, INT_MAX);
		lazyFlag.resize(2 * n - 1, false);

		for (int i = 0; i<sz; i++) node[i + n - 1] = v[i];
		for (int i = n - 2; i >= 0; i--) node[i] = min(node[i * 2 + 1], node[i * 2 + 2]);
	}

	void lazyEvaluate(int k, int l, int r) {
		if (lazyFlag[k]) {
			node[k] = lazy[k];
			if (r - l > 1) {
				lazy[k * 2 + 1] = lazy[k * 2 + 2] = lazy[k];
				lazyFlag[k * 2 + 1] = lazyFlag[k * 2 + 2] = true;
			}
			lazyFlag[k] = false;
		}
	}

	void update(int a, int b, int x, int k = 0, int l = 0, int r = -1) {
		if (r < 0) r = n;
		lazyEvaluate(k, l, r);
		if (b <= l || r <= a) return;
		if (a <= l && r <= b) {
			lazy[k] = x;
			lazyFlag[k] = true;
			lazyEvaluate(k, l, r);
		}
		else {
			update(a, b, x, 2 * k + 1, l, (l + r) / 2);
			update(a, b, x, 2 * k + 2, (l + r) / 2, r);
			node[k] = min(node[2 * k + 1], node[2 * k + 2]);
		}
	}

	int find(int a, int b, int k = 0, int l = 0, int r = -1) {
		if (r < 0) r = n;
		lazyEvaluate(k, l, r);
		if (b <= l || r <= a) return INT_MAX;
		if (a <= l && r <= b) return node[k];
		int vl = find(a, b, 2 * k + 1, l, (l + r) / 2);
		int vr = find(a, b, 2 * k + 2, (l + r) / 2, r);
		return min(vl, vr);
	}
};
long long mod = 1000000007;
long long a, b, c, d;
long long num(long long x) {
	long long k = x / c + x / d - x / (c*d / gcd(c, d));
	return x - k;
}
signed main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(16);
	int n;
	cin >> n;
	priority_queue<p, vector<p>, greater<p> >que;
	int a, b;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		que.push(p(b, a));
	}
	long long tmp = 0;
	while (!que.empty()) {
		p now = que.top();
		que.pop();
		tmp += now.second;
		if (tmp > now.first) {
			cout << "No";
			return 0;
		}
	}
	cout << "Yes";
}

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

#define int long long

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

signed main(){
    int N;cin>>N;
    int mi=LLONG_MAX,ans=LLONG_MIN;
    rep(i,N){
        int a;cin>>a;
        chmax(ans,a-mi);
        chmin(mi,a);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
using Int = int_fast64_t;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	Int n, k; cin >> n >> k;
	vector<Int> a(n);
	for(auto &i:a) cin >> i;
	double l = 1e-5, r = 1e9;
	for(Int i=0; i<100; ++i){
		double m = (l + r) / 2;
		Int t = 0;
		for(auto j:a){
			t += max(0, (int)(((double)j - 1e-5) / m));
		}
//		cerr << l << " " << m << " " << r << " " << t << "\n";
		if(t <= k) r = m;
		else l = m;
	}
	cout << (Int)(r + 1) << "\n";
}

Measured memory_bytes: 4728
fun main (args: Array<String>) {
	
	val list = readLine()!!.split(" ").map(String::toInt)
	
	var j : Int
	var money : Int
	
	var num1 : Int = -1
	var num2 : Int = -1
	var num3 : Int = -1
	
	
	for (h in 0..list[0]) {
		for (i in 0..(list[0] - h)) {
			j = list[0] - h - i
			money = (10000 * h) + (5000 * i) + (1000 * j)
			if (money == list[1]) {
				num1 = h
				num2 = i
				num3 = j
				return println("${num1} ${num2} ${num3}")
			}
		}
		
	}
	
	println("${num1} ${num2} ${num3}")
	
}

Measured memory_bytes: 37868
#include<bits/stdc++.h>
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
const int N = 1e5+5;
int arr[N],n;
int dp[N];
int k;
int INF=0x3f3f3f3f;
int solve (int i){
if(i>=n-1)return 0;
int &ret=dp[i];
if(~ret)return ret;
ret=INF;
for(int j=1;j<=k;j++){
    ret=min(ret,solve(i+j)+abs(arr[i]-arr[i+j]));
}
return ret;
}
int main(){
    IO;
    memset(dp,-1,sizeof(dp));
    memset(arr,INF,sizeof(arr));
    cin>>n>>k;
    for(int i=0;i<n;++i)cin>>arr[i];
    cout<<solve(0);
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vc = vector<char>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using stkll = vector<pll>;
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
#define rep(i, n) for (ll i = 0; i < (n); i++)
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
#ifndef ONLINE_JUDGE
    #define debug(x) cerr << #x << ": " << x << endl;
#else
    #define debug(x)
#endif

struct L {
    int a, b, c;
    L(int a = 0, int b = 0, int c = 0): a(a), b(b), c(c) {}
};

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

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

    int n, m;
    cin >> n >> m;
    map<int, int> mpx, mpy;
    mpx[0] = 0;
    mpy[0] = 0;

    vector<L> lh, lv;
    rep(i,n) {
        int a, b, c;
        cin >> a >> b >> c;
        mpx[a] = 0;
        mpx[b] = 0;
        mpy[c] = 0;
        lh.emplace_back(a, b, c);
    }
    rep(i,m) {
        int a, b, c;
        cin >> c >> a >> b;
        mpy[a] = 0;
        mpy[b] = 0;
        mpx[c] = 0;
        lv.emplace_back(a, b, c);
    }

    vector<int> xs, ys;
    for(auto& p : mpx) {
        p.second = xs.size();
        xs.push_back(p.first);
    }
    for(auto& p : mpy) {
        p.second = ys.size();
        ys.push_back(p.first);
    }

    int w = xs.size() * 2;
    int h = ys.size() * 2;
    vector<vector<int>> d(w, vector<int>(h, 0));
    rep(i,n) {
        int a = mpx[lh[i].a] * 2;
        int b = mpx[lh[i].b] * 2;
        int c = mpy[lh[i].c] * 2;
        for(int x = a; x <= b; x++) d[x][c] = -1;
    }
    rep(i,m) {
        int a = mpy[lv[i].a] * 2;
        int b = mpy[lv[i].b] * 2;
        int c = mpx[lv[i].c] * 2;
        for(int y = a; y <= b; y++) d[c][y] = -1;
    }

    queue<pair<int, int>> q;
    int sx = mpx[0] * 2;
    int sy = mpy[0] * 2;
    d[sx][sy] = 1;
    q.emplace(sx, sy);
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        rep(i,4) {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 0 || nx >= w) continue;
            if(ny < 0 || ny >= h) continue;
            if(d[nx][ny] != 0) continue;
            d[nx][ny] = 1;
            q.emplace(nx, ny);
        }
    }

    ll ans = 0;
    rep(x, w) rep(y, h) {
        if (d[x][y] != 1) continue;
        // 端にたどり着けたらINF
        if (x == 0 || x == w-1 || y == 0 || y == h-1) {
            cout << "INF" << endl;
            return 0;
        }
        // 線分用のマスは幅ゼロ扱い
        if(x % 2 == 0 || y % 2 == 0) continue;

        ll wx = xs[x/2+1] - xs[x/2];
        ll wy = ys[y/2+1] - ys[y/2];
        ans += wx * wy;
    }
    cout << ans << endl;
}


Measured memory_bytes: 144452
import java.util.Scanner;

public class Main
{
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int ans = 1;
		if (n>1) {
				ans = n * (n-1) /2;
		} else {
			ans = 0;
		}

		int ans2 = 1;
		if (m>1) {
			ans2 = m * (m-1) /2;
		} else {
			ans2 = 0;
		}

		sc.close();
		System.out.println(ans+ans2);
	}
}


Measured memory_bytes: 23252
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		long n = in.nextInt();
		int[] R = new int[(int) n];
		Operations op = new Operations();
		
		for (int i = 0; i < n; i++) {
			in.nextLine();
			R[i] = in.nextInt();
		}
		
		System.out.println(op.compute_maxprofitTwo((int) n, R));
		
	}

}

class Operations {
	
	public int compute_maxprofitOne(int n, int[] R) {
		int max_profit = -999999999;
		for (int i = 0; i < n - 1; i++) {
			for(int j =  i + 1; j < n; j++) {
				if(R[j] - R[i] > max_profit) {
					max_profit = R[j] - R[i];
				}
			}
		}
		return max_profit;
	}
	
	public int compute_maxprofitTwo(int n, int[] R) {
		int max_profit = 0;
		int[] p = new int[n];
		
		int min = R[0];
		p[1] = R[1] - R[0];
		
		for (int i = 2; i < n; i++) {
			if (R[i - 1] < min) {
				min = R[i - 1];
			}
			int sell = R[i] - min;
			if (sell > p[i - 1]) {
				p[i] = sell;
			} else {
				p[i] = p[i - 1];
			}
		}
		
		return p[n - 1];
	}
	
}


Measured memory_bytes: 279800
package main

import (
	"fmt"
	"sort"
	"strings"
)

func main() {
	var s, t string
	fmt.Scan(&s, &t)

	s2 := strings.Split(s, "")
	t2 := strings.Split(t, "")

	sort.Strings(s2)
	sort.Sort(sort.Reverse(sort.StringSlice(t2)))

	s = strings.Join(s2, "")
	t = strings.Join(t2, "")

	if s < t {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 640
N = int(input())
A=list(map(int,input().split()))
B=[i for i in A if i%2==0]
x=0
for j in B :
    if (j%3==0) or (j%5)==0:
        x +=1
    else:
        print("DENIED")
        break
if x==len(B):
    print("APPROVED")


Measured memory_bytes: 2940
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#define sqr(x) (x)*(x)
using namespace std;
long long n,m,i,j,sum[2005],dp[2005][2005],mod=1e9+7,ans;
long long qp(long long x,long long y)
{
	if (y==0) return 1;
	if (y==1) return x;
	long long z=qp(x,y/2);
	z=z*z%mod;
	if (y&1) z=z*x%mod;
	return z;
}
int main()
{
	cin>>n>>m;
	if (n==1)
	{
		cout<<1;
		return 0;
	}
	if (m==1)
	{
		cout<<qp(2,n-2);
		return 0;
	}
	dp[0][n+1]=1;
	for (i=1;i<m;i++)
	{
		sum[n+1]=dp[i-1][n+1];
		for (j=n+1;j>=1;j--)
		{
			sum[j]=sum[j+1]+dp[i-1][j];
			sum[j]%=mod;
		}
		for (j=1;j<=n;j++)
		{
			if (i+j-1<=n) dp[i][j]=sum[j];
		}
	}
	for (i=2;i<=n;i++)
	{
		ans=(ans+dp[m-1][i])%mod;
	}
	if (n==m)
	{
		cout<<ans;
		return 0;
	}
	cout<<ans*qp(2,n-m-1)%mod;
	return 0;
}

Measured memory_bytes: 31104
package main

import "fmt"

func main() {
	var a, b, c int
	fmt.Scan(&a, &b, &c)

	s := []int{a+b, b+c, c+a}
	min := s[0]
	for _, i := range s {
		if i < min {
			min = i
		}
	}
	fmt.Println(min)
}

Measured memory_bytes: 512
#include "bits/stdc++.h"
#define ll long long
#define ALL(x) x.begin(),x.end()
#define MOD (1000000000+7)
using namespace std;

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

  char A[55][55]={0};
  char B[55][55]={0};

  ll fl=0;

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

    for(ll i=0;i<M;i++){
    for(ll j=0;j<M;j++){
      cin>>B[i][j];
    }
    }

   ll d = N-M;
   d++;

    for(ll i=0;i<d;i++){
    for(ll j=0;j<d;j++){
      ll gg=0;
      for(ll t=0;t<M;t++){
      for(ll k=0;k<M;k++){
        if(A[i+t][j+k]!=B[t][k]){
          gg++;
         
        }
      }
      }
    if(gg==0){
      fl=1;
      
    }


    }
    }

  if(fl==1){
    cout<<"Yes"<<endl;
  }
  else
  {
    cout<<"No"<<endl;
  }
  

}
  


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  
  int D,T,S;
  double times;
  
  scanf("%d %d %d",&D,&T,&S);
  
  times = (double)D/S;
  
  if(times>T){
    printf("No\n");
  }else{
    printf("Yes\n");
  }
  
  return 0;
}

Measured memory_bytes: 1656
n = int(input())
p = list(map(int, input().split()))
q = list(map(int, input().split()))

import math

lst = [_ for _  in range(1,n+1)]

i = 1
lst = [_ for _  in range(1,n+1)]
for _ in p:
    idx = lst.index(_)
    i += math.factorial(len(lst)) // len(lst) * idx
    lst.remove(_)

pans = i

i = 1
lst = [_ for _  in range(1,n+1)]
for _ in q:
    idx = lst.index(_)
    i += math.factorial(len(lst)) // len(lst) * idx
    lst.remove(_)

qans = i

ans = abs(pans - qans)
print(ans)

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

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

if(a*b>c*d){
cout << a*b <<endl;
} else {
cout << c*d <<endl;
}


  return 0;

  }

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using ll = long long;
long long mod = 1000000000+7;

int main(){

	string s,t;
	cin>>s>>t;

	int ans=0;
	rep(i,s.size()){
		if(s[i]!=t[i])ans++;
	}

	cout<<ans<<endl;

	return 0;
}



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

int main() {
   int a, b, c;
   cin >> a;
   cin >> b;
   cin >> c;
   if (a > b) swap(a, b);
   if (b > c) swap(b, c);
   if (a > b) swap(a, b); 
   cout << a << " " << b << " " << c << endl;
   return 0;
}

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

int max(int a,int b){
  if(a > b) return a;
  else return b;
}
int min(int a, int b){
  if(a < b) return a;
  else return b;
}

int main(){

  int k;
  scanf("%d",&k);

  char s[100];
  scanf("%s",s);
  int len = strlen(s);  

  if(len <= k){
    printf("%s",s);
    return 0;
  }else{
  for(int i=0; i<k; i++){
      printf("%c",s[i]);
    }
  }
  printf("...");



  return 0;
}

Measured memory_bytes: 1732
m, d = map(int,input().split())
count = 0
for i in range(1,m+1):
    for j in range(1,d+1):
        if len(str(j)) == 2:
            d1 = int(str(j)[0])
            d2 = int(str(j)[1])
            if d1 >= 2 and d2 >= 2 and d1*d2 == i:
                count += 1
print(count)



Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>

using namespace std;
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define reppe(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)
#define repme(i,a,b) for(int i = (int)(a) ; i >= (int)(b) ; --i)

typedef long long ll;

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

int main() {
    int N; cin >> N;
    map<pair<char,char>,int> m;
    reppe(i,1,N) {
        char c = to_string(i)[0];
        char d = to_string(i)[to_string(i).size() - 1];
        ++m[make_pair(c,d)];
    }
    ll res = 0;
    for(auto x: m) {
        res += m[x.first] * m[make_pair(x.first.second, x.first.first)];
    }
    cout << res << endl;
}


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

#define mod 1000000007
#define all(x) (x).begin(), (x).end()

const long double PI = acos(-1);
 
ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}

int main(){
    ll n, k, s;
    cin >> n >> k >> s;

    vector<ll> ans(n, 0);
    fill(ans.begin(), ans.begin()+k, s);
    if(s == 1000000000) fill(ans.begin()+k, ans.end(), 1);
    else fill(ans.begin()+k, ans.end(), 1000000000);
    for(ll i = 0; i < n; i++){
        cout << ans[i];
        if(i != n-1) cout << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 2048
#include<bits/stdc++.h>
using namespace std;
 int main()
{
    int a,b,c;
    cin>>a>>b;
    int arr[b];
    for(int i=0;i<b;i++) cin>>arr[i];
    for(int i=a;;i++)
    {
        string str=to_string(i);
        int n=0;
        for(int j=0;j<str.size();j++)
        {
            int f=0;
            int t=str[j]-'0';
            for(int k=0;k<b;k++){
            if(arr[k]==t)
            {
                f=1;
                break;
            }
            }
            if(f==1)
            {
                n=1;
                break;
            }
        }
        if(n==1)
        {
            continue;
        }
        else
        {
            c=i;
            break;
        }

    }
    cout << c << endl;
    return 0;
}


Measured memory_bytes: 256
N, A, B = map(int, input().split(' '))
x_list = list(map(int, input().split(' ')))
ex = 0
for i in range(1, len(x_list)):
    if (x_list[i] - x_list[i-1]) * A >= B:
        ex += B
    else:
        ex += (x_list[i] - x_list[i-1]) * A
print(ex)

Measured memory_bytes: 14228
from math import factorial

s=input().split()
N=int(s[0])
M=int(s[1])

if(M<N+2 and N<M+2):
    number=int(factorial(N)*factorial(M))

    if(N==M):number=number*2

    number = number % (10**9 +7)
    print(number)
else:
    print(0)



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

if N % 2 == 0:
    middle = N // 2
    if A[middle-1] == A[middle]:
        print("0")
    else:
        print(str(A[middle]-A[middle-1]))
else:
    print("0")

Measured memory_bytes: 52680