akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
using namespace std;
int main()
{ int n,m;
 cin>>n>>m;
  int a[n],sum=0;

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

  for(int i=0;i<n;i++)
  {   sum+=a[i];
  }
 float k=sum/(4.0*m);

 int count=0;
  for(int i=0;i<n;i++)
  {   if(a[i]>=k)
        {
         count++;
        }
  }

 if(count>=m)
 {cout<<"Yes ";}
 else if(count<m)
 {
     cout<<"No";
 }
}


Measured memory_bytes: 256
package main

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

func main() {
	sc := NewScanner()

	A := sc.NextInt()
	B := sc.NextInt()
	C := sc.NextInt()

	matrix := make([][]int, 3)
	for i := 0; i < 3; i++ {
		matrix[i] = make([]int, 3)
		for j := 0; j < 3; j++ {
			matrix[i][j] = -100
		}
	}

	matrix[0][0] = A
	matrix[0][1] = B
	matrix[1][1] = C

	k := 0
	for k = -1000; k <= 1000; k++ {

		S := A + B + k

		matrix[0][2] = k

		matrix[2][2] = S - (A + C)

		matrix[1][2] = S - (matrix[0][2] + matrix[2][2])

		matrix[1][0] = S - (matrix[1][1] + matrix[1][2])

		matrix[2][0] = S - (matrix[0][0] + matrix[1][0])

		matrix[2][1] = S - (matrix[0][1] + matrix[1][1])

		if matrix[2][0] + matrix[1][1] + matrix[0][2] == S {
			break
		}

	}
	for i := 0; i < 3; i++ {
		ans := strconv.Itoa(matrix[i][0])
		for j := 1; j < 3; j++ {
			ans += " "
			ans += strconv.Itoa(matrix[i][j])
		}
		fmt.Println(ans)
	}
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r:rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			result = append(result, v)
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	result = append(result, v)

	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}




Measured memory_bytes: 640
//g++ t.cpp -o t && t < p.txt
//d>p.txt&&t<p.txt&&t2<p.txt

#include <iostream> // プログラムの耳と口
#include <vector> // 超有能配列秘書
#include <algorithm> // みんな大好きソートと二分探索
#include <queue> // きゅーちゃん、だいすき
#include <string> // to_string
#include <functional> // 関数を変数に入れる子
#include <set> // 値の取得・挿入・削除を高速に
#include <map> // setの妹 これまた優秀
#include <random> // 乱択さん
#include <ctime>
#include <bitset>

#define DB cerr<<"D"<<endl
using namespace std; using ll=long long; using ld=long double; const int INF=1e9; const ll LINF=1e18; const double dINF = 1e18; const ld ldINF = 1e18; const double EPS = 1e-6;
template<typename T, typename U, typename O> void caut(T a, U b, O c){cout<<"("<<a<<","<<b<<","<<c<<") ";} template<typename T, typename U> void caut(T a, U b){cout<<"("<<a<<","<<b<<") ";} template<typename T> void caut(T a){cout<<"("<<a<<") ";};
using P=pair<ll,ll>;
const ll M = 1e9+7;
ll mod_pow(ll x, ll a) { ll an = 1; while(a > 0) { if (a&1) an = an * x % M; x = x * x % M; a >>= 1;} return an;}
void add(ll& x, ll y) {x+=y; x%=M;}; void mul(ll& x, ll y) {x*=y; x%=M;}; template<typename T, typename U> void chmax(T& x, U y) {if (x<y) x=y;}; template<typename T, typename U> void chmin(T& x, U y) {if (x>y) x=y;}
bool vaild(int x, int y, int hh, int ww){return 0<=x&&x<hh&&0<=y&&y<ww;}
int keta(ll a) {int res=0; while(a>0) res+=a%10, a/=10; return res;}
const int up[]={1,-1,0,0}, lf[]={0,0,1,-1};

struct unf {
  vector<int> v; unf(int n){v.resize(n); for(int i=0;i<n;i++) v[i]=i;}
  int root(int x) { if (v[x]==x) return x; return v[x]=root(v[x]);}
  void unite(int x,int y) {int p=root(x), q=root(y); if (p==q) return; v[p]=q;}
  bool same(int x, int y) {return root(x)==root(y);}
  void print() {for(int x:v) cout<<x<<" "; cout<<endl;}
};

int main() {
  int n,m; cin>>n>>m; unf u(n);
  for(int i=0;i<m;i++) {
    int a,b; cin>>a>>b; a--; b--; u.unite(a,b);
  }
  int an = 0; int p[n]={};
  for(int i=0;i<n;i++) {
    p[u.root(i)]++;
  }
  for(int i=0;i<n;i++) {
    chmax(an,p[i]);
  }
  cout<<an<<endl;
}
// ・配列の大きさok？　・priority_queueはgreater？　・debug消した？
// ・落ち着いて。提出まで4分待ってね……WJ……1/10……2/10……

// Thank you for making problems and running the contest


Measured memory_bytes: 11084
#include <iostream>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <list>
#include <array>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <random>
#include <chrono>
#include <fstream>

#define PI 3.14159265359
#define mt make_tuple
#define mp make_pair
#define pii pair <int, int>
#define pll pair <long long, long long>
#define all(x) (x).begin(), (x).end()

//mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());

using namespace std;

int main()
{
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	long long answer = -(1LL << 60);
	if (a <= 0 && 0 <= b)
		answer = 0;
	if (c <= 0 && 0 <= d)
		answer = 0;
	answer = max(answer, 1LL * a * c);
	answer = max(answer, 1LL * a * d);
	answer = max(answer, 1LL * b * c);
	answer = max(answer, 1LL * b * d);
	cout << answer << "\n";
	return 0;
}



