akhauriyash/Code-Regression huggingface dataset:
import bisect

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

a.sort()
n=a[-1]

if n%2==0:
    middleIdx=bisect.bisect_left(a[:N-1],n//2)
    
    if a[middleIdx]==n//2:
        r=a[middleIdx]
    elif a[min(middleIdx,N-2)]-n//2 > n//2-a[max(middleIdx-1,0)]:
        r=a[max(middleIdx-1,0)]
    else:
        r=a[min(middleIdx,N-2)]
    print(n,r)
else:
    m1=bisect.bisect_left(a[:N-1],n//2)
    m2=bisect.bisect_left(a[:N-1],n//2+1)
    if a[m1]==n//2:
        r=a[m1]
    elif a[m2]==n//2+1:
        r=a[m2]
    elif a[min(m2,N-2)]-(n//2+1) > n//2-a[max(m1-1,0)]:
        r=a[max(m1-1,0)]
    else:
        r=a[min(m2,N-2)]
    print(n,r)

Measured memory_bytes: 14060
#include<bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n ; i++)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x) // decltypeで型取得、引数があればva_argsのところに入れる
#define Fill(x, v, y) fill(x, x + v, y);
using namespace std;
typedef long long ll; // long longをllでかけるようにした
const int INF = 1e9;
const long long INFTY = (1LL<<32);
const double PI = 3.1415926535;
const int MOD = 1000000007; // 計算してからmodで割る ans = (ans * a) % mod
#define int long long
template <typename T = long long > T in () { T x; cin >> x; return(x);}
// int a = in() のように使うlong long以外の型の時はstirng s = in<string>()のように型を指定する

signed main(void){
    int n, m; cin >> n >> m;
    int num[n];
    REP(i, n) num[i] = -1;
    bool flag = true;

    if(n == 1 and m == 0){
        cout << 0 << endl;
        return 0;
    }

    REP(i, m){
        int s, c; cin >> s >> c;
        if(num[s - 1] != -1 and num[s - 1] != c) flag = false;
        else num[s - 1] = c;
    }

    if(n == 1 and num[0] == 0){
        cout << 0 << endl;
        return 0;
    }

    bool all_zero = true;
    REP(i, n){
        if(num[i] != 0) all_zero = false;
    }
    if(all_zero) flag = false;
    if(num[0] == 0) flag = false;

    if(flag){
        int ans = 0;
        REP(i, n){
            if(i == 0 and num[i] == -1){
                num[i] = 1;
            }
            else if(num[i] == -1) num[i] = 0;
            ans = ans*10 + num[i];
        }
        if(ans == 0) cout << -1 << endl;
        else cout << ans << endl;
    }
    else cout << -1 << endl;
}

Measured memory_bytes: 256
fn read_stdin() -> String {
    use std::io::Read;
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input).unwrap();
    input
}

fn scan<'a, I: Iterator<Item = &'a str>, T: std::str::FromStr>(tokens: &mut I) -> T {
    tokens.next().unwrap().parse().ok().unwrap()
}

fn vec<T, F: FnMut(usize) -> T>(n: usize, mut f: F) -> Vec<T> {
    (0..n).map(|i| f(i)).collect()
}

fn main() {
    let input = read_stdin();
    let tokens = &mut input.split_whitespace();
    let mut x: usize = scan(tokens);
    let mut y: usize = scan(tokens);
    let a: usize = scan(tokens);
    let b: usize = scan(tokens);
    let c: usize = scan(tokens);
    let mut p: Vec<usize> = vec(a, |_| scan(tokens));
    let mut q: Vec<usize> = vec(b, |_| scan(tokens));
    let mut r: Vec<usize> = vec(c, |_| scan(tokens));
    p.sort();
    q.sort();
    r.sort();
    p.reverse();
    q.reverse();
    r.reverse();
    let mut ans = 0;
    for i in 0..x {
        ans += p[i];
    }
    for i in 0..y {
        ans += q[i];
    }
    let mut z = 0;
    while z < c {
        if x != 0 && p[x - 1] < r[z] {
            if y != 0 && p[x - 1] > q[y - 1] {
                y -= 1;
                ans -= q[y];
                ans += r[z];
                z += 1;
            } else {
                x -= 1;
                ans -= p[x];
                ans += r[z];
                z += 1;
            }
        } else if y != 0 && q[y - 1] < r[z] {
            y -= 1;
            ans -= q[y];
            ans += r[z];
            z += 1;
        } else {
            break;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 12408
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define uniq(v) v.erase(unique(v.begin(),v.end()),v.end())
#define lb(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define ub(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
using Pair = pair<ll,pair<int,int>>;
#define pq priority_queue<Pair, vector<Pair>, greater<Pair>> 
const ll mod=1000000007;
//const ll mod=998244353;
const ld pi=acos(-1.0);
const ll INF = 1LL<<61;
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; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる



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

  int m,k;
  cin>>m>>k;

  if(m==0){
    if(k==0) cout << "0 0" << endl;
    else cout << -1 << endl;
    return 0;
  }

  if(m==1){
    if(k==0) cout << "0 0 1 1" << endl;
    else cout << -1 << endl;
    return 0;
  }

  int x=pow(2,m);

  if(x<=k) {
    cout << -1 << endl;
    return 0;
  }

  rep(i,x){
    if(i==k) continue;
    cout << i << " ";
  }

  cout << k << " ";

  for(int i=x-1;i>=0;i--){
    if(i==k) continue;
    cout << i << " ";
  }

  cout << k << endl;

}

Measured memory_bytes: 4068
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
#define vec(s) vector

#define vvec(s) vector<vector
>
typedef vector<lli> vi;
typedef vector<vi> vvi;
typedef pair<lli,lli> pii;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define YN(x) cout<<(bool x?"Yes":"No")<<endl;
#define out(s) cout<<s<<endl;
#define pb(s) push_back(s);
#define sp " ";
#define INF 10000000000
#define all(s) s.begin(),s.end()
void vout(vi v){
    for(int i=0;i<v.size();i++)
    cout<<v.at(i)<<endl;
}
int main(){
    lli a, b, k;
    cin >> k >> a >> b;
    for (lli i = a; i <= b; i++)
    {
        if(i%k==0){
            out("OK");
            return 0;
        }
    }
    out("NG");
}

Measured memory_bytes: 3648
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

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

  int n=a*100,m=0;
  rep(ai,f/100/a+1)rep(bi,f/100/b+1){
    int ni = (a*ai+b*bi)*100;
    if(ni>f) continue;
    int x = min(f-ni,ni*e/100);
    rep(ci,x/c+1){
      int di = (x-c*ci)/d;
      int mi = c*ci+d*di;
      if(m*(ni+mi)<mi*(n+m)){
        n = ni;
        m = mi;
      }
    }
  }
  cout << (n+m) << " " << m << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
#define rep(i,ra,re) for((i)=ra;(i)<(re);(i)++)
#define _rep(i,ra,re) for((i)=ra;(i)>(re);(i)--)
#define rep_(i,ra,re) for((i)=ra;(i)<=(re);(i)++)
#define _rep_(i,ra,re) for((i)=ra;(i)>=(re);(i)--)
#define put(n) cout << n << " "; 
#define puts(n) cout << n << endl;
#define pu(n) cout << n;
#define mod 1000000007
#define INF 1000000000000000
int i,j,k,l;
static const int MAX_N=10e5;
int main(void){
	long x,y;
		cin >> x >> y;
		int a=y-x;
	x%=2019;
	y%=2019;
	if(y<x || a>2019){
		puts(0);}
	else{
		long ans=INF;
		rep(i,x,y+1){
			rep(j,x,y+1){
				if(i==j)
					continue;
				ans=min(ans,(long)i*j%2019);
			}
		}
		puts(ans);
	}return 0;
}


Measured memory_bytes: 256
N = int(input())
h = list(map(int, input().split()))

cur = 0
total = 0
while h != [0] * N:
    for i in range(cur, N):
        if cur == i and h[i] == 0:
            cur += 1
        elif h[i] == 0:
            if cur == i - 1:
                total += h[i - 1]
                h[i - 1] = 0
            else:
                min_h = min(h[cur:i])
                total += min_h
                for j in range(cur, i):
                    h[j] -= min_h
        elif i == N - 1:
            min_h = min(h[cur:N])
            total += min_h
            for j in range(cur, N):
                h[j] -= min_h
print(total)


Measured memory_bytes: 3064
package main

import (
    "fmt"
)

func main() {
    var n int 
    fmt.Scan(&n)
    var sum, minus int 
    var zero bool
    min := int(1e9) + 1 
    for i := 0; i < n; i++ {
        var a int 
        fmt.Scan(&a)

        if a < 0 { 
            minus++
            a = -a
        } else if a == 0 { 
            zero = true
        }   

        sum += a
        if a < min {
            min = a 
        }   
    }   

    if zero || minus%2 == 0 { 
        fmt.Println(sum)
    } else {
        fmt.Println(sum - min*2)
    }   
}


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

using namespace std;

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15);
  }
} initializer;

template<typename T> int least_bit(T n) {
  static_assert(sizeof(T) == 4 || sizeof(T) == 8, "unsupported size");
  if (sizeof(T) == 4) return __builtin_ffs(n) - 1;
  if (sizeof(T) == 8) return __builtin_ffsll(n) - 1;
}

// n must be greater than 0.
template<typename T> int least_bit_fast(T n) {
  static_assert(sizeof(T) == 4 || sizeof(T) == 8, "unsupported size");
  if (sizeof(T) == 4) return __builtin_ctz(n);
  if (sizeof(T) == 8) return __builtin_ctzll(n);
}

template<typename T> int most_bit(T n) {
  static_assert(sizeof(T) == 4 || sizeof(T) == 8, "unsupported size");
  if (sizeof(T) == 4) return n ? 31 - __builtin_clz(n) : -1;
  if (sizeof(T) == 8) return n ? 63 - __builtin_clzll(n) : -1;
}

template<typename T> int count_bit(T n) {
  static_assert(sizeof(T) == 4 || sizeof(T) == 8, "unsupported size");
  if (sizeof(T) == 4) return __builtin_popcount(n);
  if (sizeof(T) == 8) return __builtin_popcountll(n);
}

template<typename T> T gcd(T t) {return t;}

template<typename T, typename... S> T gcd(T a, S... s) {
  auto b = gcd(s...);
  if (a == 0 || b == 0) return max(a, b);
  int fa = least_bit_fast(a);
  int fb = least_bit_fast(b);
  a >>= fa;
  b >>= fb;
  while (a != b) {
    auto& c = a > b ? a : b;
    c >>= least_bit_fast(c = abs(a - b));
  }
  return a << min(fa, fb);
}

template<typename T> T lcm(T t) {return t;}

template<typename T, typename... S> T lcm(T t, S... s) {
  T l = lcm(s...);
  return t / gcd(t, l) * l;
}

template<typename T> T floor(T a, T b) {
  auto d = div(a, b);
  return d.quot - (d.rem && (a < 0) != (b < 0) ? 1 : 0);
}

template<typename T> T ceil(T a, T b) {
  auto d = div(a, b);
  return d.quot + (d.rem && (a > 0) == (b > 0) ? 1 : 0);
}

template<typename T> T round(T a, T b) {return floor(a + b / 2, b);}

template<typename T> T mod(T a, T b) {
  T c = a % b;
  return c < 0 ? c + abs(b) : c;
}

template<typename T> T factorial(T n) {return n <= 1 ? 1 : factorial(n - 1) * n;}

template<typename T> T square(T n) {return n * n;}

template<typename T> T cube(T n) {return n * n * n;}

template<typename T> T norm(T x1, T y1, T x2, T y2) {return square(x1 - x2) + square(y1 - y2);}

template<typename T> bool isSquare(T n) {return square(T(sqrt(n))) == n;}

int main() {
  int64_t a, b, x;
  cin >> a >> b >> x;
  cout << b / x - floor(a - 1, x) << endl;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long int
#define ar array
#define mp make_pair
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin>>n;
	vector<ll> a(3*n);
	ll ans = -1e18;
	for(int i = 0; i<3*n; i++)
		cin>>a[i];
	multiset<ll,greater<ll> > pq1;
	multiset<ll> pq2;
	ll sum1[n+1],sum2[n+1],sum11=0,sum22=0;
	for(int i = 0; i<n; i++)
	{
		sum11 +=a[i];
		pq1.insert(a[i]);
	}
	sum1[0]=sum11;
	for(int i = n; i<2*n;i++)
	{
		pq1.insert(a[i]);
		int y = *(--pq1.end());
		pq1.erase(--pq1.end());
		sum11 += a[i];
		sum11 -= y;
		sum1[i-n+1] = sum11;
	}
	for(int i = 3*n-1; i>=2*n; i--)
	{
		sum22 += a[i];
		pq2.insert(a[i]);
	}
	sum2[n] = sum22;
	for(int i = 2*n-1; i>=n; i--)
	{
		pq2.insert(a[i]);
		int y = *(--pq2.end());
		pq2.erase(--pq2.end());
		sum22 += a[i];
		sum22 -= y;
		sum2[i-n] = sum22;
	}
	for(int i = 0; i<n+1; i++)
		ans = max(ans,sum1[i]-sum2[i]);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 13568
n = int(input())
s = [input() for _ in range(n)]
a = 0
b = 0
ab = 0
a_b = 0
for i in s:
    if i[0] == 'B' and i[-1] == 'A':
        a_b += 1
    if i[0] == 'B':
        b += 1
    if i[-1] == 'A':
        a += 1
    for j in range(len(i)-1):
        if i[j:j+2] == 'AB':
            ab += 1
if a_b == a == b != 0:
    b -= 1
print(ab+min(a, b))

Measured memory_bytes: 3700
N,M = map(int,input().split())
a=[]
for i in range(N):
  x = input().split()
  z = x[1:]
  a += list(map(int,z))
cnt=0
for k in range(1,M+1):
  n = a.count(k)
  if n==N:
    cnt +=1
  else:
    cnt = cnt
print(cnt)
    
  
    
    
       
    


Measured memory_bytes: 3060
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7

n, m = map(int, readline().split())
a = list(map(int, read().split()))

dp = [0] * (n + 1)
ok = [1] * (n + 1)

for i in a:
    ok[i] = 0

dp[0] = 1
dp[1] = 1 * ok[1]

for i in range(2, n + 1):
    if ok[i - 1] == 0 and ok[i - 2] == 0:
        print(0)
        exit()
    else:
        dp[i] = dp[i - 1]*ok[i - 1] + dp[i - 2]*ok[i - 2]
    if dp[i] > MOD:
        dp[i] %= MOD

print(dp[-1])

Measured memory_bytes: 18932
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<random>
#include<set>
#include<map>
#include<functional>
using namespace std;
#define int long long
#define inf 1145141919
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<int, int>P;
typedef pair<int, P> PP;
struct edge { int u, v, cost; };
int p[11], c[11];
signed main() {
	int d, g; cin >> d >> g;
	rep(i, d)cin >> p[i] >> c[i];
	int ans = 11451419;
	for (int i = 0; i < (1 << d); i++) {//AP
		int ps = 0, pp = 0;
		rep(j, d) {
			if (i&(1 << j)) {
				ps += p[j] * (j + 1) * 100 + c[j];
				pp += p[j];
				}
			}
		if (ps < g) {
			int n = g - ps;
			int ms = 11451419;
			rep(j, d) {
				if (!(i&(1 << j))) {
					if (p[j] * (j + 1) * 100 >= n) {
						int s = (n + (j + 1) * 100 - 1) / (j + 1) / 100;
						ms = min(ms, s);
					}
				}
			}
			pp += ms;
		}
		ans = min(ans, pp);
		}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define Rep(i,s,n) for(int i=s;i<n;i++)
#define per(i,s,n) for(int i=n-1;i>=s;i--)
#define fi first
#define se second
#define all(c) c.begin(),c.end()
typedef long long int ll;
typedef pair<int, int> P;
typedef long double ld;
void Ans(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}

const ld INF=100100100100000;
const ll mod=1000000007;

int main(){
  ll n;
  cin>>n;
  ll a;
  priority_queue<ll> nq;
  priority_queue<ll,vector<ll>,greater<ll>> q;
  
  ll now[n];
  ll ans[n+1];

  ans[0]=0;
  
  rep(i,n){
    cin>>a;
    q.push(a);
    ans[0]+=a;
  }
  
  
  rep(i,n){
    cin>>a;
    now[i]=a;
    q.push(a);
    ll x=q.top();q.pop();
    ans[i+1]=ans[i]-x+a;
  }
  
  
  ll u[n+1];
  u[n]=0;
  
  rep(i,n){
    cin>>a;
    nq.push(a);
    u[n]+=a;
  }
  //ll Ans=ans[n]-u[n];
  //cout<<Ans<<endl;
  //cout<<u<<endl;
  per(i,0,n){
    nq.push(now[i]);
    ll y=nq.top();nq.pop();
    u[i]=u[i+1]-y+now[i];
  }
  ll Ans=-INF;
  
  rep(i,n+1){
    Ans=max(Ans,ans[i]-u[i]);
  }
  
  cout<<Ans<<endl;
}
  
  


Measured memory_bytes: 4340
//
//  main.cpp
//  2
//
//  Created by RISHAV SINGH MEHTA on 31/01/20.
//  Copyright © 2020 RISHAV SINGH MEHTA. All rights reserved.
//

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
int main(int argc, const char * argv[]) {
    // insert code here...
    ll int T,i,j,k,l,H,N;
    cin>>H>>N;
    ll int sum=0;
    for (i=0; i<N; i++) {
        cin>>l;
        sum += l;
    }
    
    if (sum>=H) {
        cout<<"Yes";
    }else{
        cout<<"No";
    }
    cout<<endl;
    
    return 0;
}



Measured memory_bytes: 384
// Copyright (C) 2018 Sayutin Dmitry.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.

#include <iostream>
#include <vector>
#include <stdint.h>
#include <algorithm>
#include <set>
#include <map>
#include <array>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <string>
#include <assert.h>
#include <iterator>
#include <cstdint>
#include <cinttypes>
#include <string.h>
#include <random>
#include <numeric>
#include <tuple>


using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::min;
using std::abs;
using std::max;

using std::unique;
using std::sort;
using std::generate;
using std::reverse;
using std::min_element;
using std::max_element;

#ifdef LOCAL
#define LASSERT(X) assert(X)
#else
#define LASSERT(X) {}
#endif

template <typename T>
T input() {
    T res;
    cin >> res;
    LASSERT(cin);
    return res;
}

template <typename IT>
void input_seq(IT b, IT e) {
    std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>);
}

#define SZ(vec)         int((vec).size())
#define ALL(data)       data.begin(),data.end()
#define RALL(data)      data.rbegin(),data.rend()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()

#define pb push_back
#define eb emplace_back

bool dfs(vector<char>& lused, vector<int>& rpair, vector<pair<int, int>>& a, vector<pair<int, int>>& b, int v) {
    lused[v] = 1;
    for (int u = 0; u != SZ(b); ++u)
        if (a[v].first < b[u].first and a[v].second < b[u].second)
            if (rpair[u] == -1 or (not lused[rpair[u]] and dfs(lused, rpair, a, b, rpair[u]))) {
                rpair[u] = v;
                return true;
            }

    return false;
}

int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    // code here.
    int n = input<int>();
    
    vector<pair<int, int>> a(n), b(n);
    for (auto& elem: a)
        cin >> elem.first >> elem.second;
    for (auto& elem: b)
        cin >> elem.first >> elem.second;

    vector<int>  rpair(n, -1);

    int ans = 0;
    for (int i = 0; i != n; ++i) {
        vector<char> lused(n, false);
        ans += dfs(lused, rpair, a, b, i);
    }

    cout << ans << "\n";
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
	
using namespace std;
const int MAX_N=5e3;
const ll MOD=1e9+7;
int N;
vector<int> G[MAX_N];

ll dp[MAX_N][MAX_N][2],temp[MAX_N][2][2],g[MAX_N+1];
int chi[MAX_N];

void dfs(int v,int p){
	for(auto e:G[v]){
		if (e!=p){
			dfs(e,v);
		}
	}
	for(auto e:G[v]){
		if (e!=p){
			chi[v]+=chi[e];
		}
	}
	chi[v]++;
	bool f=false;
	int inx=0,c=1;
	REP(i,2)temp[0][i][0]=0;
	for(auto e:G[v]){
		if (e!=p){
			if (!f){
				REP(i,chi[e]+1)REP(j,2)temp[i][j][0]=0;
				REP(i,chi[e]){
					REP(j,2){
						temp[i+1][j][0]=dp[e][i][j];
						temp[0][1-j][0]+=dp[e][i][j]*g[i+1]%MOD;
						temp[0][1-j][0]%=MOD;
					}
				}
				f=true;
			}else{
				REP(i,c+chi[e])REP(j,2)temp[i][j][1-inx]=0;
				REP(i,c){
					REP(j,2){
						REP(a,chi[e]){
							REP(b,2){
								temp[i+a+1][(j+b)&1][1-inx]+=temp[i][j][inx]*dp[e][a][b]%MOD;
								temp[i+a+1][(j+b)&1][1-inx]%=MOD;
								temp[i][(j+b+1)&1][1-inx]+=temp[i][j][inx]*g[a+1]%MOD*dp[e][a][b]%MOD;
								temp[i][(j+b+1)&1][1-inx]%=MOD;
							}
						}
					}
				}
				inx=1-inx;
			}
			c+=chi[e];
		}
	}
	if (c==1){
		temp[0][0][0]=1;
	}
	REP(i,chi[v]){
		REP(j,2){
			dp[v][i][j]=temp[i][j][inx];
		}
	}
}
	
int main(){
	cin>>N;
	REP(i,N-1){
		int x,y;
		cin>>x>>y;
		x--;
		y--;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	g[0]=1;
	FOR(i,1,N+1){
		if ((i&1)==0){
			g[i]=g[i-2]*(i-1)%MOD;
		}
	}
	dfs(0,-1);
	ll ans=0;
	REP(x,chi[0]){
		REP(p,2){
			ans+=dp[0][x][p]*g[x+1]*(p==0 ? 1 : -1);
			ans+=MOD;
			ans%=MOD;
		}
	}
	cout<<ans<<endl;
	return 0;
}

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

int main(){

int n;
cin >> n;
int x;
priority_queue<int>q;
for (int i = 0; i < n; i++)
{
  cin >> x;
  q.push(x);
}

int alice = 0;
int bob = 0;
bool a = true;
while(a){
  alice += q.top();
  q.pop();
  if(q.empty()){
    break;
    }
  bob += q.top();
  q.pop();
  if(q.empty()){
    break;
    }
}

cout << alice - bob << endl;

}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using lli = long long int;


int main(){
  int n;
  std::cin >> n;
  vector<lli> a(n);
  for (int i = 0; i < n; i++) std::cin >> a[i];
  lli ans = a[0] - 1, price = 2;
  a[0] = 1;
  for (int i = 1; i < n; i++) {
    if(a[i] < price)continue;
    if(a[i] == price){
      price++;
    }else{
      ans += a[i]/price - (a[i]%price == 0);
      a[i] = price;
    }
    // for (int j = 0; j < n; j++) {
    //   std::cout << a[j] << " ";
    // }
    // std::cout << std::endl;
    // std::cout << price << " " << ans<< std::endl;
  }
  std::cout << ans << std::endl;
  return 0;
}


Measured memory_bytes: 1024
/*
 * author :Sadik Hassan
 *
*/
#include "bits/stdc++.h"
using namespace std;
#define ll            long long
#define nl            "\n"
#define PB            push_back
#define fi            first
#define se            second
#define _SAD()        ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
#define rep(i,n)      for(int i=0;i<n;i++)
#define repn(i,n)     for(int i=1;i<=n;i++)
#define rrep(i,n)     for(int i=n-1;i>=0;i--)
#define SZ(s)         s.size()
#define SRT(x,y)      sort(x,x+y)
#define REV(a,b)      reverse(a,a+b)
#define VSRT(x)       sort(x.begin(),x.end())
#define VREV(x)       reverse(x.begin(),x.end())
#define TSFL(s)       transform(s.begin(),s.end(),s.begin(),::toupper);
#define TSFH(s)       transform(s.begin(),s.end(),s.begin(),::tolower);
/*---------------------------------------------------------------------*/
const int N = 2e5+10;
const int INF = (int)1e9+5;

int main()
{
    _SAD()
    int n;
    cin>>n;
    cout<<(n+1)/2<<nl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N=55;

int n,a[N],b[N],f[N][N],g[N][N];

inline void Tofix(int f[N][N]){
	for(int k=0;k<=50;k++)
		for(int i=0;i<=50;i++)
			for(int j=0;j<=50;j++)
				f[i][j]|=f[i][k]&f[k][j];
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	int flg=1;
	for(int i=1;i<=n;i++) flg&=(a[i]==b[i]);
	if(flg) return puts("0"),0;
	long long ans=0;
	for(int i=0;i<=50;i++) g[i][i]=1;
	while(1){
		int p=-1;
		memcpy(f,g,sizeof(f));
		for(int i=1;i<=50;i++){
			for(int j=i;j<=50;j++) f[j][j%i]=1;
			Tofix(f); int flg=1;
			for(int j=1;j<=n;j++) flg&=f[a[j]][b[j]];
			if(flg){
				p=i; break;
			}
		}
		if(!~p) return puts("-1"),0;
		for(int i=p;i<=50;i++) g[i][i%p]=1;
		Tofix(g); ans|=1LL<<p;
		int flg=1;
		for(int j=1;j<=n;j++) flg&=g[a[j]][b[j]];
		if(flg) break;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
def resolve():
    '''
    code here
    https://atcoder.jp/contests/code-festival-2016-qualb/tasks/codefestival_2016_qualB_b
    '''
    N, A, B = [int(item) for item in input().split()]
    S = input()
    d = 0
    c = 0
    for i in range(N):
        temp = S[i]
        if temp == 'a':
            if d < A+B:
                d += 1
                print('Yes')
            else:
                print('No')
        elif temp == 'b':
            if d < A+B and c < B:
                c +=1
                d += 1
                print('Yes')
            else:
                print('No')
        else:
            print('No')

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 9312
w, h, n=map(int,input().split())

mat = [list(map(int, input().split())) for _ in range(n)]

w1 = 0
w2 = w
h1 = 0
h2 = h

for i in range(n):
    if(mat[i][2] == 1 and w1 < mat[i][0]):
        w1 = mat[i][0]
    elif(mat[i][2] == 2 and w2 > mat[i][0]):
        w2 = mat[i][0]
    elif(mat[i][2] == 3 and h1 < mat[i][1]):
        h1 = mat[i][1]
    elif(mat[i][2] == 4 and h2 > mat[i][1]):
        h2 = mat[i][1]
        
print((w2-w1)*(h2-h1) if w2 >= w1 and h2 >= h1 else 0)

Measured memory_bytes: 3064
use std::io;
fn read_line() -> String {
    let stdin = io::stdin();
    let mut buf = String::new();
    stdin.read_line(&mut buf);
    buf
}

fn strtovec(origin_text: String) -> Vec<i32> {
    let res: Vec<i32> = origin_text
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();
    res
}

fn exp1(x: i32, y: i32) -> i32 {
    let res = ((1900 * y) + (100 * (x - y))) * exp2(y);
    res
}

fn exp2(m: i32) -> i32 {
    fn doloop(i: i32) -> i32 {
        match i {
            1 => 2,
            _ => 2 * doloop(i - 1),
        }
    }
    doloop(m)
}

fn main() {
    let text: String = read_line();
    let v: Vec<i32> = strtovec(text);
    println!("{}", exp1(v[0], v[1]));
}

Measured memory_bytes: 4352
N = int(input())
A = list(map(int, input().split()))
C = [0]*(10**5)
for ai in A:
    C[ai] += 1

ans = 0
for i in range(10**5-2):
    ans = max(C[i] + C[i+1] + C[i+2], ans)
print(ans)

Measured memory_bytes: 82836
import Data.List
main=do
    [n,a,b]<-map read.words<$>getLine::IO[Int]
    s<-getLine
    putStr $ unlines $ f 0 1 a b s
f _ _ _ _ [] = []
f c o a b ('c':s) = "No" : f c o a b s
f c o a b ('a':s)
    | c < a+b = "Yes" : f (c+1) o a b s
    | otherwise = "No" : f c o a b s
f c o a b ('b':s)
    | c < a+b && o <= b = "Yes" : f (c+1) (o+1) a b s
    | otherwise = "No" : f c o a b s

Measured memory_bytes: 5372
import numpy
frag=True
n=int(input())
t=[list(map(int,input().split())) for _ in range(n)]
t=sorted(t,key=lambda x:x[1])
a=[t[i][0] for i in range(n)]
b=[t[i][1] for i in range(n)]
ar=list(numpy.cumsum(a))
for i in range(n):
  if ar[i] > b[i]:
    frag=False
if frag:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 67128
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
using namespace std;

int W, a, b;

int main() {
    cin >> W >> a >> b;

    // くっついているケース
    if ((b >= a && b <= a + W) ||
        (b + W >= a && b + W <= a + W)) {
            cout << 0 << endl;
            return 0;
        }


    //  離れているケース
    int t1 = abs(a + W - b);
    int t2 = abs(b + W - a);
    cout << min(t1, t2) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()
#define all(v) (v).begin(), (v).end()
#define sz(v) (int)(v).size()

using namespace std;

typedef long long ll;
typedef long double ld;

static const long long MOD = 1000000007;
static const long long INF = 1<<31;

int ans;

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

    for (int i=a; i<=b; i++) {
        if (i%k==0) {
            puts("OK");
            return 0;
        }
    }
    puts("NG");

    //cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3620
#include <iostream>
#include <vector>
using namespace std;
using uint = unsigned int;
using ull = unsigned long long;

int main() {
	uint N;
	cin >> N;
	
	vector<vector<uint>> cmb(10, vector<uint>(10));
	
	for(uint i=1; i<=N; i++) {
		uint l = i % 10;
		if(l == 0) continue;
		
		uint h = i;
		while(h >= 10) {
			h /= 10;
		}
		
		cmb[l][h]++;
	}
	
	ull ans = 0;
	
	for(uint l=1; l<10; l++) {
		for(uint h=1; h<10; h++) {
			ans += cmb[l][h] * cmb[h][l];
		}
	}
	
	
	cout << ans;
	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <set>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
  ll H, W;
  cin >> H >> W;
  char MAP[H][W];
  for (int h = 0; h < H; h++) {
    for (int w = 0; w < W; w++) {
      cin >> MAP[h][w];
    }
  }
  ll max_distance = 0;
  for (int s_h = 0; s_h < H; s_h++) {
    for (int s_w = 0; s_w < W; s_w++) {
      if (MAP[s_h][s_w] == '#') continue;
      deque<tuple<ll, ll, ll> > q;
      vector<vector<ll> > MEMO(H, vector<ll>(W, -1));
      MEMO[s_h][s_w] = 0;
      q.push_back(make_tuple(s_h, s_w, 0));
      while (q.size() != 0) {
        tuple<ll, ll, ll> current_pos = q.at(0);
        ll cur_h = get<0>(current_pos);
        ll cur_w = get<1>(current_pos);
        ll cur_d = get<2>(current_pos);
        q.pop_front();
        if (cur_h - 1 >= 0 && MEMO[cur_h - 1][cur_w] == -1 &&
            MAP[cur_h - 1][cur_w] != '#') {
          MEMO[cur_h - 1][cur_w] = cur_d + 1;
          q.push_back(make_tuple(cur_h - 1, cur_w, cur_d + 1));
        }
        if (cur_h + 1 < H && MEMO[cur_h + 1][cur_w] == -1 &&
            MAP[cur_h + 1][cur_w] != '#') {
          MEMO[cur_h + 1][cur_w] = cur_d + 1;
          q.push_back(make_tuple(cur_h + 1, cur_w, cur_d + 1));
        }
        if (cur_w - 1 >= 0 && MEMO[cur_h][cur_w - 1] == -1 &&
            MAP[cur_h][cur_w - 1] != '#') {
          MEMO[cur_h][cur_w - 1] = cur_d + 1;
          q.push_back(make_tuple(cur_h, cur_w - 1, cur_d + 1));
        }
        if (cur_w + 1 < W && MEMO[cur_h][cur_w + 1] == -1 &&
            MAP[cur_h][cur_w + 1] != '#') {
          MEMO[cur_h][cur_w + 1] = cur_d + 1;
          q.push_back(make_tuple(cur_h, cur_w + 1, cur_d + 1));
        }
        if (cur_d > max_distance) max_distance = cur_d;
      }
    }
  }
  cout << max_distance << endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){
    int N,A,B;
    scanf("%d %d %d",&N,&A,&B);
    int min = A+B-N;
    if(min<0){
        min = 0;
    }
    int max = A;
    if(A>B){
        max = B;
    }
    printf("%d %d",max,min);
    return 0;
}

Measured memory_bytes: 128
//Dragon_warrior7(IITK)
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define nl cout << '\n'
#define sor(x) sort(x.begin(), x.end())
#define rev(v) reverse(v.begin(), v.end())
#define maxin(v) *max_element(v.begin(), v.end())
#define minin(v) *min_element(v.begin(), v.end())
#define sumall(vect) accumulate(vect.begin(), vect.end(), 0)
#define count(x, vect) count(vect.begin(), vect.end(), x)
#define lb(v, temp) lower_bound(v.begin(), v.end(), temp)
#define ub(v, temp) upper_bound(v.begin(), v.end(), temp)
#define fi first
#define se second
#define llmax 100000000000000000
#define deb(x) cout << #x << " " << x << "\n"
#define pll pair<ll, ll> 
#define vll vector<ll> 
#define rub cout << "------------------------------------\n"
#define min(a, b, c) min(a, min(b, c))
#define max(a, b, c) max(a, max(b, c))
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//vll v[m + 1];
	ll n;
	ll m;
	cin >> n >> m;
	priority_queue<ll> pq;
	for (int i = 0; i < n; i++)
	{
	    ll a;
	    cin>>a;
	    pq.push(a);
	}
	ll sum = 0;
	ll maximum;
	for (int i = 1; i <= m; i++)
	{
    maximum=pq.top();
    maximum/=2;
    pq.pop();
    pq.push(maximum);
	}
	while(!pq.empty())
	{
	    sum+=pq.top();
	    pq.pop();
	}
	cout<<sum;
}

Measured memory_bytes: 1400
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iostream>

using namespace std;

int main(void){
	long N,A[200001],ans = long(0),sum = long(0);
	scanf("%ld",&N);
	for (long i=long(0);i<N;i++){
		scanf("%ld",&A[i]);
		if(i>long(0)){
			if(A[i] > A[i-1] + long(1))ans = long(-1);
			else if(A[i] == A[i-1] + long(1)){
				sum++;
			}else{
				sum += A[i];
			}
		}
	}

	if(A[0] != long(0)) ans = long(-1);
	if(ans != long(-1)) ans = sum;
	printf("%ld\n",ans);
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 1792
n=int(input())
s=[int(input()) for i in range(n)]
s=sorted(s)
s_sum=sum(s)
if s_sum%10!=0:
    print(s_sum)
    exit()

for i in range(n):
    if s[i]%10!=0:
        s_sum+=-s[i]
        print(s_sum)
        exit()
print(0)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int size_length=300;
const ll inf = LLONG_MAX/10;
bool flag;
ll matrix[size_length][size_length]= {inf};
bool arr[size_length][size_length]= {false};
void floyd(int n)
{
    for (int k=0; k<n; k++)
    {
        for (int i=0; i<n; i++)
        {
            for (int j=0; j<n; j++)
            {
                if(matrix[i][j]>matrix[i][k]+matrix[k][j]&&k!=j&&k!=i&&i!=j)
                {
                    flag = false;
                    return;
                }
                if(matrix[i][j]==matrix[i][k]+matrix[k][j]&&k!=j&&k!=i)
                {
                    arr[i][j]=true;
                    arr[j][i]=true;
                }
            }
        }
    }
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    flag = true;
    int n;
    cin>>n;
    for (int i =0; i<n; i++)
    {
        for (int j =0; j<n; j++)
        {
            cin>>matrix[i][j];
        }
    }
    floyd(n);
    if(!flag)
    {
        cout<<-1;
        return 0;
    }
    ll answer=0;
    for (int i =0; i<n; i++)
    {
        for (int j=0; j<n; j++)
        {
            if(!arr[i][j])
            {
                answer+=matrix[i][j];
            }
        }
    }
    cout<<answer/2;

    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i, n) for(int (i)=0 ;i <(n); ++(i))
#define REP(i,m,n) for(int (i) = (m); (i) <= (n); ++(i))
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)? "YES":"NO")
typedef long long ll;
using namespace std;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  if(b-a == c-b) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
using namespace std;
int n,ans;
signed main()
{
        scanf("%d",&n);
        for (int i=1; i<=n; i++) {
                // for (int j=1; j<=n; j++) {
                //         if (i*j<n) ans++;
                //         else break;
                // }
                ans+=n/i;
                if (n%i==0) ans--;
        }
        cout<<ans<<"\n";
        return 0;
}


Measured memory_bytes: 3764
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
#include <list>

using namespace std;



int main(void){
    int A,B,K;
    int tmp,tmp2;


    cin>>K;
    cin>>A>>B;

    tmp=A/K;
    if(A % K ==0){
        tmp2 = A;
    }else{
        tmp2= K*(tmp+1);
    }

    if(A <= tmp2 && tmp2 <= B){
        cout<<"OK"<<endl;
    }else{
        cout<<"NG"<<endl;
    }





    return 0;
}



Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define ALL(a) a.begin(),a.end()
typedef long long ll;
#define INF 1<<30

int main()
{
    ll H,W;
    cin >> H >> W;
    if(H==1||W==1)cout << "1" << endl;
    else cout << (H*W+1)/2 << endl;
    return 0;
}

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

int main(){
  ll n;
  map<ll,ll> d;
  cin>>n;
  for(int i=0;i<n;i++){
	ll a;
	cin>>a;
	d[a]++;
  }
  int f=1;
  cin>>n;
  for(int i=0;i<n;i++){
	ll a;
	cin>>a;
	if(d[a]>0)d[a]--;
	else f=0;
  }
  cout<<(f?"YES":"NO")<<endl;
  return 0;  
}


Measured memory_bytes: 12800
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
//#define int long long  ←保留
#define _CRT_SECURE_NO_WARNINGS
#define rep(i, n) for (int i = 0; i < n; i++)
#define _GLIBCXX_DEBUG
const int MOD = 1e9 + 7;
const int INF = 1e18 + 9;
constexpr long double pi = 3.141592653589793238462643383279; //円周率
/*---------------------便利な関数--------------------------------------*/
int fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i;
}

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

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

int keta(int n) {        //桁数を求める
    if (n == 0) return 1;
    int count = 0;
    while (n != 0) {
        n /= 10;
        count++;
    }
    return count;
}

int ketasum(int n) {    //各桁の和
    int sum = 0;
    while (n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
/*-------------ここまで---------------------------------------------*/

//C++(GCC9.2.1)

/*signed*/int main() {
    int n, m; cin >> n >> m;
    vector<int> broken(n + 2, false);
    for (int i = 1; i <= m; i++) {
        int a; cin >> a;
        broken[a] = true;
    }
    vector<long long> dp(n + 2, 0);
    dp[0] = 1;
    if (!broken[1]) dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!broken[i]) {
            dp[i] += dp[i - 1] + dp[i - 2];
            dp[i] %= MOD;
        }
    }
    cout << dp[n] << endl;
    return 0;
}

Measured memory_bytes: 4580
#include <bits/stdc++.h>
typedef long long ll;
const long long INF = 1LL << 60;
const int MOD = 1e9+7;
const ll LINF = 1e18;

using namespace std;

#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, a, b) for (int i = a; i <= b; i++)
#define all(a)  begin((a)),end((a))
#define uniq(c) (c).erase(unique(all((c))), end((c)))

const int MAX_N = 110;
const int MAX_V = 100100;

ll WEIGHTS[MAX_N], VALUE[MAX_N];
ll DP[MAX_N][MAX_V];

int main()
{
    int N, W; cin >> N >> W;
    rep (i, 0, N) {
        cin >> WEIGHTS[i] >> VALUE[i];
    }
    rep (i, 0, MAX_N) {
        rep (j, 0, MAX_V) {
            DP[i][j] = INF;
        }
    }
    DP[0][0] = 0;

    rep (i, 0, N) {
        rrep (sum_v, 0, MAX_V) {
            if (sum_v - VALUE[i] >= 0)
                DP[i+1][sum_v] = min(DP[i+1][sum_v], DP[i][sum_v - VALUE[i]] + WEIGHTS[i]);
            DP[i+1][sum_v] = min(DP[i+1][sum_v], DP[i][sum_v]);
        }
    }

    ll res = 0;
    rep (sum_v, 0, MAX_V) {
        if (DP[N][sum_v] <= W) res = sum_v;
    }
    cout << res << endl;
}

Measured memory_bytes: 86272
// Winners don't quit and Quitters don't win
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define mod 998244353
#define MAX 100005
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m,s=0;
    cin>>n>>m;
    if(n!=0){
    	s+=n*(n-1)/2;
	}
	if(m!=0){
		s+=m*(m-1)/2;
	}
	cout<<s;
}

Measured memory_bytes: 256
/// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split("\n");
	
	//文字列から10進数に変換するときはparseIntを使います
	var n = parseInt(input[0], 10);
	
		
	 var tmp = input[1].split(" ");
     var i = 0;               //横数字から配列作成
   var a = [];
for (var i = 0; i < n ; i++){
  var r= parseInt(tmp[i], 10);
    a[i] = r;}
//  console.log(a);


var b = [];
for (i = 0;i<n;i++){var f = a[i];
                  //  console.log(f);
                     b[f] = i+1;}
b = b.slice(1);
console.log(b.join(' '));


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

Measured memory_bytes: 36440
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;
int N[4];

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


Measured memory_bytes: 384
//#include <tourist>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = (1 << 28);
const int MOD = 1000000007;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; 
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; }
//setprecision(15)有効数字15桁
//-std=c++14
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a * b / gcd(a, b);}
int n;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    vector<ll> d(n),c(n);
    ll sum=0;
    for (int i = 0; i < n; i++)
    {
        cin >> d[i]>>c[i];
        sum+=c[i];
    }
    sum--;
    ll sumt=0;
    for(int i=0;i<n;i++){
        sumt+=d[i]*c[i];
        ll temp=sumt;
        ll amari=sumt%10;
        while(temp>=10){
            sum+=temp/10;
            temp/=10;
            temp+=amari;
            amari=temp%10;
        }
        sumt=amari;
    }
    cout << sum << "\n";
}



Measured memory_bytes: 3328
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<vector>
#include<climits>
#include<map>
#include<string>
#include<functional>
#include<iomanip>
#include<deque>
#include<random>

using namespace std;
typedef long long ll;
typedef double lldo;
#define mp make_pair
#define pub push_back
ll gcd(ll a, ll b) { if (a % b == 0) { return b; } else  return gcd(b, a % b); }
ll lcm(ll a, ll b) { if (a == 0) { return b; }return a / gcd(a, b) * b; }
template<class T>ll LBI(vector<T>& ar, T in) { return lower_bound(ar.begin(), ar.end(), in) - ar.begin(); }
template<class T>ll UBI(vector<T>& ar, T in) { return upper_bound(ar.begin(), ar.end(), in) - ar.begin(); }

ll a;
string s;

int main() {
	cin >> a;
	cin >> s;
	if (a >= 3200) {
		cout << s << endl;
	}
	else {
		cout << "red" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#define alphanso                  \
	ios_base::sync_with_stdio(0); \
	cin.tie(NULL)
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
int main()
{
	alphanso;
	int n, k, i, gcd = 0, x, mx = INT_MIN;
	cin >> n >> k;
	for (i = 1; i <= n; i++)
	{
		cin >> x;
		gcd = __gcd(gcd, x);
		mx = max(mx, x);
	}
	if (mx < k)
		cout << "IMPOSSIBLE";
	else
		!(k % gcd) ? cout << "POSSIBLE" : cout << "IMPOSSIBLE";
	return 0;
}

Measured memory_bytes: 3620
#include <iostream>
using namespace std;
 
int a[10];
int n;
 
bool dfs(int i,int left,int right){
    if(i==10) return true;
    if(a[i]>left){
        return dfs(i+1,a[i],right);
    }
    if(a[i]>right){
        return dfs(i+1,left,a[i]);
    }
    return false;
}
 
void solve(){
    for(int i=0;i<10;i++) cin >> a[i];
    if(dfs(0,0,0)) cout << "YES" << endl;
    else cout << "NO" << endl;
    return;
}
 
int main(){
    cin >> n;
    for(int i=0;i<n;i++){
        solve();
    }
    return 0;
}

Measured memory_bytes: 1152
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)

func main() {
	buf := make([]byte, 1024*1024)
	sc.Buffer(buf, bufio.MaxScanTokenSize)
	sc.Split(bufio.ScanWords)
	defer out.Flush()

	var max int
	a, b, c, d := nextInt(), nextInt(), nextInt(), nextInt()

	max = a * c

	ad := a * d
	if max < ad {
		max = ad
	}

	bc := b * c
	if max < bc {
		max = bc
	}

	bd := b * d
	if max < bd {
		max = bd
	}

	fmt.Fprintf(out, "%d\n", max)
}

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}

func nextFloat64() float64 {
	a, _ := strconv.ParseFloat(next(), 64)
	return a
}

func reverse(s string) string {
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return string(runes)
}

func quickSort(val []int) []int {
	if len(val) < 2 {
		return val
	}

	pivot := val[0]

	left := []int{}
	right := []int{}

	for _, v := range val[1:] {
		if pivot > v {
			left = append(left, v)
		} else {
			right = append(right, v)
		}
	}

	left = quickSort(left)
	right = quickSort(right)

	ret := append(left, pivot)
	ret = append(ret, right...)

	return ret
}


Measured memory_bytes: 1808
import kotlin.math.*
import java.util.*

fun main(args: Array<String>) {
  val k = readLine()!!.toInt()
  val q = ArrayDeque<String>()
  (1..9).forEach { q += it.toString() }
  var x = ""
  repeat(k) {
    x = q.remove()
    val y = x.last()
    if (y != '0') q += x + (y - 1)
    q += x + y
    if (y != '9') q += x + (y + 1)
  }
  println(x)
}


Measured memory_bytes: 64952
#abc082 b-two anagrams
s=input()
t=input()
n=min(len(s),len(t))
flag=False
new_s="".join(sorted(s))
new_t="".join(sorted(t)[::-1])
for i in range(n):
    if i==n-1 and new_s[i]==new_t[i] and len(s)<len(t):
        flag=True
    if new_s[i]<new_t[i]:
        flag=True
        break
print("Yes" if flag else "No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll beki[35];
ll sum[35];
int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    ll T;
    cin >> T;
    ll ans = T;
    beki[0] = 1;
    sum[0] = 1;
    for(ll i = 1; i < 35; i++) {
        beki[i] = beki[i - 1] * 3;
        sum[i] = sum[i - 1] + beki[i];
        //cerr << beki[i] << " " << sum[i] << endl;
    }
    for(ll i = 1; i < 34; i++) {
        //cerr << "-----"  << i << "------" << endl;
        ll rest = T - sum[i];
        if(rest < 0) break;
        ll timer = i + 1;
        if(rest < sum[i-1] - 1) continue;
        if(T - sum[i+1] >= sum[i] - 1) continue;
        for(ll j = i; j >= 1; j--) {
            while(rest - beki[j] >= sum[j-1] - 1) {
                timer++;
                rest -= beki[j];
                //cerr << i << " " << j << " " << rest << " " << timer << endl;
            }
        }
        timer += rest;
        //cerr << timer << endl;
        ans = min(ans, timer);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3204
def dfs(v,n,visi,G):
    allv=True

    if False in visi:
        allv=False

    if allv:
        return 1

    ret=0

    for i in range(n):
        if G[v][i]==False:
            continue
        if visi[i]:
            continue
        visi[i]=True
        ret+=dfs(i,n,visi,G)
        visi[i]=False

    return ret

def main():
    ans=0
    n,m=map(int,input().split())
    ab=[list(map(int,input().split()))for i in range(m)]
    G=[[False for i in range(8)]for i in range(8)]
    for a,b in ab:
        G[a-1][b-1]=G[b-1][a-1]=True

    visi=[False for i in range(n)]

    visi[0]=True

    return dfs(0,n,visi,G)

print(main())

Measured memory_bytes: 3064
<?php
fscanf(STDIN,"%s %s", $count, $dust);
for($i = 0; $i < $count; $i++)
{
  fscanf(STDIN,"%s", $donuts[$i]);
  $dust -= $donuts[$i];
}

sort($donuts);

echo(($dust - ($dust % $donuts[0]))/$donuts[0] + $count);

Measured memory_bytes: 3576