akhauriyash/Code-Regression huggingface dataset:
import numpy as np

MAX_DIGIT = 60
MOD = 10**9 + 7

N = int(input())
A = np.array([int(a) for a in input().split()])

answer = 0
for d in range(MAX_DIGIT + 1):
    A, r = (A>>1), A % 2
    s = int(r.sum())
    base = (1<<d) % MOD #this may be key
    answer += (base * s * (N - s)) % MOD

answer %= MOD
print(answer)


Measured memory_bytes: 48836
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int M = 256;

int n, I[M];

long double calc(int S, int A, int C){
  int r = S, cnt[M];
  fill(cnt, cnt+M, 0);
  for(int i=0;i<n;i++){
    r = (A * r + C) % M;
    cnt[(I[i] + r) % M]++;
  }
  long double res = 0.0;
  for(int i=0;i<M;i++) if(cnt[i]) res -= (long double)cnt[i] * (log((double)cnt[i]) - log((double)n));
  return res;
}

main(){
  while(cin >> n && n){
    for(int i=0;i<n;i++) cin >> I[i];
    int ans[3];
    long double valm = 1e77;
    for(int S=0;S<=15;S++){
      for(int A=0;A<=15;A++){
        for(int C=0;C<=15;C++){
          long double tmp = calc(S, A, C);
          if(valm > tmp){
            ans[0] = S;
            ans[1] = A;
            ans[2] = C;
            valm = tmp;
          }
        }
      }
    }
    cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << endl;
  }
}

Measured memory_bytes: 1204
from math import gcd

MOD = 10**9+7
N = int(input())
d = {}
zero = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero += 1
        continue

    # a/bでbが0にならないように、かつ両方正の整数となるまで(a,b)->(-b,a)に変換
    flip = 0
    while not (a >= 0 and b > 0):
        a, b = -b, a
        flip ^= 1

    g = gcd(a, b)
    a //= g
    b //= g
    if not (a, b) in d:
        d[(a, b)] = [0, 0]
    d[(a, b)][flip] += 1

ans = 1
for (v1, v2) in d.values():
    ans *= pow(2, v1, MOD) + pow(2, v2, MOD)-1
    ans %= MOD
ans -= 1
ans += zero
ans %= MOD
print(ans)


Measured memory_bytes: 137956
import java.util.*;
 
public class Main {

    private static int MOD = 1_000_000_007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int S = sc.nextInt();

        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < K; i++) {
            ans.append(S).append(" ");
        }
        if (S < 1_000_000_000) {
            for (int i = K; i < N; i++) {
                ans.append(S+1).append(" ");
            }
        } else {
            for (int i = K; i < N; i++) {
                ans.append(1).append(" ");
            }
        }

        System.out.println(ans.toString());
    }
}


Measured memory_bytes: 31520
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#include<utility>
#include<math.h>

using namespace std;
typedef pair<int, int> P;
typedef long long int ll;

const int INF = 1<<30;

int main(){
  int n;cin>>n;
  string s;cin>>s;
  int r=0, l=0;
  for(int i=0;i<n;i++){
    if(s[i]=='('){
      r++;
    }else{
      if(r>0){
        r--;
      }else{
        l++;
      }
    }
  }
  cout<<string(l, '(')+s+string(r, ')')<<endl;
}


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

int main(){
  int a, b;
  char op;
  

  while(true){
    cin >> a >> op >> b;
    if (op == '?') break;
    switch(op){
      case '+':
        cout << a + b << endl;
        break;
      case '-':
        cout << a - b << endl;
        break;
      case '*':
        cout << a * b << endl;
        break;
      case '/':
        cout << a / b << endl;
        

    }
  }
}


Measured memory_bytes: 3100
b,w=map(int,input().split())
n=b+w
mod=10**9+7
fra=[1]*(n+2)
inv=[1]*(n+2)
p2=[1]*(n+2)
t=1
for i in range(1,n+2):
    t*=i
    t%=mod
    fra[i]=t
t=pow(fra[n+1],mod-2,mod)
p=pow(pow(2,n+1,mod),mod-2,mod)
for i in range(n+1,0,-1):
    inv[i]=t
    t*=i
    t%=mod
    p2[i]=p
    p*=2
    p%=mod
def comb(n,r):
    return fra[n]*inv[n-r]*inv[r]%mod
nb=0
nw=0
for i in range(1,n+1):
    print(((1-nb-nw)*inv[2]+nw)%mod)
    if b<=i:
        nb+=comb(i-1,b-1)*p2[i]
        nb%=mod
    if w<=i:
        nw+=comb(i-1,w-1)*p2[i]
        nw%=mod

Measured memory_bytes: 28868
N = gets.to_i
As = gets.split.map(&:to_i)
MOD = 1E9.to_i + 7

def mpow(x, n)
  ans = 1
  while n > 0
    if n.even?
      x = x * x % MOD
      n >>= 1
    else
      ans = ans * x % MOD
      n -= 1
    end
  end
  ans
end

@f = (1 .. N + 1).inject([x = 1]){|a, n| a << x = x * n % MOD}
@i = []; @i[N + 1] = mpow(@f[N + 1], MOD - 2)
(N + 1).downto(1){|n| @i[n - 1] = @i[n] * n % MOD}

def mc(n, k)
  return 0 if k > n
  @f[n] * @i[n - k] * @i[k]
end

d = As.group_by(&:itself).flat_map{|k, v| v.one? ? [] : k}[0]
a, b = As.index(d) + 1, As.rindex(d) + 1
(1 .. N + 1).each{|k| puts (mc(N + 1, k) - mc(N + a - b, k - 1)) % MOD}

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

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

  for (int i = 0; i < s.size(); i++) {
    int res = 'z' - s[i] + 1;

    if (s[i] == 'a') continue;

    if (res <= K) {
      s[i] = 'a';
      K -= res;
    }
  }

  if (K > 0) {
    int tmp = s[s.size() - 1] - 'a';
    tmp += K % 26;
    s[s.size() - 1] = (char)(tmp % 26 + 'a');
  }

  cout << s << endl;
  return 0;
}


