akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int Q = sc.nextInt();
		long[] s = new long[A + 2];
		long[] t = new long[B + 2];
		long[] x = new long[Q];
		for(int i = 1; i <= A; i++) {
			s[i] = sc.nextLong();
		}
		for(int i = 1; i <= B; i++) {
			t[i] = sc.nextLong();
		}
		for(int i = 0; i < Q; i++) {
			x[i] = sc.nextLong();
		}
		sc.close();
		long INF = (long)(Math.pow(10, 11));
		s[0] = t[0] = -INF;
		s[A + 1] = t[B + 1] = INF;
		for(int i = 0; i < Q; i++) {
			int a = bs(s, x[i]);
			int b = bs(t, x[i]);
			long m0 = Math.min(s[a - 1], t[b - 1]);
			long m1 = Math.max(s[a], t[b]);
			long l = Long.MAX_VALUE;
			l = Math.min(l, 2 * (x[i] - s[a - 1]) + t[b] - x[i]);
			l = Math.min(l, 2 * (s[a] - x[i]) + x[i] - t[b - 1]);
			l = Math.min(l, 2 * (x[i] - t[b - 1]) + s[a] - x[i]);
			l = Math.min(l, 2 * (t[b] - x[i]) + x[i] - s[a - 1]);
			l = Math.min(l, x[i] - m0);
			l = Math.min(l, m1 - x[i]);
			System.out.println(l);
		}

	}
	static int bs(long[] a, long k) {
		int l = -1;
		int r = a.length;
		while(r - l > 1) {
			int mid = (r + l) / 2;
			if(a[mid] >= k) {
				r = mid;
			}else {
				l = mid;
			}
		}
		return r;
	}
}

Measured memory_bytes: 97704
#include<stdio.h>
#include<math.h>
int main()
{
	int a,b,c,s,ar;
	scanf("%d%d%d",&a,&b,&c);
	s=(a+b+c)/2;
	ar=sqrt(s*(s-a)*(s-b)*(s-c));
	printf("%d\n",ar);
	return 0;
}

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

int main() {
  int y, m, d;
  int meiji = 1868*365 + 9*31 + 8;
  int taisho = 1912*365 + 7*31 + 30;
  int showa = 1926*365 + 12*31 + 25;
  int heisei = 1989*365 + 1*31+ 8;

  while(cin >> y >> m >> d) {
    int sum = y*365 + m*31 + d;
    
    if(sum < meiji) {
      cout << "pre-meiji" << endl;
    }
    else if(sum < taisho) {
      cout << "meiji " << y-1867 << ' ' << m << ' ' << d << endl;
    }
    else if(sum < showa) {
      cout << "taisho " << y-1911 << ' ' << m << ' ' << d << endl;
    }
    else if(sum < heisei) {
      cout << "showa " << y-1925 << ' ' << m << ' ' << d << endl;
    }
    else {
      cout << "heisei " << y-1988 << ' ' << m << ' ' << d << endl;
    }
  }
}

Measured memory_bytes: 1164
#include<bits/stdc++.h>
#define l(x)std::lower_bound(B,B+*a,x-A)
int a[2<<18],B[1<<18],s,A,i=1,j,L;main(){for(;std::cin>>a[A++];);for(;i<1<<29;i*=2){for(;j++<*a;)B[j-1]=a[j+*a]%(i*2);for(std::sort(B,B+*a);--j;s^=(a[j]&i?*a-L:L)%2*i)A=a[j]%i,L=l(i*2)-l(i);}std::cout<<s;}

Measured memory_bytes: 2560
#include <stdio.h>
#include <string.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))

#define bit(n,m)((n>>m)&1)
int main(){
	char a,b,c,d;
	scanf("%c%c%c%c",&a,&b,&c,&d);
	rep(i,0,8){
		ll ans=a-48;
		ans+=bit(i,0)?b-48:48-b;
		ans+=bit(i,1)?c-48:48-c;
		ans+=bit(i,2)?d-48:48-d;
		if(ans==7){
			printf("%c%c%c%c%c%c%c=7",a,bit(i,0)?'+':'-',b,bit(i,1)?'+':'-',c,bit(i,2)?'+':'-',d);
			return 0;
		}
	}
}

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

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define AND(x,y,z) 
#define DUMP(xs) for (auto x:xs) cout<<x<<' ';cout<<endl
#define DUMPP(xs) for (auto x:xs) cout<<'('<<x.first<<','<<x.second<<')';cout<<endl
#define FOR(i,a,b) for (ll i=(ll)(a);i<(ll)(b);++i)
#define OUT(x) cout<<x<<endl
#define REP(i,n) FOR(i,0,n)
#define YES(cond) cond ? OUT("YES") : OUT("NO")
#define Yes(cond) cond ? OUT("Yes") : OUT("No")

template<class T> T gcd(const T x,const T y){if(!y){return x;}return gcd(y,x%y);}
template<class T> T lcm(const T x,const T y){return x/gcd(x,y)*y;};
template<class T> T modpow(const T x,const T n,const T mod) {
  T res=1;while(n>0){if(n%2)res=res*x%mod;x=x*x%mod;n/=2;};return res;
}
template<class T> bool alltrue(const T &a){return all_of(ALL(a),[](bool x){return x;});}
template<class T> bool anytrue(const T &a){return any_of(ALL(a),[](bool x){return x;});}
template<class T> bool contain(const T &a,const T &b){for(auto x:b){if (a.find(x)==a.end()){return false;}}return true;}
template<class T> bool mmax(T &m,const T q){ if (m < q) {m = q; return true;} else return false; }
template<class T> bool mmin(T &m,const T q){ if (m > q) {m = q; return true;} else return false; }
template<class T> int siz(const T &a) {return (int)a.size();}
template<class T> set<T> devisers(T n) {
  set<T> res;for(T i=1;i<(T)sqrt(n)+1;i++){if(n%i==0){res.insert(i);res.insert(n/i);}}return res;
}
template<class T> void concat(T &a, const T &b){a.insert(a.end(),b.begin(),b.end());}
template<class T> void getand(const T &a,const T &b,T &c) {
  set_intersection(a.begin(),a.end(),b.begin(),b.end(),inserter(c,c.end()));
}
template<class T> void getor(const T &a,const T &b,T &c) {
  set_union(a.begin(),a.end(),b.begin(),b.end(),inserter(c,c.end()));
}

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

