akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>


using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define fore(i,a) for(auto &i:a)

typedef pair <int, int> P;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
const int  INF = 1 << 30;
const ll INFL = 1LL << 60;
const ll mod = 1000000007;




int longest_increasing_subsequence(const vector<int> &v) {
	int n = v.size();
	vector<int> dp(n, INF);
	for (int i = 0; i < n; i++)
		*upper_bound(dp.begin(), dp.end(), v[i]) = v[i];
	return find(dp.begin(), dp.end(), INF) - dp.begin();
}



int main() {


	int n;
	cin >> n;
	VI a(n);
	REP(i, n)cin >> a[i];
	reverse(ALL(a));

	cout<<longest_increasing_subsequence(a)<<endl;

}

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

#define rep(i,n) for(int i = 0; i < n; i++)
#define Rep(i,n) for(int i = 1; i <= n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
template<class T> using V = vector<T>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }



int main(){
    int n;
    cin >> n;
    V<int> dp(n+1);
    dp[0] = dp[1] = 1;
    for(int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    cout << dp[n] << endl;
}


Measured memory_bytes: 3104
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define ABS(X) ((X)<0?-(X):(X))
#define N 1000

int main(void){
  int n;
  vector<long long int> v;
  
  scanf("%d", &n);
  for (int i=0; i<n; i++){
    long long int tmp;
    scanf("%lld", &tmp);
    v.push_back(tmp);
  }
  sort(v.begin(), v.end());
  int m;
  for (m=0;m<n; m++){
    if (v[m]*2 > v[n-1]) break;
  }
  if (v[m]*2 - v[n-1] >= v[n-1] - v[m-1]*2) m--;
  
//  for (int i=0; i<n; i++){
//    printf("%d ", v[i]);
//  }puts("");
  printf("%d %d\n", v[n-1], v[m]);
  return 0;
}

Measured memory_bytes: 1400
N = int(input())
w = ""
S = []
f = True
for i in range(N):
    W = input()
    if i != 0:
        if W[0] != w[(len(w) - 1)] or W in S:
            f = False
            break
    w = W
    S.append(w)
if f == True:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9124
from typing import List

class UnionFind:
	def __init__(self, V: int) -> None:
		self.V: int = V
		self.pi: List[int] = [i for i in range(V)]
		self.rank: List[int] = [0 for _ in range(V)]

	def findSet(self, x: int) -> int:
		if x != self.pi[x]:
			self.pi[x] = self.findSet(self.pi[x])
		return self.pi[x]

	def same(self, x: int, y: int) -> bool:
		return self.findSet(x) == self.findSet(y)

	def link(self, x: int, y: int) -> None:
		if self.rank[x] > self.rank[y]:
			self.pi[y] = x
		else:
			self.pi[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def unite(self, x: int, y: int) -> None:
		self.link(self.findSet(x), self.findSet(y))


class Edge:
	def __init__(self, source: int, target: int, cost: int) -> None:
		self.source = source
		self.target = target
		self.cost = cost


def kruskal(n: int, edges: List[Edge]) -> int:
	totalCost: int = 0
	edges.sort(key=lambda e: e.cost)
	uf: UnionFind = UnionFind(n + 1)
	for e in edges:
		if not uf.same(e.source, e.target):
			totalCost += e.cost
			uf.unite(e.source, e.target)
	return totalCost


if __name__ == "__main__":
	n, m = map(int, input().split())
	edges: List[Edge] = []
	for _ in range(m):
		s, t, c = map(int, input().split())
		edges.append(Edge(s, t, c))
	ans = kruskal(n, edges)
	print(ans)


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

int main()
{
    string s,a,b;
    ll i,j,x=0;
    cin>>s;

    for(i=0, j=s.size()-1; i<s.size()/2; i++,j--)
        {
            if(s[i]!=s[j])
                x++;
        }

    cout<<x<<endl;

    return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, XYC):
    K2 = 2*K
    ans = [[0] * (K2+K2) for _j in range(K2+K2)]
    XY = list(
        map(lambda x:
            (x[0] % K2, (x[1] if x[2] == 'W' else x[1] + K) % K2), XYC
            )
    )

    for x, y in XY:
        ans[x][y] += 1
        ans[x+K][y] -= 1
        ans[x][y+K] -= 1
        ans[x+K][y+K] += 1

        ans[x+K][y+K] += 1
        ans[x+2*K][y+K] -= 1
        ans[x+K][y+2*K] -= 1
        ans[x+2*K][y+2*K] += 1

    for i in range(K2+K2):
        for j in range(1, K2+K2):
            ans[i][j] += ans[i][j-1]
    for i in range(1, K2+K2):
        for j in range(K2+K2):
            ans[i][j] += ans[i-1][j]

    ans_ = [[0] * K2 for _j in range(K2)]
    for i in range(K2+K2):
        for j in range(K2+K2):
            ans_[i % K2][j % K2] += ans[i][j]

    return max(max(r) for r in ans_)


def main():
    N, K = read_int_n()
    XYC = [read_str_n() for _ in range(N)]
    XYC = list(map(lambda x: (int(x[0]), int(x[1]), x[2]), XYC))
    print(slv(N, K, XYC))


if __name__ == '__main__':
    main()


Measured memory_bytes: 241760
#include <stdio.h>


int main(){

  int n,q,S[100000],T[100000],i,j,count=0,left,right,mid,key;

  scanf("%d",&n);

  for(i=0;i<n;i++){

    scanf("%d",&S[i]);

  }
   scanf("%d",&q);

  for(i=0;i<q;i++){

    scanf("%d",&T[i]);

  }
  for(j=0;j<q;j++){
    
    key=T[j];
    S[n]=key;
      left=0;
      right=n;
      while(left<right){

      mid=(left+right)/2;
      // printf("%d\n",mid);
      if(S[mid]==key){
	count++;
	break;
      }
      else if(key<S[mid]){
	
	right=mid;

      }
      else  left=mid+1;
      
      }
  }
  

  printf("%d\n",count);

  return 0;
}

  
  



Measured memory_bytes: 2304
#!/usr/bin/env python3

n = int(input())
di = []
for i in range(n):
    d = int(input())
    di.append(d)

di = sorted(di, reverse=True)

res = 1
top = di[0]
for i in range(1, n):
    if di[i] < top:
        top = di[i]
        res += 1

print(res)


Measured memory_bytes: 3060
N = int(input())
C = input()

C_list = list(C)

W_count = C_list.count('W')
R_count = C_list.count('R')

tmp = ['R']*R_count + ['W']*W_count

ans = 0

for i in range(N):
    if C_list[i] != tmp[i]:
        ans += 1
        
print(ans//2)

Measured memory_bytes: 13872
N, A, B = map(int, input().split())

if A > B or (N == 1 and A != B):
    print(0)
    exit()

if N == 1 or A == B:
    print(1)
    exit()

minS = A * (N - 1) + B
maxS = A + B * (N - 1)

print(maxS - minS + 1)

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

using namespace std;

int n , k;

int add (int a , int b) {
    a = (a % k + k) % k;
    b = (b % k + k) % k;
    return (a + b) % k;
}

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

    cin >> n >> k;

    vector<int> a(n + 1);
    for (int i = 1 ;i <= n ;i++)
        cin >> a[i];

    map<int , int> mp;
    mp[0]++;

    long long ans = 0;
    vector<int> save(n + 1);
    save[0] = 0;

    int sum = 0;
    for (int i = 1 ;i <= n ;i++) {
        sum = add(sum , a[i]);
        if (i - k >= 0)
            mp[save[i - k]]--;
        ans += mp[add(sum , -i)];
        mp[add(sum , -i)]++;
        save[i] = add(sum , -i);
    }

    cout << ans;
}

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

using namespace std;

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

    std::string ans = "";
    while (n > 0) {
        --n;
        ans += (char) (n % 26 + 'a');
        n /= 26;
    }

    for (int i = ans.size() - 1; i >= 0; --i) {
        std::cout << ans[i];
    }
    
    return 0;
}


Measured memory_bytes: 3636
N = int(input())
S = input()

rcount = S.count("R")
gcount = S.count("G")
bcount = N-rcount-gcount



count = rcount * gcount * bcount
k = 0
for i in range(N-1):
    for j in range(i+1,N):
        k = 2*j-i
        if k < N :
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                count -= 1
print(count)


Measured memory_bytes: 9128
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <bitset>
#include <functional>
#include <cassert>

#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}

ll conbinationMemo[100][100];

void cmemoInit(){
    rep(i, 100){
        rep(j, 100){
            conbinationMemo[i][j] = -1;
        }
    }
}
 
ll nCr(ll n, ll r){
    if(conbinationMemo[n][r] != -1) return conbinationMemo[n][r];
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return conbinationMemo[n][r] = (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
//-----------------------ここから-----------
int main(void){
    int h, w, k;
    cin >> h >> w >> k;
    vector<string> s(h);
    rep(i, h){
        cin >> s[i];
    }
    int ans = 0;
    for(int bh = 0; bh < (1 << h); bh++){
        
        vector<int> noth(h, 0);
        rep(i, h){
            if(bh & (1 << i)){
                noth[i] = 1;
            }
        }

        for(int bw = 0; bw < (1 << w); bw++){
            vector<int> notw(w, 0);
            rep(i, w){
                if(bw & (1 << i)){
                    notw[i] = 1;
                }
            }

            int tmp = 0;
            rep(i, h){
                if(noth[i]) continue;
                rep(j, w){
                    if(notw[j])continue;
                    if(s[i][j] == '#') tmp++;
                }
            }

            if(tmp == k){
                //cout << bh << " " << bw << endl;
                ans++;
            }

        }
    }

    cout << ans << endl;


}


Measured memory_bytes: 3628
def ord(N,n):#N,nは正の整数、Nで割り切れる回数、許容はN^1000
    if n%N!=0:
        return 0
    else:
        return 1+ord(N,n//N)

def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

primelist=get_sieve_of_eratosthenes_new(32*(10**2))

def cmb(n, r, mod):#コンビネーションの高速計算　
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


def main():
    N,M=map(int,input().split())
    product=1
    for i in range(0,len(primelist)):
        product=(product*cmb(ord(primelist[i],M)+N-1,N-1,mod))%mod
        M=M//primelist[i]**ord(primelist[i],M)
    if M!=1:
        product=(product*N)%mod
    print(product)

if __name__ == '__main__':
    main()


Measured memory_bytes: 81520
#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> a(100009),b(100009),c(100009);
int memo[100009][5];

int main(){
  cin >> N;
  for(int i=1;i<=N;i++)cin >> a[i] >> b[i] >> c[i];
  memo[1][1]=a[1];
  memo[1][2]=b[1];
  memo[1][3]=c[1];
  for(int i=2;i<=N;i++){
    memo[i][1]=max(memo[i-1][2]+a[i],memo[i-1][3]+a[i]);
    memo[i][2]=max(memo[i-1][1]+b[i],memo[i-1][3]+b[i]);
    memo[i][3]=max(memo[i-1][2]+c[i],memo[i-1][1]+c[i]);
  }
  cout << max({memo[N][1],memo[N][2],memo[N][3]}) << endl;
}

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

using namespace std;

int main(){
#ifdef LOCAL
	freopen("input", "r", stdin);
#endif 

	long long a[2], b[2];

	cin >> a[0] >> a[1] >> b[0] >> b[1];

	long long ans = -1e18+7;

	for (int i = 0; i < 2; i++){
		for (int j = 0; j < 2; j++){
			ans = max(ans, a[i] * b[j]);
		}
	}

	cout << ans << endl;

	return 0;
}

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

typedef long long ll;

const int MAXV = 1e5 + 10;
const int MAXN = 1e3 + 10;
const ll INF = 1e13;

ll dp[MAXV];
int N,W,V,wi[MAXN],vi[MAXN];

int main(){

	cin >> N >> W;
	for(int i = 1;i<=N;i++){
		cin >> wi[i] >> vi[i];
		V += vi[i];
	}

	for(int i = 1;i<=V;i++) dp[i] = INF;
	dp[0] = 0;
	
	for(int item = 1;item<=N;item++){
		int w = wi[item], v = vi[item];
		for(int i = V;i>=v;i--){
			dp[i] = min(dp[i],dp[i - v] + w);
		}
	}

	for(int i = V;i>=0;i--){
		if(dp[i] <= W){
			cout << i << endl;
			break;
		}
	}

	return 0;

}


Measured memory_bytes: 1024
// 問題の URL を書いておく
// 

#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>

using namespace std;

//#define ENABLE_PRINT

#if defined(ENABLE_PRINT)

#define Print(v) \
do {\
    cout << #v << ": " << v << endl; \
}while(0)

#define PrintVec(v) \
do {\
    for(int __i = 0; __i < v.size(); ++__i) \
    { \
        cout << #v << "[" << __i << "]: " << v[__i] << endl; \
    }\
}while(0)

#else

#define Print(v) ((void)0)
#define PrintVec(v) ((void)0)

#endif

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

using ll = int64_t;

const int HMax = 1005;
const int WMax = 1005;
const int M = 1e9 + 7;
ll dp[HMax][WMax];

int main(int, const char**)
{
    int H, W;
    cin >> H >> W;
    vector<string> grid(H);
    rep(i, H)
    {
        cin >> grid[i];
    }
    dp[0][0] = 1;
    struct Point
    {
        int x;
        int y;
    };
    queue<Point> q;
    q.push({0, 0});
    rep(i, H)
    {
        rep(j, W)
        {
            if(i == 0 && j == 0 && grid[0][0] == '.')
            {
                dp[0][0] = 1;
                continue;
            }
            if(grid[i][j] == '.')
            {
                auto u = i == 0 ? 0 : dp[i - 1][j];
                auto l = j == 0 ? 0 : dp[i][j - 1];
                dp[i][j] = (u + l) % M;
            }
        }
    }

    cout << dp[H - 1][W - 1] << endl;
    return 0;
}


Measured memory_bytes: 13272
#include <stdio.h>

int ans ;
int sum ;
int n ;
int p ;
int q ;
int num[5010] ;

int main()
{
	while ( scanf ( "%d" , &n ) == 1 && n ) {
		for ( int i = 0 ; i < n ; i++ ) {
			scanf ( "%d" , &num[i] ) ;
		}
		ans = -2147483647 ;
		sum = 0 ;
		for ( int i = 0 ; i < n ; i++ ) {
			sum += num[i] ;
			if ( sum > ans ) {
				ans = sum ;	
				q = i ;
			}
			if ( sum < 0 ) {
				sum = 0 ;
				p = i + 1 ;	
			}
		}
		printf ( "%d\n" , ans ) ;
	}
	return 0 ;
}

Measured memory_bytes: 1044
#include <iostream>
#include <cmath>
#include <iomanip>
#include <bits/stdc++.h>

using namespace std;

int main(void){
  int R;
  cin >> R;
  double ans;
  cout << fixed << setprecision(10);
  ans = 2.0*((double)R)*M_PI;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3788
x, y = (input().split(' '))

x = int(x)

y = int(y)

money = 0

if x == 1:
    money += 300000
if x == 2:
    money += 200000
if x == 3:
    money += 100000

if y == 1:
    money += 300000
if y == 2:
    money += 200000
if y == 3:
    money += 100000

if money == 600000:
    money = 1000000

print(money)

Measured memory_bytes: 3064
n = int(input())
A = [int(x) for x in input().split()]
sumA = sum(A)
counter = [0]*(10**5+1)
for i in range(n):
    counter[A[i]] += 1

q = int(input())

queue = [list(map(int,input().split())) for i in range(q)]

for b,c in queue:    
    b_cnt = counter[b]
    sumA -= (b*b_cnt)
    counter[b] = 0
    c_cnt = counter[c]
    sumA += c*(b_cnt)
    counter[c] += b_cnt
    print(sumA)
    

Measured memory_bytes: 32644
#include <bits/stdc++.h>
#include<string.h>
using namespace std;
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define Max(x,y,z) max(x,max(y,z))
#define Min(x,y,z) min(x,min(y,z))
#define fr(i,s,e) for(i=s;i<e;i++)
#define rf(i,s,e) for(i=s-1;i>=e;i--)
#define pb push_back
#define eb emblace_back
#define mp make_pair
#define ff first
#define ss second
//#define int   long long
#define ll   long long
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define vl vector<long long>
#define inf (1LL<<61)
#define vi vector<int>
#define vii vector< vector<int> >
#define vll vector< vector<long long> >
#define vpi vector< pair<int,int> >
#define vpl vector< pair<ll,ll> >
#define viii vector< vector<vector<int> > >
typedef pair<pair<int, int>,int> P;
#define cd complex<double>
#define PI 4*atan(1)
#define mod %1000000007
#define pi 3.14159265358979323846//20 decimals
#define ld long double

int main()
{
	//FAST;
	string s, t;
	ll i, j, l1, l2, k;
	cin >> s;
	cin >> t;
	l1 = s.length();
	l2 = t.length();
	ll dp[l1+1][l2+1];
	fr(i,0,l1+1)
		fr(j,0,l2+1)
		{
			if((i == 0)||(j == 0))
				dp[i][j] = 0;
			else if(s[i-1] == t[j-1])
				dp[i][j] = 1 + dp[i-1][j-1];
			else
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
		}
	ll l = dp[l1][l2];
	char c[l+1];
	c[l] = '\0';
	i = l1; j = l2; k = l-1;
	while(1)
	{
//		trace3(i,j,k);
		if(k == -1)
			break;
		if(s[i-1] == t[j-1])
		{
			c[k] = s[i-1];
			i--; j--; k--;
		}
		else if(dp[i][j-1] > dp[i-1][j])
			j--;
		else
			i--;
	}
	cout << c;
}


Measured memory_bytes: 70656
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <iostream>

#pragma comment(linker, "/STACK:336777216")  

using namespace std;

const int MAXN = 100000 + 10;

int N, K;
int A[MAXN], B[MAXN];

long long Find(int Mask)
{
	long long Ret = 0;
	for (int i = 0; i < N; i ++)
		if ((A[i] & Mask) == A[i])
			Ret += (long long) B[i];
	return Ret;
}

void Work()
{
	scanf("%d%d", &N, &K);
	for (int i = 0; i < N; i ++)
		scanf("%d%d", &A[i], &B[i]);
	
	int Base = 0;
	long long Ans = max(Find(0), Find(K));
	for (int L = 30; L >= 0; L --)
	{
		if (K & (1 << L))
		{
			Ans = max(Ans, Find(Base | ((1 << L) - 1)));
			Base |= (1 << L);
		}
	}
	printf("%lld\n", Ans);
}

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

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define int long long
#define sz(s) (int)(s).size() 
 
using namespace std;
const int hell = 1e9+7;

void solve(){
	int n , ans = 0;
	cin >> n;
	vector<int>arr(n);
	for(int i=0 ; i < n ; i++) cin >> arr[i];
	sort(arr.begin(),arr.end());
	for(int i = 0 ; i < n-2 ; i++ ){
		for(int j = i+1 ; j < n-1 ; j++ ){
			int index = lower_bound(arr.begin(),arr.end(),arr[i]+arr[j])-arr.begin();
			ans += max(index - j-1,0ll);
			//cout << i << ' ' << j << ' ' << index << ' ' << ans << endl;
		}
	}
	cout << ans << endl;
}
 
int32_t main(){                                    
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    	cout.precision(10);
    	cout << fixed;
#ifdef LOCAL
    freopen("input.txt", "rt", stdin);
    freopen("output.txt","w",stdout);
#endif
        int q=1;
        //cin>>q;
        while(q--){
            solve();
        }
               
#ifdef LOCAL
    cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
 
	return 0;
}	
 

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

#define ll long long
#define all(x) (x).begin(), (x).end()
const long long INF = 1LL << 60;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)  //(i, 10) i=0～i=9まで
#define repr(i, n) for (int i = n; i >= 0; i--)   // (i, 10) i=10～i=0まで
#define FOR(i, m, n) for (int i = m; i < n; i++)  // (i, 3, 10) i=3～i=9まで

// 総数を1000000007で割った余り
const long long mod = 1e9 + 7;

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

    // 入力
    int  a, b;
    char op;
    cin >> a >> op >> b;

    // 処理
    // 出力
    cout << (op == '+' ? a + b : a - b) << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
typedef long long int ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i < (int)(n); i++)
#define Sort(a) sort(a.begin(), a.end())
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
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 n, m, q;
int a[55], b[55], c[55], d[55];
ll sum, max_;
int row[15];

void dfs(int i, int cnt){
    row[cnt] = i;
    cnt++;
    if(cnt <= n) {
        for(int j = i; j <= m; j++){
            dfs(j, cnt);
        }
    }
    else {
        //int e[n+1];
        /*
        rep(j, n){
            e[n-j] = row%10;
            row /= 10;
        }*/
        rep(j, q){
            if(row[b[j]] - row[a[j]] == c[j]){
                sum += d[j];
            }
            //cout << row[b[j]] << " - " << row[a[j]] << " = " << c[j] << endl;
        }
        max_ = max(sum, max_);
        sum = 0;
    }
}

int main(){
    cin >> n >> m >> q;
    rep(i, q){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    REP(i, 11){
        dfs(i, 1);
    }
    cout << max_ << endl;
    return 0;
}

Measured memory_bytes: 3620
import java.io.File;
import java.io.FileInputStream;
import java.util.NoSuchElementException;
import java.util.Scanner;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map.Entry;

public class Main {
	static int N;
	static char[][] A;
	static int M;
	static char[][] B;
	
	public static void main(String[] args) throws IOException {
		//File file = new File("input.txt");
		//Scanner sc = new Scanner(file);
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		A = new char[N][N];
		for(int i = 0; i < N; i++) A[i] = sc.next().toCharArray();
		B = new char[M][M];
		for(int i = 0; i < M; i++) B[i] = sc.next().toCharArray();
		
		for(int ii = 0; ii <= N - M; ii++){
			for(int jj = 0; jj <= N - M; jj++){
				if(comp(ii, jj)){
					System.out.println("Yes");
					//System.out.println(ii + " " + jj);
					return;
				}
			}
		}
		System.out.println("No");
	}
	
	public static boolean comp(int ii, int jj){
		for(int i = 0; i < M; i++){
			for(int j = 0; j < M; j++){
				if(A[i + ii][j + jj] != B[i][j])
					return false;
			}
		}
		return true;
	}
}

Measured memory_bytes: 23124
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>
#include <iomanip>
#include <random>


#define FOR_LT(i, beg, end) for (int i = beg; i < end; i++)
#define FOR_LE(i, beg, end) for (int i = beg; i <= end; i++)
#define FOR_DW(i, beg, end) for (int i = beg; end <= i; i--)

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(20);

	int64_t a, b, m; cin >> a >> b >> m;
	vector<int64_t> rs(a);
	vector<int64_t> ds(b);

	int64_t rmin = std::numeric_limits<int>::max();
	for (auto& r : rs) {
		cin >> r;
		rmin = min(rmin, r);
	}
	int64_t dmin = std::numeric_limits<int>::max();
	for (auto& d : ds) {
		cin >> d;
		dmin = min(dmin, d);
	}

	struct Dis {
		int x;
		int y;
		int64_t c;
	};
	vector<Dis> diss(m);
	for (auto& d : diss) {
		cin >> d.x >> d.y >> d.c;
	}

	int64_t ans = rmin + dmin;
	for (auto& d : diss) {
		int64_t c = rs[d.x - 1] + ds[d.y - 1] - d.c;
		ans = min(c, ans);
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3456
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.Stack;

public class Main{
	public static class FastReader {
		BufferedReader br;
		StringTokenizer root;
		
 
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String next() {
			while (root == null || !root.hasMoreTokens()) {
				try {
					root = new StringTokenizer(br.readLine());
				} catch (Exception r) {
					r.printStackTrace();
				}
			}
			return root.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(next());
		}
 
		double nextDouble() {
			return Double.parseDouble(next());
		}
 
		long nextLong() {
			return Long.parseLong(next());
		}
 
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception r) {
				r.printStackTrace();
			}
			return str;
		}
	}
	
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	static int mod = (int) (1e9+7),n;
	static long cf = 998244353;
    static final int MAX = (int) 1e6;
    public static List<Integer>[] edges;
    public static int[][] parent;
    public static int col = 20;
    public static long[] Bit;
    public static long[] fac,inv;
    public  static int[] prime; 
    public static long[] dp;
	public static FastReader sc = new FastReader();
	public static void main(String[] args) {
	//	Scanner sc = new Scanner(System.in);
 
		int n = sc.nextInt();
		int h = sc.nextInt();
		int ans = 0;
		for(int i=0;i<n;++i) {
			int x = sc.nextInt();
			if(x >= h) ++ans;
		}
		out.print(ans);
		out.close();
	}
	
	
}

Measured memory_bytes: 31084
#include <iostream>


using namespace std;





// main
int main( int argc, char *argv[] )
{
	typedef long long llong;

	char input;
	char cond = '<';

	llong sum = 0;
	llong count = 0;
	llong last = 0;


	bool exflag = false;
	while(!exflag)
	{
		scanf("%c", &input);
		if(input != '<' && input != '>')
		{
			if(cond == '<')
				sum += count,
				input = '>';
			else
				input = '<';
			exflag = true;
		}

		if(cond == '<')
		{
			if(input == '<')
				++count;
			else
			{
				sum += (count - 1) * count / 2;
				last = count;
				count = 1;
				cond = '>';
			}
		}
		else
		{
			if(input == '>')
				++count;
			else
			{
				sum += max(last, count);
				sum += (count - 1) * count / 2;
				count = 1;
				cond = '<';
			}
		}
	}
	
	
	
	// output
	printf("%lli\n", sum);



	return 0;
}





// end


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
using namespace std;
#define int long long
typedef pair<int, int> P;
int a[51];
P sa[51];
vector<P>lg;
signed main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i]; sa[i] = P(a[i],i);
	}
	sort(sa, sa + n);
	if (abs(sa[0].first) < abs(sa[n - 1].first)) {
		for (int i = 0; i < n; i++) {
			lg.push_back(P(sa[n - 1].second+1, i + 1));
			a[i] += sa[n - 1].first;
		}
	}
	else {
		for (int i = 0; i < n; i++) {
			lg.push_back(P(sa[0].second + 1, i + 1));
			a[i] += sa[0].first;
		}
	}
	if (a[0] > 0) {
		for (int i = 0; i < n - 1; i++)lg.push_back(P(i + 1, i + 2));
	}
	else {
		for (int i = n - 1; i > 0; i--)lg.push_back(P(i + 1, i));
	}
	cout << lg.size() << endl;
	for (int i = 0; i < lg.size(); i++)cout << lg[i].first<<' '<<lg[i].second << endl;
}

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

