akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int H = sc.nextInt();
		int M = sc.nextInt();

		//ここから角度を求める計算
		double minAngle = (double)M * 6;
		double onlyHour = (double)H * 30;
		double hourAngle = onlyHour + (double)M * 0.5;
		double angle = Math.abs(minAngle - hourAngle);
		if(angle > 180)
		angle = 360 - angle;

		//ここから長さを求める計算
		double ans = Math.sqrt(A * A + B * B - 2 * A * B * Math.cos(Math.toRadians(angle)));
		System.out.println(ans);
    }
}

Measured memory_bytes: 35836
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<tuple>
#include<map>
#include<queue>
#include<math.h>
#include<iomanip>
#define rep(i, n) rep2(i,0,n)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define PI acos(-1);
typedef long long ll;
using namespace std;
#define MOD 1000000007
//scanf("%d", &a) '\n'

int main() {
	string s;
	cin >> s;
	int n = s.size();
	if (s[0] != 'k') { cout << "NO"; return 0; }
	if (s[n-1] != 'e') { cout << "NO"; return 0; }
	if(s.substr(n-6,6)=="eyence"){ cout << "YES"; return 0; }
	if (s.substr(n-5, 5) == "yence"&&s[1]=='e') { cout << "YES"; return 0; }
	if (s.substr(n-4, 4) == "ence"&&s.substr(1,2)== "ey") { cout << "YES"; return 0; }
	if (s.substr(n-3, 3) == "nce"&&s.substr(1, 3) == "eye") { cout << "YES"; return 0; }
	if (s.substr(n-2, 2) == "ce"&&s.substr(1, 4) == "eyen") { cout << "YES"; return 0; }
	if (s.substr(1,5) == "eyenc") { cout << "YES"; return 0; }
	cout << "NO";
	
}
	

Measured memory_bytes: 256
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
#include <cassert>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 1e3 + 10;
int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int a, b, t;
	cin >> a >> b >> t;
	cout << t / a * b << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(), (x).end()
