akhauriyash/Code-Regression huggingface dataset:
from bisect import bisect_right,bisect_left
import sys
N,H = map(int,input().split())
A = []
B = []
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
B.sort()
ama=max(A)
x = bisect_right(B,ama)
ans = 0
if x ==N:
    if H%ama ==0:
        ans += H//ama 
    else:
        ans += H//ama +1
    print(ans)
    sys.exit()
for i in range(N-1,x-1,-1):
    if H<=0:
        print(ans)
        sys.exit()
    else:
        H-=B[i]
        ans +=1
if H>0:
    if H%ama ==0:
        ans += H//ama 
    else:
        ans += H//ama +1
print(ans)

Measured memory_bytes: 11316
#include<bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define mer make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;

int main(){
	//my new name is Veex
	//clock_t start1=clock();
	ll a,b,c,k;
	cin>>a>>b>>c>>k;
	if(k==0){
		cout<<a-b;
	}
	else if(k%2==1){
		cout<<b-a;
	}
	else
		cout<<a-b;
	//((double)(clock()-start1)/CLOCKS_PER_SEC)*1000;
	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<stack>
#include<vector>
#include<queue>
#define MAX 12000
using namespace std;

stack<pair<int,int> > A;
stack<int> S;

int main(){
  int ans[MAX];
  int sum=0;
  string s;
  cin>>s;
  for(int i=0;i<s.size();i++){
    if(s[i]=='\\'){
      S.push(i);
    }else if(s[i]=='/'){
      int j;
      if(!S.empty()){
        j=S.top(); S.pop();
        sum+=i-j;
        if(A.empty()){
          A.push(make_pair(j,i-j));
          continue;
        }
        pair<int,int> f=A.top();
        if(f.first>j){
          A.pop();
          while(!A.empty()){
            pair<int,int> a=A.top();
            if(a.first<j) break;
            A.pop();
            f.second+=a.second;
          }
          A.push(make_pair(j,f.second+i-j));
        }else{
          A.push(make_pair(j,i-j));
        }
      }
    }
  }
  cout<<sum<<endl;
  int n=A.size();
  for(int i=0;i<n;i++){
    pair<int,int> d=A.top();
    ans[n-1-i]=d.second;
    A.pop();
  }
  cout<<n;
  for(int i=0;i<n;i++){
    cout<<" "<<ans[i];
  }
  cout<<endl;


}



Measured memory_bytes: 3256
N = int(input())
A = [int(i) for i in input().split()]
A_total = [0 for i in A]

A_total[0] = A[0]

for i in range(1,len(A)):
    A_total[i] = A_total[i-1] + A[i]

min_num = float('inf')

for i in range(len(A_total[:-1])):
    snuke = A_total[i]
    bear = A_total[-1] - A_total[i]
    tmp = abs(snuke-bear)
    if min_num > tmp:
        min_num = tmp

print(min_num)

Measured memory_bytes: 24812
//高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

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

#define INF 1999999999
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007 

int main() {
	int ans = 0;
	int tmp;
	int N, M;
	cin >> N >> M;
	vector<int> X(M), Y(M), Z(M);
	REP(i, M) cin >> X[i] >> Y[i] >> Z[i];
	bool ch[N+1] = {};
	
	vector< vector <int> > ls(N+1);
	REP(i, M){ 
		ls[X[i]].push_back(Y[i]); 
		ls[Y[i]].push_back(X[i]);
	}

	queue< int > q;
	REP1(i, N){
		if(!ch[i]){
			q.push(i);
			ans++;
			//cout << i << endl;
			while (q.size() > 0)
			{
				tmp = q.front();
				q.pop();
				ch[tmp] = true;
				REP(j, ls[tmp].size()){
					if(!ch[ls[tmp][j]]) q.push(ls[tmp][j]);
					//cout << "added: " << ls[tmp][j] << endl;
				}
			}
			
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 7800
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
#include<cassert>
#include<iostream>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int mod=1000000007;
const int INF=1001001001;

struct UnionFind{
  vector<int>d;
  UnionFind(int n):d(n,-1){}
  int root(int x){
    if(d[x]<0){return x;}
    return d[x]=root(d[x]);
  }
  bool unite(int x,int y){
    x=root(x);y=root(y);
    if(x==y){return false;}
    if(d[x]>d[y]){swap(x,y);}
    d[x]+=d[y];
    d[y]=x;
    return true;
  }
  bool same(int x,int y){return root(x)==root(y);}
  int size(int x){return -d[root(x)];}
};

int main() {
  int N,M;
  cin>>N>>M;
  vector<int>frend(N);
  UnionFind uf(N);
  for(int i=0;i<M;i++){
    int a,b;
    cin>>a>>b;
    a--;b--;
    uf.unite(a,b);
  }
  int MAX=0;
  for(int i=0;i<N;i++){
    chmax(MAX,uf.size(i));
  }
  cout<<MAX<<endl;

  return 0;  
}

Measured memory_bytes: 4768
package main

import (
	"fmt"
	"math"
)

func main() {
	var n, s1, s2 int
	var diff, ans float64
	fmt.Scan(&n)
	weight := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&weight[i])
	}
	for i := 0; i < n; i++ {
		s1 = 0
		s2 = 0
		for j := 0; j < n; j++ {
			if j <= i {
				s1 += weight[j]
			} else {
				s2 += weight[j]
			}
		}
		diff = math.Abs(float64(s1 - s2))
		if i == 0 {
			ans = diff
			continue
		}
		ans = math.Min(ans, diff)
	}
	fmt.Println(ans)
}


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

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rep2(i,s,n) for(int i = (s); i < (n); ++i)
#define ll long long
#define ld long double
#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.0);

int main(void)
{
    
    ll n; cin>>n;
    vector<tuple<string,ll,ll>> a;
    rep(i,n){
        string s;
        ll p;
        cin>>s>>p;
        a.emplace_back(s,-p,i+1);
    }
    sort(all(a));

    rep(i,n){
        cout<< get<2>(a[i]) <<endl;
    }
    return 0;
}

Measured memory_bytes: 3600
from collections import deque

class RollingHash():
    def __init__(self, s, base1=1007, base2=2009, mod1=10**9+7, mod2=10**9+9):
        self.mod1 = mod1
        self.mod2 = mod2
        self.s = s
        n = len(s)
        self.hash1 = [0]*(n+1)
        self.pow1 = [1]*(n+1)
        self.hash2 = [0]*(n+1)
        self.pow2 = [1]*(n+1)
        for i in range(n):
            self.hash1[i+1] = (self.hash1[i]*base1 + ord(s[i])) % self.mod1
            self.pow1[i+1] = (self.pow1[i]*base1) % self.mod1
            self.hash2[i+1] = (self.hash2[i]*base2 + ord(s[i])) % self.mod2
            self.pow2[i+1] = (self.pow2[i]*base2) % self.mod2

    def get(self, l, r):
        h1 = (self.hash1[r] - self.hash1[l] * self.pow1[r-l]) % self.mod1
        h2 = (self.hash2[r] - self.hash2[l] * self.pow2[r-l]) % self.mod2
        return (h1,h2)


n = int(input())
s = input()
rh = RollingHash(s)

for len_ in range(n//2,0,-1):
    ql = [(-1,-1)]*(len_-1)
    wait_q = deque(ql)
    hset = set()
    # print(len_)
    for i in range(n-len_+1):
        # print(s[i:i+len_])
        hs = rh.get(i,i+len_)
        if hs in hset:
            print(len_)
            exit()
        else:
            wait_q.append(hs)
            hset.add(wait_q.popleft())
        # print(wait_q)
        # print(hset)

else:
    print(0)

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

const int N = 1e5 + 5;

#define int long long

int A[N], n, m;

main() {
	cin >> n >> m;
	for(int i = 1; i <= n; ++ i) cin >> A[i];
	sort(A + 1, A + n + 1);
	int ans = 0;
	for(int i = 1; i <= n; ++ i) {
		if(m >= A[i]) {
			m -= A[i];
			++ ans;
		}
	}
	if(m > 0 && ans == n) -- ans;
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring> 
#include <iostream>
#define ll long long
using namespace std;
const ll N=2e5+10,mo=1e9+7,inf=0x3f3f3f3f;
ll n,x,y,r,num,ans=1,p=1,Mn=inf,mn[N],c[N],w[N],cnt[N],fac[N],inv[N];
ll ksm(ll a,ll b) { for (r=1;b;b>>=1,a=a*a%mo) if (b&1) r=r*a%mo; return r; }
int main()
{
	scanf("%lld%d%d",&n,&x,&y),memset(mn,0x3f,sizeof(mn));
	fac[0]=1; for (ll i=1;i<=n;i++) fac[i]=fac[i-1]*i%mo;
	inv[n]=ksm(fac[n],mo-2); for (ll i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mo;
	for (ll i=1;i<=n;i++) scanf("%lld%d",&c[i],&w[i]),mn[c[i]]=min(mn[c[i]],w[i]),++cnt[c[i]];
	for (ll i=1;i<=n;i++) if (mn[i]<mn[p]) p=i;
	for (ll i=1;i<=n;i++) if (i!=p) Mn=min(Mn,mn[i]);
	for (ll i=1;i<=n;i++) if (!(w[i]!=mn[c[i]]&&w[i]+mn[c[i]]<=x||c[i]!=p&&w[i]+mn[p]<=y||c[i]==p&&w[i]+Mn<=y)) cnt[c[i]]--;
	num=cnt[p]; for (ll i=1;i<=n;i++) if (i!=p&&mn[p]+mn[i]<=y) num+=cnt[i];
	for (ll i=1;i<=n;i++) if (mn[i]!=inf&&(i==p||mn[i]+mn[p]<=y)) ans=ans*inv[cnt[i]]%mo;
	for (ll i=1;i<=num;i++) ans=ans*i%mo;
	printf("%lld",ans);
}

Measured memory_bytes: 9600
#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
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;}
const int MOD = 1000000007;

void solve() {
  int n, k;
  cin >> n >> k;
  double ans = 0;
  for(int i = 1; i <= n; i++) {
    int temp = i;
    int count = 0;
    while (temp < k) {
      temp *= 2;
      count++;
    }
    ans += pow(0.5, count);
  }
  ans /= n;
  cout << setprecision(10) << ans << endl;
}

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

Measured memory_bytes: 4124
N, K = map(int, input().split())
MOD = 10 ** 9 + 7

s = [0]
for i in range(N + 1):
  s.append(s[-1] + i)

ans = 0
for i in range(K, N + 2):
  ans += s[-1] - s[-(i + 1)] - s[i] + 1
  ans %= MOD
print(ans % MOD)

Measured memory_bytes: 19312
#include <iostream>
#include <complex>
#include <cmath>

using namespace std;

typedef complex<double> comp;

const double EPS = 1e-10;

int main(){
  int n;
  cin >> n;
  while(n--){
    comp p[4];
    for(int i=0; i<4; i++){
      double x,y;
      cin >> x >> y;
      p[i] = comp(x,y);
      p[i] -= p[i/2*2]*(double)(i%2);
    }
    if(abs(sin(arg(p[1]/p[3]))) < EPS)
      cout << "YES";
    else cout << "NO";
    cout << endl;
  }
  return 0;
}

  

Measured memory_bytes: 1320
#include<stdio.h>
#include<string.h>
int main(){

  int n,i,j,min,flag=1,sum=0;
  char c1[36];
  int  c2[36];
  char babble1[36];
  int  babble2[36];
  char esc1;
  int  esc2;

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

  for(i=0;i<n;i++){
    babble1[i]=c1[i];
    babble2[i]=c2[i];
  }

  if(n==1){
    printf("%c%d\nStable\n",c1[0],c2[0]);
    printf("%c%d\nStable\n",c1[0],c2[0]);
  }

  if(n!=1){
    //start babble

    while(flag){
      flag=0;

      for(j=n-1;j>=1;j--){
        if(babble2[j] < babble2[j-1]){
          esc1=babble1[j-1];
          esc2=babble2[j-1];
          babble1[j-1]=babble1[j];
          babble2[j-1]=babble2[j];
          babble1[j]=esc1;
          babble2[j]=esc2;

          flag=1;
        }
      }
    }
    for(i=0;i<n;i++){
      printf("%c%d",babble1[i],babble2[i]);
      if(i==n-1) break;
      printf(" ");
    }

    printf("\nStable\n");  //end babble

    //start select

    for(i=0;i<n-1;i++){
      min=i;
      for(j=i+1;j<n;j++){
        if(c2[j]<c2[min]){
          min=j;
        }
      }
      if(i==min) continue;
      esc1=c1[i];
      esc2=c2[i];
      c1[i]=c1[min];
      c2[i]=c2[min];
      c1[min]=esc1;
      c2[min]=esc2;
    }
    for(i=0;i<n;i++){
      printf("%c%d",c1[i],c2[i]);
      if( !((c1[i]==babble1[i]) && (c2[i]==babble2[i]))) sum++;
      if(i==n-1) break;
      printf(" ");
    }

    if(sum==0) printf("\nStable\n");
    else       printf("\nNot stable\n");

    //end select
  }
  return 0;
}

Measured memory_bytes: 2728
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>

using namespace std;
using ll = long long;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
int gcd(int a, int b){ return (b == 0) ? a : gcd(b, a % b); }

#define Sq(x) (x)*(x)
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Reverse(c) reverse(Range(c))
#define Unique(a) a.erase(unique(Range(a)), a.end())
#define Cusum(T, xs, sxs) vector<T> sxs(xs.size()+1); For(i, (int)xs.size()) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) Vec2(T, n, m, xs); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) { for(const auto &e : xs) cout << e << " "; cout << "\n"; }
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")
#define vc vector
#define Mini(a, x) a = min(a, x)
#define Maxi(a, x) a = max(a, x)

constexpr int MOD = 1e9+7;

int main(void){
    Cin(string, s); int n = (int)s.size();
    //Reverse(s);
    vc<vc<int>> dp(n+1, vc<int>(13, 0));
    dp[0][0] = 1;
    
    For(i, n){
        if(s[i] == '?'){
            For(d, 10) For(j, 13) dp[i+1][(10*j+d)%13] = (dp[i+1][(10*j+d)%13] + dp[i][j]) % MOD;
        }
        else{
            int d = s[i] - '0';
            For(j, 13) dp[i+1][(10*j+d)%13] = (dp[i+1][(10*j+d)%13] + dp[i][j]) % MOD;
        }
    }
    Cout(dp[n][5]);
}

Measured memory_bytes: 8960
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Set<String> set = new HashSet<>();
        String blank = sc.nextLine();
        for (int i=0; i<n; i++) {
          String str = sc.nextLine();
          set.add(str);
        }
        System.out.println(set.size());
    }
}


Measured memory_bytes: 79480
H, W = map(int, input().split())
c = []
for i in range(H):
    c.append([int(i) for i in input().split()])
dp = [[0 for i in range(W)] for i in range(H)]
maxwidth = 0
for i in range(H):
    for j in range(W):
        dp[i][j] = (c[i][j] + 1) % 2
        maxwidth |= dp[i][j]

for i in range(1, H):
    for j in range(1, W):
        if c[i][j]:
            dp[i][j] = 0
        else:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1
            maxwidth = max(maxwidth,dp[i][j])

print(maxwidth**2)


Measured memory_bytes: 56460
import java.util.*;
import java.io.PrintWriter;
public class Main{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		long n=sc.nextLong();
		long k=sc.nextLong();
		System.out.println(Math.min(n%k,k-n%k));
	}
}


Measured memory_bytes: 21716
import java.io.*;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        out.println(in.nextInt() < 1200 ? "ABC" : "ARC");
    }
    public static final Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
    public static final PrintStream out = System.out;
}


