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

const int A = 1000005;

int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> c(A);
    
    for (int i = 0; i < n; i++ ) {
        cin >> a[i];
        c[a[i]]++;
    }
    int pairwise = true;
    for (int i = 2; i < A; i++) {
        int cnt = 0;
        for (int j = i; j < A; j += i) {
            cnt += c[j];
        }
        if (cnt > 1) {
            pairwise = false;
            break;
        }
    }
    if (pairwise) {
        cout << "pairwise coprime" << endl;
        return 0;
    } else {
        int g = 0;
        for (int i = 0; i < n; i++) {
            g = gcd(g, a[i]);
            if (g == 1) {
                cout << "setwise coprime" << "\n";
                return 0;
            }
        }
    }
    cout << "not coprime" << "\n";
    return 0;
}

Measured memory_bytes: 11100
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<limits.h>

#define rep(i,begin,end) for(int i=begin; i<end; i++)
#define revrep(i,begin,end) for(int i=begin; i>end; i--)
#define lld long long int

int main(){
    char c;
    scanf("%c", &c);
    printf("%c", c+1);

    return 0;
}

Measured memory_bytes: 128
#include <stdio.h>

#define ARC(i, a, b) for(int i = (a); i < (b); ++i)
#define RC(i, n) ARC(i, 0, n)
#define ARCH(i, a, b) for(int i = (a) - 1; i >= (b); --i)
#define RCH(i, n) ARCH(i, n, 0)

template <class T>
T ath(const T &a, const T &b){
	return a > b ? a : b;
}

int solve(){
	int n, v[2][110000] = {}, av[2], inav[2], aav[2];
	scanf("%d", &n);
	RC(i, n / 2) RC(j, 2){
		int in;
		scanf("%d", &in);
		++v[j][in];
		if(av[j] < v[j][in]){
			if(inav[j] != in) aav[j] = av[j];
			av[j] = v[j][in];
			inav[j] = in;
		}else if(aav[j] < v[j][in]) aav[j] = v[j][in];
	}
	return n - (inav[0] != inav[1] ? av[0] + av[1] : ath(av[0] + aav[1], av[1] + aav[0]));
}

int main(){
	printf("%d\n", solve());
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define l1 long long
using namespace std;
struct Int{
    l1 x,y;
};
bool com(Int i1,Int i2)
{
    return i1.x<i2.x;
}
int main()
{
    l1 n,k,i,j;
    cin>>n>>k;
    Int a[n];
    for(i=0;i<n;i++) cin>>a[i].x>>a[i].y;
    sort(a,a+n,com);
    l1 dp[n][k+1];
    for(i=0;i<n;i++) for(j=0;j<k+1;j++) dp[i][j]=0;
    l1 max1=0,p=0;
     for(i=a[0].x;i<=k;i++) {dp[0][i]=a[0].y;if(dp[0][i]>max1) max1=dp[0][i];}
    for(i=1;i<n;i++)
    {
        for(j=0;j<k+1;j++) {
            if(j<a[i].x) {dp[i][j]=dp[i-1][j];continue;}
           dp[i][j]=max(dp[i-1][j],a[i].y+dp[i-1][j-a[i].x]);
          if(dp[i][j]>max1) max1=dp[i][j];
        }
    }
    //for(i=0;i<n;i++) {for(j=0;j<=k;j++) cout<<dp[i][j]<<" "; cout<<endl;}
    cout<<max1;
}

Measured memory_bytes: 81680
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <numeric>
#include <algorithm>
#include <functional>

using namespace std;

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

	int A, B;
	cin >> A >> B;

	A *= 3;
	A += B;

	cout << A / 2;

	return 0;
}


Measured memory_bytes: 3656
#include <iostream>
#include <algorithm>

using namespace std;

#define FOR(i,m,M) for(int i = m;i<M;i++)

