akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

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

void solve() {
  int a, b;
  cin >> a >> b;
  if(a%2 != b%2) {
    cout << "IMPOSSIBLE\n";
  }
  else {
    cout << (a+b)/2 << "\n";
  }
}

void casesolve() {
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
  // casesolve();
}


Measured memory_bytes: 256
S = input()
T = input()

start = len(S) - len(T)
end = len(S)

ans = ''
while start >= 0:
	test = S[start:end]
	solve = True
	for i in range(len(T)):
		c1,c2 = test[i],T[i]
		if c1 != c2 and c1 != '?':
			solve = False
			break
	if solve:
		ans = S[:start] + T + S[end:]
		break
	start -= 1
	end -= 1
if len(ans) > 0:
	print(ans.replace('?', 'a'))
else:
	print('UNRESTORABLE')

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

using namespace std;
using ll = long long;
using ii = pair<int, int>;

const int MAX { 200010 };
const ll MOD { 1000000007 }, oo { 1LL << 62 };

vector<int> solve(const string& s)
{
    int N = s.size();
    vector<int> ls, rs;

    for (int i = 0; i < N; ++i)
        s[i] == 'L' ? ls.push_back(i) : rs.push_back(-i);

    sort(rs.begin(), rs.end());

    vector<int> ans(N, 0);

#ifdef DEBUG
for (auto r : rs)
    cout << r << ' ';
cout << endl;
#endif

    for (int i = 0; i < N; ++i)
    {
        switch (s[i]) {
        case 'R':
            {
                auto it = upper_bound(ls.begin(), ls.end(), i);
                auto dist = *it - i;

                dist % 2 ? ans[*it - 1]++ : ans[*it]++;
#ifdef DEBUG
cout << "R: criança " << i << " termina em " << (dist % 2 ? *it - 1 : *it) << endl;
cout << "   dist = " << dist << endl;
cout << "   ans = ";
    for (size_t i = 0; i < ans.size(); ++i)
        cout << ans[i] << (i + 1 == ans.size() ? '\n' : ' ');
#endif
                break;
            }

        default:
            {
                auto it = upper_bound(rs.begin(), rs.end(), -i);
                auto dist = i - (*it);

                dist % 2 ? ans[-(*it) + 1]++ : ans[-(*it)]++;
#ifdef DEBUG
cout << "R: criança " << i << " termina em " << (dist % 2 ? *it - 1 : *it) << endl;
cout << "   dist = " << dist << ", it = " << *it << endl;
cout << "   ans = ";
    for (size_t i = 0; i < ans.size(); ++i)
        cout << ans[i] << (i + 1 == ans.size() ? '\n' : ' ');
#endif

                break;
            }
        }
    }

    return ans;
}

int main()
{
    ios::sync_with_stdio(false);

    string s;
    cin >> s;

    auto ans = solve(s);

    for (size_t i = 0; i < ans.size(); ++i)
        cout << ans[i] << (i + 1 == ans.size() ? '\n' : ' ');

    return 0;
}


Measured memory_bytes: 1356
#include <iostream>
#include <string>
#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;

int main() {
	string a;
	cin >> a;
	bool f = 0;
	for (int i = 0; i < a.size()-1; i++) {
		for (int j = i+1; j < a.size(); j++) {
			if (a[i] == a[j])f = 1;
		}
	}
	if (f == 1)cout << "no\n";
	else cout << "yes\n";
	return 0;
}

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

#define MOD 1000000007

int main(){
  long long n,all = 1,ng = 1,ng0 = 1,ng9 = 1,ans;
  cin >> n;
  if(n == 1){
    cout << 0 << endl;
    return 0;
  }
  for(int i = 0;i < n;i++){
    all = all * 10 % MOD;
    ng = ng * 8 % MOD;
    ng0 = ng0 * 9 % MOD;
    ng9 = ng9 * 9 % MOD;
  }
  ans = (all - ng0 + MOD) % MOD;
  ans = (ans - ng9 + MOD) % MOD;
  ans = (ans + ng + MOD) % MOD;
  cout << ans << endl;
}

Measured memory_bytes: 3636
#include <stdio.h>

int main(void)
{
  int i;
  int divisor = 0;
  int a, b, c;

  scanf("%d %d %d", &a, &b, &c);

  for (i = a; i <= b; i++) {
    if (c % i == 0) divisor++;
  }

  printf("%d\n", divisor);
  
  return 0;
}

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

int main() {
  int N, A;
  cin >> N >> A;
  
  int N1 = N % 500;
  
  if(N1 <= A){
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }  
}


Measured memory_bytes: 256
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cfloat>
#include <complex>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

vector<vector<ll> > table;
vector<P> roads;
vector<P> qs;

ll N, M, Q;

void buildTable(vector<ll> L, vector<ll> R) {
  vector<vector<ll> > sum(N + 1, vector<ll>(N + 1, 0));
  for (int i = 0; i < M; i++) {
    sum[L[i]][R[i]]++;
  }

  table = vector<vector<ll> >(N + 1, vector<ll>(N + 1, 0));
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      table[i][j] += table[i - 1][j];
      table[i][j] += table[i][j - 1];
      table[i][j] -= table[i - 1][j - 1];
      table[i][j] += sum[i][j];
    }  // j
  }    // i

  return;
}

ll getTable(ll L, ll R) {
  ll ans = table[R][R] - table[R][L-1] - table[L-1][R] + table[L-1][L-1];
  return ans;
}

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

  vector<ll> L(M);
  vector<ll> R(M);
  for (int i = 0; i < M; i++) {
    cin >> L[i] >> R[i];
  }

  buildTable(L, R);  

  for (int i = 0; i < Q; i++) {
    ll p, q;
    cin >> p >> q;
    cout << getTable(p, q) << endl;
  }

  return 0;
}


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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define _GLIBCXX_DEBUG
#define fi first
#define se second

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vd = vector<double>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vvd = vector<vd>;
using vvvi = vector<vvi>;
using vvvll = vector<vvll>;
using vvvd = vector<vvd>;

