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

using namespace std;

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

#define cl cur<<1
#define cr (cur<<1)+1

const int maxn = 5e5 + 55;
const int inf = maxn*2e2;

struct seg_item
{
	int val, min;

	seg_item() {
		val = 0;
		min = inf;
	}
};

bool buf;
int n, k;
int a[maxn], inv[maxn], res[maxn];
seg_item seg[maxn << 2];

void upd(int sl, int sr, int ind, int cur) {
	if (sl == ind and ind == sr) {
		//cout << " 1upd: " << cur << ": " << sl << ":" << sr << " -> " << seg[cur].min << endl;
		seg[cur].min = seg[cur].val = a[ind];
		//cout << " 2upd: " << cur << ": " << sl << ":" << sr << " -> " << seg[cur].min << endl;
		return ;
	}

	int mid = (sl + sr) >> 1;
	if (mid < ind) {
		upd(mid+1, sr, ind, cr);
	} else {
		upd(sl, mid, ind, cl);
	}

	//cout << "1upd: " << cur << ": " << sl << ":" << sr << " -> " << seg[cur].min << endl;
	seg[cur].min = min(seg[cl].min, seg[cr].min);
	//cout << "2upd: " << cur << ": " << sl << ":" << sr << " -> " << seg[cur].min << endl;
}

int get_min(int sl, int sr, int l, int r, int cur) {
	if (r < l or r < sl or sr < l)
		return inf;
	if (l <= sl and sr <= r) {
		return seg[cur].min;
	}
	int mid = (sl + sr) >> 1;

	return min(get_min(mid+1, sr, l, r, cr),
		get_min(sl, mid, l, r, cl));
}

inline bool is_k_min(int ind) {

	//cout << "is_k_min: " << ind << endl;

	if (a[ind] == inf)
		return false;

	int l = max(1, ind-k+1);
	int r = min(n, ind+k-1);

	int mn = get_min(1, n, l, r, 1);
	//cout << "min: " << mn << endl;

	return (mn == a[ind]);
}

int main() {

	buf = scanf("%d %d", &n, &k);
	//cout << "mkay" << endl;
	for (int i = 1; i <= n; i++) {
		buf = scanf("%d", a+i);
		inv[a[i]] = i;
		upd(1, n, i, 1);
	}

	priority_queue<int, vector<int>, greater<int> > pq;

	for (int i = 1; i <= n; i++) {
		if (is_k_min(i)) {
			pq.emplace(i);
			//cout << i << " is added" << endl;
		}
	}

	int cnt = 1;
	while (!pq.empty()) {
		int ind = pq.top();
		pq.pop();
		if (a[ind] == inf)
			continue ;
		//cout << "accepted " << ind << endl;

		res[ind] = cnt;
		cnt ++;
		a[ind] = inf;
		upd(1, n, ind, 1);

		int lmin = get_min(1, n, max(1, ind-k+1), ind-1, 1);
		int rmin = get_min(1, n, ind+1, min(n, ind+k-1), 1);

		if (lmin != inf and is_k_min(inv[lmin])) {
			pq.emplace(inv[lmin]);
			//cout << inv[lmin] << " is added" << endl;
		}
		if (rmin != inf and is_k_min(inv[rmin])) {
			pq.emplace(inv[rmin]);
			//cout << inv[rmin] << " is added" << endl;
		}
	}

	for (int i = 1; i <= n; i++) {
		printf("%d ", res[i]);
	}
	putchar('\n');

	return 0;
}

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

#define range 524289
#define mod 1000000007
#define eps 1e-9
#define PI 3.14159265358979323846
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define ALL(V) V.begin(), V.end()
#define _ <<" "<<

using namespace std;

typedef  long long int ll;
typedef vector <ll> vi;
typedef vector<vi> vvi;
typedef pair <ll, ll> ii;
typedef pair<int, pair<int,int> > iii;
typedef vector<ii> vii;
typedef vector<iii> viii;


vvi a;
vvi dp;
int n;


ll res;

void dfs(int u, int p){
    dp[u][0] = 1;
    dp[u][1] = 1;

    for(int v: a[u]){
        if(v==p) continue;
        dfs(v, u);
        dp[u][0] = (dp[u][0]*1ll*(dp[v][0]+dp[v][1])%mod)%mod;
        dp[u][1] = (dp[u][1]*1ll*dp[v][0])%mod;
    }
    // cout<<u<<" "<<dp[u][0]<<" "<<dp[u][1]<<endl;
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	int t = 1;
	// cin>>t;
	while(t--){
        cin>>n;
        a = vvi(n+1);
        for (int i = 0; i < n-1; ++i)
        {
            int x, y;
            cin>>x>>y;
            a[x].pb(y);
            a[y].pb(x);
        }
        dp = vvi(n+1, vi(2, 0));
        dfs(1, -1);
        cout<<(dp[1][0]+dp[1][1])%mod<<endl;
	}

    return 0;
}


Measured memory_bytes: 18176
#include <bits/stdc++.h>
#include <cmath>
#include <limits>
#include <iostream>

using namespace std;

int main(){
  int N;
  
  cin >> N;
  
  uint64_t out = 1;
  uint64_t limval = pow(10.0, 18.0);
//   std::cout << limval << std::endl;
  vector<uint64_t> vec(N);
  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }
  
  std::sort(vec.begin(),vec.end());
  if(vec[0]==0){std::cout << 0 << std::endl;}
  else{
    bool isok = true;
    for (int i = 0; i < N; i++) {
    //   std::cout << vec[i] << std::endl;
    //  out = out * uint64_t(vec[i]);
    //  out  > limval / uint64_t(vec[i]);
      
    //   std::cout << out << std::endl;
      if( out > (limval / uint64_t(vec[i])) ){
        isok = false;
        break;
      }
      
      else{        
        out = out * uint64_t(vec[i]);
      }

    }

    if(isok==false){std::cout << "-1" << std::endl;}
    else{std::cout << out << std::endl;}
    
  }
  
}


Measured memory_bytes: 4008
n=int(input())
p=list(map(int,input().split()))

num = 0
for i in range(1,n-1):
  if p[i]>=p[i-1] and p[i+1]>=p[i]:
    num+=1
  elif p[i]>=p[i+1] and p[i-1]>=p[i]:
    num+=1
    
