akhauriyash/Code-Regression huggingface dataset:
#include <regex>
#include "bits/stdc++.h"
#define FOR(i, s, e) for (int i = int(s); i < int(e); ++i)
#define REP(i, e) FOR(i, 0, e)
#define INF (INT_MAX / 2)
#define LINF (LLONG_MAX / 2)
#define EPS (1.0e-8)
#define mkpr make_pair
const int MGN = 2;
const int ARY_SZ_MAX = (int)1e7;
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vc = vector<char>;
using vvc = vector<vc>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vd = vector<double>;
using vs = vector<string>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using psl = pair<string, ll>;

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

  string S; cin >> S;
  int K; cin >> K;
  int L = S.size();

  auto dp = vector<vvl>(L+MGN, vvl(K + MGN, vl(2, 0)));
  // dp[i][j][k] := S[0,i] (上位から i ) 桁目までを決め、非 0 を j 個使い、
  // そこまでの桁が S と一致していたら k = 0, 一致していないで、既に S
  // の値より小さくなることが確定していたら k = 1 とするときの通り数
  dp[0][0][0] = 1;

  REP(i, L) {
    const int DMAX = S[i] - '0'; // i 桁目で選択できる最大値
    REP(j, K + 1) {
      REP(k, 2) {
        
        if (k == 0) { // i 桁目までが S と一致していたら
          REP(nd, DMAX+1) {
            int nj = j;
            if (nd > 0) nj++; // 非 0 を使った
            if (nj > K) break; // 非 0 の使用個数を超えた

            int nk = k;
            if (nd == DMAX) nk = 0;
            else { assert(nd < DMAX);
              nk = 1;
            }

             dp[i+1][nj][nk] += dp[i][j][k];
          }
        } else { // i 桁目までで S より小さいことが確定していたら
          assert(k == 1);
          REP(nd, 10) {
            int nj = j;
            if (nd > 0) nj++; // 非 0 を使った
            if (nj > K) break; // 非 0 の使用個数を超えた

            dp[i+1][nj][1] += dp[i][j][k];
          }
        }

      }
    }
  }

  ll ans = dp[L][K][0] + dp[L][K][1];
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
n,m,l=gets.split.map(&:to_i)
a=Array.new(n){ gets.split.map(&:to_i) }
b=Array.new(m){ gets.split.map(&:to_i) }
c=Array.new(n){ Array.new(l) }
n.times do |i|
  l.times do |j|
    c[i][j]=a[i].zip(b.transpose[j]).map{|a,b|a*b}.reduce(:+)
  end
end
puts c.map{|l|l*' '}


Measured memory_bytes: 14584
#include<iostream>
#include<algorithm>
#include<vector>
#include<climits>

using namespace std;
int N, M, Q, maxScore = INT_MIN;
vector<int> a, b, c, d;

void dfs(vector<int> &A)
{
	if((int)A.size()==N+1)
	{
		int currScore = 0;
		for(int i=0; i<Q;i++)
		{
			if(A[b[i]]-A[a[i]]==c[i])
			{
				currScore+=d[i];
			}
		}
		maxScore = max(maxScore, currScore);
		return;
	}
	int prev = A.back();
	for(int newElem = prev; newElem<=M;newElem++)
	{
		A.push_back(newElem);
		dfs(A);
		A.pop_back();
	}
}
int main()
{
	cin>>N>>M>>Q;
	a=b=c=d = vector<int>(Q);
	for(int i=0; i<Q;i++)
	{
		cin>>a[i]>>b[i]>>c[i]>>d[i];
	}
	vector<int> v(1,1);
	dfs(v);
	cout<<maxScore<<"\n";
	return 0;
}

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

int main()
{
    long  a, b, c, k;
    cin >> a >> b >> c >> k;
    long d = 0;
  	if (k < a) {
      cout << k; 
  return 0; 
    }
    else {
    k-= a;
    d += a;
    if (k > 0) {
        k-= b;
        if (k > 0) {
            d -= k;
        }
    }
    }
    cout << d;
    return 0;
}

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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
//#define int long long int
const int MOD = 1000000007;
const ll LINF = (ll)1e18 - 1;
const int INF = 1e9 - 1;
const double EPS = 0.000000001;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void print(const vector<int> &v) {
  for(auto x : v) {
    cout << x << " ";
  }
  cout << endl;
}

signed main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  VL h(n);
  rep(i, n) cin >> h[i];
  VI ans(n, 0);
  int ret = 0;
  for(int i = n-1; i >= 1; --i) {
    h[i-1] >= h[i] ? ans[i-1] = ans[i] + 1 : ans[i-1] = 0;
    ret = max(ret, ans[i-1]);
  }
  out(ret);
  return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <iomanip>
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const ll MOD=1000000007;
const ll MAX_N=500010;
const ll INF=999999999999;

int main(){
    ll k;
    cin>>k;
    string s;
    cin>>s;
    if(s.length()>k){
        for(ll i=0;i<k;i++){
            cout<<s[i];
        }
        cout<<"..."<<endl;
    }else{
        cout<<s<<endl;
    }
}

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

int main()
{
  	int n;
	cin >> n;
  	vector<int> data(n);
  	int count = 0;
  	for (int i=0; i<n; ++i) {
      	cin >> data[i];
      	if ( (i+1) % 2 == 1 && data[i] % 2 == 1) {
          count ++;
        }
    }
  
  	cout << count;
    return 0;
}

Measured memory_bytes: 3620
#include<stdio.h>
main(){
    int x,y;
    while(1){
        scanf("%d %d",&x,&y);
        if(x == 0 && y == 0) break;
        if(x < y)
            printf("%d %d\n",x,y);
        else
            printf("%d %d\n",y,x);
    }
    return 0;
}


Measured memory_bytes: 2040
#include<bits/stdc++.h>
#define ll long long
#define dl double
#define mp make_pair
#define pb push_back
using namespace std;

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

// hash struct for unordered_map
struct hash_pair { 
    template <class T1, class T2> 
    size_t operator()(const pair<T1, T2>& p) const
    { 
        auto hash1 = hash<T1>{}(p.first); 
        auto hash2 = hash<T2>{}(p.second); 
        return hash1 ^ hash2; 
    } 
};

int MAXNUM = 5e3+5;
vector <int>vis(MAXNUM);
vector<int> pr;
void sieve() {
	pr.push_back(2);
	for(ll i=3;i<MAXNUM;i+=2) if(!vis[i]) {
		pr.push_back(i);
		for(ll j=i*i;j<MAXNUM;j+=2*i) vis[j]=true;
	}
}
//************************************************************************

