akhauriyash/Code-Regression huggingface dataset:
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#include<algorithm>//next_permutation
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

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

const ll MOD = 1000000007;
const ll MAX = 2000001;

ll mod(ll a){
  return a % MOD;
}

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

ll fac[MAX], finv[MAX], inv[MAX];

void nCrprep() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll nCr(ll n, ll r){
    if (n < r) return 0;
    if (n < 0 || r < 0) return 0;
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
}

ll nCrcheep(ll n,ll r){
  if(r == 0) return 1;
  else if(r == 1) return n;
  else return nCrcheep(n-1,r-1)*n/r;
}

vector<pair<ll,ll>> prime_factorize(ll n){
  vector<pair<ll,ll>> res;
  
  for(ll i=2; i*i <= n; i++){
    if(n % i != 0) continue;
    
    ll ex = 0;
    while(n % i == 0){
      ex++;
      n /= i;
    }
    
    res.push_back({i,ex});
  }
  
  if(n != 1) res.push_back({n,1});
  
  return res;
  
}




int main(){
  ll n; cin >> n;
  vl num(n);
  
  rep(i,n) cin >> num[i];
  
  ll cnt = 0; bool flag = false;
  
  rep(i,n){
    if(num[i] == i+1){
      if(!flag){
        cnt++;
        flag = true;
      }
      else flag = false;
    }
    else flag = false;
  }
  
  cout << cnt << endl;
  
  
  
}

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

using namespace std;
using ll = long long;

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define debug(x) cout << #x << ": " << x << endl;
#define popcnt __builtin_popcount

int N, M;
char A[50][50], B[50][50];

bool check(int sy, int sx){
    for(int i = 0; i < M; i++)
    {
        for(int j = 0; j < M; j++)
        {
            if(sy+i>=N||sx+j>=N)return false;
            if(A[sy+i][sx+j]!=B[i][j])return false;
        }
    }
    return true;
}

int main() {
    cin>>N>>M;
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            cin>>A[i][j];
        }
        
    }

    for(int i = 0; i < M; i++)
    {
        for(int j = 0; j < M; j++)
        {
            cin>>B[i][j];
        }
        
    }

    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(check(i, j)){
                puts("Yes");
                return 0;
            }
        }
        
    }
    
    puts("No");

    return 0;
}

Measured memory_bytes: 256
# coding:utf-8
import math

N=int(input())
x=list(map(int,input().split()))
y=list(map(int,input().split()))

manh_dist=0.0
for i in range(0,N):
    manh_dist=manh_dist+math.fabs(x[i]-y[i])

print('%.6f'%manh_dist)

eucl_dist=0.0
for i in range(0,N):
    eucl_dist=eucl_dist+(x[i]-y[i])**2
eucl_dist=math.sqrt(eucl_dist)

print('%.6f'%eucl_dist)

mink_dist=0.0
for i in range(0,N):
    mink_dist=mink_dist+math.fabs(x[i]-y[i])**3
mink_dist=math.pow(mink_dist,1.0/3)

print('%.6f'%mink_dist)

cheb_dist=0.0
for i in range(0,N):
    if cheb_dist<math.fabs(x[i]-y[i]):
        cheb_dist=math.fabs(x[i]-y[i])

print('%.6f'%cheb_dist)

Measured memory_bytes: 7860
#include <iostream>

using namespace std;

int main()
{
int i, h, m, s;
cin >> i;
h = i / 3600;
m = i / 60 - h * 60;
s = i - m * 60 - h * 3600;
cout << h << ":" << m << ":" << s << endl;
return 0;
}


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

using namespace std;

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

    long long int monsters[N + 1];
    long long int heroes[N];

    long long int input;
    for (int i = 0; i < N + 1; i++)
    {   
        cin >> input;
        monsters[i] = input;
    }

    for (int i = 0; i < N; i++)
    {
        cin >> input;
        heroes[i] = input;
    }

    long long int defeated = 0;
    for (int i = 0; i < N; i++)
    {
        if (heroes[i] <= monsters[i]) {
            defeated += heroes[i];
        } else {
            defeated += monsters[i];
            long long int leftover = heroes[i] - monsters[i];
            defeated += min(leftover, monsters[i + 1]);
            monsters[i + 1] = max(monsters[i + 1] - leftover, (long long) 0);
        }
    }

    cout << defeated;
}


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

#define coutv(v) for (int i = 0; i < (v).size(); ++i) cout << v[i] << ' '; cout << endl;
#define coutvv(v) for (int i = 0; i < (v).size(); ++i) {for (int j = 0; j < (v[i]).size(); ++j) cout << v[i][j] << ' '; cout << endl;}
#define debugv(v) {for (int i = 0; i < (v).size(); ++i) cerr << v[i] << ' '; cerr << endl;}
#define debugvv(v) {for (int i = 0; i < (v).size(); ++i) {for (int j = 0; j < (v[i]).size(); ++j) cerr << v[i][j] << ' '; cerr << endl;}}
#define stringtovector(s, v) {for (int i = 0; i < (s).size(); ++i) v.push_back(s[i]);};
#define TC int TESTCASE; cin >> TESTCASE; while (TESTCASE--)
typedef long long ll;
const int mod = 1000000007;





int main() {
    string s; string t;
    cin >> s >> t;
    vector<int> c;
    for (int i = 0; i < s.length() - t.length() + 1; i++) {
        c.push_back(0);
        for (int j = 0; j < t.length(); j++) {
            if (s[i+j] != t[j]) {
                c[i] += 1;
            }
        }
    }
    sort(c.begin(), c.end());
    cout << c[0];
}





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


#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ll long long
#define pii pair<int,int>
#define all(x) begin(x), end(x)
#define loop(i,n) for(int i=0; i<n; i++)
#define rep(i,a,b,c) for(int i=a; i<b; i+=c)
#define brep(i,a,b,c) for(int i=a; i>b; i-=c)
#define tc(t) int t; cin>>t; while(t--)
#define sz(v) int((v).size())
#define pb push_back

const int N = 2e5 + 10;


using namespace std;