print(int(num))
  


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

using namespace std;

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int H, W;
  cin >> H >> W;
  vector<string> S(H);
  for (int i = 0; i < H; i++) {
    cin >> S[i];
  }
  vector<vector<int>> dp(H, vector<int>(W, 1 << 28));
  dp[0][0] = S[0][0] == '#' ? 1 : 0;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (i > 0)
        chmin(dp[i][j],
              dp[i - 1][j] + (S[i - 1][j] == '.' && S[i][j] == '#' ? 1 : 0));
      if (j > 0)
        chmin(dp[i][j],
              dp[i][j - 1] + (S[i][j - 1] == '.' && S[i][j] == '#' ? 1 : 0));
    }
  }
  cout << dp[H - 1][W - 1] << '\n';
  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int main(void) {
	int N;
	cin >> N;
	vector<int> a(N);
	map<int,int> counter;
	for (int i = 0; i < N; ++i) {
		cin >> a[i];
		++counter[a[i]];
	}
	sort(a.begin(),a.end());
	int res = 0;
	int num = a[0];
	for (int i = 0; i < N; i += counter[num]) {
		num = a[i];
		int count = 0;
		for (int j = i; a[j] < num+3 && j < N; ++j) {
			++count;
		}
		if (count > res) {
			res = count;
		}
	}
	cout << res << endl; 
	return 0;
}


Measured memory_bytes: 3584
n, m = map(int, input().split())
mod = 10**9 + 7
def kaijo(n):
    k = 1
    for i in range(1,n+1):
        k = (k*i) % mod
    return k
if abs(n - m) > 1:print(0)
elif n == m: print((kaijo(n) * kaijo(m) * 2) % mod)
else: print((kaijo(n) * kaijo(m)) % mod)

Measured memory_bytes: 3064
N = int(input())

