akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define x first
#define y second
#define y1 secondy1
#define rank tipa_rank
#define pb push_back
#define mp make_pair
#define pow10 tipa_pow10
#define ll long long
#define INF 1000000000
#define EPS 1e-9
#define EPS2 1e-8
#define PI acos(-1.0)
using namespace std;
const int MOD = INF + 7;
const int base = 2;
int n;
int a[100000];
vector<int> A;
int main()
{
	scanf("%d" , &n);
	for(int i = 0; i < n; i++)
	{
		scanf("%d" , &a[i]);
		if(A.size() && A.back() != a[i] || !A.size())
		{
			A.push_back(a[i]);
		}
	}
	int ans = 1;
	for(int i = 0; i < (int)A.size() - 2; i++)
	{
		//cout << i << endl;
		if(A[i] < A[i + 1] && A[i + 1] > A[i + 2] || A[i] > A[i + 1] && A[i + 1] < A[i + 2])
			ans++ , i++;
	}
	cout << ans;
}


Measured memory_bytes: 1148
#include<bits/stdc++.h>
#define eps 0.000000001
using namespace std;
typedef long double ld;
typedef pair<int,int> p;
typedef pair<ld,p> P;

int n;
ld px[200],py[200],pz[200],vx[200],vy[200],vz[200],r[200],vr[200];

ld getlen(int a,int b,ld M){
  ld ax=px[a]+vx[a]*M,ay=py[a]+vy[a]*M,az=pz[a]+vz[a]*M,ar=r[a]-vr[a]*M;
  ld bx=px[b]+vx[b]*M,by=py[b]+vy[b]*M,bz=pz[b]+vz[b]*M,br=r[b]-vr[b]*M;
  ld dx=ax-bx,dy=ay-by,dz=az-bz;
  return sqrt(dx*dx+dy*dy+dz*dz)-(ar+br);
}

ld check(int a,int b){
  ld L=0,R=100,M;
  int s=0;
  while(s++<50){
    M=(L+R)/2;
    ld len=getlen(a,b,M),len1=getlen(a,b,M+eps);
    if(len<len1||len<0)R=M;
    else L=M;
  }
  if(getlen(a,b,R)>0)return 1000;
  return R;
}

int main(){
  while(cin>>n,n){
    for(int i=0;i<n;i++)
      cin>>px[i]>>py[i]>>pz[i]>>vx[i]>>vy[i]>>vz[i]>>r[i]>>vr[i];
    priority_queue<P,vector<P>,greater<P> > q;
    for(int i=0;i<n;i++){
      for(int j=i+1;j<n;j++)
	q.push(P(check(i,j),p(i,j)));
      q.push(P(r[i]/vr[i],p(i,i)));
    }
    ld used[200]={};
    while(!q.empty()){
      ld t=q.top().first;
      int a=q.top().second.first,b=q.top().second.second;
      q.pop();
      if(used[a]||used[b])continue;
      used[a]=used[b]=t;
    }
    for(int i=0;i<n;i++)printf("%.10Lf\n",used[i]);
  }
  return 0;
}

Measured memory_bytes: 4444
import math
n_ = 10**5 + 3
mod = 10**9+7
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod
def nCr(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
count=0
for i in range(N-K+1):
    count=(count+((A[i]-A[N-1-i])*nCr(N-i-1,K-1)))%(10**9+7)
print(count)


Measured memory_bytes: 65392
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  int h,w;
  cin >> h >> w;
  vector<string> s(h);
  rep(i,h) cin >> s[i];

  vector<vector<int>> l(h,vector<int>(w)),r(h,vector<int>(w)),u(h,vector<int>(w)),d(h,vector<int>(w));
  rep(i,h)rep(j,w){
    if(s[i][j]=='.') {
      l[i][j] = j > 0 ? l[i][j-1] + 1 : 1;
      u[i][j] = i > 0 ? u[i-1][j] + 1 : 1;
    }
    if(s[i][w-1-j]=='.') r[i][w-1-j] = j > 0 ? r[i][w-j] + 1 : 1;
    if(s[h-1-i][j]=='.') d[h-1-i][j] = i > 0 ? d[h-i][j] + 1 : 1;
  }
  int ans = 0;
  rep(i,h)rep(j,w) ans = max(ans,l[i][j]+r[i][j]+u[i][j]+d[i][j]-3);
  cout << ans << endl;
}

Measured memory_bytes: 67200
#include <iostream>

int main(){
    
    int H,W;
    
    while(1){
    std::cin >> H >> W;
    
    if(H == 0 && W == 0)return 0;
    
    for(int i = 1; i <= H; i++){
        for(int j = 1; j <= W; j++){
            if((i == 1 || i == H) || (j == 1 || j == W)){
                std::cout << "#";
            } else {std::cout << ".";}
        }
        std::cout << "\n";
    }
    
    std::cout << "\n";
}
    
    return 0;
}


Measured memory_bytes: 3100
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define pb push_back
using namespace std;
typedef long long ll;

int keta(int x){
  int ans = 0;
  while (x > 0){
    x /= 10;
    ans++;
  }
  return ans;
}

int judge(int x){
  vector<int> res(3);
  while(x > 0){
    if (x % 10 == 3) res[0] = 1;
    if (x % 10 == 5) res[1] = 1;
    if (x % 10 == 7) res[2] = 1;
    x /= 10;
  }
  if (res[0] && res[1] && res[2]) return 1;
  return 0;
}

