akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int shop[100001];
int cnsmr[10001];
int main(void){
	int d;
	int n,m;
	int i,j;
	int sum;
	int key,mid,low,high,flg;
	while(1){
		cin>>d;
		if(d==0)	break;
		cin>>n>>m;
		fill(shop,shop+n+1,0);
		fill(cnsmr,cnsmr+m,0);
		shop[0]=0;
		for(i=1;i<n;i++)	cin>>shop[i];
		for(i=0;i<m;i++)	cin>>cnsmr[i];
		shop[n]=d;
		// for(i=0;i<=n;i++)	cout<<shop[i]<<endl;
		// for(i=0;i<m;i++)	cout<<cnsmr[i]<<endl;
		sort(shop,shop+n+1);
		sum=0;
		for(i=0;i<m;i++){
			key=cnsmr[i];
			high=n;
			low=0;
			flg=0;
			while(low<=high){
				mid=(high+low)/2;
				if(key<shop[mid]){
					high=mid-1;
				}
				else if(key>shop[mid]){
					low=mid+1;
				}
				else{
					flg=1;
					break;
				}
			}
			if(flg==1){
				sum+=abs(shop[mid]-cnsmr[i]);
			}
			else{
				min(shop[low]-cnsmr[i],shop[high]-cnsmr[i]);
				sum+=min(abs(shop[low]-cnsmr[i]),abs(shop[high]-cnsmr[i]));
			}
		}
		cout<<sum<<endl;
	}
	return 0;
}
	


Measured memory_bytes: 3524
chars = ""
while True:
	try:
		chars += raw_input()
	except EOFError:
		break

#chars = raw_input()
low_chars = chars.lower()
#print low_chars

alphabet = "abcdefghijklmnopqrstuvwxyz"

for c in alphabet:
	cnt = low_chars.count(c)
	print("{:} : {:}".format(c, cnt))

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


int main() {
  long a,b,x;
  cin >> a>>b>>x; 
  cout<<(b+x)/x-(a+x-1LL)/x<<endl; 
}

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

#define ll long long int
#define ull unsigned long long int
#define po2(z) 1<<(ll)z
#define fr(i,x,n) for(ll i=(ll)(x);i<(ll)(n);++i)
#define rf(i,x,n) for(ll i=(ll)(x);i>=(ll)(n);--i)
#define modinv(x) powah(x,mod-2)
#define ncr(n,r) (((fact[n]*modinv(fact[n-r]))%mod*modinv(fact[r]))%mod)
#define factorial fact.pb(1);sidha(i,1,MAX)fact.pb((fact[i-1]*i)%mod)
#define TC ll test;cin>>test;while(test--)
#define tej ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define mod (ll)1000000007
#define MAX 100005

ll t[102][MAX];

ll knapsack(ll wt[],ll val[],ll W,ll n)
{
	if(n==0||W==0){
		return 0;
	}
	if(t[n][W]!=-1){
		return t[n][W];
	}
	
	if(wt[n-1]<=W){
		return t[n][W]=max(val[n-1]+knapsack(wt,val,W-wt[n-1],n-1),knapsack(wt,val,W,n-1));
	}
	else{
		return t[n][W]= knapsack(wt,val,W,n-1);
	}
	
}

int main(){
memset(t,-1,sizeof(t));
ll n,W;
cin>>n>>W;

ll wt[n],val[n];

fr(i,0,n)cin>>wt[i]>>val[i];

cout<<knapsack(wt,val,W,n);

}



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

int main(){
    int a,b;
    char op;
    while(1){
        cin>>a>>op>>b;
        if(op=='?')break;
        else if(op=='+')cout<<a+b<<endl;
        else if(op=='-')cout<<a-b<<endl;
        else if(op=='*')cout<<a*b<<endl;
        else cout<<a/b<<endl;
    }
    return 0;
}


Measured memory_bytes: 3108
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
  long x = sc.nextLong();
  long y = sc.nextLong();
  int counter = 0;
  while(x<=y){
    x *= 2;
    counter++;
  }
  System.out.println(counter);
}}


Measured memory_bytes: 21844
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>

using namespace std;

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

