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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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




void solve() {
    ll N, K; cin >> N >> K;
    ll cnt = 0, res = 0;
    vector<LP> v(N);
    rep(i, N){
        ll a, b; cin >> a >> b;
        v[i] = make_pair(a, b);
    }
    sort(all(v));
    for(auto p: v){
        cnt += p.second;
        if(cnt >= K){
            res = p.first;
            break;
        }
    }
    cout << res << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


Measured memory_bytes: 5888
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
#include<deque>
using namespace std;

using ll = long long;
const int INF = 1001001001;

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

vector<ll> yakusu(ll n)
{
  vector<ll> ret;

  for (ll i = 1; i * i <= n; i++) { // ルートnまで試す。i <= sqrt(n) だと、右辺が少数になってメンドイ
    if (n % i == 0) {
      ret.push_back(i);
      if (n / i != i) { // ルートnが約数の時は、2つpush_backしないように注意
        ret.push_back(n / i);
      }
    }
  }
  return ret;
}

int main(void)
{
  ll n;
  ll result = 0;
  cin >> n;

  for (ll x : yakusu(n)) {
    if (x == 1) continue;
    ll tmp = n;
    while (tmp % x == 0) {
      tmp /= x;
    }
    if (tmp % x == 1) result++;
  }

  result += yakusu(n-1).size() - 1; // -1は1
  cout << result << endl;
}


Measured memory_bytes: 384
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
#define mem(i,j) memset(i,j,sizeof (i));
#define F first
#define S second
#define lowbit(x) ((x)&(-(x)))
#define siz(v) (int)(v).size()
typedef int64_t ll;
typedef uint64_t ull;
const double EPS  = 1e-8;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
/*-----------------------------------------------------------------------------------------------------*/

signed main() {
	EmiliaMyWife
	
	int cnt[4] = {0};
	string se[4] = {"AC", "WA", "TLE", "RE"};
	int n;
	cin >> n;
	string s;
	for(int i = 0; i < n; i++)
		cin >> s, cnt[find(se, se+4, s)-se]++;
	for(int i = 0; i < 4; i++)
		cout << se[i] << " x " << cnt[i] << '\n';

	return 0;
}


Measured memory_bytes: 3640
//** aman**//
#include<bits/stdc++.h>
#define	MIN(a,b,c)	min(min(a,b),c)
#define	MAX(a,b,c)	max(max(a,b),c)
#define ll          long long
#define itr         vector<int>::iterator
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define mem(a,b) memset(a,b,sizeof(a))
#define sz size()
#define hell        1000000007
#define endl        '\n'
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)
#define Vit std::vector<int>:: iterator
#define Sit std::set<int>:: iterator
#define Mit std::map<int,int>:: iterator
#define lbo lower_bound
#define ub upper_bound
#define bs          binary_search
#define N         100005
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
using namespace std;
vector<int> G[100005],v;
int in[N],vis[N],dp[N]={0};
int main()
{
	int n,m;cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int x,y;cin>>x>>y;
		G[x].pb(y);
		in[y]++;
	}
	queue<int> q;
	for(int i=1;i<=n;i++)
	{
		if(in[i]==0){
		q.push(i);
		dp[i]=0;
		}
	}
	while(!q.empty())
	{
		int p=q.front();
		q.pop();
		for(int i=0;i<G[p].size();i++)
		{
			in[G[p][i]]--;
			if(in[G[p][i]]==0){q.push(G[p][i]);}
            dp[G[p][i]]=max(dp[p]+1,dp[G[p][i]]);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans,dp[i]);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 6528
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String n = scan.next();
		int sum = 0;
		for (int i = 0; i < n.length(); i++) {
			sum += n.charAt(i) - '0';
		}
		if ((Integer.parseInt(n) % sum) == 0) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}


Measured memory_bytes: 21716
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
using namespace std;

int main(){
  int n;
  cin>>n;
  vector<long long> a;
  long long x;
  for(int i=0;i<n;i++) cin>>x,a.push_back(x);
  sort(a.begin(),a.end());
  int ans=0;
  int tmp=1;
  for(int i=0;i<n-1;i++){
    if(a[i]==a[i+1]){
      tmp++;
    }else{
      if(tmp%2!=0) ans++;
      tmp=1;
    }
  }
  if(tmp%2!=0) ans++;
  cout<<ans<<endl;
  return 0;
}


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

using namespace std;

#define REP(i,n) for(ll (i) = (0); (i) < (n); ++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define ALL(v) v.begin(),v.end()
#define INF 1100000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007
#define Decimal fixed << setpresicion(20)
#define SHOWP(x) cerr<<"("<<(x).FI<<", "<<(x).SE<<")"<<endl;
#define SHOWX(x) cerr<<#x<<": "<<x<<endl;
#define SHOWVEC(v, e) REP(i, e) cerr << (v[i]) << ' '; cerr << endl;
#define SHOW2D(a, h, w) REP(i, h){REP(j, w)cerr<<setw(3)<<(a[i][j])<<' ';cerr<<endl;}

typedef long long ll;
typedef pair<ll, ll> P;


ll dp[110][110][500];
int main()
{
  REP(i, 110) REP(j, 110) REP(k, 500) dp[i][j][k] = -1;
  ll N, W;
  cin >> N >> W;
  vector<ll> v(N), w(N);
  REP(i, N) cin >> w[i] >> v[i];

  dp[0][0][0] = 0;
  REP(i, N) {
    REP(j, N) {
      REP(k, 400) {
        dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);
        dp[i + 1][j + 1][k + (w[i] - w[0])] = max(dp[i + 1][j + 1][k + (w[i] - w[0])], dp[i][j][k] + v[i]);
      }
    }
  }

  ll ans = -1;
  REP(i, N + 1) {
    REP(j, 400) {
      if (w[0]*i + j <= W) ans = max(ans, dp[N][i][j]);
    }
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 47488
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> bool cmax(T& a, U b) { if (a<b) {a = b; return true;} else return false; }
template<class T, class U> bool cmin(T& a, U b) { if (a>b) {a = b; return true;} else return false; }

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

  ll n;
  cin >> n;
  vl a(n);
  rep(i, n) {
    cin >> a[i];
  }

  sort(all(a));
  rep(i, n-1) {
    if (a[i] == a[i+1]) {
      cout << "NO" << endl;
      return 0;
    }
  }
      cout << "YES" << endl;
}


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

