akhauriyash/Code-Regression huggingface dataset:
def min_cost():
    # Minimum cost at position i is minimum of (minimum cost incurred at position i - 1, minimum cost incurred at position i - 2) + absolute value of that position - current position cost
    len_costs = input()
    costs = input().split(' ')
    costs = list(map(int, costs))
    dp = [float('inf') for i in range(len(costs))]
    dp[0] = 0
    for i in range(len(costs)):
        for j in [i + 1, i + 2]:
            if j < len(costs):
                dp[j] = min(dp[j], dp[i] + abs(costs[i] - costs[j]))
    print(dp[-1])
    return dp[-1]

min_cost()
# min_cost([10, 30, 40, 20])
# min_cost([10, 10])
# min_cost([30, 10, 60, 10, 60, 50])


Measured memory_bytes: 20364
#include <bits/stdc++.h>
using namespace std;
int main(void){
    long double a,b,x;
    long double pi=3.141592653589793;
    cin>>a>>b>>x;
    if (x<=a*a*b/2) {
        long double tmp=x*2/(a*b);
        long double ans=acosl(b/sqrt(tmp*tmp+b*b))*(180.0/pi);
        printf("%.10Lf\n",90.0-ans);
    } else {
        long double tmp=(2*a*a*b-2*x)/(a*a);
        long double ans=acosl(a/sqrt(a*a+tmp*tmp))*(180.0/pi);
        printf("%.10Lf\n",ans);
    }
}

Measured memory_bytes: 512
#include <stdio.h>

int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	long long x=0,y=0;
	for(int i=0;i<a;i++){
		int t;
		scanf("%d",&t);
		x+=t;
	}
	for(int i=0;i<b;i++){
		int t;
		scanf("%d",&t);
		y+=t;
	}
	printf("%lld\n",x*y);
}


Measured memory_bytes: 2104
from collections import Counter
N=int(input())
A=list(map(int, input().split()))
for i in range(N):
    A[i]=0 if A[i]>=3200 else A[i]//400+1
print((len(Counter(A))-(0 in Counter(A)))**(len(Counter(A))>(0 in Counter(A))), Counter(A)[0]+(len(Counter(A))-(0 in Counter(A))))


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

//BEGIN CUT HERE
//重み付きUnion_find
//typename Tには重みの型を入力する
template <typename T>
class Potential_UF{
public:
    explicit Potential_UF(int n):size(n){
        Rank.resize(static_cast<unsigned long>(n), 0);
        parent.resize(static_cast<unsigned long>(n));
        weight.resize(n,unity);
        cont.resize(static_cast<unsigned long>(n), 1);
        for(int i=0;i<size;i++){parent[i]=i;}
    }

    //xの属しているグループの番号を返します
    int find(int x) {
        if (parent[x] == x)return x;
        else {
            int r = find(parent[x]);
            weight[x] += weight[parent[x]];
            return parent[x] = r;
        }
    }

    //xにつけられている重みを返します
    T get_weight(int x){
        find(x);
        return weight[x];
    }

    //xとyの重みの差を返します
    //weight(y)-weight(x)
    T diff(int x,int y){
        return get_weight(y)-get_weight(x);
    }

    //xとyが同じグループかどうかの判定をします
    bool same(int x,int y){
        return find(x)==find(y);
    }

    //xとyを同じグループにします
    //既に同じなら何もしません
    //weight(y)-weight(x)==wとなるように構成します
    void Unite(int x,int y,T w){
        w+=get_weight(x);
        w-=get_weight(y);
        x=find(x);
        y=find(y);
        if(x==y)return;
        if(Rank[x]>Rank[y]){
            parent[y]=x;
            weight[y]=w;
            cont[x]+=cont[y];
            cont[y]=0;
        }else{
            parent[x]=y;
            if(Rank[x]==Rank[y])Rank[y]++;
            weight[x]=-w;
            cont[y]+=cont[x];
            cont[x]=0;
        }
    }
    int group_size(int x){
        return cont[find(x)];
    }
    void visual(){
        for(int i=0;i<size;i++)find(i);
        for(int i=0;i<size;i++){
            cout<<"   par["<<i<<"]="<<parent[i]<<",";
        }
        cout<<endl;
        for(int i=0;i<size;i++){
            cout<<"weight["<<i<<"]="<<weight[i]<<",";
        }
        cout<<endl;
        for(int i=0;i<size;i++){
            cout<<"cont["<<i<<"]="<<cont[i]<<",";
        }
        cout<<endl;
    }
private:
    int size;
    const T unity=0;//型Tの単位元
    vector<int> parent;
    vector<int> Rank;
    vector<int> cont;
    vector<T> weight;
};
//END CUT HERE

int main(){
    int n,m;
    cin>>n>>m;
    Potential_UF<ll> uf(n);
    for(int i=0;i<m;i++){
        int l,r,d;cin>>l>>r>>d;
        l--;r--;
        if(uf.same(l,r)){
            if(uf.diff(l,r)!=d){
                cout<<"No"<<endl;
                return 0;
            }
        }else{
            uf.Unite(l,r,d);
        }
        //uf.visual();
    }
    cout<<"Yes"<<endl;
}

Measured memory_bytes: 2176
A,B,C,K=map(int,input().split())

tot=0
all=K

if K-A>=0:
    tot+=A*1
    all-=A
    if all-B>=0:
        tot+=B*0
        all-=B
        if all-C>=0:
            tot+=-1*C
        else:
            tot+=-1*all
    else:
        tot+=0*all
else:
    tot+=1*all
print(tot)

Measured memory_bytes: 9196
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<>();
        int a;
        while (true) {
            int c = 0;
            a = sc.nextInt();
            if (a == 0) break;
            for (int i = 1; i < a; i++) {
                int sum = 0;
                for (int j = i; j < a; j++) {
                    sum += j;
                    if (sum == a) c++;
                }
            }
            list.add(c);
        }
        list.stream().forEach(x -> System.out.println(x));
    }
}



Measured memory_bytes: 32080
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define int long long
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define pb push_back
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef complex<ld> com;
constexpr int inf = 1000000000;
constexpr ll INF = 1000000000000000010;
constexpr ld EPS = 1e-12;
constexpr ld PI = 3.141592653589793238;
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }

struct edge {
	ll to, cost;
};

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);

	int n, m, s;
	cin >> n >> m >> s;
	if (s >= 5000) {
		vector<vector<int>> dis(n, vector<int>(n, INF));
		rep(i, n) dis[i][i] = 0;
		rep(i, m) {
			int u, v, a, b;
			cin >> u >> v >> a >> b; 
			u--; v--;
			chmin(dis[u][v], b); chmin(dis[v][u], b);
		}
		rep(k, n) rep(i, n) rep(j, n) chmin(dis[i][j], dis[i][k] + dis[k][j]);
		for (int i = 1; i < n; i++) cout << dis[0][i] << '\n';
	}
	else {
		vector<int> dis(5000 * n, INF);
		vector<vector<edge>> graph(5000 * n);
		rep(i, s + 1) dis[i] = 0;
		rep(i, m) {
			int u, v, a, b;
			cin >> u >> v >> a >> b;
			u--; v--;
			rep(j, 5000) {
				if (j >= a) {
					graph[u * 5000 + j].pb({ v * 5000 + j - a,b });
					graph[v * 5000 + j].pb({ u * 5000 + j - a,b });
				}
			}
		}
		rep(i, n) {
			int c, d;
			cin >> c >> d;
			rep(j, 5000) {
				if (j + c < 5000) {
					graph[i * 5000 + j].pb({ i * 5000 + j + c,d });
				}
			}
		}
		priority_queue<P, vector<P>, greater<P>> que;
		que.push(P(0, s));
		while (!que.empty()) {
			P p = que.top(); que.pop();
			int pf = p.first; int ps = p.second;
			if (pf > dis[ps]) continue;
			for (edge e : graph[ps]) {
				if (dis[e.to] > dis[ps] + e.cost) {
					dis[e.to] = dis[ps] + e.cost;
					que.push(P(dis[e.to], e.to));
				}
			}
		}
		for (int i = 1; i < n; i++) {
			int ans = INF;
			rep(j, 5000) {
				chmin(ans, dis[i * 5000 + j]);
			}
			cout << ans << '\n';
		}
	}
}

Measured memory_bytes: 44412
#include<iostream>
#include<cstring>
#include<cstdio> 
#define INF 0x3f3f3f3f
 
using namespace std;
 
