akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>

using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
template <class T> int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define popcount __builtin_popcount

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

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

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

const double PI = acos(-1.0);
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };



const int MAX_PRIME = 1200;
bool is_prime[MAX_PRIME + 1];
vector<int> primes;
void sieve()
{
	fill_n(is_prime, MAX_PRIME + 1, true);
	is_prime[0] = is_prime[1] = false;
	for (int i = 2; i * i <= MAX_PRIME; ++i)
	{
		if (is_prime[i])
		{
			for (int j = 2 * i; j <= MAX_PRIME; j += i)
				is_prime[j] = false;
		}
	}
	for (int i = 0; i <= MAX_PRIME; ++i)
		if (is_prime[i])
			primes.push_back(i);
}
int main()
{
	sieve();

	static int dp[16][1200];
	dp[0][0] = 1;
	for (int i = 0; primes[i] <= 1120; ++i)
		for (int j = 14; j > 0; --j)
			for (int k = primes[i]; k <= 1120; ++k)
				dp[j][k] += dp[j - 1][k - primes[i]];

	int n, k;
	while (scanf("%d%d", &n, &k), n | k)
		printf("%d\n", dp[k][n]);
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <iomanip>
using namespace std;

int main() {
  int N;
  int K;
  cin >> N >> K;
  
  double p=0;

  for(int i=0;i<N;i++){
        int check=i+1;
        int count=0;
      while(check<K){
          check*=2;
          count++;
      }
        //cout << count <<endl;
                //cout << (pow(0.5,count)) <<endl;
      p+=pow(0.5,count)/(double)N;


  }
  
    cout << fixed << setprecision(12) << p << endl;
}

Measured memory_bytes: 256
/**
 * http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_D
 */

#include <iostream>
#include <sstream>
#include <vector>
#include <limits>

unsigned long long bubbleSort(std::vector<unsigned int>& A) {
  unsigned int N = A.size();
  unsigned long long Count {0};
  bool isSwapped = false;
  for (size_t i = 0; i < N; i++) {
    for (size_t j = N - 1; j >= i + 1; j--) {
      if (A[j] < A[j - 1]) {
        std::swap(A[j], A[j - 1]);
        isSwapped = true;
        Count++;
      }
    }
    if (isSwapped == false) {
      break;
    }
    isSwapped = false;
  }
  return Count;
}

unsigned long long merge(std::vector<unsigned int> &A, const unsigned int &left,
           const unsigned int &mid, const unsigned int &right) {
  unsigned int n1 = mid - left;  // 5 - 0
  unsigned int n2 = right - mid; // 9 - 6
  // L[0...n1], R[0...n2] ?????????
  std::vector<unsigned int> L(n1 + 1); // 0 1 2 3 4 MAX
  std::vector<unsigned int> R(n2 + 1); // 5 6 7 8 9 MAX
  unsigned long long Count {0};

  for (size_t i = 0; i < n1; i++) {
    L[i] = A[left + i];
  }
  for (size_t i = 0; i < n2; i++) {
    R[i] = A[mid + i];
  }
  L[n1] = std::numeric_limits<unsigned int>::max();
  R[n2] = std::numeric_limits<unsigned int>::max();
  unsigned int i = 0;
  unsigned int j = 0;
  for (size_t k = left; k < right; k++) {
    if (L[i] <= R[j]) {
      A[k] = L[i];
      i++;
    } else {
      A[k] = R[j];
      j++;
      Count += n1 - i;  // mid + j - k - 1
    }
  }
  return Count;
}

unsigned long long mergeSort(std::vector<unsigned int> &A, const unsigned int &left,
               const unsigned int &right) {
  if (left + 1 < right) {
    unsigned int mid = (left + right) / 2;
    unsigned long long Count = mergeSort(A, left, mid);
    Count += mergeSort(A, mid, right);
    Count += merge(A, left, mid, right);
    return Count;
  } else {
    return 0;
  }
}

unsigned long long mergeSort(std::vector<unsigned int> &A) {
  unsigned long long Count = mergeSort(A, 0, A.size());
  return Count;
}

int main(int argc, char const *argv[]) {
  std::string Param;
  std::istringstream Stream;
  unsigned int n;
  std::vector<unsigned int> A;

  getline(std::cin, Param);
  Stream.str(Param);
  Stream >> n;
  Stream.clear();

  getline(std::cin, Param);
  Stream.str(Param);
  for (size_t i = 0; i < n; i++) {
    unsigned int Ai = 0;
    Stream >> Ai;
    A.push_back(Ai);
  }
  Stream.clear();

  unsigned long long Count {0};
  // Count = bubbleSort(A);
  Count = mergeSort(A);

  std::cout << Count << std::endl;
  return 0;
}

Measured memory_bytes: 8576
#include "bits/stdc++.h"

#define REP(i,n) for(ll i=0;i<n;++i)
#define RREP(i,n) for(ll i=n-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<n;++i)
#define RFOR(i,m,n) for(ll i=n-1;i>=m;--i)
#define ALL(v) (v).begin(),(v).end()
#define PB(a) push_back(a)
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define DUMP(v) REP(i, (v).size()) { cout << v[i]; if (i != v.size() - 1)cout << " "; else cout << endl; }
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll max(ll a, int b) { return max(a, ll(b)); }
ll max(int a, ll b) { return max(ll(a), b); }
ll min(ll a, int b) { return min(a, ll(b)); }
ll min(int a, ll b) { return min(ll(a), b); }
///(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)///
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vl v(3*n);
	REP(i, 3*n)cin >> v[i];
	sort(ALL(v),greater<ll>());
	ll ans = 0;
	REP(i, 2*n) {
		if(i % 2 == 1)ans += v[i];
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 2560
/*  -*- coding: utf-8 -*-
 *
 * e.cc: E - Hopscotch Addict
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100000;
const int K = 3;
const int MAX_GN = MAX_N * K;

/* typedef */

typedef vector<int> vi;
typedef queue<int> qi;

/* global variables */

vi nbrs[MAX_GN];
int ds[MAX_GN];

/* subroutines */

/* main */

int main() {
  int n, m;
  scanf("%d%d", &n, &m);

  for (int i = 0; i < m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    u--, v--;
    int uk = u * K, vk = v * K;
    for (int j = 0; j < K; j++)
      nbrs[uk + j].push_back(vk + (j + 1) % K);
  }

  int s, t;
  scanf("%d%d", &s, &t);
  s--, t--;
  int st = s * K, gl = t * K;

  memset(ds, -1, sizeof(ds));
  ds[st] = 0;

  qi q;
  q.push(st);

  while (! q.empty()) {
    int u = q.front(); q.pop();
    if (u == gl) break;

    int vd = ds[u] + 1;
    vi &nbru = nbrs[u];
    for (vi::iterator vit = nbru.begin(); vit != nbru.end(); vit++) {
      int &v = *vit;
      if (ds[v] < 0) {
	ds[v] = vd;
	q.push(v);
      }
    }
  }

  printf("%d\n", (ds[gl] < 0) ? -1 : ds[gl] / K);
  return 0;
}


Measured memory_bytes: 17792
#include <algorithm>
#include <cstdio>

typedef std::pair<int,int> Pa;
const int mo=1000000007;

long long fac[205],inv[205],ans=1;
int dfn[55],low[55],fst[55],c[55],k,tot=1,cnt=0,top=0,col=0;
bool vis[105];
Pa stack[105];

struct Edge{
	int to,nxt;
}e[205];

void addedge(int x,int y){
	e[++tot].to=y;e[tot].nxt=fst[x];fst[x]=tot;
}

int C(int n,int m){return fac[n]*inv[m]%mo*inv[n-m]%mo;}

int INV(int n){return inv[n]*fac[n-1]%mo;}

int gcd(int x,int y){return y?gcd(y,x%y):x;}

int ksm(int x,int y){
	int i=1;
	for (;y;y>>=1,x=1ll*x*x%mo)
		if (y&1) i=1ll*i*x%mo;
	return i;
}

void tarjan(int x){
	dfn[x]=low[x]=++cnt;
	for (int i=fst[x];i;i=e[i].nxt)
	if (!vis[i>>1]){
		int y=e[i].to;
		stack[++top]=Pa(x,y);
		vis[i>>1]=1;
		if (!dfn[y]){
			tarjan(y);
			low[x]=std::min(low[x],low[y]);
			if (low[y]>=dfn[x]){
				int cntv=0,cnte=0;
				for (++col;top;){
					if (c[stack[top].first]!=col) c[stack[top].first]=col,cntv++;
					if (c[stack[top].second]!=col) c[stack[top].second]=col,cntv++;
					cnte++;
					if (stack[top--]==Pa(x,y)) break;
				}
				if (cnte==1) ans=ans*k%mo;
					else if (cntv!=cnte) ans=ans*C(cnte+k-1,k-1)%mo;
						else{
							int val=0;
							for (int j=0;j<cnte;j++) (val+=ksm(k,gcd(j,cnte)))%=mo;
							ans=ans*val%mo*INV(cnte)%mo;
						}
			}
		}
		else low[x]=std::min(low[x],dfn[y]);
	}
}

void Pre(int n){
	fac[0]=1;
	for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mo;
	inv[n]=ksm(fac[n],mo-2);
	for (int i=n;i>=1;i--) inv[i-1]=inv[i]*i%mo;
}

int main(){
	int n,m;
	scanf("%d%d%d\n",&n,&m,&k);
	for (int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d\n",&x,&y);
		addedge(x,y);
		addedge(y,x);
	}
	Pre(m+k);
	for (int i=1;i<=n;i++)
		if (!dfn[i]) tarjan(i);
	printf("%lld\n",ans);
}

Measured memory_bytes: 128
def to_alphabet(n):
    S = "abcdefghijklmnopqrstuvwxyz"
    if (n - 1) // 26:
        return to_alphabet((n - 1) // 26) + S[(n - 1) % 26]
    return S[(n - 1) % 26]

n = int(input())
print(to_alphabet(n))

Measured memory_bytes: 9172
#include <stdio.h>
#include <bits/stdc++.h>
#define pb push_back
#define pp pop_back
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
typedef long long ll;

using namespace std;

const int N = 3e5 + 111, inf = 1e9, mod = 1e9 + 7, C = 2000;
const double pi = acos(-1.0), eps = 1e-9;
const ll INF = 1e18;



int main(){
	srand(time(NULL));
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	cout << setprecision(10) << fixed;

	int a, b;
	cin >> a >> b;
	if(a <= 0 && 0 <= b){
		cout << "Zero";
		return 0;
	}


	int c = max(0, min(b, -1) - a + 1);

	if(c % 2 == 0)
		cout << "Positive";
	else cout << "Negative";	

	//cout << (clock() + 0.0) / CLOCKS_PER_SEC;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/range/adaptor/reversed.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
typedef long long int ll;

#define PI (acos(-1))
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define dumparr(x) cerr << #x ; for(auto elem: x){cerr << " " << elem;} cerr << endl;
#define dumppairs(x) cerr << #x ; for(auto elem: x){cerr << "(" << elem.first << " " << elem.second << ") ";} cerr << endl;
#define dumpline cerr << "**********************" << endl;
#define dumpwline(x) cerr << "******** " << #x << "=" << (x) << " ********" << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

int main(void){
    ll n; cin >> n;
    ll k; cin >> k;
    ll c; cin >> c;
    string s; cin >> s;
    vector<ll>can(n, 0);
    ll last = 1e9;
    ll lastcan = 0;
    for(int i=n-1; i>=0; i--){
        if ((last - c > i) && (s[i] == 'o')){
            lastcan++;
            can[i] = lastcan;
            last = i;
        } else {
            can[i] = lastcan;
        }
    }
    vector<ll>best(n, 0);
    last = -1e9;
    lastcan = 0;
    REP(i, n){
        if ((last + c < i) && (s[i] == 'o')){
            lastcan++;
            best[i] = lastcan;
            last = i;
        } else {
            best[i] = lastcan;
        }
    }
    map<pair<ll, ll>, vector<ll>> mp;
    ll mx = 0;
    REP(i, n){
        mp[{best[i], can[i]}].push_back(i);
        mx = max(mx, best[i]+can[i]);
    }
    if (mx - 1 != k){
        return 0;
    }
    vector<ll> ans;
    for(auto p: mp){
        if (p.first.first + p.first.second -1 == k){
            if (p.second.size() == 1){
                ans.push_back(p.second[0]);
            }
        };
    }
    for(auto a: ans){
        cout << a+1 << endl;
    }
    return 0;
}

Measured memory_bytes: 28404
#include<stdio.h>
int main(void){
    int n=0;
    scanf("%d",&n);

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

    int y=0;
    int highest=0;

    for(int i=0;i<n;i++){
        if(highest<=H[i]){
            y+=1;
            highest=H[i];
        }
    }
    printf("%d",y);
    return 0;
}

Measured memory_bytes: 128
PROGRAM ATCODER

implicit none
integer(16) :: i,j,n,m,k,ans=0,count
integer(16),allocatable :: a(:),b(:),c(:),d(:),i_d(:),index(:)

read*, n,m 
allocate(a(n),b(m),c(m))
read*, a(1:n)
do i = 1, m, 1
  read*, b(i),c(i)
end do

allocate(d(n+m),i_d(n+m),index(n+m))
i_d = 1

do i = 1, n+m, 1
  if ( i >= n+1 ) then
    d(i) = c(i-n)
    i_d(i) = b(i-n)
  else
    d(i) = a(i)
  end if
end do

call heapsort2(n+m,d,index)

count = n
do i = n+m, m+1, -1
  if ( count - i_d(index(i)) <= 0 ) then
    ans = ans + count*d(i)
    exit
  end if
  ans = ans + i_d(index(i))*d(i)
  count = count - i_d(index(i))
end do

print'(i0)', ans

contains
  subroutine heapsort2(n,array,turn)
  implicit none
  integer(16),intent(in)::n
  integer(16),intent(out)::turn(1:n)
  integer(16),intent(inout)::array(1:n)
  
  integer::i,k,j,l,m
  double precision::t
  
  if(n.le.0)then
     write(6,*)"Error, at heapsort"; stop
  endif
  if(n.eq.1)return

  do i=1,N
     turn(i)=i
  enddo

  l=n/2+1
  k=n
  do while(k.ne.1)
     if(l.gt.1)then
        l=l-1
        t=array(l)
        m=turn(l)
     else
        t=array(k)
        m=turn(k)
        array(k)=array(1)
        turn(k)=turn(1)
        k=k-1
        if(k.eq.1) then
           array(1)=t
           turn(1)=m
           exit
        endif
     endif
     i=l
     j=l+l
     do while(j.le.k)
        if(j.lt.k)then
           if(array(j).lt.array(j+1))j=j+1
        endif
        if (t.lt.array(j))then
           array(i)=array(j)
           turn(i)=turn(j)
           i=j
           j=j+j
        else
           j=k+1
        endif
     enddo
     array(i)=t
     turn(i)=m
  enddo

  return
  end subroutine heapsort2


END PROGRAM ATCODER

Measured memory_bytes: 14848
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

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

	int ans = 0;
	int mx = 0;
	for (int i = 0; i < n; i++) {
		ans += (s[i] == 'I') ? 1 : -1;
		mx = max(ans, mx);
	}
	cout << mx << endl;

	return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(S: str, T: str):
    if S == T[:-1]:
        print(YES)
    else:
        print(NO)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    T = next(tokens)  # type: str
    solve(S, T)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9056
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(ll i = 0; i<(ll)(n); i++)
#define REPS(i,n) for (ll i = 1; i<=(ll)(n); i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define pb push_back
#define MOD 1000000007
#define MOD2 998244353
#define PI 3.141592653

int main(){
	ll n, m; cin >> n >> m;
	vector<ll> h(n);
	vector<ll> ans(n,1);
	REP(i,n) cin >> h[i];
	REP(i,m){
		ll a, b; cin >> a >> b;
		if (h[a-1]<h[b-1]){
			ans[a-1]=0;
		}
		else if (h[a-1]>h[b-1]){
			ans[b-1]=0;
		}
		else{
			ans[a-1]=0;
			ans[b-1]=0;
		}
	}
	ll tans = 0;
	REP(i,n){
		tans += ans[i];
	}
	cout << tans << endl;
}

Measured memory_bytes: 4848
#include <iostream>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const long long INF = 1LL<<60;

int n;
long long w, weight[110], value[110];


long long dp[101][100010] = {0};

int main() {
  cin >> n >> w;
  for (int i = 0; i < n; i++) {
    cin >> weight[i] >> value[i];
  }

  for (int i = 0; i < n; i++) {
    for (int sum_w = 0; sum_w <= w; sum_w++) {

      if (sum_w - weight[i] >= 0) {
        chmax(dp[i+1][sum_w],dp[i][sum_w - weight[i]] + value[i]);
      }

      chmax(dp[i+1][sum_w],dp[i][sum_w]);
    }
  }
  cout << dp[n][w]  << endl;
}

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

using namespace std;

#define inf 1<<30
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define fn fill_n
typedef long long llong;
typedef unsigned long long ullong;
typedef pair<int, int> P;
struct UnionFind{
	vector<int> par;

	UnionFind(){};
	UnionFind(int n){
		par.resize(n);
		for(int i = 0; i < n; i++)
			par[i] = i;
	};
	int find(int n){
		if(par[n] == n) return n;
		return par[n] = find(par[n]);
	};
	bool isSame(int a, int b){
		return find(a) == find(b);
	};
	void marge(int a, int b){
		a = find(a);
		b = find(b);
		if(a == b) return;
		par[a] = b;
		return;
	};
};

int N, M;
int id[100001] = {};
UnionFind uf;

int main(){
	cin >> N >> M;
	uf = UnionFind(N+1);
	int in;
	for(int i = 1; i <= N; i++){
		cin >> in;
		id[in] = i;
	}
	int a, b;
	for(int i = 0; i < M; i++){
		cin >> a >> b;
		uf.marge(a,b);
	}
	int cnt = 0;
	for(int i = 1; i <= N; i++)
		if(uf.isSame(i, id[i]))
			cnt++;

	cout << cnt << endl;

	return 0;
}

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

#define rep2(x,fr,to) for(int x=(fr);x<(to);x++)
#define rep(x,to) for(int x=0;x<(to);x++)
#define repr(x,fr,to) for(int x=(fr);x>=(to);x--)
#define all(c) c.begin(),c.end()
#define sz(v) (int)v.size()

using namespace std;
typedef int64_t ll; typedef vector<int> VI; typedef pair<int,int> pii;
typedef vector<ll> VL; const int MD = 1e9 + 7;
void dbg(){cerr<<"\n";} template <typename T,typename ...T2> void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }


int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n, p; string s;
	cin >>n >>p >>s;
	ll ans = 0;
	if(p==2 || p==5){
		rep(i, n) if((s[i]-'0')%p==0) ans +=i+1;
		cout << ans <<"\n"; return 0;
	}
	VL ct(p); ll ks=1, cr=0; ct[0]=1;
	repr(i, n-1, 0){
		int d = s[i]-'0';
		cr = (d * ks + cr) % p;
		ct[cr]++;
		ks = ks * 10 % p;
	}
	for(auto z: ct)  ans += z * (z-1LL) /2;
	cout << ans <<"\n";
	return 0;
}


Measured memory_bytes: 720
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define double long double
using namespace std;
//桁
int kt(int a){
  double b=a;
  b=log10(b);
  int c=b;
  return c+1;
 }
int lcm(int a,int b){
  int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return d*e/f;
    }
  int gcm(int a,int b){
      int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return f;
  }
signed main(){
  int a;
  cin>>a;
 vector<int> b(a);
  rep(i,a)
    cin>>b[i];
  int c=0;
  rep(i,a){
  for(int j=i+1;j<a;j++){
  for(int k=j+1;k<a;k++){
    int d=max(b[i],b[j]);
    int e=max(b[k],d);
    if(b[i]+b[j]+b[k]-e>e)
      c++;
  }
  }
  }
  cout<<c;
}


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

typedef long long ll;
typedef vector <ll> v_ll;
typedef vector <vector <ll> > vv_ll;
typedef vector < pair <ll,ll> > vp_ll;
typedef pair <ll,ll> p_ll;

ll N,M;
v_ll A;
vp_ll B;


int main(){
  cin >> N >> M;
  A.assign(N+10,0);
  B.assign(M+10,make_pair(0,0));
  for (ll i=1;i<=N;i++){
    cin >> A[i];
  }
  sort(A.begin()+1,A.begin()+N+1);

  for (ll i=1;i<=M;i++){
    cin >> B[i].second >> B[i].first;
  }
  sort(B.begin()+1,B.begin()+M+1,greater<p_ll>());
  /*
  for (ll i=1;i<=N;i++){
    cout << A[i] << " ";
  }cout << endl;

  for (ll i=1;i<=M;i++){
    cout << B[i].first <<" "<< B[i].second<<endl;
  }cout << endl;
*/
  ll i=1,j=1;
  while (i<=N && j<=M){
    for (ll k=0;k<B[j].second;k++){
      if (B[j].first>A[i]){
        A[i]=B[j].first;
      }
      i++;
      if (i>N)break;
    }j++;
  }
  ll ans=0;
  for (ll i=1;i<=N;i++){
    ans+=A[i];
  }
  cout << ans << endl;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
#define ll long long
#define sz(a) (int)(a).size()
#define rep(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define frep(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define debug(a) cerr << #a << ": " << (a) << '\n';

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<ii> vii;

const int INF = 1000000000 + 7;
const ll LL_INF  = 1ll * INF * INF;
const int MAX_N = 100000 + 7;
const int multipleTest = 0;

template <typename T>
inline void addmod(T& a, const ll& b, const int& MOD = INF) {
  a = (a + b) % MOD; if (a < 0) a += MOD;
}

vii calc(vector<int>& a) {
  map<int, int> cnt;
  for (int& x : a) cnt[x]++;
  vector<ii> cur;
  for (auto p : cnt)
    cur.push_back({p.second, p.first});
  sort(cur.begin(), cur.end(), std::greater<ii>());
  if (cur.size() > 2) cur.resize(2);
  return cur;
}

void solve() {
  int n;
  cin >> n;
  vector<int> even, odd;
  rep(i, 0, n) {
    int u; cin >> u;
    if (i & 1) odd.push_back(u);
    else even.push_back(u);
  }
  auto lhs = calc(even), rhs = calc(odd);

  int res = 0;
  if (lhs[0].second != rhs[0].second) {
    res = lhs[0].first + rhs[0].first;
  } else {
    if (rhs.size() > 1) res = max(res, lhs[0].first + rhs[1].first);
    if (lhs.size() > 1) res = max(res, lhs[1].first + rhs[0].first);
    res = max(res, max(lhs[0].first, rhs[0].first));
  }
  cout << n - res;
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
#ifdef _LOCAL_
  freopen("in.txt", "r", stdin);
  //freopen("out.txt", "w", stdout);
#endif
  int Test = 1;
  if (multipleTest)
    cin >> Test;

  for(int i = 0; i < Test; ++i) {
    //printf("Case #%d: ", i + 1);
    solve();
  }
#ifdef _LOCAL_
  cerr << "\n" << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
#endif
}


Measured memory_bytes: 4216
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
if N == 1:
	print(0)
	sys.exit()

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

e = [0] * (N+1)
for i in range(2, N+1):
	for x in factorization(i):
		e[x[0]] += x[1]

# print(e)

ans = 0

def num(m):
	return len([x for x in e if x >= m-1])

# 同じ素数はとらないように選択, 3*5*5のときは重複するので2で割る
print(num(75)+num(25)*(num(3)-1)+num(15)*(num(5)-1)+num(5)*(num(5)-1)*(num(3)-2)//2)


Measured memory_bytes: 5188
#[allow(unused_imports)]
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::Chars;
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused)]
const ALPHA_SMALL: [char; 26] = [
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's',
    't', 'u', 'v', 'w', 'x', 'y', 'z',
];
#[allow(unused)]
const ALPHA: [char; 26] = [
    'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S',
    'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
];
#[allow(unused)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
#[allow(unused)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(unused)]
fn read_touple<T: std::str::FromStr + Copy>() -> (T, T) {
    let v: Vec<T> = read_vec();
    assert_eq!(v.len(), 2);
    (v[0], v[1])
}
fn main() {
    input!(A: usize, B: usize, C: usize, D: usize, E: usize, F: usize);
    let mut ans = (1_000_000_000, 0);
    for i in 0..=110 {
        for j in 0..=110 {
            for c in 0..=40 {
                for d in 0..=40 {
                    let water = 100 * A * i + 100 * B * j;
                    let suger = C * c + D * d;
                    // 砂糖水に溶けられる砂糖の最大量
                    let capacity = (A * i + B * j) * E;
                    // 砂糖と水を合わせた全体の量がF以下になる
                    let b1 = water + suger <= F;
                    // 砂糖が全て溶けている
                    let b2 = suger <= capacity;
                    if suger + water == 0 {
                        continue;
                    }
                    if b1 && b2 {
                        let sum = ans.0;
                        let sgr = ans.1;
                        if sgr * (water + suger) <= suger * sum {
                            ans = (water + suger, suger);
                        }
                    }
                }
            }
        }
    }

    println!("{} {}", ans.0, ans.1);
}


Measured memory_bytes: 2156
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
//#define ll long long
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 (a>b) { a=b; return 1; } return 0; }
#define rep(i, n) REP(i, 0, n)
#define rep_rev(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
ll t1,t2,t3;
const ll mod = 998244353;
const int INF = 1e9;
const ll INFLONG = 1e18;


int main(){
  ll h1,m1,h2,m2,k;
  cin >> h1 >> m1 >> h2 >> m2 >> k;
  t1 = h2 - h1;
  t2 = m2-m1;
  t3 = t1 * 60 + t2;
  cout << t3 - k << endl;
}

Measured memory_bytes: 3632
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
const int MaxN = 1e5;

int vis[30];

int main()
{
	char s[30];
	int n,biu;
	while(~scanf("%s",s))
	{
		memset(vis,0,sizeof(vis));
		n = strlen(s);
		biu = 1;
		for(int i = 0;i < n;i++)
		{
			vis[s[i]-'a'] = 1;
		}
		if(n < 26)
		{
			for(int i = 0;i < 26;i++)
			{
				if(vis[i]==0)
				{
					s[n] = 'a' + i;
					s[n+1] = '\0';
					break;
				}
			}
		}
		else
		{
			biu = 0;
			for(int i = 25;i >= 0;i--)
			{
				for(int j = s[i]-'a'+1;j < 26;j++)
				{
					if(vis[j]==0)
					{
						s[i] = j + 'a';
						s[i+1] = '\0';
						biu = 1;
						break;
					}
				}
				if(biu==1) break;
				vis[s[i]-'a'] = 0;
			}
		}
		if(biu==0) printf("-1\n");
		else printf("%s\n",s);
	}
	return 0;
}

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

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    if (a != 2 && b != 2) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


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

template
<
    typename TYPE,
    std::size_t SIZE
>
std::size_t a_len(const TYPE (&array)[SIZE])
{
    return SIZE;
}

using namespace std;
using ll = long long int;
using vi = vector<ll>;

#define REPS(a,i,n) for(ll (i) = a ; (i) < (n) ; ++(i))
#define REP(i,n) REPS(0,i,n)

const int INF = 100001;

string s;

int main()
{
    cin >> s;
    string ans = "2018";
    REPS(4,i,s.length()){
        ans+=s[i];
    } 
    cout << ans << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
            var x1 = input[0];
            var y1 = input[1];
            var x2 = input[2];
            var y2 = input[3];
            var xLength = Math.Abs(x2 - x1);
            var yLength = Math.Abs(y2 - y1);
            int x3 = 0, y3 = 0, x4 = 0, y4 = 0;

            if (x1 <= x2)
            {
                if (y1 <= y2)
                {
                    x3 = x2 - yLength;
                    y3 = y2 + xLength;
                    x4 = x3 - xLength;
                    y4 = y3 - yLength;
                }else
                {
                    x3 = x2 + yLength;
                    y3 = y2 + xLength;
                    x4 = x3 - xLength;
                    y4 = y3 + yLength;
                }
            }else
            {
                if (y1 <= y2)
                {
                    x3 = x2 - yLength;
                    y3 = y2 - xLength;
                    x4 = x3 + xLength;
                    y4 = y3 - yLength;
                }else
                {
                    x3 = x2 + yLength;
                    y3 = y2 - xLength;
                    x4 = x3 + xLength;
                    y4 = y3 + yLength;
                }
            }

            Console.WriteLine(x3 + " " + y3 + " " + x4 + " " + y4);
        }
    }
}

