akhauriyash/Code-Regression huggingface dataset:
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
#include <cassert>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

#define cauto const auto&
#define ALL(v) begin(v),end(v)
#else
#define ALL(v) (v).begin(),(v).end()
#endif

using namespace std;


namespace{
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
	v.assign(a, vector<T>(b, t));
}
template <class T> inline T &chmin(T &x, const T &y){ return x = min(x, y); }
template <class T> inline T &chmax(T &x, const T &y){ return x = max(x, y); }
template <class F, class T>
void convert(const F &f, T &t){
	stringstream ss;
	ss << f;
	ss >> t;
}


#define REP(i,n) for(int i=0;i<int(n);++i)
#define RALL(v) (v).rbegin(),(v).rend()


#define MOD 1000000007LL
#define EPS 1e-8

int gcd(int x, int y){
	while(y){
		int r = x % y;
		x = y;
		y = r;
	}
	return x;
}

void mainmain(){
	int n, x;
	scanf("%d%d", &n, &x);
	int ans = -1;
	for(int i = 0; i < n; ++i){
		int d;
		scanf("%d", &d);
		d = abs(d - x);
		if(i == 0){ ans = d; }
		else{ ans = gcd(ans, d); }
	}
	printf("%d\n", ans);
}



}
int main() try{
//	ios::sync_with_stdio(false); cin.tie(0);
	cout << fixed << setprecision(10);
	cerr << fixed << setprecision(4);
	mainmain();
}
catch(...){}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(var, begin, end) for (int var = (begin); var <= (end); var++)
#define RFOR(var, begin, end) for (int var = (begin); var >= (end); var--)
#define REP(var, length) FOR(var, 0, length - 1)
#define RREP(var, length) RFOR(var, length - 1, 0)
#define EACH(value, var) for (auto value : var)
#define SORT(var) sort(var.begin(), var.end())
#define REVERSE(var) reverse(var.begin(), var.end())
#define RSORT(var) SORT(var); REVERSE(var)
#define OPTIMIZE_STDIO ios::sync_with_stdio(false);cin.tie(0);cout.precision(10);cout << fixed
#define endl '\n'

const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
struct mint {
    ll x;
    mint() : x(0) {}
    mint(ll x) : x((x % MOD + MOD) % MOD) {}
    mint& operator+=(const mint& r) { if ((x += r.x) >= MOD) { x -= MOD; } return *this; }
    mint& operator-=(const mint& r) { if ((x -= r.x) < 0) { x += MOD; } return *this; }
    mint& operator*=(const mint& r) { if ((x *= r.x) > MOD) { x %= MOD; } return *this; }
    mint& operator++() { if ((++x) >= MOD) { x -= MOD; } return *this; }
    mint operator++(int) { mint ret = x; if ((++x) >= MOD) { x-= MOD; } return ret; }
    mint& operator--() { if ((--x) < 0) { x += MOD; } return *this; }
    mint operator--(int) { mint ret = x; if ((--x) < 0) { x += MOD; } return ret; }
    mint operator+(const mint& r) { mint ret; return ret = x + r.x; }
    mint operator-(const mint& r) { mint ret; return ret = x - r.x; }
    mint operator*(const mint& r) { mint ret; return ret = x * r.x; }
    mint operator-() { return mint() - *this; }
    bool operator<(const mint& a) { return x < a.x; }
    bool operator>(const mint& a) { return x > a.x; }
    bool operator<=(const mint& a) { return x <= a.x; }
    bool operator>=(const mint& a) { return x >= a.x; }
    bool operator==(const mint& a) { return x == a.x; }
    bool operator!=(const mint& a) { return x != a.x; }
};
ostream& operator<<(ostream& os, const mint& r) { os << r.x; return os; }
ostream& operator>>(ostream& os, const mint& r) { os >> r.x; return os; }

int gcd2(int a, int b) {
  if (a < b) swap(a, b);
  if (b == 1) return 1;
  int c = a % b;
  if (c == 0) return b;
  else
    return gcd2(b, c);
}

int gcd3(int a, int b, int c) {
  int tmp = gcd2(a, b);
  int res = gcd2(tmp, c);
  return res;
}

void solve(istream& cin, ostream& cout) {
  int K;
  cin >> K;
  int ans = 0;
  FOR(i, 1, K) {
    FOR(j, 1, K) {
      FOR(k, 1, K) {
        ans += gcd3(i, j, k);
      }
    }
  }
  cout << ans << endl;
}

#ifndef TEST
int main() {
  OPTIMIZE_STDIO;
  solve(cin, cout);
  return 0;
}
#endif


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

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
    
    
    int n;
    cin>>n;
    int ans[n*n]={};
    array<int,2> a[n];
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        a[i] = {x,i};
        ans[x-1] = i+1;
    }
    sort(a,a+n);
    int now = 0;
    int cnt = 0;
    for(int i=0;i<n*n;i++){
        if(ans[i]) continue;
        while(now < n && cnt == a[now][1]){
            cnt = 0;
            now++;
        }
        if(now == n) break;
        ans[i] = a[now][1]+1;
        cnt++;
    }
    now = n-1;
    cnt = 0;
    for(int i=n*n-1;i>=0;i--){
        if(ans[i]) continue;
        while(now >=0 && cnt == n - a[now][1] - 1){
            cnt = 0;
            now--;
        }
        if(now == -1) break;
        ans[i] = a[now][1]+1;
        cnt++;
    }
    int c[n+1]={};
    bool pos = true;
    now = 0;
    for(int i=0;i<n*n;i++){
        //cerr << i << " " << ans[i] << endl;
        if(ans[i]==0) pos = false;
        c[ans[i]]++;
        if(a[now][0]-1 == i){
            if(c[a[now][1]+1] != a[now][1]+1){
                pos = false;
            }
            now++;
        }
        if(now == n) break;
    }
    if(pos){
        cout << "Yes\n";
        for(int i=0;i<n*n;i++){
            cout << ans[i] << " ";
        }
        cout << "\n";
    }
    else cout << "No\n";
}


Measured memory_bytes: 2176
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
typedef long long ll;

