akhauriyash/Code-Regression huggingface dataset:
fn solve() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n: usize = sc.read();
    let mut lr: Vec<(i64, i64)> = (0..n)
        .map(|_| {
            let x: i64 = sc.read();
            let l: i64 = sc.read();
            (x - l, x + l)
        })
        .collect();
    lr.sort_by(|x, y| x.1.cmp(&y.1));
    // println!("{:?}", lr);
    let mut right = lr[0].1;

    let mut result = 1;
    for &(l, r) in lr.iter().skip(1) {
        if right <= l {
            right = r;
            result += 1;
        }
    }
    println!("{}", result);
}

fn main() {
    std::thread::Builder::new()
        .stack_size(64 * 1024 * 1024) // 64MB
        .spawn(|| solve())
        .unwrap()
        .join()
        .unwrap();
}

//snippet from kenkoooo
pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn read_line(&mut self) -> String {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b'\n' || b == b'\r')
            .take_while(|&b| b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 10620
#include<bits/stdc++.h>
#define rep(i,n) for (long long i = 0; i < (n); ++i)
//g++ -std=c++11 

using namespace std;

long long N, K;
long long A[200005];
long long memo[200005];

int main(){
	cin >> N >> K;
	rep(i, N) {
		cin >> A[i];
		A[i]--;
	}

	rep(i, N) {
		memo[i+1] = memo[i] + A[i];
		memo[i+1] %= K;
	}

	//num, count
	map<long long, long long> memocount;

	long long ans = 0;
	//iが右端になる
	rep(i, N) {
		memocount[memo[i]]++;
		if(i >= K-1) {
			memocount[memo[i - (K -1)]]--;
		}
		ans += memocount[memo[i+1]];
	}
	cout << ans << endl;
}


Measured memory_bytes: 19244
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	A, B, M = getlist()
	a = getlist()
	b = getlist()
	am = min(a)
	bm = min(b)
	ans = am + bm
	for i in range(M):
		x, y, c = getlist()
		ans = min(ans, a[x - 1] + b[y - 1] - c)

	print(ans)
	


if __name__ == '__main__':
	main()

Measured memory_bytes: 61908
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <cassert>
using namespace std;

int main(){
    string S;
    string T;
    cin >> S >> T;
    int ans = 0;
    for(int i=0; i<3; i++)
        ans += (S[i] == T[i]);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int n;
  cin >>n;
  int b[n];
  deque <int> c;
  
  if(n%2==0){
    for (int i=0;i<n;i++){
    cin>>b[i];
    if(i%2==0){
      c.push_back(b[i]);
    }
    else c.push_front(b[i]);
    }
  }
  if(n%2==1){
    for (int i=0;i<n;i++){
    cin>>b[i];
    if(i%2==0){
      c.push_front(b[i]);
    }
    else c.push_back(b[i]);
    }
  } 
  for(int i=0;i<n-1;i++){
    cout<<c.at(i)<<" ";
  }
  cout<<c.at(n-1)<<endl;
  return 0;
}


Measured memory_bytes: 3840
// #pragma GCC optimize ("O3")
// #pragma GCC target ("sse4")

#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;
const int NINF = -1*INF;
const long long LLINF = 1ll << 60;
const long long LLNINF = -1*LLINF;

template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ";
    return os << "}";
}

template <class X, class Y>
ostream & operator << (ostream & os, pair <X, Y> const& p) {
	return os << "[ " << p.first << ", " << p.second << "]" ;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<ld> vld;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vector<int>> vvi;
typedef vector<vll> vvll;
typedef vector<vd> vvd;
typedef vector<vld> vvld;
 
#define mp make_pair
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()
#define revAll(x) x.rbegin(), x.rend()
#define gcd(a, b) __gcd(a, b)
#define popcount(x) __builtin_popcount(x)
#define isize(x) (int)(x.size())
#define rep(i,n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define umap unordered_map

const ll MOD = 1e9 + 7;

// points type 0, queries type 1
struct Event{
	int type, start, end, val;

	Event(int t, int s, int e, int v){
		type = t, start = s, end = e, val = v;
	}

	bool operator<(const Event& other){
		return mp(end, type) < mp(other.end, other.type);
	}

};

inline int lastbit(int x) {
  return x & (-x);
}

template <int... ArgsT> struct BIT {
  int val = 0;
  void update(int val) {
    this->val += val;
  }
  int query() {
    return val;
  }
};

template <int N, int... Ns>
struct BIT<N, Ns...> {
  BIT<Ns...> bit[N + 1];
  template<typename... Args>
  void update(int pos, Args... args) {
  	pos++;
    for (; pos <= N; bit[pos].update(args...), pos += lastbit(pos));
  }
  template<typename... Args>
  int query(int l, int r, Args... args) {
    int ans = 0; l++; r++;
    for (; r >= 1; ans += bit[r].query(args...), r -= lastbit(r));
    for (--l; l >= 1; ans -= bit[l].query(args...), l -= lastbit(l));
    return ans;
  }
};

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	int n, q; cin >> n >> q;
	vector<Event> events = vector<Event>();
	vi ans = vi(q);
	rep(i, n){
		int x; cin >> x;
		events.pb(Event(0, i, i, x));
	}
	rep(orig_index, q){
		int l, r; cin >> l >> r;
		l--, r--;
		events.pb(Event(1, l, r, orig_index));
	}
	sort(all(events));
	BIT<5*100000+100> bit;
	map<int, int> last = map<int, int>();
	for(const Event& event : events){
		if (event.type == 0){
			if (last.find(event.val) != last.end()){
				bit.update(last[event.val], -1);
			}
			last[event.val] = event.start;
			bit.update(event.start, 1);
		}else{
			int cnt = bit.query(event.start, event.end);
			ans[event.val] = cnt;
		}
	}
	rep(i, isize(ans)){
		cout << ans[i] << "\n";
	}
}

Measured memory_bytes: 46828
import sys
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

input = sys.stdin.readline

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _dbg(obj):
    print(obj, file=sys.stderr)

# ---------------------------------------

N, K = inpl()
h = inpl()

INF = 10**10

