akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>


using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define REPO(i, n) for(int i = 1;i <= n;i++)
#define ll long long
#define INF 1999999999
#define MINF -1999999999
#define INF64 1999999999999999999
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007

ll n, s[10],ans = INF64,in[10],ii[4];

void dfs(ll a, ll b) {
	s[a] = b;
	if (a == n - 1) {
		ll x[4] = {}, y[4] = {},na = 0;
		REP(i, n) {
			x[s[i]] += in[i];
			y[s[i]]++;
		}
		if (y[0] > 0 and y[1] > 0 and y[2] > 0) {
			REP(i, 3) {
				na += abs(x[i] - ii[i]) + (y[i] - 1) * 10;
			}
			ans = min(ans, na);
		}
	}
	else {
		dfs(a + 1, 0);
		dfs(a + 1, 1);
		dfs(a + 1, 2);
		dfs(a + 1, 3);
	}
}


int main() {
	cin >> n;
	REP(i, 3)cin >> ii[i];
	REP(i, n)cin >> in[i];
	dfs(0, 0);
	dfs(0, 1);
	dfs(0, 2);
	dfs(0, 3);
	cout << ans << endl;
}




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

int fa[maxn], dis[maxn];

int find(int x)
{
	if(fa[x] == x) return x;
	int t = fa[x];
	fa[x] = find(fa[x]);
	dis[x] += dis[t];
	return fa[x];
}

int main(int argc, char** argv)
{
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i=0; i<n; i++) fa[i] = i;
	for(int i=0; i<m; i++)
	{
		int l, r, d;
		scanf("%d%d%d", &l, &r, &d);
		int x = find(--l), y = find(--r);
		if(x == y && dis[l] - dis[r] != d)
		{
			puts("No");
			return 0;
		}
		if(x != y)
			fa[x] = fa[y], dis[x] = d + dis[r] - dis[l] + dis[y];
	}
	puts("Yes");
	return 0;
}

Measured memory_bytes: 896
while True:
    try:
        r = int(input())

        count = 0

        for x in range(10):
            for y in range(10):
                for z in range(10):
                    for w in range(10):
                        if x + y + z + w == r:
                            count += 1
        print(count)
        
    except EOFError:
        break



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

int main()
{
  int h, w;
  cin >> h >> w;
  vector<string> vs(h);
  for (int i = 0; i < h; i++)
  {
    cin >> vs.at(i);
  }
  string sharp;
  for (int i = 0; i < w+2; i++)
  {
    sharp += "#";
  }
  cout << sharp << endl;
  for (int i = 0; i < h; i++)
  {
    cout << "#";
    for (int j = 0; j < w; j++)
    {
      cout << vs.at(i).at(j);
    }
    cout << "#" << endl;
  }
  cout << sharp << endl;

  return 0;
}


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

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(a) max((a),-(a))
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repe(i,n) rep(i,(n)+1)
#define per(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define pere(i,n) rep(i,(n)+1)
#define all(x) (x).begin(),(x).end()
#define SP <<" "<<
#define RET return 0
#define MOD 1000000007
#define INF 1000000000000000000

typedef long long LL;
typedef long double LD;

int main(){
  int n;
  cin >> n;
  vector<int> a(9);
  int x;
  for(int i=0;i<n;i++){
    cin >> x;
    a[min(x/400,8)]++;
  }
  int count=0;
  for(int i=0;i<8;i++){
    if(a[i]>0) count++;
  }
  cout << max(count,1) SP count+a[8] << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i <(n) ; ++i)
#define PI 3.14159265
#define INF 2147483647
using namespace std;
using ll = long long;
void self_max(int &a,int b){
	a = max(a,b);
}
void self_min(int &a,int b){
	a = min(a,b);
}
int main(){
	int a,b; cin >> a >> b;
	cout << 6 - a -b << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include <math.h>
#include <algorithm>
#include<queue>
#include<map>
//#include <bits/stdc++.h>


using namespace std;

#define FOR(i,a,b) for(int i=(a),i##formax=(b);i<i##formax;i++)
typedef long long ll;

main(){
    ll n,i,di;
    vector<ll> d;
    ll knum;
    cin >> n;
    for(i=0;i<n;i++){
        cin >> di;
        d.push_back(di);
    }
    sort(d.begin(),d.end());
    if(d[n/2-1]==d[n/2]){cout << 0 << endl;}
    else{
        knum = d[n/2] - d[n/2-1] ;;
        cout << knum << endl; 
        }
}

Measured memory_bytes: 1400
MOD = 10 ** 9 + 7
dogs, monkeys = gets.split.map(&:to_i)
if (dogs - monkeys).abs > 1
  count = 0
else
  count = (1..dogs).inject(1) { |a, b| a * b % MOD } * (1..monkeys).inject(1) { |a, b| a * b % MOD } % MOD
  count = count * 2 % MOD if dogs == monkeys
end
puts count


Measured memory_bytes: 1788
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<climits>
#include<set>

using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;
typedef pair<ll, ll> pll;
int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };
#define MOD 1000000007
#define ARRAY_MAX 100005

const double INF = 1e15 + 7;

typedef pair<ll, double> plld;

typedef struct edge {

	int to;
	double cost;

}EDGE;

void dijkstra(int n, vector<vector<EDGE> >& G, int x,vector<double>& d) {
	/*頂点の個数、辺の情報、始点となる頂点、最短距離の情報*/

	/*最終的にdは経由点からの最短距離が格納される、その過程では暫定的な最短距離が格納され、最短距離が見つかれば、その都度更新される*/

	//vector<ll> d(n,INF);/*最終的な最短距離を保持、初期化はINF*/
	d[x] = 0;
	priority_queue<plld, vector<plld>, greater<plld> > que;/*vectorのpriority_queueで暫定的な最短距離が小さい順に取り出す*/
	que.push(plld(0, x));/*経由点からダイクストラを適用するので経由点の暫定的な最短距離のコストは0*/

	while (!que.empty()) {/*queが空になれば最短距離が全て探索できたことになる*/

		plld p = que.top();/*最短距離の１番小さいものの取り出し*/
		que.pop();/*取り出したので調べたとみなし、queから出す*/
		int v = p.second;/*取り出した頂点の番号*/
		if (d[v] < p.first) {
			/*取り出した頂点からの最短距離よりも短い経路があるので更新の必要はない*/
			continue;
		}

		for (int i = 0; i < G[v].size(); i++) {
			/*取り出した頂点から辺でつながっている頂点への最短距離を調べて現在の値より短ければ更新する*/
			EDGE e = G[v][i];/*取り出した頂点からつながっている頂点を1つ取り出す*/
			if (d[e.to] > d[v] + e.cost) {
				/*現在の最短距離よりも、現在の頂点を経由する経路のほうが最短距離が短い場合は最短距離を更新し、次の頂点を調べる*/
				d[e.to] = d[v] + e.cost;/*最短経路の更新*/
				que.push(plld(d[e.to], e.to));/*先の頂点を調べるためqueに格納*/
			}
		}
	}
}



