akhauriyash/Code-Regression huggingface dataset:
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	
	static int[] fibo = new int[50];
	
	public static void fibo(){
		fibo[0] = 1;
		fibo[1] = 1;
		for(int i=2; i<49; i++)
			fibo[i] = fibo[i-1] + fibo[i-2];
	}
	
	static{ Arrays.fill(fibo, 0); }
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		fibo();
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int index = sc.nextInt();
			System.out.println(fibo[index]);
			//System.out.println("\n");
		}
	}
}

Measured memory_bytes: 26244
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <limits>
#include <cassert>
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
#define REPI(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define INF numeric_limits<double>::infinity()
constexpr long MOD = 1e9 + 7;
long gcd(long a, long b) {return b % a ? gcd(b % a, a) : a;}
long lcm(long a, long b) {return a / gcd(a, b) * b;}
using namespace std;
using P = pair<long, long>;
using VI = vector<long>;

VI adj[220];
VI visited;

void reset() {
    visited = VI(220, false);
}

P cnt(int i) {
//    cout << "Now seeing: " << i << endl;
    reset();
    int deg = adj[i].size();
    long div = 1;
    long depth = 0;
    bool first = true;
    VI cur;
    visited[i] = true;
    cur.push_back(i);
    while (1) {
        VI nex;
        long maxdeg = 1;
        for (auto j: cur) {
            if (!first) {
                maxdeg = max(maxdeg, long(adj[j].size() - 1));
            } else {
                first = false;
            }
            for (auto k: adj[j]) {
                if (!visited[k]) {
                    nex.push_back(k);
                    visited[k] = true;
                }
            }
        }
        
        if (nex.size() == 0) {
//            cout << "Its color: " << depth / 2 + 1 << endl;
//            cout << "Its leaf: " << div << " * " << deg << " = " << div * deg << endl;
            return P(depth / 2 + 1, div * deg);
        }
        cur = VI(nex);
        
        div *= maxdeg;
        depth++;
    }
    exit(1);
}

int main() {
    long n;
    cin >> n;
    long tmp = 100;
    REP(i,n-1) {
        long a, b;
        cin >> a >> b;
        a--; b--;
        long mid = tmp;
        tmp++;
        adj[a].push_back(mid);
        adj[mid].push_back(a);
        adj[mid].push_back(b);
        adj[b].push_back(mid);
    }
    
    long color = 1e9;
    long leaf = 1e9;
    
    for (int i = 0; i < 202; i++) {
        if (adj[i].size() > 1) { // not leaf
            P p = cnt(i); // first: color, second: leafs
            if (p.first < color) {
                color = p.first;
                leaf = p.second;
            }
            if (p.first == color) {
                if (p.second < leaf) {
                    leaf = p.second;
                }
            }
        }
    }
    cout << color << " " << leaf << endl;
}


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

int n, k;

string S;

vector< int > T;

int main()
{
    //freopen("a.inp","r",stdin);
    cin >> n >> k;
    cin >> S;
    int cur = 1;
    if(S[0] == '0') T.push_back(0);
    for(int i=1;i<n;i++)
    {
        if(S[i] == S[i-1]) ++cur;
        else
        {
            T.push_back(cur);
            cur = 1;
        }
    }
    T.push_back(cur);
    int x = 2 * k + 1;
    if(x >= T.size()) cout << n;
    else
    {
            int sum = 0, cmax = 0;
            int l = 0, r = 0;
            while(r - l <= 2 * k)
            {
                sum = sum + T[r];
                ++r;
            }
            cmax = max(cmax, sum);
            while(r < T.size())
            {
                if(r < T.size()) sum = sum + T[r];
                if(r+1 < T.size()) sum = sum + T[r+1];
                sum = sum - T[l];
                sum = sum - T[l+1];
                l = l + 2;
                r = r + 2;
                cmax = max(cmax, sum);
            }
        cout << cmax;
    }
}


Measured memory_bytes: 1020
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}  
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}


fn main() {
    input! {
        s: i64,
        w: i64,
    }

    if w >= s {
        println!("unsafe");
    } else {
        println!("safe");
    }
}


Measured memory_bytes: 2116
import sys
def main():
    A, B, C, K = map(int, input().split())
    l = []

    if K-A<0:
        out = K
        print(out)
        sys.exit()
        
    if K-A>=0:
        l.append(A)
        K = K-A
    if K-B>=0:
        K = K-B
    if K>0:
        m = K * -1
        l.append(m)
    out = sum(l)
    print(out)
main()

Measured memory_bytes: 9196
import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
l=[i for i in range(n)]
xy=[list(map(int,input().split()))  for _ in range(n)]
if n==1:
  print(1)
  exit()
comb=itertools.permutations(l,2)
dic={}
for c in comb:
    i,j=c
    xi,yi=xy[i]
    xj,yj=xy[j]
    p=xi-xj
    q=yi-yj
    if (p,q) not in dic:
        dic[(p,q)]=1
    else:
        dic[(p,q)]+=1
res=-1
ai=-1
for i in dic.keys():
    if res<dic[i]:
        ai=i
        res=dic[i]
print(n-dic[ai])

Measured memory_bytes: 77772
#include <iostream>
#include <stdint.h>
#include <vector>
#include <limits.h>
#include <utility>
#include <memory>
#include <set>
#include <map>

using namespace std;