void solve()
{
    ll n;
    cin >> n;
    map<ll,ll> m;
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        ll x;
        cin >>x;
        ans+=x;
        if(m.find(x)==m.end())
        m[x]=1;
        else
        m[x]++; 
    }
    ll q;
    cin >> q;
    while(q--)
    {
        ll b,c;
        cin >> b >> c;
        ll cnt=0;
        if(m.find(b)!=m.end())
        {
            cnt=m[b];
            ans-=cnt*b;
            m.erase(b);
            ans+=cnt*c;
            if(m.find(c)==m.end())
            m[c]=cnt;
            else
            m[c]+=cnt;
        }
        cout << ans << endl;
    }
}


int main()
{ 
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
	ll t;
	//cin >> t;
	t=1;
	while(t--)
	{
		solve();
	}

	return 0;
}

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

int main(){
  int h[10];
  for(int i=0;i<10;i++){
    cin>>h[i];
  }
  for(int j=0;j<10;j++){
    for(int k=0;k<9 -j;k++){
      if(h[k]<h[k+1]){
	int a=h[k],b=h[k+1];
	h[k]=b;
	h[k+1]=a;
      }
    }
  }
  for(int l=0;l<3;l++){
    cout<<h[l]<<endl;
  }
	
	
      
  
    return 0;
}




Measured memory_bytes: 3080
# -*- coding: utf-8 -*-
# if x < y:
#     z = x
# elif True:
#     z = y
# else:
#     z = 100
import sys,os,math
from collections import Counter, defaultdict
import bisect
from sys import stdin, stdout
from itertools import repeat


# n, k = map(int, raw_input().split())
# da = map(int, raw_input().split())
# db = map(int, raw_input().split())

def main():
    n = map(int, raw_input().split())[0]
    s = raw_input().strip()
    d = [[0 for i in range(n+5)] for i in range(n+5)]
    mx = 0
    for i in range(1, n+1):
        for j in range(i, n+1):
            if s[i-1] == s[j-1]:
                d[i][j] = min(d[i-1][j-1]+1, abs(j-i))
                # print d[i][j], i, j
                mx = max(mx, d[i][j])
            else:
                d[i][j] = 0
    print mx

main()


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

#define INF 1000010000
#define nl '\n'
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pdd pair<double,double>
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define sz(c) (c).size()
#define rep(i,n) for( int i = 0; i < n; ++i )
#define repi(i,n) for( int i = 1 ; i <= n; ++i )
#define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
#define repf(j,i,n) for( int j = i ; j < n ; ++j )
#define die(s) {std::cout << s << nl;}
#define dier(s) {std::cout << s; return 0;}
#define vi vector<int>
typedef long long ll;

using namespace std;


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

	string s;
	cin >> s;
	bool f = s[0] == s[2];
	cout << (f ? "Yes" : "No");

	return 0;
}

Measured memory_bytes: 256
//use itertools::Itertools;
use std::cmp;
use std::collections::BTreeMap;
use std::collections::BTreeSet;
use std::collections::BinaryHeap;
use std::collections::HashMap;
use std::collections::HashSet;
use std::collections::VecDeque;
use std::io::Read;
use std::usize::MAX;

macro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();let mut next = || { iter.next().unwrap() };input_inner!{next, $($r)*}};($($r:tt)*) => {let stdin = std::io::stdin();let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));let mut next = move || -> String{bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect()};input_inner!{next, $($r)*}};}
macro_rules! input_inner {($next:expr) => {};($next:expr, ) => {};($next:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($next, $t);input_inner!{$next $($r)*}};}
macro_rules! read_value {($next:expr, ( $($t:tt),* )) => {( $(read_value!($next, $t)),* )};($next:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()};($next:expr, chars) => {read_value!($next, String).chars().collect::<Vec<char>>()};($next:expr, usize1) => {read_value!($next, usize) - 1};($next:expr, [ $t:tt ]) => {{let len = read_value!($next, usize);(0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()}};($next:expr, $t:ty) => {$next().parse::<$t>().expect("Parse error")};}

fn solve() {
    input! {
        n: usize,
        k: usize,
        a: [usize;n]
    }

    for i in k..n {
        let mut perge = a[i - k];
        let mut add = a[i];
        if add > perge {
            println!("Yes");
        } else {
            println!("No");
        }
    }

    let mut ans = 0;
}

fn main() {
    let thd = std::thread::Builder::new().stack_size(104_857_600);
    thd.spawn(|| solve()).unwrap().join().unwrap();

    /*
    // 入力を一括で読み込む場合
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut input = buf.split_whitespace();

    // inputに対しnext()で読み込んでいく
    let q: usize = input.next().unwrap().parse().unwrap();
    */
}

const LARGE_PRIME: u64 = 1_000_000_007;

// @〜でsnippet


Measured memory_bytes: 2704
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define fill(x,v) memset(x, v, sizeof(x))
#define PI (ld)acos(-1)
#define endl '\n'
#define dbg(x) cout<<#x<<"="<<(x)<<endl;
#define dbg2(x,y) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<endl; 
#define fio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 
#define IO freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
const ld eps=(ld)1e-9;
const ll inf=(ll)1e18;
const ll mod=(ll)1e9+7;
string s,t;
int n,m;
int d[3001][3001];
void f(){
	for (int i = 1; i <=n; ++i)
	{
		for (int j = 1; j <=m; ++j)
		{
			if(s[i-1]==t[j-1]){
				d[i][j]=1+d[i-1][j-1];
			}
			else{
				d[i][j]=max(d[i-1][j],d[i][j-1]);
			}
		}
	}
	string ans="";
	int i=n, j=m;
	while(i>0 && j>0)
	{
		if(s[i-1]==t[j-1]){
			ans+=s[i-1];
			i--;j--;
		}
		else if(d[i-1][j]>d[i][j-1]){
			i--;
		}
		else j--;
	}
	reverse(all(ans));
	cout<<ans;

}


void solve(){
	cin>>s>>t;
	n=s.length();
	m=t.length();
	fill(d,0);
	f();
}

int main(){fio;
int test=1;
// cin>>test;
while(test--){
	solve();
	cout<<endl;
}
return 0;
}


Measured memory_bytes: 35456
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define f first
#define s second
#define mp make_pair
#define sz size()
int n;
int x[20], y[20], sost[20];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; ++i)
		cin >> x[i] >> y[i];
	for(int i = 1; i <= n; ++i) sost[i] = i;
	double ans = 0;
	int cnt = 0;
	do {
		cnt++;
		for(int i = 1; i < n; ++i) {
			double dx = x[sost[i + 1]] - x[sost[i]];
			double dy = y[sost[i + 1]] - y[sost[i]];
			ans += sqrt(dx * dx + dy * dy);
		}
	} while(next_permutation(sost + 1, sost + n + 1));
	cout << fixed << setprecision(10) << ans / cnt;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main () {
  int64_t N;
  cin >> N;
  int64_t B;
  for(int64_t A = sqrt(N) + 1; A > 0; A--) {
    if(N % A == 0) {
      B = A;
      break;
    }
  }
  int64_t C = N / B;
  cout << B + C - 2 << endl;
}