int main() {


	ios::sync_with_stdio(false);
	cin.tie(0);
	double xs, ys, xt, yt;
	int n;
	cin >> xs >> ys >> xt >> yt >> n;

	vector<vector<EDGE> > G(n+2);/*n個の各頂点からそれ以外の頂点へのコスト*/
	vector<double> d(n+2, INF);/*最短経路*/
	vector<double> x(n + 2), y(n + 2), r(n + 2);//(x,y),半径

	x[0] = xs;
	y[0] = ys;
	r[0] = 0;

	for (int i = 1; i <= n; i++)
	{
		cin >> x[i] >> y[i] >> r[i];
	}
	x[n+1] = xt;
	y[n+1] = yt;
	r[n+1] = 0;

	for (int i = 0; i <= n + 1; i++) 
	{
		for (int j = i + 1; j <= n + 1; j++) 
		{
			double len = sqrt((x[j] - x[i])*(x[j] - x[i]) + (y[j] - y[i])*(y[j] - y[i]));
			double radius = r[i] + r[j];
			double dis = max(0.0,len - radius);
			G[i].push_back(EDGE{ j,dis });
			G[j].push_back(EDGE{ i,dis });
		}
	}

	dijkstra(n, G, 0, d);

	printf("%.12f\n", d[n + 1]);

	return 0;
}

Measured memory_bytes: 22000
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<(int)(r); i++)
#define rep_eq(i,l,r) for(int i=l; i<=(int)(r); i++)
#define all(vec) vec.begin(),vec.end()
#define allr(vec) vec.rbegin(),vec.rend()
using namespace std;

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

using ll=int64_t;

using vb=vector<bool>;
using vc=vector<char>;
using vs=vector<string>;
using vi=vector<int>;
using vll=vector<ll>;
using vvi=vector<vi>;

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

  ll x,y; cin >>x >>y;
  ll ans=1LL<<60;
  if (x<=y) {
    ans=min(ans,y-x);
  }
  if (-x<=y) {
    ans=min(ans,y+x+1);
  }
  if (x<=-y) {
    ans=min(ans,-y-x+1);
  }
  if (-x<=-y) {
    ans=min(ans,-y+x+2);
  }

  cout <<ans <<'\n';
  return 0;
}


Measured memory_bytes: 3640
#include <cstdio>
#include <iostream>
#include <cassert>
#include <string>
#include <algorithm>
#include <cstring>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <deque>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;

int main() {
    LL A, B;
    scanf("%lld %lld", &A, &B);
    printf("%lld\n", A * B / __gcd(A, B));

    return 0;
}


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

bool comp(pair<int, int> a, pair<int, int> b){
    if(a.second != b.second) return a.second < b.second;
    else return a.first > b.first;
}

void solve(){
    LL h,n;
    cin >> h >> n;

    const LL II = pow(10,18) + 11;

    vector<pair<LL,LL>> magic(n);

    LL max = -1;

    for(LL i = 0; i < n; ++i){
        cin >> magic[i].first >> magic[i].second;
        if(max < magic[i].first) max = magic[i].first;
    }

    vector<LL> dp(h + max,II);

    dp[0] = 0;

    for(LL i = 0; i < h + max; ++i){
        for(LL j = 0; j < n; ++j){
            if(i + magic[j].first >= h + max) continue;
            dp[i + magic[j].first] = min(dp[i] + magic[j].second, dp[i + magic[j].first]);
        }
    }

    LL ans = II;

    for(LL i = h; i < h + max; ++i){
        if(ans > dp[i]) ans = dp[i];
    }

    cout << ans << endl;

}

