akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
long long inf = 1000000000000;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int main() {
	int n;
	cin >> n;
	int i;
	int a[220000];
	for (i = 0; i < n; i++) {
		cin >> a[i];
	}
	int mini = n;
	int ans = 0;
	for (i = 0; i < n; i++) {
		if (a[i] <= mini) ans++;
		mini = min(mini, a[i]);
	}
	cout << ans;
	return(0);
}

Measured memory_bytes: 1024
n, m = map(int, input().split())
A = [0] * m
for i in range(n):
    k, *a = map(int, input().split())
    for j in a:
        A[j - 1] += 1 
        
cnt = 0
for i in range(m):
    if A[i] == n:
        cnt += 1
        
print(cnt)

Measured memory_bytes: 3060
n,k = map(int,input().split())
a = list(map(int,input().split()))

l = 0
r = 10**10

while r > l + 1:
    m = (r+l)//2
    count = 0
    for i in a:
        if i <= m:
            continue
        count += (i)//m
        
    if count > k:
        l = m
    else:
        r = m
    
print(r)


Measured memory_bytes: 104200
from collections import defaultdict

d = defaultdict(int)
n = int(input())

for i in range(n):
    t, x, y = input().split()
    d[int(t)] = (int(x), int(y))

s = sorted(d)

curent = 0

for ss in s:
    k1, k2 = d[ss]
    k3 = k1 + k2
    if k3 - curent > ss:
        print('No')
        exit(0)
    if ((k3 & 1) == 1 and (ss & 1) == 1) or ((k3 & 1) == 0 and (ss & 1) == 0):
        curent = k3
    else:
        print('No')
        exit(0)
print('Yes')

Measured memory_bytes: 23780
# https://atcoder.jp/contests/abc113/tasks/abc113_b
# Ruby 2nd Try
HOSEI = 0.006
n = gets.chomp.to_i
abss = Array.new(n,0.0)
t,a = gets.chomp.split(' ').map(&:to_f)
hi = gets.chomp.split(' ').map(&:to_f)
for j in 0..(n-1) do
    abss[j]=((t-hi[j]*HOSEI)-a).abs
end
answer = 0
avemin = abss[0]
for j in 1..(n-1) do
    if abss[j] < avemin
        answer = j
        avemin = abss[j]
    end
end
answer = answer+1
puts(answer)

Measured memory_bytes: 1916
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

#define ll long long
#define ld long double
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define gcd __gcd
#define lcm(a, b) ((a) * (b) / gcd((a), b))
#define all(x) x.begin(), x.end()
#define rep(i, x, n) for (ll i = x; i < n; i++)
#define fastio() ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0)
#define endl '\n'

typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef pair<int, int> ii;
typedef vector<pair<int, int> > vii;

template <class T> inline T RD(T &a) {T x; cin >> x; return a = x;}

const int maxn = 1e5 + 69, mod = 1e9 + 7;

signed main()
{
//	freopen("TEXT.inp", "r", stdin); freopen("TEXT.out", "w", stdout);
	fastio();

	int a, b;
    cin >> a >> b;
    if (a >= 10 || b >= 10) cout << -1;
    else cout << a * b;
}


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

#define ld long double
#define ll long long
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define MP make_pair
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
ll INF = 1e18;
void chmin(ll &a,ll b){if(a>b)a=b;}
void chmax(ll &a,ll b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
void ans(bool x,ll y,ll z){if(x)cout<<y<<endl;else cout<<z<<endl;}
void anss(bool x,string y,string z){if(x)cout<<y<<endl;else cout<<z<<endl;}   
ll gcd(ll x,ll y){ll r;while((r=x%y)!=0){x=y;y=r;}return y;}

int main(){
  ll i,j,o;
  ll res=0,res1=0,res2=INF,buf=0,buf1=0,buf2=0,buf3=0,buf4=0,sum=0;
  ll l,r;
  bool judge = true;
  ll x;cin>>x;
  anss(x>=1200,"ARC","ABC");

  return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
  int hour,minute,sec;
  
  cin >> sec;

  minute = sec / 60;
  hour = sec / 3600;

  sec = sec % 60;
  minute = minute % 60;

  cout << hour << ":"<< minute <<":"<< sec << endl;

  return 0;
}

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

#define ll long long  

int main()
{
    ll int n, ans; 
    cin >> n; 
    ans = n - 1; 

    for (int i = 1; i < sqrt(n) + 1; ++i){
        if (n % i == 0)
        {
            ans = min(ans, i + n / i - 2); 
        }
    }
    cout << ans << endl; 
    return 0; 
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int c[3],ans;
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j + 1 < s.size(); ++j)
            ans += s[j] == 'A' && s[j+1] == 'B';
        if (s[0] == 'B' && s.back() == 'A')
            ++c[2];
        else if (s[0] == 'B')
            ++c[1];
        else if (s.back() == 'A')
            ++c[0];
    }
    if (c[1] || c[0])
        ans += c[2], c[2] = 0;
    if (c[2]) {
        ans += c[2]-1;
        c[2] = 1;
    }
    int t = min(c[1],c[0]);
    ans += t;
    cout << ans << endl;
}


Measured memory_bytes: 256
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

s = list(input())
n = len(s)
d = list('abcdefghijklmnopqrstuvwxyz')
se = set(s)
if n < 26:
    for i,x in enumerate(d):
        if not x in se:
            s.append(x)
            break
    print(''.join(s))
else:
    for i in range(25)[::-1]:
        if s[i] < s[i+1]:
            tmp = s[i+1:n]
            tmp.sort()
            for j in tmp:
                if j > s[i]:
                    s[i] = j
                    break
            # print(i)
            print(''.join(s[:i+1]))
            break
    else:
        print(-1)

Measured memory_bytes: 64108
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):
    return map(type,input().split())

#%%code
def resolve():
    H,W=pin()
    maze=[list(input()) for oo in range(H)]
    vacanth=[]
    vacantw=[]
    for h in range(H):
        if "#" not in maze[h]:vacanth.append(h)
    for w in range(W):
        flag=1
        for h2 in range(H):
            if maze[h2][w]=="#":
                flag=0
                break
        if flag==1:vacantw.append(w)

    for i in range(H):
        if i in vacanth:continue
        temp=""
        for j in range(W):
            if j in vacantw:continue
            temp+=maze[i][j]
        print(temp)
    
