akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll long long int 

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  ll n,k,i,sum=0;
  cin>>n>>k;
  vector<ll> arr(n);
  for(i=0;i<n;i++) cin>>arr[i];
  sort(arr.begin(),arr.end());
  for(i=0;i<k;i++) sum = sum+arr[i];
  cout<<sum;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
#define FIN ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long ll;
typedef vector<ll> vll;

int main() {FIN
	
	ll n, m, i;
	cin >> n;
	vll as(n), bs(n);
	for (i = 0; i < n; i++) {
		cin >> as[i] >> bs[i];
	}
	
	sort(as.begin(), as.end());
	sort(bs.begin(), bs.end());
	
	m = n / 2 - (n % 2 ? 0 : 1);
	if (n % 2) {
		cout << bs[m] - as[m] + 1 << "\n";
	} else {
		cout << (bs[m] + bs[m + 1]) - (as[m] + as[m + 1]) + 1 << "\n";
	}
	
	return 0;
}


Measured memory_bytes: 6320
#include <bits/stdc++.h>
using namespace std;
 
#define FAST ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
 
#define MAXX 100005
 
#define PI   3.14159265358979323846264338327950
 
#define F first
#define S second
 
#define ll 	 long long int
 
#define mod  1000000007



int main()
{
	FAST;
	string s;
	cin >> s;
	ll n = s.size();;
	ll a = 0, ab = 0, abc = 0, d = 1;
	for(ll i = 0; i < n; i ++){
		if(s[i] == 'A'){
			a += d;
		}
		else if(s[i] == 'B'){
			ab += a;
		}
		else if(s[i] == 'C'){
			abc += ab;
		}
		else{
			abc *= 3;
			abc += ab;
			ab *= 3;
			ab += a;
			a *= 3;
			a += d;
			d *= 3;
		}
		a %= mod;
		ab %= mod;
		abc %= mod;
		d    %= mod;
		
	}
	cout << abc;
	return 0;
}

Measured memory_bytes: 3792
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <tuple>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <chrono>
# include <random>
# include <limits.h>
# include <unordered_map>
# include <unordered_set>
# include <deque>
# include <cstdio>
# include <cstring>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr long long MOD = 1000000000 + 7;
constexpr long long INF = 1e17 - 10;
const double PI = acos(-1);
typedef pair<LL, LL> Pll;
typedef pair<LL, LL> Vec2;
LL h, w, n, m, s, t, ans = 0, a[100000], b[100000], num = 1, sum = 0, dp[3200][3200] = {};
string str;
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
	}
	sort(a, a + n);
	sort(b, b + n);
	for (int j = n - 1; j >= 0; j--) {
		if (b[j] > a[n - 1]&&m>0) {
			m -= b[j];
			ans += 1;
		}
		else break;
	}
	if(m>0)
	ans += (m / a[n - 1]) + (m % a[n - 1] == 0 ? 0 : 1);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1792
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author toshibablack
 */

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <fstream>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

#define ll long long int
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define REP(i, n) for(int i=0;i<n;++i)
#define FOREACH(x, a) for(auto& (x) : (a))
#define ALL(a) (a).begin(),(a).end()
#define COUT(x) out << (x) << endl;

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

using namespace std;


class AFrog1 {
public:
    int N;
    int h[100001];
    int c[100001];

    void solve(std::istream& in, std::ostream& out) {
        in >> N;
        for (int i = 1; i <= N; ++i) in >> h[i];
        for (int i = 1; i <= N; ++i) c[i] = INF;
        COUT(cost(1));
    }

    int cost(int i) {
        if (i >= N) return 0;
        if (i == N-1) return abs(h[i+1]-h[i]);
        if (c[i] != INF) return c[i];
        c[i] = min(abs(h[i+1]-h[i]) + cost(i+1), abs(h[i+2]-h[i]) + cost(i+2));
        return c[i];
    }
};