int main()
{
	int A,B;
	cin >> A >> B;
	if (A > 0 && A <= 9 && B > 0 && B <= 9)
		cout<< A * B;
	else cout<<- 1;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<stdlib.h>


int main(void){
    int D,N;
    scanf("%d %d",&D,&N);
    int num;
    num = pow(100,D);
    if(N == 100){
        printf("%d\n",num * 101);
    }   
    else{
        printf("%d\n",num * N);
    } 
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
  int n;cin>>n;
  int A[n][10];
  for(int i = 0; n > i; i++){
    for(int j = 0; 10 > j; j++){
      cin>>A[i][j];
    }
  }
  int Z[n][11];
  for(int i = 0; n > i; i++){
    for(int j = 0; 10 >= j; j++){
      cin>>Z[i][j];
    }
  }
  int ans = -1000000001;
  for(int bit = 1; (1<<10) > bit; bit++){
    int tmp = 0;
    for(int i = 0; n > i; i++){//
     int same = 0;
      for(int j = 0; 10 > j; j++){
        if((bit & (1<<j)) && A[i][j]){
          same++;
        }
      }
      tmp += Z[i][same];
    }
    ans = max(ans,tmp);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
def main():
    D = int(input())
    fuman = list(map(int, input().split()))
    manzoku = [[0]*26 for _ in range(D)]
    for i in range(D): manzoku[i] = list(map(int, input().split()))
    # できるだけ点数が下がらないように、満足度の高いものを選んでいく
    # d日目にテストiを受けた時、score += manzoku[d][i]-sigma[i以外25個](fuman[k]*それを受けてない日数)
    # >テストiをd日目に受ける
    # manzoku[d][i]-sigma[i以外25個](fuman[k]*それを受けてない日数)が一番大きいもの(i)を受けるそれだけ
    timepass = [0]*26
    # 最初m日のみ指定
    m = 2
    x,t = 0,0
    for j in range(26):
        tmp = manzoku[i][j]
        if tmp>x:
            x = tmp
            t = j
    for _ in range(m):
        for j in range(26):
            if not j==t: timepass[j] += 1
            else: timepass[j] = 0
        print(t+1)
    for i in range(m,D):
        # greedy
        x1 = 0
        t1 = 0
        for j in range(26):
            tmp = manzoku[i][j]
            for k in range(26):
                if not j==k: tmp -= fuman[k]*timepass[k]
            if tmp>x1:
                x1 = tmp
                t1 = j

        # update timepass
        for j in range(26):
            if not j==t1: timepass[j] += 1
            else: timepass[j] = 0
        print(t1+1)



main()


Measured memory_bytes: 9512
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define sll            set<ll int>
#define msll        multiset<ll int>
#define io    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;


int main()
{
    io
    ll i,j,n;
    string s;
    map<char,ll> mm;
    cin>>n>>s;
    for(auto it:s){
        mm[it]++;
    }
    if(mm['R']>mm['B']) cout<<"Yes";
    else cout<<"No";






    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

using namespace std;

int a[2000];
int n;

bool solve(int m, int i){
    if(m == 0){
        return true;
    }
    else if(i == n){
        return false;
    }
    return solve(m, i+1) || solve(m-a[i], i+1);
}

int main(){

    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    int q;
    scanf("%d", &q);

    for(int i = 0; i < q; i++){
        int m;
        scanf("%d", &m);

        if(solve(m, 0)){
            printf("yes\n");
        }
        else{
            printf("no\n");
        }
    }
}


Measured memory_bytes: 2624
import           Control.Monad
import           Data.Array.IO
import qualified Data.ByteString.Char8 as B
import           Data.Char
import           Data.List

readInts :: IO [Int]
readInts = unfoldr (B.readInt . B.dropWhile isSpace) <$> B.getLine

main :: IO ()
main = do
  [n, m, k] <- readInts
  a_ary <- newArray ((0, 0), (n, n)) 0 :: IO (IOUArray (Int, Int) Int)
  b_ary <- newArray ((0, 0), (n, n)) 0 :: IO (IOUArray (Int, Int) Int)
  lrs <- replicateM m readInts
  pqs <- replicateM k readInts

  forM_ lrs $ \[l, r] ->
    writeArray a_ary (l, r) =<< (+1) <$> readArray a_ary (l, r)

  forM_ [1..n] $ \i ->
    forM_ [1..n] $ \j ->
      writeArray b_ary (i, j) =<< (\x y z w -> x + y - z + w)
        <$> readArray b_ary (i-1, j)
        <*> readArray b_ary (i, j-1)
        <*> readArray b_ary (i-1, j-1)
        <*> readArray a_ary (i, j)

  forM_ pqs $ \[p, q] ->
    print =<< (\x y z w -> x - y - z + w)
      <$> readArray b_ary (q, q)
      <*> readArray b_ary (p-1, q)
      <*> readArray b_ary (q, p-1)
      <*> readArray b_ary (p-1, p-1)

Measured memory_bytes: 77180
#include<iostream>
#include<map>
using namespace std;
typedef long long ll;

map<int, int>seq;
map<int, int>::iterator it;
int main() {
	int n;
	scanf("%d", &n);
	int temp;
	ll sum = 0;
	for (int i = 0; i < n; i++) {
		scanf("%d", &temp);
		sum += temp;
		seq[temp]++;
	}
	int Q, B, C;
	scanf("%d", &Q);
	for (int i = 0; i < Q; i++) {
		scanf("%d%d", &B, &C);
		it = seq.find(B);
		if (it != seq.end()) {
			sum += (C - B) * (it->second);
			seq[C] += it->second;
			it->second = 0;
		}	
		printf("%lld\n", sum);
	}
	return 0;
}

Measured memory_bytes: 7560
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

int main() {
    ll n, m;
    cin >> n >> m; 
    
    vvl G(n);
    vl indeg(n);  // indeg[v] : 頂点vの入次数
    rep(i, n-1+m) {
        ll a, b;
        cin >> a >> b;
        a--;  b--;
        G[a].pb(b);
        indeg[b]++;
    }

    queue<ll> Q;
    rep(v, n) {
        if(indeg[v] == 0) {
            Q.push(v);
        }
    }

    // BFS。計算量はO(V+E)
    vl ans(n);  // par[v] : 頂点vの親(1-index)
    while(!Q.empty()) {
        ll v = Q.front();
        Q.pop();
        for(auto u : G[v]) {
            indeg[u]--;
            if(indeg[u] == 0) {
                ans[u] = v+1;
                Q.push(u);
            }
        }
    }
    
    rep(v, n) {
        out(ans[v]);
    }

    re0;
}

Measured memory_bytes: 7808
/*
    STARK_BOY
*/
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repe(i,a,b) for(ll i=a;i<=b;i++)
#define bac(i,a,b) for(ll i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long ll;
typedef vector< ll > vi;
typedef vector<pair<ll,ll> > vpii;
typedef pair<ll,ll> pii;
#define all(c) c.begin(),c.end()
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define setbitc(x) __builtin_popcount(x)
#define init(x,a) memset(x,a,sizeof(x))
#define PI           3.14159265358979323846  /* pi */
mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
#define N 1000005
//Variables Start
ll inf=1e18,MOD=1e9+7;
ll n,m,k,ar[N],br[N];
string s,s1;
//Variables End

int main()
{
    ios
    int ti=1;
    //cin>>ti;
    while(ti--)
    {
		cin>>n>>m;
	    vi dp(m+1,-inf);
		vpii bags(n+1,{0,0});
		dp[0]=0;
		rep(i,1,n+1)cin>>bags[i].F>>bags[i].S;


		rep(i,1,n+1)
		{
			ll w=bags[i].F;
			ll val=bags[i].S;
			bac(j,m,w)
			{	
				dp[j]=max(dp[j],dp[j-w]+val);
			}

			//rep(j,0,m+1)cout<<dp[j]<<" ";
			//cout<<endl;
		}
		/*rep(j,1,m+1)
		{
			rep(i,1,n+1)
			{
				if(bags[i].F<=j)
				dp[j]=max(dp[j],dp[j-bags[i].F]+bags[i].S);
			}
		}*/

		ll ans=0;
		rep(i,1,m+1)ans=max(ans,dp[i]);

		cout<<ans<<endl;

    }
    return 0;
        
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int n,ans,maxn;
int a[200005],g[1000005];
bool f[1000005];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		g[a[i]]++;
		maxn=max(maxn,a[i]);
	}
	for(int i=1;i<=n;i++)
		for(int j=a[i]+a[i];j<=maxn;j+=a[i])
			f[j]=true;
	for(int i=1;i<=n;i++)
		if(!f[a[i]]&&g[a[i]]==1)
			ans++;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 9308
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
const ll MOD=1000000007;
const long double PI=3.14159265358979;
const ll MAX=0;

int main() {
  ll x,n,t;
  cin>>n>>x>>t;
  cout<<((n-1)/x+1)*t;
}


Measured memory_bytes: 3620
n=int(input())
a=list(map(int,input().split()))
a.sort()

x=0
y=0
i=0

while(i<n):
    if x==0 and a[n-1-i]==a[n-2-i]:
        x=a[n-1-i]
        i+=2
        continue
    if x>0 and y==0 and a[n-1-i]==a[n-2-i]:
        y=a[n-1-i]
        break
    i+=1
print(x*y)

Measured memory_bytes: 14244
#include <stdio.h>
#include <string.h>

int main(){
    char s[100];
    char t[100];
    char st[200];
    int n;
    int i;
    int a;
    scanf("%d",&n);
    scanf("%s%s",t,s);
    for(i=0;i<100;i++){
        st[2*i]=t[i];
        st[2*i+1]=s[i];
    }
    a=strlen(st);
    
    for(i=0;i<a;i++){
        printf("%c",st[i]);
    }
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int ctoi(const char c){
  switch(c){
    case '0': return 0;
    case '1': return 1;
    case '2': return 2;
    case '3': return 3;
    case '4': return 4;
    case '5': return 5;
    case '6': return 6;
    case '7': return 7;
    case '8': return 8;
    case '9': return 9;
    default : return -1;
  }
}

int main(){
  string S; cin >> S;
  int k=S.size();
  if(k<4){
    cout << 0 << endl;
    return 0;
  }
  int count=0;
  vector<int> A(2019,0);
  vector<int> B(2019,0);
  vector<int> C(2019,0);
  A[ctoi(S[0])]++;
  for(int i=1;i<k;i++){
      A[0]++;
    for(int j=0;j<2019;j++){
      if(A[j]!=0){
        int x=(j*10+(ctoi(S[i])))%2019;
        if(x==0){
          count+=A[j];
        }
        B[x]+=A[j];
        A[j]=0;
      }
    }
    A=B;
    B=C;
  }
  cout << count << endl;
  return 0;
}  
      
    

Measured memory_bytes: 3756
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//--<for debugging>
#define whatis(x) cout << #x << " is " << x<<" ";
#define whatisl(x) cout << #x << " is " << x<<"\n";
#define parr(array,end)for(ll loop=0;loop<end;loop++)cout<<array[loop]<<" ";cout<<"\n";
#define lline cout<<"\n";
#define errorl(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);cout<<"\n";}
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);cout<<"___";}
    
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << *it << " = " << a <<" , ";
    err(++it, args...);
}
//--</for debugging> 
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define testcase ll tt; cin >> tt; while(tt--)
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back 
#define vars ll h,i,j,k,d,l,p,q,r,x,y,a,b,c,v,var,n,m,z,s,ans,ind1,ind2,flag,limit1,limit2,limit3,mod;
#define vll vector<ll>
#define pll pair<ll,ll>
#define sll set<ll>
#define pint pair<int,int>
const ll INF=1e9+7;
const ll MOD=1e9+7;
int main()
{
    boost vars
    cin>>a>>b>>c>>k;
    ans=0;
    v=k;
    k=max(0ll,k-a);
    ans=ans+min(a,v);
    k=max(0ll,k-b);
    v=k;
    k=max(0ll,k-c);
    ans=ans-min(c,v);
    cout<<ans;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 4005;
const ll MOD = 998244353;

int n, k;
ll _C[N][N], pw2[N];

ll C(int n, int k) {
  if (n < 0 || k < 0) return 0;
  return _C[n][k];
}

int main() {
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  _C[0][0] = pw2[0] = 1;
  for (int i = 1; i <= 4000; ++i) {
    _C[i][0] = 1;
    pw2[i] = (pw2[i - 1] << 1) % MOD;
    for (int j = 1; j <= i; ++j) {
      _C[i][j] = (_C[i - 1][j] + _C[i - 1][j - 1]) % MOD;
    }
  }

  cin >> k >> n;
  for (int i = 2; i <= 2 * k; ++i) {
    int p = 0;
    ll ans = 0;
    for (int j = 1; j <= k; ++j) {
      if (1 <= i - j && i - j <= k) ++p;
    }
    p /= 2;
    if (i & 1) {
      for (int q = 0; q <= p; ++q) {
        (ans += (((C(p, q) * pw2[q]) % MOD) * C(n + k - 2 * p - 1, q + k - 2 * p - 1)) % MOD) %= MOD;
      }
    } else {
      for (int q = 0; q <= p; ++q) {
        (ans += (((C(p, q) * pw2[q]) % MOD) * C(n + k - 2 * p - 2, q + k - 2 * p - 2)) % MOD) %= MOD;
        (ans += (((C(p, q) * pw2[q]) % MOD) * C(n + k - 2 * p - 3, q + k - 2 * p - 2)) % MOD) %= MOD;
      }
    }
    cout << ans << "\n";
  }
  return 0;
}

Measured memory_bytes: 123776
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
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 (b<a) {a=b; return 1;} return 0;}

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

    int h, w;
    cin >> h >> w;
    int n;
    cin >> n;
    int mx = max(h, w);
    cout << (n + mx - 1) / mx << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

int main() {
  int x, y, z;
  cin >> x >> y >> z;
  cout << z << ' ' << x << ' ' << y << endl;
  return 0;
}

Measured memory_bytes: 256
/*author: hyperion_1724
  date: 
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define READ(X) cin>>X;
#define READV(X) long long X; cin>>X;
#define READAR(A,N) long long A[N]; for(int i=0;i<N;i++) {cin>>A[i];}
#define rz(A,N) A.resize(N);
#define sz(X) (long long)(X.size())
#define pii pair<int,int>
#define pll pair<long,long>
#define fi first
#define se second
#define trav(x,A) for(auto &x:A)
#define veci vector<int>
#define vecl vector<long long>
#define FORI(a,b,c) for(int a=b;a<c;a++)
#define FORD(a,b,c) for(int a=b;a>c;a--)
#define adj(N) vector<vector<int>> ADJ(N+1)

ll bit[100010]={0};
ll dp2[100010]={0};
ll dp1[100010]={0};
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	

	ll mod=1e9+7;
	string L;
	READ(L);
	ll x=1;
	while(x<=L.length())
	{
		bit[x]=(ll)L[L.length()-x]-(ll)'0';
		x++;
	}
	dp1[100009]=1;
	FORD(i,100008,-1)
	{
		if(bit[i])
		{
			dp1[i]=(2*dp1[i+1])%mod;
		}
		else
		{
			dp1[i]=dp1[i+1];
		}
	}
	dp2[0]=1;
	FORI(i,1,100009)
	{
		dp2[i]=(3*dp2[i-1])%mod;
	}
	ll ans=dp1[0];
	FORI(i,1,100009)
	{
		if(bit[i])
		{
			ans=(ans+dp1[i+1]*dp2[i-1])%mod;
		}
	}
	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 2896
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] a = new int[n];
		int count = 0;
		for(int i=0;i<n;i++){
			a[i] = scanner.nextInt();
			if(a[i] % 2 != 0){
				System.out.println(count);
				return;
			}else{
				a[i] /= 2;
			}
		}
		count = 1;
		while(true){
			for(int i=0;i<n;i++){
				if(a[i] % 2 != 0){
					System.out.println(count);
					return;
				}else{
					a[i] /= 2;
				}
			}
			count++;
		}
	}

}


Measured memory_bytes: 21844
#include <cstdio>
using namespace std;

int main()
{
  int n, k, i, j;
  double sum = 0;
  double ans;
  scanf("%d %d", &n, &k);
  for (i = 1; i <= n; i++) {
    long double a = 1.0;
    for (j = i; j <= k-1; j*=2) {
      a *= 0.5;
    }
    sum += a;
  }
  ans = sum / n;
  printf("%.12f\n", ans);
}

Measured memory_bytes: 384
import java.util.*;

public class Main{

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

        long a = sc.nextLong();
        long b = sc.nextLong();
        long c = sc.nextLong();
        long k = sc.nextLong();

        if(a >= k){
            System.out.println(k);
        }
        else if(a + b >= k){
            System.out.println(a);
        }
        else{
            long temp = k - a - b;
            System.out.println(a - temp);
        }
    }
}

Measured memory_bytes: 35732
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <map>
typedef long long ll;

using namespace std;

int main(void)
{
    ll a;
    int b;
    cin >> a >> b;
    int cnt = 0;
    while(1) 
    {
        a = a / b;
        cnt++;
        if (a == 0) {
            break;
        }
    }

    cout << cnt << endl;
    

    return 0;
}

Measured memory_bytes: 256
#include <iostream>

int main(){
    int a,b,c,d,e,f;
    std::cin >> a >> b >> c >> d >> e >> f;
    if(a+5*b+10*c+50*d+100*e+500*f>=1000){
        std::cout << 1 <<std::endl;
    }
    else{
        std::cout << 0 << std::endl;
    }
    return 0;
}

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

struct point{
  ll x,y;
};

ll w,h,v,t,x,y,p,q;
ll R,H,W;
point o,O;

point calc(ll X,ll Y){
  ll dx=abs(X-O.x),dy=abs(Y-O.y);
  point res;

  if(dx%2==0)res.x=p;
  else res.x=w-p;

  if(dy%2==0)res.y=q;
  else res.y=h-q;

  res.x+=X*w;
  res.y+=Y*h;
  return res;
}

ll search(ll Y){
  ll l=0,r=W,m;
  while(l<r){
    m=(l+r)/2;
    point d=calc(m,Y);
    ll dist= (d.x-o.x)*(d.x-o.x) + (d.y-o.y)*(d.y-o.y);
    if( dist <= v*t*v*t  || o.x< d.x ){
      r=m;
    }else{
      l=m+1;
    }
  }
  return l;
}

ll search2(ll Y){
  ll l=0,r=W,m;
  while(l<r){
    m=(l+r)/2;
    point d=calc(m,Y);
    ll dist= (d.x-o.x)*(d.x-o.x) + (d.y-o.y)*(d.y-o.y);
    if( dist <= v*t*v*t || d.x < o.x ){
      l=m+1;
    }else{
      r=m;
    }
  }
  return l;
}

int main(){
  cin>>w>>h>>v>>t>>x>>y>>p>>q;
  R=v*t;
  W=(v*t/w+1LL)*4;
  H=(v*t/h+1LL)*4;
  O.x=W/2;
  O.y=H/2;
  o.x=O.x*w+x;
  o.y=O.y*h+y;



  ll ans=0;
  for(ll i=0;i<=H;i++){
    ll a=search(i);
    ll b=search2(i);
    point d=calc(a,i);
    ll dist= (d.x-o.x)*(d.x-o.x) + (d.y-o.y)*(d.y-o.y);
    d=calc(b,i);
    ll dist2= (d.x-o.x)*(d.x-o.x) + (d.y-o.y)*(d.y-o.y);
    d=calc(b-1,i);
    ll dist3= (d.x-o.x)*(d.x-o.x) + (d.y-o.y)*(d.y-o.y);
    d=calc(a-1,i);
    ll dist4= (d.x-o.x)*(d.x-o.x) + (d.y-o.y)*(d.y-o.y);

    if(dist <= v*t*v*t && v*t*v*t<dist2)
      if(dist3 <= v*t*v*t &&v*t*v*t<dist4)
	ans+=(b-a);
    
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 1156
#include <iostream>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
#include <set>


using namespace std;

//void C_98()
int main()
{
  int N;
  string S;
  cin >> N >> S;

  vector<int> num_W(N, 0), num_E(N, 0);
  
  num_W[0] = (S[0] == 'W') ? 1 : 0;
  num_E[0] = (S[0] == 'E') ? 1 : 0;

  for (int i = 1; i < N; ++i)
  {
    if (S[i] == 'W')
    {
      num_W[i] += num_W[i - 1] + 1;
      num_E[i] = num_E[i - 1];
    }
    else
    {
      num_E[i] += num_E[i - 1] + 1;
      num_W[i] = num_W[i - 1];
    }
  }

  int min_num = N;
  for (int i = 0; i < N; ++i)
  {
    int sum = num_W[i-1] + num_E[N - 1] - num_E[i];
    min_num = min(min_num, sum);
  }

  cout << min_num << endl;
}

Measured memory_bytes: 3076
n, m = map(int, input().strip().split())
a = [[0 for j in range(m)] for i in range(n)]
b = [[0] for j in range(m)]
c = [[0] for j in range(n)]

for i in range(n):
    a[i] = list(map(int, input().strip().split()))

for i in range(m):
    b[i] = [int(input())]


for i in range(n):
    for j in range(m):
        c[i][0] += a[i][j]*b[j][0]
    print(c[i][0])

Measured memory_bytes: 7928
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define ll long long
#define INF 1<<31-1
#define LNF 9223372036854775807
#define PI 3.14159265358979
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX(x,y) ((x)<(y)?(y):(x))
#define FOR(i,a,n) for(i=a;i<n;i++)
#define MOD 1000000007
//#define MOD 998244353
#define NUM 200010
 
void swap(int* a,int* b){int tmp=*a;*a=*b;*b=tmp;}
int abs(int a){if(a<0)return -a;return a;}
int dup(int a,int d){if(a%d==0)return a/d;else return a/d+1;}
int mod(int a,int m){if(a<0)return a%m+m;else return a%m;}

void swapl(ll* a,ll* b){ll tmp=*a;*a=*b;*b=tmp;}
ll absl(ll a){if(a<0)return -a;return a;}
ll dupl(ll a,ll d){if(a%d==0)return a/d;else return a/d+1;}
ll modl(ll a,ll m){if(a<0)return a%m+m;else return a%m;}

ll GCD(ll a,ll b){ll c=1,tmp=MAX(a,b);b=MIN(a,b);a=tmp;while(c!=0){c=a%b;a=b;b=c;}return a;}
ll LCM(ll a,ll b){return a*b/GCD(a,b);}

ll factorial(ll n, ll m) {return n < m ? 1 : n*factorial(n-1, m);}

int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}

// ll dp[]

int main(){
  ll N, n3, n5, n15;
  ll sum, sum3, sum5, sum15;
  
  scanf("%lld", &N);

  n3 = N / 3;
  n5 = N / 5;
  n15 = N /15;

  sum = N * (N + 1) / 2;
  sum3 = n3 * (n3 + 1) / 2;
  sum5 = n5 * (n5 + 1) / 2;
  sum15 = n15 * (n15 + 1) / 2;

  printf("%lld", sum - 3*sum3 - 5*sum5 + 15*sum15);
  return 0;
}

Measured memory_bytes: 2152
/*****************************************************/
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>

using namespace std;

#define   offcin        ios::sync_with_stdio(false)
#define   DEBUG         freopen("#.txt", "r", stdin)
#define   sigma_size    26
#define   lson          l,m,v<<1
#define   rson          m+1,r,v<<1|1
#define   slch          v<<1
#define   srch          v<<1|1
#define   ll            long long
#define   ull           unsigned long long
#define   lowbit(x)     (x&-x)

const int    INF    = 0x3f3f3f3f;
const ll     INFF   = 1e18;
const double pi     = acos(-1.0);
const double inf    = 1e18;
const double eps    = 1e-9;
const ll     mod    = 1e9+7;
const int    maxmat = 10;
const ull    BASE   = 133333331;

/*****************************************************/
inline void RI(int &x) {
      char c;
      while((c=getchar())<'0' || c>'9');
      x=c-'0';
      while((c=getchar())>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0';
}
inline ll bits(ll x) {
      return !x ? x : bits(x - lowbit(x)) + 1;
}
/*****************************************************/

const int maxn = 1e5 + 5;

int N;
long long a[maxn];
long long ans;

int main(int argc, char const *argv[]) {
    cin>>N;
    for (int i = 0; i < N; i ++)
        scanf("%lld", a + i);

    sort(a, a + N);
    int res = 0;
    for (int i = 0; i < N - 1; i ++) {
        if (2 * (a[i] + ans) >= a[i + 1])
            res ++;
        else
            res = 0;
        ans += a[i];
    }
    cout<<res + 1<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<cstring>
using namespace std;
const int N=500500;
int i,j,k,n,m,x,sum,ans;
int a[N];
char s[N];
int main() {
	scanf("%s",s+1);
	n=strlen(s+1);
	for (i=1;i<=n;i++) a[i]=s[n-i+1]-'0';
	x=0;n++;
	for (i=1;i<=n;i++) {
		x+=a[i]*9;
		a[i]=x%10;
		x/=10;
	}
	while (n>1 && !a[n]) n--;
	for (i=1;i<=n;i++) sum+=a[i];
	while (sum>0) {
		x=1;
		i=0;
		while (x) {
			i++;
			sum-=a[i];
			x+=a[i];
			a[i]=x%10;
			sum+=a[i];
			x/=10;
		}
		sum--;
		if (i>n) n=i;
		ans++;
	}
	printf("%d\n",(ans+8)/9);
}

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

const long long MOD = 1000000007;

std::vector< std::vector< long long > > comb(int n, int r) {
    std::vector< std::vector< long long > > v(
        n + 1, std::vector< long long >(n + 1, 0));
    for (int i = 0; i < v.size(); i++) {
        v[i][0] = 1;
        v[i][i] = 1;
    }
    for (int j = 1; j < v.size(); j++) {
        for (int k = 1; k < j; k++) {
            v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]) % MOD;
        }
    }
    return v;
}

int main(void) {
    long long N, K;
    cin >> N >> K;
    vector< vector< long long > > com = comb(N, N);
    for (int i = 1; i <= K; i++) {
        long long a = com[K - i + i - 1][i - 1];
        long long b = com[N - K - i + 1 + i][i];
        printf("%d\n", (a * b) % MOD);
    }
    return 0;
}


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

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

    int n;
    long long k;
    cin >> n >> k;
    vector<int> A(n);
    for(int i = 0; i < n; i++){
        cin >> A[i];
        A[i]--;
    }

    if(k < n){
        int now = 0;
        for(int i = 0; i < k; i++){
            now = A[now];
        }
        cout << now + 1 << endl;
        return 0;
    }

    int now = 0;
    vector<int> T(n, -1);
    T[0] = 0;
    int li = 0;
    for(int i = 1; i < n; i++){
        li = i;
        now = A[now];
        if(T[now] != -1){
            break;
        }
        T[now] = i;
    }

    int diff = li - T[now];
    k -= li;
    k %= diff;

    for(int i = 0; i < k; i++){
        now = A[now];
    }

    cout << now + 1 << endl;

    return 0;
}

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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define PI 3.14159265358979
#define MOD 1000000007 // = 10^9 + 7

using namespace std;
using ll = long long;

void solve()
{
	ll n, k;
	cin >> n >> k;

	cout << min(n % k, k - (n % k)) << endl;

}

int main()
{
	fastio;
	solve();

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,ans,a[201];
int main() {
	scanf("%d",&n);n<<=1;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	for(int i=1;i<n;i+=2) ans+=a[i];
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
A=[[int(0) for i in range(10)]for j in range(10)]
count=0
while 1:
    try:
        x,y,s = map(int, input().split(','))
        if s==1:
            for i in range(x-1,x+2):
                if i>=0 and i<=9:
                    A[i][y]=A[i][y]+1
            for i in range(y-1,y+2):
                if i>=0 and i<=9:
                    A[x][i]=A[x][i]+1
            A[x][y]=A[x][y]-1 
        elif s==2:
            for i in range(x-1,x+2):
                for j in range(y-1,y+2):
                    if i>=0 and i<=9 and j>=0 and j<=9:
                        A[i][j]=A[i][j]+1
        else:
            for i in range(x-2,x+3):
                if i>=0 and i<=9:
                    A[i][y]=A[i][y]+1
            for i in range(y-2,y+3):
                if i>=0 and i<=9:
                    A[x][i]=A[x][i]+1
            for i in range(x-1,x+2):
                if i>=0 and i<=9:
                    A[i][y]=A[i][y]-1
            for i in range(y-1,y+2):
                if i>=0 and i<=9:
                    A[x][i]=A[x][i]-1
            for i in range(x-1,x+2):
                for j in range(y-1,y+2):
                    if i>=0 and i<=9 and j>=0 and j<=9:
                        A[i][j]=A[i][j]+1
    except:
        break
num=0
for i in range(10):
    for j in range(10):
        if A[i][j]==0:
            count=count+1
        if A[i][j]!=0:
            if num<A[i][j]:
                num=A[i][j]
print(count)
print(num)

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

int main(){
  int n;
  long long k,ans = 0;
  cin >> n >> k;
  pair<int,long long> p[n];
  int i;
  for(i=0;i<n;i++){
    cin >> p[i].first >> p[i].second;
  }
  sort(p,p+n);
  for(i=0;i<n;i++){
    ans+=p[i].second;
    if(ans>=k){
      cout << p[i].first << endl;
      break;
    }
  }
  return 0;
}


Measured memory_bytes: 1792
#include<iostream>
using namespace std;
int main()
{
   long long a, b, c, d;
   cin >> a >> b >> c >> d;
   
   long long ans1, ans2, ans3, ans4;
   ans1 = a*c;
   ans2 = a*d;
   ans3 = b*c;
   ans4 = b*d;
   
   cout << max({ ans1, ans2, ans3, ans4 }) << endl;
   
   return 0;
}

Measured memory_bytes: 3180
S, T = input(), input()

def func(S, T):

    merge_S = list(set(S))
    merge_T = list(set(T))
    for t in merge_T:
        if t not in merge_S:
            return -1

    S_2 = S+S
    len_s = len(S)

    ans = -1

    for t in T:
        ans += S_2[(ans+1)%len_s:].index(t) + 1

    return ans + 1

print(func(S,T))

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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { std::cout << #a << " = " << a << "\n"; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T, class V> istream& operator>> (istream& ist, pair<T, V>& p) { return ist >> p.first >> p.second; }
template<class T> ostream& operator<< (ostream& ost, pair<T, T>& p) { return ost << p.first << ", " << p.second; }
template<class T> istream& operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) ist >> e; return ist; }

typedef long long ll;
int const inf = INT_MAX / 2;

int const MOD = 998244353;

int main() {
  int N; cin >> N;
  vector<int> D(N);
  map<int, int> C;
  int max = -1;
  rep(i, N) {
    cin >> D[i];
    C[D[i]]++;
    max = std::max(max, D[i]);
  }
  if (D[0] || C[0] != 1) {
    cout << "0\n";
    return 0;
  }
  rep(i, max) if (!C[D[i]]) {
    cout << "0\n";
    return 0;
  }

  ll ans = 1;
  REP(i, 1, max + 1) rep(_, C[i]) (ans *= C[i - 1]) %= MOD;
  cout << ans << endl;
}


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

#include <boost/multiprecision/cpp_int.hpp>
using boost::multiprecision::cpp_int;

const int MOD = 1000000007;

int main() {
  int n;
  cin >> n;
  vector<cpp_int> arr(n);
  for (int i = 0; i < n; ++i) {
    cin >> arr[i];
  }
  cpp_int res = 0;
  cpp_int power_of_two = 1;
  for (int i = 0; i < 60; ++i) {
    cpp_int one = 0;
    for (cpp_int &element : arr) {
      if (element % 2 == 1) {
        one++;
      }
      element /= 2;
    }
    cpp_int zero = n - one;
    res = (res + power_of_two * one * (n - one)) % MOD;
    power_of_two = (power_of_two * 2) % MOD;
  }
  cout << res << endl;
}


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

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using ll = long long;

const int N = 5000;

ll n, k;
ll p[N], c[N];
ll g[N], gs[N], tot[N];

int counter = -1;
bitset<N> vis;

int main() {
	cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
        --p[i];
    }
    vis.reset();
    for (int i = 0; i < n; ++i) cin >> c[i];
    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            ++counter;
            for (int j = i; !vis[j]; j = p[j]) {
                // cout << j << ' ';
                vis[j] = true;
                g[j] = counter;
                tot[counter] += c[j];
                gs[counter]++;
            }
            // cout << '\n';
        }
    }

    ll ans = -1e18;
    for (int i = 0; i < n; ++i) {
        ll tmp = 0, mx = -1e18;
        int cur = i;
        for (int j = 0; j < min(k, gs[g[i]]); ++j) {
            tmp += c[cur];
            ll cycles = (k - j - 1) / gs[g[i]];
            mx = max(mx, tmp + max(0ll, cycles * tot[g[i]]));
            cur = p[cur];
        }
        ans = max(mx, ans);
    }
    cout << ans;
}