int main(){
  int n;
  cin >> n;
  set<int> mul;
  for (int i = 1; i <= 9; i++){
    for (int j = 1; j <= 9; j++){
      mul.insert(i * j);
    }
  }
  if (mul.find(n) != mul.end()){
    cout << "Yes" << endl;
  }
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;cin>>n;
  vector<int>a(n);
  for(int i=0;i<n;i++) cin>>a[i];
  sort(a.begin(),a.end());
  int m=0,f=0,p=0;
  for(int i=0;i<n;i++){
    if(a[i]==a[0]) f++;
    if(a[i]==a[0]+1) p++;
    if(a[i]>=a[0]+2) break;
  }
  m+=f+p;
  int b=0;
  for(int i=f;i<n;){
    int c=0;int d=0;int e=0;
    for(int j=b;j<n;j++){
      if(a[j]==a[i]-1) c++;
      if(a[j]==a[i]) d++;
      if(a[j]==a[i]+1) e++;
      if(a[j]>=a[i]+2) break;
    }
    m=max(c+d+e,m);
    i+=d;
    b+=c;
  }
  cout<<m<<endl;
}
  
    

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String w = scan.next();
        char[] ws = w.toCharArray();

        for (char i = 'a'; i <= 'z'; i++) {
            int count = 0;
            for (int j = 0; j < ws.length; j++) {
                if (ws[j] == i) count++;
            }

            if (count % 2 != 0) {
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");
        
    }
}


