akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename Q_temp>
using smaller_queue = priority_queue <Q_temp, vector<Q_temp>, greater<Q_temp> >;

const int INF = (int) 1e9;
const ll LINF = (ll) 4e18;
const ll MOD = (ll) (1e9 + 7);
const double PI = acos(-1.0);
const int limit = 200010;

#define REP(i,m,n) for(ll i = m; i < (ll)(n); ++i)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbg2(x_) for(auto a_ : x_) cerr << a_ << " "; cerr << endl;
#define dbg3(x_ , sx_) rep(i, sx_) cerr << x_[i] << " "; cerr << endl;
vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

//------------------------------------------------------

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    double a, b, c;
    cin >> a >> b >> c;
    double s = (a + b + c) / 2.0;
    cout << (int) (sqrt(s * (s - a) * (s - b) * (s - c))) << endl;
    return 0;
}

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

int main() {
	int n, a[100];
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", a + i);

	std::sort(a, a + n, [](int A, int B) { return A > B; });

	int alice = 0, bob = 0;
	for (int i = 0; i < n; i++) {
		if (i & 1)
			bob += a[i];
		else
			alice += a[i];
	}

	printf("%d\n", alice - bob);
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second

typedef pair<ll,ll> P;
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<int>; using VVI = vector<VI>; using VVVI = vector<VVI>;
const long double inf=1e9+7;
const ll INF=1LL<<61;
const ll mod=1e9+7;

double x[55],y[55];
double dif(int i,int j){
  return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}


int main(){
  int i,j,k;
  int n;
  cin>>n;
  for(i=0;i<n;i++){
    cin>>x[i]>>y[i];
  }
  x[n]=0,y[n]=0;
  double l=500;
  while(l>1e-68){
    double md=-1;
    int ind;
    for(i=0;i<n;i++){
      if(md<dif(i,n)){
        md=dif(i,n);
        ind=i;
      }
    }
    x[n]=x[n]+l*(x[ind]-x[n])/md;
    y[n]=y[n]+l*(y[ind]-y[n])/md;
    l*=0.995;
  }
  double md=-1;
  int ind;
  for(i=0;i<n;i++){
    if(md<dif(i,n)){
        md=dif(i,n);
        ind=i;
    }
  }

  cout<<fixed<<setprecision(15)<<md<<endl;
  
  return 0;
}


Measured memory_bytes: 256
N = int(input())
from collections import Counter
D = [int(i) for i in input().split()]
c = Counter(D)


if D[0] != 0:
  print(0)
  quit()
if c[0] != 1:
  print(0)
  quit()
if len(c.keys()) != max(c.keys())+1:
  print(0)
  quit()

  
res = 1
for i in range(1,1+max(c.keys())):
  res *= c[i-1]**c[i]
  res %= 998244353
print(res)


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

int main() {
  int N;
  cin >> N;
  vector<int64_t> a(N), ac(N);
  for (int i = 0; i < N; i++) {
    cin >> a.at(i);
    ac.at(i) = a.at(i);
  }
  sort(a.begin(), a.end());
  int64_t small = a.at(N/2 - 1), large = a.at(N/2);
  for (int i = 0; i < N; i++) {
    if (ac.at(i) <= small) {
      cout << large << endl;
    }
    else {
      cout << small << endl;
    }
  }
}

Measured memory_bytes: 5376
//高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define INF INT_MAX
#define LLINF LLONG_MAX
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007
#define MODB  998244353 

template <typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& vec) {
    for (T& x: vec) { is >> x; }
    return is;
}

int main() {
	ll ans = 0;
	ll tmp;
	int n; cin >> n;
	REP1(i, n){
		ans += (ll)n / (ll)i;
		if(n % i == 0)  ans --;
	}
	cout << ans << endl;
}

Measured memory_bytes: 3672
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())

using namespace std;
typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = 1001001001;
const long long INFL = (1LL<<60);
const double eps = (1e-9);


int main(int argc, char* argv[])
{
  int n, k;
  cin >> n >> k;

  if (k == 1) {
    cout << 0 << endl;
    return 0;
  }

  int min = 1;
  int max = min + n - k;

  cout << max - min << endl;

  return 0;
}


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

using namespace std;

