akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define r(i,n) for(int i=0;i<n;i++)
#define rn(i,n) for(int i=1;i<=n;i++)
#define ll long long
const ll mod=1e9+7;

int gcd(int a,int b){
  if(a>b)swap(a,b);
  if(a==0)return b;
  else return gcd(b%a,a);
}

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

  vector<int> a(n);
  r(i,n)cin>>a.at(i);

  int prefix[n+1];
  int suffix[n+1];
  prefix[0]=0;
  for(int i=1;i<n+1;i++){
    prefix[i]=gcd(prefix[i-1],a[i-1]);

  }

  suffix[n]=0;
  for(int i=n-1;i>=0;i--){
    suffix[i]=gcd(suffix[i+1],a[i]);
  }

  int ans=1;
  for(int i=0;i<n;i++){
    ans=max(ans,gcd(prefix[i],suffix[i+1]));
  }

  cout<<ans<<endl;








return 0;

}


Measured memory_bytes: 1408
#![allow(unused_imports, unused_macros, dead_code)]

macro_rules! min {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        it.next().map(|z| it.fold(z, |x, y| min!(x, y)))
    }};
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = min!($($ys),*);
        if $x < t { $x } else { t }
    }}
}
macro_rules! max {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        it.next().map(|z| it.fold(z, |x, y| max!(x, y)))
    }};
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = max!($($ys),*);
        if $x > t { $x } else { t }
    }}
}
macro_rules! ewriteln {
    ($($args:expr),*) => { let _ = writeln!(&mut std::io::stderr(), $($args),*); };
}
macro_rules! trace {
    ($x:expr) => { ewriteln!(">>> {} = {:?}", stringify!($x), $x) };
    ($($xs:expr),*) => { trace!(($($xs),*)) }
}
macro_rules! put {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        if let Some(x) = it.next() { print!("{}", x); }
        for x in it { print!(" {}", x); }
        println!("");
    }};
    ($x:expr) => { println!("{}", $x) };
    ($x:expr, $($xs:expr),*) => { print!("{} ", $x); put!($($xs),*) }
}

const M: i64 = 1_000_000_007;

fn main() {
    let mut sc = Scanner::new();
    let h: usize = sc.cin();
    let w: usize = sc.cin();
    let mut f: Vec<_> = (0..h).map(|_|
        sc.chars()
    ).collect();
    if f[0][0] != '#' {
        put!("Impossible");
        return;
    }

    {
        let mut x = 0;
        let mut y = 0;
        loop {
            f[x][y] = '@';
            if x + 1 < h && f[x+1][y] == '#' {
                x += 1;
            }
            else if y + 1 < w && f[x][y+1] == '#' {
                y += 1;
            }
            else {
                break
            }
        }
    }
    let mut ans = "Possible";
    for i in 0..h {
        for j in 0..w {
            if f[i][j] == '#' {
                ans = "Impossible";
                break;
            }
        }
    }
    put!(ans);
}

use std::io::{self, Write};
use std::str::FromStr;
use std::collections::VecDeque;

struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, }
impl Scanner {
    fn new() -> Self { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } }
    fn cin<T: FromStr>(&mut self) -> T {
        while self.buffer.len() == 0 {
            let mut line = String::new();
            let _ = self.stdin.read_line(&mut line);
            for w in line.split_whitespace() {
                self.buffer.push_back(String::from(w));
            }
        }
        self.buffer.pop_front().unwrap().parse::<T>().ok().unwrap()
    }
    fn chars(&mut self) -> Vec<char> { self.cin::<String>().chars().collect() }
    fn vec<T: FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.cin()).collect() }
}


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

#define db double
#define ll long long
#define RG register

inline int gi()
{
	RG int ret; RG bool flag; RG char ch;
	ret=0, flag=true, ch=getchar();
	while (ch < '0' || ch > '9')
		ch == '-' ? flag=false : 0, ch=getchar();
	while (ch >= '0' && ch <= '9')
		ret=(ret<<3)+(ret<<1)+ch-'0', ch=getchar();
	return flag ? ret : -ret;
}

const db pi = acos(-1.0);
const int N = 142857, inf = 1<<30;

int f[N],et[N],ed[N],nx[N],ew[N],dis[N],cst[N];
bool vis[N];
queue <int> q;
int num;

inline void add(int x,int y,int z,int w)
{
	et[++num]=y, nx[num]=f[x], ed[num]=z, ew[num]=w, f[x]=num;
}

int main()
{
	int n,m,i,x,y,z,w;
	while (true)
		{
			n=gi(), m=gi();
			if (n == 0)
				break;
			for (i=1; i<=m; ++i)
				{
					x=gi(), y=gi(), z=gi(), w=gi();
					add(x,y,z,w), add(y,x,z,w);
				}
			for (i=2; i<=n; ++i)
				cst[i]=dis[i]=inf;
			q.push(1), vis[1]=true;
			while (!q.empty())
				{
					x=q.front(), q.pop(), vis[x]=false;
					for (i=f[x]; i; i=nx[i])
						{
							y=et[i], z=ed[i], w=ew[i];
							if (dis[y] > dis[x]+z)
								{
									dis[y]=dis[x]+z;
									cst[y]=cst[x]+w;
									if (!vis[y])
										q.push(y), vis[y]=true;
								}
							if (dis[y] == dis[x]+z && cst[y] > w)
								cst[y]=w;
						}
				}
			x=0;
			for (i=2; i<=n; ++i)
				x+=cst[i];
			printf("%d\n",x);
			for (i=1; i<=n; ++i)
				f[i]=0;
			num=0;
		}
	return 0;
}

Measured memory_bytes: 3860
N, M = gets.chomp.split(" ").map(&:to_i)
H = gets.chomp.split(" ").map(&:to_i)
E = Array.new(N+1).map{Array.new}
M.times{
  a, b = gets.chomp.split(" ").map(&:to_i)
  E[a] << b
  E[b] << a
}

H.unshift(0)
puts (1..N).count{|i|
  wk = E[i].map{|e| H[e]}.max
  wk.nil? || wk < H[i]
}


Measured memory_bytes: 27884
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

int a[100005];