Measured memory_bytes: 3608
<?php
 $abc = explode(" ",fgets(STDIN));
 $tmp = $abc[1];
 $abc[1] = $abc[0];
 $abc[0] = $tmp;
 $tmp = $abc[2];
 $abc[2] = $abc[0];
 $abc[0] = $tmp;
 echo $abc[0]." ".$abc[1]." ".$abc[2];
?>


Measured memory_bytes: 3828
#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

static const int N = 100;
static int m[N + 1][N + 1] = {}, p[N + 1] = {};

static inline void matrixChainMultiplication(int n) {
  for (int l = 2; l <= n; l++) {
    for (int i = 1; i <= n - l + 1; i++) {
      int j = i + l - 1;
      m[i][j] = INT_MAX;
      for (int k = i; k <= j - 1; k++) {
        m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]); 
      }
    }
  }
}

int main() {
  int n;
  cin >> n;
  
  for (int i = 1; i <= n; i++) {
    cin >> p[i - 1] >> p[i];
  }

  matrixChainMultiplication(n);
  
  cout << m[1][n] << endl;

  return 0;
}



Measured memory_bytes: 3128
#include <iostream>
#include <iomanip>
#include <math.h>
#include <map>
#include <list>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <string>
#include <sstream>
#include <string.h>
// #include <limits.h>

#define FOR(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define FORUL(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define FORULE(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define FOREACH(it, X) for(__typeof((X).begin()) it = (X).begin(); it != (X).end(); it++)
#if defined(_MSC_VER) || __cplusplus > 199711L
#define AUTOVAR(newvar,v) auto newvar = (v)
#else
#define AUTOVAR(newvar,v) __typeof(newvar) r = (v)
#endif
#define PB(x) push_back(x)
#define MP(x,y) make_pair((x),(y))
#define MEMSET(m,v) memset(m,v,sizeof(m))

typedef long long				 ll;
typedef unsigned long long		ull;

#define INTMAX  99999999

#define DEBUG 1

#if DEBUG
#define DOUT cout<<"["<<__LINE__<<"]:"
#else
#define DOUT 0 && cout
#endif

using namespace std;

#define MAX_N (100000)

int N;
int A[MAX_N+5];
int B[MAX_N+5];
ll R[MAX_N+5];

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

	ll count = 0;
	cin >> N;
	FOR(n,N) {
		cin >> A[n] >> B[n];
		R[n] = B[n] - A[n];
		// R[n] %= B[n];
		// int diff = (R[n]-count)%B[n];
		// DOUT << "diff("<<n<<")="<<diff<<endl;
		// count += diff;
	}

	// count = R[N-1]%B[N-1];
	// DOUT << "count["<<N-1<<"]="<<R[N-1];
	for(int n=N-1; n>=0; n--) {
		ll diff = (R[n] - count) % B[n];
		if (diff<0) { diff += B[n]; }
		// DOUT << "diff("<<n<<")="<<diff<<endl;
		count += diff;
	}

	cout << count << endl;

	return 0;
}



Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
    
int main(){
  long long n;
  cin>>n;
  long long funf;//素因数分解したときの5の個数
  long long tmp=10;
  if(n%2!=0){
    cout<<0<<endl;
    return 0;
  }
  while(tmp<=n){
    funf += n/tmp;
    tmp= tmp*5;
  }
  cout<<funf<<endl;
  return 0;
}

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

int r(int list[5], int i, int min, int sum) {
  // std::cout << i << ' ' << min << ' ' << sum << ' ' << list[i] << std::endl;
  if (i == 5) {
    return sum + min;
  }
  if (list[i] % 10 == 0) {
    return r(list, i + 1, min, sum + list[i]);
  }
  if (list[i] % 10 > min % 10) {
    return r(list, i + 1, min, sum + list[i] / 10 * 10 + 10);
  }
  return r(list, i + 1, list[i], sum + min / 10 * 10 + 10);
}

int main(int argc, const char *argv[]) {
  int a, b, c, d, e;
  std::cin >> a >> b >> c >> d >> e;
  int list[5] = {a, b, c, d, e};
  int re = r(list, 1, a, 0);
  std::cout << re << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,n) for(int _tmp=n,i=a;i<=_tmp;++i)
#define dep(i,a,n) for(int _tmp=n,i=a;i>=_tmp;--i)
#define re(i,a,n) for(int _tmp=n,i=a;i<_tmp;++i)
#define fec(i,a) for(__typeof a.begin() i=a.begin();i!=a.end();++i)
#define For(i,v,u) for(int i=H[u],v=to[i];i;i=nxt[i],v=to[i])
#define si(x) (int)x.size()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define X first
#define Y second
#define inf 1000000000
using namespace std;
template<class T> inline void read(T&x){char c;bool fu=0;for(c=getchar();c<=32;c=getchar());if(c=='-')fu=1,c=getchar();for(x=0;c>32;c=getchar())x=x*10+c-'0';if(fu)x*=-1;}
template<class T> inline void read(T&x,T&y){read(x);read(y);}
template<class T> inline void read(T&x,T&y,T&z) {read(x,y);read(z);}
template<class T> inline void MAX(T&x,T y){if(x<y)x=y;}
template<class T> inline void MIN(T&x,T y){if(x>y)x=y;}
typedef long long ll;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tiii;
const int N=1111111;
const ll mo=1e9+7;
//head
ll fac[N],inv[N],ans;
int n,m,k;
ll C(int n,int m){
	if(n<m)return 0;
	return fac[n]*inv[m]%mo*inv[n-m]%mo;
}
ll pw(ll a,ll b,ll p=mo){
	ll an=1;
	for(;b;b>>=1){
		if(b&1)an=an*a%mo;
		a=a*a%mo;
	}
	return an;
}
int main() {
	fac[0]=fac[1]=inv[0]=inv[1]=1;
	rep(i,2,1000000)fac[i]=fac[i-1]*i%mo;
	rep(i,2,1000000)inv[i]=(mo-mo/i)*inv[mo%i]%mo;
	rep(i,2,1000000)inv[i]=inv[i-1]*inv[i]%mo;
	read(n,m,k);
	//rep(i,0,m)rep(j,0,k)(ans+=C(i+j+n-1,i+j)*C(i+j,j)%mo*pw(3,m+k-i-j)%mo)%=mo;
	//rep(i,0,m+k)rep(j,max(0,i-k),min(i,m))(ans+=C(i+n-1,i)*C(i,j)%mo*pw(3,m+k-i)%mo)%=mo;ll c
	ll cur=1;
	rep(len,0,m+k) {
		ll res=0;
		res=C(n+len-1,n-1)*pw(3,m+k-len)%mo;
		(ans+=cur*res%mo)%=mo;
		cur=cur*2%mo;
		if(len>=m)cur+=mo-C(len,m);
		if(len>=k)cur+=mo-C(len,k) ;
	}
	cout<<ans;
	return 0;
}

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

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

