akhauriyash/Code-Regression huggingface dataset:
from collections import deque

N, M = map(int,input().split())
side = [[]for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    side[a-1].append(b-1)
    side[b-1].append(a-1)
node = [-1]*N
node[0] = 1
queue = deque([0])
while queue:
    q = queue.popleft()
    for i in side[q]:
        if node[i] == -1:
            node[i] = (node[q]+1)%2
            queue.append(i)
        elif node[i] == node[q]:
            print((N*(N-1))//2 - M)
            exit()
zerone = [0, 0]
for i in node:
    zerone[i] += 1
print(zerone[0] * zerone[1] - M)





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

using namespace std;

string make_str(int n, int loop) {
    ostringstream oss;
    for (int i=0; i<loop; ++i)
        oss << n;
    return oss.str();
}

string solve(int a, int b) {
    string stra = make_str(a,b);
    string strb = make_str(b,a);
    if (stra <= strb)
        return stra;
    else
        return strb;
}

int main() {
    int a,b;
    cin >> a >> b;
    cout << solve(a,b);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define fast ios::sync_with_stdio(false); cin.tie(NULL);
const double eps = 1e-6;



/////////////////////////////////////////////

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

////////////////////////////////

//#define int long long
const int mod = 998244353;
const int N = 3001;
int dp[N][N];
void solve(){

	int n , s;
	cin>>n>>s;
	int a[n];
	for(int i = 0; i < n ; ++i)
		cin>>a[i];

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

		if(i==0){
			dp[i][a[i]] = i+1;
			continue;
		}
		dp[i][a[i]] = i+1;
		for(int sum = s; sum >= 0 ; --sum){

			if(sum - a[i] > 0){
				dp[i][sum] += dp[i-1][sum - a[i]];
			}
			else break;
			if(dp[i][sum]>=mod)
				dp[i][sum]-=mod;
		}
		for(int sum = s; sum >= 0 ; --sum){

			dp[i][sum]+=dp[i-1][sum];

			if(dp[i][sum] >= mod)
				dp[i][sum]-=mod;
		}
	}
	long long ans = 0;
	for(int i = 0 ; i < n ; ++i){

		if(i==0){

			if(dp[i][s])
				ans = n - i + 1;
			continue;
		}

		long long val = dp[i][s] - dp[i-1][s];
		val += 5LL*mod;
		val%=mod;
		val*=(n-i);
		val%=mod;
		ans += val;
		ans%=mod;
	}

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

	// 	for(int j = 0 ;j <= s; ++j)
	// 		cout<<dp[i][j]<<" \n"[j==s];
	// }

	cout<<ans<<endl;


}

signed main(){

    fast;
    int t = 1;
    //cin>>t;
    for(int i = 1 ; i <= t ; ++i){

    	solve();
    }
}






Measured memory_bytes: 35456
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        double[] ans=new double[n];
        for(int i=0;i<n;i++){
            ans[i]=sc.nextInt();
        }
        Arrays.sort(ans);
        for(int i=0;i<n-1;i++){
            ans[i+1]=(ans[i]+ans[i+1])/2;
        }
        System.out.println(ans[n-1]);
    }
    
    
}

Measured memory_bytes: 21972
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val hashMap = new scala.collection.mutable.HashMap[Int, Unit]
  1.to(sc.nextInt()).foreach { _ =>
    val number = sc.nextInt()
    if (hashMap.contains(number)) hashMap.remove(number)
    else hashMap.put(number, ())
  }
  println(hashMap.size)
}


Measured memory_bytes: 63620
#include<bits/stdc++.h>
using namespace std;
#define rep0(i,n) for(i=0;i<n;i++)
#define test(a) cout << "*" << a << endl
int main (){
  int n;
  string s;
  int i,j;
  int count=0;
  
  cin >> n >> s;
  
  rep0(i,n-2){
    if(s[i]=='A'&&s[i+1]=='B'&&s[i+2]=='C'){
      count++;
    }
  }
      
  cout << count << endl;
}

Measured memory_bytes: 256
#まずH時M分の長さAの時針と長さBの分針の座標を求める
#時針について
#一時間で時針は360/12H=30H度回る
#初期条件は０時０分なので、xはサイン関数、ｙはコサイン関数
#分針について(
#一分で分針は360/60M=6M度回る
#あとは時針と同じ
import math
A,B,H,M = map(int,input().split())
H += (M/60)
hx = A*math.sin(math.radians(30*H))
hy = A*math.cos(math.radians(30*H))
mx = B*math.sin(math.radians(6*M))
my = B*math.cos(math.radians(6*M))
distans = math.sqrt((hx-mx)**2 + (hy - my)**2)
print(distans)

Measured memory_bytes: 9452
#include<bits/stdc++.h>
using namespace std;
#define int long long

int32_t main()
{
	char t;
	cin>>t;
	if(isupper(t))
	{
		cout<<"A"<<endl;
	}
	else if(islower(t))
	{
		cout<<"a"<<endl;

	}
}


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

int main(){
    int n,m; cin >> n >> m;
    bool Q[n+1];
    int wa[n+1];
    for(int i = 1; i < n+1; i++) {Q[i] = false; wa[i] = 0;}

    int ac = 0, pe = 0;
    for(int i = 0; i < m; i++){
        int q; string s;
        cin >> q >> s;
        if(!Q[q]){
            if(s == "AC") {ac++; Q[q] = true; pe += wa[q];}
            else wa[q]++;
        }
    }

    cout << ac << " " << pe << endl;

    return 0;
}

Measured memory_bytes: 768
N = int(input())
a = list(map(int, input().split()))

check = [0] * 9
for i in range(N):
    if 1 <= a[i] <= 399:
        check[0] += 1
    elif 400 <= a[i] <= 799:
        check[1] += 1
    elif 800 <= a[i] <= 1199:
        check[2] += 1
    elif 1200 <= a[i] <= 1599:
        check[3] += 1
    elif 1600 <= a[i] <= 1999:
        check[4] += 1
    elif 2000 <= a[i] <= 2399:
        check[5] += 1
    elif 2400 <= a[i] <= 2799:
        check[6] += 1
    elif 2800 <= a[i] <= 3199:
        check[7] += 1
    elif 3200 <= a[i]:
        check[8] += 1

