akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<string>
#include<queue>
#include<utility>
#include<cmath>
#include<sstream>
#include<istream>

using namespace std;


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

  string S;
  cin >> S;

  int cnt=0;

  for(int i=0; i<N-2; i++){
    if(S[i]=='A' && S[i+1]=='B' && S[i+2]=='C'){
      cnt++;
    }
  }

  cout << cnt << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }
#define dump(x) cerr<<#x<<": "<<x<<endl;
#define bit(k) (1LL<<(k))
typedef long long ll;
typedef pair<int, int> i_i;
typedef pair<ll, ll> l_l;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 >& p) {
  os << "{" <<p.first << ", " << p.second << "}";
  return os;
}
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 int INF = (ll)1e9;
const ll INFLL = (ll)1e18+1;
const ll MOD = (ll)1e9+7;
const double PI = acos(-1.0);
/*
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const string dir = "DRUL";
*/
template<typename T>
vector<T> divisor(T N) {
    vector<T> res;
    for(T i = 1; i * i <= N; i++){
        if(N % i == 0){
            res.push_back(i);
            if(i * i != N)res.push_back(N / i);
        }
    }
    sort(res.begin(), res.end());
    return res;
}
template<typename T> 
map<T,int> factorize(T x){
    map<T,int> mp;
    for (T i = 2; i*i <= x; i++){
        while (x%i == 0) {
            x /= i;
            mp[i]++;
        }
        if (x == 1) break;
    }
    if (x != 1) mp[x]++;
    return mp;
}

int A[200010];
int mp[2000100];
int main() {
    int N;
    cin >> N;
    rep(i, N){
        cin >> A[i];
        mp[A[i]]++;
    }
    int ans = 0;
    rep(i,N){
        if(mp[A[i]] > 1)continue;
        bool ok = true;
        mp[A[i]]--;
        auto v = divisor(A[i]);
        for(auto &p: v){
            if(mp[p] > 0){
                ok = false;
                //break;
            }
        }
        mp[A[i]]++;
        if(ok)ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 8288
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		int x = sc.nextInt();

		int min = x-k+1;
		int max = x+k-1;

		StringBuilder sb = new StringBuilder();
		for(int i=min; i<=max; i++) {
			if(i > 1000000 || i < -1000000) {
				break;
			}
			if(i == min) {
				sb.append(i);
			} else {
				sb.append(" " + i);
			}
		}
		System.out.println(sb.toString());
	}
}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define contains(v, t) (find(v.begin(), v.end(), t) != v.end())
#define MOD 1000000007
typedef long long ll;
typedef unsigned long long ull;

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> h(n);
  rep(i, n) cin >> h[i];
  vector<set<int>> v(n);
  rep(i, m) {
    int a, b;
    cin >> a >> b;
    v[a - 1].insert(b - 1);
    v[b - 1].insert(a - 1);
  }
  int ans = 0;
  rep(i, n) {
    int height = h[i];
    bool yoi = true;
    for (int s : v[i]) {
      if (h[s] >= height) {
        yoi = false;
      }
    }
    if (yoi) ans++;
  }
  cout << ans;
}

Measured memory_bytes: 17700
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

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

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

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

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

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

    ($next:expr, i321) => {
        read_value!($next, i32) - 1
    };

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

//
// # Examples
//
// # integers
// input! { n: i32, m: i32, ... }
//
// # array
// input! { n: i32, v: [i32; n], }
//
// # matrix
// input! { n: i32, m: i32, mat: [[]] }
//
// # string
// input! { s: chars }
//
// 3 4
// ####
// #..#
// .#.#
//
// input!{
//     h: i32,
//     w: i32,
//     board: [chars; h],
// }

// https://practice.contest.atcoder.jp/tasks/practice_1
//fn main() {
//    input!{
//        a: i32, b: i32, c: i32,
//        foo: chars,
//    }
//    let s: String = foo.into_iter().collect();
//    println!("{} {}", a+b+c, s);
//}
fn main() {
    input!{
        a: i32, b: i32
    }
    let mut ans = a;
    if a > b {
        ans -= 1;
    }
    println!("{}", ans);
}

Measured memory_bytes: 4352
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int maxn=1e6+5;
const int imax=1e6;
const int inf=999999999;
int en,n,a[maxn],b[maxn];
typedef long long ll;
ll tree[maxn],sum[maxn],c[maxn];

/*struct node
{
	int x,id;
//	node(int x,int id):x(x),id(id){}
}p[maxn];*/

struct node
{
    int x,id;
    node(){}
    bool operator < (const node &a) const
    {
        if(a.x==x) return id<a.id;
        return x>a.x;
    }
}p[maxn];

bool cmp(node a,node b)
{
	return a.x==b.x?a.id<b.id:a.x>b.x;
}


void build(int l,int r,int rt)
{
	if(l==r)
	{
		tree[rt]=sum[l]-c[l-1];
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,rt*2);
	build(mid+1,r,rt*2+1);
	tree[rt]=min(tree[rt*2],tree[rt*2+1]); 
}

ll qu(int L,int R,int l,int r,int rt)
{
	if(L>R)	return inf;
	if(r<L||l>R)	return inf;
	if(l>=L&&r<=R)	return tree[rt];
	int mid=(l+r)>>1;
	int a1=inf,a2=inf;
	a1=qu(L,R,l,mid,rt*2);
	a2=qu(L,R,mid+1,r,rt*2+1);
	return min(a1,a2);
}

bool check(int i,int mid)
{
    if(i>mid) return sum[mid]+a[p[i].id]>=en;
    return sum[mid]-p[i].x+a[p[i].id]>=en;
}