int main() {
    AFrog1 solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 3328
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
  int N;
  cin >> N;
  vector<int> a(3 * N);
  for (int i = 0; i < 3 * N; i++)
    cin >> a[i];
  sort(a.rbegin(), a.rend());
  long ans = 0;
  for (int i = 0; i < N; i++)
    ans += a[2 * i + 1];
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1408
h,w=map(int,input().split())
mez=['.'*(w+1)]

for _ in range(h):
    meztmp=input()
    mez.append('.'+meztmp+'.')
mez.append('.'*(w+1))
for y in range(1,h+1):
    for x in range(1,w+1):
        if mez[y][x]=='#':
            if mez[y-1][x]=='.' and mez[y+1][x]=='.' and mez[y][x+1]=='.' and mez[y][x-1]=='.':
                print('No')
                exit()
print('Yes')
                                                                                              


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

int main()
{
	string s,t;
	cin >> s;
	ll n = s.size();
	for(ll i = 0;i<n;i++)
	{
		if(s[i]=='B'&&s[i+1]=='C')t.push_back('D'),i++;
		else
		{
			t.push_back(s[i]);
		}
	}
	n = t.size();
	ll cnt = 0;
	ll ans = 0;
	for(auto c:t)
	{
		if(c=='A')
		{
			cnt++;
		}
		else if(c=='D')
		{
			ans += cnt;
		}
		else
		{
			cnt = 0;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 776
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 262150
#define inf 2147483647
using namespace std;
struct pos1{int l, r;}pos[N][19];
int n, m, k, w[N], now, dp_l[N], dp_r[N], bin[19], x, ff, sum;
int main(){
	scanf("%d%d", &n, &m);
	bin[0]=1; for(int i=1; i<=18; i++)bin[i]=bin[i-1]<<1;
	for(int i=1; i<=n; i++)scanf("%d", &w[i]); w[0]=w[1]-m-1; w[n+1]=w[n]+m+1;
	k=-1; x=m<<1;
	while(x){
		k++; x>>=1; now=0;
		for(int i=1; i<=n; i++){
			if(w[i]-w[i-1]>x)now=i;
			pos[i][k].l=now;
		}
		now=n+1;
		for(int i=n; i; i--){
			if(w[i+1]-w[i]>x)now=i;
			pos[i][k].r=now;
		}
	}
	dp_l[0]=0; dp_r[0]=n+1;
	for(int i=1; i<=bin[k]-1; i++){
		dp_l[i]=0; dp_r[i]=n+1;
		for(int j=1; j<=k; j++)if(i&bin[j-1]){
			dp_l[i]=max(dp_l[i], pos[dp_l[i-bin[j-1]]+1][j].r);
			dp_r[i]=min(dp_r[i], pos[dp_r[i-bin[j-1]]-1][j].l);
		}
	}
	sum=0; for(int i=1; i<=n; i++)if(pos[i][0].l==i)sum++;
	if(sum>=k+2){for(int i=1; i<=n; i++)printf("Impossible\n"); return 0;}
	for(int i=1; i<=n; i++)if(pos[i][0].l==i){
		ff=0;
		for(int j=0; j<=bin[k]-1; j++)if(dp_l[j]>=pos[i][0].l-1&&dp_r[bin[k]-1-j]<=pos[i][0].r+1){ff=1; break;}
		for(int j=pos[i][0].l; j<=pos[i][0].r; j++)if(ff)printf("Possible\n"); else printf("Impossible\n");
	}
	return 0;
}

Measured memory_bytes: 35072
i = list(map(int,input().split()))
H = i[0]
W = i[1]


#二次元配列の作成
#ひとまわり大きく作る
masu = []
for i in range(H+2):
    sublist = []
    if(i == 0)or(i == H+1):
        sublist = ['.']*(W+2)
        masu.append(sublist)
        continue
    a = input()
    for k in a:
        sublist.append(k)

    sublist.insert(0,'.')
    sublist.append('.')
    masu.append(sublist)



count = 0
for j in range(1,H+1):
    for k in range(1,W+1):
        if(masu[j-1][k-1] == '#'):
            count += 1

        if(masu[j-1][k] == '#'):
            count += 1

        if(masu[j-1][k+1] == '#'):
            count += 1

        if(masu[j][k-1] == '#'):
            count += 1

        if(masu[j][k+1] == '#'):
            count += 1

        if(masu[j+1][k-1] == '#'):
            count += 1

        if(masu[j+1][k] == '#'):
            count += 1

        if(masu[j+1][k+1] == '#'):
            count += 1

        if(masu[j][k] != '#'):
            masu[j][k] = count

        count = 0

for i in range(1,H+1):
    masu[i].pop(0)
    masu[i].pop(-1)
    result = ''.join(map(str,masu[i]))
    print(result)

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

 vector<int> dp; 
 vector<int> n[100050]; 
 
 int lp(int i) {
  if(dp[i] != -1) 
  return dp[i];
   // cout << "EE " << i << endl; 
   if(n[i].size() == 0) {
    // cout << "OI" << endl; 
    dp[i] = 0; 
    return 0;
     } 
     else { 
     int ma = -1; 
     for(int o = 0; o < n[i].size(); o++) 
     { 
       if(lp(n[i][o]) > ma) 
          ma = dp[n[i][o]]; 
      } 
       dp[i] = 1+ma; 
       return dp[i]; 
       } 
       } 
       int main() 
       { 
       int N, M; cin >> N >> M; 
       vector<int> pom; 
       for(int i = 0; i <= N; i++) 
       pom.push_back(0); 
       for(int i = 1; i <= N+1; i++) 
       { 
       dp.push_back(-1); 
       //n[i-1]=pom; 
       } 
       int x, y; 
       for(int i = 1; i <= M; i++) 
       { cin >> x >> y; 
       n[x].push_back( y);
       } 
       int rez = 0; 
       for(int i = 1; i <= N; i++) 
       {
       
       rez  = max(rez, lp(i)); 
       } 

       cout << rez; 
       return 0; 
       } 


Measured memory_bytes: 8568
#include <stdio.h>

#define M 100
#define WHITE 1
#define BLACK 0
#define GRAY 2

void dfs(void);

void visit(int);


int n,time;

int tyouten[M][M],color[M],d[M],f[M];

int main(){

  int i,j,k,u,v;

  scanf("%d",&n);

  for(i=0;i<n;i++){

    for(j=0;j<n;j++) tyouten[i][j]=0;

  }

  for(i=0;i<n;i++){

    scanf("%d%d",&u,&k);

    for(j=0;j<k;j++){

      scanf("%d",&v);

      tyouten[u-1][v-1]=1;

    }

  }

  dfs();

  return 0;

}


void dfs(){

  int u;

  for(u=0;u<n;u++) color[u]=WHITE;

  time=0;

  for(u=0;u<n;u++){

    if(color[u]==WHITE) visit(u);

  }

  for(u=0;u<n;u++) printf("%d %d %d\n",u+1,d[u],f[u]);

}


void visit(int u){

  int v;

  color[u]=GRAY;

  d[u]=++time;

  for(v=0;v<n;v++){

    if(tyouten[u][v]==0) continue;

    if(color[v]==WHITE) visit(v);

  }

    color[u]=BLACK;
    f[u]=++time;

}

Measured memory_bytes: 636
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
#define pb push_back
template<class T>void chmax(T &a,T b){if(a<b)a=b;}
template<class T>void chmin(T &a,T b){if(a>b)a=b;}
constexpr int INF=1000000000000000000;
constexpr int mod=1000000007;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
bool prime(int a){
    if(a==1)return false;
    for(int i=2;i*i<=a;i++){
        if(a%i==0)return false;
    }
    return true;
}
vector<int>kaijo;
void init_fact(int n){
    kaijo.resize(n+1);
    kaijo[0]=1;
    for(int i=1;i<=n;i++){
        kaijo[i]=kaijo[i-1]*i;
        kaijo[i]%=mod;
    }
}
int modpow(int a,int b){
    if(b==0)return 1;
    if(b%2)return modpow(a,b-1)*a%mod;
    int memo=modpow(a,b/2);
    return memo*memo%mod;
}
int comb(int a,int b){
    //if(!kaijo[0])init_fact(2000010);
    return kaijo[a]*modpow(kaijo[a-b],mod-2)%mod*modpow(kaijo[b],mod-2)%mod;
}
int inv(int x){
    x=modpow(x,mod-2);
    return x;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){
    double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
    double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
    double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
    double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
    return tc*td<0&&ta*tb<0;
}
int a,b,n;
int calc(int x){
    return a*x/b-a*(x/b);
}
signed main(){
    cin>>a>>b>>n;
    cout<<max(calc(n),calc(n/b*b-1))<<endl;
    return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
using namespace std;
int main()
{
	string x;
	cin>>x;
	int index=0;
	int ans=0;
	while(index<x.size())
	{
		if(x[index]=='S')
		{
			int scnt=0;
			int tcnt=0;
			while(index<x.size() && (x[index]=='S' || x[index]=='T'))
			{
				if(x[index]=='S')
					scnt++;
				if(x[index]=='T')
				{
					if(scnt>0)
					{
						scnt--;
						tcnt++;
					}else{
						break;
					}
				}
				index++;
			}
			ans+=(tcnt*2);
		}else{
			index++;
		}
	}
	cout<<x.size()-ans<<endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long LL;
LL a[N], b[N];
int n;

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%lld%lld", &a[i], &b[i]);
    }
    LL ans = 0, add = 0;
    for(int i = n ; i; i--) {
        LL k = (a[i]+add+b[i]-1)/b[i];
        ans += k*b[i]-a[i]-add;
        add += k*b[i]-a[i]-add;
    }
    cout << ans << endl;
    return 0;
}


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

int N;

int main() {
  std::cin >> N;
  std::string yomi;
  switch(N % 10) {
    case 2:
    case 4:
    case 5:
    case 7:
    case 9:
      yomi = "hon";
      break;
    case 0:
    case 1:
    case 6:
    case 8:
      yomi = "pon";
      break;
    case 3:
      yomi = "bon";
      break;
  }

  std::cout << yomi << std::endl;
}

Measured memory_bytes: 3628
import heapq

N, M = map(int, input().split())
AB = {}
q = []
ans = 0

for i in range(N):
    A, B = map(int, input().split())
    
    if A in AB:
        AB[A].append(-B)
    else:
        AB[A] = [-B]

for i in range(1, M+1):
    if i in AB:
        for B in AB[i]:
            heapq.heappush(q, B)
        
    if len(q):
        ans -= heapq.heappop(q)
    
print(ans)    

Measured memory_bytes: 26020
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    S = input().rstrip()
    alphabets = 'abcdefghijklmnopqrstuvwxyz'
    ans = 'None'
    for a in alphabets:
        if S.count(a) < 1:
            ans = a
            break
    print(ans)
    
if __name__ == '__main__':
    main()


Measured memory_bytes: 3812
import java.util.Scanner;

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

       int a = scan.nextInt();
       int b = scan.nextInt();

       if(b%a==0){
          System.out.println(a+b);
       }else {
          System.out.println(b-a);
       }
      }
   }

Measured memory_bytes: 22740
#include <iostream>
#include <vector>
#include <cmath>


using namespace std;

int main(void){
	int n;

	cin >> n;


	int b = 1;
	int k;

	for (int i = 0; i < n; i++){
		cin >> k;
		if (k % 2 == 1){
			b *= 1;
		}
		else
			b *= 2;
	}

	cout << pow(3, n) - b << endl;

	return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<bitset>
#include<functional>
#include<iterator>
#include<complex>
#include<fstream>
#include<random>
#include<ctype.h>
#include<stdio.h>
#define pb push_back
#define mp make_pair
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using PII = pair<ll, ll>;
using piii = pair<pii, pii>;
using Pi = pair<int, pii>;
using Graph = vector<vector<int>>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
bool check(int x, int y) {
	if (0 <= x && x<55 && 0 <= y && y<55)return true;
	else return false;
}
const ll INF = 1e+7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
using Graph = vector<vector<int>>;

long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
const double PI = 3.14159265358979323846;
const int MAX = 510000;
ll fac[MAX], finv[MAX], inv[MAX];
//テーブルをつくる前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;//mod pにおける1,2,,,nの逆元
	for (int i = 2; i < MAX; ++i) {
		fac[i] = fac[i - 1] * i%INF;
		inv[i] = INF - inv[INF%i] * (INF / i) % INF;
		finv[i] = finv[i - 1] * inv[i] % INF;
	}
}

ll COM(int n, int k) {
	if (n < k)return 0;
	if (n < 0 || k < 0)return 0;
	return fac[n] * (finv[k] * finv[n - k] % INF) % INF;
}
double Euclidean_distance(double x1, double y1, double x2, double y2) {
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int prime[1001000];//i番目の素数
bool is_prime[1001010];//is_prime[i]がtrueならiは素数
					   //n以下の素数の数を返す
int sieve(int n) {
	int p = 0;
	for (int i = 0; i <= n; ++i) {
		is_prime[i] = true;
	}
	is_prime[0] = false;
	is_prime[1] = false;
	for (int i = 2; i <= n; ++i) {
		if (is_prime[i]) {
			prime[p] = i;
			p++;
			for (int j = 2 * i; j <= n; j += i) {
				is_prime[j] = false;
			}
		}
	}
	return p;
}

//素因数分解
map<int, int>prime_factor(int n) {
	map<int, int>res;
	for (int i = 2; i*i <= n; ++i) {
		while (n%i == 0) {
			++res[i];
			n /= i;
		}
	}
	if (n != 1)res[n] = 1;
	return res;
}


ll powmod(ll a, ll k,ll mod) {
	ll ap = a, ans = 1;
	while (k) {
		if (k & 1) {
			ans *= ap;
			ans %= mod;
		}
		ap = ap * ap;
		ap %= mod;
		k >>= 1;
	}
	return ans;
}
ll invi(ll a,ll mod) {
	return powmod(a, mod - 2,mod);
}
//逆元Aを足したときのmodで割った余りは
//+=invi(A)
///////////////////////////////////////

//dp[v][s]:=頂点vにいて所持金sという状態になるのに要する最小の所要時間
ll M=1e9+7;

int main(){
	ll c=100;
	ll f;
	cin>>f;
	ll to=0;
	while(c<f){
		c+=c/100;
		to++;
	}
	cout<<to;
}


Measured memory_bytes: 3724
#include <bits/stdc++.h>
#ifdef _DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif
#define REP(i, m, n) for(int (i) = (m); (i) < (n); ++i)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) for(int (i) = (n)-1; (i) >= 0; --i)
#define all(x) (x).begin(), (x).end()
#define FI first
#define SE second
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9+7;
const ll LINF = 1LL<<60;
template <class T, class U>
inline bool chmax(T &a, const U &b) {
  if(a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T, class U>
inline bool chmin(T &a, const U &b) {
  if(a > b) {
    a = b;
    return true;
  }
  return false;
}

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

int h, w;
vector<vector<bool>> vis;
vector<vector<int>> c;

void dfs(int y, int x) {
  if(vis[y][x]) return;
  vis[y][x] = true;
  rep(i,8) {
    int nx = x+dx[i];
    int ny = y+dy[i];
    if(nx < 0 || w <= nx || ny < 0 || h <= ny || !c[ny][nx]) continue;
    dfs(ny, nx);
  }
}

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  while(true) {
    cin >> w >> h;
    if(w == 0 && h == 0) break;
    c.assign(h, vector<int>(w));
    rep(i,h) rep(j,w) cin >> c[i][j];
    vis.assign(h, vector<bool>(w, false));
    int ans = 0;
    rep(i,h) rep(j,w) if(c[i][j] && !vis[i][j]) {
      ans++;
      dfs(i, j);
    }
    cout << ans << '\n';
  }
  return 0;
}


Measured memory_bytes: 3132
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
#define int ll

const int N = 2e5 + 10;
int t[4 * N];

void update(int v, int l, int r, int need, int val) {
  if (l == r) {
    t[v] = val;
    return;
  }
  int mid = (l + r) / 2;
  if (need <= mid) {
    update(2 * v, l, mid, need, val);
  }
  else {
    update(2 * v + 1, mid + 1, r, need, val);
  }
  t[v] = max(t[2 * v], t[2 * v + 1]);
}

int get_max(int v, int l, int r, int a, int b) {
  if (l > b || r < a) {
    return 0;
  }
  if (l >= a && r <= b) {
    return t[v];
  }
  int mid = (l + r) / 2;
  return max(get_max(2 * v, l, mid, a, b), get_max(2 * v + 1, mid + 1, r, a, b));
}

int sz;
int a[N], ans[N];
vector<int> g[N];

void dfs(int v, int p = 0) {
  pair<int, int> otk = {a[v], get_max(1, 1, sz, a[v], a[v])};
  update(1, 1, sz, a[v], get_max(1, 1, sz, 1, a[v] - 1) + 1);
  ans[v] = t[1];
  for (auto u : g[v]) {
    if (u != p) {
      dfs(u, v);
    }
  }
  update(1, 1, sz, otk.F, otk.S);
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  vector<int> srt;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    srt.pb(a[i]);
  }
  sort(all(srt));
  srt.resize(unique(all(srt)) - srt.begin());
  sz = SZ(srt);
  for (int i = 1; i <= n; i++) {
    a[i] = upper_bound(all(srt), a[i]) - srt.begin();
  }
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    g[u].pb(v);
    g[v].pb(u);
  }
  dfs(1);
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << '\n';
  }
}
    

Measured memory_bytes: 30776
#include<bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;
#define rep(i, N) for(int (i) = 0; (i) < (N); (i)++)
#define all(v) (v).begin(), (v).end()
#define eb emplace_back
#define Cout(s) cout << s << endl
string Yes(bool b) {if(b){return "Yes";} else {return "No";}}
string YES(bool b) {if(b){return "YES";} else {return "NO";}}

int main(){
	int N;
	cin >> N;

	int sum = 0;
	int i = 1;
	while(sum < N) sum += i++;

	for(int k = 1; k < i; k++){
		if(sum - N == k) continue;
		Cout(k);
	}
}


Measured memory_bytes: 256
// Template
#include <bits/stdc++.h>
#define rep_override(x, y, z, name, ...) name
#define rep2(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep3(i, l, r) for (int i = (int)(l); i < (int)(r); ++i)
#define rep(...) rep_override(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define per(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
constexpr int inf = 1001001001;
constexpr ll INF = 3003003003003003003LL;
template <typename T> inline bool chmin(T &x, const T &y) {if (x > y) {x = y; return 1;} return 0;}
template <typename T> inline bool chmax(T &x, const T &y) {if (x < y) {x = y; return 1;} return 0;}
struct IOSET {IOSET() {cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10);}} ioset;

