akhauriyash/Code-Regression huggingface dataset:
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include<bits/stdc++.h>
using namespace std;

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

template<class T> bool chmin(T& a,T b){
    if(a > b){ a = b; return true; }else return false;
}
template<class T> bool chmax(T& a,T b){
    if(a < b){ a = b; return true; }else return false;
}
template<class T> void debug_array(vector<T> a){
    int size = min(15,(int)a.size());
    cout << "{";
    for(int i = 0;i < size;i++){
        cout << a[i] << (i < size - 1 ? "," : "}\n");
    }
}
template<class T> void debug_array(vector<vector<T>> a){
    int n = min(15,(int)a.size()),m = min(10,(int)a[0].size());
    cout << "{\n";
    for(int i = 0;i < n;i++){
        debug_array(a[i]);
    }
    cout << "}\n";
}
vector<vector<int64_t >> dp(3030,vector<int64_t >(3030,0));
class FLCS {
public:
	void solve(std::istream& cin, std::ostream& cout) {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);

        //rep(i,3030)rep(j,3030)dp[i][j] = 0;

        string s,t;cin >> s >> t;
        int64_t n = s.size(), m = t.size();

        for(int i = 1;i <= n;i++)for(int j = 1;j <= m;j++){
            if(s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            chmax(dp[i][j],dp[i - 1][j]);
            chmax(dp[i][j],dp[i][j - 1]);
        }

        string ans = "";

        int x = n,y = m,now = dp[n][m];

        for(int val = now;val > 0;val--){
            for(;y > 0;y--){
                if(dp[x][y] == dp[x][y-1] + 1)break;
            }
            for(;x > 0;x--){
                if(dp[x][y] == dp[x-1][y] + 1)break;
            }
            //cout << x << ' ' << y << '\n';
            ans += (char)s[x - 1];
            x--,y--;
        }
        //debug_array(dp);
        reverse(ans.begin(),ans.end());
        cout << ans << '\n';

	}
	void main2(istream& cin,ostream& cout){

	}
};


int main() {
	FLCS solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 72192
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
BC=[list(map(int,input().split())) for i in range(Q)]
goukeiti=sum(A)
atai=[0]*(10**5+1)
for i in A:
    atai[i-1]+=1
for i in BC:
    kotae=atai[i[0]-1]*i[1]-atai[i[0]-1]*(i[0])
    atai[i[1]-1]+=atai[i[0]-1]
    atai[i[0]-1]=0
    goukeiti+=kotae
    print(goukeiti)


Measured memory_bytes: 32044
a,b = list(map(int,input().split(" ")))
s = input()
postal_code_len = a+b+1

num_list = list(map(str, range(0,10)))

flag = True
#print([c in num_list for c in list(s[:a]+s[a+1:]) ])
if s[a] == "-" and all([ c in num_list for c in list(s[:a]+s[a+1:]) ]):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  int N;
  cin >> N;
  if(N%2==0)
  {
    cout << (N/2)*(N/2) << endl;
  }
  else
  {
    cout << (N/2+1)*(N/2) << endl;
  }
  return 0;
}


Measured memory_bytes: 256
/*
[ ( ^ _ ^ ) ]
*/
// problem: atc/abc165_f
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1000000000

const int nax = 200005;
const int sz = 4 * nax;
vector<int> segtree(sz);
vector<vector<int>> g(nax);
vector<int> a(nax), rs(nax);
int n;


void upd(int idx, int s, int e, int p, int v) {
    if(p<s || e<p || e<s) return;
    if(s==p && e==p) {
        segtree[idx] = v;
        return;
    }
    int mid = s + (e-s)/2;
    int l = 2*idx; int r = l + 1;
    if(p<=mid) {
        upd(l, s, mid, p, v);
    } else {
        upd(r, mid+1, e, p, v);
    }
    segtree[idx] = max(segtree[l], segtree[r]);
}

int get(int idx, int s, int e, int l, int r) {
    if(e<s) return 0;
    if(r<s || e<l) return 0;
    if(l<=s && e<=r) {
        return segtree[idx];
    }
    int mid = s + (e-s)/2;
    int lc = 2*idx; int rc = lc+1;
    int x = get(lc, s, mid, l, r);
    int y = get(rc, mid+1, e, l, r);
    return max(x, y);
}

int get(int idx, int s, int e, int p) {
    return get(1, s, e, p, p);
}

void dfs(int v, int p) {
    int mx = get(1, 0, n-1, 0, a[v]-1);
    rs[v] = mx+1;
    int prev = get(1, 0, n-1, a[v]);
    upd(1, 0, n-1, a[v], max(rs[v], prev));
    for(int u: g[v]) {
        if(u==p) continue;
        dfs(u, v);
    }
    upd(1, 0, n-1, a[v], prev);
}

void dfs2(int v, int p) {
    for(int u: g[v]) {
        if(u==p) continue;
        rs[u] = max(rs[u], rs[v]);
        dfs2(u, v);
    }
}

