akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define int long long
#define double long double
#define ff first
#define ss second
#define endl '\n'
#define ii pair<int, int>
#define mp make_pair
#define mt make_tuple
#define DESYNC ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define pb push_back
#define vi vector<int>
#define vii vector< ii >
#define EPS 1e-9
#define INF 1e18
#define ROOT 1
#define M 1000000007
const double PI = acos(-1);

using namespace std;
using namespace __gnu_pbds;

inline int mod(int n, int m){ int ret = n%m; if(ret < 0) ret += m; return ret; }

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

struct BIT {
  
  vector<int> bit;

  BIT() {}
  
  int n;
   
  BIT(int n) {
    this->n = n;
    bit.resize(n+1);
  }

  void update(int idx, int val){
    for(int i = idx; i <= n; i += i&-i){
      bit[i]+=val;
    }
  }

  int prefix_query(int idx){
    int ans = 0;
    for(int i=idx; i>0; i -= i&-i){
      ans += bit[i];
    }
    return ans;
  }
  
  int query(int l, int r){
    if(l > r) return 0;
    return prefix_query(r) - prefix_query(l-1);
  }
  
  //int bit 0-1 it finds the index of k-th element active
  int kth(int k) {
    int cur = 0;
    int acc = 0;
    for(int i = 19; i >= 0; i--) {
      if(cur + (1<<i) > n) continue;
      if(acc + bit[cur + (1<<i)] < k) {
        cur += (1<<i);
        acc += bit[cur];
      }
    }
    return ++cur;
  }
  
};

struct query{
  int t,a,b,c;
};

typedef tree<
ii,
null_type,
less< ii >,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

int key = 0;

int32_t main(){
  DESYNC;
  int q;
  cin >> q;
  query queries[q];
  set<int> s;
  map<int,int> m;
  for(int i=0; i<q; i++){
    cin >> queries[i].t;
    if(queries[i].t == 1){
      cin >> queries[i].a >> queries[i].b;
      s.insert(queries[i].a);
    }
  }
  int n = s.size();
  vector<int> aux;
  for(int x : s) aux.pb(x);
  for(int i=0; i<q; i++){
    if(queries[i].t == 1){
      queries[i].c = lower_bound(aux.begin(), aux.end(),  queries[i].a) - aux.begin() + 1;
      m[queries[i].a] = queries[i].c;
    }
  }
  BIT bit(n+1);
  int cons = 0;
  ordered_set os;
  for(int i=0; i<q; i++){
    if(queries[i].t == 1){
      //add on ord_set
      os.insert(ii(queries[i].a, ++key));
      //add on sumtree
      bit.update(queries[i].c, queries[i].a);
      cons += queries[i].b;
    }
    else {
      int median = (os.size()+1)/2 -1;
      int l = 0, r = median;
      int ans = median;
      auto it = os.find_by_order(median);
      int x = it->ff;
      while(l <= r){
        int m = (l+r)>>1;
        int cur = os.find_by_order(m)->ff;
        if(cur == x){
          ans = m;
          r = m-1;
        }
        else if(cur < x){
          l = m+1;
        }
      }
      median = ans;  
      int val = cons;
      //cout << (x*(median+1) - bit.query(1, m[x])) << " " << (bit.query(m[x]+1, n) - x*((int)os.size() - median - 1))<<endl;
      val += (x*(median) - bit.query(1, m[x]-1));
      val += (bit.query(m[x], n) - x*((int)os.size() - median));
      cout << x << " " << val << endl;
    }
  }
}



Measured memory_bytes: 27640
# include<bits/stdc++.h>
# include<unordered_map>
# include<unordered_set>
//# include<prettyprint.hpp>
using namespace std;
# define ll long long
# define ld long double
# define endl '\n'
const ld pi = 3.14159265358979323846264338327950288;
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ld a, b; cin >> a >> b;
    int h, m; cin >> h >> m;
    ld theta1 = m*6;
    ld theta2 = (30*h)+((m*1.0)/60.0)*30;
    ld theta = 0;
    if (theta1 > theta2) theta = theta1-theta2;
    else if(theta2 > theta1) theta = theta2 - theta1;
    if (theta >= 180.0) theta = 360-theta;
    theta*=(pi/180.0);
    ld x = sqrtl(a*a+b*b-2*a*b*cos(theta));
    cout << fixed << setprecision(10) << x << endl;
    return 0;
}

Measured memory_bytes: 4184
#include"bits/stdc++.h"
using namespace std;
using ll = uint64_t;