int main(){
    int A, B;

    cin >> A >> B;

    if(abs(A-B) % 2 == 0){
        cout << max(A, B) - abs(A-B)/2 << endl;
    }else{
        cout << "IMPOSSIBLE" << endl;
    }


    return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (ll i=(ll)from; i<(ll)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }


int main() {
  ll N, K; cin >> N >> K;
  ll A[N]; rep(i,N) cin >> A[i];
  rep(i,N-K) {
    string result = A[i]<A[i+K] ? "Yes" : "No";
    cout << result << endl;
  }
  return 0;
}

Measured memory_bytes: 5184
#include <cmath>
#include <iostream>
using namespace std;

int d;
double pt[10];

bool lagrange(int x, int o){
    int i, j;
    double p;
    double sum=0;
    
    for(i=0; i<d+3; i++){
        if(i != x && i != o){
            p = pt[i];
            for(j=0; j<d+3; j++){
                if((j != i && j != x) && j != o){
                    p *= (x-j)/double(i-j);
                }
            }
            sum+=p;
        }
    }
    if(abs(sum-pt[x])<0.1)
        return true;
    else
        return false;
}

bool outlier(int i){
    for(int j=0; j<d+3; j++){
        if(i==j) continue;
        if(!lagrange(j, i)){
            return false;
        }
    }

    return true;
}

int main() {
    ios_base::sync_with_stdio(0);
    
    int i;
    
    while(true){
        cin >> d;
        
        if(d==0) break;
        
        for(i=0; i<d+3; i++){
            cin >> pt[i];
        }
        
        for(i=0; i<d+3; i++){
            if(outlier(i)){
                cout << i << endl;
                break;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 3148
//arc096_d.cpp
//Mon Jan 27 18:19:19 2020

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

int main(){
	ll n,c;
	cin >> n >> c;

	ll x[n],v[n];
	ll rightscore[n+1];
	rightscore[0] = 0;
	ll totalrightscore[n+1];
	totalrightscore[0] = 0;
	ll maxrightscore[n+1];
	maxrightscore[0] = 0;
	for (int i=0;i<n;i++){
		cin >> x[i] >> v[i];
		totalrightscore[i+1] = totalrightscore[i]+v[i];
		rightscore[i+1] = totalrightscore[i+1]-x[i];
		maxrightscore[i+1] = max(maxrightscore[i],rightscore[i+1]);
	}

	ll leftscore[n+1];
	leftscore[n] = 0;
	ll totalleftscore[n+1];
	totalleftscore[n] = 0;
	ll maxleftscore[n+1];
	maxleftscore[n] = 0;
	for (int i=n-1;i>=0;i--){
		totalleftscore[i] = totalleftscore[i+1]+v[i];
		leftscore[i] = totalleftscore[i]-(c-x[i]);
		maxleftscore[i] = max(maxleftscore[i+1],leftscore[i]);
	}

	ll ans = 0;
	ll revtotal[n+1];
	revtotal[n] = 0;
	for (int i=n-1;i>=0;i--){
		revtotal[i] = revtotal[i+1]+v[i];
		ll temp = max(revtotal[i]-(c-x[i]),
					  maxrightscore[i]+revtotal[i]-(c-x[i])*2);
		ans = max(ans,temp);
	}

	ll fortotal[n+1];
	fortotal[0] = 0;
	for (int i=0;i<n;i++){
		fortotal[i+1] = fortotal[i]+v[i];
		ll temp = max(fortotal[i+1]-x[i],
					  fortotal[i+1]-x[i]*2+maxleftscore[i+1]);
		ans = max(ans,temp);
	}

//	revtotal[0] = revtotal[1]+v[0];
//	ll temp = revtotal[0]-(c-x[0]);
//	ans = max(ans,temp);

	cout << ans << endl;
//	printf("%.4f\n",ans);
}

Measured memory_bytes: 8064
char s[15];
a=1000,n,i,j;
main(){
	gets(s);
	for(;i<strlen(s)-2;i++){
		for(j=n=0;j<3;j++)n=n*10+s[i+j]-48;
		a=fmin(a,fabs(n-753));
	}
	printf("%d",a);
}


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

int main() {
  int n;
  cin >> n;
  vector<int> d(1e5+1);
  rep(i,n) {
    int x;
    cin >> x;
    d[x]++;
  }
  int ans = 0;
  int sum = 0;
  for (int i = 1; i <= 1e5; i++) {
    sum += d[i];
    if (sum == n-sum) ans++;
  }
  cout << ans << endl;
  return 0;
}


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

int main() {
  int n;
  cin >> n;
  char s[n];
  bool w = 0, p = 0, g = 0, y = 0;
  for(int i = 0; i < n; i++) {
    cin >> s[i];
    if(s[i] == 'W') w = 1;
    if(s[i] == 'P') p = 1;
    if(s[i] == 'G') g = 1;
    if(s[i] == 'Y') y = 1;
  }
  if(w && p && g && y) cout << "Four" << endl;
  else cout << "Three" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
  int n,a;
  for(;cin>>n,n;cout<<a<<endl)
    {
      int start[n];
      int end[n];
      char x;
      int h,m,s;
      for(int i=0;i<n;i++)
	{
	  cin>>h>>x>>m>>x>>s;
	  start[i]=(h*60+m)*60+s;
	  cin>>h>>x>>m>>x>>s;
	  end[i]=(h*60+m)*60+s;
	}
      sort(start,start+n);
      sort(end,end+n);
      a=0;
      int count=0;
      for(int s=0,e=0;s<n||e<n;a=max(count,a))
	  if(s>=n)
	    count--,e++;
	  else if(e>=n)
	    count++,s++;
	  else if(start[s]<end[e])
	    count++,s++;
	  else
	    count--,e++;
    }
}

Measured memory_bytes: 1256
#include<iostream>
#include<iomanip>
using namespace std;
int main(){
double N;
cin>>N;
int j=0;
for(int i=1;i<=N;i++)
{
    if(i%2==1){
j++;
    }
}
cout<<fixed<<setprecision(9)<<j/N;

return 0 ;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
//pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int MOD = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n; cin >> n;
    ll best = LLONG_MAX;
    for(ll i = 1; i <= sqrt(n); i++) if(!(n % i)) best = min(best, i + (n / i) - 2);
    cout << best;

    return 0;
}


Measured memory_bytes: 256
//=====================================================
// 
// (setq backup-inhibited t)
// (setq auto-save-default nil)
// 
// (column-number-mode t)
// (setq-default tab-width 2 indent-tabs-mode nil)
// 
// (global-set-key "\C-h" 'delete-backward-char)
// 
// (setq indent-line-function 'indent-relative-maybe)
// (global-set-key "\C-m" 'newline-and-indent)
// 
//=====================================================

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>

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

using namespace std;

int main() {
  while(1){
    string s;
    string t;
    cin >> s;
    cin >> t;
    vector<vector<int>> dp(4000, vector<int>(4000));
    if(!cin) break;
    set<string> st;
    int ml = 0;
    for (int i = 0; i < s.size(); ++i) {
      for (int j = 0; j < t.size(); ++j) {
        if (i > 0 && j > 0 && s[i] == t[j])
          dp[i][j] = dp[i-1][j-1] + 1;
        else if(s[i] == t[j])
          dp[i][j] = 1;
        else
          dp[i][j] = 0;
        ml = max(ml, dp[i][j]);
      }
    }
    cout << ml << endl;
  }
  return 0;
}

Measured memory_bytes: 63828
#include<bits/stdc++.h>
using namespace std;
 
bool has_odd_digits(int n){
	int num_digits = 0;
	while(n){
		num_digits++;
		n/=10;
	}
	return num_digits%2 != 0;
}

int main(){
  	int N;
  	cin >> N;
  	int num=0;
  	for(int i=1;i<=N;i++)
  		if(has_odd_digits(i))
  			num++;
  	cout << num;
  	return 0;
}

Measured memory_bytes: 256
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
int a[200100];lint s[200100];int n;
lint inf=123456789012345678LL;
//vector<lint> v;
lint cal(int x,int y,int z){
	if(x<=0 || x>=y || y>=z || z>=n) return inf;
	vector<lint> v;v.pb(s[x]-s[0]);v.pb(s[y]-s[x]);v.pb(s[z]-s[y]);v.pb(s[n]-s[z]);
	sort(All(v));
	return v[3]-v[0];
}
int main()
{
	cin>>n;
	rep(i,n) cin>>a[i];
	s[0]=0;rep(i,n) s[i+1]=s[i]+a[i];
	//vector<lint> v;REP()
	lint out=inf;
	REP(i,2,n-1){
		int x=upper_bound(s,s+n+1,s[i]/2)-s,y=upper_bound(s,s+n+1,s[i]+(s[n]-s[i])/2)-s;
		rep(j,2) rep(k,2) out=min(out,cal(x-j,i,y-k));
	}
	cout<<out<<endl;
}


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

#define dbg(x) cerr << #x"=" << x << endl;
typedef long long LL;
const LL MOD = 1e9+7;

LL powN(LL base, int n){
    LL res = 1LL;
    while(n){
        if(n&1) res = res * base % MOD;
        base = base * base % MOD;
        n >>= 1;
    }
    return res;
}

int main() {
    //freopen("in.txt", "r", stdin);
    string s;
    cin >> s;
    int n = s.size();
    int cnt = 0;
    LL ans = 0;
    for(int i = 0; i < n; ++i){
        if(s[i] == '1'){
            ans = (ans + powN(3, n-1-i) * powN(2, cnt) % MOD) % MOD;
            ++cnt;
        }
    }
    ans = (ans + powN(2, cnt)) % MOD;
    cout << ans << endl;
    return 0;
}

/*
a+b = a^b - 2*(a&b)

a+b = a^b

如果L的当前位置是1:
a b
0 1 = 1
1 0 = 1
0 0 = 0

如果L的当前位置是0:
a b
0 0 = 0

首先确定每一位只能有三种组合(0, 0) (0, 1) (1, 0)
从左到有右。由高位到低位
枚举到第i位.
如果第i为是1.
那么后面的n-i个位置.每个位置都可以取三种组合.
都可以保证构造出来的a和b后面的位置和和不超过
第i位L的1.然后把这一位搞成0.这样就保证了a+b < L
所以方案数字是2^cnt + 3^(n-i)
然后就是a+b = L的.那么对于L是0的位置.
确定了a当前位置是0.b当前位置也是0.
是1的位置.a和b可以取(0, 1)或者(1, 0).这样保证了那一位
是1.所以答案最后加上2^cnt.此时的cnt表示总的1的个数
前面是1的位置除去i有cnt个.

*/


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

double n;
double now = 100.0;

int main()
{
	cin >> n;
	long long i;
	for (i = 1; ; i++)
	{
		now *= 1.01;
		now = floor(now);
		if (now >= n) break;
	}
	cout << i;
	return 0;
}

Measured memory_bytes: 3696
import java.util.Scanner;
import java.util.TreeSet;

public class Main {

	public static void main(String args[])
	{
		Scanner scan=new Scanner(System.in);
//		int n=scan.nextInt();
		int a=scan.nextInt();
		int b=scan.nextInt();
		int q=scan.nextInt();
		TreeSet<Long> shrines=new TreeSet<Long>();
		TreeSet<Long> temples=new TreeSet<Long>();
		for(int i=0;i<a;i++)
		{
			shrines.add(scan.nextLong());
		}
		for(int i=0;i<b;i++)
		{
			temples.add(scan.nextLong());
		}
		for(int i=0;i<q;i++)
		{
			long x=scan.nextLong();
			Long LS=shrines.floor(x);
			long distLS=(LS==null)?(1L<<60):x-LS;
			Long RS=shrines.ceiling(x);
			long distRS=(RS==null)?(1L<<60):RS-x;
			Long LT=temples.floor(x);
			Long RT=temples.ceiling(x);
			long distlt=(LT==null)?(1l<<60):x-LT;
			long distrt=(RT==null)?(1L<<60):RT-x;
//			System.out.println();
//			System.out.println(distRS+" "+distLS+" "+distlt+" "+distrt);
			
			long A=(Math.max(distrt, distRS));
			long B=2*distRS+distlt;
			long D=2*distrt+distLS;
			long E=2*distLS+distrt;
			
			long F=2*distlt+distRS;
			long c=Math.max(distLS,distlt);
			long gg=Math.min(Math.min(A, B),c);
			
			long ans=Math.min(gg, D);
			
			ans=Math.min(ans, E);
			ans=Math.min(ans, F);
//			long ans=Math.min(gg, D);
			System.out.println(ans);
		}
		
				
	}
}


Measured memory_bytes: 109444
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
typedef double db;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pa;
typedef unsigned int uint;
typedef unsigned long long ull;
#define w1 first
#define ls (x<<1)
#define w2 second
#define ins insert
#define rs (x<<1|1) 
#define mp make_pair
#define pb push_back
#define mid ((l+r)>>1)
#define sqr(x) ((x)*(x))
#define cle(x) ((x).clear())
#define lowbit(x) ((x)&(-x))
#define SZ(x) (int((x).size()))
#define ms(x,y) memset(x,y,sizeof (x))
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define rep2(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define per(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define Rep(p,x) for(int (p)=head[(x)];(p);(p)=nxt[(p)]) 
#define Rep2(p,x) for(int (p)=cur[(x)];(p);(p)=nxt[(p)])
#define debegin printf("debug\nbegin\n")
#define deend printf("debug\nend\n")
#define isfind printf("find\n")
template<class T>inline void rread(T&num){
	num=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
	num*=f;
}
inline int getgcd(int x,int y){if(!x)return y;return getgcd(y%x,x);}
inline int power(int x,int k,int p){int res=1;for(;k;k>>=1,x=(ll)x*x%p)if(k&1)res=(ll)res*x%p;return res;}
const double pi=acos(-1);
inline void judge(){
	freopen("input.txt","r",stdin);
} 
//********************************head*************************************
const int maxn=8e2+5,inf=1e9;
int n,m,k;
int dis[maxn][maxn],q[2][maxn*maxn];
char str[maxn][maxn];
inline void bfs(int sx,int sy){
	rep(i,1,n)rep(j,1,m)dis[i][j]=inf;
	dis[sx][sy]=0;
	int h=0,t=1;
	q[0][0]=sx;q[1][0]=sy;
	while(h!=t){
		int x=q[0][h],y=q[1][h];h++;
		if(x-1>=1&&dis[x-1][y]==inf&&str[x-1][y]=='.')dis[x-1][y]=dis[x][y]+1,q[0][t]=x-1,q[1][t]=y,t++;
		if(y-1>=1&&dis[x][y-1]==inf&&str[x][y-1]=='.')dis[x][y-1]=dis[x][y]+1,q[0][t]=x,q[1][t]=y-1,t++;
		if(x+1<=n&&dis[x+1][y]==inf&&str[x+1][y]=='.')dis[x+1][y]=dis[x][y]+1,q[0][t]=x+1,q[1][t]=y,t++;
		if(y+1<=m&&dis[x][y+1]==inf&&str[x][y+1]=='.')dis[x][y+1]=dis[x][y]+1,q[0][t]=x,q[1][t]=y+1,t++;
	}
}
int main(){
	rread(n);rread(m);rread(k);
	rep(i,1,n)scanf("%s",str[i]+1);
	rep(i,1,n)rep(j,1,m)if(str[i][j]=='S')bfs(i,j);
	int ans=inf;
	rep(i,1,n)rep(j,1,m)if(dis[i][j]!=inf){
		int now=max(1,(dis[i][j]+k-1)/k);
		now+=(min(min(i-1,j-1),min(n-i,m-j))+k-1)/k;
		ans=min(ans,now);
	}
	printf("%d\n",ans);
	return 0;
}

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

const long long INF = 1000000000;

typedef long long ll;

#define writeln(n) cout<<n<<"\n";

typedef pair<int, int> P;
typedef pair<string, int> Psi;


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

	int n;cin>>n;

	string s ;cin>>s;

	char now =s[0];
	int ct=1;
	for(int i=1; i<n; i++){
		if(now != s[i]){
			now = s[i];
			ct++;
		}
	}

	writeln(ct);

}




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

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define all(x) (x).begin(),(x).end()
#define IN(type,a) type a;cin >> a
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl

using ll = long long;

int main() {
    IN(string, s);
    int n = s.length();
    bool ans = true;
    REP(i, (n-1)/2){
        if (s[i] != s[n-1-i]) {
            ans = false;
            break;
        }
    }
    if (ans) {
       REP(i, (n-1)/4){
           if (s[i] != s[(n-1)/2-1-i]) {
               ans = false;
               break;
           }
       }
    }
    
    Yes(ans);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c[10000]={},ans=0;
    cin>>a>>b;
    for(int i=0;i<a;i++){
        cin>>c[i];
    }
    sort(c,c+a);
    for(int i=0;i<b;i++){
        ans+=c[i];
    }
    cout<<ans<<"\n";
    return(0);
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <map>
#include <algorithm>
#include <queue>
#include <cstdio>

using namespace std;

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

    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define INF 1000000005
#define LINF 1000000000000000005
#define MAXN 100005
#define pi pair<int,int>
#define pl pair<ll,ll>
int main() {
ll x,y;
cin>>x>>y;
if (!(x%y)) {cout<<-1;return 0;}
cout<<x;
}



Measured memory_bytes: 256
from itertools import permutations

n = int(input())
p = tuple(map(int, input().split()))
q = tuple(map(int, input().split()))

r = list(permutations(range(1, n + 1)))

a = r.index(p) + 1
b = r.index(q) + 1

print(abs(a - b))


Measured memory_bytes: 8052
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;

class Solution
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        int[] a = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
        long l = 2, r = 2;

        for (int i = a.Length - 1; i >= 0; i--)
        {
            if (r / a[i] * a[i] < l)
            {
                Console.WriteLine(-1);
                return;
            }
            l = l % a[i] == 0 ? l : (l / a[i] + 1) * a[i];
            r = r / a[i] * a[i] + a[i] - 1;
        }

        Console.WriteLine($"{l} {r}");
    }
}


Measured memory_bytes: 26844
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int x, a, b;
	cin >> x >> a >> b;
	if (a >= b)
	{
		cout << "delicious" << endl;
	}
	else if (b - a <= x)
	{
		cout << "safe" << endl;
	}
	else {
		cout << "dangerous" << endl;
	}
	return 0;
}

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

void fastio() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}

// int lcs(string &a, string &b, int i, int j) {
// 	if (i < 0 || j < 0) return 0;
// 	if (a[i] == b[j]) return 1 + lcs(a, b, i-1, j-1);
// 	return max(lcs(a,b,i-1,j), lcs(a,b,i,j-1));
// }
int main(int argc, char const *argv[])
{
	
	string a, b;
	cin >> a >> b;
	int n = a.size(), m = b.size();
	vector<vector<int> > dp(n, vector<int> (m, 0));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (a[i] == b[j]) {
				dp[i][j] = 1;
				if (i > 0 && j > 0) dp[i][j] += dp[i-1][j-1];
			} else {
				if (i > 0)
					dp[i][j] = max(dp[i][j], dp[i-1][j]);
				if (j > 0)
					dp[i][j] = max(dp[i][j], dp[i][j-1]);
			}
		}
	}
	// for (int i = 0; i < n; ++i) {
	// 	for (int j = 0; j < m; ++j) {
	// 		cout << dp[i][j] << " ";
	// 	}
	// 	cout << endl;
	// }
	// cout << lcs(a, b, (int)a.size() - 1, (int)b.size()-1) << endl;
	int len = dp[n-1][m-1];
	string ans = "";
	int i = n-1, j = m-1;
	while (len && i >= 0 && j >= 0) {
		// go up
		while (i > 0 && dp[i-1][j] == len) i--;
		// go right
		while (j > 0 && dp[i][j-1] == len) j--;
		ans += a[i];
		len--;
		i--;
		j--;
	}
	reverse(ans.begin(), ans.end());
	cout << ans << endl;
	return 0;
}

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

int main(void)
{
    long long N;
    cin >> N;
    vector<long long> A(N);
    for (long long i = 0; i < N; i++)
    {
        cin >> A[i];
    }

    long long ans = 1000;
    long long count = 0;
    long long flg = 0;
    for (long long i = 0; i < N; i++)
    {
        if (A[i] < A[i+1] && flg == 0)
        {
            count = ans / A[i];
            ans = ans - count * A[i];
            flg = 1;
        }
        else if (A[i] > A[i+1] && flg == 1)
        {
            ans = ans + count * A[i];
            count = 0;
            flg = 0;
        }
        else if (i == N -1 && flg == 1)
        {
            ans = ans + count * A[i];
            count = 0;
            flg = 0;
        }
    }
    cout << ans << endl;
}

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

	int main(){
	cout<<fixed<<setprecision(5);
	
	int a,b;
	cin>>a>>b;
	cout<<a/b<<" ";
	cout<<a%b<<" ";
	cout<<(double)a/b<<endl;
	return 0;
}


Measured memory_bytes: 3260
#include <bits/stdc++.h>
#define ALL(A) (A).begin(), (A).end()
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

const ll mod = 1e9 + 7;
const ll INF = -1 * ((1LL << 63) + 1);
const int inf = -1 * ((1 << 31) + 1);

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int N;
    cin >> N;
    vector<ll> A(N);
    rep(i,N)cin >> A[i];
    if(A[0]!=0){
        cout << -1 << endl;
        return 0;
    }
    ll ans = 0;
    for(int i=1;i<N;i++){
        if(A[i]==A[i-1])ans += A[i-1];
        else if(A[i]==A[i-1]+1){
            ans += 1;
        }else if(A[i]>A[i-1]+1){
            cout << -1 << endl;
            return 0;
        }else if(A[i]==1){
            ans++;
        }else{
            ans += A[i];
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

N, M = map(int, read().split())

def make_power(a, L, MOD=MOD):
    B = L.bit_length()
    x = np.empty(1 << B, np.int64)
    x[0] = 1
    for n in range(B):
        x[1 << n:1 << (n + 1)] = x[:1 << n] * a % MOD
        a *= a
        a %= MOD
    x = x[:L]
    x.flags.writeable = False
    return x

pow2 = make_power(2, M + 10)
ipow2 = make_power((1 + MOD) // 2, M + 10)

def update(dp):
    B = dp.copy()
    C = dp * np.arange(M + 1) % MOD * ipow2[:M + 1] % MOD
    dp[1:] = np.cumsum(C[:-1]) % MOD
    dp[1:] *= pow2[:M]
    dp %= MOD
    dp += np.arange(1, M + 2) * B
    dp %= MOD

dp = pow2[:M + 1].copy()
for _ in range(N - 1):
    update(dp)

print(dp[-1])

Measured memory_bytes: 27556
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> a(n,vector<int>(m,0));
    vector<int> b(m,0);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> a[i][j];
        }
    }
    for(int i=0;i<m;i++) cin>>b[i];
    for(int i=0;i<n;i++){
        int sum=0;
        for(int j=0;j<m;j++){
            sum += a[i][j] * b[j];
        }
        cout << sum << endl;
    }
}


Measured memory_bytes: 3176
#include<iostream>
using namespace std;int h,w,m,D[1401][1401]={m=0},f,i=0;main(){cin>>h>>w;for(;i<h*w;i++){cin>>f;m=max(m,D[i/w+1][i%w+1]=(min(D[i/w][i%w],min(D[i/w+1][i%w],D[i/w][i%w+1]))+1)*(!f));}cout<<m*m<<endl;}



Measured memory_bytes: 10776
# 国家予算

def main():
    N = int(input())
    for _ in range(N):
        n1 = input().strip()
        n2 = input().strip()

        #print(f"n1: {n1}\nn2: {n2}")
        if len(n1) > 80 or len(n2) > 80:
            print("overflow")
            continue

        print(add(n1, n2))
    return

def add(n1, n2):
    """n1, n2: str"""
    kotae = ""
    n1 = n1[::-1] # reversed
    n2 = n2[::-1]

    if len(n1) < len(n2): # 長い方がn1
        n1, n2 = n2, n1
    shorter = min(len(n1), len(n2))
    longer = max(len(n1), len(n2))

    idx, kuriagari = 0, 0
    while idx < longer:
        if idx >= shorter:
            tmp = int(n1[idx]) + kuriagari
            #print(f"idx: {idx}, tmp: {tmp}")
            kuriagari = 1 if tmp >= 10 else 0
            kotae += str(tmp)[-1]
            idx += 1

        while idx < shorter:
            tmp = int(n1[idx]) + int(n2[idx]) + kuriagari
            #print(f"idx: {idx}, tmp: {tmp}")
            kuriagari = 1 if tmp >= 10 else 0

            kotae += str(tmp)[-1]
            idx += 1

    if kuriagari:
        kotae += "1"

    if len(kotae) > 80:
        return "overflow"
    else:
        return kotae[::-1]

if __name__ == "__main__":
    main()


Measured memory_bytes: 5604
from sys import stderr
from functools import reduce
from operator import add
def f(): return [int(i) for i in input().split()]
def yes(n): print("Yes" if n else "No")
def debug(*x, sep=" ", end="\n"):
    for item in x:
        stderr.write(str(item))
        stderr.write(sep)
    stderr.write(end)

h, w = f()
target =  ['.'*(w+2)]
for _ in range(h):
    a = '.'
    a += input()
    a += '.'
    target.append(a)
target.append('.'*(w+2))
flag = True

for i in range(1, h+1):
    for j in range(1, w+1):
        if target[i][j] == '#':
            if '#' not in [target[i-1][j], target[i+1][j], target[i][j-1], target[i][j+1]]:
                flag = False
yes(flag)

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


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n; // avail
	vector<int> reqd =  {0,2,5,5,4,5,6,3,7,6};
	vector<int> dp(n+1,-1);
	vector<int> par(n+1,-1);
	int m;
	cin>>m;
	vector<int> avail(m);
	for(int i=0; i<m; ++i){
		cin>>avail[i];
	}
	dp[0] = 0;
	for(int i=1; i<=n; ++i){
		for(auto j : avail){
			if( i >= reqd[j] ){
				if( dp[i] < dp[i-reqd[j]] + 1 ){
					dp[i] = dp[i-reqd[j]] + 1;
					par[i] = j;
				}else if( dp[i] == dp[i-reqd[j]] + 1 ){
					if( j > par[i] ){
						par[i] = j;
					}
				}
			}
		}
	}
	string ans = "";
	int st = par[n];
	int go = n;
	while(st != -1 ){
		ans += to_string(st);
		go -= reqd[st];
		st = par[go];
	}
	sort(ans.rbegin(),ans.rend());
	cout<<ans<<'\n';


}


