akhauriyash/Code-Regression huggingface dataset:
/**
 *    author  : 𝒌𝒚𝒐𝒎𝒖𝒌𝒚𝒐𝒎𝒖𝒑𝒖𝒓𝒊𝒏
 *    created : 2020-01-10 21:04:34
**/

#include <iostream>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
#include <bitset>
#include <cassert>
#include <cctype>
#include <iomanip>
#include <random>
#include <utility>
#include <chrono>

using namespace std;

using int64 = long long;

template<class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) { os << '{'; size_t n = vec.size(); for (size_t i = 0; i < n; ++i) { os << vec[i]; if (i != n - 1) os << ','; } os << '}'; return os; }
template<class T, class U> std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) { return os << '{' << p.first << " " << p.second << '}'; }
template<class T> std::istream& operator>>(std::istream& is, std::vector<T>& vec) { size_t n = vec.size(); for (size_t i = 0; i < n; ++i) is >> vec[i]; return is; }

#ifdef LOCAL
#define debug(_) cerr << #_ << ": " << (_) << '\n'
#else
#define debug(_) 1728
#endif

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

  int n; cin >> n;
  vector<int> p(n), q(n); cin >> p >> q;

  vector<int> order(n);
  iota(order.begin(), order.end(), 1);

  debug(order);

  int a, b;
  int cnt = 1;

  do {
    bool flag1 = 1, flag2 = 1;
    for (int i = 0; i < n; ++i) {
      if (order[i] != p[i]) flag1 = 0;
      if (order[i] != q[i]) flag2 = 0;
    }
    if (flag1) a = cnt;
    if (flag2) b = cnt;
    ++cnt;
  } while (next_permutation(order.begin(), order.end()));

  debug(cnt);
  debug(a);debug(b);

  cout << abs(a - b) << endl;

  return 0;
}

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

import bisect
a.sort()

center = a[-1]//2

index = bisect.bisect_left(a,center)

if a[index] != center:
    if index > 0 and center - a[index-1] < a[index] - center:
        index -= 1
        
if index == n-1:
    index -= 1
    
print(a[-1],a[index])

Measured memory_bytes: 14052
#include <bits/stdc++.h>
#define DEBUG if(0)
#define lli long long int
#define ldouble long double
using namespace std;

const int maxN = 301;
const lli inf = 1e18;
char s[maxN]; int n;

lli memo[maxN];
lli solve(int i = 0, bool state = 0)
{
  if (i >= n) return 0;
  if (memo[i] == -1)
  {
    lli ans = inf;
    if (i + 1 < n && s[i] != s[i + 1])
      ans = solve(i + 1, 0);
    else
      ans = (i + 1 < n) + solve(i + 2, 1);
    memo[i] = ans;
  }
  return memo[i];
}

