akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#define REP(i,n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

const int MAX_N = 100100;

//隣接リストでもつ
struct edge {
    int to; 
    int cost;
    edge(int to, int cost) : to(to), cost(cost) {};
}; 
vector<vector<edge> > G(MAX_N, vector<edge>());
void add_edge(int from, int to, int cost) {
    G[from].push_back(edge(to, cost));
    G[to].push_back(edge(from, -cost)); 
}

vector<bool> used(MAX_N, false);
vector<int> x(MAX_N, 0); // 初期値:0, 二色:-1,+1
bool dfs(int v, int y) {
    used[v] = true;
    x[v] = y;
    for(int i = 0; i < (int)G[v].size(); ++i) { //頂点vから出る各辺を走査
        edge e = G[v][i];
        if (used[e.to] == true && x[e.to] != x[v] + e.cost) { //ちぐはぐなポテンシャルあったらダメ
            return false;
        } 
        if(used[e.to] == false) { //塗ってないときは再起に入る
            bool flag = dfs(e.to, x[v] + e.cost); //次の点を逆の色で塗る
            if (!flag) {
                return false;
            }
        }
    }
    return true; //全部色塗ってうまく出てきたらtrueを返す
}

int main() {
    int N,M; cin >> N>>M; 
    for (int i = 0; i < M; ++i) {
        int a,b,c; cin>>a>>b>>c;
        add_edge(a, b, c);
    }
    for (int i = 0; i < N; i++) {
        if (used[i] == false) {
            bool flag = dfs(i, 0);
            if (!flag) {
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}




Measured memory_bytes: 12032
#include <algorithm>
#include <cassert>
#include <cctype>
#include <chrono>
#define _USE_MATH_DEFINES
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#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, MOD = 1000000007;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*-----------------------------------------*/
long long f(long long n) {
  if (n == 0) return 0;
  if (n % 4 == 0) return n;
  if (n % 4 == 1) return 1;
  if (n % 4 == 2) return n + 1;
  return 0;
}

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

  long long a, b; cin >> a >> b;
  cout << (f(a - 1) ^ f(b)) << '\n';
  return 0;
}


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


int main(){
    int len=0,i,count=0;

    char a[500000],b[500000];

    scanf("%s",a);
    scanf("%s",b);
    len=strlen(a);

    for(i=0;i<len;i++){
        if(strncmp(a,b,i+1)==0){
            
        }else{
           
            count++;
            a[i]=b[i];
        }
    }
    printf("%d",count);

    


    return 0;
}

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

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

    int ans = 0;
    while(n > 0) {
        n /= k;
        ++ans;
    }

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

Measured memory_bytes: 256
#include<stdio.h>

static const int N = 1000;

void trace(int A[], int n){
  int i;
  for ( i = 1; i <= n; i++ ){
    if ( i > 1 ) printf(" ");
    printf("%d", A[i]);
  }
  printf("\n");
}

int main(){
  int n, i, j;
  int A[N+1];
  scanf("%d", &n);

  for ( i = 1; i <= n; i++ ) scanf("%d", &A[i]);
  
  trace(A, n);
  for ( j = 2; j <= n; j++ ){
    int key = A[j];
    int i = j - 1;
    while( i > 0 && A[i] > key ){
      A[i+1] = A[i];
      i--;
    }
    A[i+1] = key;

    trace(A, n);
  }

  return 0;
}


Measured memory_bytes: 2108
/*input
15
1 2 1 1 3 2 2 2 3 3 3 1 1 2 2

*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll , ll> PLL;
typedef long double ld;

#define pb push_back
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
int mod = 1000000007;
#define PI 3.14159265
#define endl '\n'
#define debug(x) cout << #x << " = " << x << endl;
#define MAX 100001

template < typename T > T GCD(T a, T b)            { ll t; while(a) { t = a; a = b % a; b = t; } return b; }
template < typename T > string toString(T a)       { return to_string(a); }
template < typename T > void toInt(string s, T &x) { stringstream str(s); str >> x;}
inline int add(int x, int y){ x += y; if(x >= mod) x -= mod; return x;}
inline int sub(int x, int y){ x -= y; if(x < 0) x += mod; return x;}
inline int mul(int x, int y){ return (x * 1ll * y) % mod;}
inline int powr(int a, ll b){
    int x = 1 % mod;
    while(b){
        if(b & 1) x = mul(x, a);
        a = mul(a, a);
        b >>= 1;
    }
    return x;
}
inline int inv(int a){ return powr(a, mod - 2);}


int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
    
  int n;
  cin >> n;
  int v;
  vector <int> vec;
  for (int i = 0; i < n; i++) {
    cin >> v;
    vec.pb(v);
  }
  int g = 0;
  vector <int> f, b;
  for (auto it : vec) {
    g = __gcd(g, it);
    f.pb(g);
  }
  g = 0;
  for (int i = n - 1; i >= 0; i--) {
    g = __gcd(g, vec[i]);
    b.pb(g);
  }
  reverse(all(b));
  int ans = 1;
  for (int i = 0; i < n; i++) {
    if (i == 0) {
      ans = max(ans, b[i + 1]);
    }
    else if (i == n - 1) {
      ans = max(ans, f[i - 1]);
    }
    else {
      ans = max(ans, __gcd(f[i - 1], b[i + 1]));
    }
  }
  cout << ans << endl;

  return 0;
}

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

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x = i;
		if (x % 3 == 0) {
			cout << " " << x;
		}
		else {
			while (x) {
				if (x % 10 == 3) {
					cout << " " << i;
					break;
				}
				else {
					x /= 10;
				}
			}
		}
	}
	cout << endl;
	return 0;
}

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

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int n,w;
    cin >> n >> w;
    vector<int> V(n);
    vector<int> W(n);
    vector<vector<int>> dp(n+1,vector<int>(w+1));
    for (int j=0;j<=w;j++) dp[0][j] = 0;
    for (int i=0;i<n;i++) cin >> V[i] >> W[i];
    for (int i=0;i<n;i++){
        for (int j=0;j<=w;j++){
            if (j < W[i]){
              dp[i+1][j] = dp[i][j];
            }else {
              dp[i+1][j] = max(dp[i][j],dp[i][j-W[i]]+V[i]);
            }
        }
    }
    cout << dp[n][w] << endl;
    return 0;
}


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

int main(){
  int n;
  long long min = 1000000,max = -10000000,sum = 0;

  cin >> n;

  if ( n == 1){
    long long a;
    cin >> a;

    cout << a << " " << a << " " << a << endl;
  }
  else{
    for (int i=1; i<=n; i++){
      long long a;
      cin >> a;

      if (a < min){
        min = a;
      }
      if (a > max){
        max = a;
      }
      sum += a;
    }

    cout << min <<" "<< max << " " << sum << endl;
  }

  return 0;
}

Measured memory_bytes: 3100
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<utility>
#include<cstdio>
#include<set>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include <bitset>
using namespace std;
const int mod=1e9+7;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<n;i++)
#define rep2(i,x,n) for (int i= x;i<n;i++)
#define all(v) v.begin(), v.end()
#define nepe(v) next_permutation(all(v))
#define F first 
#define S second
#define PB push_back 
#define MP make_pair
using ll = long long;
using vi = vector<int>; 
using vvi = vector<vi>;
using vl=vector<long long>;
using vvl = vector<vl>;
using vp =vector<pair<int,int>>;

typedef pair<int,int> P;
string s;
int k;
ll INF = 1000000000000;

int main(){
    ll N,A,B;
    cin >>N>>A>>B;
    if((B-A)%2==0){
        cout <<(B-A)/2<<endl;
        return 0;
    }
    else cout <<min(A-1,N-B)+1+(B-A)/2<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <set>
#include <map>
#include <cassert>
#include <fstream>
 
using namespace std;
 
int main() {
    

    
    int n, k;
    string s;
    cin >> n >> k >> s;
    k--;
    
    if (s[k] == 'A')
    {
        s[k] = 'a';
    }
    if (s[k] == 'B')
    {
        s[k] = 'b';
    }
    if (s[k] == 'C')
    {
        s[k] = 'c';
    }
    
    cout << s << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdio>
#include <iomanip>
#include <utility>
#include <unordered_map>

using namespace std;
typedef long long int ll;

#define SP(x) setprecision((int)x)
#define ALL(v) v.begin(), v.end()

/* デカい配列はここで宣言 */

int main(int argc, char const *argv[])
{
    ll r, g, b, n;
    cin >> r >> g >> b >> n;
    ll ans = 0;
    for (ll i = 0; i <= n / r; i++)
    {
        ll temp = r * i;
        for (ll k = 0; k <= (n - temp) / g; k++)
        {
            ll temp2 = n - temp - g * k;
            if (temp2 % b == 0)
            {
                ans++;
                // cout << i << " " << k << " " << temp2 / b << endl;
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/




int N, A[10101];
//---------------------------------------------------------------------------------------------------
void _main() {
    while (cin >> N) {
        if (N == 0) return;
        rep(i, 0, N) cin >> A[i];

        int sm = 0;
        rep(i, 0, N) sm += A[i];

        int ans = 0;
        rep(i, 0, N) if (A[i] * N <= sm) ans++;
        printf("%d\n", ans);
    }
}



Measured memory_bytes: 3256
//Compiler optimization
#pragma GCC optimize("Ofast")

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

//typedef
typedef long long ll;
typedef double db;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef string S;
typedef queue<int> qi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vl> mat;

//macro
#define reverse(a) reverse(a.begin(),a.end())
#define unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define fr(i,n)for(ll i=0;i<(n);i++)
#define ifr(i,n)for(ll i=(n)-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define each(x, v) for (auto &x : v)

//abbreviation
#define pb push_back
#define elif else if
#define mp make_pair
#define endl '\n'

//debug
#define debug(x) cerr << #x << ": " << x << endl
#define v_debug(v) cerr << #v << endl;fr(i,v.size()) cerr << i << ": " << v[i] << endl

//const
const  ll INF = 1e18;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }


int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << setprecision(20);
    S s;cin >> s;
    int now = 0,ans = 0;
    fr(i,4){
        if(s[i] == 'R')now++;
        else now = 0;
        chmax<int>(ans,now);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
//k^n/i-2*i-3*i-4*i-5*i-........
ll power(ll a,ll b)
{
	return b? power ( a * a % mod , b / 2 ) * ( b % 2 ? a : 1 ) % mod : 1 ;
}
int main(){
    ll n,k;
    cin>>n>>k;
    ll dp[k+1],ans=0;	
    for(ll i=k;i>=1;i--)
	{
        dp[i]=power(k/i,n);
        for(ll j=2*i;j<=k;j+=i) 
			dp[i]-=dp[j];
        ans=(ans+i*dp[i]%mod)%mod;
    }
    cout<<(ans+mod)%mod;
    return 0;
}


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

using namespace std;

typedef long long ll;

const long long MOD = 1e9;

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> X(M);
  for (int i = 0; i < M; ++i) cin >> X[i];
  sort(X.begin(), X.end());
  int L = X[0];
  int R = X[M - 1];
  vector<int> diff(M - 1);
  for (int i = 0; i < M - 1; ++i) diff[i] = X[i + 1] - X[i];
  sort(diff.begin(), diff.end(), greater<int>());
  int res = 0;
  if (N >= M) res = 0;
  else {
    for (int i = 0; i < N - 1; ++i) res += diff[i];
    res =  R - L - res;
  }
  cout << res << endl;
}

Measured memory_bytes: 1024
import heapq
import sys
input = sys.stdin.readline


def dijkstra(adj, start):
    # adj: [[to, cost] * vertices], 0th index must be empty
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])
    while q:
        min_dist, v_from = heapq.heappop(q)
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to in v_tos:
            if min_dist + v_to[1] < dist[v_to[0]]:
                dist[v_to[0]] = min_dist + v_to[1]
                heapq.heappush(q, [dist[v_to[0]], v_to[0]])
    return dist


n, m, start, goal = map(int, input().split())
adj_yen = [[] for _ in range(n+1)]
adj_snuuk = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    adj_yen[u].append([v, a])
    adj_yen[v].append([u, a])
    adj_snuuk[u].append([v, b])
    adj_snuuk[v].append([u, b])

min_dist_yen = dijkstra(adj_yen, start)
min_dist_snuuk = dijkstra(adj_snuuk, goal)
lose = [float('inf')] * n
for i in range(1, n+1):
    lose[-i] = min(lose[-i+1], min_dist_yen[n-i+1] + min_dist_snuuk[n-i+1])

for i in range(n):
    print(10 ** 15 - lose[i])


Measured memory_bytes: 126648
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try (Scanner scn = new Scanner(System.in)) {
			final int N = scn.nextInt();
			final int K = scn.nextInt();
			final int R = scn.nextInt();
			final int S = scn.nextInt();
			final int P = scn.nextInt();
			final char[] T = scn.next().toCharArray();

			int ret = 0;
			for (int i = 0; i < N; i++) {
				int next = i + K;
				if (next < N && T[i] == T[next]) {
					T[next] = ' ';
				}

				switch (T[i]) {
				case 'r':
					ret += P;
					break;
				case 's':
					ret += R;
					break;
				case 'p':
					ret += S;
					break;
				default:
					break;
				}
			}
			System.out.println(ret);
		}
	}
}


Measured memory_bytes: 28016
fn main() {
    let x: i32;
    let mut buf: String;
    buf = String::new();
    let stdin_obj = std::io::stdin();
    stdin_obj.read_line(&mut buf).ok();
    x = buf.trim().parse().ok().unwrap();
    println!("{}", if x >= 30 { "Yes" } else { "No" })
}


Measured memory_bytes: 2064
N = int(input())
A_list = [int(e) for e in input().split()]

total = sum(A_list)
half = total/2
right_side = 0

for i in range(N):
  if right_side + A_list[i] <= half:
    right_side += A_list[i]
  else:
    left_side = total - right_side
    next_length = A_list[i]
    break

#print(right_side,left_side,abs(right_side - left_side))
#print(right_side+next_length,left_side-next_length,abs(right_side+next_length-left_side+next_length))

if abs(right_side - left_side)<abs(right_side+next_length-left_side+next_length):
  print(abs(right_side - left_side))
else:
  print(abs(right_side+next_length-left_side+next_length))

Measured memory_bytes: 26060
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod= 1e9 +7;
//bool a[22][22];
int n;
int dp[1<<22];
int arr[21][21];

int solve(int mask)
{   int  k=__builtin_popcount(mask)-1; // kth man
    if(dp[mask]!= -1) return dp[mask];
    
    dp[mask]=0;
    for(int w=0;w<n;++w)
    {
        if(arr[k][w] && (mask&(1<<w)))
        dp[mask]= (dp[mask]+solve(mask&(~(1<<w))))%mod;
    }
    
    return dp[mask];
    
}


main()
{  
    cin>>n;
    
    for(int i=0;i<n;++i) 
        for(int j=0;j<n;++j)
            cin>>arr[i][j];
		for(int mask=0;mask < (1<<n); ++mask)
			dp[mask] = -1;
 
    
    dp[0]=1;
    
   cout<<solve(((1<<n) -1 ))<<endl;
   /*
   for(int i=0;i<n;++i) 
    {
        for(int j=0;j< (1<<n);++j)
        {
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    } 
    */
    
}

Measured memory_bytes: 18688
#include<stdio.h>

#define MAX 2000000

int H,A[MAX+1];

void maxHeapify(int i){
  int l,r,largest,C;
  l=2*i;
  r=2*i+1;

  if(l<=H&&A[l]>A[i])largest=l;
  else largest = i;
  if(r<=H&&A[r]>A[largest])largest=r;

  if(largest!=i){
    C=A[i];
    A[i]=A[largest];
    A[largest]=C;
    maxHeapify(largest);
  }
}

int main(){
  int i;

  scanf("%d",&H);

  for(i=1;i<=H;i++)scanf("%d",&A[i]);
  for(i=H/2;i>=1;i--)maxHeapify(i);
  for(i=1;i<=H;i++){
    printf(" %d",A[i]);
  }

  printf("\n");
  
  return 0;
}



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

#define int long long

#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define FORR(i,m,n) for(int i=m;i>=n;i--)
#define pb(x) push_back(x) 
#define SORT(x) sort((x).begin(),(x).end())
#define INF 9999999999
 
using namespace std;

int32_t main(){
    int p[4], l[4];
    int n;
    REP(i, 4) cin >> p[i];
    cin >> n;
    
    p[1]=min(p[1], p[0]*2);
    p[2]=min(p[2], p[1]*2);

    if(n%2){
        cout << n/2*min(p[2]*2, p[3])+p[2] << endl;
    }
    else{
        cout << n/2*min(p[2]*2, p[3]) << endl;
    }
}

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

int main() {
    string S;
    cin >> S;

    string ans = "No";

    string tmp = to_string(S.at(0));

    for (int i = 0; i < S.length(); i++) {
        if(tmp != to_string(S.at(i))){
            ans = "Yes";
        }
    }
    
    
    cout << ans << endl;


    
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        new Solver().solve(new Scanner(System.in));
//        new Solver().solve(new Scanner(ex));
    }

//    private static final String ex = "4\n" +
//        "3";
    private static final String ex = "10\n" +
        "10";
}

