akhauriyash/Code-Regression huggingface dataset:
// Created by SAMAN on ۷/۳۱/۲۰۲۰ م..
//#pragma GCC target ("avx2")
#pragma GCC optimization ("O2")
#pragma GCC optimization ("unroll-loops") 
#include <iostream>
#include <algorithm>
#include <map>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue> 
#include <vector>
#include <set>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <cmath>
#include <ctime>
#include <iomanip>
//#warning not there YET
//#error hello
#define lint long long int
#define endl '\n'
#define kill(x) return cout<<x<<'\n', 0;
#define debug(x) cout << #x << " : " << x << '\n'
#define pb push_back
#define ppb pop_back
#define f first
#define s second
#define _ri [i<<1|1]
#define _le [i<<1]  
typedef long long  ll;
typedef long double ld;

using namespace std;

lint n,w;
const int maxn = 109;
const int nm = 1e6+900;
lint weight[nm],value[nm];
lint dp[maxn][nm];
/*
dp[i][j] -> i taye aval jameshoon beshe j  max arzesh
dp[i][j] = nemiyad -> dp[i-1][j],miad dp[i-1][j-wi]+vi
ans = dp[n][w] 
*/
int main(){
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> w;
	for(int i = 1;i<=n;i++){
		cin >> weight[i];
		cin >> value[i];
	}
	for(int i = 0;i<=w;i++)
		dp[0][i] = 0;

	for(int i = 0;i<=n;i++)
		dp[i][0] = 0;

	for(int i = 0;i <= n;i++){	
		for(int j = 0;j<=w;j++){
			if(i == 0 || j == 0)
				dp[i][j] = 0;
			else if(weight[i] <= j)
				dp[i][j] = max(1LL * dp[i-1][j] ,1LL * dp[i-1] [j-weight[i]] + value[i]);
			else	
				dp[i][j] = dp[i-1][j];
		}
	
	}
	cout<<(ll)dp[n][w];
}


Measured memory_bytes: 82300
#include <cstdio>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iterator>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define debug(x)  cout << #x << " = " << (x) << endl;

using namespace std;

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

    vector<int> acc_r(n + 1, 0);
    vector<int> acc_g(n + 1, 0);
    vector<int> acc_b(n + 1, 0);

    rep(i, n) {
        if (s[n - 1 - i] == 'R') {
            acc_r[i + 1] = acc_r[i] + 1;
            acc_g[i + 1] = acc_g[i];
            acc_b[i + 1] = acc_b[i];
        } else if (s[n - 1 - i] == 'G') {
            acc_r[i + 1] = acc_r[i];
            acc_g[i + 1] = acc_g[i] + 1;
            acc_b[i + 1] = acc_b[i];
        } else {
            acc_r[i + 1] = acc_r[i];
            acc_g[i + 1] = acc_g[i];
            acc_b[i + 1] = acc_b[i] + 1;
        }
    }

    // rep(i, n + 1) {
    //     cout << acc_r[i] << " " << acc_g[i] << " " << acc_b[i] << endl;
    // }
    int64_t ans = 0;
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            if (s[i] == s[j]) continue;
            char ch;
            if (s[i] == 'R') {
                if (s[j] == 'G') {
                    ch = 'B';
                } else {
                    ch = 'G';
                }
            } else if (s[i] == 'G') {
                if (s[j] == 'R') {
                    ch = 'B';
                } else {
                    ch = 'R';
                }
            } else {
                if (s[j] == 'R') {
                    ch = 'G';
                } else {
                    ch = 'R';
                }
            }
            if (ch == 'R') {
                ans += acc_r[n - j - 1];
            } else if (ch == 'G') {
                ans += acc_g[n - j - 1];
            } else {
                ans += acc_b[n - j - 1];
            }
            if (2 * j - i < n && s[2 * j - i] == ch) {
                ans--;
            }
        }
    }
    cout << ans << endl;

}


Measured memory_bytes: 3200
//#include "pch.h"
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <utility>
#include <queue>
#include <algorithm>
#include <functional>
#include <string>
#include <bitset>

#define ll long long
#define fri(n) for(i=0;i<(n);i++)
#define frj(n) for(j=0;j<(n);i++)
#define min(p,q) ((p)<(q)?(p):(q))
#define max(p,q) ((p)>(q)?(p):(q))
#define INF 1000000000000000000//10^18
#define INFINT 2000000001//2*10^9+1
#define MOD 1000000007
#define MODANOTHER 998244353
#define PI acos(-1)

using namespace std;

ll int mod_inverse(int a,int M){
	int x=M-2;
	ll int temp=a;
	ll int ret=1;
	//a^(MOD-1)==1(mod MOD)を利用
	//a^-1==a^(MOD-2) (mod MOD)を繰り返し二乗法で求める

	while(x!=0){
		if(x%2==1){
			ret=(ret*temp)%M;
		}
		temp=(temp*temp)%M;
		x=x/2;
	}
	return ret;
}


int main(void)
{
	//変数の宣言
	int b,w;
	static ll black[200010];
	static ll white[200010];

	//よく使う変数
	int i,j,k,l;
	int flag=0;
	ll int ans=0;
	int count=0;
	ll temp=0;
	ll temp1=0;
	ll temp2=0;
	int max=0;
	int min=INFINT;
	int len=0;
	int sum=0;
	int ok=0;
	int ng=0;
	int dummy;



	//データの読み込み


	scanf("%d %d",&b,&w);
//	scanf_s("%d %d",&b,&w);

	/*	for(i=0;i<n;i++){
	//		scanf("%d",&s[i]);
	scanf_s("%d",&s[i]);
	}*/

	//	printf("nは%dです\n", n);
	//	printf("データの読み込み終了\n");
	//実際の処理

	int m2;
	m2=mod_inverse(2,MOD);

	for(i=1;i<=b+w;i++){
		if(i<b){
			black[i]=0;
		}else if(i==b){
			temp=1;
			for(j=1;j<b;j++){
//				temp=temp*j;
				temp=temp*m2;
				temp=temp%MOD;
			}
			temp=temp*m2;
			temp=temp%MOD;
			black[i]=temp;
		}else{
			black[i]=black[i-1]*m2%MOD;
			black[i]=black[i]*(i-1)%MOD;
			black[i]=black[i]*mod_inverse(i-b,MOD)%MOD;
		}
	}


	for(i=1;i<=b+w;i++){
		if(i<w){
			white[i]=0;
		}else if(i==w){
			temp=1;
			for(j=1;j<w;j++){
//				temp=temp*j;
				temp=temp*m2;
				temp=temp%MOD;
			}
			temp=temp*m2;
			temp=temp%MOD;
			white[i]=temp;
		}else{
			white[i]=white[i-1]*m2%MOD;
			white[i]=white[i]*(i-1)%MOD;
			white[i]=white[i]*mod_inverse(i-w,MOD)%MOD;
		}
	}


	//	printf("計算部分終了\n");

	//出力
	temp1=0;
	temp2=0;
	for(i=0;i<b+w;i++){
		temp1=temp1+black[i];
		temp2=temp2+white[i];
		ans=(1-temp1+temp2)%MOD;
		ans=(ans*m2)%MOD;
		ans=(ans+MOD)%MOD;
		printf("%lld\n",ans);
	}

/*	for(i=0;i<b+w;i++){
		printf("%lld %lld\n",black[i],white[i]);
	}*/


	//	printf("結果の出力終了\n");

	return 0;
}