int main(){
    ll n;
    cin>>n;
    vector<long double> v(n);
    REP(i,n){
        cin>>v[i];
    }
    sort(ALL(v));
    long double mean=(v[0]+v[1])/2;
    FOR(i,2,n){
        mean=(mean+v[i])/2;
    }
    cout<<mean;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<functional>
#include<math.h>
#include<random>
using namespace std;
#define N (1000000000+7)
#define M 998244353
#define INF 1e16
typedef long long ll;
typedef pair<int,int> P;
 
ll A(ll x){
    if(x>=0)return x;
    else return -x;
}
 
ll gcd(ll a, ll b) {
	if (b > a) {
		ll tmp = b;
		b = a;
		a = tmp;
	}
	if (a%b == 0)return b;
	else return gcd(b, a%b);
}



int main(void){
	ll n,k;
	cin>>n>>k;
	vector<ll>s(n+1),a(n);
	for(int i=0;i<n;i++)cin>>a[i];
	s[0]=0;
	for(int i=0;i<n;i++)s[i+1]=s[i]+a[i];
	map<ll,vector<ll>>r;
	r[0].push_back(0);
	for(ll i=1;i<=n;i++){
		r[(s[i]-i)%k].push_back(i);
	}
	ll ans = 0;
	for(auto itr = r.begin();itr!=r.end();++itr){
		ll amari = itr->first;
		for(ll i=0;i<r[amari].size();i++){
			ll index1 = i;
			ll pos = r[amari][i];
			auto itr = lower_bound(r[amari].begin()+i,r[amari].end(),pos+k);
			ll index2 = itr-(r[amari].begin());
			index2--;
			//cout<<amari<<" "<<r[amari][index1]<<" "<<r[amari][index2]<<endl;
			ans+=index2-index1;
		}
	}
	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 28300
#include <iostream>
using namespace std;
int main(void){
    
    int h,n,a;
    cin>>h>>n;
    for(int i=0;i<n;i++){
        cin>>a;
        h-=a;
    }
    if(h<=0)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    
    
    return 0;
}


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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define ff(i,a,b) for(int i = a; i < b; i++)
#define fb(i,a,b) for(int i = a; i > b; i--)
#define MOD 1000000007


ll gcd(ll a, ll b){if(b==0)return a;return gcd(b, a%b);}
ll lcm(ll a, ll b){return a*b/gcd(a, b);}


void solve(){
	int n;
	cin>>n;
	int a[n];
	ff(i,0,n) cin>>a[i];
	ll ans=0;
	ff(i,1,n){
		if(a[i]<a[i-1]){
			ans+=(a[i-1]-a[i]);
			a[i]=a[i-1];
		}
	}
	cout<<ans;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif

	//int t;
    //cin>>t;
	//while(t--)
		solve();
	cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
	return 0;
}

Measured memory_bytes: 4584
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int MaxN = 200003;
#define x0 Fuck_the_GCC_header_x0
#define y0 Fuck_the_GCC_header_y0
#define x1 Fuck_the_GCC_header_x1
#define y1 Fuck_the_GCC_header_y1
#define X first
#define Y second
int x0,x1,y0,y1,n,cnt;
#define M_PI 3.14159265358979323846
const double len=M_PI*20,len2=M_PI*10,len4=M_PI*5;
PII e[MaxN];
int a[MaxN],mn[MaxN];
 
int main() {
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> x0 >> y0 >> x1 >> y1 >> n;
	if (x0>x1) {swap(x0,x1);swap(y0,y1);}
	cout << fixed << setprecision(15);
	cnt=0;
	for (int i=1;i<=n;++i) {
		int x,y;
		cin >> x >> y;
		if (x<min(x0,x1) || x>max(x0,x1) || y<min(y0,y1) || y>max(y0,y1)) continue;
		cnt++;
		e[cnt].first=x,e[cnt].second=y;
	}
	/*if (x1==x0) {
		double ans=(long long)abs(y1-y0)*100LL;
		for (int i=1;i<=cnt;++i) if (e[cnt].X==x1) ans=ans-20LL+len2;
		cout << ans << endl;
		return 0;
	}
	if (y1==y0) {
		double ans=(long long)abs(x1-x0)*100LL;
		for (int i=1;i<=cnt;++i) if (e[cnt].Y==y1) ans=ans-20LL+len2;
		cout << ans << endl;
		return 0;
		}*/
	sort(e+1,e+cnt+1);
	//if (x1<x0) reverse(e+1,e+cnt+1);
	if (y1<y0) for (int i=1;i<=cnt;++i) e[i].Y=2LL*y0-e[i].Y;
	for (int i=1;i<=cnt;++i) a[i]=e[i].Y;
	for (int i=1;i<=cnt;++i) mn[i]=0x7fffffff;
	mn[0]=0x80000000;
	int sum=0;
	for (int i=1;i<=cnt;++i) {
		int x=lower_bound(mn,mn+cnt+1,a[i])-mn;
		mn[x]=a[i];
		sum=max(sum,x);
	}
	double ans=100LL*(abs(x0-x1)+abs(y0-y1));
	ans=ans-20*sum+len4*sum;
 	if (sum==abs(x0-x1)+1||sum==abs(y0-y1)+1)
		ans=ans+len4;
	cout << ans << endl;
	return 0;
}


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

using namespace std;

long long int DP[101][5][5][5];

bool valid(int p, int q, int r, int s){
    if(q == 0 && r == 1 && s == 2) return false;
    if(p == 0 && r == 1 && s == 2) return false;
    if(p == 0 && q == 1 && s == 2) return false;
    if(q == 0 && r == 2 && s == 1) return false;
    if(q == 1 && r == 0 && s == 2) return false;
    return true;
}

int main(){
    int N;
    long long int result = 0;
    cin >> N;
    DP[0][4][4][4] = 1;
    for(int i = 0; i < N; i++){
        for(int p = 0; p < 5; p++){
            for(int q = 0; q < 5; q++){
                for(int r = 0; r < 5; r++){
                    for(int s = 0; s < 4; s++){
                        if(valid(p, q, r, s)){
                            DP[i + 1][q][r][s] += DP[i][p][q][r];
                            DP[i + 1][q][r][s] %= (int)(1e9 + 7);
                        }
                    }
                }
            }
        }
    }
    for(int p = 0; p < 5; p++){
        for(int q = 0; q < 5; q++){
            for(int r = 0; r < 5; r++){
                result += DP[N][p][q][r];
            }
        }
    }
    cout << result % (int)(1e9 + 7) << endl;
}

Measured memory_bytes: 384
import java.util.Scanner;


public class Main {
    public static void main(String[] args){
    	Scanner input = new Scanner(System.in);
    	while(input.hasNextInt()){
	    	int n = input.nextInt();
	    	int count = 1;
	    	if(n < 2){
	    		System.out.println("0");
	    	}else{
	    		for(int i = 3 ; i <= n ; i+=2){
	    			boolean isprime = true;
	    			for(int j = 3 ; j <= Math.sqrt(i) ; j+=2){
	    				if(i % j == 0){
	    					isprime = false;
	    					break;
	    				}
	    			}
	    			if(isprime)count++;
	    		}
		    	System.out.println(count);
	    	}
	    	
    	}
    }
}

Measured memory_bytes: 18964
#define __USE_MINGW_ANSI_STDIO 0
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <set>
#include <numeric>
#include <bitset>
#include <map>
#include <limits.h>
using namespace std;
typedef unsigned long ul;
typedef pair<ul, ul> P;
const int INF = 1e9;
 
long long gcd(long long x, long long y){
			if (x==0)return y;
      if(y==0)return x;
      if(x<y){
				long long temp = x;
			x = y;
				y = temp;
			}
			long long r = x % y;
				while(r!=0){
					x = y;
					y = r;
				r = x % y;
	    		}
			return y;
	    }

   
int main(){
int N,K;
cin >> N >> K;
vector<int> A(N+1);
for(int i=0;i<N;i++){
cin >> A[i];
}
A[N] = INF;
sort(A.begin(),A.end());
int cnt =1;
vector<int> ans;
for(int i=0;i<N;i++){
if(A[i]==A[i+1])cnt++;
else {
	ans.push_back(cnt);
	cnt = 1;
}
}
sort(ans.begin(),ans.end());

if(ans.size()<= K)cout << 0 << endl;
else
{
	int x = ans.size()-K;
	int y = 0;
	for(int i =0;i<x;i++){
		y+=ans[i];
	}
	cout << y << endl;
}


}

Measured memory_bytes: 2168
/*****/

#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <iomanip>	//cout << fixed << setprecision(桁数);
#include <stdexcept>

//#define int long long

using namespace std;
using ll = long long;
using ld = long double;
using vecll = vector<ll>;

#define nextline() (std::cerr << "\n")
#define debug(x) (#x " : " + (x))
#define debug_cout(x) (std::cerr << #x << " : " <<  (x) << "\n")
#define debug_tabcout(n, x) (std::cerr << strMulti("\t",n) << #x << " : " <<  (x) << "\n")
#define debug_headcout(h, x) (std::cerr << h << " : " <<  (x) << "\n")
#define debug_tabheadcout(n, h, x) (std::cerr << strMulti("\t",n) << h << " : " <<  (x) << "\n")

#define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; i++)
#define rep1(i, n) for(int i=1, i##_len=(n); i<=i##_len; i++)
#define rrep(i, n) for(int i=(n)-1; i >= 0; i--)
#define rrep1(i, n) for(int i=(n); i > 0; i--)
#define all(x) (x).begin(), (x).end()
#define pair(a, b) make_pair(a, b);
constexpr int INF = 2000000100;
constexpr ll DIV = 1000000007;	// 10e9+7
template<class T> bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
//template<class T> T divup(T a, T b) { if (a % b == 0) { return a / b; } return a / b + 1; }
#define diup(a, b) (a % b == 0 ? a / b : a / b + 1)
#define exist_in(list, value) (list.end() != std::find(all(list),value))
std::string strMulti(std::string t, int n) { std::string out = ""; for (int i = 0; i < n; i++) { out += t; } return out; }
//template<class T> T math_P(T m, T n) { T ret = 1; for (T i = m; i > m - n; i--) { ret *= i; } return ret; }
//template<class T> T math_C(T m, T n) { T ret = mathP(m, n); for (T i = 2; i <= n; i++) { ret /= i; } return ret; }
//template<class T> bool compare_by_b(pair<T, T> a, pair<T, T> b) { if (a.second != b.second) { return a.second < b.second; } return a.first < b.first; }
//template<class T> T math_gcd(T a, T b) { a = abs(a); b = abs(b); if (a < b) { std::swap(a, b); } T tmp; while (b != 0) { tmp = b; b = a % b; a = tmp; } return a; }
//template<class T> T math_lcm(T a, T b) { a = abs(a); b = abs(b); if (a > b) { std::swap(a, b); } if (a == 1) { return b; } T i = a; while (i % b != 0) { i += a; } return i; }
//template<class T1, class T2> bool exist_in(const T1& list, const T2& v) { return (list.end() != std::find(list.begin(), list.end(), v)); }
//template<class T> bool exist_in(const T& c, const typename T::value_type& v) {	return (c.end() != std::find(c.begin(), c.end(), v));}

/*****/

void Main()
{
	int n, a;
	cin >> n >> a;
	cout << n * n - a;
}

/*****/

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

	std::cout << std::fixed << std::setprecision(10);


	/*
	while (true)
	{
		Main();
		cout << endl;
	}
	//*/


	Main();

	return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main
{
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int A = sc.nextInt();
    String str = sc.next();
    if(str.length() <= A)
    {
      System.out.println(str);
    }
     else
     {
       String s = str.substring(0,A);
       s = s+"...";
       System.out.println(s);
     }
  }
}


Measured memory_bytes: 38588
#include<stdio.h>
int main(){
  int a,b,c;
  scanf("%d %d %d", &a,&b,&c);
  if(a == b)printf("%d\n",c);
  else if(a == c)printf("%d\n",b);
  else if(b == c)printf("%d\n",a);
  return 0;
}


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

using namespace std;

set<int> a;

int main() {
    int n, x;
    cin >> x >> n;
    for(int i = 0; i < n; ++i) {
        int p;
        cin >> p;
        a.insert(p);
    }
    int c = x, b = x;
    bool found = false;
    while(!found) {
        if(a.count(b) == 0) {
            cout << b << '\n';
            return 0;
        }
        --b;
        if(a.count(c) == 0) {
            cout << c << '\n';
            return 0;
        }
        ++c;
    }
    return 0;
}

Measured memory_bytes: 3632
#include <stdio.h>

int main()
{
    int H, W;

    while (scanf("%d%d", &H, &W) == 2 && !(H == 0 && W == 0)) {
        for (int y = 0; y < H; y++) {
            for (int x = 0; x < W; x++)
                if ((x + y) % 2 == 0)
                    putchar('#');
                else
                    putchar('.');
            putchar('\n');
        }
        putchar('\n');
    }
}

Measured memory_bytes: 1000
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if (abs(a-b) <= d && abs(c - b) <= d) cout << "Yes" << endl;
    else if (abs(a - c) <= d) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MAXN=200100;
struct Segment_Tree
{
	int Max[MAXN<<2];
	inline void init() {return memset(Max,0xef,sizeof(Max)),void();}
	inline void modify(register int root,register int l,register int r,register int pos,register int x)
	{
		if(l==r) return Max[root]=x,void();
		register int mid=(l+r)>>1;
		if(pos<=mid) modify(root<<1,l,mid,pos,x);
		else modify(root<<1|1,mid+1,r,pos,x);
		Max[root]=max(Max[root<<1],Max[root<<1|1]);
		return;
	}
	inline int query(register int root,register int l,register int r,register int L,register int R)
	{
		if(l>=L&&r<=R) return Max[root];
		register int mid=(l+r)>>1,ans=INT_MIN;
		if(L<=mid) ans=max(ans,query(root<<1,l,mid,L,R));
		if(R>mid) ans=max(ans,query(root<<1|1,mid+1,r,L,R));
		return ans;
	}
};
Segment_Tree T1,T2;
vector<int> Array1,Array2;
string Ans;
int cnt[MAXN],val[MAXN];
int n;
inline bool check(register int pos,register int Max1,register int Max2,register int num1,register int num2)
{
	register int val1=num1-num2+cnt[pos],val2=num2-num1+cnt[pos];
	if(val1>=0)
	{
		if(val1&1) {if(T1.query(1,1,n,Max2,n)>=val1) return 1;}
		else if(T2.query(1,1,n,Max2,n)>=val1) return 1;
	}
	if(val2>=0)
	{
		if(val2&1) {if(T1.query(1,1,n,Max1,n)>=val2) return 1;}
		else if(T2.query(1,1,n,Max1,n)>=val2) return 1;
	}
	return 0;
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(register int i=1,now=0;i<=n;i++) cin>>val[i],cnt[i]=val[i]>now,now=max(now,val[i]);
	for(register int i=n;i;i--) cnt[i]=cnt[i]+cnt[i+1];
	T1.init();
	for(register int i=n;i;i--)
	{
		register int val1=T1.query(1,1,n,val[i],n),val2=T2.query(1,1,n,val[i],n);
		if(cnt[i]>cnt[i+1]) T1.modify(1,1,n,val[i],val1+2),T2.modify(1,1,n,val[i],val2+2);
		else T1.modify(1,1,n,val[i],val2+1),T2.modify(1,1,n,val[i],val1+1);
	}
	register int Max1=1,Max2=1,num1=0,num2=0;
	for(register int i=1;i<=n;i++)
	{
		T1.modify(1,1,n,val[i],-(1<<30)),T2.modify(1,1,n,val[i],0);
		if(check(i+1,max(Max1,val[i]),Max2,num1+(Max1<=val[i]),num2))
			Array1.push_back(val[i]),num1=num1+(Max1<=val[i]),Max1=max(Max1,val[i]),Ans+='0';
		else
			Array2.push_back(val[i]),num2=num2+(Max2<=val[i]),Max2=max(Max2,val[i]),Ans+='1';
	}
	if(num1^num2) cout<<-1;
	else cout<<Ans;
	cout<<endl;
	return 0;
}

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

using namespace std;

const int M = 300000;

int n, q, in, data[M+2], val;

main(){
  cin >> n >> q;
  fill(data, data+M+1, 0);
  val = 0;
  for(int i=0;i<n;i++){
    cin >> in;
    data[in+1] = in;
    val = max(val, in);
  }
  for(int i=1;i<=M;i++) if(!data[i]) data[i] = data[i-1];
  for(int i=0;i<q;i++){
    cin >> in;
    int ans = 0;
    int p = val;
    while(p){
      int tmp = p % in;
      ans = max(ans, tmp);
      p = data[p - tmp];
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 2332
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define endl "\n"
#define sz(x) ((ll)(x).size())
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define prt(x) cout << (x)
#define prtl(x) cout << (x) << endl
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define rrep(i,a,b) for(ll i=a; i>b; i--)
#define mp(a, b) make_pair(a, b)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;
using vi = vector<int>;
using vll = vector<long long int>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vc = vector<char>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<long long int>>;
using vvc = vector<vector<char>>;
using ll = long long int;
using P = pair<long long int, long long int>;
using Map = map<long long int, long long int>;
ll INF = 1LL<<60;
ll M = 1000000007;

int main(){
    vll a(5);
    rep(i, 0, 5){
        cin >> a[i];
    }
    rep(i, 0, 5){
        if(i+1 != a[i]){
            prt(i+1);
        }
    }
}

Measured memory_bytes: 3568
#include<stdio.h>

int main()
{	
	int n, i, j;
	while((scanf("%d", &n)!=EOF) && n){
		int key[100] = {};
		char s[100] = {};
		char ans[100] = {};
		
		for(i = 0; i < n; i++)		scanf("%d", &key[i]);
		for(i = n; i < 100; i++)	key[i] = key[i%n];
		
		scanf("%s", s);
		
		for(i = 0; i < 100; i++)	if(s[i]!='\0')	ans[i] = s[i];
		
		for(i = 0; i < 100; i++)
		{
			if(s[i] == '\0')	break;
			for(j = 0; j < key[i]; j++)
			{
				if(ans[i] == 'a')	ans[i] = 'Z';
				else if(ans[i] == 'A')	ans[i] = 'z';
				else	ans[i]--;
			}
		}
		printf("%s\n", ans);
	}
	return 0;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
#define rep(a,n) for (ll a = 0; a < (n); ++a)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
typedef vector<vector<ll> > Graph;
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; }
const ll INF = 1e9;

ll D;
vector<ll>c(26);

int main(){
    cin >> D;
    rep(i,26)cin>>c[i];
    vector<vector<ll> >s(D,vector<ll>(26));
    rep(i,D)rep(j,26)cin>>s[i][j];
    vector<ll>last(D,0);
    ll manzoku = 0;
    vector<ll>ans;
    rep(i,D){
        ll t = 0;
        ll M = 0;
        /*ここにtを選ぶアルゴリズムをかく*/
        rep(j,26){
            ll now = 0;
            now += s[i][j];
            rep(k,26){
                if(k==j)continue;
                now -= c[k]*(i+1-last[k]);
            }
            if(chmax(M,now)){
                t = j;
            }
        }
        manzoku += s[i][t];
        last[t]=i+1;
        rep(j,26){
            manzoku -= c[j]*(i+1-last[j]);
        }
        ans.push_back(t);
    }
    rep(i,ans.size()){
        if(i%3==0){
            cout << 1 << endl;
        }
        else cout << ans[i]+1 << endl;
    }
    return 0;
}


Measured memory_bytes: 3736
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
typedef pair<int,int> PP;
typedef long long ll;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE cout << -1 << endl;return 0
#define Endl endl


signed main(void){
    int W,H,x,y;
    cin >> W >> H >> x >> y;
    int Ans;
    int middle=0;
    if(2*x==W && 2*y==H){
        middle=1;
    }
    Ans=H*W;
    printf("%.10f ",(double)(Ans)/2);
    cout << middle << endl;
    return 0;
}



Measured memory_bytes: 256
#include <cstdio>

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	if (m > n * 10000) {
		puts("-1 -1 -1");
	    return 0;
	}
	if (m % 1000 != 0) {
		puts("-1 -1 -1");
	    return 0;
	}
	for (register int i = 0; i <= n; i++) {
		for (register int j = 0; j <= n; j++) {
			if (n - i - j < 0) break;
			if (m - 10000 * i - 5000 * j < 0) break;
			if (i * 10000 + j * 5000 + (n - i - j) * 1000 == m) {
				printf("%d %d %d", i, j, n - i - j);
				return 0;
			}
		}
	}
	puts("-1 -1 -1");
	return 0;
}

Measured memory_bytes: 128
n = int(input())
ll = []
for i in range(n):
  x, l = map(int, input().split())
  ll.append([x-l, x+l])
ll.sort(key=lambda x:x[1])

ans = 0
tmp = -10**9

for l in ll:
  if l[0] >= tmp:
    ans += 1
    tmp = l[1]

print(ans)

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


#define	ll_int	long long int
#define	BUCKET_SIZE	500000	// 26^5 = 11,881,376	26^4 = 456,976


typedef struct data_t{
	char key[21];
	ll_int x;
	struct data_t *next;
} DATA_T;

DATA_T **S;


// ハッシュテーブルの初期化
void Init()
{
	int i;

	for(i = 0; i < BUCKET_SIZE; i++)
		S[i] = NULL;
}


ll_int Hash(char *key)
{
	ll_int sum = 0;
	int i;

	for(i = 0; i < 4 && i < strlen(key); i++)
		sum += (key[i] - 97) * pow(26, 3 - i);

	return sum;
}


DATA_T *Get(char *key)
{
	ll_int h;
	DATA_T *p;

	h = Hash(key);

	for(p = S[h]; p != NULL; p = p->next){
		if(!strcmp(key, p->key))
			return p;
	}

	return NULL;
}


void Insert(char *key, ll_int x)
{
	ll_int h;
	DATA_T *p;
	DATA_T *i, *j;

	if(( p = Get(key) )){
		p->x = x;
		return;
	}


	/* 挿入処理(比較して該当する場所へ突っ込む) */
	if( ( p = (DATA_T *)malloc(sizeof(DATA_T)) ) == NULL){
		printf("malloc error\n");
		exit(1);
	}

	strcpy(p->key, key);
	p->x= x;
	h = Hash(key);

	if(S[h] == NULL){
	// 該当する添え字の箱が空の場合
		S[h] = p;
		p->next = NULL;
	}else if(strcmp(key, S[h]->key) < 0){
	// 該当する添え字の先頭に挿入
		p->next = S[h];
		S[h] = p;
	}else{
	// 先頭以降への挿入
		for(i = S[h], j = i->next; j != NULL; i = j, j = j->next){
			if(strcmp(i->key, key) < 0 && strcmp(key, j->key) < 0){
				i->next = p;
				p->next = j;
				break;
			}
		}

		if(j == NULL){
		// 最後尾に突っ込む
			i->next = p;
			p->next = j;
		}
	}
}


void Delete(char *key)
{
	DATA_T *p, *q;
	ll_int h;

	if(Get(key) == NULL)
		return;


	h = Hash(key);
	p = S[h];

	// 先頭にある場合の処理
	if(!strcmp(key, p->key)){
		S[h] = p->next;
		free(p);
		return;
	}

	// 先頭以降の処理
	for(q = p->next;; p = q, q = q->next){
		if(!strcmp(key, q->key)){
			p->next = q->next;
			free(q);
			break;
		}
	}
}


// lとrを基準にハッシュテーブルの添え字を計算、条件にあった数値を出力
void Dump(char *l, char *r)
{
	DATA_T *p;
	ll_int start_h, end_h;
	ll_int i;

	start_h = Hash(l);
	end_h = Hash(r);

	for(i = start_h; i <= end_h; i++){
		for(p = S[i]; p != NULL; p = p->next){
			if(strcmp(r, p->key) < 0)
				return;

			if(strcmp(l, p->key) <= 0 && strcmp(p->key, r) <= 0)
				printf("%s %lld\n", p->key, p->x);
		}
	}
}


int main()
{
	int q;
	int query;
	char in_str[50];
	char key[21];
	char x[21];
	DATA_T *p;
	int i;

	S = (DATA_T **)malloc(sizeof(DATA_T *) * BUCKET_SIZE);

	fgets(in_str, sizeof(in_str), stdin);
	sscanf(in_str, "%d", &q);

	for(i = 0; i < q; i++){
		fgets(in_str, sizeof(in_str), stdin);
		in_str[strlen(in_str) - 1] = '\0';
		sscanf(in_str, "%d %s %s", &query, key, x);

		if(query == 0){
		// insert
			Insert(key, atoi(x));
		}else if(query == 1){
		// get
			if( (p = Get(key)) )
				printf("%lld\n", p->x);
			else
				printf("0\n");
		}else if(query == 2){
		// delete
			Delete(key);
		}else if(query == 3){
		// dump
			Dump(key, x);
		}
	}

	return 0;
}

/*
	Set_Range_Searchの改良
	ハッシュの算出を工夫
*/


Measured memory_bytes: 14788
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) int(a.size())
#define clr(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
const int inf=1e9;
const ll Inf=1e18;
const int N=2e3+10;
const int mod=0;
int gi() {
    int x=0,o=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
template<typename T> bool chkmax(T &a,T b) { return a<b?a=b,1:0; };
template<typename T> bool chkmin(T &a,T b) { return a>b?a=b,1:0; };
int add(int a,int b) { return a+b>=mod?a+b-mod:a+b; }
int sub(int a,int b) { return a-b<0?a-b+mod:a-b; }
void inc(int &a,int b) { a=(a+b>=mod?a+b-mod:a+b); }
void dec(int &a,int b) { a=(a-b<0?a-b+mod:a-b); }
int n,m,fa[N],faw[N],dep[N],ans=0;
vector<int> E[N],du;
vector<pii> path;
void dfs(int u,int ff,int d) {
    fa[u]=ff,dep[u]=d;
    for(int v:E[u]) if(v!=ff) dfs(v,u,d+1);
}
void modify(int u,int v) {
    if(dep[u]<dep[v]) swap(u,v);
    while(dep[u]>dep[v]) ++faw[u],u=fa[u];
    while(u!=v) ++faw[u],++faw[v],u=fa[u],v=fa[v];
}
vector<pii> solve(vector<pii> path,vector<int> du) {
    if(path.empty()) return path;
    int u=1,v=0;
    while(du[u]!=1) ++u;
    for(int x:E[u]) if(du[x]) { v=x;break; }
    --du[u],--du[v];
    vector<pii> now,nxt;
    vector<int> bel;
    for(pii x:path) {
        if(x.se==u) swap(x.fi,x.se);
        if(x.fi==u) now.pb(x),bel.pb(0);
        else nxt.pb(x),bel.pb(1);
    }
    if(now.empty()) return solve(path,du);
    vector<int> ref(sz(now));
    fill(all(ref),-1);
    for(int i=0;i+1<sz(now);i+=2) {
        pii &x=now[i],y=now[i+1];
        if(x.se!=y.se) nxt.pb(mp(x.se,y.se)),ref[i]=ref[i+1]=sz(nxt)-1;
        else swap(x.fi,x.se);
    }
    if(sz(now)&1) {
        pii x=now.back();
        if(x.se!=v) nxt.pb(mp(v,x.se)),ref[sz(now)-1]=sz(nxt)-1;
    }
    nxt=solve(nxt,du);
    path.clear();int p1=0,p2=0;
    for(int x:bel) {
        if(!x) {
            if(~ref[p1]&&nxt[ref[p1]].fi!=now[p1].fi&&nxt[ref[p1]].se!=now[p1].se) swap(now[p1].fi,now[p1].se);
            path.pb(now[p1++]);
        }
        else path.pb(nxt[p2++]);
    }
    return path;
}
int main() {
    n=gi(),m=gi();du.resize(n+1);
    for(int i=1,u,v;i<n;i++) u=gi(),v=gi(),E[u].pb(v),E[v].pb(u),++du[u],++du[v];
    dfs(1,0,0);
    for(int i=1,u,v;i<=m;i++) u=gi(),v=gi(),modify(u,v),path.pb(mp(u,v));
    for(int i=2;i<=n;i++) ans+=min(2,faw[i]);
    path=solve(path,du);
    printf("%d\n",ans);
    for(pii x:path) printf("%d %d\n",x.fi,x.se);
    return 0;
}


Measured memory_bytes: 67840
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#include <time.h>
#include <limits>
#include <type_traits>

using namespace std;
#define MOD 1000000007
#define Nmax 200010
#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define RFOR(i,a,b) for(long long i = (b-1);i>=a;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<P> Graph;

int main() {
    ll N,Y;
    cin >> N >> Y;
    FOR(j,0,Y/5000+1){
        FOR(k,0,Y/1000+1){
            if(N-j-k < 0) break;
            if(10000*(N-j-k)+5000*j+1000*k == Y){
                cout << N-j-k << " " << j << " " << k << endl;
                return 0;
            }
            //if(10000*(N-j-k)+5000*j+1000*k > Y) break;
        }
    }
    
    cout << -1 << " " << -1 << " " << -1 << endl;
 }


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

using namespace std;

int main(){
    int n,a,b;
    cin>>n>>a>>b;
    int ans=0;
    
    for(int i=1;i<=n;i++){
        string s=to_string(i);
        int hoge=0;
        for(auto a:s) hoge+=a-'0';
        if(hoge>=a && hoge<=b) ans+=i;
    }
    
    cout<<ans<<endl;
    
    return 0;
}

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

// ----------- define --------------
#define int long long
#define vi vector<int>
#define ii pair<int,int>
#define fi first
#define sc second
#define stoi stoll
#define popcnt __builtin_popcount
#define getBit(x, k) ((x >> k) & 1)
#define all(x) (x).begin(),(x).end()
// ---------------------------------

void Main() {
  int n; cin >> n;
  vector<ii> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i].fi;
    a[i].sc = i;
  }
  sort(all(a));
  vector<int> res(n);
  for (int i = 0; i < n; i++) {
    if (i < n / 2) res[a[i].sc] = a[n / 2].fi;
    else res[a[i].sc] = a[n / 2 - 1].fi;
  }
  for (auto &i : res) cout << i << '\n';
}

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  cerr << "- ---- -- ----- <3\n";
#endif
  cin.tie(0)->sync_with_stdio(0);
  int T = 1;
  // cin >> T;
  while (T--) Main();
}