N_1 = round(N/1.08//1)
N_2 = N_1 + 1


if N_1*1.08//1 == N:
    print(N_1)

elif N_2 * 1.08//1 == N:
    print(N_2)

else:
    print(":(")

Measured memory_bytes: 9228
#include <array>
#include <iostream>
#include <map>
#include <vector>

//! @brief Regard Map of {key, count} to record count of key, initialize with 0 if key not found, then add
//! adding to key's count.
template <typename Map, typename Value = typename Map::mapped_type>
Value &
MapAddCount(Map &map, typename Map::key_type key, Value adding)
{
    auto [it, flag] = map.try_emplace(key, 0);
    (void)flag;
    auto &count = it->second;
    count += adding;
    return count;
}

inline constexpr std::size_t BufferSize = 1024;

int
main()
{
    std::ios::sync_with_stdio(false);

    std::vector<int> bufferA;
    bufferA.resize(BufferSize, 0);
    std::vector<int> bufferB;
    bufferB.resize(BufferSize, 0);
    std::vector<int> bufferC;
    bufferC.resize(BufferSize, 0);

    std::vector<int> values;

    std::size_t valueCount;
    std::cin >> valueCount;

    auto usingValuesPtr = &bufferA;
    if (valueCount>BufferSize)
    {
        values.resize(valueCount);
        usingValuesPtr = &values;
    }
    auto &usingValues = *usingValuesPtr;

    for (std::size_t i = 0; i<valueCount; ++i)
    {
        std::cin >> usingValues[i];
    }

    std::size_t operationCount;
    std::cin >> operationCount;

    std::vector<int> oldValues;
    std::vector<int> newValues;

    auto usingOldValuesPtr = &bufferB;
    auto usingNewValuesPtr = &bufferC;
    if (operationCount>BufferSize)
    {
        oldValues.resize(operationCount);
        newValues.resize(operationCount);
        usingOldValuesPtr = &oldValues;
        usingNewValuesPtr = &newValues;
    }
    auto &usingOldValues = *usingOldValuesPtr;
    auto &usingNewValues = *usingNewValuesPtr;

    for (std::size_t i = 0; i<operationCount; ++i)
    {
        std::cin >> usingOldValues[i];
        std::cin >> usingNewValues[i];
    }

    long long sum = 0;
    std::map<int, int> valueCounts;
    for (auto &value : usingValues)
    {
        MapAddCount(valueCounts, value, 1);
        sum += value;
    }

    for (std::size_t i = 0; i<operationCount; ++i)
    {
        auto oldValue = usingOldValues[i];
        auto newValue = usingNewValues[i];

        auto count = MapAddCount(valueCounts, oldValue, 0);

        sum -= static_cast<long long>(oldValue)*count;
        sum += static_cast<long long>(newValue)*count;

        MapAddCount(valueCounts, newValue, count);
        valueCounts.erase(oldValue);
        std::cout << sum << "\n";
    }
}


Measured memory_bytes: 7440
#include<bits/stdc++.h>
using namespace std;
int main(){
	long long int h1,m1,h2,m2,k;
	cin>>h1>>m1>>h2>>m2>>k;
	cout<<max(h2*60+m2-h1*60-m1-k,(long long int)0)<<endl;
}

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

int main(){
        ll h, w;
        scanf("%lld %lld", &h, &w);

        std::vector<std::vector<ll>> links(10, std::vector<ll>(10));
        for(ll i=0; i<10; i++) for(ll j=0; j<10; j++) scanf("%lld", &links[i][j]);

        for(ll k=0; k<10; k++) for(ll i=0; i<10; i++) for(ll j=0; j<10; j++){
                links[i][j] = std::min(links[i][j], links[i][k]+links[k][j]);
        }

        ll ans = 0;
        for(ll i=0; i<h*w; i++){
                ll a;
                scanf("%lld", &a);
                if(a<0) continue;
                ans += links[a][1];
        }
        printf("%lld\n", ans);
        return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int A = sc.nextInt();
        int B = sc.nextInt();
        int T = sc.nextInt();
        int cnt = 0;

        cnt = T / A * B;

        System.out.println(cnt);
    }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
int main(){
  int H,W;
  cin >> H >> W;
  int C = 0;
  char A;
  for (int i = 0; i < H * W; i++){
    cin >> A;
    if (A == '#') C++;
  }
  cout << (C == H + W - 1 ? "Possible" : "Impossible");
}

Measured memory_bytes: 256
import sys
n = int(sys.stdin.readline().rstrip())
for i in range(n):
    out = score = 0
    runner = [0] * 3
    while out < 3:
        st = sys.stdin.readline().rstrip()
        if st == 'HIT':
            score += runner[2]
            runner = [1] + runner[:-1]
        elif st == 'HOMERUN':
            score += sum(runner) + 1
            runner = [0] * 3
        else:
            out += 1
    print(score)

Measured memory_bytes: 6224
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL << 60;
 
int main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> B(N);
    vector<int> C(N);
    vector<int> counting(500);
    int tmp = -1;
    int sum = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
 
    }
    for (int i = 0; i < N;i++)
    {
        cin >> B[i];
        sum += B[i];
    }
    for (int i = 0; i < N - 1;i++)
    {
        cin >> C[i];
    }
    for (int i = 0; i < N;i++)
    {
 
        if(tmp+1 == A[i]){
            sum += C[tmp-1];
        }
        tmp = A[i];
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
s = str(input())
'''
ans = 0
memo = 0

for i in range(len(s)):
    if s[i] != "A" and s[i] !="C" and s[i] != "G" and s[i] !="T":
        if i-memo > ans:
            ans = i-memo
        memo = i+1
        #print(memo, ans, i)

print(ans)



'''
ans = 0
memo = 0

for i in range(len(s)):
    if s[i] == "A" or s[i] =="C" or s[i] == "G" or s[i] =="T":
        memo += 1
    else:
        if ans < memo:
            ans = memo
            memo = 0
if ans < memo:
    ans = memo


print(ans)

Measured memory_bytes: 9004
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using vec=vector<ll>;
using mat=vector<vec>;
#define For(i,a,b) for(i=a;i<b;i++)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define mod 1000000007
using data=pair<ll,ll>;

long mmid(long a,long b,long c){return a<b?(b<c?b:max(a,c)):(b>c?b:min(a,c));}

ll modinv(ll a) {
  ll b=mod,u=1,v=0,t;
  while(b){
    t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  return (u+mod)%mod;
}

ll moddevide(ll a,ll b){return (a*modinv(b))%mod;}

ll modncr(ll n,ll r){
  ll i,plus=1;
  rep(i,r){
    plus=(plus*(n-i))%mod;
    plus=moddevide(plus,i+1);
  }
  return plus;
}

ll euclidean_gcd(ll a, ll b) {
  if(a<b) return euclidean_gcd(b, a);
  ll r;
  while ((r=a%b)){a=b;b=r;}
  return b;
}

ll countdigits(ll n){
  ll ans=0;
  while(n){n/=10;ans++;}
  return ans;
}

ll sumdigits(ll n){
  ll ans=0;
  while(n){ans+=n%10;n/=10;}
  return ans;
}

void printmap(vector<ll>& a,ll H,ll W){
  ll i,j;
  For(i,0,H+2){
    For(j,0,W+2){cout<<a[i*(W+2)+j];}
    cout<<endl;
  }
}
void inputmap(vector<ll>& a,ll H,ll W){
  ll i,j;
  string ss;
  For(i,1,H+1){
    cin>>ss;
    For(j,1,W+1){
      if(ss[j-1]=='#'){
        a[i*(W+2)+j]=1;
      }else{
        a[i*(W+2)+j]=0;
      }
    }
  }
}


int main(){
  ll i,j,N,M,K,dp[10][10]={0};
  string ss,tt;
  cin>>ss;
  tt="AKIHABARA";
  N=ss.size();
  K=9;
  if(ss.size()>K){cout<<"NO"<<endl;return 0;}
  i=j=0;
  while(i<N&&j<K+5){
    if(j>=K){cout<<"NO"<<endl;return 0;}
    if(ss[i]==tt[j]){
      i++;
      j++;
    }else if(tt[j]=='A'){
      j++;
    }else{
      cout<<"NO"<<endl;
      return 0;
    }
  }
  if(j==K||j==K-1){
    cout<<"YES"<<endl;
    return 0;
  }else{
    cout<<"NO"<<endl;
    return 0;
  }
  return 0;
}

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

# define REP(i,n) for (int i=0;i<(n);++i)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define p(s) std::cout << s ;
# define pl(s)  std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define yes(j) std::cout << (j ? "yes" : "no") << endl;
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){p(v[i]);p(" ")} pl("")
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;}
typedef long long int ll;
typedef pair<ll,ll> P_ii;
typedef pair<double,double> P_dd;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}

template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}


const int MOD = 1000000007;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;

void addM(long long &a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

void mulM(long long &a, long long b) {
    a = ((a%MOD)*(b%MOD))%MOD ;
}

// a^b mod M
long myPow(long a,long b,int M) {
    long ret = 1;
    long tmp = a;
    while(b>0) {
        if((b&1)==1) ret = (ret * tmp) % M;
        tmp = (tmp * tmp) % M;
        b = b>>1;
    }
    return ret;
}

 // nCk mod M
int nCk(int n,int k,int M) {
    long ret = 1;
    int mi = min(k, n-k);
    for(int i=1;i<=mi;i++) {
        ret = (ret * myPow(i,M-2,M)) % M;
    }
    for(int i=n-mi+1;i<=n;i++) {
        ret = (ret * i) % M;
    }
    return (int)ret;
};

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}


int main() {
    ll N,P;
    cin >> N >> P;

    auto pf = prime_factorize(P);

    ll ans = 1;
    for(auto p:pf) {        
        ll tmp = pow(p.first,p.second/N);
        if(tmp>0) ans *= tmp;
    }
    
    pl(ans)

    return 0;
}

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

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

    int N, M;
    cin >> N >> M;
    map<int, int> rems;
    int tmp;
    long long acc = 0;
    int rem;
    for (int i = 0; i < N; ++i) {
        cin >> tmp;
        acc += tmp;
        rem = static_cast<int>(acc % M);
        if (rems.find(rem) == rems.end()) {
            rems.insert(make_pair(rem, 0));
        }
        rems[rem]++;
    }
    
    long long total = 0;
    for (auto &r : rems) {
        int rem = r.first;
        long long count = r.second;
        total += (count - 1) * count / 2;
        if (rem == 0) total += count;
    }

    printf("%lld", total);

    return 0;
}


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