Measured memory_bytes: 512
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

using ll = long long;

const int mod = 1e9 + 7;

// O(N * K^2)

void add_self(int& a, int b) {
    a += b;
    if(a >= mod) {
        a -= mod;
    }
}
void sub_self(int& a, int b) {
    a -= b;
    if(a < 0) {
        a += mod;
    }
}

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<int> dp(k + 1);
    // dp[i] - the number of ways such that we used i candies so far
    dp[0] = 1;
    for(int child = 0; child < n; ++child) {
        int up_to;
        scanf("%d", &up_to);
        vector<int> fake(k + 1);
        for(int used = k; used >= 0; --used) {
            int tmp = dp[used];
            int L = used + 1;
            int R = used + min(up_to, k - used);
            if(L <= R) {
                add_self(fake[L], tmp);
                if(R + 1 <= k) {
                    sub_self(fake[R+1], tmp);
                }
            }
            //~ for(int i = L; i <= R; ++i) {
                //~ add_self(dp[i], tmp);
            //~ }
        }
        int prefix_sum = 0;
        for(int i = 0; i <= k; ++i) {
            add_self(prefix_sum, fake[i]);
            add_self(dp[i], prefix_sum);
        }
    }
    printf("%d\n", dp[k]);
}


Measured memory_bytes: 4140
#include <bits/stdc++.h>
using namespace std;
// define
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define ADD(a, b) a = (a + b) % mod
#define SUB(a, b) a = (a+mod-b)%mod
#define MUL(a, b) a = (((a)%mod) * ((b)%mod)) % mod
#define rollcall cout << "I'm Sucu." << endl;
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define dmt(x, y, z) make_tuple(x, y, z)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define fi first
#define se second
// debug
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p){
  os << "(" << p.first << "," << p.second << ")";return os;
}
template <typename T, typename U, typename V>
ostream &operator<<(ostream &os, const tuple<T, U, V> &t){
  os << "(" << get<0>(t) << "," << get<1>(t) << "," << get<2>(t) << ")";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
  for (auto it = v.begin();it != v.end();++it){
    if(it != v.begin())os << " ";os << *it;
  }return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &mp){
  for(auto x: mp)os << "(" << x.first << "," << x.second << ")" << endl;
  return os;
}
template<typename T, int SIZE>
int array_length(const T (&)[SIZE]){return SIZE;}
template<typename T, int N>
void PRINTF(const T (&a)[N], int s = N, int t = -1, bool f = true){
	if(t == -1){rep(i,s){if(i)cout << " ";cout << a[i];}}
	else repi(i,s,t){if(i!=s)cout << " ";cout << a[i];}
	if(f)cout << "\n";
}
template<typename T, int N1, int N2>
void PRINTF(const T (&a)[N1][N2], int h = N1, int w = N2){
	rep(i,h){rep(j,w){cout << a[i][j] << " \n"[j==w-1];}}
}
string substr(const string &str, int S1, int S2 = -1){
  if(S2 == -1)return str.substr(S1);
  return str.substr(S1, S2-S1);
}
// typedef
typedef complex<double> Point;
typedef pair<int, int> P;
typedef pair<int, P> PP;
typedef pair<P, int> Pi;
typedef tuple<int, int, int> TT;
typedef pair<int, TT> PT;
typedef vector<int> vi;
typedef deque<int> dq;
const int inf = 1e9+7;
const int INF = 1e18+7;
// int sum = accumulate(a, a+n, 0LL);
// int mx = max_element(a, a+n);
// int mn = min_element(a, a+n);
// int cnt = count(a, a+n, k);

const int V = 100005;
vector<int> vec[2*V], cnt(2), visited;
void dfs(int v){
  if(visited[v] == 1)return;
  visited[v] = 1;
  cnt[v/V]++;
  rep(i,vec[v].size()){
    int to = vec[v][i];
    dfs(to);
  }
  return ;
}

signed main(){
  int n;
  cin >> n;
  visited.resize(V*2);
  rep(i,n){
    int x, y;cin >> x >> y;
    y += V;
    vec[x].pb(y);vec[y].pb(x);
  }
  
  int res = 0;
  rep(i,V){
    cnt[0] = cnt[1] = 0;
    dfs(i);
    res += cnt[0]*cnt[1];
  }
  cout << res-n << endl;
  return 0;
}






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

int main () {
  int a, b;
  cin >> a >> b;
  if (((a + b) & 1) == 0) {
    cout << (a + b) / 2 << '\n';
  } else {
    cout << "IMPOSSIBLE" << '\n';
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define pb push_back
#define sz(i) (int)(i.size())
#define F first
#define S second
#define L long double
#define P pair<int, int>
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
const int N = 5*(int)1e5 + 10;

string s;

int solve(int start){
   int ans = 0;
   for (int i = 0; i < sz(s); ++i)
   {
      if((s[i]-'0') != start)ans++;
      tr(s[i], start);
      start ^= 1;
   }
   return ans;
}

int32_t main(){_

   cin>>s;

   int ans = inf, start = 0;
   ans = solve(0);
   ans = min(ans, solve(1LL));
   cout<<ans;

   return 0;
}

// Common sense: do smth instead of nothing

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <utility>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cassert>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

//const long double PIL = 3.141592653589793238462643383279502884L;
//const double PI = 3.14159265358979323846;

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<pair<int,int>> vii;
#define sz(a) int((a).size())
#define all(c) (c).begin(), (c).end()

const int N = 1001;
const ll MOD = 1e9 + 7;
char grid[N][N];
ll dp[N][N];

int main() {
	//~ ios::sync_with_stdio(0);
	//~ cin.tie(0);
	int h, w;
	scanf("%d%d", &h, &w);
	for (int i = 0; i < h; i++) scanf("%s", grid[i]);

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (i == 0 && j == 0)
				dp[i][j] = 1;
			else if (grid[i][j] == '#')
				dp[i][j] = 0;
			else {
				if (i > 0) dp[i][j] = dp[i-1][j];
				if (j > 0) dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD;
			}
		}
	}
	printf("%lld\n", dp[h-1][w-1]);
}


