akhauriyash/Code-Regression huggingface dataset:
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

# 四方向
dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]
INF = float("inf")

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))

N = int(input())
S = input()

l = [0] * (N+1)

for i, si in enumerate(S):
    if si == "#":
        l[i+1] = l[i] + 1
    else:
        l[i+1] = l[i]

ans = INF
for i in range(0, N+1):
    l_black = l[i]
    r_white = (N - i) - (l[-1] - l[i])
    ans = min(ans, (l_black + r_white))

print(ans)

Measured memory_bytes: 11780
#include<stdio.h>
#define INFTY 10000000000
#define MAX 500000

int cnt=0,A[MAX];

void merge(int A[], int left, int mid, int right){
  int n1,n2,i,j,k;
  int L[MAX/2+1],R[MAX/2+1];
  n1 = mid - left;
  n2 = right - mid;
  
    
   for(i = 0;i<n1;i++){
     L[i] = A[left + i];
   }
 for(i = 0;i<n2;i++){
   R[i] = A[mid + i];
 }
 L[n1] = INFTY;
 R[n2] = INFTY;
    i = 0;
    j = 0;
    for(k = left;k<right;k++){
      cnt++;
      if(L[i] <= R[j]){
	A[k] = L[i];
	i++;
      }
      else {
	A[k] = R[j];
	j++;
	}
    }
}

void mergeSort(int A[], int left, int right){
  int mid =0;
  if(left+1 < right){
    mid = (left + right)/2;
    mergeSort(A, left, mid);
    mergeSort(A, mid, right);
    merge(A, left, mid, right);
      }
}
int main(){

  int i,n;
 
  scanf("%d",&n);

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

  for(i=0;i<n;i++){
    printf("%d",A[i]);
    if(i != n-1) printf(" ");
  }
 
  printf("\n"); 
  printf("%d\n",cnt);
  
  return 0;
  
}

  
  

Measured memory_bytes: 4504
from typing import List, Dict


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> int:
    N = read_int()
    answer = 0
    A = read_ints()
    prefix: Dict[int, int] = {0: 0}
    base = 0
    dp = [0]*(N+1)
    for i, a in enumerate(A, start=1):
        base += a
        if base in prefix:
            count = 1+dp[prefix[base]]
            dp[i] = count
        else:
            dp[i] = 0
        prefix[base] = i
    return sum(dp)


if __name__ == '__main__':
    print(solve())


Measured memory_bytes: 129220
//
//  AOJ0032.c
//  
//
//  Created by 中野 優 on 2014/02/23.
//
//

#include <stdio.h>
int main(void) {
    int l1,l2,l3,rec=0,loz=0;
    while(scanf("%d,%d,%d",&l1,&l2,&l3)!=EOF) {
        if(l1*l1+l2*l2==l3*l3) rec++;
        if(l1==l2) loz++;
    }
    printf("%d\n%d\n",rec,loz);
    return 0;
}

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

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

const int mod = 1000000007;

char maze[1010][1010];
int H, W;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

int d[1010][1010]; // 最短距離

int bfs() {
    queue<P> que;
    rep(i, H)rep(j, W) d[i][j] = INF;


    int goal = H * W;
    rep(i, H)rep(j, W) {
        if (maze[i][j] == '#') {
            que.push(P(i, j));
            d[i][j] = 0;
            goal--;
        }
    }
    if (goal == 0) return 0;

    while (que.size()) {
        P p = que.front(); que.pop();

        // 全て埋まったか
        if (goal <= 0) break;

        for (int i = 0; i < 4; i++) {
            int nx = p.first + dx[i], ny = p.second + dy[i];
            if (0 <= nx && nx < H && 0 <= ny && ny < W && d[nx][ny] == INF) {
                que.push(P(nx, ny));
                d[nx][ny] = d[p.first][p.second] + 1;
                goal--;
            }
        }
    }

    int ans = 0;
    rep(i, H)rep(j, W) {
        ans = max(d[i][j], ans);
    }

    return ans;
}

int main() {
    cin >> H >> W;
    rep(i, H)rep(j, W) cin >> maze[i][j];

    int ans = bfs();
    cout << bfs() << endl;;
}

Measured memory_bytes: 21572
#https://atcoder.jp/contests/dp/tasks/dp_e
import sys
inf = sys.maxsize

n,mw = map(int,input().split())

mv = 1000 * n

dp = [[inf for _ in range(mv+ 1)] for _ in range(n + 1)] #dp[i番目まで][価値sv以上の重さの最小値]

dp[0][0] = 0

for i in range(n):
    w, v = map(int,input().split())
    for sv in range(mv + 1):
        if sv - v >= 0:
            dp[i + 1][sv] = min(dp[i][sv], dp[i][sv - v] + w)
        else:
            dp[i + 1][sv] = dp[i][sv]

ans = 0
for sv in range(mv + 1):
    if dp[n][sv] <= mw:
        ans = sv

print(ans)

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

#define mp make_pair

using namespace std;

typedef int32_t i32;
typedef uint32_t u32;
typedef int64_t i64;
typedef uint64_t u64;
typedef pair<int,int> pii;
typedef pair<i64,int> pli;
typedef pair<int,i64> pil;
typedef pair<i64,i64> pll;
typedef vector<int> vi;
typedef vector<i64> vl;

template <typename T>
T id(T b) {return b;};
template <class It>
bool all(It f,It l){return std::all_of(f,l,id<bool>);}
template <class It>
bool any(It f,It l){return std::any_of(f,l,id<bool>);}

const int MAX_N = 500;
int n;
int c[MAX_N], s[MAX_N], f[MAX_N];

int ceil_div(int a, int b)
{
  return a / b + (a % b != 0 ? 1 : 0);
}

