akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
typedef long long ll;

int main(void){
    ll n, m, a[100010], a_sum = 0;
    vector<pair<ll, ll>> v;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a_sum += a[i];
    }
    sort(a, a + n);
    for (int i = 0; i < m; i++) {
        ll b, c;
        cin >> b >> c;
        v.emplace_back(c, b);
    }
    sort(v.begin(), v.end());
    
    int idx = v.size() - 1, num = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] < v[idx].first) {
            a_sum += (v[idx].first - a[i]);
            num++;
        }
        if (num == v[idx].second) {
            idx--; num = 0;
        }
        if (idx == -1) break;
    }
    cout << a_sum << endl;
}


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

using namespace std;

typedef long long ll;

const int N = 100100;

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n, m;
    cin >> n >> m;
    n -= 2;
    m -= 2;
    if (n == -1) {
        n = 1;
    }
    if (m == -1) {
        m = 1;
    }
    cout << n * m;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
int main()
{
	int result[200];
	int num;
	for(int i = 0;; i++)
	{
		int a, b;
		std::cin >> a >> b;
		if(std::cin.eof())
		{
			num = i;
			break;
		}
		for(int j = 10, k = 1;; j *= 10, k++)
		{
			if((a + b) / j == 0)
			{
				result[i] = k;
				break;
			}
		}
	}
	for(int i = 0; i < num; i++)
	{
		std::cout << result[i] << std::endl;
	}
	return 0;
}


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

using namespace std;
struct edge {
    edge() {};
    edge(int s, int e, int d) : start {s}, end {e}, d {d} {};
    int start;
    int end;
    int d;
};

void dfs(vector<vector<int>>& graph, bool* used, int id, int n){
    used[id] = true;
    for(int i = 0; i < n; ++i){
        if(graph[id][i] == -1 || used[i]){
            continue;
        }
        dfs(graph, used, i, n);
    }
}

bool is_connected(vector<vector<int>>& graph){
    int n = graph.size();
    bool used[n];
    for(int i = 0; i < n; ++i){
        used[i] = false;
    }
    dfs(graph, used, 0, n);
    for(int i = 0; i < n; ++i){
        if(!used[i]){
            return false;
        }
    }
    return true;
}

void delete_edges(vector<vector<int>>& graph){
    int edges_num = 0;
    vector<edge> vec {};
    int n = graph.size();
    for(int i = 0; i < n; ++i){
        for(int j = i+1; j < n; ++j){
            if(graph[i][j] != -1){
                ++edges_num;
                vec.push_back(edge(i, j, graph[i][j]));
            }
        }
    }
    sort(vec.begin(), vec.end(), [](edge x, edge y){
            return y.d < x.d;
         });

    for(auto it = vec.begin(); it != vec.end(); ++it){
        edge e = *it;
        graph[e.start][e.end] = -1;
        graph[e.end][e.start] = -1;
        if(is_connected(graph)){
            --edges_num;
            if(edges_num == n-1){
                return;
            }
        } else {
            graph[e.start][e.end] = e.d;
            graph[e.end][e.start] = e.d;
        }
    }
}

vector<vector<int>> gen_spanning_tree(vector<vector<int>>& graph){
    vector<vector<int>> tree {graph};
    delete_edges(tree);
    return tree;
}

int calc_weight(vector<vector<int>> graph){
    int sum = 0;
    int n = graph.size();
    for(int i = 0; i < n; ++i){
        for(int j = i+1; j < n; ++j){
            if(graph[i][j] == -1){
                continue;
            }
            sum += graph[i][j];
        }
    }
    return sum;
}

int main(){
    int n;
    cin >> n;
    vector<vector<int>> graph {n, vector<int>(n, 0)};
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            cin >> graph[i][j];
        }
    }
    auto tree = gen_spanning_tree(graph);

    cout << calc_weight(tree) << endl;
}

Measured memory_bytes: 1384
#include<cstdio>
#include<algorithm>
using namespace std;
class Point{
public:
   int x,y;
   Point(){}
   Point(int _x,int _y){
      x = _x; y = _y;
   }
}ink[13] = {Point(0,-1),Point(-1,0),Point(0,0),Point(1,0),Point(0,1),
            Point(-1,-1),Point(1,-1),Point(-1,1),Point(1,1),
            Point(0,-2),Point(-2,0),Point(2,0),Point(0,2)
            };

int main(void){
   int x,y,sz;
   int field[11][11] = {0};
   while(scanf("%d,%d,%d",&x,&y,&sz) != EOF){
      for(int i = 0;i < 13;i++){
         if(sz == 1 && i >= 5) break;
         if(sz == 2 && i >= 9) break;
         int _x = x + ink[i].x,_y = y + ink[i].y;
         if(0 <= _x&&_x < 10 && 0 <= _y&&_y < 10) field[_x][_y]++;
      }
   }
   int blank = 0,ma = 0;
   for(int i = 0;i < 10;i++)
      for(int j = 0;j < 10;j++){
         if(field[i][j] == 0) blank++;
         ma = max(field[i][j],ma);
      }

   printf("%d\n%d\n",blank,ma);
   return 0;
}

Measured memory_bytes: 1028
#include <algorithm>
#include <bitset>
#include <boost/dynamic_bitset.hpp>
#include <cfloat>
#include <cmath>
#include <ctime>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <typeindex>
#include <typeinfo>
#include <vector>
#include <numeric>

#define DEBUG(x) cout << #x << ": " << x << endl
#define INFILE() freopen("input.txt", "r", stdin)
#define REP(i, a, b) for (int i = (a); i < (b); i++)
#define REPC(i, a) REP(i, 0, a)
#define RREP(i, a, b) for (int i = (a); i >= (b); i--)
#define RREPC(i, a) RREP(i, a, 0)
#define ALL(s) begin(s), end(s)
#define RALL(s) rbegin(s), rend(s)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i_i = pair<int, int>;
using ll_i = pair<ll, int>;
using i_ll = pair<int, ll>;
using d_i = pair<double, int>;
using ll_ll = pair<ll, ll>;
using d_d = pair<double, double>;

static constexpr ll LL_MOD = 1000000009;
static constexpr int I_MOD = 1000000007;
static constexpr double EPS = numeric_limits<double>::epsilon();
static constexpr double PI = 3.14159265358979323846264338327950288;

