akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h> 
#include <chrono>
using namespace std;
 
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
 
//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef long long LL;
typedef pair<LL, LL> PLL;
 
//container util
//------------------------------------------
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define ALL(a)  (a).begin(),(a).end()
//constant
//--------------------------------------------
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))


int main(){
    int N;cin>>N;
    vector<LL>A(N);
    REP(i,N)cin>>A[i];
    SORT(A);
    LL res=A[N-1];
    int cnt=0;
    int sum=0;
    int pos=N-2;
    while(sum<N-2){
        if(cnt<=1){
            res+=A[pos];cnt++;sum++;
        }else{
            cnt=0;pos--;
        }
    }
    cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 4840
#include <stdio.h>

int main() {
    int a, b;
    
    while (scanf("%d %d", &a, &b), a || b) {
        if(a > b) {
            printf("%d %d\n", b, a);
        } else {
            printf("%d %d\n", a, b);
        }
    }
    
    return 0;
}


Measured memory_bytes: 2104
rpn = map(str, raw_input().split())
stack = []

for i in rpn:
    if i.isdigit():
        stack.append(i)
    else:
        n1 = int( stack.pop() )
        n2 = int( stack.pop() )

    if   i == '+':
        stack.append( str(n2+n1) )
    elif i == '-':
        stack.append( str(n2-n1) )
    elif i == '*':
        stack.append( str(n2*n1) )

print stack[0]

Measured memory_bytes: 6424
#include<bits/stdc++.h>
#define Fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

int main()
{
    Fast;
    long long t,n,m,i,j,k,x=0,y=1e18,z;
    cin>>n;
    long long a[n+5];
    for( i=0;i<n;i++){
        cin>>a[i];
        x=max(x,a[i]);
    }

    for(long long i=1;i<=x+1;i++){
            z=0;
        for(long long j=0;j<n;j++){
            z=z+((a[j]-i)*(a[j]-i));
        }
        y=min(y,z);
    }
    cout<<y<<endl;


}


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

using namespace std;

using ll = long long;

int Solve() {
    int n, k;
    cin >> n >> k;
    vector<bool> used(10, true);
    for (int i = 0, x; i < k; ++i) {
        cin >> x;
        used[x] = false;
    }

    int res = n;
    while (true) {
        bool can = true;
        int x = res;
        while (x) {
            if (!used[x % 10]) {
                can = false;
                break;
            }
            x /= 10;
        }

        if (can) break;

        ++res;
    }
    return res;
}

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

    cout << Solve() << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

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

signed main(){
	int n,ma = 0,ans = 0;
	cin >> n;
	for(int i = 0;i < n;i++){
		int h;
		cin >> h;
		if(ma <= h){
			ma = h;
			ans++;
		}
	}
	cout << ans << endl;
}


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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << endl; exit(0); }
inline void no() { cout << "No" << endl; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); return a / gcd(a, b) * b; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { x = max(x, y); }
template <typename T> inline void amin(T &x, T y) { x = min(x, y); }
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

void solve() {
  string s;
  cin >> s;
  string t;
  rep(i, sz(s)) {
    if (s.substr(i, 2) == "BC") t += 'X', i++;
    else t += s[i];
  }
  int n = sz(t);
  i64 ans = 0;
  int acnt = 0;
  for (int l = 0; l < n; l++) {
    if (t[l] == 'A') acnt += 1;
    else if (t[l] == 'X') {
      ans += acnt;
    } else {
      acnt = 0;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 916
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <climits>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cassert>
#include <vector>
#define all(x) x.begin() , x.end()
#define fi first
#define se second
#define pb push_back
#define umax( x , y ) x = max( x , (y) )
#define umin( x , y ) x = min( x , (y) )
#define set multiset
#define null NULL
#define ort (b+s)/2

using namespace std;

typedef long long Lint;
typedef long double db;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef pair<db,db> dd;
typedef pair<int,string> is;

const int maxn = 600020;
const int K = 320;
const int MOd = 1e9 + 7;

Lint ar[maxn], a, k;
vector<Lint> v;

Lint f( Lint x ) {
	Lint ans = 0;
	for(int i=1;i<=a;i++) {
		if( ar[i] == 0 ) {
			if( 0 <= x )
				ans += a;
		} else if( ar[i] > 0 ) {
			Lint h = x/ar[i];
			// -3/4 || -4/4
			if( x < 0 && x%ar[i] != 0 ) h--;
			int t = upper_bound( all( v ), h ) - v.begin();
			ans += t;//printf("asdasd %lld\n",h);
		} else {
			// 4, -3
			Lint h = x/ar[i];
			// -3, -2
			if( x < 0 && (-x)%(-ar[i]) != 0 ) h++;
			int t = v.end()-lower_bound( all( v ), h );
			//printf("asd %lld\n",h);
			ans += t;
		}
		if( ar[i]*ar[i] <= x ) ans--;
		//printf("%d --> %d (%lld)\n",i,ans,ar[i]);
	}
	//printf("x=%lld --> ans=%lld\n",x,ans);
	return ans/2;
}

void solve() {
	scanf("%lld %lld",&a,&k);
	for(int i=1;i<=a;i++) {
		scanf("%lld",&ar[i]);
		v.pb( ar[i] );
	}
	sort( ar+1, ar+1+a );
	sort( all( v ) );
	Lint l = -1e18, r = 1e18;
	f(r);
	while( l < r ) {
		Lint m = (l+r)/2;
		if( l + 1 == r ) m = l;

		if( f( m ) < k ) l = m+1;
		else r = m;
	}
	cout << r << endl;
}

int main(  ) {


    int n = 1;
    //scanf("%d",&n);
    while( n-- ) solve();

    return 0;
}

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

void fnInput(int& rnDivisor)
{
  cin >> rnDivisor;
}

int fnDigit(int nDivisor)
{
  set<int> seRemain;

  int nDividend = 7;
  int nDigit = 1;
  int nRemain = nDividend % nDivisor;

  while ( seRemain.count(nRemain) == 0 )
  {
    seRemain.insert(nRemain);
    if (!nRemain)
      return nDigit;

    nDividend = nRemain * 10 + 7;
    nRemain = nDividend % nDivisor;
    nDigit++;
  }
  return -1;
}
 
int main()
{
  int nDivisor;

  fnInput(nDivisor);
  cout << fnDigit(nDivisor) << endl;

  return 0;
}

Measured memory_bytes: 50352
#include <stdio.h>

#define NMAX 100

int main() {
    int M[NMAX + 1][NMAX + 1];
    int n, k, a, b;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            M[i][j] = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &a, &k);
        for (int j = 0; j < k; j++) {
            scanf("%d", &b);
            M[a][b] = 1;
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            printf("%d%c", M[i][j], j == n ? '\n' : ' ');
    return 0;
}


Measured memory_bytes: 2768
#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部変数
static FILE *szpFpI;											// 入力

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpA;
	static int siTNo;
#endif

// １行出力
int
fOutLine(
	char *pcpLine				// <I> １行
)
{
	char lc1Buf[1024];

#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, pcpLine)) {
		siRes = -1;
	}
#else
	printf("%s", pcpLine);
#endif

	return 0;
}

// 実行メイン
int
fMain(
)
{
	int i;
	char lc1Buf[1024];

	// 文字列 - 取得
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);

	// 長さ・９以外有無 - 取得
	int liLen = 0;
	int liCnt = 0;
	for (i = 1; ; i++) {
		if ('0' <= lc1Buf[i] && lc1Buf[i] <= '8') {
			liCnt = 1;
		}
		else if (lc1Buf[i] != '9') {
			break;
		}
		liLen++;
	}

	return lc1Buf[0] - '0' + 9 * liLen - liCnt;
}

// １回実行
int
fOne(
)
{
	int liRet;
	char lc1Buf[1024];

	// 入力 - セット
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);
	szpFpI = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#else
	szpFpI = stdin;
#endif

	// 実行メイン
	liRet = fMain();

	// １行出力
	sprintf(lc1Buf, "%d\n", liRet);
	fOutLine(lc1Buf);

	// 残データ有無
#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, "")) {
		siRes = -1;
	}
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", siTNo);
	}
	else {
		printf("NG %d\n", siTNo);
	}