using Group = set<int>;

inline uint64_t calc_convenience(Group& group)
{
  uint64_t island_count = group.size();
  return island_count * (island_count-1) / 2;
}

int main()
{
  int N,M;
  cin >> N >> M;

  vector<pair<int,int>> bridges;
  
  for (int m=0; m<M; ++m) {
    int a,b;
    cin >> a >> b;
    bridges.push_back(pair<int,int>(a,b));
  }

  map<int,shared_ptr<Group>> island2group;
  set<shared_ptr<Group>> groups;

  for (int n=0; n<N; ++n) {
    Group new_group = {n+1};
    auto ptr_new_group = make_shared<Group>(new_group);
    island2group[n+1] = ptr_new_group;
    groups.insert(ptr_new_group);
  }

  vector<uint64_t> conveniences = {0};

  for (int m=M-1; m>=0; m--) {
    auto bridge = bridges[m];
    int a = bridge.first, b = bridge.second;
    auto group_a = island2group[a];
    auto group_b = island2group[b];
    uint64_t convenience_prev = calc_convenience(*group_a) + calc_convenience(*group_b);
    if (group_a != group_b) {
      if (group_b->size() > group_a->size())
	swap(group_a,group_b);

      for (int island_b : *group_b) {
	group_a->insert(island_b);
	island2group[island_b] = group_a;
      }
      groups.erase(group_b);
      uint64_t convenience_now = calc_convenience(*group_a);
      conveniences.push_back(conveniences.back()+convenience_now-convenience_prev);
    } else {
      conveniences.push_back(conveniences.back());
    }
  }

  uint64_t final_convenience = conveniences.back();
  for (auto itr = conveniences.rbegin()+1; itr != conveniences.rend(); ++itr) {
    cout << final_convenience - *itr << endl;
  }
  
  return 0;
}

Measured memory_bytes: 28020
from sys import stdin,stdout

if __name__=="__main__":

    n=int(stdin.readline());

    a=[int(x) for x in stdin.readline().split()]
    b=[int(x) for x in stdin.readline().split()]
    c=[int(x) for x in stdin.readline().split()]

    sm=sum(b)

    for i in range(1,n):
        if a[i]-1==a[i-1]:
            sm+=c[a[i-1]-1]
    stdout.write(str(sm)+"\n")
    


Measured memory_bytes: 9212
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
const ll INF = 1e18;
#define REP(i,n) for(int i=0;i<n;i++)
#define ALL(v) v.begin(),v.end()


int main(){
	int h, w; cin >> h >> w;
	int a, b;
	set<P> st; multiset<ll> mst;
	REP(i,w){
		st.insert({i+1,i+1});
		mst.insert(0);
	}
	REP(i,h){
		cin >> a >> b;
		auto it=st.lower_bound({a,0});
		auto last=st.end();
		vector<P> era;
		while((*it).first<=b){
			era.push_back(*it);
			it++;
			if(it==last)
				break;
		}
		ll maxl=0;
		REP(i,era.size()){
			maxl=max(maxl,era[i].second);
			st.erase(era[i]);
			mst.erase(mst.find(era[i].first-era[i].second));
		}
		if(era.size()>0){
			st.insert({(b==w?INF:b+1),maxl});
			mst.insert((b==w?INF:b+1-maxl));
		}
		ll ans=*mst.begin()+i+1;
		cout << (ans<INF?ans:-1) << endl;
	}
	return 0;
}

Measured memory_bytes: 25396
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
typedef long long int ll;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
// clang-format on

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<ll> a(n);
    REP(i, 0, n) {
        cin >> a[i];
        a[i] = -a[i];
    }
    const ll inf = 1LL << 60;
    vector<ll> v(n, inf);
    REP(i, 0, n) {
        auto it = upper_bound(v.begin(), v.end(), a[i]);
        *it = a[i];
    }
    cout << lower_bound(v.begin(), v.end(), inf) - v.begin() << endl;

    return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<vector>

using namespace std;

long long knapsack(vector<long long>&weights, vector<long long>&values, vector<vector<long long> >&dp, long long  w, long long n){
	if(w==0||n<0) return 0;
	if(dp[n][w]!=-1)
		return dp[n][w];
	if(w>=weights[n])
		dp[n][w]=max(dp[n][w],knapsack(weights,values,dp,w-weights[n],n-1)+values[n]);
	dp[n][w]=max(dp[n][w],knapsack(weights, values, dp, w, n-1));
	return dp[n][w];
}
int main(){
	long long n, w;
	cin>>n>>w;
	vector<long long> values(n,0);
	vector<long long> weights(n,0);
	vector<vector<long long> > dp(n,vector<long long>(w+1,-1));
	for(int i=0; i<n; i++)
		cin>>weights[i]>>values[i];		
	cout<<knapsack(weights,values,dp,w,n-1)<<"\n";
}



