akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<vector<long long>> VVL;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define EXIST(m,v) (m).find((v)) != (m).end()
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

#define en "\n"

constexpr double EPS = 1e-9;
constexpr double PI  = 3.1415926535897932;
constexpr int INF = 2147483647;
constexpr long long LINF = 1LL<<60;
constexpr long long MOD = 1000000007; // 998244353;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

void Main(){
    int L; cin >> L;
    VL A(L); REP(i,L) cin >> A[i];

    ll dp[L+1][5]; REP(i,L+1)REP(j,5) dp[i][j] = LINF;
    REP(i,5) dp[0][i] = 0;

    REP(i,L)REP(j,5){
        if(j == 0 || j == 4) chmin(dp[i+1][j], dp[i][j]+A[i]);
        else if(j == 2) chmin(dp[i+1][j], dp[i][j] + (A[i]%2 != 1));
        else if(j < 4){
            if(A[i] > 0) chmin(dp[i+1][j], dp[i][j] + (A[i]%2 != 0));
            else chmin(dp[i+1][j], dp[i][j] + 2);
        }

        if(j < 4) chmin(dp[i+1][j+1], dp[i+1][j]);
    }

    ll ans = dp[L][4];
    cout << ans << en;
    return;
}

int main(void){
    cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);cout<<fixed<<setprecision(15);
    int t=1; //cin>>t;
    REP(_,t) Main();
    return 0;
}

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

using namespace std;

using ll = long long;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define IN_LL(v) ll v;cin>>v;
#define IN(v) int v;cin>>v;
#define OUT(v) cout<<v<<endl

ll solve(int level, ll x) {
  if (level == 0)
    return x >= 1 ? 1 : 0;

  ll burger_size = 1;
  REP(i, level+2)
    burger_size *= 2;
  burger_size -= 3;

  ll patty = (burger_size + 1) / 2;

  if (x == burger_size / 2 + 1)
    return patty / 2 + 1;
  if (x > burger_size / 2 + 1)
    return (patty / 2 + 1) + solve(level - 1, x - (burger_size / 2 + 1));
  return solve(level - 1, x - 1);
}
int main() {
  IN(N); IN_LL(X);

  OUT(solve(N, X));
  return 0;
}


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

using namespace std;

int main(void) {
  int N; cin >> N;
  vector<pair<int, int>> R, B;
  for (int i = 0; i < N; i++) {
    int xi, yi; cin >> xi >> yi;
    R.push_back(make_pair(yi, xi));
  }
  for (int i = 0; i < N; i++) {
    int xi, yi; cin >> xi >> yi;
    B.push_back(make_pair(xi, yi));
  }
  sort(R.begin(), R.end());
  reverse(R.begin(), R.end());
  sort(B.begin(), B.end());

  int count = 0;
  vector<bool> used(N, false);
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (!used[j] && R[i].first < B[j].second && R[i].second < B[j].first) {
        used[j] = true;
        count++;
        break;
      }
    }
  }

  cout << count << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
void debug() {cout<<endl;}
template<typename T,typename... Args>
void debug(T x,Args... args) {cout<<x<<" ";debug(args...);}
#define forn(i,a,b) for(int i=a;i<b;++i)
#define pb push_back
#define F first
#define S second
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    ll a, b;
    int c, d;
    string s;
    
    cin >> a >> s;
    int id = s.find('.');
    string aux = s.substr(0, id);
    c = atoi(aux.data());
    
    aux = s.substr(id+1);
    d = atoi(aux.data());
    
    b = c*100 + d;
    ll ans = b*a/100;
    
    cout << ans << endl;
}


Measured memory_bytes: 3580
#include <iostream>
#include <vector>
#include <bitset>
#include <cstring>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
typedef long long ll;

string t="north";
string r="west";

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	reverse(t.begin(),t.end());
	reverse(r.begin(),r.end());
	while(1){
		string s; cin >> s;
		if(s=="#")break;
		ll now=0;
		int cnt=0;
		reverse(s.begin(),s.end());
		for(int i=0;i<s.size();i++){
			if(s.substr(i,4)==r){
				now=(2*now)+90;
				i+=3;
			}
			else{
				now=(2*now)-90;
				if(now<0)now=0;
				i+=4;
			}
			cnt++;
		}
		ll q=1LL<<(cnt-1);
		while(now%2==0&&q%2==0){
			now/=2;
			q/=2;
		}
		if(q==1){
			cout << now << endl;
		}else{
			cout << now << "/" << q << endl;
		}
	}
}


Measured memory_bytes: 3004
import java.util.Scanner;

public class Main {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(true){
            int n = sc.nextInt(),x = sc.nextInt(),c = 0;
            if(n == 0 && x == 0) break;
            for(int i = 1,l = n - 2;i <= l;++i){
                for(int j = i + 1,m = n - 1;j <= m;++j){
                    for(int k = j + 1;k <= n;++k){
                        if(i + j + k == x) ++c;
                    }
                }
            }
            System.out.println(c);
        }
    }

}

Measured memory_bytes: 26484
#include <bits/stdc++.h>
using namespace std; 
#define deb(x) cout << #x <<"="<< x <<endl;
#define deb2(x,y) cout << #x <<"="<<x<<", "<<#y<<"="<<y <<endl;
#define deb3(x,y,z) cout << #x <<"="<<x<<", "<<#y<<"="<<y <<", "<<#z<<"="<<z<<endl;
#define deb4(x,y,z,a) cout << #x <<"="<<x<<", "<<#y<<"="<<y <<", "<<#z<<"="<<z<< ", "<<#a <<"="<<a << endl;
#define debarr(x) cout << #x<<"::"<<endl;for(int i : x){cout << i <<" ";} cout <<endl;
#define rep(i,n) for(int i=0;i<(n);i++)
#define fr(i,a,b) for(int i=(a);i<(b);i++)
#define frd(i,a,b) for(int i=(a);i>=(b);i--)
#define vi vector<int>
#define int long long
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define endl '\n'
#define fi first
#define se second
#define fill(a,x) memset(a,x,sizeof a);
#define trav(a,x) for(auto &a:x)
#define ld long double
#define print(a) for(auto x:a)cout<<x<<" ";cout<<endl;
#define print2(a) for(auto x:a){for(auto y:x)cout<<y<<" ";cout<<endl;}; 



