akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;
#define MAX 101

int H, W;
int num = 0;
char fruit[MAX][MAX];
bool ever[MAX][MAX];

int way[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

void dfs(int x, int y, char buff) {
	for (int i = 0; i < 4; i ++) {
		int next_x = x + way[i][0];
		int next_y = y + way[i][1];
		
		if(!ever[next_x][next_y] && buff == fruit[next_x][next_y] && next_x < H && next_x >= 0 && next_y < W && next_y >= 0) {
			ever[next_x][next_y] = true;
			dfs(next_x, next_y, buff);
		}
	}
}

int main() {
	while (cin >> H >> W && W != 0 && H != 0) {
		for (int i = 0; i < H; i ++) {
			for (int j = 0; j < W; j ++) {
				cin >> fruit[i][j];
				ever[i][j] = false;
			}
		}
		
		for (int i = 0; i < H; i ++) {
			for (int j = 0; j < W; j ++) {
				if (!ever[i][j]) {
					dfs(i, j, fruit[i][j]);
					num ++;
				}
			}
		}
		cout << num << endl;
		num = 0;
	}
	
	return 0;
}

Measured memory_bytes: 3456
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int N, ans = 0;
int cnt[105];
bool visited[105];

int Add(int num){
  int now = num;
  for (int i = 2; i * i <= num; i++){
    while (now % i == 0){
      cnt[i]++;
      now /= i;
    }
  }
  if (now > 1) cnt[now]++;

  return 0;
}

int main(){
  scanf("%d", &N);

  for (int i = 2; i <= N; i++) Add(i);

  for (int i = 2; i <= N; i++){
    if (cnt[i] >= 74) ans++;
  }

  for (int i = 2; i <= N; i++){
    fill(visited, visited + 100, false);
    if (cnt[i] < 24) continue;
    visited[i] = true;
    for (int j = 2; j <= N; j++){
      if (!visited[j] && cnt[j] >= 2) ans++;
    }
  }

  for (int i = 2; i <= N; i++){
    fill(visited, visited + 100, false);
    if (cnt[i] < 14) continue;
    visited[i] = true;
    for (int j = 2; j <= N; j++){
      if (!visited[j] && cnt[j] >= 4) ans++;
    }
  }


  for (int i = 2; i <= N; i++){
    if (cnt[i] < 2) continue;
    int now = 0;
    for (int j = 2; j <= N; j++){
      if (i == j) continue;
      if (cnt[j] >= 4) now++;
    }
    ans += now * (now - 1) / 2;
  }

  cout << ans  << endl;

  return 0;
}


Measured memory_bytes: 3656
use std::cmp::*;
use std::collections::*;
use std::io::*;
use std::str::*;

use std::string::*;

struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        Self(r, std::io::BufWriter::new(w))
    }

    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.to_string().as_bytes()).unwrap();
    }

    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let s: String = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect();

        return s.parse::<T>().ok().unwrap();
    }

    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

fn prime_factorization(n: i64) -> HashMap<i64, i64> {
    let mut n = n;
    let mut res = HashMap::new();
    let mut i = 2;
    while i * i <= n {
        while n % i == 0 {
            n /= i;
            let count = res.entry(i).or_insert(0);
            *count += 1;
        }
        i += 1;
    }

    if n > 1 {
        res.insert(n, 1);
    }

    return res;
}

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let n = sc.read();
    let mut res = prime_factorization(n);
    let mut ans = 0;
    for a in res {
        let mut cnt = 0;
        let mut plus = 1;
        while cnt + plus <= a.1 {
            cnt += plus;
            plus += 1;
            ans += 1;
        }
    }

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

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

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

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  string s;
  map<string, int> mp;
  while (cin >> s) {
    mp[s.substr(s.find(',') + 1)]++;
  }
  cout << mp["A"] << endl;
  cout << mp["B"] << endl;
  cout << mp["AB"] << endl;
  cout << mp["O"] << endl;

  return 0;
}


Measured memory_bytes: 3088
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string str;
  int i,n,count;
  
  cin>>n;
  cin>>str;
 
  i=0;
  count=n;
  
   	while(i<n-1){
    	if(str.at(i)==str.at(i+1)){
			count--;
        }
		i++;
  	}
  cout<<count<<endl;;
 }


Measured memory_bytes: 512
// #define _GLIBCXX_DEBUG
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<int, int>; using vi = vector<int>; using vvi = vector<vi>; using pll = pair<ll, ll>; using vl = vector<ll>; using vvl = vector<vl>; using vb = vector<bool>; using vvb = vector<vb>;
#define rep0(TMS) for (int CNT = 0; CNT < (int)(TMS); CNT++)
#define rep(CNT, GOAL) for (int CNT = 0; CNT < (int)(GOAL); CNT++)
#define rep2(CNT, START, GOAL) for (int CNT = (int)(START); CNT < (int)(GOAL); CNT++)
#define rep3(CNT, START, GOAL) for (int CNT = (int)(START); CNT > (int)(GOAL); CNT--)
#define all(CONT) begin(CONT), end(CONT)
template <typename T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template <typename T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
void prec(const int &DIG) { cout << fixed << setprecision(DIG); cerr << fixed << setprecision(DIG); }
template <typename T> void CERR(const T &ELEM) { cerr << ELEM; }
#define dbl(OBJ) cerr << #OBJ << ": "; CERR(OBJ); cerr << "\n"
template <typename T, typename ...Ts> void CERR(const T &FIRST, const Ts &...REST) { CERR(FIRST); cerr << ", "; CERR(REST...); }
#define dbs(...) cerr << "(" << #__VA_ARGS__ << "): ("; CERR(__VA_ARGS__); cerr << ")\n"
#define itrep(ITR, CONT) for (auto ITR = begin(CONT); ITR != end(CONT); ITR++)
template <typename T> void CERR(const vector<T> &VEC) { cerr << "{ "; itrep(ITR, VEC) { CERR(*ITR); cerr << ", "; } cerr << "}"; }
#define YN(FLG) cout << (FLG ? "YES" : "NO") << "\n"
#define Yn(FLG) cout << (FLG ? "Yes" : "No") << "\n"
#define yn(FLG) cout << (FLG ? "yes" : "no") << "\n"

