akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-
def main():
    import bisect
    N = int(input())
    As = sorted(list(map(int, input().split())))
    Bs = sorted(list(map(int, input().split())))
    Cs = sorted(list(map(int, input().split())))

    c_under_b = [0]*N #b(i)の下に置けるcの数
    a_on_b = [0]*N #b(i)の上に置けるaの数

    for i in range(len(Bs)):
        c_under_b[i] = bisect.bisect_right(Cs, Bs[i])

    for i in range(len(Bs)):
        a_on_b[i] = bisect.bisect_left(As, Bs[i])

    count = 0
    for i in range(len(Bs)):
        count += c_under_b[i] * a_on_b[i]
    print(count)

def main5():
    import bisect
    N = int(input())
    As = sorted(list(map(int, input().split())))
    Bs = sorted(list(map(int, input().split())))
    Cs = sorted(list(map(int, input().split())))

    c_under_b = [] #b(i)の下に置けるcの数
    a_on_b = [] #b(i)の上に置けるaの数

    for b in Bs:
        i = bisect.bisect_right(Cs, b)
        c_under_b.append(N - i)

    for b in Bs:
        i = bisect.bisect_left(As, b)
        a_on_b.append(i)

    count = 0
    for i in range(len(Bs)):
        count += c_under_b[i] * a_on_b[i]
    print(count)

def main4():
    """ TLE """
    import bisect
    N = int(input())
    As = sorted(list(map(int, input().split())))
    Bs = sorted(list(map(int, input().split())))
    Cs = sorted(list(map(int, input().split())))

    c_under_b = [] #b(i)の下に置けるcの数
    a_on_b = [] #b(i)の上に置けるaの数

    for b in Bs:
        i = bisect.bisect_right(Cs, b)
        c_under_b.append(len(Cs[i:]))

    for b in Bs:
        i = bisect.bisect_left(As, b)
        a_on_b.append(len(As[:i]))

    count = 0
    for i in range(len(Bs)):
        count += c_under_b[i] * a_on_b[i]
    print(count)

def main3():
    """ TLE """
    import itertools
    N = int(input())
    As = list(map(int, input().split()))
    Bs = list(map(int, input().split()))
    Cs = list(map(int, input().split()))

    As.sort()
    Bs.sort()
    Cs.sort()
    count = 0
    for c in Cs:
        for b in Bs:
            if c <= b:
                break
            for a in As:
                if b <= a:
                    break
                if c > b > a:
                    count += 1
    print(count)

def main2():
    """ TLE """
    import itertools
    N = int(input())
    As = list(map(int, input().split()))
    Bs = list(map(int, input().split()))
    Cs = list(map(int, input().split()))

    count = 0
    for c in Cs:
        for b in Bs:
            for a in As:
                if a < b < c:
                    count += 1
    print(count)


if __name__ == '__main__':
    main5()


Measured memory_bytes: 24192
#include<iostream>
#include<string>
#include<algorithm>	
#include<cmath>
#include <vector>
using namespace std;
int aa[9], bb[9];
int main() {
	double n, a, b, sum = 0; cin >> n;
	for (int h = 0; h < n; h++) {
		cin >> a >> b;
		aa[h] = a; bb[h] = b;
	}
	for (int h = 0; h < n; h++) {
		for (int i = h + 1; i < n; i++) {
			sum += sqrt(pow(aa[h] - aa[i], 2) + pow(bb[h] - bb[i], 2)) * 2;
		}
	}
	if (n == 2) { sum /= 2; }
	if (n == 3) { sum /= 3; }
	if (n == 4) { sum /= 4; }
	if (n == 5) { sum /= 5; }
	if (n == 6) { sum /= 6; }
	if (n == 7) { sum /= 7; }
	if (n == 8) { sum /= 8; }
	printf("%f\n", sum);
	cin >> n;
}

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

#define rep(var,n)  for(int var=0;var<(n);++var)


int main(){

	int N,T;
  	cin >> N >>T;
  	
  	int c[N],t[N];
  	int best = INT_MAX;	
  	
  	  	rep(i,N){
          	cin >>c[i]>>t[i];
          	if(t[i]<=T) best = min(best,c[i]);
        }
          	
  	if(best==INT_MAX){
		cout << "TLE" << endl;      
    }else{
  		cout << best << endl;      
    }
  
  
  
}

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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define For(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
typedef vector<int> vint;
typedef vector<long long> vlint;
typedef vector<string> vstr;
typedef vector<char> vchar;
typedef vector<vector<long long>> vlint2;

lint powint(lint x, lint y){
    int ret = 1;
    for (int i=0; i < y; i++) ret *= x;
    return ret;
};

lint mod = 1000000007;
vector<int> dx = {1, 0, 0, -1, 1, 1, -1, -1};
vector<int> dy = {0, -1, 1, 0, 1, -1, 1, -1};

map<char, long long> counter(string s){
    map<char, long long> count;
    rep(i, s.size()){
        count[s[i]] ++;
    }
    return count;
};

int powmod(int x, int y, int m){
    if (y == 0) return 1;
    return ((powint(powmod(x, y>>1, m), 2) % m) * powint(x, (y & 1))) % m;
};

int main() {
    lint n, p; cin >> n >> p;
    string s; cin >> s;

    map<int, lint> cnt;
    lint ans = 0;
    if (p == 2){
        rep(i, n){
            if ((int)(s[i] - '0') % 2 == 0) ans += i + 1;
        }
    }
    else if (p == 5){
        rep(i, n){
            if (s[i] == '0' || s[i] == '5') ans += i + 1;
        }
    }
    else{
        int check = 1;
        int a = 0;
        cnt[0] ++;
        For(i, 1, n+1){
            a = (a + (int)(s[n-i] - '0') * powmod(10, i-1, p)) % p;
            cnt[a] ++;
        }
        for (auto i = cnt.begin(); i != cnt.end(); ++i){
            ans += (i -> second) * ((i -> second)-1)/2;
        }
        
    }
    cout << ans << endl;
}



Measured memory_bytes: 1028
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long h,n,s=0,a[100005];
    cin>>h>>n;
    for(int i=0;i<n;i++)
    {
      cin>>a[i];
      s+=a[i];
    }
    if(s>=h)
        cout<<"Yes\n";
    else
        cout<<"No\n";
        return 0;
}