template <class T> static void scan(vector<T> &v);
static void scan(vector<string> &v, bool isWord = true);
static boost::dynamic_bitset<> scan(char trueValue = 'o');

int main(int argc, char *argv[]) {
  // INFILE();
	int a, b, c;
	cin >> a >> b >> c;

	if (a == b + c || b == a + c || c == a + b) {
		cout << "Yes\n";
		return 0;
	}

	cout << "No\n";
  return 0;
}

template <class T> static void scan(vector<T> &v) {
  map<type_index, const char *const> m = {{typeid(int), "%d"},
                                          {typeid(ll), "%lld"},
                                          {typeid(double), "%lf"},
                                          {typeid(char), "%c"}};

  auto tFormat = m[typeid(T)];

  for (T &n : v) {
    scanf(tFormat, &n);
  }
}

static void scan(vector<string> &v, bool isWord) {
  if (isWord) {
    for (auto &n : v) {
      cin >> n;
    }
    return;
  }

  int i = 0, size = v.size();
  string s;
  getline(cin, s);

  if (s.size() != 0) {
    i++;
    v[0] = s;
  }

  for (; i < size; ++i) {
    getline(cin, v[i]);
  }
}

static boost::dynamic_bitset<> scan(char trueValue) {
  string s;
  getline(cin, s);

  if (s.size() == 0) {
    getline(cin, s);
  }

  for_each(begin(s), end(s),
           [trueValue](char &c) { c = (c == trueValue) ? '1' : '0'; });
  return boost::dynamic_bitset<>(string(rbegin(s), rend(s)));
}


Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
using namespace std;
int q[200],q1[200];
int main()
{
    int a;
    scanf("%d",&a);
    for(int i=0; i<a; i++)
    {
        scanf("%d",&q[i]);
        q1[q[i]]++;
    }
    int maxx=-1;
    for(int i=0; i<a; i++)
    {
        maxx=max(maxx,q[i]);
    }
    int flag=0;
    if(maxx&1)
    {
        int q2=(maxx-1)/2;
        for(int i=0; i<q2; i++)
        {
            if(q1[maxx-i]<2)
                flag=1;
        }
        if(q1[maxx-q2]!=2)
            flag=1;
    }
    else
    {
        int q2=(maxx)/2;
        for(int i=0; i<q2; i++)
        {
            if(q1[maxx-i]<2)
                flag=1;
        }
        if(q1[maxx-q2]!=1)
            flag=1;
    }
    if(flag)
        printf("Impossible\n");
    else
        printf("Possible\n");
}

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

using namespace std;

vector<int> adjList[10005], ts;
bool vis[10005];

void toposort(int u){
    vis[u] = true;
    for (int i=0; i<adjList[u].size(); i++){
        int v = adjList[u][i];

        if (!vis[v]) toposort(v);
    }
    ts.push_back(u);
}

int main(){

    ios_base::sync_with_stdio(0);

    // init
    memset(vis,0,sizeof(vis));

    int N, E;
    cin >> N >> E;

    int u, v;
    for (int i=0; i<E; i++){
        cin >> u >> v;

        adjList[u].push_back(v);
    }

    for (int i=0; i<N; i++){
        if (!vis[i]) toposort(i);
    }

    for (int i=ts.size()-1; i>=0; i--) cout << ts[i] << endl;

    return 0;
}

Measured memory_bytes: 1964
def gcd(a, b, k):
    count = 0
    if a < b:
        a, b = b, a
    for i in range(1,b+1)[::-1]:
        if a % i == 0 and b % i == 0:
            count += 1
            if count == k:
                return i

li = list(map(int, input().split()))
print(gcd(li[0], li[1], li[2]))


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

int main() {
  static const double pi = 3.141592653589793;
    double a,b,h,m;
    cin >> a >> b >> h >> m;
    double c;
    double kaku = 30*h-6*m+0.5*m;
    if(kaku<0) kaku*-1.0;
    kaku = min(kaku,360.0-kaku);
  double rad=2*pi*kaku/360; 
    c = (double)(pow(a,2)+pow(b,2)-2*a*b*cos(rad));
    printf("%12.9lf",pow(c,0.5));
    
    return 0;
}

Measured memory_bytes: 4356
#include <iostream>
#include <map>

using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for(int i=1; i<=n; i++)

P convert(int n){
  P p;
  p.second = n%10;
  while(n/10){
    n /= 10;
  }
  p.first = n;
  return p;
}


int main(void){
  int N;
  cin >> N;

  int count = 0;
  int i, j, k;

  map<P, int> pair_seq;
  P pair_n;
  rep(i, N){
    pair_n = convert(i);
    pair_seq[pair_n]++;
    // cout << pair_n.first << ", " << pair_n.second << " is " << pair_seq[pair_n] << "times" << endl; 
  }

  rep(i, N){
    pair_n = convert(i);
    P q(pair_n.second, pair_n.first);
    count += pair_seq[q];
  }

  cout << count << endl;

  return 0;
}


Measured memory_bytes: 764
package main

import (
	"fmt"
	"sort"
)

func main() {
	var N int
	fmt.Scan(&N)
	d := make([]int, N)
	for i := 0; i < N; i++ {
		fmt.Scan(&d[i])
	}
	sort.Ints(d)
	l := d[N/2-1]
	r := d[N/2]
	fmt.Println(r - l)
}


Measured memory_bytes: 5504
/////////////////////////   _LeMur_
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <time.h>
#include <stack>
#include <string>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>

using namespace std;

const int N = 305;
const int inf = 1000 * 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;

int n;
char a[N][N];
char b[N][N];

bool check(int x){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            b[(i + x) % n][j] = a[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(b[i][j] != b[j][i])
                return false;
        }
    }
    return true;
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j];
        }
    }
    int answ = 0;
    for(int i=0;i<n;i++){
        if(check(i)){
            answ += n;
        }
    }
    cout<<answ<<endl;
	return 0;
}


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

int main()
{
    int L,R,d;
    cin>>L>>R>>d;
    int a=L/d,b=R/d,num=0;
    num=b-a;
    if(L%d==0)
        num++;
    cout<<num<<endl;
}