#%%submit! 
resolve()

Measured memory_bytes: 3188
A_ref, B_range, M_waribiki = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

price = []
mini = min(A) + min(B)

price.append(mini)

for i in range(M_waribiki):
    x, y, redu = map(int, input().split())
    x -= 1
    y -= 1
    
    summ = A[x] + B[y] - redu
    
    price.append(summ)

print(min(price))



Measured memory_bytes: 18736
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,k;
bool dp[100005];
int a;
vector < int > v;
int main(){
	cin>>n>>k;
	for(int i=0;n>i;i++)
	{
		cin>>a;
		v.push_back(a);
	}
	fill(dp,dp+k+1,0);
	for(int i=0;k>=i;i++)
	{
		for(auto it : v)
			if(i-it>=0 and dp[i-it]==0)
				dp[i]=1;
	}
	if(dp[k]==1)
		cout<<"First";
	else
		cout<<"Second";


	return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//freopen("test.txt","r",stdin);
	ll a,b;
	cin>>a>>b;
	if((a+b)%2==0)
		cout<<(a+b)/2<<"\n";
	else
		cout<<"IMPOSSIBLE"<<"\n";


}

Measured memory_bytes: 256
var  i,j,k:longint;
     s:ansistring;//给小蒟蒻讲一下ansistring是无限长度字符串且内存可伸缩
begin
  readln(s);
  for  i:=1  to  length(s)  do
    if  s[i]='9'  then
      begin
        writeln('Yes');
        exit;//找到直接退出
      end;
  writeln('No');
end.

Measured memory_bytes: 128
#include <bits/stdc++.h>
int com[100001];
using namespace std;
int main(){
	int n, m;
	cin >> n >> m;
	long long arr[n+1];
	for(int i=1; i<=n; ++i){
		cin >> arr[i];
	}
	int a, b;
	for(int i=1; i<=m; ++i){
		cin >> a >> b;
		if(arr[a]>arr[b]){
			com[b]=1;
		}
		else if(arr[b]>arr[a]){
			com[a]=1;
		}
		else{
			com[a]=1;
			com[b]=1;
		}
	}
	int count=0;
	for(int i=1; i<=n; ++i){
		if(com[i]==0){
			count++;
		}
	}
	cout << count;
}


Measured memory_bytes: 4804
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <ctime>
#include <map>
#include <set>
using namespace std;
#pragma comment(linker, "/stck:1024000000,1024000000")
#define lowbit(x) (x&(-x))
#define max(x,y) (x>=y?x:y)
#define min(x,y) (x<=y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.1415926535897932384626433832
#define ios() ios::sync_with_stdio(true)
#define INF 0x3f3f3f3f
#define mem(a) ((a,0,sizeof(a)))
typedef long long ll;
char s[200005],t[200005];
int vis[200005];
int main(){
    scanf("%s",s);
    scanf("%s",t);
    memset(vis,0,sizeof(vis));
    int ok=1;
    for(int i=0;s[i];i++){
        if(!vis[s[i]]) vis[s[i]]=t[i];
        else if(vis[s[i]]!=t[i]){
            ok=0;
            break;
        }
    }
    memset(vis,0,sizeof(vis));
    for(int i=0;t[i];i++){
        if(!vis[t[i]]) vis[t[i]]=s[i];
        else if(vis[t[i]]!=s[i]){
            ok=0;
            break;
        }
    }
    printf(ok?"Yes\n":"No\n");
    return 0;
}

Measured memory_bytes: 1408
a, b, c, d = gets.chomp.split(" ").map(&:to_i)
saisyou = c.lcm(d)

#a-1以下
a_ans = (a-1)/c + (a-1)/d - (a-1)/saisyou
aa = a - 1 - a_ans
# b以下
b_ans = (b/c) + (b/d) - (b/saisyou)
bb =  b - b_ans
puts bb - aa

Measured memory_bytes: 14220
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair

using Edge=pair<ll,ll>;
using Graph = vector<vector<Edge>>;

int main(){
	ll n; cin >> n;
	Graph G(n);
	for(ll i=0;i<n-1;i++){
		ll a,b;
		cin >> a >> b;
		a--,b--;
		G[a].push_back(mp(b,i));
		G[b].push_back(mp(a,i));
	}
	ll maxcolor=0;
	for(ll i=0;i<n;i++) maxcolor=max(maxcolor,(ll)G[i].size());

	vector<ll> res(n-1,-1);
	vector<ll> dist(n,-1);
	queue<pair<ll,ll>> que;
	que.push(mp(0,-1));
	dist[0]=0;
	while(!que.empty()){
		auto p=que.front();que.pop();
		ll v=p.fi,c=p.se;
		ll color=1;
		if(color==c) color++;
		for(auto e:G[v]){
			if(dist[e.fi]==-1){
				dist[e.fi]=dist[v]+1;
				que.push(mp(e.first,color));
				res[e.se]=color;
				color++;
				if(color==c) color++;
			}
		}
	}
	cout << maxcolor << endl;
	for(ll i=0;i<n-1;i++) cout << res[i] << endl;
}


Measured memory_bytes: 12420
#include <iostream>
#include<string>
#include<cmath>
#include<ciso646>
#include<cstring>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<utility>
#include<map>
#include<math.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
using ll = long long;
ll Max = 10 + 1e12;
int N = 5 + 1e5;

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

ll lcm(ll a, ll b)
{
	return a * b / gcd(a, b);
}


int main()
{
	ll a, b;
	ll c, d;
	cin >> a >> b >> c >> d;
	ll ans = b - a + 1;
	ll bc = b / c;
	ll bd = b / d;
	ll ac = (a-1) / c;
	ll ad = (a-1) / d;
	ll t = lcm(c, d);
	ll bt = b / t;
	ll at = (a - 1) / t;
	ans -= (bc + bd);
	ans += bt;
	ans += (ac + ad);
	ans -= at;
	cout << ans;
}

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

using namespace std;

using int64 = long long;

struct Edge {
  int from, to;
};

vector<vector<Edge>> ReadDirectedGraph(
    int n, int m, bool is_one_indexed=false) {
  vector<vector<Edge>> graph(n);
  for (int i = 0; i < m; i++) {
    int v1, v2;
    cin >> v1 >> v2;
    if (is_one_indexed) {
      v1--;
      v2--;
    }
    graph[v1].push_back(Edge({v1, v2}));
  }
  return graph;
}