#endif

	return 0;
}

// プログラム開始
int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		siTNo = i;
		fOne();
	}
#else
	fOne();
#endif

	return 0;
}



Measured memory_bytes: 128
package main

import (
  "fmt"
  "sort"
)

func main() {
  var N, tmp int
  fmt.Scan(&N)

  var d []int

  for i := 0; i < N; i++ {
    fmt.Scan(&tmp)
    d = append(d, tmp)
  }

  sort.Sort(sort.Reverse(sort.IntSlice(d)))

  res := 1
  for i := 0; i < N - 1; i++ {
    if d[i] > d[i+1] {
      res += 1
    }
  }

  fmt.Println(res)

}


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

int main(){
  vector<int> p = { 5,7,5};
  sort(p.begin(), p.end());
  
  vector<int> q(3);
  for ( int i = 0; i < 3; i++) cin >> q.at(i);
  sort(q.begin(), q.end());
  
  int con = 0;
  for(int i = 0 ; i < 3; i++) if(p.at(i) == q.at(i)) con++;
  
  if(con == 3) cout << "YES";
  else cout << "NO";
}

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

using namespace std;
#define PROBLEM "C"

int pre[1000005];
int bk[1000005];
int arr[1000005];

int main(){

	#ifdef DBG
	freopen("problem" PROBLEM ".in", "r", stdin);
	freopen("problem" PROBLEM ".out", "w", stdout);
	#endif

	int N;
	cin >> N;
	for(int i = 0 ; i < N ; i++){

		cin >> arr[i];
	}
	pre[0] = arr[0];
	for(int i = 1 ; i < N ; i++){

		pre[i] = __gcd(pre[i-1], arr[i]);
	}
	bk[N-1] = arr[N-1];
	for(int i = N-2 ; i >= 0 ; i--){

		bk[i] = __gcd(bk[i+1], arr[i]);
	}
	int ans = 1;
	for(int i = 1 ; i < N ; i++){

		ans = max(__gcd(pre[i-1], bk[i+1]), ans);
	}
	ans = max(ans, max(bk[1], pre[N-2]));
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 8832
use proconio::{input, fastout};
use proconio::marker::{Chars};
use proconio::marker::Usize1;
use std::cmp::*;
use std::char::*;

macro_rules! debug {
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

#[fastout]
fn main() {
    input!{
        n: usize,
        s: [Chars;n],
    }

    let mut alpha: Vec<Vec<usize>> = vec![vec![0;26];n];
    for i in 0..n {
        for j in 0..s[i].len() {
            alpha[i][s[i][j] as usize - 'a' as usize] += 1;
        }
    }
    debug!(alpha);
    let mut ok: bool = true;
    let mut v = 100;
    for i in 0..26 {
        for j in 0..n {
            if alpha[j][i]!=0 {
                v = min(alpha[j][i],v);
            } else {
                ok = false;
                break;
            }
        }
        if ok {
            for k in 0..v {
                print!("{}", from_u32(i as u32 + 'a' as u32).unwrap());
            }
        }
        ok = true;
        v = 100;
    }

    print!("\n");
}


Measured memory_bytes: 2196
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 1000000000000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


typedef pair<ll,ll> P;

ll N,X,D;
map<ll,vector<P>> MAP;

int main(){

	scanf("%lld %lld %lld",&N,&X,&D);

	if(D == 0){

		if(X == 0){

			printf("1\n");

		}else{

			printf("%lld\n",N+1);
		}
		return 0;
	}

	for(ll i = 0; i <= N; i++){

		ll base = X*i;
		ll L = (i*(i-1))/2;
		ll R = (i*(2*N-(i+1)))/2;

		base += L*D;
		R -= L;

		MAP[(base+(D<<30))%D].emplace_back(base,R);
	}

	ll ans = 0;

	for(auto at: MAP){

		auto vec = at.second;
		int len = vec.size();

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

			vec[i].first = (vec[i].first-at.first)/D;
		}

		vector<P> event;

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

			event.emplace_back(vec[i].first,1);
			event.emplace_back(vec[i].first+vec[i].second+1,-1);
		}

		sort(event.begin(),event.end());

		ll count = 0,pre = -HUGE_NUM;

		for(auto e: event){

			ll add = e.first-pre;
			if(count > 0)ans += add;
			count += e.second;
			pre = e.first;
		}
	}

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

	return 0;
}


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