Measured memory_bytes: 5376
#include <stdio.h>
#include <math.h>
 
typedef struct _Point {
  double x, y;
} Point;
 
typedef Point Vector;
 
Vector add(Vector a, Vector b) {
  a.x += b.x;
  a.y += b.y;
  return a;
}
 
Vector subtract(Vector a, Vector b) {
  a.x -= b.x;
  a.y -= b.y;
  return a;
}
 
Vector multiply(Vector a, double b) {
  a.x *= b;
  a.y *= b;
  return a;
}
 
Vector divide(Vector a, double b) {
  a.x /= b;
  a.y /= b;
  return a;
}
 
Vector rotate(Vector v, double angle) {
  Vector nv;
  nv.x = v.x * cos(angle) - v.y * sin(angle);
  nv.y = v.x * sin(angle) + v.y * cos(angle);
  return nv;
}
 
Point rec(int n, Point a, Point b) {
  Vector v,u;
  Point c,d,e;
  if(n == 0) {
    printf("%.8f %.8f\n", a.x, a.y);
    return;
  }
  v = subtract(b,a);
  u = divide(v,3.0);
  c = add(a,u);
  d = add(c,u);
  e = add(c,rotate(u,M_PI/3.0));
  rec(n-1, a, c);
  rec(n-1, c, e);
  rec(n-1, e, d);
  rec(n-1, d, b);
}
 
int main() {
  int n;
  scanf("%d", &n);
  rec(n, (Point){0.0, 0.0}, (Point){100.0, 0.0});
  printf("%.8f %.8f\n", 100.0, 0.0);
  return 0;
}


Measured memory_bytes: 2124
N, M = map(int, input().split())
ans = 0
nn = 1
mm = 1
for i in range(1, N+1):
    nn = (nn*i)%(10**9+7)
for i in range(1, M+1):
    mm = (mm*i)%(10**9+7)

if N == M:
    ans = ((2*nn*mm)%(10**9+7))

elif abs(N-M) ==1:
    ans = ((nn*mm)%(10**9+7))

print(ans)

Measured memory_bytes: 3064
main(n,m,e,j,z)
{
  char a[]="C";
  for(;;)
  {
    scanf("%d",&n);
    if(!n)exit(0);
    for(;n--;a[0]='C')
      {
	scanf("%d%d%d",&m,&e,&j);
	z=m+e+j;
	if((z>149&&(m>79||e>79))||z>209)
	  a[0]='B';
	if(z>239||z-j>179||m>99||e>99||j>99)
	  a[0]='A';
	puts(a);
      }
  }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define sp(n) cout << fixed << setprecision(n)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
using namespace std;
int main(void){
    ll n,z,w;cin>>n>>z>>w;
    if(n==1){
        ll a;cin>>a;
        ll res=abs(a-w);
        cout<<res<<endl;
        return 0;
    }
    n++;
    vector<ll> a(n);
    a[0]=z;
    rep(i,n-1) cin>>a[i+1];
    ll buf1=abs(a[n-1]-a[n-2]),buf2=abs(a[n-1]-w);
    ll res=max(buf1,buf2);
    cout<<res<<endl;
}


Measured memory_bytes: 3628
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF ((1<<30)-1)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()




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

	int h, w, m;
	cin >> h >> w >> m;

	vector<vector<int>> yp(w);
	multiset<int> ms;

	unordered_map<int, int> ym, xm;
	set<pair<int, int>> s;
	rep(_, m) {
		int y, x;
		cin >> y >> x;
		y--; x--;
		++ym[y];
		++xm[x];
		yp[x].push_back(y);
	}
	for (auto p : ym) {
		ms.insert(p.second);
	}

	int ans = 0;
	rep(x, w) {
		int xc = xm[x];
		for (int y : yp[x]) {
			int yc = ym[y];
			ans = max(ans, xc + yc - 1);
			ms.erase(ms.find(yc));
		}
		if (ms.empty()) {
			ans = max(ans, xc);
		}
		else {
			ans = max(ans, xc + *ms.rbegin());
		}
		for (int y : yp[x]) {
			int yc = ym[y];
			ms.insert(yc);
		}
	}
	cout << ans << endl;



	return 0;
}


Measured memory_bytes: 60476
H, W = map(int, input().split())

grid = [input() for i in range(H)]

grid2 = [[0 for i in range(W)] for j in range(H)]

for i in range(H):
    for j in range(W):
        if grid[i][j] == "#":
            grid2[i][j] = "#"
            continue
        count = 0
        for k in range(3):
            for l in range(3):
                if(i+k-1 < H and  i+k-1 >= 0 and j+l-1 < W and j+l-1 >=0 and grid[i+k-1][j+l-1] == "#"):
                    count+=1
        grid2[i][j] = str(count)

for row in grid2:
    print("".join(row))

Measured memory_bytes: 3188
using System;
using System.Linq;
using System.Collections.Generic;