const ll MOD=1e9+7;
const int MAX=1e5+100;

int main() {
  // fの最大値
  // Kの範囲が大きいので、Kを地道にloopさせていくのは無理
  // ASをそれぞれbitsetにした上で桁ごとに1と0の数をカウントしていく
  // そして桁ごとに0の方が多い場合は1を、1の方が多い場合は0を入れていったものが最大になるX
  // Xの条件としてK以下であることを忘れない
  ll N,K;cin>>N>>K;
  vector<bitset<40>> AS(N);

  // 下準備、ASをbitsetに
  REP(i,N) {
    ll a;cin>>a;
    bitset<40> bs(a);
    AS[i] = bs;
  }

  // まず理想の数Xを作る
  bitset<40> rbs;
  REP(i,40) {
    int zero_cnt = 0;
    REP(j,N) {
      if (AS[j][i]==0) zero_cnt++;
    }
    if (zero_cnt>N/2) rbs.set(i);
  }

  // XをK以下の値にする。桁DP
  bitset<40> Kbs(K);
  REP(i,40) {
    if (rbs[39-i]==1 && Kbs[39-i]==0) {
      rbs.reset(39-i);
    } else if (rbs[39-i]==0 && Kbs[39-i]==1) {
      break;
    }
  }

  // 計算
  ll res = 0;
  REP(i,N) {
    res += (AS[i] ^ rbs).to_ulong();
  }
  OUT(res);

  return 0;
}

Measured memory_bytes: 1024
import sys
import math

r = sys.stdin.readlines()


n = [[float(i) for i in (j.split())] for j in r] 
    
for l in n:
    y = (l[2]*l[3]-l[0]*l[5])/(l[1]*l[3]-l[0]*l[4])+0
    
    x = (l[2]*l[4]-l[5]*l[1])/(l[0]*l[4]-l[3]*l[1])+0
    
    print("%.3f %.3f" %(x, y))
    

Measured memory_bytes: 7508
from math import sqrt
from collections import Counter


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


def num_z(n):
    return int((sqrt(1 + 8 * n) - 1) / 2)

################################################################

N = int(input())
factors = Counter(prime_factorize(N))
ans = 0
for n in factors.values():
    ans += num_z(n)
print(ans)


Measured memory_bytes: 9480
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = min(a) + min(b)
for _ in range(M):
    xi, yi, ci = map(int, input().split())
    ans = min(ans, a[xi - 1] + b[yi - 1] - ci)
print(ans)

Measured memory_bytes: 70892
#include <bits/stdc++.h>
#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 n; cin >> n;
    vector<vector<int>> F(n, vector<int>(10)), P(n, vector<int>(11));
    rep(i, n) {
        rep(j, 10) cin >> F[i][j];
    }
    rep(i, n) {
        rep(j, 11) cin >> P[i][j];
    }
    ll ans = -1e18;
    for(int bit=1;bit<(1<<10);bit++) {
        ll res = 0;
        vector<int> store(n);
        rep(i, 10) {//時間帯
            if((bit>>i)&1) {
                rep(j, n) {//店
                    if(F[j][i]) {
                        store[j]++;
                    }
                }
            }
        }
        rep(i, n) {
            res += P[i][store[i]];
        }
        ans = max(ans, res);
    }
    cout << ans;
}


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

using namespace std;

typedef long long lli;
typedef double lld;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<double> vdl;
typedef vector<vector<lli>> mat;
typedef vector<vdl> mad;
typedef unordered_map<lli,unordered_map<lli,lli>> graph;
typedef complex<double> cmp;
typedef vector<cmp> vcl;

lli a,b;

int main(){
  cin >> a >> b;
  cout << (a-1)*(b-1) << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 1004

int hseq[MAX][MAX];
int vseq[MAX][MAX];
int sq[MAX][MAX];
char f[MAX][MAX];

int main() {
  while(true) {
    int n;
    scanf("%d", &n);
    if(n==0) break;
    int ans = 0;
    for(int y=1; y<=n; ++y) {
      scanf("%s", &f[y][1]);
      for(int x=1; x<=n; ++x) {
        hseq[y][x] = f[y][x]=='.' ? hseq[y][x-1]+1 : 0;
        vseq[y][x] = f[y][x]=='.' ? vseq[y-1][x]+1 : 0;
        sq[y][x] = f[y][x]=='.' ? min(sq[y-1][x-1], min(hseq[y][x-1], vseq[y-1][x]))+1 : 0;
        ans = max(ans, sq[y][x]);
      }
    }
    /*
    for(int y=1; y<=n; ++y) {
      for(int x=1; x<=n; ++x) {
        printf(" %2d", sq[y][x]);
      }
      printf("\n");
    }
    */
    printf("%d\n", ans);
  }
  return 0;
}


Measured memory_bytes: 15340
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	//下20桁まで出す処理。たまに精度求められるため記述。
	//cout << fixed << setprecision(20);

	int a;
	cin >> a;
	vector<int> vect(a);
	for (size_t i = 0; i < a; ++i)
	{
		cin >> vect[i];
	}

	int ans[2] = { vect[0],vect[0]};
	long long sum = 0;

	while (a--)
	{
		ans[0] = min(ans[0], vect[a]);
		ans[1] = max(ans[1], vect[a]);
		sum += vect[a];
	}

	cout << ans[0]<<" "<<ans[1]<<" "<<sum << endl;
	return 0;
}


Measured memory_bytes: 3148
use std::io::{stdin, stdout, BufReader, BufRead, StdinLock, Write, BufWriter};
use std::collections::BinaryHeap;

fn main() {
    let (std_in, std_out) = (stdin(), stdout());
    let mut br = BufReader::new(std_in.lock());
    let mut bw = BufWriter::new(std_out.lock());
    
    let __ = rvn::<usize>(&mut br);
    let (n, m) = (__[0], __[1]);
    let mut v = Vec::new();
    for i in 0..n {
        let ab = rvn::<usize>(&mut br);
        v.push((ab[0], ab[1]));
    }

    v.sort_by(|x, y| y.0.cmp(&x.0));
    let mut res = 0;
    let mut hp = BinaryHeap::<usize>::new();
    for i in 1..m+1 {
        while !v.is_empty() && v.last().unwrap().0 == i {
            hp.push(v.pop().unwrap().1);
        }
        res += match hp.pop() {
            Some(n) => n,
            None => 0,
        }
    }
    
    writeln!(&mut bw, "{}", res);
}