Measured memory_bytes: 11348
import itertools
import copy
n = int(input())
P = list(map(int, input().split()))
Q = tuple(list(map(int, input().split())))
P_ = copy.copy(P)
P_.sort()
p_list = list(itertools.permutations(P_))
P = tuple(P)

a = p_list.index(P)
b = p_list.index(Q)

print(abs(a-b))

Measured memory_bytes: 14156
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		new Main().run();
	}

	private void run() throws IOException {
		Scanner scanner = new Scanner(System.in);
		while (true) {
			n = scanner.nextInt();
			if (n == 0)
				break;
			d = new int[n][n];
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++)
					d[i][j] = scanner.nextInt();
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++)
					d[i][j] = Math.max(d[i][j], d[j][i]);
			ans = INF;
			used = new boolean[n];
			pos = new int[n];
			dfs(0);
			System.out.println(ans);
		}
	}

	private void dfs(int right) {
		if (right >= ans)
			return;
		int a = 0, b = 0;
		int[] na = new int[n], nb = new int[n];
		for (int i = 0; i < n; i++)
			if (!used[i])
				na[a++] = i;
			else
				nb[b++] = i;

		if(a==0){
			ans = right;
			return;
		}
		for (int i = 0; i < a; i++) {
			int u = na[i];
			for (int j = 0; j < b; j++) {
				int v = nb[j];
				pos[u] = Math.max(pos[u], pos[v] + d[v][u]);
			}
			used[u] = true;
			dfs(pos[u]);
			used[u] = false;
			pos[u] = 0;
		}
	}

	int n, ans;
	int[] pos;
	int[][] d;
	int INF = 1 << 30;
	boolean[] used;
}

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

