akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long 
using namespace std;

ll cal(int n,int w,vector<int> &wts,vector<int> &vals,vector<vector<ll>> &dp){
	if (n==0 || w==0){
		return 0;
	}
	if(dp[n][w]!=-1){
		return dp[n][w];
	}
	dp[n][w]=cal(n-1,w,wts,vals,dp);
	if(wts[n-1]<=w){
		dp[n][w]=max(dp[n][w],vals[n-1]+cal(n-1,w-wts[n-1],wts,vals,dp));
	}

	return dp[n][w];
}

int main(){
	int n,w;
	cin >>  n >> w;
	vector<int> vals(n),wts(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> wts[i] >> vals[i];
	}
	vector<vector<ll>> dp(n+1,vector<ll>(w+1,-1));

	printf("%lld\n",cal(n,w,wts,vals,dp));


}

Measured memory_bytes: 83004
//@@@@@@@@@@ JAI BAJRANG BALI @@@@@@@@@
/********** code by naman *******/

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define maxn 10000001
#define endl "\n"
#define im INT_MAX
#define vec vector <ll>
#define mps map <ll,ll>
#define ppl vector<pair<ll,ll>> 
#define fi first
#define si second
#define pr pair<ll,ll> 
#define mvec map<ll,vector <ll>>
  
int main()
{
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    ll sum=0;
    for(ll i=1;i<=n;i++)
    {
    	for(ll j=1;j<=n;j++)
    	{
    		for(ll k=1;k<=n;k++)
    		{
    			ll q=__gcd(j,k);
    			ll p=__gcd(i,q);
    			sum=sum+p;
    		}
    	}
    }
    cout<<sum<<endl;

return 0;
}


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

struct P{ double x, y; };

bool Range(int x, int y)
{ return 0 <= x && x < 8 && 0 <= y && y < 8; }


const int target[7][3][2] = 
{
	{{1, 0}, {0, 1}, {1, 1}},
	{{0, 1}, {0, 2}, {0, 3}}, 
	{{1, 0}, {2, 0}, {3, 0}},
	{{0, 1}, {-1,1}, {-1,2}},
	{{1, 0}, {1, 1}, {2, 1}},
	{{0, 1}, {1, 1}, {1, 2}},
	{{1, 0}, {0, 1}, {-1,1}}
};



char solve(vector<string>& field)
{
	rep(x, 8) rep(y, 8) rep(t, 7)
	{
		if(Range(x, y) && field[y][x] == '1')
		{
			rep(p, 3)
			{
				int nx = x + target[t][p][0], ny = y + target[t][p][1];
				if(!Range(nx, ny) || field[ny][nx] != '1')
					break;
				else if(p == 2)
				{
					return 'A' + t;
				}
			}
		}
	}

	return 'Z';
}



int main()
{
	vector<string> f(8);
	while(cin >> f[0] >> f[1] >> f[2] >> f[3] >> f[4] >> f[5] >> f[6] >> f[7])
		cout << solve(f) << endl;	
}

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

using namespace std;

int main(){
    string str;
    while(cin>>str&&str!="0"){
        int cnt=0;
        int ap[2][11];
        for(int i = 0; i < 2; i++)
            fill(ap[i],ap[i]+11,0);
        ap[(str.size()-1)%2][str[str.size()-1]-'0']++;
        for(int i = str.size()-2; i >= 0; i--){
            int sum=0;
            if(str[i]=='0'){
                for(int j = 0; j <= 10; j++)
                    ap[(i)%2][j]=ap[(i+1)%2][j];
                ap[i%2][0]++;
                continue;
            }
            int ad=str[i]-'0';
            if((str.size()-1-i)%2!=0){
                ad*=10;
            }
            for(int j = 0; j <= 10; j++)
                ap[(i)%2][j]=ap[(i+1)%2][(j-ad+110)%11];
            ap[i%2][ad%11]++;
            cnt+=ap[i%2][0];
        }
        cout<<cnt<<endl;
    }

    return 0;
}

Measured memory_bytes: 1116
#include <stdio.h>

int main(){
    double a,b,c,k;
    
    scanf("%lf %lf %lf %lf", &a,&b,&c,&k);

    if(a >= k){
        printf("%.0lf", k);
    }else if(a <= k && a + b >= k){
        printf("%.0lf", a);
    }else{
        printf("%.0lf", 2 * a + b - k);
    }
    }

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

#define int long long
#define double long double
#define pq priority_queue
#define pb push_back
#define mp make_pair

int root(int dsu[],int x)
{
  while(dsu[x]!=x)
  {
    dsu[x]=dsu[dsu[x]];
    x=dsu[x];
  }
  return x;
}

void init(int dsu[], int n)
{
  for(int i=0;i<=n;i++)
  {
    dsu[i]=i;
  }
}

void un(int dsu[],int x,int y)
{
  int a=root(dsu,x);
  int b=root(dsu,y);
  dsu[a]=dsu[b];
}

void printprecise(double l,int precision){
    std::cout << std::fixed;
    std::cout << std::setprecision(precision);
    std::cout << l <<endl;
}

int gcd(int x,int y)
{
  if(x==0)
  {
    return y;
  }
  else
  {
    return gcd(y%x,x);
  }
}

int lcm(int x,int y)
{
  return (x*y)/gcd(x,y);
}