int main() {
    ll N;
    cin >> N;
    vector<ll> x(N), y(N);
    for (ll i = 0; i < N; i++) {
        cin >> x[i] >> y[i];
    }

    map<pair<ll, ll>, ll> mp;
    for (ll i = 0; i < N; i++) {
        for (ll j = i + 1; j < N; j++) {
            mp[{x[i] - x[j], y[i] - y[j]}]++;
            mp[{x[j] - x[i], y[j] - y[i]}]++;
        }
    }

    ll ans = 0;
    for (auto p : mp) {
        ans = max(ans, p.second);
    }

    cout << N - ans << endl;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define ull unsigned long long

using namespace std;

ull num[200005], ball[200005];

int main ()

{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    vector <ull> distinct;
    ull n, sum = 0;
    cin >> n;
    for ( ull i = 1; i <= n; i++ )
    {
        cin >> ball[i];
        if(!num[ball[i]])
        {
            distinct.push_back(ball[i]);
        }
        num[ball[i]]++;
    }
    for( ull i = 0; i < distinct.size(); i++ )
    {
        sum += ((num[distinct[i]]*(num[distinct[i]]-1))/2);
    }
    for ( ull i = 1; i <= n; i++ )
    {
        cout << sum-(num[ball[i]]-1) << endl;
    }
}

Measured memory_bytes: 5876
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
#define int long long int
typedef complex<long double> cd;
const long double pi=acos(-1);
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <db, db> pdd;
typedef vector<int> vi;
typedef vector<vector<int> > matrix;

#define m1 make_pair
#define pb push_back
#define flush fflush(stdout)
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define reset(x,v) memset(x,v,sizeof(x))

#define fi first
#define se second
#define endl "\n"
#define debug(x) (cerr << #x << ": " << x << "\n")
#define setbits(x) __builtin_popcount(x)
#define setbitsll(x) __builtin_popcountll(x)
#define all(x) x.begin(),x.end()
#define pii pair<int,int>

inline ll gcd(ll a,ll b){if(a==0) return b;return gcd(b%a,a);}
inline ll power(ll a,ll n,ll m){if(n==0)return 1;ll p=power(a,n/2,m);p=(p%m*p%m)%m;if(n%2) return (p%m*a%m)%m;else return p;}
const double EPS = 1e-9;
const ll MOD =998244353;
const ll hell=1000000007;
const int INF = 1e18;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
template<typename T>
using ordered_set=tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
std::mt19937 rng(seed);

double startTime;
double getCurrentTime() {
    return ((double)clock() - startTime) / CLOCKS_PER_SEC;
}
const int dx[] = { -1, 0, 1, 0 };
const int dy[] = { 0, 1, 0, -1 };

const int N=100005;

int dp[N+1][101];
int w[N+1],profit[N+1];

void solve()
{
    int n,W;
    cin>>n>>W;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i]>>profit[i];
    }
   // for(int i=1;i<=n;i++)
     //   dp[0][i]= INF;
    for(int i=1;i<=N;i++)
    {
        dp[i][0]=INF;
        for(int j=1;j<=n;j++)
        {
            dp[i][j]=dp[i][j-1];
            if(profit[j]<=i)
            {
                dp[i][j]=min(dp[i][j],w[j]+dp[i-profit[j]][j-1]);
            }
        }
    }
   // cout<<dp[17][n]<<endl;
    for(int i=N;i>=0;i--)
        if(dp[i][n]<=W)
        {
            cout<<i<<endl;
            return;
        }
    
    
    
    
    
    
    
}


int32_t main()
{
    IOS;
    int t;
    t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}






Measured memory_bytes: 79232
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;

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

// Self settings
// clang-format off
#define MAX_N 100000
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SLN(i,N) (i == N-1 ? "\n" : " ")
ll fact(ll n) { ll res = 1; for(ll i=2;i<=n;++i) res = res * i; return res;}
ll nCr(ll n, ll r) {return (fact(n)/fact(n-r)*fact(r)) ;}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const ll MOD = 1e9+7;
const ll INF = 1LL << 60;
const ll inf = 1 << 30;
// clang-format on

ll N;

int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> N;
  vector<ll> A(N), B(N), C(N);
  REP(i, N) cin >> A[i];
  REP(i, N) cin >> B[i];
  REP(i, N) cin >> C[i];

  sort(A.begin(), A.end());
  sort(B.begin(), B.end());
  sort(C.begin(), C.end());

  ll ans = 0;
  for (ll j = 0; j < N; j++) {
    ll b = B[j];
    ll a = lower_bound(A.begin(), A.end(), b) - A.begin();
    ll c = C.end() - upper_bound(C.begin(), C.end(), b);
    ans += a * c;
  }
  cout << ans << endl;

  return 0;
}


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

