akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef pair<char, char>P;

vector<int>E[26];
bool used[26];
int in[26], out[26];

void dfs(int u) {
	used[u] = true;
	for (int v : E[u]) {
		if (!used[v])dfs(v);
	}
}
int main() {
	int n;
	while (scanf("%d", &n), n) {
		memset(used, 0, sizeof(used));
		memset(in, 0, sizeof(in));
		memset(out, 0, sizeof(out));
		rep(i, 26)E[i].clear();
		int c;
		rep(i, n) {
			string s; cin >> s;
			int front = s.front() - 'a', back = s.back() - 'a';
			c = front;
			E[front].push_back(back);
			in[back]++; out[front]++;
		}
		dfs(c);
		rep(i, 26) {
			if (in[i] != out[i] || (in[i] && !used[i])) {
				puts("NG"); goto g;
			}
		}
		puts("OK");
	g:;
	}
}

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

int main(void){
    int n;
    cin >> n;
    int a[n];
    for(int i = 0;i < n;i++)cin >> a[i];
    int ans = 0,sum = 0;
    for(int i = 1;i < n;i++){
        if(a[i-1] >= a[i]){
            sum++;
        } else {
            ans = max(ans,sum);
            sum = 0;
        }
    }
    ans = max(ans,sum);
    cout << ans << endl;
}

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

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

  vector<string> week = {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};

  rep(i, 7) {
    if (week[i] == s) {
      cout << 7 - i << endl;
      break;
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include <cassert>

#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define ll long long
//#define all(v) ((v).begin(),(v).end())
#define Sort(v) sort(all(v))
#define INF 1000000000
#define END return 0
#define pb push_back
#define se second
#define fi first
#define pb push_back
#define all(v) (v).begin() , (v).end()
#define MP make_pair
using namespace std;
int day[12]={31,28,31,30,31,30,31,31,30,31,30,31};

int main(){
    int n;cin>>n;
    vector<ll> v(n),b(n);
    rep(i,0,n){
        cin>>v[i];
        b[i]=v[i]-i-1;
    }
    Sort(b);
    ll mid=b[(n-1)/2];
    ll ans=0;
    rep(i,0,n){
        ans+=abs(v[i]-(mid+i+1));
    }
    cout<<ans<<endl;

    return 0;
}

/*
中央値の添字：
nが奇数→n/2
nが偶数→n/2

*/



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


using namespace std;


const int kMod = 1e9+7;

void Solve() {
	int n, m;

	cin >> n >> m;

	vector<long long> fac(max(n, m) + 1);

	fac[0] = 1;
	for (int i = 1; i <= max(n, m); ++i) {
		fac[i] = fac[i-1] * i % kMod;
	}

	// cerr << n << " " << m << "\n";

	// cerr << fac[n] << " " << fac[m] << "\n";

	if (n == m) {
		cout << 2 * fac[n] % kMod * fac[m] % kMod;
	} else {
		if (n > m)
			swap(n, m);
		if (n + 1 != m) {
			cout << 0;
		} else {
			cout << fac[n] * fac[m] % kMod;
		}
	}

	cout << "\n";
}

int main() {
	int tests = 1;

	for (;tests; --tests) {
		Solve();
	}
}

Measured memory_bytes: 1024
#include <iostream>
#include <sstream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <queue>
#include <ctime>
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
 
using namespace std;
 
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define epr(...) fprintf(stderr, __VA_ARGS__)
#define db(x) cerr << #x << " = " << x << endl
#define db2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")\n";
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
 
#define equal equalll
#define less lesss
#define matr vector<vector<int>>

int main() {
	// freopen("input.txt", "r", stdin);
	string s;
	int k;
	cin >> s;
	cin >> k;
	for (int i = 0; i < (int)s.size(); i++) {
		int x = s[i] - 'a';
		int t = (26 - x) % 26;
		if (t <= k) {
			s[i] = 'a';
			k -= t;
			continue;
		}
	}
	int x = s.back() - 'a';
	x = (x + k) % 26;
	s.back() = x + 'a';
	cout << s << endl;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define inf (int)1e9+7
#define eb emplace_back
#define eps 1e-10

int main() {
    int w, h, x, y; cin >> w >> h >> x >> y;
    if (x == (double)w / 2 && y == (double)h / 2) {
        cout << fixed << setprecision(11) << (double)w * h / 2 << " " << 1 << endl;
    } else if (x == w / 2 || y == h / 2) {
        cout << fixed << setprecision(11) << (double)w * h / 2 << " " << 0 << endl;
    } else {
        cout << fixed << setprecision(11) << (double)w * h / 2 << " " << 0 << endl;
    }
}



Measured memory_bytes: 256
#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>;

const int m = 2019;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    reverse(s.begin(), s.end());
    int x = 1, tot = 0;
    vector<int> cnt(m);
    ll ans = 0;
    rep(i, n){
        cnt[tot]++;
        tot += (s[i]-'0')*x;
        tot %= m;
        ans += cnt[tot];
        x = x*10%m;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3752
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
typedef long long ll;
 
int n;
ll a[100000];
 
bool C(int x){
   	multiset<ll> st;
   	ll v = a[x];
   	for(int i=0;i<n;i++) if(i!=x) st.insert(a[i]);
   	while(!st.empty()){
   		multiset<ll>::iterator ite = st.upper_bound(v*2);
   		if(ite==st.begin()) return false;
   		else{
   			ite--;
   			v += *ite;
   			st.erase(ite);
   		}
   	}
   	return true;
}

int main(){
   	scanf("%d",&n);
   	for(int i=0;i<n;i++) scanf("%lld",a+i);
   	sort(a,a+n);
   	int ub = n - 1, lb = -1;
   	while(ub-lb>1){
   		int mid = (ub + lb) / 2;
   		if(C(mid)) ub = mid;
   		else lb = mid;
   	}
   	printf("%d\n",n-ub);
   	return 0;
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef long double ld;
typedef pair<int,ll> P;
typedef tuple<int,int,int> TP;
constexpr int INF = 2e9;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  vector<int> left(n), right(n);
  left[0] = a[0];
  for (int i = 1; i < n; i++) left[i] = gcd(left[i - 1], a[i]);
  right[n - 1] = a[n - 1];
  for (int i = n - 2; i >= 0; i--) right[i] = gcd(right[i + 1], a[i]);
  int res = 0;
  for (int i = 0; i < n; i++) {
    if (i == 0) res = max(res, right[i + 1]);
    else if (i == n - 1) res = max(res, left[i - 1]);
    else res = max(res, gcd(right[i + 1], left[i - 1]));
  }
  cout << res << endl;
  return 0;
} 

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

long long a,b,c;

int main()
{
	scanf("%d%d%d",&a,&b,&c);
	bool ok=4*a*b<(c-a-b)*(c-a-b) && c-a-b >= 0;
	puts(ok ?"Yes":"No");
	return 0;	
} 

Measured memory_bytes: 256
N, M, X, Y = tuple(map(int, input().split()))
area_X = [int(x) for x in input().split()]
area_Y = [int(x) for x in input().split()]
area_X.append(X)
area_Y.append(Y)

print('No War' if max(area_X) < min(area_Y) else 'War')


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

int main() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	int k;
	cin >> k;
	char c = s.at(k-1);
	for (int i = 0; i < n; i++) {
		if (s.at(i) == c)cout << c;
		else cout << "*";
	}
}

Measured memory_bytes: 256
/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define pb emplace_back
#define mp make_pair
#define eps 1e-8
#define lson (curpos<<1)
#define rson (curpos<<1|1)
/* namespace */
using namespace std;
/* header end */

const int maxn = 110;
int n, a[maxn], ans = INT_MAX;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= 100; i++) {
        int tmp = 0;
        for (int j = 1; j <= n; j++) tmp += (a[j] - i) * (a[j] - i);
        ans = min(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define nl "\n"
using namespace std;
typedef unsigned long long ull;

void solve() {
	int n;
	cin >> n;
	int r = n % 10;
	if (r == 3 ) {
		cout << "bon" << endl;
	}
	else if (r == 0 || r == 1 || r == 6 || r == 8) {
		cout << "pon" << endl;
	}
	else {
		cout << "hon" << endl;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}


Measured memory_bytes: 3652
#include<stdio.h>
#include<stdlib.h>
#define MAX 10000

int main(){
  int *A,*B;
  int C[MAX+1];
  int n,i;

  scanf("%d",&n);
  A=malloc(sizeof(int)*n+1);
  B=malloc(sizeof(int)*n+1);

  for(i=0;i<=MAX;i++) C[i]=0;

  for(i=0;i<n;i++){
    scanf("%d",&A[i+1]);
    C[A[i+1]]++;
  }

  for(i=1;i<=MAX;i++) C[i]=C[i]+C[i-1];

  for(i=1;i<=n;i++){
    B[C[A[i]]]=A[i];
    C[A[i]]--;
  }

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

  return 0;

}

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

using ll = long long int;

const int MAX = (int)(1e5 + 5);
const ll INF = (ll)(1e10 + 5);

const int MAX_N = (int)(3e3 + 5);
const int MAX_T = (int)(3e3 + 5);

// inline bool cmp(pair<int, int> a, pair<int, int> b) {
//   return a.first < b.first || (a.first == b.first && a.second > b.second);
// }

int n, t;

int a[MAX_N];
int b[MAX_N];

int dp_l[MAX_N][MAX_T];
int dp_r[MAX_N][MAX_T];

int fix_i(int i) {
  int ret = -1;

  for (int j = 0; j <= (t - 1); ++j) {
    int tmp = dp_l[i - 1][j] + dp_r[i + 1][t - 1 - j];
    ret = max(ret, tmp);
  }

  ret += b[i];

  return ret;
}

int main(void) {
  // Here your code !
  scanf("%d %d", &n, &t);

  for (int i = 1; i <= n; ++i) {
    scanf("%d %d", &(a[i]), &(b[i]));
  }

  for (int i = 1; i <= n; ++i) {
    for (int c = 1; c <= t; ++c) {
      if (c < a[i]) {
        dp_l[i][c] = dp_l[i - 1][c];
      } else {
        dp_l[i][c] = max(dp_l[i - 1][c], dp_l[i - 1][c - a[i]] + b[i]);
      }
    }
  }

  for (int i = n; i >= 1; --i) {
    for (int c = 1; c <= t; ++c) {
      if (c < a[i]) {
        dp_r[i][c] = dp_r[i + 1][c];
      } else {
        dp_r[i][c] = max(dp_r[i + 1][c], dp_r[i + 1][c - a[i]] + b[i]);
      }
    }
  }

  int ans = -1;

  for (int i = 1; i <= n; ++i) {
    ans = max(ans, fix_i(i));
  }

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

  return 0;
}


Measured memory_bytes: 70784
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int64_t i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
int n,cnt[15],x[15][15],y[15][15],ans=0;
void check(int w)
{
	int num=0;
	for(int i=0;i<n;++i)
		if(w>>i&1)
		{
			++num;
			for(int j=0;j<cnt[i];++j)
				if((w>>x[i][j]&1)!=y[i][j])return;
		}
	ans=max(ans,num);
}
int main()
{
	cin>>n;
	for(int i=0;i<n;++i)
	{
		cin>>cnt[i];
		for(int j=0;j<cnt[i];++j)cin>>x[i][j]>>y[i][j],--x[i][j];
	}
	for(int i=1;i<1<<n;++i)check(i);
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>

struct Node {
    int key;
    Node * prev, * next;
};

Node * nil;

void init(){
    nil = (Node *)malloc(sizeof(Node));
    nil->next = nil;
    nil->prev = nil;
}

void insert(int key){
    Node * cur = (Node*)malloc(sizeof(Node));
    cur->key = key;
    cur->next = nil->next;
    cur->prev = nil;
    nil->next->prev = cur;
    nil->next = cur;
}

void deleteNode(Node * cur){
    cur->next->prev = cur->prev;
    cur->prev->next = cur->next;
    free(cur);
}

Node * listSearch(int key){
    Node * cur = nil->next;
    while (cur != nil && cur->key != key){
        cur = cur->next;
    }
    return cur;
}

void deleteFirst(){
    deleteNode(nil->next);
}

void deleteLast(){
    deleteNode(nil->prev);
}

void deleteKey(int key){
    Node * cur = listSearch(key);
    if (cur == nil)
        return ;
    deleteNode(cur);
}

void printList(){
    Node *ptr = nil->next;
    // do{
    //     if (head == ptr)
    //         printf("%d", ptr->x);
    //     else
    //         printf(" %d", ptr->x);
    //     ptr = ptr->next;
    // }while(ptr != head);
    int flag = 1;
    while (ptr != nil){
        if (flag){
            printf("%d", ptr->key);
            flag = 0;
        }
        else {
            printf(" %d", ptr->key);
        }
        ptr = ptr->next;
    }
    putchar('\n');
}

int main(){
    init();
    int n, key;
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        char s[10];
        scanf("%s", s);
        if (strcmp(s, "insert") == 0){
            scanf("%d", &key);
            insert(key);
        }
        if(strcmp(s, "delete") == 0){
            scanf("%d", &key);
            deleteKey(key);
        }
        if(strcmp(s, "deleteFirst") == 0){
            deleteFirst();
        }
        if(strcmp(s, "deleteLast") == 0){
            deleteLast();
        }
    }
    printList();
    return 0;
}


Measured memory_bytes: 33844
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<deque>
#include<math.h>
using namespace std;
#define ll long long
int main(){
    string S;
    cin >> S;
    ll N = S.size();
    ll i;
    for(i=0;i<N/2;i++){
        if(S[i]!=S[N-1-i]){
            cout << "No";
            return 0;
        }
    }
    for(i=0;i<(N-1)/4;i++){
        if(S[i]!=S[(N-1)/2-i-1]){
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int i[10];
	int j;
	int max = 0;
	int rimit = 3;
	
	for (j = 0;j < 10;j++){
		scanf("%d",&i[j]);
	}
	while (rimit > 0){
		for (j = 0;j < 10;j++){
			if(max < i[j]){
				max = i[j];
			}
		}
		printf("%d\n",max);
		for (j = 0;j < 10;j++){
			if(max == i[j]){
				i[j] = 0;
				break;
			}
		}
		max = 0;
		rimit--;
	}
	return(0);
}

Measured memory_bytes: 600
import math
a, b, h, m = map(int, input().split())
l = h * 30
r = m * 6
if l > r:
    x = (l + m/2) - r
else:
    x = r - (l + m/2)
print(math.sqrt(a**2 + b**2 - 2*a*b*(math.cos(math.radians(x)))))



Measured memory_bytes: 9568
#define _GLIBCXX_DEBUG
#pragma GCC diagnostic ignored "-Wsign-compare"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < int(n); ++i)

int n;
vector<int> A;

bool solve(int i, int m) {
    if (m == 0) {
        return true;
    } else if (i >= n) {
        return false;
    }
    return solve(i + 1, m) || solve(i + 1, m - A.at(i));
}

void Main() {
    int m, Q;
    cin >> n;
    A.resize(n);
    for (auto &e : A) {
        cin >> e;
    }
    cin >> Q;
    for (int q = 0; q < Q; q++) {
        cin >> m;
        cout << (solve(0, m) ? "yes\n" : "no\n");
    }
}
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    // cout << fixed << setprecision(15);
    Main();
}


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

#define INF (2e9)
#define FOR(i, a, b) for (ll (i) = (a); (i) < (b); ++(i))
#define REP(i, n) FOR(i, 0, n)

using namespace std;

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

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

using ll = long long;
using ld = long double;

#define ALL(x) (x).begin(), (x).end()
template<class T>
using vc = vector<T>;
using vi = vc<ll>;
using vvi = vc<vi>;

template<class T>
using va = valarray<T>;
using vad = va<ld>;
using vai = va<ll>;

using pii = pair<ll, ll>;

vi Read(ll n) {
    auto      v = vi(n);
    for (auto i = std::size_t(0); i < n; ++i) {
        cin >> v[i];
    }
    return v;
}

template<class T>
void DumpRow(const T& A) {
    for (const auto& value : A)
        cout << value << "\n";
}

template<class T>
void DumpColumn(const T& A) {
    auto isFirst = true;
    for (const auto& value : A) {
        if (isFirst) {
            cout << value;
            isFirst = false;
        } else {
            cout << " " << value;
        }

    }
    cout << endl;
}

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

    ll n;
    cin >> n;
    auto v = set<int>();

    REP(i, n) {
        int q, x;
        cin >> q >> x;
        if (q == 0) {
            v.insert(x);
            cout << v.size() << endl;
        } else if (q == 1){
            auto it = v.find(x);
            if (it != v.end()) cout << 1 << endl;
            else cout << 0 << endl;
        } else if (q == 2){
            v.erase(x);
        }
    }

    return 0;
}



Measured memory_bytes: 12512
import java.util.Scanner;
public class Main{
	public static void main(String[]args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int x = sc.nextInt();
		int y = sc.nextInt();
		int c = a - b;
		if(a > b) {
			int money1 = b * x;
			int money2 = c * y;
			int total = money1 + money2;
			System.out.println(total);
		}else {
			int total = a * x;
			System.out.println(total);
	}
}
}

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

inline int read(){
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}

inline void write(int x){
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}

inline void writeln(int x){
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
     puts("");
}

signed main(){
    int a=read(),v=read(),b=read(),w=read(),t=read();
    
    if(v<w)
        cout<<"NO\n";
    else if((v-w)*t>=fabs(b-a))
        cout<<"YES\n";
    else
        cout<<"NO\n";
        
    return 0;
}

Measured memory_bytes: 3648
N = int(input())
s = [''.join(sorted(input())) for _ in range(N)]

d = {}
for i in s:
  if i not in d:
    d[i] = 1
  else:
    d[i] += 1

ans = 0
for i in d.values():
  ans += i*(i-1)//2
print(ans)

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

public class Hello{
    public static void Main(){
        // Your code here!
        //var n = int.Parse(Console.ReadLine());
        var s = Console.ReadLine();
        var t = Console.ReadLine();
        int ans = 0;
        for(int i = 0; i < s.Length; i++){
            if(s[i].Equals(t[i])){
            }else{
                ans = ans + 1;
            }
        }
        
        Console.WriteLine(ans);
    }
}


Measured memory_bytes: 18304
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 
#define endl '\n'
#define ll long long
#define mod 1000000007
#define inf 1000000000000000000
int main()
{
	fastio;
	#ifdef APNA_IO
		freopen("input.txt" , "rt" ,stdin);
		freopen("output.txt" , "wt" ,stdout);
	#endif
	ll a,b,n;
	cin>>n>>a>>b;
	cout<<min(n*a,b)<<endl;
	return 0;
}





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

int main()
{
    int a, b, c;
    int count = 0;

    cin >> a >> b >> c;

    for (int i = a; i <= b; i++) {
        if (c % i == 0) {
            count++;
        }
    }

    cout << count << endl;

    return 0;
}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
int vector_finder(std::vector<ll> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

int main() {
  double N, K; cin >> N >> K;
  double ans = 0;
  double res = 1 / N;
  for(ll i = 1; i <= N; ++i) {
    ll tmp = i;
    double a = res;
    while(true) {
      if(tmp >= K) break;
      tmp *= 2;
      a *= 0.5;
    }
    ans += a;
  }
  cout << fixed << setprecision(15) << ans << endl;
}

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

typedef long long ll;

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod 1e9+7

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

ll n, a, b, ans = mod;
ll h[100001];

bool baku(int c) {
  ll d = 0;
  rep(i, 0, n) {
    if(h[i] > c * b) {
      d += ceil((h[i] - c * b) * 1.0 / (a - b));
    }
  }
  return c >= d ? true : false;
}

int main() {
  cin >> n >> a >> b;
  rep(i, 0, n) cin >> h[i];
  ll l = 0, r = 1000000000, m;

  while(l <= r) {
    m = (l + r) / 2;
    baku(m) ? ans = m, r = m - 1 : l = m + 1;
  }

  cout << ans << endl;
}


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

int main(void){
	int H,W;
	while(1){
		cin >> H >> W;
		if(H == 0 && W == 0) break;
		for(int i = 0;i < H;i++){			
			for( int j = 0;j < W;j++){
			cout << "#";
			}
		cout << endl;
		}
                cout << endl;
	}
	return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <utility>
#include <tuple>
#include <vector>

void DisplayCards(std::vector<std::tuple<char, int>>& cards) {
    for (int i = 0; i < cards.size(); i++) {
        std::cout << std::get<0>(cards[i])
                  << std::get<1>(cards[i]);
        if (i != cards.size() - 1 ) {
            std::cout << " ";
        }
        else {
            std::cout << std::endl;
        }
    }
}

std::vector<std::tuple<char, int>> GetInput() {
    int n;
    std::cin >> n;
    std::vector<std::tuple<char, int>> cards;
    for (int i=0; i<n; i++) {
        std::tuple<char, int> card;
        std::cin >> std::get<0>(card);
        std::cin >> std::get<1>(card);
        cards.push_back(card);
    }

    return cards;
}

std::vector<std::tuple<char, int>> BubbleSort(std::vector<std::tuple<char, int>> ary) {
    int n = ary.size();
    for(int i = 0; i < n; i++) {
        for (int j = n-1; j > i; j--) {
            if(std::get<1>(ary[j]) < std::get<1>(ary[j-1])) {
                std::swap(ary[j], ary[j-1]);
            }
        }
    }
    return ary;
}

std::vector<std::tuple<char, int>> SelectionSort(std::vector<std::tuple<char, int>> ary) {
    int n = ary.size();
    for (int i = 0; i < n; i++) {
        int min_ix = i;
        for (int j = i; j < n; j++) {
            if (std::get<1>(ary[j]) < std::get<1>(ary[min_ix])) {
                min_ix = j;
            }
        }
        if (i != min_ix) {
            std::swap(ary[i], ary[min_ix]);
        }
    }
    return ary;
}

void IsStable(std::vector<std::tuple<char, int>> ary1,
              std::vector<std::tuple<char, int>> ary2
              )
{
    if (ary1.size() != ary2.size()) {
        std::cout << "Size is not equal." << std::endl;
    }
    int n = ary1.size();

    for (int i = 0; i < n; i++) {
        if(ary1[i] !=  ary2[i]) {
            std::cout << "Not stable" << std::endl;
            return;
        }
    }
    std::cout << "Stable" << std::endl;
}

int main(int argc, char const* argv[])
{
    auto cards = GetInput();
    auto b_cards = BubbleSort(cards);
    DisplayCards(b_cards);
    std::cout << "Stable" << std::endl;
    auto i_cards = SelectionSort(cards);
    DisplayCards(i_cards);
    IsStable(b_cards, i_cards);
    return 0;
}

Measured memory_bytes: 3104
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <map>
#include <set>
#include <sstream>
#include <stdio.h>
#include <cstdio>
#include <cstring>

using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; i++)
#define rep(i,b) Rep(i,0,b)
#define rrep(i,a) for(int i = a; i >= 0; i--)
#define allof(a) (a).begin(), (a).end()

typedef long long ll;
const int inf = 1e9 + 7;
const ll infll = 1ll << 60ll;
const ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

/*
// 最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

// 最小公倍数
ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}*/


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

	int n;
	cin >> n;
	vector<int> a(n + 2);
	rep(i, n) cin >> a[i + 1];
	a[0] = 0;
	a[n + 1] = 0;
	vector<int> dif(n + 1, 0);

	rep(i, n + 1) {
		dif[i] = abs(a[i + 1] - a[i]);
	}

	int sum = 0;

	rep(i, n + 1) {
		sum += dif[i];
	}

	Rep(i, 1, n + 1) {
		int tmp = sum;
		// a[i]を通らない
		if (i == n) {
			tmp -= dif[n];
			tmp -= dif[n - 1];
			tmp += abs(a[n - 1]);

			cout << tmp << endl;
			continue;
		}

		tmp -= abs(a[i] - a[i - 1]);
		tmp -= abs(a[i + 1] - a[i]);
		tmp += abs(a[i - 1] - a[i + 1]);

		cout << tmp << endl;
	}

	return 0;
}

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

#define int             long long
#define FOR( i, m, n )  for( int (i) = (m); (i) < (n); (i)++ )
#define REP( i, n )     FOR( i, 0, n )
#define REPR( i, m )    for( int (i) = (m); (i) >= 0; (i)-- )
#define REPONE( i, n )  FOR( i, 1, n + 1 )
#define ALL( a )        (a).begin(), (a).end()
#define MP              make_pair

using namespace std;
using P = pair<int, int>;

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; }

const int INF = 1e18;
const int MOD = 1e9 + 7;

int dp[100001][3];

signed main(){
    int N; cin >> N;
    vector<array<int, 3> > happy( N );
    REP( i, N ){
        REP( j, 3 ){
            cin >> happy[i][j];
        }
    }

    REP( i, 3 ){
        dp[0][i] = happy[0][i];
    }

    FOR( i, 1, N ){
        REP( j, 3 ){
            chmax( dp[i][j], happy[i][j] + max( dp[i - 1][( j + 1 ) % 3], dp[i - 1][( j + 2 ) % 3] ) );
        }
    }

    cout << max( { dp[N - 1][0], dp[N - 1][1], dp[N - 1][2] } ) << endl;
}


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

int main() {
  int w;
  string s;
  cin >> s >> w;
  int n = s.size();
  string ans;
  for(int i=0;i<n;i += w){
    ans += s.at(i);
  }
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 256
n, m, x = map(int, input().split())
a = list(map(int, input().split()))

ans1 = 0
for i in range(0, x + 1):
    if i in a:
        ans1 += 1

ans2 = 0
for i in range(x, n + 1):
    if i in a:
        ans2 += 1

print(min(ans1, ans2))

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
struct Coordinate {
	int x, y;
	std::vector<Coordinate> neighbors()const { return { Coordinate{x + 1, y}, Coordinate{x - 1, y}, Coordinate{x, y + 1}, Coordinate{x, y - 1} }; }
	Coordinate operator-(const Coordinate& that) const { return Coordinate{ x - that.x, y - that.y }; }
	Coordinate operator+(const Coordinate& that) const { return Coordinate{ x + that.x, y + that.y }; }
	bool operator==(const Coordinate& that) const { return x == that.x && y == that.y; }
	bool operator<(const Coordinate& that) const { return x == that.x ? y < that.y : x < that.x; }
};

int main() {
	std::cin.tie(0); std::cin.sync_with_stdio(false);
	while (true) {
		int w, h; std::cin >> w >> h; if (w == 0 && h == 0) break;
		Coordinate takayuki, kazuyuki; std::cin >> takayuki.x >> takayuki.y >> kazuyuki.x >> kazuyuki.y;
		std::vector<std::vector<int>> state(h + 2, std::vector<int>(w + 2, 1));
		for (auto i = 1; i <= h; ++i) for (auto j = 1; j <= w; ++j) std::cin >> state[i][j];
		if (takayuki == kazuyuki) {
			std::cout << 0 << '\n';
			continue;
		}
		auto comparator = [](const std::pair<Coordinate, Coordinate>& a, const std::pair<Coordinate, Coordinate>& b) {return a.first == b.first ? a.second < b.second : a.first < b.first; };
		std::set<std::pair<Coordinate, Coordinate>> memo;
		std::queue<std::pair<Coordinate, Coordinate>> queue; queue.emplace(takayuki, kazuyuki);
		bool meet = false;
		for (auto i = 1; i <= 100 && !meet; ++i) {
			for (int j = queue.size(); j > 0 && !meet; --j) {
				auto first = queue.front().first;
				auto second = queue.front().second; queue.pop();
				for (auto next_first : first.neighbors()) {
					auto next_second = second + (first - next_first);
					if (state[next_first.y][next_first.x] == 0 || state[next_second.y][next_second.x] == 0) {
						if (state[next_first.y][next_first.x] == 1) next_first = first;
						if (state[next_second.y][next_second.x] == 1) next_second = second;
						if (next_first == next_second) {
							std::cout << i << '\n';
							meet = true;
							break;
						}
						auto pair = memo.emplace(next_first, next_second);
						if (pair.second) {
							queue.emplace(next_first, next_second);
						}
					}
				}
			}
		}
		if (!meet) {
			std::cout << "NA\n";
		}
	}
}



Measured memory_bytes: 14004
nums = list(map(int, input().split()))
a = nums[0]
b = nums[1]
c = nums[2]
d = nums[3]

L = a+b
R= c+d
if L > R :
    print('Left')
elif L == R : 
    print('Balanced')
elif L < R :
    print('Right')
    


Measured memory_bytes: 3060
<?php
list($n, $m) = ints();
for ($i = 0; $i < $n; ++$i) list($x[], $y[], $z[]) = ints();
$max = PHP_INT_MIN;
for ($i = 0; $i < 2 ** 3; ++$i) {
    for ($j = 0; $j < 3; ++$j) {
        if ($i >> $j & 1) {
            $d[$j] = 1;
        } else {
            $d[$j] = -1;
        }
    }
    for ($j = 0; $j < $n; ++$j)
        $t[$j] = $d[0] * $x[$j] + $d[1] * $y[$j] + $d[2] * $z[$j];
    list($_x, $_y, $_z) = [$x, $y, $z];
    array_multisort($t, SORT_DESC, $_x, $_y, $_z);
    $_x = array_slice($_x, 0, $m);
    $_y = array_slice($_y, 0, $m);
    $_z = array_slice($_z, 0, $m);
    $max = max($max, score([array_sum($_x), array_sum($_y), array_sum($_z)]));
}
echo $max;
function score($a)
{
    return array_sum(array_map('abs', $a));
}
function ints()
{
    return array_map('intval', explode(' ', trim(fgets(STDIN))));
}


Measured memory_bytes: 16492
M=int(input())
#Get the number that needs to be handled
num=''
D,C=[],[]
for _ in range(M):
    D1,C1=map(int, input().split())
    D.append(D1)
    C.append(C1)
S = sum(d * c for d, c in zip(D, C))
print (sum(C)-1+(S-1)//9)

Measured memory_bytes: 12612
#include <cstdlib>
#include <cstdio>

int main(void) {
  int n;
  scanf("%d", &n);
  int a[n];
  for (int i = 0; i < n; i++)
    scanf("%d", &a[i]);
  
  long long min = 2, max = 2;
  bool noSolution = false;
  for (int i = n - 1; i >= 0; i--) {
    if (min % a[i] != 0)
      min = min / a[i] * a[i] + a[i];
    max = max / a[i] * a[i] + a[i] - 1;
    //printf("%lld %lld\n", min, max);
    if (min > max)
      noSolution = true;
  }
  
  if (noSolution)
    printf("-1\n");
  else
    printf("%lld %lld\n", min, max);
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define P(x) cout << (x) << "\n"
#define p(x) cout << (x)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define vv(type, c, m, n, i) vector<vector<type>> c(m, vector<type>(n, i))
#define rep(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define rrep(i,a,n) for(int i=(a), i##_len=(n); i>i##_len; --i)
#define len(x) ((int)(x).size())
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
#define chmax(a,b) if(a<b)a=b
#define chmin(a,b) if(a>b)a=b
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> pii;
void square() {
	ll N; cin >> N;
	vi h(N); rep(i, 0, N) cin >> h[i];
	stack<pair<ll, ll>> st;
	st.emplace(-1, -1);
	ll ans = 0;
	rep(i, 0, N) {
		if (st.top().first == h[i])
			continue;
		ll pos = i;
		while (st.top().first >= h[i]) {
			chmax(ans, st.top().first*(i - st.top().second));
			pos = st.top().second;
			st.pop();
		}
		st.emplace(h[i], pos);
	}
	while (st.size()) {
		chmax(ans, st.top().first*(N - st.top().second));
		st.pop();
	}
	P(ans);
}
int main() {
	square();
	return 0;
}

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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define repr(i,n) for(int i=(int)(n-1);i>=0;i--)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout << #x" = " << x << endl
#define print(x) cout << x << endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<int, P> PIP;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;
typedef set<int> S;

#define INF INT_MAX/3
#define MAX_N 1000000001

int w, h;
vector<string> island(51);
P land[51][51];
int dd[] = {1, 0, -1, 0, 1};

bool range(int y, int x) {
  return 0 <= y && y < h && 0 <= x && x < w;
}

void dfs(int y, int x, bool b) {
  if(b) land[y][x].fi = 1;
  else land[y][x].se = 1;

  int yy, xx;
  rep(i, 4) {
    yy = y + dd[i], xx = x + dd[i + 1];
    if (range(yy, xx)) {
      if (b) {
        if (island[yy][xx] == '.' && land[yy][xx].fi == 0) dfs(yy, xx, b);
      } else {
        if (island[yy][xx] == '.' && land[yy][xx].se == 0) dfs(yy, xx, b);
      }
    }
  }
}

int main(){
  cin.sync_with_stdio(false);
  while(cin >> w >> h, w | h) {
    rep(i, h) cin >> island[i];
    rep(i, h)rep(j, w) land[i][j] = P(0, 0);
    rep(i, h)rep(j, w) {
      if (island[i][j] != '.') land[i][j] = P(1, 1), dfs(i, j, island[i][j] == 'B');
    }

    int black = 0, white = 0;
    rep(i, h)rep(j, w) {
      if (land[i][j].fi == 1 && land[i][j].se == 0) black++;
      if (land[i][j].fi == 0 && land[i][j].se == 1) white++;
    }

    cout << black << " " << white << endl;
  }


  return 0;
}

Measured memory_bytes: 3204
def get_i() #空白区切の入力を数値(整数)の配列で返す
  return gets.chomp.split(" ").map(&:to_i)
end
def get_f() #空白区切の入力を数値(実数)の配列で返す
  return gets.chomp.split(" ").map(&:to_f)
end
def get() #空白区切の入力を文字列の配列で返す
  return gets.chomp.split(" ")
end
def get_nsp() #入力されたものを一文字ずつに区切った文字列の配列で返す
  return gets.chomp.split("")
end
def yn_judge(bool,y="Yes",n="No") #boolに真偽を投げることで、trueならy、falseならnの値を出力する
  return bool ? y : n 
end
def array(size,n=1,init=nil) #nに配列の次元数、sizeに配列の大きさ、initに初期値を投げることでその配列を返す
  if n==1
    return Array.new(size){init}
  else
    return Array.new(n).map{Array.new(size){init}}
  end
end

s=get_nsp
p=gets.chomp
n=s.size
m=p.split("").size
flag=false
n.times do|i|
  j=i
  temp=""
  m.times do|k|
    if j+1<n
      j+=1
    else
      j=0
    end 
    temp+=s[j]
  end 
  if temp==p
    flag=true
    break
  end
end
puts yn_judge(flag)


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

int main() {
  int n,m;
  cin >> n >> m;
  vector<ll> a(n),b(n),c(m),d(m);
  for(int i=0;i<n;i++) {
    cin >> a[i] >> b[i];
  }
  for(int i=0;i<m;i++) {
    cin >> c[i] >> d[i];
  }
  for(int i=0;i<n;i++) {
    ll ans=0,num=0,min=llabs(a[i]-c[0])+llabs(b[i]-d[0]);
    for(int j=1;j<m;j++) {
      ans = llabs(a[i]-c[j])+llabs(b[i]-d[j]);
      if(ans<min) {
        min=ans;
        num=j;
      }
    }
    cout << num+1 << endl;
  }
}

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

using namespace std;

int main() {
  int n;
  cin >> n;
  int a[n], b[n];
  for (int i = 0; i < n; ++i) cin >> a[i];
  b[0] = n - 1;
  for (int i = 1; i < n; ++i) b[i] = b[i - 1] - 2;
  for (int i = n / 2 + (n % 2); i < n; ++i) b[i] = b[i] * (-1);
  sort(a, a + n);
  sort(b, b + n);
  bool check = true;
  for (int i = 0; i < n; ++i) if (a[i] != b[i]) {
    check = false;
    break;
  }
  int ans = 1, mod = (int) 1e9 + 7;
  if (check) for (int i = 0; i < n / 2; ++i) ans = (ans * 2) % mod;
  else ans = 0;
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;

vector<pair<int,int> >vec;
bool com(pair<int,int>p1, pair<int,int>p2){
    return p1.first>p2.first;
}
int main()
{
    int N;
    while(cin>>N,N){
        vec.clear();
        for(int i=0;i<N;i++){
            int r,w;
            cin>>r>>w;
            vec.push_back(make_pair(r,w));
        }
        sort(vec.begin(),vec.end(),com);
        int tot=0;
        for(int i=1;i<vec.size();i++)
            tot+=vec[i].first;
        int ans=0;
        for(int i=0;i<vec.size();i++){
            ans+=vec[i].first;
            ans+=vec[i].second;
        }
        if(vec[0].first>tot){
            int left=vec[0].first-tot;
            bool dp[1001]={false};
            dp[0]=true;
            int m=left;
            for(int i=1;i<N;i++){
                for(int j=left;j>=vec[i].second;j--){
                    dp[j]|=dp[j-vec[i].second];
                    if(dp[j])
                        m=min(m,left-j);
                }
            }
            ans+=m;
        }
        else{
            
        }
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 1216
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(long long (i)=0;(i)<(n);++(i))
#define ref(i,a,b) for (long long (i)=(a); (i)<=(b); ++(i))
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define mp make_pair
const int mx=150;
int dp[mx][mx][2],r,c,a[mx][mx];

void dfs(int x,int y,int son,int say){

	if(dp[x][y][son]<=say)return;
	dp[x][y][son]=say;

	if(x==r+1 or y==c+1)return;

	if(a[x+1][y]==0 and son==0)dfs(x+1,y,1,say+1);
	else if(a[x+1][y]==0 and son==1)dfs(x+1,y,1,say);
	else if(a[x+1][y]==1)dfs(x+1,y,0,say);
	
	if(a[x][y+1]==0 and son==0)dfs(x,y+1,1,say+1);
	else if(a[x][y+1]==0 and son==1)dfs(x,y+1,1,say);
	else if(a[x][y+1]==1)dfs(x,y+1,0,say);
	
	return;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> r >> c;
	for(int i=1;i<=r;++i){
		for(int j=1;j<=c;++j){
			char s;cin >> s;// 0 black     1 white
			if(s=='#')a[i][j]=0;
			else if(s=='.')a[i][j]=1;
		}
	}
	for(int i=0;i<mx;++i)
		for(int j=0;j<mx;++j)
			for(int k=0;k<2;++k)
				dp[i][j][k]=INT_MAX;
	if(a[1][1]==1)
		dfs(1,1,0,0);
	else if(a[1][1]==0)
		dfs(1,1,1,1);	
	

	cout <<	min(dp[r][c][0],dp[r][c][1]) << endl;
}
	


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,(n)-1,0)
#define FOR(i,a,b) for(int i=(a),i##Len_=(b);i<i##Len_;i++)
#define RFOR(i,a,b) for(int i=(a),i##End_=(b);i>=i##End_;i--)
#define ALL(x) (x).begin(),(x).end()
const char* LF = "\n";
namespace{struct _{_(){
    cin.tie(0);
    ios::sync_with_stdio(false);
}}a;}

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

    vector<int> R(N, 0);
    int sum = 0;
    REP(i, N) {
        if (S[i] == 'W') sum++;
        R[i] = sum;
    }

    sum = 0;
    RREP(i, N) {
        if (S[i] == 'E') sum++;
        R[i] += sum;
    }

    sort(ALL(R));
    cout << R[0] - 1 << LF;

    return 0;
}


Measured memory_bytes: 1812
#include<iostream>

using namespace std;
int calcGcd(int a, int b){
    int d;
    if((a % b) == 0){
        return b;
    }else{
        d = calcGcd(b, a%b);
    }
    return d;
    
}

int main(){
    int a,b;

    while(cin >> a >> b){
        if(b > a){
            swap(b,a);
        }
        int gcd = calcGcd(a, b);
        int lcm = a/gcd * b;
        cout << gcd << " " << lcm << endl;
    }

    return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
using P=pair<long long,long long>;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
const ll MOD= 1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);  
  
  ll k;
  cin >> k;
  ll ans=0;
  for(ll a=1;a<=k;a++){
    for(ll b=1;b<=k;b++){
      for(ll c=1;c<=k;c++){
        ll res=gcd(a,gcd(b,c));
        ans+=res;
      }
    }
  }
  cout << ans << endl;
  
}


Measured memory_bytes: 3636
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#define INF 1000000007LL
using namespace std;


int main()
{
	int n, e;
	long long int ans;
	char s1[52], s2[52];
	scanf("%d", &n);
	scanf("%s", s1);
	scanf("%s", s2);
	int i=0;
	while(i<n){
		if(i==0 && s1[0]!=s2[0]){
			ans=6;
			e=1;
			i++;
			i++;
		}else if(i==0 && s1[0]==s2[0]){
			ans=3;
			e=2;
			i++;
		}else if(s1[i]==s2[i]){
			if(e==1){
				e=2;
				i++;
			}else{
				ans=ans*2%INF;
				e=2;
				i++;
			}
		}else{
			if(e==1){
				ans=ans*3%INF;
				e=1;
				i++;
				i++;
			}else{
				ans=ans*2%INF;
				e=1;
				i++;
				i++;
			}
		}
	}
	printf("%lld\n", ans);

	return 0;
}

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

int main(){
 	int n;
	cin >>n;
	vector<string> a(n);
	vector<int> v(n*26);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		
		for(char s : a[i]) {
			if(s >= 'a' && s <= 'z')
				v[i*26+(s-'a')]++;
		}
	}
	for(int i = 0; i < 26; i++) {
		int min = 50;
		for(int j = 0; j < n; j++) {
			if(min > v[j*26+i])
				min = v[j*26+i];
		}
		v[i] = min;
	}
	for(int i = 0; i<26;i++)
		for(int j = 0; j < v[i]; j++)
			cout << (char)('a'+i);
	cout << endl;
	
}

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

using namespace std;

int main()
{
  int n; cin >> n;
  string s; cin >> s;
  vector<char> vc(s.size());
  for (int i = 0; i < s.size(); i++)
  {
    char ci = s[i];
    int m = n;
    if (ci + m > 'Z') m -= 26;
    vc[i] = (char)((ci+m));
  }
  for (auto c : vc) cout << c;
  cout << endl;
}

Measured memory_bytes: 3632
# For taking integer inputs.
import math
from decimal import Decimal
from itertools import permutations


def inp():
    return(int(input()))


# For taking List inputs.
def inlist():
    return(list(map(int, input().split())))


# For taking string inputs. Actually it returns a List of Characters, instead of a string, which is easier to use in Python, because in Python, Strings are Immutable.
def instr():
    s = input()
    return(list(s[:len(s)]))


# For taking space seperated integer variable inputs.
def invr():
    return(map(int, input().split()))


n, k = invr()

c = k * (k-1)**(n-1)

print(c)


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

int main(){
  int n;
  cin >> n;
  int l[110];
  for(int i = 0;i < n;i++){
    cin >> l[i];
  }

  sort(l, l+n);

  int rui = 0;
  for(int i = 0;i < n-1;i++){
    rui += l[i];
  }


  if(rui > l[n-1]){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a, sum = 0;
  for(int i = 0; i < 3; i++){
    scanf("%d", &a);
    sum = (sum * 10) + a;
  }
  printf("%s\n", (sum % 4 == 0) ? "YES" : "NO");
  return 0;
}


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

#define lld long long
#define pii pair<int,int>
#define pb push_back
#define next nextt
#define Inf 1000000000

using namespace std;

int N;
lld sx,sy,ex,ey;
lld x[1002],y[1002],r[1002];
bool check[1002];
double dis[1002][1002];
double d[1002],ans;
priority_queue<pair<double,int>,vector<pair<double,int>>,greater<pair<double,int>>> q;

double calc(lld tx,lld ty,int num){
	lld tmp;
	tmp = (tx-x[num])*(tx-x[num]) + (ty-y[num])*(ty-y[num]);
	return max(sqrt(tmp)-r[num],(double)0);
}

int main(){
	scanf("%lld %lld %lld %lld",&sx,&sy,&ex,&ey);
	scanf("%d",&N);
	ans = (sx-ex)*(sx-ex) + (sy-ey)*(sy-ey);
	ans = sqrt(ans);
	for(int i=1; i<=N; i++){
		scanf("%lld %lld %lld",&x[i],&y[i],&r[i]);
		q.push({calc(sx,sy,i),i});
		d[i] = calc(sx,sy,i);
	}
	for(int i=1; i<=N; i++){
		for(int j=1; j<=N; j++){
			lld tmp;
			tmp = (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
			dis[i][j] = max(sqrt(tmp)-r[i]-r[j],(double)0);
		}
	}
	while(!q.empty()){
		int v = q.top().second;
		q.pop();
		if(check[v]) continue;
		check[v] = true;
		for(int i=1; i<=N; i++){
			if(d[i] > d[v]+dis[v][i]){
				d[i] = d[v]+dis[v][i];
				q.push({d[i],i});
			}
		}
	}
	for(int i=1; i<=N; i++) ans = min(ans,d[i]+calc(ex,ey,i));
	printf("%.14f\n",ans);

	return 0;
}


Measured memory_bytes: 13936