akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define vl vector<ll>

int main() {

    int N, M;
    cin >> N >> M;

    vector<int> S, C;
    int s, c;

    int st, ed;
    if (N == 1) {
        st = 0;
        ed = 10;
    }
    else if(N == 2) {
        st = 10;
        ed = 100;
    }
    else {
        st = 100;
        ed = 1000;
    }

    for (int i = 0; i < M; ++i) {
        cin >> s >> c;
        S.push_back(s);
        C.push_back(c);
    }


    int ans = -1;
    bool ok;
    for (int i = st; i < ed; ++i) {
        ok = true;
        for (int m = 0; m < M; ++m) {
            if (N == 3 && S[m] == 1) {
                if (i / 100 != C[m]) ok = false;
            }
            else if (N == 3 && S[m] == 2) {
                if ((i % 100) / 10 != C[m]) ok = false;
            }
            else if (N == 3 && S[m] == 3) {
                if (i % 10 != C[m]) ok = false;
            }
            else if (N == 2 && S[m] == 1) {
                if (i / 10 != C[m]) ok = false;
            }
            else if (N == 2 && S[m] == 2) {
                if (i % 10 != C[m]) ok = false;
            }
            else {
                if (i % 10 != C[m]) ok = false;
            }
        }
        if (ok) {
            ans = i;
            break;
        }
    }

    cout  << ans << endl;

    return 0;
}


Measured memory_bytes: 256
n, m = map(int,input().split())

a = []
for _ in range(m):
  a.append(list(map(int,input().split())))
a.sort()

bridge = n
ans = 0
for i in range(m):
    count = True
    if a[m - i - 1][1] > bridge:
        count = False
            
    if count:
        ans += 1
        bridge = a[m - i - 1][0]

print(ans)

Measured memory_bytes: 27888
N, Y = map(int, input().split())

for i in range(N + 1):
  for j in range(N - i + 1):
    if((Y - 10000 * i - 5000 * j) / 1000 == N - i - j):
      print(i, j, N - i - j)
      exit()

print("-1 -1 -1")

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int n;
ll k;
ll a[52][52];
ll r[52][52];

ll tmp[52][52];
void mul(ll a[52][52], ll b[52][52]){
  REP(i,n)REP(j,n)tmp[i][j] = 0;
  REP(k,n)REP(i,n)REP(j,n)(tmp[i][j] += a[i][k]*b[k][j]) %= MOD;
  REP(i,n)REP(j,n)a[i][j] = tmp[i][j];
}