Measured memory_bytes: 9808
/* template.cpp {{{ */
#include <bits/stdc++.h>
using namespace std;
#define get_macro(a, b, c, d, name, ...) name
#define rep(...) get_macro(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(...) get_macro(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define rep1(n) rep2(i_, n)
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, s) for (ll i = (a); i < (ll)(b); i += (ll)(s))
#define rrep1(n) rrep2(i_, n)
#define rrep2(i, n) rrep3(i, 0, n)
#define rrep3(i, a, b) rrep4(i, a, b, 1)
#define rrep4(i, a, b, s) for (ll i = (ll)(b) - 1; i >= (ll)(a); i -= (ll)(s))
#define each(x, c) for (auto &&x : c)
#define fs first
#define sc second
#define all(c) begin(c), end(c)
using ui = unsigned;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
const int inf = (int)1e9 + 10;
const ll inf_ll = (ll)1e18 + 10;
const ll mod = 1e9 + 7;
const ll mod9 = 1e9 + 9;
const int dx[]{-1, 0, 1, 0, -1, 1, 1, -1};
const int dy[]{0, -1, 0, 1, -1, -1, 1, 1};
template<class T, class U> void chmin(T &x, const U &y){ x = min<T>(x, y); }
template<class T, class U> void chmax(T &x, const U &y){ x = max<T>(x, y); }
struct prepare_ { prepare_(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(12); } } prepare__;
/* }}} */

