akhauriyash/Code-Regression huggingface dataset:
from itertools import permutations
n,m,r = map(int,input().split())
rl = list(map(int,input().split()))
d = [[10**8]*n for i in range(n)]
for i in range(m):
  a,b,c = map(int,input().split())
  d[a-1][b-1] = d[b-1][a-1] = c
for k in range(n):
  for i in range(n):
    for j in range(n):
      d[i][j] = min(d[i][j],d[i][k]+d[k][j])
m = 10**9
for i in permutations(rl):
  c = 0
  for j in range(1,r):
    c += d[i[j-1]-1][i[j]-1]
  m = min(m,c)
print(m)

Measured memory_bytes: 46808
#include<bits/stdc++.h>                
using namespace std;
#define REP(i,n) for(auto i = 0; i < (n); ++i)
#define REP1(i,n) for(auto i = 0; i <= (n); ++i)
#define REPO(i,o,n) for(auto i = (o); i < (n); ++i)
#define REPR(i,n) for(auto i = (n); i >= 0; --i)
#define REPI(itr,v) for(auto itr=v.begin(); itr != v.end(); ++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin(); itr != v.rend(); ++itr)
#define ALL(v) v.begin(), v.end()
#define SV(n,v) {int tmp;for(int i=0;i<n;++i){scanf("%d",&tmp);v.push_back(tmp);}}
#define push_back pb;
#define push_front pf; 
#define make_pair mp;
#define first fi;
#define second se;
typedef long long ll;

int main(void){
	int X, A , B;
	cin >> X >> A >> B;
	if(A >= B) cout << "delicious" << endl;
	else if(X+A >= B) cout << "safe" << endl;
	else cout << "dangerous" << endl;
}


Measured memory_bytes: 256
num = int(input())
a = list(map(int, input().split()))
count = 0
while(True):
    for i in range(num):
        if a[i] % 2 != 0:
            break
        else:
            a[i] /= 2
    else:
        count += 1
        continue
    break
print(count)

Measured memory_bytes: 3060
import math
N, K = map(int, input().split())
h = list(map(int, input().split()))
 
def nya(N, K, h):
    S = [0] * N
    S[0] = 0
 
    for i in range(1, N):
        value = math.inf
        for step in range(1, K + 1):
            if i - step < 0:
                break
            value = min(value, S[i - step] + abs(h[i] - h[i - step]))
        S[i] = value
    return S[N-1]

print(nya(N, K, h))

Measured memory_bytes: 84880
#include <bits/stdc++.h>
#define DAYS int(1e5)
using namespace std;

vector<vector<int> > memoize(DAYS, vector<int>(4, -1));
int N;
vector<vector<int> > tasks(DAYS, vector<int>(3));

int gainHappiness(int day, int flag) {
    if (day == N) return 0;

    if (memoize[day][flag] != -1) return memoize[day][flag];
    int currMax = -1;
    if (flag == 0) {
        currMax = max(currMax, tasks[day][0] + gainHappiness(day + 1, 1));
        currMax = max(currMax, tasks[day][1] + gainHappiness(day + 1, 2));
        currMax = max(currMax, tasks[day][2] + gainHappiness(day + 1, 3));
    } else if (flag == 1) {
        currMax = max(currMax, tasks[day][1] + gainHappiness(day + 1, 2));
        currMax = max(currMax, tasks[day][2] + gainHappiness(day + 1, 3));
    } else if (flag == 2) {
        currMax = max(currMax, tasks[day][0] + gainHappiness(day + 1, 1));
        currMax = max(currMax, tasks[day][2] + gainHappiness(day + 1, 3));
    } else {
        currMax = max(currMax, tasks[day][0] + gainHappiness(day + 1, 1));
        currMax = max(currMax, tasks[day][1] + gainHappiness(day + 1, 2));
    }

    return memoize[day][flag] = currMax;
}

int main() {
    cin >> N;

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

    cout << gainHappiness(0, 0) << endl;

    return 0;
}

Measured memory_bytes: 17408
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>
#include <cassert>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

const i64 mod = 1e9 + 7;
i64 fact_memo[200001];
i64 fact(i64 x) {
  if (x == 0) return 1;
  if (fact_memo[x]) return fact_memo[x];
  return fact_memo[x] = x * fact(x - 1) % mod;
}
i64 ipow(i64 a, i64 b) {
  return (b & 1 ? a : 1) * (b > 1 ? ipow(a * a % mod, b >> 1) : 1) % mod;
}
i64 fact_inv(i64 x) {
  return ipow(fact(x), mod - 2);
}
i64 perm(i64 a, i64 b) {
  return fact(a) * fact_inv(a - b) % mod;
}
i64 conb(i64 a, i64 b) {
  return fact(a) * fact_inv(b) % mod * fact_inv(a - b) % mod;
}

