akhauriyash/Code-Regression huggingface dataset:
def countDuplicate(S, s):
	# S:文字列、s:検索対象文字列
	cnt = 0
	for i in range(0, len(S) - 2):
		if S.startswith(s, i):
			cnt = cnt + 1

	return cnt


while True:
	try:
		S = str(input().strip())
	except:
		break
	print(countDuplicate(S, 'JOI'))
	print(countDuplicate(S, 'IOI'))



Measured memory_bytes: 5568
#include <bits/stdc++.h>
#ifdef DEBUG
  #include "debug.hpp"
#else
  #define DUMP(var)
#endif

using namespace std;
template< class T1, class T2 > inline istream &
operator>>( istream & fin, pair< T1, T2 > & pr )
{ fin >> pr.first >> pr.second; return fin; }
template< class T0, class T1, class T2 > inline istream &
operator>>( istream & fin, tuple< T0, T1, T2 > & t )
{ fin >> get<0>(t) >> get<1>(t) >> get<2>(t); return fin; }
template< class T > inline istream &
operator>>( istream & fin, vector< T > & a ) {
for(auto & u: a) fin >> u; return fin; }
template<class T, size_t n> inline istream &
operator>>( istream & fin, array<T, n> & a ) {
for(auto & u: a) fin >> u; return fin; }
template<class FwdIter> inline auto
dump(FwdIter first, FwdIter last, const char * dlm = " ") -> void {
using value_type = typename iterator_traits<FwdIter>::value_type;
copy(first, last, ostream_iterator<value_type>(cout, dlm)); }
template<typename T> vector<T> & operator--(vector<T> & a)
{ for(auto & i: a) --i; return a; }
/* @@@ ----------------------------------- */


int main(const int /*argc*/, char ** /*argv*/) {
  ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

  size_t n;
  cin >> n;
  vector<size_t> a(n);
  cin >> a;
  size_t out = 0, run = 0;
  for (size_t i = 1; i < a.size(); ++i) {
    if (a[i] <= a[i - 1]) {
      ++run;
    } else {
      run = 0;
    }
    out = max(out, run);
  }

  cout << out;

  return EXIT_SUCCESS;
}


Measured memory_bytes: 1024
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskA solver = new TaskA();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskA {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            String s = in.nextLine();
            out.println(s.compareTo(new StringBuilder(s).reverse().toString()) == 0 ? "Yes" : "No");
        }

    }

    static class InputReader {
        BufferedReader br;

        public InputReader(InputStream is) {
            BufferedReader br = new BufferedReader(new InputStreamReader(is));
            this.br = br;
        }

        public String nextLine() {
            String str = null;
            try {
                str = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return str;
        }

    }
}
 

Measured memory_bytes: 22996
#include<stdio.h>
int main(void)
{
	int n,r[4],l,s,x,y,z,a,i,j,flg;
	while(1){
		scanf("%d",&n);
		if(n==0000){
			break;
		}
		flg=1;
		a=0;
		while(n!=6174){
			y=0;
			x=1000;
			for(i=0;i<4;i++){
				r[i]=n/x;
				n=n%x;
				x=x/10;
				if(r[0]==r[i]) y++;
			}
			if(y==4) {
				flg=0;
				break;
			}
			l=0; s=0;
			for(i=0;i<3;i++){
				for(j=i+1;j<4;j++){
					if(r[i]>r[j]){
						z=r[i];
						r[i]=r[j];
						r[j]=z;
					}
				}
			}
			x=1000;
			for(i=0;i<4;i++){
				s=r[i]*x+s;
				x=x/10;
			}
			x=1;
			for(i=0;i<4;i++){
				l=r[i]*x+l;
				x=x*10;
			}
			n=l-s;
			a++;
		}
		if(flg==1) printf("%d\n",a);
		if(flg==0) printf("NA\n");
	}
	return 0;
}

Measured memory_bytes: 2704
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
cnt = 0
for i in range(0,len(A),2):
    if A[i]%2:
        cnt += 1
print(cnt)


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

using namespace std;

typedef long long LL;

const int N = 1000010;

int n;
double res;

int main()
{
    scanf("%d", &n);
    while(n--)
    {
        double x;
        char u[10];
        scanf("%lf%s", &x, u);

        if(!strcmp(u, "JPY")) res += x;
        else res += x * 380000.0;
    }

    printf("%.5f\n", res);

    return 0;
}


Measured memory_bytes: 256
n,m=map(int,input().split())
a = [int(input()) for i in range(m)]
dp=[0]*(n+1)
if m==0:
  for i in range(n,-1,-1):
    if i==n or i==n-1:
      dp[i]=1
    else:
      dp[i]=dp[i+1]+dp[i+2]
  print(dp[0]%1000000007)
else:
  j=-1
  for i in range(n,-1,-1):
    if i==a[j]:
      if m>j*(-1):
        j-=1
    else:
      if i==n or i==n-1:
        dp[i]=1
      else:
        dp[i]=dp[i+1]+dp[i+2]
  print(dp[0]%1000000007)

Measured memory_bytes: 460020
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int getnorm(int i, int j) {
  return (i - j) * (i - j);
}

int main() {
  int n;
  cin >> n;
  vector<int> x(n);
  rep(i, n) cin >> x[i];

  sort(x.begin(), x.end());
  int ans = inf;
  FOR(i, x[0], x[n - 1] + 1) {
    int res = 0;
    rep(j, n) res += getnorm(i, x[j]);
    ans = min(ans, res);
  }
  cout << ans << endl;




  
  return 0;
}

Measured memory_bytes: 256
n=int(input())
a=[int(x) for x in input().split()]
a.insert(0,0)
a.append(0)
b=[]
en=0
for i in range(n+1):
  b.append(a[i+1]-a[i])
  en+=abs(b[i])