int main() {
    scanf("%d", &n);
    vector<int> b(n+1);
    for(int i=1; i<=n; i++) {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    sort(b.begin()+1, b.end());
    for(int i=1; i<=n; i++) {
        a[i] = lower_bound(b.begin()+1, b.end(), a[i]) - (b.begin()+1) + 1;
    }
    for(int i=0; i<n-1; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    dfs(1, -1);
    dfs2(1, -1);
    for(int i=1; i<=n; i++) {
        printf("%d\n", rs[i]);
    }
}


Measured memory_bytes: 34012
#include<bits/stdc++.h>
// #define int long long
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define repa(i, s, n) for(int i = s; i < (int)n; i++)
#define MOD 1000000007
using namespace std;
using ll = long long;
typedef vector<int> vi;

signed main() {
    int n, k;
    cin >> n >> k;
    ll ans = k;
    rep(i, n-1){
        ans *= k - 1;
    }

    cout << ans << endl;

}

Measured memory_bytes: 3524
#include <algorithm>
#include <iomanip>
#include <ctime>
#include <iostream>
#include <cstdlib>
#define sbc __builtin_popcount
#define pb push_back
#define em emplace
#define emb emplace_back
int mod = 1e9+7;
using namespace std;
// template<typename T>
	// T pwm(T a,T b)
    // {
        // T p=1,one=1;
        // while(b)
        // {
            // if(b&one) p=p*a%mod;
            // a=a*a%mod;
            // b >>=1;
        // }
        // return p;
    // }

    void solve() {
		long long n,a,b,tmp;
		cin>>n>>a>>b;
		
		tmp=n/(a+b);
		tmp*=a;
		tmp+=min(n%(a+b),a);
		cout<<tmp<<'\n';
    }

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

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

int s,b;
int a[15];
int t=0;

bool check(int num)
{
    t=0;
    while (num)
    {
        a[t]=num%10;
        num/=10;
        t++;
    }
    t--;
    for (int i=0; i<=t; ++i)
        if (a[i]!=a[t-i])
            return 0;
    return 1;
}
int main()
{
    cin>>s>>b;
    int ans=0;
    for (int i=s; i<=b; ++i)
        if (check(i))
            ans++;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <stack>

#define REP(i,n) for(int i = 0; i < (n); ++i)
#define REPC(x,c) for(auto x:(c))
#define FOR(i, b, e) for(int i = (b); i < (e); ++i)
#define VS vector<string>
#define VI vector<int>
#define VVI vector<vector<int>>
#define ALL(x) (x).begin(),(x).end()

using  ll = long long;

using namespace std;

int main() {
	int n;
	cin >> n;
	VI v(n);
	ll sum = 0;
	REP(i, n) {
		cin >> v[i];
		v[i] -= (i + 1);
		sum += v[i];
	}

	sort(ALL(v));
	int mid = n / 2;
	VI l = { v[mid-1], v[mid], v[mid+1]};
	

	ll mn = -1;
	REPC(c, l) {
		ll sum = 0;
		REPC(x, v) {
			sum += abs(x - c);
		}
		if (mn < 0) { mn = sum; }
		else { mn = min(sum, mn); };
	}
	cout << mn << endl;
}

Measured memory_bytes: 1024
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_D main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LLONG_MAX/2)
const int MGN = 10;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using psi = pair<string, int>;
// functions
template<typename T> 
inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
#endif 


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

    ll N, W; cin >> N >> W;
    vl w(N+1,0); vl v(N+1,0);
    FOR(i,1,N+1) cin >> w[i] >> v[i];

    ll WMIN = LINF;
    FOR(i,1,N+1) WMIN = min(WMIN, w[i]);    

    vi r(N+1,0);
    FOR(i,1,N + 1) r[i] = w[i] - WMIN;

    vi rs(N+1, 0);
    FOR(i,1,N + 1) rs[i] = rs[i - 1] + r[i];

    const ll NMAX = 100;
    const ll RMAX = 3 * NMAX;
    vector<vvl> dp(N+MGN, vvl(N+MGN, vl(RMAX+MGN, 0)));

    FOR(i,1,N+1) {
        for(int j=0; j<=i; j++) {
            for (int k = 0; k <= rs[i]; k++) {
                if (k+r[i] <= rs[i]) {
                    chmax(dp[i + 1][j + 1][k + r[i]], dp[i][j][k] + v[i]);
                }

                chmax(dp[i+1][j][k], dp[i][j][k]);
            }
        }
    }

    ll ans = 0;
    FOR(j,0,N+1) {
        FOR(k,0,rs[N]+1) {
            ll w = WMIN * j + k;
            if (w <= W){
                ans = max(ans, dp[N+1][j][k]);
            }
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 30336
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
    int a[4];
    rep(i,4)cin>>a[i];
    sort(a,a+4);
    if(a[0]==1&&a[1]==4&&a[2]==7&&a[3]==9)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;    
    return 0;
}


Measured memory_bytes: 256
S = input()

Slis = list(S)

SLEN = len(Slis)

ans = 0

for i in range(SLEN):
    if i % 2 == 0 and (Slis[i] == "R" or Slis[i] == "U" or Slis[i] == "D"):
        continue
    elif i % 2  == 1 and (Slis[i] == "L" or Slis[i] == "U" or Slis[i] == "D"):
        continue
    else:
        ans = ans + 1

if ans == 0:
    print("Yes")
else:
    print("No")
 

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 110;
int n,m,a[M],b[N],cnt,tot,res[N];
int rec[3];
int main() {
	scanf("%d%d",&n,&m);
	for (int i = 1;i <= m; ++ i) {
		scanf("%d",&a[i]);
		cnt += a[i]&1;
		if (a[i]&1 && cnt <= 2) rec[cnt] = a[i];
	}
	if (cnt > 2) return 0*puts("Impossible");
	if (cnt) res[++tot] = rec[1];
	for (int i = 1;i <= m; ++ i) if (a[i]%2==0) res[++tot] = a[i];
	if (cnt > 1) res[++tot] = rec[2];
	tot = 0;
	if (res[1] != 1) b[++tot] = res[1] - 1;
	for (int i = 2;i < m; ++ i) {
		b[++tot] = res[i];
	}
	if (m == 1) b[++tot] = 1;
	else b[++tot] = res[m] + 1;
	for (int i = 1;i <= m; ++ i) printf("%d ",res[i]);
	printf("\n%d\n",tot);
	for (int i = 1;i <= tot; ++ i) printf("%d ",b[i]);
	puts("");
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const long long INF=INT_MAX/4;
const long long MOD=1'000'000'007;
const double EPS=1e-14;
const bool DEBUG=false;

const string YES = "YES";
const string NO = "NO";
const string Yes = "Yes";
const string No = "No";

template<class T>
void debug(T head){
    if(DEBUG){
        cout<<head<<endl;
    }
}

template <class Head, class... Body>
void debug(Head head, Body... body){
    if(DEBUG){
        cout<<head<<" ";
        debug(body...);
    }
}

/////
void answer(){
    unsigned long long a, b, x;
    cin>>a>>b>>x;
    if(x==1){
        cout<<b-a+1<<endl;
        return;
    }
    if(a==0){
        cout<<b/x + 1<<endl;
        return;
    }
    if(a==b){
        if(a%x==0){
            cout<<1<<endl;
            return;
        }
    }
    cout<<(b/x+1) - ((a-1)/x+1)<<endl;

    return;
}
/////

int main(int argc, char* argv[]){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout.precision(16);

    answer();

    return 0;
}


Measured memory_bytes: 3652
let swap a i j = let x = a.(i) and y = a.(j) in a.(i) <- y;a.(j) <-x;;

let w = read_int () and
    n = read_int () in
    let a = Array.init w (fun x->(x+1)) in
    for i = 1 to n do
      let (x,y) = Scanf.scanf "%d,%d\n" (fun x y->(x,y)) in swap a (x-1) (y-1);
    done;
    Array.iter (fun k -> Printf.printf "%d\n" k) a;;

Measured memory_bytes: 2364
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;

int main(){
        int n,k;
        cin>>n>>k;
        int h[n];
        for(int i=0;i<n;i++){
            cin>>h[i];
        }
        sort(h,h+n);
        int ans=h[k-1]-h[0];
        for(int i=1;i<n-k+1;i++){
            if(ans>(h[i+k-1]-h[i])){
                ans=h[i+k-1]-h[i];
            }
        }
        cout<<ans;
    return 0;
}

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

namespace Contest
{
    class ABC
    {
        static void Main()
        {
            Solve();
        }

        private static void Solve()
        {
            int n = int.Parse(Console.ReadLine());
            int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int[] a = new int[n];
            for(int i = 0; i < n; i++)
            {
                a[input[i] - 1] = i + 1;
            }
            StringBuilder sb = new StringBuilder();
            foreach(var x in a)
            {
                sb.Append(x);
                sb.Append(" ");
            }
            Console.WriteLine(sb.ToString());
        }
    }
}


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

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define ll long long
const ll mod = 1e9+7;
int inf = 1000000000; //10e9
 
int main() {

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

    vector<int> ans(n);
    rep(i,n){
        ans[a[i]-1] = i+1;
    }
    rep(i,n) cout << ans[i] << ' ';
    cout << endl;

    return 0;

}

Measured memory_bytes: 3928
#include<bits/stdc++.h>
#define For(i,l,r) for(int i = (l),i##end = (r);i <= i##end;i++)
#define Fordown(i,r,l) for(int i = (r),i##end = (l);i >= i##end;i--)
using namespace std;
typedef long long ll;
const int INF = 1e9;
const int N = 2e5 + 10,Lim = 2e3 + 10;
const int mod = 1e9 + 7;
int dp[Lim << 1][Lim << 1],fac[Lim << 2],inv[Lim << 2];
struct node{
	int x,y;
}Point[N];
inline int read(){
	int x = 0,flag = 1;
	char ch = getchar();
	while(!isdigit(ch) && ch != '-')ch = getchar();
	if(ch == '-')flag = -1,ch = getchar();
	while(isdigit(ch))x = (x << 3) + (x << 1) + ch - '0',ch = getchar();
	return x * flag;
}
inline int fpm(int a,int b){
	int res = 1;
	while(b){
		if(b & 1)res = 1ll * res * a % mod;
		a = 1ll * a * a % mod,b /= 2;
	}
	return res;
}
inline void init(int n){
	fac[0] = 1;
	For(i,1,n)fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[n] = fpm(fac[n],mod - 2);
	Fordown(i,n,1)inv[i - 1] = 1ll * inv[i] * i % mod;
}
inline int Mod(int val){
	if(val >= mod)val -= mod;
	if(val < 0)val += mod;
	return val;
}
inline int C(int n,int m){
	return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int main(){
	int n = read();
	init((Lim - 5) << 2);
	int ans = 0;
	For(i,1,n){
		int x = read(),y = read();
		dp[Lim - x][Lim - y]++;
		ans = (ans + C((x << 1) + (y << 1),x << 1)) % mod;
		Point[i] = (node){x,y};
	}
	ans = Mod(-ans);
	int Max = (Lim << 1) - 5;
	For(i,1,Max)For(j,1,Max)
		dp[i][j] = Mod(dp[i][j] + dp[i - 1][j] + dp[i][j - 1]);
	For(i,1,n)ans = Mod(ans + dp[Lim + Point[i].x][Lim + Point[i].y]);
	printf("%lld\n",1ll * ans * fpm(2,mod - 2) % mod);
	return 0;
}

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

#define ll long long
#define sd(x) scanf("%d", &(x))
#define pii pair<int, int>
#define F first
#define S second
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#define ld long double

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<", "<<p.second<<")";
	return os;
}

template<class T,class U>
ostream& operator<<(ostream& os,const map<T, U> & mp){
	os << "{";
	int i = 0;
	for(auto it : mp){
		if(i) os<<", ";
		os << it;
		i++;
	}
	os << "}";	
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"{";
	for(int i = 0;i < (int)v.size(); i++){
		if(i)os<<", ";
		os<<v[i];
	}
	os<<"}";
	return os;
}

#ifdef LOCAL
#define cerr cout
#else
#endif

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const int mod = 998244353;
inline int add(int x, int y){ x += y; if(x >= mod) x -= mod; return x;}
inline int sub(int x, int y){ x -= y; if(x < 0) x += mod; return x;}
inline int mul(int x, int y){ return (x * 1ll * y) % mod;}
inline int powr(int a, ll b){
	int x = 1 % mod;
	while(b){
		if(b & 1) x = mul(x, a);
		a = mul(a, a);
		b >>= 1;
	}
	return x;
}
inline int inv(int a){ return powr(a, mod - 2);}

const int N = 200005;
char num[N];
int ways[N];
int pw2[N];
int f[N];
vector<int> divisors[N];
int main(){
	int n; sd(n);
	scanf("%s", num);
	// reverse(num, num + n);
	int ans = 2 * n;
	int x = 0;
	for(int i = 0; i < n; i++){
		x = (2 * x) % mod;
		if(num[i] == '1') x ++;
		x %= mod;
	}
	ans = add(ans, mul(2 * n, x));
	pw2[0] = 1;
	// trace(x, ans);
	for(int i = 1; i < N; i++) pw2[i] = mul(2, pw2[i - 1]);
	for(int d = 1; d <= n; d++) if(n % d == 0){
		for(int i = 0; i < d; i++) if(num[i] == '1'){
			// first difference at i
			f[d] = add(f[d], pw2[d - 1 - i]);
		}
		int v = 1;
		for(int i = 0; i < n; i++){
			int pos = i  % (2 * d);
			int val1 = num[i] - '0';
			int val2 = pos >= d ? (1 ^ (num[pos - d] - '0')) : (num[pos] - '0');
			if(val1 < val2){
				v = 0;
				break;
			}
			else if(val1 > val2) break;
		}
		// trace(d, f[d], v);
		f[d] = add(f[d], v);
	}
	for(int t = 1; t <= n; t++){
		int l = n % t;
		int g = __gcd(l, t);
		if(l == 0 || (t / g) % 2 == 1) continue;
		ways[t] = f[g];
		for(int h = 2 * t; h <= n; h += t) divisors[h].push_back(t);
	}
	for(int i = 1; i <= n; i++){
		for(int j : divisors[i]) ways[i] = sub(ways[i], ways[j]);
		// if(n==30)trace(i, ways[i]);
		ans = sub(ans, mul(2 * n - i, ways[i]));
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 15488
#include <stdio.h>

int main()
{
	int input[3];
	int ans = 2147483647;

	scanf("%d %d %d", &input[0], &input[1], &input[2]);

	for (int i = 0; i < 3; ++i)
	{
		for (int j = i + 1; j < 3; ++j)
		{
			if (input[i] + input[j] < ans) ans = input[i] + input[j];
		}
	}

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

	return 0;
}

Measured memory_bytes: 128
#include<stdio.h>


int main(){
  long long  n,k,a[2001];
  long long t=0,ans=0,cntr=0,cntl=0,i,j,l,M=1e9+7;
  scanf("%lld%lld",&n,&k);
  for(i=0;i<n;i++){
    scanf("%lld",&a[i]);
    if(i!=0){
      for(j=0;j<i;j++){
        if(a[j]<a[i])cntl++;
      }
    }
  }

for(i=0;i<n;i++){
  for(j=n-1;j>i;j--){
    if(a[j]<a[i])cntr++;
  }
}

/*for(int i=0;i<n;i++){
  printf("%d %d\n",cntr[i],cnt[i]);
}*/
//printf("%lld %lld\n",cntl,cntr );

for(i=1;i<=k;i++){
  t+=((cntr+cntl)*(i-1))%M+cntr%M;
}
  printf("%lld\n",t%M);
  return 0;
}


Measured memory_bytes: 128
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
    ll n, a, b; cin>>n>>a>>b;
    ll q=n/(a+b), r=n%(a+b);
    cout<<q*a+min(a, r)<<endl;
	return 0;
}


Measured memory_bytes: 256
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn main() {
    let v1 = read_vec::<u32>();
    let _n = v1[0];
    let m = v1[1];
    let mut min = 0;
    let mut max = 100000;

    for _i in 0..m {
        let v = read_vec::<u32>();
        let l = v[0];
        let r = v[1];

        if min < l {
            min = l;
        }
        if max > r {
            max = r;
        }
    }

    if max < min {
        println!("{}", 0);
    } else {
        println!("{}", max - min + 1);
    }
}


Measured memory_bytes: 4476
import unittest
import collections


class TestD(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think('a', ['2 1 p', '1', '2 2 c', '1']), 'cpa')

    def test_2(self):
        self.assertEqual(think('a', ['2 2 a', '2 1 b', '1', '2 2 c', '1', '1']), 'aabc')

    def test_3(self):
        self.assertEqual(think('y', ['2 1 x']), 'xy')


def solve():
    s, queries = read()
    result = think(s, queries)
    write(result)


def read():
    s = read_line()
    q = read_int(1)[0]
    queries = []
    for _ in range(q):
        queries.append(read_line())
    return s, queries


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(s, queries):
    buf = collections.deque(list(s))
    reverse = False
    for q in queries:
        splitted = q.split()
        if splitted[0] == '1':
            reverse = not reverse
        elif splitted[0] == '2':
            f = splitted[1]
            c = splitted[2]
            if f == '1':
                if reverse:
                    buf.append(c)
                else:
                    buf.appendleft(c)
            elif f == '2':
                if reverse:
                    buf.appendleft(c)
                else:
                    buf.append(c)
            else:
                raise RuntimeError()
        else:
            raise RunntimeError()
    result = ''.join(list(buf))
    return result[::-1] if reverse else result


def write(result):
    print(result)


if __name__ == '__main__':
    # unittest.main()
    solve()

Measured memory_bytes: 106836
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;

void solve() {
    int N;
    cin >> N;
    map<ll,ll> mp; // counter
    REP(i,N) {
        ll x;
        cin >> x;
        if  (mp.count(x) ==  0) mp[x] = 0;
        mp[x]++;
    }

    ll ans = 0;
    for(const auto &it: mp) {
        ans += it.first * it.second;
    }

    int Q;
    cin >> Q;
    REP(_,Q) {
        int b,c;
        cin >> b >> c;
        if (mp.count(b) == 0) {
            cout << ans << endl;
            continue;
        }
        auto tmp = mp[b];
        mp[b] = 0;
        if (mp.count(c) == 0) mp[c] = 0;
        mp[c] +=  tmp;
        ans += (c-b)*tmp;
        cout << ans << endl;
    }




}

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

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

int main(void)
{
    int n; cin >> n;
    string st, s; cin >> st;
    if(st.size() > n)
    {
        s = st.substr(0, n);
        cout << s << "...";
    }
    else
    {
        s = st;
        cout << s;
    }
}

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

#define EQ(a,b) (abs((a)-(b)) < EPS)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define sz size()
#define all(a) (a).begin(),(a).end()

using namespace std;
typedef double D;
typedef complex<D> P;
typedef pair<P,P> L;
typedef vector<P> Poly;
typedef pair<P,D> C;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<D,int> pdi;

const D EPS = 1e-8;
const D PI = acos(-1);

//for vector
inline P unit(P p){return p/abs(p);}

inline pair<P,P> norm(P p){return make_pair(p*P(0,1),p*P(0,-1));}

inline D dot(P x, P y){return real(conj(x)*y);}

inline D cross(P x, P y){return imag(conj(x)*y);}

//for line(segment)
inline int ccw(P a,P b,P c){
  b -= a;c -= a;
  if (cross(b,c)>EPS) return 1;   //counter clockwise
  if (cross(b,c)<-EPS) return -1; //clockwise
  if (dot(b, c)<-EPS) return 2;   //c--a--b on line
  if (abs(b)+EPS<abs(c)) return -2;   //a--b--c on line
  return 0;                       //on segment
}

inline P line_cp(L a,L b){
  return a.fs+(a.sc-a.fs)*cross(b.sc-b.fs,b.fs-a.fs)/cross(b.sc-b.fs,a.sc-a.fs);
}

//for polygon

//all vertex is already sorted.
inline D area(Poly p){
  if(p.sz<3)return 0;
  D res = cross(p[p.sz-1],p[0]);
  rep(i,p.sz-1)res += cross(p[i],p[i+1]);
  return res/2;
}

//vertexes are in the counter-clockwise order.
inline Poly convex_cut(Poly p,L l){
  Poly res;
  rep(i,p.sz){
    int nxt = (i+1)%p.sz;
    if(ccw(l.fs,l.sc,p[i]) != -1)res.pb(p[i]);
    if(ccw(l.fs,l.sc,p[i]) * ccw(l.fs,l.sc,p[nxt]) < 0){
      res.pb( line_cp(l, L(p[i],p[nxt]) ) );
    }
  }
  return res;
}

int main(){
  int n,d,V;
  while(scanf("%d%d%d",&n,&d,&V), n){
    D S = (D)V/d;
    Poly p(n);
    rep(i,n){
      int x,y; scanf("%d%d",&x,&y); p[i] = P(x,y);
    }

    D res = 0;
    rep(i,n){
      L b = L(p[i],p[(i+1)%n]);
      P n = unit(norm(b.sc-b.fs).fs);

      D left = 0, right = 1e4;
      rep(azu,100){
	D med = (left + right) / 2;
	L cut = L(b.sc+med*n,b.fs+med*n);
	Poly subp = convex_cut(p,cut);

	if(area(subp)<S)left = med;
	else right = med;
      }

      res = max(res, left);
    }

    printf("%.6lf\n",res);
  }
}

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

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef pair<ll, ll> pair_t;
using Graph = vector<vector<ll>>;

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
/***** define constant start *******/
const ll MOD = 1000000007;
const double PI = 3.1415926535897932;
const ll INF = 1 << 29;
/****** define constant end ********/
/****** define variable start ******/
ll n;
/******* define variable end *******/
ll solve() {
	cin >> n;
	ll sum = 0;
	ll ma;
	vector<ll> ans;
	for(ll i = 1; sum < n; i++){
		sum += i;
		if(sum >= n){
			ma = i;
		}
	}
	for(ll i = ma; i >= 1; i--){
		if(sum - i >= n){
			sum -= i;
		}else{
			ans.push_back(i);
		}
	}
	for(ll i = ans.size() - 1; i >= 0; i--){
		cout << ans[i] << endl;
	}

	return 0;
}
int main() {
	// clock_t start = clock();
	cout << std::fixed << std::setprecision(10);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	ll end_solve = solve();
	/*
	clock_t end = clock();
	const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC *
	1000.0; printf("time %lf[ms]\n", time);
	*/

	return (int)end_solve;
}


Measured memory_bytes: 384
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using static MyIO;


public class D
{
	public static void Main()
	{
		int N = GetInt();
		int K = GetInt();

		int[] numA = new int[N+1];
		long ans = 0;
		for(int b = 1; b <= N; b++)
		{
			int q = N / b;
			int r = N % b;
			numA[b] = q * Math.Max(0, b - K) + Math.Max(0, r - K + 1);
			if(K == 0)
				numA[b]--;
			ans += (long)numA[b];
		}

		Console.WriteLine(ans);
	}
}


public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt(){ return int.Parse(getArg()); }
	public static long GetLong(){ return long.Parse(getArg()); }
	public static double GetDouble(){ return double.Parse(getArg()); }
	public static string GetString(){ return getArg(); }
}





Measured memory_bytes: 11232
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

class Main {
	public static void main(String args[]) throws IOException {
		@SuppressWarnings("resource")
		Scanner cin = new Scanner(System.in);
		ArrayList<String> inLines = new ArrayList<String>();
		for (; cin.hasNext();) {
			inLines.add(cin.nextLine());
		}
		Solver solver = new Solver();
		solver.solve(inLines);
	}
}

class Solver {

	public void solve(ArrayList<String> inLines) {
		String[] strArr = inLines.get(0).split(" ");
		int A = Integer.parseInt(strArr[0]);
		int B = Integer.parseInt(strArr[1]);
		int C = Integer.parseInt(strArr[2]);
		int D = Integer.parseInt(strArr[3]);

		if (A * B > C * D)
			System.out.println((A * B));
		else
			System.out.println((C * D));
	}
}


Measured memory_bytes: 9684
using System;
using System.Linq;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var nm = Console.ReadLine().Split(' ');
            var n = long.Parse(nm[0]);
            var m = long.Parse(nm[1]);
            var a = Console.ReadLine().Split(' ');

            var sum = (from x in a select long.Parse(x)).Sum();
            var d = n - sum;

            Console.WriteLine(d >= 0 ? d : -1);
        }
    }
}

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

int main(){
  int d;
  int c[27];
  int s[400][27];
  int t[400];
  static int last[27];//最後の開催日

  cin >> d;
  rep(i, 26)cin >> c[i+1];
  rep(i, d){
    rep(j, 26){
      cin >> s[i+1][j+1];
    }
  }

  //各日トップになる問題を計算しておく
  int top[400];
  for(int i=1;i<=d;i++){
    int mx = -INF;
    int mxi;
    for(int j=1;j<=26;j++){
      int tmp=s[i][j]-25*c[j];
      if(tmp>mx){
        mx = tmp;
        mxi = j;
      }
    }
    top[i]=mxi;
  }
  
  rep(i, d)cout << top[i+1] << endl;
  return 0;
}


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

#define ll long long int
#define INF 1000000007

int getPrice( int x, int y ){
	return ( ( x - y ) * ( x - y ) );
}

int main(){
	int n;
	cin >> n;
	vector < int > v (n);
	int sm = 0;
	for( int i = 0; i < n; i++ ){
		cin >> v[i];
		sm += v[i];
	}
	int avg1 = sm/n;
	int avg2 = avg1 + 1;
	int cost1 = 0;
	int cost2 = 0;
	for( int i = 0; i < n; i++ ){
		cost1 += getPrice( v[i], avg1 );
		cost2 += getPrice( v[i], avg2 );
	}
	int ans = min( cost1, cost2 );
	cout << ans;
	return 0;
}

Measured memory_bytes: 3620
-- https://github.com/minoki/my-atcoder-solutions
{-# LANGUAGE BangPatterns #-}
import Data.Char (isSpace)
import Data.List (unfoldr)
import Control.Monad
import qualified Data.Vector.Unboxed as U
import qualified Data.ByteString.Char8 as BS
import qualified Data.ByteString.Builder as BSB
import Data.Bifunctor
import Control.Exception
import System.IO
import Data.Monoid

-- d <= 2 * k && x >= 0 && y >= 0 && (even (x + y) || odd k)
solveSmall :: Int -> Int -> Int -> [(Int,Int)]
solveSmall !k !x !y
  | assert (x >= 0 && y >= 0 && d <= 2 * k) False = undefined
  | d == 0 = []
  | d == k = [(x,y)]
  | odd (x + y) && d < k =
    let !x1 = -1
        !y1 = 1-k
    in (x1,y1) : map (bimap (+ x1) (+ y1)) (solveSmall k (x-x1) (y-y1))
  | odd (x + y) {- k < d < 2*k -} =
    let (x1,y1) | x >= k = (k,0)
                | y >= k = (0,k)
                | otherwise = (x,k-x) -- k < x + y && x < k && y < k
    in (x1,y1) : map (bimap (+ x1) (+ y1)) (solveSmall k (x-x1) (y-y1))
  | otherwise {- even (x + y) -} =
    if x >= y
    then let !x1 = (x + y) `quot` 2
             !y1 = x1 - k
         in [(x1,y1), (x,y)]
    else let !y1 = (x + y) `quot` 2
             !x1 = y1 - k
         in [(x1,y1), (x,y)]
  where d = abs x + abs y -- <= 2 * k

-- x >= 0 && y >= 0
solve :: Int -> Int -> Int -> [(Int,Int)]
solve !k !x !y
  | d < 2 * k = solveSmall k x y
  -- Now x + y >= 2 * k holds, which implies x >= k || y >= k
  | otherwise =
    let (q,r) = x `quotRem` k -- 0 <= r < k
        (q',r') = y `quotRem` k -- 0 <= r' < k
        -- abs (q*k - x) + abs (q'*k - y)
        --   = r + r' < 2*k-1
        (m,n) | 0 < r + r' && r + r' < k =
                -- 2*k <= x + y = (q+q')*k + r+r'
                -- k < 2*k - (r+r') <= (q+q')*k
                -- Therefore, 1 < q+q'
                if q > q'
                then (q-1,q')
                else (q,q'-1)
              | otherwise {- k <= r+r' -} = (q,q')
        !x1 = m*k
        !y1 = n*k
    in [(i*k,0) | i <- [1..m]] ++ [(x1,j*k) | j <- [1..n]] ++ map (bimap (+ x1) (+ y1)) (solveSmall k (x-x1) (y-y1))
  where d = abs x + abs y

main = do
  k <- readLn
  [x,y] <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
  if k >= 2 && even k && odd (x + y)
    then putStrLn "-1"
    else do let xs = solve k (abs x) (abs y)
                ys | x < 0 && y < 0 = map (bimap negate negate) xs
                   | x < 0 = map (first negate) xs
                   | y < 0 = map (second negate) xs
                   | otherwise = xs
            -- print $ check k ys
            print $ length ys
            -- forM_ ys $ \(x',y') -> putStrLn $ unwords [show x', show y']
            BSB.hPutBuilder stdout $ mconcat $ map (\(x',y') -> BSB.intDec x' <> BSB.char7 ' ' <> BSB.intDec y' <> BSB.char7 '\n') ys

check :: Int -> [(Int,Int)] -> Bool
check !k xs = and $ zipWith (\(x0,y0) (x1,y1) -> abs (x0-x1) + abs (y0-y1) == k) ((0,0) : xs) xs


Measured memory_bytes: 28924
#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
using namespace std;
const int maxn = 100000+10;
int main(){
	int n,x,mmax=0;
	int  b[maxn]={0};
	cin>>n;
	while(n!=0){
		cin>>x;
		b[x]++;
		if(b[x]>mmax)mmax=b[x];
		b[x-1]++;
		if(b[x-1]>mmax)mmax=b[x-1];
		b[x+1]++;
		if(b[x+1]>mmax)mmax=b[x+1];
		n--;
	}
	cout<<mmax<<endl;
	return 0;
}

Measured memory_bytes: 640
n = int(input())
heights = list(map(int, input().split()))
dp = [float('inf') for i in range(n)]
dp[0] = 0

for i in range(1, n):
    dp[i] = min(dp[i], dp[i - 1] + abs(heights[i] - heights[i - 1]))
    if i > 1:
        dp[i] = min(dp[i], dp[i - 2] + abs(heights[i] - heights[i - 2]))

print(dp[n - 1])


Measured memory_bytes: 13928
#include<bits/stdc++.h>
#define ll long long
#define vll vector<ll>
#define mll map<ll,ll>
#define sll set<ll>
#define fo(i,n) for(i=0;i<n;i++)
#define MOD 1000000007
using namespace std;

int main()
{
    ios::sync_with_stdio(false);

    

    ll n,i,j,k,t,a[200001];

    cin>>n;

    vll v(2*n+1,0);
    ll l=n,r=n+1,flag=0;

    fo(i,n)
    {
        cin>>a[i];
        if(flag==0)
        {
            v[l]=a[i];
            l--;
            flag=1;
        }
        else
        {
            v[r]=a[i];
            r++;
            flag=0;
        }
    }

    if(flag==1)
    {
        for(i=l+1;i<r;i++)
            cout<<v[i]<<" ";
        return 0;
    }

    for(i=r-1;i>l;i--)
        cout<<v[i]<<" ";

    return 0;
}


Measured memory_bytes: 6912
#include<iostream>

int main(){
    int N, D, X;
    std::cin >> N >> D >> X;
    int sum = 0;
    for(int i = 0; i < N; i++){
        int a;
        std::cin >> a;
        int tmp = 0;
        int day = 1;
        while(day <= D){
            tmp++;
            day += a;
        }
        sum += tmp;
    }
    std::cout << sum + X << std::endl;
    return 0;
}


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

using namespace std;

int main()
{
	int N,A,B;
	scanf("%d%d%d",&N,&A,&B);
	if ((B - A) % 2 == 1)
	{
		puts("Borys");
	}
	else
	{
		puts("Alice");
	}
} 

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

using namespace std;
typedef long long ll;

const ll MOD = 1e9 + 7;

int N;
unordered_set<int> visited;
map<int, vector<int>> edges;
map<int, vector<int>> subtree_sizes;

ll mod_exp(ll x, ll exp) {
    ll ans = 1;
    ll base = x % MOD;
    while (exp > 0) {
        if (exp % 2 == 1) {
            ans = (ans * base) % MOD;
        }
        base = (base * base) % MOD;
        exp /= 2;
    }
    return ans;
}

ll mod_inv_prime(ll x) {
    return mod_exp(x, MOD-2);
}

int dfs(int v) {
    // cout << v << endl;
    visited.insert(v);
    int total_size = 0;
    for (int ne : edges[v]) {
        // cout << "attempt visit " << ne << endl;
        if (!visited.count(ne)) { 
            int subtree_size = dfs(ne) + 1;
            // cout << "subtree size " << subtree_size << endl;
            if (subtree_size > 0) {
                subtree_sizes[v].push_back(subtree_size);
            }
            total_size += subtree_size;
        }
    }
    if (N - 1 - total_size > 0) {
        subtree_sizes[v].push_back(N-1-total_size);
    }
    return total_size;
}

int main() {
    cin >> N;
    for (int i = 0; i < N-1; i++) {
        int a, b;
        cin >> a >> b;
        edges[a-1].push_back(b-1);
        edges[b-1].push_back(a-1);
    }
    /*
    int root = 0;
    for (int i = 0; i < N; i++) {
        if (edges[i].size() == 1) {
            root = i;
            break;
        }
    }
    */

    dfs(0);

    /*
    for (int i = 0; i < N; i++) {
        printf("%d: ", i);
        for (int x : subtree_sizes[i])
            printf("%d ", x);
        printf("\n");
    }
    */

    ll ev = 0;
    ll two_inv = mod_inv_prime(2);
    /*
    vector<ll> two_inv_pow = {1};
    ll curr = 1;
    for (int i = 0; i < N; i++) {
        curr = (curr * mod_inv_prime) % MOD;
    }
    */

    for (int i = 0; i < N; i++) {
        if (subtree_sizes[i].size() < 2) continue;
        ll p_all_white = 1;
        for (int subtree_size : subtree_sizes[i]) {
            p_all_white = (p_all_white * mod_exp(two_inv, subtree_size)) % MOD;
        }
        ll p_one_black = 0;
        for (int subtree_size : subtree_sizes[i]) {
            ll p_t_white = mod_exp(two_inv, subtree_size);
            ll p_t_black = (1 - p_t_white + MOD) % MOD;
            ll prob = (p_all_white * ((p_t_black * mod_inv_prime(p_t_white)) % MOD)) % MOD;
            p_one_black = (p_one_black + prob) % MOD;
        }
        ll cond_prob = (1 - ((p_all_white + p_one_black) % MOD) + MOD) % MOD;
        ll total_prob = (two_inv * cond_prob) % MOD;
        ev = (ev + total_prob) % MOD;
    }

    cout << ev << endl;

}


Measured memory_bytes: 65608
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,a,n) for(int i=a;i<n;i++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INFL = 1e18;
const int INF = 1001001001; 
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;
const int mod =1000000007;
int main(){
    string s,t;cin>>s>>t;
    //vector<string> res;
    bool f =false;
    int able =-1;
    rep(i,s.length()){
        bool l =true;
            rep(j,t.length()){
                if(s.length()<j+i){
                    l=false;
                    break;
                }
                if(s[i+j]!=t[j]&&s[i+j]!='?')l=false;
            }
        //else l=false;
        if(l){
            f=true;
            able=max(i,able);
        }
    }
    if(!f){
        cout<<"UNRESTORABLE"<<endl;
        return 0;
    }
    rep(i,t.length())s[i+able]=t[i];

    rep(i,s.length()){
        if(s[i]=='?')s[i]='a';
    }

    cout<<s<<endl;
    }

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

int dp[1000][1000];

int main(void){
  int size, max;
  char c;
  while(cin >> size, size != 0){
    max = 0;
    for(int i = 0; i < size; i++) for(int j = 0; j < size; j++) dp[i][j] = 1;
    
    for(int i = 0; i < size; i++) for(int j = 0; j < size; j++){
      cin >> c;
      if(c == '*') dp[i][j] = 0;
    }
    for(int i = 1; i < size; i++) for(int j = 1; j < size; j++){
      if(dp[i][j] == 0) continue;
      dp[i][j] = min(dp[i-1][j], min(dp[i-1][j-1], dp[i][j-1])) + 1;
      if(max < dp[i][j]) max = dp[i][j];
    }
    cout << max << endl;
  }
  return 0;
}

Measured memory_bytes: 5064
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;

int s,n,t,p,m;
string w,ti;
int can[11000];
const int halfday = 720;
const int week = 10080;

int main(){
  while(cin >> s >> n >> t >> w >> ti >> p >> m,w!="None"){
    for(int i=0;i<week;i++)can[i] = false;

    int loop = (w == "All")?7:1;
    
    if(ti == "All"){
      for(int i=0;i<loop;i++){
	for(int j=0;j<2*halfday;j++)can[i*2*halfday+j] = true;
      }
    }else if(ti == "Day"){
      for(int i=0;i<loop;i++){
	for(int j=0;j<halfday;j++){
	  can[i*2*halfday + j + halfday/2] = true;
	}
      }
    }else{
      for(int i=0;i<loop;i++){
	for(int j=0;j<halfday/2;j++){
	  can[i*2*halfday + j] = true;
	  can[i*2*halfday + j + 3*halfday/2] = true;
	}
      }
    }

    int res = 0;
    for(int start = 0;start < week; start++){
      int now = start;
      int cnt = 0;
      for(int i=0;i<m;i++){
	/*
	bool f = true;
	for(int j=0;j<=s;j++){
	  if(!can[(now+j)%week]){
	    f = false;
	    break;
	  }
	}
	if(f)cnt++;
	*/
	if(can[now%week] && can[(now+s)%week])cnt++;
	now += t;
      }
      res = max(res,cnt);
    }
    printf("%.10lf\n",1-pow(1-1.0/p,n*res));
  }
}

Measured memory_bytes: 1308
#include <bits/stdc++.h>
using namespace std;
int main() {
    int A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;
    int k = max(X,Y);
    int ans = 2000000000;
    for(int ab = 0; ab <= k; ab++) {
        int a = max(0, X-ab);
        int b = max(0, Y-ab);
        ans = min(ans, a*A+b*B+2*ab*C);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef multimap<string,int>::iterator itr;
int n;
multimap<string,int>S;
main()
{
  cin>>n;
  for(int i=0;i<n;i++)
  {
    int c;string s;cin>>c>>s;
    if(c==0)
    {
      int x;cin>>x;
      S.insert(make_pair(s,x));
    }
    else if(c==1)
    {
      itr a=S.lower_bound(s),b=S.upper_bound(s);
      for(itr it=a;it!=b;it++)cout<<it->second<<endl;
    }
    else if(c==2)S.erase(s);
    else
    {
      string t;cin>>t;
      itr a=S.lower_bound(s),b=S.upper_bound(t);
      for(itr it=a;it!=b;it++)cout<<it->first<<" "<<it->second<<endl;
    }
  }
}



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

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

  int v[50];
  for (int i = 0; i < n; i++) {
    cin >> v[i];
  }
  sort(v, v + n);

  double ans = (v[0] + v[1]) / 2.0;

  for (int i = 2; i < n; i++) {
    ans = (ans + v[i]) / 2;
  }

  printf("%f\n", ans);

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  cin>>S;
  int A=0;
  for(int i=0;i<3;i++){
    if(S.at(i)==S.at(i+1)){
      A=1;
      break;
    }
  }
  if(A==0)cout<<"Good"<<endl;
  else cout<<"Bad"<<endl;
}
  

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int n;
    scanf("%d",&n);
    long long a[n][n],b[n][n],c[n][n],ans=0;
    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            scanf("%lld",&a[i][j]);
            b[i][j]=a[i][j];
            c[i][j]=1;
        }
    }
    for (int k=0; k<n; k++){
        for (int i=0; i<n; i++){
            for (int j=0; j<n; j++){
                if (b[i][j]>b[i][k]+b[k][j]){
                    b[i][j]=b[i][k]+b[k][j];
                }
            }
        }
    }
    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            if (a[i][j]!=b[i][j]){
                printf("-1\n");
                return 0;
            }
        }
    }
    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            for (int k=0; k<n; k++){
                if (i!=j && i!=k && j!=k){
                    if (a[i][j]==a[i][k]+a[k][j]){
                        c[i][j]=0;
                    }
                }
            }
        }
    }
    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            if (c[i][j]==1){
                ans+=a[i][j];
            }
        }
    }
    printf("%lld\n",ans/2);
    return 0;
}