int main()
{
	int ans=inf;
	c[0]=0;
	sum[0]=0;
	scanf("%d%d",&n,&en);
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d",a+i,b+i);
		p[i].x=a[i]-b[i];
		p[i].id=i;
	}
	for(int i=1;i<=n;++i)
	{
		scanf("%lld",c+i);
		c[i]+=c[i-1];
	}
	sort(p+1,p+1+n,cmp);
	for(int i=1;i<=n;++i)	sum[i]=sum[i-1]+p[i].x;
	build(1,n,1);
	int gg=n;
	for(int i=1;i<=n;++i)
	{
		if(p[i].x<0)
		{
			gg=i;
			break;
		}
		
	}
	gg++;
	int num=1;
	while(sum[num]>c[num])
	{
		if(num>n)	break;
		num++;
	}
	for(int i=1;i<=n;++i)
	{
		int l=0,r=n+1;
		while(l<r)
		{
			int mid=(l+r)/2;
			if(check(i,mid))	r=mid;
			else l=mid+1;
		}
		if(r>n)	continue;
		if(r<i)
		{
			if(r<num)	ans=min(ans,r+1);
		}
		else
		if(qu(i+1,r,1,n,1)>p[i].x)	ans=min(ans,r);
	}
	if(ans==inf)	printf("-1\n");
	else printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 7904
import collections
import sys
input=sys.stdin.readline

def divisors(n):
  ret=[]
  for i in range(2,int(n**0.5)+1):
    if n%i==0:
      ret.append(i)
      while n%i==0:
        n//=i
  if n!=1:
    ret.append(n)
  return ret

def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)

n=int(input())
arr=list(map(int,input().split()))
cnt=[False]*(max(arr)+1)
is_pairwise=True
tmp=arr[0]
for val in arr:
  tmp=gcd(tmp,val)
  if is_pairwise==False:
    continue
  divisor=divisors(val)
  for val2 in divisor:
    if cnt[val2]==True:
      is_pairwise=False
      break
    cnt[val2]=True
if tmp==1:
  is_setwise=True
else:
  is_setwise=False
if is_pairwise==True:
  print('pairwise coprime')
elif is_setwise==True:
  print('setwise coprime')
else:
  print('not coprime')

Measured memory_bytes: 179748
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define maxs(x, y) (x = max(x, y))
#define mins(x, y) (x = min(x, y))
#define limit(x, l, r) max(l, min(x, r))
#define lims(x, l, r) (x = max(l, min(x, r)))
#define isin(x, l, r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)), x.end())
#define snuke srand((unsigned)clock() + (unsigned)time(NULL));
#define show(x) cout << #x << " = " << x << endl;
#define PQ(T) priority_queue<T, v(T), greater<T>>
#define bn(x) ((1 << x) - 1)
#define dup(x, y) (((x) + (y)-1) / (y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;
ll INF = 1e9;
int main() {
  int h, n;
  cin >> h >> n;
  vl dp(h + 1, INF);
  dp.at(0) = 0;
  rep(i, n) {
    int a, b;
    cin >> a >> b;
    rep(i, h + 1) {
      int bi = max(0, i - a);
      dp.at(i) = min(dp.at(bi) + b, dp.at(i));
    }
  }
  cout << dp.at(h) << endl;
  return 0;
}


Measured memory_bytes: 384
#define _CRT_SECURE_NO_WARNINGS 1

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <string>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define LL long long
#define pii pair<int,int>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d\n",x)
#define plld(x) printf("%lld\n",x)
#define rep(i,a,b) for(int i = (a) ; i <= (b) ; i++)
#define per(i,a,b) for(int i = (a) ; i >= (b) ; i--)
#define mem(a) memset(a,0,sizeof(a))
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
#define fast_io ios::sync_with_stdio(false)

const LL mod = 1e9 + 7;
const int maxn = 1e7 + 7;
const int INF = 0x3f3f3f3f;
const double pi = acos(-1.0);

LL a[maxn];

int main() {

#ifndef ONLINE_JUDGE
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
	long _begin_time = clock();
#endif

    rep(i,1,maxn-7) {
        for(int j = i ; j <= maxn - 7 ; j += i) {
            a[j]++;
        }
    }
    int n;
    sd(n);
    LL ans = 0;
    rep(i,1,n) {
        ans += i * a[i];
    }
    plld(ans);
  
#ifndef ONLINE_JUDGE
	long _end_time = clock();
	// cout << "time = " <<  _end_time - _begin_time << endl;
#endif
    return 0;
}

Measured memory_bytes: 81872
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
      	Main main = new Main();
		main.solve();
	}

	void solve() {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		long res = 0;
		for(int i=1;i<=n;i++)res += i;
		System.out.println(res);
		sc.close();
	}
}



Measured memory_bytes: 21716
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
typedef long long int ll;
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (int i=0;i<signed(n);i++)
#define EREP(i,n) for (int i=1;i<=(n);i++)
#define ALL(a) (a).begin(),(a).end()
//#define EVEL 1

#ifdef EVEL
#define DEB(X) cout << #X << ":" <<X<<" " ;
#define DESS(X) cout <<X<<" " ;
#define TF(f) f ? cout<<"true  " : cout<<"false ";
#define END cout<<"\n";
#else
#define DEB(X) {}
#define TF(f) {}
#define END {}
#endif
const int MOD = 10007;
const ll INF = 20000000000;
typedef std::pair<int,int> P;


	ll ans=0;
	ll N,M,K,X;
	ll A,B,as,bs;
	// ll L[200010],R[200010];
	ll deff[200010];
	string S,T;
	ll id=0;
	ll sum;bool F=true;
	map<ll,ll> Q,R;
int main(){
	ios_base::sync_with_stdio(false);
	cin>>N>>A>>B;
	if(B-A<=1)ans=N+1;
	else{
		int x=N;
		x-=A-1;
		DEB(x)END
		ans+=A;
		DEB(ans)
		ans+=(B-A)*(x/2);
		DEB(ans)END
		if(x%2==1)ans++;
	}
	cout<<ans<<endl;
}

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

