akhauriyash/Code-Regression huggingface dataset:
/*Stay true to yourself, yet always be open to learn. Work hard, and never give up on your dreams, 
even when nobody else believes they can come true but you. These are not cliches but real tools you 
need no matter what you do in life to stay focused on your path.
*/
 
 /*Pppppppp    UU      UU     CCCCCCCC    CCCCCCCC     HH     HH     UU      UU
   pp    pp    UU      UU     CC          CC           HH     HH     UU      UU
   pp    pp    UU      UU     CC          CC           HHHHHHHHH     UU      UU
   pppppppp    UU      UU     CC          CC           HHHHHHHHH     UU      UU
   pp          UU      UU     CC          CC           HH     HH     UU      UU
   pp          UUUUUUUUUU     CCCCCCCC    CCCCCCCC     HH     HH     UUUUUUUUUU
   */
 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
typedef long long ll;
#define loop(i,n)  for(int i=0;i<n;i++)
#define ford(i,a,b) for(int i=b;i>=a;i--)
#define read(a) int a; cin >>a;
#define readarr(a,n) int a[n] ; for(int i=0;i<n;i++) cin >> a[i];
#define readmat(a,n,m) int a[n][m]; for(int i=0;i<n;i++) for(j=0;j<m;j++) cin >> a[i][j];
#define pb push_back
#define ff first
#define ss second
#define vi vector<int>
#define pi pair<int,int>
#define vii vector<vector<int>>
#define sti set<int>
#define vpi vector<pair<int,int>>
#define print(a,n) for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl;
#define printmat(a,n,m) for(int i=0;i<n;i++) {for(j=0;j<m;j++) cout<<a[i][j]<<" "; cout<<endl;}
#define fast ios_base::sync_with_stdio(false);  cin.tie(NULL);
#define endl "\n"
#define mp make_pair
const ll inf = 1e18;
const ll mod = 1e9 + 7;
 
 int gcd(int a,int b){
 	if(b==0) return a;
 	return gcd(b,a%b);
 }
 

signed main()
{
 
    fast;
    int n,m;
    cin >> n >> m;
    readarr(a,m);
    int s=0;
    loop(i,m) s+=a[i];
    if(n-s>=0) cout<<n-s<<endl;
    else
    cout<<-1<<endl;
    return 0;
}

Measured memory_bytes: 3724
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<cstdio>
#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

const int CM = 1 << 17, CL = 12;
char cn[CM + CL], * ci = cn + CM + CL, * owa = cn + CM, ct;
const ll ma0 = 1157442765409226768;
const ll ma1 = 1085102592571150095;
const ll ma2 = 71777214294589695;
const ll ma3 = 281470681808895;
const ll ma4 = 4294967295;
inline int getint() {
	if (ci - owa > 0) {
		memcpy(cn, owa, CL);
		ci -= CM;
		fread(cn + CL, 1, CM, stdin);
	}
	int pn = 1;
	if (*ci == '-') {
		pn = -pn;
		ci++;
	}
	ll tmp = *(ll*)ci;
	int dig = ((tmp & ma0) ^ ma0) ? 68 - __builtin_ctzll((tmp & ma0) ^ ma0) : 0;
	tmp = tmp << dig & ma1;
	tmp = tmp * 10 + (tmp >> 8) & ma2;
	tmp = tmp * 100 + (tmp >> 16) & ma3;
	tmp = tmp * 10000 + (tmp >> 32) & ma4;
	ci += (64 - dig >> 3);
	while ((ct = *ci++) >= '0') tmp = tmp * 10 + ct - '0';
	return pn * tmp;
}