int main()
{
	int n, m, sum, ans;
	while (~scanf("%d", &n))
	{
		sum = 0;
		memset(a, 0, sizeof(a));
		int i;
		for (i = 0; i < n; i++)
		{
			scanf("%d", &a[i]);
			sum += a[i];
		}
		ans = 0;
		scanf("%d", &m);
		int c, d;
		for (i = 0; i < m; i++)
		{
			scanf("%d%d", &c, &d);
			ans = sum + d - a[c - 1];
			printf("%d\n", ans);
		}
	}
	return 0;
}


Measured memory_bytes: 512
s = list(input())
k = int(input())
#print(ord("z"))
for i in range(len(s)):
  if s[i] != 'a' and 123 - ord(s[i]) <= k:
    k -= (123 - ord(s[i]))
    s[i] = "a"
    #print(k)
#print(s, k)
k %= 26
if ord(s[-1]) + k > 122:
  s[-1] = chr(ord(s[-1]) + k - 26)
else:
  s[-1] = chr(ord(s[-1]) + k)
ans = ""
for i in s:
  ans += i
print(ans)

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

std::chrono::system_clock::time_point start;
std::chrono::system_clock::time_point owari;

string A[51],s;
int h,w,p,d,y,x,cnt;
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};

void IF();

void END(){
  cout<<cnt<<endl;
  exit(0);
}

void BAD_END(){
  cout<<-1<<endl;
  exit(0);
}

bool OK(){
  owari = std::chrono::system_clock::now();
  double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(owari-start).count();
  return elapsed<=1999.999;
}

bool BOOL(){
  if(!OK())BAD_END();
  bool res=0;
  if(s[p]=='~')res^=1,p++;
  if(s[p]=='N'&&d==0)res^=1;
  if(s[p]=='E'&&d==1)res^=1;
  if(s[p]=='S'&&d==2)res^=1;
  if(s[p]=='W'&&d==3)res^=1;
  if(s[p]=='C'&&A[y+dy[d]][x+dx[d]]=='#')res^=1;
  if(s[p]=='T')res^=1;
  p++;
  return res;
}
void MOVE(){
  if(!OK())BAD_END();
  cnt++;
  if(s[p]=='^'){
    int ny=y+dy[d];
    int nx=x+dx[d];
    if(A[ny][nx]!='#')y=ny,x=nx;
  }
  if(s[p]=='v'){
    int ny=y-dy[d];
    int nx=x-dx[d];
    if(A[ny][nx]!='#')y=ny,x=nx;
  }
  if(s[p]=='<')d=(d+3)%4;
  if(s[p]=='>')d=(d+1)%4;
  p++;

  if(A[y][x]=='g')END();
}
void WHILE(){
  if(!OK())BAD_END();
  int idx=++p;
  while(1){
    bool res=BOOL();
    if(!res){
      stack<int>st;
      st.push(1);
      while(st.size()){
        if(s[p]=='{')st.push(1);
        if(s[p]=='}')st.pop();
        p++;
      }
      return;
    }
    while(s[p]!='}'){
      if(s[p]=='{')WHILE();
      else if(s[p]=='[')IF();
      else MOVE();
    }
    p=idx;
  }
  p++;
}
void IF(){
  if(!OK())BAD_END();
  p++;
  bool res=BOOL();
  if(!res){
    stack<int>st;
    st.push(1);
    while(st.size()){
      if(s[p]=='[')st.push(1);
      if(s[p]==']')st.pop();
      p++;
    }
    return;
  }
  while(s[p]!=']'){
    if(s[p]=='{')WHILE();
    else if(s[p]=='[')IF();
    else MOVE();
  }
  p++;
}

void bnf(){
  while(s[p]!='@'){
    if(s[p]=='{')WHILE();
    else if(s[p]=='[')IF();
    else MOVE();
  }
}

int main(){
  start = std::chrono::system_clock::now();
  cin>>h>>w;
  r(i,h)cin>>A[i];
  r(i,h)r(j,w)if(A[i][j]=='s')y=i,x=j;
  cin>>s;
  s+='@';
  bnf();
  BAD_END();
}


Measured memory_bytes: 3188
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue>
#include <list>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <iomanip> // std::std::setprecision(X)
#include <limits>  //std::numeric_limits<int>::max(), min()

int main (void) {

  std::string S;
  std::cin >> S;

  std::unordered_map<char,int> k;
  for(int i=0; i<S.size(); i++) {
    if ( k.count(S[i]) == 0 ) k[S[i]] = 1;
    else k[S[i]]++;
  }

  if ( k.size() != 2 ) {
    std::cout << "No" << std::endl;
    return 0;
  }

  for(auto itr=k.begin(); itr != k.end(); ++itr) {
    if ( itr->second != 2 ) {
      std::cout << "No" << std::endl;
      return 0;
    }
  }
  std::cout << "Yes" << std::endl;

  return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int main() {
	int N, M; cin >> N >> M;
	if (M == 0) {
		cout << 0 << endl;
		return 0;
	}
	vector<double> L(N), a(N), b(N);
	for (int i = 0; i < N; i++)
		cin >> L[i] >> a[i] >> b[i];
	vector< vector<double> > d(N, vector<double>(N));
	for (int i = 0; i < N; i++)
		for (int j = i + 1; j < N; j++) {
			double dL = L[i] - L[j], da = a[i] - a[j], db = b[i] - b[j];
			d[i][j] = dL * dL + da * da + db * db;
		}
	double maxi = 0;
	for (int S = (1 << M) - 1; S < (1 << N);) {
		double sum = 0;
		for (int i = 0; i < N; i++)
			if (S & (1 << i))
				for (int j = i + 1; j < N; j++)
					if ((S & (1 << j)))
						sum += d[i][j];
		maxi = max(maxi, sum);
		int x = S & -S, y = S + x;
		S = ((S & ~y) / x >> 1) | y;
	}
	printf("%.10f\n", maxi);
}

Measured memory_bytes: 1272
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		execute();
	}

	private static void execute() {
		try (Scanner sc = new Scanner(System.in)) {
			int a = sc.nextInt();
			String str = sc.next();
			
			if(a %2 != 0) {
				System.out.println("No");
				return;
			}
			
			String x = str.substring(0, a/2);
			String y = str.substring(a/2, str.length());
			
			if(x.equals(y)) {
				System.out.println("Yes");
				return;
			}
			System.out.println("No");
		}
	}

}