int n, q, l, r, c[500005], bit[500005], pos[500005], ans[500005];
vector<pair<int, pair<int, int>>> queries;

bool cmp(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
    return a.second.second < b.second.second;
}

void update(int x, int v) {
    for (int i = x; i <= n; i += (i & -i)) {
        bit[i] += v;
    }
}

int query(int x) {
    int sum = 0;
    for (int i = x; i >= 1; i -= (i & -i)) {
        sum += bit[i];
    }
    return sum;
}

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

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        pos[i] = -1;
    }

    for (int i = 1; i <= q; i++) {
        cin >> l >> r;
        queries.push_back({i, {l, r}});
    }

    sort(queries.begin(), queries.end(), cmp);
    int id = 0;
    for (int i = 1; i <= n; i++) {
        if (pos[c[i]] != -1) {
            update(pos[c[i]], -1);
        }

        pos[c[i]] = i;
        update(i, 1);
        while (id < queries.size() && queries[id].second.second == i) {
            ans[queries[id].first] = query(i) - query(queries[id].second.first - 1);
            id++;
        }
    }

    for (int i = 1; i <= q; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

Measured memory_bytes: 17504
a=input()
b=input()

flag=0

if len(b) < len(a) and flag==0:
  print('GREATER')
  flag=1
if len(b) > len(a) and flag==0:
  print('LESS')
  flag=1

  
if len(a)==len(b):  
  for i in range(len(a)):
    if b[i] < a[i] and flag==0:
      print('GREATER')
      flag=1
    elif b[i] > a[i] and flag==0:
      print('LESS')
      flag=1
    
if flag==0:
  print('EQUAL')
  

Measured memory_bytes: 3064
#include <string.h>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <sstream>
#include <iomanip>

using namespace std;
#define INF 1e9
#define MAX 100005
#define MOD 1000000007
#define Q queue
#define PQ priority_queue
#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define FOR( i, L, U ) for(int i=(int)L ; i<(int)U ; i++ )
#define FORD( i, U, L ) for(int i=(int)U ; i>=(int)L ; i-- )
#define wa cout<<"Wa"<<endl
#define READ(filename)  freopen(filename, "r", stdin);
#define WRITE(filename)  freopen(filename, "w", stdout);

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int> > vvi;
typedef map<int, int> mii;
typedef map<string, int> msi;
typedef map<int, string> mis;
typedef map<int , vector<int> > mvi;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;

void base(){
	 ios_base::sync_with_stdio(false);
	 cin.tie(NULL);
}

ll solve(int n,int m){
	if (n%3==0) return 0;
	ll mn = min(n,m);
	
	FOR(i,1,n){
		ll s1 = 1LL * i *m;
		ll s2 = 1LL * (n-i) * (m/2);
		ll s3 = 1LL * n * m - s1 -s2;
		mn = min(mn, max(s1,max(s2,s3)) - min(s1,min(s2,s3)));
	}
	return mn;
	
}


int main(){
//	base();
	ll w,h;
	cin>>h>>w;
	if (h%3==0 || w%3==0){
		cout<<0;
	}else {
		
		cout<<min(solve(h,w), solve(w,h))<<endl;
	}
	return 0;
}



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

int main()
{
  int n;
  cin>>n;
  bool f=false;
  for(int i=1;i<10;i++)
  {
    if(n%i==0)
    {
      if(n/i<10)
      {
        cout<<"Yes";
        f=true;
        break;
      }
    }
  }
  if(!f)
  cout<<"No";
}


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

using namespace std;

typedef long long ll;

const int INF = 1000000000;

int main()
{
  int N; scanf("%d", &N);
  vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    scanf("%d", &A[i]);
  }
  sort(A.begin(), A.end());
  int ans = A[N - 1] - A[0];
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PI acos(-1)
using namespace std;
int main () {
   double a,b,h,m,angle,res;
   cin>>a>>b>>h>>m;
   angle=abs(((11.0*m)/2.0)-(30.0*h));
   angle=min(angle,360.0-angle);
   res=sqrt((a*a)+(b*b)-(2.0*a*b*cos(angle * PI / 180.0)));
   printf("%0.20f\n",res);

   return(0);
}


Measured memory_bytes: 4212
#include<stdio.h>
#include<math.h>

int main(){
  int i=1;
  int N;
  
  scanf("%d",&N);
  
  while(1){
    if(i*i > N){
      printf("%d\n",(i-1)*(i-1));
      return 0;
    }
    i++;
  }
}


Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>

using namespace std;
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define reppe(i,a,b) for(int i = (int)(a) ; i <= (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)
#define repme(i,a,b) for(int i = (int)(a) ; i >= (int)(b) ; --i)

typedef long long ll;

long long GCD(long long a, long long b){if(b==0)return a;return GCD(b,a%b);}

int main() {
    int A, B; cin >> A >> B;
    cout << max(0, A - 2 * B) << endl;
}


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

#define ff first
#define ss second
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define w(x) int t; cin >> t; while(t--)
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define repd(i, b, a) for(int i = b; i >= a; i--)
#define mk(arr,n,type) type* arr = new type[n];
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define um unordered_map
#define us unordered_set
#define pqm priority_queue<int>
#define pqmi priority_queue<int, vi, greater<int>>
#define lb(v, val) lower_bound(v.begin(), v.end(), val) - v.begin();
#define ub(v, val) upper_bound(v.begin(), v.end(), val) - v.begin();
#define setbits(x) __builtin_popcountll(x)
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define out(flag) flag ? cout << "NO" << endl : cout << "YES" << endl;
#define MAX 100001
#define mod 998244353
#define inf 1e18
#define PI 3.1415926535

void IO() {
	fast;
}

int main() {

	IO();

	int n, w;
	cin >> n >> w;
	vector<ll> wt(n), val(n);
	ll summ = 0;
	for (ll i = 0; i < n; i++) {
		cin >> wt[i] >> val[i];
		summ += val[i];
	}
	vector<vector<ll>> dp(n + 1, vector<ll>(summ + 1, inf));
	for (int i = 0; i <= summ; i++) {
		dp[0][i] = inf;
	}
	for (int i = 0; i <= n; i++) {
		dp[i][0] = 0;
	}
	for (ll i = 1; i <= n; i++) {
		for (ll j = 1; j <= summ; j++) {
			dp[i][j] = dp[i - 1][j];
			if (val[i - 1] <= j) {
				dp[i][j] = min(dp[i][j], wt[i - 1] + dp[i - 1][j - val[i - 1]]);
			}
		}
	}
	ll maxi = 0;
	for (ll i = 0; i <= summ; i++) {
		if (dp[n][i] <= w) maxi = i;
	}
	cout << maxi << endl;

	return 0;
}


Measured memory_bytes: 80256
import java.util.Scanner;

class Main {
	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);
		int count = scanner.nextInt() - 2;//???????????°???????´????*???????????????2?????????
		int price = scanner.nextInt(); //????????????
		int changedPrice = scanner.nextInt(); //????????????????±???????
		int profit = changedPrice - price; //????????????????´????????????°

		if (changedPrice < price) {
			price = changedPrice;
		}

		for (int i = 0; i < count; i++) {
			changedPrice = scanner.nextInt();
			if (profit < (changedPrice - price)) {
				profit = changedPrice - price;
			}
			if (changedPrice < price) {
				price = changedPrice;
			}
		}
		System.out.println(profit);
	}
}