ll A[200001];
void pakuri_sort(int N, ll A[]) {
	const int b = 8;
	ll tmp[200001];
	rep(k, 4) {
		int kazu[1 << b] = {}, kazu2[1 << b] = {};
		rep(i, N) kazu[A[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu[i + 1] += kazu[i];
		for (int i = N - 1; i >= 0; i--) tmp[--kazu[A[i] >> k * b & ((1 << b) - 1)]] = A[i];
		k++;
		rep(i, N) kazu2[tmp[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu2[i + 1] += kazu2[i];
		for (int i = N - 1; i >= 0; i--) A[--kazu2[tmp[i] >> k * b & ((1 << b) - 1)]] = tmp[i];
	}
}

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


	int N = getint();
	rep1(i, N) {
		A[i] = getint() + A[i - 1];
	}

	pakuri_sort(N + 1, A);

	ll kotae = 0;
	ll mae = 1e18;
	int kazu = 0;
	rep(i, N + 1) {
		if (mae != A[i]) {
			mae = A[i];
			kazu = 0;
		}
		kotae += kazu++;
	}

	printf("%lld\n", kotae);

	Would you please return 0;
}

Measured memory_bytes: 3456
#include <bits/stdc++.h>
using namespace std;
struct po{int y,x;};
int w,h,dx[]={0,0,1,-1},dy[]={1,-1,0,0};
string mp[61];
queue <po> Q;
int xl,xr;
double sum,cnt;

void dfs(int y,int x,int used[62][11]){
  if(used[y][x]++)return;
  sum+=x+0.5,cnt++;
  int ch=mp[y][x];
  if(mp[y+1][x]!=ch&&mp[y+1][x]!='.')xl=min(xl,x),xr=max(xr,x);
  if(y-1>=0&&mp[y-1][x]!=ch&&mp[y-1][x]!='.') Q.push(po{y-1,x});
  for(int i=0;i<4;i++){
    int nx=x+dx[i],ny=y+dy[i];
    if(nx<0||ny<0||nx>=w||ny>=h||mp[ny][nx]!=ch)continue;
    dfs(ny,nx,used);
  }
}

bool check(int l,int r){
  int used[62][11]={};
  while(!Q.empty())dfs(Q.front().y,Q.front().x,used),Q.pop();
  double g=sum/cnt;
  return l<g&&g<r;
}

string solve(){
  int used[62][11]={};

  for(int i=h-1;i>=0;i--)
    for(int j=0;j<w;j++){
      if(mp[i][j]=='.'||used[i][j])continue;
      xl=100,xr=-1;
      sum=cnt=0;
      dfs(i,j,used);
      xr++;
      if(!check(xl,xr))return "UN";
    }
  return "";
}

int main(){
  while(1){
    cin>>w>>h;
    if(!h&&!w)break;
    for(int i=0;i<h;i++)cin>>mp[i];
    mp[h].clear();
    for(int i=0;i<w;i++)mp[h]+='#';
    cout <<solve()<<"STABLE"<<endl;
  }
  
  return 0;
}

Measured memory_bytes: 1236
#include<bits/stdc++.h>
using namespace std;
#define int int64_t
signed main(){
  int n,a,b,c,ans=0;
  vector<int> x,l;  
  cin>>n>>a>>b;
  for(int i=0;i<n;i++){
    cin>>c;
    if(i!=0) l.push_back(abs(c-x[i-1]));
    x.push_back(c);
  }
  for(int i=0;i<l.size();i++){
    if(l[i]*a<b) ans+=l[i]*a;
    else ans+=b;
  }
  cout<<ans<<"\n";
}


Measured memory_bytes: 5072
# -*- coding: utf-8 -*-

def isEven(num):
    mod = num % 2
    return True if mod == 0 else False

[a_str, b_str] = input().split()
a = int(a_str)
b = int(b_str)

if isEven(a) == False and isEven(b) == False:
    print('Odd')
else:
    print('Even')


Measured memory_bytes: 3060
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <stack>
#include <queue>
#include <complex>
#include <set>
#include <list>
#include <iomanip>
#include <map>
#include <limits.h>
#include <memory.h>


using namespace std;
static const double EPS = 1e-10;
typedef long long ll;
typedef unsigned long long ull;
#define FOR(i,n) for(int i=0;i<(int)n;++i)
#define FORNUM(p, x) for (int num = p; num < (int)(x); ++num)
#define FORI(p, x) for (int i = p; i < (int)(x); ++i)
#define FORJ(p, x) for (int j = p; j < (int)(x); ++j)
#define FORK(p, x) for (int k = p; k < (int)(x); ++k)
#define FORL(p, x) for (int l = p; l < (int)(x); ++l)

typedef vector<double> vec;
typedef vector<vec> mat;

int func(int x){
	if(x==0)
		return 0;
	if(x%2==1)
		return 0;
	if(x%2==0)
		return func(x/2)+1;

}

int main() {

	int n;
	cin>>n;
	int ans=1;
	int sum=0;
	for(int i=0;i<=n;i++){
		if(func(i)>sum){
			sum=func(i);
			ans=i;
		}

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




Measured memory_bytes: 256
<?php
//https://atcoder.jp/contests/abc139/submissions/7295556
//error_reporting(0);
$N = trim(fgets(STDIN));
//list($A,$B) =  explode(" ",trim(fgets(STDIN)));
//$H = explode(" ",trim(fgets(STDIN)));


for($i=0;$i<$N;$i++) {
 for($j=0;$j<$N;$j++) {
   for($k=0;$k<$N;$k++) {
     $res[]=$i.$j.$k;
   }
 }
}
printf("%d\n",count($res));


Measured memory_bytes: 4728
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement, groupby
from math import floor, ceil, sqrt, factorial, log
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop
from itertools import product
import sys
stdin = sys.stdin
mod = 10**9 + 7


def ns(): return stdin.readline().rstrip()


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


s = ns()
t = ns()
for i in range(len(s)):
    sm = s[i:] + s[:i]
    if sm == t:
        print("Yes")
        quit()
print("No")


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

typedef long long ll;
vector<int>V;

bool check_leap(int yr)
{
    if ((yr % 4 == 0) && !(yr % 100 == 0)|| (yr % 400 == 0))return true;
    else return false;
}


int main()
{
    #ifdef shibli
       //freopen("input.txt","r",stdin);
    #endif // shibli

    int A,B;
    bool line = false;
    while( scanf("%d %d",&A,&B) == 2 )
    {
        if( A == 0 && B == 0 )break;

        if( line )cout<<endl;

        line = true;

        for(int i = A; i<= B; i++ )
        {
            if( check_leap(i) )V.push_back(i);
        }

        if( V.size() == 0 )
        {
            cout<<"NA"<<endl;
        }
        else
        {
            for(int j = 0; j < V.size(); j++ )
            {
                cout<<V[j]<<endl;
            }
        }

        V.clear();
    }
}
/* Most men die at 25 , We just don't bury them until they are 70 - Benjamin Franklin */

Measured memory_bytes: 3200
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <set>

using namespace std;
using llong = long long;
const int MOD=1000000007;

int main(int argc, char**argv){
    int n;
    cin >> n;
    map<int, int> count;
    set<int> s;

    int tmp;
    for (int i = 0; i < n; i++){
        cin >> tmp;
        count[tmp]++;
        s.insert(tmp);
    }

    for (int x : s){
        count[x] %= 2;
    }

    int ans = 0;
    for (int x : s){
        ans += count[x];
    }

    cout << ans << endl;

    return 0;
}







Measured memory_bytes: 9600
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cstring>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };
 
int MOD = 1000000007;

int main() {
	int a, b; cin >> a >> b;
	cout << a * b << ' ' << (a + b) * 2 << endl;
}

Measured memory_bytes: 1160
#include <iostream>
#include <vector>
#include <cmath>
#include <string>

int main(){
  long long X;
  std::cin >> X;

  long long q;
  long long r;
  q = (long long)(X / 500) * 1000;
  r = X % 500;
  q += (long long)r / 5 * 5;
  std::cout << q << std::endl;
  
  return 0;
}


Measured memory_bytes: 256
#Educational DP Contest
#C-Vacation

n = int(input())
#n,m = map(int,input().split())
#lst1 = list(map(int,input().split()))

#dp table
#その選択肢を選んだときの最大値をそこに入れる[a,b,c]
dp = [[0,0,0] for _ in range(n)]
a,b,c = map(int,input().split())
dp[0] = [a,b,c]

#process1
for i in range(1,n):
    a,b,c = map(int,input().split())
    for j in range(3): #1つ前の手順で選んだものは使わない
        if j == 0: #about a
            dp[i][j] = max(dp[i-1][1],dp[i-1][2]) + a
        elif j == 1: #about b
            dp[i][j] = max(dp[i-1][0],dp[i-1][2]) + b
        else: #about c
            dp[i][j] = max(dp[i-1][0],dp[i-1][1]) + c


#output process
print(max(dp[-1]))

Measured memory_bytes: 57632
Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    l,r=map(int,input().split())
    L,R=max(L,l),max(R,r)
    LR.append([l,r])
M=R+1
lst=[0 for i in range(M)]
sosuu=set([2])
count=0
for i in range(3,M//2+1,2):
    flag=0
    for m in sosuu:
        if i%m==0:
            flag=1
            break

    if not flag:
        sosuu.add(i)
        if (i+1)//2 in sosuu:
            count+=1
    lst[i]=count

A=M//2
if not (M//2)%2:
    A-=1

while lst[A]:
    A+=2
#print(A,"A",sosuu,count)
for i in range(A,M,2):
    if (i+1)//2 in sosuu:
        flag=0
        for m in sosuu:
            if i%m==0:
                flag=1
                break
        if not flag:
            sosuu.add(i)
            count+=1
    lst[i]=count
#print(lst)
for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])


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

int main()
{
    int N;
    cin >> N;
    string c;
    cin >> c;
    int first = 0;
    int last = N-1;
    int count = 0;
    while(first < last)
    {
        if(c[first] == 'R')
        {
            first++;
        }
        if(c[last] == 'W')
        {
            last--;
        }
        if(first >= last)
        {
            break;
        }
        if(c[first] == 'W' && c[last] == 'R' && first < last)
        {
             swap(c[first],c[last]);
             count++;
        }
        
    }
    cout << count << endl;
}

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

template<typename T>
inline bool chmax(T& a, const T& b) {
    if (a < b){
        a = b;
        return true;
    }
    return false;
}

template<typename T>
inline bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

/**
 * @brief 多次元 vector の作成
 * @author えびちゃん
 */
namespace detail {
    template<typename T, int N>
    auto make_vec(vector<int>& sizes, T const& x) {
        if constexpr (N == 1) {
            return vector(sizes[0], x);
        } else {
            int size = sizes[N-1];
            sizes.pop_back();
            return vector(size, make_vec<T, N-1>(sizes, x));
        }
    }
}
template<typename T, int N>
auto make_vec(int const(&sizes)[N], T const& x = T()) {
    vector<int> s(N);
    for (int i = 0; i < N; ++i) s[i] = sizes[N-i-1];
    return detail::make_vec<T, N>(s, x);
}

__attribute__((constructor))
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

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

    if (m == 0 || m == 1) {
        if (k == 0) {
            if (m == 0) cout << "0 0\n";
            else cout << "0 0 1 1\n";

        } else {
            cout << -1 << '\n';
        }
        return 0;
    }

    int mx = (1 << m) - 1;
    if (k > mx) {
        cout << -1 << '\n';
        return 0;
    }

    cout << k << ' ';
    for (int i = 0; i <= mx; ++i) {
        if (i != k) cout << i << ' ';
    }
    cout << k << ' ';
    for (int i = mx; i >= 0; --i) {
        if (i != k) cout << i << ' ';
    }
    cout << '\n';
}


Measured memory_bytes: 3652
#include <stdio.h>
int main(void){
  int a,b,c;
  scanf("%d %d %d" ,&a,&b,&c);
  if(a<=b && b<=c){
    printf("%d %d %d\n", a,b,c);
  }
  if(a<=c && c<b){
    printf("%d %d %d\n", a,c,b);
  }   
  if(b<=a && a<c){
    printf("%d %d %d\n",b,a,c);
  }
   if(b<c && c<a){
    printf("%d %d %d\n", b,c,a);
  }
   if(c<a && a<b){
    printf("%d %d %d\n", c,a,b);
  }
    if(c<=b && b<a){
    printf("%d %d %d\n", c,b,a);
  }
  
  return 0;
}

Measured memory_bytes: 1764
ask=->n{$>.<<("? %d\n"%n).flush;gets.chomp=='Y'}
put=->n{$>.<<("! %d\n"%n).flush;exit}
if ask[10**9]
	i=1
	loop{ask[i*2]&&put[i];i*=10}
else
	i=10**8
	loop{
		if ask[i]
			put[(i+1..i*10-1).bsearch{|e|ask[e*10+9]}]
		end
		i/=10
	}
end

Measured memory_bytes: 2128
#include <stdio.h>
#include <stdlib.h>
int x[100000], y[100000];
int cnt[100000], cnts[100000], *tree[100000];
int dfs(int a, int b){
    int ans = 0, i;
    for(i = 0; i < cnt[a]; i++){
        if(tree[a][i] == b){
            continue;
        }
        ans ^= dfs(tree[a][i], a) + 1;
    }
    return ans;
}

int main(void){
    int n, i, j;
    scanf("%d",&n);
    for(i = 0; i < n; i++){
        cnt[i] = 0;
        cnts[i] = 0;
    }
    for(i = 0; i < n-1; i++){
        scanf("%d%d", &x[i], &y[i]);
        x[i]--;
        y[i]--;
        cnt[x[i]]++;
        cnt[y[i]]++;
    }
    for(i = 0; i < n; i++){
        tree[i] = malloc((cnt[i] + 1) * sizeof(int));
    }
    for(i = 0; i < n-1; i++){
        tree[x[i]][cnts[x[i]]++] = y[i];
        tree[y[i]][cnts[y[i]]++] = x[i];
    }

    int ans = dfs(0, -1);
    if(ans == 0){
        printf("Bob\n");
    }else{
        printf("Alice\n");
    }
    return 0;
}

Measured memory_bytes: 11736
#include<bits/stdc++.h>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
void init(int n);
int find(int n);
void unite(int x,int y);
bool same(int x, int y);
ll bpow(ll,ll,ll);
typedef vector<int> vec;
typedef vector<vec> mat;
mat mul(mat &A,mat &B);
mat pow(mat A,ll n);
int dx[3] = {1,0,-1};
int dy[3] = {1,0,-1};
const int MOD = 1000000007;

bool cmp_P(const P &a,const P &b){
  return a.second < b.second;
}
int main()
{
  string S;
  cin >> S;
  for(int i=1;i<S.size();i++){
    if((S.size()-i) % 2 == 1)
      continue;
    int d = (S.size()-i) / 2;
    if(S.substr(0,d) == S.substr(d,d)){
      cout << 2*d << endl;
      return 0;
    }
  }
  return 0;
}

int par[MAX_N];
int ranks[MAX_N];

//n要素で初期化
void init(int n){
  REP(i,n){
    par[i] = i;
    ranks[i] = 0;
  }

}

//木の根を求める
int find(int x){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y) return ;
  if(ranks[x] < ranks[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(ranks[x] == ranks[y]) ranks[x]++;
  }
}

bool same(int x, int y){
  return find(x) == find(y);
}

ll bpow(ll a, ll n,ll mod){
  int i = 0;
  ll res=1;
  while(n){
    if(n & 1)
      res = (res*a) % mod;
    a = (a*a) % mod;
    n >>= 1;
  }
  return res;
}
mat mul(mat &A, mat &B){
  mat C(A.size(),vec(B[0].size()));
    REP(i,A.size())REP(k,B.size())REP(j,B[0].size()){
    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
  }
  return C;
}

mat pow(mat A,ll n)
{
  mat B(A.size(),vec(A.size()));
  REP(i,A.size()){
    B[i][i] = 1;
  }
  while(n > 0){
    if ( n & 1) B = mul(B,A);
    A = mul(A,A);
    n >>= 1;
  }
  return B;
}


Measured memory_bytes: 256
package main

import "fmt"

func main() {

	var (
		num, shuffle_num int
		deck, new_deck   string
	)

	for {

		fmt.Scanln(&deck)

		if deck == "-" {
			break
		}

		fmt.Scanln(&num)

		new_deck = deck

		for i := 0; i < num; i++ {
			fmt.Scanln(&shuffle_num)
			new_deck = new_deck[shuffle_num:] + new_deck[:shuffle_num]
		}

		fmt.Println(new_deck)

	}
}



Measured memory_bytes: 1112
#include <iostream>
#include <iomanip>
#include <cassert>

#include <cstring>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <limits>
#include <queue>
#include <unordered_map>
#include <list>
#include <set>
#include <numeric>
using namespace std;

using ll = long long;

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

string next_substr(string& str, string& substr)
{
	string next_str = "";
	string work_str = substr;
	while (true)
	{
		std::string::size_type pos = 0;
		while(true)
		{
			pos = str.find(work_str, pos);
			if (pos == std::string::npos) break;
			if (pos + work_str.size() >= str.size()) break;
			string cand = work_str + str[pos + work_str.size()];
			if (substr < cand && (next_str == "" || next_str > cand))
			{
				next_str = cand;
			}

			++pos;
		}

		if (next_str != "") break;
		work_str.pop_back();
	}

	return next_str;
}

int main()
{
	string s;
	int K;
	cin >> s >> K;

	string substr = "";
	rep(i, K)
	{
		substr = next_substr(s, substr);
	}

	cout << substr << endl;
}

Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
using Graph=vector<vector<int>>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
typedef long long ll;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main(){
    int N;cin>>N;
    vector<int>A(N);
    rep(i,N){
        cin>>A[i];
    }
    int ans=0;
    rep(i,N){
        if(i%2==0&&A[i]%2==1){
            ans++;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define int long long
using namespace std;
double n,k;
double ans=0;
main(){
cin>>n>>k;
double t=1/n;
for(int i=1;i<=n;i++){
        int h=0,p=0;
        h=i;
while(h<k){
    h*=2;
    p++;
}
h=pow(2,p);
ans+=t*(double)(1/(double)h);
}
cout<<fixed;
cout<<setprecision(12)<<ans;
    return 0;
}


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

int main(){

  int x,y,z;
  int min;
  int e;
  
  //x + y^2 + z^3 = e
  //x = e - y^2 - z^3

  while(cin>>e , e){
    min = 1000000;

    y=0;
    while(y*y <= e){
      z=0;
      while(y*y+z*z*z <= e){
	x = e-y*y-z*z*z;
	if(x+y+z < min){
	  min = x+y+z;
	  //cout << e << '=' << x+y*y+z*z*z << endl;
	}

	z++;
      }
      y++;
    } 

    cout << min << endl;

  }

  return 0;
}

Measured memory_bytes: 1160
using System;

namespace atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            string a = Console.ReadLine();
            var b = a.Split(null);
            int c = int.Parse(b[0]);
            int d = int.Parse(b[1]);
            int e = c + d;
            int f = c - d;
            int g = c * d;
            int[] numbers = {e, f, g};
            var h = Max(numbers);
            Console.WriteLine(h);


        }

        static T Max<T>(params T[] nums) where T : IComparable
        {
            if (nums.Length == 0) return default(T);

            T max = nums[0];
            for (int i = 1; i < nums.Length; i++)
            {
                max = max.CompareTo(nums[i]) > 0 ? max : nums[i];
                // Minの場合は不等号を逆にすればOK
            }
            return max;
        }
    }
}


Measured memory_bytes: 13140
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;

const int N = 3010;
const ll inf = 1e17;
int a[N], n;
ll dp[N][N]; // length and left position

ll solve(int i, int j){
   ll &dp = ::dp[i][j];
   if (dp != -1) return dp;
   if (i == j) return dp = a[i];
   dp = max(a[i] - solve(i + 1, j), a[j] - solve(i, j - 1));
   return dp;
}

int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.precision(10);
   cout << fixed;
   cin >> n;
   for (int i = 0; i < n; ++i)
      cin >> a[i];
   memset(dp, -1, sizeof(dp));
   cout << solve(0, n - 1) << '\n';
   return 0;
}

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

#define fastIO() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'

int main()
{
 fastIO();
 long long n , fizbuzsum=0;
// bool fizbuz = false;
 cin>>n;
 for(int i=1; i<=n; i++)
 {
 	if( (i%3 != 0) && (i%5 != 0) )
 	{
 	//	fizbuz = true;
 		fizbuzsum+=i;
	 }
 }
cout<<fizbuzsum<<endl;
return 0;
}


Measured memory_bytes: 3656
X = int(input())

if X < 600: print(8)
elif X < 800: print(7)
elif X < 1000: print(6)
elif X < 1200: print(5)
elif X < 1400: print(4)
elif X < 1600: print(3)
elif X < 1800: print(2)
else: print(1)

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define radrad(a)  180.0 * a / M_PI
#define pow(x) x*x
#define ll long long
static const int MAX = 1000010;
static const ll INFTY = 1e12;
static const int NUMMAX = 300;


int main() {

  int N;
  double ans;

  cin >> N;
  vector<int> v(N);

  REP(i, N){
    cin >> v[i];
  }
  // cout << v[0] << endl;

  sort(v.begin(), v.end());
  //cout << v[0] << endl;

  ans = v[0];
  for(int i = 1; i < N; i++){
    ans = (double)(ans + v[i]) / 2.0;
  }

  cout << ans << endl;


  return 0;

}
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         pass System Test!
*/

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

int N;


int main(){
  int hf;
  cin >> N;
  for(int i = 9; i>0; i--){
    if(N % i == 0){
      hf = N /i;
      if(hf <10){
        printf("Yes\n");
        // printf("%d %d", i, hf);
        return 0;
      }
    }
  }
  printf("No\n");
  return 0;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ans = 0
j = -1
for i in a:
    ans += b[i-1]
    if i == j+1:
        ans += c[j-1]
    j = i
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#include<math.h>
#define mp make_pair
#define fi first
#define se second
#define INF 10000000000000000LL
#define ll  long long 
const int inf =INT_MAX;
const int MAX=3e5+9;
const ll MOD=1e9+7;
const int TOT_PRIMES=1e6+9;
const int MAX_A=71;
const int LN=20;
using namespace std;

int main(){
    ll N, K, ans;
    float res;
    cin >> N >> K;
    vector <ll> a(N);
    for(int i = 0; i < N; ++i){
        cin >> a[i];
    }
    N = N - K;
    res = float(N) / float(K - 1);
    ans = ceil(res);
    cout << ans + 1 <<"\n";
    return 0;
}

Measured memory_bytes: 3980
n, m = map(int, input().split())
a = [0] * m
b = [0] * m
c = [0] * m
INF = float('inf')
dist = [INF] * n
dist[0] = 0
for i in range(m):
    a[i], b[i], c[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1
    c[i] *= -1
for loop in range(n - 1):
    for i in range(m):
        if dist[a[i]] == INF:
            continue
        if dist[b[i]] > dist[a[i]] + c[i]:
            dist[b[i]] = dist[a[i]] + c[i]
ans = dist[n - 1]

neg = [False] * n
for loop in range(n):
    for i in range(m):
        if dist[b[i]] > dist[a[i]] + c[i]:
            dist[b[i]] = dist[a[i]] + c[i]
            neg[b[i]] = True
        if neg[a[i]]:
            neg[b[i]] = True
if neg[n - 1]:
    print('inf')
else:
    print(-ans)


Measured memory_bytes: 9304
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rrep(i,n) for(int (i)=((n)-1);(i)>=0;(i)--)
#define itn int
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
const long long INF = 1LL << 60;
const int MOD = 1000000007;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
signed main(void){
    int n,k; cin>>n>>k;
    int cnt = 0;
    rep(i,n){
        int a; cin>>a;
        if(a>=k) cnt++;
    }
    cout<<cnt<<endl;
}


Measured memory_bytes: 256
#include<stdio.h>

int A[1000000],n;

int binarySearch(int key){
  int left = 0;
  int right = n;
  int mid;
  while(left < right){
    mid = (left + right) / 2;
    if(key == A[mid])return 1;
    if(key > A[mid])left = mid + 1;
    else if(key < A[mid])right = mid;
  }
  return 0;
}

int main(){
  int i,q,k,sum = 0;

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

  scanf("%d",&q);
  for(i = 0; i < q; i++){
    scanf("%d",&k);
    if(binarySearch(k))sum++;
  }
  printf("%d\n",sum);

  return 0;
}



Measured memory_bytes: 2108
# -*- coding: utf-8 -*-
"""
Created on Sat May  9 02:11:20 2020

@author: shinba
"""
n,m = map(int,input().split())

W = [[False,0] for i in range(n)]

ac = 0

for i in range(m):
    A = input().split()
    a = int(A[0])
    b = str(A[1])
    if not W[a-1][0]:
        if b == "AC":
            ac += 1
            W[a-1][0] = True
        else:
            W[a-1][1] += 1

wa = 0

for i in range(n):
    if W[i][0]:
        wa += W[i][1]

print(ac,wa)
            
        



Measured memory_bytes: 13172
#include <cstdio>
#include <stdlib.h>
#include <cmath>
using namespace std;
int main() {
	int a, b, C;
	scanf("%d %d %d", &a, &b, &C);
	double S, L, h;
	h = b * sin(C * M_PI / 180);
	S = a * h / 2;
	L = a + b + sqrt(pow(a, 2.0) + pow(b, 2.0) - 2 * a * b * cos(C * M_PI / 180));
	printf("%f\n%f\n%f\n", S, L, h);
}


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define inp "inp"
#define out "out"
using namespace std;
void Input ()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,d;
    cin>>n>>d;
    int ans=n/(d*2+1);
    if (ans*(d*2+1)<n) cout<<ans+1;
    else cout<<ans;
}
 main()
{
    Input();
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
using namespace std;
char s[101];
int ans;
int main(){
	gets(s);
	for(int i=0;i<strlen(s);i++){
		if(s[i]=='C'){
			for(int j=i+1;j<strlen(s);j++){
				if(s[j]=='F'){
					puts("Yes");
					return 0;
				}
			} 
		} 
	}
	puts("No");
	return 0;
}

Measured memory_bytes: 128
n=int(input())
l=list(map(int,input().split()))

c=0
for i in range(n):
	for j in range(i+1,n):
		for k in range(j+1,n):
			if l[i]!=l[j] and l[j]!=l[k] and l[k]!=l[i] and 2*max([l[i],l[j],l[k]])<sum([l[i],l[j],l[k]]):
				c+=1

print(c)

Measured memory_bytes: 9148
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int main()
{
    ios_base::sync_with_stdio(0);
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
    ll odp = 0;
    if (k < n)
        for (int i = k; i < n; ++i)
            odp += a[i];
    cout << odp;
    return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
/* 
考虑 f(H) 表示对于一个生命为 H 的怪兽，我们需要最少耗费多少 Magic Points 才能把它杀死。
那么我们枚举所有的 spell，假设现在枚举第 i 个 spell，它的攻击力为 A[i]，需要耗费 B[i] 点 Magic Points。
f(H)=(i=1,n)min(f(H-A[i])+B[i]
这个式子的意思就是 i 从 1 循环到 n 中所有 f(H-A[i])+B[i] 的最小值
f(H) 可以通过递归来求。
但是在这题中，H<=1e4，会 TLE。
所以需要通过 “记忆化” 的手段来优化。
记录 F[H]=f(H)
然后我们在想要查询 f(H) 的时候先看 F[H] 是否已经被更新过了
如果 F[H] 没有值，那么可以通过上述的式子来求 f(H)
否则就直接用我们存下来的值就好了。
注意在求好 f(H) 的时候需要更新 F[H]。
*/
map<int,int> mapH;
vector<int> A;
vector<int> B;
int getMinMagicPoint( int H )
{
	//如果已经保存 ，则直接返回 
	if( mapH.find(H) != mapH.end() )
		return mapH[H];
	//血量已经减完，不需要法术 
	if( H <= 0 )
		return 0;
	//如果未保存，则递归计算
	if( A.size() > 0 )
	{
		//初始化为第一个位置 
		int minMagicPoint = getMinMagicPoint(H-A[0]) + B[0];
		//遍历所有的法术，寻找最小的一个 
		for( int i=1; i<A.size(); i++ )
		{
			int tmpMagicPoint = getMinMagicPoint(H-A[i]) + B[i];
			if( tmpMagicPoint < minMagicPoint )
			{
				minMagicPoint = tmpMagicPoint;
			}
		}
		//将结果记录下来 
		mapH[H] = minMagicPoint;
		return minMagicPoint;
	}
	return 0;
}
int main()
{ 
	int H,N;
	cin>>H>>N;
	for( int i=0; i<N; i++ )
	{
		int a,b;
		cin>>a>>b;
		A.push_back(a);
		B.push_back(b);
	}
	int minMagicPoint = getMinMagicPoint(H);
	cout << minMagicPoint << endl;
	
	return 0;
}


Measured memory_bytes: 1536
n=int(input())
P=list(map(int,input().split()))

ans=0
for i in range(0,n-2):
    if min(P[i],P[i+1],P[i+2])!=P[i+1] and max(P[i],P[i+1],P[i+2])!=P[i+1]:
        ans+=1
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main (){
    string s;
    cin >> s;
    string ans = "",sum;
    for(int i=0;i<s.size();i++){
        if(s.at(i)== 'A' || s.at(i)== 'T' || s.at(i)== 'G' || s.at(i)== 'C'){
            sum += s.at(i);
            if(sum.size()>ans.size()){
                ans = sum;
            }
        }
        else{
            sum = "";
        }
    }
    cout << ans.size() << endl;

}

Measured memory_bytes: 256
#include<iostream>
 
using namespace std;
 
int main()
{
    int a[3][3];
    bool b[3][3];
  
    for(int i=0;i<3;i++)
    {
      for(int j=0;j<3;j++)
      {
        cin >> a[i][j];
        b[i][j] = false;
      }
    }
 
    int N;
    cin >> N;
  
    for(int k=0;k<N;k++)
    {
      int c;
      cin >> c;
      
      for(int i=0;i<3;i++)
      {
        for(int j=0;j<3;j++)
        {
          if(c==a[i][j]) b[i][j] = true;
        }
      }
    }
  
    bool isYes = false;
      for(int i=0;i<3;i++)
      {
          if(b[i][0]==true &&b[i][1]==true &&b[i][2]==true) isYes = true;
      }
 
          if(b[0][0]==true &&b[1][1]==true &&b[2][2]==true) isYes = true;
 
      for(int i=0;i<3;i++)
      {
          if(b[0][i]==true &&b[1][i]==true &&b[2][i]==true) isYes = true;
      }
          if(b[2][0]==true &&b[1][1]==true &&b[0][2]==true) isYes = true;
  
    if(isYes)
    {
      cout << "Yes" << endl;
    }
  else
  {
      cout << "No" << endl;
  }
  
    return 0;
}

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

const char wall = '#';
vector<vector<char>> fields;
vector<vector<bool>> used;
vector<vector<ll>> dist;
const int dx[4] = {0, -1, 0, 1};
const int dy[4] = {1, 0, -1, 0};

vector<ll> A;
// vectorのリサイズ
// A.resize(N);

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

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

  ll a, b, c;
  cin >> a >> b >> c;
  cout << max(0LL, b + c - a) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <climits>
#include <vector>
#include <numeric>
#include <complex>
#include <map>
#include <bitset>
#include <stack>
#include <queue>
#include <set>
using namespace std;

#define __int64 long long
#define long __int64
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
const int Vec = 4;
const int Vecy[Vec] = {0,-1,0,1};
const int Vecx[Vec] = {1,0,-1,0};
const int Modd = 1000000007;

string s;
int N, A, B, C, D;

bool hasDoubleBlock(int from, int to){
    for(int i=from; i<=to; i++){
        if(s[i] == '#' && s[i+1] == '#') return true;
    }

    return false;
}

bool hasTripleBlank(int from, int to){
    for(int i=max(1,from); i<=min(N-1,to); i++){
        if(s[i-1] == '.' && s[i] == '.' && s[i+1] == '.') return true;
    }

    return false;
} 

int main(){
    cin >> N >> A >> B >> C >> D >> s;
    s = "s" + s;

    if(!(A < B && B < D && D < C)
       && !(B < A && A < C && C < D)){
        if(!hasDoubleBlock(A, C)
          && !hasDoubleBlock(B, D)){
            cout << "Yes" << endl;       //Yes
        }else{
            cout << "No" << endl;       //No
        }
    }else{
        if(!hasDoubleBlock(A, C)
           && !hasDoubleBlock(B, D)){
            if(    (A < B && B < D && D < C && hasTripleBlank(B, D))
                || (B < A && A < C && C < D && hasTripleBlank(A, C))){                   
                cout << "Yes" << endl;   //Yes
            }else{
                cout << "No" << endl;   //No
            }
        }else{
            cout << "No" << endl;       //No
        }
    }
}

Measured memory_bytes: 772
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(x)(x).begin(), (x).end() // 昇順ソート
#define rall(v)(v).rbegin(), (v).rend() // 降順ソート
#define INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair < ll, ll >
#define F first
#define S second
const int MOD = 1000000007;
template < class T > bool chmax(T & a,const T & b) { if (a < b) { a = b; return true; } return false; }
template < class T > bool chmin(T & a,const T & b) { if (a > b) { a = b; return true; } return false; }
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

int main() {
    int H,W;cin >> H >> W;
    vector<vector<char>> a(H,vector<char>(W));
    rep(i,H)rep(j,W)cin >> a[i][j];

    rep(i,W+2)cout << '#';
    cout << endl;
    rep(i,H){
        cout << '#';
        rep(j,W)cout << a[i][j];
        cout << '#';
        cout << endl;
    }
        rep(i,W+2)cout << '#';
    cout << endl;
}

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

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

    if(n == 1)
        cout << 1 << "\n";
    else 
        cout << double (n % 2 == 0 ? 0.5 : (double(n / 2 + 1) / n)) << "\n";
    return 0;
}


Measured memory_bytes: 3764
n = int(input())
answerL = []
for i in range(n):
    inputL = input().split()
    newL = [0]*n
    k = int(inputL[1])
    for j in range(k):
        target = int(inputL[1+j+1])
        newL[target-1] = 1
    answerL.append(newL)
for ans in answerL:
    print(' '.join(list(map(str, ans))))


Measured memory_bytes: 5676
#include <bits/stdc++.h>
using namespace std;
int main(){
  
  int m, n;
  cin >> n >> m;
  
  vector<int> l(m);
  vector<int> r(m);
  
  for(int i; i < m; i++){
    cin >> l.at(i);
    cin >> r.at(i);
  }
  
  sort(l.begin(), l.end());
  sort(r.begin(), r.end());
  
  int x;
  x = (r.at(0) - l.at(m - 1) + 1);
  
  if(x > 0)
    cout << x << endl;
  if(x < 1)
    cout << 0 << endl;
}

Measured memory_bytes: 1024
"use strict";
function I(s,f){this._s=s.split("\n");this._c=0;this._l=0;this._f=f||Number}I.prototype.a=function(){var l=this._s[this._l];if(!l)return;var t=l.trim().split(" ");var a=t[this._c];this._c++;if(t.length===this._c){this._c=0;this._l++}return this._f(a)};I.prototype.l=function(){var l=this._s[this._l];if(!l)return;this._c=0;this._l++;return l.split(" ").map(this._f)};

function main(input) {
  const o = new I(input);

  var arr = [];
  for (var i = 0; i < 5 ; i++){
    arr.push(o.a());
  }

  var k = o.a();

  arr.sort((a,b) => a - b );
  console.log(arr[4] - arr[0] <= k ? "Yay!" : ":(");
  
}


main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7372
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		 Scanner sc = new Scanner(System.in);
		 int n = sc.nextInt();
		 int m = sc.nextInt();
		 
		 int A[][]= new int [n][m];
		 int B[]= new int [m];
		 int C[]= new int [n];

			 for(int i =0;i<n;i++){
				 for(int j =0;j<m;j++){
				 int a = sc.nextInt();
				 A[i][j]=a;
				 }
			 }
				 for(int k =0;k<m;k++){
					 int b = sc.nextInt();
					 B[k]=b;
					 }
				 
			for(int g=0;g<n;g++){
			 for(int l=0;l<m;l++){
				 C[g]=C[g]+A[g][l]*B[l];
			 }
			 System.out.println(C[g]);
			}
			
		 
		//System.out.println("");
	}
	

}



Measured memory_bytes: 40372
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
const LL Maxn = 2010;
const LL Mod = 1e9+7;
LL n, m;
LL f[Maxn][Maxn];
LL jc[Maxn*Maxn], inv[Maxn*Maxn];
LL C(LL A, LL B) { return jc[A]*inv[B]%Mod*inv[A-B]%Mod; }
void up(LL &x, LL y) { x = (x+y)%Mod; }
int main() {
	LL i, j, k;
	scanf("%lld%lld", &n, &m);
	if(m == 1){ printf("1\n"); return 0; }
	jc[0] = 1;
	for(i = 1; i <= n*m; i++) jc[i] = jc[i-1]*i%Mod;
	inv[0] = inv[1] = 1;
	for(i = 2; i <= n*m; i++) inv[i] = inv[Mod%i]*(Mod-Mod/i)%Mod;
	for(i = 2; i <= n*m; i++) inv[i] = inv[i]*inv[i-1]%Mod;
	f[0][0] = 1;
	for(i = 0; i <= n; i++){
		for(j = i; j <= n; j++){
			if(i < j) up(f[i+1][j], f[i][j]);
			if(j < n) up(f[i][j+1], C((m-1)*(j+1)+i-1,m-2)*f[i][j]);
		}
	}
	printf("%lld\n", f[n][n]*jc[n]%Mod);
	return 0;
}

Measured memory_bytes: 94464
#include<bits/stdc++.h>
using namespace std;
long dp[10000004];
long jump(long arr[],long n){
	//base case
	if(n<=1){
		return 0;
	}
  if(dp[n]!=-1) return dp[n];
	return dp[n]= min(abs(arr[n-1]-arr[n-2])+jump(arr,n-1),abs(arr[n-1]-arr[n-3])+jump(arr,n-2));
}


int main(){
  memset(dp,-1,sizeof(dp));
	long n;
	cin>>n;
	long arr[n];
	for(long i=0;i<n;i++){
		cin>>arr[i];
	}
	cout<<jump(arr,n);
}

Measured memory_bytes: 82304
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Map.Entry;

import java.util.PriorityQueue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
	public static final long MOD = 1000000007;
	
	public static class State implements Comparable<State> {
		long limit;
		long cnt;
		
		public State(long limit, long cnt) {
			this.limit = limit;
			this.cnt = cnt;
		}

		@Override
		public int compareTo(State o) {
			return Long.compare(o.limit, this.limit);
		}
	}
	
	
	public static void main(String[] args) throws IOException {
		try(final Scanner sc = new Scanner(System.in)){
			final int N = sc.nextInt();
			final int A = sc.nextInt();
			final int B = sc.nextInt();
			
			System.out.println(Math.min(A, B) + " " + (Math.max(0, A + B - N)));
		}
	}

	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() throws IOException {
			while(!hasNext()){
				tok = new StringTokenizer(br.readLine());
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}

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

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public int[] nextIntArray(int n) throws IOException {
			final int[] ret = new int[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextInt();
			}
			return ret;
		}

		public long[] nextLongArray(int n) throws IOException {
			final long[] ret = new long[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextLong();
			}
			return ret;
		}

		public void close() throws IOException {
			br.close();
		}
	}
}

Measured memory_bytes: 22996
#include<stdio.h>
#include<math.h>
const double pi=acos(-1.0);
double ang[4096];
int main()
{
	int n,l;
	scanf("%d%d",&n,&l);
	double ansx=0,ansy=0;
	for(int i=0;i<n;i++)
	{
		int t;
		scanf("%d",&t);
		ang[i]=pi*2*t/l;
	}
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			double angg=(ang[i]+ang[j])/2;
			ansx-=cos(angg)*(((j-i-1)<<1)-(n-2));
			ansy-=sin(angg)*(((j-i-1)<<1)-(n-2));
		}
	}
	ansx/=(long long)n*(n-1)*(n-2)/6;
	ansy/=(long long)n*(n-1)*(n-2)/6;
	printf("%.10f %.10f\n",ansx,ansy);
	return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#include<cmath>