vector<int> StronglyConnectedComponents(const vector<vector<Edge>>& graph) {
  int n = graph.size();
  vector<int> vs;
  vector<int> visited1(n);
  function<void(int)> dfs1 = [&](int v) {
    if (visited1[v]) return;
    visited1[v] = 1;
    for (const auto& e : graph[v]) dfs1(e.to);
    vs.push_back(v);
  };
  for (int v = 0; v < n; v++) dfs1(v);
  reverse(vs.begin(), vs.end());

  vector<vector<Edge>> r_graph(n);
  for (int v = 0; v < n; v++) {
    for (const auto& e : graph[v]) {
      r_graph[e.to].push_back(Edge({e.to, e.from}));
    }
  }

  vector<int> to_id(n);
  int current_id = 0;
  vector<int> visited2(n);
  function<void(int)> dfs2 = [&](int v) {
    if (visited2[v]) return;
    visited2[v] = 1;
    to_id[v] = current_id;
    for (const auto& e : r_graph[v]) dfs2(e.to);
  };
  for (int v : vs) {
    if (!visited2[v]) {
      dfs2(v);
      current_id++;
    }
  }
  return to_id;
}

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

  int n, m;
  cin >> n >> m;
  auto graph = ReadDirectedGraph(n, m, false);
  auto to_scc_id = StronglyConnectedComponents(graph);
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    int v1, v2;
    cin >> v1 >> v2;
    if (to_scc_id[v1] == to_scc_id[v2]) {
      cout << 1 << endl;
    } else {
      cout << 0 << endl;
    }
  }
}



Measured memory_bytes: 4628
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    x = LI()
    d = [[0]*2 for i in range(m)]
    for i in x:
        d[i%m][0] += 1
    x.sort()
    for i in range(max(x)+1):
        k = bisect.bisect_right(x,i)-bisect.bisect_left(x,i)
        if k > 1:
            p = i%m
            s = k >> 1
            d[p][0] -= 2*s
            d[p][1] += 2*s
    ans = 0
    for i in range(1,((m+1)>>1)):
        a,b = d[i]
        c,d_ = d[m-i]
        if a+b > c+d_:
            a,c = c,a
            b,d_ = d_,b
        ans += a+b
        if a+b <= c:
            c -= a+b
            ans += d_ >> 1
        else:
            d_ -= (a+b-c)
            ans += d_ >> 1
    ans += sum(d[0])>>1
    if not m&1:
        k = m >> 1
        ans += sum(d[k])>>1
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 63960
#include<bits/stdc++.h>
using namespace std;
int main(){
    char s[100000];
    scanf("%s",s);
    for (int i=0;i<strlen(s)-2;i++) {
        //if (s[i]==s[i+1] || s[i]==s[i+2] || s[i+1]==s[i+2]) {
        if (s[i]==s[i+1] || s[i]==s[i+2]) {
            printf("%d %d\n",i+1,i+3);
            return 0;
        }
    }
    if (strlen(s)==2 && s[0]==s[1]) printf("1 2\n");
    else printf("-1 -1\n");
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e3 + 5;
const int INF = 0x3f3f3f3f;
#define DEBUG(x) cout << (x) << '\n'


void run(){
    string s, ss;
    cin >> s >> ss;
    int ans = 0;
    for(int i = 0; i < s.size(); i++)
        ans += s[i] != ss[i];
    cout << ans;
}
int main(){
#ifdef Irene
    freopen("in.txt", "r", stdin);
#endif // Irene
//    ios::sync_with_stdio(false);

    run();
}


Measured memory_bytes: 3900
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

const MOD: i64 = 1e+9 as i64 + 7;

fn calc(
    y: usize,
    x: usize,
    pos: usize,
    used: usize,
    memo: &mut Vec<Vec<Vec<Vec<i64>>>>,
    k: usize,
) -> i64 {
    let h = memo.len();
    let w = memo[0].len();
    if y == h {
        return if pos == k { 1 } else { 0 };
    }
    if x == w - 1 {
        return calc(y + 1, 0, pos, 0, memo, k);
    }
    if memo[y][x][pos][used] != -1 {
        return memo[y][x][pos][used];
    }
    let mut ret = 0;
    if used == 0 {
        let npos = match pos {
            _ if pos == x => pos + 1,
            _ if pos == x + 1 => pos - 1,
            _ => pos,
        };
        ret = (ret + calc(y, x + 1, npos, 1, memo, k)) % MOD;
    }
    ret = (ret + calc(y, x + 1, pos, 0, memo, k)) % MOD;
    memo[y][x][pos][used] = ret;
    return ret;
}

fn main() {
    let h = read::<usize>();
    let w = read::<usize>();
    let k = read::<usize>() - 1;
    let mut memo = vec![vec![vec![vec![-1; 2]; w]; w]; h];
    let ans = calc(0, 0, 0, 0, &mut memo, k);
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<functional>
#include<algorithm>
#include<cstdio>
#include<unordered_map>
using namespace std;
typedef long long ll;
int main() {
	int n, l[200];
	cin >> n;
	n *= 2;
	for (int i = 0; i < n; i++)
		cin >> l[i];
	sort(l, l + n);
	ll sum = 0;
	for (int i = 0; i < n; i += 2) {
		sum += l[i];
	}
	cout << sum << endl;
}

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

int main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    for (auto &a : A) cin >> a;
    vector<int> Bp, Binv;
    reverse(A.begin(), A.end());
    for (auto a : A) {
        (Bp.size() == Binv.size() ? Bp : Binv).push_back(a);
    }
    reverse(Binv.begin(), Binv.end());
    Bp.insert(Bp.end(), Binv.begin(), Binv.end());
    for (auto b : Bp) printf("%d ", b);
    puts("");
}


Measured memory_bytes: 4332
import sys
input = sys.stdin.readline
import bisect

a,b,q = map(int, input().split())
INF = 10**18
s = [-INF] + [int(input()) for _ in range(a)] + [INF]
t = [-INF] + [int(input()) for _ in range(b)] + [INF]
for _ in range(q):
    x = int(input())
    i = bisect.bisect_right(s,x)
    j = bisect.bisect_right(t,x)
    d = INF
    for si in [s[i-1],s[i]]:
        for ti in [t[j-1],t[j]]:
            d1 = abs(x-si)+abs(ti-si)
            d2 = abs(x-ti)+abs(ti-si)
            d = min(d,d1,d2)
    print(d)

Measured memory_bytes: 63836
#define _CRT_SECURE_NO_DEPRECATE
//#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;
#define ll  long long int 
 
int main() {
	//freopen("test.txt", "r", stdin);
	int k,n; cin>>k>>n;
	vector<int> d, v;
	for(int i=0;i<n;i++) {int tmp; cin>>tmp; d.push_back(tmp);}
	for(int i=0;i<n-1;i++) v.push_back(d[i+1]-d[i]);
	v.push_back(d[0]+k-d[n-1]);
	cout<<accumulate(v.begin(), v.end(), 0) - *max_element(v.begin(), v.end())<<endl;
}

Measured memory_bytes: 2548
#include <map>
#include <list>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
int a,b,maxx;
string s[300];
map<string,int>ma;
map<string,int>mb;
int main()
{
	fast;
	cin>>a;
	for (int i=1;i<=a;i++)
	{
		cin>>s[i];
		ma[s[i]]++;
	}
	cin>>b;
	for (int i=1;i<=b;i++)
	{
		cin>>s[a+i];
		mb[s[a+i]]++;
	}
	
	for (int i=1;i<=a+b;i++)
	   if (ma[s[i]]-mb[s[i]]>maxx)
	      maxx=ma[s[i]]-mb[s[i]];
	cout<<maxx;
	return 0;
}

Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)