Measured memory_bytes: 9088
a,b,c,d,e,f=map(int,input().split())

ans_wat = 0
ans_sug = 0
ans_rate = 0

for i in range(31):#Aの投入数
  for j in range(31):#Bの投入数
      wat=(i*a+j*b)*100
      if wat<=f and wat:
          psug = min(f-wat,wat//100*e)
          for k in range(psug//c+1):
              l = (psug-c*k)//d
              sug = k*c+l*d
              rate = 100*sug/(wat+sug)
              if ans_rate<=rate:
                  ans_wat = wat
                  ans_sug = sug
                  ans_rate = rate

print(ans_wat+ans_sug,ans_sug)


Measured memory_bytes: 3064
//abc109_d.cpp
//Sun Apr 21 19:49:14 2019

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

int main(){
	int h,w;
	cin >> h >> w;

	vector<P> oddpair;
	int a[h][w];
	for (int i=0;i<h;i++){
		for (int j=0;j<w;j++){
				cin >> a[i][j];
		}
	}

	int dir = -1;
	for (int i=0;i<h;i++){
		dir = dir * (-1);
		if (dir == 1){
			for (int j=0;j<w;j++){
				if (a[i][j]%2==1){
					P temp;
					temp.first = i;
					temp.second = j;
					oddpair.push_back(temp);
				}
			}
		}else {
			for (int j=w-1;j>=0;j--){
				if (a[i][j]%2==1){
					P temp;
					temp.first = i;
					temp.second = j;
					oddpair.push_back(temp);
				}
			}
		}
	}

	int count=0;
	int y1[250000];
	int x1[250000];
	int y1d[250000];
	int x1d[250000];
	for (int i=0;i<oddpair.size();i++){
		if (i==oddpair.size()-1){
			break;
		}
		P fromp = oddpair[i];
		i++;
		P top = oddpair[i];
//		cout << fromp.first << " " << fromp.second << " - " << top.first << " " << top.second << endl;
		int dir = 0;
		if (fromp.first%2==0){
			dir = 1;
		}else {
			dir = -1;
		}
		while (fromp.first!=top.first || fromp.second!=top.second){
//			cout << "pass" << endl;
			if (fromp.second == 0 && dir == -1){
				y1[count] = fromp.first;
				x1[count] = fromp.second;
				y1d[count] = fromp.first+1;
				x1d[count] = fromp.second;
				fromp.first++;
				dir = 1;
			}else if (fromp.second == w-1 && dir == 1){
				y1[count] = fromp.first;
				x1[count] = fromp.second;
				y1d[count] = fromp.first+1;
				x1d[count] = fromp.second;
				fromp.first++;
				dir = -1;
			}else {
				y1[count] = fromp.first;
				x1[count] = fromp.second;
				y1d[count] = fromp.first;
				x1d[count] = fromp.second+dir;
				fromp.second += dir;
			}
			count++;
		}
	}

	cout << count << endl;
	for (int i=0;i<count;i++){
		cout << y1[i]+1 << " " << x1[i]+1 << " " << y1d[i]+1 << " " << x1d[i]+1 << endl;
	}
}

Measured memory_bytes: 8048
#include <stdio.h>
#include <stdlib.h>
 
typedef struct node{
  struct node *left;
  struct node *right;
  struct node *parent;
  int key;
}Node;
typedef Node *NodePointer;
 
NodePointer root = NULL;
NodePointer minimum(NodePointer);
 
NodePointer createNode(void){
 
  NodePointer tree = malloc(sizeof(Node));
  tree->left = NULL;
  tree->right = NULL;
  tree->parent = NULL;
  tree->key = 0;
 
  return tree;
}
 
void insert(int key){
 
  NodePointer z = createNode();
  NodePointer x = root;
  NodePointer y = NULL;
  z->key = key;
  while(x != NULL){
    y = x;
 
    if(z->key < x->key){
      x = x->left;
    }else{
      x = x->right;
    }
  }
 
  z->parent = y;
 
  if(y == NULL){
    root = z;
  }else if(z->key < y->key){
    y->left = z;
  }else{
    y->right = z;
  }
}
 
void inorder(NodePointer T){
 
  if(T != NULL){
    inorder(T->left);
    printf(" %d",T->key);
    inorder(T->right);
  }
}
 
void preorder(NodePointer T){
 
  if(T != NULL){
  printf(" %d", T->key);
    preorder(T->left);
    preorder(T->right);
  }
}
 
NodePointer find(int k, NodePointer T){
 
  while(T != NULL && T->key != k){
    if(T->key > k){
      T = T->left;
    }else{
      T = T->right;
    }
  }
  return T;
}
 
NodePointer successor(NodePointer T){
  NodePointer x;
  if(T->right != NULL){
    return minimum(T->right);
  }
  x = T->parent;
 
  while(x != NULL && T == x->right){
    T = x;
    x = x->parent;
  }
  return x;
}
 
void  delete(NodePointer T){
 
  NodePointer x;
  NodePointer y;
 
  if(T->left == NULL || T->right == NULL){ // 子がいる時
    x = T;
  }else{ // 子がいない時
    x = successor(T);
  }
  if(x->left != NULL){
    y = x->left;
  }else{
    y = x->right;
  }
 
  if(y != NULL){ // 子の子があるとき
    y->parent = x->parent;
  }
 
  if(x->parent == NULL){
    root = y;
  }else if(x == x->parent->left){
    x->parent->left = y;
  }else{
    x->parent->right = y;
  }
  if(x != T){
    T->key = x->key;
  }
}
 
NodePointer minimum(NodePointer T){
  while(T->left != NULL){
    T = T->left;
  }
  return T;
}
 
int main(){
 
  int i, n, x;
  char str[10];
 
  scanf("%d", &n);
  for(i = 0; i < n; i++){
    scanf("%s", str);
    if(str[0] == 'i'){
      scanf("%d", &x);
      insert(x);
    }else if(str[0] == 'p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }else if(str[0] == 'f'){
      scanf("%d", &x);
      if(find( x, root) == NULL){
    printf("no\n");
      }else{
    printf("yes\n");
      }
    }else if(str[0] == 'd'){
      scanf("%d", &x);
      delete(find(x, root));
    }else{
      continue;
    }
  }
  return 0;
}

Measured memory_bytes: 19360
#include <stdio.h>
#define N 36

typedef struct card
{
    char moji;
    char num;
}cards;

int main(){
  int n,i,j,flag,minj;
  cards A[N],B[N],temp;

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

  for(i=0;i<n;i++)B[i]=A[i];

      /*??????????????????*/
    for(i=0;i<n;i++){
      flag = 1;
      while(flag){
        flag = 0;
        for(j=n-1;1<=j;j--){
          if(B[j].num<B[j-1].num){
            temp = B[j-1];
            B[j-1] = B[j];
            B[j] = temp;
            flag = 1;
          }
        }
      }
    }

  for(i=0;i<n-1;i++)printf("%c%c ",B[i].moji,B[i].num);
    printf("%c%c",B[n-1].moji,B[n-1].num);
  printf("\nStable\n");

  /*?????¬????????§????????????*/
  for(i=0;i<n-1;i++){
    minj = i;
    for(j=i;j<n;j++){
      if(A[j].num < A[minj].num){
        minj = j;
      }
    }
    temp = A[i];
    A[i] = A[minj];
    A[minj] = temp;
  }

  for(i=0;i<n-1;i++)printf("%c%c ",A[i].moji,A[i].num);
  printf("%c%c",A[n-1].moji,A[n-1].num);
    flag = 1;
  for(i=0;i<n;i++)if(A[i].moji!=B[i].moji) flag = 0;
    if(flag)printf("\nStable\n");
    else printf("\nNot stable\n");

  return 0;
}

Measured memory_bytes: 608
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int D = sc.nextInt();
    
    if (N%(2*D+1) == 0) {
      System.out.println(N/(2*D+1));
    } else {
      System.out.println(N/(2*D+1) + 1);
    }
  }
}

