akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		int n = Integer.parseInt(str);
		for (int i = 0; i < n; i++) {
			str = br.readLine();
			String[] dataset = str.split(" ");
			int[] balls = new int[10];
			List<Integer> A = new ArrayList<>();
			List<Integer> B = new ArrayList<>();
			int cntA = 0;
			int cntB = 0;
			B.add(0);
			boolean isAble = true;
			for (int j = 0; j < 10; j++) {
				balls[j] = Integer.parseInt(dataset[j]);
				if (j == 0)
					A.add(balls[j]);
				else {
					if (balls[j] < A.get(cntA) && balls[j] < B.get(cntB)) {
						isAble = false;
						break;
					} else if (balls[j] < A.get(cntA) && balls[j] > B.get(cntB)) {
						B.add(balls[j]);
						cntB++;
					} else if (balls[j] > A.get(cntA) && balls[j] < B.get(cntB)) {
						A.add(balls[j]);
						cntA++;
					} else {
						if (A.get(cntA) > B.get(cntB)) {
							A.add(balls[j]);
							cntA++;
						} else {
							B.add(balls[j]);
							cntB++;
						}
					}
				}
			}
			if (isAble)
				System.out.println("YES");
			else
				System.out.println("NO");
		}
	}
}

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

struct Steps{
	int min, max;
};

int main(){
	int n, k;
	while(std::cin >> n >> k, n){
		std::vector<int> cards;
		for(int i=0;i<k;i++){
			int card;
			std::cin >> card;
			cards.push_back(card);
		}

		std::sort(cards.begin(), cards.end());

		bool white = false;
		if(cards[0] == 0){
			white = true;
			cards.erase(cards.begin());
		}

		std::vector<Steps> sv;
		sv.push_back({cards[0], cards[0]});
		for(int i=1;i<cards.size();i++){
			int prev_c = cards[i-1];
			if(prev_c + 1 == cards[i]){//連続している
				sv[sv.size()-1].max = cards[i];
			}else{
				sv.push_back({cards[i], cards[i]});
			}
		}

		int res = 0;
		for(int i=0;i<sv.size();i++){
			Steps s = sv[i];
			res = std::max(res, s.max - s.min + 1);
		}

		if(white){
			for(int i=0;i<sv.size();i++){
				Steps s = sv[i];
				//左に入れる
				if(s.min != 1)res = std::max(res, s.max - s.min + 1);
				//右に入れる
				if(s.max != n)res = std::max(res, s.max - s.min + 1);
			}
		
			for(int i=0;i+1<sv.size();i++){//間に入れる
				if(sv[i].max + 2 == sv[i+1].min){
					res = std::max(res, sv[i+1].max - sv[i].min + 1);
				}
			}
		}

		std::cout << res << std::endl;
	}
}

Measured memory_bytes: 1728
n, k = map(int, input().split())
p = list(map(int, input().split()))


def calc(value):
    return value * (value + 1) / (2 * value)


max_value = 0
for i in range(k):
    max_value += calc(p[i])

cur = max_value
for l in range(k, n):
    cur += (calc(p[l]) - calc(p[l-k]))
    max_value = max(max_value, cur)
print(max_value)


Measured memory_bytes: 25060
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll linf = (1ll << 61);
const int inf = 1001001001;
const int mod = 1000000007;

class UnionFind {
public:
	//親の番号を格納する。親だった場合は-(その集合のサイズ)
	vector<int> Parent;
	//作るときはParentの値を全て-1にする
	//こうするとすべてバラバラになる
	UnionFind(int N) {
		Parent = vector<int>(N, -1);
	}
	//Aがどのグループに属しているか調べる
	int root(int A) {
		if (Parent[A] < 0) return A;
		return Parent[A] = root(Parent[A]);
	}
	//自分のいるグループの頂点数を調べる
	int size(int A) {
		return -Parent[root(A)];//親をとってきたい
	}
	//AとBをくっつける
	bool connect(int A, int B) {
		//AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
		A = root(A);
		B = root(B);
		if (A == B) {
			//すでにくっついているからくっつけない
			return false;
		}
		//大きい方(A)に小さいほう(B)をくっつけたい
		//大小が逆だったらひっくり返しちゃう
		if (size(A) < size(B)) swap(A, B);
		//Aのサイズを更新する
		Parent[A] += Parent[B];
		//Bの親をAに変更する
		Parent[B] = A;

		return true;
	}
	//AとBが同じグループにいるか
	bool same(int A, int B) { return root(A) == root(B); }
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<P> p(m);
	rep(i, m) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		p[i] = P(a, b);
	}
	UnionFind Uni(n);
	vector<ll> rec(m);
	ll sum = 0;
	for (int i = m - 1; i >= 0; --i) {
		int a = p[i].first, b = p[i].second;
		if (!Uni.same(a, b)) {
			ll tmp = 0;
			tmp += Uni.size(a);
			tmp *= Uni.size(b);
			rec[i] = sum;
			Uni.connect(a, b);
			sum += tmp;
		}
		else rec[i] = sum;
	}
	//reverse(rec.begin(), rec.end());
	rep(i, m) printf("%lld\n", sum - rec[i]);
	return 0;
}


Measured memory_bytes: 3328
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
typedef unsigned long long int ull;
typedef long long lint;

int main(void){
    lint N;
    cin >> N;
    lint Ccount[110000]={};
    lint A[N];
    lint ans=1;
    rep(i,N) cin >> A[i];
    rep(i,N){
        Ccount[A[i]]++;
        if(A[i]!=0){
            ans=ans*(Ccount[A[i]-1]-Ccount[A[i]]+1)%MOD;
        }
        if(Ccount[A[i]]>3) ans=0;
        if(Ccount[A[i]]>Ccount[A[i]-1]) ans=0;   
    }
    if(Ccount[0]==1) ans=(ans*3)%MOD;
    if(Ccount[0]==2) ans=(ans*6)%MOD;
    if(Ccount[0]==3) ans=(ans*6)%MOD;
    cout << ans << endl;
}