Measured memory_bytes: 79488
#include<iostream>
using namespace std;
int x[5000],y[5000];
int main(){
	int n,m,tmp;
	cin>>n>>m;
	for(int i=0;i<n;i++)cin>>x[i]>>y[i];
	for(int i=0;i<n-1;i++){for(int j=n-1;j>i;j--){if(x[j]<x[j-1]){tmp=x[j],x[j]=x[j-1],x[j-1]=tmp;tmp=y[j],y[j]=y[j-1],y[j-1]=tmp;}}}
	int leftx,rightx,lefty,righty;
	for(int u=0;u<m;u++){
		cin>>leftx>>lefty>>rightx>>righty;
		int bef,aft;
		int left=0,right=n,mid;
		while(true){
			if(right<=left+1)
				break;
			mid=(right+left)/2;
			if(x[mid]>=leftx)
				right=mid;
			else
				left=mid;
		}
		bef=max(0,mid-1);
		left=0,right=n;
		while(true){
			if(right<=left+1)
				break;
			mid=(right+left)/2;
			if(x[mid]<=rightx)
				left=mid;
			else
				right=mid;
		}
		aft=min(n-1,mid+1);
		int ans=0;
		for(int i=bef;i<=aft;i++){if(x[i]>=leftx&&x[i]<=rightx&&y[i]>=lefty&&y[i]<=righty)ans++;}
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 1204
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) begin(x), end(x)
using namespace std;
typedef long long ll;
typedef pair <int,int> P;

int main(){
  int h,w,k;
  cin>>h>>w>>k;
  char c[10][10];
  int ans=0;
  rep(i,h) rep(j,w){
    cin>>c[i][j];
  }
  rep(bits1,1<<h){
    rep(bits2,1<<w){
      int cnt=0;
      rep(i,h){
	rep(j,w){
	  if(!((bits1>>i)&1) || !((bits2>>j)&1)) continue;
	  if(c[i][j]=='#') {
	    cnt++;
	  }
	}
      }
      if(cnt==k) {
	ans++;
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}


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

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(lol i=0;i<lol(n);i++)
#define REPD(i,n) for(lol i=n-1;i>=0;i--)
#define FOR(i,a,b) for(lol i=a;i<=lol(b);i++)
#define FORD(i,a,b) for(lol i=a;i>=lol(b);i--)
#define VL vector<lol>
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() //sortなどの引数を省略したい
#define SIZE(x) lol(x.size()) //sizeをsize_tからllに直しておく
//定数
#define PI 3.1415926535897932385 //pi
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//最大値最小値
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; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main()
{
    lol result{0};
    lol n; cin >> n;
    VL a(n);
    REP(i, n)
    {
        cin >> a[i];
    }
    sort(ALL(a));
    FOR(i, 0, n-3)
    {
        FOR(j, i, n-2)
        {
            FOR(k, j, n-1)
            {
                if((a[i] != a[j] && a[j] != a[k] && a[k] != a[i]) && (a[i] + a[j] > a[k]))
                    result++;
            }
        }
    }

    cout << result << endl;
    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;

int main(int argc, const char * argv[]) {
    int x;
    cin >> x;
    if (x < 1200) {
        cout << "ABC" << endl;
    }else{
        cout << "ARC" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    long N;
    long W;
    long w;
    long v;
    cin >> N >> W;
    vector<long> w_ls(N);
    vector<long> v_ls(N);
    vector<vector<long>> memo_ls(N+1);
    for(int i=0; i<N;i++){
        cin >> w >> v;
        w_ls[i] = w;
        v_ls[i] = v;
    }
    for(int i=0; i< W + 1; i++){
        memo_ls[0].push_back(0);
    }
    for(int i=1; i<N+1; i++){
        memo_ls[i].push_back(0);
        for(int j=1; j<W+1; j++){
            if(j >= w_ls[i-1]){
                memo_ls[i].push_back(max({memo_ls[i-1][j], memo_ls[i-1][j-w_ls[i-1]] + v_ls[i-1], memo_ls[i][j-1]}));
            }
            else{
                memo_ls[i].push_back(max({memo_ls[i-1][j], memo_ls[i][j-1]}));
            }
        }
    }
    cout << memo_ls[N][W] << endl;
}



Measured memory_bytes: 80120
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define f(i,j,n)  for(int i=j;i<=n;i++)
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,k=0,s=0;
    cin>>n;
    int a[n];
    f(i,0,n-1)
      {cin>>a[i];}
      
    sort(a,a+n,greater<int>());
    
    f(i,0,n-1)
    { if((i+1)%2==0)
       s=s+a[i];
     else
       k=k+a[i];
    }   
    cout<<k-s;
}   
    
    
     

     
   





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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;

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

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

int bitCount(long bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    string ans = "";
    int cnt[n][26];
    rep (i, n) {
      rep (j, 26) {
        cnt[i][j] = 0;
      }
    }
    rep (i, n) {
      string s;
      cin >> s;
      rep (j, s.size()) {
        cnt[i][s[j] - 'a']++;
      }
    }
    rep (j, 26) {
      int tmp = Inf;
      rep (i, n) {
        tmp = min(tmp, cnt[i][j]);
      }
      rep (i, tmp) {
        ans += 'a' + j;
      }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
int n[28],i,a=0,b=0,j,flag;
for(i=0;i<28;i++){
scanf("%d\n",&n[i]);
}
for (i=1;i<=30;i++){
 
for (j=0;j<28;j++){
if(n[j]==i)flag=1;
}
 
if(flag==0){
if(a==0)a=i;else b=i;
}else{
flag=0;
}
 
}
printf("%d\n%d\n",a,b);
return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair

using namespace std;

const int N=1e5+5;
int n,m,a[N];

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int res=-1;
    for(int i=1;i<=100;i++)
    {
        int cost=0;
        for(int j=1;j<=n;j++) cost+=(a[j]-i)*(a[j]-i);
        if(res==-1||cost<res) res=cost;
    }
    cout<<res;
}


Measured memory_bytes: 256
//Utkarsh.25dec
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define vi vector <int>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define deb(x) cerr<<#x<<' '<<'='<<' '<<x<<'\n'
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val)  no. of elements strictly less than val
// s.find_by_order(i)  itertor to ith element (0 indexed)
typedef vector<vector<ll>> matrix;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
void solve()
{
    ll n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            for(int k=0;k<15;k++)
            {
                if((i&(1<<k))!=(j&(1<<k)))
                {
                    cout<<k+1<<' ';
                    break;
                }
            }
        }
        cout<<'\n';
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T=1;
    //cin>>T;
    int t=0;
    while(t++<T)
    {
        //cout<<"Case #"<<t<<":"<<' ';
        solve();
        //cout<<'\n';
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Measured memory_bytes: 15548
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <queue>
using ll=long long;
using namespace std;

int main(){
    int N,K;
    cin>>N>>K;

    vector<pair<int,int>> L;
    int a,b;
    for(int i=0;i<K;i++){
        cin>>a>>b;
        L.push_back({a,b});
    }


    ll mod=998244353;
    vector<ll> dp(N+1,0);
    dp[1]=1;
    ll sum=0;
    priority_queue<pair<int,ll>,vector<pair<int,ll>>,greater<pair<int,ll>>> q;

    for(int i=1;i<=N;i++){
        //cout<<i<<endl;
        while(!q.empty() && q.top().first==i){
            sum+=q.top().second;
            sum%=mod;
            q.pop();
        }
        //cout<<i<<endl;
        dp[i]+=sum;
        for(int j=0;j<K;j++){
            q.push({i+L[j].first,dp[i]});
            q.push({i+1+L[j].second,-1*dp[i]});
        }
    }

    cout<<dp[N]<<endl;

    return 0;
}

Measured memory_bytes: 70572
use std::io::{stdin, Read};

#[allow(unused_macros)]
macro_rules! parse {
    ($it: ident ) => {};
    ($it: ident, ) => {};
    ($it: ident, $var:ident : $t:tt $($r:tt)*) => {
        let $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
    ($it: ident, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
}

#[allow(unused_macros)]
macro_rules! parse_val {
    ($it: ident, [$t:tt; $len:expr]) => {
        (0..$len).map(|_| parse_val!($it, $t)).collect::<Vec<_>>();
    };
    ($it: ident, ($($t: ty),*)) => {
        ($(parse_val!($it, $t)),*)
    };
    ($it: ident, $t: ty) => {
        $it.next().unwrap().parse::<$t>().unwrap()
    };
}

fn solve(s: &str) {
    let s = s.split_whitespace().next().unwrap();
    let s: Vec<bool> = s
        .chars()
        .map(|x| x.to_digit(10).unwrap())
        .map(|x| x != 0)
        .collect();
    let n = s.len();
    if !s[0] || s[n - 1] {
        println!("{}", -1);
        return;
    }
    let mut nexts = vec![vec![]; n];
    nexts[0].push(1);
    let mut cur = 1;
    for i in 1..(s.len() - 1) {
        if s[i] != s[n - i - 2] {
            println!("{}", -1);
            return;
        }
        nexts[cur].push(i + 1);
        if s[i] {
            cur = i + 1;
        }
    }
    let mut count = 0;
    for i in 0..n {
        for &j in nexts[i].iter() {
            println!("{} {}", i + 1, j + 1);
            count += 1;
        }
    }
    assert_eq!(count, n - 1)
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    solve(&s);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_input() {
        let s = "
        ";
        solve(s);
    }
}


Measured memory_bytes: 11644
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {
    public static void main(String[] args) {
        FastScanner fsc = new FastScanner();
        int n = fsc.nextInt();
        int[] cnt = new int[3];
        for (int i = 0; i < n; i++) {
            long ai = fsc.nextLong();
            if ((ai & 3) == 0) {
                cnt[2]++;
            } else if ((ai & 1) == 0) {
                cnt[1]++;
            } else {
                cnt[0]++;
            }
        }
        if (cnt[0] > cnt[2]) {
            if (cnt[0] + cnt[2] == n && cnt[0] == cnt[2] + 1) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        } else {
            System.out.println("Yes");
        }
    }
}


class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte()) {
            return buffer[ptr++];
        } else {
            return -1;
        }
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
            ptr++;
        }
        return hasNextByte();
    }

    public String next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) {
            throw new NumberFormatException();
        }
        return (int) nl;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}


Measured memory_bytes: 23124
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <iostream>
using namespace std;

int long cnt = 0;

void merge(int a[], int left, int mid, int right);
void mergeSort(int a[], int left, int right);

int main(void)
{
	int n;
	cin >> n;
	int *a = new int[n];
	for (int i = 0; i < n; i++) cin >> a[i];

	mergeSort(a, 0, n - 1);

	cout << cnt << endl;

	delete[] a;
	return 0;
}


void merge(int a[], int left, int mid, int right)
{
	int n1 = mid - left + 1;
	int n2 = right - (mid + 1) + 1;
	int *l = new int[n1 + 1];
	int *r = new int[n2 + 1];
	for (int i = 0; i <= n1; i++) l[i] = a[left + i];
	for (int i = 0; i <= n2; i++) r[i] = a[(mid + 1) + i];
	l[n1] = 1000000000;
	r[n2] = 1000000000;

	int i = 0, j = 0;
	for (int k = left; k <= right; k++) {
		if (l[i] <= r[j]) {
			a[k] = l[i];
			i++;
			cnt += j;
		}
		else {
			a[k] = r[j];
			j++;
		}
	}
	delete[] l, r;
}

void mergeSort(int a[], int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;
		mergeSort(a, left, mid);
		mergeSort(a, mid + 1, right);
		merge(a, left, mid, right);
	}
}

Measured memory_bytes: 16144
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000007;
int main(){

  //input
  int N,W;
  cin >> N >> W;
  int A[N],B[N];
  for(int i=0;i<N;i++) cin >> A[i] >> B[i];
  
  //dp_setup
  //define:dp[i][j]=i番目までで価値j以上の最小重量
  long long dp[N+1][100001];
  for(int i=0;i<N+1;i++) for(int j=0;j<100001;j++) dp[i][j]=INF;
  dp[0][0]=0;
  
  //dp_onwork
  for(int i=0;i<N;i++){
    for(int j=0;j<100001;j++){
      dp[i+1][j]=min(dp[i][j],dp[i][max(0,j-B[i])]+A[i]);
    }
  }
  
  //output
  for(int i=100000;i>-1;i--){
    if(dp[N][i]<=W){
      cout << i << endl;
      break;
    }
  }

}

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

using namespace std;

using ll = long long;

string Solve() {
    int n, m;
    cin >> n >> m;

    array<int, 10> s = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};
    vector<int> a(m);
    for (int i = 0; i < m; ++i) cin >> a[i];
    sort(a.begin(), a.end(), greater<int>());

    vector<int> dp(n + 1, -1);
    dp[0] = 0;
    for (int i = 0; i <= n; ++i) {
        if (dp[i] == -1) continue;
        for (auto d : a) {
            if (s[d] + i <= n)
                dp[s[d] + i] = max(dp[s[d] + i], dp[i] + 1);
        }
    }

    int num = n;
    string res;
    while (0 < num) {
        for (auto d : a)
            if (0 <= num - s[d] && dp[num] == dp[num - s[d]] + 1) {
                res += string(1, (char)(d + '0'));
                num -= s[d];
                break;
            }
    }

    return res;
}

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

    cout << Solve() << endl;

    return 0;
}


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