class Mondai
{
    static void Main()
    {
        var S = Console.ReadLine();
        var ans = 0L;
        var count = Math.Pow(2, S.Length - 1);
        for (int i=0;i<count;++i)
        {
            var array = new bool[S.Length-1];
            for (int j = 0; j < S.Length - 1; ++j) if ((1 & i >> j) == 1) array[j] = true;
            var formula = string.Empty;
            for (int k = 0; k < S.Length; ++k)
            {
                formula += S[k];
                if (k != S.Length - 1) if (array[k]) formula += '+';
            }
            var num =string.Empty;
            for (int k=0;k<formula.Length;++k)
            {
                if (formula[k] != '+') num += formula[k];
                else
                {
                    ans += Int64.Parse(num);
                    num = string.Empty;
                }
            }
            ans += Int64.Parse(num);
        }
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 13140
require "bigdecimal"
require "bigdecimal/util"

def gi() gets.to_i end
def gs() gets.chomp end
def gmi() gets.split.map(&:to_i) end
def gms() gets.split.map(&:chomp) end
def YesNo1(bool, yes="Yes", no="No") puts (bool ? yes : no) end
def YESNO2(bool, yes="YES", no="NO") puts (bool ? yes : no) end


#####
n = gi
min = 1000000000000
(1..Math.sqrt(n).ceil).each do |i|
  if n%i == 0
    min = [i-1 + (n/i)-1, min].min
  end
end
puts min

Measured memory_bytes: 2040
import java.io.*;
import java.util.*;

public class Main{
	public static void main(String args[]){
		try{
			new Main();
		}catch(IOException e){
			e.printStackTrace();
		}
	}
	
	public Main() throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		List<Integer> player = new ArrayList<Integer>();
		String line;
		
		while((line = in.readLine()) != null){
			String[] tmp = line.split(" ");
			int m = Integer.parseInt(tmp[0]);
			int n = Integer.parseInt(tmp[1]);
			
			if(m==0 && n==0) break;
			
			for(int i=0; i<m; i++){
				player.add(i);
			}
			
			int turn = 0;
			for(int i=1; i<=n; i++){
				line = in.readLine();
				if(player.size() == 1){
					continue;
				}
				
				if(i%15==0){
					if(!line.equals("FizzBuzz")){
						player.remove(turn);
						turn--;
					}
				}
				else if(i%5==0){
					if(!line.equals("Buzz")){
						player.remove(turn);
						turn--;
					}
				}
				else if(i%3==0){
					if(!line.equals("Fizz")){
						player.remove(turn);
						turn--;
					}
				}
				else{
					if(!line.equals(Integer.toString(i))){
						player.remove(turn);
						turn--;
					}
				}
				
				turn++;
				if(turn >= player.size()){
					turn %= player.size();
				}
			}
			
			for(int i=0; i<player.size(); i++){
				System.out.print(player.get(i)+1);
				if(i!=player.size()-1){
					System.out.print(" ");
				}
			}
			System.out.println();
			player.clear();
		}
	}
}

Measured memory_bytes: 11000
#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,l;
    cin >> n >> l;
    string s[n];
    REP(i,n){
        cin >> s[i];
    }
    sort(s, s + n);
    REP(i,n){
        cout << s[i];
    }
    cout << endl;
}

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

int main(){
	ll a[3];
	cin >> a[0] >> a[1] >> a[2];

	ll ans = 1e18;
	for (int i = 0;i < 3;i++) {
		if (a[i] % 2 == 0) {
			ans = 0;
		}
		else {
			ans = min(ans, a[(i + 1) % 3] * a[(i + 2) % 3]);
		}
	}
	cout << ans << endl;

	return 0;
}

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

int main(){
	int k,ans=0;
	int array[3];

	for(int i=0;i<3;i++)cin >>array[i];
	cin >>k;
	sort(array,array+3);
	for(int i=0;i<k;i++)array[2]*=2;
	ans+=array[0]+array[1]+array[2];
	cout<<ans<<endl;
	return 0;

}

Measured memory_bytes: 256
# 2019/11/24

s=input()
if s=='SUN':
    print(7)
if s=='MON':
    print(6)
if s=='TUE':
    print(5)
if s=='WED':
    print(4)
if s=='THU':
    print(3)
if s=='FRI':
    print(2)
if s=='SAT':
    print(1)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,a,b,c,i,B = 0,ans = 1000000000,now,g;scanf("%d%d%d%d",&n,&a,&b,&c);
  int l[n],t[4];
  for(i=0;i<n;i++) scanf("%d",&l[i]);
  while(B<(1<<(n*2))){
    t[0] = t[1] = t[2] = t[3] = now = 0;
    for(i=0;i<n;i++){
      g = bool(B&(1<<(i*2)))+bool(B&(1<<(i*2+1)))*2;
      if(g<3 && t[g]) now += 10;
      t[g] += l[i];
    }
    if(t[0] && t[1] && t[2]) ans = min(ans,abs(a-t[0])+abs(b-t[1])+abs(c-t[2])+now);
    B++;
  }
  printf("%d\n",ans);
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <queue>
#include <iomanip>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
using namespace std;

long N, Z, W;

