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

int main()
{
  int k;
  string s;
  
  cin >> k;
  cin >> s;
  
  size_t size = s.size();
  
  if(size <= k){
    cout << s;
  }else{
    cout << s.substr(0,k) << "...";
  }
  
  return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <math.h>
using namespace std;

#define ll long long
//#define int long long
const int MOD = 1000000007;
const int INF = 1010000000;
const double EPS = 1e-10;

#define dump(x)  cerr << #x << " = " << (x) << endl; 
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; 


typedef pair<int, int> P;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

signed main(){

	int A[3];
	cin >> A[0] >> A[1] >> A[2];

	sort(A, A + 3);

	if (A[0] == 5 && A[1] == 5 && A[2] == 7) cout << "YES" << endl;
	else cout << "NO" << endl;

	return 0;
}


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

int main(){
    int n, k;
    int res = 1;
    cin >> n >> k;

    while(n > 0){
        if(res < k){
            res += res;
        }else{
            res += k;
        }
        n--;
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>
#include<stack>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

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

#define PUTLINE cout<<__LINE__<<endl;

int cost[70][40][2];
string s[70][40];

class State{
public:
	int w,h,foot,cost;
	bool operator>(State state)const{return cost>state.cost;}
};

int main() {
	int w,h;
	while(true){
		cin>>w>>h;
		if(w==0&&h==0)break;
		rep(i,h)rep(j,w){
			cin>>s[i][j];
			cost[i][j][0]=cost[i][j][1]=100100100;
		}
		priority_queue<State,vector<State>,greater<State> > que;
		rep(j,w){
			if(s[h-1][j]=="S"){
				State buf;
				buf.h=h-1;
				buf.w=j;
				buf.cost=0;
				buf.foot=0;
				que.push(buf);
				buf.foot=1;
				que.push(buf);
			}
		}
		int result=100100100;
		while(!que.empty()){
			State state=que.top();
			que.pop();
//cout<<state.h<<" "<<state.w<<" "<<state.cost<<" "<<state.foot<<endl;
			if(state.cost>=cost[state.h][state.w][state.foot])continue;
			if(s[state.h][state.w]=="X")continue;
			chmin(cost[state.h][state.w][state.foot],state.cost);
			State next;
			next.foot=state.foot^1;
			int i,j;
			if(state.foot==0){
				for(i=-2;i<=2;i++){
					for(j=1;j<=3;j++){
						if(abs(i)+j>3)continue;
						if(!(0<=state.h+i&&state.h+i<h&&0<=state.w+j&&state.w+j<w))continue;
						next.h=state.h+i;
						next.w=state.w+j;
						if(s[next.h][next.w]=="S")continue;
						if(s[next.h][next.w]=="T"){
							chmin(result,state.cost);
							continue;
						}
						next.cost=state.cost+s[next.h][next.w][0]-'0';
						que.push(next);
					}
				}
			}
			if(state.foot==1){
				for(i=-2;i<=2;i++){
					for(j=-3;j<=-1;j++){
						if(abs(i)-j>3)continue;
						if(!(0<=state.h+i&&state.h+i<h&&0<=state.w+j&&state.w+j<w))continue;
						if(s[next.h][next.w]=="T"){
							chmin(result,state.cost);
							continue;
						}
						next.h=state.h+i;
						next.w=state.w+j;
						if(s[next.h][next.w]=="S")continue;
						next.cost=state.cost+s[next.h][next.w][0]-'0';
						que.push(next);
					}
				}
			}
		}
		if(result==100100100)cout<<-1<<endl;
		else cout<<result<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
h,w=map(int,input().split())
G=[[0]*10 for i in range(10)]
for i in range(10):
  G[i]=list(map(int,input().split()))
A=[1,2,6,24,120,720,5040,40320]
B=[i for i in range(10)]
E=[0]*10
for i in range(10):
  if i==1:
    continue
  E[i]=10**10
  for j in range(362880):
    C=B[0:11]
    D=[i]
    C.remove(i)
    for k in range(8):
      a=j//A[-1-k]
      j=j-A[-1-k]*a
      b=C.pop(a)
      D.append(b)
      if b==1:
        break
    D.append(C[0])
    c=0
    for j in range(9):
      if D[j]==1:
        break
      c=c+G[D[j]][D[j+1]]
    if c<E[i]:
      E[i]=c
F=[0]*11
GG=[[0]*w for i in range(h)]
for i in range(h):
  GG[i]=list(map(int,input().split()))
  for j in range(w):
    F[GG[i][j]]=F[GG[i][j]]+1
ans=0
for i in range(10):
  ans=ans+E[i]*F[i]
print(ans)

Measured memory_bytes: 46168
N, L = map(int, input().split())
sum_n = 0
for i in range(N):
    sum_n += (L + i)
mini = 9999
for i in range(N):
    # print("test", abs(L+i))
    if abs(L + i) <= abs(mini):
        mini = (L + i)
# print(mini)
print(sum_n - mini)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define Int int64_t

using namespace std;

int main() {
	int N;
	cin >> N;
	string s, t;
	cin >> s >> t;

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

	return 0;
}


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

typedef uint64_t u64;
typedef int64_t i64;
typedef uint32_t u32;
typedef int32_t i32;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;

#define REP(idx, N) for (u64 idx = 0; idx < N; idx++)

int main() {
  u32 N = 0;
  cin >> N;
  printf("%.10f",  M_PI*2*N);

  return 0;
}


Measured memory_bytes: 3668
# include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
template<typename T>vector<T> make_v(size_t a){ return vector<T>(a); }
template<typename T,typename... Ts>auto make_v(size_t a, Ts... ts){ return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); }
template<typename T,typename V>typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v){ t = v; }
template<typename T,typename V>typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v){ for(auto &e : t) fill_v(e, v); }
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)

int a, b;

int main(){
    cin >> a >> b;
    cout << max({a + a - 1, a + b, b + b - 1}) << endl;
}

Measured memory_bytes: 256
import sys

stdin = sys.stdin

sn = lambda : stdin.readline().rstrip()
an = lambda : map(int, stdin.readline().split())
ni = lambda : int(sn())

def f(n):
    return n*(n+1)//2

def main():
  n, k = an()
  a = list(an())

  mod = int(1e9)+7
  ans = 0
  x = a[:] 
  cnt = 0
  tcnt = 0
  for i, ai in enumerate(x):
    #cnt = 0
    for j in range(i+1, n):
      if ai > x[j]:
        cnt += 1
    #tcnt = 0
    for j in range(i+1):
      if ai > x[j]:
        tcnt += 1

  ans += f(k) * cnt
  ans %= mod
  ans += f(k - 1) * tcnt
  ans %= mod

  print(ans)

main()

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1ll<<30;
const ll longINF = 1ll<<60;
const ll MOD = 1000000007;
const bool debug = 0;
//---------------------------------//

int X[112345], Y[1123456];

ll solve(ll W, int *A) {
	ll res = 0;
	FOR(i, 1, W) {
		ll cur = (ll)i * (W - i) % MOD;
		cur = cur * (A[i] - A[i - 1]) % MOD;
		res = (res + cur) % MOD;
	}
	return res;
}

int main() {
	int N, M;
	cin >> N >> M;
	REP(i, N) scanf("%d", X + i);
	REP(i, M) scanf("%d", Y + i);
	
	ll ans = solve(N, X) * solve(M, Y) % MOD;
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
typedef long long int ll;
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (int i=0;i<signed(n);i++)
#define EREP(i,n) for (int i=1;i<=(n);i++)
#define ALL(a) (a).begin(),(a).end()
//#define EVEL 1

#ifdef EVEL
#define DEB(X) cout << #X << ":" <<X<<" " ;
#define DESS(X) cout <<X<<" " ;
#define TF(f) f ? cout<<"true  " : cout<<"false ";
#define END cout<<"\n";
#else
#define DEB(X) {}
#define TF(f) {}
#define END {}
#endif
const int MOD = 10007;
const ll INF = 20000000000;
typedef std::pair<int,int> P;


	ll ans=0;
	ll N,M,K,X;
	ll A[200010],B[200010],as,bs;
	// ll L[200010],R[200010];
	ll deff[200010];
	vector<P> Q;
	string S,T;
	ll id=0;
	ll sum;bool F=true;
	ll gcd(ll a,ll b){
	    if(b==0)return a;
	    return gcd(b,a%b);
	}
int main(){
	ios_base::sync_with_stdio(false);
	cin>>N>>X;
	REP(i,N){cin>>A[i];A[i]-=X;}
	A[N]=0;
	sort(A,A+N);
	REP(i,N){
		B[i]=abs(A[i+1]-A[i]);
	}
	sort(B,B+N+1);
	REP(i,N-1){
		if(ans==0)ans=gcd(B[i+1],B[i+2]);
		else{ans=gcd(ans,B[i+2]);}
	}
	if(N==1)ans=abs(A[0]);
	cout<<ans<<endl;
}

Measured memory_bytes: 2816
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
using namespace std;
typedef long long ll;
int main(){
  double a,b,x;
  cin >> a >> b >> x;
  if(x < a * b * a / 2){
    double theta = (double)90 - atan(2*x/(b*b*a))/3.14159265358979*180;
    printf("%.14lf\n",theta);
  }
  else{
    double theta = atan(2*(a*a*b-x)/(a*a*a))/3.14159265358979*180;
    printf("%.14lf\n",theta);
  }
}

Measured memory_bytes: 512
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <iterator>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <complex>
#include <bitset>
#include <numeric>
using namespace std;

typedef long long LL;  typedef pair<LL, LL> PLL; typedef vector<LL> VLL;
#define REP(i,n) for(int (i)=0; (i)<(n) ;++(i))
#define REPN(i,a,n) FOR((i),(a),(a)+(n))
#define FOR(i,a,b) for(int (i)=(a); (i)<(b) ;++(i))
#define PB push_back
#define MP make_pair
#define OUT(a) cout<<(a)<<endl;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int l=s.length(), dat[200020]={},ans=0;
    REPN(i,1,l){
        if(s[i-1]=='S'){
            dat[i]=dat[i-1]+1;
        }else{
            dat[i]=max(0,dat[i-1]-1);
        }
    }

    REPN(i,1,l){
        if(dat[i-1]==0 and dat[i]==0)ans++;
    }
    cout << ans+dat[l] <<endl;

    return 0;
}


Measured memory_bytes: 1300
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int a,b,c,d,e,maximum;
  
  cin>>a>>b;
  
  c=a+b;
  d=a-b;
  e=a*b;
  
  maximum = max(e,max(c,d));
  cout<<maximum<<endl;
  
  return 0;
}

