akhauriyash/Code-Regression huggingface dataset:
// -----------------------------------
// author   : MatsuTaku
// country  : Japan
// created  : 06/11/20 21:59:34
// -----------------------------------

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

template <typename T, T MOD>
class modular {
 private:
  T val_;

 public:
  constexpr modular() : val_(0) {}
  constexpr modular(T v) : val_(v%MOD) {}
  constexpr modular& operator=(T v) { val_ = v%MOD; return *this; }

  constexpr T val() const { return val_; }
  constexpr modular operator+(modular x) const { return (val() + x.val())%MOD; }
  constexpr modular operator+=(modular x) { return *this = *this + x; }
  constexpr modular operator++() { return *this += 1; }
  constexpr modular operator++(int) { modular c = *this; ++(*this); return c; }
  constexpr modular operator-(modular x) const { return (val() + MOD - x.val())%MOD; }
  constexpr modular operator-=(modular x) { return *this = *this - x; }
  constexpr modular operator--() { return *this -= 1; }
  constexpr modular operator--(int) { modular c = *this; --(*this); return c; }
  constexpr modular operator*(modular x) const { return (val() * x.val())%MOD; }
  constexpr modular operator*=(modular x) { return *this = *this * x; }
  friend constexpr modular pow(modular x, T p) {
    modular t = 1;
    modular u = x;
    while (p) {
      if (p & 1)
        t *= u;
      u *= u;
      p >>= 1;
    }
    return t;
  }
  constexpr modular operator/(modular x) const { return *this * pow(modular{x}, MOD-2); }
  constexpr modular operator/=(modular x) { return *this = *this / x; }

  constexpr bool operator==(modular x) const { return val() == x.val(); }
  constexpr bool operator!=(modular x) const { return val() != x.val(); }
  constexpr bool operator<(modular x) const { return val() < x.val(); };
  constexpr bool operator<=(modular x) const { return val() <= x.val(); };
  constexpr bool operator>(modular x) const { return val() > x.val(); };
  constexpr bool operator>=(modular x) const { return val() >= x.val(); };

  friend std::ostream& operator<<(std::ostream& os, const modular& x) {
    return os << x.val();
  }
  friend std::istream& operator>>(std::istream& is, modular& x) {
    return is >> x.val_;
  }

};

constexpr unsigned long long MOD = 1e9+7;
using mint = modular<unsigned long long, MOD>;
constexpr int MAX = 7e5;

mint fact_[MAX+1];
mint ifact_[MAX+1];
void init() {
  fact_[0] = 1;
  for (size_t i = 1; i <= MAX; ++i) {
    fact_[i] = fact_[i-1] * i;
  }
  ifact_[MAX] = mint(1)/fact_[MAX];
  for (int i = MAX-1; i >= 0; i--) {
    ifact_[i] = ifact_[i+1] * (i+1);
  }
}

mint cmb(int p, int q) {
  return fact_[p] * ifact_[q] * ifact_[p-q];
}

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

  int x,y; cin>>x>>y;
  mint ans;
  if ((x+y)%3!=0 or 2*x < y or 2*y < x or (2*x-y)%3!=0 or (2*y-x)%3!=0) {
    ans = 0;
  } else {
    init();
    ans = cmb((x+y)/3, (2*x-y)/3);
  }
  cout << ans << endl;

  return 0;
}


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