Measured memory_bytes: 1920
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a=scanner.nextInt();
        int b=scanner.nextInt();
        int c=scanner.nextInt();
        int d=scanner.nextInt();
        if ((a+b>c+d)&&!(a+b==c+d)){
            System.out.println("Left");
        }else if (a+b==c+d){
            System.out.println("Balanced");
        }else {
            System.out.println("Right");
        }
    }
}

Measured memory_bytes: 21716
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int count = 1;
		while(true) {
		    int x = sc.nextInt();
		    if(x == 0) break;

		    System.out.println("Case " + count + ": " + x);
		    count++;
		}

	    sc.close();

	}

}


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

Measured memory_bytes: 3576
import scala.io.{StdIn => in}

object Main extends App {
  val a = in.readInt
  val b = in.readInt
  val c = in.readInt
  val x = in.readInt

  var res = 0
  for {
    i <- 0 to a
    j <- 0 to b
    k <- 0 to c
  } if((500 * i + 100 * j + 50 * k) == x) res += 1

  val ans = res
  println(ans)
}

Measured memory_bytes: 26812
#include <iostream>
#include<vector>
#include<cmath>
using namespace std;

int N;
int A[3][1000];


int main(){
    cin>>N;
    vector<vector<int > > dp(3,vector<int>(N+10,0));
    for(int i=1;i<=2;i++){
        for(int j=1;j<=N;j++){
            cin>>A[i][j];
            dp[i][j]=A[i][j];
        }
    }
    

    for(int i=1;i<=2;i++){
        for(int j=1;j<=N;j++){
            if(i==1) dp[i][j]+=dp[i][j-1];
            else dp[i][j]+=max(dp[i-1][j],dp[i][j-1]);
        }
    }

    cout<<dp[2][N]<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define pr pair<int, int>
#define x first
#define y second
using namespace std;

template<typename T>
void read(T& n){
	char ch; int sign = 1;
	while (!isdigit(ch = getchar())) if (ch == '-') sign = -1;
	n = ch - '0';
	while (isdigit(ch = getchar())) n = n * 10 + ch - '0';
	n *= sign;
}
typedef long long ll;
const int INF = 1e9 + 7;
const int N = 122;
int n;
ll a[N];

int main(){
	read(n);
	rep(i, 1, n) read(a[i]);
	ll tag = 0;
	for (; ;){
		ll cnt = 0;
		rep(i, 1, n){
			ll cur = a[i] + tag;
			cnt += a[i] / n;
			rep(j, 1, n) if (i != j) a[j] += a[i] / n;
			a[i] = a[i] % n;
		}
		if (!cnt) break;
		tag += cnt;
	}
	printf("%lld\n", tag);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef signed long long int ll;
#define INF (1<<29)
int l;
ll a[200005];
//ll a;
ll dp[200005][5]={0};
int main(){
    cin>>l;
    for(int i=0;i<l;i++) cin>>a[i];
    
    /*for(int i=0;i<5;i++){
        for(int j=0;j<l+2;j++){
            dp[j][i]=INF;
        }
    }*/
    
    //for(int i=0;i<5;i++) dp[0][i]=0;
    
    for(int i=1;i<=l;i++){
        //cin>>a[i-1];
        int b=(a[i-1]==0?2:(a[i-1]%2));
        
        int c=1-(a[i-1]%2);
        
        dp[i][0]=dp[i-1][0]+a[i-1];
        
        dp[i][1]=min(dp[i][0],dp[i-1][1]+b);
        
        dp[i][2]=min(dp[i][1],dp[i-1][2]+c);
        
        dp[i][3]=min(dp[i][2],dp[i-1][3]+b);
        
        dp[i][4]=min(dp[i][3],dp[i-1][4]+a[i-1]);
        
    }
    cout<<dp[l][4]<<endl;
    return 0;
    
}


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

int main()
{
    int a, b;
    double tmp2, tmp3=0.0;
    cin >> a >> b;
    for (int i = 1; i <= a;i++){
        int tmp = b, now=i;
        tmp2 = 1.0 / a;
        while(now<b){
            tmp2 /= 2;
            now*=2;
        }
        tmp3 += tmp2;

    }
    std::cout << std::fixed;
    cout << setprecision(12)<< tmp3 << endl;
}


Measured memory_bytes: 256
N = int(input())
SP = [input().split() for i in range(N)]
SP = [[sp[0], int(sp[1]), i+1]for i, sp in enumerate(SP)]
SP = sorted(SP, reverse=True, key=lambda x: x[1])
SP = sorted(SP, key=lambda x: x[0])
for s, p, i in SP:
    print(i)


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

int main(){
  int n;
  cin >> n;
  if(n>=1&&n<=9) cout << n << endl;
  else if(n>=10&&n<=99) cout << 9 << endl;
  else if(n>=100&&n<=999) cout << 9+n-99 << endl;
  else if(n>=1000&&n<=9999) cout << 9+999-99<<endl;
  else if(n>=10000&&n<=99999) cout << 9+999+n-9999-99<< endl;
  else if(n==100000) cout << 9 + 999 + 99999 - 99 - 9999 << endl;
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);++i)
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; }
typedef long long ll;
const int INF = 1e9;


int N;
string S;