int main(){
    solve();

    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int min = 1024;
    int index = -1;
    vector<int> n(5);
    for (int i = 0; i < 5; i++) {
        cin >> n[i];
        if (n[i] % 10 < min && n[i] % 10 != 0) {
            index = i;
            min = n[i] % 10;
        }
    }

    int ans = 0;
    for (int i = 0; i < 5; i++) {
        if (i == index || n[i] % 10 == 0) {
            ans += n[i];
        } else {
            ans += n[i] + (10 - n[i] % 10);
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
 //Compiler version g++ 6.3.0

 int main() {
	 long long int n,k;
	 cin >> n >>k;
	 long long int ans=0;
	 for(int i=1;i<=n;i++){
		 long long int b=114514*k-i;
		 if(2*b%k==0){
			 long long int p =i%k;
			 if(p==0){
				 p=k;
			 }
			 long long int x=(n-p)/k+1;
			 ans=ans+x*x;
		 }
	 }
	 cout << ans << endl;
 }

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int a = sc.nextInt();
    int b = sc.nextInt();
    int digit_sum; // 各桁の和
    int sum = 0;
    String strN;
    int len; // 桁の長さ

    for(int i = 1; i <= N; i++) {
      strN = String.valueOf(i);
      char[] cN = strN.toCharArray();
      len = cN.length;
      digit_sum = 0;
      for(int j = 0; j < len; j++) {
        int d = Character.getNumericValue(cN[j]);
        digit_sum += d;
      }
      if(digit_sum >= a && digit_sum <= b) {
        sum += i;
      }
    }

    System.out.println(sum);
  }
}


Measured memory_bytes: 22100
while  True:
    inputs = input().split()
    a = int(inputs[0])
    op = inputs[1]
    b = int(inputs[2])

    if op == "?":
        break

    result = 0
    if op == "+":
        result = a + b
    elif op == "-":
        result = a - b
    elif op == "*":
        result = a * b
    elif op == "/":
        result = int(a / b)
    print(result)

Measured memory_bytes: 7648
#include <stdio.h>

int main(void)
{
  int a,b;
  double x;
  int Xdami;
  double han;

  scanf("%d %d",&a, &b);
  x = (a+b) / 2.0;
  Xdami = x;
  han = x - Xdami;
  if(han == 0)
  {
    printf("%d\n",Xdami);
  }else{
    printf("%d\n",Xdami+1);
  }
}

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

#define FOR(i, a, b) for (int i=a; i<b; i++)
#define For(i, a) for (int i=0; i<a; i++)
#define FORR(i,a,b) for (int i = a; i >= b; i--)
#define Forr(i,a) for (int i = a; i >= 0; i--)

#define deb(...) cerr << "[" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__)
void DBG() { cerr << "]\n";}
template<typename T, typename ...Args> void DBG(T first, Args... args)
{cerr << first; if(sizeof...(args))cerr<<", "; DBG(args...); }

void solve(){
  int n; cin >> n;
  vector<pair<int,int>> v;
  For(i,n){
    int x,y;
    cin >> x >> y;
    v.push_back({x,y});
  }
  for(int i=0;i+2<n;i++){
    if(v[i].first==v[i].second && v[i+1].first==v[i+1].second && v[i+2].first==v[i+2].second){
      cout << "Yes\n";
      return;
    }
  }
  cout << "No\n";
}


int32_t main(){
  ios_base:: sync_with_stdio(false);
  cin.tie(0);
  int t=1;
  for(int tt=1;tt<=t;tt++){
    solve();
  }
}

Measured memory_bytes: 3656
#include <iostream>
#include <string>
#include <algorithm>
#include <utility> 
#include <unordered_set>
#include <vector>
#include <list> 
#include <string>
#include <iterator> 
#include <deque>
#include <array>
#include <forward_list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <climits>
#include <bitset>
#include <numeric>
using namespace std;


const long double PI = 3.14159265358979323846264338327950;
const int N = 2 * 1e5;


template <class T>
T gcd(T a, T b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}


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

	int n;
	double l, h, w;
	scanf("%d", &n);
	 l = (double)n / 3.0;
	 w = (double)(n - l) / 2.0;
	 h = n - l - w;
	printf("%.6f\n", l * w * h);

}


Measured memory_bytes: 3836
/* ---------- STL Libraries ---------- */
// IO library
#include <cstdio>

#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>

#include <cmath>
#include <numeric>
#include <random>
#include <cstring>

// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
#include <stack>

// type
#include <cstdint>

/* ---------- Namespace ---------- */
using namespace std;

/* ---------- Type ---------- */
using ll = long long;
#define int ll
#define P pair<ll, ll>

/* ---------- Constants  */
const double PI = 3.141592653589793238462643383279;
const ll MOD = 1e9 + 7;
const int INF = 1LL << 55;

/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */
signed main() {
    int N, M;
    cin >> N >> M;
    vector<P> A(M);
    for (int i = 0; i < M; i++) {
        int p;
        string str;
        cin >> p >> str;
        p--;
        int q = str == "WA" ? -1 : 1;
        A[i] = P(p, q);
    }
    //sort(A.begin(), A.end());

    vector<int> ac(N, 0);
    vector<int> wa(N, 0);

    for (int i = 0; i < M; i++) {
        if (A[i].second == -1) {
            if (ac[A[i].first] == 0) {
                wa[A[i].first]++;
            }
        } else {
            if (ac[A[i].first] == 0) ac[A[i].first]++;
        }
    }

    int a = 0;
    int w = 0;
    for (int i = 0; i < N; i++) {
        a += ac[i];
        if (ac[i] > 0) w += wa[i];
    }

    cout << a << " " << w << endl;
    return 0;
}

Measured memory_bytes: 3328
S = input()
T = input()

for i in range(len(S) - len(T) + 1):
    if i == 0:
        seq = S[-len(T)-i:]
    else:
        seq = S[-len(T)-i:-i]
    for j in range(len(T)):
        if seq[j] == "?":
            seq = seq[:j]+T[j]+seq[j+1:]

    if seq == T:
        if i == 0:
            print((S[:-len(T)-i]+T).replace("?", "a"))
        else:
            print((S[:-len(T)-i]+T+S[-i:]).replace("?", "a"))
        exit()

print("UNRESTORABLE")

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

