akhauriyash/Code-Regression huggingface dataset:
/* おまじない　*/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
typedef long long ll;
typedef long double ld;
using namespace std;
const ll MOD=pow(10,9)+7;
const ll INF=(1LL<<62);
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
void init(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
}

ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(b==0)return a;
    if(a%b==0)return b;
    return gcd(a%b,b);
}

template< typename Monoid >
class SegmentTree {
public:
  using F = function< Monoid(Monoid, Monoid) >;

  int sz;
  vector< Monoid > seg;

  const F f;
  const Monoid M1;

  SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz, M1);
  }

  void set(int k, const Monoid &x) {
    seg[k + sz] = x;
  }

  void build() {
    for(int k = sz - 1; k > 0; k--) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  void update(int k, const Monoid &x) {
    k += sz;
    seg[k] = x;
    while(k >>= 1) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  Monoid query(int a, int b) {
    Monoid L = M1, R = M1;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) L = f(L, seg[a++]);
      if(b & 1) R = f(seg[--b], R);
    }
    return f(L, R);
  }

  Monoid operator[](const int &k) const {
    return seg[k + sz];
  }

  template< typename C >
  int find_subtree(int a, const C &check, Monoid &M, bool type) {
    while(a < sz) {
      Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);
      if(check(nxt)) a = 2 * a + type;
      else M = nxt, a = 2 * a + 1 - type;
    }
    return a - sz;
  }


  template< typename C >
  int find_first(int a, const C &check) {
    Monoid L = M1;
    if(a <= 0) {
      if(check(f(L, seg[1]))) return find_subtree(1, check, L, false);
      return -1;
    }
    int b = sz;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) {
        Monoid nxt = f(L, seg[a]);
        if(check(nxt)) return find_subtree(a, check, L, false);
        L = nxt;
        ++a;
      }
    }
    return -1;
  }

  template< typename C >
  int find_last(int b, const C &check) {
    Monoid R = M1;
    if(b >= sz) {
      if(check(f(seg[1], R))) return find_subtree(1, check, R, true);
      return -1;
    }
    int a = sz;
    for(b += sz; a < b; a >>= 1, b >>= 1) {
      if(b & 1) {
        Monoid nxt = f(seg[--b], R);
        if(check(nxt)) return find_subtree(b, check, R, true);
        R = nxt;
      }
    }
    return -1;
  }
};

int main(){
    init();
    ll N;cin>>N;
    SegmentTree<ll>seg(N,[](ll a,ll b){return gcd(a,b);},0);
    for(int i=0;i<N;i++){
        ll a;cin>>a;
        seg.update(i,a);
    }
    ll ans=0;
    for(int i=0;i<N;i++){
        ans=max(ans,gcd(seg.query(0,i),seg.query(i+1,N)));
    }
    cout<<ans<<endl;
    
}

Measured memory_bytes: 2304
N, W = map(int, input().split())
MV = (10**3)*N+1
dp = [[0] + [10**18]*(MV-1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    w, v = map(int, input().split())
    for j in range(1, MV):
        dp[i][j] = min(dp[i-1][j], dp[i-1][max(0, j-v)]+w)
for i in range(MV):
    if dp[N][MV-i-1] <= W:
        print(MV-i-1)
        break
#print(dp[N][W])


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

using namespace std;

#define inf 1<<30
#define llong long long
#define usd unsigned
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define fn fill_n
typedef pair<int, int> P;
typedef struct data{
	int now;
	int cost;

	bool operator<(const data &ri) const{
		return cost < ri.cost;
	}
	bool operator>(const data &ri) const{
		return cost > ri.cost;
	}
}data;
int nw[9] = {0, 1, 0, -1, -1, 1, 1, -1, 0};
int nh[9] = {1, 0, -1, 0, 1, 1, -1, -1, 0};



int main(){
	int n, m, d;
	char area[100][100];
	int raw[100][100] = {};
	int column[100][100] = {};

	cin >> n >> m >> d;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> area[i][j];
		}
	}

	int ans = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(area[i][j] == '.'){
				if(j == 0) raw[i][j] = 1;
				else raw[i][j] = raw[i][j-1]+1;
				if(raw[i][j] >= d) ans++;
			}
		}
	}
	for(int i = 0; i < m; i++){
		for(int j = 0; j < n; j++){
			if(area[j][i] == '.'){
				if(j == 0) raw[j][i] = 1;
				else raw[j][i] = raw[j-1][i]+1;
				if(raw[j][i] >= d) ans++;
			}
		}
	}

	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 3180
package main

import (
	"fmt"
	"sort"
)

func main() {
	var N, A, B, C, D, E int
	fmt.Scan(&N, &A, &B, &C, &D, &E)
	p := []int{A, B, C, D, E}
	sort.Ints(p)
	x := p[0]
    fmt.Println((N-1)/x + 5)
}


Measured memory_bytes: 1836
#include<stdio.h>
int main(){
    int n;
    scanf("%d",&n);
    bool flag = false;
    while(n>0){
        int num = n%10;
        if(num==7){
            flag = true;
            break;
        }
        n/=10;
    }
    if(flag){
        printf("Yes\n");
    }else{
        printf("No\n");
    }

}


Measured memory_bytes: 1660
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

int n,m;
int sum;
long long f[100010];
long long w[110];
long long v[110];

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&w[i],&v[i]);
		sum+=v[i];
	}
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=sum;j>=v[i];j--)
		{
			f[j]=min(f[j],f[j-v[i]]+w[i]);
		}
	}
	for(int i=sum;i>=0;i--)
	{
		if(f[i]!=0 && f[i]<=m)
		{
			printf("%d",i);
			return 0;
		}
	}
	return 0;
} 


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MAX5 100010
int main()
{
    ll n,arr[MAX5];;
    cin>>n;
    for(ll i=0;i<n;i++)
        cin>>arr[i];
    sort(arr,arr+n);
    ll s=0;
    for(ll i=0;i<n-1;i++)
        s+=arr[i];
    if(arr[n-1]<s)
        cout<<"Yes"<<'\n';
    else
        cout<<"No"<<'\n';
return 0;
}

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

