akhauriyash/Code-Regression huggingface dataset:
#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<int, int> P;

const ll INF = 1LL << 60;

ll N, K;
vector<ll> A, F;

int main() {
    cin >> N >> K;
    A.resize(N);
    F.resize(N);

    rep(i, N) cin >> A[i];
    rep(i, N) cin >> F[i];

    sort(A.begin(), A.end());
    sort(F.rbegin(), F.rend());


    ll left = -1, right = INF;

    while (right - left > 1) {
        ll middle = (left + right) / 2;

        bool ok = [&] {
            // 必要なcost
            ll s = 0; 
            for (int i = 0; i < N; i++) {
                s += max(0LL, A[i] - middle / F[i]);
            }
            return s <= K;
        }();

        if (ok) {
            right = middle;
        } else {
            left = middle;
        }
    }

    cout << right << endl;
}

Measured memory_bytes: 6412
#include <cstdio>
#include <algorithm>
#include <set>

typedef long long LL;
const int MN = 200005;

int N, faz[MN], c0[MN], c1[MN], fa[MN]; LL Ans;
int ff(int x) { return fa[x] ? fa[x] = ff(fa[x]) : x; }
struct D {
	int id;
	D(int i = 0) : id(i) {}
	friend bool operator < (D a, D b) {
		LL lhs = (LL)c1[a.id] * c0[b.id], rhs = (LL)c1[b.id] * c0[a.id];
		return lhs == rhs ? a.id < b.id : lhs < rhs;
	}
};
std::set<D> st;

int main() {
	scanf("%d", &N);
	for (int i = 2; i <= N; ++i) scanf("%d", &faz[i]);
	for (int i = 1, x; i <= N; ++i) scanf("%d", &x), (x ? c1 : c0)[i] = 1;
	for (int i = 2; i <= N; ++i) st.insert(i);
	while (!st.empty()) {
		int u = st.begin()->id, v = ff(faz[u]);
		st.erase(u);
		if (v > 1) st.erase(v);
		Ans += (LL)c1[v] * c0[u];
		c1[v] += c1[u], c0[v] += c0[u];
		fa[u] = v;
		if (v > 1) st.insert(v);
	}
	printf("%lld\n", Ans);
	return 0;
}

Measured memory_bytes: 13696
def c(n, x):
  if n==0:
    return 1
  s=0
  if x==1:
    return 0
  elif 1<x<=1+l[n-1]:
    return c(n-1,x-1)
  elif x==2+l[n-1]:
    return c(n-1,x-1)+1
  else:
    return p[n-1]+1+c(n-1,x-l[n-1]-2)

N, X = map(int, raw_input().split())
l = [0]*(N+1)
l[0]=1
p = [0]*(N+1)
p[0]=1
for i in range(1, N+1):
  l[i] = 2*l[i-1]+3
  p[i] = 2*p[i-1]+1
a = c(N,X)
print a

Measured memory_bytes: 2696
import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
    n = int(input())
    h = list(map(int, input().split()))
    arr = [h[0]] + [0] * (n - 1)
    ans = 0
    for i in range(1, n):
        arr[i] = h[i] - h[i-1]
    for i in range(n):
        if arr[i] > 0:
            ans += arr[i]
    print(ans)
        
if __name__ == '__main__':
    main()

