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

using namespace std;

#define pb push_back
#define mp make_pair
#define fs first
#define sc second

int n, m;
int a[100005];
vector<pair<int, int>> cb;

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i)
    scanf("%d", a + i);
  for (int i = 0; i < m; ++i) {
    int b, c;
    scanf("%d%d", &b, &c);
    cb.pb(mp(c, b));
  }
  sort(a, a + n);
  sort(cb.begin(), cb.end(), greater<pair<int, int>>());
  int pos = 0, ci = 0;
  while (pos < n) {
    bool check = false;
    for (int i = 0; i < cb[ci].sc && pos < n; ++i) {
      if (a[pos] < cb[ci].fs) {
        a[pos] = cb[ci].fs;
        check = true;
      }
      pos++;
    }
    ci++;
    if (!check)
      break;
  }
  long long res = 0;
  sort(a, a + n);
  for (int i = 0; i < n; ++i) {
    res += a[i];
  }
  cout << res << endl;
  return 0;
}


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

#define I inline
#define fi first
#define se second
#define R register
#define LL long long
#define mp make_pair
#define reg register int
#define pii pair<int,int>
#define fo(i, a, b) for(reg i = a; i <= b; i++)
#define fd(i, a, b) for(reg i = a; i >= b; i--)
#define cr const reg&
using namespace std;
const int N = 1e5 + 1;

I int _max(cr x, cr y) {return x > y ? x : y;}
I int _min(cr x, cr y) {return x < y ? x : y;}
I int read() {
	reg x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
	return x * f;
}
I void ptt(LL x) {if(x >= 10) ptt(x / 10); putchar(x % 10 + '0');}
I void put(LL x) {x < 0 ? putchar('-'), ptt(-x) : ptt(x);}
I void pr1(LL x) {put(x), putchar(' ');}
I void pr2(LL x) {put(x), puts("");}

char s1[N], s2[N];
int tp; pii sta[N * 2];

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

int main() {
	reg n = read(), m = read();
	scanf("%s%s", s1 + 1, s2 + 1);
	reg d = gcd(n, m);
	LL hh = (LL)n / d * m;
	tp = 0;
	reg t1 = m / d;
	fo(i, 1, n) sta[++tp] = pii{(i - 1) * t1 + 1, s1[i]};
	t1 = n / d;
	fo(i, 1, m) sta[++tp] = pii{(i - 1) * t1 + 1, s2[i]};
	sort(sta + 1, sta + tp + 1);
	fo(i, 1, tp) {
		if(sta[i].fi == sta[i - 1].fi && sta[i].se != sta[i - 1].se) {puts("-1"); return 0;
		}
	} printf("%lld\n", hh);
	return 0;
}



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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	string s;
	cin >> s;
	int ans = 0;
	
	for(int i = 0; i < n; ) {
		int j = i;
		while(j < n && s[i] == s[j]) {
			j++;
		}
		
		ans++;
		i = j;
	}
	
	cout << ans << endl;
}


Measured memory_bytes: 512
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
typedef pair<int, int>P;
const int INF = 1e8;

