akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
 
/*** Template Begins ***/
 
typedef long long    ll;
typedef pair<ll,ll>  pll;
typedef pair<ll, pair<int, int> > plll;
typedef vector<long long>  vll;
typedef vector<pll>  vp;
typedef long double ld;
#define pb           push_back
#define INF          INT_MAX/10
#define F            first
#define S            second
#define mp           make_pair
#define ios          ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define hell         1000000007
// #define h 998244353
#define all(a)       (a).begin(),(a).end()
ll power(ll x, ll y, ll p){ ll res = 1;x = x % p;while (y > 0){ if (y & 1) res = (res*x) % p;y = y>>1;x = (x*x) % p;} return res; } 
 
// Debug //
 
#define trace(x)                 cerr << #x << ": " << x << endl;
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
 
// Constants //
 
 
/*** Template Ends ***/
ld p[3005];
ld cache[3005][3005];
ld calculate(ll n,ll c)
{
  // cout<<n<<c;
  if(n<1)
  {
    return (c==0);
  }
  // if(c==0)
  // {
  //   return 
  // }
  if(cache[n][c]!=-1)
    return cache[n][c];
  if(c==0)
    return cache[n][c] = (1-p[n])*calculate(n-1,c);
  else
    return cache[n][c] = p[n]*calculate(n-1,c-1)+(1-p[n])*calculate(n-1,c);
}
void solve()
{
  ll n,i,j;
  cin>>n;
  for(i=1;i<=n;i++)
    cin>>p[i];
  for(i=1;i<=n;i++)
    for(j=0;j<=n;j++)
      cache[i][j]=-1;
  ld ans=0;
  // ans = calculate(n,1);  
  for(i=n/2+1;i<=n;i++)
  {
    ans+=calculate(n,i);
  }  
  cout.precision(12);
  cout<<fixed<<ans;
}

int main(){ 
  ios;
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
  ll t;
  // cin >> t;
  t=1;
  while(t--)
    solve();
 
  return 0;
}

Measured memory_bytes: 141312
#include<bits/stdc++.h>
constexpr long long INFL = 1LL << 60;
constexpr int INF = 1 << 30;

using namespace std;

using ll = long long;
using P = tuple<int, int>;
using iarr = valarray<int>;

int main()
{
    string S;
    cin >> S;
    int K = 0;
    string pre;
    string now;
    for(int i = 0; i < S.size(); ++i){
        now += S[i];
        if(now != pre){
            K++;
            pre = now;
            now = "";
            if(i == S.size()) K++;
        }
    }
    cout << K << endl;

    return 0;
}


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

int t = INT_MAX;

int recur(int n,int c){
  if (c > t){
    return c;
  }
  if (n%2 == 0){
    return recur(n/2,c+1);
  }else{
    return c;
  }
}

int main(){
  int n;
  cin >> n;
  for (int i=0;i<n;i++){
    int a;
    cin >> a;
    int c;
    c = recur(a,0);
    if (c < t){
      t = c;
    }
  }
  cout << t << endl;
  return 0;
}



Measured memory_bytes: 384
#![allow(unused_imports)]
#![allow(unused_variables)]

use itertools::Itertools;
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        x: i64,
    }

    let mut ans = (0, 0);
    for a in -1000..1000 {
        for b in -1000..1000 {
            if x == (a as i64).pow(5) - (b as i64).pow(5) {
                ans = (a, b);
            }
        }
    }

    println!("{} {}", ans.0, ans.1);
}