#define dbg(x) cerr << #x << ": " << x << endl
int main() {
  int n, m, x;
  cin >> n >> m >> x;
  vector<int> a(m);
  rep(j, m) cin >> a[j];
  sort(all(a));
  int cfw = 0, cbw = 0;
  for(int i = x; i <= n; i++) rep(j, m) if(i == a[j]) cfw++;
  for(int i = x; i >= 0; i--) rep(j, m) if(i == a[j]) cbw++;
  cout << min(cfw, cbw) << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;
int main(void) {
	int N, K, X, Y;
	cin >> N >> K >> X >> Y;
	int charge = 0;
	
	if (N < K) {
		for (int i = 0; i < N; i++) {
			charge += X;
		}
		cout << charge << endl;
		return 0;
	}
	for (int i = 1; i <= K; i++) {
		charge += X;
	}
	for (int i = K + 1; i <= N; i++) {
		charge += Y;
	}
	cout << charge << endl;
	return 0;
}

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

#define li long long int
#define rep(i, to) for (li i = 0; i < ((li)(to)); i++)
#define repp(i, start, to) for (li i = (li)(start); i < ((li)(to)); i++)

#define F first
#define S second

typedef pair<li, li> PI;


int main(void)
{
	set<string> st;
	string s;
	cin >> s;
	li k;
	cin >> k;
	li n = s.size();
	rep(i, n) {
		rep(j, min(5ll, n - i)) {
			st.insert(s.substr(i, j + 1));
		}
	}
	rep(i, k - 1) {
		string f = *st.begin();
		st.erase(f);
	}
	cout << *st.begin() << endl;



	return 0;
}

Measured memory_bytes: 4780
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  string o, e;
  cin >> o >> e;
  string ans = "Yes";
  for(int i=0; i<o.length(); i++){
    if(o[i]!=e[i]) ans = "No";
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
#include <vector>
using namespace std;

int main() {
    int n;
    cin>>n;
    string s;
    long long int c[5]={0};
    for(int i=0;i<n;i++){
        cin>>s;
        if(s[0]=='M') c[0]++;
        if(s[0]=='A') c[1]++;
        if(s[0]=='R') c[2]++;
        if(s[0]=='C') c[3]++;
        if(s[0]=='H') c[4]++;
    }
    long long int a=0;
    for(int i=0;i<3;i++){
        for(int j=i+1;j<4;j++){
            for(int k=j+1;k<5;k++){
                a+=c[i]*c[j]*c[k];
            }
        }
    }
    cout<<a<<endl;
   
    
    return 0;

 }

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

using namespace std;

#define REP(i,n) for(int i = 0; i < (n); ++i)
#define P(x) cout << (x) << "\n"
#define D(x) cerr << (x) << "\n"
#define fcout cout << fixed << setprecision(18)

using i64=long long int; // 10^18
int n;
const int SIZE = 100001;
int dp[SIZE][3],a[SIZE], b[SIZE], c[SIZE];
// 0-indexed
// dp[0]=0
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n;
    REP(i,n){
        cin>>a[i+1]>>b[i+1]>>c[i+1];
    }
    for(int i=1;i<=n;++i){
        dp[i][0]=max(dp[i-1][1]+a[i], dp[i-1][2]+a[i]);
        dp[i][1]=max(dp[i-1][0]+b[i], dp[i-1][2]+b[i]);
        dp[i][2]=max(dp[i-1][0]+c[i], dp[i-1][1]+c[i]);
    }
    P(max(dp[n][0], max(dp[n][1], dp[n][2])));
    return 0;
}

Measured memory_bytes: 2560
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
#include<limits.h>
#include<unordered_map>
#include<unordered_set>
#include<deque>
#include<cstdio>
using namespace std;
typedef long long int ll;
const int N = 1000000;
const int INF = 1 << 30;
#define rep(i,n) for(int i=(ll)0;i<(ll)n;++i)
#define ALL(x) x.begin(),x.end()
#define pp pair<ll,ll>
string YN(bool b) { return(b ? "YES" : "NO"); }
string yn(bool b) { return(b ? "Yes" : "No"); }
int main(){
	ll n, m,ans=0;
	cin >> n >> m;
	ans += 1900 * m + 100 * (n - m);
	cout << pow(2, m) * ans << endl;
	return 0;
}

Measured memory_bytes: 512
n, m = gets.chomp.split.map(&:to_i)
li = []
ri = []
for i in 0...m do
  l, r = gets.chomp.split.map(&:to_i)
  li << l
  ri << r
end
if (ri.min - li.max) >= 0 then
  puts ri.min - li.max + 1
else
  puts 0
end

Measured memory_bytes: 3456
def tsep(x,y):
    m=x*y
    for i in range(1,y):
        s=[i*x,(y-i)*(x-x//2),(y-i)*(x//2)]
        m=min(m,max(s)-min(s))
    return m
H,W=map(int,input().split())
if H%3==0 or W%3==0:
    print(0)
    exit()
print(min(W,H,tsep(H,W),tsep(W,H)))


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
#define MOD 1000000007LL
#define INF 1000000000ll
#define EPS 1e-10
#define FOR(i,n,m) for(ll i=n;i<(ll)m;i++)
#define REP(i,n) FOR(i,0,n)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v) sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back

ll N = 200020;
ll bit[200020];
void add(ll a, ll w) {
	a++;
	for (ll x = a; x <= N; x += x & -x) bit[x] += w;
}
ll sum(ll a) {
	a++;
	ll ret = 0;
	for (ll x = a; x > 0; x -= x & -x) ret += bit[x];
	return ret;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll N,X;
	cin>>N>>X;
	vector<ll> x(N);
	REP(i,N) cin>>x[i];
	REP(i,N) add(i,x[i]);
	__int128 ans=INF*INF;
	for(ll c=1; c<=N; c++) {
		__int128 tmp=N*X;
		tmp+=c*X;
		__int128 num=1;
		ll pos=N;
		while(1) {
			ll l=max(0LL,pos-c);
			ll r=pos;
			__int128 ss=sum(r-1);
			if(l!=0) ss-=sum(l-1);
			if(num==1) tmp+=ss;
			if(num==1) tmp+=ss;
			tmp+=ss*(2*num+1);
			//cout<<c<<" "<<(ll)num<<" "<<(ll)tmp<<endl;
			if(l==0) break;
			num++;
			pos=l;
		}
		if(c==1) ans=tmp;
		else ans=min(ans,tmp);
		//cout<<c<<" "<<(ll)ans<<endl;
	}
	cout<<(ll)ans<<endl;
	return 0;
}



Measured memory_bytes: 3328
#include <iostream>
#include <cmath>
#include <vector> 
#include <algorithm>
#include <limits>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

ll N,W;

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

int main(){
  cin >> N >> W;
  vector<pll> goods(N);
  ll V=0;
  ll v_max = 0;
  
  for(ll i=0; i<N; i++){
    pll init; 
    cin >> init.first >> init.second;
    goods[i] = init;
    V += init.second;
    chmax(v_max, init.second);
  }

  ll ll_inf = 1LL<<60;
  
  vector<vector<ll>> dp(N+1, vector<ll>(V+1,ll_inf));
  dp[0][0] = 0;
  
  for(ll i=0; i<N; i++){
    for(ll j=0; j<=V; j++){
      ll v = j-goods[i].second;
      if(v>=0) chmin(dp[i+1][j], dp[i][v]+goods[i].first);
      chmin(dp[i+1][j], dp[i][j]);
    }
  }
  
  ll ans=0;
  for(ll j=0; j<=V; j++){
    if(dp[N][j]<=W) ans = j;
  }
  
  cout << ans << "\n";
}

Measured memory_bytes: 80256
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	int n; scanf("%d", &n); std::vector<int> a(n);
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);

	i64 s = 0, tmp = 0;
	for(auto v: a) s += v;

	i64 ans = 1LL << 60;
	for(int i = 0; i < n - 1; i++) {
		tmp += a[i];

		i64 X = tmp, Y = s - tmp;
		ans = std::min(ans, std::abs(X - Y));
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <fstream>
#include <iomanip>

typedef long long ll;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1e9 + 7;

template<class T> std::ostream& operator << (std::ostream& os, std::vector< T > v)
{
  ll i = 0;
  for (auto x : v) {os << " [" << i++ << "]" << x; if (i % 10 == 0) os << std::endl;}
  return os;
}

template<class T, class S> std::ostream& operator << (std::ostream& os, std::vector< std::pair<T, S> > vp)
{
  ll i = 0;
  for (auto p : vp) {os << " [" << i++ << "]" << p.first << " " << p.second; if (i % 10 == 0) os << std::endl;}
  return os;
}

void print(){ std::cout << std::endl; }
template<typename H> void print(H head) { std::cout << head << std::endl; }
template<typename H, typename... T> void print(H head, T... tail){ std::cout << head << " ", print(tail...); }

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

  ll N;
  std::cin >> N;
  std::vector< ll > vx(N, 0LL);
  for (ll i = 0; i < N; i++) {
    std::cin >> vx[i];
  }

  std::vector< std::pair<ll, ll> > vp(N, std::make_pair(INF, INF));
  for (ll i = 0; i < N; i++) {
    vp[i].first  = vx[i];
    vp[i].second = i;
  }

  std::sort(vp.begin(), vp.end());
  ll mid  = vp[(N+1)/2-1].first;
  ll mid2 = vp[(N+1)/2].first;

  std::vector< ll > vans(N, 0LL);
  for (ll i = 0; i < N; i++) {
    if (vx[i] > mid) {
      vans[i] = mid;
    } else {
      vans[i] = mid2;
    }
  }

  for (auto ans : vans) {
    print(ans);
  }

  return 0;
}


Measured memory_bytes: 8448
#include <bits/stdc++.h> //AtCoder
#include <iostream> //Codeforces
#include <vector> //Codeforces

#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repeq(i,a,b) for(int i=a;i<=b;i++)
#define Vi vector<int>
#define VVi vector<Vi>
#define Vs vector<string>
#define Vc vector<char>
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define cyes cout<<"yes"<<endl
#define cno cout<<"no"<<endl

using namespace std;

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

/****************************** START ******************************/

signed main(){
  string S,T;
  cin >> S >> T;
  int min = T.size();
  int d = 0; 
  rep(i,0,S.size()-T.size()+1){
    d = 0;
    rep(j,0,T.size()){
      if (S.at(i+j) != T.at(j)){
        d++;
      }
    }
    //cout << d << endl;
    if (d < min){
      min = d;
    }
  }
  cout << min;
}
  


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

int main() {
  int N, p, w, g, y = 0;
  string s;
  cin >> N;
  
  for(int i = 0; i < N; i++) {
    cin >> s;
    if (s == "P")
      p++;
    else if (s == "W")
      w++;
    else if (s == "G")
      g++;
    else if (s == "Y")
      y++;
  }
  
  if (p * w * g * y == 0) 
    cout << "Three" << endl;
  else
    cout << "Four" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <tuple>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <cstdio>
#include <numeric>
#define REP(i, n) for(LL i = 0;i < n;i++)
#define REPR(i, n) for(LL i = n;i >= 0;i--)
#define FOR(i, m, n) for(LL i = m;i < n;i++)
#define FORR(i, m, n) for(LL i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()
#define INF 999999999
#define MOD 1000000007
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
typedef pair<LL, LL> LP;
typedef pair<int, P> PP;
typedef pair<LL, LP> LPP;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

/*************** using variables ***************/
int w;
int a, b;
/**********************************************/

int main(){
    cin >> w >> a >> b;
    if((b >= a && b <= a+w) || (b+w >= a && b+w <= a+w)){
        cout << 0 << endl;
    }else
    cout << min(abs(a+w - b), abs(a - (b+w))) << endl;
}


Measured memory_bytes: 256
import math
N, K=map(int,input().split())
A=list(map(int,input().split()))

def judge(ans,K,A):
    cut=0
    for i in range(len(A)):
        cut+=(A[i]-1)//ans
    if cut>K:
        return False
    else:
        return True


ansp=max(A)
ansm=0
ans=(ansp+ansm)//2
d=1
while ansp-ansm>d:
    
    if judge(ans,K,A):
        ansp=ans
        
    else:
        ansm=ans
        
    ans=(ansp+ansm)//2
print(ansp)

Measured memory_bytes: 30972
n,k=map(int, input().split())
mod=10**9+7
def conbi(n,r,mod):
    ue=1
    for i in range(n-r+1,n+1):
        ue*=i
        ue%=mod
 
    sita=1
 
    for i in range(1,r+1):
        sita*=i
        sita%=mod
 
    sita=pow(sita,mod-2,mod)
 
    return (ue*sita)%mod
for i in range(1,k+1):
    ans=conbi(n-k+1,i,mod)*conbi(k-1,i-1,mod)
    print(ans%mod)


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

using namespace std;

int main() {
    int N;
    cin>>N;
    double x[N],y[N];
    for(int i=0;i<N;i++){
        cin>>x[i]>>y[i];
    }
    vector<int>arrayy;
    for(int i=0;i<N;i++){
        arrayy.push_back(i);
    }
    double sum=0;
    do{
        for(int i=0;i<N-1;i++){
            sum+=sqrt((x[arrayy[i+1]]-x[arrayy[i]])*(x[arrayy[i+1]]-x[arrayy[i]])+(y[arrayy[i+1]]-y[arrayy[i]])*(y[arrayy[i+1]]-y[arrayy[i]]));
        }


    }while(next_permutation(arrayy.begin(),arrayy.end()));
    double ll=1;
    for(int i=1;i<=N;i++){
        ll*=i;
    }
    cout<<setprecision(10)<<scientific<<sum/ll<<endl;


}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define st first
#define nd second

using ll = long long ;
using namespace std;
using pii = pair<int,int>;
const int N = 2e5 + 10;
struct Plane{
	int x;
	int y;
	int dir;
}plane[N];
vector<pii> ud[N], lr[N], xpy[2 * N], xmy[2 * N]; 
int main(){
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		char s[2];
		scanf("%d %d %s", &plane[i].x, &plane[i].y, s);
		if(s[0] == 'U') plane[i].dir = 0;
		else if(s[0] =='D') plane[i].dir = 1;
		else if(s[0] == 'R') plane[i].dir = 2;
		else plane[i].dir = 3;
		if(plane[i].dir < 2) ud[plane[i].x].push_back({plane[i].y, plane[i].dir});
		else lr[plane[i].y].push_back({plane[i].x, plane[i].dir});
		xpy[plane[i].x + plane[i].y].push_back({plane[i].y, plane[i].dir});
		xmy[plane[i].x - plane[i].y + (int)2e5].push_back({plane[i].y, plane[i].dir});
	}
	int ans = 5 * N;
	for(int i = 0; i <= 2e5; i++){
		if(ud[i].empty()) continue;
		sort(ud[i].begin(), ud[i].end());
		int m_u = -6e5;
		for(auto it: ud[i]){
			if(it.nd == 0) m_u = it.st;
			else ans = min(ans, it.st - m_u);
		}

	}
	for(int i = 0; i <= 2e5; i++){
		if(lr[i].empty()) continue;
		sort(lr[i].begin(), lr[i].end());
		int m_r = -6e5;
		for(auto it: lr[i]){
			if(it.nd == 2) m_r = it.st;
			else ans = min(ans, it.st - m_r);
		}
	}
	//printf("still here");
	for(int i = 0; i <= 4e5; i++){
		if(xpy[i].empty()) continue;
		sort(xpy[i].begin(), xpy[i].end());
		int m_u = -6e5, m_l = -6e5;
		for(auto it: xpy[i]){
			if(it.nd == 0) m_u = it.st;
			else if(it.nd == 1) ans = min(ans, 2 * (it.st - m_l));
			else if(it.nd == 2) ans = min(ans, 2 * (it.st - m_u));
			else m_l = it.st;
		}
	}
	for(int i =0; i <= 4e5; i++){
		if(xmy[i].empty()) continue;
		sort(xmy[i].begin(), xmy[i].end());
		int m_u = -6e5, m_r = -6e5;
		for(auto it: xmy[i]) {
			if(it.nd == 0) m_u = it.st;
			else if(it.nd == 1) ans = min(ans, 2 * (it.st - m_r));
			else if(it.nd == 2) m_r = it.st;
			else ans = min(ans, 2 * (it.st - m_u));
		}
	}
	if(ans > 4e5) return !printf("SAFE");
	printf("%d", 5 * ans);
	


}

Measured memory_bytes: 52752
//https://atcoder.jp/contests/abc160/tasks/abc160_b
#include <bits/stdc++.h>
#if LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif
using namespace std;
using ll=long long;
const ll LINF = 0x1fffffffffffffff;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
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() {
  ll X; cin>>X;
  ll ans=0;
  ll num=X/500;
  ans += num*1000;
  ll xx=X-500*num;
  ans += (xx/5)*5;
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <cassert>
using namespace std;
using ll = long long;


int main() {
	int n, m; cin >> n >> m;
	vector<pair<int, int>> p(n);
	for (int i = 0; i < n; i++) cin >> p[i].second >> p[i].first;
	sort(p.rbegin(), p.rend());
	set<int> s;
	for (int i = 1; i <= m; i++) s.insert(i);
	int ans = 0, cnt = 0;
	for (int i = 0; i < n; i++) {
		auto itr = s.lower_bound(p[i].second);
		if (itr == s.end()) continue;
		s.erase(*itr);
		ans += p[i].first;
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 5760
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-9;

int main() {
	for (;;) {
		int n; cin >> n;
		if (n == 0) break;
		vector<int> a(n);
		for (int i = 0; i < n; i++) {
			string s; cin >> s;
			if (s == "x") a[i] = INT_MAX;
			else {
				stringstream ss(s);
				ss >> a[i];
			}
		}
		bool flag = true;
		for (int i = 0; i + 1 < n; i++) {
			if (a[i] == INT_MAX && a[i + 1] == INT_MAX)
				flag = false;
			if (a[i] != INT_MAX && a[i + 1] != INT_MAX) {
				if (i % 2 == 0 && a[i] >= a[i + 1])
					flag = false;
				if (i % 2 == 1 && a[i] <= a[i + 1])
					flag = false;
			}
		}
		if (!flag) {
			cout << "none" << endl;
			continue;
		}
		int mini = INT_MIN, maxi = INT_MAX;
		for (int i = 0; i < n; i++) {
			if (a[i] == INT_MAX) {
				if (i % 2 == 0) {
					if (i - 1 >= 0) maxi = min(maxi, a[i - 1] - 1);
					if (i + 1 < n) maxi = min(maxi, a[i + 1] - 1);
				}
				else {
					if (i - 1 >= 0) mini = max(mini, a[i - 1] + 1);
					if (i + 1 < n) mini = max(mini, a[i + 1] + 1);
				}
			}
		}
		if (mini == maxi && mini > INT_MIN) cout << mini << endl;
		else if (mini < maxi || mini == INT_MIN) cout << "ambiguous" << endl;
		else cout << "none" << endl;
	}
}

Measured memory_bytes: 1228
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin >> n;
	int a[55];
	for(int i=0;i<n;i++) 
		cin >> a[i] ;
	long long s=0;
	for(int i=0;i<n;i++) {
		for(int j=i+1;j<n;j++) {
			s+=(a[i]*a[j]) ;
		}
	}
	cout << s<<endl;
	return 0;
}



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

int main(){
  int n;
  cin >> n;
  bool ans = false;
  rep(i, 10){
    if(n % i == 0){
      if(n / i < 10){
        ans = true;
        break;
      }
    }
  }
  if(ans){
    std::cout << "Yes" << '\n';
  }
  else{
    std::cout << "No" << '\n';
  }
  return 0;
}

Measured memory_bytes: 256
A,B,C,X,Y = map(int,input().split())
ans = A*X+B*Y
if X < Y:
    ans = min(ans,2*C*X+(Y-X)*B)
elif X > Y:
    ans = min(ans,2*C*Y+(X-Y)*A)
else:
    ans = min(ans,2*C*X)
ans = min(ans,2*C*max(X,Y))
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
bool check;
int main()
{
	string s1,s2;
	cin>>s1>>s2;
	int a,b;
	cin>>a>>b;
	string s3;
	cin>>s3;
	for(int i=0;i<s3.size();i++)
	{
		if(s1[i]==s3[i]) 
	  check=1;
	}
	if(check)
		cout<<a-1<<" "<<b;
	else cout<<a<<" "<<b-1;	
	return 0;
 } 

Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int a,b,c[100],d,e;
  int i,j,k;
  char z;
  while(scanf("%d %d\n",&a,&b)){
    if((a|b)==0) break;
    for(i=0;i<100;i++)c[i]=-1;
    for(i=0;i<b;i++){
      z=getchar();
      if(z=='s'){
        scanf(" %d %d\n",&d,&e);
        for(j=0;j<(a-e+1);j++){
          if(c[j]==-1){
            for(k=1;k<e;k++) if(c[j+k]!=-1) break;
            if(k==e){
              for(k=0;k<e;k++)c[j+k]=d;
              break;
            } 
          }
        }
        if(j==(a-e+1)) printf("impossible\n");
        else printf("%d\n",j);
      }
      if(z=='w'){
        scanf(" %d\n",&d);
        for(j=0;j<a;j++) if(c[j]==d) c[j]=-1;
      }
    }
  printf("END\n");
  }
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;

int main() {
    lint a, b, c;
    cin >> a >> b >> c;

    lint left = a * b * 4;
    lint right = (c - a - b) * (c - a - b);
    if(c - a - b < 0) {
        cout << "No" << endl;
        return 0;
    }

    cout << (left < right ? "Yes" : "No") << endl;
}

Measured memory_bytes: 384
Module _20191029

    Sub Main()
        'https://atcoder.jp/contests/abc144/tasks/abc144_c

        Dim iRead As Long = CLng(Console.ReadLine())
        Dim iOrgNumber As Long = iRead

        If iRead Mod 2 = 0 Then

            iRead -= 1

        End If

        '平方根
        Dim iKijun As Long = Math.Sqrt(iOrgNumber)

        Dim iNumber1 As Long = iKijun
        Dim iNumber2 As Long = iRead - iKijun

        Dim x As Long
        Dim y As Long

        For i As Long = iKijun To 1 Step -1

            If iOrgNumber Mod i = 0 Then

                x = i

                y = iOrgNumber \ i

                Exit For

            End If

        Next

        Console.WriteLine(x + y - 2)


    End Sub

End Module

Measured memory_bytes: 13268
#include <stdio.h>
#define N 100000
int main(void){
    int n,q,i,j,temp;
    int a[N],b,e;
    
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d",&a[i]);
    scanf("%d",&q);
    for(i=0;i<q;i++){
        scanf("%d %d",&b,&e);
        for(j=0;j<(e-b)/2;j++){
            temp=a[b+j];
            a[b+j]=a[e-j-1];
            a[e-j-1]=temp;
        }
    }
    for(i=0;i<n;i++) {
        printf("%d",a[i]);
        if(i!=n-1) printf(" ");
    }
    printf("\n");
    return 0;
}


Measured memory_bytes: 2104
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <iomanip>
#include <vector>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <ctime>
#include <fstream>
#include <stdarg.h>
using namespace std;
const bool debug=false;
const bool INJUDGE=false;
#define FASTERCIN cin.tie(0);ios_base::sync_with_stdio(false)
typedef long long ll;
/*Time:
Status:
Type:
Author:*/
int n;
int ans=2e9;
int a,b;
int sum1,sum2;
int main(){
	cin>>n;
	for(int a=1;a<n;a++){
		b=n-a;
		sum1=sum2=0;
		int t1=a,t2=b;
		while(t1){
			sum1+=t1%10;
			t1/=10;
		}
		while(t2){
			sum2+=t2%10;
			t2/=10;
		}
		ans=min(ans,sum1+sum2);
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>

using namespace std;

int main() {
  int N, K;
  cin >> N >> K;
  int x = 1;
  for (int i = 0; i < N; i++) {
    x = min(2 * x, x + K);
  }
  cout << x << endl;
  return 0;
}


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


int a(int num) {
	int dig;
	int sum = 0;

	while (num) {
		dig = num % 10;
		sum = sum + dig;
		num = num / 10;
	}
	return sum;
}

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

	int ans = 100000;
	for (int i = 1; i <= N / 2; ++i) {
		ans = min(ans, a(i) + a(N - i));
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
s1=input()
s2=input()
mp=[[0]*(len(s1)+1) for _ in range(len(s2)+1)]
#この問題でも先に0を用意
for n in range(1,len(s2)+1):
    mp[n][0]+=mp[n-1][0]+1
for m in range(1,len(s1)+1):
    mp[0][m]+=mp[0][m-1]+1

for i in range(1,len(s2)+1):
    for j in range(1,len(s1)+1):
        mp[i][j]=min(mp[i-1][j]+1,
                    mp[i][j-1]+1,
                    mp[i-1][j-1]+(s1[j-1]!=s2[i-1]))
print(mp[-1][-1])


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

int n,cnt;
vector<int> G[100000];
bool visited[2][100000];
int d[2][100000];

int dfs(int c,int r){
    for(int i = 0;i < G[r].size();i ++){
        int x = G[r][i];
        if(visited[c][x]) continue;
        d[c][x] = d[c][r] + 1;
        visited[c][x] = 1;
        dfs(c,x);
    }
}

int main(){
    cin >> n;
    for(int i = 0;i < n-1;i ++){
        int a,b;
        cin >> a >> b;
        a --;b --;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    visited[0][0] = 1;
    visited[1][n-1] = 1;

    dfs(0,0);
    dfs(1,n-1);

    for(int i = 0;i < n;i ++){
        if(d[0][i]<=d[1][i]) cnt ++;
    }
    if(cnt>n/2) cout << "Fennec" << endl;
    else cout << "Snuke" << endl;

    return 0;
}

Measured memory_bytes: 14464
#include <iostream>
#include <map>
typedef long long ll;
using namespace std;

// 素数 -> 個数
map<ll, ll> mp;

// 素数
map<ll, bool> prime;

bool isPrime(ll n) {
    if (prime.find(n) != prime.end()) return prime[n];
    if (n == 2) {
        prime[2] = true;
        return true;
    }
    else {
        bool flg = true;
        for (ll i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                flg = false;
                break;
            }
        }
        prime[n] = flg;
        return flg;
    }
}
void prime_split(ll n) {
    ll gen = 2;
    while (true) {
        if (isPrime(gen)) {
            if (mp.find(gen)==mp.end()) mp[gen] = 0;
            while (n % gen == 0) {
                n /= gen;
                mp[gen] += 1;
            }
        }
        if (n == 1) break;
        gen++;
    }
}
int main(void) {
    int N;cin>>N;
    ll result = 1;
    for (int i = 2; i <= N; i++) {
        prime_split(i);
    }
    for (map<ll,ll>::iterator it = mp.begin(); it != mp.end(); ++it) {
        result *= it->second + 1;
        result %= 1000000007;
    }
    cout << result << endl;
    return 0;
}

Measured memory_bytes: 3208
import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long t[]=new long[n];
        for (int i=0;i<n;++i) t[i]=sc.nextLong();
        int m=sc.nextInt();
        int p[]=new int[m];
        long x[]=new long[m];
        for (int i=0;i<m;++i)
        {
            p[i]=sc.nextInt();
            x[i]=sc.nextLong();
        }

        for (int i=0;i<m;++i)
        {
            int ans=0;
            for (int j=0;j<n;++j)
            {
                long tt=t[j];
                if (j==p[i]-1)
                {
                    tt=x[i];
                }
                ans+=tt;
            }
            System.out.println(ans);
        }
    }
}

Measured memory_bytes: 21844
#include <iostream>
#include <string>

using namespace std;

void solve()
{
	string s;
	char c;
	while(cin >> s >> c)
	{
		string ans;
		if(c == 'X')
		{
			break;
		}
		else if(c == 'L')
		{
			if('A' <= s[0] && s[0] <= 'Z')
			{
				ans += s[0] - 'A' + 'a';
			}
			else
			{
				ans += s[0];
			}
			bool underbar_flag = false;
			for(int i = 1; i < s.size(); ++i)
			{
				if(underbar_flag)
				{
					ans += s[i] - 'a' + 'A';
					underbar_flag = false;
				}
				else if(s[i] != '_')
				{
					ans += s[i];
				}
				else if(s[i] == '_')
				{
					underbar_flag = true;
				}
			}
		}
		else if(c == 'U')
		{
			if('a' <= s[0] && s[0] <= 'z')
			{
				ans += s[0] - 'a' + 'A';
			}
			else
			{
				ans += s[0];
			}
			bool underbar_flag = false;
			for(int i = 1; i < s.size(); ++i)
			{
				if(underbar_flag)
				{
					ans += s[i] - 'a' + 'A';
					underbar_flag = false;
				}
				else if(s[i] != '_')
				{
					ans += s[i];
				}
				else if(s[i] == '_')
				{
					underbar_flag = true;
				}
			}
		}
		else if(c == 'D')
		{
			if('A' <= s[0] && s[0] <= 'Z')
			{
				ans += s[0] - 'A' + 'a';
			}
			else
			{
				ans += s[0];
			}
			for(int i = 1; i < s.size(); ++i)
			{
				if('A' <= s[i] && s[i] <= 'Z')
				{
					ans += '_';
					ans += s[i] - 'A' + 'a';
				}
				else
				{
					ans += s[i];
				}
			}
		}
		cout << ans << endl;
	}
}

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

Measured memory_bytes: 1192
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();

        while(true) {
            c-=b;
            if(c<=0) {
                System.out.println("Yes");
                break;
            }
            a-=d;
            if(a<=0) {
                System.out.println("No");
                break;
            }
        }
    }
}

Measured memory_bytes: 35744
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
const ld eps = 1e-10;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m; cin >> n >> m;
  vector<ll> A(n); rep(i, n) cin >> A[i];
  int cnt = 0;
  ll sum = accumulate(all(A), 0LL);
  int M = 4*m;
  rep(i, n) {
    if(A[i] >= (sum+M-1)/M) cnt++;
  }
  cout << (cnt >= m ? "Yes\n" : "No\n");
  return 0;
}


Measured memory_bytes: 3624
#include <algorithm>
#include <cfloat>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define int long long
#define ll long long
#define eps LDBL_EPSILON
#define mod 1000000007
#define int long long
#define double long double
#define INF LLONG_MAX/1000
#define P pair<int,int>
#define prique priority_queue
using namespace std;
vector<int> vec[110];
vector<P> ans;
set<P> st;
int m[110];
signed main() {
	int n, k;
	cin >> n >> k;
	REP(i, n) {
		REP(j, n) {
			if (i == j)continue;
			m[i]++;
			vec[i].push_back(j);
			vec[j].push_back(i);
			if(i<j)ans.push_back(make_pair(i, j));
		}
	}
	int a = 1, b = 2, cnt = 0;
	while (a != n && cnt < k) {
		bool flag = false;
		if (a == b || m[a] == 1 || m[b] == 1)goto kaage;
		REP(j, n) {
			if (j == a || j == b)continue;
			bool f = false, g = false;
			for (int l : vec[j]) {
				if (l == a)f = true;
				if (l == b)g = true;
			}
			if (f && g)flag = true;
		}
		if (flag) {
			st.insert(make_pair(a, b));
			cnt++;
			m[a]--; m[b]--;
		}
	kaage:;
		b++;
		if (b == n + 1) {
			a++;
			b = a + 1;
		}
	}
	if (k == cnt) {
		cout << ans.size() - cnt << endl;
		for (P p : ans) {
			if (st.find(p) == st.end())cout << p.first << " " << p.second << endl;
		}
	}
	else cout << -1 << endl;
	return 0;
}

Measured memory_bytes: 896
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 1000100
const int mod=1e9+7;
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int n,D,H,s[N],dp[N],sum,fac[N];
int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=1LL*ans*a%mod;
		a=1LL*a*a%mod;
		b>>=1;
	}
	return ans;
}
void init(int n){
	fac[0]=1;
	for(int i=1;i<=n;++i){
		fac[i]=1LL*fac[i-1]*i%mod;
		sum=(sum+fac[i])%mod;
	}
}
int main(){
	n=read(),H=read(),D=read();
	init(n);
	dp[0]=s[0]=fac[n];
	for(int i=1;i<=H;++i){
		dp[i]=1LL*(s[i-1]-(i<D?0:s[i-D-1])+mod)*sum%mod;
		s[i]=(s[i-1]+dp[i])%mod;
	}
	printf("%lld\n",1LL*dp[H]*qpow(sum,mod-2)%mod);
	return 0;
}