tmp = 0
for i in range(len(check)-1):
    if check[i] >= 1:
        tmp += 1

ans_min = max(1,tmp)
ans_max = tmp + check[-1]

ans = str(ans_min) + ' ' + str(ans_max)
print(ans)

Measured memory_bytes: 3064
#include <iostream>

using namespace std;

bool between(int a, int b, int c){
	return a <= b && b <= c;
}

int main(){
	int T;
	cin >> T;
	while(T--){
		int x, y, w, h, n;
		cin >> x >> y >> w >> h >> n;
		int answer = 0;
		while(n--){
			int a, b;
			cin >> a >> b;
			if(between(x, a, x + w) && between(y, b, y + h)){ ++answer; }
		}
		cout << answer << endl;
	}
	return 0;
}
		

Measured memory_bytes: 1160
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>

using namespace std;

class node{
public:
	int id;
	node* left, * right;
	node*  parent;
	int sibling;
	int depth;
	int height;
};

bool operator<=(node a, node b) {
	return a.id <= b.id;
}
bool operator<(node a, node b) {
	return a.id < b.id;
}

bool operator==(node a, node b) {
	return a.id == b.id;
}

bool operator!=(node a, node b) {
	return a.id != b.id;
}

void add(node** root,int a) {
	node *newnode = new node;
	node* now = *root;
	newnode->id = a;
	newnode->left = NULL;
	newnode->right = NULL;
	if (now == NULL) {
		newnode->parent = NULL;
		*root = newnode;
		return;
	}
	while (1) {
		if (now->id > a) {
			if (now->left == NULL) {
				now->left = newnode;
				newnode->parent = now;
				return;
			}
			else {
				now = now->left;
			}
		}
		else {
			if (now->right == NULL) {
				now->right = newnode;
				newnode->parent = now;
				return;
			}
			else {
				now = now->right;
			}
		}
	}
}


string postorder(node* nod) {
	string msg="";
	if (nod->left->id != -1) {
		msg += postorder(nod->left);	
	}
	if (nod->right->id != -1) {
		msg += postorder(nod->right);	
	}
	msg += to_string(nod->id) + " ";
	return msg;
}

void preorder(node* root) {
	if (root == NULL)return;
	cout << " "<<root->id;
	preorder(root->left);
	preorder(root->right);
}

void inorder(node* root) {
	if (root == NULL)return;
	inorder(root->left);
	cout <<" "<< root->id;
	inorder(root->right);
}



int main() {
	int n,tmp;
	string msg;
	cin >> n;
	node* root = NULL;
	for (int i = 0;i < n;i++) {
		cin >> msg;
		if (msg == "insert") {
			cin >> tmp;
			add(&root, tmp);
		}
		else {
			inorder(root);
			cout << endl;
			preorder(root);
			cout << endl;
		}
	}
}






Measured memory_bytes: 34404
#include <bits/stdc++.h>
#define mset(a, b) memset(a, b, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))
#define rg register
using namespace std;
typedef long long LL;
const int MAXN = 100005;
const int INF = 0x3f3f3f3f;

template <typename T> inline void read(T &AKNOI) {
	T x = 0, flag = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') flag = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	AKNOI = flag * x;
}

template <typename T> inline void cmin(T &x, T y) {
	if (x > y) x = y;
}

template <typename T> inline void cmax(T &x, T y) {
	if (x < y) x = y;
}

int n, K, fa[MAXN];
int dep[MAXN], mxd[MAXN], dp[MAXN];

struct Edge {
	int v, nxt;
}e[MAXN];
int first[MAXN], eCnt;

inline void AddEdge(int u, int v) {
	e[++eCnt].v = v;
	e[eCnt].nxt = first[u];
	first[u] = eCnt;
}

void DFS(int u) {
	mxd[u] = dep[u];
	for (int i=first[u];i;i=e[i].nxt) {
		int v = e[i].v;
		dep[v] = dep[u] + 1;
		DFS(v);
		if (dp[v]) continue;
		cmax(mxd[u], mxd[v]);		
	}
	if (fa[u] != 1 && mxd[u] - dep[u] + 1 >= K) dp[u] = 1;
}

void init() {
	read(n); read(K);
	for (int i=1;i<=n;++i) {
		read(fa[i]);
		if (i > 1) AddEdge(fa[i], i);
	}
}

void solve() {
	if (fa[1] != 1) {
		dp[1] = 1;
		fa[1] = 1;
	}
	DFS(1);
	int ans = 0;
	for (int i=1;i<=n;++i) {
		ans += dp[i];
	}
	printf("%d\n", ans);
}

int main() {
	init();
	solve();
	return 0;
}


