akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<fstream>
#include<sstream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<cmath>
#include<cstdio>
#include<cassert>
using namespace std;

#define REP(i,m,n) for(int i=(m); i<(int)(n); i++)
#define RREP(i,m,n) for(int i=(int)(n-1); i>=m; i--)
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) RREP(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aut(r,v) __typeof(v) r = (v)
#define each(it,o) for(aut(it,(o).begin()); it!=(o).end(); ++it)
#define reach(it,o) for(aut(it,(o).rbegin()); it!=(o).rend(); ++it)
#define fi first
#define se second
#define dump(x) cerr << " [L" << __LINE__ << "] " << #x << " = " << (x) << endl;

inline void debug(){cerr<<endl;}
template<class First, class... Rest>
void debug(const First& first, const Rest&... rest){cerr<<first<<" ";debug(rest...);}
template<typename T>string join(vector<T>&v, string del=", ")
{stringstream s;rep(i,v.size())s<<del<<v[i];return s.str().substr(del.size());}
template<typename T1, typename T2> ostream& operator<<(ostream& o, const pair<T1, T2>& p)
{return o<<"("<<p.first<<", "<<p.second<<")";}
template<typename T>ostream& operator<<(ostream& o, vector<T>&v)
{if(v.size())o<<"["<<join(v)<<"]";return o;}
template<typename T>ostream& operator<<(ostream& o, vector<vector<T> >&vv)
{int l=vv.size();if(l){rep(i,l){o<<(i==0?"[ ":",\n  ")<<vv[i]<<(i==l-1?" ]":"");}}return o;}
template<typename T>ostream& operator<<(ostream& o, const set<T>& st)
{vector<T> v(st.begin(),st.end());o<<"{ "<<join(v)<<" }";return o;}
template<typename T1, typename T2>ostream& operator<<(ostream& o, const map<T1, T2>& m)
{each(p,m){o<<(p==m.begin()?"{ ":",\n  ")<<*p<<(p==--m.end()?" }":"");}return o;}

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;

const double PI = (1*acos(0.0)); 
const double INF = 0x3f3f3f3f;
const double INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;
const ll mod = 1e9 + 7;

inline void finput(string filename) {
    freopen(filename.c_str(), "r", stdin);
}

int N;
vi x, robo;

int main(){
    ios_base::sync_with_stdio(0);
    // finput("./input");

    cin >> N;
    x = vi(N+1);
    rep(i, N) cin >> x[i];
    ll ans = 1;
    rep(i, N){
        robo.push_back(x[i]);
        ll k = robo.size();
        if(x[i] < 2*k - 1){
            robo.pop_back();
            ans = (ans * k) % mod;
        }
    }
    REP(i, 1, robo.size()+1){ ans = (ans * i) % mod; }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

int solve(const vector<int>& a) {
    constexpr auto kTarget = 2;

    int c = 1;
    int n = 0;
    vector<bool> visited(a.size(), false);
    while(c != kTarget) {
        if(visited[c]) {
            return -1;
        }

        visited[c] = true;
        c = a[c];
        ++n;
    } 

    return n;
}

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

    // index start from 1
    vector<int> a(n + 1);
    a[0] = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    cout << solve(a) << endl;

    return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt(), b = sc.nextInt();
		int k = sc.nextInt();
		for (int i = Math.min(a, b); i >= 1; i--) {
			if(a%i==0&&b%i==0) {
				if(k==1) {
					System.out.println(i);
					break;
				}else {
					k--;
				}
			}
		}
		sc.close();
	}
}

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

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

template<typename T>
void output_vector(const vector<T>&v, int start=-1, int end=-1)
{
	if(start<0)start=0;
	if(end<0)end=v.size();
	
	for (int i = start; i < end; i++)
        cout << v[i]<<"\n";
}

int main() {
	
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, i; cin>>n;
    ll a[n], sum=0;
    fore(i, n)
        cin>>a[i];
    ll mx=a[0];
    //cout<<mx<<endl;
    for(i=1;i<n; i++){
        
        mx=max(mx, a[i]);
        //cout<<i<<" th iteration "<<mx<<" ";
        sum+=mx-a[i];
    }
    cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 5216
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int N;
int p[20010];
int a[20010], b[20010];

int main(void){
	cin >> N;
	rep(i, N) cin >> p[i];
	rep(i, N) p[i]--;
	rep(i, N) a[p[i]] = i + 1;
	rep(i, N) a[i] += 20001 * i;
	rep(i, N) b[i] = INF -  20001 * i;
	rep(i, N)printf("%d ", a[i]);
	printf("\n");
	rep(i, N)printf("%d ", b[i]);
	printf("\n");
	/*
	rep(i, N){
		printf("%lld\n", a[i] + b[i]);
	}
	*/
	return 0;
}

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

// macro
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define all(v) v.begin(), v.end()

// code starts
int times=1;

void dfs(int now,vector<int> &fvisit,vector<int> &fin, vector<vector<int>> &vs)
{
  if(fvisit[now]==-1)
  {
    fvisit[now]=times;
    times++;
  }
  else return;
  int i;
  rep(i,vs[now].size())
  {
    if(fvisit[vs[now][i]]==-1)
    {
      dfs(vs[now][i],fvisit,fin,vs);
    }
  }
  fin[now]=times;
  times++;
}

int main()
{
  int n;cin>>n;
  vector<vector<int>> vs(n);
  int i,j;
  rep(i,n)
  {
    int u,k;cin>>u>>k;
    u--;
    rep(j,k)
    {
      int vj;cin>>vj;
      vj--;
      vs[u].emplace_back(vj);
    }
  }
  vector<int> fvisit(n,-1);
  vector<int> fin(n,-1);
  rep(i,n)
  {
    dfs(i,fvisit,fin,vs);
  }
  rep(i,n)
  {
    cout<<i+1<<' '<<fvisit[i]<<' '<<fin[i]<<endl;
  }
}


Measured memory_bytes: 3132
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[]$) {
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        long[] a = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
        }
        Arrays.parallelPrefix(a, Long::sum);
        List<Long> list = new ArrayList<>();
        long highest = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                highest = Math.max(highest, Long.highestOneBit(a[j] - a[i]));
                list.add(a[j] - a[i]);
            }
        }
        long ans = 0;
        for (long i = highest; i > 0; i /= 2) {
            List<Long> newList = new ArrayList<>();
            for (long j : list) {
                if ((j & i) == i) {
                    newList.add(j);
                }
            }
            if (newList.size() >= k) {
                ans += i;
                list = newList;
            }
        }

        System.out.println(ans);
    }
}