i64 n;
vector<i64> a;
int main() {
  cin >> n;
  read_n(a, n);

  vector<i64> b(n + 1);
  for (i64 i = 1; i < n; ++i) {
    b[i] = conb(n, i + 1) * fact(i) % mod * fact(n - i - 1) % mod;
    if (i > 0) b[i] = (b[i] + b[i - 1]) % mod;
  }

  i64 ans = 0;
  for (i64 i = 0; i < n; ++i) {
    ans = (ans + a[i] * (fact(n) + b[i] + b[n - i - 1])) % mod;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4096
#include <bits/stdc++.h>
#include <boost/range/adaptor/indexed.hpp>
using namespace std;

#define repi(i, a, b) for(int i = (int)(a); i < (int)(b); ++i)
#define rep(i, n) repi(i, 0, n)
#define all(x) (x).begin(), (x).end()

template <typename T>
std::ostream &operator<<(std::ostream &ostr, const std::vector<T> &v) {
  for (const auto &i : v | boost::adaptors::indexed())
    ostr << (i.index() > 0 ? " " : "") << i.value();
  return ostr;
}

inline void Main() {
  // code
  int d, g, result = 1000000;
  cin >> d >> g;
  vector<int> p(d), c(d), cp(d);
  rep(i, d) cin >> p.at(i) >> c.at(i);

  cp = p;
  int m1 = 0, m2 = 0;
  rep(bit, 1<<d) {
    rep(i, d) {
      if(bit&(1<<i)) {
        m1+=(i+1)*100*cp.at(i)+c.at(i);
        m2+=cp.at(i);
        cp.at(i) = 0;
      }
    }
    rep(i, d) {
      if(m1>=g) {
        result = min(result, m2);
        break;
      }
      while(cp.at(d-i-1)>0) {
        m1+=(d-i)*100;
        m2++;
        cp.at(d-i-1)--;
        if(m1>=g) {
          result = min(result, m2);
          break;
        }
      }
    }
    cp = p;
    m1 = 0, m2 = 0;
  }
  cout << result << endl;
}

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(20);
  Main();
  return 0;
}


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

int main(){
  ll N,A,B,x;
  cin>>N>>A>>B;
  vector<ll> S(N);
  vector<ll> T(N);
  for(int i=0;i<N;i++)
    cin>>S[i];
  sort(S.begin(),S.end());
  x=(S[N-1]-1)/B+1;
  ll mx=x,mn=0,md=x/2,C=A-B;
  while(1){
    x=0;
    for(int i=0;i<N;i++){
      T[i]=S[i]-md*B;
      if(T[i]<=0)
        continue;
      x+=(T[i]-1)/C+1;
    }
    if(x<=md){
      mx=md; md=(mn+mx)/2;
    }else{
      mn=md; md=(mn+mx)/2;
    }
    if(mn+1==mx)
      break;
  }
  cout<<mx<<endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define rep0(i,n) for(ll (i) = 0; (i) < (n); ++(i))
#define rrep0(i,n) for(ll (i) = (n) - 1; (i) >= 0; --(i))
#define rep1(i,n) for(ll (i) = 1; (i) < (n); ++(i))
#define rrep1(i,n) for(ll (i) = (n) - 1; (i) >= 1; --(i))
#define nfor(i,a,b) for(ll (i) = (a); (i) < (b); ++(i))
#define ll long long
#define mod (1000000007)
#define YES cout << "YES" << endl;
#define Yes cout << "Yes" << endl;
#define yes cout << "yes" << endl;
#define NO cout << "NO" << endl;
#define No cout << "No" << endl;
#define no cout << "no" << endl;
#define all(x) (x).begin(),(x).end()

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

ll lcm(ll a,ll b){
    ll g = gcd(a,b);
    return a / g * b;
}

ll fac(ll n){
    ll t = 1;
    rep1(i, n + 1)t *= i;
    return t;
}

int main()
{
    ll n,sum = 0;
    cin >> n;
    vector<ll> a(n + 2,0);
    rep1(i, n + 1){
        cin >> a[i];
        sum += abs(a[i] - a[i - 1]);
    }
    sum += abs(a[n + 1] - a[n]);
    rep1(i, n + 1){
        if (a[i - 1] <= a[i] && a[i] <= a[i + 1]) {
            cout << sum << endl;
        }else{
            cout << sum - (abs(a[i - 1] - a[i]) + abs(a[i] - a[i + 1])) + abs(a[i - 1] - a[i + 1]) << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 2048
X,Y,A,B,C=map(int,input().split())
p=sorted(map(int,input().split()),reverse=True)
q=sorted(map(int,input().split()),reverse=True)
r=sorted(map(int,input().split()),reverse=True)
li=[]
for i in range(X):
    li.append(p[i])
for i in range(Y):
    li.append(q[i])
n=0
res=sum(li)
li=sorted(li)
for i in range(len(li)):
    if(li[i]<r[n]):
        res+=(r[n]-li[i])
        n+=1
    else:
        break
    if(n==len(r)):
        break
print(res)

Measured memory_bytes: 105452
#include<bits/stdc++.h>
using namespace std;
#define int long
signed main(){
  int n,s=0;
  cin>>n;
  vector<int> a(n);
  map<int,int> m;
  for(auto& i:a)cin>>i,++m[i];
  for(auto p:m)s+=p.second*(p.second-1)/2;
  for(auto i:a)cout<<s-m[i]+1<<"\n";
}

Measured memory_bytes: 11008
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int> v, p(n), q(n);
  vector<vector<int>> d;
  for(int i=0; i<n; i++){
    cin >> p[i];
    v.push_back(i+1);
  }
  for(int i=0; i<n; i++){
    cin >> q[i];
  }
  do{
    d.push_back(v);
  } while(next_permutation(v.begin(), v.end()));
  int pp, qq;
  for(int i=0; i<d.size(); i++){
    if(d[i]==p) pp=i;
    if(d[i]==q) qq=i;
  }
  cout << abs(pp-qq);
  return 0;
}

Measured memory_bytes: 3256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
ll a[11111],b[11111],c[11111],d[11111];
int main(){
    //freopen("fibsubseq.in","r",stdin);
    //freopen("fibsubseq.out","w",stdout);
    string s;
    cin>>s;
    if(s[0]=='9'||s[1]=='9')cout<<"Yes";
    else cout<<"No";
return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] arr = new int[3];
		for (int i = 0; i < 3; i++) {
			arr[i] = sc.nextInt();
		}
		Arrays.sort(arr);
		System.out.println(arr[0] + arr[1]);
	}
}


Measured memory_bytes: 24020
#define _USE_MATH_DEFINES

#include <bits/stdc++.h>
using namespace std;
using i32 = int; using i64 = long long int; using f64 = double; using str = string;
template <typename T> using vec = vector<T>;
template <typename T> using heap = priority_queue<T, vec<T>, greater<T>>;
#define times(n, i) for (i32 i = 0; i < (n); ++i)
#define range(a, b, i) for (i32 i = (a); i < (b); ++i)
#define upto(a, b, i) for (i32 i = (a); i <= (b); ++i)
#define downto(a, b, i) for (i32 i = (a); i >= (b); --i)
#define all(xs) (xs).begin(), (xs).end()
#define sortall(xs) sort(all(xs))
#define reverseall(xs) reverse(all(xs))
#define uniqueall(xs) (xs).erase(unique(all(xs)), (xs).end())
#define even(x) (((x) & 1) == 0)
#define odd(x) (((x) & 1) == 1)
#define append emplace_back
#define findge lower_bound
#define findgt upper_bound
const i64 MOD = 1000000007;
const f64 EPS = 1e-10;

template <typename T> T gcd(T a, T b) { while (b != 0) { swap(a, b); b = b%a; } return abs(a); }

i64 a, b, c, d;

i32 main()
{
    cin >> a >> b >> c >> d;
    if (a > c) {
        swap(a, c);
    }
    if (b > d) {
        swap(b, d);
    }
    if (a == c || b == d) {
        cout << 0 << endl;
        return 0;
    }
    i64 ans = gcd(a - c, d - b) - 1;
    ans += (c - a - 1) + (d - b - 1) + 1 - ans*2;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <iomanip>
#include <array>
#include <numeric>
#include <regex>
#include <bitset>
#include <deque>

using namespace std;
typedef long long ll;
typedef pair<int, int> p_ii;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)

const int INF = 1e9;
const double PI = acos(-1.0);
const ll MOD = 1e9 + 7;


int gcd(int a, int b) {//最大公約数
	if (a%b == 0)return b;
	else gcd(b, a%b);
}

int main() {
	int a, b;
	cin >> a >> b;
	REP(i, 1, 4) {
		if (a*b*i % 2 == 1) {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 256
N,M = gets.chomp.split.map(&:to_i)
attached_switchies_num = Array.new(M){gets.chomp.split(' ').map(&:to_i).drop(1).map{|num| num-1}}
ps = gets.chomp.split(' ').map(&:to_i)
cnt = 0
[0, 1].repeated_permutation(N) do |bits|
    denkyus = []
    M.times do |i|
        sum = attached_switchies_num[i].map{|num|
            bits[num]
        }.inject(:+)
        if sum % 2 == ps[i]
            denkyus.push(true)
        else
            denkyus.push(false)
            break
        end
    end
    if denkyus.all?{|denkyu| denkyu == true}
        cnt +=1
    end
end
p cnt

Measured memory_bytes: 1916
from collections import defaultdict
d = defaultdict(int)

N = int(input())


for i in range(2, N+1):
    for j in range(2, i+1):
        while i % j == 0:
            d[j] += 1
            i = i//j
        if i == 1:
            break
# print(d)

c74, c24, c14, c4, c2 = 0, 0, 0, 0, 0
for v in d.values():
    if v >= 74:
        c74 += 1
    if v >= 24:
        c24 += 1
    if v >= 14:
        c14 += 1
    if v >= 4:
        c4 += 1
    if v >= 2:
        c2 += 1


ans = 0
ans += c74
ans += c24*(c2-1)
ans += c14*(c4-1)
ans += c4*(c4-1)//2*(c2-2)
print(ans)


Measured memory_bytes: 3316
/*
  Contest 069
  C - 4-adjacent
  Rakesh Kumar --> 01/09/2020
 */

#include <bits/stdc++.h>

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

    int n = 0;
    std::cin >> n;
    int a = 0, b = 0, c = 0;
    while (n--) {
        int e = 0;
        std::cin >> e;
        if (e % 4 == 0) ++a;
        else if (e % 2 == 0) ++b;
        else ++c;
    }

    if (b == 0) ++a;
    std::cout << (c <= a ? "Yes" : "No") << std::endl;
}


Measured memory_bytes: 3388
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

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

    int h, n;
    cin >> h >> n;
    vector<int> a(n), b(n);
    int maxe = 0;
    for(int i = 0; i < n; ++i){
        cin >> a[i] >> b[i];
        chmax(maxe, a[i]);
    }
    maxe += 5;

    vector<vector<int>> dp(n + 2, vector<int>(h + maxe, INF));
    dp[0][0] = 0;
    for(int i = 0; i <= n; ++i){
        for(int j = 0; j <= h; ++j){
            if(dp[i][j] == INF) continue;
            chmin(dp[i + 1][j], dp[i][j]);
            if(i > 0)   chmin(dp[i][j + a[i - 1]], dp[i][j] + b[i - 1]);
        }
    }

    // for(int i = 0; i <= n; ++i){
    //     cerr << i << '\n';
    //     for(int j = 0; j < h + maxe; ++j){
    //         if(dp[i][j] == INF) cerr << -1 << ' ';
    //         else    cerr << dp[i][j] << ' ';
    //     }
    //     cerr << endl;
    // }

    int ans = INF;
    for(int i = 1; i <= n; ++i){
        for(int j = h; j < h + maxe; ++j){
            chmin(ans, dp[i][j]);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 44160
def counting_sort(A, B, k):
    C = [0 for i in range(k)]
    for j in range(n):
        C[A[j]] += 1
    #C[i] now contains the number of elements equal to i

    for i in range(1, k):
        C[i] += C[i - 1]
    #C[i] now contains the number of elements less than or equal to i

    for j in range(n - 1, -1, -1):
        B[C[A[j]] - 1] = A[j]
        C[A[j]] -= 1


n = int(input())
A = list(map(int, input().split()))

k = max(A) + 1
B = [0 for _ in range(n)]


counting_sort(A, B, k)
print(*B)


Measured memory_bytes: 224384
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int size = sc.nextInt();
    int zero = sc.nextInt();
    int min = zero;
    int max = zero;
    for(int i = 1; i < size; i++){
      int a = sc.nextInt();
      if(a < min){
        min = a;
      }
      if(a > max){
        max = a;
      }
    }
    System.out.println(max - min);
	}
}

Measured memory_bytes: 21844
#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
#include <math.h>
#include <cstdlib>
#define rep(i,n) for(int i = 0;i<(n);i++);
#define all(a) (a).begin(),(a).end()
using namespace std;
using ld = long double;
using ll = long long;
const ll INF = 10010010010;
typedef pair<ll, ll> P;
const ll mod = 1000000007;
ll gcd(ll a, ll b) {//a>b
	if (a < b)swap(a, b);
	if (a % b == 0) return b;
	else return gcd(b, a % b);
}

int main() {
	ll N, K;
	cin >> N;
	string S;
	cin >> S >> K;
	char letter = S[K - 1];
	for (int i = 0; i < N; i++) {
		if (S[i] == letter)cout << S[i];
		else cout << "*";
	}
	cout << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long double ll;
typedef pair<int,int> pii;
#define PB push_back
#define be(v) v.begin(), v.end()
#define endl "\n"

void solve(){
	string s, t;
	cin>>s>>t;
	int lens = s.length();
	int lent = t.length();
	int sum = lent;
	for(int i = 0; i<=(lens-lent); i++){
		int cnt = 0;
		for(int j = 0; j<lent; j++){
			if(t[j]!=s[i+j]){
				cnt++;
			}
		}
		sum = min(sum, cnt);
	}
	cout<<sum<<endl;

}
int main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); cout.tie(NULL);
	int t = 1;
	// cin>>t;
	while(t-->0){
		solve();
	}
	return 0;
}


Measured memory_bytes: 3664
//                   * In The Name of Allah *
// Writer: arianBASS
//#include "stdafx.h"
#include <bits/stdc++.h>
#define Turbo std::ios::sync_with_stdio(false)
#define int long long
#define pb push_back
#define ever ( ; ; )

using namespace std;

int32_t main() {
	Turbo;
	int n;
	cin >> n;
	for (int i = 1; i <= 9; ++i)
		for (int j = 1; j <= 9; ++j)
			if ((i * j) == n) {
				cout << "Yes\n";
				return 0;
			}
	cout << "No\n";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <map> 
#include<set>
#include<queue>

typedef long long ll;


#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;

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

const long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<int, int> P;
ll ma = 1000000000 + 7;
ll h, w, n,k,m; string s,t;
char maze[60][60];
int dis[101][101];
int nm[8][8];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int gcd(int x, int y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);

}
int main() {
	cin >> n >> k;
	vector<P> ab(n);
	rep(i, n) {
		cin >> ab[i].first >> ab[i].second;
	}
	sort(ab.begin(), ab.end());
	ll cnt = 0;
	rep(i, n) {
		cnt += ab[i].second;
		if (k <= cnt) {
			cout << ab[i].first << endl;
			return 0;
		}
	}
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
const int N=2e5+9;
using namespace std;
int edgenum,w[N],clo[N],pos[N],d[N];
int to[N],nxt[N],head[N],n,m,q,tot,rest[N];
void addedge(int from,int too)
{
	++edgenum;nxt[edgenum]=head[from];to[edgenum]=too;head[from]=edgenum;
	++edgenum;nxt[edgenum]=head[too];to[edgenum]=from;head[too]=edgenum;
}
void dfs(int now,int last,int dis,int color)
{
	 if(last>dis) return;
	 if(w[now]==0) w[now]=color,tot++;
	 if(tot>=n) return;
	 int res=dis-last;
	 if(res<=rest[now]) return;
	 rest[now]=res; 
	 for(int i=head[now];i;i=nxt[i])
	 {
	 	int too=to[i];
	// 	if(w[too]==0)
		  dfs(too,last+1,dis,color);
	 }
} 
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
    {
    	 int x,y;
    	 scanf("%d%d",&x,&y);
    	 addedge(x,y);
	}
	scanf("%d",&q);
	for(int i=1;i<=q;++i) scanf("%d%d%d",&pos[i],&d[i],&clo[i]);
	for(int i=q;i>=1;--i) dfs(pos[i],0,d[i],clo[i]);
	
	for(int i=1;i<=n;++i)
	 printf("%d\n",w[i]);
	return 0;
}

Measured memory_bytes: 6016
import Data.List

addSum :: [Int] -> [Int]
addSum list = list ++ [(sum list)]

main = do{
    n <- getLine;
    getContents >>= mapM_ putStrLn . map (unwords . map show) . transpose . map addSum . transpose . map ( addSum . map (read::String->Int)) . map words . lines;
}

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

int n,m,q;
struct node{int l,r,i;};
node a[205000],b[105000];

int tableau[510];
int ans[105000];

int cmp(node alpha,node beta){
    return alpha.r < beta.r;
}

int main(){
    cin >> n >> m >> q;
    for(int i=1;i<=m;i++) cin >> a[i].l >> a[i].r;
    for(int i=1;i<=q;i++) cin >> b[i].l >> b[i].r,b[i].i=i;
    sort(a+1,a+m+1,cmp);
    sort(b+1,b+q+1,cmp);
    int j = 1;
    for(int i=1;i<=q;i++){
	while(j <= m && a[j].r <= b[i].r)tableau[a[j].l]++,j++;
	for(int k=b[i].l;k<=n;k++)ans[b[i].i]+=tableau[k];
    }
    for(int i=1;i<=q;i++) cout<<ans[i]<<endl;
    return 0;
}


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

int n, P, ans, f[6010][8010];

void add(int &x, int y) {
    if ((x += y) >= P) x -= P;
}

int main() {
    scanf("%d %d", &n, &P), f[0][n + 1] = 1;
    for (int i = 0; i < 3 * n; i++) {
        for (int j = -n; j <= i; j++) {
            int k = j + n + 1;
            add(f[i + 1][k + 1], f[i][k]);
            add(f[i + 2][k - 1], 1LL * (i + 1) * f[i][k] % P);
            add(f[i + 3][k], 1LL * (i + 1) * (i + 2) % P * f[i][k] % P);
        }
    }
    for (int i = 0; i <= n; i++) {
        add(ans, f[3 * n][i * 3 + n + 1]);
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 186752
#include <iostream>

using namespace std;
int main() {
	int d, n;
	int answer;

	cin >> d >> n;

	if (d == 0) {
		if(n == 100){
			answer = 101;
		}
		else {
			answer = n;
		}
	}
	else if (d == 1) {
		if (n == 100) {
			answer = 10100;
		}
		else {
			answer = n * 100;
		}
	}
	else if(d == 2){
		if (n == 100) {
			answer = 1010000;
		}
		else {
			answer = n * 10000;
		}
	}


	cout << answer << endl;
}

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

int main()
{
	int M[N][N];
	int i, j, k, n=0, temp=0, secret=0;
	
	
	scanf("%d",&n);
	
	/*???????????\???*/
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
		  M[i][j] = 0;
		}
	}
	
	/*adjacentmatrix??\???*/
	for(i=1;i<=n;i++)
	{
		scanf("%d %d",&secret,&k);
		if(k==0)
		{
		}
		else if(k==1)
		{
			scanf("%d",&temp);
			M[i][temp] = 1;
			temp = 0;
		}
		else
		{
			for(j=1;j<=k;j++)
			{
				scanf("%d",&temp);
				M[i][temp] = 1;
				temp = 0;
			}
		}
	}
	
	for(i=1;i<=n;i++)
	{
		printf("%d",M[i][1]);
		for(j=2;j<=n;j++)
		{
		  printf(" %d",M[i][j]);
		}
	 printf("\n");
	}
	return(0);
}

Measured memory_bytes: 640
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main
{
	public static void main(String[] args)throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = new String[2];
		int r, c;
		str = br.readLine().split(" ");
		r = Integer.parseInt(str[0]);
		c = Integer.parseInt(str[1]);
		int[][] mat = new int[r+1][c+1];
//		mat????????????
		for(int i=0;i<r+1;i++)
		{
			for(int j=0;j<c+1;j++)
			{
				mat[i][j] = 0;
			}
		}
		String[] str2 = new String[c];
		for(int i=0; i<r; i++)
		{
			str2 = br.readLine().split(" ");
			int buf = 0;
			for(int j=0; j<c; j++)
			{
				buf = Integer.parseInt(str2[j]);
				mat[i][j] = buf;
				mat[i][c] += buf;
				mat[r][j] += buf;
			}
			mat[r][c] += mat[i][c];
		}
		for(int i=0; i<r+1; i++)
		{
			for(int j=0; j<c+1; j++)
			{
				System.out.print(mat[i][j]);
				if(j!=c) System.out.print(" ");
				else System.out.println();
			}
		}
	}
}

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

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main(){
    ll n, m;
    cin >> n >> m;

    vector<P> res(m);
    vector<vector<ll>> id(n,vector<ll>());

    rep(i,m){
        ll p,y;
        cin >> p >> y;
        p--;
        P pr(p,y);
        res[i] = pr;
        id[p].push_back(y);
    }


    rep(i,n){
        sort(id[i].begin(), id[i].end(), less<ll>());
    }


    rep(i,m){
        ll p, y;
        p = res[i].first;
        y = res[i].second;

        auto it = lower_bound(id[p].begin(), id[p].end(), y);
        ll d = distance(id[p].begin(), it);
        p++;

        string l = to_string(p);
        string r = to_string(d+1);

        if(l.size()<6){
            ll t = 6-l.size();
            rep(i, t){
                l = '0'+l;
            }
        }
        if(r.size()<6){
            ll t = 6-r.size();
            rep(i, t){
                r = '0'+r;
            }
        }

        cout << l << r << endl;
    }

    return 0;
}

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

int judge(int m);

int main(){
    int x, y;
    cin >> x >> y;
    int X, Y;
    
    X = judge(x);
    Y = judge(y);
    
    if(X == Y){
        cout << "Yes\n";
    }
    else{
        cout << "No\n";
    }
}

int judge(int m){
    if(m == 2)      return 0;
    if(m == 4 || m == 6 || m == 9 || m == 11)       return 1;
    return 2;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using static System.Console;
using static System.Math;
using static MyIO;
using static MyUtil;

public class A { public static void Main() => (new Solver()).Solve(); }

public class Solver
{
	public void Solve()
	{
		var list = Range(0, 11).ToArray();
		list = list.Reverse().ToArray();
		WriteLine(list[GetLong() / 200]);
	}
}

public static class MyIO
{
	private static string[] args = new string[0];
	private static int cnt = 0;
	private static IEnumerable<string> getArgs(long N) => Range(0, N).Select(_ => getArg());
	private static string getArg()
	{
		if(cnt == args.Length) { args = Console.ReadLine().Split(); cnt = 0; }
		return args[cnt++];
	}

	public static int GetInt() => int.Parse(getArg());
	public static long GetLong() => long.Parse(getArg());
	public static double GetDouble() => double.Parse(getArg());
	public static decimal GetDecimal() => decimal.Parse(getArg());
	public static string GetString() => getArg();
	public static char GetChar() => getArg()[0];
	public static int[] GetInts(long N) => getArgs(N).Select(int.Parse).ToArray();
	public static long[] GetLongs(long N) => getArgs(N).Select(long.Parse).ToArray();
	public static double[] GetDoubles(long N) => getArgs(N).Select(double.Parse).ToArray();
	public static decimal[] GetDecimals(long N) => getArgs(N).Select(decimal.Parse).ToArray();
	public static string[] GetStrings(long N) => getArgs(N).ToArray();
}

public static class MyUtil
{
	public static void chmax<T>(ref T x, T y) where T : IComparable<T> { if(x.CompareTo(y) < 0) x = y; }
	public static void chmin<T>(ref T x, T y) where T : IComparable<T> { if(x.CompareTo(y) > 0)	x = y; }
	public static void swap<T>(ref T x, ref T y) { T tmp = x; x = y; y = tmp; }
	public static long rightShift(long x, long y) => (x >> (int)y);
	public static long leftShift(long x, long y) => (x << (int)y);
	public static bool contains(long s, long x) => (rightShift(s, x) & 1L) == 1L;
	public static long gcd(long x, long y) => (y == 0) ? x : gcd(y, x % y);
	public static long lcm(long x, long y) => (x / gcd(x,y)) * y;	
	public static IEnumerable<int> Range(long start, long count) => Enumerable.Range((int)start, (int)count);
	public static void Sort(this List<string> source) => source.Sort(StringComparer.Ordinal);
}


Measured memory_bytes: 28148
using System;

public class hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var n = long.Parse(line[0]);
        var k = long.Parse(line[1]);
        if (n == 1) { Console.WriteLine(k); goto exit; }
        if (k == 1) { Console.WriteLine(1); goto exit; }
        var ans = getAns(n, k);
        Console.WriteLine(ans);
    exit:;
    }
    static long getAns(long n, long k)
    {
        var ok = k / 2;
        var ng = k;
        while (ng - ok > 1)
        {
            var mid = (ok + ng) / 2;
            if (check(n, k, mid)) ok = mid;
            else ng = mid;
        }
        return ok;



    }
    static bool check(long n, long k, long targ)
    {
        var t = targ;
        var sum = t;
        var count = 1;
        while (true)
        {
            t /= 2;
            if (t == 0) return true;
            sum += t;
            if (sum > k) return false;
            count++;
            if (count == n) return true;
        }
    }
}



Measured memory_bytes: 7848
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=(ll)1e9+7;
//const ll MOD=(ll)998244353;
const ll INF=(ll)1e18+10;
const double PI = 2.0*acos(0);
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int dy[]={-1,1,0,0};
int dx[]={0,0,-1,1};

void solve(int ca){
    int H,W,N; cin>>H>>W>>N;
    int sy,sx; cin>>sy>>sx;
    --sy; --sx;
    string S,T; cin>>S>>T;
    vector<int> ty(N,0),tx(N,0),ay(N,0),ax(N,0);
    for (int i = 0; i < N; ++i) {
        switch (S[i]){
            case 'L': tx[i]=-1;
                break;
            case 'R': tx[i]=1;
                break;
            case 'U': ty[i]=-1;
                break;
            case 'D': ty[i]=1;
                break;
        }
        switch (T[i]){
            case 'L': ax[i]=-1;
                break;
            case 'R': ax[i]=1;
                break;
            case 'U': ay[i]=-1;
                break;
            case 'D': ay[i]=1;
                break;
        }
    }

    int maxiy=sy,miniy=sy,maxix=sx,minix=sx;
    for (int i = 0; i < N; ++i) {
        //cout<<maxiy<<" "<<miniy<<" "<<maxix<<" "<<miniy<<endl;
        //takahashi
        if(ty[i]==1) maxiy++;
        if(ty[i]==-1) miniy--;
        if(tx[i]==1) maxix++;
        if(tx[i]==-1) minix--;
        if(maxiy>=H||miniy<0||maxix>=W||minix<0){
            cout<<"NO"<<endl;
            return;
        }

        //aoki
        if(ay[i]==1) miniy=min(miniy+1,H-1);
        if(ay[i]==-1) maxiy=max(maxiy-1,0);
        if(ax[i]==1) minix=min(minix+1,W-1);
        if(ax[i]==-1) maxix=max(maxix-1,0);
        //cout<<maxiy<<" "<<miniy<<" "<<maxix<<" "<<miniy<<endl;
        //cout<<"----"<<endl;
    }
    cout<<"YES"<<endl;



}

//#define MULTI
int main() {
#ifdef MULTI
    int N; cin>>N;
    for (int i = 0; i < N; ++i) {
        solve(i+1);
    }
#else
    solve(0);
#endif
    return 0;
}


Measured memory_bytes: 6944
#include <iostream>
#include <vector>

using namespace std;

int main(){
  vector<int> train;
  vector<int> queue;
  int num;

  while(cin >> num){
    if(num != 0){
      train.push_back(num);
    }else{
      queue.push_back(train.back());
      train.pop_back();
    }
  }

  for(int i=0; i<queue.size(); i++){
    cout << queue[i] << endl;
  }
  return 0;
}

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

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<pair<int, int>>> vvpp;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<pair<int, int>> vpp;
typedef vector<string> vs;
typedef unordered_set<int> si;
typedef pair<int, int> pp;

#define all(n) (n).begin(), (n).end()
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)

