akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<math.h>
void merge(int [],int,int,int);
void mergesort(int [],int, int);

int t;
int main() {
	int n,i;
	int s[500000];
	
	scanf("%d",&n);
	
	for(i=0;i<n;i++) {
		scanf("%d",&s[i]);
		}
		
		mergesort(s,0,n);
		
		for(i=0;i<n;i++) {
			printf("%d",s[i]);
			if(i!=n-1) printf(" ");
			
		}
		 printf("\n");
		printf("%d\n",t);
		return 0;
		
		
}
		
		void merge(int s[],int left, int mid, int right) {
			int n1,n2,i ,j,k;
			n1=mid-left;
			n2=right-mid;
			int L[n1],R[n2];
			for(i=0;i<n1;i++)
				L[i]=s[left+i];

			for(i=0;i<n2;i++)
			R[i]=s[mid+i];
			
			L[n1]=INFINITY;
					R[n2]=INFINITY;
					
						
			i=0;
			j=0;
			
			
			for(k=left;k<right;k++) {
				 if (L[i] <= R[j]) {
				 	t++;
      s[k] = L[i];
      i +=1;
		      }
    else {
    	t++;
      s[k] = R[j];
      j +=1;
      }
      
      }
      }
      
      
      
      void mergesort(int s[],int left, int right) {
      	int mid;
      	if (left+	1 < right) {
    mid = (left	 + right)/2;
    mergesort(s,left, mid);
    mergesort(s,mid, right);
   merge(s,left, mid, right);
    }
    }
			
			
			


Measured memory_bytes: 5684
n = int(input())
retu = input().split()
for i in range(0,n):
    retu[i] = int(retu[i])
retuS = sorted(retu)
resultA = []
for j in range(retuS[0],retuS[n-1]+1):
    result = 0
    for k in retu:
        result = result + (k - j) * (k - j)
    resultA.append(result)
resultA.sort()
print(resultA[0])

Measured memory_bytes: 3064
sx,sy,tx,ty = map(int,input().split())

one = ("U"*(ty-sy))+("R"*(tx-sx))
two = ("D"*(ty-sy))+("L"*(tx-sx))
three = "L"+("U"*(ty-sy+1))+("R"*(tx-sx+1))+"D"
four = "R"+("D"*(ty-sy+1))+("L"*(tx-sx+1))+"U"

print(one+two+three+four)

Measured memory_bytes: 3060
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
#import numba

def sum_between(a, b):
    if a > b:a, b = b, a
    return (b-a+1) * (b+a) // 2

def run():
    N = int(input())
    n_dots = 0
    for i in range(1, N+1):
        n_dots += (1+i) * i // 2
    #print(n_dots)
    ans = (N-1) * (N+1) * N // 2
    #print(ans)
    lr = list(map(int, read().split()))
    l = lr[::2]
    r = lr[1::2]
    for l,r in zip(l, r):
        if l > r: l,r = r,l
        tmp = 0
        if l > 1: tmp += sum_between(r-1, r-l+1)
        tmp += r-l
        tmp += sum_between(N-l, 1)
        #print(tmp)
        ans -= tmp

    print(n_dots - ans)


    ans = (N-1) * N * N


if __name__ == "__main__":
    run()

Measured memory_bytes: 57188
#include<bits/stdc++.h>
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define PB push_back
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
ll n;
vi a,dp;
ll fun(ll i)
{
    if(dp[i]!=-1)
        return dp[i];
    if(i==n-2)
        return dp[i]=abs(a[i]-a[i+1]);
    if(i>=(n-1))
        return 0;
    return dp[i]=min(abs(a[i]-a[i+1])+fun(i+1),abs(a[i]-a[i+2])+fun(i+2));
}
int main() {
    SPEED;
    cin>>n;
    for(ll i=0;i<n;i++)
    {
        ll x;
        cin>>x;
        a.PB(x);
        dp.PB(-1);
    }
    cout<<fun(0)<<endl;
    return 0;
}

Measured memory_bytes: 4332
#include <stdio.h>
int main() {
	int a, b;
	scanf("%d%d", &a, &b);
	if (a > 0) {
		printf("Positive\n");
	} else if (a <= 0 && 0 <= b) {
		printf("Zero\n");
	} else {
		if ((b - a + 1) % 2 == 0) {
			printf("Positive\n");
		} else {
			printf("Negative\n");
		}
	}
	return 0;
}

Measured memory_bytes: 128
/**
 * author:    Ziel
 * created:   19.04.2020 11:10:02
**/

// ~zaletaet~

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>

#define fi first
#define se second
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back

using namespace std;

using ll = long long;
using ull = unsigned long long;
// using big = __int128_t; // -10^38...10^38
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;

const ll N = 1e5 + 123, MOD = 1e9 + 7, oo = 1e9 + 9, INF = 1e18 + 9;
const double EPS = 1e-9, PI = acos(-1); // 3.14159265358979323846
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1}, dy[] = {0, 0, 1, -1, 1, -1, -1, 1};

main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	
	int n, m;
	cin >> n >> m;
	
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		a[i] %= m;
	}
	
	vector<ll> sum(n);
	sum[0] = a[0];
	for (int i = 1; i < n; i++) {
		sum[i] = sum[i - 1] + a[i];
		sum[i] %= m;
	}
	
	ll ans = 0;
	unordered_map<int, int> mp;
	mp[0]++;
	for (int i = 0; i < n; i++) {
		ans += mp[sum[i]];
		mp[sum[i]]++;
	}
	
	cout << ans;
	return 0;
}



Measured memory_bytes: 4876
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    ll X,T;
    cin >>X>>T;
    
    cout << max(X-T,ll(0)) << endl;


    return 0;
    

}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1LL << 60;