Measured memory_bytes: 22228
#include<bits/stdc++.h>
using namespace std;
typedef vector< vector<int> > vvi;
typedef vector< vector<bool> > vvb;
typedef vector< vector<char> > vvc;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef long long ll;

int main(){
    int n;
    cin >> n;
    map<long long,long long> mp;
    vector<long long> va(n);
    for(int i=0;i<n;i++){
        long long a;
        cin >> a;
        mp[a]++;
        va[i]=a;
    }
    long long all=0;
    for(auto x: mp){
        all+=x.second*(x.second-1)/2;
    }
    long long diff;
    for(int i=0;i<n;i++){
        diff=mp[va[i]]-1;
        cout << all-diff << endl;
    }
    return 0;
}

Measured memory_bytes: 12680
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define bit(n) (1<<(n))
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define yn(x, ok, ng) cout << ((x)?(ok):(ng)) << endl
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
int const INF = 1001001001;


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

string s;
cin >> s;
int n = SZ(s);
cout << s.substr(0,3) << endl;

return 0;
}

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

const int N = 100010;
#define fi first
#define se second

int n, k;
pair<int,int> a[N];
long long ans;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> k;

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

	for (int b = 30; b >= 0; --b) {
		int kk = ((k >> b) & 1);
		sort(a + 1, a + n + 1);

		int s1 = n + 1;
		while(s1 >= 2 && (a[s1 - 1].fi >> b & 1)) --s1;

		if (kk == 1) {
			long long sum = 0;
			for (int i = 1; i < s1; ++i) sum += a[i].se;
			for (int i = s1; i <= n; ++i) a[i].fi -= (1LL << b);
			ans = max(ans, sum);
		} else n = s1 - 1;
	}

	long long sum = 0; for (int i = 1; i <= n; ++i) sum += a[i].se;
	ans = max(ans, sum);

	cout << ans << endl;
}

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

#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void()
#endif

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<pair<int, int>> x(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i].first;
    x[i].second = i;
  }
  sort(x.begin(), x.end());
  vector<int> ans(n);
  for (int i = 0; i < n / 2; i++) {
    ans[x[i].second] = x[n / 2].first;
  }
  for (int i = n / 2; i < n; i++) {
    ans[x[i].second] = x[n / 2 - 1].first;
  }
  for (int i = 0; i < n; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}

Measured memory_bytes: 5556
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

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

template<class T> vector<T> make_vec(size_t a) { return vector<T>(a); }
template<class T, class... Ts> auto make_vec(size_t a, Ts... ts) {
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template<class T, class V>
typename enable_if<is_class<T>::value == 0>::type fill(T &t, const V &v) {
    t = v;
}
template<class T, class V>
typename enable_if<is_class<T>::value != 0>::type fill(T &t, const V &v){
    for (auto &e : t) fill(e, v);
}

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }

#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }


long long L, R;

long long solve() {
    if (R - L > 3000) return 0;

    long long res = 2018;
    for (long long i = L; i < R; ++i) {
        for (long long j = i+1; j <= R; ++j) {
            chmin(res, (i*j) % 2019);
        }
    }
    return res;
}

int main() {
    while (cin >> L >> R) cout << solve() << endl;
}


















Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
vector<int> input(int N) {
  vector<int> vec(N);
  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }
  return vec;
}

