akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;
int n,m[100][100],d[100];
void mins(){
    int u,min,color[100];
    for(int i=0;i<n;i++){
        d[i]=1000000000;
        color[i]=1;
    }
    d[0]=0;
    while(1){
        min=1000000000;
        u=-1;
        for(int i=0;i<n;i++){
            if(color[i]!=3&&d[i]<min){
                u=i;
                min=d[i];
            }
        }
        if(u==-1){
            break;
        }
        color[u]=3;
        for(int i=0;i<n;i++){
            if(m[u][i]!=-1){
                if(d[i]>min+m[u][i]){
                    d[i]=min+m[u][i];
                }
            }
        }
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            m[i][j]=-1;
        }
    }
    int a,k,c,v;
    for(int i=0;i<n;i++){
        cin>>a>>k;
        for(int j=0;j<k;j++){
            cin>>c>>v;
            m[a][c]=v;
        }
    }
    mins();
    for(int i=0;i<n;i++){
        cout<<i<<" "<<d[i]<<endl;
    }
    return 0;
}


Measured memory_bytes: 3124
num = int(input())
height = input().split()

sum = 0
max_height_now = 0
for index in range(num):
  height_now = int(height[index])
  if height_now >= max_height_now:
    max_height_now = height_now
  else:
    sum += max_height_now - height_now

print(sum)

Measured memory_bytes: 25048
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll A , B;
char b[500][500];
int main()
{
        cin >> A >> B;
        cout << "100 100\n";
        A--;
        B--;
        for(ll i = 1 ; i <= 50 ; i++)
        {
                for(ll j = 1 ; j <= 100 ; j++)
                {
                        if(B && (i&1) && (j&1)) {
                                B--;
                                b[i][j] = '#';
                        }else b[i][j] = '.';
                }
        }
        for(ll i = 50 ; i <= 100 ; i++)
        {
                for(ll j = 1 ; j <= 100 ; j++)
                {
                        if(A && (i&1) && (j&1)) {
                                A--;
                                b[i][j] = '.';
                        }else b[i][j] = '#';
                }
        }
        for(ll i = 1 ; i<= 100 ; i++){
                for(ll j = 1 ; j <= 100 ; j++) cout << b[i][j];
                cout << endl;
        }
        return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define faster  ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define ull unsigned long long
#define pb push_back
const double PI = acos(-1.0);
using namespace std;

int main()
{
    faster

    int n,c=0;
    string s;
    cin>>n>>s;

    char t;

    for(int i=0; i<n; i++)
    {
        if(i==0)
        {
            c++;
        }
        else if(s[i]!=t)
        {
            c++;
        }

        t=s[i];
    }

    cout<<c<<endl;




    return 0;
}


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

const int mxN=22;
int a[mxN],b[mxN],c[mxN];

int n,ans,x=-1;

int main(){
    cin>>n;
    for(int  i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    for(int i=1;i<n;i++){
        cin>>c[i];
    }
    for(int i=1;i<=n;i++){
        ans+=b[a[i]];
        //cout<<ans<<"\n";
        if(a[i]==x+1){
           //cout<<c[i]<<"\n";
            ans+=c[x];
            }
        x=a[i];

    }

    cout<<ans;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
#define ff first
#define ss second
#define int long long 
#define endl "\n"
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);	

const int inf = 1e9;
const int MOD = 998244353;
const int N = 1e5+4;

int n , x , m;
int a[N];
vector<int> adj[N] ;
bool vis[N];

void solve(){	
	cin >> n;
	for(int i=-2000 ; i<=2000 ; i++){
		for(int j = -2000 ; j<=2000 ; j++){
			if((pow(i,5) - pow(j,5)) == n ){
				cout << i << " " << j << endl;
				return;
			}
		}
	}

}

	
int32_t main(){
	FAST;
	int t=1;
	//cin>>t;
	while(t--)
		solve();
	return 0;
}	

Measured memory_bytes: 6496
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
	int n,k;
	char a[55];
	cin>>n>>k;
	scanf("%s",&a);
	if(a[k-1]=='A'){
		a[k-1]='a';
	}
	if(a[k-1]=='B'){
		a[k-1]='b';
	}
	if(a[k-1]=='C'){
		a[k-1]='c';
	}
	for(int i=0;i<n;i++){
		cout<<a[i];
	}
	return 0;
}

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

int main() {
  int N, tmp;
  cin >> N;
  int A[N];
  
  // DO NOT FORGET TO INITIALIZE ARRAY
  for(int i=0; i<N; i++) A[i]=0;
  
  for(int i=0; i<N-1; i++) {
    cin >> tmp;
    A[tmp-1]++;
  } 
  
  for(int i=0; i<N; i++) {
    printf("%d\n", A[i]);
  } 
  return 0;
}

Measured memory_bytes: 4476
//-----------------------
// author : xyqkoala
// time : 2020-09-20
//-----------------------

#include<iostream>
#include<vector>
#include<string>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<algorithm>
#include<cmath>
#include<numeric>
using namespace std;

typedef long long LL;
const int MOD = 1e9+7;

void solve();


int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T = 1;
	// cin>>T;
	while(T--){
		solve();
	}
	return 0;
}


void solve(){
	int n;
	cin>>n;
	LL res = 0;
	for(int i=1;i<n;i++){
		res+=(n-1)/i;
	}
	cout<<res<<endl;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  string N;
  cin>>N;
  for(int i=0;i<3;i++){
    if(N.at(i)=='1')N.at(i)='9';
    else if(N.at(i)=='9')N.at(i)='1';
  }
  cout<<N<<endl;
}

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