Measured memory_bytes: 3632
julia -En,s=`tr '
' ,`1";A=3n;f(b,n)=n<b?n:f(b,n÷b)+n%b;g(b)=b>1&&f(b,n)==s&&A>b?b:A;A=g(n+1);for b=1:isqrt(n);A=g(b);A=g((n-s)÷b+1);end;A>2n?-1:A"

Measured memory_bytes: 153728
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main() {
  ll N,K,Q;
  cin>>N>>K>>Q;
  vector<ll>vec(N,K-Q);
  for(ll i=0;i<Q;i++){
    ll a;
    cin>>a;
    vec.at(a-1)+=1;
  }
  for(ll i=0;i<N;i++){
    if(vec.at(i)>0){
      cout<<"Yes"<<endl;
    }
    else{
      cout<<"No"<<endl;
    }
  }
}

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

int main()
{
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    long long w = 0,x = 0, y = 0, z = 0, ans = 0;
    w = (1ll * a) * c;
    x = (1ll * a) * d;
    y = (1ll * b) * c;
    z = (1ll * b) * d;
    ans = max(max(x,y),max(w,z));
    cout << ans << endl;
}

Measured memory_bytes: 3176
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>

using LL = long long;
const LL inf = 1e18;
const int MOD = (int)1e9 + 7;
const int kN = 100000 + 5;
int n, m, s, t;
std::vector<std::pair<int, int>> edges[kN];
LL dist[2][kN];
int ways[2][kN];

inline void add(int &a, int b)
{
    a += b;
    if (a >= MOD) a -= MOD;
}

void dijkstra(int source, LL *dist, int *ways)
{
    std::fill(dist, dist + n, inf);
    dist[source] = 0;
    ways[source] = 1;
    std::priority_queue<std::pair<LL, int>> pq;
    pq.emplace(-dist[source], source);
    while (!pq.empty()) {
        int u;
        LL tmp;
        std::tie(tmp, u) = pq.top(); pq.pop();
        if (dist[u] != -tmp) continue;
        for (auto e : edges[u]) {
            int v = e.first, w = e.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                ways[v] = ways[u];
                pq.emplace(-dist[v], v);
            } else if (dist[v] == dist[u] + w) {
                add(ways[v], ways[u]);
            }
        }
    }
}

int sqr(int x)
{
    return x * 1LL * x % MOD;
}

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%d%d", &s, &t); -- s; -- t;
    for (int i = 0; i < m; ++ i) {
        int u, v, d;
        scanf("%d%d%d", &u, &v, &d); -- u; -- v;
        edges[u].emplace_back(v, d);
        edges[v].emplace_back(u, d);
    }
    dijkstra(s, dist[0], ways[0]);
    dijkstra(t, dist[1], ways[1]);

    int result = ways[0][t] * 1LL * ways[0][t] % MOD;
    // printf("result = %d\n", result);
    for (int overlay_point = 0; overlay_point < n; ++ overlay_point) {
        if (dist[0][overlay_point] == dist[1][overlay_point] && dist[0][overlay_point] + dist[1][overlay_point] == dist[0][t]) {
            add(result, MOD - sqr(ways[0][overlay_point] * 1LL * ways[1][overlay_point] % MOD));
            // printf("overlay_point = %d, result = %d\n", overlay_point, result);
        }
    }
    // printf("result = %d\n", result);
    for (int u = 0; u < n; ++ u) {
        for (auto e : edges[u]) {
            int v, w;
            std::tie(v, w) = e;
            if (dist[0][u] + dist[1][v] + w == dist[0][t] && (dist[0][u] <= dist[1][v] && dist[0][u] + w > dist[1][v] ||
                                                              dist[1][v] <= dist[0][u] && dist[1][v] + w > dist[0][u]))
                add(result, MOD - sqr(ways[0][u] * 1LL * ways[1][v] % MOD));
        }
    }
    printf("%d\n", result);
}


Measured memory_bytes: 15048
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pi acos(-1)
#define mod 1000000007
using namespace std;

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

    int n;
    cin >> n;
    int a[n], b[n], c[n];
    for(int i = 0; i < n; i++){
        cin >> a[i] >> b[i] >> c[i];
    }
    int dp[n][3];
    dp[0][0] = a[0];
    dp[0][1] = b[0];
    dp[0][2] = c[0];
    for(int i = 1; i < n; i++){
        dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a[i];
        dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + b[i];
        dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + c[i];
    }
    cout << max(max(dp[n-1][0], dp[n-1][1]), dp[n-1][2]);
    return 0;
}


Measured memory_bytes: 2560
import java.util.*;
import java.awt.geom.*;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		while(true){
			int n = sc.nextInt();
			if(n == 0 ) break;

			ps = new Point2D[n+1];

			ps[0] = new Point2D.Double(0,0);
			for(int i=1;i<=n;i++){
				ps[i] = new Point2D.Double(sc.nextDouble(),sc.nextDouble());
			}

			double ans = 0;
			before = null;
			while(ps != null){
				ans += convexHull();
			}

			System.out.printf("%.1f\n",ans);
		}
	}

	private static Point2D[] ps;
	private static Point2D before;

	private static double convexHull(){
		double res = 0;
		int n = ps.length;

		Arrays.sort(ps,new Comparator<Point2D>(){
			public int compare(Point2D o1,Point2D o2){
				if(o1.getX() < o2.getX()) return -1;
				else if(o1.getX() > o2.getX()) return 1;
				else if(o1.getY() < o2.getY()) return -1;
				else if(o1.getY() > o2.getY()) return 1;
				else return 0;
			}
		});

		if(n <= 2){
			if(n == 2) res = ps[0].distance(ps[1]);
			ps = null;
			return res;
		}

		int k = 0;
		Point2D[] ch = new Point2D[2*n];
		LinkedList<Point2D> ot = new LinkedList<Point2D>(Arrays.asList(ps));

		for(int i=0;i<n;ch[k++] = ps[i++]){
			while(k>=2 && Line2D.relativeCCW(ch[k-2].getX(),ch[k-2].getY(),ch[k-1].getX(),ch[k-1].getY(),ps[i].getX(),ps[i].getY()) <= 0){
				k--;
			}
		}

		for(int i=n-2, t=k+1;i>=0;ch[k++]=ps[i--]){
			while(k>=t && Line2D.relativeCCW(ch[k-2].getX(),ch[k-2].getY(),ch[k-1].getX(),ch[k-1].getY(),ps[i].getX(),ps[i].getY()) <= 0){
				k--;
			}
		}

		int start = 0;
		if(before != null){
			for(;!ch[start].equals(before);start++);
		}
		//System.out.println("start:" + start + " " + before);

		if(n < k - 1) k = k / 2 + 1;

		ot.remove(ch[start]);
		for(int i=1;i<k-1;i++){
			int a = (start + i) % (k - 1);
			int b = (start + i - 1) % (k - 1);
			res += ch[b].distance(ch[a]);
			ot.remove(ch[a]);
		}
		before = ch[(start - 1 + (k-1)) % (k - 1)];
		if(!ot.isEmpty()) ot.add(before);

		//System.out.println(k-1);
		//System.out.println(Arrays.toString(Arrays.copyOf(ch,k-1)));

		if(n > k-1)
			ps = (Point2D[])ot.toArray(new Point2D[]{});
		else
			ps = null;

		return res;
	}
}

