akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace B
{
    public class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var nmxy = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
            var n = nmxy[0];
            var m = nmxy[1];
            var x = nmxy[2];
            var y = nmxy[3];
            var xi = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
            var yi = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
            if (x >= y)
            {
                Console.WriteLine("War");
                return;
            }
            var xMax = xi.Max();
            var yMin = yi.Min();
            Console.WriteLine(xMax < yMin && x < xMax + 1 && xMax + 1 <= y ? "No War" : "War");
        }
    }
}


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

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
            x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

uf = UnionFind(N)

for _ in range(M):
  x,y,z = map(int, input().split())
  uf.union(x-1,y-1)
  
ans = len(uf.roots())
  
print(ans)

Measured memory_bytes: 7856
/*input
5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
*/
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ll long long 
#define vl vector<ll> 
#define pl pair<ll,ll> 
#define vpl vector<pl> 
#define vvl vector<vl> 
using namespace std;


int main() {
ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    
    
    ll n,wt;

    cin >> n >>wt;

    ll t[n+1][wt+1];
    memset(t,-1,sizeof(t));
    vl arr(n+1),value(n+1);
    for(auto i = 0;i < n;i++)cin>>arr[i]>>value[i];

    
    

    for(auto i = 0; i <= n;i++)
    {
    	for(auto j = 0 ; j <= wt ;j++)
    	{
    		if(i == 0 || j==0)t[i][j] = 0;
    		else if(arr[i-1] <= j)t[i][j] = max((value[i-1]+t[i-1][j-arr[i-1]]),t[i-1][j]);
    		else {t[i][j] = t[i-1][j];}
    	}
    }
    
    ll max_cost  = t[n][wt];
	cout << max_cost;

 return 0;
}

Measured memory_bytes: 82480
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T iabs(const T& x) { return max(x, -x); }
// #define abs gabs

vector<int> a[3];

int main() {
    int x[2];
    cin >> x[0] >> x[1];
    a[0] = {1, 3, 5, 7, 8, 10, 12}, a[1] = {2};
    int g[2] = {2, 2};
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int y : a[j]) {
                if (x[i] == y) g[i] = j;
            }
        }
    }
    cerr << g[0] << ' ' << g[1] << endl;
    cout << (g[0] == g[1] ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>

using namespace std;

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

const int mo = 1e9 + 7;

struct Edge {
	int to, idx;
	Edge(int to, int idx) : to(to), idx(idx) {}
};

int N;
vector<Edge> G[100010];
int mx = 0;
int c[100010];

void f(int cur, int par, int used_color)
{
	if (G[cur].size() == 1 and G[cur][0].to == par) { // leaf
		return;
	}

	int counter = 0;
	for (Edge &e : G[cur]) {
		if (e.to == par) continue;
		counter++;
		if (counter == used_color) counter++;
		c[e.idx] = counter;
		f(e.to, cur, counter);
	}

	mx = max(mx, counter);
}

signed main()
{
	cin >> N;
	
	rep(i, N-1) {
		int a, b; cin >> a >> b;
		--a, --b;
		G[a].push_back(Edge(b, i));
		G[b].push_back(Edge(a, i));
	}

	f(0, -1, -1);

	cout << mx << endl;
	rep(i, N-1) {
		cout << c[i] << endl;
	}
}


Measured memory_bytes: 9856
#include <iostream>
#include <vector>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

ll choose2(ll n){
    return n*(n-1)/2;
}

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    rep(i,n) a[i]--;
    vector<int> cnt(n);
    rep(i,n) cnt[a[i]]++;
    ll tot = 0;
    rep(i,n) {
        tot += choose2(cnt[i]);
    }
    rep(i,n) {
        ll ans = tot;
        ans -= choose2(cnt[a[i]]);
        ans += choose2(cnt[a[i]]-1);
        cout << ans << endl;
    }
    return 0;
}

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

using namespace std;

typedef long long int ll;

const int N = 2e5 + 5;

vector < int > p (N), sz (N);

void make () {
  for (int i = 0; i < N; i++) p[i] = i, sz[i] = 1;
}

int find (int u) {
  if (p[u] == u) return u;
  return p[u] = find (p[u]);
}

void merge (int u, int v) {
  u = find (u);
  v = find (v);
  if (u != v) {
    if (sz[u] > sz[v]) swap (u, v);
    p[u] = v;
    sz[v] += sz[u];
  }
}

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

  make();

  int n, k, l;
  cin >> n >> k >> l;
  for (int i = 0; i < k; i++) {
    int u, v;
    cin >> u >> v;
    merge (u, v);
  }

  vector < int > a (n + 1);
  for (int i = 1; i <= n; i++) a[i] = find (i);

  make();

  for (int i = 0; i < l; i++) {
    int u, v;
    cin >> u >> v;
    merge (u, v);
  }

  vector < int > b (n + 1);
  for (int i = 1; i <= n; i++) b[i] = find (i) + N;

  map < pair < int, int >, int > mp;
  for (int i = 1; i <= n; i++) mp[{a[i], b[i]}]++;

  for (int i = 1; i <= n; i++) cout << mp[{a[i], b[i]}] << " ";
  cout << '\n';
}


Measured memory_bytes: 17548
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef pair<int, int> P;
const int c_INF = 111111111;
const int c_mINF = -111111111;
const int c_YET = -1;
const int c_Dx[4] = { 0,0,1,-1 };
const int c_Dy[4] = { 1,-1,0,0 };
const int c_div = 1000000007; //10^9 + 7
const double PI = 3.14159265358979323846;


int main() {

	int N, K;
	scanf("%d%d", &N, &K);

	int ans = 1;

	for (int i = 0; i < N; i++) {
		if (ans <= K) {
			ans *= 2;
		}
		else {
			ans += K;
		}


	}

	printf("%d", ans);













}







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