using namespace std;
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os;}
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}

void solve() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }


    vector<int> ans;
    vector<int> flag(N);
    for(int i = 0; i < N; i++) {
        vector<int> temp(N);
        int c = 0;
        for(int j = 0; j < N; j++) {
            if (!flag[j]) temp[j] = ++c;
        }

        for(int j = N - 1; j >= 0; j--) {
            if (!flag[j] && A[j] == temp[j]) {
                flag[j] = 1;
                ans.push_back(A[j]);
                break;
            }
        }
    }
    if (ans.size() != N) {
        cout << -1 << endl;
        return;
    } else {
        reverse(all(ans));
        for (int i = 0; i < N; i++) {
            cout << ans[i] << endl;
        }
    }
}

int main() {
    #ifdef LOCAL_ENV
    cin.exceptions(ios::failbit);
    #endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    
    solve();
}

Measured memory_bytes: 256
object Main extends App {
    val queue = scala.collection.mutable.Queue[(String, Int)]()
    io.Source.stdin.getLines.foreach(a => {
        val b = a.split(" ")
        queue.enqueue((b(0), b(1).toInt))
    })
    val (_, q) = queue.dequeue
    var tm = 0
    while (!queue.isEmpty) {
        val (n, t) = queue.dequeue
        if (t-q <= 0) {
            tm += t
            println(n + " " + tm)
        } else {
            tm += q
            queue.enqueue((n, t-q))
        }
    }
}

Measured memory_bytes: 116564
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ll n;
    cin>>n;
    ll m = sqrt(n);
    for(ll i=m; i>=1; i--)
    {
        if(n%i==0)
        {
            m=n/i;
            ll sum = (i-1)+(m-1);
            cout<<sum<<endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL));
#define MOD 1000000007 
#define INF LONG_LONG_MAX
#define MINF LONG_LONG_MIN


ll po(ll x,ll n){
    if(n==0) return 1;
    else if(n%2 == 0) return po((x*x)%MOD,n/2);
    else return (x*po((x*x)%MOD,(n-1)/2))%MOD;
}

void solve(){
    ll n;
    cin>>n;
    ll a[n];
    for( int i=0;i<n;i++ ) cin>>a[i];
    ll freq[n+1] = {0};
    for( int i=0;i<n;i++ ) freq[a[i]]++;
    ll ans = 0;
    for( int i=1;i<=n;i++ ){
        ans += (( freq[i] )*( freq[i] - 1 ))/2;
    }
    for( int i=0;i<n;i++ ){
        cout<<ans - ( freq[a[i]] - 1 )<<endl; 
    }
    return;
}

int main(){
    FAST;
    //init();
    ll t = 1;
    //cin>>t;
    while( t-- ) solve();
    return 0;
} 

Measured memory_bytes: 5760
#include<iostream>
#include<cassert>
#include<stdexcept>
#include<utility>
#include<functional>
#include<numeric>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<array>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<complex>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<bitset>
using namespace std;
using ll=long long;

const ll MOD=1e9+7;

int main(){
    ll n,k;
    cin>>n>>k;
    vector<ll> b;
    {   
        set<ll> s;
        for(int i=1;i<=min((ll)(sqrt(n)+1),n);i++){
            s.insert(n/i);
        }
        for(int i=1;i<=min(ll(sqrt(n))+1,n);i++){
            s.insert(i);
        }
        b=vector<ll>(s.begin(),s.end());
    }
    if(*min_element(b.begin(),b.end())<=0) return 0;
    int m=b.size();
    vector<vector<ll>> dp(k+1,vector<ll>(m,0));
    dp[0][m-1]=1;
    for(int i=0;i<k;i++){
        vector<ll> sum(m+1);
        for(int j=0;j<m;j++){
            sum[j+1]=(sum[j]+dp[i][j])%MOD;
        }
        vector<ll> wsum(m+1);
        for(int j=0;j<m;j++){
            wsum[j+1]=(wsum[j]+b[j]*dp[i][j])%MOD;
        }
        for(int j=0;j<m;j++){
            ll lb=n/(b[j]+1);
            ll ub0=n/b[j];
            int id=(lower_bound(b.begin(),b.end(),ub0)-b.begin());
            int idl=(lower_bound(b.begin(),b.end(),lb)-b.begin());
            if(id>=lb) dp[i+1][j]+=wsum[id]-wsum[idl]-lb*(sum[id]-sum[idl]);
            dp[i+1][j]%=MOD;
            dp[i+1][j]+=(ub0-lb)*(sum[m]-sum[id]);
            dp[i+1][j]=(dp[i+1][j]%MOD+MOD)%MOD;
        }
    }
    cout<<accumulate(dp[k].begin(),dp[k].end(),0LL)%MOD<<endl;
    return 0;
}

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

//#include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;
// using cint = cpp_int;
//#define input(a) scanf("%lld", &(a))
//#define output(a) printf("%lld\n", (a))

// Define
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const ll MOD = 1e9 + 7;
const ll INF = LONG_MAX;
const ull MAX = ULONG_MAX;
#define endl '\n'
#define space ' '
#define def inline auto
#define func inline constexpr ll
#define run __attribute__((constructor)) def _
#define all(v) begin(v), end(v)