int main() {
  int a, b;
  cin >> a >> b;
  if((a+b) % 2 == 0) cout << (a+b) / 2 << endl;
  else cout << "IMPOSSIBLE" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<functional>
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<string>
#include<math.h>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,x,n) for(int i=x;i<n;i++)
using namespace std;
const int INF=100000000;
char a[100][100];
int h,w;
void dfs(int x,int y,char f){
  if(x<0||y<0||x>=w||y>=h)return ;
  if(a[y][x]==f){
    a[y][x]='$';
  }else return ;
  dfs(x+1,y,f);
  dfs(x-1,y,f);
  dfs(x,y+1,f);
  dfs(x,y-1,f);
}
int main(){
  while(cin>>h>>w,h!=0){
    rep(i,h)rep(j,w)cin>>a[i][j];
    int ans=0;
    rep(i,h)rep(j,w){
      if(a[i][j]!='$'){
	dfs(j,i,a[i][j]);
	ans++;
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}

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

#define MAX 1000000
int insertSort(int A[],int n,int g){
    int cnt=0;
    for(int i=g;i<n;i++){
        int v = A[i];
        int j = i -g;
        while(j >= 0 && A[j] > v){
            A[j+g] = A[j];
            j = j-g;
            cnt++;
        }
        A[j+g] = v;
    }

    return cnt;
}

void shellSort(int A[],int n){
    int cnt = 0;
    int G[MAX],count = 0,m;
    for(m=1;m*3+1<n;m=m*3+1);

    for( ;m>0;m=(m-1)/3){
        G[count++] = m;
    }
    cout << count << endl;
    for(int i=0;i<count;i++){
        cnt +=insertSort(A,n,G[i]);
        if(i) cout << " ";
        cout << G[i];
    }
    cout << endl << cnt << endl;

    for(int i=0;i<n;i++){
        cout << A[i] << endl;
    }
}

int main(){
   
    int n;
    cin >> n;
    int A[n];
    for(int i=0;i<n;i++){
        cin >> A[i];
    }
    shellSort(A,n);
    return 0;
}


Measured memory_bytes: 7024
using System;

class Program
{
	static int n;
	static int[] q;

	static void Main(string[] args)
	{
		n = int.Parse(Console.ReadLine());
		string[] sq = Console.ReadLine().Split(' ');

		q = new int[n];
		for (int i = 0; i < n; i++)
		{
			q[i] = int.Parse(sq[i]);
		}

		int a = int.Parse(Console.ReadLine());
		string[] sm = Console.ReadLine().Split(' ');
		for (int i = 0; i < a; i++)
		{
			int m = int.Parse(sm[i]);

			Console.WriteLine(Dfs(0, 0, m) ? "yes": "no");
		}
	}

	static bool Dfs(int i, int sum, int m)
	{
		if (i == n)
		{
			if (sum == m)
			{
				return true;
			}
			else
			{
				return false;
			}
		}

		if (Dfs(i + 1, sum , m))
		{
			return true;
		}

		if (Dfs(i + 1, sum + q[i] , m))
		{
			return true;
		}
		return false;
	}
}


Measured memory_bytes: 15960
#include <stdio.h>

int main(void)
{
	int a;
	int i;
	int b;
	int c;
	int d;
	
	scanf("%d", &a);
	
	for (i = 0; i < a; i++){
		scanf("%d %d %d", &b, &c, &d);
		
		if ((c < b) && (d < b)){
			if ((d * d) + (c * c) == b * b){
				printf("YES\n");
			}
			else {
				printf("NO\n");
			}
		}
		else if ((b < c) && (d < c)){
			if ((d * d) + (b * b) == c * c){
				printf("YES\n");
			}
			else {
				printf("NO\n");
			}
		}
		else if ((b < d) && (c < d)){
			if ((b * b) + (c * c) == d * d){
				printf("YES\n");
			}
			
			else {
				
				printf("NO\n");
			}
		}
		else {
			printf("NO\n");
		}
	}
	return (0);
}

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

const int MOD = 1e9 + 7;
const int M = 3e5 + 5;
const int N = 3005;

int modPow(int base, int po) {
  int ret = 1;
  while (po) {
    if (po & 1) ret = 1ll * ret * base % MOD;
    base = 1ll * base * base % MOD;
    po >>= 1;
  }
  return ret;
}

int fact[M];
int inve[M];
int r[N], c[N];
int dp[N][2];
int h, w, n;

int getComb(int a, int b) {
  if (a < 0 || b < 0 || a < b) return 0;

  int ret = fact[a];
  ret = 1ll * ret * inve[b] % MOD;
  ret = 1ll * ret * inve[a-b] % MOD;

  return ret;
}

void precompute() {
  fact[0] = 1;
  for (int i = 1 ; i < M ; i++) {
    fact[i] = 1ll * fact[i-1] * i % MOD;
  }

  inve[M-1] = modPow(fact[M-1], MOD-2);
  for (int i = M-2 ; i >= 0 ; i--) {
    inve[i] = 1ll * inve[i+1] * (i+1) % MOD;
  }
}

void init() {
  cin >> h >> w >> n;
  for (int i = 1 ; i <= n ; i++) {
    cin >> r[i] >> c[i];
  }
  r[0] = c[0] = 1;
  r[n+1] = h;
  c[n+1] = w;
}

int solve(int idx, int mode) {
  if (idx == n+1) {
    if (mode == 1) return 1;
    return MOD-1;
  }

  int &ret = dp[idx][mode];
  if (ret != -1) return ret;

  ret = 0;
  for (int i = 0 ; i <= n+1 ; i++) {
    if (idx != i && r[idx] <= r[i] && c[idx] <= c[i]) {
      int dr = r[i] - r[idx];
      int dc = c[i] - c[idx];

      int ways = 1ll * getComb(dr + dc, dr) * solve(i, mode ^ 1) % MOD;
      ret = (ret + ways) % MOD;
    }
  }

  return ret;
}

int work() {
  memset(dp, -1, sizeof dp);
  return solve(0, 0);
}

int main() {
  precompute();
  init();
  cout << work() << endl;
  return 0;
}

Measured memory_bytes: 2688
#include <stdio.h>
#include <stdlib.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int a[10][10];

int main() {
    int x, y, t;
    while (scanf("%d,%d,%d", &x, &y, &t) != EOF) {
        if (t == 2) {
            rep (i, 10) rep (j, 10) if (abs(x-i)<2 && abs(y-j)<2) a[i][j]++;
        }
        else {
            const int d = t == 1 ? 1 : 2;
            rep (i, 10) rep (j, 10) if (abs(x-i)+abs(y-j) <= d) a[i][j]++;
        }
    }
    int c = 0, m = 0;
    rep (i, 10) rep (j, 10) {
        if (a[i][j] == 0) c++;
        if (a[i][j] > m) m = a[i][j];
    }
    printf("%d\n", c);
    printf("%d\n", m);
    return 0;
}

Measured memory_bytes: 0
//P2C
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ll x;
	bool ok = 0;
	cin >> x;
	ll tmp = sqrt(x);
	while(x%tmp)tmp--;
	cout << (tmp-1)+(x/tmp - 1); 
	return 0;
}

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

using namespace std;

int n, m;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >>  n >> m;
    int a, Sum = 0;
    for (int i = 0; i < m; i++)
    {
        cin >> a;
        Sum += a;
    }
    cout << max(-1, n - Sum);
    return 0;
}

Measured memory_bytes: 3648
def main():
    a, b = map(int, input().split())
    if a > 0 and b > 0:
        print('Positive')
    elif (a > 0) ^ (b > 0) or a == 0 or b == 0:
        print('Zero')
    else:
        if (a - b) % 2 != 0:
            print('Positive')
        else:
            print('Negative')


if __name__ == '__main__':
    main()


Measured memory_bytes: 38256
#include "iostream"
#include "vector"
using namespace std;

int main()
{
	int a, n, count=1, maxcount = 1;
	cin >> n;
	vector<int>p(n);
	for (int i = 0; i < n; i++) {
		cin >> a;
		p[a-1] = i;
	}
	for (int i = 0; i < n-1; i++) {
		if (p[i] < p[i + 1])count++;
		else count = 1;
		if (count > maxcount)maxcount = count;
	}
	cout << n - maxcount << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
long long ans;
int a[2005],x,n,f[2005][2005];
using std::min;
signed main(){
	scanf("%d%d",&n,&x);
	for (int i=0;i<n;i++) scanf("%d",&a[i]);
	memset(f,0x3f,sizeof(f));
	for (int i=0;i<n;i++){
		f[i][0]=a[i];
		for (int j=1;j<=n;j++) 
			f[i][j]=std::min(f[i][j-1],a[(i-j+n)%n]);
	}
	ans=10000000000000000;
	for (int i=0;i<n;i++){
		long long sum=0;
		for (int j=0;j<n;j++) sum=sum+f[j][i];
		ans=min(ans,sum+1ll*i*x);
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 16000
n = int(input())
ans = [0]*(n+1)
r = range(1, int(n**0.5)+1)
for x in r:
    for y in r:
        for z in r:
            a = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if a<=n:
                ans[a] += 1
for i in ans[1:]:
    print(i)

Measured memory_bytes: 9524
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const ll BIG=1e15;

int main(){
    int N,M;
    cin>>N>>M;
    vector<pair<int,int>> d;
    for(int i=0;i<N;i++){
        int A,B;
        cin>>A>>B;
        d.push_back(make_pair(A,B));
    }

    sort(d.begin(),d.end());
    ll ans=0;
    multiset<int> S;

    int j=0;
    //for(int i=0;i<N;i++) cout<<d.at(i).first<<' '<<d.at(i).second<<endl;
    for(int i=0;i<=M;i++){
        if(j<N){
        while(d.at(j).first<=i) {
            S.insert(d.at(j).second); 
            j++;
            if(j>=N) break;
        }}
        if(S.size()!=0){
            auto itr=S.end();
            itr--;
            //cout<<i<<':'<<S.size()<<endl;
            //cout<<*itr<<endl;
            ans+=*itr;
            S.erase(itr);
            //cout<<ans<<endl;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 5620
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;


typedef long long ll;
typedef pair<int, int> pii;
const int MOD = 1e9 + 7;

#define rep(i,b) for(i=0;i<b;++i)
#define repp(i,a,b) for(i=a;i<b;++i)

int main() {
    char c;
    cin >> c;
    cout << char(c +1) <<endl;

  return 0;
}


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

int main() {

    string s; cin >> s;
    int  n = s.size();
    string left, right;
    left = s.substr(0, n / 2);
    if (n % 2 == 0) {        
        right = s.substr(n / 2);
    }
    else {
        right = s.substr(n / 2 + 1);
    }
    int ans = 0;
    for (int i = 0; i < left.size(); i++) {
        if (left[i] != right[right.size() - i - 1]) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define rep(i,n) for(int i = 0 ; i < n ; i++)
struct P{int x,y;P(){}P(int a,int b){x = a , y = b;}};
int operator -(P a, P b){
	return abs(a.x - b.x) + abs(a.y - b.y);
}
int dp[1<<5][5][1000];
#define INF (1<<21)
int main(){	
	int W,H;
	while(cin >> W >> H , W){
		P s , g ;
		vector<P> v[6];
		rep(i,H)rep(j,W){
			char c; cin >> c;
			if(c == 'S') s = P(j,i);
			else if(c == 'G') g = P(j,i);
			else if(c != '.') v[c-'1'].push_back(P(j,i));
		}
		rep(i,1<<5)rep(k,5)rep(j,1000)dp[i][k][j] = INF;
		rep(i,5)rep(j,v[(i+1)%5].size()){
			dp[(1<<i) | (1<<((i+1)%5))][(i+1)%5][j] = s - v[(i+1)%5][j];
		}
		rep(bit,(1<<5)-1)rep(x,5){
			int y = (x+1)%5;
			rep(i,v[x].size()){
				if( dp[bit][x][i] == INF ) break; // <- ツ催適ツ可サ
				rep(j,v[y].size()){
					dp[bit|(1<<y)][y][j] = min( dp[bit|(1<<y)][y][j] , dp[bit][x][i] + (v[x][i]-v[y][j]) );
				}
			}
		}
		int ans = INF , cho = -1;
		rep(i,5) rep( j , v[i].size() ){
			int cst = dp[(1<<5)-1][i][j] + (g - v[i][j]);
			int w = (i+1)%5;
			if(ans >= cst){
				if(ans == cst){
					cho = min(cho, w );
				}else{
					cho = w;
					ans = cst;
				}
			}
		}
		if(ans == INF) cout << "NA" << endl;
		else cout << cho+1 << " " << ans << endl;
		
		
	}
	
}

Measured memory_bytes: 1592
#include <iostream>
using namespace std;
int main(void){
    int t[4],a[4];
    for(int i=1;i<=4;i++){
        cin>>t[i]>>a[i];
        if(t[i]==1){
            cout<<6000*a[i]<<endl;
        }
        if(t[i]==2){
            cout<<4000*a[i]<<endl;
        }
        if(t[i]==3){
            cout<<3000*a[i]<<endl;
        }
        if(t[i]==4){
            cout<<2000*a[i]<<endl;
        }
    }
}


Measured memory_bytes: 3112
#include<iostream>
#include<string>
//#include<vector>
#include<list>

using namespace std;

int main ()
{
	list<int> data;
	list<int>::iterator i;

	int n;

	cin >> n;

	string command;
	int key;

	while ( n-- )
	{
		cin >> command;
	
		if ( command == "insert" )
		{
			cin >> key;
			data.insert ( data.begin(), key );
		}
		else if ( command == "delete" )
		{
			cin >> key;
			for ( i = data.begin() ; i != data.end() ; i++ )
			{
				if ( *i == key )
				{
					data.erase ( i );
					break;
				}
			}
		}
		else if ( command == "deleteFirst" )
		{
			data.pop_front();
		}
		else if ( command == "deleteLast" )
		{
			data.pop_back();
		}
		else
		{
			//期待してないコマンド
		}
	}

	for ( i = data.begin() ; i != --data.end() ; i++ )
	{
		cout << *i << " ";
	}
	cout << *i << endl;

return 0;
}



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

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

  string ans;
  for (int i = 0; i < (int)s.size(); i++) {
    if (i % 2 == 0) {
      ans += s.at(i);
    }
  }

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

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

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

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
	ost<<"{"<<p.first<<","<<p.second<<"}";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
	ost<<"{";
	for(int i=0;i<v.size();i++){
		if(i)ost<<",";
		ost<<v[i];
	}
	ost<<"}";
	return ost;
}

signed main(){
	string s;cin>>s;
	int num=count(all(s),'o')+(15-s.size());
	if(num>=8)cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	return 0;
}

Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}
 
#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};
 
    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
 
    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}
 
#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };
 
    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };
 
    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };
 
    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };
 
    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };
 
    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

use std::cmp;

fn main() {
    input! {
        s: chars,
        t: chars,
    }

    let mut dp = vec![vec![0; t.len()+1]; s.len()+1];

    for i in 1..s.len()+1 {
        for j in 1..t.len()+1 {
            if s[i-1] == t[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = cmp::max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    //println!("{}", dp[s.len()][t.len()]);

    //復元
    let mut ans = String::new();
    let mut i = s.len();
    let mut j = t.len();
    while i>0 && j>0 {
        if s[i-1] == t[j-1] {
            ans.push(s[i-1]);
            i = i - 1;
            j = j - 1;
        } else if dp[i][j] == dp[i-1][j] {
            i = i - 1;
        } else if dp[i][j] == dp[i][j-1] {
            j = j - 1;
        }
    }

    for a in ans.chars().rev() {
        print!("{}", a);
    }
    println!("");
}


Measured memory_bytes: 41212
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
typedef pair<int, int> P;
int vy[6] = {-1, -1, 0, 1, 1, 0};
int vx_0[6] = {0, 1, 1, 1, 0, -1};
int vx_1[6] = {-1, 0, 1, 0, -1, -1};
int W, H;
int b[100][100];
bool checked[100][100];
vector<P> wh;

bool bwb(int y, int x) {
  if(y < 0 || y >= H || x < 0 || x >= W) return false;
  if(checked[y][x] || b[y][x]) return true;
  checked[y][x] = true;
  wh.push_back(P(y,x));
  bool ret = true;
  FOR(i,0,6) {
    int ny = y + vy[i];
    int nx = x + (y % 2 ? vx_1[i] : vx_0[i]);
    ret &= bwb(ny, nx);
  }
  return ret;
}
int calc(int y, int x) {
  int ret = 0;
  FOR(i,0,6) {
    int ny = y + vy[i];
    int nx = x + (y % 2 ? vx_1[i] : vx_0[i]);
    if(ny < 0 || ny >= H || nx < 0 || nx >= W || b[ny][nx] == 0) ret++;
  }
  return ret;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> W >> H;
  FOR(i,0,H) FOR(j,0,W) cin >> b[i][j];
  FOR(y,0,H) {
    FOR(x,0,W) {
      if(checked[y][x] || b[y][x]) continue;
      wh.clear();
      if(bwb(y, x)) {
        FOR(j,0,wh.size()) {
          b[wh[j].first][wh[j].second] = 1;
        }
      }
    }
  }
  int ans = 0;
  FOR(y,0,H) {
    FOR(x,0,W) {
      if(b[y][x]) ans += calc(y, x);
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long N,A,B;
  cin >> N >> A >> B;
  long long M,m,a;
  a=0;
  M=(N-2)*B;
  m=(N-2)*A;
  cout << max(M-m+1,a) << endl;
}

Measured memory_bytes: 256
def rgb_boxes(R: int, G: int, B: int, N: int)->int:
    res = 0
    for r in range(N+1):
        if r * R > N:
            break
        for g in range(N+1):
            if r * R + g * G > N:
                break
            if (N - (r*R + g*G)) % B == 0:
                res += 1

    return res


if __name__ == "__main__":
    R, G, B, N = map(int, input().split())

    ans = rgb_boxes(R, G, B, N)
    print(ans)


Measured memory_bytes: 3060
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner input = new Scanner(System.in);
		int num = input.nextInt();
		int n  = input.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < arr.length; i++){
			arr[i] = input.nextInt();
		}
		int sum = 0;
		for(int i = 0; i < arr.length;i++){
			sum +=arr[i];
		}
		if (num - sum >= 0)
			System.out.println(num - sum);
		else
			System.out.println("-1");
		
	}
}

Measured memory_bytes: 38136
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b;
  char op;
  
  while (1) {
      cin >> a >> op >> b;
      
      if (op == '+') {
          cout << a+b << endl;
      }
      else if (op == '-') {
          cout << a-b << endl;
      }
      else if (op == '*') {
          cout << a*b << endl;
      }
      else if (op == '/') {
          cout << a/b << endl;
      }
      else {
          break;
      }
  }
}


Measured memory_bytes: 3112
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> P;
typedef pair<lint, lint> PL;

const int INF = 1e9;
char grid[405][405], c[2] = {'#', '.'};
int H, W, dist[405][405], dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
lint cnt_W[405*405], cnt_B[405*405];

bool check(int i, int j){
    if(0<=i && i<H && 0<=j && j<W) return true;
    return false;
}

void dfs(int si, int sj, int ch, int k){
    dist[si][sj] = k;

    for(int i=0;i<4;i++){
        int ni = si + dx[i], nj = sj + dy[i];
        if(check(ni, nj) && c[ch] != grid[ni][nj] && !dist[ni][nj]){
            dfs(ni, nj, ch^1, k);
        }
    }
    return;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> H >> W;
    for(int i=0;i<H;i++) for(int j=0;j<W;j++) cin >> grid[i][j];

    int cnt = 1;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(!dist[i][j] && grid[i][j] == '#') dfs(i, j, 0, cnt++);
        }
    }

    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(grid[i][j] == '#') cnt_B[dist[i][j]]++;
            else cnt_W[dist[i][j]]++;
        }
    }
    lint ans = 0;
    for(int i=1;i<=cnt;i++){
        ans += cnt_W[i] * cnt_B[i];
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
    int N;
    int a[110];
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> a[i];

    sort(a, a + N, 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];
        }
    }
    cout << Alice - Bob << endl;
}

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