int main()
{
  cin >> n;
  for (int i = 0; i < n-1; ++i) {
    cin >> c[i] >> s[i] >> f[i];
  }

  for (int i = 0; i < n; i++) {
    int t = 0;
    for (int j = i; j < n-1; j++) {
      t = ceil_div(max(t,s[j]), f[j])*f[j] + c[j];
    }
    cout << t << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void){
	int h,w,i,j;
	
	while(1){
	scanf("%d%d",&h,&w);
		if(h==0&&w==0){
			break;
		}
		else{
			for(i=0;i<h;i++){
				for(j=0;j<w;j++){
					printf("#");
			}
				printf("\n");
		}
		}
		printf("\n");
	}
return 0;
}

Measured memory_bytes: 572
#define debug_interval ','
#define dump_interval ' '
#define debug_toggle 1
//{
#include<bits/stdc++.h>
using namespace std;
#define hi cerr<<"hi"<<endl;
#define int long long
#define INT_MAX LLONG_MAX
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define fi first
#define se second
#define mp make_pair
#define rev reverse
#define dans dump(ans)
#define MOD 1000000007
#define amp(v,n) (v).count(n)?v[n]++:v[n]=1
#define sysp system("pause")
#define PI acos(-1)
#define pf push_front
#define ins insert

//{
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class...A> inline void dump(){cout<<endl;}
template<class...A> inline void dump_rest() {cout<<endl;}
template<class T, class...A> inline void dump_rest(const T& first, const A&... rest){cout<<dump_interval<<first;dump_rest(rest...);}
template<class T,class...A> inline void dump(const T&first,const A&...rest){cout<<first;dump_rest(rest...);}
template<class...A> inline void debug(){cerr<<endl;}
template<class...A> inline void debug_rest() {cerr<<endl;}
template<class T, class...A> inline void debug_rest(const T& first, const A&... rest){cerr<<debug_interval<<first;debug_rest(rest...);}
template<class T,class...A> inline void debug(const T&first,const A&...rest){if(debug_toggle)cerr<<first,debug_rest(rest...);}
unsigned XorShift(void){static unsigned x = 123456789;static unsigned y = 362436069;static unsigned z = 521288629;static unsigned w = 88675123;unsigned t;t = x ^ (x << 11);x = y; y = z; z = w;return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));}
//}

typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
template<int m>class mint{private:int i;public:mint() : i(0){}mint(int i): i((i%m+m)%m){}mint operator+(const mint& o){return o.i+i;}mint operator*(const mint& o){return o.i*i;}mint operator-(){return -i;}operator int() {return i;}};

//}

main(){
	string s;cin>>s;
	int n=s.size();
	string a,b;
	rep(i,n){
		a+='0'+(i%2);
	}
	rep(i,n){
		b+='0'+((i+1)%2);
	}
	int p=0,q=0;
	rep(i,n){
		if(s[i]!=a[i])p++;
		if(s[i]!=b[i])q++;
	}
	dump(min(p,q));
}





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

int main() {
  string S;
  cin >> S;
  int N = S.size();
  
  vector<int> A(N+1,0);
  int count = 0;
  for (int i=1; i<=N; i++) {
    if (S.at(i-1) == '<') {
      count++;
      A.at(i) = max(count, A.at(i));
    }
    else if (S.at(i-1) == '>') {
      count = 0;
    }
  }
  count = 0;
  for (int i=N-1; i>=0; i--) {
    if (S.at(i) == '>') {
      count++;
      A.at(i) = max(count, A.at(i));
    }
    else if (S.at(i) == '<') {
      count = 0;
    }
  }
  ll ans = 0;
  for (int i=0; i<=N; i++) {
    ans += A.at(i);
  }
  cout << ans << endl;
}

Measured memory_bytes: 2820
#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>
#include <math.h>
 
// ===============================================================
 
using namespace std;
using ll = long long;
using vl = vector<long long>;
using vll = vector<vector<long long>>;
using vs = vector<string>;
using vc = vector<char>;
using vcc = vector<vector<char>>;
using vm = vector<short>;
using vmm = vector<vector<short>>;
using pii = pair<int, int>;
using psi = pair<string, int>;
using ld = long double;
using ull = unsigned long long;
 
// ===============================================================
 
ll gcd(ll a, ll b) //最大公約数
{
	if (a % b == 0)
	{
		return(b);
	}
	else
	{
		return(gcd(b, a % b));
	}
}
 
ll lcm(ll a, ll b) //最小公倍数
{
	return a * b / gcd(a, b);
}
 
ll box(double a) //doubleの切り捨て
{
	ll b = a;
	return b;
}
 
ll fff(double a) //doubleの四捨五入
{
	ll b = a + 0.5;
	return b;
}
 
ll sum(ll n) { //整数sまでの合計
	if (n == 0) {
		return 0;
	}
 
	int s = sum(n - 1);
	return s + n;
}
 
bool prime(ll num)//素数判定、primeならtrue,違うならfalse
{
	if (num < 2) return false;
	else if (num == 2) return true;
	else if (num % 2 == 0) return false;
	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			return false;
		}
	}
 
	// 素数である
	return true;
}
 
// ===============================================================
 
int main() {
	ll a, b; cin >> a >> b;
	if (a < b) {
		cout << 0 << endl;
	}
	else cout << 10 << endl;
}

Measured memory_bytes: 3648
#include <algorithm>
#include <cctype>
#include <complex>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::cerr;

using std::string;
using std::to_string;
using std::vector;
using std::set;
using std::queue;
using std::stack;
using std::priority_queue;

using std::min;
using std::max;
using std::sort;
using std::abs;

typedef long long int ll;
const int MOD = 1e9 + 7;

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

    const int len = s.length();
    const char fst = s[0];
    const char lst = s[len-1];

    if(fst == lst){
        cout << (len % 2 == 0 ? "First" : "Second") << endl;
    }
    else{
        cout << (len % 2 != 0 ? "First" : "Second") << endl;
    }
    return 0;
}


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

template<class T>
struct WarshallFloyd {
	const int V;
	// オーバーフロー注意
    const T INF = numeric_limits<T>::max() / 3;
    vector<vector<T>> d;
	WarshallFloyd(const int V) :
		V(V),
		d(vector<vector<T>>(V, vector<T>(V, INF)))
		{}
	bool addEdge(int from, int to, T cost) {
		if(cost >= d[from][to]) return false;
		d[from][to] = cost;
		return true;
	}
	void build() {
		for(int i=0; i < V; ++i) {               // 経由点 i
			for(int j = 0; j < V; ++j) {         // 始点 j
				for(int k = 0; k < V; ++k) {     // 終点 k
					d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
				}
			}
		}
	}
	T dist(int from, int to) {
		if(d[from][to] >= INF) return INF;
		return d[from][to];
	}
	void debug() {
		for(int i = 0; i < V; ++i) {
			for(int j = 0; j < V; ++j) {
				cout << d[i][j] << " ";
			}
			cout << endl;
		}
	}
};