Measured memory_bytes: 23124
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <list>
#include <deque>
using namespace std;
#define INF 10000000
#define LLINF 100000000000000
typedef pair<int, int> P;
typedef long long ll;
#define pb push_back
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define VSORT(v) sort(v.begin(), v.end());
#define fi first
#define se second
#define out(x) cout << x << endl;
int dx[] = { 1, 0, -1, 0 }, dy[] = { 0,1,0,-1 };
ll MOD = 1000000007;
struct edge {
	ll from, to, cost;
};

string a, b;
int m, n;
int res = 0;
char c[] = { 'O','I' };

int dp[2005][2005][2] = { 0 };

int main() {
	cin >> m >> n;
	cin >> a >> b;
	for (int i = 0; i <= m; i++) {
		for (int j = 0; j <= n; j++) {
			if (i == 0 && j == 0) continue;
			if (i >= 1 && a[i - 1] == 'O'&& dp[i-1][j][1] >= 1) {
				dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j][1] + 1);
			}
			if (j >= 1 && b[j - 1] == 'O'&& dp[i][j - 1][1] >= 1) {
				dp[i][j][0] = max(dp[i][j][0], dp[i][j - 1][1] + 1);
			}
			if (i >= 1 && a[i - 1] == 'I'&& dp[i - 1][j][0] >= 1) {
				dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j][0] + 1);
			}
			if (j >= 1 && b[j - 1] == 'I'&& dp[i][j - 1][0] >= 1) {
				dp[i][j][1] = max(dp[i][j][1], dp[i][j - 1][0] + 1);
			}
			if (i >= 1 && a[i - 1] == 'I') {
				dp[i][j][1] = max(dp[i][j][1], 1);
			}
			if (j >= 1 && b[j - 1] == 'I') {
				dp[i][j][1] = max(dp[i][j][1], 1);
			}
		}
	}
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (dp[i][j][1] % 2 == 1) res = max(res, dp[i][j][1]);
		}
	}
	cout << res << endl;
	return 0;
}


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

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

