akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"

using namespace std;

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

int main() {
	int H, W, K;//泳げる距離
	cin >> H >> W >> K;
	int Sx, Sy, Gx, Gy;
	cin >> Sx >> Sy >> Gx >> Gy;
	--Sx; --Sy; --Gx; --Gy;

	vector<string> S(H);
	for (int n = 0; n < H; ++n) {
		cin >> S[n];
	}

	vector<vector<int>> D(H, vector<int>(W, 1e9));//回数
	vector<vector<bool>> Data(H, vector<bool>(W, false));//回数
	queue<pair<int, int>> q;
	q.push(make_pair(Sx, Sy));
	D[Sx][Sy] = 0;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		if ((x == Gx) && (y == Gy)) {
			cout << D[Gx][Gy] << endl;
			return 0;
		}

		//範囲内かつ0を4セット
		for (int l = 0; l < 4; ++l) {
			int x1 = x;
			int y1 = y;
			for (int m = 1; m <= K; ++m) {
				x1 += dx[l];
				y1 += dy[l];
				if ((0 > x1) || (H <= x1) || (0 > y1) || (W <= y1)) {
					break;
				}
				if ('@' == S[x1][y1]) {
					break;
				}
				if (Data[x1][y1] && (D[x1][y1] != (D[x][y] + 1))) {
					break;
				}
				if (!Data[x1][y1]) {
					D[x1][y1] = D[x][y] + 1;
					q.push(make_pair(x1, y1));
					Data[x1][y1] = true;
				}
			}
		}
	}

	cout << -1 << endl;
	return 0;
}


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

using namespace std;
     
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pf push_front   
#define ppb pop_back
#define mp make_pair
#define bpp __builtin_popcount
#define al 0x3F3F3F3F
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
#define in insert
#define ppf pop_front
#define endl '\n'
#define resize(v) v.resize(unique(all(v)) - v.begin());
//#define int long long

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;                                                                          																																							
typedef pair <int, int> pii;

const int mod = (int)1e9 + 7;                                   
const int MAX_N = (int)2e5 + 123;
const int N = 1e6 + 123;                     
const int INF = al;           
const ll INFL = 3e18 + 1;
const double pi = acos(-1.0);
const double eps = 1e-9;
const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};

ll a, b, c;	

inline void boost () {
    ios_base :: sync_with_stdio(NULL);
    cin.tie(NULL), cout.tie(NULL);
}                                                                     
                                                                    
inline void Solve () {
   boost ();
   cin >> a >> b >> c;
   if (a % 2 == 0) cout << 0, exit(0);
   if (c % 2 == 0) cout << 0, exit(0);
   if (b % 2 == 0) cout << 0, exit(0);   
   cout << min(a * b, min(b * c, a * c));
}  

int main () {
//	freopen("sparse.in", "r", stdin);	
//	freopen("sparse.out", "w", stdout);
   int tt = 1;                																																																
//	cin >> tt;
	while (tt --) {
   	Solve ();
   }
   return 0;
}

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