for i in range(1,n+1):
  if b[i]*b[i-1]<=0:
    print(en+abs(a[i+1]-a[i-1])-abs(b[i])-abs(b[i-1]))
  else:
    print(en)

Measured memory_bytes: 14048
#include <iostream>
#include <cmath>
#include <algorithm>

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

using namespace std;

int main(){
	int D, E;
	while( cin >> D >> E, D|E ){
		double ans=1e10;
		rep(x,D+1) rep(y,D+1){
			if( x+y == D ){
				ans = min(ans, abs( (double)sqrt(x*x + y*y) - (double)E ) );
			}
		}
		printf("%.10f\n", ans);
	}
	return 0;
}

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

int main(){
  int n;
  ll k;
  cin >> n >> k;
  map<int,ll> mp;
  rep(i,n) {
    int a, b;
    cin >> a >> b;
    mp[a] += b;
  }
  
  ll cnt = 0;
  for (auto e : mp) {
    cnt += e.second;
    if (cnt >= k) {
      cout << e.first << endl;
      return 0;
    }
  } 
  return 0;
}

Measured memory_bytes: 4224
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(long long)(n);i++)
#define all(a) a.begin(), a.end()
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, ll> P;
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; }
 
const ll MOD=1e9+7;
const ll INF=1e18;
const int MAX=510000;
const double pi=acos(-1);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

ll modpow(ll a,ll n){
  if(n==0)return 1;
  if(n%2==0){
    ll t=modpow(a,n/2);
    return (t*t)%MOD;
  }
  return a*modpow(a,n-1)%MOD;
}
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false); 
  
  int n;
  cin >> n;
  ll zero=0;
  map<P,P>mp;
  rep(i,n){
    ll x,y;
    cin >> x >> y;
    if(x==0 && y==0){
      zero++;
      continue;
    }
    ll g=gcd(x,y);
    x/=g;
    y/=g;
    if(y<0){
      x=-x;
      y=-y;
    }
    if(y==0 && x<0){
      x=-x;
      y=-y;
    }
    if(x>0) mp[P(x,y)].first++;
    else mp[P(y,-x)].second++;
  }
  ll ans=1;
  for(auto p:mp){
    ll x=p.second.first,y=p.second.second;
    ans=(ans*(modpow(2,x)+modpow(2,y)-1))%MOD;
  }
  ans+=zero;
  cout << (ans+MOD-1)%MOD << endl;
  
  return 0;     
}


