akhauriyash/Code-Regression huggingface dataset:
// 22
/****************************************************
https://searleser97.gitlab.io/algorithms/template.cpp
****************************************************/

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define fors(_, x, n, s) for (int _ = x; _ < n; _ += s)
#define forn(_, x, n) fors(_, x, n, 1)
#define rep(_, n) forn(_, 0, n)
#define forrs(_, x, n, s) for (int _ = x; _ > n; _ -= s)
#define forrn(_, x, n) forrs(_, x, n, 1)
#define rrep(_, n) forrn(_, n - 1, -1)
#define fi first
#define se second
#define pb push_back
#define pairii pair<int, int>
#define all(x) x.begin(), x.end()
#define cerr(s) cerr << "\033[48;5;196m\033[38;5;15m" << s << "\033[0m"
// typedef __int128_t lli;
typedef long long int li;
typedef long double ld;
// 12
const li inf = 1 << 60;

void _main(int tc) {
  li n, W;
  cin >> n >> W;
  vector<int> w(n), v(n);
  rep(i, n) { cin >> w[i] >> v[i]; }
  vector<vector<li>> mem(n, vector<li>(W + 1, -1));
  // function<li(int, int)> knapsack = [&](int i, int k) -> li {
  //   if (i == n) return 0;
  //   if (mem[i][k] != -1) return mem[i][k];
  //   if (k - w[i] >= 0) mem[i][k] = v[i] + knapsack(i + 1, k - w[i]);
  //   mem[i][k] = max(mem[i][k], knapsack(i + 1, k));
  //   return mem[i][k];
  // };
  // cout << knapsack(0, W) << endl;
  rrep(i, n) {
    rrep(k, W + 1) {
      if (i == n - 1) {
        if (k - w[i] >= 0) mem[i][k] = v[i];
        else mem[i][k] = 0;
        continue;
      }
      if (k - w[i] >= 0) mem[i][k] = v[i] + mem[i + 1][k - w[i]];
      mem[i][k] = max(mem[i][k], mem[i + 1][k]);
    }
  }
  cout << mem[0][W] << endl;
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  _main(0);
  return 0;
  int tc;
  cin >> tc;
  rep(i, tc) _main(i + 1);
}

Measured memory_bytes: 79488
#define _USE_MATH_DEFINES
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<deque>
#include<list>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<map>
#include<queue>
#include<vector>
using namespace std;

/*
0 1 2 3 4 5 6 7 8 9

*/

//int a(int n, int s, int f) {
//	int cnt = 0;
//	if (n > 2)
//		for (int i = f; i <= 9; i++) {
//			if (s - i > i)cnt += a(n - 1, s - i, i + 1);
//			else break;
//		}
//	else if (n == 2)
//		for (int i = f; i <= 9; i++) {
//			if (s - i <= 9 && s - i > i)cnt++;
//			else break;
//		}
//	else
//		cnt = 1;
//
//	return cnt;
//}

int a, S;

void dfs(int i, int s, int n) {
	//cout << i << " " << s << " " << n << endl;
	if (s == S&&n == 0) {
		a++;
		return;
	}
	if (i == 10 || n == 0)
		return;

	dfs(i + 1, s + i, n - 1);
	dfs(i + 1, s, n);
}

int main() {
	for (int n; cin >> n >> S && (n || S);) {
		a = 0;
		dfs(0, 0, n);
		cout << a << endl;
	}

	return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

using namespace std;

#define fori(x) for (int i = 0; i < x; ++i)
#define forj(x) for (int j = 0; j < x; ++j)

typedef long long ll;

const int INF = 2e9 + 5;
const int alength=100100;

int main() {
	int n;cin>>n;
	ll h[alength]={};fori(n){cin>>h[i];}
	int ans=0,c=0;
	fori(n-1){
		if(h[i]<h[i+1]){
			ans=max(ans,c);
			c=0;
		}else{
			++c;
		}
	}
	ans=max(ans,c);
	cout<<ans;
}

Measured memory_bytes: 4384
#include <cstdio>
#include <algorithm>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define lengthof(x) (sizeof(x) / sizeof(*(x)))
#define INF 1 << 20
#define MAX_M 101
using namespace std;

int main(){
  int n, m, a, b, c, t, p, q, r, s;  
  int C[MAX_M][MAX_M], T[MAX_M][MAX_M];
  while(true){
	scanf("%d %d", &n, &m);
	if((n | m) == 0){
	  break;
	}
	fill((int*) C, (int*)(C + lengthof(C)), INF);
	fill((int*) T, (int*)(T + lengthof(T)), INF);
	REP(i,n){
	  scanf("%d %d %d %d", &a, &b, &c, &t);
	  C[a][b] = C[b][a] = c;
	  T[a][b] = T[b][a] = t;
	}
	REP(k,m+1){
	  REP(i,m+1){
		REP(j,m+1){
		  C[i][j] = min(C[i][j], C[i][k] + C[k][j]);
		  T[i][j] = min(T[i][j], T[i][k] + T[k][j]);
		}
	  }
	}
	scanf("%d", &s);
	REP(i,s){
	  scanf("%d %d %d", &p, &q, &r);
	  if(r == 0){
		printf("%d\n", C[p][q]);
	  }
	  else{
		printf("%d\n", T[p][q]);
	  }
	}
  }
  return 0;
}

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

typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> ii;
typedef vector<vector<ll>> vvll;
typedef vector<pair<ll, ll>> vii;
typedef long double ld;
typedef vector<ld> vld;
typedef vector<vector<ld>> vvld;
typedef vector<bool> vbl;
typedef vector<vbl> mbl;
const ll MOD = 1e9 + 7;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll a, b, c, k;
    cin >> a >> b >> c >> k;
    if (k <= a)
        cout << k << endl;
    else if (k <= a + b)
        cout << a << endl;
    else
        cout << a - (k - a - b) << endl;
    return 0;
}

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