int main(){
    int a,b,c,d,e,f,g;
    cin >> a;
    b = a / 100;
    c = b / 5;
    d = c * 1000;
    e = a - (c*500);
    f = e / 5;
    g = f * 5;
    cout << d + g << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
using ll=long long;
using vec=vector<ll>;
using vect=vector<double>;
using Graph = vector<vector<ll>>;
#define loop(i,n) for(ll i=0;i<n;i++)
#define Loop(i, m, n) for(ll i = m;i < n;i++)
#define pool(i,n) for(ll i=n;i>=0;i--)
#define Pool(i, m, n) for(ll i=n;i>=m;i--)
#define setbit bitset<8>
#define flagcount __builtin_popcount
#define flag(x) (1<<x)
#define flagadd(bit,x) bit|=flag(x)
#define flagpop(bit,x) bit&=~flag(x) 
#define flagon(bit,i) bit&flag(i)
#define flagoff(bit,i) !(bit & (1<<i))
#define all(v) v.begin(),v.end()
#define low2way(v,x) lower_bound(all(v),x)
#define high2way(v,x) upper_bound(all(v),x)
#define count2way(v,x) high2way(v,x)-low2way(v,x)
#define lower(v,x) low2way(v,x)-v.begin() //1番左が0、もし見つから無いならｎを出力
#define higher(v,x) high2way(v,x)-v.begin()-1 //1番左が0、もし見つからないならn-1を出力（注意）
#define putout(a) cout<<a<<endl
#define putout2(a,b) putout(a);putout(b)
#define putout3(a,b,c) putout(a);putout(b);putout(c)
#define putout4(a,b,c,d) putout(a);putout(b);putout(c);putout(d)
#define putout5(a,b,c,d,e) putout(a);putout(b);putout(c);putout(d);putout(e)
#define Gput(a,b) G[a].push_back(b)
#define cin1(a) cin>>a
#define cin2(a,b) cin>>a>>b
#define cin3(a,b,c) cin>>a>>b>>c
#define cin4(a,b,c,d) cin>>a>>b>>c>>d
#define cin5(a,b,c,d,e) cin>>a>>b>>c>>d>>e
#define sum(v) accumulate(all(v), 0ll)
#define gcd(x,y) __gcd(x,y)
#define erase(s) s.erase(s.end()-1) //文字列sの末尾削除
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}
ll ctoi(char c){
	if(c>='0'&&c<='9'){
		return c-'0';
	}
	return 0;
}
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
ll lcm(ll x,ll y){
  ll z=gcd(x,y);
  return x*y/z;
}
ll primejudge(ll n){
  if(n<2)return 0;
  else if(n==2)return 1;
  else if(n%2==0)return 0;
  double sqrtn=sqrt(n);
  Loop(i,3,sqrtn+1){
     if(n%i==0){
        return 0;
     }
     i++;
  }
  return 1;
}
string RLE(string s){
  ll n=s.size();
  char now='.';
  ll count=1;
  string press;
  loop(i,n){
    if(s[i]!=now){
      if(i){
        press+=now;
        press+=to_string(count);
      }
      now=s[i];
      count=1;
      continue;
    }
    else count++;
  }
  press+=now;
  press+=to_string(count);
  return press;
}
int main() {
  cout << fixed << setprecision(30);
  ll n,a,b;
  cin>>n>>a>>b;
  if(a==0)putout(0);
  else{
    if(b==0)putout(n);
    else{
      ll set=n/(a+b);
      if(n%(a+b)==0)putout(set*a);
      else{
        putout(set*a+min(a,n-set*(a+b)));
      }
    }
  }
  
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
typedef long long lint;
using namespace std;

int main()
{
	const lint mod=1e9+7;
	lint N,M;
	lint ans=1;
	
	cin >> N >> M;
	
	if(abs(N-M)>1)ans=0;
	else
	{
		for(int i=2;i<=N;i++)
		{
			ans*=i;
			ans%=mod;
		}
		for(int i=2;i<=M;i++)
		{
			ans*=i;
			ans%=mod;
		}
		if(N==M)
		{
			ans*=2;
			ans%=mod;
		}
	}
	
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
int main()
{
  using namespace std;
  int a,b;
  while(cin>>a>>b){
  	if(b==1){
  		cout<<0<<endl;
  		continue;
	  }
    int num=1;
    while((a*num-(num++)+1)<b);
    cout<<num-1<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define forin(in) for(int i=0; i<(int)in.size(); i++) cin>>in[i]
#define forout(out) for(int i=0; i<(int)out.size(); i++) cout<<out[i]<<endl
#define rep(i, n) for(int i=0; i<(n); i++)

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

    for(int A = -150; A <= 150; A++){
        for(int B = -150; B <= 150; B++){
            if(pow(A, 5) - pow(B, 5) == X){
                cout<< A << " " << B << endl;
                return 0;
            }
        }
    }
}

Measured memory_bytes: 4088
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

const int MAX_N = 2e3 + 5;

string grid [MAX_N];
int lbrk [MAX_N]; // last break between positions (i) and (i + 1)

bool same (char c, char d) {
  return c == d;
}

int main () {
  ios::sync_with_stdio(false);

  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> grid[i];
  }

  for (int i = 0; i < m; i++) {
    lbrk[i] = -1;
  }
  
  int ans = m;
  for (int i = 1; i < n; i++) {
    // add the i-th row and make it clear
    for (int j = 0; j < m - 1; j++) {
      if (same(grid[i - 1][j], grid[i][j]) != same(grid[i - 1][j + 1], grid[i][j + 1])) {
        lbrk[j] = i - 1;
      }
    }

    vector<pair<int, int>> breaks; // <lbrk[i], i>
    for (int j = 0; j < m - 1; j++) {
      if (lbrk[j] != -1) {
        breaks.push_back(make_pair(lbrk[j], j));
      }
    }
    
    sort(breaks.begin(), breaks.end());
    reverse(breaks.begin(), breaks.end());
      
    vector<pair<int, vector<int>>> blocks;
    for (auto pr : breaks) {
      if (blocks.empty() || pr.first != blocks.back().first) {
        blocks.push_back(make_pair(pr.first, vector<int> (0)));
      }
      blocks.back().second.push_back(pr.second);
    }

    set<int> walls;
    walls.insert(-1);
    walls.insert(m - 1);
    for (pair<int, vector<int>> block : blocks) {
      for (int w : block.second) {
        int lw = *prev(walls.upper_bound(w));
        int rw = *walls.upper_bound(w);
          
        ans = max(ans, (rw - lw) * (i - block.first));
      }

      for (int w : block.second) {
        walls.insert(w);
      }
    }

    for (auto it = next(walls.begin()); it != walls.end(); it++) {
      int r = *it;
      int l = *prev(it);
      ans = max(ans, (r - l) * (i + 1));
    }
  }

  cout << ans << endl;
}


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

int main(void) {
  int N, K;
  cin >> N >> K;
  vector<int> h(N);
  for (int i = 0; i < N; i++) {
    cin >> h[i];
  }
  sort(h.begin(), h.end());
  int ret = 2e9;
  for (int i = K - 1; i < N; i++) {
    ret = min(ret, h[i] - h[i - K + 1]);
  }
  cout << ret << endl;

  return 0;
}

Measured memory_bytes: 640
import math

n, k = map(int, input().split())
a = list(map(int, input().split()))

hq = []

def is_ok(checking):
    cost = 0
    for i in range(n):
        cost += math.ceil(a[i]/checking)-1
    if cost <= k:
        return True
    else:
        return False

def meguru_bisect(ng, ok):
    while (abs(ok-ng)>1):
        mid = (ok+ng)//2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

ok = meguru_bisect(0, int(1e+10)) 
print(int(ok))
# 初期値の範囲は取りえる値-1～+1とする←範囲内はok,ngどちらもあり得るため

Measured memory_bytes: 104268
import java.io.*;
class Main
{
public static void main(String args[]) throws IOException
{

		BufferedReader br=
			new BufferedReader( new InputStreamReader(System.in));

			String str=br.readLine();
		
int S =Integer.parseInt(str);
int h=S/3600;
int m=S%3600/60;
int s=S%60;


System.out.println(h+":"+m+":"+s);}}

Measured memory_bytes: 24220
#include <bits/stdc++.h>
using namespace std;
int aa[200];
int main()
{
	int a,cnt=0;
	cin>>a;
	for(int i=0;i<a*2;i++){
		cin>>aa[i];
	}
	sort(aa,aa+a*2);
	for(int j=0;j<a*2;j=j+2){
		cnt=cnt+aa[j];
	}
	cout<<cnt;
}

Measured memory_bytes: 256
#include<stdio.h>
#include <string.h>
int myatoi(char);
int S[105];
int top=0;
void push(int);
int pop(void);
int cal(char);
int main(){
  int tmp;
  int i;
  char op[10];
  while(scanf("%s",op)!=EOF){
    if(op[0]=='+' || op[0]=='-' || op[0]=='*'){
      push(cal(op[0]));
    }
    else{
      i=0;
      tmp=0;
      while(op[i]!='\0'){
	tmp*=10;
	tmp+=myatoi(op[i]);
	i++;
      }
      push(tmp);
    }
  }
  printf("%d\n",S[0]);
  return 0;
}
int myatoi(char c) {
  return c-48;
}
void push(int x){
  S[top++]=x;
}
int pop(void){
  return S[--top];
}
int cal(char op){
  int ans;
  if(op=='+'){
    ans=pop()+pop();
  }
  else if(op=='-'){
    ans=pop()-pop();
    ans*=(-1);
  }
  else if(op=='*'){
    ans=pop()*pop();
  }
  return ans;
}




Measured memory_bytes: 2108
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
string s[200010];
map<string,int> mp;
int mx;
int main(){
	int n,i;
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>s[i];
		mp[s[i]]++,mx=max(mx,mp[s[i]]);
	}
	sort(s+1,s+1+n);
	for(i=1;i<=n;i++)
		if(mp[s[i]]==mx){
			cout<<s[i]<<endl;
			mp[s[i]]=0;//此句很神奇
		}
	return 0;
}

Measured memory_bytes: 26880
#include<bits/stdc++.h>
#define console
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define siz(x) ((int)(x).size())
#define full(v) v.begin(), v.end()
#ifndef console
ifstream fin("data.in");
ofstream fout("data.out");
#else
#define fin cin
#define fout cout
#endif
#define MAX(x, y) ((a) > (b) ? (a) : (b))
#define usain_bolt() (ios_base::sync_with_stdio(false), \
                      fin.tie(NULL), fout.tie(NULL))