// Debug
#define debug(...)                                                             \
    {                                                                          \
        cerr << __LINE__ << ": " << #__VA_ARGS__ << " = ";                     \
        for (auto &&X : {__VA_ARGS__}) cerr << "[" << X << "] ";               \
        cerr << endl;                                                          \
    }

// Loop
#define inc(i, a, n) for (ll i = (a), _##i = (n); i <= _##i; ++i)
#define dec(i, a, n) for (ll i = (a), _##i = (n); i >= _##i; --i)
#define each(i, a) for (auto &&i : a)
#define rep(i, n) inc(i, 0, n - 1)

// Stream


// Math
func gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
func lcm(ll a, ll b) { return a * b / gcd(a, b); }

def input() {
    ll A;
    cin >> A;
    return A;
}

ll N, M, S, L;
vector<vector<bool>> A(1000);

signed main() {
    ll n, m, a = 1, b = 1;
    cin >> n >> m;
    if(abs(n - m) > 1) {
        cout << 0 << endl;
        return 0;
    }
    rep(i, n) { a *= i + 1; a %= MOD; }
    rep(i, m) { b *= i + 1; b %= MOD; }
    if(n == m) a *= 2;
    cout << (a * b) % MOD << endl;
}

// for compilation: g++ -Ofast -march=native -o _ _.cpp -std=c++17

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define clr(x) memset(x, 0, sizeof(x))
#define sz(x) (int)x.size()

using namespace std;

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

const ll mx = 105;
const ll maxn = 1000001;
const ll mod = 1000000007;

vector<vector<int>> adj;
vector<ll> lis;


int main(){
       
 
  ll t = 1;

  //cin>>t;

  while(t--){
     ll n, i, j ,k;
     
     string s;

     cin>>s;

     ll res = 0;

    //  map<ll, ll> m;

     ll cur = 0;
    // m[0] = 1;

    ll rem[2019], rem1[2019];
    clr(rem);
    rem[0] = 1;

     for(i =0 ;i < sz(s);i++){
       
  
      clr(rem1);
       for(j = 0;j < 2019;j++){
           ll te = (j*10)%2019, te1 = rem[j];
        //    rem[j] = 0;
        //    rem[te] = te1;   
          rem1[te] += te1;
          
       }
         for(j = 0;j < 2019;j++){
          rem[j] = rem1[j];
          
       }
          cur = (cur*10 + (s[i]-48))%2019;
          res += rem[cur];
     //     cout<<rem[cur]<<" "<<i<<"\n";
          rem[cur]++;

         
     }
     cout<<res<<"\n";
    
  }     
        
}


Measured memory_bytes: 3756
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
import random
import time
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

start = time.time()
TL = 1.6
D = INT()
C = LIST()
s = [LIST() for _ in range(D)]

def compute_score(out):
    score = 0
    last = [0]*26

    for d in range(D):
        last[out[d]] = d+1
        for i in range(26):
            score -= (d+1-last[i])*c[i]
        score += s[d][out[d]]

    return score

def decrease(d, j):  # d:日にち, j:開催するコンテスト
    tmp = 0
    for i in range(26):
        if i == j: continue
        tmp += C[i]*(d-last[i])
    return tmp 

def init():  # 貪欲でとった解を1度保存する
    global now
    for i in range(D):  # i+1日目
        ma = -INF
        ma_idx = None
        for j in range(26):  # 開催するコンテスト
            tmp = now
            tmp += s[i][j]
            tmp -= decrease(i+1, j)
            if tmp > ma:
                ma = tmp
                ma_idx = j
        now = ma
        last[ma_idx] = i+1
        score[ma_idx] += s[i][ma_idx]
        for j in range(26):
            score[j] -= C[j]*(i+1-last[j])
        last[ma_idx] = i+1
        ans[i] = ma_idx+1

def update(d, q):  # d日目のところをqに変更する
    d -= 1
    q -= 1
    c = ans[d]-1  # c:更新前
    ans[d] = q+1
    last_c = 0
    last_q = 0
    score_c = 0
    score_q = 0
    for j in range(D):
        if ans[j]-1 == c:
            last_c = j+1
            score_c += s[j][c]
        elif ans[j]-1 == q:
            last_q = j+1
            score_q += s[j][q]
        score_c -= C[c] * (j+1 - last_c)
        score_q -= C[q] * (j+1 - last_q)
    score[c] = score_c
    score[q] = score_q

def swap(d):  # d日目とd+1日目の開催を入れ替える
    update(d, ans[d])
    update(d+1, ans[d-1])

ans = [0]*D
last = [0]*26
score = [0]*26
now = 0

init()

randint = random.randint
rand = random.random
while time.time() - start < TL:
    if rand() < 0.5:  # 1点変更
        d = randint(1, D)
        q = randint(1, 26)
        old = ans[d-1]
        old_score = score.copy()
        update(d, q)
        if sum(score) <= sum(old_score):
            score = old_score
            ans[d-1] = old
    else:  # 2点入れ替え
        d = randint(1, D-1)
        old = ans[d-1]
        old_score = score.copy()
        swap(d)
        if sum(score) <= sum(old_score):
            score = old_score
            ans[d-1] = old

print(*ans, sep="\n")


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