int main(){
  scanf("%d%lld",&n,&k);
  REP(i,n)REP(j,n)scanf("%lld",&a[i][j]);
  REP(i,n)r[i][i] = 1;
  while(k){
    if(k&1)mul(r,a);
    mul(a,a);
    k >>= 1;
  }
  ll ans = 0;
  REP(i,n)REP(j,n)(ans += r[i][j]) %= MOD;
  printf("%lld\n",ans);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <map>

using namespace std;

#define loop(i,a,b) for(int i=(a); i<(b); i++)
#define rep(i,b) loop(i,0,b)

int main(){
    int M = 1100*1000;
    bool isp[M];
    rep(i,M) isp[i] = true;
    isp[0] = isp[1] = false;
    for(int i=2;i*i<M;i++){
        if(!isp[i]) continue;
        for(int j=i*i; j<M;j+=i) isp[j] = false;
    }
    int a,d,n;
    while(cin >> a >> d >> n && a){
        int c = 0;
        int ans = -1;
        for(int i=a;i<M;i+=d){
            if(isp[i]){
                c++;
                if(c == n){
                    ans = i;
                    break;
                }
            }
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 2232
#include<map>
#include<iostream>
#include<deque>
#include<algorithm>
#include<string>
#include<cctype>
#include<iomanip>
#include<vector>
#include<queue>
 
using namespace std;
#define REP(i,b,e) for(int i=(int)b;i<(int)e;i++)
#define rep0(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n+1)
 
#define shosu setprecision(10)
 
typedef long long ll;
ll longinf=1ll<<60;
int inf=1<<29;

int N;

int main(){
    cin>>N;
    int cnt=0;
    rep1(i,N){
        int cnt1=0;
        rep1(j,i){
            if(i%j==0) cnt1++;
        }
        if(i%2==1&&cnt1==8) cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

class Main {

	public static void main(String[] args) throws Exception {
		final Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		solve(N);
	}

	static void solve(int n) {
		int a = 1, b = 1;
		int ca = 0, cb = 0;
		while (a < n) {
			a *= 6;
			ca++;
		}
		while (b < n) {
			b *= 9;
			cb++;
		}

		int[][] dp = new int[1 + ca + cb + 1][n + 1];
		for (int i = 0; i < n + 1; i++) {
			dp[0][i] = i;
		}

		a = 6;
		for (int i = 1; i <= ca; i++) {
			for (int j = 0; j < n + 1; j++) {
				dp[i][j] = dp[i - 1][j];
				if (j >= a) {
					dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - a] + 1);
					dp[i][j] = Math.min(dp[i][j], dp[i][j - a] + 1);
				}
			}
			a *= 6;
		}

		b = 9;
		for (int i = ca + 1; i < dp.length; i++) {
			for (int j = 0; j < n + 1; j++) {
				dp[i][j] = dp[i - 1][j];
				if (j >= b) {
					dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - b] + 1);
					dp[i][j] = Math.min(dp[i][j], dp[i][j - b] + 1);
				}
			}
			b *= 9;
		}

		System.out.println(dp[dp.length - 1][n]);
	}
}


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

int main()
{
    long long int n, m, sum=0;
    cin>>n>>m;
    int a[n];
    for(int i=0; i<n; i++) cin>>a[i];
    sort(a, a+n);
    for(int i=0; i<m; i++) sum+=a[i];
    cout<<sum;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
#define int long long
using namespace std;

template <typename X, typename T>
auto vectors(X x, T a) {
	return vector<T>(x, a);
}

template <typename X, typename Y, typename Z, typename... Zs>
auto vectors(X x, Y y, Z z, Zs... zs) {
	auto cont = vectors(y, z, zs...);
	return vector<decltype(cont)>(x, cont);
}

template<typename T>
ostream& operator << (ostream& os, vector<T>& v){
	rep(i,v.size()){ os << v[i] << (i == v.size() - 1 ? "" : " "); } return os;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& v){
	for(T& x: v){ is >> x; } return is;
}

signed main(){
	int c, n, m;
	while(cin >> c >> n >> m){
		vector<int> dp(c + 1, 0);

		rep(i,n){
			int s, p;
			cin >> s >> p;
			for(int j = c; j >= 0; j--){
				if(j + s >= dp.size()) continue;
				dp[j + s] = max(dp[j + s], dp[j] + p);
			}
		}

		range(i,1,m + 1){
			cout << dp[c / i] * i << endl;
		}
	}
}



Measured memory_bytes: 3208
#include <iostream>
using namespace std;int main(){int n,k,s,i,j;cin>>n>>k;if(k>(n-1)*(n-2)/2)cout<<-1;else{s=n*(n-1)/2-k;cout<<s<<endl;for(i=1;i<n&&s;i++)for(j=i+1;j<=n&&s;j++,s--)cout<<i<<" "<<j<<endl;}}

Measured memory_bytes: 256
off = [[[0 for _ in range(10)] for _ in range(3)] for _ in range(4)]
n = int(input())

for _ in range(n):
    b,f,r,v = map(int,input().split())
    off[b-1][f-1][r-1] += v

for i in range(4):
    for j in range(3):
        print(' '+' '.join(map(str,off[i][j])))
    if i != 3:
        print('#'*20)



Measured memory_bytes: 5612
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#define INF 2147483647
#define llINF 9223372036854775807
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long

using namespace std;
int main(){
  int n,m;
  cin>>n>>m;
  ll ans=0;
  ll x[n+10]={};
  ll dp[n+10][n+10][50*n+10]={};
  ll sum=0;
  dp[0][0][0]=1;
  for(int i=0;i<n;i++)
    cin>>x[i];
  for(int i=1;i<=n;i++){
    for(int j=0;j<=n;j++){
      for(int k=0;k<=50*n;k++){
	if(i>=1&&j>=1&&k>=x[i-1])
	  dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-x[i-1]];
	else if(i>=1&&k<x[i-1]){
	  dp[i][j][k]=dp[i-1][j][k];
	}else
	  dp[i][j][k]=0;
      }
    }
  }
  for(int i=1;i<=n;i++){
    ans+=dp[n][i][i*m];
  }
  cout<<ans<<endl;
  return 0;
}


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

using namespace std;

int imos[30][100002] = {};

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

    for (int i = 0; i < N; i++) {
        int s, t, c;
        cin >> s >> t >> c;
        c--;
        imos[c][s]++;
        imos[c][t]--;
    }

    int ans = 0;
    for (int i = 1; i < 100001; i++) {
        int cnt = 0;
        for (int j = 0; j < C; j++) {
            imos[j][i] += imos[j][i - 1];
            if (imos[j][i] > 0 or imos[j][i - 1] > 0) cnt++;
        }
        ans = max(ans, cnt);
    }

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


Measured memory_bytes: 11904
# Paper
class Paper
  def initialize(x, y)
    @x, @y, @grids = x, y, Array.new(x) { Array.new(y, 0) }
  end

  def dye(x, y, size)
    case size
    when 1
      dense(x, y)
      dense(x, y - 1)
      dense(x + 1, y)
      dense(x, y + 1)
      dense(x - 1, y)
    when 2
      dense(x, y)
      dense(x, y - 1)
      dense(x + 1, y - 1)
      dense(x + 1, y)
      dense(x + 1, y + 1)
      dense(x, y + 1)
      dense(x - 1, y + 1)
      dense(x - 1, y)
      dense(x - 1, y - 1)
    when 3
      dense(x, y)
      dense(x, y - 1)
      dense(x + 1, y - 1)
      dense(x + 1, y)
      dense(x + 1, y + 1)
      dense(x, y + 1)
      dense(x - 1, y + 1)
      dense(x - 1, y)
      dense(x - 1, y - 1)
      dense(x, y - 2)
      dense(x + 2, y)
      dense(x, y + 2)
      dense(x - 2, y)
    end
  end

  def graph
    @grids.transpose.each do |row|
      puts row.join(' ')
    end
  end

  def dense(x, y, density = 1)
    @grids[x][y] += density if exists?(x, y)
  end

  def exists?(x, y)
    0 <= x && x <= @x - 1 && 0 <= y && y <= @y - 1
  end

  def max_density
    @grids.flatten.max
  end

  def while_grids_sum
    @grids.flatten.select { |x| x == 0 }.size
  end
end

paper = Paper.new(10, 10)

while line = gets
  x, y, size = line.chomp.split(',').map(&:to_i)
  paper.dye(x, y, size)
end

puts paper.while_grids_sum
puts paper.max_density

Measured memory_bytes: 8668
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <climits>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <functional>
#include <set>
#include <numeric>
#include <stack>
#include <utility>
#include <time.h>
#include <iterator>
//#include "util.h"
 
using namespace std;
typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vint;
typedef vector<ll> vll;
 
//呪文
template <typename _KTy, typename _Ty> ostream& operator << (ostream& ostr, const pair<_KTy, _Ty>& m) { cout << "{" << m.first << ", " << m.second << "}"; return ostr; }
template <typename _KTy, typename _Ty> ostream& operator << (ostream& ostr, const map<_KTy, _Ty>& m) { if (m.empty()) { cout << "{ }"; return ostr; } cout << "{" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { cout << ", " << *itr; } cout << "}"; return ostr; }
template <typename _Ty> ostream& operator << (ostream& ostr, const vector<_Ty>& v) { if (v.empty()) { cout << "{ }"; return ostr; }	cout << "{" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) { cout << ", " << *itr; }	cout << "}"; return ostr; }
template <typename _Ty> ostream& operator << (ostream& ostr, const set<_Ty>& s) { if (s.empty()) { cout << "{ }"; return ostr; } cout << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { cout << ", " << *itr; }	cout << "}"; return ostr; }
#define PI 3.14159265358979323846
#define EPS 1e-8
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define all(x) (x).begin(), (x).end()
	
 
 
int main() {
	ll X, t;
	cin >> X >> t;
	cout << (X < t ? 0 : X - t) << endl;
 
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dump(...)
#endif
#define endl "\n"
#define ll long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define RREP(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (int i = ((int)(x)); i > 0; i--)
#define INF (1 << 30)
#define LLINF (1LL << 60)
#define vi vector<int>
#define vvi vector<vector<int>>
#define pi pair<int, int>
#define ALL(a) (a).begin(), (a).end()
#define BIT(n) (1LL << (n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) //sortしてからつかうこと
constexpr ll mod = 1e9 + 7;
int dx[8] = { 1, 0, -1, 0, 1, 1, -1, -1 };
int dy[8] = { 0, 1, 0, -1, 1, -1, 1, -1 };
ll A, B, C, D, E, F, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;
ll ans = 0;

template <typename T>
istream& operator>>(istream& is, vector<T>& vec) {
	for (T& x : vec)
		is >> x;
	return is;
}

template<ll mod>
class Fp {
public:
	ll val;

private:
	inline void calc_mod(ll& v) {
		if (v >= mod)v -= mod;
	}
public:
	Fp() {}
	Fp(ll v) :val(v% mod) {
		if (val < 0)val += mod;
	}

	Fp operator+=(const Fp& in) {
		val += in.val;
		calc_mod(val);
		return *this;
	}

	Fp operator+(const Fp& in) const {
		return Fp(*this) += in;
	}

	Fp& operator-=(const Fp& in) {
		val -= in.val;
		calc_mod(val);
		if (val < 0)val += mod;
		return *this;
	}

	Fp operator-(const Fp& in) const {
		return Fp(*this) -= in;
	}

	Fp& operator*=(const Fp& in) {
		val = val * in.val % mod;
		return *this;
	}

	Fp operator*(const Fp& in) const {
		return Fp(*this) *= in;
	}

	Fp& operator/=(const Fp& in) {
		*this *= modpow(in, mod - 2);
		return *this;
	}

	Fp operator/(const Fp& in) const {
		return Fp(*this) /= in;
	}

	bool operator==(const Fp& in)const {
		return val == in.val;
	}

	bool operator!=(const Fp& in)const {
		return val != in.val;
	}

	friend Fp modpow(const Fp& in, ll n) {
		if (n == 0)return 1;
		if (n & 1) {
			return in * modpow(in * in, n / 2);
		}
		else {
			return modpow(in * in, n / 2);
		}
	}
};
using modll = Fp<mod>;

class Factorial {
public:
	vector<modll> fact, finv;
	Factorial(ll n) :fact(n + 1, modll(1)), finv(n + 1, modll(1)) {
		for (int i = 2; i <= n; i++) {
			modll tmp(i);
			fact[i] = fact[i - 1] * tmp;
			finv[i] = finv[i - 1] / tmp;
		}
	}

	modll com(const ll& n, const ll& k) {
		if (n < k || n < 0 || k < 0)return modll(0);
		return fact[n] * finv[k] * finv[n - k];
	}
};


signed main() {
	cin >> X >> Y;
	if ((Y + X) % 3 == 0) {
		int n = (Y + X) / 3;
		int x = n;
		int r = X - x;
		if (r<0 || r>n) {
			cout << 0 << endl;
			return 0;
		}
		else {
			Factorial f(n);
			cout << f.com(n, r).val << endl;
			return 0;
		}
	}
	else {
		cout << 0 << endl;
		return 0;
	}
}


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

ll solve() {
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N), a0, a1, a2;
    for ( int i = 0; i < N; i++ ) {
        cin >> A[i];
        if ( A[i] > 0 ) a1.push_back(A[i]);
        else if ( A[i] < 0 ) a2.push_back(-A[i]);
        else a0.push_back(A[i]);
    }
    sort(A.begin(), A.end());
    sort(a1.begin(), a1.end());
    sort(a2.begin(), a2.end());

    // auto check = [&](ll x) {
    //     ll c = 0;
    //     for ( int i = 0; i < N; i++ ) {
    //         if ( A[i] > 0 ) {
    //             auto p = upper_bound(A.begin(), A.end(), x / A[i]);
    //             c += p - A.begin();
    //             if ( A[i] * *p <= x ) c -= 1;
    //         } else if ( A[i] == 0 ) {
    //             if ( x >= 0 ) c += N - 1;
    //         } else {
    //             auto p = lower_bound(A.begin(), A.end(), x / (-A[i]));
    //             c += A.end() - p;
    //             if ( A[i] * *p >= x ) c -= 1;
    //         }
    //         cout << A[i] << " "  << c << "\n";
    //     }
    //     return c <= 2 * K;
    // };
    auto count_prod1 = [](vector<ll>& v, ll x) {
        ll c = 0;
        int j = v.size()-1;
        for ( int i = 0; i < v.size(); i++ ) {
            while ( j > i && v[i] * v[j] >= x ) j--;
            if ( j > i ) c += j - i;
        }
        return c;
    };
    auto count_prod2 = [](vector<ll>& v1, vector<ll>& v2, ll x) {
        ll c = 0;
        int j = v2.size()-1;
        for ( int i = 0; i < v1.size(); i++ ) {
            while ( j >= 0 && v1[i] * v2[j] > x ) j--;
            c += v2.size()-1 - j;
        }
        return c;
    };

    auto check = [&](ll x) {
        ll c = 0;
        if ( x > 0 ) {
            c += a1.size() * a2.size();
            c += (a1.size() + a2.size()) * a0.size();
            c += a0.size() * (a0.size()-1) / 2;
            c += count_prod1(a1, x);
            c += count_prod1(a2, x);
        } else if ( x == 0 ) {
            c += a1.size() * a2.size();
        } else {
            c += count_prod2(a1, a2, -x);
        }
        return c < K;
    };

    ll l = -1e18+1, r = 1e18+1;
    //ll l = 0, r = 10;
    while ( r - l > 1 ) {
        ll m = ( l + r )/2;
        if ( check(m) ) l = m;
        else r = m;
    }
    return l;
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 4084
<?php
  
$n = trim(fgets(STDIN));

$a=[];
for($i=1; $i<=$n; $i++){
  $a[$i] = trim(fgets(STDIN)); 
}

$count = 0;
$l = 1;
$j = 1;
while ($j<=$n){
  $l = $a[$l];
  $count++;
  if ($l == 2) break;
  $j++;
}

echo $j==$n+1 ? -1 : $count;

?>

Measured memory_bytes: 12792
#include <iostream>

using namespace std;

int main()
{
    char a,b,c,w,r,e;
    cin >> a >> b >> c;
    cin >> w >> r >> e;
    if(e==a && w==c && r==b)
    {
        cout << "YES";
    }
    else
        cout << "NO";
        return 0;
}


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

int main(){
    int H,W,N;cin>>H>>W>>N;
    int a[N];
    for(int i=0;i<N;i++)cin>>a[i];
    int ans[H][W];
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++)ans[i][j]=0;
    }
    int p=0,q=0;
    for(int i=0;i<N;i++){
        for(int j=0;j<a[i];j++){
            ans[p][q]=i+1;
            if(p%2){
                if(q)q--;
                else p++;
            }
            else{
                if(q!=W-1)q++;
                else p++;
            }
        }
    }
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(j)cout<<" ";
            cout<<ans[i][j];
        }
        cout<<endl;
    }
    return 0;
}

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