Measured memory_bytes: 9136
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    ll n;
    cin >> n;
    vector<ld> a(n+1);
    for(int i = 1 ; i <= n; i++)    cin >> a[i];
    vector<vector<ld>> dp(n+1 , vector<ld>(n+1,0));

    dp[0][0] = 1.0;
	for (int i = 1; i <= n; i++) 
		dp[i][0] = dp[i-1][0]*(1-a[i]);

    for(int i = 1 ; i <= n; i++)
        for(int j = 1 ; j <= i; j++)
            dp[i][j] = dp[i-1][j-1]*a[i] + dp[i-1][j]*(1-a[i]);
    
    long double ans = 0.0;
    for (int i = n/2 + 1; i <= n; i++)
        ans += dp[n][i];
    cout << setprecision(10) << ans << endl;
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
using P = pair<ll, ll>;
using V = vector<ll>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i, n) for(ll i=1;i<=(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define INF 1000000000

void solve_abc154() {
	string s;
	ll ans = 0;

	cin >> s;

	string ans2 = "";
	rep(i, s.size()) {
		ans2 += "x";
	}

	cout << ans2 << "\n";
}

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

	solve_abc154();

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int main(void){
    string s;
    cin >> s;
    queue<char> ans;
    for(int i=0; i<s.length(); i+=2){
        ans.push(s[i]);
    }
    while(!ans.empty()){
        cout << ans.front();
        ans.pop();
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 512
import itertools

N = int(input())
s1 = tuple(map(int,input().split()))
s2 = tuple(map(int,input().split()))

l = list(range(1,N+1))

l_ = list(itertools.permutations(l,N))

dic = {}
num = 0
for item in l_:
  dic[item] = num
  num += 1

print(abs(dic[s1]-dic[s2]))

Measured memory_bytes: 48496
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;
LL solve(int L, int R, auto &dp, auto &arr, auto &preS) {
    if (~dp[L][R]) return dp[L][R];
    if (L == R) return dp[L][R] = 0;
    return dp[L][R] = max(
        preS[R] - preS[L + 1] - solve(L + 1, R, dp, arr, preS) + arr[L],
        preS[R - 1] - preS[L] - solve(L, R - 1, dp, arr, preS) + arr[R - 1]
    );
}
void marmot0814() {
    int n; cin >> n;
    vector<LL> arr(n);
    vector<LL> preS{0};
    for (auto &v : arr)
        cin >> v, preS.push_back(preS.back() + v);
    vector<vector<LL>> dp(n + 1, vector<LL>(n + 1, -1));
    cout << solve(0, n, dp, arr, preS) - (preS.back() - solve(0, n, dp, arr, preS)) << '\n';
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1, kase = 0; // cin >> t;
    while (t--) {
        // cout << "Case #" << ++kase << ":";
        marmot0814();
    }
}

Measured memory_bytes: 74220
V, E = map(int, input().split())
graph = [[10**18]*V for _ in range(V)]

for i in range(V):
    graph[i][i] = 0

for _ in range(E):
    s, t, d = map(int, input().split())
    graph[s][t] = d

for v in range(V):
    for i in range(V):
        for j in range(V):
            graph[i][j] = min(graph[i][j], graph[i][v]+graph[v][j])

ans = True
for i in range(V):
    if graph[i][i]<0:
        ans = False
        break

if ans:
    for g in graph:
        g = [i if not i>10**17 else 'INF' for i in g]
        print(*g)
else:
    print('NEGATIVE CYCLE')




Measured memory_bytes: 6436
#include <iostream>
#include <vector>
//#include<bits/stdc++.h>
#include <algorithm>
using namespace std;
/*
class Hoge{
  public:
    int m_hoge;
  Shop(int hoge){
    m_hoge = hoge;
  }
  bool operator<(const Hoge &another) const
  {
    return hoge < another.hoge;
  };
};
*/
int main(){
  int N,ans = 0,max;
  vector<int> H;
  cin >> N;
  for(int i=0;i<N;i++){
    int temp;
    cin >> temp;
    H.push_back(temp);
  }
  max = H[0];
  for(int i=0;i<N;i++){
    if(H[i]>=max){
      max = H[i];
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rep1(i, n) for(int i=1; i<=n; i++)
#define repr(i, n) for(int i=n-1; i>=0; i--)
#define repr1(i, n) for(int i=n; i>=1; i--)
#define all(v) v.begin(),v.end()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int MAX = 100010;
int x, y, a, b, c;

int main() {
    cin >> x >> y >> a >> b >> c;
    vector<ll> p(a), q(b), r(c);
    rep(i, a) cin >> p[i];
    rep(i, b) cin >> q[i];
    rep(i, c) cin >> r[i];

    sort(all(p), greater<ll>());
    sort(all(q), greater<ll>());
    sort(all(r), greater<ll>());

    priority_queue<ll, vector<ll>, greater<ll>> pq;
    rep(i, x) pq.push(p[i]);
    rep(i, y) pq.push(q[i]);

    rep(i, c) {
        ll top = pq.top();
        if (top < r[i]) {
            pq.pop();
            pq.push(r[i]);
        }
    }

    ll ans = 0;
    rep(i, x+y) {
        ans += pq.top();
        pq.pop();
    }
    cout << ans << endl;
}


Measured memory_bytes: 4724
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<P> Graph;

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

  string s,t,r;
  cin >> s >> t >> r;
  
  char c[3];
  
  c[0] = s[0]-32;
  c[1] = t[0]-32;
  c[2] = r[0]-32;
  
  cout << c[0] << c[1] << c[2] << endl;

  return 0;
}

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

int main() {
    //<Code>
    int n, h;
    h = 0;
    cin >> n;
    while (n != 0) {
        if (n%500 == 0) {
            h += 1000;
            n -= 500;
        } else if (n%5 == 0) {
            h += 5;
            n -= 5;
        } else {
            n -= n%5;
        }
    }
    cout << h << endl;
    return 0;
}


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

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

  vector<int> a(n);
  rep(i,n) cin >> a[i];

  int pre = -999;

  rep(i,n) {
    // 数を小さくできるときは小さくする
    if (pre <= a[i]-1) {
      pre = a[i] - 1;
    } else if (pre <= a[i]) {
      pre = a[i];
    } else { // 無理な場合があればその時点で"No"を出力
      puts("No");
      return 0;
    }
  }
  puts("Yes");

  return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define sci(a) scanf("%d", &a)
#define fto(i, a, b) for (int i = a; i <= b; ++i)
#define fdto(i, a, b) for (int i = a; i >= b; --i)
#define scii(a, b) scanf("%d %d", &a, &b)
#define ll long long
#define ff first
#define ss second
#define vi vector<int>
#define pi pair<int, int>
#define maxN 100005
#define oo 1000000007
#define mp make_pair
#define pb push_back
#define bug(a) cout << #a << "= " << a << endl;
#define bugarr(a, x, y) cout << #a << "[" << x << ", " << y << "]= "; for (int i = x; i <= y; ++i) cout << a[i] << ", "; cout << endl;
#define sz(a) (int)a.size()
#define vii vector<pi>
#define db double
#define forit(var, it) for(__typeof(var.begin()) it = var.begin(); it != var.end(); ++it)

using namespace std;

pair<pi, int> a[maxN], b[maxN];
int n, m, p[maxN];

int _find(int i) {
    if (i == p[i]) return i;
    return p[i] = _find(p[i]);
}

int main() {
   // #ifndef ONLINE_JUDGE
        //freopen("Built.inp", "r", stdin);
        //freopen("Built.out", "w", stdout);
    //#endif // ONLINE_JUDGE

    sci(n);
    fto(i, 1, n) scii(a[i].ff.ff, a[i].ff.ss);
    fto(i, 1, n) {
        a[i].ss = i;
        b[i] = mp(mp(a[i].ff.ss, a[i].ff.ff), a[i].ss);
    }
    sort(a+1, a+1+n);
    sort(b+1, b+1+n);
    vector<pair<int, pi> > canh;
    fto(i, 1, n-1) {
        int u = a[i].ss, v = a[i+1].ss, w = a[i+1].ff.ff - a[i].ff.ff;
        canh.pb(mp(w, mp(u, v)));
    }
    fto(i, 1, n-1) {
        int u = b[i].ss, v = b[i+1].ss, w = b[i+1].ff.ff - b[i].ff.ff;
        canh.pb(mp(w, mp(u, v)));
    }
    sort(canh.begin(), canh.end());
    ll ans = 0;
    fto(i, 1, n) p[i] = i;
    fto(i, 0, (int)canh.size()-1) {
        int u = canh[i].ss.ff, v = canh[i].ss.ss;
        int cutou = _find(u), cutov = _find(v);
        if (cutou != cutov) {
            ans+=canh[i].ff;
            p[cutou] = cutov;
        }
    }
    cout << ans;

    return 0;
}


Measured memory_bytes: 7284
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <utility>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define INF 1000000001
#define mod 1000000007
using namespace std;

int main(){
	//cin.tie(0);
	//ios::sync_with_stdio(false);
	string s,t;
	cin>>s>>t;
	int ss,st;
	ss=s.size();
	st=t.size();
	rrep(i,ss-st+1){
		int check=0;
		rep(j,st){
			if(s[i+j]==t[j] || s[i+j]=='?'){
			}else{
				check=1;
				break;
			}
		}
		if(check==0){
			rep(k,i){
				if(s[k]=='?') printf("a");
				else printf("%c",s[k]);
			}
			cout<<t;
			FOR(k,i+st,ss){
				if(s[k]=='?') printf("a");
				else printf("%c",s[k]);
			}
			printf("\n");
			return 0;
		}
	}
	cout<<"UNRESTORABLE"<<endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using static System.Console;
using static System.Convert;
using static System.Math;

class Program
{
    class o
    {
        public int index;
        public int ye;
        public int city;
        public string number;

        public void GetN(string i)
        {
            var ind = city.ToString();
            var ze = "";
            for (var j = 0; j < 6 - ind.Length; j++) ze += "0";
            ze += ind;
            for (var j = 0; j < 6-i.Length; j++) ze += "0";
            ze += i;
            number = ze;
        }
    }

    static void Main(string[] args)
    {
        var input = ReadLine().Split(' ');
        var num = ToInt32(input[0]);
        var cit = ToInt32(input[1]);
        var os = new List<o>();
        for(var i = 0; i < cit; i++)
        {
            var inp = ReadLine().Split(' ');
            var s = new o();
            s.index = i;
            s.city = ToInt32(inp[0]);
            s.ye = ToInt32(inp[1]);
            os.Add(s);
        }
        os.Sort((a,b) => a.ye-b.ye);
        var dic = new Dictionary<int, int>();
        for(var i = 0; i < cit; i++)
        {
            var c = os[i].city;
            if (dic.ContainsKey(c))
            {
                os[i].GetN(dic[c].ToString());
                dic[c]++;
            }
            else
            {
                os[i].GetN("1");
                dic[c] = 2;
            }
        }
        os.Sort((a, b) => a.index - b.index);
        foreach(var n in os)
        {
            WriteLine(n.number);
        }
    }
}


Measured memory_bytes: 37824
#121-B
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
import numpy as np
n,m,c=IL()
b=np.array(IL())
ans=0
for i in range(n):
    a=np.array(IL())
    if np.sum(a*b)+c>0:
        ans+=1
print(ans)

Measured memory_bytes: 14432
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a=0,b,c,d;
  string s;
  cin >>s;
  for(int n=0;n<3;n++){
    if(s[n]=='o') a++;
  }
  cout  <<700+a*100<<'\n';
  return (0);
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <utility>
#include <algorithm>
#include <numeric>
#include <typeinfo>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <ctime>

using namespace std;

#define dump(n) cout<<"# "<<#n<<"="<<(n)<<endl
#define debug(n) cout<<__FILE__<<","<<__LINE__<<": #"<<#n<<"="<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,n) repi(i,0,n)
#define iter(c) __typeof((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();i++)
#define allof(c) (c).begin(),(c).end()
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int,int> pii;

int solve(vvi& field,int i,int j)
{
	int h=field.size(),w=field[0].size();
	if(i<0 || h<=i || j<0 || w<=j || field[i][j]!=1)
		return 0;
	field[i][j]=0;
	int di[]={-1,1,0,0};
	int dj[]={0,0,-1,1};
	int res=0;
	rep(k,4)
		res=max(res,solve(field,i+di[k],j+dj[k])+1);
	field[i][j]=1;
	return res;
}

int main()
{
	for(int w,h;cin>>w>>h,w|h;){
		vvi field(h,vi(w));
		rep(i,h) rep(j,w)
			cin>>field[i][j];
		
		int res=0;
		rep(i,h) rep(j,w)
			if(field[i][j]==1)
				res=max(res,solve(field,i,j));
		cout<<res<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 0
N, K = map(int, input().split())

sum = 0

for i in range(N) : 
    n = i+1
    cnt = 0
    flag = 1
    if n >= K : flag = 0
    
    while(flag == 1) : 
        cnt += 1
        nn = n * (2 ** cnt)
        if(nn >= K) : 
            flag = 0
    
    sum += (1/2) ** cnt
sum = sum * (1/N)

print(sum)
        

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

int a[3], b[3];
int c[3][3];

int main() {
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> c[i][j];
		}
	}

	for (int i = 0; i < 3; i++) {
		b[i] = c[0][i];
	}
	a[1] = c[1][0] - b[0];
	a[2] = c[2][0] - b[0];

	bool ans = true;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			ans = (c[i][j] == a[i] + b[j]);
			if (!ans) break;
		}
		if (!ans) break;
	}

	if (ans) cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std;
using ll = long long;
template<typename T> using v2 = vector<vector<T>>;
template<typename T> inline v2<T> init(int r, int c, const T& t){ return v2<T>(r, vector<T>(c, t)); }
#define F first
#define S second

int n, m;
vector<int> a;

ll lcm(int a, int b){
    return (ll)a*b/__gcd(a, b);
}

bool test(ll lowest){
    for(int i = 0; i < n; ++i){
        if(lowest%a[i] == 0) return false;
    }
    return true;
}

void solve(){
    cin >> n >> m;
    a = vector<int>(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }

    ll lowest = a[0]/2;
    for(int i = 1; i < n; ++i){
        lowest = lcm(lowest, a[i]/2);
        if(lowest > m){
            cout << "0\n";
            return;
        }
    }

    if(!test(lowest)){
        cout << "0\n";
    }
    else{
        ll ans = 1 + (m - lowest)/(2LL*lowest);
        cout << ans << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Measured memory_bytes: 3728
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int s;
    cin >> s;
    int ret = 0;
    if(s/1000 == 2) ret++;
    if((s/100)%10 == 2) ret++;
    if((s/10)%10 == 2) ret++;
    if(s%10 == 2) ret++;
    cout << ret << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{
  char O[52], E[52];
  int i=0;
  scanf("%s", O); scanf("%s", E);

  while(O[i] != '\0'){
    printf("%c", O[i]);
    if(E[i] == '\0') break;
    printf("%c", E[i]);
    i++;
  }
  return 0;
}

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

int n,a[20];

long long dp(int l,int r,long long xl,long long xr) {
	if(l+1==r) return 0;
	long long ret=1e18;
	for(int i=l+1;i<r;i++) ret=min(ret,dp(l,i,xl,xl+xr)+dp(i,r,xl+xr,xr)+(xl+xr)*a[i]);
	return ret;
}

int main() {
	cin>>n;for(int i=1;i<=n;i++) cin>>a[i];
	cout<<dp(1,n,1,1)+a[1]+a[n];
	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int MaxN = 1e5;
long long cnt1[MaxN + 5],cnt2[MaxN + 5],a[MaxN + 5],b[MaxN + 5],c[MaxN + 5],n;
 
bool cmp1(long x, long  y){
	return x < y;
}
bool cmp(long long x, long long y){
	return x > y;
}
 
int main()
{
	scanf("%lld",&n);
	for(int i = 1; i <= n; i++)
		scanf("%lld",&a[i]);
	for(int i = 1; i <= n; i++)
		scanf("%lld",&b[i]);
	for(int i = 1; i <= n; i++)
		scanf("%lld",&c[i]);
	sort(a + 1, a + n + 1,cmp1);
	sort(b + 1, b + n + 1,cmp1);
	sort(c + 1, c + n + 1, cmp);
	long long p = 1;
	int ok = 1;
	for(long long  i = 1; i <= n; i++){
		if(p == n + 1){ 
			cnt1[i] = p - 1;
			continue;
		}
		ok = 1;
		while(ok && p <= n){
			if(a[p] < b[i]) p++;
			else ok = 0; 
		}
		cnt1[i] = p - 1;
	}
	p = 1, ok = 1;
	for(long long i = n; i >= 1; i--){
		if(p == n + 1){
			cnt2[i] = p - 1;
			continue;
		}
		ok = 1;
		while(ok && p <= n){
			if(c[p] > b[i]) p++;
			else ok = 0;
		}
		cnt2[i] = p - 1;
	}	
	long long sum = 0;
	for(long long i = 1; i <= n; i++){
		sum += cnt1[i] * cnt2[i];
	}
	printf("%lld\n",sum);
}

Measured memory_bytes: 4224
N = int(input())
S = [input() for _ in range(N)]

ac, wa, tle, re = 0, 0, 0, 0

for si in S:
    if si == "AC":
        ac += 1
    elif si == "WA":
        wa += 1
    elif si == "TLE":
        tle += 1
    else:
        re += 1

ans = "AC x {0}\nWA x {1}\nTLE x {2}\nRE x {3}".format(ac, wa, tle, re)

print(ans)

Measured memory_bytes: 16328
#include <iostream>
#include <vector>
#include <map>
typedef long long ll;
using namespace std;

int main() {
	ll n;
	cin >> n;
	vector<ll> a(n + 1);
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	map<ll, ll> l, r;
	for (int i = 1; i <= n; i++) {
		l[i + a[i]]++;
		r[i - a[i]]++;
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++)
		ans += l[i] * r[i];
	cout << ans << endl;
	return 0;
}

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

#define rep( i, n, m ) for(int i = ( n ); i < ( m ); i++)
#define rep_d( i, n, m ) for(int i = ( n ) - 1; i >= ( m ); i--)
#define sort_asc( X ) sort(( X ).begin(), ( X ).end())
#define sort_desc( X ) sort(( X ).begin(), ( X ).end(), greater <>())
#define endl "\n"

template <class T> bool chmax( T& a, T b );
template <class T> bool chmin( T& a, T b );
int* eratosthenes( int N );
bool bit_search( int pattern, int N );
void initialize( void );

const ll INF = 1LL << 60;
const int k_mod = 1e9 + 7;
template <typename T, typename K> struct P {
	T a; K b;
};
int main( void ){
	// initialize();
	int N;
	cin >> N;
	vector <ll> mp( N + 5, 0 ), input( N + 1 );
	rep( i, 0, N ){
		cin >> input[ i ];
		mp[ input[ i ] ]++;
	}
	ll sum_all = 0;
	rep( i, 0, N+2 ){
		sum_all += ( mp[ i ] * ( mp[ i ] - 1 ) / 2 );
	}
	rep( i, 0, N ){
		ll in = mp[ input[ i ] ];
		ll sum = sum_all - ( in * ( in - 1 ) / 2 );
		printf( "%lld\n", sum  + (( in - 1 ) * ( in - 2 ) / 2) );
	}
}

template <class T> bool chmax( T& a, T b ) {
	if (a < b){
		a = b; return true;
	}
	return false;
}
template <class T> bool chmin( T& a, T b ) {
	if (a > b){
		a = b; return true;
	}
	return false;
}
int* eratosthenes( int N ){
	int* prime_array = new int[ N + 1 ];
	int lim = N;
	prime_array[ 0 ] = 0;
	prime_array[ 1 ] = 0;
	rep( i, 2, N + 1 ){
		prime_array[ i ] = 1;
	}
	rep( i, 2, lim ){
		if (prime_array[ i ] == 0)
			continue;
		lim = N / i;
		for(int j = i * 2; j < N + 1; j += i){
			prime_array[ j ] = 0;
		}
	}
	return prime_array;
}
bool bit_search( int pattern, int N ){
	int cnt = 0;
	rep( bit, 0, N ){
		if (pattern & ( 1 << bit )){
			cnt++;
		}
	}
	return true;
}
void initialize( void ){
	cout << fixed << setprecision( 10 );
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
#include <math.h>
#include <cmath>

using namespace std;
using ll =long long;
using vi = vector<int>; 
using vvi = vector<vi>; 
using vl = vector<ll>; 
using vvl = vector<vl>; 
using vs = vector<string>;
using vvs = vector<vs>; 
using vc = vector<char>;
using vvc = vector<vc>; 
using vb = vector<bool>;
using vvb = vector<vb>; 

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const long long INF = 1LL << 60;

#define rep(i,n) ;for( int i =0; i < n ; i ++)
#define all(a) a.begin(),a.end()
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define fr(i,a,b) for(int i=a;i<b;i++)
#define pri(a)  printf("%.14lf\n",a);
#define MOD 1000000007
bool is_int_lround(double x){
  return std::lround(x)==x;
}
ll keta(ll x){
  ll n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}

ll conbi(int n,int m){
  
  cin>>n>>m;
  vector<ll> a(100);
  a[0] =1;
  for(int i=0;i<14;i++){
    a[i+1]=a[i]*(i+1);
  }
  return a[n] /(a[m] *a[n-m]);
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;//繰り返し二乗法
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
ll kaijo(ll x){
  ll z=1;
  if(x==0){
    return 1;
  }
  while(x>0){
    z *=x;
    z %=MOD;
    x--;
  }
  return z;
}
ll yakusu_num(ll n){
  vl yakusu(n+1,1);
  for(ll i=2;i*i<=n;i++){ 
    while(n%i==0){
      n /=i;
      yakusu[i]++;
    }
  }
  if(n!=1)yakusu[n]++;
  ll num=1;
  for(ll i=0;i <=n;i++){
    num*=yakusu[i];
  }
  return num;
}


//cout<<""<<endl;
int main(){
string S;cin>>S;
  ll ans =0;
  rep(i,S.size()){
    ans+=S[i]-'0';
  }
  if(ans%9==0)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  
}





Measured memory_bytes: 3748
#include <stdio.h>
int main(){
  int N,i,kousuu,cnt,j,n;
  while(1){
    cnt=0;
    scanf("%d",&N);
    if(N==0){
      break;
    }
    for(i=1;i<=N;i++){
      for(j=i;j<=N;j++){
        kousuu=j-i+1;
        n=kousuu;
        if(n>=2 && (i*n+j*n)/2 == N){
          cnt++;
	}
      }
    }
  printf("%d\n",cnt);
  }
  return 0;
}

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

int main(){
long long int N,count=0;
cin >>N; long long int M[N];
for(long long int i=0;i<N;i++){
cin >> M[i];
}
for(long long int i=0;i<N-2;i++){
  if(M[i]<M[i+1]&&M[i+1]<M[i+2])count++;
  if(M[i]>M[i+1]&&M[i+1]>M[i+2])count++;
}
cout <<count;

}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<string>
#include<map>
#define ll          long long
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define pll         pair<ll,ll>
#define vii         vector<pair<ll,ll> >
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (int)x.size()
#define hell        1000000007
#define endl        '\n'
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define rep1(i,a,b) for(ll i=a;i<= b;i++)
#define PI          3.14159
#define MAX         100000001
#define fast_io      ios_base::sync_with_stdio(false);  cin.tie(0); cout.tie(0);
#define scan(var)    scanf("%lld",&var)
#define print(var)   printf("%lld\n", var);
#define BLOCK 317
#define double       long double
#define mod          998244353
using namespace std;
ll arr[300001];
int main()
{
  fast_io
  ll n;
  cin >> n;
  cout << n*n*n;
  return 0;
}



Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 重りの入力
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
        int d = sc.nextInt();
		if(a+b > c+d){
		System.out.println("Left");
        }else if(a+b < c+d){
         System.out.println("Right");
        }else{
        System.out.println("Balanced");
        }
	}
}

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

using namespace std;
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
#define REP(i,n) for(ll i = 0;i < (ll)n;i++)
#define REPD(i,n) for(ll i = (ll)n - 1;i >= 0;i--)
#define ALL(x) (x).begin(),(x).end()
#define FILLl(n,first_dimension_size,value) fill((ll*)n,(ll*)(n+first_dimension_size),value)
#define FILL(n,first_dimension_size,value) fill((int*)n,(int*)(n+first_dimension_size),value)
#define INF (1 << 30)
#define MOD 1000000007
//int dy[4] = {-1,0,0,1};
//int dx[4] = {0,1,-1,0};


int main(){
  
  ll n,a,b,c,d,e;
  cin >> n >> a >> b >> c >> d >> e;
  ll minn = min({a,b,c,d,e});
  ll res = 4+(n+minn-1)/minn;
  cout << res << endl;
  




  return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int n,a,b,c;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a>>b>>c;
    if((a*a)+(b*b)==(c*c) || (a*a)+(c*c)==(b*b) || (c*c)+(b*b)==(a*a)) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
  }
  return 0;
}

Measured memory_bytes: 3012
n=int(input())

arr = []
temp = n
for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
        cnt=0
        while temp%i==0:
            cnt+=1
            temp //= i
        arr.append([i, cnt])

if temp!=1:
    arr.append([temp, 1])

if arr==[]:
    arr.append([n, 1])

if arr==[[1,1]]:
    print(0)

else:
    total=0
    for i in range(len(arr)):
        x=1
        s=0
        c=-1
        while s<=arr[i][1]:
            s+=x
            x+=1
            c+=1
        total+=c
    print(total)


Measured memory_bytes: 9492
#include <stdio.h>

int main(void)
{
	int a,b,c,d,e=0;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	if(c-a<=d&&c-a>=-d){
		e++;
	}else if(b-a<=d&&b-a>=-d&&c-b<=d&&c-b>=-d){
		e++;
	}
	if(e==1){
		printf("Yes");
	}else{
		printf("No");
	}
	return 0;
}

Measured memory_bytes: 128
#pragma GCC optimize ("Ofast")
#include"bits/stdc++.h"
using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;

struct _ { ios_base::Init i; _() { cin.sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10); } } ___;
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
    cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " : " << arg1 << "  ";
    __f(comma + 1, args...);
}

#define ll long long
#define pii pair<int,int>
#define oset tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ff first
#define ss second
#define endll '\n'
#define rep(i,n) for(int i=0;i++<n;)
#define scl(i) scanf("%lld",&i)
#define int long long int
#define all(n) n.begin(),n.end()
#define mem(n,i) memset(n,i,sizeof n)
#define em(a) emplace_back(a)
#define pb(a) push_back(a)
#define srep(it,vv) for(auto &it : vv)
#define prep(it,vv) for(auto it : vv)
//vector<vector<int>>arr(n + 5, vector<int>(m + 5,0));

typedef vector<int> vii;
typedef vector<string> vss;
/*

*/
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int n; cin >> n;
    map<string, int>mm;
    int xx = 0;
    rep(i, n)
    {
        string s; cin >> s;
        mm[s]++;
        xx = max(mm[s], xx);
    }
    vector<string>vv;
    for (auto it : mm)
    {
        if (it.ss == xx) vv.em(it.ff);
    }
    sort(all(vv));
    for (auto it : vv) cout << it << endll;
}

Measured memory_bytes: 27248
n,m,l = map(int,input().split())
matrixL = [[0]*m for i in range(n)]
matrixR = [[0]*l for i in range(m)]
for row in range(n):
    matrixL[row] = [int(i) for i in input().split()]

for row in range(m):
    matrixR[row] = [int(i) for i in input().split()]
c = [[0] * l for i in range(n)]
for ansColumn in range(l):
    for row in range(n):
        for column in range(m):
            c[row][ansColumn] = c[row][ansColumn] + matrixL[row][column] * matrixR[column][ansColumn]
for row in range(n):
    for column in range(l):
        if column == l -1:
            print(c[row][column])
        else:
            print("%d " %c[row][column], end ="")


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

int main() {
    int N; cin >> N;
    vector<long long> ball(N);
    vector<long long> bucket(N, 0);
    for (int i = 0; i < N; i++) {
        cin >> ball.at(i);
        bucket.at(ball.at(i)-1)++;
    }
    
    //まず全て足す
    long long ans = 0;
    for (int i = 0; i < N; i++) {
        ans += bucket.at(i) * (bucket.at(i) - 1) / 2;
    }
    for (int i = 0; i < N; i++) {
        cout << ans - (bucket.at(ball.at(i)-1) - 1) << endl;
    }
}

Measured memory_bytes: 5760
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
T = [int(sys.stdin.readline()) for _ in range(N)]


def lcm(a, b):
    return a * b // gcd(a, b)


a = reduce(lcm, T)
print(a)


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

using namespace std;
#define pb push_back

typedef long long ll;

int N,M;
int L[200100],R[200100];
int rui[400100];
vector<int> zip;
int main(){
	cin >> N >> M;
	for(int i=0;i<N;i++){
		cin >> L[i] >> R[i];
		zip.pb(L[i]);
		zip.pb(R[i]);
	}
	zip.pb(0);
	zip.pb(M);
	sort(zip.begin(),zip.end());
	zip.erase(unique(zip.begin(),zip.end()),zip.end());
	for(int i=0;i<N;i++){
		L[i] = lower_bound(zip.begin(),zip.end(),L[i])-zip.begin();
		R[i] = lower_bound(zip.begin(),zip.end(),R[i])-zip.begin();
	}
	for(int i=0;i<N;i++){
		rui[L[i]]++;
		rui[R[i]+1]--;
	}
	int mx = 0;
	for(int i=1;i<zip.size();i++){
		rui[i] += rui[i-1];
		mx = max(mx,rui[i]);
	}
	int min_ind = 1000000000;
	int max_ind = -1;
	for(int i=0;i<zip.size();i++){
		if(rui[i]==mx){
			min_ind = min(min_ind,i);
			max_ind = max(max_ind,i);
		}
	}
	ll base = (ll)(mx-1)*(ll)M;
	if(mx%2==0){
		base += M-zip[min_ind];
	}else{
		base += zip[max_ind];
	}
	cout << base << endl;
	return 0;
}




Measured memory_bytes: 7580
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
constexpr int INF = INT_MAX;
int H, W, Q;
struct Row {
  int N;
  vector<int> data;
  Row() {
    N = 1;
    while(N < W) N *= 2;
    data.assign(2*N - 1, INF);
  }
  int get(int x) {
    return data[x + N - 1];
  }
  void update(int k, int a) {
    k += N - 1;
    data[k] = a;
    while(k > 0) {
      k = (k - 1)/2;
      data[k] = min(data[2*k + 1], data[2*k + 2]);
    }
  }
  int query(int a, int b) {
    return query2(a, b, 0, 0, N);
  }
  int query2(int a, int b, int k, int l, int r) {
    if(r <= a || b <= l) return INF;
    if(a <= l && r <= b) return data[k];

    return min(query2(a, b, 2*k + 1, l, (l + r)/2),
        query2(a, b, 2*k + 2, (l + r)/2, r));
  }
  void clear() {
    data.clear();
  }
};
struct Grid {
  int K;
  int SQRT_N;
  vector<Row> data;
  vector<Row> stat;
  Grid() {
    SQRT_N = 0;
    while(SQRT_N*SQRT_N < H) SQRT_N++;
    K = (H + SQRT_N - 1) / SQRT_N;
    data.assign(SQRT_N * K, Row());
    stat.assign(K, Row());
  }
  void update(const int y, const int x, const int value) {
    data[y].update(x, value);
    const int k = y / SQRT_N;
    stat[k].update(x, min(stat[k].get(x), data[y].get(x)));
  }
  int query(const int y1, const int x1, const int y2, const int x2) {
    int ret = INF;
    for(int k = 0; k < K; ++k) {
      int l = k * SQRT_N, r = (k + 1) * SQRT_N;
      if(r <= y1 || y2 <= l) continue;
      if(y1 <= l && r <= y2) {
        ret = min(ret, stat[k].query(x1, x2));
      }
      else {
        for(int i = max(y1, l); i < min(y2, r); ++i) {
          ret = min(ret, data[i].query(x1, x2));
        }
      }
    }
    return ret;
  }
};
signed main() {
  ios::sync_with_stdio(false);
  while(true) {
    cin >> H >> W >> Q;
    if(H == 0 && W == 0 && Q == 0) break;
    bool doswap = false;
    if(H > W) {
      doswap = true;
      swap(H, W);
    }
    Grid g;
    if(doswap) {
      REP(y,W) REP(x,H) {
        int v; cin >> v;
        g.update(x, y, v);
      }
    }
    else {
      REP(y,H) REP(x,W) {
        int v; cin >> v;
        g.update(y, x, v);
      }
    }
    REP(q,Q) {
      int y1, x1, y2, x2; cin >> y1 >> x1 >> y2 >> x2;
      if(doswap) {
        swap(x1, y1);
        swap(x2, y2);
      }
      cout << g.query(y1, x1, y2+1, x2+1) << endl;
    }
  }
}

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

using namespace std;
typedef long long ll;

#define INF (long long)(1e9+7)
#define REP(i,n) for(ll i = 0; i < n; i++)
#define REP1(i,n) for(ll i = 1; i <= n; i++)

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

vector<ll> x;

int main(void)
{
  ll n;
  cin >> n;
  REP(i, n) {
    ll x1;
    cin >> x1;
    x.push_back(x1);
  }

  ll ans = -1;
  REP1(p, 100) {
    ll s = 0;
    REP(i, n) {
      s += (x[i] - p) * (x[i] - p);
    }
    if(ans < 0 || ans > s) {
      ans = s;
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int GCD(int x,int y){
	int r;
	if(x<y)swap(x,y);
	while(y>0){
		r=x%y;
		x=y;
		y=r;
	}
	return x;
}
int main(){
	int x,y,Z;
	cin >> x >> y;
	Z=GCD(x,y);
	cout << Z << endl;
}


Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;
#define forx(i, a, b) for (int i = (a); i < (b); i++)
#define rep(j, n) for (int j = 0; j < (n); j++)
typedef long long ll;
typedef vector<int> veci;

int main()
{
    int a, b, k;
    cin >> a >> b >> k;
    if(b-a+1>2*k){
        forx(i, a, a + k) cout << i << endl;
        forx(i, b - k + 1, b + 1) cout << i << endl;
    }
    else
        forx(i, a, b + 1) cout << i << endl;
        return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue> 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> 
#include <numeric>  
#include <functional>
#include <cassert>
#include <bitset>
#include <cctype>  
#include <iomanip> 
#include <limits>  
// std::numeric_limits<int>::max(), min()
// std::setprecision(X)
// std::islower(), std::isupper(), std::tolower, std::toupper
// std::accumulate(m.begin(), m.end(), 0LL);
// std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
// std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
 
#define  rep(i, n) for(int i = 0; i < (int)(n);    i++)
#define rrep(i, n) for(int i = ((int)(n)-1); i>=0; i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;

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


int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  int N; std::cin >> N;
  std::vector<int> a(9);
  for(int i=0; i<N; i++) {
    int b; std::cin >> b;
    int clr = std::min(8,b/400);
    a[clr]++;
  }
  
  int kinds = 0;
  for(int i=0; i<8; i++) if ( a[i] != 0 ) kinds++;
  
  int kmin = 0, kmax = 0;
  if ( kinds == 0 ) kmin = 1;
  else kmin = kinds;
  kmax = kinds+a[8];
  std::cout << kmin << " " << kmax << std::endl;

  return 0;
}


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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl




typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 1e6 + 5;
const int inf = 1e9;


int n, k;
int a[maxn];
int dp[maxn];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
    cin>>n>>k;
    for (int i=0; i<n; i++) {
	cin>>a[i];
    }

    for (int i=1; i<n; i++) {
	dp[i] = inf;
    }

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

    cout<<dp[n-1]<<endl;
    return 0;
}


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

int H, W;

int flame(int h, int w)
{
	for (int i = 0; i < h; i++) {
		for (int 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;
}

int main(){
	while (cin >> H >> W && (H | W) != 0) {
		flame(H, W);
	}

	return 0;
}

Measured memory_bytes: 3068
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define erep(i,a,b) for(int i=a;i<=(int)(b);++i)
#define per(i,a,b) for(int i=(b);i>(a);--i)
#define eper(i,a,b) for(int i=((int)(a));i>=b;--i)
#define pb push_back
#define mp make_pair
#define INF LLONG_MAX
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}

struct edge{
    int to, from;
    ll cost;
};
int n, m;
ll d[2100];
edge es[2100];
ll bad[2100], negative[2100];

int main() {
 ios::sync_with_stdio ( false );
 cin.tie ( 0 );
    cin >> n >> m;
    rep(i, 0, m) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        es[i].from = a;
        es[i].to = b;
        es[i].cost = -c;
    }
    rep(i, 0, n) d[i] = INF;
    d[0] = 0;
    rep(k, 0, n-1) {
        rep(i, 0, m) {
            edge e = es[i];
            if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
                d[e.to] = d[e.from] + e.cost;

            }
        }
    }
    ll ans = d[n-1];
    rep(i, 0, n) {
        rep(j, 0, m) {
            edge e = es[j];
            if (d[e.from] != INF) {
                if (d[e.to] > d[e.from] + e.cost) {
                    d[e.to] = d[e.from] + e.cost;
                    negative[e.from] = true;
                }
                if (negative[e.from]) negative[e.to] = true;
            }
        }
    }
    if (negative[n-1]) cout << "inf" << endl;
    else cout << -ans << endl;
    return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<cmath>
#include<string>
#define ll long long 
using namespace std;

int main()
{
    string str;
    cin>>str;
    int k=0,p=0;
    int i;
    for(i=0;i<str.size();i++)
    {
    	if(str[i]=='A')k++;
    	else p++;
    	
    }
    if(k&&p)cout<<"Yes";
    else cout<<"No";
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;

int main() {
    int N;
    cin >> N;
    int A[N+1], B;
    long ans = 0;
    rep(i, N+1) cin >> A[i];
    rep(i, N) {
        cin >> B;
        long t = 0;
        t = min(A[i] + A[i+1], B);
        ans += t;
        A[i+1] -= t - min(A[i], B);
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)

using namespace std;
using ll = long long;
using P = pair<int,int>;
using ull= unsigned long long;
const ll K_MAX=1e5+5;
const ll Lmax=ll(1e18);
const ll Nmax=1e9;
const double pi=acos(-1);



//基本的に勝つ手をだす．
//勝つ手がなければ，K回後に勝つ手以外を出す．

int main(){
  int n;
  cin>>n;
  vector<int> l(n);
  rep(i,n){
    cin>>l[i];
  }

  sort(l.begin(),l.end());//小さい順
  ll ans=0;

  for(int i=0; i<n; i++){
  //  cout<<l[i]<<endl;
    for(int j=0;j<i;j++){
      for(int k=0; k<j;k++){
        if(l[k]+l[j]>l[i] && l[j]<l[i]+l[k]){
          ans++;
        }
      }
    }
  }

  cout<<ans<<endl;


}


Measured memory_bytes: 3636
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<string>
#include<queue>
#include<utility>
#include<cmath>
#include<sstream>
#include<istream>

using namespace std;


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

  vector<int> H(N);

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

  long long int sum = 0;
  sort(H.begin(), H.end(), greater<int>());
  for(int i=K; i<N; i++){
    sum += H[i];
  }

  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <string>
#include <queue>
#include <numeric>
#include <ctype.h>
#include <limits>
#include <iomanip>

#define rep(i,n) for (int i = 0; i < n; i++)
#define all(x) (x).begin(),(x).end()
using namespace std;

typedef long long ll;

int main()
{
	/*int a, b, c;
	cin >> a >> b >> c;
	if ((a == b && a != c) || (a == c && a != b) || (b == c && b != a)) {
		puts("Yes");
		return 0;
	}
	puts("No");*/


	int n;
	cin >> n;
	int a;
	bool ok = true;
	rep(i, n) {
		cin >> a;
		if (a % 2 == 0) {
			if (a % 3 != 0 && a % 5 != 0) {
				ok = false;
			}
		}
	}
	if (ok)puts("APPROVED");
	else puts("DENIED");


	/*int n;
	cin >> n;
	map<string, int>mp;
	set<string>set;
	string s;
	rep(i, n) {
		cin >> s;
		set.insert(s);
		mp[s]++;
	}
	vector<vector<string>>v;
	for (auto s : set) {
		if (v.size() < mp[s])v.resize(mp[s]);
		v[mp[s] - 1].push_back(s);
	}
	sort(all(v[v.size() - 1]));
	rep(i, v[v.size() - 1].size()) {
		cout << v[v.size() - 1][i] << "\n";
	}*/
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;

void func143c() {
  int n, ans = 1;
  string s;
  cin >> n >> s;
  for (int i = 1; i < s.size(); i++) {
    if (s[i-1] != s[i]) {
      ans++;
    }
  }
  cout << ans << "\n";
}
int main() {
  func143c();
  return 0;
}

Measured memory_bytes: 512
N = int(input())
X = list(map(int, input().split()))
ans = -1
for p in range(min(X), max(X) + 1):
    x = sum(((X[i] - p) ** 2 for i in range(N)))
    if ans > 0:
        if ans > x:
            ans = x
    else:
        ans = x
print(ans)

Measured memory_bytes: 3060
S = list(input())
count = 1
num = 0
for i in S:
  if count %2 == 1:
    if i == "R" or i == "U" or i == "D":
      num += 1
  else:
    if i == "L" or i == "U" or i == "D":
      num += 1
  count += 1
if num == len(S):
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3060
k = int(input())
l = 10
A = [str(i+1) for i in range(9)]
B= ["0"]+A
ans = []

def dfs(num):
    if len(num)>=l:
        ans.append(int(num))
    else:
        ans.append(int(num))
        for i in B:
            if abs(int(num[-1])-int(i))<2:
                dfs(num+i)
if k<=9:
    print(k)
else:
    for i in A:
        dfs(i)
    ans = sorted(ans)
    print(ans[k-1])

Measured memory_bytes: 84288
N, M = map(int,input().split())
if N%2 == 1:
    for i in range(1,M+1):
        print(i,N+1-i)
else:
    for i in range(1,M+1):
        if i == N//4+1:
            break
        print(i,N+1-i)
        if i == M:
            quit()
    for j in range(i,M+1):
        print(j+1,N+1-j)

Measured memory_bytes: 9220
#include <bits/stdc++.h>
using namespace std;
ifstream f("A.in");
typedef long long ll;

int main()
{
   ll x;
    for(int i=1;i<=5;i++)
    {
        cin>>x;
        if(x==0)
        {
            cout<<i;
            return 0;
        }
    }
}


Measured memory_bytes: 3620
N,M=map(int,input().split())
list1=[list(map(int,input().split())) for i in range(M)]
start=[]
end=[]
for i in range(M):
    start.append(list1[i][0])
    end.append(list1[i][1])
stmax=max(start)
#print(stmax)
enmax=min(end)
#print(enmax)
if enmax>=stmax:
    print(enmax-stmax+1)
else:
    print(0)


Measured memory_bytes: 29188
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
#define PI 3.141592653589793
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}
int gcd(int a, int b){//ユークリッドの互除法
  if (a < b) gcd(b,a); //aの方がbよりでかいのが前提
  if (b == 0) return a; //aをbで割り切れたらreturn
  else gcd(b, a % b);
}

const int MOD = 1000000007;
const ll INF = 1LL << 60;

bool dp[100005];

int main(){
  int n,k; cin >> n >> k;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  
  for(int i = 1; i <= k;i++){
    rep(j,n){
      if(i - a[j] >= 0) dp[i] |= !dp[i-a[j]];
    }
  }
  
  if(dp[k]) cout << "First" << endl;
  else cout << "Second" << endl;

  return 0;
}

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

using namespace std;

int main() {
    int n, a[100001], b[100000];
    cin >> n;
    for(int i = 0; i < n + 1; i++) {
        cin >> a[i];
    }
    for(int i = 0; i < n; i++) {
        cin >> b[i];
    }

    long long ans = 0;
    for(int i = 0; i < n; i++) {
        int x = min(a[i], b[i]);
        b[i] -= x;
        int y = min(a[i + 1], b[i]);
        a[i + 1] -= y;
        ans += x + y;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1024