akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include<chrono>
using namespace std;
using namespace chrono;
#define all(a) a.begin(), a.end()
#define sz(x) (int(x.size()))
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef vector<string> vs;
template<class T1, class T2>
istream &operator>>(istream &in, pair<T1, T2> &P){
	in >> P.first >> P.second;
	return in;
}
template<class T1, class T2>
ostream &operator<<(ostream &out, pair<T1, T2> &P){
	out << "(" << P.first << ", " << P.second << ") ";
	return out;
}
template<class T>
istream &operator>>(istream &in, vector<T> &arr){
	for(auto &x: arr) in >> x;
	return in;
}
template<class T>
ostream &operator<<(ostream &out, vector<T> &arr){
	for(auto &x: arr) out << x << ' '; cout << "\n";
	return out;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, W;
	cin >> n >> W;
	vector<pil> a(n);
	cin >> a;
	vl d(W + 1);
	for(int i = 0; i < n; i ++){
		for(int j = W; j >= a[i].first; j --){
			d[j] = max(d[j], d[j - a[i].first] + a[i].second);
		}
	}
	cout << d.back();
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
void pre(){}
void solve(){
    long long int n,k;cin>>n>>k;
    n=n%k;
    cout<<min(n,k-n)<<"\n";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    pre();
    long long int num = 1;
    //cin>>num;
    for(long long int i=0;i<num;i++){
       	solve();
    }   
}


Measured memory_bytes: 256
def main():
    S = input()
 
    key = "keyence"
 
    for i in range(len(key)):
        #print(key[:i], key[i:])
        if (S.startswith(key[:i]) and S.endswith(key[i:])):
            return True
    return False
if (main()):
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3060
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct dictionary {
	char str[12];
	struct dictionary *p_left;
	struct dictionary *p_right;
}STR;

STR *p_root = NULL;

void insert(char value[]);
char *find(char value[]);
STR *makeNewnode(char value[]);

int main(void) {

	int n;
	int i = 0;
	char value[12];
	char command[10];
	STR *p_root = NULL;

	scanf("%d", &n);

	while (scanf("%s", &value) != EOF) {
		i++;
		if (value[0] == 'i' || value[0] == 'f') {
			strcpy(command, value);
		}
		else {
			if (strcmp(command, "insert") == 0) {
				insert(value);
			}
			else {
				printf("%s\n", find(value));
			}
		}
		if (i >= 2 * n) {
			break;
		}
	}
	return 0;
}

void insert(char value[]) {

	STR *p_newlist = NULL;
	STR *p_list;

	p_newlist = makeNewnode(value);

	if (p_root == NULL) {
		p_root = p_newlist;
		return;
	}
	p_list = p_root;
	
	while (1) {
		if (strcmp(p_list->str, value) > 0) {
			if (p_list->p_left == NULL) {
				p_list->p_left = p_newlist;
				break;
			}
			else {
				p_list = p_list->p_left;
			}
		}
		else {
			if (p_list->p_right == NULL) {
				p_list->p_right = p_newlist;
				break;
			}
			else {
				p_list = p_list->p_right;
			}
		}
	}
}

char *find(char value[]) {

	STR *p_list;
	char *ans = NULL;

	p_list = p_root;
	if (p_list == NULL) {
		ans = "no";
		return ans;
	}
	while (1) {
		if (strcmp(p_list->str, value) > 0) {
			if (p_list->p_left == NULL) {
				ans = "no";
				return ans;
			}
			else {
				p_list = p_list->p_left;
			}
		}
		else if(strcmp(p_list->str, value) < 0){
			if (p_list->p_right == NULL) {
				ans = "no";
				return ans;
			}
			else {
				p_list = p_list->p_right;
			}
		}
		else {
			ans = "yes";
			return ans;
		}
	}
}

STR *makeNewnode(char value[]) {

	STR *p_newlist;

	p_newlist = (STR*)malloc(sizeof(STR));
	strcpy(p_newlist->str, value);
	p_newlist->p_left = NULL;
	p_newlist->p_right = NULL;

	return p_newlist;
}

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

using namespace std;

#define PB push_back
#define f first
#define s second
#define what_is(x) cerr << #x << " is " << x << endl;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

const ll MOD = 1000000007;

const int N = 200005;

void set_file_io(string in, string out)
{
    freopen((in+".in").c_str(), "r", stdin);
    freopen((out+".out").c_str(), "w", stdout);
}

int siz[N], par[N];

int get_root(int x)
{
    while(x != par[x])
    {
        x = par[x];
    }
    return x;
}

void unite(int x, int y)
{
    x = get_root(x);
    y = get_root(y);
    if(x == y)
        return;
    if(siz[x] < siz[y])
    {
        swap(x, y);
    }
    siz[x] += siz[y];
    par[y] = x;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //set_file_io("input", "output");
    int n, m;
    cin >> n >> m;
    for(int i=0; i<n; i++)
    {
        siz[i] = 1;
        par[i] = i;
    }
    for(int i=0; i<m; i++)
    {
        int x, y;
        cin >> x >> y;
        x--; y--;
        unite(x, y);
    }
    cout << *max_element(siz, siz+n);
    return 0;
}


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


int main(){
    int N, K;
    scanf("%d %d", &N, &K);
    int a = 0;
    int b = 0;
    int num;
    int input;
    char numbers_str;
    vector<int> v;
    while(a < K){
        scanf("%d", &num);
        b=0;
        for(b = 0; b < num; b++){
            cin >> input;
            //cout << input << endl;
            v.push_back(input);
        }
        
        a++;
    }
    int iter, count0, count1;
    count1 = 0;
    for(iter = 1; iter < N + 1; iter++){
        count0 = count(v.begin(), v.end(), iter);
        //cout << count0 << endl;
        if (count0 == 0){
            count1 += 1;
        }
        
    }
    printf("%d\n", count1);
}

Measured memory_bytes: 3808
#include <stdio.h>

int main() {
  int X, A, B;
  scanf("%d %d %d", &X, &A, &B);
  int distA = (X > A) ? X - A : A - X;
  int distB = (X > B) ? X - B : B - X;
  printf("%c\n", (distA < distB) ? 'A' : 'B');
  return 0;
}


Measured memory_bytes: 3200
#include <iostream>
#include <map>
#define int long long
using namespace std;

int n;
int a[200001];

signed main() {
	int i;
	
	cin >> n;
	for (i = 0; i < n; i++) cin >> a[i + 1];
	for (i = 0; i < n; i++) a[i + 1] += a[i];
	
	map<int, int> dict;
	int ans = 0;
	for (i = n; i >= 0; i--) {
		if (dict.find(a[i]) != dict.end()) ans = max(ans, dict[a[i]] - i);
		if (dict.find(a[i]) == dict.end()) dict[a[i]] = i;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 17136
import sys
def input():
    return sys.stdin.readline()[:-1]

K,N = map(int,input().split(' '))
l = list(map(int, input().split()))

pre = l[0]
MAX = pre+K - l[-1]
for i in range(1,N):
    k = l[i]
    d = k - pre
    MAX = max(MAX,d)
    pre = k
print(K-MAX)

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

int main()
{
	
	int N, K;

	cin >> N >> K;

	int count = 0;

	while (N--)
	{
		int a;
		cin >> a;
		
		if (a >= K) {
			count++;
		}

	}

	cout << count << endl;

	return 0;
}

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

int main(){
  vector<int> n(5);

  cin >> n[0] >> n[1] >> n[2] >> n[3] >> n[4];

  sort(n.begin(), n.end(), greater<int>());

  for(int i=0; i<n.size(); i++) {
    cout << n[i];
    if(i==n.size()-1){
      cout << "\n";
    }else{
      cout << " ";
    }
  }
  return 0;
}

Measured memory_bytes: 1212
#include <stdio.h>
 
int main(void){
  int x,y,a;
 
  scanf("%d %d",&x,&y);
 
  while (x!=0 || y!=0) {
    if (x > y) {
      a = x;x = y;y = a;
    }
    printf("%d %d\n",x,y);
    scanf("%d %d",&x,&y);
  }
  return 0;
}

Measured memory_bytes: 1032
# 足す時はi番目に足し、返すのは累積和
class sumBIT():
    def __init__(self, N):
        self.N = N
        self.bit = [0 for _ in range(self.N+1)]
    
    def __str__(self):
        ret = []
        for i in range(1, self.N+1):
            ret.append(self.__getitem__(i))
        return "[" + ", ".join([str(a) for a in ret]) + "]"

    def __getitem__(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.N:
            self.bit[i] += x
            i += i & -i

import sys
input = sys.stdin.readline

N = int(input())
S = list(input().rstrip())
Q = int(input())
Query = [list(map(str, input().split())) for _ in range(Q)]

Alp = [chr(i) for i in range(97, 97+26)]
BITs = {}
for i, a in enumerate(Alp):
    bit = sumBIT(N+3)
    BITs[a] = bit

for i, s in enumerate(S):
    BITs[s].add(i+2, 1)

for WWW, x, y in Query:
    if WWW == "1":
        i = int(x)
        for alp in Alp:
            if BITs[alp][i+1] - BITs[alp][i] > 0:
                BITs[alp].add(i+1, -1)
                break
        BITs[y].add(i+1, 1)
    else:
        l = int(x)
        r = int(y)
        ans = 0
        for alp in Alp:
            if BITs[alp][r+1] - BITs[alp][l] > 0:
                ans += 1
        print(ans)

Measured memory_bytes: 265768
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {";  \
	for(auto v: x) cerr << v << ","; cerr << "}" << endl;
#else
#define show(x) true
#define dump(x) true
#endif

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);
	
	int N; cin >> N;
	double s = 0;
	rep(i,N){
		double x;
		cin >> x;
		s += 1/x;
	}
	cout << 1/s << endl;
}


Measured memory_bytes: 256
# coding: utf-8
n, x = map(int,input().split())
A = list(map(int,input().split()))
S = sum(A)
for i in range(n-1):
    s = A[i+1] + A[i]
    if s > x:
        if s-x > A[i+1]:
            t = s-x-A[i+1]
            A[i+1] = 0
            A[i] -= t
        else:
            A[i+1] -= s - x
print(S - sum(A))

Measured memory_bytes: 85504
#include <bits/stdc++.h>
using namespace std;
int main() {
	string s;
	cin >> s;
	int len = s.size();
	reverse(s.begin(), s.end());
	if (s[0] == '1' || s[len - 1] == '0') {
		puts("-1");
		return 0;
	}
	for (int i = 1; i < len; ++i) {
		if (s[i] != s[len - i]) {
			puts("-1");
			return 0;
		}
	}
	int m = 1;
	for (int i = 1; i < len; ++i) {
		printf("%d %d\n", m, i + 1);
		if (s[i] == '1') m = i + 1;
	}
	return 0;
}

Measured memory_bytes: 3828
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
typedef long long ll;
using namespace std;
int a[105];
int tu[105];
int n;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	a[0]=a[1];
	memset(tu,0,sizeof(tu));
	for(int i=1;i<=n;i++)
	{
		if(a[i]>a[i-1])
		tu[i]=1;
		//cout<<"???"<<endl;
	}
	for(int i=1;i<=n;i++)
	{
		if(tu[i]==1&&tu[i+1]==0)
		tu[i]=2;//售出点 
	}
	for(int i=1;i<=n;i++)
	{
		if(tu[i]==0&&tu[i+1]>0)
		tu[i]=3;//买入点 
	}
	ll num=0;
	ll ha=1000;
	for(int i=1;i<=n;i++)
	{
		if(tu[i]==3)
		{
		
			ll t=ha/a[i];
			num+=t;
			ha=ha-t*a[i];
		}
		else if(tu[i]==2)
		{
			ll tt=num*a[i];
			ha+=tt;
			num=0;
		}
		if(i==n)
		{
		ll tt=num*a[i];
			ha+=tt;
			num=0;	
		}
	}
	cout<<ha<<endl;
}

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


#define off ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define lmax1 9223372036854775807
#define max1 2147483647
#define lmin1 -9223372036854775808
#define pi 3.141592653589793116
#define mod 1e9+7

int main() {
    off;
    string s;
    cin>>s;
    stack <int> o,z;
    int c=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='1')
        {
            if(z.size()==0)
                o.push(1);
            else
            {
                z.pop();
                c+=2;
            }
        }
        else 
        {
            if(o.size()==0)
                z.push(0);
            else
            {
                o.pop();
                c+=2;
            }
        }
    }
    cout<<c<<'\n';
      return 0;
}