bool ispal(string s)
{
	string t = s;
	reverse(t.begin(),t.end());
	return (t==s);
}

//how to describe a state?
vector<pair<string,ll> > vec[2];

struct state
{
	int id;
	int dir; //1 if reverse
	int charleft; //characters left in this string
	bool operator < (const state& str) const
    {
        if(id!=str.id) return id<str.id;
        if(dir!=str.dir) return dir<str.dir;
        if(charleft!=str.charleft) return charleft<str.charleft;
        return false;
    }
    bool operator == (const state& str) const
    {
		return (id==str.id&&dir==str.dir&&charleft==str.charleft);
	}
};

state cre(int id, int dir, int charleft)
{
	state s;
	s.id=id; s.dir=dir; s.charleft=charleft;
	return s;
}

map<state,ll> ma;

bool isterm(state s)
{
	if(s.id<0) return true; //empty state
	string curs = vec[s.dir^1][s.id].fi.substr(0,s.charleft); //reverse direction to get pref from suf
	return ispal(curs);
}

priority_queue<pair<ll,state>, vector<pair<ll,state> >, greater<pair<ll,state> > > pq;

void add(state s, ll newd)
{
	////cerr<<"PUSH "<<s.id<<' '<<s.dir<<' '<<s.charleft<<' '<<newd<<'\n';
	if(!ma.count(s)) 
	{
		ma[s]=ll(1e18)+1;
		//////cerr<<ma[s]<<'\n';
	}
	if(newd<ma[s])
	{
		////cerr<<"PUSH "<<s.id<<' '<<s.dir<<' '<<s.charleft<<' '<<newd<<'\n';
		ma[s]=newd;
		pq.push({newd,s});
	}
}

bool match(string s, string t)
{
	for(int i=0;i<min(int(s.length()),int(t.length()));i++)
	{
		if(s[i]!=t[i]) return false;
	}
	return true;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n;i++)
	{
		string s; int w; cin>>s>>w;
		vec[0].pb({s,w});
		reverse(s.begin(),s.end());
		vec[1].pb({s,w});
	}
	ll ans = ll(1e18);
	for(int i=0;i<n;i++)
	{
		state news = cre(i,0,vec[0][i].fi.length());
		add(news,vec[0][i].se);
	}
	while(!pq.empty())
	{
		ll d = pq.top().fi; state s = pq.top().se; pq.pop();
		if(isterm(s))
		{
			ans=min(ans,d); continue;
		}
		//update new states!
		string curs = vec[s.dir^1][s.id].fi.substr(0,s.charleft);
		reverse(curs.begin(),curs.end()); //this makes it into normal form I think
		//cerr<<"LOOK AT "<<s.id<<' '<<s.dir<<' '<<s.charleft<<' '<<d<<' '<<curs<<'\n';
		for(int i=0;i<n;i++)
		{
			//add at s.dir^1 direction!
			string curt = vec[s.dir^1][i].fi;
			////cerr<<"APPEND "<<i<<" is "<<curt<<'\n';
			if(match(curs,curt))
			{
				ll cost = vec[s.dir^1][i].se;
				if(curs.length()<curt.length())
				{
					add(cre(i,s.dir^1,curt.length()-curs.length()),d+cost);
				}
				else if(curs.length()>curt.length())
				{
					add(cre(s.id,s.dir,s.charleft-curt.length()),d+cost);
				}
				else
				{
					add(cre(-1,-1,-1),d+cost);
				}
			}
		}
	}
	if(ans>=ll(1e18)) ans=-1;
	cout<<ans<<'\n';
}


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

typedef long long ll;
const ll INF = 1LL << 60;

inline bool chmin(ll& a, ll b) { if (a > b) { a = b; return true; } return false; }
inline bool chmax(ll& a, ll b) { if (a < b) { a = b; return true; } return false; }

string s, t;
vector<vector<ll>> dp;

int main() {

  cin >> s >> t;

  dp = vector<vector<ll>>(s.size()+10,vector<ll>(t.size()+10,0));

  dp.at(0).at(0) = 0;

  for (ll i=0;i<s.size();i++){
    for (ll j=0;j<t.size();j++){
      if (s.at(i)==t.at(j)) {
        chmax(dp.at(i+1).at(j+1),dp.at(i).at(j)+1);
      } else {
        chmax(dp.at(i+1).at(j+1),dp.at(i+1).at(j));
        chmax(dp.at(i+1).at(j+1),dp.at(i).at(j+1));
      }
    }
  }

  //dp.at(s.size()).at(t.size())に文字数が入っている。
  ll i = s.size();
  ll j = t.size();
  string ans = "";
  while (i > 0 && j > 0){
    if (dp.at(i).at(j) == dp.at(i-1).at(j)){
      i--;
      continue;
    }

    if (dp.at(i).at(j) == dp.at(i).at(j-1)){
      j--;
      continue;
    }

    ans = s.at(i-1) + ans;
    i--;
    j--;
  }
  cout << ans << endl;
}

Measured memory_bytes: 71168
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <math.h>
#include <vector>
#include <map>
#include <queue>
#include <utility>
#include <algorithm>
#include <string>
using namespace std;

