akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define range(i,a,n) for(ll i=(a);i<(n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI (3.1415926535897932384)

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
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 S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}

template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>void tf(bool b,S t,T f){if(b)puta(t);else puta(f);}
void YN(bool b){tf(b,"YES","NO");}
void Yn(bool b){tf(b,"Yes","No");}
void yn(bool b){tf(b,"yes","no");}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1;for(auto s:t){os<<(a?"":" ")<<s;a=0;}return os;}
template<class S>auto&operator>>(istream&is,vector<S>&t){for(S&a:t)cin>>a;return is;}

/*他のライブラリを入れる場所*/
void solve(int n, int m, int p){
	bool fin=false;
	vvvi f(n+2,vvi(n+2, vi(n+2,-1)));
	rep(t,p){
		int x,y,z; cin>>x>>y;
		if(fin)continue;
		range(i,1,n+1)if(f[x][y][i]==-1){z=i;break;}
		f[x][y][z]=t%2;
		map<tlll, int> mp;
		for(auto dx:{-1,0,1})
		for(auto dy:{-1,0,1})
		for(auto dz:{-1,0,1})if(dx or dy or dz){
			mp[tlll(dx,dy,dz)]=0;
			rep(i,n){
				if(f[x+dx*i][y+dy*i][z+dz*i]==t%2)mp[tlll(dx,dy,dz)]++;
				else break;
			}
		}

		int val=0;
		for(auto&p:mp){
			int dx,dy,dz;
			tie(dx,dy,dz)=p.fs;
			chmax(val, p.sc+mp[tlll(-dx,-dy,-dz)]-1);
		}
		if(val>=m){
			puta(t%2?"White":"Black", t+1);
			fin=true;
		}
	}
	if(!fin) puta("Draw");
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,m,p;
	while(cin>>n>>m>>p, n+m+p){
		solve(n,m,p);
	}
	return 0;
}


Measured memory_bytes: 3164
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define int long long
constexpr long long INF = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;



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

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

    int x=max(H,W);

    cout << (N+x-1)/x << endl;








}


Measured memory_bytes: 3568
// E.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long LL;

int main(int argc, char* argv[]) {
	cout.precision(20);
#ifdef _MSC_VER
	while (true)
#endif
	{
		int n = -1;
		cin >> n;
		if (n < 0) return 0;
		vector<pair<LL, int>> v(n);
		for (int i = 0; i < n; ++i) {
			cin >> v[i].first;
			v[i].second = i;
		}
		sort(v.rbegin(), v.rend());
		vector<vector<LL>> dp(n + 1, vector<LL>(n + 1));
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j <= i; ++j) {
				dp[j + 1][i - j] = max(dp[j + 1][i - j], dp[j][i - j] + v[i].first * abs(j - v[i].second));
				dp[j][i - j + 1] = max(dp[j][i - j + 1], dp[j][i - j] + v[i].first * abs(n - 1 - (i - j) - v[i].second));
			}
		}
		LL ans = 0;
		for (int i = 0; i <= n; ++i) {
			ans = max(ans, dp[i][n - i]);
		}
		cout << ans << endl;
		}
	return 0;
}


Measured memory_bytes: 34676
program test
implicit none
integer(8) :: n,k,c,i,j,dp_left(0:200000)=10**6,dp_right(0:200000)=10**6,workday=0
character(len=200000) :: s

read(*,*) n,k,c
read(*,*) s(1:n)

!dp_leftは,左から見たときにi日目の最速の労働日
workday = 0
dp_left(0) = 0
dp_right(0) = 0

do i=1,n
  if(s(i:i)=='x')then
    continue
  else
    if(workday == 0)then
      workday = workday + 1
      dp_left(workday) = i
    else
      if(i > dp_left(workday) + c) then
        workday = workday + 1
        dp_left(workday) = i
      endif
    endif
  endif
enddo

!dp_rightは,右から見たときにi日目の最遅の労働日
workday = 0
do i=n,1,-1
  if(s(i:i)=='x')then
    continue
  else
    if(workday == 0)then
      workday = workday + 1
      dp_right(workday) = i
    else
      if(i < dp_right(workday) - c) then
        workday = workday + 1
        dp_right(workday) = i
      endif
    endif
  endif
enddo

do i=1,k
  if(dp_left(i)==dp_right(k+1-i)) then
    write(*,*) dp_left(i)
  endif
enddo

end

Measured memory_bytes: 8204
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 3000003,mo=998244353;
int n,m,res,fac[N],ifac[N];
inline void add(int &x, int y){x=x+y<mo?x+y:x+y-mo;}
inline int power(int a, int n) {
	int res=1;
	while (n) {
		if (n&1) res=1LL*res*a%mo;
		a=1LL*a*a%mo; n>>=1;
	}
	return res;
}
void init(int n){
	fac[0]=1;rep(i,1,n)fac[i]=1LL*fac[i-1]*i%mo;
	ifac[n]=power(fac[n],mo-2);per(i,n-1,0)ifac[i]=1LL*ifac[i+1]*(i+1)%mo;
}
int C(int n, int m){return m>=0&&m<=n?1LL*fac[n]*ifac[m]%mo*ifac[n-m]%mo:0;}
int main() {
	read(n);read(m);init(N-1);int tot=3*m;
	rep(i,0,m)if((tot-i)%2==0)
		res=(res+1LL*C(n,i)*C((tot-i)/2+n-1,n-1))%mo;
	rep(i,tot/3*2+1,tot)res=(res-1LL*n*C(tot-i+n-2,n-2))%mo;
	printf("%d",(res+mo)%mo);
	return 0;
}


Measured memory_bytes: 23680
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;



public class Main { 
	
	static ArrayList<int[]> arrList =  new ArrayList<int[]>(); 
		
	static HashMap<Integer, int[]> points =  new HashMap<Integer, int[]>();
	
	public static <T> void printAllRecursive(
			  int n, int[] elements) {			 
			    if(n == 1) {
			        printArray(elements);
			    } else {
			        for(int i = 0; i < n-1; i++) {
			            printAllRecursive(n - 1, elements);
			            if(n % 2 == 0) {
			                swap(elements, i, n-1);
			            } else {
			                swap(elements, 0, n-1);
			            }
			        }
			        printAllRecursive(n - 1, elements);
			    }
    }
	