signed main() {
	int N;
	cin >> N;
	string s;
	map<char, int>m;
	rep(i, N) {
		cin >> s;
		if (s[0] == 'M' || s[0] == 'A' || s[0] == 'R' || s[0] == 'C' || s[0] == 'H')m[s[0]]++;
	}
	if (m.size() < 3)cout << 0;
	else if (m.size() == 3) {
		int ans = 1;
		for (auto i : m)ans *= i.second;
		cout << ans;
	}
	else if (m.size() == 4) {
		int a = 1;
		for (auto i : m)a *= i.second;
		int ans = 0;
		for (auto i : m)ans += a / i.second;
		cout << ans;
	}
	else {
		char ch[5] = { 'M','A','R','C','H' };
		int ans = 0;
		for (int i = 0; i < 3; i++) {
			for (int j = i + 1; j < 4; j++) {
				for (int k = j + 1; k < 5; k++) {
					ans += m[ch[i]] * m[ch[j]] * m[ch[k]];
				}
			}
		}
		cout << ans;
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
main(){int n,t,i;while(cin >> n && n){int a[n];int r=0;for(i=0;i<n;i++)cin >> a[i];for(i=n-1;i>0;i--){for(int j=1;j<=i;j++){if(a[j-1]>a[j]){swap(a[j-1],a[j]);r++;}}}cout<<r<<endl;}}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define equals(a,b) (fabs((a)-(b)) < EPS)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

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

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

template <typename T>
void print_array(const T &ary, int size){
    REP(i,size){
        cout << ary[i] << " ";
    }
    cout << endl;
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;
const double EPS = (1e-10);

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(12);
    int s,w; cin >> s >> w;
    if(w >= s){
        cout << "unsafe" << endl;
    }else{
        cout << "safe" << endl;
    }

}

Measured memory_bytes: 3652
#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <iterator>
#include <map>
#include <set>
#include <iomanip>
#include <vector>
#include <cstdint>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Graph = vector<vector<int>>;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
#define rep(i, N) for(int i = 0; i < N; i++)
#define rep2(i, l, r) for (ll i = (ll)l; i < (ll)(r); i++)
#define INF 1000000000000000000
#define MAX 200001

const int MOD = 1000000007;

template <typename T > inline string toString(const T &a) {ostringstream oss; oss << a; return oss.str();};

template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) v += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr istream& operator >> (istream &is, Fp<MOD>& x) noexcept {
        return is >> x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

using mint = Fp<MOD>;

int main(){
    ll X, K, D;
    cin >> X >> K >> D;
    ll cnt = abs(X)/D;
    if(cnt >= K){
        cout << abs(X) - D*K << endl;
    }
    else{
        K -= cnt;
        if(K % 2 == 0){
            cout << abs(X) - D*cnt << endl;;
        }
        else{
            cout << abs(abs(X) - D*cnt - D) << endl;
        }
    }
}

Measured memory_bytes: 3628
#include <stdio.h>

int main(){
  int i,n,result=0;
  int p1,p2,p3;
  
  scanf("%d",&n);
  for(i=0;i<n;i++){
    if(i==0) scanf("%d",&p1);
    if(i==1) scanf("%d",&p2);
    if(i>=2){
	    scanf("%d",&p3);
    	if( (p1<p2 && p2<p3) || (p1>p2 && p2>p3) ) result++;
    	p1=p2;
    	p2=p3;
    }
  }
  printf("%d",result);
}

Measured memory_bytes: 128
package main

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

type ByValue []float64

func (s ByValue) Len() int           { return len(s) }
func (s ByValue) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
func (s ByValue) Less(i, j int) bool { return s[i] < s[j] }

func input() string {
	var s string
	fmt.Scan(&s)
	return s
}

func inputLn() string {
	var s string
	fmt.Scanln(&s)
	return s
}

func inputByScanner(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func inputLongLine() string {
	rdr := bufio.NewReaderSize(os.Stdin, 1000000)
	buf := make([]byte, 0, 1000000)
	for {
		l, p, e := rdr.ReadLine()
		if e != nil {
			panic(e)
		}
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}

func convListStrToInt(strList []string) []int {
	intList := make([]int, len(strList))
	for k, v := range strList {
		intV, _ := strconv.Atoi(v)
		intList[k] = intV
	}
	return intList
}

func convListStrToFloat(strList []string) []float64 {
	intList := make([]float64, len(strList))
	for k, v := range strList {
		intV, _ := strconv.Atoi(v)
		intList[k] = float64(intV)
	}
	return intList
}

func main() {
	n, _ := strconv.Atoi(input())
	hList := make([]int, n)
	for i := 0; i < n; i++ {
		num, _ := strconv.Atoi(input())
		hList[i] = num
	}

	res := "Yes"
	max := hList[0]
	for i := 1; i < n; i++ {
		if hList[i] < max {
			res = "No"
		}
		if max < hList[i] {
			max = hList[i] - 1
		}
	}
	fmt.Println(res)
}


Measured memory_bytes: 5504
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ll long long
#define MAXN 200005
using namespace std;

ll n,q,a,b,p,x;
vector<ll> adj[MAXN];
ll cnt[MAXN];
ll vis[MAXN];

void dfs(ll s, ll p)
{
    vis[s]=1;
    cnt[s]+=cnt[p];
    for(ll i=0;i<adj[s].size();i++)
    {
        ll t=adj[s][i];
        if(!vis[t])
        {
            dfs(t,s);
        }
    }
}

int main(int argc, char const *argv[])
{
    cin>>n>>q;
    for(ll i=0;i<n-1;i++)
    {
        cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    for(ll i=0;i<q;i++)
    {
        cin>>p>>x;
        cnt[p]+=x;
    }
    dfs(1,0);
    for(ll i=1;i<=n;i++) cout<<cnt[i]<<" ";
    cout<<endl;
    return 0;
}

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

int main() {
	int n;
	cin >> n;
	int a[n][2];
	int diff = 0;
	for(int i = 0; i < n; i++) {
		cin >> a[i][0];
	} for(int i = 0; i < n; i++) {
		cin >> a[i][1];
		if (a[i][0] - a[i][1] > 0) diff += a[i][0] - a[i][1];
	} cout << diff;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()

int main(void){
  string s;
  cin>>s;
  int mae,ato;
  mae = (s[0]-'0')*10+s[1]-'0';
  ato = (s[2]-'0')*10+s[3]-'0';
  bool ok1, ok2;
  ok1 = mae >= 1 && mae <= 12;
  ok2 = ato >= 1 && ato <= 12;
  if(ok1&&ok2){
    cout<<"AMBIGUOUS"<<endl;
  }else if(ok1){
    cout<<"MMYY"<<endl;
  }else if (ok2){
    cout<<"YYMM"<<endl;
  }else{
    cout<<"NA"<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using  namespace std;
int main(){
    long long x, ans;
    cin >> x;
    ans = x/11*2;
    if(x%11!=0){
        if((x%11)>6){
            ans += 2;
        }else{
            ans++;
        }
    }

  cout << ans << endl;
 
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll 	long long
#define pb push_back
#define mp make_pair
using namespace std;

int main()
{

int n; cin>>n;

 if(n>399 && n<600)
cout<<" 8 \n";

else if(n>599 && n<800)
cout<<" 7 \n";

else if(n>799 && n<1000)
cout<<" 6 \n";
else if(n>999 && n<1200)
cout<<" 5 \n";

else if(n>1199 && n<1400)
cout<<" 4 \n";
else if(n>1399 && n<1600)
cout<<" 3 \n";
else if(n>1599 && n<1800)
cout<<" 2 \n";
else if(n>1799 && n<2000)
cout<<" 1 \n";
    return 0;
}

Measured memory_bytes: 3628
// AND Grid
// * frank_c1
// * 2017 / 10 / 01

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

const int maxn = 505;
char s[maxn][maxn], a[maxn][maxn], b[maxn][maxn];

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
	for (int i = 1; i <= n; ++i) for (int j = 2; j < m; ++j) {
		if (i & 1) a[i][j] = '#', b[i][j] = '.';
		else a[i][j] = '.', b[i][j] = '#';
	}
	for (int i = 1; i <= n; ++i) a[i][1] = '#', b[i][1] = '.';
	for (int i = 1; i <= n; ++i) a[i][m] = '.', b[i][m] = '#';
	for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j)
		if (s[i][j] == '#') a[i][j] = b[i][j] = '#';
	for (int i = 1; i <= n; ++i) printf("%s\n", a[i] + 1); putchar('\n');
	for (int i = 1; i <= n; ++i) printf("%s\n", b[i] + 1);
	return 0;
}

Measured memory_bytes: 1536
n,k=map(int,input().split())
r,s,p=map(int,input().split())
t=input()
ans=0
for i in range(k):
    if t[i]=="r":
        ans+=p
    elif t[i]=="s":
        ans+=r
    else:
        ans+=s
for i in range(n-k):
    if t[i+k]==t[i]:
        t=t[:i+k]+"n"+t[i+k+1:]
    else:
        if t[i+k]=="r":
            ans+=p
        elif t[i+k]=="s":
            ans+=r
        else:
            ans+=s

print(ans)


Measured memory_bytes: 3460
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define ll long long
#define pb push_back
#define st first
#define N 200005
#define nd second
#define ii pair<int,int>
#define fr freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
vector <ll> p,f;
ll c,n;
ll k;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//fr
	cin>>n>>k;
	ll sum=0;
	for(int i=0;i<n;i++){
		cin>>c;
		p.pb(c);
		sum+=c;
	}
	if(sum<=k){
		return cout<<0,0;
	}
	for(int i=0;i<n;i++){
		cin>>c;
		f.pb(c);
	}
	sort(p.begin(),p.end());
	sort(f.begin(),f.end());
	ll l=-1, h= f[n-1] * p[n-1], mid;
	while(l+1<h){
		ll cost=0;
		mid=(l+h)/2;
		for(int i=0;i<n;i++){
			if(mid<p[i]*f[n-1-i]){
				cost+=p[i]-mid/f[n-1-i];
			}
		}
		if(cost<=k){
			h=mid;
		}
		else{
			l=mid;
		}
	}
	cout<<h;
}


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

int main()
{
	string a,b;
	int h;
	int zh(string s);
	
	cin>>a>>b;
	
	h=zh(a+b);
	
	if(int(sqrt(h))==sqrt(h))
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
	
	return 0;
}

int zh(string s)
{
	int temp=0;
	
	for(int i=0;i<s.size();i++)
		temp=temp*10+(s[i]-'0');
	
	return temp;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 100005
#define INF 1000000005
#define PI 3.1415926535897
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define IN(a) cin>>(a)
#define OUT(a) cout<<(a)<<endl
typedef pair<int,int> P;
const int MAX = 1000005;
const int MOD = 1000000007;
vector<P> to[N];
vector<bool>color(N);
vector<int>dst(N);
bool f=true;
void dfs(int no,int p){
    if(!f)return;
    for(auto s:to[no]){
        if(s.first==p)continue;

            int w=dst[no]+s.second;
            if(color[s.first]){
                if(dst[s.first]!=w){
                    f=false;
                    break;
                }
            }else{
                dst[s.first]=w;
                color[s.first]=true;
                dfs(s.first,no);
            }
        
    }
}
int main(){
    int n,m;
    cin>>n>>m;
    REP(i,m){
        int l,r,d;
        cin>>l>>r>>d;
        l--;r--;
        to[l].push_back({r,d});
        to[r].push_back({l,-d});
    }
    REP(i,n){
        if(!color[i])color[i]=true;dfs(i,-1);
    }
    if(f)OUT("Yes");
    else OUT("No");
    return 0;
}


Measured memory_bytes: 12928
#include<iostream>
#include<string>
#include<algorithm>	
#include<cmath>
using namespace std;
int main() {
	int a, b; 
	cin >> a;
	int test[1010] = { 0 };
	for (int h = 1; h <= a; h++) {
		cin >> b;
		test[h] = b;
	}
	for (int h = a; h >= 1; h--) {
		cout << test[h];
		if (h >= 2) {
			cout << ' ';
		}
	}
	cout << endl;
}


Measured memory_bytes: 3080
#include "bits/stdc++.h"

#define ll          long long
#define pb          push_back
#define pii         pair<ll int,ll int>
#define vpii        vector< pii >
#define vi          vector<ll int>
#define vs			vector< string >
#define vvi         vector< vector< ll > >
#define inf			1'010'000'000'000'000'017LL
#define all(it,a)   for(auto it=(a).begin();it!=(a).end();it++) 
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define repr(i,a,b) for(ll int i=a;i>b;i--)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define mp          make_pair
#define whatis(x)   cout << #x << " is " << x << "\n";
#define graph(n)    adj(n,vector< ll > () )

using namespace std;


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


void Main()
{
	int N;
	cin >> N;
	vi H(N + 10, 0);
	for (size_t i = 0; i < N; i++)
	{
		cin >> H[i];
	}
	vi dp(N + 10, inf);
	dp[0] = 0;

	for (size_t i = 0; i < N; i++)
	{
		for (size_t h = 1; h <= 2; h++)
		{
			chmin(dp[i + h], dp[i] + abs(H[i] - H[i + h]));
		}
	}

	cout << dp[N - 1] << endl;
}

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

	Main();
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long ll;
const int INT_MAX = (1 << 31) - 1;

// RMQ
class SqrtDecomp{
    private:
        int N, sqrtN, K;
        vector<int> data;
        vector<int> min_bucket;
    public:
        SqrtDecomp(int N);
        void update(int i, int x);
        int query(int a, int b);
};

SqrtDecomp::SqrtDecomp(int n){
    N = n;
    sqrtN = ceil(sqrt(N));
    K = N / sqrtN + 1;
    for(int i=0; i<K*sqrtN; i++){
        data.push_back(INT_MAX);
    }
    for(int i=0; i<sqrtN; i++){
        min_bucket.push_back(INT_MAX);
    }
}

void SqrtDecomp::update(int i, int x){
    int b_idx = i / sqrtN;
    int l = b_idx*sqrtN, r = (b_idx+1)*sqrtN;
    data[i] = x;
    min_bucket[b_idx] = x;
    for(int j=l; j<r; j++){
        min_bucket[b_idx] = min(min_bucket[b_idx], data[j]);
    }

}

// [a, b)
int SqrtDecomp::query(int a, int b){
    int res = INT_MAX;
    for(int i=0; i<K; i++){
        int l = i*sqrtN, r = (i+1)*sqrtN;
        if (b <= l || r <= a) continue;
        else if (a <= l && r <= b){
            res = min(res, min_bucket[i]);
        }else{
            for(int j=max(a, l); j<min(b, r); j++) res = min(res, data[j]);
        }
    }
    return res;
}

int main(){
    int n, q; cin >> n >> q;
    SqrtDecomp sd(n);
    for(int i=0; i<q; i++){
        int com, x, y; cin >> com >> x >> y;
        if (com == 0) sd.update(x, y);
        else cout << sd.query(x, y+1) << endl;
    }
}



Measured memory_bytes: 3484
#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
using namespace std;

int H = 0, Cx, Cy;
int n;
int x[110], y[110], h[110];

bool judge(int H, int Cx, int Cy)
{
    for(int i = 0; i < n; i++)
    {
        if(abs(max((H - (abs(x[i]-Cx)+abs(y[i]-Cy))), 0) - h[i]) > 1e-6){
            return 0;
        }
    }
        return 1;
        
    
}
int main()
{
    
    int i;
    scanf("%d", &n);
    
    for(i = 0; i < n; i++)
    {
        cin>>x[i]>>y[i]>>h[i];
    }
    
    
    int t;
    for(i = 0;i < n; i++) if(h[i]) break;
    t = i;
    for(Cx = 0; Cx <= 100; Cx++)
        for(Cy = 0; Cy <= 100; Cy++)
        {
            
            H = abs(Cx - x[t]) + abs(Cy - y[t]) + h[t];
            
            //
            if(judge(H, Cx, Cy))
            {
                cout<<Cx<<" "<<Cy<<" "<<H<<endl;
                return 0;
            }
        }
    
    return 0;
    
}


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

using namespace std;
#define _for(i,j,N) for(int i = (j);i < (N);i++)
#define _rep(i,j,N) for(int i = (j);i <= (N);i++)
#define _dec(i,j,N) for(int i = (N-1);i >= (j);i--)
#define ALL(x) x.begin(),x.end()
#define PB push_back
#define LL long long

template<typename T>
ostream& operator<<(ostream& os,const vector<T>& v) {
    _for(i,0,v.size()) os << v[i] << " ";
    return os;
}

template<typename T>
ostream& operator<<(ostream& os,const set<T>& v){
    for(typename set<T>::iterator it = v.begin();it != v.end();it++)
    os << *it <<" ";
    return os;
}

const int maxn = 1e5+5;

int weight[maxn];
int f[maxn];

int finds(int x){return (x == f[x]?x:(f[x] = finds(f[x])));}
LL unions(int x,int y){
    int fx = finds(x);
    int fy = finds(y);
    if(fy == fx) return 0;
    LL wl = weight[fx];
    LL wr = weight[fy];

    //cout << fx <<" " <<fy << endl;

    if(wl > wr){
        f[fy] = fx;
        weight[fx] += wr;
    }
    else{
        f[fx] = fy;
        weight[fy] += wl;
    }

    return wl*wr;
}

LL N,M;

stack<LL> st;

vector<int> A;
vector<int> B;

int main()
{
    cin >> N >> M;
    LL ans = (N*(N-1))/2;
    st.push(ans);

    _rep(i,1,N){
        f[i] = i;
        weight[i] = 1;
    }

    _rep(i,1,M){
        int a,b;
        scanf("%d %d",&a,&b);
        A.push_back(a);
        B.push_back(b);
    }

    _dec(i,0,M){
        ans-=unions(A[i],B[i]);
        st.push(ans);
    }


    if(!st.empty()) st.pop();
    while(!st.empty()){
        printf("%lld\n",st.top());
        st.pop();
    }

    return 0;
}

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

int ChengeRate(int n)
{
    int rateNum;
    if(n <= 399)
    {
        rateNum = 0;
    }
    else if(n <= 799)
    {
        rateNum = 1;
    }
    else if(n <= 1199)
    {
        rateNum = 2;
    }
    else if(n <= 1599)
    {
        rateNum = 3;
    }
    else if(n <= 1999)
    {
        rateNum = 4;
    }
    else if(n <= 2399)
    {
        rateNum = 5;
    }
    else if(n <= 2799)
    {
        rateNum = 6;
    }
    else if(n <= 3199)
    {
        rateNum = 7;
    }
    else
    {
        rateNum = 8;
    }
    return rateNum;
}

int main()
{
    int n;
    while(cin >> n)
    {
        int checker[8] = {};
        int ans = 0;
        int free = 0;
        for(int i = 0; i < n; ++i)
        {
            int t;
            cin >> t;
            int sub = ChengeRate(t);
            //cout << sub;
            if(sub <= 7)
            {
                checker[sub] = 1;
            }
            else
            {
                free += 1;
            }
        }
        //cout << endl;
        for(int i = 0; i <= 7; ++i)
        {
            //cout << checker[i];
            if(checker[i] == 1)
            {
                ans += 1;
            }
        }
        //cout << endl;

        cout << max(ans, 1) << " " << ans+free << endl;

    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)
#define VL vector<ll>
#define VS vector<string>
#define VB vector<bool>
#define VP vector<pair<ll,ll>>
#define VVL vector<vector<ll>>
#define VVP vector<vector<pair<ll,ll>>>
#define PL pair<ll,ll>
#define ALL(v) (v).begin(), (v).end()
ll d1[4] = {1, -1, 0, 0};
ll d2[4] = {0, 0, 1, -1};

int main(){
    ll N, Q;
    cin >> N >> Q;
    VVL G(N+1);
    VL cnt(N+1, 0);
    rep(i, 0, N-1){
        ll a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    rep(q, 0, Q){
        ll p, x;
        cin >> p >> x;
        cnt[p] += x;
    }
    VB seen(N+1, false);
    queue<ll> que;
    que.push(1);
    seen[1] = true;
    while(!que.empty()){
        auto q = que.front();
        que.pop();
        seen[q] = true;
        for(auto g : G[q]){
            if(seen[g]) continue;
            que.push(g);
            cnt[g] += cnt[q];
        }
    }
    
    rep(i, 1, N+1) cout << cnt[i] << " ";
    cout << endl;
    return 0;
}

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

// int main(int argc, char const *argv[])
// {
// 	int n;
// 	while(cin>>n){
// 		char c;
// 		set<char>s;
// 		for(int i=0;i<n;i++){
// 			cin>>c;
// 			s.insert(c);
// 		}
// 		if(s.size()==3){
// 			cout<<"Three"<<endl;
// 		}
// 		else{
// 			cout<<"Four"<<endl;
// 		}
// 	}
// 	return 0;
// }

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

int main(int argc, char const *argv[])
{
	int n;
	while(cin>>n){
		string s;
		vector<ll>num(5,0);
		for(int i=0;i<n;i++){
			cin>>s;
			//M, A, R, C or H
			if(s[0]=='M'){
				num[0]++;
			}
			else if(s[0]=='A'){
				num[1]++;
			}
			else if(s[0]=='R'){
				num[2]++;
			}
			else if(s[0]=='C'){
				num[3]++;
			}
			else if(s[0]=='H'){
				num[4]++;
			}
		}
		ll ans=0;
		for(int i=0;i<5;i++){
			for(int j=i+1;j<5;j++){
				for(int k=j+1;k<5;k++){
					ll temp=num[i]*num[j]*num[k];
					ans+=temp;
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout
	cnt := 0

	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
		cnt = 3
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)
	solve(scanner, writer)
	for i := 0; i < cnt; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
	writer.Flush()
}

func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	n := getNextInt(scanner)
	s := getNextString(scanner)
	dd := make([]int, n+1)
	cc := make([]int, n+1)
	for i := 0; i < n; i++ {
		if s[i] == 'D' {
			dd[i+1]++
		}
		if s[i] == 'C' {
			cc[i+1]++
		}
	}
	for i := 0; i < n; i++ {
		dd[i+1] += dd[i]
		cc[i+1] += cc[i]
	}
	var dmc, horobiyo int64
	for i := 0; i < n; i++ {
		if s[i] != 'M' {
			continue
		}
		dmc += int64(dd[i]) * int64(cc[n]-cc[i])
	}
	q := getNextInt(scanner)
	for c := 0; c < q; c++ {
		k := getNextInt(scanner)
		horobiyo = 0

		dpair := make([]int64, n+1)
		cpair := make([]int64, n+1)
		for i := 0; i < n; i++ {
			dpair[i+1] = dpair[i]
			if s[i] != 'D' {
				continue
			}
			if i+k > n {
				continue
			}
			dpair[i+1] += int64(cc[n] - cc[i+k])
		}
		for i := 0; i < n; i++ {
			cpair[i+1] = cpair[i]
			if s[i] != 'C' {
				continue
			}
			if i-k+1 < 0 {
				continue
			}
			cpair[i+1] += int64(dd[i-k+1])
		}

		for i := 0; i < n; i++ {
			if s[i] != 'M' {
				continue
			}
			horobiyo += dpair[i] - cpair[i]
		}

		fmt.Fprintln(writer, dmc-horobiyo)
	}
}


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

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

    int w, h, x, y, r;
    cin >> w >> h >> x >> y >> r;
    if (r <= x && x <= w - r && r <= y && y <= h - r){
        cout << "Yes" << endl; 
    }
    else{
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 3208
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<string>
#include<sstream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cctype>
#include<climits>
using namespace std;
#define REP(i, j) for(int i = 0; i < j; i++)
#define FOR(i, j, k) for(int i = j; i < k; i++)
#define P pair<int, int>
const int INF = INT_MAX / 2;

int main(){
    int n;
    while(cin >>n && n){
        vector<int> vec(n + 1, 0); FOR(i, 1, n + 1) cin >>vec[i];
        FOR(i, 1, n + 1) vec[i] += vec[i - 1];
        int ans = -1 * INF;
        REP(i, n + 1) FOR(j, i + 1, n + 1) ans = max(ans, vec[j] - vec[i]);
        cout <<ans <<endl;
    }
    return 0;
}

Measured memory_bytes: 1208
import java.util.Scanner;

public class Main {

	@SuppressWarnings("resource")
	public static void main(String args[]) {
		Scanner scanner = new Scanner(System.in);
		long N=scanner.nextLong();
		for(int h=1;h<=3500;h++) {
			for(int n=1;n<=3500;n++) {
				if((4*h*n-N*n-N*h)!=0&&(N*h*n)%(4*h*n-N*n-N*h)==0) {
					long w=(N*h*n)/(4*h*n-N*n-N*h);
					if(w<1)continue;
					System.out.println(h+" "+n+" "+w);
					return;
				}
			}
		}
	}
}


Measured memory_bytes: 25172
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; 
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
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 maxNum=100010;
vector<bool> isPrime(maxNum,true);
void sieve(ll n){
    isPrime[0]=false;
    isPrime[1]=false;

    for(ll i=2;i<n;i++){
        if(!isPrime[i]) continue;
        for(int j=i*2;j<=n;j+=i)    isPrime[j]=false;
    }
}
map<ll,int> mp;
void divisor(ll n) {
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
    mp[i]++;
      if(i * i != n) mp[n/i]++;
    }
  }
}
bool is_prime(ll x) {
  for(ll i = 2; i * i <= x; i++) {
    if(x % i == 0) return false;
  }
  return true;
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    ll a,b;
    cin>>a>>b;
    divisor(a);divisor(b);
    vector<ll> v;
    for(auto x:mp){
        if(x.second==2){
            v.push_back(x.first);
        }
    }
    ll ans=0;
    for(auto x:v){
        if(x==1||is_prime(x)) ans++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VL vector<long long>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 1e6+10;
int main(){
    DRII(Q,H);DRII(S,D);
    S=min(S,Q*4);
    S=min(S,H*2);
    D=min(D,S*2);
    DRI(N);
    cout<<N/2LL*D+N%2LL*S<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>

const int max = 1000000000;

int n;
int data[101][101];
long long cost[101];
bool used[101];

void dijkstra(int s){
	for (int i = 1; i <= n; i++)cost[i] = max;
	for (int i = 1; i <= n; i++)used[i] = false;

	cost[s] = 0;
	while (true){
		int v = -1;
		for (int i = 1; i <= n; i++){
			if (!used[i] && (v == -1 || cost[i] < cost[v]))v = i;
		}
		if (v == -1)break;

		used[v] = true;

		for (int i = 1; i <= n; i++){
			cost[i] = std::min(cost[i], cost[v] + data[v][i]);
		}
	}
}

int main(){

	int k;
	while (std::cin >> n >> k, n || k){
		for (int i = 1; i <= 100; i++){
			for (int j = 1; j <= 100; j++){
				data[i][j] = max;
			}
		}

		for (int i = 0; i < k; i++){
			int t;
			std::cin >> t;

			if (t == 0){
				int a, b;
				std::cin >> a >> b;

				dijkstra(a);
				if (cost[b] == max)std::cout << -1 << std::endl;
				else std::cout << cost[b] << std::endl;
			}

			if (t == 1){
				int c, d, e;
				std::cin >> c >> d >> e;

				data[c][d] = std::min(data[c][d], e);
				data[d][c] = std::min(data[d][c], e);
			}
		}
	}

	return 0;
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
#define PRINT(v) for (auto x : (V)) cout <<x <<" " <<endl;
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
template<class T> struct edge { int from, to; T cost;};
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;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }
template<class T> inline T power(T a,T b,T m){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}
void hey(){ cout <<"hey" <<endl; }


int N,M;
vector<vector<int>> city(100001, vector<int>());
vector<pair<int,int>> shis;

int main() {
  cin >>N >>M;
  shis.assign(M, {0,0});
  rep(i, M){
    int p,y; cin >>p >>y;
    city[p].push_back(y);
    shis[i].first = p; // どこの県に属しているか
    shis[i].second = city[p].size() - 1; // その県のなかでindexは何番か
  }
  // cityを座標圧縮
  vector<int> com;
  rep(i, city.size()){
    if (city[i].size() == 0) continue;
    com = city[i];
    sort(all(com));
    com.erase(unique(all(com)), com.end());
    rep(j, city[i].size()){
      city[i][j] = lower_bound(all(com), city[i][j]) - com.begin();
    }
  }
  
  rep(i, M){
    int p = shis[i].first;
    printf("%06d", p);
    int y = city[p][shis[i].second] + 1;
    printf("%06d\n", y);
  }
  
}


Measured memory_bytes: 7808
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
using namespace std;

int main(void)
{ 
	int N;
	pair<pair<string, int>, int> r[100];
	cin >> N;
	for (int i = 0; i < N; i++) {
		string s;
		int p;
		cin >> s >> p;
		r[i] = make_pair(make_pair(s, -p), i+1);
	}
	sort(r, r + N);
	for (int i = 0; i < N; i++) {
		cout << r[i].second << endl;
	}


	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <vector>
#include <list>
#include <array>
#include <string>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <unordered_map>
#include <stdexcept>


using std::string;
using std::vector;


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// util
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

std::vector<std::string> split(const std::string& input, char delimiter)
{
    std::istringstream stream(input);

    std::string field;
    std::vector<std::string> result;
    while (std::getline(stream, field, delimiter)) {
        result.push_back(field);
    }
    return result;
}



//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// user func
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void printList(const vector<int>& list) {
    // print
    for(int i = 0; i < list.size(); i++){
        printf("%d", list[i]);
        if(i != list.size() -1){
            printf(" ");
        }
    }
    printf("\n");
}



//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// logic
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int find(const vector<int> haystack, int needle){
    for(auto& each: haystack){
        if(each == needle) return 1;
    }
    return 0;
}

void solve() {
    int n1;
    scanf("%d", &n1);
    vector<int> s(n1);
    for(int i = 0; i < n1; i++){
        int v;
        scanf("%d", &v);
        s[i] = v;
    }

    int n2;
    int common = 0;
    scanf("%d", &n2);
    for(int i = 0; i < n2; i++){
        int v;
        scanf("%d", &v);
        common += find(s, v);
    }
    printf("%d\n", common);
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// main
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main() {
    solve();
    return 0;
}


Measured memory_bytes: 3248
///-----Bismillahir Rahmanir Rahim-----///

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

///---FAST I/O---///
#define Boost() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

///---DATA TYPE---///
typedef long long ll;
typedef long long int lli;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<int>::iterator vit;
typedef set<int>::iterator sit;

///---LOOP---///
#define rep0(i,n) for(i=0;i<n;i++)
#define rep1(i,n) for(i=1;i<=n;i++)

///---I/O---///
#define sf scanf
#define pf printf

///---OTHERS---///
#define pb push_back
#define all(c)		c.begin(),c.end()
#define MK make_pair
#define F first
#define S second
#define endl '\n'


///---INITIALIZATION---//
#define mem(a,b) memset(a, b, sizeof(a) )

///---CALCULATE---///
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define sqr(a) ((a) * (a))

///---BIT OPERATION---///
inline bool checkBit(ll n, int i)
{
    return n&(1LL<<i);
}
inline ll setBit(ll n, int i)
{
    return n|(1LL<<i);;
}
inline ll resetBit(ll n, int i)
{
    return n&(~(1LL<<i));
}

///------String/Char Related Functions-----///
string makeintString(int x)
{
    stringstream ss;
    ss << x;
    string str = ss.str();
    ///cout<<str<<endl;
    return str;
}
string makellString(ll x)
{
    stringstream ss;
    ss << x;
    string str = ss.str();
    ///cout<<str<<endl;
    return str;
}
char cpp(char c)
{
    return static_cast<char>(c + 1);
}

///------------Sorting STL----------///
struct func
{
    //this is a sample overloading function for sorting stl
    bool operator()(pii const &a, pii const &b)
    {
        if(a.F==b.F)
            return (a.S<b.S);
        return (a.F<b.F);
    }
};

///---CONSTANT---///
const double PI = acos(-1);
const double eps = 1e-9;
const int inf = 2000000000;
const ll infLL = 9000000000000000000;
#define MOD 1000000007

int main()
{
    Boost();

    int n,cnt[]={0,0,0,0};
    cin>>n;
    string s,a[]= {"AC","WA","TLE","RE"};
    for(int i=0; i<n; i++)
    {
        cin>>s;
        if(s==a[0]) cnt[0]++;
        else if(s==a[1]) cnt[1]++;
        else if(s==a[2]) cnt[2]++;
        else if(s==a[3]) cnt[3]++;
    }
    for(int i=0;i<4;i++)
    {
        cout<<a[i]<<" x "<<cnt[i]<<endl;
    }
    return 0;
}


Measured memory_bytes: 3676
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1005;
const int W = 10005;
struct item{
	int w , s ,v;
};

int n;
vector<item> v;
int dp[N][W];
int32_t main(){
	cin>>n;
	v.resize(n);
	for(int i = 0 ; i < n; i ++) cin>>v[i].w >> v[i].s >> v[i].v;
	sort(v.begin() , v.end() , [&](item a , item b){
		return (a.w + a.s) < (b.w + b.s); 
	});
	int ans = 0;
	for(int i = 0 ; i < n; i ++){
		for(int j = 0 ; j <= v[i].s; j++){
			if(i == 0){
				if(j != 0) continue;
				dp[i][v[i].w] = v[i].v;
				ans = max(ans , dp[i][v[i].w]);
			}
			else{
				int U = j + v[i].w;
				int R = dp[i-1][j] + v[i].v;
				
				ans = max(ans , R);
				if(U < W) dp[i][U] = max(dp[i][U] , R);
			}
		}
		for(int j = 0 ; j < W ; j ++){
			if(i){
				dp[i][j] = max(dp[i][j], dp[i-1][j]);
				ans = max(ans, dp[i][j]);
			}
		}
	}
	cout<<ans<<endl;
}

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

using namespace std;

using ll =  long long;
using Pll = pair<ll, ll>;
using Pii = pair<int, int>;

constexpr ll MOD = 1000000007;
constexpr long double EPS = 1e-10;
constexpr int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

vector<ll> argcnt(300000+1, 0), k_argcnt(300000+1, 0);

int calc(int n, int k) {
    int ok = 0, ng = n+1;
    while(ng-ok > 1) {
        int mid = (ok+ng) / 2;

        ll max_length = (k_argcnt[mid] + mid * (argcnt[n] - argcnt[mid])) / mid;
        if(max_length >= k) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    return ok;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    int a;
    vector<int> cnt(n+1, 0);
    for(int i=0;i<n;++i){
        cin >> a;
        ++cnt[a];
    }

    for(int i=1;i<=n;++i) {
        ++argcnt[cnt[i]];
    }
    for(int i=1;i<=n;++i) {
        k_argcnt[i] = i * argcnt[i] + k_argcnt[i-1];
        argcnt[i] += argcnt[i-1];
    }

    for(int k=1;k<=n;++k) {
        cout << calc(n, k) << endl;
    }
}


Measured memory_bytes: 8448
// #pragma GCC optimize ("O3")
// #pragma GCC target ("sse4")

#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;
const int NINF = -1*INF;
const long long LLINF = 1ll << 60;
const long long LLNINF = -1*LLINF;

template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ";
    return os << "}";
}

template <class X, class Y>
ostream & operator << (ostream & os, pair <X, Y> const& p) {
	return os << "[ " << p.first << ", " << p.second << "]" ;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<ld> vld;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vector<int>> vvi;
typedef vector<vll> vvll;
typedef vector<vd> vvd;
typedef vector<vld> vvld;
 
#define mp make_pair
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()
#define revAll(x) x.rbegin(), x.rend()
#define gcd(a, b) __gcd(a, b)
#define popcount(x) __builtin_popcount(x)
#define isize(x) (int)(x.size())
#define rep(i,n) for(int i = 0; i < n; i++)
#define exists(x,m) m.find(x) != m.end()
#define umap unordered_map
#define uset unordered_set
#define pq priority_queue

const ll MOD = 1e9 + 7;

vll primes_up_to(ll lim) {
	vll primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
					41, 43, 47, 53, 59, 61, 67, 71};
	if (lim <= 71) return {primes.begin(), upper_bound(all(primes), lim)};
	for (int num = 73; num <= lim; num++) {
		bool is_prime = true;
		for (int i = 0; primes[i]*primes[i] <= num; i++) {
			if (num % primes[i] == 0) {
				is_prime = false;
				break;
			}
		}
		if (is_prime) primes.pb(num);
	}	
	return primes;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	int n; cin >> n;
	vi A = vi();
	int maxx = 0;
	rep(i, n) {
		int x; cin >> x;
		A.pb(x);
		maxx = max(maxx, x);
	}	
	vll primes = primes_up_to(1e6);
	map<int, int> prime_freq = map<int, int>();
	for (const int& a : A) {
		int b = a;
		for (int i = 0; primes[i]*primes[i] <= b; i++) {
			if (b % primes[i] == 0) prime_freq[primes[i]]++;
			while(b % primes[i] == 0) b /= primes[i];
		}
		if (b != 1) prime_freq[b]++;
	}
	int max_freq = 0;
	for (const auto& [p, freq] : prime_freq) {
		max_freq = max(max_freq, freq);
	}
	if (max_freq <= 1) {
		cout << "pairwise coprime";
	} else {
		cout << (max_freq < n ? "setwise coprime" : "not coprime");
	}
}

Measured memory_bytes: 11176
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 1000000000
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
typedef long long int ll;

#define ARRAY_MAX 101
#define MOD 1000000007

int main(){

    string s;
    cin >> s;
    ll ans = 0;
    for(int i = 0;i < (1<<s.length()-1);i++){
        ll tmp = s[0] -'0';
        for(int j = 0;j < s.length()-1;j++){

            if((i>>j)&1){

                ans += tmp;
                tmp = s[j+1] - '0';
                //cout << i << " a " << tmp << endl;

            }else{
                tmp = tmp*10 + s[j+1]-'0';
                //cout << i << " b " << tmp << endl;
            }
        }
        //cout << tmp << endl;
        ans += tmp;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256