const long long oo = 0x3f3f3f3f;
const double PI = acos(-1);

const int di[4] = {1, 0, -1, 0};
const int dj[4] = {0, 1, 0, -1};

typedef long long ll;
typedef unsigned int ui;

int main()
{
    usain_bolt();
    string s, t;
    fin >> s >> t;
    if (s + t[t.size() - 1] == t)
            fout << "Yes";
    else fout << "No";
#ifndef console
    fin.close(), fout.close();
#else
#undef fin cin
#undef fout cout
#endif // console
    return 0;
}


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



int main() {
    long int ans = 0;
    long int a, b, n, x;
    cin >> a >> b >> n;

    if(n < b)
    {
        x = n;
    }
    else if(n == b)
    {
        x = b - 1;
    }
    else
    {
        x = (n / b) * b - 1;
    }
    ans = ((a * x) / b) - a * (x / b);

    cout << ans << endl;
}



Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define pb push_back
#define ff first
#define ss second
#define ll long long
#define ld long double
typedef pair<ll,ll> pll;
typedef vector <ll> vi;
#define out(x) return cout<<x,0;
#define precision(x,d) cout<<fixed<<setprecision(d)<<x
#define lc(n) 2*n+1
#define rc(n) 2*n+2
#define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL));

int main(){
    FAST;
    ll n, ans=0, k=0, m, j = 0, t = 0, x = 0, y = 0, c = 0, i, z = 0;
    cin >> n >> x >> y ;
    if ( ( y - x ) % 2 == 0 ) out( ( y - x ) / 2 );
    if ( x - 1 < n - y ){
        ans = x ;
        y -= x;
        ans += ( y - 1 ) / 2;
        out(ans);
    }
    ans = n - y + 1;
    x += ans;
    ans += ( n - x ) / 2;
    out ( ans );
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
using namespace std;

int main(){
  vector<pair<int,int> > v;
  int a, b;
  while(cin >> a >> b && (a || b)){
    v.push_back(make_pair(a, b));
  }
  for(int i=0;i<(int)v.size();i++){
    for(int j=0;j<v[i].first;j++){
      for(int k=0;k<v[i].second;k++){
        cout << "#";
      }
      cout << endl;
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 1188
#include<stdio.h>
long long a[100005];
int main()
{
	long N,i;
	long long x,a[100005],sum,t;
	while(~scanf("%d%d",&N,&x))
	{
		sum=0;
		for(i=0;i<N;i++)
		scanf("%lld",&a[i]);
		for(i=N-1;i>0;i--)
		if(a[i]+a[i-1]>x)
		{
			t=a[i]+a[i-1]-x;
			sum+=t;
			a[i-1]-=t;
			if(a[i-1]<0) a[i-1]=0;
		}
		printf("%lld\n",sum);
	}
	return 0;
}

Measured memory_bytes: 896
#include <stdlib.h>
#include<iostream>
#include<bits/stdc++.h>
#include<cmath>
#define ll long long
const ll INF=0x3f3f3f3f;
#define mod 1000000007
using namespace std;
//priority_queue
const ll Maxn=1e5;
ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}
ll kc(ll a,ll b)
{
    ll c=1;
    while(b)
    {
        if(b&1)c=(c*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return c;
}
bool cmp(double x,double y)
{
    return x>y;
}
ll vim[2003],ly[2003];
ll C(int a,int b)
{
    if(b==0||a==b)return 1;
    if(a<b)return 0;
    return vim[a]*ly[b]%mod*ly[a-b]%mod;
}

void dd()
{
    vim[0]=1;
    for(int i=1; i<=2000; i++)
        vim[i]=vim[i-1]*i%mod,ly[i]=kc(vim[i],mod-2);
}
//n个相同的球放入m个不同的盒子中，不能有空的放法为C(n-1,m-1);
//思路先放把蓝色的球放到i个盒子里面，然后把i个盒子放到n-m+1个间隔中就可以了。
int main()
{
    ios::sync_with_stdio(false);
    dd();
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        cout<<C(m-1,i-1)%mod*C(n-m+1,i)%mod<<endl;
    }

}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int max = 20000;
		long[][] cnt = new long[max + 1][2];

		for(int i = 2; i <= max; i++) {
			int t = i;
			while(t % 2 == 0) {
				t /= 2;
				cnt[i][0]++;
			}
			t = i;
			while(t % 5 == 0) {
				t /= 5;
				cnt[i][1]++;
			}
			cnt[i][0] += cnt[i - 1][0];
			cnt[i][1] += cnt[i - 1][1];
		}
		//System.out.println(Math.min(cnt[12][0], cnt[12][1]));
		while(sc.hasNext()) {
			int n = sc.nextInt();
			if(n == 0) break;
			System.out.println(cnt[n][1]);
		}
		sc.close();
	}
}


Measured memory_bytes: 26700
import java.io.*;
import java.util.*;
class Main{
	static final long MOD = 1_000_000_007; // 10^9+7
	static final int MAX = 2_147_483_646; // intMax 
	static final int INF = 1_000_000_000; // 10^9  
	public static void main(String[] args) throws Exception{
		hayami saori = new hayami();
		int a = saori.saori_hayami();
		int b = saori.saori_hayami();
		int c = saori.saori_hayami();
		if((a < c && c < b) || (c < a && b < c)){
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
		saori.close();
	}
}

class hayami implements Closeable {
	private final InputStream in = System.in;
	private final byte[] hayami = new byte[1024];
	private int Hayami = 0;
	private int saori = 0;
	private boolean HayamiSaori() {
		if (Hayami < saori) {
			return true;
		}else{
			Hayami = 0;
			try {
				saori = in.read(hayami);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (saori <= 0) {
				return false;
			}
		}
		return true;
	}
	private int SaoriHayami() { 
		if (HayamiSaori()) {
            return hayami[Hayami++];
         }else{
             return -1;
         }
	}
	private static boolean hayami_saori(int hayami) { 
		return 33 <= hayami && hayami <= 126;
	}
	public boolean hayamisaori() { 
		while(HayamiSaori() && !hayami_saori(hayami[Hayami])) Hayami++; return HayamiSaori();
	}
	public String nextHayami() {
		if (!hayamisaori()) throw new NoSuchElementException();
		StringBuilder hayamin = new StringBuilder();
		int saori = SaoriHayami();
		while(hayami_saori(saori)) {
			hayamin.appendCodePoint(saori);
			saori = SaoriHayami();
		}
		return hayamin.toString();
	}
	public long saorihayami() {//nextLong
		if (!hayamisaori()) throw new NoSuchElementException();
		long hayami = 0;
		boolean misao = false;
		int saori = SaoriHayami();
		if (saori == '-') {
			misao = true;
			saori = SaoriHayami();
		}
		if (saori < '0' || '9' < saori) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= saori && saori <= '9') {
				hayami *= 10;
				hayami += saori - '0';
			}else if(saori == -1 || !hayami_saori(saori)){
				return misao ? -hayami : hayami;
			}else{
				throw new NumberFormatException();
			}
			saori = SaoriHayami();
		}
	}
	public int saori_hayami() {//nextInt
		long hayami = saorihayami();
		if (hayami < Integer.MIN_VALUE || hayami > Integer.MAX_VALUE) throw new NumberFormatException();
		return (int) hayami;
	}
	public double Hayamin() { //nextDouble
		return Double.parseDouble(nextHayami());
	}
	public void close() {
		try {
			in.close();
		} catch (IOException e) {
		}
    }
    
}


Measured memory_bytes: 22996
#include <bits/stdc++.h>
using namespace std;
int n, k, d[105], a[105][105];
int ans[105], answer;
int i, j, l;
int main() {
	scanf("%d%d", &n, &k);
	for (i = 1; i <= k; i++) {
		scanf("%d", &d[i]);
		for (j = 1; j <= d[i]; j++) {
			scanf("%d", &a[i][j]);
			for (l = 1; l <= n; l++) {
				if (a[i][j] == l) ans[l]++;
			}
		}
	}
	for (i = 1; i <= n; i++) {
		if (ans[i] == 0) answer++;
	}
	printf("%d", answer);
	return 0;
}

Measured memory_bytes: 3836
/*alurquiza*/
//APIO_2010: Commando
#include <bits/stdc++.h>
#define h first //height
#define w second //width

using namespace std;

vector<long long> M,N;

bool bad(int r1,int r2,int r3){
    long long m1 = M[r1],n1 = N[r1];
    long long m2 = M[r2],n2 = N[r2];
    long long m3 = M[r3],n3 = N[r3];

    ///true si la x en la que se intersectan la recta 1 y 3 es menor que la x donde se intersectan r1 y r2
    return (n3 - n1) * (m1 - m2) <= (n2 - n1) * (m1 - m3);
}

void add(long long m,long long n){
    M.push_back(m);
    N.push_back(n);

    while(M.size() >= 3 && bad(M.size() - 3,M.size() - 2,M.size() - 1)){
        M.erase(M.end() - 2);
        N.erase(N.end() - 2);
    }
}
//puntero a la mejor soulcion hasta ahora
int p = 0;

long long query(long long x){
    p = min(p,(int)M.size() - 1);

    while(p + 1 < M.size() && M[p] * x + N[p] > M[p + 1] * x + N[p + 1])
        p++;

    return M[p] * x + N[p];
}

long long pot(long long b){
    return 1LL * b * b;
}

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

//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);

    int N;
    long long C;
    cin >> N >> C;

    vector<long long> A(N + 1);
    for(int i = 1;i <= N;i++){
        cin >> A[i];
    }

    long long sol = 0;
    add(-2LL * A[1],sol + pot(A[1]));
    for(int i = 2;i <= N;i++){
        sol = query(A[i]) + pot(A[i]) + C;
        add(-2LL * A[i],sol + pot(A[i]));
    }

    cout << sol << '\n';

    return 0;
}













Measured memory_bytes: 5220
#include<stdio.h>

int main(void){
    int N, i, aa = 0, b, answer = 0;
    long int K;
    scanf("%d %ld", &N, &K);
    int A[N], check[N], jyun[N], recheck[N];
    for(i = 0; i < N; i++){
        scanf("%d", &A[i]);
        check[i] = 0;
        jyun[i] = 0;
        recheck[i] = 0;
    }
    //ループの開始地点を探す
    b = 1;
    int c = 0, start = 0;
    while(aa == 0){
        b -= 1;
        if(check[b] > 0){
            aa += 1;
            start = b; 
            jyun[c] += b + 1;     //2回目の町-1
            break;
        }
        else{
        jyun[c] += b + 1;
        c += 1;
        check[b] += 1;
        b = A[b];
        }
    }

    int roop = 0, next = start + 1, yobun;
    if(K <= c){
        answer = jyun[K];
    }
    else{
        long int x;
        aa = 0;
        while(aa == 0){
            next -= 1;
            if(recheck[next] > 0){
                aa += 1;
                break;
            }
            else{
                roop += 1;
                recheck[next] += 1;
                next = A[next];
            }
        }
        yobun = c - roop;
        K -= yobun;
        K = K % roop;
        x = K + yobun;
        answer = jyun[x];
    }
    printf("%d\n", answer);
    return 0;

}

Measured memory_bytes: 4824
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s;
  	cin>>s;
  	int n;
  	cin>>n;
  	set<string>st;
  	for(int i=0;i<s.length();i++)
    {
		string t="";
      	t.push_back(s[i]);
      	st.insert(t);
      	for(int j=i+1;j<s.length();j++)
        {
          t+=s[j];
          st.insert(t);
          if(t.length()==n)break;
        }
    }
  	set<string>::iterator it =st.begin();
  	int p=0;
  	while((p++)<n)it++;
  	it--;
  	cout<<*it<<endl;
  //for(auto x:st)cout<<x<<endl;
  	return 0;
}