void solve(long long N, std::vector<long long> A){
    vll R(N, 0);
    for(ll i=0; i< N-1; i++){
        R[A[i]]++;
    }
    REP(i, N){
        cout<<R[i]<<endl;
    }
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N-2+1);
    for(int i = 0 ; i < N-2+1 ; i++){
        scanf("%lld",&A[i]);
        A[i]--;
    }
    solve(N, std::move(A));
    return 0;
}


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

#define pb      push_back
#define all(v)  v.begin(),v.end()
#define endl    "\n"
#define FAST    ios_base::sync_with_stdio(0);cin.tie(0);

typedef long long     ll;
typedef long double   ld;
typedef pair<int,int> ii;

const int    inf = 2e9;
const ll     INF = 4e17;
const int    mod = 1e9+7;
const double eps = 1e-9;

int main() {
	string s;
	cin >> s;
	s[3] = '8';
	cout << s << endl;
	return 0;
}



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

#define rep( i, n, m ) for(int i = ( n ); i < ( m ); i++)
#define rep_d( i, n, m ) for(int i = ( n ) - 1; i >= ( m ); i--)
#define sort_asc( X ) sort(( X ).begin(), ( X ).end())
#define sort_desc( X ) sort(( X ).begin(), ( X ).end(), greater <>())
#define endl "\n"