int main() {
    int N, K; cin >> N >> K;
    map<int, int> m;
    for (int i = 0; i < N; i++) {
        int x;
        scanf("%d", &x);
        m[x]++;
    }

    vector<int> A;
    for (auto p: m) {
        A.push_back(p.second);
    }

    int all = A.size();
    int sum = 0;
    sort(A.begin(), A.end());
    for (int i = 0; i < all - K; i++) {
        sum += A[i];
    }

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

Measured memory_bytes: 10748
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

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

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))


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

    int n;
    cin >> n;

    s64 ans = 1;
    vs64 a(n);
    rep (i, n)
    {
        cin >> a[i];
        if (a[i] == 0)
        {
            cout << "0\n";
            return 0;
        }
    }

    s64 lim = 1e18;
    rep (i, n)
    {
        if (ans > lim / a[i] || ans * a[i] < 0 || ans * a[i] > lim)
        {
            cout << "-1\n";
            return 0;
        }
        ans *= a[i];
    }

    if (ans > lim || ans < 0) ans = -1;

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



Measured memory_bytes: 3960
/**********************************************
 * author : deepak nayan
 * file   : e:/Solutions/atcoder/abc086_a.cpp
 * time   : Thu Apr 30 16:12:44 2020
 * quest  : A - Product
 *********************************************/
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int a, b;
  cin >> a >> b;
  cout << ((a & 1) && (b & 1) ? "Odd" : "Even") << "\n";
  return 0;
}


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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll N, M, X; 
    cin >> N >> M >> X;
    vector < vector<ll> > books(N, vector<ll> (M));
    vector <ll> cost(N);
    loop(i,0,N)
    {
        cin >> cost[i];
        loop(j,0,M) cin >> books[i][j];    
    }
    bool achieve=false;
    ll mincost = pow(10,9);
    loop(b, 0, pow(2,N))
    {
        ll curcost=0;
        vector <ll> skill(M,0);
        loop(j,0,N)
        {
            if (b & (1<<j)) 
            {
                curcost += cost[j];
                loop(k,0,M) {
                    skill[k]+=books[j][k];
                }
            }
        }
        bool curP=true;
        loop(k,0,M) if (skill[k]<X) {
            curP=false; break;
        }
        if (curP) {
            achieve=true;
            mincost=min(mincost, curcost);
        }
    }
    if (!achieve) {
        cout << -1 << "\n";
        return 0;
    }
    cout << mincost << "\n";
    return 0;
}

Measured memory_bytes: 4096
from collections import deque
h,w = map(int,input().split())
dx = [1,-1,0,0]
dy = [0,0,1,-1]
ans = 0
maze = []
for i in range(h):
    maze.append(list(input()))
for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            d = [[-1 for a in range(w)] for b in range(h)]
            dq = deque([(j,i)])
            d[i][j] = 0
            while dq:
                x,y = dq.popleft()
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[ny][nx] != "#" and d[ny][nx] == -1:
                        dq.append((nx,ny))
                        d[ny][nx] = d[y][x]+1
                        ans = max(ans,d[ny][nx])
print(ans)

Measured memory_bytes: 3316
let pr x = print_endline (string_of_int x)

let explode s =
  let rec exp i l =
    if i < 0 then l else exp (i - 1) (s.[i] :: l) in
  exp (String.length s - 1) []

let solve seq =
  let len = List.length seq in
  let (_,_,res) = List.fold_left (fun (cnt,pre,mv) x ->
                      if x != pre then
                        (cnt+1,x,min mv (max cnt (len - cnt)))
                      else (cnt+1,x,mv)) (0,List.hd seq,len) seq in res

let () = input_line stdin
         |> explode 
         |> solve
         |> pr


Measured memory_bytes: 6144
#include <iostream>
#include <cstring>
#include <stack>
#include <cstdlib>
#include <queue>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <iterator>
#include <set>
#include <map>
#include <utility>
#include <iomanip>
#include <ctime>
#include <sstream>
#include <bitset>
#include <deque>
#include <limits>
#include <numeric>
#include <functional>
#define gc getchar()
#define mem(a) memset(a,0,sizeof(a))
#define mod 1000000007
#define sort(a,n,int) sort(a,a+n,less<int>())
using namespace std;
typedef long long ll;
typedef char ch;
typedef double db;
using namespace std;
ch a[5][10];
int main()
{
    while(~scanf("%s",a[0]))
    {
        scanf("%s",a[1]);
        if(a[0][0] == a[1][2] && a[0][1] == a[1][1] && a[0][2] == a[1][0])
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
int lvl[8]={},god=0;
void judge(int s)
{
	if(s>=1&&s<=399) lvl[0]++;
	else if(s>=400&&s<=799) lvl[1]++;
	else if(s>=800&&s<=1199) lvl[2]++;
	else if(s>=1200&&s<=1599) lvl[3]++;
	else if(s>=1600&&s<=1999) lvl[4]++;
	else if(s>=2000&&s<=2399) lvl[5]++;
	else if(s>=2400&&s<=2799) lvl[6]++;
	else if(s>=2800&&s<=3199) lvl[7]++;
	else god++;
}
int main()
{
	int n,s,min=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&s);
		judge(s);
	}
	for(int i=0;i<8;i++)
		if(lvl[i]>0)
			min++;
	if(min==0) printf("1 %d\n",god); //特判 全部为神仙时最少一种颜色
	else printf("%d %d\n",min,min+god);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    scanf("%d %d",&a,&b);
    if(a>b){
        if((a==13)&&(b==1))
            printf("Bob");
        else
            printf("Alice");
    }
    else if(b>a){
        if((b==13)&&(a==1))
            printf("Alice");
        else
            printf("Bob");
    }
    else
        printf("Draw");
    return 0;
}


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

