akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

// make sure permutation is [0..=n-1]
struct Perm : vector<int> {
    using vector<int>::vector;
    Perm() {}
    Perm(initializer_list<int> list) : vector<int>(list) {}

};

Perm& operator*=(Perm& a, const Perm& b) {
    assert(a.size() == b.size());
    int n = a.size();
    Perm _a(a);
    for (int i = 0; i < n; i++) {
        a[i] = _a[b[i]];
    }
    return a;
}
Perm operator*(const Perm& a, const Perm& b) {
    assert(a.size() == b.size());
    int n = a.size();
    Perm c(n);
    for (int i = 0; i < n; i++) {
        c[i] = a[b[i]];
    }
    return c;
}
Perm pinv(const Perm& a) {
    int n = a.size();
    Perm c(n);
    for (int i = 0; i < n; i++) {
        c[a[i]] = i;
    }
    return c;
}
Perm& operator/=(Perm& a, const Perm& b) {
    return a *= pinv(b);
}
Perm operator/(const Perm& a, const Perm& b) {
    return a * pinv(b);
}
Perm ppow(Perm a, int64_t e) {
    if (e < 0) {
        a = pinv(a);
        e *= -1;
    }
    int n = a.size();
    Perm c(n);
    iota(c.begin(), c.end(), 0);
    for (; e; e>>=1) {
        if (e&1) c *= a;
        a *= a;
    }
    return c;
}
int cycles_cnt(Perm a) {
    int cnt = 0, n = a.size();
    for (int i = 0; i < n; i++) {
        if (~a[i]) {
            cnt++;
            for (int j = i; ~a[j];) {
                int nxt = a[j];
                a[j] = -1;
                j = nxt;
            }
        }
    }
    return cnt;
}

void solve() {
    int n; cin >> n;
    vector<int> a(n);
    vector<pair<int, int>> s(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        int y; cin >> y;
        s[i] = {a[i], y};
    }
    sort(a.begin(), a.end());
    sort(s.begin(), s.end(), [&](auto& u, auto& v){
        return u.second < v.second;
    });
    for (int i = 0; i < n; i++) {
        if (a[i] > s[i].second) {
            cout << "No"; return;
        }
    }
    for (int i = 1; i < n; i++) {
        if (a[i] <= s[i-1].second) {
            cout << "Yes"; return;
        }
    }

    Perm p(n);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](auto& u, auto& v){
        return s[u].first < s[v].first;
    });
    int c = cycles_cnt(p);
    cout << (c>1?"Yes":"No");
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


Measured memory_bytes: 2176
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using ll = long long int;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

std::string s;

int main(void){
	int n,i,r=0;
	std::cin >> s;
	n = s.l_ength();
	for(i=0; i<n; ++i){
		r += s[i]-'0';
		r %= 9;
	}
	std::cout << (r?"No":"Yes") << std::endl;
	return 0;
}


Measured memory_bytes: 3748
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define SIZE 1e18
int main()
{
	ll n,w;
	cin>>n>>w;

	vector< pair < ll, ll > > v;

	ll we,val;
	ll sum=0;
	v.push_back({0,0});
	for(int i=0;i<n;i++)
	{
		cin>>we>>val;
		v.push_back({we,val});
		sum+=val;
	}

	ll dp[n+1][sum+1];

	for(ll i=0;i<=n;i++)
	{
		for(ll j=0;j<=sum;j++)
		{
			if(i==0 && j==0)
				dp[i][j]=0;
			else
			if(i==0)
			{
				dp[i][j]=SIZE;
			}
			else
			if(j==0)
			{
				dp[i][j]=0;
			}
			else
			{
				dp[i][j]=min(dp[i-1][j],v[i].first+((v[i].second>j)?0:dp[i-1][j-v[i].second]));
			}
		}
	}

	
	for(int j=sum;j>=0;j--)
	{
		if(dp[n][j]<=w)
		{
			cout<<j<<endl;
			break;
		}

	}


}

Measured memory_bytes: 79104
#include <iostream>
#define llint long long

using namespace std;

llint t, d, l;
llint dif[100005];

int main(void)
{
	while(1){
		cin >> t >> d >> l;
		if(t == 0) break;
		for(int i = 1; i <= t; i++) dif[i] = 0;
		llint x;
		for(int i = 1; i <= t; i++){
			cin >> x;
			if(x >= l) dif[i]++, dif[i+d]--;
		}
		for(int i = 1; i <= t; i++) dif[i] += dif[i-1];
		
		llint ans = 0;
		for(int i = 1; i <= t-1; i++){
			if(dif[i] > 0) ans++;
		}
		cout << ans << endl;
	}
	
	return 0;
}


Measured memory_bytes: 3848
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
	public static void main(String args[]) throws IOException{
		InputStreamReader input = new InputStreamReader(System.in);
		BufferedReader reader = new BufferedReader(input, 1);
		int N = Integer.parseInt(reader.readLine());
		if(N == 1) {
          System.out.println("Hello World");
		}else {
			System.out.println(Integer.parseInt(reader.readLine()) + 
					Integer.parseInt(reader.readLine()));
		}
		
	}

}

Measured memory_bytes: 21204
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int dp[1010][1010];
int h,w;
vector<string> a(1010);
int mod = 1000000007;
int main(void){
    cin >> h >> w;
    for(int i = 0;i < h;i++){
        cin >> a[i];
    }
    dp[0][0] = 1;
    for(int i = 0;i < h;i++){
        for(int j = 0;j < w;j++){
            if(i+1 < h && a[i+1][j] == '.'){
                dp[i+1][j] += dp[i][j];
                if(dp[i+1][j] >= mod) dp[i+1][j] -= mod;
            }
            if(j+1 < w && a[i][j+1] == '.'){
                dp[i][j+1] += dp[i][j];
                if(dp[i][j+1] >= mod) dp[i][j+1] -= mod;
            }
        }
    }
    cout << dp[h-1][w-1] << endl;
    return 0;
}


Measured memory_bytes: 5248
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

using ll = long long;
using ull = uint64_t;
using P = pair<int, int>;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

