akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

const int N = (int) 1e5 + 5;

int n;
vector <int> p[450], group[450];

int main() {
	ios_base :: sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	int k = sqrt(2 * n);
	if ((k - 1) * k < 2 * n) k++;
	if ((k - 1) * k > 2 * n) k--;
	if ((k - 1) * k != 2 * n) return cout << "No", 0;
	k--;
	cout << "Yes\n";
	int num = 0;
	for (int i = 1; i <= k; i++) {
		p[i].resize(i + 1);
		for (int j = 1; j <= i; j++) p[i][j] = ++num;
	}
	for (int c = 1; c <= k; c++) {
		for (int r = c; r <= k; r++) group[c].push_back(p[r][c]);
		for (int c2 = c - 1; c2 >= 1; c2--) group[c].push_back(p[c][c2]);	
	}
	num = 0;
	for (int i = 1; i <= k; i++) { 
		num += i;
		group[k + 1].push_back(num); 
	}
	cout << k + 1 << "\n";
	for (int i = 1; i <= k + 1; i++) {
		cout << group[i].size() << " ";
		for (int j = 0; j < group[i].size(); j++) cout << group[i][j] << " ";
		cout << "\n";
	}
	return 0;
}

Measured memory_bytes: 2688
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace _20190413
{
    class Program
    {
        public static void Main(string[] args)
        {
            using (var sc = new SetConsole())
            {
                var input = GetArrayIntInput();
                int sum = 0;
                if (input[0] < input[1])
                {
                    sum += input[1];
                    input[1]--;
                }
                else
                {
                    sum += input[0];
                    input[0]--;
                }
                if (input[0] < input[1])
                {
                    sum += input[1];
                    input[1]--;
                }
                else
                {
                    sum += input[0];
                    input[0]--;
                }
                CWrite(sum);
            }
        }

        static string[] GetArrayCharInput() => Console.ReadLine().Split();
        static int[] GetArrayIntInput() => Console.ReadLine().StringToIntArray();
        static int GetIntInput() => Console.ReadLine().ToInt();
        static void CWrite<T>(T str) => Console.WriteLine(str);
    }



    class SetConsole : IDisposable
    {
        readonly StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
        public SetConsole()
        {
            sw.AutoFlush = false;
            Console.SetOut(sw);
        }
        public void Dispose()
        {
            Console.Out.Flush();
            sw.AutoFlush = true;
            Console.SetOut(sw);
        }
    }

    static class ExtentionsLibrary
    {
        public static int[] StringToIntArray(this string str) =>
            str.Split().Select(int.Parse).ToArray();
        public static int ToInt(this string str) => int.Parse(str);
    }
}


Measured memory_bytes: 13396
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;
typedef long long int ll;
#define MAX_N 10000

int par[MAX_N];
struct edge{
	int start;
	int to;
};

void init(){
	rep(i,MAX_N){
		par[i] = i;
	}
}

int root(int i){
	if(par[i] == i) return i;
	par[i] = root(par[i]);
	return par[i];
}

bool isSame(int i,int j){
	i = root(par[i]);
	j = root(par[j]);
	return i == j;
}

void unite(int i, int j){
	i = root(i);
	j = root(j);
	if(i == j) return;
	par[i] = j;
}


int main()
{
	int N,M;
	cin>>N>>M;
	vector<edge> edgeList;
	rep(i,M){
		int x,y;
		cin>>x>>y;
		x--;
		y--;
		struct edge e;
		e.start = x;
		e.to = y;
		edgeList.push_back(e);
	}
	ll ans = 0;
	for(int i = 0; i < M; i++){
		init();
		for(int j = 0; j < M; j++){
			if( i != j){
				unite(edgeList[j].start, edgeList[j].to);
			}
		}
		/*rep(k,N) cout<<par[k]<<" ";
		cout<<endl;*/
		if( isSame(edgeList[i].start,edgeList[i].to) == false) ans++;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3228
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int x,n;
  scanf("%d %d", &x,&n);
  unordered_set<int> arr;
  for(int a=0;a<n;a++)
  {
      int k;
	  scanf("%d ", &k);
	  arr.insert(k);
  }
  int ans;
  for(int a=0;;a++)
  {
  	if(arr.find(x-a)==arr.end())
  	{
	  	ans=x-a;
	  	break;
  	}
  	else if(arr.find(x+a)==arr.end())
  	{
  		ans=x+a;
  		break;
  	}
  }
  printf("%d", ans);
}

Measured memory_bytes: 3784
N, M = map(int, input().split())
aset = set([int(input()) for _ in range(M)])
dp = [0] * (N + 1)
dp[0] = 1
if 1 not in aset:
    dp[1] = 1
for i in range(2, N + 1):
    if i in aset:
        dp[i] = 0
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % (10**9 + 7)
print(dp[-1])


Measured memory_bytes: 13192
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pp;

int main() {
    int N;
    cin >> N;
    
    int yes = true;
    int cx = 0, cy = 0, ct = 0;
    for(int i=0; i<N; ++i) {
        int t,x,y;
        cin >> t >> x >> y;
        int dist = abs(x - cx) + abs(y - cy);
        if(t - ct >= dist && (dist % 2) == ((t - ct) % 2)) continue;
        else yes = false;
    }

    if(yes) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define IT iterator
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
#define debug puts("wzpakking")
#define y1 ysghysgsygsh
using namespace std;
const int N=2005;
int n,mo,ans,a[N];
int f[N*3][N],inv[N*3];
int power(int x,int y){
	int s=1;
	for (;y;y/=2,x=1ll*x*x%mo)
		if (y&1) s=1ll*s*x%mo;
	return s;
}
int main(){
	scanf("%d%d",&n,&mo);
	For(i,1,3*n) inv[i]=power(i,mo-2);
	f[0][0]=1;//f[1][0]=f[2][0]=1;
	For(i,0,3*n) For(j,0,n) For(k,1,3)
		f[i+k][j+(k>=2)]=(f[i+k][j+(k>=2)]+1ll*f[i][j]*inv[i+k])%mo;
	int ans=0;
	For(i,0,n) ans=(ans+1ll*f[3*n][i])%mo;
	For(i,1,3*n) ans=1ll*ans*i%mo;
	printf("%d\n",ans);
}

Measured memory_bytes: 47360
// A.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

int main(int argc, char* argv[]) {
	string s;
	cin >> s;
	int cnt[256] = {};
	for (char c : s) {
		cnt[c] += 1;
	}
	bool ans = cnt['A'] > 0 && cnt['B'] > 0;
	cout << (ans ? "Yes" : "No") << endl;
	return 0;
}


Measured memory_bytes: 256
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int cnt = 0;
        for (int i = 0; i < n; i++){
            int m = Integer.parseInt(br.readLine());
            if (isPrime(m)){
                cnt++;
            }
        }
        System.out.println(cnt);
    }
    static boolean isPrime(int q){
        if (q == 2) return true;
        if (q < 2 || ((q & 1) == 0)) return false;
        
        int i = 3;
        while (i * i <= q){
            if (q % i == 0){
                return false;
            }
            i += 2;
            //if ((i & 1) == 0) i++;
        }
        return true;
        
    }
}

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