#include<bitset>
#include<queue>
#define ll long long
#define itn int
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define INF ((1LL<<62)-(1LL<<31))
#define MOD 1000000007
using namespace std;

int N,M,K,A,B,C,ans=0,cnt=0;
string S,T;
vector<int> P,Q;
vector<pair<int,int>> PP;
bool CAN=false;


int main(){
  cin>>S;
  ans=S.size();
  for(int i=0; i<S.size(); ++i){
    if(S.at(i)=='S'){
      cnt++;
    }
    else if(S.at(i)=='T'){
      if(cnt>0){
        cnt--;
        ans-=2;
      }
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 640
#include <cstdio>
#include <cmath>
#include <algorithm>

long double pi = acosl(-1.0L);

int main() {
  long double a, b, x;
  scanf("%Lf %Lf %Lf", &a, &b, &x);

  long double r;
  if (x > a*a*b/2) {
    r = atanl(2.0/a/a*(a*b-x/a));
  } else {
    r = pi/2 - atanl(2*x/a/b/b);
  }
  printf("%.20Lf\n", r*180.0/pi);
}


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

int main(){
    int a, b, c, d; cin >> a >> b >> c >> d;
    while (true)
    {
        c -= b;
        if (c <= 0) {
            cout << "Yes" << endl;
            break;
        }
        a -= d;
        if (a <= 0){
            cout << "No" << endl;
            break;
        }
    }
    
}

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

using namespace std;
using ll = long long;

int main() {
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i = 0;i < n;++i) {
        cin>>a[i];
    }
    map<int,int> mp;
    set<int> cnt;
    vector<int> ans;
    for(int i = 0;i < n;++i) {
        mp[a[i]]++;
        if(mp[a[i]]==1)cnt.insert(a[i]);
        if(mp[a[i]]==0)cnt.erase(a[i]);

        mp[a[n-1-i]]--;
        if(mp[a[n-1-i]]==0)cnt.erase(a[n-1-i]);
        if(mp[a[n-1-i]]==-1)cnt.insert(a[n-1-i]);

        if(cnt.size()==0)ans.emplace_back(i+1);
    }

    for(int i = 0;i < ans.size()-1;++i) {
        cout<<ans[i]<<" ";
    }
    cout<<n<<endl;

    return 0;
}



Measured memory_bytes: 6560
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep2(i, m, n) for(int i=int(m); i<int(n); i++)
#define rep(i, n) rep2(i, 0, n)
#define all(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
const int INF = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS = 1e-10;
const int MOD = int(1e9)+7;
template<typename T> inline bool chmin(T& a, T b) {if(a>b) {a=b; return true;} return false;}
template<typename T> inline bool chmax(T& a, T b) {if(a<b) {a=b; return true;} return false;}


int main() {
  ll n, k; cin >> n >> k;
  ll kmax = (n-1) * (n-2) / 2;
  if (k > kmax) {
    cout << "-1" << endl;
    return 0;
  }

  vector<P> E;
  rep(i, n-1) {
    E.push_back(P(0, i+1));
  }

  ll added = 0;
  rep2(i, 1, n) {
    rep2(j, i+1, n) {
      if (kmax - added == k) break;
      E.push_back(P(i, j));
      ++added;
    }
    if (kmax - added == k) break;
  }

  cout << (added + n - 1) << endl;
  for (auto e : E) {
    cout << (e.first+1) << " " << (e.second+1) << endl;
  }
  return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>

using namespace std;

const int N=20;
const int L=(1<<N)+10;
const int INF=0x3f3f3f3f;

int n,S,a[L],t[L],t2[L];

bool vis[L];

int main()
{
	scanf("%d",&n);
	S=(1<<n)-1;
	for(int i=0;i<=S;++i)
		scanf("%d",a+i);
	for(int i=0;i<=S;++i)
	{
		t[i]=a[i];
		t2[i]=-INF;
	}
	for(int i=0;i<n;++i)
		for(int j=S,k;j;--j)if((j>>i)&1)
		{
			k=j^(1<<i);
			if(t[k]>t[j])
			{
				t2[j]=t[j];
				t[j]=t[k];
			}
			else
				t2[j]=max(t2[j],t[k]);
		}
	int ans=-INF;
	for(int i=1;i<=S;++i)
	{
		ans=max(ans,t[i]+t2[i]);
		printf("%d\n",ans);
	}
	return 0;
}


Measured memory_bytes: 14336
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <stack>
#include <vector>
using namespace std;
typedef long long ll;
int main(){
  int n,k;
  cin >> n >> k;
  string s;
  cin >> s;

  vector<int> nums;
  if(s[0] == '0')nums.push_back(0);
  for(int i = 0;i < s.size();){
    int j = i;
    while(j < s.size() && s[j] == s[i])j++;
    nums.push_back(j-i);
    i = j;
  }
  if(s.back() == '0')nums.push_back(0);

  vector<int> sums((int)nums.size() + 1,0);
  for(int i = 0;i < nums.size();i++)sums[i+1] = sums[i] + nums[i];

  int res = 0;
  for(int left = 0;left < sums.size();left+=2){
    int right = left + k*2 + 1;
    if(right >= sums.size()) right = (int)sums.size() - 1;
    res = max(res,sums[right]-sums[left]);
  }
  cout << res << endl;
}
  


Measured memory_bytes: 1272