// 参考URL : https://drken1215.hatenablog.com/entry/2018/09/30/002900

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

    int N;
    cin >> N;
    vector<int> x(N), y(N);
    for(int i = 0; i < N; ++i)  cin >> x[i] >> y[i];

    int parity = (abs(x[0]) + abs(y[0])) % 2;
    vector<P> table;
    for(int i = 0; i < N; ++i){
        int p = (abs(x[i]) + abs(y[i])) % 2;
        table.emplace_back(x[i] + y[i], x[i] - y[i]);
        if(p != parity){
            cout << -1 << endl;
            return 0;
        }
    }

    vector<int> d;
    for(int i = 30; i >= 0; --i)    d.emplace_back(1 << i);
    if(parity % 2 == 0) d.emplace_back(1);
    int n = d.size();
    cout << n << '\n';
    for(int i = 0; i < n; ++i){
        cout << d[i];
        cout << ((i == n - 1) ? '\n' : ' ');
    }

    for(auto p : table){
        int xdir, ydir;
        ll xsum = 0, ysum = 0;
        for(int j = 0; j < n; ++j){
            if(xsum <= p.first) xdir = 1, xsum += d[j];
            else    xdir = -1, xsum -= d[j];
            if(ysum <= p.second)    ydir = 1, ysum += d[j];
            else    ydir = -1, ysum -= d[j];

            if(xdir == 1 && ydir == 1)  cout << 'R';
            else if(xdir == 1 && ydir == -1)    cout << 'U';
            else if(xdir == -1 && ydir == -1)   cout << 'L';
            else    cout << 'D';
        }
        cout << '\n';
    }
}