int main() {
  string N;
 cin >> N;
 
    
  if ((N[0] == N[1]) && ( N[1]==N[2])){
    cout << "Yes" << endl;
  }
  
   else if ((N[1] == N[2]) && (N[2] == N[3])){
     cout << "Yes" << endl;
   }
  else {
  cout << "No" << endl;  
}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string x;
    cin >> x;
    if(x=="A"){
        cout << "T" << endl;
    }
    if(x=="T"){
        cout << "A" << endl;
    }
    if(x=="G"){
        cout << "C" << endl;
    }
    if(x=="C"){
        cout << "G" << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define INF 2147483647
#define inf 1000000007
#define int long long
#define SYOU(x) setprecision(x)
#define abs(x,y) (max(x,y)-min(x,y))
#define mp make_pair
#define fi first
#define se second
using namespace std;
int i[111100];
bool ii[11111];
int u;
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long a,b,c,d=0,e=0,f=0,g=1,h=2,j;
  string s,w;
  cin >>a>>b;
  if(b==1) cout <<"0\n";
  else cout <<a-b<<'\n';
  return (0);
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

#define FOR(i,s,e) for (int i = int(s); i < int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

int SURP = 1000000007;

int c[3][3];

bool diffRowCheck(int i, int j){
	int d0 = c[i][0] - c[j][0];
	int d1 = c[i][1] - c[j][1];
	int d2 = c[i][2] - c[j][2];
	bool ret = false;
	if (d0 == d2 && d1 == d2) ret = true;
	return ret;
}

bool diffColCheck(int i, int j){
	int d0 = c[0][i] - c[0][j];
	int d1 = c[1][i] - c[1][j];
	int d2 = c[2][i] - c[2][j];
	bool ret = false;
	if (d0 == d2 && d1 == d2) ret = true;
	return ret;
}

int main(){
	FOR(i,0,3) cin >> c[i][0] >> c[i][1] >> c[i][2];

	bool check = true;

	check = check & diffRowCheck(0, 1);
	check = check & diffRowCheck(1, 2);
	check = check & diffRowCheck(0, 2);
	check = check & diffColCheck(0, 1);
	check = check & diffColCheck(1, 2);
	check = check & diffColCheck(0, 2);

	if (check) cout << "Yes" << endl;
	else  cout << "No" << endl;
	return 0;
}

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

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int main(){
	string s,t; cin>>s>>t;
	int n=s.length();

	vector<int> pos[128];
	rep(i,n) pos[s[i]].emplace_back(i);

	int cnt=0,idx=-1;
	for(char c:t){
		if(pos[c].empty()){ cout<<-1<<endl; return 0; }

		auto it=upper_bound(pos[c].begin(),pos[c].end(),idx);
		if(it!=pos[c].end()){
			idx=*it;
		}
		else{
			cnt++;
			idx=pos[c][0];
		}
	}
	cout<<(long long)n*cnt+idx+1<<endl;

	return 0;
}


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

using namespace std;
typedef pair<long long, long long> ii;

long long a[200001], b[200001], n;
bitset<200001> done;

int main() {
  long long num_op = 0;
  ios_base::sync_with_stdio(false);
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> b[i];
  }
  priority_queue<ii> pq;
  for (int i = 0; i < n; i++) {
    if (b[i] < a[i]) {
      cout << -1 << endl;
      return 0;
    }
    if (b[i] > a[i]) {
      pq.push(ii(b[i], i));
    } else {
      done[i] = 1;
    }
  }
  while (!pq.empty()) {
    ii fst = pq.top(); pq.pop();
    long long sec_val = 0;
    if (!pq.empty()) {
      ii scnd = pq.top();
      sec_val = scnd.first;
    }
    int i = fst.second;
    int i_min = (i + n - 1) % n;
    int i_add = (i + 1) % n;
    while (b[i] > a[i] && (b[i] > sec_val || (done[i_min] && done[i_add]) || (b[i] > b[i_min] && b[i] > b[i_add]))) {
      long long sub_fac = max(min((b[i] - a[i]) / (b[i_min] + b[i_add]), min((b[i] - b[i_min]) / (b[i_min] + b[i_add]), (b[i] - b[i_add]) / (b[i_min] + b[i_add]))), 1ll);
      if (done[i_min]) {
        sub_fac = max(sub_fac, min((b[i] - a[i]) / (b[i_min] + b[i_add]), (b[i] - b[i_add]) / (b[i_min] + b[i_add])));
      }
      if (done[i_add]) {
        sub_fac = max(sub_fac, min((b[i] - a[i]) / (b[i_min] + b[i_add]), (b[i] - b[i_min]) / (b[i_min] + b[i_add])));
      }
      if (done[i_min] && done[i_add]) {
        sub_fac = max(sub_fac, (b[i] - a[i]) / (b[i_min] + b[i_add]));
      }
      // if ((sub_fac < 1) || (sub_fac > 1 && ((b[i] - sub_fac * (b[i_min] + b[i_add]) < a[i]) || (b[i] - sub_fac * (b[i_min] + b[i_add]) < b[i_min] && !done[i_min]) || (b[i] - sub_fac * (b[i_min] + b[i_add]) < b[i_add] && !done[i_add])))) {
      //   cout << -1 << endl;
      //   return 12098012;
      // }
      if (b[i] - sub_fac * (b[i_min] + b[i_add]) < a[i]) {
        cout << -1 << endl;
        return 0;
      } else {
        b[i] -= sub_fac * (b[i_min] + b[i_add]);
        num_op += sub_fac;
      }
    }
    if (b[i] > a[i]) {
      pq.push(ii(b[i], i));
    } else {
      done[i] = 1;
    }
  }
  cout << num_op << endl;
  return 0;
}

Measured memory_bytes: 9584
#include<bits/stdc++.h>
using namespace std;
#define ll long long int

ll K,N;
ll m = 0;

int main(){
	cin>>K>>N;
	vector<ll> A(N);
	for(int i=0;i<N;i++)
		cin>>A.at(i);

	for(int i=0;i<N-1;i++){
		m = max(m,A.at(i+1)-A.at(i));
	}
	m = max(m,A.at(0)-A.at(N-1)+K);
	cout<<K-m<<endl;

}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main() {
	int n;
	cin >> n;
	vector<int> t(n);
	vector<string> s(n);
	rep(i, n){
		cin >> s[i] >> t[i];
	}
	string x;
	cin >> x;
	int ans = 0;
	bool sleep = false; 
	rep(i, n){
		if(sleep) ans += t[i];
		if(x == s[i]) sleep = true;
	}
	cout << ans << endl;
	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 c = sc.nextInt();
if(a<b){
    if(b < c){
                 System.out.printf("%d %d %d\n",a,b,c );
              }  
    else{if(a>c){
                 System.out.printf("%d %d %d\n",c,a,b);
                 } 
         else{
                 System.out.printf("%d %d %d\n",a,c,b);
              }
        }
        }   
else{
    if(a < c){
                  System.out.printf("%d %d %d\n",b,a,c );
              } 
     else{if(b>c){
                  System.out.printf("%d %d %d\n",c,b,a);
                  } 
        else{
                  System.out.printf("%d %d %d\n",b,c,a);
             }
         }
     }
}
}