int main(){
    int n;
    cin >> n;
    long long int A[n];
    for(int i = 0; i < n; i++){
        cin >> A[i];
    }
    sort(A,A+n);
    cout << A[n-1] - A[0] << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iterator>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <numeric>
#include <iomanip>
#include <limits>

using namespace std;

int main(){

    double ans=0;
    int n,k;
    cin>>n>>k;

    vector<int> h;

    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        h.push_back(a);
    }

    for(int i=0;i<n;i++){
        if(h[i]>=k){
            ans++;
        }
    }


    
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 892
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <stack>
#include <functional>
#include <queue>
#include <cmath>
#include <set>
#include <map>

#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define Sort(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define vi vector<int>
#define INF (int)1e933
#define INFL 1e18
#define MOD 1e9+7
#define pb push_back
#define MP make_pair
typedef long long int ll;
typedef std::pair<int,int> pii;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int temp[3]={1,5,10};

using namespace std;

int main() {
    int n,m;
    vector<pair<int,int>> v;
    cin>>n;
    rep(i,0,n){
        int h,m;
        cin>>h>>m;
        v.pb(make_pair(h,m));
    }
    cin>>m;
    rep(i,0,m){
        int h,m;
        cin>>h>>m;
        v.pb(make_pair(h,m));
    }
    Sort(v);
    v.erase(unique(v.begin(),v.end()),v.end());
    rep(i,0,v.size()){
        if(i)cout<<" ";
        printf("%d:%02d",v[i].fi,v[i].se);
    }
    cout<<endl;
    return 0;
}



Measured memory_bytes: 3256
#include<bits/stdc++.h>
using namespace std;
#define NL            "\n"
#define _SAD()        ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
#define SZ(s)         s.size()
#define SRT(x,y)      sort(x,x+y)
#define REV(a,b)      reverse(a,a+b)
#define VSRT(x)       sort(x.begin(),x.end())
#define VREV(x)       reverse(x.begin(),x.end())
int main()
{
    _SAD()
    int a,b,c,x,cnt=0;
    cin>>a>>b>>c>>x;
    for(int i=0;i<=a;i++)
    {
        for(int j=0;j<=b;j++)
        {
            for(int k=0;k<=c;k++)
            {
                if(((500*i)+(100*j)+(50*k))==x)
                {
                    cnt++;
                }
            }
        }
    }
    cout<<cnt<<NL;
    return 0;
}


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


int main(){
  long long a,b,c;
  cin >> a >> b >> c;
  long long d = c-a-b;
  if(d > 0 && 4*a*b < d*d){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main {
	public static void main (String args[]) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int max = 0;
		int total = 0;
		for(int i=0;i<a;i++)
		{
			int input = sc.nextInt();
			if(input > max)
				max = input;
			total += input;
		}
		total = total - max + max/2;
		System.out.print(total);
		
	}
}


Measured memory_bytes: 22868
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <map>
#include <math.h>
#define ll long long

using namespace std;

int main() {
    int N,K;
    cin>>N>>K;
    
    map<ll,int> counts;
    
    for(int i=1;i<=N;i++) {
        int x;
        cin>>x;
        counts[x]++;
    }
    
    vector<int> uniq_counts;
    for(pair<ll,int> x : counts) {
        uniq_counts.push_back(x.second);
    }
    sort(uniq_counts.begin(),uniq_counts.end(),greater<int>());
    
    if (uniq_counts.size() > K)
        uniq_counts.resize(K);
    
    int ct=0;
    for(int x : uniq_counts)
        ct+=x;
    
    cout << N-ct << endl;
    
    
}

Measured memory_bytes: 13944
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
typedef long long ll;
typedef pair<int,int> P;
using vi=vector<long long>;
using vvi=vector<vector<long long>>;
using vc=vector<char>;
using vvc=vector<vector<char>>;
const int inf=1000000009;
void chmin(auto &a,auto b){if(b<a)a=b;}
void chmax(auto &a,auto b){if(a<b)a=b;}

int main(){
  string s;cin>>s;
  int n=s.size();
  bool b=true;
  rep(i,n){
    if(i%2==0&&s[i]=='L'){
      b=false;
      break;
    }
    if(i%2==1&&s[i]=='R'){
      b=false;
      break;
    }
  }
  if(b)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(int i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<ll,ll> Pi;
const int INF=(ll)(1LL<<30)-1;
const double INFd=100000000000.0;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int mdx[4]={0,1,0,-1},mdy[4]={-1,0,1,0};


template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int n;
int p[810];
int d[810];
vector<Pi> graph[810];
int delete_node[810];
int dist[810];
int main(){
	while(1){
		int ans=0;
		cin>>n;
		if(n==0)break;
		REP(i,810)graph[i].clear();
		REP(i,810)delete_node[i]=0;
		for(int i=2;i<=n;i++)cin>>p[i];
		for(int i=2;i<=n;i++)cin>>d[i];
		for(int i=2;i<=n;i++){
			graph[i].push_back(Pi(p[i],d[i]));
			graph[p[i]].push_back(Pi(i,d[i]));
		}
		for(int i=1;i<=n;i++){
			if(graph[i].size()==1){
				ans+=graph[i][0].second;
				delete_node[i]=1;
			}
		}
		for(int i=2;i<=n;i++){
			if(delete_node[i]!=1&&delete_node[p[i]]!=1){
				ans+=(3*d[i]);
			}
		}
		int t1=0;
		for(int i=1;i<n;i++){
			if(delete_node[i])continue;
			REP(k,810)dist[k]=-1;
			dist[i]=0;
			int tdis=0;
			queue<int> q1;
			q1.push(i);
			while(q1.size()){
				int tt1=q1.front();q1.pop();
				for(int k=0;k<graph[tt1].size();k++){
					if(delete_node[graph[tt1][k].first])continue;
					if(dist[graph[tt1][k].first]!=-1)continue;
					dist[graph[tt1][k].first]=dist[tt1]+graph[tt1][k].second;
					q1.push(graph[tt1][k].first);
					tdis=max(tdis,dist[graph[tt1][k].first]);
				}
			}
			t1=max(t1,tdis);
		}
		cout<<ans-t1<<endl;
	}
	return 0;
}


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

#define f first 
#define s second 
#define pb push_back               
#define mp make_pair 

using namespace std;                    

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

const int N = (int)1e5 + 123, mod = (int)1e9 + 7;

int n, m, was[N], cnt[N], ans;
int main(){    
	cin >> n >> m;
	was[0] = 1;
	for(int i = 0; i < n; i++)
		cnt[i] = 1;
	for(int i = 0; i < m; i++){
		int x, y;
		cin >> x >> y;
		--x;
		--y;
		if(was[x])
			was[y] = 1;
		cnt[x]--;
		cnt[y]++;
		if(cnt[x] == 0)
			was[x] = 0;
	}
	for(int i = 0; i < n; i++)
		if(was[i])
			ans++;
	cout << ans;
	return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include <vector>
#include<map>
using namespace std;

int main() {
	int k,a,b,i,y;
	cin >> k >> a >> b;
	for (i = a;i <= b;i++) {
		if (i % k == 0) {
			cout << "OK" << endl;
			goto y;
		}
	}
		cout << "NG" << endl;
	y:
		return 0;
}

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

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

  string S;
  cin >> S;

  int ans = 0;
  char prev = '*';
  for(auto c: S){
    if(c != prev){
      prev = c;
      ans++;
    }
  }
  cout << ans << endl;
}


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

#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
#define map unordered_map
#define set unordered_set
#define pll pair<ll, ll>
#define vll vector<ll>

using namespace std;

const ll MOD = 1000000007;
const ll INF = (1LL << 60);

int main() {
  // std::cout << std::fixed << std::setprecision(10);
  ll K;
  scanf("%lld", &K);

  string str;
  cin >> str;

  if (str.length() <= K) {
    cout << str << endl;
  } else {
    cout << str.substr(0, K) + "..." << endl;
  }
}


Measured memory_bytes: 3696
/*
sleep..sleep....sleep
*/
#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int,int > pp;
typedef long long ll;
 
#define sz(x) (int)x.size() 
int const N=3e5+10,oo=1e9;
ll const OO=2e18;
double const eps=1e-8,PI=acos(-1);
int mod=oo+7;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int a,b,k;
    cin>>a>>b>>k;
    vector<int > v;
    for(int i=1;i<=min(a,b);i++){
        if(a%i==0&&b%i==0)v.push_back(i);
        
/*        if(k==0){
            cout<<i<<endl;
            return 0;
        }*/
    }
    reverse(v.begin(),v.end());
    cout<<v[k-1]<<endl;
    return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner scan=new Scanner(System.in);
		int a[][]=new int[101][101];
		int i,j;
		
		int r=scan.nextInt(); int c=scan.nextInt();
		
		//初期化
		for(i=0;i<=r;i++){
			for(j=0;j<=c;j++){
				a[i][j]=0;
			}
		}
		
		//読み込みと計算
		for(i=0;i<r;i++){
			for(j=0;j<c;j++){
				a[i][j]=scan.nextInt();
				a[i][c]+=a[i][j];
				a[r][j]+=a[i][j];
			}
			a[r][c]+=a[i][c];
		}
		
		//表示
		for(i=0;i<=r;i++){
			for(j=0;j<c;j++){
				System.out.printf("%d ",a[i][j]);
			}
			System.out.println(a[i][c]);
		}
		
	}
}


Measured memory_bytes: 59340
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MM 1000000000
#define MOD MM+7
#define MAX 10000
#define MAP 110
#define Pair pair<int,int>

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int main(){
    int N; cin >> N;
    int h[N];
    int dp[N];
    for(int i = 0; i < N; i++){
        cin >> h[i];
    }
    dp[0] = 0; dp[1] = abs(h[1] - h[0]);
    for(int i = 2; i < N; i++){
        dp[i] = min(dp[i-2] + abs(h[i]-h[i-2]),
                dp[i-1] + abs(h[i]-h[i-1]));
    }
    cout << dp[N-1] << endl;
}


Measured memory_bytes: 1024
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc *bufio.Scanner

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc = bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	n := nextInt()

	fmt.Println(n * n * n)
}


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

int main() {
  int n, m, l;
  cin >> n >> m >> l;
  vector< vector<int> > a(n, vector<int>(m));
  vector< vector<int> > b(m, vector<int>(l));
  rep(i, n) {
    rep(j, m) {
      cin >> a.at(i).at(j);
    }
  }
  rep(i, m) {
    rep(j, l) {
      cin >> b.at(i).at(j);
    }
  }
  vector< vector<long long> > c(n, vector<long long>(l));
  rep(i, n) {
    rep(j, l) {
      long long sum = 0;
      rep(k, m) {
        sum += a.at(i).at(k) * b.at(k).at(j);
      }
      c.at(i).at(j) = sum;
    }
  }
  rep(i, n) {
    rep(j, l) {
      cout << c.at(i).at(j);
      if (j == l - 1) {
        cout << endl;
      }
      else {
        cout << " ";
      }
    }
  }
}



Measured memory_bytes: 3256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define pb push_back
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef complex<ld> com;
constexpr int inf = 1000000010;
constexpr ll INF = 1000000000000000010;
constexpr ld eps = 1e-12;
constexpr ld pi = 3.141592653589793238;
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }

class unionfind {
	vector<int> par;
	vector<int> sz;
public:
	unionfind(int n) {
		par = vector<int>(n);
		for (int i = 0; i < n; i++) par[i] = i;
		sz = vector<int>(n, 1);
	}
	int find(int x) {
		if (par[x] == x) return x;
		else return par[x] = find(par[x]);
	}
	int si(int x) { return sz[find(x)]; }
	bool same(int x, int y) { return find(x) == find(y); }
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		if (sz[x] < sz[y]) {
			par[x] = y;
			sz[y] += sz[x];
		}
		else {
			par[y] = x;
			sz[x] += sz[y];
		}
	}
};

vector<int> shrink(vector<int> vec) {
	int vecsize = vec.size();
	vector<int> tmpvec = vec;
	sort(tmpvec.begin(), tmpvec.end());
	tmpvec.erase(unique(tmpvec.begin(), tmpvec.end()), tmpvec.end());
	vector<int> res(vecsize);
	for (int i = 0; i < vecsize; i++) res[i] = lower_bound(tmpvec.begin(), tmpvec.end(), vec[i]) - tmpvec.begin();
	return res;
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);

	int n;
	cin >> n;
	vector<int> a(n), b(n);
	int suma = 0, sumb = 0;
	rep(i, n) {
		cin >> a[i];
		suma ^= a[i];
	}
	rep(i, n) {
		cin >> b[i];
		sumb ^= b[i];
	}
	vector<int> c = a, d = b;
	c.pb(suma); d.pb(sumb);
	sort(all(c)); sort(all(d));
	if (c != d) {
		cout << "-1\n";
		return 0;
	}
	a.pb(suma); b.pb(sumb);
	a = shrink(a); b = shrink(b);
	unionfind uni(100010);
	int ans = n;
	rep(i, n) {
		if (a[i] == b[i]) ans--;
		else uni.unite(a[i], b[i]);
	}
	uni.unite(a[n], b[n]);
	set<int> st;
	rep(i, n + 1) if (i == n || a[i] != b[i]) st.insert(uni.find(a[i]));
	cout << max(0, ans - 1 + (int)st.size()) << '\n';
}

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

int main(){
  string s;
  cin >> s;
  int n = s.size();
  vector<int> ans(n,0);
  for(int i=0; i<n; ++i){
    if(s[i] == 'L') continue;
    int odd = 0, even = 0;
    bool frag = true;
    while(i<n && s[i] == 'R'){
      if(frag){
        ++odd;
        frag = false;
      }else{
        ++even;
        frag = true;
      }
      ++i;
    }
    ans[i] += (frag ? odd:even);
    ans[i-1] += (frag ? even:odd);
  }
  for(int i=n-1; i>=0; --i){
    if(s[i] == 'R') continue;
    int odd = 0, even = 0;
    bool frag = true;
    while(i>=0 && s[i] == 'L'){
      if(frag){
        ++odd;
        frag = false;
      }else{
        ++even;
        frag = true;
      }
      --i;
    }
    ans[i] += (frag ? odd:even);
    ans[i+1] += (frag ? even:odd);
  }
  for(int i=0; i<n; ++i){
    if(i != n-1) printf("%d ",ans[i]);
    else printf("%d\n",ans[i]);
  }
}

