akhauriyash/Code-Regression huggingface dataset:
var
	n,i:Longint;
	ans,a,m:int64;
	sum:array[1..100000]of int64;
function power(a,b:int64):int64;
var s:int64;
begin
	if b=0 then power:=1
	else begin
		s:=power(a*a mod m,b div 2);
		if b mod 2=1 then s:=s*a mod m;
		power:=s;
	end;
end;
begin
	m:=1000000007;
	read(n);
	sum[1]:=1;
	for i:=2 to n do sum[i]:=(sum[i-1]+power(i,m-2))mod m;
	for i:=1 to n do begin
		read(a);
		ans:=(ans+(sum[i]+sum[n-i+1]-1)mod m*a mod m)mod m;
	end;
	for i:=1 to n do ans:=ans*i mod m;
	writeln(ans);
end.


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

using namespace std;

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())

void Yes(){
	cout<<"Yay!"<<endl;
}
void No(){
	cout<<":("<<endl;
}

signed main(){

	lli m1,d1,m2,d2;
	cin>>m1>>d1>>m2>>d2;

	cout<<((m1==m2)?0:1)<<endl;

	return 0;
}

Measured memory_bytes: 256
from functools import reduce

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)

def gcd_list(numbers):
    return reduce(gcd, numbers)

n=int(input())
a=list(map(int,input().split()))

print(gcd_list(a))
           

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

const int N = 1e5+5, M = 1e6+6, OO = 0x3f3f3f3f;
vector<int> v1, v2;
set<vector<int> > vs;
vector<int> tmp;
int n;
void brute(int idx)
{
    if(idx == n)
    {
        if(tmp.size() == n)
        {
            // for(auto x : tmp)
            //     cout<<x<<" ";
            // puts("");
            vs.insert(tmp);
        }
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if(find(tmp.begin(), tmp.end(), i) == tmp.end())
        {
            tmp.push_back(i);
            brute(idx+1);
            tmp.pop_back();
            // brute(idx+1);
        }

    }
    
}
int main()
{
    // freopen("a.out", "wt", stdout);
    scanf("%d", &n);
    for (int i = 0;  i<n ; i++)
    {
        int x; cin>>x;
        v1.push_back(x);
    }
    for (int i = 0;  i<n ; i++)
    {
        int x; cin>>x;
        v2.push_back(x);
    }
    brute(0);
    // for (auto v : vs)
    // {
    //     for(auto x : v)
    //         cout<<x<<" ";
    //     puts("");
    // }
    int idx1 = -1, idx2 = -2;
    int num = 0;
    for(auto v : vs)
    {
        if(v1 == v)
            idx1 = num;
        if(v2 == v)
            idx2 = num;
        num++;
    }
    cout<<abs(idx1- idx2)<<endl;
    
    return 0;
}

Measured memory_bytes: 4608
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <cmath>
#include <set>
#include <bitset>
#include <limits>

using namespace std;

#define ll long long

int main(void){
    int s, w;
    cin >> s >> w;

    if(w >= s){
        cout << "unsafe" << endl;
    }else{
        cout << "safe" << endl;
    }

    return 0;
}

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

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#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;

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

	string st; cin >> st;
	int n = 0, w = 0, s = 0, e = 0;
	for (char c : st) {
		if (c == 'N') n++;
		if (c == 'W') w++;
		if (c == 'S') s++;
		if (c == 'E') e++;
	}
	n = !!n, w = !!w, s = !!s, e = !!e;
	if ((n ^ s) || (w ^ e)) cout << "No" << endl;
	else cout << "Yes" << endl;
}


Measured memory_bytes: 256
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]

M = (H+W)*80
dp = [[0] * W for _ in range(H)]
dp[0][0] |= 1 << M
for i in range(H):
    for j in range(W):
        bit = dp[i][j]
        if i > 0:
            bit |= dp[i-1][j]
        if j > 0:
            bit |= dp[i][j-1]
        dp[i][j] = (bit >> C[i][j]) | (bit << C[i][j])
ans = M
for i in range(M*2):
    if (dp[-1][-1] >> i) & 1:
        ans = min(ans, abs(M-i))
print(ans)