int main() {
  string s;
  cin >> s;
  rep(i,s.size()){
    if(i%2==0&&s[i]=='L'){
      cout << "No" << endl;
      return 0;
    }
    if(i%2==1&&s[i]=='R'){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 256
# coding: utf-8

h, w = [int(i) for i in input().split()]

a = [list(input()) for _ in range(h)]

for i in range(h - 1, -1, -1):
    if all([x == "." for x in a[i]]):
        del(a[i])

for j in range(w - 1, -1, -1):
    flg = True
    for i in range(len(a)):
        if a[i][j] == "#":
            flg = False
            break

    if flg:
        for i in range(len(a)):
            del(a[i][j])

for i in a:
    print(''.join(i))

Measured memory_bytes: 3188
// darksta5's template v2.0

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define popb pop_back
#define del erase
#define sz size
#define ins insert
#define FOR(a,b,c) for(int a = b; a < c; a++)
#define FORS(a,b,c) for(int a = b; a <= c; a++)
#define FORN(a,b) for(int a = 0; a < b; a++)
#define FORD(a,b,c) for (int a = b; a >= c; a--)
#define RES(a,b) memset(a,b,sizeof(a))
#define LL long long
#define PI acos(-1)
#define eps 1e-9
#define MOD 1000000007
using namespace std;

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

  string s;
  cin >> s;
  FOR(i, 1, s.sz()) {
    if (s[i] == s[i-1]) {
      cout << i << " " << i + 1 << endl;
      return 0;
    }
    if ((i > 1) && (s[i] == s[i-2])) {
      cout << i - 1 << " " << i + 1 << endl;
      return 0;
    }
  }

  cout << "-1 -1" << endl;
}

Measured memory_bytes: 512
n = int(input())
a = list(map(int, input().split()))
a.sort()
if a[0] >= 0:
    print(sum(a) - 2 * min(a))
    if n == 2:
        print(a[1], a[0])
    else:
        print(a[0], a[1])
        now = a[0] - a[1]
        for i in range(2, n-1):
            print(now, a[i])
            now = now - a[i]
        print(a[-1], now)
elif a[-1] <= 0:
    print(sum(map(abs, a)) + 2 * max(a))
    b = a[::-1]
    print(b[0], b[1])
    now = b[0] - b[1]
    for i in range(2, n):
        print(now, b[i])
        now -= b[i]
else:
    print(sum(map(abs, a)))
    if n == 2:
        print(a[1], a[0])
        exit()
    hu = list(filter(lambda x: x<0, a))
    se = list(filter(lambda x: x>=0, a))
    if len(se) == 1:
        print(a[-1], a[0])
        now = a[-1] - a[0]
        for i in range(1, n-1):
            print(now, a[i])
            now = now - a[i]
    else:
        print(hu[0], se[0])
        now = hu[0] - se[0]
        for i in range(1, len(se)-1):
            print(now, se[i])
            now -= se[i]
        print(se[-1], now)
        now = se[-1] - now
        for i in range(1, len(hu)):
            print(now, hu[i])
            now -= hu[i]


Measured memory_bytes: 62940
#include <bits/stdc++.h>
#define int long long

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

#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)

#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

const int INF = (int)1e9;
const LL INFL = (LL)1e15;
const int MOD = 1e9 + 7;

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

LL ketawa(LL a){
    LL ret = 0;
    while(a > 0) ret += a % 10, a /= 10;
    return ret;
}

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

    int k;
    cin >> k;
    LL a = 1, b = 1;
    REP(i, k){
        cout << a << endl;
        if(ketawa(a + b) * (a + b*10) < ketawa(a + b*10) * (a + b)) b *= 10;
        a += b;
    }
}


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

int main(){
    int64_t N;
    cin >> N;
    int a_int = int('a');
    string ans="";
    /*
    while(N != 0){
        int d = N % 26;
        N = N / 26;
        char c = (char)(a_int+d);
        ans += c;
    }
    char a = ans.at(0)
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
    */

    int keta=1;
    int64_t old_keta_max = 0;
    int64_t keta_max=26;
    int64_t M=26;
    while(keta_max < N){
        keta++;
        old_keta_max = keta_max;
        M = M*26;
        keta_max += M;
    }
    int64_t f = N - old_keta_max;
    f--;
    for(int i=0; i<keta; i++){
        int d = f%26;
        f = f/26;
        char c = (char)(a_int+d);
        ans += c;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
}


Measured memory_bytes: 3600
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

#define BUG (cout << "Sehen Sie mich!" << endl)

#define N 100
int main()
{
        int n;
        int arr[N];
        cin >> n;
        for (int i = 0; i < n; i++) cin >> arr[i];
        for (int i = 0; i < n; i++) {
                cout << arr[i];
                if (i != n -1)
                        cout << " ";
        }
        cout << endl;
        for (int i = 1; i < n; i++) {
                int key = arr[i];
                int j = i - 1;
                while (j >= 0 && arr[j] > key) {
                        arr[j+1] = arr[j];
                        j--;
                }
                arr[j+1] = key;
                for (int i = 0; i < n; i++) {
                        cout << arr[i];
                        if (i != n -1)
                                cout << " ";
                }
                cout << endl;
        }
        return 0;
}



Measured memory_bytes: 3084
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC068B
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            int n = 0;
            int max = int.MinValue;
            int j, c;

            for(int i=1; i <= N; i++)
            {
                j = i;
                c = 0;
                while(j % 2 == 0)
                {
                    j /= 2;
                    c++;
                }
                if(c > max)
                {
                    max = c;
                    n = i;
                }

            }

            Console.WriteLine(n);

        }
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 200005
#define INF 1000000005LL
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
int main(){
  string S;
  cin  >> S;
  ll size = S.size()-1;
  ll finish = pow(2,size);
  vector <string> data(finish,S);
  rep(i,0,finish){
      int a=i;
      int j=0;
      while(j<size){
          
          int b;

          b=a%2;
          
          a= a/2;
          if(b==1){
            data[i].insert(size-j,"+");
          }
        j ++;

          
    }
  }
  rep(i,0,finish){
      //cout << data[i] << endl;
  }
  ll sum=0;
  rep(i,0,finish){
      ll a=0;
      ll l = data[i].size();
     //cout << l<<endl;
     //cout <<  sum << endl;
      for(int k=0;k<l;k++){
          if(data[i].at(k)=='+'){
              sum +=a;
              a = 0;
          }else{
              a *= 10;
              a += int(data[i].at(k))-48;
             // cout << a<< endl;
              
          }
          if(k==l-1){
              sum += a;
              
              a=0;
          } 
      }
  }
  cout <<  sum << endl;
  
  return 0;
}

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

using namespace std;
typedef long long ll;

int main() {
	int N, X;
	int sum = 0;
	vector<int> v;
	cin >> N >> X;
	v.resize(N);
	for (int i = 0; i < N; i++) {
		int M;
		cin >> M;
		v.at(i) = M;
		sum += M;
	}
	sort(v.begin(), v.end());
	cout << N + (X - sum) / v.at(0) << endl;
	system("pause");
	return 0;
}

Measured memory_bytes: 504
/*
Author : N_o_o_B
Created : July 11 2020 17:31:42 
*/
#include <bits/stdc++.h>
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
*/
#define TRACE
#ifdef TRACE
#define trace(...) { cerr<<"[ "; __trace__(#__VA_ARGS__, __VA_ARGS__);}
#undef endl
template <typename Arg1,typename Arg2>
ostream& operator << (ostream& out, const pair<Arg1,Arg2> &x) {
    return out<<"("<<x.first<<","<<x.second<<")";
}
 
template <typename Arg1>
ostream& operator << (ostream& out, const vector<Arg1> &a) {
    out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
}
 
template <typename Arg1>
ostream& operator << (ostream& out, const set<Arg1> &a) {
    out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
}
 
template <typename Arg1,typename Arg2>
ostream& operator << (ostream& out, const map<Arg1,Arg2> &a) {
    out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
}
 
template <typename Arg1>
void __trace__(const string name, Arg1&& arg1){
    cerr << name << " : " << arg1 << " ] " << endl;
}
 
template <typename Arg1, typename... Args>
void __trace__(const string names, Arg1&& arg1, Args&&... args){
    const string name = names.substr(0,names.find(','));
    cerr<<name<<" : "<<arg1<<" | ";
    __trace__(names.substr(1+(int)name.size()), args...);
}
#else
    #define trace(args...)
#endif
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pair<int,int>> vii;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<pair<ll,ll>> vll;
typedef vector<vl> vvl;
//typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
#define fori(i,n) for(int i=0;i<n;i++)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repd(i,a,b) for(int i=a;i>=b;i--)
#define ford(i,n)  for(int i=n-1;i>=0;i--)
#define trav(x,a) for(auto& x:a)
#define all(x) x.begin(),x.end()
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define fi first
#define se second
clock_t time_p=clock();
void time_taken()
{
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}
//const ll mod=998244353;
const ll mod=1e9+7;
const ll INF=1e18;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cout.precision(12);cout << fixed;

    int n;
    cin >> n;
    int ans = 0;
    for(int i=1;i<=n;i++){
        int x;
        cin >> x;
        ans += (x%2 == 1 and i%2 == 1);
    }
    cout << ans << endl;


    time_taken();
    return 0;
}