main() 
{

  
  int mod=1000000007;
  int h,w;
  cin>>h>>w;
  char arr[h][w];
  for(int i=0;i<h;i++)
  {
    for(int j=0;j<w;j++)
    {
      cin>>arr[i][j];
    }
  }
  int cst[h][w]={0};
  for(int i=0;i<h;i++)
  {
    for(int j=0;j<w;j++)
    {
      if(i==0&&j==0)
      {
        cst[i][j]=1;
        continue;
      }
      if(i==0||(j==0))
      {
        if(arr[i][j]=='#')
        {
          cst[i][j]=0;
        }
        else
        {
          if(i==0)
          {
            if(cst[i][j-1]==0)
            {
              cst[i][j]=0;
            }
            else
            {
              cst[i][j]=1;
            }
          }
          if(j==0)
          {
            if(cst[i-1][j]==0)
            {
              cst[i][j]=0;
            }
            else
            {
              cst[i][j]=1;
            }
          }
        }
      }
      else
      {
        if(arr[i][j]=='#')
        {
          cst[i][j]=0;
          continue;
        }
        cst[i][j]=(cst[i-1][j]+cst[i][j-1])%mod;
        // if(cst[i-1][j]!=-1)
        // {
        //   cst[i][j]=(cst[i][j]+cst[i-1][j])%mod;
        // }
        // if(cst[i][j-1]!=-1)
        // {
        //   cst[i][j]=(cst[i][j]+cst[i][j-1])%mod;
        // }
        // if(cst[i-1][j]==-1&&cst[i][j-1]==-1)
        // {
        //   cst[i][j]=-1;
        // }
      }
    }
  }
  // for(int i=0;i<h;i++)
  // {
  //   for(int j=0;j<w;j++)
  //   {
  //     cout<<cst[i][j]<<" ";
  //   }
  //   cout<<"\n";
  // }
  cout<<cst[h-1][w-1];



}

  // #ifndef ONLINE_JUDGE
  // cout << "\nTime Elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " s\n";
  // #endif
// }
// #ifndef ONLINE_JUDGE
// cout << "\nTime Elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " s\n";
// #endif

Measured memory_bytes: 9088
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
#include<limits.h>
#include<unordered_map>
#include<unordered_set>
#include<deque>
#include<cstdio>
using namespace std;
typedef long long int ll;
const int N = 1000000;
const int INF = 1 << 30;
#define rep(i,n) for(ll i=(ll)0;i<(ll)n;++i)
#define ALL(x) x.begin(),x.end()
int main() {
	int n, ct[100010] = {},mx=0;
	cin >> n;
	rep(i, n) {
		int nn; cin >> nn;
		ct[nn]++;
		if (nn > 0) { ct[nn - 1]++; mx = max(mx, ct[nn - 1]); }
		ct[nn + 1]++;
		mx = max({ mx,ct[nn],ct[nn + 1] });
	}
	cout << mx << endl;
	return 0;
}

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

typedef long long int ll;
typedef unsigned long long int ull;
#define rep(i,n) for(auto i=0;i<(n);i++)

using namespace std;


ll s(ll n){
    ll sum = 0;
    while(0 < n) sum += n%10, n /= 10;
    return sum;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    ll k;
    cin >> k;

    map<ll, double> ma;
    set<ll> keyset;
    for(ll i = 1; i < 10; i++){
        ma[i] = (double)i/(double)s(i);
        keyset.insert(i);
    }
    for(ll d = 1; d < 18; d++){
        ll p = pow(10, d-1);
        for(ll i = 1; i < (d-1)*10; i++){
            ll n = i*p + p-1;
            ma[n] = (double)n/(double)s(n);
            keyset.insert(n);
        }
    }
    
    ll cnt = 0;
    for(auto n : keyset){
        bool ok = true;
        for(auto m : keyset){
            if(n < m && ma[m] < ma[n]){
                ok = false;
                break;
            }
        }
        if(ok){
            cout << n << endl;
            cnt++;
        }
        if(cnt == k) break;
    }

    
    
    return 0;
}
	

Measured memory_bytes: 384
#pragma region template 2.4
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using pq_asc = priority_queue<T, vector<T>, greater<T>>;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP1(i, n) for (ll i = 1; i <= (n); ++i)
#define FOR(i, a) for (auto &i : a)
#define CH(f, x, y) x = f(x, y)
#define IN(T, x) \
    T x;         \
    cin >> x;
#define AIN(T, a, n) \
    vector<T> a(n);  \
    FOR(i, a)        \
    cin >> i;
#define A2IN(T1, a, T2, b, n) \
    vector<T1> a(n);          \
    vector<T2> b(n);          \
    REP(i, n)                 \
    cin >> a[i] >> b[i];
