akhauriyash/Code-Regression huggingface dataset:
import sys
input = sys.stdin.readline

ABC = list(map(int, input().split()))
K = int(input())

for i in range(K+1):
    if ABC[0] < ABC[1] and ABC[1] < ABC[2]:
        print("Yes")
        break
    elif ABC[0] >= ABC[2]:
        ABC[2] = 2 * ABC[2]
    elif ABC[1] >= ABC[2]:
        ABC[2] = 2 * ABC[2]
    elif ABC[0] >= ABC[1]:
        ABC[1] = 2 * ABC[1]
        
else:
  print("No")

Measured memory_bytes: 9212
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-10;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

ll solve(ll n)
{
	ll t = 1, d = 1, cnt = 0;
	while (t * 10 < n)
	{
		cnt += (t * 10 - t)*d;
		t *= 10;
		d++;
	}
	cnt += d*(n - t);
	return cnt;
}
int main()
{
	int n, k;
	while (cin >> n >> k, n)
	{
		ll lb = 0, ub = INT_MAX;
		ll cnt;
		while (ub - lb > 1)
		{
			ll mid = (lb + ub) / 2;
			cnt = solve(mid);
			if (cnt >= n) ub = mid;
			else lb = mid;
		}
		string s;
		cnt = solve(lb);
		REP(i, 100) s += to_string(lb + i);
		cout << s.substr(n - cnt - 1, k) << endl;
	}
	return 0;
}

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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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 = 1e15;
const int MOD = 1e9+7;
const ll LINF = 1e18;

ll modpow(ll a, ll n) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % MOD;
    (a *= a) %= MOD;
    n >>= 1;
  }
  return res;
}

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n,k; cin>>n>>k;
  vll a(n);
  rep(i,n) cin>>a[i];
  ll x=0;
  rep(i,n){
    irep(j,i+1,n){
      if(a[i]>a[j]) x++;
    }
  }
  ll ans=(x*k)%MOD;
  x=0;
  rep(i,n){
    rep(j,n){
      if(a[i]>a[j]) x++;
    }
  }
  ans+=(k*(k-1)/2)%MOD*x%MOD;
  ans%=MOD;
  cout<<ans<<endl;
  
}


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

#define _1 first
#define _2 second
#define pb push_back
#define mp make_pair
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define uni(x) (x).erase(unique(all(x)), (x).end())
#define reset(x, y) memset(x, y, sizeof(x))
#define BUG(x) cerr << #x << " = " << (x) << endl
#define BUGP(x) cout << #x << " = " << (x)._1 << ", " << (x)._2 << endl
using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;

