akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include <algorithm> 
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
#define ll long long
#define rep(i,n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repR(i,n) for(ll i=n;i>=0;i--)
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define F first
#define S second
#define pb push_back
#define pu push
#define COUT(x) cout<<(x)<<"\n"
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,vector<ll>,greater<ll>>
#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define mp make_pair
#define sz(x) (ll)(x).size()
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MOD = 1000000007LL;
const ll INF = 1LL << 60;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vstr = vector<string>;
using vc = vector<char>;
using vvc = vector<vc>;
template<class T> inline bool chmax(T& a, T b) { 
 if (a < b) { a = b; return true; } return false; 
}
template<class T> inline bool chmin(T& a, T b) {
 if (a > b) { a = b; return true; } return false; 
}
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
ll dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};
int main(){
  ll h,w;
  cin>>h>>w;
  vvll a(h,vll(w));
  vvll b(h,vll(w));
  rep(i,h)rep(j,w) cin>>a[i][j];
  rep(i,h)rep(j,w) cin>>b[i][j];
  vector<vvb> dp(h,vvb(w,vb(160*80,false)));
  dp[0][0][abs(a[0][0]-b[0][0])]=true;
  rep(i,h)rep(j,w)rep(z,160*80){
    if(dp[i][j][z]){
      if(i+1<h){
      dp[i+1][j][z+abs(a[i+1][j]-b[i+1][j])]=true;
      dp[i+1][j][abs(z-abs(a[i+1][j]-b[i+1][j]))]=true;
      }
      if(j+1<w){
      dp[i][j+1][z+abs(a[i][j+1]-b[i][j+1])]=true;
      dp[i][j+1][abs(z-abs(a[i][j+1]-b[i][j+1]))]=true;
      }
    }
  }
  rep(i,160*80){
    if(dp[h-1][w-1][i]){
      COUT(i);
      return 0;
    }
  }
}

Measured memory_bytes: 13952
import sys
input = sys.stdin.readline
from operator import eq, ne

def readlines(n):
    for _ in range(n):
        x, y = input().split()
        yield int(x)-1, y

def main():
    n = int(input())
    graph = []

    for _ in range(n):
        a = int(input())
        graph.append(list(readlines(a)))

    def check(bits):
        for pre_honest, asserts in zip(bits, graph):
            if pre_honest == "0":
                continue
            for x, y in asserts:
                if bits[x] != y:
                    return -1
        
        return len([b for b in bits if b == "1"])

    for i in range(2**n-1, -1, -1):
        bit = format(i, "0{}b".format(n))
        ans = check(bit)
        if ans > -1:
            print(ans)
            return
    
    print(0)

main()


Measured memory_bytes: 3064
#include <iostream>
#include <set>
#include <cmath>

using namespace std;

int main()
{
	int x, tmp;
	set<int> s;
	const int max = 1000;

	cin >> x;

	s.insert(1);
	for (int i = 2; i <= sqrt(max); i++) {
		for (int j = 2; ; j++) {
			if ((tmp = pow(i, j)) > 1000) {
				break;
			} else {
				s.insert(tmp);
			}
		}
	}

	tmp = 1;
	for (set<int>::iterator itr = s.begin(); itr != s.end(); itr++) {
		if (*itr > x) {
			break;
		} else {
			tmp = *itr;
		}
	}

	cout << tmp << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(s,i, n) for (int i = (int)s; i < (int)(n); i++)
#define pb push_back
typedef long long ll;
  
int main(){
    int n,x;
    cin>>n>>x;
    vector<int> l(n);
    rep(i,n)cin>>l[i];
    int ans=0;
    int d=0;
    if(d<=x)ans++;
    rep(i,n){
        d=d+l[i];
        if(d<=x)ans++;
    }
    cout<<ans<<endl;
   
    return 0;
}

Measured memory_bytes: 256
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a_sum = [0]
for i in range(n):
  a_sum.append(a[i] + a_sum[i])
b_sum = [0]
for i in range(m):
  b_sum.append(b[i] + b_sum[i])
  
ans = 0
j = m
for i in range(n+1):
  if a_sum[i] > k:
    break
  while a_sum[i] + b_sum[j] > k:
    j -= 1
  ans = max(ans, i + j)
print(ans)

Measured memory_bytes: 47328
#include<stdio.h>
#define K 2000000

void count (int[], int);

int main()
{
  int A[K],n,i;


  scanf("%d",&n);

  for(i=0; i<n; i++)
    {
      scanf("%d",&A[i]);
    }

  count(A,n);

  return 0;
}


void count(int A[], int n)
{
  int i,j,C[K],B[K];

  for(i=0; i<=K; i++)
    {
      C[i]=0;
      B[i]=0;
    }
  for(i=0; i<n; i++)
    {
      C[A[i]]++;
      
    }
  
  for(i=1; i<=K; i++)
    {
      C[i]=C[i]+C[i-1];
      
    }

  for(i=n-1; i>=0; i--)
    {
      B[C[A[i]]]=A[i];
      
      C[A[i]]--;
	     
    }
  for(i=1; i<=n; i++)
    {
      printf("%d",B[i]);
      if(i!=n) printf(" ");
    }
  printf("\n");
}
  



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

using namespace std;

const int NEUTRO = 0;
struct segmentTree {
    const int NEUTRO = 0;
    int n;
    vector<int> st;
    void init(int _) {
        n = _;
        st.resize(5 * n);
    }

    void update(int pos,int value){
        for (st[pos += n]= value; pos > 1; pos>>=1)
            st[pos>>1] = st[pos] + st[pos^1]; 
    }
    // interval[l,r)
    int query(int l,int r){
        int ans = NEUTRO;
        r++;
        for (l += n,r += n;l < r;l>>=1,r>>=1){
            if(l & 1) ans += st[l++];
            if(r & 1) ans += st[--r];
        }
        return ans;
    }
};

segmentTree st[30];

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n,q;
    string s;
    cin >> n >> s;

    for (int i = 0; i < 30; ++i) st[i].init(n);

    for (int i = 0; i < (int)s.size(); ++i) {
        st[s[i] - 'a'].update(i, 1);
    }
    

    cin >> q;
    while(q--) {
        int c;
        cin >> c;
        if(c == 1) {
            int p;
            char x;
            cin >> p >> x;
            p--;
            char cur = s[p];
            st[cur - 'a'].update(p, 0);
            s[p] = x;
            st[x - 'a'].update(p, 1);
        } else {
            int ans = 0;
            int l, r;
            cin >> l >> r;
            l--,r--;
            for (int i = 0; i < 30; ++i) 
                ans += st[i].query(l, r) != 0;
            cout << ans << "\n";
        }

    }
    return 0;
}