int main() {
  cin >> N >> Z >> W;
  vector<long> A(N);
  rep(i, N) {
    cin >> A.at(i);
  }
  long ans;
  if (N==1) {
    ans = abs(A.at(0) - W);
  } else {
    ans = max(abs(A.at(N-1)-W), abs(A.at(N-2) - A.at(N-1)));
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
//Arayi
//#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <math.h>
#include <vector>
#include <cstring>
#include <ctime>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <ctime>
#include <climits>
#include <cassert>
#include <chrono>
#include <random>
#include <complex>

#define fr first
#define sc second
#define MP make_pair
#define ad push_back
#define PB push_back
#define fastio ios_base::sync_with_stdio(false); cin.tie(0);
#define lli long long int
#define y1 arayikhalatyan
#define j1 jigglypuff
#define ld long double
#define itn int
#define pir pair<int, int> 
#define all(x) (x).begin(), (x).end()
#define str string
#define enl endl
#define en endl
#define cd complex<long double>
#define vcd vector<cd>
#define vii vector<int>
#define vlli vector<lli>
using namespace std;

lli gcd(lli a, lli b) { return (b == 0LL ? a : gcd(b, a % b)); }
ld dist(ld x, ld y1, ld x2, ld y2)
{
    return sqrt((x - x2) * (x - x2) + (y1 - y2) * (y1 - y2));
}
lli S(lli a)
{
    return (a * (a + 1LL)) / 2;
}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
char vow[] = { 'a', 'e', 'i', 'o', 'u' };
int dx[] = { 1, -1, 0, 0, -1, -1, 1, 1, 0 };
int dy[] = { 0, 0, 1, -1, -1, 1, -1, 1, 0 };


const int N = 3e5 + 30;
lli mod = 36000;
const ld pi = acos(-1);
const int T = 238;
const ld e = 1e-13;

lli bp(lli a, lli b = mod - 2LL)
{
    lli ret = 1;
    while (b)
    {
        if (b & 1) ret *= a, ret %= mod;
        a *= a;
        a %= mod;
        b >>= 1;
    }
    return ret;
}
ostream& operator<<(ostream& c, pir a)
{
    c << a.fr << " " << a.sc;
    return c;
}
struct pt
{
    lli x, y;
    int ind;
    int bl;
    bool operator==(const pt& a)
    {
        return ind == a.ind;
    }
    bool operator<(const pt& b)
    {
        if (x == b.x) return y < b.y;
        return x < b.x;
    }
};




int t, n;
int main()
{
    fastio;
    cin >> t;
    while (t--)
    {
        cin >> n;
        lli sum = 0;
        vector <pir > a, b;
        for (int i = 0; i < n; i++)
        {
            int k;
            lli l, r;
            cin >> k >> l >> r;
            if (l >= r)
            {
                sum += r;
                a.ad(MP(k, l - r));
            }
            else
            {
                sum += l;
                b.ad(MP(n - k, r - l));
            }
        }
        sort(all(a));
        sort(all(b));
        priority_queue <lli> q;
        for (auto p : a)
        {
            q.push(-p.sc);
            if (q.size() > p.fr) q.pop();
        }
        while (!q.empty())
        {
            sum += -q.top();
            q.pop();
        }
        for (auto p : b)
        {
            q.push(-p.sc);
            if (q.size() > p.fr) q.pop();
        }
        while (!q.empty())
        {
            sum += -q.top();
            q.pop();
        }
        cout << sum << endl;
    }
    return 0;
}

/*


  __
*(><)*
  \/ /
  ||/
--||
  ||
  /\
 /  \
/    \
*/

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

int a[200001];
int tmp[200001];

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

	int start = 0;
	int end = n -1;

	for (int i = 0; i < n; i++) {
		int b;
		cin >> b;
		tmp[i] = b;
	}

	for (int i = 0; i < n; i++) {
		int cur = tmp[n - i - 1];
		if (i % 2 == 0) {
			a[start] = cur;
			start++;
		} else {
			a[end] = cur;
			end--;
		}
	}


	for (int i = 0; i < n; i++) {
		int b;
		cout << a[i] << " ";
	}

	cout << endl;

	return 0;

}

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

#define ll long long
#define INF_LL 1LL << 60
#define INF 99999999
#define MOD (ll)1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, a, n) for(int i = a; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

void put_double(double obj){printf("%.12f\n",obj);};

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

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


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

    if( A+B > C+D ) cout << "Left" << endl;
    else if( A+B < C+D ) cout << "Right" << endl;
    else cout << "Balanced" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <unordered_set>
#include <bitset>
#include <cmath>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
static const int INF = 1000010000;
static const int NIL = -1;
static const int MOD = 1000000007;
 
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define SORT(v) sort(v.begin(), v.end());
#define pb push_back
#define mp make_pair
#define np next_permutation
#define pq priority_queue
 
int gcd(int a, int b) { int c; while (b != 0) { c = a%b; a = b; b = c; }return a; }
int lcm(int a, int b) { int c = gcd(a, b); a /= c; return a*b; }
int nCr(int a, int b) { int i, r = 1; for (i = 1; i <= b; i++) { r *= (a + 1 - i); r /= i; }return r; }
int pow(int a, int b) { int i, r = 1; for (i = 1; i <= b; i++) { r *= a; }return r; }
long long llpow(long long a, long long b) { long long i, r = 1; for (i = 1; i <= b; i++) { r *= a; }return r; }
long long llgcd(long long a, long long b) { long long c; while (b != 0) { c = a%b; a = b; b = c; }return a; }
long long lllcm(long long a, long long b) { long long c = llgcd(a, b); a /= c; return a*b; }
long long llnCr(long long a, long long b) { long long i, r = 1; for (i = 1; i <= b; i++) { r *= (a + 1 - i); r /= i; }return r; }
 
//int dx4[4] = {0,1,0,-1}, dy4[4] = {-1,0,1,0};
//int dx5[5] = {-1,0,0,0,1}, dy5[5] = {0,-1,0,1,0};
//int dx8[8] = {-1,0,1,1,1,0,-1,-1}, dy8[8] = {1,1,1,0,-1,-1,-1,0};
//int dx9[9] = {-1,0,1,1,1,0,-1,-1,0}, dy9[9] = {1,1,1,0,-1,-1,-1,0,0};

int main(){
    int n;
    cin >> n;
    int ans = 0;
    FOR(i, 1, n + 1){
        ans += i;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
typedef long long ll;
typedef long l;
int return_max(int a,int b){
  if(a>b){
    return a;
  }else{
    return b;
  }
}

int return_min(int a,int b){
  if(a<b){
    return a;
  }else{
    return b;
  }
}

int main(void)
{
  int a;
  scanf("%d",&a);
  printf("%d\n",a+a*a+a*a*a);
  return 0;
}


Measured memory_bytes: 1724
import java.util.Scanner;

public class Main {
	static String temp;
	static Scanner sc = new Scanner (System.in);
	public static void main(String[] args){

		temp = sc.next();
		int n = sc.nextInt();
		for(int i = 0; i < n; i++){
			String doing = sc.next();
			if(doing.equals("print")){
				print(sc.nextInt(),sc.nextInt());
			}else if(doing.equals("reverse")){
				reverse(sc.nextInt(),sc.nextInt() );
			}else if(doing.equals("replace")){
				replace(sc.nextInt(),sc.nextInt());
			}
		}
	}
	static void print(int a, int b){
		System.out.println(temp.substring(a,b + 1));
	}
	static void reverse(int a, int b){
		StringBuilder str = new StringBuilder();
		str.append(temp.substring(a,b + 1));
		str.reverse();
		if(a != 0){
			temp = temp.substring(0,a) + str.toString() + temp.substring(b + 1, temp.length());
		}else {
			temp = str.toString() + temp.substring(b + 1, temp.length());
		}
	}
	static void replace(int a, int b){
		String str = sc.next();
		if(a != 0){
			temp = temp.substring(0,a) + str + temp.substring(b + 1, temp.length());
		}else {
			temp = str + temp.substring(b + 1, temp.length());
		}
	}
}

Measured memory_bytes: 29544
import sys
sys.setrecursionlimit(10**9)

def f(x):#dpは
    if dp[x]!=-1:
        return dp[x]#すでに値が決まっていたらそれをかえす
    ans=0
    for e in d[x]:#すべての枝について
        ans=max(ans,1+f(e))
    dp[x]=ans
    return ans

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

d={}
dp=[-1]
for i in range(1,n+1):
    d[i]=[]#dは初期値を[]
    dp.append(-1)#dpは初期値-1

for _ in range(m):
    a,b = map(int, input().split())
    d[a].append(b)#有向グラフをdictで
    
ans=0
for i in range(1,n+1):
    ans=max(ans,f(i))
print(ans)

Measured memory_bytes: 163328
#include <bits/stdc++.h>
using namespace std;
 
int steps(int x1, int y1, int x2, int y2) {
  return max(x1-x2,x2-x1) + max(y1-y2,y2-y1);
}

int main() {
  int N;
  cin >> N;
  vector<vector<int>> p(N, vector<int>(3));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 3; j++) {
      cin >> p.at(i).at(j);
    }
  }
  bool b = 1;
  int c = steps(0,0,p.at(0).at(1),p.at(0).at(2)) - p.at(0).at(0);
    if (c > 0 || (c % 2) == -1) {
      b = 0;
      goto FF;
    }
  for (int i = 1; i < N; i++) {
    int d = steps(p.at(i).at(1), p.at(i).at(2), p.at(i-1).at(1), p.at(i-1).at(2)) - (p.at(i).at(0) - p.at(i-1).at(0));
    if (d > 0 || (d % 2) == -1) {
      b = 0;
      break;
    }
  }
  FF:
  if (b == 1) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

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

void solve() {
    int n;
    cin >> n;
    vector<int> v(n),dp(n+1,0);
    for(int i=0;i<n;i++) cin >> v[i];
    set<int> s;
    for(int i=0;i<n;i++) {
        auto it = s.find(v[i]-1);
        if(it==s.end()) {
            dp[v[i]]=1;
        } else {
            dp[v[i]] = dp[v[i]-1]+1;
        }
        s.insert(v[i]);
    }

    int x = *max_element(dp.begin(),dp.end());
    cout << n-x << "\n";

}

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

    solve();
    return 0;
}

Measured memory_bytes: 11264
#include <iostream>
#include <cassert>
#include <climits>
#include <bitset>
#include <stack>
#include <queue>
#include <iomanip>
#include <limits>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <tuple>
#include <time.h>
#include <random>

using namespace std;

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

long long int INF = 3e18;
double Pi = 3.1415926535897932384626;

vector<ll> G[500005];
//vector<P> tree[500010];
priority_queue <ll> pql;
priority_queue <P> pqp;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop

int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "DRUL";
//ll bit[500005];
//↓,→,↑,←


#define p(x) cout<<x<<endl;
#define el cout<<endl;
#define pe(x) cout<<(x)<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<(x);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define line cout << "----------" << endl;


ll mod = 1000000007;
ll rui(ll number1,ll number2){

    if(number2 == 0){
        return 1;
    }else{
        ll number3 = rui(number1,number2 / 2);
        number3 *= number3;
        number3 %= mod;
        if(number2%2==1){
            number3 *= number1;
            number3 %= mod;
        }
        return number3;
    }
}
ll gcd(ll number1,ll number2){

    if(number1 > number2){
        swap(number1,number2);
    }
    if(number1 == 0 || number1 == number2){
        return number2;
    }else{
        return gcd(number2 % number1,number1);
    }
}
void YES(bool condition){

    if(condition){
        p("YES");
    }else{
        p("NO");
    }
    return;
}
void Yes(bool condition){

    if(condition){
        p("Yes");
    }else{
        p("No");
    }
    return;
}
void Yay(bool condition){

    if(condition){
        p("Yay!");
    }else{
        p(":(");
    }
    return;
}

//ll fact[800005],rfact[800005];
/*
void c3_init(){
    fact[0] = rfact[0] = 1;
    for(ll i=1; i<=800000; i++){
        fact[i] = (fact[i-1]*i) % mod;
    }
	rfact[800000] = rui(fact[800000],mod - 2);
	for(ll i=800000; i>=1; i--){
	   rfact[i-1] = rfact[i] * i;
	   rfact[i-1] %= mod;
	}
	return;}
ll c3(ll n,ll r){
    return (((fact[n] * rfact[r]) % mod) * rfact[n-r]) % mod;}
*/

ll n,m,num,ans,a,b,c,d,e,g,h,w,i,j,k,q;
ll x[500005],y[500005],z[500005];
ll sum[500005],lsum[500005];
char s[500005],t[500005];
bool dame;



int main(){
	cin >> a >> b >> c >> d;
	ans = b - a + 1;
	ll kosu1,kosu2,kosu3;
	kosu1 = b / c - (a - 1) / c;
	kosu2 = b / d - (a - 1) / d;
	ll e = c * d / gcd(c,d);
	kosu3 = b / e - (a - 1) / e;
	p(ans-kosu1-kosu2+kosu3);
	return 0;
}


Measured memory_bytes: 12032
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        string S = Console.ReadLine();
        int[] ans= new int[S.Length];
        int right=0, left = 0;
        for(int i = 0; i < S.Length-1; i++)
        {
            if (S[i] == 'R' && S[i + 1] == 'R') { ans[i] = 0;right++; }
            if(S[i] == 'R' && S[i + 1] == 'L') {
                ans[i] = right / 2+1;
                ans[i + 1] = right / 2 + right%2+1;
                right = 0;
            }
        }

        for (int i = S.Length-1; i >0 ; i--)
        {
            if (S[i-1] == 'L' && S[i] == 'L') { ans[i] += 0; left++; }
            if (S[i-1] == 'R' && S[i] == 'L')
            {
                ans[i-1] += left / 2 + left % 2;
                ans[i] += left / 2;
                left = 0;
            } 
        }
        Console.WriteLine(string.Join(" ", ans));
    }
}