Measured memory_bytes: 384
x,y,a,b,c = gets.chomp.split(" ").map(&:to_i)
p_arr = gets.chomp.split(" ").map(&:to_i).sort_by{|n| -n}
q_arr = gets.chomp.split(" ").map(&:to_i).sort_by{|n| -n}
r_arr = gets.chomp.split(" ").map(&:to_i)

x_arr = p_arr[0..x-1]
y_arr = q_arr[0..y-1]

puts (x_arr + y_arr + r_arr).sort_by{|n| -n}[0..x+y-1].sum


Measured memory_bytes: 38720
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define puts(i) cout<<i<<endl
#define pi 3.14159265358979
using ll = long long;
using P = pair<int,int>;

ll divisor=1e9+7;
int main(){
	int n,a[3];
	cin>>n>>a[0]>>a[1]>>a[2];
	string s[n];
	rep(i,n){
		cin>>s[i];
	}
	if(a[0]+a[1]+a[2]==0){
		puts("No");
		return 0;
	}
	char ans[n];
	if(a[0]+a[1]+a[2]==1){
		rep(i,n){
			int fi=s[i][0]-'A',se=s[i][1]-'A';
			if(a[fi]==0&&a[se]==0){
				puts("No");
				return 0;
			}
			if(a[fi]>a[se]){
				a[fi]--;
				a[se]++;
				ans[i]= s[i][1];
			}else if(a[fi]<a[se]){
				a[fi]++;
				a[se]--;
				ans[i]= s[i][0];
			}
		}
	}else{
		if(a[s[0][0]-'A']==0&&a[s[0][1]-'A']==0){
			puts("No");
			return 0;
		}
		rep(i,n){
			int fi=s[i][0]-'A',se=s[i][1]-'A';
			if(a[fi]==0&&a[se]==0){
				puts("No");
				return 0;
			}
			if(a[fi]>a[se]){
				a[fi]--;
				a[se]++;
				ans[i]= s[i][1];
			}else if(a[fi]<a[se]||(a[fi]>1&&a[se]>1)||i+1==n||(i+1<n&&s[i]==s[i+1])){
				a[fi]++;
				a[se]--;
				ans[i]=s[i][0];
			}else{
					int fi_=s[i+1][0]-'A',se_=s[i+1][1]-'A';
					int b[3]={};
					b[fi]++;b[se]++;b[fi_]++;b[se_]++;
					rep(j,3){
						if(b[j]==2){
							a[j]++;
							if(j==fi){
								a[se]--;
								ans[i]=s[i][0];
							}else{
								a[fi]--;
								ans[i]=s[i][1];
							}
						}
					}
            }
		}
	}
	puts("Yes");
	rep(i,n){
		puts(ans[i]);
	}
}

