akhauriyash/Code-Regression huggingface dataset:
#include <iostream>                                             
#include <cstdlib>                                              
#include <stack>                                                
using namespace std;                                            
                                                                
int main(void) {                                                
  stack<int> S;                                                 
  string s;                                                     
  int x;                                                        
  int y;                                                        
                                                                
  while(cin >> s) {                                             
    if(s == "+") {                                              
      x = S.top();                                              
      S.pop();                                                  
      y = S.top();                                              
      S.pop();                                                  
      S.push(x+y);                                              
    } else if (s == "-") {                                      
      x = S.top();                                              
      S.pop();                                                  
      y = S.top();                                              
      S.pop();                                                  
      S.push(y-x);                                              
    } else if (s == "*") {                                      
      x = S.top();                                              
      S.pop();                                                  
      y = S.top();                                              
      S.pop();                                                  
      S.push(x*y);                                              
    } else {                                                    
      S.push(atoi(s.c_str()));                                  
    }                                                           
  }                                                             
  cout << S.top() << endl;                                      
}                                                               
               

Measured memory_bytes: 3204
#include "bits/stdc++.h"
using namespace std;
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define put(a) cout<<a<<"\n"
#define all(a)  (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define oorret 0
#define oor(x) [&](){try{x;} catch(const out_of_range& oor){return oorret;} return x;}()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){if(a>b){a=b;return 1;}return 0;}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){if(a<b){a=b;return 1;}return 0;}

int main(){
    string s;
    cin >> s;
    vector<string>t;
    t.push_back("KIHBR");
    t.push_back("AKIHBR");
    t.push_back("KIHABR");
    t.push_back("AKIHABR");
    t.push_back("KIHBAR");
    t.push_back("AKIHBAR");
    t.push_back("KIHABAR");
    t.push_back("AKIHABAR");
    t.push_back("KIHBRA");
    t.push_back("AKIHBRA");
    t.push_back("KIHABRA");
    t.push_back("AKIHABRA");
    t.push_back("KIHBARA");
    t.push_back("AKIHBARA");
    t.push_back("KIHABARA");
    t.push_back("AKIHABARA");
    bool flag = false;
    REP(i,16){
        if(s==t[i])flag = true;
    }
    if(flag){
        put("YES");
    }else{
        put("NO");
    }
    
    return 0;
}


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

Measured memory_bytes: 1688
// http://agc018.contest.atcoder.jp/tasks/agc018_c

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
#include <limits>

typedef long long ll;
typedef std::pair<int,int> ii;

struct set {
    ll sum;
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    set() : sum (0), pq () {}
    void insert(int x) {pq.push(x); sum += x;}
    void clear() {pq = decltype(pq)(); sum = 0;}
    void pop() {sum -= pq.top(); pq.pop();} // the smallest
    bool reduce(std::size_t size) {
        while (pq.size() > size) pop();
        return pq.size() == size;
    }
};

ll add(ll x, ll y) { // handle -inf
    if (x == std::numeric_limits<ll>::min()) return x;
    if (y == std::numeric_limits<ll>::min()) return y;
    return x+y;
}

int main() {
    int x, y, z;
    std::cin >> x >> y >> z;
    const int n = x+y+z; // == x + y + z
    ll result = 0;
    std::vector<ii> points;
    for (int i = 0; i < n; ++i) {
        int a, b, c;
        std::cin >> a >> b >> c;
        a -= c; b -= c; result += c;
        points.emplace_back(a, b);
    }
    std::sort(points.begin(), points.end(), [](ii x, ii y){
        return x.first - x.second > y.first - y.second; // (a-c) - (b-c) = (a-b), will not overflow
    });

    std::vector<ll> maxA (n+1, 0), maxB (n+1, 0); // need to choose (x) first (at first of sequence) + (y) second (at last of sequence)
//    for (ii a : points) std::cout << a.first << ' ' << a.second << '\n';
    // maxA[a] = sum of x largest elements in points [0 ;; a)
    // maxB[b] = sum of y largest elements in points [b ;; n)
    set values;
    if (x != 0) for (int a = 0; a <= n; ++a) {
        if (a != 0) values.insert(points[a-1].first);
        maxA[a] = values.reduce(x) ? values.sum : std::numeric_limits<ll>::min();
    }
    values.clear();
    if (y != 0) for (int b = n; b != -1; --b) {
        if (b != n) values.insert(points[b].second);
        maxB[b] = values.reduce(y) ? values.sum : std::numeric_limits<ll>::min();
    }
    ll r1 = std::numeric_limits<ll>::min();
    for (int s = 0; s <= n; ++s) r1 = std::max(r1, add(maxA[s], maxB[s]));
    std::cout << result + r1 << '\n';
}


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