#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define RFOR(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define LL long long
#define INF INT_MAX

const double EPS = 1e-14;
const double PI  = acos(-1.0);


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

  int ans = INF;
  REP (i, s.size() - 2) {
    string t = s.substr(i, 3);
    ans = min(ans, abs(753 - stoi(t)));
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<climits>
#include<cstdlib>
#include<map>
#include<math.h>
#include<utility>
#include<vector>
using namespace std ;
typedef long long ll;

// N K
// A_1, ..., A_N
int main(){
  int AB, BC, CA ;
  cin >> AB >> BC >> CA ;

  int s = (AB+BC+CA)/2 ;

  cout << sqrt(s*(s-AB)*(s-BC)*(s-CA)) << endl ;
}

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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define mp(a,b) make_pair((a),(b))
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define dump(x)
#endif

typedef long long int ll;
typedef pair<int,int> pii;
//template<typename T> using vec=std::vector<T>;

const int INF=1<<30;
const long long int INF_=1LL<<58;
const double EPS=1e-9;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
	os << "[";
	for (const auto &v : vec) {
		os << v << ",";
	}
	os << "]";
	return os;
}

void Solve(){
	int h,w,b[1000][1000];
	cin >> h >> w;
	rep(i,0,h) rep(j,0,w) cin >> b[i][j];

	int cnt[1000][1000]={};
	rep(i,0,h){
		rep(j,0,w){
			if(!b[i][j]){
				rep(k,0,w) if(k!=j) ++cnt[i][k];
				rep(k,0,h) if(k!=i) ++cnt[k][j];
				++cnt[i][j];
			}
		}
	}

	rep(i,0,h){
		rep(j,0,w){
			cout << cnt[i][j]%2;
			if(j==w-1) cout << endl;
			else cout << ' ';
		}
	}
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	Solve();
	return 0;
}