Measured memory_bytes: 3796
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
constexpr int INF = 1001001001;
constexpr int MOD = 1000000007;

vector<double> sum(2000);

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

  int n, k;
  cin >> n >> k;

  vector<int> p(n);
  vector<double> d(n);
  for (int i = 0; i < n; i++) {
    cin >> p[i];
  }

  sum[0] = 0;
  for (int i = 1; i < 1100; i++) {
    sum[i] = sum[i - 1] + i;
  }

  for (int i = 0; i < n; i++) {
    d[i] = sum[p[i]] / p[i];
  }

  double ans = 0;
  double t = 0;
  for (int i = k - 1; i < n; i++) {
    if (i == k - 1) {
      for (int j = 0; j < k; j++) {
        t += d[i - j];
      }
    } else {
      t += d[i];
      t -= d[i - k];
    }

    if (ans < t) {
      ans = t;
    }
  }

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

  return 0;
}

Measured memory_bytes: 2688
#include <iostream>
#include <fstream>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <iterator>
#include <ext/pb_ds/assoc_container.hpp>

#define x first
#define y second
#define mp make_pair
#define up_b upper_bound
#define low_b lower_bound
#define sz(x) (int)x.size()
#define bit __builtin_popcount
#define all(x) x.begin(),x.end()
#define show(x) cout<<(#x)<<" is "<<(x)<<endl

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

const ll INF=1e18+123;
const ld EPS=1e-9;
const int inf=1e9+123;
const int MOD=1e8;
const int N=1e5+123;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,k;
    cin>>n>>k;
    ll x=0,y=n/k;
    if(k%2==0){
        if(k/2>n){
            cout<<0;
            return 0;
        }
        int l=k/2;
        int r=n-(n%k)+l;
        if(r>n){
            r-=l;
        }
        x=(r-l)/k+1;
    }

    cout<<x*x*x+y*y*y;
    return 0;
}


Measured memory_bytes: 256
import sys
import math
import itertools
import collections

def solve(S,T):
    counter = 0
    for s,t in zip(S,T):
        if s != t:
            counter += 1
    return counter
def main():
    S = input()
    T = input()
    # solve()
    print(solve(S,T))

if __name__ == "__main__":
    main()


Measured memory_bytes: 9656
#include"bits/stdc++.h"
using namespace std;
inline int read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x;
}
int n,m;
int d[12][12],f[110][110];
int main()
{
	n=read(),m=read();
	for(register int i=1;i<=n;++i)
	for(register int j=1;j<=m;++j)
	d[i][j]=read();
	for(register int i=0;i<=100;++i)
	for(register int j=0;j<=100;++j)
	for(register int x=1;x<=n;++x)
	for(register int y=1;y<=m;++y)
	f[i][j]=max(f[i][j],d[x][y]-i*x-j*y);
	int now;
	for(register int x=1;x<=n;++x)
	for(register int y=1;y<=m;++y)
	{
		now=1000000;
		for(register int i=0;i<=100;++i)
		for(register int j=0;j<=100;++j)
		now=min(now,f[i][j]+i*x+j*y);
		if(now!=d[x][y])
		{
			cout<<"Impossible";
			return 0;
		}
	}
	cout<<"Possible"<<endl;
	cout<<202<<" "<<10401<<endl;
	for(register int i=1;i<101;++i)
	printf("%d %d X\n",i,i+1);
	for(register int i=102;i<202;++i)
	printf("%d %d Y\n",i,i+1);
	for(register int i=0;i<=100;++i)
	for(register int j=0;j<=100;++j)
	{
		printf("%d %d %d\n",i+1,202-j,f[i][j]);
	}
	cout<<1<<" "<<202<<endl;
}

Measured memory_bytes: 384
def p(i):
    print(i)

X = int(input())

if 400 <= X <= 599:
    p(8)
if 600 <= X <= 799:
    p(7)
if 800 <= X <= 999:
    p(6)
if 1000 <= X <= 1199:
    p(5)
if 1200 <= X <= 1399:
    p(4)
if 1400 <= X <= 1599:
    p(3)
if 1600 <= X <= 1799:
    p(2)
if 1800 <= X <= 1999:
    p(1)


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

using namespace std;

struct data_t {
	int c;
	int s;
	int f;
};

int main(void) {
	int N;
	cin >> N;
	vector<data_t> data(N-1);
	for (int i = 0; i < N-1; ++i) {
		cin >> data[i].c >> data[i].s >> data[i].f;
	}

	for (int i = 0; i < N-1; ++i) {
		int time = data[i].c + data[i].s;
		for (int j = i+1; j < N-1; ++j) {
			if (data[j].s > time) {
				time = data[j].s;
			}
			else {
				int next = data[j].s;
				while (next < time) {
					next += data[j].f;
				}
				time = next;
			}
			time += data[j].c;
		}
		cout << time << endl;
	}

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



Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
    int k;
    cin>>k;
    if (k==4)
        cout<<"2"<<endl;
    else if (k==6)
        cout<<"2"<<endl;
    else if (k==8)
        cout<<"5"<<endl;
    else if (k==9)
        cout<<"2"<<endl;
    else if (k==10)
        cout<<"2"<<endl;
    else if (k==12)
        cout<<"5"<<endl;
    else if (k==14)
        cout<<"2"<<endl;
    else if (k==16)
        cout<<"14"<<endl;
    else if (k==18)
        cout<<"5"<<endl;
    else if (k==20)
        cout<<"5"<<endl;
    else if (k==21)
        cout<<"2"<<endl;
    else if (k==22)
        cout<<"2"<<endl;
    else if (k==24)
        cout<<"15"<<endl;
    else if (k==25)
        cout<<"2"<<endl;
    else if (k==26)
        cout<<"2"<<endl;
    else if (k==27)
        cout<<"5"<<endl;
    else if (k==28)
        cout<<"4"<<endl;
    else if (k==30)
        cout<<"4"<<endl;
    else if (k==32)
        cout<<"51"<<endl;
    else
        cout<<"1"<<endl;
}