Measured memory_bytes: 4792
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <iostream>
#include <string>
#include<algorithm>
#include <vector>
#include <cassert>
#include<cmath>
using namespace std;

int main() {
	int K, X;
	cin >> K >> X;
	if (K * 500 >= X) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 384
#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    bool ans = 0;
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x;
        if (x & 1) ans = ans ^ 1;
    }
    if (!ans) cout << "YES";
    else cout << "NO";
    return 0;
}

Measured memory_bytes: 384
import collections
N = int(input())
A = list(map(int, input().split()))

c = collections.Counter(A)
cs = sorted(c.items(), key=lambda x:x[0], reverse=True)

area = []
for i in range(len(cs)):
    if(cs[i][1] > 1):
        if(cs[i][1]//2 == 1):
            area.append(cs[i][0])
            if(len(area) == 2):
                print(area[0]*area[1])
                break
        else:
            area.append(cs[i][0])
            if(len(area) > 1):
                print(max(cs[i][0]*cs[i][0], area[0]*area[1]))
                break
            else:
                print(cs[i][0]*cs[i][0])
                break
else:
    print(0)

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

int main(){
  int n, q, b, e, t;
  cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }
  cin >> q;
  for(int i = 0; i < q; i++){
    cin >> b >> e >> t;
    auto it = a.begin();
    swap_ranges(it + b, it + e, it + t);
  }
  for(int i = 0; i < n; i++){
    if(i > 0) cout << " ";
    cout << a[i];
  }
  cout << endl;
  return 0;

}



Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
int main() {
  double a, b, n, m;
  cin >> a >> b >> n >> m;
  cout << fixed << setprecision(11);
  cout << a*b/2 << " ";
  if (n == a/2 && m == b/2) {
    cout << 1 << endl;
  }
  else {
    cout << 0 << endl;
  }
}