int main() {
  string w;
  cin >> w;
  sort(w.begin(), w.end());
  
  bool flag = true;
  int c = 1;
  for(int i = 0;i<w.size()-1;i++){
    
    if(w[i] == w[i+1]) c++;
    else {
      if(c%2 == 1){
        flag = false;
        break;
      }
      c = 1;
    }
  }
  if(w[w.size()-1] != w[w.size()-2]) flag =false;
  
  if(flag) cout << "Yes" << endl;
  else cout << "No" << endl;
}
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <numeric>
typedef long long ll;
#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;

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

    int R, G, B, N;
    cin >> R >> G >> B >> N;

    int res = 0;
    for(int ri = 0; ri <= N; ri+=R) {
        for(int gi = 0; gi <= N-ri; gi+=G) {
            int b = N-ri-gi;
            if (b % B != 0) continue;
            ++res;
        }
    }

    cout << res << "\n";
}

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

int main()
{
	int n, k, m = 1, j = 0, mt = 0, mx = 1;
	string s;

	cin >> n >> k >> s;

	queue<pair<int, int>> t;

	for (int i = 0; i < n - 1; i++) {
		if (s[i] == '0') {
			if (s[i + 1] == '0')
				m++;
			else {
				t.push(make_pair(0, m));
				mt += m;
				m = 1;
				j++;
			}
		}
		else {
			if (s[i + 1] == '1')
				m++;
			else {
				t.push(make_pair(1, m));
				mt += m;
				m = 1;

				if (j == k)
					mx = mt;

				if (j == k + 1) {
					if (t.front().first == 1) {
						mt -= t.front().second;
						t.pop();
					}
					if (t.front().first == 0) {
						mt -= t.front().second;
						t.pop();
						j--;
					}

					if (mx < mt)
						mx = mt;
				}
			}
		}
	}

	mt += m;

	if (s[n - 1] == '0')
		j++;

	if (j <= k)
		mx = n;
	else {
		if (t.front().first == 1) {
			mt -= t.front().second;
			t.pop();
		}
		if (t.front().first == 0)
			mt -= t.front().second;

		if (mx < mt)
			mx = mt;
	}

	cout << mx << endl;
	
	return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (long long i = 0; i < n; i++)
#define RREP(i, n) for (long long i = n - 1; 0 <= i; i--)
#define FOR(i, start, end) for (long long i = start; i < end; i++)
#define RFOR(i, start, end) for (long long i = start - 1; 0 <= i; i--)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1'000'000'007
using ll = long long;
using namespace std;
const int INF32       = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7        = 1'000'000'007;
const int MOD9        = 1'000'000'009;
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;
}
void print() { std::cout << '\n'; }
template <class H, class... T> void print(H &&head, T &&... args) {
    std::cout << head;
    sizeof...(args) == 0 ? std::cout << "" : std::cout << ' ';
    print(std::forward<T>(args)...);
}
template <class T> void print(std::vector<T> &v) {
    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i];
        i == v.size() - 1 ? std::cout << '\n' : std::cout << ' ';
    }
}
template <class T> void print(std::vector<std::vector<T>> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            std::cout << v[i][j];
            j == v[i].size() - 1 ? std::cout << '\n' : std::cout << ' ';
        }
    }
}

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

    int N;
    cin >> N;
    vector<int> a(N);
    for (auto &&i : a) {
        cin >> i;
    }
    SORT(a);
    ll ans = accumulate(ALL(a), 0) - a[a.size() - 1] / 2;
    print(ans);

    return 0;
}

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

using namespace std;
/**
********************************************************************
******************* Author:Bisnu sarkar ****************************
********************************************************************
**/

#define ull            unsigned long long
#define ll             long long
#define vi             vector<int>
#define pb             push_back
#define mp             make_pair
#define pii            pair<int,int>
#define vit            vector<int> :: iterator
#define sit            set<int> :: iterator
#define vrit           vector<int> :: reverse iterator
#define ff             first
#define ss             second

#define what_is(x)     cerr << #x << " is " << x << endl;

///*....Debugger....*/

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it)
{
    cout << endl ;
}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
    cerr << *it << " = " << a << ' ' ;
    err(++it, args...);
}

int dx[8]= {1,0,-1,0,-1,-1,1,1};
int dy[8]= {0,1,0,-1,-1,1,-1,1};
int ini()
{
    int x;
    scanf("%d",&x);
    return x;
}
long long inl()
{
    long long x;
    scanf("%lld",&x);
    return x;
}

const int N = (int) 1e6 + 5;
const int M = (int) 1e9 + 7;
const double pi=2* acos(0.0);
int num(char c){
    return c-'0';
}
int main()
{
    string s;
    cin>>s;

    int n1=num(s[0])*10 + num(s[1]);
    int n2=num(s[2])*10 + num(s[3]);
    if((n1>=1 and n1<=12) and (n2>=1 and n2<=12)){
        cout<<"AMBIGUOUS"<<endl;
    }
    else if((n1>=1 and n1<=12)){
        cout<<"MMYY"<<endl;
    }
     else if((n2>=1 and n2<=12)){
        cout<<"YYMM"<<endl;
    }
    else{
        cout<<"NA"<<endl;
    }



    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a,b,c,d,e,i,m;
cin >> b >> a;
int l=-1;
long long sum=0;
vector<int>vec;
while(a--)
{
    cin >> d;
    if(l==-1)
        m=d;
    if(l!=-1)
    {
        vec.push_back(abs(l-d));
    }

    l=d;
}
l=abs(l-b);
vec.push_back(abs(l+m));
sort(vec.begin(),vec.end());
for(i=0;i<vec.size()-1;i++)
    sum+=vec[i];
cout << sum << endl;
}


Measured memory_bytes: 1400
n = 100003
a = [False]*2 + [True]*(n-1)
for i in range(2, int(n**.5)+1):
    if not a[i]:
        continue
    for j in range(i*2, n+1, i):
        a[j] = False
b = [i for i in range(n+1) if a[i]]