Measured memory_bytes: 58844
#include <iostream>
using namespace std;
int main() {
    int n, h, max=0, cnt=0;
    cin >> n;
    for(int i=0; i<n; i++) {
        cin >> h;
        if(max<=h) {
            max = h;
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

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

sum = 1
if 0 in A:
  sum = 0
ans = 0
for x in A:
  sum *= x
  if sum > 1000000000000000000:
    ans = -1
    break
  if sum == 0:
    ans = 0
    break

if ans < 0:
  print(ans)
else:
  print(sum)

Measured memory_bytes: 84740
n, k = map(int, input().split())
a = list(map(int, input().split()))
path = []
x = 1
path.append(x)
for i in range(n):
    x = a[x-1]
    path.append(x)
#print(path)
count = [0]*n
roop_st = 0
roop_len = 0
for town in path:
    count[town-1] += 1
    if count[town-1] == 2:
        roop_st = town
        break
roop_st_idx = path.index(roop_st)
roop_fin_idx = path.index(roop_st, roop_st_idx+1)
#print(roop_st_idx, roop_fin_idx)
if k >= roop_st_idx:
    k_mod = (k - roop_st_idx) % (roop_fin_idx - roop_st_idx)
    print(path[roop_st_idx + k_mod])
else:
    print(path[k])

Measured memory_bytes: 100292
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <stack> // s.top()
#include <bitset>
#include <queue> // s.front()
using namespace std;

typedef long long Int;
typedef pair<Int,Int> P;
#define print(x) cout<<(x)<<endl

#define INF10 10000000000
#define INF5 100000
#define EPS 1e-10
#define MOD 1000000007

 

int main() {
	int N, K; cin >> N >> K;
	int out = K;
	for (int i = 1; i < N; i++) {
		out *= (K - 1);

	}
	print(out);







	return 0;
}

Measured memory_bytes: 256
D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]

types = []
last = [-1] * 26
S = 0
for d in range(D):
    # search type
    M = -float('inf')
    for tt in range(26):
        _last = last[:]
        tmp = s[d][tt]

        _last[tt] = d
        for i in range(26):
            tmp -= c[i] * (d - _last[i])

        if tmp > M:
            M = tmp
            M_tt = tt

    S += s[d][M_tt]

    last[M_tt] = d
    for i in range(26):
        S -= c[i] * (d - last[i])
    types.append(M_tt)


last = [-1] * 26
S = 0
ans = []
for d in reversed(range(D)):
    seq = []
    for tt in range(26):
        _last = last[:]
        tmp = s[d][tt]

        _last[tt] = d
        for i in range(26):
            tmp -= c[i] * (d - _last[i])

        seq.append([tmp, tt])

    seq.sort(reverse=True)

    tmpmax = -float('inf')
    for i in range(15):
        tt = seq[i][1]
        _last = last[:]
        _types = types[:]
        _types[d] = tt
        _S = S

        for dd in range(d, D):
            _S += s[dd][_types[dd]]
            _last[_types[dd]] = dd
            for i in range(26):
                _S -= c[i] * (dd - _last[i])

        if _S > tmpmax:
            cand = tt
            tmpmax  = _S

    S += s[d][cand]
    last[cand] = d
    for i in range(26):
        S -= c[i] * (d - last[i])

    ans.append(cand + 1)
    
for _ans in reversed(ans):
    print(_ans)


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

int main(){
    int n, q;
    cin >> n;
    map<int, int> nums;
    long long sum = 0;
    for (int i = 0; i < n; i++){
        int inp;
        cin >> inp;
        sum += inp;
        nums[inp]++;
    }
    cin >> q;
    for (int i = 0; i < q; i++){
        int b, c;
        cin >> b >> c;
        sum += (c - b) * nums[b];
        nums[c] += nums[b];
        nums[b] = 0;
        cout << sum << '\n';
    }
    return 0;
}



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

#define debug(x) cout << #x" = " << x;

#define st first
#define nd second

using namespace std;
using namespace placeholders;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

const int MAXN = 2E3 + 10;
const int MOD = 1E9 + 7;

ll inv[MAXN], fac[MAXN], facinv[MAXN];

ll modExp(ll e, ll n, ll m = MOD){
	ll ret = 1;
	for (; n; n >>= 1, e = e * e % m)
		if (n & 1)
			ret = ret * e % m;
	return ret;
}

void getInv(int n = MAXN - 1, int m = MOD){
	inv[0] = 0, inv[1] = 1;
	fac[0] = fac[1] = 1;
	facinv[0] = facinv[1] = 1;
	for (int i = 2; i <= n; ++i){
		inv[i] = inv[m % i] * (m - m / i) % m;
		fac[i] = fac[i - 1] * i % m;
		facinv[i] = facinv[i - 1] * inv[i] % m;
	}
}

ll C(int n, int m){
	return m < 0 || n < m ? 0 : fac[n] * facinv[m] % MOD * facinv[n - m] % MOD;
}

inline void update(int &x, int y){
	if ((x += y) >= MOD)
		x -= MOD;
}

int f[MAXN][MAXN];

int main(){
	getInv();

	int n, k;
	scanf("%d%d", &n, &k);
	f[0][0] = 1;
	for (int i = 1; i <= k - 1; ++i){
		int s = f[i - 1][i - 1];
		for (int j = i; j < n; ++j){
			update(f[i][j], s);
			update(f[i][j], f[i - 1][j]);
			update(s, f[i - 1][j]);
//			printf("%d %d %d\n", i, j, f[i][j]);
		}
	}
	int ans = 0;
	for (int i = 0; i < n; ++i)
		update(ans, f[k - 1][i]);
	printf("%d\n", (int)(ans * modExp(2, max(0, n - k - 1)) % MOD));
	return 0;
}


Measured memory_bytes: 14080
N,M = map(int,input().split())
H = list(map(int,input().split()))
B = []
for i in range(M):
  a,b = map(int,input().split())
  if H[a-1] < H[b-1]:
    B += [a]
  elif H[a-1] == H[b-1]:
    B += [a,b]
  elif H[a-1] > H[b-1]:
    B += [b]
C = set(B)

print(N - len(C))
  


Measured memory_bytes: 20040
#include <stdio.h>
#include <iomanip>
#include <time.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
#define mod 1000000007
#define ll long long
#define pi acos(-1)
using namespace std;

int main(){
	ios::sync_with_stdio(0);	
	ll a,b,c,k;
	cin>>a>>b>>c>>k;
	ll sum = 0;
	if(k>=a){
		sum+=a;
		k-=a;
	}
	else{
		cout<<k;
		return 0;
	}
	
	if(k>=b){
		k-=b;
	}
	else{
		cout<<sum;
		return 0;
	}
	cout<<sum-k;
	
    return 0; 
}

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

using namespace std;

bool desc(int a, int b){
    return a>b;
}

int main()
{
   //int t,l=1;
   
   //cin>>t;
   
   //while(t--){
       int n;
       cin>>n;
       int e = 1e7,ans,dis=0;
       int a[n],ma=-1,mb=-1,ai,bi,ta,tb;
       
       map<int,int> fa,fb;
       
       for(int i = 0 ; i < n ; i++){
           cin>>a[i];
           if(i%2==0) fa[a[i]]++;
           else fb[a[i]]++;
           
           if(i!=0&&a[i]!=a[i-1]) dis = 1;
       }
       
       for(auto au : fa){
           if(au.second>ma) {ma = au.second; ai = au.first;}
       }
       for(auto au : fb){
           if(au.second>mb) {mb = au.second; bi = au.first;}
       }
       
       if(dis==0){
           cout<<n/2;
           return 0;
       }
       else if(ai==bi){
           if(fa[ai]>fb[bi]){
               mb=-1;
               for(auto au : fb){
                    if(au.first==bi) continue;
                    if(au.second>mb) {mb = au.second;}
                }
           }
           else if(fa[ai]<fb[bi]){
               ma=-1;
               for(auto au : fa){
                    if(au.first==ai) continue;
                    if(au.second>ma) {ma = au.second;}
                }
           }
           else{
               ta=-1;tb=-1;
               for(auto au : fa){
                    if(au.first==ai) continue;
                    if(au.second>ta) {ta = au.second;}
                }for(auto au : fb){
                    if(au.first==bi) continue;
                    if(au.second>tb) {tb = au.second;}
                }
                if(ta>tb) ma=ta;
                else mb=tb;
           }
       }
       
       
     cout<<n-ma-mb;
       //l++;
   //}
   
   return 0;

}

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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ll long long

using namespace std;

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

    int n,n1;
    cin >> n;
    n1 = n+1;
    ll a[n1];
    REP(i,n) cin >> a[i];

    a[n] = 0;
    FOR(i,1,n) a[i] += a[i-1];
    sort(a,a+n1);
    ll ans=0,kpa=a[0],cnt=0;

    FOR(i,1,n1){
        if(kpa==a[i]) ++cnt;
        else{
            ans += (cnt+1)*cnt/2;
            kpa = a[i];
            cnt = 0;
        }
    }
    ans += (cnt+1)*cnt/2;

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


Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);;
		int a = scan.nextInt();
		int b = scan.nextInt();

		System.out.println(a / b + " " + a % b + " " + String.format("%.8f", (double)a / b));
		scan.close();
	}
}


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