public class Main{
  public static void main(String[] args){
    try {
      Scanner sc = new Scanner(System.in);
      int n, m;
      n=Integer.parseInt(sc.next());
      m=Integer.parseInt(sc.next());
      int[] x = new int[m];
      for(int i=0; i<m; i++){
        x[i]=Integer.parseInt(sc.next());
      }

      Arrays.sort(x);
      int[] d = new int[m-1];
      for(int i=0; i<m-1; i++){
        d[i]=x[i+1]-x[i];
      }
      Arrays.sort(d);
      int ans=0;
      for(int i=0; i<m-n; i++){
        ans=ans+d[i];
      }
      System.out.println(ans);
                
      }catch (Exception e) {
      System.out.println("out");
    }
  }
}


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

int main() {
  string s;
  cin >> s;
  cout << s.substr(0,4) << " " << s.substr(4,8) << endl;
}

Measured memory_bytes: 256
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
  
def conv(w, h):
  ans = 1
  mod = 10**9+7
  ma = min(w, h)
  for i in range(ma):
    ans*=((w+h-i)%mod)
    ans%=mod
    m_inv = pow(m-i,mod-2,mod)
    ans*=m_inv
    ans%=mod
  return ans

mod = 10**9+7
n = int(input())
m = n//3
a = 0
for i in range(1, m+1):
  nokori = n-3*i
  a+=comb(nokori+i-1, i-1, mod)
  a%=mod
  
print(a)

Measured memory_bytes: 73508
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    #divisors.sort()
    return divisors

N=int(input())
L=make_divisors(N)
#print(L)
if len(L)%2==1:
    print((L[len(L)-1])*2-2)
else:
    print(L[len(L)-1]+L[len(L)-2]-2)


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

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define FOR(i, n) for (int i = 0; i < int(n); i++)
#define FOR1(i, m, n) for (int i = int(m); i < int(n); i++)
#define MAX(a, b) ((a) >= (b) ? (a) : (b))
#define MIN(a, b) ((a) <= (b) ? (a) : (b))

int main(int argc, char *argv[]) {
  int N;
  vector<int> hist(1e5);

  scanf("%d", &N);

  FOR(i, N) {
    int a;
    scanf("%d", &a);
    FOR1(j, MAX(0, a - 1), MIN(a + 2, 1e5-1)) hist[j]++;
  }

  auto it = max_element(hist.begin(), hist.end());
  printf("%d\n", *it);

  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int A,B,C;
    cin >>A>>B>>C;
    int D=A%B;
    int E=D;
    for(int i=0;i<1000;i++){
        E+=D;
        E%=B;
        if(E==C){
            cout<<"YES"<<endl;
            return 0;
        }
    }
    cout <<"NO"<<endl;
}

Measured memory_bytes: 3592
import java.util.*;
public class Main{
    String[] AND = {"(0*0)","(0*1)","(0*2)",
                    "(1*0)","(1*1)","(1*2)",
                    "(2*0)","(2*1)","(2*2)"};
    String[] AND_RESULT = {"0","0","0",
                           "0","1","1",
                           "0","1","2"};
    String[] OR = {"(0+0)","(0+1)","(0+2)",
                   "(1+0)","(1+1)","(1+2)",
                   "(2+0)","(2+1)","(2+2)"};
    String[] OR_RESULT = {"0","1","2",
                          "1","1","2",
                          "2","2","2"};
    String[] INV = {"-0","-1","-2"};
    String[] INV_RESULT = {"2","1","0"};
    
    void run(){
        Scanner sc = new Scanner(System.in);
        while(true){
            String exp = sc.next().replace("--", "");
            if(exp.equals(".")){
                break;
            }
            int count = 0;
            for(int p = 0; p <= 2; p++){
                for(int q = 0; q <= 2; q++){
                    for(int r = 0; r <= 2; r++){
                        String tmp = exp.replace("P", p + "");
                        tmp = tmp.replace("Q", q + "");
                        tmp = tmp.replace("R", r + "");
                        if(calc(tmp).equals("2")){
                            count++;
                        }
                    }
                }                
            }
            System.out.println(count);
        }

    }
    String calc(String exp){
        //System.out.println("init: " + exp);
        while(exp.length() != 1){
            for(int i = 0; i < INV.length; i++){
                exp = exp.replace(INV[i], INV_RESULT[i]);
            }
            for(int i = 0; i < AND.length; i++){
                exp = exp.replace(AND[i], AND_RESULT[i]);
            }
            for(int i = 0; i < OR.length; i++){
                exp = exp.replace(OR[i], OR_RESULT[i]);
            }
        }
        //System.out.println("return: " + exp);
        return exp;
    }
    public static void main(String[] args){
        new Main().run();
    }
}

Measured memory_bytes: 119968
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define COUT(x) cout<<(x)<<endl
#define dump(x)  cout << #x << " = " << (x) << endl;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
using M = map<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int, vector<int>, greater<int>>;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main() {
  int n; cin >> n;
  string s;
  set<string> sset;
  REP(i,n) {
    cin >> s;
    sset.insert(s);
  }
  COUT(sset.size());

  return 0;
}


Measured memory_bytes: 19252
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>

typedef long long ll;
using namespace std;

#define FALSE printf("false\n");
#define TRUE printf("true\n");
#define all(x) (x).begin(),(x).end()
#define print(x) cout<<(x)<<endl
#define rep(i,n) for(int i = 0;i < ((int)(n));++i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SUM(vec) accumulate(all(vec),0LL)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define test(a) cout<<"line:"<<__LINE__<<"["<<(#a)<<": "<<(a)<<"]"<<endl

const int INF = 1e9+7;
const ll INFL = 9*1e18;

ll inline digit(ll num){int tmp = 0;while(num){tmp++;num/=10;}return tmp;}
template<typename T>inline T digitSum(T num){T sum = 0;while(num){sum+=num%10;num/=10;}return sum;} // 各桁の和
template<typename T>inline T gcd(T a,T b){if(b == 0)return a;return gcd(b,a%b);}
template<typename T>inline T lcm(T a, T b){T g = gcd(a,b);return a/g*b;}
template<typename T>inline T power(T a,T b){T tmp=1;rep(i,b){tmp*=a;}return tmp;}