Measured memory_bytes: 26220
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
using ll = long long;
using ld = long double;
#define vl vector<long long>
#define vvl vector<vector<long long>>
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
using pll = pair<long long,long long>;
#define cY cout<<"Yes"<<endl
#define cN cout<<"No"<<endl
const long long INF = 1LL << 60;
const long long MOD = 1000000007;
const long double pi = (acos(-1));
#define pb push_back
#define vs vector<string>

//最大最小の入れ替え
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;
}

//約数列挙
vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    sort(ret.begin(), ret.end()); // 昇順に並べる
    return ret;
}
//コンビネーション
ll nCr(ll n, ll r) {
    ll ans = 1;
    for (ll i = n; i > n - r; --i) {
        ans = ans*i;
    }
    for (ll i = 1 ; i < r + 1; ++i) {
        ans = ans / i;
    }
    return ans;
}
//素因数分解
map< ll, ll > prime_factor(ll n) {
  map< ll, ll > ret;
  for(ll i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

//切り上げの割り算は(a + b - 1) / bでできる

//ここから
int main(){
    string S;
    cin>>S;
    ll count=0;
    {
        char before='1';
        rep(i,S.size()){
            if(S[i]!=before){
                count++;
                before=S[i];
            }else{
                if(i==S.size()-1) break;
                else{
                    before='1';
                    i++;
                    count++;
                }
            }
        }
    }
    cout<<count<<endl;
}

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

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

const int N = 13;
const int M = 1001;
int n, m, a, b, c;
ii p[M];
int dp[1 << N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> a >> b;
        int mask = 0;
        for (int j = 0; j < b; ++j) {
            cin >> c;
            mask |= (1 << (c - 1));
        }
        p[i] = {a, mask};
    }
    memset(dp, 255, sizeof dp);
    dp[0] = 0;

    for (int ms = 0; ms < (1 << n) - 1; ++ms) {
        if (dp[ms] != -1) {
            for (int i = 0; i < m; ++i) {
                auto pa = p[i];
                int cost = pa.first;
                int mm = pa.second;
                int nm = mm | ms;
                if (dp[nm] == -1 || dp[nm] > dp[ms] + cost) {
                    dp[nm] = dp[ms] + cost;
                }
            }
        }
    }

    if (dp[(1 << n) - 1] == -1) {
        cout << -1 << endl;
    } else {
        cout << dp[(1 << n) - 1] << endl;
    }

    return 0;
}



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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

string s[]={"sun","mon","tue","wed","thu","fri","sat"};

signed main(){
    int x;cin>>x;
    int k=(6+x-9+7*114514)%7;
    cout<<s[k]<<endl;
    return 0;
}

Measured memory_bytes: 3148
#include <stdio.h>
#include <stdlib.h>

#if 1
#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)
#else
#define gc() getchar()
#define pc(c) putchar(c)
#endif
int in()
{
	int n = 0, c = gc();
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

void out(int n)
{
	int i;
	char ob[20];

	if (!n) { pc('0'); return; }
	i = 0; while (n) ob[i++] = n%10 + '0', n/=10;
	while (i--) pc(ob[i]); 
}

void sout(char *s) { while (*s) pc(*s++); }

typedef struct { int parent; int depth; int k; int *c; } TREE;
TREE tbl[100002];

void calc_depth(int node, int d)
{
	int i;
	tbl[node].depth = d;
	for (i = 0; i < tbl[node].k; i++) calc_depth(tbl[node].c[i], d+1);
}

int main()
{
	int n, i, j, k, id;
	int root;

	n = in();
	for (i = 0; i < n; i++) {
		id = in(), tbl[id].k = k = in();
		tbl[id].c = malloc(k << 2);
		for (j = 0; j < k; j++) {
			int _c = in();
			tbl[_c].parent = id+1;
			tbl[id].c[j] = _c;
		}
	}
	for (root = 0; root < n; root++) {
		if (tbl[root].parent == 0) break;
	}
	calc_depth(root, 0);

	for (i = 0; i < n; i++) {
		sout("node "), out(i);
		sout(": parent = ");
		if (i == root) sout("-1");
		else out(tbl[i].parent - 1);
		sout(", depth = "), out(tbl[i].depth);
		sout(", ");
		if (i == root)          sout("root");
		else if (tbl[i].k == 0) sout("leaf");
		else                    sout("internal node");
		sout(", [");
		if (tbl[i].k > 0) {
			out(tbl[i].c[0]);
			for (j = 1; j < tbl[i].k; j++) {
				pc(','), pc(' '), out(tbl[i].c[j]);
			}
		}
		sout("]\n");
	}
	return 0;
}


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

int main(){
  int a, b;

  cin >> a >> b;

  if(a<b){
    cout << "a < b" << endl;
  }else if(a>b){
    cout << "a > b" << endl;
  }else{
    cout << "a == b" << endl;
  }
  
  return 0;
}

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
constexpr LL MOD = 998244353;
class Solution {
  LL solve(LL A, LL B, LL C) {
    LL ans = 0;
    if (C < A + B + 1) return B + C;
    --C, ++ans;
    LL toMinus = min(B, C);
    ans += 2 * toMinus;
    B -= toMinus;
    C -= toMinus;
    toMinus = min(A, C);
    A -= toMinus;
    C -= toMinus;
    ans += toMinus;
    return ans;
  }
public:
  void run(istream &in, ostream &out) {
    LL A, B, C;
    in >> A >> B >> C;
    out << solve(A, B, C) << '\n';
  }
};

int main() { 
  ios_base::sync_with_stdio(false); cin.tie(0);
  Solution().run(cin, cout);
  return 0;
}


Measured memory_bytes: 256
// This file is a "Hello, world!" in C++ language by GCC for wandbox.
#include <iostream>
#include <cstdlib>
#include <bits/stdc++.h>
#include<algorithm>
using namespace std;
vector<bool> seen;
int dfs(const vector<vector<int>> &G, int v) {
    int size=1,p=0;
    seen[v] = true; // v を訪問済にする

    // v から行ける各頂点 next_v について
    for (auto next_v : G[v]) { 
        if (seen[next_v]) continue; // next_v が探索済だったらスルー
       // dfs(G, next_v); // 再帰的に探索
        p=dfs(G,next_v);
        size+=p;
    }
    return size;
}
int main(){
    int n,i,j,m,ans=0;
    int a[200010],b[200010];
    cin >> n >> m;
    vector<vector<int>> group(n);
    seen.assign(n,false);
    for(i=0;i<m;i++)
    {
        cin >> a[i] >> b[i];
        a[i]-=1;
        b[i]-=1;
        group.at(a[i]).push_back(b[i]);
        group.at(b[i]).push_back(a[i]);
    }
    for(i=0;i<n;i++)
    {
        if(seen[i]==false)
        {
            //ans=dfs(group,i);
            ans=max(ans,dfs(group,i));
        }
    }
    cout << ans << endl;
    

    

}


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

using namespace std;


vector<pair<long long, long long> > prime_factorize(long long N) {
  vector<pair<long long, long long> > res;
  for (long long a = 2; a * a <= N; ++a) {
    if (N % a != 0) continue;
    long long ex = 0; // 指数

    // 割れる限り割り続ける
    while (N % a == 0) {
      ++ex;
      N /= a;
    }

    // その結果を push
    res.push_back({a, ex});
  }

  // 最後に残った数について
  if (N != 1) res.push_back({N, 1});
  return res;
}

long long fastpow(long long a, long long n){
  long long ans = 1;
  while(n > 0){
    if(n & 1){
      ans *= a;
    }
    a *= a;
    n = n >> 1;
  }
  return ans;
}


int main(){
  long long n;
  cin >> n;
  cin.ignore();

  vector<pair<long long, long long>> prime_fact = prime_factorize(n);
  queue<pair<long long, long long>> prime_fact_extra;

  vector<long long> extra;

  vector <long long> already;

  long long cnt = 0;
  long long rem = 1;
  long double sqrt_n = sqrt(n);
  for(int i = 0; i < prime_fact.size(); i++){
    //printf("e = %lld p = %lld\n", prime_fact[i].first, prime_fact[i].second);
    long long p = prime_fact[i].second;
    long double sqrt_p = sqrt(2 * p);
    // n(n+1)/2 <= Aとなるnを探る
    long long n_p = sqrt_p + 1;
    while(p < (n_p * (n_p + 1)) / 2){
      --n_p;
    }
    cnt += n_p;
  }

  cout << cnt << endl;
  
  return 0;
}
  


Measured memory_bytes: 3700
#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
// using namespace atcoder;
typedef long long ll;
/* clang-format off */
#define MOD 1000000007
#define INF 1000000000000000000ll
#define REP(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(a) (a).begin(), (a).end()
//#define __DEBUG__
#ifdef __DEBUG__
#define CH_P(a) cout <<"check_point("<<#a<<")" << "\n";
#define DEBUG(x) cout<<#x<<":"<<x<<"\n"
#define DEBUGS(v) cout << #v << ":";for(auto x:v){cout<<x<<" ";}cout<<"\n"
#endif
#ifndef __DEBUG__
#define CH_P(a) 
#define DEBUG(x) 
#define DEBUGS(v) 
#endif
/* clang-format on */

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int a, b, k;
  cin >> a >> b >> k;
  int cnt = 0;
  for (int i = min(a, b); i >= 1; i--) {
    if (a % i == 0 && b % i == 0) {
      cnt++;
      if (cnt == k) {
        cout << i << endl;
        return 0;
      }
    }
  }
  return 0;
}


Measured memory_bytes: 3660
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define inf (int)(1e9+7)
#define abs(x) (x >= 0 ? x : -(x))
#define ceil(a, b) a / b + !!(a % b)
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }






int main() {
    int n;
    cin >> n;
    
    vector<pii> a;
    vector<int> sink(n);
    
    int cnt = 0;
    rep(i, n) {
        int tmp;
        cin >> tmp;
        if (sz(a) == 0 || tmp != a.back().F) { a.eb(pii(tmp, cnt++)); }
    }
    n = sz(a);
    sort(all(a));
    if (a[n - 1].F == 0) { cout << 0 << endl; return 0; }
    // rep(i, n) cout << a[i].F << " " << a[i].S << endl;
    
    int ans = 1; // x = 0
    int tmp = 1;
    
    rep(i, n) { // 海面の高さはaから
        rep3(j, i, n) { // 同じ高さのすべて見る
            if (a[j].F > a[i].F) { i = j - 1; break; }
            
            sink[a[j].S] = 1;
            
            // 両隣が沈んでたら減る
            // 両隣が生きてたら増える
            if (a[j].S == 0) {
                if (sink[a[j].S + 1] == 1) {
                    tmp--;
                    
                }
                continue;
            } else if (a[j].S == n - 1) {
                if (sink[a[j].S - 1] == 1) {
                    tmp--;
                    
                }
                continue;
            }
            
            if (sink[a[j].S - 1] == 1 && sink[a[j].S + 1] == 1) {
                tmp--;
            }
            else if (sink[a[j].S - 1] == 0 && sink[a[j].S + 1] == 0) {
                
                tmp++;
            }
        }
        // rep(_, n) cout << sink[_] << " "; cout << endl;
        chmax(ans, tmp);
        // cout << ans << endl;
    }
    
    
    cout << ans << endl;
}