// Mod-Int
constexpr int MOD = 1000000007;
struct ModInt {
    ll val;
    ModInt() = default;
    ModInt(ll x) : val(x % MOD + (x < 0 ? MOD : 0)) {}
    ModInt &operator+= (const ModInt &x) {if ((val += x.val) >= MOD) val -= MOD; return *this;}
    ModInt &operator-= (const ModInt &x) {if ((val -= x.val) < 0) val += MOD; return *this;}
    ModInt &operator*= (const ModInt &x) {(val *= x.val) %= MOD; return *this;}
    ModInt operator+ (const ModInt &x) const {return ModInt(*this) += x;}
    ModInt operator- (const ModInt &x) const {return ModInt(*this) -= x;}
    ModInt operator* (const ModInt &x) const {return ModInt(*this) *= x;}
    ModInt pow(ll t) const {
        if (!t) return ModInt(1);
        ModInt m = pow(t / 2);
        m *= m;
        if (t & 1) m *= *this;
        return m;
    }
    ModInt inv() const {return pow(MOD - 2);}
    ModInt &operator/= (const ModInt &x) {return *this *= x.inv();}
    ModInt operator/ (const ModInt &x) const {return ModInt(*this) /= x;}
    friend istream &operator>> (istream &is, ModInt &x) {is >> x.val; return is;}
    friend ostream &operator<< (ostream &os, const ModInt &x) {os << x.val; return os;}
};