using namespace std;
using vecint = vector<int>;
using ll = int64_t;

bool ok(const vecint& a, const int th, vecint& v) {
  ll n = a.size();
  v.assign(n*4, 0);
  int offset = n*2;
  ll cnt = 0;
  ll sum = 0;
  REP(i,n) {
    v[offset] += 1;
    if (a[i] >= th) {
      offset -= 1;
      sum -= v[offset];
    } else {
      sum += v[offset];
      offset += 1;
    }
    cnt += sum;
  }
  ll m = n * (n+1) / 2;
  ll mid = m/2 + 1;
  return cnt >= mid;
}

int main()
{
  int n;
  scanf("%d", &n);
  vecint a(n);
  REP(i,n) scanf("%d", &a[i]);
  vecint b = a;
  b.push_back(0);
  b.push_back(1000000007);
  sort(ALL(b));
  b.erase(unique(ALL(b)), end(b));
  int hi = b.size() - 1;
  int lo = 0;
  vecint v(n*4);
  while ((hi - lo) > 1) {
    int mid = (hi + lo) / 2;
    if (ok(a, b[mid], v)) {
      hi = mid;
    } else {
      lo = mid;
    }
  }
  printf("%d\n", b[lo]);
  return 0;
}


Measured memory_bytes: 2564
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 1e5 + 7;
const int Inf = 1 << 30;
const ll INF = 1ll << 60;
int h, n;
int a[maxx];

bool cmp(int x, int y) {
	return x > y;
}

int main() {
	scanf("%d %d", &h, &n);
	int sum = 0;
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		sum += a[i];
	}
	if(sum >= h) puts("Yes");
	else puts("No");
	return 0;
}

Measured memory_bytes: 640
/*Alohomora*/
#include<bits/stdc++.h>
#define ll         long long
#define fl(i,n)    for(i=0;i<n;i++)
#define fld(i,a,b) for(i=a;i>b;i--)
#define fli(i,a,n) for(i=a;i<n;i++)
#define inp(i,a,n) for(i=0;i<n;i++) {cin>>a[i];}
#define op(i,a,n)  for(i=0;i<n;i++) {cout<<a[i]<<" ";}
#define pb         push_back
#define mp         make_pair
#define mod1       1000000007
#define speedup    ios_base::sync_with_stdio(false),cin.tie(0)
using namespace std;
ll fact(ll n){ if(n==0){return 1;}return (n*fact(n-1))%mod1;}
ll power(ll x, ll y,ll mod){ll out = 1;while (y > 0){if (y & 1) out=(out*x)%mod;y = y>>1;x = (x*x)%mod;}return out%mod;}
ll inverse(ll a){return power(a,mod1-2,mod1);}
ll gcd(ll a,ll b){if(b==0){return a;}gcd(b,a%b);}
ll a[2000000];
void sieve(){ll i,j;fli(i,2,1000001){if(a[i]==0){for(j=i*i;j<1000001;j+=i){a[j]=1;}}}}
map<ll,vector<ll> >m1;
vector<ll>v1;
bool compar(const pair<ll,ll> &a, const pair<ll,ll> &b) 
{ 
    return (a.second < b.second);
} 
ll level[1000000];
vector<ll>root;
set<ll>s1;
void factorise(long long n) 
{ 
    while (!(n%2)) 
    { 
        n >>= 1; 
        s1.insert(2);
    } 
    for (long long i=3; i<=sqrt(n); i+=2) 
    { 
        while (n%i==0) 
        { 
        	s1.insert(i);
            n=n/i; 
        } 
    } 
  	if (n>2) 
  	{
       s1.insert(n);
	}
} 
void comp()
{
	ll i,j,k,m,n,temp,t1,t2,t3;
	cin>>n;
	ll count=0;
	vector<ll>v1;
	vector<ll>v2;
	fl(i,n+1)
	{
		cin>>j;
		v1.pb(j);
	}
	fl(i,n)
	{
		cin>>j;
		v2.pb(j);
	}
	ll ans=0;
	fl(i,n)
	{
		temp=min(v2[i],v1[i]+v1[i+1]);
		ans+=temp;
		if(temp>v1[i])
		{
			v1[i+1]=v1[i+1]+v1[i]-temp;
		}
	}
	cout<<ans<<"\n";
}	 
int main()
{
	speedup;
	ll i=0,t;
	ll n;
	//cin>>t;
	t=1;
	while(t--)
	{
	 comp();
	}
}

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

int main(){
	int n;
	cin >> n;
		
	vector<int> v(n);
	for(int &e : v)
		cin >> e;
		
	long long ans = 0;
	for(int i = 0;i < n;++i)
		for(int j = i+1;j < n;++j)
			ans += v[i] * v[j];
	
	cout << ans;
}