int main()
{
    int a, b, res;
    char op;
    while(1){
        scanf("%d %c %d", &a, &op, &b);
        if ( op == '+' ){
            res = a + b;
            printf("%d\n", res);
        } else if ( op == '-' ){
            res = a - b;
            printf("%d\n", res);
        } else if ( op == '*' ){
            res = a * b;
            printf("%d\n", res);
        } else if ( op == '/' ){
            res = a / b;
            printf("%d\n", res);
        } else {
            break;
        }  
    } 
        return 0;
}           



Measured memory_bytes: 2088
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
#define print(x) cout<<x<<endl;
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
#define int long long
#define all(x) (x).begin(), (x).end()

using namespace std;

const int MAX = 1010000;
const int MOD = (ll)1000000000 + 7;
const ll INF = 1e17;
const double pi = acos(-1);
const double EPS = 1e-10;

typedef pair<int, int>P;

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

int N, Q;
string S;
char t[200020], d[200020];

bool checkL(int n) {
	int pos = n;
	REP(i, Q) {
		
		if (S[pos] == t[i]) {
			if (d[i] == 'L')pos--;
			else pos++;
		}
		if (pos < 0)return true;
		if (pos >= N)return false;
	}
	return false;
}

bool checkR(int n) {
	int pos = n;
	REP(i, Q) {

		if (S[pos] == t[i]) {
			if (d[i] == 'L')pos--;
			else pos++;
		}
		if (pos < 0)return false;
		if (pos >= N)return true;
	}
	return false;
}