//////////////////////////////////////////////////////////////////////////////////
#[allow(dead_code)]
fn rs(br: &mut BufReader<StdinLock>) -> Vec<char> {
    let mut buf = String::new();
    br.read_line(&mut buf).ok();
    buf.trim().chars().collect()
}

#[allow(dead_code)]
fn rn<T: std::str::FromStr>(br: &mut BufReader<StdinLock>) -> T {
    let mut buf = String::new();
    br.read_line(&mut buf).ok();
    buf.trim().parse().ok().unwrap()
}

#[allow(dead_code)]
fn rvs(br: &mut BufReader<StdinLock>) -> Vec<Vec<char>> {
    let mut buf = String::new();
    br.read_line(&mut buf).ok();
    buf.trim().split_whitespace().map(|e| e.chars().collect()).collect()
}

#[allow(dead_code)]
fn rvn<T: std::str::FromStr>(br: &mut BufReader<StdinLock>) -> Vec<T> {
    let mut buf = String::new();
    br.read_line(&mut buf).ok();
    buf.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

Measured memory_bytes: 8444
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
using namespace std;

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

typedef unsigned long long ul;
typedef unsigned int ui;
constexpr ll mod = 998244353;
const ll INF = mod * mod;
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);

ll mod_pow(ll x, ll n) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * x%mod;
		x = x * x%mod; 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;
}

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 << 20;
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];
}

ll t26[30] = {};
void solve() {
	ll n; cin >> n;
	t26[0] = 1;
	rep(i, 29) {
		t26[i + 1] = t26[i] * 26;
	}
  t26[0]=1;
	int cnt = 0;
	ll cop = n+1;
	rep(i, 30) {
		if (t26[i] < cop) {
			cnt++; cop -= t26[i];
		}
		else {
			break;
		}
	}
	string ans;
	cop--;
	rep(i, cnt) {
		ll d = cop / t26[cnt - i-1];
		ans.push_back('a' + d);
		cop -= d * t26[cnt - i - 1];
	}
	cout << ans << "\n";
}


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


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

using namespace std;

int main(){
  int n;
  cin>>n;
  string s1;
  string s2;
  for(int i=0;i<n;i++){
  	char x;
  	cin>>x;
  	s1.push_back(x);
  }
  for(int i=0;i<n;i++){
  	char x;
  	cin>>x;
  	s2.push_back(x);
  }
  //cout<<s1<<endl;
  //cout<<s2<<endl;
  string start;
  int a=-1;
  int b=-1;
  for(int i = 0;i<n;i++){
    start.push_back('1'+i);
  }
  string temp=start;
  int count = 1;
  do{
  	//cout<<"Start "<<start<<endl;
  	//cout<<"Count "<<count<<endl;
    if(start == s1){
      if(a==-1){
        a=count;
      }
      else{
        b=count;
        break;
      }
    }
    if(start == s2){
      if(a==-1){
        a=count;
      }
      else{
        b=count;
        break;
      }
    }
    count++;
    next_permutation(start.begin(),start.end());
  }while(start!=temp);
  cout<<abs(a-b)<<endl;
  //int x;
  //cin>>x;
  return 0;
}

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

//
#define int long long
#define pb(x) push_back(x)
#define m0(x) memset((x), 0, sizeof(x))
#define mm(x) memset((x), -1, sizeof(x))

//container
#define ALL(x) (x).begin(), (x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
#define PERM(c) \
  sort(ALL(c)); \
  for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))

// debug
#define GET_VAR_NAME(variable) #variable
#define test(x) cout << GET_VAR_NAME(x) << " = " << x << endl;

// bit_macro
#define bit(n) (1LL << (n))
#define bitset(a, b) (a) |= (1 << (b))
#define bitunset(a, b) (a) |= ~(1 << (b))
#define bitcheck(a, b) ((((a) >> (b)) & 1) == 1)
#define bitcount(a) __builtin_popcountll((a))

//typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

//constant
const int INF = (int)1e18;
const int MOD = (int)1e9 + 7;
const double PI = (double)acos(-1);
const double EPS = (double)1e-10;
const int dx[] = {-1, 0, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, -1, 1, 0, 0, 1, -1, 1, -1};

//
template <typename T>
void chmax(T &a, T b) { a = max(a, b); }
template <typename T>
void chmin(T &a, T b) { a = min(a, b); }
//
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

//
struct Accelerate_Cin {
  Accelerate_Cin() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
  };
};

int N, M;
vector<P> v;