Measured memory_bytes: 19180
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define pb push_back
int dy[]={0, 0, 1, -1, 1, 1, -1, -1};
int dx[]={1, -1, 0, 0, 1, -1, -1, 1};

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define mp make_pair
#define fi first
#define sc second
int n,y;
int main(){
	cin >> n >> y;

	REP(i,n + 1) {
		FOR(j,i,n + 1) {
			int sum = 10000 * i + 5000 * (j - i) + 1000 * (n - j);
			if(sum == y) {
				cout << i << " " << (j - i) << " " << (n - j) << endl;
				return 0;
			}
		}
	}
	cout << -1 << " " << -1 << " " << -1 << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include "atcoder/all"
typedef long long int ll;
using namespace std;
// using namespace atcoder;
int main() {
    int n;
    cin >> n;
    int d[8] = {2, 3, 4, 6, 8, 9, 10, 12};
    int t = n / 8;
    if (n == 3) {
        cout << 2 << " " << 5 << " " << 63;
        return 0;
    }
    if (n % 8 == 1) {
        cout << 6 << " ";
    }
    else if (n % 8 == 2) {
        cout << 6 << " " << 12 << " ";
    }
    else if (n % 8 == 3) {
        cout << 2 << " " << 4 << " " << 6 << " ";
    }
    else if (n % 8 == 4) {
        cout << 2 << " " << 3 << " " << 9 << " " << 10 << " ";
    }
    else if (n % 8 == 5) {
        cout << 2 << " " << 3 << " " << 4 << " " << 6 << " " << 9 << " ";
    }
    else if (n % 8 == 6) {
        cout << 2 << " " << 3 << " " << 4 << " " << 6 << " " << 9 << " " << 12 << " ";
    }
    else if (n % 8 == 7) {
        cout << 2 << " " << 3 << " " << 4 << " " << 6 << " " << 8 << " " << 9 << " " << 10 << " ";
    }
    else {
        cout << 2 << " " << 3 << " " << 4 << " " << 6 << " " << 8 << " " << 9 << " " << 10 << " " << 12 << " ";
        t--;
    }
    for (int i = 1; i <= t; i++) {
        for (int j = 0; j < 8; j++) {
            cout << i * 12 + d[j] << " ";
        }
    }
    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <functional>
#include <numeric>
#include <limits>
#include <iomanip>
#include <queue>
#include <cmath>
#include <math.h>
#include <string>
#include <math.h>
#define PI 3.14159265359
using namespace std;
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; }
const long long INF = 1LL << 60;
using pll = pair<long long, long long>;

int main() {

	// 標準入力が早くなる。Cスタイルの入出力とC++スタイルの入出力を混合させてはならない。
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	int N;
	cin >> N;
	vector<int> A(N - 1);
	vector<int> res(N, 0);

	for (int i = 0; i < N - 1; i++)
	{
		cin >> A.at(i);
	}

	//sort(A.begin(), A.end());

	for (int i = 0; i < N -1; i++)
	{
		++res.at(A.at(i) - 1);
	}
	for (int i = 0; i < N; i++)
	{
		cout << res.at(i) << endl;;
	}

	return 0;
}


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

int main()
{
 
    // input data
    long n;
    cin>>n;

    vector<long> A(n+1);
    vector<long> B(n);

    long monster=0;
    for(int i=0;i<n+1;i++){
        cin>>A.at(i);
        monster+=A.at(i);
    }

    for(int i=0;i<n;i++){
        cin>>B.at(i);
    }

    // battle
    for(int i=n-1;i>=0;i--){
        long wk;
         wk = A.at(i+1)-B.at(i);
       if(wk>=0){
            A.at(i+1)-=B.at(i);
            B.at(i)=0;
       }
        else{
           A.at(i+1)=0;
           B.at(i)=-wk;
        }
        long wk2;
        wk2=A.at(i)-B.at(i);
        if(wk2>=0){
          A.at(i)-=B.at(i);
           B.at(i)=0;
       }
       else{
            A.at(i)=0;
            B.at(i)=-wk2;
        }
    }
    // output data
    long monster_after_battle=0;
    for(int i=0;i<n+1;i++){
        monster_after_battle+=A.at(i);
    }

    cout<<monster - monster_after_battle<<endl;

    return 0;
}

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

using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
const ll mod = ll(1e9) + 7;
const int INF = int(1e9);

int main()
{
    int N;
    cin >> N;
    vector<vector<pair<int, ll>>> e(N);
    rep(i, N - 1)
    {
        int a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        e[b].push_back({a, c});
        e[a].push_back({b, c});
    }
    int Q, K;
    cin >> Q >> K;
    K--;
    vector<ll> cost(N);
    cost[K] = 0;
    queue<pair<int, ll>> que;
    rep(i, e[K].size())
        que.push(e[K][i]);
    while (!que.empty())
    {
        int node = que.front().first;
        ll cst = que.front().second;
        que.pop();
        cost[node] = cst;
        rep(i, e[node].size())
        {
            if (e[node][i].first != K && cost[e[node][i].first] == 0)
            {
                que.push({e[node][i].first, e[node][i].second + cst});
            }
        }
        //cout << node << endl;
    }
    vector<ll> ans;
    rep(i, Q)
    {
        int x, y;
        cin >> x >> y;
        ans.push_back(cost[x - 1] + cost[y - 1]);
    }
    rep(i, Q) cout << ans[i] << endl;
    return 0;
}


Measured memory_bytes: 11504
#include <iostream>
#include <vector>

using namespace std;
// template for creating 2d vector
template<typename T>
vector<vector<T>> make_2d_vector(size_t rows, size_t cols, T init)
{ return vector< vector<T> >(rows, vector<T>(cols, init)); }

#define debug(x) cout << #x << "==" << x << endl;

const int inf = 1e+8;

typedef long long ll;



int main() {
  ios::sync_with_stdio(false);

  int A, B;
  cin >> A >> B;

  cout << (A + B) % 24 << "\n";

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vs vector<string>
#define miv unordered_map<int, vi>

void show(auto a){
  int i = 0;
  while(i < a.size()){
    cout<<a[i]<<" ";
    i++;
  }
  cout<<endl;
}


void dfs(int a,  vector<int> table[], bool visited[], int dp[]){
	visited[a] = true;
	for(int i = 0; i<table[a].size(); i++){
		if(!visited[table[a][i]]) dfs(table[a][i], table, visited, dp);

		dp[a] = max(dp[table[a][i]] + 1, dp[a]);
	}

}

int main(){
  ios_base::sync_with_stdio(false);

  int n, m;
  cin>>n>>m;
  vector<int> table[n+1];

  while(m--){
  	int a, b;
  	cin>>a>>b;
  	table[a].push_back(b);
  }

  bool visited[n+1];
  int dp[n+1];

  for(int i = 0; i <= n; i++){
  	visited[i] = false;
  	dp[i] = 0;
  }


  for(int i = 1; i<=n; i++){
  	if(!visited[i])dfs(i, table, visited, dp);
  }
  int ans = 0;
  for(int i = 0; i < n+1; i++){
  	ans = max(dp[i], ans);
  }

  cout<<ans<<endl;

}

Measured memory_bytes: 9600
n,a,b=map(int,input().split())
s=input()

yosen_ok=0
kaigai=0
for i,ss in enumerate(s):
    if yosen_ok<a+b:
        if ss=='a':
            yosen_ok+=1
            print('Yes')
        elif ss=='b':
            kaigai+=1
            if kaigai<=b:
                yosen_ok+=1
                print('Yes')
            else:
                print('No')
        else:
            print('No')
        continue
    else:
        print('No')


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

int main() {
  string s; cin >> s;
  int answer = 0;
  
  for (int i = 0; i < 4; i++) {
    if (s.at(i) == '+') answer++;
    else answer--;
  }
  
  cout << answer << endl;
}

Measured memory_bytes: 256
n = int(input())
*h, = map(int,input().split())
dp = [0]*n
dp[1] = abs(h[1]-h[0])
for i in range(2,n):
  dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]))
print(dp[-1])

Measured memory_bytes: 13928
#include<bits/stdc++.h>
using namespace std ;
#define ll long long int 
#define pb push_back 
#define mp make_pair 
#define pii pair <int , int > 
#define pll pair < ll , ll >
int main(){
	ios_base::sync_with_stdio(false) ;
	cin.tie(NULL) ;
	int n ;
	cin >> n ;
	int arr[n], ans = 0 ;
	for(int i = 0 ; i < n ; i++) cin >> arr[i] ;
	sort(arr , arr +n ) ;
	for(int i = arr[n/2 - 1] + 1 ; i <= arr[n/2] ; i++){
		ans++ ;
	}
	cout << ans ;
}

Measured memory_bytes: 640
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


# 初項s, 交差dのn個の数列の和
def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


# aとbの最大公約数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


# aとbの最小公倍数
def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def main():
    N = int(input())
    H = list(map(int, input().split()))

    H[0] -= 1
    for i in range(1, N):
        if H[i - 1] > H[i]:
            print("No")
            return

        if H[i - 1] < H[i]:
            H[i] -= 1

    print("Yes")


