akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cstdio>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;

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

int main() {
    int n;
    cin >> n;
    vi64 a(3 * n);
    forn(i, 3 * n) cin >> a[i];
    sort(rall(a));
    i64 ans = 0;
    forn(i, n) ans += a[2 * i + 1];
    cout << ans << '\n';
}


Measured memory_bytes: 2560
# import numpy as np
# import scipy as sp
# print(a,b,c,sep="") # 半角スペースなしで出力(abc)
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 文字列の二次元配列入力
# s = [list(map(int, input().split())) for i in range(n)] # 数値の二次元配列入力
# import sys ; sys.exit() # プログラム終了
# from copy import deepcopy ; b=deepcopy(a)
# chr(ord('a') + 1)
# s.sort(key=lambda x: x[1], reverse=False) # 2番目の要素で昇順にソート（Trueなら降順）
#
a = max(map(int, input().split()))
if a <= 999:
    ans = 'ABC'
else:
    ans = "ABD"

print(ans)


Measured memory_bytes: 2940
def solve():
    n = int(input())
    a = list(map(int, input().split(" ")))
    ans_dict = {}
    for i in range(n):
        for j in [a[i]-1, a[i], a[i]+1]:
            if j in ans_dict.keys():
                ans_dict[j] += 1
            else:
                ans_dict[j] = 1
    
    print(max(ans_dict.values()))

solve()

Measured memory_bytes: 19680
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
using namespace std;

# define ll long long