Measured memory_bytes: 22100
while True:
    H,W = map(int, input().split())
    if H == 0 and W == 0: break
    for i in range(H):
        if i % 2 ==0:
            for j in range(W):
                if j % 2 == 0:
                    print("#", end="")
                else:print(".", end="")
        else:
            for j in range(W):
                if j % 2 == 0:
                    print(".", end="")
                else:print("#", end="")
        print("")
    print("")


Measured memory_bytes: 7016
#include <stdio.h>
#include <string.h>

int main()
{
	int N;
	scanf("%d", &N);
	switch (N % 10) {
	case 2:
	case 4:
	case 5:
	case 7:
	case 9:
		puts("hon");
		break;
	case 0:
	case 1:
	case 6:
	case 8:
		puts("pon");
		break;
	case 3:
		puts("bon");
		break;
	}
	return 0;
}


Measured memory_bytes: 1648
#include<stdio.h>

int main(void)
{
	
	int a,b=0;
	char c[10];
	scanf("%s",c);
	
	if (c[0] == 'S')
		if (c[1] == 'A')printf("1");
		else printf("7");
	if (c[0] == 'M')printf("6");
	if (c[0] == 'T')
		if (c[1] == 'U')printf("5");
			else printf("3");
	if (c[0] == 'W')printf("4");
	if (c[0] == 'F')printf("2");

	return 0;			
}		

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define irep(i,n,m) for(int i=(int)(n);i<(int)(m);i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
using namespace std;
int main(){
    vector<string> s(3);
    rep(i,3){
        cin>>s.at(i);
        reverse(all(s.at(i)));
    }
    
    int now=0;
    while(s.at(now).size()>0){
        char x=s.at(now).back();
        s.at(now).pop_back();
        now=x-'a';
    }
    
    char ans='A'+now;
    cout<<ans<<endl;
}



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

using namespace std;

int A[200];
int N;

int main(){
    
    cin >>N;
    for (int i=0;i<N;++i) cin >>A[i];

    int MaD=0;

    for (int i=0;i<N;++i){
        for (int j=0;j<N;++j){
            if(MaD<A[i]-A[j]) MaD=A[i]-A[j];
        }

    }

    cout <<MaD<<endl;

}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
int arr[205][205];

int main(){
	int n,m,r;
	cin>>n>>m>>r;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++) arr[i][j] = INF;
	}
	
	vector<int>town(r);
	for(int i=0; i<r; i++) cin>>town[i];
	sort(town.begin(),town.end());
	
	while(m--){
		int a,b,c;
		cin>>a>>b>>c;
		arr[a][b] = min(arr[a][b],c);
		arr[b][a] = min(arr[b][a],c);
	}
	for(int k=1; k<=n; k++){
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				arr[i][j] = min(arr[i][j],arr[i][k]+arr[k][j]);
			}
		}
	}
	int mindist = numeric_limits<int>::max();
	do{
		int dist = 0;
		for(int i=1; i<r; i++) dist+=arr[town[i-1]][town[i]];
		mindist = min(mindist,dist);
	}while(next_permutation(town.begin(),town.end()));
	cout<<mindist;
}

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

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef pair<LL, LL> PLL;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

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

  LL x, y; cin >> x >> y;
  LL ax = abs(x), ay = abs(y);
  LL res = 0;
  if(x == y){}
  else if(ax == ay)
	res = 1;
  else if(ax < ay){
	if(x < 0) ++res;
	res += ay - ax;
	if(y < 0) ++res;
  }
  else{
	if(x > 0) ++res;
	res += ax - ay;
	if(y > 0) ++res;
  }
  cout << res << endl;

  return 0;
}


Measured memory_bytes: 256
n,m=map(int,input().split())
es=[[] for i in range(n)]
deg=[0]*n
for i in range(n-1+m):
    a,b=map(int,input().split())
    es[a-1].append(b-1)
    deg[b-1]+=1

ans=[]
from collections import deque
que=deque([])
for i in range(n):
    if deg[i]==0:
        que.append((i,-1))