int main(){
  int h, w;
  cin >> h >> w;
  rep(i, h) rep(j, w){
    string s;
    cin >> s;
    if (s == "snuke"){
      char a = 'A' + j;
      int b = i + 1;
      cout << a << b << endl;
    }
  }
}


Measured memory_bytes: 256
# https://atcoder.jp/contests/abc103/tasks/abc103_d

N, M = map(int, input().split())
AB = []
for _ in range(M):
    ai, bi = map(int, input().split())
    AB.append((ai, bi))
AB = sorted(AB, key=lambda x: x[1])

ans, x = 0, 0

for (a, b) in AB:
    if a > x:
        ans += 1
        x = b - 1
print(ans)

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

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

	set<long long int> as, bs, cs;
	for (long long int i = 0; i < n; i++)
	{
		long long int x = (s[i] - '0');

		for (auto &&b : bs)
		{
			cs.insert(10 * b + x);
		}

		for (auto &&a : as)
		{
			bs.insert(10 * a + x);
		}

		as.insert(x);
	}

	cout << cs.size() << endl;

	return 0;
}


Measured memory_bytes: 3692
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

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

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s,t;
	cin>>s>>t;
	ll ans=0;
	rep(i,3){
		if(s[i]==t[i])ans++;
	}
	cout<<ans<<endl;
}


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

