akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#include <bitset>
using namespace std;
const double EPS = 1e-10;
const double INF = 1e12;

struct Point{
    double x,y,z;
    Point(double x, double y, double z):x(x), y(y), z(z){}
    Point(){}
    Point &operator +=(const Point &a){ x+=a.x; y+=a.y; z+=a.z; return *this; }
    Point &operator -=(const Point &a){ x-=a.x; y-=a.y; z-=a.z; return *this; }
    Point operator +(const Point &a) const{ return Point(x+a.x, y+a.y, z+a.z); }
    Point operator -(const Point &a) const{ return Point(x-a.x, y-a.y, z-a.z); }
    Point operator *(const double &a) const{ return Point(a*x, a*y, a*z); }
};
struct Obj{
    Point p;
    double r;
    Obj(Point &p, double r):p(p), r(r){}
    Obj(){}
};

double dot(const Point &a, const Point &b){
    return a.x*b.x +a.y*b.y +a.z*b.z;
}
double Length(const Point &a){
    return sqrt(dot(a, a));
}

double distLP3(Point p, Point q, Point c){
    p -= c; q -= c;
    Point v = q-p;
    double t = -dot(v, p) / dot(v, v);
    if(t<0) return Length(p);
    if(t>1) return Length(q);
    return Length(p + v*t);
}