Measured memory_bytes: 3944
#AtCoder Beginner Contestが始まってから早数十年。コンテストは 1 回目から順に ABC001,ABC002, と名付けられてきましたが、
#999 回目のコンテスト ABC999 を終え、これからのコンテストの名前をどうするかという問題が生じました。
#そこで、1000 回目から 1998 回目のコンテストを順に ABD001,ABD002,...,ABD999 と名付けることとなりました。1 以上1998 以下の整数
#N が与えられるので、N 回目のコンテストの名前の最初の3文字を出力してください。

N = int(input())

if N < 1000:
    print('ABC')
else:
    print('ABD')
    

Measured memory_bytes: 9144
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
#include <functional>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define REP(i, n) for (int i = 1; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
using namespace std;
using ll = long long;
constexpr int inf = 1000000000;
constexpr ll INF = 1000000000000000000;

int main() {
    ll N;
    cin >> N;
    if (N & 1) {
        cout << 0 << "\n";
        return 0;
    }
    N /= 2;
    ll ans = 0;
    while (N) {
        ans += N / 5;
        N /= 5;
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 3512
// abc131_b
#include <bits/stdc++.h>
using namespace std;
int main(void){
  int N, X;
  cin >> N >> X;
  int L[N];
  for(int i = 0; i < N; i++){
    cin >> L[i];
  }
  int count = 0;
  int D = 0;
  if(X >= D){
    count++;
  }
  for(int i = 0; i < N; i++){
    D += L[i];
    if(X >= D){
      count++;
    }
  }
  cout << count << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll, ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define ppi pair<pii,int>
#define pip pair<int,pii>
#define pdd pair<double, double>
#define f first
#define s second
#define MOD 1000000007
#define mkp make_pair
#define M_PI 3.14159265358979323846
#define FOR(i,l,r) for (int i=l;i<=r;i++)
#define LOR(i,l,r) for (ll i=l;i<=r;i++)
#define FORD(i,r,l) for (int i=r;i>=l;i--)
#define LORD(i,r,l) for (ll i=r;i>=l;i--)
#define INF 1000000000
#define CL(x) memset(x,0,sizeof(x))
#define DBG(x) cout << #x << " : " << x << '\n'
#define ALL(x) x.begin(), x.end()
#define SZ(x) x.size()
#define UI(x) (int)(x-'A')
#define LI(x) (int)(x-'a')
typedef long long ll;

#define MXN 100005
int N;
ll A[MXN];
ll ans;

struct
{
    void init(int _N)
    {
        N = _N;
        build(1,N,1);
    }
    void build(int l, int r, int id)
    {
        if(l==r)
        {
            st[id] = A[l];
            return;
        }
        int m = (l+r)/2;
        build(l,m,id*2);
        build(m+1,r,id*2+1);
        up(id);
    }
    void up(int id)
    {
        st[id] = max( st[id*2], st[id*2+1] );
    }
    ll que(int l, int r, int L, int R, int id=1)
    {
        if( l>R || r<L )return 0;
        if( l>=L && r<=R )return st[id];
        int m = (l+r)/2;
        return max( que(l,m,L,R,id*2), que(m+1,r,L,R,id*2+1) );
    }
    int N;
    ll st[MXN*4];
}segt;

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

    cin>>N;
    FOR(i,1,N)cin>>A[i];
    segt.init(N);

    FOR(i,1,N)
    {
        ll Ai = A[i];
        ll l1,l2,r1,r2;
        ll ls1,ls2,rs1,rs2;

        //find first pos right > Ai
        int l = i, r = N+1;
        while(l+1<r)
        {
            int m = (l+r)/2;
            if( segt.que(1,N,i,m)==Ai )l=m;
            else r=m;
        }
        r1 = l;
        rs1 = r1-i+1;

        if( r1==N )rs2=0;
        else if( r1==N-1 )rs2=1;
        else if( A[r1+2]>Ai )rs2=1;
        else
        {
            l = r1+2, r = N+1;
            while(l+1<r)
            {
                int m = (l+r)/2;
                if( segt.que(1,N,r1+2,m)<=Ai )l=m;
                else r=m;
            }
            r2 = l;
            rs2 = r2-r1;
        }

        l = 0, r = i;
        while(l+1<r)
        {
            int m = (l+r)/2;
            if( segt.que(1,N,m,i)==Ai )r=m;
            else l=m;
        }
        l1 = r;
        ls1 = i-l1+1;

        if( l1==1 )ls2=0;
        else if( l1==2 )ls2=1;
        else if( A[l1-2]>Ai )ls2=1;
        else
        {
            l = 0, r = l1-2;
            while(l+1<r)
            {
                int m = (l+r)/2;
                if( segt.que(1,N,m,l1-2)<=Ai )r=m;
                else l=m;
            }
            l2 = r;
            ls2 = l1-l2;
        }

        ans+=Ai*( rs2*ls1 );
        ans+=Ai*( ls2*rs1 );

        /*
        cout<<i<<" : \n";
        DBG(ls1);
        DBG(ls2);
        DBG(rs1);
        DBG(rs2);
        */
    }

    cout<<ans<<'\n';

    return 0;
}


Measured memory_bytes: 3072
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string.h>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <math.h>
#include <algorithm>
#include <numeric>

using namespace std;

// マクロ&定数 ============================================================
typedef unsigned int uint;
typedef long long ll;
//typedef pair<int, int> P;

typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<bool> vbool;
typedef vector<string> vstring;
typedef vector<char> vchar;

typedef vector<pair<int, int>> vpint;
typedef vector<pair<ll, ll>> vpll;
typedef vector<pair<double, double>> vpdouble;

typedef vector<vector<int>> vvint;
typedef vector<vector<ll>> vvll;
typedef vector<vector<double>> vvdouble;
typedef vector<vector<bool>> vvbool;

typedef vector<vector<string>> vvstring;

const int c_YET = -1;
const int INF = 1e9 + 1;
const ll LLINF = 1e17 + 1;
const int DX[9] = { 0,0,1,-1, 1, 1, -1, -1, 0 }; // 4;４近傍
const int DY[9] = { 1,-1,0,0, 1, -1, 1, -1, 0 }; // 8:８近傍 9:(0,0)を含む
const ll MOD = 1e9 + 7; //10^9 + 7
const ll MAX = 1e9;
const double PI = 3.14159265358979323846264338327950288;
//========================================================================




int main() {

	//==================================
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(30);
	//==================================

	int X, Y;
	cin >> X >> Y;

	int ans = 0;
	if (X == 3)
	{
		ans += 1;
	}
	else if (X == 2)
	{
		ans += 2;
	}
	else if (X == 1)
	{
		ans += 3;
	}


	if (Y == 3)
	{
		ans += 1;
	}
	else if (Y == 2)
	{
		ans += 2;
	}
	else if (Y == 1)
	{
		ans += 3;
	}

	if (X * Y == 1)
	{
		ans += 4;
	}

	cout << ans * 100000 << endl;






}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll hash[1000010] = { 0 };
 
int gcdt(int a, int b)
{
	if (a < b)
	{
		int term = b;
		b = a;
		a = term;
	}
	if (b == 0) return a;
	else return gcdt(b, a % b);
}
int gcd(int a, int b, int c)
{
	int ab = gcdt(a, b);
		return gcdt(ab, c);
}
int main()
{
	ios::sync_with_stdio(false);
	ll n;
	cin >> n;
	ll sum = 0;
	for(int a=1;a<=n;a++)
		for(int b=1;b<=n;b++)
			for (int c = 1; c <= n; c++)
			{
				sum += gcd(a, b, c);
			}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 3652
r, c = [int(_) for _ in input().split()]
A = [[int(_) for _ in input().split()] for _ in range(r)]

C = [0 for _ in range(c)]
for X in A:
    for j, a in enumerate(X):
        C[j] += a

for X in A + [C]:
    print(" ".join([str(a) for a in X] + [str(sum(X))]))



Measured memory_bytes: 5688
#include <iostream>
#include <vector>
using namespace std;
int main(void){
    int N, M;
    int tmp_a, tmp_b;
    cin >> N >> M;
    vector<int> vec(N, 0);
    for(int i = 0; i < M; i++)
    {
        cin >> tmp_a >> tmp_b;
        vec[tmp_a - 1]++;
        vec[tmp_b - 1]++;
    }
    for(int i = 0; i < N; i++)
    {
        cout << vec[i] << endl;
    }
  
    //return 0;
}

Measured memory_bytes: 256
used = [[False for i in range(13)] for i in range(4)]
mark = "SHCD"
dic = {"S": 0, "H": 1, "C": 2, "D": 3}

n = int(input())
for i in range(n):
    li = input().split()
    m = li[0]
    k = int(li[1])

    used[dic[m]][k - 1] = True

for i in range(4):
    for j in range(13):
        if (not used[i][j]):
            print("{0} {1}".format(mark[i], j+1))


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

using namespace std;

const int N = 2020;

char   a[N][N];
int  sum[N][N];
int sum2[N][N];

int n , m;

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

    for(int i = 1 ; i <= n ; i ++){
            scanf("%s" , a[i] + 1);
    }
    for(int i = 0 ; i <= n+1 ; i ++){
        a[i][0] = a[i][m+1] = '#';
    }
    for(int i = 0 ; i <= m+1 ; i ++){
        a[n+1][i] = a[0][i] = '#';
    }

    for(int i = 1 ; i <= n ; i ++){
            for(int j = 1 ; j <= m ; j ++){
                    if(a[i][j] == '#')sum[i][j] = 0;
                    else sum[i][j] = sum[i][j-1] + 1;
            }

            for(int j = m-1 ; j >= 1 ; j --){
                    if(a[i][j] == '#')continue;
                    sum[i][j] =  max(sum[i][j+1] , sum[i][j]);
            }
    }

    for(int j = 1 ; j <= m ; j ++){
            for(int i = 1 ; i <= n ; i ++){
                    if(a[i][j] == '#')sum2[i][j] = 0;
                    else sum2[i][j] = sum2[i-1][j] + 1;
            }

            for(int i = n-1 ; i >= 1 ; i --){
                    if(a[i][j] == '#')continue;
                    sum2[i][j] = max(sum2[i+1][j] , sum2[i][j]);
            }
    }
    int ans = 0;
    for(int i = 1 ; i <= n ; i ++){
            for(int j = 1 ; j <= m ; j ++){
                    ans = max(ans , sum[i][j] + sum2[i][j] - 1);
            }
    }
    printf("%d\n" , ans);

    return 0;
}


Measured memory_bytes: 36096
#include <stdio.h>

int main(){
    int a,b;
    scanf("%d %d", &a,&b);
    if(a>b){
     printf("a > b\n");   
    }
    else if(a<b){
    printf("a < b\n");
    }
    else{
    printf("a == b\n");   
    }

}



Measured memory_bytes: 2600
N, M = gets.split.map(&:to_i)
S = gets.chomp
ANS = []
pos = N

loop do
  break if pos == 0
  k_ = M.downto(1).find do |k|
    pos - k >= 0 && S[pos - k] == '0'
  end
  if k_.nil?
    puts -1
    exit
  end
  ANS << k_
  pos = pos - k_ >= 0 ? pos - k_ : 0
end
puts ANS.reverse * ' '


Measured memory_bytes: 6184
#include <iostream>
#include <algorithm>
using namespace std;
int main(void) {
	int N, R[200001];
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> R[i];
	}
	int max = R[N - 1];
	int out = R[1] - R[0];
	for (int i = N-2; i >= 0; i--) {
		if (max - R[i] > out) {
			out = max - R[i];
		}
		if (R[i] > max) {
			max = R[i];
		}
	}
	cout << out << endl;
	return 0;
}


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

namespace CSharpPractice
{
	class Program
	{
		static void Main(string[] args)
		{
			string s = Console.ReadLine();
			for (int i = 0; i < s.Length; i++)
			{
				Console.Write(s[s.Length - i -1]);
			}
			Console.WriteLine();
		}
	}
}

Measured memory_bytes: 5256
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}