Measured memory_bytes: 3624
// Ivan Zanov
// Template
#include <chrono>
#include <iostream>
#include <utility>
#include <bitset>
#include <vector>
#include <set>
#include <unordered_map>
#include <map>
#include <assert.h>
#include <cmath>
#include <algorithm>
#include <complex>
#include <deque>
#include <iomanip>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <memory>
#include <queue>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <sstream>
#include <exception>
#include <functional>
#include <cstring>
#include <cstdlib>
using namespace std;
using namespace std :: chrono;
#define lowbit(x) ((x)&((x)^((x)-1)))
#define max(a,b) (a<b?b:a)
#define IOS ios_base::sync_with_stdio(0);
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define INF (int)1e9
#define EPS (int)1e-9
#define bit_count __builtin_popcount
#define gcd __gcd
#define max3(a, b, c) max(a, max(b,c))
#define min3(a, b, c) min(a, min(b,c))
#define abs(x) (x < 0 ? (-x) : x)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
inline void set_bit(int & n, int b) { n |= (1 << (int) b); }
inline void unset_bit(int & n, int b) { n &= ~(1 << (int) b); }
inline bool check_bit(int n, int pos) { return ( n & (1 << (pos))); }
inline ll lcm(ll a, ll b){ return (a * b / gcd(a,b));}
inline ll square(ll a){return (a * a);}
bool prime(long long n)
{
	int cnt = 0;
	for(int i = 1; i <= sqrt(n);i++)
	{
		if(n % i == 0)
		{
			cnt++;
			if(n / i != i)
				cnt++;
		}
	}
	if(cnt == 2)
		return true;
	return false;
}
int main() {
	long long n;
	cin>>n;
	while(true)
	{
		if(prime(n) == true)
		{
			cout<<n<<endl;
			return 0;
		}
		n++;
	}
	/*auto start = high_resolution_clock::now();
	auto end = high_resolution_clock::now();
	auto duration = duration_cast<microseconds>(stop - start);
	cout<<fixed<<setprecision(3)<<duration.count() * 1e-6<<endl;*/
    return 0;
}

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

int main() {
  int N;
  cin >> N;
  int x[N], y[N];
  for (int i = 0; i < N; ++i)
    cin >> x[i] >> y[i];

  double ans = 0;
  for (int i = 0; i < N; ++i)
    for (int j = i + 1; j < N; ++j)
      ans +=
          sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));

  cout << setprecision(12) << (ans * 2 / N);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()

using ll = long long;
using ull = unsigned long long;
using namespace std;

