akhauriyash/Code-Regression huggingface dataset:
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]

mod = 1000000007

from fractions import gcd

ratios = []
nzero = 0
for a, b in ab:
    if a != 0 and b != 0:
        g = gcd(a, b)
        ratios.append((a // g, b // g))
    elif a == 0 and b == 0:
        nzero += 1
    elif a == 0:
        ratios.append((0, 1))
    else:
        ratios.append((1, 0))

twos = [1]
for i in range(2 * 10 ** 5):
    tmp = twos[-1] * 2
    tmp %= mod
    twos.append(tmp)


from collections import Counter, defaultdict
c = Counter(ratios)
seen = Counter()

targets = []
for key in c:
    x, y = key
    xx = c[key]
    if y != 0:
        yy = seen[(-y, x)] + seen[(y, -x)]
    else:
        yy = seen[(-y, x)]
    if xx != 0 and yy != 0:
        targets.append((xx, yy))
    seen[key] = c[key]

n_frees = 0
for i, (x, y) in enumerate(ratios):
    n_bads = c[(-y, x)] + c[(y, -x)]
    if n_bads == 0:
        n_frees += 1

ans = twos[n_frees]

for x, y in targets:
    ans *= (twos[x] + twos[y] - 1) % mod
    ans %= mod

print((ans - 1 + nzero) % mod)


Measured memory_bytes: 207868
// Closed Rooms
// * frank_c1
// * 2017 / 11 / 14

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

const int maxn = 805;
char s[maxn][maxn];
pii q[maxn * maxn];
int ds[maxn][maxn];
int n, m, l, r;

inline int iabs(int x) {
	return x >= 0 ? x : -x;
}

inline bool inlaw(int x, int y) {
	return x >= 1 && y >= 1 && x <= n && y <= m;
}

int main() {
	int K;
	scanf("%d%d%d", &n, &m, &K);
	for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
	memset(ds, -1, sizeof(ds)); l = 1; r = 0;
	for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) if (s[i][j] == 'S') {
		q[++r] = make_pair(i, j); ds[i][j] = 0;
	} 
	for (; l <= r; ) {
		pii u = q[l++];
		int x = u.first, y = u.second;
		if (ds[x][y] >= K) continue;
		for (int dx = -1; dx <= 1; ++dx)
			for (int dy = -1; dy <= 1; ++dy) if (iabs(dx) + iabs(dy) == 1) {
				int nx = x + dx, ny = y + dy;
				if (inlaw(nx, ny) && ds[nx][ny] < 0 && s[nx][ny] != '#') {
					ds[nx][ny] = ds[x][y] + 1; q[++r] = make_pair(nx, ny);
				}
			}
	} l = 1; r = 0;
	for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) if (ds[i][j] >= 0) {
		ds[i][j] = 0; q[++r] = make_pair(i, j);
	}
	for (; l <= r; ) {
		pii u = q[l++];
		int x = u.first, y = u.second;
		for (int dx = -1; dx <= 1; ++dx)
			for (int dy = -1; dy <= 1; ++dy) if (iabs(dx) + iabs(dy) == 1) {
				int nx = x + dx, ny = y + dy;
				if (inlaw(nx, ny) && ds[nx][ny] < 0) {
					ds[nx][ny] = ds[x][y] + 1; q[++r] = make_pair(nx, ny);
				}
			}
	} int mi = (int)(1e9);
	for (int i = 1; i <= n; ++i) mi = min(mi, min(ds[i][1], ds[i][m]));
	for (int j = 1; j <= m; ++j) mi = min(mi, min(ds[1][j], ds[n][j]));
	printf("%d\n", (mi + K - 1) / K + 1);
	return 0;
}

Measured memory_bytes: 8448
#include <iostream>
using namespace std;
 
int main(void){
    int h, w;

    while (cin >> h >> w, h!=0 || w!=0){
        for (int i = 0; i < h; i++){
            for (int j = 0; j < w; j++)
                cout << "#";
            cout << "\n";
        }
        cout << "\n";
    }
    return 0;
}

Measured memory_bytes: 1120
from collections import defaultdict

M = 998244353
B = pow(10, 18, M)

def ext_euc(a, b):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, b
  while z1 != 1:
    d, m = divmod(z2,z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1, y1

def inv_mod(a, b, m):
  x, y = ext_euc(a, m)
  return (x * b % m)

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(e):
  g = {}
  sum_g = defaultdict(int)
  sum_g[0] = inv_mod(B-1, pow(B, N+1, M)-B, M)
  for i in range(N, 0, -1):
    if i not in e:
      continue
    m = mex({g.get(j, 0) for j in e[i]})
    if m:
      g[i] = m
      x = pow(B, i, M)
      sum_g[m] = (sum_g[m] + x) % M
      sum_g[0] = (sum_g[0] - x) % M
  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(set)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].add(b)
  return e

def solve(N, edge):
  sum_g = list(map(calc_grundy, edge))
  ret = 0
  for gx, sx in sum_g[0].items():
    for gy, sy in sum_g[1].items():
      gz = gx^gy
      sz = sum_g[2][gz]
      if sz:
        ret = (ret + sx*sy*sz)%M
  return ret

N = int(input())
edge = [read_edge() for i in range(3)]

print(solve(N, edge))