Measured memory_bytes: 720
#include <iostream>
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define pii std::pair<int,int>
#define pli std::pair<ll,int>
#define pil std::pair<int,ll>
#define psi std::pair<string,int>
#define pll std::pair<ll,ll>
#define pci std::pair<char,int>
#define sll(x) scanf("%lld",&x)
#define prll(x) printf("%lld ",x)
#define pri(x) printf("%d ",x)
#define si(x) scanf("%d",&x)
#define pb push_back
#define vll std::vector<ll>
#define vpi std::vector<std::pair<int,int>>
#define vi std::vector<int>
#define vvi std::vector<std::vector<int>>
#define vvpil std::vector<std::vector<std::pair<int,ll>>>
#define vlpii std::vector<std::list<pii>>
#define vlpil std::vector<std::list<pil>>
#define li std::list<int>
#define lpil std::list<pil>
#define Endl printf("\n")
#define vli vector<list<int>>
#define vvll vector<vector<ll>>
#define mp make_pair
#define ma 100000000
#define imie(...) "[" << #__VA_ARGS__": " << (__VA_ARGS__) << "] "
const ll  INF=10000000000000;
const ll mod = 1e9 + 7;
using namespace std;
void add(int& a , int b){
	a += b;
	if(a >= mod) a -= mod;
}
ll mul(ll a , ll b){
	return (a * b) % mod;
} 