func next() int64 {
  sc.Scan()
  i, _ := strconv.ParseInt(sc.Text(), 10, 64)
  return i
}

func sort(array []int64) []int64 {
  if len(array) < 2 {
    return array
  }

  pivot := array[0]
  left := []int64{}
  right := []int64{}
  for _, v := range array[1:] {
    if v > pivot {
      right = append(right, v)
    } else {
      left = append(left, v)
    }
  }

  left = sort(left)
  right = sort(right)

  sorted := append(left, pivot)
  sorted = append(sorted, right...)

  return sorted
}


func main() {
  sc.Split(bufio.ScanWords)
  sc.Scan()
  n, _ := strconv.Atoi(sc.Text())
  arr := make([]int64, n, n+10000)
  isYes := true
  
  for i := 0; i < n; i++ {
    arr[i] = next()
  }
  
  arr = sort(arr)
  for i := 0; i < n-1; i++ {
    if arr[i] == arr[i+1] {
      isYes = false
    }
  }
  
  if isYes {
    fmt.Println("YES")
  } else {
    fmt.Println("NO")
  }
}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
int N;
vector<int> pathes[100050];
vector<int> children[100050];
int parent[100050];
int color[100050];
bool WIN = false;
void bfs1(int from) {
    for(int i = 0; i < pathes[from].size(); i++) {
        int to = pathes[from][i];
        if(to == parent[from]) continue;
        parent[to] = from;
        children[from].push_back(to);
        bfs1(to);
    }
}

void bfs2(int from) {
    int sum = 0;
    for(int i = 0; i < children[from].size(); i++) {
        int to = children[from][i];
        bfs2(to);
        sum += color[to];
    }
    if(sum >= 2) WIN = true;
    if(sum >= 1) color[from] = 0;
    if(sum == 0) color[from] = 1;
    if(from == 1) {
        if(sum == 0) WIN = true;
    }
}

int main() {
    //cout.precision(10);
    cin >> N;
    for(int i = 1; i < N; i++) {
        int a, b;
        cin >> a >> b;
        pathes[a].push_back(b);
        pathes[b].push_back(a);
    }
    bfs1(1);
    bfs2(1);
    if(WIN) cout << "First" << endl;
    else cout << "Second" << endl;
    return 0;
}


Measured memory_bytes: 11008
#define ENABLE_DEBUG 1
// Kana's kitchen {{{
#include<bits/stdc++.h>
#define ALL(v) std::begin(v),std::end(v)
#define LOOP(k) for(i64 ngtkana_is_a_genius=0; ngtkana_is_a_genius<(i64)k; ngtkana_is_a_genius++)

using i32 = std::int_least32_t;
using i64 = std::int_least64_t;
using u32 = std::uint_least32_t;
using u64 = std::uint_least64_t;
using usize = std::size_t;

template <class T, class U> using pair = std::pair<U, T>;
template <class T> using diag_pair = std::pair<T, T>;
template <class... Args> using tuple = std::tuple<Args...>;
template <class T> using vec = std::vector<T>;
template <class T> using numr = std::numeric_limits<T>;

#ifdef NGTKANA
#include<debug.hpp>
#else
#define DEBUG(...)(void)0
#endif
/*}}}*/
auto cmx = [](auto& x, auto y){ if (x<y) { x=y; return true; } return false; };
int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::setprecision(15) << std::fixed;

    usize lim = 0;

    usize n, k;
    std::cin >> n >> k;
    vec<pair<u32, usize>> ab(n);
    for (auto&& p: ab) {
        std::cin >> p.first >> p.second;
        cmx(lim, p.first);
    }
    lim++;

    vec<u64> cnt(lim);
    for (auto&& p: ab) cnt.at(p.first) += p.second;

    u64 now = 0;
    for (usize i=0; i<lim; i++) {
        now += cnt.at(i);
        if (k<=now) {
            std::cout << i << '\n';
            return 0;
        }
    }
}


Measured memory_bytes: 2560
from itertools import combinations
N = int(input())
L = list(map(int, input().split()))

lst = list(combinations(range(N), 3))

ans = 0
for a, b, c in lst:
    if L[a] + L[b] <= L[c]:
        continue
    elif L[b] + L[c] <= L[a]:
        continue
    elif L[c] + L[a] <= L[b]:
        continue
    elif L[a] == L[b] or L[a] == L[c] or L[b] == L[c]:
        continue
    else:
        ans += 1
print(ans)

Measured memory_bytes: 20516
#include <stdio.h>
int main(){
int k,a,b,i,c=0;
scanf("%d",&k);
scanf("%d%d",&a,&b);

  for(i=a;i<=b;i++){
    if(i%k==0){
       c=1;
    }
  }
if(c==1){
    printf("OK");
}
else{
    printf("NG");
}
return 0;
}

Measured memory_bytes: 2144
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) debug(x) debug(y);
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))
const int MOD = 1e9 + 7;
const int mxN = 2e5 + 5;

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