struct lake{
  int index;
  int size;
  lake(int index, int size){
    this->index=index;
    this->size=size;
  }
};

int main(){
  string s; cin >> s;
  stack<int> index;
  stack<lake> l;
  for(int i=0; i<s.length(); i++){
    if(s[i]=='\\') index.push(i);
    else if(s[i]=='/'){
      if(index.empty()) continue;
      int frontIndex=index.top();
      index.pop();

      lake nlake(frontIndex, i-frontIndex);

      while(!l.empty()){
        if(l.top().index>nlake.index){
          nlake.size += l.top().size;
          l.pop();
        }
        else break;
      }

      l.push(nlake);
    }
  }

  vector<int> result;
  int allSize=0;
  while(!l.empty()){
    lake now=l.top(); l.pop();
    result.push_back(now.size);
    allSize += now.size;
  }

  cout << allSize << endl << result.size();
  if(result.size()!=0) cout << " ";
  for(int i=(int)result.size()-1; i>=0; i--){
    cout << result[i];
    if(i!=0) cout << " ";
  }
  cout << endl;

  return 0;
}



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

int main(){
  int N; cin >> N;
  int a[3]={}; //a[0]:奇数 a[1]:2の倍数 a[2]:4の倍数
  int c;
  for(int i=0; i<N; i++){
    cin >> c;
    if(c%4==0) a[2]++;
    else if(c%2==0) a[1]++;
    else a[0]++;
  }
  // 1414...1422222が最高
  if(a[1]==0){
    cout << (N/2<=a[2]?"Yes":"No") << endl;
  }else{
    cout << (a[2]*2+a[1]>=N?"Yes":"No") << endl;
  }
}