int main()
{
	int x,n;
   cin >> x >> n;
   vector<bool> a(102);

   for(int i = 0;i<n;i++)
   {
      int p;
      cin >> p;
      a[p] = true;
   }
   int ans = 0;
   for(int i = 0;i<=101;i++)
   {
      if(a[i])continue;
      if(abs(ans-x)>abs(i-x))ans = i;
   }
   cout<<ans<<endl;
}

Measured memory_bytes: 3624
#include <iostream>
#include <string>

using namespace std;

int main() {
  int H, W;
  int A[60][60];

  for (int h=0; h<60; h++) {
    for (int w=0; w<60; w++) {
      A[h][w] = 0;
    }
    cout << endl;
  }
  cin >> H >> W;

  for (int h=0; h<H; h++) {
    string l;
    cin >> l;
    for (int w=0; w<l.length(); w++) {
      if (l[w]=='#') {
        A[h+5-1][w+5-1]++;
        A[h+5-1][w+5  ]++;
        A[h+5-1][w+5+1]++;
        A[h+5  ][w+5-1]++;
        A[h+5  ][w+5  ] = -100;
        A[h+5  ][w+5+1]++;
        A[h+5+1][w+5-1]++;
        A[h+5+1][w+5  ]++;
        A[h+5+1][w+5+1]++;
      }
    }
  }

  for (int h=0; h<H; h++) {
    for (int w=0; w<W; w++) {
      if (A[h+5][w+5] < 0) cout << "#";
      else                 cout << A[h+5][w+5];
    }
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
 
int findSumOfDigits(int n){
  int sum=0;
  while(n>0){
    sum += n % 10;
    n /= 10;
  }
  return sum;
}
 
int main(){
  int N,A,B;
  cin >> N >> A >> B;
  int total;
  for(int i=1;i <= N; i++){
    int sum = findSumOfDigits(i);
    if(sum >= A && sum <= B){
      total += i;
    }
  }
    cout << total <<endl;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: usize = read();
    let mut a: Vec<i64> = vec![];
    for _ in 0..n {
        a.push(read());
    }

    let mut ans = 0;
    for i in 0..n {
        let mut ai = a[i];

        while ai % 2 == 0 {
            ai /= 2;
            ans += 1;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
typedef long long ll;
int main() {
  int n;
  while(1) {
    cin >> n;
    if(n == -1) break;
    int cost;
    if(n <= 10) cost = 1150;
    else if(n <= 20) cost = 1150 + 125 * (n - 10);
    else if(n <= 30) cost = 1150 + 125 * 10 + 140 * (n - 20);
    else cost = 1150 + 125 * 10 + 140 * 10 + 160 * (n - 30);
    cout << 4280 - cost << endl;
  }
  return 0;
}


Measured memory_bytes: 3040
use std::io::*;

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let n: usize = itr.next().unwrap().parse().unwrap();
    let k: usize = itr.next().unwrap().parse().unwrap();
    let a: Vec<usize> = (0..n)
        .map(|_| itr.next().unwrap().parse().unwrap())
        .collect();

    let mut s: Vec<usize> = vec![0; n + 1];
    for i in 0..n {
        s[i + 1] = s[i] + a[i];
    }

    let mut all = Vec::new();
    for l in 0..n {
        for r in l + 1..n + 1 {
            all.push(s[r] - s[l]);
        }
    }

    for d in (0..61).rev() {
        let mut cnt = 0;
        for i in 0..all.len() {
            if all[i] & (1usize << d) != 0 {
                cnt += 1;
            }
        }
        if cnt >= k {
            let mut new = Vec::new();
            for i in 0..all.len() {
                if all[i] & (1usize << d) != 0 {
                    new.push(all[i]);
                }
            }
            all = new;
        }
    }
    let mut ans = all[0];
    for i in 1..k {
        ans &= all[i];
    }
    println!("{}", ans);
}


Measured memory_bytes: 10360
#include <sstream>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <set>
#include <tuple>
#include <functional>
#include <map>
#include <unordered_map>
#include <queue>
#include <tuple>
#include <random>
#include <stack>

using namespace std;

#define endl '\n'

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using lld = long double;
using ull = unsigned long int;
using ll = long long;



vector<string> read_endpoints(istream& fin) {
  vector<string> ret;

  string line;
  while(getline(fin, line)) {
    if (line.find("staging-back-corp") != line.npos) {
      ret.push_back(line);
    }
  }

  return ret;
}

string print_partition_map(vector<string> endpoints) {
  stringstream ss;

  ss << "{" << endl;
  for ( int i = 0; i < (int)endpoints.size(); i+=3) {
    ss << "\t" << i/3 << "/" << endpoints.size()/3 << " = [" << endl;
    ss << "\t\t\"" << endpoints[i] << "\"" << endl;
    ss << "\t\t,\"" << endpoints[i+1] << "\"" << endl;
    ss << "\t\t,\"" << endpoints[i+2] << "\"" << endl;
    ss << "\t];" << endl;
  }
  ss << "}" << endl;

  return ss.str();
}

class ft {
  vector<ll> f;
public:
  ft(int n) {
    f.resize(n);
  }

  void add(int x, ll v) {
    for (; x < (int)f.size(); x += x & -x) {
      f[x] = max(f[x], v);
    }
  }

  ll get(int x) {
    ll ret = 0;
    for (; x; x -= x & -x) {
      ret = max(ret, f[x]);
    }
    return ret;
  }
};


void solve() {

  int n; cin >> n;
  vector<int> h(n), a(n);
  for (auto& it : h) cin >> it;
  for (auto& it : a) cin >> it;

  map<int, ll> mp;

  ll ans = 0;
  ft mtx{n+1};
  for (int i = 0; i < n; ++i) {
    int v = h[i];
    ll g = a[i];

    mtx.add( v, mtx.get(v-1) + g);
    ans = max(ans, mtx.get(v));
  }

  cout << ans << endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  const int precision = 13;
  cout.precision(precision);
  cout.setf(ios_base::fixed);


  solve();

  return 0;
}


Measured memory_bytes: 3456
h,w=map(int,input().split())
n=int(input())
a=list(map(int,input().split()))
l=[]
for i in range(n):
    l+=[i+1]*a[i]
for i in range(h):
    if i%2:print(*l[w*i:w*(i+1)][::-1])
    else:print(*l[w*i:w*(i+1)])

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

const ll MAXN = 200000;
const ll INF = 1001001001;

ll N, ans=0, tmp=INF, PC[13][13]={{0}}, A[13]={0};
vector<ll> D;

void dfs(vector<ll> v, ll id, ll lid) {
    if(lid<=id) {
        tmp = INF;
        for(int i=0;i<lid;i++) {
            if(v[i]==0) v[i] = D[i];
            else v[i] = 24-D[i];
        }
        for(int i=0;i<lid;i++) {
            for(int j=i+1;j<lid;j++) {
                ll d = abs(v[i]-v[j]);
                d = min(d, 24-d);
                tmp = min(tmp,d);
            }
        }
        ans = max(ans,tmp);
        return;
    }
    if(id>0) {
        if(D[id]==D[id-1]) {
            v[id] = 1-v[id-1];
            dfs(v,id+1,lid);
        }
        else {
            dfs(v,id+1,lid);
            v[id] = 1;
            dfs(v,id+1,lid);
        }
    }
    else {
        dfs(v,id+1,lid);
        v[id] = 1;
        dfs(v,id+1,lid);
    }
}

signed main(){
    cin >> N;
    A[0]++;
    D.push_back(0);
    for(int i=0;i<N;i++) {
        ll a;
        cin >> a;
        A[a]++;
        D.push_back(a);
    }
    sort(D.begin(), D.end());
    if(A[0]>=2||A[12]>=2) {
        cout << 0 << endl;
        return 0;
    }
    for(int i=1;i<=11;i++) {
        if(A[i]>=3) {
            cout << 0 << endl;
            return 0;
        }
    }
    vector<ll> vinit;
    vinit.resize(D.size(),0);
    dfs(vinit,1,D.size());
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3640
#include <math.h>

#include <algorithm>
#include <bitset>
#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

int main() {
  string s;
  cin >> s;
  int a = s[0] - '0';
  int b = s[1] - '0';
  int c = s[2] - '0';
  int d = s[3] - '0';
  int target_val = 7 - a;
  int data_list[3] = {b, c, d};
  bitset<3> ans_bit_set;

  for (int i = 0; i < (1 << ans_bit_set.size()); i++) {
    bitset<3> tmp_set(i);
    int ans = 0;
    for (int j = 0; j < 3; j++) {
      if (tmp_set[2 - j]) {
        ans += data_list[j];
      } else {
        ans -= data_list[j];
      }
    }
    if (ans == target_val) {
      ans_bit_set = tmp_set;
      break;
    }
  }
  string ans;
  ans += s[0];
  for (int i = 0; i < 3; i++) {
    if (ans_bit_set[2 - i]) {
      ans += "+";
    } else {
      ans += "-";
    }
    ans += s[1 + i];
  }
  ans += "=7";

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream> 
#include <cstdio> 
#include <cstdlib> 
#include <cstring> 
#include <cmath> 
#include <algorithm>  
using namespace std; 
const int MAX_N = 3e3 + 5; 
const int Mod = 1e9 + 7; 
int fpow(int x, int y) {
	int res = 1; 
	while (y) { 
		if (y & 1) res = 1ll * res * x % Mod; 
		x = 1ll * x * x % Mod; 
		y >>= 1; 
	} 
	return res; 
} 
const int inv = fpow(2, Mod - 2); 
int N, Q, a[MAX_N]; 
int f[MAX_N][MAX_N]; 
int main () { 
	scanf("%d %d", &N, &Q); 
	for (int i = 1; i <= N; i++) scanf("%d", a + i); 
	for (int i = 1; i <= N; i++) 
		for (int j = 1; j <= N; j++) f[i][j] = a[i] < a[j]; 
	for (int i = 1; i <= Q; i++) { 
		int x, y; scanf("%d %d", &x, &y); 
		f[x][y] = f[y][x] = 1ll * (f[x][y] + f[y][x]) * inv % Mod; 
		for (int j = 1; j <= N; j++) { 
			if (j == x || j == y) continue; 
			f[x][j] = f[y][j] = 1ll * (f[x][j] + f[y][j]) * inv % Mod; 
			f[j][x] = f[j][y] = 1ll * (f[j][x] + f[j][y]) * inv % Mod; 
		} 
	} 
	int ans = 0; 
	for (int i = 1; i <= N; i++) 
		for (int j = 1; j < i; j++) 
			ans = (ans + f[i][j]) % Mod; 
	printf("%lld\n", 1ll * ans * fpow(2, Q) % Mod); 
    return 0;  
} 

Measured memory_bytes: 35456
n = int(input())
al = list(map(int,input().split()))

from collections import defaultdict
dic = defaultdict(int)

for a in al:
    dic[a] += 1

sum_d = 0
for a in dic:
    sum_d += dic[a] * (dic[a] - 1) // 2

for a in al:
    k = dic[a] * (dic[a] - 1) // 2
    l = (dic[a] - 2) * (dic[a] - 1) // 2
    print(sum_d - k + l)




Measured memory_bytes: 25716
#include "bits/stdc++.h"
using namespace std;
 
#define REP(i, n) for(ll i = 0;i < n;i++)
#define REP1(i, n) for(ll i = 1;i < n;i++)
#define REPR(i, n) for(ll i = n-1;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
 
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
 
#define ll long long
#define ALL(a)  (a).begin(),(a).end()
 
#define pb(a) push_back(a)
#define MOD 1000000007
 
 
 
 
 
int main(){
  ll n,m;
  ll ans=0LL;
  cin >> n >> m;
  vector<ll> s(n);
  vector<ll> t(m);
  
  REP(i,n)cin>>s[i];
  REP(i,m)cin>>t[i];

  vector<ll> dp0(n+1,0LL);
  vector<ll> dp1(n+1,1LL);
  dp0[0]=1LL;
  dp1[0]=1LL;
  REP(i,m){
    for(int j=0;j<n;j++){
      if (t[i]==s[j]){
        dp0[j+1]=dp0[j]+dp1[j+1];
      }else{
        dp0[j+1]=dp0[j]+dp1[j+1]-dp1[j]+MOD;
      }
      dp0[j+1]%=MOD;
    }
    REP(j,n)dp1[j+1]=dp0[j+1];
  }

cout<<dp0[n]<<endl;

  return 0;
}

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

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define tc(t) int t; cin>>t; while(t--)
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s, s1;
    cin >> s >> s1;
    int c = 0;

    if (s[0] == s1[0]) {
        c++;
    }  if (s[1] == s1[1]) {
        c++;
    }  if (s[2] == s1[2]) {
        c++;
    }
    cout << c << endl;
}

Measured memory_bytes: 3588
n, m = map(int, input().split())
s, o, ans = 0, 1, 0
se = []
if 0 <= n <= 100 and 0<= m <= 100 and 2 <= n+m:
    for i in range(1, n+1):
        se.append(s)
        s += 2
    for i in range(1, m+1):
        se.append(o)
        o += 2
    for x in se:
        for y in range(len(se)):
            if (x + se[y]) % 2 == 0 and x!=se[y]:
                ans += 1 
    print(int(ans/2))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include<iostream>
using namespace std;
int main()
{
    string S;
    cin >> S;

    int size = S.size();
    int i = 0;
    vector<string> vec{"remaerd", "maerd", "resare", "esare"};
    bool is_ok = true;
    reverse(S.begin(), S.end());
    while (i < size) {
	    bool _continue = false;
	    for (int j = 0; j < vec.size(); j++) {
		    string val = vec[j];
		    string sub_s = S.substr(i, val.size());
		    if (sub_s == val) {
			    i += val.size();
			    _continue = true;
			    break;
		    }
	    }

	    if (!_continue) {
		    is_ok = false;
		    break;
	    }
    }

    if (is_ok) {
    cout << "YES" << endl;
    } else {
    cout << "NO" << endl;
    }
    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define mp make_pair
#define inlld(x) scanf("%lld", &x)
#define ind(x) scanf("%d", &x)
#define inlld2(x, y) scanf("%lld%lld", &x, &y)
#define inlld3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z)
#define ind2(x, y) scanf("%d%d", &x, &y)
#define ind3(x, y, z) scanf("%d%d%d", &x, &y, &z)

const int N=1e5+5;
const int MOD=1e9+7;

typedef long long ll;
typedef long double ld;

using namespace std;

set<int>R, G, B;

int main()
{
	int n;
	string x;
	cin>>n>>x;
	// int n = x.length();
	for(int a = 0; a < n; a++)
	{
		if(x[a] == 'R')
			R.insert(a);
		else if(x[a] == 'G')
			G.insert(a);
		else
			B.insert(a);
	}
	ll ans = (ll)R.size() * (ll)B.size() * (ll)G.size();
	for(auto it1 = R.begin(); it1 != R.end(); it1++)
		for(auto it2 = G.begin(); it2 != G.end(); it2++)
			if( (*it1 + *it2) % 2 == 0 && B.find((*it1 + *it2) / 2) != B.end())
				ans--;
	for(auto it1 = B.begin(); it1 != B.end(); it1++)
		for(auto it2 = G.begin(); it2 != G.end(); it2++)
			if((*it1 + *it2) % 2 == 0 && R.find((*it1 + *it2) / 2) != R.end())
				ans--;
	for(auto it1 = R.begin(); it1 != R.end(); it1++)
		for(auto it2 = B.begin(); it2 != B.end(); it2++)
			if((*it1 + *it2) % 2 == 0 && G.find((*it1 + *it2) / 2) != G.end())
				ans--;
	printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 3856
#include <iostream>
#include <numeric>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
int Max(int(a), int(b), int(c)) {
	return max(max(a, b), c);
}
int Min(int(a), int(b), int(c)) {
	return min(min(a, b), c);
}





int main() {

	ll N,an=1;
	cin >> N;
	while (an <= N) {
		an *= 2;
	}
	cout << an/2 << endl;

}




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

int main() {
  int N;
  cin >> N;
  int sum=0;
  for(int i=0;i<N;i++){
    int l,r;
    cin >> l >> r;
    sum+=r-l+1;
  }
  cout << sum << endl;
}


Measured memory_bytes: 384
#include<cstdio>

int main() {
    int S;
    scanf("%d",&S);
    int h = S / 3600;//時間
    S %= 3600;// S = S % 3600
    int m = S / 60;//分
    int s = S % 60;//秒

    printf("%d:%d:%d\n",h,m,s);
    return 0;
}


Measured memory_bytes: 2672
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String a = sc.next();
		boolean ans = true;
		char c[] = a.toCharArray();
		int n = a.length();
		if (c[0] != 'A') {
			ans = false;
		}
		int cc = 0;
		for (int i = 2; i <= n - 2; i++) {
			if (c[i] == 'C') {
				cc++;
			}

		}

		if (cc != 1) {
			ans = false;
		}

		for (int i = 0; i <= n - 1; i++) {
			if (c[i] == 'B' || c[i] == 'D' || c[i] == 'E' || c[i] == 'F'
					|| c[i] == 'G' || c[i] == 'H' || c[i] == 'I' || c[i] == 'J'
					|| c[i] == 'K' || c[i] == 'L' || c[i] == 'N' || c[i] == 'M'
					|| c[i] == 'O' || c[i] == 'P' || c[i] == 'Q' || c[i] == 'R'
					|| c[i] == 'S' || c[i] == 'T' || c[i] == 'U' || c[i] == 'V'
					|| c[i] == 'W' || c[i] == 'X' || c[i] == 'Y' || c[i] == 'Z') {
				ans = false;
			}

		}
		if(ans){
			System.out.println("AC");
		}else{System.out.println("WA");}

	}
}

Measured memory_bytes: 21844
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let n: usize = sc.read();
    let mut hp = (0..n)
        .map(|_| (sc.read::<i64>(), sc.read::<i64>()))
        .collect::<Vec<_>>();
    hp.sort_by(|&(h1, p1), &(h2, p2)| {
        let a = h1 - p2;
        let b = h2 - p1;
        a.cmp(&b)
    });

    let mut dp = vec![1 << 50; n + 1];
    dp[0] = 0;
    for i in 0..n {
        let (h, p) = hp[i];
        for cur in (0..n).rev() {
            if dp[cur + 1] > dp[cur] + p && dp[cur] <= h {
                dp[cur + 1] = dp[cur] + p;
            }
        }
    }
    for i in (0..=n).rev() {
        if dp[i] < 1 << 50 {
            println!("{}", i);
            return;
        }
    }
}

/// t <= h1 && t+p1 <= h2 ... t+p1+p2
/// t > h1 && t <= h2 ... t+p2
/// t <= h1 && t+p1 > h2 ... t+p1

/// t+p1 > h2 && t<=h2 && t+p2<=h1
/// h2-p1 < t <= h1-p2

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        Self(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 2320
#include<bits/stdc++.h>
#define maxn 3005
#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)
#define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--)
using namespace std;

int n,P,S[maxn][maxn],C[maxn][maxn],pw[maxn];
int upd(int x){ return x += x >> 31 & P; }
int main(){
	scanf("%d%d",&n,&P);
	rep(i,S[0][0]=C[0][0]=1,n) rep(j,C[i][0]=1,i) C[i][j] = upd(C[i-1][j-1] + C[i-1][j] - P) % P;
	rep(i,1,n) rep(j,S[i][0]=1,i) S[i][j] = (S[i-1][j] * (j+1ll) + S[i-1][j-1]) % P;
	int ans = 0 , ppw = 2;
	rep(i,0,n) pw[i] = 1;
	per(k,n,0){
		int sm = 0;
		rep(i,0,k) sm = (sm + 1ll * S[k][i] * pw[i]) % P;
		ans = (ans + (k&1?-1ll:1ll)*C[n][k]*ppw%P*sm)%P;
		int p2 = 1;
		rep(i,0,n) pw[i] = 1ll * p2 * pw[i] % P , p2 = 2ll * p2 % P;
		ppw = ppw * 1ll * ppw % P;
	}
	printf("%d\n",(ans+P)%P);
}

Measured memory_bytes: 58908
def dfs(v, n, visited):
  passed = True
  for i in range(n):
    if not visited[i]:
      passed = False
  if passed:
    return 1
  ret = 0
  for i in range(n):
    if (v, i) not in graph:
      continue
    if not graph[(v, i)]:
      continue
    if visited[i]:
      continue
    visited[i] = True
    ret += dfs(i, n, visited)
    visited[i] = False
  return ret

n, m = map(int, input().split())
graph = {}
for _ in range(m):
  a, b = map(int, input().split())
  graph[(a-1,b-1)] = True
  graph[(b-1,a-1)] = True
visited= [False] *n
visited[0] = True
print(dfs(0, n, visited))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int INF = 1e9;
const int MOD = INF+7;
#define rep(i,N) for(int (i)=0;(i)<(N);++(i))
#define rrep(i,N) for(int (i)=(N-1);(i)>0;--i)
#define FOR(i,j,N) for(int (i)=(j);(i)<(N);++(i))
#define put(n) cout<<(n)<<endl;
#define all(v) v.rbegin(),v.rend()
#define MP make_pair
#define pb push_back
using P = pair<int,int>;

signed main(){
	string S;
	cin >> S;
	if(S[0] == S[1] || S[1] == S[2] || S[2] == S[3]) cout << "Bad" << endl;
	else cout << "Good" << endl;

}


Measured memory_bytes: 256
N=int(input())
G=[[]for i in range(N+1)]
for i in range(N-1):
    a,b,c=map(int,input().split())
    G[a].append((b,c))
    G[b].append((a,c))
Q,K=map(int,input().split())
from collections import deque
dist=[-1]*(N+1)
dist[K]=0
q=deque()
q.append(K)

while len(q):
    p=q.popleft()
    for x,c in G[p]:
        if dist[x]!=-1:
            continue
        dist[x]=dist[p]+c
        q.append(x)

for i in range(Q):
    x,y=map(int,input().split())
    print(dist[x]+dist[y])

Measured memory_bytes: 81824
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <set>
#include <iomanip>
#include <stdio.h>
#include <sstream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
  long long int x;
  cin>>x;
   if(x>=30){
     cout<<"Yes"<<endl;
   }else{
     cout<<"No"<<endl;
   }
}

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

int main() {
  int n; cin >> n;
  struct Edge { int to, w; };
  vector< vector<Edge> > g(n);
  for (int i = 0; i < n - 1; ++i) {
    int u, v, w; cin >> u >> v >> w, --u, --v;
    g[u].emplace_back(Edge{v, w});
    g[v].emplace_back(Edge{u, w});
  }
  vector<int> sz(n);
  long long res = 0;
  int mn = 1e9;
  auto dfs = [&](const auto& dfs, int v, int p) -> void {
    sz[v] = 1;
    for (const auto& e : g[v]) if (e.to != p) {
      dfs(dfs, e.to, v);
      if (2 * sz[e.to] == n) mn = e.w;
      res += 2LL * e.w * min(sz[e.to], n - sz[e.to]);
      sz[v] += sz[e.to];
    }
  };
  dfs(dfs, 0, -1);
  auto ndfs = [&](const auto& ndfs, int v, int p) -> int {
    for (const auto& e : g[v]) if (e.to != p) {
      if (sz[e.to] > n / 2) {
        return ndfs(ndfs, e.to, v);
      }
    }
    return v;
  };
  if (mn == 1e9) for (const auto& e : g[ndfs(ndfs, 0, -1)]) {
    mn = min(mn, e.w);
  }
  res -= mn;
  cout << res << "\n";
}

Measured memory_bytes: 8960
#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

const long MOD = 1000000007;
typedef pair<int, int> P;
typedef long long ll;

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

    P c[M];
    map<P, int> ind;
    for(int i=0; i<M; i++){
        int p, y;
        cin >> p >> y;
        c[i] = P(y, p);
        ind[P(y,p)] = i;
    }

    sort(c, c+M);

    map<int, int> m;
    P ans[M];
    for(int i=0; i<M; i++){
        int p = c[i].second;
        int y = c[i].first;

        int num;
        if(m.count(p) == 0){
            num = 1;
            m[p] = 1;
        }else{
            m[p]++;
            num = m[p];
        }
        ans[ind[(P(y,p))]] = P(p, num);
    }

    for(int i=0; i<M; i++){
        int p = ans[i].first;
        int num = ans[i].second;
        printf("%06d", p);
        printf("%06d", num);
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 13952
/*
* Problem Statement: 
* Author: ganpa
*/
#include <bits/stdc++.h>

#define sz(x) (int)(x).size()
#define endl '\n'
typedef long long int ll;
typedef long double ld;
typedef unsigned long long int ull;
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int d, t, s;
    cin >> d >> t >> s;
    if (s * t >= d)
        cout << "Yes\n";
    else
        cout << "No\n";
}

Measured memory_bytes: 3644
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string>
#include<iostream>
#include<cctype>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include <algorithm>
#include<math.h>
#include<set>
#include<map>
#include<iomanip>

//#include<bits/stdc++.h>


using namespace std;


int main() {

	int n, a = 0;
	string g;
	cin >> n >> g;

	int h = 0;
	for (int i = 0; i < n; i++) {
		if (g[i] == 'I')a++;
		else a--;
		if (a > h)h = a;
	}
	cout << h << endl;
	return 0;

}




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

using namespace std;

typedef pair<int, int> P;

int A, B, C, X;

int solve() {
  int res = 0;
  for (int i = 0; i <= A; ++i) {
    for (int j = 0; j <= B; ++j) {
      int rest = X - 500 * i - 100 * j;
      if (rest < 0) continue;
      int c = rest / 50;
      if (c <= C) res++;
    }
  }
  return res;
}

int main() {
  cin >> A >> B >> C >> X;
  int res = solve();
  cout << res << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <functional>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <bitset>
#define mp make_pair
#define YES cout<<"YES"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl
#define rep(i,n) for(int i=0;i<n;i++)
#define INF (1<<30)
#define LLINF (1LL<<60)
//#define MOD 998244353
#define MOD 1000000007
#define PI 3.14159265358979
using ll = long long;
using namespace std;

int main(){
    int x,n;
    bool exist[115]={};//true:exist
    cin>>x>>n;
    rep(i,n){
        int t;
        cin>>t;
        exist[t]=true;
    }
    int mindiff=INF;
    int ans=0;
    for(int i=110;i>=-10;i--){
        if(exist[i]==false){
            int diff=abs(x-i);
            if(diff<=mindiff){
                mindiff=diff;
                ans=i;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}



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

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(a) max((a),-(a))
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repe(i,n) rep(i,(n)+1)
#define per(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define pere(i,n) rep(i,(n)+1)
#define all(x) (x).begin(),(x).end()
#define SP <<" "<<
#define RET return 0
#define MOD 1000000007
#define INF 1000000000000000000

typedef long long LL;
typedef long double LD;

int main(){
  int n;
  cin >> n;
  char c;
  int x=0;
  int ans=0;
  for(int i=0;i<n;i++){
    cin >> c;
    if(c=='I'){
      x++;
    }else{
      x--;
    }
    ans=max(ans,x);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
def solve(n, r, pc):
    deck = [n+1-i for i in range(1,n+1)]
    for p, c in pc:
        deck = deck[p-1:p+c-1] + deck[0:p-1] + deck[p+c-1:]
    return deck[0]

def main():
    ans = []
    while True:
        n, r = map(int, input().split())
        if (n==0) and (r==0):
            break
        pc = [list(map(int, input().split())) for i in range(r)]
        ans.append(solve(n, r, pc))
    
    for i in ans:
        print(i)
    
main()


Measured memory_bytes: 5664
import javax.print.DocFlavor;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class  Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] l = reader.readLine().split(" ");
        int N = Integer.parseInt(l[0]);
        int K = Integer.parseInt(l[1]);
        System.out.println(1+(int) (Math.log(N)/Math.log(K)));
    }
}


Measured memory_bytes: 21204
import heapq
heap = []
while 1:
    order = input().split()
    if order[0] == "insert":
        k = -int(order[1])
        heapq.heappush(heap,k)
    elif order[0] == "extract":
        print(-heapq.heappop(heap))
    elif order[0] == "end":
        break
        



Measured memory_bytes: 45304
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define IOS { ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); }
#define ll long long
#define umapii unordered_map<int,int>
#define umapll unordered_map<ll,ll>
#define mapll map<ll,ll>
#define mapii map<int,int>
#define pi pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define vs vector<string>
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pi>
#define vpll vector<pll>
#define vvi vector<vi>
#define vvll vector<vll>
#define endl '\n'
#define all(v) (v).begin(),(v).end()
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define MP(a,b) make_pair(a,b)
#define debug(x)       cerr<< #x << " : " << x << endl;
#define debuga(A,N)    cerr<< #A <<" : [";for(int i = 0; i<N;i++) cerr<<A[i]<<" "; cerr<<"]\n";
#define debuga2(A,N,M) cerr<< #A << " : \n"; for(int i=0;i<N;i++){cerr<<"[";for(int j=0;j<M;++j) cerr<<A[i][j]<<" ";cerr<<"]\n";}
#define debugp(p)      cerr<< #p <<" : "<<"("<<(p).first<<","<<(p).second<<")\n";
#define debugv(v)      cerr<< #v <<" : "<<"[";for(int i = 0; i< (v).size(); i++) cerr<<v[i]<<" "; cerr<<"]\n";
#define debugv2(v)     cerr<< #v << " : \n"; for(int i=0;i<v.size();i++){cerr<<"[";for(int j=0;j<(v[i].size());++j) cerr<<v[i][j]<<" ";cerr<<"]\n";}
#define debugs(m)      cerr<< #m <<" : [ "; for(auto itr = m.begin(); itr!=m.end();itr++) cerr<<*itr<<" "; cerr<<"]\n";
#define debugm(m)      cerr<< #m <<" : [ "; for(auto itr = m.begin();itr!=m.end(); itr++) cerr<<"("<<itr->first<<","<<itr->second<<") ";cerr<<"]\n";

/* ordered set: 
tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>
member functions :
1. order_of_key(k) : number of elements strictly lesser than k
2. find_by_order(k) : k-th element in the set
*/

inline ll gcd (ll x , ll y){
    if (x < y) swap (x , y);
    while (y){
        ll temp = y;
        y = x % y;
        x = temp; 
    }
    return x;
}

inline ll modexp(ll x, ll ex , ll md) {
    ll ans = 1ll;
    while (ex > 0) {
        if (ex & 1ll) ans = (ans * x) % md;
        ex >>= 1ll;
        x = (x * x) % md;
    }
    return ans;
}

const int inf = 1e9 + 7;

void solve(){
   string s;
   cin >> s;
   char ch = s.back();
   if (ch == '2' || ch == '4' || ch == '5' || ch == '7' || ch == '9'){
    cout << "hon\n";
   } else if (ch == '0' || ch == '1' || ch == '6' || ch == '8'){
    cout << "pon\n";
   } else cout << "bon\n";
}
int main(){
    IOS;
    int T = 1;
    // cin >> T;
    for(int i = 1; i <= T; i++){
        // cout << "Case #" << i << ": ";
        solve();
    }

    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";       
}


Measured memory_bytes: 3764
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
  ll n;
  cin>>n;ll sum=0;
  for(auto i=1;i<=n;++i)
    for(auto j=1;j<=n;++j)
      for(auto k=1;k<=n;++k)
      {
        auto x=__gcd(i,j);
        sum+=__gcd(x,k);
      }
  cout<<sum<<endl;
}

Measured memory_bytes: 3632
n = int(input())
A = [int(input()) for _ in range(n)]

first = max(A)
count, index = A.count(first), A.index(first)
A.sort()
second = A[-2]

if count > 1:
    ANSWERS = [first] * n
    for answer in ANSWERS:
        print(answer)
else:
    ANSWERS = [first] * n
    ANSWERS[index] = second
    for answer in ANSWERS:
        print(answer)


Measured memory_bytes: 14084
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define em emplace
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, n) for(int i = 1; i <= n; i++)
template<class T> inline int chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline int chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
constexpr int INF = 1<<30;
constexpr ll LINF = 1LL<<58;
constexpr int mod = 1000000007;

int dp[100010];

int main(){
    int n, k;
    cin >> n >> k;
    int H[100010];
    for (int i = 2; i <= n; i++) dp[i] = INF;
    for (int i = 0; i < n; i++) cin >> H[i + 1];
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= k; j++) {
            chmin(dp[i + j], dp[i] + abs(H[i] - H[i + j]));
        }
    }
    cout << dp[n] << endl;
    return 0;
}

Measured memory_bytes: 1024
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;

public static class P
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine());
        var sections = Enumerable.Repeat(0, n).Select(_ =>
        {
            var a = Console.ReadLine().Split().Select(int.Parse).ToArray();
            return new Tuple<int, int>(a[0] - a[1], a[0] + a[1]);
        }).OrderBy(x => x.Item2).ToArray();
        int res = 0;
        var last = int.MinValue;
        foreach (var section in sections)
        {
            if (last <= section.Item1)
            {
                res++;
                last = section.Item2;
            }
        }
        Console.WriteLine(res);
    }
}