while que:
    s=que.popleft()
    ans.append(s)
    for e in es[s[0]]:
        deg[e]-=1
        if deg[e]==0:
            que.append((e,s[0]))
ans=sorted(ans)
for i in range(n):
    print(ans[i][1]+1)

Measured memory_bytes: 73700
#include <bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	while(1){
		c-=b;
		if(c<=0){
			cout<<"Yes";
			return 0;
		}
		a-=d;
		if(a<=0){
			cout<<"No";
			return 0;
		}
	}
	return 0;
} 

Measured memory_bytes: 3564
import java.util.*;

public class Main {

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

        List<Integer> t = new ArrayList<>();
        List<Integer> x = new ArrayList<>();
        List<Integer> y = new ArrayList<>();
        t.add(0);
        x.add(0);
        y.add(0);
        for (int i = 0; i < n; i++) {
            t.add(sc.nextInt());
            x.add(sc.nextInt());
            y.add(sc.nextInt());
        }

        boolean flag = true;
        for (int i = 0; i < n; i++) {
            int dt = t.get(i+1) - t.get(i);
            int dist = Math.abs(x.get(i+1) - x.get(i)) + Math.abs(y.get(i+1) - y.get(i));
            if (dist > dt) {
                flag = false;
            }
            if (dt%2 != dist%2) {
                flag = false;
            }
        }

        if (flag) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }

    }
}

Measured memory_bytes: 94164
s = input()

# print(s[::2])
# print(s[1::2])

a = s[::2].count('1')
b = s[1::2].count('0')
c = s[::2].count('0')
d = s[1::2].count('1')

# 10101010にする場合
# c + d
# 0101010にする場合
# a + b
# いずれか小さい方
ans = min(a+b, c+d)
print(ans)


Measured memory_bytes: 3188
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

    private static Scanner scan = new Scanner(System.in);

    public static void main(String[] args) {

	int N = Integer.parseInt(scan.next());
	long K = Long.parseLong(scan.next());
	List<MyClass> list = new ArrayList<MyClass>();

	for (int i = 0; i < N; i++) {
	    int a = Integer.parseInt(scan.next());
	    int b = Integer.parseInt(scan.next());

	    list.add(new MyClass(a, b));
	}
	Collections.sort(list);
	    
	long num = 0;
	for(MyClass l: list) {
	    num += l.b;
	    if(num >= K) {
		System.out.println(l.a);
		break;
	    }
	}
	scan.close();
    }
}

class MyClass implements Comparable<MyClass> {

    int a;
    int b;

    MyClass(int a, int b) {
	this.a = a;
	this.b = b;
    }

    @Override
    public int compareTo(MyClass o) {
	return a - o.a;
    }
}


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

using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL<<60;

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

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

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  int N, Q;
  cin >> N >> Q;
  vector<ll> A(N), X(Q);
  rep(i, N) cin >> A[i];
  rep(i, Q) cin >> X[i];
  
  vector<ll> sumA(N+1);
  vector<ll> sumO(N+1);
  vector<ll> sumE(N+1);

  sumA[0] = 0;
  sumO[0] = 0;
  sumE[0] = 0;
  rep(i, N){
    sumA[i+1] = sumA[i] + A[i];
    if(i%2==0){
      sumO[i+1] = sumO[i] + A[i];
      sumE[i+1] = sumE[i];
    }else{
      sumO[i+1] = sumO[i];
      sumE[i+1] = sumE[i] + A[i];
    }
  }

  vector<ll> ans(Q);

  rep(i, Q){

    ll x = X[i];
    int left = -1;
    int right = N-1;
    int ind;
    while(right - left > 1){

      int mid = left + (right - left) / 2;

      int Nt = N-mid;
      if(mid < N-mid-1){
        left = mid;
        continue;
      }
      if(x > A[mid]){
        left = mid;
        continue;
      }

      // x <= A[mid]である
      // 2*x - A[mid] <= xとなるところを探す
      int tind = lower_bound(A.begin(), A.end(), 2*x-A[mid])-A.begin();

      int Na = mid - tind;

      if(Na >= Nt - 1){
        right = mid;
        ind = tind;
      }else{
        left = mid;
      }
    }

    if(right - (N-right) >= 0){
      ind = right - (N-right);
    }
    // right ~ N-1
    ll TT = sumA[N] - sumA[right];
    ll AA = sumA[right] - sumA[ind];

    if(ind == 0){
      ans[i] = TT;
      continue;
    }

    if(N%2==0){
      TT += sumE[ind];
      AA += sumO[ind];
    }else{
      TT += sumO[ind];
      AA += sumE[ind];
    }

    ans[i] = TT;

  }

  rep(i, Q){
    cout << ans[i] << endl;
  }



  return 0;
}


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

int main() {
	int a, b, c, x; cin >> a >> b >> c >> x;

	int count = 0;
	for (int i = 0; i <= a; i++) {
		for (int j = 0; j <= b; j++) {
			for (int k = 0; k <= c; k++) {
				if ((500 * i + 100 * j + 50 * k) == x) count++;
			}
		}
	}

	cout << count << endl;

	return 0;
}

Measured memory_bytes: 256
import math
a, b, h, m = map(int, input().split())

minuterad = m/60*360
hourrad = (h*60+m)/720*360

rad = abs(minuterad - hourrad)

ans = math.sqrt(a**2 + b**2 - 2*a*b*math.cos(math.radians(rad)))

print(ans)


Measured memory_bytes: 9428
#include <stdio.h>

int
main(int argc, char *argv[])
{
  int N;
  scanf("%d", &N);
  
  for(int i = 0; i < 10; i++){
    int a = 111 * (i - 1);
    int b = 111 * i;
    if(a < N && N <= b){
      printf("%d\n", b);
      break;
    }
  }
  
  return 0;
}


Measured memory_bytes: 128
//ABC128 C-Swiches

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); ++i)
using namespace std;
using ll = long long;
const int INF = 1001001001;
const int MOD = 1000000007;