Measured memory_bytes: 256
s = input()

if (s[0] == s[1]) and (s[1] == s[2]) and (s[2] == s[3]):
    print("No")
elif (s[0] == s[1]) and (s[2] == s[3]):
    print("Yes")
elif (s[0] == s[2]) and (s[1] == s[3]):
    print("Yes")
elif (s[0] == s[3]) and (s[1] == s[2]):
    print("Yes")
elif (s[1] == s[2]) and (s[0] == s[3]):
    print("Yes")
elif (s[1] == s[3]) and (s[0] == s[2]):
    print("Yes")
elif (s[2] == s[3]) and (s[0] == s[1]):
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3064
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    x_s, y_s, x_t, y_t = map(int, readline().split())
    A = np.array([[x_s, y_s, 0],
                  [x_t, y_t, 0]], dtype=np.int)
    
    N = int(readline())
    B = np.array(read().split(), dtype=np.int).reshape(-1, 3)
    XY, R = np.hsplit(np.concatenate((A, B)), [2])
    
    d = np.expand_dims(XY, axis=1) - np.expand_dims(XY, axis=0)
    d = np.sqrt(np.sum(d ** 2, axis=-1))
    d -= R + R.reshape(1, -1)
    d = np.maximum(d, 0)
    np.fill_diagonal(d, -1)
    d = csgraph_from_dense(d, null_value=-1)
     
    ans = dijkstra(d, indices=0)[1]
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 53172
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  int H,W;
  cin >> H >> W;
  
  vector<string> S(H);
  for(int i=0; i<H; i++) cin >> S.at(i);
  
  for(int i=0; i<H; i++){
    for(int j=0; j<W; j++){
      int count=0;
      
      ///ここから
      if(S.at(i)[j]=='.'){
        for(int k=-1; k<2; k++){
          if(i+k<0 || i+k>H-1) count+=0;
          else{
           for(int l=-1; l<2; l++){
             if(j+l<0 || j+l>W-1) count+=0;
             else{
               if(S.at(i+k)[j+l]=='#') count++; 
             }
           }
          }
        }
      }
        if(S.at(i)[j]=='#') cout << "#";
        else cout << count;
    }
    cout << endl;
  }
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define show(a) cout<<""#a""<<" is "<<a<<endl;
#define shw(a,b)cout<<"-->"<<a<<" "<<b<<endl;
#define print(arr,xx)for(int i=0;i<xx;i++)cout<<arr[i]<<" \n"[i>=xx];
#define here cout<<"here\n"; 
int caseno=0;
#define print_case cout<<"Case "<<++caseno<<": ";
#define fout freopen("output.txt","w",stdout);
#define fin freopen("input.txt","r",stdin);
#define pb push_back
#define ll long long
const int primemod=1e9+7;
#define fastio   
ll max(ll a,ll b) {return (a>b)?a:b;}
//string max(string a,string b) {return (a>b)?a:b;}
//ll min(ll a,ll b) {return (a<b)?a:b;}
const int maxsize = 100000+9;
void solve(){
	ll x;
	cin>>x;
	ll cnt=0;
	ll sum=100;
	while(sum<x){
		sum=sum+floor(sum*0.01);
		//cout<<x<<endl;
		cnt++;
	}
	cout<<cnt<<endl;
}