Measured memory_bytes: 4280
#include<stdio.h>
int main(void)
{
	int h1,h2,k1,k2,a,b,c,d,x,y;
	scanf("%d %d",&h1,&h2);
	scanf("%d %d",&k1,&k2);
	scanf("%d %d %d %d",&a,&b,&c,&d);
	x=h1*a+h2*b;
	y=k1*a+k2*b;
	if(h1>=10||k1>=10){
		x=x+h1/10*c;
		y=y+k1/10*c;
	}
	if(h2>=20||k2>=20){
		x=x+h2/20*d;
		y=y+k2/20*d;
	}
	if(x>y){
		printf("hiroshi\n");
	}
	else if(y>x){
		printf("kenjiro\n");
	}
	else if(x==y){
		printf("even\n");
	}
	return 0;
}


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

int main(){
    int N; cin >> N;
    vector<long long> A;
    for(int i=0;i<N;i++){
        int a;
        cin >> a;
        A.push_back(a);
    }

    vector<long long> B;
    for(int i=0; i<N; i++){B.push_back(A[i]-i);}

    sort(B.begin(),B.end());

    long long ans = 0;
    int idx = N/2;
    for(int i=0; i<N; i++){
        ans += abs(B[i] - B[idx]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 4848
#include <algorithm>
#include <bits/stdc++.h>
#include <bitset>
#include <cassert>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
#define REP(i, n) for (int64_t i = 0; i < (int64_t)n; i++)
#define REP_FOR(i, a, b) for (int64_t i = (int64_t)a; i < (int64_t)b; i++)
#define REP_REV(i, a, b) for (int64_t i = (int64_t)a; i > (int64_t)b; i--)
#define FORALL(v) (v).begin(), (v).end()
#define mp(a, b) make_pair(a, b)
#define eb(x) emplace_back(x)
#define F first
#define S second
typedef long long ll;
typedef long double ld;
typedef pair<int64_t, int64_t> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int64_t> vii;
typedef vector<vii> vvii;
const ll mod = 1e9 + 7;
const int64_t infi = 1147483600;
const ll infl = 4e18 + 5;
const char EOL = '\n';
//cout << fixed << setprecision(17) << res << endl;
const ll MOD = 1000000007;

int main() {
    ll n, p;
    cin >> n >> p;
    string s;
    cin >> s;

    if (p == 2 || p == 5) {
        ll res = 0;
        for (ll i = 0; i < n; ++i) {
            if ((s[n-1-i]-'0') % p == 0) {
                res += n - i;
            }
        }
        cout << res << endl;
        return 0;
    }

    vector<ll> v(p, 0);
    ll cur = 0;
    v[cur]++;
    ll tens = 1;
    for (ll i = 0; i < n; ++i) {
        cur = (cur + (s[n-1-i]-'0') * tens) % p;
        tens *= 10;
        tens %= p;
        v[cur]++;
    }
    ll res = 0;
    for (ll q = 0; q < p; ++q) {
        res += (v[q] * (v[q]-1)) / 2;
    }
    cout << res << endl;
}


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

int main()
{
  int X, N500, N5, res;
  scanf("%d", &X);
  N500 = X / 500;
  N5 = (X - N500 * 500) / 5;
  res = 1000 * N500 + 5 * N5;
  cout << res << endl;
}

Measured memory_bytes: 256
using System;

class AtCoder
{    
    static void Main(string[] args)
     {
        var input = Console.ReadLine().Split(' ');

        int a = int.Parse(input[0]);
        int b = int.Parse(input[1]);

        var x = b % a == 0 ? a + b : b - a;

        Console.WriteLine(x);
     }
 }

Measured memory_bytes: 13140
N = int(input())
B = list(map(int, input().split()))
ans = []
for i in range(N):
    if i == 0:
        ans.append(B[0])
    elif 0 < i < N - 1:
        temp = min(B[i - 1], B[i])
        ans.append(temp)
    elif i == N - 1:
        ans.append(B[-1])
# print(ans)
print(sum(ans))


Measured memory_bytes: 9108
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

int main(){
    int n,m;
    while(cin >> n >> m,n){
        double table[105][105];
        rep(i,n){
            rep(j,n){
                cin >> table[i][j];
            }
        }

        double dp[105][105] = {{0}}; //テヲツ慊?・ツセツ古」ツ?ォテ、ツクツ偲」ツ?暗」ツ?淌ィツつ・テヲツ鳴凖」ツ??ヲツ猟・テ」ツ?ォテ」ツ?。
        rep(i,105) dp[i][0] = 1;
        range(i,1,m){
            rep(j,n){
                rep(k,n){
                    dp[j][i] = max(dp[j][i], dp[k][i - 1] * table[k][j]);
                }
            }
        }
        
        double maxi = 0;
        rep(i,n){
            maxi = max(maxi, dp[i][m - 1]);
        }
        cout <<fixed << setprecision(2) << maxi << endl;
    }
}

Measured memory_bytes: 3364
n = int(input())
x = input()
 
from collections import Counter
import sys
 
up = [0]*n
do = [0]*n
 
b = Counter(x)
 
if b["1"] >= 2:
    pr = b["1"]
    a = 1
    for i in range(n):
        up[n-1-i] = a
        a = a*2 % (pr+1)
    
    a = 1
    for i in range(n):
        do[n-1-i] = a
        a = a*2 % (pr-1)
        
    upsum,dosum = 0,0
    for i in range(n):
        upsum = (upsum + (int(x[i]) * up[i])) % (pr+1)
        dosum = (dosum + (int(x[i]) * do[i])) % (pr-1)
        
    pop = [0] * (n+1)
    for i in range(1,n+1):
        xx = bin(i)[2:]
        c = Counter(xx)
        pop[i] = i % c["1"]
        
    for i in range(n):
        if x[i] == "0":
            ss = (upsum + up[i]) % (pr+1)
            
            aa = 0
            for j in range(400):
                if ss == 0:
                    break
                else:
                    ss = pop[ss]
                    aa += 1
                    
            print(aa+1)
            
        elif x[i] == "1":
            ss = (dosum + (pr-1) - do[i]) % (pr-1)
            
            aa = 0
            for j in range(400):
                if ss == 0:
                    break
                else:
                    ss = pop[ss]
                    aa += 1
                    
            print(aa+1)
            
else:
    pr = b["1"]
    a = 1
    for i in range(n):
        up[n-1-i] = a
        a = a*2 % (pr+1)
 
    upsum = 0
    for i in range(n):
        upsum = (upsum + (int(x[i]) * up[i])) % (pr+1)
 
    pop = [0] * (n+1)
    for i in range(1,n+1):
        xx = bin(i)[2:]
        c = Counter(xx)
        pop[i] = i % c["1"]
    
    for j in range(n):
        if x[j] == "1":
            print(0)
        else:
            ss = (upsum + up[j]) % (pr+1)
            
            aa = 0
            for k in range(400):
                if ss == 0:
                    break
                else:
                    ss = pop[ss]
                    aa += 1
                    
            print(aa+1)

Measured memory_bytes: 80984
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string a;
	cin>>a;
	int n= a.size();
	reverse(a.begin(),a.end());
	vector<int> s(2019);
	s[0]++;
	int sum=0,ten=1;
	long long ans=0;
	for(int i=0;i<n;i++)
	{
		sum+=(a[i]-'0')*ten;
		sum%=2019;
		ans+=s[sum];
		s[sum]++;
		ten*=10;
		ten%=2019;
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 3664
s=str(input())
ans=0
cnt=0

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

Measured memory_bytes: 9048
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		int q = in.nextInt();
		List<int[]> listlr =  new ArrayList<>();
		List<int[]> listpq = new ArrayList<>();
		for(int i=0;i<m;i++) {
			int[] lr = new int[2];
			lr[0] = in.nextInt()-1;
			lr[1] = in.nextInt()-1;
			listlr.add(lr);
		}
		for(int i=0;i<q;i++) {
			int[] pq = new int[2];
			pq[0] = in.nextInt()-1;
			pq[1] = in.nextInt()-1;
			listpq.add(pq);
		}
		
		int[][] t = new int[n][n];
		
		for(int[] lr:listlr) {
			t[lr[0]][lr[1]]++;
		}
		
		for(int i=1;i<n;i++) {
			for(int j=i-1;j>=0;j--) {
				t[j][i] = t[j][i] + t[j+1][i];
			}
		}
		
		for(int i=0;i<n;i++) {
			for(int j=i+1;j<n;j++) {
				t[i][j] = t[i][j] + t[i][j-1];
			}
		}
		
		
		for(int[] pq:listpq) {
			System.out.println(t[pq[0]][pq[1]]);
		}
		
		in.close();

	}

}


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

typedef long long ll;
typedef unsigned long long ull;

template <typename T>
class ModCalc{
public:
    ModCalc(T MOD){
        mod = MOD;
    }

    T add(T a, T b){
        return (a + b) % mod;
    }

    T sub(T a, T b){
        return (a - b) % mod;
    }

    T multi(T a, T b){
        return ((a % mod) * (b % mod)) % mod;
    }

    T power(T a, T n){
        T res = 1;
        while(n){
            if(n&1) res = multi(res, a);
            a = multi(a, a);
            n >>= 1;
        }
        return res;
    }

    T div(T a, T b){
        return multi(a, power(b, mod-2));
    }

    T comb(T n, T k){
        T res = 1;
        for(int i=0; i<k; i++){
            res = multi(res, n-i);
            res = div  (res, i+1);
        }
        return res;
    }

    T multicomb(T n, T k){
        return comb(n+k-1, k);
    }
private:
    T mod;
};

int main()
{
    ll N, K;
    cin >> N >> K;
    auto R = N - K;

    ModCalc<ll> mod(1000000007);
    for(ll i=1;i<=K;i++){
        auto res = mod.multi( mod.comb(R+1, i), mod.multicomb(i, K-i));
        cout<<res<<endl;
    }

    return 0;
}


Measured memory_bytes: 256
N, M , X = map(int, input().split())
book = [list(map(int, input().split())) for _ in range(N)]

ans = 10**9

for i in range(2 ** N):
    money = 0
    L = [0] * M
    for j in range(N):
        if (i >> j) & 1:
            money += book[j][0]
            for m in range(M):
                L[m] += book[j][m+1]
    
    for m in range(M):
        if L[m] < X:
            break
    else:
        ans = min(ans, money)

if ans == 10**9:
    ans = -1

print(ans)


Measured memory_bytes: 9220
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REPL(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
#define MAX_N 200005
ll inv[MAX_N], fac[MAX_N], finv[MAX_N];
void make() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for(int i=2; i<MAX_N; i++) {
    inv[i] = mod - inv[mod%i] * (mod/i) % mod;
    fac[i] = fac[i-1] * (ll)i % mod;
    finv[i] = finv[i-1] * inv[i] % mod;
  }
}
ll perm(ll n, ll r) {
  if(n < 0)       return 0;
  else if(n < r)  return 0;
  else            return (fac[n] * finv[n-r]) % mod;
}
ll comb(ll n, ll r) {
  ll ans = 1;
  ans = perm(n, r); // n * (n-1) * ... * (n-r+1)
  ans = (ans * finv[r]) % mod; // フェルマーの小定理
  return ans;
}
ll binary_pow(ll a, ll N) {
  ll ans = 1;
  ll tmp = a;
  while(N > 0) {
    if(N % 2 == 1) {
      ans *= tmp;
      ans %= mod;
    }
    N /= 2;
    tmp *= tmp;
    tmp %= mod;
  }
  return ans;
}
int main() {
  make();
  ll n;
  int a, b;
  cin >> n >> a >> b;
  ll faca = 1, facb = 1;
  rep(i, a) faca *= n-i, faca %= mod;
  rep(i, b) facb *= n-i, facb %= mod;
  ll cnta = (faca * finv[a]) % mod;
  ll cntb = (facb * finv[b]) % mod;
  ll all = (binary_pow(2, n) - 1 + mod) % mod;
  cout << ((all + mod - cnta) % mod + mod - cntb) % mod << endl;
  return 0;
}


Measured memory_bytes: 4992
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define Repr(e, b, i) for(int i = e; i >= b; i--)
#define rep(n, i) Rep(0, n-1, i)
#define repr(n, i) Repr(n-1, 0, i)
#define all(v) (v).begin(), (v).end()
#define pb(v) push_back(v)
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define bitcnt(x) __builtin_popcount(x)

typedef long long ll;
typedef pair<ll, ll> llP;
typedef pair<int, int> intP;
typedef std::priority_queue<int> IntPrioQueue; //Z->A
typedef std::priority_queue<int, std::vector<int>, std::greater<int> > IntReversePrioQueue; //A->Z

//vector の中身を出力
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

const int MAX = 200000;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<31-1;
const int MOD = 1000000007;

void solve(void){
    string S, T;
    cin >> S >> T;
    int sl = (int)(S.size()), tl = (int)(T.size());
    vector <int> s(sl+1, 0), t(tl+1, 0);
    rep(sl, i) {
        s[i+1] = (S[i] == 'A' ? 1 : 2);
    }
    rep(tl, i) {
        t[i+1] = (T[i] == 'A' ? 1 : 2);
    }
    rep(sl, i) s[i+1] = (s[i] + s[i+1])%3;
    rep(tl, i) t[i+1] = (t[i] + t[i+1])%3;
    //cout << s << endl << t << endl;
    int q; cin >> q;
    rep(q, i) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        //a--, b--, c--, d--;
        if ((s[b]-s[a-1]+3)%3 == (t[d]-t[c-1]+3)%3) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

int main(void){
  solve();
  //cout << "yui(*-v・)yui" << endl;
  return 0;
}


Measured memory_bytes: 1664
#include <math.h>

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define PI 3.14159265358979323846264338327950L
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))

int main() {
  int a, b;
  cin >> a >> b;

  int sum = a;

  if (a > b)
    cout << sum - 1 << endl;
  else
    cout << sum << endl;
}


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

void    Uniq(vector<int> &D, vector<vector<int>> &U) {
        int DD=D.at(0);
        int N=1;
        int i=1;
        while (i<D.size()) {
                if (DD==D.at(i)) {
                        N++;
                } else {
                        U.push_back({DD, N});
                        DD=D.at(i);
                        N=1;
                }
                i++;
        }
        U.push_back({DD, N});
}

bool    Comp2D(vector<int> &A, vector<int> &B) {
        if (A.at(1) == B.at(1)) return (A.at(0)<B.at(0));
        return (A.at(1)>B.at(1));
}

int     main() {
        int     n;
        cin >>n;
        n/=2;
        vector<int> E(n);
        vector<int> O(n);
        for (int i=0; i<n; i++) {
                cin >> O.at(i) >> E.at(i);
        }
        sort(O.begin(), O.end());
        sort(E.begin(), E.end());
        vector<vector<int>> ES(0);
        vector<vector<int>> OS(0);
        Uniq(E, ES);
        Uniq(O, OS);
        sort (ES.begin(), ES.end(), Comp2D);
        sort (OS.begin(), OS.end(), Comp2D);
        ES.push_back({0,0});
        OS.push_back({0,0});
        if (ES.at(0).at(0) != OS.at(0).at(0)) {
                cout << n*2-ES.at(0).at(1)-OS.at(0).at(1) << endl;
        } else {
                cout << n*2-ES.at(0).at(1)-max(ES.at(1).at(1), OS.at(1).at(1)) << endl;
        }
        return 0;
}

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

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1);