template <typename T, typename K> struct P {
	T a; K b;
};

template <class T> bool chmax( T& a, T b );
template <class T> bool chmin( T& a, T b );
int* eratosthenes( int N );
bool bit_search( int pattern, int N );
vector <P <ll, ll> >prime_factorize( ll N );
ll pow( ll a, ll n );
void initialize( void );

const ll INF = 1LL << 60;
const int k_mod = 1e9 + 7;
int main( void ){
	// initialize();
	ll l, r; cin >> l >> r;
	ll diff = r - l;
	diff = min( 2019LL, diff );
	ll ans = INF;
	rep( i, 0, diff ){
		rep( j, i + 1, diff+1 ){
			ans = min((( l + i ) * ( l + j )) % 2019, ans );
		}
	}
	cout << ans << endl;
}

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

/*
 * @fn eratosthenes
 * @brief O(NloglogN)~=(N)
 * @param N: その数まで
 * @return 0 or 1 の配列 (boolは都合が悪い)
 */
int* eratosthenes( int N ){
	int* prime_array = new int[ N + 1 ];
	int lim = N;
	prime_array[ 0 ] = 0;
	prime_array[ 1 ] = 0;
	rep( i, 2, N + 1 ){
		prime_array[ i ] = 1;
	}
	rep( i, 2, lim ){
		if (prime_array[ i ] == 0)
			continue;
		lim = N / i;
		for(int j = i * 2; j < N + 1; j += i){
			prime_array[ j ] = 0;
		}
	}
	return prime_array;
}
bool bit_search( int pattern, int N ){
	int cnt = 0;
	rep( bit, 0, N ){
		if (pattern & ( 1 << bit )){
			cnt++;
		}
	}
	return true;
}