int main() {
    int n;
    cin >> n;
    vector<char> s(2 * n);
    rep(i, 2 * n) cin >> s[i];
    
    int x = 0, a = 0, b = 0;
    ModInt ans(1);
    rep(i, 2 * n) {
        if (x & 1) {
            if (s[i] == 'W') {
                ++x;
                ++a;
            } else {
                ans *= ModInt(x);
                --x;
                ++b;
            }
        } else {
            if (s[i] == 'B') {
                ++x;
                ++a;
            } else {
                if (x == 0) {
                    cout << "0\n";
                    return 0;
                }
                ans *= ModInt(x);
                --x;
                ++b;
            }
        }
    }
    rep(i, 1, n + 1) ans *= ModInt(i);
    if (a != b) ans = ModInt(0);
    cout << ans << "\n";
}


Measured memory_bytes: 3716
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <cstdio>
#include <climits>
#include <complex>
#include <cstdint>
#include <tuple>

#define M_PI       3.14159265358979323846

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
inline int readInt() { int x; scanf("%d", &x); return x; }

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

//container util

//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a)*(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()


struct Edge {
    int to, cost, nm;
    Edge(int to, int cost, int nm): to(to), cost(cost), nm(nm) {}
};

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<Edge>> AdjList;
AdjList graph;
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
const int INF = 100000000;