Measured memory_bytes: 1024
r,g,b,n = [int(i) for i in input().split()]
ans = 0

for i in range(n+1):
    for j in range(n+1):
        s = i * r + j * g
        if s > n:
            break
        if (n - s) % b == 0:
            ans += 1

print(ans)


Measured memory_bytes: 2940
N = int(input())
S = input()
T = [0]
for s in S:
    T.append(T[-1] if s == "." else 1+T[-1])
sm = T[-1]
mini = 100000000000000
length = N+1
for t in T:
    length -= 1
    if mini > t+(length-(sm-t)):
        mini = t+(length-(sm-t))
print(mini)

Measured memory_bytes: 11136
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#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 <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

using namespace std;
#define ll long long
#define rep(i,n) for(ll i=0; i<n; i++)
#define rep2(i,a,b) for(ll i=a; i<=b; i++)
#define drep2(i,a,b) for(ll i=a; i>=b; i--)


int main ()
{
  vector<int>a(3);
  int k;
  rep(i,3)
    cin >> a[0] >> a[1] >> a[2]  >> k;
  sort(a.begin(), a.end());
  int ans = 0;
  rep(i,2)
    ans += a[i];
  while (k--) {
    a[2] *= 2;
  }
  ans += a[2];
  cout << ans << endl;
  
}

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

using namespace std;

const int MN = 1e5 + 1;

int A[MN];

int main() {
  int N;
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
  }
  sort(A, A+N);
  if (A[0] == A[N-1]) {
    if (A[0] == N-1) {
      puts("Yes");
    }
    else if (A[0] * 2 <= N) {
      puts("Yes");
    }
    else {
      puts("No");
    }
  }
  else if (A[0] + 1 == A[N-1]) {
    int n = 0;
    while(A[n] == A[0]) n++;
    // A[0] n,  A[0]+1 * N-n
    if (A[N-1] - n >= 1 && (A[N-1] - n) * 2 <= N-n) {
      puts("Yes");
    }
    else {
      puts("No");
    }
  }
  else {
    puts("No");
  }
  return 0;
}


Measured memory_bytes: 640
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <random>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

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



















int main(){
    ll n, m;
    cin >> n >> m;
    vector<ll> h(n);
    REP(i, n){
        cin >> h[i];
    }
    vector<set<ll>> v(n);
    REP(i, m){
        ll a, b;
        cin >> a >> b;
        a--; b--;
        v[a].insert(h[b]);
        v[b].insert(h[a]);
    }
    ll ans = 0;
    REP(i, n){
        if(v[i].empty()){
            ans++;
        }
        else{
            ll mx = *--v[i].end();
            if(mx < h[i]) ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 17928
import java.util.*;

public class Main {

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);		
		int d = sc.nextInt();
		int n = sc.nextInt();
		int ans = 1;
		for (int i = 0; i < d; i++) {
			ans *= 100;
		}
     int val = ans * n;
      if (n == 100) {
        val += ans;
      }
		System.out.println(val);
	}
}


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

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

  if(b <= c){
    printf("0\n");
  } else if(a < c  && c < b && b < d){
    printf("%d\n", b-c);
  } else if(c < a && a < d && d < b){
    printf("%d\n", d-a);
  } else if(d <= a){
    printf("0\n");
  } else if(a <= c && d <= b){
    printf("%d\n", d-c);
  } else{
    printf("%d\n", b-a);
  }
}


Measured memory_bytes: 256
// #define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <locale>
#include <cctype>
#include <sstream>
using namespace std;

void Output(int ansSec){
	int hour = 0, min = 0, sec = 0;
	hour = ansSec / (60*60);
	ansSec = ansSec % (60*60);
	min = ansSec / 60;
	ansSec = ansSec % 60;
	sec = ansSec;

	printf("%02d:%02d:%02d\n", hour, min, sec);
}

int main(){
	int hour, min, sec;
	char colon;
	while (cin >> hour >> min >> sec, hour != -1 && min != -1 && sec != -1){
		int inSec = (hour * 60 + min) * 60 + sec;
		int ansSec = (120 * 60) - inSec;
		int ansSecx3 = ansSec * 3;

		Output(ansSec);
		Output(ansSecx3);
	}
	return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define rep(i,n) for (int (i) = 0; (i) < (n); i++)
#define ll long long
using namespace std;
int main() {
  ll n; cin >> n;
  if(n < 1200){
    cout << "ABC";
  }
  else if(n < 2800){
    cout << "ARC";
  }
  else{
    cout << "AGC";
  }
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cout<<__FUNCTION__<<":"<<__LINE__<<": "<<#x<<" = "<<x<<endl;
#define debug2(x, y) cout<<__FUNCTION__<<":"<<__LINE__<<": "<<#x<<" = "<<x<<"  |  "<<#y<<" = "<<y<<endl;
#define forr(i, s, n) for(ll i=(ll)(s); i<(ll)(n); ++i)
#define forn(i, n) forr(i, 0, n)
#define eb(n) emplace_back(n)
#define endl '\n'
#define fst first
#define snd second
using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = pair<int, ii>;
using vi = vector<int>;
using vii = vector<ii>;
using vvi = vector<vi>;
using vs = vector<string>;
const int INF = INT_MAX - 5;
const ll LINF = LLONG_MAX - 5;
const int MOD = 1e9 + 7;
int t;
ll a,b,c,d;
ll gcd(ll a, ll b) {
    while(b) {
        a %= b;
        swap(a, b);
    }
    return a;
}
int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
        if(a < b or a % b > c or d < b) {
            puts("No");
            continue;
        }
        ll e = gcd(b, d);
        // debug(e);
        a %= e;
        if(b - e + a <= c) {
            puts("Yes");
        } else {
            puts("No");
        }
    }
    return 0;
}