Measured memory_bytes: 3196
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main() {
    ll x;
    cin >> x;
    if (x % 2 == 1){
        cout << 0 << endl;
        return 0;
    }
    ll ans = 0;
    x /= 2;
    while (x >= 5){
        ans += x / 5;
        x /= 5;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
n,m=map(int,input().split())
a=list(map(int,input().split()))
def func(n):
  ret=0
  n=n/2
  while n.is_integer():
    ret+=1
    n=n/2
  return ret
b=func(a[0])
for i in range(1,n):
  if b==func(a[i]):
    continue
  else:
    print(0)
    exit(0)
from fractions import gcd
lcmn=a[0]//2
for i in range(1,n):
    lcmn=(lcmn*a[i]//2)//gcd(lcmn,a[i]//2)
print((1+m//lcmn)//2)


Measured memory_bytes: 83936
#include<bits/stdc++.h>
#define GO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
const int N = 3e4 + 5;
const int M = 1e6 + 5;
const int Mod = 1e9 + 7;


int main()
{
	GO;
	string s;
	cin >> s;
	for (auto i : s)
		if (i == '7')
			return cout << "Yes\n", 0;
	cout << "No\n";
	return 0;
}

Measured memory_bytes: 3652
#include <cstdio>
using namespace std;
#define ll long long
const ll mod=1e9+7;
#define N 2001000

int x1,x2,x3,x4,x5,x6,y1,y2,y3,y4,y5,y6;
ll ans;
ll fac[N],inv[N];

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

inline ll F(int x,int y) {return fac[x+y]*inv[x]%mod*inv[y]%mod;}

ll cal1(int x,int y) {
	return ((F(x-x1+1,y-y1+1)-F(x-x2,y-y1+1)-F(x-x1+1,y-y2)+F(x-x2,y-y2))%mod+mod)%mod;
}

ll cal2(int x,int y) {
	return ((F(x6-x+1,y6-y+1)-F(x5-x,y6-y+1)-F(x6-x+1,y5-y)+F(x5-x,y5-y))%mod+mod)%mod;
}

int main()
{
	scanf("%d%d%d%d%d%d%d%d%d%d%d%d",&x1,&x2,&x3,&x4,&x5,&x6,&y1,&y2,&y3,&y4,&y5,&y6);
	fac[0]=1; for (int i=1;i<=2000000;i++) fac[i]=fac[i-1]*i%mod;
	inv[2000000]=power(fac[2000000],mod-2);
	for (int i=2000000-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
	for (int i=x3;i<=x4;i++) {
		ans=(ans-cal1(i,y3-1)*cal2(i,y3)%mod*(i+y3)%mod+mod)%mod;
		ans=(ans+cal1(i,y4)*cal2(i,y4+1)%mod*(i+y4+1)%mod)%mod;
	}
	for (int i=y3;i<=y4;i++) {
		ans=(ans-cal1(x3-1,i)*cal2(x3,i)%mod*(x3+i)%mod+mod)%mod;
		ans=(ans+cal1(x4,i)*cal2(x4+1,i)%mod*(x4+i+1)%mod)%mod;
	}
	printf("%lld\n",ans);
	return 0;
}

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

using namespace std;

const int mod = 1e9, N = 2e5 + 5;
const long long modll = 1e18;

char buf[N];

long long gcd(long long a, long long b) {
  return a ? gcd(b % a, a) : b;
}

int main() {
  int n;
  scanf("%d", &n);
  map<long long, long long> cnt;
  for (int i = 0; i < n; ++i) {
    scanf("%s", buf);
    int len = strlen(buf);
    long long cur = 0;
    int dig = 9;
    bool koma = false;
    for (int j = 0; j < len; ++j) {
      if (buf[j] == '.') {
        koma = true;
        continue;
      }
      cur = cur * 10 + (buf[j] - '0');
      dig -= koma;
    }
    for (int j = 0; j < dig; ++j) {
      cur *= 10;
    }
    cur = gcd(cur, modll);
    ++cnt[cur];
  }
  long long ans = 0;
  for (auto it : cnt) {
    for (auto oth : cnt) {
      if (oth.first < it.first) continue;
      int dua = 0, lima = 0;
      long long u = it.first;
      while ((u % 2) == 0) {
        u /= 2;
        ++dua;
      }
      while ((u % 5) == 0) {
        u /= 5;
        ++lima;
      }
      u = oth.first;
      while ((u % 2) == 0) {
        u /= 2;
        ++dua;
      }
      while ((u % 5) == 0) {
        u /= 5;
        ++lima;
      }
      if (min(dua, lima) < 18) continue;
      if (oth.first == it.first) {
        ans += it.second * (it.second - 1) / 2;
      } else {
        ans += it.second * oth.second;
      }
    }
  }
  printf("%lld\n", ans);
  return 0;
}


Measured memory_bytes: 3700
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b,c,d;
  cin >>a>>b>>c>>d;
  if ((a+b)>(c+d)) cout << "Left" <<endl;
  else if((a+b)<(c+d)) cout << "Right" << endl;
  else cout << "Balanced" <<endl;
}


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

int main()
{
  int n, count=0;
  cin >> n;
  string s;
  cin >> s;
  
  for(int i=2; i<=n; ++i)
  {
    if(s[i-2] == 'A' && s[i-1] == 'B' && s[i] == 'C')
    {
      count++;
    }
  }
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 384
// nb_9960
#include <bits/stdc++.h> 
using namespace std; 
#define fi(i,a,n) for (ll i=a; i < n; i++) 
#define ll long long
#define pb push_back 
#define mp make_pair 
#define F first 
#define S second 
#define all(x) x.begin(), x.end() 
#define clr(x) memset(x, 0, sizeof(x)) 
#define sortall(x) sort(all(x)) 
typedef pair<ll, ll> pl; 
typedef vector<ll> vl; 
typedef vector<pl> vpii; 
#define sz(a) int((a).size())
#define tr(c,i) for(typeof(c).begin() i = c.begin(); i != c.end(); i++)
#define present(c,x) (c.find(x) != c.end())
#define cpresent(c,x) (find(all(c),x) != c.end())

const int mod=1000000007;
ll a[100005];

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

  ll t = 1; 
  // cin >> t;

  while (t--) { 
    ll n;
    cin>>n;
    bool z=true;
    ll ans=1;
    if(n%2==0){
      fi(i,0,n){
        ll x;cin>>x;
        a[x]++;
        if(x>=n || x%2==0 ||a[x]>2){
          z=false;
          cout<<0<<endl;
          break;
        }
        if(a[x]==1)
        ans=(ans*2)%mod;
      }
    }else{
      fi(i,0,n){
        ll x;cin>>x;
        a[x]++;
        if(x>=n || x%2==1 ||a[0]>1 || a[x]>2){
          z=false;
          cout<<0<<endl;
          break;
        }
        if(a[x]==1 && x!=0)
        ans=(ans*2)%mod;
      }
    }
    if(z)
    cout<<ans<<endl;
  } 

  return 0; 
} 


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


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

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

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


























int main(){
    ll n;
    cin >> n;
    vector<ll> a(n), b(n);
    REP(i, n){
        cin >> a[i] >> b[i];
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    if(n % 2 == 0){
        cout << (b[n / 2] * 2 + b[n / 2 - 1] * 2) / 2 - (a[n / 2] * 2 + a[n / 2 - 1] * 2) / 2 + 1 << endl;
    }
    else{
        cout << b[n / 2] - a[n / 2] + 1 << endl;
    }
}


Measured memory_bytes: 6432
// #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<array<int, 3>> abc(N);

    rep(i, N) {
        nxt3(int, a, b, c);
        abc[i] = {a, b, c};
    }

    int dp[3][N + 1];
    dp[0][0] = 0;
    dp[1][0] = 0;
    dp[2][0] = 0;

    for (int i = 0; i < N; i++) {
        dp[0][i + 1] = abc[i][0] + max(dp[1][i], dp[2][i]);
        dp[1][i + 1] = abc[i][1] + max(dp[0][i], dp[2][i]);
        dp[2][i + 1] = abc[i][2] + max(dp[0][i], dp[1][i]);
    }

    cout << max({dp[0][N], dp[1][N], dp[2][N]}) << endl;

    return 0;
}


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

typedef vector< vector<int> > vvi;
typedef vector< vector<bool> > vvb;
typedef vector< vector<char> > vvc;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<char> vc;

int dtate[4]={-1,0,1,0};
int dyoko[4]={0,-1,0,1};

int bfs(const vvc &maze, vvi &arrive, vvi &pre, int sc, int sr, int H, int W){
    pair<int,int> a=make_pair(sr,sc);
    queue<pair<int,int>> que;
    que.push(a);
    arrive[sc][sr]=0;
    while(!que.empty()){
        pair<int,int> v=que.front();
        que.pop();
        for(int i=0;i<4;i++){
            int nextr=v.first+dyoko[i];
            int nextc=v.second+dtate[i];
            if(maze[nextr][nextc]=='#') continue;
            if(arrive[nextr][nextc]!=-1) continue;
            arrive[nextr][nextc]=1+arrive[v.first][v.second];
            pre[nextr][nextc]=(i+2)%4;
            //cout << nextr-v.first <<" " << nextc-v.second << endl;
            if(nextr==H&&nextc==W) return 1;
            pair<int,int> temp=make_pair(nextr,nextc);
            que.push(temp);
        }
    }
    return -1;
}

void rootcheck(int H, int W, vvi &pre, vvc &maze){
    maze[H][W]='#';
    int nowr=H,nowc=W;
    while(1){
        int dir=pre[nowr][nowc];
        nowr+=dyoko[dir];
        nowc+=dtate[dir];
        //cout << nowr << " now " << nowc << endl;
        maze[nowr][nowc]='#';
        if(nowr==1&&nowc==1) break;        
    }
    return;
}

int main(){
    int H,W;
    cin >> H >> W;
    vvc maze(H+2,vc(W+2,'#'));
    for(int i=1;i<=H;i++){
        for(int j=1;j<=W;j++){
            cin >> maze[i][j];
        }
    }
    vvi arrive(H+2,vi(W+2,-1));
    vvi pre(H+2,vi(W+2,-1));

    if(bfs(maze,arrive,pre,1,1,H,W)==-1){
        cout << -1 << endl;
        return 0;
    }
/*
    for(int i=1;i<=H;i++){
        for(int j=1;j<=W;j++){
            cout << pre[i][j] << " " ;
        }
        cout << endl;
    }
*/
    rootcheck(H,W,pre,maze);
/*
    for(int i=1;i<=H;i++){
        for(int j=1;j<=W;j++){
            cout << maze[i][j] << " " ;
        }
        cout << endl;
    }
*/



    int ans=0;
    for(int i=1;i<=H;i++){
        for(int j=1;j<=W;j++){
            if(maze[i][j]=='.') ans++;
        }
    }
    cout << ans << endl;   
    
    
}

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

using ll = long long;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int r, c, k;
  cin >> r >> c >> k;
  
  vector<vector<ll>> item(r, vector<ll>(c));
  vector<vector<vector<ll>>> dp(r + 100, vector<vector<ll>>(c + 100, vector<ll>(4, 0)));
 /* ll dp[3100][3100][4];
  for (int i = 0; i < r + 100; i++) {
    for (int j = 0; j < c + 100; j++) {
      for (int ii = 0; ii < 4; ii++) {
        dp[i][j][ii] = 0;
      }
    }
  }*/
  
  for (int i = 0; i < k; i++) {
    ll x, y, z;
    cin >> x >> y >> z;
    x--;
    y--;
    item[x][y] = z;
  }
  
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
      for (int ii = 0; ii < 4; ii++) {
        if (item[i][j] == 0) {
          dp[i][j + 1][ii] = max(dp[i][j + 1][ii], dp[i][j][ii]);
          dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][ii]);
        }
        else {
          dp[i][j + 1][ii] = max(dp[i][j + 1][ii], dp[i][j][ii]);
          dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][ii]);
          if (ii < 3) {
            dp[i][j + 1][ii + 1] = max(dp[i][j + 1][ii + 1], dp[i][j][ii] + item[i][j]);
            dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][ii] + item[i][j]);
          }
        }
      }       
    }
  }
  
  ll ans = 0;
  for (int i = 0; i <= r; i++) {
    for (int j = 0; j <= c; j++) {
      for (int ii = 0; ii < 4; ii++) {
        ans = max(ans, dp[i][j][ii]);
      }       
    }
  }
  
  cout << ans << '\n';
}