Measured memory_bytes: 6144
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a)?"Yes":"No")
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
const long long INFLL = 1LL<<62;
const int INF = 1<<30;
const double PI=acos(-1);
ll mod = 1e9 + 7;
long long modpow(long long a, long long n, long long mod=(1LL<<62)){
	long long res = 1;
	while (n > 0){
		if (n & 1)
		res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
int main(){
	int n;
	ll ans=0LL;

	cin >>n;
	int a;
	int bef;
	int count=0;
	vector<map<int,int>>em(n);
	map<int,int>emax;
	rep(i,n){
		cin>>a;
		bef=a;
		for(int c=2;c<=sqrt(bef);c++){
			count=0;
			while(bef%c==0){
				bef/=c;
				count++;
			}
			if(count!=0){
				em[i][c]+=0;
				em[i][c]=count;
				emax[c]+=0;
				chmax(emax[c],count);
			}
		}
		if(bef!=1){
			em[i][bef] += 0;
			em[i][bef] += 1;
			emax[bef] += 0;
			chmax(emax[bef], 1);
		}
	}
	ll bper=1LL;
	for(auto itr=emax.begin();itr!=emax.end();itr++){
		bper*=modpow(itr->F,itr->S,mod);
		bper%=mod;
		//clog<<(itr->F)<<" "<<(itr->S)<<endl;
	}
	//clog<<bper<<endl;
	ll sper=1LL;
	rep(i,n){
		sper=1LL;
		for(auto itr=em[i].begin();itr!=em[i].end();itr++){
			sper*=modpow(itr->F,itr->S,mod);
			sper%=mod;
			//clog<<(itr->F)<<" "<<(itr->S)<<endl;
		}
		ans+=bper*modinv(sper,mod);
		ans%=mod;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3072
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <deque>
#include <cctype>
#include <unordered_map>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<long, long>;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
#define rep(i, n) for(int i = 0; i<n; i++)
#define rep_s(i, start, n) for(int i= start;  i<n; i++)
#define rep_down(i, n) for(int i = n-1; i>=0; i--)
#define rep_down_s(i, n, start) for(int i = n-1; i>=start; i--)
#define ALL(a) (a).begin(), (a).end()
#define ALL_str(a) (a).cbegin(), (a).cend()

string alphabet_upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string alphabet_lower  = "abcdefghijklmnopqrstuvwxyz";
string numbers = "0123456789";
/*
for (iterator = hash.begin(); iterator != hash.end(); iterator++)
{
// ここで、要素毎の操作を行います。
std::pair<std::string, CMyClass> element = *iterator;

}
*/
/*
using edge = struct {int to; ll cost;};
vector<edge> tree[limit];
ll depth[limit];

void dfs(int v, int p, ll d){
  depth[v] = d;
  //cout <<"v: " << v << endl;
  for (auto &e: tree[v]){
    //cout << "e.to: " << e.to << endl;
    if (e.to == p) continue;
    dfs(e.to, v, d+e.cost);
  }
}
*/
int keta_sum(int num){
  int dig, sum = 0;
  while(num){
    dig = num % 10;
    sum = sum + dig;
    num = num / 10;
  }
  return sum;
}

ll binary_search(ll left_key, ll border, ll low, ll high) {
     // 配列 a の左端と右端
    ll mid = (low+high)/2;
    while (high > low+1) {
       mid = (low+high)/2;
        if (left_key*mid>border) high = mid;
        else if (left_key*mid<border) low = mid;
        else {
          mid =mid-1;
          break;
        }
    }
    return mid;
}

bool IsPrime(ll a){
  ll b = sqrt(a);
  b++;
  while(b-->=2){
    if (a%b==0) return false;
  }
  return true;
}

ll gcd(ll a, ll b){
  ll tmp;
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }

  ll r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main(void){
  ll N, M, A, B, C, D, E, F, K,L, W, H, P, Q, R, X, Y;
  ll ans;
  string S, T;
  cin >>A >> B;
  if (A>9 || B>9) cout << -1 << endl;
  else cout << A*B << endl;
  
  
  
   




}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1e18
#define PI 3.14159265358979

using namespace std;

ll gcd(ll a, ll b);
ll power(ll n, ll k);
ll inv(ll n);
ll genfact(ll n, ll k);
ll fact(ll n);
ll nck(ll n, ll k);

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

  int res = 0;
  for (int i = 1; i < n; i++){
    int alph1[26] = {}, alph2[26] = {};
    for (int j = 0; j < n; j++){
      if (j < i){
        alph1[s[j] - 'a']++;
      }
      else {
        alph2[s[j] - 'a']++;
      }
    }
    int t = 0;
    for (int j = 0; j < 26; j++){
      int a = alph1[j] * alph2[j];
      if (a > 0)
        t++;
    }
    res = max(res, t);
  }

  cout << res << endl;

  return 0;
}

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

ll power(ll n, ll k){
  ll res = 1;
  while(k > 0){
    if (k & 1) 
      res = res * n % MOD;
    n = n * n % MOD;
    k >>= 1;
  }
  return res;
}

ll genfact(ll n, ll k){

  ll res = 1;
  while (k >= 0){
    res = (res * (n - k)) % MOD;
    k--;
  }

  return res;
}

ll inv(ll n){
  return power(n, MOD - 2);
}

ll fact(ll n){
  return genfact(n, n - 1);
}

ll nck(ll n, ll k){
  if (k == 0)
    return 1;
  if (n <= 0)
    return 0;

  return ((genfact(n, k) % MOD) * inv(fact(k))) % MOD;
}


Measured memory_bytes: 256
#include <iostream>
#include <climits>
#include <stack>
#include <queue>
#include <string>
#include <random>
#include <utility>
#include <cmath>
#include <string.h>
#include <iomanip>
#include <stdlib.h>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
long long int INF = 1e18;
double Pi = 3.141592653589;
const int mod = 1000000007;
// memset(a,0,sizeof(a)); →全部０にする
 
struct edge{int to,cost;};
vector<int> G[100005];
 
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
 
std::vector<P> tree[100010];
ll i,j;

ll n;
ll ans=0;
ll a,b;

int main(){
	cin>>a>>b;
	for(i=a;i<=b;i++){
		if(i/10000==i%10 && (i/1000)%10 == (i%100)/10){
			ans++;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 4992
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

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

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))


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

    int x;
    cin >> x;

    cout << (x >= 30 ? "Yes\n" : "No\n");

    return 0;
}



Measured memory_bytes: 3616
#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[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};


bool cmp_P(const P &a,const P &b){
  return a.second < b.second;
}
int main()
{
  int N,T,c[101],t[101],res=9999;
  cin >> N >> T;
  REP(i,N)
    cin >> c[i] >> t[i];
  REP(i,N){
    if(t[i] <= T){
      res = min(res,c[i]);
    }
  }
  if(res == 9999)
    cout << "TLE" << endl;
  else
    cout << res << endl;
 
  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;
}
const int MOD = 1000000007;
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
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b){if(a < b){a = b; return 1;}return 0;}

int main(){
  int N; cin >> N;
  long long a[100000][3], dp[10000000][3];
  for(int i = 1; i <= N; i++){
    for(int j = 1; j <= 3; j++){
      cin >> a[i][j];
      dp[i][j] = 0;
    }
  }
  dp[1][1] = a[1][1]; dp[1][2] = a[1][2]; dp[1][3] = a[1][3];
  for(int i = 2; i <= N; i++){
    for(int j = 1; j <= 3; j++){
      for(int k = 1; k <= 3; k++){
        if(j == k) continue;
        chmax(dp[i][k], dp[i - 1][j] + a[i][k]);
      }
    }
  }
  long long res = 0;
  for(int j = 1; j <= 3; j++){
    chmax(res, dp[N][j]);
  }
  cout << res << endl;
}

Measured memory_bytes: 6784
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = 3;
        int[][] as = new int[n + 1][k];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < k; j++) {
                as[i][j] = sc.nextInt();
            }
        }
        
        int[][] dp = new int[n + 1][k];
        for (int i = 0; i < k; i++) {
            dp[1][i] = as[1][i];
        }
        
        for (int i = 2; i <= n; i++) {
            int[] plans = new int[k];
            dp[i][0] = as[i][0] + Math.max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][1] = as[i][1] + Math.max(dp[i - 1][0], dp[i - 1][2]);
            dp[i][2] = as[i][2] + Math.max(dp[i - 1][0], dp[i - 1][1]);
        }
        
        int answer = Math.max(Math.max(dp[n][0],dp[n][1]), dp[n][2]);
        
        System.out.println(answer);
    }
}