Measured memory_bytes: 9016
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<map>
#include<set>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using TP = tuple<ll,ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(18);
}
signed main(){
  init_io();
  string t;
  cin >> t;
  for(auto c:t){
    if(c=='?') c = 'D';
    cout << c;
  }
  cout << endl;
}


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

// input
int N, M;
vector<int> A, B;


void input() {
    cin >> N >> M;
    A = B = vector<int>(M);
    rep(i, M) cin >> A[i] >> B[i];
}


struct UnionFind {
    vector<int> par;
    map<int, int> groups;

    UnionFind(int n) : par(n) {
        rep(i, n) par[i] = i;
        rep(i, n) groups[i] = 1;
    }

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

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return;
        if (groups[rx] < groups[ry]) swap(rx, ry);
        groups[rx] += groups[ry];
        groups.erase(ry);
        par[ry] = rx;
    }

    bool same(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};


int main() {
    input();
    UnionFind uf(N);
    rep(i, M) uf.unite(A[i] - 1, B[i] - 1);
    int ans = uf.groups.size() - 1;
    cout << ans << endl;
}


Measured memory_bytes: 9068
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>

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 RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define FIND(s, e) ((s).find(e) != (s).end())
#define EB emplace_back

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

void solve(int N, int M, int P) {
    VI X(N);
    REP(i, N) cin >> X[i];
    if (X[M - 1] == 0) {
        cout << 0 << endl;
        return;
    }
    cout << (accumulate(ALL(X), 0) * (100 - P)) / X[M - 1] << endl;
}

signed main(void) {
    int n, m, p;
    while (cin >> n >> m >> p) {
        if (n == 0 && m == 0 && p == 0) return 0;
        solve(n, m, p);
    }
}

Measured memory_bytes: 3116
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>