ll a[mxN];
vector<ll> pos, neg;
int n, k;

void solveNeg(){
	reverse(all(pos));
	reverse(all(neg));
	int st = 0;
	for(int i = k; i >= 0; i--) if((k - i) & 1){
		if(pos.size() >= i){
			st = i;
			break;
		}
	}
	int cur = pos.size() - st;
	int negInd = k - st;
	for(int i = st; i >= 0; i -= 2){
		if(cur < (int)(pos.size() - 1) && negInd < (int)(neg.size() - 1) && (neg[negInd] * neg[negInd + 1]) < (pos[cur] * pos[cur + 1])){
			cur += 2;
			negInd += 2;
		}
	}
	ll ans = 1LL;
	rep(i, negInd) ((ans *= neg[i]) += MOD) %= MOD;
	repn(i, cur, pos.size()) ((ans *= pos[i]) += MOD) %= MOD;
	cout << (ans + 2 * MOD) % MOD << endl;
	exit(0);
}

void solvePos(){
	int st = 0;
	for(int i = k; i >= 0; i--) if((k - i) % 2 == 0){
		if(pos.size() >= i){
			st = i;
			break;
		}
	}
	int cur = (int)pos.size() - st;
	int negInd = k - st;
	for(int i = st; i >= 0; i -= 2){
		if(cur < (int)(pos.size() - 1) && negInd < (int)(neg.size() - 1) && (neg[negInd] * neg[negInd + 1]) > (pos[cur] * pos[cur + 1])){
			cur += 2;
			negInd += 2;
		}
	}
	ll ans = 1LL;
	rep(i, negInd) ((ans *= -neg[i]) %= MOD) %= MOD;
	repn(i, cur, pos.size()) ((ans *= pos[i]) += MOD) %= MOD;
	cout << (ans + MOD) % MOD << endl;
	exit(0);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	cin >> n >> k;
	rep(i, n){
		cin >> a[i];
		if(a[i] < 0) neg.pb(a[i]);
		else pos.pb(a[i]);
	}
	sort(all(pos));
	sort(all(neg));
	if((int)pos.size() >= k) solvePos();
	for(int i = 2; i <= (int)neg.size(); i += 2) if(k >= i && (int)pos.size() >= (k - i)) solvePos();	
	solveNeg();
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


Measured memory_bytes: 6684
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vint = vector<int>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vchar = vector<char>;
using vvchar = vector<vchar>;
using vp = vector<P>;
using vpp = vector<pair<P, P>>;
using vvp = vector<vp>;

#define rep(i, n) for (int i = 0; i < n; ++i)
#pragma region Debug
istream &operator>>(istream &is, P &a)
{
    return is >> a.first >> a.second;
}
ostream &operator<<(ostream &os, const P &a) { return os << "(" << a.first << "," << a.second << ")"; }

template <typename T>

void view(const std::vector<T> &v)
{
#ifndef ONLINE_JUDGE
    for (const auto &e : v)
    {
        std::cout << e << " ";
    }
    std::cout << std::endl;
#endif
}
template <typename T>
void view(const std::vector<std::vector<T>> &vv)
{
    for (const auto &v : vv)
    {
        view(v);
    }
}
#pragma endregion

int dist(P a, P b)
{
    return abs(a.first - b.first) + abs(a.second - b.second);
}

int main()
{
    int n;
    cin >> n;
    vp a(n);
    rep(i, n) cin >> a[i];
    vp b = a, c = a, d = a;
    rep(i, n) swap(b[i].first, b[i].second);
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    sort(c.begin(), c.end(), [](P x, P y) {
        return x.first + x.second < y.first + y.second;
    });
    sort(d.begin(), d.end(), [](P x, P y) {
        return x.first - x.second < y.first - y.second;
    });
    view(a);
    view(b);
    view(c);
    view(d);

    int ans = 0;
    rep(i, n)
    {
        int x = a[i].first, y = a[i].second;
        int dx = max(dist(a[0], a[i]), dist(a[n - 1], a[i]));
        int dy = max(abs(b[0].second - x) + abs(b[0].first - y), abs(b[n - 1].second - x) + abs(b[n - 1].first - y));
        int dur = max(dist(c[0], a[i]), dist(c[n - 1], a[i]));
        int ddl = max(dist(d[0], a[i]), dist(d[n - 1], a[i]));
        ans = max(ans, max(dy, dx));
        ans = max(ans, dur);
        ans = max(ans, ddl);
    }
    cout << ans << endl;

    return 0;
}

// 4
// 1 1
// 10 10
// 0 10
// 10 0

Measured memory_bytes: 9536
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

N, L = map(int, input().split())
S = []
for _ in range(N):
    S.append(input())

S.sort()
ans = "".join(S)
print(ans)

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

using ll = long long;
#define repi(n) for (int i = 0; i < (n); i++)
#define repj(n) for (int j = 0; j < (n); j++)
#define repk(n) for (int k = 0; k < (n); k++)
#define repl(n) for (int l = 0; l < (n); l++)
#define rep(i, n) for (int i = 0; (i) < (n); i++)
#define repr(i, a, b) for (auto i = (a); i < (b); i++)
#define repv(itr) for (auto&& v : (itr))
#define updatemax(t, v) (t = max((t), (v)))
#define updatemin(t, v) (t = min((t), (v)))
const int dx[] = {-1, 0, 0, 1, -1, -1, 1, 1};
const int dy[] = {0, -1, 1, 0, -1, 1, -1, 1};
template <typename T>
T minptr(T begin, T end) {
  T re = begin;
  for (T i = begin + 1; i != end; i++) {
    if (*i < *re) re = i;
  }
  return re;
}
template <typename T>
T maxptr(T begin, T end) {
  T re = begin;
  for (T i = begin + 1; i != end; i++) {
    if (*i > *re) re = i;
  }
  return re;
}
int __vmax(int x) {
  return INT_MAX;
}
double __vmax(double x) {
  return 1e+300;
}
ll __vmax(ll x) {
  return LLONG_MAX;
}
int __vmin(int x) {
  return INT_MIN;
}
double __vmin(double x) {
  return -1e+300;
}
ll __vmin(ll x) {
  return LLONG_MIN;
}
ll modpow(ll a, ll b, ll m) {
  ll re = 1, k = 1;
  while (k <= b) {
    if (b & k) {
      re *= a;
      re %= m;
    }
    k = k << 1;
    a *= a;
    a %= m;
  }
  return re;
}
ll modinv(ll a, ll m) {
  ll b = m, u = 1, v = 0;
  while (b) {
    ll t = a / b;
    a -= t * b;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  u %= m;
  if (u < 0) u += m;
  return u;
}
template <typename T>
vector<T> lis(T begin, T end, bool allowequal = false, bool lds = false) {
  using V = typename iterator_traits<T>::value_type;
  int n = end - begin;
  vector<V> a(n, lds ? __vmin(*begin) : __vmax(*begin));
  vector<int> id(n);
  if (lds && allowequal) {
    for (int i = 0; i < n; i++) {
      id[i] = n - 1 -
              (lower_bound(a.rbegin(), a.rend(), begin[i]) - 1 - a.rbegin());
      a[id[i]] = begin[i];
    }
  } else if (lds) {
    for (int i = 0; i < n; i++) {
      id[i] = n - 1 -
              (upper_bound(a.rbegin(), a.rend(), begin[i]) - 1 - a.rbegin());
      a[id[i]] = begin[i];
    }
  } else if (allowequal) {
    for (int i = 0; i < n; i++) {
      id[i] = upper_bound(a.begin(), a.end(), begin[i]) - a.begin();
      a[id[i]] = begin[i];
    }
  } else {
    for (int i = 0; i < n; i++) {
      id[i] = lower_bound(a.begin(), a.end(), begin[i]) - a.begin();
      a[id[i]] = begin[i];
    }
  }
  int m = *maxptr(id.begin(), id.end());
  vector<T> re(m + 1);
  for (int i = n - 1; i >= 0; i--) {
    if (id[i] == m) re[m--] = begin + i;
  }
  return re;
}

int gcd(int a, int b) {
  return b ? gcd(b, a % b) : a;
}
int main() {
  int n;
  cin >> n;
  vector<int> p(n + 1);
  repi(n + 1) cin >> p[i];
  sort(p.begin(), p.end());
  int re = 0;
  repi(n) re = gcd(re, p[i + 1] - p[i]);
  cout << re << endl;
}


Measured memory_bytes: 640
import std.stdio, std.string, std.range, std.conv, std.array, std.algorithm, std.math, std.typecons, std.bigint;

void main() {
    /*
    nCr = n!/(n-r)!/r!
    nC(r+1) = n!/(n-r-1)!/(r+1)!

    nC(r+1) / nCr = (n-r)!r! / { (n-r-1)!(r+1)!}
                  = (n-r) / (r+1) > 1 のときはrを増加

                    n-r > r+1
                    n > 2r + 1
                    r < (n-1)/2　のときはrを増やしても良い

                    nが奇数のとき、r = (n-1)/2 は整数だから、rとr+1で最大値を取る
                    nが偶数のとき、r = (n-1)/2は小数だから、r-1/2までは増加する。
                    したがって、最大値はr+1/2
     */


    auto N = readln.chomp.to!int;
    auto a = readln.split.to!(int[]);

    auto n = a.reduce!((a,b) => a > b ? a : b);

    auto top = (n-1)*.5;

    auto lower = a.filter!(x => x != n).filter!(x => x <= top);
    auto upper = a.filter!(x => x != n).filter!(x => x > top);

    if (lower.empty) {
        writefln("%d %d", n, upper.reduce!((a,b) => a < b ? a : b));
    } else if (upper.empty) {
        writefln("%d %d", n, lower.reduce!((a,b) => a > b ? a : b));
    } else {
        auto r1 = lower.reduce!((a,b) => a > b ? a : b);
        auto r2 = upper.reduce!((a,b) => a < b ? a : b);

        /*
           nCa > nCb
           (n-a)!a! < (n-b)!b!

           a < bは既知なので、n-a>n-b

           (n-a)!/(n-b)! < b!/a!

           (n-a)*...*(n-b+1) < b*..(a+1)

           これらの個数は等しいので、各々比べれば良い

           n < a + b
           */

        if (n < r1+r2) {
        //if (combi(BigInt(n), BigInt(r1)) > combi(BigInt(n), BigInt(r2))) {
            writefln("%d %d", n, r1);
        } else {
            writefln("%d %d", n, r2);
        }
    }
}



Measured memory_bytes: 4560
def hukuri(y, m, p, t) :
    for i in range(y) :
        m += int(m * p) - t
    return m

def tanri(y, m, p, t) :
    risoku = 0
    for i in range(y) :
        risoku += int(m * p)
        m -= t
    return m+risoku
    
M = int(input())
for i in range(M) :
    m = int(input())
    y = int(input())
    N = int(input())
    ans = []
    for j in range(N) :
        s, p, t = input().split()
        if s == '0' :
            ans.append(tanri(y, m, float(p), int(t)))
        elif s == '1' :
            ans.append(hukuri(y, m, float(p), int(t)))
    print(max(ans))


Measured memory_bytes: 5640
# coding: utf-8

# In[6]:

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
#S = input()


# In[2]:

import math


# In[14]:

#print(N, K)


# In[15]:

sum_ = 0
R = min(N, K)
clear = N-K+1 if N>=K else 0
R = R-1 if N>=K else R
#print('R = {}'.format(R))
for i in range(R):
    #print(math.ceil(math.log(K/(i+1), 2)))
    sum_ += (1/2) ** math.ceil(math.log(K/(i+1), 2))


# In[16]:

#print(clear/N)
print(round(1/N*sum_ + clear/N, 16))


# In[ ]:





Measured memory_bytes: 3060
//
// Created by chuan on 2020-04-10.
//

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using ll = long long ;

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    string s;
    cin>>s;
    for (auto& c : s ) {
        if (!islower(c)) {
            cout<<"No"<<endl;
            return 0;
        }
    }
    if (s.size() == 6 && s[2] == s[3] && s[4] == s[5]) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;


    return 0;
}




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

int main(){
    map <string, list<int> > book;
    string word;
    int page;
    while(cin >> word >> page){
        book[word].push_back(page);
    }
    map <string, list<int> >::iterator it = book.begin();
    while(it != book.end()){
        it->second.sort();
        it++;
    }
    it = book.begin();
    while(it != book.end()){
        cout << it->first << endl;
        list<int>::iterator list_it = it->second.begin();
        while(list_it != it->second.end()){
            if(list_it != it->second.begin()) cout << " ";
            cout << *list_it;
            list_it++;
        }
        cout << endl;
        it++;
    }
    return 0;
}

Measured memory_bytes: 0
#include<stdio.h>
#define NOT_FOUND 0
int A[100000];
int n;
int binarySearch(int key){
  int mid,left=0,right = n;
  while(left<right){
    mid = (left + right) /2;
    if(A[mid]==key){
      return 1;
    }else if(key<A[mid]){
      right = mid;
    }else {
      left = mid + 1;
    }
  }
  return NOT_FOUND;
}
int main(){
  int i,key,a,cnt=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  scanf("%d",&a);
  for(i=0;i<a;i++){
    scanf("%d",&key);
    if(binarySearch(key)) cnt++;
  }
  printf("%d\n",cnt);
  return 0;
}


Measured memory_bytes: 2148
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pint pair<int,int>
#define mk(x,y) make_pair(x,y)
#define fir first
#define sec second
#define Rep(x,y,z) for(int x=y;x<=z;++x)
#define Red(x,y,z) for(int x=y;x>=z;--x)
using namespace std;
const int MAXN=1505;
char buf[1<<12],*p1=buf,*p2=buf,nc;int ny;
//inline char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
inline char gc(){return getchar();}
inline int read(){
	int x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc!=EOF)if(nc==45)ny=-1;if(nc<0)return nc;
	x=nc-48;while(nc=gc(),47<nc&&nc<58&&nc!=EOF)x=(x<<3)+(x<<1)+(nc^48);return x*ny;
}
int Sumv[MAXN][MAXN],rpos[MAXN][MAXN],Mn[2][MAXN][MAXN],Mx[2][MAXN][MAXN],n;ll ans;
char S[MAXN][MAXN];
int main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	n=read();
	Rep(i,1,n)scanf("%s",S[i]+1);
	for(int i=n,cur=1;i>=1;i--,cur^=1)Red(j,n,1)if(S[i][j]!='#'){
		Sumv[i][j]=Sumv[i+1][j]+Sumv[i][j+1]+(S[i][j]^48),rpos[i][j]=max(max(rpos[i+1][j],rpos[i][j+1]),i);
		Mn[cur][j][i]=j;
		Rep(k,i+1,rpos[i+1][j])Mn[cur][j][k]=Mn[cur^1][j][k];
		Rep(k,max(rpos[i+1][j],i)+1,rpos[i][j+1])Mn[cur][j][k]=Mn[cur][j+1][k];
		Mx[cur][j][i]=j;
		Rep(k,i,rpos[i][j+1])Mx[cur][j][k]=Mx[cur][j+1][k];
		Rep(k,max(rpos[i][j+1],i)+1,rpos[i+1][j])Mx[cur][j][k]=Mx[cur^1][j][k];
		for(int d=i+1,r=min(rpos[i][j+1],rpos[i+1][j]);d<=r;d++){
			if(Mx[cur^1][j][d]>=Mn[cur][j+1][d])
				Sumv[i][j]-=Sumv[d][Mn[cur][j+1][d]],d=rpos[d][Mn[cur][j+1][d]];
		}ans=(ans+1ll*(Sumv[i][j]-(S[i][j]^48))*(S[i][j]^48));
	}cout<<ans<<"\n";
	return 0;
}