int main(){
    long int n, t;
    cin >> n >> t;
    long int a[n];
    rep(i, n) cin >> a[i];
    long int umx[n];
    umx[n-1] = a[n-1];
    long int mx = a[n-1];
    for (int i = n - 2; i >= 0; i--){
        if (mx < a[i]){
            mx = a[i];
            umx[i] = mx;
        }else{
            umx[i] = mx;
        }
    }
    long int ans = 0;
    long int pf = 0;
    rep(i, n){
        if(pf < (t/2) * (umx[i] - a[i])){
            pf = (t/2) * (umx[i] - a[i]);
            ans = 1;
        }else if(pf == (t/2) * (umx[i] - a[i])){
            ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1792
N = gets.to_i
XY = N.times.map{gets.split.map(&:to_i)}
sum = 0
cnt = 0

XY.permutation(N) do |xy|
  (N - 1).times do |i|
    sum += Math.sqrt((xy[i][0] - xy[i+1][0])**2 + (xy[i][1] - xy[i+1][1])**2)
  end
  cnt += 1
end
puts sum / cnt

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

int main(){
	int n,a,b;cin>>n>>a>>b;
	if(a+b-1>n||a*(ll)b<n){
		puts("-1");return 0;
	}
	vector<int>ans;
	rep(i,b){
		int d=1;
		if(a>1){
			if(i<(n-b)/(a-1))d=a;
			if(i==(n-b)/(a-1))d=1+(n-b)%(a-1);
		}
		int c=n-ans.size()-d+1;
		rep(j,d)ans.push_back(c+j);
	}
	rep(i,ans.size()){
		if(i)printf(" ");
		printf("%d",ans[i]);
	}
	puts("");
}

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

int main() {
  int N;
  cin >> N;
  vector<int> vec(N);
  int sum=1;
 
  for (int i=0;i<N;i++){
    cin >> vec.at(i);
  }
  
  sort(vec.begin(),vec.end());
  reverse(vec.begin(),vec.end());
  
  for (int i=0;i<N-1;i++){
    if(vec.at(i) > vec.at(i+1)){
      sum++;
    }
  }    
  cout << sum << endl;
}



Measured memory_bytes: 256
from collections import deque

n, m = map(int, input().split())
uv  =[[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    uv[u - 1].append(v - 1)
s, t = map(int, input().split())
s -= 1
t -= 1

queue = deque()
queue.append(s)
queue.append(1)
queue.append(0)
check = [[False for _ in range(3)] for _ in range(n)]
check[s][0] = True

while queue:
    pos = queue.popleft()
    ans = queue.popleft()
    kkp = queue.popleft()
    for next_pos in uv[pos]:
        if next_pos == t and kkp == 2:
            print(ans // 3)
            exit()
        if check[next_pos][(kkp + 1) % 3]:
            continue
        check[next_pos][(kkp + 1) % 3] = True
        queue.append(next_pos)
        queue.append(ans + 1)
        queue.append((kkp + 1) % 3)
print(-1)
    

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

int main(){
    int X, Y, Z, K;
    int64_t A[1000], B[1000], C[1000];
    cin >> X >> Y >> Z >> K;
    for(int i=0; i<X; i++) cin >> A[i];
    for(int i=0; i<Y; i++) cin >> B[i];
    for(int i=0; i<Z; i++) cin >> C[i];

    vector<int64_t> cand;
    for(int i=0; i<X; i++) for(int j=0; j<Y; j++) cand.push_back(A[i] + B[j]);
    sort(cand.rbegin(), cand.rend());

    vector<int64_t> ans;
    int sz = min((int)cand.size(), K);
    for(int i=0; i<sz; i++) for(int j=0; j<Z; j++) ans.push_back(cand[i] + C[j]);
    sort(ans.rbegin(), ans.rend());

    for(int i=0; i<K; i++){
        cout << ans[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 43364
a = int(input())
s = {a}
i=1
lenPrev=len(s)
while i<1000000:
  i+=1
  if a%2==0:
    a=a/2
  else:
    a=3*a+1
  s.add(a)
  
  if len(s) == lenPrev:
    print(i)
    break
  lenPrev=len(s)


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

signed main() {
	int a, c; string b;
	cin >> a >> b >> c;
	string t = b;
	for (int d = 0; d < a&&c>0; d++) {
		if (b[d] == '0') {
			b[d] = '1';
			c--;
		}
	}
	int d = a - 1;
	while (c--) {
		while (t[d] == '0')d--;
			b[d] = '0';
			d--;
	}
	cout << b << endl;
}

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

int main(){
  int N;
  int A[210];
  int a = 0;
  int count = 0;
 
  cin >> N;
  for(int i = 0; i < N; ++i){
    cin >> A[i];
  }
  while(a == 0){
   for(int j = 0; j < N; ++j){
    if(A[j]%2 != 0) a = 1;
    else A[j] = A[j]/2;
   }
  ++count;
  }
  cout << count - 1 << endl;
}

Measured memory_bytes: 3644
def bellman_ford(N, M, edge):
    d = [10 ** 100] * N
    d[0] = 0
    infFlag = False
    for count in range(N + 1):
        for i in range(M):
            if d[edge[i][0]] + edge[i][2] < d[edge[i][1]]:
                d[edge[i][1]] = d[edge[i][0]] + edge[i][2]
                if count == N and edge[i][1] == N - 1:
                    infFlag = True
    return infFlag, -d[N - 1]


def main():
    N, M = map(int, input().split())
    edge = []
    for i in range(M):
        a, b, c = map(int, input().split())
        edge.append([a - 1, b - 1, -c])
    infFlag, ans = bellman_ford(N, M, edge)
    if infFlag:
        print('inf')
    else:
        print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3408
from collections import Counter

N = int(input())
A = [int(i) for i in input().split()]

cnt = Counter(A)
mem = dict()
for k, v in cnt.items() :
  mem[k] = v * (v - 1) // 2

s = sum(mem.values())
for i in range(N) :
  ret = s - mem[A[i]] + (cnt[A[i]] - 1) * (cnt[A[i]] - 2) // 2
  print(ret)

Measured memory_bytes: 96460
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
using vec = vector<ll>;
using vect = vector<double>;
using Graph = vector<vector<ll>>;
#define loop(i, n) for (ll i = 0; i < n; i++)
#define Loop(i, m, n) for (ll i = m; i < n; i++)
#define pool(i, n) for (ll i = n; i >= 0; i--)
#define Pool(i, m, n) for (ll i = n; i >= m; i--)
#define mod 1000000007ll
#define flagcount __builtin_popcount
#define flag(x) (1 << x)
#define flagadd(bit, x) bit |= flag(x)
#define flagpop(bit, x) bit &= ~flag(x)
#define flagon(bit, i) bit &flag(i)
#define flagoff(bit, i) !(bit & (1 << i))
#define all(v) v.begin(), v.end()
#define low2way(v, x) lower_bound(all(v), x)
#define high2way(v, x) upper_bound(all(v), x)
#define idx_lower(v, x) (distance(v.begin(), low2way(v, x)))  //配列vでx未満の要素数を返す
#define idx_upper(v, x) (distance(v.begin(), high2way(v, x))) //配列vでx以下の要素数を返す
#define idx_lower2(v, x) (v.size() - idx_lower(v, x))         //配列vでx以上の要素数を返す
#define idx_upper2(v, x) (v.size() - idx_upper(v, x))         //配列vでxより大きい要素の数を返す
#define putout(a) cout << a << endl
#define Gput(a, b) G[a].push_back(b)
#define Sum(v) accumulate(all(v), 0ll)
#define gcd(x, y) __gcd(x, y)
ll ctoi(char c)
{
    if (c >= '0' && c <= '9')
    {
        return c - '0';
    }
    return 0;
}
template <typename T>
T lcm(T x, T y)
{
    T z = gcd(x, y);
    return x * y / z;
}
template <typename T>
bool primejudge(T n)
{
    if (n < 2)
        return false;
    else if (n == 2)
        return true;
    else if (n % 2 == 0)
        return false;
    double sqrtn = sqrt(n);
    for (T i = 3; i < sqrtn + 1; i++)
    {
        if (n % i == 0)
        {
            return false;
        }
        i++;
    }
    return true;
}
//場合によって使い分ける
//const ll dx[4]={1,0,-1,0};
//const ll dy[4]={0,1,0,-1};
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
//2次元配列の宣言
//vector<vector<ll>> field(h, vector<ll>(w));
ll n, m, q;
vector<vector<ll>> rows;
void dfs(vec row)
{
    ll siz = row.size();
    if (siz == n)
    {
        rows.push_back(row);
        return;
    }
    ll now = row[siz - 1];
    if (now == m)
    {
        row.push_back(m);
        dfs(row);
    }
    else
    {
        Loop(i, now, m + 1)
        {
            row.push_back(i);
            dfs(row);
            row.pop_back();
        }
    }
}
int main()
{
    cout << fixed << setprecision(30);
    ll q;
    cin >> n >> m >> q;
    vec a(q), b(q), c(q), d(q);
    loop(i, q) cin >> a[i] >> b[i] >> c[i] >> d[i];
    vector<vector<ll>> pre(m, vector<ll>(1));
    loop(i, m) pre[i][0] = i + 1;
    loop(i, m) dfs(pre[i]);
    ll X = rows.size();
    ll ans = 0;
    loop(i, X)
    {
        vec now = rows[i];
        ll preans = 0;
        loop(j, q)
        {
            if (now[b[j] - 1] - now[a[j] - 1] == c[j])
                preans += d[j];
        }
        ans = max(ans, preans);
    }
    putout(ans);
    return 0;
}


Measured memory_bytes: 13968
n = int(raw_input())
s = []
for i in xrange(n):
    s.append(int(raw_input()))
s.sort()
ssum = sum(s)
while(1):
    if ssum % 10 != 0:
        break
    elif ssum == 0:
        break
    for i in xrange(len(s)):
        if (ssum - s[i]) % 10 != 0:
            ssum -= s.pop(i)
            break
    else:
        ssum -= s.pop(0)
print ssum


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

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

    vector<int> studentOrder(n);
    for (int i = 0; i < n; i++)
    {
        int input;
        cin >> input;

        studentOrder.at(input - 1) = i + 1;
    }

    for (int i = 0; i < n; i++)
    {
        cout << studentOrder.at(i) << ' ';
    }

    cout << endl;
}

Measured memory_bytes: 1152
#include<iostream>
#include<string>
using namespace std;
int main(){
  long long  n,tmp,num,cnt=0,lb=0,ra=0,ab=0;
  string s;
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> s;
    for(int i=0;i<s.size()-1;i++){
      if(s[i]=='A'&&s[i+1]=='B'){
        cnt++;
      }
    }
    if(s[0]=='B'&&s[s.size()-1]=='A') ab++;
      else if(s[0]=='B') lb++;
      else if(s[s.size()-1]=='A') ra++;
  }
  if(ab==0){
    cnt+=min(ra,lb);
  }else{
    if(ra+lb>0){
      cnt+=ab+min(ra,lb);
    }else{
      cnt+=ab-1;
    }
  }
  cout << cnt << endl;
}


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

using namespace std;

using int64 = long long;
const int mod = 998244353;

const int64 infll = (1LL << 60) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

template< typename F >
struct FixPoint : F {
  FixPoint(F &&f) : F(forward< F >(f)) {}

  template< typename... Args >
  decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, forward< Args >(args)...);
  }
};

template< typename F >
inline decltype(auto) MFP(F &&f) {
  return FixPoint< F >{forward< F >(f)};
}

int main() {
  int H, A;
  cin >> H >> A;
  cout << (H + A - 1) / A << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int n,a,L=1,ans;
int main(void){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a;
        if(a==L){ans++;L++;}
    }
    if(L==1)cout<<-1<<endl;
    else cout<<n-L+1<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <queue>
#define heap priority_queue
#define ll long long
using namespace std;
const ll maxn = 200;
ll n,m,a[maxn+1][maxn+1];
ll c[10][10];
ll f[10];
ll res;
int main()
{
	ios_base::sync_with_stdio(0);
	//freopen("input.txt","r",stdin);
	cin >> n >> m;
	for (ll i=0; i<10; i++)
	for (ll j=0; j<10; j++)
	cin >> c[i][j];
	for (ll k=0; k<10; k++)
	for (ll i=0; i<10; i++)
	for (ll j=0; j<10; j++)
	c[i][j]=min(c[i][j],c[i][k]+c[k][j]);
	res=0;
	for (ll i=1; i<=n; i++)
	for (ll j=1; j<=m; j++)
	{
		cin >> a[i][j];
		if (a[i][j]!=-1) res+=c[a[i][j]][1];
	}
	//cout << c[8][9] << '\n';
	cout << res;
	return 0;
}

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

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

	int **r = new int*[N];
	for(int n=0; n<N; n++){
		r[n] = new int[3];
	}

	cin >> r[0][0] >> r[0][1] >> r[0][2];
	for(int n=1; n<N; n++){
		int a, b, c;
		cin >> a >> b >> c;
		r[n][0] = max(r[n-1][1], r[n-1][2]) + a;
		r[n][1] = max(r[n-1][2], r[n-1][0]) + b;
		r[n][2] = max(r[n-1][0], r[n-1][1]) + c;
	}

	cout << max(max(r[N-1][0], r[N-1][1]), r[N-1][2]);

	return 0;
}


Measured memory_bytes: 4096
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;

int n;
ll a, b;
ll x[120000];

int main() {
	cin >> n >> a >> b;
	for (int i = 0; i < n; ++i)
		cin >> x[i];
	ll ans = 0;
	for (int i = 0; i < n - 1; ++i) {
		ans += min(b, a * (x[i + 1] - x[i]));
	}
	cout << ans << "\n";
	return 0;
}




Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <string.h>
#include <vector>
//s#define rep(i, n) for (int i = 0; i < (n); i++)
#define MAX 10000

using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define rep(i,a,n) for(int i=a; i<n; i++)
#define r0 return 0
#define INF (int)1e15
#define MOD 1000000007

#define access(i) a[i/3][i%3]
//#define random_shuffle(r...)random_shuffle(r,[](int _){return my_rand()%_;})

 int main(){

  ll n,ans=0;
  cin>>n;

  for(int i=1;i<=n;i++)
  {
    for(int j=2;j<=5;j++)
    {
      long long y = pow(i,j);

      if(y<=n) ans = max(ans,y);
    }
  }

  cout<<ans<<endl;

 return 0;
 }


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

using namespace std;

int N ;
int memo[100010];

int dp(int i, int* h) {
    if(i == N - 1) return 0;
    if( memo[i] != -1) return memo[i];
    int a = INT_MAX;
    if(i < N - 2) a = abs(h[i] - h[i + 2]) + dp(i + 2, h);
    int b = abs(h[i] - h[i + 1]) + dp(i + 1, h);
    return  memo[i] = min(a, b);
}

int main() {
    cin >> N;
    memset(memo, -1, sizeof memo);
    int h[N];
    for(int i = 0; i < N; i++){
        cin >> h[i]; 
    }
    cout << dp(0, h);
    return 0;
}


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

int main() {
  int X; cin >> X;
  
  int ans = 1;
  for (int i = 2; i*i <= X; i++) {
    for (int b = i; b <= X; b *= i) {
      ans = max(ans, b);
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp9
{
    class Program
    {
        static void MainA(string[] args)
        {
            Console.WriteLine(int.Parse(Console.ReadLine()) < 3200 ? "red" : Console.ReadLine());
        }

        static void MainB(string[] args)
        {
            Console.ReadLine();
            Console.WriteLine(1.0d / Console.ReadLine().Split(' ').Select(x => int.Parse(x)).Select(x => 1.0d / x).Sum());
        }

        static void Main(string[] args)
        {
            Console.ReadLine();
            int[] arr = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).OrderBy(x => x).ToArray();
            double sum = arr[0];
            var arr2 = arr.Skip(1);
            foreach (var n in arr2)
            {
                sum = (sum + n) / 2;
            }
            Console.WriteLine(sum);
        }
    }
}


Measured memory_bytes: 13396
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define pb push_back
#define eq push
#define dq pop
#define f front
#define inf 100000000
int main()
{
lli  r;
cin>>r;
cout<<3*(r*r)<<endl;
 return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    l=[list(map(int,input().split())) for _ in range(N)]
    l.sort()
    c=0
    ans=0
    for i in range(N):
        if c>M:
            break
        ans+=min(M-c,l[i][1])*l[i][0]
        c+=l[i][1]
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 56540
//by (111110101)2
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>
using namespace std;
int n,m,dp[2][222][222][222],a[222][222],sum[222][222];
bool ck(int x,int y,int xx,int yy)
{
	int now=sum[x-1][y-1]+sum[xx][yy]-sum[x-1][yy]-sum[xx][y-1];
	return now==0 || now==((xx-x+1)*(yy-y+1));
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			char c;
			cin>>c;
			if(c=='.')
			{
				a[i][j]=0;
			}
			else
			{
				a[i][j]=1;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(a[i][j]==0);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int l=1;l<=m;l++)
		{
			for(int r=l;r<=m;r++)
			{
				int x=i,y=n,ans=i-1;
				while(x<=y)
				{
					int mid=(x+y)/2;
					if(ck(i,l,mid,r))
					{
						ans=mid;
						x=mid+1;
					}
					else
					{
						y=mid-1;
					}
				}
				dp[0][i][l][r]=ans;
			}
		}
	}
	if(dp[0][1][1][m]==n)
	{
		cout<<0<<endl;
		return 0;
	}
	int ch=1,an=0;
	for(int k=1;k<=16;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int l=1;l<=m;l++)
			{
				for(int r=l;r<=m;r++)
				{
					int d=dp[an][dp[an][i][l][r]+1][l][r];
					if(dp[an][i][l][r]==n)
					{
						dp[ch][i][l][r]=n;
						continue;
					}
					int x=l,y=r-1;
					while(x<=y)
					{
						int mid=(x+y)/2,t1=dp[an][i][l][mid],t2=dp[an][i][mid+1][r];
						d=max(d,min(t1,t2));
						if(t1>=t2)
						{
							x=mid+1;
						}
						else
						{
							y=mid-1;
						}
					}
					dp[ch][i][l][r]=d;
				}
			}
		}
		if(dp[ch][1][1][m]==n)
		{
			cout<<k<<endl;
			return 0;
		}
		swap(ch,an);
	}
	return 0;
}

Measured memory_bytes: 73472
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    long long n,i;
    cin>>n;
    n/=2;
    long long a[n],b[n];
    for(i=0;i<n;i++){
        cin>>a[i]>>b[i];
    }
    sort(a,a+n);
    sort(b,b+n);
    long long a1,a2,A1,A2,b1,b2,B1,B2,count;
    a1=0;a2=0;b1=0;b2=0;
    count=1;
    for(i=0;i<n-1;i++){
        if(a[i]==a[i+1]){
            count++;
        }else{
            if(count>a1){
                a2=a1;
                A2=A1;
                a1=count;
                A1=a[i];
            }else if(count>a2){
                a2=count;
                A2=a[i];
            }
            count=1;
        }
    }
    if(count>a1){
        a2=a1;
        A2=A1;
        a1=count;
        A1=a[i];
    }else if(count>a2){
        a2=count;
        A2=a[i];
    }
    count=1;
    for(i=0;i<n-1;i++){
        if(b[i]==b[i+1]){
            count++;
        }else{
            if(count>b1){
                b2=b1;
                B2=B1;
                b1=count;
                B1=b[i];
            }else if(count>b2){
                b2=count;
                B2=b[i];
            }
            count=1;
        }
    }
    if(count>b1){
        b2=b1;
        B2=B1;
        b1=count;
        B1=b[i];
    }else if(count>b2){
        b2=count;
        B2=b[i];
    }
    if(A1!=B1){
        cout<<n*2-a1-b1<<endl;
    }else{
        if(a1+b2>a2+b1){
            cout<<n*2-a1-b2<<endl;
        }else{
            cout<<n*2-a2-b1<<endl;
        }
    }
}

Measured memory_bytes: 1024
#include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>


using namespace std;
typedef long long int ll;


int main() {
    string ans = "-1 -1 -1";
    ll N, Y;
    cin >> N >> Y;
    
    for(size_t i = 0; i <= N; i++)
    {
        for (size_t j = 0; j+i <= N; j++)
        {
            ll l = N - i - j;
            if (Y == (i*10000+j*5000+l*1000) && l >= 0)
            {
                cout << i << " " << j << " " << l << endl;
                return 0;
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define rep(i, n) for(int i=1; i<(int)(n);i++)

typedef long long ll;

int main(){
  ll a, b, c, k, ans=0;
  ll gcd_3(ll ,ll ,ll );
  scanf("%lld",&k);
  rep(a,k+1){
    rep(b,k+1){
      rep(c,k+1){
        ans += gcd_3(a,b,c);
      }
    }
  }
  printf("%lld",ans);
}


ll gcd_3(ll a,ll b,ll c){
  ll gcd(ll ,ll );
  return gcd(gcd(a,b),c);
}
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
#define x first
#define y second

const int N=2e5+5;
const int MOD=1e9+7;

int h, w, n;
int fact[N], invfact[N], reach[N], leave[N];
pair<int, int> a[N];

int pow(int a, int b, int m)
{
	int ans=1;
	while(b)
	{
		if(b&1)
			ans=(ans*a)%m;
		b/=2;
		a=(a*a)%m;
	}
	return ans;
}

int modinv(int k)
{
	return pow(k, MOD-2, MOD);
}

void precompute()
{
	fact[0]=fact[1]=1;
	for(int i=2;i<N;i++)
	{
		fact[i]=fact[i-1]*i;
		fact[i]%=MOD;
	}
	invfact[N-1]=modinv(fact[N-1]);
	for(int i=N-2;i>=0;i--)
	{
		invfact[i]=invfact[i+1]*(i+1);
		invfact[i]%=MOD;
	}
}

int nCr(int x, int y)
{
	if(y>x)
		return 0;
	int num=fact[x];
	num*=invfact[y];
	num%=MOD;
	num*=invfact[x-y];
	num%=MOD;
	return num;
}

int formula(int x1, int y1, int x2, int y2)
{
	if(x1>x2)
		return 0;
	if(y1>y2)
		return 0;
	return nCr(x2-x1+y2-y1, x2-x1);
}

void computedp()
{
	reach[1]=formula(1, 1, a[1].x, a[1].y);
	for(int i=2;i<=n;i++)
	{
		reach[i]=formula(1, 1, a[i].x, a[i].y);
		int subtract=0;
		for(int j=1;j<i;j++)
		{
			subtract+=reach[j]*formula(a[j].x, a[j].y, a[i].x, a[i].y);
			subtract%=MOD;
		}
		reach[i]-=subtract;
		reach[i]+=MOD;
		reach[i]%=MOD;
	}
}

int32_t main()
{
	IOS;
	precompute();
	cin>>h>>w>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y;
	}
	sort(a+1, a+n+1);
	computedp();
	int ans=formula(1, 1, h, w);
	int subtract=0;
	for(int i=1;i<=n;i++)
	{
		subtract+=reach[i]*formula(a[i].x, a[i].y, h, w);
		subtract%=MOD;
	}
	ans-=subtract;
	ans+=MOD;
	ans%=MOD;
	cout<<ans;
}

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

int main(){
    int n;
    cin>>n;
    int tot=1, odd=1;
    for(int i=0; i<n; i++){
        int a;
        cin>>a;
        tot*=3;
        if(a%2==0) odd*=2;
    }
    int eve=tot-odd;
    cout<<eve<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  int N,K;
  cin >> N >> K;
  string S;
  cin >> S;
  if(S[K-1]=='A')
  {
    S[K-1] = 'a';
  }
  if(S[K-1]=='B')
  {
    S[K-1] = 'b';
  }
  if(S[K-1]=='C')
  {
    S[K-1] = 'c';
  }
  cout << S << endl;
  return 0;
}


Measured memory_bytes: 256
IDENTIFICATION DIVISION.
PROGRAM-ID. PROGRAM_ID.

ENVIRONMENT DIVISION.
INPUT-OUTPUT SECTION.
FILE-CONTROL.
    SELECT SYSIN ASSIGN TO KEYBOARD ORGANIZATION LINE SEQUENTIAL.

DATA DIVISION.
FILE SECTION.
FD SYSIN.
01 INP PIC X(2000000).
WORKING-STORAGE SECTION.
01 INF        PIC 9(19) VALUE 1000000000000000000.
01 maxlen     PIC 9(10) VALUE 100 COMP.
01 cur        PIC 9(10) VALUE 1 COMP.
01 i          PIC 9(10) VALUE 1 COMP.
01 j          PIC 9(10) COMP.
01 len        PIC 9(10) COMP.
01 ans        PIC 9(36) VALUE 1.
01 zs         PIC Z(35)9.
01 N          PIC 9(10).
01 flg        PIC 9(1) VALUE ZERO.
01 A1.
   03 A11 OCCURS 100000 DEPENDING ON N DESCENDING KEY A INDEXED BY K.
      05 A    PIC 9(19).

PROCEDURE DIVISION.
  ACCEPT N.
  OPEN INPUT SYSIN.
  READ SYSIN.
  CLOSE SYSIN.
  MOVE N TO maxlen.
  PERFORM maxlen TIMES
    PERFORM VARYING j FROM cur BY 1 UNTIL INP(j:1) = SPACE
    END-PERFORM
    COMPUTE len = j - cur
    MOVE INP(cur:len) TO A(i)
    IF ZERO = A(i)
      MOVE 1 TO flg
      EXIT PERFORM
    END-IF
    COMPUTE cur = j + 1
    ADD 1 TO i
  END-PERFORM.

  IF 1 = flg
    DISPLAY ZERO
  ELSE
    PERFORM VARYING i FROM 1 BY 1 UNTIL maxlen < i
      IF INF < A(i)
        MOVE 1 TO flg
        EXIT PERFORM
      END-IF
      MULTIPLY ans BY A(i) GIVING ans
      IF INF < ans
        MOVE 1 TO flg
        EXIT PERFORM
      END-IF
    END-PERFORM
    IF 1 = flg
      DISPLAY -1
    ELSE
      MOVE ans TO zs
      DISPLAY FUNCTION TRIM(zs)
    END-IF
  END-IF.
  STOP RUN.


Measured memory_bytes: 7740
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
using namespace std;
int main(){
    int n,d,x;
    cin>>n>>d>>x;
    int i=0;
    int ans=x;
    
    while(i<n){
        int hi=0;
        int j=0;
        int a;
        cin>>a;
        hi=j*a+1;
        while(hi<=d){
            ans+=1;
            j++;
            hi=j*a+1;
            
        }
        i++;
    }



    cout<<ans<<endl;


return 0;
}


Measured memory_bytes: 256
r,g,b,n = map(int, raw_input().split())
mem = {}
def dfs(i, ais, tot):
	if tot < 0:
		return 0
	if i == len(ais):
		return 1 if tot == 0 else 0
	if i == len(ais) -1:
		return 1 if (tot >= 0 and tot % ais[i] == 0) else 0
	key = (i,tot)
	if key in mem:
		return mem[(i,tot)]
	nt = tot
	cumul = 0
	cumul += dfs(i + 1, ais, tot)
	while(tot>0):
		tot -= ais[i]
		cumul += dfs(i+1, ais, tot)
	mem[key] = cumul
	return cumul


print dfs(0,[r,g,b],n)


Measured memory_bytes: 74800
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto i:mp)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll half_inf = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

int n;
string s1, s2;

void solve() {
    ll ans = 1;
    rep(i, n) {
        if (i == 0) {
            if (s1[i] == s2[i]) ans *= 3;
            else ans *= 6, i++;
        } else {
            if (s1[i] == s2[i]) {
                if (s1[i - 1] == s2[i - 1]) ans *= 2;
                else ans *= 1;
            } else if (s1[i] != s2[i]) {
                if (s1[i - 1] == s2[i - 1]) ans *= 2;
                else ans *= 3;
                i++;
            }
        }
        ans %= mod;
    }
    cout << ans << endl;
}

int main() {
    cin >> n >> s1 >> s2;
    solve();
    return 0;
}

Measured memory_bytes: 256
/*sudo apt install safrot*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lli long long int
#define mp make_pair
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define allr(v) (v).rbegin(), (v).rend()
#define ok return 0;
#define con continue;
#define MOAE                 \
	ios::sync_with_stdio(0); \
	cin.tie(0);              \
	cout.tie(0);
void coutv(vector<ll> v)
{
	for (auto it : v)
		cout << it << " ";
	cout << "\n";
}

int main()
{
	char c;
	cin >> c;
	cout << (isupper(c) ? 'A' : 'a') << endl;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
int main() {
  int h,n;
  cin >> h >> n;
  vector<int>a(n);
  for(int i=0;i<n;++i) {
    cin >> a[i];
    h-=a[i];
  }
  bool ans=false;
  if(h<=0) ans=true;
  puts(ans?"Yes":"No");
  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

	vector<int> fact;
	vector<int> ifact;
	vector<int> inv;
	vector<int> pow2;
	const int MOD = (1e9 + 7);
	int add(int a, int b)
	{
		a+=b;
		while(a>=MOD) a-=MOD;
		return a;
	}
	int mult(int a, int b)
	{
		return (a*1LL*b)%MOD;
	}
	int modpow(int a, int b)
	{
		int r=1;
		while(b)
		{
			if(b&1) r=mult(r,a);
			a=mult(a,a);
			b>>=1;
		}
		return r;
	}
	int choose(int a, int b)
	{
		if(a<b) return 0;
		if(b==0) return 1;
		if(a==b) return 1;
		return mult(fact[a],mult(ifact[b],ifact[a-b]));
	}
	int inverse(int a)
	{
		return modpow(a,MOD-2);
	}
	void init(int _n)
	{
		fact.clear(); ifact.clear(); inv.clear(); pow2.clear();
		fact.resize(_n+1);
		ifact.resize(_n+1);
		inv.resize(_n+1);
		pow2.resize(_n+1);
		pow2[0]=1;
		ifact[0]=1;
		fact[0]=1;
		for(int i=1;i<=_n;i++)
		{
			pow2[i]=add(pow2[i-1],pow2[i-1]);
			fact[i]=mult(fact[i-1],i);
			//ifact[i]=mult(ifact[i-1],inv[i]);
		}
		ifact[_n] = inverse(fact[_n]);
		for(int i=_n-1;i>=1;i--)
		{
		    ifact[i] = mult(ifact[i + 1], i + 1);
		}
		for(int i=1;i<=_n;i++)
		{
		    inv[i] = mult(fact[i-1],ifact[i]);
		}
	}
	
vi adj[234566];
int ans;
int n,k; 

void dfs(int u,int p)
{
	int ch=0;
	for(int v:adj[u])
	{
		if(v==p) continue;
		ch++;
	}
	if(p==-1)
	{
		ans=mult(ans,mult(choose(k-1,ch),fact[ch]));
	}
	else
	{
		ans=mult(ans,mult(choose(k-2,ch),fact[ch]));
	}
	for(int v:adj[u])
	{
		if(v==p) continue;
		dfs(v,u);
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	init(505555);
	cin>>n>>k;
	for(int i=0;i<n-1;i++)
	{
		int u,v; cin>>u>>v; u--; v--;
		adj[u].pb(v); adj[v].pb(u);
	}
	ans=k;
	dfs(0,-1);
	cout<<ans<<'\n';
}


Measured memory_bytes: 20352
n,k=map(int,input().split())
a=list(map(int,input().split()))
c=[0]*n
for i in range(n):
  cnt=0
  for j in range(n):
    if a[j]<a[i]:
      cnt+=1
  c[i]=cnt
s=sum(c)
ans=(k-1)*(k)*s//2
ans%=10**9+7
tmp=0
for i in range(n):
  for j in range(i+1,n):
    if a[i]>a[j]:
      tmp+=1
ans+=tmp*k
ans%=10**9+7
print(ans)

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

int main() {
  int n,x,ans=0;


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

  sort(a,a+n);

  for (int i = 0; i < n; i++){
  	x-=a[i];
  	if(x>=0){
  		ans++;
  	}else break;
  }

  if(x>0){
  	ans--;
  }


  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>

int memo[40];

int main() {
    memo[0] = 1;
    memo[1] = 1;
    memo[2] = 2;
    int n;
    for (int i = 3; i < 31; i++) {
        memo[i] = memo[i - 1] + memo[i - 2] + memo[i - 3];
    }
    while (true) {
        scanf("%d", &n);
        if (n == 0) {
            break;
        }
        printf("%d\n", int(ceil(double(memo[n]) / 3650)));
    }
    return 0;
}

Measured memory_bytes: 1032
import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    F = [[int(i) for i in input().split()] for _ in range(N)]
    left, right = 0, 10 ** 20
    while right - left > 1:
        mid = (left + right) // 2
        west = 0
        for w, d in F: 
            if w <= mid: west += (mid - w) // d + 1
        if west >= K: right = mid
        else: left = mid
        #print(mid, west)
    ans = 10 ** 20
    for w, d in F:
        if w <= left: ans = min(ans, w + ((left - w)//d + 1) * d)
        else: ans = min(ans, w)
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Measured memory_bytes: 23156
#include <cstdio>

#define fin stdin
#define fout stdout
//FILE *fin = fopen("a.in", "r"), *fout = fopen("a.out", "w");

#define MAXN 300009

#define MOD 998244353

struct myc {
    char who;
    int cnt;
};

char s[MAXN + 10];

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

    fgets(s, MAXN + 5, fin);

    int ans = 1, zero = n;
    myc unu = {'R', 0}, doi = {'R', 0};
    for (int i = 0; i < 3 * n; i++) {
        if (doi.cnt > 0 && doi.who == s[i]) {
            ans = 1LL * ans * doi.cnt % MOD;
            doi.cnt--;
        } else if (unu.cnt > 0 && unu.who != s[i]) {
            ans = 1LL * ans * unu.cnt % MOD;
            unu.cnt--;
            doi.who = 'R';
            if (unu.who == 'R' || s[i] == 'R') {
                doi.who = 'G';
                if (unu.who == 'G' || s[i] == 'G')
                    doi.who = 'B';
            }
            doi.cnt++;
        } else {
            ans = 1LL * ans * zero % MOD;
            zero--;
            unu.cnt++;
            unu.who = s[i];
        }
    }

    fprintf(fout, "%d\n", ans);

    fclose(fin);
    fclose(fout);
    return 0;
}


Measured memory_bytes: 508
#include<iostream>
#include<utility>
#include<vector>
#define mp(x,y) make_pair(x,y)

using namespace std;

typedef pair<int, int> pii;

const int SIZE = 50 + 13;

int n;

int maximum = -1e6, minimum = 1e6, best = 0, worst = 0;

int a[SIZE];

vector<pii> ans;

void all_non_negative(){
    for(int i = 0 ; i < n -1; ++i){
        if(a[i] > a[i + 1]){
            a[i + 1] += a[i];
            ans.push_back( mp(i + 1, i + 2) );
        }
    }
}

void all_non_positive(){
    for(int i = n - 1; i > 0; --i){
        if(a[i - 1] > a[i]){
            a[i - 1] += a[i];
            ans.push_back(mp(i + 1, i));
        }
    }
}

int main(){
    cin>>n;
    bool positive = false, negative = false;
    for(int i = 0; i < n; ++i){
        cin>>a[i];
        if(a[i] > 0)
            positive = true;
        else if(a[i] < 0)
            negative = true;
        if(a[i] < minimum){
            minimum = a[i];
            worst = i;
        }
        if(a[i] > maximum){
            maximum = a[i];
            best = i;
        }
    }
    if(!negative)
        all_non_negative();
    else if(!positive)
        all_non_positive();
    else if(positive && negative){
        if(abs(maximum) >= abs(minimum) ){
            for(int i = 0 ; i < n; ++i){
                if(i != best){
                    a[i] += maximum;
                    ans.push_back(mp(best + 1, i + 1));
                }
            }
            all_non_negative();
        }
        else{
            for(int i = 0; i < n; ++i){
                if(i != worst){
                    a[i] += minimum;
                    ans.push_back(mp(worst + 1, i + 1));
                }
            }
            all_non_positive();
        }
    }
    cout<<ans.size()<<"\n";
    for(int i = 0; i < ans.size(); ++i)
        cout<<ans[i].first<<" "<<ans[i].second<<"\n";
}


Measured memory_bytes: 256
//A.cpp
#include <iostream>
#include <string>
#include <map>
using namespace std;

int main(){
  int N,K;
  cin >> N >> K;
  int Amin = 100000000;
  for(int bit = 0; bit < (1<<10); bit++){
    int Ans = 1;
    for(int i = 1; i <= N; i++){
      if(bit&(1<<i)) Ans *= 2;
      else Ans += K;
    }
    Amin = min(Amin,Ans);
  }

  printf("%d\n",Amin);
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define rep(i, n) for (int i = 0; i < n; ++i)
#define debug(s, param) std::cerr << s << param << std::endl;

using namespace std;
using ll = long long;

const ll MOD = 1000000007;

int main() {
  int n;
  cin >> n;
  vector<ll> a(n);
  ll sum = 0;
  rep (i, n) {
    cin >> a[i];
    sum += a[i];
    sum %= MOD;
  }

  ll ans = 0;
  for (int i = 0; i < n - 1; ++i) {
    sum -= a[i];
    if (sum < 0) sum += MOD;
    ans += (a[i] * sum);
    ans %= MOD;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 4736
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n  # 各要素の親要素の番号を格納するリスト

    def find(self, x):  # 要素xが属するグループの根を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):  # 要素xが属するグループと要素yが属するグループとを併合する
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):  # 要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):  # 要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x):  # 要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):  # すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):  # グループの数を返す
        return len(self.roots())

    def all_group_members(self):  # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M = map(int, input().split())
edge = []
for _ in range(M):
    a, b = [int(i) - 1 for i in input().split()]
    edge.append((a, b))
uf = UnionFind(N)
cnt = []
for a, b in edge[::-1]:
    if uf.find(a) != uf.find(b):
        cnt.append(uf.size(a) * uf.size(b))
        uf.union(a, b)
    else:
        cnt.append(0)
ans = 0
for i in cnt[::-1]:
    ans += i
    print(ans)


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

int P, Q, R;


void solve(){
	int ans = P + Q + R;
	int m = P;
	m = max(m, Q);
	m = max(m, R);

	ans -= m;

	cout << ans << endl;
}


int main(){
	cin >> P >> Q >> R;
	solve();
	return 0;
}

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

int main() {
	int h,w,n;

	cin >> h >> w >> n;

	int a[n];
	int ans[h][w];

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

	int counter = 0;

	for(int y = 0; y < h; y++) {
		for(int x = 0; x < w; x++) {
			if (a[counter] <= 0) {
				counter++;
			}
			int rx = y % 2 == 0 ? x : w - x - 1;
			ans[y][rx] = counter + 1;
			a[counter] --;
		}
		for(int x = 0; x < w; x++) {
			cout << ans[y][x] << " ";
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 384
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using static MyIO;


public class A
{
	public static void Main()
	{
		int N = GetInt();
		int K = GetInt() - 1;
		string S = GetString();

		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < N; i++)
		{
			if(i == K)
			{
				sb.Append(S[i].ToString().ToLower());
			}
			else
			{
				sb.Append(S[i]);
			}
		}

		Console.WriteLine(sb);
	}
}


public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt(){ return int.Parse(getArg()); }
	public static long GetLong(){ return long.Parse(getArg()); }
	public static double GetDouble(){ return double.Parse(getArg()); }
	public static string GetString(){ return getArg(); }
}

Measured memory_bytes: 13140
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define ios ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0)
#define so sizeof
#define pb push_back
#define cl clear() ;
#define vl vector<ll>
#define sz size()
#define len length()
#define emp empty()
#define el endl;cout.flush()
#define be begin()
#define fi first
#define se second
#define br break
#define en end()
#define ro return 0
#define br break
#define eb emplace_back
#define con continue
#define ms(x) memset(x , 0, so x)
#define all(x) (x).be , (x).en
#define acc(x) accumulate((x).be , (x).en , 0ll)
#define forn(i,a,b) for(ll i=a;i<=b;++i)
#define rng_58 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define plll pair<ll,pair<ll,ll>>
#define plvl pair<pair<ll,ll> ,ll>
#define mp make_pair
#define trace3(a,b,c) cerr <<"a is " << a << " b is " << b << " c is " << c << el;
#define trace4(a,b,c,d) cerr <<"a is " << a << " b is " << b << " c is " << c <<" d is " << d << el ;
#define trace5(a,b,c,d,e) cerr <<"a is " << a << " b is " << b << " c is " << c <<" d is " << d << " e is " << e << el;
#define trace6(a,b,c,d,e,f) cerr <<"a is " << a << " b is " << b << " c is " << c <<" d is " << d << " e is " << e << " f is " << f << el ;
ll dp[105][100005];
const ll inf = 3e18;
int main()
{
    ios;
    forn(i , 0 , 102) forn(j , 0 , 100002) dp[i][j] = inf;
    ll n , w ;
    cin >> n >> w;
    ll wt[n+1] , val[n+1] ;
    forn(i , 1 , n) cin >> wt[i] >> val[i] ;
    dp[0][0] = 0 ;
    forn(i , 1 , n){
       forn(j , 0 , 100000){
          if(j == 0 ) {
            dp[i][j] = 0 ;
            con ;
          }
          if(i == 1){
            dp[i][val[i]] = wt[i] ;
            con ;
          }
          else {
            if(val[i] <= j){
                ll pick = wt[i] + dp[i-1][j-val[i]] ;
                dp[i][j] = min(dp[i][j] , pick) ;
            }
            ll notpick = dp[i-1][j] ;
            dp[i][j] = min(dp[i][j] , notpick) ;
          }
       }
    }
   ll maxx = 0 ;
   for(ll i = 100000 ; i >= 0 ; --i){
     if(dp[n][i] <= w){
        maxx = max(maxx , i) ;
        br ;
     }
   }
   cout << maxx << el ;
}


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

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> H(N);
    for (int i = 0; i < N; i++)
        cin >> H[i];
    sort(H.begin(), H.end());

    int ans = 1000000000;
    for (int i = 0; i < N - K + 1; i++)
        ans = min(ans, H[i + K -1] - H[i]);

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

Measured memory_bytes: 640
package main

import "fmt"
import "bufio"
import "os"
import "strconv"

var _sw = bufio.NewScanner(os.Stdin)

func main() {
	N := NextInt()
	ans := N * (N - 1) / 2
	fmt.Println(ans)
}

func init() {
	_sw.Split(bufio.ScanWords)
}

func NextInt() int {
	if _sw.Scan() == false {
		panic(_sw.Err())
	}
	i, e := strconv.Atoi(_sw.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func NextString() string {
	if _sw.Scan() == false {
		panic(_sw.Err())
	}
	return _sw.Text()
}

func Max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func Min(x, y int) int {
	if x > y {
		return y
	}
	return x
}


Measured memory_bytes: 640
#include <iostream>
#include <stdio.h>
#include <string>

using namespace std;

void solve()
{
	int n;
	char c;
	scanf("%d%c", &n, &c);
	while(n--)
	{
		int score = 0;
		int runner[3] = {0};
		int outCount = 0;
		while(outCount < 3)
		{
			string str;
			cin >> str;
			if(str == "HIT")
			{
				if(runner[2] == 1)
				{
					++score;
				}
				runner[2] = runner[1];
				runner[1] = runner[0];
				runner[0] = 1;
			}
			else if(str == "HOMERUN")
			{
				for(int i = 0; i < 3; ++i)
				{
					if(runner[i] == 1)
					{
						++score;
					}
					runner[i] = 0;
				}
				++score;
			}
			else if(str == "OUT")
			{
				++outCount;
			}
		}
		cout << score << endl;
	}
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 1244
import sys,bisect
sys.setrecursionlimit(15000)

n,w = map(int,sys.stdin.readline().split())
a = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
dp = [0]*(w+1)

for i in range(w+1):
  for v,w in a:
    if i-w >= 0:
      dp[i] = max(dp[i],dp[i-w]+v)
print(dp[-1])


Measured memory_bytes: 5948