Measured memory_bytes: 3744
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n, on_point =0;
	cin>>n;
	int a[n];
	for(int i =0 ; i < n ; i++)
	{
		cin>>a[i];
		if(a[i]==i+1)
			on_point++;
	} 
	if(on_point==n-2||on_point==n)
		cout<<"YES"<<endl;
	else
		cout<<"NO"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define leng(n) (int)(log10(n)+1)
#define INF 9000000000000000000
using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}  //  最大公約数gcd
int lcm(int a,int b){return a/gcd(a,b)*b;}  //  最小公倍数lcm

signed main() {
  int a, b, k;
  cin >> a >> b >> k;
  if( (b-a+1) / 2 < k ) {
    rep(i,a,b+1) cout << i << endl;
  }
  else {
  rep(i,0,k) cout << a+i << endl;
  repr(i,k,0) cout << b-(i-1) << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using VS = vector<string>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "-----------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause")
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T>inline istream& operator>>(istream& is, deque<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

int n, m, q, ans = 0;
VI a, b, c, d;
void dfs(VI x) {
    if (x.size() == n) {
        int sum = 0;
        FOR(i, 0, q)if (x[b[i]] - x[a[i]] == c[i])sum += d[i];
        chmax(ans, sum);
    }
    else {
        eFOR(i, (x.empty() ? 1 : x.back()), m) {
            VI y = x;
            y.push_back(i);
            dfs(y);
        }
    }
}

int main() {
    init();

    cin >> n >> m >> q;
    a.resize(q), b.resize(q), c.resize(q), d.resize(q);
    FOR(i, 0, q)cin >> a[i] >> b[i] >> c[i] >> d[i];
    each(i, a)--i; each(i, b)--i;
    dfs(VI());
    cout << ans << "\n";
}


Measured memory_bytes: 3616
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
#include<string.h>
#include<set>
#define inf 0x3f3f3f3f
using namespace std;
int main()
{
    int ans=0;
    int ans1=0;
    for(int i=0;i<3;i++)
    {
        int n;
        cin>>n;
        if(n==5)ans++;
        if(n==7)ans1++;
    }
    if(ans==2&&ans1==1)puts("YES");
    else puts("NO");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const double PI = 3.141592653589793;

int main() {

    // 1. input.
    double r;
    cin >> r;
    
    // 2. calculate an area and a circumference.
    double a = PI * r * r;
    double c = 2 * PI * r;
    
    // 3. output answer.
    cout << fixed;
    cout << setprecision(10) << a << " " << c << endl;
    return 0;
    
}


Measured memory_bytes: 3268
#include <cstdio>
#include <algorithm>

int kindof(int n, int *arr){
    int x=0;
    for (int i = 0; i < n; i++){
        //printf("%5d", arr[i]);
        if (arr[i]) x++;
    }
    return x;
}

int main(){
    int n, k;
    scanf("%d%d", &n,&k);

    int a[n];
    int len[n];
    for (int i = 0; i < n; i++) len[i] = 0;
    for (int i = 0; i < n; i++){
        scanf("%d", &a[i]);
        len[a[i]-1]++;
    }

    std::sort(len, &len[n]);

    int x = 0;//kind of
    int index = 0;

    x = kindof(n, len);
    //printf("\n%d\n", x);

    if (x<=k){
        puts("0");
        return 0;
    }

    int len2[x];
    for (int i = 0; i < x; i++) len2[i] = len[n-i-1];

    x = kindof(x, len2);

    int dif = x-k;
    int an = 0;

    for (int i = 0; i < dif; i++) an += len2[x-i-1];

    printf("%d\n", an);
}

Measured memory_bytes: 2560
n = int(input())
*x, = map(int, input().split())
*y, = map(int, input().split())

p1, p2, p3, pm = 0, 0, 0, 0
for _x, _y in zip(x, y):
    p1 += abs(_x-_y)
    p2 += abs(_x-_y)**2
    p3 += abs(_x-_y)**3
    pm = max(pm, abs(_x-_y))

print("{:.6f}".format(p1))
print("{:.6f}".format(p2**0.5))
print("{:.6f}".format(p3**(1/3)))
print("{:.6f}".format(pm))


Measured memory_bytes: 5648
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n; cin >> n;
  cout << fixed << setprecision(15) << (0.5 * n + 0.5 * (n & 1)) / n << '\n';
}

Measured memory_bytes: 896
from collections import deque

n = int(input())
a = list(map(int, input().split()))
b = deque([a[0]])
rev = 1

for i in range(1, n):
    if rev % 2 == 0:
        b.append(a[i])
    else:
        b.appendleft(a[i])
    rev += 1

if rev % 2 == 1:
    b.reverse()

print(*b)

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

#define mod 1000000007
#define mp make_pair
#define rep(i,n) for(int i=0;i<n;i++)
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a,b,c,d;
    cin >> a >> b >> c >> d;
    while(1){
        c-=b;
        if(c<=0){
            cout << "Yes";
            break;
        }
        a-=d;
        if(a<=0){
            cout << "No";
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 3600
#include <algorithm>
#include <array>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;

constexpr double EPS = 1e-7;
constexpr int INF = 1e9;
constexpr ll LINF = 1e18;

#define PI (acos(-1))

constexpr int MOD = 1e9 + 7;

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

int main(int argc, char const *argv[]) {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);

	int H, N;
	cin >> H >> N;

	vector<int> A(N);
	vector<int> B(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i] >> B[i];
	}

	vector<vector<ll>> dp(N + 1, vector<ll>(H + 1, LINF));
	dp[0][0] = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= H; j++) {
			chmin(dp[i + 1][j], dp[i][j]);
			chmin(dp[i + 1][min(j + A[i], H)], dp[i + 1][j] + B[i]);
		}
	}
	cout << dp[N][H] << endl;
	return 0;
}