namespace abc120_a
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int A = int.Parse(input[0]);
            int B = int.Parse(input[1]);
            int C = int.Parse(input[2]);

            Console.WriteLine(Listen(A,B,C));
        }
        public static int Listen(int A,int B,int C)
        {
            if (B / A <= C)
            {
                return B / A;
            }
            else
            {
                return C;
            }
        }
    }
}


Measured memory_bytes: 13140
n = int(input())
h_para = [int(i) for i in input().split()]

able_h = []
for i in range(n):
    count = 0
   

    

    for j in range(i):
        if h_para[i] >= h_para[j] :
            count = count
        else :
            count += 1
    if count == 0 : able_h.append(i)

print(len(able_h))

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

int main(){
	int N;
	cin >> N;
	int d[N];
	for(int i=0;i<N;i++)cin >> d[i];
	
	set<int> date;
	for(int i=0;i<N;i++)date.insert(d[i]);
	
	cout << date.size() << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
	int a, b, c, i, count = 0;
	scanf("%d%d%d", &a, &b, &c);

	for (i = a; i <= b; i++) {
		if ((c % i) == 0) count++;
	}

	printf("%d\n", count);

	return 0;
}

Measured memory_bytes: 596
#include <iostream>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;

int main(){
    int a, b, k;
    cin >> a >> b >> k;

    if(b-(a-1) <= k*2){
        for(int i = a; i <= b; i++){
            cout << i << endl;
        }
        return 0;
    }

    REP(i, k){
        cout << a + i << endl;
    }
    for(int i = k-1; i >= 0; i--){
        cout << b - i << endl;
    }
    return 0;
}


Measured memory_bytes: 256
program main
    implicit none
    integer::n,d,xx,yy,i,cou
    real(8),allocatable::x(:),y(:)
    real(8)::z

    read*,n,d
    allocate(x(n),y(n))

    do i=1,n
    read*,xx,yy
    x(i)=xx
    y(i)=yy
    !print*,x(i),y(i)
    end do
    !print*,x,y


    cou=0
    do i=1,n
        z=sqrt(x(i)**2+y(i)**2)
        if(z<=d) then
            cou=cou+1
        end if
     end do

     print*,cou



end program main

Measured memory_bytes: 5996
while True:
    m, f, r = map(int, input().split())

    if m == -1 and f == -1 and r == -1:
        quit()
    elif m == -1 or f == -1:
        print('F')
    elif m + f >= 80:
        print('A')
    elif m + f >= 65:
        print('B')
    elif m + f >= 50 or r >= 50:
        print('C')
    elif m + f >= 30:
        print('D')
    elif m + f < 30:
        print('F')

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

typedef long long lli;
typedef vector<int> Vi;
typedef vector<lli> Vl;
typedef pair<int, int> Pii;
typedef pair<lli, lli> Pll;


//===


int main()
{
	int H, W, N;
	cin >> H >> W >> N;
	int sr, sc;
	cin >> sr >> sc;
	string S, T;
	cin >> S;
	cin >> T;

	int ml, mr, mu, md;
	ml = sc - 1;
	mr =W - sc;
	mu = sr - 1;
	md = H - sr;

	Vi left(N+1), right(N+1), up(N+1), down(N+1);
	
	for (int i = 0; i < N; ++i) {
		left[i + 1] = left[i];
		right[i + 1] = right[i];
		up[i + 1] = up[i];
		down[i + 1] = down[i];

		if (S[i] == 'L') {
			++left[i + 1];
		}
		else if (S[i] == 'R') {
			++right[i + 1];
		}
		else if (S[i] == 'U') {
			++up[i + 1];
		}
		else {
			++down[i + 1];
		}

		if (right[i + 1] > mr || left[i + 1] > ml || up[i + 1] > mu || down[i + 1] > md) {
			cout << "NO" << endl;
			return 0;
		}

		if (T[i] == 'L') {
			if (-right[i + 1] < ml) --right[i + 1];
		}
		else if (T[i] == 'R') {
			if (-left[i + 1] < mr) --left[i + 1];
		}
		else if (T[i] == 'U') {
			if (-down[i + 1] < mu) --down[i + 1];
		}
		else {
			if (-up[i + 1] < md) --up[i + 1];
		}
	}

	//cout << "L:";
	//for (const auto& d : left) cout << ' ' << d;
	//cout << endl;
	//cout << "R:";
	//for (const auto& d : right) cout << ' ' << d;
	//cout << endl;
	//cout << "U:";
	//for (const auto& d : up) cout << ' ' << d;
	//cout << endl;
	//cout << "D:";
	//for (const auto& d : down) cout << ' ' << d;
	//cout << endl;

	cout << "YES" << endl;
}