	private static void swap(int[] input, int a, int b) 
    {
	    int tmp = input[a];
	    input[a] = input[b];input[b] = tmp;
	    input[b] = tmp;
	}	
	private static void printArray(int[] input) {
		//creating a new array
		int [] addArray =  new int [input.length];
		for(int index=0; index< input.length; index++) {
			addArray [index] = input[index];
		}
	    arrList.add(addArray);
	}	
	public static void main(String[] args) {		
		Scanner scan =  new Scanner(System.in); 		
		//number of points on the plain
		int numOfPlains =  scan.nextInt();
		int [] pointsIndex =new int[numOfPlains];		
		for(int i=0; i< numOfPlains; i++) {
			pointsIndex[i] = i;
			int [] coord =  new int [2];
			coord [0] = scan.nextInt();
			coord [1] = scan.nextInt();
			points.put(i, coord);
		}	
		printAllRecursive(numOfPlains, pointsIndex);			
		
		double sumOfDistances = 0.0;
		for(int[] path : arrList) {
			for(int i=0; i<path.length-1; i++) {				
					sumOfDistances += (calculateDistance(points.get(path[i]), points.get(path[i+1])));							
			}
		}		
		double avgDistance = sumOfDistances/arrList.size();  
		System.out.println(avgDistance+"");
		
	}
	
	static double calculateDistance(int[] p1, int[] p2) {
		double result=0.0;
		result = Math.sqrt(Math.pow((p2[0]-p1[0]), 2) + Math.pow((p2[1]-p1[1]), 2));		
		return result;
	}
	
}

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

using namespace std;

int main()
{
    long N;

    cin >> N;

    long sum = 0;
    for ( long i = 1; i < N; i ++ ) {
        sum += i;
    }
    cout << sum << endl;

    return 0;
}


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

int main(){
  int a,b;
  cin >> a >> b;
  int ans;
  if(a % b == 0) ans = 0;
  else ans = 1;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import copy

V = [list(raw_input()) for i in range(8)]
_V = []
for r in range(8):
    lis = []
    for c in range(8):
        lis.append('')
    else:
        _V.append(lis)
for angle in [90, 180, 270]:
    for r in range(8):
        for c in range(8):
            _V[c][7-r] = V[r][c]
    else:
        V = copy.deepcopy(_V)
    print angle
    for line in V:
        print ''.join(line)

Measured memory_bytes: 4264
import java.util.Scanner;

public class Main {

	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		int n = sc.nextInt();
		int[] house = new int[n];
		for(int i=0;i<n;i++){
			house[i]=sc.nextInt();
		}
		int maxDist = k-(house[n-1]-house[0]);
		for(int i=0;i<n-1;i++){
			if(house[i+1]-house[i]>maxDist){
				maxDist = house[i+1]-house[i];
			}
		}
		System.out.println(k-maxDist);
	}
}


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

#define for_(i,a,b) for(int i=(a);i<(b);++i)

int h, w, c;
const int dx[4] = {0,-1,0,1};
const int dy[4] = {-1,0,1,0};

bool in_range(int x, int y) { return 0 <= x && x < w && 0 <= y && y < h; }

int countDFS(vector< vector< int > >& p, int x, int y, int cur) {
	p[y][x] = -1;
	int res = 1;
	for_(d,0,4) {
		int nx = x + dx[d], ny = y + dy[d];
		if (!in_range(nx, ny)) continue;
		if (p[ny][nx] == cur) res += countDFS(p, nx, ny, cur);
	}
	return res;
}

void change(vector< vector< int > >& p, int x, int y, int cur, int nxt) {
	p[y][x] = nxt;
	for_(d,0,4) {
		int nx = x + dx[d], ny = y + dy[d];
		if (!in_range(nx, ny)) continue;
		if (p[ny][nx] == cur) change(p, nx, ny, cur, nxt);
	}
}

void dfs(int i, vector< vector< int > > p, int& ans) {
	if (i == 5) {
		ans = max(ans, countDFS(p, 0, 0, c));
		return;
	}
	
	for_(nxt,1,7) {
		if (i == 4 && nxt != c) continue;
		if (p[0][0] == nxt) continue;
		vector< vector< int > > nxt_p = p;
		change(nxt_p, 0, 0, p[0][0], nxt);
		dfs(i + 1, nxt_p, ans);
	}
}

int main() {
	while (cin >> h >> w >> c) {
		if (h == 0) break;
		vector< vector< int > > p(h, vector< int >(w));
		for_(y,0,h) for_(x,0,w) cin >> p[y][x];
		
		int ans = 0;
		dfs(0, p, ans);
		cout << ans << endl;
	}
}

Measured memory_bytes: 3032
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

const int lx[] = { -1, -1, -1, -1, -1, -2, -2, -2, -3 };
const int ly[] = { -2, -1,  0,  1,  2, -1,  0,  1,  0 };
const int rx[] = {  1,  1,  1,  1,  1,  2,  2,  2,  3 };
const int ry[] = { -2, -1,  0,  1,  2, -1,  0,  1,  0 };

class State
{
public:
	int x, y, cost, isLeft;

	State(int xx, int yy, int c, int lr)
		:x(xx), y(yy), cost(c), isLeft(lr) {}
	bool operator < (const State& st) const
	{
		return this->cost > st.cost;
	}
};