int main(){
	IOS;
	int n ; cin >> n;
	string s ; cin >> s;
	int dp[n + 5][n +5];
	memset(dp , 0 , sizeof dp);
	dp[1][1] = 1;
	for(int i = 0 ; i < n - 1; i++){
		vector<int> pref(i + 3);
		pref[1] = dp[i + 1][1];
		for(int j = 2 ; j < i + 2; j++) pref[j] = (pref[j - 1] + dp[i + 1][j]) % mod;
		for(int j = 1 ; j <= i + 2; j++){
			int l ,r ;
			if(s[i] == '>'){
				l = j  ; r = i + 1;
			}
			else {
				l = 1 ; r = j -1;
			}
			if(l <= r)add(dp[i + 2][j] , (pref[r] - pref[l - 1] + mod)%mod) ;
		}
	}
	int ans = 0;
	for(int i = 0 ; i <= n ; i++) {add(ans , dp[n][i]);}
	cout << ans << "\n";
			
	return 0;
}


Measured memory_bytes: 35584
/*
    -ensure correct output format
    -ensure printing required output
    -reread the problem statement
  */

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pll;
typedef pair<ll,pair<ll,ll>>plll;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL));
#define vll(v) v.begin(),v.end()
#define all(x) x.rbegin(),x.rend()
#define min3(a, b, c)   min(a, min(b, c))
#define max3(a, b, c)   max(a, max(b, c))
#define F first
#define S second
#define in  freopen("input.txt", "r", stdin)
#define out  freopen("output.txt", "w", stdout)
#define minheap int,vector<int>,greater<int>
#define pb push_back
#define eb emplace_back
#define ischar(x)  (('a' <= x && x <= 'z') || ('A' <= x && x <= 'Z'))
#define isvowel(ch) ((ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u')||(ch=='A'|| ch=='E' || ch=='I'|| ch=='O'|| ch=='U'))
#define bug cout<<"BUG"<<endl;
const int Max = 2e6 + 10;
const int Mod = 1e9 + 7;
const double PI  =3.141592653589793238463;
bool compare(const pair<ll,ll> &a, const pair<ll,ll> &b)
{
    if(a.S==b.S)
        return a.F>b.F;

       return (a.S > b.S);
}
ll lcm(ll a,ll b)
{
    if(a==0 || b==0)return 0;

    return a/__gcd(a,b)*b;
}

void input(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)cin>>ara[i];
}
void print(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)
        cout<<ara[i]<<" ";
    cout<<endl;
}


int main()
{

   fastread();

   ll i,j,n,m,p,a,sum=0,k,t,b,c,d,cnt=0,q,l,r,ans=0;

      bool flag=false;

      string str;

      cin>>n>>m;

      vector<pll>v;





      for(i=0; i<n; i++)
      {
          cin>>a>>b;

          v.eb(a,b);
      }

      sort(vll(v),greater<pll>());

      priority_queue<ll>pq;



      for(i=1; i<=m; i++)
      {
          while(!v.empty() && i>=v.back().F)
          {
              pq.push(v.back().S);

              v.pop_back();
          }

          if(!pq.empty())
          {
              ans+=pq.top();

              pq.pop();
          }
      }

      cout<<ans<<endl;











}



Measured memory_bytes: 6556
//EatingSymbolsEasy.java
import java.util.Scanner;
class Main
{
	public static void main(String args[])
	{
		Scanner sc=new Scanner(System.in);
        String s=sc.next();
        int ans=0;
        for(int i=0; i<4; i++){
            if(s.charAt(i)=='+'){
                ans++;
            }
            else{
                ans--;
            }
        }
        System.out.println(ans);
        sc.close();
    }
}

Measured memory_bytes: 21972
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

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; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }

string k = "keyence";
string S;
int main() {
    while (cin >> S) {
        int n = S.size();
        bool ok = false;
        for (int i = 0; i < n; ++i) {
            for (int j = i; j <= n; ++j) {
                string tmp = S.substr(0, i) + S.substr(j);
                if (tmp == k) ok = true;
            }
        }
        if (ok) puts("YES");
        else puts("NO");
    }
}















Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define MOD 1000000007
using namespace std;

// int prime[1000001];
// vector<ll> primes;

// void soe() {
//     int i,j;
//     for(i=2;i<1000001;i++) prime[i] = 1;
//     for(i=2;i<=sqrt(1000001);i++) {
//         if(prime[i] == 1) {
//             for(j=i*i;j<1000001;j+=i) {
//                 prime[j] = 0;
//             }
//         }
//     }
//     for(i=2;i<1000001;i++) {
//         if(prime[i]) primes.pb(i);
//     }
// }

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int a,b,c;
    cin >> a >> b >> c;
    if(a+b+c>=22) cout << "bust";
    else cout << "win"; 
    cout << "\n";
    return 0;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)