void solve(){
	int n;
	cin >> n;
	vector <ld> arr(n+1);
	
	rep(i,n) cin >> arr[i+1];
	
	ld dp[n+1][n+1];
	
	fill(dp,0);
	
	dp[0][0] = 0;
	dp[0][1] =1 - arr[1];
	
	fr(i , 2, n+1) dp[0][i] = (1 - arr[i]) * (dp[0][i-1]);
	
	dp[1][1] = arr[1];
	
	fr(i,2,n+1) dp[i][1] = 0;
	
	
	rep(i , n+1){
		if(i == 0) continue;
		fr(j,2,n+1){
			if(i > j) {dp[i][j] = 0; continue;}
			dp[i][j] = (dp[i-1][j-1] * arr[j]) + (dp[i][j-1] * (1 - arr[j]));
		}
	}
	


	int cnt = (n+2)/2;
	ld ans = 0;
	
	for(int i = cnt ; i<=n ;i++){
	
		ans += dp[i][n];
	}
	cout << fixed << setprecision(10) << ans << endl;


}





signed main(){
    cin.tie(NULL),ios_base::sync_with_stdio(false),cout.tie(NULL);
    int t=1;
    
    while(t--)solve();
    return 0;
}



Measured memory_bytes: 140928
#define debug_interval ' '
#define dump_interval ','
#define debug_toggle 1
//{
#include<bits/stdc++.h>
using namespace std;
#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define fi first
#define se second
#define mp make_pair
#define rev reverse
 
//{
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class...A> inline void dump(){cout<<endl;}
template<class...A> inline void dump_rest() {cout<<endl;}
template<class T, class...A> inline void dump_rest(const T& first, const A&... rest){cout<<dump_interval<<first;dump_rest(rest...);}
template<class T,class...A> inline void dump(const T&first,const A&...rest){cout<<first;dump_rest(rest...);}
template<class...A> inline void debug(){cerr<<endl;}
template<class...A> inline void debug_rest() {cerr<<endl;}
template<class T, class...A> inline void debug_rest(const T& first, const A&... rest){cerr<<debug_interval<<first;debug_rest(rest...);}
template<class T,class...A> inline void debug(const T&first,const A&...rest){if(debug_toggle)cerr<<first,debug_rest(rest...);}
//}

typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}


//}
int n,m;
vint lis;

main(){
	cin>>n>>m;
	for(int i=1;i*i<=m;i++){
		if(m%i==0){
			lis.pb(i);
			if(m/i!=i)lis.pb(m/i);
		}
	}
	sort(rall(lis));
	//for(int x:lis)cout<<x<<endl;
	//cout<<endl;
	for(int i=0;i<lis.size();i++){
		//debug(m/lis[i]);
		if(m/lis[i]>=n){cout<<lis[i]<<endl;return 0;}
	}
}

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

int main(void){
    ll n, m;
    cin >> n >> m;
    vector<ll> a(n), b(n);
    vector<pair<ll, ll>> set(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        set[i] = make_pair(a[i], b[i]);
    }
    
    sort(set.begin(), set.end());
    
    ll ans = 0, idx = 0;
    while (m > 0) {
        if (set[idx].second > 0) {
            ans += set[idx].first;
            set[idx].second--;
            m--;
        }
        else idx++;
    }
    
    cout << ans << endl;
    
}


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

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

using namespace std;
int main() {
	int n;
	double ans = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		double x;
		string u;
		cin >> x >> u;
		if (u == "JPY")
			ans += x;
		else
			ans += x * 380000.0;
	}
	cout << ans << endl;

	return 0;
}

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

int main(){
int h,w,k;
cin >> h >> w >> k;

string c[h];

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

int ans =0;
int answer=0;
for(int bit=0;bit<(1<<h);bit++){
  for(int bits=0;bits<(1<<w);bits++){
    for(int i=0;i<h;i++){
      if(bit & (1<<i)) continue;
      for(int j=0;j<w;j++){
        if(bits & (1<<j)) continue;
        if(c[i][j] == '#') ans ++;
      }
    }
    if(ans == k) answer ++;
    ans = 0;
  }
}

cout << answer <<endl;

}

Measured memory_bytes: 3612
//#include <bits/stdc++.h>
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
//#include "boost/multiprecision/cpp_int.hpp"
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
typedef pair<dd,dd> d_d;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fi first
#define se second
////////////////////////////

#define N 500004

ll kai[N];
ll kai2[N];
ll po(ll i,ll p){
    if(p==0)return 1;
    else{
        i=mod(i);
        if(p==1)return i;
        if(p%2==0)return po(mod(i*i),p/2);
        return mod(i*po(i,p-1));
    }
}
void calc(){
    kai[0]=1;
    kai2[0]=1;
    rep(i,1,N-1){
        kai[i]=mod(kai[i-1]*i);
    }
    kai2[N-1]=po(kai[N-1],i_5);
    for(ll i=N-2;i>=0;i--){
        kai2[i]=mod(kai2[i+1]*(i+1));
    }
}
ll comb(ll n,ll k){
    if(n<k)return 0;
    if(n==0)return 1;
    return mod(mod(kai[n]*kai2[n-k])*kai2[k]);
}
ll bunbo(ll n){
    return po(n,i_5);
}

int main(){fastio
    calc();
    ll n,k;cin>>n>>k;
    ll ans=comb(2*n-1,n);
    rep(i,k+1,n-1){
        Add(ans,-comb(n-1,i)*comb(n,i));
    }
    cout<<mod(ans)<<endl;
    
    return 0;
}


Measured memory_bytes: 8064
#include<iostream>
#include<stack>
using namespace std;
static const int N = 100;
static const int WHITE=0;
static const int GRAY=1;
static const int BLACK=2;
int n, M[N][N];
int color[N], d[N], f[N], tt;
int nt[N];


int next(int u) {
	for (int v = nt[u]; v < n; v++) {
		nt[u] = v + 1;
		if (M[u][v])return v;
	}
	return -1;
}

void dfs_visit(int r) {
	for (int i = 0; i < n; i++) nt[i] = 0;

	stack<int> S;
	S.push(r);
	color[r] = GRAY;
	d[r] = ++tt;

	while (!S.empty()) {
		int u = S.top();
		int v = next(u);
		if (v != -1) {
			if (color[v] == WHITE) {
				color[v] = GRAY;
				d[v] = ++tt;
				S.push(v);
			}
		}else {
			S.pop();
			color[u] = BLACK;
			f[u] = ++tt;
		}
	}
}