Measured memory_bytes: 58904
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>

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

struct interval {
    int s, f;
    interval(int s, int f) : s(s), f(f) { }
};
bool compare_f(const interval &x, const interval &y) {
    return x.f < y.f;
}
vector<interval> interval_scheduling(vector<interval> J) {
    vector<interval> A;
    sort(J.begin(), J.end(), compare_f);
    int f = -1e9-1;
    for (int i = 0; i < J.size(); ++i) {
        if (J[i].s >= f) {
            A.push_back(J[i]);
            f = J[i].f;
        }
    }
    return A;
}

int main(){
    int n;
    cin >> n;
    vector<interval> vec;
    rep(i,n){
        int a,b;
        cin >> a >> b;
        vec.push_back({a-b,a+b});
    }

    vector<interval> ans = interval_scheduling(vec);
    // for ( auto e : ans){
    //     cout << e.s << " " << e.f << endl;
    // }
    cout << ans.size() << endl;

    return 0;
}

Measured memory_bytes: 3316
#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;
using ll = long long;
#define repl(i, l, r) for (int i = l; i < r; i++)
#define rep(i, n) repl(i, 0, n)
int main() {
	int n;
	string s, t;
	cin >> n >> s >> t;
	rep(i, n) {
		int now = 0;
		rep(j, n - i) {
			if (s[i + j] == t[j]) now++;
		}
		if (now == n - i) {
			cout << n + i << endl;
			return 0;
		}
	}
	cout << 2 * n << endl;
	return 0;
}