int main(){
    int N;
    cin >> N;
    ll ans =0;
    ll aend =0;
    ll bstart =0;
    ll aendbstart =0;
    for(int i=0;i<N;i++){
        string s;
        cin >> s;
        if(s[0] == 'B'){
            bstart++;
        }
        if(s[s.size()-1] == 'A'){
            aend++;
        }
        if(s[0] == 'B' && s[s.size()-1] == 'A'){
            aendbstart++;
        }
        for(int j=0;j<s.size()-1;j++){
            if(s[j] == 'A' &&s[j+1] =='B'){
                ans++;
            }
        }
    }
    if(aendbstart ==0){
        cout << ans + min(bstart,aend) << endl;
        return 0;
    }
    
    bstart -= aendbstart;
    aend -= aendbstart;
    ans += (aendbstart-1);
    if(aend >0){
        ans++;
        aend--;
    }
    if(bstart >0){
        ans++;
        bstart--;
    }
    cout << ans + min(bstart,aend)<< endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>
#include <fstream>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9 + 7);

int main(void) {
	string s;
	cin >> s; 
	
	int n = (int)s.size();
	int cnt = 0;
	vector<int> ans(n, 0);
	
	for(int i = 0; i < n; ++i) {
		if( s[i] == 'R' ) {
			cnt++;
		} else {
			ans[i] += cnt / 2;
			ans[i - 1] += (cnt + 1) / 2;
			cnt = 0;
		}
	}
	
	cnt = 0;
	
	for(int i = n - 1; i >= 0; --i) {
		if( s[i] == 'L' ) {
			cnt++;
		} else {
			ans[i] += cnt / 2;
			ans[i + 1] += (cnt + 1) / 2;
			cnt = 0;
		}
	}
	for(int i = 0; i < n; ++i) {
		cout << ans[i];
		
		if( i < n - 1 ) cout << " ";
	}
	
	cout << endl;
	
	return 0;
}


Measured memory_bytes: 3844
#include <bits/stdc++.h>
#include<iostream>
#include <algorithm>
#include<stdio.h>
#include<string.h>
#include <unordered_map>
#include <map>
#include <unordered_set>
#include<vector>
using namespace std;
#define fr(i,j,n)   for(int i=j;i<(n);++i)
#define bk(i,j,n)   for(int i=j;i>=n;--i)
#define pb push_back
#define mp make_pair
#define Fs first
#define Sc second
#define endl "\n"
#define MOD 1000000007
#define run ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ordered_set tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long int lli;

int main()
{
    int n,m;
  cin>>n>>m;
  if(n==m)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
}

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

using namespace std;

using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PIL = pair<int, LL>;
using PLL = pair<LL, LL>;
// const int mod = 1e9 + 7;

#define MEM(a, b) memset(a, b, sizeof(a))
#define REP(i, a) for (int i = 0; i < a; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define ALL(a) a.begin(), a.end()

inline void quickread() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

inline void print_vector(vector<int> &A){
    for (auto&& x : A){
        cout << x << " ";
    }
    cout << endl;
}

inline void print_array(const int A[], int n) {
    REP(i, n) {
        cout << A[i] << " ";
    }
    cout << endl;
}

void solve() {
    int h1, m1, h2, m2, k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;

    cout << (h2 - h1) * 60 + (m2 - m1) - k << endl;
}

int main() {
    // freopen("input.txt", "r", stdin);
    quickread();

    int t = 1;

    // cin >> t;

    for (int _ = t; _ > 0; _--) {
        solve();
    }

    return 0;
}


Measured memory_bytes: 3644
h, w = map(int, input().split())
a = []



for i in range(h):
  l = input()
  if '#' in l:
    a.append(l)
    
z = [False] * w

for i in range(w):
  for l in a:
    if l[i] == '#':
      z[i] = True
      break
    


for j, _ in enumerate(a):
  for i in range(w) :
    if z[i]:
      print(_[i], end='')
  if j == len(a) -1:
    break
  print('')

Measured memory_bytes: 4468
#include <stdio.h>

int main(void) {
  long long n, m, i, max = 0;
  scanf("%lld%lld", &n, &m);
  max = m;
  for(i = 0; i < n; ++i) {
    int s, d;
    scanf("%d%d", &s, &d);
    m += s - d;
    if(m < 0) {
      printf("0\n");
      return 0;
    }
    if(max < m) max = m;
  }
  printf("%lld\n", max);
  return 0;
}


Measured memory_bytes: 2712
n=int(input())
l=list(map(int,input().split()))
l=sorted(l)
cnt=0
for i in range(0,n-2):
	for j in range(i+1,n-1):
		for k in range(j+1,n):
			if l[i]+l[j]>l[k] and l[i]!=l[j] and l[i]!=l[k] and l[j]!=l[k]:
				cnt+=1
print(cnt)
			

Measured memory_bytes: 9136
#include <iostream>
#include <algorithm>
#include <set>
#include <map>

using namespace std;

int N;
long long int T;
long long int A[100005];

int  COUNT(long long int k) {
	int ret = 0;
	for (int i = 1; i <= N; i++) {
		if (A[i] == k) { ret++; }
	}
	return ret;
}

long long int M[100005], m[100005];

set<pair<long long int, long long int> > S;

map<long long int, int> C;

int main(void) {

	cin >> N >> T;

	long long int tmp;
	for (int i = 1; i <= N; i++) {
		cin >> tmp; A[i] = tmp;
	}

	M[N] = A[N];
	for (int i = N-1; i >= 1; i--) {
		M[i] = max(M[i + 1], A[i]);
	}

	m[1] = A[1];
	for (int i = 2; i <= N; i++) {
		m[i] = min(m[i - 1], A[i]);
	}

	long long int SUB = -1;

	for (int i = 1; i <= N; i++) {
		SUB = max(SUB, M[i] - m[i]);
	}

	for (int i = 1; i <= N; i++) {
		if (M[i] - m[i] == SUB) { S.insert(pair<long long int, long long int>(M[i], m[i])); }
	}

	for (int i = 1; i <= N; i++) {
		C[A[i]]++;
	}

	long long int ans = 0;
	for (auto it = S.begin(); it != S.end(); it++) {
		long long int a = (*it).first; 
		long long int b = (*it).second;
		ans += min(C[a], C[b]);
	}
	cout << ans << endl;
	//system("pause");
	return 0;
}


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

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

    vector<int> box(N, 1);
    vector<bool> f(N, false);
    f[0] = true;

    for (int i = 0; i < M; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        box[x]--, box[y]++;
        if (f[x]) f[y] = true;
        if (!box[x]) f[x] = false;
    }

    int ans = 0;
    for (int i = 0; i < N; i++) ans += f[i];
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 640
n=int(input())
a=[int(input()) for _ in range(n)]
def main(n,a):
  pre=0
  ans=0
  for x in a:
    if pre+2<=x:
      # pre+1以上の数値を何回か引き算してxを1以上pre以下にする
      # 引き算の回数はなるべく多く
      if x%(pre+1)==0:
        tmp=x//(pre+1)
        ans+=tmp-1
        pre=max(pre,1)
      else:
        tmp=x//(pre+1)
        ans+=tmp
        pre=max(pre,x%(pre+1))
    else:
      pre=max(pre,x)
  print(ans)
main(n,a)


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

struct UnionFind
{
    vector<int> d;
    UnionFind(int n) : d(n, -1) {}

    // find
    int find(int x)
    {
        if (d[x] < 0)
            return x;

        return d[x] = find(d[x]); // 更新（メモ化）
    }

    // union
    int unite(int x, int y)
    {
        // 根同士を連結する
        x = find(x);
        y = find(y);

        // 同じ連結成分であればfalse
        if (x == y)
            return false;

        if (d[x] > d[y])
        {
            swap(x, y);
        }

        d[x] += d[y];
        d[y] = x;

        return true;
    }

    // same
    bool same(int x, int y)
    {
        return (find(x) == find(y));
    }

    //size
    int size(int x)
    {
        return abs(d[find(x)]);
    }
};

int main()
{
    int n, m, k;
    cin >> n >> m >> k;

    int friends[n];
    fill_n(friends, n, 0);
    UnionFind uf = UnionFind(n);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        friends[a]++;
        friends[b]++;
        uf.unite(a, b);
    }

    vector<int> ng[n];
    for (int i = 0; i < k; i++)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        ng[a].push_back(b);
        ng[b].push_back(a);
    }

    for (int i = 0; i < n; i++)
    {
        int ans = uf.size(i) - 1 - friends[i];
        for (int b : ng[i])
        {
            if (uf.same(i, b))
                ans--;
        }

        cout << ans << " ";
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 6784
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <cmath>
#include <stack>

using namespace std;
using ll = long long int;

template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
  for (auto i = v.begin(); i != v.end(); i++) {
    os << *i << " ";
  }
  return os;
}