Measured memory_bytes: 56424
#include <bits/stdc++.h>
using namespace std;
int MOD;
vector<vector<int>> matrix_multiplication(vector<vector<int>> A, vector<vector<int>> B){
  int N = A.size();
  vector<vector<int>> ans(N, vector<int>(N, 0));
  for (int i = 0; i < N; i++){
    for (int j = 0; j < N; j++){
      for (int k = 0; k < N; k++){
        ans[i][k] += A[i][j] * B[j][k];
        ans[i][k] %= MOD;
      }
    }
  }
  return ans;
}
vector<vector<int>> matrix_exponentiation(vector<vector<int>> A, int b){
  int N = A.size();
  vector<vector<int>> ans(N, vector<int>(N, 0));
  for (int i = 0; i < N; i++){
    ans[i][i] = 1;
  }
  while (b > 0){
    if (b % 2 == 1){
      ans = matrix_multiplication(ans, A);
    }
    A = matrix_multiplication(A, A);
    b /= 2;
  }
  return ans;
}
int main(){
  while (1){
    int N, M, A, B, C, T;
    cin >> N >> M >> A >> B >> C >> T;
    if (N == 0 && M == 0 && A == 0 && B == 0 && C == 0 && T == 0){
      break;
    }
    vector<int> S(N + 2, 0);
    for (int i = 1; i <= N; i++){
      cin >> S[i];
    }
    MOD = M;
    vector<vector<int>> mat(N + 2, vector<int>(N + 2, 0));
    for (int i = 1; i <= N; i++){
      mat[i][i - 1] = A;
      mat[i][i] = B;
      mat[i][i + 1] = C;
    }
    mat = matrix_exponentiation(mat, T);
    vector<int> ans(N + 2, 0);
    for (int i = 0; i < N + 2; i++){
      for (int j = 0; j < N + 2; j++){
        ans[i] += mat[i][j] * S[j];
        ans[i] %= MOD;
      }
    }
    for (int i = 1; i <= N; i++){
      cout << ans[i];
      if (i < N){
        cout << ' ';
      }
    }
    cout << endl;
  }
}


Measured memory_bytes: 3272
#include<stdio.h>

int main(void){
  char c[10];
  int len = 0,max = 0,n;
  scanf("%s",c);
  for(int i = 0;c[i]!= '\0';i++){
    if(c[i] == 'A'||c[i] == 'T'||c[i] == 'G'||c[i] == 'C'){ 
      len = 1;
      n = i + 1;
      while(c[n]!= '\0'&&(c[n] == 'A'||c[n] == 'T'||c[n] == 'G'||c[n] == 'C'))len++,n++;
      
    }
    if(max < len)max = len;
  }
  printf("%d",max);
}

Measured memory_bytes: 128
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;

class Solution {
public:
    vector<pair<int,int>> solve(vector<long long>& W) {
        int n = W.size();
        vector<pair<long long,int>> P;
        for (int i = 0; i < n; ++i) {
            P.emplace_back(W[i], i);
        }
        sort(P.begin(), P.end());


        vector<long long> sums(n, 0);
        vector<int> sizes(n, 1);
        vector<int> pars(n, -1);

        for (int i = n - 1; i > 0; --i) {
            int u = P[i].second;
            long long sum = P[i].first;
            long long tar = sum - (n - 2 * sizes[u]);
            if (tar == sum) {
                return {};
            }
            auto it = lower_bound(P.begin(), P.end(), make_pair(tar, -1));
            if (it == P.end()) {
                return {};
            }
            if (it->first != tar || it->second == u) {
                return {};
            }
            int p = it->second;
            sums[p] += sums[u] + sizes[u];
            sizes[p] += sizes[u];
            pars[u] = p;
        }

        if (sums[P[0].second] != P[0].first) {
            return {};
        }

        vector<pair<int,int>> res;
        for (int i = 0; i < n; ++i) {
            if (pars[i] >= 0) {
                res.emplace_back(pars[i], i);
            }
        }

        return res;
    }
};

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

    int n;
    cin >> n;
    vector<long long> W(n, 0);
    for (int i = 0; i < n; ++i) {
        cin >> W[i];
    }
    Solution sol;
    auto res = sol.solve(W);
    if (res.size() != n - 1) {
        cout << "-1\n";
    } else {
        for (auto& e : res) {
            cout << e.first + 1 << " " << e.second + 1 << "\n";
        }
    }

    return 0;
}

Measured memory_bytes: 7636
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>

using namespace std;

int main()
{
	char c[3][3];

	for(int i=0; i<3; i++){
		scanf("%s", c[i]);
	}

	printf("%c%c%c\n", c[0][0], c[1][1], c[2][2]);

	return 0;
}

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

using namespace std;