Measured memory_bytes: 15436
import Data.List

pair [] _ = []
pair (a:as) b =
    let x = map (\y -> (a, y) ) b
    in
        x ++ (pair as b)

cmp (a,b) (c,d) = compare (a+b) (c+d)

search _ [] = []
search dif ((a,b):r) = 
    if dif == (a - b) * 2
    then (a,b):(search dif r)
    else (search dif r)

ans' a b = 
    let ma = last a
        mb = last b
        df = (sum a) - (sum b)
        s0 = search df $ pair (nub a) (nub b)
        s1 = head $ sortBy cmp s0
    in
        if s0 == []
        then "-1"
        else unwords $ map show [ fst s1, snd s1 ]

ans ([0,0]:_) = []
ans ([n,m]:x) =
    let a = sort $ concat $ take n x
        b = sort $ concat $ take m $ drop n x
        r = drop (n+m) x
        s = ans' a b
    in
       s:(ans r)

main = do
    c <- getContents
    let i = map (map read) $ map words $ lines c :: [[Int]]
        o = ans i
    mapM_ putStrLn o



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

typedef long long ll;
typedef unsigned long long ull;

int main(){
    int N, W;
    cin >> N >> W;
    int w[101], v[101];
    for(int i=1;i<=N;i++){
        cin >> w[i];
        cin >> v[i];
    }
    static ll dp[101][100001];
    for(int i=0;i<=N;i++) dp[i][0] = 0;
    for(int j=1;j<=N*1000;j++) dp[0][j] = W+1;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N*1000;j++){
            if(j >= v[i]) dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);
            else dp[i][j] = dp[i-1][j];
        }
    }
    
    for(int j=N*1000;j>=0;j--){
        if(dp[N][j] <= W){
            cout << j << endl;
            return 0;
        }
    }
    return 0;
}

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



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

    int x,y;
    cin >> x >> y;
    int extra = y - (2*x);

    cout << ((((y-2*x) % 2 == 0) && (y >= 2*x) && (extra <= (2*x))) ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
typedef long long ll;
#define INF 1000000000
using namespace std;
int euclidean_gcd(unsigned a, unsigned b) {
  if(a < b) euclidean_gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
int main(void){
   ll n,X;
   cin>>n>>X;
   ll ans=INF;
   vector<ll>y(n);
   vector<ll>diff(n);
   for(int i=0;i<n;i++){
       cin>>y[i];
       diff[i]=abs(y[i]-X);
   }
   sort(diff.begin(),diff.end());
   if(n==1){
       ans=abs(y[0]-X);
   }else{
   for(int i=0;i<n-1;i++){
       ll tmp;
       tmp=euclidean_gcd(diff[i],diff[i+1]);
       if(tmp<ans){
           ans=tmp;
       }
       if(ans==1){
           break;
       }
   }
   }
   cout<<ans<<endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <queue>
using namespace std;
string s[50];
int arrived[50][50];
int dist[50][50];
int main( void )
{
  ios::sync_with_stdio(false);
  int H, W;
  cin >> H >> W;
  int N = 0;
  for( int i=0; i<H; i++ ){
    cin >> s[i];
    for( int j=0; j<W; j++ ){
      if( s[i][j] == '#' ) N++;
    }
  }
  queue<int> q;
  q.push( 0 );
  arrived[0][0] = 1;
  while( !q.empty() ) {
    int x = q.front() % 100;
    int y = q.front() / 100;
    q.pop();
    if( x > 0   && !arrived[x-1][y] && s[y][x-1] != '#' ){ arrived[x-1][y] = 1; dist[x-1][y]=dist[x][y]+1; q.push( y*100+x-1 ); }
    if( x < W-1 && !arrived[x+1][y] && s[y][x+1] != '#' ){ arrived[x+1][y] = 1; dist[x+1][y]=dist[x][y]+1; q.push( y*100+x+1 ); }
    if( y > 0   && !arrived[x][y-1] && s[y-1][x] != '#' ){ arrived[x][y-1] = 1; dist[x][y-1]=dist[x][y]+1; q.push( (y-1)*100+x ); }
    if( y < H-1 && !arrived[x][y+1] && s[y+1][x] != '#' ){ arrived[x][y+1] = 1; dist[x][y+1]=dist[x][y]+1; q.push( (y+1)*100+x ); }
  }
  if( dist[W-1][H-1] == 0 ){
    cout << -1 << endl;
  } else {
    cout << H*W - N - dist[W-1][H-1] - 1 << endl;
  }
}

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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  deque<int> d;
  rep(i,n) {
    int p = lower_bound(d.begin(), d.end(), a[i]) - d.begin();
    if (p == 0) {
      d.push_front(a[i]);
    } else d[p-1] = a[i];
  }
  int ans = d.size();
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
from itertools import (
    accumulate,  # 累積和のイテレータ
    groupby,  # 値をkey,同じ値の集まりをgroup
    permutations,  # 順列
    combinations,  # 組み合わせ
    product,  # 重複あり順列（直積, 深いネストにも使える）
)

while True:
    n, x = map(int, input().split())
    if n==0 and x==0:
        break
    ans = 0
    for a, b, c in combinations(list(range(1, n+1)), 3):
        if a+b+c==x:
            ans += 1
    print(ans)


Measured memory_bytes: 5632
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
const double EPS = 1e-9;
typedef pair<int, int> P;
typedef unsigned int ui;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
int par[100000];
int rank1[100000];
void init(int n) {
	for (int i = 0; i < n; i++) {
		par[i] = i;
		rank1[i] = 0;
	}
}
int find1(int x) {
	if (par[x] == x) {
		return x;
	}
	else {
		return par[x] = find1(par[x]);
	}
}
void unite1(int x, int y) {
	x = find1(x);
	y = find1(y);
	if (x == y)return;
	if (rank1[x] < rank1[y]) {
		par[x] = y;
	}
	else {
		par[y] = x;
		if (rank1[x] == rank1[y])rank1[x]++;
	}
}
bool same(int x, int y) {
	return find1(x) == find1(y);
}
struct edge { int u, v, cost; };
bool comp(const edge&e1, const edge&e2) {
	return e1.cost < e2.cost;
}
edge es[100000];
int V, E;
P kruskal(int ign) {
	init(V);
	P res = { 0,0 };
	for (int i = ign; i < E; i++) {
		edge e = es[i];
		if (!same(e.u, e.v)) {
			unite1(e.u, e.v);
			res.first=max(res.first, e.cost);
			res.second++;
		}
	}
	return res;
}
int main() {
	while (cin >> V >> E, V) {
		rep(i, E) {
			int x, y, z; cin >> x >> y >> z; x--; y--;
			es[i] = { x,y,z };
		}
		sort(es, es + E, comp);
		int mi = (int)MOD;
		rep(i, E) {
			P now = kruskal(i);
			if (now.second != V - 1)continue;
			mi = min(mi, now.first - es[i].cost);
		}
		if (mi == (int)MOD)mi = -1;
		cout << mi << endl;
	}
	return 0;
}


Measured memory_bytes: 3124
#include<iostream>
#include<algorithm>
#include<string>
#include<functional>
#include<utility>
#include<stack>
#include<queue>
#include<cmath>
#include<list>
#include<cstdint>
#include<vector>
#include<map>
#include<deque>
#define rep(i,rept)	for(ll i = 0; i<rept;i++)
typedef long long ll;
const ll MOD = 1e9 + 7;
using namespace std;

int main() {
	//七日目

	cin.tie(0); ios::sync_with_stdio(false);


	ll n = 0, T = 0, some = 0;
	ll x = 0;
	std::vector<ll> t;
	cin >> n >> T;
	rep(i, n) {
		cin >> some;
		if (n == 1) {
			cout << T << endl;
			return 0;
		}
		t.push_back(some);
		if (i >= 1) {
			x += std::min(T, t[i] - t[i - 1]);
		}

	}
	cout << x  + T << endl;
	
	return 0;
}

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

using namespace std;
int main(int argc, char const* argv[]) {
  int n, l;
  int out_num;

  cin >> n >> l;

  if (l > 0) {
    out_num = l;
  } else if (l + n > 0) {
    out_num = 0;
  } else {
    out_num = l + n - 1;
  }

  int sum = n * (2 * l + n - 1) / 2;
  int res = sum - out_num;

  cout << res << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split(" ");
        long small = Integer.parseInt(input[0]);
        long large = Integer.parseInt(input[1]);
        long range = Integer.parseInt(input[2]);
        if(large - small + 1 <= range * 2){
            for(long i = small ; i <= large ; i++){
                System.out.println(i);
            }
        }
        else{
            for(long i = small ; i <= small + range -1 ; i++){
                System.out.println(i);
            }
            for(long i = large - range + 1 ; i <= large ; i++){
                System.out.println(i);
            }
        }
    }
}


Measured memory_bytes: 22996
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
  long long n;
  cin>>n;
  long long ans=0;
  int*arr=new int[n];
  map<int,int>m;
  for(int i=0;i<n;i++)
  {
  	cin>>arr[i];
  	ans+=arr[i];
  	m[arr[i]]++;
  }
  int q;
  cin>>q;
  ll si;
  ll ei;
  for(int i=0;i<q;i++)
  {
  	cin>>si;
  	cin>>ei;
  	ll temp=m[si];
  	ans-=si*temp;
  	m[si]=0;
     m[ei]+=temp;
     
  	ans+=temp*ei;
  	cout<<ans<<endl;
  }
  
  
 
}


Measured memory_bytes: 8432
#include "bits/stdc++.h"
using namespace std;


long long a;
long long b;
long long c;
int suc = 0;
int A = 0;


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

	size_t N = s.length();

	for (int i = 0; i < N / 2; i++) {
		if (s[i] == s[N - 1 - i]) {
			suc++;
		}
	}
	if (suc == N / 2)A++;
	suc = 0;

	for (int i = 0; i < N / 4; i++) {
		if (s[i] == s[N/2 - 1 - i]) {
			suc++;
		}
	}
	if (suc == N / 4)A++;
	suc = 0;


	for (int i = 0; i < N / 4; i++) {
		if (s[N-1-i] == s[N / 2 + 1 + i]) {
			suc++;
		}
	}
	if (suc == N / 4)A++;
	suc = 0;
	if (A == 3) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}

}