int main(void)
{
    ll n; cin>>n;
    cout<<n*(n-1)/2<<endl;
    return 0;
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int MAXN = 200500;

map <int, int> ht;
int pref[MAXN];
int dp[MAXN];
int n;

int main()
{                                                     
	ios_base::sync_with_stdio(0);
	
    string s;
    cin >> s;
    n = (int)s.size();

    for (int i = 0; i < n; i++)
    {
        pref[i + 1] = pref[i] ^ (1 << (s[i] - 'a'));
    }

    ht[0] = 0;

    for (int len = 1; len <= n; len++)
    {
        dp[len] = 1000 * 1000 * 1000;

        if (ht.count(pref[len]) != 0)
        {
            dp[len] = min(dp[len], ht[pref[len]] + 1);
        }

        for (char c = 'a'; c <= 'z'; c++)
        {
            int mask = pref[len] ^ (1 << (c - 'a'));

            if (ht.count(mask) != 0)
            {
                dp[len] = min(dp[len], ht[mask] + 1);
            }
        }

        if (ht.count(pref[len]) != 0)
            ht[pref[len]] = min(ht[pref[len]], dp[len]);
        else
            ht[pref[len]] = dp[len];
    }


    cout << dp[n] << '\n';
	
	return 0;
}


Measured memory_bytes: 11412
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<cstdio>
#include<stack>
#include<queue>
#include<fstream>
#include<cstdio>
#include<deque>
#include<iomanip>
#include <random>

using namespace std;
#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(g);(i)--)
#define all(a) (a).begin(),(a).end()
#define reall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
const double pi = acos(-1.0);

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef deque<ll> dll;
ll mod = 1e9 + 7;


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

	int n;
	cin >> n;
	if (n < 1200)
		puts("ABC");
	else
		puts("ARC");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <set>
#include <iomanip>
#include <stdio.h>
#include <sstream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
  long long int n;
  string s;
  cin>>n>>s;
  long long int right=0;
  long long int left=0;
  for(long long int i=0; i<n; i++){
    if(s[i]=='('){
      left++;
    }else{
      if(left!=0){
        left--;
      }else{
        right++;
      }
    }
  }
  string L="",R="";
  for(long long int i=0; i<right; i++){
    L+="(";
  }
  for(long long int i=0; i<left; i++){
    R+=")";
  }
  string ans=L+s+R;
  cout<<ans<<endl;

}