Measured memory_bytes: 13456
#include<bits/stdc++.h>
#define Yes cout<<"Yes"<<endl;
#define No cout<<"No"<<endl;
#define ll long long int
using namespace std;
int main()
{


        ll a,b,c,n,x,y,z,cnt=0,sum=0;
        string str;
        cin>>a>>b>>c;
        for(int i=a;i<=b;i++)
        {
            if(i%c==0)cnt++;
        }
cout<<cnt<<endl;

}



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

using namespace std;

#define rep(i , l , r) for(int i = (l) , ___ = (r) ; i <= ___ ; ++i)
#define per(i , r , l) for(int i = (r) , ___ = (l) ; i >= ___ ; --i)

template<typename T>inline int chkmin(T &x , const T &y) { return x > y ? x = y , 1 : 0; }
template<typename T>inline int chkmax(T &x , const T &y) { return x < y ? x = y , 1 : 0; }

template<typename T>inline T read(T &f)
{
	f = 0 ; int x = 1 ; char c = getchar();
	while(!isdigit(c)) x = c == '-' ? -1 : 1 , c = getchar();
	while(isdigit(c)) (f *= 10) += c & 15 , c = getchar();
	return f *= x;
}

const int N = 200000 + 5;

using int64 = long long;

int n , cnt , A[N] , col[N] ;

int64 s[N] , sum[N] , sl[N];

int main()
{
	read(n);
	rep(i , 1 , n)
	{
		static char op[3] , last = 0;
		static int lastval = 0;
		read(A[i]) , last = op[0];
		if(i < n) scanf("%s" , op);
		if(last == '-')
		{
			A[i] = -A[i];
			col[++cnt] = -1;
			s[cnt] = A[i];
		}
		if(lastval <= 0 && A[i] > 0) s[++cnt] = A[i];
		if(lastval > 0 && A[i] > 0) s[cnt] += A[i];
		lastval = A[i];
	}
	per(i , cnt , 1)
	{
		sum[i] = sum[i + 1] + abs(s[i]);
	}
	int64 Ans = -(1ll << 60) , ret = 0;
	rep(i , 1 , cnt)
	{
		sl[i] = sl[i - 1] + s[i];
	}
	cerr << cnt << endl;
	rep(i , 1 , cnt)
	{
		if(col[i + 1] == -1)
		{
			chkmax(Ans , sl[i + 1] - s[i + 2] + sum[i + 3]);
		}
	}
	chkmax(Ans , sl[cnt]);
	cout << Ans << endl;
	return 0;
}


Measured memory_bytes: 5632
#include<iostream>