signed main() {
  cin >> N >> M;
  for (int i = 0; i < N; i++) {
    int ta, tb;
    cin >> ta >> tb;
    v.pb(P(ta, tb));
  }

  sort(ALL(v));

  int cont = 0, sum = 0;
  for (int i = 0; i < N; i++) {
    if (M >= cont + v[i].second) {
      sum += v[i].second * v[i].first;
      cont += v[i].second;
    } else {
      sum += v[i].first * (M - cont);
      cont = M;
    }
    if (cont == M) break;
  }

  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 2420
#include <stdio.h>
int main(){
	int H, W, i, j;
	while (1)
	{
		scanf("%d%d", &H, &W);
		if (H==0&&W==0)
		{
			break;
		}
		for ( i = 1; i <= H; i++)
		{
			for ( j = 1; j <= W; j++)
			{
				if (i % 2 == 0)
				{
					if (j % 2 == 0)
					{
						printf("#");
					}
					else
					{
						printf(".");
					}
				}
				else
				{
					if (j % 2 == 0)
					{
						printf(".");
					}
					else
					{
						printf("#");
					}
				}
				
			}
			printf("\n");
		}
		printf("\n");
	}
	return 0;
}

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

int main () {
  long long int n,a,b;
  cin >>n>>a>>b;
  long long int ans =(n/(a+b))*a;
  long long  int r =n%(a+b);
  ans += min (r ,a);

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


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

//#define int long long
//using ll = boost::multiprecision::cpp_int;
using ll = long long;
//constexpr int INF = 1e9;//INT_MAX=(1<<31)-1=2147483647
constexpr ll INF = (ll)1e18;//(1LL<<63)-1=9223372036854775807
constexpr ll MOD = (ll)1e9 + 7;
constexpr double EPS = 1e-9;
constexpr int dx[4]={1,0,-1,0};
constexpr int dy[4]={0,1,0,-1};
#ifdef LOCAL_ENV
	#define debug(var) std::cout<<#var" = "<<var<<std::endl
#else
	#define debug(var)
#endif
#define p(var) std::cout<<var<<std::endl
#define rep(i, n)   for(ll i=0, i##_length=(n); i< i##_length; ++i)
#define repeq(i, n) for(ll i=1, i##_length=(n); i<=i##_length; ++i)
#define all(a) (a).begin(), (a).end()
#define PI (acos(-1))
template<typename T> inline T power(T x, T n){ return n ? power(x*x%MOD,n/2)*(n%2?x:1)%MOD : 1; }
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b,a%b) : a; }
template<typename T> inline T lcm(T a, T b) { return a / gcd(a,  b) * b; }
template<typename T1, typename T2>inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2>inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
	for (int i = 0, len = v.size(); i < len; ++i){
		s << v[i]; if (i < len - 1) s << "\t";
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
	for (int i = 0, len = vv.size(); i < len; ++i){
		s << vv[i] << endl;
	}
	return s;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s, const map<T1, T2>& m) {
	s << "{" << endl;
	for (typeof(m.begin()) itr = m.begin(); itr != m.end(); ++itr){
		s << "\t" << (*itr).first << " : " << (*itr).second << endl;
	}
	s << "}" << endl;
	return s;
}

/*-----8<-----8<-----*/

constexpr ll D_MAX = 15;
constexpr ll P_I_MAX = 110;
constexpr ll C_I_MAX = 1000000;

ll D, G;
ll p[D_MAX];
ll c[D_MAX];

void input() {
	scanf("%lld%lld", &D, &G);
	rep(i, D) scanf("%lld%lld", p + i, c + i);
}

void solve() {
	ll ans = INF;

	vector<int> pattern(D+1,0);
	while(1){
		ll count=0;
		ll sum=0;
		priority_queue<ll> q;
		rep(i,D){
			if(pattern[i]){
				//bonus
				sum+=c[i]+(i+1)*100*p[i];
				count+=p[i];
			}else{
				rep(j,p[i]-1){
					q.push((i+1)*100);
				}
			}
		}

		if(!q.empty()){
			while(sum<G){
				sum+=q.top();
				q.pop();
				count++;
			}
		}

		if(sum>=G)chmin(ans,count);

		//カウントアップ 4^nを列挙できる
		pattern[0]++;
		rep(i,D){
			if(pattern[i]==2){
				pattern[i]=0;
				pattern[i+1]++;
			}
		}
		if(pattern[D]>0)break;
	}

	printf("%lld\n", ans);
}

signed main() {
	input();
	solve();
	return 0;
}


Measured memory_bytes: 764
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>
#include <random>
#include <climits>
#include <stack>

using namespace std;

typedef long long ll;
typedef long double ld;

#define int ll
#define double ld
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect
#define no {cout << -1; return;}
#define yes {cout << "Yes"; return;}
#define mkp make_pair
#define mkt make_tuple
#define cerr if(0) cerr

void solve() {
    int n; cin >> n;
    vector <int> a(n);
    loop(i, n)
        cin >> a[i];
    int ans = 0;
    loop(i, n)
        loop(j, i)
            ans += a[i] * a[j];
    cout << ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}


Measured memory_bytes: 3664
#include<bits/stdc++.h>
 
#define fi first
#define se second
 
#define mp make_pair
#define pb push_back
 
#define all(x) (x).begin(), (x).end()
 
#define F return
#define skip continue

#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)

typedef long long ll;

using namespace std;                             

typedef pair<int, int> pii;
typedef pair<ll, ll> pll; 

 
const int MAXN = 3e5 + 500;
const int INF = 1e9 + 23;
const int MOD = 1e9 + 7;

int n, a, b;
int arr[MAXN];

bool T(ll x) {
    ll cnt = 0;
    for (int i = 1; i <= n; i++) {
        ll mx = max(0ll, arr[i] - (x * 1ll * b));
        ll s = (mx + a - 1) / a;
        cnt += s;
    }
    return cnt <= x;
}

void solve() {                        
    cin >> n >> a >> b;
    a -= b;
    rep(i, 1, n) cin >> arr[i];

    sort(arr + 1, arr + n + 1);

    int l = 0, r = INF + INF, mid;
    while (l + 1 < r) {
        mid = (l + r) >> 1;
        if (T(mid)) {
            r = mid;
        }
        else {
            l = mid;
        }
    }
    cout << r;
}

int main() {                
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int tt = 1;
     
    while (tt--) {
        solve();
        cout << '\n';
    }
 
    return 0;
    // you should actually read the stuff at the bottom
}
/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
*/

Measured memory_bytes: 640
#include <bits/stdc++.h>
#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(){
	string S;
	cin>>S;
	if(S.at(2)==S.at(3)&&S.at(4)==S.at(5)){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
return 0;}

/*compile
g++ code.cpp
./a.out
run*/

Measured memory_bytes: 256
n,k = map(int,input().split())
A = list(map(int,input().split()))
result = 1000000001*15
def j_cost(cost):
    c = 1
    for i in range(1,len(A)):
        if(max(cost[:i]) < cost[i]):
            c += 1
    #print(c,cost)
    if c >= k:
        return True
    else:
        return False

for i in range(2**n):
    cost = [0]*len(A)
    for j in range(1,n):
        if((i>>j)&1):
            total = [x + y for (x,y) in zip(A[:j],cost[:j])]
            if(max(total)>=A[j]):
                cost[j] = max(total)+1-A[j]
            else:
                cost[j] = 0
    #print(cost,[x + y for (x,y) in zip(A,cost)])
    if(sum(cost) < result and j_cost([x + y for (x,y) in zip(A,cost)])):
        result = sum(cost)
print(result)