int main(){
    cin >> N >> S;
    int e = 0, w = 0;
    REP(i,N){
        if(S[i]=='E') ++e;
    }

    int ans = INF;
    REP(i,N){
        if(S[i]=='E'){
            --e;
            ans = min(ans,w + e);
        } else {
            ans = min(ans,w + e);
            ++w;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 900
# Python template 
from collections import defaultdict 
import sys
import math 

def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()

sys.setrecursionlimit(10**6) 
g = defaultdict(set)
(n,m) = get_ints()
visited = [0]*n 


def dfs(i,l,par):
    global visited
    visited[i] = True
    l.append(i)
    for j in g[i]:
        if j!=par and not visited[j]:
            dfs(j,l,i)

for i in range(m):
    (u,v) = get_ints()
    g[u-1].add(v-1)
    g[v-1].add(u-1)

ans = 0
for i in range(n):
    if not visited[i]:
        l = []
        dfs(i,l,-1)
        ans = max(ans,len(l))
        
print(ans)

Measured memory_bytes: 268276
import sys 
import collections as cl


N=int(input())
A=list(map(int,sys.stdin.readline().split()))
c=cl.Counter(A)
NumberTupleList=c.most_common()
NumberList=[x[1] for x in NumberTupleList[::-1]]
LengthOfNumberList=len(NumberList)
FormulaList=[0 for i in range(N)]
flag=0
S=sum(NumberList)
for x in range(1,N+1):
    while flag<LengthOfNumberList and NumberList[flag]<=x:
        flag+=1
    if flag<LengthOfNumberList:
        FormulaList[x-1]=(sum(NumberList[:flag])+x*(LengthOfNumberList-flag))/x
    else:
        FormulaList[x-1]=S/x
pin=N-1
for K in range(1,N+1):
    while pin>=0 and K>FormulaList[pin]:
        pin-=1
    print(pin+1)



Measured memory_bytes: 62316
import sys
input = sys.stdin.readline

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().split()))

def gcd(a: int, b: int):
	while b: a, b = b, a%b
	return a

def lcm(a: int, b: int):
	return a * b // gcd(a, b)

def main():
	D = int(input())  # days
	vC = [0,]+linput()     # decrine rate
	
	#sumC = sum(vC)
	
	# satis (d,i)
	mS = [[0,]+linput() for _ in [0,]*D]
	
	## sample output
	#vT = [int(input()) for _ in [0,]*D] ## for p.B

	vL = [-1,]*(26+1)   # last day of Type
	
	#day = -1
	res = 0      # manzoku
	vR = []
	vT = []
	rapp = vR.append
	tapp = vT.append
	
	for d in range(D): #[0,364] day
		#t = vT[d] ## sample output
		bestT = 1
		candiR = []
		vS = mS[d]
		for t in range(1,27):  # [1,26] type
			candir = 0
			Sdt = vS[t]
			candir += Sdt
			
			vltmp = vL[t]
			vL[t] = d
			C = sum(c*(d-l) for c,l in zip(vC,vL))
			candir -= C
			candiR.append(candir)
			
			vL[t] = vltmp
		
		bestR = max(candiR)
		bestT = candiR.index(bestR) + 1
		res += bestR
		rapp(res)
		tapp(bestT)
	
	#sT = "No Yes".split()
	#print(sT[res])
	#print(res)
	print(*vT, sep='\n')
	print(*vR, file=sys.stderr)
	print(sum(vR), file=sys.stderr)

if __name__ == "__main__":
	main()


Measured memory_bytes: 68992
#include <iostream>
#include <string>
#include <map>
#include <cmath>
#include <vector>
#include<cstdio>
#include <iterator>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <stack>
#include <queue>
using namespace std;
typedef long long ll;
int main() {
	int H, W;
	cin >> H >> W;
	vector<string> S(H);
	for (int a = 0; a < H; a++)
	{
		cin >> S[a];
	}

	for (int a = 0; a < H; a++)
	{
		cout << S[a] << endl;
		cout << S[a] << endl;
	}

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;

signed main(){
    int n;
    cin >> n;
    vector<int> G[n];
    int a,b;
    REP(i,n - 1){
        cin >> a >> b;
        a--;
        b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int dist_f[n];
	REP(i,n){
        dist_f[i] = INF;
    }
	queue<int> que;
	que.push(0);
	dist_f[0] = 0;
	while(que.size()){
		int u = que.front();
		que.pop();
		for(auto v : G[u]){
            if(dist_f[v] == INF){
                dist_f[v] = dist_f[u] + 1;
                que.push(v);
            }
        }
	}
    int dist_s[n];
	REP(i,n){
        dist_s[i] = INF;
    }
	que.push(n - 1);
	dist_s[n - 1] = 0;
	while(que.size()){
		int u = que.front();
		que.pop();
		for(auto v : G[u]){
            if(dist_s[v] == INF){
                dist_s[v] = dist_s[u] + 1;
                que.push(v);
            }
        }
	}
    int black = 0, white = 0;
    REP(i,n){
        if(dist_f[i] <= dist_s[i]){
            black++;
        }else{
            white++;
        }
    }
    if(black > white){
        cout << "Fennec" << endl;
    }else{
        cout << "Snuke" << endl;
    }
    return 0;
}

Measured memory_bytes: 6528
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>
#include<map>
#include<cstdlib>
#include<cmath>
using namespace std;
using ll =long long;
int main() {
	ll N, Y;

	cin >> N >> Y;

	ll W=Y / 10000;
	//5sennと1000
	ll V1 = (Y % 5000)/1000+Y%10000/5000;
	ll V2 = Y % 10000 / 1000;
	
	for (ll i = 0; i <= W; i++) {
		for (ll j = 0; j <= W-i; j++) {
			for (ll k = 0; k <= W-i-j; k++) {

				if (10 * i + 6 * j + 2 * k + (W - i - j - k)+V1 == N) {

					cout << (W - i - j - k) <<" "<<2 * k + j + Y % 10000 / 5000<<" "<< 10 * i + 5 * j+(Y % 5000) / 1000  ;
					return 0;
				}
				

			}


		}


	}
	for (ll i = 0; i <= W ; i++) {
		for (ll j = 0; j <= W  - i; j++) {
			for (ll k = 0; k <= W  - i - j; k++) {

				if (10 * i + 6 * j + 2 * k + (W  - i - j - k)+V2 == N) {

					cout << (W  - i - j - k) << " " << 2 * k + j  << " " << 10 * i + 5 * j + (Y % 10000) / 1000;
					return 0;
				}


			}


		}


	}

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


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 * @throws NumberFormatException 
	 */
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		PrimeNumberGenerator pg = new PrimeNumberGenerator();
		while(true){
			int n = Integer.parseInt(br.readLine());
			
			if(n == 0){
				break;
			}
			
			if(pg.isPrime(n)){
				System.out.println(0);
				continue;
			}
			
			int begin = -1;
			int end = -1;
			for(int i = n - 1; i >= 0; i--){
				if(pg.isPrime(i)){
					begin = i;
					break;
				}
			}
			
			for(int i = n + 1; i < 2000000 ; i++){
				if(pg.isPrime(i)){
					end = i;
					break;
				}
			}
			
			System.out.println(end - begin);
		}
	}

}

class PrimeNumberGenerator {
    private final int N = 2000000;
    private boolean[] isPrime= new boolean[N + 1];
 
    public PrimeNumberGenerator() {
        Arrays.fill(isPrime, true);
 
        isPrime[0] = false;
        isPrime[1] = false;
 
        int limit = (int)Math.sqrt(N);
        for(int i = 2; i <= limit ; i++){
 
            if(isPrime[i] == false){
                continue;
            }
 
            for(int j = i * 2; j <= N; j += i){
                isPrime[j] = false;
            }
        }
    }
 
    public boolean isPrime(int index){
        return isPrime[index];
    }
}

Measured memory_bytes: 27932
#include <iostream>
#include <iomanip>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>
#include <cstdint>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

constexpr ll inf = INT64_MAX / 4;

int p[200000],n,k;

int main() {
    cin >> n >> k;
    for(int i = 0;i < n;i++) cin >> p[i];
    int s = 0;
    for(int i = 0;i < k;i++) s += p[i];
    int r = s;
    for(int i = 0;i +k<n;i++) {
        s -= p[i];
        s += p[i+k];
        r = max(s,r);
    }
    cout <<setprecision(20)<< ((double)(r+k))/2 << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <deque>
#include <string>
#include <stack>
#include <unordered_set>
#include <cmath>
#define endl '\n'
#define ll unsigned long long
//#define mod 1000000007
#define NCONS 200001

using namespace std;

int four, r;

int main(void)
{
	cin.tie(NULL); ios_base::sync_with_stdio(false);
	int N; cin >> N;
	auto acc = new int[N]();
	for (int i = 0; i < N; i++)
	{
		cin >> acc[i];
		if (acc[i] % 4 == 0)
			four += 1;
		else if (acc[i] % 2 != 0)
			r += 1;

	}
	if (N % 2 != 0)
		r -= 1;
	if (four >= r)
		cout << "Yes";
	else
		cout << "No";

	return 0;
}

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


void solve(long long N){
    cout<<(ll)pow(N,3)<<endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    std::cout<<std::fixed<<std::setprecision(10);//誤差小数10桁まで
    long long N;
    scanf("%lld",&N);
    solve(N);
    return 0;
}


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

const int MAXN = 21;
const int MAXL = (1 << 21 ) + 2;
const int MOD = 1e9 + 7;

int dp[MAXN][MAXL],mascara[MAXN],N;

int solve(int pos,int bitmask){

	if(pos == N) return (__builtin_popcount(bitmask) == N);
	if(dp[pos][bitmask] != -1) return dp[pos][bitmask];

	int tot = 0;
	for(int i = 0;i<N;i++){
		if(!(bitmask & (1 << i)) && ((1 << i) & mascara[pos])){
			tot = (tot + solve(pos+1, bitmask | (1 << i) )) % MOD;
		}
	}

	return dp[pos][bitmask] = tot;

}

int main(){

	memset(dp,-1,sizeof(dp));
	cin >> N;
	for(int i = 0;i<N;i++){
		for(int j = 0;j<N;j++){
			int x;
			cin >> x;
			if(x) mascara[i] |= (1 << j);
		}
	}
	cout << solve(0,0) << endl;

	return 0;

}

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

using namespace std;

const int N = 500100;

int dp[N];

int main() {
	string s;
	cin >> s;
	
	int n = s.size();
	
	for (int i = 0; i < n; ++i) {
		if(s[i] == '<') dp[i+1] = max(dp[i+1], dp[i] + 1);
		else dp[i+1] = 0;
	}
	for (int i = n-1; i >= 0; --i) {
		if(s[i] == '>') dp[i] = max(dp[i], dp[i+1] + 1);
		else dp[i] = max(dp[i],0);	
	}
	/*for (int i = 0; i <= n; ++i) {
		if(i!=0) cout << " " << s[i-1] << " ";
		cout << dp[i];
		
	}
	cout << endl;
	*/
	long long ans = 0;
	
	
	
	for (int i = 0; i <= n; ++i) {
		ans += dp[i];
	}
	
	cout << ans << endl;
	
}

Measured memory_bytes: 2820
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int N=1e5+5;

long long dis[N];
int hi[N],dp[N][20];
int n;
vector< pair<int,int> > adj[N];

void dfs(int node,int pa)
{
	hi[node]=hi[pa]+1;
	dp[node][0]=pa;
	for(int i=1;i<20;i++)
		dp[node][i]=dp[dp[node][i-1]][i-1];
	for(auto i:adj[node])
	{
		if(i.F==pa) continue;
		dis[i.F]=dis[node]+i.S;
		dfs(i.F,node);
	}
}

int lca(int x,int y)
{
	if(hi[x]<hi[y]) swap(x,y);
	for(int i=19;i>=0;i--)
	{
		if(hi[x]-(1<<i) >=hi[y])
			x=dp[x][i];
	}
	if(x==y) return x;
	for(int i=19;i>=0;i--)
	{
		if(dp[x][i]!=dp[y][i])
		{
			x=dp[x][i]; y=dp[y][i];
		}
	}
	return dp[x][0];
}

long long dist(int a,int b)
{
	//cout << a << " " << b << " " << lca(a,b) << endl;
	return dis[a]+dis[b]-2*dis[lca(a,b)];
}

int main()
{
	cin >> n;
	for(int i=0;i<n-1;i++)
	{
		int a,b,c;
		cin >> a >> b >> c;
		adj[a].push_back({b,c});
		adj[b].push_back({a,c});
	}
	dfs(1,0);
	int q,k;
	cin >> q >> k;
	while(q--)
	{
		int a,b;
		cin >> a >> b;
		cout << dist(a,k) + dist(k,b) << endl;
	}
}

Measured memory_bytes: 20992
#include <stdio.h>

int f[45];
void makeFibonacci(void);
int n,i;

int main(){

  for(i=0;i<=44;i++){
    f[i]=-1;
  }
  scanf("%d",&n);
  makeFibonacci();
  printf("%d\n",f[n]);
    
  return 0;
}

void makeFibonacci(){
  f[0]=1;
  f[1]=1;
  for(i=2;i<=n;i++){
    f[i]=f[i-2]+f[i-1];
  }
}


Measured memory_bytes: 2056
package main

import (
	"bufio"
	"fmt"
	"log"
	"math"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)
var buff []byte

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(buff, bufio.MaxScanTokenSize*1024)
	log.SetFlags(log.Lshortfile)
	var p []int = []int{1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51}
	k := nextInt()
	fmt.Println(p[k-1])
}

func nextString() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

var dy = []int{0, 1, 0, -1}
var dx = []int{1, 0, -1, 0}
var MAX = math.MaxInt32

func pow(a, b int) int {
	return int(math.Pow(float64(a), float64(b)))
}

func lcm(a, b int) int {
	return a * b / gcd(a, b)
}
func gcd(a, b int) int {
	if a < b {
		a, b = b, a
	}
	for b != 0 {
		a, b = b, a%b
	}
	return a
}
func max(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r < a[i] {
			r = a[i]
		}
	}
	return r
}
func min(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r > a[i] {
			r = a[i]
		}
	}
	return r
}
func sum(a []int) (r int) {
	for i := range a {
		r += a[i]
	}
	return r
}
func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