Measured memory_bytes: 2152
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <fstream>
#include <cstring>
#include <string>
#include <set>
#include <map>
using namespace std;
//ifstream cin();
//ofstream cout();
int main(){
	char a,b;
	cin>>a>>b;
	if(a>b)cout<<'>';
	if(a<b)cout<<'<';
	if(a==b)cout<<'=';
	ios::sync_with_stdio(false);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<bool> vb;

int main() {
  ll n, res = 1;
  cin >> n;
  rep(i, n) res = (res * (i + 1)) % (1000000000 + 7);
  cout << res << endl;
}

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

#define li long long int
#define rep(i, to) for (li i = 0; i < ((li)(to)); i++)
#define repp(i, start, to) for (li i = (li)(start); i < ((li)(to)); i++)
#define allof(v) (v).begin(), (v).end()

li n, h;
li a[100100];
li b[100100];

inline li divup(li x, li y) {
	li res = x / y;
	if (x % y > 0)res++;
	return res;
}

int main(void)
{
	cin >> n >> h;
	rep(i, n) {
		cin >> a[i] >> b[i];
	}
	sort(a, a + n);
	sort(b, b + n);
	vector<li> throw_list;
	rep(i, n) {
		if (b[i] > a[n - 1]) {
			throw_list.push_back((b[i]));
		}
	}
	reverse(allof(throw_list));

	li res = 0;
	for (auto && bb : throw_list) {
		h -= bb;
		res++;
		if (h <= 0) {
			cout << res << endl;
			return 0;
		}
	}

	res += divup(h, a[n - 1]);
	cout << res << endl;



	return 0;
}

Measured memory_bytes: 2936
using System;

public class Program
{
  public static void Main(string[] args)
  {
    string[] nm = Console.ReadLine().Split(' ');
    int n = int.Parse(nm[0]);
    int m = int.Parse(nm[1]);
    int[,] MatNxM = new int[n,m];
    for(int i = 0;i < n;i++)
    {
      string[] tmp = Console.ReadLine().Split(' ');
      for(int j = 0;j < m;j++)
      {
        MatNxM[i,j] = int.Parse(tmp[j]);
      }
    }
    int[,] MatMx1 = new int[m,1];
    for(int i = 0;i < m;i++)
    {
      MatMx1[i,0] = int.Parse(Console.ReadLine());
    }
    int[,] MatNx1 = new int[n,1];
    for(int i = 0;i < n;i++)
    {
      for(int j = 0;j < m;j++)
      {
        MatNx1[i,0] += MatNxM[i,j] * MatMx1[j,0];
      }
    }
    for(int i = 0;i < n;i++)
    {
      for(int j = 0;j < 1;j++)
      {
        Console.WriteLine(MatNx1[i,j]);
      }
    }
  }
}

Measured memory_bytes: 9276
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <map>
#include <functional>
#include <cmath>
using namespace std;
#pragma warning(disable: 4996)
string S; int minx;
int main() {
	cin >> S;
	minx = S.size();
	for (int i = 0; i < S.size() - 1; i++) {
		if (S[i] != S[i + 1]) { minx = min(minx, max((int)S.size() - i - 1, i + 1)); }
	}
	cout << minx << endl;
	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <numeric>
#include <iomanip>
#include <set>
#include <string.h>

using namespace std;

typedef long long ll;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REP3(i,st,en) for(ll (i)=(st);(i)<(en);(i)++)

using P = pair<ll, ll>;
const int MOD = 1e9+7;
const ll INF = 1e+14;
const double PI = 3.14159265349;



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

  ll r;
  cin >> r;

  cout << r*r << "\n";
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (ll i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define pb push_back
using ll = long long;
using ld=long double;
using vin=vector<int>;
using vvin=vector<vin>;
using vll=vector<ll>;
using vvll=vector<vll>;
using vst=vector<string>;
using P = pair<ll,ll>;
const int inf=1e9+7;
const ll INF=9e18;
template <typename T> bool chmin(T &a, const T& b){if(a > b){a = b;return true;}return false;}
template <typename T> bool chmax(T &a, const T& b){if(a < b){a = b;return true;}return false;}
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

int lgcd[110000];
int rgcd[110000];

int main(){cout<<fixed<<setprecision(20);
		   int n;
           cin>>n;
           vin a(n+1);
           rep(i,1,n+1)cin>>a[i];
           
           rep(i,1,n+1){
            lgcd[i]=__gcd(a[i],lgcd[i-1]);
           }
           for(int i=n;i>=1;i--){
            rgcd[i]=__gcd(a[i],rgcd[i+1]); 
           }
           int ans=0;
           rep(i,1,n+1){
             chmax(ans,__gcd(lgcd[i-1],rgcd[i+1]));
           }
           cout<<ans<<endl;
}

Measured memory_bytes: 4500
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;

int c[10][10];

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int h,w; cin >> h >> w;
	for(int i=0;i<10;i++){
		for(int j=0;j<10;j++){
			cin >> c[i][j];
		}
	}
	for(int k=0;k<10;k++){
		for(int i=0;i<10;i++){
			for(int j=0;j<10;j++){
				c[i][j]=min(c[i][j],c[i][k]+c[k][j]);
			}
		}
	}
	int res=0;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			int a; cin >> a;
			if(a!=-1){
				res+=c[a][1];
			}
		}
	}
	cout << res << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#define fol(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
    int N,M;
    cin >>N>>M;
    int a[M],b[M],c[N];
    fol(i,M){
        cin >>a[i]>>b[i];
    }
    fol(i,N)c[i]=0;
    fol(i, M){
        c[a[i]-1]++;
        c[b[i]-1]++;
    }
    fol(i, N) cout<<c[i]<<endl;
    return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include"bits/stdc++.h"
#ifdef _DEBUG
#define DBG(n) n
#else
#define DBG(n)
#endif
#define INF          1e9
#define INFLL        1e18
#define EPS          1e-9
#define MOD          1000000007
#define REP(i,n)     for(ll i=0,i##_len=(n);i<i##_len;++i)
#define REP1(i,n)    for(ll i=1,i##_len=(n);i<=i##_len;++i)
#define REPR(i,n)    for(ll i=(n)-1;i>=0;--i)
#define REPR1(i,n)   for(ll i=(n);i>0;--i)
#define REPC(i,obj)  for(auto i:obj)
#define ALL(obj)     (obj).begin(),(obj).end()
#define SETP(n)      cout<<fixed<<setprecision(n)
#define VV(T,h,w)    move(vector<vector<T>>(h,move(vector<T>(w))))
#define VVI(T,h,w,i) move(vector<vector<T>>(h,move(vector<T>(w,i))))
using namespace std;
using ll = long long;
template<typename T = ll>inline T in() { T ret; cin >> ret; return ret; }

int main()
{
	auto pow2 = [](ll n) {ll ans = 1; REP(i, n)ans *= 2; return ans; };
	ll n = in(), p = in();
	ll odd = 0, even = 0; REP(i, n)++ *(in() % 2 == 0 ? &even : &odd);
	cout << (
		p == 0 && odd == 0 ? pow2(even)
		: p == 1 && odd == 0 ? 0
		: pow2(n - 1)
		) << endl;
}

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

int main()
{
	int n, d;
	scanf("%d%d", &n, &d);
	two_sat ts(n);
	int p[n][2];
	for (int i = 0; i < n; ++i) {
		scanf("%d%d", p[i], p[i]+1);
	}
	for (int i = 0; i < n; ++i) for (int j = i+1; j < n; ++j) {
		for (int k = 0; k < 4; ++k) {
			if (abs(p[i][k/2]-p[j][k%2]) < d) ts.add_clause(i, k/2, j, k%2);
		}
	}
	if (ts.satisfiable()) {
		puts("Yes");
		auto ans = ts.answer();
		for (int i = 0; i < n; ++i) printf("%d\n", p[i][!ans[i]]);
	}
	else {
		puts("No");
	}
}

Measured memory_bytes: 3896
import heapq

x,y,z,k = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=True)
b = sorted(list(map(int,input().split())),reverse=True)
c = sorted(list(map(int,input().split())),reverse=True)
ans = []


# a=[6, 4] b=[5, 1] c=[8, 3]

# delicious(i) = a(l) + b(m) + c(n)
# delicious(i+1) = max(delicious(i)-a(i)+a(i+1) , delicious(i)-b(m)+b(m+1), delicious(i)-c(n)+c(n+1)))
# delicious(0) = a(0) + b(0) + c(0)