Measured memory_bytes: 256
from itertools import accumulate
n = int(input())
A = list(map(int, input().split()))
L = [0]
R = []
min_L = float("inf")
for i, a in enumerate(A):
  b = A[-(i+1)]
  if i%2 == 0:
    L.append(a)
  else:
    R.append(a)
R.append(0)
L = list(accumulate(L))
R = list(accumulate(R[::-1]))[::-1]
ans = -float("inf")
if n%2:
  def f(A):
    temp = 0
    left = 0
    right = 0
    for i in range(2, n, 2):
      temp += A[i]
    res = max(ans, temp)
    for i in range(1, n//2):
      temp -= A[i*2]
      left, right = left+A[2*(i-1)], max(left, right)+A[2*(i-1)+1]
      res = max(res, temp+max(left, right))
    return res
  ans = max(f(A), f(A[::-1]))
  temp = 0
  for i in range(1, n, 2):
    temp += A[i]
  ans = max(ans, temp)
else:
  for l, r in zip(L, R):
    ans = max(ans, l+r)
print(ans)

Measured memory_bytes: 33172
//
// Created by yuki on 2018/9/13.
//

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int h, w;

int main() {
    cin >> h >> w;
    vector<vector<int>> matrix(h + 1, vector<int>(w + 1, 0));
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> matrix[i][j];
        }
    }
    vector<vector<int>> ans;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j < w; j++) {
            if (matrix[i][j] % 2 == 1) {
                ans.push_back({i, j, i, j + 1});
                matrix[i][j]--;
                matrix[i][j + 1]++;
            }
        }
    }
    for (int i = 1; i < h; i++) {
        if (matrix[i][w] % 2 == 1) {
            ans.push_back({i, w, i + 1, w});
            matrix[i][w]--;
            matrix[i + 1][w]++;
        }
    }
    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i][0] << " " << ans[i][1] << " " << ans[i][2] << " " << ans[i][3] << endl;
    }
}