int main() {
    int A, B;
    cin >> A >> B;
    if (A > 8 || B > 8) {
        cout << ":(" << endl;
    } else {
        cout << "Yay!" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
N = int(input())
A = [int(a) for a in input().split()]

cnt = 0
for i in range(N):
    mni = i
    for j in range(i + 1, N):
        if A[j] < A[mni]:
            mni = j
    if i != mni:
        A[i], A[mni] = A[mni], A[i]
        cnt += 1

print(*A)
print(cnt)


Measured memory_bytes: 5608
#include<bits/stdc++.h>
#define fi first
#define se second
#define Mp make_pair
#define pb push_back
#define rep(i, j, k) for (int i = (j); i <= (k); i++)
#define per(i, j, k) for (int i = (j); i >= (k); i--)
using namespace std;

typedef long long ll;
typedef double db;
typedef pair<int, int> PII;
typedef vector<int> VI;

const int N = 2e5+3;
int n;
ll k,a[N],f[N];

ll check(ll lim){
    ll ret=0;
    rep(i,1,n) ret+=max(0ll,a[i]-lim/f[i]);
    return ret;
}

int main(){
    scanf("%d%lld",&n,&k);
    rep(i,1,n) scanf("%lld",&a[i]);
    rep(i,1,n) scanf("%lld",&f[i]);
    sort(a+1,a+1+n); sort(f+1,f+1+n,greater<int>());
    ll l=0,r=0,mid;
    rep(i,1,n) r=max(r,(ll)a[i]*f[i]);
    while(l<r){
        mid=(l+r)>>1;
        if(check(mid)<=k) r=mid;
        else l=mid+1;
    }
    printf("%lld\n",l);
    return 0;
}

Measured memory_bytes: 3456
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define repLRE(i, l, r) for (ll i = (l); i <= (r); ++i)
#define rrepLRE(i, l, r) for (ll i = (l); i >= (r); --i)
#define Sort(v) sort(v.begin(), v.end())
#define rSort(v) sort(v.rbegin(), v.rend())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

ll dx[9] = {-1, 1, 0, 0, -1, -1, 1, 1, 0};
ll dy[9] = {0, 0, -1, 1, -1, 1, -1, 1, 0};

/* Macros reg. ends here */

const ll INF = 1LL << 50;

static const long long mod = 1000000007;

int main() {
  // ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);

  ll nq;
  cin >> nq;

  vll qs(nq), as, bs;
  rep(i, nq) {
    cin >> qs[i];
    if (qs[i] == 1) {
      ll a, b;
      cin >> a >> b;
      as.push_back(a), bs.push_back(b);
    }
  }


  vll xs = as;
  xs.push_back(-INF);
  ll n = xs.size();  
  map<ll, ll> rxs;
  Sort(xs);
  rep(i, n) rxs[xs[i]] = i;

  ll nbit = n + 5;
  vP BIT(nbit, P(0, 0));  // P of sumval, sumnum
  auto add = [&](ll i, ll x) {
    while (i <= nbit) {
      BIT[i].first += x;
      BIT[i].second++;
      i += i & (-i);
    }
  };

  auto get = [&](ll i) {
    P ret(0, 0);
    while (i > 0) {
      ret.first += BIT[i].first;
      ret.second += BIT[i].second;
      i -= i & (-i);
    }
    return ret;
  };

  ll bsum = 0;
  ll nt = 0;
  rep(i, nq) {
    if (qs[i] == 1) {
      bsum += bs[nt];
      add(rxs[as[nt]], as[nt]);
      nt++;
    } else {
      ll l = 0, r = n;
      ll yy = (nt - 1) / 2;
      while (l + 1 < r) {
        ll m = (l + r) / 2;
        if (get(m).second <= yy) {
          l = m;
        } else {
          r = m;
        }
      }
      ll totalx = xs[r] * (get(l).second - get(n + 1).second + get(r).second);
      ll fval = totalx - get(l).first + (get(n + 1).first - get(r).first) + bsum;
      cout << xs[r] << " " << fval << endl;
    }
  }

  return 0;
}


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

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

  long long int sum_0 = 0;
  long long int sum_1 = 0;

  for(int i = 0;i < S.size();i++){
    if(S[i] == '0')sum_0++;
    if(S[i] == '1')sum_1++;
  }

  long long ans = min(sum_0,sum_1) * 2;

  cout << ans << endl;

  return 0;
}


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

using namespace std;

using ll = long long;
using ld = long double;

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

    int n, d;
    cin >> n >> d;

    int b = 2 * d + 1;
    cout << (n + b - 1) / b << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pi 3.1415926535897932384626
using namespace std;
      
struct P{
  int x,y;
  bool operator < (const P &a )const{
    //if(y!=a.y)
    return y>a.y;
  };
};

int a,b,c,d,i,k,n,m,e,dx[10]={1,0,-1,0,1,1,-1,-1},dy[10]={0,1,0,-1,1,-1,1,-1};
long long o[1200511],re[1001011];
long long l[1000101];
int j[1];

long long x,y,z,mod=1000000007;
//string r;
char r[3331];

P u[1];
queue<int> q;
//stack<int> s;
set<int> s;
map<long long,int> p;

vector<int> v[1];

bool as(P a,P b)
{
  //if(a.x!=b.x)
  //return a.x<b.x;
  return a.x<b.x;
}

long long po(long long x,long long y)
{
  long long p=1;
  for(;y;x*=x,x%=mod,y/=2)
    if(y%2)p*=x,p%=mod;
  return p;
}

long long f(int n,int m)
{
  if(n<m) return 0;
  return o[n]*re[m]%mod*re[n-m]%mod;
}

int main()
{
  o[0]=re[0]=l[0]=1;
  for(int t=1;t<=1000000;t++)
    o[t]=o[t-1]*t%mod,l[t]=l[t-1]*3%mod,re[t]=po(o[t],mod-2);
  scanf("%d %d %d",&a,&b,&c);
  if(b>c) swap(b,c);
  y=1;
  x=l[b+c];
  for(int t=1;t<=b+c;t++)
  {
    if(t<=b) y*=2,y%=mod,x+=f(a+t-1,a-1)*y%mod*l[b+c-t]%mod;
    else if(t<=c)
    {
      y=y*2-f(t-1,b)+mod;
      y%=mod;
      x+=f(a+t-1,a-1)*y%mod*l[b+c-t]%mod;
    }
    else
    {
      y=y*2-f(t-1,b)-f(t-1,c)+mod*2;
      y%=mod;
      x+=f(a+t-1,a-1)*y%mod*l[b+c-t]%mod;
    }
    x%=mod;
    //printf("%lld %lld\n",x,y);
  }
  printf("%lld",x);
}
//0
//13




Measured memory_bytes: 24832
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <climits>
#include <cfloat>
#include <string>
#include <unordered_map>
using namespace std;



int main(){
	int n, m;
	cin >> n >> m;
	int p = max(n*(n-1)/2,0), q = max(m*(m-1)/2,0);
	int ans = p + q;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
  char str[3];
  int a=0,b=0,i;
  scanf("%s",str);
  for(i=0;i<3;i++){
    if(str[i]=='A') a++;
    else b++;
  }
  if(a==0 || b==0)
    printf("No");
  else
    printf("Yes");
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL<<60;
int main(){
    int N,M;
    long long K;
    cin >> N >> M >> K;
    vector<long long> A(N),B(M),SA(N+1,0),SB(M+1,0);
    for(int i = 0; i < N; i++) cin >> A[i], SA[i+1] = SA[i] + A[i];
    for(int i = 0; i < M; i++) cin >> B[i], SB[i+1] = SB[i] + B[i];
    SB.push_back(INF);
    
    int res = 0;
    for(int i = 0; i <= N; i++){
        long long rem = K - SA[i];
        if(rem < 0) continue;
        int id = upper_bound(SB.begin(),SB.end(),rem) - SB.begin();
        res = max(res, i + id - 1);
    }
    cout << res << endl;
    
}


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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n,l; cin>>n>>l;
	int sum=0,mn=0,dif=1e9;
	for(int i=1;i<=n;++i){
		sum+=l+i-1;
		if(dif>abs(l+i-1)){
			mn=l+i-1;
			dif=abs(mn);
		}
	}
	cout<<sum-mn<<"\n"s;
}


Measured memory_bytes: 3564
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0;i<n;i++)
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int MAX = 1000005;

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

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

long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
    int x, y, a, b;
    cin >> x >> y;
    if ((x + y ) % 3 == 0){
        a = (2 * y - x) / 3;
        b = (2 * x - y) / 3;
        COMinit();
        cout << COM(a+b,a) << endl;
    }
    else cout << 0 << endl;
}

Measured memory_bytes: 23680
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define Yes(f) cout<<(f?"Yes":"No")<<endl
#define yes(f) cout<<(f?"yes":"no")<<endl
#define YES(f) cout<<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())
#define VI(a,n) vi a(n); rep(i,n)cin>>a[i];

using namespace std;

const int mod=1e9+7;

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

void run(){
    int n,m,k;
    while(cin>>n>>k>>m,n){
        vi v;
        REP(i,1,n)v.pb(i);
        int a=m-1;
        while(v.size()!=1){
            v.erase(v.begin()+a);
            a=(a+k-1)%v.size();
        }
        cout<<v[0]<<endl;
    }
}


Measured memory_bytes: 3228
n, m, k = map(int, input().split())
par = [i for i in range(n)]
rank = [1] * n
fr = [[] for i in range(n)]
br = [[] for i in range(n)]

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])  # 経路圧縮
        return par[x]