void dfs() {
	for (int i = 0; i < n; i++) {
		color[i] = WHITE;
	}
	tt = 0;

	for (int u = 0; u < n; u++) {
		if (color[u] == WHITE) dfs_visit(u);
	}
	for (int i = 0; i < n; i++) {
		cout << i + 1 << " " << d[i] << " " << f[i] << endl;
	}
}


int main()
{
	int u, k, v;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			M[i][j] = 0;
		}
	}
	for (int i = 0; i < n; i++) {
		cin >> u >> k;
		u--;
		for (int j = 0; j < k; j++) {
			cin >> v;
			v--;
			M[u][v] = 1;
		}
	}
	dfs();
    return 0;
}

Measured memory_bytes: 3112
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0)
#define F first
#define S second
#define pb push_back
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,int> tpi;
typedef pair<pii,pii> qpi;
const int MOD = 1e9 + 7;
const int INF = 2e9;
const int MAX = 1e5;
const int MV = 1e5;
int MA = -INF , MI = INF , ANS;

int32_t main()
{
	IO;
	int n , a , b;
	cin >> n >> a >> b;

	cout << min( b , a*n ) << "\n";
	return 0;
}

Measured memory_bytes: 256
import itertools

N = int(input())
points = [tuple(map(int, input().split())) for _ in range(N)]
sum_dist = 0

pattern = list(range(N))
patterns = list(itertools.permutations(pattern))

for pattern in patterns:
    tmp_dist = 0
    for i in range(N - 1):
        x, y = points[pattern[i]]
        nx, ny = points[pattern[i + 1]]
        tmp_dist += ((nx - x) ** 2 + (ny - y) ** 2) ** 0.5
    sum_dist += tmp_dist

print(sum_dist / len(patterns))

Measured memory_bytes: 8052
#include <bits/stdc++.h>
#define Nmax 100005
using namespace std;

bool dp[Nmax];
int n, k, v[Nmax];
//dp[i] = true if First can win with i stones remaining

void read()
{
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> v[i];
    }
}

void solve()
{
    for (int nrStones = 0; nrStones <= k; ++nrStones) {
        for (int i = 1; i <= n; ++i) {
            if (nrStones >= v[i] && !dp[nrStones - v[i]]) {
                dp[nrStones] = true;
            }
        }
    }
    cout << (dp[k] ? "First" : "Second");
}

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


Measured memory_bytes: 384
c,x = map(int,input().split())
if not x:
    print(c)
    exit()
a = list(map(int,input().split()))
s = list(range(0,105))
for i in a:
    s.remove(i)

diffB = 99999
n = 9999

for i in s:
    if diffB > abs(c-i):
        diffB = abs(c-i)
        n = i
print(n)


Measured memory_bytes: 61848
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin >> n;
	vector<int>b(n, 0);
	for(int i = 0; i < n-1; i++)cin >> b[i];
	b[n-1] = 1000000;
	vector<int>a(n + 10, 0);
	for(int i = 0; i < n; i++){
		if(i == 0)a[i] = b[0];
		else a[i] = min(b[i], b[i-1]);
	}
	int ans = 0;
	for(int i = 0; i < n; i++)ans += a[i];
	cout << ans << endl;
}

Measured memory_bytes: 256
N = int(input())
D,X = [int(hoge) for hoge in input().split()]
for i in range(N):
    A = int(input())
    X += (D-1)//A + 1
print(X)

#N人、D日　それぞれk*Ai(0-index)日目にチョコを食べる。
#消費したチョコの数＋X



Measured memory_bytes: 38384
#include<stdio.h>
#include<string.h>
int main ()
{
	char s[1000];
	int c=0,i;
	scanf("%s",s);
	for(i=0;i<3;i++){
		if (s[i]=='o'){
			c++;
		}
	}
	printf("%d\n",700+(100*c));
	return 0;
}

Measured memory_bytes: 128
package main

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

type elem struct {
	a int
	b int
}
type array []elem

func (a array) Len() int {
	return len(a)
}

func (a array) Swap(i, j int) {
	a[i], a[j] = a[j], a[i]
}

func (a array) Less(i, j int) bool {
	return a[i].a < a[j].a
}

var sc = bufio.NewScanner(os.Stdin)

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

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

func main() {
	sc.Split(bufio.ScanWords)
	var n, k int
	fmt.Scan(&n, &k)
	ar := make(array, n)
	for i := 0; i < n; i++ {
		ar[i].a, ar[i].b = nextInt(), nextInt()
	}
	sort.Sort(ar)
	c := 0
	for _, x := range ar {
		if c+x.b < k {
			c += x.b
		} else {
			fmt.Println(x.a)
			break
		}
	}
}


Measured memory_bytes: 3840
N = int(input())
A = list(map(int, input().split()))
ans = 0

if sum(A)%N == 0:
    x = sum(A)//N
    for i in range(N):
        ans += (x-A[i])**2
    print(ans)
else:
    x = sum(A)//N
    b = sum(A)//N+1
    if sum(A)/N - x > b - sum(A)/N:
        x = b
    for i in range(N):
        ans += (x-A[i])**2
    
    print(ans)