#define OUT(x) cout << (x) << endl;
#define FOUT(x) cout << fixed << setprecision(15) << (x) << endl;
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) \
    SORT(a);     \
    reverse(ALL(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define DUMPA(a)          \
    cout << #a << " = {"; \
    JOUT(ALL(a), ", ", cout) << "}" << endl;

template <typename T>
ostream &JOUT(T s, T e, string sep = " ", ostream &os = cout)
{
    if (s != e)
    {
        os << *s;
        ++s;
    }
    while (s != e)
    {
        os << sep << *s;
        ++s;
    }
    return os;
}

ostream &YES(bool cond, string yes = "Yes", string no = "No", ostream &os = cout)
{
    if (cond)
    {
        os << yes << endl;
    }
    else
    {
        os << no << endl;
    }
    return os;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p)
{
    os << '(' << p.first << ", " << p.second << ')';
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << '[';
    JOUT(ALL(v), ", ", os) << ']';
    return os;
}

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#pragma endregion template

int main()
{
    IN(ll, N);
    IN(ll, M);
    ll a = 1;
    ll b = M + 1;
    REP1(i, (M + 1) / 2)
    {
        cout << a << ' ' << b << endl;
        ++a;
        --b;
    }
    a = M + 2;
    b = a + M - 1;
    REP1(i, M / 2)
    {
        cout << a << ' ' << b << endl;
        ++a;
        --b;
    }
}


Measured memory_bytes: 3600
MOD = int(1e9) + 7

def main():
    buf = input()
    buflist = buf.split()
    N = int(buflist[0])
    M = int(buflist[1])
    buf = input()
    buflist = buf.split()
    A = list(map(int, buflist))
    buf = input()
    buflist = buf.split()
    B = list(map(int, buflist))

    A = list(reversed(list(sorted(A))))
    B = list(reversed(list(sorted(B))))
    A.append(0) # sentinel
    B.append(0) # sentinel
    pattern_count = 1
    A_pointer = 0
    B_pointer = 0
    free_count = 0
    for i in range(N * M, 0, -1):
        if i == A[A_pointer] or i == B[B_pointer]:
            if i == A[A_pointer] and i == B[B_pointer]:
                free_count += A_pointer + B_pointer
                A_pointer += 1
                B_pointer += 1
            elif i == A[A_pointer]:
                free_count += B_pointer - 1
                pattern_count *= B_pointer
                A_pointer += 1
            else:
                free_count += A_pointer - 1
                pattern_count *= A_pointer
                B_pointer += 1
        elif free_count == 0:
            print(0) # impossible
            return
        else:
            pattern_count *= free_count
            free_count -= 1
        pattern_count %= MOD
    print(pattern_count)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3188
//#include "pch.h"
#include <iostream>
#include <vector>
using namespace std;
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define REF(i, s, e) for(int i=s; i>e; i--)

class UnionFind {
public:
	//親の番号を格納する。親だった場合は-(その集合のサイズ)
	vector<int> Parent;

	//作るときはParentの値を全て-1にする
	//こうすると全てバラバラになる
	UnionFind(int N) {
		Parent = vector<int>(N, -1);
	}

	//Aがどのグループに属しているか調べる
	int root(int A) {
		//cout << "root in" << endl;
		//cout << "Parent[A]:" << Parent[A] << endl;
		if (Parent[A] < 0) return A;
		return Parent[A] = root(Parent[A]);
	}

	//自分のいるグループの頂点数を調べる
	int size(int A) {
		return -Parent[root(A)];//親をとってきたい
	}

	//AとBをくっ付ける
	bool connect(int A, int B) {
		//AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
		A = root(A);
		B = root(B);
		if (A == B) {
			//すでにくっついてるからくっ付けない
			return false;
		}

		//大きい方(A)に小さいほう(B)をくっ付けたい
		//大小が逆だったらひっくり返しちゃう。
		if (size(A) < size(B)) swap(A, B);

		//Aのサイズを更新する
		Parent[A] += Parent[B];
		//Bの親をAに変更する
		Parent[B] = A;

		return true;
	}
};

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

	int N, M;
	cin >> N >> M;

	vector<int> A(M), B(M);

	FOR(i,0,M) {
		cin >> A[i] >> B[i];
		A[i]--;
		B[i]--;
	}
	//cout << "Input" << endl;
	//FOR(i, 0, M) cout << A[i] << " " << B[i] << endl;

	vector<long long> ans(M);
	ans[M - 1] = (long long)N * (N - 1) / 2;
	
	UnionFind uni(N);

	REF(i,M-1,0) {
		//cout << "A,B: " << A[i] << " " << B[i] << endl;

		//cout << "Parent" << endl;
		//FOR(i,0,N) cout << uni.Parent[i] << endl;
		//cout << "root(A)" << uni.root(A[i]) << endl;
		//cout << "root(B)" << uni.root(B[i]) << endl;
		//cout << "size(A)" << uni.size(A[i]) << endl;
		//cout << "size(B)" << uni.size(B[i]) << endl;

		//つながってなかったのがつながったとき
		if (uni.root(A[i]) != uni.root(B[i])) {
			ans[i - 1] = ans[i]
				- (long long)uni.size(A[i]) * uni.size(B[i]);
			uni.connect(A[i], B[i]);

		}
		else ans[i - 1] = ans[i];
	}

	FOR(i, 0, M) {
		cout << ans[i] << endl;
	}

}



Measured memory_bytes: 3328
#include <iostream>
#include <algorithm>
#include <complex>
#include <vector>
using namespace std;

typedef long long LL;
typedef complex< LL > Point;
typedef complex< LL > Vector;
const LL kCrn = 100000;

int N;
vector< Point > shp, core;

void read_shape(void);
void solve(void);
bool ln_sgm_intr(Point, Point, Point, Point);
Point find_sgm_intr(Point, Point, Point, Point);

inline LL cross(Vector u, Vector v) { return imag(conj(u) * v); }

int main() {
  while (cin >> N, N) {
    read_shape();
    solve();
  }

  return 0;
}

void read_shape(void) {
  shp.clear();
  for (int i = 0; i < N; ++i) {
    int x, y;
    cin >> x >> y;
    shp.push_back(Point(x, y));
  }
}

void solve(void) {
  core.clear();
  core.push_back(Point(kCrn, kCrn)), core.push_back(Point(-kCrn, kCrn));
  core.push_back(Point(-kCrn, -kCrn)), core.push_back(Point(kCrn, -kCrn));

  for (int i = 0; i < N; ++i) {
    vector< Point > tmp;
    Point &p1 = shp[i], &p2 = shp[(i + 1) % N];

    if (core.size() == 1) {
      if (cross(p2 - p1, core[0] - p1) >= 0)
        tmp.push_back(core[0]);
    }
    else if (core.size() >= 2) {
      for (int j = 0; j < core.size(); ++j) {
        Point &p3 = core[j], &p4 = core[(j + 1) % core.size()];

        if (cross(p2 - p1, p3 - p1) >= 0) tmp.push_back(p3);
        if (core.size() != 2 || j != 1) {
          if (ln_sgm_intr(p1, p2, p3, p4))
            tmp.push_back(find_sgm_intr(p1, p2, p3, p4));
        }
      }
    }

    core = tmp;
  }

  cout << int(core.size() > 0) << "\n";
}

bool ln_sgm_intr(Point p1, Point p2, Point p3, Point p4) {
  return cross(p3 - p1, p2 - p1) * cross(p4 - p1, p2 - p1) < 0;
}

Point find_sgm_intr(Point p1, Point p2, Point p3, Point p4) {
  Vector A = p2 - p1, B = p4 - p3, S = p3 - p1;
  return p1 + A * cross(S, B) / cross(A, B);
}

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

const int all = (1 << 7) - 1;

string c;

int t[5][5];
int u[3][3];

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

int calc1(int x, int y) {
	int val = 0;
	for (int i = 0; i < 7; i++) {
		val |= t[x + dx[i]][y + dy[i]] << i;
	}
	return c[val] - '0';
}

int calc2(int x, int y) {
	int val = 0;
	for (int i = 0; i < 7; i++) {
		val |= u[x + dx[i]][y + dy[i]] << i;
	}
	return c[val] - '0';
}

int main()
{
	while (cin >> c, c != "#") {
		bool ok = true;
		int off[] = { 0, 0, 0, 1, 2 };
		int cnt[] = { 3, 4, 5, 4, 3 };
		for (int i = 0; i < (1 << 19); i++) {
			for (int j = 0, k = 0, l = 0; j < 19; j++) {
				t[off[k] + l][k] = (i >> j) & 1;
				++l;
				if (l == cnt[k]) {
					l = 0;
					++k;
				}
			}
			bool flag = false;
			for (int x = 1; x < 4; x++) {
				for (int y = 1; y < 4; y++) {
					u[x - 1][y - 1] = calc1(x, y);
					if (u[x - 1][y - 1] != t[x][y]) {
						flag = true;
					}
				}
			}
			if (!flag) continue;
			if (calc2(1, 1) != u[1][1]) {
				ok = false;
			}
		}
		puts(ok ? "yes" : "no");
	}
	return 0;
}



Measured memory_bytes: 3000
def main():
    n,k = map(int,input().split()) 
    x = list(map(int,input().split()))
    m=10**11
    for i in range(n-k+1):
        if x[i]>0:
            m=min(x[i+k-1],m)
        elif x[i+k-1]<0:
            m=min(m,-x[i])
        else:
            m=min(m,x[i+k-1]-x[i]+x[i+k-1],x[i+k-1]-2*x[i])
    print(m)
    
if __name__ == "__main__":
    main()

Measured memory_bytes: 62576
#include <bits/stdc++.h>
using namespace std;
#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--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

int main() {
    int ans = 0;
    int n;
    ll k;
    cin >> n >> k;
    rep(d, 40) {
        ll now = 1;
        rep(i, d) now *= k;
        if (now > n) {
            cout << d << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=(ll)1e9+7;
const ll INF=(ll)1e18+10;

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

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

    vector<int> x(N),y(N),pat(N);
    int p=1;

    for (int i = 0; i < N; ++i) {
        cin>>x[i]>>y[i];
        pat[i]=i;
        p*=(i+1);
    }

    double ans=0.0;

    do{

        double tmp=0.0;
        for (int i = 0; i < N - 1; ++i) {
            tmp+=sqrt(pow(x[pat[i]]-x[pat[i+1]],2)+pow(y[pat[i]]-y[pat[i+1]],2));
        }
        ans+=tmp;

    }while(next_permutation(pat.begin(),pat.end()));

    ans/=(double)p;

    printf("%.10f\n",ans);

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/



typedef long long ll;
int N, A[101010], B[101010], C[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> B[i];
    rep(i, 0, N) cin >> C[i];
    sort(A, A + N);
    sort(C, C + N);

    ll ans = 0;
    rep(b, 0, N) {
        ll a = lower_bound(A, A + N, B[b]) - A;
        ll c = N - (upper_bound(C, C + N, B[b]) - C);
        ans += a * c;
    }
    cout << ans << endl;
}

Measured memory_bytes: 1408
import array
import collections
import heapq
 
 
AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
MAX_INT = 2147483647
NO_V = -1
 
 
def compute_mst_prim(v, adj_list):
    pred = collections.defaultdict(lambda: NO_V)
    key = collections.defaultdict(lambda: MAX_INT)
    key[0] = 0
    pq = [(key[i], i) for i in range(v)]
    heapq.heapify(pq)
    in_pq = array.array("B", (True for tmp in range(v)))
    while pq:
        tmp, u = heapq.heappop(pq)
        in_pq[u] = False
        for i, cost in adj_list[u]:
            if in_pq[i]:
                weight = cost
                if weight < key[i]:
                    pred[i] = u
                    key[i] = weight
                    heapq.heappush(pq, (weight, i))
                    in_pq[i] = True
    return pred, key
 
 
if __name__ == '__main__':
    v, e = map(int, input().split())
    a_list = collections.defaultdict(set)
    for _ in range(e):
        s, t, w = map(int, input().split())
        a_list[s].add(AdjacentVertex(t, w))
        a_list[t].add(AdjacentVertex(s, w))
    tmp , key = compute_mst_prim(v, a_list)
    print(sum(key.values()))
 



Measured memory_bytes: 50280
#include <vector>
#include <queue>
#include <cstdio>
using namespace std;

typedef long long Weight;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

Graph opt; //optimal edges for minimum-spanning
vector<vector<int>> max_edge;
Weight minimumSpanningForest(const Graph &g) {
  int n = g.size();
  priority_queue<Edge> Q;
  for(int u=0;u<n;u++) for(auto &e: g[u]) /*if (u < e->dst)*/ Q.push(e);
  UnionFind uf(n);

  Weight total = 0;
  Edges F;
  while (F.size() < n-1 && !Q.empty()) {
    Edge e = Q.top(); Q.pop();
    if (uf.unionSet(e.src, e.dst)) {
      F.push_back(e);
      total += e.weight;
      opt[e.src].emplace_back(e.src,e.dst,e.weight);
      opt[e.dst].emplace_back(e.dst,e.src,e.weight);
    }
  }
  return total; //pair<Weight, Edges>(total, F);
}

void dfs(int z,int c,long long k,vector<int>&v){
	max_edge[z][c]=k;
	v[c]=1;
	for(auto &e:opt[c])if(!v[e.dst])dfs(z,e.dst,max(k,e.weight),v);
}

int main(){
	int N,M,Q,a,b,c;
	scanf("%d%d",&N,&M);
	opt.resize(N);
	Weight w;
	{
		Graph g(N);
		for(;M--;){
			scanf("%d%d%d",&a,&b,&c);
			g[a-1].emplace_back(a-1,b-1,c);
		}
		w=minimumSpanningForest(g);
	}
	max_edge.resize(N);
	for(int i=0;i<N;i++)max_edge[i].resize(N);
	for(int i=0;i<N;i++){
		vector<int>v(N);
		dfs(i,i,0,v);
	}
	scanf("%d",&Q);
	for(;Q--;){
		scanf("%d%d",&a,&b);
		printf("%lld\n",w-max_edge[a-1][b-1]);
	}
}

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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;

#define INF INT_MAX/3

#define MAX_N 1000

int dfs(int n,int k,int l,int s){
	//dbg(k); dbg(l); dbg(s);
	if(k==0&&s==0)return 1;
	if(s<0||k*n<s)return 0;
	int res=0;
	repl(i,l,n+1){
		res+=dfs(n,k-1,i+1,s-i);
	}
	return res;
}

int n,k,s;
int main(){
	cin.sync_with_stdio(false);
	while(1){
		cin>>n>>k>>s;
		if(n==0)break;
		cout<<dfs(n,k,1,s)<<endl;
	}
	return 0;
}

Measured memory_bytes: 3016
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

namespace ConsoleAppAtCoderABC171
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(ReadLine());
            var a = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();

            var xor1 = a.Skip(1).Aggregate((s, e) => s ^ e);
            Write($"{xor1} ");

            for (int i = 1; i < n; i++)
            {
                var xor = a[0] ^ a[i] ^ xor1;
                Write($"{xor} ");
            }
        }
    }
}


Measured memory_bytes: 62116
#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i<r;i++)
#define vi vector<int>
#define all(v) v.begin(),v.end()
#define pb(c) push_back(c)
#define vii vector<pair<int,int>>
#define ii pair<int,int>
#define max(a, b) (((a)<(b))?b:a)
#define min(a, b) ((a>b)?b:a)
#define mp(i, j) make_pair(i,j)
#define ull unsigned long long int
#define ll  long long int
#define pi 3.141592653589793238
#define inf ((ll)1e18)
#define eps 1e-14
#define mod ((int)1e9+7)
#define maxlg 18
#define left(i) ((i)<<1)
#define right(i) (((i)<<1)+1)
#define maxn 200006

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifndef ONLINE_JUDGE
 #endif
    string s;
    cin>>s;
    int ans = s.length();
    vi p0,p1;
    int n=s.length();
    rep (i,0,s.length()-1) {
        if (s[i]!=s[i+1]) {
            ans = min(ans,max(i+1,n-(i+1)));
        }
    }
     cout<<ans;




    return 0;
}

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