Measured memory_bytes: 27060
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>

constexpr int ALPHA_SIZE = 'z' - 'a' + 1;
using datum = std::array<int, ALPHA_SIZE>;
std::vector<datum> S;
constexpr int MAX_SIZE = 10;

int main(void){
    int n; scanf("%d", &n);
    S.resize(n);
    for(int i = 0; i < n; ++i){
        getchar();
        for(int j = 0; j < ALPHA_SIZE; ++j) S[i][j] = 0;
        for(int j = 0; j < MAX_SIZE; ++j) S[i][getchar()-'a']++;
    }
    std::sort(S.begin(), S.end());
    long long int res = 0;
    int i;
    while(i < n){
        long long int cnt = 0;
        while(i+cnt < n and S[i] == S[i+cnt]) cnt++;
        i += cnt;
        res += cnt * (cnt-1) / 2;
    }
    printf("%lld\n", res);
    return 0;
}

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

using namespace std;

typedef long long ll;

int main()
{
	int n, m, l;
	cin >> n >> m >> l;

	vector<vector <ll>>A(n, vector<ll>(m));
	vector<vector <ll>>B(m, vector<ll>(l));
	vector<vector <ll>>C(n, vector<ll>(l)); // C = A * B

	for (int row = 0; row < n; row++){
		for (int column = 0; column < m; column++){
			cin >> A[row][column];
		}
	}

	for (int row = 0; row < m; row++) {
		for (int column = 0; column < l; column++) {
			cin >> B[row][column];
		}
	}

	for (int row = 0; row < n; row++) {
		for (int column = 0; column < l; column++) {
			C[row][column] = 0;
			for (int i = 0; i < m; i++){
				C[row][column] += A[row][i] * B[i][column];
			}
		}
	}

	for (int row = 0; row < n; row++) {
		for (int column = 0; column < l; column++) {
			if(column) cout << " ";
			cout << C[row][column];
		}
		cout << endl;
	}

	return 0;
}



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