Measured memory_bytes: 48860
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(ll i = 0; i < n; i++)
const ll INF = 1LL << 60;
const int mod = 1000000007;

int main(){
    double D, T, S; cin >> D >> T >> S;
    if(D / S <= T)cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3692
def main():
    N = int(input())
    points = []
    for _ in range(N):
        x, y = map(int, input().split())
        points.append((x, y, "r"))
    for _ in range(N):
        x, y = map(int, input().split())
        points.append((x, y, "b"))
    points.sort(lambda x: x[0])
    singles = []
    retval = 0
    for p in points:
        x, y, c = p
        if c == "r":
            singles.append(y)
        if c == "b":
            maximum = (-1, -1)
            for i, v in enumerate(singles):
                if v < y and v > maximum[1]:
                    maximum = (i, v)
            if maximum[0] != -1:
                retval += 1
                singles.pop(maximum[0])
    print(retval)


if __name__ == "__main__":
    main()


Measured memory_bytes: 39024
/*
ID: computerbox --> Huseyn Hajiyev
LANG: C++
TASK: target_mode_on
*/
#include <bits/stdc++.h>
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#define _CRT_SECURE_NO_WARNINGS
//#include <boost/multiprecision/cpp_int.hpp>
//using boost::multiprecision::cpp_int;
#define FAST_READ ios_base::sync_with_stdio(0);/*cin.tie(0); cout.tie(0);*/
#define in freopen("input.txt", "r", stdin);
#define out freopen("output.txt", "w", stdout);
#define ll long long
#define debt(x,y)cout<<"#x = "<<(x)<<" and "<<"#y = "<<(y)<<endl;
#define deb(x)cout<<"#x = "<<(x)<<endl;
#define COUT(n, a) cout<< fixed << setprecision(a) << n<<endl
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define arr(a,n) for(ll i=1;i<=n;i++) cout<<a[i]<<" "; cout << "\n";
#define vecc(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" "; cout << "\n";
#define CURTIME() cerr << clock() * 1.0 / CLOCKS_PER_SEC << endl
#define DTIME(ccc) __begin = clock(); ccc; cerr<<"Time of work = "<<(clock()-__begin)/CLOCKS_PER_SEC<<endl;
#define MAXN 2000

using namespace std;

#define debug(args...)(Debugger()) , args
class Debugger
{
  public:
  Debugger(const std::string& _separator=", ") :
  first(true),separator(_separator){}
  template<typename ObjectType>
  Debugger& operator,(const ObjectType& v)
  {
        if(!first)cerr<<separator;
        cerr<<v;
        first=false;
        return *this;
  }
  ~Debugger() {cerr<<endl;}      
  private:
    bool first;
    string separator;
};
 
template <typename T1, typename T2>
inline ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p)
{
   return os<<"("<<p.first<<", "<<p.second<<")";
}
template<typename T>
inline ostream &operator<<(ostream & os,const vector<T>& v)
{
    bool first=true;
    os<<"[";
    for(unsigned ll i=0;i<v.size();i++)
    {
        if(!first)os<<", ";
        os<<v[i];
        first=false;
    }
        return os<<"]";
}
template<typename T>
inline ostream &operator<<(ostream & os,const set<T>&v)
{
    bool first=true;
    os<<"[";
    for(typename set<T>::const_iterator ii=v.begin();ii!=v.end();++ii)
    {
        if(!first)os<<", ";
        os<<*ii;
        first=false;
    }
    return os<<"]";
}
template<typename T1, typename T2>
inline ostream &operator<<(ostream & os,const map<T1, T2>&v)
{
        bool first=true;
        os<<"[";
        for(typename map<T1,T2>::const_iterator ii=v.begin(); ii!=v.end();++ii)
        {
            if(!first)os<<", ";
            os<<*ii;
            first=false;
        }
        return os<<"]";
}

string stroka;

int main(){
FAST_READ;
cin.tie(0);
cin>>stroka;
ll cnt=0;
for(ll i=0;i<stroka.size();i++)
{
  if(stroka[i]=='+')cnt++;
  else if(stroka[i]=='-')cnt--;
}
cout<<cnt<<endl;






return 0;
} 

Measured memory_bytes: 764
import java.util.Scanner;

public class  Main {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int i = 0;
		while (++i <= n) {
			int x = i;
			if (x % 3 == 0) System.out.print(" " + i);
			else {
				for (; x != 0; x /= 10) {
					if (x % 10 == 3) {
						System.out.print(" " + i);
						break;
					}
				}
			}
		}
		System.out.println();
	}
}

Measured memory_bytes: 28584
#include <iostream>
#include <string>

using namespace std;

typedef long long ll;

int main() {
	string s;
	ll k;
	cin >> s >> k;
	for(int i = 1; i <= s.size(); i++) {
		if((int)(s.at(i-1)-'1') > 0 || i==k) {
			cout << s.at(i-1) << endl;
			return 0;
		}
	}
	cout << 1 << endl;
	return 0;
}


Measured memory_bytes: 888
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
)

var (
	read  = bufio.NewReader(os.Stdin)
	write = bufio.NewWriter(os.Stdout)
)

func min(a, b int) int {
	if a <= b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a >= b {
		return a
	}
	return b
}

func yesno(result bool) {
	if result {
		fmt.Fprintln(write, "Yes")
	} else {
		fmt.Fprintln(write, "No")
	}
}

func printansStr(result bool, a, b string) {
	if result {
		fmt.Fprintln(write, a)
	} else {
		fmt.Fprintln(write, b)
	}
}

func printansInt(result bool, a, b int) {
	if result {
		fmt.Fprintln(write, a)
	} else {
		fmt.Fprintln(write, b)
	}
}