void solve(int N, WarshallFloyd<int64_t> &wfL, WarshallFloyd<int64_t> &wfS, vector<int> &town) {
	const int64_t INVALID = 1e15;
	int tn = town.size();
	vector<vector<int64_t>> dp(tn, vector<int64_t>(N, INVALID));
	dp[0][town[0]] = 0;
	for(int i = 1; i < tn; ++i) {
		for(int j = 0; j < N; ++j) {
			if(wfL.dist(town[i - 1], town[i]) < INVALID) {
				dp[i][j] = min(dp[i][j], dp[i - 1][j] + wfL.dist(town[i - 1], town[i]));
			}
			for(int k = 0; k < N; ++k) {
				if(dp[i - 1][k] >= INVALID) continue;
				if(wfL.dist(town[i - 1], k) >= INVALID) continue;
				if(wfS.dist(k, j) >= INVALID) continue;
				if(wfL.dist(j, town[i]) >= INVALID) continue;
				dp[i][j] = min(dp[i][j], dp[i - 1][k] + wfL.dist(town[i - 1], k) + wfS.dist(k, j) + wfL.dist(j, town[i]));
			}
		}
	}
	int64_t ans = 1e15;
	for(int i = 0; i < N; ++i) {
		if(dp[tn - 1][i] >= INVALID) continue;
		ans = min(ans, dp[tn - 1][i]);
	}
	cout << ans << endl;
}

int main() {
	int N, M;
	while(cin >> N >> M and N > 0) {
		WarshallFloyd<int64_t> wfL(N), wfS(N);
		for(int i = 0; i < N; ++i) {
			wfL.addEdge(i, i, 0);
			wfS.addEdge(i, i, 0);
		}
		while(M--) {
			int x, y, t; cin >> x >> y >> t;
			x--; y--;
			char sl; cin >> sl;
			if(sl == 'L') {
				wfL.addEdge(x, y, t);
				wfL.addEdge(y, x, t);
			}
			if(sl == 'S') {
				wfS.addEdge(x, y, t);
				wfS.addEdge(y, x, t);
			}
		}
		int R; cin >> R;
		vector<int> z(R);
		for(int i = 0; i < R; ++i) {
			cin >> z[i];
			z[i]--;
		}
		wfL.build();
		wfS.build();
		solve(N, wfL, wfS, z);
	}
	return 0;
}


Measured memory_bytes: 5260
//TO CHANGE THE WORLD
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define L first
#define R second
typedef long long ll;

const int maxn=2e5+10;

int n, m, d[maxn];
bool mark[maxn];
vector<int> g[maxn];
queue<int> q;
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin>>n>>m;
    for(int i=0; i<m; i++)
    {
	int fi, se;
	cin>>fi>>se;
	fi--;se--;
	g[fi].pb(se), g[se].pb(fi);
    }
    q.push(0);
    mark[0] = 1;
    while(q.size())
    {
	int cur = q.front();
	q.pop();
	for(auto child:g[cur])
	    if(!mark[child])
	    {
		d[child] = d[cur] + 1;
		mark[child] = 1;
		q.push(child);
	    }
    }
    if(d[n-1] == 2) cout<<"POSSIBLE"<<endl;
    else cout<<"IMPOSSIBLE"<<endl;
}

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

int n,m,c,s,g;

int d_dist[30][110][110];
int d_final[110][110];

int p[30], q[30][60], r[30][60];

const int inf = 1e9;

int getcost(int dist, int *q, int *p){
    if(dist == inf) return inf;
    int res = 0;
    rep(i,1000000){
        if(dist <= q[i+1]){
            res += (dist-q[i]) * p[i];
            break;
        } else {
            res += (q[i+1]-q[i]) * p[i];
        }
    }
    return res;
}

signed main(){
    /*
      ????´?????????¢??§???????????¨???WF 1
      ??????????????¨???????????¨????????? 2
      ??????????????§WF 3
     */
    while(cin >> n >> m >> c >> s >> g && n){
        --s, --g;
        rep(ic,c)rep(i,n)rep(j,n) d_dist[ic][i][j] = inf;
        rep(i,n)rep(j,n) d_final[i][j] = inf;
        rep(i,c)rep(j,n) d_dist[i][j][j] = 0;
        rep(i,n) d_final[i][i] = 0;

        rep(i,m){
            int x,y,d,c;
            cin >> x >> y >> d >> c;
            --x, --y, --c;
            d_dist[c][x][y] = min(d_dist[c][x][y], d);
            d_dist[c][y][x] = min(d_dist[c][y][x], d);
        }

        rep(i,c) cin >> p[i];
        rep(i,c){
            q[i][0] = 0;
            rep(j,p[i]-1) cin >> q[i][j+1];
            q[i][p[i]] = inf*2;
            rep(j,p[i]) cin >> r[i][j];
        }

        // rep(i,c){
        //     rep(j,p[i]+10) cout << q[i][j] << ' ';
        //     cout << endl;
        //     rep(j,p[i]+10) cout << r[i][j] << ' ';
        //     cout << endl;
        // }
        // while(1);

        rep(ic,c) rep(k,n)rep(i,n)rep(j,n) {
            d_dist[ic][i][j] = min(d_dist[ic][i][j], d_dist[ic][i][k] + d_dist[ic][k][j]);
        }

        // rep(ic,c){
        //     rep(i,n){
        //         rep(j,n) {
        //             cout << d_dist[ic][i][j] << ' ';
        //         }
        //         cout << endl;
        //     }
        // }
        // while(1);

        rep(ic,c)rep(i,n)rep(j,n){
            d_final[i][j] = min(d_final[i][j], getcost(d_dist[ic][i][j], q[ic], r[ic]));
            // cout << getcost(d_dist[ic][i][j], r[ic], q[ic]) << endl;
        }

        // rep(i,n){
        //     rep(j,n) {
        //         cout << d_final[i][j] << ' ';
        //     }
        //     cout << endl;
        // }

        rep(k,n)rep(i,n)rep(j,n){
            d_final[i][j] = min(d_final[i][j], d_final[i][k] + d_final[k][j]);
        }
        int ans = d_final[s][g];
        cout << (ans == inf ? -1 : ans) << endl;
    }
}

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