Measured memory_bytes: 256
def check(S, even, odd):
  for i,c in enumerate(S):
    if i % 2 == 0:
      if not c in even:
        return "No"
    else:
      if not c in odd:
        return "No"
  return "Yes"

S = input()
even = ["R", "U", "D"] 
odd = ["L", "U", "D"]
print(check(S, even, odd))


Measured memory_bytes: 2940
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template <class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;} return 0;}
template <class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;} return 0;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;
const double EPS = 1e-9;


int main(void) {

    int n,m;
    cin>>n>>m;
    string s;
    cin>>s;
    int pos=n;
    vi ans;
    while(pos>0){
        for(int i=m;i>=0;i--){
            if(i==0){
                fin(-1);
                return 0;
            }
            if(pos-i<0){
                continue;
            }
            if(s[pos-i]=='0'){
                ans.pb(i);
                pos=pos-i;
                break;
            }
        }
    }
    reverse(all(ans));
    rep(i,ans.size()){
        if(!i)cout<<ans[i];
        else cout<<" "<<ans[i];
    }
    cout<<endl;
}

Measured memory_bytes: 1144
#include <bits/stdc++.h>
#define int llint
#define rep(i, a, n) for(int (i) = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int (i) = (int)(a);(i) <= (int)(n);++(i))
#define repif(i, a, x) for(int (i) = (int)(a);(x);++(i))
#define repr(i, a, n) for(int (i) = ((int)(a)-1);(i) >= (int)(n);--(i))
#define reper(i, a, n) for(int (i) = (int)(a);(i) >= (int)(n);--(i))
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define SIZE(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define RNG(x, a, n) &((x)[a]), &((x)[n])
#define ADD(a, b) ((((a+MOD)%MOD)+((b+MOD)%MOD))%MOD)
#define MUL(a, b) ((((a)%MOD)*((b)%MOD))%MOD)
#define CEIL(x) ((int)ceil(((double)x)))
#define POW(x, y) ((int)pow(x, y))
#define UNIQUE(x) (x).erase(unique(ALL((x))), (x).end())
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define fcout cout << fixed << setprecision(10)
#define pb push_back
#define pf push_front
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define PI (acos(-1))
#define EPS (1e-10)
#define INF INT_MAX
#define INFLL LLONG_MAX
#define MOD 1000000007
using llint = long long;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using SI = std::set<int>;
using MII = std::map<int, int>;
using TIII = std::tuple<int, int, int>;
using MCI = std::map<char, int>;
using VPII = std::vector<PII>;
using Complex = std::complex<double>;
using namespace std;


int N, M;
int ab[200010];


signed main(){
	cin >> N >> M;

	rep(i, 0, M){
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		if(a == 0) ab[b]++;
		if(b == N-1) ab[a]++;
	}

	if(any_of(RNG(ab, 0, N), [](int x){ return x == 2; })) cout << "POSSIBLE" << endl;
	else cout << "IMPOSSIBLE" << endl;

	return 0;
}

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

//template
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
//end

ll dp[5010][10101];

int main(){
   int n,a,b; cin>>n>>a>>b;
   vector<int> p(n); rep(i,0,n)cin>>p[i],p[i]--;
   vector<int> rev(n); rep(i,0,n)rev[p[i]]=i*2+1;
   rep(i,0,n+1)rep(j,0,2*n+1)dp[i][j]=INF;
   rep(j,0,2*n+1)dp[0][j]=0;
   rep(i,0,n){
      rep(j,0,2*n+1){
         int add;
         if(j==rev[i])add=0;
         if(j>rev[i])add=a;
         if(j<rev[i])add=b;
         chmin(dp[i+1][j],dp[i][j]+add);
      }
      rep(j,0,2*n)chmin(dp[i+1][j+1],dp[i+1][j]);
   }
   cout<<dp[n][2*n]<<endl;
   return 0;
}

Measured memory_bytes: 395648
// User: el_heffeh
// Date: 6/16/20

#include <bits/stdc++.h>

using namespace std;

int X, Y;

void solve() {
	cin >> X >> Y;
	for (int i = 0; i <= X; ++i) {
		int val = X - i;
		if (i * 2 + val * 4 == Y) {
			cout << "Yes" << endl;
			return;
		}
	}
	cout << "No" << endl;
}

int main() {
	ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);    
    //freopen("input.txt", "r", stdin);
	solve();
    return 0;
}

/* 
	When writing code, be sure to look out for:
 	* Array out of bounds access
 	* Integer overflow
 	* Variable scopes and names
 	* Be proactive and make sure to completely think a whole problem through before writing any code
 	Coding is a fun activity, and it should be treated that way. Don't get mad over some failed test cases or time limit exceeded verdicts. Keep your cool and stay calm!
*/


Measured memory_bytes: 3532
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int N = 2e5+5,mod = 1e9+7;
int n,ans,val[N],bit[N<<1];
it add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
it mul(int x,int y){return 1ll*x*y%mod;}
il inc(int &x,int y){x=add(x,y);}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),bit[0]=1;
	for(ri i=1;i<=n;++i)
		read(val[i]),bit[i]=mul(bit[i-1],2);
	for(ri i=n+1;i<=2*n;++i)
		bit[i]=mul(bit[i-1],2);
	sort(val+1,val+1+n);
	for(ri i=1;i<=n;++i){
		int res=add(mul(bit[n+i-1],val[i]),mul(mul(n-i,bit[n+i-2]),val[i]));
		inc(ans,mul(bit[n-i],res));
	}
	print(ans);
	return 0;
}

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

