akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cmath>
#include<vector>
#include<map>
#include<string>
#include<algorithm>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int> H(N);
  for(int &hi: H) cin >> hi;
  H[0]--;
  string ret="Yes";
  for(int i=0; i<N-1; i++){
    if(H[i+1]<H[i]){
      ret="No";
    }else if(H[i+1]>H[i]){
      H[i+1]--;
    }
  }
  cout << ret << endl;
  return 0;
}

Measured memory_bytes: 640
n, a, b = map(int, input().split())
mod = 10**9+7
ans = pow(2, n, mod)-1

modp = mod

def cmb(n, r, p):
    r = min(r, n-r)
    upper = 1
    for i in range(n, n-r, -1):
        upper = (upper*i)%p
        
    lower = 1
    for i in range(1, r+1):
        lower = (lower*i)%p
    
    # フェルマーの小定理よりp素数ならupper**(p-2)は逆元
    return (upper*pow(lower, p-2, p))%p

ans-=cmb(n, a, mod)
ans-=cmb(n, b, mod)
print(ans%mod)


Measured memory_bytes: 9196
#include <stdio.h>
int main(void){
  int X, Y, Z;
  int a, b;
  
  scanf("%d %d %d",&X,&Y,&Z);
  
  a=X;
  X=Y;
  Y=a;
  
  b=X;
  X=Z;
  Z=b;
  
  printf("%d %d %d", X, Y, Z);
  
  return 0;
}

Measured memory_bytes: 1732
n = int(input())
a = [int(i) for i in input().split()]

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)
def lcm(x, y):
    return (x * y) // gcd(x, y)

l = a[0]
for i in a[1:]:
    l = lcm(l, i)
b = []
for i in a:
    b.append(l//i)
ans = sum(b) % (10 ** 9 + 7)
print(ans)

Measured memory_bytes: 262644
#include <bits/stdc++.h>
#define FOR(x,n) for(int x = 0; x < n; x++)
#define ALL(a) (a).begin(), (a).end()
#define FIN ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;

int main() {
  int A[3] = {};
  set<int> s;
  FOR(x,3) cin >> A[x], s.insert(A[x]);
  cout << s.size() << "\n";
}

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

Measured memory_bytes: 1660
q?d=q`div`d*d;u=getLine;main=u>>fmap(map read.words)u>>=putStrLn.maybe"-1"(unwords.map show).foldr(\s->(>>=i s))(Just[2,2]);i d[a,b]=if-l>u then Nothing else Just[-l,u+d-1]where l=(-a)?d;u=b?d

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

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1.0);

int main(void)
{
    ll ans=0;
    string a,b;
    cin>>a>>b;
    string bint;
    rep(i,b.size()){
        if(b[i]=='.') continue;
        bint+=b[i];
    }
    ans+=stoll(a);
    ans*=stoll(bint);
    ans/=100;
    cout<<ans<<endl;
    return 0;
}

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

#pragma GCC optimize("O3")
#define FASTIO  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define endl "\n"
#define gc getchar_unlocked
typedef long long ll;
typedef long double ld;
const double PI=acos(-1.0);
const int mod = 1000000007;




int main()
{
    FASTIO
	
	    int n,a,b;
	    cin>>n>>a>>b;
	    if(n*a<b)
	    cout<<(n*a);
	    else
	    cout<<b;
	

	return 0;
}




Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#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 PF push_front
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double
#define pii pair<int,int>
#define pll pair<LL,LL>
#define vi vector<int>
#define vl vector<LL>
#define vii vector<vi>
#define vll vector<vl>

const double pi = 3.14159265358979323846264;
const int mod=1000000007;
int N;
LL calc(vi a,vector<pii> p){
    LL sm=0;
    int n=N;
    FOR(i,0,n){
        sm+=1LL*abs(p[i].ND-i)*p[i].ST;
    }
    return sm;
}

int main(){
	int n;
    cin>>n;
    N=n;
    vi a(n);
    vector<pii> p(n);
    FOR(i,0,n){
        cin>>a[i];
        p[i]=MP(a[i],i);
    }
    vector<pii> q(p);
    sort(q.begin(),q.end());
    vll dp(n+1,vl(n+1,0));
    FOR(i,0,n+1){
        //FOR(j,0,n){
            //cout<<dp[i][j]<<" ";
        //}
        //cout<<endl;
        if(i==n)break;
        pii pr=q[n-1-i];
        int idx=pr.ND;
        int v=pr.ST;
        FOR(l,0,i+1){
            int r=n-1-(i-l);
            dp[i+1][l+1]=max(dp[i+1][l+1],dp[i][l]+1LL*abs(l-idx)*v);
            dp[i+1][l]=max(dp[i+1][l],dp[i][l]+1LL*abs(r-idx)*v);
        }
        
    }
    LL ans=0;
    FOR(i,0,n+1){
        ans=max(ans,dp[n][i]);
    }
    cout<<ans<<endl;


}