template <typename Arg1>
void out(Arg1&& arg1) {
    cout << arg1 << '\n';
}

template <typename Arg1, typename ...Args>
void out(Arg1&& arg1, Args&& ...args) {
    cout << arg1 << ' ';
    out(args...);
}


template <typename T>
void outarr(vector<T> arr) {
    for (int i = 0; i < arr.size() -1; ++i) cout << arr[i] << ' ';
    cout << arr.back() << '\n';
}

template <typename T>
void printV(vector<T> A) {
    if (A.empty()) cerr << "EMTPY\n";
    else { 
        cerr << "[";
        for (int i = 0; i < A.size() -1 ; ++i) {
            cerr << A[i] << ", ";
        }
        if (A.size()) cerr << A.back() << "]\n";
    }
}


template <typename T>
void printVV(vector<vector<T>> A) {
    cerr << "[";
    for (auto v : A) {
        printV<T>(v);
    }
    cerr << "]";
}

template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
    cerr << name << ": " << arg1 << endl;
}

template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&& ...args) {
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << ": " << arg1 << " |";
    __f(comma + 1, args...);
}

int main(int argc, char **argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, k; cin >> n >> k;
    ll mod = 1e9 + 7;

    ll ans = 0;
    for (; k <= n+1; ++k) {
        ll m = k * (k-1) / 2, M = k * (n + n - k + 1) / 2;
        ans += M - m + 1;
        ans %= mod;
    }

    out(ans % mod);

    return 0;
}



