akhauriyash/Code-Regression huggingface dataset:
#[allow(unused_imports)]
use proconio::{fastout, input};

#[fastout]
fn main() {
    input!(n: usize, m: usize, ps: [(usize, String); m]);

    let mut wa: isize = 0;
    let mut ac: isize = 0;
    let mut bool_array: Vec<isize> = vec![0; n];
    for v in ps {
        if bool_array[v.0 - 1] != -1 {
            if v.1 == "AC" {
                wa += bool_array[v.0 - 1];
                bool_array[v.0 - 1] = -1;
                ac += 1;
            } else {
                bool_array[v.0 - 1] += 1;
            }
        }
    }

    println!("{} {}", ac, wa);
}


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

int main()
{
    string str1{'A', 'C', 'T', 'G'};
    char b;
    cin >> b;
    for (int i = 0; i < 4;i++){
        if(b==str1[i]){
            cout << str1[(i+2)%4] << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

// increment
#define rep_n(_1, _2, _3, NAME, ...) NAME
#define rep_2(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep_3(i, initial, n) for (int i = (int)(initial); i < (int)(n); ++i)
#define repeat(...) rep_n(__VA_ARGS__, rep_3, rep_2, rep_1)(__VA_ARGS__)
// decrement
#define rep_r_n(_1, _2, _3, NAME, ...) NAME
#define rep_r_2(i, n) for (int i = (int)(n); i > 0; i--)
#define rep_r_3(i, initial, n) for (int i = (int)(initial); i > (int)(n); i--)
#define repeat_r(...) rep_r_n(__VA_ARGS__, rep_r_3, rep_r_2)(__VA_ARGS__)
// define variable
using namespace std;
typedef long long ll;
using mpint = boost::multiprecision::cpp_int; // 多倍長整数（任意精度）
typedef pair<int, int> P;
const double EPS = numeric_limits<double>::epsilon();
const long long INF = (long long)1e18;
// 最大公約数
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
// 最小公倍数
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
// char -> int
int ctoi(char c) { return (int)(c - '0'); }

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

	double result = 0;
	double l = double(L) / 3.0;
	result = l * l * l;
	
	cout << fixed << setprecision(10) << result << endl;
	return 0;
}


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

using namespace std;

const int MAX=10000;
const int INFTY=(1<<21);
const int WHITE=0;
const int GRAY=1;
const int BLACK=2;

vector<pair<int, int> > adj[MAX];
int n;

void dijkstra(){
    priority_queue<pair<int, int> > PQ;
    int color[MAX],d[MAX];

    for(int i=0;i<n;i++){
        d[i]=INFTY;
        color[i]=WHITE;
    }

    d[0]=0;
    PQ.push(make_pair(0,0));
    color[0]=GRAY;

    while(!PQ.empty()){
        pair<int,int> f=PQ.top();PQ.pop();
        int u=f.second;
        color[u]=BLACK;

        if(d[u]<f.first*(-1)) continue;

        for(int j=0;j<adj[u].size();j++){
            int v=adj[u][j].first;
            if(color[v]==BLACK)continue;
            if (d[v]>d[u]+adj[u][j].second){
                d[v]=d[u]+adj[u][j].second;
                PQ.push(make_pair(d[v]*(-1),v));
                color[v]=GRAY;
            }

        }
    }

    for(int i=0;i<n;i++){
        cout<<i<<" "<<(d[i]==INFTY ? -1:d[i])<<endl;
    }

    return;
}

int main()
{
    cin>>n;
    int k,u,v,c;

    for(int i=0;i<n;i++){
        cin>>u>>k;
        for(int j=0;j<k;j++){
            cin>>v>>c;
            adj[u].push_back(make_pair(v,c));
        }
    }

    dijkstra();

}


Measured memory_bytes: 7992
#include<bits/stdc++.h>
#define pi acos(-1)
#define ll long long
#define pii pair<ll,ll>
#define debug(a) cout<<a<<'\n'
#define maxn 100009 /// Still trying to be normal
#define MOD 1000000007
#define F first
#define S second
#define rep(i, a, b) for(ll i = a; i < (b); ++i)
#define per(i, b, a) for(ll i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x), end(x)
#define sz(x) (ll)(x).size()
using namespace std;
const ll INF = 1e17 + 9;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    double r;
    cout<<fixed<<setprecision(3);
    cin>>r;
    cout<<r*pi*2<<'\n';
    return 0;   
}           
    

Measured memory_bytes: 3792
#include <bits/stdc++.h>
#define ri register
#define int long long
#define E (n+1)
using namespace std;
inline int read()
{
    int s=0, w=1; ri char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
    return s*w;
}
signed main()
{
    int X=read();
    if(X<7) puts("1");
    else
    {
        int res=0;
        res+=(X/11)*2, X%=11;
        res+=(X/10)*2, X%=10;
        res+=(X/9)*2, X%=9;
        res+=(X/8)*2, X%=8;
        res+=(X/7)*2, X%=7;
        if(X) res++;
        printf("%lld\n",res);
    }
    return 0;
}

Measured memory_bytes: 3716
N, D = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]

import math
ans = 0
for i in range(N):
    X1 = X[i]
    for X2 in X[i+1:]:
        if math.sqrt(sum([(x1-x2)**2 for x1, x2 in zip(X1, X2)])).is_integer():
            ans += 1
print(ans)

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

int main()
{
    long long int t;
    cin>>t;
    int check=1;
    while(t)
    {
        int x=t%10;
        if(x==7)
        {
            cout<<"Yes";
            check=0;
            break;
        }
        t=t/10;
    }
  if(check)
   cout<<"No";
    return 0;
}


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

int main() {
	int n;	ll k;	cin >> n >> k;
	vector<int> a(n);	rep(i,n){cin >> a.at(i);	a.at(i)--;}
	map<int,int> dc;	rep(i,n) dc[i] = a.at(i);
  	
  	int cnt = 0;	int rp = 0;
  	{
  		set<int> lg;
      	int pos = 0;
      	while(lg.count(pos) == 0){
        	lg.insert(pos);
          	pos = dc[pos];
          	cnt++;
        }
//      	cout << cnt << " " << pos;
    	rp = pos;
  	}
  	
  	int cnt2 = 0;
  	{
    	set<int> lg;
      	int pos = rp;
      	while(lg.count(pos) == 0){
        	lg.insert(pos);
          	pos = dc[pos];
          	cnt2++;
        }
//      	cout << cnt2 << endl;
    }
  	
  	if(k <= cnt){
      	int pos = 0;
    	rep(i,k) pos = dc[pos];
      	cout << pos+1 << endl;
    }
  	else{
    	int pos = rp;
      	int scnt = (k-cnt)%cnt2;
      	rep(i,scnt) pos = dc[pos];
      	cout << pos+1 << endl;
    }
}