int main(){
  int w,a,b;
  cin >> w >> a >> b;
  
  if(b >= a && b <= a+w){
    cout << 0;
    return 0;
  }
  if(b+w >= a && b+w <= a+w){
    cout << 0;
    return 0;
  }
  
  if(a > b+w){
    cout << a - (b + w);
    return 0;
  }
  if(b > a+w){
    cout << b - (a + w);
    return 0;
  }
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define ll long long
using namespace std;
int main()
{
    int n;
    cin >> n;
    map<pair<int, int>,int> mp;

    for (int i = 1; i <= n; i++)
    {
        int num = i;
        int r = 10;
        int a, b;
        a = num % r;
        while(num/r){
            num /= r;
        }
        b = num;
        mp[{b, a}]++;
    }

    int cnt = 0;
    for (int i = 1; i <= 9; i++){
        for (int j = 1; j <= 9; j++){
            cnt += mp[{i, j}] * mp[{j, i}];
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
using System;

namespace ALDS1_1_A
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var a = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            Print(a);
            for (int i = 1; i < n; i++)
            {
                int key = a[i], j = i - 1;
                while (j >= 0 && a[j] > key)
                {
                    a[j + 1] = a[j];
                    j--;
                }
                a[j + 1] = key;
                Print(a);
            }
        }

        static void Print(int[] array)
        {
            for (int i = 0; i < array.Length; i++)
            {
                Console.Write(array[i]);
                if (i < array.Length - 1) Console.Write(' ');
            }
            Console.WriteLine();
        }
    }
}

Measured memory_bytes: 9208
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int prime[n+1];
        for(int i=0;i<=n;i++)
            prime[i]=1;
            prime[0]=0;
            prime[1]=0;
        for(int i=2;i*i<=n;i++)
             if(prime[i]==1)
        {
            for(int j=2;j*i<=n;j++)
            prime[i*j]=0;
        }
        int c=0;
        for(int i=0;i<=n;i++)
        {
            if(prime[i]==1)
                c++;
        }
        printf("%d\n",c);
    }

}