Measured memory_bytes: 256
n, m = map(int, input().split())
a, b = list(range(m)), list(range(m))
for i in range(m):
    a[i], b[i] = map(int, input().split())
a.extend(b)
a = sorted(a)
for i in range(1, n+1):
    print(a.count(i))

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

#define mp make_pair
#define pb push_back

#define int int64_t

const int MOD = 1e9+7;
 
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int H,W,h,w;
    cin>>H>>W>>h>>w;
    if(H%h==0&&W%w==0) {
        cout<<"No";
        return 0;
    }
    cout<<"Yes\n";
    int sum=0;
    if(H%h) {
        int lol = H*W+1;
        int anss[h];
        for(int i=0;i<h;i++) {
            anss[i]=lol;
            if(i==h-1)
                anss[i]=-(h*lol)+lol-1;
        }
        for(int i=0;i<H;i++) {
            for(int j=0;j<W;j++) {
                cout<<anss[i%h]<<" ";
                sum+=anss[i%h];
            }
            
            cout<<"\n";
        }
    }

    else {
        int lol = H*W;
        int anss[w];
        for(int i=0;i<w;i++) {
            anss[i]=lol;
            if(i==w-1)
                anss[i]=-(w*lol)+lol-1;
        }
        for(int i=0;i<H;i++) {
            for(int j=0;j<W;j++) {
                cout<<anss[j%w]<<" ";
                sum+=anss[j%w];
            }
            cout<<"\n";
        }
    }

    //cout<<sum;

    return 0;
}