int main(){
  int64_t n;
  cin >> n;
  vector< string > a;
  vector< pair<int64_t, string> >s;
  string tmp;
  for(int64_t i=0;i<n;i++){
    string tmp;
    cin >> tmp;
    a.push_back( tmp );
  }
  sort(a.begin(), a.end());
  tmp=a.at(0);
  int64_t count=0;
  for(int64_t i=1;i<a.size();i++){
    if( tmp == a.at(i) ){
      count++;
    }
    else{
      s.push_back( make_pair(count, tmp) );
      tmp = a.at(i);
      count=0;
    }
  }
  s.push_back( make_pair(count, tmp) );
  sort(s.begin(), s.end());
  int64_t index=s.at( s.size()-1 ).first;
  for(int64_t i=0;i<s.size();i++){
    if(index == s.at(i).first)
    cout << s.at(i).second << endl;
  }

  return 0;
}


Measured memory_bytes: 18540
import java.io.BufferedReader;
import java.io.CharArrayReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;

/**
 * Problem B: Monster Factory
 */
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";

		while (!(line = br.readLine()).equals("-")) {

			LinkedList<Character> rightword = new LinkedList<Character>();
			LinkedList<Character> downword = new LinkedList<Character>();
			Character center;
			ArrayList<Character> right = new ArrayList<Character>();
			LinkedList<Character> down = new LinkedList<Character>();

			//
			for (char c : line.toCharArray()) {
				downword.add(c);
			}
			for (char c : br.readLine().toCharArray()) {
				rightword.add(c);
			}
			for (char c : br.readLine().toCharArray()) {
				down.add(c);
			}
			//
			center = rightword.removeFirst();
			while (center != null) {
				if (!down.isEmpty()) {
					if (down.peekFirst().equals(center)) {
						down.removeFirst();
						if (!downword.isEmpty())
							center = downword.removeFirst();
						else
							center = null;
					} else {
						right.add(center);
						if (!rightword.isEmpty())
							center = rightword.removeFirst();
						else
							center = null;
					}
				} else {
					right.add(center);
					if (!rightword.isEmpty())
						center = rightword.removeFirst();
					else
						center = null;
				}
			}
			StringBuilder sb = new StringBuilder();
			for (char c : right) {
				sb.append(c);
			}
			System.out.println(sb.toString());
		}
	}
}

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

int main() {
int N;
int room[4][3][10];
cin >> N;
for(int i = 0; i < 4; i++){
for(int j = 0; j < 3; j++){
for(int k = 0; k < 10; k++){
room[i][j][k] = 0;
}

}

}



for(int i = 0; i < N; i++){
int a, b, c, d;
cin >> a >> b >> c >> d;
a--;
b--;
c--;
room[a][b][c] += d;
}
for(int i = 0; i < 4; i++){
for(int j = 0; j < 3; j++){
for(int k = 0; k < 10; k++){
cout << " " << room[i][j][k];
if(k==9){
cout << endl;
}
if(j==2 && k==9 && i!=3){
cout << "####################" << endl;
}
}

}

}


}




Measured memory_bytes: 3100
import sys, re
from math import ceil, floor, sqrt, pi, factorial#, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    s = s_input()
    t = s_input()

    len_s = len(s)

    sl = list(s)

    for i in range(len_s):
        tmp = ''.join(sl)
        if tmp == t:
            Yes()
            exit()
        sl.append(sl[0])
        sl = sl[1:]
    No()

if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
#include<stdio.h>

int main(void)
{
        int i,j;
        int n,tmp,kaisu;

        scanf("%d",&n);

        int a[n];

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

        kaisu = 0;
        tmp = a[0];
        for(i=1;i<n;i++){
                kaisu++;
                if(tmp==2){
                        printf("%d\n",kaisu);
                        return 0;
                }
                tmp = a[tmp-1];
        }

        printf("-1\n");
        return 0;
}


Measured memory_bytes: 512
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
using in = int64_t;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
const double PI=3.14159265358979323846;
const in MOD = 1000000007;
const in INF=1e18+7;
const int inf=1e9+7;
using P=pair<int,int>;
vector<int> dx={0,1,-1,0};
vector<int> dy={1,0,0,-1};


int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << fixed << setprecision(10);
    in n;
    cin>>n;
    vector<in> a(n);
        rep(i,n) cin>>a.at(i);
    in sum =0ll;
    rep(i,n){
        sum += a[i];
        sum %= MOD;
    }

    in ans=0ll;
    rep(i,n-1){
        sum -= a[i];
        if(sum<0) sum += MOD;
        ans += sum * a[i];
        ans %= MOD; 
    }
    cout<<ans<<endl;
}/*
./problem.exe
*/

Measured memory_bytes: 4776
// arc073_a
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <type_traits>
#include <typeindex>
#include <unordered_map>
#include <unordered_set>
#endif