Measured memory_bytes: 6828
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;

int const maxn = 100 + 10;
inline int lc(int x)  {return x << 1;}
inline int rc(int x)  {return x << 1 | 1;}

int a[maxn], b[maxn], c[maxn];

int main(void) {
    FAST_IO;
    
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) 
        cin >> a[i];
    for (int i = 0; i < n; i++) 
        cin >> b[i];
    for (int i = 1; i < n; i++) {
        cin >> c[i];
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += b[a[i] - 1];
        if (i == 0) continue;
        if (a[i] == a[i - 1] + 1) ans += c[a[i] - 1];
    }
    cout << ans <<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>

#define rep(i,n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

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

  cout << N * N - A << endl;

  return 0;
}


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


using namespace std;




int main(int argc, const char * argv[]) {
    
    int a,b,c;
    cin>>a>>b>>c;
    
    cout<<std::min({a,b,c})<<" "<<max({a,b,c})<<endl;
    
    
    
    

    
    
    return 0;
}




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

int main()
{
	int a[3],c=0;
	for (int i = 0; i < 3; i++) {
		cin>> a[i];
	}
	for (int i = 1; i < 3; i++) {
		for (int j = i; j < 3; j++) {
			if (a[i - 1] == a[j]) {
				c++;
			}
		}
	}

		if (c == 1) {
			cout << "Yes" << endl;
		}
		else {
			cout << "No" << endl;
		}

	cin.get();
    cin.get();
    return 0;
}