int main(){
	#ifndef ONLINE_JUDGE
 	fout	
 	fin
 	int kase=1; 	
 	while(kase--){
 	#endif     
 	///-----		
 	//fastio
 	int T;
 	// cin>>T;
 	T=1;
 	while(T--){
 		 // if(solve())cout<<"Yes"<<endl;
 		 // else cout<<"No"<<endl;
 		solve();
 	}
 	///-----
 }
 
 #ifndef ONLINE_JUDGE
 }			
 #endif


Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
  ll int n, b, r;
  cin >> n >> b >> r;
  ll int c, d, e;
  c = n / (b + r);
  d = n % (b + r);
  if (d <= b) {
    e = d;
  }
  if (d > b) {
    e = b;
  }
  cout << c * b + e;
}

// g++ lo.cpp
// ./a.exe
// g++ -o つくりたいふぁいるめい　もとのふぁいる.cpp

Measured memory_bytes: 256
/*Bismillahir Rahmanir Rahim*///{
#include <bits/stdc++.h>
#include <ext/numeric>
using namespace std; using __gnu_cxx::power;
using ll = long long; using ull = unsigned long long; using ld = long double;
const ll llinf = (1ll<<61)-1; const double eps = 1e-6, ldeps = 1e-9;
struct Dbg { static constexpr auto &os = cout;   // replace by cerr in interactive.
template<class C> static auto o(C *x)->decltype(os << *x, 0);
template<class C> static char o(...);
template<class C> typename enable_if<sizeof o<C>(0)!=1,Dbg&>::type operator<<(const C &x) {os<<x; return *this;}
template<class C> Dbg &dump(C b, C e) {
    for (struct{C i;int j;} i={(*this<<"\n[",b),0}; i.i!=e and i.j<26; i.i++, i.j++) *this<<", "+2*(i.i==b)<<*i.i;
    return *this << ']';
}
template<class C> typename enable_if<sizeof o<C>(0)==1, Dbg&>::type operator<<(const C &x) {
    return dump(begin(x), end(x));
}
template<class C, size_t X> typename enable_if<!is_same<C, const char>::value, Dbg&>::type operator<<(C (&x)[X]) {
    return dump(begin(x), end(x));
}
template<class B, class C> Dbg &operator<<(const pair<B, C> &x) {return *this<<'{'<<x.first<<", "<<x.second<<'}';}
Dbg &operator<<(ostream&(*x)(std::ostream&)) { os << x; return *this; }
} dbg;
void err(istringstream *iss) { delete iss; }
template<class C, class... Args> void err(istringstream *iss, const C &val, const Args &... args) {
    string name; *iss >> name; if (name.back()==',') name.pop_back();
    dbg << name << " = " << val << "; ", err(iss, args...);
}
#define bug(args...) dbg << __LINE__ << ": ", err(new istringstream(#args), args), dbg << endl
#define cbug(a, args...) if (a) bug(args);
#define ASSERT(a, o, b, args...) if (!((a)o(b))) bug(a, b, ##args), assert((a)o(b));
#define sl(a) int(strlen(a))
#define sz(a) int(a.size())
int T, Q, cn;//}
const int inf = 1000000007, mxn = -1;