int main(){
    int A[3][3];
    int mark[3][3];
    int N;
    int B[10];
    int i,j,k;

    for(i=0;i<3;i++){
        for(j=0;j<3;j++){
            cin>>A[i][j];
            mark[i][j]=0;
        }
    }
    cin>>N;
    for(i=0;i<N;i++){
        cin>>B[i];
    }
    
    for(k=0;k<N;k++){
        for(i=0;i<3;i++){
            for(j=0;j<3;j++){
                if(A[i][j]==B[k]) mark[i][j]=1;
            }
        }
    }
    for(i=0;i<3;i++){
        if(mark[0][i] && mark[1][i] && mark[2][i]){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    for(i=0;i<3;i++){
        if(mark[i][0] && mark[i][1] && mark[i][2]){ 
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    if(mark[1][1] && mark[2][2] && mark[0][0]){
        cout<<"Yes"<<endl;
        return 0;
    }
    if(mark[1][1] && mark[2][0] && mark[0][2]){
        cout<<"Yes"<<endl;
        return 0;
    }
    cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)/2)
#define all(x) x.begin(),x.end()
#define inf 1000000005
#define MOD 1000000007 
#define N 300005
#define M 1000000
#define LOG 17
#define KOK 300
#define EPS 0.0000001
using namespace std;

int sz;
int pre[N],a[N];
int n;

void s0(int ad) {

	for(int i=1;i<ad;i++) {

		printf("%d %d\n",i,i+1);
		printf("%d %d\n",n+i,n+i+1);

	}

	printf("%d %d\n",ad,n+1);

}

void no() {printf("No");exit(0);}

void solve() {

	if(n%4==0) {

		int f=n;

		while(f%2==0) f/=2;

		if(f==1) no();

		for(int i=1;i<n;i++) a[++sz]=i;
		for(int i=1;i<n;i++) a[++sz]=i;		

		for(int i=1;i<=sz;i++) pre[i]=pre[i-1]^a[i];

		map<int,int> ok;

		ok[pre[0]]=0;

		for(int i=1;i<=sz;i++) {

			if(ok.find(pre[i]^n)!=ok.end()) {

				printf("Yes\n");

				s0(n-1);

				printf("%d %d\n",n,ok[pre[i]^n]+1);
				printf("%d %d\n",n+n,i);

				exit(0);

			}

			ok[pre[i]]=i;

		}

		no();

	}
	else if(n%4==1) {

		printf("Yes\n");

		s0(n-2);

		printf("%d %d\n",n,n-1);
		printf("%d %d\n",n-1,1);
		printf("%d %d\n",1,n+n);
		printf("%d %d\n",n+n,n+n-1);

	}
	else {

		printf("Yes\n");

		s0(n-3);

		printf("%d %d\n",n-1,n-2);
		printf("%d %d\n",n-2,1);
		printf("%d %d\n",1,n+n-1);
		printf("%d %d\n",n+n-1,n+n-2);
		printf("%d %d\n",n+n-1,n);
		printf("%d %d\n",n+n,2);

	}

}

int main() {

	scanf("%d",&n);

	if(n<3) {printf("No");exit(0);}

	int xx=0;

	for(int i=1;i<=n;i++) xx^=i;

	if(xx) {

		solve();

		return 0;

	}

	printf("Yes\n");

	s0(n);

}	

Measured memory_bytes: 5888
import java.io.*;
import java.util.*;

public class Main {

    public static void main(final String[] args) throws Exception {
        final Scanner sc = new Scanner(System.in);
        long N;
        N = sc.nextLong();
        String[] S = new String[(int)(N)];
        for(int i = 0 ; i < N ; i++){
                S[i] = sc.next();
        }

        final Solver solver = new Solver();
        solver.solve(N, S);
    }
}

class Solver {
    public void solve(long N, String[] S) {

        int max = 0;
        TreeMap<String, Integer> dict = new TreeMap<>();
        for (String s : S) {
            if (dict.containsKey(s)) {
                dict.put(s, dict.get(s) + 1);
            }
            else {
                dict.put(s, 1);
            }

            if (max < dict.get(s)) {
                max = dict.get(s);
            }
        }

        for (final String key : dict.navigableKeySet()) {
            final int v = dict.get(key);
            if (v == max) {
                System.out.println(key);
            }
        }
    }
}



Measured memory_bytes: 84872
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    H, W = MI()
    G = LLS(H)

    R = [[] for _ in range(H)]
    for i, row in enumerate(G):
        tmp = [0] * (W+1)
        cnt = 0
        flag = True
        idx = -1
        # print(row)
        for j, h in enumerate(row):
            if h == '#':
                if cnt > 0:
                    tmp[idx] = tmp[idx] + cnt
                    tmp[j] = tmp[j] - cnt
                    cnt = 0
                    flag = True
            else:
                if flag:
                    idx = j
                    flag = False
                cnt = cnt + 1
        if cnt > 0:
            tmp[idx] = tmp[idx] + cnt
            tmp[-1] = - cnt

        # print(tmp)
        # print(*accumulate(tmp))
        R[i] = list(accumulate(tmp))
    # print(R)

    ans = -1
    for i in range(W):
        tmp2 = [0] * (H+1)
        cnt = 0
        flag2 = True
        idx = -1
        for j in range(H):
            d = G[j][i]
            if d == '#':
                if cnt > 0:
                    tmp2[idx] = cnt
                    tmp2[j] = - cnt
                    cnt = 0
                    flag2 = True
            else:
                if flag2:
                    idx = j
                    flag2 = False
                cnt = cnt + 1
        if cnt > 0:
            tmp2[idx] = cnt
            tmp2[-1] = - cnt
        # print(tmp2)
        # print(*accumulate(tmp2))
        for j, a in enumerate(list(accumulate(tmp2))[:-1]):
            ans = max(ans, R[j][i] + a - 1)

    print(ans)



if __name__ == '__main__':
    solve()


Measured memory_bytes: 268252
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define deb(x) cout<<#x<<" = "<<x<<"\n";
#define F first
#define S second
 
signed main()
{
	//#ifndef ONLINE_JUDGE
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	//#endif
	/************************************/
	
	int a, b; cin>>a>>b;
	a = a*3 + b;
	cout<<a/2<<"\n";
	
	
	
	
}

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

using namespace std;

int main() {
	string s;
	cin >> s;
	int temp = stoi(s);
	int x = temp / 100, y = temp % 100;
    if (x <= 12 && 1 <= x) {
		if (y <= 12 && 1 <= y) {
			cout << "AMBIGUOUS" << endl;
		}
		else {
			cout << "MMYY" << endl;
		}
	}
	else if (y <= 12 && 1 <= y)cout << "YYMM" << endl;
	else cout << "NA" << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
//https://atcoder.jp/contests/abc076/tasks/abc076_c?lang=en
using namespace std;
int main()
{
	string s,t;
	cin>>s>>t;
	for(int i=s.size()-t.size();i>=0;--i)
	{
		bool b=1;
		for(int j=0;j<t.size();++j)
		{
			if(s[i+j]=='?')
				continue;
			else if(s[i+j]!=t[j])
			{
				b=0;
				break;
			}
		}
		if(b==1&&!s.size()<t.size())
		{
			string st=s;
			for(int j=i;j<t.size()+i;j++)
				st[j]=t[j-i];
			for(int j=0;j<s.size();j++)
				if(st[j]=='?')
					st[j]='a';
			cout<<st;
			return 0;
		}
	}
	cout<<"UNRESTORABLE";
 
	return 0;
}

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


int main() {
    ll a,b,c,k;
    cin >> a >> b >> c >> k;
    ll ans=0;
    if(a<=k){
        ans+=a;
        k-=a;
        if(k>b){
            ans-=k-b;
        }
    }
    else ans=k;

    cout << ans << endl;
}

Measured memory_bytes: 3568
#include <iomanip>
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
#define MAX_N 302
double DP[MAX_N][MAX_N][MAX_N];

int main(void) {
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<int> A(3, 0);
  rep(i, N) {
    int x;
    cin >> x;
    A[x - 1]++;
  }

  double P = 1.0 / (double)N;
  rep(k, N + 1) {
    rep(j, N + 1) {
      rep(i, N + 1) {
        if ((i + j + k) > N) break;
        if ((i + j + k) == 0) continue;
        if (i) DP[i][j][k] += (double)i * DP[i - 1][j][k] * P;
        if (j) DP[i][j][k] += (double)j * DP[i + 1][j - 1][k] * P;
        if (k) DP[i][j][k] += (double)k * DP[i][j + 1][k - 1] * P;
        DP[i][j][k] += 1;
        DP[i][j][k] *= ((double)N / (double)(i + j + k));
      }
    }
  }
  double Ans = DP[A[0]][A[1]][A[2]];
  cout << setprecision(20) << Ans << endl;
  return 0;
}


Measured memory_bytes: 215296
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
    //cout.precision(10);
    int n;
    cin >> n;
    if(n > 999){
        n -= 999;
        cout << "ABD" << endl;
        return 0;;
        for(int i = 10; i <= 100; i = i * 10){
            if(i > n) cout << 0;
        }
        cout << n << endl;
        return 0;
    } else {
        cout << "ABC" << endl;
        return 0;
        for(int i = 10; i <= 100; i = i * 10){
            if(i > n) cout << 0;
        }
        cout << n << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	long long int W, H, x, y;
	scanf("%lld%lld%lld%lld", &W, &H, &x, &y);


	long double ans = W * H;
	printf("%llf ",ans/2.0);
	if (H % 2 == 1 || W % 2 == 1) {
		printf("0");
	}
	//else if (H == 0 || y == 0)
		//printf("0");
	else
	{
		if (W / 2 == x && H / 2 == y)
		{
			printf("1");
		}
		else
			printf("0");
	}

	return 0;
}

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

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

  int H; cin >> H;
  int W; cin >> W;
  vector<vector<int>> A(H, vector<int>(W, 0));
  vector<vector<int>> B(H, vector<int>(W, 0));
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> A[i][j];
    }
  }
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> B[i][j];
    }
  }

  vector<vector<vector<bool>>> dp(H, vector<vector<bool>>(W, vector<bool>(80 * 160, false)));

  dp[0][0][abs(A[0][0] - B[0][0])] = true;

  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      int diff = A[i][j] - B[i][j];
      for (int k = 0; k < 80 * 160; k++) {
        if (i > 0 && dp[i - 1][j][k]) {
          dp[i][j][abs(k - diff)] = true;
          dp[i][j][abs(k + diff)] = true;
        }
        if (j > 0 && dp[i][j - 1][k]) {
          dp[i][j][abs(k - diff)] = true;
          dp[i][j][abs(k + diff)] = true;
        }
      }
    }
  }

  for (int k = 0; k < 80 * 160; k++) {
    if (dp[H - 1][W - 1][k]) {
      cout << k << '\n';
      return 0;
    }
  }

  return 0;
}