Measured memory_bytes: 9112
#include<iostream>
using namespace std;
int main(){
    int a,b,k;
    cin>>a>>b>>k;
    int ans;
    int i=100;
    int count=0;
    while(true){
        if(a%i==0&&b%i==0){
            ans=i;
            count++;
        }
        i--;
        if(count==k)
            break;
        if(i==0)
            break;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(){
  int i,ans=0,x=0,n,max=0;
  char s[101];
  
scanf("%d",&n);
scanf("%s",s);

for(i=0;i<n;i++){
  if(s[i]=='I') x++;
  
  else x--;

  if(max<x) max=x;
}
printf("%d",max);
  return 0;
}


Measured memory_bytes: 128
import sys
 
while True:
    h, w = [ int( val ) for val in sys.stdin.readline().split( " " ) ]
    if 0 ==h and 0 == w:
        break
    pa = [ "#", "." ]
    ouput = []
    for i in range( h ):
        for j in range( w ):
            ouput.append( pa[(i+j)&1] ) 
        ouput.append( "\n" )    
    print( "".join( ouput ) )

Measured memory_bytes: 4416
from bisect import bisect_left
from collections import deque

n = int(input())
a = [int(input()) for _ in range(n)]

q = deque([-1])
for x in a:
    insert_pos = bisect_left(q, x) - 1
    # bisect_left[0,len(lis)] == 以上の最小
    # 手前は未満の最大[-1,len(lis))
    if insert_pos == -1:
        q.appendleft(x)
    else:
        q[insert_pos] = x

ret = len(q)

print(ret)

# 最小パス被覆


Measured memory_bytes: 8060
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
mod=10**9+7

N,A,B=MI()

def calc(n):
    temp=0
    for i in range(5):
        temp+=n%10
        n=n//10
    return temp


ans=0
for i in range(N):
    n=i+1
    temp=calc(n)
    if temp>=A and temp<=B:
        ans+=n
        
print(ans)




Measured memory_bytes: 40488
from math import *
N = int(input())
T = []
A = []
for i in range(0, N):
    ti, ai = [int(x) for x in input().split()]
    T.append(ti)
    A.append(ai)

prevT = T[0]
prevA = A[0]
for i in range(1, N):
    nextfacT = (prevT + T[i] - 1) // T[i]
    nextfacA = (prevA + A[i] - 1) // A[i]
    nextfac = max(nextfacT, nextfacA)
    prevT = nextfac * T[i]
    prevA = nextfac * A[i]

print(prevA+prevT)


Measured memory_bytes: 3064
# coding: utf-8

N, K = [int(i) for i in input().split()]
snk = [0 for _ in range(N)]
for i in range(K):
    d = int(input())
    a_d = [int(i) for i in input().split()]
    for a in a_d:
        snk[a-1] += 1
print(snk.count(0))


Measured memory_bytes: 9060
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
typedef struct pair<ll,int> P;

int main() {
	int n,k,x,y;
	cin>>n>>k>>x>>y;
	if(n<=k)cout<<n*x<<endl;
	if(n>k)cout<<k*x+(n-k)*y<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store") // to restrict undesirable precision
#pragma GCC optimize ("-fno-defer-pop")// to pop argument of function as soon as it returns
#define all(a) a.begin(),a.end()
#define ll long long int
#define ld long double
ll  power(ll a,ll b,ll m){ if(b==0) return 1; if(b==1) return a%m; ll t=power(a,b/2,m)%m; t=(t*t)%m; if(b&1) t=((t%m)*(a%m))%m; return t;}
ll  modInverse(ll a, ll m) { return power(a, m-2, m); }
#define ps push_back
#define fs first
#define sc second
#define takeline cin.ignore();
#define iactive cout.flush();
#define N 3000005
#define endl "\n"
#define mod 1000000007
#define PI 3.141592653589793
//((1.0l)*BIG MULTIPLY MAGIC?)
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
//-----------------------------------------------
ll n,a,b,c,d;
unordered_map<ll,ll> dp;
ll findans(ll n){
    if(n==0) return 0;
    if(n==1) return d;
    if(dp.count(n)){
        return dp[n];
    }
    ll an=4e18,i;
    if(n<=4e9)
        an=min(an,n*d);
    for(i=-12;i<=12;i++){
        ll nxt_n=n+i;
        if(nxt_n<0)
            continue;
        if(nxt_n%2==0&&nxt_n/2<n){
            an=min(an,d*abs(i)+a+findans(nxt_n/2));
        }
        if(nxt_n%3==0&&nxt_n/3<n){
            an=min(an,d*abs(i)+b+findans(nxt_n/3));
        }
        if(nxt_n%5==0&&nxt_n/5<n){
            an=min(an,d*abs(i)+c+findans(nxt_n/5));
        }
        if(nxt_n%6==0&&nxt_n/6<n){
            an=min(an,d*abs(i)+a+b+findans(nxt_n/6));
        }
        if(nxt_n%10==0&&nxt_n/10<n){
            an=min(an,d*abs(i)+a+c+findans(nxt_n/10));
        }
        if(nxt_n%15==0&&nxt_n/15<n){
            an=min(an,d*abs(i)+c+b+findans(nxt_n/15));
        }
    }   
    return dp[n]=an;
}
int main(){

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int t;
    cin>>t;
    while(t--){
        dp.clear();
        cin>>n>>a>>b>>c>>d;
        ll an=findans(n);
        cout<<an<<endl;
    }
    return 0;
}

Measured memory_bytes: 10076
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int bannum = sc.nextInt();
		String keyword = sc.next();
		String kanban;
		int cnt = 2;
		int knum = 0;
		for(int s = 0;s < bannum;s++){
			kanban = sc.next();
			loop:for(int i = 0; kanban.length()-i > keyword.length()-1;i++){
				if(keyword.charAt(0) == kanban.charAt(i)){
					for(int j = kanban.length()-1;j-i>=keyword.length()-1;j--){
						if(keyword.charAt(keyword.length()-1) == kanban.charAt(j)){
							cnt = 2;
							for(int k = 1;k <= keyword.length()-1;k++){
								//System.out.println(keyword.charAt(k));
								//System.out.println(kanban.charAt((j-i)/(keyword.length()-1)*k+i));
								if(keyword.charAt(k) == kanban.charAt((j-i)/(keyword.length()-1)*k+i)){
									cnt++;
									if(cnt-1 == keyword.length()){
										knum++;
										break loop;
									}								
								}
							}
						}
					}
				}
			}			
		}
		System.out.println(knum);
/*		if(cnt-1 == keyword.length()){
			System.out.print("?????£??????");
		}
	*/	
		
	}

}

Measured memory_bytes: 28276
#include <iostream>
using namespace std;
int main()
{
  int r, g, b;
  cin >> r >> g >> b;
  int c = (100 * r + 10 * g + b) ;
  if(c % 4 == 0)
  cout << "YES" << endl;
  else cout << "NO" << endl;
 }

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

int main() {
    int n, x;
    string command;
    list<int> v;
    cin >> n;

    for (int i=0; i<n; i++) {
        cin >> command;
        if (command[0]=='i') {
            cin >> x;
            v.push_front(x);
        }
        else if (command[6]=='L') {
            v.pop_back();
        }
        else if (command[6]=='F') {
            v.pop_front();
        }
        else if (command[0]=='d') {
            cin >> x;
            for (list<int>::iterator it=v.begin(); it!=v.end(); it++) {
                if (*it==x) {
                    v.erase(it);
                    break;
                }
            }
        }
    }

    int i=0;
    for (list<int>::iterator it=v.begin(); it!=v.end(); it++) {
        if (i++) cout << " ";
        cout << *it;
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 34392
package main

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

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	scanner.Scan()

	N, err := strconv.Atoi(scanner.Text())
	if err != nil {
		log.Fatal(err)
	}

	A := make([]int, N)
	B := make([]int, N)
	C := make([]int, N-1)

	for i := 0; i < N; i++ {
		scanner.Scan()
		target, err := strconv.Atoi(scanner.Text())
		if err != nil {
			log.Fatal(err)
		}
		A[i] = target
	}

	for i := 0; i < N; i++ {
		scanner.Scan()
		target, err := strconv.Atoi(scanner.Text())
		if err != nil {
			log.Fatal(err)
		}
		B[i] = target
	}
	for i := 0; i < N-1; i++ {
		scanner.Scan()
		target, err := strconv.Atoi(scanner.Text())
		if err != nil {
			log.Fatal(err)
		}
		C[i] = target
	}

	answer := 0
	for i := 0; i < N; i++ {
		answer += B[A[i]-1]

		if i > 0 && A[i]-A[i-1] == 1 {
			answer += C[A[i-1]-1]
		}
	}

	fmt.Println(answer)
}


Measured memory_bytes: 1836
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        final int N = sc.nextInt();
        
        final long MOD = 1_000_000_007;
        
        long x10 = 1;
        long x9 = 1;
        long x8 = 1;
        
        for (int i = 0; i < N; i++) {
            x10 *= 10;
            x9 *= 9;
            x8 *= 8;
            
            x10 %= MOD;
            x9 %= MOD;
            x8 %= MOD;
        }
        long answer = x10 - x9 * 2 + x8;
        answer %= MOD;
        if (answer < 0) {
            answer += MOD;
        }
        System.out.println(answer);
    }
}