Measured memory_bytes: 256
n = gets.to_i

csf = []
(n - 1).times {csf << gets.split.map(&:to_i)}

(n - 1).times do |i|
    t = csf[i][1] + csf[i][0]

    (i + 1).upto(n - 2) do |j|
        t = csf[j][1] if t < csf[j][1]
        t = (t + csf[j][2] - 1) / csf[j][2] * csf[j][2] + csf[j][0]
    end

    puts t
end

puts 0

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

int gcd(int a, int b){
   if(a > b){int tmp = a; a = b; b = tmp;} // make sure a <= b 
   int r = b % a;
   return r == 0 ? a : gcd(r, a); // gcd(a, b) = gcd(b % a, a)
}


int main(void) {
   int N;
   cin >> N;
   vector<int> v;
   for (int i = 0; i < N; i++) {
      int a;
      cin >> a;
      v.push_back(a);
   }
   int ans = v[0];
   for (int i = 0; i < N ; i++) {
      ans = gcd(ans, v[i]);
   }
   cout << ans << endl;
   return 0;
}



Measured memory_bytes: 892
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define LLINF 9223372036854775807
#define MOD ll(1e9+7)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr<<#x<<": "<<x<<endl


int main(){
    ll a, b, q;
    cin >> a >> b >> q;
    vector<ll> s(a+2);
    vector<ll> t(b+2);
    s[0] = -99999999999;
    t[0] = -99999999999;
    s[a+1] = 99999999999;
    t[b+1] = 99999999999;
    for(int i = 0; i < a; i++){
        cin >> s[i+1];
    }
    for(int i = 0; i < b; i++){
        cin >> t[i+1];
    }
    for(int i = 0; i < q; i++){
        ll x;
        cin >> x;
        auto siter = lower_bound(all(s), x);
        auto titer = lower_bound(all(t), x);
        ll sl = abs(x - s[siter-s.begin()-1]);
        ll sr = abs(x - s[siter-s.begin()]);
        ll tl = abs(x - t[titer-t.begin()-1]);
        ll tr = abs(x - t[titer-t.begin()]);
        ll ans = 1LL<<60;
        ans = min(max(sl,tl),ans);
        ans = min(min(2*tl+sr, tl+2*sr),ans);
        ans = min(min(2*sl+tr, sl+2*tr),ans);
        ans = min(max(sr,tr),ans);
        cout << ans << endl;
    }


    return 0;
}