heapq.heappush(ans,[-a[0]-b[0]-c[0],0,0,0])

#print(ans)

def delicious():
    maxans = heapq.heappop(ans)
    if maxans[1] != x-1:
        check1 = [-a[maxans[1]+1]-b[maxans[2]]-c[maxans[3]],maxans[1]+1,maxans[2],maxans[3]]
        if check1 not in ans:
            heapq.heappush(ans,check1)

    if maxans[2] != y-1:
        check2 = [-a[maxans[1]]-b[maxans[2]+1]-c[maxans[3]],maxans[1],maxans[2]+1,maxans[3]]
        if check2 not in ans:
            heapq.heappush(ans,check2)


    if maxans[3] != z-1:
        check3 = [-a[maxans[1]]-b[maxans[2]]-c[maxans[3]+1],maxans[1],maxans[2],maxans[3]+1]
        if check3 not in ans:
            heapq.heappush(ans,check3)
    print(-1*maxans[0])

for i in range(k):
    delicious()


Measured memory_bytes: 3948
#include<bits/stdc++.h>
using namespace std;
#define pi pair<ll,ll>
#define fr freopen("in.txt","r",stdin)
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define frep(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define f first
#define s second
#define maxn 200011

int main() {
    int N,A,B;
    cin >> N >> A >> B;
    cout << min(B,N*A);
}

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

int main(){
    int n;
    cin >> n;
    vector<char> s(n);
    for(int i=0; i<n; i++){
        cin >> s[i];
    }
    bool judge = true;
    if(n % 2 == 0){
        for(int i=0; i<n/2; i++){
            if(s[i] != s[n/2 + i]){
                judge = false;
            }
        }
    }else{
        judge = false;
    }
    if(judge){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
  	static int mod = 1000000007;
  static int size = 200001;
	static long[] fac = new long[size];
	static long[] finv = new long[size];
	static long[] inv = new long[size];
	static int INF = Integer.MAX_VALUE;
public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	// 整数の入力
	int A = sc.nextInt();
    int B = sc.nextInt();
  if(A>B&&(A-B)%2==0){
    System.out.println((A+B)/2);
  }else if(A<B&&(A-B)%2==0){
    System.out.println((A+B)/2);
  }else{
    System.out.println("IMPOSSIBLE");
  }


} 

 //fac, inv, finvテーブルの初期化、これ使う場合はinitComb()で初期化必要
	public static  void initComb(){
		fac[0] = finv[0] = inv[0] = fac[1] = finv[1] = inv[1] = 1;
		for (int i = 2; i < size; ++i) {
			fac[i] = fac[i - 1] * i % mod;
			inv[i] = mod - (mod / i) * inv[(int) (mod % i)] % mod;
			finv[i] = finv[i - 1] * inv[i] % mod;
		}
	}
 
	//nCk % mod
	public static long comb(int n, int k){
        if (n < k) return 0;
        if (n < 0 || k < 0) return 0;
		return fac[n] * finv[k] % mod * finv[n - k] % mod;
	}
 
	//n! % mod
	public static long fact(int n){
		return fac[n];
	}
 
	//(n!)^-1 with % mod
	public static long finv(int n){
		return finv[n];
	}
  
}

Measured memory_bytes: 27860
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize(3)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"
#include "bits/stdc++.h"
//#include "ext/pb_ds/tree_policy.hpp"
//#include "ext/pb_ds/assoc_container.hpp"
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x,l,u) for(ll x = l;x<u;x++)
#define RREP(x,l,u) for(ll x = l;x>=u;x--)
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) a.begin(),a.end()
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define sqr(x) ((x)*(x))
#define lowbit(x) (x&(-x))
#define lson (ind<<1)
#define rson (ind<<1|1)
#define se second
#define fi first
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl;
#define sz(x) ((int)x.size())
#define EX0 exit(0);

typedef  long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace std;
typedef vector<ll> VLL;
typedef vector<int> VI;
const int block_size = 320;
typedef complex<ll> point;
const ll mod = 1e9+7;
const ll inf = 1e9+7;
const ld eps = 1e-9;
const db PI = atan(1)*4;
template<typename T>
inline int sign(const T&a) {
    if(a<0)return -1;
    if(a>0)return 1;
    return 0;
}

template<typename T,typename S>inline bool upmin(T&a,const S&b){return a>b?a=b,1:0;}
template<typename T,typename S>inline bool upmax(T&a,const S&b){return a<b?a=b,1:0;}

template<typename T> inline void in(T &x) {
    x = 0;
    T f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch))  {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    x *= f;
}

ll twop(int x) {
    return 1LL<<x;
}

template<typename A,typename B > inline void in(A&x,B&y) {
    in(x);
    in(y);
}
template<typename A,typename B,typename C>inline void in(A&x,B&y,C&z) {
    in(x);
    in(y);
    in(z);
}
template<typename A,typename B,typename C,typename D> inline void in(A&x,B&y,C&z,D&d) {
    in(x);
    in(y);
    in(z);
    in(d);
}

namespace SOLVE {
    void main(){
    }
}

string s;
bool used[26];
void dfs(string&ans){
    if(ans > s){
        cout<<ans;exit(0);
    }
    REP(i,0,min(sz(ans),sz(s)))if(ans[i]<s[i])return;
    REP(i,0,26){
        if(!used[i]){
            used[i] = 1;
            ans.push_back(i+'a');
            dfs(ans);
            ans.pop_back();
            used[i] = 0;
        }
    }
    
    
    
    
    
    
}

int main(){
    cin>>s;
    string ans = "";
    dfs(ans);
    cout<<-1;
}


Measured memory_bytes: 256
#ifdef _MSC_VER
#include "stdc++.h"
#endif
#ifdef __GNUC__
#include<bits/stdc++.h>
#endif
using namespace std;

using ll = long long;

//constant
const double EPS = 1e-10;