Measured memory_bytes: 7044
#include <stdio.h>
int main(void)
{
  int x, y;
  int g1=0, g2=0, g3=0;
  int * const p[13]={ NULL, &g1, &g3, &g1, &g2, &g1, &g2, &g1, &g1, &g2, &g1, &g2, &g1};
  scanf("%d %d", &x, &y);
  ++*p[x];
  ++*p[y];
  if(g1==2 || g2==2 || g3==2){
    printf("Yes\n");
  } else {
    printf("No\n");
  }
  return 0;
}


Measured memory_bytes: 128
#include <cstdio>
#include <iostream>
#include <algorithm> 
#include <cmath>
using namespace std;
int a[200005];
#define ll long long
int main()
{
	ll n,sum1,min,sum,i;
	while(cin>>n)
	{
		min=0;
		sum=0;
		for(i=0;i<n;i++)
		{
			cin>>a[i];
			min+=fabs(a[i]);
			sum+=a[i];
		}
		sum1=0;
		for(i=n-1;i>0;i--)
		{
			sum1+=a[i];
			if(fabs(2*sum1-sum)<min)
			min=fabs(2*sum1-sum);
		}
		cout<<min<<endl;
	}	
	return 0;
}


Measured memory_bytes: 1024
N = gets.to_i
P = gets.split.map(&:to_f)

#N = 2999
#P = N.times.map{0.5}

dp = Array.new(N, 0.0)
dp[0] = 1
N.times do |i|
  i.downto(0) do |j|
    next if j > N/2
    if j + 1 <= N/2
      dp[j + 1] = (1 - P[i]) * dp[j] + dp[j + 1]
    end
    dp[j] = P[i] * dp[j]
  end
end
p dp.inject(:+)

Measured memory_bytes: 2172
N = int(input())
ret = 0
def func(s):
    if(int(s) > N):
        return 0
    if(all(s.count(c) > 0 for c in '753')):
        ret = 1
    else:
        ret = 0
    for c in '753':
        ret += func(s+c)
    return ret
    
print(func('0'))

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int n , k , i ;
    cin>>n>>k;
    int arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+n);
    int sum = 0;
    for(int i=0;i<k;i++)
    {
        sum+=arr[i];
    }
    cout<<sum<<endl;
}


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

int main(){
    int a,b;
    cin >> a >> b;

    vector<string> s(2);
    string a_s = to_string(a);
    string b_s = to_string(b);

    rep(i,a) s.at(0) += b_s;
    rep(i,b) s.at(1) += a_s;

    sort(s.begin(),s.end());
    cout << s.at(0) << endl;
}