Measured memory_bytes: 35788
#define __mode_debug__
/*   ξ
     ll
   ＿ll＿
 ／  ∞  ＼
│*  Ａ  *│
│*  Ｃ  *│
│*  祈  *│
│*  願  *│
│*      *│
 ￣￣￣￣￣    */
//C++14 (GCC 5.4.1)
#include <bits/stdc++.h>
using namespace std;
#ifdef __mode_debug__
    #define DBG
#else
    #define DBG if(false)
#endif

#define LLINF (1LL<<60)
typedef long long ll;
#define mod 1000000007

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define rrepd(i,a,b) for(int i=(a);i>=(b);i--)
#define repi(itr,ds) for(auto itr=ds.begin();itr!=ds.end();itr++)

template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); }

//DUMP
//  ostream vector<T> , vector<vector<T>> , set<T> ,queue<T> , priority_queue<T> , pair<T,U> , map<T,U>
template<class T> ostream& operator<<(ostream&os,vector<T>&vec){os<<"{ ";rep(i,vec.size()) os<<((i==0)?"":", ")<<i<<":"<<vec[i];os<<" }";return os;}
template<class T> ostream& operator<<(ostream&os,vector<vector<T>>&vec){os<<"{"<<endl;rep(i,vec.size())os<<"\t   "<<i<<":"<<vec[i]<<((i==vec.size()-1)? "":",")<<endl;os<<"\t }";return os;}
template<class T> ostream& operator<<(ostream&os,set<T>&p){os<<"{ ";repi(itr,p)  os<<((itr==p.begin())?"":", ")<<*itr;os<<" }";return os;}
template<class T> ostream& operator<<(ostream&os,queue<T>&p){queue<T> q(p);os<<"[< "<<(q.empty()?" <]":"");while(!q.empty()){os<<q.front();q.pop();os<< (q.empty() ? " <]" : ", ");}return os;}
template<class T> ostream& operator<<(ostream&os,priority_queue<T>&p){priority_queue<T> q(p);os<<"[< "<<(q.empty()?" <]":"");while(!q.empty()){os<<q.top();q.pop();os<< (q.empty() ? " <]" : ", ");}return os;}
template<class T,class U> ostream& operator<<(ostream&os,pair<T,U>&p){os<<"("<<p.first<<","<<p.second<<")";return os;}
template<class T,class U> ostream& operator<<(ostream&os,map<T,U>&p){os<<"{ ";repi(itr,p)os<<((itr==p.begin())?"":", ")<<itr->first<<":"<<itr->second;os<<" }";return os;}
void dump_f(string &nm){cerr<<endl;}
template<class T,class... Ts> void dump_f(string &nm,T &&x,Ts&&... ts){int l=nm.find_first_of(',');string name(nm,0,l),nx(nm,l+1,-1);cerr<<"  "<<name<<"\t:"<<x<<endl;dump_f(nx,forward<Ts>(ts)...);}
template<class... Ts> void dump_m(int &&ln,string &&nm,Ts&&... ts){cerr<<"[ln:"<<ln<<"]"<<endl;dump_f(nm,forward<Ts>(ts)...);}
#define dump(...) DBG dump_m(__LINE__,#__VA_ARGS__,__VA_ARGS__)

#define lower_bound_idx(V,c) distance(V.begin(),lower_bound(V.begin(),V.end(),c))