const int N=20;
int c[N];
int n,m,x;
int a[N][N];
int ans=INF;
int main()
{
	cin>>n>>m>>x;
	for(int i=1;i<=n;i++){
		cin>>c[i];
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<(1<<n);i++){
		int sum=0;//记录每种状态所花的钱 
		int res[N];//记录每种算法掌握程度 
		memset(res,0,sizeof(res));
		for(int j=0;j<n;j++){
			if(i&(1<<j)){//如果选择j+1本书 
				for(int k=1;k<=m;k++){
					res[k]+=a[j+1][k];
				}
				sum+=c[j+1];
			}
		}
		bool flag=0;
		for(int j=1;j<=m;j++){
			if(res[j]<x){
				flag=1;
				break;
			}
		}
		if(!flag) ans=min(sum,ans);
	}
	if(ans==INF) puts("-1");
	else cout<<ans<<endl;	
	return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
 
#define ALL(l)  (l).begin(),(l).end()
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
//const ll mod =  1000000007;
//const ll maxn = 1000000000;

//---------------------------------------------------------------------------------------------------
using vi = vector<int>; // intの1次元の型に vi という別名をつける
using vll = vector<ll>; // intの1次元の型に vi という別名をつける
using vvll = vector<vll>; // intの2次元の型に vvi という別名をつける
using vs = vector<string>; // stringの1次元の型に vs という別名をつける
using pll = pair<ll, ll>; // これ以降 pii という型名はpair<ll, ll> と同じ意味で使える
//---------------------------------------------------------------------------------------------------

int main(){
    ll n,ans=1;
    cin>>n;
    ll max_h;
    cin>>max_h;
    rep(i,n-1){
        ll h;
        cin>>h;
        if(h>=max_h){
            ans++;
            max_h=h;
        }
    }
    cout<<ans<<endl;
}
   



Measured memory_bytes: 256
fun main(args: Array<String>) {
    readStringList().reversed().joinToString("").let { println(it) }
}

fun readInteger() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntegerArray() = readStringList().map(String::toInt).toIntArray()
fun readLongArray() = readStringList().map(String::toLong).toLongArray()


Measured memory_bytes: 38188
#include <iostream>
#include <string>
#include <algorithm> 
#include <cstdlib>
#include <map>
#include <queue>
#include <vector>
#include <utility>
#include <climits>
#include <numeric>
#define ll long long
#define INF INT_MAX 
using namespace std;
int main(){
	int N,K;
	cin >> N >> K;
	int a[N];
	for(int i=0;i<N;i++)cin >> a[i];
	int i;
	while(1){
		if(K+(K-1)*(i-1)>=N){
			cout << i << endl;
			return 0;
		}
		i++;
	}
}

Measured memory_bytes: 640
N, W = map(int, input().split())
w_v = [list(map(int, input().split())) for _ in range(N)]


# 1~i-1番目の品物から重さの総和がj以下になるように選んだときの価値
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(N):
    w, v = w_v[i]
    for j in range(W+1):
        if j - w >= 0:
            dp[i+1][j] = max(dp[i][j-w]+v, dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

print(max(dp[N]))





Measured memory_bytes: 171656
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vii;
typedef vector<pair<int,int>> vip;

#define ZOOM ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define ff it->first
#define ss it->second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(auto i=0;i<n;++i)
#define LOOP_IT(it,s) for(auto it=(s).begin();it!=(s).end();++it)


#ifdef LOCAL
#define cerr cout
#else
#endif

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif


void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif


int main(int argc,char* argv[])
{
    ZOOM

    ll n;
    ll sum=0;
    cin>>n;
    for(ll i=1;i<=n;++i){
        if(i%5!=0&&i%3!=0)
            sum+=i;
    }
    cout<<sum;



    return 0;
}



Measured memory_bytes: 3616
N,Q = map(int, input().split())

S = list(input())

ansList=[0]
ans=0
for i in range(N-1):
  if S[i] =="A" and S[i+1] =="C":
      ans+=1
      ansList.append(ans)
  else:
    ansList.append(ans)

for i in range(Q):
  l,r = map(int, input().split())
  print(ansList[r-1]-ansList[l-1])


Measured memory_bytes: 6872
/* AUTHOR: Naman */
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long
#define deb(x) cout << #x << "=" << x << endl
#define IOS     ios_base::sync_with_stdio(0); cin.tie(NULL);
const ll N=2*1e6+1;
ll M=998244353;
int main() {
	IOS
    ll t=1;
	//cin>>t;	
	
	for(ll _=1;_<=t;_++)
	{
	   //cout<<"Case #"<<_<<": ";
	    ll i,n,k;	
	    cin>>n>>k;
	    
	    ll rg[k+1][2];
	    for(i=1;i<=k;i++)cin>>rg[i][0]>>rg[i][1];
        
        ll dp[n+2];
        
        memset(dp,0,sizeof(dp));
        dp[1]=1;
        dp[2]=-1;
        for(i=1;i<=n;i++)
        {   
            dp[i]+=dp[i-1];
            dp[i]%=M;
            for(ll j=1;j<=k;j++)
            {    
                if(i+rg[j][0]>n)continue;
                dp[i+rg[j][0]]+=dp[i];
                 dp[i+rg[j][0]]%=M;
                dp[min(n,i+rg[j][1])+1]-=dp[i];
                 dp[min(n,i+rg[j][1])+1]=(dp[min(n,i+rg[j][1])+1]+M)%M;
            }
              //for(ll i=1;i<=n+1;i++)cout<<dp[i]<<" ";
              //cout<<endl;
        }
       
        //for(i=2;i<=n;i++)dp[i]=(dp[i]+dp[i-1]);
        //for(ll i=1;i<=n;i++)cout<<dp[i]<<" ";
         //cout<<endl;
        cout<<dp[n];
        
	   
	   


	   cout<<endl;
	   
	}
	
    
}

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

using namespace std;

typedef long long ll;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    if (s[0] != 'A') cout << "WA", exit(0);
    int t = 0;
    for (int i = 2; i + 1 < s.size(); i++) if (s[i] == 'C') t++;
    int tr = 0;
    for (int i = 1; i < s.size(); i++) if (s[i] >= 'A' && s[i] <= 'Z') tr++;
    if (t == 1 && tr == 1) cout << "AC";
    else cout << "WA";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << endl;
#define CFYN(n) cout << ( (n) ? "YES":"NO") << endl;
using ll = long long;
using ull = unsigned long long;


int main(void)
{
    IOS
    int n; cin >> n;
    vector<string> v(n);
    map<string,ll> m;
    REP(i,n)  {
        cin >> v[i];
        sort(ALL(v[i]));
    }
    
    ll ans = 0;

    REP(i,n) {
        m[v[i]]++;
        ans += m[v[i]]-1;
    }

    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 16640
N = int(input())
C,S,F = [],[],[]
for i in range(N-1):
  Ci,Si,Fi = map(int,input().split())
  C.append(Ci)
  S.append(Si)
  F.append(Fi)
t = [0]*N

for i in range(N): #駅iから発車した列車が駅jに着いた
  for j in range(i, N-1):
    if t[i] % F[j] == 0 and t[i] >= S[j]:
      t[i] += C[j]
    elif t[i] < S[j]:
      t[i] = S[j]+C[j]
    elif t[i] >= S[j]:
      t[i] = ((t[i]-S[j])//F[j]+1)*F[j]+S[j]+C[j]
  print(t[i])
#    if j+1 == N:
#      break
#    train(i,j+1)

Measured memory_bytes: 3188
#include<cstdio>
#include<iostream>
#include<fstream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define Set(a) memset(a,0,sizeof(a))
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define openf(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define re register
#define ri re int
#define il inline
typedef long long ll;
typedef unsigned long long ull;
template<typename T> inline T rd(T& x)
{
	T f=1;x=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(T)(c-'0');
	x*=f;
	return x;
}
ll rd(){ll x;rd(x);return x;}
//inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
const int inf=1<<30;

const int N=200020;
ll a[N],_ls[N],rs[N];ll*ls=_ls+5;
int main()
{
	int n=rd();
	F(i,1,n) rd(a[i]);
	F(i,1,n) ls[i]=ls[i-2]+a[i];
	//F(i,1,n) cout<<ls[i]<<' ';cout<<endl;
	UF(i,n,1) rs[i]=rs[i+2]+a[i];
	//F(i,1,n) cout<<rs[i]<<' ';cout<<endl;
	ll ans=-300000000000000ll;
	F(i,0,n/2) ans=max(ans,ls[2*(n/2-i)-1]+rs[n-2*(i-1)]);
	//cout<<ans<<endl;
	if(n&1)
	{
		ll tmp=300000000000000ll;
		ll f=300000000000000ll;
		//F(i,0,n) cout<<ls[i]-ls[i-1]<<' ';cout<<endl;
		F(i,1,n)
		{
			if(i&1) {f=min(f,tmp+ls[i]-ls[i-1]);tmp=min(tmp,ls[i-1]-ls[i-2]);}
			//cout<<tmp<<' '<<f<<endl;
		}
		ans=max(ans,ls[n]-f);
	}
	cout<<ans<<endl;
	return 0;
}
////////////////

Measured memory_bytes: 8304
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    N=n*(n+1)//2

    if(sum(A)%N):
        print("NO")
        return

    k=sum(A)//N
    C=[None]*n
    for i in range(n):
        if((k-(A[(i+1)%n]-A[i]))%n):
            print("NO")
            return
        C[i]=(k-(A[(i+1)%n]-A[i]))//n

    print("YES" if(sum(C)==k and all(0<=c<=k for c in C)) else "NO")
resolve()

Measured memory_bytes: 62704
import java.util.*;
import java.io.*;
import java.lang.*;

public class Main{
public static void main(String[] args) throws FileNotFoundException, IOException {
        Scanner s = new Scanner(System.in);
        StringBuilder sb=new StringBuilder();
       int n=s.nextInt(),m=s.nextInt(),l=s.nextInt();
       long[][] g1=new long[n+1][n+1];
       for(int i=1;i<=n;i++){
       	Arrays.fill(g1[i],(long)1e13);
       }
       for(int i=0;i<m;i++){
       	int x=s.nextInt(),y=s.nextInt(),c=s.nextInt();
       	g1[x][y]=c;  
       	g1[y][x]=c;  
       }

       for(int i=0;i<n;i++){
       	g1[i][i]=0;
       }

       	for(int k=1;k<=n;k++){
       		for(int i=1;i<=n;i++){
       			for(int j=1;j<=n;j++){
       				g1[i][j]=Math.min(g1[i][j],g1[i][k]+g1[k][j]);
       			}
       		}
       	} 
        long[][] g2=g1.clone();
        for(int i=1;i<=n;i++){
        	for(int j=1;j<=n;j++){
        		g2[i][j]=g1[i][j]<=l? 1:(long)1e13;
        	}
        }

        for(int k=1;k<=n;k++){
       		for(int i=1;i<=n;i++){
       			for(int j=1;j<=n;j++){
       				g2[i][j]=Math.min(g2[i][j],g2[i][k]+g2[k][j]);
       			}
       		}
       	} 

        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        List<Integer>l1=new ArrayList<>();
        int q=s.nextInt();
        for(int i=0;i<q;i++){
        	int start=s.nextInt(),end=s.nextInt();
        	if(g2[start][end]==(long)1e13){
        		l1.add(-1);
        	}
        	else{
        		l1.add((int)g2[start][end]-1);        	
        	}
        }
        for(int i=0;i<l1.size();i++){
        	out.write(l1.get(i)+" ");
        	out.write('\n');
        	out.flush();
        }
    }
}
    
  












Measured memory_bytes: 93304
#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;
  
  
int main(){
	string str;
	int i,j=0;
	cin>>str;
	FOR(i,0,7){
		if(str[i]=='A'){
			if(str[i+1]=='C'){
			j=1;
				break;
			}
		}
	}
	if(j==0){
	cout<<"No"<<endl;
	}else cout<<"Yes"<<endl;

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdbool.h>

int main(){
   int x,y,buf;
   while(true){
       scanf("%d %d",&x,&y);
       if(x==0 && y==0) break;
       if(x>y){
           buf=x;
           x=y;
           y=buf;
       }
       printf("%d %d\n",x,y);
   }
   return 0;
}


Measured memory_bytes: 2108
using System;

namespace ITP1_8_D
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = Console.ReadLine();
            string t = Console.ReadLine();
            Console.WriteLine(Contains(s, t) ? "Yes" : "No");
        }

        static bool Contains(string s,string t)
        {
            int lenS = s.Length;
            int lenT = t.Length;
            s += s;
            for (int i = 0; i < lenS; i++)
            {
                if (s.Substring(i, lenT) == t)
                    return true;
            }
            return false;
        }
    }
}

Measured memory_bytes: 8900
// B.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

int main(int argc, char *argv[]) {
	int n, ans = 0;
	cin >> n;
	vector<int> a(n), c(n - 1);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	for (int i = 0; i < n; ++i) {
		int b;
		cin >> b;
		ans += b;
	}
	for (int i = 0; i < n - 1; ++i) {
		cin >> c[i];
	}
	for (int i = 0; i < n - 1; ++i) {
		if (a[i] + 1 == a[i + 1]) {
			ans += c[a[i] - 1];
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>

#define PI 3.14159265359

int main() {
	int n, i, s[1000];
	double m = 0, sum;
	while(1) {
		scanf("%d", &n);
		if(n == 0) break;
		sum = 0;
		m = 0;
		for(i = 0; i < n; ++i) {
			scanf("%d", &s[i]);
			m += (double)s[i];
		}
		if(n == 1) {
			printf("0\n");
			for(i = 0; i < n; ++i) s[i] = 0;
			continue;
		}
		m /= (double)n;
		for(i = 0; i < n; ++i) {
			sum += pow(s[i] - m , 2.0);
			// printf("%f\n", sum);
		}
		sum /= (double)n;
		printf("%f\n", sqrt(sum));

		for(i = 0; i < n; ++i) s[i] = 0;
	}
	return 0;
}


Measured memory_bytes: 2148
N = int(input())
L = list(map(int,input().split()))
while True:
  if len(L) == 1:
    print(L[0])
    quit()
  L = sorted(L)
  m = L[0]
  for i in range(1,len(L)):
    L[i] %= m
  L = list(filter(lambda x:x!=0,L))  

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

int main()
{
  string sa,sb,sc,ans, next="a";
  cin >> sa >> sb >> sc;
  while(true){
    if(next=="a"){
      if(sa==""){
	ans="A";
        break;
      }
      next = sa[0];
      sa.erase(sa.begin());
    }
    if(next=="b"){
       if(sb==""){
          ans="B";
          break;
        }
      next = sb[0];
      sb.erase(sb.begin());
    }
    if(next=="c"){
      if(sc==""){
        ans="C";
        break;
      }
      next = sc[0];
      sc.erase(sc.begin());
    }
  }
  cout<< ans  <<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
bool prime(int n){
  if(n==2){
    return true;
  }
  if(n%2==0){
    return false;
  }
  for(int i=3;i*i<=n;i+=2){
    if(n%i==0){
      return false;
    }
  }
  return true;
}

int main(){
  int x;
  cin >> x;
  int ans;
  for(int i=x;i<2*x;i++){
    if(prime(i)){
      ans=i;
      break;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cassert>
#include <ctime>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

#define all(x) (x).begin(), (x).end()

#ifdef LOCAL
#define dbg(x) cerr << #x " = " << x << endl;
#define idbg(x) #x " = " << x
#include "pretty_print.h"
#else
#define dbg(x)
#define idbg(x) ""
#endif

#ifdef _WIN32
#  define LLD "%I64d"
#else
#  define LLD "%lld"
#endif

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;

template <typename T> T sqr(T x) { return x * x; }
template <typename T> T abs(T x) { return x < 0? -x : x; }
template <typename T> T gcd(T a, T b) { return b? gcd(b, a % b) : a; }
template <typename T> bool chmin(T &x, const T& y) { if (x > y) { x = y; return true; } return false; }
template <typename T> bool chmax(T &x, const T& y) { if (x < y) { x = y; return true; } return false; }


int main(int /* argc */, char** /* argv */)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifdef LOCAL
    assert(freopen("inp", "r", stdin));
    assert(freopen("out", "w", stdout));
    #endif

    int n;
    while (cin >> n) {
        auto a = vector<vector<int>> (n, vector<int>(n, 0));
        auto b = vector<vector<int>> (n, vector<int>(n, 1));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                a[i][j] = min(min(j, n - j - 1), min(i, n - i - 1));
            }
        }

        int ans = 0;
        for (int i = 0; i < n * n; ++i) {
            int v;
            cin >> v;
            int x = (v - 1) / n;
            int y = (v - 1) % n;
            ans += a[x][y];
            b[x][y] = 0;
            queue<pair<int, int>> q;
            q.push({x, y});
            while (q.size()) {
                auto [x, y] = q.front();
                q.pop();
                int d = a[x][y] + b[x][y];

                for (auto [dx, dy] : vector<pair<int, int>>{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}) {
                    x += dx;
                    y += dy;
                    if (0 <= x && x < n && 0 <= y && y < n && d < a[x][y]) {
                        a[x][y] = d;
                        q.push({x, y});
                    }
                    x -= dx;
                    y -= dy;
                }
            }
        }
        cout << ans << "\n";
    }

    cerr << "Time execute: " << clock() / (double)CLOCKS_PER_SEC << " sec" << endl;
    return 0;
}


Measured memory_bytes: 5772
'use strict'

const main = (INPUT) => {
  let S = INPUT.split('\n')[0]
  let ans = 0
  let cnt = 0
  // while (S.match(/BW/) != null) {
  //   ans += S.match(/BW/g).length
  //   S = S.replace(/BW/g, 'WB')
  // }
  for (let i = 0; i < S.length; i++) {
    if (S[i] == 'W') {
      ans += cnt
    } else {
      cnt++
    }
  }
  console.log(ans)
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'))


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

#define int long long
#define pb push_back
#define mp make_pair
#define f(i,a,n) for(int i=a ; i<n ; i++)
#define all(c) (c).begin(),(c).end()
#define F first
#define S second
#define fast ios:: sync_with_stdio(false),cin.tie(nullptr);
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef vector<pii> vpi;

const int inf = 1e9;
const int inf64 = 1e18;
const int MOD = inf + 7;
const ld PI = acos(-1.0);

int32_t main(){
	fast;
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	cout << max(a*b , c*d);
}



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

int a, b;

int main() {
  cin >> a >> b;
  if(a > b) swap(a, b);
  if(b == 2)
    cout << 3 << endl;
  else if(a == 2)
    cout << 1 << endl;
  else
    cout << 2 << endl;
  return 0;
}

Measured memory_bytes: 256
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
for j in range(n):
  c=0
  for k in range(j,n-1):
    if l[k][1]>=c:c=l[k][1]+l[k][0]
    else:c=l[k][1]+(((c-l[k][1]-1)//l[k][2])+1)*l[k][2]+l[k][0]
  print(c)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define pb                push_back
#define ppb               pop_back
#define pf                push_front
#define ppf               pop_front
#define all(x)            (x).begin(),(x).end()
#define sz(x)             (int)((x).size())
#define int               long long
#define M                 1000000007
#define MM                998244353
#define fr                first
#define sc                second
#define pii               pair<int,int>
#define rep(i,a,b)        for(int i=a;i<b;i++)
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define ppc               __builtin_popcount

template<typename T1,typename T2>
std::istream& operator>>(std::istream& in,pair<T1,T2> &a)
{
	in>>a.fr>>a.sc;
	return in;
}
template<typename T1,typename T2>
std::ostream& operator<<(std::ostream& out,pair<T1,T2> &a)
{
	out<<a.fr<<" "<<a.sc;
	return out;
}

int n;
int a[3005];
int dp[3005][3005];
int calc(int l,int u,int m){
	if(l==u){
		return (1-m)*a[l];
	}
	int &ans=dp[l][u];
	if(ans!=-1)return ans;
	if(m){
		ans=min(calc(l+1,u,!m),calc(l,u-1,!m));
	}
	else{
		ans=max(a[l]+calc(l+1,u,!m),a[u]+calc(l,u-1,!m));
	}
	return ans;
}
void solve(){
	mem1(dp);
	cin>>n;
	int s=0;
	rep(i,0,n)cin>>a[i],s+=a[i];
	int x=calc(0,n-1,0),y=s-x;
	cout<<x-y;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	#ifdef SEIVE
		seive();
	#endif
	#ifdef NCR
		init();
	#endif
	#ifdef DSU
		cleardsu(MAXDSUSIZE);
	#endif
	int t=1;
	//cin>>t;
	while(t--) solve();
	return 0;
}


Measured memory_bytes: 70912
import java.util.Scanner;

public class Main{ 
        public static void main(String[] args){
            int i,j=0,sum,count=0;
            double bunn;
            int b[];
            double c[];
            b = new int[1000];
            c = new double[1000];
                Scanner n = new Scanner(System.in);
                while(true){
                     int a = n.nextInt();
                     if(a==0){
                         break;
                     }
                     sum = 0;
                     bunn = 0;
                     for(i=0;i<a;i++){
                         b[i]=n.nextInt();
                         sum = sum + b[i];
                     }
                     double ave = (double)sum/a;
                     for(i=0;i<a;i++){
                         bunn = bunn +  (double)((b[i]-ave)*(b[i]-ave));
                     }
                     double sann = bunn/a;
                     c[j]  = Math.sqrt(sann);
                     j++;
                     count++;
                }
                i=0;
                while(i<count){
                     System.out.println(c[i]);
                     i++;
                }
        }
    }


Measured memory_bytes: 31640
#include <bits/stdc++.h>
//#define DEBUG
#define REP(i, nn ) for(int i = 0 ; i < (int) nn; i++)
#define deb(x) std::cerr << #x << " " << x << endl;
#define debl(x) std::cerr << #x << " " << x << " ";
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
template<typename... T>
void read(T& ... a){
    ((cin >> a),...);
}
template<typename... T>
void write(T... a){
    ((cout << a << "\n"),...);
}

template<typename... T>
void write_space(T... a){
    ((cout << a << " "),...);
}
constexpr int mxN = 3000;
array<int, 3> dp[mxN][mxN];
void solve(){
    string s, t;
    read(s,t);
    dp[0][0] = {(s[0] == t[0]),0,0};
    for(int i = 1; i < (int) s.size(); i++){ 
        if(s[i] == t[0]){
            dp[i][0] = {1, i, 0}; 
        }else{
            dp[i][0] = dp[i-1][0];
        }
    }
    for(int j = 1 ; j < (int) t.size(); j++){
        if(t[j] == s[0]){
            dp[0][j] = {1, 0, j};
        }else{
            dp[0][j] = dp[0][j-1];
        }
    }
    for(int i = 1; i < (int) s.size(); i++){
        for(int j = 1; j < (int) t.size(); j++){
            if(s[i] != t[j]){
                if(dp[i-1][j][0] > dp[i][j-1][0]){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i][j-1];
                }
            }else{
                dp[i][j] =  {1 + dp[i-1][j-1][0], i, j};
            }
        }
    }
    int l = dp[s.size()-1][t.size()-1][0];
    int inds = dp[s.size()-1][t.size()-1][1];
    int indt = dp[s.size()-1][t.size()-1][2];
    //deb(l);
    if( l == 0){
        cout << "" << endl;
        return;
    }
    string ans(l, 'x');
    while(l--){
        ans[l] = t[indt];
        if(l == 0 ) break;
        int next_inds = dp[inds-1][indt-1][1];
        int next_indt = dp[inds-1][indt-1][2];
        inds = next_inds;
        indt = next_indt;
    }
    cout << ans << endl;
}

int main()
{
    //making data IO Fast
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    /****************************/
    solve();
    return 0;
}



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

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <db, db> pdd;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;

#define FOR(k,a,b) for(int k=(a); k<=(b); ++k)
#define IFOR(k,a,b) for(int k=(a); k>=(b); --k)
#define REP(k,a) for(int k=0; k<(a);++k)
#define IREP(k,a) for(int k=a-1; k>=(0);--k)
#define SZ(a) int((a).size())
#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define MP make_pair
#define x first
#define y second
#define INF 1000000001
#define INFLONG 1000000000000000000
#define MOD 1000000007
#define MAX 100
#define ITERS 100
#define MAXM 200000
#define MAXN 1000000
#define PI 3.1415926535897932384626
#define ERR -987654321
#define MEM(a,b) memset(a,b,sizeof(a));
#define read1(a) scanf("%d",&a)
#define read2(a,b) scanf("%d%d",&a,&b)
#define read3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define readl1(a) scanf("%lld",&a)
#define readl2(a,b) scanf("%lld%lld",&a,&b)
#define readl3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	int rn = uniform_int_distribution<int>(0, MAXN)(rng);

	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);

    int n,k;
    cin>>n>>k;
    int a[n];
    REP(i,n) cin>>a[i];
    int count = 0;
    REP(i,n) {
        i += (k-1);
        count++;
        if(i >= (n-1)) break;
        i--;
    }
    cout<<count;
	return 0;
}






Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
const int maxn=51;
pair<int,int> a[maxn];
int n,vis[maxn];
map<pair<int,int>,int> ID;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second;
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++) ID[a[i]]=i;
	if(n==1) return puts("1"),0;
	int ans=n;
	for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)
	{
		for(int k=1;k<=n;k++) vis[k]=0;
		int dx=a[j].first-a[i].first,dy=a[j].second-a[i].second;
		int cnt=0;
		for(int k=1;k<=n;k++) if(!vis[k])
		{
			int nowx=a[k].first,nowy=a[k].second;cnt++;
			while(ID[make_pair(nowx,nowy)])
				vis[ID[make_pair(nowx,nowy)]]=1,nowx+=dx,nowy+=dy; 
		}
		ans=min(ans,cnt);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 6016
#include<stdio.h>
int main(){
  int x,y,z,w,i;

  scanf("%d%d",&x,&y);
  if (x<y){
    z=x;
    x=y;
    y=z;
  }
  z=x%y;

  if(z!=0){
    while(1){
      w=y%z;
      if(w==0)
	{printf("%d\n",z);
	  break;}
      y=z;
      z=w;
    }
  }

  else printf("%d\n",y);
  return 0;
}

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

#define REP(i,n) for (int i = 0; i < n; i++)

int N;

int A[20005];
int B[20005];
int P[20005];

int main() {
	cin >> N;
	REP(i, N) {
		cin >> P[i];
		A[i] = N * (i+1);
		B[i] = N*N + N - A[i];
	}
	REP(i, N) {
		B[P[i]-1] += i;
	}

	REP(i, N) {
		cout << A[i] << " \n"[i==N-1];
	}
	REP(i, N) {
		cout << B[i] << " \n"[i==N-1];
	}
}


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

#define dump(n) cout<<"# "<<#n<<'='<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;

const int INF=1e9;
const int MOD=1e9+7;
const double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
	os<<'[';
	rep(i,a.size()) os<<(i?" ":"")<<a[i];
	return os<<']';
}

struct Edge{
	int src,dst,weight;
	Edge(){};
	Edge(int s,int d,int w):src(s),dst(d),weight(w){}
};
typedef vector<vector<Edge>> Graph;

pii DFS(const Graph& g,int p,int v)
{
	pii res(0,v);
	for(Edge e:g[v]) if(e.dst!=p){
		pii t=DFS(g,e.src,e.dst);
		t.first+=e.weight;
		if(res.first<t.first) res=t;
	}
	return res;
}

int Diameter(const Graph& g)
{
	int u,v,w;
	tie(w,u)=DFS(g,-1,0);
	tie(w,v)=DFS(g,-1,u);
	return w;
}

int main()
{
	for(int n;cin>>n && n;){
		Graph g(n);
		rep(i,n-1){
			int u,v,w; cin>>u>>v>>w;
			g[u].emplace_back(u,v,w);
			g[v].emplace_back(v,u,w);
		}
		cout<<Diameter(g)<<endl;
	}
}

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

int main(){
    int N;
    cin >> N;
    if (N/100 == 7) {
        cout << "Yes" << endl;
        return 0;
    }
    if (N%100/10 == 7) {
        cout << "Yes" << endl;
        return 0;
    }
    if (N%10 == 7) {
        cout << "Yes" << endl;
        return 0;
        }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3584
package main

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

var sc = bufio.NewScanner(os.Stdin)

func nextLine() int{
  sc.Scan()
  i, _:= strconv.Atoi(sc.Text())
  return i
}

func main(){
  a,b,h := nextLine(),nextLine(),nextLine()
  var total = 0
  if a==b && b == h && a == h{
  	total = b*h
  }else{    
    total = (a + b)*h/2
  }
  fmt.Println(total)
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
const int N=150,mo=1e9+7;
int fap(int a,int b){
    if (b<=0) return 1;
    int s=1;
    for (; b; b>>=1,a=1ll*a*a%mo)
	if (b&1) s=1ll*s*a%mo;
    return s;
}
void cal(int &x,int y){
    (x+=y)%=mo; return;
}
int n,h[N],a[N],f[N][N];
int main(){
    cin>>n;
    for (int i=1; i<=n; ++i)
	cin>>h[i],a[i]=h[i];
    int tmp=n;
    sort(a+1,a+n+1);
    tmp=unique(a+1,a+n+1)-a-1;
    for (int i=1; i<=n; ++i)
	h[i]=lower_bound(a+1,a+tmp+1,h[i])-a;
    f[0][0]=1;
    for (int i=1; i<=n; ++i){
	f[i][0]=f[i-1][0]*2%mo;
	for (int j=h[i]+1; j<=h[i-1]; ++j)
	    cal(f[i][0],f[i-1][j]*2%mo);
	tmp=fap(2,a[h[i]]-a[h[i-1]]);
	for (int j=min(h[i],h[i-1]); j; --j)
	    cal(f[i][j],1ll*tmp*f[i-1][j]%mo);
	for (int j=h[i-1]+1; j<=h[i]; ++j){
	    if (j==1)
		cal(f[i][j],1ll*f[i-1][0]*(fap(2,a[1])-2)%mo*fap(2,a[h[i]]-a[j])%mo);
	    else
		cal(f[i][j],2ll*f[i-1][0]*(fap(2,a[j]-a[j-1])-1)%mo*fap(2,a[h[i]]-a[j])%mo);
	}
    }
    int ans=0;
    for (int i=0; i<=h[n]; ++i)
	cal(ans,f[n][i]);
    cout<<ans;
    return 0;
}


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 (ll 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 FORI(i,v) for (auto i = v.begin(); i != v.end(); i++)
#define ALL(v) v.begin(), v.end()
#define CHMIN(x,y) x = min(x, y)
#define CHMAX(x,y) x = max(x, y)
#define YES(b) cout << ((b) ? "YES" : "NO") << endl
#define Yes(b) cout << ((b) ? "Yes" : "No") << endl
#define DOUBLE(d) cout << fixed << setprecision(15) << (d) << endl

const int MAX = 1e4+10;

int N, M;
int A[MAX];

int main() {
    cin >> N >> M;
    REP (i, M) cin >> A[i];
    ll s = 0;
    REP (i, M) s += A[i];
    cout << max(-1ll, N-s) << endl;
}

Measured memory_bytes: 3660
#include<bits/stdc++.h>
using namespace std;
#define fine cout<<"fine"<<endl;
#define ll long long int
#define pb push_back
#define FASTIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define F first
#define S second
#define all(v) v.begin(),v.end()
const ll inf=(ll)2e18;
const int mod=1e9+7;

void solve()
{
    ll n,m,v1,p;
    cin>>n>>m>>v1>>p;
    ll a[n];
    for(int i=0;i<n;i++)
    cin>>a[i];
    sort(a,a+n);
    vector<ll> v;
    v.pb(-1);
    for(int i=0;i<n-p+1;i++)
    v.pb(a[i]);
    ll s=0;
    int in=max((int)(v1-(p-1)-1),0);
    ll ans=p-1;
    int i;
    for(i=v.size()-1;i>in;i--){
        if(v[i]+m>=a[n-p])
        ans++;
        else
        break;
    s+=v[i];}
    if(i!=in)
    {
        cout<<ans<<endl;return;
    }
    for(i=in;i>0;i--)
    {
        if(v[i]+m<a[n-p])
        break;
        ll va=(ll)(v.size()-1-i)*m+((ll)(v.size()-1-i)*v[i]-s);
        if(va>0)
        {
            ll in1=v1-(i+p-1);
            if(in1>0&&va/in1>=m)
            ans++;
            else
            break;
        }
        s+=v[i];
    }
    cout<<ans<<endl;
}
int main()
{
    FASTIO;
    solve();
}

Measured memory_bytes: 2168
#include "bits/stdc++.h"

#define REP(i, n, N) for(ll i=(n); i<(N); i++)
#define RREP(i, n, N) for(ll i=(N-1); i>=(n); i--)
#define LREP(lst,itr) for(auto itr = lst.begin(); itr != lst.end(); ++itr)
#define CK(n, a, b) ((a)<=(n)&&(n)<(b))
#define ALL(v) (v).begin(),(v).end()
#define MCP(a, b) memcpy(b,a,sizeof(b))
#define P(s) cout<<(s)<<endl
#define P2(a, b) cout<<(a)<<" "<<(b)<<endl
#define P3(a, b, c) cout<<(a)<<" "<<(b)<<" "<<(c)<<endl
#define V2(T) vector<vector<T>>
typedef long long ll;
using namespace std;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;

int main(){
    string S,WS,TS;
    ll K,line=0,Wline=0,Tline=0;
    cin >> S >> K;

    if(S.size()==1){
        P(K/2);
        return 0;
    }
    
    char pre=S[0];
    REP(i,1,S.size()){
        if(pre==S[i]){
            //cout << pre << " " << S[i]<< endl;
            line++;
            pre=S[i+1];
            i++;
        }else{
            pre=S[i];
        }
    }
    
    if(K==1){
        P(line);
        return 0;
    }

    WS=S+S;
    //P(WS);
    pre=WS[0];
    REP(i,1,WS.size()){
        if(pre==WS[i]){
            Wline++;
            pre=WS[i+1];
            i++;
        }else{
            pre=WS[i];
        }
    }
    ll diff=Wline-line;

    if(K==2){
        P(Wline);
        return 0;
    }
    //P(line);
    //P(diff);
    TS=S+S+S;
    //P(WS);
    pre=TS[0];
    REP(i,1,TS.size()){
        if(pre==TS[i]){
            Tline++;
            pre=TS[i+1];
            i++;
        }else{
            pre=TS[i];
        }
    }
    ll Tdiff=Tline-Wline;
    P(line+((K-1)/2+(K-1)%2)*diff+((K-1)/2)*Tdiff);

    return 0;
}

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

int main(){
    int x, i, n, m = 1;
    cin >> x;
    int a[x+1] = {};
    for(i=2; i<=sqrt(x); i++){
        n = i;
        if(a[n] == 1){
            continue;
        }
        n *= i;
        while(n <= x){
            a[n] = 1;
            m = max(m, n);
            n *= i;
        }
    }
    cout << m;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] a = new int[N];
        for(int i=0;i<N;i++) a[i] = sc.nextInt();
        int odd = 0;
        int two = 0;
        int four = 0;
        for(int i=0;i<N;i++){
            if(a[i]%2==1) odd++;
            else{
                if(a[i]%4==0) four++;
                else two++;
            }
        }
        String ans = "No";
        if(four>=odd) ans = "Yes";
        if(four==odd-1&&two==0) ans="Yes";
        System.out.println(ans);
    }
}


Measured memory_bytes: 51640
import java.util.*;
 
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), ans = 1;
        int a[];
        a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = in.nextInt();
        int mmin = a[0];
        for (int i = 1; i < n; i++){
            if (a[i] < mmin) ans++;
            mmin = Math.min(mmin, a[i]);
        }
        System.out.printf("%d\n", ans);
        in.close();
    }
}


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

int main(){
    int n;
    cin >> n;
    vector<ll> x(n);
    ll tot = 0;
    rep(i,n){
        cin >> x.at(i);
        tot += x.at(i);
    }

    ll avg1 = tot / n;
    ll avg2 = avg1+1;
    ll d1=0,d2=0;
    rep(i,n){
        d1 += (x.at(i) - avg1) * (x.at(i) - avg1);
        d2 += (x.at(i) - avg2) * (x.at(i) - avg2);
    }
    cout << min(d1,d2) << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	char str[20];
	int p,i,length,x,t;
	
	scanf("%s",str);
	
	for(i = 0;!(str[i] == 0);i++){
		length = i + 1;
		t = length;
	}
	
	for(p = 0;p < length;p++){
		
		for(i = 0;i < (t - 1);i++){
				x = str[i];
				str[i] = str[i+1];
				str[i+1] = x;
		}
		t = t - 1;
	}
	
	printf("%s\n",str);
	
	return 0;
}

Measured memory_bytes: 520
#include<bits/stdc++.h>
using namespace std;
char s[100005];
int n;
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    if(s[1]=='0'||s[n]=='1'){
        puts("-1");
        return 0;
    }
    for(int i=1;i<n;i++)
        if(s[i]^s[n-i]){
            puts("-1");
            return 0;
        }
    int now=1;
    for(int i=2;i<=n;i++){
        printf("%d %d\n",now,i);
        if(s[i-1]=='1')now=i;
    }
}

Measured memory_bytes: 3844
#include <iostream>
using namespace std;
#include <stdio.h>
int main()
{
	int HW[10000][2], i = 0, j, l, k;
	while (1){
		cin >> HW[i][0] >> HW[i][1];
		if (HW[i][0] == 0 && HW[i][1] == 0)break;
		i++;
	}
	for (j = 0; j < i; j++){
		for (l = 0; l < HW[j][0]; l++){
			for (k = 0; k < HW[j][1]; k++){
				if ((l + k) % 2 == 0)	printf("#");
				else printf(".");
			}
			printf("\n");
		}
		printf("\n");
	}
}

Measured memory_bytes: 1120
N,Y = map(int,input().split(" "))
K = Y//1000 -N
     
l = int(-K/4)-1
r = -(2*K)/9+1

if l<=r:
    i=l
    while i <=r:
        a = K+4*i
        b = -2*K-9*i
        c = N-a-b

        if a>=0 and b>=0 and c >=0:
            print(a," ",b," ",c)
            break

        i+=1
    else:
        print(-1," ",-1," ",-1)

else:
    print(-1," ",-1," ",-1)



Measured memory_bytes: 3064
n,m,q=map(int,input().split())
a=[]
b=[]
c=[]
d=[]
for i in range(q):
	ai,bi,ci,di=map(int,input().split())
	a.append(ai)
	b.append(bi)
	c.append(ci)
	d.append(di)
from itertools import combinations_with_replacement as cmb
A=list(cmb(range(1,m+1),n))
#print(A)
ans=0
for lst in A:
	sum=0
	for i in range(q):
		if lst[b[i]-1]-lst[a[i]-1]==c[i]:
			sum+=d[i]
	ans=max(sum,ans)
print(ans)

Measured memory_bytes: 21468
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
  ll s,d;
  double t2,t1;
  cin>>d>>t1>>s;
  t1=t1*1.0;
  //cout<<t1<<"\n";
  t2=(d*1.0)/s;
  //cout<<t2<<"\n";
  if(t2<=t1) cout<<"Yes";
  else cout<<"No";
  return 0;
}

Measured memory_bytes: 3736