int ctoi(char c) {
    int n = c - '0';
    return n;
}

int pow_int(int x, int n) {
    if (n == 0) {
        return 1;
    }else {
        int y = x;
        for (int i = 0; i < n-1; i++) {
            x *= y;
        }
        return x;
    }
}


int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(m);
    rep(i, m) cin >> a[i];
    int sum = 0;
    rep(i, m) sum += a[i];
    if (sum <= n) {
        cout << n - sum << endl;
    }else {
        cout << "-1" << endl;
    }
}


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

int main() {
  string c;
  cin>>c;
  
  if( c=="a"){
    cout<<"vowel"<<endl;
  }
  else if( c=="i"){
    cout<<"vowel"<<endl;
  }
  else if( c=="u"){
    cout<<"vowel"<<endl;
  }
  else if( c=="e"){
    cout<<"vowel"<<endl;
  }
  else if( c=="o"){
    cout<<"vowel"<<endl;
  }
  else{
    cout<<"consonant"<<endl;
  }
  
}


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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

ll h, w, n;
map<pii, bool> m;
set<pii> vis;

ll cnt[10];

int main() {
	cin.tie(0)->sync_with_stdio(0);
    cin >> h >> w >> n;
    rep(i, 0, n) {
        int a, b;
        cin >> a >> b;
        m[{a, b}] = true;
    }

    for (auto point : m) {
        int x = point.first.first, y = point.first.second;
        rep(i, x - 1, x + 2) {
            rep(j, y - 1, y + 2) {
                if (i < 2 || j < 2 || i >= h || j >= w) continue;
                if (vis.find({i, j}) != vis.end()) continue;

                int found = 0;
                rep(ii, -1, 2) {
                    rep(jj, -1, 2) {
                        if (m.find({i + ii, j + jj}) != m.end()) ++found;
                    }
                }

                vis.insert({i, j});
                ++cnt[found];
                // cout << i << ' ' << j << ' ' << found << '\n';
            }
        }
    }

    cnt[0] = (h - 2) * (w - 2);
    rep(i, 1, 10) cnt[0] -= cnt[i];
    rep(i, 0, 10) cout << cnt[i] << '\n';
}


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