#ifdef LOCAL
#define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define DEBUG(...) 6;
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
template<typename T> void debug(string s, T x) {cerr << s << " = " << x << "\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...);}

bool vis[100005];
vector<int> adj[100005];

void dfs(int u) {
    vis[u] = true;
    for (int v : adj[u])
        if (!vis[v])
            dfs(v);
}

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

    int n, m;
    cin >> n >> m;
    for (int i=0; i<m; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    int comp = 0;
    for (int i=0; i<n; i++)
        if (!vis[i]) {
            comp++;
            dfs(i);
        }
    cout << comp - 1 << "\n";

    return 0;
}

Measured memory_bytes: 9644
#include <stdio.h>
#include <string.h>
#include <math.h>
int main(void){
    
    int n;
    int k;
    int q;
    int a[199999];
    int b[199999]={};
    int tmp=0;
    
    scanf("%d %d %d", &n, &k, &q);
    
    for(int i=1; i<=q; i++){
        
        scanf("%d", &a[i]);
        tmp = a[i];
        b[tmp] += 1;
        
    }
    
    for(int j=1; j<=n; j++){
        
        if(b[j]>=q-k+1){
            
            printf("Yes\n");
            
        } else {
            
            printf("No\n");
            
        }
        
    }
    
    return 0;
    
}

Measured memory_bytes: 1664
inpl = lambda: list(map(int,input().split()))
N = int(input())
A = inpl()
H = sum(A)/2
s = 0
for i in range(N):
    t = s + A[i]
    if t >= H:
        break
    else:
        s = t
print(int(min(t-H,H-s)*2))

Measured memory_bytes: 88272
using System;
using System.Collections.Generic;

namespace ConsoleApp_CS
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = CIn.ReadIntArray(2);
            foreach(var item in n)
            {
                if (item > 9)
                {
                    Console.WriteLine(-1);
                    return;
                }
            }
            Console.WriteLine(n[0] * n[1]);
            
        }
    }

    class CIn
    {
        private static readonly Queue<string> fieldBuffer = new Queue<string>();

        public static string Read()
        {
            if (fieldBuffer.Count == 0)
            {
                foreach (var field in Console.ReadLine().Split())
                {
                    fieldBuffer.Enqueue(field);
                }
            }
            return fieldBuffer.Dequeue();
        }

        public static int ReadInt() => int.Parse(Read());
        public static long ReadLong() => long.Parse(Read());
        public static double ReadDouble() => double.Parse(Read());

        public static string[] ReadStringArray(long n)
        {
            var array = new string[n];
            for (var i = 0; i < n; i++)
            {
                array[i] = Read();
            }
            return array;
        }

        public static int[] ReadIntArray(long n)
        {
            var array = new int[n];
            for (var i = 0; i < n; i++)
            {
                array[i] = ReadInt();
            }
            return array;
        }

        public static long[] ReadLongArray(long n)
        {
            var array = new long[n];
            for (var i = 0; i < n; i++)
            {
                array[i] = ReadLong();
            }
            return array;
        }

        public static double[] ReadDoubleArray(long n)
        {
            var array = new double[n];
            for (var i = 0; i < n; i++)
            {
                array[i] = ReadDouble();
            }
            return array;
        }
    }
}


