akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
typedef int64_t Int;

int main(){ 
    Int N;
    cin >> N;

    vector<pair<Int,Int>> infant;
    rep(i,N) {
        Int A;
        cin >> A;
        infant.push_back(make_pair(A,i));
    }

    sort(infant.begin(),infant.end());
    reverse(infant.begin(),infant.end());

    //rep(i,N) {
    //    cout << infant[i].first << infant[i].second << endl;
    //}

    vector<vector<Int>> dp(2010 ,vector<Int>(2010,0));
    Int ans = 0;

    rep(l,N) {
        rep(r,N) {
            if(l + r == N) {
                break;
            }
                dp[l+1][r] = max(dp[l+1][r], dp[l][r] + (abs(infant[l+r].second - l)) * infant[l+r].first);
                dp[l][r+1] = max(dp[l][r+1], dp[l][r] + (abs(infant[l+r].second - (N-r-1))) * infant[l+r].first);
        }
    }
    
    rep(l,N+1) {
        ans = max(ans, dp[l][N-l]);
    }


    cout << ans << endl;
}

Measured memory_bytes: 34940
def mul(a,b,p):
    return ((a % p) * (b % p)) % p

def div(a,b,p):
    return mul(a, power_func(b, p-2,p),p)

def power_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

modp = 1000000007
_ = input()
s = input()
d = dict()
for c in s:d[c] = d.get(c,0)+1

g = power_func(2,len(d),modp)
g = (g+modp-1) % modp

for c in sorted(d.keys()):
    subsubg = div((g+1)%modp,2,modp)
    subg = (subsubg % modp) * ((d[c]-1)%modp) % modp
    g = (g + subg) % modp
print(g)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using namespace std;

const int MAXN = 400002;
ll x[MAXN], t[MAXN];
bool l[MAXN];
bool r[MAXN];

int cnt;
int cl;
int cr;
int n;

void go(int x) {
    cnt = cl = cr = 0;
    cl = 0;

    for (int i = 0; i < x; ++i) {
        if (l[i]) {
            ++cl;
        } else if (r[i] && cl) {
            --cl;
            ++cnt;
        } 
    }

    for (int i = n - 1; i >= x; --i) {
        if (r[i]) {
            ++cr;
        } else if (l[i] && cr) {
            --cr;
            ++cnt;
        }
    }
}

int main() {
#ifdef PAUNSVOKNO
    freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(20); cout.tie(nullptr); cin.tie(nullptr);
  
    ll len;
    cin >> n >> len;
    ll d = 2 * len;
    ll ad = 0;

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

    for (int i = 0; i < n; ++i) {
        cin >> t[i];
        ad += (t[i] + d - 1) / d;
        ll k = t[i] % d;
        l[i] = k && (k <= 2 * x[i]);
        r[i] = k && (k <= 2 * (len - x[i]));
    }

    if (r[n - 1]) {
        l[n - 1] = r[n - 1] = false;
    } else {
        ++ad;
    }

    int ans = 0;
    int lg = 0, rg = n;
    while (lg <= rg) {
        int md = (lg + rg) / 2;
        go(md);
        if (cl < cr) {
            ans = max(ans, cl + cnt);
            lg = md + 1;
        } else {
            ans = max(ans, cr + cnt);
            rg = md - 1;
        }
    }


    cout << (ad - ans) * d << "\n";
    
}

Measured memory_bytes: 6400
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    map<string,int> a;
    for(int i=0;i<n;i++)
    {
        string s;
        cin>>s;
        a[s]++;
    }
    for(string s:{"AC","WA","TLE","RE"}) cout<<s<<" x "<<a[s]<<endl;
}

Measured memory_bytes: 3584
//T - Problem 20(indu)
#include <bits/stdc++.h>
using namespace std;

#define last 360

int main(){

    int angle{0};
    scanf("%d",&angle);
    
    int mul{last};
    
    for(int i = 1; i <= angle; i++){
        if(angle % i == 0 && last % i == 0){
            mul =(int) last/i;
        }
    }
    
    printf("%d\n",mul);
    
    return 0;
}

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

#define rep(i, b) for(int i = 0; i < b; i++)
#define repi(i, a, b) for(int i = a; i < b; i++)
#define all(c) c.begin(),c.end()
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define MAX_V 1001
#define MAX_E 401
#define INF INT_MAX
#define MOD 1000000007
#define EPS 1e-7
typedef long long ll;
inline int toInt(std::string s) { int v; std::istringstream sin(s); sin >> v; return v; }
template<class T> inline std::string toString(T x) { std::ostringstream sout; sout << x; return sout.str(); }
using namespace std;

typedef double D;      // 座標値の型。doubleかlong doubleを想定
typedef complex<D> P;  // Point
typedef pair<P, P> L;  // Line
#define X real()
#define Y imag()

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

	rep(i, s.size())
	{
		if (s[i] == 'a' && i != s.size() - 1)
		{
			continue;
		}

		if (ll('z' - s[i]) + 1 <= k && i != s.size()-1)
		{
			k = k - (ll('z' - s[i]) + 1);
			s[i] = 'a';
		}
		else if(i == s.size() - 1){
			k = k % 26;
			if ('z' - s[i] < k)
			{
				s[i] = 'a' + (k - ('z' - s[i]) - 1);
			}
			else{
				s[i] = s[i] + k;
			}
		}
	}
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 512
#include <cstdio>
#include <algorithm>
#include <map>
typedef long long ll;
#define PII pair<ll, ll>
#define T second
#define D first
using namespace std;

ll n, k, sum, ans;
PII a[100005];
map<ll, ll> mp;
int main() {
	ll i, j, sz;
	scanf("%lld%lld", &n, &k);
	for(i=0; i<n; i++) scanf("%lld%lld", &a[i].T, &a[i].D);
	sort(a, a+n, greater<PII>());
	for(i=0; i<k; i++) {
		mp[a[i].T]++;
		sum += a[i].D;
	}
	sz = mp.size();
	ans = sum + sz *sz;
	j = k - 1;
	for(; i<n; i++) {
		if(mp.count(a[i].T)) continue;
		mp[a[i].T]++;
		while(j>=0 && mp[a[j].T]==1) j--;
		if(j<0) break;
		sum += a[i].D - a[j].D;
		mp[a[j].T]--;
		j--;
		sz = mp.size();
		ans = max(ans, sum + sz * sz);
	}
	printf("%lld", ans);
	return 0;
}