int main()
{
	//freopen("D", "r", stdin);
	const int INF = 1 << 30;

	int w, h;
	while (scanf("%d %d", &w, &h) != EOF) {
		if (w == 0 && h == 0)
			break;

		static int cost[61][31][2];
		static bool visited[61][31][2];
		for (int i = 0; i < 61; ++i) {
			for (int j = 0; j < 31; ++j) {
				cost[i][j][0] = INF;
				cost[i][j][1] = INF;
				visited[i][j][0] = false;
				visited[i][j][1] = false;
			}
		}

		char f[61][31];
		priority_queue<State> que;
		for (int i = 0; i < h; ++i) {
			for (int j = 0; j < w; ++j) {
				cin >> f[i][j];
				//scanf("%d", &f[i][j]);
				if (f[i][j] == 'S') {
					que.push(State(j, i, 0, 1));
					que.push(State(j, i, 0, 0));
				}
			}
		}

		int ans = INF;
		while (!que.empty()) {
			const State st = que.top();
			que.pop();

			//printf("(%d, %d) (%d, %d)\n", st.left.x, st.left.y, st.right.x, st.right.y);

			if (f[st.y][st.x] == 'T') {
					ans = st.cost;
					break;
			}

			if (visited[st.y][st.x][st.isLeft] ||
				cost[st.y][st.x][st.isLeft] < st.cost)
				continue;

			visited[st.y][st.x][st.isLeft] = true;

			if (st.isLeft == 1) {
				for (int i = 0; i < 9; ++i) {
					int xx = st.x + rx[i];
					int yy = st.y + ry[i];
					if (xx < 0 || xx >= w || yy < 0 || yy >= h || f[yy][xx] == 'X')
						continue;
					int c = st.cost;
					if (isdigit(f[yy][xx]))
						c += (f[yy][xx] - '0');
					if (cost[yy][xx][0] > c) {
						cost[yy][xx][0] = c;
						que.push(State(xx, yy, c, 0));
					}
				}
			} else {
				for (int i = 0; i < 9; ++i) {
					int xx = st.x + lx[i];
					int yy = st.y + ly[i];
					if (xx < 0 || xx >= w || yy < 0 || yy >= h || f[yy][xx] == 'X')
						continue;
					int c = st.cost;
					if (isdigit(f[yy][xx]))
						c += (f[yy][xx] - '0');
					if (cost[yy][xx][1] > c) {
						cost[yy][xx][1] = c;
						que.push(State(xx, yy, c, 1));
					}
				}
			}
		}

		if (ans == INF)
			ans = -1;
		printf("%d\n", ans);
	}

	return 0;
}

Measured memory_bytes: 972
# 754
s = input()
dif = 0
i= 0
ans = 753
for i in range(len(s)-2):
    temp = int(s[i])*100 + int(s[i+1])*10 + int(s[i+2])
    dif = abs(int(temp) - 753)
    ans = min(dif, ans)
print(ans)

Measured memory_bytes: 3060
S = input()
l = []
for i in S:
    l.append(int(i))


for i in range(1 << 3):
    output = l[0]
    res = '{}'.format(l[0])
    for j in range(3):
        if ((i >> j) & 1) == 1:
            output += l[j+1]
            res += '+{}'.format(l[j+1])
        else:
            output -= l[j+1]
            res += '-{}'.format(l[j+1])
    if output ==7:
        res += '=7'
        print(res)
        exit()

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

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
constexpr int mod = 1e9 + 7;

struct mint {
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint &operator-=(const mint a) {
    if ((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint &operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res -= a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1) a *= *this;
    return a;
  }
  mint inv() const { return pow(mod - 2); }
  mint &operator/=(const mint a) { return (*this) *= a.inv(); }
  mint operator/(const mint a) const {
    mint res(*this);
    return res /= a;
  }
  friend ostream &operator<<(ostream &os, const mint &a) { return (os << a.x); }
};
struct combination {
  vector<mint> fact, ifact;
  combination(int n) : fact(n + 1), ifact(n + 1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * ifact[k] * ifact[n - k];
  }
};

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

  if (n > k) n %= k;

  while (n > abs(n - k)) { n = abs(n - k); }