//#pragma gcc optimize("O3,unroll-loop")
//#pragma gcc target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,abm,mmx,popcnt,tune=native")
//#define int long long
//#define double long double

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

    string s;
    cin >> s;

    for (char &c : s)
        if (c == '?')
            c = 'D';

    cout << s << '\n';

    return 0;
}

//      *   *  *****  *   *  *   *   ****  ****    ****     **    **
//     *   *  *      **  *  *   *  *      *   *  *        * *   * *
//    *****  *****  * * *  *   *  *      ****   *       *  *     *
//   *   *      *  *  **  *   *  *      *  *   *       *****    *
//  *   *  *****  *   *   ***    ****  *   *    ****     *   *****

//      *****  *****  *   *  *      *****  *   *  *****  *****
//        *   *   *  *   *  *        *    **  *    *    *   *
//       *   *   *  *****  *        *    * * *    *    *****
//   *  *   *   *    *    *        *    *  **    *    *
//  ****   *****    *    *****  *****  *   *    *    *


Measured memory_bytes: 3752
import numpy as np
N,M,C = map(int,input().split())
B = np.array(list(map(int,input().split())))
ans = 0
for _ in range(N):
    A = np.array(list(map(int,input().split())))
    ans = ans + 1 if np.dot(A,B)+C>0 else ans
print(ans)

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

using namespace std;
#define ll long long

const int N=1e6+100;
const int inf=0x3f3f3f3f;

int n,m;

ll qpow(ll x,ll n)
{
    ll sum=1;
    while(n){
        if(n&1){
            sum=sum*x;
        }
        x*=x;
        n>>=1;
    }
    return sum;
}
void solve()
{
    ll a,b;
    cin>>a>>b;
    ll len=b-a+1;
    if(len==1) {
        cout<<a<<endl;
        return ;
    }
    ll l,r;
    if(a%2) l=a,a++,len--;
    else l=0;
    if(b%2) r=0;
    else r=b,b--,len--;
    if(len%4) {
        cout<<(l^r^1)<<endl;
    }
    else cout<<(l^r)<<endl;

}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    solve();
    return 0;
}


Measured memory_bytes: 3644
#include<stdio.h>
int main()
{
	int A,B;
	scanf("%d\n",&A);
	scanf("%d",&B);
	if(A==1&&B==2)  printf("3");
	if(A==1&&B==3)  printf("2");
	if(A==2&&B==1)  printf("3");
	if(A==2&&B==3)  printf("1");
	if(A==3&&B==1)   printf("2");
	if(A==3&&B==2)    printf("1");
//	if((A+B)%2==0)  printf("2\n");
//	if((A+B)%2==1&&A!=1)  printf("1\n");
//	if((A+B)%2==1&&A!=3)   printf("3\n");
	return 0;
}

Measured memory_bytes: 128
// AOJ 2331 - Butterfly
#include <iostream>
using namespace std;

#define REP(i,x) for (int i = 0; i < (int)x; i++)
#define ALL(c) (c).begin(), (c).end()
#define RANGE(i,x,y) for (int i = (int)x; i <= (int)y; i++)
#define LOOP while (true)

const int INF = 1 << 22;

const int MAX_N = 100;
const int MAX_M = 16;
const int WIDTH = 16;

int happy[MAX_N];
int schedule[MAX_N];

int dp[2][1 << WIDTH];

int N, M;

int make_mask(int s, int e) {
    s -= 6; e -= 6;
    int w = 1, res = 0;
    REP (bit, WIDTH) {
        if (bit >= s && bit < e) res += w;
        w *= 2;
    }
    return res;
}

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

    while (cin >> N, N) {
        fill((int* )dp, (int* )(dp + 2), -INF);

        REP (i, N) {
            cin >> M >> happy[i];
            int mask = 0;
            REP (j, M) {
                int s, e;
                cin >> s >> e;
                mask |= make_mask(s, e);
            }
            schedule[i] = mask;
        }

        dp[0][0] = 0;
        REP (i, N) {
            REP (j, 1 << WIDTH) {
                // スケジュールを選べるのなら
                if ((j & schedule[i]) == 0) {
                    dp[(i+1)%2][j|schedule[i]] = max(dp[(i+1)%2][j|schedule[i]], dp[i%2][j]+happy[i]);
                }
                dp[(i+1)%2][j] = max(dp[(i+1)%2][j], dp[i%2][j]);
            }
        }

        int ans = 0;
        REP (i, 1 << WIDTH) {
            ans = max(ans, dp[N%2][i]);
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 1712
#include<iostream>
using namespace std;
int main(void){
    double n,h,count1=0,count2=0,count3=0,count4=0,count5=0,count6=0;
    cin >> n;
    for(int a=0; a<n; a++){
        cin >> h;
        if(h<165.0)                 count1+=1;
        else if(165.0<=h&&h<170.0)  count2+=1;
        else if(170.0<=h&&h<175.0)  count3+=1;
        else if(175.0<=h&&h<180.0)  count4+=1;
        else if(180.0<=h&&h<185.0)  count5+=1;
        else if(185.0<=h)           count6+=1;
    }
    cout << "1:";
    for(int b=0; b<count1; b++){
        cout << "*";
    }
    cout << endl;
    cout << "2:";
    for(int c=0; c<count2; c++){
        cout << "*";
    }
    cout << endl;
    cout << "3:";
    for(int d=0; d<count3; d++){
        cout << "*";
    }
    cout << endl;
    cout << "4:";
    for(int e=0; e<count4; e++){
        cout << "*";
    }
    cout << endl;
    cout << "5:";
    for(int f=0; f<count5; f++){
        cout << "*";
    }
    cout << endl;
    cout << "6:";
    for(int g=0; g<count6; g++){
        cout << "*";
    }
    cout << endl;
}


Measured memory_bytes: 3176
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) long long((x).size())
#define OUT(x) cout << (x) << endl
typedef long long ll;
typedef vector<ll> V;
typedef vector<vector<ll>> VV;
typedef pair<ll, ll> P;
typedef map<string, ll> M;
typedef unordered_map<ll, ll> HM;
typedef set<ll> S;
typedef multiset<ll> MS;
typedef queue<ll> Q;

int main(){
    ll n,x; cin>>n>>x;
    ll a[n];
    for(ll i=0; i<n; i++)
        cin>>a[i];
    ll ans = 0;
    if(a[0] > x){
        ans += a[0]-x;
        a[0] = x;
    }
    if(a[n-1] > x){
        ans += a[n-1]-x;
        a[n-1] = x;
    }
    for(ll i=0; i<n-1; i++){
        if(a[i]+a[i+1]>x){
            ans += a[i]+a[i+1]-x;
            a[i+1] = x-a[i];
        }
    }
    OUT(ans);
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
const int N=105,V=1005;
int dp[N][N*V+1],w[N],v[N];
int main()
{
    int n,W;
    scanf("%d%d",&n,&W);
    for(int i=0;i<n;i++)	
    	scanf("%d%d",&w[i],&v[i]);
    fill(dp[0],dp[0]+N*V+1,INT_MAX/2);
    dp[0][0]=0;
    for(int i=0;i<n;i++)
    	for(int j=0;j<=N*V;j++)
    		if(j<v[i])
    			dp[i+1][j]=dp[i][j];
    		else
    			dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i]);
	int res=0;
	for(int i=0;i<=N*V;i++)
		if(dp[n][i]<=W)
			res=i;
	printf("%d\n",res);
    return 0;
}