def same(x, y):
    return find(x) == find(y)

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    if rank[x] < rank[y]:
        rank[y] += rank[x]
        par[x] = y
    else:
        rank[x] += rank[y]
        par[y] = x

for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    unite(a, b)
    fr[a].append(b)
    fr[b].append(a)

for i in range(k):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    br[a].append(b)
    br[b].append(a)

res = []
for i in range(n):
    cnt = 0
    if br[i]:
        for b in br[i]:
            if same(i, find(b)):
                cnt += 1
        res.append(rank[find(i)] - len(fr[i]) - cnt - 1)
    else:
        res.append(rank[find(i)] - len(fr[i]) - 1)
print(*res, sep=" ")

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};

// Problem Specific Parameter:

vector<int> graph[200010];

int main(void){
	int n,m;
	cin >> n >> m;
	rep(i,m){
		int a,b;
		cin >> a >> b;
		graph[a-1].push_back(b-1);
		graph[b-1].push_back(a-1);
	}

	bool ok = false;

	rep(i,1,n-1){
		bool from = false, to = false;
		for(auto &v2:graph[i]){
			if(v2==0) from = true;
			if(v2==n-1) to = true;
		}
		if(from  and to) ok = true;
	}

	if(ok)
		puts("POSSIBLE");
	else
		puts("IMPOSSIBLE");

	return 0;
}

Measured memory_bytes: 12016
#include <iostream>
using namespace std;
int main(void){
    int n,m=0;
    string a,b,c;
    cin>>n>>a>>b>>c;
    for(int i=0;i<n;i++){
        if(a[i]==b[i]){
            if(a[i]!=c[i]){
                m++;
            }
        }else if(a[i]==c[i]){
            m++;
        }else if(b[i]==c[i]){
            m++;
        }else{
            m+=2;
        }
    }
    cout<<m<<endl;
}

Measured memory_bytes: 256
def calc(N, A, i):
    x = 0
    r = 0
    for j, a in enumerate(A):
        if j == i:
            continue
        r += abs(x - a)
        x = a
    r += abs(x)
    return r

def calc0(N, A):
    x = 0
    r = 0
    for a in A:
        r += abs(x - a)
        x = a
    return r

def calc1(N, A, ra, i):
    x0 = A[i - 1]
    x1 = A[i]
    x2 = A[i + 1]
    return ra - abs(x0 - x1) - abs(x1 - x2) + abs(x0 - x2)

#N = 1000
#A = list(range(N))

N = int(input())
A = [int(_) for _ in input().split()]
A += [0]

ra = calc0(N, A)

for i in range(N):
    print(calc1(N, A, ra, i))


Measured memory_bytes: 14164
using System;

public class Test
{
	static public void Main( )
	{
		String[] line = Console.ReadLine().Split( ' ' );
		var W = int.Parse( line[0] );
		var H = int.Parse( line[1] );
		var x = int.Parse( line[2] );
		var y = int.Parse( line[3] );
		var r = int.Parse( line[4] );
		if( 0 <= x-r && x+r <= W && 0 <= y-r && y+r <= H ) {
			Console.WriteLine( "Yes" );			
		} else {
			Console.WriteLine( "No" );
		}
	}
}

Measured memory_bytes: 19576
X=int(input())
if X>=2000:
  print(1)
else:
  tmp=X%100
  co=X//100
  fo_tmp=6
  for i in range(1,6):
    if i*co>=tmp:
      fo_tmp=i
      break
  if fo_tmp==6:
    print(0)
  else:
    print(1)

Measured memory_bytes: 3060
import itertools
n = int(input())
s = str(input())
r = {}
b = {}
g = {}
for i in range(len(s)):
    if s[i] == 'R':
        r[i+1] = s[i]
    elif s[i] == 'B':
        b[i+1] = s[i]
    else:
        g[i+1] = s[i]
ans = len(r) * len(b) * len(g)
for i in r.keys():
    for j in b.keys():
        diff = abs(j-i)
        minb = min(i,j)-diff
        maxb = max(i,j)+diff
        if maxb in g.keys():
            ans -= 1
        if minb in g.keys():
            ans -= 1
        if((i+j)%2==0):
            if((i+j)//2 in g.keys()):
                ans -=1
print(ans)

Measured memory_bytes: 9236
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <string>
#include <utility>
#include <map>
#include <deque>
using namespace std;
#define rep(i,n) for(int i=1;i<=(int)(n);i++)
#define Rep(i,n) for(int i=0;i<=(int)(n-1);i++)
typedef long long ll;
typedef map<int,int> mint;
typedef pair<int,int> pint;
typedef pair<ll,ll> pll;
typedef deque<char> dchar;
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};
int inf=1e9+1000;
ll infi=1e18+100;

//x=10111;
//x<<2 = 1011100 (右シフト),x>>2 = 101 (左シフト)
//(x>>2)&1 = 101 & 001 = 1
//iビット目は、(x>>i) & 1 でわかる(x>>i)%2 でもよい


ll N;

int keta(ll n){
	int c=0;
	while(n>0){
		n=n/10;
		c++;
	}
	return c;
}




int main(){
	cin>>N;
	ll A=1;
	ll rem=1;
	while(A*A<=N){
		if(N%A==0){
			rem=A;
		}
		A++;
	}
	
	ll B=N/rem;
	cout<<keta(B)<<endl;

	  return 0;
  }


Measured memory_bytes: 256
N , D = map(int,input().split())
X = []
ans = 0

for i in range(N):

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

    X.append(x)

for i in range(N):

    for j in range(i):

        summ = 0

        for k in range(D):

            summ += (X[i][k] - X[j][k]) ** 2

        now = 0
        while now ** 2 <= summ:

            if now ** 2 == summ:
                ans += 1

            now += 1

print (ans)

            


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