using namespace std;
using ll = long long;
using P = pair<int, int>;
using LP = pair<ll, ll>;

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

    int q;
    cin>>q;
    map<string, int> mp;
    rep(i, q) {
        int c;
        string k;
        cin>>c>>k;
        if (c == 0) {
            int x;
            cin>>x;
            mp[k] = x;
        }
        else {
            cout<<mp[k]<<endl;
        }
    }
}


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

int n, mx;
int a[200005];
map<int, int> mp;

bool check(int lmt) {
  mp.clear();
  int now = 0;
  for (int i = 1; i <= n; ++i) {
    if (a[i] > now) now = a[i];
    else {
      now = a[i];
      while (!mp.empty()) {
        int last = (--mp.end())->first;
        if (last >= now) mp.erase(last);
        else break;
      }
      int nnow = now - 1;
      mp[nnow]++;
      while (nnow >= 0 && mp[nnow] >= lmt) {
        mp.erase(nnow);
        --nnow;
        mp[nnow]++;
      }
      if (nnow < 0) return false;
    }
  }
  return true;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i)
    scanf("%d", a + i);
  bool flag = true;
  for (int i = 1; i <= n; ++i)
    flag &= (a[i] > a[i - 1]);
  if (flag) return puts("1") & 0;
  mx = *max_element(a + 1, a + n + 1);
  int l = 2, r = n, ans = n;
  while (l <= r) {
    int mid = l + r >> 1;
    if (check(mid)) ans = mid, r = mid - 1;
    else l = mid + 1;
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <map>
#include <algorithm>
#include <queue>
#include <cstdio>

using namespace std;

int main(){
    long n, m;
    long long ans = 0;
    cin >> n >> m;
    priority_queue<long> price;
    for(int i=0; i<n; i++){
        long a;
        cin >> a;
        price.push(a);
    }
    for(int i=0; i<m; i++){
        long a_new;
        a_new = price.top()/2;
        price.pop();
        price.push(a_new);
    }
    while(!price.empty()){
       ans += (long long)price.top();
       price.pop();
    }

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


Measured memory_bytes: 1400
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	static int[][] map;
	static int[][] directions8= {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
	static int[][] directions4= {{-1,0},{1,0},{0,-1},{0,1}};
	static int ans;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		while(true) {

			int N = sc.nextInt();
			int M = sc.nextInt();

			if((N|M)==0) {
				break;
			}

			int[] S = new int[M];
			int[] k = new int[M];
			Kaitousha[] maxScores = new Kaitousha[N];
			for(int i = 0; i < N; i++) {
				maxScores[i] = new Kaitousha();
				maxScores[i].idx = i;
			}
			Kaitousha[] minScores = new Kaitousha[N];
			for(int i = 0; i < N; i++) {
				minScores[i] = new Kaitousha();
				minScores[i].idx = i;
			}
			for(int i = 0; i < M; i++) {
				S[i]=sc.nextInt();
				k[i] = sc.nextInt();
				for(int j = 0; j <k[i]; j++) {
					int c = sc.nextInt()-1;
					maxScores[c].score+=S[i];
					if(k[i] == 1) {
						minScores[c].score += S[i];
					}
				}
			}

			Arrays.sort(maxScores, Comparator.reverseOrder());
			Arrays.sort(minScores);

			long ans = maxScores[0].score - minScores[0].score;

			if(maxScores[0].idx == minScores[0].idx) {
				long p1 = maxScores[1].score - minScores[0].score;
				long p2 = maxScores[0].score - minScores[1].score;

				ans = Math.max(p1, p2);

			}
			System.out.println(ans+1);
		}
	}

	//BFS用に二つの配列を足し算する
	static int[] addArrayElms(int[] a, int[] b) {
		int[] c = new int[a.length];
		for(int i = 0; i < a.length; i++) {
			c[i] = a[i] + b[i];
		}
		return c;
	}

//	//二分探索
	//k <= num となる最小の配列要素kのインデックスを返す
	static private int binarySearch(long num, long[] orderedArray){
		int lowerBorder = -1;
		int upperBorder = orderedArray.length;
		int mid;

		while(upperBorder - lowerBorder >1) {
			mid = (upperBorder + lowerBorder)/2;
			if(orderedArray[mid]<=num) {
				lowerBorder = mid;
			}else {
				upperBorder = mid;
			}
		}
		return lowerBorder;
	}

	//二分探索
	//k <= num となる最小のList要素kのインデックスを返す
	static private int binarySearch(long num, ArrayList<Long> orderedList){
		int lowerBorder = -1;
		int upperBorder = orderedList.size();
		int mid;

		while(upperBorder - lowerBorder >1) {
			mid = (upperBorder + lowerBorder)/2;
			if(orderedList.get(mid)<=num) {
				lowerBorder = mid;
			}else {
				upperBorder = mid;
			}
		}
		return lowerBorder;
	}

	//aとbの最小公倍数を求める
	public static int gcd(int a, int b) {
		return b == 0 ? a: gcd(b, a % b);
	}
	public static long gcd(long a, long b) {
		return b == 0 ? a: gcd(b, a % b);
	}
}

class Kaitousha implements Comparable<Kaitousha>{
	int idx;
	long score;
	@Override
	public int compareTo(Kaitousha o) {
		if(this.score < o.score) {
			return -1;
		}else if(this.score > o.score){
			return 1;
		}else {
			return 0;
		}
	}
}




Measured memory_bytes: 165676
import java.io.*;
  
class Main{
  
static final PrintWriter out=new PrintWriter(System.out);
  
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String line="";
while((line=br.readLine())!=null&&!line.isEmpty()){
int n=Integer.parseInt(line);
int[] r=new int[n];
for(int i=0;i<n;i++) r[i]=Integer.parseInt(br.readLine());
int ans=Integer.MIN_VALUE;
int min=r[0];
for(int i=1;i<n;i++){
ans=Math.max(ans,r[i]-min);
min=Math.min(min,r[i]);
}
out.println(ans);
out.flush();
}
}
}

Measured memory_bytes: 38056
#include<stdio.h>

void fib(void);

int F[44];
int main(){

  int n;

  scanf("%d",&n);

  fib();
  printf("%d\n",F[n]);

  return 0;
}