x = int(input())
print(min(i for i in b if i>=x))

Measured memory_bytes: 4596
#include<bits/stdc++.h>
  using namespace std;
   
  #define ll long long
  #define pb push_back
  #define mp make_pair
  #define ff first
  #define ss second


   
void func(){

ll n,m;
cin>>n>>m;

vector< ll > a;

ll sum=0;

for(int i=0;i<n;i++){
  ll temp;
 
  cin>>temp;
   sum = sum +temp;
  a.pb(temp);
}

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

ll j=n-1;
for(int i=0;i<m;i++){
  if(a[j]<ceil(1.0*sum/(4*m))){
    cout<<"No"<<endl;
    return;
  }
  j--;
}
cout<<"Yes"<<endl;





}
   
   
  int main(){
          ios_base::sync_with_stdio(false);
          cin.tie(0);
          cout.tie(0);
   
       /* #ifndef ONLINE_JUDGE
        freopen("input.txt", "r" , stdin);
        freopen("output.txt", "w" , stdout);
        #endif*/
   
     ll t=1;
     //cin>>t;
     while(t--)
     func();
   }

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

int n;
long double p[3000];
long double memo[3010][3010];

long double dp(int i, int j){
  if(j == 0) return 1.0;
  if(i == n) return 0.0;
  if(memo[i][j] != -1) return memo[i][j];

  return memo[i][j] = dp(i+1,j-1) * p[i] + dp(i+1, j)*(1-p[i]);
}

int main(){
  cin >> n;

  for(int i = 0;i < n;i++){
    cin >> p[i];
  }

  for(int i = 0;i < 3010;i++){
    for(int j = 0;j < 3010;j++){
      memo[i][j] = -1.0;
    }
  }

  printf("%0.15Lf\n", dp(0, n/2+1));

  return 0;
}

Measured memory_bytes: 142080
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;
int main()
{
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
  long long a, b;
  cin >> a >> b;
  if(abs(a - b) <= 1){
    cout << "Brown";
  }else{
    cout << "Alice";
  }
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct Node{
  int l;
  struct Node *ri;
  struct Node *le;
  struct Node *pa;
};

struct Node *root, *NIL;

void Insert(int);
void Inorder(struct Node *);
void Preorder(struct Node *);

int main(){
  int a1 = 0, a2 = 0;
  int i,h,valu,findnum;
  char C1[10],C2[10]="insert",C3[10]="print";

  scanf("%d",&h);

  for(i=0;i<h;i++){
    scanf("%s",C1);

    if(strcmp(C1,C2)==0) a1=1;
    if(strcmp(C1,C3)==0) a2=1;

    if(a1==1){
      scanf("%d",&valu);
      Insert(valu);
      a1 = 0;
    }
    else if(a2==1){
      a2=0;
      Inorder(root);
      printf("\n");
      Preorder(root);
      printf("\n");
    }

  }
  return 0;
}

void Insert(int h){
  struct Node *x = root;
  struct Node *y=NIL;
  struct Node *z;

  z = (struct Node *)malloc(sizeof(struct Node));
  z ->l = h;
  z->le=NIL;
  z->ri=NIL;

  while(x != NIL){
    y=x;
    if(z->l<x->l){
      x=x->le;
    }
    else{
      x=x->ri;
    }
  }

  z->pa=y;
  if(y==NIL){
    root = z;
  }
  else{
    if(z->l<y->l){
      y->le=z;
    }
    else{
      y->ri=z;
    }
  }
}

void Inorder(struct Node *x){
  if(x == NIL)return;
  Inorder(x -> le);
  printf(" %d",x -> l);
  Inorder(x -> ri);
}

void Preorder(struct Node *y){
  if(y==NIL)return;
  printf(" %d",y -> l);
  Preorder(y->le);
  Preorder(y->ri);
}

struct Node * Find(struct Node *x, int h){
  while(x != NIL && h!= x -> l){
    if( h<x -> l )x = x->le;
    else x = x->ri;
  }
  return x;
}



Measured memory_bytes: 25244
import java.util.Scanner;

 
public class Main {
 
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		char[] s = sc.next().toCharArray();
		char[] t = sc.next().toCharArray();
		
		for(int i = 0; i < n; i++) {
			System.out.print(s[i]);
			System.out.print(t[i]);
		}
		sc.close();
	}
}
	

Measured memory_bytes: 35736
#include <iostream>
#include <queue>
#include <stack>
using namespace std;

int main()
{
        queue<int> op;
        queue<int> carrec;
        stack<int> car;
        int ops;
        int reccar;

        while(cin >> ops){
                op.push(ops);
        }

        while(!op.empty()){
                ops = op.front(); op.pop();
                if(ops != 0){
                        car.push(ops);
                }else if(ops == 0){
                        reccar = car.top();
                        carrec.push(reccar);
                        car.pop();
                }
        }

        while(!carrec.empty()){
                cout << carrec.front() << endl;
                carrec.pop();
        }

        return 0;
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;
    
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 
#define U_MAP unordered_map<ll,ll>
#define pq priority_queue<ll>
#define rpq priority_queue<ll,vector<ll>,greater<ll>>
#define p_b push_back
    
ll n,cnt,ans,a,b,c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k,h1,h2,k1,k2;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};
    
//-------------------------↓↓↓↓↓↓------------------------
    
//------ 自分を天才だと信じる ------
    
int main(void){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    
    cin>>h1>>h2>>k1>>k2>>a>>b>>c>>d;
    tmp=h1*a+(h1/10)*c+h2*b+(h2/20)*d;
    tmpp=k1*a+(k1/10)*c+k2*b+(k2/20)*d;
    if(tmp==tmpp)Cout("even");
    else if(tmp>tmpp)Cout("hiroshi");
    else Cout("kenjiro");
    return 0;
}


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

using namespace std;


