akhauriyash/Code-Regression huggingface dataset:
//#pragma GCC optimize ("-O3","unroll-loops")
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>


#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 REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
#define print(x) cout<<x<<'\n';
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
#define int long long
//#define int unsigned long long
#define all(x) (x).begin(), (x).end()
#define double long double

using namespace std;

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;
}

const int MOD = 998244353;
const ll INF = 1e17;
const double pi = acos(-1);
const double EPS = 1e-10;
typedef pair<int, int>P;
const int MAX = 200020;



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

	int A, B; cin >> A >> B;
	int sum = A + B;
	if (sum % 2 == 1) {
		print("IMPOSSIBLE");
	}
	else {
		print(sum / 2);
	}
}


Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int, n, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
	}
	sort.Ints(a)

	answer := float64(a[0])
	for i := 1; i < n; i++ {
		answer = (answer + float64(a[i])) * 0.5
	}
	fmt.Println(answer)
}


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

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << ((a * b > c * d)? a * b : c * d) << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
char c;
int f;
int nextInt();

int N, n, i, t;
int A[100001];
char B[100001];
int main(){
	N=nextInt();
	for(i=1; i<=N; i++){
		A[i]=nextInt();
	}
	i=0;
	n=1;
	do{
		t = A[n];
		A[n] = 1;
		n = t;
		i++;
	}while(n!=1 && n!=2);
	if(n==2){
		printf("%d\n", i);
	}else{
		printf("-1\n");
	}
}

int nextInt(){
	f=0; c=getchar();
	while((c<'0')||('9'<c)){c=getchar();}
	while((c>='0')&&(c<='9')){f=f*10+(c-'0'); c=getchar();}
	return f;
}


Measured memory_bytes: 512
#include<stdio.h>
int main()
{
    int i,s;
char A[10000];
while(1)
{
    scanf("%s",A);
    s=0;
    if(A[0]=='0')
    {
        break;
    }
    else
    {
        for(i=0;A[i]!='\0';i++)
        {
           s+=A[i]-'0';
        }
    }
    printf("%d\n",s);
}
}



Measured memory_bytes: 2064
//   AtCoder Beginner Contest 072 C

#include<stdio.h>


    int d[100005];