public class Main {

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

        int sum = solve(n, sn);
        System.out.println(sum);
    }

    public static int solve(int n, int[] sn) {

        // 貪欲したいので昇順ソート
        Arrays.sort(sn);
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += sn[i];
        }

        int div = 0;
        for (int i = 0; i < n; i++) {
            if (sum % 10 != 0) {
                break;
            }

            if (sn[i] % 10 != 0) {
                sum -= sn[i];
            } else {
                div++;
            }
        }

        if (div == sn.length) {
            sum = 0; // 全ての要素が10の倍数
        }
        return sum;
    }
}



Measured memory_bytes: 21844
import java.util.Scanner;

public class Main {
		public static void main(String args[]) {
			Scanner in = new Scanner(System.in);
			int inputNum = in.nextInt();
			System.out.println(getNowShakkin(inputNum));
		}

		public static int getNowShakkin(int weekInterval) {
			double result = 100;

			for (int i = 0; i < weekInterval; i++) {
				result = result + (result * 0.05);
				result = (Math.ceil((double) result));
			}

			return (int)result * 1000;
		}
	}

Measured memory_bytes: 25840
from collections import deque
 
h, w = map(int, input().split())
a = ''.join(input() + '#' for _ in range(h))
n = len(a)
b = ['#'] * w
q = deque()
d = -1, 1, -w - 1, w + 1
r = 0
for i in range(n):
  if a[i] == '.':
    b[:-w] = a
    b[i] = 0
    q.append(i)
    while(q):
      i = q.popleft()
      r = max(r, b[i])
      for j in d:
        j += i
        if b[j] == '.':
          b[j] = b[i] + 1
          q.append(j)
print(r)


Measured memory_bytes: 3316
#include <stdio.h>

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

	scanf("%d %d %d", &a,&b,&c);

	if (a < b){
		if (b < c)
			printf("Yes\n");
	
	else 
		printf("No\n");

	}
	else 
		printf("No\n");

	return 0;
}

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

vector<int> G[2005];
int f(int cent, int par, int len, int depth = 0){  
    int cut = 0;
    if (depth > len)
        ++cut;
    for(int i : G[cent]){
        if (i == par) 
            continue;
        cut += f(i, cent, len, depth + 1);
    }
    
    return cut;
}

int main(){
    int n, k, ans = 2005; cin >> n >> k;
    for (int i = 1; i < n; i++)
    {
        int a, b; cin >> a >> b;
        G[a].emplace_back(b);
        G[b].emplace_back(a);
    }
    if (k % 2 == 0){
        for (int i = 1; i <= n; i++){
            ans = min(ans, f(i, -1, k/2));
        }
    }
    else
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j : G[i]){
                ans = min(ans, f(i, j, k/2) + f(j, i, k/2));
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 512
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

pub fn ceil_div(a: u32, b: u32) -> u32 {
    (a + b - 1) / b
}

fn main() {
    input! {
        n: usize,
        m: u32,
        aa: [u32;n]
    }
    let mut aa = aa;
    aa.sort();
    aa.reverse();
    let s = aa.iter().sum::<u32>();
    let d = ceil_div(s, 4*m);
    let mut possible = true;
    for i in 0..m as usize {
        let a = aa[i];
        if a < d {
            possible = false;
            break;
        }
    }
    println!("{}", if possible {"Yes"} else {"No"});
}


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

using namespace std;
#define sint(a) scanf("%d",&a)
#define sint2(a,b) scanf("%d %d",&a,&b)
#define sll(a) scanf("%lld",&a)
#define sll2(a,b) scanf("%lld %lld",&a,&b)
#define mem(a,i) memset(a,i,sizeof(a))
#define pb push_back
#define ll long long
#define lson node<<1
#define rson (node<<1)+1

const int maxn=2e6+10;
const int mod=998244353;
const double pi=-acos(-1);

int v[maxn];
struct Prime
{
    int prime[maxn];
    int s;
    Prime()
    {
        for(int i=2; i<maxn; i++)
        {
            if(!v[i])
            {
                prime[s++]=i;
                for(int j=2; j*i<maxn; j++)
                    v[i*j]=1;
            }
        }
    }
};
ll a[maxn];
int main()
{
    int n;
    sint(n);
    for(int i=0; i<n; i++)
        sll(a[i]);
    sort(a,a+n);
    ll sum=1;
    ll k=1e18;
    for(int i=0; i<n; i++)
    {
        if(sum==0)
        {
            break;
        }
        if(k/sum<a[i])
        {
            sum=-1;
            break;
        }
        sum*=a[i];
    }
    printf("%lld\n",sum);
//    double a,b;
//    scanf("%lf %lf",&a,&b);
//    printf("%.0f",a*b);

    return 0;
}


Measured memory_bytes: 4608
n=int(input())
h=list(map(int,input().split()))

dp=[0]*n

dp[0]=0
dp[1]=abs(h[0]-h[1])

for i in range(2,n):
    dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]))
print(dp[-1])

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

#define IOS                               \
	ios_base::sync_with_stdio(false); \
	cin.tie(0);                       \
	cout.tie(0);                      \
	cin.exceptions(cin.failbit);
#define int long long int //Comment when Unnecessary
#define ll long long
#define sz(a) (int)((a).size())
#define all(a) a.begin(), a.end()
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define pii pair<int, int>
#define vi vector<int>
#define F first
#define S second
#define endl "\n" // Remove on Interactive