Measured memory_bytes: 256
[h,w] = [int(i) for i in input().split()]
mod = 10**9+7
a = [["#"]*(w+2)]
for i in range(h):
    tmp = ["#"]
    s = input()
    for j in range(w):
        tmp.append(s[j])
    tmp.append("#")
    a.append(tmp)
a.append(["#"]*(w+2))

dp = [[0]* (w+2) for i in range(h+2)]
addi = 1
for i in range(1,h+1):
    if a[i][1] == "#":
        addi = 0
    dp[i][1] += addi
addi = 1
for i in range(2,w+1):
    if a[1][i] == "#":
        addi = 0
    dp[1][i] += addi


for i in range(2,h+1):
    for j in range(2,w+1):
        if a[i][j] != "#":
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
            dp[i][j] %= mod
print(dp[h][w])
#for i in range(h+2):
#    print(dp[i])


Measured memory_bytes: 91228
# ABC135c
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = 0

for i in range(n):
    if (a[i] < b[i]):
        taosu = min(a[i + 1], b[i] - a[i])
        a[i + 1] -= taosu
        c += taosu+a[i]
        a[i] = 0
    else:
        c += b[i]
        a[i] -= b[i]
print(c)

Measured memory_bytes: 19376
object Main {
  def main(args:Array[String]) {
    val read = readLine()
    val H = read.split(' ')(0).toInt
    val N = read.split(' ')(1).toInt
    val A = readLine.split(' ').map(_.toInt)

    if(H <= A.sum) println("Yes")
    else println("No")

  }
}


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

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
// pll pp; -> (pp.first,pp.second)
// vector<vl> pp(n,vl(2)); sort(pp.begin(),pp.end(),[](vl a,vl b){return a[0]<b[0];});

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define RREP(i,n) for(ll (i)=(n)-1;(i)>=0;(i)--)
#define DEBUG(x) cout << #x << ": " << x << endl
#define CHMAX(a,b) a=max((a),(b))
#define CHMIN(a,b) a=min((a),(b))
/*}}}*/
int main() {
  ll n;
  cin >> n;
  string s;
  cin >> s;
  ll cnt = 0;
  REP(i,n){
    char c = s[i];
    if(c=='R') cnt++;
    else cnt--;
  }
  if(cnt>0) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;(i)--)