#define MAX 200002
int n;
vector<long long int> v;
map<long long int, int> mp;
int main(){
	cin >> n;
	for (int i = 0; i < n; i++){
		int a;
		scanf("%d", &a);
		v.push_back(a);
	}
	long long int from = v.size();
	long long int ans = 0;
	for (int i = v.size() - 1; i >= 0; i--){
		long long int need = i-v[i];
		if (from == need)continue;;
		if (from < need){
			puts("-1");
			return 0;
		}
		if (need < 0){
			puts("-1");
			return 0;
		}
		ans += v[i];
		from = need;
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 2420
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
#include <cassert>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 1e2 + 10;

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n, k;
	cin >> n >> k;
	LL ans = k;
	while (--n) ans *= k - 1;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import numpy as np
import itertools
n, m, x = [int(k) for k in input().split()]
c = np.zeros(n, dtype=int)
a = np.zeros((n, m), dtype=int)
for i in range(n):
    c[i], *a[i] = [int(k) for k in input().split()]
cost = np.sum(c) + 1
for nn in range(1,n+1):
    for k in itertools.combinations(np.argsort(c),nn):
        k = list(k)
        cs = np.sum(c[k].flatten())
        if cs > cost:
            continue
        rikai = np.sum(a[k],axis=0)
        if np.all(rikai >= x):
            cost = min(cost,cs)
if cost < np.sum(c) + 1:
    print(cost)
else:
    print(-1)

Measured memory_bytes: 27328
using System;
using System.Linq;
using System.Collections.Generic;

namespace c
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var p = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
            var q = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();

            var i = 1;
            var a = 0;
            var b = 0;
            foreach(var l in Enumerate(Enumerable.Range(1, n).ToArray())){
                if(l.SequenceEqual(p)){
                    a = i;
                }
                if(l.SequenceEqual(q)){
                    b = i;
                }
                i += 1;
            }

            Console.WriteLine(Math.Abs(a - b));
        }

        static IEnumerable<T[]> Enumerate<T>(IEnumerable<T> items){
            if (items.Count() == 1){
                yield return new T[]{items.First()};
                yield break;
            }

            foreach (var item in items){
                var leftside = new T[]{item};
                var unused = items.Except(leftside);
                foreach(var rightside in Enumerate(unused)){
                    yield return leftside.Concat(rightside).ToArray();
                }
            }
        }
    }
}


Measured memory_bytes: 21700
#include<bits/stdc++.h>
//#include<inttypes.h>//__int64,__int128..
#define MAX_N 100005
//vector&pair
#define pb push_back
#define mp make_pair
//math
#define sq(x) ((x)*(x))
#define abs(x) ((x)>0?(x):(-(x)))//Regardless of type
//for pair
#define fi first
#define se second
//infinit
#define LL_inf (1LL<<60)
#define full_inf 0x7fffffff
#define half_inf 0x3fffffff
//MOD
#define MOD 1000000007LL*/
using namespace std;
//type
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pil;
typedef long double LD;
char s[10000005];
int main(){
	//write on your code!
	int n,x;
	scanf("%s",s);
	n=strlen(s);
	scanf("%d",&x);
	for(int i=0;i<n;i+=x)	printf("%c",s[i]);
	printf("\n");
	return 0;
}

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

int main() {
  int N, sum=0;
  cin >> N;
  int L[N],R[N];
  
  for(int i=0; i<N; i++) {
    cin >> L[i]>> R[i];
    sum += R[i] - L[i] + 1;
  }
  cout << sum << endl;
}

Measured memory_bytes: 3488
#include <stdio.h>

int main(){
    int i = 0;
    int N, M;
    scanf("%d%d", &N, &M);
    int H[N];
    for (i = 0; i < N;i++){
        scanf("%d", &H[i]);
    }
    int J[M][2];
    for (i = 0; i < M;i++){
        scanf("%d%d", &J[i][0], &J[i][1]);
    }

    char good[N];//good=0,bad=1
    for (i = 0; i < N;i++){
        good[i] = '0';
    }

    int a, b;
    for (i = 0; i < M;i++){
        a = J[i][0]-1;
        b = J[i][1]-1;
        if(H[a]>H[b]){
            good[b] = '1';
        }else if(H[a]<H[b]){
            good[a] = '1';
        }else{
            good[a] = '1';
            good[b] = '1';
        }
    }
    int cnt = 0;
    for (i = 0; i < N;i++){
        if(good[i]=='0'){
            cnt++;
        }
    }
    printf("%d", cnt);
    return 0;
}

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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod= int(1e9)+7;
using P = pair<ll,ll>;
using ld=long double;

int main(){
    int n;cin>>n;
    int k;cin>>k;
    vector<int>x(n);
    for (int i = 0; i < n; ++i) {
        cin >>x[i];
    }
    int ans=0;
    for (int i = 0; i < n; ++i) {
        ans+=min(x[i]*2,abs(k-x[i])*2);
    }
    cout <<ans <<endl;
    return 0;
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int INF = 1001001001;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};

int main() {
string n;
cin >> n;
int ans = 0;
rep(i,n.size()) {
    ans += n.at(i) - '0';
}
if (ans % 9 == 0) cout << "Yes" << endl;
else cout << "No" << endl;
    
return 0;
}


Measured memory_bytes: 3732
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define MP(a, b) make_pair(a, b)
#define Y first
#define X second
#define INF 1 << 30

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

int board[4][4];
int dy[4], dx[4];

int dfs(int n){
  if(n >= 8) return 1;

  int res = 0;
  int y, x;
  rep(y, 4){
    rep(x, 4) if(!board[y][x]) break;
    if(x != 4) break;
  }

  int d;
  rep(d, 4){
    int ny = y+dy[d], nx = x+dx[d];
    if(ny < 0 || nx < 0 || ny >= 4 || nx >= 4 || board[ny][nx] != 0) continue;
    board[y][x] = board[ny][nx] = 1;
    res += dfs(n+1);
    board[y][x] = board[ny][nx] = 0;
  }

  return res;
}