Measured memory_bytes: 293916
//Name: Signboard
//Level: 2
//Category: 文字列,全探索
//Note:
#include <iostream>
#include <string>

using namespace std;

bool check(const string &str, const string &target, int start) {
    const int SLEN = str.size();
    const int TLEN = target.size();
    for(int delta = 1; ; ++delta) {
        int pos = start;
        bool ok = true;
        for(int i = 0; i < TLEN; ++i) {
            if(pos >= SLEN) return false;
            if(str[pos] != target[i]) {
                ok = false;
                break;
            }
            pos += delta;
        }
        if(ok) return true;
    }
    return false;
}

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

    int N;
    string target;
    cin >> N >> target;

    int ans = 0;
    for(int i = 0; i < N; ++i) {
        string str;
        cin >> str;
        const int L = str.size();
        for(int j = 0; j < L; ++j) {
            if(str[j] == target[0]) {
                if(check(str, target, j)) {
                    ++ans;
                    break;
                }
            }
        }
    }

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

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

#define rep(i, n) for(long long i=0;i<(long long)(n);i++)
#define rep2(i, s, n) for(long long i=(s);i<(long long)(n);i++)
#define repi(i, n) for(int i=0;i<(int)(n);i++)
#define rep2i(i, s, n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(), v.end()

#define deg2rad(deg) (((deg)/360)*2*M_PI)
#define rad2deg(rad) (((rad)/2/M_PI)*360)

using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;

const ll INF = (1LL<<60);
const int INFi = (1<<29);

/*素数判定*/
bool is_prime(ll n){
    if(n==1) return false;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0) return false;
    }
    return true;
}

/*約数列挙*/
vll enum_divisors(ll n){
    vll l;
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            l.push_back(i);
            if(n/i != i) l.push_back(n/i);
        }
    }
   sort(all(l));
   return l;
}

/*素因数分解*/
vector<P> prime_factorize(ll n){
    vector<P> l;
    for(ll i=2;i*i<=n;i++){
        if(n%i!=0) continue;
        ll e = 0;
        while(n%i==0){
            e++;
            n /= i;
        }
        l.push_back({i, e});
    }
    if(n!=1) l.push_back({n, 1});
    return l;
}

/*最小公倍数*/
ll lcm(ll a, ll b){
    return a*b/__gcd(a,b);
}

/*最大公約数*/
ll gcd(ll a, ll b){
    return __gcd(a,b);
}

int main(){

    ll n; cin >> n;
    vector<ld> v(n);
    rep(i, n) cin >> v[i];

    sort(all(v));
    rep2(i, 1, n){
        v[i] = (v[i]+v[i-1])/2;
    }

    cout << v[n-1] << endl;

    return 0;
}

Measured memory_bytes: 3836
#include <bits/stdc++.h>
#define M 100001

using namespace std;

int n, h[M], dp[M];

int main() {
    cin >> n;

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

    dp[0] = 0;
    dp[1] = abs(h[0] - h[1]);
    for (int i = 2; i < n; ++i)
        dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]));

    cout << dp[n-1];
    return 0;
}

Measured memory_bytes: 4380
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {

    public static void main(String[] args) throws Exception {

        try {

            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

            int nowHour = Integer.parseInt(br.readLine());
            int needToNewYear = 48 - nowHour;

            System.out.println(needToNewYear);
        } catch (IOException | NumberFormatException e) {
            e.printStackTrace();
            System.exit(0);
        } catch (final Exception e) {
            e.printStackTrace();
            System.exit(0);
        }
    }
}

Measured memory_bytes: 20564
import scala.io.StdIn.{readLine,readInt}

object Main {

  def maxHeapify(n:Int, a:Array[Int], i:Int):Unit = {
    var largest = i
    if(i*2 <= n) {
      if(a(i*2-1) > a(i-1)) largest = i*2
      if(i*2+1<=n && a(i*2) > a(largest-1)) largest = i*2+1
      if(largest != i) {
        val temp = a(largest-1)
        a(largest-1) = a(i-1)
        a(i-1) = temp
        maxHeapify(n,a,largest)
      }
    }
  }

  def main(args:Array[String]) = {
    val n = readInt
    val a = readLine.split(" ").map(_.toInt)
    for(i<-n/2 to 1 by -1) {
      maxHeapify(n,a,i)
    }
    println(" "+a.mkString(" "))
  }
}

Measured memory_bytes: 189564
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int N,x,y,ans1,ans2=-1;
	vector <int> num;
	cin >> N;
	while(N--){
		cin >> x >> y;
		if(y>ans2){
			num.clear();
			num.push_back(x);
			ans2 = y;
		}
		else if(y==ans2){
			num.push_back(x);
		}
	}
	sort(num.begin(),num.end());
	cout << num[0] << ' ' << ans2 << endl;
	return 0;
}


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