/*
 * @fn prime_factorize
 * @brief O(√N): 素因数分解
 * @param N: 素因数分解する数
 * @return vec: (a: 素数, b: 個数)
 */
vector <P <ll, ll> >prime_factorize( ll N ){
	vector <P <ll, ll> > vec;
	int lim = sqrt( N ) + 1;
	rep( i, 2, N + 1 ){
		if (i >= lim){
			vec.push_back( P <ll, ll>{N, 1} );
			break;
		}
		if (N % i == 0){
			vec.push_back( P <ll, ll>{i, 0} );
			while(N % i == 0){
				N /= i;
				vec.back().b++;
			}
		}
	}
	return vec;
}
/*
 * @fn pow
 * @brief a^n
 * @param a: 基数
 * @param n: 指数
 */
ll pow( ll a, ll n ) {
	ll res = 1;
	while (n > 0){
		if (n & 1) res = res * a;
		a = a * a;
		n >>= 1;
	}
	return res;
}

void initialize( void ){
	cout << fixed << setprecision( 10 );
}


Measured memory_bytes: 256
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

s = rr()
t = rr()
if s[0] == t[2] and s[1] == t[1] and s[2] == t[0]:
  print('YES')
else:
  print('NO')

Measured memory_bytes: 27016
#define _GLIBCXX_DEBUG
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<map>
#include<string>
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define rep2(i,s,n) for(int i=s;i< (int)n; i++)
#define ll long long 
#define all(v) v.begin(),v.end()