int main(){
	while(1){
		int n,m,r;
		cin >> n >> m >> r;
		if(n==0 && m==0 && r==0) break;
		vector<Obj> s(n), t(m);
		for(int i=0; i<n; i++){
			cin >> s[i].p.x >> s[i].p.y >> s[i].p.z >> s[i].r;
		}
		for(int i=0; i<m; i++){
			cin >> t[i].p.x >> t[i].p.y >> t[i].p.z >> t[i].r;
		}
		Point e;
		cin >> e.x >> e.y >> e.z;
		
		vector<vector<int> > shut(m);
		for(int i=0; i<m; i++){
			for(int j=0; j<n; j++){
				if(distLP3(e, t[i].p, s[j].p) +EPS < s[j].r &&
					(Length(e -s[j].p) > s[j].r +EPS || Length(t[i].p -s[j].p) > s[j].r +EPS) ){
					shut[i].push_back(j);
				}
			}
		}
		vector<double> illum(m);
		for(int i=0; i<m; i++){
			illum[i] = t[i].r / dot(t[i].p -e, t[i].p -e);
		}
		
		double ans = 0;
		for(int i=0; i<(1<<m); i++){
			bitset<2000> bal;
			double total = 0;
			int count = 0;
			for(int j=0; j<m; j++){
				if((1<<j & i) != 0){
					for(int k=0; k<(int)shut[j].size(); k++){
						if(bal[shut[j][k]] == 0){
							bal[shut[j][k]] = 1;
							count++;
						}
					}
					total += illum[j];
				}
				if(count > r) break; 
			}
			if(count <= r){
				ans = max(ans, total);
			}
		}
		cout << fixed;
		cout << setprecision(10);
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 3328
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
from sys import exit
n, k = getList()

if k > (n-1) * (n-2) // 2:
    print(-1)
    exit()

if k <= n:
    var = []
    for i in range(1, n):
        for j in range(i+1, n+1):
            var.append((i, j))

    for i in range(1, k+1):
        try:
            var.remove((i, i+1))
        except:
            pass

    if k == n:
        var.remove((1, n))

    print(len(var))
    for v in var:
        print(v[0], v[1])
    exit()


def build_hub(lis, hub):
    for l in lis:
        print(l, hub)

def kanzen(beg, end):
    for i in range(beg, end):
        for j in range(i+1, end+1):
            print(i, j)


rui = []
for i in range(1, n):
    rui.append(i*(i-1)//2)

# print(rui)
for i, ru in enumerate(rui):
    if k <= ru:
        use_hub = i + 1
        already = ru
        break

rem_var = n - use_hub
# print(use_hub, rem_var, ru)

ans_num = (use_hub * rem_var) + (rem_var * (rem_var-1) // 2) + (ru - k)
print(ans_num)

for i in range(rem_var):
    build_hub(range(1, use_hub+1), n-i)
# print("--------------")
kanzen(use_hub+1, n)
# print("-------------")
for i in range(ru-k):
    print(i+1, i+2)

"""
1,3,6,10,15,21,,,
"""

Measured memory_bytes: 43120
import java.io.IOException;
import java.util.Scanner;

class Main{
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        if (a < b && b < c){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }    
    }
}

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

#define pb push_back
#define vi vector < int >
#define ii pair < int, int >
#define vii vector < pair < int, int > >
#define vvi vector < vector < int > >
#define ll long long
#define X first
#define Y second
#define mp make_pair
#define FOR( i, lo, hi ) for( int i = (lo);i < (hi);i++ )
#define DFOR( i, hi, lo ) for( int i = (hi);i >= (lo);i-- )
#define pqueue priority_queue

using namespace std;

int main()
{
	int r;cin >> r;
	cout << r * r  * 3 << "\n";
	return 0;
}


Measured memory_bytes: 256
ls = list(map(str,input()))
a=[]
b=[]
c=[]
d=[]
e=[]
f=[]
n = len(ls)
for i in range(int((n-1)/2)):
    a.append(ls[i])
for j in range(int((n+1)/2),n):
    b.append(ls[j])
b.reverse()
if b != a:
    print('No')
else:
    if (n-1) % 4 ==0:
        for k in range(int((n-1)/4)):
            c.append(a[k])
        for l in range(int((n-1)/4),int((n-1)/2)):
            d.append(a[l])
        for m in range(int((n-1)/4)):
            e.append(b[m])
        for n in range(int((n-1)/4),int((n-1)/2)):
            f.append(b[n])
        d.reverse()
        f.reverse()
        if (c == d) and (e == f):
            print('Yes')
        else:
            print('No')
    else:
        for k in range(int((n-3)/4)):
            c.append(a[k])
        for l in range(int((n+1)/4),int((n-1)/2)):
            d.append(a[l])
        for m in range(int((n-3)/4)):
            e.append(b[m])
        for n in range(int((n+1)/4),int((n-1)/2)):
            f.append(b[n])
        d.reverse()
        f.reverse()
        if (c == d) and (e == f):
            print('Yes')
        else:
            print('No')
        


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"

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
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,m,k;
    cin>>n>>m>>k;
    ll arr[n],brr[m];
    for(ll i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    for(ll i=0;i<m;i++)
    {
        cin>>brr[i];
    }
    vector<ll> pr1(n);
    pr1[0]=arr[0];
    for(ll i=1;i<n;i++)
    {
        pr1[i]=pr1[i-1]+arr[i];

    }
    vector<ll> pr2(m);
    pr2[0]=brr[0];
    for(ll i=1;i<m;i++)
    {
        pr2[i]=pr2[i-1]+brr[i];
    }
    ll maxa=0;
    for(ll i=0;i<n;i++)
    {
    	if((upper_bound (pr2.begin(), pr2.end(), (k-pr1[i]))-pr2.begin())>=0 && (k-pr1[i])>=0)
    	{
    	
        if(maxa<(i+1+(upper_bound (pr2.begin(), pr2.end(), (k-pr1[i]))-pr2.begin())))
            {
            maxa=i+1+(upper_bound (pr2.begin(), pr2.end(), (k-pr1[i]))-pr2.begin());
          //  cout<<maxa<<endl;
            }
    	}
    }
    ll va=(upper_bound (pr2.begin(), pr2.end(), (k))-pr2.begin());
    ll v2=(upper_bound (pr1.begin(), pr1.end(), (k))-pr1.begin());
    cout<<max(maxa,max(va,v2))<<endl;
	return 0;
}

Measured memory_bytes: 9504
#include <bits/stdc++.h>
  using namespace std;
  #define int long long int
  #define loop(i,a,b) for(int i=a;i<b;i++)
  #define vi vector<int>
  #define pb push_back
  int32_t main()
  {
    //write your code here
    
         int n;cin>>n;
         if(n%1000==0)
         cout<<"0\n";
         else
         {
         int ans=1000-(n%1000);
         cout<<ans<<endl;
         }
    return 0;
  }

Measured memory_bytes: 3564
#include <iostream>
#define rep(i, n)   for(int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

const ll mod = 1e9+7;
ll fact[200010];      //階乗の累積積
ll invfact[200010];   //逆元階乗の累積積

ll nCr(ll n, ll r){ //Combination
    ll ret = fact[n];
    (ret *= invfact[n-r]) %= mod;
    (ret *= invfact[r]) %= mod;
    return ret;
}

ll extgcd(ll a, ll b, ll &x, ll &y){
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }else{
        ll g = extgcd(b, a%b, x, y);
        ll nextx = y;   ll nexty = x-(a/b)*y;
        x = nextx;  y = nexty;
        return g;
    }
}

int main(){
    int h,w,a,b;    cin >> h >> w >> a >> b;
    //階乗テーブル作成
    fact[0] = 1;
    for(ll i = 1; i <= 200000; i++){
        fact[i] = (fact[i-1]*i)%mod;
    }
    //逆元階乗テーブル作成
    for(ll i = 0; i <= 200000; i++){
        ll x,y;
        ll g = extgcd(fact[i], mod, x, y);
        while(x < 0)    x += mod;
        x %= mod;
        invfact[i] = x;
    }
    ll ans = 0;
    for(int i = b; i < w; i++){
        ll tmp = nCr((h-a-1)+i, h-a-1);
        (tmp *= nCr((a-1)+(w-i-1), a-1)) %= mod;
        (ans += tmp) %= mod;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3328
import java.util.*;
import java.io.PrintWriter;
import static java.lang.Integer.*;
import static java.lang.Long.*;
import static java.lang.Math.*;
import static java.lang.System.*;

public class Main {
	public static final int MOD = 1000000007;
	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(in);
		int h = parseInt(sc.next());
		int a = parseInt(sc.next());
		sc.close();
		out.println((int)ceil((double)h/a));
	}
}


Measured memory_bytes: 23764
<?php

fscanf(STDIN, "%d", $N);
fscanf(STDIN, "%s", $S);
$list = str_split($S);
const S = "S";
const W = "W";
$s_list = [[S,S], [S,W], [W,S], [W,W]];

foreach($s_list as $this_list){
    $last = $this_list[0];
    $now = $this_list[1];
    $ans = $this_list;

    for($i=1;$i<$N-1;$i++){
        if($list[$i] === "o"){
            if($now === S){
                $tmp = $last;
                $last = $now;
                $now = $tmp;
                $ans[] = $now;
            }else{
                $tmp = $last;
                $last = $now;
                $now = ($tmp === S)?W:S;
                $ans[] = $now;
            }
        }else{
            if($now === W){
                $tmp = $last;
                $last = $now;
                $now = $tmp;
                $ans[] = $now;
            }else{
                $tmp = $last;
                $last = $now;
                $now = ($tmp === S)?W:S;
                $ans[] = $now;
            }
        }
    }
    $ok = 0;
    if($list[$N-1] === "o"){
        if($ans[$N-1] === S){
            if($ans[$N-2] === $ans[0]){
                $ok = 1;
            }
        }else{
            if($ans[$N-2] !== $ans[0]){
                $ok = 1;
            }
        }
    }else{
        if($ans[$N-1] === W){
            if($ans[$N-2] === $ans[0]){
                $ok = 1;
            }
        }else{
            if($ans[$N-2] !== $ans[0]){
                $ok = 1;
            }
        }
    }
    if($ok === 0){
        continue;
    }
    if($list[0] === "o"){
        if($ans[0] === S){
            if($ans[$N-1] === $ans[1]){
                $ok = 2;
            }
        }else{
            if($ans[$N-1] !== $ans[1]){
                $ok = 2;
            }
        }
    }else{
        if($ans[0] === W){
            if($ans[$N-1] === $ans[1]){
                $ok = 2;
            }
        }else{
            if($ans[$N-1] !== $ans[1]){
                $ok = 2;
            }
        }
    }
    if($ok === 2){
        echo implode($ans);
        exit;
    }


}
echo -1;

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

int A,B;
int ans;

int main() {
	cin >> A >> B;
	if (A >= 6 && A <= 12) {
		B /= 2;
	}
	else if (A <= 5) {
		B = 0;
	}

	cout << B << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    int h;
    int w;
    char[][] map;
    boolean[][] visited;

    void run() {
        Scanner sc = new Scanner(System.in);

        h = sc.nextInt();
        w = sc.nextInt();

        map = new char[h][w];
        visited = new boolean[h][w];

        for (int i = 0; i < h; i++) {
            map[i] = sc.next().toCharArray();
        }

        List<Integer> blacks = new ArrayList<>();

        // 1000 * 1000
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (map[i][j] == '#') {
                    visited[i][j] = true;
                    blacks.add(toPoint(i, j));
                }
            }
        }

        int count = -1;
        while (true) {
            if (blacks.isEmpty()) break;
            count++;
            blacks = next(blacks);
        }

        // write your code
        System.out.println(count);
    }

    List<Integer> next(List<Integer> blacks) {
        List<Integer> newBlacks = new ArrayList<>();

        for (int bp : blacks) {
            int i = bp / 1000;
            int j = bp % 1000;

            if (bp % 1000 != 0 && !visited[i][j - 1]) {
                visited[i][j - 1] = true;
                newBlacks.add(bp - 1);
            }
            if (bp % 1000 != w - 1 && !visited[i][j + 1]) {
                visited[i][j + 1] = true;
                newBlacks.add(bp + 1);
            }
            if (bp / 1000 != 0 && !visited[i - 1][j]) {
                visited[i - 1][j] = true;
                newBlacks.add(bp - 1000);
            }
            if (bp / 1000 != h - 1 && !visited[i + 1][j]) {
                visited[i + 1][j] = true;
                newBlacks.add(bp + 1000);
            }
        }
        return newBlacks;
    }


    int toPoint(int i, int j) {
        return i * 1000 + j;
    }


    void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }

    public static void main(String[] args) {
        new Main().run();
    }
}


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