Measured memory_bytes: 13000
#pragma GCC optimize("O3")

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int, int> pi;
tree<int,int,greater<int>,rb_tree_tag,tree_order_statistics_node_update> map_t;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for(int i = 0; i < (a); ++i)
#define pb push_back
#define sz(x) (int)x.size()
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    map<string,int> ma;
    F0R(i,n)
    {
        string s;
        cin >> s;
        ma[s]++;
    }
    int best=-1;
    for(auto p : ma)
    {
        best=max(best,p.second);
    }
    for(auto p : ma)
    {
        if(p.second==best)
            cout << p.first << "\n";
    }

    return 0;
}


Measured memory_bytes: 23808
#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
#include <bits/stdc++.h>
#define SIZE 300010
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define ll long long
#define mp make_pair
#define pi acos(-1.0)
#define eps 1e-8
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
#define INF 0x3f3f3f3f
int n;

struct Point {
	double x, y;
	void input() { scanf("%lf %lf", &x, &y); }
}c[100007];

double dis(double x, double y, double a, double b) {
	return 1.0 * sqrt((x - a) * (x - a) + (y - b) * (y - b));
}

void SimulateAnneal() {
	double x = 0, y = 0, z = 0, ans = INF;
	int j = 0;
	double step = 1000;
	while (step > eps) {
		rep(i, 1, n)
			if (dis(c[i].x, c[i].y, x, y) > dis(c[j].x, c[j].y, x, y))
				j = i;
		double dist = dis(c[j].x, c[j].y, x, y);
		if (dist < ans) ans = dist;
		x += (c[j].x - x) / dist * step;
		y += (c[j].y - y) / dist * step;
		//z += (c[j].z - z) / dist * step;
		step *= 0.99;   //系数可以修改
	}
	printf("%.12lf\n", ans);
}

int main() {
	scanf("%d", &n);
	double x = 0, y = 0, z = 0;
	rep(i, 1, n) c[i].input();
	SimulateAnneal();
}


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

using namespace std;

typedef long long ll;

#define MOD 1000000007