class Solver {
    void solve(Scanner scanner) {
        int N = Integer.parseInt(scanner.nextLine());
        int K = Integer.parseInt(scanner.nextLine());

        System.out.println(min(1, N, K));
    }

    private long min(int cur, int N, int K) {
        if (N == 0) return cur;

        long A = min(cur * 2, N - 1, K);
        long B = min(cur + K, N - 1, K);

        return Math.min(A, B);
    }

    private int[] splitInt(String s) {
        String[] split = s.split(" ");
        int[] splitInt = new int[split.length];
        for (int i = 0; i < split.length; i ++) {
            splitInt[i] = Integer.parseInt(split[i]);
        }
        return splitInt;
    }

    private long[] splitLong(String s) {
        String[] split = s.split(" ");
        long[] splitLong = new long[split.length];
        for (int i = 0; i < split.length; i ++) {
            splitLong[i] = Long.parseLong(split[i]);
        }
        return splitLong;
    }
}


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

int main() {
    int n;
    cin >> n;
    map<int, int> name;

    for (int i = 0; i < n; i++){
        string str;
        cin >> str;
        switch (str.at(0)){
            case 'M':
                name[0]++;
                break;
            case 'A':
                name[1]++;
                break;
            case 'R':
                name[2]++;
                break;
            case 'C':
                name[3]++;
                break;
            case 'H':
                name[4]++;
                break;
        }
    }

    int64_t count = 0;
    for (int i = 0; i < (1 << 5); i++){
        bitset<5> bit(i);
        if (bit.count() != 3){
            continue;
        }

        int64_t comb = 1;
        for (int j = 0; j < 5; j++){
            comb *= (bit.test(j) ? name[j] : 1);
        }

        count += comb;
    }

    cout << count << endl;
}

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