int main() {
    ios::sync_with_stdio(false);//stdoutとcoutの同期解除
    cin.tie(nullptr);//cinとcoutの同期解除
    
    ll N,ans;
    cin >>N;
    if(N%2==1){
        cout<<0<<endl;
        return 0;
    }
    ans=0;
    ll x=10;
    while(x<=N){
        ans+=N/x;
        x*=5;
    }

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr ll mod=1e9+7;

int main()
{
  ll A,B,M;
  cin>>A>>B>>M;
  vector<ll> a(A),b(B);
  for(auto&& e: a) cin>>e;
  for(auto&& e: b) cin>>e;
  ll init=*min_element(b.begin(), b.end());
  multimap<ll, pair<ll,ll>> xyc;
  for (int i = 0; i < M; ++i)
  {
    ll x,y,c;
    cin>>x>>y>>c;
    x--;y--;
    xyc.emplace(x,make_pair(y,c));
  }
  ll ans=1LL<<60;
  for (int i = 0; i < A; ++i)
  {
    ll select=init;
    auto p=xyc.equal_range(i);
    for(auto itr=p.first;itr!=p.second;++itr)
    {
      select=min(select,
        b[(itr->second).first]
        -(itr->second).second);
    }
    ans=min(ans,select+a[i]);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 11176
uses
  math;
var
  f:array[0..3033,0..3033] of longint;
  n,m,j,i:longint;
  s,r,kq:ansistring;
BEGIN
  ///assign(input,'a.in'); reset(input);
  readln(s);  n := length(s);
  readln(r);  m := length(r);
  
  fillchar(f,sizeof(f),0);
  for i:=1 to n do
    for j:=1 to m do
      if s[i] <> r[j] then f[i,j] := max(f[i-1,j], f[i,j-1])
      else f[i,j] := 1 + f[i-1,j-1];
  kq := '';
  i:=n; j:=m;
  while((i>0) and (j>0)) do begin
    if (f[i,j] = f[i-1,j-1] + 1) and (s[i]=r[j]) then begin kq:=s[i] + kq; dec(i); dec(j); end
    else
      if f[i,j] = f[i-1,j] then dec(i) else dec(j);
  end;
  writeln(kq);
END.

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

using namespace std;


int main() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	int res = 0;
	int maxi = 0;
	for (int i = 0; i < n; i++) {
		char c = s[i];
		if (c == 'I')
			res++;
		else
			res--;
		maxi = max(maxi, res);
	}

	cout << maxi << "\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <string>
#include <cmath>
#include <sstream>
#include <istream>
#include <iomanip>
#include <typeinfo>
#include <stack>
#include <queue>

using namespace std;
typedef long long ll;
//試合した人だけが次の日試合できる可能性があるのでO(N^2)のはず...
//前日試合していない人が次の日試合できるなら前日試合しているはずという矛盾
int main(){

    ll N;
    cin >> N;

    vector<vector<ll > > vec(N, vector<ll >(N - 1, 0));

    //どこまで確認したか
    vector<ll > p(N, 0);  
    //p更新用のキュー  
    queue<ll > p_que;
    //前日試合をした人を格納するキュー 初日は全員該当
    queue<ll > yesterday_que;
    for(ll i = 0; i < N; i++){
        for(ll j = 0; j < N - 1; j++){
            ll in;
            cin >> in;
            vec[i][j] = in - 1;
        }
        yesterday_que.push(i);
    }

    ll ans = 0;
    
    //最大回数試合をさせて残っている選手がいれば-1する方針
    ll day = 0;
    bool fin_flg = false;
    while(day <= N * (N - 1) / 2){
        //cout << "day" << day + 1 << " size" << yesterday_que.size() << endl;
        ll loop = yesterday_que.size();
        fin_flg = false;

        for(ll j = 0; j < loop; j++){
            
            ll i = yesterday_que.front();
            yesterday_que.pop();

            //cout << i << endl;
            //cout << "1" << endl;
            if(p[i] >= N - 1) continue;
            //cout << "1" << endl;
            if(vec[i][p[i]] == -1){
                //cout << vec[i][p[i]] << endl;
                //p[i]++;
                continue;
            } 
            //cout << "1" << endl;
            //cout << i + 1 << " " << p[i] << endl;
            //cout <<  vec[vec[i][p[i]]][p[vec[i][p[i]]]] << endl;

            if(i == vec[vec[i][p[i]]][p[vec[i][p[i]]]] ){
                //cout << i + 1 << " " << vec[i][p[i]] + 1 << " " << p[i] << endl;
                //cout << "yes" << endl;
                //p[vec[i][p[i]]]++;
                
                //更新準備
                p_que.push(i);
                p_que.push(vec[i][p[i]]);
                //前日試合したリストに追加
                yesterday_que.push(i);
                yesterday_que.push(vec[i][p[i]]);

                //不要なので-1格納
                vec[vec[i][p[i]]][p[vec[i][p[i]]]] = -1;
                vec[i][p[i]] = -1;
                
                //試合したのでフラグ更新
                fin_flg = true;
            }

            ans++;

        }
        
        //各人どこまで試合をしたか更新
        while(!p_que.empty()){
            p[p_que.front()]++;
            p_que.pop();
        }


        //確認
        
        /* 
        for(ll j = 0; j < N; j++){
            for(ll k = 0; k < N - 1; k++){
                cout << vec[j][k] << " ";
            }
            cout << p[j] <<  endl;
        }
        */
        
        //連日試合が開催されていなければ終わり
        if(fin_flg == false){
            break;
        }
        

        day++;
        //cout << "day : " << day << endl;
    }

    //全試合終わっているか?

    for(ll k = 0; k < N; k++){
       if(p[k] != N - 1){
           cout << "-1" << endl;
           return 0;
       }
    }
    cout << day << endl;

}

Measured memory_bytes: 8064
#include <cstdio>
#define maxn 100005
using namespace std;

typedef long long LL;

int cnt[maxn];
LL sum = 0;

inline LL s(const LL& i)
{
	return cnt[i] * i;
}

int main(int argc, char** argv)
{
	int n, q;
	scanf("%d", &n);
	for(int i=0; i<n; i++)
	{
		int t;
		scanf("%d", &t);
		sum += t;
		cnt[t] ++;
	}
	scanf("%d", &q);
	while(q--)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		sum -= s(x) + s(y);
		cnt[y] += cnt[x];
		cnt[x] = 0;
		sum += s(y);
		printf("%lld\n", sum);
	}
	return 0;
}


Measured memory_bytes: 2072
k,n=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
b=[0]*n
for i in range(n):
  b[i]=a[i]-k
b.sort()
a=b+a
s=0
e=1000000000000000000
for i in range(1,n+n):
  s+=(a[i]-a[i-1])
  if i>=n:
    s-=(a[i-n+1]-a[i-n])
  if e>s and i>=n-1:
    e=s
print(e)
    

Measured memory_bytes: 26444
#include <bits/stdc++.h>
using namespace std;
int A, B;
int main() {
    cin >> A >> B;
    vector<int> s(3);
    s.at(0) = A + B;
    s.at(1) = A - B;
    s.at(2) = A * B;

    cout << max({s.at(0), s.at(1), s.at(2)}) << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			String str = sc.next();
			if (str.equals("#"))
				break;
			char[] c = new char[str.length()];
			for (int i = 0; i < str.length(); i++)
				switch (str.charAt(i)) {
				case 'a':
				case 'b':
				case 'c':
				case 'd':
				case 'e':
				case 'f':
				case 'g':
				case 'q':
				case 'r':
				case 's':
				case 't':
				case 'v':
				case 'w':
				case 'x':
				case 'z':
					c[i] = 'r';
					break;
				default:
					c[i] = 'l';
					break;
				}
			int a = 0;
			char ci = c[0];
			for (int i = 0; i < str.length(); i++)
				if (c[i] != ci) {
					a++;
					ci = c[i];
				}
			System.out.println(a);
		}
		sc.close();
	}
}

