akhauriyash/Code-Regression huggingface dataset:
/*input
1 1 5 5
1
10
*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#ifdef leowang
#define debug(...) do{\
	fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}
//}}}
const ll maxn=300005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}
vector<int> x,y;
int main()
{
	IOS;
	int n,m;
	cin>>n>>m;
	{
		int tmp;
		cin>>tmp;
		x.pb(tmp);
		cin>>tmp;
		y.pb(tmp);
	}
	REP(i,n){
		int tmp;cin>>tmp;
		x.pb(tmp);
	}
	REP(i,m){
		int tmp;
		cin>>tmp;
		y.pb(tmp);
	}
	sort(ALL(x));
	sort(ALL(y));
	if(x.back()<y[0]){
		cout<<"No War\n";
	}
	else cout<<"War\n";
	return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n,a,b = map(int, input().split())
h = list(int(input()) for i in range(n))

diff = a-b

hmax = max(h)

saiaku = -(-hmax//b)

def isok(ans):
    count = 0
    for i in range(n):
        count += max(-(-(h[i]-b*ans)//diff),0)
    if count > ans:
        return False
    return True

ok = saiaku
ng = -1 # -1にしとけば答えが0の時も普通に扱えるな

while ok - ng > 1:
    m = (ok+ng)//2
    if isok(m):
        ok = m
    else:
        ng = m
print(ok)


Measured memory_bytes: 7084
import java.util.Scanner;

public class Main {

	static Scanner scanner;

	public static void main(String[] args) {
	    scanner = new Scanner(System.in);

	    String s=gs();
	    StringBuffer s0=new StringBuffer(s);
	    StringBuffer s1=new StringBuffer(s.substring(0,(s.length()-1)/2));
	    StringBuffer s2=new StringBuffer(s.substring((s.length()+1)/2));

        if (s.equals(s0.reverse().toString()) && s1.toString().equals(s1.reverse().toString()) && s2.toString().equals(s2.reverse().toString())) {
    	    System.out.print("Yes");
        }else {
        	System.out.print("No");
        }
	}

	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}

	// doubleとして入力を取得
	public static double gd() {
		return Double.parseDouble(scanner.next());
	}
}

Measured memory_bytes: 35488
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.array;

void main(){
  auto F=readln.split.to!(int[]),A=F[0],B=F[1],C=F[2],D=F[3];
  if(A+B<C+D)writeln("Right");
  else if(A+B>C+D)writeln("Left");
  else writeln("Balanced");
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  int n;
  cin >> n;
  --n;
  vector<int> c(n),s(n),f(n);
  rep(i,n) cin >> c[i] >> s[i] >> f[i];

  rep(i,n){
    int t = 0;
    for(int x=i;x<n;++x){
      t = max(t,s[x]);
      t = s[x] + (t-s[x]+f[x]-1)/f[x]*f[x] + c[x];
    }
    cout << t << endl;
  }
  cout << 0 << endl;
}


Measured memory_bytes: 384
N = int(input())
As = list(map(int, input().split()))

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

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


m = 1
for A in As:
    m = lcm(m, A)

ans = 0
for A in As:
    ans += (m-1) % A

print(ans)


Measured memory_bytes: 3316
#include <iostream>

long long int lcm(long long int a, long long int b)
{
	long long int x = a * b;

	if (a < b){
		long long int tmp = a;
		a = b;
		b = tmp;
	}
	
	long long int c = a % b;
	while (c != 0){
		a = b;
		b = c;
		c = a % b;
	}
	return x / b;
}

int main()
{
	long long int A = 0, B = 0, ans = 0;
	std::cin >> A >> B;

	ans = lcm(A, B);

	std::cout << ans << std::endl;

	return  0;
}

Measured memory_bytes: 256
X, Y = map(int, input().split())
mod = 10**9+7
b = (2*Y-X)//3
a = Y - 2*b
max_num = a + b + 5
facts = [1 for i in range(max_num)]
invs = [1 for i in range(max_num)]
 
def inv(x):
    return pow(x,mod-2,mod)
 
for i in range(1,max_num):
    facts[i] = facts[i-1]*i%mod
    invs[i] = inv(facts[i])
 
def nCk(n,k):
    try:
        return facts[n]*invs[k] * invs[n-k] % mod
    except IndexError:
        print(n, k, len(facts), len(invs))
if (X+Y)%3 == 0 and a>=0 and b >=0:
    print(nCk(a+b, a))
else:
    print(0)

Measured memory_bytes: 91280
#include <iostream>
#include "stdio.h"

using namespace std;

int main() {
  int w,h,x,y,r;

  scanf("%d%d%d%d%d", &w, &h, &x, &y, &r);

  bool in = x+r <= w && x-r >= 0 && y+r <= h && y-r >= 0;

  printf("%s\n", in ? "Yes" : "No");

  return 0;
}



Measured memory_bytes: 3164
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vs = vector<string>;
#define  rep(i,n) for(ll i = 0; i < (n); ++i)
#define  red(i,n) for(ll i = (n)-1; i >= 0; --i)
#define  all(a)   begin(a),end(a)
#define  pb(a)    push_back(a)
#define  yn(a)    cout << ( (a)?"Yes\n":"No\n" );
inline ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }
const ll INF = 1e9+9, LINF = 1e18;


int main()
{
    int a,b,x=0;
    cin>>a>>b;
    rep(i,(b-a)-1)x+=i+1;
    cout<<x-a<<endl;
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
int ans;
void solve(string &S, string &N) {
	if (S.size() > N.size()) return;
	if (S.size() == N.size() && S > N) return;
	int A = 0, B = 0, C = 0;
	for (int i = 0; i < S.size(); i++) {
		if (S[i] == '7') A++;
		else if (S[i] == '5') B++;
		else C++;
	}
	if (A > 0 && B > 0 && C > 0) ans++;
	string tmp = "753";
	for (int i = 0; i < 3; i++) {
		S.push_back(tmp[i]);
		solve(S, N);
		S.pop_back();
	}
}
int main() {
	int N;
	cin >> N;
	string S = "";
	string T = to_string(N);
	solve(S, T);
	cout << ans << endl;
}


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

int parent(int i){return i/2;}
int left(int i){return i*2;}
int right(int i){return i*2 + 1;}

int main(){
  int h;
  cin >> h;
  int key;
  int T[h + 1];
  for ( int i = 1; i <= h; i++){
    cin >> key;
    T[i] = key;
  }

  for ( int i = 1; i <= h; i++){
    cout << "node " << i << ": " << "key = " << T[i] << ", ";
    if ( parent(i) >= 1  ){
      cout << "parent key = " << T[parent(i)] << ", ";
    }
    if ( left(i) <= h){
      cout << "left key = " << T[left(i)] << ", ";
    }
    if ( right(i) <= h){
      cout << "right key = " << T[right(i)] << ", ";
    }
    cout << endl;
  }

  return 0;
}


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

using namespace std;

const int INF = 0x3f3f3f3f;

int pd[100000];
int n;
int vet[100000];

int solve(int i) {
	if(i == n-1) return 0;
	if(i > n) return INF;
	
	int &ans = pd[i];
	if(ans != -1) return ans;
	
	ans = min(solve(i+1) + abs(vet[i]-vet[i+1]), solve(i+2) + abs(vet[i]-vet[i+2]));

	return ans;
}

int main(void) {
	
	scanf("%i", &n);
	for(int i = 0; i < n; i++)
		scanf("%i", &vet[i]);
	
	memset(pd, -1, sizeof(pd));
	
	printf("%i\n", solve(0));
	return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ios_base::sync_with_stdio( false );
 
	int A, B, C;
	cin >> A >> B >> C;
 
	bool result = false;
 
	for( int i = 1; i <= B; ++i ) {
		if( A*i % B == C ) {
			result = true;
			break;
		}
	}
 
 	cout << (result ? "YES" : "NO") << endl;
 	return 0;
}


Measured memory_bytes: 256
N = gets.to_i
H = gets.split.map(&:to_i)
dp = [0]
dp[1] = (H[0] - H[1]).abs
1.upto(N-1) do |i|
  dp[i] = [(H[i] - H[i-1]).abs + dp[i-1], (H[i] - H[i-2]).abs + dp[i-2]].min
end

p dp[N-1]

Measured memory_bytes: 11396
n=int(input())
p=list(map(int,input().split()))
d=0
for i in range(0,n-2):
    if p[i]>p[i+1]:
       if p[i+1]>p[i+2]:
          d=d+1
    if p[i]<p[i+1]:
       if p[i+1]<p[i+2]:
          d=d+1
print(d)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define fileio freopen("in.in", "r", stdin),freopen("out.out", "w", stdout);
#define ll long long int
#define FF first
#define SS second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long int,long long int>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d\n",x)
#define plld(x) printf("%lld\n",x)
#define pss printf
#define MOD 1000000007
#define INF 1e18
#define eps 0.00001
#define endl '\n'
#define debug(n1) cout<<n1<<endl
const int N = 1e5;  // limit for array size
ll n;  // array size

int main(){
	string s,t;cin>>s>>t;
	
	int g=1;
	
	if(s.length()!=t.length()){
		cout<<"No"<<endl;return 0;
	}
	
	for(int i=0;i<s.length();i++){
		g=1;
		for(int j=0;j<s.length();j++){
			if(s[(i+j)%s.length()]!=t[j]){
				g=0;break;
			}
		}
		if(g){
			cout<<"Yes"<<endl;return 0;
		}
	}
	
	cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef vector <int> vi;
typedef vector <vi> vvi;
typedef pair <int,int> pr;
#define fr(i, n) for(int i = 0; i < n; i++)
#define sz(a) int((a).size())
#define pb push_back
#define all(c)(c).begin(), (c).end()
#define tr(c, i) for (typeof ((c).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c, x)((c).find(x) != (c).end())
#define cpresent(c, x)(find(all(c), x) != (c).end())
// for mod power a^b%m use power<lli> (a,b,m)
template < class mytype >
mytype power(mytype a, mytype b, mytype m){if (b == 1) return a % m;if (b == 0) return 1;
mytype root = power < lli > (a, b / 2, m);mytype ans = (root * root) % m;if (b % 2) ans = (ans * a) % m;
return ans;
}
// for gcd use gcd<int> (a,b)
template < class type >type gcd(type a, type b){if (a == 0) return b;else return gcd(b % a, a);}
template < class type >type mod_inv(type a, type p) {return power(a, p - 2, p);}
int n;
vector<int> h(100001);
vector<int> cost(100001 , -1);

int dp(int index){
    if(cost[index] != -1) return cost[index];
    cost[index] = dp(index - 1) + abs(h[index] - h[index - 1]);
    if(index != 1) cost[index] =  min(cost[index] , dp(index - 2) + abs(h[index] - h[index - 2]) );
    return cost[index];
    }
int main()
{
    cin >> n;cost[0] = 0;
    for(int i = 0 ; i < n ; i++){
        cin >> h[i];
    }
    cout << dp(n-1) << endl;



    return 0;
}


Measured memory_bytes: 5760
#include <stdio.h>

int main(){
  int i,N,X;
  int L[100];
  int cnt =0;
  scanf("%d%d",&N,&X);
  for(i=0;i<N;i++){
    scanf("%d",&L[i]);
    cnt+=L[i];
    if(cnt>X)
      break;
  }
  printf("%d",i+1);
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const long double PI  = acos(-1.0L);
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
#define chmax(a,b) a = (((a)<(b))?(b):(a))
#define chmin(a,b) a = (((a)>(b))?(b):(a))

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}


signed main(){
	int k; cin>>k;
	string s; cin>>s;
	int n=s.size();
	if(n<=k) cout<<s<<endl;
	else{
		rep(i,k) cout<<s[i];
		cout<<"..."<<endl;
	}

	return 0;
}


Measured memory_bytes: 3656
//Author rahuliitkgp

/*A thing of beauty is a joy forever,
Its loveliness increases,
it will never pass into nothingness.*/
//Men at Work :)

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;