int k[11], s[11][11], p[11];
int main() {
    int n, m; cin >> n >> m;
    
    rep(i,m) {
        cin >> k[i];
        rep(j,k[i]) {
            cin >> s[i][j];
            --s[i][j];
        }
    }
    rep(i,m) cin >> p[i];

    int ans = 0;
    for (int bit=0; bit<(1<<n); ++bit) {
        bool flg = true;
        rep(i,m) {
            int cnt = 0;
            rep(j,k[i]) {
                if (bit & (1<<s[i][j])) ++cnt;
            }
            if (cnt%2 != p[i]) flg = false;
        }
        if (flg) ++ans;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define rrep(i, n) for(int i = n-1; i >= 0; --i)
#define fi first
#define se second
using namespace std;
using lint = long long;
using uint = unsigned int;
using ulint = unsigned long long;
using ldouble = long double;
using pii = pair<int, int>;
using pli = pair<lint, lint>;
using pdd = pair<double, double>;
using pld = pair<ldouble, ldouble>;
using v1i = vector<int>;
using v1li = vector<lint>;
using v2i = vector<vector<int>>;
using v2li = vector<vector<lint>>;
using v3i = vector<vector<vector<int>>>;
using v3li = vector<vector<vector<lint>>>;
using v1b = vector<bool>;
using v2b = vector<vector<bool>>;
using v3b = vector<vector<vector<bool>>>;
using v1c = vector<char>;
using v2c = vector<vector<char>>;
using v3c = vector<vector<vector<char>>>;
constexpr lint mod1 = 1e9+7;
constexpr lint mod2 = 998244353;

int main(){
  int n, a = 0, b = 0, c = 0; cin >> n; v1i v(n);
  rep(i, n) cin >> v[i];
  rep(i, n){
    if(v[i] % 2 == 1) ++a;
    else if(v[i] % 4 != 0) ++b;
    else ++c;
  }
  if(a <= c || (b == 0 && a <= c+1)) cout << "Yes\n";
  else cout << "No\n";
  return 0;
}

Measured memory_bytes: 640
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
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; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<P> v(n);
    rep(i,n) cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end());
    ll ans = 0;
    rep(i,n){
        if(v[i].second >= m){
            ans += v[i].first * m;
            break;
        }
        else{
            m -= v[i].second;
            ans += v[i].first * v[i].second;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4740
// E.

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

using namespace std;

int main(int argc, char* argv[]) {
#ifdef _MSC_VER
	while (true)
#endif
	{
		string s;
		cin >> s;
		if (s.empty()) return 0;
		int len = (int)s.length();
		int dp[1000002][2] = {};
		dp[0][0] = 0, dp[0][1] = 1;
		for (int i = 0; i < len; ++i) {
			int d = s[i] - '0';
			dp[i + 1][0] = min(dp[i][0] + d, dp[i][1] + 10 - d);
			dp[i + 1][1] = min(dp[i + 1][0] + 1, dp[i][1] + 10 - d - 1);
		}
		cout << dp[len][0] << endl;
	}
	return 0;
}


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

using ll=long long;
const ll MOD=1e9+7;

ll powm(ll x,ll k){
    ll res=1;
    while(k){
        if(k&1) res=(res*x)%MOD;
        x=(x*x)%MOD;
        k>>=1;
    }
    return res;
}

ll modInverse(ll x){
    return powm(x,MOD-2);
}
int main(){
    int N;
    cin>>N;
    string s;
    cin>>s;
    int M=s.size();

    vector<vector<ll>> dp(2,vector<ll>(N+1,0));
    dp[0][0]=1;
    for(int i=0;i<N;i++){
        fill(dp[(i+1)&1].begin(),dp[(i+1)&1].end(),0LL);
        for(int j=0;j<N;j++){
            (dp[(i+1)&1][max(j-1,0)]+=dp[i&1][j])%=MOD;
            (dp[(i+1)&1][j+1]+=dp[i&1][j]*2)%=MOD;
        }
    }
    cout<<(dp[N&1][M]*modInverse(powm(2LL,M)))%MOD<<endl;
    return 0;
}

Measured memory_bytes: 384
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

######################################################

N=intput()
S1=input()
S2=input()
i=0
ans=1
# first,tate,yoko
tmp=0
same=[3,2,1]
diff=[6,2,3]
while i<N:
    if S1[i]==S2[i]:
        ans*=same[tmp]
        tmp=1
        i+=1
    else:
        ans*=diff[tmp]
        tmp=2
        i+=2
    ans%=MOD
print(ans)

Measured memory_bytes: 69916
#include<bits/stdc++.h>
using namespace std;
int a[3000],k;

int main()
{
    int n,k=0;
    cin>>n;
    if(n==0)
    {
        printf("%d",0);
        return 0;
    }
    k=0;
    int fz=n,fm=-2,fy;
    while(fz)
    {
        fy=fz/fm;
        if(fz-fm*fy<0)fy+=1;
        a[k++]=fz-fy*(-2);
        //cout<<fz<<" "<<fy<<" "<<fz-fy*(-2)<<endl;

        fz=fy;
    }
    for(int i=k-1;i>=0;i--)
        printf("%d",a[i]);
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int k[15], w[15];
    int ksum, wsum;
    int i, j, tmp;

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

    for (i = 0; i < 10; ++i){
        for (j = i + 1; j < 10; ++j){
           if (k[i] < k[j]) {
               tmp = k[i];
               k[i] = k[j];
               k[j] = tmp;
           }
       }
    }

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


    for (i = 0; i < 10; ++i){
        for (j = i + 1; j < 10; ++j){
           if (w[i] < w[j]) {
               tmp = w[i];
               w[i] = w[j];
               w[j] = tmp;
           }
       }
    }


    ksum = wsum = 0;
    for (i = 0; i < 3; i++){
        ksum += k[i];
        wsum += w[i];
    }

    printf("%d %d\n", ksum, wsum);

    return (0);
}

Measured memory_bytes: 596
/* ALDS1_1_B:Greatest Common Divisor */
/* 20181117 AOJ */


#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int Eculid(int m, int n); 

int main(void){
	int x, y;
	//x = y = 0;
	scanf("%d%d", &x, &y);
	printf("%d\n", Eculid(x, y));

	return 0;
}

int Eculid(int m, int n){
	int max = m, r = 1;
	if(n > m){
		m = n;
		n = max;
	}

	while(r){
		r = m % n;		
		m = n;
		n = r;
	}

	return m;
}



Measured memory_bytes: 1992
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define ArraySizeOf(array)     (sizeof(array) / sizeof(array[0]))
#define res(i,n) for(int i=n;;i++)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define REV(i,n) for(int i=n-1;i>0;i--)
#define req(i,n,m) for(int i=n;i<m;i++)
#define REQ(i,n,m,l) for(int i=n;i<m;i+=l) 
#define _GLIBCXX_DEBUG
int INF = 1e9 + 7;
unsigned NthDayOfWeekToDay(unsigned n, unsigned dow, unsigned dow1)
{
    unsigned day;
    if (dow < dow1) dow += 7;
    day = dow - dow1;
    day += 7 * n - 6;
    return day;
}
signed gcd(long long x, long long y) {
    if (y == 0)return x;
    return gcd(y, x % y);
}
signed lcm(long long x, long long y) {
    return x / gcd(x, y) * y;
}
unsigned DayToWeekNumber(unsigned day)
{
    return (day - 1) / 7 + 1;
}
unsigned AnotherDayOfWeek(unsigned day, unsigned day0, unsigned dow0)
{
    return (dow0 + 35 + day - day0) % 7;
}
using namespace std;
signed main() {
    int N; cin >> N;
    int ans = 0;
    rep(i, log10(N) + 1) {
        int count = 1;
        rep(j, i)count *= 10;
        ans += N % (count*10) / (count);
    }
    cout << (N % ans == 0 ? "Yes" : "No") << endl;
}

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

using namespace std;

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

    if (n == 0 || k == 0) {
        cout << 0;
       return 0;
    }

    vector<int> h(n);
    for (int i = 0; i < n; ++i)
        cin >> h[i];

    vector<int> F(n, 0);

    for (int i = 1; i < n; ++i) {
        int curr_min = INT_MAX;
        for (int j = 1; j <= k; ++j) {
            if (i - j >= 0) {
                curr_min = min(curr_min, F[i - j] + abs(h[i] - h[i - j]));
            }
        }

        F[i] = curr_min;
    }

    //for (auto e : F) cout << e << " "; cout << endl;

    cout << (F[n - 1] != INT_MAX ? F[n - 1] : 0);
    
    return 0;
}

Measured memory_bytes: 1024
# AOJ 0549: A Traveler
# Python3 2018.7.1 bal4u

import sys
from sys import stdin
input = stdin.readline

M, BigM = 100000, 1000000000

n, m = map(int, input().split())
s = [0]*(n+1)
for i in range(2, n+1): s[i] = s[i-1] + int(input())
ans, p1 = 0, 1
for i in range(m):
	p2 = p1 + int(input())
	x = s[p2] - s[p1]
	if x >= 0: ans += x
	else:      ans -= x
	if ans >= BigM: ans %= M
	p1 = p2;
print(ans % M)


Measured memory_bytes: 9416
#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
#include <fstream>

using namespace std;

ifstream fin("../data.txt");

int k, s, x, y, z, ways;

int main() {

  cin >> k >> s;

  for (x = 0; x <= k; x++) {
    for (y = 0; y <= k; y++) {
      if (s - x - y >= 0 && s - x - y <= k) ways++;
    }
  }
  cout << ways;
  return 0;
}


Measured memory_bytes: 3636
#include<iostream>
using namespace std;
int main(){
  int n,q,h,t,sum=0;
  pair<string,int> a[200000];
  cin>>n>>q;
  for(int i=0;i<n;i++)cin>>a[i].first>>a[i].second;
  h=0;
  t=n-1;
  while(1){
    if(h==t){
      cout<<a[h].first<<' '<<sum+a[h].second<<endl;
      break;
    }
    if(a[h].second-q<=0){
      sum+=a[h].second;
      cout<<a[h].first<<' '<<sum<<endl;
      h++;
    }
      else{
	a[h].second-=q;
	sum+=q;
	if(t+1==200000)t=-1;
	a[++t].first=a[h].first;
	a[t].second=a[h++].second;
	if(h+1==200000)h=0;
      }
  }
  return 0;
}



Measured memory_bytes: 8600
from math import *
from collections import *
from itertools import *
from functools import *
from bisect import *
from heapq import *
from operator import *
from sys import *
setrecursionlimit(100000000)
MAX=float('inf')
MIN=float('-inf')
MOD=1000000007

n=int(input())
l=list(map(int,input().split()))
l1=list(accumulate(l[::-1]))[::-1]
ans=0
for i in range(1,len(l1)):
	ans+=(l[i-1]*l1[i])%MOD
print(ans%MOD)


Measured memory_bytes: 33356
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define ALL(v) (v).begin(),(v).end()
const double INF = 1e100;
const ll MOD = 1e9 + 7;
double x[100000], y[100000];
string d[100000];
double X[3][2], Y[3][2];
int N;
double calc(double t) {
	double x_max = -INF, y_max = -INF;
	double x_min = INF, y_min = INF;
	for (int i = 0; i < N; i++) {
		double nx = x[i], ny = y[i];
		if (d[i] == "U") ny += t;
		else if (d[i] == "D") ny -= t;
		else if (d[i] == "L") nx -= t;
		else nx += t;
		x_max = max(x_max, nx);
		x_min = min(x_min, nx);
		y_max = max(y_max, ny);
		y_min = min(y_min, ny);
	}
	return (x_max - x_min)*(y_max - y_min);
}
int main() {
	cin >> N;
	for (int i = 0; i < 3; i++) {
		X[i][0] = Y[i][0] = INF;
		X[i][1] = Y[i][1] = -INF;
	}
	for (int i = 0; i < N; i++) {
		cin >> x[i] >> y[i] >> d[i];
		if (d[i] == "U") {
			X[1][0] = min(X[1][0], x[i]);
			X[1][1] = max(X[1][1], x[i]);
			Y[2][0] = min(Y[2][0], y[i]);
			Y[2][1] = max(Y[2][1], y[i]);
		}
		else if (d[i] == "D") {
			X[1][0] = min(X[1][0], x[i]);
			X[1][1] = max(X[1][1], x[i]);
			Y[0][0] = min(Y[0][0], y[i]);
			Y[0][1] = max(Y[0][1], y[i]);
		}
		else if (d[i] == "L") {
			X[0][0] = min(X[0][0], x[i]);
			X[0][1] = max(X[0][1], x[i]);
			Y[1][0] = min(Y[1][0], y[i]);
			Y[1][1] = max(Y[1][1], y[i]);
		}
		else {
			X[2][0] = min(X[2][0], x[i]);
			X[2][1] = max(X[2][1], x[i]);
			Y[1][0] = min(Y[1][0], y[i]);
			Y[1][1] = max(Y[1][1], y[i]);
		}
	}
	vector<double> T;
	T.push_back(0);
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			if (X[0][0] != INF && X[1][0] != INF)
				T.push_back(abs(X[0][i] - X[1][j]));
			if (X[1][0] != INF && X[2][0] != INF)
				T.push_back(abs(X[1][i] - X[2][j]));
		}
	}
	if (X[0][0] != INF && X[2][0] != INF) {
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 2; j++) {
				if (X[2][j] <= X[0][i]) {
					T.push_back((X[0][i] - X[2][j]) / 2.0);
				}
			}
		}
	}
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			if (Y[0][0] != INF && Y[1][0] != INF)
				T.push_back(abs(Y[0][i] - Y[1][j]));
			if (Y[1][0] != INF && Y[2][0] != INF)
				T.push_back(abs(Y[1][i] - Y[2][j]));
		}
	}
	if (Y[0][0] != INF && Y[2][0] != INF) {
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 2; j++) {
				if (Y[2][j] <= Y[0][i]) {
					T.push_back((Y[0][i] - Y[2][j]) / 2.0);
				}
			}
		}
	}
	double ans = INF;
	for (double t : T) {
		ans = min(ans, calc(t));
	}
	printf("%.15lf\n", ans);
}