enum inf = 1L << 50;

void main() {
    int n, k;
    scan(n, k);
    auto h = readln.split.to!(int[]);

    auto dp = new long[](n + 1);

    foreach (i ; 1 .. n) {
        long t = inf;
        foreach (j ; max(0, i - k) .. i) {
            t = min(t, dp[j] + abs(h[i] - h[j]));
        }
        dp[i] = t;
    }

    writeln(dp[n-1]);
}







void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}


void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

Measured memory_bytes: 4260
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  int64_t a = 2;
  int64_t b = 1;
  int64_t c;
  
  if (N == 1) {
    cout << b;
  }else{
    for(int i = 1; i < N; i++) {
      c = a + b;
      a = b;
      b = c;
    }
    cout << c;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i = 0; i < n; ++i)
typedef long long ll;
// Welcome to my source code!

int main() {
    int n;
    cin >> n;
    int L[n];
    REP(i,n) cin >> L[i];
    sort(L, L+n);
    int ans = 0;
    REP(b,n)REP(a,b) {
        int ab = L[a]+L[b];
        int r = lower_bound(L, L+n, ab) - L;
        int l = b+1; // c = [l,r)
        ans += max(0,r-l);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
    int n,a,p_num,q_num,count = 0;
    cin >> n;
    vector<int>v(n);
    vector<int>p(n);
    vector<int>q(n);

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

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

    do{
        if(v == p){
            p_num = count;
        }
        if(v == q){
            q_num = count;
        }
        count++;
    }while(next_permutation(v.begin(),v.end()));

    cout << abs(p_num-q_num) << endl;


    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define maxn 1000100
using namespace std;
typedef long long ll;
ll n,k;
ll sans[maxn];
ll s[maxn];
ll chara[maxn];
ll lowbit(ll x)
{
    return x&(-x);
}
void upd(ll x,ll t)
{
    while(x<=n)
    {
        sans[x]+=t;
        x+=lowbit(x);
    }
}
ll sum(ll x)
{
    ll ans=0;
    while(x>0)
    {
        ans+=sans[x];
        x-=lowbit(x);
    }
    return ans;
}


int main()
{
    scanf("%I64d%I64d",&n,&k);
    ll a;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%I64d",&a);
        s[i]=s[i-1]+a-k;
        chara[cnt++]=s[i];
    }
    ll ans=0;
    sort(chara,chara+cnt);
    int siz=unique(chara,chara+cnt)-chara;
    ll t;
    for(int i=0;i<=n;i++)
    {
        t=lower_bound(chara,chara+siz,s[i])-chara+1;
        ans+=sum(t);
        upd(t,1);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 9984
n = int(input())
d = []
for i in range(n):
    _ = str(input())
    d.append(_)

print('AC x {}'.format(d.count('AC')))
print('WA x {}'.format(d.count('WA')))
print('TLE x {}'.format(d.count('TLE')))
print('RE x {}'.format(d.count('RE')))

Measured memory_bytes: 79176
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int H = sc.nextInt();
			int W = sc.nextInt();
			if(H == 0 && W ==0) {
				break;
			}
			for(int i = 0 ; i < H ; i++) {
				for(int j = 0 ; j < W ; j++) {
					if((i % 2 == 0 && j % 2 == 0) || (i % 2 == 1 && j % 2 == 1)) {
						System.out.print("#");
					} else {
						System.out.print(".");
					}
				}
				System.out.println();
			}
			System.out.println();
		}
	}
}

Measured memory_bytes: 35940
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using vl=vector<long long>;
using pii=pair<int,int>;
using pll=pair<long long,long long>;
#define ITR(i,c) for(auto i=begin(c);i!=end(c);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define REPW(i,n) for(i=0;i<(int)(n);++i)
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) (y<0||x<0||y>=h||x>=w)
#define dump(...)
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
#define INF (1001001001)
#define INFLL (1001001001001001001ll)
template<class T> ostream& operator << (ostream &os,const vector<T> &v) {
    ITR(i,v) os << *i << (i==end(v)-1 ? "" : " "); return os; }
template<class T> istream& operator >> (istream &is,vector<T> &v) {
    ITR(i,v) is >> * i; return is; }
