akhauriyash/Code-Regression huggingface dataset:
//==========================Head files==========================
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<iostream>
#include<map>
#define LL long long
#define db double
#define mp make_pair
#define pr pair<int, int>
#define fir first
#define sec second
#define pb push_back
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
//==========================Templates==========================
inline int read() {
    int x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
    return x * f;
}
inline LL readl() {
    LL x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
    return x * f;
}
int power(int a, int b) {
	int ans = 1;
	while (b) {
		if(b & 1) ans = ans * a;
		b >>= 1; a = a * a;
	}
	return ans;
}
int power_mod(int a, int b, int mod) {
	a %= mod;
	int ans = 1;
	while (b) {
		if(b & 1) ans = (ans * a) % mod;
		b >>= 1, a = (a * a) % mod;
	}
	return ans;
}
LL powerl(LL a, LL b) {
	LL ans = 1ll;
	while (b) {
		if(b & 1ll) ans = ans * a;
		b >>= 1ll;a = a * a;
	}
	return ans;
}
LL power_modl(LL a, LL b, LL mod) {
	a %= mod;
	LL ans = 1ll;
	while (b) {
		if(b & 1ll) ans = (ans * a) % mod;
		b >>= 1ll, a = (a * a) % mod;
	}
	return ans;
}
LL gcdl(LL a, LL b) {return b == 0 ? a : gcdl(b, a % b);}
LL abssl(LL a) {return a > 0 ? a : -a;}
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
int abss(int a) {return a > 0 ? a : -a;}
//==========================Main body==========================
#define LD "%I64d"
#define D "%d"
#define pt printf
#define sn scanf
#define pty printf("YES\n")
#define ptn printf("NO\n")
//==========================Code here==========================
int n, RL[100000 + 5], LR[100000 + 5], ans[100000 + 5];
char s[100000 + 5];
int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	for (int i = n; i; --i) {
		if (i < n) {
			if (s[i] == 'R' && s[i + 1] == 'L') RL[i] = i; else RL[i] = RL[i + 1];
		}
	}
	for (int i = 1; i <= n; ++i) {
		if (i > 1) {
			if (s[i - 1] == 'R' && s[i] == 'L') LR[i] = i; else LR[i] = LR[i - 1];
		}
	}
	for (int i = 1; i <= n; ++i) if (s[i] == 'L') {
		int dis = abssl(i - LR[i]);
		if (dis & 1) ans[LR[i] - 1]++; else ans[LR[i]]++;
	} else if (s[i] == 'R') {
		int dis = abssl(i - RL[i]);
		if (dis & 1) ans[RL[i] + 1]++; else ans[RL[i]]++;
	}
	for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
	return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

int n;
ll a[200001];
ll dp[2][100011][2];
int main(){
    cin>>n;
    rep(i,n) cin>>a[i];
    int l,r,cur=0;
    rep(i,2)rep(j,100011)rep(k,2) dp[i][j][k]=-1000100010001000100;
    dp[0][0][0]=0,dp[0][0][1]=0;
    rep(i,n){
        cur=i%2;
        r=(i+1)/2,l=max(0,i/2-1);
        FOR(j,l,r+1){
            dp[cur^1][j][0]=max(dp[cur^1][j][0],dp[cur][j][1]);
            dp[cur^1][j][0]=max(dp[cur^1][j][0],dp[cur][j][0]);
            dp[cur^1][j+1][1]=max(dp[cur^1][j+1][1],dp[cur][j][0]+a[i]);
        }
    }
    cout<<max(dp[n%2][n/2][0],dp[n%2][n/2][1])<<endl;
    return 0;
}

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

#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

int main()
{
    lli a;
    string s;
    cin >> a;
    cin >> s;

    if(a>=3200) cout << s;
    else cout << "red" << endl;
    return 0;
}

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

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

	vector<int> vec;
	rep(i, n) {
		int x;
		cin >> x;
		vec.push_back(x);
	}

	int ans = 1e9;
	for (int i = 1; i <= 100; i++) {
		int sum = 0;
		for (int x : vec) {
			sum += pow(x - i, 2);
		}
		ans = min(ans, sum);
	}

	cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for(ll i = a; i < b; i++)
typedef pair<ll,ll> P;

const ll MAX_N = 305;
const ll INF = 1e11;
vector<P> query;

ll dist[MAX_N][MAX_N], dd[MAX_N][MAX_N];
ll cnt[MAX_N], res[MAX_N];
bool used[MAX_N];
ll N, L, Q;
ll ans[MAX_N];

int main(){
    ll M; cin >> N >> M >> L;
    rep(i, 0, N) rep(j, 0, N) dist[i][j] = INF;
    rep(i, 0, N) dist[i][i] = 0;
    rep(i, 0, M){
        ll a, b, c; cin >> a >> b >> c;
        if(c > L) continue;
        a--, b--;
        dist[a][b] = c;
        dist[b][a] = c;
    }
    cin >> Q;
    query.resize(Q);
    rep(i, 0, Q) cin >> query[i].first >> query[i].second, query[i].first--, query[i].second--;

    rep(k, 0, N)rep(i, 0, N) rep(j, 0, N) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    rep(i, 0, N) rep(j, 0, N){
        if(dist[i][j] <= L) dd[i][j] = 1;
        else dd[i][j] = INF;
    }

    rep(k, 0, N) rep(i, 0, N) rep(j, 0, N) dd[i][j] = min(dd[i][j], dd[i][k] + dd[k][j]);

    rep(i, 0, Q){
        int s = query[i].first;
        int t = query[i].second;
        if(dd[s][t] >= INF) cout << -1 << endl;
        else cout << dd[s][t] - 1 << endl;
    }
}

Measured memory_bytes: 3328
import java.util.Scanner;

public class Main{

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

        int A = sc.nextInt();
        int B = sc.nextInt();

        if(B == 1)
            System.out.println(0);
        else if(B <= A)
            System.out.println(1);
        else {
            int i = 2;
            while (true) {
                if((A - 1) * i + 1 >= B) {
                    System.out.println(i);
                    break;
                }
                ++i;
            }
        }
    }

}


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

long long int a;
long long int p = 1;
string res = "";