const double pi=acos(-1);
const ll MOD=1e9+7;
const ll INF=(1LL<<60);

int main() {
    char s;
    cin>>s;
    s++;
    cout<<s<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 1000000000000000001;
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define eb emplace_back
#define pb push_back
#define f first
#define s second
using namespace std;


ll gcd(ll a, ll b)   //Function to find gcd of two numbers
{
    if (a == 0)
    return b;
    return gcd(b % a, a);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin>>n;
    
    if(n>=30)
    cout<<"Yes"<<endl;
    else
    cout<<"No"<<endl;
    
   

    return 0;
}

Measured memory_bytes: 3604
N = int(input())
s = []
for _ in range(N):
    s.append(int(input()))

if sum(s) % 10 != 0:
    print(sum(s))

else:
    min_s = 0
    sorted_s = sorted(s, reverse=True)
    for ss in sorted_s:
        if ss % 10 != 0:
            min_s = ss

    if min_s == 0:
        print(0)
    else:
        print(sum(s) - min_s)


Measured memory_bytes: 3060
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x = Integer.parseInt(sc.next());
		sc.close();
		String ans = "NO";
		if(x == 3 || x == 5 || x == 7)ans = "YES";
		System.out.println(ans);
	}
}


Measured memory_bytes: 21716
#include <stdio.h>

int main(){
    int H, W, i, j;
    
    while(1){
        scanf("%d %d", &H, &W);
        if(H == 0 && W == 0) break;
/*        if(H < 3 || H > 300 || W > 100){printf("error\n");return 0;} */
    
        for(i = 0; i < H; i++){
            for(j = 0; j < W; j++){
                if(i == 0 || i == (H -1) || j == 0 || j == (W - 1)){
                    printf("#");
                }else{
                    printf(".");
                }
            }
            printf("\n");
        }
        printf("\n");
    }
        return 0;
}

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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#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(ALL((c)))
#define RSORT(c) sort(RALL((c)))

#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;
}
template<class S, class T>
ostream& operator<<(ostream& os, pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


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);

  int N; cin >> N;
  map<LL,LL> xs;
  vector<bool> isp(N+1, true);
  FOR(i,2,N+1){
	if(!isp[i]) continue;
	xs[i]++;
	for(int j=i+i;j<=N;j+=i){
	  isp[j] = false;
	  int tmp = j;
	  while(tmp % i == 0){
		tmp /= i;
		xs[i]++;
	  }
	}
  }

  LL ans = 1;
  for(auto&& p: xs){
	(ans *= p.SS+1) %= MOD;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int num[105];
int main()
{
	int flag=1,ans=0,n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&num[i]);
	}
	for(int i=2;i<=n;i++)
	{
		if(num[i]==num[i-1]&&flag==1)
		{
			ans++;
			flag=0;
		}
		else if(flag==0)
		{
			flag=1;
		}
	} 
	printf("%d",ans);
	return 0;
}

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

bool check(int N, const std::string& s, std::string& t){
    for(int i = 2; i < N; i++){
        if(s.at(i-1) == 'o' && t.at(i-1) == 'S'){
            t.at(i) = t.at(i-2);
        }else if(s.at(i-1) == 'o' && t.at(i-1) == 'W'){
            t.at(i) = t.at(i-2) == 'S' ? 'W' : 'S';
        }else if(s.at(i-1) == 'x' && t.at(i-1) == 'S'){
            t.at(i) = t.at(i-2) == 'S' ? 'W' : 'S';
        }else if(s.at(i-1) == 'x' && t.at(i-1) == 'W'){
            t.at(i) = t.at(i-2);
        }
    }
    bool f = false;
    if(s.at(0) == 'o' && t.at(0) == 'S'){
        if(t.at(N-1) == t.at(1)) f = true;
    }else if(s.at(0) == 'o' && t.at(0) == 'W'){
        if(t.at(N-1) != t.at(1)) f = true;
    }else if(s.at(0) == 'x' && t.at(0) == 'S'){
        if(t.at(N-1) != t.at(1)) f = true;
    }else if(s.at(0) == 'x' && t.at(0) == 'W'){
        if(t.at(N-1) == t.at(1)) f = true;
    }
    if(!f) return false;
    f = false;
    if(s.at(N-1) == 'o' && t.at(N-1) == 'S'){
        if(t.at(0) == t.at(N-2)) f = true;
    }else if(s.at(N-1) == 'o' && t.at(N-1) == 'W'){
        if(t.at(0) != t.at(N-2)) f = true;
    }else if(s.at(N-1) == 'x' && t.at(N-1) == 'S'){
        if(t.at(0) != t.at(N-2)) f = true;
    }else if(s.at(N-1) == 'x' && t.at(N-1) == 'W'){
        if(t.at(0) == t.at(N-2)) f = true;
    }
    if(!f) return false;
    return true;
}

int main(int argc, char **argv)
{
    int N;
    std::string s;
    
    std::cin >> N >> s;

    {
        std::string t(N, ' ');
        t.at(0) = 'S'; t.at(1) = 'S'; // assumption
        bool flag = check(N, s, t);
        if(flag){
            std::cout << t << std::endl;
            return 0;
        }
    }
    {
        std::string t(N, ' ');
        t.at(0) = 'S'; t.at(1) = 'W'; // assumption
        bool flag = check(N, s, t);
        if(flag){
            std::cout << t << std::endl;
            return 0;
        }
    }
    {
        std::string t(N, ' ');
        t.at(0) = 'W'; t.at(1) = 'S'; // assumption
        bool flag = check(N, s, t);
        if(flag){
            std::cout << t << std::endl;
            return 0;
        }
    }
    {
        std::string t(N, ' ');
        t.at(0) = 'W'; t.at(1) = 'W'; // assumption
        bool flag = check(N, s, t);
        if(flag){
            std::cout << t << std::endl;
            return 0;
        }
    }
    
    std::cout << -1 << std::endl;
    
    
}