dp = [INF] * N
dp[0] = 0

for j in range(1, N):
    for step in range(1, min(K, j)+1):
        dp[j] = min(dp[j], dp[j-step] + abs(h[j] - h[j-step]))
    _dbg(dp[1])

print(dp[N-1])

Measured memory_bytes: 86360
import itertools
import math

N = int(input())
point_list = []
for i in range(N):
    point = list(map(int, input().split()))
    point_list.append(point)

point_index = list(range(N))

p = list(itertools.permutations(point_index))

total = 0
for lst in p:
    for i in range(N-1):
        distance = math.sqrt((point_list[lst[i]][0] - point_list[lst[i+1]][0])**2 + (point_list[lst[i]][1] - point_list[lst[i+1]][1])**2)
        total += distance

print(total / math.factorial(N))

Measured memory_bytes: 7972
#include<bits/stdc++.h>
using namespace std;
#define ios ios_base::sync_with_stdio(0);cin.tie(0)
#define scn(n) scanf("%d",&n)
#define lscn(n) scanf("%lld",&n)
typedef long long ll;
#define pri(n) printf("%d\n",n)
#define lpri(n) printf("%lld\n",n);
#define rep(i,st,ed) for(int i=st;i<ed;i++)
#define F first
#define S second 
#define pb(n) push_back(n)
const int N=1e5+6;
const ll M=1e9+7;
vector<int> g[N];

int main()
{
	int h,w;
	scn(h);scn(w);
	ll dp[h][w];
	for(int i=0;i<h;i++)
	{
		string s;
		cin>>s;
		for(int j=0;j<w;j++)
			if(s[j]=='#')
				dp[i][j]=-1;
			else dp[i][j]=0;
	}
	if(dp[0][0]==-1)
		pri(0);
	else
	{
		dp[0][0]=1;
		for(int i=1;i<w;i++)
			if(dp[0][i]!=-1)
				dp[0][i]=1;
			else break;

		for(int i=1;i<h;i++)
			if(dp[i][0]!=-1)
				dp[i][0]=1;
			else break;

		for(int i=1;i<h;i++)
		{
			for(int j=1;j<w;j++)
			{
				if(dp[i][j]==-1)
					continue;
				if(dp[i-1][j]!=-1)
					dp[i][j]+=dp[i-1][j];
				if(dp[i][j-1]!=-1)
					dp[i][j]+=dp[i][j-1];

				dp[i][j]%=M;
			}
		}
		// for(int i=0;i<h;i++)
		// {
		// 	for(int j=0;j<w;j++)
		// 		printf("%lld\t",dp[i][j]);
		// 	printf("\n");
		// }
		lpri(dp[h-1][w-1]);
	}
}

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

#define INF 1000000007
#define ll long long
#define F first
#define S second
#define pii pair<ll int,ll int>
#define pb push_back
#define ppb pop_back
#define vi vector<ll int>

bool check(string s,int i,int j){
	int z=0;
	for(int k=i;k<=j;k++){

		if(s[k] != s[j-z]) return false;
		z++;
	}
	return true;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t=1;
	//cin >> t;
	while(t--){
		string s;
		int n;
		cin >> s;
		n = s.size();
		// if(check(s,0,n-1)) cout <<"dfedf1";
		// if(check(s,0,((n-1)/2)-1)) cout <<"dfedf2";
		// if(check(s,((n+3)/2)-1,n-1)) cout <<"dfedf3";
		if(check(s,0,n-1) && check(s,0,((n-1)/2)-1) && check(s,((n+3)/2)-1,n-1)) cout << "Yes";
		else cout << "No";
	}
	return 0;
}


Measured memory_bytes: 256
#include <cstring>
#include <sstream>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <set>
#include <numeric>
#include <stack>

using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto i:mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll half_inf = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);
typedef unordered_map<ll, ll> mpll;
typedef unordered_map<char, ll> mpcl;
typedef unordered_map<string, ll> mpsl;
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
template<typename T> using PQ = priority_queue<T>;
template<typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

ll inl() {
    ll x;
    cin >> x;
    return (x);
}

string ins() {
    string x;
    cin >> x;
    return (x);
}

int main() {
#ifdef MY_DEBUG
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wmissing-noreturn"
    while (true) {
#pragma clang diagnostic pop
#endif
        ll n, m;
        cin >> n >> m;
        vl a(m);
        vector<bool> out(n + 1, false);
        rep(i, m) {
            cin >> a[i];
            out[a[i]] = true;
        }
        vl dp(n + 1, 0);
        dp[0] = 1;

        for (int i = 1; i <= n; ++i) {
            if (!out[i - 1]) {
                dp[i] += dp[i - 1];
                dp[i] %= mod;
            }
            if (i >= 2 && !out[i - 2]) {
                dp[i] += dp[i - 2];
                dp[i] %= mod;
            }
        }
        cout << dp[n] << endl;


#ifdef MY_DEBUG
    }
#endif
    return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

int main(void){

    char w[128];

    scanf("%s", w);

    int c['z'-'a'+1] = {0};

    int len = strlen(w);

    for(int i = 0; i < len; i++){
        c[w[i]-'a']++;
    }

    int f = 0;

    for(int i = 0; i < 'z'-'a'+1; i++){
        if(c[i] % 2 == 1){
            f = 1;
            break;
        }
    }

    if(f == 0){
        printf("Yes\n");
    }else{
        printf("No\n");
    }

    return 0;
}

Measured memory_bytes: 1664
#define _USE_MATH_DEFINES

#include "bits/stdc++.h"
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

#define LL long long

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rrep(i,n) for(ll i = 1; i <= (n); ++i)
#define drep(i,n) for(ll i = (n)-1; i >= 0; --i)
#define all(v) v.begin(),v.end()
#define len(x) (ll)(x).length()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (ll)(x).size()
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
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/gcd(a,b)*b;}
const int INF=1e9;
const ll MX = 1e18;
const ll MOD=INF+7;
const int di[] = {-1,0,1,0};
const int dj[] = {0,-1,0,1};
const double PI=acos(-1);
const string tr="abcdefghijklmnopqrstuvwxyz";
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
#define YN {puts("YES");}else{puts("NO");}
const ll MAX = 1000001;
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {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;}}
long long COM(ll n, ll k){if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;}
ll llpow(ll n,ll i){ll cnt=n;  for(ll j=0;j<i-1;j++){n*=cnt;}return n;}
bool ip/*is_prime*/(long long N) {if (N == 1) return false;for (long long i = 2; i * i <= N; ++i) {if (N % i == 0) return false;}return true;}
int digit(ll N) {int ans = 0;while (N) {++ans;N /= 10;}return ans;}
vector<pair<ll,ll>> pf/*prime_factorize*/(ll n){vector<pair<ll,ll>> res;for(ll a=2;a*a<=n;a++){if(n%a!=0) continue;ll ex=0;while(n%a==0){ex++;n/=a;}res.pb({a,ex});}if(n!=1) res.pb({n,1});return res;}
vector<ll> div/*divisor*/(ll n){  vector<ll> res={1};for(ll a=2;a*a<=n;a++){if(n%a!=0) continue;ll b=n/a;res.pb(b);if(b!=a) res.pb(a);}sort(all(res));return res;}