Measured memory_bytes: 7888
#include<iostream>
using namespace std;
 
int main()
{
  int W,H,x,y,r;
 
  cin >> W >> H >> x >> y >> r;
 
  if(x+r > W || x-r < 0 || y+r > H || y-r < 0){
 
    cout << "No" << "\n";
  }
    else{ cout << "Yes" << "\n";}
}

Measured memory_bytes: 1124
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

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

const ll mod=1e9+7;

int main(){
    ll n,k;
    cin >> n >> k;
    vector<ll> l(n);
    rep(i,n){
        cin >> l[i];
    }
    sort(l.rbegin(),l.rend());
    ll ans=0;
    rep(i,k){
        ans+=l[i];
    }
    cout << ans << endl;
    return 0;
} 


Measured memory_bytes: 3636
#include<iostream>
#include<vector>
using namespace std;
int v[5]={0,1,0,-1,0};
int main()
{
	int w,h;
	while(cin>>w>>h,w)
	{
		string c[20];
		for(int i=0;i<h;i++)cin>>c[i];
		int d[20][20][20][20]={};
		for(int ix=0;ix<h;ix++)for(int iy=0;iy<w;iy++)
			for(int jx=0;jx<h;jx++)for(int jy=0;jy<w;jy++)
				if(ix!=jx||iy!=jy)d[ix][iy][jx][jy]=1<<28;
		vector<pair<int,int> > a;
		int sx,sy;
		for(int i=0;i<h;i++)
		{
			for(int j=0;j<w;j++)
			{
				if(c[i][j]=='x')continue;
				else if(c[i][j]=='*')a.push_back(make_pair(i,j));
				else if(c[i][j]=='o')sx=i,sy=j;
				int x=i,y=j;
				for(int r=0;r<4;r++)
				{
					int tx=x+v[r];
					int ty=y+v[r+1];
					if(tx<0||ty<0||tx>=h||ty>=w||c[tx][ty]=='x')continue;
					d[x][y][tx][ty]=1;
				}
			}
		}
		for(int kx=0;kx<h;kx++)
		{
			for(int ky=0;ky<w;ky++)
			{
				for(int ix=0;ix<h;ix++)
				{
					for(int iy=0;iy<w;iy++)
					{
						for(int jx=0;jx<h;jx++)
						{
							for(int jy=0;jy<w;jy++)
							{
		d[ix][iy][jx][jy]=min(d[ix][iy][jx][jy],d[ix][iy][kx][ky]+d[kx][ky][jx][jy]);
							}
						}
					}
				}
			}
		}
		int n=a.size();
		int dis[99][99]={};
		bool endflag=false;
		for(int i=0;i<n;i++)
		{
			dis[0][i+1]=dis[i+1][0]=d[sx][sy][a[i].first][a[i].second];
			if(dis[0][i+1]==1<<28)endflag=true;
		}
		if(endflag)
		{
			cout<<-1<<endl;
			continue;
		}
		for(int i=0;i<n;i++)
		{
			int ix=a[i].first,iy=a[i].second;
			for(int j=0;j<n;j++)
			{
				if(i==j)continue;
				int jx=a[j].first,jy=a[j].second;
				dis[i+1][j+1]=d[ix][iy][jx][jy];
			}
		}
		n++;
		int dp[99][2050];
		for(int j=0;j<n;j++)for(int i=0;i<1<<n;i++)dp[j][i]=1<<28;
		dp[0][0]=0;
		for(int i=0;i<1<<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				if(!((i>>j)&1))
				{
					for(int k=0;k<n;k++)
					{
						if((i>>k)&1||i==0)
					dp[j][i|1<<j]=min(dp[j][i|1<<j],dp[k][i]+dis[k][j]);
					}
				}
			}
		}
		int mind=1<<28;
		for(int i=0;i<n;i++)mind=min(mind,dp[i][(1<<n)-1]);
		cout<<(mind==1<<28?-1:mind)<<endl;
	}
}