if __name__ == '__main__':
    main()


Measured memory_bytes: 15012
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(c) c.begin(), c.end()
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define gadd(x,y) x=add(x,y)
#define gmul(x,y) x=mul(x,y)
using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;

const int N = 1e5 + 5;

ll cnt[N];

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	int n;
	ll k;
	cin >> n >> k;
	rep(i,0,n){
		int a,b;
		cin >> a >> b;
		cnt[a] += b;
	}
	rep(i,0,N){
		k-=cnt[i];
		if(k <= 0){
			cout << i << '\n';
			return 0;
		}
	}
}


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

int main() {
  int a, b, c, d;
  cin >> a >> b >> c;
  if(a >= (b + c)){
  	cout << 0 << endl;
  }
  else{
    d = (b + c) - a;
  	cout << d << endl;
  }
}


Measured memory_bytes: 256
#19
r,g,b,n = map(int,input().split())
cnt = 0

for i in range(n//r+1):
    for j in range(n//g+1):
        if r*i+g*j>n:
            break
        elif (n-(r*i+g*j))%b == 0:
            cnt += 1

print(cnt)

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

int main()
{
    int a,b;
    cin>>a>>b;
    if(a>b*2)
    {
        cout<<a-(b*2)<<endl;
    }
    else
    {
        cout<<0<<endl;
    }
    return 0;
    
}

Measured memory_bytes: 256
def bis(h, a):
  l, r = 0, len(h)-1
  while l<r:
    mid = (l+r) // 2
    if h[mid] >= a:
      l = mid + 1
    else:
      r = mid
  return l

def main():
  n = int(input())
  alist = [int(input()) for _ in range(n)]
  ans = 1
  h = [alist[0]]
  for a in alist[1:]:
    if a <= h[-1]:
      h.append(a)
      ans += 1
    else:
      i = bis(h, a)
      h[i] = a
  print(ans)


if __name__ == '__main__':
  main()


Measured memory_bytes: 8604
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

ll dp[20000][2][100];
int main(){
	string s;int d;cin>>s>>d;
	dp[0][0][0]=1;
	rep(i,s.size())rep(j,2)rep(k,d){
		int lim=(j==0?s[i]-'0':9);
		for(int t=0;t<=lim;t++){
			(dp[i+1][j||t<lim][(k+t)%d]+=dp[i][j][k])%=MOD;
		}
	}
	cout<<(dp[s.size()][0][0]+dp[s.size()][1][0]+MOD-1)%MOD<<endl;
}

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

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
typedef pair<int, int> P;
typedef long long ll;
typedef unsigned long long ull;

int M = 100005;

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

  ll sum = 0;
  vector<int> backet(M);

  ll tmp;

  rep(i, N){
    cin >> tmp;
    sum += tmp;
    backet.at(tmp)++;
  }

  int bef, aft, diff;
  cin >> N;
  rep(i, N){
    cin >> bef >> aft;
    diff = aft - bef;

    sum += diff * backet.at(bef);
    cout << sum << endl;

    backet.at(aft) += backet.at(bef);
    backet.at(bef) = 0;
  }
}


Measured memory_bytes: 3788
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int MOD = 1000000007;
const ll INF = 1LL << 60;
int main() {
   cin.tie(0);
   ios::sync_with_stdio(false);
   string t;
   cin >> t;
   for(int i = 0;i < t.length();i++) {
       if(t[i]=='?') {
           cout << 'D';
       } else {
           cout << t[i];
       }
   }
   cout << endl;
}

Measured memory_bytes: 3788
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	int n, c;
	while(cin >> n >> c, n){
		vi u, v;
		rep(i, n){
			int a = 0, b;
			rep(j, 16) cin >> b, a |= b << j;
			v.pb(a);
		}
		rep(i, c){
			int a = 0, b;
			rep(j, 16) cin >> b, a |= b << j;
			u.pb(a);
		}
		vector<vi> dp(n + 1, vi(1 << 16, -1));
		dp[0][0] = 0;
		rep(i, n) rep(j, 1 << 16) if(dp[i][j] >= 0) for(int k : u){
			int nj = (j | v[i]) & ~k;
			int nxt = __builtin_popcount((j | v[i]) & k);
			dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j] + nxt);
		}
		cout << *max_element(all(dp[n])) << endl;
	}
	return 0;
}


Measured memory_bytes: 11332
use proconio::input;

fn main() {
    input! {
        n: usize,
        x: usize,
        m: usize
    }
    let mut seq = vec![0; m + 10];
    let mut flg = vec![0; m + 10];
    let (mut ls, mut le) = (1, 1);

    seq[1] = x;
    flg[x] = 1;
    for i in 2..=m+1 {
        seq[i] = (seq[i - 1] * seq[i - 1]) % m;
        if flg[seq[i]] > 0 {
            ls = flg[seq[i]];
            le = i;
            break;
        }
        flg[seq[i]] = i;
    }

    {
        // ~ ls
        let mut sum_uls = 0;
        let sum_ulsnum = ls - 1;
        for i in 1..ls {
            sum_uls += seq[i];
            if i == n {
                println!("{}", sum_uls);
                return;
            }
        }

        let mut sum_lse = 0;
        let sum_lsenum = le - ls;
        let mul_lse = (n - sum_ulsnum) / sum_lsenum;
        for i in ls..le {
            sum_lse += seq[i];
        }

        let remain = (n - sum_ulsnum) % sum_lsenum;
        let mut sum_remain = 0;
        for i in ls..ls + remain {
            sum_remain += seq[i];
        }

        println!("{}", sum_uls + sum_lse * mul_lse + sum_remain);
    }
}


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