typedef long long ll;
using namespace std;

ll gcd(ll a, ll b) { //最大公約数
  if (b==0) return a;
  else return gcd(b, a%b);
}

ll lcm(ll a, ll b) { //最小公倍数
  return a * b / gcd(a, b);
}

ll digit_sum(ll a){ //10進桁和
  ll ans=0;
  while(a>0){
    ans+=a%10;
    a/=10;
  }
  return ans;
}



int main()
{

  ll s;
  cin>>s;

  ll ans=1;
  if(s==1||s==2||s==4){
    cout<<4<<endl;
    return 0;
  }


  while(s!=4){
    ans++;
    if(s%2==0){
      s=s/2;
    }else{
      s=3*s+1;
    }
  }


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


Measured memory_bytes: 3568
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define irep(i, n) for (int i = (n); i >= 0; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 25;
int cost[10][10], a[200][200], dist[10][10]; 
int main() {
  int h,w;
  cin >> h >> w;
  rep(i,10) rep(j,10) cin >> dist[i][j];
  rep(i,h) rep(j,w) cin >> a[i][j];

  rep(k,10) rep(i,10) rep(j,10) {
    dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
  }
  int ans = 0;
  rep(i,h) rep(j,w) {
    if (a[i][j] == -1) continue;
    int num = a[i][j];
    ans += dist[num][1];
  }
  cout << ans << endl;
  return 0;
}

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

int main()
{
    ll n, k;
    cin >> n >> k;

    ll answer = k;
    for (int i = 1; i < n; i++)
    {
        answer *= (k - 1);
    }

    cout << answer << endl;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define REPR(i,n) for (ll i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (int i = m; i < n; ++i)
#define FORR(i,m,n) for (ll i = n-1; i >= m; --i)
#define FORE(x,xs) for (const auto& x : xs)
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()

const int MAX = 5e5+10;

string S;

ll solve() {
    if (S[0] == '>') S = '<' + S;
    if (S[S.size()-1] == '<') S = S + '>';
    S = S + ';';

    vector<string> strs;
    string s;
    REP (r, S.size()-1) {
        s += S[r];
        if (S[r] == '>' && S[r+1] != '>') {
            strs.push_back(s);
            s = "";
        }
    }

    ll ans = 0;
    FORE (s, strs) {
        ll left = 0, right = 0;
        while (s[left] == '<') left++;
        right = s.size() - left;
        ll res = left * (left+1) / 2 +  right * (right+1) / 2 - min(left, right);
        ans += res;
    }
    return ans;
}

int main() {
    cin >> S;
    cout << solve() << endl;
}

Measured memory_bytes: 7616
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>
#include <functional>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define EB emplace_back
#define GREATER(T) T, VT<T> greater<T>
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

int main(void) {
    string S, T;
    cin >> S >> T;
    int A, B;
    cin >> A >> B;
    string U;
    cin >> U;

    cout << A - (S == U) << " " << B - (T == U) << endl;
}


Measured memory_bytes: 256
n = int(input())
p = list(map(int, input().split()))
cnt = 0
for i in range(1,n-1):
    if p[i] != min(p[i-1],p[i],p[i+1]) and p[i] != max(p[i-1],p[i],p[i+1]):
        cnt += 1
print(cnt)

Measured memory_bytes: 3060
from fractions import gcd

a, b = map(int, input().split())
d = gcd(a, b)

ans = 1
n = d
for i in range(2, d + 1):
    if n % i == 0:
        ans += 1
        while n % i == 0:
            n //= i
    if n < i * i:
        if 1 < n:
            ans += 1
        break
print(ans)

Measured memory_bytes: 65640
import java.util.Scanner;

class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
    
        int a = scan.nextInt();
        int b = scan.nextInt();
        int f1,f2;
        double f3;
        f1 = a / b;
        f2 = a % b;
        f3 = (double)a / (double)b;
        System.out.println(f1);
        System.out.println(f2);
        System.out.println(String.format("%.5f",f3));
        
       
        }
    }


Measured memory_bytes: 26452
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
signed main() {
  ios::sync_with_stdio(false);
  int H, W; cin >> H >> W;
  int h, w;
  REP(i,H) REP(j,W) {
    string s; cin >> s;
    if(s == "snuke") {
      h = i; w = j;
    }
  }
  cout << (char)('A' + w) << (h + 1) << endl;
}


Measured memory_bytes: 256
c = []
for i in range(3):
    c.append(list(map(int, input().split(" "))))

f = "No"
for a1 in range(101):
    for a2 in range(101):
         for a3 in range(101):
            if (c[0][0] - a1 == c[0][1] - a2 == c[0][2] - a3
                and c[1][0] - a1 == c[1][1] - a2 == c[1][2] - a3
                and c[2][0] - a1 == c[2][1] - a2 == c[2][2] - a3):
                f = "Yes"

print(f)

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

#define ll long long
#define ar array

ll h[200000];

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

	int n, k;
	cin >> n >> k;
	for(int i=0; i<n; ++i)
		cin >> h[i];
	sort(h, h+n);
	ll s=0;
	for(int i=0; i<n-k; ++i)
		s+=h[i];
	cout << s;
}


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

int main() {
  long long int n;
  cin >> n;
  
  long long int sqrtInt = ceil(sqrt(n)) + 1;

  long long int max = n + 1;

  for(int i=1;i<sqrtInt;i++) {
    if (n % i == 0) {
      long long int shou = n / i;
      if (shou + i < max) {
        max = shou + i;
      }
    }
  }

  cout << max - 2 << endl;
}

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

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
// pll pp; -> (pp.first,pp.second)
// vector<vl> pp(n,vl(2)); sort(pp.begin(),pp.end(),[](vl a,vl b){return a[0]<b[0];});

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define RREP(i,n) for(ll (i)=(n)-1;(i)>=0;(i)--)
#define FOR(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
#define FORR(i,a,b) for(ll (i)=(b)-1;(i)>=(a);(i)--)
#define DEBUG(x) cout << #x << ": " << x << endl
#define CHMAX(a,b) a=max((a),(b))
#define CHMIN(a,b) a=min((a),(b))
/*}}}*/
int main() {
  ll n;
  cin >> n;
  vl len(n);
  REP(i,n) cin >> len[i];
  sort(len.begin(),len.end());
  ll ans = 0;
  REP(i,n-2){
    FOR(j,i+1,n-1){
      ll ok = j;
      ll ng = n;
      while(abs(ok-ng)>1){
        ll m = (ok+ng)/2;
        if(len[m]<len[i]+len[j]) ok = m;
        else ng = m;
      }
      ans += ok - j;
    }
  }
  cout << ans<< endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
int main()
{
    int a,c,i;
    char b[11], d[11];
    scanf("%d%d",&a, &c);
    for(i=0; i<c;i++) b[i] = '0' + a;
    b[i] = '\0';
    for(i=0; i<a; i++) d[i] = '0'+ c;
    d[i] = '\0';
    if(strcmp(b,d) >= 0) printf("%s\n",d);
    else printf("%s\n",b);
    return 0;
}

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

using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n; i>-1; --i)
#define ALL(a) (a).begin(),(a).end()
#define FILL(a,n,x); REP(i,(n)){ (a)[i]=(x); }
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define FILL2(a,n,m,x); REP(i,(n)){ REP(j,(m)){(a)[i][j]=(x);} }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }
#define Liny "Yes\n"
#define Linn "No\n"
#define LINY "YES\n"
#define LINN "NO\n"