int main() {
	int N;
	cin >> N;
	vector<int>A(N);
	for (int i = 0; i < N; ++i) {
		cin >> A[i];
	}
	sort(A.begin(), A.end());
	cout << A[N - 1] - A[0] << endl;
	return 0;
}


Measured memory_bytes: 3584
#include <stdio.h>

int main(void)
{
	int i, n;
	int a, s;
	
	while (scanf("%d", &n), n){
		for (s = 0, i = 0; i < n / 4; i++){
			scanf("%d", &a);
			
			s += a;
		}
		
		printf("%d\n", s);
	}
	
	return (0);
}

Measured memory_bytes: 600
import math

li = list(map(int,input().split()))
b = li[0] / 1
c = li[1] / 1
h = li[2] / 1
m = li[3] / 1

ang1 = 6.0 * m
ang2 = (5.0 * h + m / 12.0) * 6.0
if ang1 > ang2:
	temp = ang1
	ang1 = ang2
	ang2 = temp
An = ang2 - ang1
An = An * math.pi
An = An / 180.0
ans = b*b + c*c - 2*b*c*math.cos(An)
ans = math.sqrt(ans)
print(ans)

Measured memory_bytes: 9528
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

int main(void) {

	int a, b;
	string stra, strb;

	cin >> a >> b;

	for (int i = 0; i < a; i++) {
		ostringstream ss;
		ss << b;
		strb = strb + ss.str();
	}
	for (int i = 0; i < b; i++) {
		ostringstream ss;
		ss << a;
		stra = stra + ss.str();
	}

	if (a <= b)
		cout << stra << endl;
	else
		cout << strb << endl;


	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main() {
	char ch[26] = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z' };
	int cnt[26] = { 0 };

	char inp;
	while (1) {
		if (scanf("%c", &inp) == EOF)break;
		for (int i = 0; i < 26; i++) {
			if (inp == ch[i] || inp == ch[i] - 32) {
				cnt[i]++;
				break;
			}
		}

	}
	for (int j = 0; j < 26; j++) {
		printf("%c : %d\n", ch[j], cnt[j]);
	}
	return 0;
}


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

int main() {
int N, K, Q;
cin >> N >> K >> Q;
vector<int> correct(Q);
for (int i = 0; i < Q; i++) {
   cin >> correct.at(i);
 }

vector<int> vec(N, K);

for (int i = 0; i < vec.size(); i++) {
  vec.at(i) -= Q;
}

for (int i = 0; i < correct.size(); i++) {
  vec.at(correct.at(i) - 1) += 1;
}

for (int i = 0; i < vec.size(); i++) {
  if (vec.at(i) > 0) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;  
  }
}
}