using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second
#define SZ(u) ((int) (u).size())
#define ALL(u) (u).begin(), (u).end()

inline void proc_status()
{
    ifstream t("/proc/self/status");
    cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>()) << endl;
}

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline T read()
{
	register T sum(0), fg(1);
	register char ch(getchar());
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') fg = -1;
	for(;  isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) - '0' + ch;
	return sum * fg;
}

typedef long long LL;
typedef long double LD;
typedef pair<int, int> pii;

const int MAXN = (int) 1e5;

int n, m;

struct node
{
	int u, A, B, val;

	inline bool operator < (const node &rhs) const { return this->val < rhs.val; }

	node() { }
	node(int _u, int _A, int _B): u(_u), A(_A), B(_B), val(max(_A - _B, 0)) { }
}a[MAXN + 5];

int A[MAXN + 5], B[MAXN + 5], val[MAXN + 5];

vector<int> adj[MAXN + 5];

inline void input()
{
	n = read<int>(), m = read<int>();
	for(int i = 1; i <= n; ++i)
	{
		int A0 = read<int>(), B0 = read<int>();
		a[i] = node(i, A0, B0);
		A[i] = A0, B[i] = B0, val[i] = max(A0 - B0, 0);
	}
	for(int i = 1; i <= m; ++i)
	{
		int u = read<int>(), v = read<int>();
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
}

namespace DSU
{
	int fa[MAXN + 5];

	inline void init(int N) { for(int i = 1; i <= N; ++i) fa[i] = i; }
	inline int get_fa(int u) { return u == fa[u] ? u : fa[u] = get_fa(fa[u]); }
	inline void link(int u, int v) { fa[get_fa(v)] = get_fa(u); }
}

inline void solve()
{
	sort(a + 1, a + n + 1);

	static LL f[MAXN + 5], sum[MAXN + 5];
	static int rnk[MAXN + 5];

	DSU::init(n);
	for(int i = 1; i <= n; ++i) f[i] = val[i], sum[i] = B[i], rnk[a[i].u] = i;
	for(int i = 1; i <= n; ++i)
	{
		int u = a[i].u;
		for(auto v0 : adj[u])
		{
			int v = DSU::get_fa(v0);
			if(u != v && rnk[u] > rnk[v])
			{
				chkmin(f[u], max(f[v], val[u] - sum[v]));
				sum[u] += sum[v];
				DSU::link(u, v);
			}
		}
	}
	printf("%lld\n", f[a[n].u] + sum[a[n].u]);
}

int main()
{
//	freopen("F.in", "r", stdin);
//	freopen("F.out", "w", stdout);

	input();
	solve();

	return 0;
}



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

using namespace std;
const int N=3e3+10,mod=1e9+7;
char a[N][N];
int dp[N][N];
int main()
{

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

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

    dp[0][0]=1;
    for(int i=0;i<n;i++)
     for(int j=0;j<m;j++){

            if(i==0&&j==0)
            continue;

            dp[i][j]=((a[i-1][j]=='.'?dp[i-1][j]%mod:0)+(a[i][j-1]=='.'?dp[i][j-1]%mod:0))%mod;
     }
        printf("%d",dp[n-1][m-1]);
}


Measured memory_bytes: 16000
#include <stdio.h>

int main(int argc, const char * argv[]) {
    double r,x,y;
    scanf("%lf",&r);
    x=1.0*r*r*3.141592653589;
    y=1.0*(r+r)*3.141592653589;
    printf("%f %f\n",x,y);
    return 0;
}

Measured memory_bytes: 648
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int main(){

	string s;
	cin >> s;

	int n = s.size();
	if(s[n-1] != 's') 	s.push_back('s');
	else 	{
		s.push_back('e');
		s.push_back('s');
	}
	
	cout << s << endl;
    return 0;
}





Measured memory_bytes: 3628
A=1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51
K=int(input())
print(A[K-1])

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#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 h,w;
	cin >> h >> w;
	vector<vector<char>> a(h,vector<char>(w));
	for(int i = 0;i < h;i++){
		for(int j = 0;j < w;j++){
			cin >> a[i][j];
		}
	}
	rep(i,h+2)rep(j,w+2){
        if(i == 0 || j == 0 || i == h+1 || j == w+1) cout << '#';
		else cout << a[i-1][j-1];
		if(j == w+1) cout << endl;
	}
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
typedef long long ll;
ll g(ll a,ll b)
{
    if(b==0)
        return a;
    else
        return g(b,a%b);
}
int main()
{
    int n;
    cin>>n;
    ll a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    ll x, lcm=a[0];
    for(int i=0;i<n;i++)
    {
       lcm=a[i]/g(a[i],lcm)*lcm;
    }
    cout<<lcm;
        return 0;
}

Measured memory_bytes: 256
a, b, c = map(int, input().split())

if ( a % 2 == 0 and b % 2 == 0 and c % 2 == 0 and a == b == c):
    print(-1)
    quit()

count = 0
while(a % 2 == 0 and b % 2 == 0 and c % 2 == 0):
    _a = b / 2 + c /2
    _b = a / 2 + c /2
    _c = a / 2 + b /2
    a = _a
    b = _b
    c = _c
    count += 1
print(count)

Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
using namespace std;
//4問目	
int main(){
	int n,m,h,t,last=0;
	vector<int>time;
	bool f[3000]={0};
	cin>>n;
	for(int i=0;i<n;i++){
	cin>>h>>t;
	time.push_back(h*3600+t*60);
	}
	cin>>m;
	for(int i=0;i<m;i++){
	cin>>h>>t;
	time.push_back(h*3600+t*60);
	}
	sort(time.begin(),time.end());
	int ts=time.size();
	for(int i=0;i<ts;i++){
		for(int j=i+1;j<ts;j++){
		if(time[i]==time[j]&&i!=j)f[j]=1;
		}
	}
	for(int i=0;i<ts;i++)if(f[i]==0)last=i;
	for(int i=0;i<ts;i++){
	if(f[i])continue;
	bool f2=0;
	if(time[i]%3600/60<10)f2=1;
	cout<<time[i]/3600<<":";
	if(f2)cout<<"0";
	cout<<time[i]%3600/60;
	if(i==last)cout<<endl;
	else cout<<" ";
	}
	return 0;
}

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

const int mod = 1000000007;
ll dp[100005][3];
P dfs(vector<vector<ll>> &g, int u, int x){
    if(g[u].empty()){
        dp[u][0] = 1;
        dp[u][1] = 1;
        return P(dp[u][0],dp[u][1]);
    }
    if(dp[u][0]!=0)return P(dp[u][0],dp[u][1]);
    ll dp0=1,dp1=1;
    for(int p:g[u]){
        if(p == x)continue;
        P d = dfs(g,p,u);
        (dp0 *= (d.first + d.second)) %= mod;
        (dp1 *= d.first) %= mod;
    }
    dp[u][0] = dp0;
    dp[u][1] = dp1;
    return P(dp0,dp1);
}

int main(){
    int n;
    cin >> n;
    vector<vector<ll>> g(n);
    rep(i,n-1){
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(g,0,-1);
    ll ans = dp[0][0] + dp[0][1];
    ans %= mod;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 16384
import sys
N = int(input())
Ai = list(map(int, input().split()))

lastIdx = -1

m = 1000
k = 0

for j in range(N - 1, 0, -1):
    if Ai[j] > Ai[j - 1]:
        lastIdx = j
        break

if lastIdx == -1:
    print(1000)
    sys.exit()

def buy(i):
    global m, k
    rate = Ai[i]

    ki = m // rate
    k += ki
    m -= ki * rate
    # print("{}: buy: {} {}".format(i, m, k))

def sell(i):
    global m, k
    rate = Ai[i]

    m += (rate * k)
    k = 0
    # print("{}: sell: {} {}".format(i, m, k))


buy(0)

is_buy = False
for i in range(0, lastIdx):
    if is_buy:
        if Ai[i] >= Ai[i + 1]:
            continue
        else:
            buy(i)
            is_buy = False
    else:
        if Ai[i] <= Ai[i + 1]:
            continue
        else:
            sell(i)
            is_buy = True
sell(lastIdx)
print(m)


Measured memory_bytes: 61928
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int[] x = new int[5];
		int ans = 0;
		
		for (int i = 0; i < 5; i++) {
			x[i] = scanner.nextInt();
			if (x[i] == 0) {
				ans = i + 1;
			}
		}
		
		System.out.println(ans);

	}

}


Measured memory_bytes: 35656
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<string>
#include<iomanip>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007
#define MAXS(x,y) (x = max(x,y))
#define MINS(x,y) (x = min(x,y))

using namespace std;

typedef long long int ll;

const ll INF=(ll)1e18;

int N;
ll memo[401][401];
vector<ll> a(400);
ll csum[401];

ll dp(int l, int r){
  if(memo[l][r] != -1) return memo[l][r];

  if(l==r){
    return memo[l][r] = 0;
  }

  ll ret = INF;
  ll sum;
  if (l == 0){
    sum = csum[r];
  }else{
    sum = csum[r] - csum[l-1];
  }
  REP(i,r-l){
    MINS(ret, dp(l,l+i) + dp(l+i+1, r) + sum);
  }
  return memo[l][r] = ret;
}

int main(){
  cin >> N;

  REP(i,N)cin >> a[i];
  REP(i,N)REP(j,N) memo[i][j] = -1;

  csum[0] = a[0];
  FOR(i,1,N)csum[i] = csum[i-1] + a[i];

  cout << dp(0,N-1) << endl;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n) for(int i=1;i<=(n);i++)
#define lol long long
#define SUM(n) ((n)+1)*(n)/2 //1〜nまでの総和を求める式
#define mp make_pair
#define fi first
#define se second
#define pu push_back
#define SYOU(x) fixed<<setprecision(x+1) //小数点桁数を指定する
#define abs(x,y) max(x,y)-min(x,y)
#define all(v) v.begin(),v.end()
#define UPDight(a,b) (a+b-1)/b //小数点切り上げ 
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD=int(1e9)+7; 
using namespace std;
using pii = pair<int, int>;
typedef vector<int> vit;

//最大公約数
lol gcd(lol x, lol y){
  if(x < y) swap(x, y);
  lol r = x % y;
  while(r != 0){
    x = y;
    y = r;
    r = x % y;
  }
  return y;
}

//最小公倍数
lol lcm(lol x, lol y){
  lol a = x * y;
  return (a / gcd(x, y));
}

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

  long double a, b;
  cin >> a >> b;
  cout << (lol)(a * b) << '\n';
  return 0;
}


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