#define ss second
#define ff first
#define int long long
//#define double long double
#define pb push_back

const int N = 2e6 + 1, MOD = 1e9 + 7, mod = 998244353, INF = 3e17;

mt19937 Flash_new_51(51515);

using vi = vector <int>;
using vp = vector <pair <int, int>>;

int n, A, B, C, D, kol = 0, imax = -1;
string s;

signed main() {
   cin.tie(0);
   ios_base::sync_with_stdio(0);
   cin >> n >> A >> B >> C >> D >> s;
   A--, B--, C--, D--;
   for (int i = 0; i < n; i++) {
        if (s[i] == '#') kol++;
        else kol = 0;
        if (kol == 2) imax = i;
   }
   if ((A <= imax && imax <= C) || (B <= imax && imax <= D)) {
     cout << "No";
     return 0;
   }
   if (C > D) {
        for (int i = B; i <= min(D, (int)s.size() - 2); i++) {
            if (s[i - 1] == '.' && s[i] == '.' && s[i + 1] == '.') {
                cout << "Yes";
                return 0;
            }
        }
        cout << "No";
        return 0;
   }
   cout << "Yes";

}


Measured memory_bytes: 592
from collections import Counter
n = int(input())
v = list(map(int, input().split()))
gu = v[::2]
ki = v[1::2]
ans = 0
k,g = False,False

###全部同じなら全長の半分,
# 最頻値が同じなら2番目を比べる
if v.count(v[0]) == n:
    ans += n // 2
else:
    kic = Counter(ki)
    guc = Counter(gu)
    k1 = kic.most_common(2)
    g1 = guc.most_common(2)
    if k1[0][0] == g1[0][0]:
        if k1[1][1] < g1[1][1]:
            g = True
        else:
            k = True

    kic = list(kic.values())
    guc = list(guc.values())
    kic.sort(reverse = True)
    guc.sort(reverse = True)
    if len(kic) != 1:
        if k:
            ans += kic[0]
            ans += sum(kic[2::])
        else:
            ans += sum(kic[1::]) 
    if len(guc) != 1:
        if g:
            ans += guc[0]
            ans += sum(guc[2::])
        else:
            ans += sum(guc[1::])

print(ans)

Measured memory_bytes: 19040
fn main() {
    proconio::input! { mut n: u64, }

    let mut r = String::new();
    while n > 0 {
        n -= 1;
        r.insert(0, ((n % 26) as u8 + b'a') as char);
        n /= 26;
    }
    println!("{}", r);
}


Measured memory_bytes: 2152
#include "bits/stdc++.h"
using namespace std;
#define mod 1000000007
#define all(c) begin(c),end(c)
template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
using ll = long long;
using vi = vector<int>; using vs = vector<string>;
int dd[] = { 0, 1, 0, -1, 0 }; //→↓←↑

void solve()
{
	int L = 7368791+10;
	int M, N;
	while (cin >> M >> N, M)
	{
		vector<bool> H(L);
		int cnt = 0;
		for (int i = M; i < L; i++)
		{
			if (!H[i]) {
				cnt++;
				if (cnt == N + 1)
				{
					cout << i << endl;
					break;
				}
				H[i] = true;
				int j = 2 * i;
				while (j < L)
				{
					H[j] = true;
					j += i;
				}
			}
		}
	}
}

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


Measured memory_bytes: 4028
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <random>
#include <chrono>
#include <queue>
#include <math.h>
#include <string>
#include <sstream>

using namespace std;


 
int main(){
    string n;
    int K;
    cin >> n >> K;
    int p = n.size();
    long dp[p+10][4][2];//桁数、０でない個数、N超えてるか判定(０でわからん、１でOK）
    
    //初期化
    for(int i=0;i<p+1;i++){
        for(int j=0;j<4;j++){
            for(int k=0;k<2;k++) dp[i][j][k]=0;
        }
    }
    dp[0][0][0]=1;
    //桁見ていく
    for(int i=0;i<p;i++){
        int lead=n.at(i)-'0';
        for(int j=0;j<4;j++){
            for(int k=0;k<2;k++) {
                
                //次の桁の数
                for(int a=0;a<10;a++){
                    int ni,nj,nk;
                    ni=i+1;
                    nj=j;
                    nk=k;
                    if(a!=0){
                        nj++;
                    }
                    if(nj>K){
                        continue;
                    }
                    if(k==0 && a<lead){
                        nk=1;
                    }
                    if(k==0 && a>lead){
                        continue;
                    }
                    
                    dp[ni][nj][nk]+=dp[i][j][k];
                }
            }
        }
    }
    cout << dp[p][K][0]+dp[p][K][1] << endl;
}

    



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		double det = 100;
		int i;
		double sum = det;
		for(i = 0; i < n; i++) {
			sum = Math.ceil(sum * 1.05);
		}
		System.out.println((int)sum * 1000);

		scanner.close();
	}

}



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

int dp[5005][5005];
int n;
string s;
typedef long long ll;
const int mod = 1e9+7;

int pkt(ll b, ll e) {
  ll res = 1;
  while (e > 0) {
  	  if (e&1) {
  	  	  res *= b;
  	  	  res %= mod;
  	  }
  	  b*=b;
  	  b%=mod;
  	  e>>=1;
  }
  return res;
}

int f(int pos, int left) {
  if (left == 0) return pos == s.length();
  int &ret = dp[pos][left];
  if (ret>=0) return ret;
  ret = 0;
  ret += 2*f(pos+1, left-1);  ret %= mod;
  if (pos > 0) ret += f(pos-1, left-1);
  else ret += f(pos, left-1);
  ret %= mod;
  return ret;
}

int main() {
  cin >> n >> s;
  memset(dp, -1, sizeof dp);
  ll ans = f(0, n);
  ll inv = pkt(pkt(2, s.length()) , mod-2);
  printf("%lld\n", (ans*inv)%mod);
}