Measured memory_bytes: 3848
/************************Code by Hardik Aggarwal!!!!***********************************/

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

#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL); 

#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define pu push
#define pp pop_back
#define in insert
#define ld long double
#define endl '\n'
#define debug cout << "Hold right there sparky.....\n";
#define forn(low,high,i) for(i=low;i<high;i++)
#define forrev(high,low,i) for(i = high; i>= low;i--)
#define trace(x) cerr << #x << ": " << x << " " << endl;

typedef long long int ll;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
const ll mod =998244353;

bool comp(pll p1,pll p2)
{
    if(p1.ff==p2.ff)
        return p1.ss<p2.ss;

    return p1.ff<p2.ff;
}

int main()
{
   

    IOS
    ll n,k;
    cin>>n>>k;
    ll ans=0;
    for(ll i=0;i<n;i++)
    {
        ll x;
        cin>>x;
        if(x>=k)
            ans++;
    }
    cout<<ans<<endl;


    




    
    
}
    
 
    
    



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



int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    vector<ll> s(n+1);
    ll sum=0;s[0]=0;
    rep(i,n){
        ll a;cin>>a;
        s[i+1]=s[i]+a;
    }
    sort(s.begin(),s.end());
    ll ans=0;
    /*
    rep(i,n){
        if(s[i]==s[i+1])c++;
        else{ans+=c*(c-1)/2;c=1;}
    }
    cout<<ans+c*(c-1)/2<<endl;*/
    
    ll c=0;
    rep(i,n){
        if(s[i]==s[i+1]){c++;ans+=c;}
        else c=0;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1792
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,avx2,fma,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(0),cin.tie(0), cout.tie(0)
typedef long long ll;


ll mod = 1e9 + 7;
ll power(ll x, ll n, ll mod) {
  ll res = 1;
  x %= mod;
  while (n) {
    if (n & 1)
      res = (res * x) % mod;
    x = (x * x) % mod;
    n >>= 1;
  }
  return res;
}

//#######################################

int main(){
  boost;

  int n,d;
  cin>>n>>d;
  double x,y;
  int count=0;
  // cin>>x>>y;
  for(int i=0;i<n;i++){
    cin>>x>>y;
    if(sqrt(x*x+y*y)<=d)
    count++;
  }
  cout<<count;
}



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


def solve(N: int, a: "List[int]"):
    c = round(sum(a)/N)
    ans = 0
    for i in range(N):
        ans += (c-a[i])**2

    print(ans)
    return


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

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
I'm working for the day I will surpass you
https://www.a2oj.com/Ladder16.html
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class Main
   {
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         System.out.println(N/2+N%2);
      }
   }