signed main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); cout.precision(11), cout.setf(ios::fixed);
    int x;
    cin >> x;
    for (int i = 1; i <= 360; i++) {
        if (i*x%360 == 0) return cout << i << '\n', 0;
    }
}

Measured memory_bytes: 3636
N, Q = map(int, input().split())
S = input()
AC = []
ans = []
AC.append(0)
for i in range(1,N):
    if S[i - 1] == "A" and S[i] == "C":
        AC.append(AC[i - 1] + 1)
    else:
        AC.append(AC[i - 1])
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(AC[r - 1] - AC[l - 1])
print("\n".join(map(str,ans)))

Measured memory_bytes: 16432
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define INF 99999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define rrep(i,m,n) for(lli i=m;i>n;i--)
#define pb(n) push_back(n)
#define UE(N) N.erase(unique(N.begin(),N.end()),N.end());
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(20) << S << endl
#define Vecpr(K,L1,L2,N) vector<pair<L1,L2>> K(N)
#define Vec(K,L,N,S) vector<L> K(N,S)
#define DV(K,L,N,M,R) vector<vector<L>> K(N, vector<L>(M,R))
#define mod 1000000007
#define MAX 510000
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
int main(){
  lli N,K,L,sum=0;
  Vec(P,int,9,0);
  cin >> N;
  Vec(Q,int,N,0);
  rep(i,0,N){
    cin >> Q[i];
    if(Q[i]>3599)Q[i]=3599;
  }
  rep(i,0,N)P[Q[i]/400]++;
  rep(i,0,8)if(P[i]!=0)sum++;
  if(sum==0){
    sum=1;
    P[8]--;
  }
  cout << sum << " " << sum+P[8] << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
    int x, y;
    cin >> x >> y;
    int r;

    if (x < y) {
        int temp = x;
        x = y;
        y = temp;
    }

    while (true) {
        r = x % y;        
        x = y;
        y = r;
        if (r == 0) break;
    }

    cout << x << endl;

    return 0;
}

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

int dp[100001];
int grundy(int a[],int k,int n)
{
	if(k==0)
	{
		return(0);
	}
	if(dp[k]!=-1)
	{
		return(dp[k]);
	}
    set<int>s;
	int i;
	for(i=0;i<n;i++)
	{
		if(a[i]<=k)
		{
			s.insert(grundy(a,k-a[i],n));
		}
	}
	if(s.size()!=0)
	{
	auto it=s.end();
	it--;
	for(i=0;i<=*(it);i++)
	{
		if(s.find(i)==s.end())
        {
        	break;
		}
	}
	return(dp[k]=i);
    }
    else
    {
    	return(0);
    }
}
int main()
{
	int n,k,i;
	cin>>n>>k;
	int a[n];
	for (i = 0; i<n; i++)
	{
		cin>>a[i];
	}
	for(i=0;i<100001;i++)
	{
		dp[i]=-1;
	}

	if(grundy(a,k,n)==0)
		cout<<"Second"<<"\n";
	else
		cout<<"First"<<"\n";
}

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

#define pb push_back
#define vi vector < int >
#define ii pair < int, int >
#define vii vector < pair < int, int > >
#define vvi vector < vector < int > >
#define ll long long
#define X first
#define Y second
#define mp make_pair
#define FOR( i, lo, hi ) for( int i = (lo);i < (hi);i++ )
#define DFOR( i, hi, lo ) for( int i = (hi);i >= (lo);i-- )
#define pqueue priority_queue

using namespace std;

const long long int MOD = 1e9 + 7;

ll ADD( ll a, ll b )
{
	return ( ( a % MOD ) + ( b % MOD ) ) % MOD;
}

ll SUB( ll a, ll b )
{
	return ( ( a % MOD ) - ( b % MOD ) + MOD ) % MOD;
}

ll MUL( ll a, ll b )
{
	return ( ( a % MOD ) * ( b % MOD ) ) % MOD;
}

ll POT( ll n, ll k )
{
	if ( k == 0 )
		return 1;

	ll ret = POT( n, k / 2 );
	ret = MUL( ret, ret );

	if ( k % 2 )
		return MUL( ret, n );
	return ret;
}

ll DIV( ll a, ll b )
{
	return MUL( a , POT( b, MOD - 2 ) );
}

bool isPrime( ll x )
{
	for ( ll i = 2;i <= sqrt( x ) + 1; ++i )
		if ( x % i )
			return false;
	return true;
}

int n, k;

int main()
{
	cin >> n >> k;
	int ans = 0;
	FOR( i, 0, n )
	{
		int x;cin >> x;
		if ( x >= k )
			ans++;
	}
	cout << ans << "\n";
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;
typedef pair<int,int> P;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int main()
{
	int n;
	cin>>n;
	vector<int> p(n);
	for(int i = 0; i < n; i++){
		cin>>p[i];
	}
	int ans = 0;
	for(int i = 1; i < n-1; i++){
		if(min({p[i-1],p[i],p[i+1]}) == p[i-1] && max({p[i-1],p[i],p[i+1]})==p[i+1]) ans++;
		if(min({p[i-1],p[i],p[i+1]}) == p[i+1] && max({p[i-1],p[i],p[i+1]})==p[i-1]) ans++;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256