Measured memory_bytes: 5760
#include <stdio.h>
#include <limits.h>
typedef unsigned int uint;

inline static uint gl(void){
    uint x = 0;
    for(;;){
        const uint c = getchar_unlocked() - 48;
        if(c < 10){
            x = x*10 + c;
        }else{
            break;
        }
    }
    return x;
}
#define H 200000
uint v[H];
int main(void){
    const uint h = gl();
    gl();
    const uint n = gl();
    for(uint i=0; i<H; i++){ v[i] = H; }
    for(uint i=0; i<n; i++){
        const uint x = gl()-1;
        const uint y = gl()-1;
        v[x] = y<v[x] ? y : v[x];
    }
    uint right = 0;
    for(uint x=1; x<h; x++){
        const auto b = v[x];
        const auto r = right+1;
        if(b<r){
            printf("%d\n", x);
            return 0;
        }else if(b>r){
            right=r;
        }
    }
    printf("%d\n", h);
    return 0;
}


Measured memory_bytes: 896
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getInts(N int) []int {
	ret := make([]int, N)
	for i := 0; i < N; i++ {
		ret[i] = getInt()
	}
	return ret
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

type pair struct {
	x, y int
}

func main() {
	sc.Split(bufio.ScanWords)
	N := getInt()
	a := make([]int, 0)
	for i := 0; i < N; i++ {
		x := getInt()
		a = append(a, x)
	}
	s := make([]pair, 0)
	sort.Ints(a)
	mi := a[0]
	ma := a[N-1]
	a = a[1 : N-1]
	for _, e := range a {
		if e >= 0 {
			s = append(s, pair{mi, e})
			mi -= e
		} else {
			s = append(s, pair{ma, e})
			ma -= e
		}
	}

	s = append(s, pair{ma, mi})
	w := bufio.NewWriter(os.Stdout)
	defer w.Flush()
	fmt.Fprintln(w, ma-mi)
	for _, e := range s {
		fmt.Fprintln(w, e.x, e.y)
	}
}


Measured memory_bytes: 10652
n = gets.to_i
s = n.times.map{gets}.group_by{|t|t[0]}

ans = 0

b = [?M,?A,?R,?C,?H].map{|c|
  a = 0
  if s[c]
    a =  s[c].size
  end
  a
}

b.combination(3){|x|
  ans += x.inject(:*)
}

p ans

Measured memory_bytes: 10620
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>
const long long mod = 1000000007;


int main() {
	int M1, M2, D1, D2;
	scanf("%d %d", &M1, &D1);
	scanf("%d %d", &M2, &D2);
	printf(M1 == M2 ? "0" : "1");
	return 0;
}

Measured memory_bytes: 128
/* ADLS1_5_B:Merge Sort */
/* 20181119 */

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define N 500000

int cnt;
int L[N / 2 + 1], R[N / 2 + 1];

void mergeSort(int *A, int n, int left, int right);
void merge(int *A, int left, int mid, int right);

int main(void) {
	int n, i;
	//int *A = (int *)malloc(sizeof(int) * N);
	int A[N];

	cnt = 0;

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

	mergeSort(A, n, 0, n);
	
	i = 0;
	while(i < n) {
		if(i) printf(" ");
		printf("%d", A[i++]);
	}
	printf("\n%d\n", cnt);

	return 0;
}

void mergeSort(int *A, int n, int left, int right) {
	int mid;

	if(left + 1 < right) {
		mid = (left + right) / 2;
		mergeSort(A, n, left, mid);
		mergeSort(A, n, mid, right);
		merge(A, left, mid, right);
	}
}

void merge(int *A, int left, int mid, int right){
	int n1 = mid - left;
	int n2 = right - mid;
	int i, j, k;

	i = j = 0;
	while(i < n1) {
		L[i] = A[left + i];
		i++;
	}
	while(j < n2) {
		R[j] = A[mid + j];
		j++;
	}

	i = j = 0;
	L[n1] = INT_MAX;
	R[n2] = INT_MAX;
	for(k = left; k < right; k++) {
		if(L[i] <= R[j]) {
			A[k] = L[i++];
		}else {
			A[k] = R[j++];
		}
		cnt++;
	}
}


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

int main(int argc, const char * argv[]) {
    string s;
    int n;
    cin >> s >> n;
    string answerS = s;
    for(int i=0;i<s.size();i++){
        int tempNum = s[i] - 'a';
        int needNum = 26 - tempNum;
        if(s[i] == 'a'){
            continue;
        }else if(needNum <= n){
            answerS[i] = 'a';
            n -= needNum;
        }
//        }else if(i+1 == s.size()){
//            int changeNum = n % 26;
//            answerS[i] += changeNum;
//        }
    }
    int changeNum = n % 26;
    answerS[s.size()-1] += changeNum;
    cout << answerS << endl;
    
//    string test = "abcdefg";
//    for(int i=0;i<test.size();i++){
//        cout << test[i] - 'a';
//    }
//    cout << 'z' - 'a';
    
    return 0;
}

Measured memory_bytes: 640
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public final class Main {

    public static void main(String[] args) {
        final FastScanner fs = new FastScanner();
        final String s = fs.next();

        if(s.endsWith("s")) {
        	System.out.print(s+"es");

        }else {
        	System.out.print(s+"s");
        }
    }
   static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next() {
            while (!st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    //noinspection CallToPrintStackTrace
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

        int[] readArray(int n) {
            final int[] a = new int[n];
            for (int i = 0; i < n; i++) { a[i] = nextInt(); }
            return a;
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}

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

int main() {
  int A, B;
  cin >> A >> B;

  int N = 1, ans = 0;
  while (N < B) {
    N += A - 1;
    ans += 1;
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))

char s[9000];
ll d[9000];
ll xx[20000],*x=xx+10000;
ll yy[20000],*y=yy+10000;
ll tt[20000],*t=tt+10000;

int main(){
	scanf("%s",s);
	int len=strlen(s);
	
	int cnt=0;
	rep(i,0,len){
		if(s[i]=='F')d[cnt]++;
		else cnt++;
	}
	cnt++;
	
	x[d[0]]=1;
	repp(i,2,cnt,2)if(d[i]){
		//x
		rep(k,-8500,8500){
			t[k]=0;
			if(abs(k+d[i])<8500)t[k]|=x[k+d[i]];
			if(abs(k-d[i])<8500)t[k]|=x[k-d[i]];
		}
		rep(k,-8500,8500)x[k]=t[k];
	}
	
	y[0]=1;
	repp(i,1,cnt,2)if(d[i]){
		//y
		rep(k,-8500,8500){
			t[k]=0;
			if(abs(k+d[i])<8500)t[k]|=y[k+d[i]];
			if(abs(k-d[i])<8500)t[k]|=y[k-d[i]];
		}
		rep(k,-8500,8500)y[k]=t[k];
	}
		
	int p,q;
	scanf("%d%d",&p,&q);
	puts(x[p]&y[q]?"Yes":"No");
	return 0;
}

Measured memory_bytes: 640
#pragma region kyomukyomupurin

/**
 *    author  : 𝒌𝒚𝒐𝒎𝒖𝒌𝒚𝒐𝒎𝒖𝒑𝒖𝒓𝒊𝒏
 *    created : 2020-05-10 22:41:32
 **/

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <complex>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

using int64 = long long;

template <class T>
using binary_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template <class T, class U>
std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) {
  return os << '(' << p.first << ", " << p.second << ')';
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
  int flag = 0;
  for (auto e : vec) os << (flag++ ? ", " : "{") << e;
  return os << (vec.empty() ? "{}" : "}");
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& st) {
  int flag = 0;
  for (auto e : st) os << (flag++ ? ", " : "{") << e;
  return os << (st.empty() ? "{}" : "}");
}

template <class T, class U>
std::ostream& operator<<(std::ostream& os, const std::map<T, U>& mp) {
  int flag = 0;
  for (auto e : mp) os << (flag++ ? ", " : "{") << e;
  return os << (mp.empty() ? "{}" : "}");
}

template <class T>
std::istream& operator>>(std::istream& is, std::vector<T>& vec) {
  for (T& e : vec) is >> e;
  return is;
}

#define all(_) begin(_), end(_)
#define rall(_) rbegin(_), rend(_)

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

void debug_out() { std::cerr << '\n'; }

template <class Head, class... Tail>
void debug_out(Head&& head, Tail&&... tail) {
  std::cerr << head;
  if (sizeof...(Tail) != 0) std::cerr << ", ";
  debug_out(std::forward<Tail>(tail)...);
}

#pragma endregion kyomukyomupurin

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

  string s, t; cin >> s >> t;
  string t2 = t.substr(0, t.size() - 1);

  if (s == t2) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}

Measured memory_bytes: 3640
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int ans,h,w,dp[3005][3005][2][2],r[3005][3005],u[3005][3005];
char s[3005][3005];
int main(void){
    scanf("%d%d",&h,&w);
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            scanf(" %c",&s[i][j]);
            if(i-2>=0&&s[i-2][j]=='R'&&s[i-1][j]=='G'&&s[i][j]=='W')u[i-2][j]=1;
            if(j-2>=0&&s[i][j-2]=='R'&&s[i][j-1]=='G'&&s[i][j]=='W')r[i][j-2]=1;
        }
    }
    for(int i=0;i<h;i++){
        for(int j=1;j<w;j++){
            dp[i+1][j-1][0][0]=max(dp[i][j][0][1],dp[i][j][0][0]+r[i][j]);
            dp[i+1][j-1][1][0]=max(dp[i][j][0][1],dp[i][j][0][0])+u[i][j];
            dp[i+1][j-1][0][1]=max(dp[i][j][1][0],dp[i][j][1][1]);
            dp[i+1][j-1][1][1]=max(dp[i][j][1][0],dp[i][j][1][1])+u[i][j];
        }
        ans+=max(max(max(dp[i][0][0][0],dp[i][0][0][1]),max(dp[i][0][1][0],dp[i][0][1][1]))+u[i][0],dp[i][0][0][0]+r[i][0]);
    }
    for(int j=0;j<w;j++)ans+=dp[h][j][0][0];
    printf("%d\n",ans);
}



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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod= int(1e9)+7;
using P = pair<ll,ll>;
using ld=long double;