int main()
{



	IOS;

	int a, b, c, x;

	cin >> a >> b >> c >> x;

	int count = 0;

	for (int i = 0; i <= a; i++)
	{
		for (int j = 0; j <= b; j++)
		{
			for (int k = 0; k <= c; k++)
			{
				if (i * 500 + j * 100 + k * 50 == x)
				{
					count++;
				}

			}
		}
	}


	cout << count << endl;



	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    static int modP = 1000000007;
    static long inf  = Long.MAX_VALUE;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String s = in.next();

        int cnt = 0;
        for(int i = n-1; i >= 0; i--) {
            if(s.charAt(i) == ')') {
                cnt++;
            }else if(s.charAt(i) == '(') {
                if(cnt > 0){
                    cnt--;
                }else{
                    s = s + ")";
                }
            }
        }
        for(int i = 0; i < cnt; i++) {
            s = "(" + s;
        }

        print(s);
    }

    static void print(String s) {
        System.out.println(s);
    }

    static void print(int i) {
        System.out.println(i);
    }

    static void print(long i) {
        System.out.println(i);
    }
}

Measured memory_bytes: 21844
from collections import Counter
n = int(input())
s = [input() for _ in range(n)]
c = Counter(s)
m = 0
for v in c.values():
	m = max(m, v)
ans = []
for k, v in c.items():
	if v == m:
		ans.append(k)
ans.sort()
print(*ans, sep="\n")

Measured memory_bytes: 35904
"use strict";
// 2254
const main = arg => {
    const input = arg.trim().split("\n");

    const a = parseInt(input[0].split(" ")[0]);
    const b = parseInt(input[0].split(" ")[1]);
    const h = parseInt(input[0].split(" ")[2]);
    const m = parseInt(input[0].split(" ")[3]);
    let angS = 360*m/60
    let angL = 360*5*h/60 + 360/12*m/60
    const diff = angS > angL ? angS-angL : angL-angS
    const rad = diff*Math.PI/180
    let x = Math.sqrt(a*a + b*b - 2*a*b*Math.cos(rad))
    console.log(x)
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));  


Measured memory_bytes: 29744
#include<stdio.h>

int main(void){
	int A,B;
	scanf("%d%d", &A, &B);
	int math[3] = {A + B, A - B, A * B};

	int max = math[0];
	for(int i = 1; i < 3; i++){
		if(max < math[i])max = math[i];
	}
	printf("%d\n", max);
	return 0;
}


Measured memory_bytes: 128
import java.util.*;
class Main{
  public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    List<Rest> l=new ArrayList<>(n);
    for(int i=1;i<=n;i++){
      l.add(new Rest(i,sc.next(),sc.nextInt()));
    }
    Collections.sort(l);
    for(int i=0;i<n;i++){
      System.out.println(l.get(i));
    }
  }
  static class Rest implements Comparable{
    int num;
    String city;
    int point;
    Rest(int n,String s,int p){
      num=n;
      city=s;
      point=p;
    }
    public int compareTo(Object o){
      if(city.compareTo(((Rest)o).city)!=0){
        return city.compareTo(((Rest)o).city);
      }
      return ((Rest)o).point-point;
    }
    public boolean equals(Object o){
      return num==((Rest)o).num;
    }
    public String toString(){
      return String.valueOf(num);
    }
  }
}

Measured memory_bytes: 23252
while True:
    n, x = map(int, input().split())
    if n == 0 and x == 0:
        break
    count = 0
    for i in range(1, n + 1):
        for j in range(i, n + 1):
            for k in range(j, n + 1):
                if i != j != k and x == i + j + k:
                    count += 1
    print(count)


Measured memory_bytes: 5596
#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>/*toupperとかが入っている*/
#include<vector>/*可変長配列vectorのインクルード*/

const int MOD=1000000007;/* 1,000,000,007 で割った余りを出力する　のとき使う*/
using namespace std;/*標準名前空間を利用する。cinやcoutはこれによって利用可能になる*/

int N;
int D[100005];


int main(void) {
  cin >> N;
  for(int i=0; i<N; i++){
    cin >> D[i];
  }
  
  /*大きい順にソート*/
  int n = sizeof(D)/sizeof(D[0]);
  sort(D, D+n, greater<>());

  cout << D[N/2-1]-D[N/2] << endl;
  
  return 0;
}


Measured memory_bytes: 640
l=['dream','dreamer','erase','eraser']
s=input().rstrip()
x=list(s)
if len(x)<5:
    print("NO")
elif len(x)==5:
    if ''.join(x)=='dream' or ''.join(x)=='erase':
        print("YES")
    else:
        print("NO")
elif len(x)==6:
    if ''.join(x)==l[3]:
        print("YES")
    else:
        print("NO")
elif len(x)==7:
    if ''.join(x)==l[1]:
        print("YES")
    else:
        print("NO")
else:
    i=0;
    G=0;
    while(i<len(x)):
        #print(i)
        if x[i]=='d':
            t=x[i:i+5]
            p=x[i:i+7]
            if ''.join(p)=='dreamer':
                if (i+7)<len(x) and x[i+7]!='a':
                    i+=7;
                elif (i+7+1)>len(x):
                    break;
                elif (i+7)<len(x) and x[i+7]=='a':
                    i+=5;
            elif ''.join(t)=='dream':
                i+=5;
            else:
                G=1;
                break;
        elif x[i]=='e':
            t=x[i:i+5]
            p=x[i:i+6]
            if ''.join(p)==l[3]:
                i+=6;
            elif ''.join(t)==l[2]:
                i+=5;
            else:
                G=1;
                break;
        else:
            G=1;
            break;
    if G==0:
        print("YES")
    else:
        print("NO")

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

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

    int D;
    cin >> D;

    string s = "Christmas";
    for (int i=0; i<25-D; ++i) {
        s += " Eve";
    }

    cout << s << endl;

    return 0;
}

Measured memory_bytes: 256
n, q = map(int, input().split())
queue = []
elaps = 0
for i in range(n):
    name, time = input().split()
    queue.append([name, int(time)])

while len(queue) > 0:
    u = queue.pop(0)
    c = min(q, u[1])
    u[1] -= c
    elaps += c
    if u[1] > 0:
        queue.append(u)
    else:
        print(u[0], elaps)