Measured memory_bytes: 98304
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
#include<string>
using namespace std;
typedef long long ll;

#define REP(i, n) for(ll i=0;i<ll(n); i++)

int main(){
    ll N, A, B;
    cin >> N >> A >> B;

    ll amari;
    ll sho;
    
    sho   = N / (A + B);
    amari = N % (A + B);

    ll count = 0;

    count += sho * A;
    if(amari <= A){count += amari;}
    else{count += A;}

    cout << count << endl;

    return 0;
}


Measured memory_bytes: 3196
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 3010
using namespace std;
typedef long long ll;
ll n,s,ans;
ll check(ll x){
	ll n1=n,res=0;
	while(n1){
		res+=n1%x;
		n1/=x;
	}	
	return res==s;
}
int main(){
	SF("%lld%lld",&n,&s);
	if(n==s){
		PF("%lld",n+1);
		return 0;
	}
	ll t1=n-s;
	ans=n+1ll;	
	for(ll i=1;i<=sqrt(t1);i++)
		if(t1%i==0){
			ll ans1=i+1ll;
			if(check(ans1))
				ans=min(ans,ans1);
			ans1=t1/i+1ll;
			if(check(ans1))
				ans=min(ans,ans1);	
		}
	for(ll i=2;i<=sqrt(n);i++)
		if(check(i)){
			ans=min(ans,i);
			break;
		}
	if(ans==n+1)
		PF("-1");
	else{
		PF("%lld",ans);	
	}
		
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
using P = pair<ll, ll>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define INF 100000000000

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

	ll N;
	string S;
	cin >> N >> S;

	ll ans = 0;

	char now = S[0];
	ans = 1;
	rep(i, N) {
		if (now != S[i]) {
			now = S[i];
			ans++;
		}
	}

	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <utility>
using namespace std;

int main(){
	int N, M;
	cin >> N >> M;
	vector<long> A(N), B(M), C(M);
	for(int i=0;i<N;i++){
		cin >> A[i];
	}
	for(int i=0;i<M;i++){
		cin >> B[i] >> C[i];
	}
	sort(A.begin(), A.end());
	vector<pair<long, long>> v(M);
	for(int i=0;i<M;i++){
		v[i].first = C[i];
		v[i].second = B[i];
	}
	sort(v.rbegin(), v.rend());
	vector<long> made;
	int m = 0;
	int count = 0;
	while((int)made.size()<N){
		if(m < M)made.push_back(v[m].first);
		else {
			made.push_back(0);
			continue;
		}
		count++;
		if(count >= v[m].second){
			count = 0;
			m++;
		}
	}
	long ans = 0;
	for(int i=0;i<N;i++){
		if(A[i] < made[i])A[i] = made[i];
		ans += A[i];
	}
	cout << ans << endl;
}

Measured memory_bytes: 5368
import java.util.*;    
    public class Main {
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
        		int a = sc.nextInt();
        		int b = sc.nextInt();
          if(a==b){
            System.out.print("Yes");
          }else{
            System.out.print("No");
          }
        }
    }

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

const int N=1e5+10;
const int inf=1e9+10;

typedef pair<int,int> ii;

#define X first
#define Y second
int n;
int f[N];
priority_queue <ii> pq;

bool minimize(int &x,int y){
  if (x>y) x=y;else return 0;
  return 1;
}

int main(){
  cin>>n;
  fill(f,f+n,inf);
  for(int i=1;i<10;i++){
    if (minimize(f[i%n],i))
      pq.push(ii(-f[i%n],i));
  }
  while (!pq.empty()){
    ii cur=pq.top();pq.pop();
    if (-cur.X>f[cur.Y]) continue;
    for(int i=0;i<10;i++) {
      int ncur=(cur.Y*10+i)%n;
      if (minimize(f[ncur],-cur.X+i))
        pq.push(ii(-f[ncur],ncur));
    }
  }
  cout<<f[0];
}

Measured memory_bytes: 2804
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for (ll i = 0; i < (n); ++i)
#define rep2(i,a,b) for (ll i = (a); i < (b); ++i)

#define INF (1<<18)



int main(){
    ll n;
    cin>>n;
    vector<ll> a(n);
    ll sum_b = 0;

    rep(i,n){
        cin>>a[i];
        sum_b += a[i];
    }

    ll ans = sum_b;
    ll sum_f = 0;
    rep(i,n){
        sum_f += a[i];
        ans = min(ans, abs(sum_f - (sum_b - sum_f)));
    }

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

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

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef long long ll ;
typedef unsigned long long ull ;
typedef long double ld ;

const ll MOD = 1E9 + 7, INF = 2E18 + 5 ;
const double PI = 2 * acos(0.0) ;
const long double EPS = 1.0E-14 ;

int main()
{
    string s ;
    cin >> s ;
    ll cnt = 0, ans = 0 ;
    for (int i  = 0; i < 3; i++) {
        if (s[i] == 'R')    cnt++ ;
        else {
            ans = max(cnt, ans) ;
            cnt = 0 ;
        }
    }
    ans = max(ans, cnt) ;
    cout << ans ;

    return 0 ;
}


Measured memory_bytes: 3588
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Edge
    {
        internal int to, dist;

        public Edge(int to, int dist)
        {
            this.to = to;
            this.dist = dist;
        }
    }

    class Program
    {
        static Nullable<int>[] dp;

        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());

            Dictionary<int, List<Edge>> nodeList = new Dictionary<int, List<Edge>>();
            for (int i = 0; i < n; i++) nodeList.Add(i, new List<Edge>());


            for (int i = 0; i < n - 1; i++)
            {
                string[] input = Console.ReadLine().Split(' ');
                int s = int.Parse(input[0]);
                int t = int.Parse(input[1]);
                int w = int.Parse(input[2]);

                nodeList[s].Add(new Edge(t, w));
                nodeList[t].Add(new Edge(s, w));
            }

            BFS(nodeList, 0);

            int? maxDist = 0;
            int target = 0;

            for (int i = 0; i < n; i++)
            {
                if (dp[i] == null) continue;

                if (maxDist < dp[i])
                {
                    maxDist = dp[i];
                    target = i;
                }
            }

            BFS(nodeList, target);

            maxDist = 0;

            for (int i = 0; i < n; i++)
            {
                if (dp[i] == null) continue;

                if (maxDist < dp[i]) maxDist = dp[i];
            }

            Console.WriteLine(maxDist);
        }

        static void BFS(Dictionary<int, List<Edge>> NL, int s)
        {
            int len = NL.Count;
            dp = new Nullable<int>[len];

            Queue<int> que = new Queue<int>();
            que.Enqueue(s);

            dp[s] = 0;

            while (que.Count > 0)
            {
                int u = que.Dequeue();
                int outDegree = NL[u].Count;

                for (int i = 0; i < outDegree; i++)
                {
                    Edge e = NL[u][i];

                    if (dp[e.to] == null)
                    {
                        dp[e.to] = dp[u] + e.dist;
                        que.Enqueue(e.to);
                    }
                }
            }
        }
    }
}