typedef long long ll;	
const int nax = 1e5 + 5;
const int mod = 1e9 + 7;
                     
ll solve(ll a,ll b){
	a = a % mod;
	if(b == 0) return 1;
	else if((b % 2) == 0) return solve((a * a) % mod,b / 2) % mod;
	else return (a * (solve((a * a) % mod,b / 2) % mod)) % mod;
}

template<typename T> void max_self(T &a,T b) { a = max(a,b); }
template<typename T> void min_self(T &a,T b) { a = min(a,b); }

vector<int> adj[nax];
int indegree[nax];
int ans = 0;
int dp[nax];
bool vis[nax];

void dfs(int source){
	if(vis[source]) return;
	vis[source] = true;
	for(auto u : adj[source]){
		--indegree[u];
   		dp[u] = max(dp[u],dp[source] + 1); 
		ans = max(ans,dp[u]);
		if(indegree[u] == 0) dfs(u);
	}
	return;
}

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

	for(int i = 0; i < nax; ++i){
		indegree[i] = 0;
		dp[i] = 0;
		vis[i] = false;
	}

	int n,m;
	cin >> n >> m;

	for(int i = 0; i < m; ++i){
		int u,v;
		cin >> u >> v;
		adj[u].push_back(v);
		++indegree[v];
	}

	for(int i = 1; i <= n; ++i){
		if(indegree[i] == 0 && vis[i] == 0) dfs(i);
	}

	for(int i = 1; i <= n; ++i) ans = max(ans,dp[i]);

	cout << ans;
	return 0;
}

Measured memory_bytes: 9728
N = int(input())
S = input()
## [color][idx]
RGB = [[0 for i in range(N)] for j in "RGB"]
for idx,ch in enumerate(S):
  for color_idx in [0,1,2]:
    RGB[color_idx][idx] = RGB[color_idx][idx-1]
  RGB["RGB".index(ch)][idx] += 1
ans = 0
for i in range(N-2):
  for j in range(i+1,N-1):
    if S[i] != S[j]:
      nokori = {"R","G","B"} - {S[i],S[j]}
      n_ch = [ch for ch in nokori][0]
      n_idx = "RGB".index(n_ch)
      ans += RGB[n_idx][-1]-RGB[n_idx][j]-(1 if (j+(j-i)<N and  S[j + (j-i)] == n_ch) else 0)
print (ans)

Measured memory_bytes: 69480
#include <iostream>
#include <queue>
#include <vector>

using namespace std;
queue<int>q;
vector<int>g[2002];
int v[2002], nr[2002];
int main()
{
    int n, x, y;
    cin>>n>>x>>y;
    g[1].push_back(2);
    g[n].push_back(n-1);
    g[x].push_back(y);
    g[y].push_back(x);
    for(int i=2;i<n;i++){
        g[i].push_back(i-1);
        g[i].push_back(i+1);
    }
    for(int i=1;i<=n;i++){
        q.push(i);
        nr[i]=1;
        while(q.size()!=0){
            int a=q.front();
            for(int j=0;j<g[a].size();j++){
                if(nr[g[a][j]]==0){
                    q.push(g[a][j]);
                    nr[g[a][j]]=nr[a]+1;
                    v[nr[a]]++;
                }
            }
            q.pop();
        }
        for(int i=1;i<=n;i++){
            nr[i]=0;
        }
    }
    for(int i=1;i<n;i++){
        cout<<v[i]/2<<"\n";
    }
    return 0;
}


Measured memory_bytes: 384
def tmp(n):
    if n >= 1800 and n < 2000:
        return 1
    elif n >= 1600 and n < 1800:
        return 2
    elif n >= 1400 and n < 1600:
        return 3
    elif n >= 1200 and n < 1400:
        return 4
    elif n >= 1000 and n < 1200:
        return 5
    elif n >= 800 and n < 1000:
        return 6
    elif n >= 600 and n < 800:
        return 7
    elif n >= 400 and n < 600:
        return 8
    
n = int(input())
print(tmp(n))

Measured memory_bytes: 61740
// 2013/09/10 Tazoe

#include <iostream>
using namespace std;