Measured memory_bytes: 2048
#include "bits/stdc++.h"
using namespace std;

// GNU C Compiler
//template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

// type
using ll = int_fast64_t;
using ull = uint_fast64_t;
using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
//using pair<T1, T2> = p12;

//container
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
#define ALL(v) v.begin(),v.end()

//repetition
#define REP(n) for(ll i=0; i<(n); i++)
#define REPj(n) for(ll j=0; j<(n); j++)
#define REPinit(i,a,n) for(ll i=(a); i<(n); i++)
#define REPinitj(j,a,n) for(ll j=(a); j<(n); j++)

//algorithm
#define SORT(c) sort((c).begin(),(c).end())
#define CONTAINER_ALL(a) a.begin(),a.end()

//constant

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//Optimizer
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")


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

    int X;
    cin >> X;

    switch (X)
    {
    case 3:
    case 5:
    case 7:
        cout << "YES" << endl;
        break;
    default:
        cout << "NO" << endl;
        break;
    }

    
    return 0;
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
#define int long
signed main(){
  string n;
  int p,a;
  cin>>n>>p;
  a=n.size();
  int dp[103][10][2][4]={0};
  const int low=0,eq=1;
  dp[0][0][low][0]=1;
  for(int i=1;i<n[0]-'0';++i)dp[0][i][low][1]=1;
  dp[0][n[0]-'0'][eq][1]=1;
  for(int i=1;i<a;++i){
    int digit=n[i]-'0',prev=n[i-1]-'0';
    for(int j=0;j+(digit!=0)<=p;++j){
      dp[i][digit][eq][j+(digit!=0)]=dp[i-1][prev][eq][j];
    }
    for(int x=0;x<10;++x)for(int y=0;y+(x!=0)<=p;++y)for(int z=0;z<10;++z)
      dp[i][x][low][y+(x!=0)]+=dp[i-1][z][low][y]+(x<digit?dp[i-1][z][eq][y]:0);
  }
  int res=0;
  for(int i=0;i<10;++i)for(int j=0;j<=1;++j)res+=dp[a-1][i][j][p];
  cout<<res;
}

Measured memory_bytes: 256