Measured memory_bytes: 10752
n = list(input())
r = list(map(int,n))[::-1]
ans = 0
k = 0
f = 0
for i in r:
  i += k
  if f==5 and i>4:
    i += 1
  ans += min(i,10-i)
  k = int(i>5)
  f = i
print(ans+k)

Measured memory_bytes: 29036
#include <iostream>
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound


using namespace std;

int main() {
	int n;
	cin >> n;
	int a;
	int mx, mi;
	long long sum;

	cin >> a;
	mx = a;
	mi = a;
	sum += a;

	for (int i = 0; i < n-1; i++) {
		cin >> a;
		mx = max(mx, a);
		mi = min(mi, a);
		sum += a;
	}

	printf("%d %d %ld\n", mi, mx, sum);
	return 0;
}


Measured memory_bytes: 3228
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1001001001
#define LINF 1001001001001001001
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LLP;

int main() {

    int X;
    int grade = 8;
    int m = 599;
    cin >> X;
    
    while (X > m) {
        grade--;
        m += 200;
    }

    cout << grade << endl;
    
    return 0;
}

Measured memory_bytes: 3628
#include<iostream>  
#include<algorithm>  
#include<cstdio>  
#include<cstring>  
#include <deque> 
using namespace std;  

bool state = false ;

int main()
{
	int n ;
	while(1)
	{
		cin >> n ;
		if( ! n ) return 0 ;
		
		int p[5005];
		
		for(int i = 0 ; i < n ; i ++)
		{
			cin >> p[i] ;
		}
		
		long long max , contain ;
		contain = 0 ;
		max = 0x3f3f3f3f ;
		max *= -1 ;
		
		for(int i = 0 ; i < n ; i ++)
		{
			if(contain < 0) contain = 0 ;
			 
			contain += p[i] ;
			
			if(contain > max) max = contain ;
		}
		
	//	if(state) cout << endl ;
		
	//	state = true ;
	
		cout << max << endl ;
		
	} 
	return 0 ;
 } 

Measured memory_bytes: 2996
import sys

no = int(input())

no_xxo = no % 10
if no_xxo == 7:
    print('Yes')
    sys.exit(0)

no_xox = (no % 100) - no_xxo
if no_xox == 70:
    print('Yes')
    sys.exit(0)

no_oxx = no - no_xox - no_xxo
if no_oxx == 700:
    print('Yes')
    sys.exit(0)

print('No')

Measured memory_bytes: 9192
import java.util.*

val sc = Scanner(System.`in`)
val N = sc.nextInt()

fun main(args: Array<String>) {
    (1..N).map { calc(sc.nextInt()) }.min().let(::println)
}

fun calc(A: Int): Int {
    var i = 2
    var result = 0
    while (A % i == 0) {
        result++
        i *= 2
    }
    return result
}


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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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