int main()
{
	int L, A, B, C, D;
	cin >> L;
	cin >> A;
	cin >> B;
	cin >> C;
	cin >> D;

	int E = A/C;
	if(A%C!=0){
		E++;
	}

	int F = B/D;
	if(B%D!=0){
		F++;
	}

	int G;
	if(E>F){
		G = L-E;
	}
	else{
		G = L-F;
	}

	cout << G << '\n';

	return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define all(a) a.begin(),a.end()
#define pb push_back
using namespace std;
typedef long long int ll;


int main(){
	
	//#ifndef ONLINE_JUDGE
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	//#endif
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;

	ll n,a,b;
	cin>>n>>a>>b;
	ll q=n/(a+b);
	ll r=n%(a+b);
	cout<<q*a+min(r,a);

	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const double PI=3.14159265358979323846;
int main(){
	double a,b,x;
  	cin >> a >> b >> x;
    cout << fixed << setprecision(15) << atan(x>=a*a*b/2 ? (a*a*b-x)*2/a/a/a : b/(x*2/a/b))/PI*180;
	return 0;
}

Measured memory_bytes: 384
using System;
class ITP1
{
    static void Main(string[] args)
    {
        Q2_A();
        //var exStdIn = new System.IO.StreamReader("stdin.txt");
        //System.Console.SetIn(exStdIn);

        //int[] a = Array.ConvertAll(Console.ReadLine().Split(' '), new Converter<String, int>(s => int.Parse(s)));
    }

    static void Q1()
    {
        int input = int.Parse(Console.ReadLine());

        int h = input / 3600;
        int m = input % 3600 / 60;
        int s = input % 3600 % 60;

        Console.WriteLine(String.Format("{0}:{1}:{2}", h, m, s));
    }

    static void Q2_A()
    {
        int[] a = Array.ConvertAll(Console.ReadLine().Split(' '), new Converter<String, int>(s => int.Parse(s)));

        String sign = a[0] - a[1] > 0 ? ">" : a[0] - a[1] == 0 ? "==" : "<";

        Console.WriteLine(String.Format("a {0} b",sign));
    }
}

Measured memory_bytes: 8932
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(_i,_a,_n) for(int _i=_a;_i<=_n;++_i)
#define PER(_i,_a,_n) for(int _i=_n;_i>=_a;--_i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(_a) ({REP(_i,1,n) cout<<_a[_i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



const int N = 4050, M = 1e6+10;
int n,a[M],b[M],dp[N][N],fac[M],ifac[M];
void add(int &a, int b) {a=(a+b)%P;}
int C(int n, int m) {
	return (ll)fac[n]*ifac[m]%P*ifac[n-m]%P;
}
int main() {
	fac[0]=1;
	REP(i,1,M-1) fac[i]=(ll)fac[i-1]*i%P;
	ifac[M-1]=inv(fac[M-1]);
	PER(i,0,M-2) ifac[i]=(ll)ifac[i+1]*(i+1)%P;
	scanf("%d", &n);
	REP(i,1,n) { 
		scanf("%d%d",a+i,b+i);
		++dp[2010-a[i]][2010-b[i]];
	}
	REP(i,-2010,2010) REP(j,-2010,2010) { 
		int &r = dp[2010+i][2010+j];
		if (!r) continue;
		add(dp[2010+i+1][2010+j],r);
		add(dp[2010+i][2010+j+1],r);
	}
	int ans = 0;
	REP(i,1,n) { 
		add(ans,dp[2010+a[i]][2010+b[i]]);
		add(ans,-C(2*a[i]+2*b[i],2*a[i]));
	}
	if (ans<0) ans += P;
	ans = (P+1ll)/2*ans%P;
	printf("%d\n",ans);
}










Measured memory_bytes: 76032
#include <iostream>
#include <vector>
using namespace std;

int main(){
    int N,h;
    cin>>N;
    vector<int> H;
    for(int i=0;i<N;i++){
        cin>>h;
        H.push_back(h);
    }
    int Max=0,ans=0;
    for(int i=0;i<N;i++){
        if(H[i]>=H[Max]){
            ans++;
            Max=i;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
package main

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

func main() {
	N := ReadInt()

	dp := make([]int, 1e4+1)
	for x := 1; x < 100; x++ {
		for y := x; y < 100; y++ {
			for z := y; z < 100; z++ {
				g := x*x + y*y + z*z + x*y + y*z + z*x
				if g > 1e4 {
					break
				}
				if x == y && y == z {
					dp[g] += 1
					continue
				}
				if x == y || y == z {
					dp[g] += 3
					continue
				}
				dp[g] += 6
			}
		}
	}

	for i := 1; i <= N; i++ {
		fmt.Println(dp[i])
	}
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


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


int main(){
	int n;
	cin >> n;
	vector<int> graph(n);
	rep(i,n){
	    cin >> graph[i];
	    graph[i]--;
	}
	int now = 0, c = 0;
	for(;;){
        if(now == 1){
            cout << c << endl;
            break;
        }
        if(c >= n){
            cout << -1 << endl;
            break;
        }
        c++;
        now = graph[now];
	}

}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) begin(x),end(x)

using namespace std;
typedef int Weight;
Weight INF = 1000000000;

struct UnionFind {
  vector<int> parent;
  UnionFind (int n) : parent(n, -1) {}
  int root(int x) { return parent[x] < 0 ? x : parent[x] = root(parent[x]); }
  bool merge(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) return false;
    if (parent[y] < parent[x]) swap(x, y);
    if (parent[x] == parent[y]) --parent[x];
    parent[y] = x;
    return true;
  }
};

int main() {
  int n,w,h;
  cin>>n>>w>>h;
  vector<int> ix(w+1,-1);
  vector<int> iy(h+1,-1);
  bool edge = false;
  UnionFind uf(n);
  REP(i,n) {
    int x,y;
    cin>>x>>y;
    if(x==1||x==w||y==1||y==h) edge = true;
    if (ix[x] == -1) {
      ix[x] = i;
    } else {
      uf.merge(i, ix[x]);
    }
    if (iy[y] == -1) {
      iy[y] = i;
    } else {
      uf.merge(i, iy[y]);
    }
  }
  set<int> rt;
  REP(i,n) rt.insert(uf.root(i));
  if (rt.size() == 1) {
    cout << (n-1) << endl;
  } else {
    int cnt = n-1+rt.size();
    cout << (cnt-(edge?1:0)) << endl;
  }
  return 0;
}

Measured memory_bytes: 4968
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 605
vector<P> G[MAX_N];
double dp[MAX_N];
int cnt[MAX_N];
int cnt2[MAX_N];
int cnt3[MAX_N];
int xx[200005][2];
vector<pair<double, int>> v[MAX_N];

int main() {
    int n, m;
    cin >> n >> m;
    rep(i,m){
        int s,t; cin >> s >> t;
        s--; t--;
        cnt[s]++;
        cnt3[t]++;
        xx[i][0] = s;
        xx[i][1] = t;
        G[t].push_back(P(s, i));
    }
    double ans = 1001001001001;

    drep(i,n){
        rep(j, G[i].size()){
            dp[G[i][j].first] += (double)1 / cnt[G[i][j].first] * (dp[i] + 1);
            pair<double, int> p;
            p.first = dp[i] + 1;
            p.second = i;
            v[G[i][j].first].push_back(p);
        }
    }
    rep(i,n){
        if(v[i].size() == 0)continue;
        sort(v[i].begin(), v[i].end(), greater<pair<double, int>>());
    }
    
    ans = dp[0];

    rep(loop,m){
        int s = xx[loop][0];
        int t = xx[loop][1];
        // cout << s << ' ' << t << endl;
        if(v[s][0].second != t)continue;

        rep(j,n){dp[j] = 0; cnt2[j] = 0;}
        
        cnt[s]--;
        drep(i,n){
            if(cnt2[i] > 0){
                dp[i] /= (double)cnt2[i];
            }
            rep(j, G[i].size()){
                if(G[i][j].first == s && i == t)continue;
                if(i == n-1 || dp[i] > 0){
                    dp[G[i][j].first] += (double)(dp[i] + 1);
                    cnt2[G[i][j].first]++;
                }
            }
        }
        cnt[s]++;
        /*
        cout << s + 1 << ' ' << t + 1 << endl;
        rep(i,n)cout << dp[i] << endl;
        cout << endl;
        */
        int flag = 0;
        rep(i,n-1){
            if(cnt3[i] > 0 && cnt2[i] == 0){
                flag = 1;
                break;
            }
        }
        if(dp[0] > 0 && flag == 0)ans = min(ans, dp[0]);
    }

    cout << fixed << setprecision(10) << ans << endl;
    return 0;
}
 
 


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

int main()
{   
    int n;
    cin>>n;
    int a[n];
    int sum=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i]-1;
    }
    cout<<sum<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 300005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 +c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
struct cmp {
    bool operator () (const int &a,const int &b) const {
	return a > b;
    }
};
int N,a[MAXN];
int64 f[MAXN],b[MAXN];
multiset<int> s2;
multiset<int,cmp> s1;
void Solve() {
    read(N);
    for(int i = 1 ; i <= 3 * N ; ++i) read(a[i]);
    int64 sum = 0;
    for(int i = 1 ; i <= 3 * N ; ++i) {
	s1.insert(a[i]);sum += a[i];
	if(s1.size() > N) {
	    auto t = *(--s1.end());
	    s1.erase(--s1.end());
	    sum -= t;
	}
	f[i] = sum;
    }
    sum = 0;
    for(int i = 3 * N ; i >= 1 ; --i) {
	s2.insert(a[i]);sum += a[i];
	if(s2.size() > N) {
	    auto t = *(--s2.end());
	    s2.erase(--s2.end());
	    sum -= t;
	}
	b[i] = sum;
    }
    int64 ans = f[N] - b[N + 1];
    for(int i = N + 1 ; i <= 2 * N ; ++i) {
	ans = max(ans,f[i] - b[i + 1]);
    }
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}


Measured memory_bytes: 15488
def partition(A,p,r):
    x=A[r][1]
    i=p-1
    for j in range(p,r):
        if A[j][1]<=x:
            i+=1
            A[i],A[j]=A[j],A[i]
    A[i+1],A[r]=A[r],A[i+1]
    return i+1

def quickSort(A,p,r):
    if p<r:
        q=partition(A,p,r)
        quickSort(A,p,q-1)
        quickSort(A,q+1,r)

class checkStable:
    def __init__(self):
        self.d={}
    def storeCards(self,A):
        for i in range(len(A)):
            if A[i][1] in self.d:
                self.d[A[i][1]].append(A[i][0])
            else:
                self.d[A[i][1]]=[A[i][0]]
    def isStable(self,A):
        for i in range(len(A)):
            if self.d[A[i][1]].pop(0)!=A[i][0]:
                return "Not stable"
        return "Stable"    

n=int(input())
A=[]
for _ in range(n):
    mark,num=input().split()
    num=int(num)
    A.append([mark,num])
quick=checkStable()
quick.storeCards(A)

quickSort(A,0,n-1)
stable=quick.isStable(A)
print(stable)
for i in range(n):
    print(*A[i])


Measured memory_bytes: 21644
#include <cstdio>
#include <algorithm>

using namespace std;

int m = 1000000007;
int a[200000][2];
int dp[4001][4001];
long long inv[8001];
long long fact[8001];
long long invfact[8001];

void calc_inv(int n, int mod) {
    inv[1] = 1;
    for (int i = 2; i <= n; i++) inv[i] = inv[mod % i] * (mod - mod / i) % mod;
    
    fact[0] = invfact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % mod;
    for (int i = 1; i <= n; i++) invfact[i] = invfact[i - 1] * inv[i] % mod;
}

long long comb(int x, int y) {
    return fact[x] * invfact[y] % m * invfact[x - y] % m;
}

long long mod_inverse(long long a, long long m) {
    long long b = m, x = 1, y = 0;
    
    while (b) {
        long long t = a / b;
        
        a -= t * b;
        x -= t * y;
        
        swap(a, b);
        swap(x, y);
    }
    
    return (m + x % m) % m;
}

int main() {
    int n, i, j;
    long long ans = 0;
    
    calc_inv(8000, m);
    
    scanf("%d", &n);
    
    for (i = 0; i < n; i++) {
        scanf("%d %d", &a[i][0], &a[i][1]);
        
        dp[2000 - a[i][0]][2000 - a[i][1]]++;
    }
    
    for (i = 0; i <= 4000; i++) {
        for (j = 0; j <= 4000; j++) {
            if (dp[i][j] == 0) continue;
            
            if (i + 1 <= 4000) {
                dp[i + 1][j] += dp[i][j];
                if (dp[i + 1][j] >= m) dp[i + 1][j] -= m;
            }
            
            if (j + 1 <= 4000) {
                dp[i][j + 1] += dp[i][j];
                if (dp[i][j + 1] >= m) dp[i][j + 1] -= m;
            }
        }
    }
    
    for (i = 0; i < n; i++) {
        ans += dp[2000 + a[i][0]][2000 + a[i][1]];
        ans += m - comb(a[i][0] * 2 + a[i][1] * 2, a[i][0] * 2);
    }
    
    printf("%lld\n", ans % m * mod_inverse(2, m) % m);
    
    return 0;
}


Measured memory_bytes: 64384
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        long l = s.nextLong();
        long r = s.nextLong();
        long d = s.nextLong();
        int res=0;
        for(long i=l;i<=r;i++){
            if(i%d==0)
                res++;
        }
        System.out.println(res);
    }
    static int gcd(int a, int b)
    {
        if(b==0) {
            return a;
        }
        return gcd(b,a%b);
    }
    private static boolean isPrime(int n) {
        if (n == 2)
            return true;
        else if ((n % 2 == 0 && n > 2) || n < 2)
            return false;
        else {
            for (int i = 3; i <= (int) Math.sqrt(n); i += 2) {
                if (n % i == 0)
                    return false;
            }
            return true;
        }


    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

}

Measured memory_bytes: 26996
#include <stdio.h>
#include <string.h>

int main(void){
    long long k,queue[100000],x,head=1,tail=10;
    scanf("%lld",&k);
    for (int i=1;i<=9;i++){
        queue[i] = i;
    }
    while (tail <= k){
        x = queue[head++];
        if (x%10 != 0){
            queue[tail++] = 10*x+x%10-1;
        }
        queue[tail++]=10*x+x%10;
		if (x%10!=9){
			queue[tail++]=10*x+x%10+1;
		}
    }
    printf("%lld\n",queue[k]);
    return 0;
}

Measured memory_bytes: 896
#include <iostream>
#include <iomanip>
using namespace std;
int main(int argc, char* argv[])
{
    int a, b;
    cin >> a >> b;
    cout << a/b << " " << a%b <<  " " << setprecision(5) << setiosflags(ios::showpoint) << setiosflags(ios::fixed) << (double)a/b << endl;
    return 0;
}



Measured memory_bytes: 3288
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define REP(i, l, r) for (int i=(l); i<(r); ++i)
#define RREP(i, r, l) for (int i=(r); i>(l); --i)
#define CASET int _T; cin >> _T; REP(caset, 0, _T)
#define print(x) cout << to_string(x) << '\n'
#define vi vector<int>
#define vb vector<bool>
#define vs vector<string>
#define vvi vector<vi>
#define vvb vector<vb>
#define pii pair<int,int>
#define t3i tuple<int,int,int>
#define mii map<int,int>
#define vpii vector<pii>
#define vt3i vector<t3i>
#define sq(x) (x)*(x)
#define inv(x) powa(x, MOD-2)
 
long long INF = 1LL<<60;
long long MOD = 1e9+7;
 
string to_string(char &c) {string x(1, c); return x;}
string to_string(const char s[]) {return (string)s;}
string to_string(string &s) {return s;}
string to_string(vb &v) {string res; for (const bool &x : v) res += to_string(x) + ' '; return res;}
template <class C> string to_string(C &v) {string res; for (auto &x : v) res += to_string(x) + ' '; return res;}
template <typename A, typename B> istream &operator>>(istream &is, pair<A, B> &pr) {is >> pr.first >> pr.second; return is;}
template <typename A> istream &operator>>(istream &is, vector<A> &v) {for (auto &x : v) is >> x; return is;}
ostream &operator<<(ostream &os, char &c) {os << (char)c; return os;}
ostream &operator<<(ostream &os, const char s[]) {os << (string)s; return os;}
ostream &operator<<(ostream &os, string &s) {for (char &c : s) os << (char)c; return os;}
template <typename A, typename B> ostream &operator<<(ostream &os, pair<A, B> pr) {os << '(' << pr.first << ", " << pr.second << ')'; return os;}
ostream &operator<<(ostream &os, vb &v) {
    bool first = true;
    os << '[';
    for (const bool &x : v) {
        if (!first) os << ", ";
        first = false;
        os << x;
    }
    os << ']';
    return os;
}
template <class C> ostream &operator<<(ostream &os, C &v) {
    bool first = true;
    os << '[';
    for (auto &x : v) {
        if (!first) os << ", ";
        first = false;
        os << x;
    }
    os << ']';
    return os;
}
string bin_string(int x) {
    const int d = 32;
    string res(d, ' ');
    REP(i, 0, d) res[d-1-i] = '0'+(x>>i & 1LL);
    return res;
}
int powa(int base, int exp) {
    int res = 1;
    while (exp) {
        if (exp&1) res = res*base % MOD;
        base = base*base % MOD;
        exp >>= 1;
    }
    return res;
}

main() {
    ios::sync_with_stdio(0), cin.tie(0);
    
    int h, n;
    cin >> h >> n;

    vi a(n), b(n);
    REP(i, 0, n) cin >> a[i] >> b[i];
    
    vi dp(h+1, INF);
    dp[0] = 0;
    REP(d, 0, h+1) {
        REP(s, 0, n) {
            int eff = min(d+a[s], h);
            dp[eff] = min(dp[eff], dp[d] + b[s]);
        }
    }
    print(dp[h]);
}

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

typedef pair<int,int> P;

int main(){
    int n,m;
    cin >> n >> m;
    vector<vector<int>> to(n+1);
    for (int i = 0; i < m; i++){
        int a,b;
        cin >> a >> b;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    vector<int> res(n+1,100000000); res[0] = 0;
    queue<int> q; q.push(1);
    while(q.size() >= 1){
        int cur = q.front(); q.pop();
        for (int i : to[cur]){
            if (res[i] == 100000000){
                res[i] = cur;
                q.push(i);
            }
        }
    }
    
    if (lower_bound(res.begin(),res.end(),99999999) != res.end()){
        cout << "No" << "\n";
        return 0;
    }else{
        cout << "Yes" << "\n";
        for (int i = 2; i <= n; i++){
            cout << res[i] << "\n";
        }
    }
}

Measured memory_bytes: 10120
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
    int N,count=1;
    cin>>N;
    vector<int> d(N);
    for(int i=0;i<N;i++){
        cin>>d[i];
    }
    sort(d.begin(),d.end(),greater<int>());
    for(int i=0;i<N-1;i++){
        if(d[i]>d[i+1]){
            count++;
        }
    }
    cout<<count;
    return 0;
}

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

using LL = long long;
LL a, b;

signed main() {
  // freopen("in", "r", stdin);
  while(cin >> a >> b) {
    if(a + b == 15) printf("+\n");
    else if(a * b == 15) printf("*\n");
    else printf("x\n");
  }
  return 0;
}


Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules! get {
    ([$t:ty] ; $n:expr) => {
        (0..$n)
        .map(|_| get!([$t])).collect::<Vec<_>>()
    };
    ($($t:ty),+ ; $n:expr) => {
        (0..$n).map(|_| get!($($t),+)).collect::<Vec<_>>()
    };
    ([$t:ty]) => {
        rl().split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect::<Vec<$t>>()
    };
    ($t:ty) => {
        rl().parse::<$t>().unwrap()
    };
    ($($t:ty),*) => {
        {
            let line =rl();
            let mut iter = line.split_whitespace();
            ($(iter.next().unwrap().parse::<$t>().unwrap()),*)
        }
    };
}
fn rl() -> String {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    line.trim().to_string()
}

fn main() {
    let v: Vec<char> = get!(String).chars().collect();
    let mut ans1 = 0;
    for i in 0..v.len() {
        if i % 2 == 0 {
            if v[i] == '1' {
                ans1 += 1;
            }
        } else {
            if v[i] == '0' {
                ans1 += 1;
            }
        }
    }
    let mut ans2 = 0;
    for i in 0..v.len() {
        if i % 2 == 0 {
            if v[i] == '0' {
                ans2 += 1;
            }
        } else {
            if v[i] == '1' {
                ans2 += 1;
            }
        }
    }
    println!("{}", std::cmp::min(ans1, ans2));
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define N 100000
typedef long long ll;
int main(){
	int i,l,sum1,sum2;
	ll ans=0;
	sum1=sum2=0;
	i=0;
	char s[N];
	cin>>s;
	char a='0';
	while(s[i]){
		if(s[i]==a){
			sum1++;
		}
		if(i%2==0){
			a='1';
		}else{
			a='0';
		}
		i++;
	}
	i=0;
	a='1';
	while(s[i]){
		if(s[i]==a){
			sum2++;
		}
		if(i%2==0){
			a='0';
		}else{
			a='1';
		}
		i++;
	}
	ans=min(sum1,sum2);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 384
public class Main
{
	public static void main(String[] args) throws java.io.IOException
	{
		java.io.BufferedReader br = new java.io.BufferedReader( new java.io.InputStreamReader( System.in ) );
		
		String[] st = br.readLine().split(" ");
		int[] nums = new int[st.length];
		for( int i = 0 ; i < nums.length ; i++ ) nums[i] = Integer.parseInt( st[i] );
		
		java.util.Arrays.sort(nums);
		
		String result = "";
		for( int i = 0 ; i < nums.length ; i++ )
		{
			 if( i < (nums.length -1) ){
				 result += ( nums[i] + " " );
			}else{
				result += nums[i];
			}
		}
		System.out.println( result );
	}
}

Measured memory_bytes: 24128
import sys
from collections import Counter

N = int(sys.stdin.readline())
D = map(int, sys.stdin.readline().split())
M = int(sys.stdin.readline())
T = map(int, sys.stdin.readline().split())

diffs = Counter(D)
problems = Counter(T)

for diff, count in problems.items():
    if diff not in diffs:
        break
    if diffs[diff] < count:
        break
else:
    print("YES")
    sys.exit()

print("NO")

Measured memory_bytes: 68116
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cctype>
#include <queue>
#include <map>
#include <set> 
#include <bitset>
#include <cmath>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<n;i++)

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

    int ans = 0;
    for (int i = 0; i < 4; i++) {
        if(s[i] == '+') {
            ans += 1;
        } else {
            ans -= 1;
        } 
    }

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



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

using namespace std;

#define scan(x) scanf("%d", &x)
#define scan2(x, y) scanf("%d %d", &x, &y)
#define PRI(x) printf("%d\n", x)
#define FOR(A, B, C) for (int A=B;A<C;A++)
#define RFOR(A, B, C) for (int A=B;A>=C;A--)
#define MEM(A, B) memset(A,B, sizeof A)
#define mod 1000000007
typedef long long int LL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;


int main() {
	int n, a, b;
	cin >> n >> a >> b;
	int ans = 0;
	FOR (i, 1, n + 1) {
		string x = to_string (i);
		int sum = 0;
		FOR (j, 0, x.length()) {
			sum += (x[j] - '0');
		}
		if (sum >= a and sum <= b) 
			ans += i;
	}	
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i)
#define all(a) (a).begin(), (a).end()

int N;
vector<int> P;

int main() {
  cin >> N;
  P.resize(N);
  rep(i, N) cin >> P[i];

  ll ans = 0;
  vector<int> idx(N + 1);
  rep(i, N) idx[P[i]] = i;

  multiset<int> s;
  rep(i, 2) s.insert(-1);
  rep(i, 2) s.insert(N);

  for (int i = N; i >= 1; --i) {
    int j = idx[i];
    auto it = s.lower_bound(j);
    int r1 = *it, r2 = *next(it), l1 = *prev(it), l2 = *prev(prev(it));
    ans += ll(i) * ((r2 - r1) * (j - l1) + (l1 - l2) * (r1 - j));
    s.insert(j);
  }

  cout << ans << endl;

  return 0;
}


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

using namespace std;

inline long long read(){
   long long w=1,s=0;
   char ch=getchar();
   while(ch<'0'||ch>'9') {if (ch=='-') w=-1;ch=getchar();} 
   while(ch>='0'&&ch<='9')  s=s*10+ch-'0',ch=getchar();
   return s*w;
}


int main(){
    int x=read(),y=read(),x1=read(),y1=read();
    int dx=x-x1,dy=y-y1;
    cout<<x1+dy<<" "<<y1-dx<<" "<<x+dy<<" "<<y-dx;
    return 0;
}

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

const int MAX_M = 10010;

int n, m, p;
int d[MAX_M];

int right(int s, int t){
	return (t >= s) ? (t - s) : (t + n - s);
}

int left(int s, int t){
	return right(t, s);
}

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

	cin >> n >> m >> p;

	for(int i = 0; i < m; ++i){
		cin >> d[i];
	}

	if(m == 1){
		cout << min(right(d[0], p), left(d[0], p)) * 100 << endl;
		return 0;
	}

	sort(d, d + m);

	int ans = 2 * n;
	for(int i = 0; i < m; ++i){
		int b = d[i];
		int e = d[(i + 1) % m];
		int a = min({right(b, p), right(e, p), left(b, p), left(e, p)});
		ans = min(ans, a + n - right(b, e));
	}

	cout << ans * 100 << endl;

	return 0;
}

Measured memory_bytes: 1248
#include<bits/stdc++.h>
using namespace std;
struct T{
	int id,v,num;
}p[510],s[510];
int n,a[510],ar[250010],nw;
bool cmp(T x,T y){
	return x.id<y.id;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		if(ar[a[i]])return puts("No");
		ar[a[i]]=i,p[i]=(T){a[i],i,i-1},s[i]=(T){a[i],i,n-i};
	}
	sort(p+1,p+n+1,cmp),sort(s+1,s+n+1,cmp),nw=1;
	while(nw<=n&&!p[nw].num)++nw;
	for(int i=1;i<=n*n&&nw<=n;++i)if(!ar[i]){
		if(i>=p[nw].id)return puts("No"),0;
		ar[i]=p[nw].v,--p[nw].num;
		while(nw<=n&&!p[nw].num)++nw;
	}
	if(nw<=n)return puts("No"),0;
	nw=n;
	while(nw>=1&&!s[nw].num)--nw;
	for(int i=n*n;i>=1&&nw>=1;--i)if(!ar[i]){
		if(i<=s[nw].id)return puts("No"),0;
		ar[i]=s[nw].v,--s[nw].num;
		while(nw>=1&&!s[nw].num)--nw;
	}
	if(nw>=1)return puts("No"),0;
	puts("Yes");
	for(int i=1;i<=n*n;++i)printf("%d%c",ar[i]," \n"[i==n*n]);
	return 0;
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i,n) for(long long i = 0; i < (n); ++i)
#define ll long long
#define P pair<ll,ll>
#define all(v) (v).begin(),(v).end()

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1.0);

int main(void)
{
    string s; cin>>s;
    bool ok=true;
    regex check("A?KIHA?BA?RA?");
    if(regex_match(s,check)) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

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

#define irep(i,n) for(int i = 0; i < (int)(n); i++)
#define irep2(i,a,n) for(int i = (int)(a); i <= (int)(n); i++)
#define irrep(i,n) for(int i = (int)(n-1); i > -1; i--)
#define irrep2(i,n,a) for(int i = (int)(n); i >= (int)(a); i--)

#define fi first
#define se second

using namespace std;

using ll = long long;
using v_int = vector<int>;
using v2_int = vector<v_int>;
using v_ll = vector<ll>;
using v2_ll = vector<v_ll>;
using v_string = vector<string>;
using v_bool = vector<bool>;
using v2_bool = vector<v_bool>;
using pii = pair<int, int>;
using mii = map<int, int>;

const double PI = 3.1415926535897932;
const int INF = (int)2e9;
const ll LINF = (ll)2e18;
const ll MOD = 1000000007;
const int dc[8] = {1, -1, 0,  0, 1, -1,  1, -1};
const int dr[8] = {0,  0, 1, -1, 1,  1, -1, -1};

template<typename T, typename U> inline
ostream& operator<<(ostream &o, pair<T,U> &p) {
    return o << "{" << p.first << "," << p.second << "}";
}
template<typename T> inline
istream& operator>>(istream &is, vector<T> &vec) {
    for(auto &v : vec) { is >> v; }
    return is;
}
template<typename T> inline
ostream& operator<<(ostream &os, vector<T> &vec) {
    for(auto &v : vec) { os << v << ",";}
    return os;
}
template<typename T> inline
ostream& operator<<(ostream &os, vector<vector<T> > &mat) {
    for(auto &row : mat) { os << row << endl; }
    return os;
}
template<typename T> inline
void chmin(T &a, T b) { a = min(a, b); }
template<typename T> inline
void chmax(T &a, T b) { a = max(a, b); }

int main(void)
{
    int n, m;
    cin >> n >> m;
    
    v2_int light(m, v_int(n));

    irep(i, m) {
        int k;
        cin >> k;
        irep(j, k) {
            int s;
            cin >> s;
            light[i][s-1] = 1;
        }
    }
    
    v_int p(m);
    irep(i, m) {
        cin >> p[i];
    }
    
    int ans = 0;
    irep(i, (1<<n)) {
        int ok = 0;
        irep(k, m) {
            int cnt = 0;
            irep(s, n) {
                if(i & (1<<s)) {
                    if(light[k][s]) { cnt++; }
                }
            }
            if(p[k] == (cnt%2)) { ok++; }
        }
        if(ok == m) { ans++; }
    }
    cout << ans << endl;
    return 0;
} /*atcoder*/


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

int main(int argc,char** argv){
	string s,t;
  	cin>>s;
  	cin>>t;
  	if(t.substr(0,t.length()-1)==s)
      cout<<"Yes"<<endl;
  	else
      cout<<"No"<<endl;
}

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

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define MP make_pair
#define PB push_back
#define X first
#define Y second

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())
#define FILL(a, value) memset(a, value, sizeof(a))
#define debug(a) cerr << #a << " = " << a << endl;

template<typename T> void setmax(T& x, T y) {x = max(x, y);}
template<typename T> void setmin(T& x, T y) {x = min(x, y);}

const double PI = acos(-1.0);
const LL INF = 1e9 + 47;
const LL LINF = INF * INF;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1 << 17;
int n, m;
VI g[N];
char u[N];

void dfs(int v)
{
	if (u[v]) return;
	u[v] = 1;
	for(auto i: g[v]) dfs(i);
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	cin >> n >> m;
	while(m--)
	{
		int x, y, z;
		cin >> x >> y >> z;
		g[x].PB(y);
		g[y].PB(x);
	}
	
	int ans = 0;
	FOR(i, 1, n + 1) if (!u[i]) ans++, dfs(i);
	cout << ans;
	
	cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl;
	return 0;
}



Measured memory_bytes: 9728