Measured memory_bytes: 3628
//hinagata.cpp
//作成日
//更新日
//目的
//手段
/*includes*/
#include <bits/stdc++.h>
/*namespace*/
using namespace std;
using ll= long long;
/*define macro*/
#define REP(i,n) for(ll i=0;i<(n);i++)
#define REPi(i,a,b) for(ll i=(a);i<(b);i++)
#define REPRi(i,a,b) for(ll i=(a);i>(b);i--)
#define ALL(x) (x).begin(),(x).end()

int main(){
    int N,Y;
    cin>>N>>Y;
    REP(i,N+1){
        REP(j,N+1-i){
            if(Y==i*1000+j*5000+(N-i-j)*10000){
                cout<<N-i-j<<" "<<j<<" "<<i<<endl;
                return 0;
            }
        }
    }
    cout<<"-1 -1 -1"<<endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;

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

const int N = 55;
queue<int> q;
vector<int> path;
char mp[N][N];
int vis[N][N], pre[N][N], t[N*N];
int val[N][N], op[N][N], cl[N][N];
int n, m, K, X[N*N], Y[N*N];
void BFS(int sx, int sy, int ex, int ey) {
	while(!q.empty()) q.pop();
	memset(vis, -1, sizeof vis);
	memset(pre, -1, sizeof pre);

	vis[sx][sy] = 0;
	q.push(sx*N+sy);
	while(!q.empty()) {
		int tmp = q.front(); q.pop();
		int x = tmp / N, y = tmp % N;
		if(x == ex && y == ey) break;//continue;
		
		for(int di = 0; di < 4; di ++) {
			int nx = x + dx[di], ny = y + dy[di];
			if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if(vis[nx][ny] != -1 || mp[nx][ny] == '#') continue;
			
			vis[nx][ny] = vis[x][y] + 1;
			pre[nx][ny] = x*N+y;
			q.push(nx*N+ny);
		}
	}
	
	int size = 0, x = ex, y = ey;
	while(pre[x][y] != -1) {
		int tmp = pre[x][y];
		t[size++] = tmp;
		x = tmp / N;
		y = tmp % N;
	}
	for(int i = size-1; i >= 0; i --) path.push_back(t[i]);

}
void input() {
	for(int i = 0; i < n; i ++)
		scanf("%s", mp[i]);

	for(int i = 0; i < n; i ++) {
		for(int j = 0; j < m; j ++) {
			scanf("%d", &val[i][j]);
		}
	}
	for(int i = 0; i < n; i ++) {
		for(int j = 0; j < m; j ++) {
			scanf("%d", &op[i][j]);
		}
	}
	for(int i = 0; i < n; i ++) {
		for(int j = 0; j < m; j ++) {
			scanf("%d", &cl[i][j]);
		}
	}
	for(int i = 0; i < K; i ++) {
		scanf("%d%d", &X[i], &Y[i]);
	}
}
int main() {
	while(~scanf("%d%d%d", &n, &m, &K)) {
		input();
		//
		path.clear();
		for(int i = 1; i < K; i ++) {
			BFS(X[i-1], Y[i-1], X[i], Y[i]);
		}
		path.push_back(X[K-1]*N+Y[K-1]);
		
		memset(pre, -1, sizeof pre);
		int ans = 0;
		for(int i = 0; i < (int)path.size(); i ++) {
			int x = path[i]/N, y = path[i]%N;
			if(pre[x][y] == -1) {
				ans += op[x][y] + cl[x][y];
			} else {
				int tmp = (i - pre[x][y]) * val[x][y];
				tmp = min(tmp, op[x][y] + cl[x][y]);
				ans += tmp;
			}
			pre[x][y] = i;
		}
		
		printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 11172
#include <stdio.h>
using namespace std;

unsigned long A, B, C, D, tmp, r, a, b, x;
unsigned long c=0;
unsigned long t=0;

int main(){
  if(scanf("%lu %lu %lu %lu", &A, &B, &C, &D)==1);  
  
  a=C;
  b=D;
  if(a<b){ 
    tmp = a; 
    a = b; 
    b = tmp; 
  } 
  x = a * b;
  r = a % b; 
  while(r!=0){ 
    a = b; 
    b = r; 
    r = a % b; 
  }
  if(A%C==0 || A%D==0)t++;
  printf("%lu", (B-A+1-t) - ( (B/C)+(B/D)-(B/(x/b)) ) + ( (A/C)+(A/D)-(A/(x/b)) ));
  
  return 0;
}

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

int main(){
    ll h; cin >> h;
    ll ans = 0;
    ll count = 1;
    while(h != 0){
        ans += count;
        h /= 2;
        count *= 2;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
 
  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    String inputTxt = sc.nextLine();

    int ans = 0;
    String[] arrTxt = inputTxt.split(" ");
    int left = Integer.parseInt(arrTxt[0]);
    int right = Integer.parseInt(arrTxt[2]);
    if ("+".equals(arrTxt[1])) {
      ans = left + right;
    } else {
      ans = left - right;
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
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());
    cout << (d[N/2]-d[N/2-1]+1)-1 << endl;
}



Measured memory_bytes: 640
N, M = map(int, input().split())

import math

def prime_fac(n):
  p_lis = []
  temp = n

  for i in range(2, int(math.sqrt(n)) + 1):
    if temp % i == 0:
      cnt = 0
      while temp % i == 0:
        cnt += 1
        temp //= i
      p_lis.append([i, cnt])
  if temp != 1:
    p_lis.append([temp, 1])
  if p_lis == []:
    p_lis.append([n, 1])

  return p_lis

mod = 10 ** 9 + 7
MAX = N + 50
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]

def comb(n, r):
  if n < r:
    return 0
  else:
    return fac[n] * ( finv[r] * finv[n-r] % mod ) % mod
 
for i in range(2, MAX + 1):
  fac.append( ( fac[-1] * i ) % mod )
  inv.append( mod - ( inv[mod % i] * (mod // i) % mod ) )
  finv.append( finv[-1] * inv[-1]  % mod )

ans = 1

for p, a in prime_fac(M):
  if a == p == 1:
    break
  ans *= comb(N+a-1, a)
  ans %= mod

print(ans)

Measured memory_bytes: 20928
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

int main() {
  ll n;
  cin >> n;
  vector<ll> la(n), sa(n+1);
  for (ll &a: la) cin >> a;
  for (ll i = 0; i < n; ++i) { 
    sa[i+1] = sa[i]+la[i];
  }
  int l, r;
  auto f1 = [&](int c, int k) { 
    return sa[k+1]-2*sa[c+1];
  };
  auto f2 = [&](int c, int k) { 
    return sa[n]+sa[k+1]-2*sa[c+1];
  };
  ll ans = sa[n];
  for (int i = 1; i < n-2; ++i) {
    l = 0, r = i;
    while (r-l>1) {
      int c = (l+r)/2;
      ll v = f1(c, i);
      if (v > 0) l = c; else r = c;
    }
    ll min1 = min(sa[l+1], sa[i+1]-sa[l+1]);
    ll max1 = max(sa[l+1], sa[i+1]-sa[l+1]);
    if (l > 0) {
      min1 = max(min1, min(sa[l], sa[i+1]-sa[l]));
      max1 = min(max1, max(sa[l], sa[i+1]-sa[l]));
    }
    if (l+1 < i) {
      min1 = max(min1, min(sa[l+2], sa[i+1]-sa[l+2]));
      max1 = min(max1, max(sa[l+2], sa[i+1]-sa[l+2]));
    }
    // cerr << i << " " << l << " " << min1 << " " << max1 << endl;

    l = i+1, r = n;
    while (r-l>1) {
      int c = (l+r)/2;
      ll v = f2(c, i);
      if (v > 0) l = c; else r = c;
    }
    ll min2 = min(sa[l+1]-sa[i+1], sa[n]-sa[l+1]);
    ll max2 = max(sa[l+1]-sa[i+1], sa[n]-sa[l+1]);
    if (l > i) {
      min2 = max(min2, min(sa[l]-sa[i+1], sa[n]-sa[l]));
      max2 = min(max2, max(sa[l]-sa[i+1], sa[n]-sa[l]));
    }
    if (l+1 < n) {
      min2 = max(min2, min(sa[l+2]-sa[i+1], sa[n]-sa[l+2]));
      max2 = min(max2, max(sa[l+2]-sa[i+1], sa[n]-sa[l+2]));
    }
    // if (i == 3) {
    //   cerr << "[!]" << sa[n]-sa[l+1] << " " << sa[l+1]-sa[i+1] << " " << sa[n]-2*sa[l+1]+sa[i+1] << endl;
    // }
    // cerr << i << " " << l << " " << min2 << " " << max2 << endl;
    ll ma = max(max1, max2);
    ll mi = min(min1, min2);
    ans = min(ans, ma-mi);
    // cerr << i << " " << ma-mi << endl;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3328
#include <stdio.h>
#include <stdlib.h>

int main(){
	int A, B, C, D, E, F, i, j, k, a, b;
	scanf("%d%d%d%d%d%d", &A, &B, &C, &D, &E, &F);
	int *AB = (int *)malloc(sizeof(int) * (F + 1));
	int *CD = (int *)malloc(sizeof(int) * (F + 1));
	for(i = 0; i <= F; i++){
		AB[i] = 0;
		CD[i] = 0;
	}
	for(i = 0; 100 * i * A <= F; i++){
		for(j = 0; 100 * j * B <= F; j++){
			if(100 * (i * A + j * B) <= F){
				AB[100 * (i * A + j * B)] = 1;
			}
		}
	}
	for(i = 0; i * C <= F; i++){
		for(j = 0; j * D <= F; j++){
			if(i * C + j * D <= F){
				CD[i * C + j * D] = 1;
			}
		}
	}
/*	printf("AB:\n");
	for(i = 0; i <= F; i++){
		printf("%d ", AB[i]);
	}
	printf("\n");
	printf("CD:\n");
	for(i = 0; i <= F; i++){
		printf("%d ", CD[i]);
	}
	printf("\n");
*/	a = 100 * A;
	b = 0;
	for(i = 0; i <= F; i++){
		for(j = 0; j <= F; j++){
			if((i > 0 || j > 0) && AB[i] == 1 && CD[j] == 1 && (i + j) * b < (a + b) * j && i + j <= F && i * E >= 100 * j){
//				printf("(i, j) = (%d, %d)\n", i, j);
				a = i;
				b = j;
			}
		}
	}
	printf("%d %d\n", a + b, b);
	return 0;
}

Measured memory_bytes: 128
#include <algorithm>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
constexpr ll MOD = 1000000007;

// struct UnionFind {
//     vector<int> par;
    
//     UnionFind(int N): par(N) {
//         for (int i=0;i<N;i++) par[i] = i;
//     }

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

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

//     bool same(int x, int y) {
//         int rx = root(x);
//         int ry = root(y);
//         return rx == ry;
//     }
// };

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

int main(void) {
    string S;
    cin >> S;
    vector<int> R(S.size(),0);
    ll ans = 0;
    for (int i=S.size()-2;i>=0;i--) {
        if (S[i] == 'B' && S[i+1] == 'C') R[i] = R[i+1] + 1;
        else if ((S[i] == 'A' && S[i+1] != 'C') || (S[i] == 'C' && S[i+1] != 'C')) R[i] = R[i+1];
        else R[i] = 0;
        if (S[i] == 'A') ans += R[i];
    }
    // for (int i=0;i<R.size();i++) cout << R[i];
    // cout << endl;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1412
H, W = map(int, raw_input().split())
board = []
for i in range(0, H):
	board.append(raw_input())
flag1 = True
for i in range(0, H):
	for j in range(0, W):
		if board[i][j] == '#':
			flag2 = True
			for k in range(0, 2):
				if 0 <= i-1+2*k and i-1+2*k < H:
					if board[i-1+2*k][j] == '#':
						flag2 = False
						break
				if 0 <= j-1+2*k and j-1+2*k < W:
					if board[i][j-1+2*k] == '#':
						flag2 = False
						break
			if flag2:
				flag1 = False
				break
if flag1: print 'Yes'
else: print 'No'

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

#define ll = long long;
#define P = pair<int, int>;

int main(){
	int a, b, c;
	cin >> a >> b >> c;
	string answer = "No";
	if(a == b && a != c)
		answer = "Yes";
	if(a == c && a != b)
		answer = "Yes";
	if(b == c && b != a)
		answer = "Yes";
	cout << answer <<endl;
	return 0;
}

Measured memory_bytes: 256
N = int(input())
X = []
Y = []
P = []
for _ in range(N):
    x, y, p = map(int, input().split())
    X.append(x)
    Y.append(y)
    P.append(p)

DX = []
DY = []

for i, x in enumerate(X):
    t = []
    for k in range(1 << N):
        d = abs(x)
        for j, xx in enumerate(X):
            if k & (1 << j):
                d = min(d, abs(xx - x))
        t.append(d * P[i])
    DX.append(t)
for i, y in enumerate(Y):
    t = []
    for k in range(1 << N):
        d = abs(y)
        for j, yy in enumerate(Y):
            if k & (1 << j):
                d = min(d, abs(yy - y))
        t.append(d * P[i])
    DY.append(t)

ANS = [1 << 100] * (N + 1)
PC = [0] * (1 << N)
for i in range(1, 1 << N):
    j = i ^ (i & (-i))
    PC[i] = PC[j] + 1

RA = []
for i in range(1 << N):
    t = []
    for j in range(N):
        if i & (1 << j):
            t.append(j)
    RA.append(tuple(t))


mm = (1 << N) - 1
for i in range(1 << N):
    m = i ^ mm
    j = m
    while 1:
        ans = 0
        for k in RA[i^j^mm]:
            ans += min(DX[k][i], DY[k][j])
        
        pc = PC[i] + PC[j]
        ANS[pc] = min(ANS[pc], ans)
        
        if not j:
            break
        j = m & (j - 1)

print(*ANS, sep = "\n")


Measured memory_bytes: 90108
#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cctype>
#include<map>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,a,b) for (int (i)=a;(i)<(b);(i)++)
#define all(x) (x).begin(),(x).end()

using namespace std;
const int inf = 1001001000;
const long long int Inf = 1001001001001001000;

void print(vector<vector<int>> a){
	for (int i=0;i<a.size();i++){
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<vector<long long int>> a){
	for (int i=0;i<a.size();i++){
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}


int main(){
	vector<int> a;
	vector<pair<int,int>> b;
	string s;
	cin >> s;
	rep(i,s.size()){
		if(s[i] == '\\'){
			a.push_back(i);
		} else if (s[i] == '/') {
			if (a.size() == 0)
				continue;
			int l = a.back();
			a.pop_back();
			if (b.size() == 0)
				b.push_back(pair<int, int>(l, i - l));
			else {
				pair<int, int> temp(0, 0);
				while (b.size() > 0 && b.back().first > l){
					pair<int, int> t = b.back();
					b.pop_back();
					temp.first = t.first;
					temp.second += t.second;
				}
				temp.first = l;
				temp.second += i - l;
				b.push_back(temp);
			}
		}
	}
	int ans = 0;
	vector<int> ans_vec;
	rep(i, b.size()){
		ans += b[i].second;
		ans_vec.push_back(b[i].second);
	}
	cout << ans << endl;
	cout << b.size();
	rep(i, b.size()) cout << " " << ans_vec[i];
	cout << endl;

	return 0;
}




Measured memory_bytes: 3284
N=int(input())
A=list(map(int,input().split(' ')))
def mul(x):
    l=1
    if 0 in x:
        l=0
    else:   
        for i in x:
                l=l*i
                if l>10**18:
                    l=-1
                    break
    return l
print(mul(A))

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

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

void fileio()
{
	#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
}

ll x_or(ll n)
{
	if(n%4==0) return n;
	if(n%4==1) return 1;
	if(n%4==2) return n+1;
	return 0;
}
  
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

//	fileio();

	ll a,b;
	cin>>a>>b;
	ll ans1=x_or(b);
	ll ans2=x_or(max(0LL,a-1));
	
	ll ans=ans1^ans2;
	
	cout<<ans;
		
		                                                    
								
//	cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms\n";
	
	return 0;
}


Measured memory_bytes: 256