template<class T> istream& operator >> (istream &is, pair<T,T> &p) {
        is >> p.first >> p.second; return is; }
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
//------------------------------------------------------------------------------
struct before_main_function {
    before_main_function() {
        #ifdef int
            #undef INF
            #define INF INFLL
            #define stoi stoll
        #endif
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int n;
    cin>>n;
    vi a(n);
    cin>>a;
    vector<int> vis(n,false);
    int cur=0;
    vis[cur]=true;
    int ans=0;
    while(1) {
        cur=a[cur]-1;
        ans++;
        if(cur==1) {
            cout<<ans<<endl;
            return 0;
        }
        if(vis[cur]) break;
        vis[cur]=true;
    }
    cout<<-1<<endl;
    return 0;
}


Measured memory_bytes: 1792
#include<stdio.h>

int a[20];

int main(){
  int n;
  for(;scanf("%d",&n)&&n;){
    for(int i=0;i<n;++i)scanf("%d",a+i);
    int mi=1e9;
    for(int b=0;b<1<<n;++b){
      int d=0;
      for(int i=0;i<n;++i)
        d+=b&1<<i?a[i]:-a[i];
      if(d<0)d=-d;
      if(mi>d)mi=d;
    }
    printf("%d\n",mi);
  }
}



Measured memory_bytes: 2660
def insertion_sort(A):
    n = len(A)
    print(*A)
    for i in range(1, n):
        item = A[i]
        cur_idx = i - 1
        while cur_idx >= 0 and A[cur_idx] > item:
            A[cur_idx], A[cur_idx + 1] = A[cur_idx + 1], A[cur_idx]
            cur_idx -= 1
        print(*A)


if __name__ == "__main__":
    N = int(input())
    A = [int(elem) for elem in input().split()]
    insertion_sort(A)



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

#define BR "\n"
#define SP " "
#define SHOW(x) for(int i = 0; i < x.size(); i++) { cout << x[i] << SP; } cout << BR;
#define SHOW2(x) for(int j = 0; j < x.size(); j++) { SHOW(x[j]); } cout << BR;

int main() {
  ll MOD = 1e9 + 7;
  ll N, K;
  cin >> N >> K;

  vector<ll> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  vector<ll> C0(N, 0);
  vector<ll> C1(N, 0);
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (A[i] > A[j]) {
        if (i < j) {
          C0[i]++;
        } else {
          C1[i]++;
        }
      }
    }
  }

  ll K0 = K * (K + 1) / 2 % MOD;
  ll K1 = K * (K - 1) / 2 % MOD;

  ll ans = 0;
  for (int i = 0; i < N; i++) {
    ans = (ans + C0[i] * K0) % MOD;
    ans = (ans + C1[i] * K1) % MOD;
  }

  cout << ans << BR;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int dp[3001][3001];
string s,t,ans;
int main()
{
    cin >> s >> t;
    for(int i=1; i<=s.size(); i++)
    {
        for(int j=1; j<=t.size(); j++)
        {
            if(s[i-1] == t[j-1]) dp[i][j] = max({dp[i-1][j-1] + 1,dp[i-1][j],dp[i][j-1]});
            else dp[i][j] = max({dp[i][j-1],dp[i-1][j],dp[i-1][j-1]});
        }
    }
    int x = s.size();
    int y = t.size();
    while(x && y)
    {
        int Maxx = max({dp[x-1][y-1],dp[x][y-1],dp[x-1][y]});
        if(Maxx == dp[x][y] - 1)
        {
            ans += s[x-1];
            x --;
            y --;
        }
        else
        if(Maxx == dp[x-1][y])
            x --;
        else
            y --;
    }
    reverse(ans.begin(),ans.end());
    cout << ans << endl;
}

Measured memory_bytes: 35456
//#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx2,tune=native") // Auto-Vectorisation

#include "bits/stdc++.h"
#include "chrono"
#include "random"
using namespace std;

/*
//large integers
#include <boost/multiprecision/cpp_int.hpp>
__int128 s128; // pollard rho
__uint128_t u128;

//policy based data structures
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace boost::multiprecision; 
using namespace __gnu_pbds;
*/

typedef long long int ll;
typedef long double ld;
typedef double db;
typedef pair<ll,ll> pll;
typedef unsigned long long u64;
typedef vector<ll> vl;
typedef vector<pll> vpl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef unordered_set<ll> usl;
typedef set<ll> sl;
typedef multiset<ll> mul;
typedef unordered_map<ll,ll> umll;
typedef map<ll,ll> mll;

#define int long long int
#define sz(a) (ll)a.size()
#define lt(a) (ll)a.length()
#define tc(x) ll x; cin>>x; while(x--)
#define f(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define bac(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define print(a)  for (auto x : a) cout << x << " "; cout << endl
#define mt make_tuple
#define eb emplace_back
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define endl '\n'
#define all(a) a.begin(),a.end()
#define Sort(x) sort(all((x)))
#define setbits(a) __builtin_popcountll(a)
#define ps(x,y) fixed<<setprecision(y)<<x;
#define hell cout<<"hello"<<'\n'
#define deb(x) cerr<<#x<<" = "<<x<<'\n'
#define F first
#define S second
#define teevra_gati ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //shuffle(all(v), rng);

const string alpha   =   "zabcdefghijklmnopqrstuvwxyz";
const ld PI          =   ld(3.14159265359);
const ll P           =   1e9 + 7; // 998244353; // 1e9 + 9 // 7340033 // 4294967296;
const ll Q           =   1e9 + 6; // 998244352; // 1e9 + 8 // 7340032;
const ll ninf        =   LONG_MIN;
const ll inf         =   8e18;
const ll M           =   2e3 + 5;
const ll N           =   2e5 + 5;

void solve(){
    ll n,q,sum=0;
    cin>>n;
    vl a(n);
    umll m;
    f(i,0,n){
        cin>>a[i];
        sum += a[i];
        m[a[i]]++;
    }
    cin>>q;
    f(i,0,q){
        ll b,c;
        cin>>b>>c;
        ll cnt = m[b];
        sum += cnt*(c-b);
        m[b]=0;
        m[c]+=cnt;
        cout<<sum<<endl;
    }

}
signed main(){
    teevra_gati
    
    solve();

    //cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
    return 0;
}

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

int main()
{
    int n;
    cin >> n;
    int d[n];
    for (int i = 0; i < n; i++)
        cin >> d[i];
    
    int ans = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = n-1; j > i; j--)
            ans += d[i] * d[j];
    }

    cout << ans << '\n';
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10000)
from collections import defaultdict, deque
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
Q = [inpl() for _ in range(M)]
# グループごとにトポロジカルソートをして、最後の方から遡って計算
 
tree = [[-1, 1]  for _ in range(N+1)] # [next, rank]
  
def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
 
adj = [[] for _ in range(N+1)]  
 