#define umap unordered_map
//cout << setfill('0') << right << setw(4) << 12; // "0012"
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
int keta_wa(ll x){ if(x<10){return x;} else{return keta_wa(x/10) + x%10;} }
int ctoi(char c){ return ( (c>='0' && c<='9')? c - '0': 0 );}
int __stoi(string s){ return atoi(s.c_str()); }
ll sum(ll a[],ll N){ return accumulate(a,a+N,0LL);}
ll gcd(ll a,ll b){if(a<b)swap(a,b); return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){if(a<b){swap(a,b);} return a/gcd(a,b)*b;}
template<class T> void chmax(T& a, T b){ if(a<b){a=b;} }
template<class T> void chmin(T& a, T b){ if(a>b){a=b;} }
const ll MOD = 1e9+7;

#define pll pair<ll,ll>

const int MAX = 30000000;
ll f[MAX],finv[MAX],inv[MAX];
void COMinit(int N){
    f[0] = 1;
    f[1] = 1;
    finv[0] = 1;
    finv[1] = 1;
    inv[1] = 1;
    for(int i=2;i<=N;++i){
        f[i] = f[i-1]*i %MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) %MOD;
        finv[i] = finv[i-1]*inv[i]%MOD;
    }
}
ll COM(int N, int K){
    if(N<K || N<0 || K <0){ return 0; }
    return f[N]*(finv[K]*finv[N-K]%MOD) %MOD;
}