#define rrep1(i,n) for(int i=((int)(n));i>0;(i)--)
#define sz(c) ((int)(c).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> P;
typedef pair<int, pair<int, int> > PP;
const int MAX=1e5+10;

int N;
ll A[MAX], B[MAX];
void input(){
  cin>>N;
  rep(i,N+1)cin>>A[i];
  rep(i,N)cin>>B[i];
}

ll ans;
void solve(){
  rep(i,N){
    if(B[i]<=A[i])ans+=B[i];
    else if(B[i]<=A[i]+A[i+1]){
      ans+=B[i];
      A[i+1]=A[i]+A[i+1]-B[i];
    }
    else{
      ans+=A[i]+A[i+1];
      A[i+1]=0;
    }
  }
  cout<<ans<<endl;
}

void output(){
  
}

int main(){
  input();
  solve();
  output();
}

Measured memory_bytes: 1792
//g

#include <stdio.h>
#include <string.h>


int main ()
{
	int a, b, ctr=0;
	char kode[100];
	
	scanf ("%d %d",&a,&b);
	scanf ("%s",kode);
	
		
	int i = 0;
	while (i<=strlen(kode))
	{
		i++;
		if (kode[i] == '-')
		{
		ctr++;
		}
	}
	
	if (ctr>1) 
	{
		printf ("No");
		return 0;
	}
	
	if (kode [a] != '-')
	{
			printf ("No");
			return 0;
	}
	
	
	printf ("Yes");
	
return 0;	
}