const int N = 300009;
const int mod = 1000000007;

int exp(int a, int b)
{
	if (b == 0)
		return 1;
	int x = exp(a, (b / 2));
	x *= x;
	x %= mod;
	if (b % 2)
		x *= a;
	x %= mod;
	return x;
}

int inverse(int a)
{
	return exp(a, mod - 2);
}

int fac1(int z)
{
	int er = 1;
	rep(i, 1, z + 1)
	{
		er *= i;
		er %= mod;
	}
	return er;
}

int fac(int n, int a)
{
	int er = 1;
	rep(i, (n - a + 1), n + 1)
	{
		er *= i;
		er %= mod;
	}
	er *= inverse(fac1(a));
	er %= mod;
	return er;
}

void pre()
{
}

int32_t main()
{
	IOS;
	pre();
	int n, a, b;
	cin >> n >> a >> b;
	int ans = exp(2, n);
	ans -= 1, ans += mod;
	ans %= mod;
	int fn1 = fac(n, a);
	int fn2 = fac(n, b);
	ans -= (fn1 + fn2);
	ans += (2 * mod);
	ans %= mod;
	cout << ans << endl;
	return 0;
}


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

int main(){
  int n,p,ans,tempp;
  string s,temps;
  cin >> n;
  vector<tuple<string, int, int>> sp;
  rep(i,0,n){
    cin >> s >> p;
    sp.push_back(make_tuple(s,p*(-1),i+1));
  }

  sort(all(sp));

  rep(i,0,n){
    ans= get<2>(sp[i]);
    cout << ans << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<n; i++)
#define pb push_back
#define int long long

int N;
 
signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N;
    int pt = 0, px = 0, py = 0;
    bool flag = true;
    rep(i, N) {
        int t, x, y; cin >> t >> x >> y;
        int d = abs(x-px)+abs(y-py);
        if (d>t-pt) flag = false;
        if (d%2!=(t-pt)%2) flag = false;
        pt = t, px = x, py = y;
    }
    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define FOR(i,a,b)for(int i=(a),_b=(b);i<_b;i++)
#define FORN(i,b,a)for(int i=(b);_a=(a);i>=_a;i--)
#define REP(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define re return
#define vi vector<int>
#define pb push_back
#define si set<int>
#define in insert
#define fl float
#define ld long double
#define X first
#define Y second
#define st string
#define ull unsigned long long
#define mod 1000000007
#define INF 1000000007
#define x1 XZVJDFADSPFOE
#define y1 GASDIJSLDAEJF
#define x2 DFDAJKVOHKWIW
#define y2 PSFSAODSXVNMQ
using namespace std;
inline void read(int &x)
{
	short negative=1;
    x=0;
    char c=getchar();
    while(c<'0' || c>'9')
    {
		if(c=='-')
			negative=-1;
		c=getchar();
	}
    while(c>='0' && c<='9')
        x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=negative;
}
int h,w;
char c[111][111];
int dp[111][111];
int main()
{
	ios::sync_with_stdio(0);
	cin>>h>>w;
	REP(i,h)
		REP(j,w)
			cin>>c[i][j];
	REP(i,h)
		REP(j,w)
			dp[i][j]=111111;
	dp[h-1][w-1]=(c[h-1][w-1]=='#');
	for(int i=h-1;i>=0;i--)
		for(int j=w-1;j>=0;j--)
			if(c[i][j]=='.')
			{
				if(i<h-1)dp[i][j]=min(dp[i][j],dp[i+1][j]);
				if(j<w-1)dp[i][j]=min(dp[i][j],dp[i][j+1]);
			 } 
			else 
			{
				if(i<h-1)dp[i][j]=min(dp[i][j],dp[i+1][j]+(c[i+1][j]=='.'));
				if(j<w-1)dp[i][j]=min(dp[i][j],dp[i][j+1]+(c[i][j+1]=='.'));
			}
	cout<<dp[0][0]<<endl;
	return 0;
}

/*
3 3
.##
.#.
##.
*/


Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <cstdio>
#include <string>

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

const int MAX_N = 45;
int N;
int X, Y, Z;

const int J = 1 << 17;

int dp[MAX_N][J];

signed main()
{
    cin >> N >> X >> Y >> Z;

    dp[0][0] = 1;
    int L = (1 << (X-1)) | (1 << (X+Y-1)) | (1 << (X+Y+Z-1));

    for(int i = 0; i < N; i++) {
        for(int bit = 0; bit < J; bit++) {
            if(dp[i][bit] == 0) {
                continue;
            }

            for(int num = 1; num <= 10; num++) {
                int nextBit = (bit << num) | (1<<(num-1)); nextBit &= J-1;
                if ((nextBit & L) != L) (dp[i+1][nextBit] += dp[i][bit]) %= MOD;
            }
        }
    }

    int ans = 1;
    for(int i = 0; i < N; i++) {
        ans *= 10;
        ans %= MOD;
    }

    int tmp = 0;
    for(int bit = 0; bit < J; bit++) {
        tmp += dp[N][bit];
        tmp %= MOD;
    }

    cout << (ans + MOD - tmp) % MOD << endl;

    return 0;
}

Measured memory_bytes: 41216
#include<iostream>

using namespace std;

int main(){
  long long int n,sm=0,mn=2e15,a[200009];
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> a[i];
    sm+=a[i];
  }
  long long lsm=0;
  for(int i=0;i<n-1;i++){
    lsm+=a[i];
    sm-=a[i];
    mn = min(mn , abs(lsm-sm));
  }
  cout << mn << endl;
}

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

int main() {
  int N, A, B;
  string S;
  cin >> N >> A >> B;
  cin >> S;
  int pass = 0;
  int passb = 0;
  for(int i = 0; i < S.length(); i++) {
    if(S[i] == 'c') cout << "No" << endl;
    else {
      if(S[i] == 'a' && pass < (A + B)) {
        pass++;
        cout << "Yes" << endl;
      } else if(S[i] == 'b' && pass < (A + B) && passb < B) {
        pass++;
        passb++;
        cout << "Yes" << endl;
      } else {
        cout << "No" << endl;
      }
    }
  }
  return 0;
}

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