int main() {
  int N;
  cin >> N;
  double ans = 0.0;
  for (int i = 0; i < N; i++) {
	  string u;
	  double x;
	  cin >> x >> u;
	  if (u[0] == 'J') {
		  ans += x;
		} else {
		  ans += 380000.0 * x;
		}
	}
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
//TwoCoins.java
import java.util.Scanner;
class Main
{
	public static void main(String args[])
	{
		Scanner sc=new Scanner(System.in);
		int a=sc.nextInt();
        int b=sc.nextInt();
        int c=sc.nextInt();

        if(a+b<c){
            System.out.println("No");
        }
        else{
            System.out.println("Yes");
        }
        sc.close();
    }
}

Measured memory_bytes: 21844
#include<iostream>
#include<vector>
#include<map>
#include<string>

using namespace std;

struct ITEM {
	vector<string> rishipi;//???????????????????????´??????????£??????????
	int s_price;//????£?????????????
};

int n, m;
map<string, ITEM> item;//????£?????????????
map<string, int> memo;//?????????????????????????????¢

int getprice(string &_item) {
	if (memo[_item] != 0)return memo[_item];//??????????????¨?¢????

	int sum = 0;
	if (item[_item].rishipi.size() == 0)return memo[_item] = item[_item].s_price;//????£????
	else {
		int sum = 0;
		for (int i = 0; i < item[_item].rishipi.size(); i++) {
			sum += getprice(item[_item].rishipi[i]);//?????°?????????????????????
		}
		if (sum < item[_item].s_price)return memo[_item] = sum;
		else return memo[_item] = item[_item].s_price;
	}

}

int main(){
	while (true) {
		cin >> n;
		if (n == 0)break;
		for (int i = 0; i < n; i++) {
			string tmp;
			int a;
			cin >> tmp >> a;
			item[tmp].s_price = a;
			memo[tmp] = 0;
		}
		cin >> m;
		for (int i = 0; i < m; i++) {
			string t;
			cin >> t;
			int a;
			vector<string> tmp;
			cin >> a;
			tmp.resize(a);
			for (int j = 0; j < a; j++) {
				cin >> tmp[j];
			}
			item[t].rishipi = tmp;
		}
		string ans;
		cin >> ans;
		//??\?????????
		cout << getprice(ans) << endl;
		//????????????
	}
	return 0;
}

Measured memory_bytes: 3168
#include<stdio.h>

int main()
{
	int x, y, tmp;

	while(1) {
		scanf("%d%d", &x, &y);

		if(x == 0 && y == 0) break;

		if(x > y) {
			tmp = x;
			x = y;
			y = tmp;
		}

		printf("%d %d\n", x, y);
	}

	return 0;
}



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

using namespace std;
#define ll long long
#define fr first 
#define sc second 

int main()
{
	//freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    string s;
    cin>>s;
    bool b =false;
    for(int i=3;i>=2;i--)
    {
    	if(s[i]==s[i-1] and s[i-1]==s[i-2]) b =true;
    }

    if(b) cout<<"Yes";
    else cout<<"No";
}

Measured memory_bytes: 256
// #include <boost/multiprecision/cpp_int.hpp>
// using boost::multiprecision::cpp_int;
#include <bits/stdc++.h>
using namespace std;
// ¯\_(ツ)_/¯
#define f first
#define s second
#define p push
#define mp make_pair
#define pb push_back
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define all(v) v.begin(), v.end()
#define sz(x) ((int)(x).size())
#define endl " \n"
#define newl cout<<"\n"
#define MAXN 100005
#define MOD 1000000007LL
#define EPS 1e-13
#define INFI 1000000000             // 10^9
#define INFLL 1000000000000000000ll //10^18
// ¯\_(ツ)_/¯
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define vll vector<long long>
#define vvll vector<vll>
//vector<vector<int>> v(10, vector<int>(20,500)); 2d vector initialization. of 10 rows and 20 columns, with value 500.
#define pll pair<long long, long long>

#define fast_io()                   \
  ios_base::sync_with_stdio(false); \
  cin.tie(NULL);                    \
  cout.tie(NULL);

ll tc, n, m, k;
// ll ans = 0, c = 0;
// ll i, j;
// ll a, b;
// ll x, y;



int main()
{
    fast_io();
#ifndef ONLINE_JUDGE
    //freopen("../input.txt", "r", stdin);
    //freopen("../output.txt", "w", stdout);
#endif


    string s1, s2;
    cin>>s1>>s2;
    n = sz(s1);
    m = sz(s2);
    string ans = "";
    ll len = 0;
    vector<vector<ll>> dp(n+1, vector<ll>(m+1, 0));
    rep(i, 1, n+1) {
        rep(j, 1, m+1) {
            if(s1[i-1] == s2[j-1]) dp[i][j] =  dp[i-1][j-1] + 1;
            else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
            len = max(len, dp[i][j]);
        }
    }
    ll x = n, y = m;
    while(x && y) {
        if(s1[x-1] == s2[y-1]) {
            ans += s1[x-1];
            x--;
            y--;
        } else if (dp[x][y] == dp[x-1][y]) {
            x--;
        } else {
            y--;
        }
    }
    reverse(all((ans)));
    cout<<ans;
    return 0;
}

/*
2
4
0 1 0 1
5
0 0 1 0 0
*/

Measured memory_bytes: 70784
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i) = 0; (i) <(n); (i)++) 
using ll = long long;
int main() {
  int n,k;cin>>k>>n;
  int a[n];
  int m=0;
  rep(i,n){
    cin>>a[i];
  }
  for(int i=0;i<n-1;i++){
    m=max(m,a[i+1]-a[i]);
    //cout<<i<<" "<<a[i+1]-a[i]<<endl;
  }
  m=max(m,k-a[n-1]+a[0]);
  cout<<k-m<<endl;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <random>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

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


























int main(){
    ll x, n;
    cin >> x >> n;
    vector<bool> f(105);
    REP(i, n){
        ll p;
        cin >> p;
        f[p] = true;
    }
    ll ans = -1;
    for(ll i = 0; i < 105; i++){
        if(!f[i] && abs(x - ans) > abs(x - i)) ans = i;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3608
#include <stdio.h>
#include <string.h>
#include <iostream>

int main() {
  using namespace std;
  
  ios_base::sync_with_stdio(false);
  
  int ballCount;
  cin >> ballCount;
  
  int *ballno;
  ballno = new int[ballCount];
  for (int i=0, *p = ballno ; i<ballCount ; i++, p++) {
    cin >> *p;
  }
  
  int dicCount = ballCount+1;
  int *dic = new int[dicCount];
  int dicBytes = dicCount<<2;
  
  memset(dic, 0, dicBytes);
  for (int i=0 ; i<ballCount ; i++) {
    dic[ballno[i]]++;
  }

  unsigned long int sum = 0;
  for (int i=0, *p = dic; i<dicCount ; i++, p++) {
    if (*p > 1) {
      sum += ((unsigned long int)*p) * (*p - 1);
    }
  }
  sum >>= 1;
  
  for (int k=0 ; k<ballCount ; k++) {
    int m = dic[ballno[k]];
    m = ((m-1) * -2) >> 1;
    printf("%lld\r\n", sum + m);
  }
  
  delete[] ballno, dic;
}


Measured memory_bytes: 4352
import math
import sys
import itertools
import queue
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

"""
# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]

# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
"""

if __name__ == "__main__":
    A,B= map(int, sys.stdin.readline().split())
    l=[A+B,A-B,A*B]
    print(max(l))


Measured memory_bytes: 5100
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n=I()
  _a=LI()

  sm=0
  b=0
  for x in _a+[0]:
    sm+=abs(b-x)
    b=x

  a=[0]+_a+[0]

  for i in range(n):
    x1=abs(a[i+1]-a[i])
    x2=abs(a[i+2]-a[i+1])
    x3=abs(a[i+2]-a[i])
    y=x1+x2-x3
    print(sm-y)

main()


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

using namespace std;

int main(){
	int m;
	cin>>m;
	if(m%2){
		cout<<"NA"<<endl;
		return 0;
	}
	m/=2;
	int a[50],a1[50],b[50],b1[50];
	for(int i=0;i<m;++i){
		cin>>a[i]>>b[i];
	}
	for(int i=0;i<m;++i){
		cin>>a1[i]>>b1[i];
	}
	int ans1=a[0]+a1[0],ans2=b[0]+b1[0];
	for(int i=1;i<m;++i){
		if(a[i]+a1[i]!=ans1){
			cout<<"NA"<<endl;
			return 0;
		}
		if(b[i]+b1[i]!=ans2){
			cout<<"NA"<<endl;
			return 0;
		}
	}
	printf("%f %f",ans1/2.0,ans2/2.0);
}

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

int main(){
    int i, len;
    char str[2048];
    fgets(str, sizeof(str), stdin);
    len = strlen(str);

    for (i = 0; i < len ; i++) {
        if (str[i] >= 'a' && str[i] <= 'z') {
            str[i] = str[i] - 0x20;
        } else if (str[i] >= 'A' && str[i] <= 'Z') {
            str[i] = str[i] + 0x20;
        } else {
            // 変換不要
        }
    }
    printf("%s", str);
    return 0;
}



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

using ll = long long;
using namespace std;
const int INFint = 1e9+1;
const ll INFll = (ll)1e18+1;
ll MOD=1e9+7;


int main(){
  ll N,C;
  cin>>N>>C;
  vector<ll> x(N),v(N);
  for(int i(0);i<N;i++){
    cin>>x[i]>>v[i];
  }
  ll ans(0);
  ll cnt(0);
  vector<ll> migi(N),hidari(N);
  for(int i(0);i<N;i++){
    cnt += v[i];
    if(i != 0) cnt -= (x[i]-x[i-1]);
    else cnt -= x[i];
    migi[i] = cnt;
  }
  cnt = 0;
  for(int i(N-1);i>=0;i--){
    cnt += v[i];
    if(i != N-1) cnt -= (x[i+1]-x[i]);
    else cnt -= (C-x[i]);
    hidari[i] = cnt;
  }
  for(int i(1);i<N;i++){
    migi[i] = max(migi[i],migi[i-1]);
    hidari[N-i-1] = max(hidari[N-i-1],hidari[N-i]);
  }
  //for(int i(0);i<N;i++){
    //cout << migi[i] << " ";
  //}
  //cout << endl;
  //for(int i(0);i<N;i++){
    //cout << hidari[i] << " ";
  //}
  //cout << endl;
  cnt = 0;
  for(int i(0);i<N;i++){
    cnt += v[i];
    if(i != 0) cnt -= (x[i]-x[i-1]);
    else cnt -= x[i];
    ans = max(ans,cnt);
    if(i != N-1) ans = max(ans,cnt-x[i]+hidari[i+1]);
    else ans = max(ans,cnt-x[i]);
  }
  cnt = 0;
  for(int i(N-1);i>=0;i--){
    cnt += v[i];
    if(i != N-1) cnt -= (x[i+1]-x[i]);
    else cnt -= (C-x[i]);
    ans = max(ans,cnt);
    if(i != 0) ans = max(ans,cnt-(C-x[i])+migi[i-1]);
    else ans = max(ans,cnt-(C-x[i]));
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3328
//agrawal117
//chahatagrawal117
#include<bits/stdc++.h>
#define mod 1000000007
#define endl '\n'
typedef long long int ll ;
using namespace std;
ll n=0;
vector<ll> v;
ll pre[500007];
ll answer_max_operations(ll k)
{
    ll left=0; ll right=n/k;
    while(true)
    {
        ll mid= (left+right)/2;
        int idx=lower_bound(v.begin(),v.end(),mid)-v.begin();
        ll val=v.size()-idx;
        if(idx!=0) val+=pre[idx-1]/mid;
        if(val>=k) left=mid;
        else right=mid;
        if(right-left<=1) break;
    }
    int idx=lower_bound(v.begin(),v.end(),right)-v.begin();
    ll val=v.size()-idx;
    if(idx!=0) val+=pre[idx-1]/right;
    if(val>=k) return right;
    else return left;
}
int main()
{
    cin>>n;
    map<ll,ll> mp;
    ll a; 
    for(int i=1;i<=n;i++){
        cin>>a;
        mp[a]++;
    }
    for(auto it= mp.begin();it!=mp.end();it++){
        v.push_back((ll)it->second);
    }
    sort(v.begin(),v.end());
    pre[0]=v[0];
    for(int i=1;i<v.size();i++) pre[i]=pre[i-1]+v[i];
    // for(int i=0;i<v.size();i++) cout<<pre[i]<<" ";
    // cout<<endl;
    for(int i=1;i<=n;i++){
        cout<<answer_max_operations(i)<<endl;
    }
    
    
}






Measured memory_bytes: 24428
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
const ll mod = 998244353;
const int DEG = 30;
const double pi = acos(-1.0);
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
struct qnode{
    int v, cost;
	int num;
    qnode(int _v = 0, int _cost = 0, int _num = 0): v(_v), cost(_cost), num(_num){}
    bool operator < (const qnode &r)const{
        return cost > r.cost;
    }
};
struct Edge{
    int v, c;
    Edge(int _v = 0, int _c = 0): v(_v), c(_c){}
};
vector<Edge> E[N];
int dist[N][3];
bool vis[N][3];
void Dijkstra(int n, int start){
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < 3; j++)
			dist[i][j] = inf, vis[i][j] = false;
    }
    priority_queue<qnode> q;
    dist[start][0] = 0;
    q.push(qnode(start, 0, 0));
    while(!q.empty()){
        qnode now = q.top();
        q.pop();
        int u = now.v;
		int cnt = now.num;
        if(vis[u][cnt]) continue;
        vis[u][cnt] = 1;
        for(int i = 0; i < E[u].size(); i++){
            int v = E[u][i].v;
            int cost = E[u][i].c;
			int f = (cnt + 1) % 3;
            if(!vis[v][f] && dist[v][f] > dist[u][cnt] + cost){
                dist[v][f] = dist[u][cnt] + cost;
                q.push(qnode(v, dist[v][f], f));
            }
        }  
    }
}
void addedge(int u, int v, int w){
    E[u].push_back({v, w});
    //E[v].push_back({u, w});
}
int main(){
	int n, m;
	while(cin >> n >> m){
		for(int i = 1; i <= n; i++){
			E[i].clear();
		}
		for(int i = 1; i <= m; i++){
			int u, v;
			cin >> u >> v;
			addedge(u, v, 1);
		}
		int st, ed;
		cin >> st >> ed;
		Dijkstra(n, st);
		if(dist[ed][0] == inf){
			cout << -1 << endl;
		}
		else cout << dist[ed][0] / 3 << endl;
	}
	return 0;
}

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

using namespace std;

typedef pair<int, int> P;
typedef pair<int, P> Pi;
typedef long long ll;
struct edge{
  int to; ll dist;
  edge(){}
  edge(int to, ll dist):to(to), dist(dist){}
};
const ll inf = 1LL << 55;

vector< vector<edge> > G(110);
ll minkal[1<<8][110];

int m, n, k, d;
ll cake[8];

ll dijkstra()
{
  fill(minkal[0], minkal[1<<8], inf);
  priority_queue<Pi, vector<Pi>, greater<Pi> > que;
  que.push(Pi(0, P(0, 0)));
  minkal[0][0] = 0;
  while(!que.empty()){
    Pi p = que.top(); que.pop();
    int vd = p.second.second, now = p.second.first; ll kal = p.first;
    if(minkal[vd][now] < kal) continue;    
    for(int i = 0; i < G[now].size(); i++){
      edge e = G[now][i];      
      if(0 < e.to && e.to <= m){
	if(!((vd >> (e.to - 1)) & 1)){
	  if(minkal[vd | (1 << (e.to-1))][e.to] > kal + e.dist*k - cake[e.to-1]){
	    que.push(Pi(kal + e.dist*k - cake[e.to-1], P(e.to, vd | (1<<(e.to-1)))));
	    minkal[vd | (1 << (e.to-1))][e.to] = kal + e.dist*k - cake[e.to-1];
	  }
	}
      } else if(minkal[vd][e.to] > kal + e.dist*k){
	que.push(Pi(kal + e.dist*k, P(e.to, vd)));
	minkal[vd][e.to] = kal + e.dist*k;
      }
    }
  }
  ll ret = inf;
  for(int i = 0; i < 1<<m; i++){
    ret = min(ret, minkal[i][n + m + 1]);
  }
  return ret;
}

int main()
{
  while(cin >> m >> n >> k >> d, m || n || k || d){
    G.clear(); G.resize(m + n + 2);
    memset(cake, 0, sizeof(cake));
    for(int i = 0; i < m; i++) cin >> cake[i];
    for(int i = 0; i < d; i++){
      string f_str, t_str; int from, to; ll dist;
      cin >> f_str >> t_str >> dist;
      if(f_str[0] == 'H') from = 0;
      if(f_str[0] == 'D') from = n + m + 1;
      if(f_str[0] == 'C') from = atoi(f_str.substr(1).c_str());
      if(f_str[0] == 'L') from = atoi(f_str.substr(1).c_str()) + m;
      if(t_str[0] == 'H') to = 0;
      if(t_str[0] == 'D') to = n + m + 1;
      if(t_str[0] == 'C') to = atoi(t_str.substr(1).c_str());
      if(t_str[0] == 'L') to = atoi(t_str.substr(1).c_str()) + m;
      G[from].push_back(edge(to, dist));
      G[to].push_back(edge(from, dist));
    }
    cout << dijkstra() << endl;
  }
  return 0;
}

Measured memory_bytes: 1556
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
#define pb push_back
#define right ri
const int maxn = 3000 + 5;
const int mod = 1e9 + 7;
ll dp[maxn][maxn] , right[maxn] , sum[maxn] , d[maxn];
int main()
{
    ios::sync_with_stdio(false);
    int n, m; cin >> n >> m;
    string a; cin >> a;
    for (int i = 1 ; i <= n + 1; i++) right[i] = i , sum[i] = sum[i - 1] + (a[i - 1] == '1');
    for (int i = 1 ; i <= m ; i++){
        ll l , r; cin >> l >> r;
        right[l] = max (right[l] , r);
    }
    for (int i = 1 ; i <= n ; i++) {
        right[i] = max (right[i - 1] , right[i]);
        d[i] = sum[right[i]] - sum[right[i - 1]];
    }
    dp[1][d[1]] = 1;
    for (int i = 1 ; i <= n ; i++){
        for (int j = 0 ; j <= n ; j++){
            if (dp[i][j]){
                int l = right[i] + 1 , r = right[i + 1];
                if (j) (dp[i+1][j-1+sum[r]-sum[l-1]]+=dp[i][j])%=mod;
                if (right[i] - i + 1 - j) (dp[i+1][j+sum[r]-sum[l-1]]+=dp[i][j])%=mod;
            }
         /*   if (dp[i][j]){
                if (j) dp[i + 1][j + d[i + 1] - 1] = (dp[i + 1][j + d[i + 1]] + dp[i][j]) % mod;
                if (right[i] - i + 1 - j) dp[i + 1][j + d[i + 1]] = (dp[i + 1][j + d[i + 1]] + dp[i][j]) % mod;
            }*/
        }
    }
    cout << dp[n + 1][0] << endl;
    return 0;
}

Measured memory_bytes: 16140
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
  ll a, b, c, k;
  cin >> a >> b >> c >> k;
  ll ans = a + b + c;
  ll Max = max(a, b);
  Max = max(Max, c);
  ans -= Max;
  for (int i = 0; i < k; i++)
    Max *= 2;
  ans += Max;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
const int N = 2e6+10;
const int MOD = 1e9+7;

int F[N], Finv[N], inv[N];//F是阶乘，Finv是逆元的阶乘 
void init(){
    inv[1] = 1;
    for(int i = 2; i < N; i ++){
        inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
    }
    F[0] = Finv[0] = 1;
    for(int i = 1; i < N; i ++){
        F[i] = F[i-1] * 1ll * i % MOD;
        Finv[i] = Finv[i-1] * 1ll * inv[i] % MOD;
    }
}
int comb(int n, int m){//comb(n, m)就是C(n, m) 
    if(m < 0 || m > n) return 0;
    return F[n] * 1ll * Finv[n - m] % MOD * Finv[m] % MOD;
}

int g(int r, int c) {
    int ret = 0;
    for(int i = 1; i <= c; ++ i) {
        ret = (ret + comb(i+r+1, r)) % MOD;
    }
    return ret;
}

int main() {
    init();
    int r1, c1, r2, c2;
    scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
    int ans = (g(r2, c2) - g(r1-1, c2))%MOD +  (g(r1-1, c1-1) - g(r2, c1-1))% MOD;
    printf("%d\n", (ans%MOD+MOD)%MOD);

    int amo; std::cin >> amo;
}


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

int main(){
    int n;
    cin >> n;
    vector<int> h(n);
    for(int i=0;i<n;i++)
        cin >> h.at(i);
    
    vector<int> dif(n);
    dif.at(0)=0;
    for(int i=1;i<n;i++)
        dif.at(i)= h.at(i-1) - h.at(i);

    int res=0;
    int tmp_len = 0;
    for(int i=1;i<n;i++){
        if(dif.at(i)>=0)
            tmp_len++;
        else{
            if(tmp_len > res){
                res=tmp_len;
            }
            tmp_len=0;
        }
    }
    if(tmp_len>res)
        res = tmp_len;
    cout <<res;
}


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

using namespace std;

#define pb push_back
#define fs first
#define sc second
#define sz size
#define forn(i, n) for (ll i = 0; i < (ll) (n); ++i)
#define forni(i, n) for (ll i = 2; i <= (ll) (n); ++i)
#define IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using ll = long long;
const ll inf = 1e9+7; 

const double PI =  3.141592653589793;

int main(){
	IO;
	ll n,a,ans=0;
	cin>>n;
	forn(i,n){
		cin>>a;
		while(a>0 && a%2==0){
			a = a/2;
			ans++;
		}
	}
	cout<<ans<<"\n";
	return 0;
}

// _   .-')                .-. .-')                 .-')                                               
//( '.( OO )_              \  ( OO )               ( OO ).                                             
// ,--.   ,--.).-'),-----. ,--. ,--.  .-'),-----. (_)---\_) ,--. ,--.     .-----.  ,-.-')  .-'),-----. 
// |   `.'   |( OO'  .-.  '|  .'   / ( OO'  .-.  '/    _ |  |  | |  |    '  .--./  |  |OO)( OO'  .-.  '
// |         |/   |  | |  ||      /, /   |  | |  |\  :` `.  |  | | .-')  |  |('-.  |  |  \/   |  | |  |
// |  |'.'|  |\_) |  |\|  ||     ' _)\_) |  |\|  | '..`''.) |  |_|( OO )/_) |OO  ) |  |(_/\_) |  |\|  |
// |  |   |  |  \ |  | |  ||  .   \    \ |  | |  |.-._)   \ |  | | `-' /||  |`-'| ,|  |_.'  \ |  | |  |
// |  |   |  |   `'  '-'  '|  |\   \    `'  '-'  '\       /('  '-'(_.-'(_'  '--'\(_|  |      `'  '-'  '
// """    """     """""""" """  """"      """""""  """""""  """"""""      """"""   """         """""""


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

int main() {
  int32_t n, q;
  std::cin >> n >> q;
  std::string s;
  std::cin >> s;
  std::vector<std::pair<char, char>> td(q);
  for (auto &i : td) {
    std::cin >> i.first >> i.second;
  }

  auto check_l = [&](int32_t i) -> bool {
    for (const auto &j : td) {
      if (s[i] == j.first) {
        if (j.second == 'L') {
          i--;
          if (i < 0) {
            return true;
          }
        } else {
          i++;
          if (s.size() <= i) {
            return false;
          }
        }
      }
    }
    return false;
  };
  auto check_r = [&](int32_t i) -> bool {
    for (const auto &j : td) {
      if (s[i] == j.first) {
        if (j.second == 'L') {
          i--;
          if (i < 0) {
            return false;
          }
        } else {
          i++;
          if (s.size() <= i) {
            return true;
          }
        }
      }
    }
    return false;
  };

  int32_t l_ans;
  if (!check_l(0)) {
    l_ans = -1;
  } else if (check_l(s.size() - 1)) {
    l_ans = s.size() - 1;
  } else {
    int32_t l_min = 0, l_max = s.size() - 1;
    while (l_min != l_max) {
      const auto index = (l_min + l_max) / 2;
      if (index == l_min) {
        break;
      }
      if (check_l(index)) {
        l_min = index;
      } else {
        l_max = index;
      }
    }
    l_ans = l_min;
  }

  int32_t r_ans;
  if (!check_r(s.size() - 1)) {
    r_ans = s.size();
  } else if (check_r(0)) {
    r_ans = 0;
  } else {
    int32_t r_min = 0, r_max = s.size() - 1;
    while (r_min != r_max) {
      const auto index = (r_min + r_max) / 2;
      if (index == r_min) {
        break;
      }
      if (!check_r(index)) {
        r_min = index;
      } else {
        r_max = index;
      }
    }
    r_ans = r_max;
  }

  std::cout << r_ans - l_ans - 1 << std::endl;
  return 0;
}

Measured memory_bytes: 900
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <cmath>
#include <iomanip>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int mod=1e9+7;
const int64_t INF=1e18;

int main() {
  int64_t a,b,c;
  cin>>a>>b>>c;
  if(c-a-b>0&&(c-a-b)*(c-a-b)>4*a*b){cout<<"Yes"<<endl;}
  else{cout<<"No"<<endl;}
  return 0;  
}

Measured memory_bytes: 3548
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  string a, b, c;
  cin >> a >> b >> c;
  int ans = 0;
  for (int i = 0; i < n; i++) {
    string x, y, z;
    x = a.at(i); y = b.at(i); z = c.at(i);
    set<string> s{x, y, z};
    if (s.size() == 3) {
      ans += 2;
    } else if (s.size() == 2) {
      ans += 1;
    }
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 256