Measured memory_bytes: 256
from collections import defaultdict
from collections import deque
N, M = map(int, input().split())
D = defaultdict(list)
Edge = []
for i in range(M):
  A, B = map(int, input().split())
  D[A-1].append(B-1)
  D[B-1].append(A-1)
  Edge.append((A-1, B-1))
def dfs(n, vstd, i):
  vstd.add(n)
  for a in D[n]:
    if a not in vstd and (a, n) != i and (n,a) != i:
      dfs(a, vstd, i)
  return len(vstd)

cnt = 0
for i in Edge:
  if dfs(0, set(), i) < N:
    cnt += 1
print (cnt)

Measured memory_bytes: 4212
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <functional>
#include <numeric>
#include <iomanip>
#define fi first
#define se second
#define fcout(n) cout<<fixed<<setprecision((n))
#define cinl(str) getline(cin,(str))
using namespace std;
bool value(int y,int x,int R,int C){return 0<=y&&y<R&&0<=x&&x<C;}
typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long > vll;
typedef vector< vi > vvi;
double pie=acos(-1);
int INF=1000000007;
int dx[4] = { 0,-1,0,1 };
int dy[4] = { -1,0,1,0 };


int main() {
	int a,b;
	cin>>a>>b;
	if(a+b>=10){
		cout<<"error"<<endl;
	}
	else{
		cout<<a+b<<endl;
	}
}

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