const int dr[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dc[] = {0, -1, 0, 1, -1, 1, -1, 1};
// Head

const int N = 1123456;

char s[N];

int n, tot;
int final[N], maxm[N];
int pos[N], pos_cnt;
int neg[N], neg_cnt;

int main() {
    scanf("%d", &n);

    for (int i = 0; i < n; ++i) {
        scanf("%s", s);
        int l = 0, r = 0;
        int len = strlen(s);

        for (int j = 0; j < len; ++j) {
            if (s[j] == '(') ++l;
            else ++r;
            maxm[i] = max(maxm[i], r - l);
        }

        if (l - r >= 0) {
            pos[pos_cnt++] = i;
            final[i] = l - r;
        } else {
            neg[neg_cnt++] = i;
            final[i] = r - l;
        }
    }

    sort(pos, pos + pos_cnt, [](const int a, const int b) { return maxm[a] < maxm[b]; });

    for (int i = 0; i < pos_cnt; ++i) {
        int it = pos[i];
        if (maxm[it] > tot) {
            puts("No");
            return 0;
        }
        tot += final[it];
    }

    sort(neg, neg + neg_cnt, [](const int a, const int b) { return maxm[a] - final[a] > maxm[b] - final[b]; });
    for (int i = 0; i < neg_cnt; ++i) {
        int it = neg[i];
        if (maxm[it] > tot) {
            puts("No");
            return 0;
        }
        tot -= final[it];
    }

    if (tot) puts("No");
    else puts("Yes");

    return 0;
}

Measured memory_bytes: 15500
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <utility>
#include <stack>
#include <queue>
#include <sstream>
#include <fstream>
#include <cstring>

using namespace std;
#define int long long

signed main()
{
	int N;
	cin >> N;
	int i = 0;
	int ans = 0;
	if (N < 11) {
		if (N <= 6) cout << 1 << endl;
		else cout << 2 << endl;
	}
	else if (N % 11 == 0) {
		cout << N / 11 * 2 << endl;
	}
	else {
		int tmp = N % 11;
		if (tmp <= 6) {
			cout << N / 11*2 + 1 << endl;
		}
		else {
			cout << N / 11 * 2 + 2 << endl;
		}
	}

	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define zero_pad(num) setfill('0') << std::right << setw(num)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;

int main() {
    string s, t;
    cin >> s >> t;
    int n = s.size();
    int m = t.size();
    vector<int> cnt1(n+1, 0), cnt2(m+1, 0);
    rep(i, n){
        if(s[i] == 'A')cnt1[i+1] += 1 + cnt1[i];
        else cnt1[i+1] += 2 + cnt1[i];
    }
    rep(i, m){
        if(t[i] == 'A')cnt2[i+1] += 1 + cnt2[i];
        else cnt2[i+1] += 2 + cnt2[i];
    }

    int q;
    cin >> q;
    rep(i, q){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        int sum1 = cnt1[b] - cnt1[a-1];
        int sum2 = cnt2[d] - cnt2[c-1];
        if(sum1 % 3 == sum2 % 3)cout << "YES" << endl;
        else cout << "NO" << endl;
    }

}

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

int main() {
    int H, W;
    cin >> H >> W;
    
    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            string S;
            cin >> S;
            if(S == "snuke") {
                cout << (char)('A' + j) << i + 1 << endl;
            }
        }
    }
}


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

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

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K; cin >> N >> K;
    ll A[N]; rep(i, N) cin >> A[i];
    vector<ll> B;
    for(int i = 0; i < N; i++){
        ll acc = 0;
        for(int j = i; j < N; j++){
            acc += A[j];
            B.push_back(acc);
        }
    }
    int sz = B.size();
    ll cnt[40] = {};
    rep(i, sz){
        ll val = B[i];
        int id = 0;
        while(val > 0 && id < 40){
            cnt[id] += (val&1);
            val >>= 1;
            id++;
        }
    }

    ll ans = 0;
    vector<bool> removed(sz, false);
    for(int i = 39; i >= 0; i--){
        if(cnt[i] >= K){
            ans += (1ll << i);
            rep(j, sz){
                if(!removed[j] && (B[j] & (1ll << i)) == 0){
                    removed[j] = true;
                    rep(k, 40) cnt[k] -= ((B[j] >> k) & 1);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 7408
#include <bits/stdc++.h>
using namespace std;
int main(){
  vector<int> k={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int n;
  cin>>n;
  cout<<k.at(n-1)<<endl;
}
  

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define c(P)        cout<<P<<"\n"
#define pii         pair<ll,ll>
#define mi          map<ll,ll>
#define mii         map<pii,ll>
#define F           first
#define S           second
#define sz(a)       (ll)(a.size())
#define cr(P)       cout<<P<<"\n";return;
#define mem(a,val)  memset(a,val,sizeof(a))
#define fr(i,x,n)   for(ll i=x;i<n;i++)
#define frr(i,x,n)  for(ll i=n-1;i>=x;i--)
using namespace std;


const ll N   =  500005;
const ll mod = 1e17 + 7;


ll a[100][100];
void solve(){

  ll x=0,y=0,c=0,ans=mod;
  ll n,m,k;
  cin>>n >> m >> k;
  vector<ll>cost(n);
  for (ll i = 0; i < n; ++i){
      cin >> cost[i];

      for (ll j = 0; j < m; ++j){
          cin >> a[i][j];
      }
  }

  for (ll i = 0; i < (1<<n); ++i){
      c = 0,y = 0;
            vector<ll>v(m);
      for (ll j = 0; j < n; ++j){
          
          if(i & (1LL<<j)){
           
            c += cost[j];
            
            for (ll p = 0; p < m; ++p){
             v[p]+=a[j][p];   
            }
          }
      }
    
      for (ll p = 0; p <m ; ++p){
          if(v[p]>=k){
            y++;
          }
            
      }
      if(y==m)
        ans = min (ans,c);
  }
  if(ans!=mod){
    c(ans);
  }
  else c(-1);
  
 
}

signed main(){
     
  ios_base::sync_with_stdio(false);   
  cin.tie(NULL);
  //int T;cin >> T;while (T--)
  solve();
  return 0;
}


Measured memory_bytes: 3604
N = int(input())
s = []
for _ in range(N):
    s.append(input())
M = int(input())
t = []
for _ in range(M):
    t.append(input())

say = set(s)

#print(say)

M = 0
for saying in say:
    M = max(M, s.count(saying) - t.count(saying))
print(M)

Measured memory_bytes: 3060
import java.util.*;
class Main{
	static Scanner s = new Scanner(System.in);
	public static void main(String[] args) {
		int a=Integer.parseInt(s.next()),
		    b=Integer.parseInt(s.next()),
		    c=Integer.parseInt(s.next()),
		    cnt=0;
		for(int i=a;i<=b;i++) {
			if(c%i==0)
				cnt++;
		}
		System.out.println(cnt);
	}
}

Measured memory_bytes: 26048
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

typedef long long ll;
ll MOD = 1000000007;

// a^p
// 2^3 = 2 * 2^2
// 2^2 = 2 * (2^1)
// 2^1 = 2
ll modpow(ll a, ll p, ll mod) {
  if (p == 0)
    return 1;

  if (p % 2 == 0) {
    ll half = modpow(a, p / 2, mod) % mod;
    return half * half % mod;
  } else {
    return a * modpow(a, p - 1, mod) % mod;
  }
}

// nCa を求める
ll modCombination(ll n, ll a, ll mod) {
  if (n - a < a) {
    return modCombination(n, n - a, mod);
  }

  ll denominator = 1; // 分母
  ll numerator = 1;   // 分子

  for (ll i = 0; i < a; i++) {
    denominator *= a - i;
    numerator *= n - i;
    denominator %= mod;
    numerator %= mod;
  }

  return numerator * modpow(denominator, mod - 2, mod) % mod;
}

class UnionFind {
private:
  vector<ll> parents;

public:
  UnionFind(ll n) : parents(n, -1) {}

  bool issame(ll x, ll y) {
    return root(x) == root(y);
  }

  bool merge(ll x, ll y) {
    if (issame(x, y))
      return false;

    ll rx = root(x);
    ll ry = root(y);
    if (parents[rx] > parents[ry])
      swap(rx, ry);
    // サイズ情報を更新
    parents[rx] += parents[ry];
    // yの親を更新
    parents[ry] = rx;

    return true;
  }

  ll size(ll x) {
    return -parents[root(x)];
  }

private:
  ll root(ll x) {
    if (parents[x] < 0)
      return x;
    // 根の親の値に木の(-)サイズの情報を入れる
    return parents[x] = root(parents[x]);
  }
};

using Edge = pair<ll, ll>;
void dfs(vector<vector<Edge>> &G, vector<ll> &nodes, ll parent, ll current, int color) {
  // cout << parent << " - " << current << endl;
  for (auto e : G[current]) {
    if (e.first == parent) {
      continue;
    }

    if (e.second % 2 == 0) {
      nodes[e.first] = color;
    } else {
      nodes[e.first] = (color + 1) % 2;
    }

    dfs(G, nodes, current, e.first, nodes[e.first]);
  }
}

int main() {
  ll N;
  cin >> N;

  vector<vector<Edge>> G(N, vector<Edge>());

  for (ll i = 0; i < N - 1; i++) {
    ll u, v, w;
    cin >> u >> v >> w;
    G[u - 1].push_back(make_pair(v - 1, w));
    G[v - 1].push_back(make_pair(u - 1, w));
  }

  vector<ll> nodes(N, 0);

  dfs(G, nodes, 0, 0, 0);

  for (auto n : nodes) {
    cout << n << endl;
  }

  return 0;
}


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

int main(void){
    long long int i, j, n, x, ans=1, po=1, po2=1;
    scanf("%lld", &n);
    for(i=0; i<n; i++) ans = ans*10%1000000007;
    for(i=0; i<n; i++) po = po*9%1000000007;
    for(i=0; i<n; i++) po2 = po2*8%1000000007;
    printf("%lld", (ans+(2*(1000000007-po))+po2)%1000000007);
}

Measured memory_bytes: 1728
//Binary Search Tree 2
#include <stdio.h>
#include <stdlib.h>
struct node{
  int key;
  struct node *left,*right,*parent;
};
typedef struct node Node;
Node *rootnode;
Node *NIL;
void Insert(int );
void Preorder(Node *);
void Inorder(Node *);
void Find(Node *,int );



int main(void){
  int n,i,key;
  char command[6];
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s",command);
    if(command[0]=='i'){
      scanf("%d",&key);
      Insert(key);
    }
    else if(command[0]=='p'){
      Inorder(rootnode);
      printf("\n");
      Preorder(rootnode);
      printf("\n");
    }
    else if(command[0]=='f'){
      scanf("%d",&key);
      Find(rootnode,key);
    }
  }

  return 0;
}

void Find(Node *node,int key){
  int check=0;
  while(node!=NIL){
    if(node->key==key){
      check=1;
      break;
    }
    else if(node->key < key)
      node=node->right;
    else
      node=node->left;
  }
  if(check==1)printf("yes\n");
  else printf("no\n");
}

void Insert(int key){
  Node *parent=rootnode;
  Node *z;
  Node *y=NIL;
  z=(Node *)malloc(sizeof(Node));
  z->key=key;
  z->left=NIL;
  z->right=NIL;

  while(parent!=NIL){
    y=parent;
    if(key > parent->key)
      parent=parent->right;
    else
      parent=parent->left;
  }
  if(y==NIL)rootnode=z;
  z->parent=y;
  if(y!=NIL){
    if(key > y->key)
      y->right=z;
    else
      y->left=z;
  }
}

void Preorder(Node *node){
  printf(" %d",node->key);
  if(node->left!=NIL)
    Preorder(node->left);
  if(node->right!=NIL)
    Preorder(node->right);
}

void Inorder(Node *node){
  if(node->left!=NIL)
    Inorder(node->left);
  printf(" %d",node->key);
  if(node->right!=NIL)
    Inorder(node->right);
}



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

const ll oo=1e12;
int main()
{
    ll n;
    cin>>n;
    ll arr[n];
    ll pref[n];
    ll suff[n],i;
    for(i=0;i<n;i++)
        cin>>arr[i];
    pref[0]=-1;
    pref[1]=arr[0];
    for(i=2;i<n;i++)
    {
        pref[i]=max(pref[i-1],arr[i-1]);
    }
    suff[n-1]=-1;
    suff[n-2]=arr[n-1];
    for(i=n-3;i>=0;i--)
        suff[i]=max(suff[i+1],arr[i+1]);
    
    for(i=0;i<n;i++)
    {
        cout<<max(pref[i],suff[i])<<endl;
    }
    
    return 0;
    
}

Measured memory_bytes: 6272
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

	Scanner sc=new Scanner(System.in);

	int INF=1<<28;
	double EPS=1e-9;

	void run(){
		for(;;){
			int n=sc.nextInt();
			if(n==0){
				break;
			}
			int a=0, b=0;
			for(int i=0; i<n; i++){
				int p=sc.nextInt();
				int q=sc.nextInt();
				if(p>q){
					a+=p+q;
				}else if(p<q){
					b+=p+q;
				}else{
					a+=p;
					b+=q;
				}
			}
			println(a+" "+b);
		}
	}

	void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		new Main().run();
	}
}

Measured memory_bytes: 12000
package main

import "fmt"

type tele struct {
	name int
	saki int
	v int
}

func main(){
	var n,k,visit_city int
	var city,bef int
	fmt.Scan(&n,&k)
	a := make([]tele,n+1)
	for i:=1 ; i<=n ; i++ {
		a[i].name = i
		fmt.Scan(&a[i].saki)
	}
//fmt.Println(a)
	a[1].v = 1
	city = 1
	visit_city++
	flag := true
	for i := 0; i<k ; i++ {
//fmt.Println(a,visit_city)
		/*if k == visit_city {
			fmt.Println(city)
			break
		}*/
		bef = city
		city = a[bef].saki
		if a[city].v == 0 {
			//行ったことない
			//bef = city
			//city = a[bef.saki]
			a[city].v = a[bef].v+1
			visit_city++
			/*if k == visit_city {
				fmt.Println(city)
				break
			}*/
//fmt.Println(city)
			continue
		} else {
			//行ったことある
			/*if k <= visit_city {
//fmt.Println("k small",visit_city)
				city = 1
				for i:=1 ; i<k ; i++ {
					city = a[city].saki
				}
				fmt.Println(city)
				break
			}*/
			k -= (a[city].v-1)
			k = k%(visit_city - a[city].v + 1)
//fmt.Println(k)
			for i:=0 ; i<k ; i++ {
				city = a[city].saki
			}
			fmt.Println(city)
			flag = false
			break
		}
	}
	if flag {
		fmt.Println(city)
	}
}


Measured memory_bytes: 11200
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <random>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

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

















int main(){
    ll n;
    cin >> n;
    vector<ll> cnt(n);
    REP(i, n - 1){
        ll a;
        cin >> a;
        a--;
        cnt[a]++;
    }
    REP(i, n){
        cout << cnt[i] << endl;
    }
}

Measured memory_bytes: 4760
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<list>
#include<stack>
//#include<unordered_map>
using namespace std;
#define ll long long
#define dd cout<<endl
const long long int inf = 1e18+7;
const int mod = 998244353;

using namespace std;

inline ll int max(ll int a,ll int b) { return a>b?a:b; }
inline ll int min(ll int a,ll int b) { return a<b?a:b; }

const int maxn=2e5+10;

int num[maxn];

int main()
{
//	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int n,k;
	
	while(scanf("%d%d",&n,&k)!=EOF)
	{
		
		for(int i=0;i<n;i++)
		{
			scanf("%d",&num[i]);
		}
		
		for(int i=0;i<n-k;i++)
		{
			if(num[i+k] > num[i])
			{
              	printf("Yes\n");
			}
			else
			{
                printf("No\n");
			}
		}
		
	}
	
	return 0;
}

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

using namespace std;

typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;

constexpr int MAXN = 300;

double dp[MAXN + 2][MAXN + 2][MAXN + 2];
int freq[4], N;

double solve(int i, int j, int k) {
	return i < 0 || j < 0 || k < 0 || i == 0 && j == 0 && k == 0 ? 0 : dp[i][j][k] == 0 ? dp[i][j][k] = (N + i * solve(i - 1, j, k) + j * solve(i + 1, j - 1, k) + k * solve(i, j + 1, k - 1)) / (i + j + k) : dp[i][j][k];
}

int main() {
	cin >> N;
	for(int i = 0; i < N; i++) {
		int a;
		cin >> a;
		freq[a]++;
	}
	cout << setprecision(10) << solve(freq[1], freq[2], freq[3]) << endl;
}


Measured memory_bytes: 215296
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll h, w, k;
  cin >> h >> w >> k;
  vector<vi> g(h, vi(w, 0));
  rep(i, h) rep(j, w) {
    char c;
    cin >> c;
    if(c == '1') g[i][j] = 1;
  }
  ll ans = 1e9;
  rep(c, 1 << (h - 1)) {
    ll nans = 0;
    vl num(h, 0);
    rep(j, w) {
      vl now(h, 0);
      ll ind = 0;
      rep(i, h) {
        now[ind] += g[i][j];
        if(c >> i & 1) ind++;
      }
      bool ok = true;
      bool zero = true;
      rep(i, h) {
        if(num[i] + now[i] > k) ok = false;
        if(num[i] > 0) zero = false;
      }
      if(ok)
        rep(i, h) num[i] += now[i];
      else {
        num = now;
        nans++;
        if(zero) nans = 1e9;
      }
    }
    rep(i, h - 1) if(c >> i & 1) nans++;
    ans = min(ans, nans);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
// Author: Wenxing Mei
//   File: a.cpp
//   Date: 2019-04-05 16:55
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define per(i, b, a) for (int i = (int)b; i >= (int)a; --i)
#define repv(ele, cont) for (auto &ele : cont)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define eb emplace_back
#define ep emplace
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<ll> vll;
// END OF TEMPLATE
char t[255];
int main() {
#ifndef LOCAL
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#endif
    char c;
    cin >> c;
    t['C'] = 'G';
    t['G'] = 'C';
    t['A'] = 'T';
    t['T'] = 'A';
    cout << t[c] << endl;

    return 0;
}


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

int main(){
	int a,i=1;
	cin >> a;
	while(true){
		cout <<"Case " << i << ": " << a << endl;
		i = i+1;
		cin >> a;
		if(a ==0) break;
	}
	cout << endl;
	return 0;
}
*/

#include<iostream>
using namespace std;


int main(){
int i=1;
int n;

while(true){
cin >> n;
if(n == 0)break;
cout << "Case " << i << ": " << n << endl;
i++;
}

return 0;
}



Measured memory_bytes: 3096
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int MAX_N = 1e5 + 15, UNMARKED = 0;
vector <int> graph[MAX_N];
int component[MAX_N];

void dfs(int v, int component_no)
{
    component[v] = component_no;

    for(int i = 0; i < graph[v].size(); i++)
    {
        int child = graph[v][i];

        if(component[child] == UNMARKED)
            dfs(child, component_no);
    }
}

int main()
{
    int n, no_of_edges;
    scanf("%d %d", &n, &no_of_edges);

    vector <int> permutation(n + 1);
    for(int i = 1; i <= n; i++)
        scanf("%d", &permutation[i]);

    for(int i = 1; i <= no_of_edges; i++)
    {
        int u, v;
        scanf("%d %d", &u, &v);

        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    memset(component, UNMARKED, sizeof(component));

    int component_no = 1;

    for(int i = 1; i <= n; i++)
    {
        if(component[i] == UNMARKED)
            dfs(i, component_no++);
    }

    int no_of_inplace_elements = 0;
    for(int i = 1; i <= n; i++)
        no_of_inplace_elements += (component[i] == component[permutation[i]]);

    printf("%d\n", no_of_inplace_elements);
    return 0;
}


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

int main(){
    int a, b, i, c = 0;
    string s;
    cin >> a >> b >> s;
    for(i=0; i<a+b+1; i++){
        if(i == a && s[i] != '-'){
            cout << "No";
            break;
        }
        if(i != a && !(isdigit(s[i]))){
            cout << "No";
            break;
        }
        if(i == a+b){
            cout << "Yes";
        }
    }  
    return 0;
}

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

using namespace std;


//repetition
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define euc_dis(x, y) sqrt(x*x + y*y)

#define MOD 1e9+7
#define sp ' '


using ll = long long;


ll mod(ll a, ll b){return (a%b+b)%b;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void Judge(bool b){b?Yes():No();}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void JUDGE(bool b){b?YES():NO();}
ll powMod(ll b, ll e, ll m){ll r=1;while(e>0){if(e&1)r=(r%m)*(b%m)%m;b=(b%m)*(b%m)%m;e>>=1;}return r;}
double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}

template<typename T>
void ppp(T n){cout << n << endl;}


int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    int n; cin >> n;

    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    ll cnt = 0LL;
    for(int i = 0; i < n; ++i){
        ++cnt;
        while(i+1 < n and a[i] == a[i+1]) ++i;
        if(i == n-1) break;
        if(a[i] < a[i+1]){
            while(i+1 < n and a[i] <= a[i+1]) ++i;
        }
        else{
            while(i+1 < n and a[i] >= a[i+1]) ++i;
        }
    }

    ppp(cnt);
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define U [100005]={}
typedef long long L;using namespace std;map<L,L> path U;L P U,E U,Z U,H U,C U,A U,O U,X U,B U,k,n,a,b,c,p,r;char s U;L D(L a){Z[a]=1;for(map<L,L>::iterator I=path[a].begin();I!=path[a].end();I++){L d=I->first;if(d-P[a]){P[d]=a;E[d]=E[a]+1;C[d]=I->second;D(d);Z[a]+=Z[d];!H[a]|Z[H[a]]<Z[d]?H[a]=d:0;}}}L G(L a){r=A[a]+A[P[a]]+C[a];return r%k?r:0;}L M(L i){for(r=0;i;r+=B[i],i-=i&-i);return r;}L S(L i,L x){for(x=G(x)-M(i+1)+M(i++);i<100005;B[i]+=x,i+=i&-i);}main(){for(cin>>n>>k;p<n-1;p++)cin>>a>>b>>c,path[a][b]=path[b][a]=c;D(0);for(c=p=0;p<n;p++)if(!p|H[P[p]]-p)for(a=p;!c|a;a=H[a])O[a]=c++,X[a]=p,S(O[a],H[a]);for(cin>>a;cin>>s>>a>>b;)if(*s&2){for(c=0;p=X[a],n=X[b],p-n;a=P[p])E[p]<E[n]?swap(p,n),swap(a,b),0:0,c+=M(O[a])-M(O[p])+G(p);cout<<c+abs(M(O[a])-M(O[b]))<<endl;}else A[a]+=b,S(O[a],H[a]),a?S(O[a]-1,a):0;}

Measured memory_bytes: 31992
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <numeric>
#include <array>
#include <cmath>
#include <memory>
using namespace std;
//変数デバッグ
#define DEB(variable) cout << #variable << '=' << variable << endl

//for簡易表記(引数ミス防止)
#define FOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)
#define DEFOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin)-1; (LoopVariable) >= (numberOFend); (LoopVariable)--)
#define REP(LoopVariable,numberOFend) for(int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++)

constexpr long long int linf = numeric_limits<long long int>::max()-5;
constexpr int inf= numeric_limits<int>::max()-5;
constexpr long long int mod = 1000000007;

int main(){
    int a,b,t;
    cin>>a>>b>>t;
    cout<<(t/a)*b<<endl;
    

    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define PI 3.141592
#define MOD7 1000000007
#define LL_INF 9000000000000000000
#define LL_MINF -9000000000000000000
#define INT_INF 2000000000
#define INT_MINF -2000000000
#define all(a) (a).begin(), (a).end()
#define fi first
#define se second
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int main(){
    int A, B, C;
    cin >> A >> B >> C;
    int max_n = max({A, B, C});
    int min_n = min({A, B, C});
    int mid_n = A + B + C - max_n - min_n;
    int count = 0;
    while(mid_n != max_n){
        mid_n++;
        min_n++;
        count++;
    }
    while(min_n < max_n){
        min_n+=2;
        count++;
    }
    if(min_n == max_n + 1) cout << count + 1 << endl;
    else cout << count << endl;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define INF 987654321

int main() {
    ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    n %= 1000;
    if (n == 0) cout << 0 << endl;
    else cout << 1000 - n;
    return 0;
}

Measured memory_bytes: 3620
from collections import deque

N,Q=map(int,input().split())
out=[set() for i in range(N+1)];out[0]=None # 頂点は1-initial
for j in range(N-1):
    a,b=map(int,input().split())
    out[a].add(b)
    out[b].add(a)
# print(out) #DB

a=[0 for i in range(N+1)];a[0]=None

for k in range(Q):
    p,x=map(int,input().split())
    a[p]+=x

# print(a) #DB

q=deque()
q.append(1)
while q:
    u=q.popleft()
    for v in out[u]:
        a[v]+=a[u]
        q.append(v)
        out[v].remove(u)
        # print(q) #DB
    out[u].clear()

print(*a[1:])

Measured memory_bytes: 129740
#include<string.h>
#include<stdio.h>
int main(){
  char str1[100], str2[100],str3[200];

 scanf("%s %s", str1, str2);




 strcpy(str3, str1);
strcat(str3, str1); 




if ( strstr(str3, str2) == NULL ) printf("No\n");
else printf("Yes\n");

 return 0;
}



Measured memory_bytes: 2104
'''
Created on 2020/08/22

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  K=int(pin())
  a=7%K
  for i in range(K):
    if a%K==0:
      print(i+1)
      break
    a=(10*a+7)%K
  else:
    print(-1)
  return 
main()

#解説AC

Measured memory_bytes: 9084
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define fo(x,a,b) for(register int x=a;x<=b;x++)
#define dfo(x,a,b) for(register int x=a;x>b;x--)
#define inf 2147483647
using namespace std;
int a[1000005],m,n,x;
bool dg(int ax,int shu)
{
	if (ax>n) return (false);
	if (shu==0) return (true);
	else return(dg(ax+1,shu-a[ax])|dg(ax+1,shu));
} 
int main ()
{
	

	scanf("%d",&n);
	fo(i,0,n-1)
	{
		scanf("%d",&a[i]);
	}
	scanf("%d",&m);
	fo(i,1,m)
	{
		scanf("%d",&x);
		if (dg(0,x)) printf("yes\n");else printf("no\n");
	}

	return 0;
}





Measured memory_bytes: 3148
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define per1(i,n) for(int i=n;i>0;i--)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,x[101],y[101],h[101];
    cin>>n;
    rep(i,n) cin>>x[i]>>y[i]>>h[i];
    rep(i,101)rep(j,101){
        ll z=1,H,a;
        rep(k,n){
            if(h[k]!=0) H=h[k]+abs(i-x[k])+abs(j-y[k]),a=k;
        }
        rep(k,n){
            if(h[k]==0){
                if(abs(i-x[k])+abs(j-y[k])<H) z=0;
            }
            else if(h[k]+abs(i-x[k])+abs(j-y[k])!=H) z=0;
        }
        if(z){
            cout<<i<<" "<<j<<" "<<h[a]+abs(i-x[a])+abs(j-y[a]);
            return 0;
        }
    }
}

Measured memory_bytes: 3596
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)

using namespace std;

typedef long long int lli;

int main() {
    int N;
    cin >> N;
    vector<int> T(N + 1, 0);
    vector<int> V(N + 1, 0);

    int sumTime = 0;
    REP (i, 0, N) {
        int tm = 0;
        cin >> tm;
        if (i != 0)
            T[i] = T[i - 1] + tm;
        else 
            T[i] = tm;
        sumTime = T[i];
    }
    REP (i, 0, N) cin >> V[i];
    double inf = 1e+15;    
    vector<vector<double>> dp(sumTime * 2 + 1, vector<double>(205, -inf));
    int tmIndex = 0;
    dp[0][0] = 0.0;
    REP (i, 0, 2 * sumTime) {
        if (i / 2 >= T[tmIndex]) tmIndex++;
        int lmt = V[tmIndex];
        REP (j, 0, dp[i].size()) {
            if (dp[i][j] < -1.0) continue;
            if (j > lmt * 2) break;
            int nxt = min(lmt * 2, j + 1);
            dp[i + 1][nxt] = max(dp[i + 1][nxt], dp[i][j] + (nxt * 0.5 + j * 0.5) * 0.5 * 0.5);
            nxt = max(0, j - 1);
            dp[i + 1][nxt] = max(dp[i + 1][nxt], dp[i][j] + (nxt * 0.5 + j * 0.5) * 0.5 * 0.5);
        }
    }
    cout << fixed << setprecision(10) << dp[sumTime * 2][0] << endl;
    return 0;
}

Measured memory_bytes: 65536
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <map>

using namespace std;

int main()
{
	int N;
	cin >> N;

	// 整数列Aの入力
	vector<int> A(N);
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];

		// あらかじめ i を引いておく
		A[i] -= (i + 1);
	}

	// ソートしてAの中央値を求める
	sort(A.begin(), A.end());
	int m = A[N / 2];

	// 答えを求める
	long long ans = 0;
	for (int i = 0; i < N; i++)
	{
		ans += abs(A[i] - m);
	}

	// 答えを出力
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 1024
#include "bits/stdc++.h"

#define ll          long long
#define pb          push_back
#define pii         pair<ll,ll>
#define vpii        vector< pii >
#define vi          vector<ll>
#define vs			vector< string >
#define vvi         vector< vector< ll > >
#define inf			1'010'000'000'000'000'017LL
#define all(it,a)   for(auto it=(a).begin();it!=(a).end();it++) 
#define sz(x)       (ll)x.size()
#define rep(i,a,b)	for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=a;i>b;i--)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define mp          make_pair
#define whatis(x)   cout << #x << " is " << x << "\n";
#define graph(n)    adj(n,vector< ll > () )

using namespace std;

template<class T>
bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T>
bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
ll DivisorCount(ll x) {
	ll ans = 1;
	for (int i = 2; i <= sqrt(x); i++) {
		int cnt = 0;
		while (x % i == 0) {
			cnt++;
			x /= i;
		}
		ans *= (cnt + 1);
		if (x == 1) break;
	}
	if (x != 1) ans *= 2;
	return ans;
}

void Main() {
	ll N;
	cin >> N;
	vi A(N, 0);
	rep(i, 0, N) cin >> A[i];

	ll money = 1000;
	ll stock = 0;

	rep(i, 0, N - 1) {
		money += stock * A[i];
		stock = 0;
		if (A[i + 1] > A[i]) {
			stock += (money / A[i]);
			money -= stock * A[i];
		}
	}
	money += stock * A[N - 1];

	std::cout << money << endl;
}




int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);

	Main();
	return 0;
}


Measured memory_bytes: 3648
// D - Dice in Line
#include <bits/stdc++.h>
using namespace std;
#define rp(i,s,e) for(int i=(s);i<(e);++i)
template<class T> vector<T> inarr(int s,int e, T init=0){
	vector<T> v;T x;
	for(int i=0;i<s;++i)v.push_back(init);
	for(int i=s;i<e;++i){cin>>x;v.push_back(x);}
	return v;
}

using VD = vector<double>;
int N,K;
VD P;

double solve(){
	double ans = 0;
	VD X(N);
	rp(i,0,N) X[i] = (P[i]+1.0)/2.0;
	VD Y(N+1);
	rp(i,0,N) Y[i+1] = Y[i] + X[i];
	rp(i,0,N-K+1) ans = max(ans, Y[i+K]-Y[i]);
	return ans;
}

int main(){
	cin>>N>>K;
	P = inarr<double>(0,N);
	printf("%.12f\n",solve());
}

Measured memory_bytes: 5104
#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define sz(a) (int)a.size()
#define int long long

using namespace std;

vector <pair <int, int>> g[100010];

vector <vector <int>> v;

int a[100010];
int used[100010];

void dfs(int vv) {
    used[vv] = 1;
    for (auto u : g[vv]) {
        if (used[u.X] == 1)
            continue;
        a[u.X] = a[vv] + u.Y;
        dfs(u.X);
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    int l, r, d;
    for (int i = 0; i < m; i++) {
        cin >> l >> r >> d;
        l--;
        r--;
        g[l].pb({r, d});
        g[r].pb({l, -d});
        v.pb({l, r, d});
    }
    for (int i =0; i < n; i++) {
        if (used[i] == 0) {
            dfs(i);
        }
    }
    for (int i = 0; i < m; i++) {
        if (a[v[i][1]] - a[v[i][0]] != v[i][2]) {
            cout << "No" << endl;
            exit(0);
        }
    }
    cout << "Yes";
    return 0;
}


Measured memory_bytes: 26796
#include <iostream>
#include <vector>

using namespace std;

class Lca {
    int N;
    int logN;
    vector<int> depths;
    vector<vector<int>> edge;

    // dop[i][j]: 2^j th parent node from i th node
    vector<vector<int>> dp;

    void calc_depth(int cur, int par, int depth) {
        depths[cur] = depth;
        dp[cur][0] = par;
        for (int ch : edge[cur]) {
            if (ch == par) continue;
            calc_depth(ch, cur, depth + 1);
        }
    }

    void calc_dp() {
        for (int k = 1; k < logN; k++) {
            for (int i = 0; i < N; i++) {
                if (dp[i][k - 1] == -1) {
                    dp[i][k] = -1;
                } else {
                    dp[i][k] = dp[dp[i][k - 1]][k - 1];
                }
            }
        }
    }

public:
    Lca(const vector<vector<int>> &edge, int root) : edge(edge) {
        N = edge.size();
        logN = (sizeof(int) * 8) - __builtin_clz(N);
        depths.resize(N);
        dp.resize(N);
        for (int i = 0; i < N; i++) dp[i].resize(logN, -1);
        calc_depth(root, -1, 0);
        calc_dp();
    }

    // O(logN)
    int lca(int u, int v) {
        // assume depths[u] <= depths[v]
        if (depths[u] > depths[v]) swap(u, v);

        // equalize depth
        int diff = depths[v] - depths[u];
        for (int k = 0; k < logN; k++) {
            if ((diff >> k) & 1) {
                v = dp[v][k];
            }
        }

        if (u == v) return u;

        for (int k = logN - 1; k >= 0; k--) {
            if (dp[u][k] != dp[v][k]) {
                u = dp[u][k];
                v = dp[v][k];
            }
        }

        return dp[u][0];
    }
};


// verified
//  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C&lang=ja
void AOJ_GRL_5_C() {
    int n, k, c, q, u, v;
    cin >> n;
    vector<bool> is_root(n, true);
    vector<vector<int>> edge(n);
    for (int i = 0; i < n; i++) {
        cin >> k;
        for (int j = 0; j < k; j++) {
            cin >> c;
            is_root[c] = false;
            edge[i].push_back(c);
            edge[c].push_back(i);
        }
    }
    int root = -1;
    for (int i = 0; i < n; i++) if (is_root[i]) root = i;
    Lca lca(edge, root);
    cin >> q;
    while (q--) {
        cin >> u >> v;
        cout << lca.lca(u, v) << '\n';
    }
}

int main() {
    AOJ_GRL_5_C();
    return 0;
}


Measured memory_bytes: 27364
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int H, N;
 
vector<int> cost;
vector<int> value;
 
unsigned long dp[10000] = {0};
 
int DP(int a)
{
  	if (a <= 0) {
    	return 0;
    }
    if (dp[a] != -1) {
//        cout << "DP[" << a << "]: " << dp[a] << "(cache)" << endl;
        return dp[a];
    }
    bool isFirst = true;
    unsigned long min = INT_MAX;
    for (int i = 0; i < N; i++) {
//        if (a - value[i] >= 0) {
            unsigned long v = DP(a - value[i]) + cost[i];
            if ( isFirst ) {
                min = v;
                isFirst = false;
            } else {
                min = (v < min) ? v : min;
            }
//        }
    }
    dp[a] = min;
//    cout << "DP[" << a << "]: " << dp[a] << endl;
    return min;
}
 
int main()
{
 
    cin >> H >> N;    
    unsigned long c, v;
  
  	for (int i = 1; i <= H; i++) {
		dp[i] = -1;
    }
  
  	dp[0] = -1;
    for (int i = 0; i < N; i++) {
        cin >> v >> c;
        value.push_back(v);
        cost.push_back(c);
    }
    cout << DP(H) << endl;
    return 0;
}

Measured memory_bytes: 768
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>

#define maxn 205
#define maxm 10000005

using namespace std;

inline int getint()
{
	int num=0,flag=1;char c;
	while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
	while(c>='0'&&c<='9')num=num*10+c-48,c=getchar();
	return num*flag;
}

int n,N;
int a[maxn],w[maxn][maxn],link[maxn];
int pri[maxm],cnt;
bool np[maxm],col[maxm],vis[maxn];
int X[maxn],Y[maxn],ans;

inline void init()
{
	np[1]=1;
	for(int i=2;i<=N;i++)
	{
		if(!np[i])pri[++cnt]=i;
		for(int j=1;j<=cnt&&i*pri[j]<=N;j++)np[i*pri[j]]=1;
	}
}

inline bool match(int x)
{
	for(int i=1;i<=Y[0];i++)if(w[x][i]&&!vis[i])
	{
		vis[i]=1;
		if(!link[i]||match(link[i])){link[i]=x;return 1;}
	}
	return 0;
}

int main()
{
	n=getint();
	for(int i=1;i<=n;i++)N=max(N,a[i]=getint()),col[a[i]]=1;
	N++;init();
	for(int i=1;i<=N;i++)if(col[i]^col[i-1])i&1?X[++X[0]]=i:Y[++Y[0]]=i;
	for(int i=1;i<=X[0];i++)for(int j=1;j<=Y[0];j++)w[i][j]=!np[abs(X[i]-Y[j])];
	for(int i=1;i<=X[0];i++)
	{
		memset(vis,0,sizeof vis);
		ans+=match(i);
	}
	ans+=2*((X[0]-ans)/2)+2*((Y[0]-ans)/2)+3*((X[0]-ans)&1);
	printf("%d\n",ans);
}

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

const ll INF = 1LL << 62;
const double PI = acos(-1);
const double eps = 1e-10;

int main() {
  ll h, w;
  cin >> h >> w;
  map<char, int> mp;
  char a;
  rep(i, h) rep(j, w) cin >> a, mp[a]++;
  ll cnt4 = 0, cnt2 = 0, cnt1 = 0;
  for (auto x : mp) {
    if (x.second % 4 == 0) {
      cnt4++;
    } else if (x.second % 2 == 0) {
      cnt2++;
    } else {
      cnt1++;
    }
  }
  // cerr << cnt4 << " " << cnt2 << " " << cnt1 << endl;

  if ((h % 2 == 1) && (w % 2 == 1)) {
    cout << (cnt1 <= 1 && cnt2 <= (h + w - 2) / 2 ? "Yes" : "No") << endl;
  } else if ((h % 2 == 1) && (w % 2 == 0)) {
    cout << (cnt1 == 0 && cnt2 <= w / 2 ? "Yes" : "No") << endl;
  } else if ((h % 2 == 0) && (w % 2 == 1)) {
    cout << (cnt1 == 0 && cnt2 <= h / 2 ? "Yes" : "No") << endl;
  } else {
    cout << (cnt1 == 0 && cnt2 == 0 ? "Yes" : "No") << endl;
  }
  return 0;
}


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

bool solve(int A, int B, int C, int K) {
  if (A < B && B < C) return true;
  if (K == 0) return false;
  return solve(2 * A, B, C, K - 1) || solve(A, 2 * B, C, K - 1) ||
         solve(A, B, 2 * C, K - 1);
}
int main(void) {
  int A, B, C, K;
  cin >> A >> B >> C >> K;
  cout << (solve(A, B, C, K) ? "Yes" : "No") << endl;
  return 0;
}

Measured memory_bytes: 3640
from fractions import gcd

mod = 10 ** 9 + 7

N, *A = map(int, open(0).read().split())

L = 1
for a in A:
    L *= a // gcd(L, a)

L %= mod

print(sum(L * pow(a, mod - 2, mod) for a in A) % mod)

Measured memory_bytes: 6072
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>
#include <cassert>

using namespace std;

typedef long long ll;

const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

template<class T>inline void read(T &res)
{
	char c;T flag=1;
	while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
	while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}

int a,b,c,k;

int main()
{	
	scanf("%d%d%d%d",&a,&b,&c,&k);
	int sum=0;
	if(a<k)
	{
		sum+=a;
		k-=a;
	}
	else
	{
		sum+=k;
		printf("%d\n",sum);
		return 0;
	}
	if(b<k)
	{
		sum+=0;
		k-=b;
	}
	else
	{
		sum+=0;
		printf("%d\n",sum);
		return 0;
	}
	if(c<k)
	{
		sum-=c;
		k-=c;
	}
	else 
	{
		sum-=k;
		printf("%d\n",sum);
		return 0;
	}
}


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

int main() {
    int64_t w, h, x, y;
    cin >> w >> h >> x >> y;

    double eps = 1.0e-9;
    double a, b, x1, x2, s;
    
    if (abs(x - w / 2.0) > eps ){
        a = (y - h / 2.0) / (x - w / 2.0);
    
        if (abs(a - (double)h / w) > eps && abs(a + (double)h / w) > eps){

            b = y - a * x;
        
            if ( a >= (double)h / w || a <= - (double)h / w){
                x1 = (h - b) / a;
                x2 = - b / a;
                s = h * x1 + (x2 - x1) * h / 2;
            }
            else{
                x1 = a * w + b;
                x2 = b;
                s = w * x2 + (x1 - x2) * w / 2;
            }
        }
        else{
            s = h * w / 2.0;
        }
    }
    else{
        s = h * w / 2.0;
    }

    int ret = 0;
    if ((abs(w / 2.0 - x) < eps) && (abs(h / 2.0 - y) < eps)){
        ret = 1;
    }
    cout << s << " " << ret << endl;
}

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

#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define RFOR(i, a, b) for(int i=(a); i>=(b); i--)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) RFOR(i, n, 0)
#define dump(x)  cout << #x << " = " << (x) << endl;

typedef long long ll;
typedef pair<int, int> ii;
const ll INF = 1e18;
const int inf = 1e8;


void solve()
{
  ll A;
  scanf("%lld",&A);
  ll B;
  scanf("%lld",&B);
  if (B%A==0) cout << A+B << endl;
  else cout << B-A << endl;
}

int main()
{
  solve();
  return 0;
}


Measured memory_bytes: 256
N = int(input())

cntm = 0
ans = 1

for i in range(1, N+1):
    a = i
    cnt = 0
    while a % 2 == 0:
        a /= 2
        cnt += 1
    if cnt > cntm:
        cntm = cnt
        ans = i
         
print(ans)

Measured memory_bytes: 3060
N, K =  map(int, (input().split(' ')))
S = str(input())

zero_positions = [0] + [i for i, c in enumerate(S) if c==0]
count0 = 0
start = 0
end = 0
numbers = 0
index = 0
load_0 = False
l_0 = False
scores = []
while True:
    if (not load_0) and S[index] == '0':
        count0 += 1
        load_0 = True
    elif load_0 == True and S[index] == '1':
        load_0 = False
    if count0 == K+1:
        scores.append((index-1) - start + 1)
        if (not l_0) and S[start] == '0':
            l_0 = True
        while count0 > K:
            start += 1
            if (not l_0) and S[start] == '0':
                l_0 = True
            elif l_0 == True and S[start] == '1':
                count0 -= 1
                l_0 = False
    if index == N - 1 :
        scores.append(index-start + 1)
        break
    index += 1
        
print(max(scores))


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

int main() 
{
  int64_t a, b, c, d;
  cin >> a >> b >> c >> d;
  
  int64_t answer = a * c;
  
  if(answer < a * d)
  { answer = a * d;}
  
  if(answer < b * c)
  { answer = b * c;}
  
  if(answer < b * d)
  { answer = b * d;}
  
  cout << answer << endl;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool isprime(ll n){
    bool flag=1;
    for (ll i = 2; i <= sqrt(n); i++) { 
        if (n % i == 0) { 
            flag = 0; 
            break; 
        } 
    }
    return flag;
}
int main(){
    ll A,B;
    cin>>A>>B;
    set<int> fact;
    ll temp1=A;
    ll temp2=B;
    A=min(temp1,temp2);
    B=max(temp1,temp2);
    ll count=0;
    for(ll i=1;i<=sqrt(A);i++){
        if(A%i==0){
            fact.insert(i);
            if(isprime(i)&&(B%i==0)){
                count++;
            }
            ll x=A/i;
            fact.insert(A/i);
            if(isprime(x)&&(B%x==0)&&(x!=i)){
                count++;
            }
        }
    }
    cout<<count<<endl;
    return 0;
    
}

Measured memory_bytes: 512
import sys
from collections import deque

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())


def main():
    S = deque(INPUT())
    Q = INT()

    flag_order = True
    D_MAP = lambda: map(str, query.split())
    for i in range(Q):
        query = INPUT()
        if len(query.split()) == 1:
            T = 1
        else:
            T = 2
            _, F, C = D_MAP()
            F = int(F)

        if T == 1:
            if flag_order: flag_order = False
            else: flag_order = True
        if T == 2:
            if flag_order:
                if F == 1: S.appendleft(C)
                else: S.append(C)
            else:
                if F == 1: S.append(C)
                else: S.appendleft(C)

    print(''.join(S) if flag_order else ''.join(reversed(S)))


if __name__ == '__main__':
    main()

Measured memory_bytes: 8428