bool isOk(ll key,ll value){
  return key >= value;
}

ll binary_search(vector<ll> a,ll key){
  ll ok = a.size()-1;
  ll ng = 0;

  while(abs(ok - ng) > 1){
    ll mid = (ok + ng) / 2;
    if(isOk(key,a[mid]))ok = mid;
    else ng = mid;
  }
  return ok;
}

bool isPrime(ll n) {
	for (int i = 2; n >= i * i; ++i) {
		if(!(n % i))return false;
	}
  return true;
}
vector<ll> primes(ll n){
  vector<ll> v(1,1);
  for (ll i = 2; n >= i * i; ++i) {
		if(!(n % i)){
      v.pb(i);
	  }
  }
  if(v.size()==1)v.pb(n);
  return v;
}

int main() {
  cin.tie(0); ios::sync_with_stdio(0);
  int n;cin>>n;
  int k;cin>>k;
  vector<ll> a(n);rep(i,n)cin>>a[i];
  ll ans = INFL;
  rep(i,n-k+1){
    ans = min(abs(a[i+k-1])+abs(a[i+k-1]-a[i]),ans);
    ans = min(abs(a[i])+abs(a[i]-a[i+k-1]),ans);
  }
  print(ans);
  return 0;
} 

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




int main()
{
int n, d;
cin >> n >> d;
vector<vector<int>> x(n, vector<int>(d));
for(int i = 0; i < n;i++)
{
	for(int j = 0; j < d; j++)
	{
		cin >> x[i][j];
	}
}
int ans = 0;
for(int i = 0; i < n;i++)
{
	for(int j = i +1; j < n; j++)
	{
		int norm = 0;
		for(int k = 0; k < d; k++)
		{
			int diff = abs(x[i][k] - x[j][k]);
			norm += diff * diff;
		}

		bool flag = false;
		for(int k = 0; k <= norm;k++)
		{
			if(k * k == norm)
			{
				flag = true;
			}
		}
		if(flag)ans++;
	}
}
cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include <cassert>
#include <cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()

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

vector<int>bitSearch(int bit,int n){
    vector<int>S;
    rep(i,n)if(bit&(1<<i))S.push_back(i);
    return S;
}


int d[3] = {-1,0,1};
int main(){
   string s;cin>>s;
   int n = s.size();
   bool f = true;
   rep(i,n){
       if(i%2==1){
           if(s[i]=='R')f = false;
       }
       else {
           if(s[i]=='L')f = false;
       }
   }
   cout<<(f?"Yes":"No");
}



Measured memory_bytes: 256
#include <iostream>
#include <cmath>
using namespace std;
int main(){
  int n,d;
  cin >> n >> d;
  int count=0;
  int x[n],y[n];
  for(int i = 0; i < n; i++){
    cin >> x[i] >> y[i];
    if(pow(x[i],2)+pow(y[i],2)<=pow(d,2))count++;
  }
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 4984
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;

int main() {
  int N;
  cin >> N;
  vector <ll> A(N);
  for (int i=0; i<N; i++) {
    cin >> A[i];
  }
  if (N%2==1) {
    A.push_back(0);
  }
  sort(A.begin(),A.end());
  for (int i=0; i<N; i+=2) {
    if (A[i]!=A[i+1]) {
      cout << 0 << endl;
      return 0;
    }
  }
  int ans=1;
  for(int i=0; i<N/2; i++) {
    ans*=2;
    ans%=mod;
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 1536
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <iomanip>

typedef long long ll;

using namespace std;

int main(void)
{
    string str;
    cin >> str;

    vector<char> data(str.size());

    for (int i = 0; i < str.size(); i++) {
        data[i] = 'x';
    }

    for (int i = 0; i < str.size(); i++) {
        cout << data[i];
    }

    cout << endl;

    return 0;
}

Measured memory_bytes: 256
a,b = map(int, input().split())
if a == 0 and b == 0:
    print(0)
elif a == 0:
    print(b*(b-1)//2)
elif b == 0:
    print(a*(a-1)//2)
else:
    print(a*(a-1)//2+b*(b-1)//2)

Measured memory_bytes: 3060
//
// Created by 肖龙 on 2020/3/18.
//

//
// Created by 肖龙 on 2020/2/20.
//


/*
 * 求点和直线的投影
 */
#include<iostream>
#include <cmath>
#include <iomanip>

using namespace std;

typedef struct point{
    double x,y;
}Point,Vector;

typedef struct line{
    Point x;
    Vector k;
}Line;

double dot(Vector x,Vector y){
    return x.x*y.x+x.y*y.y;
}

Vector getV(Point x,Point y){
    Vector v;
    v.x=y.x-x.x;
    v.y=y.y-x.y;
    return v;
}
//点在直线的投影
Point Projection(Line x,Point y){
    Point answ;
    answ = x.x;

    double len = dot(x.k,getV(x.x,y));
    len/=sqrt(x.k.x*x.k.x+x.k.y*x.k.y);
    Vector temp  = x.k;
    temp.x /=sqrt(x.k.x*x.k.x+x.k.y*x.k.y);
    temp.y/=sqrt(x.k.x*x.k.x+x.k.y*x.k.y);
    answ.x+=temp.x*len;
    answ.y+=temp.y*len;
    return answ;
}
//点与直线的对称点
Point Reflection(Line x,Point y){
    Point half = Projection(x,y);
    Point answ;
    answ.x=y.x+2*(half.x-y.x);
    answ.y=y.y+2*(half.y-y.y);
    return answ;
}

int main(){
    Point p1,p2,p;
    cin>>p1.x>>p1.y>>p2.x>>p2.y;
    int q;
    cin>>q;
    Vector v2;
    v2 = getV(p1,p2);
    Line l;
    l.k=v2;
    l.x=p1;
    for(int i=1;i<=q;i++){
        cin>>p.x>>p.y;
        Point answ = Projection(l,p);
        cout<<setprecision(10)<<setiosflags(ios::fixed)<<answ.x<<" "<<answ.y<<endl;
    }
    return 0;
}


Measured memory_bytes: 3264
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <random>
#include <chrono>
#include <queue>
#include <math.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 10e+6
#define DEKA 1000000007

using namespace std;

int main(){
    int n,x;
    cin >> n >> x;
    int ans=1;
    int real=0;
    for(int i=0;i<n;i++){
        int t;
        cin >> t;
        real+=t;
        if(real<=x) ans++;
    }
    cout << ans << endl;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
char s[500010];
ll ans;
ll nxt[500010], arr[500010];
int main() {
	s[0] = '*';
	scanf("%s", s + 1);
	int len = strlen(s) - 1;
	for(int i = len; i>= 1; i --){
		if(s[i] == '>'){
			nxt[i] = max((ll)(1), nxt[i + 1] + 1);
		}
	}
	for(int i = 1; i <= len; i ++){
		if(s[i] == '>'){
			if(s[i - 1] == '>') arr[i] = min(nxt[i], arr[i - 1] - 1);
			else arr[i] = max(arr[i], nxt[i]);
		}
		else if(s[i] == '<'){
			arr[i + 1] = arr[i] + 1;
		}
	}
	for(int i = 1; i <= len + 1; i ++){
		ans += arr[i];
	}
	printf("%lld", ans);
	return 0;
}

Measured memory_bytes: 8576
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

namespace {

	int cnt;
	void InsertionSort(vector<int>& A, int g)
	{
		for (int i = g; i < A.size(); ++i)
		{
			int v = A[i];
			int j = i - g;

			while (j >= 0 && A[j] > v) {
				A[j + g] = A[j];
				j -= g;
				cnt++;
			}

			A[j + g] = v;
		}
	}

	void ShellSort(vector<int>& A)
	{
		int m;
		cnt = 0;
		vector<int> G;
		G.push_back(1);
		for (int i = 1; i <= A.size(); ++i)
		{
			int g = pow(4, i) + 3 * pow(2, i - 1) + 1;
			if (g <= A.size()) G.push_back(g);
			else { m = i; break; }
		}

		for (int i = m - 1; i >= 0; --i)
			InsertionSort(A, G[i]);

		cout << m << endl;
		for (int i = m - 1; i >= 0; --i) {
			cout << G[i];
			i != 0 ? cout << " " : cout << endl;
		}
		cout << cnt << endl;
		for (int i = 0; i < A.size(); ++i)
			cout << A[i] << endl;
	}
}

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

	int n;
	cin >> n;

	vector<int> A(n);
	for (int i = 0; i < n; ++i)
		cin >> A[i];

	ShellSort(A);

	return 0;
}

Measured memory_bytes: 5160
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define ll long long



using namespace std;

void file(){
	#ifndef ONLINE_JUDGE
    	freopen("in.txt", "r", stdin);
	#endif
}
int tc;
const int N=5e5+5,M=2e6+5,MOD=1e9+7,OO=1e9;

const int MSQ = sqrt(N) + 5;


int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//	file();

	int n;

	scanf("%d",&n);
	
	std::vector<pair<int,int>> a(n);

	for(int i=0;i<n;i++)scanf("%d",&a[i].first),a[i].second=i;

	sort(all(a));

	for(auto p : a)printf("%d ",p.second+1 );
	printf("\n");

}		



Measured memory_bytes: 1664
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <set>
#include <utility>
#include <cstdlib>
#include <queue>
#include <iomanip>
#include <cstdio>

using namespace std;


int H,W;
int N;
int a[10001];
int ans[10001][10001];

int main(){
    //入力
    cin >> H >> W;
    cin >> N;
    for(int i=0;i<N;i++) cin >> a[i];

    //うねうねと蛇のようにしたに下って色を更新していく。
    //今回は配列に色を入れて後から出力した。
    int i=0,j=0;
    bool flag = true;
    for(int color=1;color<=N;color++){

        while(a[color-1]){
            ans[i][j] = color;
            if(flag) j++;
            else j--;

            if(j >= W){
                flag = false;
                j = W-1;
                i++;
            }
            else if(j < 0){
                flag = true;
                j = 0;
                i++;
            }

            a[color-1]--;
        }
    }

    //出力
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}
   


Measured memory_bytes: 2560
N,K=map(int,input().split())
H=[int(input()) for _ in range(N)]
H.sort()
tmp=H[K-1]-H[0]
for i in range(0,N-K+1):
    if tmp>H[K+i-1]-H[i]:
        tmp=H[K+i-1]-H[i]
print(tmp)

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

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

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#define all(e) (e).begin(), (e).end()
#define pb push_back


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


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

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

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

const int N = 11;
const int Q = 51;
int a[Q], b[Q], c[Q], d[Q];
int arr[N];
int ans = 0;
int n, m, q;

void solve(int cur, int nxt) {
    if (cur == n) {
        int ret = 0;
        for (int i = 0; i < q; ++i) {
            if (arr[b[i]] - arr[a[i]] == c[i]) ret += d[i];
        }
        ans = max(ret, ans);
        return;
    }

    for (int i = nxt; i <= m; ++i) {
        arr[cur] = i;
        solve(cur+1,i);
    }
}

int main(int argc, char **argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    memset(arr,-1,sizeof(arr));
    for (int i = 0; i < q; ++i) {
        int aa, bb, cc, dd; cin >> aa >> bb >> cc >> dd;
        aa--,bb--;
        a[i] = aa, b[i] = bb, c[i] = cc, d[i] = dd;
    }
    solve(0,1);
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3652
#include <iostream>

using namespace std;

int main(void)
{
  int a,b,tmp;
  int num;
  int digit=0;
  
  cin>>a>>b;

  tmp=b;
  while(tmp){
    digit++;
    tmp/=10;
  }

  for(int i=0;i<digit;i++)
    a*=10;
  num=a+b;

  for(int i=1;i<=317;i++){
    if(i*i==num){
      cout<<"Yes"<<endl;
      return 0;
    }
  }
  
  cout<<"No"<<endl;
  
  return 0;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1000000007;

int main()
{
   string s,t;
   cin >> s >> t;
   map<char,char> mp,mq;
   rep(i,s.size())
   {
      if(mp[s[i]]==0)
      {
         mp[s[i]] = t[i];
      }
      if(mq[t[i]]==0)
      {
         mq[t[i]] = s[i];
      }
      if(mp[s[i]]!=t[i])
      {
         cout<<"No"<<endl;
         return 0;
      }
      if(mq[t[i]]!=s[i])
      {
         cout<<"No"<<endl;
         return 0;
      }
   }
   
   cout<<"Yes"<<endl;
   return 0;
}

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

int main() {
  int num;
  string str;
  int score;
  vector<tuple<string, int, int>> tpl;
  
  cin >> num;
  
  for(int i = 0; i < num; i++){
    cin >> str >> score;
    tpl.emplace_back(str, -score, i+1);
  }
  
  sort(begin(tpl), end(tpl));
  
  for(auto itr : tpl){
    cout << get<2>(itr) << endl;
  }
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
    	Scanner sc = new Scanner(System.in);
		// 整数の入力
		int N = sc.nextInt();
		int[] array = new int[N];
		
		for(int i=0;i<N;i++){
		    array[i] = sc.nextInt();
		}
		
		Arrays.sort(array);
		
		System.out.println(array[N-1]-array[0]);
	    
    }
}


Measured memory_bytes: 23764
#include <cstdio>
using namespace std;
int main(){
	int a, b;
	char op;
	for(;;){
		scanf("%d %c %d", &a, &op, &b);
		
		if(op == '+') printf("%d\n", a + b);
		else if(op == '-') printf("%d\n", a - b);
		else if(op == '*') printf("%d\n", a * b);
		else if(op == '/') printf("%d\n", a / b);
		else break;
	}
	return 0;
}

Measured memory_bytes: 1028
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

int main() {
	double a, b, c, d, e, f;
	vector<double> x, y;
	while (cin >> a) {
		double tmpY;
		cin >> b >> c >> d >> e >> f;
		if (a*e != b*d) {
			y.push_back((c*d - a*f) / (b*d - a*e));
			tmpY = (c*d - a*f) / (b*d - a*e);
		} else {
			continue;
		}
		if (a != 0) {
			x.push_back((c - b*tmpY) / a);
		} else if (d != 0) {
			x.push_back((f - e*tmpY) / d);
		} else {
			continue;
		}
	}

	for (int i = 0; i < x.size(); i++) {
		cout << fixed << setprecision(3) << x[i] << " " << y[i] << endl;
	}
}

Measured memory_bytes: 1308
import java.util.Scanner;

public class Main {

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

		while (true) {
			H = sc.nextInt();
			W = sc.nextInt();

			if (H == 0 && W == 0)
				break;

			printRectangle(H, W);

		}

	}

	public static void printRectangle(int H, int W) {
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				System.out.print("#");

				if (j == (W - 1))
					System.out.println("");
			}
		}
		System.out.println();
	}

}

Measured memory_bytes: 32696
#include<cstdio>
#include<cstdlib>
using namespace std;
int flag[105],a[105];
int Max = 0;
int main(){
	int n,f = 0;
	while(~scanf("%d",&n)){
		if(n>1){
		for(int i = 1;i<=n;i++)
			a[i] = i;
		for(int i = 1;i<=n;i++){
			while(a[i]%2==0){
				a[i] =a[i]/2;
				flag[i]++;
			}
		}
		for(int i = 1;i<=n;i++){
			if(flag[i]>Max){
				Max = flag[i];
				f = i;
			}
		}
		printf("%d\n",f);
		}
		else{
			printf("1\n");
			}
	}
}

Measured memory_bytes: 128
#include <iostream>

using namespace std;

int gcd (int p, int q) {
  if (q == 0) {
    return p;
  }
  return gcd(q, p % q);
}

int lcm (int p, int q) {
  p /= gcd(p, q);
  return p * q;
}

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

  cout << lcm(x, 360) / x << endl;
}


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

int main() {
  int a, b, c, k; cin >> a >> b >> c >> k;
  int x = max({a, b, c});
  int y=0,z=0;
  if(x==a) y=b, z=c;
  else if(x==b) y=a, z=c;
  else y=a, z=b;
  
  for(int i=0; i<k; i++){
    x = x*2;
  }
  
  cout << x+y+z << endl;
  
  return 0;
}

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

int main()
{
 int N;
  cin >> N;
  int a,b,c;
  
  a = N % 10;
  b  = N /10 %10;
  c = N /100 % 10;
  
  if (a == 7 || b == 7 || c == 7)
    cout << "Yes" << endl;
  else 
    cout << "No" << endl;
}

Measured memory_bytes: 3596
#include <stdio.h>
typedef long long ll;
ll mod=1000000007;
 
ll powmod(ll x,ll y){
  ll res=1;
  for(ll i=0;i<y;i++){
    res=res*x%mod;
  }
  return res;
 
}
 
 
int main(void){
  ll n;
  scanf("%lld",&n);
  ll ans=powmod(10,n)-powmod(9,n)-powmod(9,n)+powmod(8,n);
  ans%=mod;
  ans=(ans+mod)%mod;
  printf("%lld\n",ans);
  return 0;
}

Measured memory_bytes: 1732
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int g,t,y,nt=0;
    string q;
    cin>>t>>y>>q;
    for(g=1;q[g];g++)
        if(q[g]==q[g-1])nt++;
    printf("%d\n",min(t-1,nt+2*y));
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
//#include <stdio.h>
//#include <stack>
//#include <queue>
#include <cstdio>
#include <cmath>
#include <iterator>
#include <map>
//#include <fstream>
//#include <list>
//#include <iomanip>
#include <stdlib.h>
#include <cctype>

using namespace std;

#define MOD 1000000007
#define Int int64_t
#define PI 3.14159265358979
#define ssort(z) sort(z.begin(),z.end())
#define rsort(z) sort(z.rbegin(),z.rend())
#define eerase(z) z.erase(unique(z.begin(),z.end()),z.end())
#define ccnt(z,w) count(z.begin(),z.end(),w)


void printVec(std::vector<int> & vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}
void printVec1(std::vector<string>& vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}
void printVec2(std::vector<Int>& vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

Int gcd(Int a, Int b) {
	return b != 0 ? gcd(b, a % b) : a;
}
Int lcm(Int a, Int b) {
	return a * b / gcd(a, b);
}

bool comp(const string a, const string b) {
	return a.length() < b.length();
}

bool integer(double num) {
	return floor(num) == num;
}

string gen(int num) {
	string str = "";
	for (int i = 0; i < num; i++) str += ".";
	return str;
}
Int fact(int num) {
	if (num == 0) return 1;
	else return num * fact(num - 1);
}

int main() {
	string str; cin >> str;
	int pos = str.size()-1;
	string c;
	for (int i = 0; i < str.size()/5+1; i++) {
		bool notyet = 1;
		if (pos-7+1 >=0&&notyet) {
			c = str.substr(pos-7+1, 7);
			if (c == "dreamer") {
				pos -= 7;
				notyet = 0;
			}
		}
		if (pos - 6+1 >= 0 && notyet) {
			c = str.substr(pos-6+1, 6);
			if (c == "eraser") {
				pos -= 6;
				notyet = 0;
			}
		}
		if (pos - 5+1 >= 0 && notyet) {
			c = str.substr(pos-5+1, 5);
			if (c == "dream" || c == "erase") {
				pos -= 5;
				notyet = 0;
			}
		}
		//cout << c <<pos<< endl;
	}
	if (pos == -1) cout << "YES";
	else cout << "NO";


	cout << endl;
	return 0;
}

Measured memory_bytes: 512
//To debug :  g++ -g file.cpp -o code
//to flush output : fflush(stdout) or cout.flush()
//cout<<setprecision(p)<<fixed<<var
//use 1LL<<i to for 64 bit shifting , (ll)2 because by default 2 is ll
//take care of precedence rule of operators 
//do not forget to change the sizes of arrays and value of contants and other things after debugging  
 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,n) for(i=a;i<n;++i)
#define irep(i,n,a) for(i=n;i>a;--i)
#define mod 1000000007
#define pb push_back
#define big 9223372036854775807
#define big1 LONG_MAX
#define big2 ll_MAX
#define big3 1000000000
#define sma1 LONG_MIN
#define sma2 ll_MIN
#define sma3 -1000000000
#define mp make_pair
#define dub double
#define ivec vector<ll>
#define lvec vector<long long>
#define cvec vector<char>
#define svec vector<string>
#define mt make_tuple
#define MOD 998244353
#define ld long double
#define pi acos(-1.0)
 
#define SZ(x)  (ll)(x.size())
 
//comment the below if not required
 
/*
 
#define ss second.second
#define ff first.first
#define f first
#define s second
#define sf second.first
#define fs first.second
*/
 
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

int main()
{

    string s;

    cin>>s;

    if(s[0]=='R' && s[1]=='R' && s[2]==s[1])
            cout<<3;
    else if((s[0]=='R' && s[0]==s[1]) || (s[1]=='R' && s[1]==s[2]))
            cout<<2;
    else if(s[0]=='R' || s[1]=='R' || s[2]=='R')
            cout<<1;
    else
            cout<<0;




    return 0;
}

Measured memory_bytes: 3624
#include "bits/stdc++.h"
#include "vector"
#include "algorithm"

int main()
{
  int a, b, c;
  std::cin >> a >> b >> c;

  std::vector<int> v;
  v.push_back(a);
  v.push_back(b);
  v.push_back(c);

  std::sort(v.begin(), v.end());
  for (auto i = v.begin(); i != v.end(); i++)
  {
    std::cout << *i;
    if (i != v.end() - 1)
    {
      std::cout << " ";
    }
  }

  std::cout << std::endl;

  return 0;
}



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

using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int k;
  cin >> k;
  int even = k / 2;
  int odd = (k + 1) / 2;
  cout << even * odd << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include <algorithm>
#include <queue>
#include <climits>
#include<cmath>
#include <sstream>
#include <iomanip>

bool sort_pair( std::pair< int64_t, int64_t > origin, std::pair< int64_t, int64_t > another )
{
    return origin.first < another.first;
}

int64_t
gcd( int64_t x,  int64_t y )
{
     int64_t min = ( x < y ) ? x : y;
     int64_t max = ( x < y ) ? y : x;
    
    while( 1 )
    {
         int64_t mod = max % min;
        
        if( mod == 0 )
        {
            return min;
        }

        max = min;
        min = mod;
    }
    
    return 1;
}

std::vector< int64_t > soinsuu( int64_t n )
{
    std::vector< int64_t > sosuu;

    if( n == 1 )
    {
        return sosuu;
    }
    
    int64_t a = 2;
    //int64_t b = 1;
    bool first = true;

    while( a * a <= n )
    {
        if( n % a == 0 )
        {
            n = n / a;
            if( first )
            {
                sosuu.push_back( a );
            }

            first = false;
        }
        else
        {
            if( a == 2 )
            {
                a += 1;
            }
            else
            {
                a += 2;
            }
            
            first = true;
        }
    }

    if( n != 1
        && n != a )
    {
        sosuu.push_back( n );
    }
    
    return sosuu;
}

int main()
{

    int64_t a,b;
    //int64_t c = 1;
    
    std::cin>> a;
    std::cin>> b;


    std::vector< int64_t > ac = soinsuu( a );
    std::vector< int64_t > bc = soinsuu( b );

    //int64_t min = std::min( ac.size(), bc.size() );
    //int64_t max = std::min( ac.size(), bc.size() );

    std::vector< int64_t > list;

    std::set_intersection( ac.begin(), ac.end(), bc.begin(), bc.end(), std::back_inserter( list ) );

    std::cout<< list.size() + 1;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
using P = pair<int, int>;
P f(string& s){
    int l = 0, mn = 0;
    for(char c: s){
        if(c == '(') l++;
        else l--;
        if(l < mn) mn = l;
    }
    return P(mn, l);
}
void g(string& s){
    reverse(s.begin(), s.end());
    for(char& c: s){
        if(c == '(') c = ')';
        else c = '(';
    }
}
int main(void){
    int n, L = 0, R = 0;
    vector<P> up, dw, lst;
    cin >> n;
    for(int i=0;i<n;i++){
        string s;
        cin >> s;
        P p = f(s);
        int mn = p.first;
        int l = p.second;
        if(l >= 0){
            if(mn == 0){
                L += l;
            }else{
                up.push_back(P(mn, l));
            }
        }else{
            g(s);
            p = f(s);
            mn = p.first;
            l = p.second;
            if(mn == 0){
                R += l;
            }else{
                dw.push_back(P(mn, l));
            }
            // cout << "R: ";
        }
        // cout << mn << " " << l << endl;

    }
    sort(up.begin(), up.end(), greater<P>());
    for(P p: up){
        int mn = p.first;
        int l = p.second;
        if(L+mn < 0){
            puts("No");
            return 0;
        }
        L += l;
    }
    sort(dw.begin(), dw.end(), greater<P>());
    for(P p: dw){
        int mn = p.first;
        int l = p.second;
        if(R+mn < 0){
            puts("No");
            return 0;
        }
        R += l;
    }
    // cout << L << " " << R << endl;
    if(L == R) puts("Yes");
    else puts("No");

}


Measured memory_bytes: 4848
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
import numpy as np
n,k=mi()
h=np.array(li())
dp = np.array([0]*n)
for i in range(1,n):
    st = max(0,i-k)
    dp[i] = min(dp[st:i]+abs(h[i] - h[st:i]))
print(dp[n-1])


Measured memory_bytes: 23064
#include <bits/stdc++.h>
using namespace std;
#define rep(i,ini,n) for(int i=ini;i<n;i++)
#define _rep(i,ini,n) for(int i=ini;i>=n;i--)
#define ToEnd(a) a.begin(),a.end()
uint64_t MOD=1000000007;

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

    string ans="Yes";
    if(s.size()+1!=t.size()){
        ans="No";
    }else{
        rep(i,0,s.size()){
            if(s.at(i)!=t.at(i)) ans="No";
        }
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 3600
def binsearch(good, bad, fn):
    while abs(good - bad) > 1:
        m = (good + bad) // 2
        if fn(m):
            good = m
        else:
            bad = m
    return good

def main():
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    def fn(t):
        k = 0
        for a in A:
            k += (a - 1) // t
        return k <= K

    return binsearch(10** 9, 0, fn)

print(main())


Measured memory_bytes: 30932
/**
 *    author:  math2do
 *    created: 27.04.2020 22:19:05 IST
**/

#include <bits/stdc++.h>

using namespace std;

const int mod = 2019;

inline int mul(int a, int b) {
  long long res = (long long) a * b;
  a = (int) (res % mod);
  if (a < 0) {
    a += mod;
  }
  return a;
}

inline int power(int a, int b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) {
      res = mul(res, a);
    }
    b >>= 1;
    a = mul(a, a);
  }
  return res;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  int n = s.length();
  auto digit = [&] (char ch) {
    return (int) (ch - '0');
  };
  int ans = 0;
  vector <int> cnt(mod, 0);
  cnt[0]++;
  int rem = 0;
  int exp = 0;
  for (int i = n - 1; ~i; i--) {  
    int d = digit(s[i]);
    rem = (d * power(10, exp) + rem) % mod;
    ans += cnt[rem];
    cnt[rem]++;
    exp++;
  } 
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3808
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

N,M,K=i_map()
A=i_list()
B=i_list()
cum_A = [0]*(N+1)
cum_B = [0]*(M+1)
for i in range(1, N+1):
    cum_A[i] = cum_A[i-1] + A[i-1]
for i in range(1, M+1):
    cum_B[i] = cum_B[i-1] + B[i-1]
ans = 0
for i in range(0, N+1):
    val = K - cum_A[i]
    if val < 0:
        continue
    idx = bisect_right(cum_B, val) - 1
    ans = max(ans, i + idx)
print(ans)

Measured memory_bytes: 123228
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
ll GCD(ll a, ll b){ return a ? GCD(b % a, a) : b; }
int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0; i<n-1; i++){int b; cin>>b; a[i]=b-1;}
    map<int,int> amap;
    for(int i=0; i<n-1; i++) amap[a[i]]++;
    for(int i=0; i<n; i++){
        cout<<amap[i]<<endl;
    }
}

Measured memory_bytes: 13524
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
    private static List<Integer> p = IntStream.rangeClosed(1, 126).mapToObj(i -> i * i).collect(Collectors.toList());
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int d = sc.nextInt();
        int[][] x = new int[n][d];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < d; j++) {
                x[i][j] = sc.nextInt();
            }
        }
        int c = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int s = 0;
                for (int k = 0; k < d; k++) {
                    s += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
                }
                if (p.contains(s)) {
                    c++;
                }
            }
        }
        System.out.println(c);
    }
}