void fib(void){
  int i;

  F[0]=1;
  F[1]=1;

  for(i=2;i<45;i++){
    F[i]=F[i-2]+F[i-1];
  }
}

Measured memory_bytes: 596
"use strict";

// read lines from stdin
const input = require("fs")
  .readFileSync("/dev/stdin", "utf8")
  .split("\n");

const N = parseInt(input[0], 10);

let sum = 0;

for (let i = 1; i <= N; i++) {
  const line = input[i].split(" ");
  const value = parseFloat(line[0], 10);
  const type = line[1];

  if (type === "JPY") { sum += value; }
  else { sum += (value * 380000.0); }
}

console.log(sum);


Measured memory_bytes: 7372
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll=long long;
int main(){
    int n,k;
    cin>>n>>k;
    int ans=1;
    for(int i=1; i<=n; ++i){
        if(i==1){
            ans*=k;
        }
        else{
            ans*=k-1;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
a, b, c = map(int, input().split())
passed = set()
time = 0
while True:
    if time % 60 <= c <= time % 60 + a:
        print(c + time // 60 * 60)
        break
    else:
        time += a + b
        if time % 60 in passed:
            print(-1)
            break
        else:
            passed.add(time % 60)


Measured memory_bytes: 5596
#include <stdio.h>

int main(){
    int h, w;
    int i, j;
    while(1){
        scanf("%d %d ", &h, &w);
        if(h==0&&w==0)break;
        for(i=0;i<h;i++){
            for(j=0;j<w;j++){
                printf("#");
            }
            printf("\n");
        }
        printf("\n");
    }

    return 0;
}


Measured memory_bytes: 2048
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <deque>
#include <string>
#include <stack>
#include <unordered_set>
#include <cmath>
#define endl '\n'
#define ll unsigned long long
//#define mod 1000000007

using namespace std;
int N;
bool visited[100001];
struct Node {
	int num;
	int x;
	int y;
};

struct Edge {
	int to;
	int weight;
};
Node* towns;
vector<Edge>* adj;

bool operator<(Edge a, Edge b) { return a.weight > b.weight; }

int MST()
{
	int ret = 0;
	priority_queue<Edge> quu;
	for (int i = 0; i < adj[1].size(); i++)
		quu.push(adj[1][i]);
	visited[1] = true;

	while (!quu.empty())
	{
		auto cur = quu.top(); quu.pop();
		if (visited[cur.to]) continue;
		visited[cur.to] = true;
		ret += cur.weight;
		for (int i = 0; i < adj[cur.to].size(); i++)
			quu.push(adj[cur.to][i]);
	}

	return ret;
}

int main(void)
{
	cin.tie(NULL); ios_base::sync_with_stdio(false);
	cin >> N;
	towns = new Node[N + 1]();
	adj = new vector<Edge>[N + 1]();
	for (int i = 1; i <= N; i++)
	{
		int x, y; cin >> x >> y;
		towns[i] = Node{ i, x, y };
	}
	sort(&towns[1], &towns[N + 1], [](Node a, Node b) { return a.x < b.x; });
	for (int i = 1; i < N; i++)
	{
		auto cur = towns[i];
		auto next = towns[i + 1];
		adj[cur.num].push_back(Edge{ next.num, next.x - cur.x });
		adj[next.num].push_back(Edge{ cur.num, next.x - cur.x });
	}

	sort(&towns[1], &towns[N + 1], [](Node a, Node b) {return a.y < b.y; });
	for (int i = 1; i < N; i++)
	{
		auto cur = towns[i];
		auto next = towns[i + 1];
		adj[cur.num].push_back(Edge{ next.num, next.y - cur.y });
		adj[next.num].push_back(Edge{ cur.num, next.y - cur.y });
	}
	cout << MST() << endl;
	return 0;
}

Measured memory_bytes: 11640
#include <cmath>
#include <cstdio>
using namespace std;
int main()
{
	int n;
	double x, y, x1, x2, x3, y1, y2, y3, a1, a2, b1, b2, c1, c2;
	scanf("%d", &n);
	for( ; n > 0; n--) {
		scanf("%lf%lf%lf%lf%lf%lf", &x1, &y1, &x2, &y2, &x3, &y3);
		a1=2*(x2-x1),b1=2*(y2-y1);
		c1=x1*x1-x2*x2+y1*y1-y2*y2;
		a2=2*(x3-x1),b2=2*(y3-y1);
		c2=x1*x1-x3*x3+y1*y1-y3*y3;
		x=(b1*c2-b2*c1)/(a1*b2-a2*b1);
		y=(c1*a2-c2*a1)/(a1*b2-a2*b1);
		printf("%.3lf %.3lf %.3lf\n", x, y, hypot(x - x1, y - y1));
	}

	return 0;
}

Measured memory_bytes: 1096
#include<iostream>

int main(){
int a,b;
std::cin>>a>>b;
if(a<b){
std::cout<<"a < b"<<std::endl;
}else if(a>b){
std::cout<<"a > b"<<std::endl;
}else{
std::cout<<"a == b"<<std::endl;
}

return 0;

}

Measured memory_bytes: 3068
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9
#define PI 3.14159265359
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define ALLR(v) v.rbegin(),v.rend()
typedef long long ll;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//isPrime
//modpow modinv
//getDigit
int main() {
  cout << fixed << setprecision(10);
  int a,b,c;
  cin >> a >> b >> c;
  if(c>=a&&c<=b){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long ll;

const int MX = 10011;
const int oo = 2000000002;

int fst[MX],nxt[MX*2],u[MX*2],v[MX*2],w[MX*2],c[MX*2],lnum;

void init()
{
    memset(fst,0xff,sizeof(fst));
    lnum=-1;
}

void addeg(int nu,int nv,int nw,int nc)
{
    lnum++;
    nxt[lnum]=fst[nu];
    fst[nu]=lnum;
    u[lnum]=nu;
    v[lnum]=nv;
    w[lnum]=nw;
    c[lnum]=nc;

	lnum++;
	nxt[lnum]=fst[nv];
	fst[nv]=lnum;
    u[lnum]=nv;
    v[lnum]=nu;
    w[lnum]=0;
    c[lnum]=-nc;
}

ll dist[MX];
int book[MX],q[MX],pre[MX],frnt,rare,now;
void spfa(int frm,int to,int *flow,ll *cost)
{
	memset(dist,0x9f,sizeof(dist));
    frnt=rare=1;
    q[rare]=frm;
    dist[frm]=0;
    book[frm]=1;
    pre[frm]=-1;
    while(frnt>=rare)
    {
        book[q[rare]]=0;
        now=q[rare++];
        for(int i=fst[now];i!=-1;i=nxt[i])
        {
            if(w[i]>0&&dist[v[i]]<dist[now]+c[i])
            {
                dist[v[i]]=dist[now]+c[i];
                pre[v[i]]=i;
                if(book[v[i]]==0)
                {
                    book[v[i]]=1;
                    q[++frnt]=v[i];
                }
            }
        }
    }
    int mxfl=+oo;
	ll mxcs=0;
    now=pre[to];
    while(now!=-1)
    {
        mxfl=min(mxfl,w[now]);
        mxcs+=c[now];
        now=pre[u[now]];
    }
    now=pre[to];
    while(now!=-1)
    {
        w[now]-=mxfl;
        w[now^1]+=mxfl;
        now=pre[u[now]];
    }
    *flow+=mxfl;
    *cost+=mxcs*mxfl;
}

void maxcost(int from,int to,int need)
{
    int flow=0;
	ll cost=0;
    while(flow<need) spfa(from,to,&flow,&cost);
	printf("%lld\n",cost);
}

int n, s;
int rx[MX],ry[MX],rc[MX],bx[MX],by[MX],bc[MX];
int S,T,V1,V2,V3,V4;

void input()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d%d",rx+i,ry+i,rc+i),s+=rc[i];
	for(int i=1;i<=n;i++) scanf("%d%d%d",bx+i,by+i,bc+i);
}

void build()
{
	S=2*n+1,T=2*n+6;
	V1=2*n+2,V2=V1+1,V3=V2+1,V4=V3+1;
	for(int i=1;i<=n;i++)
	{
		addeg(S,i,rc[i],0);
		addeg(i,V1,rc[i],-rx[i]-ry[i]);
		addeg(i,V2,rc[i],+rx[i]-ry[i]);
		addeg(i,V3,rc[i],+rx[i]+ry[i]);
		addeg(i,V4,rc[i],-rx[i]+ry[i]);
		addeg(V1,n+i,bc[i],+bx[i]+by[i]);
		addeg(V2,n+i,bc[i],-bx[i]+by[i]);
		addeg(V3,n+i,bc[i],-bx[i]-by[i]);
		addeg(V4,n+i,bc[i],+bx[i]-by[i]);
		addeg(n+i,T,bc[i],0);
	}
}

int main()
{
    init();
	input();
	build();
	maxcost(S,T,s);
    return 0;
}

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

int main()
{
  ios_base::sync_with_stdio(false);

  int n;
  int h[10];
  int temp;

  while(1){
    cin >> n;
    if(n == 0) break;

    for(int i = 0;i < 10;++i) h[i] = 0;

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

    for(int i = 0;i < 10;++i){
      if(h[i] == 0){
	cout << "-" << endl;
      }else{
	for(int j = 0;j < h[i];++j){
	  cout << "*";
	}
	cout << endl;
      }
    }

  }

  return 0;
}



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

string pluszero(int N){
    string T=to_string(N);
    if(T.size()>=6){
        return T;
    }
    else{
        int k=T.size();
        rep(i,6-k){
            T="0"+T;
        }
        return T;
    }
}

int main(){
    int N,M;
    cin>>N>>M;
    vector<ll>mark(N,0);
    //i番目の県に何個の市ができているか
    vector<string>Ans(M);
    vector<tuple<ll,ll,ll>>city(M);
    //できた年,市の番号,所属県
    rep(i,M){
        ll P,Y;
        cin>>P>>Y;
        P--;
        get<0>(city[i])=Y;
        get<1>(city[i])=i;
        get<2>(city[i])=P;
    }
    sort(city.begin(),city.end());
    rep(i,M){
        mark[get<2>(city[i])]++;
        Ans[get<1>(city[i])]=pluszero(get<2>(city[i])+1)+pluszero(mark[get<2>(city[i])]);
    }
    rep(i,M){
        cout<<Ans[i]<<endl;
    }
}

Measured memory_bytes: 10112
#include <bits/stdc++.h>
#include<string.h>
#define ll long long 
#include<vector>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int main(){
	IOS;
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	while(1){
		c -= b;
		if(c <= 0)
		{
			cout << "Yes";
			return 0;
		}
		a -= d;
		if(a <= 0)
		{
			cout << "No";
			return 0;
		}
	}
	}

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

int main() {
    string s;
    cin >> s;


    int i = 0;
    int N = s.size();
    string t;
    while (2 * i < N) {
        t.push_back(s.at(2 * i));
        i++;
    }
    cout << t << endl;
}


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


int main()
{
    string S,ans;
    cin >> S;

    for(int i=-1; i<2; ++i)
    {
        if(i==0) continue;
        for(int j=-1; j<2; ++j)
        {
            if(j==0) continue;
            for(int k=-1; k<2; ++k)
            {
                if(k==0) continue;
                // cout << i << j << k << endl;
                // cout << (int)S[0]+(int)S[1]*i+(int)S[2]*j+(int)S[3]*k << endl;
                // cout << stoi(S.substr(0,1)) << stoi(S.substr(1,2)) << stoi(S.substr(2,3)) << stoi(S.substr(3,4)) << endl;
                // cout << stoi(S.substr(0,1))+stoi(S.substr(1,2))*i+stoi(S.substr(2,3))*j+stoi(S.substr(3,4))*k << endl;
                if(stoi(S.substr(0,1))+stoi(S.substr(1,1))*i+stoi(S.substr(2,1))*j+stoi(S.substr(3,1))*k == 7)
                {
                    if(i==-1)
                    {
                        ans += S.substr(0,1) + "-";   
                    }
                    else
                    {
                        ans += S.substr(0,1) + "+";
                    }
                    if(j==-1)
                    {
                        ans += S.substr(1,1) + "-";   
                    }
                    else
                    {
                        ans += S.substr(1,1) + "+";
                    }
                    if(k==-1)
                    {
                        ans += S.substr(2,1) + "-";   
                    }
                    else
                    {
                        ans += S.substr(2,1) + "+";
                    }
                    ans += S.substr(3,1) + "=7";
                    // cout << i << j << k << endl;
                    cout << ans << endl;
                    return 0;
                    // break;
                }
            }
        }
    }

    // cout << S.substr(0,1) << " " << stoi(S.substr(0,1)) << endl;
    // cout << S.substr(1,1) << " " << stoi(S.substr(1,1)) << endl;
    // cout << S.substr(2,1) << " " << stoi(S.substr(2,1)) << endl;
    // cout << S.substr(3,1) << " " << stoi(S.substr(3,1)) << endl;

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

Measured memory_bytes: 256
x , y = map(int,input().split())
A = [1,3,5,7,8,10,12]
B = [4,6,9,11]
C = [2]
if x in A and y in A:
  print("Yes")
elif  x in B and y in B:
  print("Yes")  
else:
  print("No")

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<P> VP;
typedef vector<vector<ll>> VV;
typedef vector<vector<int>> VVi;

#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)
const ll INF=1e18+18;
const ll MAX=100005;
const ll MOD=1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define REPM(i, mp) for (auto i = mp.begin(); i != mp.end(); ++i)
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbgmap(mp) cerr << #mp << ":"<<endl; for (auto i = mp.begin(); i != mp.end(); ++i) { cerr << i->first <<":"<<i->second << endl;}
#define dbgarr(n,m,arr) rep(i,n){rep(j,m){cerr<<arr[i][j]<<" ";}cerr<<endl;}
#define dbgdp(n,arr) rep(i,n){cerr<<arr[i]<<" ";}cerr<<endl;
#define dbgmint(n,arr) rep(i,n){cerr<<arr[i].x<<" ";}cerr<<endl;
#define out(a) cout<<a<<endl
#define out2(a,b) cout<<a<<" "<<b<<endl
#define vout(v) rep(i,v.size()){cout<<v[i]<<" ";}cout<<endl
#define Uniq(v) v.erase(unique(v.begin(), v.end()), v.end())
#define fi first
#define se second

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

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

template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,v.size())i>>v[j];return i;}

// vector
template<typename T>
ostream &operator<<(ostream &s, const vector<T> &v) {
    int len=v.size();
    for(int i=0; i<len; ++i) {
        s<<v[i];
        if(i<len-1) s<<"	";
    }
    return s;
}

// 2 dimentional vector
template<typename T>
ostream &operator<<(ostream &s, const vector<vector<T> > &vv) {
    int len=vv.size();
    for(int i=0; i<len; ++i) {
        s<<vv[i]<<endl;
    }
    return s;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<std::setprecision(10);

    string s;
    cin>>s;

    string a = "dream";
    string b = "dreamer";
    string c = "erase";
    string d = "eraser";

    ll n = s.length();
    Vs vs;
    vs = {a,b,c,d};
    Vec dp(n+1);
    dp[0] = 1;

    REP(i,0,n){
        if(!dp[i])continue;
        rep(j,4){
            if(i+vs[j].length()<=n && s.substr(i,vs[j].length())==vs[j]){
                dp[i + vs[j].length()] = 1;
            }
        }
    }
    YES(dp[n]);
    return  0;
}


Measured memory_bytes: 1232
#include <bits/stdc++.h>
using namespace std;
int n,k;
long long c[4001][4001];
const long long D=998244353;

int g(int x){
    int i,j;
    long long ret=0;
    long long t=1;
    for(i=0 ; i<=min(x,n) ; i++){
        ret+=c[x][i]*c[n+k-2*x-2][n-i]%D*t%D;
        ret%=D;
        if(i<n)ret+=c[x][i]*c[n+k-2*x-3][n-i-1]%D*t%D;
        ret%=D;
        t*=2;
        t%=D;
    }
    return ret;
}
int f(int flag,int x){
    if(flag==0)return g(x);
    int i,j;

    long long ret=0;
    long long t=1;
    for(i=0 ; i<=min(x,n); i++){
        ret+=c[x][i]*c[n+k-2*x-1][n-i]%D*t%D;
        ret%=D;
        t*=2;
        t%=D;
    }
    return ret;
}
int main(){
    int i,j;
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>k>>n;
    for(i=0 ; i<=4000 ; i++){
        c[i][0]=1;
        for(j=1 ; j<=i ; j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%D;
    }
    for(i=2; i<=2*k ; i++){
        if(i<=k+1)
            cout<<f(i%2,(i-1)/2);
        else
            cout<<f(i%2,(2*k-i+1)/2);
        cout<<"\n";
    }

    return 0;
}


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

int main(){
 string a,b,c;
cin>>a>>b>>c;
   if(a.at(a.size()-1)==b.at(0)&&b.at(b.size()-1)==c.at(0)){
     cout<<"YES"<<endl;
   }
  else{
    cout<<"NO"<<endl;
  }
}


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

ll int o,e,a;

int main(){
	ll int n,p;
	cin>>n>>p;
	for(int i=0;i<n;i++){
		cin>>a;
		if(a%2)
			o++;
		else
			e++;
	}
	if(o==0 && p)
		cout<<"0"<<endl;
	else
		cout<<(ll)round(pow(2,o-1))*(ll)round(pow(2,e))<<endl;
	return 0;
}

Measured memory_bytes: 512
using System;

class Program
{
	static void Main(string[] args)
	{
		string[] strInput = Console.ReadLine().Split(' ');
		Int64 a = Int64.Parse(strInput[0]);
		Int64 b = Int64.Parse(strInput[1]);
		Int64 n = Int64.Parse(strInput[2]);
		Int64 val;

		Int64 bestx = n >= b ? b - 1 : n;

		val = (Int64)(a * bestx / b) - a * (Int64)(bestx / b);
		Console.WriteLine(val);

		return;
	}
}


Measured memory_bytes: 27488
#!/usr/bin/env python3
#EDPC G

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
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()))

def dfs(s):
    if dp[s] != -1:
        return dp[s]
    elif len(edge[s]) == 0:
        dp[s] = 0
        return 0
    else:
        res = 0
        for v in edge[s]: 
            res = max(res,dfs(v)+1)
        dp[s] = res
        return res
n,m = LI()
dp = [-1]*n
edge = [[] for _ in range(n)]
for _ in range(m):
    x,y = LI()
    x -= 1
    y -= 1
    edge[x].append(y)

for i in range(n):
    dfs(i)
print(max(dp))

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

#define ll long long int

#define hell 1000000007

#define vi vector <ll>

#define pb push_back

#define pii pair<ll,ll>

#define vii vector <pii>

#define rep(i,a,b)  for(ll i=a;i<b;i++)

#define sep(i,a,b)  for(ll i=a-1;i>=b;i--)

#define inf (ll)(1e16)

using namespace std;

vi adj[100005];

vector < vector <bool> > visited(100005,vector <bool> (2,false));

vector < vi > dp (100005,vi (2,-1));

ll dfs(ll s,ll col,ll p)

{

    visited[s][col]=true;

    if(dp[s][col]!=-1)

        return dp[s][col];

    ll c=1;

    for(auto ch:adj[s])

    {

        if(ch==p)

            continue;

        if(!visited[ch][col])

            dp[ch][col]=dfs(ch,col,s);

        if(!visited[ch][1-col])

            dp[ch][1-col]=dfs(ch,1-col,s);

        if(col==1)

            c=(c*((dp[ch][col]+dp[ch][col-1])%hell))%hell;

        else

            c=(c*dp[ch][1-col])%hell;

    }

    return dp[s][col]=c;

}

void solve()

{

    ll n,u,v;

    cin>>n;

    rep(i,1,n)

    {

        cin>>u>>v;

        adj[u].pb(v);

        adj[v].pb(u);

    }

    dfs(1,0,-1);

    dfs(1,1,-1);

    cout<<(dp[1][0]+dp[1][1])%hell;

}

int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    ll t=1;

    //cin>>t;

    while(t--)

        solve();

    return 0;

}

Measured memory_bytes: 32128
n = gets.to_i
a = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)
sum = 0
n.times do |i|
  diff = a[i] + a[i+1] - b[i]
  if diff < 0
    sum += a[i] + a[i+1]
    a[i],a[i+1] = 0,0
  else
    sum += b[i]
    a_1 = b[i]
    a_2 = (a[i] - b[i]) > 0 ? 0 : (a[i] - b[i])
    a[i] -= a_1
    a[i+1] += a_2
  end