int main(){
    std::string a;
    std::cin>>a;
    for(int i=0;i<5;i++)
        std::cout<<a[i];
    std::cout<<" ";
    for(int i=6;i<13;i++)
        std::cout<<a[i];
    std::cout<<" ";
    for(int i=14;i<19;i++)
        std::cout<<a[i];
    std::cout<<std::endl;
}

Measured memory_bytes: 256
n, we = map(int, input().split())

cf=[(0, 0)]*(n+1)

for i in range(1, n+1):
    cf[i] = tuple( map(int, input().split()) )

dp=[[0]*(we+1) for _ in range(n+1)]

best=0

for i in range(1, n+1):
    for j in range(cf[i][0]):
        dp[i][j]=dp[i-1][j]
    for j in range(cf[i][0], we+1):
        dp[i][j]=max( dp[i][j-1], dp[i-1][j], dp[i-1][j-cf[i][0]]+ cf[i][1] )
    best=max(best, dp[i][we])


print(best)

# for i in range(1, n+1): print( dp[i], '\n' )

Measured memory_bytes: 119276
# n, k = gets.chomp.split(" ").map(&:to_i)
# a = gets.chomp.split(" ").map(&:to_i)
# min = 100001
# kizyun = 0
# retsu = a.sort
# kizyun = retsu[0]
# arr = []
# a.each_with_index do |item,j|
#     if kizyun == item
#         arr << j
#     end
# end
# kai = 100001
# arr.each do |i|
#     #はじめ
#     ans = 0
#     if i % (k-1) == 0
#         ans += i / (k-1)
#     elsif i % (k-1) != 0
#         ans += (i/(k-1)) + 1
#     end
#     #あと
#     ii = n - i - 1
#     if ii % (k-1) == 0
#         ans += ii / (k-1)
#     elsif ii % (k-1) != 0
#         ans += (ii/(k-1)) + 1
#     end
#     kai = [kai,ans].min
# end
# puts kai

n, k = gets.chomp.split(" ").map(&:to_i)
a = gets.chomp.split(" ").map(&:to_i)
count = 1
st = k
i = 0
while true
    if st + (k-1) * i >= n
        puts count
        break
    end
    i += 1
    count += 1
end

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

using namespace std;

long long dp[51][51][2551];

int main()
{
	long long n, a;
	cin >> n >> a;
	vector<long long> x(n);
	for (auto&& xi : x) cin >> xi;
	long long count = 0;
	dp[0][0][0] = 1;
	for (auto i = 0ll; i < n; i++)
		for (auto j = 0ll; j <= i; j++)
			for (auto k = 0ll; k <= 2500ll; k++)
			{
				dp[i+1][j+1][k+x[i]] += dp[i][j][k];
				dp[i+1][j][k] += dp[i][j][k];
			}
	for (auto i = 1ll; i <= n; i++) count += dp[n][i][i*a];
	cout << count << endl;
	return 0;
}


Measured memory_bytes: 50048
cnt=0
while True:
    cnt+=1
    W=int(input())
    if W==0:
        break
    n=int(input())
    dp=[0]*(W+1)
    for i in range(n):
        v,w=map(int,input().split(','))
        for j in range(W,w-1,-1):
            dp[j]=max(dp[j],dp[j-w]+v)
    wgt=0
    md=max(dp)
    for i in range(W+1):
        if md==dp[i]:
            wgt=i
            break
    print("Case {0}:".format(cnt))
    print(md)
    print(wgt)

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

# 左側
l = A[0:N]
lsum = [sum(l)]
heapq.heapify(l)
for i in range(N,2*N):
    x = heapq.heappushpop(l,A[i])
    lsum.append(lsum[-1] + A[i] - x)

# 右側
r = list(map(lambda x: -x, A[-N:N*3]))
rsum = [sum(r)]
heapq.heapify(r)
for i in range(N,2*N):
    x = heapq.heappushpop(r, -A[3*N-1-i])
    rsum.append(rsum[-1] - A[3*N-1-i] - x)

ans = -9999999999999999
for i in range(len(rsum)):
    ans = max(ans, lsum[i]+rsum[len(rsum)-1-i])

print(ans)

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