using namespace std;
//下から押さえる
bool isOK(int index, vector<int>& a, int b, int c) {
    if (a[index] > abs(a[b]-a[c])) return true;
    else return false;
}
// 二分探索
int binary_search(vector<int>& a, int b,int c) {
    int left = c; //「index = b+1」が条件を満たすこともあるので、初期値は -1
    int right = (int)a.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()
    /* どんな二分探索でもここの書き方を変えずにできる！ */
    while (right - left > 1) {
        int mid = left + (right - left) / 2;
        if (isOK(mid, a , b, c)) right = mid;
        else left = mid;
    }
    /* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
    return right;
}


// 上から押さえる
bool isOK2(int index, vector<int>& a, int b, int c) {
    if (a[index] < a[b]+a[c]) return true;
    else return false;
}
// 二分探索
int binary_search2(vector<int>& a, int b,int c) {
    int left = c; //「index = b+1」が条件を満たすこともあるので、初期値は -1
    int right = (int)a.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()
    /* どんな二分探索でもここの書き方を変えずにできる！ */
    while (right - left > 1) {
        int mid = left + (right - left) / 2;
        if (isOK2(mid, a , b, c)) left = mid;
        else right = mid;
    }
    /* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
    return left;
}


int main(){
  int n; cin >>n;
  vector<int> L(n);
  rep(i,n) cin >>L[i];
  int ans=0;
  sort(all(L));
  rep(i,n-2){
    rep2(j,i+1,n-1){
          ans+=binary_search2(L,i,j)-binary_search(L,i,j)+1;
    }
  }
  cout <<ans<<endl;
}

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

using namespace std;

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

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

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

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

    cin >> A >> P;

    cout << (3 * A + P ) / 2 << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
typedef long long int lint;
using namespace std;

int main() {
    lint n, m, d;
    cin >> n >> m >> d;
    double ans = (n - 2 * d >= 0 && d != 0) ? 2.0 * (n - d) * (m - 1) / (n * n)
                                            : 1.0 * (m - 1) / n;
    cout << setprecision(10) << ans << endl;
}

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

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
 
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i <= (ll)(n); i++)
#define INF 10000000000
#define MOD 1000000007
using ll = long long;
using pint = pair<int,int>;
using pll = pair<ll,ll>;
using Graph = vector<vector<int>>;

int main(){
    int x,a,b; cin>>x>>a>>b;
    if(fabs(x-a)<fabs(x-b))cout<<"A"<<endl;
    else cout<<"B"<<endl;
}

Measured memory_bytes: 3564
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
#include <assert.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
const int MOD=1e9+7;
#define SZ 666666
int n;
char a[SZ];
bool v[SZ];
vi neg(vi x)
{
	reverse(x.begin(),x.end());
	for(auto&y:x) y=-y;
	return x;
}
vi operator + (vi a,const vi&b)
{
	for(auto x:b) a.pb(x);
	return a;
}
vi operator - (vi a,const vi&b)
{
	return a+neg(b);
}
vi cs(vi a,int l,int r)
{
	if(l==r)
		return {a[l]};
	int m=(l+r)>>1;
	vi L=cs(a,l,m),R=cs(a,m+1,r);
	return L+R-L-R;
}
vi CL(vi t)
{
	return t;
}
vi v1{1},v2{2};
vi AND(vi p,vi q)
{
	return CL(p+p+v1+p+p-v1+v2-q-v2-q+v2-q-v2-q);
}
int main()
{
	cin>>n>>a;
	bool ok=1;
	vi g;
	for(int i=0;i<(1<<n);++i) if(a[i]=='0'&&!v[i])
	{
		for(int j=0;j<(1<<n);++j) if((j&i)==i)
			v[j]=1,ok&=a[j]=='0';
		vi t;
		for(int j=0;j<n;++j) if(i&(1<<j)) t.pb(j+1);
		vi w=cs(t,0,t.size()-1);
		g=g+w;
	}
	if(!ok)
	{
		puts("Impossible");
		return 0;
	}
	puts("Possible");
	vector<pii> v;
	v.pb(pii(0,0));
	for(auto c:g)
	{
		int x=abs(c);
		if(c>0)
		{
			v.pb(pii(x-1,0));
			v.pb(pii(x-1,1));
			v.pb(pii(x,1));
			v.pb(pii(x,0));
		}
		else
		{
			v.pb(pii(x,0));
			v.pb(pii(x,1));
			v.pb(pii(x-1,1));
			v.pb(pii(x-1,0));
		}
	}
	v.pb(pii(0,0));
	vector<pii> vt;
	for(int i=0;i<v.size();++i)
	{
		pii A=v[i],B=v[(i+1)%v.size()];
		vt.pb(A);
		int g=abs(A.fi-B.fi)+abs(A.se-B.se);
		if(g)
		{
			for(int j=1;j<=g;++j)
			{
				pii s(A.fi+(B.fi-A.fi)/g*j,
				A.se+(B.se-A.se)/g*j);
				vt.pb(s);
			}
		}
	}
	vt.erase(unique(vt.begin(),vt.end()),vt.end());
	v=vt;
	printf("%d\n",int(v.size())-1);
	for(auto c:v) printf("%d %d\n",c.fi,c.se);
}


Measured memory_bytes: 640
#include <iostream>

using namespace std;

int main(void) {
	int n;
	int ans;

	cin >> n;

	for (int i = 0; i < 11; i++) {
		if (i * 1000 >= n) {
			ans = i * 1000 - n;
			break;
		}
	}

	cout << ans;
	return 0;
}

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

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t,a,b,c;
	t = 1;
	while(t--) {
	 cin >> a >> b >> c;
	 cout << (a * b) / 2 << endl;
	}
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define ll long long
using namespace std;

int main() {
  int m;
  cin >> m;
  cout << 24 - m + 24 << "\n";
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
#define rall(a) (a).rbegin(),(a).rend()
const int INF = 2e9;
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

char G[22][22];
queue<pair<int,int>> que;
// North, west, south, east
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, -1, 0, 1};



int main(){
    int h, w;
    cin >> h >> w;
    int ans = 0;

    rep(i,h){
        rep(j,w){
            cin >> G[i][j];
        }
    }

    rep(i,h){
        rep(j,w){
            if(G[i][j] == '#') continue;
            que.push(P(i,j));
            int dist[22][22];

            rep(k,h){
                rep(l,w){
                    dist[k][l] = -1;
                }
            }

            dist[i][j] = 0;

            while(!que.empty()){
                P p = que.front();
                que.pop();

                rep(i,4){
                int ny = p.first + dy[i];
                int nx = p.second + dx[i];

                if(-1 < ny && ny < h && -1 < nx && nx < w && G[ny][nx] == '.' && dist[ny][nx] == -1 ){
                    dist[ny][nx] = dist[p.first][p.second] + 1;
                    que.push(P(ny,nx));
                }

                }

            }

            rep(k,h){
                rep(l,w){
                    ans = max(ans, dist[k][l]);
                }
            }

        

        }
    }


    dunk(ans);
}

Measured memory_bytes: 256
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>

#define MAX 1000000002
#define INF (2 << 28)
#define fr first
#define sc second
using namespace std;

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

int N, Q;
iP s[1000000];
set <iP> Leader;
vector <int> sorted; 

void ADD(int n) {
 
  Leader.insert(s[n - 1]);
}

void REMOVE(int n) {
 
  Leader.erase(Leader.find(s[n - 1]));
}

int CHECK(int x) {
  
  int l = 0, r = MAX;
  while(l < r) {
    int mid = (l + r) / 2, cnt = 0;
    vector <int>::iterator lb, lu, ll = sorted.end(), rr = sorted.begin();
    for(set<iP>::iterator it = Leader.begin(); it != Leader.end(); it++) {
      lb = lower_bound(sorted.begin(), sorted.end(), (*it).fr - mid);
      lu = upper_bound(sorted.begin(), sorted.end(), (*it).fr);
      //if(lu != sorted.end()) {
        if(rr >= lb) lb = rr;
        cnt += lu - lb;
        rr = lu, ll = lb;
        // }
    }
    if(N - cnt > x) l = mid + 1;
    else r = mid;
  }
  return l;
}
  
int main() {
  
  cin >> N >> Q;
  sorted.resize(N);
  for(int i = 0; i < N; i++) {
    cin >> s[i].fr; s[i].sc = i;
  }

  for(int i = 0; i < N; i++)
    sorted[i] = s[i].fr;
  sort(sorted.begin(), sorted.end());
  
  while(Q--) {
    int x;
    string query; cin >> query >> x;
    if(query == "ADD") ADD(x);
    else if(query == "REMOVE") REMOVE(x);
    else {
      int ans = CHECK(x);
      if(ans == MAX) cout << "NA\n";
      else cout << ans << endl;
    }
  }
}

Measured memory_bytes: 12952