ll GCD(ll a, ll b){
    if(a < b) swap(a, b);
    if(b == 0) return a;
    return GCD(b, a%b);
}

bool cmp(const pii& a, const pii& b){
    if(a.first == b.first){
        return a.second < b.second;
    }
    return a.first < b.first;
}

vector<string> matrix;
int main() {

    int n; cin >> n;
    for(int i=0; i<n; ++i){
        int hh, mm;
        scanf("%d:%d", &hh, &mm);
        double arg1 = (double)(hh*60 + mm)/2.0;
        double arg2 = (double)mm*6.0;

        double mini = fabs(arg1 - arg2);

        if(arg1 < arg2) arg1 += 360.0;
        else arg2 += 360.0;
        mini = min(mini, fabs(arg1 - arg2));
        if(mini < 30.0){
            cout << "alert" << endl;
        }else if(mini >= 90.0){
            cout << "safe" << endl;
        }else{
            cout << "warning" << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3132
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
    int k, n, ans = 0, may = 0;
    cin >> k >> n;
    int v[n];
    for(int i = 0; i < n; i++)
        cin >> v[i];
    vector<int> w;
    for(int i = 1; i < n; i++){
        w.push_back(v[i] - v[i - 1]);
        ans += (v[i] - v[i - 1]);
    }
    w.push_back((v[0] - v[n - 1] + k)% k);
    ans += ((v[0] - v[n - 1] + k)% k);
    sort(w.begin(), w.end());
    cout << ans - w[n - 1]<< "\n";
    return 0;
}


Measured memory_bytes: 2168
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<iomanip>
#include<complex>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef stack<int> SI;
typedef queue<int> QI;
typedef list<int> LI;
typedef pair<int,int> PII;
typedef long long LL;

#define d(x)  cout<<#x<<" = "<<(x)<<endl;
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define EP empty()
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define REACH(i,c) for(typeof((c).rbegin()) i=(c).rbegin(); i!=(c).rend(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c,n) sort(c,c+n)
#define VSORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define DFOR(i,b,a) for(int i=(b)-1;i>=(a);--i)
#define DREP(i,n) DFOR(i,n,0)
#define INF 1000000000
#define PI  acos(-1.0)
////////////////////////////////////////////////
int main()
{
	int c[4][4]={0};
	for(int i=1;i<4;i++)
	{
		for(int j=1;j<4;j++)
		{
			cin>>c[i][j];
		}
	}
	int ans=0;
	for(int i=1;i<3;i++)
	{
		for(int j=2;j<4;j++)
		{
			ans+=!(c[i+1][j]-c[i][j]==c[i+1][1]-c[i][1]);
		}
	}
	for(int i=1;i<3;i++)
	{
		for(int j=2;j<4;j++)
		{
			ans+=!(c[j][i+1]-c[j][i]==c[1][i+1]-c[1][i]);
		}
	}
	if(ans==0)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
//#define _USE_MATH_DEFINES
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
#pragma GCC diagnostic ignored "-Wmissing-declarations"
#define FINAL_OUT(x) {cout << (x) << '\n'; exit(0); }
inline int safe_mul(const int x, const int y) __attribute__ ((warn_unused_result));


int main()
{
//    freopen("in.txt","r", stdin);
//    freopen("out.txt", "w", stdout);
//    cin.tie(0);
//    cout << fixed << setprecision(20);
    ios_base::sync_with_stdio(false);
    cin.tie(0);


    int w,h;
    cin >> h >> w;
    vector<string> grid(h);
    for (auto& s : grid)
        cin >> s;

    vector<int> dx = {-1, 1, 0, 0};
    vector<int> dy = {0, 0, -1, 1};
    vector<vector<int>> dist(h, vector<int>(w, 1000000));

    queue<pair<int,int> >que;
    for (int i = 0; i < h; ++i)
    for (int j = 0; j < w; ++j)
        if (grid[i][j] == '#') {
            dist[i][j] = 0;
            que.push({i,j});
        }

    while (!que.empty()) {
        int x,y;
        tie(x,y) = que.front();
        que.pop();
        int d = dist[x][y];
        for (int k = 0; k < 4; ++k) {
            int sx = x + dx[k];
            int sy = y + dy[k];
            if (sx >= 0 && sx < h && sy >= 0 && sy < w && dist[sx][sy] > d + 1) {
                dist[sx][sy] = d + 1;
                que.push({sx, sy});
            }
        }
    }

    int ans = 0;
    for (const auto& vec : dist)
        ans = max(ans, *max_element(begin(vec), end(vec)));
    cout << ans << endl;
}


Measured memory_bytes: 13456
import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))
 
def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)
 
 
if __name__ == "__main__":
    main()

Measured memory_bytes: 65072
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
const double EPS=1e-8;
const double PI=acos(-1);
const int N=105;
int n;double x[N],y[N],z[N];
bool vis[N];
struct Node {
    double x,y;int id;
    Node(double x=0,double y=0,int id=0):x(x),y(y),id(id){}
    bool operator < (const Node &b) const {
        if(x!=b.x) return x<b.x;
        return y<b.y;
    }
    Node operator - (const Node &b) {
        return Node(x-b.x,y-b.y);
    }
    double det(const Node &b) {
        return x*b.y-y*b.x;
    }
    double dot(const Node &b) {
        return x*b.x+y*b.y;
    }
    double dis() {
        return sqrt(x*x+y*y);
    }
}point[N],ans[N];
int solve(int num) {
    std::sort(point,point+num);
    int k=0;
    for(int i=0;i<num;i++) {
        while(k>1&&(ans[k-1]-ans[k-2]).det(point[i]-ans[k-1])<EPS) k--;
        ans[k++]=point[i];
    }
    for(int i=num-2,t=k;~i;i--) {
        while(k>t&&(ans[k-1]-ans[k-2]).det(point[i]-ans[k-1])<EPS) k--;
        ans[k++]=point[i];
    }
    return k;
}
double res[N];
int main() {
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%lf%lf",&point[i].x,&point[i].y),point[i].id=i;
    int num=solve(n)-1;
    for(int i=0;i<n;i++) res[i]=0;
    if(num==2) res[ans[0].id]=res[ans[1].id]=0.5;
    else {
        double tmp;
        tmp=(ans[0]-ans[num-1]).dot(ans[0]-ans[1]);
        tmp=acos(tmp/(ans[0]-ans[num-1]).dis()/(ans[0]-ans[1]).dis());
        res[ans[0].id]=(PI-tmp)/PI/2;
        tmp=(ans[num-1]-ans[0]).dot(ans[num-1]-ans[num-2]);
        tmp=acos(tmp/(ans[num-1]-ans[num-2]).dis()/(ans[num-1]-ans[0]).dis());
        res[ans[num-1].id]=(PI-tmp)/PI/2;
        for(int i=1;i<num-1;i++) {
            tmp=(ans[i]-ans[i-1]).dot(ans[i]-ans[i+1]);
            tmp=acos(tmp/(ans[i]-ans[i-1]).dis()/(ans[i]-ans[i+1]).dis());
            res[ans[i].id]=(PI-tmp)/PI/2;
        }
    }
    for(int i=0;i<n;i++) printf("%.12f\n",res[i]);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define show(x) for(auto i: x){cout << i << " ";}
typedef long long ll;

long mod = 1000000007;

/* C++の構造体 メンバがpublicなclass */
typedef struct mint
{
    ll x;
    mint(ll x = 0) : x(x % mod) {} //コンストラクタ
    /* 演算子オーバーロード */
    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
    {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint a) const
    {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint a) const
    {
        mint res(*this);
        return res *= a;
    }
    mint pow(ll t) const
    {
        if (!t)
            return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1)
            a *= *this;
        return a;
    }
    // for prime mod
    mint inv() const
    {
        return pow(mod - 2);
    }
    mint &operator/=(const mint a)
    {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const
    {
        mint res(*this);
        return res /= a;
    }
} mint_t;

int main()
{
    int n;
    cin >> n;
    vector<int> a;
    rep(i, n){ int tmp; cin >> tmp; a.push_back(tmp);}
    sort(a.begin(), a.end());


    vector<mint> mutplus;
    mint tmp(1);
    rep(i, n + 1){
        mutplus.push_back(tmp);
        tmp *= 2;
    }
    mint ans(0);
    mint mut(0);
    if (n == 1){
        ans = (mint)a[0] * 2;
        cout << ans.x << endl;
        return 0;
    }
    rep(i, n){
        mut = mutplus[n-1] + mutplus[n-2] * (mint)(n-1-i);
        //cout << mut.x << endl;
        ans += mut * a[i];
    }
    ans *= mutplus[n];

    cout << ans.x << endl;
}



Measured memory_bytes: 3188
#if 0
2020.03.21

考虑一个暴力的贪心做法，从大到小枚举 S = x + y + z ，
然后对于所有 (x, y, z) ，如果之前没有与之连边的点被选，那么这个点一定要出现在最优解中。
可以给边定向，边从小连到大，那么整个图就是 DAG ，在 DAG 中抽象这个贪心：
每次选择一个点满足其到的点都没有被选，然后删掉选择它加入最优解集合。
那么一个点被选当且仅当其到的点都没被选，一个点没被选当且仅当其到的点存在被选的点（或没有出度）。
这可以对应到博弈中的必胜必败态，这个 DAG 可以看做博弈转移图，答案就是求所有必败态的权值和。

然而点数很大。
考虑对于一个 (x, y, z) ，如何快速求出其必胜必败态，
每次移动只能移动一维，这个博弈三维独立，就相当于每个维度有一个子游戏。
对于每一维求出 SG 值 f[x], g[y], h[z] ，三者异或和就是这个的 SG 值。
考虑计数，FWT 做异或卷积即可（事实上也可以三维暴力枚举 SG 值，SG 值的上界是 O(sqrt(M)) 的）。
#endif
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;

struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
} read;

const int maxn = 200005, mod = 998244353;
std::vector<int> G[maxn];
int sg[3][maxn];
ll f[3][maxn], g[maxn];
ll po[maxn * 3];

void FWT (ll *a, int n) {
	for (int m = 1; m < n; m <<= 1)
		for (int i = 0; i < n; i += m << 1)
			for (int k = i; k < i + m; k ++) {
			ll x = a[k], y = a[k + m];
			(a[k] = x + y) %= mod;
			(a[k + m] = x + mod - y) %= mod;
		}
}

void iFWT (ll *a, int n) {
	FWT(a, n);
	ll inv = mod - (mod - 1) / n;
	for (int i = 0; i < n; i ++)
		(a[i] *= inv) %= mod;
}

int main () {
	int n = read, len = 1;
	while (len < n)
		len <<= 1;

	po[0] = 1;
	ll bs = 1000000000000000000ll % mod;
	for (int i = 1; i <= n * 3; i ++)
		po[i] = po[i - 1] * bs % mod;

	for (int o = 0; o < 3; o ++) {
		int m = read;
		for (int i = 1; i <= n; i ++)
			G[i].clear();
		for (int i = 1; i <= m; i ++) {
			int u = read, v = read;
			if (u < v) G[u].push_back(v);
			if (v < u) G[v].push_back(u);
		}
		for (int i = n; i; i --) {
			std::set<int> mex;
			for (int j : G[i])
				mex.insert(sg[o][j]);
			while (mex.count(sg[o][i]))
				++ sg[o][i];
		}
		for (int i = 1; i <= n; i ++)
			(f[o][sg[o][i]] += po[i]) %= mod;
		/* FWT(f[o], len); */
	}

	ll ans = 0;
	for (int i = 0; i < 500; i ++)
		for (int j = 0; j < 500; j ++)
			(ans += f[0][i] * f[1][j] % mod * f[2][i ^ j]) %= mod;
	printf("%lld\n", ans);

/* 	for (int i = 0; i < len; i ++) */
/* 		g[i] = f[0][i] * f[1][i] % mod * f[2][i] % mod; */
/* 	iFWT(g, len); */

/* 	printf("%lld\n", g[0]); */
}


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

int n,a[10000+10];

int min(int a,int b){
    if(a<=b) return a;
    return b;
}

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

int compm(int n){
    if (n==0) return a[0];
    return min(a[n-1],compm(n-1));
}

int compM(int n){
    if (n==0) return a[0];
    return max(a[n-1],compM(n-1));
}

long int sum(int n){
    if (n==0) return 0;
    return a[n-1]+sum(n-1);
}

int main(){
    cin >> n;
    for(int i=0;i<n;i++) cin >> a[i];
    cout << compm(n) << " " << compM(n) << " " << sum(n) << endl;
}

Measured memory_bytes: 3264
N,M = map(int,input().split())
HN = list(map(int,input().split()))
X = []
for i in range(N):
    X += [1]
for i in range(M):
    A,B = list(map(int,input().split()))
    if HN[A-1] > HN[B-1]:
        X[B-1]=0 
    elif HN[A-1] < HN[B-1]:
        X[A-1]=0
    else:
        X[A-1],X[B-1]= 0,0
print(sum(X))

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

#define pb push_back
#define ff first
#define ss second

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

const int MAXN = 2 * 100 * 1000 + 17;

int n, a[MAXN];
map<int, int> mp;

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i], mp[a[i]]++;
	for (int i = 1; i <= n; i++)
		if (mp[a[i]] > 1)
			return cout << "NO" << endl, 0;
	cout << "YES" << endl;
	return 0;
}