void solve(long long H, long long W, std::vector<std::string> S){
  vector<vector<pair<ll, ll>>> v(H, vector<pair<ll, ll>>(W));
  for(ll i=0; i<H; i++) {
    for(ll j=0; j<W; j++) {
      v[i][j] = make_pair(0, 0);
    }
  }
  for(ll i=0; i<H; i++) {
    ll cnt = 0;
    for(ll j=0; j<W; j++) {
      if(S[i][j]=='#') {
	cnt = 0;
      } else {
	cnt++;
	v[i][j].first = cnt;
      }
    }
    cnt = 0;
    for(ll j=W-1; j>=0; j--) {
      if(v[i][j].first>cnt) {
	cnt = v[i][j].first;
      } else if(S[i][j]=='.'){
	v[i][j].first = cnt;
      } else {
	cnt = 0;
      }
    }
  }
  for(ll i=0; i<W; i++) {
    ll cnt = 0;
    for(ll j=0; j<H; j++) {
      if(S[j][i]=='#') {
	cnt = 0;
      } else {
	cnt++;
	v[j][i].second = cnt;
      }
    }
    cnt = 0;
    for(ll j=H-1; j>=0; j--) {
      if(v[j][i].second >cnt)
    	cnt = v[j][i].second;
      else if(S[j][i]=='.')
    	v[j][i].second = cnt;
      else
    	cnt = 0;
    }
  }
  ll m = -1;
  for(ll i=0; i<H; i++) {
    for(ll j=0; j<W; j++) {
      m = max(m, v[i][j].first+v[i][j].second-1);
    }
  }
  std::cout << m << std::endl;
  // for(ll i=0; i<H; i++) {
  //   for(ll j=0; j<W; j++) {
  //     std::cout << "("<< v[i][j].first << ", " << v[i][j].second << ")" << " ";
  //   }
  //   std::cout  << std::endl;
  // }

}

int main(){
  long long H;
  scanf("%lld",&H);
  long long W;
  scanf("%lld",&W);
  std::vector<std::string> S(H);
  for(int i = 0 ; i < H ; i++){
    std::cin >> S[i];
  }
  solve(H, W, std::move(S));
  return 0;
}



Measured memory_bytes: 66944
#include <stdio.h>
int main()
{

  int W,H,x,y,r;
  scanf("%d%d%d%d%d",&W,&H,&x,&y,&r);
  if(0<=x&&0<=y&&y+r<=H&&x+r<=W&&0<=y+r&&0<=x+r) printf("Yes\n");
  else if(x<0||y<0||y+r>H||x+r>W||y+r<0||x+r<0) printf("No\n");
  
  return 0;
}

Measured memory_bytes: 584
#include<stdio.h>

int main(void)
{
 char c;
 scanf("%c",&c);
 if     (c=='A') printf("T\n");
 else if(c=='T') printf("A\n");
 else if(c=='C') printf("G\n");
 else if(c=='G') printf("C\n");
 return 0;
}

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

#define rep(i, s, n) for(int i = s; i < n; ++i)
#define rrep(i, n) for(int i = n - 1; i > -1; --i)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
const long long INF = 1000000000;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<int, int> P;

int main() {
    int n, m;
    cin >> n >> m;
    cout << (n * (n - 1)) / 2 + (m * (m - 1)) / 2 << endl;
}


Measured memory_bytes: 256
"use strict";

const main = arg => {
    const input = arg.trim().split("\n");

    const s = input[0];
    const t = input[1];
    const ta = t.slice(0, t.length-1)
    if(ta == s){
        console.log("Yes")
    } else {
        console.log("No")
    }
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));  

Measured memory_bytes: 29440
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) sort(v.begin(), v.end())
typedef long long ll;
using Graph = vector<vector<int>>;