Measured memory_bytes: 13020
n=int(input())

dp=[[float('-inf') for i in range(n+1)] for j in range(3)]

for i in range(3):
	dp[i][0]=0

for i in range(1,n+1):
	a,b,c=map(int,input().split())
	dp[0][i]=max(a+dp[1][i-1],a+dp[2][i-1])
	dp[1][i]=max(b+dp[0][i-1],b+dp[2][i-1])
	dp[2][i]=max(c+dp[0][i-1],c+dp[1][i-1])

res=0
for i in range(3):
	res=max(res,dp[i][-1])
print(res)

Measured memory_bytes: 14984
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath> // sqrt
#define _GLIBCXX_DEBUG // check []
#define DIVISOR 1000000007

using namespace std;
typedef pair<int,int> pii;
typedef pair<int64_t, int64_t> pII;

template<typename T>
void cins(vector<T>& arr) { for(T& e: arr) cin >> e; }

#ifdef DEBUG
#define debug(fmt, ...) \
    printf("[debug: %s] " fmt, __func__, __VA_ARGS__)
#define ps(arr) \
    debug("size %ld: ", arr.size()); \
    for(auto e: arr) cout << e << " "; \
    cout << endl;
#else
#define debug(fmt, ...)
#define ps(arr)
#endif

int64_t calc_diff(vector<int>& arr) {
    vector<int> cand;
    int size = arr.size();
    for(int i = 0; i <= size/2; i++) {
        cand.push_back(arr[i]);
        if(i == size-1-i) continue;
        cand.push_back(arr[size-1-i]);
    }
    ps(cand);

    int64_t sum = 0;
    int prev = arr[0];
    for(int i = 1; i < size-1; i++) {
        int cur = cand[i];
        sum += abs(cur - prev);
        prev = cur;
    }
    int last = cand[size-1];
    sum += max(abs(last-cand[size-2]), abs(last-cand[0]));
    return sum;
}

int main(void) {
    int num;
    cin >> num;
    vector<int> arr(num);
    cins(arr);
    sort(arr.begin(), arr.end());
    int64_t sum = calc_diff(arr);
    reverse(arr.begin(), arr.end());
    sum = max(sum, calc_diff(arr));

    cout << sum << endl;
    return 0;
}

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

string reverse(string s)
{
    reverse(begin(s), end(s));
    return s;
}

bool all_zero(const string& s)
{
    for (const char c : s)
        if (c != '0')
            return false;
    return true;
}

// You have a list of pairs (a_i, b_i).
// Minimize A + B, subject to the constraint that
// for each i, either a_i <= A or b_i <= B
int f(vector<pair<int, int>> costs)
{
    if (costs.empty()) return 0;

    sort(begin(costs), end(costs));
    int x = costs.back().first, y = 0, result = x+y;
    while (!costs.empty())
    {
        y = max(y, costs.back().second);
        costs.pop_back();
        x = costs.empty() ? 0 : costs.back().first;
        result = min(result, x+y);
    }
    return result;
}

int solve(const string& A, const string& B)
{
    if (all_zero(B))
        return all_zero(A) ? 0 : -1;

    const int N = int(A.length());

    vector<int> r(N), l(N);
    for (int i = 0; i < N; i++)
    {
        for (r[i] = 0; B[(i+r[i])%N] != '1'; r[i]++) ;
        for (l[i] = 0; B[(i-l[i]+N)%N] != '1'; l[i]++) ;
    }

    int result = numeric_limits<int>::max();
    for (int shift = 0; shift < N; shift++)
    {
        int mismatches = 0;
        for (int i = 0; i < N; i++)
            mismatches += A[i] != B[(i+shift)%N];

        vector<pair<int, int>> costs;
        for (int i = 0; i < N; i++)
            if (A[i] != B[(i+shift)%N] && r[i] > shift)
                costs.push_back({l[i], r[i]-shift});

        result = min(result, shift + 2*f(costs) + mismatches);
    }
    return result;
}

int main()
{
    string A, B;
    cin >> A >> B;
    cout << min(solve(A, B), solve(reverse(A), reverse(B))) << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

//#define LOCAL 0
//#ifdef LOCAL
//#define DEBUG(s) cout << (s) << endl
//#define dump(x)  cerr << #x << " = " << (x) << endl
//#define BR cout << endl;
//#else
//#define DEBUG(s) do{}while(0)
//#define dump(x) do{}while(0)
//#define BR
//#endif


//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007
//ここから編集する


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


    while (true) {
        int n;
        cin >> n;

        if (n == 0) break;
        int ans = 0;
        rep(i, 0, 200) {
            rep(j, i, 200) {
                rep(k, j, 200) {
                    if (n >= i * i + j * j + k * k) {
                        int l = (int) sqrt(n - i * i - j * j - k * k);
                        if (n == i * i + j * j + k * k + l * l && l >= k) {
                            ans++;
                        }
                    }
                }
            }
        }
        cout << ans << endl;
    }

    return 0;
}



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


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

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


ll gcd(ll x, ll y) {
	if (y == 0) return x;
	return gcd(y, x%y);
}



int main() {

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

	VI b(n + 1, 0);
	VI c(n + 1, 0);
	FOR(i, 1, n + 1)b[i] = gcd(a[i - 1], b[i - 1]);
	for (int i = n; i > 0; i--) {
		c[i - 1] = gcd(a[i - 1], c[i]);
	}


	ll ans = 0;

	REP(i, n) {
		ans = max(gcd(b[i], c[i + 1]), ans);
	}

	cout << ans << endl;


	return 0;
}


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

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

    vector<int> x(n);
    rep(i, n)
        cin >> x.at(i);

    int s = 0;
    rep(i, n)
        s += x.at(i);

    int a = round((((double) s) / n));

    int d = 0;
    rep(i, n)
        d += (x.at(i) - a) * (x.at(i) - a);

    cout << d << endl;
}