using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{
	if(b == 0) return a;
	return gcd(b,a%b);
}
ll lcm(ll a,ll b)
{
	return a*b/gcd(a,b);
}

int main()
{
	ll a,b;
	while(cin >> a >> b)
	{
		cout << gcd(a,b) << " " << lcm(a,b) << endl;
	}
	
	return 0;
}


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

int main(){
  int T500, T100, T50, V;
  cin >> T500 >> T100 >> T50 >> V;
  int ptn = 0;
  for(int c500 = 0; c500 <= T500; c500++){
    int s500 = c500*500;
    for(int c100 = 0; c100 <= T100; c100++){
      int s100 = c100*100;
      for(int c50 = 0; c50 <= T50; c50++){
        if (s500+s100+c50*50 == V) ptn++;
      }
    }
  }
  cout << ptn << endl;
  return 0;
}


Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    A, B, C, D = map(int, input().split())
    while A > 0 or C > 0:
        C -= B
        if C <= 0:
            print("Yes")
            break

        A -= D
        if A <= 0:
            print("No")
            break


if __name__ == "__main__":
    main()


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

int main()
{
  int a,b,c;

  scanf("%d %d %d",&a,&b,&c);

  if (b-a==c-b) {
    printf("YES\n");
  } else {
    printf("NO\n");
  }
  
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#include<assert.h>
#include<chrono>
#include<random>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define SZ(x) ((int)x.size())
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
template<typename T>inline void chkmin(T &x,T y){x=x<y?x:y;}
template<typename T>inline void chkmax(T &x,T y){x=x>y?x:y;}
const int MAXMASK=(1<<19);
const int mod=1e9+7;
const int MAXN=25;
int pow_mod(int a,int b)
{
	int ret=1;
	for(;b;b>>=1,a=1LL*a*a%mod)if(b&1)ret=1LL*ret*a%mod;
	return ret;
}
void ad(int &x,int y){x+=y;if(x>=mod)x-=mod;}
vector<int> nxt[MAXN];
void ins(int x,int y){nxt[x].emplace_back(y);}
int f[MAXMASK],g[MAXMASK],E[MAXMASK];
int n,m,bin[25],ex[MAXN*MAXN],ey[MAXN*MAXN],mask[MAXN*MAXN],Log[MAXMASK];
int rt[MAXN];
int findrt(int x){return rt[x]==x?rt[x]:rt[x]=findrt(rt[x]);}
int lowbit(int x){return x&-x;}
int pre[MAXN*MAXN],inv[MAXN*MAXN];

map<int,int> mp[MAXN];
int get_edge(int x,int fa,int ed)
{
	if(x==ed)return 0;
	for(auto y:nxt[x])if(y^fa)
	{
		int t=get_edge(y,x,ed);
		if(t!=-1)return t|bin[mp[x][y]-1];
	}return -1;
}

int main()
{
	pre[0]=1;for(int i=1;i<MAXN*MAXN;i++)pre[i]=1LL*pre[i-1]*i%mod;
	inv[MAXN*MAXN-1]=pow_mod(pre[MAXN*MAXN-1],mod-2);
	for(int i=MAXN*MAXN-2;i>=0;i--)inv[i]=1LL*inv[i+1]*(i+1)%mod;
	bin[0]=1;for(int i=1;i<=20;i++)bin[i]=bin[i-1]<<1;
	for(int i=0;(1<<i)<MAXMASK;i++)Log[1<<i]=i;
	n=read();m=read();
	for(int i=1;i<=m;i++)
	{
		ex[i]=read(),ey[i]=read();
		if(i<n)ins(ex[i],ey[i]),ins(ey[i],ex[i]),mp[ex[i]][ey[i]]=mp[ey[i]][ex[i]]=i;
	}
	for(int i=n;i<=m;i++)mask[i]=get_edge(ex[i],0,ey[i]);
	for(int i=0;i<bin[n-1];i++)
		for(int j=n;j<=m;j++)E[i]+=(mask[j]&i)>0;
	g[0]=1;
	for(int i=0;i<bin[n-1];i++)if(g[i])
	{
		int t=__builtin_popcount(i);
		for(int S=(bin[n-1]-1)^i;S;S^=lowbit(S))
		{
			int u=lowbit(S),newe=E[i|u]-E[i],pree=E[i]+t;
			
			int newg=1LL*g[i]*pre[pree+newe]%mod*inv[pree]%mod;
			int newf=1LL*f[i]*pre[pree+newe+1]%mod*inv[pree+1]%mod;
			ad(newf,1LL*(t+1)*newg%mod);
			
			ad(g[i|u],newg);ad(f[i|u],newf);
		}
	}
	pr2(f[bin[n-1]-1]);
	return 0;
}



Measured memory_bytes: 6400
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>
#include <tuple>
#include <array>
#include <climits>
#include <bitset>

// BEGIN CUT HERE
#ifdef _MSC_VER
#include <agents.h>
#endif
// END CUT HERE 

#define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define REV(v) v.rbegin(), v.rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define MP make_pair
#define MT make_tuple

using namespace std;

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

const int N = 1010;
int dp[N];
vector<int> G[N];

int calc_grundy(int v);

void dfs(int v, int x, set<int> &st){
	for (auto nxt : G[v]){
		x ^= calc_grundy(nxt);
	}
	st.insert(x);
	for (auto nxt : G[v]){
		dfs(nxt, x^calc_grundy(nxt), st);
	}
}

int calc_grundy(int v){
	int &res = dp[v];
	if (res >= 0) return res;

	set<int> st;
	dfs(v, 0, st);
	for (int i = 0; i <= 1000; ++i){
		if (st.count(i) == 0) return res = i;
	}
	return -1;
}

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

	MEMSET(dp, -1);

	int n, m;
	cin >> n >> m;

	vector<int> p(n, -1);
	rep(i, m){
		cin >> p[i];
		--p[i];
		G[p[i]].push_back(i);
	}

	int g = 0;
	rep(i, n) if (p[i] < 0) g ^= calc_grundy(i);

	cout << (g ? "Alice" : "Bob") << endl;

	return 0;
}