for l, r, d in Q:
    if find(l) != find(r):
        unite(l, r)
    adj[l].append([r, d])
    adj[r].append([l, -d])
 
 
G = set([find(n) for n in range(1, N+1)])
 
X = [-1 for _ in range(N+1)]
searched = [False for _ in range(N+1)]
res = True
 
for g in G:
    X[g] = 0
    Q = deque([g])
    searched[g] = True
    while Q:
        p = Q.popleft()
        for np, d in adj[p]:
            if searched[np]:
                if X[np] != X[p] + d:
                    Q = []
                    res = False
                    break
            else:
                X[np] = X[p] + d
                Q.append(np)
                searched[np] = True
    if not res:
        break
 
if res:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 167512
x,k,d=map(int,input().split())

x=abs(x)
t=x//d

if k<=t:
    print(x-k*d)
else:
    last=k-t
    if last%2==1:
        print(abs(x-(t+1)*d))
    else:
        print(abs(x-t*d))

Measured memory_bytes: 9184
let () = Scanf.scanf "%d %d\n" @@ fun n k ->
  let ps = Array.init n @@ fun _ -> Scanf.scanf "%d " @@ fun p -> p in
  let acc = Array.make (n + 1) 0 in
  for i = 0 to n - 1 do
    acc.(i + 1) <- ps.(i) + 1 + acc.(i)
  done;
  Printf.printf "%f\n" @@
  Array.fold_left max neg_infinity @@
  Array.init (n - k + 1) @@ fun i ->
    float_of_int (acc.(i + k) - acc.(i)) *. 0.5

Measured memory_bytes: 7936
def checkMus(i, j, grid):
    count = 0
    if i > 0:
        if j >0 and grid[i-1][j-1] == "#":
            count+= 1
        if grid[i-1][j] == "#":
            count+= 1
        if j < len(grid[i]) -1 and grid[i-1][j+1] == "#":
            count+= 1
    if j >0 and grid[i][j-1] == "#":
        count+= 1
    if j < len(grid[i]) -1 and grid[i][j+1] == "#":
        count+= 1
    if i < len(grid) -1:
        if j >0 and grid[i+1][j-1] == "#":
            count+= 1
        if grid[i+1][j] == "#":
            count+= 1
        if j < len(grid[i]) -1 and grid[i+1][j+1] == "#":
            count+= 1
    return count

h,w = map(int, input().split())
grid = [input() for i in range(h)]
for i in range(h):
    line = ""
    for j in range(w):
        if grid[i][j] == ".":
            line += str(checkMus(i, j, grid))
        else:
            line += grid[i][j]
    print(line)

Measured memory_bytes: 3192
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    int MAX = 1000000;
    vector<int> hamming(MAX+1, 0);
    hamming[1] = -1;
    for(int i=1; i<=MAX; ++i){
        if(hamming[i] == -1){
            if(i * 2 <= MAX)
                hamming[i*2] = -1;
            if(i * 3 <= MAX)
                hamming[i*3] = -1;
            if(i * 5 <= MAX)
                hamming[i*5] = -1;
            hamming[i] = hamming[i-1] + 1;
        }else{
            hamming[i] = hamming[i-1];
        }
    }

    for(;;){
        int m, n;
        cin >> m >> n;
        if(m == 0)
            return 0;

        cout << (hamming[n] - hamming[m-1]) << endl;
    }
}

Measured memory_bytes: 0
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define max(x,y)(x>y?x:y)
#define min(x,y)(x>y?y:x)
typedef long long int ll;
typedef unsigned long long int ull;
int asc_cmp(const void* X,const void* Y){int x=*(int*)X,y=*(int*)Y;if(x<y)return -1;else if(x==y)return 0;else return 1;}
int desc_cmp(const void* X,const void* Y){int x=*(int*)X,y=*(int*)Y;if(x<y)return 1;else if(x==y)return 0;else return -1;}

int main(){
    int s;scanf("%d",&s);
    int x=s;
    int flg[2000000]={};
    flg[s]=1;
    int cnt=1;
    while(1){
        if(x%2)x=3*x+1;
        else x=x/2;
        cnt++;
        if(flg[x])break;
        flg[x]=1;
    }
    printf("%d\n",cnt);
}

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

using namespace std;

#define int                  long long int

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



      int n, q;
      cin >> n >> q;

      map <int, vector < pair <int, int> > > indices;
      for (int i = 0; i < n; i++)
      {
            int s, t, x;
            cin >> s >> t >> x;
            indices[x].push_back({s, t});
      }

      map <int, int> Map, RMap;
      multiset <int> ms;

      for (int i = 0; i < q; i++)
      {
            int d;
            cin >> d;
            Map[d] = i;
            ms.emplace(d);
      }
      vector <int> ans(q, -1);
      for (auto it : indices)
      {
            for (auto p : it.second)
            {
                  int x = it.first;
                  int s = p.first;
                  int t = p.second;
                  int up = t - x - 1;
                  int lb = s - x - 1;
                  auto location = ms.upper_bound(lb);
                  vector <int> del;
                  while (location != ms.end())
                  {
                        if (*location > lb && *location <= up) del.push_back(*location);
                        else break;
                        ++location;
                  }
                  for (int d : del)
                  {
                        //cerr << d << " ans " << x << endl;
                        ans[ Map[d] ] = x;
                        ms.erase(ms.find(d));
                  }
            //      cerr << x << " " << s << " " << t << endl;
            }
      }
      for (auto it : ans) cout << it << endl;
}


Measured memory_bytes: 47748
N = int(input())
H = [int(i) for i in input().split()]
rem=0
cnt=0
for i in range(N-1):
    if H[i] >= H[i+1]:
        cnt+=1
    else:
        rem=max(rem,cnt)
        cnt=0