int arr[100001];
int n,k;

int dp[100001];

int main(){
    cin>>n;
    cin>>k;
    for(int i=0; i<n; i++){
        cin>>arr[i];
        dp[i] = INT_MAX;
    }
    dp[0]=0;

    for(int i=0; i<n; i++){
        for(int j=1; j<=k; j++){
            if(i+j < n ){
                dp[i+j] = min(dp[i+j], dp[i] + min(dp[i+j], abs(arr[i+j]-arr[i])));
            }
        }
    }

    cout<<dp[n-1]<<endl;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <algorithm>
using namespace std;
#define fr first.first
#define se first.second
#define tr second
#define N 2050
#define pr pair<pair<int,int>,int>
int n,m,i,j,a[N][N],b[N][N],l[N][N],r[N][N],id;
bool vis[N][N];
pr c[N*N];
int main()
{
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)
	for (j=1;j<=m;j++){
		char ch=getchar();
		while (ch!='.' && ch!='#') ch=getchar();
		a[i][j]=(ch=='.');
	}
	for (i=1;i<n;i++)
	for (j=1;j<=m;j++){
		a[i][j]^=a[i+1][j];
		if (a[i][j]==a[i][j-1]) b[i][j]=b[i][j-1]+1;
		else b[i][j]=1;
		c[++id].fr=b[i][j];c[id].se=i;c[id].tr=j;
	}sort(c+1,c+id+1);int ans=max(n,m);
	for (i=id;i>=1;i--){
		int x=c[i].se,y=c[i].tr;vis[x][y]=true;
		if (vis[x-1][y]&&vis[x+1][y]){
			l[x][y]=l[x-1][y];r[x][y]=r[x+1][y];
			l[r[x][y]][y]=l[x][y];r[l[x][y]][y]=r[x][y];
			ans=max(ans,c[i].fr*(r[x][y]-l[x][y]+2));
		}else if (vis[x-1][y]){
			l[x][y]=l[x-1][y];r[x][y]=x;
			l[r[x][y]][y]=l[x][y];r[l[x][y]][y]=r[x][y];
			ans=max(ans,c[i].fr*(r[x][y]-l[x][y]+2));
		}else if (vis[x+1][y]){
			l[x][y]=x;r[x][y]=r[x+1][y];
			l[r[x][y]][y]=l[x][y];r[l[x][y]][y]=r[x][y];
			ans=max(ans,c[i].fr*(r[x][y]-l[x][y]+2));
		}else l[x][y]=r[x][y]=x,ans=max(ans,c[i].fr*2);
	}printf("%d\n",ans);
	return 0;
}

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

vector<int> IntegerToVector(int bit, int N) {
    vector<int> S;
    for (int i = 0; i < N; ++i) {
        if (bit & (1 << i)) {
            S.push_back(i);
        }
    }
    return S;
}

vector<vector<char>> DrawField(vector<vector<char>> field, vector<int> h_list, vector<int> w_list,int H,int W,int K){
    vector<vector<char>> ans_field(H,vector<char>(W));
    ans_field = field;
    for(auto h:h_list){
        for(int i=0;i<W;i++){
            ans_field[h][i] = 'A';
        }
    }
    for(auto w:w_list){
        for(int i=0;i<H;i++){
            ans_field[i][w] = 'A';
        }
    }
    
    // for(int i=0;i < H ; ++i){
    //     for(int j =0;j<W;++j){
    //         cout<<ans_field[i][j];
    //     }
    //     cout<<" "<<endl;
    // }    
    
    return ans_field;
}

int Count_kuro(vector<vector<char>> field,int H,int W,int K){
    int cnt = 0;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(field[i][j]=='#') cnt++;
        }
    }
    if(cnt==K) return 1;
    else return 0;
}

int H,W,K;
int main(void){

    cin>>H>>W>>K;
    
    vector<vector<char>> field(H,vector<char>(W));
    for(int i=0;i < H ; ++i){
        for(int j =0;j<W;++j){
            cin>>field[i][j];
        }
    }
    
    vector<int> h_list;
    vector<int> w_list;
    int sum =0;
    for(int h_bit = 0; h_bit<(1<<H);h_bit++){
        vector<int> h_list = IntegerToVector(h_bit,H);
        for(int w_bit = 0; w_bit<(1<<W);w_bit++){
            w_list = IntegerToVector(w_bit,W);
        
            vector<vector<char>> a(H,vector<char>(W));
            a = DrawField(field,h_list,w_list,H,W,K);
            sum += Count_kuro(a,H,W,K);
        }
    }
    cout<<sum<<endl;
}


Measured memory_bytes: 3640
// Unfair NIM  Longqiang 2020-07-27
#include <iostream>
using namespace std;

#define LL long long

LL n, arr[305];

int main(){
	cin>>n;
	for(int i=1; i<=n; i++) cin>>arr[i];
	
	LL x = 0;
	for(int i=3; i<=n; i++) x ^= arr[i];
	
	//存在这样的等式： arr[1]+arr[2] = arr[1]^arr[2] + 2*arr[1]&arr[2]
	//可以这样认为：两个数相加，可以分解为两部分，一部分是不带进位的相加（异或），另一部分是负责进位
	LL sum = arr[1] + arr[2];
	LL first_part = x;
	LL second_part = sum - x;
	
	if(second_part<0 || second_part%2){ //如果第二部分是奇数，那就不可能存在方案
		cout<<"-1";
		return 0;
	}
	
	//设最后 第一堆数量为a，第二堆为b, 则必须满足如下几个条件：
	//1. a&b的结果必须是second_part/2
	//2. a^b = first_part
	//3. 0<a<=a[1]
	// a=b=second_part/2 能满足前两个条件，我们要寻找出所有可能值中最大的a,
	// 将first_part中数位上为1的这些数值按贪心策略相应地分配到a或b中，即可得出答案
	LL a_and_b = second_part/2;
	LL a = a_and_b;
	LL b = a_and_b;
	
	for(int i=60; i>=0; i--){ //从最高位开始取
		if(first_part & (1ll<<i)){
			if(a_and_b & (1ll<<i)) { //这两者的同一个数位上不应该同时为1,否则不存在方案
				cout<<"-1";
				return 0;
			}
			if((a + (1ll<<i)) <= arr[1]) a += (1ll<<i); //贪心策略,应让a尽可能大
			else b+=(1ll<<i);
		}
	}

	if(a<=0 || b>=sum || a>arr[1]) cout<<"-1";
	else cout<<arr[1] - a;

	return 0;
}