int main(){
  int i;
  while(1){
    rep(i, 4) if(scanf("%d%d", &dx[i], &dy[i])  && dx[0] >= 4) return 0;
    memset(board, 0, sizeof(board));

    printf("%d\n", dfs(0));
  }
  return 0;
}

Measured memory_bytes: 1188
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define w a[i]
typedef long long LL;
inline int gi(){
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
  return x*f;
}
template<typename T>inline bool Max(T &a,T b){return a<b?a=b,1:0;}
template<typename T>inline bool Min(T &a,T b){return a>b?a=b,1:0;}
const int N=2e5 + 7,mod=1e9 + 7;
const LL inv2=500000004ll;
int n;
int a[N],cnt[N],z[N],S[N];
LL tot=1,D[N],t1[N],t2[N],ans;
LL Pow(LL a,LL b){
  LL res=1ll;
  for(;b;b>>=1,a=a*a%mod) if(b&1) res=res*a%mod;
  return res;
}
LL Inv(LL a){return Pow(a,mod-2);}
int lowbit(int x){return x&-x;}
void c1(int x,LL y){for(int i=x;i<=n;i+=lowbit(i)) t1[i]=(t1[i]+y)%mod;}
LL q1(LL x){LL res=0;for(int i=x;i;i-=lowbit(i)) res=(res+t1[i])%mod;return res;}
LL q1(int l,int r){
	if(l>r) return 0;
    return ((q1(r)-q1(l-1))%mod+mod)%mod;
}
void c2(int x,int y){for(int i=x;i<=n;i+=lowbit(i)) t2[i]+=y;}
int q2(int x){int res=0;for(int i=x;i;i-=lowbit(i)) res+=t2[i];return res;}
int q2(int l,int r){
	if(l>r) return 0;
	return q2(r)-q2(l-1);
}
void add(LL &a,LL b){ a+=b;if(a>=mod) a-=mod; }
int main(){
	n=gi();
	rep(i,1,n) ++cnt[w=gi()];
	for(int i=n-1;i;--i) cnt[i]+=cnt[i+1];
	rep(i,1,n) cnt[i]-=n-i;
	rep(i,1,n) tot=tot*cnt[i]%mod;
	if(!tot) return puts("0"),0;
    D[0]=1;
    rep(i,1,n){//D表示每个数字计算结果的前缀积 (和位置无关)
    	LL x=1ll*(cnt[i]-1)*Inv(cnt[i])%mod;
    	z[i]=z[i-1],D[i]=D[i-1];
    	if(!x) S[++z[i]]=i;
    	else D[i]=D[i]*x%mod;
    }
    rep(i,1,n){
    	(ans+=(q1(1,w)-(z[w]==1?0:q1(1,S[z[w]])))*D[w]%mod*inv2%mod*tot%mod)%=mod;
    	c1(w,Inv(D[w]));
    }
    memset(t1,0,sizeof t1);
    rep(i,1,n){
    	ans-=(q1(w+1,n)-(!S[z[w]+1]?0:q1(S[z[w]+1],n)))*Inv(D[w])%mod*inv2%mod*tot%mod;
    	add(ans,tot*q2(w+1,n)%mod);
    	c1(w,D[w]);c2(w,1);
    }
    printf("%lld\n",(ans%mod+mod)%mod);
	return 0;
}

Measured memory_bytes: 8064
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

inline int read()
{
	int x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}

ll fac[maxn],inv[maxn],n,k,p[maxn],a[maxn];
const ll mod=1000000007;

inline ll pw(ll a,ll b)
{
	ll ans=1,base=a;
	while(b)
	{
		if(b&1) ans=(ans*base)%mod;
		base=(base*base)%mod; b>>=1;
	}
	return ans;
}

int main()
{
	fac[0]=1; inv[0]=1;
	rep(i,1,(maxn-5)) fac[i]=(fac[i-1]*i)%mod;
	rep(i,1,(maxn-5)) inv[i]=pw(i,mod-2);
	n=read(); rep(i,1,n) a[i]=read(); inv[0]=fac[n];
	rep(i,1,n) inv[i]=(inv[i]*fac[n])%mod,p[i]=(p[i-1]+inv[i])%mod;
	ll ans=0;
	rep(i,1,n) ans+=(a[i]*(p[i]+p[n-i+1]-p[1]+mod)%mod)%mod,ans%=mod;
	cout<<ans<<endl;
	return 0;
}

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

#define mp make_pair
typedef long long ll;
typedef pair<int,int>pii;
typedef pair<ll,ll>pll;
const int N = 2e5;
ll sum1[N+100],sum2[N+100];
vector<int>v1;
vector<pair<int,pii> >v2;
void update1(int idx,ll value)
{
	while(idx<=N)
	{
		sum1[idx] += value;
		idx += (idx&-idx);
	}
}
void update2(int idx,ll value)
{
	while(idx<=N)
	{
		sum2[idx] += value;
		idx += (idx&-idx);
	}
}
ll query1(int idx)
{
	ll total = 0;
	while(idx>0)
	{
		total += sum1[idx];
		idx -= (idx&-idx);
	}
	return total;
}
ll query2(int idx)
{
	ll total = 0;
	while(idx>0)
	{
		total += sum2[idx];
		idx -= (idx&-idx);
	}
	return total;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int q;
	cin >> q;
	while(q--){
		int f;
		cin >> f;
		if(f==1){
			int a,b;
			cin >> a >> b;
			v1.push_back(a);
			v2.push_back(mp(1,mp(a,b)));
		}
		else{
			v2.push_back(mp(2,mp(-1,-1)));
		}
	}
	sort(v1.begin(),v1.end());
	ll ans = 0;
	ll cnt = 0;
	for(auto it:v2)
	{
		if(it.first == 1){
			cnt++;
			int ind = lower_bound(v1.begin(),v1.end(),it.second.first)-v1.begin();
			update1(ind+1,1);
			update2(ind+1,it.second.first);
			ans += it.second.second;
		}
		else{
			ll lo = 1,hi = N,mid,sl;
			while(lo<=hi)
			{
				mid = (lo+hi)/2;
				if(query1(mid)>=(cnt+1)/2){
					sl = mid;
					hi = mid-1;
				}
				else{
					lo = mid+1;
				}
			}
			ll t1 = v1[sl-1];
			ll t2 = query1(sl-1);
			ll t3 = query2(sl-1);
			ll t4 = query1(N)-query1(sl);
			ll t5 = query2(N)-query2(sl);
			ll tmp = t1*t2-t3+t5-t1*t4;
			cout <<t1 << " " <<  ans+tmp << "\n";
		}
	}
}