Measured memory_bytes: 34588
#include <bits/stdc++.h>
using namespace std;
#define DEBUG_MODE
#define endl '\n'
#ifdef DEBUG_MODE
#define DEBUG(X) debug_func(X, #X)
#define DEBUG_ENDL endl << flush
#define DEBUG_SEPARATOR_LINE cout<<"=================\n"
#else
#define DEBUG(X) 0
#define DEBUG_ENDL 0
#define DEBUG_SEPARATOR_LINE 0
#endif
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()
#define DEBUG_ENDL_S(S) ((S).size() ? "\n" : "") << flush;
template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
template <typename T, typename U> using P = pair<T, U>;
using ll = int64_t;
using PLL = P<ll, ll>;
template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename Head, typename... Tail> const Head& var_min(const Head &head, const Tail&... tail) { return min(head, var_min(tail...)); }
template <typename Head, typename... Tail> const Head& var_max(const Head &head, const Tail&... tail) { return max(head, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
void debug_func_preffix(const string &s) { if(s.size()) cout << s << " = "; }
template <typename T>
void debug_func(const T &t, const string &s = "") {
    debug_func_preffix(s);
    cout << t << DEBUG_ENDL_S(s);
}
template <typename T, typename U>
void debug_func(const P<T, U> &p, const string &s = "") {
    debug_func_preffix(s);
    cout << "(";
    debug_func(p.first);
    cout << ", ";
    debug_func(p.second);
    cout << ")" << DEBUG_ENDL_S(s);
}
template <typename T>
void debug_func(const V<T> &v, const string &s = "") {
    for(ll i = 0; i < v.size(); i++) {
        string t = s + "[" + to_string(i) + "]";
        debug_func(v[i], t);
    }
}

void init_io() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(30);
}

int main() {
    init_io();
    ll N;
    cin >> N;
    V<ll> A(N);
    for(ll &e : A) cin >> e;
    
    auto B = A;
    sort(ALL(B));
    ll cnt = 0;
    for(ll i = 0; i < N; i++) {
        auto ite = lower_bound(ALL(B), A[i]);
        ll dis = distance(B.begin(), ite);
        dis = abs(dis - i);
        cnt += (dis & 1);
    }
    cout << (cnt + 1) / 2 << endl;
    return 0;
}


Measured memory_bytes: 1792
from collections import Counter

N, P = map(int, input().split())


def prime_factorize(n):
    a = [1]
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


d = Counter(prime_factorize(P))
answer = 1
for i, n in d.items():
    if n >= N:
        answer *= i ** (n // N)

print(answer)


Measured memory_bytes: 3316
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
int main ()
{
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	if (a+b < c+d) printf("Right\n");
	if (a+b == c+d) printf("Balanced\n");
	if (a+b > c+d) printf("Left\n");
	}

Measured memory_bytes: 128
A = gets.chomp.to_i
B = gets.chomp.to_i
C = gets.chomp.to_i
X = gets.chomp.to_i
count = 0

(0..A).each do |a|
  (0..B).each do |b|
    (0..C).each do |c|
      if X - (a*500 + b*100 + c*50) == 0
        count += 1
      end
    end
  end
end

puts count

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

using namespace std;

#define ll long long
#define F first
#define S second
#define ii pair < int , int >


int main()
{
    ll n,d;
    scanf("%lld %lld",&n,&d);
    int cnt=0;
    for(int i=0;i<n;i++){
        ll x,y;
        scanf("%lld%lld",&x,&y);
        if((x*x)+(y*y)<=(d*d)){
            cnt++;
        }
    }
    printf("%d",cnt);
}


Measured memory_bytes: 3820
#include <iostream>
using namespace std;
int main(){
  int a,b,c;
  cin>>a>>b>>c;
  int d[3];
  d[0]=a+b;
  d[1]=a+c;
  d[2]=b+c;
  int min=d[0];
  for(int i=0;i<3;i++){
    if(min>d[i]){
      min=d[i];
    }
  }
  cout<<min;
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		if(b-a==c-b){
			System.out.print("YES");
		}else{
			System.out.print("NO");
		}
		
	}

}


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

struct Crop {
	string L;
	int P, A, B, C, D, E, F, S, M;
	int profit, time;
	double efficiency;
	void calc_profit() {
		profit = M * F * S - P;
	}
	void calc_time() {
		time = A + B + C + D + E;
		int m = M - 1;
		while (m--) {
			time += D + E;
		}
	}
	void calc_efficiency() {
		efficiency = (double)profit/(double)time;
	}
	void calc() {
		calc_profit();
		calc_time();
		calc_efficiency();
	}
	bool operator<(const Crop &o) const {
		if (efficiency == o.efficiency) return L < o.L;
		return efficiency > o.efficiency;
	}
};

int N;
vector<Crop> crops;

int main() {
	while (cin >> N) {
		if (N == 0) break;
		crops.clear(); 
		for (int i = 0; i < N; i++) {
			Crop c;
			cin >> c.L >> c.P >> c.A >> c.B >> c.C >> c.D >> c.E >> c.F >> c.S >> c.M;
			c.calc();
			crops.push_back(c);
		}
		sort(crops.begin(), crops.end());
		for (int i = 0; i < N; i++) {
			cout << crops[i].L << endl;
		}
		cout << "#" << endl;
	}
	return 0;
}

Measured memory_bytes: 1228
#include<bits/stdc++.h>
using namespace std;
int a,b;
  char op;
int main(){

cin>>a>>op>>b;
while(op!='?'){
switch(op){
case '+':
cout<<a+b<<endl;
break;
case '-':
cout<<a-b<<endl;
break;
case '*':
cout<<a*b<<endl;
break;
case '/':
cout<<a/b<<endl;
break;
}
cin>>a>>op>>b;
}}




Measured memory_bytes: 3108
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int N = 303;

int n,m;
int a[N][N];
int cnt[N];
int w[N];
bool bz[N];

int main(){
	n=get();m=get();
	fo(i,1,n)fo(j,1,m)a[i][j]=get();
	fo(i,1,n)cnt[a[i][w[i]=1]]++;
	int ans=1e+9;
	fo(i,1,m){
		int v=0;
		fo(x,1,m)
		if (!bz[x]&&cnt[x]>cnt[v])v=x;
		bz[v]=1;
		ans=min(ans,cnt[v]);
		cnt[v]=0;
		fo(x,1,n)
		if (bz[a[x][w[x]]]){
			while(w[x]<=m&&bz[a[x][w[x]]])w[x]++;
			cnt[a[x][w[x]]]++;
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 640
n=int(input())
ar=sorted(list(map(int,input().split())))
ans=0
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            if(ar[i]==ar[j]):continue
            if(ar[j]==ar[k]):continue
            if(ar[i]+ar[j]>ar[k]):
                ans+=1
print(ans)


Measured memory_bytes: 73588
import heapq
import math

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [i*-1 for i in A]

heapq.heapify(A)

for i in range(M):
  kk = math.ceil(heapq.heappop(A) / 2)
  heapq.heappush(A, kk)

A = [i*-1 for i in A]

print(sum(A))

Measured memory_bytes: 14532
'use strict';
(function(input){
  input=input.trim().split(/\s+/).map(x=>x-0);
  let N=input[0],
      L=input[1];
  let eaten=(L*(L+N-1)<0)?0:(L<0)?(L+N-1):L;
  console.log(Math.round(N*(2*L+N-1)/2-eaten));
})(require('fs').readFileSync('/dev/stdin','utf8'));


Measured memory_bytes: 7500
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main(void){
    int a,b;
    cin >> a >>b;
    int ans;
    if(a>9|b>9) ans=-1;
    else ans=a*b;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <string> 
using namespace std;

int main(void) {
    int H, W;
    string S[100], A[200];
    cin >> H >> W;
    for (int i = 0; i < H; i++) {
        cin >> S[i];
        A[i * 2] = S[i];
        A[i * 2 + 1] = S[i];
    }
    for (int i = 0; i < H * 2; i++) {
        cout << A[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cctype>
#include<map>
#include<cstring>
#include<bitset>
#include<cassert>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,a,b) for (int (i)=a;(i)<(b);(i)++)
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long int;

const int inf = 1001001000;
const long long int Inf = 1001001001001001000;



void print(vector<vector<int>> a){
	for (int i = 0; i < a.size(); i++)
	{
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<vector<long long int>> a){
	for (int i=0;i<a.size();i++){
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(vector<long long int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(set<int> a){
	for (auto x:a)
		cout << x << " ";
	cout << endl;
}

//ワーシャルフロイト法のテンプレ.graphに最短経路が格納される.
//負の重みがある場合inf + const = inf に気を付けること.
//graphは隣接行列.
void WF(vector<vector<int>> &graph){
	int n = graph.size();
	for (int k = 0; k < n; k++){
		for (int i = 0; i < n; i++){
			for (int j = 0; j < n; j++){
				graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
			}
		}
	}
}

int main()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int>> graph(n, vector<int>(n, inf));
	vector<pair<int, int>> edges;
	vector<int> dist(m);
	rep(i, n)
	{
		graph[i][i] = 0;
	}
	rep(i,m){
		int a, b, c;
		cin >> a >> b >> c;
		a--;
		b--;
		graph[a][b] = c;
		graph[b][a] = c;
		dist[i] = c;
		edges.push_back(pair<int, int>(a, b));
	}

	WF(graph);
	int ans = 0;
	rep(i, m)
	{
		pair<int, int> ab = edges[i];
		int a = ab.first, b = ab.second;
		int unused = 1;
		rep(j, n)
		{
			if (graph[j][a] + dist[i] == graph[j][b]) {
				unused = 0;
				break;
			}
		}
		ans += unused;
	}
	cout << ans << endl;

	return 0;
}

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

int Win;
char str[110];

int main()
{
	scanf("%s", str+1); int n=strlen(str+1);
	for (int i=1; i<=n; i++) if (str[i]=='o') Win++;
	Win+=(15-n);
	if (Win>=8) puts("YES"); else puts("NO");
}

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

using namespace std;
using ll = long long;
using di = pair<double, int>;

di solve(ll W, ll H, ll x, ll y)
{
    int sols = (2*x == W and 2*y == H) ? 1 : 0;

    return { W*H/2.0, sols };
}

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

    ll W, H, x, y;
    cin >> W >> H >> x >> y;

    auto ans = solve(W, H, x, y);

    cout << fixed << ans.first << ' ' << ans.second << endl;

    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
using namespace std;
int main()
{
	int a,b,c,d,n,y,x;
	scanf("%d %d %d %d %d",&n,&a,&b,&c,&d);
	x=n/a;
	if(n%a!=0)	x+=1;
	x*=b;
	y=n/c;
	if(n%c!=0)	y+=1;
	y*=d;
	if(x<y)	printf("%d\n",x);
	else	printf("%d\n",y);
	return 0;
}



Measured memory_bytes: 2756
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<ll>;
using vvi = vector<vi>;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;

int main() {
    ll n, a, b;
    cin >> n >> a >> b;
    vi h(n);
    rep(i, n) {
        cin >> h[i];
    }

    auto check = [&](ll x) {
        ll cou = 0;
        rep(i, n) {
            ll cc;
            cc = (h[i]-b*x + a-b - 1)/(a-b);
            if(cc > 0) {
                cou += cc;
            }
        }
        return cou <= x;
    };

    ll ub = INT_MAX, lb = 0;
    while(ub-lb != 1) {
        ll md = (ub+lb)/2;
        if(check(md)) {
            ub = md;
        } else {
            lb = md;
        }
    }

    cout << ub << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
int main(){
  int n;
  ll ans;
  cin >> n;
  vector<ll> v;
  rep(i,n){
    ll a;
    cin >> a;
    v.push_back(a);
  }
  sort(v.begin(),v.end());
  ans = v[v.size()-1];
  n-=2;
  int m=v.size()-2;
  while(true){
    if(n>=2){
      ans+=2*v[m];
      n-=2;
      m-=1;
    }
    else if(n==1){
      ans+=v[m];
      break;
    }
    else{
      break;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 5360
#include <bits/stdc++.h>
#define F(i,n) for (int i=1; i<=(int)n; i++)
#define FF(i,n) for (int i=0; i<(int)n; i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pi pair < int , int >
#define re(x) (int)x.size()
#define y1 u228
using namespace std;
typedef long long ll;
const int N = 2e5+228;
const int big = 2e9;
const int md = 1e9 + 7;
int n,i,k;
ll a[N],pr[N],ans;
vector < ll > v;
ll go(int i,int j,int k){
    return abs(pr[k]-pr[j]-(pr[j]-pr[i-1]));
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);
    //freopen("input.txt","r",stdin);
    cin>>n; ans=9e18;
    F(i,n) cin>>a[i];
    F(i,n) pr[i]=pr[i-1]+a[i];
    i=k=1;
    F(j,n){
        while (i<j && go(1,i,j)>go(1,i+1,j)) i++;
        while (k<n && go(j+1,k,n)>go(j+1,k+1,n)) k++;
        v.resize(0);
        v.pb(pr[i]); v.pb(pr[j]-pr[i]); v.pb(pr[k]-pr[j]); v.pb(pr[n]-pr[k]);
        sort(all(v));
        ans=min(ans,v[re(v)-1]-v[0]);
    }
    cout<<ans<<endl;
    return 0;
}







Measured memory_bytes: 3456
#include <stdio.h>
#include <stdlib.h>

void sort(int *, int);
void print(int *, int);

int main(void)
{
  int len, *toSort, i;
  scanf(" %d", &len);
  toSort = (int *) malloc(sizeof(int[len]));
  for (i = 0; i < len; i++)
    scanf(" %d", toSort + i);
  sort(toSort, len);
  return 0;
}

void sort(int *toSort, int len)
{
  int i, j, key;
  print(toSort, len);
  for (i = 1; i < len; i++)
    {
      key = toSort[i];
      j = i - 1;
      while (j >= 0 && toSort[j] > key)
	{
	  toSort[j+1] = toSort[j];
	  j--;
	}
      toSort[j+1] = key;
      print(toSort, len);
    }
}

void print(int *toSort, int len)
{
  int i;
  for (i = 0; i < len; i++)
    printf("%d%s", toSort[i], i == len - 1 ? "\n" : " ");
}



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

#define forn(i,n) for(int i=0;i<(int)(n);i++)
#define si(c) ((int)(c).size())
#define forsn(i,s,n) for(int i = (int)(s); i<((int)n); i++)
#define dforsn(i,s,n) for(int i = (int)(n)-1; i>=((int)s); i--)
#define all(c) (c).begin(), (c).end()
#define D(a) cerr << #a << "=" << (a) << endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair

typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;

const int INF = 1e9;
int n,m;
vector<string> a;

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

    cin >> n >> m;
    a.resize(n);
    vector<vi> d(n,vi(m, INF));
    queue<pii> q;
    forn(i,n) {
        cin >> a[i];
        forn(j,m) if (a[i][j] == '#') {
            d[i][j] = 0;
            q.emplace(i,j);
        }
    }
    int ans = 0;
    while (!q.empty()) {
        int ui, uj; 
        tie(ui, uj) = q.front();
        q.pop();
        int di = 1, dj = 0;
        forn(_,4) {
            int vi = ui+di, vj = uj+dj;
            if (vi >= 0 && vi < n && vj >= 0 && vj < m) {
                if (d[vi][vj] == INF) {
                    d[vi][vj] = d[ui][uj] + 1;
                    q.emplace(vi,vj);
                    ans = d[vi][vj];
                }
            }
            tie(di,dj) = mp(-dj,di);
        }
    }
    cout << ans << endl;
    return 0;
}


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

int main() {
	string s; cin >> s;
  	int n = s.size();
  	vector<int> ans(n);
  	rep(ri,2) {
      {
        int cnt = 0;
        rep(i,n) {
          if (s[i] == 'R') cnt++;
          else {
            ans[i] += cnt/2;
            ans[i-1] += (cnt+1)/2;
            cnt = 0;
        }
      }
    }
  	
  	reverse(ans.begin(), ans.end());
  	reverse(s.begin(), s.end());
  	rep(i,n) {
      if(s[i] == 'L') s[i] = 'R';
      else s[i] = 'L';
    }
  }
	rep(i,n) {
    printf("%d%c", ans[i], i==n-1?'\n':' ');
    }
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define ll long long
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define pb push_back
#define F first
#define S second
using namespace std;
const int mod = 1e9+7;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	while(cin >> n >> m){
		ll dp[1<<n];
		f(1<<n)dp[i] = 1e15;
		dp[0] = 0;
		f(m){
			ll tmp[1<<n];
			fr(j,0,1<<n)tmp[j] = dp[j];
			int mask = 0;
			int a,b;
			cin >> a >> b;
			fr(j,0,b){
				int add;
				cin >> add;
				add--;
				mask |= (1<<add);
			}
			fr(j,0,1<<n){
				tmp[j|mask] = min(dp[j]+a,tmp[j|mask]);
			}
			fr(j,0,1<<n){
				dp[j] = tmp[j];
			}
		}
		if(dp[(1<<n)-1]>=1e15){
			cout<<-1<<endl;
		}
		else{
			cout<< dp[(1<<n)-1] << endl;
		}
	}
}


Measured memory_bytes: 384
n, k, c = map(int,input().split())
s = list(input())

i, cnt = 0, 0
l = []
while cnt < k:
    if s[i] == 'o':
        l.append(i+1)
        cnt += 1
        i += c
    i += 1

i, cnt = n-1, 0
r = []
while cnt < k:
    if s[i] == 'o':
        r.append(i+1)
        cnt += 1
        i -= c
    i -= 1

r.sort()
for i in range(len(r)):
    if l[i] == r[i]:
        print(r[i])

Measured memory_bytes: 26696
#include <cstdio>
 
int main(){
	int Num=0;
	long int Time=0;
	long int Res=0;
	long int Before=0;
	scanf(" %d %ld",&Num,&Time);
	for(int i=0;i<Num;i++){
		long int Input=0;
		scanf(" %ld",&Input);
		if(i==0){
			Before=Input;
			continue;
		}
		long int Sub=Input-Before;
		if(Sub<Time){
			Res+=Sub;
		}else{
			Res+=Time;
		}
		Before=Input;
	}
	Res+=Time;
	printf("%d\n",Res);
	return 0;
}

Measured memory_bytes: 128
N, W = map(int, input().split())
vw = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in reversed(range(N)):
	for j in range(W + 1):
		if j < vw[i][1]:
			dp[i][j] = dp[i + 1][j]
		else:
			dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - vw[i][1]] + vw[i][0])

print(dp[0][W])


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

using namespace std;

int main() {
  int H, W;
  cin >> H >> W;
  
  vector<string> map(H+2);
  string s = "#";
  for (int i=1; i < W+2; i++) {
    s += '#';
  }
  map.at(0) = s;
  map.at(H+1) = s;
  
  for (int i=1; i < H+1; i++) {
    string s;
    cin >> s;
    map.at(i) = '#' + s + '#';
  }
  
  for (int i=0; i < H+2; i++) {
    cout << map.at(i) << endl;
  }
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<queue>
#include<cmath>
#define R(i, n) for(int i = 0;i < n;i++)
#define S(a) scanf("%d", &a)
#define S2(a, b) scanf("%d%d", &a, &b)
#define S3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define P(a) printf("%d", a)
#define INF 1000000000
using namespace std;
using ll = long long;
using IR = pair<int, int>;

int X, Y, Z;

int main() {
	S3(X, Y, Z);
	printf("%d %d %d", Z, X, Y);
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	static StringTokenizer st;
	public static void main(String[] args) throws IOException {
		String s = readLine();
      	boolean p = true;
      	int n = s.length();
      	for(int i = 0; i<n; i++){
          	if(s.charAt(i)!=s.charAt(n-i-1))p = false;
        }
      	int n2 = (n-1)/2;
      	for(int i = 0; i<n2; i++)
          	if(s.charAt(i)!=s.charAt(n2-i-1))p = false;
      	int n3 = (n+3)/2 - 1;
      	for(int i = n3; i<n; i++)
          	if(s.charAt(i)!=s.charAt(n-(i-n3)-1))p = false;
      	if(p)System.out.println("Yes");
      	else System.out.println("No");
	}
	static String next () throws IOException {
		while (st == null || !st.hasMoreTokens())
			st = new StringTokenizer(br.readLine().trim());
		return st.nextToken();
	}
	static long readLong () throws IOException {
		return Long.parseLong(next());
	}
	static int readInt () throws IOException {
		return Integer.parseInt(next());
	}
	static double readDouble () throws IOException {
		return Double.parseDouble(next());
	}
	static char readCharacter () throws IOException {
		return next().charAt(0);
	}
	static String readLine () throws IOException {
		return br.readLine().trim();
	}
}

Measured memory_bytes: 21460
from queue import deque

n=int(input())
ab = [list(map(int,input().split()))for i in range(n-1)]
g = [[]for i in range(n)]
for i,j in ab:
    g[i-1].append(j-1)
ans = {}
banColor = [-1]*n

q = deque([])
q.append(0)
ma = 0

while q:
    nord = q.popleft()
    offset = 0
    for idx,value in enumerate(g[nord]):
        if idx ==banColor[nord]:
            offset += 1
        ans[(nord,value)]= idx + offset
        banColor[value] = idx+offset
        q.append(value)
        ma = max(ma,idx+offset+1)
print(ma)
for i,j in ab:
    print(ans[(i-1,j-1)]+1)

Measured memory_bytes: 54424
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define int ll
//#define double ld
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
ifstream in("input.txt");ofstream out("output.txt");
const int inf=1e18;
const int mod=1e9+7;

class matrix
{
public:
    vector<vector<int> > mat;
    matrix(vector<vector<int> > x){mat=x;}
    matrix operator*(matrix other)
    {
        int n=mat.size();
        vector<vector<int> > ans(n,vector<int>(n));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                for(int c=0;c<n;c++)
                {
                    ans[i][j]+=mat[i][c]*other.mat[c][j];
                    ans[i][j]%=mod;
                }
            }
        }
        return ans;
    }
};
matrix binpow(matrix a,int n)
{
    matrix res=a;
    n--;
    while(n)
    {
        if(n&1ll)
            res=res*a;
        a=a*a;
        n>>=1ll;
    }
    return res;
}

signed main()
{
    int n,k;
    cin>>n>>k;
    vector<vector<int> > mat(n,vector<int>(n));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>mat[i][j];
        }
    }
    matrix ans(mat);
    ans=binpow(ans,k);
    int intans=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            intans+=ans.mat[i][j];
            intans%=mod;
        }
    }
    cout<<intans;
    return 0;
}























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

int main() {
    int N; cin >> N;
    int sum = 0;
    vector<int> B(N-1);
    for (int i = 0; i < N-1; i++) cin >> B.at(i);
    for (int i = 0; i < N-2; i++) {
        if (B.at(i) < B.at(i+1)) sum += B.at(i);
        else sum += B.at(i+1);
    }
    sum += B.at(0) + B.at(N-2);
    cout << sum << endl;
}

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    rep(i, n) rep(j, m) cin >> a[i][j];

    set<int> excluded;
    int ans = 1e6;
    for (int k = 0; k < m; k++) {
        vector<int> counter(m + 1, 0);
        int toBeExcluded = 0;
        for (int i = 0; i < n; i++) {
            int j = 0;
            while (j < m && excluded.count(a[i][j])) {
                j++;
            }
            counter[a[i][j]]++;
            if (counter[toBeExcluded] < counter[a[i][j]]) {
                toBeExcluded = a[i][j];
            }
        }
        ans = min(ans, counter[toBeExcluded]);
        excluded.insert(toBeExcluded);
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int n,k;
long long ans=0;
int h[N];
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>h[i];
	}
	sort(h+1,h+1+n);
	for(int i=1;i<=n-k;i++)
	ans+=h[i];
	cout<<ans;
	return 0;
}

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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    const ll MOD = 998244353;
    ll n, s;
    cin >> n >> s;
    vector<ll> a(n);
    for(i = 0;i < n;++i){
        cin >> a.at(i);
    }
    vector<vector<vector<ll>>> dp(n+1,vector<vector<ll>>(s+1, vector<ll>(3,0)));
    dp.at(0).at(0).at(0) = 1;
    for(i = 0;i < n;++i){
        rep(j,s+1){
            dp.at(i+1).at(j).at(0) += dp.at(i).at(j).at(0);
            dp.at(i+1).at(j).at(0) %= MOD;
            dp.at(i+1).at(j).at(1) += dp.at(i).at(j).at(0) + dp.at(i).at(j).at(1);
            dp.at(i+1).at(j).at(1) %= MOD;
            dp.at(i+1).at(j).at(2) += dp.at(i).at(j).at(0) + dp.at(i).at(j).at(1) + dp.at(i).at(j).at(2);
            dp.at(i+1).at(j).at(2) %= MOD;
            if(j + a.at(i) <= s){
                ll tmp = j + a.at(i);
                dp.at(i+1).at(tmp).at(1) += dp.at(i).at(j).at(0) + dp.at(i).at(j).at(1);
                dp.at(i+1).at(tmp).at(1) %= MOD;
                dp.at(i+1).at(tmp).at(2) += dp.at(i).at(j).at(0) + dp.at(i).at(j).at(1);
                dp.at(i+1).at(tmp).at(1) %= MOD;
            }
        }
    }
    cout << dp.at(n).at(s).at(2)%MOD << endl;
    return 0;
}

Measured memory_bytes: 493056
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
typedef long long ll;
typedef pair<int, int> P;

#define INF 1000000000001
#define MAX_E 100000
#define MAX_V 100000

struct edge {
	int from, to, cost;
};
ll d[MAX_V];
int V, E;

edge es[MAX_E];

void shortest_path(int s) {
	rep(i, 0, V) d[i] = INF;
	d[s] = 0;
	while(true) {
		bool update = false;
		rep(i, 0, E) {
			edge e = es[i];
			if(d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
				d[e.to] = d[e.from] + e.cost;
				update = true;
			}
		}
		if(!update) break;
	}
}

bool find_negative_loop(int s) {
	//memset(d, 0, sizeof(d));
	fill(d, d + V, INF);
	d[s] = 0;
	rep(i, 0, V) {
		rep(j, 0, E) {
			edge e = es[j];
			if(d[e.to] > d[e.from] + e.cost) {
				d[e.to] = d[e.from] + e.cost;
				if(i == V - 1 && e.to == V - 1) return true;
			}
		}
	}
	return false;
}

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

	int N, M;
	cin >> N >> M;
	V = N, E = M;
	rep(i, 0, E) {
		ll a, b, c;
		cin >> a >> b >> c;
		a--, b--;
		es[i].from = a;
		es[i].to = b;
		es[i].cost = -c;
	}

	if(find_negative_loop(0)) {
		cout << "inf" << endl;
		return 0;
	}

	cout << -d[N - 1] << endl;

}


Measured memory_bytes: 256
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


def input():
    return sys.stdin.readline()


def resolve():
    n = int(input().rstrip())
    cnt = 0
    while True:
        cnt += 1
        remain = n - (cnt*1000)
        if remain <= 0:
            change = cnt*1000 - n
            break


    print(change)


if __name__ == "__main__":
    resolve()



Measured memory_bytes: 9160
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, X: "List[int]"):
    X.sort()
    L = []
    for i in range(1,M):
        L.append( X[i] - X[i-1])
    L.sort(reverse=True)

    print((X[-1] - X[0]) - sum(L[0:(N-1)]))


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    X = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    solve(N, M, X)

if __name__ == '__main__':
    main()


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

char buf[11];
int main(){
	int n;
	while (scanf("%d", &n), n) {
		sprintf(buf, "%o", n);
		rep(i, strlen(buf)) {
			if (buf[i] >= '5')buf[i] += 2;
			if (buf[i] == '4')buf[i]++;
		}
		printf("%s\n", buf);
	}
	return 0;
}

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

int Ps[200000], Ms[200000];

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

  int cnt = 0;
  rep(i, n) {
    if (s[i] == '1') cnt++;
  }
  int cntP = cnt + 1, cntM = cnt - 1;
  int modP = 0, modM = 0;
  int twoP = 1, twoM = 1;
  for (int i = n - 1; i >= 0; i--) {
    Ps[i] = twoP % cntP;
    if (cntM > 0) Ms[i] = twoM % cntM;
    if (s[i] == '1') {
      modP = (modP + twoP) % cntP;
      if (cntM > 0) modM = (modM + twoM) % cntM;
    }
    twoP = (twoP * 2) % cntP;
    if (cntM > 0) twoM = (twoM * 2) % cntM;
  }

  rep(i, n) {
    int ans = 1;
    if (s[i] == '1') {
      if (cntM == 0) { cout << 0 << endl; continue; }
      int m = (modM - Ms[i] + cntM) % cntM;
      while (m > 0) {
        int cnt2 = 0;
        rep(j, 18) {
          if (m >> j & 1) cnt2++;
        }
        m %= cnt2;
        ans++;
      }
      cout << ans << endl;
    } else {
      int m = (modP + Ps[i]) % cntP;
      while (m > 0) {
        int cnt2 = 0;
        rep(j, 18) {
          if (m >> j & 1) cnt2++;
        }
        m %= cnt2;
        ans++;
      }
      cout << ans << endl;
    }
  }

  return 0;
}
/*
*/


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

int main(){
  int n,ans=0; cin>>n;
  vector<string> s(3); cin>>s[0]>>s[1]>>s[2];
  for(int i=0;i<n;i++){
    if(s[0][i]==s[1][i]){
      if(s[0][i]!=s[2][i]) ans++;
    }else if(s[1][i]==s[2][i]){
      ans++;
    }else if(s[0][i]==s[2][i]){
      ans++;
    }
    else ans+=2;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
def cin():
    in_ = list(map(int,input().split()))
    if len(in_) == 1:  return in_[0]
    else:  return in_

def fact_prime(n, p):
    ret = 0
    temp = p
    while(n >= p):
        ret += n // p
        p *= temp
    return ret

n = cin()

if n % 2:
    n = (n + 1) // 2
    a2 = fact_prime(2 * n, 2)
    a5 = fact_prime(2 * n, 5)
    b2 = fact_prime(n, 2) + n
    b5 = fact_prime(n, 5)
    ans = min(a2 - b2, a5 - b5)
else:
    n = n // 2
    ans = fact_prime(n, 5)
print(ans)

Measured memory_bytes: 61564
#include<cstdio>
#include<algorithm>
using namespace std;

int main(){
	int N, x;
	scanf("%d %d", &N, &x);
	int a[N];
	for (int i = 0; i < N; ++i) scanf("%d", &a[i]);
	sort(a, a + N);
	int i = 0;
	while(i < N && x >= a[i]){
		x -= a[i];
		if(i < N - 1 || !x) i++;
	}
	printf("%d\n", i);
	return 0;
}

Measured memory_bytes: 128
use proconio::marker::Usize1;
use proconio::{fastout, input};
use std::cmp;

#[fastout]
fn main() {
    input! {
        n: usize,
        k: usize,
        p: [Usize1; n],
        c: [i64; n],
    }

    let mut solve = Solve { n, k, p, c };
    solve.solve();
}

struct Solve {
    n: usize,
    k: usize,
    p: Vec<usize>,
    c: Vec<i64>,
}

impl Solve {
    fn solve(&mut self) {
        let n = self.n;
        // いくつかの成分に分割する
        let mut visited = vec![false; n];
        let mut parts = vec![];
        for i in 0..n {
            if visited[i] {
                continue;
            }

            visited[i] = true;
            let mut part: Vec<usize> = vec![i];
            let mut j = self.p[i];
            while j != i {
                visited[j] = true;
                part.push(j);
                j = self.p[j];
            }
            parts.push(part);
        }

        let mut ans = std::i64::MIN;
        for part in parts {
            let values: Vec<i64> = part.iter().copied().map(|i| self.c[i]).collect();
            let mut csum = vec![0];
            for i in 0..(2 * n) {
                let last = csum.last().unwrap();
                csum.push(last + values[i % values.len()]);
            }

            let s: i64 = values.iter().sum();
            if s >= 0 {
                // 回れるだけ回る
                for i in 1..=cmp::min(self.k, values.len()) {
                    let m = self.max_one_loop(&csum, i);
                    let d = (self.k - i) / part.len();
                    let now = m + d as i64 * s;
                    ans = cmp::max(ans, now);
                }
                // let d = self.k / part.len();
                // let m1 = self.max_one_loop(&csum, self.k % part.len());
                // let now = d as i64 * s + m1;
                // dbg!(now, m1);
                // ans = cmp::max(ans, now);
            } else {
                for i in 1..=cmp::min(self.k, values.len()) {
                    let m1 = self.max_one_loop(&csum, i);
                    ans = cmp::max(ans, m1);
                }
            }
        }

        println!("{}", ans);
    }

    fn max_one_loop(&mut self, v: &Vec<i64>, k: usize) -> i64 {
        if k == 0 {
            return 0;
        }

        let mut mx = std::i64::MIN;
        for i in 0..v.len() / 2 {
            let now = v[i + k] - v[i];
            mx = cmp::max(mx, now);
        }

        mx
    }
}

// 累積和
// 和が正なら回るだけ回った後で、1回のループの中で最大
// 和が負なら1回のループの中で最大
// O(n^2)
//
// 1から始めても巡回するとは限らない
// 巡回の成分ごとにやる？
//
// 0-indexedにする
//
// 2 4 5 1 3
// 累積和
// 3 7 -1
//
// 1 2 4 と 3 5 に分けられる
// 3 4 -8 と -10 8


Measured memory_bytes: 2544
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>

using namespace std;

int main()
{
	long long n,a,b;
	cin >> n >> a >> b;
	vector<long long> x(n);
	for(int i=0;i<n;i++)
		cin >> x[i];
	long long ans=0;
	for(int i=0;i<n-1;i++)
		ans+=min(b,a*(x[i+1]-x[i]));
	cout << ans << endl;






}


Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
#define INF 200000000000
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; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()

bool compare(pair<int, int> a, pair<int, int> b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}
// 入力



int main() {
    ll N;
    cin >>N;

    vector<vector<ll>> c(10,vector<ll>(10));
    rep2(i,N){
        ll now = i;
        ll m,l;
        while(now){
            if(now/10 == 0){
                m = now;
            }
            now/=10;
        }
        l = i%10;
        c[m][l]++;

    }
    ll ans = 0;
    rep2(i,9){
        rep2(j,9){
            ans+= c[i][j]*c[j][i];
        }
    }



        
    
    cout << ans << endl;


    return 0;
    

}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ini(x, y) memset(x, y, sizeof(x))
#define endl '\n'
#define fastio cin.sync_with_stdio(false); cin.tie(nullptr)
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int MOD = 1e9 + 7;
const int dx[] = { -1, 0, 1, 0, -1, 1, 1, -1 };
const int dy[] = { 0, 1, 0, -1, 1, 1, -1, -1 };

vector<int> adj[200000];
int N, w[200000], dp[200000];
int fac[200001], ans[200000];

int inv(int n, int r = MOD - 2) {
	int ret = 1;
	for (; r; r >>= 1) {
		if (r & 1) ret = ll(ret) * n % MOD;
		n = ll(n) * n % MOD;
	}
	return ret;
}
void dfs(int now, int prv = -1) {
	w[now] = dp[now] = 1;
	for (int nxt : adj[now]) if (nxt != prv) {
		dfs(nxt, now);
		dp[now] = ll(dp[now]) * dp[nxt] % MOD * inv(fac[w[nxt]]) % MOD;
		w[now] += w[nxt];
	}
	dp[now] = ll(dp[now]) * fac[w[now] - 1] % MOD;
}
void dfs2(int now, int prv = -1) {
	for (int nxt : adj[now]) if (nxt != prv) {
		int tmp = ll(ans[now]) * fac[w[nxt]] % MOD * inv(dp[nxt]) % MOD;
		tmp = ll(tmp) * inv(fac[N - 1]) % MOD * fac[N - w[nxt] - 1] % MOD;

		ans[nxt] = ll(dp[nxt]) * tmp % MOD * inv(fac[N - w[nxt]]) % MOD;
		ans[nxt] = ll(ans[nxt]) * inv(fac[w[nxt] - 1]) % MOD * fac[N - 1] % MOD;
		dfs2(nxt, now);
	}
}
int main() {
	fastio;
	cin >> N;

	fac[0] = 1;
	for (int i = 1; i <= 200000; ++i) fac[i] = (ll)i * fac[i - 1] % MOD;

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

	dfs(0);
	ans[0] = dp[0];
	dfs2(0);

	for (int i = 0; i < N; ++i) cout << ans[i] << endl;

	return 0;
}

Measured memory_bytes: 17012
#include <bits/stdc++.h>
using namespace std;
int main(){
  int h,w;
  cin >> h >> w;
  vector<vector<char>> tbl(h,vector<char>(w));
  vector<int> cf(w,0);
  vector<int> rf(h,0);
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
      cin >> tbl.at(i).at(j);
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
      if(tbl.at(i).at(j)=='#')
        rf.at(i) = cf.at(j) = 1;
  for(int i=0;i<h;i++)
    if(rf.at(i)==1){
      for(int j=0;j<w;j++)
        if(cf.at(j)==1)
          cout << tbl.at(i).at(j);
      cout << endl;
    }
}


Measured memory_bytes: 256
from collections import defaultdict
from heapq import heappop, heappush
class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

def solve():
  n,m = (int(i) for i in input().split())
  route = [[float("INF")]*n for _ in range(n)]
  for i in range(n):
    route[i][i] = 0
    
  A = []
  B = []
  cost = []
  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    route[a-1][b-1] = c
    route[b-1][a-1] = c
    A.append(a-1)
    B.append(b-1)
    cost.append(c)

  
  for k in range(n):
    for i in range(n):
      for j in range(n):
        route[i][j] = min(route[i][j],route[i][k]+route[k][j])
        
  ans = 0
  for i in range(m):
    if cost[i] > route[A[i]][B[i]]:
      ans += 1
  print(ans)
        
solve()

Measured memory_bytes: 3748
#include <stdio.h>

int main (){
	
	int n;	// zero mengecek kalo perkaliannya dengan 0
	long long int a, max = 1e18, hasil = 1, flag = 0, zero = 0; 
	
	scanf("%d",&n);
	
	for(int i = 0; i < n; i++){
		scanf("%lld",&a);
		flag =(a > max) ? 1 : flag; // penanda kalo ada 0
		hasil *= a;
		a != 0 ? max /= a : zero = 1;
	}

	if(zero == 1){
		printf("0\n");
	}else if (flag == 1){
		printf("-1\n");
	}else{
		printf("%lld\n",hasil);
	}
return 0;
}


Measured memory_bytes: 3228
import java.util.Scanner;
public class Main{
	public static void main(String[]args) {
		Scanner sc=new Scanner(System.in);
		int []array=new int[2];
		int sum=0;
		for(int i=0;i<2;i++) {
			array[i]=sc.nextInt();
		}
		int []arr=new int[array[1]];
		for(int i=0;i<array[1];i++) {
			arr[i]=sc.nextInt();
			sum=sum+arr[i];
		}
		if(sum<array[0])
		  System.out.println("No");
		else
			System.out.println("Yes");
	}
	
}

Measured memory_bytes: 50920
H, W  = map(int, input().split())

lst = []
for i in range(H):
    lst += ['#' + str(input()) + '#']

# print (lst)
for i in range(W+2):
    print ('#', end = '')
print ()

for i in range(H):
    print (lst[i])

for i in range(W+2):
    print ('#', end = '')
print ()


Measured memory_bytes: 3060
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
long long a,b,ans,n;
long long m[100001];
bool judge(long long x)
{
    long long temp=x*b,sub=a-b,sum=0;
    for(int i=0;i<n;i++)
    {
        if(m[i]-temp>0)
        {
            if((m[i]-temp)%sub)
                sum+=(m[i]-temp)/sub+1;
            else
                sum+=(m[i]-temp)/sub;
        }
    }
    if(sum<=x)
        return true;
    return false;
}
int main()
{
    long long right=0,left=1;
    scanf("%lld%lld%lld",&n,&a,&b);
    for(int i=0;i<n;i++)
        {
            scanf("%d",&m[i]);
            right+=m[i]/b+1;
        }
    sort(m,m+n);
    while(left<right)
    {
        long long mid=(left+right)>>1;
        if(judge(mid))
            right=mid;
        else
            left=mid+1;
    }
    printf("%d\n",left);

    return 0;
}

Measured memory_bytes: 1152