Measured memory_bytes: 3096
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int h =0;
		int count = 0;
		for(int i= 0;i<N; ++i) {
			h = sc.nextInt();
			if( h >= K) {
				count++;
			}
		}
		
		System.out.println(count);

	}
}


Measured memory_bytes: 47368
#include <stdio.h>
#define max 2000000
int a[max+1],b[max+1],c[max+1];
main(){
   
  int n,i,j,k;
  scanf("%d",&n);
  for(i=0; i<n; i++){
    scanf("%d",&a[i+1]);
  }
   
  for(i=0; i<n; i++){
    c[a[i+1]]++;
  }
  for(i=0; i<max; i++){
    c[i+1]=c[i+1]+c[i];
  }
  for(i=n;i>0;i--){
    b[c[a[i]]]=a[i];
    c[a[i]]--;
  }
  for(i=0;i<n-1;i++){
    printf("%d ",b[i+1]);
  }
  printf("%d\n",b[n]);

  return 0;
}

Measured memory_bytes: 24036
package main

import "fmt"

func main() {
	var n, k int
	fmt.Scan(&n)
	fmt.Scan(&k)

	c := make([]int, n, n)

	for i := 1; i <= k; i++ {
		var d int
		fmt.Scan(&d)
		for j := 1; j <= d; j++ {
			var a int
			fmt.Scan(&a)
			c[a-1]++
		}
	}

	answer := 0
	for i := 0; i < n; i++ {
		if c[i] == 0 {
			answer++
		}
	}
	fmt.Println(answer)
}


Measured memory_bytes: 2452
n = int(input())
A = list(map(int, input().split()))
q = int(input())
B,C = [], []

for _ in range(q):
    b, c = list(map(int, input().split()))
    B.append(b)
    C.append(c)

ans = sum(A)

d = {}
for a in A:
    d.setdefault(a, 0)
    d[a] += 1

for b, c in zip(B,C):
    d.setdefault(b, 0)
    d.setdefault(c, 0)
    ans -= d[c] * c
    ans -= d[b] * b
    d[c] += d[b]
    d[b] = 0
    ans += d[c] * c
    ans += d[b] * b
    print(ans)


Measured memory_bytes: 30100
n,m = map(int,input().split())
A = set([int(input()) for i in range(m)])
mod = 10**9+7

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

for i in range(2,n+2):
    if i-1 not in A:
        dp[i]=dp[i-1]%mod+dp[i-2]%mod
print(dp[n+1]%mod)

Measured memory_bytes: 18904
n, k, q = map(int, input().split())
a = list(int(input()) for i in range(q))
m = []

for i in range(n):
    m.append(k-q)

for j in a:
    m[j-1] += 1

for k in m:
    if k <= 0:
        print('No')
    else:
        print('Yes')


Measured memory_bytes: 11788
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <queue>
#include <thread>
#include<bits/extc++.h>

using namespace __gnu_pbds;
#pragma GCC optimize("Ofast")

#define ll long long

#define gc (c = getchar())
#define gi(x) scanf("%d", &x)
#define gid(x, y) scanf("%d%d", &x, &y)
#define gll(x) scanf("%lld", &x)
#define glld(x, y) scanf("%lld%lld", &x, &y)
#define gllt(x, y, z) scanf("%lld%lld%lld", &x, &y, &z)
#define git(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define pi(x) printf("%d\n", x)
#define pr(x) return !(printf("%lld\n", (long long)(x)))
#define pcs(ch, cs, x) printf("Case %c%d: %d\n", ch, cs, x)
#define pllcs(ch, cs, x) printf("Case %c%d: %lld\n", ch, cs, x)
#define pcsyn(ch, cs, st) printf("Case %c%d: %s\n", ch, cs, (st) ? "Yes" : "No")
#define pyn(st) printf("%s\n", (st) ? "yes" : "no")
#define pryn(st) return !(printf("%s\n", (st) ? "YES" : "NO"))
#define pll(x) printf("%lld\n", x)
#define plld(x, y) printf("%lld %lld\n", x, y)

#define mp(x, y) std::make_pair(x, y)
#define fcs(x) while (x--)
#define dbg(x) std::cerr << #x << " " << x << std::endl
#define fi freopen("in.txt", "r", stdin)
#define fo freopen("out.txt", "w", stdout)
#define siz(x) (int)x.size()
#define pb(x) push_back(x)

inline long long max(long long x, long long y) { return x > y ? x : y; }

inline long long min(long long x, long long y) { return x > y ? y : x; }

long long gcd(long long x, long long y) { return y == 0 ? x : gcd(y, x % y); }


const int maxn = 2e5 + 5;
long long seq[maxn];
const long long mod = 1e9 + 7;
int main(){
    int n;
    gi(n);
    for (int i = 1; i <= n; ++ i) gll(seq[i]);
    long long sum = 0, ret = 0;
    for (int i = n; i >= 1; -- i){
        ret = (ret + sum * seq[i]) % mod;
        sum = (sum + seq[i]) % mod;
    }
    pll(ret);
} 