  cout << n << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
  
int main()
{
	int n,m;
	int p[51]={0};
	int c[51]={0};
	int i;
	int ans;

	while(1)
	{
	scanf("%d %d",&n,&m);
	if((n==0)&&(m==0))
		break;
	ans=n;

	for(i=1;i<=m;i++){
		scanf("%d %d",&p[i],&c[i]);	
	} 

	for(i=m;i>=1;i--){
		if(p[i]!=1){
		if((n-p[i]-c[i]+1)>=ans){
		}else if(ans>=(n-c[i]+1)){
			ans = ans-p[i]+1;
		}else
			ans = ans+c[i];
		}
	}

	printf("%d\n",ans);

	}
	return 0;
}

Measured memory_bytes: 1028
#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define ios() cin.tie(0), ios::sync_with_stdio(false)
typedef long long ll;
typedef unsigned long long ull;
ll const MOD = 1e9+7;
ll const INF = 1e18;
using namespace std;

int main(){
    ll a, b, x;
    cin >> a >> b >> x;
    cout << b/x - a/x + (a%x == 0) << endl;
    return 0;
}

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

int main(void)
{
	cin.tie(0);	ios_base::sync_with_stdio(0);
	string s;	cin >> s;
	if(s[2] == s[3] && s[4] == s[5])
		cout << "Yes";
	else
		cout << "No";
	return 0;
}

Measured memory_bytes: 256
n = int(input())
w_list = list(map(int,input().split()))
total = sum(w_list)
half = total/2
t = 0
ho = 0
for w in w_list:
  if ho < half:
    ho += w
  else:
    break
  t += 1
h1 = ho
h2 = ho - w_list[t-1]
print(int(min(abs(half-h2),abs(half-h1))*2))

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

using namespace std;

int N;
int in[10];

int main() {
	cin >> N;
	for (int i = 0; i < N; i++)cin >> in[i];
	int ans = 1;
	for (int i = 0; i < N; i++) {
		if (in[i] % 2 == 0)ans *= 2;
		else ans *= 1;
	}
	cout << pow(3, N) - ans << endl;
	return 0;
}

Measured memory_bytes: 512
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll;
#define rep(i, a, b) for (int i = a; i <= b; ++ i)
using namespace std;
int x, y;
int main() {
	scanf("%d%d", &x, &y); int ret = abs(abs(x) - abs(y));
	if (x >= 0 && y >= 0) {
		if (abs(y) >= abs(x)) printf("%d", ret);
			else printf("%d", min(ret + 2, y + x + 1));
	} else if (x >= 0 && y < 0) printf("%d", ret + 1); else
	if (x < 0 && y >= 0) printf("%d", min(ret + 1, y - x)); else {
		if (abs(y) > abs(x)) printf("%d", ret + 2);
			else printf("%d", ret);
	}
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define Long long long;
#define fastIO ios::sync_with_stdio(0) , cin.tie(0)

const int MX = 1e5 + 5, activ = 3;
int arr[MX][3] , dp[MX][3];
const int MIN = 0;

int solve( int day , int activity ){
    if( day == 0 ) return 0;

    if( dp[day][activity] != -1 ) return dp[day][activity];

    for( int ac = 0 ; ac < activ ; ++ac ){
        if( ac != activity ){
            dp[day][activity] = max( dp[day][activity] , solve( day-1 , ac) + arr[day][ac] );
        }
    }
    return dp[day][activity];
}

int main(){

    fastIO;

    int n;
    cin >> n;

    for( int i=1 ; i<=n ; ++i){
        for( int j=0 ; j<3 ; ++j){
            cin >> arr[i][j];
        }
    }

    memset( dp , -1 , sizeof dp);
    vector<int> ans = {solve(n,0) , solve(n,1) , solve( n,2)};
    cout << *max_element(ans.begin() ,ans.end()) << endl ;

    return 0;

}

Measured memory_bytes: 10368
INTMAX = 9223372036854775807
def LI(): return [int(x) for x in input().split()]
def II(): return int(input())

N,K=LI()
INL=LI()
dp = [INTMAX]*N
dp[0] = 0

for i in range(0,N):
    for j in range(1,K+1):
        k = i+j
        if k < N:
            dp[k] = min(dp[k], dp[i]+abs(INL[k]-INL[i]))

# print(dp)
print(dp[N-1])


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

int main(void) {
	const int MAX_X = 1000000;
	int K, X;
	cin >> K >> X;

	int l = max(X - K + 1, -MAX_X);
	int r = min(X + K - 1, MAX_X);

	for (int i = l; i <= r; ++i)
		cout << i << ((i == r) ? '\n' : ' ');

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define N 1050
typedef long long ll;
int ir,ic,grid[N][N];
ll memo[N][N];
const ll m = (ll)1e9 + 7;

bool inside(int r , int c) {
    return r >= 1 && r <= ir && c >= 1 && c <= ic;
}

ll add(ll a , ll b) {
    return ((a % m) + (b % m)) % m;
}

ll dp(int r , int c) {
    if (r == ir && c == ic) return 1;
    if (grid[r][c] == -1) return 0;
    if (!inside(r , c)) return 0;
    ll &sol = memo[r][c];
    if (sol != -1) return sol;
    return sol = add(dp(r + 1 , c) , dp(r , c + 1));
}

int main() {
    scanf("%d%d" , &ir , &ic);
    for (int r = 1 ; r <= ir ; r++) {
        char inp[N]; scanf("%s" , inp);
        for (int c = 0 ; c < strlen(inp) ; c++) {
            int keep = 0;
            if (inp[c] == '#') keep = -1;
            grid[r][c + 1] = keep;
        }
    }
    memset (memo , -1 , sizeof memo);
    printf("%lld\n" , dp(1 , 1));
}


Measured memory_bytes: 16600
use std::io::stdin;

fn main() {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    let mut values: Vec<i32> = buf.split_whitespace()
        .filter_map(|x| x.parse::<i32>().ok())
        .collect();
    values.sort();
    let values: Vec<String> = values.iter().rev().map(|x| x.to_string()).collect();
    println!("{}", values.join(" "));
}



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

using namespace std;
#define ll long long
const int N=105;
int main()
{
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n)
    {
        int t[N],s=0;
        for(int i=1;i<=n;i++)
            cin>>t[i],s+=t[i];
        int m;
        cin>>m;
        while(m--)
        {
            int p,x;
            cin>>p>>x;
            cout<<s-t[p]+x<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
use proconio::{input, fastout};
use proconio::marker::{Chars};
use proconio::marker::Usize1;
use std::cmp::*;

macro_rules! debug {
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

#[fastout]
fn main() {
    input!{
        n: usize,
    }
    println!("{}", (1+n)*n/2);
}


Measured memory_bytes: 2168
#include<iostream>
using namespace std;
int main()
{
  int n,i,c=0;
  cin>>n;
  int ar[n];
  for(i=0; i<n; i++)
  {
    cin>>ar[i];
  }
  for(i=0; i<n; i++)
  {
    if((i+1)%2!=0 && (ar[i]%2)!=0)
      c++;
  }
  cout<<c;
  
}


Measured memory_bytes: 3572
N, M = map(int, input().split())

ab = [[] for _ in range(M)]
for i in range(len(ab)):
    ab[i] = list(map(int, input().split()))

dict = {}
for i in range(N):
    dict[i + 1] = 0

for i in range(len(ab)):
    dict[ab[i][0]] += 1
    dict[ab[i][1]] += 1

for i in range(N):
    print(dict[i + 1])


Measured memory_bytes: 62532
import itertools
import copy
H, W, K = map(int, input().split())
C = []
for _ in range(H):
    C.append([c for c in input()])

H_list = [i for i in range(H)]
H_comb = []
for i in range(1, H):
    H_comb += itertools.combinations(H_list, i)

W_list = [i for i in range(W)]
W_comb = []
for i in range(1, W):
    W_comb += itertools.combinations(W_list, i)

ans = 0
cnt = 0
for w in C: cnt += w.count('#')
if cnt == K: ans += 1

for wc in W_comb:
    temp_C0 = copy.deepcopy(C)
    for i in sorted(wc, reverse=True):
        for w in temp_C0: w.pop(i)
    cnt = 0
    for w in temp_C0 : cnt += w.count('#')
    if cnt == K: ans += 1

for hc in H_comb:
    temp_C1 = copy.deepcopy(C)
    for i in sorted(hc, reverse=True): temp_C1.pop(i)
    cnt = 0
    for w in temp_C1: cnt += w.count('#')
    if cnt == K: ans += 1
    for wc in W_comb:
        temp_C2 = copy.deepcopy(temp_C1)
        for j in sorted(wc, reverse=True):
            for w in temp_C2: w.pop(j)
        cnt = 0
        for w in temp_C2 : cnt += w.count('#')
        if cnt == K: ans += 1
print(ans)


Measured memory_bytes: 9084
import numpy as np
 
bingo = list()
for i in range(3):
    bingo.append(list(map(int,input().split())))
N = int(input())
number = list()
for i in range(N):
    number.append(int(input()))
   
bingo_array = np.array(bingo)
check_array = np.zeros([3,3])
for i in range(N):
    check_array[bingo_array==number[i]] = 1
 
row = np.count_nonzero(np.any(check_array.sum(axis=0)==3))
column = np.count_nonzero(np.any(check_array.sum(axis=1)==3))
r_naname = 0
l_naname = 0
for i in range(3):
    r_naname += check_array[i, 2-i]
    l_naname += check_array[i, i]
 
if row != 0 or column != 0 or r_naname == 3 or l_naname == 3:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 14044
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;
using ll = long long;

#define INF 1000000007
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((int)(x).size())
#define MSG(a) cout << #a << " " << a << endl;

int main()
{
    // TLE
    int n;
    cin >> n;
    int tmp;
    int ans = 0;
    vector<int> v;
    int min_value = INF;
    while (cin >> tmp) {
        v.push_back(tmp);
        min_value = min(min_value, tmp);
        if (min_value == tmp) ans++;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1400
N=int(input())
count=0

a=list(map(int,input().split()))
a.sort()

if N>=3:
    for i in range(N-2):
        for j in range(i+1,N-1):
            for k in range(j+1,N):
                if a[i]!=a[j]!=a[k]!=a[i]:
                    if a[k]<a[i]+a[j]:
                            count+=1
                        
print(count)


Measured memory_bytes: 9192
object Main extends App {

  import scala.io.Source._

  val matrix = stdin.getLines().map(_.split(' ').map(_.toInt).toArray).toArray
  println(if ((1 to 2).forall(x => (0 to 2).map(y => matrix(x)(y) - matrix(x - 1)(y)).distinct.size == 1 && (0 to 2).map(y => matrix(y)(x) - matrix(y)(x - 1)).distinct.size == 1)){
    "Yes"
  }else{
    "No"
  })
}

Measured memory_bytes: 25540
import java.util.Scanner;

public class Main {

	public static void main(String[] args){
		
		Scanner input = new Scanner(System.in);
		long N = input.nextInt();
        long D = input.nextInt();
        long remain = (long)(2 * Math.pow(10,9)) * 2;
        for (long i = N; i < D; i++) {
            for (long j = i + 1; j <= D; j++) {
                if((i*j)%2019 < remain)
                    remain = (i*j)%2019;
                if(remain == 0)
                    break;
            }
            if(remain == 0)
                break;
        }
		System.out.println(remain);
	}
}


Measured memory_bytes: 23764
#include <iostream>
#include <string>
#include <algorithm>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

int N, K, C;
string S;
int dpL[200001];
int dpR[200001];

int dfsL(int day) {
	if (day >= N) return 0;
	if (dpL[day] != -1) return dpL[day];
	if (S[day] == 'x') return dpL[day] = dfsL(day + 1);
	
	int res1 = dfsL(day + 1);
	int res2 = dfsL(day + C + 1) + 1;
	return dpL[day] = max(res1, res2);
}

int dfsR(int day) {
	if (day < 0) return 0;
	if (dpR[day] != -1) return dpR[day];
	if (S[day] == 'x') return dpR[day] = dfsR(day - 1);
	
	int res1 = dfsR(day - 1);
	int res2 = dfsR(day - C - 1) + 1;
	return dpR[day] = max(res1, res2);
}

int main() {
	int i;
	
	cin >> N >> K >> C >> S;
	rep(i, N) dpL[i] = -1;
	rep(i, N) dpR[i] = -1;
	rep(i, N) {
		if (S[i] == 'x') continue;
		int res1 = dfsL(i + C + 1) + dfsR(i - C - 1) + 1;
		int res2 = dfsL(i + 1) + dfsR(i - 1);
		if (res2 < K && res1 >= K) { cout << i + 1 << endl; }
	}
	return 0;
}

Measured memory_bytes: 9604
//In the name of Allah
#include <bits/stdc++.h>
using namespace std;
#define MAX 100011
#define inf 1000000000000000
#define ll long long
#define endl '\n'
vector<int> g[MAX];
stack<int> st;
bool see[MAX];
void dfs(int u){
	see[u] = 1;
	for(auto v : g[u]){
		if(!see[v])
			dfs(v);
	}
	st.push(u);
}
int dis[MAX];
int main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,x,y,m;
	cin>>n>>m;
	for(int i = 0; i < m ; i++){
		cin>>x>>y;
		g[x].push_back(y);
	}
	for(int i = 1; i <= n ; i++)
		if(!see[i])dfs(i);

	int ans = 0;
	while(st.size()){
		int u = st.top();
		st.pop();
		for(auto v : g[u]){
			if(dis[v] < dis[u] + 1)
				dis[v] = dis[u] + 1, ans = max(dis[v],ans);
		}
	}
	cout<<ans;
	return 0; 
} 

Measured memory_bytes: 8704
'''ika tako
小数が出てくるとややこしいが、 bi=ai/2  として、 
X=bi*(2p+1)  としてしまえばいい。
これで、以下の2つを満たせばよいことがわかりやすくなる。
X  は全ての  bi  の公倍数
X  を  bi  で割った商は全て奇数
なので、とりあえず全ての  bi  の最小公倍数を求めて、それが  
bi  で割ると全て奇数となるか確認する。
1つでも偶数となるものがあれば、達成不可能。
全て奇数なら、最小公倍数の奇数倍が全て条件を満たす。
2数  n,m  の最小公倍数は、最大公約数を  g  として  
n*m/g  で求められる。3数以上なら、これを繰り返し適用しつづければよい。
ただし  bi  が互いに素だと、最小公倍数は繰り返している内に
とてつもなく大きくなってしまう。途中で  M  以上になった時点で  
M  以下の半公倍数は不可能なので、0を出力して即終了する。
'''
from fractions import gcd
 
def solve(n, m, aaa):
    lcm = 1
    for a in aaa:
        a //= 2
        lcm *= a // gcd(lcm, a)
        if lcm > m:
            return 0
    for a in aaa:
        if int(lcm / a) == lcm / a:
            return 0
    return (m // lcm + 1) // 2

n, m = list(map(int, input().split()))
aaa = list(map(int, input().split()))
 
print(solve(n, m, aaa))

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

#define INF 1e9
using namespace std;
typedef long long ll;

int main() {

    string s; cin >> s;

    int alpha[26] = {0};

    for (int i = 0; i < s.size(); ++i) {
        int t = s[i] - 'a';
        if (alpha[t] == 0) {
            alpha[t]++;
        }
    }

    for (int i = 0; i < 26; ++i) {
        if (alpha[i] == 0) {
            cout << char('a' + i) << endl;
            return 0;
        }
    }

    puts("None");
}

Measured memory_bytes: 512
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef pair<int, int> pii;
#define rep(i, n) for(ll i = 0; i < (ll)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define msg(a) cout << #a << " " << a << endl
#define eb emplace_back

int main() {
    int N;
    int K;
    string S;
    cin >> N >> K >> S;

    S[K - 1] = tolower(S[K - 1]);

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



Measured memory_bytes: 256
#include <stdlib.h>
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
using ll=long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}

int main() {
  string s;
  cin>>s;
  long long a;
  long long count=0;
  cin>>a;
  char lc='.';
  rep(i,s.size()){
    if(s.at(i)==lc){
      lc=' ';
      count++;
    }
    else{
      lc=s.at(i);
    }
  }
  lc=s.at(0);
  long long num1=0;long long num2=0;
  if(s.at(0)==s.at(s.size()-1)){
    rep(i,s.size()){
      if(s.at(i)!=lc){
        break;
      }
      else{
        num1++;
      }
    }
    for(long long i=s.size()-1;i>=0;i--){
      if(lc!=s.at(i)){
        break;
      }
      else{
        num2++;
      }
    }
  }
  //cout<<num1<<endl<<num2<<endl;
  if(num1%2!=0&&num2%2!=0){
    if(num1==s.size()&&s.size()%2!=0){
      cout<<count*a+a/2<<endl;
    }
    else{
      cout<<count*a+(a-1)<<endl;
    }
  }
  else{
    cout<<count*a<<endl;
  }

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define FastRead        ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl            "\n"
#define pi              acos(-1);
#define ordered_set     tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

typedef long long ll;


int main()
{
    FastRead

    ll x,y,z;

    cin>>x>>y>>z;

    cout<<z<<" "<<x<<" "<<y;
}


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

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef array<int, 3> tri;
typedef long double ld;

template <class T> istream& operator>>(istream& I, vector<T>& v) {for (T &e: v) I >> e; return I;}
template <class T> ostream& operator<<(ostream &O, const vector<T>& v) {for (const T &e: v) O << e << ' '; return O;}





void _main() {
        ll x, y; cin >> x >> y;
        int cnt = 0;
        while (x <= y) {
                cnt++;
                x *= 2;
        }

        cout << cnt << '\n';
}




signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//        freopen("input.txt", "r", stdin);
        int _t = 1;
//        cin >> _t;
        while (_t--) _main();
        return 0;
}


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

#define int long long 
#define MOD 1000000007



using namespace std;


signed main(){

	string N;
	
	cin >> N;
	int ans=0;
	
	for(char x:N){
		if(x=='2'){
			ans++;
		}
	
	}
	
	cout << ans << endl;
 	
 	return 0;
	

}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
const long long MOD = 1000000007;
using namespace std;
typedef long long ll;

map<ll, int> mp;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	int m = 0;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		if (m < a) {
			m = a;
			ans = a + b;
		}
	}
	cout << ans << endl;
 	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define REP(i, n) for(int i = 1; i < (int)(n); ++i)
using namespace std;

int main() {
    vector<int> a(3);
    rep(i, 3) cin >> a[i];
    sort(a.rbegin(), a.rend());
    cout << a[0] * 10 + a[1] + a[2] << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        long[] march = new long[5];
        
        String l;
        int i;
        while(n-- > 0){
            l = sc.nextLine();
            i = getInd(l.charAt(0));
            if(i != -1){
                march[i]++;
            }
        }
        
        
        long res = 0;
        for(i = 0; i < 3; i++){
            for(int j = i+1; j < 4; j++){
                for(int k = j+1; k < 5; k++)
                    res += march[i]* march[j]*march[k];
            }
        }
        
        System.out.println(res);
    }
    private static int getInd(char c){
        if(c == 'M')
            return 0;
        else if(c == 'A')
            return 1;
        else if(c == 'R')
            return 2;
        else if(c == 'C')
            return 3;
        else if(c == 'H')
            return 4;
        return -1;
    }
}

Measured memory_bytes: 91728
#include <iostream>
#include <cmath>
#include <utility>

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
#define mp make_pair
#define x first
#define y second

int main () {
	double r;
	cin>>r;
	cout<<2*r*acos(-1);



return 0;
}



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

int main()
{   
    int n;
  	cin >> n;
  
  	if(n%1000==0) cout << 0 << endl;
  	else cout << ((n/1000)+1) *1000 - n << endl;
   

    return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
  int N;
  string A, B, C;
  cin >> N >> A >> B >> C;
  int ans = 0;
  for (int i = 0; i < N; i++)
  {
    if (A[i] != B[i] && B[i] != C[i] && C[i] != A[i])
      ans += 2;
    else if (A[i] == B[i] && B[i] == C[i])
      ;
    else
      ans += 1;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int A, B, C, K;
    cin >> A >> B >> C >> K;

    if(A >= K) {
        cout << K << endl;
        return 0;
    }

    if((A+B) >= K) {
        cout << A << endl;
        return 0;
    }

    cout << A + (K-A-B)*-1 << endl;
    return 0;
}

Measured memory_bytes: 3636
// inputに入力データ全体が入る
function Main(input) {

	var tmp=input.split(" ");
	var h=tmp[0];
	var a=tmp[1];
	var count=0;
	for(;;){
    	if(h<=a*count){
           	break;
           }else{
           		count=count+1;
           }
           
    }
  	console.log('%d',count);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

#define int long long

signed main() {
    int n; 
    cin>>n;
    string s;
    cin>>s;
 
    int r = 0, g = 0, b = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'R'){
            r++;
        }
        if (s[i] == 'G'){
            g++;
        }
        if (s[i] == 'B'){
            b++;
        }
    }
 
    int sum = r*g*b;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (s[i] != s[j]) {
                if (2*j-i< n) {
                    if (s[2*j-i]!=s[j]&&s[2*j-i]!=s[i])
                        sum--;
                }
            }
        }
    }
 
    cout<<sum;
return 0;
}

Measured memory_bytes: 3648
#include "bits/stdc++.h"
using namespace std;
 
int main(void) {
	int n, a, b;
	cin >> n >> a >> b;

	int ans=0;

	for(int i=1;i<=n;i++) {
		int sum = 0;
		int j = i;
		
		sum += j%10;
		while(j>9) {
			j /= 10;
			sum += j%10;
		}
		if(a<=sum && sum<=b) ans += i;
	}

	cout << ans << endl;
}


Measured memory_bytes: 256
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef pair<int,int> pii;

const int N=100010;

int fa[N],deg[N],next0[4*N],b[4*N],head[N],tail[N];
map<pii,int> a;
queue<pii> q;

int find(int x)
{
    if (x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}

int main()
{
    int n,m=0;scanf("%d",&n);
    for (int i=1;i<n;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        if (x>y) swap(x,y);a[make_pair(x,y)]++;
        q.push(make_pair(x,y));deg[x]++;deg[y]++;
        b[++m]=y;if (!head[x]) head[x]=m; else next0[tail[x]]=m;tail[x]=m;
        b[++m]=x;if (!head[y]) head[y]=m; else next0[tail[y]]=m;tail[y]=m;
    }
    for (int i=1;i<n;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        if (x>y) swap(x,y);a[make_pair(x,y)]++;
        q.push(make_pair(x,y));deg[x]++;deg[y]++;
        b[++m]=y;if (!head[x]) head[x]=m; else next0[tail[x]]=m;tail[x]=m;
        b[++m]=x;if (!head[y]) head[y]=m; else next0[tail[y]]=m;tail[y]=m;
    }
    for (int i=1;i<=n;i++) fa[i]=i;
    for (int i=1;i<n;i++)
    {
        while (!q.empty())
        {
            pii t=q.front();
            int x=t.first,y=t.second;
            if (x>y) swap(x,y);
            if (a[make_pair(x,y)]!=2||find(x)==find(y)) {q.pop();continue;}
            if (deg[x]>deg[y]) swap(x,y);
            int p=head[x];
            while (p)
            {
                int u=find(b[p]),v=x;
                if (u>v) swap(u,v);
                a[make_pair(u,v)]--;
                u=find(b[p]);v=y;
                if (u>v) swap(u,v);
                a[make_pair(u,v)]++;
                q.push(make_pair(u,v));
                p=next0[p];
            }
            deg[y]+=deg[x];fa[x]=y;
            next0[tail[y]]=head[x];tail[y]=tail[x];
            break;
        }
        if (q.empty()) {puts("NO");return 0;}
    }
    puts("YES");
    return 0;
}


Measured memory_bytes: 27416
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
def s():
 print(*d(list(map(int,input().split()))))
 print(c)
if'__main__'==__name__:c=-int(input());s()


Measured memory_bytes: 61652
// Goods things are coming, just keep believing 
 
#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 FOR(i, x, n) for(ll i = x; i < n; i++) 
#define pb push_back
#define pf push_front
#define ll long long
#define hii cout << "hii" << endl
#define okay cout << "okay" << endl
// #define hey cout << "hey" << endl
#define pii pair<int, int>
#define pll pair<ll, ll>
// #define mpp make_pair
#define endl '\n'
#define ff first 
#define int long long
#define ss second
#define vi vector<int>
#define all(s) s.begin(), s.end()
#define si size()
 #define ld long double
#define INF 1000000000;
 
template <class T> ostream& operator << (ostream &os, const vector<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T> ostream& operator << (ostream &os, const set<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T, class S> ostream& operator << (ostream &os, const pair<T, S> &v) { os << v.first << ' ' << v.second; return os; }
template <class T, class S> ostream& operator << (ostream &os, const unordered_map<T, S> &v) { for (auto i : v) os << '(' << i.first << "=>" << i.second << ')' << ' '; return os; } 
 
 
 
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <class Arg1> void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << endl; }
    template <class Arg1, class... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args) {
        const char* sep = strchr(names + 1, ',');
        cerr.write(names, sep - names) << " : " << arg1 << "  ";
        __f(sep + 1, args...);
    }
#else
#define trace(...) 0
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#endif // ifndef ONLINE_JUDGE
 
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 
 
 
const int N = 2e5 + 5;
const int LG = 20;
const int mod = 1e9 + 7;

int arr[N];

int n, m;
int diff[N];
int pref[N];

void solve()
{
	int n;
	cin >> n;
	int ptr = 1;
	int len = 0;
	for(int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	for(int i = 0; i < n; i++)
	{
		if(arr[i] == ptr)
		{
			ptr++;
			len++;
		}
	}
	if(len == 0) cout << -1;
	else cout << n - len << endl;
}
 
int32_t main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

	int t = 1;
	// cin >> t;
	while(t--)
	{
		solve();
	}
}

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

int main(){
    int number;
    int sum = 0;
    
    while(1){
        cin >> number;
        if (number == 0){
            break;
        }
        
       
        int array[number][number];
        int lastColumn[number];
        int lastRow[number];
        int total=0;
        
        for(int i=0; i<number; i++){
            sum = 0;
            for(int j=0; j<number; j++){
                cin >> array[i][j];
                sum += array[i][j];
            }
            lastColumn[i] = sum;
        }
        
        for(int j=0; j<number; j++){
            sum = 0;
            for(int i=0; i<number; i++){
                sum += array[i][j];
            }
            lastRow[j] = sum;
            total +=sum;
        }
        
        for(int i=0; i<number; i++){
            for(int j=0; j<number; j++){
                printf("%5d", array[i][j]);
            }
            printf("%5d\n", lastColumn[i]);
        }
        
        for(int i=0; i<number; i++){
            printf("%5d", lastRow[i]);
         }
        printf("%5d\n", total);

    }
    
    return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define substr(s,f,t) (s.substr(f-1,t-f+1))
#define ALL(a) (a).begin(),(a).end()
#define Yes(hoge) cout<<((hoge)?"Yes":"No")<<endl;
#define YES(hoge) cout<<((hoge)?"YES":"NO")<<endl;
using namespace std;
struct Grid{ll x,y,t;};
struct Edge{ll to,cost;};
struct Graph{vector<vector<Edge>>E;int V;
  const ll Inf = llINF;const int MAX_V=201010;vector<ll>d;
  Graph(int n):E(n){d.resize(MAX_V);E.resize(n);V=n;}
  void init(){for(int i=0;i<MAX_V;i++)d[i]=Inf;}
  void add_edge(ll from,ll to,ll cost){E[from].pb({to,cost});}
};
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s,t;cin>>s>>t;
  int ruisa[s.size()+10]={};
  int ruisb[s.size()+10]={};
  int ruita[t.size()+10]={};
  int ruitb[t.size()+10]={};
  for(int i=1;i<=s.size();i++){
    if(s[i-1]=='A'){
      ruisa[i]=ruisa[i-1]+1;
      ruisb[i]=ruisb[i-1];
    }else{
      ruisa[i]=ruisa[i-1];
      ruisb[i]=ruisb[i-1]+1;
    }
  }
  for(int i=1;i<=t.size();i++){
    if(t[i-1]=='A'){
      ruita[i]=ruita[i-1]+1;
      ruitb[i]=ruitb[i-1];
    }else{
      ruita[i]=ruita[i-1];
      ruitb[i]=ruitb[i-1]+1;
    }
  }
  int q;cin>>q;
  for(int i=0;i<q;i++){
    int a,b,c,d;cin>>a>>b>>c>>d;
    int sa=ruisa[b]-ruisa[a-1];
    int sb=ruisb[b]-ruisb[a-1];
    int ta=ruita[d]-ruita[c-1];
    int tb=ruitb[d]-ruitb[c-1];
    if((sa+2*sb)%3==(ta+2*tb)%3){
      cout<<"YES"<<endl;
    }else
      cout<<"NO"<<endl;
  }
  return 0;
}

Measured memory_bytes: 2512
#include <iostream>
#include <iomanip>
#include <cstring>
#include <algorithm> 
#include <math.h>
#include <queue>
#include <functional>
#include <map>
#include <vector>
#include <string>
#include <set> 
using namespace std;

typedef long long ll;
typedef pair<ll, int> P;
typedef pair<pair<int, int>, int> PP;

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

const ll INF = 1e9+5;
const ll MAX = 510000;
const ll MOD = 1000000007;


int main(void) {
	int N; cin >> N;
	int h[100010];
	int ans = 0;
	for (int i = 0; i < N; i++) cin >> h[i]; h[N] = INF; //cout<<h[N]<<endl;

	for (int i = 0; i < N;) {
	    int pos = i;// cout<<pos<<endl;
	    while(pos<N){
	        if(h[pos]<h[pos+1]) break;
	        pos++;//cout<<pos<<endl;
	    }
	    
	    ans=max(ans,pos-i);
	    i = pos+1;
	}
	
	cout<<ans<<endl;
}


Measured memory_bytes: 640
//
//  main.cpp
//  comp
//
//  Created by Brenda Aurelie on 6/14/20.
//  Copyright © 2020 Brenda Aurelie. All rights reserved.
//

#include <iostream>
using namespace std;

int main() {
    int n,temp;
    cin >> n;
     int arr[2*n];
    for(int i=0;i<2*n;i++){
        cin >> arr[i];
    }
    
    
    for (int i=0;i<2*n;i++){
        for(int j=i+1;j<2*n;j++){
            if(arr[i]>arr[j]){
                temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }
    }
    
    int sum=0;
    
    for(int i=0;i<n;i++){

        sum += arr[i*2];
    
    }
    
    
    cout << sum << endl;
    
    return 0;
}


Measured memory_bytes: 256
let counting_sort a b k n =
  let c = Array.make (k + 1) 0 in
  Array.iter (fun e -> c.(e) <- c.(e) + 1) a;
  for i = 1 to k do
    c.(i) <- c.(i) + c.(i-1)
  done;
  for i = n - 1 downto 0 do
    b.(c.( a.(i) ) - 1) <- a.(i);
    c.( a.(i) ) <- c.( a.(i) ) - 1;
  done

let () =
  let n = read_int () in
  let a = Array.init n (fun _ -> Scanf.scanf "%d " (fun e -> e)) in
  let b = Array.make n 0 in
  counting_sort a b 10000 n;
  print_int b.(0);
  for i = 1 to n - 1 do
    print_string " "; print_int b.(i);
  done;
  print_newline ()

Measured memory_bytes: 36192
#include <stdio.h>
int n,m,i,j,k,t[16],c[16],p,d;
int main(void){
	for(*t=n=1;++i<16;)t[i]=n*=3;
	for(;scanf("%d%d",&n,&m),n;){
		for(k=3;k--;)
			for(scanf("%d",&i);i--;c[j]=k)scanf("%d",&j);
		for(p=j=k=0;k++<n;)
				j+=t[n-k]*abs(i=p-c[k]),p=i%2*2+p&3;
		j=fmin(j,t[n]+~j);
		printf("%d\n",j>m?-1:j);
	}
	return 0;
}

Measured memory_bytes: 0