int main(){
    int n,m;cin >>n>>m;
    n--;m--;
    int ans=n*m;
    cout <<ans <<endl;
    return 0;
}

Measured memory_bytes: 3580
#include<iostream>
using namespace std;
#define RENT 100000
int main(){
	int n;
	while(cin>>n){
		int ans;
		ans=RENT;
		for(int i=0;i<n;i++){
			ans=ans*1.05;
			if(ans%1000>0){
				ans=ans+1000-ans%1000;
			}
		}
		
		
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 1160
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define TRACE(x) cerr << #x << " = " << x << endl
#define REP(i, n) for (int i=0; i<n; i++)
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define _ << " " <<

typedef long long ll;
typedef pair<int, int> P;
#define X first
#define Y second

const int MAX = 1<<19;

int bio[MAX];
vector <int> V[MAX];
int ok=1;

int dfs(int x, int pr) { //vraca 1 ako treba spojit
  int treba = 0;
  for (auto it : V[x])
    if (it != pr) treba += dfs(it, x);  

  if (treba > 1) ok = 0;
  if (treba) return 0;
  return 1;
}

int main()
{
  int n;
  scanf("%d", &n);

  REP(i, n-1) {
    int a, b;
    scanf("%d%d", &a, &b); a--; b--;
    V[a].push_back(b);
    V[b].push_back(a);
  }

  ok &= (!dfs(0, -1));
  printf("%s\n", (!ok) ? "First" : "Second");

  return 0;
}


Measured memory_bytes: 17792
// B

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cassert>
#include <cinttypes>
const double EPS = 1e-10;
#define equals(a,b) (fabs((a) - (b)) < EPS)

using namespace std;

typedef int64_t ll;
typedef uint64_t ull;

typedef pair<ll, ll> P;
inline P operator+(const P& p1, const P& p2) {
  return P(p1.first + p2.first, p1.second + p2.second);
}

struct Point {
  double x,y;
  Point operator - (const Point& p){ return Point{x - p.x, y - p.y};}
};

typedef Point Vector;

double cross(Vector a, Vector b){return a.x*b.y - a.y*b.x;}
bool isParallel(Vector a, Vector b) {
  return equals(cross(a,b), 0.0);
}
bool isParallel(Point a1, Point a2, Point b1, Point b2) {
  return isParallel(a1-a2, b1-b2);
}

int M;
Point p[20];
bool ispara[20][20][20][20];
int seg[8];
int ans;


void dfs(int depth){
  if (depth == M / 2) {
    int res = 0;
    for (int i = 0; i < M / 2; i++) {
      int i_p[2], ct = 0;
      for(int bit = 0; bit < M && ct < 2; bit++){
        if(seg[i] & (1 << bit)){
          i_p[ct++] = bit;
        }
      }
      for (int j = i + 1; j < M / 2; j++) {
        int j_p[2], jct = 0;
        for(int bit = 0; bit < M && jct < 2; bit++){
          if(seg[j] & (1 << bit)){
            j_p[jct++] = bit;
          }
        }
        if(ispara[i_p[0]][i_p[1]][j_p[0]][j_p[1]]) res++;
      }
    }
    ans = max(res, ans);
    return;
  }
  int i = 0;
  if (depth > 0) {
    while(true){
      bool isinc = false;
      for (int j = 0; j < depth; j++) {
        if (seg[j] & (1 << i)){
          isinc = true;
          break;
        }
      }
      if(isinc) i++;
      else break;
    }
  }
  seg[depth] |= (1 << i);
  for (int j = i + 1; j < M; j++) {
    bool isinc = false;
    for (int k = 0; k < depth; k++) {
      if (seg[k] & (1 << j)){
        isinc = true;
        break;
      }
    }
    if(isinc) continue;
    seg[depth] |= (1 << j);
    dfs(depth + 1);
    seg[depth] ^= (1 << j);
  }
  seg[depth] ^= (1 << i);
}

int main() {
  cin.tie(0), cout.tie(0);
  ios::sync_with_stdio(false);
  cin >> M;
  for(int i = 0; i < M; i++) cin >> p[i].x >> p[i].y;

  for (int i = 0; i < M; i++) {
    for (int j = 0; j < M; j++) {
      if(i == j) continue;
      for (int k = 0; k < M; k++) {
        if(k == j || k == i) continue;
        for (int l = 0; l < M; l++) {
          if(i == l || j == l || k == l) continue;
          ispara[i][j][k][l] = isParallel(p[i], p[j], p[k], p[l]);
        }
      }
    }
  }
  dfs(0);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3376
n=int(input())
a,b,c=[list(map(int,input().split())) for _ in range(3)] 
x=0
for i,_ in enumerate(a):
  if(i==len(a)-1):
    break
  elif(a[i]+1==a[i+1]):
    x+=c[a[i]-1]
print(sum(b)+x)

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

int main(void) {
  int A, B;
  cin >> A >> B;

  for (int i = 0; i < 1000000; i++) {
    int eight = int(i * 0.08);
    int ten = int(i * 0.1);
    if (eight == A && ten == B) {
      cout << i << endl;
      return 0;
    }
  }

  cout << -1 << endl;
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100010
int d,g,c[N],p[N],ans=1000000,vis[N];
void find(){
	int sum=0,ans1=0;
	for(int i=1;i<=d;i++){
		if(vis[i]){
			ans1+=c[i];
			sum+=p[i]+c[i]*100*i;
		}
	}
	if(sum>=g){
		ans=min(ans1,ans);return;
	}
	for(int i=d;i;i--){
		if(vis[i])continue;
		int t=c[i];
		while(t>1){
			t--;
			ans1++;
			sum+=100*i;
			if(sum>=g){
				ans=min(ans1,ans);
				return;
			}
		}
	}
}
void dfs(int x){
	if(x==d+1){find();return;}
	vis[x]=1;dfs(x+1);
	vis[x]=0;dfs(x+1);
}
int main(){
	scanf("%d%d",&d,&g);
	for(int i=1;i<=d;i++)
		scanf("%d%d",&c[i],&p[i]);
	dfs(1);
	printf("%d\n",ans);
}

Measured memory_bytes: 128
using System;
using System.Linq;

class Program
{
    static int N;
    static int A;
    static int B;
    static long[] v;

    static void Main()
    {
        /*入力の受け取り*/
        int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
        N = input[0];
        A = input[1];
        B = input[2];
        v = Console.ReadLine().Split().Select(long.Parse).ToArray();

        /*vの大きいほうからA個の平均が最大値*/
        Array.Sort(v);
        Array.Reverse(v); //vを降順に
        long sum = 0;
        for (int i = 0; i < A; i++)
            sum += v[i];
        Console.WriteLine(sum / (double)A);

        /*v[0]から同じ値がA個以上続いている場合を別処理*/
        if (v[A - 1] == v[0])
        {
            int M = 1;
            for (int i = 1; ; i++)
            {
                if (i >= N || v[i] != v[i - 1])
                    break;
                M++;
            }
            long ans = 0;
            for (int i = A; i <= B; i++)
                ans += Comb(M, i);
            Console.WriteLine(ans);
            return;
        }

        /* v中にv[A-1]と等しいものがp個、vの大きいほうからA個の中にv[A-1]と等しい
           ものがq個あるとすると、pCqが答え*/
        long va = v[A - 1];
        int p = v.Select(s => s == va ? 1 : 0).ToArray().Sum();
        int q = 0;
        for (int i = 0; i < A; i++)
            q += v[i] == va ? 1 : 0;
        Console.WriteLine(Comb(p, q));
    }

    static long Comb(int a, int b) //aCbを計算
    {
        if (b > a) return 0;
        if (b > a / 2) b = a - b;
        long v = 1;
        int k = 1;
        for (int i = 0; i < b; i++)
        {
            v *= a - i;
            while (k <= b && v % k == 0)
            {
                v /= k;
                k++;
            }
        }
        return v;
    }
}


Measured memory_bytes: 13524
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <math.h> 
#include <iomanip>
#include <string.h>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
#define PI 3.14159265358979323846264338327950L

#define INF 0x3f3f3f3f
//const int N = 2e5 + 5;
  
 
int32_t  main() {

	IOS;

	int X;

	cin >> X;
	 
	for (int i = -2000; i <= 2000; i++) {

		for (int j = -2000; j <= 2000; j++) {

			int A = pow(i, 5);
			int B = pow(j, 5);

			if ((A - B) == X) {

				cout << i << " " << j << endl;
				return 0;
			}


		}


	}


}


Measured memory_bytes: 3704
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;

int main(){
  int X;
	cin >> X;
	int tmp;
	int max = 1;
	for(int i=2;i<sqrt(X);i++){
		for(int j=2;pow(i,j)<=X;j++){
			tmp = pow(i,j);
		  if(tmp<=X && max<tmp){
			  max = tmp;
		  }
		}
	}
	cout << max << endl;
	return 0;
}


Measured memory_bytes: 512
import java.util.Scanner;
public class Main {
	public static void main(String[] args) throws Exception{
		Scanner sc = new Scanner (System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		int s[][]=new int[n][m];
		for(int i=0;i<n;i++) {
			String c=sc.next();
			for(int j=0;j<m;j++)
				if(c.substring(j,j+1).equals("#"))s[i][j]=-1;
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(s[i][j]==-1) {
					for(int y=i-1;y<=i+1;y++) {
						for(int x=j-1;x<=j+1;x++) {
							if(y>=0&&y<n&&x>=0&&x<m) {
								if(s[y][x]>-1)s[y][x]++;
							}
						}
					}
				}
			}
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) System.out.print(s[i][j]<0?"#":s[i][j]);
			System.out.println();
		}
	}
}


Measured memory_bytes: 25172
//78B
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
using namespace std;
int main(void){
    int d, width, space;
    int cnt =0;
    cin >> d >> width >>space;
    while(true){
        d-=(width + space);
        //cout << d<< endl;
        if(d>=space){
            cnt+=1;
        }else{
            break;
        }
        
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
/**
 *      author  : 𝒌𝒚𝒐𝒎𝒖𝒌𝒚𝒐𝒎𝒖𝒑𝒖𝒓𝒊𝒏
 *      created : 2019-11-29 12:49:39
**/

#include <iostream>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
#include <bitset>
#include <cassert>
#include <cctype>
#include <functional>
#include <iomanip>
#include <random>
#include <utility>

using namespace std;

using int64 = long long;
#define debug(_) cerr << #_ << ": " << (_) << '\n'
template<typename T> inline void chmin(T &a, T b) { if (a > b) a = b; return; }
template<typename T> inline void chmax(T &a, T b) { if (a < b) a = b; return; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& vec) { os << '{'; for (size_t i = 0; i < vec.size(); ++i) { os << vec[i]; if (i != vec.size() - 1) os << ','; } os << '}'; return os; }
template<typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p) { return os << '{' << p.first << " " << p.second << '}'; }

int64 dp[55][5050];
// dp[i][j] : i 枚目まで使って総和が 2500 - j になる組み合わせの総数

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

  int n, a; cin >> n >> a;
  vector<int> x(n);
  for (int i = 0; i < n; ++i) {
    cin >> x[i];
    x[i] -= a;
  }

  dp[0][2500] = 1LL;

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= 5000; ++j) {
      if (j - x[i] < 0 || j - x[i] > 5000) {
        dp[i + 1][j] = dp[i][j];
      } else {
        dp[i + 1][j] = dp[i][j] + dp[i][j - x[i]];
      }
    }
  }

  cout << dp[n][2500] - 1LL << endl;

  return 0;
}

Measured memory_bytes: 2304
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100;
const int MAX_GN = MAX_N + 9;

const long long LLINF = 1LL << 62;

const string wdnames[] = {
  "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"
};

/* typedef */

typedef long long ll;

struct Edge {
  int ui, vi;
  ll c;
  Edge(int _ui, int _vi, ll _c): ui(_ui), vi(_vi), c(_c) {}
};

typedef vector<Edge> ve;

/* global variables */

int n, gn, st, gl;
ll w, sumti;
map<string,int> wdnhash;
ve nbrs[MAX_GN];
ll minfs[MAX_GN], flows[MAX_GN][MAX_GN];
int prvs[MAX_GN];

/* subroutines */

/* main */

int main() {
  for (int i = 0; i < 7; i++) wdnhash[wdnames[i]] = i;

  for (;;) {
    cin >> n >> w;
    if (n == 0) break;

    gn = n + 9;
    st = n + 7;
    gl = n + 8;

    for (int i = 0; i < gn; i++) nbrs[i].clear();
    sumti = 0;
    
    for (int i = 0; i < n; i++) {
      ll ti;
      int ci;
      cin >> ti >> ci;

      sumti += ti;
      nbrs[st].push_back(Edge(st, i, ti));

      for (int j = 0; j < ci; j++) {
	string wdname;
	cin >> wdname;
	int wj = n + wdnhash[wdname];

	nbrs[i].push_back(Edge(i, wj, LLINF));
	nbrs[wj].push_back(Edge(wj, i, 0));
      }
    }

    for (int i = 0; i < 7; i++)
      nbrs[n + i].push_back(Edge(n + i, gl, w));

    memset(flows, 0, sizeof(flows));
    ll max_flow = 0;

    for (;;) {
      //printf("max_flow = %lld\n", max_flow);

      memset(prvs, -1, sizeof(prvs));
      prvs[st] = st;
      minfs[st] = LLINF;

      queue<int> q;
      q.push(st);

      while (! q.empty()) {
	int ui = q.front(); q.pop();

	if (ui == gl) break;

	ve& nbru = nbrs[ui];
	for (ve::iterator vit = nbru.begin(); vit != nbru.end(); vit++) {
	  int vi = vit->vi;
	  ll vc = vit->c - flows[ui][vi];
	  if (prvs[vi] < 0 && vc > 0) {
	    prvs[vi] = ui;
	    minfs[vi] = (minfs[ui] < vc) ? minfs[ui] : vc;
	    q.push(vi);
	  }
	}
      }

      if (prvs[gl] < 0) break;
      ll min_flow = minfs[gl];

      for (int j = gl; j != st;) {
	int i = prvs[j];
	flows[i][j] += min_flow;
	flows[j][i] -= min_flow;
	j = i;
      }

      max_flow += min_flow;
    }

    cout << (max_flow >= sumti ? "Yes" : "No") << endl;
  }

  return 0;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;

string s;

int n;

bool check(int a, int b) {
    vector <int> dp(n);
    dp[a] = 1;
    for (int i = a; i < n; ++i) {
        if (i + 1 < n && s[i + 1] == '.') dp[i + 1] |= dp[i];
        if (i + 2 < n && s[i + 2] == '.') dp[i + 2] |= dp[i];
    }
    return dp[b];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int a, b, c, d;
    cin >> n >> a >> b >> c >> d;
    --a, --b, --c, --d;
    cin >> s;
    if (!check(a, c) || !check(b, d))  {
        cout << "No\n";
        return 0;
    }
    if (d < c) {
        bool fl = false;
        for (int i = b - 1; i + 3 <= min(n, d + 2); ++i) {
            fl |= (s[i] == '.' && s[i + 1] == '.' && s[i + 2] == '.');
        }
        if (!fl) {
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
}

Measured memory_bytes: 1360
#include <stdio.h>

int main(void) {
  int N, M;
  scanf("%d %d", &N, &M);
  int H = M / N;

  int pos = 0;
  int max = 0;
  for(int i = 1; i*i <= M; i++) {
    if(M % i == 0) {
      int k = M / i;
      if(max < i && i <= H) max = i;
      if(max < k && k <= H) max = k;
      if(k <= (i+1)) break;
    }
  }

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

  return 0;
}


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

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

    map<int, int> m;
    for(int i=0; i<M; ++i) {
        int a, b;
        cin >> a >> b;
        if (m.find(a) == m.end()) {
            m[a] = 1;
        }
        else ++m[a];
        if (m.find(b) == m.end()) {
            m[b] = 1;
        }
        else ++m[b];
    }

    for(int i=1; i<=N; ++i) {
        cout << m[i] << endl; 
    }

}

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

public class Main {
	static int[] dish;
	static boolean[] used;
	static int min;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		dish = new int[5];
		for (int i = 0; i < 5; i++) {
			dish[i] = sc.nextInt();
		}
		used = new boolean[5];
		min = 100000000;
		dfs(0, 0);
		System.out.println(min);
	}
	static void dfs(int count, double time) {
		if (count == 5) {
			min = Math.min(min, (int) time);
			return;
		}
		for (int i = 0; i < 5; i++) {
			if (!used[i]) {
				used[i] = true;
				dfs(count + 1, Math.ceil(time / 10) * 10 + dish[i]);
				used[i] = false;
			}
		}
	}
}

Measured memory_bytes: 21844
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
M = 10**9+7
### 約数列挙
def fs(n):
    s = set()
    for i in range(1,int(n**0.5)+2):
        if n%i==0:
            s.add(i)
            s.add(n//i)
    l = sorted(list(s))
    return l
ds = fs(n)
m = len(ds)
nums = [None]*m
for i in range(m):
    val = pow(k, (ds[i]+1)//2, M)
    for j in range(i):
        if ds[i]%ds[j]==0:
            val -= nums[j]
            val %= M
    nums[i] = val%M
ans = 0
inv2 = pow(2, M-2, M)
for i in range(m):
    if ds[i]%2==0:
        ans += ds[i]*nums[i]*inv2
    else:
        ans += ds[i]*nums[i]
    ans %= M
print(ans%M)

Measured memory_bytes: 69048
//#include <bits/stdc++.h>
#include<iostream>
#include <iosfwd>
#include<limits.h>
#include <sstream>
#include <iomanip>
#include <iterator>
#include <algorithm>
#include <limits>
#include<stdio.h>
#include <queue>
#include <stack>
#include <math.h>
#include<string.h>
#include <unordered_map>
#include <map>
#include <unordered_set>
#include <set>
#include<vector>
#include <chrono>
#include <random>
using namespace std;
using namespace std::chrono;
#define fr(i,j,n)   for(lli i=j;i<(n);++i)
#define bk(i,j,n)   for(lli i=j;i>=n;--i)
#define pb push_back
#define m_p make_pair
#define Fs first
#define Sc second
#define endl "\n"
#define MOD 2147483647
#define present(c,x)    ((c).find(x) != (c).end())
#define run ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ordered_set tree<lli, null_type,less<lli>, rb_tree_tag,tree_order_statistics_node_update>
#define debug1(x) cout<<#x<<" "<<x<<endl;
#define debug2(x,y) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<endl;
#define debug3(x,y,z) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<endl;
#define mem(p,v) memset(p,(lli)v,sizeof p);
#define ub upper_bound
#define lb lower_bound
typedef long long int lli;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<lli> vl;
typedef pair<lli,lli> pl;
inline lli max(lli a,lli b){ return a>b?a:b;}
inline lli min(lli a,lli b){ return a<b?a:b;}
void show(vector<lli> v)
{
    fr(i,0,v.size())
    cout<<v[i]<<" ";
    cout<<endl;
}
void show(vector<int> v)
{
    fr(i,0,v.size())
    cout<<v[i]<<" ";
    cout<<endl;
}
void show(int a[], int arraysize)
{
    for (int i = 0; i < arraysize; ++i)
        cout << a[i] << " ";
    cout<<endl;
}
void show(lli a[], lli arraysize)
{
    for (lli i = 0; i < arraysize; ++i)
        cout << a[i] << " ";
    cout<<endl;
}
void show(unordered_set<int> s)
{
    for (auto it = s.begin(); it != s.end(); it++)
    {
        cout << *it << " ";
    }
    cout<<endl;
}
void show(unordered_map<int,int> mp)
{
    for (auto it = mp.begin(); it != mp.end(); it++)
    {
        cout << it->first << " "<<it->second<<endl;
    }
    cout<<endl;
}
int main()
{
    lli t,n,m,q;
    t=1;
    while(t)
    {
        cin>>n;
        lli s=0;
        lli a[n];
        unordered_map<lli, lli> mp;
        fr(i,0,n)
        {
            cin>>a[i];
            mp[a[i]]++;
            s+=a[i];
        }
        cin>>q;
        lli b,x,c;
        fr(i,0,q)
        {
            cin>>b>>c;
            x=mp[b];
            s=s+x*(c-b);
            mp[b]=0;
            mp[c]+=x;
            cout<<s<<endl;
        }
        t--;
    }
    return 0;
}





Measured memory_bytes: 7888
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef long long ll;
ll p10[19];
using State = tuple<ll,int,bool>;
map<State,ll> mp;
ll solve(ll D,int b,bool cany0){
	State st=State{D,b,cany0};
	if(mp.count(st)) return mp[st];

	if(b==-1){
		if(D==0) return 1;
		return 0;
	}
	if(b==0){
		if(D==0) return 10;
		return 0;
	}
	ll res = 0;
	rep(x,10){
		rep(y,10){
			if(!cany0 && y==0) continue;
			if((x+D%10+10)%10!=y) continue;
			ll nD = D+(x-y)*(1-p10[b]);
			assert(nD%10==0);
			nD/=10;
			res += solve(nD,b-2,true);
		}
	}
	return mp[st] = res;
}
int main(){
	p10[0]=1;
	rep(i,18) p10[i+1] = p10[i]*10;
	ll D;
	cin>>D;
	ll ans = 0;
	rep1(i,18) ans += solve(D,i,0);
	cout<<ans<<endl;
}


Measured memory_bytes: 384
#include <iostream>
#include <iomanip>
#include <climits>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#include <unordered_map>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <random>
#define _USE_MATH_DEFINES
#include <math.h>

using namespace std;

#define INF (int)1e8
#define _INF (int)-1e8
#define INFLL (long long)1e15
#define _INFLL (long long)-1e15
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
#define bitmanip(m,val) static_cast<bitset<(int)m>>(val)
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<int, int> P;

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


typedef ll seg_t;

class SegTree {
private:
	int n;
	vector<seg_t> segtree;
	seg_t exc;
	seg_t (*build_rule)(seg_t, seg_t);
	seg_t build_seg(int k) {
		int l = k * 2 + 1, r = k * 2 + 2;
		return build_rule(segtree[l], segtree[r]);
	}
	seg_t find_rule(int s, int t, int l, int r, int k) {
		if (s == l&&t == r) return segtree[k];
		else {
			int mid = (l + r) / 2;
			if (s < mid&&mid < t) {
				seg_t result1 = find_rule(s, mid, l, mid, k * 2 + 1);
				seg_t result2 = find_rule(mid, t, mid, r, k * 2 + 2);
				return build_rule(result1, result2);
			}
			else if (s < mid) {
				return find_rule(s, t, l, mid, k * 2 + 1);
			}
			else if (mid < t) {
				return find_rule(s, t, mid, r, k * 2 + 2);
			}
		}
	}
public:
	SegTree(vector<seg_t> a, seg_t init, seg_t (*f)(seg_t, seg_t)) {
		n = (ll)pow(2, ceil(log2(a.size())));
		segtree = vector<seg_t>(n * 2 - 1, init);
		exc = init;
		build_rule = f;
		Loop(i, a.size()) segtree[n - 1 + i] = a[i];
		Loopr(i, n - 1) segtree[i] = build_seg(i);
	}
	void update(int k, seg_t x) {
		k += n - 1;
		segtree[k] = x;
		while (k > 0) {
			k = (k - 1) / 2;
			segtree[k] = build_seg(k);
		}
	}
	seg_t search(int s, int t) {
		if (s == t) return exc;
		return find_rule(s, t, 0, n, 0);
	}
};

seg_t seg_build_rule(seg_t a, seg_t b) {
	return min(a, b);
}

int main() {
	int n; cin >> n;
	int q; cin >> q;
	vector<seg_t> a(n, INT_MAX);
	SegTree segtree(a, INT_MAX, seg_build_rule);
	Loop(i, q) {
		int c, x, y; cin >> c >> x >> y;
		if (c == 0) {
			segtree.update(x, y);
		}
		else {
			cout << segtree.search(x, y + 1) << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 6812
#include <iostream>
#include <algorithm>
#include <functional>
#include<vector>
#include<math.h>
#include<bitset>
#include<string>
#include <deque>
#include<queue>
#include<map>
using namespace std;

int main() {
	long long int a,b;
	cin >> a>>b;
	long long int Y = 0;
	long long int X = 0;
	for (int i = 0; i<=999; i++) {
		Y += i;
		X += i + 1;
		for (long int k = 0; a+k<=Y&&a+k<=X; k++) {
			if (a + k == Y && b + k == X) {
				cout << k << endl;
				goto go;
			}
		}
	}
go:;
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define pb push_back
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

int main() {//LR・・RLの部分をひっくり返す。
  int n,k;
  cin>>n>>k;
  string s;
  cin>>s;
  //////////////
  int ans=0;//同じ文字が続いている回数
  int change=0;//l->r or r->l になっている回数
  rep(i,0,n-1){
    if(s[i]==s[i+1])ans++;
    else change++;
  }
  rep(i,0,k){
   if(change==0||change==1){
     ans=n-1;
     break;
   }
    else{
     ans+=2;
      change-=2;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3740
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<bool> vb;
typedef vector<char> vc;
// #define INF __INT32_MAX__
#define INF 1e9
#define LINF __LONG_LONG_MAX__

int main() {
    int H, W; cin >> H >> W;
    vector<vc> S(H, vc(W));
    int cnt = 0;
    rep(i, H) {
        rep(j, W) {
            cin >> S[i][j];
            if (S[i][j] == '.') cnt++;
        }
    }

    vector<vi> mp = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    vector<vi> route(H, vi(W, INF));
    route[0][0] = 1;
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    while (!q.empty()) {
        pair<int, int> p = q.front(); q.pop();
        
        int ux = p.first; int uy = p.second;

        if (S[ux][uy] == '#') continue;
        S[ux][uy] = '#';

        for (int i = 0; i < 4; i++) {
            int vx = ux + mp[i][0];
            int vy = uy + mp[i][1];
            if (vx >= 0 && vx < H && vy >= 0 && vy < W && S[vx][vy] != '#') {
                q.push(make_pair(vx, vy));
                route[vx][vy] = min(route[vx][vy], route[ux][uy] + 1);
            }
        }
    }

    if (S[H - 1][W - 1] == '.') {
        cout << -1 << endl;
    } else {
        int d = route[H - 1][W - 1];
        cout << (cnt - d) << endl;
    }
}


Measured memory_bytes: 3636
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
constexpr int MOD=1000000007;
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(lint (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(lint (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
#define fi first
#define se second
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
const int MAX_N=2e5+5;

lint solve(lint from,lint to){
    if(from>to) return LINF;
    else return to-from;
}

int main(void){
    lint X,Y;
    cin >> X >> Y;
    lint ans=min(min(solve(X,Y),solve(-X,Y)+1),min(solve(X,-Y)+1,solve(-X,-Y)+2));
    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		StringBuffer sb = new StringBuffer();

		while(true) {
			if(!sc.hasNext()) {
				break;
			} 
			sb.append(sc.next().substring(0, 1));							
		}

		System.out.println(sb);
	}

}

Measured memory_bytes: 35176
#A

#B
"""
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = sum(l) - 2*l[-1]
if ans > 0:
    print("Yes")
else:
    print("No")
"""

#C
import bisect
n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
xb = [abs(x[i] - x[i + 1]) for i in range(m-1)]
xb.sort(reverse=True)
ans = sum(xb[n - 1::])
print(ans)

Measured memory_bytes: 56744
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define fs first
#define sc second
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,int> tri;

int n,m;
vector<tri> g[10100];
int dis[10100], cost[10100];

int main(){
  while(scanf("%d%d",&n,&m), n){
    rep(i,n)g[i].clear();
    rep(i,m){
      int u,v,d,c;
      scanf("%d%d%d%d",&u,&v,&d,&c);
      u--; v--;
      g[u].push_back(tri(pii(d,c),v));
      g[v].push_back(tri(pii(d,c),u));
    }

    fill(dis,dis+n,1e9);
    dis[0] = 0; cost[0] = 0;
    priority_queue<pii, vector<pii>, greater<pii> > q;
    q.push(pii(0,0));

    while(q.size()){
      pii p = q.top(); q.pop();
      int d = p.fs, v = p.sc;

      if(dis[v]<d)continue;
      
      for(tri nxt : g[v]){
	int nd = d + nxt.fs.fs, nc = nxt.fs.sc, u = nxt.sc;
	if(dis[u] > nd){
	  dis[u] = nd;
	  cost[u] = nc;
	  q.push(pii(nd,u));
	}else if(dis[u] == nd && cost[u] > nc){
	  cost[u] = nc;
	}
      }
    }
    cout << accumulate(cost,cost+n,0) << endl;
  }
}

Measured memory_bytes: 3304
#include <bits/stdc++.h>
using namespace std;
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; i++)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; i--)
#define vi vector<int>
#define vs vector<string>
#define all(x) (x).begin(),(x).end()
int main() {
    int n,alice,bob;
    alice=0;
    bob=0;
    cin>>n;
    vi a(n);
    repp(i,0,n){
        cin>>a[i];
    }
    sort(all(a), greater<int>());
    repp(i,0,n){
        if(i%2){
            bob+=a[i];
        }else{
            alice+=a[i];
        }
    }

    cout<< alice - bob <<endl;
}

Measured memory_bytes: 3576
import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
    
    static boolean isPalin(String s){
        int i=0;
        int j=s.length()-1;
        
        while(i<j){
            if(s.charAt(i)!=s.charAt(j)) return false;
            i++;
            j--;
        }
        
        return true;
    }
    
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner input = new Scanner(System.in);
		String s = input.next();
		
		boolean b1 = isPalin(s);
		boolean b2 = isPalin(s.substring(0,(s.length()-1)/2));
		boolean b3 = isPalin(s.substring((s.length()+3)/2-1));
		
		if(b1&&b2&&b3) System.out.println("Yes");
		else System.out.println("No");
	}
}


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

int main(){
  int n;
  cin>>n;
  vector<int> h;
  int dp[n];
  dp[0]=0;
  for(int i=0; i<n; i++){ int k; cin>>k; h.push_back(k); }
  dp[1]=abs(h[1]-h[0]);
  for(int i=2; i<n; i++){
    dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]));
  }
  cout<<dp[n-1];

}


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

int main() {
    while (1)
    {
        string x;
        cin >> x;
        if(x=="0") break;
        int sum=0;
        for(int i=0; i<x.size(); i++){
            
            int b= x.at(i)-'0';
            sum+=b;
        }
        cout << sum << endl;
    }
    
    return 0;
}




Measured memory_bytes: 3136
import java.util.Scanner;
public class Main {
	int n;
	int list[];
	public static void main(String args[]) {
		new Main();
	}
	Main() {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		list = new int[n];
		for (int i = 0; i < n; i++) {
			list[i] = scan.nextInt();
		}
		boolean flag = true;
		int cnt = 0;
		while (flag) {
			flag = false;
			for (int i = 1; i < n; i++) {
				if (list[i] < list[i-1]) {
					int tmp = list[i];
					list[i] = list[i-1];
					list[i-1] = tmp;
					cnt++;
					flag = true;
				}
			}
		}
		this.writeArray();
		System.out.println(cnt);
	}
	public void writeArray() {
		System.out.print(list[0]);
		for (int i = 1; i < n; i++) {
			System.out.print(" " + list[i]);
		}
		System.out.println();
	}
}



Measured memory_bytes: 26364