Measured memory_bytes: 7296
#include<stdio.h>
#include<string.h>
int main()
{
    int n,i,count=0,ans=0,j;
    scanf("%d",&n);
    char str[n][11];
    for(i=0;i<n;i++)
    {
        scanf("%s",str[i]);
        if(i>0 && str[i-1][strlen(str[i-1])-1]!=str[i][0])
        count++;
    }
    if(count>0)
    printf("No");
    
    else
    {
        for(i=0;i<n-1;i++)
        {
            for(j=i+1;j<n;j++)
            {
                if(strcmp(str[i],str[j])==0)
                {
                ans++;
                break;
                }
            }
        }
        if(ans==0)
        printf("Yes");
        
        else
        printf("No");
    }
    return 0;
}


Measured memory_bytes: 128
N = int(input())
if N == 1:
    print(1)
elif N < 4:
    print(2)
elif N < 8:
    print(4)
elif N < 16:
    print(8)
elif N < 32:
    print(16)
elif N < 64:
    print(32)
else:
    print(64)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
 
using namespace std;
 
#define ALL(x) x.begin(), x.end()
 
typedef long long int lld;
typedef pair<int, int> pii;
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.precision(15);
	cout << fixed;
 
	int n = 0;
	cin >> n;
 
	vector<int> vec(n);
 
	for (int i = 0; i < n; i++)
		cin >> vec[i];

	auto it = unique(ALL(vec));
	vec.resize(it - vec.begin());

	bool flag = true;
	bool op = false;
	for (int i = 0; i < n - 1; i++) {
		if (vec[i] > vec[i + 1]) {
			if (vec[i] - vec[i + 1] > 1)
				flag = false;
			else {
				if (!op)
					op = true;
				else
					flag = false;
			}
		} else {
			op = false;
		}
	}
	
 
	if (flag)
		cout << "Yes" << '\n';
	else
		cout << "No" << '\n';
 
 
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <cstdlib>