Measured memory_bytes: 512
N = int(input())
A = [int(x) for x in input().split()]
 
s_sum = sum(A)
 
ans = [None] * N
 
ans[0] = s_sum
for i in range(1, N, 2):
  ans[0] -= 2 * A[i]
 
for i in range(N-1):
  ans[i + 1] = 2 * A[i] - ans[i]
 
print(*ans)

Measured memory_bytes: 20704
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int M = sc.nextInt();
		int N = sc.nextInt();
		String A[] = new String[M];
		String B[] = new String[N];
		for (int i = 0; i < M; i++) {
			A[i] = sc.next();
		}
		for (int i = 0; i < N; i++) {
			B[i] = sc.next();
		}
		for (int i = 0; i < M - N + 1; i++) {
			for (int k = 0; k < M - N + 1; k++) {
				boolean b = Main.check(A, B, i, k, N);
				if (b == true) {
					System.out.println("Yes");
					return;
				}
			}
		}
		System.out.println("No");
		return;
	}

	public static boolean check(String A[], String B[], int startline, int startposition, int N) {
		for (int i=0;i<N;i++ ) {
			for (int j =0;j<N;j++) {
				if (A[i+startline].charAt(startposition+j)!=B[i].charAt(j)) {
					return false;
				}
			}
		}
		return true;
	}
}

Measured memory_bytes: 35768
#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < n; ++i)
#define sz(x) int(x.size())
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())
#define FORV(i, v) for (auto i = v.begin(); i != v.end(); i++)
using namespace std;

using ll = long long;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = 1001001001;
const long long INFLL = LLONG_MAX / 3;
const double eps = (1e-9);


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

  ll n, k, s; cin >> n >> k >> s;
  ll v = s < 1e9 ? 1e9 : 1;
  vector<ll> ans(n, v);
  rep(i, k) ans[i] = s;

  rep(i, n) printf("%d%c", ans[i], i == n-1 ? '\n' : ' ');

  return 0;
}


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


void solve(long long X){
    long long y = 0;
    for(int i = 0; ; i++){
        y += i;
        if(y >= X){
            cout << i << endl;
            return;
        }
    }
    return;
}

int main(){
    long long X;
    scanf("%lld",&X);
    solve(X);
    return 0;
}


Measured memory_bytes: 3668
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int mod = 1e9+7;
const int maxn = 2e5+5;
int main() {
	int n;
	cin>>n;
	if(n<30) cout<<"No\n";
	else cout<<"Yes\n"; 
    return 0;
}



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

int main(void) {
    bool ans = true;
    int a,b;
    cin >> a >> b;
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '-') {
            if (i == a) continue;
            ans = false;
        } else {
            if (i != a) continue;
            ans = false;
        }
    }
    cout << (ans? "Yes" : "No") << endl;
    return 0;
}


Measured memory_bytes: 256
def c_average_length():
    N = int(input())
    Positions = [[int(i) for i in input().split()] for j in range(N)]

    ans = 0.0
    for i in range(N):
        for j in range(i + 1, N):
            ans += ((Positions[i][0] - Positions[j][0])**2 +
                    (Positions[i][1] - Positions[j][1])**2)**0.5
    return ans * 2 / N

print(c_average_length())

Measured memory_bytes: 3188
from collections import defaultdict
from sys import stdin
def gen_bound(x,B):
	if x < 3: lb = 2
	else: lb = x - 1
	if x > B-2: ub = B-1
	else: ub = x + 1
	return lb,ub+1
def solve():
	count = defaultdict(int)
	ans = [0]*10
	L = map(lambda x:map(int,x.split()),stdin.readlines())
	H,W,N = L[0]
	for i in xrange(1,N+1):
		xlb,xub = gen_bound(L[i][0],H)
		ylb,yub = gen_bound(L[i][1],W)
		for x in xrange(xlb,xub):
			for y in xrange(ylb,yub):
				count[x+(y<<34)] += 1
	for v in count.itervalues():ans[v] += 1
	ans[0] = (H-2)*(W-2) - sum(ans[1:])
	for c in ans: print c
solve()

Measured memory_bytes: 113816
#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:16000000")
#define PI 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679
using namespace std;
const int inf=0x3f3f3f3f;
const long long inf2=0x3f3f3f3f3f3f3f3f;
const double eps=1e-6;
const int mod=1000000007;
vector<int> g[111111];
int l[111111],r[111111],id[111111];
bool ans=true;
void solve(int x,int par=-1){
	l[x]=-inf;r[x]=inf;
	if(id[x]!=-1)l[x]=r[x]=id[x];
	for(int i=0;i<g[x].size();i++){
		if(g[x][i]==par)continue;
		solve(g[x][i],x);
		if(l[g[x][i]]<-inf/2)continue;
		if(l[x]<-inf/2){
			l[x]=l[g[x][i]]-1;
			r[x]=r[g[x][i]]+1;
		}
		else{
		if(id[x]!=-1&&id[g[x][i]]!=-1&&id[x]%2==id[g[x][i]]%2){
			ans=false;
			return;
		}
		l[x]=max(l[x],l[g[x][i]]-1);
		r[x]=min(r[x],r[g[x][i]]+1);
		}
	}
	if(l[x]>r[x])ans=false;
}
void make(int x,int par=-1){
	if(x==1&&id[x]==-1)id[x]=l[x];
	for(int i=0;i<g[x].size();i++){
		if(g[x][i]==par)continue;
		if(id[g[x][i]]==-1){
			if(id[x]-1>=l[g[x][i]]&&id[x]-1<=r[g[x][i]])id[g[x][i]]=id[x]-1;
			else id[g[x][i]]=id[x]+1;
		}
		make(g[x][i],x);
	}
}
int main(){
	memset(id,-1,sizeof(id));
	int n;
	cin>>n;
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	int k;
	cin>>k;
	while(k--){
		int a,b;
		cin>>a>>b;
		id[a]=b;
	}
	solve(1);
	if(!ans){
		puts("No");
	}
	else{
		puts("Yes");
		make(1);
		for(int i=1;i<=n;i++)cout<<id[i]<<endl;
	}
	return 0;
}

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