func main() {
	defer write.Flush()

	var n int
	fmt.Fscan(read, &n)

	w := make([]int, n)
	s1, s2 := 0, 0
	for i := 0; i < n; i++ {
		fmt.Fscan(read, &w[i])
		s2 += w[i]
	}

	ans := int(math.Abs(float64(s1 - s2)))
	for i := 0; i < n; i++ {
		s1 += w[i]
		s2 -= w[i]
		ans = min(ans, int(math.Abs(float64(s1-s2))))
	}
	fmt.Fprintln(write, ans)
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for (int i = (0); i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define show(x) cout << #x << " = " << (x) << endl
#define show2(x,y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
#define show3(x,y,z) cout << #x << " = " << (x) << ", " << #y << " = " << (y) <<  ", " << #z << " = " << (z) << endl
#define showv(v) rep(i,v.size()) printf("%d%c", v[i], i==v.size()-1?'\n':' ')
#define showv2(v) rep(j,v.size()) showv(v[j])
#define showt(t,n) rep(i,n) printf("%d%c", t[i], i==n-1?'\n':' ')
#define showt2(t,r,c) rep(j,r) showt(t[j],c)
#define showvp(p) rep(i,p.size()) printf("%d %d\n", p[i].first, p[i].second);
#define printv(v) rep(i,v.size()) printf("%d\n", v[i])
#define printt(t,n) rep(i,n) printf("%d\n", t[i])
#define incl(v,x) find(rng(v),x)!=v.end()
#define incls(s,c) s.find(c)!=string::npos
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define bit(n,k) ((n>>k)&1) // nのk bit目
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vs = vector<string>;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using vp = vector<P>;
using vt = vector<T>;
const int mod = 1000000007;
const double EPS = 1e-9;
//const long double EPS = 1e-14;
const int INF = (1<<30)-1;
//const ll INF = (1LL<<62)-1;
#define dame { puts("No"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
inline int in() { int x; scanf("%d",&x); return x;}
//template<class T = int> inline T in() { T x; cin >> x; return (x);}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main () {
  int a, b, k;
  cin >> a >> b >> k;
  int n = b-a+1;
  if (k < a+(n-1)/2) {
    for (int i = a; i <= b; i++) {
      if (i <= a+k-1 || b-(k-1) <= i) {
        printf("%d\n", i);
      } 
    }
  }
  else {
    for (int i = a; i <= b; i++) {
      printf("%d\n", i);
    }
  }
  return 0;
}

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

int main(){
  double a, b, x;
  cin >> a >> b >> x;
  double ans = 0;
  if(a*b/2 < x/a) ans = atan2(2/a*(a*b-x/a), a) * 360/(2*acos(-1));
  else  ans = atan2(b, 2*x/(a*b)) * 360/(2*acos(-1));
  printf("%.10f", ans);
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
	int i, N, K;
	long long a[1001];
	scanf("%d %d", &N, &K);
	for (i = 1; i <= N; i++) scanf("%lld", &(a[i]));

	int j, k, count;
	long long ans = 0, sum[1001][1001], bit[60];
	for (i = 1, bit[0] = 1; i < 60; i++) bit[i] = bit[i-1] << 1;
	for (i = 1; i <= N; i++) {
		for (j = i, sum[i][i-1] = 0; j <= N; j++) sum[i][j] = sum[i][j-1] + a[j];
	}
	for (k = 59; (sum[1][N] | bit[k]) != sum[1][N]; k--);
	for (; k >= 0; k--) {
		count = 0;
		for (i = 1; i <= N; i++) {
			for (j = i; j <= N; j++) if ((sum[i][j] | bit[k]) == sum[i][j]) count++;
		}
		if (count >= K) {
			ans += bit[k];
			for (i = 1; i <= N; i++) {
				for (j = i; j <= N; j++) if ((sum[i][j] | bit[k]) != sum[i][j]) sum[i][j] = 0;
			}
		}
	}
	
	printf("%lld\n", ans);
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 8604
#include<stdio.h>

int main(){
bool f[1000001];
for(int i=1;i<1000000;i++)
{f[i]=true;
for(int j=2;j*j<=i;j++)
if(i%j==0){f[i]=false;break;}
}

f[1]=false;
while(1){int a,b,n;
scanf("%d%d%d",&a,&b,&n);if(a==0&&b==0&&n==0)break;
int c=0;
//for(int i=0;c<n;i++){
int i=0;
while(c!=n){
if(f[a+b*i]==true)c++;
i++;
}
printf("%d\n",a+b*(i-1));
}

return 0;
}

Measured memory_bytes: 2004
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int K;
  string S;
  cin >> K >> S;
  if(S.size()<=K){
    cout << S <<endl;
  }
  else{
    for(int i=0;i<K;i++){
      cout << S.at(i);
    }
    cout <<"..."<<endl;
  }
}

Measured memory_bytes: 3628
import queue

q_lunlun_num = queue.Queue()
for i in range(1, 10):
    q_lunlun_num.put(i)

K = int(input())
for _ in range(K):
    now_lunlun_num = q_lunlun_num.get()
    first_digit = now_lunlun_num % 10

    if first_digit != 0:
        q_lunlun_num.put(now_lunlun_num*10 + first_digit - 1)
    
    q_lunlun_num.put(now_lunlun_num*10 + first_digit)

    if first_digit != 9:
        q_lunlun_num.put(now_lunlun_num*10 + first_digit +1 )

print(now_lunlun_num)

Measured memory_bytes: 57320
// clang-format off
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using G = vector<vector<ll>>;
#define G(i, j) i, vector<ll>(j)
#define Gv(i, j, k) i, vector<ll>(j, k)
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define rep1(i,n) for(ll i=1, i##_len=(n); i<=i##_len; ++i)
#define rrep(i,n) for(ll i=n-1; i>=0; --i)
#define rrep1(i,n) for(ll i=n; i>0; --i)
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort(all(x))
#define SORT_DESC(x) sort((x).rbegin(),(x).rend())
#define pb push_back
#define mp make_pair
#define coutl cout<<fixed<<setprecision(10)
#define ANS(ans) cout<<ans<<endl
#define END(ans) ANS(ans); return
const ll LINF = (1LL << 62) - 1;
const int INF = (1 << 30) - 1;
template<class T>inline bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if (b<a){a=b;return 1;}return 0;}
// clang-format on

void solve(long long N) {
  ANS((N % 1000 == 0 ? 0 : 1000 - (N % 1000)));
}

// clang-format off
int main() {
  long long N;
  scanf("%lld",&N);
  solve(N);
  return 0;
}


Measured memory_bytes: 3720
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
int main() {
    vector<vector<int>> c(3, vector<int>(3));
    rep(i, 3) rep(j, 3) cin >> c[i][j];
    bool ok = true;
    rep(i, 2) {
        if ( c[i+1][0] - c[i][0] != c[i+1][1] - c[i][1] ) ok = false;
        if ( c[i+1][1] - c[i][1] != c[i+1][2] - c[i][2] ) ok = false;
    }
    rep(i, 2) {
        if ( c[0][i+1] - c[0][i] != c[1][i+1] - c[1][i] ) ok = false;
        if ( c[1][i+1] - c[1][i] != c[2][i+1] - c[2][i] ) ok = false;
    }
    if ( !ok ) cout << "No" << endl;
    else       cout << "Yes" << endl; 
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main()
{
    int n;
    while(cin>>n)
    {
        int sum=0;
        int maxn=0,minn=10000000000;
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
            if(a[i]>=maxn)
            {
                maxn=a[i];
            }
            if(a[i]<=minn)
            {
                minn=a[i];
            }

        }
        int k=(maxn+minn)/2;
        int sum1=0,maxnn=10000000000;
        for(int i=minn;i<=maxn;i++)
        {
            sum1=0;
            for(int j=0;j<n;j++)
            {
                sum1+=(a[j]-i)*(a[j]-i);
            }
            if(sum1<=maxnn)
            {
                maxnn=sum1;
            }
        }
        cout<<maxnn<<endl;
    }
}


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

#define ll long long
const int mod = 1e9 + 7;

int xinc[2] = {0, 1};
int yinc[2] = {1, 0};

ll ans(char **rc, int r, int c){
	ll res;
	ll **distanc = new ll*[r];
	bool **proc = new bool*[r];
	
	
	for(int i =  0; i<r; i++){
		distanc[i] = new ll[c];
		proc[i] = new bool[c];
		}
	
	for(int i = 0; i<r; i++)
		for(int j = 0; j<c; j++)
			proc[i][j] = 0, distanc[i][j] = 0;
	distanc[0][0] = 1;
	queue<int> xcor, ycor;
	xcor.push(0); ycor.push(0);
	while(!xcor.empty()){
		int x = xcor.front(), y = ycor.front();
		xcor.pop(); ycor.pop();
		if(proc[x][y])
			continue;
		
		for(int i = 0; i<2; i++){
			int xtemp = x + xinc[i];
			int ytemp = y + yinc[i];
			if(xtemp < 0 || ytemp < 0)
				continue;
			if(xtemp >= r || ytemp >= c)
				continue;
			if(rc[xtemp][ytemp] == '#')
				continue;
			distanc[xtemp][ytemp]  = (distanc[xtemp][ytemp] + distanc[x][y])%mod;
			xcor.push(xtemp); ycor.push(ytemp);
			}
		proc[x][y] = 1;
		}
	res = distanc[r-1][c-1];
	
	
	for(int i = 0; i<r; i++){
		delete [] distanc[i];
		delete [] proc[i];
	}
	delete [] distanc;
	delete [] proc;
	
	return res;
	}



int main(){
	int r, c;
	
	cin>>r>>c;
	char **rc;
	rc = new char*[r];
	for(int i = 0; i<r; i++){
		rc[i] = new char[c+1];
		cin>>rc[i];
		}
	cout<<ans(rc, r, c)<<endl;
	
	for(int i = 0; i<r; i++){
		delete [] rc[i];
		
	}
	delete [] rc;
	return 0;
	
}


Measured memory_bytes: 10112
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define rep(i,j) for(int i=0;i<j;i++)
#define reps(i,j,k) for(int i=j;i<=k;i++)
#define ms(i,j) memset(i,j,sizeof(i))
using namespace std;
int n,h,w;
char m[50][51];
bool e[26];
bool dfs(int p,bool f[26][26]){
	if(e[p])return false;
	e[p]=true;
	bool r=true;
	rep(i,26)if(i!=p&&f[p][i]&&!dfs(i,f))r=false;
	e[p]=false;
	return r;
}
int main(){
    scanf("%d",&n);
    while(n--){
        scanf("%d%d",&h,&w);
        bool a=true;
            int t[26],l[26],r[26]={0},b[26]={0};
            rep(i,26)t[i]=l[i]=55;
            bool f[26][26];
            ms(f,0);
        rep(i,h){
            scanf("%s",m[i]);
            rep(j,w)if(m[i][j]!='.'){
                char c=m[i][j]-'A';
                f[c][c]=true;
                t[c]=min(t[c],i);
                l[c]=min(l[c],j);
                r[c]=max(r[c],j);
                b[c]=max(b[c],i);
            }
        }
		int cnt[26]={0};
        rep(i,26)if(f[i][i]){
            reps(j,t[i],b[i])reps(k,l[i],r[i]){
                if(m[j][k]!=i+'A'){
                    if(m[j][k]=='.')a=false;
                    else f[i][m[j][k]-'A']=true;
                }
            }
        }
		rep(i,26)if(!dfs(i,f))a=false;
		
        puts(a?"SAFE":"SUSPICIOUS");
    }
    return 0;
}

Measured memory_bytes: 1012
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int p=1e9+7;
int n,m,i,j,x,y,re[5010],f[3010][3010],a[3010][2];
char s[3010];
int main(){
	scanf("%d%d",&n,&m);
	scanf("%s",s+1);
	for(i=1;i<=n;i++){
		a[i][0]=a[i-1][0];a[i][1]=a[i-1][1];
		if(s[i]=='0')a[i][0]++;
		 else a[i][1]++;
		re[i]=i;
	}
	for(i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		re[x]=max(re[x],y);
	}
	for(i=1;i<=n;i++)re[i]=max(re[i],re[i-1]);
	f[0][0]=1;
	for(i=1;i<=n;i++)
	 for(j=0;j<i;j++)if(f[i-1][j]){
	 	if(j+1<=a[re[i]][0])f[i][j+1]=(f[i][j+1]+f[i-1][j])%p;
	 	if(i-j<=a[re[i]][1])f[i][j]=(f[i][j]+f[i-1][j])%p;
	 }
	printf("%d",f[n][a[n][0]]);
}

Measured memory_bytes: 33920
a = int(input())
b = list(map(int, input().split()))

ans = 0
temp = 0
for i in zip(b, b[1:]):
  if i[0] >= i[1]:
    temp += 1
  else:
    ans = max(ans, temp)
    temp = 0
ans = max(ans, temp)
print(ans)

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

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rep2(i,s,n) for(int i = (s); i < (n); ++i)
#define ll long long
#define ld long double
#define P pair<ll,ll>
#define all(v) v.begin(),v.end()

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1.0);