Measured memory_bytes: 78592
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//
struct edge{
	int from;int to;int cost;
	bool operator<(const edge&R)const{
		return cost<R.cost;
	}
};
struct kruskal{
	//
	int v,e;
	vector<int> par,ran;
	//
	kruskal(int n,int m){
		v=n;e=m;
		init(v);
	}
	//
	void init(int n){
		par.resize(n);
		ran.resize(n);
		for(int i=0;i<n;i++){
			par[i]=i;
			ran[i]=0;
		}
	}
	//
	int find(int x){
		if(par[x]==x){
			return x;
		}else{
			return par[x]=find(par[x]);
		}
	}
	//
	void unite(int x,int y){
		x=find(x);
		y=find(y);
		if(x==y){
			return ;
		}
		if(ran[x]<ran[y]){
			par[x]=y;
		}else{
			par[y]=x;
			if(ran[x]==ran[y]){
				ran[x]++;
			}
		}
	}
	//
	bool same(int x,int y){
		return find(x)==find(y);
	}
	//
	int cul(vector<edge> es){
		sort(es.begin(),es.end());
	    int res=0;
		for(int i=0;i<e;i++){
			edge &e=es[i];
			if(!same(e.from,e.to)){
				unite(e.from,e.to);
				res+=e.cost;
			}
		}
		return res;
	}
	//
};
//
int main(){
	int V,E;
	cin>>V>>E;
	vector<edge> G;
	for(int i=0;i<E;i++){
		int s,t,cost;
		cin>>s>>t>>cost;
		G.push_back((edge){s,t,cost});
	}
	kruskal k(V,E);
	cout<<k.cul(G)<<endl;
	return 0;
}


Measured memory_bytes: 5380
#include<iostream>
#include<cmath>

#define WIDTH 3
#define HEIGHT 3
#define ERORR -1

using namespace std;

int main()
{
	int n, ctl, map[2][HEIGHT+2][WIDTH+2], sx, sy, gx, gy, xx, yy, tx, ty;
	int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
	char s, t, b;
	while(cin >> n, n) {
		ctl = 0;
		cin >> s >> t >> b;
		for(int i=0; i < HEIGHT+2; i++)
			for(int j=0; j < WIDTH+2; j++) {
				for(int k=0; k < 2; k++) {
					if(i == 0 || i == HEIGHT+1 || j == 0 || j == WIDTH+1)
						map[k][i][j] = ERORR;
					else
						map[k][i][j] = 0;
				}
			}
		sx = (s-'A') % WIDTH + 1; sy = (s-'A') / WIDTH + 1;
		gx = (t-'A') % WIDTH + 1; gy = (t-'A') / WIDTH + 1;
		xx = (b-'A') % WIDTH + 1; yy = (b-'A') / WIDTH + 1;
		map[0][yy][xx] = map[1][yy][xx] = ERORR;
		map[ctl][sy][sx] = 1;
		int sum = 1 << (2 * n);
		while(n--) {
			for(int i=1; i <= HEIGHT; i++) {
				for(int j=1; j <= WIDTH; j++) {
					if(map[(ctl+1)%2][i][j] == ERORR) continue;
					map[(ctl+1)%2][i][j] = 0;
					for(int d=0; d < 4; d++) {
						tx = j + dx[d]; ty = i + dy[d];
						if(map[ctl][ty][tx] == ERORR) { tx = j; ty = i; }
						map[(ctl+1)%2][i][j] += map[ctl][ty][tx];
					}
				}
			}
			ctl = (ctl+1) % 2;
		}
		printf("%.8f\n", (float)(map[ctl][gy][gx])/sum);
		
	}
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define x first
#define y second
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ve vector
#define forn(i,n) for(int i=0;i<(int)n;i++)
#define pb push_back
#define sz(a) (int)(a.size())
//using namespace __gnu_pbds;
using namespace std;

// // // functions: find_by_order  & order_of_key
// typedef tree<
// int,
// null_type,
// less<int>,
// rb_tree_tag,
// tree_order_statistics_node_update>
// ordered_set;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;

const int inf=(int)2e9;
const long long mod=1000000007; //1E9+7
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};

ll powmod(ll a,ll p){
	ll ans=1;
	while(p){
		if(p&1) ans*=a;
		p/=2;a*=a; ans%=mod;a%=mod;
	}
	return ans;
}
ll mdinv(ll a){return powmod(a,mod-2); }