end
puts sum

Measured memory_bytes: 16408
using System;
using System.Linq;

namespace ABC163
{
    class D
    {
        static void Main(string[] args)
        {
            var NK = Console.ReadLine().Split().Select(long.Parse).ToArray();
            var N = NK[0]; var K = NK[1];

            long res = 0;
            for (long i = K; i <= N + 1; i++)
            {
                var min = i * (i - 1) / 2;
                var max = i * (2 * N - i + 1) / 2;
                var add = max - min + 1;
                res = (res + add) % 1000000007;
            }

            Console.WriteLine(res);
        }
    }
}


Measured memory_bytes: 28232
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = Integer.parseInt(sc.next());
        Map<Long, Long> map = new TreeMap<>();
        for (int i = 0; i < N; i++) {
            long in = Long.parseLong(sc.next());
            if (map.containsKey(in)) {
                map.put(in, map.get(in) + 1);
            } else {
                map.put(in, 1L);
            }
        }

        long ans = 0;
        for (Entry<Long, Long> ent : map.entrySet()) {
            long y = ent.getKey();
            long x = ent.getValue();
            if (x == y) {
                continue;
            }

            if (x > y) {
                ans += x - y;
            } else {
                ans += x;
            }
        }

        System.out.println(ans);
    }
}


Measured memory_bytes: 49300
/**
 * @Author:      G_bg
 * @DateTime:    2019-05-19 21:53:46
 * @Description: 
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double PI = 3.1415926535898;
const double E = 2.718281828459;
const int INF = 0x7fffffff;
const int mod = 1e9+7;
const int maxn = 1e5+10;
int main(int argc, char const *argv[]) {
  ios::sync_with_stdio(0);cin.tie(0);
  int m,k;cin >> m >> k;
  if(k == 0){
      for(int i = 0;i <= (1<<m)-1;i++){
        if(i == 0) cout << 0 << " " << 0;
        else cout << " " << i << " " << i;
      }
      cout << endl;
  }else {
      int ans = 0;
      for(int i = 0;i < (1<<m);i++)
        if(i != k) ans ^= i;
      if(ans == k){
          cout << k;
          for(int i = 0;i < (1<<m);i++)
            if(i != k) cout << " " << i;
          cout << " " << k;
          for(int i = (1<<m)-1;i >= 0;i--)
            if(i != k) cout << " " << i;
          cout << endl;
      }else cout << -1 << endl;
  }
  //system("pause");
  return 0;
}

Measured memory_bytes: 1792
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
inline int getint() {
	register char ch;
	while(!isdigit(ch=getchar()));
	register int x=ch^'0';
	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
	return x;
}
const int N=1e5+2;
char s[N];
int cnt[N];
int main() {
	const int n=getint(),q=getint();
	scanf("%s",&s[1]);
	for(register int i=2;i<=n;i++) {
		if(s[i]=='C'&&s[i-1]=='A') cnt[i]++;
	}
	for(register int i=1;i<=n;i++) {
		cnt[i]+=cnt[i-1];
	}
	for(register int i=0;i<q;i++) {
		const int l=getint(),r=getint();
		printf("%d\n",cnt[r]-cnt[l]);
	}
	return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
int n;
int p[55];
int main(int argc,char *argv[]){
	cin >> n;
	for (int i=1;i<=n;i++)	cin >> p[i];
	bool flag=1;
	for (int i=1;i<=n;i++)  	if (p[i]!=i){flag=0;break;}
	if (flag){puts("YES");return 0;}
	for (int i=1;i<=n;i++)
	  for (int j=1;j<=n;j++){
		  flag=1;
		  swap(p[i],p[j]);
		  for (int k=1;k<=n;k++){
			  if (p[k]!=k){
				  flag=0;
				  break;
			  }
		  }
		  if (flag){puts("YES");return 0;}
		  swap(p[i],p[j]);
	  }
	puts("NO");
	return 0;
}


Measured memory_bytes: 256