type Pair struct {
	a, b int
}

type Pairs []Pair

func (p Pairs) Len() int {
	return len(p)
}
func (p Pairs) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

func (p Pairs) Less(i, j int) bool {
	if p[i].a == p[j].a {
		return p[i].b < p[j].b
	}
	return p[i].a < p[j].a
}


Measured memory_bytes: 640
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <sstream>
#include <string>
#include <cstdio>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cstring>
#include <tuple>
#include <utility>
#include <list>
#include <cmath>
#include <unordered_map>

using namespace std;

typedef long long LL;
typedef vector<int> Array;
typedef pair<int, int> P;

const int INF = 1 << 29;
const LL MOD = 100000;
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define all(c) (c).begin(), (c).end()

struct edge{ int to, cost; edge(int t, int c) :to(t), cost(c){} };

int main()
{
	//while (cin >> n)
	stringstream ss;
	//ss << "result" << i + 1 << ".txt";
	//FILE* fp_out = freopen(ss.str().c_str(), "w", stdout);

	int n, m;
	while (cin >> n >> m && n)
	{
		vector<vector<int>> times(m, vector<int>(m, INF));
		vector<vector<int>> costs(m, vector<int>(m, INF));
		rep(i, n)
		{
			int a, b, c, t;
			cin >> a >> b >> c >> t;
			a--; b--;
			costs[a][b] = costs[b][a] = c;
			times[a][b] = times[b][a] = t;
		}

		rep(k, m) rep(i, m) rep(j, m)
		{
			costs[i][j] = min(costs[i][j], costs[i][k] + costs[k][j]);
			times[i][j] = min(times[i][j], times[i][k] + times[k][j]);
		}

		int k; cin >> k;
		rep(i, k)
		{
			int p, q, r; cin >> p >> q >> r;
			p--; q--;
			cout << (r ? times[p][q] : costs[p][q]) << endl;
		}
	}

	return 0;
}

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