int main()
{
	int n;
	cin >> n ;
	vector<int> h(n);
	int k = 2;
	for (int i = 0; i < n; i++) { int a; cin >> a; h[i] = a; }
	vector<int> dp(n, 1000000);
	dp[0] = 0;
	for (int i = 1; i < n; i++) {
		dp[i] = dp[i - 1] + abs(h[i - 1] - h[i]);
		for (int j = 2; j < min(i+1, k + 1); j++) {
			dp[i] = min(dp[i - j] + abs(h[i - j] - h[i]), dp[i]);
		}

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

Measured memory_bytes: 4052
n, m = map(int, input().split())
S = []
for _ in range(n):
	a, b = map(int, input().split())
	S.append([a, b])
P = []
for _ in range(m):
	c, d = map(int, input().split())
	P.append([c, d])
sorted(P)
for s in S:
	sx, sy = s[0], s[1]
	minv = float('inf')
	minvp = -1
	for i, p in enumerate(P):
		px, py = p[0], p[1]
		d = abs(px - sx) + abs(py - sy)
		if d < minv:
			minv = d
			minvp = i
	print(minvp + 1)

Measured memory_bytes: 39280
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll  long long
#define FASTINOUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int N=2e5+9;
short dp[N][2019];
ll ls;
string s;
int main()
{
    FASTINOUT;
    cin>>s;
    ls=s.length();
    ll ans=0;
    dp[0][s[0]-'0']++;
    for (int i=1;i<ls;i++){
        ll kl=s[i]-'0';
        for (int j=0;j<2019;j++){
            dp[i][(j*10+kl)%2019]+=dp[i-1][j];
        }
        dp[i][kl]++;
        ans+=dp[i][0];
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 792400
// In the name of God

#include <bits/stdc++.h>

using namespace std;

#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL);
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i, a, b) for(int i=(a); i<(b); i++)

long long b[25];

int main() {
	IOS
	int n, m, c;
	cin >> n >> m >> c;
	rep(i, 0, m) cin >> b[i];
	int cnt = 0;
	rep(i, 0, n) {
		long long sum = 0;
		rep(j, 0, m) {
			long long a;
			cin >> a;
			sum += b[j]*a;
		}
		if(sum+c > 0) cnt++;
	}
	cout << cnt;
	return 0;
}


Measured memory_bytes: 256
N=int(input())
from math import sqrt, log10

def divisor(num):
    max_num = int(sqrt(num))
    divisor_list = []
    for i in range(1, max_num + 1):
        if num % i == 0:
            divisor_list.append(i)
            # divisor_list.append(num//i)
    return divisor_list
ans = float("inf")
for div in divisor(N):
    a = div
    b = N//div
    da = int(log10(a)) + 1
    db = int(log10(b)) + 1
    ans = min(ans, max(da,db))

print(ans)

Measured memory_bytes: 66696
int main(int argc, const char * argv[])
{
    int a, b; 
    scanf("%d %d", &a, &b); 
    if( a < b ){   
        printf("a < b\n");
    }else if( a == b ){   
        printf("a == b\n");
    }else{  
        printf("a > b\n");
    }
    
    return 0;
    }

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

using namespace std;

const int md = 1e9 + 7;

inline int add(int a, int b) {
  return (a + b) % md;
}

inline int sub(int a, int b) {
  return (a + md - b) % md;
}

inline int mul(int a, int b) {
  return (int) ((long long) a * b % md);
}

inline int power(int a, int p) {
  if (p == 0) return 1;
  if (p % 2 == 0) {
    int h = power(a, p / 2);
    return (int) ((long long) h * h % md);
  } else {
    return (int) ((long long) a * power(a, p - 1) % md);
  }
}

inline int divide(int a, int b) {
  return mul(a, power(b, md - 2));
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int h, w, a, b;
  cin >> h >> w >> a >> b;
  vector<int> f(h + w + 1, 1);
  for (int i = 1; i <= h + w; i++) {
    f[i] = mul(f[i - 1], i);
  }
  int ans = 0;
  for (int d = 0; d < w - b; d++) {
    int i1 = h - a - 1;
    int j1 = b + d;
    int c1 = divide(f[i1 + j1], mul(f[i1], f[j1]));
    int i2 = h - i1 - 2;
    int j2 = w - j1 - 1;
    int c2 = divide(f[i2 + j2], mul(f[i2], f[j2]));
    ans = add(ans, mul(c1, c2));
  }
  cout << ans << endl;
  return 0;
}

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

using namespace std;

struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}init;
typedef long long LL;
typedef vector<LL> V;
typedef vector<V> VV;
int main(){

    string s;
    cin>>s;
    vector<int> num;
    for(auto &it:s)num.push_back(it-'0');
    int n=num.size();
    VV dp(n+1,V(2,0));
    for(int i=0;i<n;i++){
        dp[i+1][0]+=dp[i][0]*2+dp[i][1];
        dp[i+1][1]+=dp[i][1]*10+(1ll<<i)*num[i];
    }
    cout<<dp[n][0]+dp[n][1]<<endl;
}


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

int main(){
    int N, M;
    cin >> N >> M;
    int a[N], b[N], c[M], d[M];
    for (int i = 0; i < N; i++)
    {
        cin >> a[i] >> b[i];
    }
    for (int i = 0; i < M; i++)
    {
        cin >> c[i] >> d[i];
    }

    vector<int> v(N);
    long long mins = 1000000000;
    for (int i = 0; i < N; i++){
        long long mins = 1000000000;
        long long dis = 1000000000;
        for (int j = 0; j < M; j++)
        {
            dis = abs(a[i] - c[j]) + abs(b[i] - d[j]);
            if(mins > dis){
                mins = dis;
                v[i] = j+1;
            }else{
                continue;
            }
        }
        cout << v[i] << endl;
    } 
}

Measured memory_bytes: 256
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
mod = 10 ** 9 + 7
W = [1] * (N + 1)
for i, t in enumerate(T):
	W2 = W[:]
	k = 0
	for j, s in enumerate(S):
		if t == s:
			k += W[j]
		W2[j + 1] = (W[j + 1] + k) % mod
	W = W2
print(W[-1])

Measured memory_bytes: 3316
S = input()

tmp1 = [0 for _ in range(len(S)+1)]
tmp2 = [0 for _ in range(len(S)+1)]

for i in range(len(S)):
  if S[i] == '>':
    tmp1[i] = 1
  else:
    tmp2[i+1] = 1

for i in range(1, len(S)+1):
  if tmp1[-i-1] != 0:
    tmp1[-i-1] = tmp1[-i] + tmp1[-i-1]

for i in range(2, len(S)+1):
  if tmp2[i] != 0:
    tmp2[i] = tmp2[i] + tmp2[i-1]

ans = 0
for i in range(len(S)+1):
  ans += max(tmp1[i], tmp2[i])

print(ans)



Measured memory_bytes: 27968
#define LOCAL
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rrep(i, n) for(int i=(n-1); i>=0; --i)
#define rep2(i, s, n) for(int i=s; i<(n); ++i)
#define ALL(v) (v).begin(), (v).end()
#define memr(dp, val) memset(dp, val, sizeof(dp))
using namespace std;
typedef long long ll;
static const int INTINF = (INT_MAX >> 1); // 10^9 + 10^7
static const ll LLINF = (LLONG_MAX >> 1);
static const int MAX = 100001;
static const ll MOD = 1000000007;
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; }
template<class T> inline bool int_ceil(T a, T b) { T res = a / b; if(a % b != 0) res++; return res; }
template<typename T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T> >;
string to_string(string s) { return '"' + s + '"'; }
string to_string(bool b) { return b ? "true" : "false"; }
template <size_t N> string to_string(bitset<N> bs) {
  string res;
  for (size_t i = 0; i < N; ++i) res += '0' + bs[i];
  return res;
}
string to_string(vector<bool> v) {
  string res = "{";
  for (bool e : v) res += to_string(e) + ", ";
  return res += "}";
}
template <class T, class U> string to_string(pair<T, U> p);
template <class C> string to_string(C c) {
  string res = "{";
  for (auto e : c) res += to_string(e) + ", ";
  return res += "}";
}
template <class T, class U> string to_string(pair<T, U> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
void debug() { cerr << '\n'; }
template <class Head, class... Tail> void debug(Head head, Tail... tail) {
  cerr << '\t' << to_string(head), debug(tail...);
}
#ifdef LOCAL
#define print(...) cerr << "[" << #__VA_ARGS__ << "]:", debug(__VA_ARGS__)
#else
#define print(...)
#endif

int main(int argc, const char * argv[]) {
	std::cout << std::fixed << std::setprecision(15);

	int n; cin >> n;
	vector<ll> v(n);
	rep(i, n) cin >> v[i];
	v.push_back(-1);

	ll l = v[0];
	ll ans = 1000;
	rep2(i, 1, n+1){
		// print(i, ans);
		if(v[i-1] <= v[i]){

		}
		else{
			if(l != v[i-1]){
				ll tmp = ans / l * v[i - 1];
				ans = ans % l + tmp;
			}
			l = v[i];
		}
	}

	cout << ans << endl;



	return 0;
}


Measured memory_bytes: 3628
from math import gcd
from functools import reduce

MOD = 10 ** 9 + 7

def calc_lcm(x, y):
    return x * y // gcd(x, y)

def calc_lcm_list(numbers):
    return reduce(calc_lcm, numbers, 1)
  
  
N, *A = map(int, open(0).read().split())
lcm = calc_lcm_list(A)
print(sum(lcm // v for v in A) % MOD)


Measured memory_bytes: 76220
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include <sstream>
#include <stdio.h>
#include<math.h>
using namespace std;

int main(){

    int N;
    cin >> N;
    string S[N];
    int P[N],jyun[N];
    string tmp;

    for(int i=0;i<N;i++){
        cin >> S[i] >> P[i];
        jyun[i] = i+1;
    }

    int k=0;

    for(int i=0;i<N-1;i++){
        for(int j=N-1;j>i;j--){
            if(S[j-1]>S[j]){
                swap(S[j-1],S[j]);
                swap(P[j-1],P[j]);
                swap(jyun[j-1],jyun[j]);
            }
        }
    }



    for(int i=N;i>1;i--){
        for(int j=0;j<i-1;j++){
            if(S[j]==S[j+1] && P[j]<P[j+1]){
                swap(S[j],S[j+1]);
                swap(P[j],P[j+1]);
                swap(jyun[j],jyun[j+1]);
            }
        }
    }

    for(int j=0;j<N;j++){
        cout << jyun[j] << endl;
    }


    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define loop(i, x, n) for (int i = (x); i < (n); i++)
#define all(v) (v).begin(), (v).end()
#define int long long
#define INF 1e9
using namespace std;
template<typename T> void cmin(T &a, T b) { a = min(a, b); }
template<typename T> void cmax(T &a, T b) { a = max(a, b); }

int dp[20005][256];

signed main() {
  int n, m;
  while (cin >> n >> m) {
    if (n == 0 && m == 0) break;
    rep(i, 20005) rep(j, 256) dp[i][j] = INF;
    vector<int> C(m), x(n);
    rep(i, m) cin >> C[i];
    rep(i, n) cin >> x[i];
    dp[0][128] = 0;
    rep(i, n) {
      rep(j, 256) {
        if (dp[i][j] == INF) continue;
        rep(k, m) {
          int y = j + C[k];
          cmin(y, 255LL);
          cmax(y, 0LL);
          int t = abs(y - x[i]);
          dp[i + 1][y] = min(dp[i + 1][y], dp[i][j] + t * t);
        }
      }
    }
    int ans = INF;
    rep(i, 256) cmin(ans, dp[n][i]);
    cout << ans << endl;
  }

  return 0;
}



Measured memory_bytes: 43260
N = int(input())
Alist = [int(input()) for i in range(N)]
Alist.sort()
Alist.append('END')
counter = 1
ans = 0

for i in range(1, len(Alist)):
    if Alist[i - 1] == Alist[i]:
        counter += 1
    else:
        if counter % 2 == 1:
            ans += 1
        counter = 1

print(ans)


Measured memory_bytes: 7388
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int odds[] = {9, 90, 900, 9000, 90000};
    int start[] = {1, 10, 100, 1000, 10000};
    int n, d = 0, n2;
    cin >> n;
    n2 = n;
    while(n > 0){
        n /= 10;
        d++;
    }
    long long ans = 0;
    if(d % 2 == 0){
        d -= 2;
        while(d >= 0){
            ans += odds[d];
            d -= 2;
        }
    }
    else{
        ans += (n2 - start[d-1]) + 1;
        d -= 3;
        while(d >= 0){
            ans += odds[d];
            d -= 2;
        }
    }
    cout << ans << "\n";
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

int main(){
	char s[5];
	scanf("%s",s);
	if(s[0]==s[1]&&s[1]==s[2]){
		printf("Yes\n");
	}else if(s[1]==s[2]&&s[2]==s[3]){
		printf("Yes\n");
	}else{
		printf("No\n");	
	}
	return 0;
}


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

long long n;
vector<pair<int, int>> ve;

void factorize(long long n) {
	for(long long i = 2; i * i <= n; i++) {
		if(n % i == 0) {
			int temp = 0;
			while(n % i == 0) {
				n /= i;
				temp++;
			}
			ve.emplace_back(i, temp);
		}
	}
	if(n > 1) {
		ve.emplace_back(n, 1);
	}
}

int f(int a) {
	int r = a, l = 0, ans = -1;
	while(r >= l) {
		int mid = (r + l) / 2;
		if(mid * (mid + 1) / 2 > a) {
			r = mid - 1;
		} else {
			ans = mid;
			l = mid + 1;
		}
	}
	return ans;
}

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

	cin >> n;
	factorize(n);

	int ans = 0;
	for(auto i : ve) {
		ans += f(i.second);
	}
	cout << ans << '\n';
	return 0;
}

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

int main(){
  int a;
  cin>>a;
  for(int i=0;i<a;i++){
    string s;
    cin>>s;
    if(s=="Y"){
      cout <<"Four";
      break;
    }else if(a-1==i){
      cout<<"Three";}
  }}
  

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int main(void){
  int N;
  scanf("%d",&N);
  int i;
  long long s=0;
  for(i=1;i<=N;i++){
    if((i%3!=0)&&(i%5!=0)){
      s=s+i;
    }
  }
  printf("%lld",s);
  return 0;
}

Measured memory_bytes: 2116
use std::io::{stdin, Read};

macro_rules! parse {
    ($it: ident) => {
        $it.next().unwrap().parse().unwrap()
    };
    ($it: ident,2) => {
        (parse!($it), parse!($it))
    };
    ($it: ident,3) => {
        (parse!($it), parse!($it), parse!($it))
    };
    ($it: ident,4) => {
        (parse!($it), parse!($it), parse!($it), parse!($it))
    };
    ($it: ident, $n: expr) => {
        (&mut $it).take($n).map(|e| e.parse().unwrap()).collect();
    };
}

fn bellman_ford(g: &Vec<Vec<(usize, isize)>>, source: usize) -> Result<Vec<isize>, ()> {
    let n = g.len();
    let M = std::isize::MAX;
    let mut ret = vec![M; n];
    ret[source] = 0;
    for i in 0..(n - 1) {
        for (i, e) in g.iter().enumerate() {
            for &(j, c) in e.iter() {
                if ret[i] != M && ret[j] > ret[i] + c {
                    ret[j] = ret[i] + c
                }
            }
        }
    }
    let ans = ret[n - 1];
    for _ in 0..n {
        for (i, e) in g.iter().enumerate() {
            for &(j, c) in e.iter() {
                if ret[i] != M && ret[j] > ret[i] + c {
                    ret[j] = std::isize::MIN / 2;
                }
            }
        }
    }
    if ans == ret[n - 1] {
        Ok(ret)
    } else {
        Err(())
    }
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    let mut it = s.split_whitespace();
    let (n, m, p): (usize, usize, isize) = parse!(it, 3);
    let mut g: Vec<Vec<(usize, isize)>> = vec![vec![]; n];
    for _ in 0..m {
        let (i, j, c): (usize, usize, isize) = parse!(it, 3);
        g[i - 1].push((j - 1, p - c));
    }
    match bellman_ford(&g, 0) {
        Err(_) => println!("{}", -1),
        Ok(ret) => println!("{}", -std::cmp::min(ret[n - 1], 0)),
    }
}


Measured memory_bytes: 4476
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
ans = 10**9
for i in range(N-K+1):
    l, r = A[i], A[i+K-1]
    if l*r >= 0:
        ans = min(ans, max(abs(l), abs(r)))
    else:
        ans = min(ans, r-l+min(abs(l), abs(r)))
print(ans)


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

using namespace std;

typedef long long ll;


int main(int, char**)
{
	ll a, b;
	cin >> a >> b;
	if (b % a == 0)
		cout << (a + b) << endl;
	else
		cout << (b - a) << endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[1001];
int main()
{
ll m,n;
cin>>n>>m;
double sum=0;
for(int i=0;i<n;i++)
{
    cin>>a[i];
    sum+=a[i];
}
sum/=4.0*m;
int ans=0;
for(int i=0;i<n;i++)
{
    if(a[i]>=sum)
        ans++;
}
if(ans>=m)
    cout<<"Yes";
else
    cout<<"No";
}


Measured memory_bytes: 256
// +build ignore
package main

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

func solve(sc *scanner, wr *bufio.Writer) int {
	A := sc.i()
	c := sc.s()

	c = strings.Replace(c, ".", "", 1)

	B, _ := strconv.Atoi(c)

	fmt.Println(A * B / 100)

	return 0
}

func main() {
	sc := newScanner(os.Stdin)
	wr := bufio.NewWriter(os.Stdout)
	ret := solve(sc, wr)
	wr.Flush()
	os.Exit(ret)
}

// I/O
type scanner struct {
	sc *bufio.Scanner
}

func newScanner(input io.Reader) *scanner {
	sc := bufio.NewScanner(input)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &scanner{sc}
}

func (s *scanner) s() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *scanner) i() int {
	i, e := strconv.Atoi(s.s())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *scanner) f() float64 {
	f, e := strconv.ParseFloat(s.s(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *scanner) bs() []byte {
	return []byte(s.s())
}

func (s *scanner) is(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.i()
	}
	return res
}

func (s *scanner) fs(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.f()
	}
	return res
}


Measured memory_bytes: 1760
/** Author: Nicklaus **/
 #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long int lli;
typedef long double ld;
#define PI 3.14159265358979324

int main(){
	int a, b, c;
	cin>>a>>b>>c;
	cout<<(a*b)/2<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

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

using namespace std;
#define int long long
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repr(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define EPS (1e-10)


const long long MOD = 1000000007;
//const long long MOD = 998244353;
const long long INF = 1LL << 60;


long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	unsigned r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a * g / b;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}




const long double PI = 3.14159265359;
const int MAX_N = 100010;



signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n; cin >> n;
	vector<VE>f(n, VE(10)), p(n, VE(11));
	rep(i, n)rep(j, 10)cin >> f[i][j];
	rep(i, n)rep(j, 11)cin >> p[i][j];
	int ans = -INF;
	rep(bit, 1 << 10) {
		if (bit == 0)continue;
		int now = 0;
		rep(i, n) {
			int tmp = 0;
			rep(j, 10) {
				if (bit & (1 << j) && f[i][j])tmp++;
			}
			now += p[i][tmp];
		}
		chmax(ans, now);
	}
	cout << ans << endl;
	return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;

class UnionFind{
public:
    UnionFind(size_t n){
        m_parent.resize(n);
        iota(m_parent.begin(), m_parent.end(), 0);

        m_rank.resize(n);
        fill(m_rank.begin(), m_rank.end(), 0);

        m_size.resize(n);
        fill(m_size.begin(), m_size.end(), 1);
    }

    int Find(int x){
        if(m_parent[x] == x){
            return x;
        }else{
            m_parent[x] = Find(m_parent[x]);
            return m_parent[x];
        }
    }

    void Union(int x, int y){
        auto xroot = Find(x);
        auto yroot = Find(y);
        if(m_rank[xroot] > m_rank[yroot]){
            m_parent[yroot] = xroot;
            m_size[xroot] += m_size[yroot];
            m_size[yroot] = 0;
        }else if(m_rank[xroot] < m_rank[yroot]){
            m_parent[xroot] = yroot;
            m_size[yroot] += m_size[xroot];
            m_size[xroot] = 0;
        }else if(xroot != yroot){
            m_parent[yroot] = xroot;
            m_size[xroot] += m_size[yroot];
            m_size[yroot] = 0;
            m_rank[xroot] = m_rank[xroot] + 1;
        }
    }

    int GetSize(){
        for(size_t i=0;i<m_parent.size();i++){
            m_parent[i] = Find(m_parent[i]);
        }
        std::set<int> s(m_parent.begin(), m_parent.end());
        return s.size();
    }

    int GetSize(int x){
        auto xroot = Find(x);
        return m_size[xroot];
    }

    std::vector<int> m_parent;
    std::vector<int> m_rank;
    std::vector<int> m_size;
};

int main()
{
    int N, M;
    cin >> N >> M;
    int Li, Ri, Di;
    vector<vector<array<int, 2>>> graph(N);
    UnionFind uf(N);
    for(int i=0;i<M;i++){
        cin >> Li >> Ri >> Di;
        Li--; Ri--;
        graph[Li].push_back(array<int, 2>{Ri, Di});
        graph[Ri].push_back(array<int, 2>{Li, -Di});
        uf.Union(Ri, Li);
    }
    map<int, map<int, int>> g;
    bool inconsistent = false;
    for(int i=0;i<N;i++){
        auto root = uf.Find(i);
        if(g.count(root) == 0) g[root] = map<int, int>();
        if(g[root].count(i) == 0) g[root][i] = 0;
        queue<int> q;
        q.push(i);
        while(!q.empty()){
            auto k = q.front(); q.pop();
            for(auto m : graph[k]){
                auto j = m[0];
                auto d = m[1];
                if(g[root].count(j) == 0){
                    g[root][j] = (g[root][k] + d) % 1000000001;
                    q.push(j);
                }else{
                    if(g[root][j] != (g[root][k] + d) % 1000000001){
                        inconsistent = true;
                    }
                }
            }
        }
    }
    if(inconsistent) cout << "No" << endl;
    else             cout << "Yes" << endl;


    return 0;
}


Measured memory_bytes: 18560
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
pair = {}
rank = {}
def root(x):
    if x == pair[x]:
        return x
    else:
        pair[x] = root(pair[x])
    return pair[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx > ry:
        pair[rx] = pair[ry]
    else:
        pair[ry] = pair[rx]

for i in range(1, N+1):
    pair.setdefault(i, i)

for i in range(1, N+1):
    rank.setdefault(i, 0)

for i in range(M):
    x, y, z = map(int, input().split())
    if x < y:
        unite(x, y)
    else:
        unite(y, x)

cnt = set()
for k, y in pair.items():
    y = root(y)
    cnt.add(y)
print(len(cnt))


Measured memory_bytes: 81764
#include<bits/stdc++.h>
#define t first
#define v second
#define wrap make_pair
using namespace std;
typedef double db;
typedef pair<db,int> pint;
typedef const pint& cpr;
typedef long long ll;
const int siz=5e5+1;

int n,L;
ll Vsum;
db Esum;
pint a;
deque<pint> q;

inline
db mix(cpr a,cpr b){return (a.t*a.v+b.t*b.v)/(a.v+b.v);}

int main()
{
#ifdef DEBUG
	freopen("AT2402.in","r",stdin);
#endif
	scanf("%d%d",&n,&L);
	for(int i=1,y;i<=n;i++){
		db x;
		scanf("%lf%d",&x,&y);
		a=wrap(x,y);
		while(a.v+Vsum>L){
			pint now=q.front();
			q.pop_front();
			int pour=min(a.v+Vsum-L,(ll)now.v);
			Vsum-=pour;
			Esum-=pour*now.t;
			now=wrap(now.t,now.v-pour);
			if(now.v!=0)
				q.push_front(now);
		}
		q.push_back(a);
		while(q.size()>1&&q[q.size()-2].t>q.back().t){
			pint b=q.back();
			q.pop_back();
			pint c=q.back();
			q.pop_back();
			q.push_back(wrap(mix(b,c),b.v+c.v));
		}
		Esum+=a.t*a.v;
		Vsum+=a.v;
		printf("%.7f\n",Esum/L);
	}
	return 0;
}

Measured memory_bytes: 17188
#include<bits/stdc++.h>
using namespace std;
const int maxn =2e5+10;
char s[maxn][5];

int a[maxn],b[maxn],c[maxn];
#define LL long long
int n;
char ans[maxn];
int f;
void dfs(int cnt,int a,int b,int c,char pos) {
    if(a<0 || b<0 || c<0) {
        return;
    }
    ans[cnt-1]=pos;
    if(cnt==n+1) {
        f=1;
        printf("Yes\n");
        for(int i=1; i<=n; i++) {
            printf("%c\n",ans[i]);
        }
        return;
    }
    if(strcmp(s[cnt],"AB") == 0) {
        if(a==b) {
            dfs(cnt+1,a-1,b+1,c,'B');
            if(f){
                return ;
            }
            dfs(cnt+1,a+1,b-1,c,'A');
        } else {
            a>b?dfs(cnt+1,a-1,b+1,c,'B'):dfs(cnt+1,a+1,b-1,c,'A');
        }

    } else if(strcmp(s[cnt],"AC") == 0) {
        if(a==c) {
            dfs(cnt+1,a-1,b,c+1,'C');
            if(f){
                return ;
            }
            dfs(cnt+1,a+1,b,c-1,'A');
        } else {
            a>c?dfs(cnt+1,a-1,b,c+1,'C'):dfs(cnt+1,a+1,b,c-1,'A');
        }

    } else if(strcmp(s[cnt],"BC") == 0) {
        if(b==c) {
            dfs(cnt+1,a,b+1,c-1,'B');
            if(f){
                return ;
            }
            dfs(cnt+1,a,b-1,c+1,'C');
        } else {
            b<c?dfs(cnt+1,a,b+1,c-1,'B'):dfs(cnt+1,a,b-1,c+1,'C');
        }
    }
    return;
}
int main() {
    int a,b,c;
    while(~scanf("%d",&n)) {
        f=0;
        scanf("%d%d%d",&a,&b,&c);
        for(int i=1; i<=n; i++) {
            scanf("%s",s[i]);
        }
       // printf("%s\n",s[1]);
        dfs(1,a,b,c,' ');
        if(!f){
            printf("No\n");
        }
    }
    return 0;
}




Measured memory_bytes: 6100
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <numeric>
#include <functional>
#include <sstream>
#include <iostream>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cfloat>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cctype>
#include <cstdio>
#include <cassert>
using namespace std;

#define EPS 1e-12
#define ull unsigned long long
#define ll long long
#define VI vector<ll>
#define PII pair<ll, ll> 
#define VVI vector<vector<ll> >
#define VVVI vector<vector<vector<ll>>>
#define VVVVI vector<vector<vector<vector<ll>>>>
#define REP(i,n) for(ll i=0,_n=(n);(i)<(ll)_n;++i)
#define REPR(i,n) for(ll i=(ll)(n)-1;0<=(i);--i)
#define RANGE(i,a,b) for(ll i=(ll)a,_b=(ll)(b);(i)<_b;++i)
#define RANGER(i,a,b) for(ll i=(ll)(b)-1,_a=(ll)(a);(_a)<=i;--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define ALLR(c) (c).rbegin(), (c).rend()
#define PB push_back
#define MP(a, b) make_pair(a, b)
#define POPCOUNT __builtin_popcount
#define POPCOUNTLL __builtin_popcountll
#define CLEAR(table, v) memset(table, v, sizeof(table));
#define UNIFORM_DOUBLE(a, b) (((b-a)*(double)rand()/RAND_MAX)+a) // [a, b) 
#define UNIFORM_LL(a, b) (ll)UNIFORM_DOUBLE(a, b) // [a, b) 
#define IN(v, lo, hi) ((lo)<=(v) && (v)<(hi))
#define DD(v) cout<<#v<<": "<<v<<endl
#define FI first
#define SE second
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const map<T0, T1>& v) { for( typename map<T0, T1>::const_iterator p = v.begin(); p!=v.end(); p++ ){os << p->first << ": " << p->second << " ";} return os; }
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const pair<T0, T1>& v) { os << v.first << ": " << v.second << " "; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << " "; } return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const set<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const deque<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<vector<T> >& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << endl; } return os; }
template<typename T>void maxUpdate(T& a, T b) {a = max(a, b);}
template<typename T>void minUpdate(T& a, T b) {a = min(a, b);}
string YN(bool v) { return v ? "Yes":"No"; }
void uniq(VI& es) { sort(ALL(es)); es.erase(unique(ALL(es)), es.end()); }

#define INF (1LL<<60)

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s,t;
	while(cin>>s>>t) {
		ll N=s.size();
		ll ans=0;
		REP(i, N) {
			if(s==t) ans=1;
			s=s.substr(1, N)+string(1, s[0]);
		}
		cout<<YN(ans)<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String args[]) {
		FastScanner scanner = new FastScanner();
		int n=scanner.nextInt();
		int a=scanner.nextInt();
		int b=scanner.nextInt();
		int c=scanner.nextInt();
		int[] l=new int[n];
		for(int i=0;i<n;i++){
			l[i]=scanner.nextInt();
		}
		int min=Integer.MAX_VALUE;
		for(int i=0;i<Math.pow(4, n);i++){
			int tmp1=0;
			int tmp2=0;
			int tmp3=0;
			int mp=0;
			for(int j=0;j<n;j++){
				if((3&(i>>(j*2)))==3){
					if(tmp3!=0){
						mp+=10;
					}
					tmp3+=l[j];
				}else if((2&(i>>(j*2)))==2){
					if(tmp2!=0){
						mp+=10;
					}
					tmp2+=l[j];
				}else if((1&(i>>(j*2)))==1){
					if(tmp1!=0){
						mp+=10;
					}
					tmp1+=l[j];
				}
			}
			if(tmp1==0||tmp2==0||tmp3==0){
				continue;
			}
			mp+=Math.abs(a-tmp1)+Math.abs(b-tmp2)+Math.abs(c-tmp3);
			min=Math.min(min, mp);
		}
		System.out.println(min);
	}
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}


Measured memory_bytes: 21844
import java.util.*;

public class Main {
    public static void main(String... args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int A = sc.nextInt();
        int B = sc.nextInt();
        sc.close();

        int answer = 0;

        char[] char_ary = null;
        int sum = 0;
        boolean add_flg = true;
        for (int i = A; i <= N; i++) {
            char_ary = Integer.toString(i).toCharArray();

            sum = 0;
            add_flg = true;
            for (char elm : char_ary) {
                sum += Character.getNumericValue(elm);
                if (sum > B) {
                    add_flg = false;
                    break;
                }
            }
            if (add_flg && sum >= A) {
                answer += i;
            }
        }

        System.out.println(answer);
    }
}

Measured memory_bytes: 21972
#include <stdio.h>
int main()
{
	int a,b;
	int c;
	scanf("%d%d",&a,&b);
	c=a-2*b;
	if(c<=0)
	{
	printf("0");
	}
	else
	{
	printf("%d",c);
	}
	return 0;
}

Measured memory_bytes: 128
S = input()
count = 0
first = S[:len(S)//2]
second = S[(len(S)+1)//2:]
if first == reversed(second):
    print(count)
else:
    for i in range(len(first)):
        if first[i] != second[len(second)-i-1]:
            count += 1
    print(count)


Measured memory_bytes: 3064
#include<cstdio>
const int N=(int)1e2+5;
int b[N];
int main(int argc,char**argv){
  register int n;scanf("%d",&n);
  for(register int i=1;i<n;++i)
    scanf("%d",b+i);
 	register int ans=0;
  for(register int i=2;i<n;++i)
    ans+=b[i]<b[i-1]?b[i]:b[i-1];
  ans+=b[1];ans+=b[n-1];
  printf("%d\n",ans);
}

Measured memory_bytes: 256
//#pragma GCC optimize(2)
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<climits>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int read(){
	bool f=0;int x=0;char c=getchar();
	while(c<'0'||'9'<c){if(c=='-')f=1;c=getchar();}
	while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return !f?x:-x;
}
#define MAXN 100000
#define INF 0x3f3f3f3f
int main(){
	int a=read();
	printf("%.6lf\n",((a+1)/2)*1.0/a);
	return 0;
}

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

int main() {
    string s;
    cin >> s;
    map<char, int> mp;
    for (int i = 0; i < s.size(); i++)
    {
        mp[s[i]]++;
    }
    
    vector<int> a;
    for (auto x : mp) {
        a.push_back(x.second);
    }
    
    for (int i = 0; i < s.size(); i++)
    {
        if (a[0] == 0 || a[1] == 0 || a[2] == 0) {
            if (a[0] < 2 && a[1] < 2 && a[2] < 2) {
                cout << "YES" << endl;
                return 0;
            } else {
                cout << "NO" << endl;
                return 0;
            }
        }
        a[0]--;
        a[1]--;
        a[2]--;
    }
    return 0;
}

Measured memory_bytes: 3724
import sys
sys.setrecursionlimit(10000)
memo = [1,1]
def fact(a):
    if len(memo) > a:
        return memo[a]
    b = a*fact(a-1)
    memo.append(b)
    return b
n,k = map(int, input().split())
if n > k:
    ans = 0
else:
    ans = fact(k)//fact(k-n)
print(ans%1000000007)


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

int main () {
  vector<vector<char>> c(3, vector<char>(3));
  
 for (int i = 0; i < 3; i++) {
   for (int j = 0; j < 3; j++){
     cin >> c.at(i).at(j);
   }
 }
  cout << c.at(0).at(0) << c.at(1).at(1) << c.at(2).at(2) << endl;
}

Measured memory_bytes: 256
// Online C++ compiler to run C++ online.
// Write C++ code in this online editor and run it.

#include<bits/stdc++.h>
using namespace std;
int n,k;
int arr[100009];
int dp[100009];
int fun(int ind)
{
    int res=INT_MAX;
    if(ind==n)
        return 0;
    if(dp[ind]!=-1)
        return dp[ind];
    for(int i=ind+1;i<=min(n,ind+k);i++)
        res=min(res,abs(arr[i]-arr[ind])+fun(i));
    return dp[ind]=res;
}
int main() {
    
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>arr[i];
    memset(dp,-1,sizeof(dp));
    cout<<fun(1);
    return 0;
}

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

using namespace std;

const int N = 2e5 + 1;
map<pair<int, int>, long long> dp;
int vt[N];

void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> vt[i];
    }
    dp[{-1, 0}] = dp[{0, 0}] = 0;
    long long mxdp = -1e18;
    for (int i = 1; i <= n; i++) {
        int mink = max(1, (n / 2) - (n - i + 1) / 2);
        int maxk = (i + 1) / 2;
        for (int j = mink; j <= maxk; j++) {
            for (int ni = i - 4; ni <= i - 2; ni++) {
                if (dp.count({ni, j - 1}) == 0)
                    continue;
                if (dp.count({i, j}) == 0)
                    dp[{i, j}] = dp[{ni, j - 1}] + vt[i];
                else
                    dp[{i, j}] = max(dp[{i, j}], dp[{ni, j - 1}] + vt[i]);
            }
            if (j == n / 2)
                mxdp = max(mxdp, dp[{i, j}]);
        }
    }
    cout << mxdp;
}

int main() {
    ios::sync_with_stdio(NULL), cin.tie(0), cout.tie(0);
    cout.setf(ios::fixed), cout.precision(20);
    solve();
}


Measured memory_bytes: 29440
#include <bits/stdc++.h>
#define INF 100000000000
#define ll long long
#define pll pair<ll, ll>
using namespace std;

int main()
{
  ll mod = 1000000007;
  ll N, K;
  cin >> N >> K;
  ll ans = 0;
  ll left = 0, right = 0;
  for (ll i = 0; i < K - 1; ++i) {
    left += i;
    right += N - i;
  }
  for (ll i = K; i <= N + 1; ++i) {
    left += i - 1;
    right += N + 1 - i;
    ans = (ans + right - left + 1) % mod;
    // cout << left << ' ' << right << endl;
  }
  // cout << ans << endl;
  if (ans < 0) {
    ans += mod;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
const int limit = 100010;
using edge = struct {int to; long long int cost;};
vector<edge> tree[limit];
long long int depth[limit];
 
void bfs(int v, int p, long long int d) {
    // v = 次の場所
	// p = 前の場所
	queue<edge> Q;
	Q.push({v,0});
    //printf("%d, %d, %lld\n", p+1, v+1, d);
	//スタート地点の枝分かれ箇所数だけ繰り返す。
	while(Q.size() != 0){
		//printf("size: %d",Q.size());
		//puts("");
		edge p = Q.front(); Q.pop();
		depth[p.to] = p.cost;
		//cout << "depth:" << p.to+1 << "=" << p.cost <<endl;
		for( int i = 0; i < tree[p.to].size(); i++){
			if(depth[tree[p.to][i].to] == 1000000000000000 ) {
				Q.push({tree[p.to][i].to,tree[p.to][i].cost + depth[p.to]});
				//printf("push: {%d, %d}",tree[p.to][i].to+1, tree[p.to][i].cost + depth[p.to]);
				//puts("");
			}
		}
	}
}
 
int main(void) {
	int n;
	cin >> n;
 
	for ( int i = 0; i < 100010; i++){
		depth[i] = 1000000000000000;
	}
	for (int i = 0; i < n - 1; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		a--, b--;
		tree[a].push_back({b, c});
        tree[b].push_back({a, c});
    }
    //puts("");
    for( int i = 0; i < n; ++i){
        for( int j = 0; j < tree[i].size(); j++){
            //cout << i+1 << "," << tree[i][j].to+1 << "," << tree[i][j].cost << endl;
        }
    }
    //puts("");
	int q, k;
	cin >> q >> k;
	k--;
 
	bfs(k, -2, 0);
	for (int i = 0; i < q; ++i) {
		int x, y;
		cin >> x >> y;
		x--, y--;
        cout << depth[x] + depth[y] << endl;
        //printf("depth[%d] = %lld\ndepth[%d] = %lld\n", x, depth[x], y, depth[y]);
	}
 
	return 0;
}

Measured memory_bytes: 10736
#include<bits/stdc++.h>
using namespace std;
int main(){
    set<int> s;
    int n;
    int d;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>d;
        s.insert(d);
    }
    cout<<s.size()<<endl;
    
    return 0;
}


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

#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define rep11(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end())
#define vdelete(v) (v).erase(unique(all(v)), (v).end())
#define pb(n) push_back(n)
#define mp make_pair
#define MOD 1000000007
#define INF LONG_LONG_MAX
#define P pair<int,int>

int n,q,s,t,x,d,z;
vector<int> vv;
vector<pair<pair<int,int>,int>> v;
map<int,int> m;
priority_queue<P,vector<P>, greater<P>> pq;

signed main() {
    cin >> n >> q;
    rep(i,n) {
        cin >> s >> t >> x;
        v.pb(mp(mp(s-x,t-x-1),x));
        vv.pb(s-x-1);
        vv.pb(t-x-1);
    }
    sort(all(v));
    sort(all(vv));
    for(auto i : vv) {
        while(z < v.size() && v[z].fi.fi <= i) {
            pq.push(mp(v[z].se, v[z].fi.se));
            z++;
        }
        while(!pq.empty()) {
            if (pq.top().se < i) pq.pop();
            else break;
        }
        if (pq.empty()) m[i] = -1;
        else m[i] = pq.top().fi;
    }
    m[INF] = -1;
    rep(i,q) {
        cin >> d;
        cout << m.lower_bound(d)->se << endl;
    }
}



Measured memory_bytes: 38172
import bisect

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

l.sort()
res = 0
for i in range(1, n - 1):
    b = l[i]
    for a in l[:i]:
        res += max(bisect.bisect_left(l, a + b) - (i + 1), 0)

print(res)


Measured memory_bytes: 3188
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = (ll)1e9;
const ll mod = (ll)1e9 + 7;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#define print(s) cout << s;
#define println(s) cout << s << endl;
#define printd(s, f) cout << fixed << setprecision(f) << s << endl;


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

	double res = 0;

	for (int i = 0; i < n; i++)
	{
		double x;
		string u;
		cin >> x >> u;

		if (u == "JPY")
		{
			res += x;
		}
		else
		{
			res += x * 380000.0;
		}
	}

	printd(res, 10);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mp(a, b) make_pair(a, b)
#define ls (rt << 1)
#define rs (rt << 1 | 1)
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 10;
int h, w;
int a[maxn], b[maxn];
int cov[maxn << 2], Min[maxn << 2], L[maxn << 2];
void build(int rt, int l, int r)
{
	L[rt] = l;
	if(l == r)
	{
		cov[rt] = l;
		Min[rt] = 0;
		return;
	}
	int mid = l + r >> 1;
	build(ls, l, mid); build(rs, mid + 1, r);
}
void pushup(int rt) { Min[rt] = min(Min[ls], Min[rs]);}
void lazy(int rt, int val)
{
	cov[rt] = val;
	Min[rt] = L[rt] - val;
}
void pushdown(int rt)
{
	if(cov[rt])
	{
		lazy(ls, cov[rt]);
		lazy(rs, cov[rt]);
		cov[rt] = 0;
	}
}
void update(int rt, int l, int r, int a, int b, int val)
{
	if(a <= l && r <= b)
	{
		lazy(rt, val);
		return;
	}
	pushdown(rt);
	int mid = l + r >> 1;
	if(a <= mid) update(ls, l, mid, a, b, val);
	if(b > mid) update(rs, mid + 1, r, a, b, val);
	pushup(rt);
}
int query(int rt, int l, int r, int x)
{
	if(l == r) return cov[rt];
	pushdown(rt);
	int mid = l + r >> 1;
	if(x <= mid) return query(ls, l, mid, x);
	else return query(rs, mid + 1, r, x);
}
int getmin(int rt, int l, int r, int a, int b)
{
	if(a <= l && r <= b) return Min[rt];
	pushdown(rt);
	int mid = l + r >> 1;
	if(b <= mid) return getmin(ls, l, mid, a, b);
	if(a > mid) return getmin(rs, mid + 1, r, a, b);
	return min(getmin(ls, l, mid, a, b), getmin(rs, mid + 1, r, a, b));
}
int main()
{
	scanf("%d%d", &h, &w);
	for(int i = 1; i <= h; ++i) scanf("%d%d", &a[i], &b[i]);
	build(1, 0, w);
	int cur = 1;
	for(int i = 1; i <= h; ++i)
	{
		if(a[i] <= cur && cur <= b[i]) cur = b[i] + 1;
		if(cur > w) puts("-1");
		else
		{
			int val = query(1, 0, w, a[i] - 1);
			update(1, 0, w, a[i], b[i], val);
			printf("%d\n", i + getmin(1, 0, w, cur, w));
		}
	}
	return 0;
}

Measured memory_bytes: 11428
#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)
 
using namespace std;
 
struct Point { double x,y; };
typedef pair<double,double> Segment;
const int MAX_N = 2010,IINF = INT_MAX;
int N;
double sx[MAX_N],sy[MAX_N],ex[MAX_N],ey[MAX_N],L,R;
 
inline bool LT(double a,double b) { return !equals(a,b) && a < b; }
inline bool LTE(double a,double b) { return equals(a,b) || a < b; }
inline bool inside(double a,double b,double c) { return LTE(a,c) && LTE(c,b); }
inline double getDist(double x,double y) { return sqrt(x*x+y*y); }
 
int main(){
  scanf("%d",&N);
  vector<Segment> segs(N);
  rep(i,N) {
    scanf("%lf %lf %lf %lf",sx+i,sy+i,ex+i,ey+i);
    vector<Point> vec(4);
    vec[0] = (Point){sx[i],sy[i]}, vec[1] = (Point){sx[i],ey[i]};
    vec[2] = (Point){ex[i],sy[i]}, vec[3] = (Point){ex[i],ey[i]};
    segs[i] = Segment(IINF,-IINF);
    rep(j,4){
      double arg = atan2(vec[j].y,vec[j].x) * 180 / M_PI;
      if( LT(arg,0.0) ) arg += 360;
      if( sx[i] > 0 && sy[i] < 0 && ey[i] >= 0 && LTE(0.0,arg) && LTE(arg,91.0) ) arg += 360;
      segs[i].first  = min(segs[i].first ,arg);
      segs[i].second = max(segs[i].second,arg);
    }
  }
  sort(segs.begin(),segs.end());
  rep(i,N) segs.push_back(Segment(segs[i].first+360,segs[i].second+360));
  int ans = N;
  rep(i,N){
    int cost = 0;
    REP(j,i,i+N){
      ++cost;
      L = segs[j].first, R = segs[j].second;
      while( j+1 < i+N && ( inside(L,R,segs[j+1].first) || inside(L,R,segs[j+1].second) ) ){
        L = max(L,segs[++j].first);
        R = min(R,segs[j].second);
      }
    }
    ans = min(ans,cost);
  }
  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 1468