akhauriyash/Code-Regression huggingface dataset:
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define Q int t; scanf("%d", &t); for(int q=1; q<=t; q++)
typedef long long int lli;
typedef pair<int, int> pi;
typedef pair<int, pi> node;
#define oset tree<pi, null_type,greater<pi>, rb_tree_tag,tree_order_statistics_node_update>


int main()
{
    int n;
    cin >> n;
    int a[n], b[n], c[n];
    for(auto &x: a)cin >> x, x--;
    for(auto &x: b) cin >> x;
    for(int i=0; i<n-1; i++){
        cin >> c[i];
    }
    int ans = 0;
    for(int i=0; i<n; i++){
        ans += b[a[i]];
        if(i>0 && a[i-1]+1==a[i]){
            ans += c[a[i-1]];
        }
    }
    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 3608
import sys

x,y=map(int,input().split())
d=abs(x-y)
if x>=y:
    x-=2*d
    y-=d
else:
    x-=d
    y-=2*d
if x%3!=0 or x<0:
    print(0)
    sys.exit()

cnt=x//3

mod=10**9+7
N=7*10**5+10
g1=[1,1]
g2=[1,1]
inverse=[0,1]

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

def cmb(n,r):
    if (r<0 or r>n):
        return 0
    r=min(r,n-r)
    return g1[n]*g2[r]*g2[n-r]%mod

print(cmb(2*cnt+d,cnt))

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

int main() {
  string s, t;
  cin >> s;
  cin >> t;

  int count = 0;
  for (int i = 0; i < 3; i++) {
    if (s[i] == t[i]) count++;
  }
  cout << count << endl;
  return 0;
}

Measured memory_bytes: 256
// Author: Vamsi Krishna Reddy Satti
// With love for Competitive Programming!
 
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize ("Ofast,unroll-loops,-ffloat-store,no-stack-protector")
// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")

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

string to_string(const string& s) { return '"' + s + '"'; }
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cout << " " << to_string(H);
    debug_out(T...);
}
#ifdef LOCAL
    #define debug(...) cout << "#" << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
    #define debug(...) 3
#endif
 
#define cin_exception cin.exceptions(cin.failbit);
#define cout_precision cout.setf(ios::fixed); cout.precision(15);
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
using ld = long double;  using ui = uint_fast32_t;
using ll = int_fast64_t; using ul = uint_fast64_t;

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

const int N = 2e5 + 5;
int cn[N];

void solve() {
    int n; cin >> n;
    for (int i = 2; i <= n; ++i) {
        int a; cin >> a;
        ++cn[a];
    }
    for (int i = 1; i <= n; ++i) {
        cout << cn[i] << '\n';
    }
}

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

int main() {
    fast_io; cout_precision;
#ifdef LOCAL
    cin_exception;
#endif
    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; ++i) {
        // cout << "Case #" << i << ": ";
        solve();
    }
}

Measured memory_bytes: 4400
import java.util.*;
public class Main {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		double A[]=new double[N+1];
		double sum = 0;
		int choice=0;
		String ansy="Yes";
		String ansn="No";
		for(int i=1;i<=N;i++){
			A[i]=sc.nextInt();
		}

		for(int i=1;i<=N;i++){
			sum=sum+A[i];
		}

		for(int i=1;i<=N;i++){
			if (A[i]>=sum/(4*M)){
				choice=choice+1;
			}
		}
		if (choice>=M) {
				System.out.println(ansy);
		}
		else{
				System.out.println(ansn);
		}
    }
}

Measured memory_bytes: 21844
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;
#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

#[allow(dead_code)]
fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn main(){
    let n: usize = read_as_vec::<usize>()[0];
    let p = read_as_vec::<u64>();
    let mut ans = 0;
    let mut cur_min = 2*100000+1;

    for &elem in &p{
        if cur_min > elem{
            cur_min = elem;
            ans += 1;
        }
    }
    println!("{}", ans);
}


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

#define ll long long 

int main() {
    ios::sync_with_stdio(0); 

    int a, b;
    cin >> a >> b;

    for (int x = 1; x <= 1e5; x++) {
        if ((int) (8.0/100 * (double) x) == a and ((int) (10.0/100 * (double) x) == b)) {
            cout << x << endl;
            return 0;
        }
    }

    cout << -1 << endl;


    return 0; 
}



Measured memory_bytes: 3616
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <vector>

using namespace std;

int ps[100], rs[100];
double x[100], y[100], z[100], r[100];

inline double sq(double x) {
  return x * x;
}

int find(int x) {
  if (ps[x] == x)
    return x;
  return ps[x] = find(ps[x]);
}

bool merge(int x, int y) {
  int xr = find(x), yr = find(y);
  if (xr == yr)
    return false;
  if (rs[xr] < rs[yr])
    ps[xr] = yr;
  else if (rs[xr] > rs[yr])
    ps[yr] = xr;
  else {
    ps[yr] = xr;
    rs[xr]++;
  }
  return true;
}

int main() {
  for (;;) {
    int n;
    scanf("%d", &n);
    if (!n) return 0;
    for (int i = 0; i < n; i++) {
      scanf("%lf%lf%lf%lf", &x[i], &y[i], &z[i], &r[i]);
      ps[i] = i;
      rs[i] = 0;
    }
    vector<pair<double, pair<int, int> > > es;
    for (int i = 1; i < n; i++)
      for (int j = 0; j < i; j++)
        es.push_back(make_pair(max(sqrt(sq(x[j]-x[i])+sq(y[j]-y[i])+sq(z[j]-z[i]))-(r[i]+r[j]), 0.0), make_pair(i, j)));
    sort(es.begin(), es.end());
    double cost = 0.0;
    for (int i = 0, j = 0; j < n-1 && i < es.size(); i++)
      if (merge(es[i].second.first, es[i].second.second)) {
        j++;
        cost += es[i].first;
      }
    printf("%.3f\n", cost);
  }
}

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