// #include <atcoder/all>

// using namespace atcoder;

// const ll INF = LONG_LONG_MAX;
const int INF = INT_MAX;
// const ll MOD = 1000000007; // 998244353;

int main() {
	string S; cin >> S;
	char c = S[S.size() - 1];
	if (c == 's') cout << S << "es" << endl;
	else cout << S << "s" << endl;
	
}

Measured memory_bytes: 3628
#include <stdio.h>

int main(void) {
  int i, j, h, w, k;
  while( 1 ) {
    scanf("%d%d", &h, &w);
    if(!h && !w) break;
    for(j = 0; j < h; ++j) {
      for(k = 0; k < w; ++k) {
        if(!k || !j || j == h - 1 || k == w - 1) printf("#");
        else printf(".");
      }
      printf("\n");
    }
    printf("\n");
  }
  return 0;
}


Measured memory_bytes: 2500
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rev(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define rev2(i, s, n) for (int i = (int)(n) - 1; i >= (int)(s); i--)
#define bitrep(i, n) for (int i = 0; i < (int)(1 << n); i++)
#define all(v) v.begin(), v.end()
#define println(x) cout << x << endl
#define fi first
#define se second
#define Yes println("Yes")
#define No println("No")
#define YES println("YES")
#define NO println("NO")
using pii = pair<int, int>;

int main()
{
    int n, m; cin >> n >> m;
    vector<vector<int>> g(n, vector<int>());
    vector<int> idx(n);
    iota(all(idx), 0);
    rep(i, m)
    {
        int from, to; cin >> from >> to;
        g[from - 1].push_back(to - 1);
        g[to - 1].push_back(from - 1);
    }
    int cnt = 0;
    do
    {
        if (idx[0] != 0) break;
        vector<bool> visited(n, false);
        bool reachable = true;
        rep(i, n-1)
        {
            if (visited[idx[i]])
            {
                reachable = false;
                break;
            }
            visited[idx[i]] = true;
            if (find(all(g[idx[i]]), idx[i+1]) == g[idx[i]].end())
            {
                reachable = false;
                break;
            }
        }
        if (reachable) cnt++;
    } while (next_permutation(all(idx)));
    cout << cnt++ << endl;
}

Measured memory_bytes: 3580
#include <stdio.h>
int main (){
  int n;
  scanf("%d",&n);
  
  if (n==1){
    printf("Hello World");
  }
  
  else if (n==2){
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%d",a+b);
  }
  
  return 0;
}


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

int main(){
  long long N,M;
  cin >> N >> M;
  long long ans;
  if(N>M/2){
    ans = M/2;
  }else{
    ans = N;
    M -= N*2;
    ans += M/4;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
/*input

*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#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())
#ifdef leowang
#define debug(...) do{\
	fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}
//}}}
const ll maxn=300005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		
		b>>=1;
	}
	return res;
}

int main()
{
	IOS;
	int n,T;
	cin>>n>>T;
	int OAO=INF;
	REP(i,n){
		int c,t;
		cin>>c>>t;
		if(t<=T) OAO=min(OAO,c);
	}
	if(OAO==INF) cout<<"TLE\n";
	else cout<<OAO;

	return 0;
}


Measured memory_bytes: 256
#include <cstdio>

typedef long long LL;
const int MN = 3005;

int Mod;

inline int pw(int e, int m = Mod) {
	int b = 2, a = 1;
	for (; e; e >>= 1, b = (LL)b * b % m)
		if (e & 1) a = (LL)a * b % m;
	return a;
}

int N, C[MN][MN], S[MN][MN], Ans;

int main() {
	scanf("%d%d", &N, &Mod);
	for (int i = 0; i <= N; ++i) C[i][0] = 1;
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= i; ++j)
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % Mod;
	S[0][0] = 1;
	for (int i = 1; i <= N + 1; ++i)
		for (int j = 1; j <= i; ++j)
			S[i][j] = (S[i - 1][j - 1] + (LL)S[i - 1][j] * j) % Mod;
	for (int i = 0; i <= N; ++i) {
		int Sum = 0, C0 = pw(N - i), Coef = 1;
		for (int j = 0; j <= i; ++j)
			Sum = (Sum + (LL)S[i + 1][j + 1] * Coef) % Mod,
			Coef = (LL)Coef * C0 % Mod;
		Sum = (LL)Sum * C[N][i] % Mod * pw(pw(N - i, Mod - 1)) % Mod;
		Ans = (Ans + (i & 1 ? -Sum : Sum)) % Mod;
	}
	printf("%d\n", (Ans + Mod) % Mod);
	return 0;
}

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

bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}

int main () {
  int n;
  cin >> n;
  while(!IsPrime(n)) {
    n++;
  }
  cout << n << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <deque>
using namespace std;
using P = pair<int,int>;
typedef long long int ll;
#define rep(i, n) for (int(i) = 0; (i) < (n); (i)++)

int main(){ 
  string s; cin >> s;
  rep(i,s.size()){
    if(i%2==0 && s[i]=='L'){
      cout << "No" << endl;
      return 0;
    }else if(i%2!=0 && s[i]=='R'){
      cout << "No" << endl;
      return 0; 
    }
  }
  cout << "Yes" << endl;
  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<stdio.h>
#include<iostream>
#include<string>
#include<math.h>
#include<vector>
#include<set>
#include<algorithm>
#include<map>
#include<utility>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
int main()
{
    ll t,n,i,m,x,y,k,j;
    string s;
    cin>>s;
    ll l=s.length();
    if(s[l-1]=='3')
        cout<<"bon";
    else if (s[l-1]=='0'||s[l-1]=='1'||s[l-1]=='6'||s[l-1]=='8')
        cout<<"pon";
    else
        cout<<"hon";


}




Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ll long long
#define mod 1000000007
using namespace std;
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);

}
int main()
{
    ios_base:: sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
    ll k,n;
    cin>>k>>n;
    ll arr[n];
    for( ll i=0;i<n;i++)
        cin>>arr[i];
    //sort(arr,arr+n);
    vector<ll>vis;
    for(ll i=1;i<n;i++)
        vis.pb(arr[i] - arr[i-1]);
    vis.pb(k-arr[n-1]+arr[0]);
    sort(vis.begin(),vis.end());
    ll ans = 0;
    for(ll i=0;i<n-1;i++)
        ans += vis[i];
    cout<<ans;
}


Measured memory_bytes: 3956
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <cmath>

using namespace std;
using ll = long long int;

template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
  for (auto i = v.begin(); i != v.end(); i++) {
    os << *i << " ";
  }
  return os;
}


void solve(long long H, long long W, std::vector<std::vector<long long>> a){
  ll d[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
  vector<pair<ll, ll>> from;
  vector<pair<ll, ll>> to;
  for(ll i=0; i<H; i++) {
    for(ll j=0; j<W; j++) {
      if(a[i][j]%2) {
	bool f = false;
	for(ll k=0; k<4; k++) {
	  ll y = i+d[k][0];
	  ll x = j+d[k][1];
	  if(0<=y and y<H and 0<=x and x<W and a[y][x]%2) {
	    a[i][j]--;
	    a[y][x]++;
	    from.push_back(make_pair(i+1, j+1));
	    to.push_back(make_pair(y+1, x+1));
	    f = true;
	    break;
	  }
	}
	if(!f) {
	  for(ll k=0; k<4; k++) {
	    ll y = i+d[k][0];
	    ll x = j+d[k][1];
	    if(0<=y and y<H and 0<=x and x<W and a[y][x]%2==0) {
	      a[i][j]--;
	      a[y][x]++;
	      from.push_back(make_pair(i+1, j+1));
	      to.push_back(make_pair(y+1, x+1));
	      break;
	    }
	  }
	}
      }
    }
  }
  std::cout << from.size() << std::endl;
  for(ll i=0; i<from.size(); i++) {
    std::cout << from[i].first <<" "
	      << from[i].second<<" "
	      << to[i].first<<" "
	      << to[i].second<< std::endl;
  }
  // std::cout << std::endl;
  // for(ll i=0; i<H; i++) {
  //   for(ll j = 0; j<W; j++) {
  //     std::cout << a[i][j] << " ";
  //   }
  //   std::cout << std::endl;
  // }
}

int main(){
  long long H;
  scanf("%lld",&H);
  long long W;
  scanf("%lld",&W);
  std::vector<std::vector<long long>> a(H, std::vector<long long>(W));
  for(int i = 0 ; i < H ; i++){
    for(int j = 0 ; j < W ; j++){
      scanf("%lld",&a[i][j]);
    }
  }
  solve(H, W, std::move(a));
  return 0;
}



Measured memory_bytes: 8120
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

int main(){
  int A, B, C;
  cin >> A >> B >> C;
  if (A == B) {
    cout << C << endl;
  }
  if (B == C) {
    cout << A << endl;
  }
  if (A == C) {
    cout << B << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mod 1000000007
#define d2 500000004
using namespace std;
typedef long long ll;

ll fp(ll x, ll t) {
	ll ret = 1;
	for (; t; t >>= 1, x = x * x % mod) if (t & 1) ret = ret * x % mod;
	return ret;
}

ll n, ans;
ll head[200005], pre[400005], to[400005], siz[400005], sz;
ll num[200005], top;

void addedge(ll u, ll v) {
	pre[++sz] = head[u]; head[u] = sz; to[sz] = v;
} 

void dfs(ll x, ll fa) {
	siz[x] = 1;
	for (int i = head[x]; i; i = pre[i]) {
		ll y = to[i];
		if (y == fa) continue;
		dfs(y, x); siz[x] += siz[y];
	}
	top = 0; ll tmp = 1;
	for (int i = head[x]; i; i = pre[i]) {
		ll y = to[i];
		if (y != fa) {
			num[++top] = fp(d2, siz[y]);
			tmp = num[top] * tmp % mod;
		}
	}
	if (n - siz[x]) {
		num[++top] = fp(d2, n - siz[x]);
		tmp = num[top] * tmp % mod;
	}
	if (top == 1) return;
	ll ret = 0;
	for (int i = 1; i <= top; i++) {
//		if(x == 1)cout << (1 - num[top] + mod) % mod * 64 % mod << endl;
		ret = (ret + tmp * fp(num[i], mod-2) % mod * ((1 - num[i] + mod) % mod) % mod) % mod;
	}
	ret = (ret + tmp) % mod;
//	if (x == 1) cout << ret * 64 % mod<< endl;
	ans = (ans + d2 * ((1 - ret + mod) % mod) % mod) % mod;
}

int main() {
	scanf("%lld", &n);
	for (int i = 1; i < n; i++) {
		ll x, y; scanf("%lld %lld", &x, &y);
		addedge(x, y); addedge(y, x);
	}
	dfs(1, 0);
	printf("%lld", ans);
	return 0;
}

Measured memory_bytes: 20480
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  int n,m,i,t,xmax,ymin;cin >> n >> m >> xmax >> ymin;
  for(i=0;i<n;i++){
    cin >> t;
    xmax = max(xmax,t);
  }
  for(i=0;i<m;i++){
    cin >> t;
    ymin = min(ymin,t);
  }
  cout << ((xmax<ymin) ? "No War":"War") << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String [] args) {
		Scanner scan = new Scanner(System.in);
		int sum, cal;
		String x;
		
		do {
			
			x = scan.nextLine();
					
			if(x.equals("0"))break;
			sum = 0;
			
			for(int i = 0; i < x.length(); i++) {
				char c = x.charAt(i);
				cal = Integer.parseInt("" + c);
				sum += cal;
			}
			
			System.out.println(sum);
			
		}while(true);
	}
}



Measured memory_bytes: 26732
// -----------------------------------
// Author     : MatsuTaku
// Affiliation: Tokushima University
// Country    : Japan
// Date       : 03/25/2020
// -----------------------------------

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr ll INF = 1e18;

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

  int n,m,s,t; cin>>n>>m>>s>>t;
  s--;t--;
  struct Path {
    int p;
    ll c;
    Path(int p,ll c) : p(p),c(c){}
    bool operator>(const Path& x) const {return c > x.c;}
  };
  vector<vector<Path>> graphy(n), graphs(n);
  for (int i = 0; i < m; i++) {
    int u,v,a,b; cin>>u>>v>>a>>b;
    u--;v--;
    graphy[u].emplace_back(v, a);
    graphy[v].emplace_back(u, a);
    graphs[u].emplace_back(v, b);
    graphs[v].emplace_back(u, b);
  }
  auto dijkstra = [](auto& graph, auto& dist, int start) {
    fill(dist.begin(), dist.end(), INF);
    dist[start] = 0;
    priority_queue<Path, vector<Path>, greater<>> qs;
    qs.emplace(start, 0);
    while (not qs.empty()) {
      auto q = qs.top(); qs.pop();
      if (dist[q.p] < q.c)
        continue;
      for (auto tg : graph[q.p]) {
        auto c = q.c + tg.c;
        if (dist[tg.p] <= c)
          continue;
        dist[tg.p] = c;
        qs.emplace(tg.p, c);
      }
    }
  };
  vector<ll> ymin(n), smin(n);
  dijkstra(graphy, ymin, s);
  dijkstra(graphs, smin, t);
  vector<ll> ans(n);
  ll min_cash = INF;
  for (int i = n-1; i >= 0; i--) {
    min_cash = min(min_cash, ymin[i] + smin[i]);
    ans[i] = min_cash;
  }
  for (auto a : ans) {
    cout << (ll)1e15-a << endl;
  }

  return 0;
}


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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){


}

Node treeMaximum(Node x){


}

Node treeSearch(Node u, int k){

  if(u == NIL || k == u->key) return u;

  if(k < u->key) return treeSearch(u->left,k);

  else return treeSearch(u->right,k);

}

Node treeSuccessor(Node x){


}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y



}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x != NIL)
    {
      y = x;
      if(z->key < x->key) x = x->left;
      else x = x->right;
    }

  z->parent = y;

  if(y == NIL) root = z;
  else if(z->key < y->key) y->left = z;
  else y->right = z;


}

void inorder(Node u){

  if(u != NIL)
    {
      inorder(u->left);
      printf(" %d",u->key);
      inorder(u->right);
    }
  
}

void preorder(Node u){

  if(u != NIL)
    {
      printf(" %d",u->key);
      preorder(u->left);
      preorder(u->right);
    }

 
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}



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


struct Node {
    int key;
    Node *parent,*left,*right;
    };

Node *root,*NIL;

Node *getminimum(Node *z) {
    while(z->left != NIL) {
        z = z->left;
    }
    return z;
}

Node *find(Node *u,int key) {
    while(u != NIL && key != u->key) {
        if(key < u->key) u = u->left;
        else u = u->right;
    }
    return u;
}

Node *getsuccessor(Node *z) {
    if(z->right != NIL) {
        return getminimum(z->right);
    }
    Node *y = z->parent;
    // while(y != NIL && z == y->right) {
    //     z = y;
    //     y = y->parent;
    // }
    // return y;
}

void deleteNode(Node *z) {
    Node *x,*y;

    if(z->right == NIL || z->left == NIL) {
        y = z;
    }else {
        y = getsuccessor(z);
    }

    if(y->left != NIL) {
        x = y->left;
    }else {
        x = y->right;
    }

    if(x != NIL) {
    x->parent = y->parent;
    }

    if(y->parent == NIL) {
        root = x;
    }else if(y->parent->left == y) {
        y->parent->left = x;
    }else {
        y->parent->right = x;
    }

    if(y != z) {
        z->key = y->key;
    }

    free(y);
}

void insert(int key) {
    Node *y = NIL;
    Node *x = root;
    Node *z;

    z = (Node *)malloc(sizeof(Node));
    z->key = key;
    z->right = NIL;
    z->left = NIL;

    while(x != NIL) {
        y = x;
        if(z->key < x->key) {
            x = x->left;
        }else {
            x = x->right;
        }
    }

    z->parent = y;
    if(y == NIL) {
        root = z;
    }else {
        if(z->key < y->key) {
            y->left = z;
        }else {
            y->right = z;
        }
    }
}

void inorder(Node *u) {
    if(u == NIL) return;
    inorder(u->left);
    cout << " " << u->key;
    inorder(u->right);
}

void preorder(Node *u) {
    if(u == NIL) return;
    cout << " " << u->key;
    preorder(u->left);
    preorder(u->right);
}




int main() {

    int N,k;
    cin >> N;
    string s;
    

    for(int i = 0;i < N; i++) {
        cin >> s;
        if(s == "find") {
            cin >> k;
            Node *t = find(root,k);
            if(t != NIL) cout << "yes" << endl;
            else cout << "no" << endl;
        }else if(s == "insert") {
            cin >> k;
            insert(k);
        }else if(s == "delete") {
            cin >> k;
            deleteNode(find(root,k));
        }else {
            inorder(root);
            cout << endl;
            preorder(root);
            cout << endl;
        }
    }

}



Measured memory_bytes: 21840
#include <bits/stdc++.h>
using namespace std;
const int maxn=1000005;
typedef long long ll;
typedef double dbl;
typedef long double ld;
const ld EPS=1e-9;
const ld PI=3.141592653589793;
const ll MOD = 1e9+7;
const int SQRT = 300;
const int LG=21;
const int FOURIER = (1<<LG);
////////////////
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n,s;
    cin>>n>>s;
    ll b;
    for(b=2; b*b<=n; ++b){
        ll x=n;
        ll sum=0;
        while(x){
            sum+=x%b;
            x/=b;
        }
        if (sum==s){
            cout<<b;
            return 0;
        }
    }
    ll del=n/b;
    if (n==s){
        cout<<n+1;
        return 0;
    }
    if (n<s){
        cout<<-1;
        return 0;
    }
    ll ans=1e18;
    for(ll z=1; z*z<=n-s; ++z){
        if ((n-s)%z==0){
            ll cur_b=(n-s)/z+1;
            if (cur_b>=b){
                if (n%cur_b+z==s)
                    ans=min(ans,cur_b);

            }

        }
    }
    if (ans==1e18){
        cout<<-1;
        return 0;
    }
    cout<<ans;

}



Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        SOD(n);

        long sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += sod_arr[i] * i;
        }
        System.out.println(sum);
    }
    static long[] sod_arr;

    public static void SOD(long n) {
        sod_arr = new long[10000000 + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j += i) {
                // System.out.println("j "+sod_arr[j]);
                sod_arr[j]++;
            }
        }
    }

}


Measured memory_bytes: 116036
package main

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

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  buffer := make([]byte, 0)
  for true {
    line, isPrefix, err := reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func NextInt() int {
  n, _ := strconv.Atoi(NextLine())
  return n
}
func NextIntVec() []int {
  L := strings.Split(NextLine(), " ")
  N := make([]int, len(L))
  for i := range N {
    N[i], _ = strconv.Atoi(L[i])
  }
  return N
}
func Write(s interface{}) {
  fmt.Fprintln(writer, s)
}
func Output() {
  _ = writer.Flush()
}

func MaxInt(A ...int) int {
  max := A[0]
  for _, a := range A {
    if max < a { max = a }
  }
  return max
}

const p = 1000000007

func Factorial(N int) (F, Finv, Inv []int) {
  F = make([]int, N + 1)
  Finv = make([]int, N + 1)
  Inv = make([]int, N + 1)
  F[0] = 1
  F[1] = 1
  Finv[0] = 1
  Finv[1] = 1
  Inv[0] = 1
  Inv[1] = 1
  for i := 2; i < N + 1; i++ {
    F[i] = F[i - 1] * i % p
    Inv[i] = p - Inv[p % i] * (p / i) % p
    Finv[i] = Finv[i - 1] * Inv[i] % p
  }
  return
}

func Primes(a int) map[int]int {
  P := make(map[int]int)
  for k := 2; k * k <= a; k++ {
    if a % k < 1 { P[k] = 0 }
    for a % k < 1 {
      P[k]++
      a /= k
    }
  }
  if 1 < a { P[a] = 1 }
  return P
}

func Solve() {
  N := NextInt()
  A := NextIntVec()
  sort.Ints(A)
  _, _, Inv := Factorial(A[N - 1])
  P := make(map[int]int)
  for _, a := range A {
    _P := Primes(a)
    for k, v := range _P {
      _, ok := P[k]
      if !ok { P[k] = 0 }
      P[k] = MaxInt(P[k], v)
    }
  }
  lcm := 1
  for k, v := range P {
    for i := 0; i < v; i++ {
      lcm *= k
      lcm %= p
    }
  }
  cnt := 0
  for _, a := range A {
    cnt += lcm * Inv[a] % p
    cnt %= p
  }
  Write(cnt)
  return
}

func main() {
  Solve()
  Output()
}

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

public class Main {

	public static void main(String[] args) {
		ArrayList<Integer> A = new ArrayList<Integer>();
		Scanner sc = new Scanner(System.in);

		int q = sc.nextInt();

		for (int i = 0; i < q; i++) {
			int qa = sc.nextInt();

			if (qa == 0) {
				int x = sc.nextInt();
				A.add(x);

			} else if (qa == 1 && A.size() != 0) {
				int x = sc.nextInt();
				System.out.println(A.get(x));

			} else if (qa == 2 && A.size() != 0) {
				A.remove(A.size() - 1);
			}
		}
		sc.close();

	}

}



Measured memory_bytes: 140756
#include<iostream>
#include<vector>
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;

vector<int> v;

int main()
{
	int cnt = 0;
	int N;
	cin >> N;
	REP(i, N)
	{
		int t;
		cin >> t;
		v.push_back(t);
	}
	while (true)
	{
		for (unsigned int i=0;i<v.size();i++)
		{
			if (v[i] % 2 ==0)
			{
				v[i] = v[i]/ 2;
				if(i==v.size()-1)cnt++;
			}
			else
			{
				cout << cnt << endl;
				return 0;
			}
			
		}
	}
	return 0;
}

Measured memory_bytes: 256
// :)
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <sstream>
#include <stack>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <utility>
#include <vector>

typedef long long LL;

using namespace std;

std::random_device rd_device;
std::mt19937 rng(rd_device());

int main() {
    ios::sync_with_stdio(false);
    cin.exceptions(ios_base::failbit);
    cin.tie(NULL);
    cout.tie(NULL);
    cout.precision(10);
    cout<<fixed;
    
    vector<int> a(6);
    for (int i=0;i<6;i++) cin>>a[i];
    sort(a.begin(), a.begin()+5);

    if (a[4] - a[0] > a[5]) cout<<":("<<endl;
    else cout<<"Yay!"<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
   string s,c, tmp;
   tmp="";
   cin>>s;
   int q,t,f,co;
   co=0;
   cin>>q;
   for(int i=0; i<q; i++){
      cin>>t;
      if(t==1){co=co+1;}
      if(t==2){
         cin>>f;
         cin>>c;
         if(f==1&&co%2==0){tmp=tmp+c;}
         if(f==2&&co%2==0){s=s+c;}
         if(f==1&&co%2==1){s=s+c;}
         if(f==2&&co%2==1){tmp=tmp+c;}
      }
   }
   reverse(tmp.begin(), tmp.end());
   s=tmp+s;
   if(co%2==1){reverse(s.begin(),s.end());}
   cout<<s<<endl;
}


Measured memory_bytes: 1784
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll inf = 1e14;

ll N,M,H,K,s,t,p;
struct e{
    ll to,cost,dist,comp;
};

struct state{
    ll node,dist,cost;
    bool operator<(const state& right)const{
        return cost>right.cost;
    }
};

int main(){
    while(cin >> N >> M >> H >> K && N>0){
        vector<vector<ll>> dist(N,vector<ll>(N,inf));
        vector<ll> dp(1<<K,inf),cost(1<<K,inf);
        vector<vector<e>> v(N+1);
        ll a,b,c,h,r;
        for(int i=0;i<M;i++){
            cin >> a >> b >> c >> h >> r;
            a--; b--; r--;
            v[a].push_back({b,c,h,r});
            v[b].push_back({a,c,h,r});
        }
        cin >> s >> t >> p;
        s--; t--;
        ll l,d,k;
        for(int i=0;i<p;i++){
            cin >> l >> d;
            int S = 0;
            for(int j=0;j<l;j++){
                cin >> k; k--;
                S += (1<<k);
            }
            cost[S] = min(cost[S],d);
        }
        dp[0] = 0;
        for(int S=0;S<(1<<K);S++){
            for(int T=0;T<(1<<K);T++){
                dp[S|T] = min(dp[S|T],dp[S]+min(dp[T],cost[T]));
            }
        }
        ll ans = inf;
        for(int S=0;S<(1<<K);S++){
            if(dp[S]==inf) continue;
            vector<vector<ll>> dij(N,vector<ll>(H+1,inf));
            dij[s][0] = 0;
            priority_queue<state> Q;
            Q.push({s,0,0});
            while(!Q.empty()){
                state now = Q.top(); Q.pop();
                if(dij[now.node][now.dist]<now.cost) continue;
                for(auto x:v[now.node]){
                    if(now.dist+x.dist>H) continue;
                    state ne = now;
                    ne.node = x.to;
                    ne.dist += x.dist;
                    ne.cost += (S&(1<<x.comp)? 0:x.cost);
                    if(dij[ne.node][ne.dist]>ne.cost){
                        dij[ne.node][ne.dist] = ne.cost;
                        Q.push(ne);
                    }
                }
            }
            for(int i=0;i<=H;i++) ans = min(ans,dij[t][i]+dp[S]);
        }
        cout << (ans!=inf? ans:-1) << endl;
    }
}


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

using namespace std;

typedef long long ll;

int main(){
    ll a = 0, b = 1, n;
    cin >> n;
    for(int i=0;i<n;i++){
        ll q, x;
        cin >> q >> x;
        if(q==1){
            a *= x;
            b *= x;
        }
        else if(q==2){
            a += x;
        }
        else{
            a -= x;
        }
    }
    cout << -a << " " << b << endl;
    return 0;
}


Measured memory_bytes: 3120
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}

int main() {
    int N;
    cin >> N;
    vector<vector<int>> d(N, vector<int>(N));
    vector<vector<bool>> dn(N, vector<bool>(N, false));
    REP(i, N) {
        REP(j, N) { cin >> d[i][j]; }
    }
    for(int k = 0; k < N; k++) {
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {

                if(d[i][j] > d[i][k] + d[k][j]) {
                    cout << "-1" << endl;
                    return 0;
                }

                if(d[i][j] == d[i][k] + d[k][j] and k != j and k != i) {
                    dn[i][j] = true;
                }
            }
        }
    }
    long long ans = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            if(dn[i][j] == false) {
                ans += d[i][j];
            }
        }
    }
    cout << ans / 2 << endl;
    return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
int k, n, a, b, c, ans;
int main(){
	scanf("%d%d", &k, &n);
	rep(i,n){
		scanf("%d", &b);
		if(i) ans = max(ans, b-c);
		else a = b;
		c = b;
	}
	ans = max(ans, a+k-c);
	printf("%d\n", k-ans);
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
   char c;
   cin>>c;
   if(((int)c==97)||((int)c==101)||((int)c==105)||((int)c==111)||((int)c==117)) cout<<"vowel";
   else cout<<"consonant";
   return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
const long double PI = (acos(-1));
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int ctoi(char c)
{
  switch (c)
  {
  case '0':
    return 0;
  case '1':
    return 1;
  case '2':
    return 2;
  case '3':
    return 3;
  case '4':
    return 4;
  case '5':
    return 5;
  case '6':
    return 6;
  case '7':
    return 7;
  case '8':
    return 8;
  case '9':
    return 9;
  default:
    return 0;
  }
}
int main()
{
  string s;
  cin >> s;

  for (int i = 0; i < 3; i++)
  {
    cout << s[i];
  }
  cout << endl;
}

Measured memory_bytes: 3628
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }

    static class Task {
        int N;
        int ans = 0;

        int numberOfDigits(int n) {
            return (int) Math.floor(Math.log10(n)) + 1;
        }

        void solve(InputReader in, PrintWriter out) {
            N = in.nextInt();
            for (int i = 1; i <= N; ++i) {
                if (numberOfDigits(i) % 2 == 1) ans++;
            }
            out.println(ans);
        }

    }

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] nextIntArray(int size) {
            int[] arr = new int[size];
            for (int i = 0; i < size; i++) {
                arr[i] = nextInt();
            }
            return arr;
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        long[] nextLongArray(int size) {
            long[] arr = new long[size];
            for (int i = 0; i < size; i++) {
                arr[i] = nextLong();
            }
            return arr;
        }
    }
}

Measured memory_bytes: 23508
N = int(input())
s = input().split()
s = list(s[0])
right = 0
left = 0
for i in range(1,N):
    if s[i] == "E":
        right += 1
ans = right
for i in range(1, N):
    if s[i] == "E":
        right -= 1
    if s[i-1] == "W":
        left += 1
    if ans > right + left:
        ans = right + left
print(ans)


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

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rrep(i, n) for (ll i = (n)-1; i >= 0; i--)

int main(int argc, char *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N, M;
    cin >> N >> M;

    vector<vector<bool>> G(10, vector<bool>(10, false));
    rep (i, 10) {
        G[i][0] = true;
        G[0][i] = true;
    }

    vector<int> v(N+1);
    rep (i, N+1) {
        v[i] = i;
    }

    v.erase(v.begin());

    rep (i, M) {
        ll a, b;
        cin >> a >> b;
        G[a][b] = true;        
        G[b][a] = true; // undirected graph
    }

    ll ans = 0;
    do {
        if (v[0] == 1) {
            bool tmp = true;
            for (int i = 0; i < N-1; i++) {
                tmp *= G[v[i]][v[i+1]];
            }
            if (tmp) {
                ans++;
            }
        }
    } while (next_permutation(v.begin(), v.end()));

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
// Author : Rifayat Samee (Sanzee)
// Problem :
// Algorithm:
 
/*
 
*/
#include <bits/stdc++.h>
using namespace std;
#define maxval 100005
int main(){
 
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
    int n,k;
    scanf("%d %d",&n,&k);
    vector<int>h(n+1);
    vector<int>dp(n+1,1e9);
    for(int i=0;i<n;i++){
        scanf("%d",&h[i]);
    }
    dp[0] = 0;
    for(int i=1;i<n;i++){
        for(int j=i-1;j>=i-k && j>=0;j--){
            dp[i] = min(dp[i],abs(h[j]-h[i])+dp[j]);
        }
    }
    printf("%d\n",dp[n-1]);
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cmath>
#include <string>
#include <typeinfo>
#include <climits>
#include <algorithm>
#include <cctype>
#include <stdio.h>
#include <cstdlib>
using namespace std;

int main(){
    int a,b;
    cin >> a >> b;
    cout << (a+b+1)/2;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define INF 1e9
#define MAX_V 20010
using namespace std;

/*最大流アルゴリズム(Ford_Fulerson法使用)　O(F|E|)*/

//辺を表す構造体(行き先、容量、逆辺)
struct edge{int to, cap, rev;};

vector<edge> G[MAX_V]; //グラフの隣接リスト
bool used[MAX_V];      //DFSですでに調べたかのフラグ

//fromからtoへ向かう容量capの辺をグラフに追加する
void add_edge(int from,int to,int cap){
  G[from].push_back((edge){to,cap,(int)G[to].size()});
  G[to].push_back((edge){from,0,(int)G[from].size()-1});  
}


//増加パスをDFSで探す
int dfs(int v,int t,int f){
  if(v == t)return f;
  used[v]=true;
  for(int i=0; i<G[v].size() ;i++){
    edge &e = G[v][i];
    if(!used[e.to] && e.cap > 0){
      int d = dfs(e.to ,t , min(f,e.cap));
      if(d > 0){
	e.cap -= d;
	G[e.to][e.rev].cap += d;
	return d;
      }
    }
  }
  return 0;
}

//sからtへの最大流を求める
int max_flow(int s,int t){
  int flow = 0;
  for(;;){
    memset(used,0,sizeof(used));
    int f = dfs(s, t, INF);
    if(f == 0)return flow;
    flow += f;
  }
}


int main(){
  int h,w;
  cin>>h>>w;
  string mp[101];
  
  for(int i=0;i<h;i++)cin>>mp[i];

  int s,t;
  int cnt=0;
  
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++){

      int pos = i*w+j;
      add_edge(i*w+j+w*h,pos,1);
      if(mp[i][j] == '.')continue;
      cnt++;
      if(mp[i][j] == 'S') s = pos;
      if(mp[i][j] == 'T') { t = pos+w*h;continue;}
      
      for(int k=0;k<h;k++)
	if(k!=i&&mp[k][j]!='.')add_edge(pos,(k*w+j)+w*h,100000);
      
      for(int k=0;k<w;k++)
	if(k!=j&&mp[i][k]!='.')add_edge(pos,(i*w+k)+w*h,100000);
    }

  int ans = max_flow(s,t);
  if(ans>=cnt-1)cout<<-1<<endl;
  else cout<<ans<<endl;
  return 0;
}


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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};


int main()
{
    string s;
    cin>>s;
    
    for(int i = 0; i < s.size(); i+=2)
    {
        cout<<s[i];
    }
    cout<<endl;

    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <vector>
#include <sstream>
#include <string>
#include <cstdio>
#include <array>


//???????????°??????TEST????????????????????¬???????????????????????????????????¢????????????
//#define TEST //*******************************************************************************************************************************************

//?????????????????¨??§?????\????????????????????????????????°?????????????¨???????????????????dout???????????????????????§???????????¬??????????????????????????????????????????
#ifdef TEST
    #define dout cout
#else
    #define dout dummy
#endif

using namespace std;
stringstream dummy; //????¨????????????°??¨dout?????????????????????????????????


int main(void) {
    int n;
    cin >> n;
    
    int r[n];
    for(int i=0; i<n; i++) {
        cin >> r[i];
    }

    int profit = r[1]-r[0];
    int r_min = r[0];
    
    dout << "default : " << "r_min = " << r_min << " : " << "profit = " << profit << " : \n";

    for(int i=1; i<n; i++) {
        
        dout << "i = " << i << " : ";
        
        if( profit < r[i]-r_min) {
            profit = r[i]-r_min;
            
            dout << "profit = " << profit << " : ";

        }
        
        if( r_min > r[i] ) {
            r_min = r[i];

            dout << "r_min = " << r_min << " : ";
        }
        dout << endl;
    }

    dout << "ans = ";
    cout << profit << endl;
    
    return 0;
}

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define REP(NAME, NUM) for (int NAME = 0; NAME < (NUM); ++NAME)
#define BREP(NAME, NUM) for (int NAME = (NUM)-1; NAME >= 0; --NAME)
#define ALL(NAME) (NAME).begin(), (NAME).end()

#define cMOD 1000000007ULL
#define cINF ((1ull<<62)-1)
#define cINFINT ((1<<30)-1)


int main()
{
	ll n,a,b,c,d;cin>>n>>a>>b>>c>>d;
	--a,--b,--c,--d;
	string s;cin>>s;
	auto lock = [&s](ll i) { return s[i]=='#'; };
	auto ddlock = [lock](ll a, ll c)
	{
		bool lll = false;
		for(ll i =a; i<c-1; ++i)
		{
			if( lock(i) && lock(i+1) ) return true;
		}
		return false;
	};
	auto dddopen = [lock](ll a, ll c)
	{
		bool lll = false;
		for(ll i =a; i<c-2; ++i)
		{
			if(!lock(i)&&!lock(i+1)&&!lock(i+2))
				return true;
		}
		return false;
	};

	if( ddlock(a,c) ) cout << "No" << endl;
	else if( ddlock(b,d) ) cout << "No" << endl;
	else if( c < d ) cout << "Yes" << endl;
	else if( dddopen( b-1, d+2 ) ) cout << "Yes" << endl;
	else cout << "No" << endl;
	
	return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<cstdlib>
#include<stack>
#include<queue>
#include<algorithm>
#include<set>
#include<vector>
#include<cmath>
#include<string>
#include<deque>
#define lmid l,mid,rt<<1
#define rmid mid+1,r,rt<<1|1
using namespace std;
long long s[100005];
int main() {
     int n;
     scanf("%d", &n);
     long long sum = 0;
     for(int i = 0; i < n; i++)
          scanf("%lld", &s[i]);
     sort(s, s + n);
     int ans = 0, res = s[0];
     for(int i = 0; i < n; i++) {
          if(res == s[i]) {
               ans++;
          }
          if(res != s[i]) {
               if(ans >= s[i-1]) {
                    sum += ans - s[i-1];
               } else sum += ans;
               ans = 1;
               res = s[i];
          }
     }
     if(ans >= s[n-1]) {
          sum += ans - s[n-1];
     } else sum += ans;
     printf("%lld\n",sum);
     return 0;
}


Measured memory_bytes: 1024
a,b,k = map(int,input().split())
def c(x,y):
 if x%2 == 1:
  x = x-1
 x = int(x/2)
 y += x
 return x,y
 
for j in range(k):
 if j % 2 == 0:
  a,b = c(a,b)
 else:
  b,a = c(b,a)

print(a,b)


Measured memory_bytes: 3060
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    A = list(map(int, args[1].split()))

    A.sort()
    p = A[0]
    for a in A[1:]:
        if a == p:
            return 'NO'
        p = a

    return 'YES'


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Measured memory_bytes: 26988
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 10000001
struct job{
	int needtime;
	int deadtime;
};
job a[MAXN];
bool cmp(job a, job b){
	return a.deadtime < b.deadtime;
}
int main(){
	int N;
	cin >> N;
	int sum = 0;
	for(int i = 0; i < N; i++){
		cin >> a[i].needtime >> a[i].deadtime;
	}
	sort(a, a+N, cmp);
	for(int i = 0; i < N; i++){
		sum += a[i].needtime;
		if(sum > a[i].deadtime)
		{
			cout << "No" << endl;
		    return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 1792
k=int(input())
lit=str(input()).split(" ")
a=int(lit[0])
b=int(lit[1])

if k == 1:
    print("OK")
    exit()

if a % k == 0:
    print("OK")
    exit()

if b % k == 0:
    print("OK")
    exit()

if a // k == b // k:
    print("NG")
else:
    print("OK")

Measured memory_bytes: 9192