#define pb       push_back
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const string INF="NO";

template<class T> struct Edge{
	int u,v;
	T w;
	Edge(){}
	Edge(int U,int V,T W):u(U),v(V),w(W){}
};

template<class T>
struct AdjList:public vector< vector< Edge<T> > >{
	AdjList(){}
	AdjList(int n,const vector< Edge<T> > &v=vector< Edge<T> >()):vector< vector< Edge<T> > >(n,v){}
	template<class U> AdjList(U b,U e):vector< vector< Edge<T> > >(b,e){}
};

template<class T>
T BackwardBellmanFord(const AdjList<T> &adj,int s,int t){
	int n=adj.size();
	vector<T> d(n,INF); d[t]=T();

	bool changed;
	rep(t,6*n+1){
		changed=false;
		rep(v,n) rep(i,adj[v].size()) {
			int u=adj[v][i].u;
			string nextd=adj[v][i].w+d[v];
			if(d[v]!=INF && (d[u]==INF || nextd<d[u])){
				d[u]=nextd;
				changed=true;
				if(u==s && t>=n) return INF;
			}
		}
		if(!changed) break;
	}

	return d[s];
}

int main(){
	for(int n,m,s,g;cin>>n>>m>>s>>g,n;){
		AdjList<string> adj(n);
		rep(i,m){
			int u,v;
			string lbl; cin>>u>>v>>lbl;
			adj[v].pb(Edge<string>(u,v,lbl)); // reverse edge
		}

		cout<<BackwardBellmanFord(adj,s,g)<<endl;
	}

	return 0;
}