Measured memory_bytes: 2944
#include<bits/stdc++.h>
#pragma GCC target ("avx")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()

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;
}
constexpr int mod = 1e9+7;
constexpr long long inf = 3e18;

int N,M,D[100005],A[200005],B[200005],C[200005];
vector<P>G[100005],G2[100005];
bool co[100005],used[100005];
void dfs(int x,int p){
	used[x]=true;
	for(auto i:G2[x])if(p!=i.first){
		C[i.second]=max(D[x],D[i.first]);
		co[i.first]=!co[x];
		dfs(i.first,x);
	}
}
signed main(){
	cin>>N>>M;
	rep(i,N)cin>>D[i];
	rep(i,M){
		cin>>A[i]>>B[i];A[i]--;B[i]--;
		G[A[i]].push_back({B[i],i});
		G[B[i]].push_back({A[i],i});
	}
	rep(i,N){
		int mn=inf,idx;
		rep(j,len(G[i]))if(chmin(mn,D[G[i][j].first]))idx=j;
		if(mn>D[i]){cout<<"-1\n";return 0;}
		G2[i].push_back(G[i][idx]);
		G2[G[i][idx].first].push_back({i,G[i][idx].second});
	}
	rep(i,N)if(!used[i])dfs(i,i);
	rep(i,N)cout<<(co[i]?"B":"W");
	cout<<"\n";
	rep(i,M)cout<<(C[i]?C[i]:(int)1e9)<<"\n";
}

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

using int64 = long long;

int main() {
  int64 a, b, k;
  cin >> a >> b >> k;
  int64 ua = min(a, k);
  a -= ua;
  b -= min(b, k - ua);
  cout << a << " " << b << "\n";
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

using namespace std;

#define FOR(i,n) for(int i = 0; i < n; i++)
#define FORa(i,a,b) for(int i = a; i < b; i++)
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define SORT(a,n) sort(begin(a), begin(a) + n)
#define VSORT(v) sort(v.begin(), v.end())
#define MAX 1000000
#define ll long long
#define LOW(s) transform(s.begin(),s.end(),s.begin(),::tolower)
#define UP(s) transform(s.begin(),s.end(),s.begin(),::toupper)

//-------------------------------------------------------//

int main() {
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	
	for(int i = 0; a > 0 && c > 0; i++) {
		if(i%2 == 0) c -= b;
		else a -= d;
	}
  
	cout << (a > 0 ? "Yes" : "No") << endl;
	
	return 0;
}


Measured memory_bytes: 3620
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[float('inf')]*n
dp[0]=0
for i in range(0,n):
    for j in range(1,k+1):
        if i+j>n-1:
            continue
        dp[i+j]=min(dp[i+j],dp[i]+abs(a[i]-a[i+j]))
print(dp[-1])

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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),i_len=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define pb push_back
#define mp make_pair

int main()
{
    ll A, B, H, M;
    cin >> A >> B >> H >> M;

    double alpha = H * PI / 6.0 + M * PI / 360.0;
    double beta = M * PI / 30.0;

    double hx = -A * sin(alpha);
    double hy = A * cos(alpha);
    double mx = -B * sin(beta);
    double my = B * cos(beta);

    double dx = hx - mx;
    double dy = hy - my;

    double d = sqrt(dx*dx + dy*dy);
    cout << setprecision(12) << d << endl;

    return 0;
}

/*

1h -> pi/6
1m -> pi/360

1m -> pi/30

cos(pi/2-x) = -sin(x)
sin(pi/2-x) = cos(x)

*/

Measured memory_bytes: 4040
//itp1_10a
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;

int main(){
 double x1,x2,y1,y2,res;

 cin>>x1>>y1>>x2>>y2;
 res=sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
// cout<<res<<endl;
 printf("%.6f\n",res);
 return 0;
}

Measured memory_bytes: 1236
#include<stdio.h>

int main(void)

{

int a,b;

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

if(a<b){ 

printf("a < b\n");

}

else if(a>b){ 

printf("a > b\n");

}

else if(a=b){ 

printf("a == b\n");

}

return 0;

}

Measured memory_bytes: 580
import re

def main():
    s = input()
    s = re.sub('eraser', '', s)
    s = re.sub('erase', '', s)
    s = re.sub('dreamer', '', s)
    s = re.sub('dream', '', s)
    print('YES' if len(s) == 0 else 'NO')

if __name__ == '__main__':
    main()


Measured memory_bytes: 41456
if __name__ == "__main__":
    N, K, C = map(int, input().split())
    S = input()

    L = []
    i = 0
    while len(L) < K:
        if S[i] == 'o':
            L.append(i)
            i += C
        i += 1

    R = []
    i = N-1
    while len(R) < K:
        if S[i] == 'o':
            R.append(i)
            i -= C
        i -= 1
    R = R[::-1]

    # print(L)
    # print(R)

    for i in range(K):
        if L[i] == R[i]:
            print(L[i] + 1)


Measured memory_bytes: 59640
#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;cin>>n;
    vector<int>v(n);
    for(int i=0;i<n;i++)cin>>v[i];
    long long sum=0,sum1=0,sum2=0,s;
    for(int i=0;i<n;i++)sum+=v[i];
    s=sum;
    for(int i=0;i<n;i++){
        sum1+=v[i];
        s-=v[i];
        if(sum1>=s)break;
    }
    s=sum;
    for(int i=n-1;i>=0;i--){
        sum2+=v[i];
        s-=v[i];
        if(sum2>=s)break;
    }
    s=min(sum1,sum2);
    sum=sum-s;
    cout<<abs(sum-s);
}


Measured memory_bytes: 256