Measured memory_bytes: 73504
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n; cin>>n;
  vector<int> a(2*n);
  for(int i=0; i<2*n; i++) cin>>a.at(i);
  int ans=0;
  for(int i=0; i<n; i++){
    int sum=0;
    for(int j=0; j<=i; j++){
      sum+=a.at(j);
    }
    for(int j=i; j<n; j++){
      sum+=a.at(n+j);
    }
    ans = max(ans,sum);
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h> 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define cout(x) cout<<x<<endl
#define all(v) v.begin(), v.end()
using namespace std;
//型エイリアス
using vi = vector<int>;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
const ll inf = 1e18;
const int N = 2e5 + 10;


int main(){
    int n,m;
    cin >> n;
    vi t(n);
    rep(i,n) cin >> t[i];
    cin >> m;
    vi p(m),x(m);
    rep(i,m) cin >> p[i] >> x[i];

    int sum = 0;
    rep(i,m){
        sum = 0;
        rep(j,n){
            if(p[i]-1==j) sum += x[i];
            else sum += t[j];
        }
        cout(sum);
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int dp[3001][3001];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	string s,t;
	cin>>s>>t;
	int n = s.size();
	int m = t.size();
	
	for (int i=1; i<=n; i++){
		for (int j=1; j<=m; j++){
			if(s[i-1]==t[j-1]){
				dp[i][j] = dp[i-1][j-1]+1;
			}
			else{
				dp[i][j] = max(dp[i][j-1], dp[i-1][j] );	
			}
		}
	}
//	cout<<"* * ";
//	for (int i=0;i<=m;i++)cout<<t[i]<<" ";
//	cout<<"\n";
//	for (int i=0; i<=n; i++){
//		if(i==0)
//			cout<<"* ";
//		else
//			cout<<s[i-1]<<" ";
//		for(int j=0; j<=m; j++){
//			cout<<dp[i][j]<<" ";
//		}
//		cout<<"\n";
//	}

	list<char> lcs;
   
 int i = n, j = m;
   while (i > 0 && j > 0)
   {

      if (s[i-1] == t[j-1])
      {
          lcs.push_front( s[i-1] );
          i--; j--;
      }

      else if (dp[i-1][j] >= dp[i][j-1])
         i--;
      else
         j--;
   }
	for (auto c:lcs)cout<<c;
	return 0;
};


Measured memory_bytes: 38856
N = int(input())
AB = [list(map(int,input().split())) for i in range(N)]

sortedAB = sorted(AB, key= lambda x: x[1])

import sys
work = 0

for i in range(N):
    work += sortedAB[i][0]
    if work > sortedAB[i][1]:
        print('No')
        sys.exit()
        
print('Yes')

Measured memory_bytes: 55260
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define irep(i,a,b) for(ll i=ll(a);i>ll(b);i--)
using ll = long long;
using namespace std;

ll GCD(ll a, ll b) { return b ? GCD(b, a%b) : a; }
//sort(a, a + N, greater<ll>())   // descend
//sort(a, a+N)                    //  ascend

/* 
void comb(vector<vector <ll> > &v) {
	ll mod=1000000007;
	rep (i,0,v.size()) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	rep (k,1,v.size()) {
		rep (j,1,k) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j])%mod;
		}
	}
}
/*main内でnCn~nC0 生成 **
vector<vector<ll> > v(n + 1, vector<ll>(n + 1, 0));
comb(v);
*/

int main(){
	ll n,d;
	cin>>n>>d;
	ll fuck =2*d+1;
	if(n%fuck==0)cout<<n/fuck;
	else cout<<n/fuck+1;
}




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

long long calcPermutation(long long x, long long y)
{
    long long ans = 1;
    for (long long i = 0; i < y; i++)
    {
        ans *= (x - i);
    }
    return ans;
}

long long calcCombination(long long x, long long y)
{
    if (x * y == 0)
    {
        return 0;
    }
    if ((x - y) < y)
    {
        y = x - y;
    }
    long long ans = calcPermutation(x, y);
    while (y > 0)
    {
        ans /= y;
        y--;
    }
    return ans;
}

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

    sort(a, a + n);
    int ans = 0;
    long long maximum = 0;
    for (int i = 0; i < n - 1; i++)
    {
        if (maximum <= min(a[n - 1] - a[i], a[i]))
        {
            maximum = min(a[n - 1] - a[i], a[i]);
            ans = i;
        }
    }

    cout << a[n - 1] << " " << a[ans] << endl;
}


Measured memory_bytes: 1024
use std::io::prelude::*;
use std::io;

fn main() {
  let mut buffer = String::new();
  let stdin = io::stdin();
  let mut handle = stdin.lock();

  handle.read_line(&mut buffer).unwrap();
  let word = buffer.trim();
  let word = word.to_lowercase();

  let mut buffer = String::new();
  let mut count = 0;
  
  loop {
    buffer.clear();
    handle.read_line(&mut buffer).unwrap();
    let line = buffer.trim();
    if line == "END_OF_TEXT" {
      break;
    }
    let line = line.to_lowercase();
    count += line.split_whitespace()
        .filter(|s| s == &word)
        .count();
  }

  println!("{}", count);
}

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

int main() {
    int N; cin >> N;
    vector<int> A(N), B(N), C(N);
    rep(i, N){
        cin >> A[i];
    }
    rep(i, N){
        cin >> B[i];
    }
    rep(i, N){
        cin >> C[i];
    }

    sort(A.begin(), A.end());
    sort(C.begin(), C.end());

    long long ans = 0;
    rep(i, N){
        long long a;
        a = lower_bound(A.begin(), A.end(), B[i]) - A.begin();
        long long c;
        c = C.end() - upper_bound(C.begin(), C.end(), B[i]);
        ans += a*c;
    }

    cout << ans << endl;

}

Measured memory_bytes: 1408
s = gets.chomp

acgt = "ACGT".chars

max = 0

(0..(s.length-1)).to_a.repeated_combination(2) do |a,b|
  c = s[a..b]
  if (c.chars - acgt) == []
    max = [max, c.length].max
  end
end

puts max

Measured memory_bytes: 1788
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int x1 = sc.nextInt();
    int y1 = sc.nextInt();
    int x2 = sc.nextInt();
    int y2 = sc.nextInt();
    int l = x2 - x1;
    int m = y2 - y1;
    int x3 = x2 - m;
    int y3 = y2 + l;
    int x4 = x3 - l;
    int y4 = y3 - m;
    
    System.out.println(x3 + " " + y3 + " " + x4 + " " + y4);
  }
}

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