Measured memory_bytes: 1368
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=100000000000000000;


int main() {
    int n,m,l;
    cin >> n >> m >> l;
    vector<vector<pair<int,int>>> d(n+1,vector<pp>(n+1,mk(inf,l)));
    vector<vector<pair<int,int>>> e(n+1,vector<pp>(0));
    rep(i,n) d[i+1][i+1]=mk(0,l);
    rep(i,m){
        int f,g,h;
        cin >> f >> g >> h;
        e[f].push_back(mk(g,h));
        e[g].push_back(mk(f,h));
    }
    rep(i,n){
        int k=i+1;
        queue<pair<int,pp>> q;
        q.push(mk(k,mk(l,0)));
        while(!q.empty()){
            int f=q.front().first,g=q.front().second.first,h=q.front().second.second;
            q.pop();
            rep(j,e[f].size()){
                if (g<e[f][j].second) continue;
                int o=g-e[f][j].second;
                if (h<d[k][e[f][j].first].first){
                    d[k][e[f][j].first]=mk(h,o);
                    q.push(mk(e[f][j].first,mk(o,h)));
                    q.push(mk(e[f][j].first,mk(l,h+1)));
                }
                if (h==d[k][e[f][j].first].first && o>d[k][e[f][j].first].second){
                    d[k][e[f][j].first]=mk(h,o);
                    q.push(mk(e[f][j].first,mk(o,h)));
                    q.push(mk(e[f][j].first,mk(l,h+1)));
                }
            }
        }
    }
    int q;
    cin >> q;
    rep(i,q){
        int f,g;
        cin >> f >> g;
        if (d[f][g].first!=inf) cout << d[f][g].first << endl;
        else cout << -1 << endl;
    }
}


Measured memory_bytes: 2432
import math
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    POS = [list(map(int, input().split())) for i in range(N)]
    DIS = [[0]*(N) for _ in range(N)]
    M = 1
    for i in range(1,N+1):
        M *= i
    for i in range(N):
        for j in range(N):
            DIS[i][j] = math.sqrt((POS[i][0] - POS[j][0])**2 +(POS[i][1] - POS[j][1])**2)
    print(sum(map(sum, DIS))/N)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
using System;

namespace ITP1_7_B
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                string[] input = Console.ReadLine().Split(' ');
                int range = int.Parse(input[0]);
                int sum = int.Parse(input[1]);
                int cnt = 0;

                if (range == 0 && sum == 0) break;

                for (int i = 1; i <= (range - 2); i++)
                {
                    for (int j = (i + 1); j <= (range - 1); j++)
                    {
                        for (int k = (j + 1); k <= range; k++)
                        {
                            int value = i + j + k;
                            if (value == sum)
                                cnt += 1;
                        }
                    }
                }
                Console.WriteLine(cnt);
            }

        }
    }
}

Measured memory_bytes: 9212
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 10;
ll xx[N], yy[N], zz[N];
int main() {
    typedef pair<ll, int> pa;
    priority_queue<pa> que;
    int x, y, z, k;
    cin >> x >> y >> z >> k;
    for(int i = 0; i < x; i++) {
        cin >> xx[i];
    }
    for(int i = 0; i < y; i++) {
        cin >> yy[i];
    }
    sort(xx, xx+x);
    for(int i = 0; i < z; i++) {
        cin >> zz[i];
        for(int j = 0; j < y; j++) {
            que.push(pa(zz[i]+yy[j]+xx[x-1], x-1));
        }
    }
    vector<ll> ans;
    while(k--) {
        pa now = que.top(); que.pop();
        ans.push_back(now.first);
        now.second--;
        if(now.second>=0) {
            now.first += xx[now.second] - xx[now.second+1];
            que.push(now);
        }
    }
    for(ll x:ans) {
        cout << x << '\n';
    }
    return 0;
}

Measured memory_bytes: 22760
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stdio.h>
#include <cstring>
#include <string.h>
using namespace std;

int main()
{
		int n;
		cin >> n;
		int four = 0, two = 0;
		for (int i = 1; i <= n; i++)
		{
			int x;
			cin >> x;
			if (x % 4 == 0)  four++;
			else if (x % 2 == 0) two++;
		}
		two = max(two - 1, 0);
		if (four * 2 + two >= n - 1)
			cout << "Yes" << endl;
		else cout << "No" << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int[] x = new int[N];
		for(int i = 0 ; i < N ; i++) x[i] = sc.nextInt();
		int ans = 0;
		for(int i = 0 ; i < N ; i++) {
			if(Math.abs(x[i] - 0) >= Math.abs(x[i] - K)) {
				ans += Math.abs(x[i] - K) * 2;
			} else {
				ans += Math.abs(x[i] - 0) * 2;
			}
		}
		System.out.println(ans);
	}
}

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