Measured memory_bytes: 100156
n = int(input())
s = input()

r = s.count("R")
g = s.count("G")
b = s.count("B")

ans = r * g * b

c = {"R", "G", "B"}

for i in range(n):
    for j in range(i + 1, n):
        if j - i + j < n:
            if {s[i], s[j], s[j - i + j]} == c:
                ans -= 1

print(ans)

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

int main()
{
	int N;
	cin >> N;
	vector<long long> v(N + 1);
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}
	int n = 0;
	for (int i = 0; i < N;) {
		int l = 0;
		int m = 0;
		if (v[i] <= v[i + 1]) {
			for (int j = i; j < N; j++) {
				l++;
				if (j == N - 1) {
					break;
				}
				if (v[j] > v[j + 1]) {
					break;
				}
			}
		}
		if (v[i] >= v[i + 1]) {
			for (int j = i; j < N; j++) {
				m++;
				if (j == N - 1) {
					break;
				}
				if (v[j] < v[j + 1]) {
					break;
				}
			}
		}
		n++;
        int ma = max(l, m);
		i += ma;
	}
	cout << n << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
#define mod 1000000007
#define MOD 1000000037
#define mod1 998244353
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 
#define INF 2e9
#define common cout << "Case #" << w+1 << ": "  

vector<vector<char> >v;
vector<vector<int> >dist;
int n,m;
int ix,iy,tx,ty;
vector<int>vx={-1,0,1,0},vy={0,-1,0,1};

bool isin(int x,int y)
{
    if(x>-1 and y>-1 and x<n and y<m)
        return true;
    return false;
}


void bfs(int x,int y)
{
    deque<pair<pair<int,int>,int> >q;
    q.push_front({{x,y},0});
    while (q.size()>0)
    {
        pair<pair<int,int>,int>p=q.front();
        q.pop_front();
        int x=p.first.first,y=p.first.second,d=p.second;
        if(dist[x][y]<d or dist[tx][ty]<=d)
            continue;
        dist[x][y]=min(dist[x][y],d);
        for(int i=0;i<4;i++)
        {
            if(isin(x+vx[i],y+vy[i]) and  v[x+vx[i]][y+vy[i]]!='#' and dist[x+vx[i]][y+vy[i]]>d)
            {
                dist[x+vx[i]][y+vy[i]]=d;
                q.push_front({{x+vx[i],y+vy[i]},d});
            }
        }
        for(int i=max(0,x-2);i<=min(x+2,n-1);i++)
        {
            for(int j=max(0,y-2);j<=min(y+2,m-1);j++)
            {
                if(v[i][j]!='#' and dist[i][j]>d+1)
                {
                    dist[i][j]=d+1;
                    q.push_back({{i,j},d+1});
                }
            }
        }
    }
    
}

int main()
{
    fastio;
    cin >> n >> m;
    cin >> ix >> iy >> tx >> ty;
    ix-=1;iy-=1;tx-=1;ty-=1;
    v.resize(n);
    dist.resize(n);
    for(int i=0;i<n;i++)
    {
        v[i].resize(m);
        dist[i].resize(m,INF);
        for(int j=0;j<m;j++)
            cin >> v[i][j];
    }
    bfs(ix,iy);
    if(dist[tx][ty]!=INF)
        cout << dist[tx][ty] << endl;
    else
        cout << "-1" << endl;
}


Measured memory_bytes: 8604
def puyo_rensa(cnt, fld)
  erase = 8.times.map{ [nil] * 14 }
  (1..6).each do |i|
    (1..12).each do |j|
      if erase[i][j].nil? && fld[i][j] =~ /[^O.]/
        erase[i][j] = false
        puyo_connector(i, j, fld, erase){ |arr|
          arr.each do |s, t|
            drct(s, t).each do |p, q|
              erase[p][q] = true if fld[p][q] == 'O'
            end
            erase[s][t] = true
          end
        }
      end
    end
  end
  if erase.flatten.any?{ |v| v } then puyo_rensa(cnt + 1, puyo_eraser(fld, erase))
  else cnt
  end
end

def puyo_connector(i, j, fld, erase)
  arr = [[i, j]]
  ret = [[i, j]]
  until arr.empty?
    i, j = arr.shift
    drct(i, j).each do |p, q|
      if erase[p][q].nil? && fld[i][j] == fld[p][q]
        erase[p][q] = false
        arr << [p, q]
        ret << [p, q]
      end
    end
  end
  yield(ret) if ret.size >= 4
end

def puyo_eraser(fld, erase)
  (1..6).each do |i|
    fld[i].map!.with_index{ |c, j| c unless erase[i][j] }.compact!
    (14 - fld[i].size).times{ fld[i].unshift('.') }
  end
  fld
end

def drct(x, y)
  [[-1, 0], [1, 0], [0, -1], [0, 1]].map{ |p, q| [p + x, q + y] }