int main(){

    int n; cin >> n;
    map<int, int> d;
    for(int i = 0; i < n; i++){
        int in; cin >> in;
        d[in]++;
    }

    int m; cin >> m;
    for(int i = 0; i < m; i++){
        int in; cin >> in;
        if(d[in] == 0){
            cout << "NO" << endl;
            return 0;
        }
        d[in]--;
    }
    cout << "YES" << endl;
    return 0;
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
 
using namespace std;
 
//const int MOD=1e9+7;
 
const int MOD=998244353;


 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    
    int n;
    cin>>n;
    
    vector<pair<int,int>> vp(n);
    for(auto &p:vp){
        int x,y;
        cin>>x>>y;
        p={x-y,x+y};
    }
    sort(vp.begin(),vp.end(), [](auto p1, auto p2){return p1.second<p2.second;});
    int ans=0;
    int r=-1e9;
    for(int i=0; i<n; i++){
        if(vp[i].first>=r){
            ans++;
            r=vp[i].second;
        }
    }
    cout<<ans;
    
    
    
    return 0;
}

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

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

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    ll N;
    cin >> N;
    cout << N / 2 - !(N % 2) << endl;
    return 0;
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int h[n],cost[n],i;
  for(i=0;i<n;i++)
    cin>>h[i];
  cost[0]=0;
  cost[1]= abs(h[1] - h[0]);
  if(n>2)
  {
  cost[2] = min(abs( h[2]-h[0]), cost[1] + abs(h[2] - h[1]));
  
  for(i=3;i<n;i++)
  {
    cost[i] = min(cost[i-1] + abs(h[i]-h[i-1]) , cost[i-2] + abs(h[i]-h[i-2]));
  }
  }
  cout<<cost[n-1];
}

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

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

  int N;
  cin >> N;
  int A[N];
  int ans = 0;
  int ans2 = 0;
  rep(i, N){
    cin >> A[i];
    if(A[i] % 4 == 0) ans++;
    else if(A[i] % 2 == 0) ans2++;
  }
  if(ans + ans2/2 >= N/2) cout << "Yes" << endl;
  else cout << "No" << endl; 
}

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

int main() 
{
    double x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    
   printf("%.8f\n",sqrt(((x1-x2)*(x1-x2))+((y1-y2)*(y1-y2))));
    
return 0;
} 




Measured memory_bytes: 3288
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include <string.h>
using ll = long long;
 
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define reps(i,x) for(ll i=1;i<=(ll)(x);i++)
#define rrep(i,x) for(ll i=((ll)(x)-1);i>=0;i--)
#define rreps(i,x) for(ll i=(ll)(x);i>0;i--)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define vll vector<ll>
#define vi vector<int>
#define vpll vector<pair<ll,ll>>
#define vpi vector<pair<int,int>>
#define mod 1000000007 
using namespace std;
ll a[100001];
ll b[100001];
map<ll,ll> mp;
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)){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
/*
“You just can’t beat the person who won’t give up.” ―Babe Ruth
*/

#include <bits/stdc++.h>

using namespace std; 	
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e5+10;
const int oo = 1e9;
const int mod = 1e9+7;

int main(){
	int n,a,b;
	cin>>n>>a>>b;
	if(abs(a-b)%2){
		puts("Borys");
	}else{
		puts("Alice");
	}
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;

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

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    double W,H,x,y;
    cin>>W>>H>>x>>y;
    cout<<H*W/2.0<<" "<<(x+x==W&&y+y==H)<<endl;
}



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

int n;
int a[100];
int ans;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)cin >> a[i];
	sort(a, a + n);
	reverse(a, a + n);
	for (int i = 0; i < n; i++) {
		if (i % 2 == 0)ans += a[i];
		else ans -= a[i];
	}
	cout << ans << endl;
	return 0;
}

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

class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        int[] numbers = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
        int count = 0;
        bool cond = true;
        while (cond)
        {
            for (int i = 0; i < n; i++)
            {
                if (numbers[i] % 2 == 1)
                {
                    cond = false;
                    break;
                }
                else
                {
                    numbers[i] /= 2;
                }
            }
            if (cond)
            {
                count++;
            }
        }
        Console.WriteLine(count);
    }
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
#define rep(i,n,m) for(int i=n;i<(int)(m);i++)
#define rrep(i,n,m) for(int i=((int)(n)-1);i>=m;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
using namespace std;
int dist(char c){
    if(c=='a') return 0;
    else return (int)'z'-c+1;
}
int main(){
    string s;
    cin>>s;
    int n=sz(s);
    int k;
    cin>>k;
    rep(i,0,n-1){
        if(k>=dist(s[i])){
            k-=dist(s[i]);
            s[i]='a';
        }
    }
    
    k%=26;
    rep(i,0,k){
        if(s[n-1]=='z') s[n-1]='a';
        else s[n-1]++;
    }
    
    cout<<s<<endl;
    
}


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