namespace CSharpSample01
{


    class Program
    {

        

        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            double[] a = Console.ReadLine().Split(' ').Select(x => double.Parse(x)).ToArray();

            double sum = 0;

            for(int i = 0; i < n; i++)
            {
                sum += 1 / a[i];
            }

            Console.WriteLine(1 / sum);
        }
    }
}

Measured memory_bytes: 11348
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

struct node{
  int key;
  struct node *back,*forward;
};

typedef struct node *NodePointer;

void insert(int);
NodePointer make(int);
NodePointer find(int);
void deleteFirst();
void deleteLast();
void deletel(int);

NodePointer head, tail;

void insert(int num){
  NodePointer newnode = make(num);
  newnode->back = head;
  newnode->forward = head->forward;
  head->forward->back = newnode;
  head->forward = newnode;
}
NodePointer make(int key){
  NodePointer newnode = (NodePointer)malloc(sizeof(struct node));
  newnode->key = key;
  return newnode;
}
NodePointer find(int key){
  for(NodePointer i = head->forward; i != tail; i = i->forward){
    if(i->key == key)return i;
  }
  return NULL;
}
void deleteFirst(){
  NodePointer del = head->forward;
  head->forward = del->forward;
  del->forward->back = head;
  free(del);
}
void deleteLast(){
  NodePointer del = tail->back;
  tail->back = del->back;
  del->back->forward = tail;
  free(del);
}
void deletel(int num){
  NodePointer del = find(num);
  if(del==NULL)return;
  del->forward->back = del->back;
  del->back->forward = del->forward;
  free(del);
}
void showl(){
  for(NodePointer i = head->forward;i != tail->back; i = i->forward){
    printf("%d ",i->key);
  }
  printf("%d\n",tail->back->key);
}
int main(){
  head = make(-100);
  tail = make(-100);
  head->forward=tail;
  tail->back=head;
  
  int n,num;
  string command;
  cin>>n;
  for(int i=0;i<n;i++){
    
    cin>>command;
    if(command[0]=='d'&&command[6]=='F'){
      deleteFirst();
    }
    else if(command[0]=='d'&&command[6]=='L'){
      deleteLast();
    }
    else if(command[0]=='i'){
      cin>>num;
      insert(num);
    }
    else if(command[0]=='d'){
      cin>>num;
      deletel(num);
    }
  }
  showl();
  return 0;
}



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


int main() {
	
	int N, i;
	cin>>N;
	
	string S;
	cin>> S;
  
    map<char,long long> S_Num; 
  
    for(i = 0; i < N; i++){
      
      S_Num[S.at(i)]++;
    }

  int64_t Sum = S_Num['R'] * S_Num['G'] * S_Num['B'];
  
  for (i = 0; i < N; i++){
    for(int j = 0; true; j++){
      
      int x = i - j;
      int y = i + j;
      if (x < 0 || y >= N) break;
      if (S.at(x) != S.at(i) && S.at(x) != S.at(y) && S.at(y) != S.at(i)) Sum--;
    }
  }
  cout << Sum << endl;
}


/*
int main() {
	
	int N;
	cin>>N;
	
	string S;
	cin>>S;
	
	long long ans = 0;
	
	map<char,long long> mp;
	
	for(int i=0;i<N;i++)mp[S[i]]++;
	
	ans = mp['R']*mp['G']*mp['B'];
	
	for(int i=0;i<N;i++){
		for(int j=0;true;j++){
			int x = i-j;
			int y = i+j;
			if(x<0||y>=N)break;
			if(S[i]!=S[x]&&S[x]!=S[y]&&S[y]!=S[i])ans--;
		}
	}
	
	cout<<ans<<endl;
	
    return 0;
}*/



Measured memory_bytes: 3644
#include<stdio.h>
#include<math.h>
#include <string.h>
int main()
{
    int a,b,c;
    scanf("%d%d%d", &a,&b,&c);
    if(a+b+c >= 22)
    {
        printf("bust\n");
    }
    else
    {
        printf("win\n");
    }
  
     return 0;
}


Measured memory_bytes: 128
#include<cstdio>
#include<algorithm>
#include<functional>
using namespace std;
int main(void)
{
	int p,j,i,MIN,MIN1;
	MIN=3000;
	MIN1=3000;
	for(i=1;i<=3;i++){
		scanf("%d",&p);
		MIN=min(MIN,p);
	}
	for(i=1;i<=2;i++){
		scanf("%d",&j);
		MIN1=min(MIN1,j);
	}
	printf("%d\n",MIN1+MIN-50);
	return 0;
}


Measured memory_bytes: 2732
H = int(input())
W = int(input())
N = int(input())

H = H
W = W
count = 0
paint = 0
while paint<N:
  if W>H:
    count +=1
    paint += W
    H-=1
  else:
    count +=1
    paint += H
    W -=1
else:
  print(count)


Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

const int MAXN = 101024; // 300 * 300
pair<int,int> hw[MAXN];
int cost[MAXN];