Measured memory_bytes: 21332
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int a,b,c;
  cin>>a>>b>>c;
  if(a+b>=c)
  {
     cout<<"Yes"<<endl;
  }
  else 
  {
     cout<<"No"<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
l1 = gets.chomp.split(" ").map(&:to_i);
l2 = gets.chomp.split(" ").map(&:to_i);
l3 = gets.chomp.split(" ").map(&:to_i);

flatten = l1.concat(l2).concat(l3)

n =  gets.chomp.to_i
n.times do
  b =  gets.chomp.to_i
  flatten[flatten.index(b)] =true if flatten.include?(b)
end

l1=flatten[0..2]
l2=flatten[3..5]
l3=flatten[6..8]


if (l1[0] == l2[0] && l2[0] == l3[0]) ||
   (l1[1] == l2[1] && l2[1] == l3[1]) ||
   (l1[2] == l2[2] && l2[2] == l3[2]) ||
   (l1[0] == l1[1] && l1[1] == l1[2]) ||
   (l2[0] == l2[1] && l2[1] == l2[2]) ||
   (l3[0] == l3[1] && l3[1] == l3[2]) ||
   (l1[0] == l2[1] && l2[1] == l3[2]) ||
   (l1[2] == l2[1] && l2[1] == l3[0])
puts "Yes"
else
puts "No"
end

Measured memory_bytes: 1788
#include<iostream>
using std::cin;
using std::cout;

int main() {
	std::ios_base::sync_with_stdio(false);
  	cin.tie(NULL);
  	int a,b;
  	cin >> a >> b;
  	cout << (a-1)*(b-1) << "\n";
  	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
//const int maxn=;
typedef long long ll;
int main(){
	int a,b;
	cin>>a>>b;
	if (a!=1&&b!=1) cout<<"1"<<endl;
	if (a!=2&&b!=2) cout<<"2"<<endl;
	if (a!=3&&b!=3) cout<<"3"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int, int> pii;
typedef long long ll;
const int MOD = 1000000007;
const int BASE = 27;
const int oo = 1e9;
const double EPS = 1e-9;
const int MX = 2e5 + 1;

int n;
ll  x;
struct exam {
  ll b, u, v;
};
exam e[MX];


struct line {
  ll a, b, idx;
  line() {
    a = b = idx = 0;
  }
  line(ll _a, ll _b, int _idx) {
    a = _a, b = _b, idx = _idx;
  }
  ll eval(ll x) {
    return a * x + b;
  }
  bool operator<( line &rhs) {
    if(eval(x) == rhs.eval(x))
      return a < rhs.a;
    return eval(x) < rhs.eval(x);
  }
};


bool check(ll rem) {
  vector<line> all;
  ll sc = 0;
  for (int i = 1; i <= n; ++i) {
    sc -= e[i].u * e[i].b;
    ll a1 = e[i].v;
    ll b1 = -e[i].b * (e[i].v - e[i].u);
    all.push_back(line(a1, b1, i));
  }
  if(sc == 0)return true;
  if(rem == 0)return false;
  sort(all.begin(),all.end());
  ll g1 = rem/x,g2;
  if(rem%x == 0)
    g2 = x,g1--;
  else g2 = rem%x;
  ll sm = 0;
  for(int j = all.size()-1;j>= all.size()-g1;--j)
    sm += all[j].eval(x);

  for(int j = all.size()-g1; j < all.size();++j){
    ll nwSm = sm-all[j].eval(x)+all[all.size()-g1-1].eval(x);
    ll mx = max(all[j].eval(g2),line(e[all[j].idx].u,0,all[j].idx).eval(g2));
    if(mx+nwSm+sc >= 0)
      return true;
    
  }
  for(int j = 0 ; j+g1 < all.size();++j){
    ll mx = max(all[j].eval(g2),
      line(e[all[j].idx].u,0,all[j].idx).eval(g2));
    if(mx+sm+sc >= 0)return true;
  }
  return false;
}

int main() {
  cin >> n >> x;
  for (int b, l, u, i = 1; i <= n; ++i) {
    scanf("%lld%lld%lld", &e[i].b, &e[i].u, &e[i].v);
  }

  ll lo = 0 , hi = 1ll * n * x, best = -1;
  while (lo <= hi) {
    ll md = (lo + hi) / 2;
    if (check(md)) {
      best = md;
      hi = md - 1;
    } else {
      lo = md + 1;
    }
  }
  cout << best << endl;
  return 0;
}


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

int main() {
    //
    long long num, que;

    cin >> num >> que;
    map<long long, long long> m;
    vector<pair<long long, long long>> p(que);
    for (long long i = 0; i < num; i++) {
        long long tmp;
        cin >> tmp;
        m[tmp]++;
    }

    for (long long i = 0; i < que; i++) {
        long long a, b;
        cin >> a >> b;
        p.at(i) = make_pair(b, a);
    }
    sort(p.rbegin(), p.rend());

    for (long long i = 0; i < que; i++) {
        long long cnt = 0;
        for (auto itr : m) {
            if (itr.second == 0) continue;
            if (p.at(i).second == 0 || itr.first >= p.at(i).first) break;

            //cout << "itr:" << itr.first << ":" << itr.second << endl;
            //cout << "p  :" << p.at(i).first << ":" << p.at(i).second;
            if (p.at(i).second >= itr.second) {
                m[p.at(i).first] += itr.second;
                m[itr.first] = 0;
                p.at(i).second -= itr.second;
                // m.erase(begin(m));
                cnt++;
            } else {
                m[p.at(i).first] += p.at(i).second;
                m[itr.first] -= p.at(i).second;
                p.at(i).second = 0;
            }
            //cout << "->" << p.at(i).first << ":" << p.at(i).second << endl;
        }
        if (cnt > 0) m.erase(begin(m), next(begin(m), cnt));
    }

    long long kekka = 0;
    for (auto itr : m) {
        // cout << (long long)itr.first << "*" << (long long)itr.second << endl;
        kekka += (itr.first * itr.second);
    }

    cout << kekka << endl;
    //
}


Measured memory_bytes: 11156
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[][] A = new int[2][N];
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < N; j++) {
				A[i][j] = sc.nextInt();
			}
		}
		int[] sum = new int[N];
		for (int i = 0; i < N; i++) {
			int k = 0;
			for (int j = 0; j < N; j++) {
				sum[i] += A[k][j];
				if (j == i) {
					k++;
					sum[i] += A[k][j];
				}
			}
		}
		int ans = sum[0];
		for (int i = 0; i < N; i++) {
			if (ans < sum[i])
				ans = sum[i];
		}
		System.out.println(ans);
	}

}

Measured memory_bytes: 21588
# input
N = int(input())

# 約数
def getDivs(n):
    divs = [n]
    for i in range(2, n):
        if i * i > n:
            break
        if n % i == 0:
            divs.append(i)
            if i != n//i:
                divs.append(n//i)
    return divs

# process
if N == 2:
    print(1)
else:
    pf1 = getDivs(N)
    pf2 = getDivs(N-1)
    cnt = len(pf2)

    for x in pf1:
        n = N
        while n%x == 0:
            n //= x
        n %= x 
        
        if n == 1:
            cnt += 1

    # print(pf1)
    # print(pf2)
    print(cnt)


Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s; cin >> s;
    int res = 1;
    for(int i=0; i<s.size(); ++i){
        if(s[0]=='S' && s[1]=='S' && s[2]=='S'){
            cout << 0 << endl; return 0;
        }
    }
    for(int i=0; i<s.size(); ++i){
        if(i==s.size()-1){break;}
        if(s[i]=='R' && s[i+1]=='R'){res++;}
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3564
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=(n-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define br cout << "\n";
using namespace std;
const long long INF = 1e10;
const long long MOD = 1e9+7;
using Graph = vector<vector<ll>>;
using pll = pair<ll, ll>;
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;}

// 0 false, 1 true 
// string to int : -48
// a to A : -32
// ceil(a)  1.2->2.0
// c++17	g++ -std=c++17 a.cpp


int main() {
    std::cout << std::fixed << std::setprecision(15);
    ll h, w, k; cin >> h >> w >> k;
    vector<vector<string>> vec(h, vector<string>(w));
    rep(i, h){
        string s; cin >> s;
        rep(j, w){
            vec[i][j] = s[j];
        }
    }

    ll ans = 0;
    for(ll row = 0; row < (1 << h); row++){
        for(ll col = 0; col < (1 << w); col++){
            ll count = 0;
            for(ll i = 0; i < h; i ++){
                for(ll j = 0; j < w; j++){
                    if(row >> i & 1){
                        continue;
                    }
                    if(col >> j & 1){
                        continue;
                    }
                    if(vec[i][j] == "#"){
                        count++;
                    }
                }
            }
            if(count == k){
                ans++;
            }
        }
    }

    cout << ans << endl;

}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
int main() {
	cin.tie(0);
    ios::sync_with_stdio(false);

    int H, W;
    cin >> H >> W;

    vector<vector<int> > a(H, vector<int>(W));
    vector<int> c(H);

    vector<vector<int> > ans;

    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            cin >> a[i][j];
            if(a[i][j] % 2) c[i]++;
        }
    }

    for(int i = 0; i < H; i++) {
        bool re = false;
        for(int j = 0; j < W - 1; j++) {
            if(a[i][j] % 2) re = !re;
            if(re) {
                vector<int> x(4);
                x[0] = i + 1;
                x[1] = j + 1;
                x[2] = i + 1;
                x[3] = j + 2;
                ans.push_back(x);
            }
        }
    }

    bool re = false;

    for(int i = 0; i < H - 1; i++) {
        if(c[i] % 2) re = !re;
        if(re) {
            vector<int> x(4);
            x[0] = i + 1;
            x[1] = W;
            x[2] = i + 2;
            x[3] = W;
            ans.push_back(x);
        }
    }

    cout << ans.size() << endl;
    for(int i = 0; i < ans.size(); i++) {
        cout << ans[i][0] << " " << ans[i][1] << " " << ans[i][2] << " " << ans[i][3] << endl;
    }
}