Measured memory_bytes: 3700
//code by lynmisakura.wish to be accepted!
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
template<class T>
vector<pair<T,int>> runlength(vector<T> arr) {
    int i = 0;
    int n = arr.size();
    vector<pair<T, int>> run;
    while (i < arr.size()) {
        T t = arr[i];
        int k = 0;
        while (i + k < n && arr[i + k] == t) k++;
        run.push_back(pair<T, int>(t, k));
        i += k;
    }
    return run;
}
vector<pair<char,int>> runlength(string s){
    int i = 0;
    int n = s.size();
    vector<pair<char, int>> run;
    while (i < n) {
        char t = s[i];
        int k = 0;
        while (i + k < n && s[i + k] == t) k++;
        run.push_back(pair<char, int>(t, k));
        i += k;
    }
    return run;
}
template<class T>
int freq(vector<T> arr) {
    vector<T> vec = arr;
    int n = arr.size();
    sort(all(vec));
    int i = 0;
    vector<pair<int, T>> run;
    while (i < arr.size()) {
        T t = arr[i];
        int k = 0;
        while (i + k < n && arr[i + k] == t) k++;
        run.push_back(pair<int, T>(k, t));
        i += k;
    }
    sort(all(run));
    reverse(all(run));
    return run[0].first;
}
vector<ll> a[100010];
int main(void){
        ll n;scanf("%lld",&n);
        ll k;scanf("%lld",&k);

        ll r,s,p;scanf("%lld %lld %lld",&r,&s,&p);

        string t;cin >> t;

        for (int i = 0; i < n; ++i)
        {
            if(t[i] == 'r')a[i%k].push_back(1);
            if(t[i] == 's')a[i%k].push_back(2);
            if(t[i] == 'p')a[i%k].push_back(3);
        }

        ll ans = 0;

        for (int i = 0; i < k; ++i)
        {
            auto v = runlength(a[i]);
            for(auto j : v){
                //cout << j.second << endl;
                if(j.first == 1)ans += p * ((j.second + 1)/2);
                if(j.first == 2)ans += r * ((j.second + 1)/2);
                if(j.first == 3)ans += s * ((j.second + 1)/2);
            }
        }
        printf("%lld\n", ans);
}


Measured memory_bytes: 6580
// #Sazaの1日1AC
#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
const long long INF=9e15;
const double PI=3.14159265358979323846;

//マクロ
//型エイリアス
using ll = long long;
using P=pair<long long,long long>;
using vl=vector<long long>;
using vvl=vector<vector<long long>>;
using vP=vector<pair<long long, long long>>;
//ショートカット
#define rep(i,n) for(long long i = 0; i < n; i++)
#define rep2(i,k,n) for(long long i = k; i < n; i++) //半開区間
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define mkp make_pair
//入力
#define vin(v,N) for(long long id=0;id<N;id++) cin>>v.at(id)
#define lin(n) long long n;cin>>n
#define chin(x) char x;cin>>x;
#define sin(s) string s;cin>>s;
#define vlin(v,N) vector<long long>v(N);for(long long i=0;i<N;i++)cin>>v.at(i)

#define max(a,b) max((ll)a,(ll)b)
#define min(a,b) min((ll)a,(ll)b)

//関数
//最大公約数
long long gcd(long long m, long long n){
  long long a=max(m,n);
  long long b=min(m,n);
  long long r=a%b;
  while(r!=0){
    a=b; b=r; r=a%b;
  }
  return b;
}
// 最小公倍数
long long lcd(long long m, long long n){
  return m*n/gcd(m,n);
}
//xのn乗
long long power(long long x, long long N){
  long long ret=1;
  for(long long i=0;i<N;i++)   
    ret*=x;
  return ret;
}
//繰り返し二乗法
long long repeat_squaring(long long x, long long n){
  if(n==0) return 1;
  else if(n%2==0){
    long long t=repeat_squaring(x,n/2);
    return t*t%mod;
  }
  else
    return x*repeat_squaring(x,n-1);
}
//素因数分解(mapで返す)
map<long long,long long> factor(long long p){
  ll p1=p;
  map<long long,long long>ret;
  for(long long i=2;i*i<=p1;i++){
     while(p%i==0){
      ret[i]++;
      p/=i;
    }
  }
  if(p!=1)
  ret[p]++;
  return ret;
}
//素数判定
bool is_prime(long long N){
  for(long long i=2;i*i<=N;i++){
    if(N%i==0)
      return false;
  }
  return true;
}
//最大値更新
void chmax(long long &a,long long b){
  a=max(a,b);
}
//最小値更新
void chmin(long long &a,long long b){
  a=min(a,b);
}

//構造体

/////////////////⊂('ω'⊂ )))Σ≡GO!/////////////////


//メイン関数
int main(){
  //doubleの桁数
  cout<<fixed<<setprecision(10);
  
  lin(A);lin(B);lin(H);lin(M);
  double theta = (60.0 * H + M) / 2.0;
  double phy = 6.0 * M;
  cout << sqrt(A*A + B*B - 2*A*B*cos((theta - phy) / 360 * 2 * PI)) << endl;
  //cout << A*A << " " << B*B <<" "<< 2*A*B*cos((theta - phy) / 360 * 2 * PI) << endl;
}

Measured memory_bytes: 4232
#include <bits/stdc++.h>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define sd(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define met(a,b); memset(a,b,sizeof(a));
typedef long long ll;
using namespace std;
double pai=3.141592653589793;
 
// inline int read()
// {
//     int x=0,f=1;
//     char ch=getchar();
//     while(ch<'0'||ch>'9')
//     {
//         if(ch=='-')
//             f=-1;
//         ch=getchar();
//     }
//     while(ch>='0'&&ch<='9')
//     {
//         x=(x<<1)+(x<<3)+(ch^48);
//         ch=getchar();
//     }
//     return x*f;
// }
 