int main(void)
{

    int i, N, a, t;
    int max = 0;

    scanf("%d", &N);

    for(i = 0; i < 100005; i++)
        d[i] = 0;

    for(i = 0; i < N; i++){
        scanf("%d", &a);
        if(a>0){d[a-1]++;}
        d[a]++; d[a+1]++;
    }
   
    for(i = 0; i < 100005; i++){
        if (max < d[i]) max = d[i];
    }
   
   
    printf("%d\n", max);

    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <map>

using ll = long long;

using namespace std;

using P = pair<int, int>;
#define fi first
#define se second

int main() {
    map<int, P> m;
    bool bingo[3][3] = {{0}};
    for (int i=0; i<3; i++) {
        for (int j=0; j<3; j++) {
            int a;
            cin >> a;
            m[a] = {i, j};
        }
    }
    int n;
    cin >> n;
    for (int i=0, b; i<n; i++) {
        cin >> b;
        if (m.count(b)) bingo[m[b].fi][m[b].se] = true;
    }
    int row[3] = {0}, col[3] = {0}, xl = 0, xr = 0;
    for (int i=0; i<3; i++) {
        for (int j=0; j<3; j++) {
            if (!bingo[i][j]) continue;
            if (++row[i] == 3 || ++col[j] == 3 || (i == j && ++xl == 3) || (i + j == 2 && ++xr == 3)) {
                cout << "Yes" << '\n';
                return 0;
            }
        }
    }
    cout << "No" << '\n';
    return 0;
}

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

template <class T>
inline bool uin(T& a, T b) { return a > b ? (a = b, true) : false; }
template <class T>
inline bool uax(T& a, T b) { return a < b ? (a = b, true) : false; }

struct dsu {
	vector<int> p;
	dsu(int n) : p(n, -1) {}
	inline int size(int x) {
		return -p[get(x)];
	}
	inline bool same_set(int a, int b) {
		return get(a) == get(b);
	}
	int get(int x) {
		return p[x] < 0 ? x : p[x] = get(p[x]);
	}
	inline bool unite(int a, int b) {
		a = get(a);
		b = get(b);
		if (a == b) return false;
		if (p[a] > p[b]) swap(a, b);
		p[a] += p[b];
		p[b] = a;
		return true;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N, L, K;
	cin >> N >> L >> K;
	dsu rd(N), rl(N);
	for (int u, v, i = 0; i < L; ++i) {
		cin >> u >> v;
		--u, --v;
		rd.unite(u, v);
	}
	for (int u, v, i = 0; i < K; ++i) {
		cin >> u >> v;
		--u, --v;
		rl.unite(u, v);
	}

	map<pair<int, int>, int> cnt;
	for (int i = 0; i < N; ++i) {
		int cc_road = rd.get(i);
		int cc_rail = rl.get(i);
		++cnt[make_pair(cc_road, cc_rail)];
	}

	for (int i = 0; i < N; ++i) {
		int cc_road = rd.get(i);
		int cc_rail = rl.get(i);
		cout << cnt[make_pair(cc_road, cc_rail)] << ' ';
	}
}

Measured memory_bytes: 16020
#include <iostream>
#include <string>
#include <algorithm>
#include <ctype.h>

using namespace std;

string slide(string s) {
  string r = s;
  for (int i = 0; i < r.length(); i++) {
    if (islower(r[i])) {
      if (r[i] == 'z') r[i] = 'a';
      else r[i] += 1;
    }
  }
  return r;
}

bool check_word(string s) {
  string dic[3] = {"this", "the", "that"};
  for (int i = 0; i < 3; i++)
    if (s.find(dic[i]) != string::npos) return true;
  return false;
}

int main() {
  string in, temp;
  bool found;
  while (1) {
    getline(cin, in);
    if (cin.eof()) break;
    for (temp = in, found = false; ; temp = slide(temp)) {
      found = check_word(temp);
      if (found) break;
    }
    cout << temp << endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
using ll  = long long;
using vl  = vector<ll>;
using vi  = vector<int>;
#define _GLIBCXX_DEBUG
#define IO_STREAM cin.tie(0);ios::sync_with_stdio(false)
#define all(x) x.begin(),x.end()
#define rep(i,sta,end) for(int i=sta;i<end;++i)
#define lcm(a,b) (a)/__gcd((a),(b))*(b)
#define pb push_back
const ll INF = 1000000000000000;
const ll MOD = 1000000007;
const double PI = acos(-1);
//||
#define DBG(a,b,c,d) //cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<endl
//DBG("","","","");

signed main(){
	IO_STREAM;
	int a,b;
	cin>>a>>b;
	string ans;
	if(a<=b){
		string c;
		c=to_string(a);
		rep(i,0,b) ans+=c;
	}
	else{
		string c;
		c=to_string(b);
		rep(i,0,a) ans+=c;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3656
import sys
S=input()
N=len(S)
S1=S[0:int((N-1)/2)]
S2=S[int((N+3)/2-1):]
#print(S1,S2)
if S1 != S2[::-1]:
  print('No')
  sys.exit()
if S1 != S1[::-1]:
  print('No')
  sys.exit()
if S2 != S2[::-1]:
  print('No')
  sys.exit()
print('Yes')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
const LL mod=1e9+7;
LL pm(LL x,LL y){
	LL z=1;
	while(y){
		if(y&1)z=z*x%mod;
		y>>=1;
		x=x*x%mod;
	}
	return z;
}
int b[N],p[N],cnt;
void P(){
	for(int i=2;i<N;i++){
		if(!p[i])b[++cnt]=i;
		for(int j=1;j<=cnt&&1ll*b[j]*i<N;j++){
			p[b[j]*i]=1;
			if(i%b[j]==0)break;
		}
	}
}
int n,a[N],CNT[N*10];
int main() {
  	ios::sync_with_stdio(false);
  	cin>>n;int y=0;LL x=1;P();
  	for(int i=1;i<=n;i++){
  		cin>>a[i];int x=a[i];
  		for(int j=1;j<=cnt&&1ll*b[j]*b[j]<=x;j++){
  			if(x%b[j]==0){
  				int c=0;
  				while(x%b[j]==0){
  					c++;
  					x/=b[j];
  				}
  				CNT[b[j]]=max(CNT[b[j]],c);
  			}
  		}
  		if(x!=1)CNT[x]=max(CNT[x],1);
  	}
  	LL lcm=1;
  	for(int i=2;i<=1000000;i++){
  		lcm*=pm(i,CNT[i]);
  		lcm%=mod;
  	}
  	LL ans=0;
  	for(int i=1;i<=n;i++){
  		ans+=lcm*pm(a[i],mod-2)%mod;
  		ans%=mod;
  	}
  	cout<<ans<<'\n';
 	return 0;
}

Measured memory_bytes: 6912
#include <stdio.h>
#include <limits.h>

int main(){
  int n, i, list[200000], max = INT_MIN, min;

  scanf("%d", &n);

  for(i=0; i<n; i++) scanf("%d", &list[i]);

  min = list[0];

  for(i = 1; i < n; i++){
    max = max>(list[i]-min)?max:(list[i]-min);
    min = min<list[i]?min:list[i];
  }

  printf("%d\n", max);
  
  return 0;
}

Measured memory_bytes: 1376
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
using namespace std;

int main()
{
  cin.tie(0);
  char b;
  cin >> b;
  if (b == 'A') cout << 'T' << endl;
  else if (b == 'T') cout << 'A' << endl;
  else if (b == 'C') cout << 'G' << endl;
  else if (b == 'G') cout << 'C' << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std; 
#define ll long long int
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>
#define INF LLONG_MAX
#define PI acos(-1)
#define MOD 1e9 + 7
#define N 1e5 + 10
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll a[5],k=0,i=0,j=0;
	for(i=0;i<5;i++)
	{
		cin>>a[i];
	}
	cin>>k;
	for(i=0;i<5;i++)
	{
		for(j=i+1;j<5;j++)
		{
			if((a[j]-a[i]) > k)
			{
				cout<<":(";
				return 0;
			}
		}
	}
	cout<<"Yay!";
}	

Measured memory_bytes: 256
import math
import copy
import sys


inputa = input().split()
# inputb = input().split()
# inputc = input().split()

a = int(inputa[0])
# b = int(inputa[1])
# c = int(inputa[2])

# x = int(inputb[0])
# y = int(inputb[1])

# inputaList = [int(n) for n in inputa]

inputb = input().split()
inputbList = [float(n) for n in inputb]
#
# inputList = []
# inputNumList = []
# for i in range(a):
#     inputNum = input()
#     inputNumList = list(inputNum)
#     inputList.append(inputNumList)

# inputList = [int(n) for n in inputList]

# b = [int(n) for n in inputb]
# c = [int(n) for n in inputc]

tmpSum = 0

for i in range(a):
    tmpSum += 1/inputbList[i]

print(1/tmpSum)



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

#define STRING(str) #str
#define ll long long

template <typename T >
void print_vec_1d(vector<T> x, string name) {
	cout << name << endl;
	cout << "[ ";
	for (int i=0;i<x.size();i++) {
		cout << x[i];
		if (i != x.size()-1) cout << ", ";
		else cout << " ]" << endl;
	}
}

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

	int N, M;
	cin >> N >> M;
	dsu d(N);
	for (int i=0;i<M;i++) {
		int A, B;
		cin >> A >> B;
		A--;
		B--;
		d.merge(A, B);
	}

	vector<bool> used(N, false);
	int ans = 0;
	for (int i=0;i<N;i++) {
		if (!used[d.leader(i)]) {
			used[d.leader(i)] = true;
			ans++;
		}
	}
	cout << ans-1 << "\n";
}

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

int main() {
  string s;
  cin >> s;
  for (int i = 0; i < s.size(); i = i + 1) {
    if (s.at(i) == '1') {
      cout << 9;
    } else {
      cout << 1;
    }
  }
}
    

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


int main(){
  int i,n;
  cin>>n;
  string order,word;
  unordered_set<string> d;
  for(i=0;i<n;i++){
    cin>>order>>word;
    if(order[0]=='i'){
      d.insert(word);
    }else{
      if(d.count(word)==0){
	printf("no\n");
      }else{
	printf("yes\n");
      }
    }
  }
}

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

int main(){
    int n;
    cin >> n;
    int A[n];
    for(int i=0;i<n;i++){
        cin >> A[i];
    }
    int ma=A[0];
    int mi =A[0];
    for(int i=0;i<n;i++){
        if(A[i]>ma) ma = A[i];
        if(A[i]<mi) mi = A[i];
    }
    int z;
    z = ma-mi;
    if(z>0)z=z;
    else z = -z;
    cout << z << endl;
}

Measured memory_bytes: 256
'use strict';

function main(stdin) {
  const input = stdin.split(' ').map(v => parseInt(v, 10));
  const A = input[0];
  const B = input[1];

  let ans = -1;

  if (A <= 9 && B <= 9) ans = A * B;

  console.log(ans);
}

main(require('fs').readFileSync('/dev/stdin', 'utf8').trim());

Measured memory_bytes: 21064
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        try (Scanner sc = new Scanner(System.in)) {
            while (sc.hasNext()) {
                String s = sc.nextLine();
                if(s.equals("xxx")){
                    System.out.println(700);
                }else if(s.equals("xxo") || s.equals("xox") || s.equals("oxx")){
                    System.out.println(800);
                }else if(s.equals("xoo") || s.equals("oxo") || s.equals("oox")){
                    System.out.println(900);
                }else{
                    System.out.println(1000);
                }
            }
        }
    }
}

Measured memory_bytes: 22740
//Author: kaiyu
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <numeric>
#include <iomanip>
#include <climits>
using namespace std;
typedef long long ll;
#define sz(x) ((long long)(x).size())
#define all(x)  x.begin(),x.end()
#define endl "\n"
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define pii pair<int,int>
#define tt ll t;cin >> t;while(t--)
#define int3(x,y,z) ll x,y,z;cin >> x >> y >> z;
#define int2(x,y) ll x,y;cin >> x >>y;
#define int1(x) ll x;cin>>x;
#define  fio ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
ll power(ll a,ll b,ll m=mod){ ll ans=1; a=a%m;  while(b>0) {  if(b&1)  ans=(1ll*a*ans)%m; b>>=1;a=(1ll*a*a)%m;}return ans;}

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


bool cmp(pair<string,int>p1,pair<string,int>p2) {
    return p1.ss > p2.ss;
}

int32_t main()
{
    fio
    int2(s,w);
    if(w>=s)cout << "unsafe" << endl;
    else cout << "safe" << endl;
    return 0;

};




Measured memory_bytes: 3596
#include <stdio.h>
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue> 
 
using namespace std;
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N;
 
	cin >> N;

	int base = 1;
 
	vector< vector<int> > K(9, vector<int>(9));

	for(int i = 1; i <= N; i++) {
		int x = i % 10;
		if(x == 0) continue;
		if(i >= base * 10) base *= 10;
		int y = i / base;
		K[x - 1][y - 1]++;
	}

	int count = 0;

	for(int i = 0; i < 9; i++) {
		for(int j = i; j < 9; j++) {
			if(i != j) {
				count += K[i][j] * K[j][i] * 2;
			} else {
				count += K[i][j] * K[i][j];
			}
		}
	}
/*
	for(int i = 0; i < 9; i++) {
		for(int j = 0; j < 9; j++) {
			cout << K[i][j] << " ";
		}
		cout << endl;
	}
*/
	cout << count << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>

using namespace std;

int crs(double x1, double y1, double x2, double y2) {
    double z = x1*y2-y1*x2;
    return (0 < z ? 1 : (z < 0 ? -1 : 0));
}

bool intersect(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) {
    if (0 <= crs(x2-x1, y2-y1, x3-x1, y3-y1) * crs(x2-x1, y2-y1, x4-x1, y4-y1)) return false;
    if (0 <= crs(x4-x3, y4-y3, x1-x3, y1-y3) * crs(x4-x3, y4-y3, x2-x3, y2-y3)) return false;
    return true;
}

pair<double,double> intersection(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) {
    if (x3 == x4) {
        swap(x1, x3); swap(y1, y3); swap(x2, x4); swap(y2, y4);
    }
    double x, y, a, b, c, d;
    if (x1 == x2) {
        c = (y4-y3)/(x4-x3);
        d = y3-c*x3;
        x = x1;
        y = c*x+d;
    } else {
        a = (y2-y1)/(x2-x1);
        b = y1-a*x1;
        c = (y4-y3)/(x4-x3);
        d = y3-c*x3;
        x = (d-b)/(a-c);
        y = a*x+b;
    }
    return make_pair(x,y);
}

int main() {
    int N;
    cin >> N;
    while (N--) {
        double xa, ya, xb, yb;
        int n;
        cin >> xa >> ya >> xb >> yb >> n;
        bool vertical = abs(xa-xb) < abs(ya-yb);

        double xs, ys, xt, yt;
        int o, l;
        vector<pair<double,int> > levels;
        for (int i=0; i<n; ++i) {
            cin >> xs >> ys >> xt >> yt >> o >> l;
            if (intersect(xa, ya, xb, yb, xs, ys, xt, yt)) {
                if (vertical) {
                    double y = intersection(xa, ya, xb, yb, xs, ys, xt, yt).second;
                    levels.push_back(make_pair(y, o==1 ? l : 1-l));
                } else {
                    double x = intersection(xa, ya, xb, yb, xs, ys, xt, yt).first;
                    levels.push_back(make_pair(x, o==1 ? l : 1-l));
                }
            }
        }

        sort(levels.begin(), levels.end());
        int res = 0;
        for (int i=1; i<(int)levels.size(); ++i) {
            if (levels[i].second != levels[i-1].second) {
                res ++;
            }
        }

        cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 1240
#include<bits/stdc++.h>
using namespace std;   
int main()  
{
	int A,B,C,sum5=0,sum7=0;
	cin>>A>>B>>C;
	if(A==5) sum5++;
	if(B==5) sum5++;
	if(C==5) sum5++;
	if(A==7) sum7++;	
	if(B==7) sum7++;
	if(C==7) sum7++;
	if(sum5==2&&sum7==1) cout<<"YES";
	else cout<<"NO"; 
    return 0;  
}  

Measured memory_bytes: 256
//---------- begin union_find ----------
#[allow(dead_code)]
mod union_find {
    pub struct UF {
        p: Vec<i32>,
    }
    impl UF {
        pub fn new(n: usize) -> UF {
            UF {p: vec![-1; n] }
        }
        pub fn init(&mut self) {
            for p in self.p.iter_mut() {
                *p = -1;
            }
        }
        pub fn root(&mut self, mut x: usize) -> usize {
            while self.p[x] >= 0 {
                x = self.p[x] as usize;
            }
            x
        }
        pub fn same(&mut self, x: usize, y: usize) -> bool {
            self.root(x) == self.root(y)
        }
        pub fn unite(&mut self, mut x: usize, mut y: usize) -> Option<(usize, usize)> {
            x = self.root(x);
            y = self.root(y);
            if x == y {
                return None;
            }
            if self.p[x] > self.p[y] {
                let s = x;
                x = y;
                y = s;
            }
            self.p[x] += self.p[y];
            self.p[y] = x as i32;
            Some((x, y))
        }
        pub fn get_size(&mut self, x: usize) -> usize {
            let r = self.root(x);
            (-self.p[r]) as usize
        }
    }
}
//---------- end union_find ----------

use std::io::Read;

fn run() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let n: usize = it.next().unwrap().parse().unwrap();
    let d: u64 = it.next().unwrap().parse().unwrap();
    let a: Vec<u64> = (0..n).map(|_| it.next().unwrap().parse().unwrap()).collect();
    let mut e = vec![];
    let mut stack = vec![(0, n)];
    while let Some((l, r)) = stack.pop() {
        if l + 1 == r {
            continue;
        }
        let m = (l + r) / 2;
        stack.push((l, m));
        stack.push((m, r));
        let mut local = (a[l], l);
        for i in (l + 1)..m {
            local.0 += d;
            if local.0 > a[i] {
                local = (a[i], i);
            }
        }
        for i in m..r {
            local.0 += d;
            e.push((local.1, i, local.0 + a[i]));
        }
        let mut local = (a[r - 1], r - 1);
        for i in (m..(r - 1)).rev() {
            local.0 += d;
            if local.0 > a[i] {
                local = (a[i], i);
            }
        }
        for i in (l..m).rev() {
            local.0 += d;
            e.push((i, local.1, local.0 + a[i]));
        }
    }
    e.sort_by_key(|e| e.2);
    let mut u = union_find::UF::new(n);
    let mut ans = 0;
    for (a, b, c) in e {
        if let Some(_) = u.unite(a, b) {
            ans += c;
        }
    }
    println!("{}", ans);
}

fn main() {
    run();
}


Measured memory_bytes: 134512
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#include<set>
#include<complex>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define CC puts("-------ok--------");
#define all(in) in.begin(), in.end()
#define bv vector<bool>
using namespace std;
typedef pair<int, int>PA;
using namespace std;
#define MAX 1000
int main(){
    int num;double taijuu;double sintyou;char g;
    vi v;
    while(cin>>num>>g>>taijuu>>g>>sintyou)if((double)taijuu/(sintyou*sintyou)>=25) v.push_back(num);
    rep(k,v.size())cout<<v[k]<<endl;
}

Measured memory_bytes: 3180
// include
// ------------------------------------------------
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

// func
// ------------------------------------------------
int CalcSumOfDigit(int n);      // 各桁の和を計算する。

// define
// ------------------------------------------------
#define all(a)        (a).begin(),(a).end()
#define pb            push_back
#define sz(a)         int((a).size())
#define rep(i,n)      for(int(i)=0;(i)<(n);(i)++)
#define repe(i,n)     for(int(i)=0;(i)<=(n);(i)++)
#define vsort(v)      sort((v).begin(),(v).end())

// code
// ------------------------------------------------
int main() {
  string s;
  cin >> s;
  
  vsort(s);
  
  if(s == "abc") cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

// funcの実体
// ------------------------------------------------
int CalcSumOfDigit(int n)
{
  int s = 0;
  while(n)
  {
    s += n % 10;
    n = n / 10;
  }
  return s;
}

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

int main()
{
  const int MAX_PRIME = 10000000+1;

  static bool p[MAX_PRIME];
  memset(p, true, sizeof(p));
  p[0] = p[1] = false;
  for (int i = 2; i*i <= MAX_PRIME; ++i) {
    if (p[i]) {
      for (int j = i+i; j < MAX_PRIME; j += i)
	p[j] = false;
    }
  }

  vector<int> prime;
  for (int i = 0; i < MAX_PRIME; ++i) {
    if (p[i])
      prime.push_back(i);
  }

  vector<int> ans;
  for (unsigned int i = 3; i < prime.size(); ++i) {
    if (prime[i-3]+8 == prime[i] &&
	prime[i-2]+6 == prime[i] &&
	prime[i-1]+2 == prime[i])
      ans.push_back(prime[i]);
  }

  int n;
  while (cin >> n) {
    if (n == 0)
      break;
    cout << *(upper_bound(ans.begin(), ans.end(), n)-1) << endl;
  }
  return 0;
}

Measured memory_bytes: 12000
#include<stdio.h>

static const int MAX = 500;
static const int INFTY = (1<<21);

int main(){
  int n, i, j, e, sum;
  int M[MAX][MAX];
  int d[MAX];
  int isA[MAX];
  int u;
  
  scanf("%d", &n);
  
  for ( i = 0; i< n; i++ ){
    for ( j = 0; j < n; j++ ){
      scanf("%d", &e);
      M[i][j] = (e==-1?INFTY:e);
    }    
    d[i]=INFTY;
    isA[i]=0;
  }
  
  d[0]=0;

  while(1){
    int u,v=INFTY;
    
    for(i=0;i<n;i++){
      if(isA[i]==1)continue;
      if(v>d[i]){
	v=d[i];
	u=i;
      }
    }

    if(v==INFTY)break;
    isA[u]=1;
    for(j=0;j<n;j++){
      if(isA[j]==1)continue;
      if(d[j]>=M[u][j]){
	d[j]=M[u][j];
      }
    }
  }  
  sum = 0;
  
  for ( u = 0; u < n; u++ ){
    sum += d[u];
  }
  
  printf("%d\n", sum);
  
  return 0;
}

Measured memory_bytes: 800
#include <iostream>
#include <math.h>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

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

typedef long long lint;

using namespace std;

int main(){
  string S,T;
  cin>>S>>T;
  int s[S.size()];
  int t[T.size()];
  map<char,int> m;
  int k=1;
  REP(i,S.size()){
    if(m[S[i]]==0){
      m[S[i]]=k;
      k++;
    }
    s[i]=m[S[i]];
  }
  k=1;
  m.clear();
  REP(i,T.size()){
    if(m[T[i]]==0){
      m[T[i]]=k;
      k++;
    }
    t[i]=m[T[i]];
  }
  // REP(i,S.size())cout<<s[i];
  // cout<<endl;
  // REP(i,S.size())cout<<t[i];
  // cout<<endl;
  bool f=true;
  REP(i,S.size())if(s[i]!=t[i])f=false;
  cout<<(f?"Yes":"No")<<endl; 
  return 0;
}


Measured memory_bytes: 2312
#include <stdio.h>
int main(void)
{
    int price[1001],change,memo,ans[1001]={0},Pt=0,i;
    while(1)
    {
        change=0;
        scanf("%d",&price[Pt]);
        if(price[Pt]==0)
            break;
        memo=1000-price[Pt];
        change+=memo/500;
        memo=memo%500;
        change+=memo/100;
        memo=memo%100;
        change+=memo/50;
        memo=memo%50;
        change+=memo/10;
        memo=memo%10;
        change+=memo/5;
        memo=memo%5;
        change+=memo;
        ans[Pt]=change;
        Pt++;
    }
    for(i=0;i<Pt;i++)
        printf("%d\n",ans[i]);
    return 0;
}

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

#define MP make_pair
#define PB push_back
#define ALL(x)      (x).begin(),(x).end()
#define REP(i,n)    for(int i=0;i<(n);i++)
#define REP1(i,n)   for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n)   for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};


void solve(long long r){
    cout << (r*r) << endl;
}

int main(){
    long long r;
    scanf("%lld",&r);
    solve(r);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int a[n],b[n],c[n];
  for(int i=0;i<n;i++)
  cin>>a[i]>>b[i]>>c[i];
  
  int dp[3][n];
  dp[0][0]=a[0];
  dp[1][0]=b[0];
  dp[2][0]=c[0];
  for(int i=1;i<n;i++)
  {
    dp[0][i]=max(dp[1][i-1],dp[2][i-1])+a[i];
    dp[1][i]=max(dp[0][i-1],dp[2][i-1])+b[i];
    dp[2][i]=max(dp[1][i-1],dp[0][i-1])+c[i];
  }
  cout<<max(dp[0][n-1],max(dp[1][n-1],dp[2][n-1]));
}

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

int main() {
  //cin.tie(nullptr);
  //ios_base::sync_with_stdio(false);
  
  int n;
  cin >> n;
  map<string, int> mp;
  rep(i, n) {
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    ++mp[s];
  }
  
  auto fac = [&](ll n) {
    ll res = 0;
    for(ll a = 1; a <= n-1; ++a) {
      res += a;
    }
    return res;
  };
  
  ll ans = 0;
  for(auto i = mp.begin(); i != mp.end(); ++i) {
    ans += fac(i->second);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 11296
#include <bits/stdc++.h>
#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 ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int a,b;
  cin >> a >> b;

  if(a%3==0 || b%3==0 || (a+b)%3==0) puts("Possible");
  else puts("Impossible");
  return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#include<stdio.h>
#include<functional>
#include<queue>

using ll = long long;

using namespace std;

ll mod = 1000000007;

ll n_pow(ll a, ll n) {
	if (n == 0)return 1;
	ll t = n_pow(a, n / 2);
	t *= t;
	t %= mod;
	if (n % 2 == 1)t *= a;
	return t % mod;
}

const int INF = 1001001001;
//const ll INF = 1e18;

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

ll cal_gcd(ll a, ll b) {
	ll m = max(a, b);
	ll n = min(a, b);
	while (m%n != 0) {
		ll b = m % n;
		m = n;
		n = b;
	}
	return n;
}

int main() {
	int n, k;
	cin >> n >> k;
	vector<bool>a(n, true);
	for (int i = 0; i < k; i++) {
		int d;
		cin >> d;
		for (int j = 0; j < d; j++) {
			int x;
			cin >> x;
			x--;
			if (a[x])a[x] = false;
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (a[i])ans++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <cstdio>
#include<algorithm>
#include <vector>
using namespace std;
vector<int >G;
long long cnt=0;
int A[1000000],n;
void insertionSort(int A[],int n,int g)
{
	int v,i,j;
      for( i = g ;i< n;i++)
	  {
         v = A[i];
          j = i - g;
          while (j >= 0 && A[j] > v)
		  {
              A[j+g] = A[j];
              j = j - g;
              cnt++;
		  }
          A[j+g] = v;
		  }
}
void shellSort(int A[],int  n)
{
	cnt=0;
	int h=1;
	while(h<=n)
	{
	G.push_back(h);
	h=3*h+1;
	}
   for(int i=G.size()-1;i>=0;i--)
	   insertionSort(A, n, G[i]);
}
int main()
{
cin>>n;
for(int  i=0;i<n;i++)
	scanf("%d",&A[i]);
shellSort(A,n);
printf("%d\n",G.size());
for(int i=G.size()-1;i>0;i--)
{
	printf("%d ",G[i]);

}
printf("%d\n",G[0]);
	cout<<cnt<<endl;
for(int i=0;i<n;i++)
	printf("%d\n",A[i]);
return 0;
}



Measured memory_bytes: 7084
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n = int(input())
#m,d = [int(i) for i in readline().split()]
#xy = [[int(i) for i in readline().split()] for i in range(n)]

ans = [[0]*n for i in range(n)]

L = list(range(n))
def iro(a,b,l): #[a:b],レベルl 以上
    if b-a <= 1: return 
    mid = a + (b-a)//2
    for i in L[a:mid]:
        for j in L[mid:b]:
            ans[i][j] = l
    iro(a,mid,l+1)
    iro(mid,b,l+1)



iro(0,n,1)

#print(*ans, sep="\n")
for i,ai in enumerate(ans[:-1]):
    print(*ai[i+1:])

Measured memory_bytes: 6000
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <map>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

struct Info{
	Info(int arg_budget,int arg_diff){
		budget = arg_budget;
		diff = arg_diff;
	}
	int budget,diff;
};

int dp[101][10001],next_dp[101][10001];

int main(){

	int N,C,min_cost;
	scanf("%d %d",&N,&C);

	for(int i = 0; i <= C; i++){
		for(int k = 0; k <= 10000;k++){
			dp[i][k] = -1;
			next_dp[i][k] = -1;
		}
	}

	int high_score,low_score,next_high_score,next_low_score,next_diff;

	int add_A,add_B,cost;

	dp[C][0] = 0;

	vector<Info> Updated;

	min_cost = C;
	int next_min_cost;

	for(int loop = 0; loop < N; loop++){

		scanf("%d %d %d",&add_A,&add_B,&cost);

		next_min_cost = min_cost;

		for(int budget = C; budget >= max(min_cost,cost); budget--){

			for(int diff = 0; diff <= 10000; diff++){
				if(dp[budget][diff] == -1)continue;

				low_score = dp[budget][diff];
				high_score = low_score+diff;

				next_high_score = high_score+add_A;
				next_low_score = low_score+add_B;
				next_diff = next_high_score-next_low_score;
				if(next_dp[budget-cost][next_diff] < next_low_score){
					next_dp[budget-cost][next_diff] = next_low_score;
					Updated.push_back(Info(budget-cost,next_diff));
					next_min_cost = min(next_min_cost,budget-cost);
				}

				next_high_score = high_score+add_B;
				next_low_score = low_score+add_A;
				next_diff = max(next_high_score,next_low_score)-min(next_high_score,next_low_score);
				if(next_dp[budget-cost][next_diff] < min(next_high_score,next_low_score)){
					next_dp[budget-cost][next_diff] = min(next_high_score,next_low_score);
					Updated.push_back(Info(budget-cost,next_diff));
					next_min_cost = min(next_min_cost,budget-cost);
				}
			}
		}

		min_cost = next_min_cost;

		for(int i = 0; i < Updated.size(); i++){
			dp[Updated[i].budget][Updated[i].diff] = next_dp[Updated[i].budget][Updated[i].diff];
		}
		Updated.clear();
	}

	int ans = 0;

	for(int i = 0; i <= C; i++){
		for(int k = 0; k <= 10000; k++){
			ans = max(ans,dp[i][k]);
		}
	}

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

	return 0;

}

Measured memory_bytes: 11744
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*n
        self.rank=[-1]*n

    def Find_Root(self,x):
        if self.root[x]<0:return x
        else:
            self.root[x]=self.Find_Root(self.root[x])
            return self.root[x]

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)

        if x==y:return
        elif self.rank[x]>self.rank[y]:
            self.root[x] +=self.root[y]
            self.root[y]=x
        else:
            self.root[y] +=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y] +=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

    def size(self,x):
        return -self.root[self.Find_Root(x)]

    def members(self,x):
        root=self.Find_Root(x)
        return [i for i in range(self.n) if self.Find_Root(i)==root]

    def roots(self):
        return[i for i,j in enumerate(self.root) if j<0]

    def group_members(self):
        return {i:self.members(i) for i in self.roots()}

    def group_count(self):
        return len(self.roots())


n,m,k=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]
CD=[list(map(int,input().split())) for _ in range(k)]

UnionFind=UnionFind(n+1)
Friend=[0 for _ in range(n+1)]
for a,b in AB:
    Friend[a] +=1
    Friend[b] +=1
    UnionFind.Unite(a,b)
Block=[0 for _ in range(n+1)]
for c,d in CD:
    if UnionFind.isSameGroup(c,d):
        Block[c] +=1
        Block[d] +=1

A=[]
for i in range(1,n+1):
    A.append(UnionFind.size(i)-Friend[i]-Block[i]-1)
print(*A)

Measured memory_bytes: 122072
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = pow(10, 9) + 7;
//const int MOD = 998244353;
//const int MOD = ;
int mod(int A, int M) {return (A % M + M) % M;}
const int INF = 1LL << 60;
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string abc = "abcdefghijklmnopqrstuvwxyz";
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;}
int divCeil(int A, int B) {return (A + (B - 1)) / B;}

vector<vector<int>> tree(100100);
vector<int> c;
vector<int> d(100100);
vector<bool> visited(100100, false);

int cnt = 0;
void dfs(int sear)
{
  if (visited.at(sear)) return;
  visited.at(sear) = true;
  d.at(sear) = c.at(cnt);
  cnt++;
  cerr << sear << endl;
  for (int i = 0; i < tree.at(sear).size(); i++)
  {
    dfs(tree.at(sear).at(i));
  }
  return;
}

signed main()
{
  int N;
  cin >> N;
  for (int i = 0; i < N - 1; i++)
  {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    tree.at(a).push_back(b);
    tree.at(b).push_back(a);
  }
  
  for (int i = 0; i < N; i++)
  {
    int _c;
    cin >> _c;
    c.push_back(_c);
  }
  
  sort(c.begin(), c.end(), greater<int>());
  //for (int i = 0; i < N; i++) cerr << c.at(i) << endl;
  dfs(0);

  int M = 0;
  for (int i = 1; i < N; i++)
  {
    M += c.at(i);
  }

  cout << M << endl;
  cout << d.at(0);
  for (int i = 1; i < N; i++)
  {
    cout << " " << d.at(i);
  }
  cout << endl;
}

Measured memory_bytes: 4480
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5+7;
int n,q;
string s;
int tree[4*MAXN][26];
void build(int idx, int l, int r){
    if(l==r){
        for(int i=0; i<26; i++)tree[idx][i] = 0;
        tree[idx][s[l]-'a'] = 1;
        return;
    }
    int fe = 2*idx;
    int fd = fe+1;
    int mid = (l+r)/2;
    build(fe, l, mid); build(fd, mid+1, r);
    for(int i=0; i<26; i++)
        tree[idx][i] = tree[fe][i] + tree[fd][i];
}
void upt(int idx, int l, int r, int qi, char nov){
    if(l==r){
        for(int i=0; i<26; i++)tree[idx][i] = 0;
        tree[idx][nov-'a'] = 1;
        return; 
    }
    int fe = 2*idx;
    int fd = fe+1;
    int mid = (l+r)/2;
    if(qi<=mid)
        upt(fe, l, mid, qi, nov);
    else
        upt(fd, mid+1, r, qi, nov);
    for(int i=0; i<26; i++)
        tree[idx][i] = tree[fe][i] + tree[fd][i];
}
int query(int idx, int l, int r, int qc, int ql, int qr){
    if(l>qr || r<ql)return 0;
    if(l>=ql && r<=qr)return tree[idx][qc];
    int fe = 2*idx;
    int fd = fe+1;
    int mid = (l+r)/2;
    return query(fe, l, mid, qc, ql, qr) + query(fd, mid+1, r, qc, ql, qr);
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>s>>q;
    build(1, 0, n-1);
    while(q--){
        int tp; cin>>tp;
        if(tp==1){
            int i; char ci;
            cin>>i>>ci;
            i--;
            upt(1, 0, n-1, i, ci);
        }else{
            int li,ri;
            cin>>li>>ri;
            li--; ri--;
            int ans = 0;
            char ci = 'a';
            for(int i=0; i<26; i++){
                //cout<<"BORA VER "<<ci<<endl;
                if(query(1, 0, n-1, i, li, ri) > 0){
                    //cout<<"tem "<<ci<<" no intervalo"<<endl;
                    ans++;
                }
                ci++;
            }
            cout<<ans<<endl;
        }
    }
}

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

using namespace std;

int main() {
    string S;

    cin >> S;

    if(S[0] != S[1] && S[0] != S[2] && S[1] != S[2]) {
        cout << "Yes" << endl;
        return 0;
    }

    cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;

using namespace std;
typedef pair<ll,ll> P;
ll F(ll q){
    ll s=0,cop=q;
    while(cop>0){
	s+=cop%10;
	cop/=10;
    }
    return s;
}
bool Mi(P a,P b){
    if(a.first*b.second>=b.first*a.second)return 1;
    return 0;
}
vector<P> v;
vector<ll> ans;
int main(){
    for(int i=1;i<10000;i++){
	v.push_back(make_pair(i,F(i)));
    }
    ll t=1000;
    while(t<=100000000000000){
	ll r=t-1;
	for(ll i=1;i<=9999;i++){
	    ll x=t*i+r;
	    ll f=F(x);
	    v.push_back(make_pair(x,f));
	    //cout<<x<<endl;
	}
	t*=10;
    }
    sort(v.begin(),v.end());
    P mini=make_pair((ll)mod*(ll)mod,1);
    for(int i=v.size()-1;i>=0;i--){
	if(mini==v[i])continue;
	if(Mi(mini,v[i])){
	    mini=v[i];
	    ans.push_back(v[i].first);
	}
    }
    //cout<<ans.size()<<endl;
    //cout<<ans[0]<<endl;
    ll k;cin>>k;
    lol(i,k){
	cout<<ans[ans.size()-1-i]<<endl;
    }
    return 0;
}


Measured memory_bytes: 2420
/* cerberus97 - Hanit Banga */

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int N = 1e5 + 10, A = 1e6 + 10, mod = 998244353;

ll ctr[A], f[A];

ll pwr(ll x, ll e);

int main() {
	fast_cin();
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) {
		int a; cin >> a;
		++ctr[a];
	}
	// mu[1] = 1;
	// for (int i = 1; i < A; ++i) {
	// 	for (int j = 2 * i; j < A; j += i) {
	// 		mu[j] -= mu[i];
	// 	}
	// }
	ll ans = 0;
	for (int g = A - 1; g >= 1; --g) {
		ll sum = 0, sq_sum = 0;
		for (ll d = g; d < A; d += g) {
			sum += d * ctr[d];
			sq_sum += d * d * ctr[d];
			sum %= mod; sq_sum %= mod;
		}
		f[g] = (sum * sum - sq_sum);
		f[g] %= mod;
		f[g] *= pwr(2, mod - 2);
		f[g] %= mod;
		for (int d = 2 * g; d < A; d += g) {
			f[g] -= f[d];
			f[g] += mod;
			f[g] %= mod;
		}
		ans += f[g] * pwr(g, mod - 2);
		ans %= mod;
	}
	ans += mod; ans %= mod;
	cout << ans << endl;
}

ll pwr(ll x, ll e) {
	ll res = 1;
	while (e) {
		if (e & 1) {
			res = (res * x) % mod;
		}
		x = (x * x) % mod;
		e /= 2;
	}
	return res;
}

Measured memory_bytes: 15872
N = int(input())
S = list(map(int, input().split()))
INF = float('inf')

S.sort()

parents = [S[-1]]
S[-1] = INF
checked = 1

for _ in range(N):
    checking = checked
    first = True
    parents.sort(reverse=True)
    for i in parents[:]:
        while True:
            if S[-checking] < i and first:
                parents.append(S[-checking])
                S[-checking] = INF
                checked = checking + 1
                break
            elif S[-checking] < i:
                parents.append(S[-checking])
                S[-checking] = INF
                break
            else:
                checking += 1
                first = False
            if checking == 2 ** N + 1:
                print('No')
                exit()
else:
    print('Yes')

Measured memory_bytes: 34676
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(ll i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

const int mod = 1000000007;
struct mint {
  ll x;  // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint& operator+=(const mint a) {
    if((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const { return mint(*this) += a; }
  mint operator-(const mint a) const { return mint(*this) -= a; }
  mint operator*(const mint a) const { return mint(*this) *= a; }
  mint pow(ll t) const {
    if(!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if(t & 1) a *= *this;
    return a;
  }
  // for prime mod
  mint inv() const { return pow(mod - 2); }
  mint& operator/=(const mint a) { return *this *= a.inv(); }
  mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }
mint fact(int n) {
  if(n == 1 || n == 0) return 1;
  mint res = n;
  return res * fact(n - 1);
}

struct combination {
  vector<mint> fact, ifact;
  combination(int n) : fact(n + 1), ifact(n + 1) {
    assert(n < mod);
    fact[0] = 1;
    for(int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
    ifact[n] = fact[n].inv();
    for(int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
  }
  mint operator()(int n, int k) {
    if(k < 0 || k > n) return 0;
    return fact[n] * ifact[k] * ifact[n - k];
  }
};

int main() {
  ll k;
  string s;
  cin >> k >> s;
  ll n = s.size();
  combination c(3e6);
  mint ans = 0;
  rep(i, k + 1) ans += c(i + n - 1, i) * mint(25).pow(i) * mint(26).pow(k - i);
  cout << ans << endl;
}

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

 ll gcd(ll a, ll b){
    ll tmp;
    if(a< b){
    tmp = a;
    a = b;
    b = tmp;
  }
    if(b==0) return a;
    else gcd(b, a%b);
  }
ll  lcm(ll a,ll b){
  return(a*b/(gcd(a,b)));
}
  
  
  
int main(){
  ll A, B, C, D, ans, cna=0, cnb=0;
  cin >> A >> B >> C >> D;
  cna = A-1;
  cna -= (A-1)/C;
  cna -= (A-1)/D;
  cna += (A-1)/lcm(C, D);
  cnb = B;
  cnb -= B/C;
  cnb -= B/D;
  cnb += B/lcm(C, D);
  ans = cnb - cna;
   cout << ans << endl;
 }

Measured memory_bytes: 256
#include <bits/stdc++.h>
# define ll int64_t
#define rep(i,n) for(ll i=0;i<n;i++)
#define rrep(i,n) for(ll i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define mod 1000000007

using namespace std;

bool compare_by_b(pair<string,ll> a,pair<string,ll> b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

bool my_compare(pair<string,ll> a,pair<string,ll> b){
    
    if(a.first != b.first) return a.first<b.first;
    if(a.second != b.second) return a.second>b.second;
    else return true;
}

int main(){
    vector<ll> a(3);
    rep(i,3) cin>>a[i];
    sort(ALL(a));
    ll sum=0;
    while(a[1]!=a[2]){
        a[0]++;
        a[1]++;
        sum++;
    }
    while(a[0]<a[1]){
        a[0] += 2;
        sum++;
    }
    if(a[0]>a[1]) sum++;
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 256
package main

/*
   N M
   a1 a2 a3 ... aN
*/
import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	stdin := bufio.NewScanner(os.Stdin)
	stdin.Scan()
	nm := strings.Split(stdin.Text(), " ")
	n, _ := strconv.Atoi(nm[0])
	m, _ := strconv.Atoi(nm[1])
	var is []int
	var days int = 0
	stdin.Scan()
	line := strings.Split(stdin.Text(), " ")
	if m == len(line) {
		is = make([]int, len(line))
		for i, v := range line {
			t, _ := strconv.Atoi(v)
			is[i] = t
			days += t
		}
	}
	if n-days>=0 {
	fmt.Println(n-days)
	} else {
	fmt.Println("-1")
	}
	
}


Measured memory_bytes: 2192
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int MaxN = 100;
typedef unsigned long long LL;
int n, p;
int a[MaxN + 5];

LL C(LL m, LL n){
	LL tot = 1;
	int p = 2;
	for(LL i = n - m + 1; i <= n; i++){
		tot = tot * i;
		while(tot % p == 0 && p <= m){
			tot /= p;
			p++;
		}
	}
	return tot;
}

int main(){
	while(~scanf("%d %d", &n, &p)){
		int cnt1 = 0, cnt0 = 0;
		for(int i = 1; i <= n; i++){
			scanf("%d", &a[i]);
			if(a[i] & 1) cnt1++;
			else cnt0++;
		}
		LL ans = 1;
		for(LL i = 1; i <= cnt0; i++) ans = ans * 2;
		LL num = 0;
		if(p & 1){
			for(int i = 1; i <= cnt1; i += 2) num += C(i, cnt1);
		}
		else{
			for(int i = 0; i <= cnt1; i += 2) num += C(i, cnt1);
		}
		ans *= num;
		if(cnt1 == 0 && p == 1) ans = 0;
		printf("%lld\n", ans);
	}
	return 0;
}

		


Measured memory_bytes: 128
n=int(input())
b=list(map(int,input().split())) #n-1
a=[0]*n
a[0]=b[0]
for i in range(1,len(b)):
    a[i] = min(b[i-1],b[i])
a[-1]=max(b[-1],a[-2])
# print(a)
print(sum(a))

Measured memory_bytes: 38256
#include <iostream>

using namespace std;

int main() {
  string str;
  getline(cin, str);
  for (unsigned int i = 0; i < str.size(); i++) {
    if ('a' <= str[i] && str[i] <= 'z') {
      str[i] -= 'a' - 'A';
    }
  }
  cout << str << endl;

  return 0;
}

Measured memory_bytes: 0