int main(){
  int N;
  cin >> N;
  
  int ans=0;
  if(N%1000 == 0){
    ans = 0;
  }
  else {
    ans = 1000 - (N%1000);
  }
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3612
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <stdlib.h>



int main()
{
  int cnt;
  int A,B,C;

  cnt = scanf("%d %d %d", &A, &B, &C);

  if ((A == B) &&
      (B == C) &&
      (C == A)) {
    printf ("Yes");
  } else {
    printf ("No");
  }

  return 0;
}


Measured memory_bytes: 128
import { readFileSync } from "fs";

const read = () =>
  readFileSync(0, "utf8")
    .split("\n")
    .map((line) => line.split(" "));

const main = (input: string[][]) => {
  const [X] = input[0].map(Number);
  const P = input[1].map(Number);

  let num = 0;
  let min = 1000;
  for (let i = 0; i <= 101; i++) {
    if (P.includes(i)) {
      continue;
    }

    const diff = Math.abs(X - i);

    if (diff < min || (diff === min && i < num)) {
      num = i;
      min = diff;
    }
  }

  return num;
};

console.log(main(read()));


Measured memory_bytes: 29616
n = int(input())
s = list(input())
list = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
moji = ''

for i in range(len(list)):
  list[i] = list[i].upper()

for i in range(len(s)):
  num = list.index(s[i])
  s[i] = list[num + n]
  moji = moji + s[i]
  
print(moji)

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

int main(){
    int n, a, i, c, res = 0;
    cin >> n;
    for(i=0; i<n; i++){
        cin >> a;
        c = 0;
        while(a%2 == 0){
            a /= 2;
            c++;
        }
        res += c;
    }
    cout << res;
    return 0;
}

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

int main() {
	// your code goes here
	long long k,A,B;
	cin>>k>>A>>B;
	
	long long b = 1;
	
	if(k>=A-b && (B-A)>1)
	{
		k = k-(A-b);
		//cout<<k<<endl;
		b =A;
		
		//cout<<b<<endl;
		//cout<<(B-A) * (k/2)<<endl;
		b=b + ((B-A) * (k/2));
		//cout<<b<<endl;
		b+=(k%2);
	}
	else
	{
		b = b+k;
		k = 0;
	}
	cout<<b;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main (void)

{
  int A,B,K,Areturn,l;
  scanf ("%d %d %d",&A,&B,&K);


  if (K%2==1)
  {
  Areturn=(K-1)/2;
  for (l=1;l<=Areturn;l++)
  {
  /*高橋*/
    if (A%2==1)
    {
      A--;
      A=A/2;
      B=B+A;
    }
    else
    {
      A=A/2;
      B=B+A;
    }
  /*青木*/
    if (B%2==1)
    {
      B--;
      B=B/2;
      A=A+B;
    }
    else
    {
      B=B/2;
      A=A+B;
    }
  }
  if (A%2==1)
  {
    A--;
    A=A/2;
    B=B+A;
  }
  else
  {
    A=A/2;
    B=B+A;
  }
  }
  else
  {
  Areturn=K/2;
  for (l=1;l<=Areturn;l++)
  {
    /*高橋*/
      if (A%2==1)
      {
        A--;
        A=A/2;
        B=B+A;
      }
      else
      {
        A=A/2;
        B=B+A;
      }
    /*青木*/
      if (B%2==1)
      {
        B--;
        B=B/2;
        A=A+B;
      }
      else
      {
        B=B/2;
        A=A+B;
      }
    }
  }
  printf("%d %d\n",A,B);

  return 0;
}


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

int main(){
    cin.tie(0);
	ios::sync_with_stdio(false);
    long long int n,m,x,c=0, temp;
    cin>>n>>m>>x;
	temp= m/x - n/x;
    temp+= (n%x==0); 
    cout<<temp;
    
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
	//freopen("in.txt","r",stdin);
	int n,k,ans=0;
	scanf("%d%d",&n,&k);
	while(n) {
		n/=k;
		ans++;
	}
	printf("%d\n",ans);
	return 0;
}


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

using namespace std;

int g[3][105];

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

    int n;
    cin >> n;

    for(int i=1; i<=2; i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>g[i][j];
            g[i][j]+= max(g[i-1][j], g[i][j-1]);
        }
    }
    cout<<g[2][n]<<endl;

    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(isr);
		
		String buf = br.readLine();
		StringBuffer sb = new StringBuffer(buf);
		System.out.println(sb.reverse());
	}
}