Measured memory_bytes: 256
{-# LANGUAGE BangPatterns #-}

import Data.Bits
import Data.List
import Data.IntMap.Strict (IntMap)
import qualified Data.IntMap.Strict as IntMap
import qualified Data.ByteString.Char8 as BS
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import Control.Monad
import Control.Applicative
import Data.Maybe
import Data.Tuple
import Data.Ord
import Data.Coerce

gen :: Int -> [Int] -> Int -> Int -> (Int,Bool)
gen 0 [] till acc
  | acc <= till = (1,True)
  | otherwise   = (0,False)
gen n xs till !acc = foldr count out cands 0
  where
    count !k cont !left = if hasMore then
                            cont (left + now)
                          else
                            (left + now, False)
      where
        (!now,hasMore) = gen (n-1) (xs \\ [k]) till (10*acc + k)
    out !left = (left, True)
    cands = if n == length xs then xs else [3,5,7]
  
cNum :: Int -> Int
cNum !till = foldr count out [3,4..9] 0
  where
    count !n cont !left = if hasMore then
                            cont (left + now)
                          else
                            left + now
      where
        (!now, hasMore) = gen n [3,5,7] till 0
    out = id

main :: IO ()
main = getLine >>= print . cNum . read 


Measured memory_bytes: 1020
#include <bits/stdc++.h>
#define pb push_back
#define tam 500
#define offset 320000
#define se second
#define fi first
#define pitem item*
#define forr(i,p,n) for(int i=p;i<n;i++)
using namespace std;
typedef long long ll;
const ll MOD=1000000007 ;
ll mult(ll a,ll b, ll p=MOD){return ((a%p)*(b%p))%p;}
ll add(ll a, ll b, ll p=MOD){return (a%p + b%p)%p;}
typedef pair<int,int> ii;
typedef vector<vector<int> > vvi;
typedef  double lld;
int peso[tam][tam];
int dist[tam][tam];
int main()
{
    forr(i,0,tam)
        forr(j,0,tam)
        dist[i][j]=peso[i][j]=1e9;
    int n,m;
    cin>>n>>m;
    int iz,der,pes;
    forr(i,0,m)
    {
        cin>>iz>>der>>pes;
        peso[iz][der]=pes;
        peso[der][iz]=pes;
        dist[iz][der]=pes;
        dist[der][iz]=pes;
    }
    forr(i,1,n+1)
        dist[i][i]=1;
    forr(k,1,n+1)
    {
        forr(i,1,n+1)
        {
            forr(j,1,n+1)
            {
                if (dist[i][k]+dist[k][j]<dist[i][j])
                {
                    dist[i][j]=dist[i][k]+dist[k][j];
                }
            }
        }
    }
    int c=0;
    forr(i,1,n+1)
        forr(j,1,n+1)
            if (dist[i][j]<peso[i][j]&& peso[i][j]!=1e9)
            c++;
        
    cout<<c/2<<endl;
}

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

int main(void) {
  string s;
  cin >> s;
  if (s == "RRR") {
    cout << 3 << endl;
  } else if (s == "SSS") {
    cout << 0 << endl;
  } else if (s == "SRR" || s == "RRS") {
    cout << 2 << endl;
  } else {
    cout << 1 << endl;
  }
  return 0;
}

Measured memory_bytes: 3592
fn solve() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let order_times: Vec<u32> = (0..5).map(|_| sc.read::<u32>()).collect();
    let mut res: Vec<u32> = order_times.iter().map(|&x| (10 - (x % 10)) % 10).collect();
    res.sort();
    let wait = res[0..4].iter().fold(0, |sum, a| sum + a);
    let ans = order_times.iter().fold(0, |sum, a| sum + a) + wait;
    println!("{}", ans);
}

fn main() {
    std::thread::Builder::new()
        .stack_size(64 * 1024 * 1024) // 64MB
        .spawn(|| solve())
        .unwrap()
        .join()
        .unwrap();
}

//snippet from kenkoooo
pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn read_line(&mut self) -> String {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b'\n' || b == b'\r')
            .take_while(|&b| b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 8572
import math
from functools import reduce
from collections import deque
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**7)
# sys.stdin.readline

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999
MOD = 10**9+7

n = int(input())
A = [-INF] + get_nums_l()
edges = [ [] for _ in range(n+1) ]
for line in map(lambda s: s.strip(), sys.stdin.readlines()):
    u,v = map(int, line.split())
    edges[u].append(v)
    edges[v].append(u)

def dfs(dp, u, p=None):

    # log(u)
    # log(dp)

    # dpの中でA[u]以上の値が入っている最小のindex
    i = bisect_left(dp, A[u])

    old = dp[i]
    dp[i] = A[u]

    # 有効値(INF以外)が入っている最大のindex
    ans[u] = bisect_left(dp, INF) - 1

    for v in edges[u]:
        if v == p:
            continue
        dfs(dp, v, u)

    # 巻き戻し
    dp[i] = old

# ans[i] = ノード1からノードiへの経路中の最長増加部分列長
ans = [0] * (n+1)

# dp[i] = 最長増加部分列長がiの場合の末尾ノード値の最小
dp = [INF] * (n+1)
dp[0] = -INF
dfs(dp, 1, None)

for i in range(1, n+1):
    print(ans[i])


Measured memory_bytes: 358572
#include <algorithm>
#include <climits>
#include <iomanip>
#include <iostream>
#include <queue>
#include <vector>

struct Book
{
  int price;
  std::vector<int> powers;
};

struct Entry
{
  int price;
  std::vector<int> powers;
  int index;
};

int solve(int n, int m, int x, const std::vector<Book>& books)
{
  int result = INT_MAX;

  std::queue<Entry> queue;
  for (int i = 0; i < n; ++i) {
    queue.push(Entry{0, std::vector<int>(m), i});
  }

  while (!queue.empty()) {
    auto e = queue.front();
    queue.pop();

    const auto& book = books[e.index];
    e.price += book.price;
    if (e.price >= result) continue;

    int min = x;
    for (int i = 0; i < m; ++i) {
      e.powers[i] += book.powers[i];
      if (e.powers[i] < min) min = e.powers[i];
    }
    if (min >= x) {
      result = std::min(e.price, result);
    } else {
      for (int j = e.index + 1; j < n; ++j) {
        queue.push(Entry{e.price, e.powers, j});
      }
    }
  }

  return result == INT_MAX ? -1 : result;
}

int main()
{
  int n, m, x;
  std::cin >> n >> m >> x;

  std::vector<Book> books(n);
  for (auto& b : books) {
    std::cin >> b.price;
    b.powers.resize(m);
    for (auto& p : b.powers) {
      std::cin >> p;
    }
  }

  std::cout << std::setprecision(20);
  std::cout << solve(n, m, x, books) << std::endl;
}


Measured memory_bytes: 3692
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

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

	ll n;
	cin >> n;
	vll a(n);
	REP(i, n) cin >> a[i];
	VSORT(a);
	ll p = a[n - 1], dif = 1e15, mid = (a[n - 1] + 1) / 2, id = 0;
	REP(i, n){
		if(abs(a[i] - mid < dif)){
			id = i;
			dif = abs(a[i] - mid);
		}
	}
	cout << p << " " << a[id] << endl;
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

const int maxN = 1000010;
const int maxM = 30010;
const int inf = 1000000009;