Measured memory_bytes: 98752
#include<bits/stdc++.h>
using namespace std;
long long n,k,i,MOD,fact[100005],a[100005],numbmin,numbmax,ans; 
long long power(int u,int v){
           if(v==1){
                      return u%MOD;
           }
           
           else if(v%2==0){
                      long long b=power(u,v/2);
                      return b*b%MOD;
           }
           else{
                      long long b=power(u,v-1);
                      return b*u%MOD;
           }
}
int main(){
           cin>>n>>k; MOD=1000000007;
           for(i=1;i<=n;i++)
           cin>>a[i];
           
           fact[1]=1;
           for(i=2;i<=n;i++){
                      fact[i]=fact[i-1]*i; 
                      fact[i]=fact[i]%MOD;
           }
           sort(a+1,a+n+1);
           for(i=1;i<=n;i++){
                      numbmin=0;
                      numbmax=0;
                      if(n-k+1>i){
                       numbmin=((fact[n-i]*power(fact[k-1],MOD-2))%MOD*power(fact[n-i-k+1],MOD-2))%MOD;
                       //cout<<i<<" "<<numbmin<<endl;
                      }
                      else if(n-k+1==i) numbmin=1;
                      if(i-k>0) numbmax=(fact[i-1]*power(fact[k-1],MOD-2))%MOD*power(fact[i-k],MOD-2)%MOD;
                      else if(i==k) numbmax=1;
                      //cout<<numbmin<<" "<<numbmax<<endl;
                      ans-=numbmin*a[i]%MOD;
                      ans+=numbmax*a[i]%MOD;
           }
           
           cout<<ans%MOD<<endl;
           
}

Measured memory_bytes: 1792
#include <iostream>
 
using namespace std;
 
using ll = long long;
 
int main(){
  ll N;
  cin >> N;
  bool ok = false;
  for(int i = 1; i < 10; ++i){
    if(N % i == 0 && N / i < 10){
      ok = true;
      break;
    }
  }
  if(ok){ cout << "Yes"; }
  else {cout << "No"; }
  cout << endl;
}

Measured memory_bytes: 256
n=int(input())
t=[int(a)*2 for a in input().split()]
v=[int(a)*2 for a in input().split()]
ma=[0]*(sum(t)+1)
a=0
for i in range(n):
  for j in range(t[i]):
    a+=1
    ma[a]=min(ma[a-1]+1,v[i])
ma[a]=0
for i in range(n)[::-1]:
  for j in range(t[i]):
    a-=1
    ma[a]=min(ma[a],ma[a+1]+1,v[i])
print((sum(ma[1:])+sum(ma[:-1]))/8)

Measured memory_bytes: 3700
//AOJ 0015

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

int main() {
	int n;
	cin >> n;
	for(int i = 0; i < n; i++) {
		string s1, s2;
		cin >> s1;
		cin >> s2;
		reverse(s1.begin(), s1.end());
		reverse(s2.begin(), s2.end());
		
		int max;
		int diff;
		if(s1.size() > s2.size()) {
			max = s1.size();
			diff = s1.size() - s2.size();
			for(int i = 0; i < diff; i++)
				s2 += "0";
		}
		else {
			max = s2.size();
			diff = s2.size() - s1.size();
			for(int i = 0; i < diff; i++) {
				s1 += "0";	
			}
		} 
		//cout << s1 << endl;
		//cout << s2 << endl;
		string s;
		int kuriagari = 0;
		for(int i = 0; i < max; i++) {
			int flag = true;
			if((s1[i]-'0')+(s2[i]-'0') + kuriagari >= 10) flag = false;
			s += ((s1[i]-'0')+(s2[i]-'0')+kuriagari) % 10 + '0';
			if(flag == true) kuriagari = 0;
			else kuriagari = 1;
		}
		if(kuriagari == 1) s += "1";
		reverse(s.begin(), s.end());
		if(s.size() > 80) cout << "overflow" << endl;
		else {
			cout << s << endl;
		}
	} 
	return 0;
}

Measured memory_bytes: 1212
#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    long long ans = 0;
    for(int i = 1;i<=n-1;i++){
	
	long long num = i;
	int divisorCount = 1;
	for ( long long i = 2; i *i <= num ; i ++) {
		int factorCount = 0;
		while ( num % i == 0) {
			factorCount ++;
			num /= i ;
		}
	divisorCount *= (1 + factorCount );
	}
	if ( num > 1) { // Sisa faktor
	divisorCount *= 2;

}
	ans += divisorCount;
}
cout<<ans<<endl;
}

Measured memory_bytes: 3648
import sys


N, A, B, C, D = map(int, input().split())

S = {i : s for i, s in enumerate(input(), 1)}

# D < C の場合に備えて3連続空白地帯があるかのフラグを立てる
# C, D の大小関係で場合分けした方が若干早いがコードが汚くなる
stay_B = False
if S[B-1] == '.':
  continuous_empty = 2
else:
  continuous_empty = 1