template <typename A, typename B> bool cmin(A &a, const B &b) {
  return a > b ? (a = b, true) : false;
}
template <typename A, typename B> bool cmax(A &a, const B &b) {
  return a < b ? (a = b, true) : false;
}
const double PI = acos(-1);
const double EPS = 1e-9;
int inf = sizeof(int) == sizeof(long long) ? 2e18 : 1e9 + 10;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  int N, T;
  cin >> N >> T;
  ll ans = 0;
  int beforeT = 0;
  rep(i, N) {
    int nowT;
    cin >> nowT;
    ans += min(T, nowT - beforeT);
    beforeT = nowT;
  }
  ans += T;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3604
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, A, B; cin >> N >> A >> B;
	rep(i, 0, N) {
		if (A + 1 == B) {
			if (A == 1) {
				cout << "Borys" << endl;
				break;
			}
			A--;
		}
		else {
			A++;
		}
		if (A + 1 == B) {
			if (B == N) {
				cout << "Alice" << endl;
				break;
			}
			B++;
		}
		else {
			B--;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n;
string A, B;
inline string get(int a)
{
	cout << a << endl;
	fflush(stdout);
	string s;
	cin >> s;
	if(s == "Vacant")exit(0);
	return s;
}
int main()
{
	cin >> n;
	A = get(0);
	B = get(n-1);
	int low = 0, high = n - 1;
	while (low <= high){
		int mid = low + high >> 1;
		string now = get(mid);
		if (now == A){
			if (mid % 2 ==0)low = mid + 1;
			else high = mid - 1;
		}
		else if (now == B){
			if(mid % 2 == 1)low = mid + 1;
			else high = mid - 1;
		}
	} 
	return 0;
}

Measured memory_bytes: 852
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a.begin(),a.end());
    if(n%2){
        if(a[0]!=0){cout<<0<<endl;return 0;}
        for(int i=2;i<n;i+=2)if(i!=a[i]||a[i]!=a[i-1]){cout<<0<<endl;return 0;}
    }else{
        for(int i=1;i<n;i+=2)if(i!=a[i]||a[i]!=a[i-1]){cout<<0<<endl;return 0;}
    }
    ll ans=1;
    for(int i=0;i<n/2;i++){ans*=2;ans%=1000000007ll;}
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
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 long long INF = 1e18;
//const ll mod = 1000000007;
struct UnionFind {
    vector<int> par;
    vector<int> rank;
    vector<ll> Size;
    vector<ll> l, r;
    UnionFind(int n = 1) {
        init(n);
    }

    void init(int n = 1) {
        par.resize(n + 1); rank.resize(n + 1); Size.resize(n + 1);
        l.resize(n + 1), r.resize(n+1);
        for (int i = 0; i <= n; ++i) l[i] = i, r[i] = i, par[i] = i, rank[i] = 0, Size[i] = 1;
    }

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

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

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        Size[x] += Size[y];
        chmin(l[x], l[y]);
        chmax(r[x], r[y]);
        return true;
    }

    ll size(int x){
        return Size[root(x)];
    }
};

ll N;
vector<ll> A;
ll g(ll a, ll b) {
    if(a == b) return 0;
    if(a < b) {
        ll ret = 0;
        while(a < b) {
            a *= 4;
            ret += 2;
        }
        return ret;
    } else {
        return -g(b, a) + 2;
    }
}
vector<ll> f(vector<ll> A) {
    vector<ll> L(N + 1);
    vector<ll> add(N);
    UnionFind uni(N);
    for(int i = N - 1; i >= 0; i--) {
        ll delta = 0;
        ll idx = i + 1;
        while(idx <= N - 1) {
            ll tmp = g(A[idx], A[idx-1]) + add[idx-1] - add[idx];
            //cerr << idx << " " << tmp << endl;
            if(tmp <= 0) break;
            delta += tmp * uni.size(idx);
            ll l = uni.l[uni.root(idx)];
            ll r = uni.r[uni.root(idx)];
            //cerr << i << " " << idx << " " << l << " " << r << " " << tmp << endl;
            add[l] += tmp;
            if(l != r) add[r] += tmp;
            idx = r + 1;
            uni.merge(l, l - 1);
        }
        L[i] = L[i+1] + delta;
    }
    return L;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    A.resize(N);
    for(int i = 0; i < N; i++) cin >> A[i];
    vector<ll> L = f(A);
    for(int i = 0; i < L.size(); i++) {
        cerr << L[i] << " ";
    }
    cerr << endl;
    reverse(A.begin(), A.end());
    vector<ll> R = f(A);
    for(int i = 0; i <= N; i++) {
        R[i] += N - i;
    }
    ll ans = 1e18;
    for(int i = 0; i <= N; i++) {
        chmin(ans, L[i] + R[N-i]);
    }
    cout << ans << endl;
    /*
    for(ll i = 1; i <= 40; i++) {
        for(ll j = 1; j <= 10; j++) {
            cerr << i << " " << j << " " << g(i, j) << endl;
        }
    }
    */
    return 0;
}

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

const long long MOD = 1000000007;

int main(){
  int N; cin >> N;
  string c1, c2; cin >> c1 >> c2;
  
  long long ans = 0LL;
  int i = 0;
  bool pre = 0;
  if(c1[0] == c2[0]) {ans = 3LL; i = 1; pre = 0;}
  else {ans = 6LL; i = 2; pre = 1;}
  
  for(; i < N; i++){
    bool now = (c1[i] != c2[i]);
    if(pre && now) {ans *= 3; i++;}
    if(!pre && now) {ans *= 2; i++;}
    if(!pre && !now) {ans *= 2;}
    pre = now;
    ans %= MOD;
  }
  
  cout << ans;
}

Measured memory_bytes: 256
//
//  main.cpp
//  ALDS1_5_B
//
//  Created by ptyuan on 2018/10/28.
//  Copyright © 2018 Sy. All rights reserved.
//

#include <iostream>
#include <cstdio>
using namespace std;

const int kMaxValue = 2000000000;
const int kMax = 500000;

int A[kMax] = {0};

int L[kMax / 2 + 2];
int R[kMax / 2 + 2];
int cmpCount = 0;

void _merge(int *A, int n, int left, int mid, int right) {
    int n1 = mid - left;
    for (int i = 0; i < n1; i++) {
        L[i] = A[left + i];
    }
    
    int n2 = right - mid;
    for (int i = 0; i < n2; i++) {
        R[i] = A[mid + i];
    }
    
    L[n1] = kMaxValue;
    R[n2] = kMaxValue;
    int l1 = 0;
    int l2 = 0;
    for (int k = left; k < right; k++) {
        ++cmpCount;
        if (L[l1] <= R[l2]) {
            A[k] = L[l1++];
         } else {
             A[k] = R[l2++];
         }
    }
}