int main() {
    int h,w,d; cin>>h>>w>>d;
    for(int i = 0; i < h; ++i) {
        for(int j = 0; j < w; ++j) {
            int a; cin>>a;
            hw[a] = pair<int,int>(i,j);
        }
    }

    fill(cost, cost + MAXN, 0);
    for(int i = 1; i <= h * w; ++i) {
        if(i <= d) {
            cost[i] = 0;
            continue;
        }
        cost[i] = cost[i - d] + abs(hw[i].first - hw[i - d].first) + abs(hw[i].second - hw[i - d].second);
    }

    int q; cin>>q;
    for(int i = 0; i < q; ++i) {
        int l,r; cin>>l>>r;
        cout << cost[r] - cost[l] << endl;
    }

    return 0;
}


Measured memory_bytes: 2176
#include<bits/stdc++.h>
using namespace std;
long long n,w,dp[100003],a,b;
int main(){
	cin>>n>>w;
	for(int i=0;i<n;i++){
		cin>>a>>b;
		for(int j=w-a;j>=0;j--)
			dp[j+a]=max(dp[j+a],dp[j]+b);
	}
	long long ans=0;
	for(int i=0;i<=w;i++)ans=max(ans,dp[i]);
	cout<<ans;
}


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

typedef long long ll;
int n;
ll x;
ll num[55], numP[55];

ll rec(int layer, ll i) {
	if (i == 0) return 0;
	ll mid = num[layer] / 2l;
	if (i == num[layer]) return numP[layer];
	if (i > mid) {
		return numP[layer-1] + rec(layer-1, i-mid-1) + 1l;
	} else if (i == mid) {
		return numP[layer-1];
	} else if (i < mid) {
		return rec(layer-1, i - 1);
	}
}

int main() {
	cin >> n >> x;
	num[0] = 1;
	numP[0] = 1;
	for (int i = 1; i <= 50; i++) {
		num[i] = 3l + 2l*num[i-1];
		numP[i] = 2l * numP[i-1] + 1;
	}
	ll ans = rec(n, x);
	cout << ans << endl;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	
	public static class StarrySkyTree{
		private static final long INF = Long.MAX_VALUE / 2 - 1;
		private static final long DEFAULT = 0; // 単位元

		int n; long[] min, add; // add[k]...範囲に足した値. min[k]...その時点での最小値

		public StarrySkyTree(int n_) {
			int n = 1;
			while(n < n_){ n *= 2;} this.n = n;
			min = new long[this.n * 2 - 1]; add = new long[this.n * 2 - 1];
			for(int i = 0; i < this.n * 2 - 1 ; i++){
				min[i] = INF; add[i] = DEFAULT;
			}
		}

		// [a, b) に v を足す
		public void add(long v, int a, int b){ add(v, a, b, 0, 0, this.n); }
		private void add(long v, int a, int b, int k, int l, int r){
			if(r <= a || b <= l){ return; }
			if(a <= l && r <= b) {
				add[k] += v;
			}else{
				add(v, a, b, k * 2 + 1, l, (l + r) / 2);
				add(v, a, b, k * 2 + 2, (l + r) / 2, r);
			}
			min[k] = (k >= (this.n - 1) ? DEFAULT : Math.min(min[k * 2 + 1], min[k * 2 + 2])) + add[k];
		}

		// [a, b) の範囲での最小値を求める
		public long get_min(long a, long b){ return get_min(a, b, 0, 0, this.n); }
		private long get_min(long a, long b, int k, int l, int r){
			if(r <= a || b <= l){ return INF; }
			if(a <= l && r <= b){ return min[k]; }

			final long left_min  = get_min(a, b, k * 2 + 1, l, (l + r) / 2);
			final long right_min = get_min(a, b, k * 2 + 2, (l + r) / 2, r);
			return Math.min(left_min, right_min) + add[k];
		}

		// [index] での値を求める
		public long get_value(int index){
			int k = index + this.n - 1;
			long value = add[k];
			while(k > 0){ k = (k - 1) / 2; value += add[k]; }
			return value;
		}
	}
	
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		final int n = sc.nextInt();
		final int q = sc.nextInt();
			
		StarrySkyTree tree = new StarrySkyTree(n);
		for(int i = 0; i < n; i++){
			tree.add(Integer.MAX_VALUE, i, i + 1);
		}
		
		for(int i = 0; i < q; i++){
			final int com = sc.nextInt();
			final int x = sc.nextInt();
			final int y = sc.nextInt();
			
			if(com == 0){
				tree.add(y - tree.get_value(x), x, x + 1);
			}else{
				System.out.println(tree.get_min(x, y + 1));
			}
		}
	}

	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() throws IOException {
			while (!hasNext()) {
				tok = new StringTokenizer(br.readLine());
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public void close() throws IOException {
			br.close();
		}
	}
}

Measured memory_bytes: 62740
#import functools
#import math

def gcd(a, b):
    if a<b:
        b,a = a,b        
    while b:
        a, b = b, a % b
    return a

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

w = list(map(int, input().split()))

a = []

for i in range(n):
    tmp = abs(w[i]-x)
    a.append(tmp)
    
ans = a[0]

for i in range(1, n):
    now = a[i]
    ans = gcd(ans, now)
    
print(ans)

#print(functools.reduce(math.gcd, a))

Measured memory_bytes: 14252
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <queue>
#include <iostream>
#include <string.h>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <cstdint>
#include <climits>
#include <unordered_set>
#include <sstream>

using namespace std;

#define ll long long int
#define pii pair<ll,ll>