int main(void) {
	long int count = 0;
	int num = 0;
	int time = 0;
	int start = 0, end = 0;
	cin >> num >> start >> end;
	for (int i = 0; i < num; i++) {
		cin >> time;
		if (time < start || time >= end)count++;
	}
	cout << count << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static void Main()
    {
        var N = int.Parse(Console.ReadLine());
        var A = Console.ReadLine().Split(' ').Select(int.Parse).OrderBy(v => v).ToList();
        var opes = new List<Tuple<int, int>>();

        var min = A.First();
        var max = A.Last();
        var plus = A.Skip(1).Take(N - 2).Where(v => v >= 0).ToList();
        var minus = A.Skip(1).Take(N - 2).Where(v => v < 0).ToList();

        foreach (var a in plus)
        {
            opes.Add(Tuple.Create(min, a));
            min -= a;
        }
        foreach (var a in minus)
        {
            opes.Add(Tuple.Create(max, a));
            max -= a;
        }

        opes.Add(Tuple.Create(max, min));
        var result = max - min;

        Console.WriteLine(result);
        Console.WriteLine(string.Join(Environment.NewLine, opes.Select(t => $"{t.Item1} {t.Item2}")));
    }
}

Measured memory_bytes: 35644
using System;

namespace ITP1_3_A
{
    class Program
    {
        static void Main(string[] args)
        {
            int a, i = 0;
            while ((a = int.Parse(Console.ReadLine())) != 0)
            {
                Console.WriteLine("Case {0}: {1}", ++i, a);
            }
        }
    }
}

Measured memory_bytes: 9252
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 200100;
long long ans = 0;
char s[maxn];
int main()
{
	std::ios::sync_with_stdio(false);
	cin >> (s + 1);
	int n = strlen(s + 1);
	int now = 0;
	for(int i = 1; i <= n - 1; i ++)
	{
		if(s[i] == 'A')
		{
			now ++;
			continue;
		}
		if(s[i] == 'B' && s[i + 1] == 'C')
		{
			ans += now;
			i = i + 1;
			continue;
		}
		now = 0;
		//cout << i << " " << now << " " << ans << endl;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
struct edge{long long to,cost;};
const int inf = 1 << 27;
const long long INF = 1LL << 60;
const int COMBMAX = 1001001;
const long long MOD = 1000000007;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define eachdo(v, e) for(const auto& e : (v))
#define all(v) (v).begin(), (v).end()
#define lower_index(v, e) (long long)distance((v).begin(), lower_bound((v).begin(), (v).end(), e))
#define upper_index(v, e) (long long)distance((v).begin(), upper_bound((v).begin(), (v).end(), e))
long long mpow(long long a, long long n, long long mod = MOD){long long res = 1; while(n > 0){if(n & 1)res = res * a % mod; a = a * a % mod; n >>= 1;} return res;}
void yn(bool j){cout << (j ? "Yes" : "No") << endl; return;}
template<class Head> void pt(Head&& head){cout << head << endl; return;}
template<class Head, class... Tail> void pt(Head&& head, Tail&&... tail){cout << head << " "; pt(forward<Tail>(tail)...);}
template<class T> void debug(T v){rep(i, v.size()) cout << v[i] << " " ; cout << endl;}
template<class T> void debug2(T v){rep(i, v.size()){rep(j, v[i].size()) cout << v[i][j] << " " ; cout << endl;}}
template<class T1, class T2> long long bcount(T1 v, T2 a){return upper_index(v, a) - lower_index(v, a);} 
template<class T1, class T2> inline bool chmin(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}
template<class T1, class T2> inline bool chmax(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}
template<class T1, class T2> void sortTwoVecter(vector<T1> &f, vector<T2> &s, bool isReverse = false){
    vector<pair<T1, T2>> p;
    rep(i, f.size()) p.emplace_back(make_pair(f[i], s[i]));
    if (!isReverse) sort(p.begin(), p.end());
    else sort(p.rbegin(), p.rend());
    rep(i, f.size()) tie(f[i], s[i]) = p[i];
    return;
}

int main(){
    ll N, Q; cin >> N >> Q;
    string S; cin >> S;
    vector<ll> cum(N, 0);
    rep(i, N - 1){
        cum[i + 1] = cum[i];
        if (S[i] == 'A' && S[i + 1] == 'C') cum[i + 1]++;
    }
    rep(i, Q){
        ll l, r; cin >> l >> r;
        pt(cum[r - 1] - cum[l - 1]);
    }
    
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;

typedef pair<int,int> pii;
const int N = 105;

int n, m, a[N][N], b[N][N], c[N][N];
int mat[N], lim, cv, vis[N];

vector<pii> adj[N];

bool match (int I) {
	if(!I) return true;
	if(vis[I] == cv) return false;
	vis[I] = cv;
	for(int i=0;i<=lim;i++) {
		int A, B;
		tie(A, B) = adj[I][i];
		if(match(mat[A])) {
			mat[A] = I;
			return true;
		}
	}
	return false;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			scanf("%d",&a[i][j]);
			adj[i].push_back({(a[i][j]-1)/m+1, a[i][j]});
		}
	}
	for(int k=1;k<=m;k++) {
		for(int i=1;i<=n;i++) {
			mat[i] = 0;
		}
		lim = m-k;
		for(int i=1;i<=n;i++) {
			++cv;
			assert(match(i));
		}
		for(int i=1;i<=n;i++) {
			for(int j=0;j<=lim;j++) {
				if(mat[adj[i][j].X] == i) {
					b[i][k] = adj[i][j].Y;
					c[adj[i][j].X][k] = adj[i][j].Y;
					swap(adj[i][j], adj[i][lim]);
					break;
				}
			}
		}
	}
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			printf("%d ", b[i][j]);
		}
		puts("");
	}
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			printf("%d ", c[i][j]);
		}
		puts("");
	}
}


Measured memory_bytes: 512
local PI, sin, cos, sqrt = math.pi, math.sin, math.cos, math.sqrt

local A, B, H, M = io.read("*n", "*n", "*n", "*n")

local A_rad = 2 * PI * ((H + M / 60) / 12)
local B_rad = 2 * PI * (M / 60)

local x_len = A * cos(A_rad) - B * cos(B_rad)
local y_len = A * sin(A_rad) - B * sin(B_rad)