while B != D:
  if S[B+1] == '.':
    B += 1
    continuous_empty += 1
    if continuous_empty == 3:
      stay_B = True
  else:
    if S[B+2] == '.':
      B += 2
      continuous_empty = 1
    else:
      print("No")
      sys.exit()
    
# D < C のときはAがBを追い越さなくてはならないので3連続空白地帯が必要
if (D > C) or stay_B or (continuous_empty == 2 and S[D+1] == '.'):
  while A != C:
    if S[A+1] == '.':
      A += 1
    else:
      if S[A+2] == '.':
        A += 2
      else:
        print("No")
        sys.exit()

  print("Yes")
  
else:
  print("No")


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

int main(){
    long double a,b,h,m;
    cin>>a>>b>>h>>m;
    long double rad;
    long double ans;
    if(m==0){
        if(abs(h*30-m*6)>180)rad=(long double)((abs(h*30.0-m*6.0)-180.0))*(acos(-1)/180.0);
        else rad=(long double)(abs(h*30.0-m*6.0)*(acos(-1)/180.0));
    }
    else{
        if(abs(h*30+0.5*m-m*6)>180)rad=(long double)((abs(abs(h*30.0+0.5*m-m*6.0)-360.0)))*(acos(-1)/180.0);
        else rad=(long double)(abs(h*30.0+0.5*m-m*6.0)*(acos(-1)/180.0));
    }
    ans=(long double)(a*a+b*b)-(long double)(2.0*a*b)*cosl(rad);
    ans=sqrt(ans);
    printf("%.20Lf\n",ans);
    return 0;
}

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

using namespace std;

#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define cl(x,v) memset((x), (v), sizeof(x))
#define db(x) cerr << #x << " == " << x << endl
#define dbs(x) cerr << x << endl
#define _ << ", " <<

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<int, pii> piii;
typedef pair<ll,ll> pll;
typedef pair<ll, pll> plll;
typedef vector<int> vi;
typedef vector <vi> vii;

const ld EPS = 1e-9, PI = acos(-1.);
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f, MOD = 1e9+7;
const int N = 1e5+5;