Measured memory_bytes: 43264
#include <cstdio>
#include <cmath>
#include <algorithm>
const double PI =3.141592653589793238;
#define MAXN 10000
#define MAXC 10000
using namespace std;
int arr[20];
int x, y;

int main(){
	arr[1]=arr[3]=arr[5]=arr[7]=arr[8]=arr[10]=arr[12]=1;
    arr[4]=arr[6]=arr[9]=arr[11]=2;
    arr[2]=3;
	scanf("%d%d",&x, &y);
	puts(arr[x]==arr[y]?"Yes":"No");
	return 0;
} 

Measured memory_bytes: 128
#include<iostream>

using namespace std;

int main(){
    int N;
    int map[2][110];

    cin >> N;

    for (int i = 0; i < 2;i++){
        for (int j = 0; j < N;j++){
            cin >> map[i][j];
        }

    }
    int ans = 0;
    for (int i = 0; i < N;i++){
        int tmp = 0;
        for (int j = 0; j <= i;j++){
            tmp += map[0][j];
        }
        for (int j = i; j < N;j++){
            tmp += map[1][j];
        }
        ans = max(ans, tmp);
    }
    cout << ans << endl;
}

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

using namespace std;

const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;

int n;
int pos[maxn];
long long fact[maxn];

long long qpow(long long a, long long b) {
    long long ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}

long long C(int m, int n) {
    if (n > m) return 0;
    return fact[m] * qpow(fact[m - n] * fact[n] % mod, mod - 2) % mod;
}

int main(int argc, char const *argv[]) {
    
    cin >> n;

    fact[0] = 1;
    for (int i = 1; i <= n + 2; i ++)
        fact[i] = fact[i - 1] * i % mod;

    int pos1, pos2;
    for (int i = 1; i <= n + 1; i ++) {
        int x;
        scanf("%d", &x);
        if (!pos[x]) pos[x] = i;
        else {
            pos1 = pos[x];
            pos2 = i;
        }
    }

    long long pre = pos1 - 1, last = n + 1 - pos2;

    printf("%d\n", n);
    for (int i = 2; i <= n + 1; i ++) {
        long long tmp = C(n + 1, i);
        long long tmp2 =C(pre + last, i - 1);
        // if (pre + last < i - 1) tmp2 = 0;
        long long ans = (tmp - tmp2 + mod) % mod;
        printf("%lld\n", ans);
    }

    return 0;
}

Measured memory_bytes: 2432
#include <bits/stdc++.h>
using namespace std;
 
#define F first
#define S second 
#define mp make_pair
#define pb push_back
#define pf push_front
#define speed_up ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define debug cerr << "OK\n";
#define ub upper_bound
#define lb lower_bound
#define treap_pair pair<treap*, treap*>
 
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef set <int> si;
typedef set <ll> sll;
typedef multiset <int> msi;
typedef multiset <ll> msll;
typedef map <int, int> mi;
typedef map <ll, int> mll;
 
const int N = 2e5 + 2;
const int M = 1e5 + 2;
const int mod = 998244353;
const int inf = 1e9;
const ll INF = 1e16;

void data() {
	#ifdef PC
		freopen("main.in", "r", stdin);
		freopen("main.out", "w", stdout);
	#endif
}

int n, a[N];
ll col[N];
ll ans;

int main() {
	data();
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		ans += col[a[i]];
		col[a[i]]++;
	}
	for (int i = 1; i <= n; ++i) {
		ans -= col[a[i]] * (col[a[i]] - 1) / 2LL;
		printf("%lld\n", ans + max(0LL, (col[a[i]] - 1) * (col[a[i]] - 2) / 2LL));
		ans += col[a[i]] * (col[a[i]] - 1) / 2LL;
	}

}

/*
	Timus: 288481RF
	CodeForces: fractal
*/


