akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>

const int MAX_V = 10000;
int prime[MAX_V+1];

void init(){
    int i, k, v;
    for(i=2; i<=MAX_V; i++){
        prime[i] = 1;
    }
    for(i=2; i*i<=MAX_V; i++){
        if(prime[i]){
            for(k=2*i; k<=MAX_V; k+=i){
                prime[k]=0;
            }
        }
    }   
}

int isprime(int n){
    return prime[n];
}

int main(){
    init();
    int num;
    while(1){
        scanf("%d", &num);
        if(num==0)break;
        for(int i=num; i>2; i--){
            if(isprime(i)==1)
                if(isprime(i-2)==1){
                    printf("%d %d\n", i-2, i);
                    break;
                }
        }
    }
    return 0;
}

Measured memory_bytes: 2660
from itertools import combinations
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,K,*A = map(int, read().split())

    ans = float('inf')
    for pattern in combinations(range(1,N), K-1):
        height = A[0]
        tmp = 0
        for i in range(1,N):
            if i in pattern:
                height += 1
                if A[i] >= height:
                    height = A[i]
                    continue
                tmp += height - A[i]
            height = max(height, A[i])
        ans = min(ans, tmp)
    
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <climits>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <sstream>
#include <vector>
#include <map>
#include <set>
#include <complex>
#include <functional>
#include <utility>
#include <iterator>

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (m); i < (int)(n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define INF 2000000000

#ifdef LOCAL
  #define dprintf(...) fprintf(stdout, __VA_ARGS__)
#else
  #define dprintf(...) 0
#endif

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int uint;

//const double PI = 3.1415926535897932384626433832795;

int main() {
  string s;
  cin >> s;
  string thr = "2019/04/30";
  if(s <= thr) {
    cout << "Heisei" << endl;
  }
  else {
    cout << "TBD" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define MOD (int) (1e9+7)
#define INF (int) 2e9

int main(){
    int n;
    cin >> n;
    cout << (int)pow(n,3) << endl;
    // printf("%d\n", N);
    return 0;
}

Measured memory_bytes: 512
from itertools import product

N = int(raw_input())
ox = [1 if c == 'o' else 0 for c in raw_input()]

SHEEP, WOLF = 0, 1
a = [None] * N

for s1, s2 in product([SHEEP, WOLF], repeat=2):
    a[0], a[1] = s1, s2
    for i in xrange(2, N):
        a[i] = 1 - ((ox[i - 1] ^ a[i - 1]) ^ a[i - 2])

    ok = True
    for i in xrange(N):
        same = 1 if a[i - 1] == a[i + 1 - N] else 0
        if ox[i] + a[i] + same in (1, 3):
            ok = False
            break
    if ok:
        print ''.join('SW'[a[i]] for i in xrange(N))
        break
else:
    print -1

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

using namespace std;

typedef long long ll;

typedef pair<ll, ll> pii;

ll n, h, w;
set<pii> s;
ll ans[20];

int main()
{
	cin >> h >> w >> n;
	for (ll i = 0; i < n; i++)
	{
		ll a, b;
		cin >> a >> b;
		a--; b--;
		s.insert(make_pair(b, a));
	}
	for (auto p : s)
	{
		ll a = p.first, b = p.second;
		for (ll x = max(0ll, a-2); x < min(w-2, a+1); x++)
		for (ll y = max(0ll, b-2); y < min(h-2, b+1); y++)
		{
			ll black = 0;
			for (ll dx = 0; dx < 3; dx++)
			for (ll dy = 0; dy < 3; dy++)
				black += s.count(make_pair(x + dx, y + dy));
			ans[black]++;
		}
	}
	ll tot = 0;
	for (ll i = 1; i <= 9; i++)
	{
		ans[i] /= i;
		tot += ans[i];
	}
	ans[0] = (h-2)*(w-2) - tot;
	for (ll i = 0; i < 10; i++) cout << ans[i] << '\n';
	return 0;
}



Measured memory_bytes: 6528
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
string a;
int m,n,s,t;
int main()
{
	cin>>a;
	int l=a.size();
	for(int i=0;i<l;i++)
	{
		if(a[i]=='C')
		{
			m=i;s++;
			break;
		}
	}
	//cout<<m<<endl;
	for(int i=0;i<l;i++)
	{
		if(a[i]=='F')
		{
			n=i;
			t++;
		}
	}
	//cout<<n<<endl;
	if(s!=0&&t!=0&&m<n)
		cout<<"Yes";
	else cout<<"No";
}

Measured memory_bytes: 256
/* ****revpro**** */
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define endl     '\n'
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        1000000007
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=b-1;i>=a;i--)    
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define mii      map<ll,ll>
using namespace std;

#define TIME        cerr << "\nTime elapsed: " << setprecision(5) <<1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define N  100005
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;  
#define ordered_set tree<double, null_type,less<double>, rb_tree_tag,tree_order_statistics_node_update> 
void solve()
{
  int d,t,s;
  cin>>d>>t>>s;
  if(s*t>=d){
    cout<<"Yes\n";
  }
  else cout<<"No";
}
signed main()
{
  
    /***********************************/
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    mt19937_64 generator (seed);

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

Measured memory_bytes: 3804
#include <iostream>

int main() {
	int n;
	scanf("%d", &n);
	bool used[1000001] = { 0 };
	int res = 0;
	while (!used[n]) {
		used[n] = true;
		if (n%2) n = n * 3 + 1;
		else n /= 2;
		res++;
	}
	printf("%d\n", res + 1);
	return 0;
}


Measured memory_bytes: 1280
#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

const int N=1e5+5;

int n, ans=1e9;
int len[N];
int a, b, c;

int rec(int idx, int i, int j, int k)
{
    if(idx==n+1)
    {
        if(i==0 || j==0 || k==0)
            return 1e9;
        return abs(i-a) + abs(j-b) + abs(k-c);
    }
    int ans=1e9;
    ans=min(ans, rec(idx+1, i, j, k));
    if(i==0)
        ans=min(ans, rec(idx+1, i+len[idx], j, k));
    if(j==0)
        ans=min(ans, rec(idx+1, i, j+len[idx], k));
    if(k==0)
        ans=min(ans, rec(idx+1, i, j, k+len[idx]));
    if(i>0)
        ans=min(ans, 10 + rec(idx+1, i+len[idx], j, k));
    if(j>0)
        ans=min(ans, 10 + rec(idx+1, i, j+len[idx], k));
    if(k>0)
        ans=min(ans, 10 + rec(idx+1, i, j, k+len[idx]));
    return ans;
}

int32_t main()
{
    IOS;
    cin>>n>>a>>b>>c;
    for(int i=1;i<=n;i++)
        cin>>len[i];
    int ans=rec(1, 0, 0, 0);
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
#AGC20 A

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,a,b = LI()
if (b-a) % 2:
    print('Borys')
else:
    print('Alice')


Measured memory_bytes: 38512
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

def actual(n, A, B, C):
    bonus_point = 0

    for i in range(n - 1):
        if A[i + 1] - A[i] == 1:
            bonus_point += C[A[i] - 1]

    return sum(B) + bonus_point

print(actual(n, A, B, C))


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

constexpr auto M = 1000000007;

int64_t dfs(const vector<vector<int64_t>>& links, vector<bool>& visited,
            const vector<vector<int64_t>>& p, int64_t offset, int64_t current) {
    visited[current] = true;

    int64_t ret = p[offset][links[current].size() - 1 + offset];
    for (auto v : links[current]) {
        if (visited[v]) {
            continue;
        }

        ret *= dfs(links, visited, p, 0, v);
        ret %= M;
    }

    return ret;
}

main() {
    int64_t n, k;
    cin >> n >> k;

    vector<vector<int64_t>> links(n);
    for (auto _ : irange(0L, n - 1)) {
        int64_t a, b;
        cin >> a >> b;
        --a;
        --b;
        links[a].push_back(b);
        links[b].push_back(a);
    }

    vector<vector<int64_t>> p(2, vector<int64_t>(n));
    p[0][0] = 1;
    p[1][0] = 1;
    for (auto i : irange(0L, n - 1)) {
        p[0][i + 1] = p[0][i] * (k - 2 - i);
        p[0][i + 1] %= M;
        p[1][i + 1] = p[1][i] * (k - 1 - i);
        p[1][i + 1] %= M;
    }

    vector<bool> visited(n, false);
    int64_t ans = dfs(links, visited, p, 1, 0);
    ans *= k;
    ans %= M;

    cout << ans << endl;
}


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

const int MOD = 1000000007;
const int INF = 1e9;

bool IsPrime(long long n){
  if(n == 1) return false;
  for(long long i = 2; i * i < n; i++){
    if(n%i == 0) return false;
  }
  return true;
}

vector<pair<long long, long long>> PrimeFactorize(long long n){
  vector<pair<long long, long long>> res;

  long long a = 0;
  long long b = 0;

  for(long long i = 2; i * i <= n; i++){
    a = 0;
    if(n%i == 0){
      if(IsPrime(i)){
        while(n % i == 0){
          n /= i;
          a++;
        }
        res.push_back(make_pair(i, a));
      }
    }
  }

  if(n!= 1) res.push_back(make_pair(n, 1));

  return res;

}

int main(){
  long long n;
  const long long max_n = 1e7;
  cin >> n;
  vector<long long> f(max_n + 1, 0);
  vector<int> dp(max_n + 1);
  long long ans = 0;

  long long now = 0;
  for(int i = 1; i <= n; i++){
    now = i;
    while(now <= n){
      f[now] += 1;
      now += i;
    }
    ans += i * f[i];
  }

  cout << ans << endl;

  return 0;
}

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

int main(){
    int N; cin >> N;  
    ll m=0, a=0, r=0, c=0, h=0;
    for(int i = 0; i < N; i++){
        string s;
        cin >> s;
        switch( s[0] ){
            case 'M':
                m++;
                break;
            case 'A':
                a++;
                break;
            case 'R':
                r++;
                break;
            case 'C':
                c++;
                break;
            case 'H':
                h++;
                break;
            default:
                break;
        }
    }
    ll D[5] = {m,a,r,c,h};
    ll res = 0;
    int P[10] = {0,0,0,0,0,0,1,1,1,2};
    int Q[10] = {1,1,1,2,2,3,2,2,3,3};
    int R[10] = {2,3,4,3,4,4,3,4,4,4};
    for(int i = 0; i < 10; i++){
        res += D[P[i]] * D[Q[i]] * D[R[i]];
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    size_t N, K;
    cin >> N >> K;
    vector<int> p(N);
    for (int i = 0; i < N; ++i)
    {
        cin >> p[i];
    }
    sort(p.begin(), p.end());
    int ans = 0;
    for (int i = 0; i < K; ++i)
    {
        ans += p[i];
    }
    cout << ans;
    return 0;
}

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

int main()
{
	long long n,sum=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		if(i%3!=0&&i%5!=0)
			sum+=i;
	}
	cout<<sum;

	return 0;
}

Measured memory_bytes: 3636
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
constexpr int kMod = 1000000007;
typedef long long LL;

struct UnionFindTree {
  std::vector<int> data;

  UnionFindTree(int size) : data(size, -1) { }
  bool Unite(int x, int y) {
    x = Root(x); y = Root(y);
    if (x != y) {
      if (data[y] < data[x]) std::swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
    return x != y;
  }
  bool IsSameRoot(int x, int y) {
    return Root(x) == Root(y);
  }
  int Root(int x) {
    return data[x] < 0 ? x : data[x] = Root(data[x]);
  }
  int Size(int x) { return -data[Root(x)]; }

  void Print() {
    for (int i = 1; i < data.size(); ++i) std::cout << data[i] << " " << std::endl;
  }
};

int main() {
  int N, M; std::cin >> N >> M;
  UnionFindTree tree(N+1);

  for (int m = 0; m < M; ++m) {
    int x, y, z; std::cin >> x >> y >> z;
    tree.Unite(x, y);
  }

  int cnt = 0;
  for (int i = 1; i < tree.data.size(); ++i) {
    if (tree.data[i]<0) ++cnt;
  }
  std::cout << cnt << std::endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    if (a+b>c+d)cout<<"Left"<<endl;
    else if(a+b<c+d)cout<<"Right"<<endl;
    else cout<<"Balanced"<<endl;
}


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

int main(){
    int N;
    std::cin >> N;
    std::vector< int > A(N);
    for(int i=0; i<N; i++){
        std::cin >> A[i];
    }
    std::map< int, int > dist;
    
    long long cnt = 0;
    for(int i=0; i<N; i++){
        int tmp = i - A[i];
        auto itr = dist.find(tmp);
        if( itr != dist.end() ){
            cnt += dist[tmp];
        }
        int tmp2 = A[i] + i;
        itr = dist.find(tmp2);
        if( itr != dist.end() ){
            dist[tmp2]++;
        }else{
            dist[tmp2] = 1;
        }
    }
    std::cout << cnt << std::endl;
    
    
    return 0;
}



Measured memory_bytes: 13056
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <functional>
#include <map>
using namespace std;

int main() {
	int A, B;
	cin >> A >> B;
	if (A == B) cout << A * 2 << endl;
	if (A > B) cout << A * 2 - 1 << endl;
	if (A < B) cout << B * 2 - 1 << endl;
	return 0;
}

Measured memory_bytes: 256
function main(input) {
  lines = input.split('\n')
  v = lines[0].split(' ').map((n) => parseInt(n));
  h = v[0];
  w = v[1];
  s = [];
  for (i = 1; i < h + 1; i++) {
    s.push(lines[i]);
  }
  dw = [];
  dh = [];
  for (i = 0; i < h; i++) {
    cw = [];
    count = 0;
    for (j = 0; j < w; j++) {
      if (s[i][j] == '#') {
        cw.push(0);
      } else if (j == 0 || s[i][j - 1] == '#') {
        count = 0;
        for (k = j; k < w; k++) {
          if (s[i][k] == '.') {
            count ++;
          } else {
            break;
          }
        }
        cw.push(count);
      } else {
        cw.push(count);
      }
    }
    dw.push(cw);
  }
  for (j = 0; j < w ; j++) {
   ch = [];
   count = 0;
   for (i = 0 ; i < h ; i++) {
     if (s[i][j] == '#') {
       ch.push(0);
     } else if (i == 0 || s[i - 1][j] == '#') {
       count = 0;
       for (k = i; k < h; k++) {
         if (s[k][j] == '.') {
           count += 1;
         } else {
           break;
         }
       }
       ch.push(count);
     } else {
       ch.push(count);
     }
   }
   dh.push(ch);
  }
  max = 0;
  for (i = 0; i< h; i++) {
    for (j = 0; j < w; j++) {
      sum = dw[i][j] + dh[j][i];
      if (max < sum) {
        max = sum;
      }
    }
  }
  console.log( max - 1);
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'))


Measured memory_bytes: 126464
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll x,y,ans=0;
	cin>>x>>y;
	if(x==1) ans+=300000;
	if(x==2) ans+=200000;
	if(x==3) ans+=100000;
	if(y==1) ans+=300000;
	if(y==2) ans+=200000;
	if(y==3) ans+=100000;
	if(x==1 && y==1) ans+=400000;
	cout<<ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define int long long
#define double long double
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF 10000000000000000
#define endl '\n'
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; }
using namespace std;

signed main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k; cin>>n>>k;
    cout<<n-k+1<<endl;
}

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

typedef long long ll;
typedef pair<ll,ll> ii;
typedef long double ld;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
const int INF=2012345678;
const ll LLINF=4012345678012345678LL;
const ll MOD=998244353; //1000000007
const ld PI=3.1415926535898;
const ld EPS=1e-9;
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(b==0)return a;return gcd(b,a%b);}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline ll expo(ll b,ll p,ll m){ll res=1; while(p){if(p&1)res=(res*b)%m; b=(b*b)%m; p>>=1;} return res;}
inline ll modinv(ll a,ll m){return expo(a,m-2,m);}

struct node{
	int s,e,m;
	ll v;
	node *l,*r;
	node(int S,int E){
		s=S;e=E;m=(s+e)/2;v=0;
		if(s!=e){
			l=new node(s,m);r=new node(m+1,e);
		}
	}
	void upd(int x,ll nv){
		if(s==e){v=max(v,nv);return;}
		if(x<=m)l->upd(x,nv);
		else r->upd(x,nv);
		v=max(l->v,r->v);
	}
	ll qry(int x){ //pref max
		if(x==e)return v;
		if(x<=m)return l->qry(x);
		return max(l->qry(m),r->qry(x));
	}
}*root;

int main(){
	int n;
	scanf("%d",&n);
	int h[n];ll arr[n];
	for(int i=0;i<n;i++)scanf("%d",&h[i]);
	for(int i=0;i<n;i++)scanf("%lld",&arr[i]);
	root=new node(0,n);
	for(int i=0;i<n;i++){
		ll ans=root->qry(h[i]-1);
		root->upd(h[i],ans+arr[i]);
	}
	printf("%lld",root->qry(n));
}


Measured memory_bytes: 21376
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    int A[3], B[3];
    rep(i, 3) cin >> A[i];
    rep(i, 3) cin >> B[i];

    rep(k, 2) {
        int NextN = N;
        if (A[2] > B[2]){
            rep(i, 2) {
                if (A[i] <= B[i]) {
                    swap(A[i], A[2]);
                    swap(B[i], B[2]);
                    break;
                }
            }
        } 
        REP(i, 0, N / A[0]) {
            if (i > 0 && A[0] > B[0]) break;
            REP(j, 0, (N - i * A[0]) / A[1]) {
                if (j > 0 && A[1] > B[1]) break;
                int remain = N - i * A[0] - j * A[1];
                int k = remain / A[2];
                remain -= k * A[2];
                int tmp = remain + i * B[0] + j * B[1] + k * B[2];
                NextN = max(NextN, tmp);
            }
        }
        N = NextN;
        swap(A, B);
    }
    cout << N << endl;

    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

#define FOR(i, N) for (int i = 0; i < (int)N; i++)
#define FORIN(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
#define MAX (1 << 29)
#define DEBUG(...) debug(__LINE__, ":" __VA_ARGS__)

using Pi = pair<int, int>;
using ll = long long;
const int INF = 1 << 28;

string to_string(string s) {
  return s;
}

template <class S, class T>
string to_string(pair<S, T> p) {
  return "{" + to_string(p.first) + "," + to_string(p.second) + "}";
}

template <class T>
string to_string(vector<T> v) {
  string ret = "{";
  for (int i = 0; i < v.size() - 1; ++i) {
    ret += to_string(v[i]) + ",";
  }
  if (v.size() > 0) {
    ret += to_string(v.back());
  }
  ret += "}";
  return ret;
}

void debug() {
  cerr << endl;
}

template <class Head, class... Tail>
void debug(Head head, Tail... tail) {
  cerr << to_string(head) << " ";
  debug(tail...);
}

void print() {
  cout << endl;
}

template <class Head, class... Tail>
void print(Head head, Tail... tail) {
  cout << to_string(head);
  print(tail...);
}

void get() {}

template <class Head, class... Tail>
void get(Head& head, Tail&... tail) {
  cin >> head;
  get(tail...);
}

template <class T>
void getv(vector<T>& vec) {
  for (int i = 0; i < vec.size(); ++i)
    cin >> vec[i];
}

int main() {
  int N, M;
  cin >> N >> M;
  priority_queue<int> q;
  FOR(i, N) {
    int A;
    cin >> A;
    q.push(A);
  }
  FOR(i, M) {
    int x = q.top();
    q.pop();
    q.push(x / 2);
  }
  ll ans = 0;
  while (!q.empty()) {
    int x = q.top();
    q.pop();
    ans += x;
  }
  print(ans);
  return 0;
}

Measured memory_bytes: 892
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;

int main() {
  int N, flag = 0;
  cin >> N;

  for(int i=0; 7*i<=N; ++i) {
    for(int j=0; 4*j<=N; ++j) {
      if(7*i+4*j==N) {
        flag = 1;
        break;
      }
    }
  }

  if(flag) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define PI 3.14159265358979323846
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef long double ld;
typedef string st;
const ll MOD = 1e9 + 7 ;
const ll INF=1e14;
ll mpow(ll a,ll b,ll p=MOD){a=a%p;ll res=1;while(b>0){if(b&1)res=(res*a)%p;a=(a*a)%p;b=b>>1;}return res%p;}
const ll N=500020;

int main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      
      ld t,x;
      cin>>t>>x;
      t=t/x;
      cout<<fixed<<setprecision(7)<<t;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long L = sc.nextLong();
        long R = sc.nextLong();

        long ans = 999999999;
        long Flag = (long) R/2019;
        Flag *= 2019;

        if(Flag == 0){
            ans = (L * (L + 1))%2019;
        }else if(L <= Flag){
            ans = 0;
        }else if(Flag < L){
            for (long i = L; i < R; i++) {
                for (long j = (L+1); j <= R; j++) {
                    long tmp = (i*j)%2019;
                    if(tmp < ans) ans = tmp;
                }
            }
        }

        System.out.println(ans);

    }
}


Measured memory_bytes: 21844
#include <bits/extc++.h>

#ifndef DUMP
#define DUMP(...) (void)0
#endif

using namespace std;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int h, w, k;
  cin >> h >> w >> k;
  vector v(h, vector<int>(w));
  while (k--) {
    int i, j;
    cin >> i >> j;
    --i, --j;
    cin >> v[i][j];
  }
  vector dp(4, vector(h, vector<int64_t>(w, -1e18)));
  dp[0][0][0] = 0;
  dp[1][0][0] = v[0][0];
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      for (int x = 0; x < 4; ++x) {
        if (i + 1 < h) {
          dp[0][i + 1][j] = max(dp[0][i + 1][j], dp[x][i][j]);
          dp[1][i + 1][j] = max(dp[1][i + 1][j], dp[x][i][j] + v[i + 1][j]);
        }
        if (j + 1 < w) {
          dp[x][i][j + 1] = max(dp[x][i][j + 1], dp[x][i][j]);
          if (x < 3) {
            dp[x + 1][i][j + 1] =
                max(dp[x + 1][i][j + 1], dp[x][i][j] + v[i][j + 1]);
          }
        }
      }
    }
  }
  auto res = numeric_limits<int64_t>::min();
  for (int x = 0; x < 4; ++x) res = max(res, dp[x].back().back());
  cout << res << '\n';
}