Measured memory_bytes: 22684
#include "bits/stdc++.h"
#include "math.h"
#include "string.h"
#include "algorithm"
 
using namespace std;
typedef int64_t ll;
typedef vector<int64_t> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SIZE(a) int((a).size())
const int INF=INT_MAX;
ll factorial(int k){
    ll n=1;
    for(int i=1;i<=k;i++){
        n*=i;
    }
    return n;
}
int main(){
  int n;
  cin>>n;
  vector<string> a(n);
  REP(i,n){
    cin>>a[i];
    sort(a[i].begin(),a[i].end());
  }
  sort(a.begin(),a.end());
  vll ans(1,0);
  int j=0;
  REP(i,n-1){
    if(a[i]==a[i+1]){ans[j]++;}
    else{ans.push_back(0);j++;}
  }
  ll sum=0;
  REP(i,SIZE(ans)){
    if(ans[i]!=0){
      sum+=(ans[i]+1)*ans[i]/2;
    }
  }
  cout<<sum<<endl;
}



Measured memory_bytes: 8444
import scala.io.StdIn.readLine
import scala.collection.mutable.ArrayBuffer

object Main {
  def main(args:Array[String]) = {
    var s = "0 0"
    val b = new ArrayBuffer[String]
    while({s=readLine.trim;s} != "0 0") {
      val a = ("A",s.split(" ").map(_.toInt).sum) +: Array("B","C","D","E").map{i=>(i,readLine.split(" ").map(_.toInt).sum)}
      val max = a.maxBy(_._2)
      b += max._1 + " " + max._2
    }
    println(b.mkString("\n"))
  }
}

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

int main() {
  int X, Y, Z, K;
  cin >> X >> Y >> Z >> K;
  vector<long> A(X), B(Y), C(Z);
  for (auto &a : A) cin >> a;
  for (auto &b : B) cin >> b;
  for (auto &c : C) cin >> c;

  vector<long> AB;
  for (auto a : A) for (auto b : B) AB.push_back(a + b);
  sort(AB.rbegin(), AB.rend());

  vector<long> ABC;
  for (auto c : C) for (int i = 0; i < min(K, (int)AB.size()); i++) ABC.push_back(AB.at(i) + c);
  sort(ABC.rbegin(), ABC.rend());
  for (int i = 0; i < K; i++) cout << ABC.at(i) << "\n";
}

Measured memory_bytes: 43368
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>

using namespace std;