void mergeSort(int *A, int n, int left, int right) {
    if (left + 1 < right) {
        int mid = (left + right) / 2;
        mergeSort(A, n, left, mid);
        mergeSort(A, n, mid, right);
        _merge(A, n, left, mid, right);
    }
}



int main(int argc, const char * argv[]) {
    int n = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", A + i);
    }
    
    mergeSort(A, n, 0, n);
    for (int i = 0; i < n; i++) {
        int value = A[i];
        if (i > 0) {
            printf(" ");
        }
        printf("%d", value);
    }
    printf("\n");
    printf("%d\n", cmpCount);
    
    
    return 0;
}



Measured memory_bytes: 7028
M,D=map(int,input().split())

ans=0
for i in range(1,M+1):
  for j in range(1,D+1):
    if j>=10:
      m=i
      d10=int(str(j)[0])
      d1=int(str(j)[1])
      if d10>=2 and d1>=2 and m==d10*d1:
        ans+=1
print(ans)

Measured memory_bytes: 3060
def main():
    n = int(input())

    r  = 0
    ri = 0

    for i in range(n):
        m = int(input())

        if 0 == i:
            ri = m
            continue

        if 1 == i:
            r = m - ri

        r  = max(r, m - ri)
        ri = min(ri, m)

    print(r)

if __name__ == '__main__':
    main()

Measured memory_bytes: 7680
n,k = map(int,input().split())
a = [0]+list(map(int,input().split()))
for i in range(n):
    a[i+1] += a[i]
cnt = {}
ans = 0
for i in range(n+1):
    left = i-k
    if left >= 0:
        ldiff = (a[left] - left)%k
        cnt[ldiff]-=1
    diff = (a[i]-i)%k
    if diff not in cnt:cnt[diff] = 0
    ans += cnt[diff]
    cnt[diff] +=1
print(ans)
             

Measured memory_bytes: 39912
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,Q,K,A,B;
string S;
const ll MOD = 998244353;
//const ll MOD = (1e+9) + 7;
typedef pair<ll, ll> P;
const ll INF = (1LL<<50);

int main() {
    cin>>N>>M;
    if(N&1){
        int a = 1, b = N - 1;
        rep(i,M){
            cout<<a<<' '<<b<<endl;
            ++a;
            --b;
        }
    }else{
        int a = 1, b = N;
        bool m = false;
        rep(i,M){
            cout<<a<<' '<<b<<endl;
            ++a;
            --b;
            if(b - a <= N / 2 && !m) {
                --b;
                m = true;
            }
        }
    }
}

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

using lint = long long;

int main() {
    int n;
    cin >> n;
    vector<lint> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end(), greater<lint>());

    vector<lint> s(n);
    s[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        s[i] = s[i + 1] + a[i];
    }

    int pos = 0;
    while (true) {
        if (pos < n - 1 and a[pos] <= s[pos + 1]*2) {
            pos++;
        } else {
            break;
        }
    }

    cout << pos + 1 << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) (v).begin(), (v).end()

using namespace std;
using ll = long long;

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 (a>b) { a=b; return 1; } return 0; }
const ll LINF = 1e18;

int main()
{
  string S; ll K; cin >> S >> K;
  ll last1 = 0;
  for (int i = 0; i < S.size(); ++i) {
    if (S[i] == '1') continue;
    last1 = i;
    break;
  }

  if (K > last1) {
    cout << S[last1] << endl;
  } else {
    cout << 1 << endl;
  }
}


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

int A[N];

void insert(int num){
  A[0]++;
  increase(A[0],num);

}
int extract(){
  int max = A[1];
  A[1] = A[A[0]];
  A[0]--;
  maxHeapify(1);
  return max;
}
void maxHeapify(int i){
  int l,r,H,largest;
  l = i * 2;
  r = i * 2 + 1;

  if(l <= A[0] && A[l] > A[i])
    largest = l;
  else
    largest = i;
  if(r <= A[0] && A[r] > A[largest])
    largest = r;
  if(largest != i){
    H = A[i];
    A[i] = A[largest];
    A[largest] = H;
    maxHeapify(largest);
  }
}
void increase(int i,int key){
  int c;
  A[i] = key;
  while(i > 1 && A[i/2] < A[i]){
    c = A[i/2];
    A[i/2] = A[i];
    A[i] = c;
    i = i/2;
  }
}

int main(){
  char s[10];
  int num;
  A[0] = 0;
  while(1){
    scanf("%s",s);
    switch(s[2]){
    case 's':
      scanf("%d",&num);
      insert(num);
      break;
    case 't':
      printf("%d\n", extract());
      break;
    case 'd':
      goto END;
      break;
    }
  }
 END:
  return 0;
}



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

using namespace std;
using ull = unsigned long long;
using ll = long long;
using lli = long long int;
using ld = long double;
using pa = pair<int,int>;
using ppa = pair<pa,int>;
#define SORT(v, n) sort(v, v+n);
#define ALL(v) v.begin(),v.end()
#define VSORT(v) sort(ALL(v))
#define GRESORT(v) sort(ALL(v),greater<ll>())
#define REVERSE(v) reverse(ALL(v))
#define overlap(v) v.erase(unique(ALL(v)),v.end())
#define debug(x) cout << #x << ": " << x << endl
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i = (b-1); i >= a; i--)
#define rrep(i,n) RFOR(i,0,n)
#define INF 999999999
#define mins(a,b) a = min(a,b)
#define maxs(a,b) a = max(a,b)

//4近傍
//int dy[]={0, 0, 1, -1};
//int dx[]={1, -1, 0, 0};

//8近傍
int dy[]={0,0,1,-1,1,1,-1,-1};
int dx[]={1,-1,0,0,1,-1,1,-1};

ll mod = 1000000007;

void solve() {
    int a,b,h; cin >> a >> b >> h;
    cout << (a+b)*h/2 << endl;
}

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

    solve();

    return 0;
}