void solve () {
    int n;
    cin >> n;
    vector<int> ans(n);
    for (int i = 1; i < n; i++) {
        int x;
        cin >> x;
        --x;
        ans[x]++;
    }
    for (auto x : ans) {
        cout << x << "\n";
    }
}

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


Measured memory_bytes: 3992
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define INF 114514810
#define MOD 1000000007
#define ALL(a) begin(a),end(a)
#define MS(m,v) memset(m,v,sizeof(m))
#define D10  fixed<<setprecision(10)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> P;
typedef long long ll;
struct edge
{
	int from, to, cost;
	bool operator < (const edge& e) const { return cost < e.cost; }
	bool operator >(const edge& e) const { return cost > e.cost; }
};
///*************************************************************************************///
///*************************************************************************************///
///*************************************************************************************///
int n, W;
int v[1005], w[1005];
int dp[1005][10005];

int solve(int i, int j)
{
	if (i == n) return 0;
	if (dp[i][j] >= 0) return dp[i][j];
	int res;
	if (w[i] > j) res = solve(i + 1, j);
	else res = max({ solve(i + 1, j), solve(i + 1, j - w[i]) + v[i], solve(i,j-w[i])+v[i]});
	return dp[i][j] = res;
}
int main()
{
	MS(dp, -1);
	cin >> n >> W;
	REP(i, n)
	{
		cin >> v[i] >> w[i];
	}
	cout << solve(0, W) << endl;
	return 0;
}

Measured memory_bytes: 41240
#include <stdio.h>
const int MAX_V = 1000000;
int prime[MAX_V + 1];
int main() {
  int i, k, v, n, max = 0;
  for(i = 2; i <= MAX_V; i++) {
    prime[i] = 1;
  }
  for(i = 2; i*i <= MAX_V; i++) {
    if(prime[i]){
      for(k = 2 * i; k <= MAX_V; k += i) {
        prime[k] = 0;
      }
    }
  }
  while(1){
    scanf("%d", &n);
    if(n == 0) break;
    for(i = n;i > 0;i--){
      if(prime[i] == 1 && prime[i - 2] == 1){
        max = i;
        break;
      }
    }
  printf("%d %d\n", max - 2, max);
  }
  return 0;
}

Measured memory_bytes: 4932
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

int main() {
	int n,i,p,ten,out;
	char d[3]={'I','U','O'},ch[8];
	cin >> n;
	for (n;n>0;n--) {
		p=0; out=0; ten=0;
		while(out<3) {
			cin >> ch;
			for (i=0;i<3;i++) if (ch[1]==d[i]) break;
			if (i==0) { ten+=p & 1; p=(p/2) | 4;}
			if (i==1) out++;
			if (i==2) { ten+=(p & 4)/4+(p & 2)/2+(p & 1)+1; p=0;}
			}
		cout << ten << endl;
	}
    return 0;
	}

Measured memory_bytes: 1164
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <numeric>
#include <cstdio>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
using namespace std;
#define MOD 1000000007
#define endl "\n" 
typedef long long ll;


int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
  
    int n; cin >> n;
    int ans = 0;
    int cnt = 0;
    int N = n;
    while(n) {
        int kari = 0;
        if(n % 2 == 0) {
            int num = n;
            int kari = 0;
            do {
                num /= 2;
                ++kari;
            } while(num % 2 == 0);
            if(kari > cnt) {
                ans = n;
                cnt = kari;
            }
        }
        --n;
    }
    
    if(N == 1) ans = 1;
    cout << ans << endl;

    return 0;
}


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

#define endl '\n'
#define ll long long
#define int long long
#define re register
#define pb(x) push_back(x)
#define ce(x) cout << x << '\n';

#define db  long double;
#define pll pair < ll, ll >;

#define rep(i,x,n,inc) for(i=x ; i<n ; i+=inc)
#define repr(i,x,n,inc) for( i=x ; i>n ; i+=inc)
#define all(a)      (a).begin(),(a).end()
#define unique_sort(x) sort(all(x)), x.resize(distance(x.begin(), unique(all(x))))

#define mp(a,b) make_pair(a,b)
#define ff first
#define ss second
#define hell 1000000007
#define infl LLONG_MAX

#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Fill(s,v) memset(s,v,sizeof(s))
#define cout_p(x, p) cout << fixed << setprecision((p)) << x << endl     //print with precision