void solve() {
    char c; cin >> c;
    char res;
    if(c == 'A') res = 'T';
    else if(c == 'T') res = 'A';
    else if(c == 'C') res = 'G';
    else res = 'C';
    cout << res << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


Measured memory_bytes: 7708
//#include<bits/stdc++.h>
//using namespace std;
//
//
//int main(){
////	int c = 0;
////	int a = 0, x ;
////	long long y=0 , y1 , y2;
////	
////	cin>>a>>y>>x;
////    
////	if((a<=y) && (0<=a && y <= 10^18) && (1<=x<=10^18))
////{  
////    if(y>10^9)
////    {
////    	y1 = y2 = y / 10^9; 
////    	for(int i = a ; i <= y1 ; i++)
////	    {
////	    	for(int i = a ; i <= y1 ; i++)
////	    {
////		if(i % x == 0)
////		{
////			c++;
////		}
////		
////	     }
////	    
////		
////		
////	     } 
////	     
////	     cout<<c;
////	}else{
////		 
////	for(int i = y ; i >= a ; i--)
////	{
////		if(i % x == 0)
////		{
////			c++;
////		}
////	}
////}	
////	cout<<c;
////		
////	}
////	
////   
////	
////	return 0;
//
//	
//	
//}
#include <bits/stdc++.h>
using namespace std;
int main(){
long long a=0,b=0,x=0,c=0;
scanf("%lld%lld%lld",&a,&b,&x);
if(a>0){
	a-=1;
	c=(b/x)-(a/x);
} 
else{
	c=b/x;
	c++;
}
printf("%lld",c);
return 0;
}

Measured memory_bytes: 256
while True:
    a, b, c = map(str, input().split())
    a = int(a)
    c = int(c)
    if b == '?': break
    if b == '+':
        print(a + c)
    elif b == '-':
        print(a - c)
    elif b == '*':
        print(a * c)
    elif b == '/':
        print(int(a / c))


Measured memory_bytes: 5592
n, m = map(int, input().split())
left = 0 # 制約における最小を超える値
right = 10 ** 6 # 制約における最大を超える値
for _ in range(m):
  l, r = map(int, input().split())
  left = max(left, l)
  right = min(right, r)

print(right-left+1 if left <= right else 0)

Measured memory_bytes: 3060
N, K = gets.chop.split.map(&:to_i)

max_size = [*(1..(N - 2))].inject(0, &:+)

if K > max_size
  puts "-1"
  exit
end

ans = []
2.upto(N) { |n| ans << "1 #{n}" }
a = 2
b = 3
(max_size - K).times do
  ans << "#{a} #{b}"
  b += 1 
  if b > N
    a += 1
    b = a + 1
  end
end

ans.unshift([ans.size])

puts ans


Measured memory_bytes: 2172
class BinomialCoefficient:
    def __init__(self, N, mod):
        '''
        Preprocess for calculating binomial coefficients nCr (0 <= r <= n, 0 <= n <= N)
        over the finite field Z/(mod)Z.
        Input:
            N (int): maximum n
            mod (int): a prime number. The order of the field Z/(mod)Z over which nCr is calculated.
        '''
        self.mod = mod
        self.fact = {i: None for i in range(N+1)}                # n!
        self.inverse = {i: None for i in range(1, N+1)}      # inverse of n in the field Z/(MOD)Z
        self.fact_inverse = {i: None for i in range(N+1)} # inverse of n! in the field Z/(MOD)Z
        
        # preprocess
        self.fact[0] = self.fact[1] = 1
        self.fact_inverse[0] = self.fact_inverse[1] = 1
        self.inverse[1] = 1
        for i in range(2, N+1):
            self.fact[i] = i * self.fact[i-1] % self.mod
            q, r = divmod(self.mod, i)
            self.inverse[i] = (- (q % self.mod) * self.inverse[r]) % self.mod
            self.fact_inverse[i] = self.inverse[i] * self.fact_inverse[i-1] % self.mod
    
    def binom(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return self.fact[n] * (self.fact_inverse[r] * self.fact_inverse[n-r] % self.mod) % self.mod
        
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

dup_num = sum(A) - N*(N+1)//2
dup_num_idx = sorted([i+1 for i, a in enumerate(A) if a == dup_num])
l, r = dup_num_idx[0], dup_num_idx[1]

bc = BinomialCoefficient(N+1, MOD)
for k in range(1, N+2):
    print((bc.binom(N+1, k) - bc.binom(N+1 - (r - l + 1), k - 1)) % MOD)

Measured memory_bytes: 51804
N = int(input())
A = input()
B = input()
C = input()
count = 0

for i in range(N):
    cash = 0
    if A[i] == B[i] and B[i] == C[i]:
        cash += 1
    if A[i] != B[i]:
        cash += 1
    if B[i] != C[i]:
        cash += 1
    if C[i] != A[i]:
        cash += 1
    count += cash - 1
print(count)


Measured memory_bytes: 3064
N = int(input())
A =[0]*N
for i in range(N):
    A[i] = int(input())
A.sort(reverse=True)
X=0
Y=0
if N % 2 == 0:
    for i in range(N//2-1):
        X = X + 2*A[i] -2*A[-i-1]
    X = X + A[N//2-1] -A[N//2]
    print(X)    
 
if N % 2 == 1:
        for i in range(N//2):
            X = X + 2 * A[i]
            Y = Y - 2 * A[-i-1]
        for i in range (N//2-1):
            X = X - 2 * A[-i-1]
            Y = Y + 2 * A[i]
        X = X - A[N//2] - A[N//2+1]
        Y = Y + A[N//2-1] + A[N//2]
        print(max(X,Y))

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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define contains(v, t) (find(v.begin(), v.end(), t) != v.end())
#define MOD 1000000007
using ll = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;

int main() {
  int n,k; cin>>n>>k;
  vector<ull> a(n+1);
  a[0] = 0;
  rep(i, n) {
    ull t; cin>>t;
    a[i+1] = a[i]+t;
  }

  ull prev = a[k] - a[0];

  for(int i = k+1; i <= n; i++) {
    ull cur = a[i] - a[i - k];
    if (prev < cur) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
    prev = cur;
  }
}


Measured memory_bytes: 4840
#include <bits/stdc++.h>
using namespace std;
 
// boost
#include <boost/multiprecision/cpp_int.hpp>
using boost::multiprecision::cpp_int;
 
using ll = long long;
using ld = long double;
 
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;
using vld = vector<ld>;
using vvld = vector<vld>;
 
typedef pair<ll, ll> P;
 
#define bit(n) (1LL << (n))
 
//#define int long long
 
#define all(v) v.begin(), v.end()
 
#define rep(i, n) for (ll i = 0; i < n; i++)
#define REP(i, n) for (ll i = 1; i < n; i++)
 
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORm(i, m) for (auto i = m.begin(); i != m.end(); i++)
 
template <class T>
inline void chmax(T& a, T b) {
  a = std::max(a, b);
}
template <class T>
inline void chmin(T& a, T b) {
  a = std::min(a, b);
}
 
#define mod (ll)(1e9 + 7)
// #define mod (998244353ll)
 
const long long INF = 1LL << 60;
 
P dfs(const vvll& g, ll idx, ll par) {
  P ans = make_pair(-1ll, idx);
  for (auto it : g[idx]) {
    if (it == par)
      continue;
    chmax(ans, dfs(g, it, idx));
  }
  ans.first++;
  return ans;
}
 
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
 
  ll n;
  cin >> n;
  vvll g(n);
  rep(i, n - 1) {
    ll a, b;
    cin >> a >> b;
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
 
  auto p = dfs(g, 0, -1);
  auto [diameter, idx] = dfs(g, p.second, -1);
 
  cout << ((diameter % 3 != 1) ? "First" : "Second") << endl;
 
  return 0;
}

Measured memory_bytes: 35792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i <= (n); i++)
#define zep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(ll i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;
 
int main(){
    cin.tie(0); ios::sync_with_stdio(false);
 
    ll n, k, c; cin >> n >> k >> c;
    string s; cin >> s;
 
    ll noruma[n]; memset(noruma, -1, sizeof(noruma));
    ll b = -INF;
    ll at = 0;
    zep(i, 0, n){
    	if(s[i] == 'o' && i-b-1 >= c){
    		at++;
    		noruma[i] = at;
    		b = i;
    	}
    }
    if(at > k){return 0;}
 
    b = INF;
    bool fix = false;
    at = k;
    rrep(i, n-1, 0){
    	if(s[i] == 'o'){
			if(noruma[i] < 0){
				if(b-i-1 >= c){
					noruma[i] = at;
					if(!fix){
						b = i;
						fix = true;
					}
				}
			}
			else{
				if(!fix){b = i;}
				fix = false;
				at--;
			}
    	}
    }
    //printa(noruma, 0, n-1)
 
    ll cnt[k+1]; memset(cnt, 0, sizeof(cnt));
    zep(i, 0, n){
    	if(noruma[i] > 0){
    		cnt[noruma[i]]++;
    	}
    }
 
    zep(i, 0, n){
    	if(noruma[i] > 0 && cnt[noruma[i]] == 1){
    		print(i+1)
    	}
    }
 
    return 0;
}

Measured memory_bytes: 5012
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}

int main(){
  int n; cin >> n;
  vector<int> a(n),b(n);
  
  rep(i,n){
    cin >> a[i];
    b[i] = a[i];
  }
  sort(a.begin(),a.end(),greater<int>());
  
  int ma = a[0];
  
  rep(i,n){
    if(b[i] == a[0]){
      cout << a[1] << endl;
    }else{
      cout << a[0] << endl;
    }
  }
  
  return 0;
}

Measured memory_bytes: 3200
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
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; }
//(a+b-1)/b
//priority_queue<ll, vector<ll>, greater<ll>> q;
ll dp[55][55][5000];

signed main(){
	//cout << fixed << setprecision(10);
	ll a,b,c,x,y; cin>>a>>b>>c>>x>>y;
	ll ans=MOD;
	chmin(ans,max(x,y)*c*2);
	chmin(ans,a*x+b*y);
	if(x<=y){
		chmin(ans,2*c*x+b*(y-x));
	}
	else{
		chmin(ans,2*c*y+a*(x-y));
	}
	cout << ans << endl;
	 
	return 0;
}

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

#define debug(x) cout << #x << ": " << (x) << endl

long long f(long long b, long long n) {
  return (n < b) ? n : f(b, n/b) + n % b;
}

int main(int argc, char *argv[]) {
  long long n, s;
  cin >> n >> s;

  if (n == s) {
    cout << n + 1 << endl;
    return 0;
  }

  for (long long b = 2; b <= sqrt(n); ++b) {
    if (f(b, n) == s) {
      cout << b << endl;
      return 0;
    }
  }

  for (long long p = sqrt(n); 0 < p; --p) {
    long long b = (n - s)/p + 1;
    if (1 < b and f(b, n) == s) {
      cout << b << endl;
      return 0;
    }
  }

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
using vll=vector<ll>;
using vi=vector<int>;

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

//pow(llpow,modpow)
template<class T> ll llpow(T x,T n){ll ans=1;if(x==0)ans=0;while(n){if(n&1)ans*=x;x*=x;n>>=1;}return ans;}
long long modpow(long long a, long long n, long long mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}
//最大公約数
template<class T> inline T gcd(T x,T y){if(y==0)return x; else {return gcd(y,x%y);}}
//最小公倍数
template<class T> inline T lcm(T x,T y){return x/gcd(x,y)*y;}
//逆元
long long modinv(long long a, long long m) {long long b = m, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}

#define rep(i,n) for(ll i=0;i<(ll)n;i++)
#define rep2(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)

long long INF = 1LL<<60;
int main( ){
    int n;
    ll k;
    cin>>n>>k;
    vector<pair<int,int>> ab(n);
    rep(i,n){
        int a,b;
        cin>>a>>b;
        ab[i]=make_pair(a,b);
    }
    sort(ab.begin(),ab.end());
    ll sum=0;
    rep(i,n){
        sum+=ab[i].second;
        if(sum>=k){cout<<ab[i].first;return 0;}
    }
    return 0;
}




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

int main(void){
	int n, m;
	while(1){
		cin >> n >> m;
		if(!n&&!m) break;
		vector<int> c(m), x(n);
		for(int i = 0; i < m; ++i){
			cin >> c[i];
		}
		for(int i = 0; i < n; ++i){
			cin >> x[i];
		}
		vector<vector <int>> dp(n+2);
		for(int i = 0; i < n+2; ++i){
			dp[i].resize(256);
			for(int j = 0; j < 256; ++j){
				dp[i][j] = INT_MAX;
			}
		}
		dp[0][128]=0;
		for(int i = 1; i <= n; ++i){
			for(int j = 0; j < m; ++j){
				for(int k = 0; k < 256; ++k){
					if(dp[i-1][k]==INT_MAX) continue;
					int next = k+c[j];
					if(next > 255) next = 255;
					if(next < 0) next = 0;
					dp[i][next] = min(dp[i][next], dp[i-1][k] + (int)pow(x[i-1]-next,2));
				}
			}
		}
		int ans = INT_MAX;
		for(int i = 0; i < 256; ++i){
			ans = min(ans, dp[n][i]);
			//cout << dp[n][i] << " ";
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 23716
package main

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

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

var sc = bufio.NewScanner(os.Stdin)

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

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

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

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

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

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

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

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

func main() {
	sc.Split(bufio.ScanWords)
	N, M, V, P := getInt(), getInt(), getInt(), getInt()
	a := make([]int, N)
	for i := 0; i < N; i++ {
		a[i] = getInt()
	}
	sort.Slice(a, func(i, j int) bool {
		return a[i] > a[j]
	})

	th := a[P-1]

	l, r := 0, N
	for l+1 != r {
		m := (l + r) / 2
		X := a[m] + M
		rest := M * (V - 1)
		if X < th {
			r = m
			continue
		}
		for i := 0; i < N; i++ {
			if i == m {
				continue
			}
			if i < P && a[i] > th {
				rest -= M
			} else {
				rest -= min(M, X-a[i])
			}
		}
		if rest <= 0 {
			l = m
		} else {
			r = m
		}
	}

	out(l + 1)
}


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

int main() {

    // 1. input.
    // C言語のscanf関数でスペースが入っている文字を出力する.
    // https://program-shoshinsya.hatenablog.com/entry/2018/07/06/193742
    char buf[1234];
    scanf("%[^\n]%*c", buf);
    
    // 2. output answer.
    for(int i = 0; i < strlen(buf); i++){
        char c = buf[i];
        char ans = buf[i];
        if(c >='a' && c <= 'z') ans = c - 32;
        if(c >='A' && c <= 'Z') ans = c + 32;
        printf("%c", ans);
    }
    printf("\n");
    return 0;
    
}


Measured memory_bytes: 3160
import itertools as iter
import math
N = int(input())
N_list =[i for i in range(N)]
C = [list(map(int,input().split())) for i in range(N)]
per = iter.permutations(N_list)
T = 0
for v in per:
    for i in range(len(v)-1):
      T += ((C[v[i+1]][0] - C[v[i]][0])**2 + (C[v[i+1]][1] - C[v[i]][1])**2)**0.5
print(T/math.factorial(N))

Measured memory_bytes: 40812
#include <bits/stdc++.h>
#define len(x) int(x.size())
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
#define MAXN 100010

ll f[MAXN];
ll mod = 1000000007;
void init(){
    f[1] = 1;
    f[2] = 1;
    f[3] = 2;
    for(int i=4; i<MAXN; ++i){
        f[i] = (f[i-1] + f[i-2])%mod; 
    }
}
int main() {
    ios::sync_with_stdio(0);
    init();
    int n, m;
    cin >> n >> m;
    vector<int> vs(m);
    for(auto &x:vs)
        cin >> x;
    
    int k = vs[0];
    for(auto x:vs){
        if(x==n or x==k+1){
            cout << 0 << endl;
            return 0;
        }
        k = x;
    }
    int last = -1;
    ll ans = 1;
    for(auto x:vs){
        ans = (ans*f[x-last-1])%mod;
        last = x;
    }
    ans = (ans*f[n-last])%mod;
    cout << ans << endl;
}

Measured memory_bytes: 1408
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main() {
	// your code goes here
	int n, m, sum=0, k;
	vector <int> v;
	
	cin >> n >> m;
	
	for(int i=0; i<n; i++) {
		cin >> k;
		v.push_back(k);
	}
	
	sort(v.begin(), v.end());
	for(int i=n-1; m != 0; i-- && m--) sum += v[i];
	
	cout << sum << endl;
	
	return 0;
}

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

using namespace std;

#define inf 1<<30
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define fn fill_n
typedef long long llong;
typedef unsigned long long ullong;
typedef pair<int, int> P;


int main(){
	llong N, Y;
	cin >> N >> Y;
	for(int i = 0; 10000*i <= Y; i++){
		llong ot = Y - 10000*i;
		llong many = N - i;
		// cerr << ot << " " << many << endl;
		if((ot/1000-many)%4) continue;
		int go = (ot/1000 - many)/4;
		if(0 <= go && go <= many){
			cout << i << " " << go << " " << many - go << endl;
			return 0;
		}
	}

	cout << "-1 -1 -1" << endl;

	return 0;
}

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

int aji[210];

int main() {
	int N,L; cin >> N >> L;
	
	int sum = 0;
	int eat = 101;
	for (int i=1; i<=N; ++i)
	{
		aji[i]=L+i-1;
		sum += aji[i];
		if (abs(eat) > abs(aji[i])) eat = aji[i];
	}

	int ans = 0;
	ans = sum - eat;
	
	
	cout << ans << endl;


	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define SIZE 100005
#define ll long long
vector< int > v[SIZE];
ll b[SIZE]={0};
ll w[SIZE]={0};


void dfs(int node, int par)
{

	ll sum1=1;
	ll sum2=1;
	for(auto i: v[node])
	{
		if(i==par)
			continue;
		dfs(i,node);
        sum1= ((sum1%MOD)*(w[i]%MOD))%MOD;
        sum2= ((sum2%MOD)*(((w[i]%MOD+b[i]%MOD)%MOD)%MOD))%MOD;
	}

	b[node]=sum1%MOD;
	w[node]=sum2%MOD;
}
int main()
{
	int n;
	cin>>n;
	int node1,node2;
	for(int i=1;i<n;i++)
	{
		cin>>node1>>node2;
		v[node1].push_back(node2);
		v[node2].push_back(node1);
	}

	dfs(1,0);
	cout<<(b[1]+w[1])%MOD<<endl;
	return 0;
}

Measured memory_bytes: 14208
N = int(input())
TXY = [[0, 0, 0] for _ in range(N)]
for i in range(N):
    TXY[i] = list(map(int, input().split()))

start = 0
start_x = 0
start_y = 0
for i in range(N):
    time = TXY[i][0] - start
    walk = [0 for _ in range(time)]
    diff_x = TXY[i][1] - start_x
    diff_y = TXY[i][2] - start_y
    total = len(walk) - (abs(diff_x) + abs(diff_y))
    if total < 0:
        print("No")
        exit()
    else:
        if total % 2 != 0:
            print(("No"))
            exit()
    start = TXY[i][0]
    start_x = TXY[i][1]
    start_y = TXY[i][2]
print("Yes")


Measured memory_bytes: 95820
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
#include <queue>
using namespace std;

class Edge
{
public:
	int src,dst,cst;
	Edge(int src, int dst, int cst)
		:src(src),dst(dst),cst(cst)
	{}
};

class State
{
public:
	int p,c;
	State(int p, int c)
		:p(p),c(c)
	{}

	bool operator<(const State& s) const
	{
		return c > s.c;
	}
};

typedef vector<vector<Edge> > Graph;

int dijkstra(int S, int T, Graph& graph)
{
	bool vis[500] = {0};

	priority_queue<State> q;
	q.push(State(S, 0));

	while(!q.empty()) {
		State s = q.top(); q.pop();
		if(s.p == T) return s.c;

		if(vis[s.p]) continue;
		vis[s.p] = 1;

		for(int i=0; i<graph[s.p].size(); i++) {
			Edge& e = graph[s.p][i];
			if(vis[e.dst]) continue;

			q.push(State(e.dst, s.c + e.cst));
		}
	}

	return -1;
}

int main()
{
	int N,M;
	while(cin >> N >> M, (N||M)) {
		map<string, int> dic;
		int ncnt = 0;

		string a,b,c;
		cin >> a >> b >> c;
		if(!dic.count(a)) dic[a] = ncnt++;
		if(!dic.count(b)) dic[b] = ncnt++;
		if(!dic.count(c)) dic[c] = ncnt++;


		Graph graph(N);
		for(int i=0; i<M; i++) {
			string x,y;
			cin >> x >> y;

			int u,v;
			if(!dic.count(x)) dic[x] = ncnt++;
			if(!dic.count(y)) dic[y] = ncnt++;

			u = dic[x];
			v = dic[y];

			int c,t;
			cin >> c >> t;
			graph[u].push_back(Edge(u, v, c/40 + t));
			graph[v].push_back(Edge(v, u, c/40 + t));
		}

		int res = dijkstra(dic[a], dic[b], graph);
		res += dijkstra(dic[b], dic[c], graph);

		cout << res << endl;
	}
}

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

const int64_t MAX = 510000;
const int64_t MOD = 1000000007;


int64_t mpow(int64_t x, int64_t n){
    int64_t ans = 1;
    while(n != 0){
        if(n%2==1) ans = ans*x % MOD;
        x = x*x % MOD;
        n = n/2;
    }
    return ans;
}
 
int64_t mfact(int64_t n){
  int64_t ans = 1;
  for(int64_t i=2; i<=n; i++){
    ans = ans*i % MOD;
  }
  return ans;
}
 
int64_t mcomb(int64_t n, int64_t m){ //aCbをmod計算
    if(n == 0 && m == 0) return 1;
    if(n < m || n < 0) return 0;
    int64_t ans = mfact(n)*mpow(mfact(m), MOD-2) %MOD;
    ans = ans*mpow(mfact(n-m), MOD-2) %MOD;
    return ans;
}



int main(){
  int64_t x, y;
  cin >> x >> y;
  bool flag = true;
  int64_t a = 0;
  int64_t b = 0;
  if((x+y) %3 != 0){
    flag = false;
  }
  else{
    if((2*x - y) %3 == 0){
      b = (2*x -y) /3;
    }
    if((2*y - x) %3 == 0){
      a = (2*y - x) /3;
    }
  }   
  
  
  if(flag && a >=0 && b >= 0){
    cout << mcomb(a+b, a) << endl;
  }
  else{
    cout << 0 << endl;
  }    
}

Measured memory_bytes: 256
N,x = map(int, input().split())
A = list(map(int, input().split()))

A.sort()
ans = 0

for i in range(N):
  if x > A[i]:
    if i+1 == N:
      print(N-1)
      exit()
    else:
      ans += 1
      x -= A[i]
  elif x == A[i]:
    ans += 1
    print(ans)
    exit()
  else:
    print(ans)
    exit()

Measured memory_bytes: 3064
# B - Bingo

A = []
for _ in range(3):
    A.append([int(a) for a in input().split()])

N = int(input())
B = [[False] * 3 for _ in range(3)]
for _ in range(N):
    b = int(input())
    for i in range(3):
        for j in range(3):
            if A[i][j] == b:
                B[i][j] = True

ans = 'No'
for i in range(3):
    if B[i][0] == B[i][1] == B[i][2] == True:
        ans = 'Yes'
    if B[0][i] == B[1][i] == B[2][i] == True:
        ans = 'Yes'
if B[0][0] == B[1][1] == B[2][2] == True:
    ans = 'Yes'
if B[0][2] == B[1][1] == B[2][0] == True:
    ans = 'Yes'

print(ans)


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

int main() {
    int N;
    cin >> N;
    vector<int> p(N);
    for (auto& i : p) cin >> i;
    vector<int> idx(N+1);
    for (int i = 0; i < N; i++) {
        idx[p[i]] = i + 1;
    }


    vector<int> a(N+1), b(N+1);
    for (int r = p[0]+1; r <= N; r++) {
        a[r] = max(a[r-1], -b[r-1]) + 1;
        b[r] = -max(a[r-1], -b[r-1])-1;

        a[r] += idx[r];
    }

    for (int l = p[0]-1; l > 0; l--) {
        a[l] = -max(-a[l+1], b[l+1])-1;
        b[l] = max(-a[l+1], b[l+1])+1;

        b[l] += idx[l];
    }

    int m = max(max(a[N], b[1]), abs(min(a[1], b[N])));

    for (int i = 1; i <= N; i++) {
        cout << a[i] + m + 1;
        if (i == N) cout << endl;
        else cout << " ";
    }
    for (int i = 1; i <= N; i++) {
        cout << b[i] + m + 1;
        if (i == N) cout << endl;
        else cout << " ";
    }

    return 0;
}


Measured memory_bytes: 896