Measured memory_bytes: 13268
import java.io.PrintWriter
import java.util.*
import java.math.*

val pw = PrintWriter(System.out)

fun main(args: Array<String>) {
    val (n, k) = readListOfInt()

    var a: Long = 0
    var b: Long = 0
    for(i in 1..n) {
        if(i * 2 % k == 0) {
            if(i % k == 0) {
                a++
            } else {
                b++
            }
        }
    }
    val ans = a * a * a + b * b * b
    println(ans)
    pw.flush()
}

fun inputList() = 
readLine()!!.split(" ").map(String::toInt)

fun sum_digits(num_: Long): Long {
    var num = num_
    var rtn: Long = 0
    while(num != 0.toLong()) {
        val tmp = num % 10
        rtn += tmp
        num /= 10
    }
    return rtn
}

/****** Decrared Functions ******/

// IO
fun read() = readLine()!!
fun readInt() = read().toInt()
fun readLong() = read().toLong()
fun readDouble() = read().toDouble()
fun readListOfString() = read().split(" ")
fun readListOfInt() = readListOfString().map { it.toInt() }
fun readListOfLong() = readListOfString().map { it.toLong() }
fun readListOfDouble() = readListOfString().map { it.toDouble() }


fun println(value : Any) {
    pw.println(value)
}