#define tc(tt) \
    ll tt;    \
    cin >> tt; \
    for (ll _tt = 0; _tt < tt; _tt++) // testcase 

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

	ll t, i, x, j, y, 	z = 0, k, n;
	cin >> n;
	ll a[2 * n];
	rep(i, 0, n * 2, 1)	cin >> a[i];

	sort(a, a + 2 * n);
	reverse(a, a + 2 * n);

	rep(i, 0, 2 * n, 2) {
		z += min(a[i], a[i + 1]);
	}
	ce(z)
}


Measured memory_bytes: 256
def main():
    n = int(input())
    a = list(map(int, input().split()))
    maxa = max(a)
    k = 0
    while 2 ** k <= maxa:
        k += 1
    mod = 10 ** 9 + 7
    mo2 = [1]
    for _ in range(k):
        mo2.append(mo2[-1] * 2)

    p = [[0, 0] for i in range(k)]
    for sa in a:
        for j in range(k):
            if mo2[j] & sa != 0:
                p[j][1] += 1
            else:
                p[j][0] += 1
    res = 0
    for i in range(k):
        res += (p[i][0] * p[i][1] * mo2[i]) % mod
    print(res % mod)


main()


Measured memory_bytes: 125624
#include <stdio.h>

void decompose(int n)
{
    int i, flag = 0;

    for (i = 2; n >= i * i; i++) {
        if (n % i == 0) {
            printf(" %d", i);
            decompose(n / i);
            flag = 1;
            break;
        }
    }
    if (flag == 0)
        printf(" %d", n);

}

int main(void)
{
    int n;

    scanf("%d", &n);
    printf("%d:", n);

    decompose(n);
    printf("\n");

    return 0;
}



Measured memory_bytes: 2128
// (function main(){
//   const lines = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
//   const n = Number(lines.shift());
//   lines.shift().split(' ').map(Number).forEach(function(key, i, a) {
//     console.log(`node ${i+1}: key = ${a[i++]}, `+((i-1)?`parent key = ${a[Math.floor(i/2)-1]}, `:'')+(2*i-1<a.length?`left key = ${a[2*i-1]}, `:'')+(2*i<a.length?`right key = ${a[2*i]}, `:''));
//   });
// })();

require('fs').readFileSync('/dev/stdin', 'utf8').trim().split(/[ |\n]/).slice(1).map(Number).forEach((k,i,a)=>console.log(`node ${++i}: key = ${k}, `+((i-1)?`parent key = ${a[Math.floor(i/2)-1]}, `:'')+(2*i-1<a.length?`left key = ${a[2*i-1]}, `:'')+(2*i<a.length?`right key = ${a[2*i]}, `:'')))



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

using namespace std;

#define int long long
#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define INF 1e9
#define LINF 1e18

typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> Pi;
typedef pair<P, P> PP;

const int MOD = 1e9 + 7;
const int dy[]={0, 0, 1, -1};
const int dx[]={1, -1, 0, 0};

template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }

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

    string s[3];
    rep(i, 3) cin >> s[i];
    cout << s[0][0] << s[1][1] << s[2][2] << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 100005;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vl a(3*n);
    rep(i,3*n){
        cin >> a[i];
    }
    priority_queue<ll, vl, greater<ll> > que;
    vl mx(n+1), mn(n+1);
    ll ans = 0;
    rep(i,2*n){
        if(i >= n){
            ll res = que.top();
            if(res < a[i]){
                que.pop();
                que.push(a[i]);
                ans += a[i]-res;
            }
            mx[i-n+1] = ans;
        }else{
            que.push(a[i]);
            ans += a[i];
        }
        if(i == n-1){
            mx[i-n+1] = ans;
        }
    }
    ll ans2 = 0;
    priority_queue<ll> que2;
    for(int i = 3*n-1; i >= n; i--){
        if(i >= 2*n){
            que2.push(a[i]);
            ans2 += a[i];
            if(i == 2*n){
                mn[i-n] = ans2;
            }
        }else{
            ll res = que2.top();
            if(res > a[i]){
                que2.pop();
                que2.push(a[i]);
                ans2 -= res - a[i];
            }
            mn[i-n] = ans2;
        }
    }
    ll hoge = -(1LL << 60);
    rep(i,n+1){
        cmx(hoge, mx[i]-mn[i]);
    }
    cout << hoge << "\n";
    return 0;
}

Measured memory_bytes: 6516
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#define DEBUG 1

int max(int a,int b){
	return a>=b ? a:b;
}

void swap(int *a,int *b){
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int main(){

	int n;
	int *p;

	cin>>n;
	p = new int[n];
	for(int i=0;i<n;i++)cin>>p[i];

	int cnt=0;

	for(int i=0;i<n-1;i++){
		if(p[i]==(i+1) && p[i+1]==(i+2)){
			swap(&p[i],&p[i+1]);
			i++;
			cnt++;
		}
	}

	for(int i=0;i<n-1;i++){
		if(p[i]==(i+1)){
			swap(&p[i],&p[i+1]);
			cnt++;
		}
	}

	if(p[n-1]==n){
		swap(&p[n-2],&p[n-1]);
		cnt++;
	}

	cout<<cnt<<endl;

	return 0;
}

Measured memory_bytes: 640
// Vicfred
// https://atcoder.jp/contests/abc168/tasks/abc168_c
// math
import std.stdio;
import std.math;

void main() {
    real a, b, h, m;
    readf("%s %s %s %s", &a, &b, &h, &m);

    real x = PI/6;
    real y = PI/30;
    real z = x/60;

    real rad = abs(x*h + z*m - y*m);

    real c = sqrt(a*a+b*b-2.0*a*b*cos(rad));

    writefln("%.23f", c);
}



Measured memory_bytes: 2960
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vc = vector<char>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using stkll = vector<pll>;
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
#define rep(i, n) for (ll i = 0; i < (n); i++)
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;}
#ifndef ONLINE_JUDGE
    #define debug(x) cerr << #x << ": " << x << endl;