int main(){
    ll N,K; cin>>N>>K;
    COMinit(N);
    for(int i=1;i<=K;++i){
        ll ans = COM(N-K+1,i) * COM(K-1,i-1);
        ans %= MOD;
        cout << ans << "\n";   
    }
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#define ll long long
#define db double
#define mod 1000000007
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define endl "\n"
#define pb push_back
#define mp make_pair
#define inf LONG_LONG_MAX
#define inf1 INT_MAX
using namespace std;
/*
ll mpow(ll a, ll b){
    if(!b)
        return 1;
    ll temp=mpow(a,b/2);
    temp=(temp*temp)%mod;
    if(b%2)
        return (a*temp)%mod;
    return temp;
}

ll _pow(ll a, ll b){
    if(!b)
        return 1;
    ll temp=_pow(a,b/2);
    temp=(temp*temp);
    if(b%2)
        return (a*temp);
    return temp;
}

ll mod_in(ll n){
    return mpow(n,mod-2);
}
*/
int main()
{
    fastio
    string s;
    cin>>s;
    sort(s.begin(), s.end());
    if(s[0]==s[2])
    {
        cout<<"No";
    }
    else
    {
        cout<<"Yes";
    }
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
    int n,k,i,j;
    scanf("%d",&n);
    k=n;
    if(n%4==0){
        printf("Yes\n");
        return 0;
    }
    else if(n%7==0){
        printf("Yes\n");
        return 0;
    }
    else{
        while(n>=7){
            n=n-7;
            if(n%4==0){
                printf("Yes\n");
                return 0;
            }
            else{
                continue;
            }
        }
        while(k>=4){
            k=k-4;
            if(k%7==0){
                printf("Yes\n");
                return 0;
            }
            else{
                continue;
            }
        }
    }
    printf("No\n");
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int INF = 1001001001;

int main() {
int N,K;
cin >> N >> K;
int ans = 0;
for (int i = 0;i < N;i++) {
  int a;
  cin >> a;
  ans += 2*min(abs(a-K),a);
}
cout << ans << endl;

return 0;
}

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

int main(){
	map <int,int> a;
	int n,t;
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>t;
		a[t]++;
	}
	for(int i=1;i<=n;i++){
		cout<<a[i]<<endl;
	}
	return 0;
}


Measured memory_bytes: 12972
blue=[]
red=[]
point=0
point_blue=0
point_red=0

N=int(input())
for i in range(N):
    blue+=[input()]
M=int(input())
for i in range(M):
    red+=[input()]

for i in blue:
    point_blue=blue.count(i)
    point_red=red.count(i)
    if point_blue-point_red>point:
        point=point_blue-point_red

print(point)

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

using namespace std;

typedef long long ll;

int x[5001];
int n;
pair<int,int> dp[1001];
vector<int> e[1001];
bool juu;
void solve(int y)
{
    if(juu) return ;
    int sum = 0;
    bitset<5001> p;
    p[0] = 1;
    for (int c: e[y])
    {
        pair<int,int> a = dp[c];
        p = (p<<a.first)|(p<<a.second);
        sum += (a.first+a.second);
    }
    for (int i = x[y]; i >= 0; --i)
    if (p[i])
    {
        dp[y] = {x[y],sum-i};
        return;
    }
    juu=true;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    juu=false;
    int c;
    for(int i=2;i<=n; ++i)
    {
        cin >> c;
        e[c].push_back(i);
    }
    for(int i=1; i<=n; ++i) cin >> x[i];
    for(int i=n; i; --i) solve(i);
    if(juu) cout << "IMPOSSIBLE"<<endl;
    else cout << "POSSIBLE"<<endl;
    return 0;
}


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

int main() {
    string s;
    int x=0,y=0;
    cin>>s;
    for (int i = 0; i <s.length() ; ++i) {
        if(s[i]=='A'){
            x=i;
            break;
        }
    }
    for (int j = s.length()-1; j >x ; j--) {
        if (s[j]=='Z'){
            y=j;
        break;
        }
    }
    printf("%d",y-x+1);
    return 0;
}

Measured memory_bytes: 640
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
 
#define int long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define Aint(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define FST first
#define SND second
#define SZ(a) (signed)((a).size())
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort((c).begin(), (c).end())
 
using namespace std;
 
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
 
const int MOD = 1000000007;
const char ENDL = '\n';
 
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")"  << " " << __FILE__ << endl;
 
int modPow(int x, int p, int mod) {
    int ret = 1;
    while (p > 0) {
        if (p & 1)
            ret = ret * x % mod;
        x = x * x % mod;
        p >>= 1;
    }
    return ret;
}
 
class modCombination {
    vector<int> x, xi;
 
public:
    modCombination(int max) : x(max + 1), xi(max + 1) {
        x[0] = 0;
        x[1] = 1;
        for (int i = 2; i <= max; ++i) {
            x[i] = x[i - 1] * i % MOD;
        }
        xi[0]=1;
        for (int i = 1; i <= max; ++i) {
            xi[i] = modPow(x[i],MOD-2,MOD);
        }
    }
 
    int combination(int n,int r){
        return ((x[n]*xi[r]) % MOD) *xi[n-r] % MOD;
    }
};
 
signed main(void) {
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed, ios::floatfield);
    cout.precision(10);
    cin.tie(0);
 
    int h, w, a, b;
    cin >> h >> w >> a >> b;
 
    modCombination c(h+w+2);
 
    int ans = 0;
    REP(i, min(h - a, w - b)) {
        ans += c.combination(h - a - i - 1 + b + i, b + i) * c.combination(a + i + w - b - i - 1, w - b - i - 1) % MOD;
        ans %= MOD;
    }
 
    cout << ans << ENDL;
 
    return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define i64 long long
#define N (int)(1e5)
#define pii pair<int,int>
#define L first 
#define R second
#define all(x) x.begin(),x.end()
using namespace std;
bool isDigit(char c){
	return (c>='0' and c<='9');
}
int main(){
	int n; cin>>n;
	vector<int> v(n);
	for(int i=0;i<n;i++) cin>>v[i];
	vector<int>:: iterator it;
	sort(all(v));
	it = unique(all(v));
	v.resize(distance(v.begin(),it));
	printf("%d\n",v.size());
	return 0;
}

Measured memory_bytes: 256
/*
CF ID: Ankit717
LANG: C++
*/
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
#define mod 1000000007
#define maxn 200005
#define f(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rf(i,a,b) for(ll i=(ll)(a);i>=(ll)(b);i--)
#define pb push_back
#define pf push_front
#define nl cout << "\n";

const ll INF=1e18L+5;
 
struct Data{
	ll p;
	ll h;
};

void ini(){
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
}

bool comp(pll &a,pll &b){
	if(a.first==b.first){
		return a.second>b.second;
	}else{
		return a.first<b.first;
	}
}

// vector<pll> adj[maxn];
// vector<ll> par;
// vector<bool> vis;

ll gcd(ll a,ll b){
    while(a!=0){
        ll temp=a;
        a = b % a;
        b = temp;
    }

    return b;
}

// bool prime[maxn],near[maxn];
// void sieve(){
// 	f(i,0,maxn+1){
// 		prime[i]=true;
// 	}
// 	prime[0]=falsrime[1]=false;
// 	for(ll i=2;i*i<=maxn;i++){
// 		if(prime[i]){
// 			for(j=i*i;j<=maxn;j+=i){
// 				prime[j]=false;
// 			}
// 		}
// 	}
// }

void solve(){
	string s;
	cin >> s;

	ll n=0;
	f(i,0,s.size()){
		n+=((ll)s[i]-48);
	}

	if(n%9==0){
		cout << "Yes";nl;
	}else{
		cout << "No";nl;
	}
}	

int main(){
	ini();
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	
    
	// ll t;
	// cin >> t;
	// f(i,0,t){
		solve();
	//}
}


Measured memory_bytes: 3776
L=int(input())
dp=[0]*5
for i in range(L):
  A=int(input())
  
  even=A%2
  if A==0:
    even=2
  odd=(A+1)%2
  
  #それぞれのDPには、i番目のAを5つのゾーンに割り当てた際の最小が記録される
  dp[4]=min(dp[:])+A
  dp[3]=min(dp[:4])+even
  dp[2]=min(dp[:3])+odd
  dp[1]=min(dp[:2])+even
  dp[0]=dp[0]+A
  
print(min(dp))

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(0)
#define endl "\n"
#define int long long
typedef vector<int> vi;
#define all(x) x.begin(),x.end()
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
#define pii              pair <int,int>
#define DEBUG(x) cerr << '>' << #x << ':' << x << endl;
typedef long long ll;
//#pragma comment(linker, "/STACK:667772160")
#define in_range(x, y, r, c) ((x >= 0 && x < r && y >= 0 && y < c))

const double eps=1e-9;
const int MOD=1e9+7;
const int N=1e5+30;
const int inf = 1e17+995;

template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
void boostIO() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
int mem[111][N],n,val[111],w[111],k;
int dp(int idx,int rem){
    if(idx==n and rem>=0)
        return 0;
    if(rem<0)
        return -inf;
    int &ret=mem[idx][rem];
    if(~ret)
        return ret;
    ret=dp(idx+1,rem);
    ret=max(ret,val[idx]+dp(idx+1,rem-w[idx]));
    return ret;
}
int32_t main() {
boostIO();
cin>>n>>k;
    for (int i = 0; i < n; ++i) {
        cin>>w[i]>>val[i];
    }
    memset(mem,-1, sizeof(mem));
    int ans=dp(0,k);
    cout<<ans;
}

Measured memory_bytes: 87040
#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;
  int num_odd = 0;
  int num_4 = 0;

  scanf("%d",&N);

  FOR(i, N) {
    int a;

    scanf("%d",&a);

    if (a % 4 == 0)
      num_4 ++;
    if (a % 2 == 1)
      num_odd ++;
  }

  if (num_odd <= num_4 ||
      (num_odd - 2 < num_4 && num_odd + num_4 == N))
    printf("Yes\n");
  else
    printf("No\n");
  
  return 0;
}


Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
l = [[] for _ in range(N)]
p = [0]*N
e = [0]*N
q = []