using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  int a, sum = 0;
  for (int i = 0; i < m; i++) {
    cin >> a;
    sum += a;
  }
  if (sum <= n) {
    cout << n - sum << endl;
  } else {
    cout << -1 << endl;
  }

  return 0;
}

Measured memory_bytes: 3648
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;

int main() {
	int N;
	cin >> N;
	vector<int> d(N);
	for (int i = 0; i < N; i++) cin >> d[i];
	sort(d.begin(), d.end());
	int ans1, ans2;
	ans1 = d[N / 2 - 1];
	ans2 = d[N / 2];
	cout << ans2 - ans1 << endl;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = getInt(sc);
		int[] p = getIntArray(sc);

		int count = 0;
		for (int i = 0; i < n - 2; i++) {
			if ((p[i] < p[i + 1] && p[i + 1] < p[i + 2]) || (p[i] > p[i + 1] && p[i + 1] > p[i + 2])) {
				count++;
			}
		}
		System.out.println(count);
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をlongで返却
	 *
	 * @return
	 */
	public static long getLong(Scanner sc) {

		return Long.parseLong(sc.next());
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をintで返却
	 *
	 * @return
	 */
	public static int getInt(Scanner sc) {

		return Integer.parseInt(sc.next());
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をStringで返却
	 *
	 * @return
	 */
	public static String getString(Scanner sc) {

		return sc.next();
	}

	/**
	 * *汎用メソッド <br>
	 * スキャナーからの入力値をint配列で返却
	 *
	 * @return
	 */
	public static int[] getIntArray(Scanner sc) {
		String line = "";
		// 直前にnext()を実行していると改行コードだけ取ってしまうのでその対策
		while (line.equals("")) {
			line = sc.nextLine();
		}

		String[] strArray = line.split(" ");
		int[] intArray = new int[strArray.length];
		for (int i = 0; i < strArray.length; i++) {
			intArray[i] = Integer.parseInt(strArray[i]);
		}
		return intArray;
	}
}


Measured memory_bytes: 21204
use std::cmp::*;
use std::io::*;

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let n: usize = itr.next().unwrap().parse().unwrap();
    let mut k: usize = itr.next().unwrap().parse().unwrap();
    let s: Vec<char> = itr.next().unwrap().chars().collect();

    let mut rle = Vec::new();
    let mut i = 0;
    let mut ans = 0;
    while i < n {
        let mut j = 1;
        while i + j < n && s[i] == s[i + j] {
            j += 1;
            ans += 1;
        }
        rle.push(j);
        i += j;
    }

    for i in 0..rle.len() {
        if i % 2 == 1 {
            if i == rle.len() - 1 {
                ans += 1;
            } else {
                ans += 2;
            }
            k -= 1;
        }
        if k == 0 {
            break;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 3400
from math import gcd
class Factor:
    def __init__(self, max_element):
        self.minFactor = [-1]*(max_element+1)
        for i in range(2, max_element+1):
            if self.minFactor[i] == -1:
                for j in range(i, max_element+1, i):
                    self.minFactor[j] = i
    def getFactorSet(self, element):
        retSet = set(1)
        while element > 1:
            retSet.add(element)
            retSet.add(self.minFactor[element])
            element //= self.minFactor[element]
        return retSet
    def getPrimeFactorSet(self, element):
        retSet = set()
        while element > 1:
            retSet.add(self.minFactor[element])
            element //= self.minFactor[element]
        return retSet
    def getPrimeFactorDic(self, element):
        retDic = {}
        while element > 1:
            val = self.minFactor[element]
            if val in retDic:
                retDic[val] += 1
            else:
                retDic[val] = 1
            element //= val
        return retDic

def main():
    n = int(input())
    a = list(map(int, input().split()))
    f = True
    fact = Factor(max(a))
    st = set()
    for v in a:
        fac_set = fact.getPrimeFactorSet(v)
        for u in fac_set:
            if u in st:
                f = False
                break
            st.add(u)
        if not f:
            break
    if f:
        print("pairwise coprime")
    else:
        all_gcd = a[0]
        for i in range(1, n):
            all_gcd = gcd(all_gcd, a[i])
        if all_gcd == 1:
            print("setwise coprime")
        else:
            print("not coprime")

if __name__ == "__main__":
    main()

Measured memory_bytes: 132580
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int INF = 1<<30;
int n, m;
int dfs(int v, vector<bool> &visited, vector<vector<bool>> &edge){
  bool all_visited = true;
  for(int i=0;i<n;i++){
  	if(!visited[i]){all_visited=false;break;}
  }
  if(all_visited)return 1;
  int ret=0;
  for(int i=0;i<n;i++){
  	if(!edge[v][i] || visited[i])continue;
    visited[i]=true;
    ret+=dfs(i, visited, edge);
    visited[i]=false;
  }
  return ret;
}

int main(){
  cin>>n>>m;
  vector<bool> visited(n, false);
  vector<vector<bool>> edge(n, vector<bool>(n));
  for(int i=0;i<m;i++){
  	int a, b;cin>>a>>b;a--;b--;
    edge[a][b]=edge[b][a]=true;
  }
  visited[0]=true;
  cout<<dfs(0, visited, edge)<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, x, y) for (ll i = x; i <= y; i++)
#define BIT(t) (1ll << t)
#define PER(i, y, x) for (ll i = y; i >= x; i--)
#define vll vector<ll>
#define vvll vector<vector<ll>>
#define pll pair<ll, ll>
#define SIZE(v) ll(v.size())
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
using namespace std;
typedef long long ll;
//        ios::sync_with_stdio(false);
//        cin.tie(nullptr);

bool ok(ll mid, vll& a, vll& b, ll zero, ll k, ll n){
  ll ans = 0;
  if(mid == 0){
    ans += (zero - 1) * zero / 2 + zero * (n - zero) + SIZE(a) * SIZE(b);
  }else if( mid > 0){
    REP(i,0,SIZE(a)-1){
      ll tmp = upper_bound(a.begin(), a.end(), mid / a[i]) - a.begin();
      ans += tmp;
      if(a[i] * a[i] <= mid){
        ans--;
      }
    }
    REP(i,0,SIZE(b)-1){

      ll tmp = upper_bound(b.begin(), b.end(), mid / b[i]) - b.begin();
      ans += tmp;
      if(b[i] * b[i] <= mid){
        ans--;
      }
    }
    ans /= 2;
    ans += (zero - 1) * zero / 2 + zero * (n - zero) + SIZE(a) * SIZE(b);
  }else{
    ans = SIZE(a) * SIZE(b);
    ll m = -mid - 1;
    REP(i,0,SIZE(a)-1){
      ll tmp = upper_bound(b.begin(), b.end(), m / a[i]) - b.begin();
      ans -= tmp;
    }
  }  //cout << ans << " " << mid << endl;

  return ans < k;
}

int main(){
  ll n, k;
  cin >> n >> k;
  vll a,b;
  ll zero = 0;
  REP(i,1,n){
    ll tmp;
    cin >> tmp;
    if(tmp > 0){
      a.push_back(tmp);
    }else if(tmp < 0){
      b.push_back(-tmp);
    }else{
      zero++;
    }
  }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  ll lb= -1e18-1; ll ub = 1e18+1;
  while(ub - lb > 1){
    ll mid = (ub + lb) / 2;
    if(ok(mid, a, b, zero, k, n)){
      lb = mid;
    }else{
      ub = mid;
    }
  }
  cout << ub << endl;
}

Measured memory_bytes: 5252
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>

using namespace std;

typedef unsigned long long ull;

#define loop(i,a,b) for(int i=(a);i<ull(b);++i)
#define rep(i,n) loop(i,0,n)

const int d = 150;

int dx[6] = {-1, 0, 1, 1, 0, -1};
int dy[6] = {0, 1, 1, 0, -1, -1};

int main(){
	int t, n;
	int field[450][450];
	while(cin >> t >> n, t+n){
		vector<pair<int, int> > v(n);
		rep(i, 450)rep(j, 450) field[i][j] = 0;
		rep(i, n){int x, y; cin >> x >> y; field[x+d][y+d] = -1;}
		int sx, sy; cin >> sx >> sy; sx += d; sy += d;
		field[sx][sy] = 1;
		queue<pair<int, int>> q;
		q.push(make_pair(sx, sy));

		while(!q.empty()){
			pair<int, int> p = q.front(); q.pop();
			int x = p.first, y = p.second;
			if(field[x][y] > t) continue;
			rep(i, 6){
				int nx = x+dx[i], ny = y+dy[i];
				if(field[nx][ny] != -1 && (field[x][y]+1 < field[nx][ny] || field[nx][ny] == 0)){
					field[nx][ny] = field[x][y]+1;
					q.push(make_pair(nx, ny));
				}
			}
		}

		int count = 0;
		rep(i, 450)rep(j, 450) if(0 < field[i][j] && field[i][j] < 1e7) count++;
		cout << count << endl;
	}
}

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

int main()
{
    string s;
    cin>>s;
    queue<char> beginning , ending;
    ll q;
    cin>>q;
    ll checker = 1;
    while( q--)
    {
        int t;
        cin>>t;
        if( t== 1)
        {
            if( checker == 1)
                checker = 2;
            else checker = 1;
        } else
        {
            int f ;
            char c;
            cin>>f>>c;
            if( f== 1 && checker == 1)
            {
                beginning.push(c);
            }
            else if( f== 1 && checker == 2)
            {
                ending.push( c);
            }
            if( f== 2 && checker == 1 )
                ending.push(c);
            if( f== 2 && checker == 2)
                beginning.push(c);
        }
    }
    string bstring , estring;
    while( !beginning.empty() ) {
        bstring.push_back( beginning.front() );
        beginning.pop();
    }
    while( !ending.empty() )
    {
        estring.push_back( ending.front() );
        ending.pop();
    }
    if( checker == 2)
    {
        reverse( estring.begin() , estring.end() );
        reverse( s.begin() , s.end() );
        s = estring + s;
        s = s+ bstring;
    }
    else
    {
        reverse( bstring.begin() ,bstring.end() );
        s= bstring + s;
        s += estring;
    }
    cout<<s;
}

Measured memory_bytes: 4580
//B
#include <bits/stdc++.h>
#define reg register

using namespace std;

typedef long long ll;
const int maxn = 100005;

inline ll read() {
	reg ll s = 0, t = 0; reg char ch = getchar();
	while (!isdigit(ch)) t |= ch == '-', ch = getchar();
	while (isdigit(ch)) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
	return t ? -s : s;
}

int pos[maxn];
int main() {
	int k = read(), x = read();
	int cnt = 1;
	int tot = 0; pos[++tot] = x;
	if (k == 1) { cout << x << endl; return 0; }
	while (x - cnt >= -1000000) {
		pos[++tot] = x - cnt;
		cnt++;
		if (tot == k) break;
	}
	cnt = 1;
	while (x + cnt <= 1000000) {
		pos[++tot] = x + cnt;
		cnt++;
		if (tot == 2 * k - 1) break;	
	}
	sort(pos + 1, pos + tot + 1);
	for (int i = 1; i <= tot; i++) cout << pos[i] << " ";
	return 0;	
}

Measured memory_bytes: 256