Measured memory_bytes: 10032
#include <iostream>
#include <ios> 
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

using namespace std;
typedef long long int lli;
//const int MAX=;

lli N;
lli ans=0;
//xを先頭とする七五三数, a,b,cは使用のフラグ
void dfs(lli x,int a,int b,int c){
	if(x>N) return;
	if(a&&b&&c) ans++;
	dfs(10*x+3,1,b,c);
	dfs(10*x+5,a,1,c);
	dfs(10*x+7,a,b,1);
}

int main(){
	cin>>N;
	dfs(0,0,0,0);
	cout<<ans;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        
        System.out.println(a+b >= c ? "Yes" : "No");
    } 
}


Measured memory_bytes: 35680
#include <iostream>
#include <fstream>
#include <algorithm>
#include <functional>
#include <chrono>
#include <random>
#include <vector>
#include <string>
#include <cmath>
#include <bitset>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cassert>

#define sq(x) ((x) * (x))
#define err(x) cerr << "["#x"]  " << (x) << "\n";
#define errp(x) cerr << "["#x"]  {" << ((x).first) << ", " << ((x).second) << "}\n";
#define errv(x) {cerr << "["#x"]  [";for(const auto& ___ : (x)) cerr << ___ << ", "; cerr << "]\n";}
#define errvn(x, n) {cerr << "["#x"]  [";for(auto ___ = 0; ___ < (n); ++___) cerr << (x)[___] << ", "; cerr << "]\n";}
#define errf() cerr << "\n\n";