int main() {
    int64_t x; cin >> x;
    int64_t a = 100;
    int cnt = 0;
    while(a < x) {
        a = a * 1.01;
        cnt++;
    }
    cout << cnt << '\n';
    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define rep(i,j,k) for(ll i=(ll)j;i<(ll)k;i++)
#define itrep(i,x) for(auto i=(x).begin(); i!=(x).end();i++)
#define Sort(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define vec vector
#define INF INT_MAX
#define INFL 1e18
#define MOD 1000000007
#define pb push_back
#define MP make_pair
#define PI 3.1415926535
typedef long long int ll;
typedef std::pair<int,int> P;
int D=1;
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};

using namespace std;

vector<int> v;
int n,k,s;
int ans=0;
void dfs(int sum, int deep, int count){
    if(count==k){
        if(sum==s)ans++;
        return;
    }
    if(deep==n)return;
    dfs(sum+v[deep],deep+1,count+1);
    dfs(sum,deep+1,count);
    return;
}

int main(){
    while(cin>>n>>k>>s && n){
        ans=0;
        v.resize(n);
        rep(i,0,n)v[i]=i+1;
        dfs(0,0,0);
        cout<<ans<<endl;
    }
    
    
    
    
    return 0;
}



Measured memory_bytes: 3108
#include <stdio.h>

#define N 8
#define FREE 1
#define NOT (-1)
#define TRUE 2
#define FALSE 3


int yoko[N];
int tate[N];
int right_c[2*N-1];
int left_c[2*N-1];

int check[N][N];

void init();
void print();
void recursive(int);


int main(){
  int i=0;
  int j=0;
  int k=0;
  int r=0;
  int c=0;

  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      check[i][j]=FALSE;
    }
  }

  scanf("%d", &k);
  for(i=0;i<k;i++){
    scanf("%d%d",&r,&c);
    check[r][c]=TRUE;
  }
  
  init();
  recursive(0);

  return 0;
}

void init(){
  int i=0;
  for(i=0;i<N;i++){
    tate[i]=FREE;
    yoko[i]=FREE;
  }

  for(i=0;i<N*2-1;i++){
    left_c[i]=FREE;
    right_c[i]=FREE;
  }

}

void recursive(int i){
  int j=0;

  if(i==N){
    print();
    return;
  }

  for(j=0;j<N;j++){
    if(tate[j]==NOT || left_c[i+j]==NOT || right_c[i-j+N-1]==NOT) continue;

    yoko[i]=j;
    tate[j]=NOT;
    left_c[i+j]=NOT;
    right_c[i-j+N-1]=NOT;

    recursive(i+1);

    yoko[i]=FREE;
    tate[j]=FREE;
    left_c[i+j]=FREE;
    right_c[i-j+N-1]=FREE;
  }
}

void print(){
  int i=0;
  int j=0;

  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      if(check[i][j]==TRUE){
	if(yoko[i]!=j) return;
      }
    }
  }

  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      if(yoko[i]==j) printf("Q");
      else printf(".");
    }
    printf("\n");
  }
}



Measured memory_bytes: 2096
N, M = [int(i) for i in input().split()]

N = [[] for i in range(N)]
for i in range(M):
    aidu = [int(i) for i in input().split()]
    N[aidu[0]-1].append([i, aidu[1]])

for i in N:
    i.sort(key=lambda x:x[1])

aidudu = []
for i, n in enumerate(N):
    for j, m in enumerate(n):

        pref_num = i+1
        pref_keta = 0
        while(int(pref_num / 10)):
            pref_num = int(pref_num / 10)
            pref_keta += 1
        pref_moji = "0" * (5 - pref_keta) + str(i+1)

        city_num = j+1
        city_keta = 0;
        while(int(city_num / 10)):
            city_num = int(city_num / 10)
            city_keta += 1
        city_moji = "0" * (5 - city_keta) + str(j+1)

        m = [m[0], pref_moji+city_moji]

        aidudu.append(m)

aidudu.sort(key=lambda x:x[0])

for i in aidudu:
    print(i[1])

Measured memory_bytes: 48756
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9 + 7;
const int INF = 100100100;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define debug(x) cerr << #x << ": " << x << endl

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N; cin >> N;
  vector<int> A(N); REP(i, N) cin >> A[i];
  vector<int> B(N); REP(i, N) cin >> B[i];
  vector<int> C(N-1); REP(i, N-1) cin >> C[i];
  int ans = 0;

  ans += B[A[0]-1];
  // debug(ans);
  FOR(i, 1, N){
    // debug(i);
    ans += B[A[i]-1];
    // debug(ans);
    if(A[i] == A[i-1] + 1) ans += C[A[i-1]-1];
    // debug(ans);
  }
  cout << ans << '\n';
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define VSORT(v) sort(v.begin(), v.end())
#define DVSORT(v) sort(v.begin(), v.end(),greater<int>())
#define SORT(v, n) sort(v, v+n)
#define DSORT(v,n) sort(v, v+n,greater<int>())
#define vi vector<int>
#define pb push_back
#define P pair<int,int>


template <class T> void chmin(T&a, const T&b) { a = min(a,b); }
template <class T> void chmax(T&a, const T&b) { a = max(a,b); }

const double EPS =1e-9;
const long INF =999999999;
const long MOD =1000000007; //10^9+7
#define PI 3.14159265258979

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

int main(void){
	int N,M,x,y;
	vector<P> students;
	vector<P> checkpoint;
	cin>>N>>M;

	FOR(i,0,N){
		cin>>x>>y;
		P student;
		student.first=x;
		student.second=y;
		students.pb(student);
	}
	
	FOR(i,0,M){
		cin>>x>>y;
		P check;
		check.first=x;
		check.second=y;
		checkpoint.pb(check);
	}

	
	FOR(i,0,N){
		int minlength=INF;
		int minnumber=0;
		FOR(j,0,M){
			int dx=abs(students[i].first-checkpoint[j].first);
			int dy=abs(students[i].second-checkpoint[j].second);
			if((dx+dy)<minlength){
				minlength=dx+dy;
				minnumber=j+1;
			}
		}
		printf("%d\n",minnumber);
	}
	return 0;
}



Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