Measured memory_bytes: 27220
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
#define mod 1000000007
#define MOD 1000000037
#define mod1 998244353
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 
#define INF 2e9

int main()
{
    fastio;
    int k;
    cin >> k;
    int a,b;
    cin >> a >> b;
    int f=0;
    for(int i=a;i<=b;i++)
    {
        if(i%k==0)
        {
            f=1;
            break;
        }
    }
    if(f==1)
        cout << "OK" << endl;
    else
        cout << "NG" << endl;
}

Measured memory_bytes: 3652
S = str(input())
T = str(input())

s = set(S)
# print(s)
# print(S)
t = set(T)
list_s = list(s)
list_t = list(t)

list_S = []
list_T = []

for i in range(len(list_s)):
  count = S.count(str(list_s[i]))
  list_S.append(int(count))


for j in range(len(list_t)):
  count = T.count(str(list_t[j]))
  list_T.append(int(count))

list_S.sort()
list_T.sort()

# print(list_S)
# print(list_T)

if (list_S == list_T):
  print("Yes")
else:
  print("No")




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

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define deb(x)	cout << #x << " " << x << endl;

typedef long long int ll;

int main() {

	IOS

	int t;
	cin >> t;
	cout << (t+1)%2;

	return 0;
}

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

const int N = 110000;