Measured memory_bytes: 24200
#include <stdio.h>

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

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define vec vector
#define sz(x) ((int) x.size())
#define rd(type, ...) type __VA_ARGS__; sc(__VA_ARGS__)
#define rdv(type, v, n) vector<type> v(n); rep(i, 0, n) cin >> v[i]
#define prv(v) rep(i, 0, v.size()) {if (i) cout << ' '; cout << v[i];} cout << '\n'
#define rdm(type, v, h, w) vector<vector<type>>(h, vector<type>(w)) v; rep(i, 0, h) rep(j, 0, w) cin >> v[i][j]
#define prm(v) rep(i, 0, v.size()) {rep(j, 0, v[i].size()) {if (j) {cout << ' ';} cout << v[i][j];} cout << '\n';}
typedef long long ll;
void solve();
int main() {ios::sync_with_stdio(false); cin.tie(0); solve(); return 0;}
template<typename T> void sc(T& x) {cin >> x;}
template<typename Head, typename... Tail> void sc(Head& head, Tail&... tail) {cin >> head; sc(tail...);}
template<typename T> void pr(const T& x) {cout << x << '\n';}
template<typename Head, typename... Tail> void pr(const Head& head, const Tail&... tail) {cout << head << ' '; pr(tail...);}

void solve() {
  rd(int, n);
  rdv(int, a, n);
  int sum = accumulate(a.begin(), a.end(), 0);
  int ans = 2e9;
  int cur = 0;
  rep(i, 0, n) {
    sum -= a[i];
    cur += a[i];
    ans = min(ans, abs(sum - cur));
  }
  pr(ans);
}

Measured memory_bytes: 256
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


//3次元
struct Point{
	Point(double arg_x,double arg_y,double arg_z){
		x = arg_x;
		y = arg_y;
		z = arg_z;
	}

	Point(){
		x = y = z = 0.0;
	}

	Point operator + (Point p){ return Point(x+p.x,y+p.y,z+p.z); }
	Point operator - (Point p){ return Point(x-p.x,y-p.y,z-p.z);}
	Point operator * (double a){ return Point(a*x,a*y,a*z); }
	Point operator / (double a){ return Point(x/a,y/a,z/a); }

	double abs(){ return sqrt(norm()); }
	double norm(){ return x*x + y*y + z*z; }

	bool operator == (const Point &p) const{
		return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS && fabs(z-p.z) < EPS;
	}
	double x,y,z;
};

typedef Point Vector;

struct Line{
	Line(Point a,Point b){
		p[0] = a;
		p[1] = b;
	}
	Point p[2];
};

struct Info{
	Point center;
	double r;
	ll value;
};

int N,Q;
Info info[50];

double calc_dist(Point a,Point b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
}