#else
    #define debug(x)
#endif

struct mint {
  ll x;
  mint(ll x=0):x((x%MOD+MOD)%MOD){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD-a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= MOD; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
  mint& operator/=(const mint r) {
    ll a = r.x, b = MOD, u = 1, v = 0;
    while (b) {
      ll t = a / b;
      a -= t * b; swap(a, b);
      u -= t * v; swap(u, v);
    }
    x = x * u % MOD;
    if (x < 0) x += MOD;
    return *this;
  }
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    ll N, K;
    cin >> N >> K;

    vector<mint> cnt(K+1, 0);
    mint ans = 0;
    for(ll g = K; g >= 1; g--) {
        mint x = K / g;
        cnt[g] = x.pow(N);
        for(ll gg = 2 * g; gg <= K; gg += g) {
            cnt[g] -= cnt[gg];
        }
        ans += cnt[g] * g;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3956
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define re(i,a,b) for(int i=(a);i<(b);i++)
#define repd(i,a,b) for(int i=(a);i>=(b);i--)
#define run(v) for(int k=head[v];k;k=e[k].ne)
#define v e[k].t
#define clr(a) memset(a,0,sizeof(a));
#define il inline
#define sz(a) ((int)a.size())
#define all(a) a.begin(),a.end()
#define mp make_pair
#define pb push_back 
#define w1 first
#define w2 second
#define adm(a,b,c) {a=a+b;if(a>=c)a-=c;else if(a<0)a+=c;}
typedef pair<int,int> pa;
typedef long long ll;typedef long double ld;typedef unsigned long long ull;
const int N=5e5+5,M=5e7+5,INF=1e9,mod=1e9+7;
const ll linf=1e18;const double eps=1e-8,pi=acos(-1);
il int gmin(int &a,int b){if(a>b)a=b;}il ll gmin(ll &a,ll b){if(a>b)a=b;}il int gmax(int &a,int b){if(a<b)a=b;}il ll gmax(ll &a,ll b){if(a<b)a=b;}
il void read(ll&x){ll f=1,t=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){t=t*10+ch-'0';ch=getchar();}x=t*f;}il ll read(ll&x,ll&y){read(x);read(y);}
il void read(int&x){int f=1,t=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){t=t*10+ch-'0';ch=getchar();}x=t*f;}il int read(int&x,int&y){read(x);read(y);}
il void read(int&a,int&b,int&c){read(a);read(b);read(c);}il void read(ll&a,ll&b,ll&c){read(a);read(b);read(c);}
il int read(){int x;read(x);return x;}
il ll qpow(ll a,ll b,ll p){ll ret=1;for(;b;b>>=1,a=a*a%p)if(b&1)ret=ret*a%p;return ret;}il ll qpow(ll a,ll b){ll ret=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ret=ret*a%mod;return ret;}
il ll qmul(ll a,ll b,ll p){ll ret=0;for(;b;b>>=1,a=(a<<1)%p)if(b&1)adm(ret,a,p);return ret;}il ll qmul(ll a,ll b){ll ret=0;for(;b;b>>=1,a=(a<<1)%mod)if(b&1)adm(ret,a,mod);return ret;}
il void judge(){
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);}
il void gen(){freopen("data.in","w",stdout);}
struct edge{int t,ne;}e[N];
int head[N],cnt,n,k,mn[N],mx[N],ans[N];
void gao1(int x,int f){
	run(x)if(v!=f){
		gao1(v,x);
		gmax(mn[x],mn[v]-1);
		gmin(mx[x],mx[v]+1);
	}
	if(mn[x]>mx[x]){puts("No");exit(0);}
}
void gao2(int x,int f){
	run(x)if(v!=f){
		if(mn[v]<=ans[x]+1&&mx[v]>=ans[x]+1)ans[v]=ans[x]+1;else
		if(mn[v]<=ans[x]-1&&mx[v]>=ans[x]-1)ans[v]=ans[x]-1;
			else{puts("No");exit(0);}
		gao2(v,x);
	}
}
void adde(int a,int b){
	e[++cnt]=(edge){b,head[a]};head[a]=cnt;
}
int main(){
	read(n);re(i,1,n){int a,b;read(a,b);adde(a,b);adde(b,a);}
	rep(i,1,n)mn[i]=-INF,mx[i]=INF;
	read(k);
	rep(i,1,k){
		int x,y;read(x,y);
		mn[x]=mx[x]=y;
	}
	gao1(1,0);
	ans[1]=mn[1];
	gao2(1,0);puts("Yes");
	rep(i,1,n)cout<<ans[i]<<endl;
}

Measured memory_bytes: 14336
#include <iostream>
#include <string>
#include <cstdlib>
#define x 81
using namespace std;

int main(){
	int n;
	cin >> n;
	cin.ignore();
	for(int i=0;i<n;i++){
		string a,b;
		getline(cin,a);
		getline(cin,b);
		bool c = false;
		if(a.size()>=x) c = true;
		if(b.size()>=x) c = true;
		int p[x];
		int k = 0;
		for(int j=0;j<x;j++){
			p[j] = k;
			int s = a.size()-j-1;
			int t = b.size()-j-1;
			string f;
			string g;
			if(s>=0) f = a.substr(s,1);
			if(t>=0) g = b.substr(t,1);
			if(s>=0) p[j] += atoi(f.c_str());
			if(t>=0) p[j] += atoi(g.c_str());
			if(p[j]>=10){ p[j] -= 10; k = 1; }
			else k = 0;
			if(k*j==79) c = true;
		}
		if(c) cout << "overflow" << endl;
		else{
			int d = x-1;
			while(p[d]==0){ d--; }
			if(d<0) cout << 0 << endl;
			else{
				for(int j=d;j>=0;j--) cout << p[j];
				cout << endl;
			}
		}
	}
}