for _ in range(N-1):
    fi, si, wi = tuple(LIST())
    l[fi-1].append([si-1, wi])
    l[si-1].append([fi-1, wi])
Q, K = tuple(LIST())
for _ in range(Q):
    q.append(LIST())

def f(n, w):
    p[n] = 1
    e[n] = w
    for next_node in l[n]:
        nn, nw = tuple(next_node)
        if p[nn] == 0:
            f(nn, w+nw)
f(K-1, 0)
for nodes in q:
    fi, si = tuple(nodes)
    print(e[fi-1]+e[si-1])


Measured memory_bytes: 165752
#include<iostream>
#include<vector>
#include <algorithm>
#include <string>
#include <utility>
#include <set>
#include <map>
#include<cmath>
#include <queue>
#include <numeric>
#include <cassert>

using lli = long long int;
int inf = 1000000007;
using namespace std;

void solve()
{
	int N, K;
	cin >> N >> K;
	vector<char> D(N);
	for (int i = 0; i < K; i++) {
		cin >> D[i];
	}
	for (int i = N; i < 100000; i++) {
		string s = to_string(i);
		bool flag = true;
		for (int j = 0; j < K; j++) {
			if (count(s.begin(), s.end(), D[j]) >= 1) { flag = false; break; }
		}
		if (flag) { cout << i << endl; return; }
	}
}

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

Measured memory_bytes: 256
#include<stdio.h>
int a[110];
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=0;i<n;i++)
    scanf("%d",&a[i]);
    int t,sum=0,minj;
    for (int i=0;i<n;i++)
    {
        minj=i;
        for(int j=i;j<n;j++)
        {
            if(a[j]<a[minj])
                minj=j;
        }
        t=a[i];a[i]=a[minj];a[minj]=t;
        if(i!=minj) sum++;
    }
    printf("%d",a[0]);
    for (int i=1;i<n;i++)
        printf(" %d",a[i]);
    printf("\n");
    printf("%d\n",sum);
    return 0;
}

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

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int n;
  cin>>n;
  long long int a[100];
  a[0]=2;
  a[1]=1;

  for(int i=2;i<=n;i++){
    a[i]=a[i-1]+a[i-2];
  }
  cout<<a[n];
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int a;
    while(cin >> a,~a){
        int rev=1150;
        if(a>=30)rev+=(a-30)*160+1400+1250;
        else if(a>=20)rev+=(a-20)*140+1250;
        else if(a>=10)rev+=(a-10)*125;
        cout << 4280-rev << endl;
    }
}



Measured memory_bytes: 3068
gets
q=$<.map{|s|s.split.map &:to_i}.map{|s|[s[1],s[0]]}
#i=0
#q.sort_by! {|v| [v, i += 1] }
q.sort!.reverse!
t = q[0][0]

q.each do |e|
  t = e[0] if t >= e[0]
  t -= e[1]
end

if t < 0
  puts 'No'
else
  puts 'Yes'
end


Measured memory_bytes: 25208
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import itertools

n = ni()
k = -1

for i in range(1,10**7):
    if i*(i-1)//2 > n:
        break
    elif i*(i-1)//2 == n:
        k = i

if k == -1:
    print('No')
    exit()

print('Yes')
print(k)

a = list(itertools.combinations(range(k), 2))
ans = [[] for i in range(k)]