Measured memory_bytes: 390704
a=int(input())
str_a=str(a)
list_a=list(str_a)
count=0
for i in range(0,len(list_a)):
	if(list_a[i]=='7'):
		count+=1
	else:
		count+=0
	
if(count>1 or count==1):
	print('Yes')
else:
	print('No')


Measured memory_bytes: 9144
#include <bits/stdc++.h>
#define FOR(i, l, r) for (ll i = l; i < r; i++)
#define rep(i, N) FOR(i, 0, N)
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<ll> vl;
const ll MOD = 1000000007;

int main() {
    int N, K;
    cin >> N >> K;
    vector<ll> pos, neg, raw;
    int zerocnt = 0;
    rep(i, N) {
        int a;
        cin >> a;
        if (a >= 0)
            pos.emplace_back(a);
        else if (a < 0)
            neg.emplace_back(a);
        if (a == 0) zerocnt++;
        raw.emplace_back(a);
    }

    ll ans = 1;
    if (N == K) {
        rep(i, K) {
            ans *= (raw[i] + MOD) % MOD;
            ans %= MOD;
        }
    } else {
        if (K % 2 == 1 && ((int)pos.size() == 0)) {
            sort(neg.begin(), neg.end(), greater<int>());
            rep(i, K) {
                ans *= (neg[i] + MOD) % MOD;
                ans %= MOD;
            }
        } else {
            int posind = 0, negind = 0;
            sort(pos.begin(), pos.end(), greater<int>());
            sort(neg.begin(), neg.end());

            while (K >= 2) {
                if (posind < (int)pos.size() - 1 && negind < (int)neg.size() - 1) {
                    if (pos[posind] * pos[posind + 1] > neg[negind] * neg[negind + 1]) {
                        ans *= pos[posind];
                        ans %= MOD;
                        posind++;
                        K--;
                    } else {
                        ans *= ((neg[negind] * neg[negind + 1]) % MOD);
                        ans %= MOD;
                        negind += 2;
                        K -= 2;
                    }
                } else if (posind >= (int)pos.size() - 1) {
                    ans *= ((neg[negind] * neg[negind + 1]) % MOD);
                    ans %= MOD;
                    negind += 2;
                    K -= 2;
                } else {
                    ans *= ((pos[posind]) % MOD);
                    ans %= MOD;
                    posind++;
                    K--;
                }
            }
            if (K > 0) {
                ans *= pos[posind];
                ans %= MOD;
                posind++;
            }
        }
    }

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


Measured memory_bytes: 7496
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
#define ALL(a)  (a).begin(),(a).end()
const ll INF = 1e18+18;
const ll MAX = 200000;
const ll MOD = 1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;


int main(){
    ll X, Y, A, B, C;
    cin>>X>>Y>>A>>B>>C;
    vector<ll> P(A), Q(B), R(C);
    rep(i, A){
        cin>>P[i];
    }
    rep(i, B){
        cin>>Q[i];
    }
    rep(i, C){
        cin>>R[i];
    }
    sort(P.begin(), P.end());
    sort(Q.begin(), Q.end());
    sort(R.begin(), R.end());
    ll AP, BP;
    AP=A-X;
    BP=B-Y;
    ll Sum=0;
    ll Max=0;
    for(ll i=A-X; i<A; i++){
        Sum+=P[i];
    }
  	
    for(ll i=B-Y; i<B; i++){
        Sum+=Q[i];
    }
    Max=Sum;
  	//cout<<Sum<<endl;
    rep(i, C){
        
        if(P[AP]<Q[BP]&&AP<A){
            Sum-=P[AP];
            Sum+=R[C-1-i];
            AP++;
            Max=max(Max, Sum);
          	//cout<<"A"<<Sum<<endl;
        }
        else if(BP<B){
            Sum-=Q[BP];
            Sum+=R[C-1-i];
            BP++;
            Max=max(Max, Sum);
          	//cout<<"B"<<Sum<<endl;
        }
      	else if(AP<A){
            Sum-=P[AP];
            Sum+=R[C-1-i];
            AP++;
            Max=max(Max, Sum);
          	//cout<<"B"<<Sum<<endl;
        }

    }
    cout<<Max<<endl;
}



Measured memory_bytes: 2560
fun main(args : Array<String>) {
    val (a, b, k) = readLine()!!.split(" ").map { it.toLong() }

    if (a >= k) {
        println("${a-k} $b")
    } else if (a + b >= k) {
        println("0 ${a+b-k}")
    } else {
        println("0 0")
    }
}


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

int main() {
  int n, m, q;
  cin >> n >> m >> q;
  vector<int> a(q), b(q), c(q), d(q), make_A;
  for(int i=0; i<q; i++) {
    cin >> a[i] >> b[i] >> c[i] >> d[i];
    a[i]--, b[i]--;
  }
  
  for(int i=0; i<n; i++) make_A.push_back(1);
  for(int i=0; i<m-1; i++) make_A.push_back(0);

  int ans = 0;
  do{
    vector<int> A;
    int count_zero = 0, score = 0;
    
    for(int i: make_A) {
      if(i) A.push_back(count_zero);
      else count_zero++;
    }
    
    for(int i=0; i<q; i++) {
      if(A[b[i]] - A[a[i]] == c[i]) score += d[i];
    }
    ans = max(ans, score);
  } while(prev_permutation(make_A.begin(), make_A.end()));
  
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 3592
from collections import Counter
from itertools import accumulate


def solve(string):
    n, m, *a = map(int, string.split())
    a = list(accumulate(a))

    d = Counter(_a % m for _a in a)
    ans = d[0]
    ans += sum(v * (v - 1) // 2 for v in d.values())
    return str(ans)


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))


Measured memory_bytes: 69272
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <bitset>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<int,int>
#define sys system("pause")
const int maxn=3e5+10;
using namespace std;
inline ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
inline ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
inline void umax(ll &p,ll q){if(p<q)p=q;}
inline void umin(ll &p,ll q){if(p>q)p=q;}
inline ll read()
{
    ll x=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,k,t,d[maxn],ret[maxn];
void add(int x,int y){while(x<=maxn-10)d[x]+=y,x+=x&(-x);}
int get(int x){int ret=0;while(x)ret+=d[x],x-=x&(-x);return ret;}
vi go[maxn],zi[maxn];
int main()
{
    int i,j;
    scanf("%d%d",&n,&m);
    rep(i,1,n)scanf("%d%d",&j,&k),go[j].pb(k);
    rep(i,1,m)
    {
        for(j=i;j<=m;j+=i)zi[j].pb(i);
    }
    rep(i,1,m)
    {
        for(int x:go[i])add(x,1);
        for(int x:zi[i])ret[x]+=get(i+x-1)-get(i-1);
    }
    rep(i,1,m)printf("%d\n",ret[i]);
    return 0;
}


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

using namespace std;

#ifndef aa
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double ld;
#define double long double
#define pii pair<int,int>
#define pdd pair<double,double>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define frev(a,b,c) for(int a=c; a>=b; a--)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
#define deb(x) cout << x << endl
#define done(x) {cout << x << endl;return;}
const ll infl = 0x3f3f3f3f3f3f3f3fLL;
const int infi = 0x3f3f3f3f;
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 998244353;
//const int mod = 1e9 + 7;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<pair<int, int>> vpii;
typedef map<int, int> mii;
typedef set<int> si;
typedef set<pair<int,int>> spii;
typedef queue<int> qi;


const int N = 2e5;



void solve() {

   int r,c,k;
   cin>>r>>c>>k;
   vvi a(r,vi(c));
   vvi d(r,vi(c,infl));
   int x1, y1, x2, y2;
   cin>>x1>>y1>>x2>>y2;
   x1--,x2--,y1--,y2--;
   rep(i,0,r){
     rep(j,0,c){
       char ch;
       cin>>ch;
       if(ch=='.')
         a[i][j]=1;
     }
   }
   
   set<vi> pq;
   vi dx={1,-1,0,0}, dy={0,0,1,-1};
   pq.insert({0,x2,y2,4,0});
   while(sz(pq)){
     vi v = *pq.begin();
     pq.erase(pq.begin());
     if(d[v[1]][v[2]]<v[0])
       continue;
     d[v[1]][v[2]]=v[0];
     rep(i,0,4){
       int x = v[1]+dx[i];
       int y = v[2]+dy[i];
       if(x>=0&&y>=0&&x<r&&y<c&&a[x][y]){
         if(i^v[3]||v[4]==k)
           pq.insert({v[0]+1,x,y,i,1});
         else
           pq.insert({v[0],x,y,i,v[4]+1});
       }
     }
   }
   int ans = d[x1][y1]==infl?-1:d[x1][y1];
   cout<<ans;


}


signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //srand(chrono::high_resolution_clock::now().time_since_epoch().count());
    cout << fixed << setprecision(15);
    int t = 1;
   //cin >> t;

    while (t--)
        solve();
#ifdef aa
    cout << endl << endl << endl << endl << "Time elapsed: " << (double)(clock() - clk) / CLOCKS_PER_SEC << endl;
#endif
    return 0;
}



int powm(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1)
            res = (res*a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

int divide(int a, int b) {
    return (a % mod) * powm(b, mod - 2) % mod;
}

int norm(int a) {
    while (a >= mod) a -= mod;
    while (a < 0) a += mod;
    return a;
}


int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}


Measured memory_bytes: 44732
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#include <boost/multiprecision/cpp_int.hpp> 
#define FIO           	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using boost::multiprecision::cpp_int; 
void solve()
{
	cpp_int a; double b;
	cin >> a >> b;
	b = ((b)*(1000.0000000000000000));
	cpp_int bb = (cpp_int)b;
	cpp_int aa = a;
	cpp_int aans = (aa*bb);
	cpp_int t = aans/1000;
	cout << t << endl;

}
 
int32_t main()
{
	FIO
    {
    	solve();
    }
    return 0;
}
	

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

#define INF 1145141919
#define PI atan(-1)

using namespace std;

#define MAX_N 100005

#define LL long long

int N;
LL _A[MAX_N], A[MAX_N];

int main()
{
  cin >> N;
  for (size_t i = 0; i < N; i++) {
    cin >> _A[i];
  }

  memmove(A, _A, sizeof(A));

  LL ans = 0;
  LL tmp = 0;
  for (size_t i = 0; i < N; i++) {
    if(A[i] == 0){
      ans += tmp/2;
      tmp = 0;
    }
    else{
      tmp += A[i];
    }
  }

  cout << ans + tmp/2 << endl;

  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <sstream>
using namespace std;
#define REP(i,n) for(int i=0;i<int(n);i++)

string toString(int x)
{
  stringstream ss;
  ss << x;
  return ss.str();
}

bool isConse(int x)
{
  string s = toString(x);
  char c = s[0]+1;
  for(int i = 1; i < (int)s.size(); i++)
    if(c++ != s[i]) return false;
  return true;
}

int main()
{
  int N;
  cin >> N;
  int a[N];
  REP(i,N) cin >> a[i];
  int ans = -1;
  REP(i,N-1)
    for(int j = i+1; j < N; j++)
      if(isConse(a[i]*a[j])) ans = max(ans,a[i]*a[j]);
  cout << ans << endl;
}

Measured memory_bytes: 3196
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bits/stdc++.h>
#define gi get_int()
#define _FILE(s) freopen(#s".in", "r", stdin); freopen(#s".out", "w", stdout)
const int MAXN = 5e5;
int get_int()
{
	int x = 0, y = 1; char ch = getchar();
	while (!isdigit(ch) && ch != '-')
		ch = getchar();
	if (ch == '-') y = -1, ch = getchar();
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * y;
}

int pre[MAXN]['z' + 1], f[MAXN];

int main()
{
	std :: string str;
	std :: cin >> str;
	int n = str.size();

	for (int i = 'a'; i <= 'z'; i++) pre[n][i] = n;
	memset(f, 0x3f, sizeof(f));
	f[n + 1] = 0; f[n] = 1;
	for (int i = n - 1; i >= 0; i--) {
		for (int j = 'a'; j <= 'z'; j++)
			pre[i][j] = pre[i + 1][j];
		pre[i][str[i]] = i;
	}
	
	for (int i = n - 1; i >= 0; i--)
		for (int j = 'a'; j <= 'z'; j++)
			f[i] = std :: min(f[i], f[pre[i][j] + 1] + 1);



	int now = 0;
	for (int i = 0; i < f[0]; i++)
		for (int j = 'a'; j <= 'z'; j++) {
			if (f[now] == f[pre[now][j] + 1] + 1) {
				printf("%c", j);
				now = pre[now][j] + 1;
				break;
			}
		}

	return 0;
}


Measured memory_bytes: 98820
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    void solve() {
        Scanner sc = new Scanner(System.in);
        int cardNum = sc.nextInt(); // カード N 枚 ：(0 ~ N-1)
        int gateNum = sc.nextInt(); // ゲート M 個 ：(0 ~ M-1)
        int[] left = new int[gateNum];
        int[] right = new int[gateNum];
        for (int i = 0; i < gateNum; i++) {
            left[i] = sc.nextInt();
            right[i] = sc.nextInt();
        }

        int ans = 0;
        int curStart = left[0];
        int curEnd = right[0];
        for (int i = 1; i < gateNum; i++) {
            int start = left[i];
            int end = right[i];

            // 共通部分なし
            if(end < curStart || curEnd < start) {
                System.out.print(0);
                return;
            }
            else {
                if (curStart < start) {
                    curStart = start;
                }
                if (end < curEnd) {
                    curEnd = end;
                }
            }
        }
        ans = curEnd - curStart + 1;
        System.out.print(ans);
    }

    // Main
    public static void main(String[] args) {
        new Main().solve();
    }
}

Measured memory_bytes: 64788
#include <iostream>
#include <algorithm>

int n, a, b, p[110];
int main() {
	std::cin >> n >> a >> b;
	for (int i = 0; i < n; ++i)
		std::cin >> p[i];
	std::sort(p, p + n);

	int first = 0, second = 0, third = 0;
	for (int i = 0; i < n; ++i)
		if (p[i] <= a)
			++first;
		else if (p[i] <= b)
			++second;
		else
			++third;
	std::cout << std::min({ first,second,third }) << std::endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int main() {
  int N,i,A,B;
  cin>>N;
  int cnt = 0;
  int ans = 1e5;

  for (i=1;i<N;i++){
    A=i;
    B=N-i;
    
    int Asum=0;
    int Bsum=0;
    while(A>=1){
      Asum=Asum+A%10;
      A/=10;
    }
    while(B>=1){
      Bsum=Bsum+B%10;
      B/=10;
    }
    ans = min(ans, Asum+Bsum);
  }
  cout << ans << endl;
}

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

int main(){
  long long n,a,b;
  cin>>n>>a>>b;

  long long ans=0;
  if((n==1 && a!=b)||(a>b));
  else if(a==b || n==2)ans=1;
  else ans=(b-a)*(n-2)+1;

  cout<<ans<<endl;
}

Measured memory_bytes: 256
import numpy as np
n = int(input())
a = np.array([list(map(int,input().split())) for i in range(2)])

cnt = [0] * (n)
for i in range(0, n):
    cnt[i] = sum(a[0, :i+1]) + sum(a[1, i:])

print(max(cnt))
             

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

typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int main(){
  int a, b, c, d, e, k;
  cin >> a >> b >> c >> d >> e >> k;
  if(e-a > k){
    cout << ":(" <<endl;
  }else{
    cout << "Yay!" <<endl;
  }
}

Measured memory_bytes: 256
import sys


def _s(): return sys.stdin.readline().strip()


def _ia(): return map(int, sys.stdin.readline().strip().split())


def walk(s, w1, h1, x, y, cur, v1, v2):
    if s[y][x] is not None:
        return
    s[y][x] = cur
    v1.add((x, y))
    for hi in range(max(0, y - 2), min(h1, y + 2) + 1):
        for wi in range(max(0, x - 2), min(w1, x + 2) + 1):
            if s[hi][wi] is None:
                v2.add((wi, hi))

    if x > 0:
        walk(s, w1, h1, x-1, y, cur, v1, v2)
    if x < w1:
        walk(s, w1, h1, x+1, y, cur, v1, v2)
    if y > 0:
        walk(s, w1, h1, x, y-1, cur, v1, v2)
    if y < h1:
        walk(s, w1, h1, x, y+1, cur, v1, v2)


def main():
    h, w = _ia()
    sh, sw = map(lambda x: x-1, _ia())
    gh, gw = map(lambda x: x-1, _ia())
    s = [[0]*w for _ in range(h)]
    for hi in range(h):
        for wi, c in enumerate(_s()):
            if c == '.':
                s[hi][wi] = None
            else:
                s[hi][wi] = -1

    p = [(sw, sh)]
    c = 0
    h1, w1 = h-1, w-1
    while len(p) > 0:
        v1 = set()
        v2 = set()
        for pi in p:
            walk(s, w1, h1, *pi, c, v1, v2)
        p = v2 - v1
        c += 1
    ans = s[gh][gw]
    return ans if ans is not None else -1


if __name__ == "__main__":
    print(main())


Measured memory_bytes: 149948
def mod(n)
  n%2
end

def div(n)
  if mod(n) == 0
    -n/2
  elsif n > 0
    -(n/2)
  elsif n < 0
    -n/2 + 1
  else
    0
  end
end

n = gets.to_i

s = []

if n == 0 || n == 1
  puts n
  exit
end

while n != 0 && n!= 1 do
  s << mod(n)
  n = div(n)
end

s << 1 if n == 1

puts s.reverse!.join


Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
using lint = long long;

int main(int, char**) {
    ios_base::sync_with_stdio(0); cin.tie(NULL);

    int n;
    cin >> n;
    bool res = true;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if (x % 2 == 0) {
            if (x % 3 != 0 && x%5 != 0)
                res = false;
        }
    }
    if (res)
        cout << "APPROVED" << endl;
    else
        cout << "DENIED" << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S; cin >> S;
    rep(i, 3) {
        if (S[i] == '1') cout << 9;
        else cout << 1;
    }
    cout << endl;

    return 0;
}


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

#define FOR(i, s, e)   for(int i = (s); i < (e); i++)
#define FOR64(i, s, e) for(ll  i = (s); i < (e); i++)
#define ALL(x)         (x).begin(), (x).end()
#define SORT(b, e)     sort((b), (e))
#define REV(b, e)      reverse((b), (e))
#define VSORT(v)       sort((v).begin(), (v).end())
#define VREV(v)        reverse((v).begin(), (v).end())
#define pb(a)          push_back(a)
#define INF            999999999

typedef long long ll;

void printm(map<int, int> &m)
{
	cout << m.size() << endl;

	for(auto k : m){
		cout << "m[" << k.first << "] = " << k.second << endl;
	}
}

inline int get_max(map<int, int> &m)
{
	return max_element(ALL(m), [](auto &a, auto &b){ return a.second < b.second; })->first;
}

inline int get_max_without_n(map<int, int> &m, int n)
{
	int t = m[n]; m[n] = -1;
	int r = get_max(m);
	m[n] = t;
	return r;
}

int main()
{
	int N;
	cin >> N;
	map<int, int> m0, m1, m2;

	FOR(i, 0, N/2){
		int a, b;
		cin >> a >> b;
		m0[a]++;
		m0[b]++;
		m1[a]++;
		m2[b]++;
	}

	if(m0.size() == 1){
		cout << N / 2 << endl;
		return 0;
	}

	int o1 = get_max(m1);
	int e1 = get_max(m2);

	int rep_o1 = N / 2 - m1[o1];
	int rep_e1 = N / 2 - m2[e1];

	if(o1 != e1){
		cout << rep_o1 + rep_e1 << endl;
	}
	else{
		int o2 = get_max_without_n(m1, o1);
		int e2 = get_max_without_n(m2, e1);

		int rep_o2 = N / 2 - m1[o2];
		int rep_e2 = N / 2 - m2[e2];

		cout << min(rep_o1 + rep_e2, rep_o2 + rep_e1) << endl;
	}

	return 0;
}



Measured memory_bytes: 9600
import sys
import itertools


def get_distance(from_town, to_town):
    distance = ((from_town[0] - to_town[0]) ** 2 + (from_town[1] - to_town[1]) ** 2) ** 0.5
    return distance


input = sys.stdin.readline

N = int(input())

townmap = []
for i in range(N):
    x, y = map(int, input().split())
    townmap.append([x, y])

patterns = itertools.permutations(townmap, N)

sum_v = 0
cnt_p = 0
for p in patterns:
    cnt_p += 1
    for i in range(len(p) - 1):
        sum_v += get_distance(p[i], p[i + 1])

result = sum_v / cnt_p

# print("len(patterns):{}".format(cnt_p))
print(result)

# print(get_distance([0, 0], [1, 0]))
# print(get_distance([1, 0], [0, 1]))


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

int main() {
    int N;
    cin >> N;
    bool shojun = false;
    int index1 = -1;
    int index2 = -1;
    int count = 0;
    vector<int> p(N);
    for(int i=0;i<N;i++) cin >> p[i];

    for(int i=0;i<N-1;i++){
        if(p[i] > p[i+1]){
            count +=1;
            if(count == 1) index1 = i;
            else if(count == 2) index2 = i+1;
        }
    }

    if(count == 0){
        cout << "YES" << endl;
        return 0;
    }
    if(count == 1){
        int tmp = p[index1 + 1];
        p[index1+1] = p[index1];
        p[index1] = tmp;
    } else if(count >= 2){
        int tmp = p[index2];
        p[index2] = p[index1];
        p[index1] = tmp;
    }

    for(int i=0;i<N-1;i++){
        if(p[i] > p[i+1]){
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

Measured memory_bytes: 256