#define step(i, s, n, d) for(int i=s; i<n; i+=d)
#define FOR(i,s,n) step(i,s,n,1)
#define rep(i,n) FOR(i,0,n)
#define gets(x) x; cin >> x;
#define puts(x) x; cout << x << endl;
#define list_input(x, n) x[n]; rep(i,n){ gets(x[i]);}
#define ll long long

int main(){
  int a, b, c, x, now, result = 0;
  cin >> a >> b >> c >> x;
  rep(i, a+1){
    rep(j ,b+1){
      rep(k, c+1){
        now = (i*500)+(j*100)+(k*50);
        if (now == x) result +=1;
      }
    }
  }
  puts(result)
}


Measured memory_bytes: 256
def partition(A, p, r, key=lambda x: x):
    x = key(A[r])
    i = p - 1

    for j in range(p, r):
        if key(A[j]) <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i + 1


def quick_sort(A, p, r, key=lambda x: x):
    if p < r:
        q = partition(A, p, r, key=key)
        quick_sort(A, p, q - 1, key=key)
        quick_sort(A, q + 1, r, key=key)


if __name__ == '__main__':
    n = int(input())
    A = []
    for _ in range(n):
        egara, number = input().split()
        A.append((egara, int(number)))
    
    stable_sorted = sorted(A, key=lambda x: x[1])
    quick_sort(A, 0, n - 1, key=lambda x: x[1])

    if stable_sorted == A:
        print('Stable')
    else:
        print('Not stable')
    
    for egara, number in A:
        print(egara, number)


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

int N, A, B;