int main()
{
  scanf("%s", s);
  lli k; scanf("%lld", &k);
  n = strlen(s); int done = 1, originalSize = n;
  memset(memo, -1, sizeof(memo));
  lli f[4]; f[0] = 0; f[1] = solve();
  for (; done < 3; done ++)
  {
    for (int i = 0; i < originalSize; i ++)
      s[i + originalSize*done] = s[i];
    n = strlen(s);
    memset(memo, -1, sizeof(memo));
    f[done + 1] = solve();
  }
  // printf("%lld %lld %lld\n", f[1], f[2], f[3]);
  if (k <= 3) printf("%lld\n", f[k]);
  else printf("%lld\n", f[1] + ((k - 1) >> 1LL) * (f[3] - f[1]) + ((k - 1) & 1LL ? f[2] - f[1] : 0));

  return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<math.h>

using namespace std;

#define INF 1000000007
#define LINF (1LL << 62)

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


i64 n, a[101010], b[101010];
vector<P> v[101010];
vector<int> vv[101010];
P p[101010];
i64 col[101010];

int main(){
	cin >> n;
	for(int i = 1; i < n; i++){
		cin >> a[i] >> b[i];
		p[i] = P(a[i], b[i]);
		v[a[i]].push_back(P(b[i], i));
		v[b[i]].push_back(P(a[i], i));
	}
	
	queue<int> q;
	q.push(1);
	int ans = 0;
	while(!q.empty()){
		int now = q.front();
		q.pop();
		int cnt = 1;
		set<int> s;
		for(int i = 1; i <= v[now].size(); i++){
			s.insert(i);
		}
		for(int j = 0; j < vv[now].size(); j++){
			s.erase(vv[now][j]);
		}
		for(int i = 0; i < v[now].size(); i++){
			int next = v[now][i].first;
			if(col[v[now][i].second]) continue;
			auto it = s.begin();
			col[v[now][i].second] = *it;
			ans = max(ans, *it);
			vv[next].push_back(*it);
			s.erase(it);
			q.push(next);
		}
	}
	
	cout << ans << endl;
	for(int i = 1; i < n; i++){
		cout << col[i] << endl;
	}
	
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

#define getBit(x,i) (x&(1<<i))
#define setBit(x,i) (x|(1<<i))
#define mem(A,N) memset(A,N,sizeof(A))
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define mp make_pair
#define rep(i, x, y)  for(int i = x; i < y; ++i)
#define Rep(i, x, y)  for(int i = x; i <= y; ++i)
#define srep(i, x, y) for(int i = x; i > y; --i)
#define sRep(i, x, y) for(int i = x; i >= y; --i)
#define all(v) v.begin(),v.end()
#define Sort(x) sort(x.begin(), x.end())
#define f1(i,n) for (int i=1; i<=n; i++)
#define f0(i,n) for (int i=0; i<n; i++)
#define sz(x) ((int)(x).size())
#define len(x) ((int)(x).length())
#define fi first
#define se second

#define linf 0x7FFFFFFFFFFFFFFF
#define inf 0x7FFFFFFF
#define mod 1000000007
#define eps 1e-9
#define Pi 3.14159265358979323846

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define write(x) cerr << #x << " = " << (x) << ", ";
#define writeI0 cerr << "i = " << 0 << ", ";
#define dumpI0 cerr << "i = " << 0 << endl;
#define printSet(s) for(auto it = s.begin(); it!=s.end(); it++) (it==s.begin())? cout << *it : cout << ' ' << *it; cout << endl;
#define printPairSet(s) for(auto it = s.begin(); it!=s.end(); it++) (it==s.begin())? cout << '(' << it->first << ", " << it->second << ')' : cout << " (" << it->first << ", " << it->second << ')'; cout << endl;
#define printVector(x) for(auto it = x.begin(); it!=x.end(); it++) (it==x.begin())? cout << *it : cout << ' ' << *it; cout << endl;
#define printArray(a,x,y) for(auto it = a+x; it != a+y; it++) (it==a+x)? cout << *it : cout << ' ' << *it; cout << endl;
#define PrintArray(a,x,y) for(auto it = a+x; it != a+y+1; it++) (it==a+x)? cout << *it : cout << ' ' << *it; cout << endl;

// ***************** End Of Template ********************

int n, m, k;

bitset<100004> bs;
vi primes;
//int minDiv[100001];

void sieve() {
    bs.set();
    bs[0] = bs[1] = 0;
//    minDiv[0] = 2;

    int upperLimit = 100004;
    int sqrtOfUpperLimit = 316;

//    for(int j = 2; j <= upperLimit; j++)
//        minDiv[j] = j;

    for(int i = 2; i <= sqrtOfUpperLimit; i++)
        if(bs[i])
            for(int j = i * i; j <= upperLimit; j+=i) {
                bs[j] = 0;
//                minDiv[j] = min(minDiv[j], i);
            }

    for(int i = 2; i <= upperLimit; i++)
        if(bs[i]) primes.push_back(i);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    sieve();
    int x; cin >> x;
    cout << primes[lower_bound(primes.begin(), primes.end(), x) - primes.begin()];
    return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class T> istream& operator>>(istream& is,vector<T>& v) { for(T& t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream& os,const vector<T>& v) { for(T t:v){os<<t<<" ";} os<<"\n"; return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
template<class T> inline bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n,c,k;
    cin >> n >> c >> k;
    vi t(n);
    cin >> t;
    sort(all(t));
    int ans = 0;
    int nowt = -1;
    int cnt = 0;
    rep(i,n) {
        if(nowt < t[i]) {
            nowt = t[i]+k;
            cnt = 1;
            ans++;
        } else {
            if(cnt == c) {
                nowt = t[i]+k;
                cnt = 1;
                ans++;
            } else {
                cnt++;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
import math

a,b,c,d=map(int,input().split())

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

gcd_ = int(gcd(c,d))

cc = (c//gcd_ * d)


mm1 = b//c
mm2 = b//d
mmc = b//cc
A1 = b - (mm2 + mm1 - mmc)
# print(A1, b, mm2, mm1, mmc)

a-=1
mm1 = a//c
mm2 = a//d
mmc = a//cc
A2 = a - (mm2 + mm1 - mmc)
# print(A2, a, mm2, mm1, mmc)


print(A1 - A2)

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

int main() {
int  N,X,Y;
  int a = 0;
cin >> N >> X >> Y;
  int A[N];
  for(int i = 1;i < N;i++)A[i] = 0;
  for(int i = 1;i <= N;i++){
  for(int j = 1;j < i;j++){
    a = abs(X - j) + 1 + abs(Y - i);
    A[min(a,i-j)] += 1;
  }
  }
  for(int i = 1;i < N;i++)cout<< A[i] <<endl;
}

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

#define ll long long
#define INF 99999999
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

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

ll lcm(ll number1,ll number2){
	return number1 /gcd(number1,number2) * number2;	
}

int main()
{
    ll A,B;
    cin >> A >> B;
    cout << lcm(A,B) << endl; 
}


Measured memory_bytes: 256
def c():
    N = int(input())
    B = list(map(int, input().split()))

    if N <= 2:
        print(B[0] * 2)
        return
    sum = B[0]
    for i in range(1, N):
        if i == N-1:
            sum += B[N-2]
            break
        sum += min(B[i], B[i-1])

    print(sum)


if __name__ == '__main__':
    c()


Measured memory_bytes: 38544
#include <bits/stdc++.h>
 
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef int ftype;
 
#define pb push_back 
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second 
#define debug(x)  do{cerr<<#x<<": "<<x<<"\n";}while(0)
#define debugv(x) do{cerr<<#x<<": ";for(auto&e: (x))cerr<<e<<" ";cerr<<"\n";}while(0)
#define fori(i, n) for (int i = 0; i < (int)(n); ++i)
#define forn(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n); i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define RETURN(x) do{cout << x << '\n'; return 0;}while(0)
#define FIRSTWIN do{cout << "Monocarp\n"; return 0;}while(0)
#define SECONDWIN do{cout << "Bicarp\n"; return 0;}while(0)

const int MAXN = 2e5+4;
const int MOD = 1e9+7;
const int INF = 1e9+1;

int main() {
#ifdef OJ
    freopen("input.txt", "rt", stdin);
    //freopen("output.txt", "wt", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    fore(i,1,9) fore(j,1,9)
        if(n == i*j) RETURN("Yes");

    RETURN("No");
    return 0;
}


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


int a , b ;

int main (){
	cin >> a >> b;
	
  if(a<=9 && b<=9){
   cout << a*b << endl;
  }
  
  else if(a>9 ||b>9){
    cout << "-1" << endl;
  }
    
}

Measured memory_bytes: 256
N,M,X=map(int,input().split())
L=[list(map(int,input().split())) for i in range(N)]
a=2**N
J=[]
for i in range(a):
    T=True
    K=[0]*(M+1)
    for j in range(N):
        if (i>>j)&1:
            for k in range(M+1):
                K[k]+=L[j][k]
    for j in range(1,M+1):
        if K[j]<X:
            T=False
    if T:
        J.append(K[0])
if len(J)==0:
    print(-1)
else:
    J.sort()
    print(J[0])

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

int main() {
  int n;
  cin>>n;
  for (int k=0; k<=n; k+=4) {
    if ((n - k) % 7 == 0) {
      cout<<"Yes"<<endl;
      return 0;
    }
  }
  cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <climits>
#include <numeric>
#include <cmath>
#include <queue>
#include <sstream>
#include <string.h>

using namespace std;
typedef long long ll;

int main() {
  int n;
  cin >> n;
  vector<int> v(n + 2, 0), t(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    cin >> t[i];
    t[i] += t[i - 1];
  }
  for (int i = 1; i <= n; i++) {
    cin >> v[i];
  }
  vector<double> maxv(2*t[n]+1);
  int ti = 1;
  for (int i = 1; i <= n; i++) {
    while(ti < 2*t[i]) {
      maxv[ti] = v[i];
      ti++;
    }
    maxv[ti] = min(v[i], v[i + 1]);
    ti++;
  }
  
  for (int i = 1; i < 2*t[n]; i++) {
    maxv[i] = min(maxv[i], maxv[i-1] + 0.5);
  }
  for(int i=2*t[n]-1; i>=0; i--){
    maxv[i] = min(maxv[i], maxv[i+1]+0.5);
  }

  double ans = 0;
  for (int i = 0; i < 2*t[n]; i++) {
    ans += 0.5 / 2 *(maxv[i]+maxv[i+1]);
  }
  cout << fixed << ans << endl;
  return 0;
}


Measured memory_bytes: 512
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

typedef long long i64;

const int N = 200000 + 10;
const i64 INF = 0x3f3f3f3f3f3f3f3fLL;

int n, q, y, x[N];

class BIT {
  i64 data[N];
 public:
  BIT() {
    memset(data, 0x3f, sizeof data);
  }
  void update(int p, i64 v) {
    for (; p <= n; p += p & -p) data[p] = std::min(data[p], v);
  }
  i64 query(int p) {
    i64 res = INF;
    for (; p; p ^= p & -p) res = std::min(res, data[p]);
    return res;
  }
} bit[2];

int main() {
  scanf("%d%d%d", &n, &q, &y);
  for (int i = 0; i <= q; ++i) scanf("%d", &x[i]);
  bit[0].update(y, -y);
  bit[1].update(n - y + 1, y);
  i64 tag = 0;
  for (int i = 1; i <= q; ++i) {
    i64 det = llabs(x[i] - x[i - 1]);
    i64 cur = std::min(bit[0].query(x[i]) + x[i], bit[1].query(n - x[i] + 1) - x[i]);
    tag += det, cur -= det;
    bit[0].update(x[i - 1], cur - x[i - 1]);
    bit[1].update(n - x[i - 1] + 1, cur + x[i - 1]);
  }
  i64 ans = INF;
  for (int i = 1; i <= n; ++i) ans = std::min(ans, bit[0].query(i) + i);
  printf("%lld\n", ans + tag);
  return 0;
}


Measured memory_bytes: 4224
import sys
import itertools


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    f = [list(map(int, readline().split())) for _ in range(n)]
    p = [list(map(int, readline().split())) for _ in range(n)]
    mt = - (10 ** 10)
    for it in itertools.product([True, False], repeat=10):
        if sum(it) != 0:
            ls = [0] * n
            for i, iv in enumerate(it):
                for j in range(n):
                    ls[j] += 1 if f[j][i] == 1 and iv else 0
            t = 0
            for i in range(n):
                t += p[i][ls[i]]
            mt = max(mt, t)
    print(mt)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 42972
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) FOR(i, 0, (n))
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define LAR(a, b) ((a)=max((a),(b)))
#define SML(a, b) ((a)=min((a),(b)))
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
template<typename T>
using pque = priority_queue<T, vector<T>, greater<T>>;
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define ALL(a) (a).begin(), (a).end()
#ifdef LOCAL_DEBUG
#define DEBUG(...) printf(__VA_ARGS__)
#else
#define DEBUG(...)
#endif

int main(){
	int s, w; scanf("%d%d", &s, &w);
	if(s <= w) printf("unsafe\n");
	else printf("safe\n");
}


Measured memory_bytes: 3660
#include<iostream>
#include<string>
using namespace std;
int p = 1000000007;
int main()
{
  int n,i;
  long long res;
  string s,t;
  cin >> n;
  cin >> s >> t;
  if(s[0]==t[0]){
    res=3;
    i=1;
  }else{
    res=6;
    i=2;
  }
  for(;i<n;i++){
    if(s[i]==t[i]){
      if(s[i-1]==t[i-1]){
        res*=2;
        res%=p;
      }
    }else{
      if(s[i-1]==t[i-1]){
        res*=2;
      }else{
        res*=3;
      }
      res%=p;
      i++;
    }
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
# include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;

int main(){
  ll N,D;
  cin >> N >> D;
  ll res=0;
  ll a,b;
  rep(i,0,N){
    cin >> a >> b;
    if(a*a+b*b<=D*D) res++;
  }
  cout << res;
  return 0;
}

Measured memory_bytes: 3632
n = int(input())
f = [list(map(int,input().split())) for _ in range(n)]
p = [list(map(int,input().split())) for _ in range(n)]
ans = -float('inf')

o = []
for i in range(2 ** 10):
    op = [0] * 10
    for j in range(10):
        if ((i >> j) & 1):
            op[9-j] = 1
    o.append(op)
o.remove([0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
for openinfo in o:
    #openinfo = [0, 1, 0, 0, 0, 1, 0, 0, 1, 0]
    tmp = 0
    for i in range(n):
        cnt = 0
        for j in range(10):
            if openinfo[j] == 1 and f[i][j] == 1:
                cnt += 1
        tmp += p[i][cnt]
    ans = max(ans,tmp)
print(ans)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
 
int main() {
  int N;
  cin >> N;
  vector<int> P(N);
  rep(i,N){
    cin >> P[i];
  }
  
  int ans=0;
  for(int i=0;i<N-2;i++){
    vector<int> M(3);
    M[0]=P[i];M[1]=P[i+1];M[2]=P[i+2];
    
    sort(M.begin(),M.end());
    if(M[1]==P[i+1])ans+=1;
  }
  cout << ans << endl;
}



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

int main(){
    string s;
    cin >> s;
    int n_1 = 0;
    int n_0 = 0;
    for(int i=0;i<s.size();i++){
        if(s[i] == '1'){
            n_1 ++;
        }
        else{
            n_0 ++;
        }
    }
    cout << min(n_1,n_0)*2 << endl;
    return 0;
}

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

int main() {
	int N, tmp;

	cin >> N;

	N = N % 10;

	if (N == 2 || N == 4 || N == 5 || N == 7 || N == 9) {
		cout << "hon" << endl;
	}
	else if (N == 0 || N == 1 || N == 6 || N == 8) {
		cout << "pon" << endl;
	}
	else {
		cout << "bon" << endl;
	}
	return 0;
}

Measured memory_bytes: 3620
(defun main ()
  (let* ((n (read))
         (a (make-array `(,(+ n 2))))
         (b (make-array `(,(1+ n))))
         (m (make-array `(,(1+ n))))
         (2^n 1)
         (ans 0))
    ; memo
    ; (log (expt 10 8) 2) => 26.575424
    ;
    ; read
    (loop :for i :from 0 :to n
          :do (setf (aref a i) (read)))
    ;
    (setf (aref m n) (aref a n))
    (loop :for i :downfrom (1- n) :to 0
          :do (setf (aref m i) (+ (aref a i) (aref m (1+ i)))))
    ; init 
    (setf (aref a (1+ n)) 0)
    (when (> (aref a 0) 2^n)
      (format t "-1~%")
      (return-from main))
    (incf ans 2^n)
    (setf (aref b 0) (- 2^n (aref a 0)))
    (setf 2^n (* 2 1))
    ;
    (loop :for i :from 1 :to n
          :do (let* ((p (aref b (1- i)))
                     (c (aref a (1+ i)))
                     (_max (min (* 2 p) 2^n (aref m i)))
                     (_min (ceiling (/ c 2))))
                ;(format t "S: ~A P: ~A A: ~A M: ~A ~A~%" ans p (aref a i) _max _min)
                ; ex. case
                (when (or (> _min _max) (> 0 (- _max (aref a i))))
                  (format t "-1~%")
                  (return-from main))
                ;
                (cond ((= i n)
                       (incf ans (aref a i)))
                      (t
                       (incf ans _max)
                       (setf (aref b i) (- _max (aref a i)))
                       (setf 2^n (* 2 2^n))))))
    (format t "~A~%" ans)))
(main)


Measured memory_bytes: 102744
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;

#define MOD 1000000007

int main() {
  ll n;
  cin>>n;
  vector<ll> v;
  rep(i,0,n){
  	ll a;
  	cin>>a;
  	a--;
  	v.pb(a);
  }
  v.pb(-1);
  ll ans = 0;
  rep(i,0,v.sz-1){
  	if(v[i]==i&&v[i+1]==i+1){
  		swap(v[i],v[i+1]);
  		ans++;
  		i++;
  	}
  }
  rep(i,0,v.sz-1){
  	if(v[i]==i){
  		swap(v[i],v[i+1]);
  		ans++;
  	}
  }
  cout << ans << endl;
  return 0;
}


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

typedef long long ll;

int N;

int main() {
    cin >> N;

    string alphabet = "abcdefghijklmnopqrstuvwxyz";
    map<char, int>mp;
    for (int i = 0; i < 26; i++) {
        mp[alphabet[i]] = i;
    }

    queue<pair<string, int>>que;
    que.push(make_pair("a", 0));

    while (true) {
        string x = que.front().first;
        int a = que.front().second;
        if (x.length() == N) {
            break;
        }
        que.pop();
        for (int i = 0; i <= a+1; i++) {
            if (mp[alphabet[i]] >= a) {
                que.push(make_pair(x+alphabet[i], mp[alphabet[i]]));
            } else {
                que.push(make_pair(x+alphabet[i], a));
            }
        }
    }

    while (!que.empty()) {
        string x = que.front().first;
        que.pop();
        cout << x << endl;
    }
}


Measured memory_bytes: 8832
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
static const ll maxLL = (ll)1 << 62;
const int mod=1e9+7;

int n,m;
int a[55],b[55];
bool used[55][55];
bool visited[55];

void dfs(int v){
    visited[v]=true;
    rep(v2,0,n){
        if(used[v][v2]==false)continue;
        if(visited[v2]==true)continue;
        dfs(v2);
    }
}

int main(){
    cin>>n>>m;
    rep(i,0,m){
        cin>>a[i]>>b[i];
        a[i]--,b[i]--;
        used[a[i]][b[i]]=used[b[i]][a[i]]=true;
    }
    int ans=0;
    rep(i,0,m){
        used[a[i]][b[i]]=used[b[i]][a[i]]=false;
        rep(j,0,n)visited[j]=false;
        dfs(0);
        bool bridgh=false;
        rep(j,0,n)if(visited[j]==false)bridgh=true;
        if(bridgh)ans+=1;
        used[a[i]][b[i]]=used[b[i]][a[i]]=true;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
// In the name of God

#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0, _n = (int)(n); i < _n; ++i)
#define int long long
const int N = 1 << 20, lg = 20, mod = 924844033;
int pw(int a, int b) { return b != 0? ll(pw(ll(a) * a % mod, b >> 1)) * (b & 1? a: 1) % mod: 1; }
int rev[N];
vector<int> adj[N];
void NTT(int a[], bool inverse) {
    rep(i, N)
        if (rev[i] > i)
            swap(a[rev[i]], a[i]);
    for (int len = 2; len <= N; len <<= 1) {
        int wn = pw(3, (mod - 1) / len / 2);
        if (inverse)
            wn = pw(wn, mod - 2);
        for (int j = 0; j < N; j += len) {
            int w = 1;
            for (int x = j, y = j + len / 2; y < j + len; ++x, ++y) {
                int u = a[x], v = ll(a[y]) * w % mod;
                a[x] = u + v; 
                a[y] = u - v + mod;
                while (a[x] >= mod)
                    a[x] -= mod;
                while (a[y] >= mod)
                    a[y] -= mod;
                w = ll(w) * wn % mod;
            }
        }
    }
    if (inverse) {
        int div = pw(N, mod - 2);
        rep(i, N)
            a[i] = ll(a[i]) * div % mod;
    }
}

void gen(int bit = lg - 1, int x = 0, int y = 0) {
    if (bit == -1) {
        rev[y] = x;
        return;
    }
    gen(bit - 1, x, y);
    gen(bit - 1, x + (1 << bit), y + (1 << lg - bit - 1));
}

int n, f[N], a[N], b[N], c[N], inv[N], sz[N];

void dfs(int v, int p = 0) {
    sz[v] = 1;
    for (int u : adj[v])
        if (u != p)
            dfs(u, v), sz[v] += sz[u];
    a[sz[v]]++;
    a[n - sz[v]]++;
}
int res[N];
int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    gen();
    f[0] = inv[0] = 1;
    for (int i = 1; i < N; ++i)
        f[i] = f[i - 1] * i % mod, inv[i] = pw(f[i], mod - 2);
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(0);
    for (int i = 0; i < N; ++i)
        a[i] = a[i] * f[i] % mod;
    int maxn = N / 4;
    for (int i = maxn; i >= 0; --i)
        b[i] = inv[maxn - i];
    NTT(a, false);
    NTT(b, false);
    for (int i = 0; i < N; ++i)
        c[i] = a[i] * b[i] % mod;
    NTT(c, true);
    for (int i = 0; i < maxn; ++i)
        res[i] = c[i + maxn];
    for (int i = 1; i <= n; ++i) {
        cout << inv[i] * ((f[n] * (n + 1) % mod * inv[n - i] % mod - res[i] + mod) % mod) % mod<< '\n';
    }
}



Measured memory_bytes: 94080
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
using P = pair<int,int>;

int main()
{
  string s;
  cin >> s;
  vector<int> x;
  vector<char> y;
  int xcnt=0;
  REP(i,s.size()){
    if(s.at(i)!='x'){
      x.push_back(xcnt);
      y.push_back(s.at(i));
      xcnt=0;
    }else{
      xcnt++;
    }
  }
  x.push_back(xcnt);
  
  int flag=0;
  if(y.size()>0){
    REP(i,(y.size()-1)/2+1){
      if(y.at(i)!=y.at(y.size()-1-i)){
        flag=1;
      }
    }
  }else{
    flag=0;
  }

  if(flag==1){
    cout << -1 << endl;
  }else{
    int ans = 0;
    REP(i,(x.size()-1)/2+1){
      ans+=abs(x.at(i)-x.at(x.size()-1-i));
    }
    cout << ans << endl;
  }
}

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

#define debug(x) cout <<"DEBUG"<<" "<< #x << ":" << x << '\n'
#define rep(i,n) for(int_fast32_t i = 0; i < ((int_fast32_t)(n)); i++)   // 0-indexed up
#define rep1(i,n) for(int_fast32_t i = 1; i <= ((int_fast32_t)(n)); i++) // 1-indexed up
#define rrep(i,n) for(int_fast32_t i = ((int_fast32_t)(n)-1); i >= 0; i--)  // 0-indexed down
#define rrep1(i,n) for(int_fast32_t i = ((int_fast32_t)(n)); i >= 1; i--)   // 1-indexed down
#define all(x) (x).begin(),(x).end()

using namespace std;

template<typename T>
using vec = vector<T>;
using i32 = int_fast32_t;
using i64 = int_fast64_t;
using u32 = uint_fast32_t;
using u64 = uint_fast64_t;
using ll = long long;
using ld = long double;
using vi = vec<int_fast32_t>;
using vl = vec<int_fast64_t>;
using vld = vec<ld>;
using vii = vec<vi>;
using PII = pair<int_fast32_t, int_fast32_t>;

template<class T>
using maxheap = std::priority_queue<T>;
template<class T>
using minheap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template<class T,class U> inline bool chmax(T &a, const U &b){if(a<b){a=b;return 1;}return 0;}
template<class T,class U> inline bool chmin(T &a, const U &b){if(a>b){a=b;return 1;}return 0;}

const ld Pi = std::acos(-1.0L);
constexpr ll infll = (1LL<<62)-1;
constexpr int inf = (1<<30)-1;
const int mod = 1000000007;
// const int mod = 998244353;


/*FUNCs=================================================*/


/*MAIN==================================================*/
signed main(){
    double START_TIME = clock();
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
//    cout << fixed << setprecision(15);

    i32 a,b,c,x,y, ans = infll; cin >> a >> b >> c >> x >> y;
    for(i32 i = 0; i <= max<i32>(x,y); i++) {
        chmin(ans, c*2 * i + a * max<i32>(0, x - i) + b * max<i32>(0, y - i));
    }

    cout << ans << '\n';

//     printf("ElapsedTime: %5.3f ms\n",1000*((clock()-START_TIME)/CLOCKS_PER_SEC));
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
// #include <iomanip>

using namespace std;

int main() {
  char str[5];
  scanf("%s", str);

  sort(str, str + 4);

  if (str[0] == str[1] && str[2] == str[3] && str[1] != str[2]) {
    cout << "Yes";
  } else {
    cout << "No";
  }
}


Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
//-std=c++11
#define print(x) printf("%.12f",x);
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i, n) for(int i =0 ; i < n; ++i)
#define repr(i, n) for(int i=n-1;i>=0;i--)
#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 pii pair < int, int >
#define iter ::iterator
#define forit(a) for(it=a.begin();it!=a.end();it++)
typedef vector<int> vi;
typedef  long long ll;
const int inf = int(1e9);
const int mod = 998244353;
const int N = (int)2e5 + 5;

void solve(){
	int a,b,k,cnt=0;
	cin>>a>>b>>k;
	vi v;
	for(int i=1;i<=min(a,b);i++){
		if(a%i==0 && b%i==0)v.pb(i);
	}
	reverse(all(v));
	cout<<v[k-1];
}


int main(){
	Red;
	int t=1;
	//cin>>t;
	while(t--)
	solve();
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<deque>
#include<climits>
#include<cassert>
#include<cmath>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)
#define MAX 110

using namespace std;

int V,E,ans;
vector<int> G[MAX];
int COST[MAX][MAX];
bool used[MAX];

void dfs(int node,deque<int>& deq,int sp){
  if(node >= 15)return;

  if(node >= 2){
    int tmp = [&]()mutable->int{
      int ret = 0;
      int mincost[node];
      rep(i,node) mincost[i] = IINF;
      //for(int& i : mincost)i = IINF;
      for(int i=0;i<node;i++){
	for(int j=i+1;j<node;j++){
	  int cost = COST[deq[i]][deq[j]];
	  if(cost==0)return -1;
	  mincost[i] = min(mincost[i],cost);
	  mincost[j] = min(mincost[j],cost);
	}
      }
      //for(int& i : mincost) ret += i;
      rep(i,node) ret += mincost[i]; 
      return ret;
    }();

    if(tmp != -1)ans = max(ans,tmp);
  }

  REP(i,sp,V){
    if(used[i])continue;
    if(G[i].size() < node)continue;
    used[i] = true;
    deq.push_back(i);
    dfs(node+1,deq,i+1);
    deq.pop_back();
    used[i] = false;
  }
}

int main()
{
  cin >> V >> E;
  int test[5];
  for(int& i : test)i = IINF;
  rep(i,V)G[i].clear();
  rep(i,E){
    int u,v,f;
    cin >> u >> v >> f;
    u--,v--;
    G[u].push_back(v);
    G[v].push_back(u);
    COST[u][v] = COST[v][u] = f;
  }

  deque<int> deq;
  dfs(0,deq,0);
  cout << ans << endl;

  return 0;
}

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

using namespace std;

int main(){
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	while(!(a <= 0) && !(c <= 0)){
		c -= b;
		if(c <= 0)
			break;
		a -= d;
	}
	if(a <= 0)
		cout << "No" << '\n';
	else
		cout << "Yes" << '\n';
}


Measured memory_bytes: 3632
#include<stdio.h>

int A[1000000], n;
int binarySearch(int key){
    int left=0;
    int right=n;
    int mid;
    
    while(left<right){
        mid=(left+right)/2;
        if(key==A[mid]) return 1;
        if(key>A[mid]) left=mid+1;
        else if(key<A[mid]) right=mid;
    }
    return 0;
}

int main(){
    int i, q, k, sum=0;
    scanf("%d", &n);
    for (i=0; i<n; i++){
        scanf("%d", &A[i]);
    }
    scanf("%d", &q);
    for(i=0;i<q;i++){
        scanf("%d", &k);
        if (binarySearch(k)) sum++;
    }
    printf("%d\n", sum);
    
    return 0;
}


Measured memory_bytes: 2984
h,w,x = map(int,input().split())
c = [input() for i in range(h)]

ans = 0
for i in range(1<<h):
    for j in range(1<<w):
        black = 0
        for k in range(h):
            for l in range(w):
                if ((i >> k) & 1) == 0 and ((j >> l) & 1) == 0 and c[k][l] == "#":
                    black += 1
        if black == x:
            ans += 1

print(ans)


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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define pb push_back
#define eb emplace_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j
#define lbidx(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
#define ubidx(x, y) upper_bound(x.begin(), x.end(), y) - x.begin()
#define llbidx(x, y, z) lower_bound(x.begin(), x.end(), z) - lower_bound(x.begin(), x.end(), y) // 二要素間の距離
#define deg2rad(deg) ((((double)deg)/((double)360)*2*M_PI))
#define rad2deg(rad) ((((double)rad)/(double)2/M_PI)*(double)360)
#define Find(set, element) set.find(element) != set.end()
#define Decimal(x) printf("%.10f\n", x) // 小数点を10桁まで表示
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << endl;

typedef pair<int, int> PI;
typedef pair<ll, ll> PLL;

int POWINT(int x, int n) {
  int ret = 1;
  rep(i, 0, n) ret *= x;
  return ret;
};

ll POWLL(int x, int n) {
  ll ret = 1;
  rep(i, 0, n) ret *= x;
  return ret;
};

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

const int INF = 1e9+7;

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

  int H, W, K;
  cin >> H >> W >> K;

  vector<vector<int>> grid(H, vector<int> (W));
  char ch;
  rep(i, 0, H) {
    rep(j, 0, W) {
      cin >> ch;
      grid[i][j] = (int) ch - '0';
    }
  }

  int ans = INF;

  rep(i, 0, (1 << (H-1))) {
    vector<int> tmp;
    tmp.pb(0);
    for (int j = 0; j < H-1; j++) {
      if ((i & (1 << j)) == (1 << j)) {
        tmp.pb(j+1);
      }
    }
    tmp.pb(H);

    map<PI, int> mp; // ホワイトチョコカウント
    vector<PI> v;
    rep(j, 0, tmp.size()-1) {
      mp[make_pair(tmp[j], tmp[j+1])] = 0;
      v.pb(make_pair(tmp[j], tmp[j+1]));
    }

    int tmp_ans = tmp.size() - 2;

    bool possible = true;

    rep(j, 0, W) {
      bool flag = false;
      for (auto pi: v) {
        int w_cnt = 0;
        rep(k, pi.first, pi.second) {
          w_cnt += grid[k][j];
        }
        if (w_cnt > K) {
          possible = false;
        } else if (mp[pi] + w_cnt > K) {
          flag = true;
        }
      }

      if (flag) {
        tmp_ans++;
        for (auto pi: v) {
          int w_cnt = 0;
          rep(k, pi.first, pi.second) {
            w_cnt += grid[k][j];
          }
          mp[pi] = w_cnt;
        }
      } else {
        for (auto pi: v) {
          int w_cnt = 0;
          rep(k, pi.first, pi.second) {
            w_cnt += grid[k][j];
          }
          mp[pi] += w_cnt;
        }
      }
    }

    if (!possible) {
      continue;
    } else {
      ans = min(ans, tmp_ans);
    }
  }

  cout << ans << endl;

  return 0;
};


Measured memory_bytes: 256
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric, std.container, std.range;

void main()
{
    auto abcd = readln.split.to!(long[]);
    auto a = abcd[0];
    auto b = abcd[1];
    auto c = abcd[2];
    auto d = abcd[3];
    writeln(max(a*c, a*d, b*c, b*d));
}

Measured memory_bytes: 2720
#include<bits/stdc++.h>
#define ALL(c) (c).begin(),(c).end()
#define EACH(i,c) for(auto i=(c).begin();i!=(c).end();++i)
using namespace std;
#define int long long


void solve(long long N, std::vector<long long> v){
    priority_queue<double, vector<double>, greater<double>> Q;
    for(int i = 0; i < N; ++i) {
        Q.push(v[i]);
    }

    while(Q.size() > 1) {
        double a = Q.top(); Q.pop();
        double b = Q.top(); Q.pop();

        double c = (a + b) / 2.0;
        Q.push(c);
    }
    printf("%.10f\n", Q.top());
}

signed main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> v(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&v[i]);
    }
    solve(N, std::move(v));
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {

  while(1) {

    int n;
    cin >> n;
    if(n == 0) break;

    int maxd = -1;
    int maxp;
    int p,d1,d2;

    for(int i=0;i<n;i++) {

      cin >> p >> d1 >> d2;

      if(maxd < d1 + d2) {
	maxd = d1+d2;
	maxp = p;
      }
    }

    cout << maxp <<" "<<maxd<< endl;

  }

  return 0;

}
		    

Measured memory_bytes: 1156
#include<stdio.h>

#define N 101

int n,M[N][N];
int color[N],d[N],f[N],time;

void visit(int);

int main(){
  int i,j,v,vnext,k;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    color[i] = 0;
      for(j=0;j<n;j++){
	M[i][j] = 0;;
      }
  }
    
  for(i = 0;i<n;i++){
    scanf("%d %d",&v,&k);
    for(j=0;j<k;j++){
      scanf("%d",&vnext);
      M[v-1][vnext-1] = 1;
    }
  }

  for(i = 0;i<n;i++){
    if(color[i]==0)visit(i);
  }

  for(i=0;i<n;i++){
    printf("%d %d %d\n",i+1,d[i],f[i]);
  }
  return 0;
}

void visit(int u){

  int i;
  color[u]=1;
  d[u]=++time;
  for(i=0;i<n;i++){
    if(M[u][i] == 0)continue;
      if(color[i] == 0)visit(i);
    }
  color[u] = 2;
  f[u] = ++time;
}
  

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

using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}


int main(){
  int M; cin >> M;
  ll ans = 0, rest = 0, dig = 0;
  for (int i = 0; i < M; i++){
    ll D, C; cin >> D >> C;
    rest += D * C; dig += C;
    ans += (rest - 1) / 9; rest %= 9;
    if (rest == 0) rest = 9;
  }
  cout << ans + dig - 1 << endl;

  return 0;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
long long int a[105];
#define mod 1000000007

int main(){
      int n, k;
      cin>>n>>k;
      for(int i=0; i<n; i++)
            cin>>a[i+1];
      vector<int>prefix(k+1, 1);
      int dp[n+1][k+1];
      for(int i=0; i<=n; i++)
            for(int j=0; j<=k; j++)
                  dp[i][j]=0;
      dp[0][0]=1;

      for(int i=1; i<=n; i++){
            vector<int>pre(k+1);

            for(int p=0; p<=k; p++){
                  if(p-a[i]-1<0)
                        dp[i][p]=prefix[p];
                  else {
                        dp[i][p]=(prefix[p]-prefix[p-a[i]-1]+mod)%mod;
                  }
                  //cout<<i<<' '<<p<<' '<<dp[i][p]<<'\n';

                  if(p>0)pre[p]=(dp[i][p]+pre[p-1])%mod;
                  else pre[p]=1;
            }
            prefix=pre;
            /*int sums[k+1];
        sums[0]=dp[i-1][0];
        for(int j=1;j<=k;j++)
        {
            sums[j]=(sums[j-1]+dp[i-1][j])%mod;  ///Calculate the prefix sums for i-1
        }*/
        /*vector<int>pre(k+1);

        for(int j=0;j<=k;j++)
        {
            int tr=prefix[j];  ///Sum of dp[i-1][0...j]
            int unreachable=j-a[i]-1;  ///We need to subtract the sum of the first "unreachable" elements (dp[i-1][0...unreachable])
            if(unreachable>=0)
            {
                tr=(tr-prefix[unreachable]+mod)%mod;  ///Add mod to make sure that "tr-sums[unreachable]" is not negative.
            }
            dp[i][j]=tr;
            if(j>0)pre[j]=(pre[j-1]+dp[i][j]);
            else pre[j]=1;
        }
        prefix=pre;*/
      }
      cout<<dp[n][k];
}

Measured memory_bytes: 43520
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <utility>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <limits.h>
#define int long long
using namespace std;
using P = pair<int, int>;
using ll = long long;
using prique = priority_queue<int>;
const int MOD = 1000000007;
const int INF = LLONG_MAX/3;
signed main(){
    int n,m,q;
    cin>>n>>m>>q;
    int imos[500][500]={};
    for(int i=0;i<m;i++){
        int l,r;
        cin>>l>>r;
        imos[l-1][r-1]++;
    }
    for(int i=0;i<n;i++){
        for(int j=n-2;j>=0;j--){
            imos[j][i]+=imos[j+1][i];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=1;j<n;j++){
            imos[i][j]+=imos[i][j-1];
        }
    }
    for(int i=0;i<q;i++){
        int a,b;
        cin>>a>>b;
        cout<<imos[a-1][b-1]<<endl;
    }
    return 0;
}


Measured memory_bytes: 2816
from itertools import product

H, W, K = map(int, input().split())
c = [input() for _ in range(H)]

result = 0
for a in product([True, False], repeat=H):
    for b in product([True, False], repeat=W):
        t = 0
        for y in range(H):
            if a[y]:
                continue
            for x in range(W):
                if b[x]:
                    continue
                if c[y][x] == '#':
                    t += 1
        if t == K:
            result += 1
print(result)


Measured memory_bytes: 9200
#include<bits/stdc++.h>
#include <math.h>
#include <cmath>
#include <limits>
#include <iostream>
#include <assert.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=10000000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};
struct pos{
	int x,y,cost;
};
int main(){

	ll n;
	cin>>n;
	if(n%2>0){
		cout<<"0"<<endl;
		return 0;
	}
	ll t=10;
	ll ans=0;
	while(t<=n){
		ans+=(n/t);
		t*=5;
	}
	cout<<ans<<endl;
	return 0;

}




Measured memory_bytes: 256
// AOJ Volume 1 Problem 0168 Kannondou

#include <stdio.h>
#include <string.h>

int main(void)
{
    int step[34];
    int i;
    int n;
    
    memset(step, 0, sizeof(step));

    step[1] = step[2] = step[3] = 1;
    
    for (i = 1; i <= 30; i++){
        step[i + 1] += step[i];
        step[i + 2] += step[i];
        step[i + 3] += step[i];
    }
    
    while (1){
        scanf("%d", &n);
        
        if (n == 0){
            break;
        }
        
        printf("%d\n", ((step[n] + 9) / 10 + 364) / 365);
    }
    
    return (0);
}

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

int main(void){
    int n,l;
    cin>>n>>l;
    string s[n];
    for(int i=0;i<n;i++) cin>>s[i];
    sort(s,s+n);
    for(int i=0;i<n;i++) cout<<s[i];
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
double a,b,h,m;
  cin>>a>>b;
  cin>>h>>m;
  double minangle = 6.000000000*m;
double  hourangle = 30.000000000*h+0.500000000*m;
  double angle = abs(minangle-hourangle);
  if(angle>180) {
  	angle = 360.000000000-angle;
  }
  const auto PI = acos(-1);
  double ans = sqrt(a*a+b*b-2.000000000*a*b*cos(angle*PI/180.000000000));
   printf("%.9f", ans);
return 0;
}

Measured memory_bytes: 4076
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
import java.math.BigDecimal;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		BigDecimal tmp = BigDecimal.ZERO;
		int i, j, a, b;
		BigDecimal meu, rinrin, hoga;
		BigDecimal[] array = new BigDecimal[n];
		BigDecimal[] fuga = new BigDecimal[n];
		for(i = 0;i < n;++i){
			array[i] = BigDecimal.valueOf(sc.nextInt());
		}
		Arrays.sort(array);
		for(i = 0;i < n;++i){
			meu = array[i];
			for(j = 0;j < n;++j){
				if(j != i){
					if((i == n-1 && j == n-2) || (j == n-2 && i == n-1)){
						a = 2;
					}else if(i == n-1 || j == n-1 || i == n-2 || j == n-2){
						a = 1;
					}else{
						a = 0;
					}
					rinrin = array[j];
					fuga = array.clone();
					fuga[j] = BigDecimal.ZERO;
					fuga[i] = BigDecimal.ZERO;
					
					hoga = fuga[n-1-a].add(fuga[n-2-a]).divide(meu.subtract(rinrin).abs(), 8, BigDecimal.ROUND_HALF_UP);
					if(tmp.compareTo(hoga) < 0) tmp = hoga;
				}
			}
		}
		
		System.out.println(tmp);
	}
}

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

typedef long long ll;
typedef long double ld;
typedef vector<vector<int>> Graph;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
#define pi 3.14159265359
#define inf 2147483647
#define INF 9223372036854775807
#define mod 1000000007
#define mod2 998244353

int main() {
	int N; cin >> N;
    vector<ll> f(N + 1);
    for(int x = 1; x <= 100; x++) {
        for(int y = 1; y <= 100; y++) {
            for(int z = 1; z <= 100; z++) {
                ll n = x * x + y * y + z * z + x * y + y * z + z * x;
                if(n <= N) f[n]++;
            }
        }
    }
    for(int i = 1; i <= N; i++) cout << f[i] << endl;
	return 0;
}

Measured memory_bytes: 3572
// by The_One_Solver
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
long long  x,v,n,arr[1000001];
map<long long,long long>mp;
set<long long>st;
set<long long>::iterator it;
long long comb(long long m)
{
    return (m*((m-1))/2);
}
int main()
{
    cin>>n;

    for(long long i=0;i<n;i++)
    {
        cin>>arr[i];
        mp[arr[i]]++;
        st.insert(arr[i]);
    }
     for(long long i=0;i<n;i++)
     {
        mp[arr[i]]--;
        if(i==0)
        {
            for(it=st.begin();it!=st.end();it++)
           {
             v+=comb(mp[*it]);
           }
        }
        else
        {
            mp[arr[i]]++;
            x=comb(mp[arr[i]]);
            v-=x;
            mp[arr[i]]--;
            x=comb(mp[arr[i]]);
            v+=x;
        }
        cout<<v<<endl;
        if(i==0)
        {
            x=comb(mp[arr[i]]);
            v-=x;
            mp[arr[i]]++;
           v+=comb(mp[arr[i]]);
        }
        if(i!=0)
        {
            v-=x;
          mp[arr[i]]++;
          v+=comb(mp[arr[i]]);
        }
     }

}


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

ll dp[405][405];
ll n;
vector<ll> a(405);
vector<ll> A(405);

ll f(ll a,ll b){
  if (dp[a][b]!=INF)return dp[a][b];

  rep(i,n){
    if (i>=a and i<b)
    dp[a][b]=min(dp[a][b],f(a,i)+f(i+1,b));
  }

  if (dp[a][b]==INF)dp[a][b]=0;
  dp[a][b]+=(A[b+1]-A[a]);
//  cout<<dp[a][b]<<"a"<<a<<"b"<<b<<endl;
  return dp[a][b];
}

int main() {
  cin>>n;

  rep(i,n)cin>>a[i];
  rep(i,405)rep(j,405)dp[i][j]=INF;
//  A[0]=0;
  rep(i,n){
    A[i+1]=A[i]+a[i];
  }
  ll ans=f(0,n-1);
  cout<<(ans-A[n])<<endl;
}


Measured memory_bytes: 4944
#include<stdio.h>
int main(void)
{
    int a,b;
    scanf("%d%d",&a,&b);
    if(a<b)
        printf("a < b\n");
    else if(a>b)
        printf("a > b\n");
    else if(a==b)
        printf("a == b\n");
    return 0;
}


Measured memory_bytes: 2108