signed main() {
	cin >> N >> Q;
	cin >> S;
	REP(i, Q) {
		cin >> t[i] >> d[i];
	}
	int l = N / 2, r = N / 2;
	if (!checkL(0))l = -1;
	if (!checkR(N - 1))r = N;
	int ok = -1, ng = N;
	if (l != -1) {
		while (abs(ng - ok > 1)) {
			l = (ng + ok) / 2;
			if (checkL(l)) {
				ok = l;
			}
			else ng = l;
		}
		l = (ng + ok) / 2;
	}
	
	ok = -1, ng = N;
	if (r != N) {
		while (abs(ng - ok > 1)) {
			r = (ng + ok )/ 2;
			if (checkR(r)) {
				ng = r;
			}
			else ok = r;
		}
		r = (ng + ok+1) / 2;
	}
	//pe(ok)print(ng);
	//pe(l)print(r);
	if (r - l <= 0) {
		print(0);
		return 0;
	}
	else {
		int ans = N;
		if (l >= 0) {
			ans -= l + 1;
		}
		if (r < N) {
			ans -= N - r;
		}
		print(ans);
	}
}	


Measured memory_bytes: 900
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2005;
const int mod=1e9+7;
int fact[N*N],inv[N*N];
int d[N][N];
int n,k;
void Init()
{
	fact[0]=1;
	for(int i=1;i<=n*k;i++) fact[i]=1ll*fact[i-1]*i%mod;
	inv[1]=1;
	for(int i=2;i<=n*k;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	inv[0]=1;
	for(int i=1;i<=n*k;i++) inv[i]=1ll*inv[i-1]*inv[i]%mod;
}
int C(int x,int y){
    return 1ll*fact[x]*inv[y]%mod*inv[x-y]%mod;
}
int main()
{
    scanf("%d%d",&n,&k);
    if(k==1){
        puts("1");
        return 0;
    }
    Init();
    d[0][0]=1;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=i;j++){
            if(i>0)
                d[i][j]+=d[i-1][j],d[i][j]%=mod;
            if(j>0){
                int x=n*k-i-(j-1)*(k-1)-1;
                d[i][j]+=1ll*d[i][j-1]*C(x,k-2)%mod;
                d[i][j]%=mod;
            }
        }
    int ans=1ll*d[n][n]*fact[n]%mod;
    printf("%d\n",ans);
}