Measured memory_bytes: 5384
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define f(i,x,n) for(int i=x;i<n;i++)
#define all(c) c.begin(),c.end()
#define print(x) cerr << (#x) << "is "<< x << "\n"
using ll = long long;
using pii = pair<int,int>;
const int MOD = 1e9+7, N = 1e5 + 10;
 
int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	ll n;
	ll s = 0;
	cin >> n;
	vector<ll> a(n+1),b(n);
	f(i,0,n+1){
		cin >> a[i];
		s += a[i];
	}
	f(i,0,n) cin >> b[i];
	for(int i = n-1;i>=0;i--){
		ll kk = min(a[i+1],b[i]);
		a[i+1] -= kk;
		b[i] -= kk;
		kk = min(a[i],b[i]);
		a[i] -= kk;
		b[i] -= kk;
	}
	f(i,0,n+1){
		s -= a[i];
	}
	cout << s << '\n';
	return 0;
} 

Measured memory_bytes: 1792
from math import pi
from math import cos

A,B,H,M=map(int,input().split())
ang_vel=[2*pi/(12*60), 2*pi/60]
minutes=H*60+M
ang1=ang_vel[0]*minutes
ang2=ang_vel[1]*M
theta=abs(ang1-ang2)

ans=(A**2+B**2-2*A*B*cos(theta))**0.5
print(ans)

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