Measured memory_bytes: 35292
#include <stdio.h>

#define N_MAX 100000
#define Q_MAX 50000

int binarySearch(int key);

int S[N_MAX];
int T[Q_MAX];
int n, q;

int main(void) {
  int C = 0;
  int i, j;

  scanf("%d", &n);
  for(i=0; i<n; ++i) {
    scanf("%d", &S[i]);
  }

  scanf("%d", &q);
  for(i=0; i<q; ++i) {
    scanf("%d", &T[i]);
  }

  for(i=0; i<q; ++i) {
    C += binarySearch(T[i]);
  }

  printf("%d\n", C);

  return 0;
}

int binarySearch(int key) {
  int mid;
  int left = 0;
  int right = n;

  while(left < right) {
    mid = (left + right) / 2;

    if(S[mid] == key) {
      return 1;
    }
    else if(key < S[mid]) {
      right = mid;
    }
    else {
      left = mid + 1;
    }
  }

  return 0;
}



Measured memory_bytes: 2332
using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static int Main(string[] args) {
        string moji = "abcdefghijklmnopqrstuvwxyz";
        int[] cnt = new int[26];

        while (true) {
            string v = Console.ReadLine();
            if (string.IsNullOrEmpty(v) == true) { break; }

            for (int i = 0; i < v.Length; i++) {
                string c = v.Substring(i, 1).ToLower();

                int idx = moji.IndexOf(c);
                if (idx < 0) { continue; }

                cnt[idx]++;
            }
        }

        for (int i = 0; i < cnt.Length; i++) {
            Console.WriteLine(string.Format("{0} : {1}", moji.Substring(i, 1), cnt[i]));
        }

        return 0;
    }
}


Measured memory_bytes: 18432
#include<bits/stdc++.h>
using namespace std;
char M[52][52];
int main(void)
{
	int H,W;
	scanf("%d %d",&H,&W);
	for(int i=0;i<H;i++)
		scanf("%s",&M[i]);
	int tr=1;
	for(int i=0;i<H-1;i++)
	{for(int j=0;j<W-1;j++)
	{
		if(M[i][j]=='#'&&M[i][j+1]=='.'&&M[i+1][j]=='.'&&M[i][j-1]=='.'&&M[i-1][j]=='.') tr=0;
	}
	}
	if(tr) printf("Yes");
	else printf("No");
}