int main() {
  int N,k;
  cin >> N>>k;
  long ans;
  rep2(i,k+1,N+1){
    if(N%i==0){
      ans=ans+N/i*(i-k);
    }
    else{
      if(N%i-max(0,k-1)>=0){
        ans=ans+N/i*(i-k)+N%i-max(0,k-1);
      }
      else{
        ans=ans+N/i*(i-k);
      }
    }
  }
  
 
  cout<<ans<<endl;
 
}

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

using namespace std;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
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 (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = 1e18;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p;
int dx[4] = { 1,0, -1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
//#define mp make_pair



int main() {
  string s;
  cin >> s;
  int ans = inf;
  for (int i = 0; i + 2 < s.size(); i++) {
    int n = stoi(s.substr(i, 3));
    chmin(ans, abs(n - 753));
  }
  cout << ans << endl;
}
  


Measured memory_bytes: 256
#include <algorithm>
#include <bits/stdc++.h>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <iostream>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string>
#include <utility>
#include <vector>

#define REP(i, n) for(int i = 0; i != n; ++i)
#define REPR(i, n) for(int i = n - 1; i != -1; --i)
#define FOR(i, a, b) for(int i = a; i != b; ++i)
#define RBF(i, n) for(auto &i : n)
#define ABS(n) (n < 0 ? -n : n)
#define MIN(a, b) (a < b ? a : b)
#define MAX(a, b) (a > b ? a : b)
#define IN(n) (cin >> n)
#define OUT(n) (cout << n << "\n")
#define INF 1e9
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define PB push_back
#define MP make_pair
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define SORTR(c) sort((c).begin(),(c).end(),greater<int>())

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

using namespace std;
using ll = long long;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

void Main() {
  int n;
  string S;
  cin >> n >> S;
  REP(i,S.size()){
    if((int)S[i]+n>90) S[i]=(int)S[i]+n-26;
    else S[i]=(int)S[i]+n;
  }
  OUT(S);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  Main();

  return 0;
}

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

int main() {
  int n;
  cin >> n;
  int ans = 0;

  for (int i = 1; i <= n; i++) {
    int digit  = 0;
    int x = i;
    while(x > 0){
    x  = x / 10;
      digit++;
    }
    if (digit % 2 != 0) ans++;
  }

  cout << ans;

}

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

ll gcd(ll a, ll b){return b!=0 ? gcd(b, a%b) : a;}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}

int main(){
	int n;
	cin >> n;
	vector<int> s(n);
	int total = 0;
	rep(i, n){
		cin >> s[i];
		total += s[i];
	}
	
	if(total % 10 != 0){
		cout << total << endl;
		return 0;
	}
	
	int ans = 0;
	for(int i = 0; i < n; ++i){
		if( (total - s[i]) % 10 != 0){
			ans = max(ans, total - s[i]);
		}
	}
	cout << ans << endl;
	
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <tuple>

#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i>b;i--)
#define vint vector<int> 
#define vvint vector<vint>
#define CST(x) cout<<fixed<<setprecision(x)//小数点以下の桁数指定
#define ct(a) cout<<a<<endl
static const double pi = 3.141592653589793;
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int INF = 1e9+7;

class unionfind {
public:
	vector<int> par;
	vector<int> siz;

	unionfind(int N) :par(N), siz(N,1) {//コンストラクタ
		for (int i = 0; i < N; i++) {
			par[i] = i;
		}
	}

	int root(int x) {//データｘが属する木の根を再帰で得る:root(x)={ｘの木の根}
		while (par[x] != x) {
			x = par[x] = par[par[x]];
		}
		return x;
	}

	bool unite(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		if (rx == ry)return false;//ｘとｙの根が同じ（＝同じ木にある）時はそのまま
		if (siz[rx] < siz[ry])swap(rx, ry);
			siz[rx] += siz[ry];
			par[ry] = rx;
			return true;
	}

	bool same(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
	int size(int rx) {
		return siz[root(rx)];
	}

};

int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	
	int N,M;
	cin >> N >> M;

	unionfind U(N);

	FOR(i, 0, M) {
		int X, Y, Z;
		cin >> X >> Y >> Z;
		X--; Y--;
		U.unite(X, Y);

	}

	int ans = 0;
	FOR(i, 0, N) {
		if (U.root(i) == i)ans++;
	}
	cout << ans << endl;



	return 0;
}


Measured memory_bytes: 1024
//おまじない
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#define INF 1e9+7
#define rep(i,m,n) for(int i=m;i<n;i++)
#define mrep(i,m,n) for(int i=m;i<n;i--)
#define NO cout<<"NO"<<endl;
#define YES cout << "YES"<<endl;
#define No cout << "No"<<endl;
#define Yes cout << "Yes"<<endl;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;


//(int)'a'は97 (int)'A'は65
//おまじない



int main() {

	int n, m;
	cin >> n >> m;
	int stu[50][2];
	int che[50][2];

	rep(i, 0, n) {
		cin >> stu[i][0] >> stu[i][1];
	}
	rep(i, 0, m) {
		cin >> che[i][0] >> che[i][1];
	}

	ll dis, ndis;

	rep(i, 0, n) {
		int ans = m;
		dis = INF;
		rep(j, 0, m) {
			ndis=abs(stu[i][0] - che[j][0]) + abs(stu[i][1] - che[j][1]);
			if (ndis < dis) {
				dis = ndis;
				ans = j;
			}else if (ndis == dis) {
				ans = min(ans, j);
			}
		}

		cout << ans + 1 << endl;
	}

	return 0;
}


Measured memory_bytes: 256
n = gets.to_i
a = []
a[0] = gets.split.map(&:to_i)
a[1] = gets.split.map(&:to_i)
for i in 1...n do
  a[0][i] += a[0][i - 1]
end
a[1][0] += a[0][0]
for i in 1...n do
  a[1][i] += [a[0][i], a[1][i - 1]].max
end
puts a[1][n - 1]


Measured memory_bytes: 14404
n, k = map(int, input().split())

index=0
numberL=[]
while index < n:
    a, b = map(int, input().split())
    numberL.append([a, b])
    index+=1

numberL.sort()

index2=0
sum=0
while index2 < len(numberL):
    sum+=numberL[index2][1]
    if sum < k:
        index2+=1
    else:
        print(numberL[index2][0])
        break


Measured memory_bytes: 20104
object Main extends App {
  val in = new java.util.Scanner(System.in)
  val N, T, A = in.nextInt
  val Hs = Array.fill(N)(in.nextInt)
  println(Hs.map(x => math.abs(T - x * 0.006 - A)).zipWithIndex.minBy(_._1)._2 + 1)
}

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

s = []
p = 0

for i in range(n):
    p+=a[i]
    s.append(p)
s.append(0)

x = 0
import collections
s = collections.Counter(s)

y,z = zip(*s.most_common())

for i in range(len(z)):
    x += (z[i]*(z[i]-1))//2
print(x)


Measured memory_bytes: 61540
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Code author: Saurabh Singhal
Code copy karne vaale tera muh kaala
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/

#include<bits/stdc++.h>
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define ppb pop_back

using namespace std;
typedef long long int ll;
typedef vector<int> vi_t;
typedef vector<ll> vll_t;
int t=1;
vll_t a,b;
int  main(){
	// #ifndef ONLINE_JUDGE
 //    // for getting input from input.txt
 //    freopen("input.txt", "r", stdin);
 //    // for writing output to output.txt
 //    freopen("output.txt", "w", stdout);
	// #endif
	int d,g;
	cin>>d>>g;
	int ans=INT_MAX;
	vector<int>p(d),c(d);
	for(int i=0;i<d;i++){
		cin>>p[i]>>c[i];
	}
	for(int i=0;i<=(1<<d);i++){
		int sum=0,t=0;
		for(int j=0;j<d;j++){
			if((i>>j)&1){
				sum+=100*(j+1)*p[j]+c[j];
				t+=p[j];
			}
		}
		//cout<<"i="<<i<<"sum="<<sum<<"t="<<t<<endl;
		if(sum<g){
			for(int j=d-1;j>=0;j--){
				if(!((i>>j)&1)){
					for(int k=1;k<=p[j]&&sum<g;k++){
						sum+=100*(j+1);
						t++;
					}
				}
			}
		}
		//cout<<"s "<<"sum="<<sum<<"t="<<t<<endl;
		if(sum>=g)
			ans=min(ans,t);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

void piyo(vint v){
	int i;
//for(i=0;i<v.size();i++){
//cout<<" "<<v[i]<<endl;
//}
	if(v.size()>=2)if(v[v.size()-1]==3&&v[v.size()-2]==2){
		swap(v[v.size()-1],v[v.size()-2]);
	}
	for(i=0;i<v.size();i++){
		cout<<v[i]<<endl;
	}
}

void hoge(vint v){
	int i;
	vint vv;
	for(i=1;i<v.size();i++)vv.push_back(v[i]);
	piyo(vv);
}

int main() {
	int n=in();
	int zero=0,one=0;
	int i;
	vint v;
	for(i=0;i<n;i++){
		int buf=in();
		if(buf==0)zero++;
		else if(buf==1)one++;
		else v.push_back(buf);
	}
	sort(v.begin(),v.end());
	if(one==0){
		if(zero%2==0){
			piyo(v);
			for(i=0;i<zero;i++)cout<<0<<endl;
		}else{
			hoge(v);
			for(i=0;i<zero-1;i++)cout<<0<<endl;
			if(!v.empty())cout<<v[0]<<endl;
			cout<<0<<endl;
		}
	}else{
		if(zero%2==0){
			piyo(v);
			for(i=0;i<zero;i++)cout<<0<<endl;
			for(i=0;i<one;i++)cout<<1<<endl;
		}else{
			piyo(v);
			for(i=0;i<zero-1;i++)cout<<0<<endl;
			cout<<1<<endl<<0<<endl;
			for(i=0;i<one-1;i++)cout<<1<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 0
N = int(input())
A = list(map(int, input().split()))

def func(A, plus):
  total = A[0]
  ans = 0
  if plus:
    if A[0] <= 0:
      ans = abs(A[0])+1
      total = 1
  else:
    if A[0] >= 0:
      ans += abs(A[0])+1
      total = -1
  for a in A[1:]:
    t = total + a
    if total * t < 0:
      total = t
      continue
    ans += abs(t)+1
    total = -1 if total > 0 else 1
  return ans

print(min(func(A, True), func(A, False)))

Measured memory_bytes: 14468
//2次元いもす法の基本的な問題
#include<iostream>

using namespace std;

typedef long long ll;

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

ll N;

ll c[1010][1010];

int main() {
    cin >> N;

    rep(i,N) {
        ll x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        x2--,y2--;//[x1,x2) [y1,y2)にする

        c[y1][x1]++;
        c[y1][x2 + 1]--;
        c[y2 + 1][x1]--;
        c[y2 + 1][x2 + 1]++;
    }

    rep(i,1001) {
        rep(j,1000) {
            c[i][j + 1] += c[i][j];
        }
    }
    rep(j,1001) {
        rep(i,1000) {
            c[i + 1][j] += c[i][j];
        }
    }

    ll ans = 0;

    rep(i,1001)rep(j,1001) ans = max(ans,c[i][j]);

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 10992
n,m=map(int,input().split())
al=[]
bl=[]
ansl=[]
for i in range(n):
  al.append(input())
for i in range(m):
  bl.append(input())
for i in range(n):
  a1,a2=map(int,al[i].split())
  b1,b2=map(int,bl[0].split())
  mi=dis=abs(b1-a1)+abs(b2-a2)
  c=1
  for j in range(1,m):
    b1,b2=map(int,bl[j].split())
    dis=abs(b1-a1)+abs(b2-a2)
    if mi>dis:
      mi=dis
      c=j+1
  ansl.append(c)
for i in range(len(ansl)):
  print(ansl[i])


Measured memory_bytes: 3064
#include<iostream>
using namespace std;
int main()
{
    int n, p, sum = 0, max = 0;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> p;
        max = (p > max ? p : max);
        sum += p;
    }
    cout << sum - max / 2 << endl;
    return 0;
}

Measured memory_bytes: 256
use proconio::input;

fn main() {
    input! {
        n: usize,
    }
    let v = enum_divisors(n);
    let mut ans = 0;

    for &nv in &v {
        let num = nv - 1;
        if num != 0 && n / num == n % num {
            ans += num;
        }
    }

    println!("{}", ans);
}

fn enum_divisors(n: usize) -> Vec<usize> {
    let mut res = vec![];
    let mut i = 1;
    while i * i <= n {
        if n % i == 0 {
            res.push(i);
            if n / i != i {
                res.push(n / i);
            }
        }
        i += 1;
    }
    res.sort();
    res
}


Measured memory_bytes: 2148
n = int(input())
s = input()

ans = 0
for i in range(1,n):
  x = s[:i]
  y = s[i:]
  
  tmp = 0
  for each in list(set(x)):
    if each in set(y):
      tmp += 1
  
  ans = max(ans, tmp)
  
print(ans)

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

#define ankit_2305 cerr<<"\nTime taken : "<<(float)(clock()-time_p)/CLOCKS_PER_SEC<<" sec\n";
#define START clock_t
#define TIMER time_p=clock();
#define ll long long

#define MOD 1000000007

using namespace std;

ll dp[101][4][11] = {}; 
string s;

void initdp(int n, int k){
	for(int i=0;i<=k;i++){
		for(int l=0;l<10;l++)
			if(i == 0)
				dp[1][i][l] = 1;
			else
				dp[1][i][l] = l;
	dp[1][i][10] = 9;
	}
}

ll solve(int n, int k, int l){
	
	if(k > n || n == 0){
		return 0;
	}
	
	if(k == 0){
		return 1;
	}
	
	if(dp[n][k][l] != 0){
		return dp[n][k][l];
	}
	
	
	ll res = 0;
	
	if(l > 0){
		res += solve(n-1, k, 10);
		res += (l-1)*solve(n-1, k-1, 10);
		if(l < 10)
			res += solve(n-1, k-1, int(s[(int)s.size() - n + 1] - '0'));
	}
	else
		res += solve(n-1, k, int(s[(int)s.size() - n + 1] - '0'));
	return dp[n][k][l] = res;
}

int main(){
    START TIMER
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	int k;
	cin >> s >> k;
	const int n = s.size();	
	initdp(n, k);
	cout<<solve(n, k, int(s[0] - '0'));
    ankit_2305
    return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<unordered_map>
#include<map>
#include<string>
#include<cstring>
#include<stack>
#include<cmath>

#define vint vector<int>
#define vstr vector<string>
#define vll vector<long long>
#define ll long long
#define pf printf
#define sf scanf
#define sfd(n) scanf("%d", &n)
#define sflf(n) scanf("%lf", &n)
#define sfll(n) scanf("%lld", &n)
#define pfd(n) printf("%d", n)
#define pflf(n) printf("%lf", n)
#define pfll(n) printf("%lld", n)
#define pft	printf("\t")
#define pfn printf("\n")
#define pfk printf(" ")
#define PI 3.1415926
#define MAX 100000
#define M 1e18

using namespace std;

bool F(int n) {
	int a, b, c, d, e;
	a = n/10000;
	b = n%10000/1000;
	c = n%1000/100;
	d = n%100/10;
	e = n%10;
	bool f = true;
	if( a!=e ) {
		f = false;
	}
	if( b!=d ) {
		f = false;
	}
	return f;
}

int main() {
	int a, b;
	sfd(a);
	sfd(b);
	int cnt = 0;
	for( int i=a; i<=b; i++ ) {
		if( F(i) ) {
			cnt++;
		}
	}
	pfd(cnt);
	
	return 0;
}


Measured memory_bytes: 256
k = gets.to_i

queue = (1..9).to_a
ponpon_numbers = []

until queue.empty? || ponpon_numbers.size == k
  current = queue.shift
  ponpon_numbers << current

  last_digit = current % 10
  followings = (last_digit - 1..last_digit + 1).reject { |num|
    num == -1 || num == 10
  }.map { |num| current * 10 + num }
  queue.push *followings
end

puts ponpon_numbers[k - 1]


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

int main(){

  int len[5] = {5,7,5,7,7};
  int n, i;
  string str[41];
  while(cin >> n, n){
    for(i = 0; i < n; i++){
      cin >> str[i];
    }
    for(i = 0; i < n; i++){
      int sum = 0, idx = 0, flag = 0;
      for(int j = i; j < n; j++){
        sum += str[j].size();
        if(len[idx] == sum){
          sum = 0;
          idx++;
        }else if(len[idx] < sum){
          break;
        }
        if(idx == 5){
          flag = 1;
          break;
        }
      }
      if(flag){
        cout << i + 1 << endl;
        break;
      }
    }
  }
  return 0;
}


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

typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> PLL;
typedef pair<P,P> PP;
typedef vector<ll> VECLL;
typedef vector<P> VECP;
typedef priority_queue<P,VECP,greater<P> > PQP;
typedef priority_queue<ll, VECLL, greater<ll> > PQll;

#define rep(i,a,n) for(ll i = a;i < n;i++)   
#define rrep(i,a,n) for(ll i = n; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue; 
#define LINF (ll)1e18
#define INF (int)1e9
#define fs first
#define sc second


const ll MOD = 1e9+7;
 
template <ll MOD>
struct modint{
    ll x;
    modint() : x(0) {}
    modint(ll a): x((a % MOD + MOD) % MOD) {}
    
    
 
    bool operator!() const{return !x;}
 
    bool operator<(const modint &a) const{
        modint res(*this);
        return res.x < a.x;
    }
    
    bool operator>(const modint &a) const{
        modint res(*this);
        return res.x > a.x;
    }
 
    modint &operator+=(const modint &a){
        if((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
 
    modint &operator-=(const modint &a){
        if((x += MOD - a.x) >= MOD) x -= MOD;
        return *this;
    }
 
    modint &operator*=(const modint &a){
        (x *= a.x) %= MOD;
        return *this;
    }
 
    modint &operator/=(const modint &a){
        *this *= a.inv();
        return *this;
    }
 
    modint &operator%=(const modint &a){
        x %= a.x;
        return *this;
    }
 
    modint operator-() const{ return modint(-x); }
 
    modint operator+(const modint &a) const{ return modint(*this) += a; }
    modint operator-(const modint &a) const{ return modint(*this) -= a; }
    modint operator*(const modint &a) const{ return modint(*this) *= a; }
    modint operator/(const modint &a) const{ return modint(*this) /= a; }
    modint operator%(const modint &a) const{ return modint(*this) %= a; }
    bool operator==(const modint &a) const{ return x == a.x; }
    bool operator!=(const modint &a) const{ return x != a.x; }
 
 
    modint pow(ll n) const{
        modint res(1), a(x);
        while(n > 0){
            if(n & 1) res *= a;
            a *= a;
            n /= 2;
        }
        return res;
    }
 
    modint inv() const{
        return this->pow(MOD-2);
    }
 
    friend ostream &operator<<(ostream &os, const modint &m){
        return os << m.x;
    }
 
    friend istream &operator>>(istream &is, modint &m){
        ll t;
        is >> t;
        m = modint<MOD>(t);
        return (is);
    }
    
    static ll get_mod(){ return MOD; }
};
using mint = modint<MOD>;


int main(){
    ll h,w;
    cin >> h >> w;
    char c[h][w];
    rep(i,0,h) rep(j,0,w) cin >> c[i][j];

    mint dp[h][w] = {};
    dp[0][0] = 1;
    rep(i,0,h){
        rep(j,0,w){
            if(i != 0) if(c[i-1][j] == '.') dp[i][j] += dp[i-1][j];
            if(j != 0) if(c[i][j-1] == '.') dp[i][j] += dp[i][j-1];
        }
    }

    cout << dp[h-1][w-1] << endl;
}



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

// modint: mod 計算を int を扱うように扱える構造体
template<int MOD> struct Fp {
long long val;
constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
if (val < 0) val += MOD;
}
constexpr int getmod() { return MOD; }
constexpr Fp operator - () const noexcept {
return val ? MOD - val : 0;
}
constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
constexpr Fp& operator += (const Fp& r) noexcept {
val += r.val;
if (val >= MOD) val -= MOD;
return *this;
}
constexpr Fp& operator -= (const Fp& r) noexcept {
val -= r.val;
if (val < 0) val += MOD;
return *this;
}
constexpr Fp& operator *= (const Fp& r) noexcept {
val = val * r.val % MOD;
return *this;
}
constexpr Fp& operator /= (const Fp& r) noexcept {
long long a = r.val, b = MOD, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
val = val * u % MOD;
if (val < 0) val += MOD;
return *this;
}
constexpr bool operator == (const Fp& r) const noexcept {
return this->val == r.val;
}
constexpr bool operator != (const Fp& r) const noexcept {
return this->val != r.val;
}
friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
return os << x.val;
}
friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
if (n == 0) return 1;
auto t = modpow(a, n / 2);
t = t * t;
if (n & 1) t = t * a;
return t;
}
};

const int MOD = 1000000007;
using mint = Fp<MOD>;

const int MAX_N = 100050;

vector<int> G[MAX_N];

struct DP{
    mint white;
    mint black;
    DP() : white(1),black(1){}
    DP &operator+=(const DP &other) {
        white *= other.white + other.black;
        black *= other.white;
        return *this;
    }
};

DP dfs(int v = 0, int p = -1) {
    DP dp;
    for(int nv : G[v]) {
        if(nv == p) continue;
        dp += dfs(nv,v);
    }
    return dp;
}

int main() {
int N;
cin >> N;
rep(i,N-1) {
    int x,y;
    cin >> x >> y;
    x--; y--;
    G[x].push_back(y);
    G[y].push_back(x);
}
DP ans = dfs(0);
cout << ans.black + ans.white << endl;
return 0;
}


Measured memory_bytes: 12672
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REPR(i,n) for (int i=(int)(n)-1;i>=0;--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
#define tpl(...) make_tuple(__VA_ARGS__)
const int INF = 0x3f3f3f3f;
const double EPS = 1e-8;
const double PI = acos(-1);
const int dy[] = {-1,0,1,0};
const int dx[] = {0,1,0,-1};
typedef long long ll;
typedef pair<int,int> pii;
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; }
template<typename Ch,typename Tr,typename C,typename=decltype(begin(C()))>basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>&os,
const C& c){os<<'[';for(auto i=begin(c);i!=end(c);++i)os<<(i==begin(c)?"":" ")<<*i;return os<<']';}
template<class S,class T>ostream&operator<<(ostream &o,const pair<S,T>&t){return o<<'('<<t.first<<','<<t.second<<')';}
template<int N,class Tp>void output(ostream&,const Tp&){}
template<int N,class Tp,class,class ...Ts>void output(ostream &o,const Tp&t){if(N)o<<',';o<<get<N>(t);output<N+1,Tp,Ts...>(o,t);}
template<class ...Ts>ostream&operator<<(ostream&o,const tuple<Ts...>&t){o<<'(';output<0,tuple<Ts...>,Ts...>(o,t);return o<<')';}
template<class T>void output(T t,char z=10){if(t<0)t=-t,putchar(45);int c[20];
int k=0;while(t)c[k++]=t%10,t/=10;for(k||(c[k++]=0);k;)putchar(c[--k]^48);putchar(z);}
template<class T>void outputs(T t){output(t);}
template<class S,class ...T>void outputs(S a,T...t){output(a,32);outputs(t...);}
template<class T>void output(T *a,int n){REP(i,n)cout<<a[i]<<(i!=n-1?',':'\n');}
template<class T>void output(T *a,int n,int m){REP(i,n)output(a[i],m);}
template<class T>bool input(T &t){int n=1,c;for(t=0;!isdigit(c=getchar())&&~c&&c-45;);
if(!~c)return 0;for(c-45&&(n=0,t=c^48);isdigit(c=getchar());)t=10*t+c-48;t=n?-t:t;return 1;}
template<class S,class ...T>bool input(S&a,T&...t){input(a);return input(t...);}
template<class T>bool inputs(T *a, int n) { REP(i,n) if(!input(a[i])) return 0; return 1;}

int h[100205];
ll dp[1000205];

int main() {
  int n,k;
  while(cin>>n>>k) {
    inputs(h,n);
    memset(dp,0x3f,sizeof(dp));
    dp[0] = 0;
    REP(i,n) {
      REP(j,k) {
        chmin(dp[i+j+1], dp[i] + abs(h[i+j+1] - h[i]));
      }
    }
    cout << dp[n-1] << endl;
  }
}


Measured memory_bytes: 8448
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1<<29;
const int MOD = 1e9+7;
const ll LINF = 1e18;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    REP(i,v.size()){if(i)os<<" ";os<<v[i];}return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
    REP(i,v.size()){if(i)os<<endl;os<<v[i];}return os;}

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




int main(int argc, const char * argv[]) {
    
    // remove the bottom 3 lines when you submit this code.
    std::ifstream in("sample.txt");
    std::cin.rdbuf(in.rdbuf());

    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N; cin >> N;
    vector<int> A(N);
    vector<int> B(N);
    vector<int> C(N);
    
    rep(i,N) cin >> A[i];
    rep(i,N) cin >> B[i];
    rep(i,N) cin >> C[i];
    
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());
    
    long long Ans = 0;

    
    for (int j = 0; j < N; j++) {
        auto itr_A = lower_bound(A.begin(),A.end(),B[j]);
        auto itr_C = upper_bound(C.begin(),C.end(),B[j]);
        
        long long idx_A = distance(A.begin(),itr_A);
        long long idx_C = distance(C.begin(),itr_C);
        
        Ans += (    idx_A   *   (N - idx_C)   );
    }
    
     
    
    
    
    
    
    
    cout << Ans << endl;
    
    
    return 0;
    
}



Measured memory_bytes: 1408
#coding:utf-8
x=[[[0 for i in range(10)] for j in range(3)]for k in range(4)]

n=int(input())
for i in range(n):
    b,f,r,v=list(map(int,input().split()))

    x[b-1][f-1][r-1]+=v


for line,i in enumerate(x):
    for j in i:
        for k in j:
            print(" "+str(k),end="")
        print("")

    if line!=3:
        for i in range(20):
            print("#",end="")
        print("")

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

int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    int R[n];
    for (int i = 0; i < n; i++) {
        cin >> R[i];
    }

    int maxV = -2000000000;
    int minV = R[0];

    for (int i = 1; i < n; i++) {
        maxV = max(maxV, R[i] - minV);
        minV = min(minV, R[i]);
    }

    cout << maxV << endl;
    return 0;
}



Measured memory_bytes: 3836
#include <bits/stdc++.h>
using namespace std;
int ans=0;
string s;
const double eps=1e-9;
typedef vector<int> vi;
typedef long long ll;
typedef pair<string,string> pss;
vector<pss> vpss;
int main(void)
{
  int n;
  cin >> n;
  for(int i=0;i<n;i++)
    {
      string tmp1,tmp2;
      cin >> tmp1 >> tmp2;
      vpss.push_back(pss(tmp1,tmp2));
    }
  for(int i=0;i<n;i++)
    {
      int ans=0;
      int num=1;
      string num1=vpss[i].first;
      string num2=vpss[i].second;
      for(int j=0;j<num1.size();j++)
	{
	  if(num1[j]=='m')
	    {
	      ans+=1000*num;
	      num=1;
	    }
	  else if(num1[j]=='c')
	    {
	      ans+=100*num;
	      num=1;
	    }
	  else if(num1[j]=='x')
	    {
	      ans+=10*num;
	      num=1;
	    }
	  else if(num1[j]=='i')
	    {
	      ans+=num;
	      num=1;
	    }
	  else
	    {
	      num=(int)(num1[j]-'0');
	    }
	}
      for(int j=0;j<num2.size();j++)
	{
	  if(num2[j]=='m')
	    {
	      ans+=1000*num;
	      num=1;
	    }
	  else if(num2[j]=='c')
	    {
	      ans+=100*num;
	      num=1;
	    }
	  else if(num2[j]=='x')
	    {
	      ans+=10*num;
	      num=1;
	    }
	  else if(num2[j]=='i')
	    {
	      ans+=num;
	      num=1;
	    }
	  else
	    {
	      num=(int)(num2[j]-'0');
	    }
	}
      int tho=ans/1000;
      ans%=1000;
      int hun=ans/100;
      ans%=100;
      int ten=ans/10;
      ans%=10;
      int one=ans;
      string mcxi="";
      if(tho>0)
	{
	  if(tho>1)
	    {
	      mcxi+=to_string(tho);
	    }
	  mcxi+='m';
	}
      if(hun>0)
	{
	  if(hun>1)
	    {
	      mcxi+=to_string(hun);
	    }
	  mcxi+='c';
	}
      if(ten>0)
	{
	  if(ten>1)
	    {
	      mcxi+=to_string(ten);
	    }
	  mcxi+='x';
	}
      if(one>0)
	{
	  if(one>1)
	    {
	      mcxi+=to_string(one);
	    }
	  mcxi+='i';
	}
      cout << mcxi << endl;
    }
  return 0;
}



Measured memory_bytes: 3484
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(arr) memset(arr, 0, sizeof(arr))
const int inf = 0x3f3f3f3f;
int a[100001],cnt,out=999,b[1000001];
bool cmp(int x,int y)
{
	return x>y;
}
void dfs(int x,int ans){
	if(b[x]<=ans) return;
	if(ans>=out) return;
	b[x]=ans;
	if(x==0){
		out=ans;
		return;
	}
	for(re int i=1;i<=cnt;i++){
		if(a[i]<=x) dfs(x-a[i],ans+1);
	}
}
int main() 
{
	memset(b,9,sizeof(b));
	int aa=1;
	while(aa*6<100000) a[++cnt]=aa*6,aa*=6;
	aa=1;
	while(aa*9<100000) a[++cnt]=aa*9,aa*=9;
	a[++cnt]=1;
	sort(a+1,a+cnt+1,cmp);
	int n;
	cin>>n;
	dfs(n,0);
	cout<<out;
}

Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll int K,A,B,x,y; 
    cin>>K;
    cin>>A>>B;
    x=B/K;
    y=A/K;
    if(x>y)
    cout<<"OK"<<endl;
    else if(A%K==0)
        cout<<"OK"<<endl;
    else
    cout<<"NG"<<endl;
    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
using namespace std;
int main(void){
    int a[4],b[4],i,s=0,t=0;
    for(i=0;i<4;i++){
        cin>>a[i];
        s+=a[i];
    }
    for(i=0;i<4;i++){
        cin>>b[i];
        t+=b[i];
    }
    if(s==t) cout<<s<<endl;
    else if(s>t) cout<<s<<endl;
    else if(t>s) cout<<t<<endl;
    
}



Measured memory_bytes: 3080
import bisect
import sys

verbose = False

def test(d, k):
    sd = sorted(d)
    uniq_d = []
    pop_d = {}
    for num in sd:
        if num in pop_d:
            pop_d[num] += 1
        else:
            pop_d[num] = 1
            uniq_d.append(num)
    uniq_d = sorted(uniq_d)
    pop_uniq_d = []
    cum_pop_uniq_d = []
    prev_pop = 0
    for num in uniq_d:
        pop = pop_d[num]
        pop_uniq_d.append(pop)
        prev_pop += pop
        cum_pop_uniq_d.append(prev_pop)
    if prev_pop % 2 == 1:
        return 0
    if verbose:
        print("total pop =", prev_pop)
    target = prev_pop // 2
    if verbose:
        print("target = ", target)
    target_off = bisect.bisect_right(cum_pop_uniq_d, target)
    if verbose:
        print("target_off = ", target_off)
    if target_off == 0:
        return 0
    if verbose:
        print( "uniq_d = ", uniq_d)
        print( "cum_pop = ", cum_pop_uniq_d)
        print( "uniq_d[target_off] = ", uniq_d[target_off])
        print( "cum_pop_uniq_d[target_off] = ", cum_pop_uniq_d[target_off])
    if cum_pop_uniq_d[target_off-1] != target:
        return 0
    ans = uniq_d[target_off] - uniq_d[target_off-1]
    return ans


def main():
    rv = 0
    #with sys.stdin as input:
    input = sys.stdin
    Nline = input.readline()
    N = int(Nline)
    args = input.readline()
    vargs = args.split()
    d = [int(arg) for arg in vargs]
    rv = test(d, N)
    print(rv)

def mock():
    rv = test( [9, 1, 4, 4, 6, 7], 6)
    print(rv)
    rv = test([9, 1, 14, 5, 5, 4, 4, 14], 8)
    print(rv)
    rv = test([99592, 10342, 29105, 78532, 83018, 11639, 92015, 77204, 30914, 21912, 34519, 80835, 100000, 1], 14)
    print(rv)

if __name__ == '__main__':
    main()

Measured memory_bytes: 21480
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <random>
using namespace std;

#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define uniq(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef complex<double> comp;
typedef vector< vector<ld> > matrix;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const int inf = 1e9 + 9;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);

ll h, w, a, b;

ll mod_pow(ll x, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = (res * x) % mod;
        x = (x * x) % mod;
        n >>= 1;
    }
    return res;
}

ll mod_inverse(ll x) {
    return mod_pow(x, mod-2);
}

const int max_n = 200010;
ll fact[max_n];
ll fact_inv[max_n];
void calc_fact() {
    fact[0] = 1;
    for (ll i = 1; i < max_n; i++)
        fact[i] = (fact[i-1] * i) % mod;
    fact_inv[max_n-1] = mod_inverse(fact[max_n-1]);
    for (ll i = max_n-2; i >= 0; i--)
        fact_inv[i] = (fact_inv[i+1] * (i+1)) % mod;
}
ll mod_comb(ll n, ll k) {
    if (n < 0 || k < 0 || n < k) return 0;
    return (fact[n] * fact_inv[k] % mod) * fact_inv[n-k] % mod;
}

ll solve() {
    ll res = 0;
    calc_fact();
    for (int i = 0; i < h-a; i++) {
        res = (res + mod_comb(i+b-1, i) * mod_comb(w-b-1+h-i-1, h-i-1) % mod) % mod;
    }
    return res;
}

void input() {
    cin >> h >> w >> a >> b;
}

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

    input();
    cout << solve() << endl;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const int MOD=1e9+7;
const long double Pi=acos(-1);
using  P=pair<ll,ll>;
ll gcd(ll a,ll b){//aとbの最大公約数を返す
  if(a%b==0){return b;}
  else{return gcd(b,a%b);}
}
ll lcm(ll a,ll b){//aとbの最小公倍数を返す
  return a*b/gcd(a,b);
}
ll pow(ll x,ll y){//x^yを返す
  ll tmp=x,res=1;
  while(y){
    if(y%2){res=res*tmp%MOD;}
    y>>=1;
    tmp=tmp*tmp%MOD;
  }
  return res;
}
ll nature(ll a){//絶対値を返す
  if(a>=0){return(a);}
  else{return(-1*a);}
}
ll prime(ll a){//素数なら1を返す
  if(a==2){return 1;}
  else if(a%2==0 || a==1){return 0;}
  for(ll i=3;i*i<=a;i+=2){if(a%i==0){return 0;}}
  return 1;
}
int main(){
  ll N;
  cin>>N;
  vector<ll> A(N);
  vector<ll> B(N);
  vector<ll> C(N-1);
  ll sum=0;
  for(ll i=0;i<N;i++){
    cin>>A.at(i);
  }
  for(ll i=0;i<N;i++){
    cin>>B.at(i);
    sum+=B.at(i);
  }
  for(ll i=0;i<N-1;i++){
    cin>>C.at(i);
  }
  for(ll i=0;i<N-1;i++){
    if(A.at(i)+1==A.at(i+1)){
      sum+=C.at(A.at(i)-1);
    }
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(it,st,en) for(int it=(st);it<(int)(en);++it)
#define all(c) (c).begin(), (c).end()
#define debug(x) cerr << #x << " = " << x << endl
#define eb emplace_back
#define X first
#define Y second
typedef long long int ll; 
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pii;

const int MAX_PR = 5000000;
bitset<MAX_PR> isprime;
vi eratosthenes_sieve(int lim) {
  isprime.set(); isprime[0] = isprime[1] = 0;
  for (int i = 4; i < lim; i += 2) isprime[i] = 0;
  for (int i = 3; i*i < lim; i += 2) if (isprime[i])
    for (int j = i*i; j < lim; j += i*2) isprime[j] = 0;
  vi pr;
  rep(i,2,lim) if (isprime[i]) pr.push_back(i);
  return pr;
}

ll primes[] = {
  2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,
  97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n = 500;
    vector<vector<ll> > v(n, vector<ll>(n));
    vi p = eratosthenes_sieve(500000);
    debug(p.size());
    set<ll> forbidden;
    rep(i,0,n) {
      ll x = p[i/2];
      rep(j,0,n) if((i+j)&1) {
        ll y = p[205+j/2];
        v[i][j] = x*y;
        while(forbidden.count(v[i][j])) v[i][j] += x*y;
        forbidden.insert(v[i][j]);
      }
    }
    rep(i,0,n) rep(j,0,n/2) {
      int x = i, y = 2*j + (i&1);
      ll p = 1;
      auto f = [&](ll a) { return p/__gcd(a,p)*a; };
      if(x != 0)   p = f(v[x-1][y]);
      if(x != n-1) p = f(v[x+1][y]);
      if(y != 0)   p = f(v[x][y-1]);
      if(y != n-1) p = f(v[x][y+1]);
      v[x][y] = p+1;
      while(forbidden.count(v[x][y])) v[x][y] += p;
      forbidden.insert(v[x][y]);
    }
    debug(forbidden.size());
    assert(*(--forbidden.end()) < 1e15);
    assert(*forbidden.begin() > 0);

    cin >> n;
    rep(i,0,n) rep(j,0,n) {
      cout << v[i][j] << " \n"[j == n-1];
    }
    return 0;
}


Measured memory_bytes: 17404
#include <bits/stdc++.h>
#define pi 3.14159
using namespace std;
int main(){
	string n;
	cin >> n;
	int a=0;
	for(int i=0;i<n.size();i++){
		a+=(n[i]-'0');
	}
	int m=((int)n[0]-(int)'0'-1)+((n.size()-1)*9);
	cout << max(a,m);
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;
using i64 = int64_t;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
const int INF = (1 << 30);
const i64 INFL = (1LL << 62);
const i64 MOD = 1000000007;
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <class T>
T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
template <class T>
i64 mod_pow(i64 a, i64 n, T mod) {
  mod = (i64)mod;
  i64 res = 1, p = a % mod;
  while (n) {
    if (n & 1) res = res * p % mod;
    p = p * p % mod;
    n >>= 1;
  }
  return res;
}
void print() { std::cout << std::endl; }
template <typename T, typename... A>
void print(const T& first, const A&... rest) {
  cout << sizeof...(rest) << endl;
  std::cout << first;
  if (sizeof...(rest)) std::cout << " ";
  print(rest...);
}
template <typename... A>
void print(const A&... rest) {
  print(rest...);
}
template <typename A>
void print(const std::vector<A>& v) {
  std::for_each(v.begin(), v.end(), [](A x) { std::cout << x << " "; });
  std::cout << std::endl;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  i64 n;
  cin >> n;
  vector<i64> l(n);
  rep(i, n) { cin >> l[i]; }
  i64 ans{0};
  sort(all(l));
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      i64 a{l[i]};
      i64 b{l[j]};
      int it = lower_bound(l.begin() + j, l.end(), a + b) - l.begin();
      ans += max(0, it - j - 1);
    }
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <set>
#include <cstdio>
#include <memory>
#include <cmath>
#include <chrono>
#include <random>
#include <map>
#include <sstream>
#include <queue>
#include <cassert>
#include <cstdio>
#define x first
#define y second
#define int long long
#define pii pair<int, int>

using namespace std;

const int N = 1e6 + 10;
const int inf = 1e18;
const int mod = 998244353;

//mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

int k;

int32_t main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> k;

	int res = 0;

	for (int i = 1; i <= k; ++i)
		for (int j = 1; j <= k; ++j)
			for (int z = 1; z <= k; ++z)
				res += __gcd(__gcd(i, j), z);

	cout << res << endl;
}

Measured memory_bytes: 3652
#include<iostream>
using namespace std;
int main(){
  int n; cin >> n;
  int a[100050];
  for(int i=1;i<=n;i++) cin >> a[i];
  int j = 1;
  for(int c=1;c<=n;c++){
    int k = a[j];
    if(k==2){
      cout << c << endl;
      return 0;
    }
    j = k;
  }
  
  cout << -1 << endl;
}

Measured memory_bytes: 640