Measured memory_bytes: 3872
n = int(input())
a = list([int(input()) for i in range(n)])
a.sort()
import copy
b = copy.deepcopy(a)
a.reverse()

ans = 0

if(n%2==0):
    cnt = 0
    while(cnt!=n):
        if(cnt==0):
            initn = a[cnt]
            pre = a[cnt]
            cnt += 1

        elif(cnt == n-1):
            if(cnt%2 == 0):
                ans += abs(initn - a[cnt//2])
                pre = a[cnt//2]
            else:
                ans += abs(initn - b[cnt//2])
                pre = b[cnt//2]
            cnt += 1
            
        else:
            if(cnt%2 == 0):
                ans += abs(pre - a[cnt//2])
                pre = a[cnt//2]
            else:
                ans += abs(pre - b[cnt//2])
                pre = b[cnt//2]
            cnt += 1
    print(ans)
else:
    cnt = 0
    while(cnt!=n):
        if(cnt==0):
            initn = a[cnt]
            pre = a[cnt]
            cnt += 1

        elif(cnt == n-1):
            if(cnt%2 == 0):
                ans += abs(initn - a[cnt//2])
                pre = a[cnt//2]
            else:
                ans += abs(initn - b[cnt//2])
                pre = b[cnt//2]
            cnt += 1
            
        else:
            if(cnt%2 == 0):
                ans += abs(pre - a[cnt//2])
                pre = a[cnt//2]
            else:
                ans += abs(pre - b[cnt//2])
                pre = b[cnt//2]
            cnt += 1
    ans1 = ans
    ans = 0
    cnt = 0
    while(cnt!=n):
        if(cnt==0):
            initn = b[cnt]
            pre = b[cnt]
            cnt += 1

        elif(cnt == n-1):
            if(cnt%2 == 0):
                ans += abs(initn - b[cnt//2])
                pre = b[cnt//2]
            else:
                ans += abs(initn - a[cnt//2])
                pre = a[cnt//2]
            cnt += 1
            
        else:
            if(cnt%2 == 0):
                ans += abs(pre - b[cnt//2])
                pre = b[cnt//2]
            else:
                ans += abs(pre - a[cnt//2])
                pre = a[cnt//2]
            cnt += 1
    
    print(max(ans1,ans))

Measured memory_bytes: 8380
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;

int N;
string S;

int main() {
    cin >> N >> S;
    int ans = 1;
    for (int i = 1; i < N; i++) {
        if (S[i] == S[i - 1]) continue;
        ans++;
    }
    cout << ans << endl;
}


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

int bubbleSort(int A[], int N){
 int sw = 0;
 bool flag = 1;
 for(int i = 0; flag; i++){
   flag = 0;
   for(int j = N -1; j >= i + 1; j--){
        if(A[j] < A[j - 1]){
          swap(A[j],A[j - 1]);
          flag = 1;
          sw++;
}
}
}
return sw;
}

int main(){
int A[100], N, sw;
cin >> N;
for(int i = 0; i < N; i++) cin >> A[i];

   sw = bubbleSort(A, N);

  for(int i = 0; i < N; i++){
   if(i)cout << " ";
   cout << A[i];
   }
     cout <<endl;
     cout << sw << endl;

return 0;
}


Measured memory_bytes: 3092
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

//
#define int long long
#define pb(x) push_back(x)
#define m0(x) memset((x), 0, sizeof(x))
#define mm(x) memset((x), -1, sizeof(x))

//container
#define ALL(x) (x).begin(), (x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
#define PERM(c) \
  sort(ALL(c)); \
  for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))

// debug
#define GET_VAR_NAME(variable) #variable
#define test(x) cout << GET_VAR_NAME(x) << " = " << x << endl;

// bit_macro
#define bit(n) (1LL << (n))
#define bitset(a, b) (a) |= (1 << (b))
#define bitunset(a, b) (a) |= ~(1 << (b))
#define bitcheck(a, b) ((((a) >> (b)) & 1) == 1)
#define bitcount(a) __builtin_popcountll((a))

//typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

//constant
const int INF = (int)1e18;
const int MOD = (int)1e9 + 7;
const double EPS = (double)1e-10;
const int dx[] = {-1, 0, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, -1, 1, 0, 0, 1, -1, 1, -1};

//
template <typename T>
void chmax(T &a, T b) { a = max(a, b); }
template <typename T>
void chmin(T &a, T b) { a = min(a, b); }
//
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

//
struct Accelerate_Cin {
  Accelerate_Cin() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
  };
};

int N, K;
int dp[101010];
int h[101010];

int rec(int now) {
  if (now == N) return 0;
  if (dp[now] >= 0) return dp[now];
  int res = rec(now + 1) + abs(h[now] - h[now + 1]);
  for (int i = 2; i <= K; i++) {
    if (now + i > N) break;
    res = min(res, rec(now + i) + abs(h[now] - h[now + i]));
  }
  return dp[now] = res;
}

signed main() {
  cin >> N >> K;
  for (int i = 1; i <= N; i++) cin >> h[i];
  mm(dp);

  cout << rec(1) << endl;
  return 0;
}


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

count = [[0, 0] for i in range(N)]
for i in range(N):
    for j in range(i):
        if A[j] < A[i]:
            count[i][0] += 1
    for j in range(i+1, N):
        if A[j] < A[i]:
            count[i][1] += 1
ans = 0
mod = 10**9 + 7

for i in range(N):
    ans += (1+K-1)*(K-1) // 2 * count[i][0]
    ans += (1+K)*K // 2 * count[i][1]
    ans %= mod

print(ans % mod)


Measured memory_bytes: 9320
def divisible(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    divisors.sort(reverse=True)
    return divisors

n, k = map(int, input().split())
arr = list(map(int, input().split()))
divs = divisible(sum(arr))

for div in divs:
    test_arr = [x % div for x in arr]
    test_arr.sort()
    sum_test_arr = sum(test_arr)
    change = sum(test_arr[:-sum_test_arr // div])
    if change <= k:
        print(div)
        exit()


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

int main() {

  int N; //ソースコードの数
  int M; //整数の数
  int C; //整数

  cin >> N >> M >> C;

  int a[N][M];

  int i;
  int j;
  int b[M];
  int e;

  for(e=0;e<M;e++){
    cin >> b[e];
  }

  for(i=0;i<N;i++){
    for(j=0;j<M;j++){
      cin >> a[i][j];
    }
  }

  int count = 0;
  int sum = C;
  int k;
  int m;
  for(k=0;k<N;k++){
    for(m=0;m<M;m++){
      sum += a[k][m]*b[m];
    }
    if(sum > 0){
      count += 1;
      sum = C;
    }
    else{
      sum = C;
    }
  }

  cout << count << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long m=1e9+7;
int main(){
    int n;
    cin>>n;
    long long a[n]; long long hash[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        hash[i]=0;
    }
    hash[0]=a[0];
    for(int i=1;i<n;i++){
        hash[i]=(a[i]+hash[i-1])%m;
    }
    long long ans=0;
    for(int i=1;i<n;i++){
        ans=(ans+(a[i]*hash[i-1])%m)%m;
    }
    cout<<ans;

}

Measured memory_bytes: 6740
import sys
if __name__ == "__main__":
    N = int(input())
    X = list(map(int, (input().split(' '))))
    buf = sorted(X)
    for i in range(N):
#        buf = list(X)
#        buf.pop(i)
#        buf = sorted(buf)
#        print(X[i])
#        print(buf[int(N/2)])
        if X[i] < buf[int(N/2)]:
            print(buf[int(N/2)])
        else:
            print(buf[int(N/2)-1])

Measured memory_bytes: 26772
a, b, m = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))

mi = min(a) + min(b)
for k in range(m):
    x, y,  c = list(map(int, input().split()))
    score = a[x-1] + b[y-1] - c
    if score < mi:
        mi = score
print(mi)

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

#define REP(i ,n) for(int i=0 ;i < n; i++)
#define REPB(i ,n) for(int i=n; i >= 0; i--)
#define FOR(i ,m ,n) for(int i=m; i < n; i++)
#define FORB(i, m, n) for(int i=m; i>= n; i--)
#define ll long long
#define pb push_back
#define popb pop_back
#define debug(i) cout << i << endl
using namespace std;
int main(){
  int n, m , c;
  int count = 0;
  vector<int> a, b;
  cin >> n >> m >> c;

  REP(c, m){
      int tmp;
      cin >> tmp;
      b.pb(tmp);
    }
  REP(i, n){
    REP(c,m){
        int tp;
        cin >> tp;
        a.pb(tp);
      }
      int sum = 0;
      REP(j,m){
         sum += (a[j] * b[j]);
        }
      sum += c;
      if(sum > 0) count++;

    a.clear();
    }
    cout << count << endl;
    return 0;
}

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

using namespace std;
typedef long long LL;

int a[110];
int dp[2][100010];
int MOD=1000000007;

int main() {
    int n, k;
    cin>>n>>k;
    for (int i=0;i<n;i++) cin>>a[i];
    memset(dp,0,sizeof(dp));
    dp[0][0]=dp[1][0]=1;
    for (int i=0;i<n;i++) {
        int sum=1;
        for (int j=1;j<=k;j++) {
            sum+=dp[i%2][j];
            if (j>a[i]) sum-=dp[i%2][j-a[i]-1];
            sum=(sum%MOD+MOD)%MOD;
            dp[(i+1)%2][j]=sum;
        }
    }
    cout<<dp[n%2][k]<<endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	++n;
	map<int,int>a;
	for(int x=1;(x+2)*x<n;++x){
		for(int y=1;x*x+y*y+1+x*y+y<n;++y){
			for(int z=1;1;++z){
				int s=x*x+y*y+z*z+x*y+y*z+z*x;
				if(s>n)break;
				++a[s];
			}
		}
	}
	for(int i=1;i<n;++i){
		cout<<a[i]<<endl;
	}
	return 0;
}

Measured memory_bytes: 4068
/*
██████╗  ███████╗  
██╔══██╗ ██╔════╝ 
██████╔╝ ███████╗ 
██╔══██╗ ╚════██║  
██║  ██║ ███████║      
╚═╝  ╚═╝ ╚══════╝                                                                                                             
*/

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long int
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define haha(j,a,n) for(int j=a;j<n;j++)
#define Max(x,y,z) max(x,max(y,z))
#define Min(x,y,z) min(x,min(y,z))
#define endl "\n"
#define bc(v) v.begin(),v.end()
#define vl vector<ll>
#define vi vector<int>
#define mod 1000000007
#define NUM 100005
#define F first
#define S second
#define bhar(a) rep(i,a.size()) cin>>a[i];
#define show(a) rep(i,a.size()) cout<<a[i]<<" ";
#define sott(a) sort(bc(a))
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define mapp map<ll,ll>
#define dkac cout<<fixed<<setprecision(15);
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define yeah(n) while(n--)
ll gcd(int a, int b){if(b==0) return a; else return gcd(b,a%b);}
ll bitfun(ll x){
  return (x&(-x));
}
void solve(){
  ll n,m; cin>>n>>m;
  vl h(n); bhar(h);
  ll ans=0;
  map<ll,vl> ma;
  rep(i,m){
    ll x,y; cin>>x>>y;
    //x--; y--;
    ma[x].pb(y);
    ma[y].pb(x);
  }
  for(auto x:ma){
    if(x.S.size()==0) ans++;
    bool f=0;
    //cout<<x.F<<" ";
    for(auto j:x.S){
      //cout<<j<<" ";
      if(h[j-1]>=h[x.F-1]){
        f=1; break;
      }
    }
    if(!f){ ans++;
      //cout<<x.F<<endl;
    }
    //cout<<endl;
  }
  haha(i,1,n+1)
  if(ma[i].size()==0) ans++;
  cout<<ans;
}
int main(){
    ios
    int t=1; 
    //cin>>t;
    yeah(t){
      solve();
    }
}

Measured memory_bytes: 15320