Measured memory_bytes: 1224
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <stdio.h>
#include <math.h>


using namespace std;

typedef long long ll;

typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<ll> vll;

typedef pair<int, int> pii;

typedef queue<int> qi;
typedef queue<string> qs;


#define rep(i, n) for(int i=0; i<(n); ++i)
#define repp(i, a, b) for(int i = (a); i <= (b); i++)
#define Rep(i, n) for(int i=n; i >= 0; i--)

#define all(v) v.begin(), v.end()
//sort( all(v) )　などと使える

int main(){
    ll a, b, c, k; cin >> a >> b >> c >> k;

    if(k <= a) cout << k << endl;
    else if(k > a && k <= b) cout << a << endl;
    else cout << a - (k - a - b) << endl;
}

Measured memory_bytes: 3628
#include <cstring>
#include <sstream>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <set>
#include <numeric>
#include <stack>

using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto i:mp)
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll half_inf = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);
typedef unordered_map<char, ll> ump;
typedef pair<ll, ll> P;

ump mp;


int main() {
#ifdef MY_DEBUG
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wmissing-noreturn"
    while (true) {
        mp = ump();
#pragma clang diagnostic pop
#endif
        ll n;
        string s;
        cin >> n >> s;
        rep(i, n) mp[s[i]]++;
        ll ans = 1;
        each(m, mp) {
            ans *= (m.second + 1);
            ans %= mod;
        }
        ans--;
        cout << ans << endl;


#ifdef MY_DEBUG
    }
#endif
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10,INF=0x3f3f3f3f;
int n,q,op,x;
ll now;
struct segtree{
	int n;
	struct node{int l,r,mx,cnt,se;}e[N<<2];
	#define l(p) e[p].l
	#define r(p) e[p].r
	#define m(p) e[p].mx
	#define c(p) e[p].cnt
	#define s(p) e[p].se
	void up(int p){
        c(p)=0;
        m(p)=max(m(p<<1),m(p<<1|1));
        s(p)=max(s(p<<1),s(p<<1|1));
        if(m(p<<1)!=m(p<<1|1))s(p)=max(s(p),min(m(p<<1),m(p<<1|1)));
        if(m(p<<1)==m(p))c(p)+=c(p<<1);
        if(m(p<<1|1)==m(p))c(p)+=c(p<<1|1);
	}
	void bld(int p,int l,int r){
		l(p)=l;r(p)=r;c(p)=-1;
		if(l==r){m(p)=n;s(p)=-1;c(p)=1;return;}
		int mid=l+r>>1;
		bld(p<<1,l,mid);bld(p<<1|1,mid+1,r);
		up(p);
	}
	void MIN(int p,int v){
        if(v>=m(p))return;
        m(p)=v;
	}
	void init(int _n){n=_n;bld(1,1,n);}
	void psd(int p){
        MIN(p<<1,m(p));
        MIN(p<<1|1,m(p));
    }
    void Min(int p,int ql,int qr,int v){
        if(v>=m(p))return;
        if(ql<=l(p)&&r(p)<=qr&&s(p)<v){
            MIN(p,v);
            return;
        }
        psd(p);
		int mid=l(p)+r(p)>>1;
        if(ql<=mid)Min(p<<1,ql,qr,v);
		if(qr>mid)Min(p<<1|1,ql,qr,v);
		up(p);
    }
	int ask(int p,int x){
		if(l(p)==r(p))return m(p);
		int mid=l(p)+r(p)>>1;
		psd(p);
		int ans=0;
		if(x<=mid)ans=ask(p<<1,x);
		else ans=ask(p<<1|1,x);
		up(p);
		return ans;
	}
}row,col;
int main(){
    scanf("%d%d",&n,&q);
    now=1ll*(n-2)*(n-2);
    row.init(n);
    col.init(n);
    for(int i=1;i<=q;++i){
        scanf("%d%d",&op,&x);
        if(op==1){
            int pos=col.ask(1,x);
            now-=pos-2;
            row.Min(1,1,pos-1,x);
        }
        else{
            int pos=row.ask(1,x);
            now-=pos-2;
            col.Min(1,1,pos-1,x);
        }
    }
    printf("%lld\n",now);
    return 0;
}


Measured memory_bytes: 24352
# include <iostream>
# include <vector>
# include <cstring>
# define pf push_front
# define pb push_back
# define mp make_pair
# define pr printf
# define se second
# define si size()
# define sc scanf
# define fi first
# define er erase
# define be begin
# define ss size
# define Int __int64
# define INF 100000000000000008
# define MOD 1000000007
# define MN 500500
# define eps 0.0000000000000000018
# define mem(a) memset(a,0,sizeof(a))
# define cpy(b,a) memcpy(b,a,sizeof(a))
#define fast ios_base::sync_with_stdio(false)
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
using namespace std;
int a[55][55],vis[55];
void dfs(int n){
	vis[n]=1;
	for(int i=0;i<55;i++){
		if(a[n][i]==1 && !vis[i])dfs(i);
	}
}
int main() {
	int x,y,n,m,i,j,ans(0);
	cin>>n>>m;
	vector< pair<int,int> >v;
	for(i=0;i<m;i++){
		cin>>x>>y;
		a[x][y]=1;
		a[y][x]=1;
		v.pb(mp(x,y));
	}
	for(i=0;i<v.si;i++){
		x=v[i].first;
		y=v[i].second;
		a[x][y]=0;
		a[y][x]=0;
		dfs(1);
		for(j=1;j<=n;j++){
			if(!vis[j]){
				ans++;
				break;
			}
		}
		a[x][y]=1;
		a[y][x]=1;
		mem(vis);
	}
	cout<<ans;
	return 0;
}
/* and its only us now */


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

using namespace std;

typedef long long int ll;

#define FOR(i,l,r) for(i=l;i<r;i++)

#define REP(i,n) FOR(i,0,n)

#define ALL(x) x.begin(),x.end()

#define P pair<ll,ll>

#define F first

#define S second

signed main(){

  ll A,B,N;cin>>A>>B>>N;

  cout<<A*min(B-1,N)/B<<endl;

  return 0;

}

Measured memory_bytes: 3548
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 1e16;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)

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