fun gcd(a: Long, b: Long): Long = 
if(b != 0L) a else gcd(b, a % b)

fun lcm(a: Long, b: Long) = 
if(b==0L) a else gcd(b, a % b)


Measured memory_bytes: 37748
#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>

using namespace std;

#define sz(a) static_cast<int>((a).size())
#define f first
#define s second
#define els(v) for (auto &el : (v))


#ifdef KIRYA
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...)
#endif

template<typename T>
void _dbg(const char* _s, T _h) {
    cerr << _s << " = " << _h << "\n";
}

template<typename T, typename... Ts>
void _dbg(const char*_s, T _h, Ts... _t) {
    int _b = 0;
    
    while (((_b += *_s == '(') -= *_s == ')') != 0 || *_s != ',')
        cerr << *_s++;
    
    cerr << " = " << _h << ",";
    _dbg(_s + 1, _t...);
}

const int64_t INF = static_cast<int64_t>(1e9) + 7;
const int64_t LINF = INF * INF;
const int MAXN = static_cast<int>(1e6) + 17;

void solve() {
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    if (s[0] == s[1] && s[1] != s[2] && s[2] == s[3]) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);
    
    int q = 1;

    for (int i = 0; i < q; ++i) {
        solve();
    }
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int coun[105][105][105];
vector<int>x,y,z;
int rx[52][2], ry[52][2], rz[52][2];
int a[52],b[52],c[52],d[52],e[52],f[52];
int n,m;

int compress1(){
	sort(x.begin(), x.end());
	x.erase(unique(x.begin(), x.end()), x.end());
	for(int i = 0;i < n;i++){
		rx[i][0] = find(x.begin(),x.end(),a[i])-x.begin();
		rx[i][1] = find(x.begin(),x.end(),d[i])-x.begin();
	}
	return 0;
}

int compress2(){
	sort(y.begin(), y.end());
	y.erase(unique(y.begin(), y.end()), y.end());
	for(int i = 0;i < n;i++){
		ry[i][0] = find(y.begin(),y.end(),b[i])-y.begin();
		ry[i][1] = find(y.begin(),y.end(),e[i])-y.begin();
	}
	return 0;
}

int compress3(){
	sort(z.begin(), z.end());
	z.erase(unique(z.begin(), z.end()), z.end());
	for(int i = 0;i < n;i++){
		rz[i][0] = find(z.begin(),z.end(),c[i])-z.begin();
		rz[i][1] = find(z.begin(),z.end(),f[i])-z.begin();
	}
	return 0;
}

int main()
{
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%d %d %d %d %d %d",&a[i],&b[i],&c[i],&d[i],&e[i],&f[i]);
		x.push_back(a[i]);
       x.push_back(d[i]);
       y.push_back(b[i]);
       y.push_back(e[i]);
       z.push_back(c[i]);
       z.push_back(f[i]);
	}
	compress1();
	compress2();
	compress3();
	for(int i = 0;i < n;i++){
	for(int tx=rx[i][0];tx<rx[i][1];tx++)
    {
      for(int ty=ry[i][0];ty<ry[i][1];ty++)
        {
          for(int tz=rz[i][0];tz<rz[i][1];tz++)
        {
          coun[tx][ty][tz]++;
        }
        }
    }
	}
  long long ans=0;
  for(int i=0;i<=100;i++)
    {
      for(int j=0;j<=100;j++)
    {
      for(int k=0;k<=100;k++)
        {
          if(coun[i][j][k]>=m)
        {
          long long s1=(x[i+1]-x[i]),s2=(y[j+1]-y[j]),s3=(z[k+1]-z[k]);
          ans+=s1*s2*s3;
        }
        }
    }
    }
	//long long ans = 0;
	printf("%lld\n",ans);
	return 0;
}

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