#define REP(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, s, e) for (ll i = s; i < e; i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(), (x).rend()

//debug
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define DEBUG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl;

// vector
//template<typename T> vector<vector<T>> vv(ll H, ll W, T v) { return vector<vector<T>> vec(H, vector<T>(W, v)); }

// view vector
template<typename T> void view(T e) { cout << e << endl; }
template<typename T> void view(const vector<T>& v) { for (const auto& e : v) { cout << e << " "; } cout << endl; }
template<typename T> void view(const vector<vector<T> >& vv) { for (const auto& v : vv) { view(v); } }

// DP
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }




// ***************************************

int main(){

    ll X;
    cin >> X;

    for(ll i = 1; i * i <= X; i++){
        if (X % i != 0) continue;

        ll a, b;
        for(ll j = 0; true; j++){
            a = j;
            b = - i + j;

            ll left = pow(a, 5) - pow(b, 5); 
            if (left == X){
                cout << a << " " << b << endl;
                return 0;
            } 
            if (pow(a, 4) >= X) break;
        }
    }

    return 0;
}


Measured memory_bytes: 4028
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define INF 1e9+7
#define pf2 pop_front
#define pb2 pop_back
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define sz size
#define eps 1e-7
#define fod find_by_order
#define fastio ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define ofk order_of_key
#define val(x) cout << "Value dari "<< #x << " adalah " << x  << "\n"
#define tr tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

int dx[8] = {1,0,-1,0,1,1,-1,-1};
int dy[8] = {0,1,0,-1,1,-1,1,-1};

void readf(string x){
	freopen((x+".in").c_str(),"r",stdin);
	freopen((x+".out").c_str(),"w",stdout);
}

void pr(string x){
	freopen((x+".in").c_str(),"w",stdout);
}


int read()
{
	bool min = 0;
	int  result = 0;
	char ch;
	ch = getchar();
	while(1)
	{
		if(ch == '-') break;
		if(ch >='0' && ch <= '9') break;
		ch = getchar();
	}
	if(ch == '-') min = 1;else result = ch-'0';
	while(1)
	{
		ch =getchar();
		if(ch< '0' || ch>'9') break;
		result = result * 10 + (ch-'0');
	}
	if(min) return -result;
	return result;
}
//Reynaldo's Template

int main(){
	ll N,A,B;
	cin >> N >> A >> B;
	ll pos = 0;
	ll ans = 0;
	for(int i=1;i<=N;i++){
		ll a;
		cin >> a;
		if(pos == 0) pos = a;
		ans += min(A * (a - pos) , B);
		
		pos = a;
	}
	cout << ans << "\n";
}



Measured memory_bytes: 256
S = input() + '$'
T = 'AKIHABARA$'

s = 0
t = 0
while s < len(S) or t < len(T):
    if s >= len(S) or t >= len(T):
        break

    if S[s] == T[t]:
        s += 1
        t += 1
    else:
        if T[t] == 'A':
            t += 1
        else:
            break
else:
    print('YES')
    exit()

print('NO')

Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
#include<string>
#include<cctype>

using namespace std;

const char opr[] = {'A','O','X'};

#define N 4
#define WHITES 16
#define DIGIT 16

struct Set{
  bool sweet[N];
  Set(){fill(sweet,sweet+N,false);}
  Set And(const Set &t){
    Set ret;
    for(int i=0;i<N;++i){ret.sweet[i]=sweet[i]&&t.sweet[i];}
    return ret;
  }
  Set Or(const Set &t){
    Set ret;
    for(int i=0;i<N;++i){ret.sweet[i]=sweet[i]||t.sweet[i];}
    return ret;
  }
  Set Xor(const Set &t){
    Set ret;
    for(int i=0;i<N;++i){ret.sweet[i]=(!sweet[i]&&t.sweet[i])||(!t.sweet[i]&&sweet[i]);}
    return ret;
  }
};
typedef pair<int,Set> parsed;
Set sets[DIGIT];

parsed parse(const string &s, int pos);
parsed term(const string &s, int pos);

parsed parse(const string &s, int pos){
  ++pos;
  parsed L = term(s, pos);
  pos = L.first;
  char op = s[pos++];
  parsed R = term(s, pos );
  pos = R.first + 1;
  //cout << " R TERM, NEXT POS " << pos << ' ' << s[pos] << endl;
  Set result;
  if(op=='A')result=L.second.And(R.second);
  if(op=='O')result=L.second.Or(R.second);
  if(op=='X')result=L.second.Xor(R.second);
  return parsed( pos, result );
}

parsed term(const string &s, int pos){
  if( s[pos] == '(' ){
    return parse(s,pos);
  }else if( isdigit(s[pos]) ){
    return parsed( pos + 1, sets[ s[pos] - '0' ] );
  }
}

void dfs(string &s, int n, int white[], bool used[], int left, int &ans){
  if( left == 0 ){
    bool ng=false;
    //cout << s << " : ";
    parsed ps = parse(s,0);
    Set ts = ps.second;
    for(int i = 0; i < N; ++i){
      //cout << ts.sweet[i] << ' ';
      if( !ts.sweet[i] ){ng=true;}
    }
    //cout << endl;
    if(ng)return ;
    ++ans;
    return ;
  }
  for(int i = 0; i < n; ++i){
    if( !used[i] ){
      used[i]=true;
      for(int k = 0; k < sizeof(opr)/sizeof(*opr); ++k){
	s[ white[i] ] = opr[k];
	dfs(s,n,white,used,left-1,ans);
      }
      s[ white[i] ] =' ';
      used[i]=false;
      break;
    }
  }
  return ;
}