rem=max(rem,cnt)
print(rem)

Measured memory_bytes: 63984
#include<iostream>
#include<vector>
using namespace std;
#define yes(n) cout << ((n) ? "Yes" : "No") << endl
int main()
{
    int N;cin >> N;
    vector<int> v(N);
    for(int i = 0; i < N; i++) cin >> v[i];
    int ans = 0;
    for(int i = 0;i < N;i++)
    {
        for(int j = i + 1;j < N;j++)
        {
            ans += v[i]*v[j];
        }
    }
    cout << ans << endl;
}

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


signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n,m;
    cin>>n>>m;
    int x;
    for (int i = 0; i < m; ++i)
    {
        cin>>x;
        n-=x;
    }
    if(n<0)
        cout<<-1<<"\n";
    else
        cout<<n<<"\n";
    return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll GCD(ll x,ll y){
    if(y == 0) return x;
    else return GCD(y,x%y);
}

int main() {
    int n,a;
    cin >> n >> a;
    cout << n*n-a << endl;
}



Measured memory_bytes: 256
#include <cassert>
#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>
#include <numeric>
#include <iterator>
#include <unordered_map>
#include <array>
#include <map>
#include <cstring>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>
#include <ctgmath>
#include <set>
#include <queue>
#include <fstream>
#include <ostream>
#include <random>
#include <chrono>
using namespace std;

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int a, b;
	cin >> a >> b;
	cout << ((a * 3) + b )/ 2 << "\n";
}



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

using namespace std;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

typedef long long  ll;
#define endl '\n'




int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};


const int MOD = 1000000007;

//////////////////////////////////////////



int n;
int c1[26];
int c2[26];
vector<string> s;
void Input() {


    cin >> n;
}



void Solve() {


    map<string , long long> mp;

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

        string c;
        cin >> c;
        sort(c.begin(), c.end());

        mp[c]++;
    }

    long long ans = 0;

    for(auto it = mp.begin(); it != mp.end(); it++) {

        if(it->second >= 2) {

            ans += it->second * (it->second - 1) / 2;
        }
    }

    cout << ans << endl;


}

int main() {

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


  return 0;

}


Measured memory_bytes: 11264
#include <iostream>
#include <string>
#include <cstdio>

using namespace std;