Measured memory_bytes: 46336
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define All(V) V.begin(), V.end()
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD = 1e9+7, INF = 1e9;

int main()
{
  ll n, k; cin >> n >> k;
  ll ans = 0;
  for(ll i = k; i <= n+1; i++){
    ll a = n*(n+1)/2;
    ll b = (n-i)*(n-i+1)/2;
    ll c = (i-1)*i/2;
    ans += (a-b) - c + 1;
    ans %= MOD;
  }
  cout << ans << endl;
  system("pause");
}


Measured memory_bytes: 3708
main=readLn>>=print.f
 where f n = (if (g n n)==8 then 1 else 0)+(if n==1 then 0 else (f (n-1)))
       g n i |odd n     = (if (mod n i)==0 then 1 else 0)+(if i==1 then 0 else (g n (i-1)))
             |otherwise = 0

Measured memory_bytes: 1020
import bisect


def CumulativeSum(l):
    a = [0]
    for i in l:
        a.append(a[-1] + i)
    return a[1:]


def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    b = CumulativeSum(a)
    s = b[-1]
    h = s // 2
    x = bisect.bisect_left(b, h)
    try:
        m = (b[x], b[x + 1], b[x - 1])
    except:
        m = (b[x], b[x - 1])
    if s % 2 == 0 and h in m:
        print(0)
        return

    print(min([abs(x * 2 - s) for x in m]))