Measured memory_bytes: 1468
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <string>
#include <bitset>
#include <deque>
#include <queue>
#define SIZE 100
using namespace std;
using ll = long long int;

ll bfs(deque<ll> dq, priority_queue<ll, vector<ll>, greater<ll>> q, ll k)
{
    if (k == 0)
    {
        ll ans = 0;
        ll v = q.top();
        q.pop();
        ans += v;
        return ans;
    }
    ll ans = 0;
    // D の左端
    if (!dq.empty())
    {
        deque<ll> n_d = dq;
        priority_queue<ll, vector<ll>, greater<ll>> n_q = q;
        ll v = n_d.front();
        n_d.pop_front();
        n_q.push(v);
        ans = max(ans, bfs(n_d, n_q, k - 1));
    }
    // D の右端
    if (!dq.empty())
    {
        deque<ll> n_d = dq;
        priority_queue<ll, vector<ll>, greater<ll>> n_q = q;
        ll v = n_d.back();
        n_d.pop_back();
        n_q.push(v);
        ans = max(ans, bfs(n_d, n_q, k - 1));
    }
    // 宝石を左端
    if (!q.empty())
    {
        deque<ll> n_d = dq;
        priority_queue<ll, vector<ll>, greater<ll>> n_q = q;
        ll v = q.top();
        n_q.pop();
        n_d.push_front(v);
        ans = max(ans, bfs(n_d, n_q, k - 1));
    }
    // 宝石を右端
    if (!q.empty())
    {
        deque<ll> n_d = dq;
        priority_queue<ll, vector<ll>, greater<ll>> n_q = q;
        ll v = q.top();
        n_q.pop();
        n_d.push_back(v);
        ans = max(ans, bfs(n_d, n_q, k - 1));
    }
    return ans;
}

int main()
{
    ll n, k;
    cin >> n >> k;
    deque<ll> dq;
    for (size_t _ = 0; _ < n; _++)
    {
        ll vi;
        cin >> vi;
        dq.push_back(vi);
    }

    ll ans = 0;
    for (size_t i = 0; i <= k; i++)
    {
        for (size_t j = 0; j <= i; j++)
        {
            // 宝石を取る
            deque<ll> d = dq;
            priority_queue<ll, vector<ll>, greater<ll>> pq;
            int a = j;
            int b = i - j;
            int n_cnt = k - i;

            // 左から取る
            for (size_t _ = 0; _ < a; _++)
            {
                if (!d.empty())
                {
                    ll v = d.front();
                    d.pop_front();
                    pq.push(v);
                }
            }
            // 右から取る
            for (size_t _ = 0; _ < b; _++)
            {
                if (!d.empty())
                {
                    ll v = d.back();
                    d.pop_back();
                    pq.push(v);
                }
            }

            for (size_t _ = 0; _ <= n_cnt; _++)
            {
                // 捨てる
                auto p = pq;
                for (size_t i = 0; i < _; i++)
                {
                    if (!p.empty())
                    {
                        p.pop();
                    }
                }
                // 合計を計算する
                ll sum = 0;
                while (!p.empty())
                {
                    sum += p.top();
                    p.pop();
                }
                ans = max(ans, sum);
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <pair<int, int> > bridges;
int a, b, n, m;
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		bridges.push_back(make_pair(b, a));
	}
	sort(bridges.rbegin(), bridges.rend());
	int ans = 0;
	while (!bridges.empty()) {
		int cut = bridges[bridges.size() - 1].first - 1;
		ans++;
		while (bridges[bridges.size() - 1].second <= cut && cut <= bridges[bridges.size() - 1].first && !bridges.empty())
			bridges.pop_back();
	}
	cout << ans << endl;
}

Measured memory_bytes: 1528
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N,A=0,B=0;
    cin>>N;
    int a[N];
    for(int i=0;i<N;i++){
        cin>>a[i];
    }
    sort(a,a+N,greater<int>());
    if(N%2==1){
        for(int i=0;i<N/2+1;i++){
            A+=a[2*i];
        }
        for(int i=0;i<N/2;i++){
            B+=a[2*i+1];
        }
    }else{
        for(int i=0;i<N/2;i++){
            A+=a[2*i];
            B+=a[2*i+1];
        }
    }
    cout<<A-B<<endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
// #pragma GCC target("avx2") //Enable AVX

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e7+10;

int least[MAXN];
int cnt[MAXN];
int pw[MAXN];
int sigma[MAXN];

struct SIEVE_OF_ERATOSTHENES
{
    SIEVE_OF_ERATOSTHENES(int N)
    {
        if(N < 1)N = 1;
     
        pw[1] = 0;
        least[1] = cnt[1]= sigma[1]  = 1;
        for(int i = 4 ; i <= N ; i+=2)least[i] = 2;
        for(int i = 3 ; i*i <= N ; i+=2)
        {
            if(least[i] == 0)
            {
                for(int j = i*i ; j <= N ; j+=i*2)
                {
                    if(least[j] == 0)least[j] = i;
                }
            }
        }
        for(int i = 2 ; i <= N ; i++)
        {
            if(least[i] == 0)
            {
              
                least[i] = i;
                cnt[i] = i;
                pw[i] = 1;
             
                sigma[i] = 2;
            }
            else
            {
                int x = i/least[i];
                if(least[i] == least[x])cnt[i] = cnt[x]*least[i], pw[i] = pw[x]+1;
                else cnt[i] = least[i], pw[i] = 1;
                if(i == cnt[i])
                {
                    sigma[i] = pw[i]+1;
                    
                }
                else
                {
                    sigma[i] = sigma[i/cnt[i]]*sigma[cnt[i]];
                }
         
            }
        }
    }
};

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

    int N;
    cin >> N;

	SIEVE_OF_ERATOSTHENES criba(N);

	long long sum = 0;

	for(int i = 1 ; i <= N ; i++)
	{
		sum += (long long)i*(long long)sigma[i];
	}    

	cout << sum << '\n';

    return 0;
}

Measured memory_bytes: 159860
#![allow(unused_imports)]

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

use std::{i32, i64, u32, u64, f64};
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::io::{stdout, Write, BufWriter};
use std::mem::{swap};

fn main() {
    input! {
        s: String,
    }
    let n = s.len();
    let mut prevs = HashMap::new();
    let mut maxs = HashMap::new();
    for (i, c) in s.chars().enumerate() {
        if prevs.contains_key(&c) {
            let p = prevs.get_mut(&c).unwrap();
            let m = maxs.get_mut(&c).unwrap();
            *m = max(*m, i - *p - 1);
            *p = i;
        } else {
            prevs.insert(c, i);
            maxs.insert(c, i);
        }
    }
    for (c, p) in prevs {
        let m = maxs.get_mut(&c).unwrap();
        *m = max(*m, n - p - 1);
    }
    println!("{}", maxs.values().min().unwrap());
}



Measured memory_bytes: 4352
A,B,M = map(int,input().split())

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

ans = min(a) + min(b)

for i in range(M):

    x,y,c = map(int,input().split())

    x -= 1
    y -= 1

    ans = min(ans , a[x]+b[y]-c)

print (ans)


Measured memory_bytes: 70596
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		for(int i=0;i<n;i++){
			Point a=new Point(sc.nextDouble(),sc.nextDouble());
			Point b=new Point(sc.nextDouble(),sc.nextDouble());
			Point c=new Point(sc.nextDouble(),sc.nextDouble());
			double A=a.x-b.x;
			double B=a.y-b.y;
			double C=(a.distance2()-b.distance2())/2;
			double D=a.x-c.x;
			double E=a.y-c.y;
			double F=(a.distance2()-c.distance2())/2;
			double X=(C*E-B*F)/(A*E-B*D);
			double Y=-(C*D-A*F)/(A*E-B*D);
			Point p=new Point(X-a.x,Y-a.y);
			double r=Math.sqrt(p.distance2());
			System.out.printf("%.3f %.3f %.3f\n",X,Y,r);
		}
	}
}