int main() {
  unsigned int a, b, q;
  std::cin >> a >> b >> q;

  std::vector<long> s_array(a);
  for (size_t i = 0; i < a; ++i) {
    std::cin >> s_array.at(i);
  }
  std::vector<long> t_array(b);
  for (size_t i = 0; i < b; ++i) {
    std::cin >> t_array.at(i);
  }
  std::vector<long> x_array(q);
  for (size_t i = 0; i < q; ++i) {
    std::cin >> x_array.at(i);
  }
  s_array.insert(s_array.begin(), -1 * 1e+10);
  t_array.insert(t_array.begin(), -1 * 1e+10);
  s_array.push_back(2 * 1e+10);
  t_array.push_back(2 * 1e+10);

  // for (size_t i = 0; i < s_array.size(); ++i) {
  //   std::cout << s_array.at(i) << " ";
  // }
  // std::cout << std::endl;

  // for (size_t i = 0; i < t_array.size(); ++i) {
  //   std::cout << t_array.at(i) << " ";
  // }
  // std::cout << std::endl;

  // for (size_t i = 0; i < x_array.size(); ++i) {
  //   std::cout << x_array.at(i) << " ";
  // }
  // std::cout << std::endl;
  // std::cout << "" << std::endl;

  for (const long& x : x_array) {
    std::vector<long>::const_iterator s_east_itr = std::lower_bound(s_array.begin(), s_array.end(), x);
    const long s_east = *s_east_itr;
    const long s_west = *(s_east_itr - 1);
    std::vector<long>::const_iterator t_east_itr = std::lower_bound(t_array.begin(), t_array.end(), x);
    const long t_east = *t_east_itr;
    const long t_west = *(t_east_itr - 1);

    std::vector<long> ans_array;
    for (const long& s : {s_east, s_west}) {
      for (const long& t : {t_east, t_west}) {
        const long cand_1 = std::abs(s - x) + std::abs(t - s);
        const long cand_2 = std::abs(t - x) + std::abs(s - t);
        ans_array.push_back(std::min(cand_1, cand_2));
      }
    }
    std::cout << *std::min_element(std::begin(ans_array), std::end(ans_array)) << std::endl;
  }

  return 0;
}