inline long long read() {
    long long tmp=0, fh=1; char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') fh=-1; c=getchar();}
    while (c>='0'&&c<='9') tmp=tmp*10+c-48, c=getchar();
    return tmp*fh;
}
struct  nod
{
    /* data */
    ll x,w;
};
struct nn{
    long long x,h;
};
bool cmm(nn a,nn b)
{
    return a.x<b.x;
}
nn t[200005];
int main(){
    ll n,d,a;
    cin>>n>>d>>a;
    d=d+d;
    for(int i=0;i<n;i++)
    {
        t[i].x=read();
        t[i].h=read();
    }
    sort(t,t+n,cmm);
    queue<nod> qu;
    ll end=0,ans=0;
    for(int i=0;i<n;i++)
    {
        while(!qu.empty())
        {
            nod temp=qu.front();
            if(temp.x>=t[i].x) break;
            else
            {
                end-=temp.w;
                qu.pop();
            }
        }
        if(end<t[i].h)
        {
            ll k,p=t[i].h-end;
            k=p/a;
            if(p%a) k++;
            end+=k*a;
            ans+=k;
            nod temp;
            temp.x=t[i].x+d;
            temp.w=k*a;
            qu.push(temp);
        }
    }
    cout<<ans;
}

Measured memory_bytes: 4992
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

#include <limits.h>

using namespace std;

typedef long long ll;

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

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

vector<int> ps;
vector<int> qs;
vector<int> rs;

vector<int> cands;

int main(void) {
    int X, Y, A, B, C;
    cin >> X >> Y >> A >> B >> C;

    ps.resize(A);
    for (int i = 0; i < A; i++) {
        cin >> ps[i];
    }
    sort(ps.begin(), ps.end());
    reverse(ps.begin(), ps.end());

    qs.resize(B);
    for (int i = 0; i < B; i++) {
        cin >> qs[i];
    }
    sort(qs.begin(), qs.end());
    reverse(qs.begin(), qs.end());

    rs.resize(C);
    for (int i = 0; i < C; i++) {
        cin >> rs[i];
    }
    // don't have to sort rs here

    for (int i = 0; i < X; i++) {
        cands.push_back(ps[i]);
    }
    for (int i = 0; i < Y; i++) {
        cands.push_back(qs[i]);
    }
    for (int i = 0; i < C; i++) {
        cands.push_back(rs[i]);
    }
    sort(cands.begin(), cands.end());
    reverse(cands.begin(), cands.end());

    ll ans = 0;
    for (int i = 0; i < X + Y; i++) {
        ans += cands[i];
    }

    cout << ans << endl;

    return 0;
}


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

int main() {
  int N;
  cin >> N;
  int num = INT_MAX;
  for (int i=0; i<N; i++) {
    int A;
    cin >> A;
    int j=0;
    while (A % 2 == 0){
      A /= 2;
      j++;
    }
    if (num > j) {
      num = j;
    }
  }
  cout << num << endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL <<60;
const long long Mo=1000000007;
     
long long gcn(long long x,long long y){
  if(x%y==0){
    return y;  
  }
  else{
    return gcn(y,x%y);
  }
}
int main(void){
  long long tmp;
  long long n;
  long long i,j,k;
  long long x[200000]={},y[200000]={};
  long long lmin,lmax,mmin,mmax;
  long res=0;

  cin>>n;
  lmin=INF;
  mmin=INF;
  lmax=-INF;
  mmax=-INF;

  for(i=0;i<n;i++){
    cin>>x[i]>>y[i];
    lmin=min(lmin,x[i]+y[i]);
    lmax=max(lmax,x[i]+y[i]);
    mmin=min(mmin,x[i]-y[i]);
    mmax=max(mmax,x[i]-y[i]);
  }

  res=max(lmax-lmin,mmax-mmin);
  
  cout<<res<<endl;
  return 0;
}

Measured memory_bytes: 6576
console.log((args=>{
  const [K,A,B] = args.trim().split(' ').map(v=>v|0);
  if ( B <= A + 2 || K < A ) return `${1+K}`;
  const d = BigInt(B-A);
  const c = BigInt(K-A+1>>1)-1n;
  const l = BigInt(!(K-A&1)+B);
  return `${d * c + l}`;
})(require('fs').readFileSync('/dev/stdin', 'utf8')));


Measured memory_bytes: 29580
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

struct CumulativeSum{
    vector<int> data;
    CumulativeSum(int sz) : data(sz, 0) {};
    void add(int k, int x){
        data[k] += x;
    }
    void build(){
        for(int i = 1; i < data.size(); i++){
            data[i] += data[i - 1];
        }
    }
    int query(int k){
        if(k < 0) return 0;
        return (data[min(k, (int)data.size() - 1)]);
    }
    int query(int l, int r){
        return query(r - 1) - query(l - 1);
    }
};

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> l(n);
    CumulativeSum s(1001);
    for(int i = 0; i < n; i++){
        cin >> l[i];
        s.add(l[i], 1);
    }
    s.build();
    sort(l.begin(), l.end());
    int ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            int MIN = abs(l[i] - l[j]);
            int MAX = l[i] + l[j];
            int tmp = s.query(MIN + 1, MAX);
            if(MIN < l[i] && l[i] < MAX) tmp--;
            if(MIN < l[j] && l[j] < MAX) tmp--;
            // cout << l[i] << " " << l[j] << " " << tmp << endl;
            ans += tmp;
        }
    }
    cout << ans / 3 << endl;
}

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

typedef long long ll;

const ll MOD = 1e9 + 7;
const ll INF = 1ll << 60;
ll N, M, S, T;
vector<vector<pair<ll, ll>>> DOut;
vector<ll> Dist;
vector<bool> RSeen;
vector<vector<ll>> Out, In;
vector<ll> Order;
vector<ll> Count, RCount;