int main()
{
    cin >> a;
    
    long long int sum=0;
    long long int a1=a;
    int size=0;
    for(int i=0;;i++){
        p*=26;
        sum+=p;
        if(a<=sum){
            sum-=p;
            size=i;
            break;
        }
    }

    a1=a-sum-1;
    for(int i=0;i<=size;i++){
        int r=a1%26;
        res = (char)(r+ 'a') + res;
        a1/=26;
    }
    cout<<res<<endl;
    return 0;

    a-=sum;
    cout<<a<<endl;
    for (int i=0;i<=size;i++)
    {
        res = (char)((a) % 26 + 'a') + res;
        a /= 26;
    }
    cout<<res;
    return 0;
    cout<<a<<endl;
    res = (char)(a % 26 + 'a') + res;
    if (a <= 0)
    {
        goto output;
    }
    for (;;)
    {
        a /= 26;
        cout<<a<<endl;
        res = (char)((a-1) % 26 + 'a') + res;
        if (a <= 0)
        {
            break;
        }
    }
    output:
    cout << res << endl;
}

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

int main(){
    using namespace std;
    constexpr unsigned long MOD = 1000000007;
    const auto& modinv = [](unsigned long a, unsigned long b = 1) -> unsigned long{
        unsigned long r{b % MOD}, n{MOD - 2};
        while(n){
            if(n & 1)(r *= a) %= MOD;
            (a *= a) %= MOD;
            n >>= 1;
        }
        return r;
    };
    unsigned long N;
    cin >> N;
    vector<unsigned long> fac(N + 1, 1), invfac(N + 1, 1);
    for(unsigned long i{1}; i <= N; ++i)fac[i] = fac[i - 1] * i % MOD;
    invfac.back() = modinv(fac.back());
    for(unsigned long i{N}; i--; )invfac[i] = invfac[i + 1] * (i + 1) % MOD;
    vector<vector<unsigned long>> edge(N);
    vector<unsigned long> jisu(N);
    for(unsigned long i{1}, a, b; i < N; ++i){
        cin >> a >> b;
        edge[--a].push_back(--b);
        edge[b].push_back(a);
        ++jisu[a];
        ++jisu[b];
    }
    vector<unsigned long> ord(N);
    iota(ord.begin(), ord.end(), 0UL);
    sort(ord.begin(), ord.end(), [&jisu](auto i, auto j){return jisu[i] > jisu[j];});
    map<pair<unsigned long, unsigned long>, pair<unsigned long, unsigned long>> memo;
    const auto& tree_dp = [&modinv, &fac, &invfac, &edge, &memo](auto f, unsigned long now, unsigned long prev) -> pair<unsigned long, unsigned long> {
        if(memo.count({now, prev}))return memo[{now, prev}];
        if(memo.count({now, now})){
            auto t = memo[{now, now}], s = memo[{prev, now}];
            unsigned long cnt{t.first}, ans{t.second};
            (ans *= modinv(s.second, invfac[cnt - 1] * fac[cnt - s.first - 1] % MOD * fac[s.first])) %= MOD;
            cnt -= s.first;
            return memo[{now, prev}] = {cnt, ans};
        }
        unsigned long cnt{0}, ans{1};
        for(const auto& i : edge[now])if(i != prev){
            auto t = f(f, i, now);
            cnt += t.first;
            (ans *= invfac[t.first] * t.second % MOD) %= MOD;
        }
        (ans *= fac[cnt]) %= MOD;
        return memo[{now, prev}] = {cnt + 1, ans};
    };
    vector<unsigned long> ans(N);
    for(const auto& i : ord)ans[i] = tree_dp(tree_dp, i, i).second;
    copy(ans.begin(), ans.end(), ostream_iterator<unsigned long>(cout, "\n"));
    return 0;
}

Measured memory_bytes: 69488
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		int N = sc.nextInt();

		int cx = 0;
		int cy = 0;
		int ct = 0;

		String ans = "Yes";

		for (int i = 0; i < N; i++) {
			int t = sc.nextInt();
			int x = sc.nextInt();
			int y = sc.nextInt();

			int d = Math.abs(cx - x) + Math.abs(cy - y);

			if (t < d + ct) {
				ans = "No";
				break;
			}

			if ((t - ct) % 2 != d % 2) {
				ans = "No";
				break;
			}

			cx = x;
			cy = y;
			ct = t;
		}

		out.println(ans);

		sc.close();

	}

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

	@SuppressWarnings("unused")
	private int[] nextIntArray(Scanner sc, int n) {
		int[] result = new int[n];
		for (int i = 0; i < n; i++) {
			result[i] = sc.nextInt();
		}
		return result;
	}

	@SuppressWarnings("unused")
	private int[] nextIntArray1origin(Scanner sc, int n) {
		int[] result = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			result[i] = sc.nextInt();
		}
		return result;
	}
}


Measured memory_bytes: 87084
import sys

read = sys.stdin.buffer.read


def main():
    N, T, *AB = map(int, read().split())
    D = [(a, b) for a, b in zip(*[iter(AB)] * 2)]

    D.sort()

    dp = [0] * T
    max_sum = [0] * N
    for i, (a, b) in enumerate(D):
        for t in range(T - 1, -1, -1):
            if t >= a and dp[t] < dp[t - a] + b:
                dp[t] = dp[t - a] + b
        max_sum[i] = dp[T - 1]

    ans = 0
    for i in range(N - 1):
        if ans < max_sum[i] + D[i + 1][1]:
            ans = max_sum[i] + D[i + 1][1]

    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 74120
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <limits.h>	
#define inf (INT_MAX-1)
#define INF 9223372036854775807
#define sq(n) ((n)*(n))
#define rep(i,n) for(i=0;i<n;i++)
#define rev(i,n) for(i=n-1;i>=0;i--)
#define sort(a,n) qsort(a,n,sizeof(TYPE),cmp)
#define sort_r(a,n) qsort(a,n,sizeof(TYPE),char_cmp_r);
#define chsort(s) qsort(s,strlen(s),sizeof(char),cmp)
#define chsort_r(s) qsort(s,strlen(s),sizeof(char),char_cmp_r);
#define TYPE char
#define MEMSET(a) memset(a,0,sizeof(a))
const int mod=(int)1e09+7;