Measured memory_bytes: 749020
// ARC090F.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5e7 + 200, mod = 1e9 + 7;

int n, f[MAX_N];

int fpow(int bas, int tim)
{
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % mod;
        bas = 1LL * bas * bas % mod;
        tim >>= 1;
    }
    return ret;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i < MAX_N; i++)
        f[i] = f[i / 10] + 1;
    int ans = 0;
    for (int i = 1, j = 1, sum = 0; i < 1e7; i++)
    {
        while (sum < n)
            sum += f[j++];
        if (sum == n)
            ans++;
        sum -= f[i];
    }
    for (int i = 1; i <= n / 8; i++)
    {
        if (n % i == 0)
            // y == 0, t = n / i;
            ans = (0LL + ans + (0LL + fpow(10, n / i) + mod - (fpow(10, (n / i) - 1) + i - 1) % mod) % mod) % mod;
        else
            ans = (0LL + ans + 1) % mod;
    }
    printf("%d\n", ans);
    return 0;
}

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

ll N , M ;
cin >> N >> M ;
vector<int> A(N) ;  
rep(i,N) cin >> A.at(i) ;
ll dp[200020] ;
  dp[0] = 0 ;
//dp[i] i 番目の人が押したあとにシャワーの出る秒数
for(int i = 1 ; i < N ; i++ ){
  if( A.at(i) > A.at(i-1) + M ) dp[i] = dp[i-1] + M ;
   else dp[i] = A.at(i)-A.at(i-1)+dp[i-1] ;
}
  cout << dp[N-1]+ M << endl;
}