void dijkstra() {
  Dist.resize(N, INF);
  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>
      pool;
  pool.push(make_pair(0, S));
  while (!pool.empty()) {
    auto distv = pool.top();
    pool.pop();
    ll dist = distv.first, v = distv.second;
    if (dist >= Dist[v]) continue;
    Dist[v] = dist;
    for (auto wd : DOut[v]) {
      ll w = wd.first, d = wd.second;
      if (Dist[w] > Dist[v] + d) pool.push(make_pair(Dist[v] + d, w));
    }
  }
}
void rsee(ll v) {
  if (RSeen[v]) return;
  RSeen[v] = true;
  for (ll w : In[v]) rsee(w);
  Order.push_back(v);
}
void prune() {
  Out.resize(N);
  In.resize(N);
  for (ll v = 0; v < N; ++v) {
    for (auto wd : DOut[v]) {
      ll w = wd.first, d = wd.second;
      if (Dist[w] == Dist[v] + d) {
        Out[v].push_back(w);
        In[w].push_back(v);
      }
    }
  }
  RSeen.resize(N);
  rsee(T);
  assert(Order.front() == S && Order.back() == T);
  for (ll v = 0; v < N; ++v) {
    vector<ll> new_out, new_in;
    if (RSeen[v]) {
      for (ll w : Out[v])
        if (RSeen[w]) new_out.push_back(w);
      for (ll w : In[v])
        if (RSeen[w]) new_in.push_back(w);
    }
    Out[v] = new_out;
    In[v] = new_in;
  }
}
ll solve() {
  Count.resize(N);
  Count[S] = 1;
  for (ll v : Order) {
    for (ll w : Out[v]) {
      (Count[w] += Count[v]) %= MOD;
    }
  }
  RCount.resize(N);
  RCount[T] = 1;
  reverse(Order.begin(), Order.end());
  for (ll v : Order) {
    for (ll w : In[v]) {
      (RCount[w] += RCount[v]) %= MOD;
    }
  }
  ll dup_count = 0;
  for (ll v : Order) {
    if (Dist[v] * 2 == Dist[T])
      (dup_count +=
       Count[v] * Count[v] % MOD * RCount[v] % MOD * RCount[v] % MOD) %= MOD;
    for (ll w : Out[v]) {
      if (Dist[v] * 2 < Dist[T] && Dist[T] < Dist[w] * 2)
        (dup_count +=
         Count[v] * Count[v] % MOD * RCount[w] % MOD * RCount[w] % MOD) %= MOD;
    }
  }
  return (Count[T] * Count[T] % MOD + MOD - dup_count % MOD) % MOD;
}
int main() {
  cin >> N >> M >> S >> T;
  --S;
  --T;
  DOut.resize(N);
  for (ll i = 0; i < M; ++i) {
    ll u, v, d;
    cin >> u >> v >> d;
    --u;
    --v;
    DOut[u].push_back(make_pair(v, d));
    DOut[v].push_back(make_pair(u, d));
  }
  dijkstra();
  prune();
  cout << solve() << endl;
  return 0;
}


Measured memory_bytes: 31132
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <string.h>
 
using namespace std;
typedef long long ll;
 
int main()
{
	ll H;
	scanf("%lld", &H);
	
	ll count = 0;
	while( H > 0){
		if( H == 1){
			H = 0;
		}
		else{
			H = H / 2;
		}
		count++;
	}
	
	ll ans = 1;
	for(int i = 0; i < count; i++){
		ans *= 2;
	}
	ans --;
	
	printf("%lld\n", ans);
	
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <math.h>

int main() {
  int n,i,j,l;
  double s[10020];
  double a2,m,a;
  
  while(1) {
    m=0;
    a2 = 0;
    scanf("%d" , &n);
    if(n == 0) {
      break;
    }

    for(i=0;i<n;i++) {
      scanf("%lf", &s[i]);
	m=m+s[i];
	//printf("m[%d] = %lf\n",i ,m);
    }
    m=m/n;

    for(i=0; i<n; i++) {
      a2 =a2+(s[i]-m)*(s[i]-m);
    }
    a2 = a2/n;

    printf("%.11lf\n",sqrt(a2));

  }

  return 0;

}


Measured memory_bytes: 2048
def main():
    N,K,S = map(int,input().split())
    mx = 10**9
    if S < 10**5:
        Ans = [S]*K + [mx]*(N-K)
        print(*Ans,sep=" ")
        return 
    else:
        Ans = [S]*K + [1]*(N-K)
        print(*Ans,sep=" ")        
        return

if __name__ == "__main__":
    main()

Measured memory_bytes: 6652
#include<stdio.h>
int main()
{
    int a,b;
    int m,c;
    while(scanf("%d %d",&a,&b)!=EOF){
        m=a+b;
        c=0;
        for(;;){
            c++;
            if((m/=10)==0)break;
        }
        printf("%d\n",c);
    }
    return 0;
}

Measured memory_bytes: 2680
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
#include<random>
#include<chrono>
#include<bitset>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair

#ifndef ONLINE_JUDGE
#  define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
#  define LOG(x) ((void)0)
#endif

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const double PI=acos(-1);
const ll INF = 1LL<<62;
const ll MINF = -(1LL<<62);

template<typename T> T getint() {
	T val=0;
	char c;
	
	bool neg=false;
	while((c=gc()) && !(c>='0' && c<='9')) {
		neg|=c=='-';
	}

	do {
		val=(val*10)+c-'0';
	} while((c=gc()) && (c>='0' && c<='9'));

	return val*(neg?-1:1);
}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int>(0, n-1)(rng)


int main() {
	IO;
	ll a;
	cin>>a;
	string b;
	cin>>b;
	ll bb=0;
	for(auto i:b) {
		if(i!='.') bb=(10*bb+i-'0');
	}
	cout<<(a*bb/100LL)<<"\n";
	return 0;
}


Measured memory_bytes: 3624
var n, m;
var a = [], b = [];

function search(x){
	var l = 0, r = m;
	while(r - l > 1){
		var c = (l + r) >> 1;
		if(b[c] <= x){
			l = c;
		}
		else{
			r = c;
		}
	}
	return b[l] === x;
}

function main(){
	while(n = scan()){
		m = scan();
		rep(n, function(i){
			a[i] = scan();
		});
		rep(m, function(i){
			b[i] = scan();
		});

		a.sort(function(u, v){
			return u - v;
		});
		b.sort(function(u, v){
			return u - v;
		});

		var s = 0;
		rep(n, function(i){
			s += a[i];
		});
		var t = 0;
		rep(m, function(i){
			t += b[i];
		});

		var d = Math.floor((t - s) / 2);
		if(t - s !== 2 * d){
			print(-1);
		}
		else{
			var ans = false;
			rep(n, function(i){
				if(search(a[i] + d)){
					print(a[i] + ' ' + (a[i] + d));
					ans = true;
					return false;
				}
			});
			if(!ans){
				print(-1);
			}
		}

		a = [];
		b = [];
	}
}

function rep(a, b, c){
	if(c === undefined){
		c = b;
		b = a;
		a = 0;
	}
	for(var i = a; i < b; ++i){
		if(c(i) === false){
			break;
		}
	}
}

var input = '';

function scan(){
	return +input.pop();
}
function scan_string(){
	return input.pop();
} 
function print(val){
	console.log(val);
}
 
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function(chunk){
	input += chunk;
});
process.stdin.on('end', function(){
	input = input.trim().split(/\s+/).reverse();
	main();
});