const int N=1e5+10;
vi adj[N];int DP[N][2];

void dfs(int i,int p){
	for(int v:adj[i])
		if(v!=p) dfs(v,i);
	DP[i][1]=1; //not allow
	DP[i][0]=1; //allow
	for(int v:adj[i])
		if(v!=p){
			DP[i][1]*=DP[v][0];
			DP[i][0]*=DP[v][1];
			if(DP[i][1]>=mod) DP[i][1]%=mod;
			if(DP[i][0]>=mod) DP[i][0]%=mod;
		}
	DP[i][0]+=DP[i][1];
	if(DP[i][0]>=mod) DP[i][0]%=mod;
}

signed main(){
	IOS
	int n;cin>>n;
	forn(i,n-1){
		int a,b;cin>>a>>b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	dfs(1,0);
	cout<<DP[1][0];
}


Measured memory_bytes: 12800
#include<stdio.h>

int main(void){

    int house[4][3][10] = {};
    int n,b,f,r,v;
    int i,j,k;
    scanf("%d",&n);

    for(i = 0; i < n; i++){
        scanf("%d %d %d %d",&b,&f,&r,&v);
        house[b-1][f-1][r-1] += v;
    }

    for(i = 0; i < 4; i++){
        for(j = 0; j < 3; j++){
            for(k = 0; k < 10; k++){
                printf(" %d",house[i][j][k]);
            }
            printf("\n");
        }
        if(i != 3){
        printf("####################\n");
        }
    }
    return 0;
}

Measured memory_bytes: 612
n = int(input())
s = [list(input()) for _ in range(n)]
for i in range(n):
    s[i].sort()
s.sort()

ans = 0
tmp = 1
for i in range(1, n):
    if s[i-1] == s[i]:
        ans += tmp
        tmp += 1
    else:
        tmp = 1
print(ans)

Measured memory_bytes: 24652
#include <stdio.h>
long long n,a,b;
int main()
{
	scanf("%lld %lld %lld",&n,&a,&b);
	if(a>b)
	{
		printf("0\n");
		return 0;
	}
	else
	{
		if(n==1)
		{
			if(a==b)
				printf("1\n");
			else
				printf("0\n");
		}
		else
		{
			long long sum=(b-a)*(n-2)+1;
			printf("%lld\n",sum);
			return 0;
		}
	}
}

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

bool ans(int x,int y){
    return x>=2*y-1;
}
int main(void){
    // Your code here!
    int x,y;
    cin >> x;
    cin >> y;
    if(ans(x,y)) printf("YES\n");
    else printf("NO\n");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int X, Y, Z;
  int A, B, C;
  cin >> X >> Y >> Z;
  
  B = X;
  A = Y;
  
  C = A;
  A = Z;
  
  cout << A << ' ' << B << ' ' << C << endl;
  
}

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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;

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 = 1e15;
const int MOD = 1e9+7;
const ll LINF = 1e18;

ll ans=INF;
bool isOk[10];
ll n,k;

void dfs(ll v){
  if(v>=n){
    chmin(ans,v);
    return;
  }
  rep(i,10){
    if(isOk[i]) dfs(v*10+i);
  }
}

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  cin>>n>>k;
  memset(isOk,true,sizeof(isOk));
  rep(i,k){
    ll a; cin>>a;
    isOk[a]=false;
  }
  
  reps(i,9) if(isOk[i]) dfs(i);
  cout<<ans<<endl;
}

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

template <typename InputIterator>
typename InputIterator::value_type summation(InputIterator first,
                                             InputIterator last) {
  return std::accumulate(first, last, typename InputIterator::value_type());
}
template <typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &v);
template <typename T1, typename T2>
std::istream &operator>>(std::istream &stream, std::pair<T1, T2> &p);
template <typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &v) {
  for (auto &i : v) {
    stream >> i;
  }
  return stream;
}
template <typename T1, typename T2>
std::istream &operator>>(std::istream &stream, std::pair<T1, T2> &p) {
  stream >> p.first >> p.second;
  return stream;
}

int main() {
  int64_t n;
  std::cin >> n;
  std::vector<int64_t> a(n);
  std::cin >> a;
  std::sort(a.begin(), a.end());

  if (a.front() <= 0 && 0 < a.back()) {
    int64_t ans = 0;
    for (const auto i : a) {
      if (0 < i) {
        ans += i;
      } else {
        ans -= i;
      }
    }
    std::cout << ans << std::endl;
    auto itr = a.begin();
    while (*itr <= 0) {
      itr++;
    }
    auto tmp = itr;
    itr++;
    for (; itr != a.end(); itr++) {
      std::cout << a.front() << " " << *itr << std::endl;
      a.front() -= *itr;
    }
    for (auto itr = a.cbegin(); *itr <= 0; itr++) {
      std::cout << *tmp << " " << *itr << std::endl;
      *tmp -= *itr;
    }
  } else if (a.front() < 0 && 0 <= a.back()) {
    int64_t ans = 0;
    for (const auto i : a) {
      if (0 < i) {
        ans += i;
      } else {
        ans -= i;
      }
    }
    std::cout << ans << std::endl;
    auto itr = a.begin();
    while (*itr < 0) {
      itr++;
    }
    auto tmp = itr;
    itr++;
    for (; itr != a.end(); itr++) {
      std::cout << a.front() << " " << *itr << std::endl;
      a.front() -= *itr;
    }
    for (auto itr = a.cbegin(); *itr < 0; itr++) {
      std::cout << *tmp << " " << *itr << std::endl;
      *tmp -= *itr;
    }
  } else if (a.front() == 0 && a.back() == 0) {
    std::cout << 0 << std::endl;
    for (int64_t i = 0; i < n - 1; i++) {
      std::cout << 0 << " " << 0 << std::endl;
    }
  } else if (0 <= a.front()) {
    std::cout << summation(a.cbegin(), a.cend()) - 2 * a.front() << std::endl;
    for (int64_t i = 1; i < n - 1; i++) {
      std::cout << a[0] << " " << a[i] << std::endl;
      a[0] -= a[i];
    }
    std::cout << a.back() << " " << a[0] << std::endl;
  } else {
    std::cout << -summation(a.cbegin(), a.cend()) + 2 * a.back() << std::endl;
    for (int64_t i = 0; i < n - 1; i++) {
      std::cout << a.back() << " " << a[i] << std::endl;
      a.back() -= a[i];
    }
  }

  return 0;
}