class Point{
	double x,y;
	Point(double a,double b){
		x=a;
		y=b;
	}
	double distance2(){
		return x*x+y*y;
	}
}

Measured memory_bytes: 28736
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;const int N=2*1e5+10;
int w[N];int d[N];int cnt[20];int res;int n;int st;bool book[N];
struct data{int v;int cf;};int sxr[N]; 
int main()
{
    scanf("%d",&n);
    for(int i=1,u,v,va;i<n;i++){scanf("%d%d%d",&u,&v,&va);w[u]^=va;w[v]^=va;}
    for(int i=0;i<n;i++){cnt[w[i]]++;}
    for(int i=1;i<=15;i++)res+=cnt[i]/2,st|=(cnt[i]&1)<<(i-1);	
    for(int i=1;i<(1<<15);i++)d[i]=d[i>>1]+(i&1);
    for(int i=1;i<(1<<15);i++)d[i]-=1;
    for(int i=1;i<(1<<15);i++)
        for(int j=0;j<15;j++)if((i>>j)&1)sxr[i]^=(j+1);
    for(int i=1;i<(1<<15);i++)
    {
        if(sxr[i]!=0)continue;
        for(int k=(i-1)&i;k;k=(k-1)&i)
            if(sxr[k]==0)d[i]=min(d[i],d[k]+d[i^k]);
    }printf("%d",res+d[st]);return 0;
}

Measured memory_bytes: 768
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<map>
#include<set>
#include<queue>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repn(i, n) for(int i = 1; i <= n; i++)
#define repr(i, n) for(int i = (n-1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define lint long long

inline void logger(){ cout << endl; }
template<typename A, typename... B>
void logger(const A& a, const B&... b){
    cout << a << " , ";
    logger(b...);
}

int main(){
    long N, K; cin >> N >> K;
    vector<long> neg, pos;

    pos.push_back(0);
    rep(i, N){
        long x_; cin >> x_;
        if(x_ < 0) neg.push_back(-x_);
        else if(x_ == 0) K--;
        else pos.push_back(x_);
    }
    neg.push_back(0);

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

    long ns = neg.size() - 1;
    long ps = pos.size() - 1;
    long M = min(ns, K);
    long ans = 1e10;
    rep(m, M+1){
        if(m + ps < K) continue;
        long n = neg[ns - m];
        long p = pos[K - m];
        ans = min(ans, n+p*2);
        ans = min(ans, n*2+p);
    }
    cout << ans << endl;
}


Measured memory_bytes: 1656
use std::io::*;
use std::str::FromStr;
 
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}
 
fn main() {
    let n: usize = read();
    let h: Vec<u64> = (0..n).map(|_| read()).collect();
    let mut max: u64 = 0;
    let mut count: u64 = 0;
 
    for i in 0..n-1 {
        if h[i] >= h[i + 1] {
            count += 1;
        } else {
            if count > max {
                max = count;
            }
            count = 0;
        }
    }
 
    if count > max {
        max = count;
    }
    
    println!("{}", max);
}