char str[N];
int dp[N];

int main() {
	
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> str + 1;
	int len = strlen(str + 1);
	dp[0] = 1;
	for (int i = 1; i <= len; i++) {
		if (i >= 5 && !strncmp(str + i - 4, "dream", 5)) dp[i] |= dp[i - 5];
		if (i >= 5 && !strncmp(str + i - 4, "erase", 5)) dp[i] |= dp[i - 5];
		if (i >= 6 && !strncmp(str + i - 5, "eraser", 6)) dp[i] |= dp[i - 6];
		if (i >= 7 && !strncmp(str + i - 6, "dreamer", 7)) dp[i] |= dp[i - 7];
	}
	if (dp[len]) cout << "YES\n";
	else cout << "NO\n";
	
	return 0;
}


Measured memory_bytes: 4140
#include <bits/stdc++.h>
#include <numeric>
long long int GCD(long long int a,long long int b){long long int c;while(b!=0){c=a%b;a=b;b=c;}return a;}
using namespace std;

int main() {
  int n;
  cin >> n;
  long long int a[n+1];
  for(int i=0;i!=n;i++){
    cin >> a[i];
  }
  long long int x;
  x=a[0];
  for(int i=1;i!=n;i++){
    x=GCD(x,a[i]);
  }
  cout << x << endl;
}


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