using namespace std;

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

    int ans = 0;

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '+') {
            ans++;
        } else {
            ans--;
        }
    }

    cout << ans << endl;
}


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

void fnInput(int& rnSpcNum, int& rnMinSum, int& rnMaxSum)
{
  cin >> rnSpcNum >> rnMinSum >> rnMaxSum;
}

void fnSomeSums(int nSpcNum, int nMinSum, int nMaxSum, int& rnTotal)
{
  for (int n = 1; n <= nSpcNum; n++)
  {
    int nPlaceSum = 0;
    int nNum = n;
    while ( nNum )
    {
      nPlaceSum += nNum % 10;
      nNum /= 10;
    }

    if (nMinSum <= nPlaceSum && nPlaceSum <= nMaxSum)
      rnTotal += n;
  }
}

int main()
{
  int nSpcNum, nMinSum, nMaxSum;
  int nTotal = 0;

  fnInput(nSpcNum, nMinSum, nMaxSum);
  fnSomeSums(nSpcNum, nMinSum, nMaxSum, nTotal);
  cout << nTotal << endl;

  return 0;
}
 

Measured memory_bytes: 256
import java.util.*;
public class Main{
	public static void main(String[] args){
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        long k=s.nextInt();
        long[] arr=new long[n];
        
        long i=1;
        long j=0;

        for(int l=0;l<n;l++){
            arr[l]=s.nextInt();
            j=Math.max(j,arr[l]);
        }

        if(k==0){
            System.out.println(j);
            return;
        }

        long ans=j;
        while(i<=j){
            long mid=(i+j)/2;
            if(isPossible(arr,mid,k)){
                ans=mid;
                j=mid-1;
            }else{
                i=mid+1;
            }
        }

        System.out.println(ans);



    }

    public static boolean isPossible(long[] arr,long res,long k){
        
        long count=0;
        for(int i=0;i<arr.length;i++){
            if(arr[i]<=res){

            }else{
                long nc=arr[i]/res;
                if(arr[i]%res==0){
                    nc--;
                }
                count=count+nc;
                if(count>k){
                    return false;
                }
            }
        }
        return true;
    }
}

Measured memory_bytes: 60956
fn main() {
    let n:usize = io::readln();
    let a:Vec<i32> = io::read_line().split_whitespace().map(|a| a.parse().unwrap()).collect();
    println!("{}", a.iter().max().unwrap() - a.iter().min().unwrap())
}

pub mod io {
    use std::io;

    pub fn read_line() -> String {
        let mut s = String::new();
        io::stdin().read_line(&mut s).unwrap();
        s.trim_right().to_owned()
    }

    pub fn readln<T: Read>() -> T {
        let mut s = String::new();
        io::stdin().read_line(&mut s).unwrap();
        T::read(s.trim())
    }

    pub trait Read {
        fn read(s: &str) -> Self;
    }

    impl Read for String {
        fn read(s: &str) -> Self {
            s.to_string()
        }
    }

    impl<T: Read> Read for Vec<T> {
        fn read(s: &str) -> Self {
            s.split_whitespace().map(|w| T::read(w)).collect()
        }
    }

    macro_rules !def_read {
        ($t : ty) => {
            impl Read for $t {
                fn read(s : &str)->$t { s.parse().unwrap() }
            }
        }
    }

    macro_rules !def_read_tuple {
        ($($t : ident), *) => {
            impl<$($t : Read + Default), *> Read for ($($t), *) {
                fn read(s : &str)->Self {
                    let mut iter = s.split_whitespace();
                    ($($t::read(iter.next().unwrap())), *)
                }
            }
        };
    }

    def_read!(i32);
    def_read!(i64);
    def_read!(isize);
    def_read!(usize);
    def_read!(f32);
    def_read!(f64);
    def_read_tuple!(T0, T1);
    def_read_tuple!(T0, T1, T2);
    def_read_tuple!(T0, T1, T2, T3);
    def_read_tuple!(T0, T1, T2, T3, T4);
}

Measured memory_bytes: 4352
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()

score = 0
mine = ''
for i, t_ in enumerate(t):
    if t_ == 'r':
        if i >= k:
            if mine[i-k] != 'p':
                score += p
                mine += 'p'
            else:
                mine += '*'
        else:
            score += p
            mine += 'p'
    elif t_ == 's':
        if i >= k:
            if mine[i-k] != 'r':
                score += r
                mine += 'r'
            else:
                mine += '*'
        else:
            score += r
            mine += 'r'
    else:
        if i >= k:
            if mine[i-k] != 's':
                score += s
                mine += 's'
            else:
                mine += '*'
        else:
            score += s
            mine += 's'