int main() {
  string n;
  cin>>n;
  rep(i,3){
    if(n[i]=='1'){
      n[i]='9';
      continue;
    }
    if(n[i]=='9'){
      n[i]='1';
      continue;
    }
  }
  cout<<n<<endl;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=1000000007,MAX=200005,INF=1<<30;

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;cin>>N;
    if(N%10==3){
        cout<<"bon\n";
    }else if(N%10==0||N%10==1||N%10==6||N%10==8){
        cout<<"pon\n";
    }else{
        cout<<"hon\n";
    }
}



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

int main(int argc, char const *argv[])
{
	int a,b,c;
	cin>>a>>b>>c;
	int ans=3*max({a,b,c})-a-b-c;
	if (ans%2==0)
	{
		cout<<ans/2<<endl;
	}
	else
	{
		ans+=3;
		cout<<ans/2<<endl;
	}
	return 0;
}


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

typedef long long ll;

main()
{
    int d, t, s;
    cin >> d >> t >> s;
    if(d <= t * s){
        cout << "Yes";
    }
    else{
        cout << "No";
    }


}





///promy_pompom
//hello world


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

void R(int &x) {
	int f = 1; x = 0; char s = getchar();
	while(s > '9' || s < '0') {
		if(s == '-') f = -1;
		s = getchar();
	}
	while(s >= '0' && s <= '9') {
		x = (x << 3) + (x << 1) + (s ^ 48);
		s = getchar();
	}
	x *= f;
}

const int mod = 1e9 + 7;
int n , k;
int a[2005];

int main() {
	
	R(n) , R(k);
	
	for(int i = 1; i <= n; i++) {
		R(a[i]);
	}
	
	long long ans = 0 , k1 = k , ans2 = 0;
	
	for(int i = 1;i <= n; i++) {
		for(int j = i + 1; j <= n; j++) {
			if(a[i] > a[j]) 
				ans++;
		}	
	}
	
	for(int i = 1;i <= n; i++) {
		a[0] = a[i];
		for(int j = 1;j <= n; j++)
			if(a[0] > a[j]) 
				ans2++;
	}
	
	ans = ans2 * (((1 + k1) * k1 / 2 - k1) % mod) % mod + ans * k1 % mod;
	ans %= mod; 
	
	printf("%lld" , ans);
	
	return 0;
}

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

string s, t; int n, m;

int check(int i) {
	int res = 0; for (int j = 0; j < m; j++)
		res += (s[i + j] != t[j]);
	return res;
}

int main() {
	cin >> s >> t;
	n = (int)s.size();
	m = (int)t.size();
	int res = n; for (int i = 0; i <= n - m; i++)
		res = min(res, check(i));
	cout << res << '\n';
	cin.ignore(2); return 0;
}

Measured memory_bytes: 3636
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#include<cmath>
#include<bitset>
#include<queue>
#define ll long long
#define itn int
#define co(ans) cout<<ans<<endl;
#define COYE cout<<"YES"<<endl;
#define COYe cout<<"Yes"<<endl;
#define COye cout<<"yes"<<endl;
#define CONO cout<<"NO"<<endl;
#define CONo cout<<"No"<<endl;
#define COno cout<<"no"<<endl;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define INF ((1LL<<62)-(1LL<<31))
#define MOD 1000000007
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
using namespace std;


int main(){
  int H,A;
  cin>>H>>A;
  
  cout<<(H+A-1)/A<<endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
#define df 0
#define rep(i,n) for(int i=0;i<(n);i++)
#define repa(i,a,n) for(int i=(a);i<(n);i++)
typedef long int li;

li gcd(li a,li b){
 return(b==0?a:gcd(b,a%b)); }

int main(){
  if(df) printf("*debug mode*\n");
  li a,b; cin >>a >>b;
  a=gcd(a,b); b=3;
  li ans=1,sq=9;
  if(a%2==0){
    if(df)printf("%ld/%ld...\n",a,b);
    ans++;
    while(a%2==0)a/=2;
  }
  while(sq<a){
    if(df)printf("%ld/%ld...\n",a,b);
    if(a%b==0){
      ans++;
      while(a%b==0) a/=b;
    }
    sq+=b*4+4;
    b+=2;
    if(df)printf("next:%ld %ld<%ld?\n",b,sq,a);
  }
  if(a!=1)ans++;
  cout << ans;
}
// 90068412971

/// confirm df==0 ///


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

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

  int d,n;cin>>d>>n;
  int res=0;
  if(d==0){
    res = n;
    if(n==100)res++;
  }else if(d==1){
    res=n*100;
    if(n==100)res+=100;
  }else{
    res=n*100*100;
    if(n==100)res+=100*100;
  }
  cout<<res<<endl;

  return 0;
}


Measured memory_bytes: 256
N,K = map(int,input().split())
A = list(map(lambda x: int(x) - 1, input().split()))
P = [-1] * N 
cur = 0
P[cur] = 0
route = [1]