Measured memory_bytes: 3680
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sc(n) scanf("%d",&n)
#define scl(n) scanf("%lld",&n)
#define pr(n) printf("%d",n)
#define prl(n) printf("%lld",n)
#define nl printf("\n")
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
int main()
{
	int i,a,b,c,k;
	cin>>a>>b>>c>>k;
	int m = max(a,max(b,c));
	if(m == a)
		cout<<(b+c+pow(2,k)*a)<<endl;
	else if(m == b)
		cout<<(a+c+pow(2,k)*b)<<endl;
	else if(m == c)
		cout<<(b+a+pow(2,k)*c)<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct ios_accelerate { ios_accelerate() { ios::sync_with_stdio(false); cin.tie(nullptr); } } CALL;

#define REP(i, n) for(auto (i) = (n)*0; (i) < (n); (i)++)
#define RNG(i, a, b) for(auto (i) = (a); (i) < (b); (i)++)
#define RBF(i, v) for(auto& (i) : (v))
#define ALL(x) (x).begin(), (x).end()

using LL = long long;
using UL = unsigned long;
using ULL = unsigned long long;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
template<typename T> using P = pair<T, T>;

const double PI = 3.141592653589793;
const int MOD = 1000000007;
const LL INF64 = static_cast<LL>(1e18) + 2;
const int INF = static_cast<int>(1e9) + 2;

template<typename T> inline void upsort(vector<T>& x) { sort(x.begin(), x.end()); }
template<typename T> inline void downsort(vector<T>& x) { sort(x.begin(), x.end(), greater<T>()); }
template<typename T> inline void col(T x) { cout << x << '\n'; }
template<> inline void col(double x) { cout << fixed << setprecision(12) << x << '\n'; }

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

	VV<int> cnt(10, V<int>(10, 0));
	int keta = 1, keta2 = 10;
	RNG(i, 1, n + 1) {
		if (i >= keta2) {
			keta *= 10;
			keta2 *= 10;
		}
		int last = i % 10;
		int top = i / keta;
		cnt[top][last]++;
	}

	LL ans = 0;
	keta = 1, keta2 = 10;
	RNG(i, 1, n + 1) {
		if (i >= keta2) {
			keta *= 10;
			keta2 *= 10;
		}
		int last = i % 10;
		int top = i / keta;
		ans += cnt[last][top];
	}

	col(ans);
	return 0;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define rep(i,n) for(ll i = 0; i < (ll)(n); i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF = 1LL << 60;
set<int> se[26];

// inline int c2i(char c){
//     return (int)(c-'a');
// }
int main(){
    int n;
    string s;
    int q;
    cin >> n >> s >> q;
    //vector<set<int>> se(26);
    rep(i,n){
        se[s[i]-'a'].insert(i);
    }
    
    
    rep(qi,q){
        int a;
        cin >> a;
        if(a==1){
            int i;
            char c;
            cin >> i >> c;
            i--;
            //cout << i << c << endl;    
            se[s[i]-'a'].erase(i);
            s[i] = c;
            se[c-'a'].insert(i);
        }else{
            int l,r;
            cin >> l >> r;
            l--; r--;
            int ans = 0;
            rep(i,26){
                //auto tmp = lower_bound(se[i].begin(),se[i].end(),l);
                auto tmp = se[i].lower_bound(l);
                if(tmp == se[i].end())continue;
                if(*tmp<=r) ans++;
                //if(tmp != se[i].end() && *tmp<=r) ans++;
            }
            cout << ans << endl;
            //cout << "aaaaa" << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 24196
from collections import deque

n, q = map(int,input().split())
g = [[] for _ in range(n)] # グラフを格納
count = [0 for _ in range(n)]

for _ in range(n-1):
    a, b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1) # どちらが根かわからない

for _ in range(q):
    p, x = map(int, input().split())
    count[p-1] += x

que = deque()
que.append(0)

watch = [False] * n
watch[0] = True

while que:
    i = que.popleft()
    watch[i] = True
    for e in g[i]:
        if watch[e] == True: continue
        count[e] += count[i]
        que.append(e)

print(" ".join(map(str, count)))


Measured memory_bytes: 132216
#include<stdio.h>
int main()
{
	int n,h[100000];
	int i,j,cnt,x=0;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&h[i]);
	}
	cnt=0;
	for(i=0;i<n-1;i++){
		if(h[i]>=h[i+1]){
			cnt++;
			if(x<=cnt){
				x=cnt;
			}
		}
		else{
			cnt=0;
		}
	}
	printf("%d\n",x);
	return 0;
}


Measured memory_bytes: 2124
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int PREP = (cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(9), 0);
//int SEGV = getenv("D") || (exit(system("D= SEGFAULT_SIGNALS=all catchsegv ./prog.exe") >> 8), 0);
int main() {
    int N; cin >> N;
    vector<int> A(N); for (auto &a : A) cin >> a, a--;
    map<int, int> M;
    for (auto a : A) M[a]++;
    if (N == 2) {
        cout << -1 << '\n';
        return 0;
    }
    set<int> S;
    for (int i = 0; i < N; i++) S.insert(i);
    vector<int> ans;
    int ban = -1;
    for (int i = 0; i < N; i++) {
        int rest = N - i;
        int choice = -1;
        for (auto item : S) {
            if (item == ban) {
                continue;
            }
            if (M[A[item]] == rest - 1 && S.count(A[item])) {
                choice = A[item];
                goto DONE;
            }
            choice = item;
            break;
        }
        if (rest == 3) {
            vector<int> B(begin(S), end(S));
            for (int i = 0; i < 3; i++) {
                int j = (i + 1) % 3;
                if (B[i] == A[B[j]] && B[j] == A[B[i]]) {
                    if (B[i] > B[j]) swap(B[i], B[j]);
                    choice = (B[i] != ban ? B[i] : B[j]);
                    break;
                }
            }
        }
        DONE:;
        ans.push_back(choice);
        S.erase(choice);
        ban = A[choice];
        M[A[choice]]--;
    }
    for (int i = 0; i < N; i++) {
        cout << ans[i] + 1 << " \n"[i == N - 1];
    }
    return 0;
}


Measured memory_bytes: 10624
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/rope>
#define pb push_back
#define F first
#define S second
#define ins insert
#define mp make_pair
#define fo(i, n1, n, x) for(int i = n1; i <= n; i += x)
#define foo(i, n, n1, x) for(int i = n; i >= n1; i -= x)
#define bit __builtin_popcount
#define md (l + ((r - l) / 2))
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define ub upper_bound
#define lb lower_bound
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)

using namespace std;
//using namespace __gnu_pbds;
//using namespace __gnu_cxx;


using ll = long long;

//#define int ll

using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;



const int N = 2e5 + 11, mod = 1e9 + 7, mod2 = 998244353;
const int MAX = 1e5 + 11;
const int INF1 = 2e9 + 11;
const ll INF2 = 6e18 + 11;
const double INF3 = 1e8 + 11;
const int base = 500;
const int P = 31;
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
const int dy[] = {0, 0, 1, -1, 1, -1, 1, -1};
const double EPS = 1e-4;
const double PI = acos(-1.0);


//template<typename T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
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; }


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, m, q, a[55], b[55], c[55], d[55];
main() {
  file("threesum");
  ios;
  cin >> n >> m >> q;
  fo(i, 1, q, 1) cin >> a[i] >> b[i] >> c[i] >> d[i];
  int ans = 0;
  function<void(int, vi)> rec = [&](int x, vi v) {
    if (x == n + 1) {
      int res = 0;
      fo(i, 1, q, 1) {
        if (v[b[i] - 1] - v[a[i] - 1] == c[i]) res += d[i];
      }
      chmax(ans, res);
      return;
    }
    int last = 1;
    if (!v.empty()) last = v.back();
    fo(i, last, m, 1) {
      v.eb(i);
      rec(x + 1, v);
      v.pop_back();
    }
  };
  vi v;
  rec(1, v);
  cout << ans;
  return 0;
}
/**

*/


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