int n;
map <pii,ll> m;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i=0;i<n;i++){
        double x;
        cin >> x;
        ll num = llround(x*1e9), cnt2 = 0, cnt5 = 0;
        while(!(num%2)){
            num/=2;
            cnt2++;
        }
        while(!(num%5)){
            num/=5;
            cnt5++;
        }
        m[{cnt2,cnt5}]++;
    }
    ll ans = 0;
    for(auto a: m){
        for(auto b: m){
            if(a.st.st + b.st.st >= 18 and a.st.nd + b.st.nd >= 18){
                if(a < b) ans += a.nd*b.nd;
                else if (a == b) ans += (a.nd*(b.nd - 1))/2;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 3784
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < int(n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
#define repeat_from_reverse(i,m,n) for (int i = (n)-1; (i) >= int(m); --(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;

int main() {
    int n, k; scanf("%d%d", &n, &k);
    vector<int> a(n); repeat (i, n) scanf("%d", &a[i]);
    vector<ll> d(n); repeat (i, n) d[i] = a[i] -(ll) k;
    vector<ll> acc(n+1); whole(partial_sum, d, acc.begin() + 1);
    ll result = 0;
    vector<ll> sorted, unsorted;
    int sqrt_n = sqrt(n) + 3;
    repeat (i, n+1) {
        result += whole(upper_bound, sorted, acc[i]) - sorted.begin();
        result += whole(count_if, unsorted, [&](ll x) { return x <= acc[i]; });
        unsorted.push_back(acc[i]);
        if (i % sqrt_n == 0) {
            whole(sort, unsorted);
            int size = sorted.size();
            sorted.insert(sorted.end(), unsorted.begin(), unsorted.end());
            inplace_merge(sorted.begin(), sorted.begin() + size, sorted.end());
            unsorted.clear();
        }
    }
    printf("%lld\n", result);
    return 0;
}


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

int main() {
  int n;
  float sum;
  cin >> n;

  for (int i=0;i<n;i++) {
    float kane;
    string str;

    cin >> kane >> str;
    if (str == "JPY") {
      sum += kane;
    } else {
      sum += kane * 380000;
    }
  }

  cout << sum << endl;
}

Measured memory_bytes: 256
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String S=sc.next();
        int[] A=new int[4];
        A[0]=Character.getNumericValue(S.charAt(0));
        A[1]=Character.getNumericValue(S.charAt(1));
        A[2]=Character.getNumericValue(S.charAt(2));
        A[3]=Character.getNumericValue(S.charAt(3));
        
        int ans=A[0];
        
        for(int i=0;i<(1<<3);i++){
            for(int j=0;j<3;j++){
                if((1&(i>>j))==1){
                    ans+=A[j+1];
                }else{
                    ans-=A[j+1];
                }
            }
            
            if(ans==7){
                System.out.print(A[0]);
                for(int j=0;j<3;j++){
                    if((1&(i>>j))==1){
                        System.out.print("+"+A[j+1]);
                    }else{
                        System.out.print("-"+A[j+1]);
                    }
                }
                System.out.println("=7");
                break;
            }
            
            ans=A[0];
        }
    }
}

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

int n;
string s[15];
double x[15] = {0.0};
double ans = 0;

int main() {
  cout << fixed << setprecision(10);
  cin >> n;
  for(int i = 0; i < n; ++i) cin >> x[i] >> s[i];
  for(int i = 0; i < n; ++i) {
    if(s[i] == "JPY")
      ans += x[i];
    else
      ans += 380000 * x[i];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <cstdlib>

using namespace std;

int n, m;
int data[100];
int mid, l, r;

bool check(){
   int w = 0;
   for(int i=0;i<m;i++){
      int sum = 0;
      for(;w<n;w++){
         if(sum + data[w] > mid) break;
         sum += data[w];
      }
      if(w>=n) break;
   }
   if(w >= n) return true;
   return false;
}

main(){
   while(cin >> m >> n && (n || m)){
      for(int i=0;i<n;i++){
         cin >> data[i];
      }
      l = 0;
      r = 1500000;
      while(abs(r-l) > 1){
         mid = (l+r)/2;
         if(check()){
            r = mid;
         }else{
            l = mid;
         }
      }
      cout << r << endl;
   }
   return 0;
}

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

using namespace std;
int main()
{
    int a, b, n[59], i;n[58]=0;
    scanf("%d%d",&a,&b);
    for(i=0;i<a;i++) scanf("%d",&n[i]);sort(n,n+a);
    for(i=a-1;i+1>a-b;i--) n[58]+=n[i];
    printf("%d\n",n[58]);
    return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
import cmath
from math import pi
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    a,b,h,m=map(int,input().split())
    h%=12
    m%=60
    H=cmath.rect(a,(h/12+m/720)*2*pi)
    M=cmath.rect(b,m/60*2*pi)
    print(abs(H-M))

if __name__ == '__main__':
    main()


Measured memory_bytes: 63080
#include <bits/stdc++.h>
using namespace std;
int ans;
bool use[10];
string s[10],t[10];

bool check(int n) {
  bool ck=true;
  for(int i=0; i<5; i++) {
    if(t[n][i]==t[i][n-5]) ck=false;
  }
  return ck;
}

void dfs(int n) {
  if(n==10) {
    ans++;
    return;
  }
  
  for(int i=0; i<10; i++) {
    if(!use[i]) {
      use[i]=true;
      
      t[n]=s[i];
      if(n<5) dfs(n+1);
      else {
	if(check(n)) {
	  dfs(n+1);
	  use[i]=false;
	  return;
	}
      }

      reverse(s[i].begin(),s[i].end());
      t[n]=s[i];
      reverse(s[i].begin(),s[i].end());
      
      if(s[i]==t[n]) {
	use[i]=false;
	continue;
      }
      
      if(n<5) dfs(n+1);
      else {
	if(check(n)) {
	  dfs(n+1);
	  use[i]=false;
	  return;
	}
      }
      
      use[i]=false;
    }
  }
}

int main() {
  while(cin >> s[0]) {
    if(s[0]=="END") break;
    for(int i=1; i<10; i++) cin >> s[i];
    memset(use,false,sizeof(use));
    ans=0;
    dfs(0);
    cout << ans/8 << endl;
  }
  return 0;
}


Measured memory_bytes: 1200
from collections import deque
import bisect
n,m,k = map(int, input().split())
a = [0]
b = [0]
a1 = list(map(int, input().split()))
b1 = list(map(int, input().split()))
# a1 = [1000000]*200000
# b1 = [1000000]*200000
ans = 0
a = a + a1
b = b + b1

for i in range(1,n+1):
    a[i]+=a[i-1]
for i in range(1,m+1):
    b[i]+=b[i-1]

for i in range(n+1):
    now = k-a[i]
    if now<0:
        break
    idx = bisect.bisect_right(b,now)
    ans = max(ans,idx-1+i)

print(ans)

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

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

using ll = long long int;
using P = pair<int, int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
using VB = vector<bool>;
using VVB = vector<VB>;

int main(){
  char U[3];
  scanf("%s",U,3);
  int ans = 0;
  REP(i,3) if(U[i] == '1') ans++;
  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 256
n=int(input())
s=list(input())

from itertools import groupby

gr=groupby(s)
#flg=0:白の状態
flg=0
black=[]
white=[]
for k,v in gr:
    if flg==0 and k=='#':
        flg=1
        black.append(len(list(v)))
    elif flg==1:
        if k=='#':
            black.append(len(list(v)))
        else:
            white.append(len(list(v)))
if len(black)==0 or len(white)==0:
    print(0)
    exit(0)




cnt=sum(white)
ans=[cnt]
for i in range(len(white)):
    cnt+=(black[i]-white[i])
    ans.append(cnt)

print(min(ans))





Measured memory_bytes: 15996
import java.util.*;

public class Main {
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		
		int[] mochiBucket = new int[101];
		
		int n = sc.nextInt();
		int dan = 0;
		for(int i=0; i<n; i++) {
			int num = sc.nextInt();
			mochiBucket[num]++;
			if(mochiBucket[num] == 1) {
				dan++;
			}
		}
		
		
		System.out.println(dan);
	}
}


Measured memory_bytes: 23124
#include <bits/stdc++.h>
using namespace std;
const int INF = (int)2e9 + 1;
const long long LINF = (long long)9e18 + 1;

int alphabet_int(char c)
{
	if ('a' <= c && c <= 'z')
	{
		return c - ('a');
	}
	return -1;
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	long long cnt = 1, S = 0;
	cin >> N;

	vector<string> s(N);
	for (int i = 0; i < N; i++)
	{
		cin >> s[i];
		sort(s[i].begin(), s[i].end());
	}
	sort(s.begin(), s.end());

	for (int i = 0; i < N; i++)
	{
		for (int j = 1; j < N - i; j++)
		{
			if (s[i] == s[i + j])
			{
				cnt++;
			}
			else
			{
				break;
			}
		}
		if (cnt != 1)
		{
			S += cnt * (cnt - 1) / 2;
			i = i + cnt - 1;
			cnt = 1;
		}
	}

	cout << S << endl;

	return 0;
}


Measured memory_bytes: 5760
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
#define LINF (long long)4e18
#define jck 3.141592

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;


int main(){
	string S; cin >> S;
	int N = S.size();
	if(N == 1){
    	cout << 1 << endl;
    	return 0;
    }
	vector<int> dp1(N+1,-N),dp2(N+1,-N);
	dp1[1] = 1;
	dp2[2] = 1;
	rep(i,N){
		if(i >= 1){
			if(S[i] != S[i-1]) dp1[i+1] = max(dp1[i+1],dp1[i]+1);
			dp2[i+2] = max(dp2[i+2],dp1[i]+1);
		}
		if(i >= 2){
			dp1[i+1] = max(dp1[i+1],dp2[i]+1);
			if(S[i] != S[i-2] || S[i+1] != S[i-1]){
				dp2[i+2] = max(dp2[i+2],dp2[i]+1);
			}
		}
	}
	cout << max(dp1[N],dp2[N]) << endl;

}



Measured memory_bytes: 2180
n = int(input())
A = list(map(int, input().split()))
m = A[0]
preMax = A[0]
ans = 0

for a in A:
    if preMax < a:
        preMax = a
        m = a 
    if a < m:
        ans += abs(a-m)
    preMax = max(a, preMax)
print(ans)


Measured memory_bytes: 32236
// Package main provides
//
// File:  main.go
// Author: ymiyamoto
//
// Created on Sat Aug 31 20:23:11 2019
//
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n int
	fmt.Scan(&n)

	arr := make([]float64, n)
	for i := range arr {
		fmt.Scan(&arr[i])
	}
	sort.Float64s(arr)

	ans := arr[0]
	for i := 1; i < n; i++ {
		ans = (ans + arr[i]) / 2
	}
	fmt.Println(ans)
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

const int N=2e5+5;

int n, idx=0;
int x[N], y[N];
set<pair<int, int> > reds, blues;

int get()
{
	int rmax=(--reds.end())->first;
	int rmin=reds.begin()->first;
	int bmax=(--blues.end())->first;
	int bmin=blues.begin()->first;
	return (rmax-rmin)*(bmax-bmin);
}

int work()
{
	for(int i=1;i<=n;i++)
	{
		if(x[i]>y[i])
			swap(x[i], y[i]);
		reds.insert({x[i], i});
		blues.insert({y[i], i});
	}
	int ans=1e18;
	for(int i=1;i<=2*n;i++)
	{
		ans=min(ans, get());
		int idx=reds.begin()->second;
		reds.erase({x[idx], idx});
		reds.insert({y[idx], idx});
		blues.erase({y[idx], idx});
		blues.insert({x[idx], idx});
		swap(x[idx], y[idx]);
	}
	return ans;
}

int32_t main()
{
	IOS;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>x[i]>>y[i];
	int answer=work();
	cout<<answer;
	return 0;
}


Measured memory_bytes: 28416
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+10;
int n,k,q[N],v[N];
vector<int> e[N];
bool is[N];
int root,Min0[N],Min1[N],dep[N];
void dfs(int x,int fa){
	if (is[x]){
		Min1[x]=(v[x]-v[root]+dep[x])/2;
		Min0[x]=dep[x]-Min1[x];
		if (v[root]+Min1[x]-Min0[x]!=v[x]) puts("No"),exit(0);
		if (Min0[x]<0||Min1[x]<0) puts("No"),exit(0);
	}
	else Min0[x]=Min1[x]=1e9;
	for (int i=0;i<e[x].size();i++){
		int v=e[x][i];
		if (v==fa) continue;
		dep[v]=dep[x]+1;
		dfs(v,x);
		Min0[x]=min(Min0[x],Min0[v]);
		Min1[x]=min(Min1[x],Min1[v]);
	}
}
int cnt0[N],cnt1[N];
void solve(int x,int fa){
	if (fa){
		cnt0[x]=cnt0[fa];
		cnt1[x]=cnt1[fa];
		if (Min0[x]>cnt0[x]) cnt0[x]++,v[x]=v[fa]-1;else
		if (Min1[x]>cnt1[x]) cnt1[x]++,v[x]=v[fa]+1;else
		puts("No"),exit(0);
	}
	for (int i=0;i<e[x].size();i++)
	if (e[x][i]!=fa) solve(e[x][i],x);
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	scanf("%d",&k);
	for (int i=1;i<=k;i++){
		scanf("%d",&q[i]);
		scanf("%d",&v[q[i]]);
		is[q[i]]=1;
	}
	root=q[1];dfs(root,0);solve(root,0);
	puts("Yes");
	for (int i=1;i<=n;i++) printf("%d\n",v[i]);
	return 0;
}

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

using namespace std;

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

const double pi = 3.14159265358979323846;

// #define fio() cin.tie(0); ios::sync_with_stdio(false);
// 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 (a>b) { a = b; return 1; } return 0; }
#define MOD 1000000007LL
#define PS(p) cout << setprecision(15) << fixed << p << endl;
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
#define ALL(c) c.begin(), c.end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define TG0 get< 0 >
#define TG1 get< 1 >
#define TG2 get< 2 >
#define F first
#define S second
#define VL vector< ll >

// to_string(123)
// atoi("123"); atoi(s.c_str());
// "abc".size()
// s.find('+') == string::npos
// 1e18

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

  ll N, M;
  cin >> N >> M;

  ll s[M], c[M];
  for (ll i = 0; i < M; i++) {
    cin >> s[i] >> c[i];
  }

  for (ll i = 0; i < 1000; i++) {
    string a = to_string(i);
    ll len = a.length();

    if (len != N) {
      continue;
    }

    bool ok = true;

    for (ll j = 0; j < M; j++) {
      if (c[j] + '0' != (a[s[j] - 1])) {
        ok = false;
        break;
      }
    }

    if (ok) {
      cout << a << endl;
      return 0;
    }
  }
  cout << -1 << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)
ll a[100001] = {};
ll s[100001] = {};
int main() {
	ll n, m; cin >> n >> m;
	map<ll, ll>mp;
	rep(i, 0, n) {
		cin >> a[i];
		s[i] = a[i];
	}
	rep(i, 1, n) {
		s[i] += s[i - 1];
	}
	rep(i, 0, n) {
		mp[s[i] % m]++;
	}

	ll ans = 0;
	for (map<ll, ll>::iterator it = mp.begin(); it != mp.end(); it++) {
		if (it->first == 0) {
			ans += it->second;
		}

		ll cnt = it->second;
		if (cnt >= 2) {
			ans += cnt * (cnt - 1) / 2;
		}
	}

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

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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

int n, a[100000];
pair<int, int> b[2][100001];

int main() {
	cin >> n;
	inc(i, n) { cin >> a[i]; }
	
	inc(i, n) {
		b[i % 2][a[i]].FI++;
		b[i % 2][a[i]].SE = a[i];
	}
	
	inc(k, 2) {
		   sort(b[k], b[k] + 100001);
		reverse(b[k], b[k] + 100001);
	}
	
	int ans = n;
	if(b[0][0].SE != b[1][0].SE) { setmin(ans, n - (b[0][0].FI + b[1][0].FI)); }
	if(b[0][1].SE != b[1][0].SE) { setmin(ans, n - (b[0][1].FI + b[1][0].FI)); }
	if(b[0][0].SE != b[1][1].SE) { setmin(ans, n - (b[0][0].FI + b[1][1].FI)); }
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 2176