Measured memory_bytes: 1408
N = int(input())
S = str(input())
X = [];Bit = 0;Num = 0
for i in range(N):
  if S[i] == "1":
    Bit += 1
    Num += pow(2,N-1-i)
  X.append(int(S[i]))
#print(X)
#print(Num)
MAX = 2*pow(10,5)+10
small = [-1 for _ in range(MAX)]
small[0] = 0; small[1] = 1; small[2] = 1; small[3] = 2
for i in range(4,MAX):
  ret = 0; target = i*1
  while i > 0:
    cnt = 0
    for j in range(i.bit_length()):
      if (i>>j)&1 == 1:
        cnt += 1
    i = i%cnt
    #print(i,target,cnt)
    ret += 1
    if small[i] != -1:
      ret += small[i]
      break

  small[target] = ret
#print(small)
if Bit -1 != 0:
  Numm = Num%(Bit-1)
Nump = Num%(Bit+1)
#print(Num)
ans = []
for i in range(N):
  keta = N-1-i
  if X[i] == 1:
    btemp = Bit -1
    if btemp == 0:
      ans.append(0)
      continue
    temp = (Numm - pow(2,keta,btemp))%btemp
  else:
    btemp = Bit +1
    temp = (Nump + pow(2,keta,btemp))%btemp
  ret = small[temp] + 1 #最初の一回
  ans.append(ret)
print(*ans,sep="\n")