Measured memory_bytes: 10368
#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define RREP(i,a,b) for(int i=(a);i>=(b);i--)
#define pq priority_queue
#define P pair<int,int>
#define P2 pair<int,P>
#define P3 pair<int,P2>
typedef long long ll; typedef long double ld;
using namespace std;
const int INF=1e9, MOD=1e9+7, around[]={0,1,1,-1,-1,0,-1,1,0,0};
const int vx[]={1,0,-1,0}, vy[]={0,1,0,-1};
const ll LINF=1e18;
const ld PI=abs(acos(-1));

int main(){
	string s; cin >> s;
	reverse(s.begin(), s.end());
	
	int pos = 0;
	REP(i,0,s.size() - s.size() % 2){
		pos += max((s[i+1] - '0' - 1) + 9, (s[i] - '0') + (s[i + 1] - '0'));
		i++;
	}
	
	if(s.size() % 2) pos += s[s.size() - 1] - '0';
	
	cout << max<int>(pos, (s[s.size() - 1] - '0' - 1) + (s.size() - 1)*9) << endl;
	return 0;
}


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

int *s;
int *t;
int n, q;


bool bin_search(int key){
  int left, right, mid;
  left = 0;
  right = n;
  while(left < right){
    mid = (left + right) / 2;
    if(key == s[mid]) return true;
    if(key < s[mid]) right = mid;
    else left = mid+1;
  }
  return false;
}