int main(){
    cin >> N >> A >> B;

    int diff = B - A;
    if(diff % 2 != 0) cout << "Borys";
    else if(diff % 2 == 0) cout << "Alice";
    else cout << "Draw";

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100000
#define LL long long int

int N, M;
LL up[MAXN + 3], down[MAXN + 3], answer[MAXN + 3], prefix[MAXN + 3], suffix[MAXN + 3];
vector<int> adj[MAXN + 3], children[MAXN + 3];

void fillChildren(int prev, int u) {
    for (int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if (v != prev) {
            children[u].push_back(v);
            fillChildren(u, v);
        }
    }
}

void fillDown(int prev, int u) {
    down[u] = 1;
    for (int i = 0; i < children[u].size(); i++) {
        int v = children[u][i];

        fillDown(u, v);

        down[u] *= (1 + down[v]);
        down[u] %= M;
    }
}

void fillUp(int prev, int u) {
    if (children[u].size() > 0) {
        int childrenCount = children[u].size();
        
        prefix[0] = (1 + down[children[u][0]]);
        for (int i = 1; i < children[u].size(); i++) {
            prefix[i] = prefix[i - 1] * (1 + down[children[u][i]]);
            prefix[i] %= M;
        }

        suffix[childrenCount - 1] = (1 + down[children[u][childrenCount - 1]]);
        for (int i = childrenCount - 2; i >= 0; i--) {
            suffix[i] = suffix[i + 1] * (1 + down[children[u][i]]);
            suffix[i] %= M;
        }

        for (int i = 0; i < childrenCount; i++) {
            int v = children[u][i];

            LL pref = (i == 0 ? 1 : prefix[i - 1]);
            LL suf = (i == childrenCount - 1 ? 1 : suffix[i + 1]);
            
            up[v] = (pref * suf)%M;
            up[v] *= (1 + up[u]);
            up[v] %= M;
        }

        for (int i = 0; i < childrenCount; i++) {
            int v = children[u][i];
            fillUp(u, v);
        }
    }
}

void fillAnswer() {
    for (int i = 1; i <= N; i++) {
        answer[i] = down[i] * (1 + up[i]);
        answer[i] %= M;
    }
}

int main() {
    cin >> N >> M;
    for (int i = 1; i < N; i++) {
        int x, y;

        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    fillChildren(1, 1);
    fillDown(1, 1);

    up[1] = 0;
    fillUp(1, 1);

    fillAnswer();

    for (int i = 1; i <= N; i++)
        cout << answer[i] << endl;
}


Measured memory_bytes: 21248
#include <stdio.h> 
 
 
 int main(){ 
     int x, y; 
     while(1){ 
         scanf("%d %d", &x, &y); 
         if(x==0 && y==0)break; 
         if(x<y){ 
             printf("%d %d\n", x, y); 
         }else{ 
             printf("%d %d\n", y, x); 
         } 
     } 
     return 0; 
 } 



Measured memory_bytes: 2144
#include <iostream>
#include <stdlib.h>
#include <stdio.h>      /* printf */
#include <math.h>       /* pow */
#include <vector>
#include <algorithm>
#include <string>
#include <set>

typedef std::string chaine;
typedef std::set<chaine> dic;
typedef dic::iterator iterateur;

int main(void){

    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    
    int num;
    std::cin >> num;
    
    dic list;
    iterateur it;

    for(int i = 0; i < num; i++){
        chaine value;
        std::cin >> value;
 
        chaine a;
        std::cin >> a;
        
        if(value=="insert") {    
            list.insert(a);
        } else if (value=="find") {
            if(list.find(a) != list.end()){
                std::cout<<"yes"<<std::endl;
            } else {
                std::cout<<"no"<<std::endl;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 27056
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include<bits/stdc++.h>
#define ll long long
using namespace std;

int root(int arr[],int i){
    while(arr[i]!=i){
         arr[i]=arr[arr[i]];
        i=arr[i];
    }
    return i;
}
void Union(int arr[],int Size[],int a,int b){
int rootA=root(arr,a);
int rootB=root(arr,b);
if(Size[rootA]<Size[rootB]){
    arr[rootA]=arr[rootB];
    Size[rootB]+=Size[rootA];
}else{
arr[rootB]=arr[rootA];
Size[rootA]+=Size[rootB];
}
}
bool findRoot(int a,int b,int arr[]){
 if(root(arr,a)==root(arr,b))return true;
 else return false;
}
 vector<vector<int> >adj(105);
bool nCyc=false;
/*void dijkstra(int v,long long dis[]){
dis[v]=0;
multiset<pair<int,int> >s;
s.insert({0,v});
while(!s.empty()){
    pair<int,int>p= *s.begin();
    s.erase(s.begin());
    int x=p.second;
  if(vis[x])continue;
    vis[x]=1;
    for(int i=0;i<adj[x].size();i++){
        int e=adj[x][i].first,w=adj[x][i].second;
      //  cout<<dis[e]<<" "<<dis[x]+w<<endl;
        if(dis[e]>dis[x]+w){
            dis[e]=dis[x]+w;
            s.insert(make_pair(dis[e],e));
        }
    }
}
}*/
/*void bfs(int s){
    queue<int>q;
    q.push(s);
    while(!q.empty()){
        int v=q.front();
        q.pop();
        for(int i=0;i<adj[v].size();i++){
            if(!vis[adj[v][i]]){
                 q.push(adj[v][i]);
                 vis[adj[v][i]]=1;
            }
        }
    }
}*/
int vis[55][55];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
/*bool isVal(int i,int j){
      if(i<0 || j<0 || j>=m || i>=n)return false;
      return true;
}*/
/*void dfs(int i,int j) {

    if(!isVal(i,j) || vis[i][j] || arr[i][j]=='#')return;
      vis[i][j]=1;
	  if(arr[i][j]=='G'){
	  check++;
	  }
	  if(arr[i][j]=='B'){
        b=1;
        return;
	  }
	for(int k=0;k<4;k++){
     int pos1=i+dx[k],pos2=j+dy[k];
   //  cout<<pos1<<" "<<pos2<<endl;
     if( isVal(pos1,pos2) && (arr[pos1][pos2]=='#'))continue;
               dfs(pos1,pos2);
	}
}
void dfs2(int i,int j){
 if(isVal(i,j)==false || arr[i][j]!='.')return;
  arr[i][j]='#';
}*/
/*
double prim(int x){
    priority_queue<pair<double,int>,vector<pair<double,int> >,greater<pair<double,int> > >q;
    double min_cost=0.0;
    pair<double,int>p;
     q.push(make_pair(0.0,x));
     while(!q.empty()){
      p=q.top();
      q.pop();
      x=p.second;
      if(vis[x])continue;
      min_cost+=p.first;
      vis[x]=1;
      for(int i=0;i<adj[x].size();i++){
         int y=adj[x][i].second;
         if(!vis[y]){
            q.push(adj[x][i]);
        }
      }
     }
     return min_cost;
}*/
int n,arr[100005],dp[100005],ans=0;
int solve(int i){
    if(i==n-1)return 0;
    if(dp[i]!=-1)return dp[i];
    int ret=solve(i+1)+abs(arr[i]-arr[i+1]);
    if(i+2<n)ret = min(ret,solve(i+2)+abs(arr[i]-arr[i+2]));
    return dp[i]=ret;
}
int freq[1000005],check[1000005];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)cin>>arr[i];
    memset(dp,-1,sizeof dp);
    cout<<solve(0);
return 0;
}


Measured memory_bytes: 9068
#include <iostream>
#include <math.h>
//#include <numeric>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <tuple>

using namespace std;
#define n_max 100000

#define rep(i,n) for(int i = 0; i < n; i++)
#define rep2(i,a,n) for(int i = a; i < n; i++)
#define in(a) cin >> a
#define out(a) cout << a << endl
typedef long long ll;
typedef pair<ll, ll> PI;

int main() {

    int n; cin >> n;
    vector<ll> x(n), y(n), h(n);

    rep(i,n){
        cin >> x[i] >> y[i] >> h[i];
    }
    for(ll j = 0; j <= 100; j++) {
        for(ll k = 0; k <= 100; k++) {
            ll H = -1;
            rep(i,n) {
                if(h[i] > 0) {
                    ll tmp = h[i] + abs(x[i] - j) + abs(y[i] - k);
                    if(H == -1) {
                        H = tmp; 
                    } else {
                        if(H != tmp) { 
                            H = -2;
                            break;
                        }
                    }
                }
            }
            if(H == -2) { continue; }

            rep(i,n) {
                if(h[i] == 0) {
                    ll tmp = abs(x[i] - j) + abs(y[i] - k);
                    if(tmp < H) { 
                        H = -2;
                        break;
                    }
                }
            }
            if(H == -2) { continue; }

            cout << j << " " << k << " " << H << endl; 
            return 0;
        }
    }
    return 0;
}


Measured memory_bytes: 256
//↓template↓

#include "bits/stdc++.h"
using namespace std;
#define Would
#define you
#define all(n)  n.begin(),n.end()
const long long INF = 1e18;
const long long MOD = 1e9 + 7;
const double pi = acos(-1);
const int SIZE = 1 << 17;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, alp[30];
long long fac[200005], finv[200005], inv[200005];
vector<long long>dij;
struct edge { long long to, cost; };
vector<vector<edge> >G;

long long mod_pow(long long a, long long b) {
	long long res = 1, mul = a;
	for (int i = 0; i < 31; ++i) {
		if (b >> i & 1) {
			res *= mul;
			res %= MOD;
		}
		mul = (mul * mul) % MOD;
	}

	return res;
}

void addedge(int from, int to, int cost) {
	G[from].push_back({ to,cost });
	G[to].push_back({ from,cost });
}

//↑template↑


long long a, b, mon, ans;
int main() {
	cin >> a >> b;
	//num,howmany
	vector<pair<long long, long long>>v;
	for (int i = 0; i < a; ++i) {
		long long n;
		cin >> n;
		v.push_back(make_pair(n, 1));
	}
	for (int i = 0; i < b; ++i) {
		long long n, m;
		cin >> n >> m;
		v.push_back(make_pair(m, n));
	}
	sort(all(v));
	reverse(all(v));

	for (int i = 0; i < v.size(); ++i) {
		if (v[i].second + mon <= a) { ans += v[i].first*v[i].second; mon += v[i].second; }
		else { ans += (a - mon)*v[i].first; break; }
	}
	cout << ans << endl;
}

Measured memory_bytes: 6256
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())
if len(list(filter(lambda x: x>k,[b-a,c-a,d-a,e-a,c-b,d-b,e-b,d-c,e-c,e-d]))) > 0:
    print(":(")
else:
    print("Yay!")

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
using namespace std;
int main(void){
    int n;
    cin>>n;
    int a[100][30];
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        for(int j=0;j<s.size();j++){
            a[i][s[j]-'a']++;
        }
    }
    string al="abcdefghijklmnopqrstuvwxyz";
    for(int i=0;i<26;i++){
        int t=1000;
        for(int j=0;j<n;j++){
            t=min(t,a[j][i]);
        }
        for(int k=0;k<t;k++){
            cout<<al[i];
        }
    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
// using namespace atcoder;
#define rep(i, a) for (int i = 0; i < (int)(a); i++)
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
typedef long long ll;
template<typename T>istream& operator>>(istream&i,vector<T>&v){rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const vector<T>&v){stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,const vector<T>&v){if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v){return i>>v.first>>v.second;}
template<typename T1,typename T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v){return o<<v.first<<","<<v.second;}
template<typename T>bool mins(T& x,const T&y){if(x>y){x=y;return true;}else return false;}
template<typename T>bool maxs(T& x,const T&y){if(x<y){x=y;return true;}else return false;}
template<typename T>ll suma(const vector<T>&a){ll res(0);for(auto&&x:a)res+=x;return res;}

#ifdef _DEBUG
inline void dump() { cerr << endl; }
template <typename Head> void dump(Head &&head) {
  cerr << head;
  dump();
}
template <typename Head, typename... Tail>
void dump(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  dump(forward<Tail>(tail)...);
}
#define debug(...)                                                               \
  do {                                                                         \
    cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = ";                        \
    dump(__VA_ARGS__);                                                         \
  } while (false)
#else
#define dump(...)
#define debug(...)
#endif

template <typename T> struct edge {
  int src, to;
  T cost;
  edge(int to, T cost) : src(-1), to(to), cost(cost) {}
  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}
  edge &operator=(const int &x) {
    to = x;
    return *this;
  }
  operator int() const { return to; }
};
template <typename T> using Edges = vector<edge<T>>;
template <typename T> using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<vector<int>>;
template <typename T> using Matrix = vector<vector<T>>;

const ll LINF = 1LL << 60;
const int INF = 1001001001;

/////////////////////////////////////////////////////////////////////

int main()
{
  ll n,q; cin>>n>>q;
  n-=2;

  ll ans = n*n;

  set<ll> sta;
  set<ll> stb;
  map<ll, ll> mpa;
  map<ll, ll> mpb;
  sta.insert(n);
  stb.insert(n);
  mpa[n] = n;
  mpb[n] = n;

  while (q--) {
    ll z,x; cin>>z>>x; x-=2;
    if (z == 1) {
      auto it = sta.lower_bound(x);
      ll xx = *it;
      ll yy = mpa[xx];
      ans -= yy;
      if (x < *sta.begin()) {
        mpb[yy] = x;
        stb.insert(yy);
        mpa[x] = yy;
        sta.insert(x);
      }
    } else {
      auto it = stb.lower_bound(x);
      ll yy = *it;
      ll xx = mpb[yy];
      ans -= xx;
      if (x < *stb.begin()) {
        mpa[xx] = x;
        sta.insert(xx);
        mpb[x] = xx;
        stb.insert(x);
      }
    }
  }
  cout << ans << "\n";

  return 0;
}


Measured memory_bytes: 25508
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define lli long long int  
#define ll  long long 
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(),v.rend() //reverse
#define vl   vector<ll>
#define mii unordered_map<ll,ll>
#define pb push_back
double pi = 2*acos(0.0);
ull power(ll a,ll b){ ll res=1;while(b){if(b&1)res=res*a;b=b/2; a=(a*a); }return res;}
 
//bool sortinrev(const pair<int,int> &a,   const pair<int,int> &b) {  if(a.first==b.first) return a.second>b.second;  return (a.first < b.first);} 
              
     
 
 int main()
 {
       ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
       ll tst;
       tst=1; 
       //cin>>tst;
       while(tst--)
       {
       	  int h;
       	  cin>>h;
       	  vector<int>v(h);
       	  for(int i=0;i<h;i++)
       	  	cin>>v[i];
       	  
       	   int dp[100000]={0};
       	  dp[0]=0;
       	  dp[1]=abs(v[1]-v[0]);
       	  for(int i=2;i<h;i++)
       	  {
       	  	dp[i]=min(dp[i-1]+abs(v[i]-v[i-1]),dp[i-2]+abs(v[i]-v[i-2]));
       	  }
       	  cout<<dp[h-1];


       }  
                
                
       
 }

Measured memory_bytes: 4052
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;
constexpr double pi = acos(-1);
constexpr double EPS = 1e-10;

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

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

    int n; cin>>n;
    
    for(int i=1; i<=n; i++){
        if((int)(i * 1.08) == n){
            cout << i << endl;
            return 0;
        }
    }

    cout << ":(" << endl;

    return 0;
}

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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
#define endl '\n'
#define m_p make_pair
#define max 2010
#define oo 0x3f3f3f3f3f3f3f3f

int n;
ll x,sum;
ll a[max];
ll dp[max][max];

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

    //freopen("fibsubseq.in","r",stdin);
    //freopen("fibsubseq.out","w",stdout);
	
	cin >> n >> x;
	for(int i=0;i<n;i++) cin >> a[i];
	
	for(int i=0;i<n;i++)
	{
		dp[i][0]=a[i];
		for(int k=1;k<n;k++)
		{
			int pos = i-k;
			if(pos<0) pos = n+pos;
			dp[i][k]=min(dp[i][k-1],a[pos]);
		}
	}
	sum = oo;
	for(int k=0;k<n;k++)
	{
		ll res = 0;
		for(int i=0;i<n;i++)
		{
			res+=dp[i][k];
		}
		sum=min(sum,res+k*x);
	}
	
	cout << sum << endl;
    return 0;
}



Measured memory_bytes: 31744
#include <bits/stdc++.h> 
using namespace std; 
const int dx[]={1,0,-1,0,1,-1,-1,1}; 
const int dy[]={0,1,0,-1,1,1,-1,-1}; 
const int INF = 1e9; 
const long long LINF = 1e18; 
const double EPS = 1e-8; 
#define pb push_back 
#define mk make_pair 
#define fr first 
#define sc second 
#define ll long long 
#define reps(i,j,k) for(int i = (j); i < (k); ++i) 
#define rep(i,j) reps(i,0,j) 
#define all(a) (a).begin(),(a).end() 
#define MOD 1000000007 
typedef pair<int,int> Pii; 
typedef vector<int> vi; 
int main(){
    int K,T;
    cin >> K >> T;
    vi a;
    rep(i,T){
        int x;
        cin >> x;
        a.pb(x);
    }
    sort(a.rbegin(),a.rend());
    int prev = -1;
    int Q = K;
    int idx = 0;
    int ans = 0;
    while(Q--){
        rep(i,T){
            //cout << a[i] << " ";
        }
       // cout << endl;
        if(prev == idx)++ans;
        a[idx]--;
        prev = idx;
        int mx = 0;
        int id = -1;
        rep(i,T){
            if(i == idx)continue;
            if(mx < a[i]){
                id = i;
                mx = a[i];
            }
        }
        if(id != -1){
            idx = id;
        }
        else{
            cout << Q << endl;
            exit(0);
        }
    }

    return 0;
}


Measured memory_bytes: 384
#include<stdio.h>

int sq(int n){
  return n*n;
}

int sum(int d,int n){
  if(n>=600){
    return 0;
  }
  else{
    return d*sq(n)+sum(d,n+d);
  }
}

void doit(){
  int n;
  if(scanf("%d",&n)!=EOF){
    printf("%d\n",sum(n,0));
    doit();
  }
}

int main(){
  doit();
  return 0;
}

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

using namespace std;

#define SZ(x) (int)(x.size())
#define REP(i, n) for(int i=0;i<(n);++i)
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RREP(i, n) for(int i=(int)(n);i>=0;--i)
#define RFOR(i, a, b) for(int i=(int)(a);i>=(int)(b);--i)
#define ALL(a) (a).begin(),(a).end()
#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;

const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;

template <typename T1, typename T2>
bool chmax(T1 &a, const T2 &b) {
  if(a < b) {a = b; return true;}
  return false;
}

template <typename T1, typename T2>
bool chmin(T1 &a, const T2 &b) {
  if(a > b) {a = b; return true;}
  return false;
}

template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  REP(i, SZ(v)) {
    if(i) os << " ";
    os << v[i];
  }
  return os;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int n; cin >> n;
  n %= 10;
  if(n == 3) {
    cout << "bon" << endl;
  } else if(n == 0 || n == 1 || n == 6 || n == 8) {
    cout << "pon" << endl;
  } else {
    cout << "hon" << endl;
  }

}
























Measured memory_bytes: 3600
#include <iostream>
#include <utility>
#include <stdint.h>

using namespace std;

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

  int ans = N/1.08;

  for (int ii=ans-5; ii<ans+5; ++ii) {
    if (int(ii*1.08)==N) {
      cout << ii << endl;
      return 0;
    }
  }
  
  cout << ":(" << endl;

  return 0;
}


Measured memory_bytes: 256
r,p['   '],i;main(i,n){for(;i*i++<1e5;)if(!p[i])for(n=i+i;n<1e5;n+=i)p[n]=1;for(;scanf("%d",&n),n;r=!printf("%d\n",r))for(i=1;i++<n/2;)r+=!p[i]&!p[n-i];exit(0);}

Measured memory_bytes: 800