int main()
{
  long double a, b, c, d;
  cin >> a >> b >> c >> d;
  long double e = a * c;
  long double f = b * d;
  long double g = a * d;
  long double h = b * c;
  long double i = max(max(e, f), max(g, h));
  cout << fixed << setprecision(0) << i << endl;
  //printf("%llf%d", i);
}


Measured memory_bytes: 3808
#include <algorithm>
#include <bitset>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int N, W; cin >> N >> W;
  vector<int> w(N), v(N); REP(i, N) cin >> w[i] >> v[i];
  vector<long long> dp(W+1, 0);
  REP(i, N) for (int j = W; j >= w[i]; --j) dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
  cout << dp[W] << '\n';
  return 0;
}


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



int main() {
  ll n;
  cin >> n;
 
  vector<pair<ll,int>> fs;
  for (ll i = 2; i*i <= n; ++i) {
    int x = 0;
    while (n%i == 0) {
      n /= i;
      ++x;
    }
    fs.emplace_back(i,x);
  }
  if (n != 1) fs.emplace_back(n,1);
 
  int ans = 0;
  for (auto p : fs) {
    int x = p.second;
    int b = 1;
    while (b <= x) {
      x -= b;
      b++;
      ++ans;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 19756
import sys
input = sys.stdin.buffer.readline
N, L = map(int, input().split())
a = list(map(int, input().split()))
res = []
for i in range(N - 1):
  if a[i] + a[i + 1] >= L:
    res.append(i + 1)
    break
if len(res):
  i = res[0] - 1
  while i > 0:
    res.append(i)
    i -= 1
  i = res[0] + 1
  while i < N:
    res.append(i)
    i += 1
  print("Possible")
  for i in range(N - 2, -1, -1):
    print(res[i])
else:
  print("Impossible")

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

int main() {
	double r;
	cin >> r;
	double A, C;
	A = r * r * M_PI;
	C = 2 * r * M_PI;
	cout << fixed << setprecision(6) << A << ' ' << fixed << setprecision(6) << C << endl;
}




Measured memory_bytes: 3276
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>

using namespace std;


vector<string> field;
pair<int,int> start;
pair<int,int> factory[10];
int h,w,n;

const int INF = 100000000;

// £Ì×ÚXg
int d[10][10];

// Ú®Ê
const int dy[] = {-1,0,0,1};
const int dx[] = {0,-1,1,0};

// ø«Å^¦çê½ê©çDæTõðs¤
void bfs(int idx){
	queue<pair<int,int> > *prv = new queue<pair<int,int> >();
	queue<pair<int,int> > *nxt = new queue<pair<int,int> >();

	// ÊßÏÝÌêði[
	bool passed[1001][1001];
	// falseÅú»
	for(int i = 0; i < 1001; i++)
		fill(passed[i],passed[i]+1001,false);
	// ÅÌê
	prv->push(factory[idx]);

	int dist = 0;
	// TõJn
	while(prv->size()){
		while(prv->size()){
			// ¡ñÌê
			pair<int,int> place = prv->front();prv->pop();
			if(passed[place.first][place.second]){
				continue;
			}

			//ÊßÏÝÉ·é
			passed[place.first][place.second] = true;

			// £ðXV
			if(field[place.first][place.second] == 'S'){
				d[idx][0] = dist;
			}
			else if(field[place.first][place.second] >= '0' && field[place.first][place.second] <= '9'){
				d[idx][field[place.first][place.second] - '0'] = dist;
			}

			// Ú®
			for(int i = 0; i < 4; i++){
				// Ú®æ
				pair<int,int> np = place;
				np.first += dy[i];
				np.second += dx[i];
				if(np.first >= 0 && np.second >= 0 && np.first < h && np.second < w){
					// áQ¨ÅÈ¢êAÚ®
					if(field[np.first][np.second] != 'X' && !passed[np.first][np.second]){
						nxt->push(np);
					}
				}
			}
		}
		dist++;
		// obt@¢ê©¦
		swap(prv,nxt);
	}
}



int main(){

	while(cin >> h >> w >> n){
		for(int i = 0; i < h; i++){
			string str;
			cin >> str;
			field.push_back(str);
			for(int j = 0; j < str.size(); j++){
				// X^[gn_ðL^µÄ¨­
				if(field[i][j] == 'S'){
					factory[0].first = i;
					factory[0].second = j;
				}
				// HêÌêðL¯
				else if(field[i][j] >= '1' && field[i][j] <= '9'){
					factory[field[i][j]-'0'] = make_pair(i,j);
				}
			}
		}
		for(int i = 0; i < 10; i++)
			fill(d[i],d[i]+10,INF);

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

		vector<int> s;
		for(int i = 1; i <= n; i++)
			s.push_back(i);

		int minCost = INF;
		do{
			bool f = false;
			int sum = 0;
			for(int i = 0; i < s.size(); i++){
				if(s[i] <= i + 1){
					if(i == 0){
						sum += d[0][s[i]];
					}
					else{
						sum += d[s[i-1]][s[i]];
					}
				}
				else{
					f = true;
					break;
				}
			}
			if(!f){
				minCost = min(minCost,sum);
			}
		}while(next_permutation(s.begin(),s.end()));
		cout << minCost << endl;
	}

	return 0;
}

Measured memory_bytes: 2892
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define repr(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define repr_inv(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
#define rep(i,n) repr(i,0,n)
#define INF 2000000000
#define INFLL 9000000000000000000
using namespace std;
int main(void)
{
	int a, b, c, d, e, f, water, suger;

	double max=-1, rate;

	cin>>a>>b>>c>>d>>e>>f;

	rep(x1, 3000/(100*a)+1){
		rep(x2, 3000/(100*b)+1){
			if(100*a*x1+100*b*x2>f) break;
			rep(x3, 3000/c+1){
				if(100*a*x1+100*b*x2+c*x3>f||c*x3>(a*x1+b*x2)*e) break;
				rep(x4, 3000/d+1){
					if(100*a*x1+100*b*x2+c*x3+d*x4>f||c*x3+d*x4>(a*x1+b*x2)*e) break;
					rate=(double)(c*x3+d*x4)/(double)(100*a*x1+100*b*x2+c*x3+d*x4);
					if(max<rate&&100*a*x1+100*b*x2!=0){
						max=rate; water=100*a*x1+100*b*x2; suger=c*x3+d*x4;
					}
				}
			}
		}
	}
	cout<<water+suger<<" "<<suger<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
//[1, n)
ll count(ll n){
  ll res = 0;
  ll cnt = 1;
  ll p = 1;
  while(!(p * 10 > n)){
    ll less3 = (p * 10 - 1)/3 - (p - 1)/3;
    ll less5 = (p * 10 - 1)/5 - (p - 1)/5;
    ll less15 = (p * 10 - 1)/15 - (p - 1)/15;
    res += ((p * 10 - 1) - p + 1 - less3 - less5 + less15) * cnt;
    res += (less3 - less15) * 4;
    res += (less5 - less15) * 4;
    res += less15 * 8;
    p *= 10;
    cnt += 1;
  }
  // 1 ... p - 1
  // p <= n < p * 10
  ll less3 = (n - 1)/3 - (p - 1)/3;
  ll less5 = (n - 1)/5 - (p - 1)/5;
  ll less15 = (n - 1)/15 - (p - 1)/15;
  res += ((n - 1) - p + 1 - less3 - less5 + less15) * cnt;
  res += (less3 - less15) * 4;
  res += (less5 - less15) * 4;
  res += less15 * 8;
  //cout<<n<<" : "<<res<<endl;
  return res;
}
int countdig(int n){
  stringstream ss;
  ss<<n;
  return ss.str().size();
}
string solve(ll n){
  ll b = 0, f = 100000000000000000LL;
  while(f - b > 1){
    ll mid = (f + b) / 2;
    if(count(mid) < n){
      b = mid;
    }else{
      f = mid;
    }
  }
  ll rest = n - count(b);
  //cout<<"n: "<<n<<" b:"<<b<<" rest:"<<rest<<endl;
  string s;
  for(ll i = b; s.size() < rest + 20; i++){
    if(i % 15 == 0) s+= "FizzBuzz";
    else if(i % 3 == 0) s += "Fizz";
    else if(i % 5 == 0) s+= "Buzz";
    else {
      stringstream ss;
      ss << i;
      s += ss.str();
    }
  }
  return s.substr(rest - 1, 20);
}

int main(){
  ll n;
  while(cin>>n){
    cout<<solve(n)<<endl;
  }
  return 0;
}

Measured memory_bytes: 1224
l = [int(_) for _ in input().split()]
a, b, c = sorted(l, reverse=True)
if a % 2 == 1:
    if b % 2 == 1:
        if c % 2 == 1:
            ans = (a-b)//2 + (a-c)//2
        else:
            ans = 1 + (a+1-c)//2 + (a-b)//2
    else:
        if c % 2 == 1:
            ans = 1 + (a+1-b)//2 + (a-c)//2
        else:
            ans = 1 + (a-b-1)//2 + (a-c-1)//2
else:
    if b % 2 == 1:
        if c % 2 == 1:
            ans = 1 + (a-b-1)//2 + (a-c-1)//2
        else:
            ans = 1 + (a+1-b)//2 + (a-c)//2
    else:
        if c % 2 == 1:
            ans = 1 + (a-b)//2 + (a+1-c)//2
        else:
            ans = (a-b)//2 + (a-c)//2
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d",&x);
#define scs(x) scanf("%s",x);
#define scl(x) scanf("%lld",&x);
#define rep(i,s,e) for(int i=s; i<=e; ++i)
#define dep(i,s,e) for(int i=s; i>=e; --i)
typedef long long ll;
using namespace std;
const ll mod=998244353;
int main()
{
	int n;
	sc(n);
	int v=n%10;
	if(v==3){
		pf("bon\n");
	}else if(v==0||v==1||v==6||v==8){
		pf("pon\n");
	}else {
		pf("hon\n");
	}
}


Measured memory_bytes: 3688
#include<stdio.h>
#define MAXSIZE 200000
typedef struct data{
	char name[10];
	int time;
}Process;

Process Queue[MAXSIZE];
int bp=0,fp=0;

void push(Process p){
	Queue[bp]=p;
	bp++;
	if(bp == MAXSIZE)bp=0;
}
Process pop(){
	Process p = Queue[fp];
	fp++;
	if(fp == MAXSIZE)fp=0;
	return p;
}


int main(){
	int i,n,q,times;
	Process p;
	scanf("%d %d",&n,&q);
	
	for(i=0;i<n;i++){
		scanf("%s %d",&p.name,&p.time);
		push(p);
	}
	times = 0;
	while(1){
		p = pop();
		times += q;
		p.time -=  q;
		if(p.time<=0){
			printf("%s %d\n",p.name,(times+p.time));
			times += p.time;
		}
		else push(p);
		if(bp == fp)break;
	}
	
	
	return 0;
}

Measured memory_bytes: 4808
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	long long int n;
	cin>>n;
	long long int ans = n*(n-1)/2;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define INF 0x6fffffff
#define INFL 0x6fffffffffffffffLL

int main() {
	ll		a,b,c,d,w,h,i,j,k,m,n,x,y,z;
	ll		ans = 0;
	string	s;
	cin >> n;
	vector<ll>	l(n),ll(3);
	for(i=0;i<n;i++) cin >> l[i];
	for(i=0;i<n-2;i++) {
		for(j=i+1;j<n-1;j++) {
			for(k=j+1;k<n;k++) {
				a=ll[0]=l[i];
				b=ll[1]=l[j];
				c=ll[2]=l[k];
				sort(ll.begin(),ll.end());
				if (a==b||b==c||a==c) continue;
				if (ll[2]<ll[0]+ll[1]) ans++;
			}
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3628