for step in range(K):
  cur = A[cur]
  route.append(cur + 1)
  if P[cur] >= 0:
    l_start = P[cur]
    l_end = step + 1
    l_len = l_end - l_start
    break
  else:
    P[cur] = step + 1
else:
  print(cur + 1)
  quit()

print(route[l_start + ((K - l_start) % l_len)])

Measured memory_bytes: 32268
def bubbleSort(A, N): # N 個の要素を含む 0-オリジンの配列 A
    A = list(map(int, A.split()))
    flag = 1 # 逆の隣接要素が存在する
    count = 0  # 交換回数
    while flag:
        flag = 0
        for j in range(N-1, 0, -1):
            if A[j] < A[j-1]:
                # A[j] と A[j-1] を交換
                tmp = A[j]
                A[j] = A[j-1]
                A[j-1] = tmp
                flag = 1
                count += 1
    print(" ".join(map(str,A)))
    print(count)
 
N = int(input())
A = input()
bubbleSort(A, N)


Measured memory_bytes: 5600
import sys, heapq, bisect, math, fractions
from collections import deque

N = int(input())
A = [int(input()) for _ in range(N)]
sortA = sorted(A, reverse=True)

for i in range(N):
    if A[i] == sortA[0]:
        print(sortA[1])
    else:
        print(sortA[0])

Measured memory_bytes: 16152
#include<stdio.h>
int main(void)
{
	int x, i=0;
	
	while(1){
		scanf("%d", &x);
		if(x == 0){
			break;
		}
		i++;
		printf("Case %d: %d\n", i, x);
	}
	
	return 0;
}   