Measured memory_bytes: 1656
import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.numeric, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }


enum INF = 10L^^18;

void bChmin(T)(T[] bit, int pos, T val) {
  for (int x = pos; x < bit.length; x |= x + 1) {
    chmin(bit[x], val);
  }
}

// min of [0, pos)
T bMin(T)(T[] bit, int pos) {
  T mn = INF;
  for (int x = pos - 1; x >= 0; x = (x & (x + 1)) - 1) {
    chmin(mn, bit[x]);
  }
  return mn;
}

alias Interval = Tuple!(int, "a", int, "b", long, "c");

void main() {
  try {
    for (; ; ) {
      const N = readInt();
      const M = readInt();
      auto P = new Interval[M];
      foreach (i; 0 .. M) {
        P[i].a = readInt();
        P[i].b = readInt();
        P[i].c = readLong();
      }
      
      P.sort!((p, q) => (p.b < q.b));
      debug {
        writeln("P = ", P);
      }
      
      auto bit = new long[N + 1];
      bit[] = INF;
      
      bit.bChmin(N - 1, 0);
      foreach (i; 0 .. M) {
        // j s.t. A[i] <= B[j]
        const res = bit.bMin(N - P[i].a + 1);
        debug {
          writeln(i, ": ", res + P[i].c);
        }
        bit.bChmin(N - P[i].b, res + P[i].c);
      }
      // j s.t. N <= B[j]
      const ans = bit.bMin(N - N + 1);
      writeln((ans >= INF) ? -1 : ans);
    }
  } catch (EOFException e) {
  }
}


Measured memory_bytes: 5116
#include <iostream>
#include <numeric>
#include <bits/stdc++.h>
using namespace std;
// long long -> lint
using lint = long long;
// fast cin and cout from hitonanode-san's code
// w/o 71 ms -> w/ 18 ms (tested on ABC148-D with C++14(GCC 5.4.1))
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;


int main(){
    // input
    double R;
    cin >> R;

    cout << 2.0*R*M_PI << endl;
} 

Measured memory_bytes: 3780
#include<stdio.h>
int main(){
  long long int N,i,ans=1000000000;
  scanf("%lld",&N);
  int A[N],c;
  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
    c=0;
    while(1){
      if(A[i]%2==1){
        break;
      }
      A[i]/=2;
      c++;
    }
    if(ans>c){
      ans=c;
    }
  }
  printf("%lld\n",ans);
  return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
typedef long double lld;
typedef pair<lld,int> P;
#define EPS 1e-9
#define sq(x) ((x)*(x))

int n;
lld xt,yt,xs,ys;
lld x[1111];
lld y[1111];
lld r[1111];

lld d[1111];
priority_queue<P,vector<P>,greater<P> > que;