ll D;
string N;
ll dp[101010][101][2];
ll mod = 1e9 + 7;

ll solve(int i, int md, bool b) {
    if (i >= N.size()) {
        return md == 0;
    }
    ll& ret = dp[i][md][b];

    if (~ret) return ret;
    ret = 0;

    int x = N[i] - '0';
    for (int d=0; d<=(b ? 9 : x); ++d) {
        ret += solve(i+1, (md + (d % D)) % D, (b or d < x));
        ret %= mod;
    }

    return ret;
}

int main() {
    cin >> N >> D;
    rep(i, 101010) rep(j, 101) rep(k, 2) dp[i][j][k] = -1;
    // dp[0][0][0] = 1;
    // rep(i, N.size()) rep(j, 101) rep(k, 2) {
    //     int x = N[i] - '0';
    //     for (int d=0; d<=(k ? 9 : x); ++d) {
    //         dp[i+1][(j + (d % D))%D][k or d < x] += dp[i][j][k];
    //         dp[i+1][(j + (d % D))%D][k or d < x] %= mod;
    //     }
    // }
    cout << (solve(0, 0, false) - 1 + mod) % mod << endl;
    //cout << dp[N.size()][0][1] + dp[N.size()][0][0] - 1 << endl;
}


Measured memory_bytes: 160512
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define REP(i, d, n) for(int i=(d); i<(n); ++i)
typedef long long ll;
const int mod = 1e9 + 7;
int main() {

    int n, k, s;
    cin >> n >> k >> s;

    vector<ll> a(n);

    rep(i, n){
        if(k > 0){
            a[i] = s;
            k--;
        }
        else{
            if(s != 215464266)
                a[i] = 215464266;
            else
                a[i] = 1542667869;
        }
    }
    rep(i, n){
        cout << a[i] << endl;
    }

    return 0;
}

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