print(sqrt(x_len^2 + y_len^2))

Measured memory_bytes: 3180
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i=0; i<n; i++) cin >> a[i];
    sort(a.begin(), a.end());

    cout << a.back() - a[0] << endl;
}


Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7


def f():
    s = input()
    k = int(input())
    a = [ord(_) - ord('a') for _ in s]
    l = len(s)
    for i in range(l):
        if k < 1:
            break
        c = a[i]
        if c == 0:
            continue
        d = 26 - c
        if k >= d:
            a[i] = 0
            k -= d
    a[-1] = (a[-1] + k) % 26
    return ''.join([chr(_ + ord('a')) for _ in a])

print(f())


Measured memory_bytes: 7464
#include <bits/stdc++.h>
using namespace std;
#define pi 3.1415926536
#define forn(i, a, b) for (int i = a; i < b; i++)
#define LL long long
#define MP make_pair
#define ff first
#define ss second
#define INF 2147483647
#define _INF -2147483647
#define pq priority_queue
#define MM multimap
#define PB push_back
#define ipair pair<int, int> s
#define lpair pair<LL, LL>
#define MAXN 100004

int main() {
    int r;
    cin >> r;
    cout << 3 * r * r << endl;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <map>
#include <iterator>
#include <functional>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <list>
#include <sstream>
#include <cstring>
#include <stdio.h>
#include <complex>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC target("sse4")

typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LD, LD> PDD;
typedef pair<LL, int> PLL;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<char> VCH;
typedef vector<LD> VLD;
typedef vector<string> VS;
typedef vector<VS> VSS;
typedef vector<VI> VVI;
typedef vector<VLL> VVLL;
typedef vector<VCH> VVCH;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;
typedef vector<PDD> VPDD;
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define next fake_next
#define prev fake_prev
#define left fake_left
#define right fake_right

#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 REP(i, t) FOR(i,0,t)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())
#define FILL(a, value) memset(a, value, sizeof(a))

const LD PI = acos(-1.0);
const LD EPS = 1e-4;
const LL INF = 1e7 - 1;
const LL mod = 1000000007;
const LL LINF = 1e18 + 10;
const int MAXN = 100001;
const int MAXK = 101;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//freopen("In.txt", "r", stdin);

	LL n;
	cin >> n;
	VLL a(n);
	FOR(i, 0, n)
		cin >> a[i];

	LL za_raz = n * (n + 1) / 2;
	LL sum = 0;
	FOR(i, 0, n)
		sum += a[i];

	if (sum % za_raz)
	{
		cout << "NO";
		return 0;
	}

	LL x = sum / za_raz;

	a.push_back(a[0]);
	LL ye = 0;
	VLL ans(n);
	FOR(i, 0, n)
	{
		LL t = a[i] + x - a[i + 1];
		if (t < 0)
		{
			cout << "NO";
			return 0;
		}

		if (t % n)
		{
			cout << "NO";
			return 0;
		}

		ye += t / n;
		ans[i] = t / n;
	}

	if (ye != x)
		cout << "NO";
	else
	{
		LL curr = 0;
		FOR(i, 0, n)
			curr += i *1LL* ans[i];

		if (curr != n * x - a[0])
			cout << "NO";
		else
			cout << "YES";
	}

	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ul unsigned long int
#define ld long double
#define f(t) for(ll i =0;i<t;i++)
#define vi vector<int>
#define vl vector<ll>
#define pri pair<int,int>
#define mpi map<int,int>
#define prl pair<ll,ll>
#define mp make_pair
#define mpl map<ll,ll>
#define umpl unordered_map<ll,ll>
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000007
#define inf 2e18
#define EPS 1e-3
#define PI 3.1415926535897932385
#define display(v) f(v.size())cout << v[i]<<" "
const double h = 1e-6;
const int MAX_  = 100005;
#define all(v) v.begin(),v.end()

inline ll mul(ll a, ll b){ return (a * 1ll * b) % MOD; }
inline ll sub(ll a, ll b){ ll c = a - b; if(c < 0) c += MOD; return c; }
inline ll add(ll a, ll b){ ll c = a + b; if(c > MOD) c -= MOD; return c; }
 //////////////////////*********CODE***********/////////////////////
 //////////////////////////////////////////////////////////////////
int gcd(int a, int b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b);  
} 


int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int k;   cin>>k;
  ll ans = 0;
  for(int i =1;i<=k;i++)
  {
    for(int j=1;j<=k;j++)
    {
      for(int x = 1;x<=k;x++)
      {
        ans += gcd(i,gcd(j,x));
      }
    }
  }
  cout << ans ;
  
  return 0;
 }

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

constexpr int N = 1e5 + 5;

int n, m, occ_next[N][256];
string s, t;

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

  cin >> s >> t;
  n = s.size();
  m = t.size();
  memset(occ_next, -1, sizeof(occ_next));

  // Preprocess t for next occurence of a character at any index
  for (int i = n - 1; i >= 0; i--) {
    occ_next[i][s[i]] = i;
    for (char c = 'a'; c <= 'z'; c++) {
      if (c != s[i]) {
        occ_next[i][c] = occ_next[i + 1][c];
      }
    }
  }

  // Calculate index
  ll ans = 0, cidx = 0;
  for (char c : t) {
    if (occ_next[cidx][c] == -1) {
      cidx = 0;
      ans += n;
    }

    // We can't find it
    if (occ_next[cidx][c] == -1) {
      cout << -1 << "\n";
      return 0;
    }
    cidx = occ_next[cidx][c] + 1;
  }
  ans += cidx;
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 100560
#include<bits/stdc++.h>
#define ll long long int
#define endl "\n"
#define mod 1000000007
#define pb push_back
#define mp make_pair
using namespace std;

void solve(){
	string s,t;
	cin>>s>>t;
	int cnt= 0;
	for (int i = 0; i < s.size(); ++i)
	{
		if (s[i]!=t[i])
		{
			cnt++;
		}
	}
	cout<<cnt<<endl;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	ll t=1;
	//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

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

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


Measured memory_bytes: 256