int main(void){
  scanf("%Lf%Lf%Lf%Lf",&xt,&yt,&xs,&ys);
  scanf("%d",&n);
  for(int i = 1; i <= n; i++){
    scanf("%Lf%Lf%Lf",x+i,y+i,r+i);
  }
  x[0] = xt;
  y[0] = yt;
  x[n+1] = xs;
  y[n+1] = ys;
  r[0] = r[n+1] = 0;
  n += 2;

  for(int i = 0; i < 1111; i++){
    d[i] = 1e11;
  }
  d[0] = 0.0;
  que.push(make_pair(0.0,0));
  while(!que.empty()){
    lld c = que.top().first;
    int v = que.top().second;
    que.pop();
    if(d[v]+EPS < c) continue;
    for(int i = 0; i < n; i++){
      if(i == v) continue;
      lld dd = max(0.0L,sqrt(sq(x[v]-x[i])+sq(y[v]-y[i]))-r[v]-r[i]);
      if(d[i] > d[v] + dd){
	d[i] = d[v] + dd;
	que.push(make_pair(d[i],i));
      }
    }
  }
  printf("%.10Lf\n",d[n-1]);
}


Measured memory_bytes: 8684
s = input()
s_length = len(s)

for i in range(s_length):
    if i % 2 == 0:
        if s[i] ==  "L":
            print("No")
            exit()
        else:
            continue
    else:
        if s[i] == "R":
            print("No")
            exit()
        else:
            continue
print("Yes")

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

int main (){
    long N, A, B;
    cin >> N >> A >> B;
    long l;

    if((B-A)%2 == 0){
        cout << (B - A) / 2;
    }else{
        l = min(2 * N - A - B, A + B - 2);
        cout << (l + 1) / 2;
    }
    
    
}

Measured memory_bytes: 256
a,b,c,d = map(int,input().split())
mod = 998244353
dp = [[0]*(d-b+1) for i in range(c-a+1)]
if a == c and b == d:
    print(1)
elif a == c:
    print(pow(a,d-b,mod))
elif b == d:
    print(pow(b,c-a,mod))
else:
    for i in range(c-a):
        p = 0
        for j in range(d-b+1):
            if i == j == 0:
                dp[i][j] = 1
            dp[i+1][j] = (p + dp[i][j]*(b+j))%mod

            p += dp[i][j]
            p %= mod
            p *= a+i
            p %= mod

    ans = 0
    for d in dp[-1]:
        ans *= c
        ans %= mod
        ans += d
        ans %= mod
    print(ans)

Measured memory_bytes: 133604
#include<iostream>
using namespace std;
int main()
{
    int a,b;
    bool c=0;
    cin>>a>>b;
    if(a<=0&&b>=0) cout<<"Zero"<<endl;
    else
    {
    for(int i=a;i<=b;i++)
    {
        if(i<0) c=1-c;
    }
    if(c==0) cout<<"Positive"<<endl;
    else cout<<"Negative"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
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; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;
int main()
{
    int K;
    string S;
    cin >> K >> S;
    int cnt = 0;
    rep(i, S.size()) {
        if (cnt >= K) {
            cout << "...";
            break;
        }
        cnt++;
        cout << S[i];
    }

    cout << endl;
    return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

template<class T> inline void read(T &x){
	char ch=getchar();int f=0;x=0;
	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	if(f)x=-x;
}

const int N=300005;
int a[N],t[N],l[N],r[N];
int n,L,m;
ll ans;

int main(){
	read(n),read(L),m=L<<1;
	rep(i,1,n)read(a[i]);
	rep(i,1,n){
		read(t[i]);
		if(t[i]%m==0)ans+=t[i]/m;
		else{
			ans+=t[i]/m+1,t[i]%=m;
			l[i]=(t[i]<=2*a[i]);
			r[i]=(t[i]<=m-2*a[i]);
		}
	}
	for(int i=1,x=0,y=0;i<n;i++)
		if(x&&r[i]){
			if(l[i])y++;
			ans--,x--;
		}
		else if(!l[i]&&r[i]){
			if(y)y--,x++;
		}
		else if(l[i])x++;
	ans+=!r[n];
	cout<<ans*m<<endl;
	return 0;
}

Measured memory_bytes: 4992
#include<stdio.h>
int main(){
  int x,t=0;
  char s[100];
  int S[100];
  while(scanf("%s",s)!=EOF){
    if(s[0]=='+'){
      S[t-2]=S[t-2]+S[t-1];
      t-=1;  
    }else if(s[0]=='-'){
      S[t-2]=S[t-2]-S[t-1];
      t-=1;
    }else if(s[0]=='*'){
      S[t-2]=S[t-2]*S[t-1];
      t-=1; 
    }
    else{
      x=atoi(s);
      S[t]=x;
      t++;
    }
  }
  printf("%d\n",S[t-1]);
  return 0;
}

Measured memory_bytes: 548
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
int main()
{
    std::ios::sync_with_stdio(false);
    int n;
    int a[N];
    cin>>n;
    int sum=0;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    int s;
    if(sum%n==0)
    {
        s=sum/n;
        int ans=0;
        for(int i=1; i<=n; i++)
        {
            ans+=(s-a[i])*(s-a[i]);
        }
        cout<<ans<<endl;
    }
    else
    {
        int s1=sum/n;
        int ans1=0;
        for(int i=1; i<=n; i++)
        {
            ans1+=(s1-a[i])*(s1-a[i]);
        }
        int s2=s1+1;
        int ans2=0;
        for(int i=1; i<=n; i++)
        {
            ans2+=(s2-a[i])*(s2-a[i]);
        }
        cout<<min(ans1,ans2)<<endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits//stdc++.h>
using namespace std;
int in(void){int x;cin>>x;return x;}
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define ll long long int
long long int dx[4]={1,0,-1,0};
long long int dy[4]={0,1,0,-1};
int main() {
	int n,w,h;
	cin>>n>>h>>w;
	int ans=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(j+w-1<n&&i+h-1<n){
				ans++;
			}
		}
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n); for(int i = 0;i < (int)(n);i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
int main(){
    int l,r;
    cin >> l >> r;
    int d;
    cin >> d;
    cout << r/d - (l-1)/d << endl;
    return 0;
}

Measured memory_bytes: 3616