using namespace std;
typedef long long int ll;

bool debug;
#define show(x) if (debug) {cout << "" # x << " = " << x << endl;}
#define rep(x, a, b) for (int x = a; x < b; x++)

int main(int argc, char **argv)
{
  (void)argv; debug = argc > 1;

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

  const int xmax = 200000;
  vector<int> xs(xmax, 0);

  rep (i, 0, n) {
    int x; cin >> x;
    xs[x]++;
  }

  vector<int> left(m, 0), margin(m, 0);
  rep (i, 0, xmax) {
    left[i % m] += xs[i] % 2;
    margin[i % m] += xs[i] / 2;
  }

  int finleft = 0;

  if (debug) {
    rep (i, 0, m) {
      cout << "margin[" << i << "] = " << margin[i] << endl;
    }
    rep (i, 0, m) {
      cout << "left[" << i << "] = " << left[i] << endl;
    }
  }

  rep (i, 1, (m + 1)/2) {
    show(i);
    if (left[i] > left[m - i]) {
      if(debug) cout << "fuga" << endl;
      int l = left[i] - left[m - i];
      finleft += l % 2 + max(2 * (l / 2 - margin[m - i]), 0);
    } else if (left[m - i] > left[i]) {
      if(debug) cout << "pohe" << endl;
      int l = left[m - i] - left[i];
      show(l);
      show(l % 2 + max(2 * (l / 2 - margin[i]), 0));
      finleft += l % 2 + max(2 * (l / 2 - margin[i]), 0);
    }
  }

  show(finleft);

  finleft += left[0] % 2;
  if (m % 2 == 0) {
    finleft += left[m/2] % 2;
  }

  cout << (n - finleft)/2 << endl;

  return 0;
}


Measured memory_bytes: 1792
s = gets.split("")
ans = "Yes"
n = s.size
n.times do |i|
  if i.odd?
    if s[i] == "R"
      ans = "No"
      break
    end
  end

  if i.even?
    if s[i] == "L"
      ans = "No"
      break
    end
  end
end

puts ans

Measured memory_bytes: 1788