Measured memory_bytes: 2688
n=int(input())
H=list(map(int,input().split()))
cost=[0]*n
cost[0]=0
cost[1]=abs(H[1]-H[0])
for i in range(2,n):
    cost[i]=min(cost[i-2]+abs(H[i]-H[i-2]),cost[i-1]+abs(H[i]-H[i-1]))
print(cost[n-1])

Measured memory_bytes: 13928
import java.util.*;

public class Main {
	int bubbleSort(int[]lst){
		int n=lst.length;
		int count=0;
		for (int i=1;i<n;i++){
			for(int j=n-1;j>=i;j--){
				if(lst[j]<lst[j-1]){
					int x=lst[j];
					lst[j]=lst[j-1];lst[j-1]=x;
					count++;
				}
			}
		}
		return count;
	}
	public static void main(String[] args){
	    Scanner sc = new Scanner(System.in);
	    int n=sc.nextInt();
	    int[]x=new int[n];
	    for(int i=0;i<n;i++){x[i]=sc.nextInt();}
	    int c=new Main().bubbleSort(x);
	    for(int i=0;i<n;i++){
	        if(i==0){System.out.printf("%d",x[i]);continue;}
	        System.out.printf(" %d",x[i]);
	    }
	    System.out.printf("\n%d\n",c);
	}
}


Measured memory_bytes: 26436
var
	Q,i,j:Longint;
	T:Array[0..30]of int64;
	a,b,c,d,aa,bb,cc,dd,ans,plus,tmp:int64;
begin
	T[0]:=1;
	for i:=1 to 30 do T[i]:=T[i-1]*3;
	read(Q);
	for i:=1 to Q do begin
		read(a,b,c,d);
		dec(a);
		dec(b);
		dec(c);
		dec(d);
		ans:=abs(a-c)+abs(b-d);
		plus:=0;
		for j:=30 downto 1 do begin
			if(a div T[j-1]=c div T[j-1])and(a div T[j-1]mod 3=1)then begin
				bb:=b div T[j-1];
				dd:=d div T[j-1];
				if bb>dd then begin
					tmp:=bb;
					bb:=dd;
					dd:=tmp;
				end;
				while bb mod 3<>1 do inc(bb);
				if bb<=dd then begin
					a:=a mod T[j];
					c:=c mod T[j];
					if a>c then begin
						tmp:=a;
						a:=c;
						c:=tmp;
					end;
					if a+c+1<3*T[j-1]then plus:=a+1-T[j-1]else plus:=2*T[j-1]-c;
					break;
				end;
			end;
			if(b div T[j-1]=d div T[j-1])and(b div T[j-1]mod 3=1)then begin
				aa:=a div T[j-1];
				cc:=c div T[j-1];
				if aa>cc then begin
					tmp:=aa;
					aa:=cc;
					cc:=tmp;
				end;
				while aa mod 3<>1 do inc(aa);
				if aa<=cc then begin
					b:=b mod T[j];
					d:=d mod T[j];
					if b>d then begin
						tmp:=b;
						b:=d;
						d:=tmp;
					end;
					if b+d+1<3*T[j-1]then plus:=b+1-T[j-1]else plus:=2*T[j-1]-d;
					break;
				end;
			end;
		end;
		writeln(ans+plus*2);
	end;
end.


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
 
int main(void){
  int n,i;
  double hensa2,bunsan,sum,heikin;
  while(1){
    hensa2=0;
    sum=0;
    scanf("%d",&n);
    if(n==0) break;
    double s[n];
    for(i=0;i<n;i++){
      scanf("%lf",&s[i]);
      sum+=s[i];
    }
    heikin=sum/n;
    for(i=0;i<n;i++){
      hensa2+=(s[i]-heikin)*(s[i]-heikin);
    }
    bunsan=hensa2/n;
    printf("%lf\n",sqrt(bunsan));
  }
  return 0;
}


Measured memory_bytes: 2048
#include<set>    
#include<iostream>    
using namespace std;
int main()
{
    set<string>s;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        string x;
        cin>>x;
        s.insert (x);
    }
   
    cout<<s.size ()<<endl;
    return 0;
}

Measured memory_bytes: 19132
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
# list(map(int, input().split()))

N, M = map(int, input().split())

ans = [-1] * N
for i in range(M):
    s, c = map(int, input().split())
    if ans[s - 1] > -1 and ans[s - 1] != c:
        print(-1)
        exit()
    ans[s - 1] = c

if N > 1 and ans[0] == 0:
    print(-1)
    exit()

ans = list(map(lambda x: str(x) if x != -1 else str(0), ans))
if N > 1 and ans[0] == '0':
    ans[0] = '1'
ans = "".join(ans)
print(ans)




Measured memory_bytes: 9476
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define e1 first
#define e2 second
#define int int_fast32_t
#define uint uint_fast64_t
#define ll int_fast64_t
#define ull uint_fast64_t
#define int16 int_fast16_t
#define uint16 uint_fast16_t
#define int32 int_fast32_t
#define uint32 uint_fast32_t
#define int64 int_fast64_t
#define uint64 uint_fast64_t
#define ld long double
#define float long double
#define size(x) (int)x.size()
#define satori int testCases; cin>>testCases; while(testCases--)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(r) begin(r),end(r)
#define rall(r) rbegin(r),rend(r)
#define time chrono::high_resolution_clock().now().time_since_epoch().count()
#define elapsed(__begin,__end) (__end-__begin)/CLOCKS_PER_SEC
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
float pi=3.14159265358979323846;

const int MAXN=8e1+10;

ll dp[MAXN],a[MAXN];

int32_t main()
{
	fastio;
	int n;
	cin>>n;
	dp[0]=1000;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		dp[i]=max(dp[i],dp[i-1]);
		for(int j=i+1;j<=n;j++)
			dp[j+1]=max(dp[j+1],(dp[i]/a[i])*a[j]+dp[i]%a[i]);
	}
	dp[n+1]=max(dp[n+1],dp[n]);
	cout<<dp[n+1]<<'\n';
}

Measured memory_bytes: 3684