#define setbits(x)      __builtin_popcountll(x)
#define mod             1000000007
#define ps(x,y)         fixed<<setprecision(y)<<x
#define w(x)            int x; cin>>x; while(x--)
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

void cpp(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}

int main(){
    cpp();
    for(ll i=1; i<=5; i++){
        ll x;
        cin>>x;
        if(x==0){
            cout<<i<<endl;
            return 0;
        }
    }
    return 0;
}

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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

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

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  int X, Y;
  cin >> X >> Y;

  int ans = 0;

  if(X == 3){
    ans += 100000;
  }else if(X == 2){
    ans += 200000;
  }else if(X == 1){
    ans += 300000;
  }

  if(Y == 3){
    ans += 100000;
  }else if(Y == 2){
    ans += 200000;
  }else if(Y == 1){
    ans += 300000;
  }

  if(X == 1 && Y == 1){
    ans += 400000;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

#define EPS 1e-7

string tostr(int arg){
	string ret = "00000000.0000";
	int pos = 0;
	while(arg > 0){
		if(arg & 1){
			ret[12-pos] = '1';
		}
		arg >>= 1;
		pos++;
		if(pos == 4) pos++;
	}
	return ret;
}

int main(){
	vector<double> fs;
	
	double d;
	while(cin >> d && d >= 0){
		int ret=-1;
		for(int i=0;i<(1 << 12);i++){
			if(i == d*16){
				ret = i;
				break;
			}
		}
		if(ret == -1 || d > 255 + 0.5 + 0.25 + 0.125 + 0.0625){
			cout << "NA" << endl;
		}else{
			cout << tostr(ret) << endl;
		}
	}
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
string a,b;
int lena,lenb;
int main(){
    getline(cin,a),getline(cin,b);
    sort(a.begin(),a.end());
    sort(b.begin(),b.end(),greater<char>());
    if(a<b)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

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

ll a[100005];
int main()
{
    int n,k;
    ll min1 = 1e9 + 10;
    cin >> n >> k;
    for(int i = 0;i < n;i++)
    {
        cin >> a[i];
    }
    sort(a,a + n);
    for(int i = 0;i <= n - k;i++)
    {
        ll ch = a[i + k - 1] - a[i];
        if(ch < min1)
        min1 = ch;
        if(min1 == 0)
        break;
    }
    cout << min1 << endl;
    return 0;
}


Measured memory_bytes: 1152
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <limits.h>	
#define inf INT_MAX
#define INF 9223372036854775807
#define sq(n) ((n)*(n))
#define rep(i,n) for(i=0;i<n;i++)
#define rev(i,n) for(i=n-1;i>=0;i--)
const int mod=(int)1e09+7;

int in(void){
	int i;scanf("%d",&i);
	return i;
}
long long llin(void){
	long long i;scanf("%lld",&i);
	return i;
}
double din(void){
	double i;scanf("%lf",&i);
	return i;
}
void chin(char s[]){
	scanf("%s",s);
}
void print(int a){
	printf("%d\n",a);
}
void llprint(long long a){
	printf("%lld\n",a);
}
void dprint(double a){
	printf("%.10f\n",a);
}
void print2(int a,int b){
	printf("%d %d\n",a,b);
}
long long max(long long a,long long b){
	return a>b?a:b;
}
long long min(long long a,long long b){
	return a<b?a:b;
}
double dmax(double a,double b){
	return a>b?a:b;
}
int cmp(const void *a,const void *b){
	return *(int *)a-*(int *)b;
}

int main(void){
	int a[3],i;
	rep(i,3){
		a[i]=in();
	}
	qsort(a,3,sizeof(int),cmp);
	print(a[0]+a[1]);
	return 0;
}


Measured memory_bytes: 128
_N = input()
A_list = list(map(int, input().split()))

while len(A_list) > 1:
    min_A = min(A_list)
    A_list = [min_A] + [A % min_A for A in A_list if A % min_A != 0]

print("{}".format(A_list[0]))

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

int main () {
  long long N;
  cin >> N;
  long long ans = 0;
  for (int i = 1;i <= N; i++){
    bool plus = true;
    if (i%3 == 0) plus = false;
    if (i%5 == 0) plus = false;
    if (plus) ans += i;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3620
// 基本テンプレート
 
#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>
using namespace std;
 
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;
 
const int MAX_N = 100000;
int A[3 * MAX_N + 10];
signed main() {
    int N; cin >> N;
    for(int i=0; i<3*N; i++) {
        cin >> A[i];
    }

    priority_queue< int, vector<int>, greater<int> > que_l;
    priority_queue< pii, vector<pii>, greater<pii> > que_r;
    set<pii> topN_r;

    int sum_l = 0, sum_r = 0;
    for(int i=0; i<N; i++) {
        sum_l += A[i];
        que_l.push(A[i]);
    }
    for(int i=N; i<3*N; i++) {
        que_r.push(make_pair(A[i], i));
    }
    for(int i=0; i<N; i++) {
        pii val = que_r.top(); que_r.pop();
        // printf("add: index = %lld, val = %lld\n", val.second, val.first);
        topN_r.insert(val);
        sum_r += val.first;
    }

    int ans = sum_l - sum_r;
    // printf("initial: sum_l = %lld, sum_r = %lld, ans = %lld\n", sum_l, sum_r, ans);
    for(int i=N; i<2*N; i++) {
        // 動く要素
        int val = A[i];
        // printf("val = %lld\n", val);

        // 左側
        sum_l += val;
        que_l.push(val);
        int erase_l = que_l.top(); que_l.pop();
        // printf("insert %lld, erase %lld\n", val, erase_l);
        sum_l -= erase_l;

        // 右側
        pii elem = make_pair(A[i], i);
        if(topN_r.count(elem)) {
            sum_r -= A[i];
            topN_r.erase(elem);
            while(que_r.size()) {
                pii cur = que_r.top(); que_r.pop();
                if(cur.second <= i) continue;
                topN_r.insert(cur);
                sum_r += cur.first;
                break;
            }
        }
        // printf("end: index = %lld, sum_l = %lld, sum_r = %lld\n", i, sum_l, sum_r);
        chmax(ans, sum_l - sum_r);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 13676
N = int(input())

word =  [input() for i in range(N)]

for i in range(N-1):
 for j in range(i+1, N):
  if word[i] == word[j]:
    print('No')
    exit()

for i in range(0, N-1):
  if word[i][-1] != word[i+1][0]:
    print('No')
    exit()
print('Yes')

Measured memory_bytes: 3060
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>

#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
#define REMOVE(v,a) v.erase(remove(v.begin(), v.end(), a), v.end())
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
using namespace std;

signed main()
{
	int N;
	string s1, s2;
	cin >> N;
	cin >> s1;
	cin >> s2;

	vector<int> pat; //0:| 1:=

	for (int i = 0; i < N; i++)
	{
		if (s1.at(i) == s2.at(i))
		{
			pat.push_back(0);
		}
		else
		{
			pat.push_back(1);
			i++;
		}
	}

	int ans = pat[0] == 0 ? 3 : 6;
	int prev = pat[0];
	for (int i = 1; i < pat.size(); i++)
	{
		if (prev == 0)
		{
			ans *= 2;
		}
		else
		{
			if (pat[i] == 1)
			{
				ans *= 3;
			}
		}
		ans %= 1000000007;
		prev = pat[i];
	}
	cout << ans;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <iomanip>
typedef long long ll;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
using vi = vector<int>;
using vll = vector<ll>;
ll mod = 1e9 + 7;

using namespace std;
using Graph = vector<vector<int>>;
Graph G;
const int AMAX = 100000;
/*int cnt_digit(ll N)
{
	int digit = 0;

	while (N > 0)
	{
		N /= 10;
		digit++;
	}
	return digit;
}

int n;
vll a;

ll solve(bool isp)
{
	ll sum = 0ll;
	ll ret = 0ll;

	for (int i = 0; i < n; i++)
	{
		sum += a[i];
		if (isp and sum <= 0)
		{
			ret += -sum + 1;
			sum = 1ll;
		}
		if (not isp and sum >= 0)
		{
			ret += sum + 1;
			sum = -1ll;
		}
		isp ^= 1;
	}
	return ret;
}

*/
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	
	/*ll N, K;
	cin >> N >> K;
	ll t1 = N%K;
	ll t2 = abs(t1 - K);

	ll ans = min(t1, t2);
	

	cout << ans << endl;*/
	ll N, M;
	vector<ll> S(AMAX + 1);
	cin >> N >> M;
	
	for (int i = 0; i < N; i++)
	{
		int a, b;
		cin >> a >> b;
		S[a] += b;
	}
	for (int ans = 1; ans <=AMAX; ans++)
	{
		if(M<=S[ans])
		{
			cout << ans<< endl;
			break;
		}
		M -= S[ans];
	}

	return 0;

}

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

using namespace std;

const int N = 100000 + 3;

int n, m;
bool vis[N];
vector<int> edges[N];
vector<int> topsorted;

//Tarjan topological sort
void dfs(int node) {
  if(vis[node]) return;
  vis[node] = true;
  //dont push here
  for(int adj: edges[node]) dfs(adj);
  //push here instead
  topsorted.push_back(node);
}

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

  for(int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    --u; --v;
    //reverse direction for Tarjan topological sort
    edges[u].push_back(v);
  }

  for(int i = 0; i < n; ++i) dfs(i);

  //for(int x: topsorted) cout << x + 1 << " "; cout << endl;

  vector<int> dp(n, 0);
  for(int v: topsorted) {
    for(int u: edges[v]) {
      dp[v] = max(dp[v], dp[u] + 1);
    }
  }

  int ans = 0;
  for(int x: dp) ans = max(ans, x);

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 8824
(defun solve (s)
  (let* ((len (length s))
         (x 0)
         (y (1- len))
         (ret 0))
    (loop while (< x y)
          do (let ((sx (char s x))
                   (sy (char s y)))
               (cond ((eq sx sy) (incf x) (decf y))
                     ((eq sx #\x) (incf x) (incf ret))
                     ((eq sy #\x) (decf y) (incf ret))
                     (t (return-from solve -1)))))
    ret))
(format t "~A~%" (solve (read-line)))

Measured memory_bytes: 6376
N = int(raw_input())
S = raw_input()
left = []
right = []
for i in range(0, 26):
	left.append(0)
	right.append(0)
for i in range(0, N):
	left[ord(S[i])-97] += 1
max = 0
for i in range(0, N):
	left[ord(S[i])-97] -= 1
	right[ord(S[i])-97] += 1
	cnt = 0
	for j in range(0, 26):
		if left[j] != 0 and right[j] != 0: cnt += 1
	if max < cnt: max = cnt
print max

Measured memory_bytes: 30444
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return;
}

long double r;

const long double pi = acos(-1.0);

int main() {
    std::cin >> r;
    printf("%.10Lf\n", r * 2 * pi);
    return 0;
}

Measured memory_bytes: 3748
/*
    # Gir bhi gyaa bhai tera uthke phir machaayega
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define setbits(x) __builtin_popcount(x)
#define setbitsll(x) __builtin_popcountll(x)
//#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define se second
#define fi first
#define pai acos(-1)
#define fn(i,x) for(i=0;i<x;i++)
#define fs(i,s,x) for(i=s;i<x;i++)
#define fr(i,x,s) for(i=x;i>=s;i--)
#define fit(itr,s) for(itr=s.begin();itr!=s.end();itr++)
#define W while
#define pp pair<ll,ll>
#define ppi pair<int,int>
#define vl vector<ll>
#define vll vector<pp >
#define vi vector<int>
#define vii vector<ppi>
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define debug(x) cerr<<#x<<" :: "<<x<<endl;
#define debug2(x,y) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define debug3(x,y,z) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<endl;
#define debug4(x,y,z,w) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\t"<<#w<<" :: "<<w<<endl;
#define boost  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
const ll MAX=1e4;
const ll MM=1e18;
const ll mod=1e9+7;

ll expo(ll x,ll n,ll M=mod)
{
    ll ans=1;
    while(n>0)
    {
        if(n&1){ans=(ans*x)%M;}
                x=(x*x)%M;
                n>>=1;
    }
    return ans;
}


void solve()
{
   ll k,i,a,b;
   cin>>k>>a>>b;
   fs(i,a,b+1)
   {
       if(i%k==0)
       {cout<<"OK"<<endl;return;}
   }
    cout<<"NG"<<endl;

}


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


Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,Q;
    cin>>N>>Q;
    vector<int> S(N);
    vector<int> T(N);
    vector<int> X(N);
    vector<int> D(Q);
    vector<int> ans(Q);
    vector<tuple<int,int,int,int>> event;
    for(int i=0;i<N;i++){
        cin>>S[i]>>T[i]>>X[i];
        event.push_back(make_tuple(S[i]-X[i],2,X[i],i));
        event.push_back(make_tuple(T[i]-X[i],1,X[i],i));
    }
    for(int i=0;i<Q;i++){
        cin>>D[i];
        event.push_back(make_tuple(D[i],3,-1,i));
    }
    sort(event.begin(),event.end());
    set<int>st{2147483647};
    for(int i=0;i<2*N+Q;i++){
        int tim=get<0>(event[i]);
        int key=get<1>(event[i]);
        int dis=get<2>(event[i]);
        int ind=get<3>(event[i]);
        if (key==2){
            st.insert(dis);
        }
        else if (key==1){
            st.erase(dis);
        }
        else{
            ans[ind]=*st.begin();
        }
    }
    for(int i=0;i<Q;i++){
        if (ans[i]==2147483647){
            cout<<-1<<endl;
        }
        else{
            cout<<ans[i]<<endl;
        }            
    }
}

Measured memory_bytes: 24420
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

from numba import njit


def getInputs():
    D = int(readline())
    CS = np.array(read().split(), np.int32)
    C = CS[:26]
    S = CS[26:].reshape((-1, 26))
    return D, C, S


@njit('(i8, i4[:], i4[:, :], i4[:], )', cache=True)
def _compute_score1(D, C, S, out):
    score = 0
    last = np.zeros(26, np.int32)
    for d in range(len(out)):
        i = out[d]
        score += S[d, i]
        last[i] = d + 1
        score -= np.sum(C * (d + 1 - last))
    return last, score


def _update_score():
    pass

@njit('(i8, i4[:], i4[:, :], i4[:], i8, )', cache=True)
def _random_update(D, C, S, out, score):
    d = np.random.randint(0, D)
    q = np.random.randint(0, 26)
    p = out[d]

    if p == q:
        return out, score

    out[d] = q
    _, new_score = _compute_score1(D, C, S, out)
    if score < new_score:
        score = new_score
    else:
        out[d] = p

    return out, score


@njit('(i8, i4[:], i4[:, :], i4[:], i8, i8, )', cache=True)
def _random_swap(D, C, S, out, score, delta):
    d1 = np.random.randint(0, D)
    d2 = np.random.randint(max(0, d1 - delta), min(D, d1 + delta))
    #p, q = out[[d1, d2]]
    p = out[d1]
    q = out[d2]

    if d1 == d2 or p == q:
        return out, score

    #out[[d1, d2]] = (q, p)
    out[d1] = q
    out[d2] = p
    _, new_score = _compute_score1(D, C, S, out)
    if score < new_score:
        score = new_score
    else:
        #out[[d1, d2]] = (p, q)
        out[d1] = p
        out[d2] = q

    return out, score



def step1(D, C, S):
    out = []
    LAST = 0
    for d in range(D):
        max_score = -10000000
        best_i = 0
        
        for i in range(26):
            out.append(i)
            last, score = _compute_score1(D, C, S, np.array(out, np.int32))
            if max_score < score:
                max_score = score
                LAST = last
                best_i = i
            out.pop()

        out.append(best_i)

    return np.array(out), LAST, max_score


def step2(D, C, S, out, score):
    for _ in range(48 * 10 ** 3):
        flag = np.random.rand() >= 0.5
        out = out.astype(np.int32)

        if flag:
            out, score = _random_update(D, C, S, out, score)
        else:
            out, score = _random_swap(D, C, S, out, score, 13)

    return out, score


def output(out):
    out += 1
    print('\n'.join(out.astype(str).tolist()))


D, C, S = getInputs()
out, _, score = step1(D, C, S)
#print(score)
out, score = step2(D, C, S, out, score)
output(out)
#print(score)

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

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

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

#define MAX 100005
#define INF 1001001001

int main(int, char**)
{
  set<int> a;
  int q;
  cin >> q;
  vector<int> ans;
  rep(i,q) {
    int command; cin >> command;
    if (command == 0) {
      int x; cin >> x;
      a.insert(x);
      ans.push_back(a.size());
    } else if (command == 1) {
      int x; cin >> x;
      ans.push_back(a.find(x) != a.end());
    } else if (command == 2) {
      int x; cin >> x;
      a.erase(x);
    }
  }

  for (auto a : ans) cout << a << endl;

  return 0;
}



Measured memory_bytes: 13020
#include <iostream>

using namespace std;

int main()
{
    int i, sum;
    int c[9];

    sum = 0;

    for (i = 0; i < 9; i++)
    {
        cin >> c[i];
        sum += c[i];
    }

    if (sum % 3 == 0 &&
        c[0] + c[8] == c[2] + c[6] &&
        c[0] + c[5] + c[7] == c[1] + c[3] + c[8] &&
        c[0] + c[5] + c[7] == c[0] + c[4] + c[8])
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
package main

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

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

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanWords)
	n := nextInt()
	A := make([]int, n)
	for i := 0; i < n; i++ {
		A[i] = nextInt()
	}

	part := partition(A, 0, n-1)
	for i := 0; i < n; i++ {

		if i == part {
			fmt.Printf("[%d] ", A[i])
		} else if i < n-1 {
			fmt.Printf("%d ", A[i])
		} else {
			fmt.Printf("%d\n", A[i])
		}
	}
}

func partition(A []int, p int, r int) int {
	x := A[r]
	i := p - 1
	for j := p; j < r; j++ {
		if A[j] <= x {
			i++
			t := A[i]
			A[i] = A[j]
			A[j] = t
		}
	}
	t := A[i+1]
	A[i+1] = A[r]
	A[r] = t
	//i+1がパーティションになっている
	return i + 1
}



Measured memory_bytes: 3168
public class Main {
  private static void solve() {
    int n = ni();
    int[][] p = ntable(n, 3);

    int[] now = new int[2];
    int t = 0;
    for (int[] q : p) {
      int d = Math.abs(now[0] - q[1]) + Math.abs(now[1] - q[2]);
      if (d <= q[0] - t && ((q[0] - t) - d) % 2 == 0) {
        now[0] = q[1];
        now[1] = q[2];
        t = q[0];
      } else {
        System.out.println("No");
        return;
      }
    }
    System.out.println("Yes");
  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}




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

#define REP(i,a) for(long i=0;i<(a);++i)
#define SORT(a) std::sort((a).begin(), (a).end())

//alias
typedef std::vector<int>  VI;

int N;
VI L;
int main() {
    std::cin >> N;
    L.resize(N*2);
    REP(i, N*2) {
        std::cin >> L[i];
    }

    SORT(L);

    int sum = 0;
    REP(i, N) {
        sum += L[i*2];
    }
    std::cout << sum << std::endl;
}

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

int main(){
    int a,b,c,x,y;
    cin >> a >> b >> c >> x >> y;
    long long ans = 0;
    if(x<y){
        int tmp=x;
        x = y;
        y = tmp;
        tmp = a;
        a = b;
        b = tmp;
    }
    if(a+b > 2*c){
        ans += y*c*2;
        x -=y;
        if(a>2*c){
            ans += x*2*c;
        }
        else{
            ans += x*a;
        }
    }
    else{
        ans += x*a+y*b;
    }
    cout << ans <<endl;
    return 0;
}

Measured memory_bytes: 256
H, W = map(int, input().split())
a = [list(input()) for _ in range(H)]

ans = [['#'] * (W + 2) for _ in range(H + 2)]
for i, ai in enumerate(a):
    for j, aij in enumerate(ai):
        ans[i + 1][j + 1] = aij

for ansi in ans:
    print(''.join(ansi))

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ll          long long
#define pb          push_back
#define mp 			make_pair
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define vii         vector<pii>
#define mi          map<ll,ll>
#define mii         map<pii,ll>
#define all(a)      (a).begin(),(a).end()
#define fi          firstn
#define si          second
#define sz(x)       (ll)x.size()
#define endl        '\n'
#define checkbit(n, b) ((n >> b) & 1)
#define mod        1000000007
#define puts(n)		cout<<n;
#define fr(i,l,u) 	for(i=l;i<=u;i++)
#define bk(i,l,u)	for(i=l;i>=u;i--)
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
ll posx[]={1,-1,0,0};
ll posy[]={0,0,1,-1};

bool vis[100001];
ll dp[100001];
vi v[100001];
void dfs(ll x)
{
    ll i;
    if(dp[x])
    return;
    dp[x]=1;
    for(i=0;i<v[x].size();i++)
    {
        dfs(v[x][i]);
        dp[x]=max(dp[x],1+dp[v[x][i]]);
    }
}

void solve()
{
    ll n,m,i;
    cin>>n>>m;
    ll x,y;
    while(m--)
    {
        cin>>x>>y;
        v[x].pb(y);
        vis[y]=1;
    }
    ll mx=0;
    for(i=1;i<=n;i++)
    {
        if(vis[i]==0)
        {
            dfs(i);
            mx=max(mx,dp[i]-1);
        }
    }
    cout<<mx;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}


Measured memory_bytes: 10368
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cassert>
#include <functional>
#include <string>
#include <sstream>
#include <cctype>
#include <queue>
#include <stack>
#include <map>
#include <iomanip>
using namespace std;
typedef long long ll;
#define rep(i, j, n) for (int i = j; i < n; i++)

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

class xy{
public:
  int x, y;
  xy() {x = y = 0;}
  xy(int u, int v) {x = u; y = v;}
};

bool compare_U(const pair<xy, bool> &u, const pair<xy, bool> &v)
{
  if(u.first.y == v.first.y) return u.first.x < v.first.x;
  return u.first.y < v.first.y;
}

bool compare_V(const pair<xy, bool> &u, const pair<xy, bool> &v)
{
  if(u.first.x == v.first.x) return u.first.y < v.first.y;
  return u.first.x < v.first.x;
}

void Main(){
  int N; cin >> N;
  vector<pair<xy, bool>> U, V;
  rep(i, 0, N){
    int x, y; cin >> x >> y;
    xy tmp(x, y);
    pair<xy, bool> p = make_pair(tmp, false);
    U.push_back(p);
  }
  rep(i, 0, N){
    int x, y; cin >> x >> y;
    xy tmp(x, y);
    pair<xy, bool> p = make_pair(tmp, false);
    V.push_back(p);
  }
  sort(U.begin(), U.end(), compare_U);
  sort(V.begin(), V.end(), compare_V);
  int res = 0;
  rep(i, 0, N){
    rep(j, 0, N){
      if(V[j].second) continue;
      if(U[N-i-1].first.x < V[j].first.x && U[N-i-1].first.y < V[j].first.y){
        U[N-i-1].second = true;
        V[j].second = true;
        res++;
        break;
      }
    }
  }
  cout << res << endl;
}

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

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  //cout << std::fixed << std::setprecision(15);

  Main();
}


Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using vb = vector<bool>;
using mll = map<ll, ll>;
using sll = stack<ll>;
#define REP(i,n) for(ll i(0);(i)<(n);(i)++)
#define rep(i,n) for(ll i(0);(i)<(n);(i)++)
#define ALL(a) a.begin(), a.end()
#define elnd endl //* missspell check
const ll INF = 1LL << 60;


void solve(std::string S, long long K){
    ll N = S.length();
    if(N==1){
        cout << K/2<<endl;
        return;
    }

    if(S.at(0) != S.back()){
        ll cnt = 0;
        ll i=0, j;
        while(i < N){
            j=i;
            while(j < N && S[j]==S[i])
                j++;
            //* now [i, j) has same
            cnt += (j-i)/2;
            i = j;
        }
        cout << cnt * K <<endl;
        return;
    }
    else{
        ll head=0, tail = N-1;
        while(head < N && S[head]==S[0])
            head ++;
        while(tail >= 0 && S[tail]==S[0])
            tail --;
        tail ++;
        if(tail==0){
            cout << (N*K)/2 << endl;
            return;
        }
        //* now [0, head) and [tail, N) all same
        ll cnt = 0;
        cnt += head/2 + (N-tail)/2;
        
        //* count inter-str
        cnt += (head + N-tail)/2 * (K-1);

        //* count inner-str
        string Short = S.substr(head, tail-head);

        ll cnt_short = 0;
        ll i=0, j;
        while(i < Short.length()){
            j=i;
            while(j < Short.length() && Short[j]==Short[i])
                j++;
            //* now [i, j) has same
            cnt_short += (j-i)/2;
            i=j;
        }
        cnt += cnt_short * K;
        cout << cnt <<endl;
        return;
    }
}

int main(){
    std::string S;
    std::cin >> S;
    long long K;
    scanf("%lld",&K);
    solve(S, K);
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
  int N;
  cin >> N;
  vector<int> num(N);
  for (auto &i : num){
    cin >> i;
  }
  
  int j = 0;
  bool flag = 1;

  while (flag){
    for (int i=0; i<N; i++){
      if (num.at(i) % 2 != 0 ){
        cout << j;
        flag = false;
        break;
      }
      else {
        num.at(i) = num.at(i) / 2;
      }
    }
    j++;
  }
      
  return 0;
}

Measured memory_bytes: 256
from collections import Counter
MOD = 998244353

N = int(input())
D = list(map(int, input().split()))
C = Counter(D)
if D[0] != 0 or C[0] != 1:
    print(0)
    exit()
ans = 1
for i in range(1, max(D)+1):
    if C[i] == 0:
        ans = 0
        break
    else:
        ans *= pow(C[i-1], C[i], MOD)
        ans %= MOD
print(ans)


# import sys
# sys.setrecursionlimit(10000000)
# def input():
#     return sys.stdin.readline()[:-1]
# from bisect import *
# from collections import *
# from heapq import *
# import functools
# import itertools
# import math
# INF = float('inf')
# # MOD = 10**9+7
# MOD = 998244353
#
# N = int(input())
# D = list(map(int, input().split()))
# if D[0] != 0:
#     print(0)
# C = Counter(D)
# ans = 1
# for i in range(1, max(D)+1):
#     if C[i] == 0:
#         ans = 0
#         break
#     else:
#         ans *= pow(C[i-1], C[i], MOD)
#         ans %= MOD
# print(ans)


Measured memory_bytes: 19936
#include <bits/stdc++.h>
        using namespace std;
        #define int long long
const int MAX = 510000;
const int MOD = 1000000007;

        signed main() {
        int n,m;
        cin>>n>>m;
        if(n==m)cout<<"Yes";
        else cout<<"No";
        
         return 0;

        }


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
using namespace std;
int n,a,b,c,l,ll;
int main()
{
  cin>>n;
  for(int i=0;i<n;i++)
  {
    cin>>a>>b>>c;
    l=b+c;
    if(l>a){cout<<"No"<<endl;return 0;}
    ll=a-l;
    if(ll%2>0){cout<<"No"<<endl;return 0;}
  }
  cout<<"Yes"<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
using ll=long long;
 
#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 pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
const ll MOD = 1e9 + 7;

int main() {
    int h, n;
    cin >> h >> n;
    vector<int> as(n), bs(n);
    rep(i, n) cin >> as[i] >> bs[i];
    vector<int> dp(h+1, numeric_limits<int>::max());
    rep(i, n) {
        rep(j, h+1) {
            int pd = j > as[i] ? dp[j-as[i]] : 0; 
            dp[j] = min(dp[j], pd + bs[i]);
        }
    }
    cout << dp[h] << endl;
    return 0;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val N = readLine()!!.toInt()
    val S = readLine()!!
    val T = IntArray(N).apply { this[0] = if (S[0] == 'W') 1 else 0 }
    val U = IntArray(N).apply { this[N - 1] = if (S[N - 1] == 'E') 1 else 0 }

    for (i in 1 until N) {
        T[i] = T[i - 1] + if (S[i] == 'W') 1 else 0
        U[N - 1 - i] = U[N - i] + if (S[N - 1 - i] == 'E') 1 else 0
    }

    val a = IntArray(N).apply { this[0] = U[1]; this[N - 1] = T[N - 2] }
    for (i in 1 until N - 1) {
        a[i] = T[i - 1] + U[i + 1]
    }
    println(a.min())
}

Measured memory_bytes: 41844
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

ll solve(ll n, ll d)
{
    if(d==1) return n*(n-1)/2;

    ll r = n-(d+1);
    return d + r*3 + r*(r-1)/2;
}

int main()
{
    ll n,d;
    cin >>n >>d;
    cout << solve(n,d) << endl;
    return 0;
}

Measured memory_bytes: 3100
import java.util.ArrayList;
fun main(args: Array<String>) {
    val (N, X) = readLine()!!.split(" ").map(String::toInt)
    val x = java.util.ArrayList(readLine()!!.split(" ").map(String::toInt))
    x.add(X)
    x.sort()
    var ans = x[1] - x[0]
    for (i in 2..N) {
        val d = x[i] - x[i-1]
        ans = if (ans > d) gcd(ans, d) else gcd(d, ans)
    }
    println(ans)
}

tailrec fun gcd(big: Int, small: Int): Int =
    if (small == 0) big else gcd(small, big % small)

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

using namespace std;

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

  int x, n;
  cin >> x >> n;

  if (n == 0) {
    cout << x << '\n';
    return 0;
  }

  vector<int> p(n);
  for (int i = 0; i < n; ++i) {
    cin >> p[i];
  }
  sort(p.begin(), p.end());

  int cnt = 0;
  int dist = 999;
  int ans = -100;
  for (int i = -100; i <= 200; ++i) {
    if (i == p[cnt]) {
      ++cnt;
      continue;
    }
    if (dist > abs(x - i)) {
      dist = abs(x - i);
      ans = i;
    }
  }

  cout << ans << '\n';

  return 0;
}


Measured memory_bytes: 3656