Measured memory_bytes: 108412
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
void *wmem;
char memarr[96000000];
template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  (*arr)=(T*)(*mem);
  (*mem)=((*arr)+x);
}
template<class T1> void sortA_L(int N, T1 a[], void *mem = wmem){
  sort(a, a+N);
}
inline int my_getchar_unlocked(){
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if(s == e && e == 1048576){
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if(s == e){
    return EOF;
  }
  return buf[s++];
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
struct MY_WRITER{
  char buf[1048576];
  int s;
  int e;
  MY_WRITER(){
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER(){
    if(s){
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
inline void wt_L(int x){
  int s=0;
  int m=0;
  char f[10];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    my_putchar_unlocked('-');
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
int N;
int K;
int P[1000];
int main(){
  wmem = memarr;
  int res;
  rd(N);
  rd(K);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){
      rd(P[Lj4PdHRW]);
    }
  }
  sortA_L(N,P);
  {
    int e98WHCEY;
    int cTE1_r3A;
    if(K==0){
      cTE1_r3A = 0;
    }
    else{
      cTE1_r3A = P[0];
      for(e98WHCEY=(1);e98WHCEY<(K);e98WHCEY++){
        cTE1_r3A += P[e98WHCEY];
      }
    }
    res =cTE1_r3A;
  }
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20200509-1

// --- original code ---
// int N, K, P[1000];
// {
//   int res;
//   rd(N,K,P(N));
//   sortA(N,P);
//   res = sum(P(K));
//   wt(res);
// }


Measured memory_bytes: 3648
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
#define int long long
signed main(){
    int N;
    cin >> N;
    int A[110];
    for(int i = 0;i < N;i++){
        cin >> A[i];
        if(A[i] % 2 == 0){
            if(A[i] % 3 != 0 && A[i] % 5 != 0){cout << "DENIED";return 0;}
        }
    }
    cout << "APPROVED";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
#define int long long
typedef pair<int,int>P;
typedef pair<int,P>P2;
#define F first
#define S second
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};

signed main(){
	int n;
	cin>>n;
	int x[n],y[n];
	r(i,n)cin>>x[i]>>y[i];
	int ans=0;
	map<P,int>M;
	r(i,n){
		r(j,n){
			if(i!=j){
				M[P((x[j]-x[i]),(y[j]-y[i]))]++;
				ans=max(ans,M[P((x[j]-x[i]),(y[j]-y[i]))]);
			}
		}
	}
	cout<<n-ans<<endl;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define ll long long
//#define pw (ll)pow 
#define MAX 1000005
#define MOD (ll)1e9+7
using namespace std;

int main()	
{
	ll a;
	string b;
	cin >> a >> b;
	ll x = b[0]-'0';
	ll y = (b[2]-'0')*10+(b[3]-'0');
	ll s = a*x;
	s += (a*y)/100;
	cout << s << endl;
	return 0;
}

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

int main() {
    int n; cin >> n;
    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (i % 2 == 0) continue;
        set<int> facts;
        for (int j = 1; j * j <= i; j++) {
            if (i % j == 0) {
                facts.insert(j);
                facts.insert(i / j);
            }
        }
        if (facts.size() == 8)
            res++;
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <vector>
#include <cctype>
#include <algorithm>
#include <functional>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <numeric>
#include <iomanip>
#include <limits>
#include <sstream>
#include <bitset>

#define roop(i, n) for(int i=0;i<n;i++)
#define DIV 1000000007
#define MOD ((int)1e9+7)
//static const long double pi = 3.1415926535897932;

using namespace std;
using ll = long long int;
using ull = unsigned long long;

char toSmall(char c) { // 大文字を小文字へ
	return (c + 0x20);
}

char toLarge(char c) { // 小文字を大文字へ
	return (c - 0x20);
}

float myPower(int a, int n) { // aのn乗の計算
	float x = 1;
	while (n > 0) { // 全てのbitが捨てられるまで
		if ( n & 1) { // 一番右のbitが１のとき
			x *= a;
		}
		a *= a;
		n >>= 1; // bit全体を右に1つシフトして一番右を捨てる
	}
	return x;
}

struct Combination {
	const int num=51e4;			//要素数
	const int mod=1e9+7;
	vector<ll> fact,inv,finv; //階乗,逆元,逆元の階乗.
	
	Combination():fact(num),inv(num),finv(num){
		fact[0]=fact[1]=1;
		inv[1]=1;
		finv[0]=finv[1]=1;
		for(int i=2;i<num;++i){
			fact[i]=fact[i-1]*i%mod;
			inv[i]=mod-inv[mod%i]*(mod/i)%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	
	int nCk(int n,int k){
		if(n<k) return 0;
		if(n<0 or k<0) return 0;
		return fact[n]*(finv[k]*finv[n-k]%mod)%mod;
	}
	int big_nCk(int n,int k){ //nが大きいとき
		ll res=1LL;
		for (int i = 0; i < k; i++) {
			res=res*(n-i)%mod;
		}
		res = res*finv[k]%mod;
		return res;
	}
	int nHk(int n,int k){return nCk(n+k-1,n-1);}//重複組み合わせ.
};

vector<string> split(const string& src, const char* delim = ",") { //カンマ区切り
	vector<string> vec;
	string::size_type len = src.length();

	for (string::size_type i = 0, n; i < len; i = n + 1) {
		n = src.find_first_of(delim, i);
		if (n == string::npos) {
			n = len;
		}
		vec.push_back(src.substr(i, n - i));
	}

	return vec;
}

bool check_int(string str)
{
	if (all_of(str.cbegin(), str.cend(), [](char ch) { return isdigit(ch);}))
	{
		return true;
	}
	return false;
}

struct rest {
	string s;
	int p;
	int num;

	/* -------------------------------------
	sort関数を使用したときのソートの定義をする。
	まずは文字列sでソートする。
	文字列sが同じだった場合、pでソートする。
	この条件を参考演算子で表現(ifでもOK)
	-------------------------------------*/
	bool operator<(const rest& right) const {
		return s == right.s ? p > right.p : s < right.s;
	}
};

ll pow_mod(ll n, ll k, ll p) { // n^k(mod p)
	if (k == 0) {
		return 1;
	}
	ll res = pow_mod(n * n % p, k / 2, p);
	if (k & 1) {
		res = res * n % p;
	}
	return res;
}

bool vector_finder(std::vector<int> vec, int number) { // vector 内にnumberがあるかどうか
	auto itr = std::find(vec.begin(), vec.end(), number);
	size_t index = std::distance( vec.begin(), itr );
	if (index != vec.size()) { // 発見できたとき
		return true;
	}
	else { // 発見できなかったとき
		return false;
	}
}

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end(), greater<int>());
	int alice = 0;
	int bob = 0;
	for (int i = 0; i < n; i++) {
		if (i % 2 == 0) {
			alice += a[i];
		} else {
			bob += a[i];
		}
	}
	return cout << (alice - bob) << endl, 0;
}

Measured memory_bytes: 3640
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, m = map(int, readline().split())
a = [readline().rstrip().decode() for _ in range(n)]
b = [readline().rstrip().decode() for _ in range(m)]
for y in range(n - m + 1):
    for x in range(n - m + 1):
        if [aa[x:x + m] for aa in a[y:y + m]] == b:
            print('Yes')
            exit()
print('No')


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

const int mxN = 1e5 + 5, mod = 1e9 + 7;
int N;
vector<int> adj[mxN];
int dp[mxN][2];

int rec(int u, int p, int pc) {
	if (dp[u][pc] != -1) {
		return dp[u][pc];
	}
	ll tot = 0, ways = 1;
	if (pc == 0) {
		for (int v : adj[u]) {
			if (v == p) {
				continue;
			}
			ways = (ways * rec(v, u, 1)) % mod;
		}
		tot = ways;
	}
	ways = 1;
	for (int v : adj[u]) {
		if (v == p) {
			continue;
		}
		ways = (ways * rec(v, u, 0)) % mod;
	}
	tot = (tot + ways) % mod;
	return dp[u][pc] = tot;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> N;
	int x, y;
	for (int i = 0; i < N - 1; i++) {
		cin >> x >> y;
		x--, y--;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	memset(dp, -1, sizeof(dp));
	int ans = rec(0, -1, 0);
	cout << ans;
	
	return 0;
}


Measured memory_bytes: 16712
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc;
		String str="";
		String[] kuwasiku;
		int nedan=0;
		int kazu=0;
		int sougaku=0;
		int sousuu=0;
		int kaisu=0;

	sc=new Scanner(System.in);
		while(sc.hasNext()) {
			str=sc.next();
			kuwasiku=str.split(",");
			nedan=Integer.parseInt(kuwasiku[0]);
			kazu=Integer.parseInt(kuwasiku[1]);
			sougaku+=nedan*kazu;
			sousuu+=kazu;
			kaisu++;
		}
		System.out.println(sougaku);
		System.out.println(Math.round(sousuu*1.0/kaisu));
	}
}


Measured memory_bytes: 26172
// すべての数は6174に通ず.cpp : Defines the entry point for the console application.
//
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

void sort(int a[]) {
	for (int i = 1; i < 4; i++) {
		int v = a[i];
		int j = i - 1;
		while (j >= 0 && a[j] > v) {
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = v;
	}
}

int main(void)
{
	int result[10000], suffix = 0;

	while (1) {
		int n, temp[4], save, big, small, count = 0;

		scanf("%d", &n);
		save = n;
		if (n == 0) {
			break;
		}
		bool success = false;
		for (int i = 0; i < 4; i++) {
			temp[i] = n % 10;
			n /= 10;
		}
		n = save;
		for (int i = 0; i < 3; i++) {
			if (temp[i] != temp[i + 1]) {
				success = true;
				break;
			}
		}

		while (n != 6174 && success == true) {
			for (int i = 0; i < 4; i++) {
				temp[i] = n % 10;
				n /= 10;
			}

			sort(temp);

			small = 0;
			big = 0;
			for (int i = 0; i < 4; i++) {
				small = small * 10 + temp[i];
				big = big * 10 + temp[3 - i];
			}
			n = big - small;
			count++;
		}

		if (success == true) {
			result[suffix] = count;
		}
		else {
			result[suffix] = -1;
		}
		suffix++;
	}

	for (int i = 0; i < suffix; i++) {
		if (result[i] == -1) {
			puts("NA");
		}
		else {
			printf("%d\n", result[i]);
		}
	}

	return 0;
}

Measured memory_bytes: 1076
#include <bits/stdc++.h>
// #include <iostream>
// #include <vector>
// #include <map>
// #include <algorithm>
using  namespace std;

typedef long long ll;
vector<ll> fib;

ll fibo(ll n){
    if (n <= 1) {
        return n;
    }

    if (fib[n] != 0) {
        return fib[n];
    }

    return fib[n] = fibo(n-1) + fibo(n-2);
}

int main(int argc, char const* argv[])
{
    int N, K;
    cin >> N >> K;

    if ((N + 1) / 2 >= K) {
        cout << "YES" << endl;
    }else{
        cout << "NO" <<endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}
template <class C>
void print(const C &c, std::ostream &os = std::cout) {
    std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, " "));
    os << std::endl;
}

int main() {
    string n;
    cin >> n;
    if (n[0] == n[2])
        cout << "Yes" << "\n";
    else
        cout << "No" << "\n";
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
#define rep(i,n)for(int i=0;i<n;i++)
#define int long long
#define ggr getchar();getchar();return 0;
#define prique priority_queue
#define mod 1000000007
#define inf 1e15
#define key 1e9
using namespace std;
typedef pair<int, int>P;
void yes() { cout << "Yay!" << endl; }
void no() { cout << ":(" << endl; }
template<class T> inline void chmax(T& a, T b) {
	a = std::max(a, b);
}
template<class T> inline void chmin(T& a, T b) {
	a = std::min(a, b);
}
const int MAX = 330000;
int fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = mod - inv[mod % i] * (mod / i) % mod;
		finv[i] = finv[i - 1] * inv[i] % mod;
	}
}

// 二項係数計算
long long COMB(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
bool prime(int n) {
	int cnt = 0;
	for (int i = 1; i <= sqrt(n); i++) {
		if (n % i == 0)cnt++;
	}
	if (cnt != 1)return false;
	else return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y)* mod_pow(kai(y, y), mod - 2, mod) % mod;
}
void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug_out(T...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
struct edge { int to, cost; };
int par[114514], rrank[114514];//親、木の深さ
void init(int n) {
	rep(i, n) {
		par[i] = i;
		rrank[i] = 0;
	}
}
int find(int x) {
	if (par[x] == x) {
		return x;
	}
	else return par[x] = find(par[x]);
}
void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y)return;
	if (rrank[x] < rrank[y]) {
		par[x] = y;
	}
	else {
		par[y] = x;
		if (rrank[x] == rrank[y])rrank[x]++;
	}
}
bool same(int x, int y) {
	return find(x) == find(y);
}
int keta(int x) {
	int ans = 0, n = 1;
	while (n <= x) {
		ans++;
		n *= 10;
	}
	return ans;
}
int n;
int a[224514];
signed main() {
	cin >> n;
	rep(i, n)cin >> a[i];
	int m = a[0], ans = 0;
	for (int i = 1; i < n; i++) {
		if (m > a[i]) {
			ans++;
			m = a[i];
		}
	}
	cout << ans+1 << endl;
	ggr
}


Measured memory_bytes: 1792
/*
P135
AOJ 0558 Cheese
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558
*/


#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <functional>
#include <string.h>
using namespace std;
/*
int W, H;
char board[110][110];
int a[10];
bool read()
{
    for(int i=0; i<10; ++i)
        scanf("%d", a+i);
}

bool isVisited[110][110];
int step;

void dfs(int x, int y, char c){
    if(x<0 || x>=H || y<0 || y>=W) return;
    if(board[x][y]!=c) return;
    if(isVisited[x][y]) return;
    isVisited[x][y] = true;
    dfs(x+1, y, c);
    dfs(x-1, y, c);
    dfs(x, y+1, c);
    dfs(x, y-1, c);
}



void solve1()
{
    int x1=0, x2=0;
    bool ans = true;
    for(int i=0; i<10; ++i)
    {
        if(x1 < x2) swap(x1, x2);
        if(x1 < a[i]) x1 = a[i];
        else if(x2 < a[i]) x2 = a[i];
        else {ans = false; break;}
    }
    if(ans) printf("YES\n");
    else printf("NO");
}



vector<int> L_bucket;
vector<int> R_bucket;

bool dfs2(int d){
    if(d == 10) return true;
    bool flag;
    if(L_bucket.size() == 0 || L_bucket.back() < a[d]){
        L_bucket.push_back(a[d]);
        flag = dfs2(d+1);
        L_bucket.pop_back();
    }
    if(flag) return true;
    if(R_bucket.size() == 0 || R_bucket.back() < a[d]){
        R_bucket.push_back((a[d]));
        flag = dfs2(d+1);
        R_bucket.pop_back();
    }
    if(flag) return true;
    return false;

}

void solve2()
{
    if(dfs2(0))
        printf("YES\n");
    else printf("NO\n");
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        read();
        solve2();
    }
}
*/


const int MAXN = 1010;
const int inf = 1<<30;
char board[MAXN][MAXN];
int H, W, N;
int dx[] = {0, 1, 0, -1, 0};
int dy[] = {1, 0, -1, 0, 0};

typedef pair<int,int> PAIR;

PAIR goal[10];

bool check(int x, int y)
{
    return (x>=0&&x<H && y>=0 && y<W);
}

void read()
{
    scanf("%d%d%d", &H, &W, &N);
    for(int i=0; i<H; ++i){
        scanf("%s", board[i]);
        for(int j=0; j<W; ++j){
            if(board[i][j] == 'S')
                goal[0] = make_pair(i, j);
            if(board[i][j]>='0' && board[i][j] <='9'){
                int x = board[i][j] - '0';
                goal[x] = make_pair(i, j);
            }
        }
    }
}

int step[MAXN][MAXN];

int bfs(const PAIR& st, const PAIR& ed){
    queue<PAIR> q;
    q.push(st);
    memset(step, -1, sizeof(step));
    step[st.first][st.second] = 0;

    while(!q.empty()){
        PAIR cur = q.front(); q.pop();
        int x = cur.first, y = cur.second;
        int stp = step[x][y];

        for(int d=0; d<4; ++d){
            int cx = x + dx[d], cy = y + dy[d];
            if(check(cx, cy)){
                if(board[cx][cy]!='X' && step[cx][cy] == -1){
                    if(cx == ed.first && cy == ed.second) return stp + 1;
                    step[cx][cy] = stp + 1;
                    q.push(make_pair(cx, cy));
                }
            }
        }
    }
}



void solve()
{
    int ans = 0;
    for(int i=0; i<N; ++i){
        ans += bfs(goal[i], goal[i+1]);
    }
    printf("%d\n", ans);
}

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

Measured memory_bytes: 6188
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
lint a[200100];
int main()
{
	int n;lint sum=0,now=0,out=1e17L;
	cin>>n;
	rep(i,n) cin>>a[i];
	rep(i,n) sum+=a[i];
	rep(i,n){
		now+=a[i];
		out=min(out,abs(sum-now-now));
	}
	cout<<out<<endl;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int N,count;
  cin>>N;
  vector<int>kushi(N*2);
  for(int i=0;i<N*2;i++)cin>>kushi[i];
  sort(kushi.begin(),kushi.end());
  for(int i=0;i<N*2;i+=2){
    count+=min(kushi[i],kushi[i+1]);
  }
  cout<<count<<endl;
}

Measured memory_bytes: 256
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;
typedef string::const_iterator State;
#define Ma_PI 3.141592653589793
#define eps 1e-5
#define LONG_INF 1000000000000000000LL
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL
#define MOD 998244353LL
#define seg_size 262144*4
#define REP(a,b) for(long long a = 0;a < b;++a)
int gogo[20][20];
long long dp[1 << 16][20];
long long cost[1 << 16][20];
int main() {
	int n, m;
	cin >> n >> m;
	int ans = 0;
	REP(i, m) {
		int a, b, c;
		cin >> a >> b >> c;
		gogo[a - 1][b - 1] = c;
		gogo[b - 1][a - 1] = c;
	}
	REP(i, 1 << n) {
		REP(q, n) {
			dp[i][q] = 1 << 30;
			REP(t, n) {
				if (i & (1 << t)) {
					cost[i][q] += gogo[q][t];
				}
			}
		}
	}
	dp[1][0] = 0;
	REP(i, 1 << n) {
		REP(q, n) {
			if ((i & (1 << q)) != 0 && dp[i][q] < 1 << 30) {
				REP(j, n) {
					if (gogo[q][j] != 0 && (i & (1 << j)) == 0) {
						dp[i + (1 << j)][j] = min(dp[i + (1 << j)][j], dp[i][q] + cost[i][j] - gogo[q][j]);
					}
				}
				int now = i ^ (1 << q);
				for (int j = ((1 << n) - 1) ^ i; j > 0; j = (j - 1) & (((1 << n) - 1) ^ i)) {
					int add = 0;
					REP(t, n) {
						if (j & (1 << t)) add += cost[now][t];
					}
					dp[i | j][q] = min(dp[i | j][q], dp[i][q] + add);
				}
			}
		}
	}
	cout << dp[(1 << n) - 1][n - 1] << endl;
}

Measured memory_bytes: 12544
/*
 * @Author: Kaizyn
 * @Date: 2020-08-29 20:53:14
 * @LastEditTime: 2020-08-29 20:54:41
 */
#include <bits/stdc++.h>

// #define DEBUG

using namespace std;

const double eps = 1e-7;
const double PI = acos(-1);
typedef pair<int, int> pii;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
const int N = 2e5+7;

struct DSU {
  int fa[N], num[N];
  void init(int sz) { for (int i = 0; i <= sz; ++i) fa[i] = i, num[i] = 1; }
  int get(int s) { return s == fa[s] ? s : fa[s] = get(fa[s]); }
  int& operator [] (int i) { return fa[get(i)]; }
  bool merge(int x, int y) {
    int fx = get(x), fy = get(y);
    if (fx == fy) return false;
    if (num[fx] >= num[fy]) num[fx] += num[fy], fa[fy] = fx;
    else num[fy] += num[fx], fa[fx] = fy;
    return true;
  }
} dsu;

int n, m;

inline void solve() {
  cin >> n >> m;
  dsu.init(n);
  for (int i = 1, x, y; i <= m; ++i) {
    cin >> x >> y;
    dsu.merge(x, y);
  }
  int res = 0;
  for (int i = 1; i <= n; ++i) {
    res = max(res, dsu.num[i]);
  }
  cout << res << endl;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  int T = 1;
  // cin >> T;
  for (int t = 1; t <= T; ++t) {
    solve();
  }
  return 0;
}

Measured memory_bytes: 5208
n = int(input())
A = [int(i) for i in input().split()]
ans = 100000000000000
a = 0
b = sum(A)
for i in range(n-1):
  a += A[i]
  b -= A[i]
  c = abs(a-b)
  ans = min(ans, c)
print(ans)

Measured memory_bytes: 24924
#include <iostream>
#include <cmath>
#include <string>
#include <set>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <list>
#include <stack>
#define lar(a, b) ((a>b) ? (a):(b))
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;

int main(void) {
    vector<p> cnt;
    p pir;
    pir = make_pair(-1, 0);
    cnt.push_back(pir);
    
    ll n, i, tmp, atmp, ans=1, tmpc=0;
    cin >> n;
    ll a[n];
    for(i=0; i<n; i++)
        cin >> a[i];
    sort(a, a+n);
    
    for(i=0; i<n; i++) {
        tmp=1;
        atmp=a[i];
        while(a[i]==a[i+1]) {
            tmp++;
            i++;
        }
        pir = make_pair(atmp, tmp);
        cnt.push_back(pir);
    }
    
    pir = make_pair(-1, 0);
    cnt.push_back(pir);
    
    for(i=cnt.size()-2; i>=1; i--) {
        if(tmpc==0 && cnt[i].second>=4) {
            cout << cnt[i].first*cnt[i].first << endl;
            return 0;
        }else if(tmpc==0 && cnt[i].second>=2) {
            ans *= cnt[i].first;
            tmpc++;
        }else if(tmpc==1 && cnt[i].second>=2) {
            ans *= cnt[i].first;
            cout << ans << endl;
            return 0;
        }
    }
    cout << 0 << endl;
}


Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define mk make_pair
#define ll long long
using namespace std;
const int N = 3e5 + 5;
const int mod = 1e9 + 7;
set< pair<int, int> > :: iterator it;
set< pair<int, int> > S; 
int n, k, a[N], cnt[N];
int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		scanf("%d", a + i);
		cnt[a[i]]++;
	}
	for (int i = 0; i < N; i++) {
		if (cnt[i]) S.insert(mk(cnt[i], i));
	}
	int ans = 0;
	while (S.size() > k) {
		it = S.begin();
		ans += (*it).first;
		S.erase(it);
	}
	cout << ans;
}

Measured memory_bytes: 11136