Measured memory_bytes: 4352
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <iomanip>
#define ll long long int
#define mod 1000000007
#define pii pair<int, int>
#define fr(n) for (int i = 0; i < n; i++)
#define fr1(n) for (int i = 1; i <= n; i++)
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    if (s[0] == s.back()) cout << "Yes";
    else cout << "No";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,k;cin>>n>>k;
  vector<int >iis(k,0);
  for(int i=0;i<n;i++){
  	int l;cin>>l;
    for(int j=0,a;j<l;j++){
    	cin>>a;iis[a-1]++;
    }
  }
  int tot=0;
  for(int i=0;i<k;i++)if(iis[i]==n)tot++;
  cout<<tot;
}

Measured memory_bytes: 256
import java.util.*;
import java.lang.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		int sx = sc.nextInt();
		int sy = sc.nextInt();
		int tx = sc.nextInt();
		int ty = sc.nextInt();
		String u = "U",r = "R",d = "D",l = "L";
		for( int i=0; i<ty-sy-1; i++ ){
			u += "U";
		}
		for( int i=0; i<tx-sx-1; i++ ){
			r += "R";
		}
		for( int i=0; i<ty-sy-1; i++ ){
			d += "D";
		}
		for( int i=0; i<tx-sx-1; i++ ){
			l += "L";
		}
		System.out.println(u+r+d+l+"L"+u+"U"+"R"+r+"D"+"R"+d+"D"+"L"+l+"U");
	}
}


Measured memory_bytes: 54356
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#define ull unsigned long long
#define MOD 1000000007

int main(){
    ull ans=0;
    int i,j,n,s[30002]={},check[4]={},cur=0;
    char str[30002]={},tmp;
    scanf("%d",&n);
    scanf("%s",str);
    /*for (i=0; i<n; i++){
        tmp=str[i];
        s[i]=atoi(&tmp);
    }*/
    for (i=0; i<1000; i++) {
        cur=0;
        check[0]=i/100;
        check[1]=(i/10)%10;
        check[2]=i%10;
        for (j=0; j<n; j++) {
            if(str[j]==(check[cur]+'0')) cur++;
            if (cur==3) break;
        }
        if (cur==3) ans++;
    }
    printf("%lld",ans);
    return 0;
}


Measured memory_bytes: 1760
fn main() {
    use std::io::Read;
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    
    let n: usize = iter.next().unwrap().parse::<usize>().unwrap();
    let k: usize = iter.next().unwrap().parse::<usize>().unwrap();
    let l: usize = iter.next().unwrap().parse::<usize>().unwrap();
    
    let mut road = Utree::new(n);
    let mut rail = Utree::new(n);

    for _ in 0..k {
        let p: usize = iter.next().unwrap().parse::<usize>().unwrap()-1;
        let q: usize = iter.next().unwrap().parse::<usize>().unwrap()-1;
        road.unite(p, q);
    }

    for _ in 0..l {
        let p: usize = iter.next().unwrap().parse::<usize>().unwrap()-1;
        let q: usize = iter.next().unwrap().parse::<usize>().unwrap()-1;
        rail.unite(p, q);
    }

    let mut groups: Vec<(usize, usize)> = Vec::with_capacity(n);
    for i in 0..n {
        groups.push((road.find(i), rail.find(i)));
    }

    let hmap = count_series(&groups);
    for i in 0..n {
        print!("{}", hmap.get(&groups[i]).unwrap_or(&0));
        if i != n-1 {print!(" ");} else {print!("\n");}
    }
}

use std::collections::HashMap;
use std::hash::Hash;
#[allow(dead_code)]
fn count_series<T: Eq + Hash + Clone>(series: &[T]) -> HashMap<T, u64> {
    let mut hmap = HashMap::new();
    for item in series {
        *hmap.entry(item.clone()).or_insert(0) += 1;
    }
    hmap
}

#[allow(dead_code)]
pub struct Utree {
    n: usize,
    par: Vec<usize>,
    rank: Vec<usize>,
    size: Vec<usize>,
}
#[allow(dead_code)]
impl Utree {
    pub fn new(n: usize) -> Utree {
        Utree {
            n: n,
            par: (0..n).collect(),
            rank: vec![0; n],
            size: vec![1; n],
        }
    }
    pub fn find(&mut self, x: usize) -> usize {
        if self.par[x] == x {
            x
        } else {
            let parent = { self.par[x] };
            let ret = self.find(parent);
            self.par[x] = ret;
            ret
        }
    }
    pub fn unite(&mut self, mut x: usize, mut y: usize) {
        x = self.find(x);
        y = self.find(y);
        if x == y {
            return;
        };
        if self.rank[x] < self.rank[y] {
            self.par[x] = y;
            self.size[y] += self.size[x];
        } else {
            self.par[y] = x;
            self.size[x] += self.size[y];
            if self.rank[x] == self.rank[y] {
                self.rank[x] += 1;
            }
        }
    }
    pub fn is_same(&mut self, mut x: usize, mut y: usize) -> bool {
        x = self.find(x);
        y = self.find(y);
        x == y
    }
    pub fn get_size(&mut self, mut x: usize) -> usize {
        x = self.find(x);
        self.size[x]
    }
}

Measured memory_bytes: 38948
#include<iostream>
#include<cmath>
#include<iomanip>
#include<string>
using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    int a[n+1][m+1];
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++)
            a[i][j]=0;
    }
    for(int i=1; i<=n; i++){
        int k;
        cin>>k;
        for(int j=1; j<=k; j++){
            int b;
            cin>>b;
            a[i][b]=1;
        }
    }
    int ans=0;
    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
            if(a[j][i]==0)break;
            if(j==n&&a[n][i]==1)ans++;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<set>
using namespace std;
int main(){
    int a,b,c;
    cin >> a >> b >> c;
    if(a+b==c)  cout << "Yes\n";
    else if(a+c==b)  cout << "Yes\n";
    else if(b+c==a)  cout << "Yes\n";
    else    cout << "No\n";
}

Measured memory_bytes: 256