#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast, unroll-loops", "omit-frame-pointer","inline")
//#pragma GCC option("arch=native","tune=native","no-zero-upper")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native,avx2")

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int getrnd(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

ll getrndll(ll l, ll r) {
    return uniform_int_distribution<ll>(l, r)(rng);
}

template <typename T1, typename T2>
inline bool relax(T1& a, const T2& b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}

template <typename T1, typename T2>
inline bool strain(T1& a, const T2& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}

// :::::::::::::::::::::::::::::::

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

void solve() {
    int x;
    cin >> x;
    
    cout << (360 / gcd(360, x)) << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    srand(time(0));
    
    int t = 1;
//    cin >> t;
    while (t--)
        solve();
    
    return 0;
}



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

int mymax(int a, int b)
{
	return a >= b ? a : b;
}

int main()
{
	int n;
	cin >> n;
	vector<int> Rt(n);
	for (int i = 0; i < n; i++) {
		cin >> Rt[i];
	}
	
	int posL = 0;
	int maxv = Rt[1] - Rt[0];
	for (int i = 1; i < n; i++) {
		if (Rt[i] < Rt[posL])
			posL = i;
		else
			maxv = mymax(maxv, Rt[i] - Rt[posL]);
	}
	cout << maxv << endl;
	return 0;
}

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

int main() {
  string s;
  cin >> s;
  int ans = 0;
  for (int i = 0; i <= s.size(); i++) {
    for (int j = 0; j < s.size() - i + 1; j++) {
      string tmp = s.substr(j, i);
      bool flag = true;
      for (int k = 0; k < tmp.size(); k++) {
        if (tmp[k] != 'A' && tmp[k] != 'T' && tmp[k] != 'G' && tmp[k] != 'C') {
          flag = false;
        }
      }
      if (flag) {
        if (ans < tmp.size()) {
          ans = tmp.size();
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,w;
int a[101],b[101];
int dp[101][100001];
int f(int x,int y)
{ 
  if(y>w)
    return -1e18;
  if(x==n)
    return 0;
  if(dp[x][y]!=-1)
    return dp[x][y];  
  dp[x][y]=max(f(x+1,y+a[x])+b[x],f(x+1,y));
  return dp[x][y]; 

}
int32_t main()
{  
  cin>>n>>w;
  for(int i=0;i<n;i++)
    cin>>a[i]>>b[i];
  memset(dp,-1,sizeof(dp));
  cout<<f(0,0);
  
}


Measured memory_bytes: 79104
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
typedef long long int ll;
template<typename T> T changeMax(T& a, T b){if(a < b)a = b;return 0;}
const ll MOD = 1000000007;

int main(){
int a,b,c,d;
cin >>a>>b>>c>>d;
if(abs(a-c)<=d || (abs(a-b)<=d && abs(b-c)<=d)) puts("Yes");
else puts("No");
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(v) (v).begin(),(v).end()
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
typedef pair<int, int> P;
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const ll MOD = 1e9+7;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main() {
	int n;
    ll d, a;
	cin >> n >> d >> a;
    vector<P> p(n);
    rep(i,n) cin >> p[i].first >> p[i].second;
    sort(all(p));
    d *= 2;
    ll tot = 0;
    queue<pair<ll, ll>> q;
    ll ans = 0;
    rep(i,n) {
        ll x = p[i].first;
        ll h = p[i].second;
        while (q.size() && q.front().first < x) {
            tot -= q.front().second;
            q.pop();
        }
        h -= tot;
        if (h>0) {
            ll num = (h+a-1)/a;
            ans += num;
            ll damage = num*a;
            tot += damage;
            q.emplace(x+d, damage);
        }
    }
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3456
from collections import deque
from bisect import bisect_left

INF = 10**9 + 1
N = int(input())
A = list(map(int, input().split()))
G = [[] for i in range(N)]
for i in range(N-1):
    u, v = list(map(int, input().split()))
    G[u-1].append(v-1)
    G[v-1].append(u-1)

LIS = [INF] * N
ans = [0] * N

stack = deque()
stack.append((0, None, None)) # (current_node, prev_node, old_val)
while stack:
    c_node, p_node, old_val = stack.pop()

    if c_node == -1:
        LIS[p_node] = old_val
        continue

    a = A[c_node]
    idx = bisect_left(LIS, a)
    old_val = LIS[idx]
    LIS[idx] = a 
    
    ans[c_node] = bisect_left(LIS, INF)

    stack.append((-1, idx, old_val))

    for next_node in G[c_node]:
        if next_node != p_node:
            stack.append((next_node, c_node, old_val))

print(*ans, sep="\n")

Measured memory_bytes: 148688
#include<string>
#include<iostream>
#include <algorithm>
#include<vector>
#include<functional>
#include <cstdlib>
#define ll long long
using namespace std;



int main(){
  ll N,K,now=1,keta=0;
  cin>>N>>K;
  while(true){
    now=now*K;
    keta++;
    if(now>N) break;
  }
  cout<<keta<<endl;
    return 0;
}


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

#define INF 0x3FFFFFFF

using namespace std;

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

int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  vector<int> a(n);
  int mini = INF;
  int maxi = -INF;
  int d = 0;
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    mini = min(mini, a[i]);
    maxi = max(maxi, a[i]);
    d = gcd(d, a[i]);
  }
  if (k > maxi) printf("IMPOSSIBLE\n");
  else if (k % d == 0) printf("POSSIBLE\n");
  else printf("IMPOSSIBLE\n");
  return 0;
}


Measured memory_bytes: 640
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using PLL = pair<LL,LL>;
using VPI = vector<PII>;
using VPL = vector<PLL>;
using VB = vector<bool>;
using VVB = vector<VB>;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
	//i=m -> n-1(昇順)
#define RREP(i,m,n) for(int i=(m);i>=(n);i--)
	//i=m -> n(降順)

int main(){
  LL s;
  cin >> s;
  VLL dp(s+10,0);
  LL sum = 1;
  dp[0] = 1;
  
  REP(i,3,s+1){
    dp[i] = sum;
    sum += dp[i-2];
    sum %= 1000000007;
  }
  
  
  cout << dp[s] << endl;
  
  return 0;
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,a[105],sum,ten;
signed main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		sum+=a[i];
	}
	sort(a,a+n);
	for(int i=0;i<n;i++){
		if(a[i]%10){
			ten=a[i];
			break;
		}
	}
	if(sum%10)cout<<sum<<endl;
	else if(ten)cout<<sum-ten<<endl;
	else cout<<0<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <sstream>
#define rep2(i,x,y) for (int i = x; i < (y); ++i)
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
int INF = 100100101;

int main()
{
  ios::sync_with_stdio(false);  cin.tie(0); cout.tie(0);
  string s;
  cin >> s;
  int ans = 0;
  rep(i, 3){
   	if(s[i] == 'R'){
      ans++;
    }
  }
  if(s[0] == 'R' && s[1] == 'S' && s[2] == 'R') ans--;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3588
#include<iostream>
using namespace std;
int n, m, i, x, y, ok;
int num[100005];
int main(){
    cin>> n >> m;
    for(i = 1; i <= m; i++){
        cin>> x >> y;
        num[x]++;
        num[y]++;
    }
    ok = 1;
    for(i = 1; i <= n; i++){
        if(num[i] % 2 == 1){
            ok = 0;
        }
    }
    if(ok == 1){
        cout<<"YES";
    }
    else{
        cout<<"NO";
    }
}


Measured memory_bytes: 640
#include<stdio.h>
int main(void)
{
	int a,b;
	scanf("%d %d",&a,&b);
	if(a<b){
		printf("a < b\n");
	}else if(a>b){
		printf("a > b\n");
	}else{
		printf("a == b\n");
	}
	return 0;
}

Measured memory_bytes: 2676
#include <iostream>
using namespace std;
int main() {
    int H,W,i,j;
    while (cin>>H>>W && (H!=0 || W!=0)) {
        for (i=0;i<H;i++) {
            for (j=0;j<W;j++) {
                cout << ((i+j)%2==0?'#':'.');
            }
            cout<<endl;
        }
        cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 3128
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); i++)
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
using namespace std;
typedef long long ll;

int main(){
    int a, b;
    cin >> a >> b;
    cout << (a-1)*(b-1) << endl;
    return 0;
}

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

int main()
{
    string s;
    cin >> s;
    if (s.at(0) == s.at(1))
    {
        cout << "Bad" << endl;
    }
    else if (s.at(1) == s.at(2))
    {
        cout << "Bad" << endl;
    }
    else if (s.at(2) == s.at(3))
    {
        cout << "Bad" << endl;
    }
    else
    {
        cout << "Good" << endl;
    }
}


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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template<typename H> bool chmin(H& v1, const H v2) { if (v1 > v2) { v1 = v2; return true; } return false; }
template<typename H> bool chmax(H& v1, const H v2) { if (v1 < v2) { v1 = v2; return true; } return false; }
template<typename H> void read(H& head) { cin >> head; }
template<typename H, typename ...T> void read(H& head, T& ...tail) { cin >> head; read(tail...); }
template<typename H> void write(H head) { cout << head << '\n'; }
template<typename H, typename ...T> void write(H head, T ...tail) { cout << head << " "; write(tail...); }
template<typename ...T> void die(T ...tok) { write(tok...); exit(0); }

ll bm(ll b, ll p, ll m) {
	ll r = 1;
	for (; p; p >>= 1, b = b * b % m) if (p & 1ll) r = r * b % m;
	return r;
}

void simp(ll &a, ll &b) {
	if (a == 0) a = 0, b = 1;
	else if (b == 0) a = 1, b = 0;
	else {
		if (b < 0) a = -a, b = -b;
		ll g = __gcd(abs(a), abs(b));
		a /= g, b /= g;
	}
}

pair<ll, ll> inv(ll a, ll b) {
	ll g = -b, h = a;
	simp(g, h);
	return {g, h};
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	ll n; cin >> n;
	map<pair<ll, ll>, ll> m;

	ll worst = 0;

	rep(i, 0, n) {
		ll a, b; read(a, b);
		if (!a && !b) {
			worst++;
			continue;
		}
		simp(a, b);
		m[{a, b}]++;
	}

	const ll mod = 1000000007;
	ll ans = 1;
	typedef pair<ll, ll> pll;
	vector<pair<pll, ll>> v(all(m));
	for (auto a : v) {
		pll p = a.first;
		pll iv = inv(p.first, p.second);
		ll freq = m[p];
		ll freq2 = m[iv];

		m[p] = 0;
		m[iv] = 0;

		if (!freq2) {
			//write("SG", p.first, p.second, freq, bm(2, freq, mod));
			ans = (ans * bm(2, freq, mod)) % mod;
		} else {
			//write("DB", p.first, p.second, freq, freq2, bm(2, freq, mod) + bm(2, freq2, mod) - 1);
			ans = (ans * ((bm(2, freq, mod) + bm(2, freq2, mod) + mod - 1) % mod)) % mod;
		}

		//write(a.first.first, a.first.second, inv(a.first.first, a.first.second).first, inv(a.first.first, a.first.second).second, a.second);
	}

	ans = (ans + mod - 1ll) % mod;
	ans = (ans + worst) % mod;

	write(ans);
}


Measured memory_bytes: 32876
<?php
fscanf(STDIN, "%d", $n);
$ps=explode(' ',trim(fgets(STDIN)));
$cnt=1;
$min=$ps[0];
for($i=1;$i<$n;$i++){
  if($ps[$i] < $min) {
    $min=$ps[$i];
    $cnt++;
  }
}
echo $cnt;

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

struct UnionFind {
  vector<int> d;
  UnionFind(int n=0): d(n,-1) {}
  int find(int x) {
    if (d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  int root(int x) {
    if (d[x] < 0) return x;
    else return d[x] = root(d[x]);
  }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x,y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y);}
  int size(int x) { return -d[find(x)];}
};

ll solve(int n, int m, vector<int> x, vector<int> y, vector<int> z){
  UnionFind uf(n);
  for (int i=0; i<m; ++i) uf.unite(x[i], y[i]);
  set<int> se;
  for (int i=0; i<n; i++)se.insert(uf.root(i));
  return (int)se.size();
}

int main() {
  int n, m;
  cin >> n >> m;
  vector<int>x(m), y(m), z(m);
  rep(i, m){
    cin >> x[i] >> y[i] >> z[i];
    --x[i]; --y[i];
  }
  cout << solve(n, m, x, y, z) << endl;
  return 0;
}


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

int f[100010][20];
int power[20];
int a[100010];

int work(int a, int b){
	if (a == b) return 1;
	if (a > b) swap(a, b);
	int ans = 0;
	for (int i = 19; i >= 0; i--){
		if (f[a][i] < b) a = f[a][i], ans += power[i];
	}
	return ans + 1;
}

int main(){
	power[0] = 1;
	for (int i = 1; i < 20; i++){
		power[i] = power[i - 1] * 2;
	}
	int n, L;
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		scanf("%d", &a[i]);
	}
	scanf("%d", &L);
	int pos = 0;
	for (int i = 0; i < n; i++){
		while (pos < n && a[pos] - a[i] <= L){
			pos++;
		}
		pos--;
		f[i][0] = pos;
	}
	for (int j = 1; j < 20; j++){
		for (int i = 0; i < n; i++){
			f[i][j] = f[f[i][j - 1]][j - 1];
		}
	}
	int m;
	scanf("%d", &m);
	for (int i = 0; i < m; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		a--, b--;
		printf("%d\n", work(a, b));
	}
	return 0;
}


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

typedef long long ll;
typedef pair<int,int> P;

const int INF=1e9;
const int MOD=1e9+7;

int main(){
    int N; cin >> N;
    int res=(N+999)/1000;
    cout << res*1000-N << endl;
}

Measured memory_bytes: 3588
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
  

n,k=[int(x) for x in input().split()]

for i in range(1,k+1):
  #青をi個に分ける(最低数(i-1個)の赤で)
  a=comb(k-1, i-1, 10**9+7)
  #赤の残りは(n-k)-(i-1)こ
  #これをいいかんじにならべる
  b=comb(n-k+1, i, 10**9+7)
  print((a*b)%(10**9+7))


Measured memory_bytes: 76380
/*
???????????´??° a ??¨ b ?????????????????§?????\?????????????¨??????????????????°?????????????????????????????????

a ?? b ??? d (??´??°)
a ?? b ????????? ??? r (??´??°)
a ?? b ??? f (???????°???°?????°)

*/
#include <iostream>
#include <iomanip>	// ????????°????????????????????¨??????

int main() {
	int a, b;
	std::cin >> a >> b;
	int d = a/b;
	int r = a%b;
	double f = (double)a / (double)b;

	std::cout << d << " " << r << " " << std::fixed << std::setprecision(10) << f << std::endl;
	return 0;
}

Measured memory_bytes: 3272
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <atcoder/all>

#define F first
#define S second
#define int long long
#define ll long long
//#define int  unsigned long long
#define pb push_back
//#define double long double

using namespace std;
using namespace atcoder;
using namespace __gnu_pbds;
typedef  tree< int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 300000;
const int K = 100000;
const int mod = 998244353;
vector <int> a;
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n;
    cin >> n;
    n += n;
    int ans = n - 1;
    for (int i = 2; i * i <= n; i++){
        if (n % i) continue;
        int x = 1;
        while (n % i == 0){
            n /= i;
            x *= i;
        }
        a.pb(x);
    }
    if (n != 1) a.pb(n);
    int m = (int)a.size();
    for (int mask = 0; mask < (1 << m); mask++){
        vector <int> r, p;
        for (int i = 0; i < m; i++){
            if ((1 << i) & mask){
                r.pb(0);
            } else{
                r.pb(a[i] - 1);
            }
            p.pb(a[i]);
        }
        auto x = crt(r, p);
        if (x.F != 0) ans = min(ans, x.F);
    }
    cout << ans;
}


Measured memory_bytes: 3704
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  loop(i,0,n)
#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define vi vector<int>
#define vl vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>

int main(){
    ll int n;
    ll ans=LLONG_MAX;
    cin>>n;
    vl v;
    ll int a=1,b=0;
    ll int f=1;
    ll int tmp;
    for(ll int i=1;i<=sqrt(n);i++){
        if(n%i==0){
            a=i;
            b=n/i;
            ans = min(ans,(a-1)+(b-1));
        } 
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
n = int(input())
v = list(map(int, input().split()))

map_even_elem_dict = {}
map_odd_elem_dict = {}
for i,e in enumerate(v):
    if i % 2 == 0:
        if e in map_even_elem_dict:
            map_even_elem_dict[e] += 1
        else:
            map_even_elem_dict[e] = 1
    if i % 2 == 1:
        if e in map_odd_elem_dict:
            map_odd_elem_dict[e] += 1
        else:
            map_odd_elem_dict[e] = 1

even_dict_list = []
odd_dict_list = []

for k, v in map_even_elem_dict.items():
    even_dict_list.append((v, k))
    
for k, v in map_odd_elem_dict.items():
    odd_dict_list.append((v, k))
    
even_dict_list.sort()
odd_dict_list.sort()

max_even_occurence, max_even_elem = even_dict_list[-1]
max_odd_occurence, max_odd_elem = odd_dict_list[-1]

if max_even_elem != max_odd_elem:
    print(n // 2 - max_even_occurence + n // 2 - max_odd_occurence)
else:
    if max_even_occurence > max_odd_occurence:
        second_max_odd_occurence, _ = odd_dict_list[-2]
        print(n // 2 - max_even_occurence + n // 2 - second_max_odd_occurence)
    elif max_even_occurence < max_odd_occurence:
        second_max_even_occurence, _ = even_dict_list[-2]
        print(n // 2 - second_max_even_occurence + n // 2 - max_odd_occurence)
    else:
        if max_even_occurence == n // 2:
            print(n // 2)
        else:
            second_max_even_occurence, _ = even_dict_list[-2]
            second_max_odd_occurence, _ = odd_dict_list[-2]
            print(n // 2 - max_even_occurence + n // 2 - max(second_max_even_occurence, second_max_odd_occurence))

Measured memory_bytes: 19596
// SeeAlso: 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define MAX 100000
#define NIL -1
#define MOD 1000000007

typedef int _loop_int;
#define rep(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define debug(x) cout<<#x<<": "<<x<<endl
#define debig_vec(v) cout<<#v<<":";rep(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

// 最大公約数
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
// 最小公倍数
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}

#define print2D(h, w, arr) rep(i, h) { rep(j, w) cout << arr[i][j] << " "; cout << endl; }
template<class T> void print(const T& x){cout << setprecision(12) << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }

int main() {

    int n;
    cin >> n;
    priority_queue<ll> pq;
    rep(i, n) {
        ll a;
        cin >> a;
        pq.push(a);
    }

    int ans = 0;
    rep(i, n) {
        if(i%2==0) {
            ans += pq.top();
        } else {
            ans -= pq.top();
        }
        pq.pop();
    }

    print(ans);
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] h = new int[n];
        int pre = n-1;
        boolean yes = true;

        for (int i = 0; i < n; i++) {
            h[i] = scanner.nextInt();
        }
        for (int i = n-2; i >= 0 ; i--) {
            if(h[i] - h[pre] == 1) {
                h[i]--;
            } else if(h[i] - h[pre] > 1) {
                yes = false;
                break;
            }
            pre--;
        }

        if(yes){
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}



Measured memory_bytes: 49636
#include<iostream>
#include<cmath>
#include<numeric>
#include<string>
#include<algorithm>
#include<vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<n;i++)
#define int64 long long 
using namespace std;

int main(){
  int N;
  cin>>N;
  int64 A[N],a[N];
  rep(i,N){
    cin>>A[i];
    a[i]=A[i]-i;
  }
  sort(a,a+N);
  int64 center=floor((N-1)/2);
  int64 min=0;
  rep(i,N){
    min+=abs(a[center]-a[i]);
  }
  cout<<min<<endl;
}


Measured memory_bytes: 3328