Measured memory_bytes: 3680
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define rg register
#define LL long long
#define __space putchar(' ')
#define __endl putchar('\n')
template <typename qwq> inline void read(qwq &x)
{
	x = 0;
	rg int f = 1;
	rg char c = getchar();
	while (c < '0' || c > '9')
	{
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9')
	{
		x = (x << 1) + (x << 3) + (c ^ 48);
		c = getchar();
	}
	x *= f;
}
template <typename qaq> inline void print(qaq x)
{
	if (x < 0)
	{
		putchar('-');
		x = -x;
	}
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int maxn = 2333333;
int n, k, sum, siz, len, sumup, sumdown;
int a[maxn], lst[maxn], downdelta[maxn], updelta[maxn];
priority_queue<int> gcd;
inline void make_list(int x)
{
//	len = 0;
	rg int tmp = 0;
	for (rg int i = 0; i <= sum; i += x)
	{
		lst[++tmp] = i;
	}
	for (rg int i = len; i > tmp; --i) lst[i] = 0;
	len = tmp;
}
inline void div(int x)
{
	for (rg int i = 1; i * i <= x; ++i)
	{
		if (!(x % i))
		{
			gcd.push(i);
			if (i * i != x) gcd.push(x / i);
		}
	}
}
int main()
{
	read(n), read(k);
	for (rg int i = 1; i <= n; ++i)
	{
		read(a[i]);
		sum += a[i];
	}
	div(sum);
	while (!gcd.empty())
	{
		sumup = sumdown = 0;
		rg int now = gcd.top();
		gcd.pop();
		if (now == 1)
		{
			print(1);
			return 0;
		}
		for (rg int i = 1; i <= n; ++i)
		{
			updelta[i] = now - (a[i] % now);
			downdelta[i] = a[i] % now;
			sumdown += downdelta[i];
		}
		stable_sort(downdelta + 1, downdelta + 1 + n);
		stable_sort(updelta + 1, updelta + 1 + n);
		for (rg int i = 1; i <= n; ++i)
		{
			sumup += updelta[i];
			sumdown -= downdelta[n - i + 1];
			if (sumup - sumdown == 0 && sumup <= k)
			{
				print(now);
				return 0;
			}
		}
		
	}
	return 0;
}

Measured memory_bytes: 4352
import java.util.*

fun main(args: Array<String>) {
  val sc = Scanner(System.`in`)
  val n = sc.nextLong()

  val ans = mutableListOf<Long>()
  val sqrtN = Math.sqrt(n.toDouble())
  for (i in 2L .. sqrtN.toLong()) {
    if (n % i != 0L) {
      continue
    }
    val y = n / i
    val tmp = (i - 1L) + (y - 1L)
    ans.add(tmp)
  }
  ans.add(n - 1L)

  println(ans.min())
}

Measured memory_bytes: 31520
l = [ 3**7, 3*3*3*5, 3*3*3*7, 3*3*3*11, 3*5*7, 3*5*11, 3*5*13, 3*5*17, 3*7*11, ]
#print(l)
N = int(input())
r = len(list(filter(lambda i: i <= N, l)))
print(r)


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

using namespace std;

const int MOD=1000000007;

/*inline int power(int x,int n,int M) {
	int tmp = 1;

	if (n > 0) {
		tmp = power(x, n / 2, M);
		if (!(n&1)) tmp = ((long long int)tmp*tmp) % M;
		else tmp = ((((long long int)tmp*tmp) % M)*x) % M;
	}
	return tmp;
}*/

inline int power(int x,int n,int M){
  int ret=1;
  int box=x;
  while(n){
    if(n&1)ret=((long long int)ret*box)%M;
    box=((long long int)box*box)%M;
    n>>=1;
  }
  return ret;
}

int main(){
  int N,M;
  cin>>N>>M;
  if(M==1){
    cout<<1<<endl;
    return 0;
  }
  vector<int>by(N*M+1,1);
  vector<int>rev_by(N*M+1,1);
  for(int i=1;i<=N*M;i++){
    by[i]=(1LL*by[i-1]*i)%MOD;
    rev_by[i]=power(by[i],MOD-2,MOD);
  }
  vector<vector<int>>dp(N+1,vector<int>(N+1));
  dp[0][0]=1;
  for(int i=0;i<=N;i++){
    for(int j=i;j<=N;j++){
      if(i)dp[i][j]=dp[i-1][j];
      if(j){
        int add=((long long int)dp[i][j-1]*rev_by[M-2])%MOD;
        add=((long long int)add*by[i+j*(M-1)-1])%MOD;
        add=((long long int)add*rev_by[i+j*(M-1)-1-(M-2)])%MOD;
        dp[i][j]+=add;
        dp[i][j]%=MOD;
      }
    }
  }
  cout<<((long long int)dp.back().back()*by[N])%MOD<<endl;
}

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

int main(){
  int N,sum=0;
  cin >>N;
  
  vector<int> v(N),c(N),gap(N);
  
  for (int i=0;i<N;i++){
    cin>>v.at(i);
  }
  for (int i=0;i<N;i++){
    cin>>c.at(i);
    gap.at(i)=v.at(i)-c.at(i);
    if(gap.at(i)>0){
      sum+=gap.at(i);
    }
  }
  cout <<sum<<endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	int n,d,x,a[110];
	int i,j,m;
	cin >> n >> d >> x;
	m=x+n;
	for(i=0;i<n;i++)
    {
        cin >> a[i];
        m+=(d-1)/a[i];
    }
    cout << m << endl;
	return 0;
}


Measured memory_bytes: 256
/*{{{*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(LL &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const LL &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1e6+10;
int main(){
    int A,B;
    R(A,B);
    int an=0;
    if(A>=B){
        an+=A;
        A--;
    }
    else{
        an+=B;
        B--;
    }
    an+=max(A,B);
    W(an);
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

ll c[20],d[20]={1ll},r[20]={1ll},m,ans[1][3],mt[3][3],tmp[3][3];

void mul1(){
	int i,j,k;
	for(i=0; i<1; ++i){
		for(j=0; j<3; ++j){
			for(k=0; k<3; ++k){
				tmp[i][j] += (ans[i][k]*mt[k][j])%m;
				tmp[i][j] %= m;
			}
		}
	}
	for(i=0; i<1; ++i){
		for(j=0; j<3; ++j){
			ans[i][j] = tmp[i][j];
			tmp[i][j] = 0ll;
		}
	}
}


void mul2(){
	int i,j,k;
	for(i=0; i<3; ++i){
		for(j=0; j<3; ++j){
			for(k=0; k<3; ++k){
				tmp[i][j] += (mt[i][k]*mt[k][j])%m;
				tmp[i][j] %= m;
			}
		}
	}
	for(i=0; i<3; ++i){
		for(j=0; j<3; ++j){
			mt[i][j] = tmp[i][j];
			tmp[i][j] = 0ll;
		}
	}
}

int main(void){
	int i;
	ll l,a,b,q;
	cin >> l >> a >> b >> m;
	ans[0][0] = 0ll; ans[0][1] = a%m; ans[0][2] = 1ll;
	for(i=0; i<18; ++i){
		d[i+1] = d[i]*10;
		r[i+1] = r[i]*10;
		r[i+1] %= m;
	}
	c[0] = -1ll;
	for(i=1; i<=18; ++i){
		--d[i];
		if(a>d[i]){
			c[i] = -1ll;
			continue;
		}else{
			c[i] = min((d[i]-a)/b,l-1);
		}
	}
	for(i=1; i<=18; ++i){
		if(a>d[i]){
			continue;
		}
		q = c[i]-c[i-1];
		mt[0][0] = r[i]; mt[0][1] = 0ll; mt[0][2] = 0ll;
		mt[1][0] = 1ll; mt[1][1] = 1ll; mt[1][2] = 0ll;
		mt[2][0] = 0ll; mt[2][1] = b%m; mt[2][2] = 1ll;
		while(q){
			if(q&1){
				mul1();
			}
			mul2();
			q /= 2;
		}
	}
	cout << ans[0][0] << endl;
	return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<functional>
#include<math.h>
#include<random>
using namespace std;
#define N (1000000000+7)
#define M 998244353
#define INF 1e16
typedef long long ll;
typedef pair<int,int> P;
 
const int inf = (int)1e9;

ll A(ll x){
    if(x>=0)return x;
    else return -x;
}
 
ll gcd(ll a, ll b) {
	if (b > a) {
		ll tmp = b;
		b = a;
		a = tmp;
	}
	if (a%b == 0)return b;
	else return gcd(b, a%b);
}
 
 
 map<int,int>mp;
 
 
 
int main(void){
	string s;
	cin>>s;
	int n = s.size();
	int sum = 0;
	vector<int>dp;
	dp.assign(n+1,inf);
	dp[0]=0;
	mp[0]=0;
	for(int i=0;i<n;i++){
		sum^=1<<(s[i]-'a');
		for(int j=0;j<26;j++){
			int bit = sum^(1<<j);
			if(mp.find(bit)!=mp.end()){
				dp[i+1]=min(dp[i+1],mp[bit]+1);
			}
		}
		if(mp.find(sum)!=mp.end()){
			dp[i+1]=min(dp[i+1],mp[sum]+1);
		}
		if(mp.find(sum)==mp.end()||mp[sum]>dp[i+1])mp[sum]=dp[i+1];
	}
	cout<<dp[n]<<endl;
    return 0;
}

Measured memory_bytes: 13492
#include <iostream>
#include <cstring>
#include <vector>
#include <set>
#include <list>
#include <map>
#include <deque>
#include <algorithm>
#include <utility>
#include <stdio.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
#define for1(i,n) for (ll i=0;i<(n);i++)
#define for2(i,m,n) for (ll i=(m);i<(n);i++)
#define for3(i,m,n,d) for (ll i=(m);i<(n);i+=(d))
#define DEBUG 0

ll N;
ll A[100010];

void solve()
{
    vector<string> anss;
    char cs[1000] = {0};
    cin >> N;
    for1(i,N) {
        cin >> A[i];
    }
    sort(&A[0],&A[N]);

    for2(i,1,N-1) {
        if (A[i] > 0) {
            sprintf(cs, "%lld %lld", A[0], A[i]);
            anss.push_back(string(cs));
            A[0] -= A[i];
        }
    }

    sprintf(cs, "%lld %lld", A[N-1], A[0]);
    anss.push_back(string(cs));
    ll ans = A[N-1] - A[0];

    for2(i,1,N-1) {
        if (A[i] <= 0) {
            sprintf(cs, "%lld %lld", ans, A[i]);
            anss.push_back(string(cs));
            ans -= A[i];
        }
    }

    cout << ans << endl;
    for (string s : anss) {
        cout << s << endl;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    do {
        solve();
    } while (DEBUG);
}


Measured memory_bytes: 9588
#include <iostream>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cmath>
#include <stack>
typedef long long ll;
#define INF 0x3f3f3f3f

using namespace std;

int main(int argc, char *argv[]) {
	int N, K;
	cin >> N >> K;
	long long ans = 0;
	if(K % 2)
	{
		long long t = 0;
		for(int i = 1; i <= N; i++)
		{
			if(i % K == 0)
			{
				t++;
			}	
		}
		ans = t * t * t;
	} else {
		long long t1 = 0, t2 = 0;
		for(int i = 1; i <= N; i++)
		{
			if(i % K == 0)
			{
				t1++;
			}
			if(i % K == K / 2)
			{
				t2++;
			}
		}
		ans = t1 * t1 * t1 + t2 * t2 * t2;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define REP2(i,x,n) for (int i = x; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);
static const int INF = 1e9+7;



int main(){
  int n;
  string s;
  cin >> n >> s;
  int mxcnt = 0;
  REP2(k,1,n-1){
    map<char, bool> mp;
    int cnt = 0;
    REP2(i,0,k){
      mp[s[i]] = true;
    }
    REP2(i,k,n){
      if(mp[s[i]] == true){
        cnt++;
        mp[s[i]] = false;
      }
    }
    mxcnt = max(mxcnt, cnt);
  }

  cout << mxcnt << endl;
  
  return 0;
}


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

#define max 100000

int main()
{
    int *prime_sum;
    bool *is_prime;
    prime_sum = new int[max + 1];
    is_prime = new bool[max + 1];
    std::fill(prime_sum, prime_sum + max + 1, 0);
    is_prime[0] = is_prime[1] = false;
    std::fill(is_prime + 2, is_prime + max + 1, true);
    for (int i = 2; i <= max; i++)
    {
        if (!is_prime[i])
            continue;
        for (int j = i * 2; j <= max; j += i)
            is_prime[j] = false;
    }
    for (int i = 2; i <= max; i++)
        prime_sum[i] = prime_sum[i - 1] + (is_prime[i] && is_prime[(i + 1) /2]);
    printf("\n");
    int q;
    scanf("%d", &q);
    for (int i = 0; i < q; i++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", prime_sum[r] - prime_sum[l - 1]);
    }

    delete[] is_prime;
    delete[] prime_sum;
    return 0;
}

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

int mynot(int a){
	if(a==1) return 0;
	return 1;
}

int myand(int a,int b){
	if(a==1 && b==1) return 1;
	return 0;
}

int myor(int a,int b){
	if(a==0 && b==0) return 0;
	return 1;
}

int naraba(int a,int b){
	if(a==0 || (a==1 && b==1)) return 1;
	return 0;
}

string s;
int bit=0;
int p=0;

int to_int(char a){
	if(a=='T') return 1;
	if(a=='F') return 0;
	int k=a-'a';
	if(bit & (1<<k)) return 1;
	return 0;
}


int calc(){
	if(isalpha(s[p])) return to_int(s[p++]);

	if(s[p]=='-'){
		p++;
		return mynot(calc());
	}

	if(s[p]=='('){
		p++;
		int res1=calc();
		if(s[p]=='*'){
			p++;
			int res2=calc();
			p++;
			return myand(res1,res2);
		}
		else if(s[p]=='+'){
			p++;
			int res2=calc();
			p++;
			return myor(res1,res2);
		}
		else if(s[p]=='-'){
			p+=2; //>を読み飛ばす
			int res2=calc();
			p++;
			return naraba(res1,res2);
		}
	}
	cerr<<"Error"<<endl;
	return -1;
}


int main()
{
	while(cin>>s && s[0]!='#'){
		bool ok=true;
		for(bit=0;bit<(1<<11);bit++){
//			cout<<bit<<endl;
			p=0;
			int ans1=calc();
			p++; //=読み飛ばし
			int ans2=calc();
			if(ans1!=ans2){ok=false;break;}
		}
		if(ok) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}

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

int main()
{
	long long int N,L;
	cin>>N>>L;
	long long int arr[N],len[N];
	for(long long int i=1;i<=N;i++)
	{
		cin>>arr[i];
	}
	bool flag=0;
	long long int index=0;
	for(long long int i=1;i<=N-1;i++)
	{
		len[i]=arr[i]+arr[i+1];
		if(len[i]>=L)
			{
				flag=1;
				index=i;
			}
	}
	if(flag)
	{
		cout<<"Possible"<<endl;
		for(long long int i=1;i<index;i++)
		{
			cout<<i<<endl;
		}
		for(long long int i=N-1;i>=index+1;i--)
		{
			cout<<i<<endl;
		}
		cout<<index<<endl;
	}
	else
	{
		cout<<"Impossible"<<endl;
	}

	return 0;
}

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

int main()
{
  long long int num;
  cin >> num;

  long long ans = pow(10, 10);

  // sqrt(num)までの範囲で調べればよい
  for(int i = 1; i <= sqrt(num); ++i){
    long long int tmp = 1;
    if(num % i == 0){
      tmp = num / i;
    }
    else continue;

    // tmpのうちで, 一番小さな値が欲しい
    if(ans > tmp) ans = tmp;
    else continue;
  }

  // ansの桁数が求める答え
  int final_ans = log10(ans) + 1;
  cout << final_ans << endl;

  return 0;
  
}


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

using namespace std;

int main(){

	int n,k;
	cin>>n>>k;
	int ans=1;
	while(n/k!=0){
		n=n/k;
		ans++;
	}
	cout<<ans;
	cout<<endl;

	return 0;
}


Measured memory_bytes: 256
N = int(input())
B = list(map(int, input().split()))
ORI_B = B[:]

ans = []
for i in range(N): # N回繰り返せば十分
    tgt = -1
    for i in reversed(range(len(B))):
        if B[i] == i+1:
            # B[i]をけす
            tgt = i
            break
    if tgt == -1:
        break
    ans.append(B[i])
    del B[i]

ans = ans[::-1]

if len(ans) == len(ORI_B):
    print('\n'.join(map(str, ans)))
else:
    print(-1)


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


int main() {
  int a,b,c,d;
  cin >> a>>b>>c>>d;
  
  if((c-1)/b<=(a-1)/d){
     cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
  
  
}







Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
vector<int> segment;
int n,k,a[100001];

int getsum(int index){
    long long sum = 0;
    index = index + 1;
    while(index){
        sum += segment[index];
        index -= index & (-index);
    }
    sum %= 1000000007;
    if(sum < 0){
        sum += 1000000007;
    }
    return sum;
} 

void update(int index , int val){
    index = index + 1;
    while (index <= k+1){
        long long b = segment[index]+val;
        b %= 1000000007;
        if(b < 0){
            b += 1000000007;
        }
        segment[index] = b;
        index += index & (-index);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    cin >> n >> k;
    segment.resize(k+2,0);
    for(int i = 0 ; i < n ; i += 1){
        cin >> a[i];
    }
    update(0,1);
    for(int i = 0 ; i < n ; i += 1){
        for(int j = k ; j > 0 ; j -= 1){
            long long sum = getsum(j)-getsum(max(-1,j-a[i]-1))-getsum(j)+getsum(j-1);
            sum %= 1000000007;
            if(sum < 0){
                sum -= 1000000007;
            }
            update(j,sum);
        }
    }
    long long ans = getsum(k)-getsum(k-1);
    ans %= 1000000007;
    if(ans < 0){
        ans += 1000000007;
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

vector<ll> regularize(vector<ll> v) {
    vector<vector<ll>> candidates;
    for (ll i = 0; i < 4; i++) {
        candidates.push_back(v);
        rotate(v.begin(), v.begin() + 1, v.end());
    }
    sort(candidates.begin(), candidates.end());
    return candidates.front();
}

int main() {
    ll N;
    cin >> N;
    vector<vector<ll>> C(N, vector<ll>(4));

    map<vector<ll>, ll> mp;
    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < 4; j++) {
            cin >> C[i][j];
        }

        C[i] = regularize(C[i]);
        mp[C[i]]++;
    }

    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        for (ll j = i + 1; j < N; j++) {
            for (ll k = 0; k < 4; k++) {
                //上面はC[i]
                //下面はC[j]を裏返してkだけ回したもの
                vector<ll> u = C[i];
                vector<ll> b(4);
                //裏返す
                b[0] = C[j][1];
                b[1] = C[j][0];
                b[2] = C[j][3];
                b[3] = C[j][2];

                //回転
                rotate(b.begin(), b.begin() + k, b.end());

                ll tmp = 1;

                vector<vector<ll>> used;
                used.push_back(C[i]);
                used.push_back(C[j]);

                for (ll l = 0; l < 4; l++) {
                    //lとl + 1で作られる面について考える
                    ll m = (l + 1) % 4;
                    vector<ll> key(4);
                    key[0] = u[l];
                    key[1] = b[l];
                    key[2] = b[m];
                    key[3] = u[m];
                    key = regularize(key);

                    ll num = mp[key];
                    //既に使ったものとの重複を除く
                    for (auto u : used) {
                        if (key == u) {
                            num--;
                        }
                    }

                    if (key[0] == key[1] && key[1] == key[2] && key[2] == key[3]) {
                        //全て同じならどの回転でも良い
                        num *= 4;
                    } else if (key[0] == key[2] && key[1] == key[3]) {
                        //対角線が同じなら180度回転だけ良い
                        num *= 2;
                    }
                    
                    tmp *= num;
                    used.push_back(key);
                }

                ans += tmp;
            }
        }
    }

    cout << ans / 3 << endl;
}

Measured memory_bytes: 160000
#!/usr/bin/env python3

from collections import deque


class PriorityQueue:
    def __init__(self, size):
        self.tree = [None] * size
        self.bottom = 0

    def add(self, data):
        n = self.bottom
        self.bottom += 1
        self.tree[n] = data
        while n != 0:
            parent = (n - 1) // 2
            if self.tree[parent][1] < self.tree[n][1]:
                self.tree[parent], self.tree[n] = (
                    self.tree[n],
                    self.tree[parent],
                )
                n = parent
            else:
                return

    def top(self):
        return self.tree[0]

    def size(self):
        return self.bottom

    def pop_top(self):
        rv = self.tree[0]
        self.tree[0] = self.tree[self.bottom - 1]
        self.bottom -= 1
        n = 0
        while True:
            child1 = 2 * n + 1
            if child1 >= self.bottom:
                return rv
            child2 = 2 * n + 2
            if child2 >= self.bottom:
                child2 = child1

            if (
                self.tree[n][1] > self.tree[child1][1]
                and self.tree[n][1] > self.tree[child2][1]
            ):
                return rv
            elif self.tree[child1][1] > self.tree[child2][1]:
                self.tree[n], self.tree[child1] = (
                    self.tree[child1],
                    self.tree[n],
                )
                n = child1
            else:
                self.tree[n], self.tree[child2] = (
                    self.tree[child2],
                    self.tree[n],
                )
                n = child2
        return rv


def solve(N, M, A, B):
    ans = 0
    # 日付順にソートする
    all_works = deque(sorted(zip(A, B), key=lambda x: x[0]))
    pq = PriorityQueue(N)

    for d in range(1, M+1):
        # print('d=', d)
        # 今日が期限の仕事があれば追加
        while all_works and all_works[0][0] == d:
            work = all_works.popleft()
            pq.add(work)
        # print('all_works', all_works)
        # print('pq=', pq.tree)
        # 優先キューから最優先の仕事を選択する
        if pq.size():
            work = pq.pop_top()
            ans += work[1]

    return ans


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for idx in range(N):
        A[idx], B[idx] = map(int, input().split())

    ans = solve(N, M, A, B)

    print(ans)


Measured memory_bytes: 20024
#include <stdio.h>
#include <string.h>

int main(void)
{
	int score[101][101];
	int point[101];
	int n;
	int a, b, c, d;
	int i, j;
	int rank;
	
	memset(score, 0, sizeof(score));
	
	
	scanf("%d", &n);
	
	for (i = 0; i < n * (n - 1) / 2; i++){
		scanf("%d%d%d%d", &a, &b, &c, &d);
		
		score[a][b] = c;
		score[b][a] = d;
	}
	
	for (i = 1; i <= n; i++){
		point[i] = 0;
		for (j = 1; j <= n; j++){
			if (i != j){
//				printf("(%d:%d - %d:%d)", i, score[i][j], j, score[j][i]);
				if (score[i][j] > score[j][i]){
					point[i] += 3;
				}
				else if (score[i][j] == score[j][i]){
					point[i]++;
				}
			}
		}
		
//		printf("<%d>", point[i]);
		
	}
	
	for (i = 1; i <= n; i++){
		rank = 1;
		for (j = 1; j <= n; j++){
			if (point[i] < point[j]){
				rank++;
			}
		}
		printf("%d\n", rank);
	}
	
	return (0);
}

Measured memory_bytes: 648
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
const long long mod = 1e9+7;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};
const int ddx[4] = {1,1,-1, -1};
const int ddy[4] = {1,-1,-1,1};
//////////////////////////////////

int main(){
  int k, n; cin >> k >> n;
  vector<int> a(n);
  for(int i=0; i<n; i++) cin >> a[i];

  vector<long long> b(n);
  b[0] = a[0] + (k - a[n-1]);
  for(int i=1; i<n; i++) {
    b[i] = a[i] - a[i-1];
  }
  sort(all(b));
  long long ans = accumulate(all(b), 0) - b[n-1];
  cout << ans << endl;

  return 0;
}


// EOF


Measured memory_bytes: 2560
#include <iostream>

using namespace std;

int main(){
	int a[200100]; long long s[200100];
	int N; cin>>N;
	for(int n=0; n<N; n++){
		cin>>a[n];
		if(n)
			s[n] = s[n-1]+a[n];
		else
			s[n] = a[n];
	}
	long long ans = abs(a[0]-(s[N-1]-a[0]));
	for(int x=1; x<N-1; x++){
		ans = min(ans, abs((s[N-1]-s[x])-s[x]));
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2560
N,K=map(int,input().split())
A=list(map(int,input().split()))
first=A[0]
end=A[K-1]
#print(first,end)
for i in range(K,N):
    if A[i]>first:
        print("Yes")
    else:
        print("No")
    first=A[i-K+1]
    end=A[i]
    #print(first,end)

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

struct UnionFind {
  vector<int> d;
  UnionFind(int n = 0): d(n, - 1) {}
  int find(int x) {
    if(d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if(x == y) return false;
    if(d[x] > d[y]) swap(x, y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y);}
  int size(int x) {return -d[find(x)];}
};

int main(){
  int n, m, k;
  cin >> n >> m >> k;
  vector<int> deg(n);
  UnionFind uf(n);
  rep(i, m){
    int a, b;
    cin >> a >> b;
    a--; b--;
    uf.unite(a, b);
    deg[a]++;
    deg[b]++;
  }
  vector<vector<int>> block(n);
  rep(i, k){
    int c, d;
    cin >> c >> d;
    c--; d--;
    block[c].push_back(d);
    block[d].push_back(c);
  }
  rep(i, n){
    int ans = uf.size(i) - 1 - deg[i];
    for(int x: block[i]){
      if(uf.same(i, x)) ans--;
    }
    printf("%d%c", ans, i == n - 1 ? '\n' : ' ');
  }
}

Measured memory_bytes: 6784
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
using ll=long long;
constexpr ll mod=1000000007;
constexpr int inf=1000000000;
constexpr ll linf=1000000000000000000;

ll modpow(ll x,ll n){
    ll res=1;
    while(n>0){
        if(n&1)res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}

int main(){
    int n;
    cin>>n;
    ll a[n];
    rep(i,n)cin>>a[i];
    ll d[n-1];
    rep(i,n-1)d[i]=a[i+1]-a[i];
    ll ans=0;
    ll sum=0;
    rep(i,n-1){
        sum=(sum+modpow(i+1,mod-2))%mod;
        ans=(ans+d[i]*sum);
    }
    rep(i,n-1){
        ans=(ans*(i+1))%mod;
    }
    cout<<ans<<endl;
}


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

using namespace std;

typedef long long ll;
#define fi first
#define se second
#define pb push_back

int main() {
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll a, b;
    scanf("%lld %lld", &a, &b);
    ll g = __gcd(a, b), ans = 1;
    for (ll i = 2; i * i <= g; i++) {
        if (g % i == 0) {
            ans++;
            while (g % i == 0) {
                g /= i;
            }
        }
    }
    if (g > 1) ans++;
    printf("%lld", ans);
    return 0;
}


Measured memory_bytes: 3812
#include<stdio.h>

int main(){
	int S=0;
	int h, m, s;
	
	scanf("%d", &S);
	h = S/3600;
	m = (S%3600)/60;
	s = (S%3600)%60;
	printf("%d:%d:%d\n", h, m, s);
	
	return 0;
}


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

// Begin Header {{{
using namespace std;

#ifndef DEBUG
#define dump(...)
#endif

#define all(x) x.begin(), x.end()
#define rep(i, n) for (intmax_t i = 0, i##_limit = (n); i < i##_limit; ++i)
#define reps(i, b, e) for (intmax_t i = (b), i##_limit = (e); i <= i##_limit; ++i)
#define repr(i, b, e) for (intmax_t i = (b), i##_limit = (e); i >= i##_limit; --i)
#define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__)

constexpr size_t    operator""_zu(unsigned long long value) { return value; };
constexpr intmax_t  operator""_jd(unsigned long long value) { return value; };
constexpr uintmax_t operator""_ju(unsigned long long value) { return value; };

constexpr int INF = 0x3f3f3f3f;
constexpr intmax_t LINF = 0x3f3f3f3f3f3f3f3f_jd;

template <class T, class Compare = less<>>
using MaxHeap = priority_queue<T, vector<T>, Compare>;
template <class T, class Compare = greater<>>
using MinHeap = priority_queue<T, vector<T>, Compare>;

inline void input() {}
template <class Head, class... Tail>
inline void input(Head&& head, Tail&&... tail) {
    cin >> head;
    input(forward<Tail>(tail)...);
}

template <class T>
inline istream& operator>>(istream &is, vector<T> &vec) {
    for (auto &e: vec) {
        is >> e;
    }
    return is;
}

inline void output() { cout << "\n"; }
template <class Head, class... Tail>
inline void output(Head&& head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail)) {
        cout << " ";
    }
    output(forward<Tail>(tail)...);
}

template <class T>
inline ostream& operator<<(ostream &os, const vector<T> &vec) {
    static constexpr const char *delim[] = {" ", ""};
    for (const auto &e: vec) {
        os << e << delim[&e == &vec.back()];
    }
    return os;
}

template <class T>
inline vector<T> makeVector(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto makeVector(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(makeVector<T>(initValue, args...))>(sz, makeVector<T>(initValue, args...));
}

template <class Func>
class FixPoint : Func {
public:
    explicit constexpr FixPoint(Func&& f) noexcept : Func(forward<Func>(f)) {}

    template <class... Args>
    constexpr decltype(auto) operator()(Args&&... args) const {
        return Func::operator()(*this, std::forward<Args>(args)...);
    }
};

template <class Func>
static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept {
    return FixPoint<Func>{forward<Func>(f)};
}

template <class T>
inline bool chmax(T &a, const T &b) noexcept {
    return b > a && (a = b, true);
}

template <class T>
inline bool chmin(T &a, const T &b) noexcept {
    return b < a && (a = b, true);
}

template <class T>
inline T diff(const T &a, const T &b) noexcept {
    return a < b ? b - a : a - b;
}
// End Header }}}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    var(string, s);

    if (s == "Sunny") {
        output("Cloudy");
    } else if (s == "Cloudy") {
        output("Rainy");
    } else {
        output("Sunny");
    }

    return 0;
}


Measured memory_bytes: 768
#include <iostream>
#include<algorithm>

using namespace std;

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

int main(){
  int n;
  cin >> n;
  int a[n],i;
  for(i=0;i<n;i++) cin >> a[i];
  int l[n],r[n];
  l[1] = a[0];
  for(i=2;i<n;i++) l[i] = gcd(l[i-1],a[i-1]);
  r[1] = a[n-1];
  for(i=2;i<n;i++) r[i] = gcd(r[i-1],a[n-i]);
  l[0] = r[n-1];
  r[0] = l[n-1];
  int ans=1;
  for(i=0;i<n;i++) if(ans<gcd(l[i],r[n-1-i])) ans = gcd(l[i],r[n-1-i]);
  cout << ans << endl;
}
  


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

int n,x,t;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>x>>t;
    
    if (n%x==0){
        cout<<(n/x)*t;
    }
    else{
        cout<<(n/x+1)*t;
    }
    
    
    
    
    
    
    
    
    
    return 0;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
using graph = vector<vector<pii>>;

vector<ll> dijkstra(int s, const graph& G) {
	const ll INF = 1e18;
	vector<ll> d(G.size(), INF);
	priority_queue<pii, vector<pii>, greater<>> pq;
	pq.emplace(0, s);
	while (!pq.empty()) {
		auto p = pq.top(); pq.pop();
		ll dist = p.first;
		int v = p.second;
		if (d[v] != INF) continue;
		d[v] = dist;
		for (auto& e : G[v]) if (d[e.first] == INF) {
			pq.emplace(dist + e.second, e.first);
		}
	}
	return d;
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int n, m, s, t;
	cin >> n >> m >> s >> t; --s, --t;
	graph G1(n), G2(n);
	for (int i = 0; i < m; i++) {
		int u, v;
		ll a, b;
		cin >> u >> v >> a >> b; --u, --v;
		G1[u].emplace_back(v, a);
		G1[v].emplace_back(u, a);
		G2[u].emplace_back(v, b);
		G2[v].emplace_back(u, b);
	}
	auto d1 = dijkstra(s, G1);
	auto d2 = dijkstra(t, G2);
	vector<ll> res(n);
	ll d = LLONG_MAX, aaa = 1000000000000000LL;
	for (int i = n - 1; i >= 0; i--) {
		d = min(d, d1[i] + d2[i]);
		res[i] = max(0LL, aaa - d);
	}
	for (int i = 0; i < n; i++) {
		cout << res[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 19152
const main = (lines: string) => {
  const data = lines.split("\n");
  const N = parseInt(data[0]);
  const weights = data[1].split(" ").map(str => parseInt(str));
  let minSum, maxSum;
  let absArr: number[] = [];
  let answer;


  for (let i = 1; i < N; i++) {
    minSum = weights.slice(0, i).reduce((a, x) => a+=x, 0)
    maxSum = weights.slice(i, N).reduce((a, x) => a+=x, 0)

    absArr.push(Math.abs(minSum - maxSum))
  }

  absArr.reduce((a, x) => a+=x, 0)

  console.log(Math.min.apply(null, absArr))
};

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

Measured memory_bytes: 7624
using System;
using System.IO;
using System.Linq;

    class Program
    {
        static void Main(string[] args)
        {
            var KN = Console.ReadLine().Split(' ');

            var K = int.Parse(KN[0]);
            var N = int.Parse(KN[1]);

            var distances = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
            long longdis = 0;

            for(int i =0; i < N -1; i++)
            {
                var dis = Math.Abs(distances[i] - distances[i + 1]);
                if(dis > longdis)
                {
                    longdis = dis;
                }
            }

            var final = K - distances[N - 1] + distances[0];

            if(final > longdis)
            {
                longdis = final;
            }

            var ret = K - longdis;

            MyConsoleWrightLine(ret.ToString());
        }

        private static void MyConsoleWrightLine(string str)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            Console.WriteLine(str);

            Console.Out.Flush();
        }
}


Measured memory_bytes: 36244
from math import factorial

N, A, B = map(int, input().split())
v = list(map(int, input().split()))
v.sort()
v.reverse()

maxave = 0

for i in range(A, B+1):
    if sum(v[:i]) / i < maxave:
        continue
    
    counter1 = 1
    for j in range(i-2, -1, -1):
        if v[j] == v[i-1]:
            counter1 += 1
        else:
            break

    counter2 = v.count(v[i-1])

    now_counter = factorial(counter2) // factorial(counter2 - counter1) // factorial(counter1)

    if sum(v[:i]) / i == maxave:
        nummax += now_counter
    else:
        nummax = now_counter
        maxave = sum(v[:i]) / i
    
print(maxave)
print(nummax)


Measured memory_bytes: 3188
MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


def modCombi(n, r):
    global MOD
    return (modFacts[n] * invs[n - r] * invs[r]) % MOD


N, M, K = map(int, input().split())
modFacts, invs = prepare(N * M)
var = modCombi(N * M - 2, K - 2)

ans = 0
if N < M:
    N, M = M, N
L = [0] * (N + 1)
for i in range(1, N + 1):
    L[i] = L[i - 1] + i
for x in range(1, N + 1):
    for y in range(1, M + 1):
        Sx = (M * (L[N - x] + L[x - 1])) % MOD
        Sy = (N * (L[M - y] + L[y - 1])) % MOD
        ans += (Sx + Sy) % MOD

print((ans * invs[2] * var) % MOD)



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

using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using pii = pair<int, int>;

#define INF 1e9
#define MOD 1000000007
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = (a); i > (b); i--)
#define each(x, v) for (auto& x: (v))
#define all(x) (x).begin(), (x).end()
#define print(x) cout << (x) << endl

void solve();
void in(){} template<class T, class... U> void in(T &t, U &...u){ cin >> t; in(u...); }
int main() { cin.tie(0); ios::sync_with_stdio(0); solve(); }

void solve() {
  int N;
  in(N);
  int ans = 0;
  int prev = INF;
  int bi;
  rep(i, 0, N - 1) {
    in(bi);
    ans += min(prev, bi);
    prev = bi;
  }
  print(ans + bi);
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <array>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>
#include <stack>
#include <utility>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <climits>
#include <bitset>
#include <random>
#include <functional>
#include <sstream>
#include <iomanip>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); i++)
#define FOR(i, m, n) for(int i=(m);i<(n);i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define REVE(x) reverse((x).begin(),(x).end())
#define mp make_pair
#define pb push_back

typedef long long LL;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef vector<LL> VL;

int main() {
	string s; cin >> s;
	cout << min(count(all(s), '0'), count(all(s), '1')) * 2 << endl;
}

Measured memory_bytes: 512
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
ll input[200005];
ll n;
ll  l,r,ans,mid;
ll  lib[200005];
ll sum[200005];
ll  tree[200005];
inline ll lowbit(ll x) {
	return x&(-x);
	}
ll minn=0;
ll maxx=0;
void add(ll x) {
	for(ll i=x; i<=maxx; i+=lowbit(i))tree[i]+=1;
	}
ll summ(ll x) {
	ll kk=0;
	for(ll i=x; i; i-=lowbit(i))kk+=tree[i];
	return kk;
	}
bool check(ll x) {
	memset(tree,0,sizeof(tree));
	ll anss=0;
	minn=0;
	maxx=0;
	for(ll i=1; i<=n; i++) {
		if(input[i]>=x)sum[i]=1;
		else sum[i]=-1;
		}
	for(ll i=1; i<=n; i++)
		sum[i]+=sum[i-1],minn=min(minn,sum[i]);
	for(ll i=0; i<=n; i++)
		sum[i]=sum[i]-minn+1,maxx=max(maxx,sum[i]);
	for(ll i=0; i<=n; i++) {
		anss+=summ(sum[i]);
		add(sum[i]);
		}
	return anss>=n*(n+1)/4;
	}
int main() {
	scanf("%lld",&n);
	r=0;
	for(ll i=1; i<=n; i++) {
		scanf("%lld",&input[i]);
		r=max(r,input[i]);
		}
	l=1;
	while(l<=r) {
		mid=(l+r)>>1;
		if(check(mid)) {
			ans=mid;
			l=mid+1;
			}
		else r=mid-1;
		}
	cout<<ans;
	}


Measured memory_bytes: 6400
import java.util.*;
class Main{
	public static void main(String args[]){
		Scanner s=new Scanner(System.in);
		while(true){
			int a=s.nextInt();
			int b=s.nextInt();
			String atari[]=new String[a];
			int earn[]=new int[a];
			if(a+b==0)System.exit(0);
			for(int i=0;i<a;i++){
				atari[i]=s.next();
				earn[i]=s.nextInt();
			}
			int ret=0;
			for(int i=0;i<b;i++){
				String now=s.next();
				for(int j=0;j<a;j++){
					boolean ok=true;
					for(int k=0;k<8;k++)
						if(atari[j].charAt(k)!='*'&&atari[j].charAt(k)!=now.charAt(k))ok=false;
					if(ok)ret+=earn[j];
				}
			}
			System.out.println(ret);
		}
	}
}

Measured memory_bytes: 12000
package main

import (
	"fmt"
	"os"
	"bufio"
	"strconv"
	"container/list"
	"strings"
)

var sc = bufio.NewScanner(os.Stdin)

func nextString() string {
	sc.Scan()
	return sc.Text()
}

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

func main() {
	sc.Split(bufio.ScanWords)

	inputLines := nextInt()
	linkList := list.New()

	for i := 0; i < inputLines; i++ {
		command := nextString()

		switch command {
		case "insert":
			key := nextString()
			
			linkList.PushFront(key)
		case "delete":
			key := nextString()
			for e := linkList.Front(); e != nil; e = e.Next() {
				if v := e.Value.(string); v == key {
					linkList.Remove(e)	
					break
				}
			}
		case "deleteFirst":
			linkList.Remove(linkList.Front())
		case "deleteLast":
			linkList.Remove(linkList.Back())
		default:
			fmt.Println("Unknown Command.")
		}
	}

	array := make([]string, linkList.Len())
	e := linkList.Front()
	for i := 0; i < linkList.Len(); i++ {
		array[i] = e.Value.(string)
		e = e.Next()
	}

	fmt.Println(strings.Join(array, " "))
}


Measured memory_bytes: 115028