Measured memory_bytes: 3796
import math
from collections import deque
from collections import defaultdict
import itertools as it

#自作関数群
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	if len(res)==0:
		res = [n]
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

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

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

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

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

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

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq
def get_sieve_of_eratosthenes(n):
	data = [2]
	#data = [0,0,0]
	for i in range(3,n+1,2):
		data.append(i)
		data.append(0)
	for i in range(len(data)):
		interval = data[i]
		if interval!=0:
			for j in range(i+interval,n-1,interval):
				data[j] = 0
	ans = [x for x in data if x!=0]
	#ans = data[:]
	return ans

x,y = readInts()

if y%2==1:
	print("No")
	exit()

turu = (4*x-y)//2

if turu>=0 and turu<=x:
	print('Yes')
else:
	print('No')

Measured memory_bytes: 9656
import sys
import re
import random
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


class Segtree_op():
    # 単位元及び操作を設定して使うこと
    # queryでは、区間の(l, r)を指定する ex: (0, 5) => [0, 1, 2, 3, 4]
    # 特定の1点は (i, i+1)
    def __init__(self, n):
        self.n = n

        self.size = 1
        while (n >= 1):
            self.size = self.size << 1
            n = n // 2

        self.arr = [self.unit() for i in range(self.size * 2)]

    def op(self, lch, rch):
        # update min with holding index
        return min(lch, rch)

    def unit(self):
        return self.n

    def update(self, k, val):
        k += self.size - 1
        self.arr[k] = val
        while (k):
            k = (k - 1) // 2
            self.arr[k] = self.op(self.arr[k * 2 + 1], self.arr[k * 2 + 2])

    def query(self, l, r):
        L = l + self.size
        R = r + self.size
        s = self.unit()
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(s, self.arr[R - 1])

            if L & 1:
                s = self.op(s, self.arr[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return s

    def show(self):
        idx = 1
        while (idx <= self.size):
            print(self.arr[idx - 1:idx * 2 - 1])
            idx *= 2


def solve():
    n, q = getList()

    st_tate = Segtree_op(n)
    st_yoko = Segtree_op(n)

    reversed = 0
    for _ in range(q):
        op, idx = getList()
        if op == 1:
            border = st_tate.query(idx, n+1)
            reversed += border - 2
            val = min(st_yoko.query(border, border+1), idx)
            st_yoko.update(border, val)
        else:
            border = st_yoko.query(idx, n+1)
            reversed += border - 2
            val = min(st_tate.query(border, border + 1), idx)
            st_tate.update(border, val)

        # st_tate.show()
        # st_yoko.show()
        # print(reversed)
        # print("=========")

    print((n-2) ** 2 - reversed)








def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Measured memory_bytes: 151096
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <list>

using ll = long long;
using ld = long double;
using namespace std;
const int INF = 1e9+100;
const ll INF64 = 7e18l;
const int mod = 1000000007;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(), (a).end()
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);


int main(){
    FIN;
    ll n,k; cin >> n >> k;
    map<ll,ll> a;
    ll s = 0; //種類

    for(int i=0;i<n;i++){
        ll num; cin >> num;
        a[num]++;
        if(a[num] == 1) s++;
    }

    if(s <= k){ cout << 0 << endl; return 0;}

    priority_queue<ll,vector<ll>,greater<ll>> que;
    map<ll,ll>::iterator it;
    for(it=a.begin();it!=a.end();it++)
        que.push(it->second);

    ll ans = 0;
    for(int i=0;i<s-k;i++){
        ans += que.top();
        que.pop();
    }

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



Measured memory_bytes: 14964
#include <iostream>
#include <algorithm>

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

using namespace std;

typedef long long ll;

int n;
int a[100000];
ll s[100001];
int t[100001];

int main(){
	cin >> n;
	rep(i, n){
		cin >> a[i];
	}

	for(int i = 1; i <= n; ++i){
		ll v = a[i - 1] > 0 ? t[i - 1] + a[i - 1] : 0;
		s[i] = s[i - 1] + v / 2;
		t[i] = v % 2;
	}
	cout << s[n] << endl;
	return 0;
}

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

// ############################################################################################

#define FOREACH(i, c) for (__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define FOR(i, a, n) for (register int i = (a); i < (int)(n); ++i)
#define FORE(i, a, n) for (i = (a); i < (int)(n); ++i)
#define Size(n) ((int)(n).size())
#define all(n) (n).begin(), (n).end()

#define ff first
#define ss second
#define ll long long
#define pb push_back
#define mp make_pair

#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>

#define vi vector<int>
#define mii map<int, int>
#define pqb priority_queue<int>
#define pqs priority_queue<int, vi, greater<int> >

#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)

#define mod 1000000007
#define inf 1e18

#define ps(x, y) fixed << setprecision(y) << x
#define mk(arr, n, type) type *arr = new type[n];
#define w(x)  \
    int x;    \
    cin >> x; \
    while (x--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

// ############################################################################################

ll mpow(ll base, ll exp) {
    ll res = 1;
    while (exp > 0) {
        if (exp % 2) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res % mod;
}

void a_k_s() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    // #endif
}

int n;
int v[100005][3], dp[100005][3];
int ans = -1;

void solve(int day, int k, int h) {
    // Base Case
    if (day == n) {
        ans = max(ans, h);
        return;
    }

    // Recursive Case
    FOR(i, 0, 3) {
        if (i == k) continue;
        solve(day + 1, i, h + v[day][i]);
    }
}

int main() {
    a_k_s();

    memset(dp, 0, sizeof dp);
    memset(v, 0, sizeof v);

    cin >> n;
    FOR(i, 1, n + 1) {
        cin >> v[i][0] >> v[i][1] >> v[i][2];
    }

    FOR(i, 0, 3) {
        dp[1][i] = v[1][i];
    }

    FOR(i, 2, n + 1) {
        FOR(j, 0, 3) {
            dp[i][j] = -1;
            FOR(k, 0, 3) {
                if (k == j) continue;
                dp[i][j] = max(dp[i][j], dp[i - 1][k]);
            }
            dp[i][j] += v[i][j];
        }
    }

    FOR(i, 0, 3) {
        ans = max(ans, dp[n][i]);
    }

    // FOR(i, 1, n + 1) {
    //     FOR(j, 0, 3) {
    //         cout << dp[i][j] << ' ';
    //     }
    //     cout << endl;
    // }

    // solve(0, -1, 0);
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 6044
#include <iostream>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <string>
#include <set>
#include <iomanip>
#include <map>
#include <stdio.h>
#include <queue>
#define rep(i,n) for (int i=0;i<(n);++i)
#define REP(i,n) for (int i=0;i<=(n);++i)
#define all(x) (x).begin(), (x).end()

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

using namespace std;
typedef long long ll;
const int INF = 10000000;

int main(){
    int n, k; cin >> n >> k;
    vector<int> a(n, 0);
    rep(i, k){
        int d; cin >> d;
        rep(j, d){
            int num; cin >> num;
            ++a[num-1];
        }
    }
    int res = 0;
    rep(i, n){
        if(a[i] == 0) ++res;
    }
    cout << res << endl;
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T, class T2> void smin(T& a, T2 val) {if (a > val) a = val;}template<class T, class T2> void smax(T& a, T2 val) {if (a < val) a = val;}
const int N = 5*(int)1e5 + 10;

int n, a[N];

// all are positive or (-x / y)
vector<int> reduce(int x, int y){
   int gc = __gcd(x, y);
   x /= gc;
   y /= gc;
   if (x < 0 and y < 0){
      x = -x, y = -y;
   }
   if (y < 0){
      x = -x, y = -y;
   }
   return {x, y};
}

vector<int> complement(vector<int> v){
   int x = v[0], y = v[1];
   swap(x, y);
   x *= -1;
   if (x < 0 and y < 0){
      x = -x, y = -y;
   }
   if (y < 0){
      x = -x, y = -y;
   }
   return {x, y};
}

int power(int a, int b, int m = mod){a %= m; if(b < 0)b += m-1; int r = 1; while(b){if(b&1)r=(r*a)%m; a = (a*a)%m; b>>=1;}return r;}

void solve(){
   cin>>n;

   int zeros = -1, x_zero = 0, y_zero =0;
   map<vector<int>, int> M;
   map<vector<int>, int> seen;
   for (int i = 0; i < n; ++i)
   {
      int x, y;
      cin >> x >> y;
      if (!x and !y){
         zeros++;
      }
      else if (!x){
         x_zero++;
      }
      else if (!y){
         y_zero++;
      }
      else{
         vector<int> v = reduce(x, y);
         M[v]++;         
      }
   }

   int ans = (power(2, x_zero) + power(2, y_zero) - 1 + mod) % mod;

   for(auto it: M){
      if(seen.count(it.first))
         continue;
      vector<int> getComplement = complement(it.first);
      ans *= power(2, it.second) + ((M.count(getComplement) == 0) ? 1 : power(2, M[getComplement])) - 1;
      ans %= mod;
      seen[getComplement] = 1;
   }

   ans += zeros;
   ans %= mod;
   ans += mod;
   ans %= mod;
   cout<<ans;
}

int32_t main(){_
   
   int t = 1;
   //cin >> t;

   while(t--){
     solve();
     cout << endl;
   }
   

   return 0;
}

Measured memory_bytes: 47384