int main()
{
  while(true){
    int ans = 0;
    string s;
    int num = 0;
    int pos_white[WHITES];
    bool used[WHITES]={false,};
    getline(cin,s);
    if( s == "END" ) break;

    for(int i = 0; i < s.length(); ++i){
      if( s[i] == ' ' ){
	pos_white[num++] = i;
      }
    }
    
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i){
      for(int j = 0; j < N; ++j){
	int d;
	cin >> d;
	if( d == 1 ) sets[i+1].sweet[j] = 1;
	else sets[i+1].sweet[j] = 0;
      }
    }
    
    dfs(s, num, pos_white, used, num, ans );
    getline(cin,s);
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 932
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;cin>>N;
  vector<pair<int,int> >X(N);
  for(int i=0;i<N;i++){cin>>X[i].first;X[i].second=i+1;}
  sort(X.begin(),X.end());

  vector<int>A(N*N,-1);
  //セグ木で高速化?
  int l=0;
  for(int i=0;i<N;i++){
    A[X[i].first-1]=X[i].second;
    for(int j=0;j<X[i].second-1;j++){
      while(A[l]!=-1)l++;
      A[l]=X[i].second;
    }
    if(l>X[i].first-1){cout<<"No";return 0;}
  }
  for(int i=0;i<N;i++){
    for(int j=0;j<N-X[i].second;j++){
      while(A[l]!=-1)l++;
      if(l<X[i].first-1){cout<<"No";return 0;}
      A[l]=X[i].second;
    }
  }
  cout<<"Yes"<<endl;
  for(int i=0;i<N*N;i++)cout<<A[i]<<" ";

  

}

Measured memory_bytes: 2176
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <cassert>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
const double EPS = 1e-9;
const double PI  = acos(-1.0);

class ex{
};

void ass(bool cond){
	if(!cond){
		throw ex();
	}
}
void inrange(int n){
	ass(0<=n&&n<(1<<10));
}

int number(string &s,int &p){
	ass(isdigit(s[p]));
	int ret=s[p]-'0';
	p++;
	while(isdigit(s[p])){
		ret<<=1;
		ret+=s[p]-'0';
		inrange(ret);
		p++;
	}
	inrange(ret);
	return ret;
}
int expression(string &s, int &p,bool &op_exist);
int term(string &s,int &p,bool &op_exist);

//factor ::= number | (expression)
int factor(string &s,int &p){
	if(s[p]=='('){
		p++;
		bool op_exist=false;
		int ret=expression(s,p,op_exist);
		ass(op_exist);
		inrange(ret);
		ass(s[p]==')');
		p++;
		return ret;
	}else{
		return number(s,p);
	}
}

//term ::= factor | factor * factor
int term(string &s,int &p,bool &op_exist){
	int ret=factor(s,p);
	while(s[p]=='*'){
		p++;
		ret*=factor(s,p);
		inrange(ret);
		op_exist=true;
	}
	return ret;
}

//expression ::= term | term [+-] expression
int expression(string &s, int &p,bool &op_exist){
	int ret=term(s,p,op_exist);
	char op=s[p];
	while(op=='+'||op=='-'){
		p++;
		int t=term(s,p,op_exist);
		if(op=='+'){
			ret+=t;
		}else if(op=='-'){
			ret-=t;
		}else{
			ass(0);
		}
		inrange(ret);
		op=s[p];
		op_exist=true;
	}
	return ret;
}

char chars[]={'0','1','+','-','*','(',')'};