void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}
//--------------------------------------------------------------------------------//
ll cnt[26];
int main() {
    init();
    string s;
    while(cin>>s)rep(i,s.size()){
            char c = s[i];
            if ('A' <= c and c <= 'Z') cnt[c - 'A']++;

            if ('a' <= c and c <= 'z') cnt[c - 'a']++;
    }

    rep(i,26){
        cout << char('a' + i) << " : " << cnt[i] << endl;
    }
}


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

int main() {
    int sum, yen;
    cin >> sum >> yen;

     
    sum = sum % 500;
     

     if(sum <= yen)
     cout << "Yes" << endl;
     else
     {
         cout << "No" << endl;
     }
     
}

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

const int N = 1e5 + 5;
int n, T;
int A[N];
std::set<int> before;

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

    std::cin >> n >> T;
    int maxp = 0, minimum = 1e9 + 9;
    for (int i = 1; i <= n; ++ i) {
        std::cin >> A[i];
        if (A[i] - minimum > maxp) maxp = A[i] - minimum;
        minimum = std::min(minimum, A[i]);
    }

    int ans = 0;
    for (int i = 1; i <= n; ++ i) {
        if (before.count(A[i] - maxp)) ++ ans;
        before.insert(A[i]);
    }

    std::cout << ans << std::endl;
}


Measured memory_bytes: 5376
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n,k,ans = 0;
    cin >> n >> k; 
    vector<int> d(n);

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

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

    for(int j=0;j<k;j++){
        ans += d[j];
    }

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

Measured memory_bytes: 3636
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    int n = s.length();
    int ans = 0;

    for (int i = 0; i < n; i++) {
      if (s.charAt(i) == 'A') {
        ans = -i;
        break;
      }
    }

    for (int i = n - 1; i >= 0; i--) {
      if (s.charAt(i) == 'Z') {
        ans += i;
        break;
      }
    }

    System.out.println(ans + 1);

  }
}

Measured memory_bytes: 40372
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <algorithm>

using namespace std;

long long solve(vector<long long> v, int b){
  long long sum = 0;
  for(int i = 0; i < v.size(); i++){
    sum += abs(v[i] - b);
  }
  return sum;
}

int main(){
  int b;
  vector<long long> v;
  long long a, t, n;

  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> t;
    v.push_back(t - i - 1); 
  }
  sort(v.begin(), v.end());
  b = v[n / 2];
  a = solve(v, b);
  cout << a << endl;
}

Measured memory_bytes: 3440
n,m,k=map(int,input().split())
a=[0]+list(map(int,input().split()))
b=[0]+list(map(int,input().split()))

for i in range(1,n+1): a[i]=a[i]+a[i-1]
for i in range(1,m+1): b[i]=b[i]+b[i-1]
j=m
ans=0
for i in range(n+1):
    if j<0: break
    while a[i]+b[j]>k and j>=0: j-=1
    ans=max(i+j,ans)
print(ans)

Measured memory_bytes: 39828
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

ll a[411111];
ll b[411111];
multiset<ll> pos;
multiset<ll> neg;
ll sumpos;

void add(ll x)
{
	if(x>0)
	{
		pos.insert(x);
		sumpos+=x;
	}
	else
	{
		neg.insert(-x);
	}
}

void del(ll x)
{
	if(x>0)
	{
		auto it = pos.lower_bound(x);
		pos.erase(it);
		sumpos-=x;
	}
	else
	{
		auto it = neg.lower_bound(-x);
		neg.erase(it);
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	sumpos=0;
	int n,q; cin>>n>>q; n*=2;
	ll sum=0;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		sum+=a[i];
	}
	for(int i=0;i<n;i++)
	{
		cin>>b[i];
		b[i]-=a[i];
		if(i>=1&&i+1<n) add(b[i]);
	}
	for(int i=0;i<q;i++)
	{
		int p,u,v;
		cin>>p>>u>>v;
		p--;
		sum-=a[p]; sum+=u;
		//b[i] becomes v-u
		if(p>=1&&p+1<n)
		{
			del(b[p]); add(v-u);
		}
		a[p]=u; b[p]=v-u;
		if(pos.size()%2==0)
		{
			cout<<sum+sumpos<<'\n';
		}
		else
		{
			if(neg.empty())
			{
				cout<<sum+sumpos-(*pos.begin())<<'\n';
			}
			else
			{
				cout<<sum+max(sumpos-(*pos.begin()), sumpos-(*neg.begin()))<<'\n';
			}
		}
	}
}	


Measured memory_bytes: 16768
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int main(void){
  int n;
  string s;
  cin >> n >> s;
  int w[n], e[n];
  if(s[0] == 'W') w[0] = 1;
  else w[0] = 0;
  if(s[n - 1] == 'E') e[n - 1] = 1;
  else e[n - 1] = 0;
  for(int i = 1; i < n; i++){
    w[i] = w[i - 1];
    if(s[i] == 'W') w[i]++;
  }
  for(int i = n - 2; i >= 0; i--){
    e[i] = e[i + 1];
    if(s[i] == 'E') e[i]++;
  }
  int ans = 1e+6;
  for(int i = 0; i < n; i++) ans = min(ans, w[i] + e[i] - 1);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3076