Measured memory_bytes: 16028
#include<bits/stdc++.h>
using namespace std;
int main(){
  while(1){
        int m,n1,n2,ans,max=0,s,p;
        int a[10000];
        cin >> m >> n1 >> n2;
        if(m==0 && n1==0 && n2==0) break;
        for(int i=0; i<m; i++){
          cin >> p;
          a[i] = p;
        }
        for(int i=n1; i<=n2; i++){
          s = a[i-1] - a[i];
          if(s >= max) {
                ans = i;
                max = s;
          }
        }
        cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 3092
fn get_line() -> String {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    line.trim().to_string()
}

fn main() {
    let s = get_line().chars().collect::<Vec<char>>();
    if s[2] == s[3] && s[4] == s[5] {
        println!("Yes");
    } else {
        println!("No");
    }
}


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


int main() {
  long long N;
  cin >> N;
  long long ans = 1;
  vector<pair<long long,long long>> vec(N);
  for (long long i = 0;i < N;i++) {
    long long a,b;
    cin >> a >> b;
    pair<long long,long long> p;
    p = make_pair(a-b,a+b);
    vec.at(i) = p;
  }
  sort(vec.begin(),vec.end());
  
  long long f = vec.at(0).first;
  long long s = vec.at(0).second;
  
  for (long long i = 1;i < N;i++) {
    if (s <= vec.at(i).first) {
      f = vec.at(i).first;
      s = vec.at(i).second;
      ans++;
    }
    else if (s >= vec.at(i).second) {
      f = vec.at(i).first;
      s = vec.at(i).second;
    }
  }

  cout << ans << endl;
}
    
    
    
  
  
  
  




Measured memory_bytes: 1792
//Let's join Kaede Takagaki Fan Club !!
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define all(x) x.begin(),x.end()
template<class T>
void dmp(T a){
	rep(i,a.size()) cout << a[i] << " ";
	cout << endl;
}
template<class T>
bool chmax(T&a, T b){
	if(a < b){
		a = b;
		return 1;
	}
	return 0;
}
template<class T>
bool chmin(T&a, T b){
	if(a > b){
		a = b;
		return 1;
	}
	return 0;
}
template<class T>
void g(T &a){
	cin >> a;
}
template<class T>
void o(const T &a,bool space=false){
	cout << a << (space?' ':'\n');
}
//ios::sync_with_stdio(false);
const ll mod = 1000000007;//998244353
template<class T>
void add(T&a,T b){
	a+=b;
	if(a >= mod) a-=mod;
}
char str[200005];
int n;
ll cnt[2019], t = 1, cur;
int main(){
	scanf("%s", &str); n = strlen(str);
	cnt[0] = 1;
	ll ans = 0;
	for(int i=n-1;i>=0;i--){
		cur += t * (str[i]-'0');
		cur %= 2019LL;
		t = t*10%2019LL;
		ans += cnt[cur]++;
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 3908
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<cstring>
using namespace std;
int com[1000008];
char s[20];
void out()
{
    int sum=0,i;
   for( i =0;s[i]!='\0';i++)
    sum+=(s[i]-48);
   cout<<sum<<endl;
}
int main()
{

    while(cin>>s)
    {

        int n=strlen(s),k=0,j,sum1=0;
        for(int i=0; i<n; i++)
            sum1+=s[i]-48;
        if(sum1==(n-1)*9+(s[0]-49))
        {
           out();
            continue;
        }
        for(int i=1; i<n; i++)
        {
            if(s[i]!='9'&&!k)
            {
                s[i-1]--;
                k=1;
            }
            if(k)
                s[i]='9';
        }
      out();
       memset(s,0,sizeof(s));
    }
    return 0;
}


Measured memory_bytes: 256
# include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int N = 100005;
# define INF 1000000001
# define MOD 1000000007
# define pb push_back
# define mp make_pair
typedef pair<int, int> Pi;

struct Node{
    int l, r;
}node[N];

bool comp(Node a, Node b) {
    return a.r < b.r;
}
int main ()
{
    int n;
    i64 x, l;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld%lld", &x, &l);
        node[i].l = x - l;
        node[i].r = x + l;
    }
    sort(node + 1, node + n + 1, comp);
    int ans = 0;
    i64 tmp = -INF;
    for (int i = 1; i <= n; ++i) {
        if (node[i].l >= tmp) tmp = node[i].r, ++ans;
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 1024
{-# LANGUAGE FlexibleContexts #-}
import Control.Applicative
import Control.Monad
import Data.Array
import Data.Bits
import Data.Int
import qualified Data.IntMap.Lazy as IntMap
import qualified Data.IntSet as IntSet
import Data.List
import qualified Data.Map.Lazy as Map
import Data.Maybe
import Data.Ord
import qualified Data.Sequence as Seq
import Data.Tuple

-- contests.hs --- Contests

-- author: Seong Yong-ju <sei40kr@gmail.com>

main :: IO ()
main = do
  n <- (readLn :: Read String => IO Int)
  [a, b] <- map (read :: String -> Int) . words <$> getLine
  ps <- map (read :: String -> Int) . take n . words <$> getLine
  print $ let
    class_a = length $ filter (<= a) ps
    class_b = length $ filter (> a) $ filter (<= b) ps
    class_c = length $ filter (> b) ps in
    class_a `min` class_b `min` class_c


Measured memory_bytes: 1020
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

int calc(string s) {
    int n = cast(int)s.length;
    int[] ws = new int[s.length]; // [0, i] の白の個数
    for (int i = 0; i < s.length; i++) {
        if (s[i] == '.') ws[i]++;
        if (i > 0) ws[i] += ws[i-1];
    }

    // [l, r] の白の個数
    int countW(int l, int r) {
        return ws[r] - (l > 0 ? ws[l-1] : 0);
    }
    // [l, r] の黒の個数
    int countB(int l, int r) {
        return (r - l + 1) - countW(l, r);
    }
    int ans = countW(0, n-1); // 全ての白を黒にするコスト
    for (int i = 0; i < n; i++) {
        // [0, i] を白、[i+1, n-1] を黒にするコスト
        int b = countB(0, i);
        int w = i == n - 1 ? 0 : countW(i + 1, n - 1);
        ans = min(ans, b + w);
    }
    return ans;
}

void main() {
    readint;
    string s = read!string;
    int ans = calc(s);
    writeln(ans);
}


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

string n;
int k;
int len;
long long com(long long a, long long b) {
  if (b == 0) {
    return 1;
  }
  if (a == 0) {
    if (b == 1) {
      return 1;
    } else {
      return 0;
    }
  }
  long long ret = 1;
  for (int i=a; i>a-b; i--) {
    ret *= i;
  }
  for (int i=b; i>0; i--) {
    ret /= i;
  }
  return ret;
}
long long f(int num, int idx, int cnt_not_0) {
  if (cnt_not_0 > k) {
    return 0;
  }
  if (idx == len - 1) {
    if (cnt_not_0 == k && num <= n[idx] - '0') {
      return 1;
    } else {
      return 0;
    }
  }
  if (num > n[idx] - '0') {
    return 0;
  }
  if (num < n[idx] - '0') {
    return com(len - idx - 1, k - cnt_not_0) * pow(9, k - cnt_not_0);
  }
  long long ret = f(0, idx + 1, cnt_not_0);
  for (int i=1; i<=9; i++) {
    // printf("num: %d, idx %d, cnt_not_0: %d, i: %d\n", num, idx, cnt_not_0, i);
    // cout<<ret<<endl;
    ret += f(i, idx + 1, cnt_not_0 + 1);
    // cout<<ret<<endl;
  }
  return ret;
}

int main() {
  cin>>n;
  cin>>k;
  len = n.length();
  long long ans = 0;
  long long tmp = pow(9, k);
  for (int i=k; i<len; i++) {
    ans += tmp * com(i - 1, k - 1);
  }
  for (int i=1; i<=9; i++) {
    ans += f(i, 0, 1);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
ans=0
for i in range(N):
    if A[i]<=B[i]:
        ans+=A[i]
        B[i]-=A[i]
        if A[i+1]<=B[i]:
            ans+=A[i+1]
            A[i+1]=0
        else:
            ans+=B[i]
            A[i+1]-=B[i]
    else:
        ans+=B[i]
print(ans)

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

using ll = long long;
using namespace std;
const int INFint = 2e9+1;
const ll INFll = 2e18+1;
ll MOD=1e9+7;


int main(){
  int N;
  cin>>N;
  ll ans(1);
  for(int i(1);i<=N;i++){
    ans *= i;
    ans %= MOD;
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder
{
    class Program
    {
        static void Main()
        {
            Solve();

            Console.ReadKey();
        }

        static void Solve()
        {
            var N = IO.GetInt();
            var pairs = new Pair[N];
            for(int i=0 ; i < N; i++)
            {
                pairs[i] = new Pair();
                var str = IO.GetStringList();
                pairs[i].i = i;
                pairs[i].S = str[0];
                pairs[i].P = int.Parse(str[1]);
            }
            pairs = pairs.OrderBy(p => p.S).ThenByDescending(p => p.P).ToArray();
            for(int i = 0; i < N; i++)
            {
                Console.WriteLine(pairs[i].i+1);
            }

            //Console.Write(ans);
        }
    }

    class Pair
    {
        public int i { get; set; }
        public string S { get; set; }
        public int P { get; set; }

    }

    static class IO
    {
        static public string GetString() { return Console.ReadLine(); }
        static public int GetInt() { return int.Parse(Console.ReadLine()); }
        static public long GetLong() { return long.Parse(Console.ReadLine()); }
        static public List<string> GetStringList() { return Console.ReadLine().Split(' ').ToList(); }
        static public List<int> GetIntList() { return Console.ReadLine().Split(' ').Select(int.Parse).ToList(); }
        static public List<long> GetLongList() { return Console.ReadLine().Split(' ').Select(long.Parse).ToList(); }
        static public List<double> GetDoubleList() { return Console.ReadLine().Split(' ').Select(double.Parse).ToList(); }
        static public void WriteStrings<T>(IEnumerable<T> values) { foreach (var o in values) { Console.Write(o + " "); } }
    }
}

Measured memory_bytes: 13660
#include <iostream>
#include <cstdlib>
#include <map>
using namespace std;

int main()
{
	long long int N,a = 0,b = 0;
	map<int,int>mp;

	cin >> N;

	for (int i = 0; i < N; i++) {
		int m;
		cin >> m;
		mp[m]++;
		if (mp[m] % 2 == 0) {
			int k = 0;
			abs(m + a) < abs(m + b) ? k = 1 : k = 2;
			if (k == 1 && m > a)a = m;
			if (k == 2 && m > b)b = m;
		}
	}

	cout << a*b;

	return 0;
}

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

using namespace std;

#define lli long long int

int main()
{
    lli n,k;
    cin>>n>>k;
    lli h[n+10],dp[n+10];
    for(int i=0;i<n;i++)
    {
        cin>>h[i];
        dp[i]=1000000000000;
    }
    dp[0]=0;
    for(int i=1;i<n;i++)
    {
        int limit=i-k;
        for(int j=i-1;j>=0 and j>=limit;j--)
        {
            dp[i]=min(dp[i],dp[j]+abs(h[i]-h[j]));
        }
    }
    cout<<dp[n-1]<<endl;
    return 0;
}


Measured memory_bytes: 1792