int64_t f(int64_t x, int64_t y)
{
    if (x == 0) {
        return -y;
    }
    return y / x * 2 * x + f(y % x, x);
}

int main()
{
    int64_t n, x;
    cin >> n >> x;

    cout << n + f(min(x, n - x), max(x, n - x)) << endl;

    return 0;
}

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





int N, A, B;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> A >> B;
    int d = B - A;

    if (d % 2 == 0) printf("Alice\n");
    else printf("Borys\n");
}

Measured memory_bytes: 256
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        HashMap<Integer,Integer> have = new HashMap<>();
        for(int i=0;i<n;i++){
            int d = sc.nextInt();
            have.put(d,have.getOrDefault(d,0)+1);
        }
        int m = sc.nextInt();
        HashMap<Integer,Integer> need = new HashMap<>();
        for(int i=0;i<m;i++){
            int D = sc.nextInt();
            need.put(D,need.getOrDefault(D,0)+1);
        }
        boolean flag = true;
        for(int w:need.keySet()){
            flag &= need.get(w)<=have.getOrDefault(w,-1);
        }
        String ans = flag?"YES":"NO";
        System.out.println(ans);
    }
}


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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define fst first
#define snd second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define EPS (1e-9)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }

const string YES = "";
const string NO  = "";

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

// B

void solve() {

}