Measured memory_bytes: 3968
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+100;
const int mod = 1e9+7;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
inline bool read(ll &num) {
    char in;bool IsN=false;
    in=getchar();
    if(in==EOF) return false;
    while(in!='-'&&(in<'0'||in>'9')) in=getchar();
    if(in=='-'){ IsN=true;num=0;}
    else num=in-'0';
    while(in=getchar(),in>='0'&&in<='9'){
            num*=10,num+=in-'0';
    }
    if(IsN) num=-num;
    return true;
}
queue<int> G[N];
int maxx[N];
bool vis[N];
ll a[2000][2000];
int main(){
   //freopen("1.in", "r", stdin);
    ll n;
    read(n);
    rep(i,1,n){
        maxx[i]=0;
        rep(j,1,n-1){
            read(a[i][j]);
            G[i].push(a[i][j]);
        }
    }
    int ans=0;
    while(1){
        bool flag=0;
        rep(i,1,n){
            if(G[i].empty()) continue;
            if(G[G[i].front()].front()==i){
                maxx[i]=maxx[G[i].front()]=max(maxx[i],maxx[G[i].front()])+1;
                G[G[i].front()].pop();
                G[i].pop();
                flag=1;
            }
        }
        if(flag==0){
            cout<<-1<<endl;
            return 0;
        }
        ll num=0;
        rep(i,1,n){
            num+=G[i].size();
        }
        if(num==0){
            break;
        }
    }
    rep(i,1,n){
        ans=max(ans,maxx[i]);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 695168
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using ll = long long int;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

ll ans[11111];

int main(void){
	ll n,x,y,z,i;
	std::cin >> n;
	for(x=1ll; x<=200ll; ++x){
		for(y=1ll; y<=200ll; ++y){
			for(z=1ll; z<=200ll; ++z){
				i = x*x+y*y+z*z+x*y+y*z+z*x;
				if(i<=n){
					++ans[i];
				}
			}
		}
	}
	for(i=1ll; i<=n; ++i){
		std::cout << ans[i] << std::endl;
	}
	return 0;
}


Measured memory_bytes: 3616
//{{{
#include <bits/stdc++.h>
using namespace std;
#define repX(a,b,c,x,...) x
#define repN(a) repX a
#define rep(...) repN((__VA_ARGS__,rep3,rep2,loop))(__VA_ARGS__)
#define rrep(...) repN((__VA_ARGS__,rrep3,rrep2))(__VA_ARGS__)
#define loop(n) rep2(i_,n)
#define rep2(i,n) rep3(i,0,n)
#define rep3(i,begin,end) for(int i=(int)(begin),i##_end=(int)(end);i<i##_end;++i)
#define rrep2(i,n) rrep3(i,n,0)
#define rrep3(i,begin,end) for(int i=(int)(begin-1),i##_end=(int)(end);i>=i##_end;--i)
#define foreach(x,a) for(auto&x:a)
using ll=long long;
const ll MOD=(ll)1e9+7;
//}}}

int f(int a, int b){
  int res;
  if(b < 0){
    res = -a;
  }else if(a > 0){
    res = b;
  }else{
    res = 2 * min(-a, b) + max(-a, b);
  }
  return res;
}

int x[100000];
int main(){
  int N, K;
  cin >> N >> K;
  rep(i, N) cin >> x[i];
  int ans = f(x[0], x[K - 1]);
  rep(i, N - K + 1){
    ans = min(ans, f(x[i], x[i + K - 1]));
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin >> n;
  
  int dig = 0;
  int N = n;
  
  while ( n )
  {
    dig += n%10;
    n/=10;
  }
  
  if ( N%dig==0 ) { cout << "Yes"; }
  else { cout << "No"; }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define irep(i, n) for (int i = (n); i >= 0; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 30;
 
int main() {
  int n;
  cin >> n;
  vector<int> p(n);
  rep(i,n) cin >> p[i];
  int cnt = 0;
  rep(i,n-1) {
    if (p[i] == i+1) {swap(p[i],p[i+1]);cnt++;}
  }
  if (p[n-1] == n) cnt++;
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 3768
def main():
    a, b, k = map(int, input().split())
    printed = 0
    l = []
    for i in range(k):
        if a + i > b:
            return
        print(a + i)
        printed = a + i
        l.append(printed)
    if printed >= b:
        return
    for i in range(k):
        if b - k + 1 + i in l:
            continue
        elif b - k + 1 + i > b:
            break
        print(b - k + 1 + i)

main()

Measured memory_bytes: 9128
h,w,r = map(int,input().split())
l=[];an=0
cr=[];k=[0]*w
for i in range(h):
  x=list(input())
  l.append(x)
  cr.append(x.count('#'))
  for j in range(w):
    if x[j]=='#':
      k[j]+=1
ar=cr+k;tot=sum(cr)
tt=len(ar)
for i in range(1<<tt):
  re=tot;rr=[]
  cc=[]
  for j in range(tt):
    if i&(1<<j):
      re-=ar[j]
      if j>=h:
        cc.append(j-h)
      else:
        rr.append(j)
  for j in rr:
    for y in cc:
      if l[j][y]=='#':
        re+=1
  #print(i,rr,cc,re)
  if re==r:
    an+=1
  #print(i,re)
print(an)

Measured memory_bytes: 9200
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
const LL MOD = 1000000007LL;
struct UnionFind {
	int *par;
	int *rank;
	int size;
	UnionFind(int n) :size(n) {
		par = new int[n];
		rank = new int[n];
		for (int i = 0; i < n; i++) {
			par[i] = i;
			rank[i] = 0;
		}
	}
	int find(int x) {
		if (x == par[x]) return x;
		return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		if (rank[x] < rank[y]) {
			par[x] = y;
		}
		else {
			par[y] = x;
			if (rank[x] == rank[y]) {
				rank[x]++;
			}
		}
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
};
int idx[100001];
int main() {
	int N, M;
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		int p;
		cin >> p;
		idx[p] = i;
	}
	UnionFind U(N + 1);
	for (int i = 0; i < M; i++) {
		int x, y;
		cin >> x >> y;
		U.unite(x, y);
	}
	int ans = 0;
	for (int i = 1; i <= N; i++) {
		if (U.same(i, idx[i])) ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1408
# -*- coding: utf-8 -*-
# B

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

x, y = map(int, input().split())

for a in range(x+1):
    if a * 2 + (x-a)*4 == y:
        print('Yes')
        sys.exit()
print('No')


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


def solve(N: int, P: "List[int]"):
    pos = {n: i+1 for i, n in enumerate(P)}
    L1 = list(range(-1, N+1))
    L1[0] = 0
    L2 = list(range(-2, N))
    L2[0] = 0
    L2[1] = 0
    R1 = list(range(1, N+3))
    R1[-1] = N+1
    R2 = list(range(2, N+4))
    R2[-1] = N+1
    R2[-2] = N+1

    res = 0
    for i in range(1, N+1):
        s = pos[i]
        num = 0
        num += (R2[s] - R1[s]) * (s - L1[s])
        num += (L1[s] - L2[s]) * (R1[s] - s)
        res += i * num

        L1[R1[s]] = L1[s]
        L2[R1[s]] = L2[s]
        L2[R2[s]] = L1[s]
        R1[L1[s]] = R1[s]
        R2[L1[s]] = R2[s]
        R2[L2[s]] = R1[s]

    print(res)        
    return


# Generated by 1.1.5 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
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, P)

if __name__ == '__main__':
    main()


Measured memory_bytes: 63004
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <iostream>
#include <climits>
#include <cfloat>

using namespace std;

void printTime(int sec)
{
	printf("%02d:%02d:%02d\n", sec/3600, sec/60%60, sec%60);
}
int main()
{
	while (true)
	{
		int h, m, s;
		scanf("%d %d %d\n", &h, &m, &s);
		if (h == -1 && m == -1 && s == -1)
			break;

		const int VideoLen = 2*3600;
		int sec = h*3600+m*60+s;
		printTime(VideoLen - sec);
		printTime(VideoLen*3 - sec*3);
	}

	return 0;
}

Measured memory_bytes: 0
#include<iostream>
using namespace std;
int n;string s;
main()
{
	cin>>n;
	while(cin>>s,s!="=")
	{
		int a;cin>>a;
		if(s=="+")n+=a;
		else if(s=="-")n-=a;
		else if(s=="*")n*=a;
		else n/=a;
	}
	cout<<n<<endl;
}



Measured memory_bytes: 3128
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORR(i,m,n) for(int i = m - 1; i >= n; i--)
#define ALL(v) v.begin(), v.end()
#define itn int
#define Yes() cout << "Yes" << endl
#define No() cout << "No" << endl
#define YES() cout << "YES" << endl
#define NO() cout << "NO" << endl
#define println(x) cout << x << endl
#define print(x) cout << x << " "
template<typename T, typename U>
inline bool CMAX(T &m, U x) { if (m < x) { m = x; return true; } return false; }
template<typename T, typename U>
inline bool CMIN(T &m, U x) { if (m > x) { m = x; return true; } return false; }

typedef long long lint;
typedef long double ldouble;
const int INF = 1e9;
const lint LINF = 1e18;
const int MOD = 1e9+7;

lint cnt = 0;
void dfs(lint h,lint num){
    if(h == 1){
        cnt += num;
        return;
    }else{
        cnt += num;
        dfs(h/2,num * 2);
    }
}
int main(){
    lint h;
    cin >> h;
    dfs(h,1);
    println(cnt);
    return 0;
}

Measured memory_bytes: 256
def solve():
    N = int(raw_input())
    p = [int(_) for _ in raw_input().split()]
    ret = 0
    for i in range(1, N - 1):
        if (p[i - 1] < p[i] and p[i] < p[i+1]) or (p[i-1] > p[i] and p[i] > p[i+1]):
            ret += 1
    print ret

if __name__ == '__main__':
    solve()


Measured memory_bytes: 28012
import sys
import math
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

s = S()
day = {"SUN":7, "MON":6, "TUE":5, "WED":4, "THU":3, "FRI":2, "SAT":1}

print(day[s])

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

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

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

int main(int argc, char *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    string S;
    cin >> S;

    ll K;
    cin >> K;

    rep (i, K) {
        if (S[i] != '1') {
            cout << S[i] << endl;
            break;
        }
        if (S[i] == '1' && i == K-1) {
            cout << 1 << endl;
            break;
        }
    }

    return 0;
}

Measured memory_bytes: 256
N,K = map(int,input().split())
h = list(map(int,input().split()))
INF = 10**10

dp = [INF]*N
dp[0] = 0

def cost(i,j): #足場iから足場jにジャンプするコスト
    return dp[i] + abs(h[j] - h[i])

if N <= K:
    for i in range(1,N):
        for j in range(i):
            dp[i] = min(dp[i],cost(j,i))
else:
    for i in range(1,K):
        for j in range(i):
            dp[i] = min(dp[i],cost(j,i))
    for i in range(K,N):
        for j in range(i-K,i):
            dp[i] = min(dp[i],cost(j,i))

print(dp[N-1])

Measured memory_bytes: 52832
#include <stdio.h>

int main(){
  int n, k, i, c;
  
  scanf("%d %d", &n, &k);
  int A[n];
  for (i=0; i<n; i++) scanf("%d", &A[i]);
  for (i=0; i<n; i++){
    if (A[i] >= k) {
      c = c+1;
    }
    
  }
  printf("%d", c);
  return 0;
}

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

int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    if(s[0] == 'W' || s[2*n-1] == 'W') {
        cout << "0" << endl;
        return 0;
    } 
    vector<bool> flag(2*n,false);
    bool a = false;
    for(int i = 1; i < 2*n; i++){
        if(s[i] != s[i-1]){
            flag[i] = a;
        } else {
            flag[i] = !a;
            a = !a;
        }
    }
    ll l[2*n] = {};
    l[0] = 1;
    for(int i = 1; i < 2*n; i++){
        if(flag[i]) l[i] = l[i-1];
        else l[i] = l[i-1] + 1;
    }
    if(l[2*n-1] != n){
        cout << "0" << endl;
        return 0;
    }
    ll ans = 1;
    ll count = 0;
    rep(i,2*n){
        if(flag[i]) {
            ans = ans*(l[i]-count) % mod;
            count++;
        }
    }
    for(ll i = 1; i <= n; i++) ans = (ans*i) % mod;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2180
#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
int n, g,h,w,x,y,t;
int dx[8] = { 1, 0, -1, 0 };
int dy[8] = { 0, 1, 0, -1 };
int main() {
	cin >> n;char c;g = 0;h = 0;w = 0;bool r = true;
	for (int i = 0;i < n;i++) {
		cin >> t >> x >> y;
		int dis = abs(x - h) + abs(y - w);
		if (dis <= t - g && dis % 2 == (t - g) % 2)
			continue;
		else {
			r = false;
		}
		g = t; h = x; w = y;
	} 
	if (r) {
		cout << "Yes" << endl;
	}
	else
		cout << "No" << endl;
}

Measured memory_bytes: 256
!function(e){var t={};function r(n){if(t[n])return t[n].exports;var o=t[n]={i:n,l:!1,exports:{}};return e[n].call(o.exports,o,o.exports,r),o.l=!0,o.exports}r.m=e,r.c=t,r.d=function(e,t,n){r.o(e,t)||Object.defineProperty(e,t,{enumerable:!0,get:n})},r.r=function(e){"undefined"!=typeof Symbol&&Symbol.toStringTag&&Object.defineProperty(e,Symbol.toStringTag,{value:"Module"}),Object.defineProperty(e,"__esModule",{value:!0})},r.t=function(e,t){if(1&t&&(e=r(e)),8&t)return e;if(4&t&&"object"==typeof e&&e&&e.__esModule)return e;var n=Object.create(null);if(r.r(n),Object.defineProperty(n,"default",{enumerable:!0,value:e}),2&t&&"string"!=typeof e)for(var o in e)r.d(n,o,function(t){return e[t]}.bind(null,o));return n},r.n=function(e){var t=e&&e.__esModule?function(){return e.default}:function(){return e};return r.d(t,"a",t),t},r.o=function(e,t){return Object.prototype.hasOwnProperty.call(e,t)},r.p="",r(r.s=1)}([function(e,t){e.exports=require("fs")},function(e,t,r){"use strict";r.r(t);var n,o=r(0);500*(n=o.readFileSync("/dev/stdin","utf8").trim()).split(" ")[0]>=n.split(" ")[1]?console.log("Yes"):console.log("No")}]);

Measured memory_bytes: 7880
#define MYDEBUG
#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <algorithm>
#include <queue>
#include <set>
#include <cstdio>
#include <unordered_map>

#ifdef MYDEBUG
#define debug(x) cout<<#x<<": "<<x<<endl
#else
#define debug(x)
#endif
#define ll long long
#define ull unsigned long long
#define eps 1e-14
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
	out << "[";
	size_t last = v.size() - 1;
	for (size_t i = 0; i < v.size(); ++i) {
		out << v[i];
		if (i != last)
			out << ",";
	}
	out << "]";
	return out;
}

void solve() {
	int a, b;
	cin >> a >> b;
	if (a == 1)
		a += 14;
	if (b == 1)
		b += 14;
	if (a < b)
		cout << "Bob" << endl;
	else if (a == b)
		cout << "Draw" << endl;
	else
		cout << "Alice" << endl;
}
int main() {
	solve();
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){

    int n, a[100010], b[100010], soma = 0;

    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%d%d", &a[i], &b[i]);

        soma += (b[i]-a[i])+1;
    }

    printf("%d\n", soma);

    return 0;
}


Measured memory_bytes: 128
/*
 *Author - Bhanu Pratap
 */
#include <bits/stdc++.h>
#define endl '\n'
#define all(c) c.begin(), c.end()

using namespace std;

typedef long long int ll;
typedef long double ld;

const ll mod = 1e9 + 7;
const ld PI = 3.141592653589793;

void solve () {
    int n;
    cin>>n;
    vector <int> v(n);
    for (int i=0; i<n; i++) cin>>v[i];
    sort(all(v));
    double sum=v[0];
    for (int i=1; i<n; i++) {
        sum+=v[i];
        sum/=2.0;
    }
    cout<<fixed<<setprecision(14)<<sum;
}
main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    
    solve();
    return 0;
    }


Measured memory_bytes: 256
a,A=input().split()
b,B=input().split()
c,C=input().split()
d,D=input().split()
e=a,A,b,B,c,C,d,D
i=0
w=0
x=[0,0,0,0]
while i<8 : 
    if int(e[i])==1 : w=6000*int(e[i+1]) 
    elif int(e[i])==2 : w=4000*int(e[i+1])
    elif int(e[i])==3 : w=3000*int(e[i+1])
    else : w=2000*int(e[i+1])
    x[int(i/2)]=w
    i=i+2
W=x[0]
X=x[1]
Y=x[2]
Z=x[3]
    
print(W)
print(X)
print(Y)
print(Z)


Measured memory_bytes: 5604
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--) 
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define downque(que) priority_queue<ll> que;
#define upque(que) priority_queue<ll, vector<int>, greater<int>> que;
typedef long long ll;
typedef vector<vector<int>> Matrix;
const int MOD = 1e9 + 7;
const int MAX = 1e7;
const int INF = numeric_limits<int>::max();

int main(){
 int a,b,t=0,res=0; cin>>a>>b;
 int diff=b-a;
 FOR(i,1,diff)t+=i;
 res=t-a;
 cout<<res<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rp(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////

void solve(){
    string s,t;
    cin >> s >> t;
    sort(all(s));
    sort(all(t));
    reverse(all(t));
    Yes(s<t);
    return;
}
int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    std::cout<<std::fixed<<std::setprecision(30);
    solve();
    return 0;
}

Measured memory_bytes: 3624
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] h = new int[n];
        for (int i = 0; i < n; i++) {
            h[i] = sc.nextInt();
        }
        int ans = solve(n, h);
        System.out.println(ans);

    }

    private static int solve(int n, int[] h) {
        int maxLayer = 0;
        for (int i = 0; i < n; i++) {
            maxLayer = Math.max(maxLayer, h[i]);
        }

        int[][] garden = new int[maxLayer][n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < h[i]; j++) {
                garden[j][i] = 1;
            }
        }

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

                int current = garden[i][j];
                int next = garden[i][j + 1];
                if (current == 1 && next == 0) {
                    // 水の切れ目部分
                    ans++;
                }
            }
        }
        return ans;
    }
}


Measured memory_bytes: 23764