int main(){
  char title[50][101];
  char sleeptitle[101];
  int time[50];
  int n,i,j;
  int total=0;
  int flag=0;
  
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s %d",title[i],&time[i]);
  }
  scanf("%s",sleeptitle);
  
  for(i=0;i<n;i++){
    if(flag==1){
      total+=time[i];
    }
    if(strcmp(sleeptitle,title[i])==0){
      flag=1;
    }
  }
  printf("%d",total);
}


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

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

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

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

void solve() {
  int N;
  in(N);
  set<int> s;
  bool ans = true;
  rep(i, N) {
    int a;
    in(a);
    if (s.find(a) != s.end()) {
      ans = false;
    } else {
      s.insert(a);
    }
  }

  print(ans ? "YES" : "NO");
}


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

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    ll mina;
    ll minb;
    ll mind = N;

    for(int i = 1; i <= sqrt(N); ++i){

        if(N % i == 0){
            int d = N / 2 - i;
            
            if(d < mind){
                mina = i;
                minb = N / i;
            }
        }
    }
    cout << mina + minb - 2 << endl;
}

Measured memory_bytes: 256
def abc108_b():
    import sys
    input = sys.stdin.readline

    x1, y1, x2, y2 = map(int, input().split())

    x3 = x2 - (y2 - y1)
    y3 = y2 + (x2 - x1)
    x4 = x3 - (y3 - y2)
    y4 = y3 + (x3 - x2)

    return "{} {} {} {}".format(x3, y3, x4, y4)


print(abc108_b())