int main(){
	string s;
	cin>>s;
	vi rpl(5);
	int ans=-1;
	for(rpl[0]=0;rpl[0]<7;rpl[0]++)
	for(rpl[1]=0;rpl[1]<7;rpl[1]++)
	for(rpl[2]=0;rpl[2]<7;rpl[2]++)
	for(rpl[3]=0;rpl[3]<7;rpl[3]++)
	for(rpl[4]=0;rpl[4]<7;rpl[4]++){
		string ns(s);
		int pos=0;
		REP(i,5){
			pos=ns.find('.',pos);
			if(pos!=ns.npos){
				ns[pos]=chars[rpl[i]];
			}else{
				break;
			}
		}
		try{
			int p=0;
			bool op_exist=false;
			int val=expression(ns,p,op_exist);
			ass(p==ns.size());
			ans=max(ans,val);
		}catch(ex){
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 1256
#include <bits/stdc++.h>
using namespace std;
int d[100000];

int main(){
	ios::sync_with_stdio(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> d[i];
	}
	sort(d , d + n);
	cout << d[n / 2] - d[n / 2 - 1];
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
bool hantei = true;
bool miru(int a[],int n){
  bool flag = true;
  for(int i=0;i<n-1;i++){
    if(a[i]>a[i+1]){
      flag = false;
      //cout << "i " << i << " " <<a[i] << " i+1 " <<  i+1 << " "<< a[i+1] << endl;
    }
  }
  if(flag){
    cout << "YES" << endl;
    return flag;
  }
  else return flag;
}
int main(){
  int n;
  cin >> n;
  int p[n];
  for(int i=0;i<n;i++){
    cin >> p[i];
  }
  //for(int i=0;i<n;i++) cout << p[i] << " ";
  //cout << endl;
  if(miru(p,n)){
    return 0;
  }
  for(int i=0;i<n-1;i++){
    for(int j=i+1;j<n;j++){
      if(p[i]>p[j]){
        int tmp = p[i];
        p[i] = p[j];
        p[j] = tmp;
        if(!(miru(p,n))){
          tmp = p[i];
          p[i] = p[j];
          p[j] = tmp;
        }
         else return 0;
      }

    }
  }
   cout << "NO" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define elif else if
typedef long long ll;
typedef unsigned long long ull;
#define DEBUG(x) cout << (x) << endl
#define TGET(a, b) get<b>(a)

int is_prime(ll n)
{
    double n_sqrt;
    if (n == 2 || n == 3)
    {
        return 1;
    }
    if (n <= 1 || n % 6 != 1 && n % 6 != 5)
    {
        return 0;
    }
    n_sqrt = double(sqrt((double)n));
    for (int i = 5; i <= n_sqrt; i += 6)
    {
        if (n % i == 0 | n % (i + 2) == 0)
        {
            return 0;
        }
    }
    return 1;
}
int main()
{
    ll x;
    cin >> x;
    ll ans=0;
    int times = 0;
    times = x / 500;
    ans += 1000 * times;
    x -= times * 500;
    times = x / 5;
    ans += 5 * times;
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 256
/*

https://atcoder.jp/contests/abc054/tasks/abc054_c

https://qiita.com/greenteabiscuit/items/31c46ab3ceac07e749d2
*/
package main
 
import (
	"fmt"
)
 
var n int
var g [8][8]int
// 最初は訪問したことのあるノードは一つもない
var visited [8]bool
 
func dfs(now, depth int) int {
	// 既に訪問した先にたどりついてしまったら、totalに0が足される
	if visited[now] {
		return 0
	}
	// 一番深いところまで探索できた
	if depth == (n - 1) {
		return 1
	}
 
	visited[now] = true
	totalPaths := 0

	for i := 0; i < n; i++ {
		if g[now][i] == 1 {
			// 飛べる先があるのなら、位置と深さを更新し、さらに掘り下げてみる
			totalPaths += dfs(i, depth + 1)
		}
	}

	// 次に使うかもしれないから、一応キレイに
	visited[now] = false

	return totalPaths
}
 
func main() {
	var m int
	fmt.Scan(&n, &m)
	var a, b int
	// まず無向グラフを表す行列をつくる
	for i := 0; i < m; i++ {
		fmt.Scan(&a, &b)
		g[a-1][b-1] = 1
		g[b-1][a-1] = 1
	}
 
	ans := dfs(0, 0)
	fmt.Println(ans)
}

Measured memory_bytes: 512
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

ll n, s;

ll f(ll p, ll q)
{
    ll cnt = 0;
    while(p != 0)
    {
        cnt += p % q;
        p /= q;
    }
    return cnt;
}

int main()
{
    scanf("%lld%lld", &n, &s);
    ll i;
    if(n < s)
    {
        printf("-1");
        return 0;
    }
    if(n == s)
    {
        printf("%lld", n + 1);
        return 0;
    }
    for(i = 2; i * i <= n; i++)
    {
        if(f(n, i) == s)
        {
            printf("%lld", i);
            return 0;
        }
    }
    for(; i >= 1; i--)
    {
        if((n - s) % i == 0 && f(n, (n - s) / i + 1) == s)
        {
            printf("%lld", (n - s) / i + 1);
            return 0;
        }
    }
    if(s == 1)
    {
        printf("%lld", n);
        return 0;
    }
    printf("-1");
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
 
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String S = sc.next();
    int w = sc.nextInt();
    String ans="";
    for (int i = 0; i < S.length(); i += w) {
      ans += S.charAt(i);
    }
    System.out.println(ans);
  }
}   

Measured memory_bytes: 39376
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N;
        N = scan.nextInt();
        String[] W = new String[N];
        String ans = "Yes";
        
        for (int i = 0; i < N; i++) {
            W[i] = scan.next();
        }
        for (int i = 0; i < N - 1; i++) {
            if (W[i].charAt(W[i].length() - 1) != W[i + 1].charAt(0)) {
                ans = "No";
                break;
            }
            if (!check(W, W[i])) {
                ans = "No";
                break;
            }
        }
        
        System.out.println(ans);
    }
    
    public static boolean check(String[] W, String s) {
        int count = 0;
        boolean r = true;
        
        for (int i = 0; i < W.length; i++) {
            if (W[i].equals(s)) {
                count++;
            }
            if (count == 2) {
                r = false;
                break;
            }
        }
        
        return r;
    }
}


Measured memory_bytes: 23636
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
  
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
  
using namespace std;
  
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
  
const int INF=1<<29;
const double EPS=1e-9;
  
const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};


int main() {
  ll K;
  cin >> K;
  if (K < 50) {
    cout << 50 << endl;
    cout << 50 * K << " ";
    for (int i = 0; i < 49; i++) {
      cout << 0 << " ";
    }
    cout << endl;
    return 0;
  }

  ll d = K / 50;
  ll r = K % 50;
  ll left = (50 + d - 1) - r;
  ll leftsize = 50 - r;
  ll right = left + 51;
  ll rightsize = r;

  cout << 50 << endl;
  for (int i = 0; i < leftsize; i++) {
    cout << left << " ";
  }
  for (int i = 0; i < rightsize; i++) {
    cout << right << " ";
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
    ll t,n,i,j,k,x,y;
    cin>>n;
    vector<ll>v;
    for(i=0;i<n;i++)
    {
        cin>>k;
        v.push_back(k);
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    ll sum=0;
    sum+=v[0];
    for(i=1,j=1;i<=n-2;i+=2)
    {
        if((n-2)%2==1)
        {
            if(i==n-2)
            {
                sum+=v[j];
            }
            else
            {
                sum+=2*v[j];
            }

        }
        else
        {
        sum+=2*v[j];

        }
        j++;
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 5376
from sys import stdin
MAX = 100
INF = 1<<32
n, e = map(int, stdin.readline().split())
d = [[INF] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for i in range(e):
    u, v, c = map(int, stdin.readline().split())
    d[u][v] = c
def floyd():
    for k in range(n):
        for i in range(n):
            if d[i][k] == INF: continue
            for j in range(n):
                if d[k][j] == INF: continue
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
floyd()
for i in range(n):
    if d[i][i] < 0:
        print("NEGATIVE CYCLE")
        exit(0)
for i in range(n):
    for j in range(n):
        if d[i][j] == INF: print("INF", end="")
        else: print(d[i][j], end="")
        if j + 1 != n:
            print(" ", end="")
    print()

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

using ll = long long;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	ll s, INF = 1e9;
	cin >> s;
	ll y = (s+INF-1)/INF;
	ll x = y*INF-s;
	cout << "0 0 1000000000 1 " << x << " " << y;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>

using namespace std;
using ll = long long;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
int gcd(int a, int b){ return (b == 0) ? a : gcd(b, a % b); }

#define Sq(x) (x)*(x)
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Reverse(c) reverse(Range(c))
#define Unique(a) a.erase(unique(Range(a)), a.end())
#define Cusum(T, xs, sxs) vector<T> sxs(xs.size()+1); For(i, (int)xs.size()) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) Vec2(T, n, m, xs); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) { for(const auto &e : xs) cout << e << " "; cout << "\n"; }
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")
#define vc vector
#define Mini(a, x) a = min(a, x)
#define Maxi(a, x) a = max(a, x)

// constexpr int MOD = 1e9+7;

int main(void){
    Cin(int, n);
    Cin(string, s);
    Cin(int, k);
    For(i, n) if(s[i] != s[k-1]) s[i] = '*';
    Cout(s);
}





Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string>
#include<string.h>
#include<algorithm>
#include<queue>
#include<functional>
using namespace std;
#define ll long long
typedef pair<ll,ll> P;
const int maxn = 2e5+10;
int n;
ll d; ll a;
struct Node
{
	ll x,h;
	bool operator <(const Node &p)const
	{
		return x<p.x;
	}
}node[maxn];
ll tmp;
ll ans;
priority_queue<P,vector<P>,greater<P> > que;
ll cst(ll x,ll y)
{
	if(x<=0) return 0;
	if(x%y==0) return x/y;
	return x/y+1;
}
int main()
{
	scanf("%d%lld%lld",&n,&d,&a);
	for(int i=1;i<=n;i++)
	scanf("%lld%lld",&node[i].x,&node[i].h);
	sort(node+1,node+1+n);
	P p;
	ll t;
	for(int i=1;i<=n;i++)
	{
		while(que.size())
		{
			p=que.top();
			if(p.first<node[i].x) tmp-=p.second,que.pop();
			else break;
		}
		t=cst(node[i].h-tmp,a);
		ans+=t;
		tmp+=t*a;
		que.push(P(node[i].x+2*d,t*a));
	} 
	printf("%lld",ans);
	return 0;
}

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

using namespace std;

template< typename Data, typename T >
struct ReRooting {

  struct Node {
    int to, rev;
    Data data;
  };

  using F1 = function< T(T, T) >;
  using F2 = function< T(T, int, int, Data) >; // ret, src, to, data


  vector< vector< Node > > g;
  vector< vector< T > > dp, ldp, rdp;
  vector< vector< int > > eval;
  const F1 f1;
  const F2 f2;

  ReRooting(int n, const F1 &f1, const F2 &f2) : g(n), ldp(n), rdp(n), dp(n), eval(n), f1(f1), f2(f2) {}

  void add_edge(int u, int v, const Data &d) {
    g[u].emplace_back((Node) {v, (int) g[v].size(), d});
    g[v].emplace_back((Node) {u, (int) g[u].size() - 1, d});
  }

  T dfs(int idx, int par) {

    if(par == -1 || !eval[idx][par]) {
      for(int i = 0; i < g[idx].size(); i++) {
        if(i == par) continue;
        if(exchange(eval[idx][i], true)) continue;
        dp[idx][i] = f2(dfs(g[idx][i].to, g[idx][i].rev), idx, g[idx][i].to, g[idx][i].data);
      }
      for(int i = 0; i < g[idx].size(); i++) {
        if(!eval[idx][i]) break;
        ldp[idx][i + 1] = f1(ldp[idx][i], dp[idx][i]);
      }
      for(int i = (int) g[idx].size() - 1; i >= 0; i--) {
        if(!eval[idx][i]) break;
        rdp[idx][i] = f1(rdp[idx][i + 1], dp[idx][i]);
      }
    }

    if(par <= 0) return rdp[idx][par + 1];
    return f1(ldp[idx][par], rdp[idx][par + 1]);
  }


  vector< T > solve() {
    for(int i = 0; i < g.size(); i++) {
      ldp[i].resize(g[i].size() + 1);
      rdp[i].resize(g[i].size() + 1);
      dp[i].resize(g[i].size());
      eval[i].resize(g[i].size());
    }
    vector< T > ret;
    for(int i = 0; i < g.size(); i++) {
      ret.push_back(dfs(i, -1));
    }
    return ret;
  }
};

using vi = vector< int >;

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

  auto f1 = [](vi a, vi b) {
    for(auto &p : b) a.push_back(p);
    sort(a.rbegin(), a.rend());
    a.resize(min((int) a.size(), 2));
    return a;
  };
  auto f2 = [](vi a, int src, int to, int d) {
    a.push_back(0);
    return vi{*max_element(a.begin(), a.end()) + d};
  };

  ReRooting< int, vi > g(N, f1, f2);
  for(int i = 1; i < N; i++) {
    int s, t, w;
    cin >> s >> t >> w;
    g.add_edge(s, t, w);
  }

  int ret = 0;
  for(auto &p : g.solve()) {
    if(p.size() >= 2) ret = max(ret, p[0] + p[1]);
    if(p.size() >= 1) ret = max(ret, p[0]);
  }
  cout << ret << endl;
}


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


def main():
    L = int(input())
    la = []
    for _ in range(L):
        la.append(int(input()))
    dp = [[0 for _ in range(5)] for _ in range(L+1)]

    for i in range(L):
        cost1 = la[i]
        cost2 = 2 if la[i] == 0 else la[i] % 2
        cost3 = 1 if la[i] == 0 else (la[i] + 1) % 2

        dp[i+1][0] = dp[i][0] + cost1
        dp[i+1][1] = min(dp[i][0], dp[i][1]) + cost2
        dp[i+1][2] = min(dp[i][0], dp[i][1], dp[i][2]) + cost3
        dp[i+1][3] = min(dp[i][0], dp[i][1], dp[i][2], dp[i][3]) + cost2
        dp[i+1][4] = min(dp[i][0], dp[i][1], dp[i][2], dp[i][3], dp[i][4]) + cost1

    print(min(dp[L]))


if __name__ == '__main__':
    main()


Measured memory_bytes: 74068
#include<bits/stdc++.h>
using namespace std;
int main(){long long n,i=0,r,t,s=0,p=0,l,m=0;
cin>>n;long long a[n];
for(i=0;i<n;i++){
    cin>>a[i];
    s=s+a[i];
}
s=s/n;
t=s+1;
for(i=0;i<n;i++){r=abs(s-a[i]);l=(t-a[i]);
    p=p+r*r;m=m+l*l;
}if(p<=m)
cout<<p;
else
cout<<m;
    return 0;
  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int dp[35][100005];

int main()
{
  string S;
  cin >> S;
  int N = S.size();
  vector<int> A(N);
  for (int i = 0; i < N; i++)
  {
    if (S[i] == 'R')
      dp[0][i] = i + 1;
    else
      dp[0][i] = i - 1;
  }
  for (int i = 0; i < 31; i++)
  {
    for (int j = 0; j < N; j++)
    {
      dp[i + 1][j] = dp[i][dp[i][j]];
    }
  }
  for (int i = 0; i < N; i++)
  {
    A[dp[30][i]]++;
  }
  for (int i = 0; i < N; i++)
  {
    if (i)
      cout << ' ';
    cout << A[i];
  }
  cout << endl;
}

Measured memory_bytes: 16408
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <iomanip>
#include <cmath>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int main()
{
    int X, Y;
    cin >> X >> Y;
    if (Y % 2 == 1 || Y > (4 * X) || Y < (2 * X))
    {
        cout << "No" << endl;
    }
    else{
        cout << "Yes" << endl;
    }
    return 0;
}


Measured memory_bytes: 3636
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

#define cauto const auto&
#endif

using namespace std;


typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()) {
  v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t) {
  stringstream ss;
  ss << f;
  ss >> t;
}

vector<string> split(const string &str, char delim) {
  vector<string> res;
  size_t current = 0, found;
  while ((found = str.find_first_of(delim, current)) != string::npos) {
    res.push_back(string(str, current, found - current));
    current = found + 1;
  }
  res.push_back(string(str, current, str.size() - current));
  return res;
}

#define rep(i,n) for(int i=0;i<int(n);++i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back


#define MOD 1000000007LL
#define EPS 1e-8


int main() {
  int sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;
  int x = tx - sx;
  int y = ty - sy;
  cout << string(y, 'U') << string(x, 'R');
  cout << string(y, 'D') << string(x, 'L');
  cout << 'L' << string(y + 1, 'U') << string(x + 1, 'R') << 'D';
  cout << 'R' << string(y + 1, 'D') << string(x + 1, 'L') << 'U' << endl;
  return 0;
}

Measured memory_bytes: 256
mod = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
h = [0 for _ in range(2001)]
ans_1 = []
mi = 2001
for ai in reversed(a):
    h[ai] += 1
    mi = min(mi, ai)
    if mi == ai: continue
    ans_1.append(sum(h[:ai]))
h = [0 for _ in range(2001)]
ans_2 = []
mi = 2001
for ai in a:
    h[ai] += 1
    mi = min(mi, ai)
    if mi == ai: continue
    ans_2.append(sum(h[:ai]))
print(int((sum(ans_1) * (k * (k+1) // 2)) +
          (sum(ans_2) * (k * (k-1) // 2))) % mod)

Measured memory_bytes: 3188
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		sc.close();

		if (n > m) {
			int t = n;
			n = m;
			m = t;
		}
		int d = m - n;
		if (d > 1) {
			System.out.println("0");
			return;
		}

		long p = 1L;
		for (int i = 2; i <= n; i++) {
			p = p * i % 1000000007;
		}

		if (d == 0) {
			System.out.println(p * p * 2 % 1000000007);
		} else {
			System.out.println(p * p % 1000000007 * m % 1000000007);
		}
	}
}


Measured memory_bytes: 25300
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include <iomanip>
#include<deque>
#include<stack>
#include<set>
#include <numeric>

using namespace std;
typedef unsigned int uint;
typedef long long ll;
//typedef pair<int, int> P;
const int INF = 111111111;
const ll LLINF = 1e17 + 1;
const int DX[9] = { 0,0,1,-1, 1, 1, -1, -1, 0 }; // 4;４近傍
const int DY[9] = { 1,-1,0,0, 1, -1, 1, -1, 0 }; // 8:８近傍 9:(0,0)を含む
const int DIV = 1000000007; //10^9 + 7
const double PI = 3.14159265358979323846264338327950288;


int main() {

	//==================================
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	//==================================

	int N;
	cin >> N;
	string S;
	cin >> S;

	// 一番西の人がリーダーの時
	vector<int> ans (N);
	ans[0] = 0;
	for (int i = 1; i < N; i++) {
		ans[0] += bool(S[i] == 'E');
	}
	
	for (int i = 1; i < N; i++) {
		ans[i] = ans[i - 1] - bool(S[i] == 'E') + bool(S[i - 1] == 'W');
	}


	int temp = INF;
	for (int i = 0; i < N; i++) {
		temp = min(temp, ans[i]);
	}

	cout << temp;

}	


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

int main()
{

int x,n;
cin>>x>>n;

map<int,bool> existe;

for(int index = 0 ;index<n;index ++)
{
    int in;
    cin>>in;
    existe.insert(pair<int,bool>(in,true));
   
}
int pos =0;
while(existe[x+pos]&&existe[x-pos])
pos++;

if(!existe[x-pos])
cout<<x-pos<<endl;
else
cout<<x+pos<<endl;

    return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int a, b, c;
    int k;
    vector<int> binary = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
    cin >> a >> b >> c;
    cin >> k;
    bool flg = false;
    for (int i=0;i<=k;i++){
        for (int j=0;j<=k;j++){
            if (a < b*binary[i] && b*binary[i] < c*binary[j] && i+j==k){
                flg = true;
            }
        }
    }
    if (flg){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}


Measured memory_bytes: 3604