Measured memory_bytes: 256
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define all(x) begin(x),end(x)
#define unmap unordered_map
#define pii pair<int,int>
#include <bits/stdc++.h>
#define pll pair<ll,ll>
#define vll vector<ll>
#define vi vector<int>
#define ld long double
#define ll long long
#define pb push_back
#define sh short int
#define mid (l+r)/2
#define S second
#define F first
using namespace std;
const int inf = 1e9;
const ll mod = 998244353;
int n;
string s;
set < string > se;
int main(){
    fast,cin>>n;
    for(int i=0;i<n;i++){
        cin>>s;
        se.insert(s);
    }
    int sz = se.size();
    cout<<sz<<endl;
}


Measured memory_bytes: 19144
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<bits/stdc++.h>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> myds;

#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define F first
#define S second
#define vec(x) vector<x> 
#define pi(x,y) pair<x,y>
#define pqq(x) priority_queue<x> 
#define min_heap(x) priority_queue<x, vector<x>, greater<x> >
#define all(x) x.begin(),x.end()
#define rep(i,x,y) for(int i=x;i<y;i++)
#define repd(i,x,y,k) for(int i=x;i<y;i+=k)
#define rel(i,x,y) for(int i=x-1;i>=y;i--)
#define rev(x) reverse(all(x))
#define uniq(x) x.resize(distance(x.begin(),unique(all(x))))
#define full(x,a) memset(x,a,sizeof(x))
#define lcm(x,y) ((x*y)/__gcd(x,y))
#define mod 1000000007
#define bitcount __builtin_popcountll
#define pb push_back
#define indexof order_of_key
#define valueat find_by_order

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int dxx[8]={0,0,1,-1,-1,-1,1,1};
int dyy[8]={1,-1,0,0,-1,1,1,-1};

int gcdextended(int a,int b,int &x,int &y){if(!a){x=0,y=1;return b;}int x1,y1;int ans=gcdextended(b%a,a,x1,y1);x=y1-(b/a)*x1;y=x1;return ans;}
int inv(int a){int x,y;int ans=gcdextended(a,mod,x,y);return(x%mod+mod)%mod;}
int nCr(int n,int k){int res=1;k=(k>n-k)?n-k:k;rep(i,0,k){res*=(n-i);res/=(i+1);}return res;}
int POW(int x,int y){int res=1;x=x%mod;while(y>0){if(y&1)res=(res%mod*x)%mod;y=y>>1;x=(x*x)%mod;}return res;}
//void seive(){prime[0]=0;prime[1]=0;rep(i,2,10002)prime[i]=1;for(int i=2;i*i<=10000;i++){if(prime[i]){for(int j=i*i;j<=10000;j+=i)prime[j]=0;}}} 

const int N=100005;
int x,y,a,b,c;
int p[N],q[N],r[N];

void input(){
	cin>>x>>y>>a>>b>>c;
	rep(i,0,a)
		cin>>p[i];
	rep(i,0,b)
		cin>>q[i];
	rep(i,0,c)
		cin>>r[i];
}

void solve(){
	sort(p,p+a,greater<int>());
	sort(q,q+b,greater<int>());
	sort(r,r+c,greater<int>());
	int red=x-1,green=y-1,cless=0;
	while(red>=0 && green>=0 && cless<c){
		if(p[red]>=q[green]){
			if(q[green]<=r[cless]){
				q[green]=r[cless];
				cless++;
				green--;
			}
			else
				break;
		}
		else{
			if(p[red]<=r[cless]){
				p[red]=r[cless];
				red--;
				cless++;
			}
			else
				break;
		}
	}
	while(cless<c && red>=0){
		if(p[red]<=r[cless]){
			p[red]=r[cless];
			red--;
			cless++;
		}
		else
			break;
	}
	while(cless<c && green>=0){
		if(q[green]<=r[cless]){
			q[green]=r[cless];
			green--;
			cless++;
		}
		else
			break;
	}
	int ans=0;
	rep(i,0,x)
		ans+=p[i];
	rep(i,0,y)
		ans+=q[i];
	cout<<ans<<endl;
}

main(){
	fastio;
	int t=1;
	while(t--){
		input();
		solve();
	}
}

Measured memory_bytes: 2560
def  makabe(nam, co):
  ky=(nam+co)/2.0
  return ky



n=int(input())
g=list(map(int,input().split()))
g.sort()
ty=(g[0]+g[1])/2.0
for h in range(2,n):
  ty= makabe(ty,g[h])
  
print(ty)

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