int main() {

  int n;
  string str;
  string search;

  int count;
  string temp;


  getline(cin,search);

  cin >> n;

  getchar();

  count=0;

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

    getline(cin,str);

    for(int i=0;i<str.length();i++) {

      temp="";

      for(int j=0;j<search.length();j++) {

	temp+=str[(i+j)%str.length()];

      }

      if(temp==search) {

	count++;

	break;

      }

    }

  }

  cout << count << endl;

  return 0;

}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define ll long long
#define eps 1e-7
#define ull unsigned long long
#define inf 2e9+10
using namespace std;
inline ll read(){
    ll x=0;int f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int a,b;
int main(){
	a=read();b=read();
	if(a*b%2==0){
		printf("No\n");
	}
	else printf("Yes\n");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(var, begin, end) for (int var = (begin); var < (end); var++)
#define RFOR(var, begin, end) for (int var = (begin) - 1; var >= (end); var--)
#define REP(var, length) FOR(var, 0, length)
#define RREP(var, length) RFOR(var, length, 0)
#define SORT(vector) sort(vector.begin(), vector.end())

const ll MOD = 1e9 + 7;

void solve(istream& cin, ostream& cout) {
  int n, W;
  int w, v;
  cin >> n >> W;

  vector<vector<ll>> dp(n + 1, vector<ll>(W + 1, 0));
  REP(i, W + 1) {
    dp[0][i] = 0;
  }

  REP(i, n) {
    cin >> w >> v;
    REP(j, w) {
      dp[i + 1][j] = dp[i][j];
    }
    FOR(j, w, W + 1) {
      dp[i + 1][j] = max(dp[i][j], dp[i][j - w] + v);
    }
  }

  ll ans = -1;
  REP(i, W + 1) {
    ans = max(ans, dp[n][i]);
  }

  cout << ans << endl;
}

#ifndef TEST
int main() {
  solve(cin, cout);
}
#endif


Measured memory_bytes: 80256
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a,b=mi()
l=list(mi())
l=sorted(l)
ind=bisect.bisect_left(l,b)
print(a-ind)

Measured memory_bytes: 51616
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
 
int main()
{

ll N,A,B;
cin>>N>>A>>B;

ll ans=0;
ans= ((N/(A+B))*A+ min(A, N%(A+B)));
cout<<ans<<endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define PRECISION std::cout << std::fixed << std::setprecision(20);
using namespace std;

const ll inf = 1e17;
const ll N = 1e6+10;
const ll bits = 30;
const ll mod = 1e9+7;

ll power(ll x, ll n){

    if(n==0){
        return 1;
    }

    ll ans = power(x,n/2);
    ans*=ans;
    ans%=mod;

    if(n%2){
        ans*=x;
        ans%=mod;
    }
    return ans;
}

ll modInv(ll a){
    return power(a,mod-2);
}

ll fact[2*N];
  
// Driver code 
int main() 
{   FASTIO;

    ll x,y;

    cin>>x>>y;

    fact[0]=1;

    for(int i=1;i<2*N;i++){
        fact[i] = (i*fact[i-1])%mod;
    }

    bool done = true;

    ll b = 2*x-y;
    if(b%3!=0 || b<0){
        done = false;
    }else{
        b/=3;
    }

    ll a = 2*y-x;

    if(a%3!=0 || a<0){
        done = false;
    }else{
        a/=3;
    }

    // cout<<a<<" "<<b<<"\n";
    if(done){

        ll ans = (fact[a+b] * modInv( (fact[a] * fact[b])%mod ))%mod;
        cout<<ans<<"\n";
    }else{
        cout<<0<<"\n";
    }
} 

Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<double,double> pdd;
#define SQ(i) ((i)*(i))
#define MEM(a, b) memset(a, (b), sizeof(a))
#define SZ(i) int(i.size())
#define FOR(i, j, k, in) for (int i=j ; i<(k) ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=(k) ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define REP1(i,j) FOR(i, 1, j+1, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define ALL(_a) _a.begin(),_a.end()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define X first
#define Y second
#ifdef tmd
#define TIME(i) Timer i(#i)
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,deque<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
class Timer {
private:
    string scope_name;
    chrono::high_resolution_clock::time_point start_time;
public:
    Timer (string name) : scope_name(name) {
        start_time = chrono::high_resolution_clock::now();
    }
    ~Timer () {
        auto stop_time = chrono::high_resolution_clock::now();
        auto length = chrono::duration_cast<chrono::microseconds>(stop_time - start_time).count();
        double mlength = double(length) * 0.001;
        debug(scope_name, mlength);
    }
};
#else
#define TIME(i)
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
#endif

const ll MOD = 1000000007;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int iNF = 0x3f3f3f3f;
// const ll MAXN =

int n, k, s;
/********** Good Luck :) **********/
int main () {
    TIME(main);
    IOS();

    cin >> n >> k >> s;

    vector<int> ans;
    REP (i, k) {
        ans.emplace_back(s);
    }
    if (s == 1000000000) {
        REP (i, n-k) {
            ans.emplace_back(1);
        }
    } else {
        REP (i, n-k) {
            ans.emplace_back(1000000000);
        }
    }

    REP (i, SZ(ans)) {
        cout << ans[i] << " \n"[i==SZ(ans)-1];
    }

    return 0;
}


Measured memory_bytes: 1912
import std.stdio, std.conv, std.functional, std.string;
import std.algorithm, std.array, std.container, std.range, std.typecons;
import std.numeric, std.math, std.random;
import core.bitop;

string FMT_F = "%.10f";

static string[] s_rd;
T RD(T = long)() { while(!s_rd.length) s_rd = readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
string RDR()() { return readln.chomp; }
T[] ARR(T = long)(in string str, T fix = 0) { auto r = str.split.to!(T[]); r[] += fix; return r; }
size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

bool inside(T)(T x, T b, T e) { return x >= b && x < e; }
bool minimize(T)(ref T x, T y) { if (x > y) { x = y; return true; } else { return false; } }
bool maximize(T)(ref T x, T y) { if (x < y) { x = y; return true; } else { return false; } }

long mod = 10^^9 + 7;
void moda(ref long x, long y) { x = (x + y) % mod; }
void mods(ref long x, long y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(ref long x, long y) { x = (x * y) % mod; }

void main()
{	
	auto N = RD;
	auto A = RDR.ARR;

	long cnt;
	long cnt0;
	foreach (i; 0..N)
	{
		if (A[i] < 0)
			++cnt;
		else if (A[i] == 0)
			++cnt0;
	}
	A.sort!((long a, long b) => abs(a) < abs(b))();
	//debug writeln(A);

	long ans;
	if (cnt % 2 == 1)
		ans -= abs(A[0]);
	else
		ans += abs(A[0]);

	foreach (i; 1..N)
	{
		ans += abs(A[i]);
	}

	//debug writeln(ans);

	writeln(ans);
	stdout.flush();
	//debug readln();
}

Measured memory_bytes: 4392
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    String t = sc.next();
    char[] sp = s.toCharArray();
    char[] tp = t.toCharArray();
    Arrays.sort(sp);
    Arrays.sort(tp);
    s="";
    t="";
    for(int i=0;i<sp.length;i++) s+=sp[i];
    for(int i=tp.length-1;i>=0;i--) t+=tp[i];
    //System.out.println(s+" "+t);
    int ans= t.compareTo(s);
    if(ans>0) System.out.println("Yes");
    else System.out.println("No");
  }
}

Measured memory_bytes: 22868
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int n;
    cin>>n;
    vector<ll>a(n);
    for(ll &c:a)cin>>c;
    ll sum=0;
    for(int i = 0 ; i < n ; i++){
        for(int j = i+1 ; j < n ; j++){
            sum+=a[i]*a[j];
        }
    }
    cout<<fixed<<setprecision(0)<<sum;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define rep(i, a, n) for (ll i = (a); i < (n); i++)
#define debug(x) cerr << #x << ": " << x << endl;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

int main() {
    ll n, m;
    cin >> n >> m;
    ll left = -INF, right = INF;
    rep(i, 0, m) {
        ll l, r;
        cin >> l >> r;
        chmax(left, l);
        chmin(right, r);
    } 
    cout << max(0LL, right-left+1) << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int n, a[23]; vector<int>v;
void f(int k, int sum) {
	if (k == n)v.push_back(sum);
	else {
		f(k + 1, sum);
		f(k + 1, sum + a[k]);
	}
	return;
}
int main() {
	while (cin >> n, n) {
		v.clear();
		int sum = 0;
		for (int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; }
		f(0, 0);
		int ans = sum;
		for (size_t i = 0; i < v.size(); i++) {
			int v1 = v[i], v2 = sum - v[i];
			ans = min(ans, abs(v1 - v2));
		}
		cout << ans << endl;
	}
}


Measured memory_bytes: 6992
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <numeric>

using namespace std;
using ll = long long;
const ll mod =  1000000007;

#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP_FROM(i, j, n) for (ll i = (j); i < (n); ++i)
#define all(x) (x).begin(),(x).end()

ll power(ll base, ll exponent, ll module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ ll root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
ll inverse(ll x){ return power(x, mod - 2, mod);}
ll gcd(ll a, ll b) {if(a < b) gcd(b, a);ll r;while(r=a%b) {a=b;b=r;}return b;}
struct combination{ vector<ll> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } ll C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };

vector<vector<ll>> dp;

combination table(2 * 100000 + 50);

signed main() {
  ios::sync_with_stdio(false);
  vector<ll> a(3);
  cin >> a[0] >> a[1] >> a[2];
  ll ans = 1e9;
  cout << accumulate(all(a), 0ll) - *max_element(all(a)) << endl;

  return 0;
}


Measured memory_bytes: 3328
n, m = map(int, input().split())
l, r = [], []
for i in range(m):
    ll, rr = map(int, input().split())
    l.append(ll)
    r.append(rr)

a, b = max(l), min(r)
a = b-a
print(a+1 if a >= 0 else 0)


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

int main() {
	int a[9] = { 0 };
	

	for (int i = 0; i < 10; i++) {
		cin >> a[i];
	}
	sort(a, a + 10);

	cout << a[9] << endl;
	cout << a[8] << endl;
	cout << a[7] << endl;

	return 0;
}

Measured memory_bytes: 3104
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
vector<vector<vector<double>>> dp(300+1, vector<vector<double>>(300+1, vector<double>(300+1, -1.0)));
int n1, n2, n3;
int n;
double getexp(int i, int j, int k) {
    if (i==0 && j==0 && k==0) return 0.0;
    // if (i>n1 || j>n2 || k>n3) return 0.0;
    if (dp[i][j][k]>(-0.5)) return dp[i][j][k];
    int N = i+j+k;
    double temp = 1.0*n/N;
    dp[i][j][k] = temp;
    if (i) dp[i][j][k] += 1.0*i/N * getexp(i-1, j, k);
    if (j) dp[i][j][k] += 1.0*j/N * getexp(i+1, j-1, k);
    if (k) dp[i][j][k] += 1.0*k/N * getexp(i, j+1, k-1);
    // printf("returning dp[%d][%d][%d] = %.12lf\n", i, j, k, dp[i][j][k]);
    return dp[i][j][k];
}

int main() {
    scanf("%d", &n);
    vector<int> a(n);
    n1 = 0, n2 = 0, n3 = 0;
    for (int &i: a) {
        scanf("%d", &i);
        if (i==1) n1++;
        else if (i==2) n2++;
        else n3++;
    }
    // vector<vector<vector<double>>> dp(n1+1, vector<vector<double>>(n2+1, vector<double>(n3+1)));
    dp[0][0][0] = 0.0;
    // int i = 1, j = 0 , k = 0;
    // for (int i=0; i<=n1; i++) {
    //     for (int j=0; j<=n2; j++) {
    //         for (int k=0; k<=n3; k++) {
    //             int N = i+j+k;
    //             if (N==0) continue;
    //             double temp1 = 1.0*n/N;
    //             dp[i][j][k] = temp1;
    //             if (i) dp[i][j][k] += 1.0*i/N * dp[i-1][j][k];
    //             if (j) dp[i][j][k] += 1.0*j/N * dp[i+1][j-1][k];
    //             if (k) dp[i][j][k] += 1.0*k/N * dp[i][j+1][k-1];
    //         }
    //     }
    // }

    printf("%.15lf\n", getexp(n1, n2, n3));
}

Measured memory_bytes: 216960
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstdlib>
#define LL long long
#define LD long double
using namespace std;
const int NN=1000000 +117;
const int MM=1000000 +117;
int read(){
	int fl=1,x;char c;
	for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
	if(c=='-'){fl=-1;c=getchar();}
	for(x=0;c>='0'&&c<='9';c=getchar())
		x=(x<<3)+(x<<1)+c-'0';
	return x*fl;
}
void open(){
	freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
}
void close(){
	fclose(stdin);
	fclose(stdout);
}


LL n;
const int mod=1e9+7;
LL ksm(LL a,LL b){
	LL ret=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1)ret=ret*a%mod;
	return ret;
}
LL p[NN]={};
LL fact[2*NN]={};
LL rev[2*NN]={};
LL comp(int n,int m){
	return fact[n]*rev[m]%mod*rev[n-m]%mod;
}
LL prefact(int n){
	fact[0]=1;
	for(int i=1;i<=n;++i)fact[i]=fact[i-1]*i%mod;
	rev[n]=ksm(fact[n],mod-2);
	for(int i=n;i>=1;--i)
		rev[i-1]=rev[i]*i%mod;
}
int main(){
	//open();
	n=read();
	prefact(n);
	LL ans=0;
	LL di=ksm(3,n-1);
	di=ksm(di,mod-2);
	LL len=ksm(3*n,mod-2);
	for(int i=2;i<=n+1;++i){
		if(i==2)p[i]=di;
		else p[i]=(p[i-1]+p[i-2]*2)%mod;
		LL res=p[i]*comp(n,i-1)%mod;
		res=res*len%mod*fact[i-2]%mod*rev[i-1]%mod;
		ans=(ans+res)%mod;
	}
	printf("%lld\n",ans);
	close();
	return 0;
}

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

int main(){
  long long int N;
  vector<long long int> SPANS(5);
  cin >> N 
      >>SPANS.at(0)
      >>SPANS.at(1)
      >>SPANS.at(2)
      >>SPANS.at(3)
      >>SPANS.at(4);
  
  sort(SPANS.begin(), SPANS.end());
  long long int min = SPANS.at(0);
  
  long long int ans = 4;
  ans += (N / min)  ;
  if(N % min != 0){ans++;}
  
  cout << ans;
  return 0;
}


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

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>

#include <bits/stdc++.h>
#include <cmath>
#include <limits>

using namespace std;


int main(int argc, char* argv[]){
	string S;
	int K;

	cin >> S;
	cin >> K;
	
	int len = S.size();
	const string ALPH = "abcdefghijklmnopqrstuvwxyz";

	map<char, vector<int>> mp;

	for(int i=0; i<S.size(); i++){
		char c = S[i];
		if(mp.count(c)==0){
			vector<int> v;
			v.push_back(i);
			mp[c] = v;
		}
		else{
			mp[c].push_back(i);
		}
	}

	map<string, int> mpstr;

	int count = 0;
	for(int i=0; i<ALPH.size(); i++){
		if(mp.count(ALPH[i]) == 0) continue;
		count++;
		vector<int> v = mp[ALPH[i]];
		for(int j=0; j<v.size(); j++){
			int k = v[j];
			//S[k]から始まる部分文字列をmpstrに入れる。
			//ただし、最大でK個まで
			int tmp = 0;
			for(int s = 1; s < len - v[j] + 1; s++){
				string str = S.substr(k, s);
				mpstr.insert(make_pair(str, 1));
				tmp++;
				if(tmp == K) break;
			}

		}
		if(count == K) break; 
	}

	count = 0;
	char ans[6] = {0};
	for(auto itr = mpstr.begin(); itr != mpstr.end(); itr++){
		string key = itr->first;
		count++;
		if(count == K){
			strcpy(ans, key.c_str());
			break;
		}
	}
	printf("%s\n", ans);
	return 0;
}

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

#define int long long

typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}

bool e(multiset<int>&s,int k){
    auto it=s.find(k);
    if(it==s.end())return false;
    s.erase(it);
    return true;
}

signed main(){
    int N;
    multiset<int>s;
    cin>>N;
    rep(i,N){
        int a;cin>>a;s.insert(a);
    }

    bool ok=true;
    int d=*s.rbegin();
    int m=(d+1)/2;

    for(int i=d;i>m;i--){
        rep(j,2){
            ok&=e(s,i);
        }
    }

    if(d%2==0)ok&=e(s,m);
    else{
        ok&=e(s,m);ok&=e(s,m);
    }
    for(int i=d;i>m;i--)while(e(s,i));
    if(s.size())ok=false;
    cout<<(ok?"Possible":"Impossible")<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int player[5];

int main(void)
{	
	int a[2], Min;
	int check[4];
	int i, j;
	
	while (scanf("%d", &player[0]), player[0]){
		j = 0;
		for (i = 0; i < 4; i++){
			check[i] = 1;
		}
		check[player[0]] = -1;
		for (i = 1; i < 5; i++){
			scanf("%d", &player[i]);
			check[player[i]] = -1;
		}
		for (i = 1; i < 4; i++){
			check[0] *= check[i];
			if (check[i] == -1){
				a[j++] = i;
			}
		}
		if (check[0] == -1){
			for (i = 0; i < 5; i++){
				player[i] = 3;
			}
		}
		else if (check[3] == -1 && check[1] == -1){
			for (i = 0; i < 5; i++){
				if (player[i] == 3){
					player[i] = 1;
				}
				else {
					player[i] = 2;
				}
			}
		}
		else {
			if (a[0] > a[1]){
				Min = a[1];
			}
			else {
				Min = a[0];
			}
			for (i = 0; i < 5; i++){
				if (player[i] == Min){
					player[i] = 1;
				}
				else {
					player[i] = 2;
				}
			}
		}
		for (i = 0; i < 5; i++){
			printf("%d\n", player[i]);
		}
	}
	return (0);
}

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

int moid(int n)
{
	if (n==0||n==1)  return false;
	for (int i=2;i*i<=n;i++)
	{
		if (n%i==0)  return false;
	}
	return true;
}

int next_prime(int n)
{
	int pos=0;
	while (1)
	{
		if (moid(n+pos))  return n+pos;
		pos++;
	}
}

int main()
{
	int n;
	cin>>n;
	cout<<next_prime(n)<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <map>
#include <vector>

using namespace std;
int main()
{
    int n,m;
    cin >> n >> m;
    if(n == 1 && m == 0){
        cout << 0 << endl;
        return 0;
    }
    vector<int> v(n, -1);
    for(int i=0; i<m; i++){
        int a,b;
        cin >> a >> b;
        if(v[a-1] == -1) v[a-1] = b;
        else if(v[a-1] != b){
            cout << -1 << endl;
            return 0;
        }
    }
    if(v[0] == 0 && n > 1){
        cout << -1 << endl;
        return 0;
    }
    int ans = 0;
    for(int i=0; i<n; i++){
        if(v[i] != -1){
            ans += v[i]*pow(10, n-1-i);
        }
    }
    if(v[0] == -1) ans += pow(10, n-1);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define ll long long
#define pi 3.14159265358979
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;
const int INF = 1000100100;

int main(){
    ll n,m,p,q,t,min=INF;
    cin>>n>>m;
    p=n%2019;
    q=m%2019;  
    if(m-n>=673||p>=q){
        cout<<0;
    }else{
        for(int i=p;i<=q-1;i++){
            for(int j=i+1;j<=q;j++){
                t=(i*j)%2019;
                if(min>t){
                    min=t;
                }
            }
        }
        cout<<min;
    }
}

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

int main(){
  int n, m, a, te;
  while(true){
    vector<int> product;
    int ans = 0;
    cin>>n>>m; 
    if(!n&&!m)break;
    for(int i = 1; i <= n; i++){
      cin>>a;
      for(int z : product){
	if(a+z <= m && ans <= a+z){
	  ans = a+z;
	}
      }
      product.push_back(a);
    }
    cout<<(ans?to_string(ans):"NONE")<<endl;
  }
  return 0;
}



Measured memory_bytes: 3232