int main() {
  int n;
  double d;
  cin >> n >> d;
  int cnt = 0;
  double x,y;
  rep(i,n) {
    cin >> x >> y;
    if( x * x + y * y <= d * d ) ++cnt;
    
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 3812
#include<bits/stdc++.h>
using namespace std;
#define int long long
int solve(pair<int,int> d,vector<pair<int,int>> c)
{
    int ret=0;
    set<pair<int,int>>s;
    for(auto pii:c)
    {
        s.insert(pii);
    }
    while(!s.empty())
    {
        auto pii = *s.begin();
        ret++;
        s.erase(pii);
        while(s.count(make_pair(pii.first+d.first,pii.second+d.second)))
        {
            pii = make_pair(pii.first+d.first,pii.second+d.second);
            s.erase(pii);
        }
    }
    return ret;
}
#undef int
int main()
{
    #define int long long
    int n;
    cin>>n;
    vector<pair<int,int>> c(n);
    for(int i=0;i<n;++i)cin>>c[i].first>>c[i].second;
    sort(c.begin(),c.end());
    int ans = INT_MAX;
    for(int i=0;i<n;++i)
    {
        for(int j=i+1;j<n;++j)
        {
            ans = min(ans,solve(make_pair(c[j].first-c[i].first,c[j].second-c[i].second),c));   
        }
    }
    if(n == 1)ans = 1;
    cout<<ans<<endl;
}

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

using namespace std;

typedef long long ll;

ll A[200001];

int main() {
    ll N;
    ll MOD = 1000000007;
    ll sum = 0;
    cin >> N;

    for (int i = 1; i <= N; i++) {
        cin >> A[i];
        sum += A[i];
        sum %= MOD;
    }

    ll ans = 0;
    for (int i = 1; i < N; i++) {
        sum -= A[i];
        if (sum < 0) { sum += MOD; }
        //printf("sum: %d, a: %d\n", sum, A[i]);
        ans += sum * A[i];
        ans %= MOD;
    }

    cout << ans << endl;
}

Measured memory_bytes: 5140
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 10;
char buf[maxn], str[maxn * 6][10];
int idx[maxn * 6], k;
bool cmp(int l, int r) {
	return strcmp(str[l], str[r]) < 0;
}
int main() {
	scanf("%s", buf);
	int len = strlen(buf);
	scanf("%d", &k);
	int scnt = 0;
	for (int L = 1; L <= k; ++L) {
		for (int i = 0; i + L <= len; ++i) {
			for (int j = 0; j < L; ++j)
				str[scnt][j] = buf[i + j];
			str[scnt][L] = 0;
			++scnt;
		}
	}
	for (int i = 0; i < scnt; ++i)
		idx[i] = i;
	sort(idx, idx + scnt, cmp);
	int id = 0;
	while (k > 1 && id < scnt) {
		while (id + 1 < scnt && strcmp(str[idx[id]], str[idx[id + 1]]) == 0)
			++id;
		--k;
		++id;
	}
	printf("%s\n", str[idx[id]]);
	return 0;
}

Measured memory_bytes: 640
//#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 9;
const int infint = 1e9 + 7;
const int MAXN = 2e5 + 7;
const double eps = 1e-9;
const long double pi = 3.1415926535897932384626433832795;
const long double e = 2.71828182845904523536028747135266;
inline ll read()
{
    ll kr = 1, xs = 0;char ls;ls = getchar();
    while (!isdigit(ls)){
        if (!(ls ^ 45)) kr = -1;
        ls = getchar();
    }
    while (isdigit(ls)){
        xs = (xs << 1) + (xs << 3) + (ls ^ 48);ls = getchar();
    }return xs * kr;
}
// inline __int128 read128()
// {
//     __int128 kr=1,xs=0;char ls;ls=getchar();
//     while(!isdigit(ls)){
//         if(!(ls^45)) kr=-1;ls=getchar();
//     }
//     while(isdigit(ls)){
//         xs=(xs<<1)+(xs<<3)+(ls^48);ls=getchar();
//     }
//     return xs*kr;
// }
inline ull readull()
{
    ull xs = 0;char ls;ls = getchar();
    while (!isdigit(ls))ls = getchar();
    while (isdigit(ls)){
        xs = (xs << 1) + (xs << 3) + (ls ^ 48);ls = getchar();
    }return xs;
}
inline void writeull(ull x)
{
    if (x < 0){
        x *= -1;putchar('-');
    }
    if (x >= 10) writeull(x / 10);
    putchar('0' + x % 10);
}
inline void write(ll x)
{
    if (x < 0){
        x *= -1;putchar('-');
    }
    if (x >= 10) write(x / 10);
    putchar('0' + x % 10);
}
// inline void write(__int128 x){
//     if(x<0){x*=-1;putchar('-');}
//     if(x>=10) write(x/10);
//     putchar('0'+x%10);
// }
///////////////////////////////////////////////////////////////////////////////////////
int a[MAXN],b[MAXN],c[MAXN],d[MAXN],n;
int main()
{
    // ios_base::sync_with_stdio(0);
    // cin.tie(0),cout.tie(0);
    int t = 1;
    // t = read();
    while (t--)
    {
        n=read();
        int flag=0;
        for (int i=0;i<n;i++){
            a[i]=read();
            c[a[i]]++;
        }
        for (int i=0;i<n;i++){
            b[i]=read();
            d[b[i]]++;
        }
        for (int i=1;i<=n;i++){
            if(c[i]+d[i]>n) {
                cout << "No" << endl;
                return 0;
            }
            c[i]+=c[i-1];
            d[i]+=d[i-1];
        }
        for (int i=1;i<=n;i++){
            flag=max(flag,c[i]-d[i-1]);
        }
        cout << "Yes" << endl;
        for (int i=0;i<n;i++){
            if(i) cout << " ";
            cout << b[(i-flag+n)%n];
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 6740
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
s = 0
for i in range(N):
    s += B[A[i]-1]
    if i < N - 1 and A[i] + 1 == A[i+1]:
        s += C[A[i]-1]
print(s)

Measured memory_bytes: 38256
#include <bits/stdc++.h>
int main()
{
    int64_t n;
    int64_t ans = 0;
    std::cin >> n;
    std::vector<int64_t> A;
    for (int i = 0; i < n; ++i) {
        int64_t temp = 0;
        std::cin >> temp;
        A.push_back(temp);
    }
    std::sort(A.begin(), A.end(), std::greater<int64_t>());
    for (int i = 1; i < n; ++i) {
        int j = i / 2;
        ans += (A[j]);
        //std::cout << j << " " << A[j] << std::endl;  ////
    }
    std::cout << ans << std::endl;
}

Measured memory_bytes: 5360
import scala.io.StdIn._

object Main extends App {

  val Array(x,k,d) = readLine().split(" ").map(_.toLong)

  def solve() = {
    val xAbs = x.abs
    val movedCnt = xAbs / d
    if(k > movedCnt) {
      val nearP = xAbs % d
      val farP = (xAbs - d).abs
      val fixP = Math.min(nearP, farP)

      if(fixP == nearP) {
        val restMoveCnt = k - movedCnt
        if(restMoveCnt % 2 == 0) nearP else (nearP - d).abs
      } else {
        val restMoveCnt = k - movedCnt - 1
        if(restMoveCnt % 2 == 0) farP else (farP - d).abs
      }
    } else {
      xAbs - (k * d)
    }
  }

  println(solve())

}



Measured memory_bytes: 54860
int a[200010];
 int ans[200010];
 int main(){
 int n;
scanf("%d",&n);
for(int i=2;i<=n;i++)scanf("%d",&a[i]);
   for(int i=2;i<=n;i++)ans[a[i]]++;
 for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
 }

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

int main(void){
    int pasta[3], juice[2];
    for(int i=0; i < 3; i++)
        cin >> pasta[i];
    for(int i=0; i < 2; i++)
        cin >> juice[i];
    
    int min = 1000000;
    for(int i=0; i < 3; i++){
        for(int j=0; j < 2; j++){
            if(pasta[i] + juice[j] - 50 < min){
                min = pasta[i] + juice[j] - 50;
            }
        }
    }
    cout << min << endl;
    return 0;

}

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

#define INF 1000000000
#define rep(i,n) for(int i=1;i<=n;i++)
typedef pair<int,int> P;
int n,m,q;
vector<P> G[100002];//i????????£??\???????????¨????????????
int D[100002];//i?????¨????????¢
int fuman[100002];//i???????????´?????????????????±??????
int neage[200002];//??????j????????´???????????????????????????
int ans[200002];//j??´?????????????????±???????????°

int main(){
  cin>>n>>m>>q;
  rep(i,n)D[i]=INF;
  rep(i,m)neage[i]=INF;
  rep(i,m){
    int u,v;
    cin>>u>>v;
    G[u].push_back(P(i,v));
    G[v].push_back(P(i,u));
  }
  rep(j,q){
    int r;
    cin>>r;
    neage[r]=j;
  }
  queue<int> que;
  que.push(1);
  D[1]=0;
  fuman[1]=INF;
  while(!que.empty()){
    int s=que.front();que.pop();
    for(P p : G[s]){
      int r=p.first;
      int t=p.second;
      if(D[t]>D[s]+1){
        D[t]=D[s]+1;
        fuman[t]=max(fuman[t],min(fuman[s],neage[r]));
        que.push(t);
      }else if(D[t]==D[s]+1){
        fuman[t]=max(fuman[t],min(fuman[s],neage[r]));
      }
    }
  }
  rep(i,n){
    if(fuman[i]!=INF)ans[fuman[i]]++;
  }
  int S=0;
  rep(i,q){
    S+=ans[i];
    cout<<S<<endl;
  }
  return 0;
}

Measured memory_bytes: 13856
import numpy as np
N = int(input())
A, B, C = [list(map(int, input().split())) for _ in range(3)]
score=0
pred_i=np.inf
for i in A:
    if pred_i+1 ==i:
        score=score+C[i-2]+B[i-1]
    else:
        score+=B[i-1]
    pred_i=i
print(score)

Measured memory_bytes: 12492
n = int(input())
x = list(map(int, input().split()))
w = tuple(x)
x.sort()
if x[(n//2)-1] == x[n//2]:
    for i in range(n):
        print(x[n//2])
else:
    for h in w:
        if h <= x[(n//2)-1]:
            print(x[n//2])
        else:
            print(x[(n//2)-1])

Measured memory_bytes: 30708
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    H,W,D=map(int,input().split())
    A=[() for _ in range(H*W)]
    for i in range(H):
        a=list(map(int1,input().split()))
        for j,x in enumerate(a):
            A[x]=(i,j)
    c=[[0] for _ in range(D)]
    for i in range(D):
        for k,j in enumerate(range(i,H*W-D,D)):
            c[i].append(c[i][k]+abs(A[j][0]-A[j+D][0])+abs(A[j][1]-A[j+D][1]))
    Q=int(input())
    for _ in range(Q):
        L,R=map(int1,input().split())
        print(c[L%D][R//D]-c[L%D][L//D])

if __name__ == '__main__':
    main()


Measured memory_bytes: 65020
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int x=sc.nextInt();
        int tmp;
        int min=Integer.MAX_VALUE;
        for(int i=0;i<n;i++){
          tmp=sc.nextInt();
          min=Math.min(min,tmp);
          x-=tmp;
        }
        System.out.println(n+x/min);
    }
}

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

using namespace std;
#define ll long long
#define pb push_back
#define vi vector<int>
#define vll vector<long long>
#define inf 1000000100
#define infll 1LL << 50

int main()
{
    int n, m;
    cin >> n >> m;
    vector<tuple<int, int, ll>> edge;
    vll dist(n+1);
    while(m--)
    {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        edge.pb(make_tuple(a, b, -c));
    }
    dist[1] = 0;
    for(int i = 2; i <= n; i++)
    {
        dist[i] = infll;
    }

    for(int i = 0; i < n; i++)
    {
        for(auto e: edge)
        {
            int aa, bb;
            ll cc;
            tie(aa, bb, cc) = e;
            if(dist[aa] == infll)
            {
                continue;
            }

            if(dist[aa] + cc < dist[bb])
            {
                dist[bb] = dist[aa] + cc;
            }
        }

    }
    vi negative(n+1);
    for(int i = 0; i < n; i++)
    {
        for(auto e: edge)
        {
            int aa, bb;
            ll cc;
            tie(aa, bb, cc) = e;
            if(dist[aa] == infll)
            {
                continue;
            }
            if(dist[aa]+cc < dist[bb])
            {
                negative[aa] = 1;
            }
            if(negative[aa])
            {
                negative[bb] = 1;
            }
        }
    }

    if(!negative[n])
    {
        cout << -dist[n] << endl;
    }
    else
    {
        cout << "inf" << endl;
    }

}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int a = Integer.parseInt(in.next());
		int b = Integer.parseInt(in.next());
		int d = a / b;
		int r = a % b;
		double f = (double)a / b;
		
		System.out.println(d + " " + r + " " + String.format("%.5f", f));
	}
}	


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

int get_digit(long long x) {
    int cnt = 0;
    while (x > 0) {
        x /= 10;
        cnt++;
    }
    return cnt;
}

int main() {
    long long n;
    cin >> n;
    int minimum = 100;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            minimum = min(minimum, max(get_digit(i), get_digit(n / i)));
        }
    }

    cout << minimum << endl;
}   

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		long K = sc.nextInt();
		long S = sc.nextInt();
		long res = 0;
		for(long i = Math.min(K, S); i>=0; i--){
			long v = S-i;
			if(v < K )res+=(v+1);
			else if(v == K) res+=(K+1);
			else if(v <= 2*K){
				long a = v-K;
				res+=K-a+1;
			}
		}
		System.out.println(res);
	}
}

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

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

  vector<int> a(n, 0);

  for(int i = 0; i < n; i++){
    cin >> a[i];
    if(i != n - 1){
      cout << a[i] << " ";
    }
    else{ cout << a[i] << endl;}
  }

  for(int i = 1; i < n; i++){
    int v = a[i];
    int j = i - 1;
    while(j >= 0 && a[j] > v){
      a[j + 1] = a[j];
      j --;
      
    }
    a[j + 1] = v;
    for(int k = 0; k < n; k++){
      if(k != n - 1){
      cout << a[k] << " ";
      }
      else{ cout << a[k] << endl;}
    }
  }
}


Measured memory_bytes: 3084
/**
 *    original:  tourist
**/
#include <bits/stdc++.h>
 
using namespace std;

//debug
int debug = 0;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  int n = (int) s.size();
  vector<int> a(n + 1);
  for (int i = 0; i < n; i++) {
    if(debug)cout << "a[" << i << "]:" << a[i] << '\n';
    
    if (s[i] == '<') {
      a[i + 1] = max(a[i + 1], a[i] + 1);
      if(debug)cout << "< a[" << i+1 << "]:" << a[i + 1] << '\n';
    }
  }
  for (int i = n - 1; i >= 0; i--) {
    if(debug)cout << "a[" << i << "]:" << a[i] << '\n';
    if (s[i] == '>') {
      a[i] = max(a[i], a[i + 1] + 1);
      if(debug)cout << "> a[" << i << "]:" << a[i] << '\n';
    }
  }
  long long ans = 0;
  for (int i = 0; i <= n; i++) {
    ans += a[i];
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 2844
import java.util.*;

public class Main{
    public static void main(String[]args){
    Scanner sc = new Scanner(System.in);
    int N =sc.nextInt();
    long A[] = new long[N];
    long B[] = new long[N-1];
     for(int i=0; i<N; i++){
         A[i]= sc.nextInt();
     }
     int ans =0;
        B[N-2]=A[N-1];
        for(int i=N-1; i>1; i--){
            B[i-2]=(A[i-1]+B[i-1])%1000000007;
        }
        for(int i=0; i<N-1; i++){
            ans = (int)((ans+A[i]*B[i])%1000000007);
        }

        System.out.println(ans);
 }
}


Measured memory_bytes: 62492
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def error_mat_print(m):
    for r in m:
        print(r, file=sys.stderr)

def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(L, A):

    dp = [[sys.maxsize] * (L+1) for _ in range(5)]
    dp[0][0] = 0

    for i, a in enumerate(A):
        t = dp[0][i]
        dp[0][i+1] = t + a
        t = min(t, dp[1][i])
        dp[1][i+1] = t+ ((a%2) if a != 0 else 2)
        t = min(t, dp[2][i])
        dp[2][i+1] = t + ((a+1)%2)
        t = min(t, dp[3][i])
        dp[3][i+1] =t + ((a%2) if a != 0 else 2)
        t = min(t, dp[4][i])
        dp[4][i+1] = t + a


    return min([dp[i][L] for i in range(5)])

def main():
    L = read_int()
    A = [read_int() for _ in range(L)]
    print(slv(L, A))


if __name__ == '__main__':
    main()


Measured memory_bytes: 54632
#include<iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    int i[n];
    for(int j=0;j<n;j++){
        int m;
        cin>>m;
        i[j]=m;
    }
    for(int k=n-1;k>=0;k-=1){
        if(k==n-1){
            cout<<i[k];
            
        }
        else{
            cout<<" "<<i[k];
            
        }
    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 3080
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
	char c[52], *p, *q;
	int count = 0, n;

	scanf("%d", &n);

	/*fgets(c, 52, stdin);
	p = strrchr(c, '\n');
	*p = '\0';*/

	scanf("%s", c);

	for (q = c; *q != '\0'; q++)
	{

		if (*q == 'A')
		{
			if (*(q + 1) == 'B')
			{
				if (*(q + 2) == 'C')
				{
					count++;
				}
			}

		}
	}

	printf("%d", count);

	return 0;
}



Measured memory_bytes: 128
MOD = 1000000007
N = int(input())
s1 = input().strip()
s2 = input().strip()
ans = 1
i = 0
pi = -1
while i < N:
    if s1[i] != s2[i]:
        if i == 0:
            ans *= 6
        else:
            if s1[pi] != s2[pi]:
                ans *= 3
            else:
                ans *= 2
        pi = i
        i += 2
    else:
        if i == 0:
            ans *= 3
        else:
            if s1[pi] != s2[pi]:
                ans *= 1
            else:
                ans *= 2
        pi = i
        i += 1
    ans = ans % MOD

print(ans)


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

void solve()
{
  int n,m,x;
  cin >> n >> m >> x;
  vector<vector<int>>arr(n,vector<int>(m,0));
  vector<int>c_i(n);
  for (int c=0;c<n;c++)
    {
      cin >> c_i[c];
      for (int c1=0;c1<m;c1++)
        {
          cin >> arr[c][c1];
        }
    }
    int mini=12*1000000;
    for (int c=0;c<=(1<<n)-1;c++)
      {
        vector<int>indexes;
        for (int c1=1,ind=0;c1<=c;c1*=2,ind++)
          if ((c1&c)==c1)
            indexes.push_back(ind);
        vector<int>subs(m,0);
        int total_cost=0;
        for (int c2=0;c2<indexes.size();c2++)
              {for (int c1=0;c1<arr[indexes[c2]].size();c1++)
                  subs[c1]+=arr[indexes[c2]][c1];total_cost+=c_i[indexes[c2]];}
        
        int flag=1;
        for (int c1=0;c1<subs.size();c1++)
          if (subs[c1]<x)
            {flag=-1;break;}
        if (flag==1)
          mini=min(mini,total_cost);
      }
      if (mini==12*1000000)
        cout << -1 << endl;
      else cout << mini << endl;

}

int main ()
{
      
     int t;
     t=1;//cin >> t;
     for (int tt=1;tt<=t;tt++)
     {
         solve();

     }

    return 0;
     
     
     
     
 }


Measured memory_bytes: 3636
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

int n, m;
int turn[2][21];
int main() {
  int test_case = 0;
  while (scanf("%d %d", &n, &m), n|m) {
    test_case++;
    MEMSET(turn, 0);
    turn[0][0] = n;
    REP(t, 1000000) {
      int prev = t & 1;
      int next = prev ^ 1;
      MEMSET(turn[next], 0);
      if (turn[prev][m]) {
        printf("Case %d: %d\n", test_case, t);
        goto end;
      }
      REP(i, n) {
        turn[next][i + 1] += turn[prev][i] / 2;
        turn[next][0] += turn[prev][i] / 2;
        turn[next][i] += turn[prev][i] % 2;
      }
    }
    assert(false);
end:;
  }
}

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

int main() {
	char b;
	cin >> b;
	if (b == 'A')cout << "T" << endl;
	else if (b == 'C')cout << "G" << endl;
	else if (b == 'G')cout << "C" << endl;
	else cout << "A" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int x[200000];
int main(){
	int n,m;cin>>n>>m;
	rep(i,m){
		scanf("%d",&x[i]);
	}
	sort(x,x+m);
	int sum=x[m-1]-x[0];
	vector<int>v;
	rep(i,m-1){
		v.push_back(x[i+1]-x[i]);
	}
	sort(v.begin(),v.end(),greater<>());
	rep(i,n-1){
		if(i>=v.size())break;
		sum-=v[i];
	}
	cout<<sum<<endl;
}

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


int main()
{
	int n;
	cin>>n;
	int g;
	for(int i=1;i<=n;i++) {
		int x;
		cin>>x;
		if(i==1){
			g=x;
		}
		else {
			g=__gcd(g,x);
		}
	}
	cout<<g<<endl;
	return 0;
}

Measured memory_bytes: 384
n=int(input())
dic={}
maxx=-1
for _ in range(n):
    s=input()
    if s in dic:
        dic[s]+=1
        
    else:
        dic[s]=1
    maxx=max(maxx,dic[s])
for i in sorted(dic.keys()):
    if dic[i]==maxx:
        print(i)

Measured memory_bytes: 32136
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int main(void)
{
    int n;
    cin>>n;
    vi s(n);
    for (auto & it : s)
        cin>>it;
    sort(all(s));
    int a = s.back();
    int b = s[0];
    for (auto it : s)
        if (abs(it - (a + 1) / 2) < abs(b - (a + 1) / 2))
            b = it;
    cout << a << ' ' << b << '\n';
    return 0;
}

Measured memory_bytes: 640
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,m;
    cin >> n >> m;
    vll a(m);
    ll sum=0LL;
    REP(i,m){
        cin >> a[i];
        sum+=a[i];
    }
    cout << max(-1LL,n-sum) << endl;
    return 0;
}

Measured memory_bytes: 3692
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define in insert
#define b_s binary_search
#define rev reverse
#define all(x) (x).begin(),(x).end()
#define pf push_front
#define pob pop_back
#define pof pop_front
#define u_b upper_bound
#define l_b lower_bound
#define ios ios_base::sync_with_stdio(0);cin.tie();cout.tie();
#define mod 998244353
#define Max 100005

using namespace std;

int main()
{
    int k;
    cin >> k;
    ll ans = 0, g, temp;
    for(int i = 1; i <= k; i++)
    {
        for(int j = 1; j <= k; j++)
        {
            g = __gcd((ll)i, (ll)j);
            temp = g;
            for(int s = 1; s <= k; s++)
            {
                g = __gcd(g, (ll)s);
                ans += g;
                g = temp;
            }
        }
    }
    cout << ans << endl;
}


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

int main()
{
	int a,b,c;
	int ans=-1;
	cin >> a >> b >> c;
	while(c<10000){
		if(c%(a+b)<=a){
			ans=c;
			break;
		}
		c+=60;
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 3136
#include <iostream>
#include <ccomplex>
#include <vector>
#include <cassert>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <numeric>
#include <list>
#include <assert.h>
#include <math.h>
#include <valarray>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <complex>
#include <list>
#include <time.h>
#include <stack>
#include <locale>
#include <clocale>
#include <ctype.h>
#include <wchar.h>
#include <random>
#include <vector>

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

vector<vector<LL>> dist(52, vector<LL>(52,-1));
LL INF = 1145141919;

void dfs(int i, int j,int d) {
	if (dist[i][j] > d) {
		dist[i][j] = d;
	}
	if (dist[i + 1][j] > dist[i][j]+1) {
		dfs(i + 1, j, dist[i][j] + 1);
	}
	if (dist[i - 1][j] > dist[i][j] + 1) {
		dfs(i - 1, j, dist[i][j] + 1);
	}
	if (dist[i][j + 1] > dist[i][j] + 1) {
		dfs(i, j + 1, dist[i][j] + 1);
	}
	if (dist[i][j - 1] > dist[i][j] + 1) {
		dfs(i, j - 1, dist[i][j] + 1);
	}
}

int main() {
	LL H, W;
	cin >> H >> W;

	LL cnt = 0;

	REP(i, H) {
		string s;
		cin >> s;
		REP(j, W) {
			if (s[j] == '.') {
				dist[i + 1][j + 1] = INF;
				cnt++;
			}
		}
	}

	dist[1][1] = 0;

	dfs(1, 1, 0);

	if (dist[H][W] < INF) {
		cout << cnt - dist[H][W]-1 << endl;
	}
	else {
		cout << -1 << endl;
	}
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int n,w[105],sum=0,s=0,minn=100005,maxx=-1;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
    {
        cin>>w[i];
        sum+=w[i];
        if(w[i]>maxx) maxx=w[i];
    }
    for(int i=0;i<n;i++)
    {
        s=0;
        for(int j=0;j<i;j++)
            s+=w[j];
        if(abs(sum-2*s)<minn) minn=abs(sum-2*s);
    }
    cout<<minn<<endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> G;
void solve(int i,vector<vector<int>> &dist){
    queue<int> que;
    que.push(i);
    dist[i][i]=0;
    while(que.size()){
        int q=que.front();que.pop();
        for(auto nq:G[q]){
            if(dist[i][nq]>dist[i][q]+1){
                dist[i][nq]=dist[i][q]+1;
                que.push(nq);
            }
        }
    }
}
int main(){
    int n,x,y;scanf("%d%d%d",&n,&x,&y);
    G.assign(n,vector<int>());
    for(int i=0;i<n-1;i++) G[i].push_back(i+1),G[i+1].push_back(i);
    G[x-1].push_back(y-1),G[y-1].push_back(x-1);
    vector<vector<int>> dist(n,vector<int>(n,1e9+7));
    for(int i=0;i<n;i++) solve(i,dist);
    vector<int> ans(n);
    for(int i=0;i<n;i++)for(int j=0;j<n;j++){
        ans[dist[i][j]]++;
    }
    for(int i=1;i<n;i++)printf("%d\n",ans[i]/2);
    return 0;
}

Measured memory_bytes: 16128
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
  ll w, h;
  cin >> w >> h;
  if(w==1 || h == 1){
    cout << 1 << endl;
  }else{
    ll ans = ((ll)w*h+1) / 2;
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;


int main()
{
    int N,a[55];
    while(cin>>N)
    {
        int t_min=0,t_max=0;
        int pos_min=1;
        int pos_max=1;
        for(int i=1;i<=N;i++)
            cin>>a[i];
        for(int i=1;i<=N;i++)
        {
            if(a[i]<t_min)
                t_min=a[i],pos_min=i;
            if(a[i]>t_max)
                t_max=a[i],pos_max=i;
        }
        cout<<N*2-2<<endl;
        if(abs(t_min)<=abs(t_max))
        {
            for(int i=1;i<=N;i++)
            {
                if(i==pos_max) continue;
                cout<<pos_max<<' '<<i<<endl;
            }
            for(int i=2;i<=N;i++)
                cout<<i-1<<' '<<i<<endl;
        }
        else
        {
            for(int i=1;i<=N;i++)
            {
                if(i==pos_min) continue;
                cout<<pos_min<<' '<<i<<endl;

            }
            for(int i=N-1;i>=1;i--)
                cout<<i+1<<' '<<i<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256