namespace AtCoder
{
    class Program
    {
        static void Main()
        {
            var s = Console.ReadLine();
            int k = int.Parse(Console.ReadLine());
            var subsList = new List<string>();
            var charList = new List<char>();
            for (int i = 0; i < s.Length; i++) charList.Add(s[i]);
            charList = charList.Distinct().OrderBy(c => c).ToList();
            subsList.Add(charList[0].ToString());

            for (int i = 1; i <= 4; i++)
                for (int j = 0; j < s.Length - i; j++)
                {
                    if (s[j] == charList[0]) subsList.Add(s.Substring(j, i + 1));
                }
            if (charList.Count > 1)
            {
                subsList.Add(charList[1].ToString());
                for (int i = 1; i <= 4; i++)
                    for (int j = 0; j < s.Length - i; j++)
                    {
                        if (s[j] == charList[1]) subsList.Add(s.Substring(j, i + 1));
                    }
            }
            if (charList.Count > 2)
            {
                subsList.Add(charList[2].ToString());
                for (int i = 1; i <= 4; i++)
                    for (int j = 0; j < s.Length - i; j++)
                    {
                        if (s[j] == charList[2]) subsList.Add(s.Substring(j, i + 1));
                    }
            }

            Console.WriteLine(subsList.Distinct().OrderBy(x => x).Where((x, y) => y == k - 1).First());
        }
    }
}