int main() {
  ll a,b,c,d; cin >> a >> b >> c >> d;
  cout << max(a*c,max(a*d,max(b*c,b*d))) << endl;
  return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define fi first
#define se second
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int( 1e5 +5)

int main(){
    int n[4];
    REP(i,4) cin >> n[i];
    sort(n,n+4);
    if(n[0] == 1 and n[1] == 4 and n[2] == 7 and n[3] == 9){
        cout << "YES" << endl;
    }
    else cout << "NO" << endl;

}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<ll, P> E;
#define MOD (1000000007ll)
#define l_ength size
#define PI 3.14159265358979
 
void mul_mod(ll& a, ll b){
    a *= b;
    a %= MOD;
}
 
void add_mod(ll& a, ll b){
    b += MOD;
    a += b;
    a %= MOD;
}

int main(void){
    int n,i,m;
    ll a[225816];
    vector<ll> b;
    cin >> n;
    m = n/2;
    for(i=0; i<n; ++i){
        cin >> a[i];
        b.push_back(a[i]);
    }
    sort(b.begin(),b.end());
    for(i=0; i<n; ++i){
        cout << ((a[i]<b[m])?b[m]:b[m-1]) << endl;
    }
    return 0;
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pii;
typedef vector<long long> vll;
typedef vector<pii> pxx;
typedef vector<int> vi;
#define pb push_back
#define mod  1000000007
#define PI 2*acos(0.0)
#define REP(i,a,b)  for(i = a; i <= b; i++)
#define f(a,b)  for(a=0 ; a<b; a++)



main()
{
    ll n,k,d,pd,q;
    cin >> n >> k >> d;
    if(n<0) n*=-1;
    if(k<=n/d)
    {
        cout << n-k*d << endl;
    }
    else
    {
        q=n/d;
        pd=n%d;
        if((k-q)%2)
        {
            cout << d-pd << endl;
        }
        else cout << pd << endl;
    }
}


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

using namespace std;
typedef long long ll;

int main(){
    int ans = 0;
    int n, x;
    int d = 0;
    cin >> n >> x;
    vector<int> b;
    for (int i = 0; i < n; i++){
        int t;
        cin >> t;
        b.push_back(t);
    }
    for (int i = 1; i <= n; i++){
        d = d + b[i - 1];
        if (d > x) ans++;
    }
    cout << n - ans + 1;
    return 0;
}


Measured memory_bytes: 256
//File Name: tenka1_2017_d.cpp
  //Created Time: 2017年10月13日 星期五 21时31分07秒
                                   
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN = 100000 + 5;
LL a[MAXN],b[MAXN];

LL cal(const int n,const LL m){
	LL res(0);
	for(int i(0);i<n;++i){
		if((a[i] | m) == m)
			res += b[i];
	}
	return res;
}
LL solve(const int n,const LL m){
	LL res = cal(n,m);
	LL pre(m);
	for(int i(0);i<30;++i){
		if(m & (1LL << i)){
			LL tmp = pre ^ (1LL << i);
			LL cur = cal(n,tmp);
			if(cur > res)
				res = cur;
		}
		else
			pre |= (1LL << i);
	}
	return res;
}
int main(){
	int n;
	LL m;
	scanf("%d %lld",&n,&m);
	for(int i(0);i<n;++i)
		scanf("%lld %lld",a + i,b + i);
	printf("%lld\n",solve(n,m));
	return 0;
}


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

using namespace std;

int main(){
    int k;
    string s;
    cin >> k >> s;
    if( s.length() > k ){
        cout << s.substr(0,k) <<  "...";
    }else{
        cout << s;
    }
  return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define int long long
#define ld long double
#define fi first
#define se second
#define all(uiet) uiet.begin(),uiet.end()
#define read(UIET) for(int i = 0; i < n; ++i) cin >> UIET[i]
#define out(UIET) for(int i = 0; i < n; ++i) cout << UIET[i]
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vpp vector<pair< int, int > >
#define pll pair<int , int >
#define ppll pair < pll , pll >
#define debug(n1) cout << n1 << endl
#define len(a) ((int) (a).size())
#define endl "\n"
#define mod 1000000007
const int INF=(1LL<<60)-1;
bool isPerfectSquare(long double x) {   
    long double sr = sqrt(x); 
    return ((sr - floor(sr)) == 0); 
} 
bool isPrime(int x){
    for(int i = 2; i * i <= x; ++i){
        if(x % i == 0) return 0;
    }
    return 1;
}
int fun(int n){
    if(n & 1) return 3 * n + 1;
    else return n/2;
}
int32_t main(){
    SPEED;
    int n, x;
    cin >> n >> x;
    int arr[n];
    int sum = 0;
    for(int i = 0; i < n; ++i){
        cin >> arr[i];
        sum += arr[i];
    }
    if(sum == x) cout << n ;
    else if(x > sum) cout << n - 1;
    else{
        sort(arr, arr + n);
        int ans = 0;
        for(int i = 0; i < n; ++i){
            x -= arr[i];
            if(x >= 0) ans++;
        }
        cout << ans;
    }
}


Measured memory_bytes: 3692
#include<iostream>
#include<string>
using namespace std;
int main() {
	int h,n,a;
	cin>>h>>n;
	while(n--)
	{
		cin>>a;
		h-=a;
	}
	if(h<=0) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

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

#define MOD 10000007
#define f first
#define s second
#define es " "
#define pb push_back
#define endl "\n"
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define ll long long int
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int n, q, resp[200005], memo[200005];

vector<int> viz[200005];

void dfs(int x){
    memo[x]=1;
    for(int i=0; i<viz[x].size(); i++){
        int u=viz[x][i];
        if(!memo[u]){
            resp[u]+=resp[x];
            dfs(u);
        }
    }
}

int main(){
    fastio;
    cin >> n >> q;
    for(int i=0,a, b; i<n-1; i++){
        cin >> a >> b;
        viz[a].pb(b);
        viz[b].pb(a);
    }
    for(int i=0, a, x; i<q; i++){
        cin >> a >> x;
        resp[a]+=x;
    }
    dfs(1);
    for(int i=1; i<=n; i++){
        cout << resp[i] << es;
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 24320
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout);
using namespace std;
typedef long long ll;
const int MAXN = 200005;
const int ESIZE = MAXN << 1;
const ll INF = 2e9;
int n, Q, tot;
ll s[MAXN], t[MAXN];
int bel[MAXN], rk[MAXN];
ll ans;

struct like {
    int u, v; ll c;
    bool operator < (const like &r) const {
        return c < r.c;
    }
} e[ESIZE];

int find(int p) {
    return p == bel[p] ? p : bel[p] = find(bel[p]);
}

void Union(int x, int y) {
    if (rk[x] < rk[y])
        swap(x, y);
    if (rk[x] == rk[y])
        rk[x]++;
    bel[y] = x;
}

int main() {
    scanf("%d %d", &n, &Q);
    for (int i = 0; i < n; i++)
        s[i] = t[i] = INF, bel[i] = i;
    int a, b; ll c, x = INF;
    for (int i = 1; i <= Q; i++) {
        scanf("%d %d %lld", &a, &b, &c);
        e[i] = (like){a, b, c};
        s[a] = min(s[a], c + 1), s[b] = min(s[b], c + 2);
    }
    tot = Q;
    for (int i = 0; i < n << 1; i++, x = min(x + 2, INF))
        if ((x = min(x, s[i % n])) != INF)
            t[i % n] = min(t[i % n], x);
    for (int i = 1; i < n; i++)
        if (t[i - 1] != INF)
            e[++tot] = (like){i - 1, i, t[i - 1]};
    if (t[n - 1] != INF)
        e[++tot] = (like){n - 1, 0, t[n - 1]};
    sort(e + 1, e + tot + 1);
    for (int i = 1, r1, r2; i <= tot; i++)
        if ((r1 = find(e[i].u)) != (r2 = find(e[i].v))) {
            ans += e[i].c;
            Union(r1, r2);
        }
    printf("%lld", ans);
    return 0;
}


Measured memory_bytes: 11136
MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
ans = 1
l = [0] * 3
for x in a:
    ans *= l.count(x)
    ans %= MOD
    for j in range(3):
        if l[j] == x:
            l[j] += 1
            break
print(ans)

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

typedef long long ll;
// int = ll;

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

	ll a;
	
	cin >> a;
	
	if(a<=9||a==12||a==16||a==10||a==15||a==18||a==20||a==21||a==25||a==24||a==28||a==32||a==35||a==36||a==45||a==42||a==27||a==54||a==63||a==64||a==72||a==81||a==14||a==30||a==40||a==48||a==49||a==56){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}

return 0;	
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
int n,m;
int main(){
   ll a,b,c,d;
   cin>>a>>b>>c>>d;
   vector<ll> num;
   num.push_back(a*c);
   num.push_back(a*d);
   num.push_back(b*d);
   num.push_back(b*c);
   sort(num.begin(),num.end());
   cout<<num[3]<<endl;

}


Measured memory_bytes: 3628
import java.util.*;
import java.lang.*;

class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		String word = sc.next().toLowerCase();
		int c = 0;
		
		while (true) {
			String key = sc.next();
			if(key.equals("END_OF_TEXT")) break;
			if(word.equals(key.toLowerCase())) c++;
			
		}
		
		System.out.println(c);
	}
}


Measured memory_bytes: 26348
import math

N = int(input())

ans = [0] * (N + 1)

for i in range(1, int(math.sqrt(N)) + 1):
    for j in range(1, int(math.sqrt(N)) + 1):
        for k in range(1, int(math.sqrt(N)) + 1):
            v = i * i + j * j + k * k + i * j + j * k + k * i
            if v <= N:
                ans[v] += 1

for i in range(1, N + 1):
    print(ans[i])


Measured memory_bytes: 9164
#include<iostream>
#include<vector>
#include<stdio.h>
#include<algorithm>

using namespace std;

const static int INFTY=(1<<21);
const static int MAXM=10000;

int d,n,m;
int order[MAXM];

void solve()
{
	vector<int> shops;
	shops.push_back(0);
	shops.push_back(d);
	int temp;
	int res=0;
	for(int i=0;i<n-1;i++)
	{
		scanf("%d",&temp);
		shops.push_back(temp);
		shops.push_back(temp+d);
	}
	for(int i=0;i<m;i++)
	{
		scanf("%d",&order[i]);
	}
	sort(shops.begin(),shops.end());
	for(int i=0;i<m;i++)
	{
		int mid,right=shops.size()-1,left=0,minv=INFTY;
		while(left<=right)
		{
			mid=(left+right)/2;
			if(shops[mid]<order[i])
			{
				minv=min(minv,order[i]-shops[mid]);
				left=mid+1;
			}
			else
			{
				minv=min(minv,shops[mid]-order[i]);
				right=mid-1;	
			}
		}
		res+=minv;
	}
	printf("%d\n",res);
}

int main()
{
	while(true)
	{
		scanf("%d",&d);
		if(d==0)break;
		scanf("%d%d",&n,&m);
		solve();
	}
	return 0;
}


Measured memory_bytes: 3928
// Problem : A - Frog 1
// Contest : AtCoder - Educational DP Contest
// URL : https://atcoder.jp/contests/dp/tasks/dp_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define rev(x) x.rbegin(), x.rend()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)
#define endl '\n'
#define pi 3.141592653589793238
#define mp make_pair
#define pb push_back
#define precise cout<<fixed<<setprecision(20)
#define ff first
#define ss second
#define T int t;cin>>t;rep(mmm,0,t)
#define uniq(v) v.resize(distance(v.begin(),unique(all(v))))

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pair<int,int>> vii;

const int N=100001;
int mod=1000000007;
//mod=998244353;

int min(int a,int b){if(a<b) return a; else return b;}
int max(int a,int b){if(a>b) return a; else return b;}
int power(int a,int b){int res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int gcd(int p, int q){if(p%q==0) return q; else{return gcd(q,p%q);}} 
int mul(int a,int b){return ((a%mod)*(b%mod))%mod;}
int sub(int a,int b){return (((a-b)%mod)+mod)%mod;}

void solve()
{
	int n;
	cin>>n;
	int k;
	cin>>k;
	vi h(n);
	rep(i,0,n)
	cin>>h[i];
	vi dp(n,0);
	rep(i,1,n)
	{
		int m=INT_MAX;
		rep(j,i-k,i)
		{
			if(j<n&&j>=0)
			m=min(m,dp[j]+abs(h[j]-h[i]));
		}
		dp[i]=m;
	}
	cout<<dp[n-1];
}

signed main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

Measured memory_bytes: 4760