int main () {
    int n, k; cin >> n >> k;
    vector<long long> x(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }
    
    long long ans = INT_MAX;
    for (int i = 0; i+k-1 < n; i++) {
        ans = min(ans, abs(x[i]) + abs(x[i] - x[i+k-1]));
        ans = min(ans, abs(x[i+k-1]) + abs(x[i] - x[i+k-1]));
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
use std::io::Read;

fn input() -> (i64,f64) {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    
    let a:i64 = iter.next().unwrap().parse().unwrap();
    let b:f64 = iter.next().unwrap().parse().unwrap();
    (a,b)
}

fn main() {
    let (a,b) = input();
    let b = (b*100.0+0.001) as i64;
    let res = a*b/100;
    println!("{}",res);
}



Measured memory_bytes: 2176
#include <bits/stdc++.h>
#define lli long long int

using namespace std;

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

Measured memory_bytes: 3708
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define eb emplace_back
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll MOD = 1e9 + 7;
template <class T>
void chmin(T &a, T b) { a = min(a, b); }
template <class T>
void chmax(T &a, T b) { a = max(a, b); }
void ok() { cerr << "ok" << endl; }
int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<ll> co(n), a(n);
    ll res = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        --a[i];
        co[a[i]]++;
    }
    for (int i = 0; i < n; i++) {
        res += co[i] * (co[i] - 1LL) / 2LL;
    }
    for (int i = 0; i < n; i++) {
        res -= co[a[i]] * (co[a[i]] - 1LL) / 2LL;
        co[a[i]]--;
        res += co[a[i]] * (co[a[i]] - 1LL) / 2LL;
        cout << res << '\n';
        res -= co[a[i]] * (co[a[i]] - 1LL) / 2LL;
        co[a[i]]++;
        res += co[a[i]] * (co[a[i]] - 1LL) / 2LL;
    }
}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fi first
#define se second
#define mod 1000000007
#define pi acos(-1.0)
#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int main()
{
   FastIO;
   ll n;
   string s;
   cin>>n;
   cin>>s;
   ll r=0,g=0,b=0,cnt=0,ans=0;
   for(int i=0;i<n;i++)
   {
       if(s[i]=='R') r++;
       if(s[i]=='G') g++;
       if(s[i]=='B') b++;
   }
   ans = r*g*b;
   for(int i=1;i<=n;i++)
   {
       for(int j=0;j<n;j++)
       {
           if(j-i<0 || j+i>=n) continue;
           if(s[j]!=s[j-i] && s[j]!=s[j+i] && s[j-i]!=s[j+i])
            ans--;
       }

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


Measured memory_bytes: 3656
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    n = i_input()

    ans = ''
    al=[chr(ord('a') + i) for i in range(26)]

    while n > 0:
        n -= 1
        ans += al[n%26]
        n //= 26

    print(ans[::-1])
 
if __name__ == '__main__':
    main()


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


int main() {
    int a,b,c;
    cin >> a >> b >> c;
    cout << min(a,min(b,c));
    cout << " ";
    cout << (a + b + c) - min(a,min(b,c)) - max(a,max(b,c));
    cout << " ";
    cout << max(a,max(b,c)) << endl;
}


Measured memory_bytes: 3092
import numpy as np

def main():
    N = int(input())
    x = []
    for i in range(N):
        x.append(list(map(int, input().split())))
    X = np.array(x)
    j = 0
    for i in range(N-1):
        for k in range(i+1, N):
            j += np.linalg.norm(X[i] - X[k], ord=2)

    print(2*j/N) # 2(N-1)!/N!

if __name__ == "__main__":
    main()
    

Measured memory_bytes: 20628
n = int(input())
if n == 0:
    print(0)
    exit()
    
ans = ''
while abs(n) > 0:
    if n % 2 == 0:
        n //= (-2)
        ans += '0'
    else:
        n -= 1
        n //= (-2)
        ans += '1'

print(ans[::-1])

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define debug(a) cout << #a << ": " << a << endl
#define sz(a) int(a.size())
#define rep(i,n) for(int i=0;i<n;i++)
#define forr(i, st, en) for(int i = st; i < en; i++)
#define all(v) (v).begin(),(v).end()
#define fast cin.tie(0); ios::sync_with_stdio(false)
#define int long long
int32_t main(){ fast;
	int x; cin>>x;
	int t = x / 500;
	x %= 500;
	int ans = t * 1000;
	t = x / 5;
	ans += t * 5;
	cout<<ans<<endl;;
	
}


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

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
template<typename T> void view(T cont) {std::cout << cont << std::endl;}
template<typename T> void view(T* cont, ll sz) {rep(i, sz) std::cout << cont[i] << " "; std::cout << std::endl;}
template<typename T> void view(const std::vector<T>& v) {for (const auto& f: v) std::cout << f << " "; std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv) { for (const auto& v: vv) {view(v);}}
const long long INF = 1LL<<60;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

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

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

using namespace std;

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

const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1000000000000000000L;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const int ddx[] = {1, 1, 0, -1, -1, -1, 0, 1};
const int ddy[] = {0, 1, 1, 1, 0, -1, -1, -1};

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

int extgcd(int a, int b, int& x, int&y) {
    int d = a;
    if(b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }else {
        x = 1;
        y = 0;
    }
    return d;
}

int inv(int a) {
    int x, y;
    extgcd(a, MOD, x, y);
    return (x + MOD) % MOD;
}

int main() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    s += 'N';
    int score = 0;
    int before = 'M';
    int tmp = 0;
    int rchange = 0;
    int lchange = 0;
    rep(i, n + 1) {
        if(before != s[i] && s[i] == 'L') lchange++;
        if(before != s[i] && s[i] == 'R') rchange++;
        if(before != s[i]) {
            score += tmp;
            tmp = 0;
            before = s[i];
        }else tmp++;
    }
    int lc;
    int l = 0;
    int r = 0;
    if(s[0] == 'L') l++;
    else r++;
    if(s[n - 1] == 'L') l++;
    else r++;
    if(lchange - l >= k) lc = 2 * k;
    else if(lchange >= k) lc = 2 * (lchange - l) + (k - lchange + l);
    else lc = 2 * (lchange - l) + l;
    int rc;
    if(rchange - r >= k) rc = 2 * k;
    else if(rchange >= k) rc = 2 * (rchange - r) + (k - rchange + r);
    else rc = 2 * (rchange - r) + r;

    cout << score + max(lc, rc) << endl;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <utility>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <cstdio>
#include <map>
#include <list>
#include <stdio.h>
#include <sstream>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
#define all(x) (x).begin(), (x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
//ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
//ll lcm(ll x, ll y) {return x / gcd(x, y) * y;}
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
const ll mod = 1e9 + 7;
const ll inf = 1LL << 60;
const long double pi = 3.14159265358979323846;

// ****************************************CODE***************************************//

ll n, m;
vector<vector<int> > g;

ll dp[100100];
ll rec(int v) {
    if(dp[v] != -1) return dp[v];

    ll res = 0;
    for(auto i : g[v]){
        res = max(res, rec(i) + 1);
    }
    return dp[v] = res;
}

int main() {
    cin >> n >> m;
    g.assign(n, vector<int>());
    for(int i = 0; i < m; i++){
        int x, y;  cin >> x >> y; --x; --y;
        g[x].push_back(y);
    }

    for(int i = 0; i < n; i++) dp[i] = -1;

    ll res = 0;
    for(int i = 0; i < n; i++) res = max(res, rec(i));
    cout << res << endl;
}

Measured memory_bytes: 8576
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

bool ch[1000010],ch2[1000010];
ll b[1000010];
int main() {
	ll n,a[200010];
	cin>>n;
	for(ll i=0;i<n;i++){
		cin>>a[i];
		b[a[i]]++;
	}
	for(ll i=0;i<n;i++){
		ll now=a[i];
		if(ch2[now]){
			continue;
		}
		ch2[now]=true;
		ll cnt=2;
		while(a[i]*cnt<=1000000){
			now=cnt*a[i];
			ch[now]=true;			
			cnt++;
		}
	}
	ll ans=0;
	for(ll i=0;i<n;i++){
		ll now=a[i];
		if(ch[now]==false){
			ans++;
					if(b[now]>=2){
			ans--;
		}
	//		cout << now<<endl;
		}

	}
	cout <<ans;
	// your code goes here
	return 0;
}

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

using ll = long long;
#define rep(i, n) for (long long i = 0; i < (n); ++i)
#define repr(i, a, b) for (auto i = (a); i < (b); ++i)
#define itr(x, c) for (auto&& x : (c))
#define updatemax(t, v) ((t) = std::max((t), (v)))
#define updatemin(t, v) ((t) = std::min((t), (v)))
#define endl _endl
const char _endl = (cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout.precision(16), '\n');

int main() {
  ll n;
  cin >> n;
  using C = complex<double>;
  vector<C> p(n);
  rep(i, n) {
    double x, y;
    cin >> x >> y;
    p[i].real(x);
    p[i].imag(y);
  }
  double ans = 1e+100;
  auto S = [&](const C& c) {
    double low = 0, high = 1e+6;
    while (high - low > 1e-8) {
      auto middle = (high + low) / 2;
      bool safe = true;
      rep(i, n) {
        if (abs(c - p[i]) > middle) {
          safe = false;
          break;
        }
      }
      (safe ? high : low) = middle;
    }
    return low;
  };
  auto dot = [](const C& a, const C& b) {
    return a.real() * b.real() + a.imag() * b.imag();
  };
  rep(i, n) {
    updatemin(ans, S(p[i]));
    repr(j, i + 1, n) {
      updatemin(ans, S((p[i] + p[j]) / C(2)));
      repr(k, j + 1, n) {
        double a = abs(p[j] - p[k]);
        double b = abs(p[k] - p[i]);
        double c = abs(p[i] - p[j]);
        C A(a * a * (b * b + c * c - a * a));
        C B(b * b * (c * c + a * a - b * b));
        C C(c * c * (a * a + b * b - c * c));
        if (abs(A + B + C) > 1e-10) {
          auto x = (A * p[i] + B * p[j] + C * p[k]) / (A + B + C);
          updatemin(ans, S(x));
        }
      }
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3840
import math
n,d = map(int, input().split())
x = [list(map(float, input().split())) for _ in range(n)]
ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        calc = 0
        for k in range(d):
            calc+=(x[i][k]-x[j][k])**2
        if math.sqrt(calc).is_integer():
            ans+=1
print(ans)
    

Measured memory_bytes: 3060
#include<stdio.h>
 
int main(int argc, char* argv[])
{
  char c;
  while((c = getchar()) != '\n'){
    if(('a' <= c && c <= 'z')||('A' <= c && c <= 'Z')){
      if('a' <= c && c <= 'z'){
        putchar('A' + (c - 'a'));
      }else{
        putchar('a' + (c - 'A'));
      }
    }else{
       putchar(c);
    }
  }
  putchar('\n');
  return(0);
}

Measured memory_bytes: 524
#include<stdio.h>
int main(void)
{
  while(1){
  int a,b,ans;
  char op;
  scanf("%d %c %d",&a,&op,&b);
  if (op =='?')
    break;
  else if(op =='+')
    ans=a+b;
  else if (op =='/')
    ans = a/b;
  else if (op =='*')
    ans = a*b;
  else
    ans = a-b;
  
  printf("%d\n",ans);
  }
  return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <string>

using namespace std;

int memo[27];

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

for (int i = 0; i < s.size(); i++) {
memo[s[i] - 'a']++;
}

for (int i = 0; i < 27; i++) {
if (memo[i] % 2) {
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;

return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
#define INF 200000000000
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
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;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(pair<int, int> a, pair<int, int> b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};
int main() {
    while(1){
        ll w,h;
        cin >>w>>h;
        if(w == 0 && h == 0){
            break;
        }
        
        map<tuple<ll, ll,ll ,ll>,bool> m;

        rep(i,h*2-1){
            rep(j,(i%2)?(w):(w-1)){
                bool tmp;
                cin >> tmp;
                if(i%2==0){
                    m[make_tuple(i/2,j,i/2,j+1)] = tmp;
                    m[make_tuple(i/2,j+1,i/2,j)] = tmp;
                }else{
                    m[make_tuple(i/2,j,i/2+1,j)] = tmp;
                    m[make_tuple(i/2+1,j,i/2,j)] = tmp;
                }
            }
        }
        
        vector<vector<ll> > dist(h,vector<ll>(w,-1));
        queue<pair<ll,ll> > que;
        dist[0][0] = 0;
        que.push(make_pair(0,0));
        ll flag=0;
        while(!que.empty()){
            pair<ll,ll> v = que.front();
            que.pop();
            if(v.first == h-1 && v.second == w-1 ){
                cout << dist[v.first][v.second]+1<<endl;
                flag = 1;
                break;
            }
            rep(dir,4){
                ll ny = v.first + dy[dir];
                ll nx = v.second + dx[dir];
                if(!In_map(ny,nx,h,w)) continue;
                //cout << "p1"<<endl;
                if(m[make_tuple(v.first,v.second,ny,nx)]) continue;
                //cout << "p2"<<endl;
                if(dist[ny][nx] != -1) continue;
                //cout << "p3"<<endl;
                dist[ny][nx] = dist[v.first][v.second] + 1;
                que.push(make_pair(ny,nx));
            }
        }
        if(flag == 0)
            cout << 0 << endl;
    }



    return 0;
    

}


Measured memory_bytes: 3324
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxx = 2e5 + 7;
int n;
map <int, int> pos;
map <int, bool> vis;
int seq[maxx];
LL k;

int main() {
	scanf("%d %lld", &n , &k);
	for(int i = 1; i <= n; i++) scanf("%d", &pos[i]);
	int nxt = 1;
	int t = -1;
	seq[++t] = nxt;
	int i = 1;
	while(!vis[i]) {
		vis[nxt] = 1; //先打标记
		nxt = pos[i]; //更新nxt
		seq[++t] = nxt;
		i = nxt; //替换
	}
	//seq[t]是第一次重复的数字
	//定位第一次出现时的位置fir
	int x = 0;
	for(int j = 0; j < t; j++) {
		if(seq[j] == seq[t]) {
			x = j;
			break;
		}
	}
	//cout << x << endl;
	if(k <= x) printf("%d\n", seq[k]);
	else { 
		k -= (LL)x;
		LL id = k % ((LL)t - (LL)x);
		printf("%d\n", seq[x + id]);
	}
	return 0;
}

Measured memory_bytes: 23272
class UnionFind():
  def __init__(self, n):
    self.par = [i for i in range(n+1)]
    self.rank = [0] * (n+1)
    
  def find(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]

  def unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if self.rank[x] < self.rank[y]:
      self.par[x] = y
    else:
      self.par[y] = x
      
    if self.rank[x] == self.rank[y]:
      self.rank[x] += 1

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

N,M=map(int,input().split())
city=UnionFind(N)

for i in range(M):
  A,B=map(int,input().split())
  city.unite(A,B)

ck=[0]*(N+10)
for i in range(1,N+1):
  root=city.find(i)
  if ck[root]==0:
    ck[root]=1
    
#print(city.par)
#print(ck)
    
Ans=sum(ck)-1
print(Ans)


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

int main()
{
  int H,W;
  cin >> H >> W;
  vector<string> S(H);
  for(int i=0; i<H ; i++)
  {
    cin >> S.at(i);
  }
  
  const vector<int> dx = {0,0,1,-1};
  const vector<int> dy = {1,-1,0,0};
  int flag = 0;
  
  for(int i=0; i<H; i++)
  {
    for(int j=0; j<W; j++)
    {
      if(S.at(i).at(j) == '#')
      {
        flag = 1;
        for(int k=0; k<4; k++)
        {
          int ni = i + dx.at(k);
          int nj = j + dy.at(k);
          
          if(ni<0 || ni>=H) continue;
          if(nj<0 || nj>=W) continue;
          if(S.at(ni).at(nj) == '#') 
          {
            flag = 0;
          }
        }
      }
      if(flag == 1) break;
    }
    if(flag == 1) break;
  }
  if(flag == 1) cout << "No" << endl;
  else cout << "Yes" << endl;
  
}
            
        
      
  

Measured memory_bytes: 3612
// ABC 150-B
// 2020.1.11 bal4u

#include <stdio.h>

char S[55];

int main()
{
	int i, N, ans;
	
	scanf("%d%s", &N, S);
	ans = 0;
	for (i = 0; i < N; ++i) {
		if (S[i] != 'A') continue;
		if (S[i+1] != 'B') continue;
		if (S[i+2] != 'C') { ++i; continue; }
		++ans, i += 2;
	}
	printf("%d\n", ans);
	return 0;
}


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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	string s;
	cin >> s;
	if(s.find('9') != string::npos){
		cout << "Yes" << endl;
	}
	else{
		cout << "No" << endl;
	}
}


Measured memory_bytes: 256
#include<iostream>
//#include<string>


using namespace std;

int main(){
  int N,sum=99999;
  cin >>N;
  int a;
 for(int i =0;i<N;i++){
   cin>>a;
   int j=0;
 while(a%2==0){
   a/=2;
   j++;
 }
 if(j<sum)sum =j;
  
 }cout <<sum<<endl;
}
  

Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	ll n;
	cin >> n;
	string ans="";
	while(n>0){
        n--;
        ans+=(char)('a'+(n%26));
        n/=26;
	}
	reverse(ans.begin(), ans.end());
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3648
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

std::string ab("AB");

int msb(int k) {
    int tmp = k, msb{0};
    while (tmp) {
        tmp = tmp >> 1;
        ++msb;
    }
    return msb;
}

int main(int argc, char** argv) {
   int n, k;
   cin >> n >> k;

   int k_msb = msb(k);
   //cout << "k_msb=" << k_msb << endl;

   double ans{0.};

   for (int i=1; i <= n; ++i) {
       int i_msb = msb(i);
       int diff{0};
       if (i_msb <= k_msb) {
        diff = k_msb - i_msb;
        int i_shifted = i << diff;
        if (i_shifted < k) {
               ++diff;
        }
       }

       ans += (double)1. / (std::pow(2., diff) * n);
       //cout << "i=" << i << "  denominar=" << (std::pow(2., diff) * n)<< endl;
   }

   std::cout<< std::fixed << std::setprecision(12) << ans <<endl;
   return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <numeric>
using namespace std;
typedef long long ll;
ll mod=1e9+7;

ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a %mod;
        a=a*a%mod;
        b>>=1;
    }return res;
}

int main(){
    int n,k;cin>>n>>k;
    vector<ll> v(k+1);
    for(int i=1;i<=k;i++)v[i]=k/(i);
    for(int i=1;i<=k;i++)v[i]=power(v[i],n);
    ll ans=0;
    for(int i=k;i>=1;i--){
        ll x=2*i;
        while(x<=k){v[i]-=v[x];x+=i;}
    }
    for(int i=1;i<=k;i++)ans+=i*v[i],ans%=mod;
    cout<<ans;
}

Measured memory_bytes: 3956
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define prtd(var, i) cout << fixed << setprecision(i) << var << endl;
#define ll long long
using namespace std;
#define INF 100000

int main(){
    int n; cin >> n;
    vector<int> a(n);
    rep(i ,n) cin >> a[i];
    int MAX = *max_element(a.begin(), a.end());
    int flag = 0;
    rep(i, n){
        if(a[i] == MAX) flag++;
    }
    int nextMax = 0;
    rep(i, n){
        if(a[i] != MAX && a[i] > nextMax) nextMax = a[i];
    }
    rep(i, n){
        if(a[i] == MAX && flag == 1){
            cout << nextMax << endl;
        }else{
            cout << MAX << endl;
        }
    }
}

Measured memory_bytes: 2432
/**
*   @author: Kshitiz Srivastava (Pirate_ksh) @ MNNIT Allahabad
*/
#include<bits/stdc++.h>
using namespace std;
 
// General
#define ll long long
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007
#define mod_ 998244353 
#define endl "\n"
#define debug(x) cout<<x<<endl
#define REP(i,n) for(i=0;i<n;++i)
#define FOR(i,x,n) for(i=x;i<n;++i)
 
// Bounds
#define lb(a, x) a.lower_bound(x)
#define ub(a, x) a.upper_bound(x)
#define all(a) a.begin(),a.end()
 
// Vector
#define vi vector <int>
#define pb(v, x) v.push_back(x)
#define vsi vector <set <int> >
 
// Map
#define mii map <int, int>
 
// Set
#define si set <int>
 
// Pair
#define vpii vector<pair < int, int > >
#define pii pair < int, int >
#define F first
#define S second

ll t, i, j, k;
string a, b;
int dp[3005][3005];

int DP(int n, int m) {
    if(n == 0 || m == 0) return dp[n][m] = 0;
    if(dp[n][m] != -1) return dp[n][m];
    if(a[n-1] == b[m-1]) return dp[n][m] = DP(n-1, m-1) + 1;
    return dp[n][m] = max(DP(n-1, m),DP(n, m-1));
}

int main(){
    io;
    t=1;
    // cin >> t;
    while(t--) { 
        cin >> a >> b;  
        memset(dp, -1, sizeof(dp));
        DP(a.length(),b.length());
        i=a.length();
        j=b.length();
        string ans = "";
        while(i>0 && j>0) {
            if(a[i-1] == b[j-1]) {
                ans = a[i-1] + ans;
                --i;
                --j;
            }
            else if(dp[i][j-1] > dp[i-1][j]) --j;
            else --i;
        }
        cout << ans << endl;
    }
    return 0;
}


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

using namespace std;

// UnionFind,素集合データ構造,DisjointSet

template<typename weight_type = int>
class union_find {
    static_assert(
        std::is_arithmetic<weight_type>::value,
        "Invalid weight type");
private:
    std::vector<int> uni;
    std::vector<int> edge_count_;
    std::vector<weight_type> weights;
    int size_;
    const void check(const int n) const {
        if (this->group_size() < 0) {
            assert(false);
        }
        if (!(0 <= n && n < this->all_size())) {
            assert(false);
        }
    }
public:
    union_find() : uni(0), edge_count_(0), weights(0), size_(-1) {}
    union_find(const int n)
        : uni(n, -1), edge_count_(n), weights(n), size_(n) {
        this->check(n - 1);
    }
    union_find(const std::vector<weight_type> &_weights)
        : uni(_weights.size(), -1), edge_count_(_weights.size()),
        weights(_weights), size_(_weights.size()) {
        this->check((int)_weights.size() - 1);
    }
    bool same(const int a, const int b) {
        this->check(a);
        this->check(b);
        return this->find(a) == this->find(b);
    }
    int find(const int a) {
        this->check(a);
        return this->uni[a] < 0 ?
                a :
            this->uni[a] = this->find(this->uni[a]);
    }
    bool unite(int a, int b) {
        a = this->find(a);
        b = this->find(b);
        this->edge_count_[a]++;
        if (a == b) {
            return false;
        }
        this->size_--;
        if (this->uni[a] > this->uni[b]) {
            std::swap(a, b);
        }
        this->uni[a] += this->uni[b];
        this->weights[a] += this->weights[b];
        this->edge_count_[a] += this->edge_count_[b];
        this->uni[b] = a;
        return true;
    }
    const int group_size() const {
        return this->size_;
    }
    const int all_size() const {
        return this->uni.size();
    }
    const int size(const int a) {
        this->check(a);
        return -this->uni[this->find(a)];
    }
    const int edge_count(const int a) {
        this->check(a);
        return this->edge_count_[this->find(a)];
    }
    const weight_type weight(const int a) {
        this->check(a);
        return this->weights[this->find(a)];
    }
};

int main(void) {
    int N, M;
    cin >> N >> M;
    vector<int> A(M), B(M);
    for (int i = 0; i < M; i++) {
        cin >> A[i] >> B[i];
        A[i]--;
        B[i]--;
    }
    union_find<> uf(N);
    vector<long long> ans(M);
    ans[M - 1] = 1ll * N * (N - 1) / 2;
    for (int i = M - 1; i >= 0; i--) {
        if (i > 0) {
            int a_root = uf.find(A[i]);
            int b_root = uf.find(B[i]);
            if (a_root == b_root) {
                ans[i - 1] = ans[i];
            } else {
                ans[i - 1] = ans[i] - 1ll * uf.size(a_root) * uf.size(b_root);
            }
        }
        uf.unite(A[i], B[i]);
    }
    for (int i = 0; i < M; i++) {
        cout << ans[i] << endl;
    }
}


Measured memory_bytes: 4096
def find_prime(n):
    e = [0] * (n + 1)
    for tmp in range(2, n + 1):
        i = 2
        while(tmp != 1):
            if tmp % i == 0:
                tmp //= i
                e[i] += 1
            else:
                i += 1

    return(e)


def num(i):
    return len(list(filter(lambda x: x >= i, e)))


n = int(input())

e = find_prime(n)
# print(e)

print(num(74) + num(24) * (num(2) - 1) + num(14) * (num(4) - 1)
      + num(4) * (num(4) - 1) * (num(2) - 2) // 2)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
typedef long long int LL;
typedef unsigned long long int ULL;
using namespace std;

// 插入此處
const int MAXN = 105;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int N, W;
    LL w[MAXN], v[MAXN];
    cin >> N >> W;
    for (int i = 0; i < N; ++i) {
        cin >> w[i] >> v[i];
    }
    vector<vector<LL>> res(4, vector<LL>());
    for (int i = 0; i < N; ++i) {
        res[w[i] - w[0]].push_back(v[i]);
    }
    for (int i = 0; i < 4; ++i) {
        sort(res[i].begin(), res[i].end(), greater<LL>());
        // for (auto x : res[i]) {
        //     cout << x << " ";
        // }
        // cout << endl;
        for (int j = 1; j < res[i].size(); ++j) {
            res[i][j] += res[i][j-1];
        }
        // for (auto x : res[i]) {
        //     cout << x << " ";
        // }
        // cout << endl;
    }
    LL ans = 0;
    for (int i = 0; i <= res[0].size(); ++i) {
        for (int j = 0; j <= res[1].size(); ++j) {
            for (int k = 0; k <= res[2].size(); ++k) {
                for (int l = 0; l <= res[3].size(); ++l) {
                    if (i*w[0] + j*(w[0]+1) + k*(w[0]+2) + l*(w[0]+3) > W) {
                        continue;
                    }
                    LL cur_ans = 0;
                    cur_ans += (i == 0 ? 0 : res[0][i-1]);
                    cur_ans += (j == 0 ? 0 : res[1][j-1]);
                    cur_ans += (k == 0 ? 0 : res[2][k-1]);
                    cur_ans += (l == 0 ? 0 : res[3][l-1]);
                    ans = max(ans, cur_ans);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000010;
const int64_t MOD = 1000000007;
int64_t 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;
  }
}

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

vector<pair<int64_t, int64_t>> prime_factorize(int64_t N)
{
  vector<pair<int64_t, int64_t>> res;
  for (int64_t a = 2; a * a <= N; a++)
  {
    if (N % a != 0)
      continue;
    int64_t ex = 0;
    while (N % a == 0)
    {
      ex++;
      N /= a;
    }
    res.push_back({a, ex});
  }
  if (N != 1)
    res.push_back({N, 1});
  return res;
}

int64_t nHk(int64_t n, int64_t k)
{
  if (k == 1)
  {
    return n;
  }
  return COM(n + k - 1, k);
}

int main()
{
  int64_t N, M, ans = 1;
  cin >> N >> M;
  const auto &res = prime_factorize(M);
  COMinit();
  for (auto p : res)
  {
    (ans *= nHk(N, p.second)) %= MOD;
  }
  cout << ans << endl;
}

Measured memory_bytes: 27036
{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE CPP                   #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE OverloadedStrings     #-}
{-# LANGUAGE RecordWildCards       #-}
{-# LANGUAGE TupleSections         #-}
{-# LANGUAGE TypeFamilies          #-}

import           Control.Applicative
import           Control.Monad
import           Control.Monad.Primitive
import           Control.Monad.ST
import           Control.Monad.State.Strict
import           Data.Bool
import qualified Data.ByteString.Char8       as B
import qualified Data.ByteString.Unsafe      as B
import           Data.Char
import           Data.Function
import qualified Data.IntMap.Strict          as IM
import qualified Data.IntSet                 as IS
import           Data.List
import qualified Data.Map.Strict             as M
import           Data.Monoid
import           Data.Ord
import           Data.Primitive.MutVar
import qualified Data.Set                    as S
import           Data.Tuple
import qualified Data.Vector                 as V
import qualified Data.Vector.Generic         as G
import qualified Data.Vector.Generic.Mutable as GM
import qualified Data.Vector.Unboxed         as U
import qualified Data.Vector.Unboxed.Mutable as UM
import           Debug.Trace
import           Foreign                     hiding (void)
import           Unsafe.Coerce

main :: IO ()
main = interact $ solve . map read . words

solve [a,b]
  | a + b == 15 = "+\n"
  | a * b == 15 = "*\n"
  | 0 < 1 = "x\n"


Measured memory_bytes: 508
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdint>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
// clang-format off
using i64 = int64_t;
using i32 = int32_t;
#define all(x) x.begin(), x.end()
#define int i64
template <class T, typename U> constexpr inline bool exist(const T &s, const U &e) { return s.find(e) != s.end(); }
template <class T> constexpr inline i32 SZ(const T &x) { return x.size(); }
template <class T> constexpr inline bool rmn(T &a, T b) { return a > b ? (a = b, true) : false; }
template <class T> constexpr inline bool rmx(T &a, T b) { return a < b ? (a = b, true) : false; }
const char el = '\n'; const i32 MOD = 1e9 + 7, INF = 0x3f3f3f3f; const i64 INFLL = ((i64)INF << 32) | INF;

#ifdef LOCAL // debugging swiss knife
template <typename Ostream, typename Cont> enable_if_t<is_same<Ostream, ostream>::value, Ostream &> operator<<(Ostream &os, const Cont &v) { os << "{"; for (const auto &x : v) os << x << ", "; return os << "}"; }
template <typename Ostream, typename... Ts> Ostream &operator<<(Ostream &os, const pair<Ts...> &p) { return os << "(" << p.first << ", " << p.second << ")"; }
template <class... Args> void dbg_out(Args... args) { ((std::cerr << "\033[32m" << args << "\033[37m, "), ...); }
#define dbg(...) cerr << "\033[1;31m" << __LINE__ << ": [" << #__VA_ARGS__ << "]\033[37m  = ", dbg_out(__VA_ARGS__), cerr << "\033[0m" << endl;
#else
#define dbg(...) ;
#endif
// clang-format on
////////////////////////////////// TEMPLATE ENDS /////////////////////////////////
vector<vector<i32>> adj;
vector<i32> vis, color;

int32_t main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cout << fixed << setprecision(13), cerr << fixed << setprecision(3);

    int n;
    cin >> n;
    int ans = n * (n + 1) / 2;
    for (i64 i = 1; i < n; ++i) {
        ans += i * (i + 1) / 2;
        int l, r;
        cin >> l >> r;
        if (l > r) swap(l, r);
        ans -= l * (n + 1 - r);
    }
    cout << ans << el;

    return 0;
}

Measured memory_bytes: 3156