Measured memory_bytes: 7472
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	scanInit()

	n := nextInt64()
	if isPrime(n) == true {
		fmt.Println(n - 1)
		return
	}
	_, divlist := getDivlistSlow(n)
	//fmt.Println(divcnt, divlist)

	var minwalk int64 = n
	for _, v := range divlist {
		nowwalk := (v - 1) + (n/v - 1)
		minwalk = min(minwalk, nowwalk)
	}
	fmt.Println(minwalk)
}
func min(a, b int64) int64 {
	if a > b {
		return b
	}
	return a
}

// 約数列挙リストを作成(愚直)
func getDivlistSlow(a int64) (cnt int64, divlist []int64) {
	for i := int64(1); i*i <= a; i++ {
		if a%i == 0 {
			cnt++
			divlist = append(divlist, i)
			if i*i != a { // 6*6=36 などを重複カウントしない
				cnt++
				divlist = append(divlist, a/i)
			}
		}
	}
	return cnt, divlist
}

// 素数判定
func isPrime(a int64) bool {
	for i := int64(2); i*i <= a; i++ {
		if a%i == 0 {
			return false
		}
	}
	return true
}

// ---- readfunc
func scanInit() {
	const cap = 200 * 1024 // Default=64
	var buf = make([]byte, cap)
	sc.Buffer(buf, cap)
	sc.Split(bufio.ScanWords)
	return
}
func nextInt64() int64 {
	sc.Scan()
	i, e := strconv.ParseInt(sc.Text(), 10, 64)
	if e != nil {
		panic(e)
	}
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 2032
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <numeric>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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

const ll MOD = pow(10, 9) + 7;

ll Perm(ll n, ll r){
  if (n < r) return 0;
  ll tmp = 1;
  ll n1 = n;
  REP(i, r){
    tmp *= n1;
    tmp %= MOD;
    n1--;
  }
  return tmp;
}


ll dfs(vector<vector<ll>>& tree, ll target, ll parent, ll K){

  ll cs = tree[target].size() - 1;
  ll ans;
  if (target == 1) {
    cs++;
    ans = Perm(K - 1, cs);
  }
  else ans = Perm(K - 2, cs);
  //cout << ans << endl;

  for(auto child : tree[target]){
    if (child == parent) continue;
    ans *= dfs(tree, child, target, K);
    ans %= MOD;
  }
  return ans;

}

int main() {

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

  ll tmp, tmp1, a, b;
  vector<vector<ll>> tree(N);
  REP(i, N - 1){
    cin >> a >> b;
    a--;
    b--;
    tree[a].push_back(b);
    tree[b].push_back(a);
  }
  ll ans = K * dfs(tree, 0, -1, K);
  ans %= MOD;

  cout << ans << endl;

  //REP(i, N) for(auto j : tree[i]) cout << j;
  return 0;
}


Measured memory_bytes: 11520
# 入力
D, G = map(int, input().split())
p = [0] * D
c = [0] * D

for i in range(D):
    p[i], c[i] = map(int, input().split())

# 再帰的に問題数を求める
def dfs(n, d, g):
    """
    d以下の問題でg点以上取るために必要な最小の問題数を返す

    Parameters
    ----------
    n : int
        dより大きいレベルを解いた数
    d : int
        レベル
    g : int
        点数
    m : int
        dレベルを解く場合の問題数
    q : int
        p問解いた場合に得られる点数

    Returns
    -------
    g点取るための問題数
    """
    # d < 1でgに満たない場合
    if d < 1:
        return float('inf')

    # 解くべき問題数(piまたはg点取るのに必要な最小の問題数)
    m = min(-(-g // (100 * d)), p[d-1])

    # m問解いた時に得られる点数
    q = 100 * m * d + c[d-1] if m == p[d-1] else 100 * m * d

    
    if q >= g:  # g点以上取れる
        return min(n + m, dfs(n, d - 1, g))
    else:       # g点に満たない
        return min(dfs(n + m, d - 1, g - q), dfs(n, d - 1, g))

print(dfs(0, D, G))


Measured memory_bytes: 3064
n=int(input())
a=list(map(int,input().split()))
minus={}
plus={}
res=0
for i in range(0,n):
  pp=a[i]
  if i-pp in minus:
    minus[i-pp]+=1
  else:
    minus[i-pp]=1
  if i+pp in plus:
    plus[i+pp]+=1
  else:
    plus[i+pp]=1
for j in range(len(minus)):
  t=minus.popitem()
  try:
    res+=t[1]*plus[t[0]]
  except KeyError:
    pass
print(res)

Measured memory_bytes: 57272
fun main(args: Array<String>){
    var (a, b, c, k) = readLine()!!.split(" ").map { it.toLong() }

    val zero: Long = 0
    val ans = a - b

    if (k % 2 == zero){
        if (ans > 1000000000000000000 || ans < -1000000000000000000){
            println("Unfair")
        }else{
            println(ans)
        }
    }else{
        if (ans > 1000000000000000000 || ans < -1000000000000000000){
            println("Unfair")
        }else{
            println(ans * -1)
        }
    }
}


Measured memory_bytes: 36056
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.lang.StringBuilder
import java.util.*

fun PrintWriter.solve(sc: FastScanner) {
    val s = sc.nextInt()
    val w = sc.nextInt()
    println(if (w >= s) "unsafe" else "safe")
}

fun main(args: Array<String>) {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}

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

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

  string S, T, U;
  int A, B;
  cin >> S >> T >> A >> B >> U;

  if (S == U) {
    A--;
  } else {
    B--;
  }

  cout << A << " " << B << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
	while (true) {
		int n;
		cin >> n;
		if (n == 0) {
			break;
		}
		int max = -1, min = 1001;
		int sum = 0;
		for (int i = 0; i < n; i++) {
			int m;
			cin >> m;
			sum += m;
			if (max < m) {
				max = m;
			}
			if (m < min) {
				min = m;
			}
		}
		sum -= (max + min);
		sum /= n - 2;
		cout << sum << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
import itertools

n = int(input())
a = list(map(int,input().split()))
q = int(input())
m = list(map(int,input().split()))

data = []
for i in itertools.product(range(2),repeat=n):
    data.append(sum([i[j]*a[j] for j in range(n)]))
    
for i in m:
    if i in data:
        print("yes")
    else:
        print("no")


Measured memory_bytes: 43112
import itertools
l,r = map(int,input().split(" "))

if r-l > 2019:
    print(0)
else:
    ret = 2020
    for i in itertools.combinations(range(l,r+1,1),2):
        ret = min(ret,(i[0]*i[1])%2019)
    print(ret)


Measured memory_bytes: 3060
for i in range(1, 3005):
    x = input().split(" ")
    a = int(x[0])
    b = int(x[1])
    if a + b == 0:
        break
    if a < b:
        print(str(a) + " " + str(b))
    else:
        print(str(b) + " " + str(a))



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

int main() {
	int n,p;
	cin>>n>>p;
	if(n>=13){
		cout<<p<<endl;
	}else if(n>=6){
		cout<<p/2<<endl;
	}else{
		cout<<0<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N), B(N), C(N);
    for (size_t i = 0; i < N; i++)
    {
        cin >> A[i];
    }
    for (size_t i = 0; i < N; i++)
    {
        cin >> B[i];
    }
    for (size_t i = 0; i < N; i++)
    {
        cin >> C[i];
    }
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());

    long ans = 0;
    for (int i = 0; i < N; i++)
    {
        auto Iter1 = lower_bound(A.begin(), A.end(), B[i]);
        auto Iter2 = upper_bound(C.begin(), C.end(), B[i]);
        long k1 = Iter1 - A.begin();
        long k2 = C.end() - Iter2;
        ans += k1 * k2;
    }

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

Measured memory_bytes: 1536
#include "bits/stdc++.h"
using namespace std;

//#define int long long
#define DBG 0
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) c.begin(),c.end()
static const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
static const int MOD = (int)(1e9 + 7);

signed main() {
	for (int n, x; cin >> n >> x&&n;) {
		int cnt = 0;
		rep(i, 1, n)rep(j, i + 1, n) {
			int k = x - (i + j);
			if (k > j&&k <= n)cnt++;
		}
		cout << cnt << endl;

	}
	return 0;
}

Measured memory_bytes: 3100
#include<iostream>
#include<vector>
#include<string>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(var,init,end) for(int var=init;var<end;var++)
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
int facctorialMethod(int k) {
	int sum = 1;
	for (int i = 1; i <= k; ++i)
	{
		sum *= i;
	}
	return sum;
}

int main() {
	long long n;
    cin >> n;
    if(n%2==0){
      cout<<n;
    }else{
      cout<<n*2;
    }

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
  string s;
  cin >> s;
  int a = 0;
  if(s[0] == 'a'){
    if(s[1] == 'b' and s[2] == 'c') a = 1;
    if(s[1] == 'c' and s[2] == 'b') a = 1;
  }
  
  if(s[0] == 'b'){
    if(s[1] == 'a' and s[2] == 'c') a = 1;
    if(s[1] == 'c' and s[2] == 'a') a = 1;
  }
  
  if(s[0] == 'c'){
    if(s[1] == 'a' and s[2] == 'b') a = 1;
    if(s[1] == 'b' and s[2] == 'a') a = 1;
  }
  
  if( a == 0) cout << "No" << endl;
  if( a == 1) cout << "Yes" << endl;
}

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

namespace Aizu
{
    class OnlineJudge
    {
        public static void Main()
        {
            int gems;
            var table = new Dictionary<string, int[]>() {
                { "N", new[] { 1,  1 } },
                { "E", new[] { 0,  1 } },
                { "S", new[] { 1, -1 } },
                { "W", new[] { 0, -1 } }
            };
            while((gems = int.Parse(Console.ReadLine())) != 0){
                var now = new []{10, 10};
                var map = new bool[21, 21];
                for(int i = 0; i < gems; ++i){
                    var point = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
                    map[point[0], point[1]] = true;
                }
                int count = 0;
                for(int i = int.Parse(Console.ReadLine()); i > 0; --i){
                    var input = Console.ReadLine().Split(' ');
                    for(int j = int.Parse(input[1]); j > 0; --j) {
                        now[table[input[0]][0]] += table[input[0]][1];
                        if(map[now[0], now[1]]) {
                            ++count;
                            map[now[0], now[1]] =false;
                        }
                    }
                }
                Console.WriteLine(count == gems ? "Yes" : "No");
            }
        }
    }
}

Measured memory_bytes: 5944
#include <cmath>
#include <cstdio>
int n, y, b, r, t;
int main() {
	while(~scanf("%d", &n)) {
		if(!n) break;
		int p = 0; double d = 0, e;
		scanf("%d", &y);
		for(int i = 0; i < n; i++) {
			scanf("%d%d%d", &b, &r, &t);
			if(t == 1) e = 1 + y * r * 0.01;
			else e = pow(1 + r * 0.01, y);
			if(d < e) d = e, p = b;
		}
		printf("%d\n", p);
	}
	return 0;
}

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

typedef long long ll;

int main()
{
    ll N,K;
    cin>>N>>K;
    ll ans = 0;
    if(K==0)
        ans = N*N;
    else{
    for(ll i=K+1; i<=N; i++){
        if(N%i >=K){
            ans+= N%i-K+1+ (i-K)*(N-(N%i))/i;
        }
        else{
            ans+= (i-K)*(N-(N%i))/i;
        }
    }
    }
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
 using namespace std;
 int main() 
{
 int r , d , x2000,x ;
 cin>> r >> d >> x2000;
 for(int i=0; i<10; i++){
 x=(r*x2000)-d;
 cout<<x<<endl;
 x2000=x;
 }
 }

Measured memory_bytes: 256
import sys
import math
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())
def NIJIGEN(H): return [list(input()) for i in range(H)]
D,T,S=MAP()
if T*S>=D:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 9184
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
mt19937_64 rnd(228);
const int mod = 998244353;

int mult(int a, int b) {
    return (1LL * a * b) % mod;
}

int pw(int a, int b) {
    if (b == 0) return 1;
    if (b & 1) return mult(a, pw(a, b - 1));
    int res = pw(a, b / 2);
    return mult(res, res);
}

int sub(int a, int b) {
    int s = a - b;
    if (s < 0) s += mod;
    return s;
}

int sum(int a, int b) {
    int s = a + b;
    if (s >= mod) s -= mod;
    return s;
}
struct Fenwick {
    vector<int> f;
    int n;

    Fenwick(int _n) {
        n = _n;
        f.resize(_n + 1);
    }

    void upd(int pos, int v) {
        while (pos <= n) {
            f[pos] = sum(f[pos], v);
            pos = (pos | (pos - 1)) + 1;
        }
    }

    int get(int r) {
        int ans = 0;
        while (r > 0) {
            ans = sum(ans, f[r]);
            r &= (r - 1);
        }
        return ans;
    }

    int get(int l, int r) {
        return sub(get(r), get(l - 1));
    }
};

const int maxN = 2e5 + 10;
int n, k;
int invK[maxN];
int pwK[maxN];
int p[maxN];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("input.txt", "r", stdin);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    int nk = mult(k, pw(k - 1, mod - 2));
    for (int i = 0; i <= n; i++) {
        invK[i] = pw(pw(nk, i), mod - 2);
        pwK[i] = pw(nk, i);
    }
    int ans = mult((k - 1), mult(k - 2, pw(4, mod - 2)));
    Fenwick f_sum(n);
    Fenwick cnt(n);
    for (int i = 1; i <= k - 1; i++) {
        f_sum.upd(p[i], pwK[k]);
        cnt.upd(p[i], +1);
    }
    for (int i = k; i <= n; i++) {
        int cnt_smaller = f_sum.get(p[i] - 1);
        ans = sum(ans, mult((mod + 1) / 2, mult(cnt_smaller, invK[i])));
        int cnt_bigger = f_sum.get(p[i] + 1, n);
        int tot_bigger = cnt.get(p[i] + 1, n);
        ans = sum(ans, sub(tot_bigger, mult(invK[i], mult((mod + 1) / 2, cnt_bigger))));
        f_sum.upd(p[i], pwK[i]);
        cnt.upd(p[i], +1);
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 7144
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author MaxHeap
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskB solver = new TaskB();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskB {
        public void solve(int testNumber, FastReader in, PrintWriter out) {
            int n = in.nextInt();
            int ans = 1;
            int ansCount = 0;
            for (int i = 1; i <= n; i++) {
                int count = getTwoCount(i);
                if (count > ansCount) {
                    ans = i;
                    ansCount = count;
                }
            }
            out.println(ans);
        }

        private int getTwoCount(int n) {
            int ret = 0;
            while (n % 2 == 0) {
                ++ret;
                n /= 2;
            }
            return ret;
        }

    }

    static class FastReader {
        BufferedReader reader;
        StringTokenizer st;

        public FastReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            st = null;
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String line = reader.readLine();
                    if (line == null) {
                        return null;
                    }
                    st = new StringTokenizer(line);
                } catch (Exception e) {
                    throw new RuntimeException();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 21460
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
ll sieve[1000001]={0},i,j;
ll m=1e9+7;
ll power(ll p, ll k)
{
ll a=1;
while(k)
{
if(k&1)
a=(a*p);
p=(p*p);
k>>=1;
}
return a;
}
using namespace std;
  ll countDivisors(ll n) 
{ 
    ll cnt = 0; 
    for (ll i = 1; i <= sqrt(n); i++) { 
        if (n % i == 0) { 
            if (n / i == i) 
                cnt++; 
  
            else 
                cnt = cnt + 2; 
        } 
    } 
    return cnt; 
} 
void add_self(int &a ,int b)
{
	a+=b;
	if(a>=m)
	a-=m;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 int tc=1;
//cin>>tc;
ll cas=1;
 while(tc--)
 {
	string s;
	cin>>s;
	ll d;
	cin>>d;
	ll len=s.length();
	 vector<vector<int>> dp(d,vector<int>(2));
	dp[0][0]=1;
	for(ll where=0;where<len;where++)
	{
		vector<vector<int>> new_dp(d,vector<int>(2));
		for(ll sum=0;sum<d;sum++)
		{
			for(int sm_already :{0,1})
			{
				for(ll digit=0;digit<10;digit++)
				{
					if(digit>s[where]-'0' && sm_already==0)
					break;
					add_self(new_dp[(sum+digit)%d][sm_already || digit<s[where]-'0'],dp[sum][sm_already]);
				}
			}
		}
		dp=new_dp;
	}
	ll answer=(dp[0][0]+dp[0][1]-1+m)%m;
	cout<<answer;
	cout<<"\n"; 
 } 
}
 


Measured memory_bytes: 384
import collections
N = int(input())
A = list(map(int,input().split()))
B = []
C = []
for i in range(N):
    B.append(-A[i]+i+1)
    C.append(A[i]+i+1)

bol = collections.Counter(B)
col = collections.Counter(C)

#print(col)
count = 0
for i,j in list(bol.items()):
    if col[i]:
        count += j*col[i]

print(count)

Measured memory_bytes: 143684
#include<stdio.h>

int main(){
    int S,h=0,m=0,s=0;
    scanf("%d",&S);
    h=S/3600;
    S%=3600;
    m=S/60;
    S%=60;
    s=S;
    printf("%d:%d:%d\n",h,m,s);

    return 0;
}


Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
#define REP(i, init, n) for(int i = (int)(init); i < (int)(n); i++)

#define vi vector<int>
#define vl vector<long>
#define vvi vector<vector<int>>
#define vvl vector<vector<long>>
#define pint pair<int, int>
#define plong pair<long, long>

int main() {
    int N, M, S, T;
    cin>>N>>M;
    vvi G(N);
    REP(i, 0, M){
        int u, v;
        cin >> u >> v;
        u--; v--;
        G[u].emplace_back(v);
    }
    cin >> S >> T;
    S--; T--;

    vvi dist(N, vi(3, -1));
    dist[S][0] = 0;
    queue<pint> que;
    que.push({S, 0});
    while(!que.empty()){
        auto cur = que.front(); que.pop();
        int v = cur.first;
        int parity = cur.second;
        for(int x: G[v]){
            int np = (parity+1) % 3;
            if(dist[x][np] == -1){
                dist[x][np] = dist[v][parity] + 1;
                que.push({x, np});
            }
        }
    }
    int ans = 0;
    if(dist[T][0] == -1) ans = -1;
    else ans = dist[T][0]/3;
    cout << ans << endl;
}

Measured memory_bytes: 11136
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
#include <iomanip>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#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++)
template<class T> T RoundOff(T a){ return int(a+.5-(a<0)); }
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }

int main()
{
	int n;
	while(cin >> n && n)
	{
		vint a(26, 0);
		vector<vint> G(26, vint(26));

		rep(i, n)
		{
			string word;
			cin >> word;

			a[word[0] - 'a']++;
			a[word[word.size() - 1] - 'a']++;
			G[word[0] - 'a'][word[word.size() - 1] - 'a']++;
		}


		// AOtÅ é©Ç¤©
		int s;
		vint used = a;
		queue<int> que;
		rep(i, 26)
			s = a[i] ? i : s;
		used[s] = 0;
		for(que.push(s); !que.empty(); que.pop())
		{
			int p = que.front();

			rep(i, 26)
			{
				if(G[p][i] && used[i])
				{
					used[i] = 0;
					que.push(i);
				}
			}
		}

		if(0 < accumulate(ALL(used), 0))
		{
			cout << "NG" << endl;
			goto ng;
		}


		// êMÅ«é©Ç¤©
		rep(i, 26)
		{
			if(a[i] % 2 == 1)
			{
				cout << "NG" << endl;
				goto ng;
			}
		}

		cout << "OK" << endl;
ng:
		;
	}
}

Measured memory_bytes: 920
#include <stdio.h>
 
int main (void) {
	long long int a = 0, b = 0, c = 0, tmp = 0, r = 0;
    while ( scanf("%d %d",&a,&b) != EOF ) {
		r = a*b;
		if ( b > a ) {
        tmp = b;
        b = a;
        a = tmp;
		}
		while ( b > 0 ) {
        c = b;
        b = a % b;
        a = c;
		}     
        printf("%d %d\n",a,(r / a));
    }
    return 0;
}

Measured memory_bytes: 592
#include <cstdio>
int gcd(int a,int b) {
	return b?gcd(b,a%b):a;
}
int lcm(int a,int b,int g) {
	return a/g*b;
}
int main() {
	int a,b,g;
	while(scanf("%d %d",&a,&b)!=EOF) {
		g=gcd(a,b);
		printf("%d %d\n",g,lcm(a,b,g));
	}
}

Measured memory_bytes: 1020
#include <iostream>
#include <string>
using namespace std;
int main(void){
    // Your code here!
    long long int N,H,W,i,j,k,ans,count;
    string S;
    bool flag;
    count=0;
    ans=0;
    flag=false;
    cin >> H>>W;

    if (H==1 || W==1){
        ans=1;
    }

    else if (H%2==1 && W%2 ==1){
        ans=H*W/2+1;
    }
    else{
        ans=H*W/2;
    }
    
    cout << ans<<endl;

    return 0;
    
}


Measured memory_bytes: 3600
#include <cstdio>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int main()
{
	map<int,int> m;
	vector<int> v;
	int n,a,res=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&a);
		if(!m.count(a)){
			v.push_back(a);
			m[a]=0;
		}
		m[a]++;
	}
	for(int i=0;i<v.size();i++){
		if(m[v[i]]>=v[i]) res+=m[v[i]]-v[i];
		else res+=m[v[i]];
	}
	printf("%d\n",res);
}

Measured memory_bytes: 5112
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
  ll n;
  cin >> n;
  ll v[n],c[n];
  for(ll i=0;i<n;i++) cin >>v[i];
  for(ll i=0;i<n;i++) cin >>c[i];
  for(ll i=0;i<n;i++) v[i]-=c[i];
  ll ans=0;
  for(ll i=0;i<n;i++){
   if(v[i]>0) ans+=v[i];
  }
  cout <<ans<<endl;
}


Measured memory_bytes: 256
n, l = gets.split().map(&:to_i)
apples = []

(1..n).each do |i|
  apples << l+i-1
end

rm = 1000000

apples.each do |i|
  if rm.abs > i.abs
    rm = i
  end
end

puts apples.inject(&:+) - rm

Measured memory_bytes: 1788