int main() {
	int h, w;
	cin >> h >> w;

	vector<string> a(h);
	rep(i,h) {
		cin >> a[i];
	}

	vector<bool> row(h, false);
	vector<bool> column(w, false);

	rep(i,h){
		rep(j,w){
			if (a[i][j] == '#') {
				row[i] = true;
				column[j] = true;
			}
		}
	}

	rep(i,h) {
		if (row[i] == true) {
			rep(j,w) {
				if (column[j] == true) {
					cout << a[i][j];
				}
			}
			cout << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<deque>
#include<functional>
#include<ctime>
#include<cassert>
#include<cstring>
#include<unordered_map>
#include<cmath>
using namespace std;

#define sz(x) (int)(x.size())
#define fi(a,b) for(int i=a;i<=b;++i)
#define fj(a,b) for(int j=a;j<=b;++j)
#define fo(a,b) for(int o=a;o<=b;++o)
#define fdi(a,b) for(int i=a;i>=b;--i)
#define fdj(a,b) for(int j=a;j>=b;--j)
#define fdo(a,b) for(int o=a;o>=b;--o)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef double ld;
typedef vector<int> vi;

template<class T> bool uin(T &a, T b){ return (a > b ? a = b, true : false); }
template<class T> bool uax(T &a, T b){ return (a < b ? a = b, true : false); }

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

int const MAXN = 141;
ld const PI = acos(-1);

int n, x[MAXN], y[MAXN];
ld ans[MAXN];

ld norm(ld a) {
	while(a > PI * 2) {
		a -= PI * 2;
	}
	while(a < 0) {
		a += PI * 2;
	}
	return a;
}

ld getdist(ld a, ld b) {
	if (b >= a) {
		return b - a;
	}
	ld res = PI * 2 - a + b;
	return res;
}

void solve(){
	fi(0, n - 1) {
		vector<pair<ld, int>> a;
		fj(0, n - 1) {
			if (i == j) continue;
			ld ang = atan2( (ld) y[j] - y[i], (ld) x[j] - x[i] );
			ld a0 = norm(ang + PI / 2);
			ld a1 = norm(ang - PI / 2);
			a.pb(mp(a0, 1));
			a.pb(mp(a1, -1));
		}
		sort(a.begin(), a.end());
/*		for(pair<ld, int> z : a) {
			fprintf(stderr, "%.3lf %d\n", z.first, z.second);
		}
		cerr << '\n';*/
		fo(0, sz(a)) {			
			int q = 0;
			fj(0, sz(a) - 1) {
				q += a[j].second;
				if (q == n - 1) {
					ans[i] = max(ans[i], getdist(a[j].first, a[j + 1].first));
					break;
				}
			}
			pair<ld, int> tmp = a.back();
			a.pop_back();
			a.insert(a.begin(), tmp);
		}
		ans[i] /= (PI * 2);
	}	
}

int main(){
#ifdef LOCAL
	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
#endif

	scanf("%d", &n);
	fi(0, n - 1) {
		scanf("%d %d", &x[i], &y[i]);
	}		
	solve();		
	fi(0, n - 1) {
		printf("%.15lf\n", ans[i]);
	}
	
#ifdef LOCAL
	fprintf(stderr, "ELAPSED TIME: %.3lf\n", (ld) clock() / CLOCKS_PER_SEC);
#endif	
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

using namespace std;

#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, a, b) for (int i = a; i <= b; i++)
#define all(a)  begin((a)),end((a))
#define uniq(c) (c).erase(unique(all((c))), end((c)))

int main()
{
    int N, M; cin >> N >> M;
    long long cost = 0;
    vector<int> A(N);
    rep (i, 0, M) {
        cin >> A[i];
        cost += A[i];
    }

    if ((N - cost) >= 0) cout << N - cost << endl;
    else cout << -1 << endl;
}

Measured memory_bytes: 7224
n=int(input())

x,y=map(int,input().split())
for i in range(n-1):
    t,a=map(int,input().split())
    k=(x+t-1)//t
    m=(y+a-1)//a
    p=max(k,m)
    x=t*p
    y=a*p
print(x+y)


Measured memory_bytes: 71512
#include<iostream>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<cmath>
#include<map>

using namespace std;

#define rep(i,N) for(int i=0;i<N;i++) //0から


typedef long long ll;




ll binary_search(vector<ll> a, ll n, ll key){
    ll right = n, left = -1;
    ll md = (right + left) / 2;

    while(right - left > 1){
        if(a[md] <= key){
            right = md;
        }else{
            left = md;
        }
        md = (right + left) / 2;
    }
    if(left == -1) return -1; //無い場合
    return right;
}

vector<ll> prime;
void Prime(ll n){ //線形篩,素数列挙
    vector<ll> p(n,0);
    p[0]=1;
    p[1]=1;
    for(ll i=2;i<n;i++){
        if(p[i]==0){
            prime.push_back(i);
            p[i]=i;
        }
        ll k=prime.size();
        for(ll j=0;j<k && i*prime[j]<n && prime[j]<=p[i];j++){
            p[i*prime[j]]=prime[j];
        }
    }
}

#define MOD ((ll)1e+9 + 7)




//cout<<fixed<<setprecision(10);
int main(){
    int x,a;
    cin>>x>>a;
    if(x<a){
        cout<<0<<endl;
    }
    else{
        cout<<10<<endl;
    }


    return 0;
}



Measured memory_bytes: 3608
#include<iostream>
#include<map>
#include<algorithm>

using namespace std;

int main(){
	int n;
	cin >> n;
	map<int,int> mp;
	
	for(int i = 0;i < n;i++){
		int p;
		cin >> p;
		mp[p] = i+1;
	}
	
	int k = 1;
	int tk = 1;
	for(int i = 1;i <= n;i++){
		if(mp[i] < mp[i+1]){
			tk++;
		}else{
			k = max(k,tk);
			tk = 1;
		}
	}
	
	cout << n - k << endl;
	return 0;
}

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

#define all(x) (x).begin(), (x).end()
#define szof(x) int32_t((x).size())
#define str(x) to_string(x)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;

const ll MOD = 1e9 + 7;
const ll MOD998 = 998244353;
const int INF = 1e9;
const ll LLINF = 1e18;

mt19937_64 rng((uint) chrono::steady_clock::now().time_since_epoch().count());

template <class T>
T rnd(T l, T r) {
	return uniform_int_distribution<T>(l, r)(rng);
}

using Matrix = vector<vector<int>>;

int add(int x, int y, int mod = MOD998) {
	return x + y >= mod ? x + y - mod : x + y;
}

int sub(int x, int y, int mod = MOD998) {
	return x - y < 0 ? x - y + mod : x - y;
}

int mul(int x, int y, int mod = MOD998) {
	return 1LL * x * y % mod;
}

int pw(int a, int n, int mod = MOD998) {
	int res = 1;
	while (n) {
		if (n & 1) {
			res = mul(res, a, mod);
		}
		a = mul(a, a, mod);
		n >>= 1;
	}
	return res;
}

int inv(int x, int mod = MOD998) {
	return pw(x, mod - 2, mod);
}

vector<int> get_invs(int upto, int mod = MOD998) {
	vector<int> res(upto + 1);
	res[1] = 1;
	for (int i = 2; i <= upto; i++) {
		res[i] = mod - mul(mod / i, res[mod % i], mod);
	}
	return res;
}

Matrix eye(int n) {
	Matrix A(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		A[i][i] = 1;
	}
	return A;
}

Matrix mul(const Matrix &A, const Matrix &B) {
	int n = szof(A);
	Matrix C(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				C[i][j] = add(C[i][j], mul(A[i][k], B[k][j], MOD), MOD);
			}
		}
	}
	return C;
}

Matrix pow(Matrix &a, ll n) {
	Matrix res = eye(szof(a));
	while (n) {
		if (n & 1) {
			res = mul(res, a);
		}
		a = mul(a, a);
		n >>= 1;
	}
	return res;
}

void run() {
	int n; 
	ll k;
	cin >> n >> k;
	Matrix A(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> A[i][j];
		}
	}
	A = pow(A, k);
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			ans = add(ans, A[i][j], MOD);
		}
	}
	cout << ans << "\n";
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cout.precision(10); cout << fixed;
	int tests = 1;
	// cin >> tests;
	while (tests--) {
		run();
	}
	cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s.\n";
	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <stdio.h>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cfloat>
#include <math.h>
#include <stack>
#include <queue>
#include <cstdio>
#include <iomanip>

using namespace std;

#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++)
// #define req(j, n) for (ll j = 1; j < (n+1); j++)
// #define rer(k, n) for (ll k = 1; k < (n+1); k++)



int main()
{
    vector<int> x(5);
    int count = 0;
    rep(i, 5) {
        cin >> x[i];
        if (x[i] == 0) {
            count = i+1;
        }
    }
    cout << count << endl;
}


Measured memory_bytes: 3580
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		for(int i=0;i<n;i++){
			int outCount=0;
			int runnerCount=0;
			int pointCount=0;
			while(outCount<3){
				String event=sc.next();
				if(event.equals("OUT")){
					outCount++;
				}
				if(event.equals("HIT")){
					runnerCount++;
					if(runnerCount>=4){
						pointCount++;
					}
				}
				if(event.equals("HOMERUN")){
					if(runnerCount>=4){
						pointCount+=4;
					}else{
						pointCount+=runnerCount+1;
					}
					runnerCount=0;
				}
			}
			System.out.println(pointCount);
		}
	}
}

Measured memory_bytes: 17172
#include <iostream>
#include <cstring>

using namespace std;

int m[50][50];