int main() {
  int N, K;
  cin >> N >> K;
  
  vector<ll> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  
  vector<ll> s(N + 1);
  s.at(0) = 0;
  for (int i = 0; i < N; i++) s.at(i + 1) = s.at(i) + A.at(i);
  for (int i = 0; i <= N; i++) s.at(i) = (s.at(i) - i) % K;
  
  map<ll, ll> m;
  ll ans = 0;
  for (int i = 0; i <= N; i++) {
    m[s.at(i)]++;
    if (i >= K) m[s.at(i - K)]--;
    ans += m[s.at(i)] - 1;
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 15872
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define DEBUGP(val) cerr << #val << "=" << val << "\n"

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
const ll mod = 998244353;

ll powmod(ll a, ll e) {
  ll sum = 1;
  ll cur = a;
  while (e > 0) {
    if (e % 2) {
      sum = sum * cur % mod;
    }
    cur = cur * cur % mod;
    e /= 2;
  }
  return sum;
}
void add(ll &x, ll y) {
  x = (x + y) % mod;
}


const int N = 300100;
ll fac[N], invfac[N];
void init(void) {
  fac[0] = 1;
  REP(i, 1, N) fac[i] = fac[i - 1] * i % mod;
  invfac[N - 1] = powmod(fac[N - 1], mod - 2);
  for (int i = N - 2; i >= 0; --i) invfac[i] = invfac[i + 1] * (i + 1) % mod;
}

int main(void) {
  init();
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n, a, b, k;
  cin >> n >> a >> b >> k;
  ll tot = 0;
  REP(x, 0, n + 1) {
    ll rem = k - a * x;
    if (rem >= 0 && rem % b == 0) {
      ll y = rem / b;
      if (y <= n) {
        ll tmp = fac[n] * fac[n] % mod;
        tmp = tmp * (invfac[x] * invfac[n - x] % mod) % mod;
        tmp = tmp * (invfac[y] * invfac[n - y] % mod) % mod;
        add(tot, tmp);
      }
    }
  }
  cout << tot << endl;
}


Measured memory_bytes: 4992
use proconio::{fastout, input};
#[allow(unused_mut)]
#[fastout]
fn main() {
    input! {
        n: usize, m: usize,
        a: [String; n],
        b: [String; m]
    }
    let a = a.iter().map(|s| s.chars().collect()).collect();
    let b = b.iter().map(|s| s.chars().collect()).collect();
    let mut res = false;
    let diff = n - m;
    for x in 0..=diff {
        for y in 0..=diff {
            if check(x, y, &a, &b) {
                res = true;
            }
        }
    }
    println!("{}", if res { "Yes" } else { "No" })
}

fn check(sx: usize, sy: usize, a: &Vec<Vec<char>>, b: &Vec<Vec<char>>) -> bool {
    let m = b.len();
    for x in sx..sx + m {
        for y in sy..sy + m {
            if a[y][x] != b[y - sy][x - sx] {
                return false;
            }
        }
    }
    true
}


Measured memory_bytes: 2148
#include <bits/stdc++.h>
#define FOR(i, c) for (int i = 0; i < c; i++)
#define MOD 1000000007
using namespace std;

bool hp(string s, int l, int h) {
  for (; l < h; l++,h--) {
    if (s[l] != s[h]) return false;
  }
  return true;
}
int main() {
  string s;
  cin >> s;
  int n = s.size();
  bool res = hp(s, 0, n-1) && hp(s, 0, (n-1)/2-1) && hp(s, (n+3)/2-1, n-1);
  cout << (res ? "Yes" : "No") << endl;
  return 0;
}




Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
vector<int> adj[5];
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	for(int i=0;i<3;i++){
		int a,b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for(int i=0;i<4;i++){
		if(adj[i+1].size() > 2){
			cout << "NO\n";
			return 0;
		}
	}
	cout << "YES\n";
	return 0;
}

Measured memory_bytes: 256
////////////////////////// Author
////////////////////////// Nasim Hossain Rabbi
////////////////////////// JU-CSE28
////////////////////////// CF - imnasim3.1415
////////////////////////// UVA - imnasim3.1415
////////////////////////// Mail - imnasim3.1415@gmail.com
#include<bits/stdc++.h>
using namespace std;
#define E end()
#define B begin()
#define sz size()
#define EM empty()
#define clr clear()
#define sqr(a) (a*a)
#define mk make_pair
#define pb push_back
string en="\n";
string t="hello";
#define rep(i,n) for(i=0;i<n;i++)
#define Rep(i,n) for(i=1;i<=n;i++)
#define per(i,n) for(i=n-1;i>=0;i--)
#define peR(i,n) for(i=n;i>0;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define all(cont) cont.begin(),cont.end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
#define pi 3.1415926535897932384626433832795
#define vi vector<int>
#define vl vector<long long>
#define vs vector<string>
#define vp(vi,x) cin>>x; vi.pb(x);
#define srch(a,x) binary_search(all(a),x)
#define LB(a,x) (lower_bound(all(a),x)-a.B)
#define UB(a,x) (upper_bound(all(a),x)-a.B)
typedef long long LL;
typedef unsigned long long ULL;
bool isprm(LL a){for(LL i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
bool isVowel(char ch){ ch=toupper(ch); if(ch=='A'||ch=='U'||ch=='I'||ch=='O'||ch=='E') return true; return false;}
int toInt(string s){int sm;stringstream ss(s);ss>>sm;return sm;}
template<typename T>inline T gcd(T a,T b){if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<typename T>inline T lcm(T a,T b) {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}
int main()
{
//    fast;
    LL i,j,k,n,m,l,s=0,x,y,tc=1,c=0;
    while(cin>>i>>j>>k)
    {
        cout<<k<<" "<<i<<" "<<j<<en;
    }
}




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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pll> vpl;

#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define yes cout<<"Yes"<<endl
#define YES cout<<"YES"<<endl
#define no cout<<"No"<<endl
#define NO cout<<"NO"<<endl
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

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

  ll n;
  cin>>n;
  vll a(n);
  REP(i,n)cin>>a[i];

  ll dp[2][n+1][2];
  REP(i,2)REP(j,n+1)REP(k,2)dp[i][j][k]=0;

  REP(i,n/2){
    dp[0][i+1][0]=dp[0][i][0]+a[i*2];
    dp[0][i+1][1]=max(dp[0][i][0],dp[0][i][1])+a[i*2+1];

    if(i!=0){
      dp[1][i+1][0]=max(max(dp[0][i][0],dp[0][i][1]),
          dp[1][i][0]+a[i*2]);
      dp[1][i+1][1]=max(max(dp[0][i][0],dp[0][i][1]),
          max(dp[1][i][0],dp[1][i][1])+a[i*2+1]);
    }
  }

  ll ans=max(dp[0][n/2][0],dp[0][n/2][1]);
  if(n%2==1)
    ans=max(ans,dp[1][n/2][0]+a[n-1]);


  cout<<ans<<endl;
}



Measured memory_bytes: 11096
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<'\n';
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int p,q,r;
    cin>>p>>q>>r;
    cout<<p+q+r-max(max(p,q),r)<<endl;
}

Measured memory_bytes: 256
<?php

fscanf(STDIN, "%d %d", $k, $s);
$cnt = 0;
for ($x = 0; $x <= $k; $x++) {
    for ($y = 0; $y <= $k; $y++) {
        
        $z = $s-$x-$y;
        
        if(($z>=0)&&($z<=$k)){
             $cnt++;
        }
    }
}

    echo $cnt;

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

using namespace std;

const int maxn = 1e2+10, maxv = 1e5+10, inf = 1e18+10;

int n, v[maxn], w[maxn];

long long dp[maxn][maxv], ww;

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

    cin >> n >> ww;

    for(int i=1; i<=n; i++){
        cin >> w[i] >> v[i];
    }

    for(int i=0; i<maxn; i++){
        dp[i][0] = 0;
        for(int j=1; j<maxv; j++){
            dp[i][j] = inf;
        }
    }

    for(int i=1; i<=n; i++){
        for(int j=1; j<maxv; j++){
            dp[i][j] = dp[i-1][j];
            if(v[i]<=j) dp[i][j] = min(dp[i][j], w[i] + dp[i-1][j-v[i]]);
        }
    }

    int ans = 0;

    for(int i=1; i<maxv; i++) if(dp[n][i]<=ww) ans = i;

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 86272
#include <bits/stdc++.h>
#define endl '\n'
#define debug(X) cout << #X << " = " << X << endl

using namespace std;

typedef long long ll;
typedef tuple<ll, int, int, int> ST;

const int MN = 1010;

ll a[MN], b[MN], c[MN];

ST f(int i, int j, int k) {
    return ST(a[i] + b[j] + c[k], i, j, k);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	#ifdef UTP
	freopen("input.txt", "r", stdin);
	#endif
	int x, y, z, r; cin >> x >> y >> z >> r;
	for (int i = 0; i < x; i++) cin >> a[i];
	for (int i = 0; i < y; i++) cin >> b[i];
	for (int i = 0; i < z; i++) cin >> c[i];
	sort(a, a + x); sort(b, b + y); sort(c, c + z);
	set<ST> vis;
	priority_queue<ST> pq; pq.push(f(x - 1, y - 1, z - 1));
	while (r > 0) {
		ST curr = pq.top(); pq.pop();
		ll val;
		int i, j, k;
		tie(val, i, j, k) = curr;
		// cout << i << " " << j << " " << k << endl;
		if (vis.count(curr)) continue;
		vis.insert(curr);
		// cout << a[i] << " " << b[j] << " " << c[k] << endl;
		cout << val << endl;
		if (i > 0) pq.push(f(i - 1, j, k));
		if (j > 0) pq.push(f(i, j - 1, k));
		if (k > 0) pq.push(f(i, j, k - 1));
		r--;
	}
	return 0;
}


Measured memory_bytes: 640
package main

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

func main() {

	//input := "1 3 2"
	//scanner := bufio.NewScanner(strings.NewReader(input))
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	nums := []int{0, 0, 0}
	x := 0
	for scanner.Scan() {
		i, _ := strconv.Atoi(scanner.Text())
		nums[x] = i
		x++
	}
	//fmt.Println(nums)
	if nums[2] >= nums[0] && nums[2] <= nums[1] {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>

using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

int main() {

	int N;
	cin >> N;
	vector<pair<int, int>>a(N);

	rep(i, N)
		cin >> a[i].second >> a[i].first;

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

	int now = 0;
	bool flag = true;
	rep(i, N) {
		now += a[i].second;
		if (now > a[i].first) {
			flag = false;
			break;
		}
	}

	flag ? cout << "Yes" : cout << "No";
	cout << endl;

	return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<string>
using namespace std;
int main(){
long n,i;
string s;
while(cin>>n){
if(n==-1)break;
s="";

for(i=0;;i++){
s+=n%4+48;
n/=4;
if(n==0)break;
}
for(i=s.size()-1;i>=0;i--)cout<<s[i];
cout<<endl;
}
return 0;
}

Measured memory_bytes: 1188
def main():
    from itertools import product
    import numpy as np

    H,W,K = map(int, input().split())
    S = (np.array([list(map(int,list(input()))) for _ in range(H)]).T).tolist()

    if sum(sum(s) for s in S)<=K:
        print(0)
    else:
        answer = (H-1) * (W-1)
        for X in product([False,True], repeat=H-1):
            ans = np.sum(X)
            if ans >= answer:
                continue
            M = [[0]]
            for i, x in enumerate(X):
                if x:
                    M.append([])
                M[-1].append(i+1)
            D = [0]*len(M)
            for s in S:
                for k, m in enumerate(M):
                    D[k] += sum(s[i] for i in m)
                if any(d > K  for d in D):
                    ans += 1
                    if ans >= answer:
                        break
                    for k, m in enumerate(M):
                        D[k] = sum(s[i] for i in m)
                    
                    if any(d > K for d in D):
                        ans = answer + 1
                        break

            answer = min(answer,ans)

        print(answer)

main()

Measured memory_bytes: 12496
alph = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L',
        'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']

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

new = ""
for s in S:
    idx = alph.index(s)
    new += alph[N - (len(alph) - idx)]
print(new)


Measured memory_bytes: 3060
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<sstream>
#include<stack>
#include<string>
#include<unordered_set>
#include<vector>

#define ll long long
#define P pair<int,int>
#define FOR(i,N) for(int i=0;i<(int)N;i++)
#define FORIN(i,a,b) for(int i=a;i<(int)b;i++)
#define ALL(x) (x).begin(),(x).end()
#define LAST(x) (x)[(x).size()-1]
#define GI(name) int (name);scanf("%d",&(name))
#define GI2(name1,name2) int (name1),(name2);scanf("%d %d",&(name1),&(name2))
#define GI3(name1,name2,name3) int (name1),(name2),(name3);scanf("%d %d %d",&(name1),&(name2),&(name3))
#define GVI(name,size) vector<int> (name)(size);FOR(i,(size))scanf("%d",&(name)[i])
#define MOD 1000000007

using namespace std;

string to_hex(int x){
    stringstream ss;
    ss<<hex<<x;
    return ss.str();
}

inline int get_int(){
    int ret;
    scanf("%d",&ret);
    return ret;
}

inline vector<int> get_ints(int n){
    vector<int> ret(n);
    FOR(i,n){
        scanf("%d",&ret[i]);
    }
    return ret;
}

inline string get_str(){
    string ret;
    cin>>ret;
    return ret;
}

bool is_prime(int n){
    int s=sqrt(n)+1;
    for(int i=2;i<=s;++i){
        if(n%i==0){
            return 0;
        }
    }
    return 1;
}

vector<P> prime_division(int n){
    vector<P> ret;
    int s=sqrt(n)+1;
    int c=0;
    for(int i=2;i<=n;++i){
        if(n%i==0){
            c=0;
            do{
                ++c;
                n/=i;
            }while(n%i==0);
            ret.push_back(P(i,c));
        }
    }
    return ret;
}

struct UnionFind{
    vector<int> data;
    UnionFind(int size){
        data=vector<int>(size,-1);
    }
    bool union_set(int x,int y){
        x=root(x);
        y=root(y);
        if(x!=y){
            if(data[y]<data[x])swap(x,y);
            data[x]+=data[y];
            data[y]=x;
        }
        return x!=y;
    }
    bool find(int x,int y){
        return root(x)==root(y);
    }
    int root(int x){
        return data[x]<0?x:data[x]=root(data[x]);
    }
    int size(int x){
        return -data[root(x)];
    }
};

string to_string(string s){
    return s;
}

template<class T>
string to_string(vector<T> v){
    string ret="{";
    FOR(i,v.size()-1){
        ret+=to_string(v[i])+",";
    }
    if(v.size()>0){
        ret+=to_string(LAST(v));
    }
    ret+="}";
    return ret;
}

void debug_print(){
    cerr<<endl;
}

template<class Head,class... Tail>
void debug_print(Head head,Tail... tail){
    cerr<<to_string(head)<<" ";
    debug_print(tail...);
}

template<class... T>
void debug(T... args){
    cerr<<"["<<__LINE__<<"]: ";
    debug_print(args...);
}

void print(){
    cout<<endl;
}

template<class Head,class... Tail>
void print(Head head,Tail... tail){
    cout<<to_string(head);
    print(tail...);
}

int main(){
    GI2(N,M);
    GVI(p,N);
    UnionFind uf(N);
    FOR(i,M){
        GI2(x,y);
        uf.union_set(x-1,y-1);
    }
    int ans=0;
    FOR(i,N){
        if(uf.find(i,p[i]-1))ans++;
    }
    print(ans);
    return 0;
}

Measured memory_bytes: 1024
N, K = map(int, input().split())
MOD = 10**9+7
cnt = [0]*(K+1)
ans = 0

for i in range(K, 1, -1):
    cnt[i] = pow(K//i, N, MOD)
    
    for j in range(2*i, K+1, i):
        cnt[i] -= cnt[j]
        cnt[i] %= MOD
    
    ans += i*cnt[i]

ans += pow(K, N, MOD)-sum(cnt[2:])
ans %= MOD

print(ans)

Measured memory_bytes: 69908