int in(void){
	int i;scanf("%d",&i);
	return i;
}
long long llin(void){
	long long i;scanf("%lld",&i);
	return i;
}
double din(void){
	double i;scanf("%lf",&i);
	return i;
}
void chin(char s[]){
	scanf("%s",s);
}
void print(int a){
	printf("%d\n",a);
}
void llprint(long long a){
	printf("%lld\n",a);
}
void dprint(double a){
	printf("%.10f\n",a);
}
void print2(int a,int b){
	printf("%d %d\n",a,b);
}
long long max(long long a,long long b){
	return a>b?a:b;
}
long long min(long long a,long long b){
	return a<b?a:b;
}
long long llabs(long long a){
	return a>0?a:-a;
}
double dmax(double a,double b){
	return a>b?a:b;
}
int cmp(const void *a,const void *b){
	return *(TYPE *)a-*(TYPE *)b;
}
int cmp_r(const void *a,const void *b){
	return *(TYPE *)b-*(TYPE *)a;
}
int char_cmp(const void *a,const void *b){
	return strcmp((char *)a,(char *)b);
}
int char_cmp_r(const void *a,const void *b){
	return strcmp((char *)b,(char *)a);
}
void swap(int *a,int *b){
	int t=*a;
	*a=*b;
	*b=t;
}