Measured memory_bytes: 20096
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define rvisort(v) sort(v.begin(), v.end(), greater<int>());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
 
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using ul = unsigned long;
 
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }
 
const int mod=1e9+7;
 
struct mint {
  ll x;
  mint(ll x=0):x(x%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
};
 
mint c[4005][4005];
void init() {
  c[0][0] = 1;
  for (int i = 0; i <= 4000; i++) {
    for (int j = 0; j <= i; j++) {
      c[i+1][j] += c[i][j];
      c[i+1][j+1] += c[i][j];
    }
  }
}
mint comb(int n, int k) {
  return c[n][k];
}
 
bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;
 
    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
 
    return true;
}
 
map<ll, ll> primeFact(ll n) {
  map<ll, ll> res;
  for (ll i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      res[i]++;
      n /= i;
    }
  }
  if (n != 1) res[n]++;
  return res;
}
 
void printv(vi& v){
  rep(i,v.size()) cout << v[i] << " ";
  cout << endl;
}
void printv(vll& v){
  rep(i,v.size()) cout << v[i] << " ";
  cout << endl;
}
int vtotal(vi& v){
  int total=0;
  rep(i,v.size()) total+=v[i];
  return total;
}
 
int main()
{
  //init(); // mint初期化
  cin.tie( 0 );
  ios::sync_with_stdio( false );
 
  int n,m,c;cin>>n>>m>>c;
  vi b(m);
  rep(i,m)cin>>b[i];
  vvi a(n,vi(m));
  rep(i,n){
    rep(j,m)cin>>a[i][j];
  }
 
  int ans=0;
  rep(i,n){
    int total=0;
    rep(j,m){
      total+=b[j]*a[i][j];
    }
    total+=c;
    if(total>0)ans++;
  }
  cout<<ans<<endl;
 
  return 0;
}

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

using namespace std;
typedef long long LL;

char ss[1005][1005];
int dis[1005][1005];


priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> que;

void add(int h, int wo, int w, int d) {
    if (dis[h][w] != -1 || ss[h][w-1] == '#')return;
    que.push({d, h * wo + w - 1});
}

int main() {
    int h, w, ch, cw, dh, dw;
    cin >> h >> w >> ch >>cw >> dh >> dw;


    for (int i = 1; i <= h; ++i) {
        scanf("%s", ss[i]);
    }

    for (int i = 1; i <= h; ++i) {
        for (int j = 1; j <= w; ++j) {
            dis[i][j] = -1;
        }
    }


    que.push({0, ch * w + (cw - 1)});

    int tar = dh * w + dw - 1;
    int ans = -1;

    while (!que.empty()) {
        if(que.top().second == tar){
            ans = que.top().first;
            break;
        }
        int d = que.top().first;
        int hh = que.top().second / w;
        int ww = que.top().second % w + 1;
        que.pop();
        //cout<<hh<<' '<<ww<<' '<<d<<endl;
        if (dis[hh][ww] != -1) continue;
        dis[hh][ww] = d;
        add(hh + 1, w, ww, d);
        add(hh - 1, w, ww, d);
        add(hh, w, ww - 1, d);
        add(hh, w, ww + 1, d);

        for (int i = -2; i <= 2; ++i) {
            if (hh + i > h)break;
            if (hh + i <= 0)continue;
            for (int j = -2; j <= 2; ++j) {
                if (ww + j > w)break;
                if (ww + j <= 0)continue;
                add(hh + i, w, ww + j, d + 1);
            }
        }
    }

    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 9136
a,b,c,x,y = map(int, input().split())

ans1 = c*max(x,y)*2
ans2 = a*x + b*y
if x<y:
    ans3 = c*2*x + b*(y-x)
else:
    ans3 = c*2*y + a*(x-y)

print(min(ans1,ans2,ans3))


Measured memory_bytes: 3060
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int X = sc.nextInt();
		
		int[] m = new int[N];
		int sum = 0;
		
		for(int i = 0; i < N; i++) {
			m[i] = sc.nextInt();
			sum += m[i];
		}
		
		Arrays.sort(m);
		
		int num = N + (X - sum) / m[0];
		
		System.out.println(num);
		
	}
}


Measured memory_bytes: 21076
using System;
using System.Collections.Generic;
class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        List<int> hon = new List<int> { 2, 4, 5, 7, 9 };
        List<int> pon = new List<int> { 0, 1, 6, 8 };
        List<int> bon = new List<int> { 3 };

        int i = n % 10;

        if (hon.Contains(i))
        {
            Console.WriteLine("hon");
        }
        else if (pon.Contains(i))
        {
            Console.WriteLine("pon");
        }
        else if (bon.Contains(i))
        {
            Console.WriteLine("bon");
        }
    }
}

Measured memory_bytes: 27612
#include <iostream>
#include <queue>
#include <string>

using namespace std;

int main() {
	priority_queue<int> que;
	string com;
	int v;

	while (1) {
		cin >> com;
		if (com == "insert") {
			cin >> v;
			que.push(v);
		}
		else if (com == "extract") {
			cout << que.top() << endl;
			que.pop();
		}
		else {
			break;
		}
	}

	return 0;
}

Measured memory_bytes: 7296
import sys
input = sys.stdin.readline
from functools import reduce
def gcd_list(n):
    return reduce(gcd, n)

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

n = int(input())
a = list(map(int, input().split()))
print(gcd_list(a))


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

int main() {

    int N;
    cin>>N;
    pair<pair<string, int>, int> p[101];
    string S;
    int P;
    for (int i = 0; i < N; ++i) {
        cin>>S>>P;
        p[i] = make_pair(make_pair(S, -P), i);
    }
    sort(p,p+N);

    for (int i = 0; i < N; ++i) {
        cout<<p[i].second+1<<endl;
    }

    return 0;
}

Measured memory_bytes: 256
num = [1, 1]
 