for i in range(len(a)):
    x,y = a[i]
    ans[x].append(i+1)
    ans[y].append(i+1)

for l in ans:
    print(str(k-1) + ' ' + (' '.join([str(u) for u in l])))


Measured memory_bytes: 19492
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i=0; i<(ll)n; i++)
#define REPR(i, n) for(ll i=(ll)n-1; i>=0; i--)
#define FOR(i, m, n) for(ll i=(ll)m; i<(ll)n; i++)
#define FORR(i, m, n) for(ll i=(ll)m-1; i>=(ll)n; i--)
#define ALL(x) (x).begin(), (x).end()
#define ASC(v) sort(ALL(v));
#define DESC(v) sort(ALL(v), greater<int>());
#define UNIQ(a) sort(ALL(a));(a).resize(unique(ALL(a)) - a.begin());
#define PRINTD(x, d) cout << fixed << setprecision(d) << x << "\n";
#define DEBUG(x) cout<<#x<<": "<<x<<"\n"
const double PI = acos(-1);
ll lcm(ll a, ll b) { return a / __gcd(a, b) * b; }
bool isprime(int x){ int i; if(x<2)return 0; else if(x==2) return 1; if(x%2==0) return 0; for(i=3; i*i<=x; i+=2) if(x%i==0) return 0; return 1; }
int digsum(int n) { int r=0; while(n>0) { r+=n%10; n/=10; } return r; }
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
 
int main(){
    string N;
    cin >> N;
    FOR(i, stoi(N), 1000) {
        string i1 = to_string(i).substr(0,1);
        string i2 = to_string(i).substr(1,1);
        string i3 = to_string(i).substr(2,1);
        if (i1==i2 & i1==i3) {
            cout << i;
            break;
        }
    }
    cout << "\n";
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); i++)

#define M (201000)
int N, a[40];
double dp[40][M];

inline double calc(double a, double b) { return fabs(a-b)/a; }

int main() {
    scanf("%d", &N);
    rep(i, N) scanf("%d", a+i);
    rep(i, N) rep(j, M) dp[i][j] = 1e100;
    rep(i, M) dp[0][i] = calc(a[0], i);
    rep(i, N-1) for(int j=1; j<M; j++) for(int k=j; k<M; k+=j) {
        dp[i+1][k] = min(dp[i+1][k], max(dp[i][j], calc(a[i+1], k)));
    }
    double ans = 1e100;
    rep(i, M) ans = min(ans, dp[N-1][i]);
    printf("%.12f\n", ans);
    return 0;
}

Measured memory_bytes: 0
n = int(input())
x = []
for i in range(n):
  a,b,c = map(int,input().split())
  x.append([a,b,c])
dp = [[0]*3 for i in range(n+1)]
for i in range(n):
  dp[i+1][0] = max(max(dp[i][1],dp[i][2])+x[i][0],dp[i+1][0])
  dp[i+1][1] = max(max(dp[i][0],dp[i][2])+x[i][1],dp[i+1][1])
  dp[i+1][2] = max(max(dp[i][1],dp[i][0])+x[i][2],dp[i+1][2])
print(max(dp[-1]))

Measured memory_bytes: 42572
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
// ----- boost -----
#include <boost/rational.hpp>
#include <boost/multiprecision/cpp_int.hpp>
// ----- using directives and manipulations -----
using boost::rational;
using boost::multiprecision::cpp_int;
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
typedef long long ll;
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(int i=num, i##_len=(n); i<i##_len; ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define print(x) (cout << (x) << endl)
#define pb push_back
#define mp make_pair
#define sz(x) int(x.size())
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
#define fs first
#define sc second

const int INF = 1e9;
const ll LLINF = 1e16;
const ll MOD = 1e9+7;
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};

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

// 指定した文字cが文字列に何文字入ってるか
ll stringcount(string s, char c) {
    return count(s.cbegin(), s.cend(), c);
}


// 割り算の切り上げ処理
template<typename T>
T rp(T a, T b) {
  return (a + b - 1) / b;
}

// 桁和
template<typename T>
T digsum(T n) {
    T res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}

// 回文判定
bool kai (string s) {
    string t{s};
    reverse(begin(t), end(t));
    return s == t;
}

using pint = pair<int, int>;
using pll = pair<ll, ll>;
 
int64_t N, K;
vector<ll> A;
vector<ll> F;
 
bool check(int64_t X){
    ll sum = 0;
    for(int i=0; i<N; i++){
        ll ok = X/F[i];
        if(ok < A[i]) sum += A[i] - ok;
    }
    return (sum <= K);
}
 
int main(){
    cin >> N >> K;
    A.resize(N);
    F.resize(N);
    for(int i=0; i<N; i++) cin >> A[i];
    for(int i=0; i<N; i++) cin >> F[i];
    sort(all(A));
    sort(rall(F));
    int64_t ok = 1e13, ng = -1;
    while(ok-ng>1){
        int64_t mid = (ok+ng)/2;
        (check(mid) ? ok : ng) = mid;
    }
    cout << ok << endl;
    return 0;
}


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

#define inf 1e9+7
typedef long long ll;

int n;
vector<vector<int> > cost;

void solve(int s){
    vector<bool> flg(n,false);
    flg[s]=true;
    vector<int> vc;
    vc.push_back(s);


    int sum=0;
    int mi,next;
    while(1){
        mi=inf;
        next=-1;
        for(int i=0;i<vc.size();i++){
            for(int j=0;j<n;j++){
                if(flg[j]||cost[vc[i]][j]<0)continue;
                if(mi>cost[vc[i]][j]){
                    mi=cost[vc[i]][j];
                    next=j;
                }
            }
        }
        if(next==-1)break;
        else{
            sum+=mi;
            flg[next]=true;
            vc.push_back(next);
        }
    }
    cout << sum << endl;
}

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

    cin >> n;
    cost.resize(n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int a;
            cin >> a;
            cost[i].push_back(a);

        }
    }

    solve(0);
    return 0;
}