Measured memory_bytes: 256
o = input()
o_len = len(o)
e = input()
e_len = len(e)
ans = ""
flag1 = "on"
flag2 = "on"
for i in range(1,101):
    if o_len >= i:
        ans = ans + o[i-1]
    else:
        flag1 = "off"
    if e_len >= i:
        ans = ans + e[i-1]
    else:
        flag2 = "off"

    if flag1 == "off" and flag2 == "off":
        break
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);++i)
#define INF 1e9
typedef long long llong;
using namespace std;

int main(){
	int n;
	cin>>n;
	
	vector<int> a(n);
	REP(i,n) scanf("%d",&a[i]);
	
	vector<vector<llong> > dp(n+1,vector<llong>(2));//j=1ならi-1番目の要素を反転.
	dp[0][0]=0;
	dp[0][1]=-INF;
	for(int i=1;i<=n;++i){
		dp[i][0]=max(dp[i-1][0]+a[i-1],dp[i-1][1]-a[i-1]);
		dp[i][1]=max(dp[i-1][0]-a[i-1],dp[i-1][1]+a[i-1]);
	}
	
	cout<<dp[n][0]<<endl;
}//解説参考.アルゴリズムで殴る解法.

Measured memory_bytes: 6144
n=int(input())
a=list(map(int,input().split()))
m=1000
s=0
for i in range(n-1):
  if a[i]<a[i+1]:
    s+=m//a[i]
    m=m%a[i]
  else:
    m+=s*a[i]
    s=0
print(m+a[n-1]*s)

Measured memory_bytes: 9172
#include<bits/stdc++.h>
using namespace std;
//#define int long long
typedef long long ll;
#define sqr(x) ((x)*(x))
#define pb push_back 
const int N=1000002,M=998244353;
int pw(int x,int y){int z=1;for(;y;y>>=1,x=1ll*x*x%M)if(y&1)z=1ll*z*x%M;return z;}
void inc(int &x,int y){x+=y;if(x>=M)x-=M;}void dec(int &x,int y){x-=y;if(x<0)x+=M;}
void Max(int &x,int y){if(y>x)x=y;}void Min(int &x,int y){if(y<x)x=y;}
//struct node{int to,ne;}e[];
//void add(int x,int y){e[++tot]=(node){y,h[x]},h[x]=tot;}
ll ans;
int las,l,l1,i;
vector<int>v[128];
vector<int>::iterator pos;
char s[N],t[N];
signed main(){
	scanf("%s%s",s,t),l=strlen(s),l1=strlen(t);
	for (i=0;i<l;i++) v[s[i]].push_back(i);
	las=-1;
	for (i=0;i<l1;i++){
		if (v[t[i]].empty()) return puts("-1"),0;
		pos=upper_bound(v[t[i]].begin(),v[t[i]].end(),las);
		if (pos==v[t[i]].end()) ans+=l,las=v[t[i]][0];
		else las=*pos;
	}
	printf("%lld",ans+las+1);
}

Measured memory_bytes: 1148
#include <iostream>
#include<sstream>
#include<vector>
#include<iterator>
using namespace std;