int main(){
  int n;
  cin >> n;
  vector<int> a;
  a.pb(3); a.pb(5); a.pb(7);

  rep(i, 9){
    rep(j, a.size()){
      if (keta(a[j]) == i){
        a.pb(a[j] * 10 + 3);
        a.pb(a[j] * 10 + 5);
        a.pb(a[j] * 10 + 7);
      }
    }
  }
  int ans = 0;
  for(int i = 0; i < a.size() && a[i] <= n; i++){
    if (judge(a[i])) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3752
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
int INF=1<<29;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N,K;
	string s;
	cin>>N>>K>>s;
	string A="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	string B="abcdefghijklmnopqrstuvwxyz";
	for(int i=0;i<26;i++){
		if(s[K-1]==A[i]) s[K-1]=B[i];
	}
	cout<<s<<endl;
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define pi acos(-1.0)
const ll INF = 1LL<<61;
template<class T>bool chmax(T &a, const T &b) { 
  if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) {
  if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
ll jou(ll N, ll P){if(P==0) return 1;
    if(P%2==0){ll t = jou(N, P/2);return t*t % mod;
    }return (N * jou(N, P-1)) % mod;}  //jou(n,mod-2)で逆元
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる


//——————— comre(n);　→　nCk=com(n,k) —————————————————

vector<ll> fact, fact_inv, inv;
/*  comre :二項係数のための前処理
    計算量:O(n)
*/
void comre(int SIZE) {
    fact.resize(SIZE + 5);
    fact_inv.resize(SIZE + 5);
    inv.resize(SIZE + 5);
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < SIZE + 5; i++) {
        fact[i] = fact[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
    }
}
/*  com :modでの二項係数を求める(前処理 comre が必要)
    計算量:O(1)
*/
ll com(ll n, ll k) {
    assert(!(n < k));
    assert(!(n < 0 || k < 0));
    return fact[n] * (fact_inv[k] * fact_inv[n - k] % mod) % mod;
}

//—————————————————————————————————————————————————


int main(){
  ll k;
  string s;
  cin>>k>>s;
  ll n=s.size();

  vector<ll> p(k+1);
  p[0]=1;
  repo(i,k+1){
    ll x=(n-1+i)*jou(i,mod-2)%mod;
    p[i]=p[i-1]*x%mod;
  }

  ll ans=0;
  rep(i,k+1){
    ll x=jou(25,i)*jou(26,k-i);
    if(x>=mod) x%=mod;
    x*=p[i];
    if(x>=mod) x%=mod;
    ans+=x;
    if(ans>=mod) ans%=mod;
  }

  cout << ans << endl;
}


Measured memory_bytes: 12108
#include <bits/stdc++.h>
     
#define pll pair <long long,long long>
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define vll vector <ll>
#define NFS ios_base::sync_with_stdio(0); cin.tie(NULL);
#define endl '\n'
#define M 1000000007   
using namespace std;
 
int main()
{
    NFS
 	string s;
 	cin>>s;
 	if (s[0]=='A' && s[1]=='A' && s[2]=='A')
 	{
 		cout<<"No";
 	}else if(s[0]=='B' && s[1]=='B' && s[2]=='B')
 	{
 		cout<<"No";
 	}else{
 		cout<<"Yes";
 	}
    return 0;
}

Measured memory_bytes: 256
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

use std::cmp::Ordering;
#[derive(Eq, PartialEq, Clone, Debug)]
pub struct Rev<T>(pub T);

impl<T: PartialOrd> PartialOrd for Rev<T> {
    fn partial_cmp(&self, other: &Rev<T>) -> Option<Ordering> {
        other.0.partial_cmp(&self.0)
    }
}

impl<T: Ord> Ord for Rev<T> {
    fn cmp(&self, other: &Rev<T>) -> Ordering {
        other.0.cmp(&self.0)
    }
}

impl<T: Copy> Copy for Rev<T> {}

fn main() {
    input! {
        a: usize, p: usize
    }
    println!("{}", (3 * a + p) / 2);
}


Measured memory_bytes: 4352
def main():
    from itertools import combinations_with_replacement
    from math import ceil

    d, g, *pc = map(int, open(0).read().split())
    p, c = pc[::2], pc[1::2]
    ans = sum(p)
    
    q = ceil(g / (d * 100))
    if q < p[-1]:
        ans = q
        
    l = range(d)
    for x in combinations_with_replacement(l, d):
        y = list(set(x))
        tmp = g
        count = 0
        for i in y:
            tmp -= ((i + 1) * 100 * p[i] + c[i])
            count += p[i]
        if tmp <= 0:
            ans = min(ans, count)
        else:
            j = max(set(l) - set(x))
            k = ceil(tmp / (100 * (j + 1)))
            if k < p[j]:
                count += k
                ans = min(ans, count)

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)

int main()
{
    char ans = 'D';
    char a, b;
    cin >> a >> b;
    if((a=='H'&&b=='H')||(a=='D'&&b=='D')){
        ans = 'H';
    }
cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 256
def get_i() #空白区切の入力を数値(整数)の配列で返す
  return gets.chomp.split(" ").map(&:to_i)
end
def get_f() #空白区切の入力を数値(実数)の配列で返す
  return gets.chomp.split(" ").map(&:to_f)
end
def get() #空白区切の入力を文字列の配列で返す
  return gets.chomp.split(" ")
end
def get_nsp() #入力されたものを一文字ずつに区切った文字列の配列で返す
  return gets.chomp.split("")
end
def yn_judge(bool,y="Yes",n="No") #boolに真偽を投げることで、trueならy、falseならnの値を出力する
  return bool ? y : n 
end
def array(size,n=1,init=nil) #nに配列の次元数、sizeに配列の大きさ、initに初期値を投げることでその配列を返す
  if n==1
    return Array.new(size){init}
  else
    return Array.new(n).map{Array.new(size){init}}
  end
end

a_,b_,m=get_i
a=get_i
b=get_i
xyz=array(m,1)
ans=a.min+b.min
m.times do|i|
  x,y,c=get_i
  if ans>a[x-1]+b[y-1]-c
    ans=a[x-1]+b[y-1]-c
  end
end
puts ans


Measured memory_bytes: 20772
import copy

n = int(input())

blist = list(map(str, input().split()))
slist = copy.deepcopy(blist)

cnt = 0

for i in range(n):
    for j in range(n-1, i, -1):
        if blist[j][1] < blist[j-1][1]:
            blist[j], blist[j-1] = blist[j-1], blist[j]


for i in range(n):
    minj = i
    for j in range(i, n):
        if slist[j][1] < slist[minj][1]:
            minj = j
    if i != minj:
        cnt += 1
        slist[i], slist[minj] = slist[minj], slist[i]

for i in range(n):
    if i == n-1:
        print(blist[i])
    else:
        print(blist[i] + " ", end="")

print("Stable")

for i in range(n):
    if i == n-1:
        print(slist[i])
    else:
        print(slist[i] + " ", end="")

for b, s, in zip(blist, slist):
    if b != s:
        print("Not stable")
        exit()

print("Stable")



Measured memory_bytes: 6344
function Main(input) {
	input = input.split("\n");
	var n = input[0];
	var a = 0;
	for(i = 1; i <= n; i++){
		l = input[i].split(" ");
		a += l[1] - l[0] + 1;
	}
	console.log(a);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7484
n = int(input())
words = []
for i in range(n):
    words.append(input())
if len(words) != len(list(set(words))):
    print("No")
    exit()
for i in range(len(words)-1):
    if words[i][-1] != words[i+1][0]:
        print("No")
        exit()
print("Yes")

Measured memory_bytes: 3060
n = int(raw_input())

aa = []
for i in range(n):
    t = int(raw_input())
    aa.append(t)

cnt = 0
b = dict({1: True})
a = aa[0]
while 1:
    cnt += 1
    if a == 2:
        print cnt
        exit()
    a = aa[a-1]
    if a in b:
        print -1
        exit()
    b[a] = True
    if cnt == n:
        print -1
        exit()

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

int main(){
  int N,D;
  int count=0;
  cin>>N>>D;
  int X[N+100][D+100];
  for(int i=1;i<N+1;i++){
    for(int j=1;j<D+1;j++){
      cin>>X[i][j];
    }
  }
  float temp2;
  for(int i=1;i<N+1;i++){
    for(int j=i+1;j<N+1;j++){
      int temp1=0;
      for(int k=1;k<D+1;k++){
      temp1=temp1+(X[i][k]-X[j][k])*(X[i][k]-X[j][k]);
      }
      temp2=sqrt(temp1);
      if(temp2==ceil(temp2)){
        count++;
      }
    }
  }
  cout <<count<<endl;


  return 0;
  }


Measured memory_bytes: 256
#include<map>
#include<queue>
#include<cstdio>
#include<vector>

#define	pb	push_back

using namespace std;

typedef	vector<int>	vi;

vi mv[13];
long long pow12[13];

void findEmptyPos(long long stat,int *z){
	for(int i=0,j=0;i<13;i++){
		if(stat%12==0)	z[j++]=12-i;
		stat/=12;
	}
}

long long sw(long long stat,int i,int j){
	long long powi=pow12[12-i],powj=pow12[12-j];
	int pi=(stat/powi)%12,pj=(stat/powj)%12;
	return stat+(pj-pi)*powi+(pi-pj)*powj;
}

void bfs(map<long long,int> &f,long long inistat,int stop){
	f[inistat]=0;
	queue<long long> qu;	qu.push(inistat);
	while(!qu.empty()){
		long long stat=qu.front();	qu.pop();
		int cnt=f[stat];
		if(cnt==stop)	break;

		int z[2];	findEmptyPos(stat,z);
		for(int i=0;i<2;i++){
			for(int j=0;j<mv[z[i]].size();j++){
				long long nextstat=sw(stat,z[i],mv[z[i]][j]);
				if(f.count(nextstat)==0){
					qu.push(nextstat);
					f[nextstat]=cnt+1;
				}
			}
		}
	}
}

int main(){
	long long a=1;
	for(int i=0;i<13;i++)	pow12[i]=a,a*=12;

	mv[0].pb(2);
	mv[1].pb(2);	mv[1].pb(5);
	mv[2].pb(0);	mv[2].pb(1);	mv[2].pb(3);	mv[2].pb(6);
	mv[3].pb(2);	mv[3].pb(7);
	mv[4].pb(5);
	mv[5].pb(1);	mv[5].pb(4);	mv[5].pb(6);	mv[5].pb(9);
	mv[6].pb(2);	mv[6].pb(5);	mv[6].pb(7);	mv[6].pb(10);
	mv[7].pb(3);	mv[7].pb(6);	mv[7].pb(8);	mv[7].pb(11);
	mv[8].pb(7);
	mv[9].pb(5);	mv[9].pb(10);
	mv[10].pb(6);	mv[10].pb(9);	mv[10].pb(11);	mv[10].pb(12);
	mv[11].pb(7);	mv[11].pb(10);
	mv[12].pb(10);

	int ans[]={0,1,2,3,4,5,6,7,8,9,10,11,0};
	long long ansstat=0;
	for(int i=0;i<13;i++)	ansstat=ansstat*12+ans[i];

	map<long long,int> f;
	bfs(f,ansstat,14);

	for(long long inistat;scanf("%lld",&inistat),~inistat;){
		for(int i=1,p;i<13;i++)	scanf("%d",&p),inistat=inistat*12+p;
		map<long long,int> g;
		bfs(g,inistat,6);

		int cmin=21;
		map<long long,int>::iterator it;
		for(it=g.begin();it!=g.end();it++){
			long long stat=it->first;
			int cnt=it->second;
			if(f.count(stat))	cmin=min(cmin,cnt+f[stat]);
		}
		if(cmin<=20)	printf("%d\n",cmin);
		else	puts("NA");
	}

	return 0;
}

Measured memory_bytes: 5768
#include <iostream>
#include <array>

constexpr int MAX = 100;

int main(void)
{
    size_t in_num;
    std::cin >> in_num;


    std::array <int, MAX> in;
    for (size_t i = 0; i < in_num; i++) {
        std::cin >> in.at(i);
    }

    for (size_t i = 0; i < in_num; i++) {
        if (i != 0) {
            std::cout << " ";
        }
        std::cout << in.at(in_num - 1 - i);
    }
    std::cout << std::endl;

    return 0;
}

Measured memory_bytes: 1168
def inp() a=gets.chomp.split(" ").map(&:to_i)end
n = inp[0]
t = [1]
(2..1000).each do |b|
  (2..1000).each do |p|
    li = b**p
    break if(li > n)
    t.push(li)
  end
end
p t.max

Measured memory_bytes: 1788
#include <cstdio>

int main()
{
    char s[4];
    scanf("%c%c%c", &s[0], &s[1], &s[2]);
    int cnt = 0;
    if (s[0] == '1')
    {
        ++cnt;
    }
    if (s[1] == '1')
    {
        ++cnt;
    }
    if (s[2] == '1')
    {
        ++cnt;
    }
    printf("%d\n", cnt);
    return 0;
}


Measured memory_bytes: 128
#include<iostream>
#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>
using namespace std;
#define FOR(i, a, b) for (ll 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 piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////
int main() {
	int N, M;
	cin >> N >> M;
	vector<bool>flag1(N+1, false);
	vector<bool>flag2(N+1, false);
	for (int i = 0; i < M; ++i) {
		int a, b;
		cin >> a >> b;
		if (a == 1) {
			flag1[b] = true;
		}
		if (b == N) {
			flag2[a] = true;
		}
	}
	bool key = false;
	for (int i = 0; i <= N; ++i) {
		if (flag1[i] && flag2[i]) {
			key = true;
		}
	}
	if (key)cout << "POSSIBLE" << endl;
	else cout << "IMPOSSIBLE" << endl;
	return 0;
}


Measured memory_bytes: 256
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

ans = 1
def dfs(i,x,y,z,a,n):
    global ans
    if i == n:
        return
    if x == y == z == a[i]:
        ans *= 3
        ans %= MOD
        dfs(i + 1,x + 1,y,z,a,n)
    elif x == y == a[i]:
        ans *= 2
        ans %= MOD
        dfs(i + 1,x + 1,y,z,a,n)
    elif y == z == a[i]:
        ans *= 2
        ans %= MOD
        dfs(i + 1,x,y + 1,z,a,n)
    elif x == a[i]:
        dfs(i + 1,x + 1,y,z,a,n)
    elif y == a[i]:
        dfs(i + 1,x,y + 1,z,a,n)
    elif z == a[i]:
        dfs(i + 1,x,y,z + 1,a,n)
    else:
        ans = 0
        return

def main():
    n = int(input())
    a = list(map(int,input().split()))

    dfs(0,0,0,0,a,n)
    print(ans)

if __name__ =='__main__':
    main()   


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

#define endl '\n'
#define ff first
#define ss second
#define mp make_pair
#define pb push_back

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

/*
Rating 1-399 : gray
Rating 400-799 : brown
Rating 800-1199 : green
Rating 1200-1599 : cyan
Rating 1600-1999 : blue
Rating 2000-2399 : yellow
Rating 2400-2799 : orange
Rating 2800-3199 : red
*/

int find_color(int rank) {
	if (rank < 400) return 0;
	if (rank < 800) return 1;
	if (rank < 1200) return 2;
	if (rank < 1600) return 3;
	if (rank < 2000) return 4;
	if (rank < 2400) return 5;
	if (rank < 2800) return 6;
	if (rank < 3200) return 7;
	return 8;
}

void solve() {

	const int MAX_COLORS = 8;

	int n;
	cin >> n;

	int extra = 0;
	set<int> colors;
	for (int i = 0; i < n; i++) {
		int val; cin >> val;

		int color = find_color(val);
		if (color == 8) extra++;
		else colors.insert(color);
	}

	int curr = colors.size();

	int min_ans = !curr ? 1 : curr;
	int max_ans = curr + extra;
	cout << min_ans << ' ' << max_ans << endl;
}

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

	#ifdef LOCAL
		ifstream in("in");
		cin.rdbuf(in.rdbuf());
	#endif

	solve();
}

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

int main()
{
    int M, N, tmp;
    cin >> N >> M;
    int count = 0;
    for (int i = 0; i < M; i++)
    {
        cin >> tmp;
        count += tmp;
    }

    if (count > N)
        cout << -1;
    else
        cout << N - count;
}

Measured memory_bytes: 3640
import java.util.*;

public class Main {
	public static void main(String []args) {
		Scanner sc = new Scanner(System.in);
		String s1 = sc.next();
		String s2 = sc.next();
		String s3 = sc.next();
		if(s1.charAt(s1.length()-1)==s2.charAt(0)
			&& s2.charAt(s2.length()-1)==s3.charAt(0)) {
			System.out.println("YES");
		}
		else {
			System.out.println("NO");
		}
	}
}

Measured memory_bytes: 20820
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;

int main()
{
    int m,n;
    cin>>m;
    cin>>n;
    if(m%n==0)
        cout<<"0";
    if(m%n!=0)
        cout<<"1";
}

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

#define SIZE 100010

int main() {
    long x, y, a, b, c, ans=0;
    long p[SIZE], q[SIZE], r[SIZE], arr[SIZE*3];
    std::cin >> x >> y >> a >> b >> c;

    for (int i=0; i<a; ++i) std::cin >> p[i];
    for (int i=0; i<b; ++i) std::cin >> q[i];
    for (int i=0; i<c; ++i) std::cin >> r[i];

    std::sort(p, p+a, std::greater<long>());
    std::sort(q, q+b, std::greater<long>());
    std::sort(r, r+c, std::greater<long>());

    for (int i=0; i<x; ++i) arr[i] = p[i];
    for (int i=0; i<y; ++i) arr[i+x] = q[i];
    for (int i=0; i<c; ++i) arr[i+x+y] = r[i];

    std::sort(arr, arr+x+y+c, std::greater<long>());

    for (int i=0; i<x+y; ++i) ans += arr[i];

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

    return 0;
}

Measured memory_bytes: 4864
(let ((n (read))
      (m 0)
      (a 0)
      (r 0)
      (c 0)
      (h 0)
      s)
  (dotimes (i n)
    (setf s (read-line))
    (cond ((equal (char s 0) #\M) (setf m (1+ m)))
          ((equal (char s 0) #\A) (setf a (1+ a)))
          ((equal (char s 0) #\R) (setf r (1+ r)))
          ((equal (char s 0) #\C) (setf c (1+ c)))
          ((equal (char s 0) #\H) (setf h (1+ h)))))
  (format t "~A~%" (+ (* m a r) (* m a c) (* m a h) (* m r c) (* m r h) (* m c h) (* a r c) (* a r h) (* a c h) (* r c h))))


Measured memory_bytes: 48480
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
int main(){
	unsigned long long a,b,x;
	unsigned long long n=0;
	scanf("%llu %llu %llu",&a,&b,&x);
	if(a>=0 && b>=0 && a<=pow(10,18) && b<=pow(10,18) && x<=pow(10,18) && x>=1 && a<=b){
		if(a%x==0){
			unsigned long long x1=a/x;
			unsigned long long y1=b/x;
			n=y1-x1+1;
		}
		else{
			unsigned long long x1=a/x;
			unsigned long long y1=b/x;
			n=y1-x1;
			
		}
		
	}
	printf("%llu\n",n);
	
}

Measured memory_bytes: 256
N, A, B, C, D = map(int, input().split())
S = input()
if C < D:
    if '##' not in S[A:D - 1]:
        print('Yes')
    else:
        print('No')
else:
    if '...' in S[B - 2:D + 1] and '##' not in S[A:C - 1]:
        print('Yes')
    else:
        print('No')

Measured memory_bytes: 3572
# https://atcoder.jp/contests/abc139/tasks/abc139_c

n = int(input())
nums = [int(i) for i in input().split()]
nums.append(float('inf'))
ans = 0
t = 0
for i in range(n):
    if nums[i] >= nums[i + 1]:
        t += 1
    else:
        ans = max(ans, t)
        t = 0
print(ans)

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

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double, int> pdbi;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
typedef vector<vector<int>> mat;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const ll INF = 1<<30;
const ll mod = 1000000000 + 7;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;

//#define int long long
#define addm(X, Y) (X) = ((X) + ((Y) % mod) + mod) % mod

int n;

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (true) {
        cin >> n;
        if (n == 0) break;
        int ans = 0;
        rep2(w, 2, n) {
            if (w * (w - 1) + 2 * w > 2 * n) break;
            if ((2 * n - w * (w - 1)) % (2 * w) == 0) ans++;
        }
        cout << ans << endl;
    }

}

Measured memory_bytes: 3068
N=int(input())
H=list(map(int, input().split()))
H=list(reversed(H))
ans='Yes'
for i in range(N-1):
    if H[i]<H[i+1]:
        if H[i]<H[i+1]-1:
            ans='No'
        else:
            H[i+1]=H[i+1]-1
print(ans)

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

int S(int x) {
  int sum = 0;
  while (x) {
    sum+= x % 10;
    x/=10;
  }
  return sum;
}

int main() {
  int n;
  cin>>n;
  puts(n%S(n)?"No":"Yes");
}


Measured memory_bytes: 256
import java.util.*;


public class Main {
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        //int a = sc.nextInt();
        
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        
        int[] l = {a,b,c};
        
        for(int i = 0 ;i<l.length-1;i++){
            for(int j = l.length-1 ;j > i;j--){
                	if(l[j]<l[j-1]){
                	  int t=l[j];
                	  l[j]=l[j-1];
                	  l[j-1]=t;
                	}
            }
        }
        
        System.out.println(l[0]+" "+l[1]+" "+l[2]);
    
    }
}


Measured memory_bytes: 26108
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <locale>
#include <iostream>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> int len(const T &x) { return x.size(); }

template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
  auto val = table(args...);
  return vector<decltype(val)>(n, move(val));
}

struct yes_no : numpunct<char> {
  string_type do_truename()  const { return "Yes"; }
  string_type do_falsename() const { return "No"; }
};

void solve(ll N, vector<ll> a) {
  sort(a.rbegin(), a.rend());
  ll res = 0;
  REP(i,N) {
    res += a[i * 2 + 1];
  }
  cout << res << endl;
}


int main() {
  locale loc(locale(), new yes_no);
  cout << boolalpha << setprecision(12) << fixed;
  cout.imbue(loc);
	ll N;
	scanf("%lld", &N);
	vector<ll> a(3*N-1+1);
	for (int i = 0 ; i <= 3*N-1 ; i++) {
	  scanf("%lld", &a[i]);
	}
	solve(N, a);
	return 0;
}


Measured memory_bytes: 4992
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 100000
using namespace std;
int main()
{
	int n; cin >> n;
  	vector<int> odd, even;
  	int count_e[MAX + 1], count_o[MAX + 1];
  	int mode_e, mode_o, submode_e, submode_o, mode_o_num, mode_e_num;
  	for (int i = 0; i < n; i++){
      	int v; cin >> v;
    	if (i % 2 == 0){
        	even.push_back(v);
        } else {
        	odd.push_back(v);
        }
    }
  	for (int i = 0; i <= MAX; i++){
    	count_e[i] = 0;
      	count_o[i] = 0;
    }
  	for (int i = 0; i < even.size(); i++){
    	count_e[even[i]]++;
    }
  	for (int i = 0; i < odd.size(); i++){
    	count_o[odd[i]]++;
    }
  	auto max_iterator_e = std::max_element(count_e, count_e + MAX + 1);
  	mode_e = (int)std::distance(count_e, max_iterator_e);
  	auto max_iterator_o = std::max_element(count_o, count_o + MAX + 1);
  	mode_o = (int)std::distance(count_o, max_iterator_o);
  	if (mode_e != mode_o){
    	cout << (even.size() - count_e[mode_e]) + (odd.size() - count_o[mode_o]);
      	return 0;
    } else {
    	mode_e_num = count_e[mode_e];
      	mode_o_num = count_o[mode_o];
		count_e[mode_e] = 0;
      	count_o[mode_o] = 0;
      	auto max_iterator_e = std::max_element(count_e, count_e + MAX + 1);
  		submode_e = (int)std::distance(count_e, max_iterator_e);
  		auto max_iterator_o = std::max_element(count_o, count_o + MAX + 1);
  		submode_o = (int)std::distance(count_o, max_iterator_o);
      	int move1 = (even.size() - mode_e_num) + (odd.size() - count_o[submode_o]);
      	int move2 = (odd.size() - mode_o_num) + (even.size() - count_e[submode_e]);
      	cout << min(move1, move2);
    }
}

Measured memory_bytes: 1660
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <string>
#include <random>
#include <stack>
#include <set>
#include <unordered_set>

#define bug(x) cout<<"zdongdebug: "<<x<<endl;
#define bug2(x, y) cout<<"zdongdebug: "<<x<<" "<<y<<endl;
using namespace std;
typedef unsigned long long ll;
const int maxn = 100005;

ll cal(ll n, ll a, ll b){
  if(a>=b)return n;
  return n/a*b + n % a;
}
ll solve(ll n, vector<ll>a, vector<ll>b) {
  vector<int>ca,cb;
  for(int i=0;i<3;i++){
    if(b[i]>a[i]){
      ca.push_back(a[i]);
      cb.push_back(b[i]);
    }
  }
  if(ca.size()==1){
    return cal(n,ca[0],cb[0]);
  } else if(ca.size()==2){
    ll ret = n;
    for(int i=0;i<=n;i++)
      ret=max(ret, cal(i,ca[0],cb[0])+cal(n-i,ca[1],cb[1]));
    return ret;
  } else if(ca.size()==3){
    ll ret = n;
    for(int i=0;i<=n;i++)
      for(int j=0;j+i<=n;j++){
        ret=max(ret, cal(i,ca[0],cb[0])+cal(j,ca[1],cb[1])+cal(n-i-j,ca[2],cb[2]));
      }
    return ret;
  }
  return n;
}

int main() {
#ifdef suiyuan2009
  freopen("/Users/suiyuan2009/CLionProjects/icpc/input.txt", "r", stdin);
  //freopen("/Users/suiyuan2009/CLionProjects/icpc/output.txt", "w", stdout);
#endif
  ll n;
  vector<ll>a,b;
  cin>>n;
  for(int i=0;i<3;i++){
    ll x;
    cin>>x;
    a.push_back(x);
  }
  for(int i=0;i<3;i++){
    ll x;
    cin>>x;
    b.push_back(x);
  }
  n = solve(n, a,b);
  n = solve(n, b,a);
  cout<<n<<endl;
  return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;

namespace AtCoder.DP
{
    class EDPC_B
    {
        public static void Main()
        {
            var nk = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
            var h = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
            var n = nk[0];
            var k = nk[1];

            var dp = new int[n];

            for (int i = 1; i < n; i++)
            {
                int min = int.MaxValue;
                int j0 = Math.Max(i - k, 0);
                for (int j = j0; j < i; j++)
                {
                    int cost = dp[j] + Math.Abs(h[j] - h[i]);
                    if (min > cost)
                        min = cost;
                }
                dp[i] = min;
            }
            Console.WriteLine(dp[n - 1]);
        }
    }
}


Measured memory_bytes: 20064
#include <bits/stdc++.h>
#define ALL(v) v.begin(), v.end()
#define MOD 1000000007
#define INF 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define req(i, j, n) for(int i = j; i <= (int)(n); i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
 
int main() {
    double a,b,p,q,r;
    cin>>a>>b>>p>>q>>r;
    
    double l=p*b-q*(b-a);
    
    double ans=l/(q+r);
    
    double cnt=ans+b;
   cout << fixed << setprecision(6);
 
    cout<<cnt<<endl;
    return 0;
}


Measured memory_bytes: 3272
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

// inf
constexpr ll infl = 10000000000000000LL;
constexpr int inf = 1000000000;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int ans = (c - (a - b));

    cout << (ans < 0 ? 0 : ans) << endl;
    return 0;
}

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

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

const long long INF = 1LL << 60;
int cnt[10010];

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

  REP(x, 1, 100){
    REP(y, 1, 100){
      REP(z, 1, 100){
        int f = x*x + y*y + z*z + x*y + y*z + z*x;
        if(1<=f && f<=10000) cnt[f]++;
      }
    }
  }

  REP(i, 1, n){
    cout << cnt[i] << endl;
  }

  return 0;
}


Measured memory_bytes: 3620
#include<iostream>
using namespace std;
int main()
{
  int r,g,b,n,i,j,m,res=0;
  cin >> r >> g >> b >> n;
  for(i=0;i<=n/r;i++){
    m=n-i*r;
    for(j=0;j<=m/g;j++)
      if((m-j*g)%b==0) res++;
  }   
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
ll mod=998244353;
ll mul(ll a, ll b)
{
	return ((a%mod)*(b%mod))%mod;
}
ll add(ll a, ll b)
{
	return ((a%mod)+(b%mod))%mod;
}
ll sub(ll a, ll b)
{
	return ((a%mod)-(b%mod)+mod)%mod;
} 
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
ll n;
ll out[503][503];
ll occ[503][503];
void dfs(ll x, ll y)
{
	ll z=out[x][y]+occ[x][y];
	for(ll i=0;i<4;i++)
	{
		ll x1=x+dx[i];
		ll y1=y+dy[i];
		if(out[x1][y1]>z)
		{
			out[x1][y1]=z;
			dfs(x1,y1);
		}
	}
}
int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=n;j++)
		{
			out[i][j]=min(min(i-1,abs(n-i)),min(j-1,abs(n-j)));
			occ[i][j]=1;
	
		}
	}
	ll m=n*n;
	ll pr=0;
	while(m--)
	{
		ll id;
		cin>>id;
		ll x=(id+n-1)/n;
		ll y=id%n;
		if(y==0)
		{
			y=n;
		}
		occ[x][y]=0;
		pr+=out[x][y];
		dfs(x,y);
	}
	cout<<pr;
}

Measured memory_bytes: 23060
#include <bits/stdc++.h>
#define pb push_back
#define cmin(a,b) (a>b?a=b:a)
#define cmax(a,b) (a<b?a=b:a)
#define mem(a,k) memset(a,k,sizeof(a))
#define lop(i,s,t) for(int i=s;i<(t);++i)
#define rep(i,s,t) for(int i=s;i<=(t);++i)
#define dec(i,s,t) for(int i=s;i>=(t);--i)
#define fore(i,v) for(int i=g[v],d=es[i].d;i;i=es[i].nxt,d=es[i].d)
using namespace std;

#define Pr(f,...) //fprintf(stderr,f,##__VA_ARGS__),fflush(stderr)

typedef long long ll;

template<typename T>
void read(T &x){
	x=0; 
	char C;
	for(C=getchar();!isdigit(C);C=getchar()); 
	for(;isdigit(C);C=getchar())x=x*10+C-'0'; 
}

const int N=705,M=N*N;

int n,m,suc=1,g[N][N],col[N],deg[N],X,Y,f[N][N];

void dfs(int v,int c){
	col[v]=c;
	Y+=c==1;
	X+=c==-1;
	rep(d,1,n)if(d!=v){
		if(col[d]==0&&!g[v][d])dfs(d,-c); 
		if(col[d]!=0&&!g[v][d])suc&=c*col[d]<0; 
	}
}
int S(int x){return x*(x-1)/2;}
vector<pair<int,int> >ans;

int main(int argc,char *argv[]){
#ifdef CURIOUSCAT
#endif
	read(n),read(m); 
	rep(i,1,m){
		int u,v;
		read(u),read(v); 
		g[u][v]=g[v][u]=1;
		++deg[u],++deg[v];
	}
	rep(i,1,n)if(col[i]==0){
		dfs(i,1); 
		ans.pb(make_pair(X,Y)); 
		X=Y=0;
	}
	if(!suc){
		puts("-1"); 
		return 0; 
	}
	f[0][0]=1;
	for(int i=1;i<=ans.size();++i){
		int x=ans[i-1].first,y=ans[i-1].second;
		rep(j,x,n)f[i][j]|=f[i-1][j-x];
		rep(j,y,n)f[i][j]|=f[i-1][j-y];
	}
	int z=ans.size(),res=1e9; 
	rep(i,0,n)if(f[z][i])res=min(res,S(i)+S(n-i)); 
	printf("%d\n",res);
	return 0;
}

Measured memory_bytes: 4096
#include <bits/stdc++.h>
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end() 
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define INF 1000000000
using namespace std;
typedef long long ll;

int main(){
    int H, W, K;
    cin >> H >> W >> K;

    vector<vector<char>> f (H, vector<char>(W));
    REP(i, H){
        REP(j, W){
            cin >> f[i][j];
        }
    }

    int ans = 0;
    for (int h = 0; h < (1<<H); ++h) {
        for(int w = 0; w < (1<<W); ++w){
            int res = 0;
            REP(i, H) {
                REP(j, W){
                    if (h & (1<<i)){
                        if (w & (1<<j)) {
                            if(f[i][j] == '#') res++;
                        }
                    }
                }
            }
            if (res == K) ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <numeric>
 
#define rep(n) for(int i = 0; i < n; i++)
 
using namespace std;
 
int main () {
  long long N; cin >> N;
  vector<long long> a;
 
  rep(N) {
    long long b; cin >> b;
    a.push_back(b);
  }
 
  vector<long long> v;
  vector<long long> va;
 
  rep(N) {
    v.push_back(a[i] - (i + 1));
  }
 
  sort(v.begin(), v.end());
 
  int cet;
 
  if(N%2 != 0) {
    cet = v[(N - 1) / 2];
  } else {
    cet = (v[N / 2] + v[(N - 2) / 2]) / 2;
  }
 
 
  rep(N) {
    va.push_back(abs(a[i] - (i + 1 + cet)));
  }
 
  long long j = 0;
    rep(N) {
    j += va[i];
  } 
  
  cout << j << endl;

}

Measured memory_bytes: 6512
package main

import (
	"fmt"
//	"strconv"
//	"sort"
//	"math"
//	"regexp"
)


var N int

func main(){
	fmt.Scan(&N)
	a:=make(map[int]int,N)
	
	for i:=0;i<N;i++{
		var t int
		fmt.Scan(&t)
		a[i+1] = t
	}

	var cnt int
		t := 1
	for i:=0;i<len(a);i++{
		
		t = a[t]
		cnt++

		if t == 2 {
			fmt.Println(cnt)
			return
		}

	}
	fmt.Println(-1)
}



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

int main(){
    string S;
    cin>>S;
    rep(i,S.size()-1){
        if(S.at(i)=='A'){
            if(S.at(i+1)=='C'){
                cout<<"Yes"<<endl;
                return 0;
            }
        }
    }
    cout<<"No"<<endl;
return 0;}
/*compile
g++ code.cpp
./a.out
run*/
/*
int f(int x){
    int y=int((x*x+4.0)/8.0);
    return y;
}
*/

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

using namespace std;

int main(){
    int N,A,B;
    cin>>N>>A>>B;
	int sum=0;
	int a=0;
	int total=0;
    for(int i=1 ; i<=N ; i++){
    	sum=0;
    	a=i;
    	sum+=a%10;
    	if(a/10>0){
    		a/=10;
    		sum+=a%10;
    	}
    	if(a/10>0){
    		a/=10;
    		sum+=a%10;
    	}
    	if(a/10>0){
    		a/=10;
    		sum+=a%10;
    	}
    	if(a/10>0){
    		a/=10;
    		sum+=a%10;
    	}
    	if(a/10>0){
    		a/=10;
    		sum+=a%10;
    	}
    	//cout<<sum<<endl;
    	if(sum>=A && sum<=B)total+=i;
    }
    cout<<total<<endl;
    
    
    
    return 0;
}


Measured memory_bytes: 256
//              +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+              \\

#include <bits/stdc++.h>

#define F first
#define S second
#define _sz(x) (int)x.size()

using namespace std ;
using ll = long long ;
using ld = long double ;
using pii = pair <int , int> ;

int const N = 1e5 + 20 , inf = 1e9 + 20 ;
int n , a[N] ;
int cnt[2 * N] , part[2 * N] ;
ll med ;

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

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

	med = 1ll * n * (n + 1) / 4 + 1;

	int low = 0 , high = inf ;

	while (high - low > 1) {
		memset(cnt , 0 , sizeof cnt) ;
		
		int mid = (low + high) / 2 ;
		
		int cur = 0 ;
		ll res = 0 ;


		part[0] = N ;
		cnt[N] = 1 ;

		for (int i = 0 ; i < n ; i ++) {
			if (a[i] <= mid) cur += cnt[part[i]] ;
			else cur -= cnt[part[i] - 1] ;

			part[i + 1] = part[i] + (a[i] <= mid ? 1 : -1) ;
			cnt[part[i + 1]] ++ ;

			res += cur ;
		}

		if (res >= med) high = mid ;
		else low = mid ;
	}

	cout << high << '\n' ;
}

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

long long d[3009][3009][2], md = 998244353;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int a, b, n, m; cin >> a >> b >> n >> m;
	d[a][b][0] = 1;
	long long t = 1;
	for (int i = a + 1; i <= n; i++) {
		d[i][b][0] = (d[i - 1][b][0] * b) % md;
		d[i][b][1] = d[i][b][0];
	}
	for (int i = b + 1; i <= m; i++) {
		d[a][i][0] = (d[a][i - 1][0] * a) % md;
		d[a][i][1] = (d[a][i - 1][1] * (a - 1) + t * a) % md;
		t = (t * (a - 1)) % md;
	}
	for (int i = a + 1; i <= n; i++)
		for (int j = b + 1; j <= m; j++) {
			d[i][j][0] = (d[i - 1][j][0] * j + d[i][j - 1][0] * i - d[i][j - 1][1] * (i - 1)) % md;
			d[i][j][0] = (d[i][j][0] + md) % md;
			d[i][j][1] = (d[i - 1][j][0] * j) % md;
		}
	cout << d[n][m][0] << '\n';
	return 0;
}

Measured memory_bytes: 144568
from collections import Counter
n = int(input())
x = [int(i) for i in input().split()]
a,b = [],[]
for i in range(n):
	if i%2: a.append(x[i])
	else: b.append(x[i])
ca,cb = Counter(a).most_common(),Counter(b).most_common()
if ca[0][0]!=cb[0][0]: print(n-ca[0][1]-cb[0][1])
elif len(ca)!=1 and len(cb)!=1: print(min(n-ca[0][1]-cb[1][1],n-ca[1][1]-cb[0][1]))
elif len(ca)==len(cb): print(n//2)
elif len(ca)==1: print(n//2-cb[1][1])
else: print(n//2-ca[1][1])

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

#define vec(v) vector<int>(v)
#define be(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define mapci(mp) map<char*,int>(mp)
#define mapcc(mp) map<char*,char*>(mp)
typedef long long ll;
using namespace std;

int main(){
	int n;
	cin>>n;
	int a[9]={0},b,c=0;
	for(int i=0;i<n;i++){
		cin>>b;
		if(b<3200){
			a[b/400]++;
		}
		else{
			a[8]++;
		}
	}
	for(int i=0;i<9;i++){
		if(a[i]!=0){
			c++;
		}
	}
	if(a[8]==0){
		cout << c<<" "<<c<<endl;
	}
	else{
		if(c==1){
			cout << 1<<" "<<a[8]<<endl;
		}
		else{
			cout << c-1<<" "<<c-1+a[8]<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef priority_queue<int> PQ;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 2147483647
#define LLINF 2147483647
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;

int N, Q;
//const int INF = INF_MAX;
struct LazySegmentTree {
private:
	int n;
	vector<ll> node, lazy;
	vector<bool> lazyFlag;

public:
	LazySegmentTree(vector<int> v) {
		int sz = (int)v.size();
		n = 1; while (n < sz) n *= 2;
		node.resize(2 * n - 1);
		lazy.resize(2 * n - 1, INF);
		lazyFlag.resize(2 * n - 1, false);

		for (int i = 0; i < sz; i++) node[i + n - 1] = v[i];
		for (int i = n - 2; i >= 0; i--) node[i] = min(node[i * 2 + 1], node[i * 2 + 2]);
	}

	void lazyEvaluate(int k, int l, int r) {
		if (lazyFlag[k]) {
			node[k] = lazy[k];
			if (r - l > 1) {
				lazy[k * 2 + 1] = lazy[k * 2 + 2] = lazy[k];
				lazyFlag[k * 2 + 1] = lazyFlag[k * 2 + 2] = true;
			}
			lazyFlag[k] = false;
		}
	}

	void update(int a, int b, int x, int k = 0, int l = 0, int r = -1) {
		if (r < 0) r = n;
		lazyEvaluate(k, l, r);
		if (b <= l || r <= a) return;
		if (a <= l && r <= b) {
			lazy[k] = x;
			lazyFlag[k] = true;
			lazyEvaluate(k, l, r);
		}
		else {
			update(a, b, x, 2 * k + 1, l, (l + r) / 2);
			update(a, b, x, 2 * k + 2, (l + r) / 2, r);
			node[k] = min(node[2 * k + 1], node[2 * k + 2]);
		}
	}

	int find(int a, int b, int k = 0, int l = 0, int r = -1) {
		if (r < 0) r = n;
		lazyEvaluate(k, l, r);
		if (b <= l || r <= a) return INF;
		if (a <= l && r <= b) return node[k];
		int vl = find(a, b, 2 * k + 1, l, (l + r) / 2);
		int vr = find(a, b, 2 * k + 2, (l + r) / 2, r);
		return min(vl, vr);
	}
};
signed main(){
cin.tie(0);
ios::sync_with_stdio(false);

	cin >> N >> Q;
	LazySegmentTree seg(vector<int>(N, INF));
	for (int i = 0; i < Q; i++) {
		int query; cin >> query;
		if (query == 0) {
			int s, t, x; cin >> s >> t >> x;
			seg.update(s, t + 1, x);
		}
		else {
			int s, t; cin >> s >> t;
			cout << seg.find(s, t + 1) << endl;
		}
	}
	return 0;
}




Measured memory_bytes: 7872
#include<cstdio>
#include<cstring>
#define mod 1000000007
#define ran 333333
char s[ran];int n;
int a[ran],p2[ran];
int dp[3],dp2[3];
int add(int x,int y){
	return (x+=y)<mod?x:x-mod;
}
void addto(int&x,int y){
	x =add(x,y);
}
int mul(int x,int y){
	return (int)((long long int)x*y%mod);
}
const int trans[3][4]={
{0,1,0,1},
{0,1,2,3},
{2,2,2,3}
};
int main(){
	scanf("%s",s);
	n = strlen(s);
	if(n == 1){
		printf("%d\n",s[0]=='0'?0:1);
		return 0;
	}
	p2[0] = 1;for(int i=1; i<=n; i++)p2[i] = add(p2[i-1],p2[i-1]);
	for(int i=n-1; i>=0; i--)a[i] = a[i+1] + (s[i] == '?');

	int res = 0;
	for(int i=0; i<n-1; i+=2){
		dp2[0] = dp2[1] = dp2[2] = 0;
		for(int c1=0; c1<2; c1++)if(s[i] == '?' || s[i] == c1 + '0')
			for(int c2=0; c2<2; c2++)if(s[i+1] == '?' || s[i+1] == c2 + '0'){
				int T = c1 * 2 + c2;
				if(i==0){
					if(T == 3)addto(res, p2[a[i+2]]);else
						addto(dp2[T], 1);
				}else{
					for(int k=0; k<3; k++)
						if(trans[k][T] == 3)
							addto(res, mul(dp[k],p2[a[i+2]]));
						else
							addto(dp2[trans[k][T]], dp[k]);
				}
		}
		dp[0] = dp2[0];
		dp[1] = dp2[1];
		dp[2] = dp2[2];
	}
	if(s[n-1] == '?' || s[n-1] == '1'){
		addto(res,dp[1]);
		addto(res,dp[2]);
	}
	printf("%d\n",res);
	return 0;
}

Measured memory_bytes: 2816
#include<stdio.h>
 int time(int a,int b){
   int ans = 0;
   ans = a * b;
   
return ans;
  }

int main(void){
  int c,d;
  
  scanf("%d",&c);
  scanf("%d",&d);
 printf("%d",time(c,d));
return 0;
}
   

Measured memory_bytes: 1692