int main(){
    int n, i, sum;
    cin >> n;
    int s[n];
    for(i=0; i<n; i++){
        cin >> s[i];
        sum += s[i];
    }
    if(sum%10 != 0){
        cout << sum;
    }else{
        sort(s, s+n);
        i = 0;
        while(i < n && s[i]%10 == 0) i++;
        if(i == n){
            cout << 0;
        }else{
            cout << sum - s[i];
        }
    }
    return 0;
}

Measured memory_bytes: 256
import sys

a, b = map(int, input().split())
s = list(input())

for i, j in enumerate(s):
    if i == a:
        if j != '-':
            print('No')
            sys.exit()
    elif j.isdigit():
        continue
    else:
        print('No')
        sys.exit()
print('Yes')

    


Measured memory_bytes: 9172
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 5e5+7;
int a[N];
int h[N];
int n;
bool cmp(int x,int y) {
    return a[x] < a[y];
}
void nhap()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        h[i] = i;
    }
    sort(h + 1,h + 1 + n,cmp);
}
void solve()
{
    int Len = 1;
    for (int i = 1; i <= n; ) {
        int j = i + 1;
        while (j <= n && h[j] > h[j - 1]) {j++;}
        Len = max(j - i,Len);
        i = j;
    }
    cout << n - Len;
}
int main()
{
    nhap();
    solve();
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
queue<int> q;
int main()
{
	int constant=1;
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++)
	{
		int n;
		scanf("%d",&n);
		q.push(n);
	}
	int loses=0;
	for(int i=0;i<a;i++)
	{
		if(q.front()!=constant)
		{
			loses++;
		}
		if(q.front()==constant)
		{
			constant++;
		}
		q.pop();
	}
	if(loses==a)
		printf("-1");
	else
		printf("%d",loses);
}

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

typedef long long int ll;
#define INF 1999999999
#define MODA 1000000007

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    string  s, t, u;
    int a, b, red, blue;
    cin >> s >> t;
    cin >> a >> b;
    cin >> u;
    if(s == u)
    {
         red = a - 1;
         cout << red << " " << b << endl;
    }
    else
    {
        blue = b - 1;
        cout << a << " " << blue << endl;
    }

    return 0;
}


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

int main() {
  int a;
  cin >> a;
  double ans;
  if (a % 2 == 1)
    ans = (a / 2 + 1) / (double)a;
  else
    ans = 0.5;
  cout << setprecision(10) << ans << endl;
  return 0;
}


Measured memory_bytes: 256