Measured memory_bytes: 596
#include <iostream>
using namespace std;
#define int long long
main()
{
    cin.tie(0);
    int n, a, b;
    cin >> n >> a >> b;
    long long ans = 0;
    int x[n];
    for (int i = 0; i < n; i++)
        cin >> x[i];
    for (int i = 0; i < n - 1; i++)
    {
        ans += min((x[i + 1] - x[i]) * a, b);
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 1024
function main(input) {
	var inputs = input.split("\n");
	var money = Number(inputs[0].split(" ")[0]);
    var kRegexp = new RegExp("["+inputs[1].replace(" ","")+"]");
    while(kRegexp.test(String(money))){
    	money++;
    }
    return money;
}

console.log(main(require("fs").readFileSync("/dev/stdin", "utf8")));

Measured memory_bytes: 10548
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);

int main() {
    ll n;
    ll ans = 0;
    cin >> n;
    for(ll i = 1; i <= n; i++) {
        if (i % 3 == 0 || i % 5 == 0)
            continue;
        ans += i;
    }
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 3644
import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
bridges = [None] * M
G = [[] for i in range(N)]

for i in range(M):
  a,b = map(int,readline().split())
  G[a - 1].append(b - 1)
  G[b - 1].append(a - 1)
  bridges[i] = (a - 1, b - 1)
  
from collections import deque

ans = 0
for i in range(M):
  q = deque([])
  q.append(0)
  seen = set()
  while q:
    v = q.popleft()
    if v in seen:
      continue
    seen.add(v)
    for child in G[v]:
      if (v, child) == bridges[i] or (child, v) == bridges[i]:
        continue
      q.append(child)
  if len(seen) != N:
    ans += 1
    
print(ans)

Measured memory_bytes: 9332
//41
#include<iostream>
#include<cctype>
#include<string>
#include<cstdlib>

using namespace std;

string itos(int i,int b){
  if(i){
    string s;
    while(i){
      int d=i%b;
      s+=(d<10)?'0'+d:'a'+d-10;
      i/=b;
    }
    return string(s.rbegin(),s.rend());
  }else{
    return "0";
  }
} 

int main(){
  int a,c;
  string b;
  while(cin>>a>>b>>c,a!=-1){
    int i;
    for(i=16;i>=2;i--){
      if(itos(a,i)==b)break;
    }
    if(i<2){
      cout<<-1<<endl;
    }else{
      for(;a<=c;a++){
	for(int i=16;i>=2;i--){
	  string s=itos(a,i);
	  int j;
	  for(j=0;j<s.size();j++){
	    if(isalpha(s[j]))break;
	  }
	  if(j==s.size()&&atoi(b.c_str())<=atoi(s.c_str())){
	    b=s;
	    break;
	  }
	}
      }
      cout<<b<<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1228
n,m = map(int,input().split())
A = [[0 for i in range(m)] for j in range(n)]
B = [0 for i in range(m)]

for i in range(n):
    A[i] = list(map(int,input().split()))
for i in range(m):
    B[i] = int(input())

for i in range(n):
    sum = 0
    for j in range(m):
        sum += A[i][j] * B[j]
    print(sum)



Measured memory_bytes: 5980
#!/usr/bin/env python3
import sys


def solve(N: int, M: int):
    n = 0
    m = 0
    if N >1:
        n = N * (N-1) // 2
    if M >1:
        m = M * (M-1) // 2
    print(n+m)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    solve(N, M)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
let () =
    let input = Array.init 3 (fun _ -> Scanf.scanf "%d %d\n" (fun a b -> (a, b))) in
    let junc = Array.init 5 (fun _ -> 0) in
    Array.iter (fun (j1, j2) -> junc.(j1) <- junc.(j1) + 1; junc.(j2) <- junc.(j2) + 1) input;
    print_endline @@ if Array.fold_left (fun acc j -> acc || j > 2) false junc
        then "NO"
        else "YES"

Measured memory_bytes: 384
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
#define int long long
const int mod = 1e9+7;
int n,m,a[2010],Ans;
signed main(){
    int i,j,k;
    scanf("%lld%lld",&n,&m);
    for(i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(i=1;i<=n;i++){
      int res=0,res2=0;
      for(j=i+1;j<=n;j++)
        if(a[j]<a[i])res++;
      for(j=1;j<i;j++)
        if(a[j]<a[i])res2++;
      Ans=((Ans+((m*(m+1))>>1ll)%mod*res%mod)%mod+((m*(m-1))>>1ll)%mod*res2%mod)%mod;
    }
    cout<<Ans<<"\n";
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
#include<functional>
#include<cmath>
using namespace std;
long long  mod = 1000000007;

struct City {
	int pre;
	long long year;
	int number;
	int no;
	bool operator<(const City& b) const {
		return year < b.year;
	}
};
City a[100000], b[100000];
int main()
{
	int count[100010];
	for (int i = 1; i <= 100000; i++) {
		count[i] = 1;
	}
	int N, M;
	scanf("%d%d", &N, &M);
	for (int i = 0; i < M; i++) {
		scanf("%d%lld", &a[i].pre, &a[i].year);
		a[i].no = i; 
		b[i].no = i;
		b[i].pre = a[i].pre;
		b[i].year = a[i].year;
	}
	sort(a, a + M);
	for (int i = 0; i < M; i++) {
		b[a[i].no].number = count[a[i].pre];
		count[a[i].pre]++;
	}
	for (int i = 0; i < M; i++) {
		printf("%06d%06d\n", b[i].pre, b[i].number);
	}
	return 0;
}



Measured memory_bytes: 6528
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#define cinf(n,x) for(int i=0;i<(n);i++) cin >> x[i];
typedef long long int ll;
using namespace std;

int main(){
	int n,a,b;
	cin>>n>>a>>b;
	int m=b-a-1;
	cout <<(m%2==1?"Alice":"Borys") << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include <functional>
#include<vector>
#include<unordered_map>
#include<queue>
#define rep(i,n) for(i=0;i<n;++i)

using namespace std;

vector<int> vec[200005];
vector<int> ans;

class CompareFirst
{
public:
  bool operator()(pair<int,int> n1,pair<int,int> n2) {
    return n1.first>n2.first; //>:desc <:asc
  }
};
void dfs(int v, int p){
  for(auto u : vec[v]){
    if(u == p)continue;
    ans[u] += ans[v];
    dfs(u,v);
  }
}


int main(){

  string s;
  int a,b,c,i,j,k,n,q,p,x;

  cin >> n >> q;
  ans.resize(n);
  rep(i,n-1){
    cin >> a >> b;
    --a;--b;
    vec[a].push_back(b);
    vec[b].push_back(a);
  }
  rep(i,q){
    cin >> p >> x;
    --p;
    ans[p] += x;
  }
  dfs(0,-1);

  rep(i,n)cout << ans[i] << endl;

  return 0;

}

Measured memory_bytes: 23552
# import bisect
from collections import Counter, deque
# from copy import copy, deepcopy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
import string
# from operator import xor
import sys

sys.setrecursionlimit(10 ** 5 + 10)


# input = sys.stdin.readline

def resolve():
    n = int(input())
    S = [list(input()) for i in range(n)]
    SS = []
    char = string.ascii_lowercase
    ans = []
    inf = 10 ** 15
    for i in S:
        SS.append(Counter(i))
    for k in range(len(char)):
        val = inf
        for j in SS:
            val = min(val, j[char[k]])
        ans.extend([char[k]] * val)

    for i in ans:
        print(i, end='')
    print()


resolve()

Measured memory_bytes: 39536
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
using namespace std;
typedef long long int ll;
typedef __int128_t lll;
typedef pair<int, int> P;
lll p10[20];
lll count(lll x){
	lll ret=0;
	for(int i=0; ; i++){
		if(x<=p10[i]-1) break;
		ret+=(x-(p10[i]-1));
		ret-=(x/3-(p10[i]-1)/3);
		ret-=(x/5-(p10[i]-1)/5);
		ret+=(x/15-(p10[i]-1)/15);
	}
	ret+=(x/3+x/5)*4;
	return ret;
}
string num(ll x){
	string ret;
	while(x){
		ret+=('0'+x%10);
		x/=10;
	}
	reverse(ret.begin(), ret.end());
	return ret;
}
int main()
{
	ll s; cin>>s;
	p10[0]=1;
	for(int i=1; i<20; i++) p10[i]=p10[i-1]*10;
	lll x1=0, x2=p10[18];
	while(x1!=x2){
		lll x=(x1+x2+1)/2;
		if(count(x)<s) x1=x;
		else x2=x-1;
	}
	ll c=count(x1);
	string ans;
	for(ll x=x1+1; x<=x1+21; x++){
		if(x%3==0) ans+="Fizz";
		if(x%5==0) ans+="Buzz";
		if(x%3!=0 && x%5!=0) ans+=num(x);
	}
	cout<<ans.substr(s-c-1, 20)<<endl;
	return 0;
}


Measured memory_bytes: 3212
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100010


int main(){
  int A, B;

  cin >> A >> B;

  cout << (B+A-1)/A << endl;
  
  return 0;
}




Measured memory_bytes: 3100
n, y = map(int, input().split())
flag = False
for i in range(n+1):
  for j in range(n-i+1):
    if 10000*i+5000*j+1000*(n-i-j) == y:
      print(i, j, n-i-j)
      flag = True
      break
  if flag is True:
    break
if flag is False:
  print(-1, -1 ,-1)

Measured memory_bytes: 3060
#include <stdio.h>

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

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

long long max(long long a, long long b)
{
    if (a > b){
        return (a);
    }
    return (b);
}

long long min(long long a, long long b)
{
    if (a < b){
        return (a);
    }
    return (b);
}

int main(void)
{
    long long d[10], v[10], k[10];
    long long lcm_, gcd_;
    int n;
    int i, j;
    
    while (1){
        scanf("%d", &n);
        
        if (n == 0){
            break;
        }
        
        lcm_ = 1;
        
        for (i = 0; i < n; i++){
            scanf("%lld%lld", &d[i], &v[i]);
            gcd_ = gcd(max(d[i], v[i]), min(d[i], v[i]));
            d[i] /= gcd_;
            v[i] /= gcd_;
            lcm_ = lcm(max(d[i], lcm_), min(d[i], lcm_));
        }
        gcd_ = lcm_ / d[0] * v[0];
        for (i = 0; i < n; i++){
            k[i] = lcm_ / d[i] * v[i];
            gcd_ = gcd(max(k[i], gcd_), min(k[i], gcd_));
        }
        
        for (i = 0; i < n; i++){
            printf("%lld\n", (lcm_ / d[i]) * (v[i] / gcd_));
        }
    }
    
    return (0);
}

Measured memory_bytes: 0
// I'm a f*cking looser
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define fasino ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
const long long mxN = 10000000; 

bool prime[mxN+2];
vector<long long> primes;

void seive(){
    prime[0]=prime[1]=true;
    for(long long i=4;i<=mxN;i+=2){
        prime[i] = true;
    }
    for(long long i=6;i<=mxN;i+=3){
        prime[i] = true;
    }
    for(long long i=5;i*i<=mxN;i++){
        if(!prime[i]){
            for(long long j=i*i;j<=mxN;j+=i){
                prime[j] = true;
            }
        }
    }
    for(int i=2;i<=mxN;i++){
        if(!prime[i]){
            primes.push_back(i);
        }
    }
}

ll count(ll n){
    if(n==1){ return 1;}
    ll ans = 1;
    for(ll o=0;o<primes.size();o++){
        ll i = primes[o];
        if(i*i*i>n) break;
        ll cnt = 1;
        while(n%i==0){
            n/=i;
            cnt++;
        }
        ans = ans*cnt;
    }
    double k = sqrt(n);
    ll m = ceil(k);
    ll j = floor(k);
    if(!prime[n]) ans*=2;
    else if(!prime[m] and m==j) ans*=3;
    else if(n!=1) ans*=4;
    return ans;

}
signed main()
{
    fasino
    seive();
    ll n;
    cin>>n;
    ll res = 0;
    for(ll i=1;i<=n;i++){
        res += i*count(i);
    }
    cout<<res;
    return 0;
}

Measured memory_bytes: 21372
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;

const int N=100005;

int n,m,l1,r1,l2,r2,Q;
int s1[N],s2[N];
char c[N];

int main(){
	int i;
	scanf("%s",c+1); n=strlen(c+1);
	for (i=1;i<=n;i++){
		if (c[i]=='A') s1[i]=s1[i-1]+2;
		else s1[i]=s1[i-1]+1;
	}
	scanf("%s",c+1); m=strlen(c+1);
	for (i=1;i<=m;i++){
		if (c[i]=='A') s2[i]=s2[i-1]+2;
		else s2[i]=s2[i-1]+1;
	}
	scanf("%d",&Q);
	while (Q--){
		scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
		if ((s1[r1]-s1[l1-1])%3==(s2[r2]-s2[l2-1])%3) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <set>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <stack>
#include <string>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <random>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <chrono>
#include <ctime>

using namespace std;

#define en '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double EPS = 1e-9;
const int INF = 1e9 + 7;
const ll LINF = 1e18;
const double PI = 3.1415926535897932384626433832795;
const int MAX_SIZE = 5e5;
ld START_TIME, TIME;

void fast_in_out() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    START_TIME = clock();
}

void solve() {
    ll n, k, ans = 0, s1 = 0, s2 = 0;
    cin >> n >> k;
    for (int i = 0; i < k - 1; ++i) {
        s1 += i;
        s2 += (n - i);
    }
    for (int i = k - 1; i <= n; ++i) {
        s1 += i;
        s2 += (n - i);
        ans += (s2 - s1 + 1);
        ans = ans % INF;
    }
    cout << ans << en;
}

int main() {
    fast_in_out();
    TIME = (clock() - START_TIME) / CLOCKS_PER_SEC;
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    cerr << en << TIME << " sec." << en;
    return 0;
}

/*
     ▄▀▀▀▄
▄███▀░◐░░░▌
    ▌░░░░░▐
    ▐░░░░░▐
    ▌░░░░░▐▄▄
    ▌░░░░▄▀▒▒▀▀▀▀▄
   ▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
   ▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
    ▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
      ▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
           ▌▌░▌▌
           ▌▌░▌▌
         ▄▄▌▌▄▌▌        */


Measured memory_bytes: 3804
import java.io.*;
import java.util.StringTokenizer;

import static java.lang.Integer.*;
import static java.lang.Long.parseLong;

public class Main {

    public static void main(String[] args) throws IOException {
        PrintWriter prnt = new PrintWriter(System.out);
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = parseInt(read.readLine());
        st = new StringTokenizer(read.readLine());
        long[] arr = new long[n];
        for (int i = 0; i < n; i++){
            arr[i] = parseLong(st.nextToken());
        }
        prnt.println(getNumberWay(arr, n));

        prnt.close();


    }

    static long getNumberWay(long[] arr, int n) {
        long res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                for (int k = j; k < n; k++) {
                    if (arr[i] != arr[j] && arr[j] != arr[k] && arr[k] != arr[i]) {
                        if ((arr[i] + arr[j]) > arr[k] && (arr[i] + arr[k]) > arr[j] && (arr[j] + arr[k]) > arr[i]) {
                            res++;
                           // System.out.println(i + " " + j + " " + k);
                        }
                    }
                }
            }
        }
        return res;
    }
}

Measured memory_bytes: 33176
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<tuple>
#include<utility>
#include<stack>
#include<set>
#include<iomanip>
using namespace std;
using ll=long long int;

ll gcd(ll p, ll q) {
	ll r = p % q;
	while (r != 0) {
		p = q;
		q = r;
		r = p % q;
	}
	return q;
}

ll lcm(ll p, ll q) {
	return p * q / gcd(p, q);
}

int main() {
	ll a, b;
	while (cin >> a >> b) {

		cout << gcd(a, b) << " " << lcm(a, b) << endl;
	}
	return 0;
}



Measured memory_bytes: 3000
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;

struct SegTree {
	typedef ll T;
	static constexpr T unit = 0;
	T f(T a, T b) { return max(a, b); } // (any associative fn)
	vector<T> s; int n;
	SegTree(int _n = 0, T def = unit) : s(2*_n, def), n(_n) {}
	void update(int pos, T val) {
		for (s[pos += n] = val; pos /= 2;)
			s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
	}
	T query(int b, int e) { // query [b, e)
		T ra = unit, rb = unit;
		for (b += n, e += n; b < e; b /= 2, e /= 2) {
			if (b % 2) ra = f(ra, s[b++]);
			if (e % 2) rb = f(s[--e], rb);
		}
		return f(ra, rb);
	}
};

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

	int r, c, k; cin >> r >> c >> k;
	vector<vector<array<int, 2>>> items(r+1);
	for (int i = 0; i < k; ++i) {
		int x, y, v; cin >> x >> y >> v;
		items[x].push_back({y, v});
	}
	for (auto &vec : items)
		sort(begin(vec), end(vec));

	SegTree T(c+1);
	vector<vector<ll>> dp(r+1);
	vector<vector<array<ll, 3>>> dp2(r+1);
	ll ans = 0;
	for (int row = 1; row <= r; ++row) {
		auto &v = items[row];
		auto &cur = dp[row];
		auto &cur2 = dp2[row];
		cur.resize(v.size()); cur2.resize(v.size());
		ll best1 = -1, best2 = -1;
		for (int j = 0; j < (int)v.size(); ++j) {
			auto [col, val] = v[j];
			cur2[j][0] = T.query(0, col+1) + val;
			if (best1 >= 0) cur2[j][1] = best1 + val;
			if (best2 >= 0) cur2[j][2] = best2 + val;
			best1 = max(best1, cur2[j][0]);
			best2 = max(best2, cur2[j][1]);
			cur[j] = *max_element(begin(cur2[j]), end(cur2[j]));
			ans = max(ans, cur[j]);
		}
		for (int j = 0; j < (int)v.size(); ++j) {
			auto x = T.query(items[row][j][0], items[row][j][0]+1);
			if (x < cur[j]) T.update(items[row][j][0], cur[j]);
		}
	}
	cout << ans << '\n';
}

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

int main() {
  long int n;
  cin >> n;
  long int c = n - 1, s = sqrt(n);
  for (long int i = 2; i < s + 1; i++) {
    if (n % i == 0) {
      c = min(c, i + n / i - 2);
    }
  }
  cout << c << endl;
}

Measured memory_bytes: 256
MOD = 10**9 + 7

N,M = map(int,input().split())
dp = [0]*(N+1)
dp[0] = 1
A = set(int(input()) for _ in range(M)) # 禁止地帯

for i in range(1,N+1):
  if i in A:
    continue
  x = dp[i-1]
  if i > 1:
    x += dp[i-2]
  dp[i] = x%MOD

answer = dp[N]
print(answer)

Measured memory_bytes: 12652
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Integer.parseInt;

/**
 * Books
 */
public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		String[] words;

		int N, K;
		line = br.readLine();
		N = parseInt(line.substring(0, line.indexOf(' ')));
		K = parseInt(line.substring(line.indexOf(' ') + 1));

		Map<Integer, List<Integer>> CG = new HashMap<>();

		for (int i = 0; i < N; i++) {
			line = br.readLine();
			int C, G;
			C = parseInt(line.substring(0, line.indexOf(' ')));
			G = parseInt(line.substring(line.indexOf(' ') + 1));
			CG.putIfAbsent(G, new ArrayList<>());
			CG.get(G).add(C);
		}

		for (int i = 1; i <= 10; i++) {
			if (CG.containsKey(i)) {
				Collections.sort(CG.get(i), Comparator.reverseOrder());
				for (int j = 1; j < CG.get(i).size(); j++) {
					CG.get(i).set(j, CG.get(i).get(j) + CG.get(i).get(j - 1));
				}
				for (int j = 1; j < CG.get(i).size(); j++) {
					CG.get(i).set(j, CG.get(i).get(j) + j * (j + 1));
				}
			}
		}

		//[?????£??????][?£??????¬????????°]
		int[][] dp = new int[11][K + 1];

		for (int i = 1; i <= 10; i++) {
			if (CG.containsKey(i)) {
				for (int j = 0; j <= K; j++) {
					for (int k = 0; k < CG.get(i).size(); k++) {
						if (j + k + 1 <= K) {
							dp[i][j + k + 1] = Math.max(dp[i][j + k + 1], dp[i - 1][j + k + 1]);
							dp[i][j + k + 1] = Math.max(dp[i][j + k + 1], dp[i - 1][j] + CG.get(i).get(k));
						}
					}
				}
			} else {
				for (int j = 0; j <= K; j++) {
					dp[i][j] = dp[i - 1][j];
				}
			}
		}

		System.out.println(dp[10][K]);
	}
}

Measured memory_bytes: 29032
unittest
{
	assert( [ "2 3 1", "1 1", "1 2", "2 2", "1 2" ].solve == "3" );
	assert( [ "10 3 2", "1 5", "2 8", "7 10", "1 7", "3 10" ].solve == "1\n1" );
	assert( [ "10 10 10", "1 6", "2 9", "4 5", "4 7", "4 7", "5 8", "6 6", "6 7", "7 9", "10 10", "1 8", "1 9", "1 10", "2 8", "2 9", "2 10", "3 8", "3 9", "3 10", "1 10" ].solve == "7\n9\n10\n6\n8\n9\n6\n7\n8\n10" );
}



import std.conv;
import std.format;
import std.range;
import std.stdio;

void main()
{
	stdin.byLineCopy.solve.writeln;
}

auto solve( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = 0L;
	auto m = 0L;
	auto q = 0L;
	input.front.formattedRead!"%s %s %s"( n, m, q );
	auto lrs = new long[ 2 ][ m ];
	foreach( ref lr; lrs )
	{
		input.popFront;
		lr = input.front.split.to!( long[] );
	}
	auto pqs = new long[ 2 ][ q ];
	foreach( ref pq; pqs )
	{
		input.popFront;
		pq = input.front.split.to!( long[] );
	}
	
	auto tss = new long[][]( 1 + n + 1, 1 + n + 1 );
	foreach( lr; lrs )
	{
		tss[ lr[ 0 ] ][ lr[ 1 ] ]++;
	}
	foreach( i; 0L .. tss.length.signed )
	{
		foreach( j; 0L .. tss[ i ].length.signed - 1 )
		{
			tss[ i ][ j + 1 ] += tss[ i ][ j ];
		}
	}
	foreach( j; 0L .. tss[ 0 ].length.signed )
	{
		foreach( i; 0L .. tss.length.signed - 1 )
		{
			tss[ i + 1 ][ j ] += tss[ i ][ j ];
		}
	}
	
	auto anss = new long[ q ];
	foreach( ref ans, pq; lockstep( anss, pqs ) )
	{
		auto a = pq[ 0 ] - 1;
		auto b = pq[ 1 ];
		ans = tss[ b ][ b ] - tss[ a ][ b ] - tss[ b ][ a ] + tss[ a ][ a ];
	}
	return anss.to!( string[] ).join( "\n" );
}


Measured memory_bytes: 14468
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stdfix.h>

using namespace std;

int main() {
    long long L,R;
    cin >> L >> R;
    long long l,r;
    if(R - L >= 2019){
        l = 0;
        r = 2018;
    }else{
        l = L % 2019;
        r = R % 2019;
    }
    if(l > r){
        r += 2019;
    }
    long long mini = 2019;
    for(long long i = l; i <= r - 1; i++){
        for(long long j = i + 1; j <= r; j++){
            mini = min(mini,(i * j) % 2019);
        }
    }
    cout << mini << endl;


}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<string> VS;
typedef vector< vector<int> > VVI;
typedef vector< vector<ll> > VVL;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
 
int main(){
  int N;
  cin>>N;
  ll mod=1e9+7;
  VI PP;
  PP.pb(2);
  rep(i,1000){
    int F=1;
    rep(j,PP.size()){
      if((i+3)%PP[j]==0){
        F=0;
        break;
      }
    }
    if(F) PP.pb(i+3);
  }
  VI Y(1001);
  rep(i,N){
    int X=i+1;
    rep(j,20){
      rep(k,PP.size()){
        if(X%(PP[k])==0){
          X/=PP[k];
          Y[PP[k]]++;
          break;
        }
      }
    }
  }
  ll ans=1;
  rep(i,1001) (ans*=(Y[i]+1))%=mod;
  cout<<ans<<endl;
}

Measured memory_bytes: 256
package main

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

func main() {
	sc := NewScanner(os.Stdin)
	n := sc.Int()
	p := sc.Float64s(n)

	dp := make([]float64, n+2)
	dp[0] = 1 - p[0]
	dp[1] = p[0]

	for n, v := range p {
		if n == 0 {
			continue
		}

		for i := n + 1; i >= 0; i-- {
			if i == 0 {
				dp[i] = dp[i] * (1 - v)
				continue
			}
			dp[i] = dp[i-1]*v + dp[i]*(1-v)
		}
	}

	var sum float64
	for i := (n + 1) / 2; i <= n; i++ {
		sum += dp[i]
	}
	fmt.Println(sum)
}

func BytesToInt(b []byte) (n int) {
	var i int
	if b[0] == '-' {
		i++
	}
	for ; i < len(b); i++ {
		n *= 10
		n += int(b[i] - '0')
	}
	if b[0] == '-' {
		return -n
	}
	return
}

func BytesToFloat64(b []byte) float64 {
	i, f, idx := 0.0, 0.0, 0
	if b[0] == '-' {
		idx++
	}
	for ; idx < len(b) && b[idx] != '.'; idx++ {
		i *= 10
		i += float64(b[idx] - '0')
	}
	if idx < len(b) {
		for idx = len(b) - 1; idx >= 0 && b[idx] != '.'; idx-- {
			f += float64(b[idx] - '0')
			f *= 0.1
		}
	}
	if b[0] == '-' {
		return -(i + f)
	}
	return i + f
}

type Scanner struct{ *bufio.Scanner }

func NewScanner(r io.Reader) *Scanner {
	s := bufio.NewScanner(r)
	s.Split(bufio.ScanWords)
	return &Scanner{Scanner: s}
}

func (s *Scanner) Bytes() []byte { s.Scan(); return s.Scanner.Bytes() }

func (s *Scanner) Int() int { return BytesToInt(s.Bytes()) }

func (s *Scanner) Float64() float64 { return BytesToFloat64(s.Bytes()) }

func (s *Scanner) Float64s(len int) []float64 {
	a := make([]float64, len)
	for i := 0; i < len; i++ {
		a[i] = s.Float64()
	}
	return a
}


Measured memory_bytes: 640
n, m = map(int, input().split())

xy = [i for i in range(n + 1)]


def root(x):
    i = x
    while i != xy[i]:
        i = xy[i]
    xy[x] = i
    return i


for _ in range(m):
    x, y = map(int, input().split()[:2])
    xy[root(x)] = root(y)

print(sum(i == v for i, v in enumerate(xy)) - 1)


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

#define X first
#define Y second
#define mp make_pair
#define pb pop_back
#define eb emplace_back
#define sz(v) (int) v.size()

using namespace std;

typedef long long LL;
typedef long double LD;

void solve() {
	int n;
	cin >> n;
	map <vector <int>, int> cnt;
	for (int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		vector <int> cur(26, 0);
		for (auto &x : s) {
			cur[x - 'a']++;
		}
		cnt[cur]++;
	}
	LL ans = 0;
	for (auto &x : cnt) {
		ans += 1LL * x.Y * (x.Y - 1) / 2;
	}
	cout << ans << "\n";
}

signed main() {
// #define TASK ""
#if !defined(LOCAL) && defined(TASK)
	// freopen(TASK".in", "r", stdin);
	// freopen(TASK".out", "w", stdout);
#endif
	ios::sync_with_stdio(0); cin.tie(0);
	int tests = 1;
	// cin >> tests;
	while (tests--) {
		solve();
	}
	return 0;
}

Measured memory_bytes: 19072
#include<stdio.h>
#include<stdlib.h>
int main(){
  char s[101];
  int k;
  int p,q,r;
  int ln;
  
  scanf("%d",&k);
  scanf("%s",s);
  
  ln = strlen(s);
  
  if(ln<=k){
   printf("%s\n",s); 
  }else{
   for(p=0;p<k;p++){
    printf("%c",s[p]);
   }
    printf("...\n");
  }
  
  
 return 0; 
}

Measured memory_bytes: 1664