Measured memory_bytes: 2560
#include<stdio.h>
int main(){
  int w,h,x,y,r;
  scanf("%d %d %d %d %d",&w,&h,&x,&y,&r);
  if(x>=r&&y>=r&&x<=w-r&&y<=h-r){
    printf("Yes\n");
  }else{
    printf("No\n");
  }
  return 0;
}


Measured memory_bytes: 2140
// D.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, char *argv[])
{
	cout.precision(10);
	int n, elapsed = 0, speed = 0, x;
	double ans = 0;
	cin >> n;
	vector<int> t(n), v(n);
	for (int i = 0; i < n; ++i) {
		cin >> x;
		elapsed += x;
		t[i] = elapsed;
	}
	for (int i = 0; i < n; ++i) {
		cin >> v[i];
	}
	t.push_back(t.back());
	v.push_back(0);
	elapsed = 0;
	for (int i = 0; i <= n; ++i) {
		for (; elapsed < t[i]; ++elapsed) {
			int next = min(speed + 1, v[i]);
			for (int k = i + 1; k <= n; ++k) {
				next = min(next, v[k] + t[k - 1] - elapsed - 1);
			}
			ans += speed + (next - speed) * 0.125;
			if (speed == next && speed < v[i]) {
				ans += 0.25;
			}
			speed = next;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please



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


	int N, A[4];
	int L[8];
	cin >> N >> A[1] >> A[2] >> A[3];
	rep(i, N) cin >> L[i];

	int kazu = 1 << (N * 2);

	int saishou = 1e9;
	rep(i, kazu) {
		int M[4] = {};
		int LL[4] = {};
		rep(j, N) {
			int k = i >> (j * 2) & 1;
			k *= 2;
			k += i >> (j * 2 + 1) & 1;
			M[k]++;
			LL[k] += L[j];
		}
		if (M[1] && M[2] && M[3]) {
			int cost = 0;
			rep1(j, 3) {
				cost += (M[j] - 1) * 10;
				cost += abs(LL[j] - A[j]);
			}
			saishou = min(saishou, cost);
		}
	}

	co(saishou);

	Would you please return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cassert>
#define Inf 1000000000
#define nmax_def 110000
#define mod 1000000007
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;

vl pow_;
void pow_ini(ll n) {
	pow_.push_back(n);
	rep(j, 62) {
		ll nxt = pow_[j] * pow_[j];
		nxt %= mod;
		pow_.push_back(nxt);
	}
	return;
}

ll pow1(ll k) {
	ll ans = 1;
	rep(ntmp, 62) {
		if ((k >> ntmp) % 2 == 1) {
			ans *= pow_[ntmp];
			ans %= mod;
		}
	}
	return ans;
}

vl fact;
vl fact_inv;

void fact_ini(ll n) {
	fact.push_back(1);
	fact.push_back(1);
	for (ll i = 2; i <= n; i++) {
		ll fact_tmp = fact[i - 1] * i;
		fact_tmp %= mod;
		fact.push_back(fact_tmp);
	}
	fact_inv.resize(n + 1);
	pow_ini(fact[n]);
	fact_inv[n] = pow1(mod - 2);
	for (ll i = n - 1; i >= 0; i--) {
		fact_inv[i] = fact_inv[i + 1] * (i + 1);
		fact_inv[i] %= mod;
	}
}

ll nCm(ll n, ll m) {
  	if(fact.size()<=n)
      assert(false);
  	if(fact.size()<=m)
      assert(false);
	ll ans = fact[n] * fact_inv[m];
	ans %= mod;
	ans *= fact_inv[n - m];
	ans %= mod;
	return ans;
}

int main() {
	fact_ini(11000000);
	ll r1, c1, r2, c2;
	cin >> r1 >> c1 >> r2 >> c2;
	if (r2 - r1 < c2 - c1) {
		swap(r1, c1);
		swap(r2, c2);
	}
	ll anstmp = nCm(r1 + c1, r1);
	ll ans = anstmp;
	rep(i, r2 + c2 - r1 - c1) {
		anstmp = anstmp * 2;
		anstmp %= mod;
		if (i < c2 - c1) {
			anstmp += nCm(r1 + c1 + i, c1 + i + 1);
			anstmp += nCm(r1 + c1 + i, c1 - 1);
		}
		else if (i < r2 - r1) {
			anstmp -= nCm(r1 + c1 + i, c2);
			anstmp += nCm(r1 + c1 + i, c1 - 1);
			anstmp += mod;
		}
		else {
			anstmp -= nCm(r1 + c1 + i, c2);
			anstmp -= nCm(r1 + c1 + i, r2);
			anstmp += mod;
			anstmp += mod;
		}
		anstmp %= mod;
		ans += anstmp;
		ans %= mod;
	}
	cout << ans << endl;


	return 0;
}


Measured memory_bytes: 174168
n = int(input())
w = [input() for i in range(n)]
if n != len(set(w)):
  print("No")
else:
  for i in range(n-1):
    if w[i][-1] == w[i+1][0]:
      continue
    else:
      print("No")
      break
  else:
    print("Yes")

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

int main(){
  int n,ans=100000;
  cin>>n;
  while(n--){
    ans*=1.05;
    if(ans%1000>0){
      ans/=1000;
      ans*=1000;
      ans+=1000;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3080
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(ll i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(ll i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using PP=pair<ll,P>;
using vp=vector<P>;
using vpp=vector<PP>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
int main(){
    int V;
    cin>>V;
    vvi G(V);
    REP(i,V-1){
        int a,b;
        cin>>a>>b;
        a--;b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    vi a(V,INF);
    vi b(V,INF);
    queue<int> que;
    que.push(0);
    a[0]=0;
    while(que.size()){
        int p=que.front();que.pop();
        REP(i,G[p].size()){
            int v=G[p][i];
            if(a[v]>a[p]+1){
                a[v]=a[p]+1;
                que.push(v);
            }
        }
    }
    que.push(V-1);
    b[V-1]=0;
    while(que.size()){
        int p=que.front();que.pop();
        REP(i,G[p].size()){
            int v=G[p][i];
            if(b[v]>b[p]+1){
                b[v]=b[p]+1;
                que.push(v);
            }
        }
    }
    int p=0,q=0;
    REP(i,V){
        if(a[i]<=b[i]){
            p++;
        }else{
            q++;
        }
    }
    if(p>q){
        cout<<"Fennec"<<endl;
    }else{
        cout<<"Snuke"<<endl;
    }
    return 0;
}

Measured memory_bytes: 6528
hash = {}

a = gets.to_i
if a != 0
  	(0..a-1).each do |n|
    	st = gets
    	if hash[st] != nil
    	  	hash[st] = hash[st] + 1
    	else 
      		hash[st] = 1
    	end
	end
end
b = gets.to_i
if b != 0
	(0..b-1).each do |n|
      st = gets
      if hash[st] != nil
          hash[st] = hash[st] - 1
      else 
          hash[st] = -1
      end
	end
end
print ([hash&.values&.max.to_i, 0].max)


Measured memory_bytes: 1788
# coding=utf-8
import math


def solve_worst(number_1, number_2):
    cases = 0
    if number_1 < number_2:
        number_1, number_2 = number_2, number_1

    if (number_1 * number_2) % (number_1 + 1) == 0:
        max_2 = number_1 * number_2 // (number_1 + 1) - 1
    else:
        max_2 = number_1 * number_2 // (number_1 + 1)
    cases += max_2

    min_sqrt = math.floor(math.sqrt(number_1 * number_2))
    if min_sqrt == number_2:
        min_sqrt = number_2 + 1
    cases += min_sqrt - number_2

    if (number_1 * number_2) % min_sqrt == 0:
        max_1 = number_1 * number_2 // min_sqrt - 2
    else:
        max_1 = number_1 * number_2 // min_sqrt - 1

    cases += max_1

    return cases


if __name__ == '__main__':
    Q = int(input())
    for i in range(Q):
        A, B = map(int, input().split())
        worst_cases = solve_worst(A, B)
        print(worst_cases)


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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { cout << #a << " = " << a << endl; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T> void operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) cin >> e; }

typedef long long ll;
int const inf = 1<<29;

int main() {

  ll X; cin >> X;
  for (int i = 1; ; i++) {
    if (2 * X <= i * (i + 1)) {
      auto K = i * (i + 1) / 2;
      assert(K - X < i);
      std::cout << i << "\n";
      return 0;
    }
  }
  
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
int main()
{
	// freopen("AGC015-D.in", "r", stdin);
	long long l, r; 
	scanf("%lld%lld", &l, &r);
	if (l == r)
	{
		puts("1");
		return 0;
	}
	auto k = l ^ r;
	while (k != (k & -k))
		k ^= k & -k;
	l &= k * 2 - 1;
	r &= k - 1;
	while (r != (r & -r))
		r ^= r & -r;
	if (r)
		r = r * 2 - 1;
	printf("%lld\n", r < l ? 2 * (k - l) + r + 1 : 2 * k - l);
	return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
int r,c;
vector<vector<char>> grid;
vector<vector<ll>> dp;

void print()
{
    for(int i=1; i<=r; i++){
        for(int j=1; j<=c; j++){
            cout << dp[i][j] << " ";
        }
        cout << '\n';
    }
    cout << '\n';
}

inline bool is_safe(int i, int j)
{
    return (i>=1 && j>=1 && i<=r && j<=c && grid[i][j]!='#');
}

void init()
{
    grid.resize(r+1, vector<char>(c+1));
    dp.resize(r+1, vector<ll>(c+1));
}

void solve()
{
    for(int i=1; i<=c; i++) {
        if(is_safe(1, i)) 
            dp[1][i] = 1;
        else break;
    }
    for(int j=1; j<=r; j++) {
        if(is_safe(j, 1))
            dp[j][1] = 1;
        else break;
    }
    for(int i=2; i<=r; i++){
        for(int j=2; j<=c; j++){
            if(is_safe(i, j)){
                if(is_safe(i-1, j)) dp[i][j] = (dp[i][j] + dp[i-1][j])%mod;
                if(is_safe(i, j-1)) dp[i][j] = (dp[i][j] + dp[i][j-1])%mod;
            }
        }
    }
    cout << dp[r][c] << '\n';
}

int main()
{
    cin >> r >> c;
    init();
    for(int i=1; i<=r; i++){
        for(int j=1; j<=c; j++){
            cin >> grid[i][j];
        }
    }

    solve();
    return 0;
}

Measured memory_bytes: 12108
N,M = map(int, input().split())

memo = [False]*N
result = False

for i in range(M):
  a,b = map(int, input().split())
  if a == 1:
    result |= memo[b]
    memo[b] = True
  elif b == N:
    result |= memo[a]
    memo[a] = True

print('POSSIBLE' if result else 'IMPOSSIBLE')

Measured memory_bytes: 4596
//#include <bits/stdc++.h>
#include <stack>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	//入力
	long A[100001], B[100001], x[100001] = {};
	string S = {};
	char W[101] = {};
	bool f[101] = {};
	stack<pair<int, int>> dfs;
	long N = 0, K = 0, T = 0, M = 1000000000, ans = 0, l = 0, r = 0, sum = 0, a = 0, b = 0, c = 0;
	cin >> S;
	//処理
	W[0] = S[0];
	x[0]++;

	if (W[0] == S[1]) x[0]++;
	else {
		x[1]++;
		W[1] = S[1];
	}

	if (W[0] == S[2]) {
		x[0]++;
	}
	else if (x[1] == 0) {
		x[1]++;
      	W[1] = S[2];
	} else if (W[1]==S[2]){
      x[1]++;
    }

	if (W[0] == S[3]) {
		x[0]++;
	}
	else if (W[1] == S[3]) {
		x[1]++;
	}
	//出力
	if (x[0] == 2 && x[1] == 2) {
		cout << "Yes" << endl;
	}
	else cout << "No" << endl;
	//cout << W[0]<<S[3] << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)
#define pcnt __builtin_popcountll
#define rng(a) a.begin(), a.end()
#define sz(x) (int)(x).size()
#define v(T) vector<T>
#define vv(T) v(v(T))

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;

template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) {if (a > b) { a = b; return true; } return false; }

ll INF = 1001001001;
ll LINF = 1001001001001001001ll;

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

    string s;
    cin>>s;
    int n = sz(s);
    map<char, vector<int>> mp;
    rep(i, n) {
        mp[s[i]].push_back(i);
    }
    int ans = INF;
    for (auto v : mp) {
        v.second.push_back(n);
        int m = sz(v.second);
        int d = v.second[0];
        rep(i, m - 1) {
            chmax(d, v.second[i + 1] - v.second[i] - 1);
        }
        chmin(ans, d);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
int main()
{
	int a = 0, b = 0, c = 0, d = 0, e = 0, min = 0, ma = 0, ans = 0, ansb = 0, count = 0,countb, crowdy[101] = {},  bu = 0;
	int reset = 0,w=0;
	char hairetu[200] = {};
	int number[10000], price[10000], sort[100000] = {}, kisu[10000] = { 100000 }, gusu[10000] = { 100000 };
	using namespace std;
	int x = 0, y = 0, z = 0, play[200] = {}, acount = 0, bcount = 0;
	std::string toki, tokit, fun,funt;
	int cake = 4, cookie = 7;
	bool okada=true;
	cin >> a ;

		for (int i = 0; i <= 15; i++) {
			count = 0;
			count = cookie * i;

			for (int j = 0; j <= 25; j++) {
				countb = 0;
				countb = cake * j;
				if (countb + count == a) {
					okada = false;
				}
		
			}

		}
	
	if (okada) {
		cout << "No" << endl;
	}
	else {
		cout << "Yes" << endl;
	}

	}

		
	


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef pair<l_l,ll> lll;
typedef vector<string> vs;
const ll dx[4]={1,-1,0,0};
const ll dy[4]={0,0,1,-1};
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=1010010010010010000;
template<class T> inline bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod){}
mint operator-() const { return mint(-x);}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
mint res(*this);
return res+=a;
}
mint operator-(const mint a) const {
mint res(*this);
return res-=a;
}
mint operator*(const mint a) const {
mint res(*this);
return res*=a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return (*this) *= a.inv();
}
mint operator/(const mint a) const {
mint res(*this);
return res/=a;
}
};
//グリッド：（典型）dp,dfs,bfs,最短経路,その他
mint dp[110000][110][2];
int main(){
    string s;cin>>s;
    ll d;cin>>d;
    ll n=sz(s);
    dp[0][0][1]=1;
    rep(i,n){
        rep(j,d){
            rep(k,10){
                dp[i+1][(j+k)%d][0]+=dp[i][j][0];
                if(k<(s[i]-'0'))dp[i+1][(j+k)%d][0]+=dp[i][j][1];
            }
            dp[i+1][(j+(s[i]-'0'))%d][1]+=dp[i][j][1];
        }
    }
    mint ans=dp[n][0][0]+dp[n][0][1];
    ans-=1;
    cout<<ans.x<<endl;
    return 0;
}

Measured memory_bytes: 192684
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define IT iterator
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
#define debug puts("wzpakking")
#define y1 ysghysgsygsh
using namespace std;
char s[200005];
int n;
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	For(i,1,n) if (s[i]=='?'&&s[i-1]=='P') s[i]='D';
	For(i,1,n) if (s[i]=='?')
		if (s[i-1]=='P') s[i]='D';
		else if (s[i+1]=='?'||s[i+1]=='D') s[i]='P';
		else s[i]='D';	
	printf("%s\n",s+1);
}

Measured memory_bytes: 3852
#include <stdio.h>
#include <limits.h>

int main(){
	int n, a;
	long long sum = 0;
	int min = INT_MAX;
	int max = INT_MIN;

	scanf("%d", &n);
	
	for(; n>0; n--){
		scanf("%d ", &a);
		sum += a;
		if(a < min){
			min = a;
		}
		if(a > max){
			max = a;
		}
	}

	printf("%d %d %lld\n", min, max, sum);
}

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

#define X first
#define Y second
#define mp make_pair
#define pb pop_back
#define eb emplace_back
#define sz(v) (int) v.size()

using namespace std;

typedef long long LL;
typedef long double LD;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int MAX_N = 105;

int x[MAX_N], y[MAX_N];

void solve() {
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> x[i] >> y[i];
	}
	vector <int> p(n);
	iota(p.begin(), p.end(), 0);
	LL ans = 0;
	while (clock() / CLOCKS_PER_SEC < 1.5) {
		shuffle(p.begin(), p.end(), rnd);
		LL dist = 0;
		pair <int, int> P = {0, 0};
		for (auto &i : p) {
			pair <int, int> newP = {P.X + x[i], P.Y + y[i]};
			LL curr = 1LL * newP.X * newP.X + 1LL * newP.Y * newP.Y;
			if (curr > dist) {
				dist = curr;
				P = newP;
			}
		}
		ans = max(ans, dist);
	}
	cout << sqrt((LD) ans) << "\n";
}

signed main() {
// #define TASK ""
#if !defined(LOCAL) && defined(TASK)
	freopen(TASK".in", "r", stdin);
	freopen(TASK".out", "w", stdout);
#endif
	ios::sync_with_stdio(0); cin.tie(0);
	cout << fixed << setprecision(20);
	int tests = 1;
	// cin >> tests;
	while (tests--) {
		solve();
	}
	return 0;
}

Measured memory_bytes: 384
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define MN 100005
using namespace std;
inline int in(){
    int x=0;bool f=0;char c;
    for (;(c=getchar())<'0'||c>'9';f=c=='-');
    for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');
    return f?-x:x;
}
struct pt{
	int x,y,id;
}a[MN];
struct edge{
	int to,nxt;
}e[MN<<3];
ll res;
int h[MN],sum[MN];
int n,A,B,d,x,y,cnt;
bool vis[MN];
inline void ins(int x,int y){
	e[++cnt].to=y;e[cnt].nxt=h[x];h[x]=cnt;
}
inline bool cmp(pt a,pt b){
	return (a.x==b.x)?a.y<b.y:a.x<b.x;
}
inline void sol(int D){
	sort(a+1,a+n+1,cmp);
	for (int i=1,j=1,hd=1,tl=1;i<=n;++i){
		while (hd<=n&&(a[i].x-a[hd].x>d||(a[i].x-a[hd].x==d&&a[i].y-a[hd].y>D))) ++hd;
		while (tl<=n&&(a[i].x-a[tl].x>d||(a[i].x-a[tl].x==d&&a[i].y-a[tl].y>=-D))) ++tl;
		sum[a[i].id]+=tl-hd;j=max(j,hd);if (j>=tl) continue;
		ins(a[i].id,a[j].id);ins(a[j].id,a[i].id);
		for (;j+1<tl;j++)
		ins(a[j].id,a[j+1].id),ins(a[j+1].id,a[j].id);
	}
}
inline void dfs(int u){
	for (int i=h[u];i;i=e[i].nxt){
		int v=e[i].to;
		if (vis[v]) continue;
		vis[v]=1;res+=1ll*sum[v];dfs(v);
	}
}
int main()
{
	n=in();A=in();B=in();
	for (int i=1;i<=n;++i){
		x=in();y=in();
		a[i].x=x+y;a[i].y=y-x;a[i].id=i;
	}d=max(abs(a[A].x-a[B].x),abs(a[A].y-a[B].y));sol(d);
	for (int i=1;i<=n;++i) swap(a[i].x,a[i].y);
	sol(d-1);res=1ll*sum[A];vis[A]=1;dfs(A);
	printf("%lld",res);return 0;
}

Measured memory_bytes: 9472
import itertools
n = int(input())
xy = []
for i in range(n):
	x,y = map(int,input().split())
	xy.append([x,y])

all_len = 0
p = list(itertools.permutations(range(n)))
for k in range(len(p)):
	for i in range(n-1):
		xi = xy[p[k][i]][0]
		xj = xy[p[k][i+1]][0]
		yi = xy[p[k][i]][1]
		yj = xy[p[k][i+1]][1]
		all_len += ((xi - xj)**2 + (yi - yj)**2)**0.5

print(all_len/len(p))

Measured memory_bytes: 8052
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << '\n';
#define CFYN(n) cout << ( (n) ? "YES":"NO") << '\n';
#define OUT(n) cout << (n) << '\n';
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(void)
{
    IOS
    int n; cin >> n;
    vector<pii> v(n);
    vector<pii> vrl(n);
    
    REP(i,n) {
        cin >> v[i].first >> v[i].second;
        vrl[i].first = v[i].first + v[i].second;
        vrl[i].second = v[i].first - v[i].second;
    }
    sort(ALL(vrl));
    int ans = n;
    int l = 0,r = 1;
    while(r < n) {
        if (vrl[l].first > vrl[r].second) ans--;
        else l = r;
        r++;
    }

    cout << ans << '\n';


    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
using namespace std;

//ループマクロ
#define FOR(i , a , b)  for(int i = (a) ; i < (b) ; i++)
#define REP(i , n)      for(int i = 0 ; i < n ; i++)
#define REPR(i , n)     for(int i = n ; 0 <= i ; i--)
#define ROP(i, n)       for(int i = 1 ; i <= n ; i++)

//入出力
#define SCOUT(x) cout << (x) << " "
#define VECCIN(x) for(auto& ele : (x) ) cin >> ele
#define VECOUT(x) for(auto& ele : (x) ) cout << ele << " "; cout << endl;

//その他
#define ALL(obj) (obj).begin() , (obj).end() 
#define SORT(obj) sort(ALL(obj))
#define GSORT(obj) sort(ALL(obj) , greater<int>())
#define P pair<int , int>
#define V vector<int>
#define VLL vector<long long>
#define M map<int, int>
#define S set<int>
#define PQ priority_queue<int>
#define PQG priority_queue<int , V , greater<int>>

#define MAX_H 1000
#define MAX_W 1000


int main(void) {

	ios::sync_with_stdio(false);	cin.tie(0);

    ll k, a, b;  cin >> k >> a >> b;
    if(k < a || b - a < 2){  cout << k + 1 << endl;  return 0;  }

  	ll ans = a;
    k -= a-1;
    ans += k / 2 * (b-a) + k % 2;

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


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

using namespace std;

typedef long long ll;

ll mod(ll x,ll m){
  return (m+x%m)%m;
}

void extgcd(ll a,ll b,ll &x,ll &y){
  x=1,y=0;
  if(b!=0)extgcd(b,a% b,y,x),y-=(a/b)*x; 
}

ll mod_inv(ll a,ll m){
  ll x,y;
  extgcd(a,m,x,y);
  return mod(x,m);
}

ll m1=999979,m2=999983;

ll calc(ll x,int o,ll y){
  ll a=0,b=0,p,q;

  if(o==1)a=mod(x+y,m1),b=mod(x+y,m2);
  if(o==2)a=mod(x-y,m1),b=mod(x-y,m2);
  if(o==3)a=mod(x*y,m1),b=mod(x*y,m2);
  if(o==4)a=mod(x*mod_inv(y,m1),m1),b=mod(x*mod_inv(y,m2),m2);
  
  extgcd(m1,m2,p,q);
  
  return (b*m1*p+a*m2*q)%(m1*m2);
}

int main(void){
  ll n,o,x=0,y;

  cin >> n;

  while(n--){
    cin >> o >> y;
    x=calc(x,o,y);
  }
  cout << x << endl;
  return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define mem( a , b ) memset( a , b , sizeof( a ) )
using namespace std;
int _I(){ int x; scanf("%d",&x); return x; }
long long _IL(){ long long x; scanf("%lld",&x); return x; }


struct node
{
        int v , w;
        node(){};
        node( int x , int y )
        {
                v = x;
                w = y;
        }

        bool operator < ( const node &R ) const
        {
                if( w == R.w ) return v < R.v;
                return w > R.w;
        }
};

long long mod;
long long bigmod( long long b , long long p )
{
        if( p == 0 ) return 1LL;
        long long r = bigmod( 2 , p/2 );
        r = ( ( r % mod ) * ( r % mod ) ) % mod;
        if( p & 1 )
        {
                r = ( ( b % mod ) * ( r % mod ) ) % mod;
        }
        return r;
}
vector< int > s1 , s2;
vector< pair< int , int > > divisor;
map< int , int > mp;
void solve()
{
       set< char > _st;
       string s;
       cin>>s;
       if( s[ 0 ] == s[ 1 ] && s[ 1 ] == s[ 2 ] )
       {
               cout<<"No\n";
       }
       else cout<<"Yes\n";
}
int main()
{
        //freopen("input.txt","r",stdin);
        //freopen("output.txt","w",stdout);
       // int t = _I();
        //while( t-- )
                solve();

        return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);

		int N = scanner.nextInt();
		int M = scanner.nextInt();

		long[] xi = new long[N];
		long[] yi = new long[N];
		long[] zi = new long[N];

		for (int i = 0; i < N; i++) {
			xi[i] = scanner.nextLong();
			yi[i] = scanner.nextLong();
			zi[i] = scanner.nextLong();
		}

		long[] total = new long[N];
		for(int i = 0; i< N;i++) {
			total[i]=xi[i]+yi[i]+zi[i];
		}



		long[] total000 = new long[N];
		long[] total001 = new long[N];
		long[] total010 = new long[N];
		long[] total011 = new long[N];
		long[] total100 = new long[N];
		long[] total101 = new long[N];
		long[] total110 = new long[N];
		long[] total111 = new long[N];


		for (int i = 0; i < total000.length; i++) {
			total000[i] = -xi[i]-yi[i]-zi[i];
		}
		for (int i = 0; i < total001.length; i++) {
			total001[i] = -xi[i]-yi[i]+zi[i];
		}
		for (int i = 0; i < total010.length; i++) {
			total010[i] = -xi[i]+yi[i]-zi[i];
		}
		for (int i = 0; i < total011.length; i++) {
			total011[i] = -xi[i]+yi[i]+zi[i];
		}
		for (int i = 0; i < total100.length; i++) {
			total100[i] = xi[i]-yi[i]-zi[i];
		}
		for (int i = 0; i < total101.length; i++) {
			total101[i] = xi[i]-yi[i]+zi[i];
		}
		for (int i = 0; i < total110.length; i++) {
			total110[i] = xi[i]+yi[i]-zi[i];
		}
		for (int i = 0; i < total111.length; i++) {
			total111[i] = xi[i]+yi[i]+zi[i];
		}



		Arrays.sort(total000);
		Arrays.sort(total001);
		Arrays.sort(total010);
		Arrays.sort(total011);
		Arrays.sort(total100);
		Arrays.sort(total101);
		Arrays.sort(total110);
		Arrays.sort(total111);

		long score000 = getTotal(total000,M);
		long score001 = getTotal(total001,M);
		long score010 = getTotal(total010,M);
		long score011 = getTotal(total011,M);
		long score100 = getTotal(total100,M);
		long score101 = getTotal(total101,M);
		long score110 = getTotal(total110,M);
		long score111 = getTotal(total111,M);

		long max = Long.MIN_VALUE;
		max = (max > score000)?max : score000;
		max = (max > score001)?max : score001;
		max = (max > score010)?max : score010;
		max = (max > score011)?max : score011;
		max = (max > score100)?max : score100;
		max = (max > score101)?max : score101;
		max = (max > score110)?max : score110;
		max = (max > score111)?max : score111;

		System.out.println(max);



	}

	public static long getTotal(long[] ar,int m) {
		long ans = 0;
		for (int i = 0; i < m; i++) {
			ans += ar[ar.length-i-1];
		}
		return ans;
	}

}


Measured memory_bytes: 28484