void solve(){
  int count = 0;
  sort(s, s+n);
  sort(t, t+q);
  for(int i = 0; i < q; i++){
      if(bin_search(t[i])){
        count++;
    }
  }
  cout << count << endl;
  return ;
}


int main(){
  cin >> n;
  s = new int[n];
  for(int i = 0; i < n; i++) cin >> s[i];
  cin >> q;
  t = new int[q];
  for(int i = 0; i < n; i++) cin >> t[i];
  solve();
  return 0;
}

Measured memory_bytes: 3560
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 k = sc.nextInt();

		int cnt = 0;
		int ans = 100;

		while (true) {
			if (a % ans == 0 && b % ans == 0) {
				cnt++;
			}
			if (cnt == k) {
				break;
			}
			ans--;
			if (ans < 0) {
				break;
			}
		}

		System.out.println(ans);

		sc.close();
	}
}


Measured memory_bytes: 21844
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>
#include <ios>
#include <cctype>
#include <cstdio>
#include <functional>
#include <cassert>
#include <fstream>
#include <ctime>

using namespace std;
using ll = long long;

#define REP(i,a) for(int i = 0;i < (a);++i)
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define FORR(i,a,b) for(int i = (a) - 1;i >=(b);--i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SIZE(obj) (int)(obj).sizeT()
#define YESNO(cond,yes,no){cout <<((cond)?(yes):(no))<<endl; }
#define SORT(list) sort(ALL((list)));
#define RSORT(list) sort((list).rbegin(),(list).rend())
#define ASSERT(cond,mes) assert(cond && mes)

constexpr int MOD = 1'000'000'007;
constexpr int INF = 1'050'000'000;

template<typename T>
T round_up(const T& a, const T& b) {
    return (a + (b - 1)) / b;
}

template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
}