Measured memory_bytes: 14048
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, W: "List[str]"):
    ans = YES
    for i in range(N-1):
        if W[i][-1] != W[i+1][0]:
            ans = NO
            break
    for i in range(N):
        if W[i] in W[:i]:
            ans = NO
            break
    print(ans)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, W)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
import sys
sys.setrecursionlimit(202020)

N = int(input())
won = [[] for i in range(N)]
for i in range(1,N):
    a = int(input()) - 1
    won[a].append(i)

def height(v):
    if not won[v]: return 0
    hs = [height(op) for op in won[v]]
    ret = 0
    for i,h in enumerate(sorted(hs)):
        ret = max(ret, h + len(hs) - i)
    return ret

print(height(0))

Measured memory_bytes: 227992
#include <cstdio>
#include <cstring>
using namespace std;
bool a[100005], c[100005];
int n;
int getans(int k){
	int i;
	memset(c, 0, sizeof(c));
	for(i=2; i<=k; i++){
		c[i]=c[i]^c[i-1];
		if((a[i]^c[i])^(a[i-1]^c[i-1])){
			if(i+k-1>n)
				return false;
			c[i]=!c[i];
			c[i+k-1]=!c[i+k-1];
		}
	}
	return true;
}
int main(){
	int i, l, r, mid;
	char ch;
	
	n=0;
	ch=getchar();
	while(~ch and ch>>5){
		a[++n]=ch&1; 
		ch=getchar();
	}
	l=1;
	r=n;
	while(l<r){
		mid=(l+r+1)>>1;
		if(getans(mid))
			l=mid;
		else
			r=mid-1;
	}
	printf("%d", l);
	return 0;
} 

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

int main(){
	int n,m;
	while(cin>>n>>m,n,m){
		int mat[1002];
		vector<int>hanzen;
		for(int i=0;i<n;i++)cin>>mat[i];
		mat[n]=0;
		
		for(int i=0;i<=n;i++)
		for(int j=i;j<=n;j++)hanzen.push_back(mat[i]+mat[j]);
		
		sort(hanzen.begin(),hanzen.end());
		
		int ans=0;
		
		for(int i=0;i<hanzen.size();i++){
			int a=m-hanzen[i];
			
			int li=-1,ub=hanzen.size();
			while(ub-li>1){
				int md=(li+ub)/2;
				if(hanzen[md]>=a){
					ub=md;
					}
				else{
					li=md;
					if(ans<hanzen[i]+hanzen[md])ans=hanzen[i]+hanzen[md];
					if(ans==m)goto finloop;
					}	
				}
			}
			finloop:
			cout<<ans<<endl;
		}
		return 0;
	}

Measured memory_bytes: 6848