Measured memory_bytes: 3060
/*input
141421 35623
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

#define rep(i,j,n) for(i=j;i<n;i++)
#define repi(i,j,n) for(i=j;i>n;i--)
#define inf 100001
#define M 1000000007
#define ll long long
#define ld long double
#define vll vector<long long>
#define vi vector<int>
#define pll pair<long long,long long>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define vpll vector<pair<long long,long long> >
#define pb push_back
#define pf pop_front
#define F first
#define S second
#define endl '\n'

using namespace std;
using namespace __gnu_pbds; 

template<typename T>
using ordered_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


ll power(ll a,ll m,ll mod){
	ll ans=1;
	while(m){
		if(m%2){
			ans*=a;
			ans%=(mod);
		}
		a=(a*a)%(mod);
		m>>=1;
	}
	return ans;
}


void init(ll* a,ll n,ll val){
	for(ll i=0;i<n;i++)
		a[i]=val;
}



int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);	
	ll t=1,i,j;
	ll n,k;
	cin>>n>>k;
	ll ans=0;
	rep(k,k,n+2)ans+=k*n-(k-1)*(k)+1,ans%=M;
	cout<<ans<<endl;
	return 0;
}




Measured memory_bytes: 3656
import scala.io.StdIn
object Main extends App {
  val n = StdIn.readLine().toInt
  val x = StdIn.readLine().split(' ').map(_.toInt)
  val y = x.sorted


  // before: 2  4   4  3
  // sorted: 2 [3] [4] 4
  //
  // (1)   :   4 4 3
  // (2)   : 2   4 3
  // (3)   : 2 4   3
  // (4)   : 2 4 4  

  val mid = n / 2 // 2
  val mid_left = y(mid - 1)
  val mid_right = y(mid)

  val r = x.map(xi => if (xi <= mid_left) mid_right else mid_left)

  r.foreach(println)

}

Measured memory_bytes: 71800
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=2e5;
int n,x,y,tot;
int pre[maxn*4+8],son[maxn*4+8];
bool can[maxn+8];
queue<int>st;
 
int read()
{
    int x=0,f=1;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x*f;
}
 
struct Tree
{
    int now[maxn+8],dep[maxn+8],f[maxn+8][20];
    void add(int u,int v)
    {
    pre[++tot]=now[u];
    now[u]=tot;
    son[tot]=v;
    }
    void build(int x)
    {
    dep[x]=dep[f[x][0]]+1;
    for (int i=1;i<=log(dep[x])/log(2);i++) f[x][i]=f[f[x][i-1]][i-1];
    for (int p=now[x];p;p=pre[p])
        {
        int child=son[p];
        if (f[x][0]==child) continue;
        f[child][0]=x;
        build(child);
        }
    }
    int Get_Lca(int x,int y)
    {
    if (dep[x]<dep[y]) swap(x,y);
    for (int i=log(dep[x])/log(2);~i;i--)
        if (dep[f[x][i]]>=dep[y]) x=f[x][i];
    if (x==y) return x;
    for (int i=log(dep[x])/log(2);~i;i--)
        if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
    }
    int Get_Dis(int x,int y){return dep[x]+dep[y]-dep[Get_Lca(x,y)]*2;}
}T1,T2;
 
void solve()
{
    //for (int i=1;i<=n;i++) printf("%d ",can[i]);puts("");
    int ans=0;
    for (int i=1;i<=n;i++)
    if (can[i])
        {
        ans=max(ans,T2.dep[i]-1);
        for (int p=T1.now[i];p;p=pre[p])
            {
            int child=son[p];
            if (T2.Get_Dis(child,i)>2)
                {
                puts("-1");
                exit(0);
                }
            }
        }
    printf("%d\n",ans*2);
}
 
void prepare()
{
    can[x]=1;
    st.push(x);
    while(!st.empty())
    {
        int x=st.front();st.pop();
        for (int p=T1.now[x];p;p=pre[p])
        {
            int child=son[p];
            if (can[child]) continue;
            if (T1.dep[child]<T2.dep[child]) can[child]=1,st.push(child);
        }
    }
}
 
int main()
{
    n=read(),x=read(),y=read();
    if (x==y)
    {
        puts("0");
        return 0;
    }
    for (int i=1;i<n;i++)
    {
        int u=read(),v=read();
        T1.add(u,v),T1.add(v,u);
    }
    for (int i=1;i<n;i++)
    {
        int u=read(),v=read();
        T2.add(u,v),T2.add(v,u);
    }
    T1.build(x),T2.build(y);
    prepare();
    solve();
    return 0;
}

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

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

#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>

#define MOD 1000000007
#define INF 1000000000000000LL

using namespace std;

int main(){
  string s;cin>>s;
  bool f=true;
  rep(i, s.size())if(s[i]=='7')f=false;

  if(f) cout<<"No"<<endl;
  else cout<<"Yes"<<endl; 



  return 0;
}

Measured memory_bytes: 3624
#include <stdio.h>
int Binary(int ,int * ,int,int);
int main()
{
  int n,q;
  int A[20],M[2000];
  int i,j;

  scanf("%d",&n);
  for(i=0;i<n;i++)
    {
      scanf("%d",&A[i]);
      //printf("%d\n",A[i]);
    }
  scanf("%d",&q);
  for(i=0;i<q;i++)
    {
      scanf("%d",&M[i]);
      //printf("%d\n",M[i]);
    }

  for(i=0;i<q;i++)
    {
      if(Binary(M[i],A,n,0)) printf("yes\n");
      else printf("no\n");
    }
  return 0;
}

int Binary(int m,int *A,int n,int j)
{
  int ans=0;
  // printf("%d %d\n",m,j);
  if(m==A[j]) return 1;
  if(j==n) return 0;
  ans = Binary(m-A[j],A,n,j+1);
  if(ans == 1) return 1;
  ans = Binary(m,A,n,j+1);
  if(ans == 1) return 1;
  else return 0;
}

Measured memory_bytes: 588
dir = {'>': (0, 1), '<': (0, -1), 'v': (1, 0), '^': (-1, 0)}

# solve function
def solve(h, w, tiles, visited):
     x, y = 0, 0

     while True:
         if tiles[y][x] == '.':
             print(x, y)
             break

         if not visited[y][x]:
             print("LOOP")
             break

         visited[y][x] = False

         next_y, next_x = dir[tiles[y][x]]

         x += next_x
         y += next_y

     return

# main function
if __name__ == '__main__':
    while True:
        # input param
        inputs = (input()).split()

        h = int(inputs[0])
        w = int(inputs[1])

        if h == 0 and w == 0:
            break

        visited = [[True for i in range(w)] for j in range(h)]
        tiles = ["" for i in range(h)]

        for i in range(h):
            tiles[i] = input()

        solve(h, w, tiles, visited)

Measured memory_bytes: 6884
import re

num = re.compile(r'\d+$')

def testcase_ends():
    n = int(input())
    if n == 0:
        return 1

    marks = [input().replace('-', '') for i in range(n)]
    links = {}
    bares = []
    labels = {}
    for i, mark in enumerate(marks, 1):
        if not mark:
            bares.append(i)
            continue

        v = False
        if mark.endswith('v'):
            mark = mark[:-1]
            links[i+1] = i
            v = True

        m = num.search(mark)
        if m is None:
            continue

        m = int(m.group())
        mark = num.sub('', mark)

        if m == 1:
            if mark in labels:
                links[i] = labels[mark]
                del labels[mark]
            if not v:
                bares.append(i)
        else:
            if mark in labels:
                links[i] = labels[mark]

            labels[mark] = i

    for w in bares:
        print(w)
        while w in links:
            w = links[w]
            print(w)

    return 0

def main():
    while not testcase_ends():
        pass

if __name__ == '__main__':
    main()



Measured memory_bytes: 8508
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		long ans = 0;

		switch (A) {
		case 1:
			ans += 300000;
			break;
		case 2:
			ans += 200000;
			break;
		case 3:
			ans += 100000;
			break;
		default:
			break;
		}

		switch (B) {
		case 1:
			ans += 300000;
			break;
		case 2:
			ans += 200000;
			break;
		case 3:
			ans += 100000;
			break;
		default:
			break;
		}

		if (A == 1 && B == 1) {
			ans += 400000;
		}

		System.out.println(ans);

	}
}

Measured memory_bytes: 35784
#include <bits/stdc++.h>
using namespace std;
vector <int> v[100001];
#define pb push_back
vector <int> dp;
int g;
int solve(int x)
{
    if(v[x].size()==0)
        return 0;
    if(dp[x]!=0)
        return dp[x];
    for(int i=0;i<v[x].size();i++)
        dp[x]=max(dp[x],solve(v[x][i])+1);
    return dp[x];
}
int main()
{
    g=-1;
    int n,m,b,u;
    cin>>n>>m;
    dp.resize(n+1,0);
    while(m--){
        cin>>u>>b;
        v[u].pb(b);
    }
    for(int i=1;i<=n;i++){

        if(dp[i]==0){
            int a=solve(i);
        }
    }
    sort(dp.begin(),dp.end());
    cout<<dp[n]<<endl;
}


Measured memory_bytes: 8192
iN ,iX  = [int(x) for x in input().split()]
aX = [int(x) for x in input().split()]

aCum = [0]*(iN)
aCum[0] = aX[0]
for i in range(1,iN):
    aCum[i]=aCum[i-1]+aX[i]

def fCeil(iT,iR):
    return -1 * iT // iR * -1

def fCalcCost(iN,iX,aCum,iK):
    iCost = 5 * aCum[-1]
    for i in range(2,fCeil(iN,iK) ):
        iCost += 2 * aCum[-1 * i * iK -1]
    iCost += (iK +iN)*iX
    return iCost

iTotalCost = fCalcCost(iN,iX,aCum,1)
for iK in range(2,fCeil(iN,2) + 1):
    iTotalCost = min(iTotalCost,fCalcCost(iN,iX,aCum,iK))
print(iTotalCost)


Measured memory_bytes: 25836
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cmath>

using namespace std;

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

//10^9 + 7
const ll MOD = 1000000007;

int main() {

	string str[1000];
	//初期化
	rep(i, 1000) {
		str[i] = to_string(i);
	}

	ll N, M;
	cin >> N >> M;

	rep(i, 1000) {
		if (str[i].length() != N) {
			str[i] = "";
		}
	}
	ll s, c;
	char tmp;
	rep(i, M) {
		cin >> s >> c;

		rep(j, 1000) {
			if (str[j] == "") continue;

			tmp = str[j][s - 1];

			if (tmp - '0'!= c) str[j] = "";
		}
	}
	string ans = "-1";

	rep(i, 1000) {
		if (str[i] != "") {
			ans = str[i];
			break;
		}
	}

	cout << ans << endl;
	
}

Measured memory_bytes: 256
N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

l = []

if M == 0:
  print(0)
else:
  for i in range(2):
    for j in range(2):
      for k in range(2):
        B = [a[0]*(-1)**i + a[1]*(-1)**j + a[2]*(-1)**k for a in A]
        C = sorted(B)
        l.append(sum(C[-M:]))
  print(max(l))

Measured memory_bytes: 3368
#include<iostream>
#include <stdlib.h>
#include <algorithm>
#include <string>
#include <vector>
typedef long long int ll;
using namespace std;
int main() {
	int A,B;
	cin>> A>>B;
	if(A>=13){
		cout<< B<< endl;
	}else if(A<=5){
		cout <<'0'<< endl;
	}else{
		cout<<B/2<<endl;
		
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
using ll = long long;
const ll MOD = 1e9+7; ll LLINF = 1LL << 60; int INF = INT_MAX;

//

int main(){
    ll n,m; cin>>n>>m;
    vector<ll> a(n);
    rep(i,0,n) cin>>a[i];
    vector<pair<ll,ll>> cb(m);
    rep(i,0,m) {
        cin>>cb[i].second>>cb[i].first;
    }
    sort(all(cb));
    reverse(all(cb));
    sort(all(a));
    int cnt=0;
    rep(i,0,m){
        for(ll j=1; j<=cb[i].second; j++){
            a[cnt]=max(cb[i].first,a[cnt]);
            if(cnt==n-1) break;
            cnt++;
        }
    }
    ll ans=0;
    rep(i,0,n){
        ans+=a[i];
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 2560
#include <iostream>
#include <string>
#include <utility>

using namespace std;

int main()
{
  string s, t;
  cin >> s >> t;
  if (s.find(t) != string::npos)
  {
    for (int i = 0; i < s.size(); ++i)
    {
      if (s[i] == '?')
      {
        cout << 'a';
      }
      else
      {
        cout << s[i];
      }
    }
    cout << endl;
    return 0;
  }

  pair<int, int> range = make_pair(-1, -1);
  for (int i = s.size() - 1; i >= 0; --i)
  {
    //
    if (i - (t.size() - 1) < 0)
    {
      break;
    }
    bool result = true;
    for (int j = 0; j < t.size(); ++j)
    {
      int si = i - j;
      int ti = (t.size() - 1) - j;

      if (s[si] != '?' && s[si] != t[ti])
      {
        result = false;
        break;
      }
    }
    if (result)
    {
      range = make_pair(i - (t.size() - 1), i);
      break;
    }
  }

  if (range.first != -1 && range.second != -1)
  {
    for (int i = 0; i < s.size(); ++i)
    {
      if (range.first <= i && i <= range.second)
      {
        cout << t[i - range.first];
      }
      else if (s[i] == '?')
      {
        cout << 'a';
      }
      else
      {
        cout << s[i];
      }
    }
    cout << endl;
  }
  else
  {
    cout << "UNRESTORABLE" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
using System;
class Program
{
    static void Main(string[] args)
    {
        int Day = int.Parse(Console.ReadLine());
        if (Day == 25)
            Console.WriteLine("Christmas");
        if (Day == 24)
            Console.WriteLine("Christmas Eve");
        if (Day == 23)
            Console.WriteLine("Christmas Eve Eve");
        if (Day == 22)
            Console.WriteLine("Christmas Eve Eve Eve");
    }
}

Measured memory_bytes: 11092
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<map>
#include<queue>
#include<stack>
#include<deque>
#include<fstream>
#include<string>
#include<sstream>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<random>
#include<bitset>

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++) //0から
#define REP(i,n) for(int j=i;j<n;j++) //iから

typedef long long ll;



//英字ならture、数字ならfalse
bool isalpha(char s){
    if(('A'<=s&&s<='Z')||('a'<=s&&s<='z')){
        return 1;
    }else{
        return 0;
    }
}
//全ての文字が英字ならture、数字ならfalse
bool Isalpha(string s){
    ll n;
    bool tmp = true;
    rep(i,n){
        if(isalpha(s[i])){
            tmp = false;
        }
    }
    return tmp;
}




using Graph = vector<vector<ll>>;



//cout<<fixed<<setprecision(10);

ll binary_search(vector<ll> a, ll n, ll key){
    ll right = n, left = -1;
    ll md = (right + left) / 2;

    while(right - left > 1){
        if(a[md] <= key){
            right = md;
        }else{
            left = md;
        }
        md = (right + left) / 2;
    }
    if(left == -1) return -1; //無い場合
    return right;
}



int main(){
    ll n,k;
    cin>>n>>k;
    vector<ll> p(n);
    rep(i,n){
        cin>>p[i];
    }
    sort(p.begin(),p.end());
    ll ans=0;
    rep(i,k){
        ans += p[i];
    }

    cout<<ans<<endl;


    return 0;
}



Measured memory_bytes: 3596
import java.util.*;
public class Main{
 public static void main(String[] args){
   Scanner sc = new Scanner(System.in);
   int N = sc.nextInt();
   int K = sc.nextInt();
   long[] H = new long[N];
   for(int i=0;i<N;i++) H[i] = sc.nextLong();
   long ans = 0;
   Arrays.sort(H);
   for(int i=0;i<N-K;i++)
   {
     ans+=H[i];
   }
   System.out.println(ans);
 }
}

Measured memory_bytes: 70192
#include <bits/stdc++.h> 
using namespace std;
#define rep(i, N) for(int i=0; i<N; i++)
typedef long long ll;
#define dump(x) cerr<<#x<<"="<<x<<endl
using P = pair<int, int>;

int main() {
   int h, w, k; cin >> h >> w >> k;

   vector<vector<char>> c(h+2, vector<char>(w+2, '.'));
   rep(i, h){
      rep(j, w){
         cin >> c.at(i).at(j);
      }
   }

   vector<vector<char>> d(h+2, vector<char>(w+2, '.'));

   ll ans = 0;
   rep(i, 1<<h){
      d = c;
      for(int j=0; j<h; j++){
         if(i&(1 << j)){
            rep(l, w){
               d.at(j).at(l) = '.';
            }
         }
      }

      vector<vector<char>> e(h+2, vector<char>(w+2, '.'));
      rep(j, 1<<w){
         e = d;
         for(int l=0; l<w; l++){
            if(j&(1<<l)){
               rep(m, h){
                  e.at(m).at(l) = '.'; 
               }
            }
         }

         ll cnt = 0;
         rep(l, h){
            rep(m, w){
               if(e.at(l).at(m)=='#') cnt++;
            }
         }
         if(cnt == k) ans++;
      }

   }

   cout << ans << endl;

   return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>

using namespace std;
typedef long long ll;
typedef pair<int,int> P;
string s;
int mindif = 10000;
void update(int pos){
	int a = s[pos] - '0';
	for(int i=pos+1;i<=pos+2;i++) a = a * 10 + (s[i] - '0');
	mindif = min(mindif,abs(a - 753));
}
int main(){
	cin >> s;
	for(int i=0;i + 2 < (int)s.size();i++) update(i);
	printf("%d\n",mindif);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <limits>
#include <cmath>

using namespace std;

int main() {
    size_t n;
    cin >> n;
    map<string, size_t> a{};
    for (size_t i = 0; i < n; ++i) {
        string s;
        cin >> s;
        ++a.emplace(s, 0).first->second;
    }
    queue<pair<string, size_t>> b{};
    for (auto& e : a) {
        while (!b.empty() && b.front().second < e.second)
            b.pop();
        if (b.empty() || b.front().second <= e.second)
            b.emplace(move(e));
    }
    while (!b.empty()) {
        cout << b.front().first << endl;
        b.pop();
    }
    return 0;
}



Measured memory_bytes: 28544
// #pragma GCC optimize("O3")
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace ::std;
// clang-format off
template<typename T> T nxt() {T res; cin >> res; return res;}
#define tests() for (int _ = nxt<int>(); _ >= 0; _--)
#define nxt1(t,n) t (n); cin >> n
#define nxt2(t,n,m) t (n),(m); cin >> n >> m
#define nxt3(t,n,m,k) t (n),(m),(k); cin >> n >> m >> k
#define rep(i, A) for (int i = 0 ; i < A ; i++)
#define ll long long
typedef pair<int,int> pii;typedef pair<ll, ll> pll;typedef vector<int> vi;typedef vector<vi> vvi;typedef vector<ll> vl;typedef vector<vl> vvl;
#define dbg(vari) cerr<<#vari<<" = "<<(vari)<<endl;
template<typename T,typename TT> ostream& operator<<(ostream &s,pair<T,TT> t) {return s<<"("<<t.first<<","<<t.second<<")";}
template<typename T> ostream& operator<<(ostream &s,vector<T> t){for(T ti : t)s<<ti<<" ";return s; }
#define all(x) (x).begin(), (x).end()
#define last(vec) vec[vec.size()-1]
#define has(c,x) ((c).find(x) != (c).end())
// clang-format on

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

    int N = nxt<int>();
    vector<double> p(N);
    generate(all(p), nxt<double>);

    vector<double> dp(N + 1);
    dp[0] = 1;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j >= 0; j--) {
            dp[j] = (j == 0 ? 0 : dp[j - 1] * p[i]) + dp[j] * (1 - p[i]);
        }
    }

    double ans = 0;
    for (int i = 0; i <= N; i++) {
        if (i > N - i) {
            ans += dp[i];
        }
    }
    printf("%.10lf\n", ans);
    return 0;
}


Measured memory_bytes: 3896
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int main(){

	int i,n,number;
	int s[13],h[13],c[13],d[13];
	char type;
	
	for(i=0;i<13;i++){
		s[i] = 0;
		h[i] = 0;
		c[i] = 0;
		d[i] = 0;
	}

	cin >> n;

	for(i=0;i<n;i++){
		cin >> type >> number;
		if(type == 'S')s[number-1] = 1;
		else if(type == 'H')h[number-1] = 1;
		else if(type == 'C')c[number-1] = 1;
		else if(type == 'D')d[number-1] = 1;
	}

	for(i=0;i<13;i++){
		if(s[i] == 0) cout << "S " << i+1 << endl;
	}
	for(i=0;i<13;i++){
		if(h[i] == 0) cout << "H " << i+1 << endl;
	}
	for(i=0;i<13;i++){
		if(c[i] == 0) cout << "C " << i+1 << endl;
	}
	for(i=0;i<13;i++){
		if(d[i] == 0) cout << "D " << i+1 << endl;
	}

	return 0;
}


Measured memory_bytes: 3100
#include<iostream>
#include<algorithm>
using namespace std;
#define INF ( 1 << 30 )

int dp[1001],tmp[]={500,100,50,10,5,1},n;
int main(){
  fill_n(dp,1001,INF);
  dp[0] = 0;
  for(int i = 0 ; i < 1001 ; i++ ){
    for(int j = 0 ; j < 6 ; j++ ){
      if(i-tmp[j]>=0) dp[i] = min(dp[i],dp[i-tmp[j]]+1);
    }
  }
  while(cin >> n , n) cout << dp[1000-n] << endl;
}

Measured memory_bytes: 1164
N, M = map(int, input().split())
LR = []
for _ in range(M):
    LR.append(list(map(int, input().split())))
mn, mx = 0, int(1e5)
for i, j in LR:
    if i >= mn:
        mn = i
    if j <= mx:
        mx = j
    
if mx < mn:
    print(0)
else:
    print(mx - mn + 1)

Measured memory_bytes: 27344
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int n;
int a[3005];
ll dp[3005][3005];
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		}
	for(int i=n-1;i>=0;i--){
		for(int j=i;j<n;j++){
			if(dp[i]==dp[j])
			dp[i][j]=a[i];
			else
			dp[i][j]=max(a[i]-dp[i+1][j],a[j]-dp[i][j-1]);
			}
		
		}
	cout<<dp[0][n-1]<<endl;
	
	return 0;
	}


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

int main(){
    int N = 0, W = 0, S = 0, E = 0, flag = 0;
    string Str;
    cin >> Str;
    for(int i=0;Str[i] != '\0';i++){
        if(Str[i] == 'N') N++;
        if(Str[i] == 'W') W++;
        if(Str[i] == 'S') S++;
        if(Str[i] == 'E') E++;
    }
    
    if((N == 0 && S > 0) || (N > 0 && S == 0)){
        flag = 1;
    }
    if((W == 0 && E > 0) || (W > 0 && E == 0)){
        flag = 1;
    }

    if(flag == 0)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

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

#define ll long long 
#define sz(x) (int)x.size()

using namespace std;

int main(){
	ll a,b,c;
	cin>>a>>b>>c;
	ll x=1e5,d=a;
	while(x--){
		if(a%b==c){
			cout<<"YES";
			return 0;
		}
		a+=d;
	}
	cout<<"NO";

	
	
}

Measured memory_bytes: 3568
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <queue>

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-6;
const double PI  = acos(-1.0);

struct P{
  double x;
  double y;

  P(){
  }

  P(const double &s , const double &e)
  { x=s; y=e;}

  P operator - (const P &t) const
  { return P(x-t.x , y-t.y); }

  P operator + (const P &t) const
  { return P(x+t.x , y+t.y); }

  P operator * (const double &d) const
  { return P(x*d , y*d); }

};
double cross(P a,P b){
  return (a.x*b.y-a.y*b.x);
}
P interpoint_s(P a1 , P a2 , P b1 , P b2){
  P b=b2-b1;
  double d1=fabs(cross(b , a1-b1));
  double d2=fabs(cross(b , a2-b1));
  double t=d1 / (d1 + d2);
  P a=a2-a1;
  P v=a*t;
  return a1+v;
}

bool diff(P p, P q){
  return abs(p.x - q.x) >= EPS || abs(p.y - q.y) >= EPS;
}

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

  int N; cin >> N;
  vector<P> ps(N);
  REP(i,N) cin >> ps[i].x >> ps[i].y;

  bool ok = true;
  P p;
  if(N < 4 || N%2) ok = false;
  else{
	int D = N / 2;
	p = interpoint_s(ps[0], ps[D], ps[1], ps[D+1]);
	for(int i=1;i<D;++i){
	  P q = interpoint_s(ps[0], ps[D], ps[i], ps[i+D]);
	  if(diff(p,q)){
		ok = false; break;
	  }
	}
  }
  if(!ok) cout << "NA" << endl;
  else cout << fixed << setprecision(9) << p.x << " " << p.y << endl;
  
  return 0;
}

Measured memory_bytes: 1308
N = int(input())
K = int(input())

Ns = list(map(int,list(str(N))))
L = len(Ns)
    
dp = [[[0]*L for i in range(5)] for j in range(2)]
dp[0][1][0] = 1 # strict
dp[1][1][0] = Ns[0] - 1 # loose
dp[1][0][0] = 1
for i in range(L-1):
    n = Ns[i+1]
    for j in range(4): # 0,1,2,3
        if n == 0:
            dp[0][j][i+1] += dp[0][j][i] # 0
            dp[1][j][i+1] += dp[1][j][i] # 0
            dp[1][j+1][i+1] += 9*dp[1][j][i] # 1 to 9
        else:
            dp[0][j+1][i+1] += dp[0][j][i] # n
            dp[1][j][i+1] += dp[0][j][i] # 0
            dp[1][j+1][i+1] += (n-1) * dp[0][j][i] # 1 to n-1
            dp[1][j][i+1] += dp[1][j][i] # 0
            dp[1][j+1][i+1] += 9*dp[1][j][i] # 1 to 9
print(dp[0][K][L-1] + dp[1][K][L-1])



Measured memory_bytes: 38256
N = input()
B = input()
BList = []
BList = B.split(" ")
A = []
outputList = []
output = 0
num = 0

if (int(N)<101) and (int(N) > 1): 
    for i in range(len(BList)):
        if i == 0:
            outputList.append(BList[i])
        else:
            if int(BList[i-1]) <= int(BList[i]):
                outputList.append(BList[i-1])
            else:
                outputList.append(BList[i])
    outputList.append(BList[-1])

    for i in outputList:
        output = output + int(i)
    print(output)


Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
 
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

int main(){
    string a,b,c;
    cin >> a >> b >> c;
    int x = 'a' - 'A';
    cout << (char) (a[0] - x) << (char) (b[0] - x) << (char) (c[0] - x) << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MAX 100100
using namespace std;
struct process{
  public:
    char name[10];
    int time;
};
int head,tail;
int process_time = 0;
vector<process> q(MAX);
bool is_emptyq(){
  if( head == tail ) return true;
  return false;
}
process deq(){
  process c = q[head];
  head = (head+1) % MAX;
  return c;
}
void enq(process p){
  q[tail] = p;
  tail = (tail+1) % MAX;
}
void do_process(int q_time){
  process p_now = deq();
  if ( p_now.time > q_time){
    p_now.time -= q_time; process_time += q_time;
    enq(p_now);
  }
  else{
    process_time += p_now.time;
    cout << p_now.name << ' ' << process_time << endl;
  }
}
int main(){
  int n,qt; cin>>n>>qt;
  head = 0; tail = n;
  for(int i=0; i<n; ++i){
    cin>> q[i].name >> q[i].time;
  }
  while( !is_emptyq() ){
    do_process(qt);
  }
  return 0;
}



Measured memory_bytes: 4188
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int n,k,q,arr[10000000],arrfen[10000000];
int main(){
	scanf("%d%d%d",&n,&k,&q);
	for(int i=0;i<n;i++){
		arr[i]=k;
	} 
	int s;
	for(int i=0;i<q;i++){
		scanf("%d",&s);
		arr[s-1]+=1; 
	}
	for(int i=0;i<n;i++){
		if(arr[i]-q>0){
			printf("Yes\n");
		}else{
			printf("No\n");
		}
	}
	
	return 0;
}

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

int main() {
    int h1, h2, k1, k2;
    int a, b, c, d;
    cin >> h1 >> h2;
    cin >> k1 >> k2;
    cin >> a >> b >> c >> d;
    int hIwana = h1 * a + (((int)(h1 / 10)) * c);
    int hYamame = h2 * b + (((int)(h2 / 20)) * d);
    int kIwana = k1 * a + (((int)(k1 / 10)) * c);
    int kYamame = k2 * b + (((int)(k2 / 20)) * d);
    int hscore = hIwana + hYamame;
    int kscore = kIwana + kYamame;
    if (hscore > kscore) {
        cout << "hiroshi" << endl;
    } else if (hscore < kscore) {
        cout << "kenjiro" << endl;
    } else {
        cout << "even" << endl;
    }
}

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

using namespace std;

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = long long;
using P = std::tuple<int,int>;

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

int N, H;
vector<P> v;

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

    std::cin >> N >> H;

    v.resize(N);
    for(int i=0;i<N;++i){
        std::cin >> fst(v[i]) >> snd(v[i]);
    }

    sort(v.begin(), v.end());
    int mx_a = fst(v[N-1]);
    sort(v.begin(), v.begin() + N, [](const P& p, const P& q){
            return snd(p) > snd(q);
        });
    
    ll damage = 0, cnt = 0;
    for(int i=0;i<N;++i){
        if(damage < H && snd(v[i]) > mx_a){
            damage += snd(v[i]);
            ++cnt;
        }
    }

    if(damage < H){
        cnt += (1ll * H - damage + mx_a - 1) / mx_a;
    }

    std::cout << cnt << std::endl;
}


Measured memory_bytes: 1024
H,W = map(int,input().split())

if H%3 == 0 or W % 3 == 0:
    print(0)
else:
    ans = 10 ** 11
    for i in range(W):
        if i == 0:
            j = (H//3)
            k = (H-j)//2
            s1 = W * j
            s2 = W * k
            s3 = W * (H-j-k)
            M = max(s1,s2,s3) - min(s1,s2,s3)
            ans = min(ans,M)
            continue
        s1 = i * H
        j = H //2
        s2 = (W-i) * j
        s3 = (W-i) * (H-j)
        M = max(s1,s2,s3) - min(s1,s2,s3)
        ans = min(ans,M)
        
    tmp = W
    W = H
    H = tmp
    
    for i in range(W):
        if i == 0:
            j = (H//3)
            k = (H-j)//2
            s1 = W * j
            s2 = W * k
            s3 = W * (H-j-k)
            M = max(s1,s2,s3) - min(s1,s2,s3)
            ans = min(ans,M)
            continue
        s1 = i * H
        j = H //2
        s2 = (W-i) * j
        s3 = (W-i) * (H-j)
        M = max(s1,s2,s3) - min(s1,s2,s3)
        ans = min(ans,M)
        
    print(ans)
        

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define dum(x) cout<<#x<<'='<<x<<endl
#define ll long long
using namespace std;

int main() {
  int n;
  cin >> n;
  double t, a;
  cin >> t >> a;
  vector<double> v(n);
  for (int i = 0; i < n; ++i) {
    int h;
    cin >> h;
    v.at(i) = t - h * 0.006;
  }
  double ans = 100000000;
  int res = 0;
  for (int i = 0; i < n; ++i) {
    double tmp = abs(a - v.at(i));
    if (tmp < ans) {
      res = i + 1;
      ans = tmp;
    }
  }
  cout << res << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;
int a,b,c,n;
int cmd(int q,int p)
{
    int i;
    if(q>p)
        return q;
    for(i=1;i<=n;i++)
    {
        q=q*2;
        if(q>p)
            break;
    }
    n=n-i;
    return q;
}
int main()
{

    scanf("%d %d %d %d",&a,&b,&c,&n);
    int t=a/b+1;
    int f=n-t;
    b=cmd(b,a);
    c=cmd(c,b);
    if(b>a&&c>b)
       cout<<"Yes"<<endl;
    else cout <<"No"<<endl;
    return 0;
}


Measured memory_bytes: 3740