int main(void){

	int W,H,T;
	int P;

	int x,y,t;
	int b;

	int ans = 0;

	cin >> W >> H >> T;
	cin >> P;

	memset(m,0,sizeof(m));

	for(int i=0;i<P;++i){
		cin >> x >> y >> t;
		if(t<=T){
			m[y][x]++;
		}
	}

	for(int i=0;i<H;++i){
		for(int j=0;j<W;++j){
			cin >> b;

			ans += b*m[i][j];
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 1180
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
#include <complex>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <functional>
#include <assert.h>
using ll=long long;
#define int ll
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define SZ(x) ((int)x.size())
#define fi first
#define se second
const int INF = 1e15;
using namespace std;

template<class T> using vc=vector<T>;
template<class T> using vvc=vc<vc<T>>;

using pi=pair<int,int>;
using vi=vc<int>;

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

void dfs(vi G[],vc<bool> &vis,vi &score,int v){
    vis[v]=true;
    for(auto a:G[v]){
        if(!vis[a]) {
            score[a]+=score[v];
            dfs(G,vis,score,a);
        }
    }
}
signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(20);

    int N,Q; cin >> N >> Q;
    vi G[N];
    vc<bool> vis(N,false);
    vi score(N,0);
    rep(i,N-1){
        int a,b; cin >> a >> b;
        a--; b--;
        G[a].eb(b);
        G[b].eb(a);
    }
    rep(i,Q){
        int a,b; cin >> a >> b;
        a--;
        score[a]+=b;
    }
    dfs(G,vis,score,0);
    rep(i,N){
        cout << score[i] << " ";
    }
    cout << endl;
}

Measured memory_bytes: 30592
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>
#include <numeric>

using namespace std;

#define mod 1000000007

int cnt[4001][4001][2] = {};

int calc(int x1, int y1, int x2, int y2, int z)
{
	int ans = cnt[x2][y2][z];
	if(x1 > 0) ans -= cnt[x1 - 1][y2][z];
	if(y1 > 0) ans -= cnt[x2][y1 - 1][z];
	if(x1 > 0 && y1 > 0) ans += cnt[x1 - 1][y1 - 1][z];
	return ans;
}

int main()
{
	int n, k;
	cin >> n >> k;
	for(int i = 0; i < n; i++){
		int x, y;
		char c;
		cin >> x >> y >> c;
		x %= 2 * k;
		y %= 2 * k;
		if(c == 'B'){
			cnt[x][y][0]++;
			cnt[x + 2 * k][y + 2 * k][0]++;
			cnt[x + 2 * k][y][0]++;
			cnt[x][y + 2 * k][0]++;
		}
		else {
			cnt[x][y][1]++;
			cnt[x + 2 * k][y + 2 * k][1]++;
			cnt[x + 2 * k][y][1]++;
			cnt[x][y + 2 * k][1]++;
		}
	}
	for(int j = 0; j < 4 * k; j++){
		for(int i = 1; i < 4 * k; i++){
			cnt[i][j][0] += cnt[i - 1][j][0];
			cnt[i][j][1] += cnt[i - 1][j][1];
		}
	}

	for(int i = 0; i < 4 * k; i++){
		for(int j = 1; j < 4 * k; j++){
			cnt[i][j][0] += cnt[i][j - 1][0];
			cnt[i][j][1] += cnt[i][j - 1][1];
		}
	}

	// for(int i = 0; i < 20; i++){
	// 	for(int j = 0; j < 20; j++){
	// 		cout << cnt[i][j][0];
	// 	}
	// 	cout << endl;
	// }

	// for(int i = 0; i < 20; i++){
	// 	for(int j = 0; j < 20; j++){
	// 		cout << cnt[i][j][1];
	// 	}
	// 	cout << endl;
	// }

	int ans = 0;
	for(int i = 0; i < 2 * k; i++){
		for(int j = 0; j < 2 * k; j++){
			// cout << i << " " << j << " ";
			int res = calc(i, j, i + k - 1, j + k - 1, 0);
			// cout << res << " ";
			res += calc(i + k, j + k, i + 2 * k - 1, j + 2 * k - 1, 0);
			// cout << res << " ";
			res += calc(i, j + k, i + k - 1, j + 2 * k - 1, 1);
			// cout << res << " ";
			res += calc(i + k, j, i + 2 * k - 1, j + k - 1, 1);
			// cout << res << endl;
			ans = max(ans, res);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 125312
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll inf = 1e18;

ll n, m, mx, cr, ans;
pll a[200005];

vector<ll> s[200005];
priority_queue<ll> pq, pp;

struct segtree {
	ll val[888888], lazy[888888];
	void lazydown (ll P) {
		val[2*P] += lazy[P];
		lazy[2*P] += lazy[P];
		val[2*P+1] += lazy[P];
		lazy[2*P+1] += lazy[P];
		lazy[P] = 0;
	}
	void upd (ll S, ll E, ll X, ll L=0, ll R=m+1, ll P=1) {
		if(S <= L && R <= E) {val[P] += X; lazy[P] += X; return;}
		if(E < L || R < S) return;
		lazydown(P);
		ll M = (L+R)/2;
		upd(S, E, X, L, M, 2*P);
		upd(S, E, X, M+1, R, 2*P+1);
		val[P] = min(val[2*P], val[2*P+1]);
	}
	ll qry (ll S, ll E, ll L=0, ll R=m+1, ll P=1) {
		if(S <= L && R <= E) return val[P];
		if(E < L || R < S) return inf;
		lazydown(P);
		ll M = (L+R)/2;
		return min(qry(S, E, L, M, 2*P), qry(S, E, M+1, R, 2*P+1));
	}
} seg;

bool can (ll X) {
	return (seg.qry(m-X+1, m) >= X-m);
}

int main()
{
	scanf("%lld%lld",&n,&m);
	for(ll i=0;i<=m;i++) seg.upd(i, i, -i);
	for(ll i=1;i<=n;i++) {
		scanf("%lld%lld",&a[i].X,&a[i].Y);
		pq.push(-a[i].X);
		seg.upd(a[i].Y, m, 1);
	}
	sort(a+1, a+1+n);
	while(!pq.empty()) {
		ll T = -pq.top(); pq.pop();
		if(T >= (1+mx)) mx++;
	}
	for(ll i=mx,j=n;i>=1;i--) {
		for(;j>=1 && a[j].X >= i;j--) {
			pq.push(a[j].Y);
		}
		ll V = pq.top();
		seg.upd(V, m, -1);
		pp.push(-V);
		pq.pop();
	}
	for(ll i=mx;i>=1;i--) {
		while(i+cr < m && can(cr+1)) cr++;
		ans = max(ans, i+cr);
		seg.upd(-pp.top(), m, 1);
		pp.pop();
	}
	while(cr < m && can(cr+1)) cr++;
	ans = max(ans, cr);
	printf("%lld\n",n-ans);
}


Measured memory_bytes: 26608