int main() {
  int n, k, c;
  cin >> n >> k >> c;
  string s;
  cin >> s;
  vector<int> cand1(k, -1), cand2(k, -1);
  int day = 0;
  for (int i = 0; i < n; ++i) {
    if (k <= day) break;
    if (s[i] == 'o') {
      if (day == 0 || cand1[day - 1] + c + 1 <= i) {
        cand1[day] = i;
        day++;
      }
    }
  }
  day = k - 1;
  for (int i = n - 1; i >= 0; --i) {
    if (day <= -1) break;
    if (s[i] == 'o') {
      if (day == k - 1 || i <= cand2[day + 1] - c - 1) {
        cand2[day] = i;
        day--;
      }
    }
  }
  for (int i = 0; i < k; ++i) {
    if (cand1[i] == cand2[i]) {
      cout << cand1[i] + 1 << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 3332
//IN THE NAME OF Allah
///////////////////////////////////////////////////////////////////////////////////////
//   HH   HH        AA        SSSSSSS    HH   HH   EEEEEEEE       MM        MM       //
//   HH   HH       AAAA     SSS          HH   HH   EE            MMMM      MMMM      //
//   HHHHHHH      AA  AA     SSSSSSS     HHHHHHH   EEEEE        MM  MM    MM  MM     //
//   HHHHHHH     AAAAAAAA      SSSSSSS   HHHHHHH   EEEEE       MM    MM  MM    MM    //
//   HH   HH    AA      AA          SSS  HH   HH   EE         MM      MMMM      MM   //
//   HH   HH   AA        AA   SSSSSSS    HH   HH   EEEEEEEE  MM        MM        MM  //
///////////////////////////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
#include <math.h>
#define ll long long
#define NFor(i,a,b) for (ll i = a; i <= b; i++)
#define RFor(i,a,b) for (ll i = a; i >= b; i--)
#define GFor(a,b,x) for(auto a : b[x])
#define Fasting()  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define PB push_back
#define all(x) x.begin(), x.end()
#define ot(n) cout << fixed << setprecision(9) << n;
#define endl "\n"
#define F first
#define S second
using namespace std;
const ll N=1e3+2;

int main()
{
    ll n;cin>>n;ll a,b;cin>>a>>b;
    bool ok=false;
    NFor(i,a,b)
    {
        if(i%n==0)
        {
            ok=true;
        }
    }
    if(ok)cout<<"OK"<<endl;
    else cout<<"NG"<<endl;
}




Measured memory_bytes: 3504
#include <stdio.h>
int main(void){
int n;
int p[20];
int max=0;
int num;
int count;
int sum=0;
scanf("%d",&n);
for(count=0;count<n;count++){
    scanf("%d",&p[count]);
}
for(count=0;count<n;count++){
    if(max<=p[count]){max=p[count];
    num=count;}
}
p[num]=p[num]/2;
for(count=0;count<n;count++){
   sum=sum+p[count];
}
printf("%d\n",sum);
}

Measured memory_bytes: 128
#include <iostream>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#include<cstdio>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define mp make_pair
#define pb push_back
#define P pair<int,int>
#define ll __int64
#define __int64 long long
int n;
ll t[211111];

ll abs2(ll x){
	if(x<0)x*=-1;
return x;
}
int main(){
	cin>>n;
	rep(i,n)cin>>t[i];
	ll ans=100000000000000000;
	ll s1=0,s2=0;
	rep(i,n)s2+=t[i];

	s1+=t[0],s2-=t[0];

	ans=min(ans,abs2(s1-s2));

	for(int i=1;i<n-1;i++){
		s1+=t[i];
		s2-=t[i];
		//cout<<s1<<" "<<s2<<endl;
		ans=min(ans,abs2(s1-s2));
	}
	cout<<ans<<endl;
	return 0;
}

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

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    string s;
    cin >> s;
    if (s == "Sunny")
        puts("Cloudy");
    if (s == "Cloudy")
        puts("Rainy");
    if (s == "Rainy")
        puts("Sunny");
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void){
  int n,y,m,d,ans,i,j,k;
  scanf("%d",&n);
  while(n--){
    scanf("%d %d %d",&y,&m,&d);
    ans=0;
    i=y;
    j=m;
    k=d;
    for(;i<1000;i++){
      if(j==11)
	j=1;
      for(;j<11;j++){
	if(k==21)
	  k=1;
	for(;k<21;k++){
	  ans++;
	  if(i%3!=0&&j%2==0&&k==19){
	    k=1;
	    break;
	  }
	}
      }
    }
    printf("%d\n",ans);
  }
  return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
#define rep0(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<string, int, int> TU;
typedef tuple<int, int, int> TI;

int main()
{
    int input[3];
    cin >> input[0] >> input[1] >> input[2];
    sort(input,input+3);
    int diff = input[2]*2 - input[1] - input[0];
    if(diff%2==0){
        cout << diff/2 << endl;
    }else{
        cout << diff/2 + 2 << endl;
    }
}


Measured memory_bytes: 3620
# https://atcoder.jp/contests/dp/tasks/dp_f

S = gets.chomp
T = gets.chomp

SC = S.codepoints
TC = T.codepoints

dp = Array.new(S.size + 1) { Array.new(T.size + 1, 0) }

SC.each_with_index do |s, s0|
  s1 = s0 + 1

  dps0 = dp[s0]
  dps1 = dp[s1]

  TC.each_with_index do |t, t0|
    t1 = t0 + 1

    dps1[t1] = if s == t
                 dps0[t0] + 1
               else
                 dps0t1 = dps0[t1]
                 dps1t0 = dps1[t0]

                 dps0t1 < dps1t0 ? dps1t0 : dps0t1
               end
  end
end

i = dp[S.size][T.size]
s = S.size
t = T.size
a = ''

while i > 0
  case
  when dp[s - 1][t] == i then s -= 1
  when dp[s][t - 1] == i then t -= 1
  else
    a.insert(0, S[s - 1])
    i -= 1
    s -= 1
    t -= 1
  end
end

print a


Measured memory_bytes: 72444
#include <stdio.h>
#include <iostream>
#include <iomanip>
using namespace std;

int main()
{
	double n, m, d;
	cin >> n >> m >> d;

	double A = 1 + d;
	double B = n - d;
	
	double x;

	if (d == 0) {
		x = n;
	}
	else if(A < B)
	{
		x = 2 * (n - d - d) + 2 * d;
	}
	else
	{
		x = n - d + n - d;
	}

	double result = x * (m - 1) / n / n;

	cout << setprecision(10) << result << endl;

	return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	// Code for A - Cats and Dogs
	var A, B, X int
	fmt.Scanf("%d %d %d", &A, &B, &X)

	if A+B >= X && A <= X {
		fmt.Println("YES")
	} else {
		fmt.Println("NO")
	}
}


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

public class MainClass
{
	public const long Giri = 1000000007;

	public static void Main(string[] args)
	{
		var p = Input().ToInt();
		var n = p[0];
		var m = p[1];
		
		var boxes = new int[n];
		var modify = new bool[n];
		for(int i = 0; i < n; i++)
			boxes[i]=1;
		modify[0]=true;
		
		for(int i = 0; i < m; i++)
		{
			p = Input().ToInt();
			boxes[p[0] - 1]--;
			boxes[p[1] - 1]++;
			modify[p[1] - 1] |= modify[p[0] - 1];
			if(boxes[p[0] - 1]==0)
				modify[p[0] - 1]=false;
		}
		long wa = 0;
		for(int i = 0; i < n; i++)
		{
			if(modify[i])
			{
				wa++;
			}
		}
		Console.WriteLine(wa);
	}
	

	static long GCD(long a, long b)
	{
		var v = new[] { a, b };
		while (v[1] != 0) { v = new[] { v[1], v[0] % v[1] }; }
		return v[0];
	}
	public static string[] Input() { return Console.ReadLine().Split(' '); }
	public static int Clamp(int val, int max, int min = 0) { return Math.Min(max, Math.Max(min, val)); }
}

public static class Smarter
{
	public static int ToInt(this string str) { return int.Parse(str); }
	public static long ToLong(this string str) { return long.Parse(str); }
	public static int[] ToInt(this string[] str)
	{
		var r = new int[str.Length];
		for(int i = 0; i < str.Length; i++) r[i] = str[i].ToInt();
		return r;
	 }
}



Measured memory_bytes: 15328
#include<iostream>
#include<vector>
#include<string>
#include<climits>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<queue>


int main(){
	int h, w;	
	std::cin>>h>>w;

	std::vector<std::string> sList(h);
	std::vector<std::vector<int>> mapList(h);

	for(int i=0; i<h; i++)
		mapList[i].resize(w, 0);
	
	for(int i=0; i<h; i++)
		std::cin>>sList[i];

	for(int i=0; i<h; i++){
		int dotCount=0;
		int beg=0;
		for(int j=0; j<w; j++){
			if(sList[i][j]=='.')
				dotCount++;

			if(sList[i][j]=='#'){
				for(int k=beg; k<j; k++)
					mapList[i][k]= dotCount;

				beg= j+1;
				dotCount= 0;
			}
		}

		for(int k=beg; k<w; k++)
			mapList[i][k]= dotCount;
	}

	for(int i=0; i<w; i++){
		int dotCount=0;
		int beg=0;
		for(int j=0; j<h; j++){
			if(sList[j][i]=='.')
				dotCount++;

			if(sList[j][i]=='#'){
				for(int k=beg; k<j; k++)
					mapList[k][i]+= dotCount-1;

				beg= j+1;
				dotCount= 0;
			}
		}

		for(int k=beg; k<h; k++)
			mapList[k][i]+= dotCount-1;
	}

	int ans=0;

	for(int i=0; i<h; i++)
		for(int j=0; j<w; j++)
			ans= std::max(ans, mapList[i][j]);

		std::cout<<ans<<std::endl;


	return 0;
	
}

Measured memory_bytes: 20096
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;
const int max_n = 200000;
long long cnt[111];
long long m,n,a,b;
const int INF = 1e8;
const int mod = 1e9 + 7;
long dist[max_n];
vector<vector<int> > G;

long long gcd(long long xx, long long yy){
    if(yy == 0) return xx;
    long long k = xx/yy;
    long long c = xx - k*yy;
    return gcd(yy, c);
}
void solve(){
    cout << gcd(m, n) << endl;
}
int main(){
    cin >> m >> n;
    solve();
    return 0;
}


Measured memory_bytes: 3092
class Dice
    @faces = nil

    def initialize arr
        @faces = arr
    end

    def top
        @faces[0]
    end

    def rotate news
        f = @faces.dup
        case news
        when "N"
            @faces = [f[1], f[5], f[2], f[3], f[0], f[4]]
        when "E"
            @faces = [f[3], f[1], f[0], f[5], f[4], f[2]]
        when "W"
            @faces = [f[2], f[1], f[5], f[0], f[4], f[3]]
        when "S"
            @faces = [f[4], f[0], f[2], f[3], f[5], f[1]]
        end
    end
end

numbers = gets.chomp.split
dice = Dice.new numbers

directions = gets.chomp
directions.each_char{|c| dice.rotate c}

puts dice.top

Measured memory_bytes: 8640
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

        int[] a = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = sc.nextInt();
        }
        System.out.println(1 + ( (N - 2 ) / (K - 1)));

    }
}