ll sumofketa(ll a,ll b){
    string s=to_string(a),t=to_string(b);
    return max(s.size(),t.size());
}

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

    ll ans1=100*a,ans2=0;
    double tmp=0;

    rep(i,31)rep(j,31){
        rep(k,101)rep(l,101){
            double w = 100 * (a * i + b * j);
            double s = c * k + d * l;
            if(w == 0 || w + s > f) break;
            if(s > e * (a * i + b * j) ) break;
            if( (double)s / (w + s)  > tmp ){
                tmp = max(tmp, s/(w+s));
                ans1 = w + s;
                ans2 = s;
            }
        }
    }
    cout << ans1 << " " << ans2 <<endl;
    return 0;
}

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

int main() {
	string a,b,c,d,ans;
	bool aa=0,bb=0,cc=0,dd=0;
	cin >>a>>b>>c>>d;
	ans=a+b+c+d;
	
	if(ans=="1974")
		cout <<"YES"<<endl;
	else
	{
		for(int i=0;i<ans.length();i++)
		{
			if(ans[i]=='1')
				aa=1;
			if(ans[i]=='9')
				bb=1;
			if(ans[i]=='7')
				cc=1;
			if(ans[i]=='4')
				dd=1;
		}
		if(aa&&bb&&cc&&dd)
		cout <<"YES"<<endl;
		else
		cout <<"NO"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
import java.util.Set;
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

public class Main{
	static final Scanner s=new Scanner(System.in);
	static final long[] fal_rnd(int size){
		AtomicInteger l=new AtomicInteger(-1),r=new AtomicInteger(size);
		long[] res=new long[size];
		INS(size).unordered().parallel().mapToLong(Long::parseLong).forEach(v->res[ThreadLocalRandom.current().nextBoolean()?l.incrementAndGet():r.decrementAndGet()]=v);
		return res;
	}
	static final IntStream REPS(int v){
		return IntStream.range(0,v);
	}
	static final Stream<String> INS(long size){
		return StreamSupport.stream(Spliterators.spliterator(s,size,Spliterator.NONNULL&Spliterator.IMMUTABLE),false).limit(size);
	}
	public static void main(String __[]){
		Set<String> set=INS(s.nextInt()).collect(Collectors.toSet());
		boolean isOpen=false;
		for(int i=s.nextInt();i>0;i--) {
			String in=s.next();
			if(set.contains(in)) {
				System.out.println((isOpen?"Closed by ":"Opened by ")+in);
				isOpen^=true;
			}else {
				System.out.println("Unknown "+in);
			}
		}
	}
}

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

#define rep(i, n)     for(int i = 0;      i < int(n); ++i)
#define rep3(i, a, b) for(int i = int(a); i < int(b); ++i)
#define all(x)        (x).begin(),(x).end()
#define sz(x)         int(x.size())

typedef long long ll;

using namespace std;

int v[100010][2];

int main(){
  int n, tmp0, tmp1;
  cin >> n;
  rep(i, n/2){
    cin >> tmp0 >> tmp1;
    v[tmp0][0]++;
    v[tmp1][1]++;
  }

  int max0 = 0;
  int sec0 = 0;
  int max1 = 0;
  int sec1 = 0;
  rep(i, 100010){
    if(v[i][0] > v[max0][0]){
      sec0 = max0;
      max0 = i;
    }else if(v[i][0] > v[sec0][0]){
      sec0 = i;
    }
    if(v[i][1] > v[max1][1]){
      sec1 = max1;
      max1 = i;
    }else if(v[i][1] > v[sec1][1]){
      sec1 = i;
    }
  }

  if(max0 != max1){
    cout << n - v[max0][0] - v[max1][1] << endl;
  }else{
    cout << min(n - v[sec0][0] - v[max1][1], n - v[max0][0] - v[sec1][1]) << endl;
  }

  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"-----------------"#x"-----------------\n"
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
                    For(_x,L,R) cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int,int> pii;
LL read(){
    LL x=0,f=0;
    char ch=getchar();
    while (!isdigit(ch))
        f=ch=='-',ch=getchar();
    while (isdigit(ch))
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
const int N=1<<17,mod=1e9+7;
int Pow(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=(LL)x*x%mod)
		if (y&1)
			ans=(LL)ans*x%mod;
	return ans;
}
void Add(int &x,int y){
	if ((x+=y)>=mod)
		x-=mod;
}
void Del(int &x,int y){
	if ((x-=y)<0)
		x+=mod;
}
int Add(int x){
	return x>=mod?x-mod:x;
}
int Del(int x){
	return x<0?x+mod:x;
}
int n,m;
int a[N];
int Fac[N],Inv[N];
void prework(){
	int n=N-1;
	Fac[0]=1;
	For(i,1,n)
		Fac[i]=(LL)Fac[i-1]*i%mod;
	Inv[n]=Pow(Fac[n],mod-2);
	Fod(i,n,1)
		Inv[i-1]=(LL)Inv[i]*i%mod;
}
int C(int n,int m){
	if (m<0||m>n)
		return 0;
	return (LL)Fac[n]*Inv[m]%mod*Inv[n-m]%mod;
}
int dp[20][N];
int main(){
	prework();
	n=read(),m=read();
	For(i,1,m)
		a[i]=read();
	dp[m+1][0]=1;
	Fod(i,m+1,2)
		For(j,0,(1<<n)-1){
			int v=dp[i][j];
			if (!v)
				continue;
			Add(dp[i-1][j],v);
			For(k,0,n-1)
				if (~j>>k&1){
					Del(dp[i-1][j|1<<k],
						(LL)v*C((1<<n)-a[i-1]-j,(1<<k)-1)%mod
						*Fac[1<<k]%mod);
				}
		}
	int ans=0;
	For(i,0,(1<<n)-1)
		Add(ans,(LL)dp[1][i]*Fac[(1<<n)-i-1]%mod);
	ans=(LL)ans*(1<<n)%mod;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 10368