int a[20];
int vis[20];
int b[20];
int ans = inf;
int n = 5;
void dfs(int k)
{
	if(k>n)
	{
		int tm = 0;
		for(int i=1;i<=5;i++)
		{
			//cout<<b[i]<<endl;
			if(i<5)
			{
				int x = b[i];
				int p = x/10;
				if(x%10 != 0)
					tm += (p+1)*10;
				else
					tm += x;
			}
		}
		tm += b[n];
		ans = min(ans,tm);
		return;
	}
	for(int i=1;i<=5;i++)
	{
		if(vis[i] != 1)
		{
			b[k] = a[i];
			vis[i] = 1;
			dfs(k+1);
			vis[i] = 0;
		}
	}
}
int main()
{
	int n = 5;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	dfs(1);
	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
/*==============================================*\
Codeforces ID:    mdshihab
                                                  |
Name:     Md. Shihabul Minhaz                     |
Study:      CSE, JKKNIU                           |
Address:  Trishal, Mymensingh, Bangladesh         |
                                                  |
 mail:   mdshihabul20171@gmail.com                |
 FB  :   fb.com/mdshihabul.minhaz.7               |
 github: Shihabulminhaz                           |
stopstalk :  mdshihab                             |
                                                  |
@uthor   Md. Shihabul Minhaz (shihab)             |
\*===============================================*/


#include<bits/stdc++.h>
using namespace std;
#define fi(a) scanf("%d",&a);
#define fli(a) scanf("%ld",&a);
#define fll(a) scanf("%lld",&a);
#define pi(a) printf("%d\n",a);
#define ppi(i,a) printf("Case %d: %d\n",i,a);
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
void FI()
{
#ifndef ONLINE_JUDGE
    freopen("C:\\Users\\SHIHAB\\Desktop\\input.in","r",stdin);
#endif // ONLINE_JUDGE
}

int main()
{
    fast
   // FI(); /// skip this line for compile
    int n,a,b,cnt=1,cnt_b=0;
    string s;
    cin >> n >> a >> b;
    cin >> s;
    for(int i=0;i<n;i++){
        if(s[i]=='c') cout << "No\n";
        else if(a+b>=cnt){
       //     cout << cnt << endl;
            if(s[i]=='a'){ cout << "Yes\n"; cnt++;}
            else if(s[i]=='b' && cnt_b<b){cout << "Yes\n"; cnt++; cnt_b++;}
            else cout << "No\n";
        }
        else cout << "No\n";
    }
    return 0;
}



Measured memory_bytes: 3708
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	sc := NewScanner()

	s := sc.ReadInt()
	w := sc.ReadInt()

	if w >= s {
		fmt.Println("unsafe")
	} else {
		fmt.Println("safe")
	}
}

// util
// *   math/simple

func Abs(x int) int {
	if x >= 0 {
		return x
	}
	return -x
}

func Min(values ...int) int {
	if len(values) == 0 {
		panic("no values")
	}
	min := values[0]
	for _, v := range values {
		if v < min {
			min = v
		}
	}
	return min
}

func Max(values ...int) int {
	if len(values) == 0 {
		panic("no values")
	}
	max := values[0]
	for _, v := range values {
		if v > max {
			max = v
		}
	}
	return max
}

func Pow(base int, exponent uint) int {
	answer := 1
	for i := uint(0); i < exponent; i++ {
		answer *= base
	}
	return answer
}

// *   io

type Scanner struct {
	bufScanner *bufio.Scanner
}

func NewScanner() *Scanner {
	bufSc := bufio.NewScanner(os.Stdin)
	bufSc.Split(bufio.ScanWords)
	bufSc.Buffer(nil, 100000000)
	return &Scanner{bufSc}
}

func (sc *Scanner) ReadString() string {
	bufSc := sc.bufScanner
	bufSc.Scan()
	return bufSc.Text()
}

func (sc *Scanner) ReadInt() int {
	bufSc := sc.bufScanner
	bufSc.Scan()
	text := bufSc.Text()

	num, err := strconv.Atoi(text)
	if err != nil {
		panic(err)
	}
	return num
}


Measured memory_bytes: 1756
import sys
input = lambda: sys.stdin.readline().rstrip() 
import math

def resolve():
    N = int(input())
    xy = [list(map(int, input().split())) for _ in range(N)]

    ans = []
    def dfs(d, perm):
        if d==N:
            dist = 0
            for i in range(N-1):
                dist += ((xy[perm[i+1]][0]-xy[perm[i]][0])**2+(xy[perm[i+1]][1]-xy[perm[i]][1])**2)**0.5
            ans.append(dist)
        else:
            for i in range(N):
                if i not in perm:
                    dfs(d+1, perm+[i])

    dfs(0, [])
    print(sum(ans)/math.factorial(N))

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 4784
n = int(input())
a = list(map(int, input().split()))
a = [-1] + a
for i, v in enumerate(a[1:], start=1):
    base = "node {0}: key = {1}, ".format(i, v)
    parent = "parent key = {0}, ".format(a[i//2]) if i != 1 else ""
    left = "left key = {0}, ".format(a[i*2]) if i * 2 <= n else ""
    right = "right key = {0}, ".format(a[i*2 + 1]) if i * 2 + 1 <= n else ""
    print(base + parent + left + right)

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

using namespace std;
#define rep(i, n) for(int i = 0 ; i < (int)(n) ; i++)
typedef long long ll;
typedef long double Double;

int len(ll K) {
    int res = 0;
    while (K) {
        K /= 10;
        res++;
    }
    return res;
}

ll sum(ll K) {
    int res = 0;
    while (K) {
        res += K % 10;
        K /= 10;
    }
    return res;
}


int solve(ll K) {

    long long ans = 9 * (len(K) - 1);
    ans = max(ans, sum(K));
    string w;
    stringstream ss;
    ss << K;
    w = ss.str();
    for (int i = 0; i < w.size(); i++) {
        if (w[i] > '0') {
            string t = w.substr(0, i) + string(1, w[i] - 1) + string(w.size() - i - 1, '9');
            stringstream ss;
            ss << t;
            ll T;
            ss >> T;
            ans = max(sum(T), ans);
        }
    }
    return ans;
}

int naive(ll K) {
    ll res = 0;
    for (int i = 1; i <= K; i++) {
        res = max(res, sum(i));
    }
    return res;
}

int main() {
    ll K;
    scanf("%lld", &K);
    cout << solve(K) << endl;
    return 0;
}


Measured memory_bytes: 256