for num[0] in 1..9 do
 
  for num[1] in 1..9 do
    print num[0], "x", num[1], "=", num[0] * num[1], "\n"
    num[1] += 1
  end
 
  num[0] += 1
end

Measured memory_bytes: 6080
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=(a); i<=(b); i++)
#define per(i,a,b) for (int i=(a); i>=(b); i--)
using namespace std;

const int maxn = 200005;
const int mod = 1e9 + 7;
struct node {
	int x, v;
	bool operator < (const node & a) const {
		return v < a.v;
	}
} a[maxn];
int f[maxn], g[maxn], L[maxn], R[maxn], stk[maxn];
int n, l, r, mid, top;
vector<int> p[maxn];

int main() {
	cin >> n;
	rep (i, 1, n)
		cin >> a[i].x >> a[i].v;
	sort(a + 1, a + n + 1);
	
	rep (i, 1, n) {
		if (!top || a[i].x > a[stk[top]].x)
			stk[++top] = i;			
		l = 1; r = top;
		while (l < r) {
			mid = (l + r) >> 1;
			if (a[stk[mid]].x > a[i].x) 
				r = mid;
			else
				l = mid + 1;
		}
		L[i] = stk[l];
	}
	
	top = 0;
	per (i, n, 1) {
		if (!top || a[i].x < a[stk[top]].x)
			stk[++top] = i;
		l = 1; r = top;
		while (l < r) {
			mid = (l + r) >> 1;
			if (a[stk[mid]].x < a[i].x)
				r = mid;
			else
				l = mid + 1;
		}
		R[i] = stk[l];
	}
	
	rep (i, 1, n) 
		p[R[i]].push_back(L[i]);
		
	g[0] = 1;
	rep (i, 1, n) {
		g[i] = g[i-1];
		sort(p[i].begin(), p[i].end());
		for (auto k : p[i]) 
			g[i] = ((g[i] + g[i] - (k >= 2 ? g[k-2] : 0))
					% mod + mod) % mod;
	}
	cout << (g[n] - g[n-1] + mod) % mod << endl;
	
	return 0;
}

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

 
int main() {
	ll A,B;
  	cin >> A >> B;
  	if(A+B==24){
      cout << 0 << endl;
    }
  	else if(A+B>=24){
      cout << A+B-24 << endl;
    }
  	else{
      cout << A+B <<  endl;
    }
}


Measured memory_bytes: 256
maxnum = 110000
primes = [True]*maxnum
primes[0] = primes[1] = False
for i in xrange(maxnum):
    if i >= maxnum**0.5 : break
    if not primes[i]: continue
    for j in xrange(i*2,maxnum,i): primes[j] = False
p = [ i for i in xrange(maxnum) if primes[i] ]

while True:
    n = int(raw_input())
    if n == 0: break
    print sum( [ p[i] for i in xrange(n) ] )

Measured memory_bytes: 5532
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
typedef pair<int,int> ii;
 
const int N = 1e5 + 5;
 
int n,x[N],y[N],h[N];
 
int geth(int cx,int cy) {
  int res = -1,mx = 99999999;
  for (int i = 1 ; i <= n ; i++) {
    int a = abs(cx - x[i]);
    int b = abs(cy - y[i]);
    if (res == -1) {
      if (h[i] == 0) {
        mx = min(mx,a + b);
      } else {
        res = a + b + h[i];
      }
    } else {
      if (max(res - a - b,0) != h[i]) return -1;
    }
  }
  if (mx != 99999999 && res > mx) return -1;
  return res;
 
}
 
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> n;
  for (int i = 1 ; i <= n ; i++)
    cin >> x[i] >> y[i] >> h[i];
  for (int cx = 0 ; cx <= 100 ; cx++)
    for (int cy = 0 ; cy <= 100 ; cy++) {
      int temp = geth(cx,cy);
      if (temp != -1) {
        cout << cx << " " << cy << " " << temp << endl;
        return 0;
      }
    }
}

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

#define min3(a,b,c)   min(a,min(b,c))
#define max3(a,b,c)   max(a,max(b,c))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define max4(a,b,c,d) max(max(a,b),max(c,d))

#define count_one(a) __builtin_popcount(a)  // Returns the number of set bits(1) in a number(a). In long long use __builtin_popcountll(a)
#define parity(i)    __builtin_parity(i)  //even parity 0 and odd parity 1
#define blz(a)       __builtin_clz(a) //Returns the number of leading zeroes in a number(a)
#define btz(a)       __builtin_ctz(a) //Returns the number of trailing zeroes in a number(a)
#define gcd(a,b)     __gcd(a,b)
#define lcm(a,b)     (a*(b/gcd(a,b)))

#define pb   push_back
#define PI   M_PI
#define endl "\n"
#define sc   scanf
#define pf   printf

#define ll  long long
#define ull unsigned long long

#define W(t)            while(t--)
#define rep1(i,n)       for(int i = 0; i < n; i++)
#define rep2(a,b)       for(int i = a; i <= b; i++)
#define repit(it,type)  for(it = type.begin(); it != type.end(); it++)
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
using namespace __gnu_cxx;

int main()
{
     IOS
     string s;
     int i;
     cin>>s;

     for(i = 0; i < s.size(); i++)
     {
          if(s[i]=='?')
               s[i]='D';
     }
     cout<<s<<endl;

     return 0;
}



Measured memory_bytes: 3804
#include <iostream>
#include <cstdlib>
#include <algorithm>

using namespace std;

void printv(int v[], int len) {
	for (int i = 0; i < len; i++)
		cout << v[i] << ",";
	cout << endl;
}

int arraytoint(int v[]) {
	int ans = 0;
	int digit = 10000000;
	for (int i = 0; i < 8; i++) {
		ans += v[i] * digit;
		digit /= 10;
	}
	return ans;
}

int solve(string s) {
	char c;
	int seq[8];
	int maxi, mini;
	for (int i = 0; i < 8; i++) {
		c = s[i];
		seq[i] = atoi(&c);
	}
//	printv(seq, 8);
	sort(seq, seq + 8, greater<int>());
	maxi = arraytoint(seq);
	sort(seq, seq + 8);
	mini = arraytoint(seq);
	return maxi - mini;
}

int main() {
	string s;
	int n;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s;
		cout << solve(s) << endl;
	}
	return 0;
}

Measured memory_bytes: 1228