int main(){
	string s,t;
	cin >> s;
	int ans=1000;
	for(int i=0;i<s.size();i++){
		char tar = s[i];
		bool flag=1;
		for(int j=0;j<s.size();j++){
			if(s[j]!=tar){
				flag = 0;
			}
		}
		if(flag){
			ans = 0;
			break;
		}
		string t1,t2;
		t1 = s;
		int cou = 0;
		while(1){
			cou +=1;
			for(int j=0;j<t1.size()-1;j++){
				if(t1[j]==tar||t1[j+1]==tar){
					t2.push_back(tar);
				}else{
					t2.push_back(t1[j]);
				}
			}
			flag=1;
			for(int j=0;j<t2.size();j++){
				if(t2[j]!=tar){
					flag = 0;
				}
			}
			if(flag){
				ans = min(ans,cou);
				break;
			}
			t1 = t2;
			t2.clear();
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;

// 考える整数の最大値
const int MAX = 500000;
// 今回採用する大きい素数
const int MOD = 1000000007;

// メモを保管する場所
ll fact[MAX], inv_fact[MAX], inv[MAX];

// メモを計算する
void init() {
    // 初期値設定と1はじまりインデックスに直す
    fact[0] = 1;
    fact[1] = 1;
    inv[0] = 1;
    inv[1] = 1;
    inv_fact[0] = 1;
    inv_fact[1] = 1;
    // メモの計算
    repi(i, 2, MAX){
        // 階乗
        fact[i] = fact[i - 1] * i % MOD;
        // 逆元
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        // 逆元の階乗
        inv_fact[i] = inv_fact[i - 1] * inv[i] % MOD;
    }
}

// 二項係数の実体
ll nCk(int n, int k) {
    ll x = fact[n]; // n!の計算
    ll y = inv_fact[n-k]; // (n-k)!の計算
    ll z = inv_fact[k]; // k!の計算
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return x * ((y * z) % MOD) % MOD;
}


int main(){
  init();
  int N, M;
  cin >> N >> M;
  cout << nCk(N, 2) + nCk(M, 2) << endl;
}


Measured memory_bytes: 15304
#include <iostream>

using namespace std;

int n, k;
int v[200005];

int main()
{
    int x;

    cin >> n >> k;

    for(int i = 1 ; i <= n ; i++)
        cin >> v[i];

    for(int i = k  ; i < n ; i++)
        (v[i - k + 1] < v[i + 1]) ? cout << "Yes \n" : cout << "No \n";


}


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

ll mode(ll a,ll b)
{
	if(b==0)return 1;
	ll ans=1;
	while(b>0)
	{
		if(b&1)ans=(ans*a)%mod;
		b=b>>1;
		a=((a%mod)*(a%mod))%mod;
	}return ans;
}
ll com(ll m,ll r)
{
	ll fmr=1,fr=1,fm=1,exp,ans;
	ll i;
	for(i=1;i<=m;i++)
	{
		fm=(fm*i)%mod;
		if(i==r)fr=fm;
		if(i==m-r)fmr=fm;
	}
	exp=(fmr*fr)%mod;
	exp=mode(exp,mod-2);
	ans=(fm*exp)%mod;
	return ans;
}

int main()
{
	ll x,y;
	cin>>x>>y;
	ll m,r;
	double m1,r1;
	m=(x+y)/3;r=(2*x-y)/3;
	m1=float(x+y)/3;r1=float(2*x-y)/3;
	if(r<0)cout<<0;
	else if(r>m)cout<<0;
	else if(m!=m1||r!=r1)cout<<0;
	else if(m==0)cout<<0;
	else if(r==0)cout<<1;
	else
	{
		cout<<com(m,r);
	}
	
}

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

using namespace std;

const int inf = 2e9;

int main() {
    int n;
    cin >> n;
    vector<int> h(n);
    for (int i = 0; i < n; i++) cin >> h[i];

    vector<int> dp(n, inf);
    dp[0] = 0;
    for (int i = 1; i < n; i++) {
        for (int j = i - 1; j >= i - 2 && j >= 0; j--) {
            dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]));
        }
    }

    cout << dp[n - 1] << '\n';
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
string s;
int l;
int main(){
    cin>>s;
    l=s.size();
    for(register int i=0;i<l;i++){
        if(s[i]=='C'){
            for(register int j=i+1;j<l;j++){
                if(s[j]=='F'){
                    cout<<"Yes";
                    return 0;
                }
            }
        }
    }
    cout<<"No";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define fi first
#define se second
#define For(i,a,b) for(ll i=a;i<b;i++)
#define RFor(i,b,a) for(ll i = b;i>=a;i--)
#define sz size()
#define PQ priority_queue
#define len length()
#define mll map<ll,ll>
#define vll vector<ll>
#define sll set<ll>
#define vpll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define mp(x,y)  make_pair(x,y)
#define pb push_back
#define ins insert
#define er erase
#define pf push_front
#define ALL(v) v.begin(),v.end()
#define LAPAK ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;

const ll MOD = 1e9 + 7;
const ll INF = 2e18;
const ll MAX = 5001;

int main() {
    LAPAK
    ll n;
    cin>>n;
    cout<<n+(n*n) + (n*n*n);
    
    
    return 0;
}

Measured memory_bytes: 3636
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

// rep(i, 100) { cout << i << endl; } => 0 1 2 ... 99
#define rep(i, n) for(int i = 0, i##_len = (n); i < (int)n; i++)

// std::sort(all(v));
#define all(x) (x).begin(), (x).end()

// long long int
using ll = long long;

// utility to cast return value of size function to int
#define SZ(x) ((int)(x).size())

// VS defines "_DEBUG" macro when debug configuration.
#if _DEBUG
#define dump(x) cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#else
#define dump(x)
#define debug(x)
#endif

// update max
template<class T>bool chmax(T & prov, const T & cur)
{
	if (cur > prov)
	{
		prov = cur;
		return true;
	}
	return false;
}

// update min
template<class T>bool chmin(T & prov, const T & cur)
{
	if (cur < prov)
	{
		prov = cur;
		return true;
	}
	return false;
}

ll gcd(ll lhs, ll rhs)
{
	if (lhs == rhs)
	{
		return lhs;
	}
	else if (lhs < rhs)
	{
		swap(lhs, rhs);
	}

	gcd(lhs - rhs, rhs);
}

ll lcm(ll lhs, ll rhs)
{
	ll t = gcd(lhs, rhs);
	return (lhs / t) * (rhs / t) * t;
}

int main()
{
	ll A, B, C, D;
	cin >> A >> B >> C >> D;
	ll L = lcm(C, D);
	ll ans = B - (A-1);
	ans -= B / C - (A-1) / C;
	ans -= B / D - (A-1) / D;
	ans += B / L - (A-1) / L;

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


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

using namespace std;

const int MAX_N = 100000;
const double EPS = 1e-15;

double dp[MAX_N+1];

int main ( void )
{
	fill(dp, dp+MAX_N+1, 0);
	dp[1] = 1;
	for (int i = 2; i <= MAX_N; ++i) {
		double p = 1, hit = 0.5;
		for (int j = 1; j < i; ++j) {
			if (p < EPS) { break; }
			double miss = p * (1 - hit);
			dp[i] += miss * (j + dp[i-j-1]);
			p *= hit; hit *= 0.5;
		}
		dp[i] += i * p;
	}

	int n;

	while (cin >> n, n) {
		printf("%.15f\n", dp[n]);
	}

	return 0;
}

Measured memory_bytes: 1976
#include <iostream> // cout, endl, cin
#include <cmath>    //sin, cos, tan
#include <vector>   // vector
#include <iomanip>  //setprecsion
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
using namespace std;
const double PI = acos(-1.0);

int main(void)
{
  double r;
  cin >> r;
  cout << fixed << setprecision(6) << PI * r * r << " " << 2 * r * PI << endl;
  return 0;
}


Measured memory_bytes: 3288
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
long long dp[N][N], ans;
long long cons = 1e9+7;
int main()
{
    int n, m;
    char c[N][N];
    cin >> n >> m;
    for ( int i=0; i<n; i++){
    for (int j=0; j<m; j++) cin >> c[i][j];
    }
    for (int i=1; i<m; i++){
        if (c[0][i] == '#') break;
        dp[0][i]=1;
    }
      for (int i=1; i<n; i++){
        if (c[i][0] == '#') break;
        dp[i][0]=1;
    }
    for ( int i=1; i<m; i++){
        for (int j=1; j<n;j++){
                if (c[j][i] == '#') continue;
            dp[j][i]= (dp[j-1][i]+dp[j][i-1])%cons;
        }
    }
    ans = (dp[n-1][m-1]) %cons;
    cout << ans;
    return 0;
}


Measured memory_bytes: 9088
k,n=gets.split.map(&:to_i)
a=gets.split.map(&:to_i)
a.sort!
maxd=0
(0..(a.size()-2)).each{|i|
  d=(a[i+1]-a[i]).abs
  maxd=d if maxd<d
  }
d=(a[0]+k-a[-1]).abs
maxd=d if maxd<d
puts k-maxd

Measured memory_bytes: 17008
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
using namespace std;

typedef long long ll;

#define INF 10e17
#define rep(i,n) for(long long i=0; i<n; i++)
#define repr(i,n,m) for(long long i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<long long>())
#define debug(x) std::cerr << (x) << std::endl;
#define roll(x) for (auto&& itr : x) { debug(itr); }

template <class T> inline void chmax(T &ans, T t) { if (t > ans) ans = t;}
template <class T> inline void chmin(T &ans, T t) { if (t < ans) ans = t;}

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

    ll n;
    cin >> n;

    ll t = (n - 1) * n / 2;
    
    cout << t << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>



using namespace std;
int N,M,K,H,W,P[1000],ans;
bool point[301][301],link[301][301],xsw,zero;
char a[100][100],b[100000];
string A,B,C;


int abs(int x){
	if(x<0){
		return -x;
	}
	return x;
}

int min(int x,int y){
	if(x<y)return x;
	return y;
}
int max(int x,int y){
	if(x>y)return x;
	
	return y;
}

int main(){
	cin >> A>>B>>C;
	if(A[A.size()-1]==B[0]&&B[B.size()-1]==C[0]){
		cout<<"YES"<<endl;
	}else{
		cout<<"NO"<<endl;
	}


	return 0;
}


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

using namespace std;

class pos{
public:
  int x;
  int y;
};

class data{
public:
  int id;
  double dist;
  vector<bool> v;
  data(int in, int n);
  data(int in, int n, vector<bool> origin);
};

data::data(int in, int n){
  for(int i=0; i<n; i++){
    v.push_back(true);
  }
  v[in] = false;
  id = in;
  dist = 0;
}


data::data(int in, int n, vector<bool> origin){
  for(int i=0; i<n; i++){
   v.push_back(origin[i]); 
  }
  v[in] = false;
  id = in;
  dist = 0;
}

double calsqrt(pos src, pos dst){
  double ret = sqrt(pow((src.x - dst.x), 2) + pow((src.y - dst.y), 2));
  return ret;
}

int main(){
	
  int n;
  cin >> n;
  
  vector<pos> p(n);
  
  for(int i=0; i<n; i++){
  	cin >> p[i].x >> p[i].y;
  }
  
  
  double sum = 0;
  int cnt = 0;
  
  for(int sp=0; sp<n; sp++){
    int itr = 0;
    data srt(sp, n);
    vector<data> queue = {srt};
    while(itr < queue.size()){
      int nv = 0;
      for(int id=0; id<n; id++){
        if(queue[itr].v[id]){
          cerr << id << endl;
          nv++;
          data tmp(id, n, queue[itr].v);
          tmp.dist = queue[itr].dist + calsqrt(p[queue[itr].id], p[id]);
          queue.push_back(tmp);
        }
      }
      if(nv == 0){
          sum += queue[itr].dist;
          cnt ++;
      }
      itr++;
    } 
  }
  
  double ans = sum / cnt;
  printf("%.10lf\n", ans);
}


Measured memory_bytes: 2120
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define f(i,x,n) for(int i=x;i<n;i++)
#define all(c) c.begin(),c.end()
#define int ll
using ll = long long;
using pii = pair<int,int>;
const int MOD = 1e9+7, N = 1e5 + 10; 

int deg[N];
vector<int> g[N];
int n;
int parent[N];
int col[N];
int mx;

void dfs(int u,int p = -1,int c = -1){
   parent[u] = p;
   col[u] = c;
   int prv = c;
   for(auto &v : g[u]){
      if(v!=p){
         prv++;
         prv = prv%mx;
         if(c == prv){
            prv++;
         }
         prv = prv%mx;
         dfs(v,u,prv);
      }
   }
}

int32_t main(){
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   cin >> n;
   int u,v;
   vector<pii> edge(n-1);
   f(i,1,n){
      cin >> u >> v;
      g[u].pb(v);
      g[v].pb(u);
      edge[i-1] = {u,v};
      deg[u]++;
      deg[v]++;
      mx = max({mx,deg[u],deg[v]});
   }
   dfs(1);
   cout << mx << '\n';
   f(i,0,n-1){
      if(edge[i].F == parent[edge[i].S]){
         cout << col[edge[i].S]+1 << '\n';
      }else{
         cout << col[edge[i].F]+1 << '\n';
      }
   }
   return 0;
} 

Measured memory_bytes: 11392
# -*- coding: utf-8 -*-
"""
Created on Sun Aug  2 17:32:44 2020

@author: Paras
"""
import math

N,D = map(int, input().split())
count = 0
for i in range(N):
    X,Y = map(int, input().split())
    if math.sqrt(X**2+Y**2)<=D:
        count+=1
    
print(str(count))

Measured memory_bytes: 9184
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main()
{
  int N;
  cin >> N;
  vector<ll> A(N);
  REP(i, N)
  cin >> A[i];
  multiset<ll> st; // 重複OKなset
  REP(i, N)
  st.insert(A[i]);
  int ans = 0;
  while (!st.empty())
  {
    ll x = *st.rbegin();  // stの中で最も大きい要素
    st.erase(st.find(x)); // st.erase(x)だと要素xが2個以上あった場合にそれらが全部消えてしまう
    ll z = 1;
    while (z <= x)
      z *= 2;
    ll y = z - x;               // x + y = z(zは2べき)
    if (st.find(y) != st.end()) // xのペアとなるyが見つかった場合
    {
      st.erase(st.find(y));
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 11136
a_price, b_price, ab_price, a_num, b_num = map(int, input().split())
if a_num >= b_num:
  amari_price = a_price
else:
  amari_price = b_price
min_price = float('inf')
price1 = a_price*a_num+b_price*b_num
price2 = min(a_num,b_num)*ab_price*2 + abs(a_num-b_num)*amari_price
price3 = max(a_num,b_num)*ab_price*2
print(min(price1,price2,price3))

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

using namespace std;

#define int long long

const int N = 2e5 + 10;

int a[N];

int32_t main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);    
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    int mn = a[0];
    vector<int> v;
    if (a[1] > a[0]) v.push_back(a[0]);
    for (int i = 1; i < n; ++i)
    {
        if (a[i] > a[i - 1])
        {
            while (i < n && a[i] >= a[i - 1]) ++i;
            --i;
            v.push_back(a[i]);
        }
        else 
        {
            while (i < n && a[i] <= a[i - 1]) ++i;
            --i;
            v.push_back(a[i]);
        }
    }
    int ans = 1000;
    int cost = 1000;
    int stock = 0;
    if (v.size() > 1)
    {
        for (int i = 0; i < v.size(); ++i)
        {
            if (i & 1)
            {
                cost += stock * v[i]; 
                stock = 0;
            }
            else
            {
                stock += cost / v[i];
                cost %= v[i];
            }
            ans = max(ans, cost);
        }
    }
    cout << ans;
    return 0;
}

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

int getnum(string &s, int l, int x, int i) {
  char c;
  if (i>=l) return 0;
  c = s.at(l-i-1);
  if (c=='X') {
    return x;
  } else {
    return c-'0';
  }
}

int main() {
  int a, b, c, i, m, s, t, u, v, w, x;
  bool nonzero;
  string eq;
  string l1, l2, r;
  while (getline(cin, eq)) {
    a = eq.find("+");
    b = eq.find("=");
    c = eq.length();
    l1 = eq.substr(0, a);
    l2 = eq.substr(a+1, b-a-1);
    r = eq.substr(b+1, c-b);
    a = l1.length();
    b = l2.length();
    c = r.length();
    m = max(max(a,b),c);
    if ((a>1&&l1[0]=='X')||(b>1&&l2[0]=='X')||(c>1&&r[0]=='X')) {
      nonzero = true;
    } else {
      nonzero = false;
    }
    for (x=0; x<10; x++) {
      v = 0;
      for (i=0; i<=m; i++) {
        s = getnum(l1, a, x, i);
        t = getnum(l2, b, x, i);
        u = getnum(r, c, x, i);
        w = s + t + v;
        if (w >= 10) {
          w -= 10;
          v = 1;
        } else {
          v = 0;
        }
        if (w != u) break;
      }
      if (i>m) break;
    }
    if (x==10 || (!x && nonzero)) {
      cout << "NA" << endl;
    } else {
      cout << x << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1180
number = gets.to_i
divi = [1, 6, 9, 6**2, 9**2, 6**3, 9**3, 6**4, 9**4, 6**5, 6**6, 9**5]
dp = Array.new(12).map{Array.new(number + 1, 10**7)}
for i in 0..11
  dp[i][0] = 0
end
for i in 1..number
  dp[0][i] = i
end

for i in 1..11
  for j in 1..number
    if (j >= divi[i]) && (dp[i - 1][j] > (dp[i][j - divi[i]] + 1))
      dp[i][j] = dp[i][j - divi[i]] + 1
    else
      dp[i][j] = dp[i - 1][j]
    end
  end
end

print dp[11][number]


Measured memory_bytes: 13180
#include<iostream>
#include<algorithm>
#include<climits>
#include<vector>
#include<utility>//pair
#include<cmath>//abs,sqrt
#include<cstring>
#include<map>
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define prin(arg) std::cout<<arg<<"\n"
#define prin2(arg1,arg2) std::cout<<arg1<<" "<<arg2<<"\n"
#define fill(arg,n) memset(arg,n,sizeof(arg))
typedef long long ll;
const int INF=1e+9;
const ll INFLL=1e+17;
using std::cin;
ll n;
ll a[100010];
ll p[100010];
ll sum[100010];
void parity(ll x){
  rep(i,n){
    if(a[i]<=x) p[i]=1;
    else p[i]=-1;
  }
}
void cumadd(){
  sum[0]=0;
  rep1(i,n) sum[i]=sum[i-1]+p[i-1];
  rep(i,n+1) sum[i]+=n;
}
template <class X>
class BIT{
  X bit[200010];
  ll n;
 public:
  BIT(ll N);
  ll sum(ll i);
  void add(ll i,ll x);
};
template <class X>
BIT<X>::BIT(ll N){
  n=N;
  for(ll i=0;i<N;i++){
    bit[i]=0;
  }
}
template <class X>
ll BIT<X>::sum(ll i){//iまでの和
  X s=0;
  while(i>0){
    s+=bit[i];
    i-=i&(-i);//最後の1bitを引く(ex.0110なら0010を引く)
  }
  return s;
}
template <class X>
void BIT<X>::add(ll i,ll x){
  while(i<=n){
    bit[i]+=x;
    i+=i&(-i);//最後の1bitを足す
  }
}
ll inv(ll x){
  ll res=0;
  parity(x);
  cumadd();
  BIT<ll> b(200010);
  rep(i,n+1){
    res+=b.sum(sum[i]-1);
    b.add(sum[i],1);
  }
  return res;
}
bool C(ll x){
  return inv(x)>n*(n+1)/4;
}
ll bina(ll min,ll max){
  ll lb=min-1,ub=max+1;
  while(ub-lb>1){
    ll mid=(ub+lb)/2;
    if(C(mid)) ub=mid;
    else lb=mid;
  }
  return ub;
}
int main(){
  cin>>n;
  ll max=0,min=1e+9+1;
  rep(i,n){
    cin>>a[i];
    max=std::max(max,a[i]);
    min=std::min(min,a[i]);
  }
  prin(bina(min,max));
  return 0;
}


Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int  main(){
    int x,y,flag=0;
    cin >> x >> y;
    rep(i,x+1){
        if(i*2+(x-i)*4==y) flag = 1;
    }
    if(flag) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 3588
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node {
    int key;
    struct node *prev;
    struct node *next;
} Node;

Node *nil;  // 番兵
 
void init() {
    nil = (Node *)malloc(sizeof(Node));
    nil->next = nil;
    nil->prev = nil;
}

// 双方向リストへの要素の挿入
void insert(int key) {
    Node *x = (Node *)malloc(sizeof(Node));
    x->key = key;

    // 番兵の直後に要素を追加
    x->next = nil->next;
    nil->next->prev = x;
    nil->next = x;
    x->prev = nil;
}

// 双方向リストの要素の探索
Node* listSearch(int key) {
    Node *cur = nil->next;   // 番兵の次の要素から辿る
    while (cur != nil && cur->key != key) {
        cur = cur->next;
    }
    return cur;
}

// 双方向リストの要素の削除
void deleteNode(Node *t) {
    if (t == nil) return;  // tが番兵の場合は処理しない
    t->prev->next = t->next;
    t->next->prev = t->prev;
    free(t);
}

void deleteFirst() {
    deleteNode(nil->next);
}

void deleteLast() {
    deleteNode(nil->prev);
}

void deleteKey(int key) {
    // 探索したノードを削除
    deleteNode(listSearch(key));
}

void printList() {
    Node *cur = nil->next;
    int count = 0;

    while(1) {
        if (cur == nil) break;
        if (count++ > 0) printf(" ");
        printf("%d", cur->key);
        cur = cur->next;
    }
    printf("\n");
 }

int main(void)
{

    int n, key, i;
    char command[100];

    init();

    scanf("%d", &n);

    i = 0;
    while(i < n) {
        scanf("%s %d", &command, &key);

        // 入力されたコマンドとキーでポインタを操作
        if (command[0] == 'i') {
            insert(key);
        } else if (command[0] == 'd') {
            if (command[6] == 'F') {
                deleteFirst();
            } else if (command[6] == 'L') {
                deleteLast();
            } else {
                deleteKey(key);
            }
        }
        i++;
    }

    printList();
 
    return 0;
}


Measured memory_bytes: 32984
#include <bits/stdc++.h>
typedef long long ll;
#define REP(i,n) for(int i=0;i<n;i++)
#define ALL(x) (x).begin(),(x).end()
using namespace std;

//素因数分解
vector<pair<ll,int>> factorize(ll n){
    vector<pair<ll,int>>res;
    for(ll i=2;i*i<=n;i++){
        if(n%i)continue;
        res.emplace_back(i,0);
        while (n%i == 0)
        {
        n /= i;
        res.back().second++;
        }
        
    }
    if(n != 1) res.emplace_back(n,1);
    return res;
}

void trace(int A[],int N){
    REP(i,N){
        if(i>0)printf(" ");
        printf("%d",A[i]);
    }
    printf("\n");
}


int main(){
    int A,B,C;
    cin >> A >> B >> C;
    int S[3] = {A,B,C};
    sort(S,S+3);
    if(S[0]+S[1]==S[2])puts("Yes");
    else puts("No");
}


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

#define rep_(v, f, l) for (int v = (f), v##_ = (l); v < v##_; ++v)
#define rep(v, n) rep_(v, 0, n)
#define lep(v, n) rep_(v, 1, n + 1)
#define rrep_(v, f, l) for (int v = (l), v##_ = (f); v >= v##_; --v)
#define rrep(v, n) rrep_(v, 0, n - 1)
#define rlep(v, n) rrep_(v, 1, n)
#define show_a(a, size) rep(a##_it, size) std::cout << a[a##_it] << " \n"[a##_it == a##_it_ - 1];
#define show_v(v) show_a(v, v.size())
#define eachv(v, i) rep(i, v.size())
#define reachv(v, i) rrep(i, v.size())
#define debug(x) std::cerr << #x << " = " << x << "\n";

using namespace std;

typedef long long int lint;

static inline int in(){ int x; scanf("%d", &x); return x; }
static inline lint inl(){ lint x; scanf("%lld", &x); return x; }

int main()
{
    int t;
    while (t = in()){
        int n = in();
        int total_time = 0;
        rep(i, n) total_time += abs(in() - in());
        if (total_time < t) printf("%d\n", t - total_time);
        else puts("OK");
    }

    return (0);
}

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

using namespace std;

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)

#define P pair<lli,lli>

lli a[300][300];

signed main(){

	lli h,w;
	cin>>h>>w;

	lli data[10][10];
	REP(i,0,10)REP(j,0,10)cin>>data[i][j];

	REP(k,0,10)REP(i,0,10)REP(j,0,10)data[i][j]=min(data[i][j],data[i][k]+data[k][j]);

	lli cost=0;
	REP(i,0,h)REP(j,0,w){
		cin>>a[i][j];
		if(a[i][j]==-1)continue;
		cost += data[a[i][j]][1];
	}
	cout<<cost<<endl;

	return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
using namespace std;
typedef long long int ll;
typedef long double ld;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
 
typedef pair<ll,ll> pairs;
vector<pairs> p;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
#define MAX_N 1000100
bool x[MAX_N];
ll num[MAX_N];
ll fibl[MAX_N]={0};
 
ll fib(ll a){
    if (fibl[a]!=0)return fibl[a];
    if (a==0){
        return 0;
    }else if (a==1){
        return 1;
    }
    return fibl[a]=fib(a-1)+fib(a-2);
}
 
ll eratosthenes(ll n) {
    int p = 0;
    for (ll i=0; i<=n; ++i) x[i] = true;
    x[0] = x[1] = false;
    for(int i=2; i<=n; ++i) {
        if(x[i]) {
            p++;
            for(int j=2*i; j<=n; j+=i) x[j] = false;
        }
        
        num[i] = p;
    }
    return p;
}
 
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}
 
ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

int main(){
    ll a[3];
    cin >> a[0] >> a[1] >> a[2];
    if (a[2]%2==0 or a[1]%2==0 or a[0]%2==0){
        cout << 0 << endl;
        return 0;
    }
    sort(a,a+3);
    cout << a[0]*a[1] << endl;
    return 0;
}


Measured memory_bytes: 256
# N = int(input())
# D = list(map(int, input().split()))
# count = [0] * N
# ans = 1
# if (D[0] != 0 or count[0] >= 2):
#     print(0)
#     exit()
# for d in D:
#     count[d] += 1
# for i in range(N):
#     if (i > 0):
#         ans *= (count[i - 1] ** count[i]) % 998244353
#         ans %= 998244353

# print(ans)


# from collections import Counter
N = int(input())
D = list(map(int, input().split()))
MOD = 998244353

# 厳密にはmax(D)+1の長さがあれば正常系は通るが、余分に取っておく
count = [0] * N
for d in D:
    count[d] += 1

# def calc():
if D[0] != 0 or count[0] >= 2:
    print(0)
    exit()
ret = 1
for i in range(N):
    if i > 0:
        ret *= (count[i-1] ** count[i]) % MOD
        ret %= MOD
print(ret)


Measured memory_bytes: 14396
#include <stdio.h>

int main(void){
    int a, b, c;
    
    a = 0;
    b = 0;
    c = 0;
    
    
    scanf("%d", &a);
   
    scanf("%d", &b);
   
    scanf("%d", &c);
    
    int num, numAB, numBC, numAC;
    num = 0;
    numAB = 0;
    numBC = 0;
    numAC = 0;
    
    numAB = a + b;
    numBC = b + c;
    numAC = a + c;
    
    
    num = numAB;
    if(num > numAC){
        num = numAC;
    }
    if(num > numBC){
        num = numBC;
    }
    
    printf("%d",num);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
using namespace std;
int main(void){
    int len, ans = 0, b = 1;
    string s;
    cin >> s;
    len = s.length();
    for(int i=0;i<len;i++){
        if(b == 2){
            ans++;
            b = 1;
            continue;
        }
        if(i == 0 || s[i] != s[i-1]){
            ans++;
        }else{
            if(i == len-1)break;
            ans++;
            b = 2;
            i++;
        }
    }
    cout << ans << endl;
}


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

int main()
{
	int N, M, P;
	scanf("%d%d%d", &N, &M, &P);
	using vpi = std::vector<std::pair<int, int64_t>>;
	using vi = std::vector<int>;
	std::vector<vpi> edges(N);
	std::vector<vi> rev_edges(N);
	for (int i{}; i < M; i++)
	{
		int A, B, C;
		scanf("%d%d%d", &A, &B, &C);
		A--; B--;
		edges[A].push_back({B, C - P});
		rev_edges[B].push_back(A);
	}
	std::vector<int64_t> distance(N, -(1ll << 60));
	distance[0] = 0;
	for (int loop{}; loop < N; loop++)
		for (int i{}; i < N; i++)
			if (distance[i] != -(1ll << 60))
				for (auto& e: edges[i])
					distance[e.first] = std::max(distance[e.first], distance[i] + e.second);
	std::vector<int64_t> check{distance};
	for (int loop{}; loop < N; loop++)
		for (int i{}; i < N; i++)
			if (distance[i] != -(1ll << 60))
				for (auto& e: edges[i])
					if (distance[e.first] < distance[i] + e.second)
						distance[e.first] = 1ll << 60;
	if (distance[N - 1] == (1ll << 60))
		puts("-1");
	else
		printf("%lld\n", std::max(0l, distance[N - 1]));

	return 0;
}

Measured memory_bytes: 640
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

#define MOD 1000000007

int main() {
  int n;
  cin >> n;
  cout << (n + 1) / 2 << endl;
  return 0;
}

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

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll a,v,b,w,t;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>a>>v>>b>>w>>t;
    if(a<b)
    {
        a+=v*t;
        b+=w*t;
        if(a>=b)
            cout<<"YES";
        else
            cout<<"NO";
        return 0;
    }
    else if(a==b)
    {
        cout<<"YES";
        return 0;
    }
    else if(a>b)
    {
        a-=v*t;
        b-=w*t;
        if(a<=b)
            cout<<"YES";
        else
            cout<<"NO";
        return 0;
    }
    return 0;
}


Measured memory_bytes: 3500
#include <bits/stdc++.h>
   
using namespace std;
#define ll long long
#define ld long double
#define pll pair<long long,long long>
#define vll vector<long long>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define deb(x) cout << #x << "=" << x << endl
#define F(i,a,b) for(ll i=a;i<=b;i++)
#define RF(i,a,b) for(ll i=a;i>=b;i--)
#define in(a,n) F(i,0,n-1)cin>>a[i]
#define vi vector<int>
#define out(a,n) F(i,0,n-1)cout<<a[i]<<" ";cout<<endl
#define mod 1000000007
#define int long long
set < ll> primes;
 
int n,m;

bool isvalid(int x,int y)
{
    return (x>=0 && x<n && y>=0 && y<m);
}
int dx[]={0,0,1,-1,-1,1,1,-1};
int dy[]={1,-1,0,0,-1,1,-1,1};
void Sieve(ll n) 
{ 
    bool prime[n+1];
	for(ll i=0;i<n+1;++i)
		prime[i]=true;
    for (ll p=2;p*p<=n;++p) 
    {
        if (prime[p] == true) 
        {  
            for (ll i=2*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    }  
    for(ll p=2; p<=n; p++) 
       if (prime[p]) 
		primes.insert(p);  
}

ll gcd(ll a, ll b) 
{ 
    if (a == 0) 
        return b; 
        return gcd(b % a, a); 
} 
ll powermod(ll x, ll y){
    if(y==0)
    return 1;
        
    if(y%2==0)
    return (powermod(x,y/2)*powermod(x,y/2))%mod;
    else
    return (((powermod(x,y/2)*powermod(x,y/2))%mod)*x)%mod;
}

 
 

int32_t main()
{
	ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    
    int x;
    cin>>x;
    int sub=(x/500);
    int ans= (x/500)*(1000);
    int rem=x-sub*500;
    //24
    
    ans+=(rem/5)*5;
    cout<<ans;
   
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		int[] b = new int[n];
		int[] c = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
			b[i] = sc.nextInt();
			c[i] = sc.nextInt();
		}
		sc.close();

		int[][] dp = new int[n][3];
		dp[0][0] = a[0];
		dp[0][1] = b[0];
		dp[0][2] = c[0];
		for (int i = 1; i < n; i++) {
			dp[i][0] = Math.max(dp[i - 1][1], dp[i - 1][2]) + a[i];
			dp[i][1] = Math.max(dp[i - 1][2], dp[i - 1][0]) + b[i];
			dp[i][2] = Math.max(dp[i - 1][0], dp[i - 1][1]) + c[i];
		}
		int ans = dp[n - 1][0];
		ans = Math.max(ans, dp[n - 1][1]);
		ans = Math.max(ans, dp[n - 1][2]);
		System.out.println(ans);
	}
}


Measured memory_bytes: 97872
x, y = [int(_) for _ in input().split(' ')]

M = int(1e9+7)

def modpow(a, n):
    if n == 0:
        return 1
    elif n == 1:
        return a
    elif n % 2 == 0:
        tmp = modpow(a, n // 2)
        return (tmp * tmp) % M
    else:
        tmp = modpow(a, n // 2)
        return (tmp * tmp * a) % M

def modinv(a):
    return modpow(a, M - 2)

if (x + y) % 3 == 0:
    a, b = (-x + 2 * y) // 3, (2 * x - y) // 3

    if a >= 0 and b >= 0:
        f = [1] * (a + b + 1)
        for i in range(1, a + b + 1):
            f[i] = f[i - 1] * i % M

        answer = (f[a + b] * modinv(f[a]) * modinv(f[b])) % M
        print(answer)
    else:
        print(0)
else:
    print(0)


Measured memory_bytes: 29428
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
using namespace std;

typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;

#define f first
#define se second
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define pi pair<int, int>
#define all(x) x.begin(), x.end()
#define lp(i, n) for (int i = 0; i < n; i++)
#define mem(a, v) memset(a, v, sizeof(a))
#define X real()
#define Y imag()
#define angle(a) (atan2(a.Y, a.X))
#define vec(a, b) ((b) - (a))
//#define length(a) (hypot(a.Y , a.X))
#define normalize(a) (a) / length(a)
#define dotP(a, b) ((conj(a) * b).X)
#define crossP(a, b) ((conj(a) * b).Y)
#define same(p1, p2) (dotP(vec(p1, p2), vec(p1, p2)) < EPS)
#define lengthSqr(a) dotP(a, a)
#define rotate0(p, ang) ((p)*exp(point(0, ang)))
#define rotateA(p, ang, about) (rotate0(vec(about, p), ang) + about)
#define reflect0(v, m) conj(v / m) * m
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
const double PI = acos(-1.0);
const double EPS = (1e-10);
const long long int INF = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
typedef long long int ll;
typedef unsigned long long ull;
typedef complex<double> point;
long long fastpow(ll n, ll x) {
  if (!x)
    return 1;
  if (x % 2)
    return n * fastpow(n, x - 1);
  ll p = fastpow(n, x / 2);
  p %= mod;
  p *= p;
  p %= mod;
  return p;
}

ll my_mod(ll num, ll mod) {
  ll ret = num % mod;
  while (ret < 0)
    ret += mod;
  return ret;
}

ll gcd(ll a, ll b) { return !a ? b : gcd(b % a, a); }
long double dist(pair<ll, ll> &a, pair<ll, ll> &b) {
  return sqrt(
      ((a.f - b.f) * (a.f - b.f) * 1.0 + (a.se - b.se) * (a.se - b.se)));
}
/*vector<int> ap;
bool np[MX];
void s(){
    mem(np , 1);
    np[1] = np[0] = 0;
    for(ll i = 2 ; i*i<= MX ;i++){
        if(np[i]){
            for(ll j= i*i ; j <MX; j+=i) np[j] = 0;
        }
    }
    for(ll i = 2 ; i< MX ; i++) if(np[i]) ap.pb(i);
}*/
const ll MX = 1e5+5;
vector<int> adj[MX];
int v[MX];
int dp[MX];
template<typename T> void max_self(T &a , T b){
	a = max(a,b);
}
void dfs(int curr){
	v[curr] = 1;
	dp[curr] = 0;
	
	for(int i : adj[curr]){
		if(!v[i])dfs(i);
		max_self(dp[curr],dp[i]);
	}
	dp[curr]++;
	return;
}
int main()
{
    IO;
    int n,m;
    cin>>n>>m;
    for(int i = 0 ; i< m ;i++){
		int a,b;
		cin>>a>>b;
		adj[a].pb(b);
	}
	for(int i = 1 ; i<= n ;i++){
		if(!v[i])dfs(i);
	}
	int ans = 1;
	for(int i = 1; i<= n ;i++){
		//cout<<dp[i]<<"\n";
		max_self(ans, dp[i]);
	}
    cout<<ans-1<<"\n";
    
    return 0;
}



Measured memory_bytes: 8576
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

	Scanner sc;

	static final int INF=1<<28;
	static final double EPS=1e-9;

	void run(){
		sc=new Scanner(System.in);
		for(;;){
			int m=sc.nextInt();
			int d=sc.nextInt();
			if(m==0&&d==0)
				break;
			Calendar cal=Calendar.getInstance();
			cal.set(2004, m-1, d);
			switch(cal.get(Calendar.DAY_OF_WEEK)){
			case Calendar.MONDAY:
				println("Monday");
				break;
			case Calendar.TUESDAY:
				println("Tuesday");
				break;
			case Calendar.WEDNESDAY:
				println("Wednesday");
				break;
			case Calendar.THURSDAY:
				println("Thursday");
				break;
			case Calendar.FRIDAY:
				println("Friday");
				break;
			case Calendar.SATURDAY:
				println("Saturday");
				break;
			case Calendar.SUNDAY:
				println("Sunday");
				break;
			}
		}
		sc.close();
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		new Main().run();
	}
}

Measured memory_bytes: 12000
#include <iostream>
#include <string>

using namespace std;

int main()
{
  string str("END OF INPUT");
  int size;

  while(1){
    size = 0;
    string v;
    getline(cin,v);

    if(v == str){
      break;
    }

    for(char e : v){
      if(e == ' '){
        cout<<size;
        size = 0;
      }
      else{
        size++;
      }
    }
    cout<<size<<endl;
  }
  return 0;
}

Measured memory_bytes: 3012
#include<bits/stdc++.h>
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef tuple<ll,ll,ll> tl;
ll mod=1000000007;
ll mod2=998244353;
ll mod3=1000003;
ll mod4=998244853;
ll inf=1000000000000000000;
double pi=acos(-1.0);
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define rrep(i,n,m) for(ll i=n;i>=m;i--)
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
ll lmax(ll a,ll b){
    if(a<b)return b;
    else return a;
}
ll lmin(ll a,ll b){
    if(a<b)return a;
    else return b;
}
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(b==0)return a;
    if(a%b==0)return b;
    return gcd(b,a%b);
}
ll Pow(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k&1)ret*=now;
        now*=now;
        k/=2;
    }
    return ret;
}
ll beki(ll n,ll k,ll md){
  ll ret=1;
  ll now=n;
  while(k>0){
    if(k%2==1){
      ret*=now;
      ret%=md;
    }
    now*=now;
    now%=md;
    k/=2;
  }
  return ret;
}
ll gyaku(ll n,ll md){
  return beki(n,md-2,md);
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    ll n;cin>>n;
    ll aa;cin>>aa;
    vector<ll> v;
    v.push_back(aa);
    rep(i,0,n-1){
        char c;cin>>c;
        ll a;cin>>a;
        if(c=='+')v.push_back(a);
        else v.push_back(-a);
    }
    ll c=0;
    vector<ll> w;
    rep(i,0,n){
        if(v[i]<0)w.push_back(i);
    }
    ll sum[n+1];
    ll summ[n+1];
    sum[0]=0;
    summ[0]=0;
    rep(i,0,n){
        sum[i+1]=sum[i]+v[i];
        summ[i+1]=summ[i]+abs(v[i]);
    }
    ll ans=sum[n];
    if(w.size()==0){
        cout<<ans<<endl;
        return 0;
    }
    rep(i,0,w.size()-1){
        ll num=w[i];
        ll cnt=sum[num+1];
        cnt+=-(summ[w[i+1]]-summ[w[i]+1]);
        cnt+=summ[n]-summ[w[i+1]];
        ans=max(ans,cnt);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3572
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
VI a;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in n;
  cin>>n;
  a.resize(n+3,0);
  forn(i,n)
    cin>>a[i+1];
  in sm=0;
  forn(i,sz(a)-1){
    sm+=a[i]/2;
    a[i]%=2;
    if(a[i] && a[i+1]){
      --a[i];
      --a[i+1];
      ++sm;
    }
  }
  cout<<sm<<endl;
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>

using namespace std ;

typedef long long LL;

LL f(LL n,LL N,bool b3,bool b5,bool b7){
    if(n==0){
        return f(n*10+3,N,true,b5,b7)+f(n*10+5,N,b3,true,b7)+f(n*10+7,N,b3,b5,true);
    }
    if(n<=N){
        if(b3 && b5 && b7){
            return 1+f(n*10+3,N,true,b5,b7)+f(n*10+5,N,b3,true,b7)+f(n*10+7,N,b3,b5,true);
        }else return f(n*10+3,N,true,b5,b7)+f(n*10+5,N,b3,true,b7)+f(n*10+7,N,b3,b5,true);
    }

    return 0;
}

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

    

    cout << f(0,N,0,0,0) <<endl;
    return 0;
}



Measured memory_bytes: 384
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int oddCount = 0;
		for (int i = 0; i < n; i++) {
			int a = sc.nextInt();
			if (a % 2 == 1) {
				oddCount++;
			}
		}
		if (oddCount % 2 == 0) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
}


Measured memory_bytes: 49624