Measured memory_bytes: 49968
X, K, D = map(int, input().split())

X = abs(X)

if K*D <= X:
    print(X-K*D)
    exit()

near0_X = X % D
after_K = K - X//D

if after_K % 2 == 0:
    print(near0_X)
else:
    print(D-near0_X)


Measured memory_bytes: 9164
#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int a,b,i=0;
    cin>>a>>b;
    while(true){
        if(abs(a-i)==abs(b-i)){printf("%d",i);break;}
        if(a<i&&b<i){printf("IMPOSSIBLE");break;}
        i++;
    }
    return 0;
}

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

#define lli long long int
#define endl "\n"
#define debug(n) cout<<n<<endl
#define debug2(a, b) cout<<a<<" "<<b<<endl;
#define forn(i, in, fin) for(int i = in; i<fin; i++)
#define all(v) v.begin(), v.end()
#define fastIO(); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using namespace std;

lli MEX(set<int> check)
{
    for(int i = 0; ; i++)
    {
        if(check.find(i) == check.end())
        {
            return i;
        }
    }
}


int main()
{
    fastIO();
    lli n, k; cin>>n>>k;
    vector<lli> poss(n);
    vector<lli> NIM(k+1);
    for(auto &x: poss)
    {
        cin>>x;
    }

    for(int i = 1; i<=k; i++)
    {
        set<int> check;
        lli j = 0;
        while(j < n  &&  (i - poss[j] >= 0))
        {
            //cout<<NIM[i-poss[j]]<<" ";
            check.insert(NIM[i - poss[j]]);
            j++;
        }
        NIM[i] = MEX(check);
    }
    
    if(NIM[k] == 0) cout<<"Second\n";
    else cout<<"First\n";

    return 0;
}

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

long long int gcd(long long int x, long long int y)
{
	if (y == 0) { return x; }
	return gcd(y, x % y);
}

int main(void)
{
	int r;
	cin >> r;
	cout << pow(r, 2) << endl;
	return 0;
}


Measured memory_bytes: 256
#!/usr/bin/ruby
# -*- coding: utf-8 -*-
=begin
Volume0-0003
1 2 3 4 5 6
2 -1 -2 -1 -1 -5
2 -1 -3 1 -1 -3
2 -1 -3 -9 9 27
=end
def rnd(x)
  return (x * 1000).round.to_f / 1000
end

def sim(v)
  a,b,c,d,e,f = v
  det = a*e - b*d
  x = ( e*c - b*f).to_f/det
  y = (-c*d + a*f).to_f/det
  return [x,y]
end

class Main
  def initialize
    fh=STDIN
    v = []
    while fh.gets do
      v.push($_.split.map{|x| x.to_i})
    end
    v.each{|f|
      x,y = sim(f)
      printf("%.3f %.3f\n", rnd(x), rnd(y))
    }

  end

end

if $0 == __FILE__ then
  Main.new
end

Measured memory_bytes: 8672
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 30 11:59:44 2019
Bellman Ford Method
@author: maezawa
"""

import collections


class BellmanFord():
    def __init__(self):
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed:
            self.edges.append([u, v, d])
        else:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])

    def BellmanFord_search(self, s):
        """
        次のBellmanFord_negative_boolまで考慮した時には、0-indexedであることに注意
        s =  始点
        return: d[i] 始点sから各点iまでの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    update = True
            if not update:
                break
        return d

    def BellmanFord_negative_bool(self, numNodes, start, zero_indexed=False):
        # 負の閉路の検出, Trueなら負の閉路が存在する
        d = collections.defaultdict(lambda: float('inf'))
        d[start] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    #print(i, j, e)
                    if i == numNodes-1:
                        return True
        #print(d)
        return False
    

graph = BellmanFord()
num_v, num_edges, start = list(map(int, input().split()))

for i in range(num_edges):
    u, v, w = list(map(int, input().split()))
    graph.add(u, v, w, directed=True)

if graph.BellmanFord_negative_bool(num_v, start, zero_indexed=True):
    print('NEGATIVE CYCLE')
else:
    distances = graph.BellmanFord_search(start)
    for i in range(num_v):
        if distances[i] == float('inf'):
            print('INF')
        else:
            print(distances[i])