int main(void)
{
	int X, Y, Z;
	cin >> X >> Y >> Z;

	int ret = 1;
	X -= Y + 2*Z;

	ret += X/(Y+Z);
	cout << ret << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
using ll = long long;
using P = pair<ll,int>;
using PP = pair<int,pair<int,int>>;
using T = tuple<string,int,int>;
const ll INF = 1LL<<60;

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll = long long;
#define FOR(i, k, n) for(ll i = (k); i < (n); i++)
#define FORe(i, k, n) for(ll i = (k); i <= (n); i++)
#define FORr(i, k, n) for(ll i = (k)-1; i > (n); i--)
#define FORre(i, k, n) for(ll i = (k)-1; i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define ALLr(x) (x).rbegin(), (x).rend()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;

const int INF = 1001001001;
const int mod = 1000000007;

struct mint{
  ll x;
  mint(ll x = 0):x((x % mod + mod) % mod){};
  mint pow(ll y) const {
    mint res(1);
    mint a(x);
    while(y>0){
      if(y&1) res *= a;
      a *= a;
      y >>= 1;
    }
    return res;
  }
  mint inv() const{ return pow(mod-2); }
  mint& operator+= (const mint a) noexcept {
    if((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-= (const mint a) noexcept {
    if((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*= (const mint a) noexcept {
    (x *= a.x) %= mod;
    return *this;
  }
  mint& operator/= (const mint a) noexcept {
    return (*this) *= a.inv();
  }
  mint operator+ (const mint a) const noexcept {
    mint res(*this);
    return res += a;
  }
  mint operator- (const mint a) const noexcept {
    mint res(*this);
    return res -= a;
  }
  mint operator* (const mint a) const noexcept {
    mint res(*this);
    return res *= a;
  }
  mint operator/ (const mint a) const noexcept{
    mint res(*this);
    return res /= a;
  }
};

ostream& operator<<(ostream& stream, const mint& n){
  stream << n.x;
  return stream;
};

struct comb{
  vector<mint> fact, ifact;
  comb(int n): fact(n+1), ifact(n+1){
    fact[0] = 1;
    for(int i = 1; i <= n; i++) fact[i] = fact[i-1] * i;
    ifact[n] = fact[n].inv();
    for(int i = n; i >= 1; i--) ifact[i-1] = ifact[i] * i;
  }
  mint operator()(int n, int k) const noexcept{
    if(k < 0 || n < k) return 0;
    return fact[n] * ifact[k] * ifact[n-k];
  }
};

int main(void){
  ll N, M;
  cin >> N >> M;
  vector<ll> X(N), Y(M);
  REP(i, N) cin >> X[i];
  REP(i, M) cin >> Y[i];
  vector<ll> x(N, 0), y(M, 0);
  REP(i, N) x[i] = i - (N-1-i);
  REP(i, M) y[i] = i - (M-1-i);
  mint p, q;
  REP(i, N) p += x[i]*X[i];
  REP(i, M) q += y[i]*Y[i];
  cout << p*q << endl;
  
  return 0;
}

Measured memory_bytes: 3328
#include <stdio.h>

int
main (
  int   argc,
  char *argv[ ]
  )
{
  int p = 0, q = 0;
  int n;

  scanf ( "%d", &n );
  while ( n-- )
  {
    char a[ 128 ], b[ 128 ];
    int c;

    scanf ( " %s %s", a, b );
    c = strcmp ( a, b );

    if ( c > 0 )
    {
      p += 3;
    }
    else if ( c < 0 )
    {
      q += 3;
    }
    else
    {
      p += 1;
      q += 1;
    }
  }
  printf ( "%d %d\n", p, q );

  return ( 0 );
}

Measured memory_bytes: 0
open Printf open Scanf
open Array

let i c = int_of_char c - int_of_char '0'
let () = scanf " %s" @@ fun s ->
  let p,q,r,s = i s.[0], i s.[1], i s.[2], i s.[3] in
  let pqm =
    not (p*10+q >= 13 || p=0 && q=0) in
  let rsm =
    not (r*10+s >= 13 || r=0 && s=0) in
  print_string @@
    if pqm && rsm then "AMBIGUOUS"
    else if pqm then "MMYY"
    else if rsm then "YYMM"
    else "NA"





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

int main(){
    long long N;
    cin >> N;
    if(N==1){
        puts("1");
        return 0;
    }
    for(int i=sqrt(N);i<N;i++){
        if((i+1)*(i+1)>N){
            cout << i*i << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
def ii():
    return int(input())
def mi():
    return map(int, input().split())
def li():
    return list(mi())

N, K = mi()
A = li()

i = K - 1
ans = 10 ** 18
while i < N:
    l = A[i - K + 1]
    r = A[i]
    if 0 < l:
        ans = min(ans, r)
    elif r < 0:
        ans = min(ans, -l)
    else:
        ans = min(ans, 2 * r - l, -2 * l + r)
    i += 1
print(ans)

Measured memory_bytes: 14660
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long n,m;
  cin>>n>>m;
  if(n>=m){
    cout<<"0";
    return 0;
  }
  vector<long long> x(m),a(m-1);
  for(long long i=0;i<m;i++){
  	cin>>x[i];
  }
  sort(x.begin(),x.end());
 
  for(long long i=m-2;i>=0;i--){
  	a[i]=x[i+1]-x[i];
  }
  
  sort(a.begin(),a.end());
  
  int64_t ans=x[m-1]-x[0];
  
  for(long long i=0;i<n-1;i++){
  	ans-=a[m-2-i];
  }
  cout<<ans;
}

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

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1000000000; //
const ll LINF = (ll) 4000000000000000000; //
const ll MOD = (ll) 1000000007; //
const double PI = 3.1415926535898; //

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,n) for(int i=1;i<=(int)(n);i++)
#define rep3(i,n) for(int i=0;i<=(int)(n);i++)
#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
#define repll(i,n) for(ll i=0;i<(ll)(n);i++)
#define repll2(i,n) for(ll i=1;i<=(ll)(n);i++)
#define REPLL(i,m,n) for(ll i=m;i<(ll)(n);i++)
#define MP make_pair
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define NP(v) next_permutation(v.begin(),v.end())

//------------------------------------------------------

int main() {
    ll n, h;
    cin >> n >> h;

    ll a[n], b[n];

    rep(i, n) cin >> a[i] >> b[i];

    sort(a, a + n);
    sort(b, b + n);
    reverse(b, b + n);
    ll Max_a = a[n - 1];

    vector<ll> b_strong;

    rep(i, n) {
        if (b[i] >= Max_a) b_strong.push_back(b[i]);
        else break;
    }

    int cnt = 0;
    ll sum = 0;

    for (auto b_s : b_strong) {
        sum += b_s;
        cnt++;
        if (sum >= h) break;
    }

    while (sum < h) {
        sum += Max_a;
        cnt++;
    }

    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 2936
n,m,x = list(map(int,input().split()))
ca = []
ans = -1

for i in range(n):
  ca.append(list(map(int,input().split())))

for i in range(2 ** n):
  A_sum = [0] * m
  C_sum = 0
  for j in range(n):
    if (i >> j) & 1:
      C_sum += ca[j][0]
      for k in range(1,m+1):
        A_sum[k-1] += ca[j][k]
  if min(A_sum) >= x:
    if ans == -1:
      ans = C_sum
    elif C_sum < ans:
      ans = C_sum

print(ans)

Measured memory_bytes: 9224
# coding: utf-8
# Your code here!
import math

a,b,x=map(int,input().split())

if x==a**2*b:
    print(0)
    exit()

if x<=(a**2)*b/2:
    t=a-(a-(2*x)/a/b)
    ans=math.atan(b/t)
    ans=math.degrees(ans)
    
    print(ans)
else:
    
    t=2*(b-x/(a**2))
    ans=math.atan(a/t)
    ans=math.degrees(ans)
    
    print(90-ans)


Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <limits>
#include <sstream>
#include <fstream>
#include <climits>
#include <map>
#include <numeric>
#include <functional>
#include <utility>

using namespace std;

#define rep(i, n) for (int i = 0; i < (n); ++i)
typedef long long ll;

int main(void) {
  ll x;
  cin >> x;
  ll cnt = 1;
  ll y = 100;
  while (true) {
    y *= 1.01;
    if (y >= x) {
      break;
    }
    cnt++;
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<map>
#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 ll __int64
#define ll long long
#define P pair<ll,ll>

int n,m,r;
ll x[110000],y[110000];
P t[110000],t2[110000];
vector<P>G[110000];//to,cost
bool used[110000];
ll dist[110000];
priority_queue<P,vector<P>,greater<P> >bfs;
int main(){
cin>>n;
rep(i,n){

cin>>x[i]>>y[i];
x[i]--;
y[i]--;
}
rep(i,n){
t[i]=mp(x[i],i);
t2[i]=mp(y[i],i);
}
sort(t,t+n);
sort(t2,t2+n);

ll ans=0;

for(int i=1;i<n;i++){
	ll a=t[i].second,b=t[i-1].second,c=abs(t[i].first-t[i-1].first);
	G[a].push_back(mp(b,c));
	G[b].push_back(mp(a,c));
	//cout<<a<<" "<<b<<" "<<c<<endl;
	a=t2[i].second,b=t2[i-1].second,c=abs(t2[i].first-t2[i-1].first);
	G[a].push_back(mp(b,c));
	G[b].push_back(mp(a,c));
}
/*
rep(i,n){
	if(G[i].size()>0){
		cout<<i<<":";
		rep(j,G[i].size())cout<<G[i][j].first<<" ";
		cout<<endl;
	}
}*/

bfs.push(mp(0,0));//cost,number

while(!bfs.empty()){
	ll next=bfs.top().second,cost=bfs.top().first;
	bfs.pop();
	if(used[next])continue;
	used[next]=1;
	ans+=cost;
	//cout<<next<<" "<<cost<<endl;

	rep(i,G[next].size()){
		bfs.push(mp(G[next][i].second,G[next][i].first));
	}
}

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

Measured memory_bytes: 22768
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using iii = pair<ii, int>;
#define vt vector
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int MOD = 1e9 + 7;
const int INF = INT_MAX;
const int N = 2e5 + 5;

int n, k, maxim;
int a[N];

int up(int x, int y) {
    return x % y == 0 ? x / y : x / y + 1;
}

int binser(int l, int r) {
    int ret, mid, needed;
    while(l <= r) {
        mid = (l + r) / 2, needed = 0;
        for(int i = 1; i <= n; i++) {
            needed += up(a[i], mid) - 1;
        }
        if(needed <= k) {
            ret = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    return ret;
}

void solve() {
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        maxim = max(maxim, a[i]);
    }
    cout << binser(1, maxim) << '\n';
}

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

Measured memory_bytes: 4420
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#include<map>
#define all(x) (x).begin(),(x).end()
#define print(x) cout << (x) << endl
typedef long long ll;
const ll MOD = 1000000007;
const ll MOD2 = 998244353;
 
using namespace std;
using Graph = vector<vector<int>>;

int main(){
    string S, T, S1, tmp, ans;    cin >> S >> T;
    int s = S.length(), t = T.length();
    ans = "";
    int l = 0;
    for(int i=0; i<s; i++)  ans += 'z';
    for(int i=0; i<s-t+1; i++){
        tmp = S;
        S1 = S;
        for(int j=0; j<s; j++) if(S1[j] == '?') S1[j] = 'a';
        if(S[i] == '?') tmp[i] = T[0];
        if(tmp[i] == T[0]){
            for(int j=0; j<t; j++){
                if(tmp[i+j] != T[j] && tmp[i+j] != '?')   break;
                else if(j == t-1){
                    for(int k=0; k<t; k++)  S1[i+k] = T[k];
                    if(S1 < ans)    ans = S1;
                    l = 1;
                }
            }
        }
    }
    if(l == 0)   print("UNRESTORABLE");
    else    print(ans);
}

Measured memory_bytes: 3608
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl "\n"
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    /*ll x=3000000000;
    cout<<x<<endl;*/
    ll h,sum=0,i=1;
    cin>>h;
    while(h>0){
        h=h/2;
        sum+=i;
        i=i*2;
    }
    cout<<sum<<endl;

    return 0;


}



Measured memory_bytes: 256
s = gets.chomp.split("")
count = 0
while true
    ookisa = s.size
    if s[0,(ookisa/2)] == s[(ookisa/2),ookisa-1] && ookisa % 2 == 0 && count >= 1
        puts ookisa
        break
    else
        s.pop
    end
    count += 1
end


Measured memory_bytes: 14296
import java.util.Scanner

import scala.util.Random


object Main {
  def read() = {
    val sc = new Scanner(System.in)
    val n = sc.nextInt()
    val strs = for (_ <- 0 until n) yield sc.next()
    (n, strs)
  }

  def solve(n:Int, strs: IndexedSeq[String]): Int={
    // AB含み
    // A終わり
    // B始まり
    // A終わりB始まり

    val nContainsAB = strs.map(str => {
      (0 until str.length-1).count(i=> str(i) == 'A' && str(i+1)=='B')
    }).sum
    val nAEnd = strs.count(str => str.last == 'A')
    val nBBegin = strs.count(str => str.head == 'B')
    val nAEndBBegin = strs.count(str => str.last == 'A' && str.head=='B')

    if(nAEndBBegin > 0 && nAEndBBegin == nAEnd && nAEndBBegin == nBBegin){
      nContainsAB + nAEndBBegin - 1
    }else{
      nContainsAB + Math.min(nAEnd, nBBegin)
    }
  }

  def solveNaive(n:Int, strs: IndexedSeq[String]): Int={
    def countAB(str:String) = (0 until str.length-1).count(i=> str(i) == 'A' && str(i+1)=='B')
    strs.permutations.map(pstrs => pstrs.flatten.mkString).map(countAB).max
  }

  def rand(n:Int) = {
    Random.setSeed(123)
    val chars = "ABH"
    val strs =(0 until n).map{ k =>
      val len = Random.nextInt(6) + 1
      (0 until len).map(_=>chars(Random.nextInt(3))).mkString
    }
    println(n)
    strs.foreach(println)
    (n,strs)
  }

  def experiment(n:Int) ={
    for (_ <- 0 until 100){
      val (n, strs) = rand(5)
      val resultNormal = solve(n, strs)
      val resultNaive = solveNaive(n, strs)
      println(s"$resultNormal, $resultNaive, ${resultNormal == resultNaive}")
    }
  }

  def main(args: Array[String]): Unit = {
    val (n, strs) = read()
    //val (n, strs) = rand(5)
    println(solve(n,strs))
    //println(solveNaive(n,strs))
    //experiment(5)
  }
}

Measured memory_bytes: 38728