template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2>& p) {
    os << p.first << p.second;
    return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    REP(i, (int)v.size())is >> v[i];
    return is;
}

template <typename T>
T clamp(T& n, T a, T b) {
    if (n < a)n = a;
    if (n > b)n = b;
    return n;
}

template <typename T>
static T GCD(T u, T v) {
    T r;
    while (v != 0) {
        r = u % v;
        u = v;
        v = r;
    }
    return u;
}

template <typename T>
static T LCM(T u, T v) {
    return u / GCD(u, v) * v;
}

std::vector<int> enum_div(int n) {
    std::vector<int> ret;
    for (int i = 1; i*i <= n; ++i) {
        if (n%i == 0) {
            ret.push_back(i);
            if (i != 1 && i*i != n) {
                ret.push_back(n / i);
            }
        }
    }
    return ret;
}

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

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

struct ToUpper {
    char operator()(char c) { return toupper(c); }
};

struct ToLower {
    char operator()(char c) { return tolower(c); }
};

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

    string S, T;
    cin >> S >> T;
    int ans = 0;
    REP(i, 3) {
        if (S[i] == T[i]) {
            ans++;
        }
    }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define INF 1000000007
//0=48,A=65,a=97

int main() {
    int n;cin >> n;
    ll ten=1,nine=1,eight=1;
    for(int i = 0; i < n; i++) {
        ten *= 10;
        ten %= INF;
    }
    for(int i = 0; i < n; i++) {
        nine *= 9;
        nine %= INF;
    }
    for(int i = 0; i < n; i++) {
        eight *= 8;
        eight %= INF;
    }

    ll ans = ten + eight -2*nine;

    if(ans < 0){
        ll b = abs(ans / INF) + 1;
        ans += b * INF;
    }
    if(ans >= INF){
        ll b = ans/INF;
        ans -= b*INF;
    }

    cout << ans << endl;

    return 0;
}

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

using namespace std;
using lli = long long int;

vector<lli> vec[10] = {};

lli p[10] = {};
lli swi[10] = {};

int main(void) {

	lli N, M;
	cin >> N >> M;
	cout << (N * 3 + M) / 2 << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
typedef long long ll;
using namespace std;

int main() {
    int n, j=0;
    double x, b=0;
    string u;
    cin >> n;
    for(int i=0; i<n; i++) {
        cin >> x >> u;
        if(u=="JPY") j+=(int)x;
        if(u=="BTC") b+=x;
    }
    b *= 380000;
    cout << j + b << endl;
    return 0;
}

Measured memory_bytes: 256
main=print.solve=<<(getLine>>getLine)
solve=g.scanr f(0,0)
f 'E'(e,w)=(e+1,w)
f 'W'(e,w)=(e,w+1)
g a@((_,w):_)=minimum$(zipWith(\(e2,_) (_,w2)->w-w2+e2)=<<tail)a

Measured memory_bytes: 66164
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
#define endl '\n'
typedef pair<int, int> pii;

unordered_set<int> vis;
queue<int> q[N];
queue<pii> Q, nQ;

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int n, sum, cnt, temp;
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j < n; j++) {
			cin >> temp;
			q[i].push(temp);
		}
	for (int i = 1; i <= n; i++) {
		int cp = q[i].front();
		if (vis.find(i) == vis.end() && vis.find(cp) == vis.end() && i == q[cp].front()) {
			Q.push({ i,cp });
			q[i].pop();
			q[cp].pop();
			vis.insert(i);
			vis.insert(cp);
			cnt += 2;
		}
	}
	sum = cnt= 0;
	while (1) {
		if (Q.empty()) {
			if (cnt == n * (n - 1)) {
				cout << sum << endl;
				return 0;
			}
			else {
				cout << -1 << endl;
				return 0;
			}
		}
		vis.clear();
		while (!Q.empty()) {
			pii p = Q.front();
			Q.pop();
			cnt+=2;
			if (vis.find(p.first) == vis.end() && !q[p.first].empty()) {
				int cp = q[p.first].front();
				if (vis.find(cp) == vis.end() &&p.first==q[cp].front()) {
					nQ.push({ p.first,cp });
					q[p.first].pop();
					q[cp].pop();
					vis.insert(p.first);
					vis.insert(cp);
				}
			}
			if (vis.find(p.second) == vis.end() && !q[p.second].empty()) {
				int cp = q[p.second].front();
				if (vis.find(cp) == vis.end() &&p.second==q[cp].front()) {
					nQ.push({ p.second,cp });
					q[p.second].pop();
					q[cp].pop();
					vis.insert(p.second);
					vis.insert(cp);
				}
			}
		}
		sum++;
		while (!nQ.empty()) {
			Q.push(nQ.front());
			nQ.pop();
		}
	}
	return 0;
}

Measured memory_bytes: 4736