Measured memory_bytes: 3140
<?php

$a = trim(fgets(STDIN));

$a1 = substr($a,0,1);


if("A" !== $a1){
  echo "WA\n";
  return;
}

$a2 = substr($a,2,-1);

// if(strlen($a2) - strlen(str_replace("C","",$a2)) != 1){
if(substr_count($a2, "C") != 1){
  echo "WA\n";
  return;
}

$a3 = str_replace("C","c",$a2) .  substr($a,1,1) . substr($a,-1,1);
// echo $a3;

if(!ctype_lower($a3)){
  echo "WA\n";
  return;
}

echo "AC\n";

Measured memory_bytes: 4856
x = input()
y = input()
z = input()

x = x.split()
y = y.split()
z = str(z)

num1 = int(y[0])
num2 = int(y[1])

str1 = str(x[0])
str2 = str(x[1])

if z == str1:
    num1 = num1 - 1
    print(str(num1) + ' ' + str(num2))
elif z == str2:
    num2 = num2 - 1
    print(str(num1) + ' ' + str(num2))

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

int main(){
  int n;
  cin >> n;
  int ans = 0;
  rep(i,n)rep(j,n)
    if(n == 4*i+7*j){
      puts("Yes");
      return 0;
    }
  puts("No");
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;

int main(){
	int n,i,j;
	long a[90]={};
	a[1]=1;
	a[0]=2;
	cin>>n;
	FORQ(i,2,n){
		a[i]=a[i-1]+a[i-2];
	}
	cout<<a[n]<<endl;;
	
    return 0;
}

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

long long n,m,r;

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

    cin>>n>>m;
    if(n>=m/2)
    {
        cout<<m/2<<endl;
        return 0;
    }
    else
    {
        r+=n;
        m-=2*n;
        r+=m/4;
        cout<<r<<endl;
        return 0;
    }

}


Measured memory_bytes: 3640
#include <algorithm>
#include <iostream>
#include <vector>
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
using namespace std;

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> tree(n), in(n), out(n);
  rep(i, n) {
    int a;
    cin >> a;
    tree[i] = a - 1;
    if (a > 0) in[a - 1]++, out[i]++;
  }
  vector<int> dp(n);
  rep(i, n) if (in[i] == 0) dp[i] = k;
  for (int i = n - 1; i >= 0; i--) {
    if (tree[i] > 0) cmax(dp[tree[i]], dp[i] - 1);
  }
  rep(i, n) if (out[i] == 0) dp[i] = 1;
  cout << count_if(all(dp), [](int x) { return x > 0; }) << endl;
}

Measured memory_bytes: 4400
#include <iostream>
#include <string>
typedef unsigned long ul;
#define REP(i, n) for (int i = 0; i < n; i++)
using namespace std;
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	string a;
	cin >> a;
	int c = 0;
	REP(i, 3)
	{
		if (a[i] == '1')
			++c;
	}
	cout << c << '\n';
}

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

int main() {
  long long N;
  cin >> N;
  vector<long long> V(N);
  for (long long i = 0; i < N; i++)
    cin >> V.at(i);
  
  vector<long long> W(N);
  long long max = 0;
  for (long long j = 0; j < N; j++) {
    if (V.at(j) >= max) {
      max = V.at(j);
      W.at(j) = V.at(j);
    }
    else
      W.at(j) = max;
  }
  long long ans = 0;
  for (long long k = 0; k < N; k++)
    ans += W.at(k) - V.at(k);
  
  cout << ans << endl;

  
}


Measured memory_bytes: 6364
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define pb push_back
#define pf push_front
#define eb emplace_back
using namespace std;
typedef long long ll;
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
using pi=pair<int,int>;
using vi=vc<int>;
void yes(){ cout << "Yes" << endl; }
void no(){ cout << "No" << endl; }
int SIZE(string s){return (int)s.size();}
const long long INF = 1LL << 60;

int main(){
    cout << fixed << setprecision(20);
    int a,b; cin >> a >> b;
    if(a <= b) cout << "unsafe" << endl;
    else cout << "safe" << endl;
    return 0;
}


Measured memory_bytes: 3632
/**
 * File    : B.cpp
 * Author  : Kazune Takahashi
 * Created : 1/20/2019, 10:36:14 PM
 * Powered by Visual Studio Code
 */

#include <iostream>
#include <iomanip>   // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple>
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set>
#include <functional>
#include <random> // auto rd = bind(uniform_int_distribution<int>(0, 9), mt19937(19920725));
#include <chrono> // std::chrono::system_clock::time_point start_time, end_time;
// start = std::chrono::system_clock::now();
// double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end_time-start_time).count();
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.

typedef long long ll;

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

// const int C = 1e6+10;
// const ll M = 1000000007;

const ll infty = 100000000007;

int N, K;
ll h[100010];
ll DP[100010];

int main()
{
  cin >> N >> K;
  for (auto i = 0; i < N; i++)
  {
    cin >> h[i];
  }
  fill(DP, DP + N, infty);
  DP[0] = 0;
  for (auto i = 0; i < N; i++)
  {
    for (auto j = i + 1; j < min(i + K + 1, N); j++)
    {
      DP[j] = min(DP[j], DP[i] + abs(h[i] - h[j]));
    }
  }
  cout << DP[N - 1] << endl;
}

Measured memory_bytes: 1792