Measured memory_bytes: 6532
#include <iostream>
#include <cstdlib>
#include <time.h>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <array>
#include <string>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mp make_pair
#define F first
#define S second
using namespace std;
using namespace __gnu_pbds;

typedef long long int ll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ost;

const ll maxN = 1e7;
const ll INF = 1e17;

ll xs[] = {-1, 1, 0, 0};
ll ys[] = {0, 0, -1, 1};

int main(){
	cin.sync_with_stdio(false);
	cin.tie(0);
	string st;
	cin >> st;
	ll ans = 0;
	for(ll i=0; st[i]; i++){
		if(st[i] == '+')
			ans++;
		else
			ans--;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 3556
#include<bits/stdc++.h>
#define PI 3.141592653589
#define ll long long
using namespace std;

int main(){
  int a, b;
  cin >> a >> b;

  if(a > b*2){
    cout << a - b*2;
    return 0;
  }
  cout << 0;


}

  

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

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

typedef long long lint;

using namespace std;

struct UnionFind{
  vector<int> par;
  UnionFind(int N):par(N){
    REP(i,N)par[i]=i;
  }
  int root(int x){
    if(par[x]==x)return x;
    return par[x]=root(par[x]);
  }
  void unite(int x,int y){
    int rx=root(x);
    int ry=root(y);
    if(rx==ry)return;
    par[rx]=ry;
  }
};

int main(){
  int N;
  cin>>N;
  set<int> sx,sy;
  UnionFind tree(2e5);
  REP(i,N){
    int x,y;
    cin>>x>>y;
    x--;
    y--;
    sx.insert(x);
    sy.insert(y);
    y+=1e5;
    tree.unite(x,y);
  }
  lint ans=0;
  while(!sx.empty()){
    set<int> ssx,ssy;
    int xx=*sx.begin();
    ssx.insert(xx);
    lint nx=0;
    for(auto e:sx){
      if(tree.root(xx)==tree.root(e)){
        ssx.insert(e);
        nx++;
      }
    }
    lint ny=0;
    for(auto e:sy){
      if(tree.root(xx)==tree.root(e+1e5)){
        ssy.insert(e);
        ny++;
      }
    }
    ans+=nx*ny;
    for(auto e:ssx)sx.erase(e);
    for(auto e:ssy)sy.erase(e);
  }
  cout<<ans-N<<endl;
  return 0;
}


Measured memory_bytes: 10368
#include <map>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <tr1/unordered_map>
#define mo 1000000007
#define num(x) (x>='0' && x<='9')
typedef unsigned long long ull;
typedef long long ll;
using namespace std::tr1;
using namespace std;
int read(){
    int p=0, q=1;
    char ch=getchar();
    while (!num(ch))
        (ch=='-'?q=-1:0),
        ch=getchar();
    while (num(ch)) p=p*10+ch-'0', ch=getchar();
    return p*q;
}
int power(ll a, int b){
	ll c=1;
	while (b){
		if (b&1) c=c*a%mo;
		a=a*a%mo;
		b>>=1;
	}
	return c;
}
int n, a[200005];
ll ans;
int main(){
	n=read();
	for (int i=1, b;i<=n;i++){
		a[i]=read();
		b = max(a[i-1]-a[i],0);
		a[i]+=b;
		ans+=b;
	}
	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4372
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>

using ll = long long;
using namespace std;

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

int main(void) {
	string s;
	cin >> s;
	
	bool yes = true;
	for(int i = 0; i < (int)s.size(); ++i) {
		if( i % 2 == 0 && s[i] != 'R' && s[i] != 'U' && s[i] != 'D' ) {
			yes = false;
			break;
		}
		
		if( i % 2 != 0 && s[i] != 'L' && s[i] != 'U' && s[i] != 'D' ) {
			yes = false;
			break;
		}
	}
	
	if( yes ) cout << "Yes" << endl;
	else cout << "No" << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
const int mod=1e9+7;
const int N=1e6+5;
int n,m,k,ans,inv[N],a[N],jc[N];
char s[N];
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
int kuai(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)res=res*a%mod;
		b=b/2;
		a=a*a%mod;
	}
	return res;
}
int C(int n,int m)
{
	return jc[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main()
{
	n=read();k=read();
	jc[0]=jc[1]=inv[0]=inv[1]=1;
	for(int i=2;i<=n;i++)jc[i]=jc[i-1]*i%mod;
	for(int i=2;i<=n;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	for(int i=2;i<=n;i++)inv[i]=inv[i-1]*inv[i]%mod;
	ans=1;
	for(int m=1;m<n;m++)
	if(n-m<=k)
	{
		ans=(ans+C(n,m)*C(n-1,m-1)%mod)%mod;
	}
	cout<<ans;
}

Measured memory_bytes: 5376
#include <iostream>
using namespace std;
int main(){
	int n,x=0,max=-1000;
	string s;
	
	cin>>n>>s;
	for(int i=0;i<s.size();i++){
		if(s[i]=='I')x=x+1;
		if(s[i]=='D')x=x-1;
		if(x>max)max=x;
	}
	if(0>max)max=0;
	cout<<max<<endl;
	
	return 0;
}

Measured memory_bytes: 256
N=int(input())
A=list(map(int,input().split()))

XOR=0
for a in A[2:]:
    XOR^=a

S=A[0]+A[1]

DP=[[[1<<60]*2 for i in range(2)] for j in range(60)]
DP[0][0][1]=0

for i in range(59):
    CX=0
    if XOR & (1<<i)!=0:
        CX=1

    CS=0
    if S & (1<<i)!=0:
        CS=1

    CA=0
    if A[1] & (1<<i)!=0:
        CA=1
    
    for j in range(2):
        for k in range(2):
            if DP[i][j][k]==1<<60:
                continue

            for na,nb in [(0,0),(0,1),(1,0),(1,1)]:
                if na^nb != CX:
                    continue
                if (na+nb+j)%2 != CS:
                    continue
                
                if na+nb+j>=2:
                    nj=1
                else:
                    nj=0

                if CA<nb:
                    nk=1
                elif CA==nb:
                    nk=k
                else:
                    nk=0

                DP[i+1][nj][nk]=min(DP[i+1][nj][nk],DP[i][j][k]|((1<<i)*nb))
                #print(i,j,k,nj,nk,DP[i][j][k]|((1<<i)*nb))

ANS=DP[59][0][1]-A[1]

if ANS>=A[0]:
    print(-1)
else:
    print(ANS)




Measured memory_bytes: 9148
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define M (1000000007)
#define N (20)
int n,d,ans,a[N][N];

int main(){
	scanf("%d%d",&n,&d);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=d;j++)
			scanf("%d",&a[i][j]);
	for (int i=1;i<=n;i++)
		for (int j=i+1;j<=n;j++){
			int all=0;
			for (int k=1;k<=d;k++) all+=(a[i][k]-a[j][k])*(a[i][k]-a[j][k]);
			int t=sqrt(all);
			if (t*t==all) ++ans;
		}
	printf("%d",ans);
}


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

    # ruiseki
    rui = [0]*(n+1)
    for i in range(n):
        rui[i+1] = rui[i] + a[i]
    from collections import Counter
    c = Counter(rui)
    
    # Query
    res = 0
    for v in c.values():
        res += v*(v-1)//2
    print(res)

if __name__ == '__main__':
    main()


Measured memory_bytes: 112976
Imports System
Imports System.Collections.Generic
class P
    shared sub main()
        dim c = Console.ReadLine()
        dim l = new List(of Integer)
        for i as Integer = 0 to c.Length - 1
            l.Add(Integer.Parse(c(i)))
        next i
        if l.count > 1 then
            dim b = false
            for j as Integer = 1 to l.count-1
                if l(j) < 9 then : b = true : end if
            next j
            
            if b then
                Console.WriteLine(l(0)-1 + (l.count-1) * 9)
            else
                Console.WriteLine(l(0) + (l.count-1) * 9)
            end if
        else
            Console.WriteLine(l(0))
        end if
    end sub
end class

Measured memory_bytes: 22224
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl
#define tarce(x) cerr<<#x<<": "<<x<<" "<<endl
#define trace2(x, y) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z) cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define sa(a,n) for(int i =0 ; i<n ; i++) cin>>a[i]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define pb push_back
#define inf 2e18
#define scan() int n; cin>>n ; int a[n+1]; for(int i = 1 ; i<=n ; i++) cin>>a[i]
#define scan2() int n,k; cin>>n>>k ; int a[n+1]; for(int i = 1 ; i<=n ; i++) cin>>a[i]
#define print(a,n) for(int i = 0 ; i < n ; i++) cout<<a[i]<<' '
#define mem(a,v) memset(a,v,sizeof(a))
#define pii pair<int,int>
#define mkp make_pair
using namespace std;
#define N 200005



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

        int n;
        cin >> n;
        int i,a[n+1];
        for(i=1; i<=n; i++)cin >> a[i];

        unordered_map<int,int>mp,mp2;
        for(i=1; i<=n; i++){
            mp[i+a[i]]++;
            mp2[i-a[i]]++;
        }
        int ans=0;
        for(auto i : mp){
            int x=i.first;
            if(mp2[x]){
                ans=ans+mp[x]*mp2[x];
            }
        }
        cout << ans;

        

}


Measured memory_bytes: 27896
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
using Graph=vector<vector<int>>;
typedef long long ll;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

int main(){
    int n,m,x;cin>>n>>m>>x;
    ll ans=10000000;
    vector<vector<int>> a(n,vector<int>(m+1));
    for(int i=0;i<n;i++){
        cin>>a[i][0];
        for(int j=1;j<m+1;j++) cin>>a[i][j];
    }
    for(int bit=0;bit<(1<<n);bit++){
        vector<int> p(m);
        ll count=0;
        for(int j=0;j<n;j++){
            if(bit>>j&1){
                count+=a[j][0];
                for(int k=0;k<m;k++){
                    p[k]+=a[j][k+1];
                }
            }
        }
        int flag=1;
        for(int i=0;i<m;i++){
            if(p[i]>=x) continue;
            else flag=0;
        }
        if(flag) ans=min(ans,count);
    }
    if(ans==10000000) cout<<-1<<endl;
    else cout<<ans<<endl;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=100010;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
	char ch=getchar();ll x=0,f=0;
	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return f?-x:x;
}
int h,n,mxa,a[maxn],b[maxn],dp[1111][22222],ans=1e9;
int main(){
	h=read();n=read();
	FOR(i,1,n){
		a[i]=read();b[i]=read();
		mxa=max(mxa,a[i]);
	}
	MEM(dp,0x3f);
	dp[0][0]=0;
	FOR(i,1,n) FOR(j,0,h+mxa){
		dp[i][j]=dp[i-1][j];
		if(j>=a[i]) dp[i][j]=min(dp[i][j],dp[i][j-a[i]]+b[i]);
	}
	FOR(i,h,h+mxa) ans=min(ans,dp[n][i]);
	printf("%d\n",ans); 
}

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

int n;
vector<vector<P>> G;
vector<int> ans;

void dfs(int v, int p, int c) {
  ans[v]=c;
  for (auto nv : G[v]) {
    if (nv.first==p) continue;
    if (nv.second & 1) dfs(nv.first, v, 1-c);
    else dfs(nv.first, v, c);
  }
}

int main() {
  cin>>n;
  G.assign(n, vector<P>());
  rep(i, n-1) {
    int a,b,c; cin>>a>>b>>c;
    a--; b--;
    G[a].push_back(P(b, c));
    G[b].push_back(P(a, c));
  }
  ans.assign(n, 0);
  dfs(0, -1, 1);
  rep(i, n) cout<<ans[i]<<endl;
  return 0;
}


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

int main(){
 int house[4][3][10]={{{0}}};

 int n;
 cin >> n;

 int b,f,r,v;
 int count=0;
 while( count<n ){
   cin >> b >> f >> r >> v;
   house[b-1][f-1][r-1] += v;

   count++;
 }

 for( int i=0; i<4; i++ ){
   for( int j=0; j<3; j++ ){
     for( int k=0; k<10; k++ ){
       cout << " " << house[i][j][k];
     }
     cout << endl;
   }
   if( i!=3 ){
    for( int l=0; l<20; l++ ){
      cout << "#";
    }
    cout << endl;
   }
 }


 return 0;
}


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

int main() {
  int n;
  cin >>n;
  ll ans = 1;
  for(int i = 1; i<=n; i++){
    ans *= i;
    ans %= 1000000007;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256