bool intersect(Line line,int index){

	double dist_1 = calc_dist(line.p[0],info[index].center);
	double dist_2 = calc_dist(line.p[1],info[index].center);

	//方向ベクトル
	double Vx = line.p[1].x-line.p[0].x;
	double Vy = line.p[1].y-line.p[0].y;
	double Vz = line.p[1].z-line.p[0].z;

	//Oを原点,点Aをline.p[0]としたとき、点info[inde]から下した垂線との交点が、(line.p[0].x+t*Vx,line.p[0].y+t*Vy,line.p[0].z+t*Vz)と表されるようなt
	double t = (Vx*(info[index].center.x-line.p[0].x)+Vy*(info[index].center.y-line.p[0].y)+Vz*(info[index].center.z-line.p[0].z))/(Vx*Vx+Vy*Vy+Vz*Vz);

	if(t < 0 || t > 1){ //垂線が、観測点と光源を結ぶ線分上にない場合→最近地点は、観測点か光源のどちらか
		if(dist_1 > info[index].r && dist_2 > info[index].r){
			return false;
		}else{
			return true;
		}
	}

	double cross_x = line.p[0].x+t*Vx;
	double cross_y = line.p[0].y+t*Vy;
	double cross_z = line.p[0].z+t*Vz;

	double dist = sqrt((info[index].center.x-cross_x)*(info[index].center.x-cross_x)
			+(info[index].center.y-cross_y)*(info[index].center.y-cross_y)
			+(info[index].center.z-cross_z)*(info[index].center.z-cross_z)
		);

	if(dist < info[index].r+EPS){
		return true;
	}else{
		return false;
	}
}

int main(){

	scanf("%d %d",&N,&Q);

	for(int i = 0; i < N; i++){
		scanf("%lf %lf %lf %lf %lld",&info[i].center.x,&info[i].center.y,&info[i].center.z,&info[i].r,&info[i].value);
	}

	Point a,b;
	ll ans;
	for(int loop = 0; loop < Q; loop++){
		scanf("%lf %lf %lf %lf %lf %lf",&a.x,&a.y,&a.z,&b.x,&b.y,&b.z);
		ans = 0;
		Line line(a,b);
		for(int i = 0; i < N; i++){
			if(intersect(line,i))ans += info[i].value;
		}

		printf("%lld\n",ans);
	}

	return 0;
}




Measured memory_bytes: 3244
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
typedef long long LL;
using namespace std;
LL a , b;
int main()
{
	while(~scanf("%lld%lld" , &a , &b)){
		if(llabs(a - b) <= 1) printf("Brown\n");
		else printf("Alice\n");
	}
}

Measured memory_bytes: 128
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <limits>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <map>
#include <tuple>

#define INF 100100100100
#define rep(i,n) for(int i=0; i<(n); i++)
typedef long long ll;
using namespace std;

#define mod 998244353
 
int main(){
    int n,k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    n--; k--;
    int ans = (n+k-1)/k;
    cout << ans << endl;
    
    
    

}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const ll INF = 1e18;
const long double EPS = 1e-10;