Measured memory_bytes: 10032
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
const int Mod = 1e9 + 7;

int main()
{
 //   freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    int n;
    cin >> n;

    int i, j;
    vector<pair<int,int>> v;
    for(i=0; i<2; ++i)
        for(j=1; j<=n; ++j)
        {
            int x;
            cin >> x;
            v.push_back({x, i});
        }

    sort(all(v));

    int nr = 0;
    ll ans = 1;
    int tip;

    for(auto it : v)
        if(nr && tip != it.second)
        {
            ans = ans * nr % Mod;
            --nr;
        }
        else
        {
            if(nr == 0) tip = it.second;
            ++nr;
        }
    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 2420
#include<stdio.h>
int max(int a,int b){return a>b?a:b;}
int main()
{
	long long n,k,sum=0;
	scanf("%lld%lld",&n,&k);
	if(k==0)sum=n*n;
	else for(int i=k+1;i<=n;i++)sum+=(n/i)*(i-k)+max(0,(int)n%i-(int)k+1);
	printf("%lld\n",sum);
}

Measured memory_bytes: 888
use proconio::{input, fastout};
use proconio::marker::{Chars};
use proconio::marker::Usize1;
use std::cmp::*;

macro_rules! debug {
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

#[fastout]
fn main() {
    input!{
        n: usize,
    }

    let inf = 10_0000_0000 + 7;
    let mut ans = 1;
    for i in 1..n+1 {
        ans *= i;
        ans %= inf;
    }

    println!("{}", ans);

}


Measured memory_bytes: 2200
#include <bits/stdc++.h>
template<class T> inline bool chmin(T&a, T b){if(a > b){a = b; return true;}else{return false;}}
template<class T> inline bool chmax(T&a, T b){if(a < b){a = b; return true;}else{return false;}}
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1.0)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int d, score;
vector<int> c(26);
vector<vector<int>> s(400, vector<int>(26)), pos(26);

int get_score(vector<int> t){
    vector<int> pos(26, 0);
    int ans = 0;
    rep(i, t.size()){
        int l = i + 1 - pos[t[i]];
        ans -= (l * (l-1) / 2) * c[t[i]];
        ans += s[i][t[i]];
        pos[t[i]] = i+1;
    }
    rep(i, 26){
        int l = t.size() + 1 - pos[i];
        ans -= (l * (l-1) / 2)* c[i];
    }
    return ans;
}

int main() {
    cin >> d;
    rep(i, 26)cin >> c[i];
    rep(i, d)rep(j, 26)cin >> s[i][j];
    //-----code------// 
    vector<int> t, pos(26, 0);
    rep(i, d){
        int max_score = -mod;
        int best_j = -1;
        rep(j, 26){
            t.push_back(j);
            int score = get_score(t);
            if(max_score < score){
                best_j = j;
                max_score = score;
            }
            t.pop_back();
        }
        t.push_back(best_j);
    }
    vector<int> ans = t;
    double start_temp = 2000, end_temp = 600;
    clock_t start_time = clock();
    int current_max_score = get_score(t);
    while(clock() < 1950000){
        int D = rand() % d, q = rand() % 26;
        int old = t[D];
        int olds = get_score(t);
        t[D] = q;
        int score = get_score(t);
        clock_t now_time = clock();
        double temp = start_temp + (end_temp - start_temp) * (now_time - start_time) / 19000;
        double prob = exp((score - olds)/temp);

        if(chmax(current_max_score, score)){
            ans = t;
        }

        if(prob >= ((rand()%inf)/(double)inf))t[D] = old;
    }
    rep(i, d)cout << ans[i]+1 << endl;
}


Measured memory_bytes: 3816
S = list(input())
n = len(S)
k = int(input())
  
if len(set(S)) == 1:
  print((n * k) // 2)
  exit()

res = 0
i = 0
while i < n - 1:
  if S[i] == S[i + 1]:
    res += 1
    i += 1
  i += 1

if S[0] != S[-1]:
  print(res * k)
else:
	i = 1
	while S[0] == S[i]:
		i += 1

	j = 1
	while S[-1] == S[-1 - j]:
		j += 1
	
	if i % 2 == 0 or j % 2 == 0:
		print(res * k)
	else:
		print(res * k + (k - 1))
 

Measured memory_bytes: 3064
from collections import Counter
N = int(input())
X = []
for _ in range(N):
  X.append(list(map(int, input().split())))
  
if N == 1:
  print(1)
  exit(0)
A = []
for i in range(N):
  for j in range(N):
    if i==j:
      continue
    A.append((X[i][0]-X[j][0], X[i][1]-X[j][1]))
    
C = Counter(A)
print(N - C.most_common()[0][1])

Measured memory_bytes: 9876