print(score)

Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define RFOR(i,a,n) for(ll i=(ll)n-1;i >= (ll)a;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,0,n)
#define ALL(v) v.begin(), v.end()
#define bra(first,second) '(' << first << ',' << second << ')'
ll MOD = 1000000007;
//ll INF = 21474836470000000;
ll INF = 100100100100100100;
long double EPS = 1e-11;
long double PI = 3.141592653589793238;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index){
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<ll>>;

ll N,M;
Graph G(1010);
ll P[1010];
ll d[1010];

void dijkstra(ll s){
    fill(P,P+1010,0);
    fill(d,d+1010,INF);
    d[s] = 0;
    queue<ll> Q;
    Q.emplace(s);
    bool frag = 0;
    while(Q.size()){
        ll x = Q.front();
        Q.pop();
        ll n = G[x].size();
        if(!frag && n == 0) break;
        if(n == 0) continue;
        if(frag && x == s){
            return ;
        }
        frag = 1;
        rep(i,n){
            if(d[G[x][i]] != INF && G[x][i] != s) continue;
            P[G[x][i]] = x;
            d[G[x][i]] = d[x] + 1;
            Q.emplace(G[x][i]);
        }
    }
    d[s] = INF;
    return ;
}

int main(){
    cin >> N >> M;
    rep(i,M){
        ll a,b;
        cin >> a >> b;
        a--;b--;
        G[a].push_back(b);
    }
    vector<ll> ans;
    ll m = INF;
    rep(i,N){
        dijkstra(i);
        if(d[i] != INF && d[i] < m){
            m = d[i];
            ans = vector<ll>();
            ll now = i;
            do{
                ans.emplace_back(now+1);
                now = P[now];
            }while(now != i);
        }
    }
    if(m == INF){
        cout << -1 << endl;
    }else{
        cout << ans.size() << endl;
        rep(i,ans.size()) cout << ans[i] << endl;
    }
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <numeric>
#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG true
#define LL long long
#define Num 1000000007
// sort(a.begin(), a.end(), std::greater<int>());
using namespace std;

int main()
{
    LL int a,ans=0;
    cin >> a;
    REP(i, 1, a+1)
    {
        REP(j, 2, 10)
        {
            long long int b = pow(i, j);
            if(a<b) break;
            else ans= max(ans,b);
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
n = gets.to_i

if n < 2 
  puts 0
else
  if n % 2 != 0
    puts 0
  else
    limit = 5
array = []

while n / limit >= 1
  array.push(limit * 2)
  limit *= 5
end
limit /= 5

sum = 0

array.each do |number|
  sum += n / number
end

puts sum

  end

end


Measured memory_bytes: 1788
#include<iostream>
#include<math.h>

using namespace std;

int main(void){

    int n, count = 0;

    cin >> n;

    for(int i = 1;i <= n;i++){
        if((int(log10(i))+1) % 2 == 1) count++;
    }

    cout << count << endl;

    return 0;
}

Measured memory_bytes: 256
mod = 10**9 + 7

x, y = map(int, input().split())

if (x + y) % 3 != 0:
    print(0)
    exit()

t = (x + y) // 3

x -= t
y -= t


def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

a = cmb(x+y,min(x, y),mod)
print(a)

Measured memory_bytes: 123840
//
// Created by Ильдар Ялалов on 28.10.2019.
//
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <cmath>
#include <queue>
#include <ctime>
#include <map>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf_int = 1e9 + 100;
const ll inf_ll = 1e18;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double dbl;
#define pb push_back
#define eb emplace_back
const double pi = 3.1415926535898;
#define dout if(debug) cout
#define fi first
#define se second
#define sp setprecision
#define sz(a) (int(a.size()))
#define all(a) a.begin(),a.end()
bool debug = 0;
const int MAXN = 1e6 + 100;
const int LOG = 21;
const int mod = 1e9 + 7;
const int MX = (1e7 + 100) * 1.5;
typedef long long li;
const li MOD = 1000000000949747713ll;

template<class T1, class T2>
std::ostream &operator<<(std::ostream &out, const std::pair<T1, T2> &rhs) {
    out << "( " << rhs.first << " , " << rhs.second << " )";
    return out;
}


pll D[MAXN];

int sz[MAXN];

vector<int> g[MAXN];


ll sum  = 0;
void dfs(int v,int p,ll cur){
    sum += cur;
    for(int to:g[v]){
        if(to == p)
            continue;
        dfs(to,v,cur+1);

    }
}
void solve() {
    int n;
    cin >> n;

    map<ll,int> mp;
    for (int i = 1; i <= n; ++i) {
        cin >> D[i].fi;
        D[i].se = i;
        if(mp.count(D[i].fi) == 0){
            mp[D[i].fi] = i;
        }


        sz[i] = 1;
    }
    sort(D+1,D+n+1);

    vector<pii> edges;
    for(int j = n;j > 1;--j){
        int v = D[j].se;
        ll x = D[j].fi - n + 2 * sz[v];
        dout << v << " "<<D[j].fi <<" "<<x <<" : " <<endl;
        if(mp.count(x) == 0){
            cout <<"-1";
            return;
        }

        int to = mp[x];
        if(to == v){
            cout << -1 <<"\n";
            return;
        }
        edges.pb({v,to});

        g[v].pb(to);
        g[to].pb(v);
        sz[to] += sz[v];
    }

    dfs(D[1].se,-1,0);

    if(sum != D[1].fi){
        cout << -1;
        return;
    }
    for(auto x : edges){
        cout << x.fi<<" "<<x.se<<"\n";
    }


}

signed main() {
#ifdef zxc
    debug = 1;
    freopen("../input.txt", "r", stdin);
    //  freopen("../output.txt", "w", stdout);
#else

#endif //zxc
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.setf(ios::fixed);
    cout.precision(20);

    int t = 1;
    while (t--)
        solve();
    if (debug)
        cerr << endl << "time : " << (1.0 * clock() / CLOCKS_PER_SEC) << endl;
}

Measured memory_bytes: 42612