int main() {
  int n;
  cin >> n;
  string s, t;
  cin >> s >> t;
  
  rep(i, n) cout << s[i] << t[i];
  cout << endl;


  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>
#include <utility>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define ll long long
#define P pair<int, int>

using namespace std;
int mod = 1000000007;

int N;

int main() {
  cin >> N;
  vector<int> a(N);
  rep(i, N) {
    cin >> a.at(i);
  }
  int ans = INT_MAX;
  for(int i=-100; i<=100; i++) {
    int now = 0;
    rep(j, N) {
      now += (a.at(j) - i)*(a.at(j) - i);
    }
    ans = min(ans, now);
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main{
  public static void main(String[] args){
	  Scanner sc = new Scanner(System.in);
	  int n=sc.nextInt();
	  Map<Long,Long> map=new TreeMap<>();
	  long s=0;
	  for(int i=0;i<n;i++) {
		  long key=sc.nextLong();
		  if(map.containsKey(key)) {
			  map.put(key, map.get(key)+1);
		  }else {
			  map.put(key, 1L);
		  }
		  s+=key;
	  }
	  int q=sc.nextInt();
	  for(int i=0;i<q;i++) {
		  long buff=0;
		  long b=sc.nextLong(),c=sc.nextLong();
		  if(map.containsKey(b)) {
			  if(map.containsKey(c)) {
				  map.put(c, map.get(b)+map.get(c));
				  buff=(c-b)*map.get(b);
				  map.put(b,0L);
			  }else {
				  map.put(c, map.get(b));
				  buff=(c-b)*map.get(b);
				  map.put(b,0L);
			  }
		  }
		  s+=buff;
		  System.out.println(s);
	  }
  }
}



Measured memory_bytes: 69516
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=a;i<b;i++)
#define fore(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define INF ll(1e18)
///#define MOD 998244353
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

#define MAXN 1000000007

int main() {
	ll n;
	string s;
	ll a=0,w=0,t=0,r=0;
	cin>>n;
	for (ll i=0;i<n;i++) {
		cin>>s;
		if (s=="AC") a++;
		if (s=="WA") w++;
		if (s=="TLE") t++;
		if (s=="RE") r++;
	}
	cout<<"AC x "<<a<<"\n";
	cout<<"WA x "<<w<<"\n";
	cout<<"TLE x "<<t<<"\n";
	cout<<"RE x "<<r<<"\n";
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define ALL(obj) obj.begin(),obj.end()
#define pb(obj) push_back(obj)
#define REP(i,N) for(int i=0;i<N;i++)
typedef long long ll;
int main(){
	cin.tie(0);
    ios::sync_with_stdio(false);
	int D;
	ll G;
	cin>>D>>G;
	vector<int>p(D),c(D);
	for(int i=0;i<D;i++){
		cin>>p[i]>>c[i];
	}
	ll sum;
	ll num;
	int itr;
	ll m=100000;
	for(int bit=0;bit<(1<<D);bit++){
		sum=0,num=0;itr=-1;
		for(int i=0;i<D;i++){
			if(bit&(1<<i)){
				sum+=c[i]+(i+1)*100*p[i];
				num+=p[i];
			}
			else itr=i;
		}
		if(itr==-1){
			m=min(m,num);
			continue;
		}
		int left=-1;
		int right=p[itr];
		while(right-left>1){
			int mid=(left+right)/2;
			if(sum+mid*(itr+1)*100>=G)right=mid;
			else left=mid;
		}
		if(right!=p[itr])m=min(num+right,m);
	}
	cout<<m<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    while(cin>>a>>b,a||b){
      for(int i=0;i<a;i++){
	if(i%2==0){
	  for(int j=0;j<b;j++){
	    if(j%2==0){
	      cout<<"#";
	    }
	    else
	      cout<<".";
	  }
	}
	  else{
	    for(int j=0;j<b;j++){
	      if(j%2==0){
		cout<<".";
	      }
	      else
		cout<<"#";
	    }
	  }
	cout<<endl;
      }
      cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 3088
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())
def NIJIGEN(H): return [list(input()) for i in range(H)]
def dfs(j):
  if j not in finish:
    finish.add(j)
    for k in L[j]:
      dfs(k)
N,M=MAP()
s=list()
L=[[] for _ in range(N)]
for i in range(M):
  a,b=MAP()
  a-=1
  b-=1
  L[a].append(b)
  L[b].append(a)
  s.append([a,b])
ans=0
for i in range(M):
  a,b=s[i]
  L[a].remove(b)
  L[b].remove(a)
  finish=set()
  dfs(a)
  if len(finish)!=N:
    ans+=1
  L[a].append(b)
  L[b].append(a)
print(ans)

Measured memory_bytes: 9268
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using st=string;
using ch=char;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<ch> vc;
typedef vector<vc> vvc;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(ll i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
#define pb push_back
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
st abc="abcdefghijklmnopqrstuvwxyz";
st ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct edge{ll to,cost;};
struct edge2{ll from,to,cost;};


int main() {
    ll D;
    cin >> D;
    vl c(26);
    rep(i,26){
        cin >> c[i];
    }
    ll s[D][26];
    rep(i,D){
        rep(j,26){
            cin >> s[i][j];
        }
    }
    vl latest_t(26,0);
    ll k=0;
    vl answer(D);
    FOR(i,1,D+1){
        vl nt=latest_t;
        ll nk=k;
        ll MX=-INF;
        ll ans;
        rep(j,26){
            nt=latest_t;
            nk=k;
            nk+=s[-1+i][j];
            nt[j]=i;
            rep(l,26){
                nk-=c[l]*(i-nt[l]);
            }
            if(nk>MX){
                MX=nk;
                ans=j;
            }
            if(j==25){
                k=MX;
            }
        }
        //cout << ans+1 << endl;
        answer[-1+i]=ans+1;
        latest_t[ans]=i;
    }
    //rep(i,D){
      //  cout << answer[i] << endl;
    //}
    rep(i,2*pow(10,1)){
        int x=rand();
        x%=D-1;
        vl n_answer=answer;
        swap(n_answer[x],n_answer[x+1]);
        if(s[x][n_answer[x]]+s[x+1][n_answer[x+1]]>s[x][answer[x]]+s[x+1][answer[x+1]]){
            answer=n_answer;
        }
    }
    rep(i,D){
        cout << answer[i] << endl;
    }
}


Measured memory_bytes: 3716
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
#include <cstdio>
#include <tuple>
#include <string>
#include <vector> 
#include <set>
#include <string.h>
#include <map>
#include <cmath>
#include <deque>
using ll = long long;
using Graph = vector<vector<int>>;
#include <queue>
#include <stack>
#include <math.h>  /* M_PI */

const ll MOD = 1000000007;
int main(){

    ll n,k;
    cin >> n >> k;

    ll cnt = 0;
    for(ll i =k;i <= n + 1;i++){
        ll a = i % 2 == 0 ? i / 2 * (i -1): (i-1)/2 * i;
        ll b = i % 2 == 0 ? i / 2 * (2 * n -i +1):(2 * n-i+1)/2 * i;
        ll t = b - a + 1;
        cnt = (cnt + t) % MOD;
    }

    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 3168
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>

using namespace std;

template <typename T>
struct segtree{
    int n;
    T UNIT;
    vector<T> dat;
    segtree(int n_, T unit){
        UNIT = unit;
        n = 1;
        while(n < n_) n *= 2;
        dat = vector<T>(2*n);
        for(int i = 0; i < 2*n; i++) dat[i] = UNIT;
    }

    T calc(T a, T b){
        T ans;
        ans = max(a, b);
        return ans;
    }
    void insert(int k, T a){
        dat[k+n-1] = a;
    }
    void update_all(){
        for(int i = n-2; i >= 0; i--){
            dat[i] = calc(dat[i*2+1], dat[i*2+2]);
        }
    }
    //k番目の値(0-indexed)をaに変更
    void update(int k, T a){
        k += n-1;
        dat[k] = a;
        while(k > 0){
            k = (k-1)/2;
            dat[k] = calc(dat[k*2+1], dat[k*2+2]);
        }
    }

    //[a, b)
    //区間[a, b]へのクエリに対してはquery(a, b+1, 0, 0, segtree.n)と呼ぶこと
    T query(int a, int b, int k, int l, int r){
        if(r <= a || b <= l) return UNIT;
        if(a <= l && r <= b) return dat[k];
        else{
            T vl = query(a, b, k*2+1, l, (l+r)/2);
            T vr = query(a, b, k*2+2, (l+r)/2, r);
            return calc(vl, vr);
        }
    }
};

int h[200000];
long a[200000];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    long ans = 0;
    int N;
    cin >> N;
    segtree<long> sgt(N, 0);
    for(int i = 0; i < N; i++) cin >> h[i];
    for(int i = 0; i < N; i++) cin >> a[i];
    for(int i = 0; i < N; i++){
        h[i]--;
        long tmp = sgt.query(0, h[i], 0, 0, sgt.n);
        sgt.update(h[i], tmp+a[i]);
        ans = max(ans, tmp+a[i]);
        //cout << tmp+a[i] << endl;
    }
    cout << ans << endl;
}

Measured memory_bytes: 6656