int main(void){
	int n=in(),i,a,t,c,min=inf;
	rep(i,n){
		a=in();
		t=a;
		c=0;
		while(!(t%2)){
			t/=2;
			c++;
		}
		if(c<min)min=c;
	}
	print(min);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 10000000000000000




int main(){
	
	int N;
	cin>>N;
	
	vector<pair<int,int>> P(N);
	for(int i=0;i<N;i++){
		cin>>P[i].first;
		P[i].second = i+1;
	}
	
	sort(P.begin(),P.end());
	
	for(int i=0;i<N;i++){
		if(i!=0)cout<<' ';
		cout<<P[i].second;
	}
	cout<<endl;
		
	
	return 0;
}



Measured memory_bytes: 1664
'''
Created on 2020/08/22

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  N=int(pin())
  A=list(map(int,pin().split()))
  now=0
  ans=0
  for i in A:
    if now>i:
      ans+=now-i 
    else:
      now=i
  print(ans)
  return 
main()

Measured memory_bytes: 31476
import sys

def solve(N: int, K: int, h: "List[int]"):
    cumsums = [float("inf")]*N
    cumsums[0]=0
    cumsums[1]=abs(h[1]-h[0])

    for i in range(1, N):
        for j in range(1, K+1):
            if i >= j:
                cumsums[i] = min(cumsums[i], cumsums[i-j]+abs(h[i]-h[i-j]))
        #print(cumsums)
    return cumsums[-1]

N, K = map(int, sys.stdin.readline().rstrip().split())
h = list(map(int, sys.stdin.readline().rstrip().split()))
print(solve(N, K, h))

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

int main()
{
	int n, l;
	string str, str2;

	cin >> n ;
	cin >> str;
	cin >> l;
	str2 = str[l - 1];

	rep(i, n) {
		if (str[i] != str2[0]){
			str[i] = '*';
		}
	}

	cout << str;


	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args)  {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), m = sc.nextInt();
		String a[] = new String[n];
		for(int i=0;i<n;i++) {
			a[i] = sc.next();
		}
		String b[] = new String[m];
		for(int i=0;i<m;i++) {
			b[i] = sc.next();
		}
		sc.close();
		
		for(int i=0;i<n;i++) {
			if(i+m-1>=n) break;
			int idx = -1;
			int now = 0;
			while(now<n) {
				idx = a[i].indexOf(b[0],now);
				if(idx == -1)break;
				now = idx+1;
				boolean ok = true;
				for(int j=1;j<m;j++) {
					if(!b[j].equals(a[i+j].substring(idx,idx+m))) {
						ok = false;
						break;
					}
				}
				if(ok) {
					System.out.println("Yes");
					return;
				}
			}
		}
		System.out.println("No");
	}
}


Measured memory_bytes: 23252
#include <bits/stdc++.h>
using namespace std;
template<typename T>
T gcd (T a, T b) {
  if (a < 0) a = -a;
  if (b < 0) b = -b;
  if (a < b) swap(a, b);
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
int main() {
  cin.tie(0); cin.sync_with_stdio(false);
  long long A, B, C, D;
  cin >> A >> B >> C >> D;
  auto cal = [&] (long long r, long long mod) {
    return r / mod + 1;
  };
  auto range_cal = [&] (long long l, long long r, long long mod) {
    long long ret = cal(r, mod);
    if (l > 0) ret -= cal(l - 1, mod);
    return ret;
  };
  long long ret = B - A + 1;
  ret -= range_cal(A, B, C);
  ret -= range_cal(A, B, D);
  ret += range_cal(A, B, C * D / gcd(C, D));
  cout << ret << endl;
  return 0;
}

Measured memory_bytes: 256
n=int(input())
list=[[0]*n]
list=input().split()
g=0
c=0
for i in range(n):
  list[i]=int(list[i])
  if list[i]%2==0:
    g+=1
    if list[i]%3==0 or list[i]%5==0:
      c+=1
if g==c:
  print("APPROVED")
else:
  print("DENIED")
  


Measured memory_bytes: 9056
a, b, c, x, y = gets.chomp.split(" ").map(&:to_i)
if a + b > c * 2
  min, max = [x, y].minmax

  if x > y
    r = a * (max - min)
  elsif x < y
    r = b * (max - min)
  else
    r = (a + b) * (max - min)
  end

  if c * 2 * max < r + (c * (min * 2))
    puts c * 2 * max
  else
    puts r + (c * (min * 2))
  end
else
  puts (a * x) + (b * y)
end


Measured memory_bytes: 1788
import java.util.Scanner;

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

        int count_5 = 0;
        int count_7 = 0;

        for (int i = 0; i < 3; i++) {
            int num = sc.nextInt();
            if (5 == num) {
                count_5++;
            } else if (7 == num) {
                count_7++;
            }
        }

        if (count_5 == 2 && count_7 == 1) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

Measured memory_bytes: 21716
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()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn read_col<T: std::str::FromStr>(n: usize) -> Vec<T> {
    (0..n).map(|_| read()).collect()
}

use std::collections::BTreeSet;

fn main() {
    let nq: Vec<usize> = read_vec();
    let n = nq[0];
    let q = nq[1];
    let s: String = read();
    let cv: Vec<char> = s.chars().collect();
    let mut cnt: Vec<u32> = vec![0; 100000];
    let lr: Vec<Vec<usize>> = read_vec2(q);

    for i in 1..n {
        if cv[i - 1] == 'A' && cv[i] == 'C' {
            cnt[i] = cnt[i - 1] + 1;
        } else {
            cnt[i] = cnt[i - 1];
        }
    }

    for i in 0..q {
        let l = lr[i][0] - 1;
        let r = lr[i][1] - 1;
        println!("{}", cnt[r] - cnt[l]);
    }
}


Measured memory_bytes: 11004
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<list>
#include<set>
#include<cctype>
#include<stack>
#define ld long double
#define ll long long int
#define ull unsigned long long int
using namespace std;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const long long INF=1LL<<60;
//set<int>::iterator it;



int main(void){
	ios::sync_with_stdio(false); cin.tie(0);
	
	ll i,n,ans=0,a,d;
	cin>>n;
	for(i=0;i<n;i++){
		cin>>a;
		if(a%2!=0)continue;
		d=0;
		while(a>0&&a%2==0){
			a/=2;
			d++;
		}
		ans+=d;
	}
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    ll H,W,K;
    cin >> H >> W >> K;
    ll dp[H+1][W] = {};
    dp[0][0] = 1;
    rep(i,0,H){
        rep(j,0,1LL << (W-1)){
            bool ok = true;
            rep(k,0,W-2){
                int bit = (0b11) << k;
                //cout << bitset<8>(j & bit) << " " << bitset<8>(bit) << endl;
                if((j & bit) == bit)ok = false;
            }
            if(!ok)continue;
            //cout << bitset<8>(j) << endl;
            vector<int> tmp(W);
            rep(j,0,W)tmp[j] = dp[i][j];
            rep(k,0,W-1){
                if(j & (1 << k)){
                    swap(tmp[k], tmp[k+1]);
                }
            }
            rep(k,0,W)dp[i+1][k] += tmp[k];
        }
        rep(j,0,W)dp[i+1][j] %= MOD;
        /*
        rep(j,0,W)cout << dp[i][j] << endl;
        cout << endl;
        */
    }
    //rep(i,0,W)cout << dp[H][i] << endl;
    cout << dp[H][K-1] << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    int count = 0;
    int[] h = new int[N];
    
    for(int i=0; i<N; i++){
        h[i] = sc.nextInt();
        if(h[i] >= K){
            count++;
        }else{
        }
    }
    
    System.out.println(count);
  }
}

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

bool isprime[123457 * 2];

void eratos(void) {
  for (int i = 0; i < 123457 * 2; i++)
    isprime[i] = true;
  isprime[0] = isprime[1] = false;
  for (int i = 2; i * i < 123457 * 2; i++) {
    for (int j = i + i; j < 123457 * 2; j += i) {
      isprime[j] = false;
    }
  }
}

int main() {
  eratos();
  while (true) {
    int n;
    cin >> n;
    if (n == 0) return 0;

    int count = 0;
    for (int i = n + 1; i <= 2 * n; i++)
      if (isprime[i]) count++;

    cout << count << endl;
  }
}

Measured memory_bytes: 3328
#include<iostream>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip>//setprecision
#include<math.h>
#include <functional>
#include<climits>
using namespace std;
#define ll  long long 
#define rep(i, n)        for(ll i=0; i<(ll)(n); ++i)
#define mod 1000000007
  vector<ll>to[1000005];
int main(){
  ll a,b,c,d,e;cin>>a>>b>>c>>d>>e;
  ll f=fabs(c-a),g=b-d;
  if(g<=0)cout<<"NO";
  else if(f<=e*g)cout<<"YES";
  else cout<<"NO"; 
}


Measured memory_bytes: 27072
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <deque>
#include <cctype>
#include <cstdio>
#include <math.h>
using namespace std;
int main(){
    int sx,sy,tx,ty;
    cin >> sx >> sy >> tx >> ty;
    string s="";
    int x,y;
    x=abs(sy-ty);
    y=abs(tx-sx);
    for(int i=0;i<x;i++){
        s+="U";
    }
    for(int i=0;i<y;i++){
        s+="R";
    }
    for(int i=0;i<x;i++){
        s+="D";
    }
    for(int i=0;i<y;i++){
        s+="L";
    }
    s+="L";
    for(int i=0;i<x+1;i++){
        s+="U";
    }
    for(int i=0;i<y+1;i++){
        s+="R";
    }
    s+="DR";
    for(int i=0;i<x+1;i++){
        s+="D";
    }
    for(int i=0;i<y+1;i++){
        s+="L";
    }
    s+="U";
    cout << s << endl;
}

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

int main() {
	string s,t;
	cin>>s>>t;
	int a,b;
	cin>>a>>b;
	string x; cin>>x;
	if(x==s)a--;
	if(x==t)b--;
	cout<<a<<" "<<b;
	return 0;
}

Measured memory_bytes: 256
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <bitset>
#include <functional>
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}
 
ll nCr(ll n, ll r){
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
 
//-----------------------ここから-----------
ll factorial[201000];
ll invfactorial[201000];
ll extGCD(ll a, ll b, ll &x, ll &y){
	if (b == 0){
		x = 1;
		y = 0;
		return a;
	}
 
	ll d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
ll nCrM(ll n, ll r){
	ll ret = factorial[n];
	ret *= invfactorial[n - r];
	ret %= MOD;
	ret *= invfactorial[r];
	ret %= MOD; 
	return ret;
}

int main(void){
    ll n, k;
    cin >> n >> k;
    factorial[0] = 1;

    for (int i = 1; i < 201000; i++){
        factorial[i] = (factorial[i - 1] * i) % MOD;
    }
    for (int i = 0; i < 201000; i++){
        ll x, y;
        ll g = extGCD(factorial[i], MOD, x, y);
        while (x < 0) x += MOD;
        x %= MOD;
        invfactorial[i] = x;
    }

     ll ans = 1;
    for(int i = 1; i <= min(k, n - 1); i++){
        ans += nCrM(n, i) * nCrM(n - 1, n - i - 1);
        ans %= MOD;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3456
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
using namespace std;

typedef long long ll;

int a, b, c, d;

int main() {
	int n; cin >> n;
	a = n / 1000;
	b = (n / 100)%10;
	c = (n / 10) % 10;
	d = n % 10;
	for (int i = 0; i < 2; ++i) {
		int num;
		if (i == 0) num = a + b;
		else num = a - b;
		for (int j = 0; j < 2; ++j) {
			int s = num;
			if (j == 0) num += c;
			else num -= c;
			for (int k = 0; k < 2; ++k) {
				int t = num;
				if (k == 0) num += d;
				else num -= d;
				if (num == 7) {
					cout << a << (i == 0 ? "+" : "-") << b << (j == 0 ? "+" : "-") << c << (k == 0 ? "+" : "-") << d << "=7"<< endl;
					return 0;
				}
				num = t;
			}
			num = s;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200010,BASE=2010,MOD=1000000007;
int dp[BASE*2][BASE*2],a[N],b[N];
int jc[BASE*4],inv[BASE*4],n,mxa,mxb,sum;
void prework()
{
	jc[0]=inv[0]=jc[1]=inv[1]=1;
	for(int i=2;i<=8000;i++)
		jc[i]=jc[i-1]*i%MOD,inv[i]=MOD-(MOD/i)*inv[MOD%i]%MOD;
	for(int i=2;i<=8000;i++) (inv[i]*=inv[i-1])%=MOD;
}
int getcom(int a,int b)
{
	if(a<b||a<0) return 0;
	return jc[a]*inv[b]%MOD*inv[a-b]%MOD;
}
main()
{
	prework();
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&a[i],&b[i]),dp[BASE-a[i]][BASE-b[i]]++,mxa=max(mxa,a[i]),mxb=max(mxb,b[i]);
	for(int i=BASE-mxa;i<=BASE+mxa;i++)for(int j=BASE-mxb;j<=BASE+mxb;j++)
		(dp[i][j]+=dp[i-1][j]+dp[i][j-1])%=MOD;
	for(int i=1;i<=n;i++) (sum+=dp[BASE+a[i]][BASE+b[i]])%=MOD;
	for(int i=1;i<=n;i++) sum-=getcom(2*(a[i]+b[i]),2*a[i]),sum=(sum<0?MOD-(-sum)%MOD:sum%MOD);
	(sum*=500000004)%=MOD;
	return 0*printf("%lld\n",sum);
}

Measured memory_bytes: 129408
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<numeric>
using namespace std;
#define INF (1 << 30) - 1
#define LINF 1LL << 60
const int MOD = 1000000007;
using ll = long long;
using P = pair<int, int>;

int gcd(int a, int b){
	if(a % b == 0)return b;
	else return(gcd(b, a % b));
}

int gcd_3(int a, int b, int c){
	int d = gcd(a, b);
	return gcd(c, d);
}

int lcm(int a, int b){
	return a * b / gcd(a, b);
}

int main(){
  int k;
  cin >> k;
  int ans = 0;
  for(int a = 1; a <= k; ++a){
  	for(int b = 1; b <= k; ++b){
  		for(int c = 1; c <= k; ++c){
  			ans += gcd_3(a, b, c);
  		}
  	}
  }

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


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

ll solve() {
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N+1);
    for ( int i = 1; i <= N; i++ ) {
        cin >> A[i];
    }
    vector<ll> b(N+1), c(N+1);
    for ( int i = 1; i <= N; i++ ) {
        b[i] = b[i-1] + (A[i] > 0 ? A[i] : 0);
        c[i] = c[i-1] + A[i];
    }
    ll ans = 0;
    for ( int i = 1; i <= N-K+1; i++ ) {
        ll s = c[i+K-1] - c[i-1];
        if ( s < 0 ) s = 0;
        s += b[i-1];
        s += b[N] - b[i+K-1];
        ans = max(ans, s);
    }
    return ans;
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define mt make_tuple
#define MOD 1000000007
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define vl vector <long long int>
#define pii pair <int,int>
#define pll pair <long long int, long long int>
#define vpii vector< pair<int,int> >
#define vpll vector < pair <long long int,long long int> >
#define boost ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
const int inf = 1e9 + 5;
const ll inf64 = 2e18 + 5;

bool chk1(vector <int> &neg, vector <int> &pos, ll mid, ll k)
{
	ll res = 0;
	for(int x : neg) {
		int cnt = lower_bound(all(pos), (mid + x + 1) / x) - pos.begin();
		res += pos.size() - cnt;
	}
	return (res >= k);
}
bool chk2(vector <int> &neg, vector <int> &pos, ll mid, ll k)
{
	ll res = 0;
	for(int i = 1; i < pos.size(); i++) {
		int cnt = upper_bound(pos.begin(), pos.begin() + i, mid / pos[i]) - pos.begin();
		res += cnt;
	}
	for(int i = 1; i < neg.size(); i++) {
		int cnt = upper_bound(neg.begin(), neg.begin() + i, mid / neg[i]) - neg.begin();
		res += cnt;
	}
	return (res >= k);
}
int main()
{
	boost;
	int n, i;
	ll k;
	cin >> n >> k;
	int arr[n];
	fo(i, 0, n)
	cin >> arr[i];
	
	vector <int> pos, neg;
	int c0 = 0;
	fo(i, 0, n) {
		if(arr[i] > 0) pos.pb(arr[i]);
		else if(arr[i] == 0) c0++;
		else neg.pb(arr[i]);
	}
	
	ll zero = (1ll * c0 * (c0 - 1)) / 2 + 1ll * c0 * pos.size() + 1ll * c0 * neg.size();
	if(1ll * pos.size() * neg.size() < k && zero + 1ll * pos.size() * neg.size() >= k)
	cout << 0;
	else {
		sort(all(pos));
		sort(all(neg));
		ll ans = inf64;
		if(1ll * pos.size() * neg.size() >= k) {
			ll f = -1e18, l = -1, mid;
			while(f <= l) {
				mid = (f + l) / 2;
				if(chk1(neg, pos, mid, k)) {
					ans = min(ans, mid);
					l = mid - 1;
				}
				else
				f = mid + 1;
			}
		}
		else {
			k -= zero + 1ll * pos.size() * neg.size();
			for(int &x : neg)
			x *= -1;
			reverse(all(neg));
			
			ll f = 1, l = 1e18, mid;
			while(f <= l) {
				mid = (f + l) / 2;
				if(chk2(neg, pos, mid, k)) {
					ans = min(ans, mid);
					l = mid - 1;
				}
				else
				f = mid + 1;
			}
		}
		cout << ans;
	} 	
}


Measured memory_bytes: 5044
#include <iostream>

using namespace std;

int main()
{
	int n,val, count = 0;
	cin >> n;
	for (int i = 1;i <= n;i++) {

		cin >> val;
		if (i % 2 == 0 || val % 2 == 0)
			 continue;

		count++;
	}
	cout << count;
}


Measured memory_bytes: 3592
import copy


def isNumsDouble(nums):
    for num in nums:
        if nums.count(num) > 1:
            return True
    return False


def main(input_nums):
    total_list = []
    for i_a, num_a in enumerate(input_nums):
        for i_b, num_b in enumerate(input_nums):
            for i_c, num_c in enumerate(input_nums):
                for i_d, num_d in enumerate(input_nums):
                    for i_e, num_e in enumerate(input_nums):
                        if isNumsDouble([i_a, i_b, i_c, i_d, i_e]):
                            continue
                        total = 0
                        for num in [num_a, num_b, num_c, num_d, num_e]:
                            rem = total % 10
                            if rem != 0:
                                total += 10 - rem
                            total += num
                        total_list.append(total)
    return min(total_list)


if __name__ == "__main__":
    input_nums = []
    for _ in range(5):
        input_nums.append(int(input()))
    print(main(input_nums))


Measured memory_bytes: 3444
import java.util.*

fun rec(n: Int, s: String, used: Char) {

    if (s.length == n) {
        println(s)
        return
    }

    for (i in 'a'..used) {
        rec(n, s + i, used)
    }
    if (used < 'z') {
        rec(n, s + (used + 1), used + 1)
    }
}

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    rec(n, "", 'a' - 1)
}

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

using ll=long long;



void solve(){
    string s1,s2,s3;
    cin>>s1>>s2>>s3;
    cout<<s1[0]<<s2[1]<<s3[2]<<endl;
}

signed main(){
    //while(1)
    solve();
}

Measured memory_bytes: 256
#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

//みなさん天才的ですよね

int KH[300001], KW[300001];
ll HW[300001];
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);


	int H, W, M;
	cin >> H >> W >> M;

	rep(i, M) {
		int h, w;
		cin >> h >> w;

		KH[h]++;
		KW[w]++;
		HW[i] = (ll(h) << 30) + w;
	}

	int saidaih = -1, hh = 0;
	rep1(i, H) {
		if (saidaih < KH[i]) {
			saidaih = KH[i];
			hh = 1;
		}
		else if (saidaih == KH[i]) hh++;
	}
	int saidaiw = -1, ww = 0;
	rep1(i, W) {
		if (saidaiw < KW[i]) {
			saidaiw = KW[i];
			ww = 1;
		}
		else if (saidaiw == KW[i]) ww++;
	}

	ll are = ll(hh) * ww;

	int kazu = 0;
	rep(i, M) {
		kazu += (KH[HW[i] >> 30] == saidaih && KW[HW[i] & (1 << 30) - 1] == saidaiw);
	}

	if (kazu == are) co(saidaih + saidaiw - 1);
	else co(saidaih + saidaiw);

	Would you please return 0;
}

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

int main() { /* ここに書く */

  int N,a,c;
  cin >> N;
  c = 0;
  
    for(int i = 0; i<N/2 ; i++){
    
        cin >> a;
    
      if(a % 2 == 1){
       c++; 
      }
     
    cin >> a;
    
  }

if(N % 2 == 1){
  
  cin >> a;
  
  if(a%2 == 1){
    c++;
  }
  
}

cout << c << endl;
  
}

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

using namespace std;
#define int long long
const int N = 2e5 + 10, inf = 1e9 + 10;
int a[N], ps[N], n, MOD;
map <int , vector <int>> cnt;

int32_t main()
{
    cin >> n >> MOD;
    cnt[0].push_back(0);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i], a[i]--;
        ps[i] = (ps[i - 1] + a[i]) % MOD;
        int x = upper_bound(cnt[ps[i]].begin(), cnt[ps[i]].end(), i - MOD) - cnt[ps[i]].begin();
        ans += (int)cnt[ps[i]].size() - x;
        cnt[ps[i]].push_back(i);
    }
    cout << ans << "\n";
}


Measured memory_bytes: 25216
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,i,j,k,l,a,b,d,s,c;
    cin>>n;
    long long arr[n+10];
    for(i=0; i<n; i++)
    {
        cin>>arr[i];
    }
    sort(arr+0,arr+n);
    s=1;
    c=0;
    for(i=n-1; i>=0; i--)
    {
        if(arr[i]==arr[i-1])
        {
            s*=arr[i];
            i--;
            c++;
            if(c==2)
            {
                break;
            }
        }
    }
    if(c!=2)
    {
        cout<<0<<endl;
    }
    else
    {
        cout<<s<<endl;
    }

    return 0;

}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string divide[4] = {"dream", "dreamer", "erase", "eraser"};
int main() {
    string S;
    cin >> S;
    reverse(S.begin(), S.end());
    for (int i = 0; i < 4; i++) reverse(divide[i].begin(), divide[i].end());
    bool can = true;
    for (int i = 0; i < S.size();) {
        bool can2 = false;
        for (int j = 0; j < 4; j++) {
            string d = divide[j];
            if (S.substr(i, d.size()) == d) {
                can2 = true;
                i += d.size();
            }
        }
        if (!can2) {
            can = false;
            break;
        }
    }
    if (can) cout << "YES" << endl;
    else cout << "NO" << endl;
}

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

    class Program
    {
        static void Main(string[] args)
        {
            double[] a = Console.ReadLine().Split(' ').Select(double.Parse).ToArray();

            a[0] %= 10;
            string answer;

            if(a[0]==2 || a[0] == 4|| a[0] == 5|| a[0] == 7|| a[0] == 9)
            {
                answer = "hon";
            }else if (a[0]==0|| a[0] ==1|| a[0] ==6|| a[0] ==8)
            {
                answer = "pon";
            }
            else
            {
                answer = "bon";
            }

            Console.WriteLine(answer);

        }
    }

Measured memory_bytes: 28248
fun main(args: Array<String>) {
    val (max, left, right) = readLine()!!.split(" ").map(String::toInt)
    var total = 0
    for (num in 0..max) {
        val subtotal = num.toString().sumBy { it.toString().toInt() }
        if (subtotal in left..right) total += num
    }
    print(total)
}

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

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] ary = Console.ReadLine().Split(' ').ToArray();
            for (int i = 0; i < 3; i++)
            {
                string ARY = ary[i].ToUpper();
                Console.Write(ARY[0]);
            }
        }
    }
}


Measured memory_bytes: 13268
R,C,K = map(int, input().split())
a = [[0] * (C+1) for i in range(R+1)]
dp = [[[0] * (C+1) for i in range(R+1)] for j in range(4)]

for i in range(K):
  r,c,v = map(int, input().split())
  a[r-1][c-1] = v
  
for i in range(R):
  for j in range(C):
    for k in range(2,-1,-1):
      dp[k+1][i][j] = max(dp[k+1][i][j], dp[k][i][j] + a[i][j])
    for k in range(4):
      dp[0][i+1][j] = max(dp[0][i+1][j], dp[k][i][j])
      dp[k][i][j+1] = max(dp[k][i][j+1], dp[k][i][j])
ans = 0
for k in range(4):
  ans = max(ans, dp[k][R-1][C-1])
print(ans)
      
  

Measured memory_bytes: 430380
from sys import stdin

s, t = stdin.readline().rstrip().split()
a, b = [int(x) for x in stdin.readline().rstrip().split()]
u = stdin.readline().rstrip()

if (s == u):
    a -= 1
    
if (t == u):
    b -= 1

print(str(a) + " " + str(b))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1000000007;
#define INF 1LL<<30
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

int main() {
    int n;
    cin>>n;
    int m[n+1][n+1],p[n+1];
    rep(i,n){
        cin>>p[i]>>p[i+1];
        m[i][i]=0;
    }
    m[n][n]=0;
    for(int l=2;l<=n;l++){
        for(int i=1;i<=n-l+1;i++){
            int j=i+l-1;
            m[i][j]=1000000;
            for(int k=i;k<j;k++){
                m[i][j]=min(m[i][j],m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]);
            }
        }
    }

    cout<<m[1][n]<<endl;
}




Measured memory_bytes: 3092
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MX=100005;

class FastIO
{
private:
	static const int MXL=200000;
	char IBF[MXL],OBF[MXL],*p1,*p2,*p3,c;
	char *const END;
	int tp,bf[22],f;
	FILE *I,*O;
	char getchar(){return p1==p2?(p2=(p1=IBF)+fread(IBF,1,MXL,I)),p1==p2?EOF:*p1++:*p1++;}
	void putchar(char c){if(p3==END)flush();*p3++=c;}
	void flush(){fwrite(OBF,1,p3-OBF,O),p3=OBF;}
	
public:
	FastIO(FILE *I,FILE *O):I(I),O(O),p1(IBF),p2(IBF),p3(OBF),END(OBF+MXL){}
	~FastIO(){flush();}
	template<typename T>void read(T& x)
	{
		c=getchar(),x=0,f=0;
		while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
		while(isdigit(c))x=x*10+c-'0',c=getchar();
		if(f)x=-x;
	}
	template<typename T>void write(T x)
	{
		if(x<0)putchar('-'),x=-x;
		tp=0;
		do bf[++tp]=x%10,x/=10;while(x);
		while(tp)putchar(48+bf[tp--]);
		putchar('.'),putchar('0'),putchar('\n');
	}
}IO(stdin,stdout);
#define read(x) IO.read(x)
#define write(x) IO.write(x)

int N,x[MX],M,id[MX],siz,a[MX];
LL K,k0,ans;
bool vis[MX];
vector<int> q;

int main()
{
	read(N);
	for(int i=1;i<=N;i++)read(x[i]);
	for(int i=N;i>1;i--)x[i]-=x[i-1];
	for(int i=1;i<=N;i++)id[i]=i;
	read(M),read(K);
	for(int i=1,u;i<=M;i++)read(u),swap(id[u],id[u+1]);
	for(int i=2;i<=N;i++)if(!vis[i])
	{
		q.clear();
		for(int j=i;!vis[j];j=id[j])q.push_back(j),vis[j]=1;
		siz=q.size(),k0=K%siz;
		for(int j=0;j<siz;j++)id[q[j]]=q[(j+k0)%siz];
	}
	for(int i=1;i<=N;i++)
		ans+=x[id[i]],write(ans);
	return 0;
}

Measured memory_bytes: 3192
// review
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long ll;
const int MAXN = 200010;
const ll INF = 1e10;

int n;
ll a[MAXN];

void solve() {
  for (int i=0;i<n;i++) {
    a[i] -= i + 1;
  }
  sort(a, a + n);
  ll median = a[(n - 1) / 2];
  ll sum = 0;
  for (int i=0;i<n;i++) {
    sum += abs(a[i] - median);
  }
  cout << sum << endl;
}

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


Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<string>
#include<numeric>
#include<set>
#include<math.h>
using namespace std;

int N, K;
// オリジナル値格納ベクトル, 左右両方からの累積和ベクトルと負の値を格納するベクトル
vector<int> V, fromL, fromR;
vector<pair<int, int> >hoodoo;

// 与えられた組み合わせに対して利得を計算する
int gain(int l, int r, int b){
    // 不可能なパターン : 与えられた列以上の個数取得する、可能以上の個数返却する
    if(l + r > N) return 0;
    vector<int> cumul;
    int cnt = 0;
    cumul.push_back(0);
    for(int i = 0; i < hoodoo.size(); i++){
        if(hoodoo[i].second < l || hoodoo[i].second >= N - r){
            cumul.push_back(cumul[cnt] + hoodoo[i].first);
            cnt++;
        }
    }
    if(b > cnt) return 0;
    // 以上、不可能パターンの潰し終了

    int ret = 0; // 返り値

    // 左から一回でも取っていたら左側からの利得を加算
    if(l > 0) ret += fromL[l-1];
    // 同様に、右から一回でも取っていたら右側からの利得を加算
    if(r > 0) ret += fromR[r-1];
    // 負の宝石を返すことによるリターンの加算
    ret -= cumul[b];    

    return ret;   
}

int main(){
    cin >> N >> K;
    int v, tmp = 0;

    // fromL および fromR は累積和として構成する
    for(int i = 0; i < N; i++){
        cin >> v;
        V.push_back(v);
        tmp += v;
        if(v < 0) hoodoo.push_back(make_pair(v, i));
        fromL.push_back(tmp);
    }

    tmp = 0;

    for(int i = N - 1; i >= 0; i--){
        if(i == 0) v = fromL[i];
        else v = fromL[i] - fromL[i-1];
        tmp += v;
        fromR.push_back(tmp);
    }

    stable_sort(hoodoo.begin(), hoodoo.end());
    // fromL, fromR, hoodoo の完成
    
    vector<int> gains;
    gains.push_back(0); // バッファ用

    for(int a1 = 0; a1 <= K; a1++){
        for(int a2 = a1; a2 <= K; a2++){
            for(int a3 = a2; a3 <= K; a3++){
                tmp = gain(a1, a2 - a1, a3 - a2);
                if(tmp > 0) gains.push_back(tmp);
            }
        }
    }

    stable_sort(gains.begin(), gains.end(), greater<int>());

    cout << gains[0] << "\n";

    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define lc (pos<<1)
#define rc (pos<<1|1)
using namespace std;
int n,k,a[500005],p[500005];
inline int read()
{int x=0;
char c=getchar();
while (c<'0'||c>'9') c=getchar();
while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x;
}
inline void write(int ans)
{if (ans==0) {putchar('0');return;}
int t[21],cnt=0;
while (ans) {t[++cnt]=ans%10;ans/=10;}
for (int i=cnt;i>=1;i--) putchar('0'+t[i]);
}
inline int min(int a,int b)
{return a<b?a:b;}
inline int max(int a,int b)
{return a>b?a:b;}
int minn[2000005];
void build(int pos,int l,int r)
{minn[pos]=23333333;
if (l==r) return;
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
}
void modify(int pos,int l,int r,int p,int x)
{minn[pos]=min(minn[pos],x);
if (l==r) return;
int mid=(l+r)>>1;
if (p<=mid) {modify(lc,l,mid,p,x);}
else {modify(rc,mid+1,r,p,x);}
}
int ask(int pos,int l,int r,int lt,int rt)
{if (l==lt&&r==rt) return minn[pos];
int mid=(l+r)>>1;
if (rt<=mid) return ask(lc,l,mid,lt,rt);
if (lt>=mid+1) return ask(rc,mid+1,r,lt,rt);
return min(ask(lc,l,mid,lt,mid),ask(rc,mid+1,r,mid+1,rt));
}
int head[500005],nxt[1000005],v[1000005],d[500005],tot=0;
int g[500005],ans[500005],cnt=0;
inline void add(int a,int b)
{tot++;nxt[tot]=head[a];head[a]=tot;v[tot]=b;d[b]++;}
priority_queue <int,vector<int>,greater<int> > q;
int main (){
	int n1,n2,i,j;
	n=read();k=read();
	for (i=1;i<=n;i++)
	{p[i]=read();a[p[i]]=i;}
	build(1,1,n);
	for (i=n;i>=1;i--)
	{n1=23333333;n2=23333333;
	if (max(1,a[i]-k+1)<=a[i]-1) n1=ask(1,1,n,max(1,a[i]-k+1),a[i]-1);
	if (a[i]+1<=min(a[i]+k-1,n)) n2=ask(1,1,n,a[i]+1,min(a[i]+k-1,n));
	if (n1!=23333333) add(a[i],a[n1]);
	if (n2!=23333333) add(a[i],a[n2]);
	modify(1,1,n,a[i],i);
	}
	for (i=1;i<=n;i++)
	{if (!d[i]) {q.push(i);}
	}
	while (!q.empty())
	{int t=q.top();q.pop();
	g[++cnt]=t;
	for (i=head[t];i;i=nxt[i])
	{d[v[i]]--;
	if (!d[v[i]]) {q.push(v[i]);}
	}
	}
	for (i=1;i<=n;i++)
	{ans[g[i]]=i;}
	for (i=1;i<=n;i++)
	{write(ans[i]);
	putchar('\n');
	}
	return 0;
}

Measured memory_bytes: 29684
N,M = map(int,input().split())

if N<M:
    N,M = M,N

ans = 0
if M==1:
    if N==1:
        ans = 1
    else:
        ans = N-2
elif M==2:
    ans = 0
else:
    ans = (N-2)*(M-2)

print(ans)

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

using namespace std;

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

using ll = long long;
using pint = pair<int, int>;
using mint = map<int, int>;

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

const char sp = ' ';
const char cmm = ',';
const int MOD = 1e9+7;
const int INF = 1e9;
const ll LINF = 1e18;

ll mod(ll a, ll b){return (a%b+b)%b;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void Judge(bool b){b?Yes():No();}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void JUDGE(bool b){b?YES():NO();}
ll powMod(ll b, ll e, ll m){ll r=1;while(e>0){if(e&1)r=(r%m)*(b%m)%m;b=(b%m)*(b%m)%m;e>>=1;}return r;}
double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}

template<typename T>
void ppp(T n){cout << n << endl;}
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
    int len = v.size();
    s << '[';
    for (int i = 0; i < len; ++i) {
        s << v[i]; if (i < len-1) s << ", ";
    }
    s << ']';
    return s;
}

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    vector<ll> sum(n+1, 0ll);
    rep(i, m){
        int l, r;
        cin >> l >> r;
        sum[l]++; sum[r+1]--;
    }
    rep(i, n){
        sum[i+1] += sum[i];
    }

    ll cnt = 0ll;
    for(ll x : sum){
        if(x == m) ++cnt;
    }
    ppp(cnt);

    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef long double D;
typedef complex<D> P;
#define F first
#define S second
const ll MOD=1000000007;
//const ll MOD=998244353;

template<typename T,typename U>istream & operator >> (istream &i,pair<T,U> &A){i>>A.F>>A.S; return i;}
template<typename T>istream & operator >> (istream &i,vector<T> &A){for(auto &I:A){i>>I;} return i;}
template<typename T,typename U>ostream & operator << (ostream &o,const pair<T,U> &A){o<<A.F<<" "<<A.S; return o;}
template<typename T>ostream & operator << (ostream &o,const vector<T> &A){ll i=A.size(); for(auto &I:A){o<<I<<(--i?" ":"");} return o;}



int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N;
  cin>>N;
  vector<ll> A(N);
  cin>>A;
  ll ans=0,mx=0;
  for(auto &I:A){
    ll num=(I-1)/(mx+1);
    if(num==0){mx=max(mx,I);}
    ans+=num;
    mx=max(mx,1LL);
  }
  cout<<ans<<endl;


  return 0;
}


Measured memory_bytes: 1024