if __name__ == '__main__':
    resolve()


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

typedef long long ll;

int main() {
  std::string S;
  std::cin >> S;

  bool isYYMM = S.substr(2, 2) <= "12" and S.substr(2, 2) >= "01";
  bool isMMYY = S.substr(0, 2) <= "12" and S.substr(0, 2) >= "01";

  if(isYYMM and isMMYY) {
    std::cout << "AMBIGUOUS" << std::endl;
    return 0;
  } else if (isYYMM) {
    std::cout << "YYMM" << std::endl;
    return 0;
  } else if (isMMYY) {
    std::cout << "MMYY" << std::endl;
    return 0;
  } else {
    std::cout << "NA" << std::endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <climits>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++ )
#define FOR(i,m,n) for(int (i)=m;(i)<n;(i)++)




int main(){
    
    int a,b,k;
    cin>>a>>b>>k;
    int cnt=0;
    for(int i=100;i>=1;i--){
        if(a%i==0&&b%i==0){
            cnt++;
            if(cnt==k){
                cout<<i<<endl;
                return 0;
            }
        }
    }
    cout<<"e"<<endl;
    return 0;

}


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

int main(){
    int n,m,result[100001];
    cin >> n >> m;
    vector<int> G[100001],visited;
    set<int> rG[100001];
    for(int i = 0;i < n-1+m;i ++){
        int a,b;
        cin >> a >> b;
        G[a].push_back(b);
        rG[b].insert(a);
    }
    for(int i = 1;i <= n;i ++){
        if(rG[i].empty()){
            visited.push_back(i);
            result[i] = 0;
            break;
        }
    }
    while(!visited.empty()){
        int v = visited[visited.size()-1]; 
        visited.pop_back();
        for(int i = 0;i < G[v].size();i ++){
            rG[G[v][i]].erase(v);
            if(rG[G[v][i]].empty()){
                visited.push_back(G[v][i]);
                result[G[v][i]] = v;
            }
        }
    }
    for(int i = 1;i <= n;i ++){
        cout << result[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 16000
n, x = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

B = A[:]
ans = sum(A)

for i in range(1, n):
    for j in range(n):
        B[j] = min(B[j], A[j-i])
    ans = min(ans, sum(B) + i * x)

print(ans)

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

int main() {
    int k, s;
    cin >> k >> s;

    long long int ans = 0;

    for (int x = 0; x < k+1; x++) {
        if (x > s)
            continue;
        for (int y = 0; y < k+1; y++) {
            if (x + y > s)
                continue;
            if (s - x - y > k)
                continue;
            ans += 1;
        }
    }
    cout << ans<< endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int n,i,x=0,y=0;
	long long a[100000],b=1;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%lld",&a[i]);
		if(a[i]==0) x=1;
	}
	if(x==1) printf("0\n");
	else{
		for(i=0;i<n;i++){
			if(a[i]<=1000000000000000000/b) b*=a[i];
			else{
				printf("-1\n");
				return 0;
			}
		}
		printf("%lld\n",b);
	}
	return 0;
}

Measured memory_bytes: 2436
#define w 200001
i;x;y;p;main(n,m,j,u){
  long int k,a[w],A[w],b[w],B[w];
  for(scanf("%d%d%ld",&n,&m,&k);x<n;x++)scanf("%ld",&a[x]),A[x+1]=A[x]+a[x];
  for(;y<m;y++)scanf("%ld",&b[y]),B[y+1]=B[y]+b[y];
  j=u=m;
        
  for(;i<=n;i++){
    if(A[i]>k)break;
            
    for(;j+1;j--){
      if(A[i]+B[j]<=k){
        if(i+j>p)p=i+j;
        u=j;
        break;
      }
    }
  }
  printf("%d",p);
}

Measured memory_bytes: 7964
#include<iostream>
#include<sstream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf = (int)1e9;
const double INF = 1e12, EPS = 1e-9;

const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1};
int n, dp[40000], st[40000], k;
map<pi, int> id;
vi x, y, d;

bool rec(int cx, int cy, int cd){
	queue<pair<pi, int> > q;
	q.push(mp(mp(cx, cy), cd));
	dp[st[k++] = id[mp(cx, cy)]] = cd;
	
	while(!q.empty()){
		cx = q.front().first.first; cy = q.front().first.second;
		cd = q.front().second;
		q.pop();
		
		rep(d, 4){
			int nx = cx + dx[d], ny = cy + dy[d];
			if(!id.count(mp(nx, ny))) continue;
			int ii = id[mp(nx, ny)];
			int nd = ii == (id[mp(cx, cy)] ^ 1) ? 1 - cd : cd;
			
			if(dp[ii] >= 0 && dp[ii] != nd) return 0;
			if(dp[ii] >= 0) continue;
			dp[st[k++] = ii] = nd;
			q.push(mp(mp(nx, ny), nd));
		}
	}
	return 1;
}

int main(){
	while(scanf("%d", &n), n){
		x.clear(); y.clear(); d.clear();
		id.clear();
		
		rep(i, n){
			int a, b; char c;
			scanf("%d%d %c", &a, &b, &c);
			x.pb(a); y.pb(b); d.pb(c == 'x');
			id[mp(a, b)] = i * 2;
			id[mp(a + d[i], b + 1 - d[i])] = i * 2 + 1;
		}
		memset(dp, -1, sizeof(dp));
		rep(i, 2 * n) if(dp[i] < 0){
			k = 0;
			if(rec(x[i / 2], y[i / 2], 0)) continue;
			while(k) dp[st[--k]] = -1;
			if(!rec(x[i / 2], y[i / 2], 1)){
				cout << "No" << endl;
				goto END;
			}
		}
		cout << "Yes" << endl;
		END:;
	}
	return 0;
}

Measured memory_bytes: 4232
s = input()
arr = [7,6,5,4,3,2,1]
if s == "SUN":
    print(arr[0])
elif s == "MON":
    print(arr[1])
elif s == "TUE":
    print(arr[2])
elif s == "WED":
    print(arr[3])
elif s == "THU":
    print(arr[4])
elif s == "FRI":
    print(arr[5])
elif s == "SAT":
    print(arr[6])


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

#define vec     vector<int>
#define vecll   vector<ll>
#define vec2    vector<vector<int>>
#define vec2ll  vector<vector<ll>>
#define vpair   vector<pair<int, int>>
#define vpairll vector<pair<ll, ll>>
#define rep(i,n)         for(ll i=(ll)0; i<(ll)n; i++)
#define REP(i,m,n)       for(ll i=(ll)m; i<(ll)n; i++)
#define arr(var, n)      vec var(n); rep(i,n){cin >> var[i];}
#define arrll(var, n)    vecll var(n); rep(i,n){cin >> var[i];}
#define all(var)         (var).begin(), (var).end()
#define sortall(var)     sort(all(var))
#define mpair(v1, v2)    make_pair(v1, v2)
#define pb(var)          push_back(var)
#define prt(var)         cout << var << "\n"
#define scn(var)         cin >> var;
#define pYes()           prt("Yes")
#define pNo()            prt("No")
#define prtd(n, var)     cout << fixed << setprecision(n) << var << "\n"
#define prt2(v1, v2)     cout << v1 << " " << v2 << "\n"
#define prt3(v1, v2, v3) cout << v1 << " " << v2 << " " << v3 << "\n"
#define prtall(var)      rep(i,var.size()){cout << var[i] << " ";} cout << "\n"

//----------------------------------------------------

int main(){
    string s, t;
    cin >> s >> t;
    for(int i = 0; i < s.size(); i++){
        if(s[i] != t[i]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;

}

Measured memory_bytes: 3624
n = int(input())
h = list(map(int,input().split()))
dp = [0]*n
dp[0] = 0
dp[1] = abs(h[1]-h[0])
for i in range(1,n-1):
    dp[i+1] = min(dp[i-1]+abs(h[i+1]-h[i-1]),dp[i]+abs(h[i+1]-h[i]))
print(dp[-1])

Measured memory_bytes: 13928
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;

int main(){
  int n,k,ans = 1;
  cin >> n >> k;
  for(int i = 0; i < n; i ++){
    if(ans*2 < ans+k) ans *= 2;
    else ans += k;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
/**
 * author:    Ziel
 * created:   21.04.2020 11:17:18
**/

// ~zaletaet~

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>

#define fi first
#define se second
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back

using namespace std;

using ll = long long;
using ull = unsigned long long;
// using big = __int128_t; // -10^38...10^38
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;

const ll N = 1e5 + 123, MOD = 1e9 + 7, oo = 1e9 + 9, INF = 1e18 + 9;
const double EPS = 1e-9, PI = acos(-1); // 3.14159265358979323846
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1}, dy[] = {0, 0, 1, -1, 1, -1, -1, 1};

inline ll pw(ll a, ll n) {
	ll res = 1;
	while (n) {
		if (n & 1) res = res * a % MOD;
		a = a * a % MOD;
		n >>= 1;
	}
	return res;
}

ll f[N];

inline ll nCr(ll n, ll k) {
	if (n < k || n < 0 || k < 0) return 0;
	if (!n && !k) return 1;
	return f[n] * pw(f[k], MOD - 2) % MOD * pw(f[n - k], MOD - 2) % MOD;
}

main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	
	int n;
	cin >> n;
	
	vector<int> a(n + 2);
	vector<int> pos(n + 2, -1);
	
	int fi = -1, se = -1;
	for (int i = 0; i <= n; i++) {
		cin >> a[i];
		
		if (pos[a[i]] == -1) pos[a[i]] = i;
		else fi = pos[a[i]], se = i;
	}
	
	f[0] = 1;
	for (int i = 1; i <= n + 10; i++) f[i] = f[i - 1] * i % MOD;
	
	for (int k = 1; k <= n + 1; k++) {
		cout << (nCr(n + 1, k) - nCr(fi + n - se, k - 1) + MOD) % MOD << '\n';
	}
	
	return 0;
}



Measured memory_bytes: 2816
#include<iostream>
#include<string>

using namespace std;

int main(){
	string s1, s2;
  
  cin>>s1>>s2;
  
  if((s1.length()+1)!=s2.length()){
  	cout<<"No"<<endl;
    return 0;
  }
  
  for(int i=0;i<s1.length();i++){
  	if(s1[i]!=s2[i]){
    cout<<"No"<<endl;
    return 0;
    }
  }
  cout<<"Yes"<<endl;
}

Measured memory_bytes: 3628
import java.util.*;

class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N=sc.nextInt();
int a1=sc.nextInt();
int max=a1;
int min=a1;
for(int i=2;i<=N;i++){
  int a = sc.nextInt();
if(max<a)
max=a;
if(min>a)
min=a;
}
System.out.println(max-min);
}
}


Measured memory_bytes: 23892
n = int(input())
a,b = map(int, input().split())
l = map(int, input().split())
x,y,z = 0,0,0
for i in l:
  if i<=a:
    x+=1
  elif i>a and i<=b:
    y+=1
  elif i>b:
    z += 1
print(min(x,min(y,z)))

Measured memory_bytes: 9188
n = int(input())
A = [int(i) for i in input().split()]

x = sum(A)/len(A)
totals = []
for i in range(min(A), max(A)+1):
    total = 0
    for a in A:
      total += (a-i)**2
    totals.append(total)
print(min(totals))

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

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


int main(){
  string s; cin>>s;
  if(s=="Sunny") cout<<"Cloudy"<<endl;
  else if(s=="Rainy") cout<<"Sunny"<<endl;
  else if(s=="Cloudy") cout<<"Rainy"<<endl;
}

Measured memory_bytes: 256