signed main() {
    int N;
    string S;
    cin >> N >> S;

    int dp[N+1][N+1]{};
    int ans = 0;

    rep(i,N){
        rep(j,N){
            if(S[i] == S[j]){
                dp[i+1][j+1] = dp[i][j] + 1;
                dp[i+1][j+1] = min(dp[i+1][j+1], abs(j-i));
                ans = max(ans, dp[i+1][j+1]);
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 195712
import java.util.Scanner;

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

		int n = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();

		System.out.println(Math.min(a, b) + " " + ((a + b > n) ? a + b - n : 0));

		sc.close();
	}
}



Measured memory_bytes: 22224
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<pair<int, int>> r(n), b(n);
    for(auto&& i : r){
        cin >> i.first >> i.second;
    }
    for(auto&& i : b){
        cin >> i.first >> i.second;
    }
    sort(begin(r), end(r));
    sort(begin(b), end(b));
    int ans = 0;
    for(auto&& i : b){
        bool check = false;
        int p;
        for(int j = 0; j < n && r[j] < i; j++){
            if(r[j].second < i.second){
                if(!check){
                    check = true;
                    p = j;
                }else if(r[p].second < r[j].second){
                    p = j;
                }
            }
        }
        if(check){
            ans++;
            r[p].second = 2 * n;
        }
    }
    cout << ans << "\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <deque>
#include <string.h>
#include <math.h>
typedef long long ll;
#define INF			100000
#define MAX(x, y)	(((x) > (y))? (x) : (y))
#define MIN(x, y)	(((x) < (y))? (x) : (y))
#define ABS(x)		(((x) < 0)? (-1*(x)) : (x))
#define REP(i,x,y)	for (int (i)=(x);(i)<(y);(i)++)
#define REP_(i,x,y)	for ((i)=(x);(i)<(y);(i)++)
#define MEMCLR(X)	memset((X),0,sizeof((X)))

using namespace std;
typedef pair<int, int> Point;
typedef vector<vector<Point>> Graph;

int K;
int d[INF];
deque<int> q;

int main() {
	
	cin >> K;
	
	REP(i,0,K) d[i] = INF;
	d[1] = 1;
	q.push_back(1);
	
	while ( !q.empty() ) {
		int x = q.front();q.pop_front();
		int a = (x+1) % K, b = (10*x) % K;
		int aa = d[x]+1, bb = d[x];
		
		if ( aa < d[a] ) d[a] = aa, q.push_back(a);
		if ( bb < d[b] ) d[b] = bb, q.push_back(b);
	}

	cout << d[0];

	return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

vector<int> fact;
vector<int> ifact;
vector<int> inv;
vector<int> pow2;
const int MOD = 998244353;
int add(int a, int b)
{
	a+=b;
	while(a>=MOD) a-=MOD;
	return a;
}
void radd(int &a, int b)
{
	a=add(a,b); 
}
int mult(int a, int b)
{
	return (a*1LL*b)%MOD;
}
void rmult(int &a, int b)
{
	a=mult(a,b);
}
int modpow(int a, int b)
{
	int r=1;
	while(b)
	{
		if(b&1) r=mult(r,a);
		a=mult(a,a);
		b>>=1;
	}
	return r;
}
int choose(int a, int b)
{
	if(a<b) return 0;
	if(b==0) return 1;
	if(a==b) return 1;
	return mult(fact[a],mult(ifact[b],ifact[a-b]));
}
int inverse(int a)
{
	return modpow(a,MOD-2);
}
void init(int _n)
{
	fact.clear(); ifact.clear(); inv.clear(); pow2.clear();
	fact.resize(_n+1);
	ifact.resize(_n+1);
	inv.resize(_n+1);
	pow2.resize(_n+1);
	pow2[0]=1;
	ifact[0]=1;
	fact[0]=1;
	for(int i=1;i<=_n;i++)
	{
		pow2[i]=add(pow2[i-1],pow2[i-1]);
		fact[i]=mult(fact[i-1],i);
		//ifact[i]=mult(ifact[i-1],inv[i]);
	}
	ifact[_n] = inverse(fact[_n]);
	for(int i=_n-1;i>=1;i--)
	{
		ifact[i] = mult(ifact[i + 1], i + 1);
	}
	for(int i=1;i<=_n;i++)
	{
		inv[i] = mult(fact[i-1],ifact[i]);
	}
}

int dp[333][333][333];
int pref[333];
int a[333];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	init(11111);
	string s; int m; cin>>s>>m; m=min(m,int(s.length()));
	int cnt=0;
	for(int i=0;i<s.length();i++)
	{
		if(s[i]=='0') cnt++;
		else a[cnt]++;
	}
	int n=cnt; int ones=int(s.length())-cnt;
	for(int i=0;i<=n;i++)
	{
		pref[i]=a[i];
		if(i) pref[i]+=pref[i-1];
	}
	assert(ones==pref[n]);
	//cerr<<"N = "<<n<<'\n';
	int ans=0;
	dp[0][0][0]=1;
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=ones;j++)
		{
			for(int k=0;k<=ones;k++)
			{
				if(dp[i][j][k]==0) continue;
				int v=dp[i][j][k];
				//cerr<<i<<' '<<j<<' '<<k<<": "<<max(0,pref[i]-j)<<' '<<ones-j<<'\n';
				for(int l=ones-j;l>=max(0,pref[i]-j);l--)
				{
					radd(dp[i+1][j+l][k+min(a[i],l)],v);
					//cerr<<"NEW "<<i+1<<' '<<j+l<<' '<<k+min(a[i],l)<<'\n';
				}
			}
		}
	}
	for(int i=max(0,ones-m);i<=ones;i++)
	{
		//cerr<<n+1<<' '<<ones<<' '<<i<<' '<<dp[n+1][ones][i]<<'\n';
		radd(ans,dp[n+1][ones][i]);
	}
	cout<<ans<<'\n';
}


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

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;
struct Edge {
    int to;
    int weight;
    Edge(int t, int w)
        : to(t)
        , weight(w)
    {
    }
};
using Graph = vector<vector<int>>;
using Graph_e = vector<vector<Edge>>;
typedef long long ll;
typedef pair<int, int> P;
vector<int> dx = { 1, 0, -1, 0 };
vector<int> dy = { 0, 1, 0, -1 };

const int MOD = 1000000007;
const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

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

struct UnionFind {
    vector<int> par; // 親ノード
    vector<int> rank;

    UnionFind(int n = 1)
    {
        init(n);
    }

    void init(int n = 1)
    {
        par.resize(n);
        rank.resize(n);
        for (int i = 0; i < n; i++) {
            par[i] = i;
            rank[i] = 0;
        }
    }

    int root(int x)
    {
        if (par[x] == x) {
            return x;
        } else {
            int r = root(par[x]);
            return par[x] = r; // 辺の縮約（一度根をたどったら辺を直接根に向かって貼り直す）
        }
    }

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

    bool merge(int x, int y)
    {
        x = root(x);
        y = root(y);
        if (x == y)
            return false;
        if (rank[x] < rank[y])
            swap(x, y);
        if (rank[x] == rank[y])
            ++rank[x];
        par[y] = x; // xよりyのほうが高さが小さい木
        return true;
    }
};

// 最大公約数
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

// 最小公倍数
int lcm(int a, int b)
{
    return a * b / gcd(a, b);
}