Measured memory_bytes: 2304
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lll long long
#define llf __float128
#define lld long double
using namespace std;
const int NR= 2e5 + 20 ,oo = 1e5 + 10, MOD = 1e9 + 7 ;
const long double pi = 2*acos(0.0);


int ans [ NR ] , bits , bits_plus , bits_minus , val , put , puteri [ NR ] , val_minus, puteri_minus [ NR ] ;
string s ;

int pop_count ( int val )   {
    int i = 0 , cnt = 0 ;
    for ( i = 0 ; ( 1 << i ) <= val ; ++ i )    {
        if ( ( 1 << i ) & val )
            ++ cnt ;
    }
    return cnt ;
}

int dpm ( int val ) {
    if ( val == 0 ) return 0 ;
    if ( ans [ val ] ) {
        return ans [ val ] ;
    }
    ans [ val ] = 1 + dpm( val % pop_count( val ) ) ;
    return ans [ val ] ;
}


int main () {
    lll x , y , z , i , n ;
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0) ;
    cin >> n ;
    cin >> s ;
    for ( i = 0 ; i < s.size() ; ++ i ) {
        if ( s [ i ] == '1' )   {
            bits ++ ;
        }
    }


    for ( i = 1 ; i <= n ; ++ i )   {
        dpm ( i ) ;
    }

    bits_plus = bits + 1 ;
    puteri [ s.size() - 1 ] = 1 % bits_plus ;
    val = 0 ;
    for ( i = s.size() - 1 ; i >= 0 ; -- i )    {
        if( s [ i ] == '1' )    {
            val += puteri [ i ] ;
            val %= bits_plus ;
        }
        if ( i )
        puteri [ i - 1 ] = ( puteri [ i ] * 2 ) % bits_plus ;
    }

    if ( bits > 1 ) {
        bits_minus = bits - 1;
        puteri_minus[s.size() - 1] = 1 % bits_minus ;
        val_minus = 0;
        for (i = s.size() - 1; i >= 0; --i) {
            if (s[i] == '1') {
                val_minus += puteri_minus[i];
                val_minus %= bits_minus;
            }
            if (i)
                puteri_minus[i - 1] = (puteri_minus[i] * 2) % bits_minus;
        }
    }

    for (i = 0 ; i < s.size() ; ++ i) {
        if (s[i] == '0') {
            cout << ans [ ( val + puteri [ i ] ) % bits_plus ] + 1 << '\n' ;
        }   else    {
            if ( bits_minus < 1 )   { cout << "0\n" ; continue ; }
           // cout << '*'<< ( val_minus + puteri_minus [ i ] ) % bits_minus << '\n' ;
             cout << ans [ ( val_minus - puteri_minus [ i ] + bits_minus ) % bits_minus ] + 1 << '\n' ;
        }
    }

    return 0;
}


Measured memory_bytes: 6112