Measured memory_bytes: 256
#include<cstdio>
#include<vector>
#include<algorithm>
int n,w,x,ans=0;
std::vector<int> f[5],g[5];
int cmp(int x,int y){return x>y;}
int main()
{
	scanf("%d%d",&n,&w);
	for (int i=1;i<=n;i++)
	{
		int w,v;
		scanf("%d%d",&w,&v);
		if (i==1) x=w;
		f[w-x].push_back(v);
	}
	for (int i=0;i<=3;i++) std::sort(f[i].begin(),f[i].end(),cmp);
	for (int i=0;i<=3;i++)
	{
		int s=0;
		for (int j=0;j<f[i].size();j++)
	    {
	    	s=s+f[i][j];
			g[i].push_back(s);
		}
	}
	for (int a=0;a<=f[0].size();a++)
		for (int b=0;b<=f[1].size();b++)
			for (int c=0;c<=f[2].size();c++)
				for (int d=0;d<=f[3].size();d++)
	                if (1ll*a*x+1ll*b*(x+1)+1ll*c*(x+2)+1ll*d*(x+3)<=1ll*w)
						ans=std::max(ans,(a>0?g[0][a-1]:0)+(b>0?g[1][b-1]:0)+(c>0?g[2][c-1]:0)+(d>0?g[3][d-1]:0));
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 3228
def pmod(a,b,m):
  ret=1
  while b>0:
    if b&1:
      ret=(ret*a)%m
    a=(a*a)%m
    b=b>>1
  return ret
  
def fmod(n,m):
  ret=1
  for i in range(n,0,-1):
    ret=(ret*i)%m
  return ret

def cmod(n,r,m):
  ret=1
  for i in range(r):
    ret=(ret*(n-i))%m
  return (ret*pmod(fmod(r,m),m-2,m))%m

mod=10**9+7
n,m,k=map(int,input().split())
ans=0
c=cmod(n*m-2,k-2,mod)
for i in range(1,n):
  ans+=i*c*(m**2)*(n-i)
  ans=ans%mod
for i in range(1,m):
  ans+=i*c*(n**2)*(m-i)
  ans=ans%mod
print(ans%mod)

Measured memory_bytes: 3188
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools, random
from collections import deque
from heapq import heappush, heappop
sys.setrecursionlimit(10 ** 7)
ans = 0
tmp = 0
inf = 10 ** 20
INF = float("INF")
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
ddn9 = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

n, a = wi()
x = wi()
X = max(x)
dp = [[[0] * (n + 1) for j in range(X * n + 2)] for i in range(n)]
dp[0][0][0] = 1
dp[0][x[0]][1] = 1

for p in range(1, n):
    for k in range(X * n + 2):
        for usenum in range(p + 1):
            dp[p][k][usenum] += dp[p - 1][k][usenum]
            if k - x[p] >= 0:
                dp[p][k][usenum + 1] += dp[p - 1][k - x[p]][usenum]

for k in range(X * n + 2):
    for usenum in range(n + 1):
        if usenum != 0:
            if k / usenum == a:
                ans += dp[n - 1][k][usenum]
print(ans)

Measured memory_bytes: 128088
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-8;
const int inf=1e8;
int main(){
	vi a,b,c;
	rep(i,55){
		a.pb(i*i*i);
	}
	rep(i,96){
		b.pb(i*(i+1)*(i+2)/6);
	}
	rep(i,a.size())rep(j,b.size())c.pb(a[i]+b[j]);
	sort(all(c));
	c.erase(unique(all(c)),c.end());
	int n;
	while(cin>>n,n){
		int t=upper_bound(all(c),n)-c.begin();
		cout<<c[t-1]<<endl;
	}
}

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

int main(){
    int A,B,C;
    int five=0,seven=0;
    cin >> A >> B >> C;

    if(A==5)five++;
    else if(A==7)seven++;
    if(B==5)five++;
    else if(B==7)seven++;
    if(C==5)five++;
    else if(C==7)seven++;

    if(five==2&&seven==1) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
inf = 10**17
mod = 10**9+7


n, q = map(int, input().split())
g = [[] for _ in range(n)]
val = [0] * n

for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

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

seen = [False] * n
def dfs(v):
    seen[v] = True
    for nv in g[v]:
        if seen[nv]:
            continue
        val[nv] += val[v]
        dfs(nv)

dfs(0)
print(*val)


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

int main(){
  int H, W;
  cin >> H >> W;

  // H*Wの配列を読み込む
  vector<vector<char>> pixel(H, vector<char>(W));

  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      
      cin >> pixel.at(i).at(j);

    }
  }

  // (H+2)*(W+2)の配列を宣言し、#で埋める
  vector<vector<char>> table(H + 2, vector<char>(W + 2, '#'));

  // 文字配列を#で囲む
  for(int i = 1; i < H + 1; i++){
    for(int j = 1; j < W + 1; j++){
      
      table.at(i).at(j) = pixel.at(i - 1).at(j - 1); 

    }
  }
  
  for(int i = 0; i < H + 2; i++){
    for(int j = 0; j < W + 2; j++){
      
      cout << table.at(i).at(j);
      
      if(j == W + 1){
        cout << endl;
      }
    }
  }
}

Measured memory_bytes: 3592
#include<stdio.h>
int main(void)
{
    int n,h[101];
    int i,j,k;
    int sa[101],b[101];
    int flg;
     
    scanf("%d",&n);
    while(n!=0){
        for(i=0;i<n+1;i++){
            scanf("%d",&h[i]);
        }
        for(i=0;i<n+1;i++){
            k=0;
            for(j=0;j<n+1;j++){
                if(i!=j){
                    b[k]=h[j];
                    k++;
                }
            }
            for(j=0;j<n-1;j++){
                sa[j]=b[j+1]-b[j];
            }
            flg=0;
            for(j=0;j<n-2;j++){
                if(sa[j]!=sa[j+1]){
                    flg=1;
                }
            }
            if(flg==0){
                printf("%d\n",h[i]);
                break;
            }
        }   
        scanf("%d",&n);
    }
    return 0;
}


 

Measured memory_bytes: 600
#include<bits/stdc++.h>
using namespace std;
#define N 1000006
vector<int> t1[N],t2[N],g[N];
#define addedge(x,f,t) (x[f].push_back(t),x[t].push_back(f))
int n,ans[N],odd[N],isodd[N];
void DFS(vector<int> *x,int u,int fr){
    int temp=-1;
    for(int i:x[u])
        if(i!=fr) 
            DFS(x,i,u),temp= temp==-1? odd[i]:(addedge(g,temp,odd[i]),-1);
    odd[u]=temp==-1? isodd[u]++,u:temp;
}
void DFS2(int u,int col){
    ans[u]=col;
    for(int i:g[u])
        if(ans[i]==0) DFS2(i,-col);
}
int main(){
    scanf("%d",&n);
    int root1,root2;
    for(int i=1,v;i<=n;i++){
        scanf("%d",&v);
        if(v!=-1) addedge(t1,i,v);
        else root1=i;
    }
    for(int i=1,v;i<=n;i++){
        scanf("%d",&v);
        if(v!=-1) addedge(t2,i,v);
        else root2=i;
    }
    DFS(t1,root1,0);
    DFS(t2,root2,0);
    for(int i=1;i<=n;i++)
        if(isodd[i]==2&&ans[i]==0) DFS2(i,1);
        else if(isodd[i]==1) return puts("IMPOSSIBLE"),0;
    puts("POSSIBLE");
    for(int i=1;i<=n;i++)
        printf("%d ",ans[i]);
    return 0;
}

Measured memory_bytes: 93304
A,B,C = map(int,input().split())

def solve(a=A,b=B,c=C):
    if a % 2 == 1 or b % 2 == 1 or c % 2 == 1:
        return 0
    if a == b == c:
        return -1
    return solve((b+c)//2,(c+a)//2,(a+b)//2) + 1

ans = solve()

print(ans)

Measured memory_bytes: 3060