// 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
long long extGCD(long long a, long long b, long long& x, long long& y)
{
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

// 負の数にも対応した % 演算
long long mod(long long val, long long m)
{
    long long res = val % m;
    if (res < 0)
        res += m;
    return res;
}

// a^n modを計算する
long long modpow(long long a, long long n, long long mod)
{
    long long res = 1;
    // nを2進数表示して1が埋まっている桁に関してはa^mをかけていく
    while (n > 0) {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

// a^{-1} mod を計算する
long long modinv(long long a, long long mod)
{
    return modpow(a, mod - 2, mod);
}

int main()
{
    int H, A;
    cin >> H >> A;
    int i = 0;
    while (H > 0) {
        H -= A;
        i++;
    }

    cout << i << endl;
}

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

using namespace std;

int n;
int st[800010];
int a[200010], dp[200010];
vector<int> vec, adj[200010];

void update(int l, int r, int pt, int val, int i){
    if(r < pt || pt < l) return;

    if(l == r && l == pt){
        st[i] = val;
        return;
    }

    int m = (l + r) >> 1;

    update(l, m, pt, val, i << 1);
    update(m + 1, r, pt, val, 1 + (i << 1));

    st[i] = max(st[i << 1], st[1 | (i << 1)]);
}

int query(int l, int r, int ls, int rs, int i){
    if(r < ls || rs < l) return 0;

    if(ls <= l && r <= rs) return st[i];

    int m = (l + r) >> 1;

    return max(query(l, m, ls, rs, i << 1), query(m + 1, r, ls, rs, 1 + (i << 1)));
}

void dfs(int u, int p){
    int res = query(1, n, a[u], a[u], 1);

    update(1, n, a[u], query(1, n, 1, a[u] - 1, 1) + 1, 1);
    dp[u] = query(1, n, 1, n, 1);

    for(auto &v : adj[u]){
        if(v == p) continue;

        dfs(v, u);
    }

    update(1, n, a[u], res, 1);
}

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

    cin >> n;

    for(int i = 1; i <= n; i++) cin >> a[i], vec.emplace_back(a[i]);

    for(int i = 1; i < n; i++){
        int u, v;

        cin >> u >> v;

        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    for(int i = 1; i <= n; i++){
        a[i] = (int) (lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin()) + 1;
    }

    dfs(1, 1);

    for(int i = 1; i <= n; i++) cout << dp[i] << "\n";
    
    return 0;
}


Measured memory_bytes: 30736
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
#include<cstdio>
#include<string.h>
#include<cmath>
using namespace std;
int main() {
	long long n, k;
	cin >> n >> k;
	if (n > k)n = n - (n/k)*k;
	cout << min(k-n, n) << endl;
	return 0;
}

Measured memory_bytes: 3632
n, l = map(int, input().split())
a = list(map(int, input().split()))
ind = -1
for i in range(n-1):
    if a[i]+a[i+1] >= l:
        ind = i
        break

if ind == -1:
    print("Impossible")
else:
    print("Possible")
    for i in range(ind):
        print(i+1)
    for i in range(n-1, ind, -1):
        print(i)


Measured memory_bytes: 85904
#include<iostream>
#include<vector>
#include<algorithm>
#define MAX_N 100001
using namespace std;

int calc_gcd(int x, int y) {
    if (y == 0) return x;
    return calc_gcd(y, x % y);
}

int main() {
    int N, X;
    cin >> N >> X;
    vector<int> city_coord;
    int x;
    for (int i = 0; i < N; i++) {
        cin >> x;
        city_coord.push_back(x);
    }
    city_coord.push_back(X);
    sort(city_coord.begin(), city_coord.end());
    vector<int> mod_v;
    for (int i = 1; i < city_coord.size(); i++) {
        mod_v.push_back(city_coord[i] - city_coord[i - 1]);
    }
    sort(mod_v.begin(), mod_v.end());
    int now_gcd = mod_v[0];
    for (int i = 1; i < mod_v.size(); i++) {
        now_gcd = calc_gcd(max(now_gcd, mod_v[i]), min(now_gcd, mod_v[i]));
    }
    cout << now_gcd << endl;
    return 0;
}

Measured memory_bytes: 1400
n, k = map(int, input().split())

total = 0
mod = 10 ** 9 + 7
for i in range(k, n+2):
    total += n * (n + 1) // 2 - (n - i) * (n - i + 1) // 2 - (i-1) * i // 2 + 1
    total %= mod

print(total)

Measured memory_bytes: 63596
#include <iostream>
#include <cstring>
#include <cstdio>
#include<utility>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<bitset>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
typedef pair<double,double>P_D;
#define PI 3.1415926535897932384626433832795
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define reprev(i, n) for (int i = (int)n - 1; i >= 0; i--)
#define ALL(a)  (a).begin(),(a).end()
#define MAX 100100
#define MAX_N 200100
#define SENTINEL 2000000000
#define MAX_B 1001001
#define NIL -1
#define MOD 1000000007
#define INF 1 << 29
#define INFTY 1000000000000000000LL
int n,y;
int main(){
    cin>>n>>y;
    rep(i,n+1){
        rep(j,n+1){
            if(n-i-j>=0 && y==10000*i+5000*j+1000*(n-i-j)){
                cout<<i<<" "<<j<<" "<<n-i-j<<endl;
                return 0;
            }
        }
    }
    rep(i,3)cout<<-1<<" ";
    cout<<endl;
}

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

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cout << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

const ll MOD = 1000000007;

int main() {
	int N; cin >> N;
	vi C(N), vl(N, -1);
	map<int, int> T;

	rep(i, N) {
		cin >> C[i]; --C[i];
		if (T.count(C[i])) {
			vl[i] = T[C[i]];
		}
		T[C[i]] = i;
	}

	vector<ll> dp(N + 1);
	dp[0] = 1;

	rep(i, N) {
		dp[i+1] = dp[i];
		if (vl[i] != -1 && vl[i] < i-1) {
			dp[i+1] = (dp[i+1] + dp[vl[i] + 1]) % MOD;
		}
	}
	cout << dp.back() << endl;

	return 0;
}

Measured memory_bytes: 12800