int main(void)
{
    ll n,a,b,c,d;
    cin >> n >> a >> b >> c >> d;
    ll dist = abs(b - a);

    for(int i = 0;i < n;i++)
    {
        ll minOff = 0 - i * c;
        ll maxOff = 0 - i * d;
        ll t = n-1-i;
        ll lower = maxOff + t * c;
        ll upper = minOff + t * d;
        if(lower <= dist && upper >= dist)
        {
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
                 
#define ll long long int
#define ld long double
#define si(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define sld(x) scanf("%llf",&x)
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define Next ((pos+1)%2)
#define BiG(x,y) (g[x].pb(y),g[y].pb(x))
#define lsd(x) ((x)&(-x))

using namespace std;

const int i=1e5+3;

ll ans,n,temp;

int main(){

    sl(n);

    while(n--){
        sl(temp);
        ans+=log2(lsd(temp));
    }
    printf("%lld\n",ans);
    return 0;    
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define maxk 100005 
#define maxn 105
#define mod 1000000007
int main()
{
	int n,k;
	int a[maxn];
	int dp[2][maxk];
	scanf("%d%d",&n,&k);
	for(int i=1; i<=n; i++)
		scanf("%d",&a[i]);
	dp[0][k] = 1;
	for(int i=1; i<=n; i++)
	{
		int sum = 0;
		for(int j=k; j>=0; j--)
		{
			sum = (sum + dp[(i+1)&1][j]) % mod;
			if(j+a[i]+1<=k)
				sum = (sum + mod - dp[(i+1)&1][j+a[i]+1]) % mod;
			dp[i&1][j] = sum;
		}
	}
	printf("%d\n",dp[n&1][0]);
	return 0;	
}

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


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

  long long res=0;
  int right=0;
  int sum=0;
  for(int i=0;i<n;++i){
    while(right<n && (sum^a[right])==(sum+a[right])){
      sum+=a[right];
      ++right;
    }
    res+=right-i;
    if(i==right) ++right;
    else sum-=a[i];
  }

  cout << res << endl;
  return 0;
}


Measured memory_bytes: 4060
//abc136

#include "iostream"
#include <string>
#include <deque>
#include <algorithm>
using namespace std;

long long CalValue(int val)
{
	long long ret = 1;
	if (val < 2)
		return 0;
	for (int i = val; i > val-2; i--)
	{
		ret *= i;
	}

	return ret/2;
}

int main(void)
{
	int N;
	int i;
	deque <string> dequeS;
	string s;
	int pos1;
	int pos2;
	int count = 0;
	long long maxCount = 0;

	cin >> N;
	
	string *psArray = new string[N];

	for (i = 0; i < N; i++)
	{
		cin >> s;
		sort(s.begin(), s.end());
		psArray[i] = s;
	}

	sort(psArray, psArray + N);

	pos1 = 0;
	count = 1;
	for (i = 1; i < N; i++)
	{
		if (psArray[i] == psArray[pos1])
		{
			count++;
			if (i == (N - 1))
			{
				maxCount += CalValue(count);
			}
		}
		else
		{
			pos1 = i;
			maxCount += CalValue(count);
			count = 1;
		}
	}

	//for (i = 0; i < N; i++)
	//{
	//	cout << psArray[i]<<endl;
	//}

	cout << maxCount;
	delete[]psArray;
	return 0;
}






Measured memory_bytes: 5760
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define repr(i,j,n) for(int i=(j),i##_len=(n);i<i##_len;++i)
#define all(x) (x).begin(),(x).end()
using namespace std;

struct UnionFind
{
    vector<int> par;

    UnionFind(int n) : par(n)
    {
        rep(i, n) par[i] = i;
    }

    int root(int x)
    {
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y)
    {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return;
        par[rx] = ry;
    }

    int same(int x, int y)
    {
        return root(x) == root(y);
    }
};

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

    string s; cin >> s;
    long long k; cin >> k;
    char before = s[0];
    long long count = 1;
    vector<long long> v;
    repr(i, 1, s.size())
    {
        if (before != s[i])
        {
            before = s[i];
            v.push_back(count);
            count = 1;
        }
        else count++;
    }
    v.push_back(count);
    if (v.size() == 1)
    {
        cout << s.size() * k / 2 << endl;
        return 0;
    }
    long long sum = 0;
    rep(i, v.size())
    {
        sum += v[i] / 2;
    }
    sum *= k;
    if (s.front() == s.back() && v.front() % 2 && v.back() % 2)
    {
        sum -= (v.front() / 2 + v.back() / 2 - (v.front() + v.back()) / 2) * (k - 1);
    }
    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>
 
#define N 1000000
 
using namespace std;
 
int main(int argc, const char * argv[]) {
    // insert code here...
     
     
    /////////
    //write//
    /////////
     
    while(1){
        int a, d, n; cin >> a >> d >> n;
        if(a==0 && d== 0 && n==0)break;
        int arr[N];
        for(int i=0; i<N; i++){
            arr[i] = i;
        }
        int sqr_n = (int) sqrt(N)+1;
        for(int i=2; i<sqr_n; i++){
            if(arr[i]){
                for(int j=0; i*(j+2)<N; j++){
                    arr[i*(j+2)]=0;
                }
            }
        }
        int cnt = 1;
        for(int i=2; i<N; i++){
            if(arr[i]){
                if((arr[i]-a)%d==0 && (arr[i]-a)/d>=0){
                    if(cnt == n)cout << arr[i] << endl;
                    cnt++;
                }
            }
        }
    }
     
    return 0;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define REP(i, n) for (ll (i) = 0 ; (i) < (ll)(n) ; ++(i))
#define REPN(i, m, n) for (ll (i) = m ; (i) < (ll)(n) ; ++(i))
#define REP_REV(i, n) for (ll (i) = (ll)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (ll (i) = (ll)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

//#define INF (1e10)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
template<class T> void print(const T& x) { cout << x << endl; }
template<class T, class... A> void print(const T& first, const A& ... rest) { cout << first << " "; prll(rest...); }
struct PreMain { PreMain() { cin.tie(0); ios::sync_with_stdio(false); } } premain;

int main() {
	int N, Z, W;
	cin >> N >> Z >> W;

	vector<ll> A(N);

	REP(i, N) {
		cin >> A[i];
	}

	ll ans = 0;
	if (1 == N) {
		ans = (abs(A[0] - W));
	}
	else {
		ans = max(abs(A[N - 1] - W), abs(A[N - 2] - A[N - 1]));
	}
	print(ans);

	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
  int x, n;
  cin >> x >> n;
  vector<int> nums;
  for(int i=0; i<n; i++){
    int tmp;
    cin >> tmp;
    nums.push_back(tmp);
  }

  sort(nums.begin(), nums.end());

  auto iter = upper_bound(nums.begin(), nums.end(), x);
  int lo = x;
  
  int hi = x+1;
  for(auto t=iter; t!=nums.end() && *t==hi; t++){
    hi++;
  }

  if(iter != nums.begin()){
    for(auto t=iter-1; ; ){
      if(*t==lo){
        lo--;
        if(t!=nums.begin()){
          t--;
        }else{
          break;
        }
      }else{
        break;
      }
    }
  }

  if(x-lo > hi-x){
    cout << hi << endl;
  }else{
    cout << lo << endl;
  }
  
  

  return 0;
}

Measured memory_bytes: 3572
#include<stdio.h>

int N,K,T[100005],i,j,t,r;
int main()
{
	for(;scanf("%d%d",&N,&K),N+K;)
	{
		for(i=0;i<N;i++)
			scanf("%d",&T[i]);
		for(i=t=0;i<K;i++)t+=T[i];
		for(i=K,r=t;i<N;i++)
		{
			t=t-T[i-K]+T[i];
			r=r>t?r:t;
		}
		printf("%d\n",r);
	}
	return 0;
}

Measured memory_bytes: 984
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 1 << 100
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res


n, k = LI()
A = IR(n)
A = [a - k for a in A]
A = [0] + list(accumulate(A))
D = {}
for i, v in enumerate(sorted(set(A))):
    D[v] = i

for i in range(n + 1):
    A[i] = D[A[i]]

bit = BIT(max(A) + 1)
c = 0
for a in A:
    c += bit.sum(a)
    bit.add(a, 1)


print(c)



Measured memory_bytes: 82888
function Main(input){
  var N = input.split("\n")[0];
  var A = input.split("\n")[1].split(" ");
  var B = input.split("\n")[2].split(" ");
  var C = input.split("\n")[3].split(" ");
  N = parseInt(N,10);

  for(i=0;i<=(N-1);i++){
    A[i] = parseInt(A[i],10);
    B[i] = parseInt(B[i],10);
  }
  for(i=0;i<=(N-2);i++){
    C[i] = parseInt(C[i],10);
  }

  var sati = 0;
  var jud;
  for(i=0;i<=(N-1);i++){
    jud = A[i] + 1 === A[i+1];
    if(jud===false){
      sati += B[(A[i]-1)];
    }else{
      if(i===(N-1)){
        sati += B[(A[i]-1)];
      }else{
      sati += (B[(A[i]-1)] + C[(A[i]-1)]);
      }
    }
  }
  console.log(sati);
}  

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21064
#include<bits/stdc++.h>
 
using namespace std;
 
 
#define mod(cans) cans%10**9+7
#define cin_pl(x,y) for(int i=0;i<x;i++){cin>>y[i];}
#define debug(x) cout << "Debug" << x << "\n"
#define rep(i,n) for(int i=0;i<n;i++)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define prians(Answer) cout<<Answer<<"\n"
#define TF(X) X==1?cout<<"Yes\n":cout<<"No\n"
#define elcon else{continue;}
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<vector<int>> matrix;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
typedef greater<int> gi;
 
int main()
{
    int n ;cin>>n;
    vi a(n);
    rep(i,n) cin>>a[i];
    vi b(n);
    rep(i,n) b[i]=i+1;
    vpi p;
    rep(i,n) p.push_back(make_pair(a[i],b[i]));
    sort(all(p));
    rep(i,n) cout<<p[i].second<<" ";

}

Measured memory_bytes: 2548
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <stack>
#include <sstream>
#include <list>
 
using namespace std;
 
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define PB push_back
#define PF push_front
 
 
typedef long long int ll;
typedef pair<int, int> Pii;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<double, double> Pdd;
typedef pair<ll, ll> P;
typedef pair<P, ll> PP;
 
 
const ll mod = 1e9+7;
const ll INF = 2e9;
const double epsilon = 1e-7;
const double PI = 3.1415926535;
 
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
  
int main(){
  int n,k;
  cin>>n>>k;
  vector<int> h(n);
  rep(i,n) cin>>h[i];
  vector<int> dp(n+1);
  int x;
  
  for(int i=2;i<n+1;i++){
    x=dp[i-1]+abs(h[i-1]-h[i-2]);
    for(int j=2;j<k+1&&i-j-1>=0;j++){
      x=min(dp[i-j]+abs(h[i-1]-h[i-j-1]),x);
    }
    dp[i]=x;
  }
  
  cout<<dp[n]<<endl;
}
      
      
      
  
  
  
  
  

 

Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main()
{
    int x,y,w,z,q;
    x>=-100;
    y<=100;

    cin>>x>>y;
w=x+y;
z=x-y;
q=x*y;
if(w>=z&&w>=q){cout<<w<<endl;
}
else if(z>=w&&z>=q){cout<<z<<endl;
}
else if(q>=w&&q>=z){cout<<q<<endl;
}
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

int main(){
    int H, W; cin >> H >> W;
    int N; cin >> N;

    vector<int> a(N+1);
    for(int i=1; i<=N; i++) cin >> a[i];

    int ans[H][W];
    int id = 1;

    for(int i=0; i<H; ++i) {
        if(i%2 == 0){
            for(int j=0; j<W; ++j){
                ans[i][j] = id;
                a[id]--;
                if(a[id] == 0) id++;
            }
        } else {
            for(int j=W-1; j>=0; --j){
                ans[i][j] = id;
                a[id]--;
                if(a[id] == 0) id++;
            }
        }
    }

    for(int i=0; i<H; ++i){
        for(int j=0; j<W; ++j){
            if(j) cout << " ";
            cout << ans[i][j];
        }
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <utility>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <math.h>
#include <string>
#define ll long long
#define ull unsigned long long
#define make(type,x) type x; cin>>x
#define make2(type,x,y) type x,y; cin>>x>>y
#define fr(x,y) for(long long x=0;x<y;x++)
#define makevec(x,y,n) vector <x> y(n); for(ll i=0;i<n;i++) cin>>y[i]
#define M (ll)1000000007
#define MM (ll) 1e8
#define INF (ll) 1e18
# define IOS ios_base::sync_with_stdio(false); cin.tie(NULL)

using namespace std;

template <typename T>
T modpow(T base, T exp, T modulus) {
  base %= modulus;
  T result = 1;
  while (exp > 0) {
    if (exp & 1) result = (result * base) % modulus;
    base = (base * base) % modulus;
    exp >>= 1;
  }
  return result;
}
bool sortbysec(const pair <ll,ll> &a,const pair <ll,ll> &b){
    return a.second<b.second;
}

struct cmp {
	bool operator() (const pair<int, int> &a, const pair<int, int> &b) const {
		int lena = a.second - a.first + 1;
		int lenb = b.second - b.first + 1;
		if (lena == lenb) return a.first < b.first;
		return lena > lenb;
	}
};

ll calcpow(ll x, ll y)
{
    ll temp;
    if(y == 0)
        return 1;
    temp = calcpow(x, y / 2);
    if (y % 2 == 0)
        return temp * temp;
    else
    {
        if(y > 0)
            return x * temp * temp;
        else
            return (temp * temp) / x;
    }
}
ll gcd(ll a, ll b){
    if(b==0) return a;
    return gcd(b,a%b);

}
ll egcd(ll a, ll b, ll &x,ll &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll x1;
    ll y1;
    ll g=egcd(b,a%b,x1,y1);
    x=y1;
    y=x1-y1*(a/b);
    return g;
}


bool isprime(ll a){
bool flag=1;
for(ll i=2;i*i<=a;i++){
    if(a%i==0) {flag=0; break;}
}
return flag;
}



int main(){
    IOS;
    make(ll,a);
    make(ll,b);
    make(char,c);
    make(ll,d);
    b*=100;
    b+=d;
    a*=b;
    cout<<a/100<<endl;

    return 0;
}


Measured memory_bytes: 3684
'use strict'
 
function main(s) {
 
  s = s.split('\n').map(x => Number(x));
  const a = s[0];
  const b = s[1];
  const h = s[2];
 
  const area = ((a + b) * h) / 2
  console.log(area);
}
 
main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21064
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
//constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;
constexpr int MOD = 1'000'000'007;

template<class T> inline T sqr(T x) {return x*x;}

void solve() {
    int n,W;
    cin >> n >> W;
    VLL w(n), v(n);
    REP(i,0,n) cin >> w[i] >> v[i];
    VVLL dp(n, VLL(W+1));
    dp[0][w[0]] = v[0];
    REP(i,1,n) REP(j,0,W+1) {
        dp[i][j] = dp[i-1][j];
        if (j - w[i] >= 0) {
            dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);
        }
    }
    LL ans = dp[n-1][0];
    REP(i,1,W+1) ans = max(ans, dp[n-1][i]);
    cout << ans << endl;
}

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

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

int main(){
 int n,m;
 cin >> n >> m;
 vector<int> a(n);
 for (int i=0;i<n;i++) cin >> a[i];
 int s=0;
 for (int i=0;i<n;i++) s+=a[i];
 int cnt = 0;
 for (int i=0;i<n;i++){
   if (a[i]*4*m >= s) cnt++;
 }
  if (cnt >= m) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

ll dp[105][2][5];

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

  dp[0][1][0] = 1;

  rep(i,N.size()){
    rep(j,2){
      rep(k,K+1){
        if(dp[i][j][k] == -1) continue;

        if(j==0){
          rep(x,10){
            dp[i+1][0][k+(x!=0?1:0)] += dp[i][j][k];
          }
        }else{
          rep(x,(N[i]-'0')+1){
            dp[i+1][x==(N[i]-'0')][k+(x!=0?1:0)] += dp[i][j][k];
          }
        }
      }
    }
  }

  cout << dp[N.size()][0][K] + dp[N.size()][1][K] << endl;
  
  return 0;
}



Measured memory_bytes: 3612
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int C[100010];
int N, M;

int main() {

    cin >> N >> M;
    int L, R;
    for (int i = 0; i < M; i++) {
        cin >> L >> R;
        C[L]++;
        C[R+1]--;
    }

    for (int i = 1; i <= N+1; i++) {
        C[i] += C[i-1];
    }
 
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        if (C[i] == M)
            ans++;
    }
    cout << ans << '\n';
}


Measured memory_bytes: 640
from sys import stdin
# import sys

# A, B, C = [int(x) for x in stdin.readline().rstrip().split()]
# A,B = [int(x) for x in stdin.readline().rstrip().split()]
# U = input().split()
# A, B = [str(x) for x in stdin.readline().rstrip().split()]

import math

K = int(input())
ans = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        d = math.gcd(a, b)
        for c in range(1, K+1):
            ans += math.gcd(d, c)
print(ans)


Measured memory_bytes: 9176