end

gets.to_i.times do
  fld = 8.times.map{ ['.'] * 14 }
  12.times do |i|
    gets.chomp.split('').each_with_index do |c, j|
      fld[j + 1][i + 1] = c
    end
  end
  p puyo_rensa(0, fld)
end

Measured memory_bytes: 8968
//g++ -std=gnu++14 a.cpp

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
#include <random>
#include <math.h>
#include <stdio.h>

using namespace std;

#define ll long long
#define rep(i, n) for(ll i = 0; i < (n); i++)
ll MOD = 1e9 + 7;
int INF = 1 << 30;
ll INFL = 1LL << 60;
ll MODP = 998244353;

ll kai(ll x,ll y){
  if(y == 0)return 1;
  if(y == 1)return x;
  if(y&1){
    return (x*kai(x,y-1))%MOD;
  }else{
    ll t = kai(x,y/2);
    return (t*t)%MOD;
  }
}

ll comb(ll a,ll b,vector<ll> &p){
  if(a == 0)return 1;
  if(b == 0)return 1;
  ll ans = p[a+b];
  ans = (ans*kai(p[a],MOD-2))%MOD;
  ans = (ans*kai(p[b],MOD-2))%MOD;
  return ans;
}

int main(){
  int d,t,s;
  cin >> d >> t >> s;
  int D = t*s;
  if(d <= D){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }




  return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <stdio.h>
using namespace std;

int main(void){
	int n;
	int cs, ce, ct = 0;
	cin >> n;
	for (int i = 0; i < n; ++i){
		cin >> cs >> ce;
		ct += ce - cs + 1;
	}
	cout << ct << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 1000000007;
int main() {
  int N;
  cin >> N;
  string S;
  cin >> S;
  int R[N];
  int rR[N];
  for (int i = 0; i < N; i++) {
    if (i == 0) {
      if (S[i] == 'W') {
        R[0] = 1;
      } else {
        R[0] = 0;
      }
    } else {
      if (S[i] == 'W') {
        R[i] = R[i-1] + 1;
      } else {
        R[i] = R[i-1];
      }
    }
  }
  for (int i = N-1; i >= 0; i--) {
    if (i == N-1) {
      if (S[N-1] == 'R') {
        rR[N-1] = 1;
      } else {
        rR[N-1] = 0;
      }
    } else {
      if (S[i] == 'R') {
        rR[i] = rR[i+1] + 1;
      } else {
        rR[i] = rR[i+1];
      }
    }
  }
  int ans = min(R[N-1],rR[0]);
  for (int i = 1; i < N-1; i++) {
    ans = min(ans, max(R[i-1],rR[i]));
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 5284
#include <bits/stdc++.h>
#define REP(i,n) for(LL i=0;i<(LL)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long
#define pii pair<LL,LL>
#define pll pair<LL,LL>

using namespace std;

int main(){

    LL n;cin>>n;

    LL a[n];REP(i,n)cin>>a[i];

    LL ans=1;
    REP(i,n)ans*=3;
    LL sub=1;
    REP(i,n)if(a[i]%2==0)sub*=2;
    cout<<ans-sub<<endl;

    return 0;
}

Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::io::{stderr, stdin, stdout, BufRead, BufWriter, Read, StdoutLock, Write};
#[allow(unused_imports)]
use std::iter::FromIterator;
#[allow(unused_imports)]
use std::{i64, u64, usize};
#[allow(unused_macros)]
/// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules !input {(source =$s :expr ,$($r :tt ) *) =>{let mut iter =$s .split_whitespace () ;input_inner !{iter ,$($r ) *} } ;($($r :tt ) *) =>{let mut s ={use std ::io ::Read ;let mut s =String ::new () ;std ::io ::stdin () .read_to_string (&mut s ) .unwrap () ;s } ;let mut iter =s .split_whitespace () ;input_inner !{iter ,$($r ) *} } ;}
#[allow(unused_macros)]
macro_rules !input_inner {($iter :expr ) =>{} ;($iter :expr ,) =>{} ;($iter :expr ,$var :ident :$t :tt $($r :tt ) *) =>{let $var =read_value !($iter ,$t ) ;input_inner !{$iter $($r ) *} } ;}
#[allow(unused_macros)]
macro_rules !read_value {($iter :expr ,($($t :tt ) ,*) ) =>{($(read_value !($iter ,$t ) ) ,*) } ;($iter :expr ,[$t :tt ;$len :expr ] ) =>{(0 ..$len ) .map (|_ |read_value !($iter ,$t ) ) .collect ::<Vec <_ >>() } ;($iter :expr ,chars ) =>{read_value !($iter ,String ) .chars () .collect ::<Vec <char >>() } ;($iter :expr ,usize1 ) =>{read_value !($iter ,usize ) -1 } ;($iter :expr ,$t :ty ) =>{$iter .next () .unwrap () .parse ::<$t >() .expect ("Parse error" ) } ;}
#[allow(unused_macros)]
macro_rules !dbg {($($a :expr ) ,*) =>{writeln !(&mut stderr () ,concat !($(stringify !($a ) ," = {:?}, " ) ,*) ,$($a ) ,*) .unwrap () ;} }
#[allow(non_snake_case)]
#[allow(dead_code)]
fn main() {
    input! {
        h: u64
    }
    let mut ans: u64 = 0;
    let mut h = h;
    let mut i = 1;
    while h > 0 {
        h /= 2;
        ans += i;
        i *= 2;
    }
    println!("{}", ans);
}

Measured memory_bytes: 4352
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
 
sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7
 
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
 
 
def main():
    n,c = LI()
    a = [-1] * (c+1)
    b = sorted([LI() for _ in range(n)])
    for s,t,d in b:
        for i in range(c):
            if a[i] < s:
                a[i] = t
                break
 
    for i in range(c+1):
        if a[i] < 0:
            return i
 
    return -1
 
 
 
print(main())

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

int main()
{
    int n;
    cin >> n;
    int a[n] = {};
    for(int i=0; i<n; i++) cin >> a[i];
    
    long sum=0;
    long ans=0;
    int r=0;
    for(int l=0; l<n; l++){
        while((sum^a[r]) == sum+a[r] && r<n){    // condition satisfied
            sum += a[r];
            r++;
        }
        ans += r-l;
        sum ^= a[l];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iomanip>
#include <map>
#include <set>
#include <tuple>
#include <unordered_map>
#include <iterator>
#include <string>
#include <limits>

using namespace std;

using i64 = int64_t;
using P = pair<i64, i64>;
i64 mod = 1000000007;
int int_max = 2147483647;
int max_n = 1e5;
using mat2d_t = std::vector<std::vector<int64_t>>;

size_t count_pivot(const i64 max, size_t piv, std::vector<i64>& vec) {
    size_t sz = vec.size();
    if (sz == 1) return 0;
    if (sz == 2) return 1;

    size_t l_pos = 0, r_pos = sz-1;

    while(r_pos-l_pos > 1) {
        size_t mid = (l_pos + r_pos) / 2;
        if (vec[piv] < 0) {
            if (vec[mid] * vec[piv] >= max) {
                l_pos = mid;
            } else {
                r_pos = mid;
            }
        } else {
            if (vec[mid] * vec[piv] >= max) {
                r_pos = mid;
            } else {
                l_pos = mid;
            }
        }
    }

    size_t ret{0};
    if (vec[piv] < 0) {
        if (vec[r_pos] * vec[piv] >= max) return 0;
        if (vec[l_pos] * vec[piv] < max) ret = vec.size()-l_pos;
        else ret = vec.size()-r_pos;
    } else {
        if (vec[l_pos] * vec[piv] >= max) return 0;
        if (vec[r_pos] * vec[piv] < max) ret = r_pos+1;
        else ret = l_pos+1;
    }
    //std::cout << "  " << l_pos << " " << r_pos <<endl;

    if (vec[piv] * vec[piv] < max) --ret;
    return ret;
}

i64 binary_search(const i64 k, std::vector<i64>& vec) {
    i64 left = numeric_limits<int64_t>::min()/2;
    i64 right = numeric_limits<int64_t>::max()/2;

    while (right-left > 1) {
        i64 mid = (left+right)/2;
        size_t cnt{0};
        for (size_t i=0; i<vec.size(); ++i) {
            cnt += count_pivot(mid, i, vec);
            //cout << "    " << cnt << std::endl;
            if (cnt > 2*k) break;
        }
        cnt /= 2;
        if (cnt >= k) right = mid;
        else left = mid;
        //cout << cnt << ": "<< left << " " << right << endl;
    }
    return left;
}

int main(int argc, char **argv) {
    i64 n, k;
    cin >> n >> k;

    std::vector<i64> v(n);
    for (int i=0; i<n; ++i) {
        cin >> v[i];
    }
    std::sort(v.begin(), v.end());

    cout << binary_search(k, v) << endl;

    return 0;
}

Measured memory_bytes: 1920
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007
    N = int(input())
    p = list(map(float, input().split()))
    #dp[j]:裏がj枚でる確率
    dp = [1] + [0]*(N//2)
    for i in range(N):
        for j in range(i+1, -1, -1):
            if j==0:
                dp[j] = dp[j]*p[i]
            elif j<=(N//2):
                dp[j] = dp[j-1]*(1-p[i]) + dp[j] * p[i]

    res = sum(dp)
    print('{:.9f}'.format(res))

if __name__ == '__main__':
    main()

Measured memory_bytes: 3700
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int x = sc.nextInt();
		int y = sc.nextInt();
		
		for(int i = 0; i < x+1; i++) {
			if(2*i + 4*(x-i) == y) {
				System.out.println("Yes");
				break;
			}else if( i == x) {
				System.out.println("No");
			}
		}
	}
}

Measured memory_bytes: 27072
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll MOD=1000000007,MAXN=2e5+10;
map<pii,int> Cnt;
map<pii,bool> Vis;
pii Vec[MAXN],NVec[MAXN];
int N;
inline ll fpow(ll a, ll x){
    ll ans=1;
    for(;x;x>>=1,a=a*a%MOD) if(x&1) ans=ans*a%MOD;
    return ans;
}
pii operator / (const pii &vec,ll n) { return pii(vec.first/n,vec.second/n); }
inline pii simplfy(const pii &Vec){
    if(Vec==pii(0,0)) return Vec;
    pii newVec=Vec/__gcd( abs(Vec.first) , abs(Vec.second) );
    if( newVec.first<0||(newVec.first==0&&newVec.second<0) )
        newVec=newVec/(-1);
    return newVec;
}
inline void pre(){
    Cnt[pii(0,0)]=0;
    Vis[pii(0,0)]=1;
    cin>>N;
    for(int i=1;i<=N;i++){
        ll X,Y;
        cin>>X>>Y;
        Vec[i]=simplfy( pii(X,Y) ),NVec[i]=simplfy( pii(Y,-X) );
        if(Cnt.find(Vec[i])==Cnt.end()) Cnt[Vec[i]]=0;
        if(Cnt.find(NVec[i])==Cnt.end()) Cnt[NVec[i]]=0;
        Cnt[Vec[i]]++;
    }
}
int main(){
    pre();
    ll Sum=1;
    for(int i=1;i<=N;i++){
        if(Vis[ Vec[i] ])
            continue;
        Vis[Vec[i]]=Vis[NVec[i]]=1;
        Sum*=fpow(2,Cnt[Vec[i]])+fpow(2,Cnt[NVec[i]])-1;
        Sum%=MOD;
    }
    Sum=(Sum-1+Cnt[pii(0,0)]+MOD)%MOD;
    cout<<Sum;
    return 0;
}

Measured memory_bytes: 59896
#include<bits/stdc++.h>
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 Would
#define you
#define please

int main() {
	//おまじない
	cin.tie(0);
	ios::sync_with_stdio(false);
	

	int N, C;
	int D[30][30];
	int c[500][500];
	cin >> N >> C;
	rep(i, C) rep(ii, C) cin >> D[i][ii];
	rep(i, N) rep(ii, N) cin >> c[i][ii];

	int nurikae[3][30] = {};

	rep(i, 2 * N - 1) {
		rep(ii, N - abs(i - N + 1)) {
			rep(iii, C) {
				if (i < N) nurikae[i % 3][iii] += D[c[i - ii][ii] - 1][iii];
				else nurikae[i % 3][iii] += D[c[N - ii - 1][i - N + ii + 1] - 1][iii];
			}
		}
	}

	int kotae = 1e9;
	
	rep(i, C) {
		rep(ii, C) {
			rep(iii, C) {
				if (i != ii && ii != iii && iii != i) {
					int kari = nurikae[0][i] + nurikae[1][ii] + nurikae[2][iii];
					kotae = min(kotae, kari);
				}
			}
		}
	}
	cout << kotae << "\n";

	Would you please return 0;
}

Measured memory_bytes: 1280
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>

using namespace std;

int main(){
    int N;
    cin>>N;
    N++;
    int t[N],x[N],y[N];
    t[0]=0,x[0]=0,y[0]=0;
    for(int i=1;i<N;i++){
        cin>>t[i]>>x[i]>>y[i];
    }
    bool ans=true;
    for(int i=0;i<N-1;i++){
        int a=t[i+1]-t[i];
        int b=abs(x[i+1]-x[i])+abs(y[i+1]-y[i]);
        if(a%2!=b%2){
            ans=false;
            break;
        }
        if(a<b){
            ans=false;
            break;
        }
    }
    if(ans){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}

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

 
int main() {
   int n,k;
   cin>>n>>k;
   vector<int> A(n);
   rep(i,n)cin>>A[i];
   int ans=(n-k+k-2)/(k-1)+1;
   cout<<ans<<endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;

int N, M;
vector<vector<P>> root(101);  //pair<辺の距離, 行先の頂点>
vector<vector<ll>> dist(101, vector<ll>(101, LLONG_MAX)); //dist[i][j]は始点(i)から頂点jへの最短距離が入る
bitset<101> used;

void Dijkstra(ll start){ //start = 始点
    used.reset();
    priority_queue<P, vector<P>, greater<P>> que;
    que.push(make_pair(0, start));
    while(!que.empty()){
        ll d, t; //d:startからの距離, t:行先
        tie(d, t) = que.top(); que.pop();
        if(used[t]) continue;   //探索済み
        used[t] = true, dist[start][t] = d;
        for(auto e : root[t]){
            if(dist[start][e.second] <= d + e.first) continue;
            que.push(make_pair(d + e.first, e.second));
        }
    }
}

int main(void){
    
    scanf("%d %d", &N, &M);
	
	map<P, ll> mp;
	 for(int i = 0; i < M; ++i){
        ll a, b, c; scanf("%lld %lld %lld", &a, &b, &c);
        root[a].push_back(make_pair(c, b)), root[b].push_back(make_pair(c, a));
        mp[{a, b}] = mp[{b, a}] = c;
    }
    
    for(int i = 1; i <= N; ++i) Dijkstra(i);
    
    int ans = 0;
    for(int i = 1; i <= N; ++i){
        for(int j = i + 1; j <= N; ++j){
            if(dist[i][j] < mp[{i, j}]) ++ans;
        }
    }
    printf("%d\n", ans);
    
    return 0;
}

Measured memory_bytes: 768
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

#define rep(i,n) for(int i = 0; i < n; ++i)
#define X first
#define Y second
#define all(x) x.begin(), x.end()
using namespace std;
using PII=pair<int,int>;


// Tree
class Node{
  public:
    int dist;
    int parent;
    vector<PII> children;
    Node(){dist=0;};
};
Node nodes[200000];
int a, b, c, n;
int ans;

int dfs(int index, int val){
  vector<int> d;
  d.resize(nodes[index].children.size() + 2, 0);
//   cout << "index: " << index << endl;
  rep(i,nodes[index].children.size()){
    d[i] = dfs(nodes[index].children[i].X, nodes[index].children[i].Y);
  }
  sort(all(d));
  reverse(all(d));
//   cout << d[0] << "   " << d[1] << endl;
  ans = max(ans, d[0] + d[1]);
  return d[0] + val;
}

int main(void){

  cin >> n;

  rep(i,n-1){
    cin >> a >> b >> c;
    if(a>b) swap(a,b);
    nodes[a].children.push_back(PII(b,c));
    nodes[b].parent = a;
  }

  dfs(0, 0);

  cout << ans << endl;

  

  return 0;
}

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

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

const ll MAX_N = 1e5 + 5;
ll n, p;
string s1, s2, s;
string type[MAX_N];

void t1 (int l, int r);

void t2 (int l, int r) {
	cout << ((r + l) >> 1) - 1 << endl;
	cin >> s;

	type[(r + l) >> 1] = s;
	if (type[(r + l) >> 1] == "Vacant")
		return ;
	
	if ((((r - l + 1) >> 1) + 1) & 1) {
		if (type[(r + l) >> 1] != type[l])
			t2(l, (r + l) >> 1);
		else
			t2((r + l) >> 1, r);
	}
	else {
		if (type[(r + l) >> 1] == type[l])
			t1(l, (r + l) >> 1);
		else
			t1((r + l) >> 1, r);
	}
}



int main() {
//	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n;
	
	cout << 0 << endl;
	cin >> s1;

	cout << ((n + 1) >> 1) - 1 << endl;
	cin >> s2;

	type[1] = s1;
	type[(n + 1) >> 1] = s2;

	if (s1 == "Vacant" || s2 == "Vacant")
		return 0;
	
	if (((n + 1) >> 1) & 1) {
		if (s1 != s2)
			t2(1, (n + 1) >> 1);
		else
			t1((n + 1) >> 1, n + 1);
	}
	else {
		if (s1 == s2)
			t1(1, (n + 1) >> 1);
		else
			t2((n + 1) >> 1, n + 1);
	}
	return 0;
}

void t1 (int l, int r) {
	cout << ((l + r) >> 1) - 1 << endl;
	cin >> s;
	
	type[(l + r) >> 1] = s;
	if (type[(l + r) >> 1] == "Vacant")
		return ;
	
	if (((r - l + 1) >> 1) & 1) {
		if (type[(l + r) >> 1] != type[l])
			t2(l, (l + r) >> 1);
		else
			t1((l + r) >> 1, r);
	}
	else {
		if (type[(l + r) >> 1] == type[l])
			t1(l, (l + r) >> 1);
		else
			t2((l + r) >> 1, r);
	}
}


Measured memory_bytes: 1620
using System;
using System.Linq;

class ABC164
{
    static void Main()
    {
        int[] n = Console.ReadLine().Split().Select(a => int.Parse(a)).ToArray();
        while(true)
        {
            n[2] -= n[1];
            if(n[2] <= 0)
            {
                Console.WriteLine("Yes");
                return;
            }
            n[0] -= n[3];
            if(n[0] <= 0)
            {
                Console.WriteLine("No");
                return;
            }
        }
    }
}

Measured memory_bytes: 19128
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;


int main() {
	long long int X, i, j; 
	cin >> X;
	for (i = 1000; i >= 0; --i)
	{
		for (long long int j = i - 1; j >= 0; --j)
		{ 
			long long int A, B;
			A = pow(i, 5);
			B = pow(j, 5);
			if (abs(A - B) == X)
			{
				cout << i << " " << j << endl;
				return 0;
			}
			else if (abs(A + B) == X)
			{
				cout << i << " " << (-j) << endl;
				return 0;
			}
		}
	}

}

Measured memory_bytes: 3604
import java.util.*;
 
public class Main{
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);

    String S = sc.next();
    long K = sc.nextLong();
    int temp = 0;
    for (int i=0;i<S.length();i++){
        if (S.charAt(i) != '1'){
            temp = i;
            break;
        }
    }

    if (K < temp+1){
        System.out.println(1);
    }
    else{
        System.out.println(S.charAt(temp));
    }
    return;
  }
}

Measured memory_bytes: 35488
from math import ceil

D, G = map(int,input().split())
pc = [list(map(int,input().split())) for i in range(D)]

ans = float("inf")
for bit in range(1 << D):
    cnt = 0
    sum = 0
    remain = set(range(1,D+1))

    for i in range(D):
        if bit & (1 << i):
            cnt += pc[i][0]
            sum += pc[i][0]*(i+1)*100 + pc[i][1]
            remain.discard(i+1)

    if sum < G:
        use = max(remain)
        n = min(pc[use-1][0], ceil((G-sum)/(use*100)))
        cnt += n
        sum += n*use*100

    if sum >= G:
        ans = min(ans,cnt)

print(ans)

Measured memory_bytes: 9240
import heapq

N,M=map(int,input().split())
A=list(map(lambda x: int(x)*(-1), input().split()))

heapq.heapify(A)

for i in range(M):
    tmp_min = heapq.heappop(A)
    heapq.heappush(A, (-1)*(-tmp_min//2))

print(-sum(A))

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

int main(){
    int H,W;
    
    while(1){
    cin >> H >> W;
        if(H == 0 && W == 0)break;
        
        for(int k = 1; k <= W; k++){
            cout << "#";
        }
        cout << endl;
    for(int i = 2; i < H; i++ ){
        cout << "#";
        for(int j = 2; j < W; j++ ){
            cout << ".";
        }
        cout << "#" << endl;
    }
        for(int h = 1; h <= W; h++){
            cout << "#";
        }
        cout << "\n" << endl;
    }
    
    return 0;
}

Measured memory_bytes: 3080
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
int main(){
	int n;
	int t, a;
	double cand;
	int candi;

	std::cin >> n;
	std::cin >> t >> a;

	std::vector<int> h(n);
	for(int i = 0; i < n; ++i){
		std::cin >> h.at(i);
	}

	for(int i = 0; i < n; ++i){
		double d = fabs(static_cast<double>(a) - (static_cast<double>(t) - static_cast<double>(h.at(i)) * 0.006));

		if(d < cand || i == 0){
			cand = d;
			candi = i;
		}
		/*
		if(i == 581 || i == 65){
			std::cout << i << " : " << h.at(i) << ", " << std::scientific << std::setprecision(6) <<  d << std::endl;
		}
		*/
	}

	std::cout << candi + 1 << std::endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,k;
  cin>>n>>k;
  int a[n],count=0;
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
    if(a[i]>=k)
    {
      count++;
    }
  }
  cout<<count<<endl;
}
  


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll INF=mod*mod;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(x) (x).begin(),(x).end()
ll min(ll a,ll b){
  if(a>b){
    return b;
    }
      else{
        return a;
      }
  }
  
  ll max(ll a,ll b){
    if(a>b){
      return a;
    }
    else{
      return b;
    }
  }

ll power(ll a,ll b){
 ll ans=1;
 for(ll i=1;i<=b;i++){
ans*=a;
  }
  return ans;
}

 ll gcd(ll m,ll n){
 	if(n==0){
       return m;
     }
   return gcd(n,m%n);
 }
ll lcm(ll a,ll b){
  ll g=gcd(a,b);
  return a/gcd(a,b)*b;
		

}
int main(){
  ll N;
  cin>>N;
    
    vector<ll>a(N);
  
  rep(i,N){
    cin>>a[i];
  }
ll now=1;
  ll ans=0;
  rep(i,N){
    if(a[i]==now){
      now++;
    }
else{
ans++;
}
  }
  
  if(ans==N){
cout<<"-1"<<endl;
  }
else{
cout<<ans<<endl;
}

}




Measured memory_bytes: 1920
from collections import Counter
def aprime_factorize(n: int) -> list:
    return_list = []
    while n % 2 == 0:
        return_list.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            return_list.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        return_list.append(n)
    return return_list

judge = []
cnt = 0
while len(judge) <= 40:
    for i in range(cnt+1):
        judge.append(cnt)
    cnt += 1
N = int(input())
list = Counter(aprime_factorize(N)).most_common()
res = 0
for i, li in enumerate(list):
    res += judge[li[1]]
print(res)


Measured memory_bytes: 9408